信息論第9章北理工

1線性碼的糾錯(cuò)及伴隨式①用校驗(yàn)矩陣編碼，也用校驗(yàn)矩陣譯碼：接收到一個(gè)接收字R后，校驗(yàn)H

RT=0T是否成立：若關(guān)系成立，則認(rèn)為R是一個(gè)碼字；否則判為碼字在傳輸中發(fā)生了錯(cuò)誤；H

RT的值是否為0是校驗(yàn)碼字出錯(cuò)與否的依據(jù)。②伴隨式/校驗(yàn)子：S=R

HT或ST=H

RT。③如何糾錯(cuò)？設(shè)發(fā)送碼矢C=(Cn－1,Cn－2,…,C0)信道錯(cuò)誤圖樣為E=(En－1,En－2,…,E0)，其中Ei=0，表示第i位無錯(cuò)；Ei=1，表示第i位有錯(cuò)。i=n－1,n－2,…,0。9.3.2伴隨式2接收字R為R=(Rn－1,Rn－2,…,R0)=C+E=(Cn－1+En－1,Cn－2+En－2,…,C0+E0)求接收字的伴隨式（接收字用監(jiān)督矩陣進(jìn)行檢驗(yàn)）

ST=H

RT=H

(C+E)T=H

CT+H

ET

(9.43)由于H

CT=0T，所以ST=H

ET設(shè)H=(h1,h2,…,hn)，其中hi表示H的列。代入式(9.43)得到3④總結(jié)伴隨式僅與錯(cuò)誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，即伴隨式僅由錯(cuò)誤圖樣決定；伴隨式是錯(cuò)誤的判別式：若S=0，則判為沒有出錯(cuò)，接收字是一個(gè)碼字；若S≠0，則判為有錯(cuò)。不同的錯(cuò)誤圖樣具有不同的伴隨式，它們是一一對應(yīng)的。對二元碼，伴隨式是H陣中與錯(cuò)誤碼元對應(yīng)列之和。4⑤舉例：(7,3)碼接收矢量R的伴隨式計(jì)算設(shè)發(fā)送碼矢C=1010011，接收碼字R＝1010011，R與C相同。5若接收字中有一位錯(cuò)誤6當(dāng)碼元錯(cuò)誤多于1個(gè)時(shí)7⑥伴隨式計(jì)算電路伴隨式的計(jì)算可用電路來實(shí)現(xiàn)。以(7,3)碼為例：設(shè)接收字為R=(R6R5R4R3R2R1R0)，伴隨式為根據(jù)上式可畫出伴隨式計(jì)算電路，如圖所示。8根據(jù)上式可畫出伴隨式計(jì)算電路，如圖所示。99.3.3漢明碼

常見的線形分組碼有重復(fù)碼，漢明碼，里德-穆勒碼，戈雷碼（1）漢明碼的構(gòu)造和譯碼漢明碼是漢明于1950年提出的糾一個(gè)錯(cuò)誤的線性碼，也是第一個(gè)糾錯(cuò)碼。由于它編碼簡單，因而是在通信系統(tǒng)和數(shù)據(jù)存儲系統(tǒng)中得到廣泛應(yīng)用的一類線性碼。10漢明碼的結(jié)構(gòu)參數(shù)：糾一個(gè)錯(cuò)誤的線性碼，其最小距離dmin=3；監(jiān)督矩陣任意兩列線性無關(guān)/H的任兩列互不相同；沒有全0的列。監(jiān)督元個(gè)數(shù)n－k=r；H陣中每列有r個(gè)元素，至多可構(gòu)成2r－1種互不相同的非0列。對于任意正整數(shù)r≥3，漢明碼的結(jié)構(gòu)參數(shù)為碼長：n=2r－1信息位數(shù)：k=2r－r－1監(jiān)督位數(shù)：r=n－k碼的最小距離：dmin=3(t=1)11例一個(gè)二元（7，4）Hamming碼的校驗(yàn)矩陣為

等價(jià)的編碼方程為

12生成矩陣為

13因?yàn)樾畔⒃猭=4,所以不同碼字有M=16漢明（7，4）碼00000000100101100001111001100001111010101010011001101001001011001100111010101111000000110010111100101101011111112024/6/23149.4.1循環(huán)碼的多項(xiàng)式描述9.4.2循環(huán)碼的生成多項(xiàng)式9.4循環(huán)碼2024/6/2315(1)循環(huán)碼的特點(diǎn)循環(huán)碼是線性分組碼的一個(gè)重要子類；由于循環(huán)碼具有優(yōu)良的代數(shù)結(jié)構(gòu)，使得可用簡單的反饋移位寄存器實(shí)現(xiàn)編碼和伴隨式計(jì)算，并可使用多種簡單而有效的譯碼方法；循環(huán)碼是研究最深入、理論最成熟、應(yīng)用最廣泛的一類線性分組碼。9.4.1循環(huán)碼的多項(xiàng)式描述2024/6/2316(2)循環(huán)碼的定義循環(huán)碼：如果(n,k)線性分組碼的任意碼矢C=(Cn－1,Cn－2,…,C0)

的i次循環(huán)移位，所得矢量C(i)=(Cn－1－i,Cn－2－i,…,C0,Cn－1,…,Cn－i)

仍是一個(gè)碼矢，則稱此線性碼為(n,k)循環(huán)碼。2024/6/2317(3)循環(huán)碼的多項(xiàng)式描述碼多項(xiàng)式：為了運(yùn)算的方便，將碼矢的各分量作為多項(xiàng)式的系數(shù)，把碼矢表示成多項(xiàng)式，稱為碼多項(xiàng)式。其一般表示式為C(x)=Cn－1xn－1+Cn－2xn－2+…+C0)碼多項(xiàng)式i次循環(huán)移位的表示方法記碼多項(xiàng)式C(x)的一次左移循環(huán)為C(1)(x)

，i次左移循環(huán)為C(i)(x)2024/6/2318碼多項(xiàng)式的模(xn+1)運(yùn)算0和1兩個(gè)元素模2運(yùn)算下構(gòu)成域。2024/6/2319碼矢C循環(huán)i次所得碼矢的碼多項(xiàng)式

C(x)乘以x，再除以(xn+1)，得2024/6/2320上式表明：碼矢循環(huán)一次的碼多項(xiàng)式C(1)(x)是原碼多項(xiàng)式C(x)乘以x除以(xn+1)的余式。寫作因此，

C(x)的i次循環(huán)移位C(i)(x)是C(x)乘以xi除以(xn+1)的余式，即結(jié)論：循環(huán)碼的碼矢的i次循環(huán)移位等效于將碼多項(xiàng)式乘xi后再模(xn+1)。2024/6/2321(4)舉例：(7,3)循環(huán)碼，可由任一個(gè)碼矢，比如(0011101)經(jīng)過循環(huán)移位，得到其它6個(gè)非0碼矢；也可由相應(yīng)的碼多項(xiàng)式(x4+x3+x2+1)，乘以xi(i=1,2,…,6)，再模(x7+1)運(yùn)算得到其它6個(gè)非0碼多項(xiàng)式。移位過程和相應(yīng)的多項(xiàng)式運(yùn)算如表9.4.1所示。2024/6/23222024/6/2323(1)循環(huán)碼的生成矩陣根據(jù)循環(huán)碼的循環(huán)特性，可由一個(gè)碼字的循環(huán)移位得到其它的非0碼字。在(n,k)循環(huán)碼的2k個(gè)碼字中，取前(k－1)位皆為0的碼字g(x)（其次數(shù)r=n－k），再經(jīng)(k－1)次循環(huán)移位，共得到k個(gè)碼字：g(x),xg(x),…,xk－1g(x)

9.4.2循環(huán)碼的生成多項(xiàng)式

這k個(gè)碼字顯然是相互獨(dú)立的，可作為碼生成矩陣的k行，于是得到循環(huán)碼的生成矩陣G(x)2024/6/2324(2)循環(huán)碼的生成多項(xiàng)式碼的生成矩陣一旦確定，碼就確定了；這就說明：(n,k)循環(huán)碼可由它的一個(gè)(n－k)次碼多項(xiàng)式g(x)來確定；所以說g(x)生成了(n,k)循環(huán)碼，因此稱g(x)為碼的生成多項(xiàng)式。2024/6/2325(3)

生成多項(xiàng)式和碼多項(xiàng)式的關(guān)系定理9.4.1：在(n,k)循環(huán)碼中，生成多項(xiàng)式g(x)是惟一的(n－k)次碼多項(xiàng)式，且次數(shù)是最低的。

[證明]：先證在(n,k)循環(huán)碼系統(tǒng)中存在(n－k)次碼多項(xiàng)式。因?yàn)樵?k個(gè)信息組中，有一個(gè)信息組為，它的對應(yīng)碼多項(xiàng)式的次數(shù)為n－1－(k－1)=n－k(n－k)次碼多項(xiàng)式是最低次碼多項(xiàng)式。若g(x)不是最低次碼多項(xiàng)式，那么設(shè)更低次的碼多項(xiàng)式為g’(x)，其次數(shù)為(n－k－1)。g’(x)的前面k位為0，即k個(gè)信息位全為0，而監(jiān)督位不為0，這對線性碼來說是不可能的，因此g(x)是最低次的碼多項(xiàng)式，即gn－k必為1。2024/6/2326g0=1，否則經(jīng)(n－1)次左移循環(huán)后將得到低于(n－k)

次的碼多項(xiàng)式。g(x)是惟一的(n－k)

次多項(xiàng)式。如果存在另一個(gè)(n－k)次碼多項(xiàng)式，設(shè)為g’’(x)，根據(jù)線性碼的封閉性，則g(x)+g’’(x)也必為一個(gè)碼多項(xiàng)式。由于g(x)和g’’(x)的次數(shù)相同，它們的和式的(n－k)

次項(xiàng)系數(shù)為0，那么g(x)+g’’(x)是一個(gè)次數(shù)低于(n－k)

次的碼多項(xiàng)式，前面已證明g(x)的次數(shù)是最低的，因此g’’(x)不能存在，所以g(x)是惟一的(n－k)

次碼多項(xiàng)式。2024/6/2327定理9.4.2：在(n,k)循環(huán)碼中，每個(gè)碼多項(xiàng)式C(x)都是g(x)的倍式；而每個(gè)為g(x)倍式且次數(shù)小于或等于(n－1)的多項(xiàng)式，必是一個(gè)碼多項(xiàng)式。

[證明]：設(shè)m=(mk－1,mk－2,…,m0)為任一信息組，G(x)為該(n,k)循環(huán)碼的生成矩陣，則相應(yīng)的碼多項(xiàng)式為2024/6/2328上式表明：循環(huán)碼的任一碼多項(xiàng)式為g(x)的倍式。顯然，凡是為

g(x)的倍式且次數(shù)小于或等于(n－1)的多項(xiàng)式，一定能分解成上式的形式，因而它就是信息多項(xiàng)式

m(x)=(mk－1xk－1+mk－21xk－2+…+m0)并由生成矩陣G(x)所生成的碼多項(xiàng)式。定理9.4.3(定理9.4.2的逆定理)：在一個(gè)(n,k)線性碼中，如果全部碼多項(xiàng)式都是最低次的(n－k)次碼多項(xiàng)式的倍式，則此線性碼為一個(gè)(n,k)循環(huán)碼。

注：一般說來，這種循環(huán)碼仍具有把(n,k)線性碼碼中任一非0碼矢循環(huán)移位必為一碼矢的循環(huán)特性，但從一個(gè)非0碼矢出發(fā)，進(jìn)行循環(huán)移位，就未必能得到碼的所有非0碼矢了。所以稱這種循環(huán)碼為推廣循環(huán)碼。2024/6/2329碼字循環(huán)關(guān)系圖單純循環(huán)碼的碼字循環(huán)圖：(7,3)循環(huán)碼2024/6/2330推廣循環(huán)碼的碼字循環(huán)圖：(6,3)循環(huán)碼2024/6/2331定理9.4.4：(n,k)循環(huán)碼的生成多項(xiàng)式g(x)是(xn+1)的因式，即xn+1=h(x)

g(x)。

[證明]：由于xkg(x)是n次多項(xiàng)式，可表示為xkg(x)=1

(xn+1)+g(k)(x)(9.4.1)

式中g(shù)(k)(x)是碼多項(xiàng)式