Đồ án Kỹ thuật mã hóa Huffman với mô hình từ điển

CHƯƠNG 0. CHƯƠNG 0 GIỚI THIỆU Ngày nay, máy tính đã thâm nhập vào hầu hết các lĩnh vực của đời sống- xã hội. Nói đến máy tính tức là nói đến hai vấn đề lớn : lưu trữ và xử lý thông tin. Với sự bùng nổ thông tin như hiện nay, việc lưu trữ và trao đổi thông tin đã và đang đặt ra nhiều vấn đề cần phải giải quyết, đó là làm sao để lưu trữ một cách tiết kiệm, hiệu quả và trao đổi thông tin một cách nhanh chóng nhất. Một giải pháp là tăng dung lượng của các thiết bị lưu trữ. Tuy nhiên, điều này đòi hỏi cao về mặt kỹ thuật phần cứng và chi phí khá tốn kém. Như vậy, giải pháp này là không kinh tế. Một giải pháp khác nhiều triển vọng hơn và mang tính khả thi đã được đặt ra, đó là nén dữ liệu. Vậy nén dữ liệu là gì ? Có thể hiểu một cách nôm na rằng, nén dữ liệu là quá trình làm giảm dung lượng lưu trữ của dữ liệu mà vẫn bảo toàn được nội dung thông tin trước đó. Như vậy, việc nén dữ liệu sẽ đem lại nhiều lợi ích thiết thực. Đó là : Tiết kiệm được không gian lưu trữ. Tăng tốc độ và giảm chi phí truyền dẫn trên mạng. Bảo mật được thông tin. Mặc dù dung lượng của các thiết bị lưu trữ ngày nay đã tăng đến tốc độ chóng mặt, có thể lên đến hàng chục Gigabytes, nhưng với những lợi ích như đã nêu trên, giải pháp nén dữ liệu trước khi lưu trữ, cũng như truyền dẫn qua mạng là điều khiến chúng ta không thể không xét đến. Nói chung, nén dữ liệu là quá trình biến đổi một luồng các kí hiệu thành một luồng các mã có kích thước nhỏ hơn ban đầu. Thông thường, một quá trình nén được tiến hành qua hai giai đoạn: (1) Mô hình hóa, là giai đoạn tiên đoán về tần suất xuất hiện của các kí tự và / hoặc chuỗi kí tự của văn bản cần nén. (2) Mã hóa, là giai đoạn dựa trên mô hình với tần suất vừa được xác định để tạo ra từ mã tương ứng. Cùng với sự phát triển mạnh mẽ của lý thuyết thông tin, có khá nhiều phương pháp mã hóa và mô hình hóa đã ra đời. Trong các phương pháp mã hóa, đáng chú ý nhất là mã hóa Huffman và mã hóa số học. Phương pháp mã hóa Huffman được D.A Huffman công bố vào năm 1952. Phương pháp mã hóa này đơn giản, dễ xây dựng và cho thời gian mã hóa ngắn. Phương pháp mã hóa số học ra đời vào cuối những năm 70. Phương pháp này hướng đến việc tối ưu độ dài từ mã nên tương đối phức tạp hơn và vì vậy thời gian mã hóa chậm hơn. Kỹ thuật nén xử lý từng kí tự một của luồng kí hiệu đầu vào được gọi là nén với mô hình thống kê (Statistical model). Ngược lại, kỹ thuật nén xem xét mỗi lúc một chuỗi các kí tự từ luồng nhập gọi là nén với mô hình từ điển (Dictionary-based model). Do đặc thù của mô hình từ điển và thực tế cũng cho thấy, với cùng một phương pháp mã hóa thì việc áp dụng mô hình từ điển sẽ cho hiệu quả nén cao hơn nhiều so với mô hình thống kê. Hầu hết các chương trình nén thương mại hiện hành đều sử dụng mô hình từ điển mà điển hình là các chương trình nén nổi tiếng như NCZip, PKZip và WinZip. Trong một thời gian ngắn, việc nghiên cứu tất cả các kỹ thuật nén dữ liệu là điều không khả thi, do vậy, trong cuốn luận văn tốt nghiệp này, tác giả chỉ đi sâu nghiên cứu về phương pháp nén dữ liệu không tổn hao dựa trên kỹ thuật mã hóa Huffman (chủ yếu là mã Huffman động) và mô hình từ điển. Do năng lực bản thân và thời gian có hạn nên Đồ án còn khá nhiều thiếu sót. Xin nhận được những lời phê bình, góp ý quý báu của các thầy cô và bạn đọc để đề tài có thể hoàn thiện hơn trong tương lai. Cấu trúc Đồ án Đồ án bao gồm 6 chương và chương trình Demo trên đĩa. Nội dung như sau : Chương 0 : Giới thiệu đề tài, vai trò và ý nghĩa của nó. Chương I : Trình bày tổng quan về lý thuyết nén và giải nén dữ liệu, làm nền tảng cho việc giải quyết vấn đề đã đặt ra trong Đồ án. Chương II : Trình bày phương pháp nén dữ liệu áp dụng kỹ thuật mã hóa Huffman dựa trên mô hình thống kê. Chương III: Tìm hiểu một số phương pháp nén dựa trên mô hình từ điển. Chương IV : Đi sâu nghiên cứu phương pháp nén dữ liệu áp dụng kỹ thuật mã hóa Huffman động, dựa trên mô hình từ điển thích ứng, làm nền tảng cho việc phát triển chương trình. Chương V : Trình bày kết quả thực nghiệm kiểm tra tính đúng đắn, chính xác của chương trình và so sánh với một số chương trình thương mại có cùng chức năng. Trên cơ sở đó, đánh giá ưu điểm và hạn chế của phương pháp nén được sử dụng. Chương VI : Kết luận, đánh giá những gì đã làm được, những gì chưa đạt được và nêu hướng phát triển của đề tài. CHƯƠNG I LÝ THUYẾT TỔNG QUAN VỀ NÉN DỮ LIỆU Khái niệm về nén dữ liệu Nén dữ liệu là quá trình làm giảm số liệu cần thiết mã vẫn bảo toàn được nội dung thông tin. Số liệu và thông tin là không đồng nhất với nhau. Số liệu chỉ là phương tiện để chuyển tải thông tin. Với cùng một nội dung thông tin, ta có thể biểu diễn bằng các dữ liệu khác nhau. Các kỹ thuật nén dữ liệu, thông thường, dựa vào một trong các đặc trưng sau: Tính hữu hạn của tập kí hiệu. Tần suất xuất hiện tương đối của các kí hiệu. Ngữ cảnh xuất hiện của các kí hiệu. Nén dữ liệu liên quan đến khái niệm thông tin trong lý thuyết thông tin. Lượng tin còn gọi là Entropy. Lượng tin của một kí hiệu được tính bằng (-log2P) với đơn vị là bit, trong đó P là xác suất xuất hiện của kí hiệu đó. Lượng tin của toàn bộ nguồn số liệu được tính bằng tổng lượng tin của các kí hiệu thành phần. Lượng tin trung bình thống kê trên một kí hiệu được gọi là Entropy của nguồn số liệu. Entropy của một nguồn số liệu càng cao thì lượng thông tin chứa đựng trong nó càng nhiều. Shannon là người đầu tiên chứng minh được sự tồn tại một giới hạn nén cho mỗi văn bản. Giới hạn ấy chính là lượng tin của văn bản. Nhìn chung, quá trình nén và giải nén dữ liệu có thể được mô tả tóm tắt theo sơ đồ sau: Quá trình nén Quá trình giải nén Dữ liệu gốc Dữ liệu nén Sơ đồ chức năng của quá trình nén dữ liệu Hình 1. Một số khái niệm cơ bản II.1. Tỉ lệ nén (compression ratio) Tỉ lệ nén là một trong những thông số quan trọng nhất của mọi phương pháp nén. Có nhiều cách khác nhau để định nghĩa tỉ lệ nén. Thông thường, người ta định nghĩa tỉ lệ nén như sau: Tuy nhiên, cần phải thấy rằng, tỉ lệ nén cao chưa phải là tất cả để đánh giá hiệu quả của một phương pháp nén. Bởi vì còn có các yếu tố khác như: chi phí về thời gian, không gian và cả độ phức tạp tính toán. II.2. Độ dư thừa số liệu Nguyên tắc chung của các phương pháp nén dữ liệu là loại bỏ các thông tin trùng lặp, các dữ liệu dư thừa đến mức tối thiểu có thể được. Việc xác định bản chất các kiểu dư thừa số liệu rất có ích trong việc xây dựng các phương pháp nén phù hợp. Nhìn chung, có bốn kiểu dư thừa chính trong dữ liệu : Sự lặp lại của những kí tự Trong một nguồn dữ liệu, nhất là các tập tin ảnh, thường có những kí tự và chuỗi kí tự lặp lại nhiều lần liên tiếp nhau. Khi đó, nguồn dữ liệu có thể được mã hóa một cách cô đọng hơn bằng cách thay thế những dãy kí tự đó bằng mã của chúng và số kí tự lặp lại. Phương pháp nén với mô hình từ điển khai thác rất hiệu quả loại dư thừa này. Sự phân bố các kí tự Xét một chuỗi kí tự, ta thường thấy có một số kí tự xuất hiện với tần suất cao hơn những kí tự khác . Như vậy, ta có thể giảm bớt lượng dữ liệu bằng cách mã hóa những kí tự xuất hiện thường xuyên với từ mã ngắn, những kí tự ít xuất hiện sẽ được mã hóa bằng những từ mã dài hơn. Kiểu dư thừa này đặc biệt phù hợp với phương pháp mã hóa Huffman. Độ dư thừa vị trí Có nhiều trường hợp, dữ liệu trong một nguồn số liệu có sự phụ thuộc lẫn nhau, do đó, nếu biết được kí hiệu xuất hiện tại một vị trí nào đó, ta có thể phỏng đoán trước một cách hợp lý sự xuất hiện của các kí hiệu khác ở những vị trí khác nhau. Ví dụ, ảnh biểu diễn trong một lưới hai chiều, một số điểm ở hàng dọc lại xuất hiện trong cùng vị trí ở các hàng khác nhau. Như vậy, thay vì lưu trữ dữ liệu ta chỉ lưu lại vị trí hàng và cột. Phương pháp nén khai tháckiểu dư thừa này gọi là phương pháp mã hóa dự đoán. Những mẫu sử dụng mật độ cao Thông thường, trong các văn bản dạng text, sự tuần tự của những kí tự bào đó sẽ tái xuất hiện với tần suất tương đối cao, vì vậy, có thể biểu diễn bằng dãy bit ngắn hơn. Để đánh giá một thuật toán nén có hiệu quả hay không, người ta sẽ dựa vào cách mà thuật toán xử lý các kiểu dư thừa như trên. Thực tế cho thấy rằng, hầu hết các kỹ thuật nén đều không đủ mềm dẻo để xử lý tất cả các kiểu dư thừa. Mỗi chiến lược nén áp dụng thường chỉ cứng nhắc cho từng kiểu số liệu mà thôi. Độ dư thừa số liệu có thể định lượng bằng toán học. Với L1,L2 là hai lượng số liệu cùng được dùng để biểu diễn một lượng tin cho trước thì độ dư số liệu tương đối RD của tập số liệu thứ nhất so với tập số liệu thứ hai là: Trong đó L1/L2 được gọi là tỉ lệ nén. II.3. Độ dài trung bình từ mã Giá trị trung bình thống kê của tất cả các từ mã trong một bộ mã được gọi là độ dài trung bình của một từ mã. C.E Shannon đã chỉ ra rằng: “Độ dài trung bình của một từ mã không bao giờ nhỏ hơn entropy của nguồn số liệu được mã hóa”. Do đó, một bộ mã tối ưu (cho hiệu suất nén cao) là bộ mã có độ dài trung bình của từ mã tiến gần đến Entropy của nguồn số liệu. II.4. Nén tổn hao và nén không tổn hao Có nhiều cách để phân loại các phương pháp nén. Cách phân loại dựa vào nguyên lý nén chia các phương pháp nén thành hai họ chính : a. Nén tổn hao (lossy compression) Nén tổn hao còn gọi là nén có mất mát thông tin. Kỹ thuật nén này chấp nhận mất mát một lượng thông tin nhất định để thu được hiệu suất nén cao hơn, do vậy, sau khi giải nén, ta sẽ không thu được dữ liệu gốc. Nén tổn hao thường được áp dụng cho các tập tin hình ảnh hay âm thanh được số hóa. Bởi vì đối với các tập tin thuộc loại này thì việc mất mát một ít thông tin là điều có thể chấp nhận được. b. Nén không tổn hao (lossless compression) Nén không tổn hao còn gọi là nén chính xác hay nén không mất thông tin. Đây là phương pháp nén mà sau khi giải nén ta thu được một bản sao chính xác của dữ liệu gốc. Phương pháp nén này thường được áp dụng đối với các nguồn số liệu mà nội dung thông tin cần được bảo toàn như các văn bản dạng text, các bảng tính hay là cơ sở dữ liệu,... Dạng nén mà ta nghiên cứu trong đồ án này là dạng nén không tổn hao. II.5. Nén số liệu = Mô hình hóa + Mã hóa [2] Nói chung, nén số liệu là chuyển đổi một luồng các kí hiệu thành một luồng các từ mã tương ứng. Nếu hiệu ứng nén xảy ra thì luồng các từ mã sẽ nhỏ hơn luồng các kí hiệu ban đầu. Việc quyết định đưa ra một từ mã nhất định cho mỗi kí hiệu hoặc một tập kí hiệu dựa trên một mô hình. Mô hình chẳng qua chỉ là một tập hợp số liệu và các nguyên tắc được sử dụng để xử lý các kí hiệu từ luồng nhập và xuất ra các từ mã. Mô hình có nhiệm vụ xác định xác suất xuất hiện của từng kí tự và/hoặc chuỗi kí tự và bộ phận mã hóa sẽ tạo ra các từ mã dựa trên các xác suất đó. Mô hình hóa và mã hóa là hai khái niệm hoàn toàn tách biệt nhau. Thế nhưng, chúng ta vẫn hay dùng thuật ngữ “mã hóa” để nói đến cả quá trình nén số liệu, mặc dù, thực chất đó chỉ mới là một giai đoạn của quá trình đó. Ví dụ, chúng ta vẫn hay dùng các thuật ngữ “mã hóa Huffman”, “mã hóa số học” để nói đến các kỹ thuật nén số liệu, trong khi đó chỉ là các phương pháp mã hóa được sử dụng cùng với một mô hình nào đó để nén số liệu. Có rất nhiều cách để mô hình hóa nguồn số liệu lại có thể cùng sử dụng một phương pháp mã hóa để tạo ra các từ mã. Ví dụ, chúng ta có thể dùng phương pháp mã hóa Huffman cho cả hai mô hình thống kê và mô hình từ điển để nén số liệu. Với phương pháp mã hóa Huffman, ta thấy một quá trình nén số liệu đầy đủ được biểu diễn như sau : Các xác suất Luồng nhập Mô hình Mã hoá Luồng ra Các ký hiệu Các từ mã Mô hình thống kê với mã hóa Huffman Hình 2. Lý thuyết về mã hóa [7] Như đã nói, nén số liệu là quá trình biến đổi một luồng các từ mã thành một luồng các từ mã. Quá trình giải nén sẽ xử lý luồng các từ mã đó để khôi phục lại nguồn số liệu ban đầu. Như vậy, việc tìm hiểu về mã nén dữ liệu là điều cần thiết. III.1. Định nghĩa mã hóa Mã hóa nguồn tin X theo bộ mã M là phép ánh xạ 1:1 biến đổi một tin xi Î X thành một tổ hợp các kí hiệu của bộ mã M. Nguồn X = {x1, x2, ..,xn} Bộ mã M = {m1, m2, ..,mk} Với k là cơ số của bộ mã Ví dụ, với mã nhị phân k = 2. Nếu tin xi được mã hóa thành mr1, mr2, ..,mrl (l là số kí hiệu của bộ mã dùng để biểu diễn xi và l cũng là độ dài từ mã). Ví dụ X = {x1, x2, ..,x4} Bộ mã nhị phân M = {0, 1} Mã hóa x1 = 00, x2 = 01, x3 = 10, x4 = 11 III.2. Một số khái niệm cơ bản Chiều dài từ mã Chiều dài từ mã là số kí hiệu của bộ mã dùng để mã hóa cho từ mã đó. Trọng lượng từ mã Trọng lượng từ mã là tổng số các kí hiệu khác 0 của từ mã Ví dụ: Từ mã 1011010 có trọng lượng là 4. Khoảng cách mã Khoảng cách mã d là số kí hiệu khác nhau tính theo vị trí tương ứng của hai từ mã có chiều dài bằng nhau W1, W2. d(W1, W2) = w(W1 Å W2), với Å là phép cộng modul-2. Khoảng cách của một bộ mã là khoảng cách mã nhỏ nhất của hai từ mã bất kỳ trong bộ mã đó. III.3. Phân loại mã Dựa vào các đặc điểm của mã, người ta phân mã ra thành nhiều loại khác nhau. Sau đây là một số cách phân loại điển hình: Phân loại theo chiều dài từ mã Mã có chiều dài không đổi. Mã có chiều dài thay đổi. Phân loại theo trọng lượng từ mã Mã có trọng lượng thay đổi. Mã có trọng lượng cố định. Phân loại theo hiệu suất thông tin Mã tối ưu. Mã chưa tối ưu. Phân loại theo cơ số của bộ mã Có thể tạo ra một bộ mã có cơ số tùy ý. Mã nhị phân (có cơ số 2) là phổ biến nhất. Phân loại theo mục đích sử dụng mã Mã sô. Mã kí tự. III.4. Một số phương pháp biểu diễn mã thông dụng Có nhiều phương pháp để biểu diễn mã. Mỗi cách đều có những ưu điểm và nhược điểm riêng. Tùy theo mục đích, ta có thể chọn cách biểu diễn cho phù hợp. a. Phương pháp liệt kê Liệt kê trong một bảng những tin của nguồn và kèm theo là các từ mã tương ứng. Ví dụ : Nguồn tin X = {x1, x2, x3, x4}. Các lớp tin của nó được mã hóa như sau: Tin x1 x2 x3 x4 Từ mã 01 10 110 001 Ưu điểm của phương pháp biểu diễn này là rõ ràng, đơn giản nhưng không phù hợp với những bộ mã lớn. b. Phương pháp đồ hình kết cấu Phương pháp này biểu diễn mã bằng một cây mã rút gọn bao gồm các nút và các nhánh có hướng. Mỗi vòng kín (bắt đầu tại nút gốc, đi theo các nhánh theo chiều mũi tên, qua các nút trung gian và kết thúc tại nút gốc) sẽ biểu diễn cho một từ mã. Thứ tự giá trị các nhánh trên đường đi chính là thứ tự giá trị các kí hiệu. Ví dụ : Đồ hình kết cấu của bộ mã 10,11,011,0101,0100. Kí hiệu v là toán tử OR, các nút được đánh số theo thứ tự xa dần nút gốc. 2 1 GỐC 3 4 0 1 1 0 0v1 1 0v1 Đồ hình kết cấu của bộ mã 10,11,011,0101,0100 Hình 3. c. Phương pháp cây Cây mã được biểu diễn bao gồm gốc và các nhánh. Trong cây có chứa các nút. Nút gốc chính là gốc của cây (mức 0). Nút lá nằm tận cùng của nhánh. Trừ nút gốc và các nút lá ra, các nút còn lại là các nút nhánh. Từ một nút nhánh có thể phát đi nhiều nhất là m nhánh (ứng với cơ số m của mã). Mỗi nhánh biểu diễn cho một từ mã. Từ mã đó có thứ tự các trị kí hiệu đi từ gốc, qua các nút nhánh và dừng lại ở nút lá tương ứng của nhánh. Dựa vào cây mã, chúng ta có thể nhận biết mã đã cho là mã đều (các nút lá có cùng bậc), hay không đều, mã đầy hay vơi. Mã là đầy khi mọi nút nhánh bậc trước các nút lá đều có m nhánh. Ví dụ : Cho bộ mã 00, 01, 11, 1010, 1011. Cây mã biểu diễn cho bộ mã này là: 0 1 0 1 0 1 0 1 1 mức gốc ( 0 ) mức 1 (n = 1) mức 2 (n = 2) mức 3 (n = 3) mức 4 (n = 4) Cây mã nhị phân cho bộ mã 00,01,11,1010,1011 Hình 4. III.5. Điều kiện để mã phân tách được Mã được gọi là có tính phân tách nếu như khi nhận được một chuỗi kí hiệu trong quá trình tạo mã, chúng ta có thể tách ra được các thành phần cơ bản là các từ mã và cách tách đó là đúng đắn và duy nhất (vì nếu không, bộ giải mã có thể sẽ nhầm lẫn trong quá trình làm việc). Để có tính phân tách được, bộ mã phải thỏa mãn điều kiện cần và đủ sau: Bất kỳ dãy các từ mã nào của bộ mã cũng không được trùng với một dãy từ mã khác của cùng bộ mã. Độ chậm giải mã : Độ chậm giải mã là số kí hiệu nhận được cần thiết để có thể phân tách được thành các từ mã. Đối với bộ mã phân tách được, độ chậm giải mã là hữu hạn, nhưng cũng có trường hợp là vô hạn. Đối với trường hợp vô hạn, bộ mã có thể xem là không phân tách được. Để kiểm tra một bộ mã có tính phân tách hay không, người ta xây dựng bảng thử mã phân tách và qua đó, xác định độ chậm giải mã. Các bước xây dựng bảng thử mã phân tách : Sắp xếp các từ mã thành một cột. Cột này được đánh số 1. Đối sánh các từ mã ngắn với các từ mã dài hơn trong cột 1, nếu từ mã ngắn trùng với phần đầu của từ mã dài hơn thì lấy phần còn lại của từ mã dài ghi vào cột thứ hai. Lặp lại bước 2, với cột k là cột chứa kết quả đối sánh giữa cột (k-1) với cột (k-2). Tiếp tục thực hiện bước 3 cho đến khi cột k trở nên trống rỗng. Để mã có tính phân tách, điều kiện cần và đủ là: Trong cột có chỉ số k >= 2 không có một tổ hợp nào trùng với các từ mã trong cột 1. Ví dụ : Cho bộ mã 01, 11, 001, 1001, 1011. Ta có bảng thử mã phân tách: Cột 1 Cột 2 01 11 001 1001 1011 Ta có độ chậm giải mã bằng 0 vì cột 2 trống rỗng. Như vậy, bộ mã đã cho có tính phân tách. Độ chậm giải mã có thể được đánh giá qua bảng thử mã phân tách như sau: Trong đó: Tc : độ chậm giải mã. k: giá trị của cột rỗng. nmin, nmax : độ dài từ mã ngắn nhất và dài nhất của bộ mã. Chúng ta có thể rút ra kết luận qua các nhận xét và ví dụ trên: Mã có khả năng phân tách được khi và chỉ khi bất kỳ một tổ hợp mã nào cũng không trùng với phần đầu của bất kỳ một tổ hợp mã khác trong cùng bộ mã. III.6. Mã có tính tiền tố (prefix) Phần tiền tố (prefix) của một từ mã có độ dài l là một bộ phận của từ mã đó sau khi bỏ đi k kí hiệu cuối cùng (0 < k < l). Ví dụ : Từ mã 1001101 có các tiền tố là: 100110, 10011, 1001, 100, 10 và 1. Định nghĩa Một bộ mã được gọi là có tính chất tiền tố nếu mọi từ mã thuộc bộ mã đều không phải là phần đầu của một từ mã khác trong cùng bộ mã. Nhờ vào tính chất tiền tố này mà mã có tính prefix thường được sử dụng để làm mã nén dữ liệu. Ta có thể nhận thấy rằng, khi biểu diễn mã bằng cây mã, mã có tính chất tiền tố khi các từ mã chỉ là nút lá. III.7. Định lý về độ dài trung bình từ mã Cho nguồn tin u = {ui} với i = 1 ¸ n và các xác suất p(ui) tương ứng. Mã hóa các tin ui bằng mã nhị phân và giả sử các kí hiệu của mã có các xác suất p(xi) bằng nhau: p(xi) = p(X) = hằng số. Ta có lượng tin trung bình bằng lượng tin của một kí hiệu mã và đạt giá trị cực đại: I(xi) = I(x) = log22 = 1 (bit / kí hiệu) Nếu ni là chiều dài của mã nhị phân mã hóa tin ui thì lượng tin chứa trong từ mã là ni bit. Ở đây, lượng tin trung bình chứa trong một từ mã bằng độ dài trung bình của các từ mã. Để tin tức không bị hao hụt qua quá trình mã hóa, lượng tin trung bình của từ mã phải không nhỏ hơn lượng tin trung bình của một tin trong nguồn tin. Về số đo, lượng tin trung bình của một tin bằng với Entropy của nguồn tin E(u). Để phép mã hóa là đúng, điều kiện sau đây phải được thỏa mãn : E(u) £ ntblogm hay E(u) £ ntb Ta có định lý : Độ dài trung bình của một từ mã không bao giờ bé hơn tỉ số Entropy của nguồn tin được mã hóa chia cho lượng tin trung bình cực đại của một kí hiệu mã. E(u) chính là giới hạn dưới của độ dài trung bình ntb của một từ mã. Như vậy, độ dài trung bình ntb của một từ mã bằng với Entropy của nguồn tin khi và chỉ khi độ dài ni của một từ mã bất kỳ bằng với lượng tin riêng I(ui) của tin mà nó mã hóa. I(ui) được tính bằng -log(p(ui)). Bây giờ, chúng ta đi xác định giới hạn trên của độ dài trung bình của từ mã. Vì ni là một số nguyên, mà I(ui) thường không phải là một số nguyên nên để đạt được một bộ mã có độ dài trung bình nhỏ nhất thì độ dài của mỗi từ mã phải thỏa mãn điều kiện sau: I(ui) £ ni £ I(ui) + 1 Lấy trị trung bình thống kê hai vế của bất đẳng thức, ta được : E(u) £ ntb £ E(u) + 1 Từ đây, ta có định lý về giới hạn trên của độ dài trung bình của từ mã : Có thể tạo được bộ mã có độ dài trung bình của từ mã không lớn hơn tỷ số Entropy của nguồn được mã hóa trên lượng tin trung bình cực đại chứa trong một kí hiệu mã cộng thêm một đơn vị. Một bộ mã được gọi là bộ mã thống kê tối ưu khi nó có độ dài trung bình thỏa mãn hai giới hạn nêu trên. Đặc điểm của mã thống kê tối ưu là