Mã phát hiện lỗi

Xác định mã CRC dùng thuật toán Mod-2

Gọi T = (k+n) bit là khung thông tin được phát , với n < k

M = k bit dữ liệu, k bit đầu tiên của T

F = n bit của khung FCS, n bit cuối của T

P = (n+1) bit, số chia trong phép toán

Số T được tạo ra bằng cách dời số M sang trái n bit rồi cộng với số F :

T = 2ⁿM + F

Chia số2nM cho P ta được :

2ⁿ

Q là số thương và R là số dư

Vì phép chia thực hiện với số nhị phân nên số dư luôn luôn ít hơn số chia 1 bit.

Ta dùng số dư này làm số F, nghĩa là :

T = 2ⁿM + R.

Ở máy thu khi nhận được khối dữ liệu, mang chia cho P, kết quả số dư sẽ = 0 :

Vì R + R = 0 nên T/P = Q

Như vậy dùng số dư R của phép chia 2ⁿM cho P làm ký tự kiểm tra trong khung FCS thì chắc chắn T sẽ chia đúng cho P nếu bản tin không có lỗi.

Thí dụ:

Cho M = 1010001101 (10 bit)

P = 110101 (6 bit)

Số phải tìm R (5 bit) cho khung FCS được xác định như sau :

- Nhân M với 2⁵ cho : 101000110100000

- Thực hiện phép chia cho P

1101010110

110101 

110101

0111011

110101

00111010

110101

00111110

110101

00101100

110101

0110010

110101

0001110  R

Ta có R = 01110, cộng với 2⁵M, sẽ cho số T phát đi là :

T = 101000110100000 + 01110 = 101000110101110

Nếu bản tin không có lỗi T phải chia đúng cho P.

Thực hiện phép chia T/P ta thấy số dư = 0

Tóm lại, để có một khung FCS n bit , người ta phải dùng một số P có n+1 bit để tạo số R có n bit dùng cho khung FCS. P được gọi là đa thức sinh (generator polynomial), dạng của nó do các giao thức qui định, tổng quát P phải có bit đầu và bit cuối là bit 1.

Dùng phép biểu diễn đa thức

Để thấy quá trình hình thành mã CRC, ta có thể dùng phép biểu diễn một số nhị phân dưới dạng một đa thức của biến x với hệ số là các số nhị phân và bậc của x là giá trị chỉ vị trí của số nhị phân đó.

Ví dụ số nhị phân 110101 có thể biểu diển bởi

1.x⁵ + 1.x⁴ + 0.x³ + 1. x² + 0.x¹ + 1.x⁰ = x⁵ + x⁴ + x² + 1

Chú ý mã số n bit cho bậc cao nhất của đa thức là n-1

Quá trình hình thành mã CRC thực hiện như sau :

- Gọi M là đa thức biểu diễn thông tin cần truyền

P là đa thức sinh, bậc n (chứa n+1 bit)

Thực hiện phép chia

xⁿ

Khung thông tin truyền đặc trưng bởi

T(x) = xⁿ M(x) + R(x)

Lưu ý là nhân M(x) với xⁿ tương đương với việc dời M(x) sang trái n bit

- Ở máy thu thực hiện phép chia T(x) cho P(x) số dư phải bằng không

Lấy lại thí dụ trên, bản tin 1010001101 tương ứng với đa thức

M(x) = x⁹ + x⁷ + x³ + x² +1

Số chia P = 110101 (6 bít) tương ứng với đa thức

P(x) = x⁵ + x⁴ + x² +1

x⁵M(x) = x¹⁴ + x¹² + x⁸ + x⁷ + x⁵

Thực hiện phép chia :

x 9 + x 8 + x 6 + x 4 + x 2 +x

x⁵ + x⁴ + x² +1  x¹⁴ + x¹² + x⁸ + x⁷ + x⁵

x¹⁴ + x¹³ + x¹¹ + x⁹

x¹³ + x¹² + x¹¹ + x⁹ + x⁸ + x⁷ + x⁵

x¹³ + x¹² + x¹⁰ + x⁸

x¹¹ + x¹⁰ + x⁹ + x⁷ + x⁵

x¹¹ + x¹⁰ + x⁸ + x⁶

x⁹ + x⁸ + x⁷ + x⁶ + x⁵

x⁹ + x⁸ + x⁶ +x⁴

x⁷ + x⁵ + x⁴

x⁷ + x⁶ + x⁴ + x²

x⁶ + x⁵ + x²

x⁶ + x⁵ + x³ + x

x³ + x² + x = R(x)

R(x) = x³ + x² + x tương ứng với 01110

Khả năng dò sai của mã CRC

Một lỗi xảy ra ở một vị trí nào đó trong khung dữ liệu làm đảo bit ở vị trí đó của khung, điều này tương đương với phép tính EX-OR bit đó và bit 1 (vì 0+1=1 và 1+1=0).

Nếu gọi E là một khung có số lượng bit bằng với khung dữ liệu, trong đó chỉ các vị trí của bit lỗi = 1 và các bit khác = 0 thì khung thông tin Tr nhận được có thể viết.

Tr = T + E.

Thí dụ:

T = 11010111010

Dạng đa thức: T(x) = x¹⁰ + x⁹ + x⁷ + x⁵ + x⁴ + x³ + x

Giả sử bản tin sai ở các bit x⁷ , x⁵ và x⁴

Khung E có dạng: E = 00010110000

E(x) = x⁷ + x⁵ + x⁴

Khung dữ liệu nhận được: Tr = 11000001010

Tr(x) =x¹⁰ + x⁹ + x³ + x

Lưu ý phép cộng Modulo 2, tương ứng với phép toán EX-OR, nên x⁷+x⁷=(1+1)x⁷ = 0

Ta có

Máy thu không nhận ra lỗi khi nào Tr(x) chia đúng cho P(x), hay chỉ khi E(x) chia đúng cho P(x).

Vậy với điều kiện nào thì E(x) chia hết cho P(x) ?

Ta sẽ xét một số trường hợp cụ thể:

@- Giả sử bản tin chỉ sai một bit, đa thức E(x) có dạng xⁱ, i là một số nguyên, E(x) chia đúng cho P(x) chỉ khi P(x) cũng có dạng xⁿ. Người ta đã chọn P(x) có ít nhất là 2 số hạng nên E(x) không thể chia đúng cho P(x). Vậy

Mã CRC luôn luôn cho phép máy thu dò ra một bit sai.

@- Giả sử bản tin sai một chuỗi, nhưng có tổng số bit sai là số lẻ: đa thức E(x) chứa số lẻ bit 1 nên E(1) =1. Mặt khác, giả sử (x+1) là thừa số của P(x), ta có thể viết P(x) = (x+1)*H(x), H(x) là một đa thức. Ta cũng giả sử lỗi này không được dò ra, nghĩa là E(x) chia đúng cho P(x), hay E(x) = P(x)*K(x). Thay P(x) = (x+1)*H(x) vào E(x) được E(x) = (x+1)*H(x)*K(x), biểu thức này cho E(1) = 0. Điều này trái với giả thiết ở trên, hay nói cách khác, máy thu sẽ dò ra lỗi nếu ta chọn P(x) sao cho chia đúng cho (x+1). Vậy

Máy thu sẽ luôn luôn dò ra lỗi gồm nhiều bit và có tổng số bit lỗi là số lẻ nếu ta chọn P(x) chia đúng cho (x+1).

@-Giả sử nhiễu làm sai một đoạn dữ liệu có chiều dài m≤ bậc n của P(x)

Giả sử chuỗi bit sai có vị trí từ thứ i đến thứ i+m-1, E(x) có dạng:

E(x) = x^i+m-1 + . . . . +xⁱ = xⁱ*(x^m-1+ . . . +1)

P(x) không là thừa số của xⁱ nên E(x) chỉ chia đúng cho P(x) khi x^m-1+ . . . +1 chia đúng cho P(x). Vì m ≤ n hay m-1<n nên phép chia trên không thể là phép chia đúng. Vậy

Máy thu luôn luôn dò ra lỗi nếu chuỗi dữ liệu sai có chiều dài ≤ bậc của P(x)

@-Đoạn dữ liệu sai có chiều dài m >n

Từ kết quả trên

Nhưng bây giờ m-1 ≥ n nên x^m-1+ . . . +1 có thể chia đúng cho P(x). Vậy vấn đề là có bao nhiêu cơ hội để điều này xảy ra.

- Trường hợp m-1 = n hay (m=n+1). Vì bậc của P(x) là n nên để có phép chia đúng P(x) phải có dạng xⁿ+ . . . . . +1 với các số hạng giữa xⁿ và 1 phải hoàn toàn giống với các số hạng của x^m-1+ . . . . . +1 thì máy thu không dò được lỗi. Có n-1 số hạng giữa xⁿ và 1 nên có 2^n-1 tổ hợp và nếu các tổ hợp này có xác suất xảy ra như nhau thì xác suất máy thu không nhận được lỗi sẽ là 1/2^n-1.

- Trường hợp m>n+1, ta chấp nhận kết quả xác suất này là 1/2ⁿ.

Lấy thí dụ mã CRC-32 (n=32), xác suất không dò ra một lỗi có chiều dài >33 bit là 1/2.10³² (tương đương với khả năng dò ra lỗi là 99,99999998%).

Tóm lại với n càng lớn việc máy thu không dò ra lỗi càng rất khó xảy ra.

Mạch tạo mã CRC.

Thuật toán mod 2 được thực hiện bởi cổng EX-OR.

Dời bit được thực hiện bởi thanh ghi dịch.

Quan sát phép tính chia mod.2 của số 2ⁿM cho P(x) để có R(x) ta thấy đây là sự kết hợp của sự dời bit của số 2ⁿM với phép cộng Mod.2 của số P(x). Trong thí dụ trên, để tạo mã CRC với P(x) = 110101, người ta dùng mạch (H 3.2): Cho chuỗi dữ liệu là số 2ⁿM (gồm 15 bit, 101000110100000) vào mạch, sau 15 lần dời bit, kết quả trên các thanh ghi dịch chính là R(x). Mạch tạo mã trong trường hợp này gồm 5 thanh ghi dịch, ký hiệu A(x⁵), B(x⁴), C(x³), D(x²), E(x) .

Mạch tạo mã CRC được thực hiện như sau:

- Thanh ghi dịch chứa n bit, bằng với chiều dài của khung FCS.

- Có nhiều nhất n cổng EX-OR.

- Sự có mặt hay không của cổng EX-OR tương ứng với sự có mặt của số hạng lũy thừa bậc n trong đa thức P(x) (Riêng bậc cao nhất (n) của đa thức không kể )

(H 3.2 )

	A	B	C	D	E	Dữ liệu vào
Bắt đầuBước 1Bước 2Bước 3Bước 4Bước 5Bước 6Bước 7Bước 8Bước 9Bước 10Bước 11Bước 12Bước 13Bước 14Bước 15	000001*1010101100	000010*1111110101	0001011111101011	001010*0101111011	0101001011110110	1010 00* Bản tin để gửi1101000 5 bit 0 thêm vào00

²

số dư

- Trong thí dụ trên P =110101 = x⁵ + x⁴ + x² + 1, nên mạch chứa ba cổng EX-OR ở các vị trí tương ứng với 1, x² và x⁴ (x⁵ ứng với thanh ghi dịch cuối cùng FFA). Đường hồi tiếp từ x⁵ về x⁴ ­, x² và 1 (x⁰) để thực hiện phép cộng Mod-2 với số P(x) như nói trên.

- Trong 5 bước đầu tiên, các bit có trọng số lớn của M(x). 2ⁿ xuất hiện ở ngã ra các FFD một cách bình thường.

- Từ bước thứ 6 các kết quả phải kể đến tác dụng của cổng EX-OR, thí dụ ở bước thứ 6 ở ngõ ra E chính là cộng Mod-2 của tín hiệu vào (bit 0) và tín hiệu ngã ra A trước đó (bit 1), tức thực hiện EX-OR hai bit 0 và 1 ta được bit 1. Ngã ra D (bit 0) EX-OR với ngã ra A (bit 1) để được bit 1 ở ngã ra C. Ngã ra B(bit 0) EX-OR với ngã ra A (bit 1) để được bit 1 ở ngã ra A. Trên hình vẽ các bit EX-OR với bit ở ngã ra A được đánh dấu.

Tương tự như thế, sau 15 lần dịch (bước 15), dữ liệu ở ngã ra các FF chính là mã CRC (số dư R = 01110). Ngã ra A là MSB.

Có 4 đa thức P(x) được dùng để tạo mã CRC thông dụng:

CRC_12 = x¹² +x¹¹ + x³ + x² + x + 1

CRC_16 = x¹⁶+x¹⁵ + x² + 1

CRC_CCITT = x¹⁶+x¹² + x⁵ + 1

CRC_32 = x³²+ x²⁶+ x²³+ x²² + x¹⁶+ x¹² + x¹¹+ x¹⁰+ x⁸+ x⁷ + x⁵ + x⁴ + x²+ x +1

CRC_12 dùng truyền với ký tự 6 bit và khung FCS dài 12 bit.

CRC_16 & CRC_CCITT dùng truyền ký tự 8 bit và khung FCS dài 16 bit. (ở Mỹ và Âu châu).

CRC_32 Dùng trong mạng cục bộ (LAN) và một số ứng dụng của DOD (Department Of Defense).