信源編碼離散信源無失真編碼

《信源編碼離散信源無失真編碼》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第三章：信源編碼（一）離散信源無失真編碼§3.1信源及其分類§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼§3.4最佳不等長(zhǎng)編碼§3.5算術(shù)編碼和LZ編碼2021/9/201§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼（順序地?cái)⑹鲆韵碌母拍睿?）不等長(zhǎng)編碼的優(yōu)越性總體上減少碼字的長(zhǎng)度。（2）不等長(zhǎng)編碼的特殊問題①唯一可譯性，或者叫做可識(shí)別性。對(duì)于一個(gè)碼，如果存在一種譯碼方法，使任意若干個(gè)碼字所組成的字母串只能唯一地被翻譯成這幾個(gè)碼字所對(duì)應(yīng)的事件序列。這個(gè)碼就被稱

2、為是唯一可譯的。解決方案：適當(dāng)?shù)鼐幋a，使得每個(gè)碼字都具有識(shí)別標(biāo)記。（注解：一個(gè)唯一可譯的、碼字長(zhǎng)度不超過N的D元碼，其碼字個(gè)數(shù)小于D(DN-1)/(D-1)個(gè)。這是因?yàn)閮蓚€(gè)碼字c(1)和c(2)連接成的字母串c(1)c(2)不能是碼字）2021/9/202§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼②平均碼字長(zhǎng)度。設(shè)信源隨機(jī)變量U的概率分布為{ak,p(ak),k=1~K}，事件ak對(duì)應(yīng)的碼字長(zhǎng)度為nk，則平均碼字長(zhǎng)度為希望小。解決方案：概率大的事件用短碼字。③實(shí)時(shí)譯碼和容量限制。2021/9/203

3、§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼唯一可譯性的兩種解決方法定義3.3.2(p51)若①事件與碼字一一對(duì)應(yīng)；②每個(gè)碼字的開頭部分都是一個(gè)相同的字母串；③這個(gè)字母串僅僅出現(xiàn)在碼字的開頭，不出現(xiàn)在碼字的其它部位，也不出現(xiàn)在兩個(gè)碼字的結(jié)合部。則稱這個(gè)字母串為逗號(hào)，稱此碼為逗點(diǎn)碼。定義3.3.4(p51)①若事件與碼字一一對(duì)應(yīng)；②每個(gè)碼字都不是另一個(gè)碼字的開頭部分（字頭）。則稱此碼為異字頭碼。2021/9/204§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼注解逗點(diǎn)碼顯然是唯一可譯的，識(shí)別碼字的方法為：見

4、到逗號(hào)就識(shí)別為一個(gè)碼字的開始。異字頭碼也是唯一可譯的，識(shí)別碼字的方法為：見到一個(gè)碼字就識(shí)別為一個(gè)碼字。2021/9/205§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼例觀察表3.3.1(p51)。碼A不是唯一可譯的。碼B不是唯一可譯的。碼C是唯一可譯的，識(shí)別碼字的方法為：見“0”或“111”就是一個(gè)碼字的結(jié)束。實(shí)際上，碼C是異字頭碼。碼D是唯一可譯的，識(shí)別碼字的方法為：見“0”就是一個(gè)碼字的開始。實(shí)際上，碼D是逗點(diǎn)碼，其中“0”是逗號(hào)。碼C不是逗點(diǎn)碼。碼D不是異字頭碼。碼C的平均碼長(zhǎng)比碼D的平均碼長(zhǎng)小

5、：碼C的平均碼長(zhǎng)為1×0.5+2×0.25+3×0.125+3×0.125=1.75；碼D的平均碼長(zhǎng)為1×0.5+2×0.25+3×0.125+4×0.125=1.875。2021/9/206§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼異字頭碼的第一種構(gòu)造方法：Shannon-Fano編碼法（D元編碼，字母表為{0,1,…,D-1}）（1）將源隨機(jī)變量的事件按概率從大到小排成一行。（2）將此行切分為D段，分別賦予標(biāo)號(hào)“0”到“D-1”，稱為1級(jí)標(biāo)號(hào)。（3）將每個(gè)非空段再切分為D段，分別賦予標(biāo)號(hào)“0”到

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

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

8、標(biāo)號(hào)為止的標(biāo)號(hào)序列。（當(dāng)然要去掉那些0概率事件和它們的標(biāo)號(hào)序列）2021/9/209§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼（為什么Shannon-Fano碼和Huffman碼都是異字頭碼？請(qǐng)看p58圖3.4.1，p58圖3.4.2。這些圖都是樹，稱為碼樹，碼樹上的每個(gè)碼字都在樹梢。如果不是異字頭碼，則有的碼字就不在樹梢，而在中間節(jié)點(diǎn)。）定理3.3.1(Kraft不等式，p53)設(shè)信源隨機(jī)變量共有K個(gè)事件。則：各碼字長(zhǎng)度分別為n1、n2、…、nK的D元異字頭碼存在的