第5章 信源編碼part1v2

第5章信源編碼信源編碼信源編碼的基礎(chǔ)是信息論中的兩個(gè)編碼定理：無(wú)失真編碼定理限失真編碼定理無(wú)失真編碼只適用于離散信源；對(duì)于連續(xù)信源，只能在失真受限制的情況下進(jìn)行限失真編碼。本章首先介紹信源編碼的相關(guān)概念以及信源編碼定理，然后描述編碼方法。2024/3/202信源編碼（主要內(nèi)容）信源編碼定理（定長(zhǎng)、變長(zhǎng)編碼定理）信源編碼的相關(guān)概念：定長(zhǎng)編碼定理變長(zhǎng)編碼定理（香農(nóng)第一定理）香農(nóng)第三定理信源編碼方法離散信源編碼連續(xù)信源編碼相關(guān)信源編碼變換編碼2024/3/203目的及基本思路相關(guān)術(shù)語(yǔ)信源編碼的目的及基本思路信源編碼的過(guò)程：目的：用盡可能少的碼符號(hào)數(shù)(條件：碼進(jìn)制數(shù)相同),去傳遞同樣多的信息量。信源符號(hào)信源符號(hào)序列信源符號(hào)集

類比：同樣多貨物，用盡可能少車(chē)次(載重量相同)去拉。碼符號(hào)序列碼符號(hào)集符合信道傳輸特性碼符號(hào)4研究信源編碼時(shí)的通信系統(tǒng)模型編碼后的符號(hào)序列要符合信道傳輸特性(32個(gè)符號(hào))010010100…5問(wèn)題：如何編碼才能保證信息的無(wú)失真?zhèn)鬏?？回答：信源符?hào)序列要與碼符號(hào)序列一一對(duì)應(yīng)。問(wèn)題：最大可能的信源符號(hào)序列數(shù)和碼符號(hào)序列數(shù)？回答：信源符號(hào)序列數(shù)碼符號(hào)序列數(shù)為簡(jiǎn)化起見(jiàn)，假設(shè)，則要求：，信源沒(méi)有被壓縮的可能性？問(wèn)題：分析：(1)由于符號(hào)之間具有相關(guān)性，有些符號(hào)的組合不可能出現(xiàn)。例：英語(yǔ)信源不會(huì)出現(xiàn)。(2)有些符號(hào)的組合，出現(xiàn)概率非常微小。對(duì)這些符號(hào)的組合，可不進(jìn)行編碼。只能實(shí)現(xiàn)近乎無(wú)失真譯碼。6問(wèn)題：假設(shè)信源符號(hào)間沒(méi)有相關(guān)性，能否實(shí)現(xiàn)完全無(wú)失真壓縮？分析：，表面上看沒(méi)有壓縮的余地。但這只是對(duì)定長(zhǎng)編碼而言。對(duì)于非定長(zhǎng)編碼，則有可能有：。實(shí)例：考慮無(wú)記憶信源的三次擴(kuò)展信源編碼：編碼后平均碼長(zhǎng)：7總結(jié)：信源的冗余主要由兩方面因素造成。(1)前后符號(hào)間的相關(guān)性。(2)不同符號(hào)的發(fā)生概率不同。*解決思路：使編碼后的碼符號(hào)序列不存在相關(guān)性，各符號(hào)出現(xiàn)概率相等。*比特平均每符號(hào)的實(shí)際載信量：比特一定有：降低了通信效率。平均每符號(hào)的最大載信量：指導(dǎo)思想：a.利用某種數(shù)學(xué)方法去除相關(guān)性。b.增加的長(zhǎng)度，

越長(zhǎng),符號(hào)間相關(guān)性越強(qiáng)。(2)高概率對(duì)應(yīng)短碼，低概率對(duì)應(yīng)長(zhǎng)碼。8去除相關(guān)性經(jīng)常采用的數(shù)學(xué)方法：傅里葉變換，離散余弦變換，變換，小波變換等例：離散傅里葉變換時(shí)域表示法：個(gè)時(shí)域采樣點(diǎn)，每個(gè)采樣點(diǎn)的幅度頻域表示法：個(gè)頻域采樣點(diǎn)，采樣點(diǎn)的傅里葉系數(shù)相關(guān)獨(dú)立正交變換，各頻率分量彼此獨(dú)立9信源編碼（主要內(nèi)容）信源編碼定理（定長(zhǎng)、變長(zhǎng)編碼定理）信源編碼的相關(guān)概念：定長(zhǎng)編碼定理變長(zhǎng)編碼定理（香農(nóng)第一定理）香農(nóng)第三定理信源編碼方法離散信源編碼連續(xù)信源編碼相關(guān)信源編碼變換編碼2024/3/2010目的及基本思路基本術(shù)語(yǔ)信源編碼的一些基本術(shù)語(yǔ)碼字長(zhǎng)度碼符號(hào)序列集合又稱碼書(shū)，碼又稱碼字又稱碼元信源符號(hào)信源符號(hào)序列信源符號(hào)集碼符號(hào)序列碼符號(hào)集符合信道傳輸特性碼符號(hào)信源符號(hào)序列集合11無(wú)失真編碼：實(shí)現(xiàn)從信源符號(hào)序列集合到碼符號(hào)序列集合間的一一映射。

元碼：又稱進(jìn)制碼，指碼符號(hào)集合中符號(hào)的個(gè)數(shù)。等長(zhǎng)碼：又稱定長(zhǎng)碼，指所有碼字的長(zhǎng)度相等。變長(zhǎng)碼：所有碼字的長(zhǎng)度可以不相等。分組碼：將信源的輸出符號(hào)序列，分組處理的編碼。非分組碼：當(dāng)前碼符號(hào)與信源已經(jīng)輸出的全部符號(hào)有關(guān)。本課程只研究分組碼。12實(shí)例：碼1是碼2是奇異碼非奇異碼問(wèn)題1：奇異碼能否實(shí)現(xiàn)無(wú)失真?zhèn)鬏?？?wèn)題2：非奇異碼是否一定能實(shí)現(xiàn)無(wú)失真?zhèn)鬏敚炕卮穑翰灰欢?。例如：碼2中的可翻譯成或?；卮穑翰荒堋?？？13原因：非奇異碼只是正確譯碼的必要條件，因?yàn)楫?dāng)碼字排在一起時(shí)還有可能出現(xiàn)奇異性。奇異碼與非奇異碼：若分組碼中所有碼字不相同，稱非奇異碼，否則稱為奇異碼。問(wèn)題：如何才能保證碼為唯一可譯碼？分析：假設(shè)所編的碼為。則所有可能的碼符號(hào)序列應(yīng)包括：一次擴(kuò)展碼：共個(gè)二次擴(kuò)展碼：共個(gè)

次擴(kuò)展碼：……共個(gè)14唯一可譯碼與非唯一可譯碼：對(duì)于任意有限長(zhǎng)的碼符號(hào)系列，若只能唯一的分割成一個(gè)個(gè)碼字，則為唯一可譯碼；否則為非唯一可譯碼。例：一連串的碼符號(hào)序列有兩種解釋

三次擴(kuò)展碼中的一個(gè)元素

二次擴(kuò)展碼中的一個(gè)元素15回答：唯一可譯要求碼的任意有限次擴(kuò)展碼應(yīng)為非奇異碼。（唯一可譯性）*在唯一可譯碼中，有一類碼，在譯碼時(shí)無(wú)需參考后續(xù)的碼符號(hào)就能立即做出判斷，譯成對(duì)應(yīng)的信源符號(hào)序列，稱此類碼為即時(shí)碼；否則，稱為非即時(shí)碼。即時(shí)碼與非即時(shí)碼：實(shí)例：碼1是碼2是非即時(shí)碼即時(shí)碼第1位第2位第3位第4位10101011?16分析碼2：即時(shí)碼的條件因?yàn)槿绻麤](méi)有一個(gè)碼字是其它碼字的前綴,則在接收到一個(gè)相當(dāng)于一個(gè)完整碼字的碼符號(hào)序列后,便可立即譯碼,而無(wú)須考慮其后的碼符號(hào)。2024/3/2017問(wèn)題：如何判斷碼是否為即時(shí)碼？（條件）回答：要求任何一個(gè)碼字都不是其它碼字的前綴。例：碼1反例即時(shí)碼的構(gòu)造：最簡(jiǎn)單、最常用的方法是利用碼樹(shù)圖法。根節(jié)點(diǎn)樹(shù)枝一級(jí)節(jié)點(diǎn)二級(jí)節(jié)點(diǎn)三級(jí)節(jié)點(diǎn)編碼過(guò)程及要點(diǎn)：對(duì)于元碼，每個(gè)節(jié)點(diǎn)應(yīng)延伸出個(gè)樹(shù)枝。從第一級(jí)樹(shù)枝開(kāi)始，每個(gè)樹(shù)枝分配一個(gè)碼元。從根節(jié)點(diǎn)開(kāi)始，到終節(jié)點(diǎn)結(jié)束的聯(lián)枝，對(duì)應(yīng)一個(gè)碼字。終端節(jié)點(diǎn)終節(jié)點(diǎn)葉節(jié)點(diǎn)其后不再有樹(shù)枝聯(lián)枝(連在一起的樹(shù)枝)18m＝2的二進(jìn)制樹(shù)圖2024/3/2019問(wèn)題：為什么上述編碼過(guò)程，能保證編碼為即時(shí)碼？回答：關(guān)鍵是對(duì)到終節(jié)點(diǎn)結(jié)束的聯(lián)枝編碼字。從樹(shù)根到每一個(gè)終端節(jié)點(diǎn)所走的路徑均不相同，故一定滿足對(duì)前綴的限制。整樹(shù)與非整樹(shù)考慮一個(gè)樹(shù)有n階節(jié)點(diǎn)整樹(shù)：碼樹(shù)的各個(gè)分支都延伸到最后一級(jí)端點(diǎn)，此時(shí)，將共有mn個(gè)碼字；非整樹(shù)：碼樹(shù)中存在分支，沒(méi)有延伸到最后一級(jí)端點(diǎn)，此時(shí)，將少于mn個(gè)碼字。2024/3/202021從根節(jié)點(diǎn)開(kāi)始，每級(jí)節(jié)點(diǎn)中所有的節(jié)點(diǎn)都向下延伸出m個(gè)節(jié)點(diǎn)，直到最后一級(jí)。滿樹(shù)：碼的分類：同價(jià)碼與非同價(jià)碼：若碼符號(hào)集中

的每個(gè)碼符號(hào)

所占的傳輸時(shí)間都相同，稱為同價(jià)碼；否則，稱為非同價(jià)碼（如：電報(bào)中的莫爾斯碼）。顯然，對(duì)于同價(jià)碼，定長(zhǎng)碼中每個(gè)碼字的傳輸時(shí)間都相同，而變長(zhǎng)碼則可能不同。(本課程只研究同價(jià)碼)非唯一可譯碼非奇異碼分組碼碼非分組碼奇異碼唯一可譯碼即時(shí)碼非即時(shí)碼非同價(jià)碼碼同價(jià)碼變長(zhǎng)碼碼定長(zhǎng)碼22信源編碼（主要內(nèi)容）信源編碼定理（定長(zhǎng)、變長(zhǎng)編碼定理）信源編碼的相關(guān)概念：定長(zhǎng)編碼定理變長(zhǎng)編碼定理（香農(nóng)第一定理）香農(nóng)第三定理信源編碼方法離散信源編碼連續(xù)信源編碼相關(guān)信源編碼變換編碼2024/3/2023唯一可譯定長(zhǎng)碼的存在條件定長(zhǎng)信源編碼定理唯一可譯定長(zhǎng)碼的存在條件2024/3/2024對(duì)一個(gè)簡(jiǎn)單信源X進(jìn)行定長(zhǎng)編碼，信源X存在唯一可譯定長(zhǎng)碼的條件是：其中，n是信源X的符號(hào)個(gè)數(shù)，m是碼符號(hào)數(shù)（碼元個(gè)數(shù)），K是定長(zhǎng)碼的碼長(zhǎng)（碼字長(zhǎng)）。唯一可譯要求:碼的任意有限次擴(kuò)展碼應(yīng)為非奇異碼。定長(zhǎng)碼:每個(gè)碼字長(zhǎng)度相等，所以只要定長(zhǎng)碼是非奇異碼，則必為唯一可譯碼。L次擴(kuò)展信源的定長(zhǎng)碼對(duì)L次擴(kuò)展信源XL進(jìn)行定長(zhǎng)編碼，若要編得的定長(zhǎng)碼是唯一可譯碼，則必須滿足：2024/3/2025唯一可譯定長(zhǎng)碼的存在條件－舉例英文電報(bào)信源有32個(gè)符號(hào)，26個(gè)英文字母加上6個(gè)標(biāo)點(diǎn)符號(hào)，對(duì)此信源的每個(gè)符號(hào)進(jìn)行二元編碼。如何實(shí)現(xiàn)唯一可譯碼？2024/3/2026這就是說(shuō)，每個(gè)英文電報(bào)符號(hào)至少要用5位二元符號(hào)進(jìn)行編碼才能得到唯一可譯碼。分析：信源符號(hào)數(shù)為n＝32，碼元個(gè)數(shù)為m＝2，碼字長(zhǎng)度？定長(zhǎng)信源編碼定理－引入2024/3/2027滿足上述條件的定長(zhǎng)編碼,可保證無(wú)失真的編碼問(wèn)題：平均碼長(zhǎng)很大，編碼的效率很低。定長(zhǎng)編碼定理：討論了編碼的有關(guān)參數(shù)對(duì)譯碼差錯(cuò)的限制關(guān)系。信源編碼（主要內(nèi)容）信源編碼定理（定長(zhǎng)、變長(zhǎng)編碼定理）信源編碼的相關(guān)概念：定長(zhǎng)編碼定理變長(zhǎng)編碼定理（香農(nóng)第一定理）香農(nóng)第三定理信源編碼方法離散信源編碼連續(xù)信源編碼相關(guān)信源編碼變換編碼2024/3/2028唯一可譯定長(zhǎng)碼的存在條件定長(zhǎng)信源編碼定理正定理：一個(gè)熵為的離散無(wú)記憶信源，若對(duì)長(zhǎng)度為的信源符號(hào)序列進(jìn)行等長(zhǎng)編碼，設(shè)碼字是從個(gè)碼符號(hào)集中選取的個(gè)碼元組成。對(duì)于任意的和,只要滿足：則當(dāng)足夠長(zhǎng)

,必可使譯碼差錯(cuò)小于。逆定理：反之，當(dāng)：，譯碼差錯(cuò)一定大于。當(dāng)時(shí)，譯碼差錯(cuò)趨近于1。定長(zhǎng)編碼定理29所要求的譯碼差錯(cuò)概率信源符號(hào)信源符號(hào)序列信源符號(hào)集碼符號(hào)序列（碼字）碼符號(hào)集符合信道傳輸特性碼符號(hào)定長(zhǎng)編碼定理的物理意義30編碼場(chǎng)景n：信源符號(hào)個(gè)數(shù)L:信源符號(hào)序列長(zhǎng)m：碼符號(hào)個(gè)數(shù)K:碼符號(hào)序列長(zhǎng)正定理：

長(zhǎng)碼符號(hào)序列的最大可能載荷信息量。折算后,平均每個(gè)信源符號(hào)的最大可能載信量。每個(gè)信源符號(hào)的實(shí)際載信量。若,說(shuō)明不夠。

物理意義的解釋：31意義：定長(zhǎng)編碼后，所能攜帶的最大信息量，一定要大于信源所攜帶的平均信息量(熵)32定長(zhǎng)編碼定理－提高效率分析：一般情況下，信源符號(hào)非等概率分布，且相互關(guān)聯(lián)信源極限熵H∞(X)

Hmax(X)=logn。2024/3/2033進(jìn)行定長(zhǎng)編碼可使每個(gè)信源符號(hào)平均所需的碼符號(hào)長(zhǎng)大大減少，從而提高效率唯一可譯定長(zhǎng)碼的存在條件問(wèn)題：平均碼長(zhǎng)很大，編碼的效率很低。定長(zhǎng)編碼定理－提高效率2024/3/2034平均每個(gè)英文信源符號(hào)只需近似用1.4個(gè)二元符號(hào)來(lái)編碼，這比由式(K/L)≥logn計(jì)算的需要5位二元符號(hào)減少了許多，從而提高了信息傳輸速率。例：英文電報(bào)的二元編碼：已知信源極限熵H∞(X)≈1.4比特/符號(hào)由可以得出：即(K/L)>1.4；編碼信息率2024/3/2035編碼信息率：編碼后平均每個(gè)信源符號(hào)能載荷的最大信息量。若對(duì)長(zhǎng)為L(zhǎng)的信源符號(hào)序列進(jìn)行定長(zhǎng)編碼，每個(gè)序列對(duì)應(yīng)的碼字長(zhǎng)度為K，則比特/信源符號(hào)編碼效率：=編碼后平均每個(gè)信源符號(hào)的最大可能載信量要求平均每個(gè)信源符號(hào)攜帶的實(shí)際信息量編碼效率36編碼后的實(shí)際碼長(zhǎng)最小可能碼長(zhǎng)=說(shuō)明：編碼效率是小于或等于1的數(shù)。對(duì)同一信源，平均碼長(zhǎng)越短，信息傳輸率就越高，編碼效率也越接近1。編碼效率可以用來(lái)衡量各種編碼方法在有效性方面的優(yōu)劣。對(duì)于等長(zhǎng)編碼觀察正定理：的含義：當(dāng)時(shí)，說(shuō)明：折算后平均每個(gè)信源符號(hào)攜帶的最大可能信息量等于要求攜帶的實(shí)際信息量。此時(shí)編碼效率為。越大，編碼效率越低。編碼效率分析37編碼效率與擴(kuò)展次數(shù)L的關(guān)系回答：定長(zhǎng)編碼定理中，只有在L足夠大的時(shí)候，必可使譯碼差錯(cuò)小于

，編碼效率才能趨近于1經(jīng)計(jì)算，當(dāng)允許錯(cuò)誤概率小于時(shí)，信源序列長(zhǎng)度L必滿足2024/3/2038問(wèn)題：什么時(shí)候編碼效率趨近1？？例1

設(shè)有離散無(wú)記憶信源要求編碼效率,譯碼錯(cuò)誤概率,求需要的信源序列長(zhǎng)度L

。(1)計(jì)算自信息量的數(shù)學(xué)期望和方差比特/信源符號(hào)比特2/信源符號(hào)2解：分析計(jì)算步驟定理的應(yīng)用—例139或者利用方差的簡(jiǎn)便計(jì)算公式：(2)根據(jù)要求的編碼效率計(jì)算比特/信源符號(hào)(3)代入公式，計(jì)算信源符號(hào)序列長(zhǎng)度。定理的應(yīng)用—例1（續(xù)）40定理的應(yīng)用—例2例2設(shè)離散無(wú)記憶信源，采取等長(zhǎng)二元編碼時(shí)，要求編碼效率，允許錯(cuò)誤概率求得：H(X)=0.8112024/3/2041分

析在編碼效率和譯碼差錯(cuò)概率都不十分苛刻的情況下，所需的符號(hào)長(zhǎng)度也是非常驚人的。一般只有在信源接近等概率分布時(shí)，算出的符號(hào)序列長(zhǎng)度才是實(shí)際可接受的。對(duì)定長(zhǎng)編碼定理應(yīng)用范圍的說(shuō)明：雖然定長(zhǎng)編碼定理的推導(dǎo)過(guò)程中要求信源是無(wú)記憶信源，但所得結(jié)論可推廣到有記憶信源。無(wú)記憶信源有記憶信源正定理逆定理多符號(hào)信源：馬爾可夫信源：42信源編碼（主要內(nèi)容）信源編碼定理（定長(zhǎng)、變長(zhǎng)編碼定理）信源編碼的相關(guān)概念：定長(zhǎng)編碼定理變長(zhǎng)編碼定理（香農(nóng)第一定理）香農(nóng)第三定理信源編碼方法離散信源編碼連續(xù)信源編碼相關(guān)信源編碼變換編碼2024/3/2043變長(zhǎng)編碼的必要性及付出代價(jià)變長(zhǎng)碼唯一可譯碼的條件變長(zhǎng)信源編碼定理變長(zhǎng)編碼的必要性44定長(zhǎng)編碼在理論上可以達(dá)到很高的編碼效率，但是從例子中可以看到，在編碼效率、錯(cuò)誤概率要求較高的情況下，擴(kuò)展次數(shù)L（定長(zhǎng)編碼需要的符號(hào)數(shù)）需要非常大，這在實(shí)際工程中是無(wú)法實(shí)現(xiàn)的。1.變長(zhǎng)編碼的必要性當(dāng)L有限時(shí)，高傳輸效率的等長(zhǎng)碼往往要引入一定的失真和錯(cuò)誤，它不像變長(zhǎng)碼那樣可以實(shí)現(xiàn)無(wú)失真編碼。在實(shí)際過(guò)程中，普遍使用變長(zhǎng)編碼。變長(zhǎng)編碼付出的代價(jià)452.付出的代價(jià)(1)譯碼時(shí)需要同步。信源符號(hào)序列2…變長(zhǎng)碼通常需要專門(mén)的同步通道。(2)可能遇到譯碼延遲。延遲問(wèn)題：可利用編成即時(shí)碼解決。定長(zhǎng)碼（例：）信源符號(hào)序列1譯碼為不需要同步通道信源編碼（主要內(nèi)容）信源編碼定理（定長(zhǎng)、變長(zhǎng)編碼定理）信源編碼的相關(guān)概念：定長(zhǎng)編碼定理變長(zhǎng)編碼定理（香農(nóng)第一定理）香農(nóng)第三定理信源編碼方法離散信源編碼連續(xù)信源編碼相關(guān)信源編碼變換編碼2024/3/2046變長(zhǎng)編碼的必要性及付出代價(jià)變長(zhǎng)碼唯一可譯碼的條件變長(zhǎng)信源編碼定理變長(zhǎng)碼唯一可譯碼的條件47唯一可譯碼的條件:變長(zhǎng)碼必須是非奇異碼，而且任意有限長(zhǎng)L次擴(kuò)展碼也應(yīng)該是非奇異碼。為了能夠即時(shí)譯碼，變長(zhǎng)碼必須是即時(shí)碼問(wèn)題1:如何判斷一組由給定碼字構(gòu)成的碼是否為即時(shí)碼？回答:要求任何一個(gè)碼字都不是其它碼字的前綴。即時(shí)碼的判定問(wèn)題判斷任何一個(gè)碼字是不是其它碼字的前綴的方法？將給定的一組碼字轉(zhuǎn)成碼樹(shù)圖的形式：若所有碼字均對(duì)應(yīng)從根節(jié)點(diǎn)到終節(jié)點(diǎn)的聯(lián)枝,則為即時(shí)碼;若某個(gè)碼字位于另一碼字對(duì)應(yīng)節(jié)點(diǎn)之后，則為非即時(shí)碼。實(shí)例：判斷以下碼是否為即時(shí)碼？即時(shí)碼的判定48問(wèn)題2:當(dāng)未給定碼字,

如何判斷能否構(gòu)造出一種即時(shí)碼？Kraft（克拉夫特）不等式即時(shí)碼的條件49描述了信源符號(hào)數(shù)和碼字長(zhǎng)度之間滿足什么條件才能構(gòu)成即時(shí)碼。定理設(shè)信源符號(hào)集

，碼符號(hào)集為

，對(duì)信源進(jìn)行編碼，相應(yīng)的碼字為

，其分別對(duì)應(yīng)的碼長(zhǎng)為

，則即時(shí)碼存在的充要條件是：說(shuō)明：給定碼字個(gè)數(shù)，碼符號(hào)集中的符號(hào)個(gè)數(shù),各碼字的碼元長(zhǎng)度，滿足Kraft（克拉夫特）不等式的構(gòu)成一類碼，這類碼中一定至少有一個(gè)是即時(shí)碼，但并不是該類碼中的每個(gè)碼都是即時(shí)碼。即時(shí)碼一定滿足Kraft不等式，但反過(guò)來(lái)則不一定。實(shí)例：僅舉一反例即可。有如下碼字：由于是的前綴，為非即時(shí)碼。但代入，得：，滿足Kraft不等式。另外：Kraft不等式同樣適用于唯一可譯碼的判別。50信源編碼（主要內(nèi)容）信源編碼定理（定長(zhǎng)、變長(zhǎng)編碼定理）信源編碼的相關(guān)概念：定長(zhǎng)編碼定理變長(zhǎng)編碼定理（香農(nóng)第一定理）香農(nóng)第三定理信源編碼方法離散信源編碼連續(xù)信源編碼相關(guān)信源編碼變換編碼2024/3/2051變長(zhǎng)編碼的必要性及付出代價(jià)變長(zhǎng)碼唯一可譯碼的條件變長(zhǎng)信源編碼定理對(duì)同一信源，用同一碼符號(hào)集編成的即時(shí)碼或唯一可譯碼可能有很多種。從高效傳輸信息的角度出發(fā)，當(dāng)然是希望尋找平均碼長(zhǎng)最短的編碼。平均碼長(zhǎng)：碼符號(hào)/信源符號(hào)

緊致碼的定義52因?yàn)槭俏ㄒ豢勺g碼，信源符號(hào)xi和碼字Wi是一一對(duì)應(yīng)的緊致碼:對(duì)于給定的信源和碼符號(hào)集，若存在一個(gè)唯一可譯碼，其平均碼長(zhǎng)小于所有其它唯一可譯碼的平均碼長(zhǎng)，則稱為緊致碼。（最佳碼）經(jīng)信源編碼后，平均每個(gè)碼符號(hào)所攜帶的信息量。單位：比特/碼符號(hào)如何計(jì)算？碼符號(hào)/信源符號(hào)比特/信源符號(hào)信息傳輸率和信息傳輸速率53信息傳輸速率：?jiǎn)挝粫r(shí)間傳輸?shù)男畔⒘俊＃ㄔO(shè):傳輸一個(gè)碼符號(hào)平均需要t秒）Rt越大，信息傳輸率就越高。信源熵H(X)是確定的，因此，提高信息傳輸率的方法是使平均碼長(zhǎng)最短。比特/秒信息傳輸率若單符號(hào)信源的熵為,碼符號(hào)集中的符號(hào)個(gè)數(shù)為,則總可以找到一種無(wú)失真編碼方法，構(gòu)成唯一可譯碼，使其平均碼長(zhǎng)滿足：即：?jiǎn)畏?hào)信源的變長(zhǎng)編碼定理54問(wèn)題：何時(shí)能取到最小的

（即上式左邊取等號(hào)）回答：要求。實(shí)例：對(duì)二元碼，要求所有消息的概率必須是只有在上述條件下，唯一可譯碼的平均碼長(zhǎng)才能達(dá)到下限值，而且可以保證所編得的碼一定為緊致碼。

必須為整數(shù)例

對(duì)編二元緊致碼。解：算出各碼字的碼長(zhǎng)，再利用碼樹(shù)圖法進(jìn)行構(gòu)造。(1)計(jì)算各碼字碼長(zhǎng)(2)利用碼樹(shù)圖法構(gòu)造驗(yàn)證上述碼為緊致碼：唯一可譯碼的碼長(zhǎng)下限：平均碼長(zhǎng):55若次擴(kuò)展信源的熵為,碼符號(hào)集中的符號(hào)個(gè)數(shù)為，對(duì)信源進(jìn)行編碼，總可以找到一種無(wú)失真編碼方法，構(gòu)成唯一可譯碼，使其平均碼長(zhǎng)滿足：?jiǎn)畏?hào)信源

次擴(kuò)展信源無(wú)記憶信源次擴(kuò)展信源的變長(zhǎng)編碼定理56是每個(gè)所對(duì)應(yīng)的平均碼長(zhǎng)與單符號(hào)信源進(jìn)行比較：趨于更短

特別地，當(dāng)時(shí)：所得碼一定是極致碼。57離散無(wú)記憶信源X中每個(gè)信源符號(hào)xi所對(duì)應(yīng)的平均碼長(zhǎng)變長(zhǎng)無(wú)失真信源編碼定理說(shuō)明，只要編碼后的碼符號(hào)序列所能攜帶的信息量不小于信源本身的信息量,就可以實(shí)現(xiàn)唯一可譯碼。

單符號(hào)信源編碼效率：編碼后平均每個(gè)信源符號(hào)的最大可能載信量要求平均每個(gè)信源符號(hào)攜帶的實(shí)際信息量可用來(lái)估算，為達(dá)到效率，所需要的信源符號(hào)序列長(zhǎng)度。擴(kuò)展信源*【分母變大，結(jié)果變小】58例要求編碼效率,對(duì)二元變長(zhǎng)編碼,求需要的信源序列長(zhǎng)度。解：代入：比特/符號(hào)計(jì)算得：比較：定長(zhǎng)編碼問(wèn)題：為什么變長(zhǎng)編碼可做到完全無(wú)失真編碼？回答：因?yàn)樽冮L(zhǎng)編碼可保證信源符號(hào)序列和碼符號(hào)序列一一對(duì)應(yīng)。59對(duì)變長(zhǎng)編碼定理應(yīng)用范圍的說(shuō)明：60雖然變