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

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

rs計(jì)算電路

se

譯碼表

r-

e電路....... rc一、循環(huán)碼譯碼的原理線性分組碼的譯碼：標(biāo)準(zhǔ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)碼的特殊性簡(jiǎ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)的電路實(shí)現(xiàn)。這樣可把n級(jí)寄存器降為n-k級(jí)。

一、循環(huán)碼譯碼的原理----利用循環(huán)碼的特殊性簡(jiǎ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相等？再編一次碼送過(guò)來(lái)的監(jiān)督位在接收端重新生成的監(jiān)督位一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路系統(tǒng)碼的譯碼一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路定理2（定理6.1.1）：設(shè)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）：設(shè)s(x)是r(x)的伴隨式，令f(x)xr(x)(modxn-1),則f(x)的伴隨式s1(x)xs(x)(modg(x))。

因此，若對(duì)r(x)循環(huán)移位，所對(duì)應(yīng)的伴隨式相當(dāng)于在除以g(x)電路中無(wú)輸入右移一位。推論1（推論6.1.1）：設(shè)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)碼的譯碼電路------梅吉特譯碼法（只糾一個(gè)錯(cuò)）計(jì)算s(x)電路(除以g(x))

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

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

作為判斷信息位錯(cuò)誤圖樣是否是Q(x)的條件（充分條件未證）。e(x)=Q(x)xn-k+s(x)-sI(x)對(duì)于戈萊碼：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五、捕錯(cuò)譯碼----改正捕錯(cuò)譯碼法s(x)e(x)五、捕錯(cuò)譯碼----改正捕錯(cuò)譯碼法w(s(x)-sI(x))t-w(Q(x))信息元無(wú)錯(cuò):w(Q1(x))=0;信息元有錯(cuò):w(Qi(x))=1. i=2,3判斷 w(s(x)-sI0)3w(s(x))3

w(s(x)-sIi)2 i=1,2 信息位的錯(cuò)誤圖樣為x11Qi(x)。 w(s(x))>3且w(s(x)-sIi(x))2嵩忠雄譯碼法(圖6-8，p203頁(yè)）。五、捕錯(cuò)譯碼----改正捕錯(cuò)譯碼法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ù)邏輯譯碼----原理對(duì)錯(cuò)誤圖樣進(jìn)行監(jiān)督，變換H為H使新的s的sn-k-1,sn-k-1,…,s0對(duì)e的某一位都作監(jiān)督，而對(duì)其它位只監(jiān)督一次。定義1（定義6.3.1)

若對(duì)H的行進(jìn)行線性組合變換為H0,使H0的每行某一特定位n-i都為1，而其它位只在其中一行為1，則稱(chēng)H為正交于n-i位的正交一致校驗(yàn)矩陣，n-i稱(chēng)為正交碼元位。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ù)邏輯譯碼----原理對(duì)錯(cuò)誤圖樣進(jìn)行監(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個(gè)為1;若e6=1,ei=1,ei=0,i,j=0,…,5,且

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

i,j,k互不相等，則s0，s1，s2最多只有2個(gè)為1，1個(gè)為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個(gè)為1;若e6=1,ei=1,ei=0,i,j=0,…,5,且

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

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

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

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

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

=

en-1+……sJ-2

=

en-1+…………s0

=

en-1+……en-1=1,最多只有[J/2]-1個(gè)si為0，大部分si仍為1en-1=0,最多只有[J/2]個(gè)si為1根據(jù)s0，s1,…,sJ中為1的數(shù)目是否多于一半對(duì)正交位糾錯(cuò)。一步大數(shù)邏輯可譯碼不多。t(n-1)/2(dev-1)dev:對(duì)偶碼的距離，要小六、大數(shù)邏輯譯碼----原理定理4（定理6.3.1)一個(gè)循六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼分兩步，第一步先確定錯(cuò)誤發(fā)生在某些碼元位， 第二步再?gòu)倪@些碼元位中確定是哪一個(gè)具體的位。定義2對(duì)H的行進(jìn)行線性變換為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次，則說(shuō)sJ-1,sJ-2,…,s0在集合{ci1,ci2,…,cil

}上正交，稱(chēng)sJ-1,sJ-2,…,s0為該集合的正交一致校驗(yàn)和式。六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼分兩步，第一步先確定六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼[7，4，3]循環(huán)漢明碼第1步：確定錯(cuò)誤發(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確定錯(cuò)誤是否發(fā)生在e6,e4中確定錯(cuò)誤是否發(fā)生在e6,e5中第2步：確定錯(cuò)誤發(fā)生在e6上s31

=e6+e4s30

=e6+e5確定錯(cuò)誤是否發(fā)生在e6上六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼[7，4，3]循環(huán)漢六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器（二）大數(shù)邏輯譯碼器1.I類(lè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ù)門(mén)＝2可檢2個(gè)錯(cuò)六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器s2=s3 六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器二步大數(shù)邏輯譯碼器（7,4,3)循環(huán)漢明碼，二步大數(shù)邏輯譯碼，P211頁(yè)圖6-11六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器二步大數(shù)邏輯譯碼器（7六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器2.II類(lèi)大數(shù)邏輯譯碼器由r(x)和H求s(x)s(x)=r(x)HT六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器2.II類(lèi)大數(shù)邏輯譯六、大數(shù)邏輯譯碼----大數(shù)邏輯可譯碼的構(gòu)造（三）大數(shù)邏輯可譯碼的構(gòu)造1.極長(zhǎng)碼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為對(duì)偶碼碼字hn-k-1,hn-k-2,…,h0線性組合，為對(duì)偶碼另一碼字h六、大數(shù)邏輯譯碼----大數(shù)邏輯可譯碼的構(gòu)造（三）大數(shù)邏輯可六、大數(shù)邏輯譯碼----極長(zhǎng)碼對(duì)偶碼互為零空間，碼字可用作對(duì)偶碼的監(jiān)督和式，因此可尋找一些特殊的對(duì)偶碼組，符合大數(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ù)邏輯譯碼的原則，又對(duì)偶碼互為零空間，這樣的碼字多項(xiàng)式是其對(duì)偶碼的監(jiān)督和式，所以漢明碼的這一組碼字可以用來(lái)作其對(duì)偶碼的譯碼，其對(duì)偶碼是大數(shù)邏輯可譯碼，叫極長(zhǎng)碼，共有n-1個(gè)xi(i=0,..,n-2)，J=（n-1）/2六、大數(shù)邏輯譯碼----極長(zhǎng)碼對(duì)偶碼互為零空間，碼字可用作對(duì)六、大數(shù)邏輯譯碼----極長(zhǎng)碼以F2上的m次本原多項(xiàng)式p*(x)生成[2m-1,2m-1-m,3]漢明碼，由于所以生成循環(huán)碼。定理5（定義6.4.1）設(shè)xn-1=g(x)p(x),其中p(x)為本原多項(xiàng)式，則g(x)生成的(n,m)循環(huán)碼是一個(gè)完備的正交碼，最小距離為dmin=2m-1

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

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

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

rs計(jì)算電路

se

譯碼表

r-

e電路....... rc一、循環(huán)碼譯碼的原理線性分組碼的譯碼：標(biāo)準(zhǔ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)碼的特殊性簡(jiǎ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)的電路實(shí)現(xiàn)。這樣可把n級(jí)寄存器降為n-k級(jí)。

一、循環(huán)碼譯碼的原理----利用循環(huán)碼的特殊性簡(jiǎ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相等？再編一次碼送過(guò)來(lái)的監(jiān)督位在接收端重新生成的監(jiān)督位一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路系統(tǒng)碼的譯碼一、循環(huán)碼譯碼的原理----求循環(huán)碼的伴隨式電路定理2（定理6.1.1）：設(shè)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）：設(shè)s(x)是r(x)的伴隨式，令f(x)xr(x)(modxn-1),則f(x)的伴隨式s1(x)xs(x)(modg(x))。

因此，若對(duì)r(x)循環(huán)移位，所對(duì)應(yīng)的伴隨式相當(dāng)于在除以g(x)電路中無(wú)輸入右移一位。推論1（推論6.1.1）：設(shè)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)碼的譯碼電路------梅吉特譯碼法（只糾一個(gè)錯(cuò)）計(jì)算s(x)電路(除以g(x))

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

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

作為判斷信息位錯(cuò)誤圖樣是否是Q(x)的條件（充分條件未證）。e(x)=Q(x)xn-k+s(x)-sI(x)對(duì)于戈萊碼：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五、捕錯(cuò)譯碼----改正捕錯(cuò)譯碼法s(x)e(x)五、捕錯(cuò)譯碼----改正捕錯(cuò)譯碼法w(s(x)-sI(x))t-w(Q(x))信息元無(wú)錯(cuò):w(Q1(x))=0;信息元有錯(cuò):w(Qi(x))=1. i=2,3判斷 w(s(x)-sI0)3w(s(x))3

w(s(x)-sIi)2 i=1,2 信息位的錯(cuò)誤圖樣為x11Qi(x)。 w(s(x))>3且w(s(x)-sIi(x))2嵩忠雄譯碼法(圖6-8，p203頁(yè)）。五、捕錯(cuò)譯碼----改正捕錯(cuò)譯碼法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ù)邏輯譯碼----原理對(duì)錯(cuò)誤圖樣進(jìn)行監(jiān)督，變換H為H使新的s的sn-k-1,sn-k-1,…,s0對(duì)e的某一位都作監(jiān)督，而對(duì)其它位只監(jiān)督一次。定義1（定義6.3.1)

若對(duì)H的行進(jìn)行線性組合變換為H0,使H0的每行某一特定位n-i都為1，而其它位只在其中一行為1，則稱(chēng)H為正交于n-i位的正交一致校驗(yàn)矩陣，n-i稱(chēng)為正交碼元位。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ù)邏輯譯碼----原理對(duì)錯(cuò)誤圖樣進(jìn)行監(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個(gè)為1;若e6=1,ei=1,ei=0,i,j=0,…,5,且

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

i,j,k互不相等，則s0，s1，s2最多只有2個(gè)為1，1個(gè)為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個(gè)為1;若e6=1,ei=1,ei=0,i,j=0,…,5,且

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

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

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

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

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

=

en-1+……sJ-2

=

en-1+…………s0

=

en-1+……en-1=1,最多只有[J/2]-1個(gè)si為0，大部分si仍為1en-1=0,最多只有[J/2]個(gè)si為1根據(jù)s0，s1,…,sJ中為1的數(shù)目是否多于一半對(duì)正交位糾錯(cuò)。一步大數(shù)邏輯可譯碼不多。t(n-1)/2(dev-1)dev:對(duì)偶碼的距離，要小六、大數(shù)邏輯譯碼----原理定理4（定理6.3.1)一個(gè)循六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼分兩步，第一步先確定錯(cuò)誤發(fā)生在某些碼元位， 第二步再?gòu)倪@些碼元位中確定是哪一個(gè)具體的位。定義2對(duì)H的行進(jìn)行線性變換為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次，則說(shuō)sJ-1,sJ-2,…,s0在集合{ci1,ci2,…,cil

}上正交，稱(chēng)sJ-1,sJ-2,…,s0為該集合的正交一致校驗(yàn)和式。六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼分兩步，第一步先確定六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼[7，4，3]循環(huán)漢明碼第1步：確定錯(cuò)誤發(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確定錯(cuò)誤是否發(fā)生在e6,e4中確定錯(cuò)誤是否發(fā)生在e6,e5中第2步：確定錯(cuò)誤發(fā)生在e6上s31

=e6+e4s30

=e6+e5確定錯(cuò)誤是否發(fā)生在e6上六、大數(shù)邏輯譯碼----二步大數(shù)邏輯譯碼[7，4，3]循環(huán)漢六、大數(shù)邏輯譯碼----大數(shù)邏輯譯碼器（二）大數(shù)邏輯譯碼器1.I類(lè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ù)門(mén)＝2