1、第三章第三章 無失真信源編碼無失真信源編碼語音、圖像信源；限失真信源編碼，文字、文件信源；無失真信源編碼，分類適用于離散信源或數(shù)字信號(hào)適用于離散信源或數(shù)字信號(hào)適用于連續(xù)信源或模擬信號(hào)適用于連續(xù)信源或模擬信號(hào)信源編碼的分類信源編碼的分類?為什么要對信源進(jìn)行編碼為什么要對信源進(jìn)行編碼? 由于信源符號(hào)之間存在由于信源符號(hào)之間存在相關(guān)性相關(guān)性和分布和分布不均勻不均勻，使得信源存，使得信源存在冗余度。在冗余度。 （1）信源輸出符號(hào)間的依賴關(guān)系使得信源熵減小，這就）信源輸出符號(hào)間的依賴關(guān)系使得信源熵減小，這就是信源的相關(guān)性。相關(guān)程度越大，信源的實(shí)際熵越小，越趨是信源的相關(guān)性。相關(guān)程度越大，信源的實(shí)際熵越小

2、，越趨近于極限熵近于極限熵 ；反之，相關(guān)程度減小，信源實(shí)際熵增大。；反之，相關(guān)程度減小，信源實(shí)際熵增大。 （2）實(shí)際信源的符號(hào)分布概率不是均勻的，這使得實(shí)際的）實(shí)際信源的符號(hào)分布概率不是均勻的，這使得實(shí)際的信源熵總是小于最大熵信源熵總是小于最大熵 。 也就是說，實(shí)際發(fā)送的消息總是包含有無用的信息。信源也就是說，實(shí)際發(fā)送的消息總是包含有無用的信息。信源包含有冗余。包含有冗余。)(XH)()(max0XHXH信源無失真編碼的信源無失真編碼的主要任務(wù)主要任務(wù)就是就是減少冗余減少冗余，提高編碼效率。，提高編碼效率。具體說，就是針對信源輸出符號(hào)序列的統(tǒng)計(jì)特性，具體說，就是針對信源輸出符號(hào)序列的統(tǒng)計(jì)特性，

3、尋找一定的方法把信源輸出符號(hào)序列變換為尋找一定的方法把信源輸出符號(hào)序列變換為最短的最短的碼字序列。碼字序列。 信源編碼的基本途徑信源編碼的基本途徑 是什么是什么? 信源編碼的信源編碼的基本途徑基本途徑有兩個(gè)，有兩個(gè)，一是一是使序列中的各個(gè)符使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立，即解除相關(guān)性；號(hào)盡可能地互相獨(dú)立，即解除相關(guān)性；二是二是使編碼中使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，即各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，即概率均勻化概率均勻化。 信源編碼的基礎(chǔ)是什么信源編碼的基礎(chǔ)是什么? 信源編碼的信源編碼的基礎(chǔ)基礎(chǔ)是：兩個(gè)編碼定理，即無失真編碼定理和限失真是：兩個(gè)編碼定理，即無失真編碼定理和限失真編碼

4、定理。編碼定理。1）無失真編碼是可逆編碼，即信源符號(hào)轉(zhuǎn)換成代碼后，可從代碼）無失真編碼是可逆編碼，即信源符號(hào)轉(zhuǎn)換成代碼后，可從代碼無失真的恢復(fù)原信源符號(hào)。只適用于離散信源。無失真的恢復(fù)原信源符號(hào)。只適用于離散信源。2）對于連續(xù)信源，編成代碼后就無法無失真地恢復(fù)原來的連續(xù)值，）對于連續(xù)信源，編成代碼后就無法無失真地恢復(fù)原來的連續(xù)值，因?yàn)楹笳叩娜≈悼捎袩o限多個(gè)。此時(shí)只能根據(jù)率失真編碼定理在因?yàn)楹笳叩娜≈悼捎袩o限多個(gè)。此時(shí)只能根據(jù)率失真編碼定理在失真受限制的情況下進(jìn)行限失真編碼失真受限制的情況下進(jìn)行限失真編碼 說明說明： 編碼定理表明編碼定理表明： （1）必存在一種編碼方法，使代碼的平均長度可任意必

5、存在一種編碼方法，使代碼的平均長度可任意接近但不能低于極限熵接近但不能低于極限熵 （2）達(dá)到這一目標(biāo)的途徑，就是使概率與碼長匹配。達(dá)到這一目標(biāo)的途徑，就是使概率與碼長匹配。 3.1編碼定義編碼定義3.2信源冗余度信源冗余度3.3無失真信源編碼無失真信源編碼 定長編碼定理定長編碼定理 變長編碼定理變長編碼定理 最佳編碼最佳編碼編碼器可以看作這樣一個(gè)系統(tǒng)，它的輸入端為原始信源編碼器可以看作這樣一個(gè)系統(tǒng)，它的輸入端為原始信源U，其符，其符號(hào)集為號(hào)集為U:u1,u2,uq；而信道所能傳輸?shù)拇a元符號(hào)集為；而信道所能傳輸?shù)拇a元符號(hào)集為X:x1,x2,xr；編碼器的功能是用碼元符號(hào)集；編碼器的功能是用碼元符

6、號(hào)集X中的元素，將原中的元素，將原始信源的符號(hào)始信源的符號(hào)ui變換為相應(yīng)的碼字符號(hào)變換為相應(yīng)的碼字符號(hào)Wi，(i=1,2,q)，所以編，所以編碼器輸出端的符號(hào)集為碼器輸出端的符號(hào)集為W:W1,W2,Wq。3.1 編碼定義編碼定義信源消息信源消息U=(u1,u2, uq)碼符號(hào)集碼符號(hào)集X=(x1,x2, xr)將將 ui Wi （ w1,w2,wq）其中某一碼字）其中某一碼字 wix1,x2,xr這種一一對應(yīng)變換稱為信源編碼。這種一一對應(yīng)變換稱為信源編碼。1 信源編碼：信源編碼：若若Li為碼字為碼字Wi中的碼元個(gè)數(shù)，則中的碼元個(gè)數(shù)，則 Li稱為碼字稱為碼字Wi的長度，的長度，簡稱碼長。簡稱碼長

7、。將信源消息分成若干組，即將信源消息分成若干組，即符號(hào)序列符號(hào)序列ui，ui=(ui1,ui2,uil,uiL)序列中的每個(gè)符號(hào)取自于同一個(gè)符號(hào)集序列中的每個(gè)符號(hào)取自于同一個(gè)符號(hào)集A， uil(a1,a2,an)。而每個(gè)符號(hào)序列而每個(gè)符號(hào)序列ui依照固定的碼表映射成一個(gè)碼字依照固定的碼表映射成一個(gè)碼字Wi，這，這樣的碼稱為分組碼。只有分組碼有對應(yīng)的碼表。樣的碼稱為分組碼。只有分組碼有對應(yīng)的碼表。分組碼定義：分組碼定義：如果每次只傳送一個(gè)符號(hào)，即序列長度如果每次只傳送一個(gè)符號(hào)，即序列長度L1要將這樣要將這樣 的符號(hào)進(jìn)行傳輸，常采用二元信道，碼符號(hào)集的符號(hào)進(jìn)行傳輸，常采用二元信道，碼符號(hào)集X為為0

8、,1。若將信源在該信道上傳輸，需把信源符號(hào)變換成。若將信源在該信道上傳輸，需把信源符號(hào)變換成0，1符號(hào)組成的碼字序列。符號(hào)組成的碼字序列。ui=ui1(a1,a2,an)例：例：信源符號(hào)信源符號(hào)信源符號(hào)出信源符號(hào)出現(xiàn)概率現(xiàn)概率碼表碼表a1a2a3a4p(a1)p(a2)p(a3)p(a4) 00 01 10 11 0 01 001 111碼碼1碼碼22 碼的類型碼的類型 碼碼非分組碼非分組碼分組碼分組碼奇異碼奇異碼非奇異碼非奇異碼非唯一可譯碼非唯一可譯碼唯一可譯碼唯一可譯碼非即時(shí)碼非即時(shí)碼即時(shí)碼（非延長碼）即時(shí)碼（非延長碼）2.1 碼符號(hào)集中符號(hào)數(shù)碼符號(hào)集中符號(hào)數(shù)r2稱為二元碼，稱為二元碼，r

9、3稱為三元碼稱為三元碼2.2 若分組碼中的碼長都相同則稱為等長碼，否則稱為變長碼若分組碼中的碼長都相同則稱為等長碼，否則稱為變長碼信源符號(hào)信源符號(hào)信源符號(hào)出信源符號(hào)出現(xiàn)概率現(xiàn)概率碼表碼表a1a2a3a4p(a1)p(a2)p(a3)p(a4) 00 01 10 11 0 01 001 111碼碼1碼碼2碼碼1是等長碼，碼是等長碼，碼2是變長碼是變長碼2.3 奇異碼和非奇異碼奇異碼和非奇異碼若信源符號(hào)和碼字是一一對應(yīng)的，即所有碼字都不相同，若信源符號(hào)和碼字是一一對應(yīng)的，即所有碼字都不相同，則該碼為非奇異碼；反之為奇異碼。則該碼為非奇異碼；反之為奇異碼。信源符號(hào)信源符號(hào)符號(hào)出現(xiàn)概率符號(hào)出現(xiàn)概率 碼

10、碼1碼碼2碼碼3碼碼4a1a2a3a41/21/41/81/8 0110011010000111010010001010010001碼碼1是奇異碼，碼是奇異碼，碼2，碼，碼3和碼和碼4是非奇異碼是非奇異碼2.4 唯一可譯碼唯一可譯碼非奇異碼中，任意有限長的碼元序列，只能被唯一的譯成所對非奇異碼中，任意有限長的碼元序列，只能被唯一的譯成所對應(yīng)的信源符號(hào)序列，稱為唯一可譯碼。應(yīng)的信源符號(hào)序列，稱為唯一可譯碼。例如：例如：U: u1,u2,u3; X:0,1; W: w1=0, w2=10, w3=11, 為唯一可譯碼。為唯一可譯碼。當(dāng)接收碼字序列為：當(dāng)接收碼字序列為：10011001111 時(shí)，可

11、以唯一地譯為：時(shí)，可以唯一地譯為：w2,w1,w3,w1,w1,w3,w3;如果碼字集合為：如果碼字集合為：W:w1=0,w2=01,w3=001 則為非唯一可譯碼。則為非唯一可譯碼。當(dāng)接收碼字序列為：當(dāng)接收碼字序列為：00101 時(shí)，可以譯為：時(shí)，可以譯為：w1,w2,w2;也可譯為也可譯為: w3,w22.5 非即時(shí)碼和即時(shí)碼非即時(shí)碼和即時(shí)碼唯一可譯碼中，如果接收端收到一個(gè)完整的碼字后，不能立唯一可譯碼中，如果接收端收到一個(gè)完整的碼字后，不能立即譯碼，還需等下一個(gè)碼字開始接收后才能判斷是否可以譯即譯碼，還需等下一個(gè)碼字開始接收后才能判斷是否可以譯碼，這樣的碼叫做碼，這樣的碼叫做非即時(shí)碼非即

12、時(shí)碼。沒有任何完整的碼字是其他碼字的前綴，可立即譯碼的叫做沒有任何完整的碼字是其他碼字的前綴，可立即譯碼的叫做即時(shí)碼即時(shí)碼（非延長碼）。（非延長碼）。例如：例如：W：1，10，100，111不是即時(shí)碼，不是即時(shí)碼， 1是是 10的前綴，的前綴， 10 為為100的前綴。的前綴。3 即時(shí)碼及其樹圖構(gòu)造法即時(shí)碼及其樹圖構(gòu)造法 碼樹碼樹碼樹碼樹：用碼樹表示碼字的組成：用碼樹表示碼字的組成碼樹構(gòu)造要點(diǎn)：碼樹構(gòu)造要點(diǎn)：1）最上（下）端為樹根，從樹根向下（上）延伸出樹枝，）最上（下）端為樹根，從樹根向下（上）延伸出樹枝，樹枝總數(shù)等于樹枝總數(shù)等于r，樹枝的盡頭為節(jié)點(diǎn)。，樹枝的盡頭為節(jié)點(diǎn)。2）從每個(gè)節(jié)點(diǎn)再伸出

13、）從每個(gè)節(jié)點(diǎn)再伸出r個(gè)樹枝，當(dāng)某節(jié)點(diǎn)被安排為碼字個(gè)樹枝，當(dāng)某節(jié)點(diǎn)被安排為碼字 后，就不再伸枝。后，就不再伸枝。3）每個(gè)節(jié)點(diǎn)伸出的樹枝標(biāo)上碼符號(hào)，從根出發(fā)到終端節(jié)）每個(gè)節(jié)點(diǎn)伸出的樹枝標(biāo)上碼符號(hào)，從根出發(fā)到終端節(jié) 點(diǎn)所走路徑對應(yīng)的碼符號(hào)序列則為終端節(jié)點(diǎn)的碼字。點(diǎn)所走路徑對應(yīng)的碼符號(hào)序列則為終端節(jié)點(diǎn)的碼字。r進(jìn)制碼樹：有進(jìn)制碼樹：有r個(gè)分支個(gè)分支樹根樹根一級(jí)節(jié)點(diǎn)：經(jīng)過一個(gè)分支到達(dá)的節(jié)點(diǎn)，有一級(jí)節(jié)點(diǎn)：經(jīng)過一個(gè)分支到達(dá)的節(jié)點(diǎn)，有r個(gè)個(gè)n級(jí)節(jié)點(diǎn)：級(jí)節(jié)點(diǎn)：rn個(gè)個(gè)碼字：從樹根到節(jié)點(diǎn)的分枝標(biāo)號(hào)序列碼字：從樹根到節(jié)點(diǎn)的分枝標(biāo)號(hào)序列碼樹圖碼樹圖 二進(jìn)制碼樹二進(jìn)制碼樹（二元編碼）（二元編碼）012000001111

14、122222三進(jìn)制碼樹三進(jìn)制碼樹（三元編碼）（三元編碼）A010000000000000111111111110114 唯一可譯碼存在的充要條件唯一可譯碼存在的充要條件：1mn1iKi其中其中n表示信源符號(hào)數(shù)，表示信源符號(hào)數(shù)，m表示進(jìn)制數(shù)，表示進(jìn)制數(shù)，Ki表示各碼字長度。表示各碼字長度。對含有對含有n個(gè)信源符號(hào)的信源用含有個(gè)信源符號(hào)的信源用含有m個(gè)碼元的碼符號(hào)集進(jìn)行個(gè)碼元的碼符號(hào)集進(jìn)行編碼，各碼字的長為編碼，各碼字的長為k1，k2.，其唯一可譯碼存在的充要，其唯一可譯碼存在的充要條件是，滿足條件是，滿足克勞夫特（克勞夫特（Kraft）不等式）不等式例：設(shè)二進(jìn)制碼樹中例：設(shè)二進(jìn)制碼樹中U=（a1

15、,a2,a3,a4),K1=1,K2=2,K3=2,K4=3,請判斷是否存在唯一可譯碼？請判斷是否存在唯一可譯碼？i4K-1-2-2-3i192=2 +2 +2 +2 =18不存在這種不存在這種Ki的唯一可譯碼。的唯一可譯碼。010011a1a2a3a4如果傳送如果傳送000100，01000，1a3,a2a4,a1a1: 1a2: 01a3: 00a4: 000如果改成如果改成K1=1,K2=2,K3=3,K4=3,請判斷這是否存在唯一可譯碼？請判斷這是否存在唯一可譯碼？i4K-1-2-3-3i12=2 +2 +2 +2 =1010011a1a2a3a4存在這種存在這種Ki的唯一可譯碼。的唯

16、一可譯碼。a1: 1a2: 01a3: 000a4: 001注意：注意：克勞夫特（克勞夫特（Kraft）不等式只是用來說明唯一可譯碼是否）不等式只是用來說明唯一可譯碼是否存在，并不能作為判斷哪些碼是唯一可譯碼的依據(jù)。存在，并不能作為判斷哪些碼是唯一可譯碼的依據(jù)。如碼字（如碼字（0，10，010，111）滿足克勞夫特不等式，但它不是）滿足克勞夫特不等式，但它不是唯一可譯碼唯一可譯碼3.2 信源冗余度信源冗余度121lim()lim(/)bit/LLLLLHHH XX XXX符號(hào)對平穩(wěn)信源對平穩(wěn)信源理論上需要傳輸?shù)淖钚⌒畔⒗碚撋闲枰獋鬏數(shù)淖钚⌒畔?3)容易看出容易看出:其中其中: H0(X) 是具

17、有是具有N種取值可能的單消息信源的最大信息熵種取值可能的單消息信源的最大信息熵(等概率時(shí)等概率時(shí))由于符號(hào)所含的信息熵依次遞減由于符號(hào)所含的信息熵依次遞減,所以平均符號(hào)信息熵自然所以平均符號(hào)信息熵自然越來越小越來越小(4) 信源效率（相對熵）信源效率（相對熵）: 信源冗余度信源冗余度:21020()()()()logHXHXHXHXN0()()HXHX1關(guān)于冗余度的理解關(guān)于冗余度的理解: H是考慮全部信源統(tǒng)計(jì)特性后的最小信息熵，是考慮全部信源統(tǒng)計(jì)特性后的最小信息熵，是信道傳送理論上的最佳值，只要在信道上傳是信道傳送理論上的最佳值，只要在信道上傳送送H，在接收端利用信源統(tǒng)計(jì)關(guān)聯(lián)的記憶特，在接收端

18、利用信源統(tǒng)計(jì)關(guān)聯(lián)的記憶特性，可恢復(fù)出全部信息。性，可恢復(fù)出全部信息。 由于存在著信源冗余由于存在著信源冗余,使得壓縮編碼成為可能。使得壓縮編碼成為可能。 信源冗余度是信源壓縮編碼的理論基礎(chǔ)。信源冗余度是信源壓縮編碼的理論基礎(chǔ)。例題：英文字母和空格鍵在英語中出現(xiàn)的概率例題：英文字母和空格鍵在英語中出現(xiàn)的概率統(tǒng)計(jì)如下，計(jì)算信源效率與信源冗余度。統(tǒng)計(jì)如下，計(jì)算信源效率與信源冗余度。Space 0.2 E 0.105 T 0.072 O 0.554 A 0.063 N 0.059I 0.055 R 0.054 S 0.052 H 0.047 D 0.035 L 0.029C 0.023 F 0.0225 U 0.0225 M 0.021 P 0.0175 Y 0.012 W 0.012 G 0.011 B 0.0105 V 0.008 K 0.003 X 0.002 J 0.001 Q 0.001 Z 0.001 H0=log227=4.76bit/符號(hào)