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

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

2、的隨機(jī)變量?？捎米兞康牡母怕拭芏雀怕拭芏?、變量間的、變量間的條件概率密度條件概率密度和和聯(lián)合概率密度聯(lián)合概率密度描述。描述。 一維概率密度函數(shù)一維概率密度函數(shù) 隨機(jī)變量隨機(jī)變量 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é)模型：?jiǎn)巫兞窟B續(xù)信源數(shù)學(xué)模型：nR 是連續(xù)變量是連續(xù)變量 X 的取值范圍。的取值范圍。n先將連續(xù)信源在先將連續(xù)信源在時(shí)間上離散化時(shí)間上離散化，再對(duì)連續(xù)變量進(jìn)行，再對(duì)連續(xù)變量進(jìn)行量化量化分

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

5、一值。當(dāng) p(x) 是是 X 的連續(xù)函數(shù)時(shí)，由中值定理可知，必存在一個(gè)的連續(xù)函數(shù)時(shí)，由中值定理可知，必存在一個(gè) 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ù)信信源源的的熵熵為為：時(shí)時(shí)，若若極極限限存存在在，即即得得當(dāng)當(dāng)0,log)()(log)()(log)()(121212 nxpxpxpxpxpXHniiniiiniiin上式右端的第一項(xiàng)一般是定值，而第二項(xiàng)在上式右端的第一項(xiàng)一般是定值，而第二項(xiàng)在 0 時(shí)是時(shí)是一無(wú)限大量。丟掉后一項(xiàng)，定義連續(xù)信源的熵為：一無(wú)限大量。丟掉后一項(xiàng)，定義連續(xù)信源的熵為：n上式定義的熵在形式上和離散信源相似，也滿足離散熵上式定義的熵在形式上和離散信源相似，也滿足離散熵的主要特性，如可加性，但在概念上與離散熵有差異因的主要特性，如可加性，但在概念上與離散熵有差異因?yàn)樗チ穗x散熵的部分含義和性質(zhì)。為它失去了離散熵

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

8、分布時(shí)的熵為: Hc(X)=log2(ba)n若若 N 維矢量維矢量 X X=(X1X2XN) 中各分量彼此統(tǒng)計(jì)獨(dú)立，中各分量彼此統(tǒng)計(jì)獨(dú)立，且分別在且分別在 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一維隨機(jī)變量一維隨機(jī)變量 X 的取值范圍是整個(gè)實(shí)數(shù)軸的取值范圍是整個(gè)實(shí)數(shù)軸 R，概率密概率密度函數(shù)呈正態(tài)分布，即：度函數(shù)呈正態(tài)分布，即：分分布布的的連連續(xù)續(xù)信信源源。所所代代表表的的信信源源稱稱為為高高斯斯由由這這樣樣隨隨機(jī)機(jī)變變量量 X dxxxpXEmXm)(的的均均值值：是是 dxxpmxmXEX)()()(2222 的的方方差差：是是 dxxpxPm)(022率率：就就是是隨隨機(jī)機(jī)變變量量的的平平均均功功時(shí)時(shí)，當(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 所所以以：因因?yàn)闉椋?dxexpdxxpdxexpdxxpxpXHmxcmx22222)(22)(2222122)(log()2log)(log)()(log)()( 說(shuō)明說(shuō)明n 高斯連續(xù)信源的熵與數(shù)學(xué)期望高斯連續(xù)信源的熵與數(shù)學(xué)期望 m 無(wú)關(guān)，只與方差無(wú)關(guān)，只與方差2 有有關(guān)；關(guān)；n 熵描述的是信源的整體特性，由圖熵描述的是信源的整體特性，由圖2.3.2看出，當(dāng)均值看出，當(dāng)均值 m 變化時(shí)，只是變化時(shí)，只是 p(x) 的對(duì)稱中心在橫軸上發(fā)生平移，曲的對(duì)稱中心在橫軸上發(fā)生平移，曲線的形狀沒(méi)有任何變化，即數(shù)學(xué)期望線的形狀沒(méi)有任何變化，即數(shù)學(xué)期望 m

12、對(duì)高斯信源的總對(duì)高斯信源的總體特性沒(méi)有任何影響；體特性沒(méi)有任何影響；n 若方差若方差2 不同，曲線的形狀隨之改變，不同，曲線的形狀隨之改變，所以高斯連續(xù)信所以高斯連續(xù)信源的熵與方差有關(guān)而與數(shù)學(xué)期望無(wú)關(guān)源的熵與方差有關(guān)而與數(shù)學(xué)期望無(wú)關(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ù)信道：輸入輸出隨機(jī)變量都取值于連續(xù)集合的信道連續(xù)信道：輸入輸出隨機(jī)變量都取值于連續(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)計(jì)獨(dú)立，相互統(tǒng)計(jì)獨(dú)立，X的概率密度函數(shù)的概率密度函數(shù)p(x)的變動(dòng)不會(huì)引起噪聲熵的變動(dòng)不會(huì)引起噪聲熵H

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

15、/(1log02sbBnSBCt當(dāng)當(dāng)S ，或，或n0 0時(shí)，時(shí)，Ct 。但是，當(dāng)?shù)?，?dāng)B 時(shí)，時(shí)，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時(shí)，若帶寬時(shí)，若帶寬B趨于無(wú)窮大，趨于無(wú)窮大，信道容量不會(huì)趨于無(wú)限大，而只是信道容量不會(huì)

16、趨于無(wú)限大，而只是S / n0的的1.44倍倍。這。這是因?yàn)楫?dāng)帶寬是因?yàn)楫?dāng)帶寬B增大時(shí)，噪聲功率也隨之增大。增大時(shí)，噪聲功率也隨之增大。 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ù)時(shí)間。每比特持續(xù)時(shí)間。 上式表明，為了得到給定的信道容量上式表明，為了得到給定的信道容量Ct，可以，可以增大增大帶寬帶寬B以換

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

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

19、(b/F)因?yàn)槊棵雮鬏斠驗(yàn)槊棵雮鬏?5幀圖像，所以要求傳輸速率為幀圖像，所以要求傳輸速率為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時(shí)

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

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

22、碼字碼字ci = ci1 ci2 cin 1、編碼的基本概念信源符號(hào)集信源符號(hào)集=我我, 是是, 一名一名，學(xué)生，老師，編碼，理論，學(xué)生，老師，編碼，理論, 信道符號(hào)集信道符號(hào)集=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”) 信源編碼可看成是從信源符號(hào)集到碼符號(hào)集的一種映射信源編碼可看成是從信源符號(hào)集到碼符號(hào)集的一種映射，即將，即將信源符號(hào)集中的每個(gè)元素（可以是單符號(hào)，也可以是符號(hào)序列）映信源符號(hào)集中的每個(gè)元素（可以是單符號(hào)，也可以是符號(hào)序列）映射成一個(gè)長(zhǎng)度為射成一個(gè)長(zhǎng)度為n的碼字。對(duì)于同一個(gè)信源，編碼方法是多種的。的碼字。對(duì)于同一個(gè)信源，編碼方法是多種的?！纠纠?.1】 用用 u1 ，u2 ，u3，u4， 表示信源的四個(gè)消息，碼符號(hào)集為表示信源的四個(gè)消息，碼符號(hào)集為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.變長(zhǎng)碼變長(zhǎng)碼若碼字集合若碼字集合C中的所有碼字中的所有碼字cm (m = 1,2, ,M)，其碼長(zhǎng)不都相同，稱其碼長(zhǎng)不都相同，稱碼碼C為變長(zhǎng)碼，表為變長(zhǎng)碼，表1中列出的碼中列出的碼3、碼、碼4 和碼和碼5就是變長(zhǎng)碼。就是變長(zhǎng)碼。 2.等長(zhǎng)碼等長(zhǎng)碼在一組碼字集合在一組碼字集合C中的所有碼字中的所有碼字c

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

56、一組分配一位碼元。n將每一分組再按同樣原則劃分，重復(fù)步驟將每一分組再按同樣原則劃分，重復(fù)步驟 2 和和 3，直，直至概率不再可分為止。至概率不再可分為止。6、費(fèi)諾編碼例例6.3.1：設(shè)有一單符號(hào)離散信源：設(shè)有一單符號(hào)離散信源n對(duì)該信源編二進(jìn)制費(fèi)諾碼。對(duì)該信源編二進(jìn)制費(fèi)諾碼。05. 010. 015. 020. 025. 025. 0,)(654321xxxxxxXPX表表二進(jìn)制費(fèi)諾編碼二進(jìn)制費(fèi)諾編碼 信源符號(hào)信源符號(hào) 概率概率 編碼編碼 碼字碼字 碼長(zhǎng)碼長(zhǎng) 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平均碼長(zhǎng)為：平均碼長(zhǎng)為：n對(duì)上述信源采用費(fèi)諾編碼的信息率為：對(duì)上述信源采用費(fèi)諾編碼的信息率為：n編碼效率為：編碼效率為：n本例中費(fèi)諾編碼有較高的編碼效率。費(fèi)諾碼比較適合于本例中費(fèi)諾編碼有較高的編碼效率。費(fèi)諾碼比較適合于每次分組概率都很接近每次分組概率都很接近的信源。特別是對(duì)每次的信源。特別是對(duì)每次分組概率分組概率都相等都相等的信源進(jìn)行編碼時(shí)，可達(dá)到理想的編碼效率。的信源進(jìn)行編碼時(shí)，可達(dá)到理想的編碼效率。)/(42325. 2)(log)()(612符號(hào)比特iiixpxpXH)/( 54 . 2)

58、(61符號(hào)比特iiikxpK2, 145. 22log145. 2log22mLmLKR這里%91.9845. 242325. 2)(RXH例例6.3.2：有一單符號(hào)離散無(wú)記憶信源：有一單符號(hào)離散無(wú)記憶信源n對(duì)該信源編二進(jìn)制費(fèi)諾碼，編碼過(guò)程如下表。對(duì)該信源編二進(jìn)制費(fèi)諾碼，編碼過(guò)程如下表。 16/116/116/116/18/18/14/14/1,)(87654321xxxxxxxxXPXn信源熵為：信源熵為：H(X)=2.75(比特比特/符號(hào)符號(hào))n平均碼長(zhǎng)為：平均碼長(zhǎng)為：n編碼效率為編碼效率為=1。之所以如此，因?yàn)槊看嗡謨山M的。之所以如此，因?yàn)槊看嗡謨山M的概率恰好相等。概率恰好相等。（比

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

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