g第4-5章：連續(xù)信號與連續(xù)信道容量

1、第四章 連續(xù)信源和連續(xù)信道容量n連續(xù)信源連續(xù)信源n連續(xù)信道容量連續(xù)信道容量4.1 連續(xù)信源n連續(xù)信源的統(tǒng)計特性連續(xù)信源的統(tǒng)計特性n連續(xù)信源的熵連續(xù)信源的熵n幾種特殊連續(xù)信源的熵幾種特殊連續(xù)信源的熵TTP已優(yōu)化方便打印1、連續(xù)信源的統(tǒng)計特性、連續(xù)信源的統(tǒng)計特性n連續(xù)信源，指輸出消息在時間和取值上都連續(xù)的信源；連續(xù)信源，指輸出消息在時間和取值上都連續(xù)的信源；n連續(xù)信源輸出的消息是隨機的，與隨機過程相對應(yīng)；連續(xù)信源輸出的消息是隨機的，與隨機過程相對應(yīng)；n連續(xù)信源的統(tǒng)計特性連續(xù)信源的統(tǒng)計特性-概率密度函數(shù)；概率密度函數(shù)；n單變量連續(xù)信源的輸出是取值連續(xù)的隨機變量?？捎米兞繂巫兞窟B續(xù)信源的輸出是取值連續(xù)

2、的隨機變量?？捎米兞康牡母怕拭芏雀怕拭芏?、變量間的、變量間的條件概率密度條件概率密度和和聯(lián)合概率密度聯(lián)合概率密度描述。描述。 一維概率密度函數(shù)一維概率密度函數(shù) 隨機變量隨機變量 X 的的一維概率密度函數(shù)一維概率密度函數(shù)（邊緣概率密度函數(shù)）為：（邊緣概率密度函數(shù)）為： yYxXYXYXdyypyYPyFdxxpxXPxFYXyFxFYXypxpdyydFypdxxdFxp)()()()()()()()()()()()()()(的的一一維維概概率率分分布布函函數(shù)數(shù)、分分別別為為變變量量、的的一一維維概概率率密密度度函函數(shù)數(shù)、分分別別為為變變量量、 條件概率密度和聯(lián)合概率密度函數(shù)條件概率密度和聯(lián)合概

3、率密度函數(shù)n條件概率密度函數(shù)：條件概率密度函數(shù)：n聯(lián)合概率密度函數(shù)：聯(lián)合概率密度函數(shù)：n它們之間的關(guān)系為：它們之間的關(guān)系為：n邊緣概率密度函數(shù)滿足：邊緣概率密度函數(shù)滿足： RXYYRXYXdxxypypdyxypxp)()()()()/()()/()()()()()/(),/(/yxpypxypxpxypyxxyFxypyxpxypYXYXYXXYXYYXXY 2、 連續(xù)信源的熵連續(xù)信源的熵n單變量連續(xù)信源數(shù)學(xué)模型：單變量連續(xù)信源數(shù)學(xué)模型：nR 是連續(xù)變量是連續(xù)變量 X 的取值范圍。的取值范圍。n先將連續(xù)信源在先將連續(xù)信源在時間上離散化時間上離散化，再對連續(xù)變量進行，再對連續(xù)變量進行量化量化分

4、層分層，并用離散變量來逼近連續(xù)變量。量化間隔越小，并用離散變量來逼近連續(xù)變量。量化間隔越小，離散變量與連續(xù)變量越接近，離散變量與連續(xù)變量越接近，當(dāng)量化間隔趨近于零時，當(dāng)量化間隔趨近于零時，離散變量就等于連續(xù)變量。離散變量就等于連續(xù)變量。 RdxxpxpRX1)()(:并并滿滿足足：n設(shè)設(shè) p(x) 如圖所示。把連續(xù)隨機變量如圖所示。把連續(xù)隨機變量 X 的取值分割成的取值分割成 n 個小個小區(qū)間，各小區(qū)間等寬，即：區(qū)間，各小區(qū)間等寬，即：=(ba)/n。則變量落在第。則變量落在第 i 個個小區(qū)間的概率為：小區(qū)間的概率為：n其中其中 xi 是是 a+(i1) 到到 a+i 之間的某一值。當(dāng)之間的某

5、一值。當(dāng) p(x) 是是 X 的連續(xù)函數(shù)時，由中值定理可知，必存在一個的連續(xù)函數(shù)時，由中值定理可知，必存在一個 xi 值使上式成值使上式成立。立。 iaiaixpdxxpiaXiaP) 1()()() 1(n這樣連續(xù)變量這樣連續(xù)變量 x 就可用取值為就可用取值為 xi(i=1,2,n) 的離散的離散變量近似。連續(xù)信源被量化成離散信源。變量近似。連續(xù)信源被量化成離散信源。)(loglim)(log)()()(loglim)(log)()()(loglim)(log)(lim)(lim2022021201200 nbabanbaniinniiinndxxpxpdxxpdxxpxpxpxpxpXH連

6、連續(xù)續(xù)信信源源的的熵熵為為：時時，若若極極限限存存在在，即即得得當(dāng)當(dāng)0,log)()(log)()(log)()(121212 nxpxpxpxpxpXHniiniiiniiin上式右端的第一項一般是定值，而第二項在上式右端的第一項一般是定值，而第二項在 0 時是時是一無限大量。丟掉后一項，定義連續(xù)信源的熵為：一無限大量。丟掉后一項，定義連續(xù)信源的熵為：n上式定義的熵在形式上和離散信源相似，也滿足離散熵上式定義的熵在形式上和離散信源相似，也滿足離散熵的主要特性，如可加性，但在概念上與離散熵有差異因的主要特性，如可加性，但在概念上與離散熵有差異因為它失去了離散熵的部分含義和性質(zhì)。為它失去了離散熵

7、的部分含義和性質(zhì)。RcdxxpxpXH)(log)()(2)(loglim)(log)()(lim2020 nbandxxpxpXH連續(xù)信源的聯(lián)合熵和條件熵連續(xù)信源的聯(lián)合熵和條件熵n兩個連續(xù)變量的聯(lián)合熵：兩個連續(xù)變量的聯(lián)合熵：n兩個連續(xù)變量的條件熵：兩個連續(xù)變量的條件熵：dxdyxypxypXYHRc)(log)()(22dxdyyxpxypYXHdxdyxypxypXYHRcRc)/(log)()/()/(log)()/(22223、 幾種特殊連續(xù)信源的熵(1) 均勻分布的連續(xù)信源的熵均勻分布的連續(xù)信源的熵n一維連續(xù)隨機變量一維連續(xù)隨機變量 X 在在 a,b 區(qū)間內(nèi)均勻分布時的熵為區(qū)間內(nèi)均勻

8、分布時的熵為: Hc(X)=log2(ba)n若若 N 維矢量維矢量 X X=(X1X2XN) 中各分量彼此統(tǒng)計獨立，中各分量彼此統(tǒng)計獨立，且分別在且分別在 a1,b1a2,b2 aN,bN 的區(qū)域內(nèi)均勻分布，的區(qū)域內(nèi)均勻分布，即：即：axbxbxaabxp,01)()()()()(log)(log)(1log)(1)(log)()()(211212112112211111NccciiNiNiiibabaNNiiiNiiibabaNNccXHXHXHababdxdxababdxdxxpxpXXXHXHNNNN NiiiNiiiNiiiabxabxabxp111)(0)()(1)(2) 高斯分布

9、的連續(xù)信源的熵高斯分布的連續(xù)信源的熵n一維隨機變量一維隨機變量 X 的取值范圍是整個實數(shù)軸的取值范圍是整個實數(shù)軸 R，概率密概率密度函數(shù)呈正態(tài)分布，即：度函數(shù)呈正態(tài)分布，即：分分布布的的連連續(xù)續(xù)信信源源。所所代代表表的的信信源源稱稱為為高高斯斯由由這這樣樣隨隨機機變變量量 X dxxxpXEmXm)(的的均均值值：是是 dxxpmxmXEX)()()(2222 的的方方差差：是是 dxxpxPm)(022率率：就就是是隨隨機機變變量量的的平平均均功功時時，當(dāng)當(dāng) 222)(221)(mxexp-4-3-2-10123400.51-4-3-2-10123400.51-4-3-2-10123400.

10、51nx=-4:0.3:4;nm1=1;n1=0.5;nm2=2;n2=0.5;nm3=1;n3=0.3;nz1=(1/sqrt(2*pi*n1)*exp(-1/2)*(x-m1).2/n12);nz2=(1/sqrt(2*pi*n2)*exp(-1/2)*(x-m2).2/n22);nz3=(1/sqrt(2*pi*n3)*exp(-1/2)*(x-m3).2/n32);nsubplot(3,1,1);n plot(x,z1)n subplot(3,1,2);n plot(x,z2)n subplot(3,1,3);n plot(x,z3)22222222log21log212log)()(

11、)(, 1)( eeXHdxxpmxdxxpc 所所以以：因因為為： dxexpdxxpdxexpdxxpxpXHmxcmx22222)(22)(2222122)(log()2log)(log)()(log)()( 說明說明n 高斯連續(xù)信源的熵與數(shù)學(xué)期望高斯連續(xù)信源的熵與數(shù)學(xué)期望 m 無關(guān)，只與方差無關(guān)，只與方差2 有有關(guān)；關(guān)；n 熵描述的是信源的整體特性，由圖熵描述的是信源的整體特性，由圖2.3.2看出，當(dāng)均值看出，當(dāng)均值 m 變化時，只是變化時，只是 p(x) 的對稱中心在橫軸上發(fā)生平移，曲的對稱中心在橫軸上發(fā)生平移，曲線的形狀沒有任何變化，即數(shù)學(xué)期望線的形狀沒有任何變化，即數(shù)學(xué)期望 m

12、對高斯信源的總對高斯信源的總體特性沒有任何影響；體特性沒有任何影響；n 若方差若方差2 不同，曲線的形狀隨之改變，不同，曲線的形狀隨之改變，所以高斯連續(xù)信所以高斯連續(xù)信源的熵與方差有關(guān)而與數(shù)學(xué)期望無關(guān)源的熵與方差有關(guān)而與數(shù)學(xué)期望無關(guān)。這是信源熵的總體。這是信源熵的總體特性的再度體現(xiàn)。特性的再度體現(xiàn)。222log21)( eXHc n連續(xù)信道的數(shù)學(xué)模型連續(xù)信道的數(shù)學(xué)模型n連續(xù)信道容量連續(xù)信道容量-香農(nóng)公式香農(nóng)公式n舉例舉例4.2 連續(xù)信道容量連續(xù)信道：輸入輸出隨機變量都取值于連續(xù)集合的信道連續(xù)信道：輸入輸出隨機變量都取值于連續(xù)集合的信道一、單維連續(xù)通信系統(tǒng)數(shù)學(xué)模型：一、單維連續(xù)通信系統(tǒng)數(shù)學(xué)模型：

13、XYp(Y/X)1)(badxxpYxypX)/(數(shù)學(xué)描述：兩類情況兩類情況 高斯加性信道高斯加性信道非高斯加性信道非高斯加性信道加性信道的重要性質(zhì)：加性信道的重要性質(zhì)： 信道的傳遞概率密度函數(shù)就等于噪聲的概率密度函數(shù)信道的傳遞概率密度函數(shù)就等于噪聲的概率密度函數(shù))()/(npxyp加加性信道性信道條件熵是由噪聲引起的，所以稱為噪聲熵條件熵是由噪聲引起的，所以稱為噪聲熵 NHXYH)/( NHYHXYHYHYXICxpxpxpmax/max;max由于加性噪聲由于加性噪聲N和信源和信源X相互統(tǒng)計獨立，相互統(tǒng)計獨立，X的概率密度函數(shù)的概率密度函數(shù)p(x)的變動不會引起噪聲熵的變動不會引起噪聲熵H

14、(N)的改變，因此加性信道的容的改變，因此加性信道的容量量C就是選擇就是選擇p(x)，使輸出熵，使輸出熵H(Y)達(dá)到最大。達(dá)到最大。n 連續(xù)信道容量連續(xù)信道容量可以證明可以證明式中式中 S 信號平均功率信號平均功率 （W）；）； N 噪聲功率（噪聲功率（W）；）； B 帶寬（帶寬（Hz）。）。 設(shè)噪聲單邊功率譜密度為設(shè)噪聲單邊功率譜密度為n0，則，則N = n0B；故上式可以改寫成：故上式可以改寫成：由上式可見，由上式可見，連續(xù)信道的容量連續(xù)信道的容量Ct和信道帶寬和信道帶寬B、信號功、信號功率率S及噪聲功率譜密度及噪聲功率譜密度n0三個因素有關(guān)三個因素有關(guān)。 )/(1log2sbNSBCt)

15、/(1log02sbBnSBCt當(dāng)當(dāng)S ，或，或n0 0時，時，Ct 。但是，當(dāng)?shù)牵?dāng)B 時，時，Ct將趨向何值？將趨向何值？令：令：x = S / n0B，上式可以改寫為：，上式可以改寫為：利用關(guān)系式利用關(guān)系式上式變?yōu)樯鲜阶優(yōu)?/(1log02sbBnSBCtxtxnSBnSSBnnSC/12002001log1log1)1ln(lim/10 xxxaealnloglog22020/120044. 1log)1 (loglimlimnSenSxnSCxxtB 上式表明，當(dāng)給定上式表明，當(dāng)給定S / n0時，若帶寬時，若帶寬B趨于無窮大，趨于無窮大，信道容量不會趨于無限大，而只是信道容量不會

16、趨于無限大，而只是S / n0的的1.44倍倍。這。這是因為當(dāng)帶寬是因為當(dāng)帶寬B增大時，噪聲功率也隨之增大。增大時，噪聲功率也隨之增大。 Ct和帶寬和帶寬B的關(guān)系曲線：的關(guān)系曲線：020/120044. 1log)1 (loglimlimnSenSxnSCxxtB圖圖4-24 信道容量和帶寬關(guān)系信道容量和帶寬關(guān)系S/n0S/n0BCt1.44(S/n0)上式還可以改寫成如下形式：上式還可以改寫成如下形式：式中式中Eb 每比特能量；每比特能量；Tb = 1/B 每比特持續(xù)時間。每比特持續(xù)時間。 上式表明，為了得到給定的信道容量上式表明，為了得到給定的信道容量Ct，可以，可以增大增大帶寬帶寬B以換

17、取以換取Eb的減小的減??；另一方面，在接收功率受限的；另一方面，在接收功率受限的情況下，由于情況下，由于Eb = STb，可以，可以增大增大Tb以減小以減小S來保持來保持Eb和和Ct不變不變。 0202021log/1log1lognEBBnTEBBnSBCbbbt)/(1log02sbBnSBCt香農(nóng)公式的主要結(jié)論：香農(nóng)公式的主要結(jié)論： （1 1）信道容量）信道容量C C隨隨S/NS/N增大而增大；增大而增大； （2 2）N N0, C0, C，無擾信道的容量為無窮大；無擾信道的容量為無窮大； （3 3） ，n n0 0為噪聲功率譜密度；為噪聲功率譜密度；02044. 1loglimnSen

18、SCW【例例】已知黑白電視圖像信號每幀有已知黑白電視圖像信號每幀有30萬個像素；每個像素有萬個像素；每個像素有8個亮個亮度電平；各電平獨立地以等概率出現(xiàn)；圖像每秒發(fā)送度電平；各電平獨立地以等概率出現(xiàn)；圖像每秒發(fā)送25幀。若要求幀。若要求接收圖像信噪比達(dá)到接收圖像信噪比達(dá)到30dB，試求所需傳輸帶寬。，試求所需傳輸帶寬?！窘饨狻恳驗槊總€像素獨立地以等概率取因為每個像素獨立地以等概率取8個亮度電平，故每個像素的個亮度電平，故每個像素的信息量為信息量為Ip = -log2(1/ 8) = 3 (b/pix)并且每幀圖像的信息量為并且每幀圖像的信息量為IF = 300,000 3 = 900,000

19、(b/F)因為每秒傳輸因為每秒傳輸25幀圖像，所以要求傳輸速率為幀圖像，所以要求傳輸速率為Rb = 900,000 25 = 22,500,000 = 22.5 106 (b/s) 信道的容量信道的容量Ct必須不小于此必須不小于此Rb值。將上述數(shù)值代入式：值。將上述數(shù)值代入式：得到得到22.5 106 = B log2 (1 + 1000) 9.97 B最后得出所需帶寬最后得出所需帶寬B = (22.5 106) / 9.97 2.26 (MHz)NSBCt/1log2n信道的信息傳輸率信道的信息傳輸率R與信源分布密切相關(guān)；與信源分布密切相關(guān)；n當(dāng)信息傳輸率當(dāng)信息傳輸率R=信道容量信道容量C時

20、時-信道與信源匹配信道與信源匹配n當(dāng)信息傳輸率當(dāng)信息傳輸率R信道容量信道容量C時時-信道與信源不匹配，信道信道與信源不匹配，信道有冗余有冗余YXIC;信道剩余度CYXICYXIC;-1;信道相對剩余度通信系統(tǒng)的優(yōu)化模型第五章 信源編碼n信源信源編碼加密信道編碼信源譯碼信道譯碼信道解密信宿密 鑰 源噪聲密 鑰 源ULVLULSmCmXnYnCmSmVLK1K2本章內(nèi)容n離散信源編碼離散信源編碼n連續(xù)信源編碼連續(xù)信源編碼n編碼的基本概念編碼的基本概念n碼的分類碼的分類n香農(nóng)編碼香農(nóng)編碼n費諾編碼費諾編碼n赫夫曼編碼赫夫曼編碼n無失真信源編碼定理無失真信源編碼定理-香農(nóng)第一定理香農(nóng)第一定理5.1 離

21、散信源編碼 a1, a2, , aK 為信源符號集，序列中每一個符號為信源符號集，序列中每一個符號uml都取自信源符都取自信源符號集。號集。 b1 ，b2 ，bD 是適合信道傳輸?shù)氖沁m合信道傳輸?shù)腄個符號，用作信源編碼器的個符號，用作信源編碼器的編碼符號。編碼輸出碼字編碼符號。編碼輸出碼字cm = cm1 cm2 cmn， c mk b1 ，b2 ，bD k = 1, 2 , , n ，n表示碼字長度，簡稱表示碼字長度，簡稱碼長碼長 信源符號信源符號 a1,a2, , aK 信道符號（碼符號）信道符號（碼符號） b1, b2, , bD 信源編碼器信源編碼器 ui = ui1 ui2 uiL

22、碼字碼字ci = ci1 ci2 cin 1、編碼的基本概念信源符號集信源符號集=我我, 是是, 一名一名，學(xué)生，老師，編碼，理論，學(xué)生，老師，編碼，理論, 信道符號集信道符號集=I=I ，am，is, are, a, student, coding, theory, apple, 如果某次該編碼器的輸入是如果某次該編碼器的輸入是“我是一名學(xué)生我是一名學(xué)生”，即輸入序列，即輸入序列ui = (ui1=“我我”，ui2=“是是” ，ui3=“一名一名” ，ui4=“學(xué)生學(xué)生”)，編碼器，編碼器的輸出的輸出“I am a student”，即輸出序列，即輸出序列ci = (ci1=“I”, ci2

23、 =“am”, ci3 =“a”, ci4 =“student”) 信源編碼可看成是從信源符號集到碼符號集的一種映射信源編碼可看成是從信源符號集到碼符號集的一種映射，即將，即將信源符號集中的每個元素（可以是單符號，也可以是符號序列）映信源符號集中的每個元素（可以是單符號，也可以是符號序列）映射成一個長度為射成一個長度為n的碼字。對于同一個信源，編碼方法是多種的。的碼字。對于同一個信源，編碼方法是多種的?！纠纠?.1】 用用 u1 ，u2 ，u3，u4， 表示信源的四個消息，碼符號集為表示信源的四個消息，碼符號集為0,1，表，表1列出了該信源的幾種不同編碼。列出了該信源的幾種不同編碼。表1 同

24、一信源的幾種不同編碼2、編碼的分類信源信源消息消息各消息各消息概率概率碼碼1 1碼碼2 2碼碼3 3碼碼4 4u1q( (u1) )000001u2q( (u2) )1101110u3q( (u3) )101000100u4q( (u4) )1111111000碼碼5 51010010001 3.變長碼變長碼若碼字集合若碼字集合C中的所有碼字中的所有碼字cm (m = 1,2, ,M)，其碼長不都相同，稱其碼長不都相同，稱碼碼C為變長碼，表為變長碼，表1中列出的碼中列出的碼3、碼、碼4 和碼和碼5就是變長碼。就是變長碼。 2.等長碼等長碼在一組碼字集合在一組碼字集合C中的所有碼字中的所有碼字c

25、m (m = 1,2, ,M)，其碼長都相同，其碼長都相同，則稱這組碼則稱這組碼C為等長碼，表為等長碼，表1中列出的碼中列出的碼1、碼、碼2 就碼長就碼長n = 2等長碼等長碼一般，可以將碼簡單的分成如下幾類：一般，可以將碼簡單的分成如下幾類： 1.二元碼二元碼若碼符號集為若碼符號集為0，1，則碼字就是二元序列，稱為二元碼，則碼字就是二元序列，稱為二元碼, ,二元碼二元碼通過二進制信道傳輸，這是數(shù)字通信和計算機通信中最常見的一種通過二進制信道傳輸，這是數(shù)字通信和計算機通信中最常見的一種碼，表碼，表1列出的列出的5種碼都是二元碼。種碼都是二元碼。 5.非奇異碼非奇異碼從信源消息到碼字的影射是一一

26、對應(yīng)的，每一個不同的信源消從信源消息到碼字的影射是一一對應(yīng)的，每一個不同的信源消息都用不同的碼字對其編碼，例表息都用不同的碼字對其編碼，例表1 1中的碼中的碼2、碼、碼3、碼、碼4和碼和碼5都都是非奇異碼。是非奇異碼。 4.奇異碼奇異碼對奇異碼來說，從信源消息到碼對奇異碼來說，從信源消息到碼字的影射不是一一對應(yīng)的。例表字的影射不是一一對應(yīng)的。例表1中中的碼的碼1 1，信源消息，信源消息u2和和u4都用碼字都用碼字11對其編碼，因此這種碼就是奇異碼對其編碼，因此這種碼就是奇異碼，奇異碼不具備惟一可譯性。，奇異碼不具備惟一可譯性。6 6）唯一可譯碼：）唯一可譯碼：若碼的任意一串有限長的碼符號序列只

27、能唯一地被譯成所對應(yīng)若碼的任意一串有限長的碼符號序列只能唯一地被譯成所對應(yīng)的信源符號序列，則此碼稱為唯一可譯碼，否則就稱為非唯一的信源符號序列，則此碼稱為唯一可譯碼，否則就稱為非唯一可譯碼?？勺g碼。111001004321ssss等長碼等長碼非奇異碼非奇異碼0 0 0 1 1 0 1 14321ssss唯一可譯唯一可譯 如果接收端收到一個完整的碼字后，不能立即譯碼，還要如果接收端收到一個完整的碼字后，不能立即譯碼，還要等下一個碼字開始接收后才能判斷是否可以譯碼，這樣的碼叫等下一個碼字開始接收后才能判斷是否可以譯碼，這樣的碼叫做非即時碼。做非即時碼。7 7 非即時碼：非即時碼：100010010

28、14321ssss非奇異碼非奇異碼1 1 0 1 0 0 1 0 0 01 0?2s01不即時不即時任何一個碼字是其它碼字的延長或前綴任何一個碼字是其它碼字的延長或前綴如果收到一個完整的碼字以后，就可以立即譯碼，則叫做即時碼。如果收到一個完整的碼字以后，就可以立即譯碼，則叫做即時碼。即時碼要求任何一個碼字都不是其他碼字的前綴部分，也叫做即時碼要求任何一個碼字都不是其他碼字的前綴部分，也叫做異異前綴碼。前綴碼。8 8、即時碼、即時碼00010010114321ssss非奇異碼非奇異碼1 0 1 0 0 1 0 0 0 1任何一個碼字不是其它碼字的延長或前綴任何一個碼字不是其它碼字的延長或前綴即

29、時 碼0 12s即時n即時碼的判決準(zhǔn)則即時碼的判決準(zhǔn)則n克拉夫特不等式：克拉夫特不等式：設(shè)信源為設(shè)信源為 ，對其進行，對其進行r元信源編碼，相應(yīng)碼字長度為元信源編碼，相應(yīng)碼字長度為 ，則即時碼存在，則即時碼存在的充要條件是：的充要條件是：nuuuU,21nlll,2111nilirn唯一可譯碼的判決準(zhǔn)則唯一可譯碼的判決準(zhǔn)則n麥克米倫不等式：麥克米倫不等式：設(shè)信源為設(shè)信源為 ，對其進行，對其進行r元信源編碼，相應(yīng)碼字長度為元信源編碼，相應(yīng)碼字長度為 ，則唯一可譯碼，則唯一可譯碼存在的充要條件是：存在的充要條件是：nuuuU,21nlll,2111nilirn不同編碼方式的衡量標(biāo)準(zhǔn)不同編碼方式的衡

30、量標(biāo)準(zhǔn)n平均碼長：平均碼長：對離散無記憶信源進行信源編碼，設(shè)編碼后各個對離散無記憶信源進行信源編碼，設(shè)編碼后各個碼字的碼長分別為碼字的碼長分別為 ，則定義該碼的平均碼長為，則定義該碼的平均碼長為：n如果某種編碼方式的平均碼長小于所有其他編碼方式，則該如果某種編碼方式的平均碼長小于所有其他編碼方式，則該碼稱為緊致碼或最佳碼。碼稱為緊致碼或最佳碼。 niiilupL1nlll,21n編碼信息率編碼信息率(編碼速率編碼速率)：n碼長碼長 表示長為表示長為N的信源序列用多少個的信源序列用多少個r進制碼符號表示，因進制碼符號表示，因此此 表示平均一個信源符號用多少個表示平均一個信源符號用多少個r進制符號

31、表示，再進制符號表示，再乘以乘以 表示將表示將r進制轉(zhuǎn)換成二進制進制轉(zhuǎn)換成二進制signbitrNlR/logNl /rlogln編碼效率：編碼效率：n含義：理論上平均每個信源符號用多少個二進制符號的個數(shù)含義：理論上平均每個信源符號用多少個二進制符號的個數(shù)除以實際上用的二進制碼符號的個數(shù)，即表示一種編碼的效除以實際上用的二進制碼符號的個數(shù)，即表示一種編碼的效率。率。 RuHn 有時消息太多，不可能或者沒必要給每個消息都分配有時消息太多，不可能或者沒必要給每個消息都分配一個碼字；一個碼字；n 給多少消息分配碼字可以做到幾乎無失真譯碼？給多少消息分配碼字可以做到幾乎無失真譯碼？n 傳送碼字需要一定

32、的信息率，碼字越多，所需的信息傳送碼字需要一定的信息率，碼字越多，所需的信息率越大。編多少碼字的問題可以轉(zhuǎn)化為對信息率大小的率越大。編多少碼字的問題可以轉(zhuǎn)化為對信息率大小的問題；問題；n 信息率越小越好，最小能小到多少才能做到無失真譯信息率越小越好，最小能小到多少才能做到無失真譯碼呢？碼呢？ 這些問題就是信源編碼定理要研究的問題。這些問題就是信源編碼定理要研究的問題。 碼字與信息率的關(guān)系 信源編碼有信源編碼有定長定長和和變長變長兩種方法。兩種方法。n定長編碼：定長編碼：碼字長度碼字長度 K 是固定的，相應(yīng)的編碼是固定的，相應(yīng)的編碼定理稱為定長信源編碼定理，是尋求定理稱為定長信源編碼定理，是尋求

33、最小最小 K 值值的編碼方法。的編碼方法。n變長編碼：變長編碼：K 是變值，相應(yīng)的編碼定理稱為變是變值，相應(yīng)的編碼定理稱為變長編碼定理。這里的長編碼定理。這里的 K 值最小意味著值最小意味著數(shù)學(xué)期望數(shù)學(xué)期望最小最小。信源編碼的方法n定長編碼定理定長編碼定理：一個熵為一個熵為 H(X) 的的離散無記憶信源離散無記憶信源 X1X2XlXN，若對信源長為，若對信源長為 N 的符號序列進行定長編的符號序列進行定長編碼，設(shè)碼字是從碼，設(shè)碼字是從 m 個字母的碼符號集中，選取個字母的碼符號集中，選取 K 個碼元個碼元組成組成Y1Y2YkYK。對于任意。對于任意0，0 ，只要滿足，只要滿足 則當(dāng)則當(dāng) N 足

34、夠大時，必可使譯碼差錯小于足夠大時，必可使譯碼差錯小于，即譯碼錯誤概，即譯碼錯誤概率能為任意小率能為任意小.反之，若：反之，若： 則不可能實現(xiàn)無失真編碼，而當(dāng)則不可能實現(xiàn)無失真編碼，而當(dāng) N 足夠大時，譯碼錯誤足夠大時，譯碼錯誤概率近似等于概率近似等于1.)(log2XHmNK2)(log2XHmNK3、定長編碼定理n定理中的公式改寫成：定理中的公式改寫成：Klog2mNH(X) Klog2m：表示長為：表示長為 K 的碼符號序列能載荷的最大信息量的碼符號序列能載荷的最大信息量NH(X) ：代表長為：代表長為N 的信源序列平均攜帶的信息量的信源序列平均攜帶的信息量 平均符號熵。平均符號熵。 定

35、長編碼定理告訴我們：定長編碼定理告訴我們：只要碼字傳輸?shù)男畔⒘看笥谛旁磾y只要碼字傳輸?shù)男畔⒘看笥谛旁磾y帶的信息量，總可實現(xiàn)幾乎無失真編碼。帶的信息量，總可實現(xiàn)幾乎無失真編碼。 譯碼差錯率：譯碼差錯率：編碼效率：編碼效率： )()(XHXH：mNK2log)(1XH )(log2XHmNKn可以證明： 。整整數(shù)數(shù)譯譯碼碼差差錯錯率率小小于于任任意意正正 niiiiiiiiXHxpxpXHxIEXHXHxIxIEXHxIExID1222222222)()(log)()()()()()(2)()()()(22)(xN 只要2222)1 ()()(XHxNn信源編碼定理從理論上說明了編碼效率接近于信源

36、編碼定理從理論上說明了編碼效率接近于 1，即：，即： 的理想編碼器的存在性，代價是在實際編碼時的理想編碼器的存在性，代價是在實際編碼時 取無限長的信源符號取無限長的信源符號 (N) 進行統(tǒng)一編碼。進行統(tǒng)一編碼。說明：說明：定長編碼定理是在平穩(wěn)無記憶離散信源的條定長編碼定理是在平穩(wěn)無記憶離散信源的條件下論證的，但它同樣適用于平穩(wěn)有記憶信源，只件下論證的，但它同樣適用于平穩(wěn)有記憶信源，只是要求有記憶信源的是要求有記憶信源的極限熵極限熵和和極限方差極限方差存在即可。存在即可。對于平穩(wěn)有記憶信源，定理中的熵應(yīng)改為極限熵。對于平穩(wěn)有記憶信源，定理中的熵應(yīng)改為極限熵。1log)(2mNKXH例例：設(shè)單符號

37、信源模型為：設(shè)單符號信源模型為：n其信息熵為：其信息熵為：H(X)=2.55（比特符號）（比特符號） 2(x)=1.323n若要求編碼效率為若要求編碼效率為 = 90%，即：即：n譯碼差錯率為譯碼差錯率為=106，則，則=0.28，n在差錯率和效率要求都不苛刻的情況下，就必須有在差錯率和效率要求都不苛刻的情況下，就必須有1600多萬個多萬個信源符號一起編碼，技術(shù)實現(xiàn)非常困難。信源符號一起編碼，技術(shù)實現(xiàn)非常困難。 04. 005. 006. 007. 010. 010. 018. 04 . 0)(87654321xxxxxxxxxpX90. 0)()( XHXH722106875. 1)(xN例

38、：離散無記憶信源：n其信息熵為：n自信息的方差為： 41,43,)(21xxxpX（比比特特信信源源符符號號）811. 034log434log41)(22 XH 4715. 0)811. 0(41log4143log43)()(log)()(2222212222 niiiiXHxpxpxID n若對信源若對信源X采取等長二元編碼時，要求采取等長二元編碼時，要求=0.96，=105n信源序列長度需長達(dá)信源序列長度需長達(dá)4130萬萬以上，才能實現(xiàn)給定的要以上，才能實現(xiàn)給定的要求，這在實際中很難實現(xiàn)。求，這在實際中很難實現(xiàn)。n一般來說，當(dāng)一般來說，當(dāng) N 有限時，高傳輸效率的等長碼往往要引有限時，

39、高傳輸效率的等長碼往往要引入一定的失真和錯誤，它不能像變長碼那樣可以實現(xiàn)無入一定的失真和錯誤，它不能像變長碼那樣可以實現(xiàn)無失真編碼。失真編碼。7522222221013.410)04.0()96.0()811.0(4715.0)1()()(XHxN(1) 基本概念基本概念n變長編碼（不等長編碼）：變長編碼（不等長編碼）：不等長編碼允許把等長的消不等長編碼允許把等長的消息變換成不等長的碼序列。通常把經(jīng)常出現(xiàn)的消息編成息變換成不等長的碼序列。通常把經(jīng)常出現(xiàn)的消息編成短碼短碼，不常出現(xiàn)的消息編成，不常出現(xiàn)的消息編成長碼長碼。這樣可使。這樣可使平均碼長平均碼長最最短，從而提高通信效率，代價是增加了編譯

40、碼設(shè)備的復(fù)短，從而提高通信效率，代價是增加了編譯碼設(shè)備的復(fù)雜度。雜度。 例如：在不等長碼字組成的序列中要正確識別每個長例如：在不等長碼字組成的序列中要正確識別每個長度不同的碼字的起點就比等長碼復(fù)雜得多。度不同的碼字的起點就比等長碼復(fù)雜得多。n譯碼延時譯碼同步：譯碼延時譯碼同步：接收到一個不等長碼序列后，有接收到一個不等長碼序列后，有時不能馬上斷定碼字是否真正結(jié)束，因而不能立即譯出時不能馬上斷定碼字是否真正結(jié)束，因而不能立即譯出該碼，要等到后面的符號收到后才能正確譯出。該碼，要等到后面的符號收到后才能正確譯出。(1) 基本概念基本概念(2) 碼樹圖碼樹圖 (3) 變長編碼定理變長編碼定理 4、變

41、長編碼定理例例：碼碼 1：顯然不是惟一可譯碼。顯然不是惟一可譯碼。x2 和和 x4 對應(yīng)于同一碼字對應(yīng)于同一碼字“11”，碼碼 1 是一個奇異碼。是一個奇異碼。碼碼 2：是非奇異碼，不是惟一可譯碼。當(dāng)收到一串碼符是非奇異碼，不是惟一可譯碼。當(dāng)收到一串碼符號號“01000”時，可將它譯成時，可將它譯成“x4 x3 x1”，也可譯為，也可譯為“x4x1x3”， “x1x2x3”或或“x1x2x1x1”等，這種碼從單等，這種碼從單個碼字來看雖然不是奇異的，但從有限長的碼序列來看，個碼字來看雖然不是奇異的，但從有限長的碼序列來看，它仍然是一個奇異碼。它仍然是一個奇異碼。例例：碼碼 3：雖然是惟一可譯碼

42、，但它要等到下一個雖然是惟一可譯碼，但它要等到下一個“1”收到收到后才能確定碼字的結(jié)束，譯碼有延時。后才能確定碼字的結(jié)束，譯碼有延時。碼碼 4：既是惟一可譯碼，又沒有譯碼延時。碼字中的符既是惟一可譯碼，又沒有譯碼延時。碼字中的符號號“1”起了逗點的作用，故稱為起了逗點的作用，故稱為逗點碼逗點碼。即時碼即時碼/前綴條件碼前綴條件碼/異前置碼異前置碼/異字頭碼異字頭碼/逗點碼逗點碼/非延非延長碼長碼：如果一個碼的任何一個碼字都不是其它碼字的前：如果一個碼的任何一個碼字都不是其它碼字的前綴。綴。碼 4 是即時碼 (2) 碼樹圖碼樹圖 m 元（元（m 進制）碼樹圖進制）碼樹圖n樹根：樹根：最頂部畫一個

43、起始點。最頂部畫一個起始點。n樹枝：樹枝：從根部引出從根部引出 m 條線段，每條線段都稱為樹枝。條線段，每條線段都稱為樹枝。n一級節(jié)點：一級節(jié)點：自根部起自根部起,通過一條樹枝到達(dá)的節(jié)點。一級通過一條樹枝到達(dá)的節(jié)點。一級節(jié)點最多有節(jié)點最多有 m 個個.nn 級節(jié)點：級節(jié)點：通過通過 n 條樹枝達(dá)到的節(jié)點。最多有條樹枝達(dá)到的節(jié)點。最多有 mn。n終節(jié)點終節(jié)點/終端節(jié)點：終端節(jié)點：下面不再有樹枝的節(jié)點。下面不再有樹枝的節(jié)點。n中間節(jié)點：中間節(jié)點：除了樹根和終節(jié)點以外的節(jié)點。除了樹根和終節(jié)點以外的節(jié)點。n聯(lián)枝：聯(lián)枝：串聯(lián)的樹枝。串聯(lián)的樹枝。n滿樹：滿樹：在碼樹圖中，在碼樹圖中，當(dāng)每一個碼字的串聯(lián)枝數(shù)

44、都相同時，當(dāng)每一個碼字的串聯(lián)枝數(shù)都相同時，就是定長碼。此時的碼樹稱為滿樹。就是定長碼。此時的碼樹稱為滿樹。 例如：碼長為例如：碼長為 N 的滿樹的終節(jié)點個數(shù)為的滿樹的終節(jié)點個數(shù)為 mN，即可表示，即可表示 mN 個碼字。個碼字。n非滿樹：非滿樹：有些樹枝未用時的碼樹。有些樹枝未用時的碼樹。 非滿樹構(gòu)造的就是變長碼非滿樹構(gòu)造的就是變長碼。 如果每一個碼字都被安排在終節(jié)點上如果每一個碼字都被安排在終節(jié)點上,這種碼就是即時碼。這種碼就是即時碼。(3) 變長編碼定理變長編碼定理 變長編碼定理（香農(nóng)第一定理）變長編碼定理（香農(nóng)第一定理）n平均碼長：平均碼長：n變長編碼定理：變長編碼定理：若一若一離散無記

45、憶信源離散無記憶信源的平均符號熵為的平均符號熵為 H(X)，對信源符號進行，對信源符號進行 m 元變長編碼，一定存在一種元變長編碼，一定存在一種無失真編碼方法，其碼字平均長度無失真編碼方法，其碼字平均長度 滿足下列不等滿足下列不等式：式： 其平均信息率滿足不等式其平均信息率滿足不等式 H(X) + RH(X)，式，式中中為任意正數(shù)。為任意正數(shù)。mXHKmXH22log)(log)(1 niiikxpK1)(n多符號情況多符號情況n 對于平穩(wěn)無記憶信源來說，當(dāng)信源輸出的是長度為對于平穩(wěn)無記憶信源來說，當(dāng)信源輸出的是長度為 N 的消息序列時，容易證明定理中式子可改進為：的消息序列時，容易證明定理中

46、式子可改進為：n 這時的這時的 代表代表平均碼序列長度。平均碼序列長度。mXNHKmXNH22log)(log)(1K 證明：證明： 多符號情況多符號情況n 已知編碼后已知編碼后平均每個信源符號能載荷的最大信息量平均每個信源符號能載荷的最大信息量為（不等長信源編碼信源平均輸出為（不等長信源編碼信源平均輸出信息率信息率）：）：，mNKR2logNmN2log足夠大時，可使當(dāng))(log)(2XHRNmXH故有：n對信源進行變長編碼一般所要求的信源符號長度對信源進行變長編碼一般所要求的信源符號長度N 比定比定長編碼小的多。長編碼小的多。：，得得到到編編碼碼效效率率的的下下界界由由： )()(XHRX

47、HNmXHXHRXH2log)()()( 變長編碼定理（香農(nóng)第一定理）n信道的信息傳輸率為（從信道的角度看）：n編碼效率定義為：n二元無損無噪信道中 m=2，所以 Hm(X)=H(X) 碼碼符符號號比比特特信信源源符符號號碼碼符符號號信信源源符符號號比比特特/)(/)(KHKHRX XX X KmHKHm2log)()(X XX X ：平平均均碼碼長長KRKH )(X X 例例：設(shè)單符號信源模型為：設(shè)單符號信源模型為：其信息熵為：其信息熵為：H(X)=2.55（比特（比特/符號）符號）這里這里 m=2，log2m=1要求要求90%，則：，則： 04. 005. 006. 007. 010. 0

48、10. 018. 04 . 0)(87654321xxxxxxxxXPX428. 019 . 0155. 255. 2NN例例：與定長編碼相比，對同一信源，要求編碼效率都達(dá)到與定長編碼相比，對同一信源，要求編碼效率都達(dá)到 90% 時，變長編碼只需時，變長編碼只需 N=4 進行編碼，而等長碼則進行編碼，而等長碼則要求要求 N 大于大于 1.6875107。用變長編碼時。用變長編碼時, N 不需要不需要很大就可以達(dá)到相當(dāng)高的編碼效率而且可實現(xiàn)無失真編很大就可以達(dá)到相當(dāng)高的編碼效率而且可實現(xiàn)無失真編碼。碼。例例：離散無記憶信源：離散無記憶信源：n其信息熵為：其信息熵為：n用二元碼符號用二元碼符號(0

49、,1)來構(gòu)造一個即時碼：來構(gòu)造一個即時碼：x10，x21n這時平均碼長：這時平均碼長：n編碼效率為：編碼效率為：n信道信息傳輸率為：信道信息傳輸率為：R=0.811 比特比特/二元碼符號二元碼符號 41,43,)(21xxxpX信信源源符符號號）（比比特特/811. 034log434log41)(22 XH信信源源符符號號）（二二元元碼碼符符號號/1 K811. 0)( KXH 例例：n為了提高傳輸效率，對無記憶信源為了提高傳輸效率，對無記憶信源 X 的二次擴展信源的二次擴展信源 X2 進行編碼，下面給出擴展信源進行編碼，下面給出擴展信源 X2 及其某一個即時碼：及其某一個即時碼：信信源源符

50、符號號）（二二元元碼碼符符號號/322722 KK二二個個信信源源符符號號）（二二元元碼碼符符號號 /162731613163216311692 K 這個碼的平均長度為：這個碼的平均長度為： 信源符號信源符號X中每一單個符號的平均碼長為：中每一單個符號的平均碼長為：例例：n其編碼效率為：其編碼效率為：n信息傳輸速率為：信息傳輸速率為：n編碼復(fù)雜了一些，但信息傳輸率有了提高。編碼復(fù)雜了一些，但信息傳輸率有了提高。n對信源對信源X的三次和四次擴展信源進行編碼，編碼效率為：的三次和四次擴展信源進行編碼，編碼效率為：n信息傳輸率為：信息傳輸率為：二二元元碼碼符符號號）（比比特特/96102.R 961

51、0278110322. 二二元元碼碼符符號號）（比比特特二二元元碼碼符符號號）（比比特特/9910/985043.R.R 9910985043. 例例：n 與定長碼比較：對于同一信源，要求編碼效率都達(dá)到與定長碼比較：對于同一信源，要求編碼效率都達(dá)到96%時，變長碼只需對二次擴展信源（時，變長碼只需對二次擴展信源（N=2）進行編碼，）進行編碼，而等長碼則要求而等長碼則要求N4.13107。n 結(jié)論結(jié)論n 用變長碼編碼時，用變長碼編碼時，L不需要很大就可以達(dá)到相當(dāng)高的不需要很大就可以達(dá)到相當(dāng)高的編碼效率，而且可以實現(xiàn)無失真編碼。編碼效率，而且可以實現(xiàn)無失真編碼。n 隨著擴展信源次數(shù)的增加，編碼的效

52、率越來越接近于隨著擴展信源次數(shù)的增加，編碼的效率越來越接近于1比特比特/二元碼符號，達(dá)到信源與信道匹配，使信道得二元碼符號，達(dá)到信源與信道匹配，使信道得到充分利用。到充分利用。n 二進制香農(nóng)碼的編碼步驟如下：二進制香農(nóng)碼的編碼步驟如下：n將信源符號按概率從大到小的順序排列，為方便起見，令：將信源符號按概率從大到小的順序排列，為方便起見，令： p(x1) p(x2) p(xn)n 令令 p(x0)=0，用，用 pa(xj)，j=i+1 表示第表示第 i 個碼字的個碼字的累加概累加概率率，則：，則：n確定滿足下列不等式的整數(shù)確定滿足下列不等式的整數(shù) ki ，并令，并令 ki 為第為第 i 個碼字的

53、長個碼字的長度度log2 p(xi) ki 1 log2 p(xi)n 將將 pa(xj) 用二進制表示，并取小數(shù)點后用二進制表示，并取小數(shù)點后 ki 位作為符號位作為符號 xi 的的編碼。編碼。njxpxpjiija, 2 , 1, )()(10 niininixpxpxpxpxpxxxxXPX121211)(,)(,),(,),(),(,)(設(shè)離散無記憶信源：設(shè)離散無記憶信源：5、香農(nóng)編碼例例6.1.1 ：有一單符號離散無記憶信源：有一單符號離散無記憶信源：n對該信源編二進制香農(nóng)碼。對該信源編二進制香農(nóng)碼。 05. 010. 015. 020. 025. 025. 0,)(654321xx

54、xxxxXPXn計算出給定信源香農(nóng)碼的平均碼長：計算出給定信源香農(nóng)碼的平均碼長：n若對上述信源采用等長編碼，要做到無失真譯碼，每個符若對上述信源采用等長編碼，要做到無失真譯碼，每個符號至少要用號至少要用 3 個比特表示。相比較，香農(nóng)編碼對信源進個比特表示。相比較，香農(nóng)編碼對信源進行了壓縮。行了壓縮。)/(7 .2505.0410.03)15.02 .0(2225.0符符號號比比特特 Kn由離散無記憶信源熵定義，可計算出信源上熵為：由離散無記憶信源熵定義，可計算出信源上熵為：n對上述信源采用香農(nóng)編碼的信息率為：對上述信源采用香農(nóng)編碼的信息率為：n編碼效率為信源熵和信息率之比。則：編碼效率為信源熵

55、和信息率之比。則：可以看出，編碼效率并不是很高?？梢钥闯觯幋a效率并不是很高。)/(42. 2)(log)()(612符符號號比比特特 iiixpxpXH2, 17 . 22log17 . 2log22 mLmLKR這這里里%63.897 . 242. 2)( RXH n將概率按從大到小的順序排列，令：將概率按從大到小的順序排列，令：p(x1) p(x2) p(xn)n按編碼進制數(shù)將概率分組，使每組概率盡可能接近或相按編碼進制數(shù)將概率分組，使每組概率盡可能接近或相等。如等。如編二進制碼就分成兩組，編二進制碼就分成兩組，編編 m 進制碼就分成進制碼就分成 m 組。組。n給每一組分配一位碼元。給每

56、一組分配一位碼元。n將每一分組再按同樣原則劃分，重復(fù)步驟將每一分組再按同樣原則劃分，重復(fù)步驟 2 和和 3，直，直至概率不再可分為止。至概率不再可分為止。6、費諾編碼例例6.3.1：設(shè)有一單符號離散信源：設(shè)有一單符號離散信源n對該信源編二進制費諾碼。對該信源編二進制費諾碼。05. 010. 015. 020. 025. 025. 0,)(654321xxxxxxXPX表表二進制費諾編碼二進制費諾編碼 信源符號信源符號 概率概率 編碼編碼 碼字碼字 碼長碼長 x1 0.25 0 00 2 x2 0.25 0 1 01 2 x3 0.20 0 10 2 x4 0.15 0 110 3 x5 0.1

57、0 0 1110 4 x6 0.05 1 1 1 1 1111 4 n該信源的熵為：該信源的熵為：n平均碼長為：平均碼長為：n對上述信源采用費諾編碼的信息率為：對上述信源采用費諾編碼的信息率為：n編碼效率為：編碼效率為：n本例中費諾編碼有較高的編碼效率。費諾碼比較適合于本例中費諾編碼有較高的編碼效率。費諾碼比較適合于每次分組概率都很接近每次分組概率都很接近的信源。特別是對每次的信源。特別是對每次分組概率分組概率都相等都相等的信源進行編碼時，可達(dá)到理想的編碼效率。的信源進行編碼時，可達(dá)到理想的編碼效率。)/(42325. 2)(log)()(612符號比特iiixpxpXH)/( 54 . 2)

58、(61符號比特iiikxpK2, 145. 22log145. 2log22mLmLKR這里%91.9845. 242325. 2)(RXH例例6.3.2：有一單符號離散無記憶信源：有一單符號離散無記憶信源n對該信源編二進制費諾碼，編碼過程如下表。對該信源編二進制費諾碼，編碼過程如下表。 16/116/116/116/18/18/14/14/1,)(87654321xxxxxxxxXPXn信源熵為：信源熵為：H(X)=2.75(比特比特/符號符號)n平均碼長為：平均碼長為：n編碼效率為編碼效率為=1。之所以如此，因為每次所分兩組的。之所以如此，因為每次所分兩組的概率恰好相等。概率恰好相等。（比

59、比特特符符號號）75. 2440625. 03212. 02)25. 025. 0( K 哈夫曼哈夫曼( (HuffmanHuffman) ) 編碼是一種效率比較高的變長無失編碼是一種效率比較高的變長無失真信源編碼方法。真信源編碼方法。7、哈弗曼編碼編碼步驟(1) 將信源符號按概率從大到小的順序排列，令：將信源符號按概率從大到小的順序排列，令：p(x1) p(x2) p(xn)(2) 信源的第一次縮減信源：信源的第一次縮減信源：給兩個概率最小的信源符號給兩個概率最小的信源符號 p(xn1) 和和 p(xn) 各分配一個碼位各分配一個碼位“0”和和“1”，將這，將這兩個信源符號合并成一個新符號，

60、并用這兩個最小的概兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結(jié)果得到一個只包含率之和作為新符號的概率，結(jié)果得到一個只包含 (n1) 個信源符號的新信源，用個信源符號的新信源，用 S1 表示。表示。(3) 將縮減信源將縮減信源 S1 的符號仍按概率從大到小順序排列，的符號仍按概率從大到小順序排列，重復(fù)步驟重復(fù)步驟 (2)，得到只含，得到只含 (n2) 個符號的縮減信源個符號的縮減信源 S2。(4) 重復(fù)上述步驟，直至縮減信源只剩兩個符號為止，此重復(fù)上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概率之和必為時所剩兩個符號的概率之和必為 1。然后從最后一級縮