信息論與編碼民大05-最佳信源編碼

5/3/2020,1/34,最佳信源編碼,5/3/2020,2/34,引言,香農(nóng)編碼定理雖然指出了理想編碼器的存在性,但是并沒有給出實(shí)用碼的結(jié)構(gòu)及構(gòu)造方法；編碼理論正是為了解決這一問(wèn)題而發(fā)展起來(lái)的科學(xué)理論；編碼的目的是為了優(yōu)化通信系統(tǒng)，使通信系統(tǒng)的性能指標(biāo)有效性、可靠性、安全性和經(jīng)濟(jì)性達(dá)到最佳；按不同的編碼目的，編碼分為三類：信源編碼、信道編碼和安全編碼（加密編碼）。,5/3/2020,3/34,信源編碼：提高通信有效性。通常通過(guò)壓縮信源的冗余度來(lái)實(shí)現(xiàn)。采用的一般方法是壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)或信源的傳輸率（碼率）。即同樣多的信息用較少的信息率來(lái)傳送，使單位時(shí)間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。信道編碼：提高信息傳輸?shù)目煽啃?。通常通過(guò)增加信源的冗余度來(lái)實(shí)現(xiàn)。采用的一般方法是增大碼率/帶寬。與信源編碼正好相反。加密編碼：提高通信系統(tǒng)的安全性。通常通過(guò)加密和解密來(lái)實(shí)現(xiàn)。從信息論的觀點(diǎn)出發(fā)，“加密”可視為增熵的過(guò)程，“解密”可視為減熵的過(guò)程。,5/3/2020,4/34,信源編碼定理：對(duì)于給定的失真率D，總可以找到一種信源編碼方法，只要信源速率R大于R(D)，就可以在平均失真任意接近D的條件下實(shí)現(xiàn)波形重建。說(shuō)明1：R(D)稱為率失真函數(shù)，它是單調(diào)非增函數(shù)，速率越高，平均失真越小。說(shuō)明2：為了保證在一定速率下的失真，必需采用信源編碼，因而會(huì)引入編碼延時(shí)。信道編碼定理：如果信源速率R小于信道容量C，總可以找到一種信道編碼方法，使得信源信息可以在有噪聲信道上進(jìn)行無(wú)差錯(cuò)傳輸，即：RC，無(wú)差錯(cuò)傳輸條件說(shuō)明1：信道容量C可根據(jù)香農(nóng)定理得到CWlog2(1+S/N)說(shuō)明2：為了保證無(wú)差錯(cuò)傳輸，必需采用信道編碼，因而會(huì)引入編碼延時(shí)。,編碼理論,信息傳輸定理：將信源編碼定理和信道編碼定理綜合，就得到信息傳輸定理。即：為保證無(wú)差錯(cuò)傳輸及失真度的要求，必需滿足：CRR(D)說(shuō)明1：在一般數(shù)字通信系統(tǒng)中，信源編碼和信道編碼可以分開考慮。信道編碼定理給出無(wú)差錯(cuò)的速率上限，信源編碼定理給出無(wú)失真或限失真的速率下限。說(shuō)明2：為了實(shí)現(xiàn)理想性能，都要付出延時(shí)的代價(jià)。,5/3/2020,6/34,速率：高速率、中速率、低速率壓縮比質(zhì)量：客觀評(píng)價(jià)主觀評(píng)價(jià)延時(shí)：質(zhì)量和延時(shí)的關(guān)系不同業(yè)務(wù)對(duì)延時(shí)的要求復(fù)雜性：算法的復(fù)雜性及軟硬件實(shí)現(xiàn)的復(fù)雜性,信源編碼的性能指標(biāo),5/3/2020,7/34,波形編碼：將波形直接變換成數(shù)字碼流。特點(diǎn)：比特率較高、解碼后質(zhì)量較高、延時(shí)較小?？梢苑譃椋簳r(shí)域波形編碼，如PCM、ADPCM、M等；頻域波形編碼，如：子帶編碼(SBC)、自適應(yīng)變換編碼(ATC)等。參數(shù)編碼：從信源信號(hào)的某個(gè)域中提取特征參數(shù)，并變換成數(shù)字碼流。特點(diǎn)：比特率較低、解碼后質(zhì)量較低、延時(shí)較大。如：各種聲碼器?；旌暇幋a：將以上二種方法混合，特點(diǎn)：以較低的比特率獲得較高的質(zhì)量，延時(shí)適中，復(fù)雜。如：GSM的語(yǔ)音編碼，IS-95的語(yǔ)音編碼等。,信源編碼的實(shí)現(xiàn)方法,5/3/2020,8/34,香農(nóng)編碼,設(shè)離散無(wú)記憶信源二進(jìn)制香農(nóng)碼的編碼步驟如下(4步)：將信源符號(hào)按概率從大到小的順序排列p(x1)p(x2)p(xn)令p(x0)=0，用pa(xj)，j=i+1表示第i個(gè)碼字的累加概率確定滿足下列不等式的整數(shù)ki，并令ki為第i個(gè)碼字的長(zhǎng)度log2p(xn)ki1log2p(xn)將pa(xj)用二進(jìn)制表示，并取小數(shù)點(diǎn)后ki位作為符號(hào)xi的編碼。,5/3/2020,9/34,例有一單符號(hào)離散無(wú)記憶信源對(duì)該信源編二進(jìn)制香農(nóng)碼。其編碼過(guò)程如表所示。,5/3/2020,10/34,香農(nóng)碼的平均碼長(zhǎng)若對(duì)上述信源采用等長(zhǎng)編碼，要做到無(wú)失真譯碼，每個(gè)符號(hào)至少要用3個(gè)比特表示。相比較，香農(nóng)編碼對(duì)信源的等長(zhǎng)編碼而言有0.3比特/符號(hào)的壓縮。,由離散無(wú)記憶信源熵定義，可計(jì)算出：對(duì)上述信源采用香農(nóng)編碼的信息率為編碼效率為信源熵和信息率之比。則可以看出，編碼效率并不是很高。,5/3/2020,11/34,費(fèi)諾編碼,費(fèi)諾編碼也是一種常見的信源編碼方法。編碼步驟如下：將概率按從大到小的順序排列，令p(x1)p(x2)p(xn)按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近或相等。如編二進(jìn)制碼就分成兩組，編m進(jìn)制碼就分成m組。給每一組分配一位碼元。將每一分組再按同樣原則劃分，重復(fù)步驟2和3，直至概率不再可分為止。,5/3/2020,12/34,例與香農(nóng)編碼一樣的單符號(hào)離散信源對(duì)該信源編二進(jìn)制費(fèi)諾碼。編碼過(guò)程如表。,5/3/2020,13/34,上述碼字還可用碼樹來(lái)表示，如圖所示。,5/3/2020,14/34,該信源的熵為平均碼長(zhǎng)為編碼效率為費(fèi)諾編碼有較高的編碼效率。費(fèi)諾碼比較適合于每次分組概率都很接近的信源。特別是對(duì)每次分組概率都相等的信源進(jìn)行編碼時(shí)，可達(dá)到理想的編碼效率。,5/3/2020,15/34,例有一單符號(hào)離散無(wú)記憶信源對(duì)該信源編二進(jìn)制費(fèi)諾碼，編碼過(guò)程如表。,5/3/2020,16/34,碼樹圖如圖信源熵為H(X)=2.75(比特/符號(hào))平均碼長(zhǎng)為信息率編碼效率為=100%。因?yàn)槊看嗡謨山M的概率恰好相等。,5/3/2020,17/34,5.4.1編碼步驟,哈夫曼(Huffman)編碼是一種效率比較高的變長(zhǎng)無(wú)失真信源編碼方法。將信源符號(hào)按概率從大到小的順序排列，令p(x1)p(x2)p(xn)給兩個(gè)概率最小的信源符號(hào)p(xn-1)和p(xn)各分配一個(gè)碼位“0”和“1”，將這兩個(gè)信源符號(hào)合并成一個(gè)新符號(hào)，并用這兩個(gè)最小的概率之和作為新符號(hào)的概率，結(jié)果得到一個(gè)只包含(n1)個(gè)信源符號(hào)的新信源。稱為信源的第一次縮減信源，用S1表示。將縮減信源S1的符號(hào)仍按概率從大到小順序排列，重復(fù)步驟2，得到只含(n2)個(gè)符號(hào)的縮減信源S2。重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號(hào)為止，此時(shí)所剩兩個(gè)符號(hào)的概率之和必為1。然后從最后一級(jí)縮減信源開始，依編碼路徑向前返回，就得到各信源符號(hào)所對(duì)應(yīng)的碼字。,哈夫曼編碼,5/3/2020,18/34,例設(shè)單符號(hào)離散無(wú)記憶信源如下，要求對(duì)信源編二進(jìn)制哈夫曼碼。,5/3/2020,19/34,將上圖左右顛倒過(guò)來(lái)重畫一下，即可得到二進(jìn)制哈夫曼碼的碼樹，如圖所示。,5/3/2020,20/34,信源熵為平均碼長(zhǎng)為編碼效率為若采用定長(zhǎng)編碼，碼長(zhǎng)K=3，則編碼效率可見哈夫曼的編碼效率提高了12.7%。,5/3/2020,21/34,注意：哈夫曼的編碼并不惟一。每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0”和“1”碼元是任意的，所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性，即能得到可分離碼字。不同的碼元分配，得到的具體碼字不同，但碼長(zhǎng)ki不變，平均碼長(zhǎng)也不變，所以沒有本質(zhì)區(qū)別；縮減信源時(shí)，若合并后的新符號(hào)概率與其他符號(hào)概率相等，從編碼方法上來(lái)說(shuō)，這幾個(gè)符號(hào)的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。不同的編法得到的碼字長(zhǎng)度ki也不盡相同。,5/3/2020,22/34,舉例說(shuō)明上述問(wèn)題例:單符號(hào)離散無(wú)記憶信源方法一：合并后的新符號(hào)排在其它相同概率符號(hào)的后面。,5/3/2020,23/34,5/3/2020,24/34,方法二：合并后的新符號(hào)排在其它相同概率符號(hào)的前面。,5/3/2020,25/34,5/3/2020,26/34,單符號(hào)信源編二進(jìn)制哈夫曼碼，編碼效率主要決定于信源熵和平均碼長(zhǎng)之比。對(duì)相同的信源編碼，其熵是一樣的，采用不同的編法，得到的平均碼長(zhǎng)可能不同。平均碼長(zhǎng)越短，編碼效率就越高。編法一的平均碼長(zhǎng)為編法二的平均碼長(zhǎng)為可見，本例兩種編法的平均碼長(zhǎng)相同，所以編碼效率相同。,5/3/2020,27/34,討論：哪種方法更好？定義碼字長(zhǎng)度的方差2：長(zhǎng)度ki與平均碼長(zhǎng)之差的平方的數(shù)學(xué)期望，即編法一碼字長(zhǎng)度方差：編法二碼字長(zhǎng)度方差：,可見：編法二的碼長(zhǎng)方差要小許多。意味著第二種編碼方法的碼長(zhǎng)變化較小，比較接近于平均碼長(zhǎng)。編法一的5個(gè)碼字有4種不同的碼長(zhǎng)；而編法二的碼字只有2種不同的碼長(zhǎng)；顯然，編法二的方法更簡(jiǎn)單、更容易實(shí)現(xiàn)，所以更好。結(jié)論：在哈夫曼編碼過(guò)程中，對(duì)縮減信源符號(hào)按概率由大到小的順序重新排列時(shí)，應(yīng)使合并后的新符號(hào)盡可能排在靠前的位置，這樣可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少，使短碼得到充分利用。,5/3/2020,28/34,“全樹”概念定義：碼樹圖中每個(gè)中間節(jié)點(diǎn)后續(xù)的枝數(shù)為m時(shí)稱為全樹；若有些節(jié)點(diǎn)的后續(xù)枝數(shù)不足m，就稱為非全樹。二進(jìn)制碼不存在非全樹的情況，因?yàn)楹罄m(xù)枝數(shù)是一時(shí)，這個(gè)枝就可以去掉使碼字長(zhǎng)度縮短。對(duì)m進(jìn)制編碼：若所有碼字構(gòu)成全樹，可分離的碼字?jǐn)?shù)（信源個(gè)數(shù)）必為m+k(m1)。k為正整數(shù)。若信源所含的符號(hào)數(shù)n不能構(gòu)成m進(jìn)制全樹，必須增加s個(gè)不用的碼字形成全樹。顯然sm1，若s=m1，意味著某個(gè)中間節(jié)點(diǎn)之后只有一個(gè)分枝，為了節(jié)約碼長(zhǎng)，這一分枝可以省略。,m進(jìn)制哈夫曼編碼,5/3/2020,29/34,例：對(duì)前面的單符號(hào)離散無(wú)記憶信源編三進(jìn)制哈夫曼碼。這里：m=3，n=8令k=3，m+k(m1)=9，則s=9n=98=1所以第一次取ms=2個(gè)符號(hào)進(jìn)行編碼。,5/3/2020,30/34,5/3/2020,31/34,平均碼長(zhǎng)為信息率為編碼效率為可見：哈夫