第五章線性碼及其應(yīng)用線性碼具有便于運(yùn)算分析的疊加性質(zhì)，目前可供使用的絕大部分差錯(cuò)控制碼都屬于線性碼。第一節(jié)碼距和碼重定義1兩個(gè)碼字X=x1x2…xn,Y=y1y2…yn之間的漢明碼距定義為兩碼字的對(duì)應(yīng)碼元不相同的位數(shù)，用D(X,Y)表示，即∑D(X,Y)=i=1n(xi·yi+xi·yi)xi,yi分別表示非xi，非yi；“·”表示與，“+”表示或。例如：D(1101,0111)=2D(10101,11010)=4第五章線性碼及其應(yīng)用線性碼具有便于運(yùn)算分析的疊加性質(zhì)，1定義2碼字X=x1x2…xn的漢明重量是碼字中非零碼元的位數(shù)，用W(X)表示。例如：W(1001)=2,W(11010)=3由定義1和定義2知D(X,Y)=W(X-Y)定義3一組碼字C包括若干碼字C1,C2,…,Cn,所有這些碼字相互間碼距的最小的數(shù)值，稱為該碼組的最小碼距d(簡(jiǎn)稱碼距d)。d=minD(Ci,Cj)=minW(Ci-Cj)i,j∈1,2,…N,i≠j例如C=(0111100,1011011,1101001)d=3說明：為盡量避免碼字受到干擾而出錯(cuò)，總是希望碼字間有盡可能大的距離，最小碼距代表了一個(gè)碼組中最不利的情況。從安全出發(fā)，往往選用最小碼距來分析碼的檢錯(cuò)糾錯(cuò)能力。定義2碼字X=x1x2…xn的漢明重量是碼字中非零碼元2第二節(jié)檢錯(cuò)能力與糾錯(cuò)能力1、碼距為1時(shí)，能保證碼字的唯一性，但不能檢錯(cuò)和糾錯(cuò)。2、碼距為2時(shí)，能檢查出一位錯(cuò)誤，但無法糾錯(cuò)。3、碼距為3時(shí)，能檢查出一位或兩位錯(cuò)誤，并且還可糾正一位錯(cuò)誤。例：設(shè)碼長為3，取000、111作為碼字，其余為禁用碼字。如接收端收到001，它是禁用碼字，知道出錯(cuò)，由于001與000相差一個(gè)碼元，與111相差兩個(gè)碼元，根據(jù)最大似然譯碼原則將001譯為000。最大似然譯碼原則：當(dāng)Ci為若干個(gè)發(fā)送碼字中的一個(gè)，R為接收碼字，若條件概率P(R/Ci)為最大，則認(rèn)為碼字Ci就是發(fā)送碼字。第二節(jié)檢錯(cuò)能力與糾錯(cuò)能力1、碼距為1時(shí)，能保證碼字的唯3結(jié)論：（一）、要檢出碼字中任意e個(gè)碼元錯(cuò)誤，必須使最小碼距d滿足d≥e+1（二）、要糾正碼字中任意t個(gè)碼元錯(cuò)誤，必須使最小碼距d滿足d≥2t+1（三）、要糾正碼字中任意t個(gè)碼元錯(cuò)誤，并同時(shí)發(fā)現(xiàn)e個(gè)錯(cuò)誤（e≥t），則最小碼距d滿足d≥t+e+1當(dāng)碼距d=2t+1時(shí)，碼長為n的一個(gè)許用碼字中可糾正的錯(cuò)誤類型總數(shù)為：∑i=1tC(n,i)∴許用碼字?jǐn)?shù)Q≤∑i=0tC(n,i)2n結(jié)論：（一）、要檢出碼字中任意e個(gè)碼元錯(cuò)誤，必須使最小碼距d4第三節(jié)寄偶監(jiān)督碼寄偶監(jiān)督碼是最簡(jiǎn)單的一種檢錯(cuò)碼，是目前計(jì)算機(jī)系統(tǒng)用得最多的一種差錯(cuò)控制碼。寄偶監(jiān)督碼的編碼方式：是在n-1位信息元[Cn-1,Cn-2,…C1]后面附加1位監(jiān)督元C0，使得碼字中“1”的數(shù)目保持為奇數(shù)或偶數(shù)。奇數(shù)監(jiān)督，對(duì)應(yīng)的監(jiān)督方程為：Cn-1+Cn-2+……+C1+C0=1偶數(shù)監(jiān)督，對(duì)應(yīng)的監(jiān)督方程為：Cn-1+Cn-2+……+C1+C0=0P169表5-1列出了用七位ASCII碼表示的十個(gè)數(shù)字符號(hào)的寄偶校驗(yàn)位。第三節(jié)寄偶監(jiān)督碼寄偶監(jiān)督碼是最簡(jiǎn)單的一種檢錯(cuò)碼，是目前5判別方法：接收端收到編好的寄偶監(jiān)督碼后，用與發(fā)送端相同的規(guī)則檢查“1”的個(gè)數(shù)是否仍保持奇數(shù)或偶數(shù)，從而確定傳輸過程中是否有錯(cuò)誤。特點(diǎn)：能發(fā)現(xiàn)一位碼元或所有奇數(shù)位碼元出錯(cuò)的情況。但不能糾正任何錯(cuò)誤以及發(fā)現(xiàn)偶數(shù)位碼元錯(cuò)誤。簡(jiǎn)單寄偶碼的效率高：η=n-1n寄偶監(jiān)督碼的實(shí)現(xiàn)：1、硬件法：采用模二相加的異或電路。C1C2C3C4C5C6C7C0C0’判別方法：接收端收到編好的寄偶監(jiān)督碼后，用與發(fā)送端相同特點(diǎn)：62、軟件法（見P170圖5-6的流程圖）為了改進(jìn)差錯(cuò)控制性能，引入二維寄偶監(jiān)督碼（水平-垂直寄偶監(jiān)督碼、方陣碼、縱橫寄偶監(jiān)督碼）。就是在水平方向進(jìn)行寄偶監(jiān)督的同時(shí)，再按垂直方向進(jìn)行一次寄偶監(jiān)督。如P171圖5-7，圖5-8（二維水平-斜向寄偶監(jiān)督碼）。二維寄偶監(jiān)督碼特點(diǎn)：能檢出每一行或每一列的兩位或偶數(shù)位錯(cuò)誤。可以用水平、垂直兩個(gè)方向上的監(jiān)督碼元，來確定單個(gè)錯(cuò)誤碼元的位置，從而進(jìn)行糾正。但它無法檢出四個(gè)錯(cuò)誤碼元構(gòu)成矩形（或平行四邊形）四個(gè)頂點(diǎn)的錯(cuò)誤圖樣，也無法檢出雙向成偶的錯(cuò)誤圖樣。2、軟件法（見P170圖5-6的流程圖）為了改進(jìn)差錯(cuò)控制性能7第五節(jié)監(jiān)督矩陣與生成矩陣設(shè)有待編碼的消息序列為M=[m1m2…mk],對(duì)應(yīng)的信息元序列[X1X2…Xk]。為了進(jìn)行差錯(cuò)控制，我們按線性代數(shù)關(guān)系來添加監(jiān)督碼元序列[Xk+1Xk+2…Xn]，則稱此碼長n，信息元數(shù)k的碼字序列[X1X2…Xk|Xk+1Xk+2…Xn]為線性分組碼。記為(n,k)，如果其最小碼距為d，也可記為(n,k,d)或[n,k,d]。其中監(jiān)督元數(shù)r=n-k。用線性的監(jiān)督方程組來表示：a11X1+a12X2+……+a1kXk=Xk+1a21X1+a22X2+……+a2kXk=Xk+2……ar1X1+ar2X2+……+arkXk=Xn式中加號(hào)均表示模二加第五節(jié)監(jiān)督矩陣與生成矩陣設(shè)有待編碼的消息序列為M=[8或a11X1+a12X2+……+a1kXk+Xk+1+0+……+0=0a21X1+a22X2+……+a2kXk+0+Xk+2+……+0=0……ar1X1+ar2X2+……+arkXk+0+0……+Xn=0若用矩陣表示，則a11a12…a1k10…0a21a22…a2k01…0…ar1ar2…ark00…1…X1X2…XkXk+1…Xk=[0]簡(jiǎn)寫為HXT=0TH：監(jiān)督矩陣XT：行矩陣X=[X1X2…Xn]的轉(zhuǎn)置矩陣或a11X1+a12X2+……+a1kXk+Xk+1+0+…9例5-1一個(gè)(7,3)碼的信息元[X1X2X3]和監(jiān)督元[X4X5X6X7]間的監(jiān)督方程組為X1+X3+X4=0X1+X2+X3+X5=0X1+X2+X6=0X2+X3+X7=0求出對(duì)應(yīng)信息元的監(jiān)督元。解：列出各種信息元組合，依據(jù)監(jiān)督方程組求出對(duì)應(yīng)監(jiān)督元如下表所示。信息元監(jiān)督元編成碼字0000010100111001011101110000110101111010111000111001010000000000011101010011101110101001110101001111010011110100例5-1一個(gè)(7,3)碼的信息元[X1X2X3]和監(jiān)督元10還可以寫出監(jiān)督矩陣形式HX=011000111010011000100110001TX1X2X3X4X5X6X7=0000還可以寫出監(jiān)督矩陣形式HX=0111說明：1、編碼中，往往在多種可能的碼字排列中，選取少量的許用碼字。2、任意兩個(gè)碼字逐位模二加，可以得到另一個(gè)碼字。這種特性叫做封閉性。它是線性碼的重要特點(diǎn)。3、由封閉性知，兩個(gè)碼字的碼距，就是另一個(gè)碼字的碼重。所以，該組碼字的最小碼距就等于碼字中碼的最小重量。4、監(jiān)督矩陣H=[A|Ir]，A為rxk階矩陣，Ir為r階單位陣，r=n-k，H起監(jiān)督是否是碼字的作用。5、在線性碼組中，如果有一個(gè)碼重為W的碼字，則在H中必有與之相應(yīng)的W列相加等于0，固稱此W列線性相關(guān)。如果要求碼組的最小碼距為d,即要求碼字的最小碼重為d，則H中至少有d列相加之和為0，任意小于或等于d-1列線性無關(guān)。說明：1、編碼中，往往在多種可能的碼字排列中，選取少量2、任12例如：例題中0011101是碼字，碼重為4，它應(yīng)該滿足監(jiān)督方程組。即HXT=0110001110100110001001100010011101=1101+1000+0100+0001=0000例如：例題中0011101是碼字，碼重為4，它應(yīng)該滿足監(jiān)督方13下面討論一下監(jiān)督矩陣H與生成矩陣G的關(guān)系。HXT=[A|Ir]X1X2…XkXk+1Xk+2…Xn=0T或[A]X1X2…Xk+[Ir]Xk+1Xk+2…Xk=0T則Xk+1Xk+2…Xn=-[A]X1X2…Xk=-[A]…mkm1m2令X1X2…Xk=[Ik]…mkm1m2下面討論一下監(jiān)督矩陣H與生成矩陣G的關(guān)系。HXT=[A|Ir14X1X2…Xk=Ik-Am1m2…mk兩邊取轉(zhuǎn)置得X=MGX，M為行矩陣的形式；G=[Ik|-AT]稱為生成矩陣。利用G可由M直接生成碼X。以前面的例題為例，知道A，可求出[-A]T=11001111101[Ik]=00010001設(shè)有信息元組m1m2m3=101則由X=MG求出對(duì)應(yīng)碼字[1010011]G=100111001001110011101可以觀察G的三行分別是例5-1求出的第5，3，2個(gè)碼字X1…Xk=Ik-Am1…mk兩邊取轉(zhuǎn)置得X=MGX，M為行15這三個(gè)碼字組成的G，能使求出的碼字信息元在前，監(jiān)督元在后，即構(gòu)成的是系統(tǒng)碼。如選其他三個(gè)碼字組合成G，得出的碼字信息元與監(jiān)督元將是交錯(cuò)排列，即非系統(tǒng)碼。由H=[A|In-k],G=[Ik|-A]T則HG=[A|In-k][]=A-A=0TIk-A由這個(gè)等式可知G的每一行都是一個(gè)碼字。生成矩陣G和監(jiān)督矩陣H的關(guān)系：一個(gè)(n,k)碼字的監(jiān)督矩陣H，正好是另一個(gè)(n,n-k)=(n,r)碼字的生成矩陣G，反之亦然。我們稱(n,n-k)碼是(n,k)碼的對(duì)偶碼?？梢杂孟旅孢@個(gè)圖反映G和H的關(guān)系（注意理解）這三個(gè)碼字組成的G，能使求出的碼字信息元在前，監(jiān)督元由H=[161001110010011000111011011000111010011000100010001krkr此處有H(7,4)=G(7,3)或H(7,3)=G(7,4)如H(7,4)=G(7,3)=100111001001100011101可以通過矩陣變換將上面矩陣化為典型監(jiān)督矩陣形式10011117第六節(jié)伴隨式與標(biāo)準(zhǔn)陣列設(shè)發(fā)送的碼序列X=[X1X2…Xi…Xn]接收的碼序列Y=[Y1Y2…Yi…Yn]兩者的差別E=Y-X=[e1e2…ei…en]稱為差錯(cuò)序列或錯(cuò)誤圖樣用監(jiān)督矩陣來校驗(yàn)接收到的碼字時(shí)，有HY=H(X+E)=HX+HETTTT=HET(X是碼字，HX=0)T令S=HY=HETTT則S=EHTS稱為伴隨式，或校驗(yàn)子，用它來檢查接收碼字中的錯(cuò)誤。P182-184用例5-1的監(jiān)督矩陣為例討論了接收端可能遇到的幾種錯(cuò)誤情況，可以看出一種碼的檢錯(cuò)和糾錯(cuò)能力受碼距的限制，超過此限度就會(huì)檢不出錯(cuò)誤，或者造成誤判。注意S是一個(gè)r維的行矩陣第六節(jié)伴隨式與標(biāo)準(zhǔn)陣列設(shè)發(fā)送的碼序列X=[X1X2…18標(biāo)準(zhǔn)陣列問題：設(shè)有一個(gè)(n,k)線性碼，它共有2個(gè)碼字C0,C1,C2…,C-1。將它排列成下表所示形式。其中零碼矢C0放在第一列，它的下面放置各種錯(cuò)誤圖樣。當(dāng)監(jiān)督元有n-k個(gè)時(shí)，在C0下放有2-1個(gè)錯(cuò)誤圖樣。在C0以后各碼字C1,C2,…C2-1的同一列下，各放置一些元素，這些元素為該列碼字與相應(yīng)行的錯(cuò)誤圖樣模二相加而成。我們稱同一行的這些元素為陪集，C0下面那些錯(cuò)誤圖樣稱為陪集首。每一行對(duì)應(yīng)著唯一的一個(gè)伴隨式。如果將標(biāo)準(zhǔn)陣列預(yù)先存儲(chǔ)在接收端，則當(dāng)接收到某個(gè)錯(cuò)誤碼字序列時(shí)，可以按照相應(yīng)的陪集位于哪一列，而依據(jù)最大似然法則將其譯成該列之首的那個(gè)碼字。k2kn-kk注意理解下表中錯(cuò)誤圖樣與伴隨式的關(guān)系。標(biāo)準(zhǔn)陣列問題：設(shè)有一個(gè)(n,k)線性碼，它共有2個(gè)碼字C19C0C1C2…C2-1伴隨式SkE2E2+C1E2+C2…E2+C2-1kE3E3+C1E3+C2…E3+C2-1k…………E2E2+C1E2+C2…E2+C2-1n-kn-kn-kn-kk例5-2設(shè)碼字X=[X1X2X3X4X5]中X1，X2為監(jiān)督元，監(jiān)督矩陣為H=100010111列出標(biāo)準(zhǔn)陣列，判斷碼字10010是否是正確碼字，如果不是則它應(yīng)該譯為的正確碼字是多少。C0C1C220解：第一步根據(jù)H求出所有許用碼字C0,C1…C7。第二步確定錯(cuò)誤圖樣的個(gè)數(shù)及形式，以及伴隨式S的形式。第三步列出標(biāo)準(zhǔn)陣列表C0C1C2C3C4C5C6C7伴隨式0000000011001010011011001110101110011111S001000011100001000101110111110110001101101010000101101101011101000110010101001011110100001001110101101100100101010011000111111碼字10010顯然不是正確碼字，檢查它在陪集中位于C5這一列，因而按最大似然法則，將它改正錯(cuò)誤后譯為C5，即11010。解：第一步根據(jù)H求出所有許用碼字C0,C1…C7。第二步21說明：采用這種方法譯碼，需要存儲(chǔ)2個(gè)陪集元素(n為碼長）。如果利用陪集首所列的錯(cuò)誤圖樣和伴隨式一一對(duì)應(yīng)的關(guān)系列表則只需存2個(gè)陪集首，因而可以節(jié)省許多存儲(chǔ)量。nn-k例如：發(fā)送碼字為11010，接收端錯(cuò)誤地接收為11110，由公式S=HY=TT10001011111110=01查出陪集首為00100，固原發(fā)送碼字為11110+00100=11010但是當(dāng)(n,k)碼的碼長n較大時(shí)即使只存儲(chǔ)2個(gè)陪集首及伴隨式，譯碼器所需內(nèi)存仍然相當(dāng)大。因此尋求好的譯碼方法和簡(jiǎn)化譯碼設(shè)備是編碼理論和應(yīng)用中的重要課題。n-k說明：采用這種方法譯碼，需要存儲(chǔ)2個(gè)陪集元素(n為碼長）22第七節(jié)漢明碼漢明碼是一類能糾正一位錯(cuò)誤的線性碼，此類碼及其變型廣泛應(yīng)用于計(jì)算機(jī)存儲(chǔ)系統(tǒng)和數(shù)據(jù)通信中。對(duì)于任意正整數(shù)m≥3，存在具有下列參數(shù)的漢明碼：碼長：n=2-1m信息位數(shù)：k=2-m-1m監(jiān)督位數(shù)：r=n-k=m最小碼距：dmin=3（糾錯(cuò)位數(shù)tc=1）例5-3取m=3，則n=7,k=4，為(n,k)=(7,4)漢明碼。如監(jiān)督方程組為x2+x3+x4=x5x1+x3+x4=x6x1+x2+x4=x7第七節(jié)漢明碼漢明碼是一類能糾正一位錯(cuò)誤的線性碼，此類23則監(jiān)督矩陣為HX=T01111000110101101001x1x2x7…=[0]TG=000011010010100101100001111如果將監(jiān)督位設(shè)在x1,x2和x4，我們可以把題中給出的監(jiān)督方程組等價(jià)變換，得到下面方程組x5+x6+x7=x4x3+x6+x7=x2x3+x5+x7=x1H=000111101100111010101則監(jiān)督矩陣為HX=T011124則在輸出端求出譯碼用的伴隨式的碼元：S=HYs1=x4+x5+x6+x7s2=x2+x3+x6+x7s3=x1+x3+x5+x7根據(jù)公式S=HE得出(7,4)漢明碼的一種校驗(yàn)表。如下表示TTT錯(cuò)位指示伴隨式s1s2s3無錯(cuò)x1x2x3x4x5x6x7000001010011100101110111則在輸出端求出譯碼用的伴隨式的碼元：S=HYs1=x4+x525由上表可見，輸出檢錯(cuò)時(shí)很方便。因?yàn)橛砂殡S式的各碼元的值正好得出等于錯(cuò)誤位置的二進(jìn)制數(shù)。例如：當(dāng)信息元為x3x5x6x7=1100,可求出對(duì)應(yīng)的監(jiān)督元x1x2x4=011,最后的碼字x1x2x3x4x5x6x7=0111100假設(shè)傳輸過程中x7發(fā)生了錯(cuò)誤，則接收端接收到錯(cuò)誤碼字x1x2x3x4x5x6x7=0111101，求出伴隨式的碼元值s1s2s3=111,二進(jìn)制數(shù)為7，由上表可以判斷錯(cuò)誤的位置在第七位x7。通過將x7取反，進(jìn)行糾錯(cuò)得到正確碼字。注意：漢明碼是糾正一位錯(cuò)的完備碼，如果將漢明碼的參數(shù)tc=1,n=2-1,Q=2,且k=2-m-1代入前面講的求最大許用碼字?jǐn)?shù)的公式，可以發(fā)現(xiàn)等式兩邊正好相等。所以稱漢明碼為完備碼。它表明碼的m位監(jiān)督元的2種表達(dá)形式，正好全部用來指示碼長n=2-1位的每一位上的錯(cuò)誤，再加上完全無錯(cuò)的一種情況，因此監(jiān)督元的利用是最充分的。mkmmm由上表可見，輸出檢錯(cuò)時(shí)很方便。因?yàn)橛砂殡S式的各例如：當(dāng)信息元26第九節(jié)卷積碼的基本概念卷積碼是伊萊亞斯(Elias)1955年提出來的，它的特點(diǎn)是：每一段時(shí)間內(nèi)所編出的幾個(gè)碼元不但與此段時(shí)間內(nèi)進(jìn)入的K個(gè)信息元有關(guān)，而且也與前面幾段（如m段）時(shí)間內(nèi)的信息元有關(guān)。1、編碼電路下圖是一個(gè)卷積碼的編碼電路。DD輸入輸出12mjpj,1pj,2第九節(jié)卷積碼的基本概念卷積碼是伊萊亞斯(Elias)127D1、D2為移位寄存器。當(dāng)一個(gè)信息元m進(jìn)入編碼電路后，一面直接輸出送往信道，另一方面與前兩段時(shí)間中送入并移位存儲(chǔ)在D1和D2中的信息元m,m進(jìn)行模二相加，所生成的兩個(gè)監(jiān)督元jj-1j-2P=mmj,1jj-1P=mmj,2jj-2跟隨在信息元m后送入信道。j設(shè)剛開始工作時(shí)，D1、D2的狀態(tài)為0，輸入信息元m1=1,求出相應(yīng)的監(jiān)督元P1,1=1,P1,2=1，則送入信道的第一段碼字為111。再輸入信息元m2=0，求出相應(yīng)的監(jiān)督元P2,1=1,P2,2=0，第二段碼字為010。如果每一段時(shí)間內(nèi)送入k個(gè)信息元，編碼電路送出n個(gè)碼元，稱n個(gè)碼元的一段為子碼。當(dāng)輸入信息元為mj,mj+1,mj+2…時(shí)，送出的子碼序列為Cj,Cj+1,Cj+2=mj,Pj,1,Pj,2,mj+1,Pj+1,1,Pj+1,2,mj+2,Pj+2,1,Pj+2,2…。D1、D2為移位寄存器。當(dāng)一個(gè)信息元m進(jìn)入編碼電路后，28可見第j段時(shí)間內(nèi)所編成的子碼Cj不僅與本段中輸入的信息元mj有關(guān)，而且也與前面兩個(gè)子碼Cj-1,Cj-2有關(guān)，對(duì)后面的兩個(gè)子碼Cj+1,Cj+2也有影響。這種子碼之間具有一環(huán)與一環(huán)相連的特點(diǎn)。因而卷積碼稱為連環(huán)碼。前面講的每一個(gè)子碼的監(jiān)督元，是本段時(shí)間內(nèi)輸入的信息組與前面m=2個(gè)子碼的信息組的線性模二和，也就是與(m+1)k個(gè)信息元發(fā)生線性關(guān)系(此處k=1)，固卷積碼編出的也是線性碼。m稱為編碼存儲(chǔ)級(jí)數(shù)，N=(m+1)稱為編碼約束度。編碼約束長度定義為：N=(m+1)nA(n,k,m)卷積碼表示有k個(gè)輸入，n個(gè)輸出，存儲(chǔ)級(jí)數(shù)為m的線性碼。如果將移位寄存器和模二相加器間的關(guān)系以及信息元序列都用多項(xiàng)式形式來表示，則卷積編碼運(yùn)算可以化為多項(xiàng)式的代數(shù)運(yùn)算。例如書P198介紹了一個(gè)k=1,n=2的卷積碼編碼電路。可見第j段時(shí)間內(nèi)所編成的子碼Cj不僅與本段中輸入的信息元前面292監(jiān)督矩陣將前面的(3,1,2)卷積碼的兩個(gè)監(jiān)督方程改寫為矩陣形式。0*mj-2+0*Pj-2,1+0*Pj-2,2+1*mj-1+0*Pj-1,1+0*Pj-1,2+1*mj+1*Pj,1+0*Pj,2=01*mj-2+0*Pj-2,1+0*Pj-2,2+0*mj-1+0*Pj-1,1+0*Pj-1,2+1*mj+0*Pj,1+1*Pj,2=0用矩陣表示：000100110100000101mj-2Pj-2,1Pj-2,2mj-1Pj-1,1Pj-1,2mjPj,1Pj,2=02監(jiān)督矩陣將前面的(3,1,2)卷積碼的兩個(gè)監(jiān)督方程改寫30000100110100000101其中h=P2TP1TP0T00I2稱為基本監(jiān)督矩陣。P2T且=01P1T=10P0T=110=0000I2=0013第一截分組碼由前面的編碼電路可以看出，每一個(gè)信息元影響的子碼數(shù)目是有限的。因此在譯某個(gè)碼元時(shí)，只需要在一個(gè)約束長度內(nèi)來考慮。假設(shè)編碼約束度N=m+1=3,我們?cè)谌齻€(gè)子碼Cj(j=0,1,2)中來討論它的監(jiān)督關(guān)系。寫出如下三個(gè)監(jiān)督方程組。1*m0+1*P0,1+0*P0,2=01*m0+0*P0,1+1*P0,2=0000100110其中h=P2TP310*m0+0*P0,1+0*P0,2+1*m1+0*P1,1+0*P1,2+1*m2+1*P2,1+0*P2,2=01*m0+0*P0,1+0*P0,2+0*m1+0*P1,1+0*P1,2+1*m2+0*P2,1+1*P2,2=01*m0+0*P0,1+0*P0,2+1*m1+1*P1,1+0*P1,2=00*m0+0*P0,1+0*P0,2+1*m1+0*P1,1+1*P1,2=0由上面方程組可以得到根據(jù)三個(gè)信息組m0,m1,m2編出來的第一截分組碼的一致監(jiān)督矩陣H為H=110101100110000101000100110100000101=P2TP1TP1TP0TP0TP0TI2I2I20000*m0+0*P0,1+0*P0,2+1*m1+0*P1,132H的意義：它表達(dá)了第一截分組碼中的3個(gè)子碼內(nèi)，6個(gè)監(jiān)督元與3個(gè)信息元之間的約束關(guān)系。它也代表了以后無限長碼序列中各子碼的約束關(guān)系。例：對(duì)下圖示的n=2,k=1的卷積碼編碼電路，它的一致監(jiān)督方程為Pj=mj+mj-2，求基本監(jiān)督矩陣以及它的第一截分組碼的一致監(jiān)督矩陣。解：將監(jiān)督方程化為矩陣形式D1D2輸出mjPj輸入基本監(jiān)督矩陣h=[100011]H的意義：它表達(dá)了第一截分組碼中的3個(gè)子碼內(nèi)，6個(gè)監(jiān)督例：對(duì)33第一截分組碼的一致監(jiān)督矩陣H=100111000114生成矩陣設(shè)輸入的信息序列為m0m1m2m3…,則編碼電路編出的碼序列為m0P0,1P0,2m1P1,1P1,2m2P2,1P2,2…。按照監(jiān)督方程列出編碼序列中每一個(gè)碼元與輸入信息元之間的關(guān)系如下：m0P0,1=m0P0,2=m0m1P1,1=m0+m1P1,2=m1m2P2,1=m1+m2P2,2=m0+m2m3P3,1=m2+m3P3,2=m1+m3…….第一截分組碼的一致監(jiān)督矩陣H=14生成矩陣設(shè)輸入的信息序34將上述關(guān)系合并在一個(gè)矩陣表達(dá)式中，有[m0P0,1P0,2m1P1,1P1,2m2P2,1P2,2m3P3,1P3,2…]=[m0m1m2m3…]其中G=∞000111010001…000000111010…000000000111…111010001000………111010001000…000111010001…000000111010…000000000111………稱為生成矩陣將上述關(guān)系合并在一個(gè)矩陣表達(dá)式中，有[m0P0,1P0,2m35仿照H矩陣的簡(jiǎn)便寫法，將G寫成∞G=∞I1P00P10P2……I1P00P10P2…I1P00P1………式中I1是kxk=1x1階單位方陣，Pi(I=0,1,2)是kx(n-k)=1x2階矩陣，0為1x1階全0方陣。第一截分組碼生成矩陣為G=I1P00P10P2I1P00P1I1P0其中第一行g(shù)=[I1P00P10P2]稱為碼的基本生成矩陣。仿照H矩陣的簡(jiǎn)便寫法，將G寫成∞G=365譯碼方法卷積碼的譯碼通常有兩種方式：P2041、門限譯碼：工作原理類似于分組碼的譯碼電路。2、序列譯碼：概率譯碼的一種。5譯碼方法卷積碼的譯碼通常有兩種方式：P2041、門限37第五章線性碼及其應(yīng)用線性碼具有便于運(yùn)算分析的疊加性質(zhì)，目前可供使用的絕大部分差錯(cuò)控制碼都屬于線性碼。第一節(jié)碼距和碼重定義1兩個(gè)碼字X=x1x2…xn,Y=y1y2…yn之間的漢明碼距定義為兩碼字的對(duì)應(yīng)碼元不相同的位數(shù)，用D(X,Y)表示，即∑D(X,Y)=i=1n(xi·yi+xi·yi)xi,yi分別表示非xi，非yi；“·”表示與，“+”表示或。例如：D(1101,0111)=2D(10101,11010)=4第五章線性碼及其應(yīng)用線性碼具有便于運(yùn)算分析的疊加性質(zhì)，38定義2碼字X=x1x2…xn的漢明重量是碼字中非零碼元的位數(shù)，用W(X)表示。例如：W(1001)=2,W(11010)=3由定義1和定義2知D(X,Y)=W(X-Y)定義3一組碼字C包括若干碼字C1,C2,…,Cn,所有這些碼字相互間碼距的最小的數(shù)值，稱為該碼組的最小碼距d(簡(jiǎn)稱碼距d)。d=minD(Ci,Cj)=minW(Ci-Cj)i,j∈1,2,…N,i≠j例如C=(0111100,1011011,1101001)d=3說明：為盡量避免碼字受到干擾而出錯(cuò)，總是希望碼字間有盡可能大的距離，最小碼距代表了一個(gè)碼組中最不利的情況。從安全出發(fā)，往往選用最小碼距來分析碼的檢錯(cuò)糾錯(cuò)能力。定義2碼字X=x1x2…xn的漢明重量是碼字中非零碼元39第二節(jié)檢錯(cuò)能力與糾錯(cuò)能力1、碼距為1時(shí)，能保證碼字的唯一性，但不能檢錯(cuò)和糾錯(cuò)。2、碼距為2時(shí)，能檢查出一位錯(cuò)誤，但無法糾錯(cuò)。3、碼距為3時(shí)，能檢查出一位或兩位錯(cuò)誤，并且還可糾正一位錯(cuò)誤。例：設(shè)碼長為3，取000、111作為碼字，其余為禁用碼字。如接收端收到001，它是禁用碼字，知道出錯(cuò)，由于001與000相差一個(gè)碼元，與111相差兩個(gè)碼元，根據(jù)最大似然譯碼原則將001譯為000。最大似然譯碼原則：當(dāng)Ci為若干個(gè)發(fā)送碼字中的一個(gè)，R為接收碼字，若條件概率P(R/Ci)為最大，則認(rèn)為碼字Ci就是發(fā)送碼字。第二節(jié)檢錯(cuò)能力與糾錯(cuò)能力1、碼距為1時(shí)，能保證碼字的唯40結(jié)論：（一）、要檢出碼字中任意e個(gè)碼元錯(cuò)誤，必須使最小碼距d滿足d≥e+1（二）、要糾正碼字中任意t個(gè)碼元錯(cuò)誤，必須使最小碼距d滿足d≥2t+1（三）、要糾正碼字中任意t個(gè)碼元錯(cuò)誤，并同時(shí)發(fā)現(xiàn)e個(gè)錯(cuò)誤（e≥t），則最小碼距d滿足d≥t+e+1當(dāng)碼距d=2t+1時(shí)，碼長為n的一個(gè)許用碼字中可糾正的錯(cuò)誤類型總數(shù)為：∑i=1tC(n,i)∴許用碼字?jǐn)?shù)Q≤∑i=0tC(n,i)2n結(jié)論：（一）、要檢出碼字中任意e個(gè)碼元錯(cuò)誤，必須使最小碼距d41第三節(jié)寄偶監(jiān)督碼寄偶監(jiān)督碼是最簡(jiǎn)單的一種檢錯(cuò)碼，是目前計(jì)算機(jī)系統(tǒng)用得最多的一種差錯(cuò)控制碼。寄偶監(jiān)督碼的編碼方式：是在n-1位信息元[Cn-1,Cn-2,…C1]后面附加1位監(jiān)督元C0，使得碼字中“1”的數(shù)目保持為奇數(shù)或偶數(shù)。奇數(shù)監(jiān)督，對(duì)應(yīng)的監(jiān)督方程為：Cn-1+Cn-2+……+C1+C0=1偶數(shù)監(jiān)督，對(duì)應(yīng)的監(jiān)督方程為：Cn-1+Cn-2+……+C1+C0=0P169表5-1列出了用七位ASCII碼表示的十個(gè)數(shù)字符號(hào)的寄偶校驗(yàn)位。第三節(jié)寄偶監(jiān)督碼寄偶監(jiān)督碼是最簡(jiǎn)單的一種檢錯(cuò)碼，是目前42判別方法：接收端收到編好的寄偶監(jiān)督碼后，用與發(fā)送端相同的規(guī)則檢查“1”的個(gè)數(shù)是否仍保持奇數(shù)或偶數(shù)，從而確定傳輸過程中是否有錯(cuò)誤。特點(diǎn)：能發(fā)現(xiàn)一位碼元或所有奇數(shù)位碼元出錯(cuò)的情況。但不能糾正任何錯(cuò)誤以及發(fā)現(xiàn)偶數(shù)位碼元錯(cuò)誤。簡(jiǎn)單寄偶碼的效率高：η=n-1n寄偶監(jiān)督碼的實(shí)現(xiàn)：1、硬件法：采用模二相加的異或電路。C1C2C3C4C5C6C7C0C0’判別方法：接收端收到編好的寄偶監(jiān)督碼后，用與發(fā)送端相同特點(diǎn)：432、軟件法（見P170圖5-6的流程圖）為了改進(jìn)差錯(cuò)控制性能，引入二維寄偶監(jiān)督碼（水平-垂直寄偶監(jiān)督碼、方陣碼、縱橫寄偶監(jiān)督碼）。就是在水平方向進(jìn)行寄偶監(jiān)督的同時(shí)，再按垂直方向進(jìn)行一次寄偶監(jiān)督。如P171圖5-7，圖5-8（二維水平-斜向寄偶監(jiān)督碼）。二維寄偶監(jiān)督碼特點(diǎn)：能檢出每一行或每一列的兩位或偶數(shù)位錯(cuò)誤?？梢杂盟?、垂直兩個(gè)方向上的監(jiān)督碼元，來確定單個(gè)錯(cuò)誤碼元的位置，從而進(jìn)行糾正。但它無法檢出四個(gè)錯(cuò)誤碼元構(gòu)成矩形（或平行四邊形）四個(gè)頂點(diǎn)的錯(cuò)誤圖樣，也無法檢出雙向成偶的錯(cuò)誤圖樣。2、軟件法（見P170圖5-6的流程圖）為了改進(jìn)差錯(cuò)控制性能44第五節(jié)監(jiān)督矩陣與生成矩陣設(shè)有待編碼的消息序列為M=[m1m2…mk],對(duì)應(yīng)的信息元序列[X1X2…Xk]。為了進(jìn)行差錯(cuò)控制，我們按線性代數(shù)關(guān)系來添加監(jiān)督碼元序列[Xk+1Xk+2…Xn]，則稱此碼長n，信息元數(shù)k的碼字序列[X1X2…Xk|Xk+1Xk+2…Xn]為線性分組碼。記為(n,k)，如果其最小碼距為d，也可記為(n,k,d)或[n,k,d]。其中監(jiān)督元數(shù)r=n-k。用線性的監(jiān)督方程組來表示：a11X1+a12X2+……+a1kXk=Xk+1a21X1+a22X2+……+a2kXk=Xk+2……ar1X1+ar2X2+……+arkXk=Xn式中加號(hào)均表示模二加第五節(jié)監(jiān)督矩陣與生成矩陣設(shè)有待編碼的消息序列為M=[45或a11X1+a12X2+……+a1kXk+Xk+1+0+……+0=0a21X1+a22X2+……+a2kXk+0+Xk+2+……+0=0……ar1X1+ar2X2+……+arkXk+0+0……+Xn=0若用矩陣表示，則a11a12…a1k10…0a21a22…a2k01…0…ar1ar2…ark00…1…X1X2…XkXk+1…Xk=[0]簡(jiǎn)寫為HXT=0TH：監(jiān)督矩陣XT：行矩陣X=[X1X2…Xn]的轉(zhuǎn)置矩陣或a11X1+a12X2+……+a1kXk+Xk+1+0+…46例5-1一個(gè)(7,3)碼的信息元[X1X2X3]和監(jiān)督元[X4X5X6X7]間的監(jiān)督方程組為X1+X3+X4=0X1+X2+X3+X5=0X1+X2+X6=0X2+X3+X7=0求出對(duì)應(yīng)信息元的監(jiān)督元。解：列出各種信息元組合，依據(jù)監(jiān)督方程組求出對(duì)應(yīng)監(jiān)督元如下表所示。信息元監(jiān)督元編成碼字0000010100111001011101110000110101111010111000111001010000000000011101010011101110101001110101001111010011110100例5-1一個(gè)(7,3)碼的信息元[X1X2X3]和監(jiān)督元47還可以寫出監(jiān)督矩陣形式HX=011000111010011000100110001TX1X2X3X4X5X6X7=0000還可以寫出監(jiān)督矩陣形式HX=0148說明：1、編碼中，往往在多種可能的碼字排列中，選取少量的許用碼字。2、任意兩個(gè)碼字逐位模二加，可以得到另一個(gè)碼字。這種特性叫做封閉性。它是線性碼的重要特點(diǎn)。3、由封閉性知，兩個(gè)碼字的碼距，就是另一個(gè)碼字的碼重。所以，該組碼字的最小碼距就等于碼字中碼的最小重量。4、監(jiān)督矩陣H=[A|Ir]，A為rxk階矩陣，Ir為r階單位陣，r=n-k，H起監(jiān)督是否是碼字的作用。5、在線性碼組中，如果有一個(gè)碼重為W的碼字，則在H中必有與之相應(yīng)的W列相加等于0，固稱此W列線性相關(guān)。如果要求碼組的最小碼距為d,即要求碼字的最小碼重為d，則H中至少有d列相加之和為0，任意小于或等于d-1列線性無關(guān)。說明：1、編碼中，往往在多種可能的碼字排列中，選取少量2、任49例如：例題中0011101是碼字，碼重為4，它應(yīng)該滿足監(jiān)督方程組。即HXT=0110001110100110001001100010011101=1101+1000+0100+0001=0000例如：例題中0011101是碼字，碼重為4，它應(yīng)該滿足監(jiān)督方50下面討論一下監(jiān)督矩陣H與生成矩陣G的關(guān)系。HXT=[A|Ir]X1X2…XkXk+1Xk+2…Xn=0T或[A]X1X2…Xk+[Ir]Xk+1Xk+2…Xk=0T則Xk+1Xk+2…Xn=-[A]X1X2…Xk=-[A]…mkm1m2令X1X2…Xk=[Ik]…mkm1m2下面討論一下監(jiān)督矩陣H與生成矩陣G的關(guān)系。HXT=[A|Ir51X1X2…Xk=Ik-Am1m2…mk兩邊取轉(zhuǎn)置得X=MGX，M為行矩陣的形式；G=[Ik|-AT]稱為生成矩陣。利用G可由M直接生成碼X。以前面的例題為例，知道A，可求出[-A]T=11001111101[Ik]=00010001設(shè)有信息元組m1m2m3=101則由X=MG求出對(duì)應(yīng)碼字[1010011]G=100111001001110011101可以觀察G的三行分別是例5-1求出的第5，3，2個(gè)碼字X1…Xk=Ik-Am1…mk兩邊取轉(zhuǎn)置得X=MGX，M為行52這三個(gè)碼字組成的G，能使求出的碼字信息元在前，監(jiān)督元在后，即構(gòu)成的是系統(tǒng)碼。如選其他三個(gè)碼字組合成G，得出的碼字信息元與監(jiān)督元將是交錯(cuò)排列，即非系統(tǒng)碼。由H=[A|In-k],G=[Ik|-A]T則HG=[A|In-k][]=A-A=0TIk-A由這個(gè)等式可知G的每一行都是一個(gè)碼字。生成矩陣G和監(jiān)督矩陣H的關(guān)系：一個(gè)(n,k)碼字的監(jiān)督矩陣H，正好是另一個(gè)(n,n-k)=(n,r)碼字的生成矩陣G，反之亦然。我們稱(n,n-k)碼是(n,k)碼的對(duì)偶碼?？梢杂孟旅孢@個(gè)圖反映G和H的關(guān)系（注意理解）這三個(gè)碼字組成的G，能使求出的碼字信息元在前，監(jiān)督元由H=[531001110010011000111011011000111010011000100010001krkr此處有H(7,4)=G(7,3)或H(7,3)=G(7,4)如H(7,4)=G(7,3)=100111001001100011101可以通過矩陣變換將上面矩陣化為典型監(jiān)督矩陣形式10011154第六節(jié)伴隨式與標(biāo)準(zhǔn)陣列設(shè)發(fā)送的碼序列X=[X1X2…Xi…Xn]接收的碼序列Y=[Y1Y2…Yi…Yn]兩者的差別E=Y-X=[e1e2…ei…en]稱為差錯(cuò)序列或錯(cuò)誤圖樣用監(jiān)督矩陣來校驗(yàn)接收到的碼字時(shí)，有HY=H(X+E)=HX+HETTTT=HET(X是碼字，HX=0)T令S=HY=HETTT則S=EHTS稱為伴隨式，或校驗(yàn)子，用它來檢查接收碼字中的錯(cuò)誤。P182-184用例5-1的監(jiān)督矩陣為例討論了接收端可能遇到的幾種錯(cuò)誤情況，可以看出一種碼的檢錯(cuò)和糾錯(cuò)能力受碼距的限制，超過此限度就會(huì)檢不出錯(cuò)誤，或者造成誤判。注意S是一個(gè)r維的行矩陣第六節(jié)伴隨式與標(biāo)準(zhǔn)陣列設(shè)發(fā)送的碼序列X=[X1X2…55標(biāo)準(zhǔn)陣列問題：設(shè)有一個(gè)(n,k)線性碼，它共有2個(gè)碼字C0,C1,C2…,C-1。將它排列成下表所示形式。其中零碼矢C0放在第一列，它的下面放置各種錯(cuò)誤圖樣。當(dāng)監(jiān)督元有n-k個(gè)時(shí)，在C0下放有2-1個(gè)錯(cuò)誤圖樣。在C0以后各碼字C1,C2,…C2-1的同一列下，各放置一些元素，這些元素為該列碼字與相應(yīng)行的錯(cuò)誤圖樣模二相加而成。我們稱同一行的這些元素為陪集，C0下面那些錯(cuò)誤圖樣稱為陪集首。每一行對(duì)應(yīng)著唯一的一個(gè)伴隨式。如果將標(biāo)準(zhǔn)陣列預(yù)先存儲(chǔ)在接收端，則當(dāng)接收到某個(gè)錯(cuò)誤碼字序列時(shí)，可以按照相應(yīng)的陪集位于哪一列，而依據(jù)最大似然法則將其譯成該列之首的那個(gè)碼字。k2kn-kk注意理解下表中錯(cuò)誤圖樣與伴隨式的關(guān)系。標(biāo)準(zhǔn)陣列問題：設(shè)有一個(gè)(n,k)線性碼，它共有2個(gè)碼字C56C0C1C2…C2-1伴隨式SkE2E2+C1E2+C2…E2+C2-1kE3E3+C1E3+C2…E3+C2-1k…………E2E2+C1E2+C2…E2+C2-1n-kn-kn-kn-kk例5-2設(shè)碼字X=[X1X2X3X4X5]中X1，X2為監(jiān)督元，監(jiān)督矩陣為H=100010111列出標(biāo)準(zhǔn)陣列，判斷碼字10010是否是正確碼字，如果不是則它應(yīng)該譯為的正確碼字是多少。C0C1C257解：第一步根據(jù)H求出所有許用碼字C0,C1…C7。第二步確定錯(cuò)誤圖樣的個(gè)數(shù)及形式，以及伴隨式S的形式。第三步列出標(biāo)準(zhǔn)陣列表C0C1C2C3C4C5C6C7伴隨式0000000011001010011011001110101110011111S001000011100001000101110111110110001101101010000101101101011101000110010101001011110100001001110101101100100101010011000111111碼字10010顯然不是正確碼字，檢查它在陪集中位于C5這一列，因而按最大似然法則，將它改正錯(cuò)誤后譯為C5，即11010。解：第一步根據(jù)H求出所有許用碼字C0,C1…C7。第二步58說明：采用這種方法譯碼，需要存儲(chǔ)2個(gè)陪集元素(n為碼長）。如果利用陪集首所列的錯(cuò)誤圖樣和伴隨式一一對(duì)應(yīng)的關(guān)系列表則只需存2個(gè)陪集首，因而可以節(jié)省許多存儲(chǔ)量。nn-k例如：發(fā)送碼字為11010，接收端錯(cuò)誤地接收為11110，由公式S=HY=TT10001011111110=01查出陪集首為00100，固原發(fā)送碼字為11110+00100=11010但是當(dāng)(n,k)碼的碼長n較大時(shí)即使只存儲(chǔ)2個(gè)陪集首及伴隨式，譯碼器所需內(nèi)存仍然相當(dāng)大。因此尋求好的譯碼方法和簡(jiǎn)化譯碼設(shè)備是編碼理論和應(yīng)用中的重要課題。n-k說明：采用這種方法譯碼，需要存儲(chǔ)2個(gè)陪集元素(n為碼長）59第七節(jié)漢明碼漢明碼是一類能糾正一位錯(cuò)誤的線性碼，此類碼及其變型廣泛應(yīng)用于計(jì)算機(jī)存儲(chǔ)系統(tǒng)和數(shù)據(jù)通信中。對(duì)于任意正整數(shù)m≥3，存在具有下列參數(shù)的漢明碼：碼長：n=2-1m信息位數(shù)：k=2-m-1m監(jiān)督位數(shù)：r=n-k=m最小碼距：dmin=3（糾錯(cuò)位數(shù)tc=1）例5-3取m=3，則n=7,k=4，為(n,k)=(7,4)漢明碼。如監(jiān)督方程組為x2+x3+x4=x5x1+x3+x4=x6x1+x2+x4=x7第七節(jié)漢明碼漢明碼是一類能糾正一位錯(cuò)誤的線性碼，此類60則監(jiān)督矩陣為HX=T01111000110101101001x1x2x7…=[0]TG=000011010010100101100001111如果將監(jiān)督位設(shè)在x1,x2和x4，我們可以把題中給出的監(jiān)督方程組等價(jià)變換，得到下面方程組x5+x6+x7=x4x3+x6+x7=x2x3+x5+x7=x1H=000111101100111010101則監(jiān)督矩陣為HX=T011161則在輸出端求出譯碼用的伴隨式的碼元：S=HYs1=x4+x5+x6+x7s2=x2+x3+x6+x7s3=x1+x3+x5+x7根據(jù)公式S=HE得出(7,4)漢明碼的一種校驗(yàn)表。如下表示TTT錯(cuò)位指示伴隨式s1s2s3無錯(cuò)x1x2x3x4x5x6x7000001010011100101110111則在輸出端求出譯碼用的伴隨式的碼元：S=HYs1=x4+x562由上表可見，輸出檢錯(cuò)時(shí)很方便。因?yàn)橛砂殡S式的各碼元的值正好得出等于錯(cuò)誤位置的二進(jìn)制數(shù)。例如：當(dāng)信息元為x3x5x6x7=1100,可求出對(duì)應(yīng)的監(jiān)督元x1x2x4=011,最后的碼字x1x2x3x4x5x6x7=0111100假設(shè)傳輸過程中x7發(fā)生了錯(cuò)誤，則接收端接收到錯(cuò)誤碼字x1x2x3x4x5x6x7=0111101，求出伴隨式的碼元值s1s2s3=111,二進(jìn)制數(shù)為7，由上表可以判斷錯(cuò)誤的位置在第七位x7。通過將x7取反，進(jìn)行糾錯(cuò)得到正確碼字。注意：漢明碼是糾正一位錯(cuò)的完備碼，如果將漢明碼的參數(shù)tc=1,n=2-1,Q=2,且k=2-m-1代入前面講的求最大許用碼字?jǐn)?shù)的公式，可以發(fā)現(xiàn)等式兩邊正好相等。所以稱漢明碼為完備碼。它表明碼的m位監(jiān)督元的2種表達(dá)形式，正好全部用來指示碼長n=2-1位的每一位上的錯(cuò)誤，再加上完全無錯(cuò)的一種情況，因此監(jiān)督元的利用是最充分的。mkmmm由上表可見，輸出檢錯(cuò)時(shí)很方便。因?yàn)橛砂殡S式的各例如：當(dāng)信息元63第九節(jié)卷積碼的基本概念卷積碼是伊萊亞斯(Elias)1955年提出來的，它的特點(diǎn)是：每一段時(shí)間內(nèi)所編出的幾個(gè)碼元不但與此段時(shí)間內(nèi)進(jìn)入的K個(gè)信息元有關(guān)，而且也與前面幾段（如m段）時(shí)間內(nèi)的信息元有關(guān)。1、編碼電路下圖是一個(gè)卷積碼的編碼電路。DD輸入輸出12mjpj,1pj,2第九節(jié)卷積碼的基本概念卷積碼是伊萊亞斯(Elias)164D1、D2為移位寄存器。當(dāng)一個(gè)信息元m進(jìn)入編碼電路后，一面直接輸出送往信道，另一方面與前兩段時(shí)間中送入并移位存儲(chǔ)在D1和D2中的信息元m,m進(jìn)行模二相加，所生成的兩個(gè)監(jiān)督元jj-1j-2P=mmj,1jj-1P=mmj,2jj-2跟隨在信息元m后送入信道。j設(shè)剛開始工作時(shí)，D1、D2的狀態(tài)為0，輸入信息元m1=1,求出相應(yīng)的監(jiān)督元P1,1=1,P1,2=1，則送入信道的第一段碼字為111。再輸入信息元m2=0，求出相應(yīng)的監(jiān)督元P2,1=1,P2,2=0，第二段碼字為010。如果每一段時(shí)間內(nèi)送入k個(gè)信息元，編碼電路送出n個(gè)碼元，稱n個(gè)碼元的一段為子碼。當(dāng)輸入信息元為mj,mj+1,mj+2…時(shí)，送出的子碼序列為Cj,Cj+1,Cj+2=mj,Pj,1,Pj,2,mj+1,Pj+1,1,Pj+1,2,mj+2,Pj+2,1,Pj+2,2…。D1、D2為移位寄存器。當(dāng)一個(gè)信息元m進(jìn)入編碼電路后，65可見第j段時(shí)間內(nèi)所編成的子碼Cj不僅與本段中輸入的信息元mj有關(guān)，而且也與前面兩個(gè)子碼Cj-1,Cj-2有關(guān)，對(duì)后面的兩個(gè)子碼Cj+1,Cj+2也有影響。這種子碼之間具有一環(huán)與一環(huán)相連的特點(diǎn)。因而卷積碼稱為連環(huán)碼。前面講的每一個(gè)子碼的監(jiān)督元，是本段時(shí)間內(nèi)輸入的信息組與前面m=2個(gè)子碼的信息組的線性模二和，也就是與(m+1)k個(gè)信息元發(fā)生線性關(guān)系(此處k=1)，固卷積碼編出的也是線性碼。m稱為編碼存儲(chǔ)級(jí)數(shù)，N=(m+1)稱為編碼約束度。編碼約束長度定義為：N=(m+1)nA(n,k,m)卷積碼表示有k個(gè)輸入，n個(gè)輸出，存儲(chǔ)級(jí)數(shù)為m的線性碼。如果將移位寄存器和模二相加器間的關(guān)系以及信息元序列都用多項(xiàng)式形式來表示，則卷積編碼運(yùn)算可以化為多項(xiàng)式的代數(shù)運(yùn)算。例如書P198介紹了一個(gè)k=1,n=2的卷積碼編碼電路。