b) Mã kiểm tra độ dư vòng CRC (Cyclic Redundancy Check)
Mã CRC là một loại mã vòng được sử dụng rộng rãi trên các kênh truyền nối tiếp bit để phát hiện lỗi (không sửa lỗi). Trong CRC, một tập bit kiểm tra được tính toán cho mỗi khung tin dựa vào nội dung khung, sau đó được gắn thêm vào đuôi khung để truyền đi. Bên thu thực hiện tính toán tương tự như bên phát để phát hiện lỗi. Các bit kiểm tra gọi là dãy kiểm tra khung FCS (Frame Check Sequence).
Bạn đang xem: Cyclic redundancy check là gì
Xem thêm: đơn Vị Tính Ea Là Gì, Ea Là Gì ý Nghĩa Của Từ Ea
Xem thêm: Công Suất Tiếng Anh Là Gì, Công Suất điện Tiếng Anh Là Gì
Thuật toán cụ thể như sau:
Tính toán tạo mã CRC bên phát và kiểm tra lỗi bên thu
Gọi M(x) là đa thức tin bậc k-1, G(x) là đa thức sinh bậc r
Thực hiện phép chia M(x)xr cho G(x), sẽ được:
Với Q(x) là thương số và R(x) là số dư
Từ đây suy ra:
Đặt T(x) = M(x)xr + R(x) là đa thức biểu diễn cho từ mã CRC phát. Rõ ràng là nếu không có lỗi xuất hiện thì bên thu, sau khi chia từ mã thu cho đa thức sinh ta sẽ được phần dư là 0
Ví dụ 3.4:
Ví dụ cần truyền đi một khung tin 8 bit 11100110 qua đường truyền số liệu, sử dụng mã CRC để phát hiện lỗi, đa thức sinh sử dụng là 11001
Từ mã CRC được tạo ra như hình 3.5 sau:
![*](https://licadho.org/wp-content/uploads/2021/07/imager_1_20923_700.jpg)
Hình 3.5 Ví dụ tạo mã CRC |
Sau khi thực hiện tính toán như trên, ta tìm được từ mã CRC là: 11100110 0110, trong đó 8 bit đầu là 8 bit tin và 4 bit sau là 4 bit kiểm tra.
Giả sử tại bên thu, ta thu được từ mã: 111001101111. Hình 3.6 trình bày việc thực hiện phép chia đa thức thu cho đa thức sinh như trên
Việc lựa chọn đa thức sinh rất quan trọng vì nó xác định các kiểu lỗi có thể phát hiện. Một đa thức sinh bậc r có ít nhất 3 số 1 sẽ phát hiện được tất cả các lỗi đơn, tất cả các lỗi đôi, tất cả các lỗi xảy ra với số lẻ, tất cả các lỗi chùm ngắn hơn r và hầu hết các lỗi chùm dài hơn hoặc bằng r. Sau đây là một vài đa thức sinh thường dùng trong thực tế:
CRC – 16: G(x) = x16 + x15 + x2 + 1
CRC – CCITT: G(x) = x16 + x12 + x5 + 1
CRC – 32: G(x) = x32 + x26 + x23 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
CRC – 16 và CRC – CCITT được dùng rộng rãi trong WAN, CRC – 32 được dùng trong hầu hết các LAN. Khả năng tự sửa lỗi của CRC thấp nhưng khả năng phát hiện lỗi rất cao nên thường được dùng kết hợp với ARQ để sửa lỗi
Chuyên mục: Hỏi Đáp