Cyclic redundancy check là gì

Cấu trúc toán học của mã vòng cho phép khả năng sửa lỗi cao.Có thể thực hiện mã vòng dễ dàng bằng phần cứng, bằng các thanh ghi dịch và các cổng XORDịch vòng một từ mã cũng được một từ mã thuộc cùng bộ mã.Có thể biểu diễn mã vòng bằng đa thứcCó thể tạo ra từ mã vòng bằng cách nhân modulo-2 vector mang tin với đa thức sinh. Lúc này mã vòng được gọi là mã vòng không hệ thống

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ì

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.

Bạn đang xem: Cyclic redundancy check là gì

Xem thêm: Screen Mirroring Trên Iphone, Làm Thế Nào Để Cài Đặt Screen Mirroring

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:

Xem thêm: Chuỗi Sự Kiện Võ Lâm Chi Mộng

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: Games/Phần Mềm