【正文】 種 (n,n1)碼為偶數(shù)監(jiān)督碼。 當(dāng)為奇數(shù)監(jiān)督時(shí)，它們之間的關(guān)系為： 1+2+3+…+c1+1=c0 (模 2) 編出的每一個(gè)碼字中 “ 1”的數(shù)目是奇數(shù)，稱(chēng)這種碼為奇數(shù)監(jiān)督碼。 奇數(shù)監(jiān)督碼或偶數(shù)監(jiān)督碼，還可統(tǒng)稱(chēng)為奇偶監(jiān)督碼 (或稱(chēng)奇偶校驗(yàn)碼 )。 奇偶監(jiān)督碼碼率 R=(n1)/n較高，且隨著 n的增加，越來(lái)越高。 最小距離 d0=2不變，因此僅能檢出 1位錯(cuò)碼，無(wú)糾錯(cuò)能力。 由于奇偶碼的碼率高，編譯碼電路簡(jiǎn)單，具有一定的抗干擾能力，所以曾得到廣泛的應(yīng)用。 不能檢測(cè)偶數(shù)個(gè)錯(cuò)誤。這是因?yàn)榕紨?shù)個(gè)錯(cuò)誤并不能改變碼組的奇偶性質(zhì)。 即使發(fā)現(xiàn) “ 1”或 ” 0”有奇數(shù)個(gè)錯(cuò)誤，也不能確定是 1個(gè)還是 3個(gè)或更多個(gè)奇數(shù)位錯(cuò)誤，因此不能糾正錯(cuò)誤。 在主要存在隨機(jī)錯(cuò)誤的信道中使用奇偶碼仍很有效。 2．定比碼 定比碼是使所編碼字中 “ 1”的數(shù)目保持一定，而在接收端檢查碼字中 “ 1”的數(shù)目是否為給定常數(shù)，借此來(lái)檢出錯(cuò)碼。定比碼在遠(yuǎn)動(dòng)系統(tǒng)中采用較多。 簡(jiǎn)單講，這種碼就是 “ 從 n中取 m” (mn)，這里 n為碼組長(zhǎng)度，m為每個(gè)許用碼組中 “ 1”的數(shù)目，例如 “ 從 5中取 3”的定比碼，就是以 5位二進(jìn)制數(shù)字組成一個(gè)碼組，這樣組成的碼組總共有25=32種。定比碼規(guī)定只有準(zhǔn)確的含有 3個(gè) “ 1”、 2個(gè) “ 0”的那些碼組為許用碼組 (故又稱(chēng) 3： 2碼 )，即為碼字，其他碼組一概為禁用碼組。 n中取 m碼，其許用碼組數(shù)可 由下式給出： !)!(!mmnnC mn ??定比碼比奇偶監(jiān)督更為嚴(yán)格。其原因是由于 “ 1“數(shù)目是一定的，所以服從數(shù)的奇偶性規(guī)律，包含有奇偶監(jiān)督。也就是說(shuō)，能發(fā)現(xiàn)所有的奇數(shù)個(gè)碼元的錯(cuò)誤。除去 “ 1”錯(cuò)成 “ 0”和 “ 0”錯(cuò)成“ 1”的成對(duì)性錯(cuò)誤外，即使出現(xiàn)二對(duì)以上的偶數(shù)個(gè)錯(cuò)誤，只要“ 1”的數(shù)目有了變化，就能發(fā)現(xiàn)錯(cuò)誤，故檢錯(cuò)能力很強(qiáng)。下表列出了 3： 2定比碼的許用碼組： 十進(jìn)制數(shù) 3： 2定比碼 十進(jìn)制數(shù) 3： 2定比碼 0 01101 5 00111 1 01011 6 10101 2 11001 7 11100 3 10110 8 01110 4 11010 9 10011 水平一致校驗(yàn)碼的如下表所示。把信息碼元以適當(dāng)?shù)拈L(zhǎng)度劃分為小組，各小組按行排列，對(duì)各行的信息元進(jìn)行奇偶校驗(yàn)，得到的校驗(yàn)元附在每行的后面。傳送時(shí)以列傳輸：首先傳輸?shù)谝涣校賯魉偷诙?，最后傳送校?yàn)元列。這種碼能發(fā)現(xiàn)長(zhǎng)度不大于列長(zhǎng)的突發(fā)錯(cuò)誤。 110111011011101…10101 小組 碼 字 信息元 校驗(yàn)元 1 11100 1 2 10111 0 3 01101 1 4 11011 0 5 10101 1 (方陣碼 ) 水平垂直一致校驗(yàn)碼又稱(chēng)方陣碼。它在水平一致校驗(yàn)的基礎(chǔ)上再對(duì)列 (垂直 )方向的碼元進(jìn)行一次奇偶校驗(yàn)。傳送時(shí)可以按列傳送也右按行傳送。這種碼能發(fā)現(xiàn)所有長(zhǎng)度不大于 n+1(n為列或行的碼元數(shù) )的突發(fā)錯(cuò)誤，以及其他不少錯(cuò)誤圖樣。 小組 碼 字 信息元 校驗(yàn)元 1 11101 1 2 10111 0 3 01101 1 4 11011 0 5 10101 1 校驗(yàn)元 01001 0 167。 46 線性分組碼 461 基本概念 在 (n,k)分組碼中，若每一個(gè)監(jiān)督元都是碼組中某些信息元按模2和而得到的，即監(jiān)督元是按線性關(guān)系相加而得到的，則稱(chēng)其為線性分組碼?；蛘哒f(shuō)，可用線性方程組表述規(guī)律性的分組碼稱(chēng)為線性分組碼。線性分組碼是一類(lèi)重要的糾錯(cuò)碼，應(yīng)用很廣泛。 現(xiàn)以 (7,4)分組碼為例來(lái)說(shuō)明線性分組碼的特點(diǎn)。設(shè)其碼字為C=[c6 c5 c4 c3 c2 c1 c0]，其中前 4位是信息元，后 3位是監(jiān)督元，可用下列線性方程組來(lái)描述該分組碼，產(chǎn)生監(jiān)督元： ??????????????346035614562cccccccccccc顯然，這 3個(gè)方程是線性無(wú)關(guān)的。經(jīng)計(jì)算可得 (7,4)碼的全部碼字。如下表，不難看出，它的最小碼距 d0=3，它能糾正一個(gè)錯(cuò)誤或檢測(cè)兩個(gè)錯(cuò)誤。 序號(hào) 碼字 序號(hào) 碼字 信息元 監(jiān)督元 信息元 監(jiān)督元 0 0000 000 8 1000 111 1 0001 011 9 1001 100 2 0010 101 10 1010 010 3 0011 110 11 1011 001 4 0100 110 12 1100 001 5 0101 101 13 1101 010 6 0110 011 14 1110 100 7 0111 000 15 1111 111 462 監(jiān)督矩陣 H和生成矩陣 G 上述 (7,4)碼的 3個(gè)監(jiān)督方程式可以改寫(xiě)為： 這組線性方程可用矩陣形式表示為： 并簡(jiǎn)記為： HCT=0T 或 CHT=0 其中， CT是 C的轉(zhuǎn)置， 0T是 0=[000]的轉(zhuǎn)置， HT是 H的轉(zhuǎn)置。 ???????????????????????????????????????????????010011010010101100010111012345601234560123456ccccccccccccccccccccc? ???????????????????????0001001101010101100101110123456Tccccccc H稱(chēng)為監(jiān)督矩陣，一旦 H給定，信息位和監(jiān)督位之間的關(guān)系也確定了。 H為 r n階矩陣， H矩陣每行之間是彼此線性無(wú)關(guān)的。 H矩陣可分成兩部分： 其中， P為 r k階矩陣， I為 r r階單位矩陣?？梢詫?xiě)成 H=[P Ir]形式的矩陣稱(chēng)為典型監(jiān)督矩陣。 ???????????100110101010110010111H? ?rIPH ????????????100110101010110010111 HCT=0T，說(shuō)明 H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來(lái)作為判斷接收碼字 C是否出錯(cuò)的依據(jù)。 若把監(jiān)督方程補(bǔ)充為下列方程： ????????????????????????34603561456233445566cccccccccccccccccccc可改寫(xiě)為矩陣形式 : 即 變換為 C=[c6 c5 c4 c3]G ??????????????????????????????????????????????????????????345601234561101101101111000010000100001ccccccccccc??????????????3456ccccGC TT其中 G稱(chēng)為生成矩陣，由 G和信息組就可以產(chǎn)生全部碼字。 G為 k n階矩陣，各行也是線性無(wú)關(guān)的。生成矩陣也可以分為兩部分，即： ?????????????1101000101010001100101110001G? ?QIGk??????????????1101000101010001100101110001其中 Q為 k r階矩陣， Ik為 k階單位陣，可以寫(xiě)成 G=[Ik Q]形式的矩陣稱(chēng)為典型生成矩陣。非典型形式的矩陣經(jīng)過(guò)運(yùn)算也可以化成典型形式的生成矩陣。 363 伴隨式 (校正子 )S 設(shè)了送碼組 C=[1 2 … c1 c0]，在傳輸過(guò)程中可能了生誤碼，接收碼組 R=[rn1 rn2 … r1 r0]，則收發(fā)碼組之差定義為錯(cuò)誤圖樣 E，也稱(chēng)為誤差矢量，即： E = RC TPQ ??????????????110101011111其中 E=[en1 en2 … e1 e0]，且 ei=0(當(dāng) ri=ci時(shí) )或 1 (當(dāng) ri≠ci時(shí) )。 也可以寫(xiě)成 R=C+E 令 S=RHT，稱(chēng)為伴隨式或校正子，則 S=RHT=(C+E)HT=EHT 由此可見(jiàn)，伴隨式 S與錯(cuò)誤圖樣 E之間有確定的線性變換關(guān)系。接收譯碼器的任務(wù)就是從伴隨式確定錯(cuò)誤圖樣，然后從接收到的碼字中減去錯(cuò)誤圖樣。 167。 47 循環(huán)碼 循環(huán)線性分組碼中的一個(gè)重要子類(lèi)。它有嚴(yán)格的代數(shù)結(jié)構(gòu)，用代數(shù)方法可以找出許多編碼效率高、檢、糾錯(cuò)能力強(qiáng)的循環(huán)碼來(lái)。由于循環(huán)碼的編碼和檢錯(cuò)方法簡(jiǎn)單，而且具有許多有效的糾錯(cuò)方法，所以得到了廣泛應(yīng)用。 循環(huán)碼可用多項(xiàng)式來(lái)分析，多項(xiàng)式系數(shù)是 “ 0”或 “ 1”.多項(xiàng)式的系數(shù)是按照冪次排列的一組有序數(shù)組，一個(gè)信息組（碼組）也是一組有序數(shù)組。所以碼組 C=(1 2 … c1 c0)不但可以用一個(gè)向量表示，而且還可以用一個(gè)多項(xiàng)式表示。用以表示碼組的多項(xiàng)式叫做碼多項(xiàng)式，記作 C(x)=1Xn1+ 2Xn2+ …+ c1X+ c0 兩個(gè)多項(xiàng)式的運(yùn)算是其對(duì)應(yīng)項(xiàng)系數(shù)的運(yùn)算，即分離系數(shù)法的運(yùn)算。要指出的是：系數(shù)的加法和乘法是模 2加和模 2乘。 一、循環(huán)碼的基本概念和特點(diǎn) (n,k)循環(huán)碼是線性分組碼，并且任一碼字的每次循環(huán)移位 (左移或右移 )得到的仍是一個(gè)碼字。 若 1 2 … c1 c0是一個(gè)循環(huán)碼字，則循環(huán)左移一位得 2， …， c1， c0， 1也是一個(gè)碼字，再移位仍是一個(gè)碼字。 一個(gè) (n,k)循環(huán)碼字循環(huán)移位一次，是原來(lái)碼多項(xiàng)式乘以 X。證明如下： 一個(gè)碼字可用碼多項(xiàng)式表示： C(x)=1Xn1+ 2Xn2+ …+ c1X+ c0 XC(x)=1Xn+ 2Xn1+ …+ c1X2+ c0X 上式左邊是碼多項(xiàng)式，右邊是循環(huán)碼字移位一次，兩者相等。 下面討論循環(huán)碼的生成多項(xiàng)式： (n,k)循環(huán)碼的生成多項(xiàng)式是碼字中 nk次的碼多項(xiàng)式，記作g(x)。 (n,k)循環(huán)碼共有 2k個(gè)碼字，從中取出一個(gè)前面 k1位都是 0的碼字，以 g(x)表示， g(x)的次數(shù)是 n1(k1)=nk。 首先 g(x)是一個(gè)碼字，根據(jù)循環(huán)碼的定義， xg(x), x2g(x), …, xk1g(x) 都是碼字。循環(huán)碼是線性碼，由線性碼的性質(zhì)得：這 k個(gè)碼字的線性組合也是一個(gè)碼字。記作： C(x)=(mk1Xk1+mk1Xk1+…+m1X+m0)g(x) 式中 mi(i=0,1,2,…,k1)為信息位，代表 “ 0”或 “ 1”。 在上式中取： M(x)=mk1Xk1+mk1Xk1+…+m1X+m0 M(x)是信息多項(xiàng)式，其信息位 mi為 “ 0”或 “ 1”，共有 k個(gè)信息位，所以 M(x)共有 2k種形式。可生成 2k個(gè)循環(huán)碼碼字。 顯然 g(x)是次數(shù)最低的碼多項(xiàng)式。因?yàn)槿?g(x)的次數(shù)為 nk1次，則能生成 2k+1個(gè)碼字，而 (n,k)碼只有 2k個(gè)碼字，所以是不可能的。 綜上可得： C(x)=M(x)g(x) 上式說(shuō)明：循環(huán)碼的碼字是待編信息多項(xiàng)式乘生成多項(xiàng)式而得，所有碼字都由 g(x)生成。 由上可知，是循環(huán)碼的 (nk)次碼序，所有循環(huán)碼字都由 g(x)生成。那么沒(méi)有碼字之前怎樣得到 g(x)呢？有下面定理： (n,k)循環(huán)碼的生成多項(xiàng)式 g(x)是 xn+1的因式。記作： xn+1=g(x) h(x) 生成多項(xiàng)式 g(x)寫(xiě)作： g(x) =Xnk+gnk1Xnk1+…+