第4章信源無失真編碼講義課件

信源的主要問題：信源的描述（數(shù)學(xué)建模）；信源輸出信息能力的定量分析（信源熵）；信源信息的有效表示（信源編碼）。（發(fā)送者）信道信宿信源干擾或噪聲消息（接收者）信源編碼由于信源符號之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。

信源編碼的基本途徑有兩個：使序列中的各個符號盡可能地互相獨立，即解除相關(guān)性；使編碼中各個符號出現(xiàn)的概率盡可能地相等，即概率均勻化。信源編碼分類：無失真編碼：只對信源的冗余度進(jìn)行壓縮，不會改變信源的熵，又稱冗余度壓縮編碼，它能保證碼元序列經(jīng)譯碼后能無失真地恢復(fù)成信源符號序列。有失真編碼：會改變信源的熵，不可逆壓縮，又稱熵壓縮編碼。無失真信源編碼的作用：符號變換：使信源的輸出符號與信道的輸入符號相匹配；冗余度壓縮：使編碼之后的新信源概率分布均勻化，信息含量效率等于或接近于100%。單符號信源無失真編碼器模型編碼器f信源f是一一對應(yīng)的映射

bit/碼字或bit/符號

bit/碼元新信源X

：編碼后的信息率R

：平均一個碼元攜帶的信息量。bit/碼元平均碼長越小，每個碼元攜帶的信息量就越多，傳輸一個碼元就傳輸了較多的信息。碼元/符號

編碼效率：編碼后的實際信息率與編碼后的最大信息率之比。

新信源的冗余度也是碼的冗余度：唯一可譯碼（UDC）：該碼的碼字組成的任意有限長碼字序列都能恢復(fù)成唯一的信源序列。否則稱為非唯一可譯碼。碼是唯一可譯碼的充分必要條件是：由碼中的碼字組成的任意有限長的碼字序列（也是碼元序列），都能唯一劃分成一個個的碼字，且任一碼字只與唯一一個信源符號對應(yīng)。奇異碼：含相同碼字的碼。否則稱為非奇異碼。非續(xù)長碼：碼中任一碼字都不是另一碼字的續(xù)長（延長）。否則為續(xù)長碼。非即時碼：如果接收端收到一個完整的碼字后，不能立即譯碼，還需等下一個碼字開始接收后才能判斷是否可以譯碼。否則為即時碼。舉例：下雨天留客天留我不留第4章離散無記憶信源無失真編碼4.1信源編碼概論4.2碼的唯一可譯性4.3定長編碼定理和定長編碼方法4.4變長編碼定理4.5變長編碼方法4.6幾種實用的無失真信源編碼4.1信源編碼概論采取適當(dāng)信道編碼和譯碼措施后，可使信道傳送的差錯率降到允許的范圍之內(nèi)，因此，圖中虛框部分可近似地視為一個等效的無損確定信道，簡稱為無噪信道，這一點是我們討論信源編碼的前提。1、基本概念噪聲信道信源編碼信源信宿等效無噪信道信源譯碼信道編碼信道譯碼無損確定信道（等效）信源編碼信源信宿信源譯碼信源編碼分類：無失真編碼、有失真編碼。無失真編碼：只對信源的冗余度進(jìn)行壓縮，不會改變信源的熵，又稱冗余度壓縮編碼，它能保證碼元序列經(jīng)譯碼后能無失真地恢復(fù)成信源符號序列。有失真編碼：又稱熵壓縮編碼，將在第6章討論。無失真信源編碼的作用：（1）符號變換：使信源的輸出符號與信道的輸入符號相匹配；（2）冗余度壓縮：使編碼之后的新信源概率分布均勻化，信息含量效率等于或接近于100%。2、編碼器模型碼長li

：碼字wi

所含碼元的個數(shù)。單位：碼元/符號，r進(jìn)制單位/符號。

定長碼(FLC，F(xiàn)ixedLengthcode)

：碼中所有碼字均有相同的碼長l；否則稱為變長碼(VLC，VariableLengthcode)。平均碼長：碼W碼字集W

碼字wi

碼元集

X碼元xi

編碼器f信源信源編碼f：一一對應(yīng)的變換。碼元/符號

定長碼：碼元/符號

平均碼長是衡量碼的性能的重要參數(shù)，“平均碼長小”說明平均一個碼元所攜帶的信息量大，信息的冗余就小。例：編碼設(shè)DMS的概率空間為對其單個符號進(jìn)行二進(jìn)制編碼。

編碼器f信源碼元/符號

碼元/符號

編碼策略：經(jīng)常出現(xiàn)（概率大）的符號采用較短的碼字，不經(jīng)常出現(xiàn)（概率?。┑姆柌捎幂^長的碼字。編碼策略：采用等長的碼字。3、編碼器的輸出編碼器f信源f是一一對應(yīng)的映射

bit/碼字或bit/符號

bit/碼元新信源X

：編碼后的信息率R

：平均一個碼元攜帶的信息量。bit/碼元平均碼長越小，每個碼元攜帶的信息量就越多，傳輸一個碼元就傳輸了較多的信息。4、編碼效率

為了衡量編碼效果，定義編碼效率：編碼后的實際信息率與編碼后的最大信息率之比。

注：編碼效率實際上也是新信源X的信息含量效率或熵的相對率。編碼器f信源新信源的冗余度也是碼的冗余度：4.2碼的唯一可譯性舉例：1）下雨天留客天留我不留2）明年逢春好不晦氣終年倒運(yùn)少有余財此地安能居住其人好不傷悲無損確定信道（等效）信源編碼信源信宿信源譯碼4.2碼的唯一可譯性f為一一對應(yīng)的變換只是無失真編碼的必要條件，并不充分;要保證將碼元序列無失真地恢復(fù)成信源符號序列，還要求編出的碼自身具有獨特的結(jié)構(gòu)。有實用價值的碼應(yīng)該具有唯一可譯性，即能從碼字序列（也是碼元序列）唯一地恢復(fù)成信源符號序列。無損確定信道（等效）信源編碼信源信宿信源譯碼1、唯一可譯碼（UDC，UniquelyDecodableCode）唯一可譯碼（UDC）：該碼的碼字組成的任意有限長碼字序列都能恢復(fù)成唯一的信源序列。否則稱為非唯一可譯碼。碼是唯一可譯碼的充分必要條件是：由碼中的碼字組成的任意有限長的碼字序列（也是碼元序列），都能唯一劃分成一個個的碼字，且任一碼字只與唯一一個信源符號對應(yīng)。奇異碼：含相同碼字的碼。否則稱為非奇異碼。非續(xù)長碼：碼中任一碼字都不是另一碼字的續(xù)長（延長）。否則為續(xù)長碼。非即時碼：如果接收端收到一個完整的碼字后，不能立即譯碼，還需等下一個碼字開始接收后才能判斷是否可以譯碼。否則為即時碼。5種不同的碼W1：定長碼。W3：變長碼。奇異碼。定長非奇異碼肯定是UDC。W2：定長碼。W4：變長碼。W5：變長碼。非奇異碼。非奇異碼。非奇異碼。非奇異碼。續(xù)長碼。非續(xù)長碼。續(xù)長碼。即時碼。非即時碼。奇異碼肯定不是UDC。不是UDC。非續(xù)長碼肯定是UDC。是UDC。非即時碼。唯一可譯碼定長非奇異碼非續(xù)長碼非奇異碼碼奇異碼非奇異碼非唯一可譯碼唯一可譯碼定長非奇異碼變長非續(xù)長碼（部分）變長續(xù)長碼非分組碼分組碼SardinasPatterson判斷法對信源U編出6種不同的碼，如下表所示。

1）這6種碼分別是什么碼？哪些是UDC？

2）分別求出各碼的平均碼長。2、碼樹碼樹從樹根開始向上長出樹枝，樹枝代表碼元，樹枝與樹枝的交點叫做節(jié)點。r進(jìn)制碼樹：碼元個數(shù)為r，各節(jié)點（含樹根）向上長出的樹枝數(shù)不大于r。l階節(jié)點：經(jīng)過l根樹枝才能到達(dá)的節(jié)點。終端節(jié)點或端點：向上不長出樹枝的節(jié)點。碼字：與碼樹上的節(jié)點對應(yīng)，組成該碼字的碼元就是從樹根開始到該節(jié)點所經(jīng)過的樹枝（或碼元）。非續(xù)長碼：所有碼字均處于終端節(jié)點，即端點上。

整樹：r進(jìn)制碼樹各節(jié)點（包括樹根）向上長出的樹枝數(shù)均等于r。一階節(jié)點二階節(jié)點三階節(jié)點W1={00，01，10，11}W4={0，10，110，111}W5={0，01，011，111}3、Kraft不等式不滿足Kraft不等式的碼肯定不是非續(xù)長碼；滿足Kraft不等式的碼也不一定是非續(xù)長碼；根據(jù)滿足Kraft不等式的碼長集合可構(gòu)造出一個非續(xù)長碼；上述定理對唯一可譯碼仍然成立。

非續(xù)長碼存在性定理：對于任一進(jìn)制非續(xù)長碼，各碼字的碼長為必須滿足Kraft不等式：

反過來，若上式成立，就一定能構(gòu)造一個進(jìn)制非續(xù)長碼。W1={0，10，110，111}W2={0，01，011，111}例如：Kraft不等式是惟一可譯碼存在的充要條件；如果碼是唯一可譯碼，則必定滿足該不等式；如果滿足Kraft不等式，則這種碼長的惟一可譯碼一定存在；但不表示所有滿足不等式的碼一定是惟一可譯碼。

唯一可譯碼存在性定理：對于任一進(jìn)制唯一可譯碼（UDC），各碼字的碼長為，必須滿足Kraft不等式：

反過來，若上式成立，就一定能構(gòu)造一個進(jìn)制唯一可譯碼（UDC）。W1={0，10，110，111}W2={1，10，011，111}例如：對任意碼字序列‘101110111’，按W2中的碼字，可以分割為10，111，011，1或者1，011，10，1114.3定長編碼定理和定長編碼方法1、對信源輸出的符號序列進(jìn)行編碼

DMS編碼器fDMS編碼器f對信源U的單個符號進(jìn)行編碼

對信源U的N長符號串進(jìn)行編碼

對擴(kuò)展信源UN的單個符號進(jìn)行編碼

2、定長編碼定理DMS編碼器fr進(jìn)制定長編碼，碼長為lN，可用的碼字?jǐn)?shù)目：唯一可譯信息傳輸率編碼效率bit/碼元

定長無失真編碼定理：用r元符號表對離散無記憶信源U的N長符號序列進(jìn)行定長編碼，N長符號序列對應(yīng)的碼長為lN，若對于任意小的正數(shù)，有不等式

就幾乎能做到無失真編碼，且隨著序列長度N的增大，譯碼差錯率趨于0。反過來，若

就不可能做到無失真編碼，且隨著N的增大，譯碼差錯率趨于1。3、定長編碼方法（例）對U的單個符號進(jìn)行2進(jìn)制編碼。碼元集：X={0，1}

取l=3bit/符號碼元/符號碼元/符號解：提高編碼效率的方法：對符號串進(jìn)行編碼，同時引入一定的失真。P1154.4變長編碼定理(香農(nóng)第一定理)無失真變長編碼定理：用元符號表對離散無記憶信源的長符號串進(jìn)行變長編碼，記長符號串對應(yīng)的平均碼長為，那么，要做到無失真編碼，平均碼長必須滿足

另一方面，一定存在唯一可譯碼，其平均碼長滿足變長編碼不要求所有碼字長度相同，但要求平均碼長最小。N趨于無窮時平均碼長和編碼效率的極限：

隨著信源序列長度的增大，單個信源符號所需的碼元數(shù)愈接近信源的熵，編碼效率提高，當(dāng)然編碼過程也愈復(fù)雜。例：對二元DMS進(jìn)行無失真編碼：N=1若用二元碼符號(0，1)進(jìn)行定長編碼：。平均碼長＝1碼元/信源符號編碼效率為輸出的信息效率要求：對比定長編碼與變長編碼的編碼效率（N=2,3,4）。練習(xí)題對U的二次擴(kuò)展信源進(jìn)行定長編碼，碼表如下表：uip(ui)碼字u1u19/1600u1u23/1601u2u13/1610u2u21/1611編碼效率為碼字平均長度單個符號的平均碼長N=2N=3,4時，對U的二次擴(kuò)展信源進(jìn)行變長編碼，碼表如下表：uip(ui)碼字u1u19/160u1u23/1610u2u13/16110u2u21/16111N=2編碼效率為碼字平均長度單個符號的平均碼長N=3,4時，分析：1、比較定長編碼與變長編碼的編碼效率可知，尤其在N較大時變長編碼的效率遠(yuǎn)大于定長編碼。N定長變長20.8110.96130.8110.98540.8110.9912、若對定長編碼與變長編碼同樣要求編碼效率達(dá)到96%，允許的譯碼錯誤概率時，定長編碼所需序列長度N：所需的信源序列長度：同樣的編碼效率，變長編碼信源序列長度N=2時即可滿足編碼效率達(dá)到96%的要求。隨著N的增加，編碼效率趨近于1。4.5變長編碼方法變長編碼采用非續(xù)長碼；力求平均碼長最小，此時編碼效率最高，信源的冗余得到最大程度的壓縮；對給定的信源，使平均碼長達(dá)到最小的編碼方法稱為最佳編碼，編出的碼稱為最佳碼；三種變長編碼方法：霍夫曼編碼、費諾編碼以及香農(nóng)編碼；霍夫曼編碼是真正意義下的最佳編碼。1、霍夫曼編碼二進(jìn)制霍夫曼編碼過程如下：（1）將信源符號按概率大小排序；（2）對概率最小的兩個符號求其概率之和，同時給兩符號分別賦予碼元“0”和“1”；（3）將“概率之和”當(dāng)作一個新符號的概率，與剩下符號的概率一起，形成一個縮減信源，再重復(fù)上述步驟，直到“概率之和”為1為止；（4）按上述步驟實際上構(gòu)造了一個碼樹，從樹根到端點經(jīng)過的樹枝即為碼字。符號概率碼字Wi碼長li11012001300014000015000001600000062進(jìn)制霍夫曼編碼。碼元集：X={0，1}

霍夫曼編碼的基本特點編出的碼是非續(xù)長碼：霍夫曼編碼實際上構(gòu)造了一個碼樹，碼樹從最上層的端點開始構(gòu)造，直到樹根結(jié)束，最后得到一個橫放的碼樹。平均碼長最小：霍夫曼編碼采用概率匹配方法來決定各碼字的碼長，概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼。碼字不唯一：每次對概率最小的兩個符號求概率之和形成縮減信源時，就構(gòu)造出兩個樹枝，由于給兩個樹枝賦碼元時是任意的，碼字不唯一。定長編碼與變長編碼冗余壓縮效果比較定長編碼(P115)變長編碼碼元/符號碼元/符號bit/符號bit/碼元bit/碼元定長編碼：{001，010，011，100，101，110，111}變長編碼：{1，01，001，0001，00001，000001，000000}符號概率碼字Wi碼長li0.35110.300120.2000130.10000140.040000150.00500000160.00500000062進(jìn)制霍夫曼編碼。碼元集：X={0，1}

碼元/符號符號概率碼字Wi碼長li0.351120.301020.200120.1000130.04000140.0050000150.0050000052進(jìn)制霍夫曼編碼。碼元集：X={0，1}

碼元/符號碼字Wi碼長li1101200130001400001500000160000006碼字Wi碼長li112102012001300014000015000005碼方差：碼字不同，碼長也不同，但平均碼長相同，因此編碼效率相同。r進(jìn)制霍夫曼編碼每次求縮減信源時，求r個最小概率之和，即將概率最小的r符號縮減為一個新符號，直到概率之和為1終止。新問題：縮減到最后時剩下不到r個符號了。為保證平均碼長最小，希望縮減到最后剛好還剩下r個符號。為達(dá)到此目的，可給信源添加幾個無用的符號（概率為0的符號），使得信源符號數(shù)q滿足:q+i=(r-1)θ+r

信源縮減的次數(shù)增加無用符號的個數(shù)符號概率碼字Wi碼長li0.32210.22110.180220.160120.0800230.0400130.003進(jìn)制霍夫曼編碼。碼元集：X={0，1，2}

碼元/符號符號串的霍夫曼編碼例：對如下DMS進(jìn)行2進(jìn)制霍夫曼編碼，分別對單個符號和二元符號串進(jìn)行編碼。bit/符號符號概率碼字碼長u10.4511u20.35012u30.20002碼元/符號對單個符號進(jìn)行編碼符號概率碼字碼長u1u10.2025112u1u20.15750113u2u10.15750013u2u20.12250003u1u30.091013u3u10.0901014u2u30.0701004u3u20.0710014u3u30.0410004碼元/符號對二元符號串進(jìn)行編碼2、費諾（Fano）編碼費諾（Fano）編碼也是構(gòu)造一個碼樹，因此，編出的碼是非續(xù)長碼，但不一定是最佳碼。費諾編碼步驟(以二進(jìn)制編碼為例)：（1）將信源符號按概率從大到小的排序；（2）將信源符號分成2組，使2組信源符號的概率之和近似相等，并給2組信源符號分別賦碼元“0”和“1”；（3）接下來再把各小組的信源符號細(xì)分為2組并賦碼元，方法與第一次分組相同；（4）如此一直進(jìn)行下去，直到每一小組只含一個信源符號為止；

（5）由此即可構(gòu)造一個碼樹，所有終端節(jié)點上的碼字組成費諾碼。符號ui概率P(u1)碼字Wi碼長liu10.20002u20.190103u30.180113u40.17102u50.151103u60.1011104u70.01111142進(jìn)制費諾編碼。碼元集：X={0，1}

碼元/符號bit/符號3、香農(nóng)編碼香農(nóng)（Shannon）編碼步驟(以二進(jìn)制編碼為例)：（1）將信源符號按概率從大到小的排序；（2）按下式求i個信源符號對應(yīng)的碼長li，并取整；（3）按下式求i個信源符號的累加概率Pi；（4）將累加概率Pi轉(zhuǎn)換成二進(jìn)制數(shù)；（5）取Pi二進(jìn)制數(shù)小數(shù)點后li個二進(jìn)制數(shù)字作為第i個信源符號的碼字。消息符號ui消息概率pi-logpi碼長li累加概率碼字wiu10.22.3430000u20.192.4130.2001u30.182.4830.39011u40.172.5630.57100u50.152.7430.74101u60.103.3440.891110u70.016.6670.991111110

對給定信源進(jìn)行r=2進(jìn)制香農(nóng)編碼?；舴蚵幋a費諾編碼香農(nóng)編碼平均碼長（碼元/符號）2.722.743.14編碼效率95.96%95.3%83.1%練習(xí)（1）對U進(jìn)行霍夫曼編碼，并求出平均碼長和編碼效率。分析編碼的冗余壓縮效果。（2）對U進(jìn)行費諾編碼，并求出平均碼長和編碼效率。（3）對U進(jìn)行香農(nóng)編碼，并求出平均碼長和編碼效率。注：設(shè)DMS為用二元符號表對其進(jìn)行定長編碼，（1）求無失真定長編碼的最小碼長和編碼效率。（2）將編碼器的輸出視為新信源X，求H(X)；（3）若所編的碼為{000，001，010，011，100，101}，求編碼器輸出碼元的一維概率P(x1)與P(x2)。（4）H(X)和H(P(x1),P(x2))之間的大小關(guān)系？（5）用二元符號表，寫出利用霍夫曼編碼后的編碼，并求平均碼長、編碼效率、編碼后的碼元的一維概率P(x1)與P(x2)。

設(shè)DMS為習(xí)題習(xí)題（1）對U進(jìn)行霍夫曼編碼，并求出平均碼長和編碼效率。（2）對U進(jìn)行費諾編碼，并求出平均碼長和編碼效率。（3）對U進(jìn)行香農(nóng)編碼，并求出平均碼長和編碼效率。注：2、設(shè)DMS為用二元符號表對其進(jìn)行定長編碼，若所編的碼為{000，001，010，011，100，101}，（1）求編碼器輸出碼元的一維概率P(x1)與P(x2)。（2）用二元符號表，寫出利用霍夫曼編碼后的編碼，并求編碼后的碼元的一維概率P(x1)與P(x2)、平均碼長。1、設(shè)DMS為習(xí)題用二元符號表對其進(jìn)行定長編碼，若所編的碼為{000，001，010，011，100，101}，（1）對編碼器輸出碼元的一維概率P(x1)與P(x2)。（2）用二元符號表，寫出利用霍夫曼編碼后的編碼，并求編碼后的碼元的一維概率P(x1)與P(x2)、平均碼長。

設(shè)DMS為對U進(jìn)行霍夫曼編碼，并求出平均碼長和編碼效率。注：

設(shè)DMS為習(xí)題對U進(jìn)行霍夫曼編碼，并求出平均碼長和編碼效率。注：

設(shè)DMS為習(xí)題信源編碼由于信源符號之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。

信源編碼的基本途徑有兩個：使序列中的各個符號盡可能地互相獨立，即解除相關(guān)性；使編碼中各個符號出現(xiàn)的概率盡可能地相等，即概率均勻化。信源編碼分類：無失真編碼：只對信源的冗余度進(jìn)行壓縮，不會改變信源的熵，又稱冗余度壓縮編碼，它能保證碼元序列經(jīng)譯碼后能無失真地恢復(fù)成信源符號序列。有失真編碼：會改變信源的熵，不可逆壓縮，又稱熵壓縮編碼。無失真信源編碼的作用：符號變換：使信源的輸出符號與信道的輸入符號相匹配；冗余度壓縮：使編碼之后的新信源概率分布均勻化，信息含量效率等于或接近于100%。單符號信源無失真編碼器模型編碼器f信源f是一一對應(yīng)的映射

bit/碼字或bit/符號

bit/碼元新信源X

：編碼后的信息率R

：平均一個碼元攜帶的信息量。bit/碼元平均碼長越小，每個碼元攜帶的信息量就越多，傳輸一個碼元就傳輸了較多的信息。碼元/符號

編碼效率：編碼后的實際信息率與編碼后的最大信息率之比。

新信源的冗余度也是碼的冗余度：唯一可譯碼（UDC）：該碼的碼字組成的任意有限長碼字序列都能恢復(fù)成唯一的信源序列。否則稱為非唯一可譯碼。碼是唯一可譯碼的充分必要條件是：由碼中的碼字組成的任意有限長的碼字序列（也是碼元序列），都能唯一劃分成一個個的碼字，且任一碼字只與唯一一個信源符號對應(yīng)。奇異碼：含相同碼字的碼。否則稱為非奇異碼。非續(xù)長碼：碼中任一碼字都不是另一碼字的續(xù)長（延長）。否則為續(xù)長碼。非即時碼：如果接收端收到一個完整的碼字后，不能立即譯碼，還需等下一個碼字開始接收后才能判斷是否可以譯碼。否則為即時碼。舉例：下雨天留客天留我不留碼奇異碼非奇異碼非唯一可譯碼唯一可譯碼定長非奇異碼變長非續(xù)長碼（部分）變長續(xù)長碼非分組碼分組碼定長編碼定理DMS編碼器fr進(jìn)制定長編碼，碼長為lN，可用的碼字?jǐn)?shù)目：唯一可譯信息傳輸率編碼效率bit/碼元

定長無失真編碼定理：用r元符號表對離散無記憶信源U的N長符號序列進(jìn)行定長編碼，N長符號序列對應(yīng)的碼長為lN，若對于任意小的正數(shù)，有不等式

就幾乎能做到無失真編碼，且隨著序列長度N的增大，譯碼差錯率趨于0。反過來，若

就不可能做到無失真編碼，且隨著N的增大，譯碼差錯率趨于1。無失真變長編碼定理：用元符號表對離散無記憶信源的長符號串進(jìn)行變長編碼，記長符號串對應(yīng)的平均碼長為，那么，要做到無失真編碼，平均碼長必須滿足

另一方面，一定存在唯一可譯碼，其平均碼長滿足編碼效率：無失真變長編碼定理：用元符號表對離散無記憶信源的長符號串進(jìn)行變長編碼，記長符號串對應(yīng)的平均碼長為，那么，要做到無失真編碼，平均碼長必須滿足

另一方面，一定存在唯一可譯碼，其平均碼長滿足香農(nóng)第一定理編碼效率：變長編碼方法變長編碼采用非續(xù)長碼；力求平均碼長最小，此時編碼效率最高，信源的冗余得到最大程度的壓縮；對給定的信源，使平均碼長達(dá)到最小的編碼方法稱為最佳編碼，編出的碼稱為最佳碼；三種變長編碼方法：霍夫曼編碼、費諾編碼以及香農(nóng)編碼；霍夫曼編碼是真正意義下的最佳編碼?；舴蚵幋a二進(jìn)制霍夫曼編碼過程如下：（1）將信源符號按概率大小排序；（2）對概率最小的兩個符號求其概率之和，同時給兩符號分別賦予碼元“0”和“1”；（3）將“概率之和”當(dāng)作一個新符號的概率，與剩下符號的概率一起，形成一個縮減信源，再重復(fù)上述步驟，直到“概率之和”為1為止；（4）按上述步驟實際上構(gòu)造了一個碼樹，從樹根到端點經(jīng)過的樹技即為碼字?；舴蚵幋a的基本特點：編出的碼是非續(xù)長碼；平均碼長最??；碼字不唯一。r進(jìn)制霍夫曼編碼每次求縮減信源時，求r個最小概率之和，即將個概率最小的r符號縮減為一個新符號，直到概率之和為1終止。新問題：縮減到最后時剩下不到r個符號了。為保證平均碼長最小，希望縮減到最后剛好還剩下r個符號。為達(dá)到此目的，可給信源添加幾個無用的符號（概率為0的符號），使得信源符號數(shù)q滿足:q+i=(r-1)θ+r

信源縮減的次數(shù)增加無用符號的個數(shù)費諾（Fano）編碼費諾（Fano）編碼也是構(gòu)造一個碼樹，因此，編出的碼是非續(xù)長碼，但不一定是最佳碼。費諾編碼步驟(以二進(jìn)制編碼為例)：（1）將信源符號按概率從大到小的排序；（2）將信源符號分成2組，使2組信源符號的概率之和近似相等，并給2組信源符號分別賦碼元“0”和“1”；（3）接下來再把各小組的信源符號細(xì)分為