Cơ Chế Hoạt Động Của Mã CRC - Timelibaray

KIỂM TRA BẰNG MÃ CRC (Cydic redundancy checks)

MÃ CRC được thiết lập trên cơ sở coi chuỗi bit là cách biểu diễn đa thức chỉ với câc hệ số 0 và 1, còn khung k bit được coi như danh sách các hệ số của đa thức với k giá trị , bắt đầu từ xk-1 đến x0, gọi là đa thức bậc k-1 .

Ví dụ chuỗi 110001 có 6 bit và nó biễu diễn cho đa thức x5+x4+x0. Các phép tính đại số đa thức được thực hiện theo modul 2 (XOR). Khi sử dụng phương pháp này thì cả bên phát và bên thu phải có cùng một đa thức sinh G(x). Cả hai bit bậc thấp (LSB) và bậc cao (MSB) của G(x) phải là 1. Ðể có thể tính được CRC cho một khung với m bit tương ứng với đa thức M(x), khung phải dài hơn đa thức sinh. Nguyên lý thực hiện là gắn các byte CRC vào đằng sau khung sao cho đa thức biểu diễn cho khung có đã có các byte CRC phải chia hết cho G(x). Khi máy thu nhận được khung, nó bị thử cho G(x), nếu còn dư thì có nghĩa là quá trình truyền có lỗi.

Thuật toán để tính CRC như sau:

– bước 1: Gọi bậc của G(x) là r. Thêm r bit 0 vào cuối khung (bậc thấp), sao cho nó có m+n bit tương ứng với đa thức xr .M(x).

– bước 2: Chia chuỗi bit tương ứng với G(x) thành chuỗi bits tương ứng với xr .M(x), sử dụng phép chia modul 2.

– bước 3: Lấy chuỗi tương ứng với đa thức xr .M(x) trừ đi cho phần dư (phần này luôn luôn có r bit hoặc ít hơn), kết quả thu được là khung đã có CRC để truyền, gọi là đa thức T(x) Mã đa thức với độ dài r bit kiểm tra sẽ cho phép phát hiện được mọi lỗi chùm có độ dài nhỏ hơn hoặc bằng r.

Trên thực tế, các đa thức sinh đã được quốc tế tiêu chuẩn hoá:

CRC-12: G(x)=x12+x11+x3+x2+x1+1

CRC-16: G(x)=x16+x15+x2+1

CRC-CCITT: G(x)=x16+x12+x5+1

Trong đó CRC-12 được sử dụng khi kí tự được mã hoá 6 bit, còn hai đa thức còn lại được dùng khi kí tự mã hoá 8 bit. Các CRC 16 bit như CRC-16 và CRC-CCITT sẽ tìm thấy tất cả các lỗi đơn và lỗi đôi, các lỗi có số bit là lẻ, tất cả các lỗi chùm có độ dài không quá 16 bit, 99,997% lỗi chùm 17 bit và 99,998% lỗi chùm từ 18 bit trở lên.

Bài viết gốc

Chia sẻ:

• Twitter
• Facebook

Thích Đang tải...

Có liên quan