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

Giả sử rằng ta muốn mã hoá 5 từ s1, s2, s3, s4, và s5 với xác suất lần lược là 1/16, 1/8, ¼, 1/16, và ½. Trình tự mã Huffman được thiết lập qua 4 bước sau đây:

Bước 1: Sắp xếp các bản tin theo xác suất giảm dần. Nếu có những xác suất bằng nhau, chọn bất cứ từ nào trước cũng được.

Bước 2: Kể từ đáy lên, tổ hợp hai xác suất cuối thành một xác suất mới với xác suất là tổng của hai xác suất cần ghép. Ta sẽ sắp xếp lại khi có được xác suất mới nếu thấy cần thiết. Và ta cũng sắp xếp theo sự giảm dần.

Chú ý rằng xác suất ở cuối của cột bên phải là sự tổ hợp của s1 và s4.

Bước 3: Tiếp tục kết nối như bước 2 cho đến khi cột bên phải cùng chỉ còn hai xác suất.

Bước 4:Gán những từ mã bằng cách bắt đầu ở bên phải với MSB (the most significant bit). Di chuyển sang bên trái và gán cho những bit khác nếu có sự phân chia xảy ra. Những bit được gán , được gạch dưới như bảng sau:

Cuối cùng các từ mã được xác định như sau:

S1 ->1110

S2 ->110

S3 ->10

S4 ->1111

S5 ->0

Chú ý rằng tại mỗi điểm có thể có hai cách gán. Nếu có ba hoặc nhiều xác suất thấp nhất bằng nhau, việc chọn lựa tổ hợp là tuỳ ý.

Chiều dài trung bình là:

Nếu mã hoá khối được sử dụng, ta cần 3 bit cho một bản tin và chiều dài trung bình sẽ là 3. Entropy của mã được xác định:

H= 2/16 log(16) + 1/8 log(8) + ¼ log(4) + ½ log(2) = 15/8 bits

Kết quả này cũng giống như chiều dài trung bình của mã Huffman. Vì thế, thủ tục Huffman sinh ra một mã có hiệu quả cao. Điều này tạo ra kết quả bởi vì tất cả các xác suất bản tin là bội của ½.

Điều bất lợi của mã Huffman là ta không thể bắt đầu gán từ mã cho đến khi toàn bộ tiến trình tổ hợp được hoàn tất. Đó là một trong những cột phải được khai triển trước khi từ mã đầu tiên được gán. Tiến trình mã hoá thường được thực hiện bằng một máy vi tính chuyên dụng.

Mã Shannon-Fanno cũng giống như mã Huffman. Sự khác nhau chủ yếu là các thao tác thường tiến hơn là lùi. Vì thế các yêu cầu lưu trữ, được xem như là thư giản và mã thực hiện dễ hơn. Nó thường dẫn đến chiều dài trung bình giống như mã Huffman. Các kết quả mã hoá Shannon-Fano thì không luôn luôn tốt như mã Huffman.

Ta sẽ minh hoạ lại kỹ thuật này bằng một ví dụ. Ta dùng một ví dụ giống như mã Huffman đã trình bày ở phần trước trong chương này.

Bước 1: Sắp xếp những bản tin theo xác suất giảm dần. Nếu có nhiều xác suất bằng nhau, chọn bất cứ từ nào trước cũng được.

Bước 2: Chia những bản tin thành những tập con có xác suất ngang nhau nhất. Ta bắt đầu tại đỉnh hoặc đáy và chia nhóm này ra hai tập hợp. Ta tìm xác suất tổng cộng của tập hợp trên và tập hợp dưới. Ta chọn đường chia sao cho kết quả nằm trong xác suất gần nhau nhất. Trong trường hợp này đường phân cách sẽ nằm dưới mẫu tin dầu tiên. Kết quả xác suất cho các mẫu tin ở trên và ở dưới là ½ như được minh hoạ dưới đây.