第三章-無失真信源編碼(2-2)

1、離散、無失真、無記憶信源符號序列編碼的一般模型：離散、無失真、無記憶信源符號序列編碼的一般模型： 每個符號Ui有n種取值采用m進制編碼，Ci有m種取值信源編碼模型信源編碼模型 對離散、無記憶、平穩(wěn)信源符號序列：對離散、無記憶、平穩(wěn)信源符號序列： U =(U1,U2 .UL)，平均每個符號的熵是平均每個符號的熵是可用可用K個碼元個碼元C =(C1,C2.Ck) 進行等長編碼，對任意進行等長編碼，對任意0,0，只要滿足：只要滿足： 則當序列長度則當序列長度L足夠大時，可使譯碼差錯小于足夠大時，可使譯碼差錯小于，反之，當反之，當 時，譯碼一定出錯。時，譯碼一定出錯。 2(/)log( ) LKLmH

2、U2(/)log()2LKLmHU)LHU（3.3定長編碼定理定長編碼定理2(/)log( ) LKLmHU2log( ) LKmLHU左邊是左邊是K長碼字所能攜帶的最大信息量，右邊是長為長碼字所能攜帶的最大信息量，右邊是長為L的信源序列的信源序列所攜帶的信息量。所攜帶的信息量。只要碼字所攜帶的信息量大于信源序列輸出的信息量，則可以使只要碼字所攜帶的信息量大于信源序列輸出的信息量，則可以使傳輸傳輸幾乎無失真幾乎無失真，條件是，條件是L足夠大。足夠大。說明：說明：2(/)log( ) LKLm HU2(/)log( ) LKLmHU沒有一種編碼器實現(xiàn)無失真譯碼沒有一種編碼器實現(xiàn)無失真譯碼臨界，可

3、能失真也可能無失真臨界，可能失真也可能無失真幾個概念：幾個概念：1個信源符號所攜帶的碼元平均信息個信源符號所攜帶的碼元平均信息2logKmL比特比特/符號符號2log mK個碼元的信息量個碼元的信息量比特比特/K個碼元個碼元序列的平均碼長序列的平均碼長碼元碼元/序列序列()iiKPKKKL碼元碼元/符號符號每個符號的平均碼長每個符號的平均碼長L=1,LKK 2( )logLcHUKm編碼效率編碼效率:信源實際信息率與編碼后的最信源實際信息率與編碼后的最大信息率之比。大信息率之比。若信源的符號熵若信源的符號熵HL(U)給定，編碼后每個信源符號平均用給定，編碼后每個信源符號平均用 個個碼元來變換，

4、編碼后的最大信息率為碼元來變換，編碼后的最大信息率為KmKlog當m=2,KUHLc)(下面分析一下等長編碼的編碼過程：下面分析一下等長編碼的編碼過程：例如，某信源有例如，某信源有8種符號，每種符號的輸出概率分別為種符號，每種符號的輸出概率分別為0.4, 0.18, 0.1, 0.1, 0.07, 0.06, 0.05, 0.04, L=1，用二元定長碼進行，用二元定長碼進行編碼。編碼。1( )2.55/H Ubit符號分析：分析：種符號，還有部分符號沒有對應的碼字。種符號，還有部分符號沒有對應的碼字。如果用如果用來編碼，則只能編來編碼，則只能編856. 5255. 2bit55. 2)(1U

5、HK信源一旦出現(xiàn)這些符號，就只能用其他碼字代替編碼，因而信源一旦出現(xiàn)這些符號，就只能用其他碼字代替編碼，因而引起差錯。差錯發(fā)生的可能性取決于這些符號出現(xiàn)的概率。引起差錯。差錯發(fā)生的可能性取決于這些符號出現(xiàn)的概率。當當L足夠大時，小概率事件發(fā)生的概率變得很小，使得差錯概率足夠大時，小概率事件發(fā)生的概率變得很小，使得差錯概率達到足夠小。達到足夠小。 所以，當采用定長編碼時，如果允許一定的差錯，則無需對全所以，當采用定長編碼時，如果允許一定的差錯，則無需對全部組合的部組合的nL種信息一一編碼，而僅需對集合中少數(shù)大概率事件種信息一一編碼，而僅需對集合中少數(shù)大概率事件的元素進行編碼即可。的元素進行編碼即

6、可。 ()pA 任何一個離散隨機序列信源，可以分成大概率事件集合任何一個離散隨機序列信源，可以分成大概率事件集合A 與小概與小概率事件集合率事件集合 ,即即 ，集，集A 中的元素有對應的輸出碼中的元素有對應的輸出碼字，而字，而 中的元素沒有對應的碼字，因而會在譯碼時發(fā)生差錯。中的元素沒有對應的碼字，因而會在譯碼時發(fā)生差錯。ALnAAA如果允許一定的差錯如果允許一定的差錯，則，則 編碼時只需要對屬于集合編碼時只需要對屬于集合 A 中的中的 個樣本賦以不同的碼字，即輸出碼字的總個數(shù)個樣本賦以不同的碼字，即輸出碼字的總個數(shù) 大于大于 就就可以了。可以了。在這種編碼方式下，差錯概率在這種編碼方式下，差

7、錯概率 即為集合即為集合 中元素發(fā)生的中元素發(fā)生的概率，此時要求概率，此時要求A)(Ap可以證明：可以證明： 22LUPe 2()()LU 為信源自信息量的方差。為信源自信息量的方差。 22UL 即當信源序列長度即當信源序列長度L滿足下式時，能達到差錯要求。滿足下式時，能達到差錯要求。22UL當當2 和和均為定值時，只要均為定值時，只要L足夠大，差錯概率可以小于任一足夠大，差錯概率可以小于任一正數(shù)正數(shù)，1Ap這些在這些在A中的元素分別用不同碼字來代表，就完成了編碼過程。中的元素分別用不同碼字來代表，就完成了編碼過程。計算所有可能的信源序列樣本矢量的概率，按概率大小排列，計算所有可能的信源序列樣

8、本矢量的概率，按概率大小排列，選用概率較大的作為選用概率較大的作為A中的元素，直到中的元素，直到定長編碼過程：定長編碼過程：在給定在給定和和后，用下式規(guī)定了后，用下式規(guī)定了L的大小。的大小。 22UL ( )( )LcLHUHU最佳編碼效率（考慮了失真）最佳編碼效率（考慮了失真）例：設有一簡單離散信源：例：設有一簡單離散信源：L=1,n=4123411112488uuuuUp對其進行近似無失真的等長編碼，若要求其編碼效率為對其進行近似無失真的等長編碼，若要求其編碼效率為95%，差錯率低于，差錯率低于10- -6，試求符號聯(lián)合編碼長度，試求符號聯(lián)合編碼長度L=？ 092.095.095.075.

9、175.141( )log1.75iiiH Uppbit 解：解：2()()LU 由由2=0.6875()95%()cH UH U編碼效率：編碼效率：可見可見,需要需要100萬個信源符號聯(lián)合編碼萬個信源符號聯(lián)合編碼,才能達到上述要求才能達到上述要求,這顯然是這顯然是不現(xiàn)實的。不現(xiàn)實的。定長編碼既要實現(xiàn)幾乎無失真，并且也要有較高的編碼效率是不定長編碼既要實現(xiàn)幾乎無失真，并且也要有較高的編碼效率是不能同時滿足的，必須考慮變長編碼。能同時滿足的，必須考慮變長編碼。再由再由:6622210813. 010)092. 0(6875. 0L3.4 變長編碼定理變長編碼定理根據(jù)信源各符號的統(tǒng)計特性，對概率大

10、的符號用短碼，對概率根據(jù)信源各符號的統(tǒng)計特性，對概率大的符號用短碼，對概率小的用較長的碼進行信源編碼。小的用較長的碼進行信源編碼。22()()1log mlog mH XH XK單個符號變長編碼定理單個符號變長編碼定理：若離散無記憶信源的符號熵為：若離散無記憶信源的符號熵為H(X),每個信源符號用每個信源符號用m進制碼元進行變長編碼，一定存在一種無進制碼元進行變長編碼，一定存在一種無失真編碼方法，其碼字平均長度失真編碼方法，其碼字平均長度 滿足下列不等式滿足下列不等式KLLHXKHX離散平穩(wěn)無記憶序列變長編碼定理離散平穩(wěn)無記憶序列變長編碼定理：對于平均符號熵為：對于平均符號熵為HL(X)的離散

11、平穩(wěn)無記憶信源，一定存在一種無失真編碼方法，使編的離散平穩(wěn)無記憶信源，一定存在一種無失真編碼方法，使編碼后的平均信息率碼后的平均信息率 滿足下列不等式滿足下列不等式K為任意小正數(shù)，為任意小正數(shù)，2logLKKmL()()LHXLHX22()()1loglogLLLLHXLHXKmm22log( )log( )LLLKmH XKm H XLL當當L足夠大時，可使足夠大時，可使 ，則證明該定理成立。，則證明該定理成立。2log mLLLHXKHX證明證明: 設用設用m進制碼元作變長編碼，序列長度為進制碼元作變長編碼，序列長度為L個信源個信源符號，可以得到平均碼字長度符號，可以得到平均碼字長度 滿足

12、下列不等式滿足下列不等式LK說明說明: （1）用變長編碼來達到相當高的編碼效率，一用變長編碼來達到相當高的編碼效率，一般所要求的符號長度般所要求的符號長度L可以比定長編碼小得多?？梢员榷ㄩL編碼小得多。 可以得到編碼效率的下界：可以得到編碼效率的下界： 2()()log()LLcLHXHXmKHXL(2)例如：例如：用二進制編碼，用二進制編碼，m2，log2m=l，H(X) =2.55比特符號，若要求比特符號，若要求 ，則編碼效率的下界為則編碼效率的下界為 %90c428. 0/ 1, 9 . 0/ 155. 255. 2LL(3) 碼的剩余度碼的剩余度 為為iiLKXPK)()11LHXK 碼

13、的剩余度碼的剩余度 用來衡量各種編碼方法與最佳碼的差距。用來衡量各種編碼方法與最佳碼的差距。 （4）編碼后碼字的平均碼長：（對長度為編碼后碼字的平均碼長：（對長度為L的符號序列編碼）的符號序列編碼）LKKL單個符號的平均碼長單個符號的平均碼長符號序列的平均碼長符號序列的平均碼長P(Xi)為符號序列的概率。為符號序列的概率。例：例：設離散無記憶信源的概率空間為設離散無記憶信源的概率空間為 4/14/321xxPX解解:其信源熵為其信源熵為 22134( )log 4log0.811443H X 比特比特/符號符號 求求:定長編碼和變長編碼的編碼效率定長編碼和變長編碼的編碼效率?(1)定長編碼定長

14、編碼 若用二元定長編碼（若用二元定長編碼（0，1）來構(gòu)造一個）來構(gòu)造一個 即時碼：即時碼：這時平均碼長為這時平均碼長為 =1 碼元碼元/符號，符號， 編碼效率為編碼效率為(對于無記憶信源而言對于無記憶信源而言,有有HL(X)=H(X) ) 輸出的信息率為輸出的信息率為 1, 021xxK2()100%81.1%log2HXKL=1().H XRK比特比特/碼元碼元(2)變長編碼變長編碼 假定信源序列的長度為假定信源序列的長度為L=1,采用二元變長編碼，其即時碼如采用二元變長編碼，其即時碼如下表所示。下表所示。 符號符號概率即時碼 x13/4 0 x2 101/40.811100%.%. 12.

15、K 碼元/符號這個碼的平均碼字長度這個碼的平均碼字長度.KK 碼元/符號 單個符號的平均碼長單個符號的平均碼長 編碼效率編碼效率 輸出的信息率為輸出的信息率為 R10.6488 比特碼元比特碼元 假定信源序列的長度為假定信源序列的長度為L=2,采用二元變長編碼，其即時碼如采用二元變長編碼，其即時碼如下表所示。下表所示。 序列序列概率即時碼 x1x1 9/16 0 x1x2 x2x1 x2x2 1/16 3/16 3/16 111 110 10信源序列二元碼符號/162731613163216311692K%1 .96%10027811. 0322符號碼元符號/322722KK這個序列的碼字平均

16、長度這個序列的碼字平均長度單個符號的平均碼長單個符號的平均碼長 編碼效率編碼效率輸出的信息率為輸出的信息率為 R20.961 比特碼元符號比特碼元符號將信源序列的長度增加，將信源序列的長度增加，L3或或L=4，對這些信源序列，對這些信源序列X進行進行變長編碼變長編碼，并求出其編碼效率分別為并求出其編碼效率分別為 %1.99%5.9843如果對這一信源采用定長二元碼編碼，要求編碼效率達到如果對這一信源采用定長二元碼編碼，要求編碼效率達到96時，時，允許譯碼錯誤概率允許譯碼錯誤概率 。則自信息的方差。則自信息的方差 510212224715.0)()(log)(iiiXHppX752221013.

17、 41004. 0)96. 0()811. 0(4715. 0L信息傳輸率分別為：信息傳輸率分別為： R30985比特碼元符號比特碼元符號 R40991比特碼元符號比特碼元符號所需要的信源序列長度所需要的信源序列長度(1)最佳碼定義是什么最佳碼定義是什么? 凡是能載荷一定的信息量，且碼字的平均長度最短，可分凡是能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合都可稱為最佳碼。離的變長碼的碼字集合都可稱為最佳碼。 (2)最佳編碼思想是什么最佳編碼思想是什么? 將概率大的信息符號編以短的碼字，概率小的符號編以長將概率大的信息符號編以短的碼字，概率小的符號編以長的碼字，使得平均碼字長

18、度最短。的碼字，使得平均碼字長度最短。 (3)最佳碼的編碼主要方法有哪些最佳碼的編碼主要方法有哪些? 香農(nóng)（香農(nóng)（Shannon）、費諾（）、費諾（Fano）、哈夫曼（）、哈夫曼（Huffman）編）編碼等。碼等。 3.5 最佳編碼最佳編碼1.1.霍夫曼編碼霍夫曼編碼（一）二進制的霍夫曼編碼（一）二進制的霍夫曼編碼 把信源發(fā)出的把信源發(fā)出的n n個消息按其概率遞減次序排列個消息按其概率遞減次序排列 把概率最小的兩個消息分別編成把概率最小的兩個消息分別編成“1”1”和和“0”0”碼元碼元( (即把概率較大的消息即把概率較大的消息編為編為“1”1”，概率較小的消息編為，概率較小的消息編為“0”0”

19、；或反之也可；或反之也可),),并對這兩個消息求并對這兩個消息求概率之和概率之和 把上述的概率和作為一個新消息的概率，再與原來的其他消息按概率遞減把上述的概率和作為一個新消息的概率，再與原來的其他消息按概率遞減的次序排列的次序排列 重復上述編碼步驟與，直到概率和是重復上述編碼步驟與，直到概率和是1 1為止為止 從最終的編碼步驟，在各個消息編碼方向線的逆行程順序地取下所編出的從最終的編碼步驟，在各個消息編碼方向線的逆行程順序地取下所編出的碼元，構(gòu)成相應的代碼組碼元，構(gòu)成相應的代碼組例：例：0.170.010.200.190.100.150.180.110000001111110.260.350.

20、390.611.01101000010010011011113422433710.2 20.19 20.18 3 0.17 3 0.15 3 0.1 40.01 42.72iiP 碼元碼元/符號符號16. 2)(log)()(712iiixPxPXHbit/bit/符號符號()2.160.962.72H XR bit/bit/碼元碼元%96由上可得代碼組的平均長度為：由上可得代碼組的平均長度為： 所以，信息傳輸速率所以，信息傳輸速率R為：為： 編碼效率編碼效率為：為：例：已知信源例：已知信源X X的概率空間，的概率空間， 用霍夫曼編碼方法找出各消息的代碼組，并計算編碼效率用霍夫曼編碼方法找出各

21、消息的代碼組，并計算編碼效率。 解解1 1：X X，P(X)P(X)X1， X2， X3， X4，X50.40.4， 0.10.1， 0.20.2， 0.20.2，0.10.10.10.20.20.10.4x1x3x4x2x5010111001.0101110110000322320.20.40.6 由題意可得：由題意可得：122. 21 . 0log1 . 022 . 0log2 . 024 . 0log4 . 0)(log)()(22251 iiixPxPXHbit/bit/符號符號510.4 20.2 2 20.1 3 22.2iiiP 碼元碼元/符號符號()2.1220.96452.2

22、H XR bit/bit/碼元碼元%45.96 解解2 2：0.10.20.20.10.4x1x3x4x2x5010001111.011010101100111412430.20.40.20.6510.4 1 0.2 20.2 3 0.1 2 42.2iiiP 碼元碼元/符號符號51222)()(iiiiKKxpKKE定義碼字長度的方差定義碼字長度的方差2：2222220.4(1 2.2)0.2(22.2)0.2(32.2)0.1(42.2)21.36222210.4(22.2)0.2(22.2)20.1(3 2.2)20.16 兩種編法的平均碼長相同兩種編法的平均碼長相同,所以編碼效率相同。

23、所以編碼效率相同。討論：哪種方法更好？討論：哪種方法更好？在哈夫曼編碼過程中在哈夫曼編碼過程中,對縮減信源符號按概率由大到對縮減信源符號按概率由大到小的順序重新排列時小的順序重新排列時,應使合并后的應使合并后的新符號盡可能新符號盡可能排在靠前排在靠前的位置的位置, 。這樣可使合并后的新符號重。這樣可使合并后的新符號重復編碼次數(shù)減少復編碼次數(shù)減少,使短碼得到充分利用。使短碼得到充分利用。2、第一種方法編出的第一種方法編出的5個碼字只有兩種不同的碼長，第個碼字只有兩種不同的碼長，第二種方法編出的碼字有二種方法編出的碼字有4種不同的碼長，因此種不同的碼長，因此第一種編碼第一種編碼方法更簡單、更容易實

24、現(xiàn)方法更簡單、更容易實現(xiàn),所以更好。所以更好。1、第一種編碼方法的碼方差要小許多。也就是說第一種、第一種編碼方法的碼方差要小許多。也就是說第一種編碼方法的碼長變化較小編碼方法的碼長變化較小,比較接近于平均碼長。比較接近于平均碼長。二、二、m 進制進制霍夫曼霍夫曼編碼編碼1. 編碼步驟編碼步驟同二進制，但需注意兩點同二進制，但需注意兩點 (1) 每次取最小的每次取最小的m個概率個概率,分別賦以分別賦以0,1,m-1； (2) 為使平均碼長最短，當對應的碼樹為非全樹時，為使平均碼長最短，當對應的碼樹為非全樹時， 第一次采用小于第一次采用小于m個概率個概率，此后每次均用，此后每次均用m個概率個概率2

25、. 非全樹時的編碼非全樹時的編碼 (1) 全樹全樹 碼樹中碼樹中,每個中間節(jié)點的每個中間節(jié)點的后續(xù)枝數(shù)必為后續(xù)枝數(shù)必為m (2) 非全樹非全樹碼樹中碼樹中,有些中間節(jié)點的后續(xù)枝數(shù)不足有些中間節(jié)點的后續(xù)枝數(shù)不足m三進制三進制滿樹滿樹（等長碼）（等長碼）三進制全樹三進制全樹（少一根即（少一根即為非全樹）為非全樹）(3) m進制的全樹的終端節(jié)點數(shù)進制的全樹的終端節(jié)點數(shù)(即時碼個數(shù)即時碼個數(shù)) m + k(m-1), k = 0,1,2,. (每從一個節(jié)點分出每從一個節(jié)點分出m枝枝, 就增加就增加m-1個終端個終端)(4) 當當 n m+k(m-1)時時, 令令 s = m+k(m-1)-n, s(m

26、-1)為構(gòu)成全樹所缺少的碼字為構(gòu)成全樹所缺少的碼字(分支分支)數(shù)。數(shù)。(5) 非全樹時的非全樹時的霍夫曼霍夫曼編碼編碼 第一次第一次取最小概率時，只取最小概率時，只取取 m-s 個個, 分別賦以分別賦以0,1,2,m-s-1。此后每次都取。此后每次都取m個個 X X P(X ) P(X )X1, X2, X3, X4, X5, X6, X7, X80.40, 0.18, 0.1, 0.1, 0.07, 0.06, 0.05, 0.04例：例： 對下列信源作三進制霍夫曼編碼對下列信源作三進制霍夫曼編碼(1)分析分析 n=8, m=3, m + k(m-1)=3+2k, 取取k = 3，得，得s=

27、1.于是于是m-s=2，即第一次取兩個概率。，即第一次取兩個概率。(2)編碼編碼0.090.220.381.00120121 x5 0.0722 x6 0.06200 x7 0.05201 x8 0.0411 x3 0.112 x4 0.110 x2 0.18 0 x1 0.40012012(3)說明說明平均碼長平均碼長編碼效率編碼效率 = 95.2%1.69/K 碼符號 信源符號2.費諾編碼費諾編碼1)將信源消息符號按其出現(xiàn)的概率大小依次排列為將信源消息符號按其出現(xiàn)的概率大小依次排列為np.pp212)將依次排列的信源符號按概率值分為兩組，使劃分后的兩個組的概將依次排列的信源符號按概率值分為

28、兩組，使劃分后的兩個組的概率之和近似相同，并對各組賦予一個二進制碼元率之和近似相同，并對各組賦予一個二進制碼元0和和13)將每一大組的信源符號再分成兩組，使劃分后的兩個組的概率之將每一大組的信源符號再分成兩組，使劃分后的兩個組的概率之和近似相同，并對各組賦予一個二進制符號和近似相同，并對各組賦予一個二進制符號0和和1。4)如此重復，直至每個組只剩下一個信源符號為止。如此重復，直至每個組只剩下一個信源符號為止。5)信源符號所對應的碼字即為費諾碼（按順序）。信源符號所對應的碼字即為費諾碼（按順序）。 X X P(X ) P(X )X1, X2, X3, X4, X5, X6, X7, 0.20,

29、0.19, 0.18, 0.17, 0.15, 0.10, 0.01例：對下列信源進行費諾編碼例：對下列信源進行費諾編碼xiP(xi)第一次分組第二次分組第三次分組第四次分組二元碼字碼長KiX10.20 0 0 00 2X20.19 1 0 010 3X30.18 1 011 3X40.17 1 0 10 2X50.15 1 0 110 3X60.10 1 0 1110 4X70.01 1 1111 4 費諾碼的平均碼長費諾碼的平均碼長 信息傳輸速率信息傳輸速率 編碼效率：編碼效率： = 95.3% 碼元比特/ 953. 074. 261. 2)(KXHR符號碼元 / 74. 2)(71iii

30、KxpK)()()()(321NxPxPxPxP 1)(log)(logiiixPKxP說明說明 i=1時，時， pi =0 i=2時，時， pi = p(x1) i=3時，時， pi = p(x2) + p(x1)根據(jù)式根據(jù)式 計算第計算第i個消息的二進個消息的二進制代碼組的長度制代碼組的長度 Ki (取正整數(shù)取正整數(shù))為了編出唯一可譯碼組，首先計算出第為了編出唯一可譯碼組，首先計算出第i個消息的累加概率個消息的累加概率 (即不包括即不包括 Xi 本身的前本身的前(i-1)個消息的累加概率個消息的累加概率)，再，再把把 Pi 變換成二進制小數(shù)，取小數(shù)點后的變換成二進制小數(shù)，取小數(shù)點后的 Ki

31、 位數(shù)作為第位數(shù)作為第i個消個消息的代碼組息的代碼組 3.香農(nóng)編碼香農(nóng)編碼 把信源發(fā)出的把信源發(fā)出的N個消息按其概率遞減的次序排列，得個消息按其概率遞減的次序排列，得 11ikkiPP例：設信源有例：設信源有7個符號，其二進制香農(nóng)編碼過程如下個符號，其二進制香農(nóng)編碼過程如下消息序號i消息概率累加概率iP代碼組長度ib二進制代碼組12345670.200.190.180.170.150.100.0100.20.390.570.740.890.992.342.412.482.562.743.346.66333334700000101110010111101111110)(ixP)(logixPKi

32、小結(jié)小結(jié)1.香農(nóng)碼香農(nóng)碼,費諾碼費諾碼,霍夫曼碼均考慮了信源概率分布特性霍夫曼碼均考慮了信源概率分布特性 大概率用短碼，因而平均碼長短，稱為大概率用短碼，因而平均碼長短，稱為最佳編碼。最佳編碼。2.三者中，以三者中，以霍夫曼碼最好霍夫曼碼最好，應用廣泛。，應用廣泛。3.局限性局限性均需預知概率分布均需預知概率分布，主要用于無記憶信源。，主要用于無記憶信源。3.4 3.4 游程編碼游程編碼 游程（游程（Run-Length，簡記，簡記RL）是指符號序列中各個符號）是指符號序列中各個符號連續(xù)重復出現(xiàn)而形成符號串的長度，又稱游程長度或游連續(xù)重復出現(xiàn)而形成符號串的長度，又稱游程長度或游長。長。游程編碼

33、（游程編碼（Run-Length Coding，簡記，簡記RLC）就是將原始）就是將原始符號序列映射成游程長度和對應符號序列的位置的標志符號序列映射成游程長度和對應符號序列的位置的標志序列。如果知道了游程長度和對應符號序列的位置的標序列。如果知道了游程長度和對應符號序列的位置的標志序列，就可以完全恢復出原來的符號序列。志序列，就可以完全恢復出原來的符號序列。一、術語一、術語游程游程序列中，相連的同種元素的統(tǒng)稱序列中，相連的同種元素的統(tǒng)稱游程長度游程長度同種元素的長度同種元素的長度(連碼個數(shù)連碼個數(shù))游程游程(長度長度)序列序列由游程長度構(gòu)成的序列由游程長度構(gòu)成的序列游程長度編碼游程長度編碼對游

34、程長度序列進行編碼對游程長度序列進行編碼 游程編碼特別適用于對相關信源的編碼。對二元相關信源，游程編碼特別適用于對相關信源的編碼。對二元相關信源，其輸出序列往往會出現(xiàn)多個連續(xù)的其輸出序列往往會出現(xiàn)多個連續(xù)的“0”或連續(xù)的或連續(xù)的“1”。在信。在信源輸出的二元序列中，連續(xù)出現(xiàn)的源輸出的二元序列中，連續(xù)出現(xiàn)的“0”符號稱為符號稱為“0游程游程”，連續(xù)出現(xiàn)的連續(xù)出現(xiàn)的“1”符號稱為符號稱為“1游程游程”，對應連續(xù)同一符號的，對應連續(xù)同一符號的個數(shù)分別稱為個數(shù)分別稱為“0”游程長度和游程長度和“1游程游程”長度，游程長度是長度，游程長度是隨機的，其取值可以是隨機的，其取值可以是1，2，3，。 對二元序

35、列，對二元序列，“0”游程和游程和“1游程游程”總是交替出現(xiàn)的，如果總是交替出現(xiàn)的，如果規(guī)定二元序列是以規(guī)定二元序列是以“0”開始的，那么第一個游程是開始的，那么第一個游程是“0”游程，游程，第二個游程必為第二個游程必為“1”游程，第三個游程又是游程，第三個游程又是“0”游程等等。游程等等。將任何二元序列變換成游程長度序列，這種變換是一一對應將任何二元序列變換成游程長度序列，這種變換是一一對應的，因此是可逆的、無失真的。的，因此是可逆的、無失真的。1. 例例 0 0 0 1 0 1 1 1 0 0 1 0 0 0 1原序列原序列(二元二元) 3 1 1 3 2 1 3 1游程序列游程序列 2.

36、 說明說明(1) 可逆可逆(2) 規(guī)定：從規(guī)定：從“0”游程開始游程開始(此后交替此后交替)(3) 游程序列為多元序列，游程序列為多元序列， 可用霍夫曼編碼等方法進行編碼可用霍夫曼編碼等方法進行編碼(4) 原則上亦可用于原則上亦可用于m元序列，但需增設標志位，因而減小了壓元序列，但需增設標志位，因而減小了壓縮比縮比 由于游程長度可從由于游程長度可從“1”直到無窮大，這在碼字的選直到無窮大，這在碼字的選擇和碼表的建立方面都有困難，實際應用時尚需采擇和碼表的建立方面都有困難，實際應用時尚需采取某些措施來改進。例如：線性碼取某些措施來改進。例如：線性碼碼字長度正碼字長度正比于游程長度的編碼。比于游程

37、長度的編碼。MH編碼編碼: MH編碼是一維編碼方案，它是一行一行的對文編碼是一維編碼方案，它是一行一行的對文件傳真數(shù)據(jù)進行編碼。件傳真數(shù)據(jù)進行編碼。 MH編碼將游程編碼和霍編碼將游程編碼和霍夫曼碼相結(jié)合，是一種改進的霍夫曼碼。夫曼碼相結(jié)合，是一種改進的霍夫曼碼。 文件傳真是指一般文件、圖紙、手寫稿、表格、文件傳真是指一般文件、圖紙、手寫稿、表格、報紙等文件的傳真，這種信源是黑白二值的，也報紙等文件的傳真，這種信源是黑白二值的，也即信源為二元信源。即信源為二元信源。對黑白二值文件傳真，每一行由連續(xù)出現(xiàn)的對黑白二值文件傳真，每一行由連續(xù)出現(xiàn)的“白（用碼符號白（用碼符號0表示）像素表示）像素”或連續(xù)出現(xiàn)或連續(xù)出現(xiàn)“黑（用碼符號黑（用碼符號1表示）像素表示）像素”組組成。成。MH碼分別對碼分別對“黑黑”、“白白