Ch2例題與證明五.doc

u 定長(zhǎng)編碼定理 由L個(gè)符號(hào)組成的，每個(gè)符號(hào)的熵為H(X)的平穩(wěn)無(wú)記憶符號(hào)序列 ，可用K個(gè)符號(hào)（每個(gè)符號(hào)有m種可能取值）進(jìn)行定長(zhǎng)編碼，對(duì)任意，只要?jiǎng)t當(dāng)L足夠大時(shí)，必可使譯碼差錯(cuò)小于。反之當(dāng)時(shí)，譯碼差錯(cuò)一定是有限值，當(dāng)L足夠大時(shí)，譯碼必定出錯(cuò)。不等式（1）中，m代表碼序列中每個(gè)符號(hào)的可能取值數(shù)，假定m個(gè)取值是等概率的,則單個(gè)符號(hào)的信息量為。對(duì)于定長(zhǎng)編碼，每個(gè)碼字的長(zhǎng)度都是K，故碼字的總數(shù)為。若信源是平穩(wěn)無(wú)記憶的，長(zhǎng)度為K的碼序列的總信息量為：代表的是消息（長(zhǎng)為L(zhǎng)的信源符號(hào)序列）的信息量。平均每個(gè)符號(hào)的信息量即平均符號(hào)熵為。顯然傳送一個(gè)信源符號(hào)所需的信息率就是。定長(zhǎng)編碼定理中的正定理說(shuō)明，信息率略大于單符號(hào)熵時(shí)，可做到幾乎無(wú)失真譯碼，條件是L必須足夠大?？梢宰C明，只要 (3)譯碼差錯(cuò)率一定小于任意正數(shù)。逆定理說(shuō)明，信息率比信源熵略小一點(diǎn)（小一個(gè)）時(shí)，譯碼差錯(cuò)未必超過(guò)限定值，但若比H(X)小，則譯碼失真一定大于，時(shí)，必定失真。 信源熵H(X)其實(shí)就是一個(gè)界限，或者說(shuō)是一個(gè)臨界值，當(dāng)編碼器輸出的信息率超過(guò)這個(gè)臨界值時(shí)，就能無(wú)失真譯碼，否則就不行。信源編碼定理從理論上闡明了編碼效率接近于1，即的理想編碼器的存在性，代價(jià)是在實(shí)際編碼時(shí)取無(wú)限長(zhǎng)的信源符號(hào)（）進(jìn)行統(tǒng)一編碼。具體來(lái)說(shuō)，就是給定和，用式（3）規(guī)定的L計(jì)算所有可能信源消息的概率，按由大到小的次序排列，選用概率較大的消息進(jìn)行編碼，于是有編碼的消息構(gòu)成一個(gè)集合，直到該集合的概率，意味著譯碼差錯(cuò)率必定小于，即完成了編碼過(guò)程。只要足夠小，就可實(shí)現(xiàn)幾乎無(wú)失真譯碼，所需的信息率也不會(huì)超過(guò)；若足夠小，編碼效率就接近于1。理想編碼器實(shí)際上是很難實(shí)現(xiàn)的。例2.4.1設(shè)某單符號(hào)信源模型為計(jì)算得 若要求編碼效率為90%,即 則 =0.28 設(shè)譯碼差錯(cuò)率為，由式（3）可得 由此可見(jiàn)，在差錯(cuò)率和效率的要求都不苛刻的情況下，就必須有1600多萬(wàn)個(gè)信源符號(hào)一起編碼，技術(shù)實(shí)現(xiàn)非常困難。不僅如此，它的編碼效率也不高。對(duì)8種可能的取值編定長(zhǎng)碼，要無(wú)差錯(cuò)地譯碼，每種取值需用3個(gè)比特，其編碼效率為了解決這一問(wèn)題，就出現(xiàn)了不等長(zhǎng)編碼，也稱(chēng)變長(zhǎng)編碼。不等長(zhǎng)編碼允許把等長(zhǎng)的消息變換成不等長(zhǎng)的碼序列。通常把經(jīng)常出現(xiàn)的消息編成短碼，不常出現(xiàn)的消息編成長(zhǎng)碼。這樣可使平均碼長(zhǎng)最短，從而提高通信效率，代價(jià)是增加了編譯碼設(shè)備的復(fù)雜度。例如在不等長(zhǎng)碼字組成的序列中要正確識(shí)別每個(gè)長(zhǎng)度不同的碼字的起點(diǎn)就比等長(zhǎng)碼復(fù)雜得多。另外，接收到一個(gè)不等長(zhǎng)碼序列后，有時(shí)不能馬上斷定碼字是否真正結(jié)束，因而不能立即譯出該碼，要等到后面的符號(hào)收到后才能正確譯出。這就是所謂的譯碼同步和譯碼延時(shí)問(wèn)題。例2.4.2 顯然碼A與信源消息不是一一對(duì)應(yīng)，因而它不是唯一可譯碼。碼B雖然能完成消息的唯一編碼，但它仍然不是唯一可譯的。因?yàn)槿羰盏?0，可譯為，也可譯為；同樣11也不是唯一可譯的。碼C雖是唯一可譯的，但它要等到下一個(gè)“0”收到后才能確定碼字的結(jié)束，于是有譯碼延時(shí)。只有碼D既是唯一可譯的，又沒(méi)有延時(shí)。 如果一個(gè)碼的任何一個(gè)碼字都不是其它碼字的前綴，則稱(chēng)該碼為前綴碼、異前置碼、異字頭碼、逗點(diǎn)碼，也稱(chēng)即時(shí)碼。 碼D是即時(shí)碼，可用樹(shù)圖法來(lái)構(gòu)造。對(duì)于m元或m進(jìn)制樹(shù)圖，在最頂部畫(huà)一個(gè)起始點(diǎn)，成為樹(shù)根。從根部引出m條線段，每條線段都稱(chēng)為樹(shù)枝。通過(guò)樹(shù)枝到達(dá)另一個(gè)節(jié)點(diǎn)，從這個(gè)節(jié)點(diǎn)往下，有可以分出m個(gè)樹(shù)枝。如此下去，就可以構(gòu)造出一個(gè)樹(shù)形圖，稱(chēng)為m元或m進(jìn)制碼樹(shù)圖。自根部起，通過(guò)一條樹(shù)枝到達(dá)的接點(diǎn)為一級(jí)節(jié)點(diǎn)，一級(jí)節(jié)點(diǎn)最多有m個(gè)；通過(guò)兩條樹(shù)枝到達(dá)的節(jié)點(diǎn)稱(chēng)為二級(jí)節(jié)點(diǎn)，二級(jí)節(jié)點(diǎn)最多有個(gè)；如此則通過(guò)n條樹(shù)枝到達(dá)的節(jié)點(diǎn)稱(chēng)為n級(jí)節(jié)點(diǎn)，n級(jí)節(jié)點(diǎn)最多有個(gè)。下面不再有樹(shù)枝的節(jié)點(diǎn)稱(chēng)為終端節(jié)點(diǎn)或終節(jié)點(diǎn)。除了樹(shù)根和終結(jié)點(diǎn)以外，其余的節(jié)點(diǎn)都稱(chēng)為中間節(jié)點(diǎn)。串聯(lián)的樹(shù)枝稱(chēng)為聯(lián)枝。從樹(shù)根開(kāi)始到每一個(gè)終結(jié)點(diǎn)的聯(lián)枝代表一個(gè)碼字。3元碼樹(shù)圖如下：在碼樹(shù)圖中，當(dāng)每一個(gè)碼字的串聯(lián)枝數(shù)都相同時(shí)，就是定長(zhǎng)碼。此時(shí)的碼樹(shù)稱(chēng)為滿樹(shù)，如上圖(a)。碼長(zhǎng)為N的滿樹(shù)的終節(jié)點(diǎn)個(gè)數(shù)為，即可表示個(gè)碼字。當(dāng)有些樹(shù)枝未用時(shí)，稱(chēng)為非滿樹(shù)，如上圖(b)所示。非滿樹(shù)構(gòu)造的就是變長(zhǎng)碼。如果每一個(gè)碼字都被安排在終節(jié)點(diǎn)上，這種碼就是異前置碼。M元長(zhǎng)度為的異前置碼存在的充要條件是 （4）式（4）稱(chēng)為克拉夫特不等式。現(xiàn)在來(lái)證明這個(gè)不等式。設(shè)異前置碼第i個(gè)碼字的長(zhǎng)度為，我們構(gòu)造了一個(gè)碼樹(shù)圖，在第級(jí)，總共有個(gè)節(jié)點(diǎn)。第i個(gè)碼字占據(jù)了第級(jí)的。根據(jù)異前置碼的定義，其后的樹(shù)枝不能再用。對(duì)于N級(jí)滿而言，其后不能用的枝數(shù)為，那么總共不用的枝數(shù)為。N級(jí)滿樹(shù)第N級(jí)上的總枝數(shù)已知為，所以必有 （5）兩邊除以，就得這就是異前置碼存在的必要條件。反之，如果式(4)成立，則式(5)必成立，總可以把第N級(jí)上的樹(shù)枝分成n組，各組中從第N級(jí)開(kāi)始刪除個(gè)枝。相對(duì)于N級(jí)滿樹(shù)而言，等于刪除了所有可能的級(jí)節(jié)點(diǎn)的。在該組中以第級(jí)節(jié)點(diǎn)作為終節(jié)點(diǎn)，就構(gòu)造好了第i個(gè)碼字。對(duì)所有的n個(gè)碼字均如法炮制，則總共刪除了所有個(gè)節(jié)點(diǎn)中的。由于于是構(gòu)造了一個(gè)異前置碼。這是異前置碼存在的充分條件。根據(jù)克拉夫特不等式，證明變長(zhǎng)編碼定理。變長(zhǎng)編碼定理 若一離散無(wú)記憶信源的符號(hào)熵為，對(duì)信源符號(hào)進(jìn)行m元變長(zhǎng)編碼，一定存在一種無(wú)失真編碼方法，其碼字平均長(zhǎng)度滿足下列不等式 (6) 其平均信息率滿足不等式 （7）式中， 為任意正數(shù)。 證明 設(shè)信源符號(hào)，概率為，若對(duì)用一個(gè)長(zhǎng)度為的碼字，使 （8）只要我們規(guī)定為整數(shù)時(shí)，式（8）取等號(hào)，非整數(shù)時(shí)，取比它大一些的最接近的整數(shù)，則滿足上式的整數(shù)必存在。將式（8）分別乘以再對(duì)i求和。得對(duì)取數(shù)學(xué)期望就是平均值，故由式(8) 碼字長(zhǎng)度滿足克拉夫特不等式，因而是異前置碼。對(duì)于平穩(wěn)無(wú)記憶信源來(lái)說(shuō)，當(dāng)信源輸出的是長(zhǎng)度為L(zhǎng)的消息序列時(shí)，易證式