第三章信源編碼離散信源無失真編碼

1、10/23/20211第三章：第三章：信源編碼（一）離散信源無失真編碼3.1 信源及其分類信源及其分類3.2 離散無記憶（簡單）信源的等長編離散無記憶（簡單）信源的等長編碼碼3.3 離散無記憶（簡單）信源的不等長離散無記憶（簡單）信源的不等長編碼編碼3.4 最佳不等長編碼最佳不等長編碼3.5 算術(shù)編碼和算術(shù)編碼和lz編碼編碼10/23/202123.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼（順序地敘述以下的概念）（1）不等長編碼的優(yōu)越性不等長編碼的優(yōu)越性 總體上減少碼字的長度。（2）不等長編碼的特殊問題不等長編碼的特殊問題 唯一可譯性，或者叫做可識別性。對于一個

2、碼，如果存在一種譯碼方法，使任意若干個碼字所組成的字母串只能唯一地被翻譯成這幾個碼字所對應(yīng)的事件序列。這個碼就被稱為是唯一可譯的。解決方案：適當(dāng)?shù)鼐幋a，使得每個碼字都具有識別標(biāo)記。（注解：一個唯一可譯的、碼字長度不超過n的d元碼，其碼字個數(shù)小于d(dn-1)/(d-1)個。這是因為兩個碼字c(1)和c(2) 連接成的字母串c(1)c(2) 不能是碼字）10/23/202133.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼平均碼字長度。設(shè)信源隨機變量u的概率分布為ak, p(ak), k=1k，事件ak對應(yīng)的碼字長度為nk，則平均碼字長度為希望 小。解決方案：概率大的

3、事件用短碼字。實時譯碼和容量限制。kkkkapnn1)(n10/23/202143.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼唯一可譯性的兩種解決方法唯一可譯性的兩種解決方法定義定義3.3.2(p51) 若事件與碼字一一對應(yīng)；每個碼字的開頭部分都是一個相同的字母串；這個字母串僅僅出現(xiàn)在碼字的開頭，不出現(xiàn)在碼字的其它部位，也不出現(xiàn)在兩個碼字的結(jié)合部。則稱這個字母串為逗號，稱此碼為逗點碼逗點碼。定義定義3.3.4(p51) 若事件與碼字一一對應(yīng)；每個碼字都不是另一個碼字的開頭部分（字頭）。則稱此碼為異字頭碼異字頭碼。10/23/202153.3 離散無記憶（簡單）信離

4、散無記憶（簡單）信源的不等長編碼源的不等長編碼注解注解逗點碼顯然是唯一可譯的，識別碼字的方法為：見到逗號就識別為一個碼字的開始。見到逗號就識別為一個碼字的開始。異字頭碼也是唯一可譯的，識別碼字的方法為：見到一個碼字就識別為一個碼字。見到一個碼字就識別為一個碼字。10/23/202163.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼例例 觀察表3.3.1(p51)。碼a不是唯一可譯的。碼b不是唯一可譯的。碼c是唯一可譯的，識別碼字的方法為：見“0”或“111”就是一個碼字的結(jié)束。實際上，碼c是異字頭碼。碼d是唯一可譯的，識別碼字的方法為：見“0”就是一個碼字的開始。實

5、際上，碼d是逗點碼，其中“0”是逗號。碼c不是逗點碼。碼d不是異字頭碼。碼c的平均碼長比碼d的平均碼長小：碼c的平均碼長為10.5+20.25+30.125+30.125=1.75；碼d的平均碼長為10.5+20.25+30.125+40.125=1.875。10/23/202173.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼異字頭碼的第一種構(gòu)造方法：異字頭碼的第一種構(gòu)造方法：shannon-fano編碼法編碼法（d元編碼，字母表為元編碼，字母表為0, 1, , d-1） （1）將源隨機變量的事件按概率從大到小排成一行。（2）將此行切分為d段，分別賦予標(biāo)號“0”到

6、“d-1”，稱為1級標(biāo)號。（3）將每個非空段再切分為d段，分別賦予標(biāo)號“0”到“d-1”，稱為2級標(biāo)號。（4）將每個非空段再切分為d段，分別賦予標(biāo)號“0”到“d-1”，稱為3級標(biāo)號。10/23/202183.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼如此一直到每個段均含有至多一個事件為止。此時，一個事件的碼字就是這個事件所在的段的標(biāo)號序列，從1級標(biāo)號到末級標(biāo)號。為了使平均碼長小，每次切分段時應(yīng)使d段的概率盡可能相近。（注解：當(dāng)然可以把“切分段”操作換為“任意分組”操作，使d組的概率盡可能相近。這樣可以使平均碼長更小。但是，這不是一種有效的操作。 ）10/23/20

7、2193.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼異字頭碼的第二種構(gòu)造方法：異字頭碼的第二種構(gòu)造方法：huffman編碼法編碼法（d元編碼，字母表為元編碼，字母表為0, 1, , d-1）（0）如果源隨機變量的事件的個數(shù)k不是(d-1)的倍數(shù)加1，則添加若干0概率事件使得事件的個數(shù)是(d-1)的倍數(shù)加1 。（1）將概率最小的d個事件分別賦予標(biāo)號“0”到“d-1”。（2）將這d個事件合并為一個事件，其概率為這d個事件概率之和。重復(fù)（1）-（2），直到事件的個數(shù)等于d。將這d個事件分別賦予標(biāo)號“0”到“d-1”。編碼完畢。此時，一個事件的碼字是這個事件從最后標(biāo)號開始

8、到最先標(biāo)號為止的標(biāo)號序列。（當(dāng)然要去掉那些0概率事件和它們的標(biāo)號序列） 10/23/2021103.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼（為什么shannon-fano碼和huffman碼都是異字頭碼？請看p58圖3.4.1，p58圖3.4.2。這些圖都是樹，稱為碼樹，碼樹上的每個碼字都在樹梢。如果不是異字頭碼，則有的碼字就不在樹梢，而在中間節(jié)點。）定理定理3.3.1(kraft不等式，p53) 設(shè)信源隨機變量共有k個事件。則：各碼字長度分別為n1、n2、nk的d元異字頭碼存在的充分必要條件是11kknkd10/23/2021113.3 離散無記憶（簡單）信

9、離散無記憶（簡單）信源的不等長編碼源的不等長編碼證明 不妨設(shè)n1n2nk。則各碼字長度分別為n1、n2、nk的d元異字頭碼存在；當(dāng)且僅當(dāng)：存在這樣一個d叉樹，樹上有n1級、n2級、nk級樹梢；當(dāng)且僅當(dāng)：nk級d叉滿樹滿樹有不存在上下關(guān)系不存在上下關(guān)系的n1級、n2級、nk級節(jié)點；當(dāng)且僅當(dāng)： nk級d叉滿樹滿樹的樹梢數(shù)量不小于;21kkkknnnnnndddknnnddd211當(dāng)且僅當(dāng)：10/23/2021123.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼定理定理3.3.2(p53) （設(shè)信源隨機變量共有k個事件）。則：一個唯一可譯的、各碼字長度分別為n1、n2、n

10、k的d元不等長碼存在的充分必要條件是11kknkd10/23/2021133.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼定理定理3.3.3(p54)duhnlog)(1log)(duhn任一唯一可譯的d元不等長碼總滿足存在唯一可譯的d元不等長碼滿足10/23/2021143.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼證明 設(shè)信源隨機變量u的概率分布為如果唯一可譯的d元不等長碼的碼字長度為則kkqqqaaau212101log) 1(loglnlogloglog1loglog)(111111kknkkknkkkknkkkknkkkkkk

11、kkkkkkkdeqdqeqdqeqdqdnqqqdnuhkknnnaaa212110/23/2021153.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼因此 。另一方面，取n1、n2、nk，則：由于 ，存在碼字長度為 的唯一可譯的d元不等長碼。duhnlog)()log)(1,(duhnkkdqknk，則若kkdqdkknkn1,) 1(111kkkkknqdkkknnnaaa212110/23/2021163.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼但此時dndnqdqqquhkkkkkknkkkkkkloglog) 1(log1

12、log)(11111log)(duhn因此10/23/2021173.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼定理3.3.3的結(jié)論的推廣(p55) 現(xiàn)在對信源隨機向量ul=(u1u2ul)做唯一可譯的d元不等長碼。此時ul的事件的個數(shù)為kl。則任一唯一可譯的d元不等長碼總滿足存在唯一可譯的d元不等長碼滿足dulhduhunlllog)(log)()(1log)(1log)()(dulhduhunll10/23/2021183.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼重新定義平均碼長：任一唯一可譯的d元不等長碼總滿足存在唯一可譯的d

13、元不等長碼滿足duhnlog)(lduhn1log)(lunnl)(10/23/2021193.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長編碼源的不等長編碼定義編碼速率r和編碼效率分別為 任一唯一可譯的d元不等長碼總滿足存在唯一可譯的d元不等長碼滿足dnldunrlloglog)()(uhr lduhrlog)(注解注解 不等長編碼與等長編碼具有相似的性質(zhì)：當(dāng)不等長編碼與等長編碼具有相似的性質(zhì)：當(dāng)l增大時，對增大時，對ul的編的編碼可以使用更短的平均碼長，因而更加節(jié)省碼可以使用更短的平均碼長，因而更加節(jié)省編碼速率。但編碼速率。但節(jié)省節(jié)省編碼編碼速率的下限是速率的下限是h(u)。ruh)(10/23/2021203.3 離散無記憶（簡單）信離散無記憶（簡單）信源的不等長