教學(xué)第一章無損信源編碼課件

第一章

無損信源編碼塊碼，序列碼，通用碼。1.信息熵和信源編碼定理2.赫夫曼編碼3.游程編碼4.冗余位編碼

1第一章

無損信源編碼1信息熵和信源編碼定理（1）1.信息熵計算公式x0,x1…..xr…x∈A={a1,a2…am}H0=log2mbitH1=-∑p(x)logp(x)H2=-∑p(x0)∑P(x1|x0)logP(x1|x0)…….Hk+1=-∑p(x0,x1..xk-1)∑P(xk|x0,x1..xk-1)logP(xk|x0,x1..xk-1)2信息熵和信源編碼定理（1）1.信息熵計算公式2信息熵和信源編碼定理（2）H0H1….Hk…...H(x0,x1..xk-1)=-∑p(x0,x1..xk-1)logp(x0,x1..xk-1)極限熵H=LimHk=LimH(x0,x1..xk-1)/kk無限2.等長碼的編碼定理碼字同樣長有利于傳輸?shù)湫托蛄小猘r出現(xiàn)Spr次.3信息熵和信源編碼定理（2）H0H1….信息熵和信源編碼定理(3)當(dāng)S趨于無限，非典型序列出現(xiàn)的概率趨于零?？芍痪庍@些序列，差錯接近零。典型序列個數(shù)是N=S!/∏(Spr)！用斯斗林公式S!=(S/e)S√(2πS)每個信源符號所需碼長是(S→∝)liml=lim(logN)/S=-∑prlogpr

4信息熵和信源編碼定理(3)當(dāng)S趨于無限，非典型序列出現(xiàn)的概率熵和信信息源編碼定理(4)S有限時有失真，可容忍時S已很大。

很難實現(xiàn)。

3.變長碼的編碼定理可分離的必要條件是異前置性。碼樹結(jié)構(gòu)(根，葉，節(jié)，枝）R0001115熵和信信息源編碼定理(4)S有限時有失真，可容忍信息熵和信源編碼定理(5)一個長為li的碼字占2L-li個長為L的碼字。Kraft不等式：∑2L-li≤2L，∑2-li≤1可分離的充要條件?？赏茝V到k進(jìn)碼。若li=-logpi

-logpi≦l<1-logpi,

6信息熵和信源編碼定理(5)一個長為li的碼字占2L信息熵和信源編碼定理(6)∑2-li≦∑pi=1,可以編碼,平均碼長l，有-∑pilogpi≦l=∑lipi<1-∑pilogpi,SH1≦Sl<1+SH1,S→∝,l→H1,這就是變長碼編碼定理，得證。對于相關(guān)信源，可把一段（長S）序列作為一個符號，有mS個碼字,進(jìn)行編碼。7信息熵和信源編碼定理(6)∑2-li≦∑pi=1,可以編赫夫曼編碼（1）1.概述從仙農(nóng)碼到赫夫曼碼

例xia1a2a3a4a5pi0.40.30.20.050.05li22355碼字00011001010010101Ra1(00)a2(01)a3(100)a4(10100)a5(10101)8赫夫曼編碼（1）1.概述從仙農(nóng)碼到赫夫曼碼Ra赫夫曼編碼(2)這是仙農(nóng)碼，非滿樹，可改進(jìn)。平均碼長l=2.5,H=1.95編碼效率η=H/l=78%不先規(guī)定碼長的費諾碼0(a1,a4,a5)0(a1)001(a4,a5)0(a4)0101(a5)0111(a2,a3)0(a2)101(a3)119赫夫曼編碼(2)這是仙農(nóng)碼，非滿樹，可改進(jìn)。9赫夫曼編碼(3)l1=l2=l3=2,l4=l5=3,l=2.1=93%另一種編法：0(a1)01(a2,a3,a4,a5)0(a2)101(a3,a4,a5)0(a3)1101(a4,a5)0(a4)11101(a5)111110赫夫曼編碼(3)l1=l2=l3=2,l4赫夫曼編碼(4)

l1=1,l2=2,l3=3,l4=l5=4,l=2.0,=97.5%如何達(dá)到最佳，導(dǎo)出赫夫曼碼2.編碼步驟：先按概率大小排隊，作為葉。把最小兩個賦予0和1，合成一個節(jié)點再排隊，直至只剩一個根。用上例來編赫夫曼碼：11赫夫曼編碼(4)赫夫曼編碼（5）a2,a3,a4,a5(0.6)a1(0.4)R1a2(0.3)00a3(0.2)a3,a4,a5(0.3)010a4(o.05)a4,a5(0.1)0110a5(0.05)0111l1=1,l2=2,l3=3,l4=l5=4l=2.0=97.5%1010011012赫夫曼編碼（5）赫夫曼編碼(6)用數(shù)學(xué)歸納法可證明其最佳性。若T(m-1)為m-1元編碼時的最佳樹，它必為滿樹，需將一葉分裂為二以構(gòu)成T(m)。平均碼長增加

l=(pm+pm-1)(lm-1+1-lm-1)=pm+pm-1,這已是最小，得證。

D=(pm-1+pm)(2lm-1+1),lm-1最小,向上排。13赫夫曼編碼(6)用數(shù)學(xué)歸納法可證明其最佳性。13赫夫曼編碼(7)3.推廣k進(jìn)碼，分裂一次增加k-1片葉，所以m=s(k-1)+k例：k=3a1(0.4)R0a2(0.3)1a3(0.2)a3a4a5(0.3)20a4(0.05)21a5(0.05)22滿樹01201214赫夫曼編碼(7)3.推廣01201214赫夫曼編碼(8)k=4,s=1,m=7a1(0.4)R0a2(0.3)1a3(0.2)2a4(0.05)a4,a5,a6,a7(0.1)30a5(0.05)31a6,a7(0)不用32，330121

30215赫夫曼編碼(8)k=4,s=1,m=7012赫夫曼編碼(9)k=3,l=1.3,=1.95/(1.3log3)=94.6%k=4,l=1.1,=1.95/(1.1log4)=88.6%k=5,l=1,=1.95/log5=84%

為了提高效率，需有m>>k,m=2時，能用并元來擴(kuò)大m，S個符號并成一個使m=2S。例：獨立二元序列p0=0.7,H=0.881,S=3

16赫夫曼編碼(9)k=3,l=1.3,=1.赫夫曼編碼(10)

符號概率碼字碼長符號概率碼字碼長0000.3430020110.063100040010.1471121010.0631001401000631010410000271.0114l=2.726/3=0.909,=0.881/0.909=96.9%增大S尚可進(jìn)一步提高效率。17赫夫曼編碼(10)符號概率碼字碼長赫夫曼編碼(11)并元還可部分解除相關(guān)性。若P(0|0)=0.97,P(0|1)=0.07,利用平穩(wěn)性，可得：p0=0.7,p1=0.30000.65900110.019511111110.259101100.0195110100010.020411000100.001471101101000.020411101010.0014711011118赫夫曼編碼(11)并元還可部分解除相關(guān)性。若18赫夫曼編碼(12)l=1.53/3=0.51<0.909=48.3%平均碼長更小，但效率下降，說明相關(guān)性未完全解除。4.缺點和措施兩大問題：a.變速輸出和恒速傳輸?shù)拿埽仨氂么鎯ζ鱽碚{(diào)整。存儲量的估計：19赫夫曼編碼(12)l=1.53/3=0.51<0赫夫曼編碼(13）若信源每秒輸出S個符號，符號的平均碼長為L比特，信道傳輸速率為R比特每秒，且R=SL,則T內(nèi)的必特數(shù)為x=∑ls,Ex=SLT=RT,令y=(x-Ex)/,2是ls的方差，T大時，y是標(biāo)準(zhǔn)正態(tài)變量，設(shè)存儲器容量為2A,開始為半滿，則取空和溢出的概率是

(-A)=p(y>A)=p(y<-A)20赫夫曼編碼(13）若信源每秒輸出S個符號，符號的平均赫夫曼編碼(14）根據(jù)要求的概率可選定A值,即得所需的存儲器容量。若R≠SL或起始存儲器非半滿，所需容量將增加。b.差錯擴(kuò)散問題差錯使碼字分離出錯而向后擴(kuò)散。最佳方案是全存儲和分段檢錯反問要求重發(fā)。21赫夫曼編碼(14）根據(jù)要求的概率可選定A值,即得所需游程編碼（1）另一種擴(kuò)展二元信源符號集的方法。1.游程和游程序列0游程，其長度l0=連0個數(shù)，1游程，其長度l1=連1個數(shù)。都是隨機(jī)變量，二元序列可變換成游程序列，例：000101110010001…3113213…22游程編碼（1）另一種擴(kuò)展二元信源符號集的方法。22游程編碼（2）二元時，若約定起始必為0游程，上列變換是可逆的。但對于多元序列不行。2.游程長度的概率特性獨立序列：p(l0)=p0l0-1p1,0游程必以10開始。El0=∑l0p(l0)=1/p1,H(l0)=-∑p(l0)logp(l0)=H(p0)/p1,23游程編碼（2）二元時，若約定起始必為0游程，上列游程編碼（3）

同理，El1=1/p0，H(l1)=H(p0)/p0,則對應(yīng)原序列的符號熵是H=[H(l0)+H(l1)]/(El0+El1)=H(p0)將0游程長度和1游程長度分別編赫夫曼碼(此時m>>2),可逼近H(l0)和H(l1)從而得到很高的編碼效率，比并元更易于實現(xiàn)，且能更好地解除相關(guān)性（一階和二階可全解除，更高階可減弱。這可說明如下：

24游程編碼（3）同理，El1=1/p0，H(l1游程編碼（4）1游程以下列形式開始:…x01y…,x與前一個0游程長度有關(guān)，y是與當(dāng)前1游程長度有關(guān)，對于一階或二階馬氏鏈，當(dāng)01一定時，y的概率已與x的取值無關(guān)，也就是當(dāng)前1游程的長度與前一個0游程的長度相互獨立，游程序列是獨立序列。它對應(yīng)于原序列的符號熵等于原序列的條件熵。計算這熵值也可得這一結(jié)果。25游程編碼（4）1游程以下列形式開始:…x01游程編碼（5）二元高階馬氏鏈通過游程變換雖不能完全解除相關(guān)性，但至少可降階，并減弱相關(guān)性。x010…101y中間ｋ個０1相間個符號。對于ｋ階馬氏鏈，ｙ的概率與ｘ取值無關(guān)，當(dāng)前的１游程只與前面ｋ-2個游程有關(guān),游程序列降至k-2階。不是０1相間時還要降得多。降階后的序列相關(guān)性也較弱。26游程編碼（5）二元高階馬氏鏈通過游程變換雖不能完游程編碼（6）3.實現(xiàn)問題：兩種游程分別編赫夫曼碼，兩個碼表。符號集中有無限個元，必須截止。令Ｎ=2n,l=1,2…2n-1各給一個碼字。l＞2n-1,用一個碼字C，2n→Ｃ00..0(n個0),2n+1→C00..1

27游程編碼（6）3.實現(xiàn)問題：27游程編碼（7）2n+1-1→C11..1,2n+1→C00..0C00..02n+1+1→C00..0C00..1………0游程的n可與1游程的n不同，0游程的C不但要與本碼表的碼字異前置，還要與1游程的碼表異前置。才能分辨C00..0C是0游程長度為2n，后面的C是1游程，還是0游程長度大于2n+1-1。28游程編碼（7）2n+1-1→C11..1,冗余位編碼（1）1.概述：冗余位---間隙固定碼位分成兩個序列傳送例x1,x2…xnyyyyyyxn+1,xn+2…xn+myyyy分成x1,x2…xn,xn+1…xn+m和11…..1000000111….10000可逆變換29冗余位編碼（1）1.概述：29冗余位編碼（2）后一序列通常是一階馬氏鏈，若P(0|0)=a,P(0|1)=b,則p0=a/(1-a+b),p1=/(1-b+a)H(y)=pH(a)+pH(b),H=H(y)+p1H(x)當(dāng)p1小時，可極大地壓縮碼率。但同時傳送兩個序列有困難，通常只好分段來編碼。30冗余位編碼（2）后一序列通常是一階馬氏鏈，若30冗余位編碼（3）2.L-D碼幀長N,信息位數(shù)Q,

nj是第j個信息位的位置0<n1<…<nO<N傳送Q和T兩個值，就可正確譯碼。若,則nQ=k+1

31冗余位編碼（3）2.L-D碼31冗余位編碼（4）

若,則nQ-1=l+1直至求得n1，就可恢復(fù)這一幀。

由

.

32冗余位編碼（4）32冗余位編碼（5）

這樣就可唯一地判定nQ,

以后的T’相當(dāng)于Q-1個信息位的情況。從而判定nQ-1.編一幀需比特33冗余位編碼（5）33冗余位編碼（6）

例：001000000010000N=15，Q=2，n1=3,n2=11,

需要4比特編Q,0010.需要7比特編T,0101111得碼字00100101111a3a11。

若Q=0或N,可只用4位碼：0000或1111

34冗余位編碼（6）例：001000000010000冗余位編碼（7）Q01234567T047911121313總碼長48111315161717壓縮率0.270.530.730.871.01.071.131.13Q小時才有效。平均編碼效率。3.信息位標(biāo)志碼上例可編為：0011a31011a110000

35冗余位編碼（7）Q01冗余位編碼（8）最后四個0是分幀號，所需比特數(shù)是A=(Q+1)log(N+1)

也只適用于Q小時。平均編碼效率不如L-D碼4.非連1碼不分幀時表示冗余位長度可用非1連碼。L12345678910碼字01000110000001010100101

36冗余位編碼（8）最后四個0是分幀號，36冗余位編碼（9）例：011111110a1a2a310011110a4a5……表示4個冗余位（01），三個信息位（6個1，1個0），9個冗余位（100），兩個信息位(4個1，1個0）譯碼是唯一的。非連1碼的個數(shù)問題。37冗余位編碼（9）例：011111110a1a2a31冗余位編碼（10）設(shè)長度為k的碼字?jǐn)?shù)N(K），以0開始的有N(K-1)個，以1開始的有N(K-2)個，則N(K)=N(K-1)+N(K-2)N(1)=2,N(2)=3N(k)=[(1/2+√5/2)k+2-(1/2-√5/2)k+2]/√5N(k≦L)≈3(1.62)L.冗余位編碼的方法尚很多，以上僅舉例。38冗余位編碼（10）設(shè)長度為k的碼字?jǐn)?shù)N(K），以0開始第一章

無損信源編碼塊碼，序列碼，通用碼。1.信息熵和信源編碼定理2.赫夫曼編碼3.游程編碼4.冗余位編碼

39第一章

無損信源編碼1信息熵和信源編碼定理（1）1.信息熵計算公式x0,x1…..xr…x∈A={a1,a2…am}H0=log2mbitH1=-∑p(x)logp(x)H2=-∑p(x0)∑P(x1|x0)logP(x1|x0)…….Hk+1=-∑p(x0,x1..xk-1)∑P(xk|x0,x1..xk-1)logP(xk|x0,x1..xk-1)40信息熵和信源編碼定理（1）1.信息熵計算公式2信息熵和信源編碼定理（2）H0H1….Hk…...H(x0,x1..xk-1)=-∑p(x0,x1..xk-1)logp(x0,x1..xk-1)極限熵H=LimHk=LimH(x0,x1..xk-1)/kk無限2.等長碼的編碼定理碼字同樣長有利于傳輸?shù)湫托蛄小猘r出現(xiàn)Spr次.41信息熵和信源編碼定理（2）H0H1….信息熵和信源編碼定理(3)當(dāng)S趨于無限，非典型序列出現(xiàn)的概率趨于零?？芍痪庍@些序列，差錯接近零。典型序列個數(shù)是N=S!/∏(Spr)！用斯斗林公式S!=(S/e)S√(2πS)每個信源符號所需碼長是(S→∝)liml=lim(logN)/S=-∑prlogpr

42信息熵和信源編碼定理(3)當(dāng)S趨于無限，非典型序列出現(xiàn)的概率熵和信信息源編碼定理(4)S有限時有失真，可容忍時S已很大。

很難實現(xiàn)。

3.變長碼的編碼定理可分離的必要條件是異前置性。碼樹結(jié)構(gòu)(根，葉，節(jié)，枝）R00011143熵和信信息源編碼定理(4)S有限時有失真，可容忍信息熵和信源編碼定理(5)一個長為li的碼字占2L-li個長為L的碼字。Kraft不等式：∑2L-li≤2L，∑2-li≤1可分離的充要條件?？赏茝V到k進(jìn)碼。若li=-logpi

-logpi≦l<1-logpi,

44信息熵和信源編碼定理(5)一個長為li的碼字占2L信息熵和信源編碼定理(6)∑2-li≦∑pi=1,可以編碼,平均碼長l，有-∑pilogpi≦l=∑lipi<1-∑pilogpi,SH1≦Sl<1+SH1,S→∝,l→H1,這就是變長碼編碼定理，得證。對于相關(guān)信源，可把一段（長S）序列作為一個符號，有mS個碼字,進(jìn)行編碼。45信息熵和信源編碼定理(6)∑2-li≦∑pi=1,可以編赫夫曼編碼（1）1.概述從仙農(nóng)碼到赫夫曼碼

例xia1a2a3a4a5pi0.40.30.20.050.05li22355碼字00011001010010101Ra1(00)a2(01)a3(100)a4(10100)a5(10101)46赫夫曼編碼（1）1.概述從仙農(nóng)碼到赫夫曼碼Ra赫夫曼編碼(2)這是仙農(nóng)碼，非滿樹，可改進(jìn)。平均碼長l=2.5,H=1.95編碼效率η=H/l=78%不先規(guī)定碼長的費諾碼0(a1,a4,a5)0(a1)001(a4,a5)0(a4)0101(a5)0111(a2,a3)0(a2)101(a3)1147赫夫曼編碼(2)這是仙農(nóng)碼，非滿樹，可改進(jìn)。9赫夫曼編碼(3)l1=l2=l3=2,l4=l5=3,l=2.1=93%另一種編法：0(a1)01(a2,a3,a4,a5)0(a2)101(a3,a4,a5)0(a3)1101(a4,a5)0(a4)11101(a5)111148赫夫曼編碼(3)l1=l2=l3=2,l4赫夫曼編碼(4)

l1=1,l2=2,l3=3,l4=l5=4,l=2.0,=97.5%如何達(dá)到最佳，導(dǎo)出赫夫曼碼2.編碼步驟：先按概率大小排隊，作為葉。把最小兩個賦予0和1，合成一個節(jié)點再排隊，直至只剩一個根。用上例來編赫夫曼碼：49赫夫曼編碼(4)赫夫曼編碼（5）a2,a3,a4,a5(0.6)a1(0.4)R1a2(0.3)00a3(0.2)a3,a4,a5(0.3)010a4(o.05)a4,a5(0.1)0110a5(0.05)0111l1=1,l2=2,l3=3,l4=l5=4l=2.0=97.5%1010011050赫夫曼編碼（5）赫夫曼編碼(6)用數(shù)學(xué)歸納法可證明其最佳性。若T(m-1)為m-1元編碼時的最佳樹，它必為滿樹，需將一葉分裂為二以構(gòu)成T(m)。平均碼長增加

l=(pm+pm-1)(lm-1+1-lm-1)=pm+pm-1,這已是最小，得證。

D=(pm-1+pm)(2lm-1+1),lm-1最小,向上排。51赫夫曼編碼(6)用數(shù)學(xué)歸納法可證明其最佳性。13赫夫曼編碼(7)3.推廣k進(jìn)碼，分裂一次增加k-1片葉，所以m=s(k-1)+k例：k=3a1(0.4)R0a2(0.3)1a3(0.2)a3a4a5(0.3)20a4(0.05)21a5(0.05)22滿樹01201252赫夫曼編碼(7)3.推廣01201214赫夫曼編碼(8)k=4,s=1,m=7a1(0.4)R0a2(0.3)1a3(0.2)2a4(0.05)a4,a5,a6,a7(0.1)30a5(0.05)31a6,a7(0)不用32，330121

30253赫夫曼編碼(8)k=4,s=1,m=7012赫夫曼編碼(9)k=3,l=1.3,=1.95/(1.3log3)=94.6%k=4,l=1.1,=1.95/(1.1log4)=88.6%k=5,l=1,=1.95/log5=84%

為了提高效率，需有m>>k,m=2時，能用并元來擴(kuò)大m，S個符號并成一個使m=2S。例：獨立二元序列p0=0.7,H=0.881,S=3

54赫夫曼編碼(9)k=3,l=1.3,=1.赫夫曼編碼(10)

符號概率碼字碼長符號概率碼字碼長0000.3430020110.063100040010.1471121010.0631001401000631010410000271.0114l=2.726/3=0.909,=0.881/0.909=96.9%增大S尚可進(jìn)一步提高效率。55赫夫曼編碼(10)符號概率碼字碼長赫夫曼編碼(11)并元還可部分解除相關(guān)性。若P(0|0)=0.97,P(0|1)=0.07,利用平穩(wěn)性，可得：p0=0.7,p1=0.30000.65900110.019511111110.259101100.0195110100010.020411000100.001471101101000.020411101010.0014711011156赫夫曼編碼(11)并元還可部分解除相關(guān)性。若18赫夫曼編碼(12)l=1.53/3=0.51<0.909=48.3%平均碼長更小，但效率下降，說明相關(guān)性未完全解除。4.缺點和措施兩大問題：a.變速輸出和恒速傳輸?shù)拿?，必須用存儲器來調(diào)整。存儲量的估計：57赫夫曼編碼(12)l=1.53/3=0.51<0赫夫曼編碼(13）若信源每秒輸出S個符號，符號的平均碼長為L比特，信道傳輸速率為R比特每秒，且R=SL,則T內(nèi)的必特數(shù)為x=∑ls,Ex=SLT=RT,令y=(x-Ex)/,2是ls的方差，T大時，y是標(biāo)準(zhǔn)正態(tài)變量，設(shè)存儲器容量為2A,開始為半滿，則取空和溢出的概率是

(-A)=p(y>A)=p(y<-A)58赫夫曼編碼(13）若信源每秒輸出S個符號，符號的平均赫夫曼編碼(14）根據(jù)要求的概率可選定A值,即得所需的存儲器容量。若R≠SL或起始存儲器非半滿，所需容量將增加。b.差錯擴(kuò)散問題差錯使碼字分離出錯而向后擴(kuò)散。最佳方案是全存儲和分段檢錯反問要求重發(fā)。59赫夫曼編碼(14）根據(jù)要求的概率可選定A值,即得所需游程編碼（1）另一種擴(kuò)展二元信源符號集的方法。1.游程和游程序列0游程，其長度l0=連0個數(shù)，1游程，其長度l1=連1個數(shù)。都是隨機(jī)變量，二元序列可變換成游程序列，例：000101110010001…3113213…60游程編碼（1）另一種擴(kuò)展二元信源符號集的方法。22游程編碼（2）二元時，若約定起始必為0游程，上列變換是可逆的。但對于多元序列不行。2.游程長度的概率特性獨立序列：p(l0)=p0l0-1p1,0游程必以10開始。El0=∑l0p(l0)=1/p1,H(l0)=-∑p(l0)logp(l0)=H(p0)/p1,61游程編碼（2）二元時，若約定起始必為0游程，上列游程編碼（3）

同理，El1=1/p0，H(l1)=H(p0)/p0,則對應(yīng)原序列的符號熵是H=[H(l0)+H(l1)]/(El0+El1)=H(p0)將0游程長度和1游程長度分別編赫夫曼碼(此時m>>2),可逼近H(l0)和H(l1)從而得到很高的編碼效率，比并元更易于實現(xiàn)，且能更好地解除相關(guān)性（一階和二階可全解除，更高階可減弱。這可說明如下：

62游程編碼（3）同理，El1=1/p0，H(l1游程編碼（4）1游程以下列形式開始:…x01y…,x與前一個0游程長度有關(guān)，y是與當(dāng)前1游程長度有關(guān)，對于一階或二階馬氏鏈，當(dāng)01一定時，y的概率已與x的取值無關(guān)，也就是當(dāng)前1游程的長度與前一個0游程的長度相互獨立，游程序列是獨立序列。它對應(yīng)于原序列的符號熵等于原序列的條件熵。計算這熵值也可得這一結(jié)果。63游程編碼（4）1游程以下列形式開始:…x01游程編碼（5）二元高階馬氏鏈通過游程變換雖不能完全解除相關(guān)性，但至少可降階，并減弱相關(guān)性。x010…101y中間ｋ個０1相間個符號。對于ｋ階馬氏鏈，ｙ的概率與ｘ取值無關(guān)，當(dāng)前的１游程只與前面ｋ-2個游程有關(guān),游程序列降至k-2階。不是０1相間時還要降得多。降階后的序列相關(guān)性也較弱。64游程編碼（5）二元高階馬氏鏈通過游程變換雖不能完游程編碼（6）3.實現(xiàn)問題：兩種游程分別編赫夫曼碼，兩個碼表。符號集中有無限個元，必須截止。令Ｎ=2n,l=1,2…2n-1各給一個碼字。l＞2n-1,用一個碼字C，2n→Ｃ00..0(n個0),2n+1→C00..1

65游程編碼（6）3.實現(xiàn)問題：27游程編碼（7）2n+1-1→C11..1,2n+1→C00..0C00..02n+1+1→C00..0C00..1………0游程的n可與1游程的n不同，0游程的C不但要與本碼表的碼字異前置，還要與1游程的碼表異前置。才能分辨C00..0C是0游程長度為2n，后面的C是1游程，還是0游程長度大于2n+1-1。66游程編碼（7）2n+1-1→C11..1,冗余位編碼（1）1.概述：冗余位---間隙固定碼位分成兩個序列傳送例x1,x2…xnyyyyyyxn+1,xn+2…xn+myyyy分成x1,x2…xn,xn+1…xn+m和11…..1000000111….10000可逆變換67冗余位編碼（1）1.概述：29冗余位編碼（2）后一序列通常是一階馬氏鏈，若P(0|0)=a,P(0|1)=b,則p0=a/(1-a+b),