複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/克拉夫特不等式/19120316
複製
複製成功

克拉夫特不等式

鎖定
克拉夫特不等式是編碼理論中的一個數學關係，給出了一個碼字長度集合存在唯一可解編碼/單義可譯碼（uniquely decodable code）的必要條件 [1]  。因為這個不等式在前綴碼和樹上面應用很多，所以在計算機科學和信息學中很常用。 [2] 
中文名
克拉夫特不等式
外文名
Kraft inequality
Kraft–McMillan inequality
提出者
克拉夫特、麥克米蘭
提出時間
1949年
適用領域
編碼理論

目錄

  1. 1 定義
  2. 2 發展歷史
  3. 3 應用
  4. 4 影響及意義

克拉夫特不等式定義

設符號表中的原始符號為：
在大小為
的字符集上編碼為唯一可解編碼的碼字長度為
[1] 
則，
反之, 給定一個滿足上述不等式的自然數集合
, 則在大小為
字符集上，存在一組唯一可解編碼符合相應的碼字長度。 [1] 

克拉夫特不等式發展歷史

1949年，克拉夫特不等式發表在克拉夫特的一本專著上。然而，克拉夫特的論文只討論了前綴碼，並將這個不等式的歸因於雷蒙德·雷德赫弗不等式（Raymond Redheffer）。
1956年，麥克米蘭獨立發現了這個結果。他證明了一般情況下唯一可解碼的結果，並將前綴碼的版本歸因於Joseph Leo Doob在1955年提到的一種現象。

克拉夫特不等式應用

克拉夫特不等式對碼字限制長度以保證前綴編碼的可能性。這個不等式説明碼字長度指數的倒數的分佈和概率質量函數很相似。克拉夫特不等式可以想象成一個受限的編碼庫，越短的編碼代價越大。
  • 如果克拉夫特不等式中嚴格成立，相應的編碼有冗餘（redundancy）。
  • 如果克拉夫特不等式中等式成立，相應的編碼被稱作完備碼（complete code）。
  • 如果克拉夫特不等式不成立，相應的編碼不是唯一可解編碼（uniquely decipherable）。 [1] 
  • 對於每一個唯一可解碼的代碼，都存在一個長度分佈相同的前綴碼。 [1] 

克拉夫特不等式影響及意義

克拉夫特不等式(Kraft inequality)信源編碼理論中的一個重要不等式.當一個碼的任意碼字與比它更長的任意碼字的字首不相同時，稱此碼為滿足字首條件的碼.由碼字分別為N;(i=1,2,……,M)的M個碼字所組成而且又滿足字首條件的碼，其存在的充分必要條件是滿足公式M-N＜1此式稱為克拉夫特不等式.
參考資料
  • 1.    吳鑫. 關於即時碼判斷方法的探討[J]. 廊坊師範學院學報(自然科學版), 2012, 12(006):22-23.
  • 2.    孫麗華、陳榮伶．信息論與編碼(第4版)：電子工業出版社，2016年：60-63