Nội dung bài viết này trình bày về lý thuyết tạo và và kiểm tra CRC. Phương pháp thực hiện mạch tính CRC nối tiếp. Đồng thời, bài viết đưa ra một RTL code tính CRC có thể lựa chọn độ dài đa thức sinh (generator polynomial) trước khi tổng hợp và gán giá trị đa thức sinh mong muốn khi sử dụng.
1. Tổng quan
Việc truyền một dữ liệu trong một môi trường từ điểm này đến điểm khác, ví dụ như truyền dữ liệu giữa hay máy tính trong một mạng, luôn tiềm ẩn nhiều yếu tố làm dữ liệu truyền bị sai. Cơ chế phát hiện lỗi dữ liệu là không thể thiếu đối với các giao thức có độ tin cậy cao.
Phương pháp chung để kiểm tra lỗi dữ liệu là thêm các bit kiểm tra kèm theo dữ liệu được truyền theo một quy tắc đã được quy định trước. Bộ truyền dữ liệu sẽ tạo ra các bit kiểm tra từ giá trị dữ liệu cần truyền và gắn nó với dữ liệu truyền. Bộ nhận sẽ nhận dữ liệu và tính toán lại các bit kiểm tra để so sánh với các bit kiểm tra mà nó nhận được. Nếu hai kết quả khác nhau thì đây là một lỗi.
Một phương pháp kiểm tra đơn giản đó chính là sử dụng parity bit. Parity bit là phương pháp sử dụng 1 bit để kiểm tra số bit "1" hoặc "0" của chuỗi dữ liệu là "chẵn" hoặc "lẻ". Ví dụ sau đây minh họa việc kiểm tra parity chẵn, tổng số bit 1 trong chuỗi được truyền đi bao gồm cả dữ liệu và bit kiểm tra luôn là một số chẵn.
- Tạo bit parity: XOR tất cả các bit dữ liệu
- Kiểm tra parity: XOR tất cả các bit dữ liệu và bit parity. Nếu giá trị là 1 thì chuỗi dữ liệu nhận bị sai.
Một số điểm cần lưu ý:
- Bit sai có thể là bit dữ liệu hoặc bit parity
- Chỉ phát hiện được nếu số bit sai là số lẻ (sai 1, 3, 5, 7, ... bit)
 |
| Hình 1. Tạo và kiểm tra Parity chẵn cho chuỗi dữ liệu 8 bit |
Phương pháp kiểm tra parity đơn giản nhưng độ tin cậy kém nên được ứng dụng cho các giao thức có tốc độ truyền dữ liệu chậm hoặc số lượng bit dữ liệu cần kiểm tra ít ví dụ như giao thức UART.
CRC (Cyclic Redundancy Code) là một phương pháp phổ biến có độ tin cậy cao hơn nhiều so với sử dụng bi parity. CRC được ứng dụng trong nhiều giao thức có khối lượng dữ liệu truyền lớn hoặc tốc độ truyền dữ liệu cao như CAN, Ethernet, giao tiếp RF 15693, ...
2. Lý thuyết về tính toán CRC
Giá trị chuỗi bit kiểm tra hay chuỗi CRC là số dư của phép chia của chuỗi bit dữ liệu cho một chuỗi bit đa thức sinh (Generator Polynomial). Đa thức sinh là số chia sẽ khác nhau tùy vào mỗi giao thức quy định. Phép chia trong tính toán CRC sử dụng cách tính modulo-2. Modulo-2 thực chất là XOR hai số hạng.
Giả sử đa thức chuỗi dữ liệu cần truyền là M(x):
Giả sử đa thức chuỗi dữ liệu cần truyền là M(x):
Đa thức sinh là G(x):
Trong đó:
- am và an bằng 1 hoặc 0
- Độ dài chuỗi CRC bằng độ dài đa thức sinh trừ 1 và bằng số mũ lớn nhất của đa thức sinh và bằng n.
Điều này, tương ứng với việc dịch trái n bit chuỗi dữ liệu M(x).
Cuối cùng, chia T(x) cho G(x) và lấy số dư. Số dư chính là chuỗi CRC n bit.
Kiểm tra CRC được thực hiện bằng 1 trong 2 cách sau:
- Lấy chuỗi dữ liệu có cả các bit kiểm tra CRC chia cho đa thức sinh. Nếu số dư khác "0" thì dữ liệu nhận bị lỗi.
- Tách chuỗi dữ liệu và chuỗi CRC riêng. Chỉ lấy chuỗi dữ liệu chia cho đa thức sinh rồi lấy số dư phép chia so sánh với chuỗi CRC. Nếu hai chuỗi khác nhau thì dữ liệu nhận bị lỗi.
Ví dụ về tính toán CRC-4, tương ứng với số bit kiểm tra là 4 bit, với đa thức sinh như sau:
x^4 + x + 1 (b10011)
Chuỗi dữ liệu cần truyền có 8 bit như sau:
x^7 + x^5 + x (b1010_0010)
Chuỗi dữ liệu trước khi chia sẽ được mở rộng thêm 4 bit "0":
x^11 + x^9 + x^5 (b1010_0010_0000)
 |
| Hình 2. Tính chuỗi CRC |
Việc kiểm tra CRC được thực hiện trên chuỗi dữ liệu có đính kèm CRC như sau:
 |
| Hình 3. Kiểm tra CRC - trường hợp nhận đúng, số dư bằng 0 |
 |
| Hình 4. Kiểm tra CRC bằng cách chia chuỗi dữ liệu có CRC với đa thức sinh - trường hợp sai 1 bit và trường hợp sai 2 bit, số dư khác 0 |
Bộ nhận sẽ không phát hiện được lỗi dữ liệu khi chuỗi dữ liệu bị sai và chuỗi CRC cũng sai trùng với giá trị CRC của chuỗi dữ liệu bị sai. Tuy nhiên, xác suất để xảy ra đúng trường hợp này là thấp. Xác suất này càng thấp khi chuỗi CRC càng dài.
 |
| Hình 6. Kiểm tra CRC không phát hiện được lỗi khi cả dữ liệu và CRC cùng sai đồng thời |
Xét đa thức sinh g(x) = x + 1, đây là đa thức CRC-1, tính CRC cho chuỗi 8 bit b10100010 và chuỗi b10011111.
 |
| Hình 7. Tính CRC-1 |
So sánh kết quả với phương pháp tính parity chẵn đã trình bày phía trên chúng ta có thể nhận thấy sự tương đồng. CRC-1 chính là phương pháp kiểm tra parity.
3. Mạch nguyên lý tính CRC
Xem lại các ví dụ đã trình bày trên đây, CRC được tính theo nguyên tắc:
- Nếu bit MSB của lần tính hiện tại bằng 1 thì nó sẽ được XOR (modulo-2) với đa thức sinh
- Nếu bit MSB của lần tính hiện tại bằng 0 thì nó sẽ không đổi
 |
| Hình 8. Vị trí có MSB = 1 được XOR với đa thức sinh |
Để thực hiện mạch CRC-1, ngoài cách XOR tất cả các bit dữ liệu đầu vào như đã trình bày ở phần trên, chúng ta có thể thực hiện dựa trên nguyên lý của việc chia đa thức như hình trên. Mạch cần 2 FF để lưu giá trị sau mỗi lần XOR và mạch sẽ dịch 1 bit sau mỗi lần XOR để lấy 1 bit dữ liệu mới như hình sau:
 |
| Hình 9. Mạch nguyên lý của CRC-1 |
Ở hình trên, bit MSB sẽ điều khiển MUX chọn có XOR với đa thức sinh x+1 hay không? Tuy nhiên, sau mỗi chu kỳ tính, bit MSB luôn bị loại bỏ nên mạch MUX và XOR của bit MSB là không cần thiết. Mạch được rút gọn như hình sau:
 |
| Hình 10. Mạch nguyên lý CRC-1 (bỏ mạch tính ở bit MSB) |
Xét mạch MUX, nếu bit MSB bằng 1 thì bit 0 XOR với 1, nếu bit MSB bằng 0 thì tương ứng với việc bit 0 XOR với 0 nên mạch MUX được loại bỏ để thay bằng bit 1 XOR bit 0.
 |
| Hình 11. Mạch nguyên lý CRC-1 (bỏ mạch MUX) |
 |
| Hình 12. Mạch nguyên lý CRC-1 (bỏ FF đầu vào) |
Ở đây, bit CRC chỉ có 1 bit nên việc thêm 1 bit 0 ở chuỗi dữ liệu đầu vào để tính CRC cũng không cần thiết vì giá trị nào XOR với 0 cũng bằng chính nó.
 |
| Hình 12. Mạch nguyên lý CRC-1 |
Biểu diễn thường thấy cho mạch tính CRC như sau:
 |
| Hình 13. Mạch nguyên lý CRC-1 với biểu diễn thông thường |
Tương tự, xét lại mạch CRC-4 có đa thức sinh x^4 + x + 1, mạch nguyên lý tính CRC-4 như sau (lưu ý, vị trí XOR với "0" thì loại bỏ cả MUX và cổng XOR):
 |
| Hình 14. Mạch nguyên lý tính CRC-4 |
5. RTL code tính CRC nối tiếp
5.1 Nhận xét
Qua hai ví dụ trên đây, nhận xét chung như sau:
- Tại vị trí mà bit đa thức sinh bằng "0" thì chỉ là phép dịch bit
- Tại vị trí mà bit đa thức sinh bằng "1" thì được chèn cổng XOR
- Dữ liệu nối tiếp để tính CRC dịch từ MSB đến LSB với số lần dịch bằng độ dài dữ liệu cộng độ dài giá trị CRC. Ví dụ, dữ liệu 8 bit dùng CRC-4 thì số lần dịch là 12 lần với 4 bit cuối là 4 bit 0 được thêm vào chuỗi dữ liệu.
5.2 Phân tích module tạo và kiểm tra CRC
Căn cứ vào những nhận xét trên, một thiết kế thực hiện tính CRC tổng quát được thực hiện như sau:
- Sử dụng một define CRC_CTRL_POLY để cho phép tạo tín hiệu input điều khiển giá trị của đa thức sinh nếu muốn. Chú ý, độ rộng tín hiệu điều khiển bằng số bit CRC vằ bằng số mũ lớn nhất của đa thức sinh. Ví dụ, nếu đa thức sinh là x^4 + x + 1 thì độ rộng tín hiệu là 4 bit và giá trị gán cho tín hiệu điều khiển là 4'b0011 (bỏ bit 1 của x^4)
- Sử dụng một define CRC_CHECKER để cho phép tạo chức năng kiểm tra CRC
- Sử dụng một parameter CRC_GPW_MAX cho phép cấu hình độ rộng đa thức sinh. Độ rộng đa thức sinh bằng số mũ lớn nhất của đa thức sinh. Ví dụ, nếu đa thức sinh là x^4 + x + 1 thì CRC_GPW_MAX = 4
- Sử dụng một parameter CRC_POLY_VALUE cho phép gán giá trị đa thức sinh sẽ sử dụng nếu không sử dụng tín hiệu điều khiển được tạo ra bởi định nghĩa CRC_CTRL_POLY. Ví dụ, nếu không định nghĩa CRC_CTRL_POLY, đa thức sinh là x^4 + x + 1 thì CRC_GPW_MAX = 4 và giá trị CRC_POLY_VALUE = 4'b0011
Sơ đồ tín hiệu giao tiếp của module CRC như sau:
 |
| Hình 15. Sơ đồ tín hiệu của module tính CRC |
Hai tín hiệu ctrl_en và chk_en sẽ điều khiển chức năng tạo và kiểm tra CRC như sau, khi tín hiệu ctrl_en tích cực, dữ liệu dùng để tạo CRC hoặc được kiểm tra CRC sẽ bắt đầu dịch vào data_in. ctrl_en sẽ tích cực bằng số bit cần dịch trên data_in.
- Nếu chk_en = 0 thì khi ctrl_en = 0, crc_seq sẽ giữ giá trị chuỗi CRC trong 1 chu kỳ xung clock
- Nếu chk_en = 1 thì khi ctrl_en = 0, crc_error sẽ báo lỗi CRC
- crc_error = 1 thì chuỗi kiểm tra bị lỗi CRC
- crc_error = 0 thì chuỗi kiểm tra không bị lỗi
Mạch tổng quát của từng bit trong thanh ghi chứa giá trị CRC như sau:
 |
| Hình 16. Mạch tổng quát tính giá trị bit CRC thứ i |
Riêng bit 0 có đầu vào là data_in có mạch như sau:
 |
| Hình 17. Mạch tổng quát tính giá trị bit CRC 0 |
Khi có định nghĩa CRC_CHECKER, mạch kiểm tra lỗi CRC sẽ được tạo ra như sau:
 |
| Hình 18. Mạch kiểm tra lỗi CRC |
5.3 RTL code
Link download RTL code và testbench: CRC RTL codepass (nếu có): nguyenquanicd
5.4 Kết quả mô phỏng
 |
| Hình 19. Mô phỏng tạo và kiểm tra CRC |
Đa thức sinh: x^4 + x + 1 tương ứng với việc gán ctrl_poly_en = 4'b0011
Dữ liệu dùng để tạo CRC: 1010_0110 sau khi thêm 4 bit "0" là 1010_0110_0000 => Kết quả tính CRC là 1110
Dữ liệu dùng để kiểm tra CRC: 1010_0110_1110. Trong đó, 4 bit LSB 1110 là chuỗi CRC => Kết quả kiểm tra CRC là crc_error = 0
Lưu ý, đa thức sinh có nhiều cách biểu diễn khác nhau. Trong bài viết này chỉ dùng cách biểu diễn thông thường (normal representation) từ MSB đến LSB.
Lịch sử cập nhật:
1) 2019.08.26 - Thêm lưu ý về cách biểu diễn đa thức sinh
Thanks :D
Trả lờiXóaCảm ơn tác giả
Trả lờiXóa