克拉夫特不等式

克拉夫特不等式克拉夫特不等式是編碼理論中的一個(gè)數(shù)學(xué)關(guān)系，給出了一個(gè)碼字長度集合存在唯一可解編碼/單義可譯碼（uniquelydecodablecode）的必要條件。因?yàn)檫@個(gè)不等式在前綴碼和樹上面應(yīng)用很多，所以在計(jì)算機(jī)科學(xué)和信息學(xué)中很常用。設(shè)符號(hào)表中的原始符號(hào)為：在大小為的字符集上編碼為唯一可解編碼的碼字長度為則，反之,給定一個(gè)滿足上述不等式的自然數(shù)集合,則在大小為字符集上，存在一組唯一可解編碼符合相應(yīng)的碼字長度。1949年，克拉夫特不等式發(fā)表在克拉夫特的一本專著上。然而，克拉夫特的論文只討論了前綴碼，并將這個(gè)不等式的歸因于雷蒙德·雷德赫弗不等式（RaymondRedheffer）。1956年，麥克米蘭獨(dú)立發(fā)現(xiàn)了這個(gè)結(jié)果。他證明了一般情況下唯一可解碼的結(jié)果，并將前綴碼的版本歸因于JosephLeoDoob在1955年提到的一種現(xiàn)象。應(yīng)用克拉夫特不等式對(duì)碼字限制長度以保證前綴編碼的可能性。這個(gè)不等式說明碼字長度指數(shù)的倒數(shù)的分布和概率質(zhì)量函數(shù)很相似?？死蛱夭坏仁娇梢韵胂蟪梢粋€(gè)受限的編碼庫，越短的編碼代價(jià)越大。如果克拉夫特不等式中嚴(yán)格成立，相應(yīng)的編碼有冗余（redundancy）。如果克拉夫特不等式中等式成立，相應(yīng)的編碼被稱作完備碼（completecode）。如果克拉夫特不等式不成立，相應(yīng)的編碼不是唯一可解編碼（uniquelydecipherable）。對(duì)于每一個(gè)唯一可解碼的代碼，都存在一個(gè)長度分布相同的前綴碼。影響及意義克拉夫特不等式(Kraftinequality)信源編碼理論中的一個(gè)重要不等式.當(dāng)一個(gè)碼的任意碼字與比它更長的任意碼字的字首不相同時(shí)，稱此碼為滿足字首條件的碼.由碼字分別為N;(i=1,2,……,M)的M個(gè)碼字所組成而且又滿足字首條件的碼，其存在的充分必要條件是滿足公式M-N＜1此式稱為克拉夫特不等式.craft不等式是克拉夫特不等式，克拉夫特不等式(Kraftinequality)信源編碼理論中的一個(gè)重要不等式，當(dāng)一個(gè)碼的任意碼字與比它更長的任意碼字的字首不相同時(shí)，稱此碼為滿足字首條件的碼?？死蛱夭坏仁?Kraftinequality)信源編碼理論中的一個(gè)重要不等，當(dāng)一個(gè)碼的任意碼字與比它更長的任意碼字的字首不相同時(shí)，稱此碼為滿足字首條件的碼，由碼字分別為N(i=1，2，……，M)的M個(gè)碼字所組成而且又滿足字首條件的碼，其存在的充分必要條件是滿足公式M-N<1此式稱為克拉夫特不等式?？死蛱夭坏仁?，碼長和熵的關(guān)系核心思想：比方說有一本書，書里的有些詞是高頻詞，那么我們就希望這些高頻詞能用碼長盡量短的碼來表示，而把碼長長的碼分配給低頻詞，以最小化總的碼長。在這種情況下，可以用“碼長的期望∑p_x*l(x)”來作為需要最優(yōu)化的目標(biāo)函數(shù)，因?yàn)楦怕势鋵?shí)代表出現(xiàn)的頻率，頻率高時(shí)就要讓被分配的碼長l(x)盡可能小，而當(dāng)p_x本身很小時(shí)l(x)大一些也沒所謂?？死蛱夭坏仁剑骸?.5^(l(x))≤1——針對(duì)：可解碼兩個(gè)“界”：1.E(l(X))≥H(X)（基于克拉夫特不等式導(dǎo)出）——針對(duì)：可解碼2.E(l(X))≤H(X)+1（香農(nóng)碼）——針對(duì)：互不為前綴碼（即可瞬時(shí)解碼）對(duì)課本做出點(diǎn)注解：1.

克拉夫特不等式（命題3.2）課本給的證明不是更一般的情況（可解碼），而是特殊的情況（可瞬時(shí)解碼），以下對(duì)這個(gè)證明做出總結(jié)。由上一次筆記可得知：“獲取互不為前綴的一組碼”等同于“構(gòu)建一棵二叉樹并取葉節(jié)點(diǎn)”，證明充分性和必要性都是圍繞二叉樹入手，從二叉樹可以導(dǎo)出獲取的葉節(jié)點(diǎn)之和最大不超過1，從克拉夫特不等式出發(fā)可以構(gòu)建一棵二叉樹。注意：構(gòu)建好二叉樹并且得到很多葉節(jié)點(diǎn)后不代表所有這些葉節(jié)點(diǎn)都要投入使用，只使用一部分就會(huì)使得克拉夫特不等式左邊的求和項(xiàng)小于1。2.

碼長期望與熵的關(guān)系1（命題3.3）若要讓等號(hào)成立，則公式3.10和公式3.12那兩個(gè)不等式要是等號(hào)才行：3.10變成等號(hào)意味著t=1，也就是滿足克拉夫特不等式；3.12變成等號(hào)意味著相對(duì)熵為0，也就是此時(shí)Px和Qx的pmf是一模一樣的，由于Px的pmf是定的，而Qx卻不一定——因?yàn)閘(x)是變化的，所以需要找到一組lx（即定值）使得Qx定下來、且每根pmf和Px的pmf一一對(duì)應(yīng)相等。3.

碼長期望與熵的關(guān)系2——香農(nóng)碼（命題3.4）┌x┐指的是對(duì)x向上取整，就是給它拉大了。公式3.14第二個(gè)不等式的來歷：0.5^x是一個(gè)單調(diào)遞減函數(shù)，x被拉大了，0.5^x就減小了。證明思路：先說明這樣給l(x)取值滿足克拉夫特不等式，然后如剛才命題3.2所述，從克拉夫特不等式出發(fā)可以構(gòu)建一棵二叉樹，也就是找到一組互不為前綴碼?？偨Y(jié)一下就是這樣給l(x)取值是可以找到一組prefixcode，并且在代入l(x)=...后可以得到一個(gè)不等式E(l(X))≤H(X)+1。物理意義（需要再仔細(xì)想想）：結(jié)合一下這兩個(gè)命題，可知在互不為前綴碼的情況下，隨機(jī)變量X的熵≤碼長的期望≤隨機(jī)變量X的熵+1。也就是說令長度的期望為H(X)時(shí)是可解碼的，卻不一定可瞬時(shí)解碼（前面那個(gè)1/2,1/4,1/4的例子也提出了這種情況是故意取1/2的n次方才會(huì)在碼長期望為H(x)時(shí)可瞬時(shí)解碼，更一般的情況下則不一定），但是若想可瞬時(shí)解碼只需要令碼長的平均值（即期望E(l(X))）額外增加（lose）1比特（即1位）