0.6 Viễn thông số  (Page 24/30)

Bây giờ ta gán giá trị zero cho tất cả các phần tử của một trong hai tập hợp và giá trị 1 cho tất cả các thành phần khác (đây là sự tuỳ chọn). Giả sử rằng ta chọn 0 cho tập hợp ở trên và 1 cho tập hợp ở dưới. Nếu một tập hợp chỉ chứa một mẫu tin, tiến trình xử lý cho tập hợp đó kết thúc. Vì thế từ mã hoá được dùng để gửi s5 đi là 0 và ta không cần xem lại tiến trình đó nữa. Ta tập trung vào tập hợp khác và ;ăpklại tiến trình chia nhỏ. Sau một lần chia nhỏ hơn ta có:

H

Chú ý rằng xác suất cả phần trên đường phân cách và phần dưới đường ấy đều là ¼. Ta đã cộng bit thứ hai cho các từ mã (cộng 0 cho từ mã ở trên đường phân cách và giá trị 1 cho ở dưới đường ấy). Bởi vì chỉ có một mẫu tin ở trên đường phân cách nên ta kết thúc và mã của s3 là 10. Tiếp tục chia nhỏ với tập hợp ở dưới đường phân cách ta có:

Cuối cùng ta chia nhỏ tập hợp ở phần dưới đường phân cách ra:

Kết quả của từ mã là:

S1 ->1110

S2 ->110

S3 ->10

S4 ->1111

S5 ->0

Quan sát kết quả trên ta thấy hoàn toàn giống với kết quả khi dùng với mã Huffman.

Ta đã minh hoạ hai kỹ thuật để rút ngắn tập hợp các bản tin thành mã nhị phân hiệu quả nhất. Ta giả sử rằng các bản tin đã được cho và chúng không tổ hợp thành mã được. Nếu các bản tin tổ hợp được, sẽ hiệu quả hơn nhiều. Ta minh hoạ điều này bằng một ví dụ với hai bản tin. Giả sử rằng bản tin này có xác suất lần lược là:

S1 ->0.9

S2 ->0.1

Thì Entropy được tính là:

H= -0.9 log 0.9-0.1 log 0.1 = 0.47 bit

Vì thế ta hy vọng sẽ đạt được một mã có chiều dài gần với giá trị này. Tuy nhiên ta sử dụng hoặc là kỹ thuật Huffman hoặc là mã Shannon-Fano sẽ cho kết quảlà gán giá trị 0 vào một trong các từ mã và giá trị 1 cho từ mã khác. Chiều dài trung bình thường là một bit trên một bản tin. Điều này, nhiều hơn hai lần Entropy.

Giả sử rằng ta tổ hợp các bản tin thành những cặp. Sau đó ta có 4 tập hợp của hai bản tin. Điều này không phụ thuộc vào các bản tin. Các tập hợp có thể và xác suất kết quả là:

S1S10.81

S1S20.09

S2S10.09

S2S20.01

Nếu sử dụng phương pháp Shannon-Fano ta gán những từ mã như sau:

S1S­10.810

S1S20.0910

S2S10.09110

S2S2 0.01111

Chiều dài từ trung bình thường được xác định như sau:

Vì mỗi bản tin được tổ hợp sẽ thể hiện hai trong số những bản tin gốc, ta chia số này cho hai, tìm ra được 0.645 bit được dùng để gửi một trong số những bản tin gốc.

Bây giờ giả sử rằng ta kết hợp 3 bản tin ở cùng một thời điểm để có được những xác suất bản tin và từ mã như sau:

S1S1S10.7290

S1S1S20.081100

S1S2S10.081101

S1S2S20.00911100

S2S1S10.081110

S2S1S20.00911101

S2S2S10.00911110

S2S2S20.00111111

Chiều dài trung bình của các mã là 1.598 bits. Vì thế chiều dài trung bình cho bản tin gốc là:

Chú ý rằng ta càng kết hợp nhiều bản tin, chiều dài trung bình sẽ tiến gần đến Entropy. Chiều dài trung bình này sẽ bằng với Entropy nếu các xác suất là nghịch đảo bội của 2. Khi càng nhiều các bản tin được kết hợp, các xác suất càng tiến đến gần nhau.