信息理論與編碼第5章

1、信息論與編碼信息論與編碼Information Theory & Coding第第5章章無(wú)失真信源編碼無(wú)失真信源編碼1.1.信源編碼的概念；信源編碼的概念；2.2.變長(zhǎng)碼的分類與主要編碼方法；變長(zhǎng)碼的分類與主要編碼方法；3.3.惟一可譯碼的判別準(zhǔn)則；惟一可譯碼的判別準(zhǔn)則；4 4.Huffman編碼編碼信源編碼一直是信息論研究的一個(gè)重要方向。信源編信源編碼一直是信息論研究的一個(gè)重要方向。信源編碼是通過(guò)壓縮編碼來(lái)去掉信號(hào)源中的冗余成分，提高信息碼是通過(guò)壓縮編碼來(lái)去掉信號(hào)源中的冗余成分，提高信息傳輸?shù)挠行?。傳輸?shù)挠行浴１菊碌闹攸c(diǎn)本章的重點(diǎn)1信源符號(hào)集信源符號(hào)集信源發(fā)出的符號(hào)消息的集合，記為信源發(fā)

2、出的符號(hào)消息的集合，記為S；設(shè)；設(shè)S 有有q個(gè)符號(hào)：個(gè)符號(hào)： S=s1,s2,sq5.1 5.1 信源編碼器信源編碼器信信源源編碼器編碼器信信 道道 碼碼 表表 1.信源的符號(hào)集和符號(hào)序列信源的符號(hào)集和符號(hào)序列2信源信源符號(hào)序列符號(hào)序列:由由信源符號(hào)集合信源符號(hào)集合S 中中符號(hào)符號(hào)的的N 次擴(kuò)展次擴(kuò)展組成長(zhǎng)度為組成長(zhǎng)度為N 的的符號(hào)序列符號(hào)序列，符號(hào)序列的集合符號(hào)序列的集合記為記為S N ； N 信源信源符號(hào)序列符號(hào)序列長(zhǎng)；長(zhǎng)；qN 符號(hào)序列個(gè)數(shù)符號(hào)序列個(gè)數(shù)信道可傳輸?shù)幕痉?hào)的集合信道可傳輸?shù)幕痉?hào)的集合,記為記為X，X有有r個(gè)符號(hào)，個(gè)符號(hào)， X=x1,x2,xr 其中其中xi 稱為碼元或

3、碼符。稱為碼元或碼符。2.碼元和碼字碼元和碼字1碼元碼元(符符)集集 r 元信道元信道：可傳輸：可傳輸r 個(gè)基本符號(hào)的信道；個(gè)基本符號(hào)的信道；二元信道二元信道：可傳輸可傳輸2個(gè)基本符號(hào)的信道。這是一種最常用個(gè)基本符號(hào)的信道。這是一種最常用的信道，其基本符號(hào)常用的信道，其基本符號(hào)常用0,1表示。表示。由碼元組成的序列稱為碼字，記為由碼元組成的序列稱為碼字，記為Wi Wi=(xi1,xi2,xil )碼字碼字W i 中的碼元個(gè)數(shù)中的碼元個(gè)數(shù)l i 稱為稱為Wi的碼長(zhǎng)的碼長(zhǎng).定長(zhǎng)碼定長(zhǎng)碼：所有碼字：所有碼字W i 的碼長(zhǎng)的碼長(zhǎng)l i 均相等，稱為碼長(zhǎng)為均相等，稱為碼長(zhǎng)為l 定長(zhǎng)碼定長(zhǎng)碼.2碼字碼字:

4、變長(zhǎng)碼變長(zhǎng)碼：碼字：碼字W i 的碼長(zhǎng)的碼長(zhǎng)l i 不全相等稱為變長(zhǎng)碼不全相等稱為變長(zhǎng)碼.例例S=s1,s2,s3,s4,s5基本符號(hào)用基本符號(hào)用0,1s1000，s2001，s3010，s4011，s51001信源編碼：信源編碼：將將信源符號(hào)信源符號(hào)si 或或符號(hào)序列符號(hào)序列SNi 按一種按一種規(guī)則規(guī)則映像成映像成碼字碼字W i的過(guò)程。的過(guò)程。2無(wú)失真編碼：無(wú)失真編碼：信源符號(hào)到碼字的映射必須一一對(duì)應(yīng)。信源符號(hào)到碼字的映射必須一一對(duì)應(yīng)。3譯碼：譯碼：從碼符號(hào)到信源符號(hào)的映射。從碼符號(hào)到信源符號(hào)的映射。4碼表：碼表：所有映射規(guī)則的集合所有映射規(guī)則的集合.3.3.編碼與譯碼編碼與譯碼1許用碼字：

5、許用碼字：信源的符號(hào)信源的符號(hào)si 或符號(hào)序列或符號(hào)序列SNi與碼字與碼字Wi定定義了義了對(duì)應(yīng)關(guān)系對(duì)應(yīng)關(guān)系的碼字。的碼字。2禁用碼字：禁用碼字：信源的符號(hào)信源的符號(hào)si 或符號(hào)序列或符號(hào)序列SNi 與碼字與碼字Wi 未未定義定義對(duì)應(yīng)關(guān)系對(duì)應(yīng)關(guān)系的碼字。的碼字。3許用碼字的全體稱為許用碼字的全體稱為碼集，記為碼集，記為C=W1,W2,。4.4.許用碼和禁用碼許用碼和禁用碼5.5.碼符序列碼符序列 按順序發(fā)送一系列表示信源消息符號(hào)的碼字構(gòu)成的按順序發(fā)送一系列表示信源消息符號(hào)的碼字構(gòu)成的碼符串稱為碼符串稱為碼符序列碼符序列。1.1.奇異性奇異性定義定義若若不同的信源符號(hào)不同的信源符號(hào)或符號(hào)序列或符號(hào)

6、序列對(duì)應(yīng)的對(duì)應(yīng)的分組碼分組碼碼字是互碼字是互 不相同的，則該不相同的，則該分組碼為分組碼為非奇異碼非奇異碼；否則稱；否則稱奇異碼奇異碼。5.2 5.2 分組碼（塊碼）分組碼（塊碼）定義定義將信將信源符號(hào)源符號(hào)si 或或符號(hào)序列符號(hào)序列SNi 按一種規(guī)則映射成碼長(zhǎng)按一種規(guī)則映射成碼長(zhǎng)為為有限長(zhǎng)度的碼字有限長(zhǎng)度的碼字W i的稱為的稱為分組碼分組碼。注意注意：分組碼為分組碼為非非奇異奇異的是正確譯碼的的是正確譯碼的必要條件必要條件，但，但分組分組碼形成碼形成碼序列碼序列(或或碼流碼流)后后不能保證正確譯碼。不能保證正確譯碼。例例分組碼為分組碼為:s11s210s311若傳送消息若傳送消息s3s2s1

7、，形成，形成碼流碼流為為11101譯碼時(shí)，譯碼時(shí)，可可分割分割為為11，10，1，但但也可也可分割分割為為1，1，10，1，無(wú)法無(wú)法唯一分割。唯一分割。2.2.唯一可譯性唯一可譯性定義定義2若若一個(gè)一個(gè)分組碼的任意一串分組碼的任意一串有限長(zhǎng)碼序列有限長(zhǎng)碼序列，只能唯一只能唯一 地分割一個(gè)個(gè)的碼字，地分割一個(gè)個(gè)的碼字，則稱為則稱為唯一可譯碼唯一可譯碼。例例分組碼為分組碼為:s11s210s311s1s111，s311，s1s1與與s3不是一一對(duì)應(yīng)的。不是一一對(duì)應(yīng)的。唯一可譯碼唯一可譯碼又稱為又稱為單義碼單義碼。非非唯一可譯碼對(duì)有限長(zhǎng)碼流，不能唯一地分割一個(gè)個(gè)唯一可譯碼對(duì)有限長(zhǎng)碼流，不能唯一地分割

8、一個(gè)個(gè)的碼字。唯一可譯碼在傳輸過(guò)程中不需要的碼字。唯一可譯碼在傳輸過(guò)程中不需要同步碼同步碼。 非奇異定長(zhǎng)碼非奇異定長(zhǎng)碼是唯一可譯碼是唯一可譯碼s2s3s110111.s2s1s1s1s2s1s3定義定義在在分組碼形成碼序列中，一個(gè)完整的碼字接收到后，分組碼形成碼序列中，一個(gè)完整的碼字接收到后，無(wú)需等到接收下一個(gè)碼字，就能立即譯碼，稱為無(wú)需等到接收下一個(gè)碼字，就能立即譯碼，稱為即即時(shí)碼。時(shí)碼。3.3.即時(shí)性即時(shí)性異前綴碼異前綴碼(即時(shí)碼即時(shí)碼)指的是碼集任何一個(gè)碼不能是其他指的是碼集任何一個(gè)碼不能是其他碼的前綴。碼的前綴。即時(shí)碼即時(shí)碼又稱為又稱為非延長(zhǎng)碼非延長(zhǎng)碼、異前綴碼異前綴碼或或逗點(diǎn)碼逗點(diǎn)碼

9、。非即時(shí)碼收到一個(gè)完整的碼字后，不能立即譯碼；還非即時(shí)碼收到一個(gè)完整的碼字后，不能立即譯碼；還需要等到下一個(gè)碼字開(kāi)始接收后才能判斷是否可以譯碼。需要等到下一個(gè)碼字開(kāi)始接收后才能判斷是否可以譯碼。4.4.有實(shí)用價(jià)值的分組碼有實(shí)用價(jià)值的分組碼 分組碼是分組碼是非奇異碼，且是唯一可譯碼、且是即時(shí)碼。非奇異碼，且是唯一可譯碼、且是即時(shí)碼。例例即時(shí)碼：即時(shí)碼：s10s210s311碼流：碼流：1001110（s2s1s3s2）碼流分割：碼流分割：10，0，11，10，非即時(shí)碼：非即時(shí)碼：s10s210s301碼流：碼流：1000110（s2s1s3s2）碼流分割：碼流分割：10，0？，？，01，10，即

10、時(shí)碼必定是唯一可譯碼，反之則不一定。即時(shí)碼必定是唯一可譯碼，反之則不一定。5.5.碼樹(shù)圖碼樹(shù)圖用碼樹(shù)來(lái)描述給定碼集各碼字的圖形。用碼樹(shù)來(lái)描述給定碼集各碼字的圖形。1碼樹(shù)圖有樹(shù)根、樹(shù)枝、節(jié)點(diǎn)組成。碼樹(shù)圖有樹(shù)根、樹(shù)枝、節(jié)點(diǎn)組成。2樹(shù)根：碼樹(shù)圖最頂部的節(jié)點(diǎn)；樹(shù)根：碼樹(shù)圖最頂部的節(jié)點(diǎn)；3節(jié)點(diǎn)：有中間節(jié)點(diǎn)、終端節(jié)點(diǎn)；節(jié)點(diǎn)：有中間節(jié)點(diǎn)、終端節(jié)點(diǎn)；中間節(jié)點(diǎn)有一級(jí)節(jié)點(diǎn)、二級(jí)節(jié)點(diǎn)中間節(jié)點(diǎn)有一級(jí)節(jié)點(diǎn)、二級(jí)節(jié)點(diǎn)用用表示；表示；終端節(jié)點(diǎn)用終端節(jié)點(diǎn)用表示；表示；4每個(gè)節(jié)點(diǎn)上的樹(shù)枝數(shù)與每個(gè)節(jié)點(diǎn)上的樹(shù)枝數(shù)與分組分組碼的碼符的個(gè)數(shù)相同；碼的碼符的個(gè)數(shù)相同；5r 個(gè)碼符的個(gè)碼符的分組分組碼可用碼可用r 進(jìn)制碼樹(shù)圖表示。進(jìn)制碼樹(shù)

11、圖表示。例例1s11s201s3001例例3s100s210s311s4010s50111 1）二元（進(jìn)制）碼樹(shù)）二元（進(jìn)制）碼樹(shù)A010011s1s2s3101s1s2s3A例例2s11s210s311A010011s1s2s3s4s5102 2）用碼樹(shù)圖構(gòu)造碼）用碼樹(shù)圖構(gòu)造碼 在樹(shù)的生長(zhǎng)過(guò)程中，節(jié)點(diǎn)生出樹(shù)枝，各樹(shù)枝旁標(biāo)出相在樹(shù)的生長(zhǎng)過(guò)程中，節(jié)點(diǎn)生出樹(shù)枝，各樹(shù)枝旁標(biāo)出相應(yīng)的碼應(yīng)的碼符符，為了清晰起見(jiàn)相同碼，為了清晰起見(jiàn)相同碼符符的樹(shù)枝方向相同，終端的樹(shù)枝方向相同，終端節(jié)點(diǎn)節(jié)點(diǎn)表示信源符號(hào)表示信源符號(hào)，從樹(shù)根到終端節(jié)點(diǎn)所經(jīng)過(guò)的樹(shù)枝旁從樹(shù)根到終端節(jié)點(diǎn)所經(jīng)過(guò)的樹(shù)枝旁的碼的碼符符按經(jīng)過(guò)的順序組成的序

12、列構(gòu)成碼字按經(jīng)過(guò)的順序組成的序列構(gòu)成碼字。3 3）用碼樹(shù)圖判斷）用碼樹(shù)圖判斷即時(shí)碼即時(shí)碼 如果表示信源符號(hào)的如果表示信源符號(hào)的終端節(jié)點(diǎn)不再延伸終端節(jié)點(diǎn)不再延伸，或，或到達(dá)到達(dá)任一任一信源符號(hào)信源符號(hào)終端節(jié)點(diǎn)的路徑終端節(jié)點(diǎn)的路徑不經(jīng)過(guò)不經(jīng)過(guò)其它的終端節(jié)點(diǎn)其它的終端節(jié)點(diǎn)，這樣構(gòu)，這樣構(gòu)造的碼滿足造的碼滿足即時(shí)碼即時(shí)碼條件條件. .定義定義所有碼字所有碼字Wi 的碼長(zhǎng)的碼長(zhǎng)li 均相等稱為碼長(zhǎng)為均相等稱為碼長(zhǎng)為l 定長(zhǎng)碼。定長(zhǎng)碼。例例用二元碼符用二元碼符0,1對(duì)對(duì)簡(jiǎn)單簡(jiǎn)單信源信源5.3 5.3 定長(zhǎng)碼定長(zhǎng)碼1.1.定長(zhǎng)碼定長(zhǎng)碼1S=s1,s2s10，s212S=s1,s2,s3s100，s201，s

13、3103S=s1,s2,s3,s4s100，s201，s310，s4114S=s1,s2,s3,s4,s5s1000，s2001，s3010，s4011，s5100對(duì)于信源對(duì)于信源S，定長(zhǎng)碼存在，定長(zhǎng)碼存在唯一可譯碼唯一可譯碼的條件是的條件是lrq 其中：其中：q 為信源為信源S 的信源符號(hào)個(gè)數(shù)；的信源符號(hào)個(gè)數(shù)；r 為碼符號(hào)的個(gè)數(shù)；為碼符號(hào)的個(gè)數(shù)； l 為定長(zhǎng)碼的碼長(zhǎng)。為定長(zhǎng)碼的碼長(zhǎng)。qlrlog2.2.信息傳輸率信息傳輸率 定義定義 平均一個(gè)碼符所攜帶的平均信息量稱為信息傳輸平均一個(gè)碼符所攜帶的平均信息量稱為信息傳輸率，記作率，記作R，（單位：，（單位：bit/碼符）碼符）lSHR)( 或或

14、定長(zhǎng)編碼的缺陷是定長(zhǎng)編碼的缺陷是信息傳輸率低。信息傳輸率低。5.4 5.4 變長(zhǎng)碼變長(zhǎng)碼5.4.1 5.4.1 信源編碼的三種主要方法信源編碼的三種主要方法1.1.匹配編碼匹配編碼最最佳佳碼碼能載荷一定信息量能載荷一定信息量,且碼字的平均碼長(zhǎng)最短，且碼字的平均碼長(zhǎng)最短，可即時(shí)、惟一分離的碼字集合?？杉磿r(shí)、惟一分離的碼字集合。編碼思路編碼思路對(duì)概率大的信息符號(hào)編以短碼對(duì)概率大的信息符號(hào)編以短碼，對(duì)概率小的，對(duì)概率小的信息符號(hào)編以長(zhǎng)碼。信息符號(hào)編以長(zhǎng)碼。這種編碼方法稱為統(tǒng)計(jì)編碼、熵編碼或概率匹配編碼。這種編碼方法稱為統(tǒng)計(jì)編碼、熵編碼或概率匹配編碼。2.2.變換編碼變換編碼3.3.識(shí)別編碼識(shí)別編碼唯

15、一可譯碼存在定理唯一可譯碼存在定理設(shè)信源符號(hào)的個(gè)數(shù)為設(shè)信源符號(hào)的個(gè)數(shù)為q ，碼符的個(gè)數(shù)為，碼符的個(gè)數(shù)為r ，信源各符，信源各符號(hào)對(duì)應(yīng)碼字的碼長(zhǎng)為號(hào)對(duì)應(yīng)碼字的碼長(zhǎng)為li (i=1,2,q)則唯一可譯碼則唯一可譯碼存在存在的的充分和必要條件充分和必要條件是滿足是滿足Kraft不等式不等式:11 qilir5.4.2 5.4.2 唯一可譯碼存在的條件唯一可譯碼存在的條件Kraft不等式是一個(gè)存在定理，不是唯一可譯碼的判定不等式是一個(gè)存在定理，不是唯一可譯碼的判定定理。定理。碼長(zhǎng)碼長(zhǎng)li 滿足滿足Kraft不等式不一定是唯一可譯碼不等式不一定是唯一可譯碼。注意注意：如果是唯一可譯碼如果是唯一可譯碼,則

16、則q、r、li 必須必須滿足滿足Kraft不等式。不等式。如果如果q、r、li 滿足滿足Kraft不等式，則不等式，則存在存在唯一可譯碼；唯一可譯碼； )()()()(2121qqspspspsssSpS qiiilspL1)(5.4.4 5.4.4 變長(zhǎng)編碼定理變長(zhǎng)編碼定理定義定義設(shè)有信源設(shè)有信源1) 1) 平均碼長(zhǎng)的定義平均碼長(zhǎng)的定義1.1.平均碼長(zhǎng)平均碼長(zhǎng)信源符號(hào)信源符號(hào)si編碼后對(duì)應(yīng)的碼字為編碼后對(duì)應(yīng)的碼字為Wi(i=1,2,q )，碼字碼字Wi 對(duì)應(yīng)的碼長(zhǎng)為對(duì)應(yīng)的碼長(zhǎng)為l i ( i=1,2,q)。碼符碼符/信源符號(hào)信源符號(hào)單符號(hào)信源對(duì)應(yīng)的變長(zhǎng)碼的平均碼長(zhǎng)為單符號(hào)信源對(duì)應(yīng)的變長(zhǎng)碼的平

17、均碼長(zhǎng)為信源符號(hào)序列信源符號(hào)序列SiN對(duì)應(yīng)的碼字為對(duì)應(yīng)的碼字為Wi(i=1,2,qN)；碼字碼字Wi 對(duì)應(yīng)的碼長(zhǎng)為對(duì)應(yīng)的碼長(zhǎng)為l i (i=1,2,qN) )()()()(2121NqNNNNqNNNNNSpSpSpSSSSpS NqiiNiNlSpL1)(NLNL1 碼符碼符/信源符號(hào)信源符號(hào)單個(gè)符號(hào)單個(gè)符號(hào)對(duì)應(yīng)的對(duì)應(yīng)的平均碼長(zhǎng)平均碼長(zhǎng)碼符碼符/信源符號(hào)序列信源符號(hào)序列符號(hào)序列符號(hào)序列對(duì)應(yīng)對(duì)應(yīng)變長(zhǎng)碼的平均碼長(zhǎng)變長(zhǎng)碼的平均碼長(zhǎng)定義定義符號(hào)序列信源空間符號(hào)序列信源空間SN其中其中SN 是是S 的的N 次擴(kuò)展。次擴(kuò)展。2) 2) 信息傳輸率信息傳輸率定義定義 平均一個(gè)碼符所攜帶的平均信息量稱為稱為

18、平均一個(gè)碼符所攜帶的平均信息量稱為稱為信息傳輸信息傳輸率率，記作，記作R，（單位：，（單位：bit/碼符）碼符）LSHR)( tLSHtRRt)( 匹配編碼匹配編碼或或熵編碼熵編碼核心是如何獲得核心是如何獲得平均碼長(zhǎng)最短的碼平均碼長(zhǎng)最短的碼。因此，當(dāng)信源概率空間確定后，信源編碼的平均碼長(zhǎng)因此，當(dāng)信源概率空間確定后，信源編碼的平均碼長(zhǎng)最短時(shí)，信息傳輸率就越大。最短時(shí)，信息傳輸率就越大。如果信道如果信道傳輸一個(gè)碼符平均需要傳輸一個(gè)碼符平均需要t 秒秒，則編碼后信道，則編碼后信道每秒傳輸?shù)男畔⒘繛槊棵雮鬏數(shù)男畔⒘繛樾畔鬏斔俾市畔鬏斔俾世旁锤怕士臻g信源概率空間 818141214321ssss

19、PS若用二元碼符若用二元碼符0,1對(duì)上述信源編碼，信源符號(hào)個(gè)數(shù)對(duì)上述信源編碼，信源符號(hào)個(gè)數(shù)為為q=4，碼符個(gè)數(shù)為，碼符個(gè)數(shù)為r=2，H(S)=- - (1/2log1/2+1/4log1/4+1/8log1/8+1/8log1/8)=1.75bit/符號(hào)符號(hào)信源各符號(hào)對(duì)應(yīng)的碼長(zhǎng)為信源各符號(hào)對(duì)應(yīng)的碼長(zhǎng)為li ，且應(yīng)滿足，且應(yīng)滿足Kraft不等式。不等式。令令l1=1,l2=2,l3=3,l4=32-1+2-2+2-3+2-3=1滿足滿足Kraft不等式不等式信息傳輸率信息傳輸率R =1.75/1.75=1bit/碼符碼符變長(zhǎng)碼方案變長(zhǎng)碼方案1 1碼字：碼字： s1W1=0,s2W2=10s3W3

20、=110s4W4=111平均碼長(zhǎng)：平均碼長(zhǎng)：381381241121 L 1.75碼符碼符/信源符號(hào)信源符號(hào)令令l1=3,l2=3,l3=2,l4=12-3+2-3+2-2+2-1=1滿足滿足Kraft不等式不等式信息傳輸率信息傳輸率R =1.75/2.625=0.667bit/碼符碼符變長(zhǎng)碼方案變長(zhǎng)碼方案2 2碼字：碼字： s1W1=111s2W2=110s3W3=10s4W4=0平均碼長(zhǎng)：平均碼長(zhǎng)：181281341321 L 2.625碼符碼符/信源符號(hào)信源符號(hào)顯然，變長(zhǎng)碼方案顯然，變長(zhǎng)碼方案2信息傳輸率比變長(zhǎng)碼方案信息傳輸率比變長(zhǎng)碼方案1低。低。定義定義對(duì)于一給定的信源和一給定的碼符集

21、，若有一對(duì)于一給定的信源和一給定的碼符集，若有一惟一惟一可譯碼可譯碼，若，若其平均碼長(zhǎng)其平均碼長(zhǎng)小于小于其它所有惟一可譯碼的其它所有惟一可譯碼的平均碼長(zhǎng)平均碼長(zhǎng)，則這種碼稱為，則這種碼稱為緊致碼緊致碼，或，或最佳碼最佳碼。3)3)最佳碼最佳碼最佳碼的實(shí)現(xiàn)最佳碼的實(shí)現(xiàn)1.最佳碼是惟一可譯碼，必須滿足最佳碼是惟一可譯碼，必須滿足Kraft不等式；不等式；2.最佳碼是即時(shí)碼；最佳碼是即時(shí)碼；3.最佳碼的平均碼長(zhǎng)是最短的。最佳碼的平均碼長(zhǎng)是最短的。定理定理1 1 對(duì)于熵為對(duì)于熵為H(S)的離散無(wú)記憶信源的離散無(wú)記憶信源1log)(log)( rSHLrSH )()()()(2121qqspspspss

22、sSpS 若用有若用有r 個(gè)碼符的集個(gè)碼符的集對(duì)該信源進(jìn)行編碼，則對(duì)該信源進(jìn)行編碼，則一定存在一定存在一種編碼方式一種編碼方式構(gòu)成唯一可譯碼構(gòu)成唯一可譯碼，使其平均碼長(zhǎng)滿足：，使其平均碼長(zhǎng)滿足：4) 4) 平均碼長(zhǎng)的界限平均碼長(zhǎng)的界限證明證明 對(duì)于信源的任一消息符號(hào)對(duì)于信源的任一消息符號(hào)si，應(yīng)如何取所對(duì)應(yīng)碼字的，應(yīng)如何取所對(duì)應(yīng)碼字的的碼長(zhǎng)為的碼長(zhǎng)為li ，設(shè)設(shè)li按如下不等式范圍取，按如下不等式范圍取，若若恰好為整數(shù)，則恰好為整數(shù)，則對(duì)上述不等式各邊乘以對(duì)上述不等式各邊乘以p(si)，因，因p(si) 0，故，故如下不等如下不等式成立，式成立，1log)(loglog)(log rsplrs

23、piii)(log)(log)()(log)(log)(iiiiiiisprspsplsprspsp rspilog)(log rspliilog)(log 對(duì)上述不等式求和，有對(duì)上述不等式求和，有 qiiiqiiqiiiiqiisprspsplsprspsp1111)(log)(log)()(log)(log)(1)(,)(,log)(log)(log)(111 qiiqiiiiqiispLlsprSHrspsp因因故可得故可得1log)(log)( rSHLrSH以上獲得平均碼長(zhǎng)的界限，但是否為以上獲得平均碼長(zhǎng)的界限，但是否為唯一可譯碼？唯一可譯碼？此定理給出了唯一可譯碼平均碼長(zhǎng)的下限和上

24、限，此定理給出了唯一可譯碼平均碼長(zhǎng)的下限和上限，但但未給出未給出如何構(gòu)造如何構(gòu)造唯一可譯碼，唯一可譯碼，是否為是否為即時(shí)碼即時(shí)碼。)(logloglog)(logiiiisprlrspl)(loglog)(loglogiliisprsprli 1)()(11 qiiqililsprsprii又因?yàn)橛忠驗(yàn)樗杂兴杂幸虼?，所有碼字長(zhǎng)度滿足因此，所有碼字長(zhǎng)度滿足Kraft不等式，則不等式，則一定存在一定存在一種編碼方式構(gòu)成唯一可譯碼。一種編碼方式構(gòu)成唯一可譯碼。定理定理 對(duì)于熵為對(duì)于熵為H(S)的離散無(wú)記憶信源的離散無(wú)記憶信源 )()()()(2121qqspspspsssSpS )()()()(

25、2121NqNNNqNNNNNNSpSpSpSSSSpS)(1)(NSHNSH H(SN)的單位：的單位：bit/N個(gè)信源符號(hào)；個(gè)信源符號(hào)；S 的的N 次擴(kuò)展為次擴(kuò)展為2.2.變長(zhǎng)無(wú)失真信源編碼定理變長(zhǎng)無(wú)失真信源編碼定理Shannon第一定理第一定理SN 為為離散平穩(wěn)無(wú)記憶序列，其離散平穩(wěn)無(wú)記憶序列，其熵為熵為H(SN)；因此因此碼符集合碼符集合X=x1,x2,xr 。對(duì)信源。對(duì)信源SN 進(jìn)行編碼，必進(jìn)行編碼，必有一種方法，使其構(gòu)成惟一可譯碼，有一種方法，使其構(gòu)成惟一可譯碼，且使得信源的每個(gè)符且使得信源的每個(gè)符號(hào)所需的平均碼長(zhǎng)滿足如下不等式號(hào)所需的平均碼長(zhǎng)滿足如下不等式1log)(log)(

26、rSHLrSHNNNNrNSHNLrNSHNNN1log)(log)( NrSHNLrSHN1log)(log)( 證明證明 將將 SN 視為視為一個(gè)新的信源，一個(gè)新的信源，對(duì)上述不等式各邊除以對(duì)上述不等式各邊除以N，有，有rSHNLLlog)( NLLSHNSHNN ,)(1)(NrSHNLrSHN1log)(log)( NrSHrNLSHNlog)(log)( )(log)(SHrNLSHN或或因?yàn)橐驗(yàn)樗运援?dāng)當(dāng)N時(shí)時(shí)將以上將以上不等式各邊乘以不等式各邊乘以logr，有，有結(jié)論結(jié)論：采用擴(kuò)展信源編碼，當(dāng)：采用擴(kuò)展信源編碼，當(dāng)N 足夠大時(shí)可使平均碼長(zhǎng)足夠大時(shí)可使平均碼長(zhǎng)接近下限。接近下限。

27、3.3.編碼信息率編碼信息率 )(log)(SHrNLSHN根據(jù)根據(jù)信源熵信源熵rLrNLSHNloglog)( NLLN 和和LSHR)( 對(duì)信源對(duì)信源SN 進(jìn)行變長(zhǎng)編碼后，平均到進(jìn)行變長(zhǎng)編碼后，平均到單個(gè)符號(hào)單個(gè)符號(hào)的平均的平均碼長(zhǎng)攜帶的碼長(zhǎng)攜帶的信息量信息量稱為稱為編碼信息率，記為編碼信息率，記為RrLSHlog)( 無(wú)噪信道的輸入和輸出是一一對(duì)應(yīng)的，其信道矩陣的無(wú)噪信道的輸入和輸出是一一對(duì)應(yīng)的，其信道矩陣的特征是為單位矩陣。特征是為單位矩陣。rXHYXICiixPxPlog)(max);(max)()( 對(duì)于有對(duì)于有r個(gè)輸出個(gè)輸出(輸入輸入)符號(hào)符號(hào)的的無(wú)噪信道無(wú)噪信道的信道容量為的信

28、道容量為對(duì)于無(wú)噪信道，通過(guò)信源編碼，使對(duì)于無(wú)噪信道，通過(guò)信源編碼，使Rlogr，減少，減少信源剩余度，使信源剩余度，使信息傳輸率盡可能接近信道容量。信息傳輸率盡可能接近信道容量。因此，因此，無(wú)失真信源編碼定理無(wú)失真信源編碼定理通常稱為通常稱為無(wú)噪信道編碼定理無(wú)噪信道編碼定理。定義定義 對(duì)信源對(duì)信源SN 進(jìn)行變長(zhǎng)編碼后，平均一個(gè)信源符號(hào)能進(jìn)行變長(zhǎng)編碼后，平均一個(gè)信源符號(hào)能攜帶的攜帶的最大信息量最大信息量稱為稱為編碼率編碼率，記作，記作Rs，rLrNLRNSloglog LNLRNS (單位單位:bit/符號(hào)符號(hào))對(duì)于對(duì)于二元碼符，二元碼符，r2，有，有l(wèi)og2r1，則，則 )()(SHRSHSS

29、hannon第一定理第一定理也可以描述為，若也可以描述為，若則存在惟一可譯碼，若則存在惟一可譯碼，若H(S)Rs 則不存在惟一可譯碼。則不存在惟一可譯碼。 定義定義 編碼效率編碼效率定義為定義為rLSHRSHslog)()( LSH)( 1定義定義 對(duì)于變長(zhǎng)對(duì)于變長(zhǎng)碼，定義碼的碼，定義碼的剩余度剩余度為為注意注意：對(duì)于：對(duì)于r2時(shí)時(shí)編碼效率編碼效率 是小于或等于是小于或等于1的的無(wú)量綱的數(shù)無(wú)量綱的數(shù)4.編碼效率與編碼剩余度編碼效率與編碼剩余度在數(shù)量上在數(shù)量上R 例例無(wú)離散記憶信源無(wú)離散記憶信源 414321ssPSs1s1s1s2s2s1s2s2Wi00011011信源熵信源熵H(S)=0.8

30、11bit/符號(hào)符號(hào)定長(zhǎng)碼定長(zhǎng)碼s10，s21L =1編碼效率編碼效率=H(S)/L=0.811N=2S2s1s1s1s2s2s1s2s2 p(S2)9/163/163/161/16H(S2)=1.622bit/2個(gè)符號(hào)個(gè)符號(hào)H(S)=0.811bit/符號(hào)符號(hào)定長(zhǎng)碼定長(zhǎng)碼L2 =2碼符碼符/2個(gè)信源符號(hào)個(gè)信源符號(hào)編碼效率編碼效率 =H(S2)/L2 =H(S)/L =0.811bit/符號(hào)符號(hào)s1s1s1s2s2s1s2s2p(S2)9/163/163/161/16Wi 010110111li 1233162731613163216311692 L961. 02732811. 0)( LSH

31、 322722 LL變長(zhǎng)碼變長(zhǎng)碼碼符碼符/2個(gè)信源符號(hào)個(gè)信源符號(hào)=0.844碼符碼符/信源符號(hào)信源符號(hào)編碼效率編碼效率H(S)=0.811bit/符號(hào)符號(hào)若若N=3則則=0.985，若，若N=4則則=0.9911.1.Shannon編碼方法編碼方法若若si 按如下不等式取所對(duì)應(yīng)碼字的碼長(zhǎng)為按如下不等式取所對(duì)應(yīng)碼字的碼長(zhǎng)為l i 1log)(loglog)(log rsplrspiii1)(log)log( iiispls當(dāng)當(dāng)r 等于等于2時(shí)時(shí),logr =15.4.5 5.4.5 變長(zhǎng)碼的編碼方法變長(zhǎng)碼的編碼方法采用擴(kuò)展信源提高編碼效率帶來(lái)的問(wèn)題采用擴(kuò)展信源提高編碼效率帶來(lái)的問(wèn)題1.碼表迅速擴(kuò)

32、大碼表迅速擴(kuò)大2.需求內(nèi)存大需求內(nèi)存大3.譯碼延時(shí)譯碼延時(shí)(1)將信源符號(hào)消息按其出現(xiàn)概率的大小依次排序；將信源符號(hào)消息按其出現(xiàn)概率的大小依次排序；p(s1)p(s2)p(sq)(2)按如下不等式取所對(duì)應(yīng)碼字的碼長(zhǎng)為按如下不等式取所對(duì)應(yīng)碼字的碼長(zhǎng)為li ；1)(log)(logiiisplsp 11)(ikkispP(3)計(jì)算第個(gè)計(jì)算第個(gè)i 消息的累加概率消息的累加概率,以便獲得唯一可譯碼以便獲得唯一可譯碼.(4)將累加概率變換為二進(jìn)制數(shù)；將累加概率變換為二進(jìn)制數(shù)；(5)取二進(jìn)制數(shù)的小數(shù)點(diǎn)后取二進(jìn)制數(shù)的小數(shù)點(diǎn)后li 位作為符號(hào)消息的二進(jìn)制碼。位作為符號(hào)消息的二進(jìn)制碼。Shannon編碼過(guò)程編碼

33、過(guò)程Shannon編碼過(guò)程編碼過(guò)程sip(si)I(si)liPiPi二進(jìn)制二進(jìn)制碼字碼字s10.202.32300.0000000s20.192.4030.200.0011001s30.182.4730.390.0110011s40.172.5630.570.1001100s50.152.7430.740.1011101s60.103.3240.890.111001110s70.016.6470.990.111111011111110例例si s1s2s3s4s5s6s7 p(si)0.200.190.180.170.150.100.01信源熵信源熵H(S)=2.61bit/符號(hào)符號(hào)平均碼長(zhǎng)

34、平均碼長(zhǎng)編碼效率編碼效率831. 014. 361. 2)( LSH 符符號(hào)號(hào)碼碼元元/14. 3)(71 iiilsPL2.2.Fano 編碼方法編碼方法(1)將信源符號(hào)消息按其出現(xiàn)概率的大小依次排列；將信源符號(hào)消息按其出現(xiàn)概率的大小依次排列；p(s1)p(s2)p(sq)(2)將依次排列的信源符號(hào)按其概率分為兩大組將依次排列的信源符號(hào)按其概率分為兩大組,使兩個(gè)組使兩個(gè)組的概率之和近似相等的概率之和近似相等,并對(duì)各組賦予一個(gè)碼元并對(duì)各組賦予一個(gè)碼元0和和1；(3)按按(2)方法將每一大組再分為兩組方法將每一大組再分為兩組,各組再賦予一個(gè)碼各組再賦予一個(gè)碼元元0和和1；(4)如此重復(fù)如此重復(fù),

35、直至每個(gè)組只剩一個(gè)信源符號(hào)為止；直至每個(gè)組只剩一個(gè)信源符號(hào)為止；(5)信源符號(hào)所對(duì)應(yīng)的碼字即為信源符號(hào)所對(duì)應(yīng)的碼字即為Fano碼。碼。sip(si)第第1次次 第第2次次 第第3次次 第第4次次碼字碼字碼長(zhǎng)碼長(zhǎng)s10.2000002s20.190100103s30.180110113s40.1710102s50.151101103s60.10111011104s70.01111111114符號(hào)符號(hào)碼元碼元/74. 2)(71 iiilspL前例采用前例采用Fano編碼方法編碼方法平均碼長(zhǎng)平均碼長(zhǎng)編碼效率編碼效率953. 074. 261. 2)( LSH 3.Huffman編碼方法編碼方法(1

36、)將信源符號(hào)消息按其出現(xiàn)概率的大小依次排序；將信源符號(hào)消息按其出現(xiàn)概率的大小依次排序；p(s1)p(s2)p(sq)(2)取兩個(gè)概率最小的符號(hào)分別配以取兩個(gè)概率最小的符號(hào)分別配以0和和1,并將這兩個(gè)概并將這兩個(gè)概率相加作為新字母的概率率相加作為新字母的概率,與未分配的字母重新排序；與未分配的字母重新排序；(3)對(duì)重新排序后的兩個(gè)概率最小的符號(hào)重復(fù)對(duì)重新排序后的兩個(gè)概率最小的符號(hào)重復(fù)(2)的過(guò)程的過(guò)程；(4)不斷重復(fù)上述過(guò)程不斷重復(fù)上述過(guò)程,直至最后兩個(gè)符號(hào)配以直至最后兩個(gè)符號(hào)配以0和和1為止；為止；(5)從最后一級(jí)開(kāi)始從最后一級(jí)開(kāi)始,向前返回到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼向前返回到各個(gè)信源符號(hào)所對(duì)應(yīng)

37、的碼元序列元序列,即為相應(yīng)的即為相應(yīng)的Huffman碼。碼。 s10.200.200.260.350.390.610 s20.190.190.200.260.3500.391 s30.180.180.190.2000.261 s40.170.170.1800.191 s50.150.1500.171 s60.1000.111 s70.011編編 碼碼 過(guò)過(guò) 程程碼字碼字101100000101001100111對(duì)前例采用對(duì)前例采用Huffman編碼方法編碼方法符符號(hào)號(hào)碼碼元元/72. 2)(71 iiilspL960. 072. 261. 2)( LsH 平均碼長(zhǎng)平均碼長(zhǎng)編碼效率編碼效率s p(si)s1