giới thiệu về mã hoá entropy và nén dữ liệu
Chủ đề chính của các phần trước thuộc chương này là mã hoá tín hiệu nguồn. Đó là kỹ thuật chuyển đổi một tín hiệu tượng tự sang tín hiệu số. Phần chính trong phần này là mã hoá entropy. Đây là phương pháp kết hợp một từ dạng số với ...
Chủ đề chính của các phần trước thuộc chương này là mã hoá tín hiệu nguồn. Đó là kỹ thuật chuyển đổi một tín hiệu tượng tự sang tín hiệu số.
Phần chính trong phần này là mã hoá entropy. Đây là phương pháp kết hợp một từ dạng số với mỗi thông tin được truyền đi. Ta sẽ thấy sự liên kết này được thực hiện trong phương cách làm giảm thiểu chiều dài thông tin được truyền.
Trong phần 7.8, ta sẽ nghiên cứu về mã hoá kiểm soát lỗi. Phương pháp này thì khác so với mã hoá entropy.
Ngay cả trong trường hợp không có nhiễu thêm vào, các mã hoá entropy cũng phải được thiết kế cẩn thận để tránh nhiều lỗi trong khi giải mã. Vấn đề số một liên quan đến khái niệm này là sự giải đoán duy nhất. Giả sử rằng có 4 bản tin cần được truyền và những bản tin này được mã hoá sang số nhị phân như sau:
M1 = 1 M2 = 10 M3= 01 M4 = 101
Giả sử bây giờ ta đang ở hệ thống thu và nhận được kết quả là 101. Ta sẽ không biết kết quả này là của M4 hoặc thông tin ghép của M2 và M1 hoặc M1 và M3. Do đó sự lựa chọn của các từ mã này cho ra một mã mà không có sự giải đoán mã duy nhất.
Một mã có thể giải đoán một cách duy nhất được nếu không có từ mã tạo nên bắt đầu (được xem như tiền tố) của bât kỳ từ mã nào khác. Vì thế, 4 mã thông tin sau đây là một ví dụ giải đoán duy nhất.
M1=1 M2=01 M3=001 M4=0001
Đặc tính giới hạn tiền tố là đầy đủ nhưng không cần thiết cho khả năng giải mã duy nhất. Ví dụ khá, mã:
M1=1 M2=10 M3=100 M4=1000
Là có thể giải đoán duy nhất được, mặc dù mỗi từ mã là tiền tố của mỗi từ mã khác ở bên phải của nó. Sự khác nhau chính yếu giữa ví dụ này và ví dụ trước là ở chỗ không từ mã nào có thể hình thành như là sự tổ hợp của những từ mã khác. Tuy nhiên đây là điều bất lợi. Mã thì có thể giải đoán duy nhất được nhưng không xảy ra lập tức. Giả sử rằng ta đang ở máy thu và nhận được mã 10. Đến khi ta thấy hai bit được nhận kế tiếp, ta không biết khi nào nhận được thông tin M2, M3, M4.
Ví dụ 7.8: Những mã nào sau đây là giải đoán duy nhất? Hãy xác định chúng khi nào xảy ra.
0, 01, 001, 0011, 101
110, 111, 101, 01
0, 01, 011, 0110111
Giải:
Đây không là giải đoán duy nhất vì từ đầu tiên và từ sau cùng khi gởi đi thành chuỗi 0101 và có thể diễn giải là 01 và 01. Đó là hai lần truyền của từ thứ hai.
Đây là giải đoán duy nhất vì tất cả những từ bắt đầu với một số 1 và đều có chiều dài là 3. Nếu một chuỗi 3 bit không bắt đầu với số 1, ta biết rằng nó chỉ là một từ có hai bit. Mã này, cũng xảy ra tức thì vì không từ mã nào là tiền tố của từ khác.
Đây là giải đoán duy nhất vì tất cả những từ bắt đầu với một số zero, số zero này không lập lại trong bất cứ từ nào là tổ hợp của những từ khác. Nó không xảy ra lập tức vì mỗi từ trong ba từ đầu tiên là một tiền tố của một từ sau cùng khác.
MÃ HOÁ ENTROPY (entropy coding)
Vấn đề ta quan tâm ở đây là tìm ra các mã có thể giải đoán duy nhất được với chiều dài nhỏ nhất. Điều này sẽ cho phép truyền với tốc độ lớn nhất trên kênh. Việc kiểm tra các mã được trình bày rõ ràng hơn trong phần này. Những bản tin khác nhau được mã hoá thành những từ có chiều dài khác nhau. Khi nói về chiều dài của một mã, ta phải chỉ ra chiều dài trung bình của những từ mã. Trị trung bình này được tính toán bằng cách lấy xác suất của mỗi bản tin. Rõ ràng rất thuận lợi khi gán những từ mã ngắn hơn cho hầu hết những bản tin có thể có. Mã Morse theo quy luật này bằng cách gán từ mã ngắn nhất bằng ký tự E.
Một định lý căn bản đã tồn tại trong thuyết mã hoá không có nhiễu. Định lý này được phát biểu rằng: đối với các chữ cái mã hoábằng số nhị phân, chiều dài từ mã trung bình, lớn hơn hoặc bằng với entropy. Người ta định nghĩa entropy là
Trong đó pi là xác suất của bản tin thứ i. Giá trị log2(1/pi) được hiểu như là nội dung của thông tin và đơn vị của nó là bit. Entropy là lượng tin trung bình trên bản tin.
Gọi chiều dài từ trung bình là n, định lý này được xác định bằng công thức sau:
Ví dụ 7.9: Tìm chiều dài trung bình nhỏ nhất của một mã với 4 bản tin với xác suất lần lược là 1/8, 1/8, ¼ và ½.
Giải: Theo mã hoá entropy ta có:
1/8 x 3 + 1/8 x 3 +1/4 x 2 + ½ x 1 = 1.75 bits
Đây cũng là chiều dài trung bình nhỏ nhất của mã này. Ta chú ý rằng mã có thể là:
M1 = 000, M2 = 001, M3=01, M4 =1
Mã này có thể giải đoán được và có chiều dài trung bình là 1.75 bits.
CÁC MÃ CÓ CHIỀU DÀI THAY ĐỔI (variable length codes)
Nếu các bản tin truyền đi với xác suất không bằng nhau tức các từ mã được chọn có chiều dài không bằng nhau, chiều dài mã trung bình ngắn hơn. Ví dụ giả sử rằng ta có 4 bản tin với xác suất lần lược là 1/8, 1/8, ¼, và ½ (giống như ví dụ 7.9). Một phương pháp để mã hoá những bản tin này sang các từ nhị phân là sử dụng 00, 01, 10 và 11 để gửi 4 bản tin có thể với chiều dài trung bình là 2 bit. Chiều dài trung bình được cho bởi:
1/8 x 3 + 1/8 x 3 +1/4 x 2 + ½ x 1 = 1.75 bits
Ta có thể mã hoá nhiều bản tin sang những từ mã ngắn hơn. Trong trường hợp đặc biệt này chiều dài từ trung bình hợp với entropy. Vì thế ta không thể tìm ra một mã với chiều dài trung bình nhỏ hơn.
Một phương pháp bắt nguồn từ các mã có chiều dài thay đổi là bắt đầu với những mã có chiều dài thay đổi và nhiều nhóm con mở rộng. Ví dụ bắt đầu với mã 1 bít ta có hai từ mã là 0 và 1 và mở rộng cho nó là: 100, 101, 110 và 111. Năm từ mã này là:
0
100
101
110
111
Một phương pháp khác bắt đầu với từ mã 2 bit 00, 01, 10, 11 và mở rộng cho một trong 4 từ mã này sang hai từ. Nếu 01 được chọn cho việc mở rộng, ta sẽ có mã 5 từ.
00
010
011
10
11
Câu hỏi bây giờ là làm sao có nhiều cách để thực hiện mở rộng mà nó sẽ cho kết quả với chiều dài trung bình nhỏ nhất. Ta đã trình bày hai cách để tìm một cách có hiệu quả những từ mã có chiều dài thay đổi. Đó là dùng mã Hufman và mã Shannon-Fano.
Mã Huffman cung cấp một kỹ thuật tổ chức cho việc tìm từ mã có chiều dài thay đổi cho một tập các bản tin. Ta trình bày các bước thực hiện như ví dụ sau đây:
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) + 1/2g(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.
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ó:
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à:
S1S1 0.81
S1S2 0.09
S2S1 0.09
S2S2 0.01
Nếu sử dụng phương pháp Shannon-Fano ta gán những từ mã như sau:
S1S1 0.81 0
S1S2 0.09 10
S2S1 0.09 110
S2S2 0.01 111
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:
S1S1S1 0.729 0
S1S1S2 0.081 100
S1S2S1 0.081 101
S1S2S2 0.009 11100
S2S1S1 0.081 110
S2S1S2 0.009 11101
S2S2S1 0.009 11110
S2S2S2 0.001 11111
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.
NÉN DỮ LIỆU (data compression)
Nén dữ liệu là một thuật ngữ được dùng rộng rãi trong các kỹ thuật làm giảm số bit truyền cho một bản tin. Mã hoá Entropy là một dạng của nén dữ liệu.
Sự thành công của các kỹ thuật nén dữ liệu, phụ thuộc vào các thuộc tính của thông tin. Ví dụ mã hoá Entropy trở nên hiệu quả nhất khi các xác suất của bản tin không bằng nhau. Những kỹ thuật khác mà ta sẽ mô tả phụ thuộc vào các thuộc tính tuần tự của bản tin. Tức chúng phụ thuộc vào các biểu tượng xảy ra trong một trật tự có thể tiên đoán.
Bây giờ ta xem sự mã hoá của một bức ảnh ti vi. Giả sử, một bức ảnh ti vi chứa 426 điểm ảnh có thể nhìn thấy (pixel) trong một đường quét ngang. Nếu ta nói về ti vi trắng đen chỉ cần gửi độ sáng (độ chói) của mỗi điểm ảnh. Giả sử ta quyết định truyền 7 bits thông tin. Thế thì, ta lượng tử độ sáng bằng 27 hoặc 128 mức khác nhau. Điều này thể hiện chất lượng của độ phân giải cao. Ta cần 7 x 426 hoặc 2982 bits để truyền thông tin cho mỗi đòng bằng cách sử dụng PCM. Một ảnh ti vi chuẩn thường chứa mộ chuỗi các điểm ảnh gần nhau với cùng độ sáng. Khi ta theo dấu của một đường quét ngang ta có thể thấy hàng trăm điểm ảnh có độ sáng giống nhau (giả sử có một hình ở giữa màn hình và phông nền, giống nhau hoặc giả sử ta gửi một đoạn văn bản trên một nền giống nhau). Trong những trường hợp như thế ta có thể sử dụng kỹ thuật nén dữ liệu (được hiểu như mã run-length) để làm giảm số bit truyền tín hiệu. Thay vì gửi độ sáng cho mỗi điểm ảnh, ta gửi vị trí bắt đầu và độ sáng của điểm ảnh đầu tiên trong số các điểm ảnh có cùng độ sáng với cùng một độ sáng. Để gửi vị trí ta cần 9 bits thông tin bởi vì 29 = 512 và có 426 vị trí khác nhau. Vì thế ta cần 9 bits cho vị trí và 7 bits cho độ sáng (tổng cộng là 16 bits). Thí dụ nếu 10 điểm ảnh lân cận có cùng độ sáng, ta cần 10 x 7 = 70 bits để gửi những thông tin này một cách độc lập. Nhưng chỉ với 16 bit để gửi chúng nếu dùng mã run-length. Khái niệm này có thể dẫn đến tiết kiệm hơn nếu được mở rộng sang hai hướng.
Một trong những bất lợi của mã run-length là tín hiệu dữ liệu xảy ra với tốc độ không đồng đều. Đó là những bit không mã hoá được gửi đi với tốc độ không đổi. Tuy nhiên, bằng cách mã hoá các vùng sáng đều lớn sẽ cho kết quả dữ liệu truyền với nhịp thấp hơn. Vì thế hệ thống đòi hỏi một vùng đệm. Một sự thiếu sót nữa là các lỗi truyền đi vì hệ thống có bộ nhớ. Một bit lỗi trong một hệ thống dùng PCM để gửi riêng thông tin từng điểm ảnh sẽ gây ra một lỗi độ sáng cho riêng điểm ảnh đó. Nhưng nếu mã run-length được dùng, một bit lỗi có thể ảnh hưởng đến toàn bộ độ sáng của đường quét.
Ta có thể dùng sự tiên đoán trong các dạng nén dữ liệu. Nếu các giá trị của dữ liệu tiếp theo có thể được tiên đoán từ các giá trị hiện tại và các giá trị trước đó thì không cần gửi tất cả dữ liệu. Chỉ cần các giá trị dữ liệu hiện tại cộng thêm một số thông số chính đủ để giúp cho việc tiên đoán.
