現(xiàn)代信息理論編碼與技術chapter6課件

第六章循環(huán)碼的譯碼陸以勤2005年5月第六章循環(huán)碼的譯碼陸以勤1一、循環(huán)碼譯碼的原理線性分組碼的譯碼：標準陣列譯碼，伴隨式譯碼 譯碼電路復雜

rs計算電路

se

譯碼表

r-

e電路....... rc一、循環(huán)碼譯碼的原理線性分組碼的譯碼：標準陣列譯碼，伴隨式譯一、循環(huán)碼譯碼的原理----線性分組碼中求伴隨式的電路例1：[7,4,3]循環(huán)漢明碼，g(x)=x3+x+1,H=111010001110101101001s=rHT=(r6r5r4r3r2r1r0)Tr6+

r5+

r4+

r2r5+

r4+

r3+

r1r6+

r5+

r3+

r0=T=（

s2s1s0)

111010001110101101001一、循環(huán)碼譯碼的原理----線性分組碼中求伴隨式的電路例1：一、循環(huán)碼譯碼的原理----利用循環(huán)碼的特殊性簡化電路s

rHTH=[-PTIn-k]=[-(r1(x))T-(r2(x))T…

-(rk(x))TIn-k]其中，ri(x)-xn-i(modg(x))(i=1,2,...,k)。modg(x)s

rHTr(modg(x))s(x)r(x)(c(x)+e(x))e(x)(modg(x))定理1：由g(x)生成的循環(huán)碼，r(x)的伴隨式s(x)滿足： s(x)r(x)e(x)(modg(x))

因此，求S(x)可用除以g(x)的電路實現(xiàn)。這樣可把n級寄存器降為n-k級。

一、循環(huán)碼譯碼的原理----利用循環(huán)碼的特殊性簡化電路s一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路例1：[7,4,3]循環(huán)漢明碼，g(x)=x3+x+1,H=111010001110101101001直接從H求s利用除以g(x)電路求s(x)一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路例1：[7,一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路系統(tǒng)碼的譯碼通常含有編碼電路..........mk-1mk-2m0cn-1=mk-1cn-2=mk-2cn-k=m0cn-k-1cn-k-2....c0求監(jiān)督位..............求監(jiān)督位rn-1rn-2rn-krn-1rn-krn-2......rn-k-1r0rn-k-1r0rn-k-1r0r

n-k-2相等？再編一次碼送過來的監(jiān)督位在接收端重新生成的監(jiān)督位一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路系統(tǒng)碼的譯碼一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路定理2（定理6.1.1）：設s(x)是r(x)的伴隨式，令f(x)xr(x)(modxn-1),則f(x)的伴隨式s1(x)xs(x)(modg(x))。證明（課本證明不好）：

r(x)=rn-1xn-1+rn-2xn-2+….+r1x+r0

xr(x)=rn-1xn+rn-2xn-1+….+r1x2+r0x

f(x)=rn-2xn-1+rn-3xn-2+….+r1x2+r0x+rn-1

=-rn-1xn+xr(x)+rn-1

=-rn-1(xn-1)+xr(x)=-rn-1h(x)g(x)+x(a(x)g(x)+s(x))=-rn-1h(x)g(x)+xa(x)g(x)+xs(x)=(-rn-1h(x)+xa(x))g(x)+xs(x)s1(x)f(x)xs(x)(modg(x))。一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路定理2（定理一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路定理2（定理6.1.1）：設s(x)是r(x)的伴隨式，令f(x)xr(x)(modxn-1),則f(x)的伴隨式s1(x)xs(x)(modg(x))。

因此，若對r(x)循環(huán)移位，所對應的伴隨式相當于在除以g(x)電路中無輸入右移一位。推論1（推論6.1.1）：設s(x)是r(x)的伴隨式，令rj(x)xjr(x)(modxn-1)(j=0,1,…n-1),則ri(x)的伴隨式sj(x)xjs(x)(modg(x))。a(x)Fq[x]:rj(x)a(x)r(x)(modxn-1)的伴隨式sj(x)a(x)s(x)(modg(x))。一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路定理2（定理二、循環(huán)碼的譯碼電路------梅吉特譯碼法（只糾一個錯）計算s(x)電路(除以g(x))

s(x)e(x)(判別最高位是否有錯）

r(x)緩沖....... r(x)c(x)++

r(x)=rn-1xn-1+rn-2xn-2+…+r1x+r0

x((rn-1+1)xn-1+rn-2xn-2+…+r1x+r0)=x(r(x)+xn-1) xr(x)+1(modxn-1-1)除以g(x)s(x)xs(x)+1如果錯誤發(fā)生在最高位，由于接收字不是碼字，所以伴隨式不為0，可以通過其伴隨式與糾錯后（是一個碼字）的關系將其校正。如果錯誤不發(fā)生在最高位，而是發(fā)生在次高位，通過將其循環(huán)移位就可以將錯誤圖樣移到最高位，而且伴隨式可通過剛求出的伴隨式通過移位的方法求出。rn-1有錯，糾正相當于s(x)移位后加1二、循環(huán)碼的譯碼電路------梅吉特譯碼法（只糾一個錯）計二、循環(huán)碼的譯碼電路------梅吉特譯碼法（系統(tǒng)碼）系統(tǒng)碼只糾信息位的錯二、循環(huán)碼的譯碼電路------梅吉特譯碼法（系統(tǒng)碼）系統(tǒng)碼二、循環(huán)碼的譯碼電路------梅吉特譯碼法（只糾一個錯）例1：[7,4,3]循環(huán)漢明碼，g(x)=x3+x+1,H=111010001110101101001二、循環(huán)碼的譯碼電路------梅吉特譯碼法（只糾一個錯）例二、循環(huán)碼的譯碼電路------梅吉特譯碼法（系統(tǒng)碼）P195頁開始，門1開，門2關。移位4次后，門1關，使4級緩沖器停止移位，g(x)除法電路再移位3次可求出s(x)。此時門2開，把上邊g(x)除法電路中的伴隨式送到下面的伴隨式計算電路中，隨即關閉門2，且上邊g(x)除法電路立即清0。門1再次打開，4級緩沖器一邊送出第1組的信息，一邊接收第2組r(x)的前k位。與此同時，上邊的伴隨式電路計算第2組的r(x)的伴隨式，而下邊的伴隨式計算電路，對第一組r(x)的信息元進行糾錯。（注意，圖6-2（A）的虛線是縮短循環(huán)碼，見P197）二、循環(huán)碼的譯碼電路------梅吉特譯碼法（系統(tǒng)碼）P19三、擴展?jié)h明碼的譯碼0110ss0/s1/s20101t3,不能糾錯t=1，可以糾錯t2，不能糾錯無錯三、擴展?jié)h明碼的譯碼0110ss0/s1/s20四、縮短循環(huán)碼的譯碼緩存：k->k-ir(x)先移位i次四、縮短循環(huán)碼的譯碼緩存：k->k-i五、捕錯譯碼----原理原理如果確知錯誤集中在檢驗位，則去掉后面的檢驗位即可。s(x)r(x)e(x)eI(x)+ep(x)ep(x)modg(x)由于s(x)<n-k,ep(x)<n-k,g(x)=n-k所以s(x)=e(x)=ep(x)伴隨式等于錯誤圖樣。111最嚴重的情況，t個錯誤均勻分布，相隔n/tn信息位k要使t個錯誤集中在校驗位，則要k<n/t定理3：糾t個錯誤的GF(q)上的[n,k]循環(huán)碼，捕錯譯碼過程（即循環(huán)移位）中已把t個錯誤集中在最低n-k位以內(nèi)的充要條件是w(si(x))<=t,其中si為伴隨式。如果不在監(jiān)督位，只要集中在一起，循環(huán)移位后變成xkr(x).監(jiān)督位n-k五、捕錯譯碼----原理原理111最嚴重的情況，t個錯誤均勻五、捕錯譯碼----兩種簡單捕錯譯碼法2.兩種簡單捕錯譯碼法第1類捕錯譯碼法第2類捕錯譯碼法把接收到r(x)自動乘以xn-k,再進入g(x)的除法電路計算伴隨式，即對r(x)的前rn-1至rk位的錯誤進行糾正。對系統(tǒng)碼來說，可以一邊糾錯一邊送出已糾正的信息元。五、捕錯譯碼----兩種簡單捕錯譯碼法2.兩種簡單捕錯譯碼五、捕錯譯碼----改正捕錯譯碼法3.改進捕錯譯碼法（戈萊碼及其嵩忠雄譯碼法)戈萊Golay碼（23，12，7）是唯一能糾多個錯的2元完備碼。其擴展碼（24，12，8）用于ITU-TH.324中完備碼？對于錯誤圖樣e(x)=x22+x11（圖中打叉的兩個點）或e(x)=x17+x11+x6（圖中三個空心園點）,不能通過循環(huán)移位把所有的錯誤移動11個監(jiān)督位中，所以不能采用簡單的捕錯譯碼法。戈萊碼采用嵩忠雄改進的捕錯譯碼法。通過將接收矢量在譯碼器中進行循環(huán)移位，使信息位上至多存在一個錯誤，其余的錯誤都移到監(jiān)督位上。對于任何可糾的錯誤圖樣，經(jīng)過i次移位，都可使信息位上不多于1個錯誤，并且只需三個多項式就能包括信息位的這個錯誤圖樣。=1+23+23*22/2+23*22*21/(2*3)=1+23+23*11+23*77=1+23(1+11+77)=1+23*89=2048223-12=211=2048五、捕錯譯碼----改正捕錯譯碼法3.改進捕錯譯碼法（戈萊五、捕錯譯碼----改正捕錯譯碼法s(x)e(x)eI(x)+ep(x)sI(x)+ep(x)modg(x)從r(x)求出已知從eI(x)求出ep(x)

s(x)-sI(x)modg(x) ep(x)=s(x)-sI(x) (1)eI(x)=Q(x)xn-ksI(x)modg(x) (2)e(x)=eI(x)+ep(x)=Q(x)xn-k+ep(x) ep(x)=e(x)-Q(x)xn-kw(ep(x))=w(e(x))-w(Q(x))t-w(Q(x)) 由（1）式得w(ep(x))=

w(s(x)-sI(x))，所以w(s(x)-sI(x))t-w(Q(x))

作為判斷信息位錯誤圖樣是否是Q(x)的條件（充分條件未證）。e(x)=Q(x)xn-k+s(x)-sI(x)對于戈萊碼：Q1(x)=0,Q2(x)=x5,Q3(x)=x6。取g(x)=x11+x10+x6+x5+x4+x2+1由（2）可得：sI1=0sI2=x9+x8+x6+x5+x2+xsI3=x10+x9+x7+x6+x3+x2五、捕錯譯碼----改正捕錯譯碼法s(x)e(x)五、捕錯譯碼----改正捕錯譯碼法w(s(x)-sI(x))t-w(Q(x))信息元無錯:w(Q1(x))=0;信息元有錯:w(Qi(x))=1. i=2,3判斷 w(s(x)-sI0)3w(s(x))3

w(s(x)-sIi)2 i=1,2 信息位的錯誤圖樣為x11Qi(x)。 w(s(x))>3且w(s(x)-sIi(x))2嵩忠雄譯碼法(圖6-8，p203頁）。五、捕錯譯碼----改正捕錯譯碼法w(s(x)-sI(x)六、大數(shù)邏輯譯碼（一）原理sn-k-1

=

en-1hn-k-1,n-1+en-2hn-k-1,n-2+…+e0hn-k-1,0sn-k-2

=

en-1hn-k-2,n-1+en-2hn-k-2,n-2+…+e0hn-k-2,0……sj

=

en-1hj,n-1+en-2hj,n-2+…+e0hi,0……s0

=

en-1h0,n-1+en-2h0,n-2+…+e0h0,0六、大數(shù)邏輯譯碼（一）原理sn-k-1=en-1hn-k六、大數(shù)邏輯譯碼----原理對錯誤圖樣進行監(jiān)督，變換H為H使新的s的sn-k-1,sn-k-1,…,s0對e的某一位都作監(jiān)督，而對其它位只監(jiān)督一次。定義1（定義6.3.1)

若對H的行進行線性組合變換為H0,使H0的每行某一特定位n-i都為1，而其它位只在其中一行為1，則稱H為正交于n-i位的正交一致校驗矩陣，n-i稱為正交碼元位。sn-k-1

=

en-1hn-k-1,n-1+en-2hn-k-1,n-2+…+e0hn-k-1,0sn-k-2

=

en-1hn-k-2,n-1+en-2hn-k-2,n-2+…+e0hn-k-2,0……sj

=

en-1hj,n-1+en-2hj,n-2+…+e0hi,0……s0

=

en-1h0,n-1+en-2h0,n-2+…+e0h0,0六、大數(shù)邏輯譯碼----原理對錯誤圖樣進行監(jiān)督，變換H為H六、大數(shù)邏輯譯碼----原理例：[7，3，4]碼，H=101|1000111|0100110|0010011|0001相加H0=101|1000110|0010100|0101s

=(s2,s1,s0

)=(e6,e5,e4,e3,e2,e1,e0

)

101|1000110|0010100|0101s2=s3 =e6

+e4+e3s1=s1 =e6

+e5 +e1 s0=s2+s0=e6

+e2+e0若e6=1,ei=0,i=0,…,5,則s0=s1=s2=1;若e6=0,ei=1,ei=0,i,j=0,…,5,且

ij，則s0，s1，s2只有1個為1;若e6=1,ei=1,ei=0,i,j=0,…,5,且

ij，則s0，s1，s2有2個為1，1個為0;若e6=0,ei=ei=1,ek=0,i,j,k=0,…,5,且

i,j,k互不相等，則s0，s1，s2最多只有2個為1，1個為0。t=1t=2六、大數(shù)邏輯譯碼----原理例：[7，3，4]碼，H=10六、大數(shù)邏輯譯碼----原理若e6=1,ei=0,i=0,…,5,則s0=s1=s2=1;若e6=0,ei=1,ei=0,i,j=0,…,5,且

ij，則s0，s1，s2只有1個為1;若e6=1,ei=1,ei=0,i,j=0,…,5,且

ij，則s0，s1，s2有2個為1，1個為0;若e6=0,ei=ei=1,ek=0,i,j,k=0,…,5,且

i,j,k互不相等，則s0，s1，s2最多只有2個為1，1個為0。若e6=1,且t=1,則s0，s1，s2有2個或2個以上為1；若e61,且t=1,則s0，s1，s2有小于2個為1。根據(jù)s0，s1，s2中為1的個數(shù)決定e6是否有錯，因為是循環(huán)碼，可以循環(huán)至下一位（判斷e5,e4,e3,e2,e1,e0

是否有錯）。這叫一步大數(shù)邏輯譯碼。定理4（定理6.3.1)

一個循環(huán)碼若能建立J個正交一致校驗和式，則該碼能糾正t[J/2]個錯誤，其中[x]表示取x的整數(shù)部分。六、大數(shù)邏輯譯碼----原理若e6=1,ei=0,i=0六、大數(shù)邏輯譯碼----原理定理4（定理6.3.1)

一個循環(huán)碼若能建立J個正交一致校驗和式，則該碼能糾正t[J/2]個錯誤，其中[x]表示取x的整數(shù)部分。sJ-1

=

en-1+……sJ-2

=

en-1+…………s0

=

en-1+……en-1=1,最多只有[J/2]-1個si為0，大部分si仍為1en-1=0,最多只有[J/2]個si為1根據(jù)s0，s1,…,sJ中為1的數(shù)目是否多于一半對正交位糾錯。一步大數(shù)邏輯可譯碼不多。t(n-1)/2(dev-1)dev:對偶碼的距離，要小六、大數(shù)邏輯譯碼----原理定理4（定理6.3.1)一個循六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼分兩步，第一步先確定錯誤發(fā)生在某些碼元位， 第二步再從這些碼元位中確定是哪一個具體的位。定義2對H的行進行線性變換為H0,H0的伴隨式為（sJ-1,sJ-2,…,s0

）。若某一碼元集合{ci1,ci2,…,cil

}的線性組合 ai1ci1+ai2

ci2+…+ailcil

(aij0,j=1,…,l)在sJ-1,sJ-2,…,s0中出現(xiàn)，而其余碼元位置集合至多在其中某一sj(0jJ-1)出現(xiàn)1次，則說sJ-1,sJ-2,…,s0在集合{ci1,ci2,…,cil

}上正交，稱sJ-1,sJ-2,…,s0為該集合的正交一致校驗和式。六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼分兩步，第一步先確定六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼[7，4，3]循環(huán)漢明碼第1步：確定錯誤發(fā)生在e6,e5,e4上s11=s2 =（e6+e4）

+e3

+e2s10=s1 =（e6+e4）

+e5

+e1s21=s1 =（e6+e5）

+e4

+e1s20=s2+s0 =（e6+e5）

+e2

+e0確定錯誤是否發(fā)生在e6,e4中確定錯誤是否發(fā)生在e6,e5中第2步：確定錯誤發(fā)生在e6上s31

=e6+e4s30

=e6+e5確定錯誤是否發(fā)生在e6上六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼[7，4，3]循環(huán)漢六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器（二）大數(shù)邏輯譯碼器1.I類大數(shù)邏輯譯碼器由s(x)r(x)(modg(x))求s(x)),一步大數(shù)邏輯譯碼器六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器（二）大數(shù)邏輯譯碼器六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器s2=s3 =e6

+e4+e3s1=s1 =e6

+e5 +e1 s0=s2+s0=e6

+e2+e0例：[7，3，4]碼g(x)=x4+x3+x2+1但大數(shù)門＝2可檢2個錯六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器s2=s3 六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器二步大數(shù)邏輯譯碼器（7,4,3)循環(huán)漢明碼，二步大數(shù)邏輯譯碼，P211頁圖6-11六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器二步大數(shù)邏輯譯碼器（7六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器2.II類大數(shù)邏輯譯碼器由r(x)和H求s(x)s(x)=r(x)HT六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器2.II類大數(shù)邏輯譯六、大數(shù)邏輯譯碼----大數(shù)邏輯可譯碼的構造（三）大數(shù)邏輯可譯碼的構造1.極長碼s=(sn-k-1sn-k-2…s0)sn-k-1=ehn-k-1sn-k-2=ehn-k-2......s0=eh0內(nèi)積sn-k-1=an-k-1sn-k-1+an-k-2sn-k-2+…+a0s0=e(an-k-1hn-k-1+an-k-2hn-k-2+…+a0h0)=ehhn-k-1,hn-k-2,…,h0為對偶碼碼字hn-k-1,hn-k-2,…,h0線性組合，為對偶碼另一碼字h六、大數(shù)邏輯譯碼----大數(shù)邏輯可譯碼的構造（三）大數(shù)邏輯可六、大數(shù)邏輯譯碼----極長碼對偶碼互為零空間，碼字可用作對偶碼的監(jiān)督和式，因此可尋找一些特殊的對偶碼組，符合大數(shù)邏輯譯碼原則（都有最高位，其它位只出現(xiàn)1次）例如漢明碼由于最小距離為3，一定存在重量為3的碼字，取一些特殊的碼字。w1(x)=xn-1+xj1+xi1w2(x)=xn-1+xj2+xi2w1(x)w2(x)j1

j2

且i1

i2

反證，若j1=j2

w1(x)+w2(x)=xi1+xi2碼字重量小于3因此，這樣的碼字符合大數(shù)邏輯譯碼的原則，又對偶碼互為零空間，這樣的碼字多項式是其對偶碼的監(jiān)督和式，所以漢明碼的這一組碼字可以用來作其對偶碼的譯碼，其對偶碼是大數(shù)邏輯可譯碼，叫極長碼，共有n-1個xi(i=0,..,n-2)，J=（n-1）/2六、大數(shù)邏輯譯碼----極長碼對偶碼互為零空間，碼字可用作對六、大數(shù)邏輯譯碼----極長碼以F2上的m次本原多項式p*(x)生成[2m-1,2m-1-m,3]漢明碼，由于所以生成循環(huán)碼。定理5（定義6.4.1）設xn-1=g(x)p(x),其中p(x)為本原多項式，則g(x)生成的(n,m)循環(huán)碼是一個完備的正交碼，最小距離為dmin=2m-1

p(x)p*(x)（也是本原多項式）互反g(x)生成c(x) 生成[2m-1,2m-1-m,3]漢明碼以這些碼字組成集合，可作為正交監(jiān)督和式組d=3,必有重量為3的碼字六、大數(shù)邏輯譯碼----極長碼以F2上的m次本原多項式p*(關鍵，找方法：先由共有(n-1)/2個W(x),六、大數(shù)邏輯譯碼----極長碼關鍵，找方法：先由共有(n-1)/2個W(x),六、大數(shù)例：求m=4的一步完備正交極長碼的生成多項式及正交監(jiān)督和式解：查表取4次本原多項式六、大數(shù)邏輯譯碼----極長碼例：求m=4的一步完備正交極長碼的生成多項式及正交監(jiān)督解：查由此可寫出譯碼電路六、大數(shù)邏輯譯碼----極長碼由此可寫出譯碼電路六、大數(shù)邏輯譯碼----極長碼2差集循環(huán)碼（課本有錯）尋找特殊碼字作為對偶碼的監(jiān)督和式循環(huán)模模六、大數(shù)邏輯譯碼----差集循環(huán)碼2差集循環(huán)碼（課本有錯）尋找特殊碼字作為對偶碼的監(jiān)督和式為使上式只有相同，其余的次數(shù)不同，要求互不相同。設由又六、大數(shù)邏輯譯碼----差集循環(huán)碼為使上式只有相同，其余的次數(shù)不同，要求互不相同。設由又六、大可證，若（p為素數(shù)），則Z(x)為的反多項式差集個數(shù)n-1次J=q+1,共q＋1個校驗和式關鍵，找出叫q階完備差集六、大數(shù)邏輯譯碼----差集循環(huán)碼可證，若（p為素數(shù)），則Z(x)為的反多項式1)定義：完備差集令P=是一個q＋1階自然數(shù)集，并有若由P中元素構成的(q+1)q個（q＋1取2的排列）有序差集滿足:(1)D中所有正差（>0）互不相同

(2)D中所有負差（<0）互不相同

(3)任意兩個正差之和不等于q(q+1)+1則稱P為q階完備單差集（完備差集）不等于D中任何正差可見，D中所有q(q+1)+1個差模構成了1~q(q+1)的任何整數(shù)六、大數(shù)邏輯譯碼----差集循環(huán)碼1)定義：完備差集令P=是一個q＋1階自然數(shù)集，并有若由P辛格曾構成了階完備差集，P為素數(shù)，s為任意正整數(shù)，特別是階的完備差集（P218,表6-4，其中右邊一欄是P）2）由完備差集構成大數(shù)可譯碼設是一個階完備差集六、大數(shù)邏輯譯碼----差集循環(huán)碼辛格曾構成了階完備差集，P為素數(shù)六、大數(shù)邏輯譯碼----差集循環(huán)碼六、大數(shù)邏輯譯碼----差集循環(huán)碼第六章循環(huán)碼的譯碼陸以勤2005年5月第六章循環(huán)碼的譯碼陸以勤43一、循環(huán)碼譯碼的原理線性分組碼的譯碼：標準陣列譯碼，伴隨式譯碼 譯碼電路復雜

rs計算電路

se

譯碼表

r-

e電路....... rc一、循環(huán)碼譯碼的原理線性分組碼的譯碼：標準陣列譯碼，伴隨式譯一、循環(huán)碼譯碼的原理----線性分組碼中求伴隨式的電路例1：[7,4,3]循環(huán)漢明碼，g(x)=x3+x+1,H=111010001110101101001s=rHT=(r6r5r4r3r2r1r0)Tr6+

r5+

r4+

r2r5+

r4+

r3+

r1r6+

r5+

r3+

r0=T=（

s2s1s0)

111010001110101101001一、循環(huán)碼譯碼的原理----線性分組碼中求伴隨式的電路例1：一、循環(huán)碼譯碼的原理----利用循環(huán)碼的特殊性簡化電路s

rHTH=[-PTIn-k]=[-(r1(x))T-(r2(x))T…

-(rk(x))TIn-k]其中，ri(x)-xn-i(modg(x))(i=1,2,...,k)。modg(x)s

rHTr(modg(x))s(x)r(x)(c(x)+e(x))e(x)(modg(x))定理1：由g(x)生成的循環(huán)碼，r(x)的伴隨式s(x)滿足： s(x)r(x)e(x)(modg(x))

因此，求S(x)可用除以g(x)的電路實現(xiàn)。這樣可把n級寄存器降為n-k級。

一、循環(huán)碼譯碼的原理----利用循環(huán)碼的特殊性簡化電路s一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路例1：[7,4,3]循環(huán)漢明碼，g(x)=x3+x+1,H=111010001110101101001直接從H求s利用除以g(x)電路求s(x)一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路例1：[7,一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路系統(tǒng)碼的譯碼通常含有編碼電路..........mk-1mk-2m0cn-1=mk-1cn-2=mk-2cn-k=m0cn-k-1cn-k-2....c0求監(jiān)督位..............求監(jiān)督位rn-1rn-2rn-krn-1rn-krn-2......rn-k-1r0rn-k-1r0rn-k-1r0r

n-k-2相等？再編一次碼送過來的監(jiān)督位在接收端重新生成的監(jiān)督位一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路系統(tǒng)碼的譯碼一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路定理2（定理6.1.1）：設s(x)是r(x)的伴隨式，令f(x)xr(x)(modxn-1),則f(x)的伴隨式s1(x)xs(x)(modg(x))。證明（課本證明不好）：

r(x)=rn-1xn-1+rn-2xn-2+….+r1x+r0

xr(x)=rn-1xn+rn-2xn-1+….+r1x2+r0x

f(x)=rn-2xn-1+rn-3xn-2+….+r1x2+r0x+rn-1

=-rn-1xn+xr(x)+rn-1

=-rn-1(xn-1)+xr(x)=-rn-1h(x)g(x)+x(a(x)g(x)+s(x))=-rn-1h(x)g(x)+xa(x)g(x)+xs(x)=(-rn-1h(x)+xa(x))g(x)+xs(x)s1(x)f(x)xs(x)(modg(x))。一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路定理2（定理一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路定理2（定理6.1.1）：設s(x)是r(x)的伴隨式，令f(x)xr(x)(modxn-1),則f(x)的伴隨式s1(x)xs(x)(modg(x))。

因此，若對r(x)循環(huán)移位，所對應的伴隨式相當于在除以g(x)電路中無輸入右移一位。推論1（推論6.1.1）：設s(x)是r(x)的伴隨式，令rj(x)xjr(x)(modxn-1)(j=0,1,…n-1),則ri(x)的伴隨式sj(x)xjs(x)(modg(x))。a(x)Fq[x]:rj(x)a(x)r(x)(modxn-1)的伴隨式sj(x)a(x)s(x)(modg(x))。一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路定理2（定理二、循環(huán)碼的譯碼電路------梅吉特譯碼法（只糾一個錯）計算s(x)電路(除以g(x))

s(x)e(x)(判別最高位是否有錯）

r(x)緩沖....... r(x)c(x)++

r(x)=rn-1xn-1+rn-2xn-2+…+r1x+r0

x((rn-1+1)xn-1+rn-2xn-2+…+r1x+r0)=x(r(x)+xn-1) xr(x)+1(modxn-1-1)除以g(x)s(x)xs(x)+1如果錯誤發(fā)生在最高位，由于接收字不是碼字，所以伴隨式不為0，可以通過其伴隨式與糾錯后（是一個碼字）的關系將其校正。如果錯誤不發(fā)生在最高位，而是發(fā)生在次高位，通過將其循環(huán)移位就可以將錯誤圖樣移到最高位，而且伴隨式可通過剛求出的伴隨式通過移位的方法求出。rn-1有錯，糾正相當于s(x)移位后加1二、循環(huán)碼的譯碼電路------梅吉特譯碼法（只糾一個錯）計二、循環(huán)碼的譯碼電路------梅吉特譯碼法（系統(tǒng)碼）系統(tǒng)碼只糾信息位的錯二、循環(huán)碼的譯碼電路------梅吉特譯碼法（系統(tǒng)碼）系統(tǒng)碼二、循環(huán)碼的譯碼電路------梅吉特譯碼法（只糾一個錯）例1：[7,4,3]循環(huán)漢明碼，g(x)=x3+x+1,H=111010001110101101001二、循環(huán)碼的譯碼電路------梅吉特譯碼法（只糾一個錯）例二、循環(huán)碼的譯碼電路------梅吉特譯碼法（系統(tǒng)碼）P195頁開始，門1開，門2關。移位4次后，門1關，使4級緩沖器停止移位，g(x)除法電路再移位3次可求出s(x)。此時門2開，把上邊g(x)除法電路中的伴隨式送到下面的伴隨式計算電路中，隨即關閉門2，且上邊g(x)除法電路立即清0。門1再次打開，4級緩沖器一邊送出第1組的信息，一邊接收第2組r(x)的前k位。與此同時，上邊的伴隨式電路計算第2組的r(x)的伴隨式，而下邊的伴隨式計算電路，對第一組r(x)的信息元進行糾錯。（注意，圖6-2（A）的虛線是縮短循環(huán)碼，見P197）二、循環(huán)碼的譯碼電路------梅吉特譯碼法（系統(tǒng)碼）P19三、擴展?jié)h明碼的譯碼0110ss0/s1/s20101t3,不能糾錯t=1，可以糾錯t2，不能糾錯無錯三、擴展?jié)h明碼的譯碼0110ss0/s1/s20四、縮短循環(huán)碼的譯碼緩存：k->k-ir(x)先移位i次四、縮短循環(huán)碼的譯碼緩存：k->k-i五、捕錯譯碼----原理原理如果確知錯誤集中在檢驗位，則去掉后面的檢驗位即可。s(x)r(x)e(x)eI(x)+ep(x)ep(x)modg(x)由于s(x)<n-k,ep(x)<n-k,g(x)=n-k所以s(x)=e(x)=ep(x)伴隨式等于錯誤圖樣。111最嚴重的情況，t個錯誤均勻分布，相隔n/tn信息位k要使t個錯誤集中在校驗位，則要k<n/t定理3：糾t個錯誤的GF(q)上的[n,k]循環(huán)碼，捕錯譯碼過程（即循環(huán)移位）中已把t個錯誤集中在最低n-k位以內(nèi)的充要條件是w(si(x))<=t,其中si為伴隨式。如果不在監(jiān)督位，只要集中在一起，循環(huán)移位后變成xkr(x).監(jiān)督位n-k五、捕錯譯碼----原理原理111最嚴重的情況，t個錯誤均勻五、捕錯譯碼----兩種簡單捕錯譯碼法2.兩種簡單捕錯譯碼法第1類捕錯譯碼法第2類捕錯譯碼法把接收到r(x)自動乘以xn-k,再進入g(x)的除法電路計算伴隨式，即對r(x)的前rn-1至rk位的錯誤進行糾正。對系統(tǒng)碼來說，可以一邊糾錯一邊送出已糾正的信息元。五、捕錯譯碼----兩種簡單捕錯譯碼法2.兩種簡單捕錯譯碼五、捕錯譯碼----改正捕錯譯碼法3.改進捕錯譯碼法（戈萊碼及其嵩忠雄譯碼法)戈萊Golay碼（23，12，7）是唯一能糾多個錯的2元完備碼。其擴展碼（24，12，8）用于ITU-TH.324中完備碼？對于錯誤圖樣e(x)=x22+x11（圖中打叉的兩個點）或e(x)=x17+x11+x6（圖中三個空心園點）,不能通過循環(huán)移位把所有的錯誤移動11個監(jiān)督位中，所以不能采用簡單的捕錯譯碼法。戈萊碼采用嵩忠雄改進的捕錯譯碼法。通過將接收矢量在譯碼器中進行循環(huán)移位，使信息位上至多存在一個錯誤，其余的錯誤都移到監(jiān)督位上。對于任何可糾的錯誤圖樣，經(jīng)過i次移位，都可使信息位上不多于1個錯誤，并且只需三個多項式就能包括信息位的這個錯誤圖樣。=1+23+23*22/2+23*22*21/(2*3)=1+23+23*11+23*77=1+23(1+11+77)=1+23*89=2048223-12=211=2048五、捕錯譯碼----改正捕錯譯碼法3.改進捕錯譯碼法（戈萊五、捕錯譯碼----改正捕錯譯碼法s(x)e(x)eI(x)+ep(x)sI(x)+ep(x)modg(x)從r(x)求出已知從eI(x)求出ep(x)

s(x)-sI(x)modg(x) ep(x)=s(x)-sI(x) (1)eI(x)=Q(x)xn-ksI(x)modg(x) (2)e(x)=eI(x)+ep(x)=Q(x)xn-k+ep(x) ep(x)=e(x)-Q(x)xn-kw(ep(x))=w(e(x))-w(Q(x))t-w(Q(x)) 由（1）式得w(ep(x))=

w(s(x)-sI(x))，所以w(s(x)-sI(x))t-w(Q(x))

作為判斷信息位錯誤圖樣是否是Q(x)的條件（充分條件未證）。e(x)=Q(x)xn-k+s(x)-sI(x)對于戈萊碼：Q1(x)=0,Q2(x)=x5,Q3(x)=x6。取g(x)=x11+x10+x6+x5+x4+x2+1由（2）可得：sI1=0sI2=x9+x8+x6+x5+x2+xsI3=x10+x9+x7+x6+x3+x2五、捕錯譯碼----改正捕錯譯碼法s(x)e(x)五、捕錯譯碼----改正捕錯譯碼法w(s(x)-sI(x))t-w(Q(x))信息元無錯:w(Q1(x))=0;信息元有錯:w(Qi(x))=1. i=2,3判斷 w(s(x)-sI0)3w(s(x))3

w(s(x)-sIi)2 i=1,2 信息位的錯誤圖樣為x11Qi(x)。 w(s(x))>3且w(s(x)-sIi(x))2嵩忠雄譯碼法(圖6-8，p203頁）。五、捕錯譯碼----改正捕錯譯碼法w(s(x)-sI(x)六、大數(shù)邏輯譯碼（一）原理sn-k-1

=

en-1hn-k-1,n-1+en-2hn-k-1,n-2+…+e0hn-k-1,0sn-k-2

=

en-1hn-k-2,n-1+en-2hn-k-2,n-2+…+e0hn-k-2,0……sj

=

en-1hj,n-1+en-2hj,n-2+…+e0hi,0……s0

=

en-1h0,n-1+en-2h0,n-2+…+e0h0,0六、大數(shù)邏輯譯碼（一）原理sn-k-1=en-1hn-k六、大數(shù)邏輯譯碼----原理對錯誤圖樣進行監(jiān)督，變換H為H使新的s的sn-k-1,sn-k-1,…,s0對e的某一位都作監(jiān)督，而對其它位只監(jiān)督一次。定義1（定義6.3.1)

若對H的行進行線性組合變換為H0,使H0的每行某一特定位n-i都為1，而其它位只在其中一行為1，則稱H為正交于n-i位的正交一致校驗矩陣，n-i稱為正交碼元位。sn-k-1

=

en-1hn-k-1,n-1+en-2hn-k-1,n-2+…+e0hn-k-1,0sn-k-2

=

en-1hn-k-2,n-1+en-2hn-k-2,n-2+…+e0hn-k-2,0……sj

=

en-1hj,n-1+en-2hj,n-2+…+e0hi,0……s0

=

en-1h0,n-1+en-2h0,n-2+…+e0h0,0六、大數(shù)邏輯譯碼----原理對錯誤圖樣進行監(jiān)督，變換H為H六、大數(shù)邏輯譯碼----原理例：[7，3，4]碼，H=101|1000111|0100110|0010011|0001相加H0=101|1000110|0010100|0101s

=(s2,s1,s0

)=(e6,e5,e4,e3,e2,e1,e0

)

101|1000110|0010100|0101s2=s3 =e6

+e4+e3s1=s1 =e6

+e5 +e1 s0=s2+s0=e6

+e2+e0若e6=1,ei=0,i=0,…,5,則s0=s1=s2=1;若e6=0,ei=1,ei=0,i,j=0,…,5,且

ij，則s0，s1，s2只有1個為1;若e6=1,ei=1,ei=0,i,j=0,…,5,且

ij，則s0，s1，s2有2個為1，1個為0;若e6=0,ei=ei=1,ek=0,i,j,k=0,…,5,且

i,j,k互不相等，則s0，s1，s2最多只有2個為1，1個為0。t=1t=2六、大數(shù)邏輯譯碼----原理例：[7，3，4]碼，H=10六、大數(shù)邏輯譯碼----原理若e6=1,ei=0,i=0,…,5,則s0=s1=s2=1;若e6=0,ei=1,ei=0,i,j=0,…,5,且

ij，則s0，s1，s2只有1個為1;若e6=1,ei=1,ei=0,i,j=0,…,5,且

ij，則s0，s1，s2有2個為1，1個為0;若e6=0,ei=ei=1,ek=0,i,j,k=0,…,5,且

i,j,k互不相等，則s0，s1，s2最多只有2個為1，1個為0。若e6=1,且t=1,則s0，s1，s2有2個或2個以上為1；若e61,且t=1,則s0，s1，s2有小于2個為1。根據(jù)s0，s1，s2中為1的個數(shù)決定e6是否有錯，因為是循環(huán)碼，可以循環(huán)至下一位（判斷e5,e4,e3,e2,e1,e0

是否有錯）。這叫一步大數(shù)邏輯譯碼。定理4（定理6.3.1)

一個循環(huán)碼若能建立J個正交一致校驗和式，則該碼能糾正t[J/2]個錯誤，其中[x]表示取x的整數(shù)部分。六、大數(shù)邏輯譯碼----原理若e6=1,ei=0,i=0六、大數(shù)邏輯譯碼----原理定理4（定理6.3.1)

一個循環(huán)碼若能建立J個正交一致校驗和式，則該碼能糾正t[J/2]個錯誤，其中[x]表示取x的整數(shù)部分。sJ-1

=

en-1+……sJ-2

=

en-1+…………s0

=

en-1+……en-1=1,最多只有[J/2]-1個si為0，大部分si仍為1en-1=0,最多只有[J/2]個si為1根據(jù)s0，s1,…,sJ中為1的數(shù)目是否多于一半對正交位糾錯。一步大數(shù)邏輯可譯碼不多。t(n-1)/2(dev-1)dev:對偶碼的距離，要小六、大數(shù)邏輯譯碼----原理定理4（定理6.3.1)一個循六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼分兩步，第一步先確定錯誤發(fā)生在某些碼元位， 第二步再從這些碼元位中確定是哪一個具體的位。定義2對H的行進行線性變換為H0,H0的伴隨式為（sJ-1,sJ-2,…,s0

）。若某一碼元集合{ci1,ci2,…,cil

}的線性組合 ai1ci1+ai2

ci2+…+ailcil

(aij0,j=1,…,l)在sJ-1,sJ-2,…,s0中出現(xiàn)，而其余碼元位置集合至多在其中某一sj(0jJ-1)出現(xiàn)1次，則說sJ-1,sJ-2,…,s0在集合{ci1,ci2,…,cil

}上正交，稱sJ-1,sJ-2,…,s0為該集合的正交一致校驗和式。六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼分兩步，第一步先確定六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼[7，4，3]循環(huán)漢明碼第1步：確定錯誤發(fā)生在e6,e5,e4上s11=s2 =（e6+e4）

+e3

+e2s10=s1 =（e6+e4）

+e5

+e1s21=s1 =（e6+e5）

+e4

+e1s20=s2+s0 =（e6+e5）

+e2

+e0確定錯誤是否發(fā)生在e6,e4中確定錯誤是否發(fā)生在e6,e5中第2步：確定錯誤發(fā)生在e6上s31

=e6+e4s30

=e6+e5確定錯誤是否發(fā)生在e6上六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼[7，4，3]循環(huán)漢六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器（二）大數(shù)邏輯譯碼器1.I類大數(shù)邏輯譯碼器由s(x)r(x)(modg(x))求s(x)),一步大數(shù)邏輯譯碼器六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器（二）大數(shù)邏輯譯碼器六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器s2=s3 =e6

+e4+e3s1=s1 =e6

+e5 +e1 s0=s2+s0=e6

+e2+e0例：[7，3，4]碼g(x)=x4+x3+x2+1但大數(shù)門＝2