tailieunhanh - Hướng dẫn mã hóa hình ảnh phần 4

Có một phương pháp thiết kế từ mã tối ưu khá đơn giản khi sử dụng, và cũng có tính giải mã duy nhất, là phương pháp mã hoá Huffman. Hình cho một ví dụ về mã hoá Huffman. | ch ơng 4 mA hoi óuh Bâng Ví dụ về một bộ từ mã có chiều dài không đổi cho trường hợp bản thông báo có 8 khả năng . Thông báo Từ mã a1 0 0 0 a2 0 0 1 a3 0 1 0 a4 0 1 1 a5 1 0 0 a6 1 0 1 a7 1 1 0 a8 1 1 1 Khi từ mã được thiết kế theo đặc trưng thống kê của các khả năng thì phương pháp thiết kế gọi là mã hoá thống kê. Để thảo luận vấn đề thiết k ế từ mã sao cho tỷ lệ bit bình quân thấp nhất phải dùng khái niệm entropy định nghĩa như sau L H -t P1log2P1 i 1 Pi là xác suất để bản tin là ai. Vì P 1 cho nên có thể chứng minh là i 1 i 0 H log2L Entropy H có thể coi là lượng tin tức bình quân chứa trong bản tin. Giả sử L 2. Nếu P1 1 và P2 0 thì entropy H bằng không và là giá trị cực tiểu ở trường hợp L 2. Trong trường hợp này xác suất để thông báo là a 1 là 100 nghĩa là bản tin không chứa tin tức gì mới. ở trạng thái cực đoan khác P1 P2 1 2 khi đó entropy H bằng 1 và là giá trị tối đa ở trường hợp L 2 khi đó hai khả năng a 1 và a2 của thông báo có xác suất xuất hiện như nhau và nếu nhận được thông báo thì rõ ràng là có một tin tức mới. Theo lý thuyết thông tin entropy H trong là tỷ lệ bit bình quân nhỏ nhất có thể đạt về mặt lý thuyết khi mã hoá một thông báo. Kết quả này tuy không chỉ ra được phương pháp thiết kế từ mã nhưng rất có ích. Giả sử ta thiết kế ra những từ mã có tỷ lệ bit bình quân vừa bằng entropy. Ta biết những từ mã này là tối ưu rồi và không cần nghiên cứu thêm. 194 ch ơng 4 mA hoi óuh Giả sử L có thể biểu thị thành luỹ thừa của 2 và các khả năn g a của thông báo bằng nhau tức là Pi 1 L với 1 i L . Theo thì entropy H trong trường hợp này là log 2L. Vì từ mã có chiều dài không đổi đưa đến tỷ lệ bit bình quân bằng log 2L cho nên trong trường hợp này từ mã có chiều dài đều là lời giải tối ưu. Entropy cũng là một tiêu chuẩn để xét chất lượng phương pháp thiết kế từ mã. Nếu thiết kế ra đạt tỷ lệ bit bình quân gần sát giá trị entropy thì phương pháp thiết kế đó là có hiệu quả. Nếu ta mã hoá từng thông báo riêng rẽ thì nói chung không thể .