第13講-信源編碼2

1、 東北石油大學(xué)電氣信息工程學(xué)院東北石油大學(xué)電氣信息工程學(xué)院 張玉波張玉波15.7 5.7 算術(shù)編碼算術(shù)編碼n 原理：原理： 算術(shù)編碼是另一種常用的算術(shù)編碼是另一種常用的變字長編碼變字長編碼，它也是利用信源概率分，它也是利用信源概率分布特性、能夠趨近熵極限的編碼方法。它與布特性、能夠趨近熵極限的編碼方法。它與 Huffman Huffman 一樣，也是對一樣，也是對出現(xiàn)出現(xiàn)概率大的符號賦予短碼，對概率小的符號賦予長碼概率大的符號賦予短碼，對概率小的符號賦予長碼。但它的編。但它的編碼過程與碼過程與 Huffman Huffman 編碼卻不相同，而且在信源概率分布比較均勻的編碼卻不相同，而且在信源概

2、率分布比較均勻的情況下其編碼效率高于情況下其編碼效率高于 Huffman Huffman 編碼。它和編碼。它和 Huffman Huffman 編碼最大的編碼最大的區(qū)別在于它不是使用整數(shù)碼。區(qū)別在于它不是使用整數(shù)碼。 Huffman Huffman 碼是用整數(shù)長度的碼字來編碼的最佳方法，碼是用整數(shù)長度的碼字來編碼的最佳方法，而算法編碼是一種并不局限于整數(shù)長度碼字的最佳編碼而算法編碼是一種并不局限于整數(shù)長度碼字的最佳編碼方法。方法。 算術(shù)編碼是把各符號出現(xiàn)的概率算術(shù)編碼是把各符號出現(xiàn)的概率表示在單位概率表示在單位概率 00，1 1 區(qū)間之中，區(qū)間的寬度代表概率值的大小區(qū)間之中，區(qū)間的寬度代表概率

3、值的大小。符號出現(xiàn)。符號出現(xiàn)的概率越大對應(yīng)于區(qū)間愈寬，可用較短碼字表示；符號的概率越大對應(yīng)于區(qū)間愈寬，可用較短碼字表示；符號出現(xiàn)概率越小對應(yīng)于區(qū)間愈窄，需要較長碼字表示。出現(xiàn)概率越小對應(yīng)于區(qū)間愈窄，需要較長碼字表示。 東北石油大學(xué)電氣信息工程學(xué)院東北石油大學(xué)電氣信息工程學(xué)院 張玉波張玉波2算術(shù)編碼算術(shù)編碼原理原理n 符號序列符號序列S S3 3S S3 3S S2 2S S4 4 為例為例S1S2S3S4S1S2S3S4S1S2S3S401/83/87/81.000.0010.0110.1111.00.0110.1110.0111 0.10010.1101在算術(shù)編碼中通常采用二進(jìn)制分?jǐn)?shù)表在算術(shù)

4、編碼中通常采用二進(jìn)制分?jǐn)?shù)表示概率，示概率，每個(gè)符號所對應(yīng)的概率區(qū)間每個(gè)符號所對應(yīng)的概率區(qū)間都是半開區(qū)間都是半開區(qū)間，即該區(qū)間包括左端點(diǎn)，即該區(qū)間包括左端點(diǎn)，而不包括右端點(diǎn)，如而不包括右端點(diǎn)，如 S S1 1對應(yīng)對應(yīng) 0, 0, 0.001)0.001)，S S2 2 對應(yīng)對應(yīng) 0.001, 0.01) 0.001, 0.01) 等。等。 東北石油大學(xué)電氣信息工程學(xué)院東北石油大學(xué)電氣信息工程學(xué)院 張玉波張玉波3算術(shù)編碼算術(shù)編碼原理原理n 符號序列符號序列 S S3 3S S3 3S S2 2S S4 4 的第一個(gè)符號的第一個(gè)符號 S S3 3 用指向第用指向第 3 3 個(gè)子區(qū)間的個(gè)子區(qū)間的指針來

5、代表，指針來代表，可以用這個(gè)區(qū)間內(nèi)的任意一個(gè)小數(shù)來表示這個(gè)指針，可以用這個(gè)區(qū)間內(nèi)的任意一個(gè)小數(shù)來表示這個(gè)指針，這里約定這個(gè)區(qū)間的左端點(diǎn)代表這個(gè)指針，因此得到第一個(gè)碼這里約定這個(gè)區(qū)間的左端點(diǎn)代表這個(gè)指針，因此得到第一個(gè)碼字字 .011.011。n 后續(xù)的編碼將在前面編碼指向的子區(qū)間內(nèi)進(jìn)行，將后續(xù)的編碼將在前面編碼指向的子區(qū)間內(nèi)進(jìn)行，將 .011, .111 .011, .111 區(qū)間再按概率大小劃分為區(qū)間再按概率大小劃分為 4 4 份，第二個(gè)符號份，第二個(gè)符號 S S3 3 指向指向 .1001 (S.1001 (S3 3 區(qū)間的左端），輸出碼字變?yōu)閰^(qū)間的左端），輸出碼字變?yōu)?.1001.100

6、1。n 然后，然后，S S3 3 對應(yīng)的子區(qū)間又被劃分為對應(yīng)的子區(qū)間又被劃分為 4 4 份，開始對第三個(gè)符號份，開始對第三個(gè)符號 S S2 2 進(jìn)行編碼，進(jìn)行編碼，. . n 算術(shù)編碼產(chǎn)生的碼字實(shí)際上是一個(gè)二進(jìn)制數(shù)值的算術(shù)編碼產(chǎn)生的碼字實(shí)際上是一個(gè)二進(jìn)制數(shù)值的指針，指向所編的符號對應(yīng)的概率區(qū)間。指針，指向所編的符號對應(yīng)的概率區(qū)間。 東北石油大學(xué)電氣信息工程學(xué)院東北石油大學(xué)電氣信息工程學(xué)院 張玉波張玉波4算術(shù)編碼算術(shù)編碼基本法則基本法則n 兩個(gè)參量：兩個(gè)參量：編碼點(diǎn)（指針?biāo)柑帲┚幋a點(diǎn)（指針?biāo)柑帲〤 C 和區(qū)間寬度和區(qū)間寬度 A A。 初始狀態(tài)初始狀態(tài) 編碼點(diǎn)（指針?biāo)柑帲┚幋a點(diǎn)（指針?biāo)柑帲?/p>

7、C = 0C = 0 區(qū)間寬度區(qū)間寬度 A = 1.0A = 1.0 新編碼點(diǎn)新編碼點(diǎn) C = C = 原編碼點(diǎn)原編碼點(diǎn) C C 原區(qū)間原區(qū)間 A AP Pi i 新區(qū)間新區(qū)間 A = A = 原區(qū)間原區(qū)間 A Ap pi i n 序列序列 S S3 3S S3 3S S2 2S S4 4 的編碼過程：的編碼過程： 第第1 1個(gè)符號個(gè)符號 (S(S3 3): ): C = 0 + 1C = 0 + 1.011 = .011.011 = .011 A = 1A = 1.1 = .1.1 = .1 第第2 2個(gè)符號個(gè)符號 (S(S3 3): ): C = .011 + .1C = .011 + .

8、1.011 = .1001.011 = .1001 A = .1A = .1.1 = .01.1 = .01 第第3 3個(gè)符號個(gè)符號 (S(S2 2): C = .1001 + .01): C = .1001 + .01.001 = .10011 .001 = .10011 A = .01 A = .01.01 = .0001.01 = .0001 第第4 4個(gè)符號個(gè)符號 (S(S4 4): C = .10011 + .0001): C = .10011 + .0001.111 = .1010011 .111 = .1010011 （輸出（輸出的碼字）的碼字） A = .0001A = .00

9、01.001 = .0000001.001 = .0000001符號符號 S Si i 對應(yīng)對應(yīng)的的累積概率累積概率符號符號 S Si i 對對應(yīng)的應(yīng)的概率概率 東北石油大學(xué)電氣信息工程學(xué)院東北石油大學(xué)電氣信息工程學(xué)院 張玉波張玉波5算術(shù)編碼算術(shù)編碼解碼解碼n 算法解碼采取與編碼過程相反的步驟算法解碼采取與編碼過程相反的步驟 把接收到的碼字串指向其對應(yīng)的子區(qū)間，得到此子區(qū)間對應(yīng)的符號，即把接收到的碼字串指向其對應(yīng)的子區(qū)間，得到此子區(qū)間對應(yīng)的符號，即為解碼后的符號。為解碼后的符號。 即從碼字串中減去已解碼符號的子區(qū)間的左端點(diǎn)的數(shù)值（即從碼字串中減去已解碼符號的子區(qū)間的左端點(diǎn)的數(shù)值（累積概率累積概

10、率），）， 并將差值除以該子區(qū)間的寬度（并將差值除以該子區(qū)間的寬度（概率值概率值），得到新的碼字串。），得到新的碼字串。n 上述例子上述例子 當(dāng)收到字碼串當(dāng)收到字碼串 (.1010011) (.1010011) 時(shí)，其指向子區(qū)間時(shí)，其指向子區(qū)間 .011, .111.011, .111，對應(yīng)于，對應(yīng)于 S S3 3，因此，得到第，因此，得到第 1 1 個(gè)符號為個(gè)符號為 S S3 3。 新碼字串：（新碼字串：（.1010011 - .011) .1010011 - .011) (.1) = 0.100011 (.1) = 0.100011 ，新碼字串仍然，新碼字串仍然指向子區(qū)間指向子區(qū)間 .01

11、1, .111.011, .111，因此，第，因此，第 2 2 個(gè)符號仍為個(gè)符號仍為 S S3 3。 其它符號依次類推其它符號依次類推n 注意：算術(shù)編碼中的進(jìn)位注意：算術(shù)編碼中的進(jìn)位 在在 Huffman Huffman 編碼中，后續(xù)符號產(chǎn)生的碼字只是簡單地附加到先前的碼字編碼中，后續(xù)符號產(chǎn)生的碼字只是簡單地附加到先前的碼字串之后，并不改變已有的碼字串。串之后，并不改變已有的碼字串。 在算術(shù)編碼中，在算術(shù)編碼中，由于新編碼點(diǎn)由于新編碼點(diǎn) C C 表達(dá)式中相加運(yùn)算而產(chǎn)生進(jìn)位表達(dá)式中相加運(yùn)算而產(chǎn)生進(jìn)位，從而與，從而與 Huffman Huffman 不同。例如上述的第不同。例如上述的第 3 3 個(gè)

12、符號后碼字串為個(gè)符號后碼字串為 .10011.10011，但第，但第 4 4 個(gè)個(gè)符號后碼字串變?yōu)榉柡蟠a字串變?yōu)?.1010011.1010011， 東北石油大學(xué)電氣信息工程學(xué)院東北石油大學(xué)電氣信息工程學(xué)院 張玉波張玉波6二進(jìn)制算術(shù)編碼二進(jìn)制算術(shù)編碼n 二進(jìn)制算術(shù)編碼的輸入的二進(jìn)制算術(shù)編碼的輸入的字符只有兩種字符只有兩種，如果信源字符集內(nèi)，如果信源字符集內(nèi)包含有多個(gè)字符，則先將這些字符經(jīng)過一系列的二進(jìn)判決，包含有多個(gè)字符，則先將這些字符經(jīng)過一系列的二進(jìn)判決，變成二進(jìn)制字符串。變成二進(jìn)制字符串。n 這兩個(gè)符號構(gòu)成的序列的編碼與算術(shù)編碼基本原理相同，仍這兩個(gè)符號構(gòu)成的序列的編碼與算術(shù)編碼基本原理

13、相同，仍是不斷劃分概率子區(qū)間的遞歸過程。是不斷劃分概率子區(qū)間的遞歸過程。n 在兩個(gè)輸入字符中，出現(xiàn)概率較大的為在兩個(gè)輸入字符中，出現(xiàn)概率較大的為 MPS (MPS (More Probable More Probable SymbolSymbol) )，MPS MPS 的概率為的概率為 P Pe e；出現(xiàn)概率較小的為；出現(xiàn)概率較小的為 LPS (LPS (Less Less Probable SymbolProbable Symbol) )，LPS LPS 的概率為的概率為 Q Qe e，P Pe e=1-Q=1-Qe e。n 編碼初始化子區(qū)間為編碼初始化子區(qū)間為 00，11，MPSMPS與與

14、 LPS LPS 分配如圖所示：分配如圖所示：QePeLPSMPS 東北石油大學(xué)電氣信息工程學(xué)院東北石油大學(xué)電氣信息工程學(xué)院 張玉波張玉波7n 編碼時(shí)，設(shè)置兩個(gè)專用寄存器（編碼時(shí)，設(shè)置兩個(gè)專用寄存器（C C，A A） C C 寄存器的值為編碼點(diǎn)（指針?biāo)柑帲┘拇嫫鞯闹禐榫幋a點(diǎn)（指針?biāo)柑帲?A A 寄存器的值為子區(qū)間的寬度寄存器的值為子區(qū)間的寬度 ( (該寬度恰好是已輸入符號串的概率該寬度恰好是已輸入符號串的概率) )n 初始化時(shí)：初始化時(shí)：C=0 A=1C=0 A=1n 隨著被編碼數(shù)據(jù)源輸入，隨著被編碼數(shù)據(jù)源輸入，C C 和和 A A 的內(nèi)容按以下編碼規(guī)則修正：的內(nèi)容按以下編碼規(guī)則修正： 當(dāng)

15、低概率符號當(dāng)?shù)透怕史?LPS LPS 到來時(shí)：到來時(shí)：(LPS (LPS 的概率為的概率為 Q Qe e，累積概率為，累積概率為 0 )0 ) C=C A=AQ C=C A=AQe e 當(dāng)高概率符號當(dāng)高概率符號MPSMPS到來時(shí)：到來時(shí)：(LPS (LPS 的概率為的概率為 P Pe e，累積概率為，累積概率為 Q Qe e ) ) C=C + AQ C=C + AQe e A=Ap A=Ape e = A= A（1-Q1-Qe e）二進(jìn)制算術(shù)編碼二進(jìn)制算術(shù)編碼編碼規(guī)則編碼規(guī)則算術(shù)編碼的基本法則：算術(shù)編碼的基本法則： 新編碼點(diǎn)新編碼點(diǎn) C = C = 原編碼點(diǎn)原編碼點(diǎn) C C 原區(qū)間原區(qū)間

16、A AP Pi i 新區(qū)間新區(qū)間 A = A = 原區(qū)間原區(qū)間 A Ap pi i符號符號 S Si i 對應(yīng)對應(yīng)的累積概率的累積概率符號符號 S Si i 對對應(yīng)的概率應(yīng)的概率QePeLPSMPS 東北石油大學(xué)電氣信息工程學(xué)院東北石油大學(xué)電氣信息工程學(xué)院 張玉波張玉波8 第第 1 1 個(gè)符號個(gè)符號 1 1 為為 MPSMPS C = C + AQ C = C + AQe e = 0 + 1 = 0 + 1 0.001 = 0.0010.001 = 0.001 A = AP A = APe e = 1 = 1 0.1110.111 = 0.111 = 0.1110.0010.111二進(jìn)制算術(shù)編

17、碼二進(jìn)制算術(shù)編碼編碼舉例編碼舉例例例: : 信源符號序列信源符號序列 11011111 11011111 0 0 為為 LPS QLPS Qe e = 1/8 = = 1/8 =（0.0010.001）b b 1 1 為為 MPS PMPS Pe e = 7/8 = = 7/8 =（0.1110.111）b b初始狀態(tài)：初始狀態(tài)：C=0 (C=0 (子區(qū)間起始位置子區(qū)間起始位置) A=1 ) A=1 （子區(qū)間寬度）（子區(qū)間寬度） 第第 2 2 個(gè)符號個(gè)符號 1 1 仍為仍為 MPSMPS C=C+AQ C=C+AQe e = = 0.0010.001 + 0.111 + 0.111 0.001

18、=0.0011110.001=0.001111 A=AP A=APe e= 0.111 = 0.111 0.1110.111 =0.110001 =0.1100010.0011110.11000101 東北石油大學(xué)電氣信息工程學(xué)院東北石油大學(xué)電氣信息工程學(xué)院 張玉波張玉波9 第第 3 3 個(gè)符號個(gè)符號 0 0 為為 LPS LPS C=C= C=C=0.0011110.001111 A=A Qe A=A Qe =0.110001 =0.110001 0.0010.001 =0.000110001 =0.000110001 繼續(xù)下去繼續(xù)下去. . 最后得最后得 C= 0.010001111110

19、111100000001C= 0.010001111110111100000001 A= 0.000011001001000010111111 A= 0.000011001001000010111111 結(jié)果結(jié)果二進(jìn)制算術(shù)編碼二進(jìn)制算術(shù)編碼編碼舉例編碼舉例0.0011110.000110001頭 CA尾頭頭 0.010001111110111100000001 （C）+ 0.000011001001000010111111 （A）尾尾 0.010101000111111111000000頭頭 0.0101尾尾傳送碼字為傳送碼字為 0101編碼輸出可以是最后一個(gè)編碼區(qū)編碼輸出可以是最后一個(gè)編碼區(qū)

20、間中的任意數(shù)值，但為了取得最間中的任意數(shù)值，但為了取得最好的編碼效率，選擇的小數(shù)應(yīng)有好的編碼效率，選擇的小數(shù)應(yīng)有最短的比特長度。最短的比特長度。 東北石油大學(xué)電氣信息工程學(xué)院東北石油大學(xué)電氣信息工程學(xué)院 張玉波張玉波100CA1CACACACACACACA尾尾頭頭事件事件序號序號判決判決符號符號C=C 符號符號“0“C=C+AQe 符號符號“1“A=AQe 符號符號“0“A=AQe 符號符號“1“子區(qū)間分段子區(qū)間分段（Pe-7/8；Qe=1/8）110.0010.111210.0011110.11001300.0011110.000110001410.0011111100010.0001010

21、10111510.0100000110111110.000100101100001610.0100010000010110010.000100000110100111710.0100011000100011011110.000011100101110001001810.0100011111101111000000010.000011001001000010111111符號串符號串“11011111” 處于范圍：處于范圍：頭頭 0.010001111110111100000001 + 0.000011001001000010111111 尾尾 0.010101000111111111000000

22、 頭頭 0.0101 尾尾 傳送碼字傳送碼字 0101二進(jìn)制算術(shù)編碼二進(jìn)制算術(shù)編碼編碼舉例編碼舉例上述算術(shù)編碼過程上述算術(shù)編碼過程 東北石油大學(xué)電氣信息工程學(xué)院東北石油大學(xué)電氣信息工程學(xué)院 張玉波張玉波11n 解碼：解碼：按按 Qe、Pe 分成兩個(gè)子區(qū)間，判斷被解碼的碼字落在哪個(gè)區(qū)分成兩個(gè)子區(qū)間，判斷被解碼的碼字落在哪個(gè)區(qū)間，并賦予對應(yīng)符號。間，并賦予對應(yīng)符號。p 設(shè)設(shè) c =（0.0101) b 是被解碼的值，初始值是被解碼的值，初始值 A=1 Qe = 0.001二進(jìn)制算術(shù)編碼二進(jìn)制算術(shù)編碼解碼解碼當(dāng)當(dāng) c 落在落在 QeAA 之間，之間，解碼符號為解碼符號為 D=1 C = C-Qe A

23、 A = A（1-Qe）當(dāng)當(dāng) c 落在落在 0QeA 之間之間，解碼符號為解碼符號為 D=0 C = C A = Qe A c = 0.0101 落在落在 Qe A -A 之間，解碼符號為之間，解碼符號為 D = 1 c = c-QeA = 0.0101 - 0.001 = 0.0011 A = A（1-Qe）= 0.111 c= 0.0011 落在落在 Qe A -A 之間，解碼符號為之間，解碼符號為 D=1 c=c-QeA= 0.0011 -0.000111=0.000101 A=A（1-Qe）= 0.111 0.111=0.110001 c = 0.000101 落在落在 0-QeA 之間之間，解碼符號為，解碼符號為 D = 0 c = c = 0.0