第五章信源編碼總結(jié)與習(xí)題

1、第五章第五章 信源編碼信源編碼2022-6-121：以以提高通信有效性提高通信有效性為目的的編碼。通常通過為目的的編碼。通常通過壓縮信源的冗余度來實(shí)現(xiàn)。采用的一般方法是壓縮每個(gè)信源符壓縮信源的冗余度來實(shí)現(xiàn)。采用的一般方法是壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)或信源的碼率。即同樣多的信息用較少的碼率號(hào)的平均比特?cái)?shù)或信源的碼率。即同樣多的信息用較少的碼率傳送，使單位時(shí)間內(nèi)傳送的平均信息量增加，從而提高通信的傳送，使單位時(shí)間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。有效性。n信道編碼：信道編碼：是以是以提高信息傳輸?shù)目煽啃蕴岣咝畔鬏數(shù)目煽啃詾槟康牡木幋a。為目的的編碼。通常通過增加信源的冗余度來實(shí)現(xiàn)。采

2、用的一般方法是增大碼通常通過增加信源的冗余度來實(shí)現(xiàn)。采用的一般方法是增大碼率率/帶寬。與信源編碼正好相反。帶寬。與信源編碼正好相反。n密碼：密碼：是以是以提高通信系統(tǒng)的安全性提高通信系統(tǒng)的安全性為目的的編碼。通常通為目的的編碼。通常通過加密和解密來實(shí)現(xiàn)。從信息論的觀點(diǎn)出發(fā)，過加密和解密來實(shí)現(xiàn)。從信息論的觀點(diǎn)出發(fā)，“加密加密”可視為可視為增熵的過程，增熵的過程，“解密解密”可視為減熵的過程。可視為減熵的過程。第五章第五章 信源編碼信源編碼2022-6-122n設(shè)離散無記憶信源設(shè)離散無記憶信源n二進(jìn)制香農(nóng)碼的編碼步驟如下：二進(jìn)制香農(nóng)碼的編碼步驟如下：q將信源符號(hào)按概率從大到小的順序排列，為方便起見

3、，將信源符號(hào)按概率從大到小的順序排列，為方便起見，令令 p(x1) p(x2) p(xn)q令令p(x0)=0，用，用pa(xj)，j=i+1表示第表示第i個(gè)碼字的累加概率，個(gè)碼字的累加概率，則則niininixpxpxpxpxpxxxxXPX121211)(,)(,),(,),(),(,)(njxpxpjiija, 2 , 1, )()(10第五章第五章 信源編碼信源編碼2022-6-123確定滿足下列不等式的整數(shù)確定滿足下列不等式的整數(shù)ki ，并令并令ki為第為第i個(gè)碼字的個(gè)碼字的長(zhǎng)度長(zhǎng)度log2 p(xi)ki1 log2 p(xi)q將將pa(xj) 用二進(jìn)制表示，并取小數(shù)點(diǎn)后用二進(jìn)制

4、表示，并取小數(shù)點(diǎn)后ki 位作為符號(hào)位作為符號(hào)xi的編碼。的編碼。第五章第五章 信源編碼信源編碼2022-6-124 費(fèi)諾編碼也是一種常見的信源編碼方法。編碼步驟如下：費(fèi)諾編碼也是一種常見的信源編碼方法。編碼步驟如下：n將概率按從大到小的順序排列，令將概率按從大到小的順序排列，令p(x1) p(x2) p(xn)n按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近或相等。如編二進(jìn)制碼就分成兩組，編或相等。如編二進(jìn)制碼就分成兩組，編m進(jìn)制碼就進(jìn)制碼就分成分成m組。組。n給每一組分配一位碼元。給每一組分配一位碼元。n將每一分組再按同樣原則劃分，重復(fù)步驟將每一分組

5、再按同樣原則劃分，重復(fù)步驟2和和3，直，直至概率不再可分為止至概率不再可分為止。第五章第五章 信源編碼信源編碼2022-6-125n將信源符號(hào)按概率從大到小的順序排列，令將信源符號(hào)按概率從大到小的順序排列，令p(x1) p(x2) p(xn)n給兩個(gè)概率最小的信源符號(hào)給兩個(gè)概率最小的信源符號(hào)p(xn-1)和和p(xn)各分配一個(gè)碼位各分配一個(gè)碼位“0”和和“1”，將這兩個(gè)信源符號(hào)合并成一個(gè)新符號(hào)，并用這兩個(gè)最小的，將這兩個(gè)信源符號(hào)合并成一個(gè)新符號(hào)，并用這兩個(gè)最小的概率之和作為新符號(hào)的概率，結(jié)果得到一個(gè)只包含概率之和作為新符號(hào)的概率，結(jié)果得到一個(gè)只包含(n1)個(gè)信源個(gè)信源符號(hào)的新信源。稱為符號(hào)的

6、新信源。稱為信源的第一次縮減信源信源的第一次縮減信源，用，用S1表示。表示。n將縮減信源將縮減信源S1的符號(hào)仍按概率從大到小順序排列，重復(fù)步驟的符號(hào)仍按概率從大到小順序排列，重復(fù)步驟2，得到只含得到只含(n2)個(gè)符號(hào)的縮減信源個(gè)符號(hào)的縮減信源S2。n重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號(hào)為止，此時(shí)所剩兩個(gè)重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號(hào)為止，此時(shí)所剩兩個(gè)符號(hào)的概率之和必為符號(hào)的概率之和必為1。然后從最后一級(jí)縮減信源開始，依編碼。然后從最后一級(jí)縮減信源開始，依編碼路徑向前返回，就得到各信源符號(hào)所對(duì)應(yīng)的碼字。路徑向前返回，就得到各信源符號(hào)所對(duì)應(yīng)的碼字。第五章第五章 信源編碼信源編碼2022-

7、6-126n在編在編m進(jìn)制哈夫曼碼時(shí)為了使平均碼長(zhǎng)最短，必須使最后一步進(jìn)制哈夫曼碼時(shí)為了使平均碼長(zhǎng)最短，必須使最后一步縮減信源有縮減信源有m個(gè)信源符號(hào)。非全樹時(shí)，有個(gè)信源符號(hào)。非全樹時(shí)，有s個(gè)碼字不用：個(gè)碼字不用：q第一次對(duì)最小概率符號(hào)分配碼元時(shí)就只取第一次對(duì)最小概率符號(hào)分配碼元時(shí)就只取(ms)個(gè)，分別配以個(gè)，分別配以0,1,ms1，把這些符號(hào)的概率相加作為一個(gè)新符號(hào)的概率，把這些符號(hào)的概率相加作為一個(gè)新符號(hào)的概率，與其它符號(hào)一起重新排列。與其它符號(hào)一起重新排列。q以后每次就可以取以后每次就可以取m個(gè)符號(hào)，分別配以個(gè)符號(hào)，分別配以0,1,m1；如此；如此下去，直至所有概率相加得下去，直至所有概

8、率相加得1為止，即得到各符號(hào)的為止，即得到各符號(hào)的m進(jìn)制碼字。進(jìn)制碼字。第五章第五章 信源編碼信源編碼2022-6-127第五章第五章 信源編碼信源編碼2022-6-128n適合有記憶信源適合有記憶信源n游程變換減弱了原序列符號(hào)間的相關(guān)性。游程變換減弱了原序列符號(hào)間的相關(guān)性。n游程變換游程變換將二元序列變換成了多元序列將二元序列變換成了多元序列；這樣就適合于用其他方法，；這樣就適合于用其他方法，如哈夫曼編碼，進(jìn)一步壓縮信源，提高通信效率。如哈夫曼編碼，進(jìn)一步壓縮信源，提高通信效率。n編碼方法：編碼方法：q首先測(cè)定首先測(cè)定“0”游程長(zhǎng)度和游程長(zhǎng)度和“1”游程長(zhǎng)度的概率分布，即游程長(zhǎng)度的概率分布，

9、即以游以游程長(zhǎng)度為元素，構(gòu)造一個(gè)新的信源程長(zhǎng)度為元素，構(gòu)造一個(gè)新的信源；q對(duì)新的信源（游程序列）進(jìn)行哈夫曼編碼。對(duì)新的信源（游程序列）進(jìn)行哈夫曼編碼。n多元序列也可以變換成游程序列，如多元序列也可以變換成游程序列，如m元序列可有元序列可有m種游程。但是種游程。但是變換成游程序列時(shí)，需要增加標(biāo)志位才能區(qū)分游程序列中的變換成游程序列時(shí)，需要增加標(biāo)志位才能區(qū)分游程序列中的“長(zhǎng)度長(zhǎng)度”是是m種游程中的哪一個(gè)的長(zhǎng)度，否則，變換就不可逆。這樣，增加種游程中的哪一個(gè)的長(zhǎng)度，否則，變換就不可逆。這樣，增加的標(biāo)志位可能會(huì)抵消壓縮編碼得到的好處。所以，的標(biāo)志位可能會(huì)抵消壓縮編碼得到的好處。所以，對(duì)多元序列進(jìn)行對(duì)多

10、元序列進(jìn)行游程變換的意義不大游程變換的意義不大。第五章第五章 信源編碼信源編碼2022-6-129 通過關(guān)于信源符號(hào)序列的累積分布函數(shù)的計(jì)算，把區(qū)間分割成許通過關(guān)于信源符號(hào)序列的累積分布函數(shù)的計(jì)算，把區(qū)間分割成許多小區(qū)間，不同的信源符號(hào)序列對(duì)應(yīng)不同的區(qū)間為多小區(qū)間，不同的信源符號(hào)序列對(duì)應(yīng)不同的區(qū)間為F(s s),F(s s)+P(s s) ?？扇⌒^(qū)間內(nèi)的一點(diǎn)來代表這序列?？扇⌒^(qū)間內(nèi)的一點(diǎn)來代表這序列。n編碼方法編碼方法：將符號(hào)序列的累積分布函數(shù)寫成二進(jìn)位的小數(shù)，取將符號(hào)序列的累積分布函數(shù)寫成二進(jìn)位的小數(shù)，取小數(shù)點(diǎn)后小數(shù)點(diǎn)后k位，若后面有尾數(shù)，就進(jìn)位到第位，若后面有尾數(shù)，就進(jìn)位到第k位，這樣

11、得到的一個(gè)位，這樣得到的一個(gè)數(shù)數(shù)C，并使，并使k滿足滿足n舉例舉例 。的碼字為得符號(hào)序列設(shè)整數(shù)代表大于或等于的最小kkkzzzzzzzCPk21212,1 , 0. 0)(1logss。的碼字為，得則110110. 0371)(10110001. 0)(sssCkPF第五章第五章 信源編碼信源編碼2022-6-1210 譯碼就是一系列比較過程，每一步比較譯碼就是一系列比較過程，每一步比較CF(s s)與與P(s s)P(0)。 F(s s0)=F(s s) F(s s1)=F(s s)+P(s s) P(0)ns s為前面已譯出的序列串；為前面已譯出的序列串；nP(s s)是序列串是序列串s

12、s對(duì)應(yīng)的寬度；對(duì)應(yīng)的寬度；nF(s s)是序列串是序列串s s的累積分布函數(shù)，即為的累積分布函數(shù)，即為s s對(duì)應(yīng)區(qū)間的下界；對(duì)應(yīng)區(qū)間的下界；nP(s s)P(0)是此區(qū)間內(nèi)下一個(gè)輸入為符號(hào)是此區(qū)間內(nèi)下一個(gè)輸入為符號(hào)“0”所占的子區(qū)間所占的子區(qū)間寬度；寬度；n若若CF(s s)P(s s)P(0)則譯輸出符號(hào)為則譯輸出符號(hào)為“1”。第五章第五章 信源編碼信源編碼2022-6-1211nLD編碼方法是一種分幀傳送的方式；編碼方法是一種分幀傳送的方式；n編碼方法編碼方法q在冗余位序列中取在冗余位序列中取N個(gè)符號(hào)作為一幀，編成一個(gè)碼字，碼個(gè)符號(hào)作為一幀，編成一個(gè)碼字，碼字中含有信息位的數(shù)量和位置信息，

13、在接收端依據(jù)這些字中含有信息位的數(shù)量和位置信息，在接收端依據(jù)這些信息進(jìn)行譯碼；信息進(jìn)行譯碼；q每個(gè)碼字傳送兩個(gè)數(shù)：每個(gè)碼字傳送兩個(gè)數(shù)：Q和和T，由下式計(jì)算，由下式計(jì)算個(gè)信息位的位置序號(hào)。幀內(nèi)第息；含有各信息位的位置信本幀內(nèi)信息位的數(shù)目；jnTQQnnnjnTjQQjj121111211第五章第五章 信源編碼信源編碼2022-6-1212qQ的位數(shù)：的位數(shù)：qT的位數(shù)：的位數(shù)：q總位數(shù)：總位數(shù)：比特。值需要種，表達(dá)，共的取值范圍：) 1(log102NQNNQ 的最小整數(shù)。表示不小于的位數(shù)種，有各信息位的可能位置共XXQNTQN2log)(log) 1(log22比特QNNA第五章第五章 信源編

14、碼信源編碼2022-6-1213q尋找某一值尋找某一值Kq若若q再找某一值再找某一值L11KnQKTQKQ則置。，確定所有信息位的位依次下去，直至求出則若令11111111nLnQLTQLQKTTQ第五章第五章 信源編碼信源編碼2022-6-1214Lempel-Ziv算法獨(dú)立于信源的統(tǒng)計(jì)特性，是一種變長(zhǎng)到定長(zhǎng)算法獨(dú)立于信源的統(tǒng)計(jì)特性，是一種變長(zhǎng)到定長(zhǎng)的編碼方案。的編碼方案。任何信源輸出序列能唯一分解為可變長(zhǎng)度的碼組，這些碼組任何信源輸出序列能唯一分解為可變長(zhǎng)度的碼組，這些碼組是用等長(zhǎng)的碼字進(jìn)行編碼的。是用等長(zhǎng)的碼字進(jìn)行編碼的。Lempel-Ziv算法及其各種變形使用消息自身迭代性地構(gòu)造一算法

15、及其各種變形使用消息自身迭代性地構(gòu)造一個(gè)變長(zhǎng)碼字的分析序列，這些不同長(zhǎng)度的碼字構(gòu)成一個(gè)碼字個(gè)變長(zhǎng)碼字的分析序列，這些不同長(zhǎng)度的碼字構(gòu)成一個(gè)碼字典，編碼過程就是在碼字典中尋找與編碼序列中下一段碼相典，編碼過程就是在碼字典中尋找與編碼序列中下一段碼相匹配的碼。匹配的碼。當(dāng)找到匹配時(shí)，編碼按照以下思路進(jìn)行：當(dāng)找到匹配時(shí)，編碼按照以下思路進(jìn)行： (1)如果因?yàn)榻邮掌饕汛嬗羞@個(gè)碼段，因此那么無需重發(fā)，只如果因?yàn)榻邮掌饕汛嬗羞@個(gè)碼段，因此那么無需重發(fā)，只需要辨認(rèn)地址以重新取回該碼段；需要辨認(rèn)地址以重新取回該碼段；第五章第五章 信源編碼信源編碼2022-6-1215 (2)如果沒有找到匹配碼段，則根據(jù)碼段序

16、列的參考位置，向序列如果沒有找到匹配碼段，則根據(jù)碼段序列的參考位置，向序列添加下一個(gè)碼元，以構(gòu)造碼字典的新碼字。添加下一個(gè)碼元，以構(gòu)造碼字典的新碼字。 (3)編碼開始時(shí)，使用一個(gè)空碼字典，所以第一個(gè)碼字是與先前碼編碼開始時(shí)，使用一個(gè)空碼字典，所以第一個(gè)碼字是與先前碼字無關(guān)的。字無關(guān)的。 (4)在一種碼字典結(jié)構(gòu)中，遞歸地形成地址的游程序列和該地址上在一種碼字典結(jié)構(gòu)中，遞歸地形成地址的游程序列和該地址上的字符段。的字符段。編碼后的碼字總是由兩部分組成：字典地址和本碼段需要添加的編碼后的碼字總是由兩部分組成：字典地址和本碼段需要添加的消息消息 。由此可見，由此可見， Lempel-Ziv編碼方法充分

17、利用了已編碼消息的信編碼方法充分利用了已編碼消息的信息。息。第五章第五章 信源編碼信源編碼2022-6-1216n本章介紹的都是離散信源變長(zhǎng)編碼。本章介紹的都是離散信源變長(zhǎng)編碼。q優(yōu)點(diǎn)優(yōu)點(diǎn)：提高編碼效率；：提高編碼效率；q缺點(diǎn)缺點(diǎn)：需要大量緩沖設(shè)備來存儲(chǔ)這些變長(zhǎng)碼，然后再：需要大量緩沖設(shè)備來存儲(chǔ)這些變長(zhǎng)碼，然后再以恒定的碼率進(jìn)行傳送；在傳輸?shù)倪^程中如果出現(xiàn)了以恒定的碼率進(jìn)行傳送；在傳輸?shù)倪^程中如果出現(xiàn)了誤碼，容易引起錯(cuò)誤擴(kuò)散，所以要求有優(yōu)質(zhì)的信道。誤碼，容易引起錯(cuò)誤擴(kuò)散，所以要求有優(yōu)質(zhì)的信道。n有時(shí)為了得到較高的編碼效率，先采用某種正交變有時(shí)為了得到較高的編碼效率，先采用某種正交變換，解除或減

18、弱信源符號(hào)間的相關(guān)性，然后再進(jìn)行換，解除或減弱信源符號(hào)間的相關(guān)性，然后再進(jìn)行信源編碼；有時(shí)則利用信源符號(hào)間的相關(guān)性直接編信源編碼；有時(shí)則利用信源符號(hào)間的相關(guān)性直接編碼。碼。第五章第五章 信源編碼信源編碼2022-6-1217第五章第五章 信源編碼信源編碼2022-6-1218第五章第五章 信源編碼信源編碼2022-6-1219第五章第五章 信源編碼信源編碼2022-6-1220第五章第五章 信源編碼信源編碼2022-6-1221第五章第五章 信源編碼信源編碼2022-6-1222m=3,取k=2,因?yàn)閙+k*(m-1)=3+2*2=7,所以一開始可取3個(gè)概率最小的符號(hào):可以用建立Huffman

19、樹的方法第五章第五章 信源編碼信源編碼2022-6-1223第五章第五章 信源編碼信源編碼2022-6-1224第五章第五章 信源編碼信源編碼2022-6-1225第五章第五章 信源編碼信源編碼2022-6-1226第五章第五章 信源編碼信源編碼2022-6-1227第五章第五章 信源編碼信源編碼2022-6-1228第五章第五章 信源編碼信源編碼2022-6-1229第五章第五章 信源編碼信源編碼2022-6-1230第五章第五章 信源編碼信源編碼2022-6-1231第五章第五章 信源編碼信源編碼2022-6-1232第五章第五章 信源編碼信源編碼2022-6-1233第五章第五章 信源編

20、碼信源編碼2022-6-1234第五章第五章 信源編碼信源編碼2022-6-1235第五章第五章 信源編碼信源編碼2022-6-12365.6 有二元平穩(wěn)馬氏鏈，已知有二元平穩(wěn)馬氏鏈，已知 ， ，求它的符號(hào)熵。，求它的符號(hào)熵。用三個(gè)符號(hào)合成一個(gè)來編二進(jìn)制哈夫曼碼，求新符號(hào)的平均碼字長(zhǎng)度和用三個(gè)符號(hào)合成一個(gè)來編二進(jìn)制哈夫曼碼，求新符號(hào)的平均碼字長(zhǎng)度和編碼效率。編碼效率。 8 . 0)00(p7 . 0) 11 (p 提示提示:只考慮二元一階平穩(wěn)馬氏鏈只考慮二元一階平穩(wěn)馬氏鏈,狀態(tài)圖狀態(tài)圖01再利用全概率公式和歸再利用全概率公式和歸1性求性求p(0)和和p(1),然后求出熵然后求出熵H(X).第五章第五章 信源編碼信源編碼2022-6-1237第三步第三步,求出擴(kuò)展信源的分布求出擴(kuò)展信源的分布:.) 1/0()0/0()0()001()0/0()0/0()0()000(?111110101100011010001000pppppppp第四步第四步,求出求出Huffman編碼編碼,再求編碼效率再求編碼效率.第五章第五章 信源編碼信源編碼2022-6-12385.7 對(duì)題對(duì)題5.6的信源進(jìn)行游程編碼。若的信源進(jìn)行游程編碼。若“0”游程長(zhǎng)度的截止值為游程長(zhǎng)度的截止值為16，“1”游游程長(zhǎng)度的截止值為程長(zhǎng)度的截止值為8，求編碼效率。，求編碼效率。 提示提示:用用P143最后一行求出