Giáo trình Truyền dữ liệu - Các loại mã trong truyền dữ liệu

các bit Ci (i = 1,......,n) dùng kiểm tra chiều ngang. (H 3.1) cho ta dạng của khối dữ liệu có thực hiện kiểm tra chẵn theo chiều ngang và dọc. bit 1 2 . . . . . . . bit n Parity Character 1 B11 B21 . . . . . . . Bn1 R1 10110111 ↓VRC Character 2 B12 B22 . . . . . . . Bn2 R2 11010111 00111010 11110000 10001011 Character m B1m B2m . . . . . . . bnm Rm 01011111 Parity check char. C1 C2 . . . . . . . Cn Cn+1 01111110 ←LRC (H 3.1) Phương pháp kiểm tra khối cho phép phát hiện và sửa một lỗi vì xác định được vị trí của lỗi đó, chính là giao điểm của hàng và cột có bit sai. Máy thu có khả năng phát hiện hai lỗi sai trên cùng một hàng hoặc cột nhưng không xác định được vị trí bit lỗi. Ví dụ hai bit 1 và 3 của ký tự thứ nhất cùng sai thì bit kiểm tra VRC không phát hiện được nhưng bit LRC thì thấy ngay. Nếu bây giờ có thêm các bit 1 và 3 của ký tự thứ 5 cùng sai thì máy thu sẽ không phát hiện được, như vậy cũng còn trường hợp không phát hiện được lỗi nếu số lỗi là một số chẵn theo những vị trí xác định nào đó, tuy nhiên trường hợp này rất hiếm xảy ra. Tóm lại, dùng kiểm tra chẵn lẻ cho phép phát hiện lỗi trong một số trường hợp, tuy nhiên hiệu suất phát sẽ bị giảm và chỉ được dùng trong các hệ thống có vận tốc truyền thấp (bất đồng bộ). Trong các hệ thống truyền đồng bộ người ta hay sử dụng mã CRC , mã này cho phép dò lỗi rất hiệu quả và hiệu suất truyền cũng cao. 3.2.2 Kiểm tra dư thừa theo chu kỳ Để cải thiện hơn nửa việc kiểm tra lỗi người ta dùng phương pháp kiểm tra dư thừa theo chu kỳ (Cyclic Redundancy Check, CRC) Nguyên tắc tạo mã CRC : Xét khung dữ liệu gồm k bit và nếu ta dùng n bit cho khung kiểm tra FCS (Frame check sequence) thì khung thông tin kể cả dữ liệu kiểm tra gồm (k+n) bit sao cho (k+n) bit này chia đúng cho một số P có (n+1) bit chọn trước (dùng phép chia Modulo-2). Ở máy thu khi nhận được khung dữ liệu, lại mang chia cho số P này và nếu phép chia đúng thì khung dữ liệu không chứa lỗi * Nhắc lại một số tính chất của phép toán Mod-2 : - Phép cộng Mod-2 là phép cộng nhị phân không nhớ, dưới đây là thí dụ về phép cộng và phép nhân 1111 11001 + 1010 x 11 _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 7 0101 11001 11001 101011 - Phép cộng Mod-2 được thực hiện bởi cổng EX-OR - Phép trừ Mod-2 giống như phép cộng - Nhân Mod-2 một số với 2n tương ứng với dời số đó n bit về bên trái và thêm n bit 0 vào bên phải số đó, thí dụ 11001* 23 = 11001000 - Phép chia Mod-2 được thực hiện giống như phép chia thường nhưng nhớ là phép trừ trong khi chia được thực hiện như phép cộng. 3.2.2.1. 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 = 2nM + F Chia số 2nM cho P ta được : 2n P RQ P M += 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 = 2nM + R. Ở máy thu khi nhận được khối dữ liệu, mang chia cho P, kết quả số dư sẽ = 0 : P RRQ P R P RQ P T ++=++= Vì R + R = 0 nên T/P = Q Như vậy dùng số dư R của phép chia 2nM 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 25 cho : 101000110100000 - Thực hiện phép chia cho P 1101010110 110101 ⏐101000110100000 110101↓⏐⏐⏐⏐ 0111011⏐⏐⏐⏐ 110101↓↓⏐⏐ 00111010⏐⏐ 110101↓↓ 00111110⏐⏐ 110101↓↓ 00101100⏐ 110101↓ 0110010 110101↓ _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 8 0001110 ← R Ta có R = 01110, cộng với 25M, 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. 3.2.2.2. 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.x5 + 1.x4 + 0.x3 + 1. x2 + 0.x1 + 1.x0 = x5 + x4 + x2 + 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 xn P(x) R(x) Q(x) P(x) M(x) += Khung thông tin truyền đặc trưng bởi T(x) = xn M(x) + R(x) Lưu ý là nhân M(x) với xn 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 P(x) R(x) P(x) R(x) Q(x) P(x) T(x) ++= Q(x) P(x) R(x) 1)(1Q(x) =++= Lấy lại thí dụ trên, bản tin 1010001101 tương ứng với đa thức M(x) = x9 + x7 + x3 + x2 +1 Số chia P = 110101 (6 bít) tương ứng với đa thức P(x) = x5 + x4 + x2 +1 x5M(x) = x14 + x12 + x8 + x7 + x5 Thực hiện phép chia : x9 + x8 + x6 + x4 + x2 +x x5 + x4 + x2 +1 ⏐ x14 + x12 + x8 + x7 + x5 x14 + x13 + x11 + x9 x13 + x12 + x11 + x9 + x8 + x7 + x5 x13 + x12 + x10 + x8 x11 + x10 + x9 + x7 + x5 x11 + x10 + x8 + x6 x9 + x8 + x7 + x6 + x5 x9 + x8 + x6 +x4 x7 + x5 + x4 x7 + x6 + x4 + x2 x6 + x5 + x2 x6 + x5 + x3 + x x3 + x2 + x = R(x) _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 9 R(x) = x3 + x2 + x tương ứng với 01110 3.2.2.3. 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) = x10 + x9 + x7 + x5 + x4 + x3 + x Giả sử bản tin sai ở các bit x7 , x5 và x4 Khung E có dạng: E = 00010110000 E(x) = x7 + x5 + x4 Khung dữ liệu nhận được: Tr = 11000001010 Tr(x) =x10 + x9 + x3 + x Lưu ý phép cộng Modulo 2, tương ứng với phép toán EX-OR, nên x7+x7=(1+1)x7 = 0 Ta có P E P T P ET +=+ 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 xi, i là một số nguyên, E(x) chia đúng cho P(x) chỉ khi P(x) cũng có dạng xn. 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) = xi+m-1 + . . . . +xi = xi*(xm-1+ . . . +1) P(x) 1)....(xx P(x) E(x) 1mi ++∗= − P(x) không là thừa số của xi nên E(x) chỉ chia đúng cho P(x) khi xm-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 _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 10 Từ kết quả trên P(x) 1)....(xx P(x) E(x) 1mi ++∗= − Nhưng bây giờ m-1 ≥ n nên xm-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 xn+ . . . . . +1 với các số hạng giữa xn và 1 phải hoàn toàn giống với các số hạng của xm-1+ . . . . . +1 thì máy thu không dò được lỗi. Có n-1 số hạng giữa xn và 1 nên có 2n-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/2n-1. - Trường hợp m>n+1, ta chấp nhận kết quả xác suất này là 1/2n. 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.1032 (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. 3.2.2.4. 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ố 2nM 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ố 2nM 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ố 2nM (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(x5), B(x4), C(x3), D(x2), 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 _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 11 Bắt đầu Bước 1 Bước 2 Bước 3 Bước 4 Bước 5 Bước 6 Bước 7 Bước 8 Bước 9 Bước 10 Bước 11 Bước 12 Bước 13 Bước 14 Bước 15 0 0 0 0 0 1* 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0* 1Ë 1 1 1 1 1 0 1 0 1 0 0 0 1 0 Ë1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 1 0* 0Ë 1 0 1 1 1 1 0 1 1 0 1 0 1 0 Ë0 1 0 1 1 1 1 0 1 1 0 1⎫ 0⏐ 1⏐ 0⏐ 0⏐ 0*⎬ Bản tin để gửi 1⏐ 1⏐ 0⏐ 1⎭ 0⎫ 0⏐ 0⎬ 5 bit 0 thêm vào 0⏐ 0⎭ 14444444244444443 số dư - Trong thí dụ trên P =110101 = x5 + x4 + x2 + 1, nên mạch chứa ba cổng EX-OR ở các vị trí tương ứng với 1, x2 và x4 (x5 ứng với thanh ghi dịch cuối cùng FFA). Đường hồi tiếp từ x5 về x4 , x2 và 1 (x0) để 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). 2n 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 = x12 +x11 + x3 + x2 + x + 1 CRC_16 = x16+x15 + x2 + 1 CRC_CCITT = x16+x12 + x5 + 1 CRC_32 = x32+ x26+ x23+ x22 + x16+ x12 + x11+ x10+ x8+ x7 + x5 + x4 + x2+ 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). 3.2.3 Mã Hamming Mã Hamming là một bước phát triển của kiểm tra chẵn lẻ và có khả năng sửa sai do xác định được vị trí lỗi. Số lượng bit của mã Hamming tùy thuộc số lượng bit của chuỗi dữ liệu. Ta có thể lý luận như sau để xác định số lượng bit của mã Hamming. Gọi m là số bit của chuỗi dữ liệu và n là số bit của mã Hamming, tổng số bit phát đi là m+n - Với n = 1 ta xác định được 1 trong 2 kết quả : chuỗi dữ liệu sai hoặc đúng nhưng không biết vị trí lỗi. - Với n = 2, 1 trong 4 trường hợp xảy ra: 2 phép kiểm tra đều cho kết quả đúng, 2 phép kiểm tra đều cho kết quả sai, phép kiểm tra thứ nhất sai, phép kiểm tra thứ hai đúng và ngược lại. 4 trường hợp này cho phép kết luận được 1 bit sai ở 1 trong 3 vị trí. _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 12 - Với n=3, có 8 khả năng xảy ra và ta có thể kết luận được 1 bit sai ở 1 trong 7 vị trí. - Với số n bất kỳ, có 2n khả năng xảy ra và ta có thể kết luận được 1 bit sai ở 1 trong 2n -1 vị trí. Vậy để có thể phát hiện 1 lỗi tại 1 vị trí cụ thể thì số n nhỏ nhất được chọn phải thỏa: 2n - 1 ≥ Ù m + n hay 2n ≥ Ù m + n + 1 Các bit của mã Hamming chèn vào vị trí 2n và dùng cho kiểm tra chẵn lẻ. Các bit khác là bit thông tin (dữ liệu). Dưới đây là một ví dụ để thấy cách xác định mã Hamming: Giả sử chuỗi dữ liệu cần truyền gồm 4 bit như sau : 1 0 1 0 Với m = 4 , ta chọn n = 3, bất đẳng thức trên được thỏa Gọi các bit của mã Hamming là H1 H2 và H4 (1, 2, 4 là các vị trí mà ta sẽ đặt 3 bit của mã Hamming vào dòng dữ liệu). Gọi các bit dòng dữ liệu là X3, X5, X6, X7. Tổ hợp các bit dữ liệu và bit mã, ta đươc 1 2 3 4 5 6 7 H1 H2 X3 H4 X5 X6 X7 Giả sử ta chọn Parity chẵn, các bit mã sẽ được xác định như sau: H1⊕ X3⊕ X5⊕X7 = 0 H1 = X3⊕ X5⊕X7 =1 ⊕ ( 0 ⊕ 0 ) = 1 ⊕ 0 = 1 Tương tự: H2 = X3⊕ X6⊕X7 =1 ⊕ (1 ⊕ 0 ) = 1 ⊕ 1 = 0 H4 = X5⊕ X6⊕X7 =0 ⊕ (1 ⊕ 0 ) = 0 ⊕ 1 = 1 Bản tin bao gồm bit mã trở thành: 1 0 1 1 0 1 0 Ở máy thu để kiểm tra người ta thực hiện các phép toán: C1 = H1⊕ X3⊕ X5⊕X7 C2 = H2⊕ X3⊕ X6⊕X7 C4 = H4⊕ X5⊕ X6⊕X7 Nếu C1= C2 = C4 = 0, không có lỗi xảy ra Nếu C1 = 1, C2 = C4 = 0, một trong các bit ở vị trí 1, 3, 5, 7 bị lỗi. Nhưng C2 = C4 = 0 có nghĩa là các bit ở vị trí 2, 3, 6, 7 và 4, 5, 6, 7 đã đúng. Vậy bit sai phải ở vị trí 1 Lý luận tương tự ta có các trường hợp khác. Thí dụ nếu C1= C2 = C4 = 1 thì bit lỗi là bit ở vị trí 7 Thí dụ bản tin nhận được là 1 0 1 1 1 1 0 Mạch dò sai sẽ tính C1 , C2 , C4 như sau: C1 = H1⊕ X3⊕ X5⊕X7 = 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1 C2 = H2⊕ X3⊕ X6⊕X7 = 0 ⊕ 1 ⊕ 1 ⊕ 0 = 0 C4 = H4⊕ X5⊕ X6⊕ X7 = 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1 Vì chỉ bit X5 thuộc cả C1 và C4 nên bit sai là bit thứ 5 Quan sát tổ hợp C4 C2 C1 ta thấy C4 C2 C1 = 101 = (5)10 . Như vậy giá trị có được của tổ hợp này cho ta biết vị trí bit sai cần sửa chữa. Nếu tổ hợp này bằng 0 chứng tỏ bản tin nhận đúng. Mã Hamming có thể được phát triển để dò ra hai bit sai và sửa được một bit lỗi. 3.3 MÃ NÉN DỮ LIỆU Một vấn đề cũng luôn được quan tâm trong truyền dữ liệu là làm thế nào để giảm thiểu số bit cần thiết để truyền một bản tin. - Như ta đã biết, phương pháp điều chế vi phân, ngoài tác dụng tốt về mặt đồng bộ còn có tác dụng giảm số bit đi rất nhiều nếu thông tin có tính lặp lại. _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 13 - Một phương pháp khác là mã hóa Run Length. Phương pháp này cho phép người ta phát đi các mã thay cho các chuỗi ký tự có tính lặp lại kèm theo mã điều khiển báo cho bên thu số lần lặp lại, nhờ mã này mà bên thu có thể tạo lại toàn bộ chuỗi thông tin đã truyền. - Mã đồ họa trong hệ thống Videotex dùng một bảng mã hình học để phát đi các đồ họa của máy tính hoặc hình ảnh video. Mỗi hình được phát đi là tập hợp các hình cơ bản với vị trí, màu sắc và kích thước xác định. Các hình cơ bản là các vòng tròn, hình chữ nhật....Điều này làm giảm rất nhiều số bit cần thiết so với việc phải phát đi từng tọa độ và màu của từng điểm trên màn hình 3.3.1 Mã Huffman Mã Huffman lợi dụng xác suất xảy ra của các ký tự khác nhau mà gán các từ mã ngắn cho các ký tự có xác suất xảy ra lớn và ngược lại. Thí dụ, thay vì dùng 7 bit để mã tất cả các ký tự như mã ASCII, người ta chỉ gán 2 bit cho chữ E và 10 bit cho chữ Z, bởi lẻ, trong tiếng Anh xác suất xuất hiện chữ E rất lớn so với xác suất xuất hiện chữ Z. Mã này còn có tên Mã phụ thuộc tần số (frequency dependent code) Với phương pháp này số bit trung bình dùng cho mỗi ký tự sẽ giảm. Nhưng do các mã dài ngắn khác nhau, để máy thu phân biệt được, người ta phải chọn các từ mã ngắn sao cho không trùng với các bit đầu của các từ mã dài hơn. Gọi là tính tiền tô (prefix property). Giải thuật Huffman: Dưới đây là các bước tạo mã Huffman - Tương ứng với mỗi dữ kiện liên kết một cây nhị phân chứa duy nhất một nút. Ở mỗi cây ghi tần số xuất hiện mà ta gọi là trọng lượng của cây. - Tìm hai cây nhẹ nhất. Nếu có nhiều hơn hai, ta chọn ngẫu nhiên hai cây trong số các cây có trọng lượng nhẹ nhất, ghép chúng lại thành một cây đơn với nút gốc mới. Tổng trọng lượng hai cây này là trọng lượng của cây mới. - Lặp lại các bước cho tới lúc chỉ còn một cây duy nhất. Các cây ban đầu trở thành các lá của cây nhị phân cuối cùng này. Ta biết rằng đối với cây nhị phân thì chỉ có một đường duy nhất từ gốc cho tới lá. Với mỗi lá, đường từ gốc đến nó chính là mã Huffman tương ứng. Mã này xác định bằng cách ghi trị 0 cho nhánh bên trái và 1 cho nhánh bên phải (hoặc ngược lại). Thí dụ 1: Thiết lập mã Huffman cho các ký tự A, B, C, D, E với tần số xuất hiện lần lượt là 0,25; 0,15; 0,10; 0,20; 0,30. (H 3.3a) là cây với 5 nút đơn ban đầu và trọng lượng tương ứng. (H 3.3b) ghép 2 cây B và C thành một cây mới với trọng lượng là tổng trọng lượng cây B và C (0,25) Bước tiếp theo ta có thể ghép cây mới hình thành với cây D hay cây A với D. (H 3.3c) ghép cây mới với D để được một cây trọng lượng là 0,45. (H 3.3d) ghép cây E và A Cuối cùng, ghép hai cây mới tạo để được một cây duy nhất, Ghi trị 0 và 1 vào các nhánh (H 3.3e). _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 14 (H 3.3) Ta được bảng mã sau: Ký tự Mã A B C D E 01 100 101 11 00 Chiều dài trung bình của từ mã có thể tính như sau: 0,25*2 + 0,15*3 + 0,10*3 + 0,20*2 + 0,30*2 = 2,25 bít/ký tự Do có sự chọn ngẫu nhiên khi các dữ kiện có cùng trọng lượng nên kết quả có thể cho các bảng mã khác nhau. Tuy nhiên, kết quả cuối cùng của các bộ mã khác nhau phải cho cùng chiều dài trung bình của từ mã. Thí dụ 2: Mã hoá giá trị nhiệt độ trong khoảng từ 20° C đến 30° C với xác suất cho trong (H 3.4). Thay vì thực hiện các cây nhị phân như trên, ta có thể dựa vào xác suất của các giá trị nhiệt độ mà lập một đồ họa để thực hiện việc mã hóa sao cho các giá trị có xác suất lớn sẽ dùng từ mã ngắn nhất có thể có. Các sự kiện (là các giá trị nhiệt độ) được liệt kê theo xác suất giảm dần (H 3.4a) Ta bắt đầu bằng cách gán hai bít 0 và 1 cho 2 sự kiện có khả năng xảy ra ít nhất, sau đó hai sự kiện này được tổ hợp thành một sự kiện có xác suất bằng tổng hai xác suất của hai sự kiện đó, các sự kiện được sắp xếp theo thứ tự giảm dần và thủ tục lặp lại từ dưới lên và từ trái sang phải cho đến khi hai sự kiện cuối cùng được kết hợp. Từ mã của các sự kiện được viết bằng cách dò theo các đường của sơ đồ theo chiều ngược lại, từ phải qua trái. Cuối cùng ta có bảng mã (H 3.4b) Từ mã trung bình: 0,21*2 + 0,17*3 + 0,15*3 + 0,12*3 + 0,1*3 + 0,06*4 + 0,05*4 + 0,04*5 + 0,03*6 + 0,02*6 =3,18 bít/sự kiện Số bit dùng mã hóa đã giảm khoảng 20%. Một ưu thế của phương pháp Huffman là có thể lập trình để thực hiện việc mã hóa. Trở lại Thí dụ 1, bây giờ giả sử chuỗi ký tự được phát đi là A B E C A D B C, tương ứng với chuỗi bit 01100001010111100101, máy thu khi nhận được chuỗi dữ liệu sẽ thực hiện việc giải mã như thế nào ? Nhờ vào tính tiền tố của các mã, máy thu sẽ lần lượt đọc các bit cho tới khi gặp một chuỗi con các bit tương ứng với một mã sẽ dừng lại, giải mã ký tự này, sau đó tiếp tục đọc chuỗi dữ liệu kế tiếp để tìm ra ký tự thứ hai. . . _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 15 (a) (b) (H 3.4) 3.3.2 Mã Run length Mã Huffman tuy có làm giảm số bit truyền đi nhưng nó đòi hỏi dữ liệu phải được tập hợp thành từng nhóm hay ký tự để xác định tần số lặp lại của các nhóm hay ký tự này. Việc này đôi khi rất khó thực hiện đối với một số loại dữ liệu thí dụ như dữ liệu từ một bản fax, tín hiệu mã hình ảnh . . . Lấy thí dụ trường hợp bản fax, dữ liệu được phát đi không phải là các ký tự mà là các bit tương ứng với điểm sáng tối trên tờ giấy, như vậy phải có một kỹ thuật phù hợp để nén chuỗi dữ liệu này, đó chính là mã Run length. Mã Run length được tạo ra bằng cách quan sát chuỗi bit 0 (hoặc 1) liên tiếp và thay thế chiều dài chuỗi bit này bởi một số nhị phân. Ở máy thu khi nhận được các số nhị phân sẽ thay các số này bởi các bit 0 (hoặc 1) đồng thời chèn các bit khác loại vào. Thí dụ ta phải tạo mã Run length cho chuỗi dữ liệu sau bằng cách dùng số 4 bit thay cho số bit 0 liên tiếp: Dòng dữ liệu 0 . . . 0 1 0 . . . 0 1 1 0 . . . 0 1 0 . . . 0 1 1 0 . . . 0 91 bit Số bit 0 liên tiếp 14 9 20 30 11 Run length (nhị phân) 1110 1001 0000 1111 0101 1111 1111 0000 0000 1011 40 bit Run length (thập phân) 14 9 0 15 5 15 15 0 0 11 Nhận xét cách tạo mã : - 1 bit 1 giữa các chuỗi bit 0 sẽ không được mã, máy thu tự động chèn bit 1 này vào khi phục hồi dữ liệu. - Nếu có 2 bit 1 liên tiếp, ta xem như có 1 chuỗi gồm không bit 0 giữa 2 bit 1 này và phải được thay thế bởi số 0000. - Nếu số số 0 nhiều hơn 15 ta phải dùng 2 số nhị phân thay cho chuỗi này (20=15+5; 30=15+15). Ở máy thu khi gặp chuỗi bốn bit 1 nó phải hiểu là phải lấy tổng số này với các số phía sau, nếu số sau cùng cũng gồm 4 bit 1, máy thu phải được báo bằng chuỗi 4 bit 0 theo sau (trường hợp sau số 30) - Nếu chuỗi dữ liệu bắt đầu bằng bit 1 thì máy phát sẽ gửi đi 4 bit 0 đầu tiên. - Ở cuối bản tin máy phát sẽ gửi tín hiệu báo chấm dứt bản tin và nhờ đó máy thu biết cách xử lý cho trường hợp bản tin kết thúc bởi chuỗi bit 0 hay bit 1. Kỹ thuật nén này chỉ có hiệu quả khi chuỗi dữ liệu chứa rất nhiều một loại bit. _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 16 Ngoài ra, kỹ thuật nén Run length cũng được dùng mã hóa các chuỗi ký tự giống nhau bằng cách thay mỗi chuỗi ký tự liên tiếp bằng con số chỉ độ dài đứng trước ký tự đó. Thí dụ, với chuỗi HHHHHFFFFFFFFYYYYYYYYYYYYYGGGGGGGGGG Sẽ có mã là: 5H8F13Y10G 3.3.3 Mã vi phân (Differential encoding) Còn gọi là mã tương đối (Relative encoding) Trong nhiều trường hợp, các dữ liệu liên tiếp nhau thay đổi rất