信息論第5章 信源編碼

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

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

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

i=1,2,…,nN6/23/2024編香農(nóng)碼并計(jì)算編碼效率①將符號(hào)xii=1,2,3,4按概率降序排列例1②確定第i個(gè)碼字的碼長(zhǎng)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分別對(duì)信源和二次擴(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)編碼過(guò)程中先確定碼長(zhǎng)，后確定碼字，保證大概率符號(hào)序列編為短碼，小概率符號(hào)序列編為長(zhǎng)碼第一個(gè)符號(hào)序列的累加概率為0，對(duì)應(yīng)碼字總是0、00、…形式具有唯一性碼率不超過(guò)熵率1/N個(gè)比特，N越大碼率越接近熵率6/23/2024習(xí)題，(P166)5.16/23/2024①將符號(hào)序列aii=1,2,…,nN按概率降序排列②不改變排列次序條件下分為兩組，使每組概率盡可能相等③給每組分配一個(gè)二進(jìn)制碼元對(duì)每個(gè)分組重復(fù)②③步驟，直到不可分為止2、費(fèi)諾碼編碼步驟分配給符號(hào)序列ai的全部碼元作為該符號(hào)序列的碼字cii=1,2,…,nN6/23/2024編費(fèi)諾碼并計(jì)算編碼效率例1①將符號(hào)xii=1,2,3,4按概率降序排列②不改變排列次序條件下第一次分組，使每組概率盡可能相等6/23/2024xiP(xi)分組1分組2分組3cix10.50x20.31x30.15x40.05③給每組分配一個(gè)二進(jìn)制碼元對(duì)每個(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分別對(duì)信源和二次擴(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ì)算平均碼長(zhǎng)(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)諾碼，碼字和碼長(zhǎng)可能完全不相同，但平均碼長(zhǎng)相等——編碼效率不會(huì)因排列方法而改變6/23/2024費(fèi)諾碼的特點(diǎn)編碼過(guò)程中先確定碼字，后確定碼長(zhǎng)大概率符號(hào)序列分解次數(shù)少，編為短碼，小概率符號(hào)序列分解次數(shù)多，編為長(zhǎng)碼不具有唯一性，但不同費(fèi)諾碼的編碼效率相同碼率不超過(guò)熵率1/N個(gè)比特，N越大碼率越接近熵率6/23/2024習(xí)題，(P166)5.26/23/2024①將符號(hào)序列aii=1,2,…,nN按概率降序排列②為概率最小的兩個(gè)符號(hào)序列各自分配一個(gè)二進(jìn)制碼元③將概率最小的兩個(gè)符號(hào)序列合并成一個(gè)新的符號(hào)序列，用兩者概率之和作為新符號(hào)序列的概率3、赫夫曼碼編碼步驟重復(fù)①②③步驟，直到合并出一個(gè)以1為概率的新符號(hào)序列6/23/2024編赫夫曼碼并計(jì)算編碼效率①將符號(hào)xii=1,2,3,4按概率降序排列例1分配給符號(hào)序列ai的全部碼元作為該符號(hào)序列的碼字cii=1,2,…,nN②為概率最小的兩個(gè)符號(hào)序列各自分配一個(gè)二進(jìn)制碼元6/23/202410③將概率最小的兩個(gè)符號(hào)合并成一個(gè)新的符號(hào)，用兩者概率之和作為新符號(hào)的概率0.2x3，xiP(xi)x10.5x2x3x40.30.150.056/23/2024重復(fù)①②③步驟，直到合并出一個(gè)以1為概率的新符號(hào)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è)編碼過(guò)程集中在一起6/23/20246/23/2024例2分別對(duì)信源和二次擴(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