CHƯƠng 1 TỔng quan về KỸ thuật truyền số liệU


* Nhắc lại một số tính chất của phép toán Mod-2



tải về 0.93 Mb.
trang5/9
Chuyển đổi dữ liệu07.07.2016
Kích0.93 Mb.
1   2   3   4   5   6   7   8   9

* 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

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 bít về bên trái và thêm n bít 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.



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

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

             3.2.2.4. Mạch tạo mã CRC.

 

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



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

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

F = n bít của khung FCS, n bít cuối của T

P = (n+1) bít, 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 bít rồi cộng với số F :

T = 2nM + F

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

                                              2n



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 bít.

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 :

                                                 

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 bít)



P = 110101 (6 bít)

Số phải tìm R (5 bít) 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



110101½¯½½½

  0111011½½½½

110101¯¯½½

00111010½½

110101¯¯

00111110½½

110101¯¯

00101100½

110101¯

0110010


110101¯

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 bít , người ta phải dùng một số P có n+1 bít để tạo số R có n bít 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ó bít đầu và bít cuối là bít 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 bít 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



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 bít


  • Ở 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) = 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)

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 bít ở vị trí đó của khung, điều này tương đương với phép tính EX-OR bít đó và bít 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 bít lỗi = 1 và các bít 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 bít 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ó:


                                                             

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 bít, đ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 bít sai.

@- Giả sử bản tin sai một chuỗi, nhưng có tổng số bít sai là số lẻ: đa thức E(x) chứa số lẻ bít 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 bít và có tổng số bít 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 bít 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) 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

Từ kết quả trên



                                                           

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 bít đượ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 bít 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 bít, 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 bít, 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ể )



                                

(H3.2)




A

B

C

D

E

Bít vào


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



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*



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





0*ý Bản tin ảo gửi







0ý 5 bit 0 thêm vào




41444444424444443

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 bít 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ế, sau15 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 da 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 bít của mã Hamming tùy thuộc số lượng bít của chuỗi dữ liệu. Ta có thể lý luận như sau để xác định số lượng bít của mã Hamming.

Gọi m là số bít của chuỗi dữ liệu và n là số bít của mã Hamming, tổng số bít 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 bít sai ở 1 trong 3 vị trí.

- Với n=3, có 8 khả năng xảy ra và ta có thể kết luận được 1 bít 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 bít 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 bít của mã Hamming chèn vào vị trí 2n và dùng cho kiểm tra chẵn lẻ. Các bít khác là bít 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 bít 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 bít của mã Hamming là H1 H2 và H4 (1, 2, 4 là các vị trí mà ta sẽ đặt 3 bít của mã Hamming vào dòng dữ liệu). Gọi các bít dòng dữ liệu là X3, X5, X6, X7.

Tổ hợp các bít dữ liệu và bít 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 bít 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

Bản tin bao gồm bít 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 bít 1, 3, 5, 7 bị lỗi. Nhưng C2 = C4 = 0 có nghĩa là các bít 2, 3, 6, 7 và 4, 5, 6, 7 đã đúng. Vậy bít sai phải là bít 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ì bít lỗi là bít 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ỉ bít X5 thuộc cả C1 và C4 nên bít sai là bít 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í bít 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 bít 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ố bít 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ố bít đi rất nhiều nếu thông tin có tính lặp lại.

- 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ố bít 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.                                                                                                                        



           3.3.2 Mã Run length.

           3.3.3 Mã vi phân.

 

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 bít để mã tất cả các ký tự như mã ASCII, người ta chỉ gán 2 bít cho chữ E và 10 bít 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ố bít 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 bít đầ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).

                                 

                                                                                 (H3.3)

Ta được bảng mã sau:




Ký tự



A

B

C



D

E


01

110


111

10

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ố bít 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 bít 01110001110110110111, 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 bít cho tới khi gặp một chuỗi con các bít 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. . .



                                    

(a)                           (H3.4)                              (b)                               



1   2   3   4   5   6   7   8   9


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2019
được sử dụng cho việc quản lý

    Quê hương