信息論第5章 信源編碼

第5章信源編碼教學(xué)內(nèi)容和要求理解無失真信源編碼定理，理解異前置碼掌握香農(nóng)碼掌握費(fèi)諾碼掌握赫夫曼碼6/23/2024一、無失真信源編碼定理與異前置碼1、無失真信源編碼定理定理N次擴(kuò)展信源的熵率為H(X)，對擴(kuò)展信源進(jìn)行二進(jìn)制編碼，設(shè)K為碼長，對任意給定的ε

>0，只要碼率N足夠大時(shí)，該編碼為無失真編碼6/23/2024如果碼率無論N多大，該編碼也一定失真無失真信源編碼定理也叫香農(nóng)第一定理，定理表明了擴(kuò)展信源無失真編碼的存在性，明確了熵率H(X)是無失真編碼的碼率下界——香農(nóng)界6/23/20242、編碼效率定義擴(kuò)展信源無失真編碼的編碼效率從提高傳輸效率的角度，碼率越接近熵率越好6/23/2024無失真信源編碼及編碼效率信源的熵率例16/23/2024無失真編碼1——等長碼碼長K=2(bit)6/23/2024二次擴(kuò)展信源6/23/2024碼長K=4(bit)6/23/2024等長碼的碼率為整數(shù)，熵率為小數(shù)情況下編碼效率不可能提高不等長碼的平均碼長和碼率才可能為小數(shù)無失真編碼2——一種不等長編碼6/23/2024二次擴(kuò)展信源6/23/20246/23/2024無失真信源不等長編碼的結(jié)論與問題大概率符號序列編為短碼、小概率符號序列編為長碼有助于壓縮平均碼長N次擴(kuò)展有助于壓縮平均碼長，隨N的增大，可以預(yù)見碼率可能漸進(jìn)達(dá)到熵率出現(xiàn)無失真譯碼問題——碼長不等，接收端如何從碼串中唯一分割出對應(yīng)于每個(gè)符號序列的碼字6/23/20243、異前置碼單義可譯碼——接收端能從不等長碼串中唯一分割出對應(yīng)于每個(gè)符號序列的碼字①即時(shí)碼——能在對應(yīng)于每個(gè)符號序列的碼字結(jié)束時(shí)譯出②延時(shí)碼——等到對應(yīng)于下個(gè)符號序列的碼字出現(xiàn)時(shí)才能譯出定義6/23/2024碼A不是單義可譯碼——不能從不等長碼串中唯一分割出對應(yīng)于每個(gè)符號的碼字；碼B是延時(shí)碼——它需等到對應(yīng)于下個(gè)符號的碼字開頭0才能確定本碼字的結(jié)束；碼C是即時(shí)碼6/23/2024定義異前置碼——任何碼字都不是其它碼字的前綴碼C是異前置碼異前置碼可以用樹圖構(gòu)造碼C所對應(yīng)的二進(jìn)制碼樹圖0101016/23/2024碼樹圖從樹根開始到每片樹葉的聯(lián)枝代表一個(gè)碼字010101碼C——0,10,110,1116/23/2024長度為ki

i=1,2,…,nN的二進(jìn)制異前置碼存在的充分必要條件——Kraft不等式4、Kraft不等式6/23/20245、最優(yōu)碼6/23/20246/23/20246/23/2024二、無失真信源編碼①將符號序列aii=1,2,…,nN按概率降序排列②確定第i個(gè)碼字的碼長1、香農(nóng)碼編碼步驟6/23/2024③令P(a0)=0，計(jì)算第i-1個(gè)符號序列的累加概率④將Pa(ai)用二進(jìn)制表示，取小數(shù)點(diǎn)后ki位作為符號序列ai的碼字ci

i=1,2,…,nN6/23/2024編香農(nóng)碼并計(jì)算編碼效率①將符號xii=1,2,3,4按概率降序排列例1②確定第i個(gè)碼字的碼長6/23/2024③令P(x0)=0，計(jì)算第i個(gè)碼字的累加概率6/23/2024④將Pa(xi)用二進(jìn)制表示，取小數(shù)點(diǎn)后ki位作為xi的碼字ciPa(x1)=0.0=(0.000000…)2→c1=0Pa(x2)=0.5=(0.100000…)2→c2=10Pa(x3)=0.8=(0.110011…)2→c3=110Pa(x4)=0.95=(0.111100…)2→c4=111106/23/2024xiP(xi)kiPa(xi)cix10.5100x20.320.510x30.1530.8110x40.0550.95111106/23/20246/23/2024分別對信源和二次擴(kuò)展信源編香農(nóng)碼并計(jì)算編碼效率(1)信源編碼并計(jì)算編碼效率例26/23/2024Pa(x1)=0.0=(0.000000…)2→c1=0Pa(x2)=0.5=(0.100000…)2→c2=10Pa(x3)=0.8=(0.110011…)2→c3=110Pa(x1)=0+0=0Pa(x2)=0+0.5=0.5Pa(x3)=0.5+0.3=0.8xiP(xi)kiPa(xi)cix10.5100x20.320.510x30.230.81106/23/20246/23/2024(2)二次擴(kuò)展信源編碼并計(jì)算編碼效率6/23/20246/23/2024Pa(x1x1)=0+0=0Pa(x1x2)=0+0.25=0.25Pa(x2x1)=0.25+0.15=0.4Pa(x1x3)=0.4+0.15=0.55Pa(x3x1)=0.55+0.1=0.65Pa(x2x2)=0.65+0.1=0.75Pa(x2x3)=0.75+0.09=0.84Pa(x3x2)=0.84+0.06=0.9Pa(x3x3)=0.9+0.06=0.966/23/2024Pa(x1x1)=0.0=(0.00)2→c1=00Pa(x1x2)=0.25=(0.010)2→c2=010Pa(x2x1)=0.4=(0.011…)2→c3=011Pa(x1x3)=0.55=(0.1000…)2→c4=1000Pa(x3x1)=0.65=(0.1010…)2→c5=1010Pa(x2x2)=0.75=(0.1100)2→c6=1100Pa(x2x3)=0.84=(0.11010…)2→c7=11010Pa(x3x2)=0.9=(0.11100…)2→c8=11100Pa(x3x3)=0.96=(0.11101…)2→c9=111016/23/2024aiP(ai)kiPa(ai)cix1x10.252000x1x20.1530.25010x2x10.1530.4011x1x30.140.551000x3x10.140.651010x2x20.0940.751100x2x30.0650.8411010x3x20.0650.911100x3x30.0450.96111016/23/20246/23/2024香農(nóng)碼的特點(diǎn)編碼過程中先確定碼長，后確定碼字，保證大概率符號序列編為短碼，小概率符號序列編為長碼第一個(gè)符號序列的累加概率為0，對應(yīng)碼字總是0、00、…形式具有唯一性碼率不超過熵率1/N個(gè)比特，N越大碼率越接近熵率6/23/2024習(xí)題，(P166)5.16/23/2024①將符號序列aii=1,2,…,nN按概率降序排列②不改變排列次序條件下分為兩組，使每組概率盡可能相等③給每組分配一個(gè)二進(jìn)制碼元對每個(gè)分組重復(fù)②③步驟，直到不可分為止2、費(fèi)諾碼編碼步驟分配給符號序列ai的全部碼元作為該符號序列的碼字cii=1,2,…,nN6/23/2024編費(fèi)諾碼并計(jì)算編碼效率例1①將符號xii=1,2,3,4按概率降序排列②不改變排列次序條件下第一次分組，使每組概率盡可能相等6/23/2024xiP(xi)分組1分組2分組3cix10.50x20.31x30.15x40.05③給每組分配一個(gè)二進(jìn)制碼元對每個(gè)分組重復(fù)②③步驟6/23/2024第二次分組及分配二進(jìn)制碼元xiP(xi)分組1分組2分組3cix10.50x20.310x30.151x40.056/23/2024第三次分組及分配二進(jìn)制碼元xiP(xi)分組1分組2分組3cix10.500x20.31010x30.1510110x40.0511116/23/20246/23/2024例2分別對信源和二次擴(kuò)展信源編費(fèi)諾碼并計(jì)算編碼效率(1)信源編碼并計(jì)算編碼效率第一次分組及分配二進(jìn)制碼元6/23/2024第二次分組及分配二進(jìn)制碼元xiP(xi)分組1分組2cix10.500x20.41010x30.11116/23/20246/23/2024(2)二次擴(kuò)展信源編碼并計(jì)算編碼效率6/23/2024第二次分組及分配二進(jìn)制碼元第一次分組及分配二進(jìn)制碼元6/23/2024第三次分組及分配二進(jìn)制碼元第四次分組及分配二進(jìn)制碼元6/23/2024第六次分組及分配二進(jìn)制碼元第五次分組及分配二進(jìn)制碼元6/23/2024aiP(ai)分組1分組2分組3分組4分組5分組6cix1x10.250000x1x20.2101x2x10.21010x2x20.1610110x1x30.0510011100x3x10.05111101x2x30.041011110x3x20.0410111110x3x30.0111111116/23/20246/23/2024兩種方法進(jìn)行費(fèi)諾編碼并計(jì)算平均碼長(1)方法1——大概率分組排在前面例3第一次分組及分配二進(jìn)制碼元6/23/2024第二次分組及分配二進(jìn)制碼元第三次分組及分配二進(jìn)制碼元6/23/2024xiP(xi)分組1分組2分組3cix10.40000x20.2101x30.21010x40.110110x50.111116/23/2024(2)方法2——小概率分組排在前面第一次分組及分配二進(jìn)制碼元第二次分組及分配二進(jìn)制碼元6/23/2024第三次分組及分配二進(jìn)制碼元第四次分組及分配二進(jìn)制碼元6/23/2024xiP(xi)分組1分組2分組3分組4cix10.400x20.21010x30.210110x40.1101110x50.1111116/23/2024采用不同排列方法編出的費(fèi)諾碼，碼字和碼長可能完全不相同，但平均碼長相等——編碼效率不會因排列方法而改變6/23/2024費(fèi)諾碼的特點(diǎn)編碼過程中先確定碼字，后確定碼長大概率符號序列分解次數(shù)少，編為短碼，小概率符號序列分解次數(shù)多，編為長碼不具有唯一性，但不同費(fèi)諾碼的編碼效率相同碼率不超過熵率1/N個(gè)比特，N越大碼率越接近熵率6/23/2024習(xí)題，(P166)5.26/23/2024①將符號序列aii=1,2,…,nN按概率降序排列②為概率最小的兩個(gè)符號序列各自分配一個(gè)二進(jìn)制碼元③將概率最小的兩個(gè)符號序列合并成一個(gè)新的符號序列，用兩者概率之和作為新符號序列的概率3、赫夫曼碼編碼步驟重復(fù)①②③步驟，直到合并出一個(gè)以1為概率的新符號序列6/23/2024編赫夫曼碼并計(jì)算編碼效率①將符號xii=1,2,3,4按概率降序排列例1分配給符號序列ai的全部碼元作為該符號序列的碼字cii=1,2,…,nN②為概率最小的兩個(gè)符號序列各自分配一個(gè)二進(jìn)制碼元6/23/202410③將概率最小的兩個(gè)符號合并成一個(gè)新的符號，用兩者概率之和作為新符號的概率0.2x3，xiP(xi)x10.5x2x3x40.30.150.056/23/2024重復(fù)①②③步驟，直到合并出一個(gè)以1為概率的新符號xiP(xi)x10.5x2x3，0.30.2100.5x2，xiP(xi)x10.5x2，0.5101x1，6/23/2024cikixiP(xi)x10.5x2x3x40.30.150.050.20.511110000101101111233整個(gè)編碼過程集中在一起6/23/20246/23/2024例2分別對信源和二次擴(kuò)展信源編赫夫曼碼并計(jì)算編碼效率(1)信源編碼并計(jì)算編碼效率6/23/2024xiP(xi)x10.5x2x30.40.10.510110ciki010111226/23/2024(2)二次擴(kuò)展信源編碼并計(jì)算編碼效率6/23/2024aiP(ai)x1x10.25x1x2x2x1x2x20.20.20.16x1x30.05x3x1x2x30.050.04x3x20.04x3x30.010.050.091000110.1100.190.410010.35100.61016/23/20242236255560110001000101110000100011000000001000.050.091000110.1