信息論與編碼理論基礎(chǔ)(第六章)

2023/2/51第六章：線性分組碼§6.1分組碼的概念(與主教材標(biāo)題不同)§6.2線性分組碼§6.3線性分組碼的校驗(yàn)矩陣(與主教材標(biāo)題不同)§6.5譯碼方法和糾錯(cuò)能力(與主教材標(biāo)題不同)§6.4、§6.6、§6.7、§6.8一些特殊的線性分組碼2023/2/52§6.1分組碼的概念設(shè)信道是一個(gè)D元字母輸入/D元字母輸出的DMC信道，字母表為{0,1,…,D-1}。其信道轉(zhuǎn)移概率矩陣為D×D矩陣傳輸錯(cuò)誤的概率為

p。信道容量為C=logD-H(p)-plog(D-1)。2023/2/53§6.1分組碼的概念對(duì)隨機(jī)變量序列X1X2…進(jìn)行的信道編碼為(N,L)碼：(X1X2…XL)→(U1U2…UN)=C(X1X2…XL)。這個(gè)(N,L)碼又稱為(N,L)分組碼。已經(jīng)有結(jié)論：當(dāng)設(shè)備所確定的編碼速率R<C/H(X)時(shí)，存在(N,L)分組碼，使得實(shí)際編碼速率(信息率L/N)任意接近R，譯碼錯(cuò)誤的概率任意接近0。問(wèn)題是：怎樣構(gòu)造這樣的分組碼？這樣的分組碼的編碼、譯碼計(jì)算量會(huì)不會(huì)太大？（這才是研究分組碼的含義）

2023/2/54§6.1分組碼的概念預(yù)備知識(shí)1：有限域設(shè)D是一個(gè)素?cái)?shù)。于是字母表{0,1,…,D-1}中的所有字母關(guān)于(modD)加法、(modD)乘法構(gòu)成了一個(gè)封閉的代數(shù)結(jié)構(gòu)，稱作有限域，又稱作Galois域，記作GF(D)：GF(D)=({0,1,…,D-1},(modD)加法,(modD)乘法)。即（1）({0,1,…,D-1},(modD)加法)構(gòu)成交換群（Abel群）。（2）({1,…,D-1},(modD)乘法)構(gòu)成交換群（Abel群）。（3）分配律成立：a(b+c)(modD)=ab+ac(modD)。2023/2/55§6.1分組碼的概念注1：如果D不是素?cái)?shù)，({0,1,…,D-1},(modD)加法,(modD)乘法)不是有限域，只是有限環(huán)。注2：有限域GF(D)上的線性代數(shù)完全類似于實(shí)數(shù)域上的線性代數(shù)，線性代數(shù)的所有內(nèi)容都在“加法”和“乘法”基礎(chǔ)上得到。元素的“加法”負(fù)元；非0元的“乘法”逆元；一組向量是否“線性無(wú)關(guān)”的概念以及所有等價(jià)的判別方法；矩陣的“秩”的概念以及所有計(jì)算方法；方陣是否“可逆”的所有判別方法；求方陣的“逆陣”的所有算法；關(guān)于對(duì)稱矩陣的所有結(jié)論；等等。注3：有限域GF(D)與實(shí)數(shù)域的區(qū)別是：傳統(tǒng)的“逼近”、“極限”的概念消失了。2023/2/56例：取D=2，則GF(2)=({0,1},(mod2)加法,(mod2)乘法)。運(yùn)算規(guī)則為：

0+0=1+1=0，0+1=1，0×0=0×1=0，1×1=1。方陣是否可逆？回答是肯定的。兩種不同的判別方法都能夠證明它是可逆的：（1）它經(jīng)過(guò)可逆行變換能夠變成單位陣；（2）它的行列式不等于0。（等于1！）2023/2/57§6.1分組碼的概念該方陣的逆矩陣是什么？怎樣計(jì)算？做聯(lián)合可逆行變換：2023/2/58§6.1分組碼的概念例：取D=3，則GF(3)=({0,1,2},(mod3)加法,(mod3)乘法))。運(yùn)算規(guī)則為：0+0=1+2=0，0+1=2+2=1，0+2=1+1=2，0×0=0×1==0×2=0，1×1=2×2=1，1×2=2。矩陣是不是滿行秩的？換句話說(shuō)，此矩陣的三個(gè)行向量是不是在域GF(3)上線性無(wú)關(guān)的？再換句話說(shuō)，能否保證此矩陣的各行的任何非0線性組合都不是全0的4維向量？再換句話說(shuō)，此矩陣能否通過(guò)一些可逆行變換變成一個(gè)“階梯陣”？2023/2/59§6.1分組碼的概念可逆行變換2023/2/510§6.1分組碼的概念例：域GF(D)上的一個(gè)L行N列的矩陣（L×N階的矩陣）G，設(shè)它是滿行秩的（當(dāng)然此時(shí)有L≤N）。則變換(u1,u2,…,uN)=(x1,x2,…,xL)G一定是單射(即(x1,x2,…,xL)的不同值一定變換為(u1,u2,…,uN)的不同值)。證明設(shè)u(1)=x(1)G，u(2)=x(2)G，且x(1)≠x(2)。要證明u(1)≠u(mài)(2)。根據(jù)線性性質(zhì)，u(1)-u(2)=(x(1)-x(2))G，因?yàn)?x(1)-x(2))≠全0的L維向量，所以(x(1)-x(2))G是G的各行的非0線性組合。G滿行秩，所以(x(1)-x(2))G≠全0的N維向量。所以u(píng)(1)≠u(mài)(2)。2023/2/511§6.1分組碼的概念預(yù)備知識(shí)2：有限域上的分組碼當(dāng)D是素?cái)?shù)時(shí)，分組碼可以充分利用有限域GF(D)的代數(shù)運(yùn)算，使得編碼和譯碼更加簡(jiǎn)便。2023/2/512§6.2線性分組碼定義取GF(D)上的一個(gè)L行N列的矩陣G，它是滿行秩的。(N,L)分組碼定義為(u1,u2,…,uN)=(x1,x2,…,xL)G其中(x1,x2,…,xL)是信息向量，(u1,u2,…,uN)是對(duì)應(yīng)的碼字。（1）稱此碼為D元(N,L)線性分組碼。（2）稱矩陣G為此碼的生成矩陣。2023/2/513§6.2線性分組碼線性分組碼的代數(shù)結(jié)構(gòu)命題1不同的信息向量對(duì)應(yīng)不同的碼字。（因?yàn)榫仃嘒是滿行秩的，所以變換u=xG是單射）命題2生成矩陣G的第1行是信息向量(1,0,0,…,0)的碼字；生成矩陣G的第2行是信息向量(0,1,0,…,0)的碼字；…生成矩陣G的第L行是信息向量(0,…,0,0,1)的碼字。2023/2/514§6.2線性分組碼命題3信息向量(x1,x2,…,xL)的碼字是：x1數(shù)乘G的第1行，加x2數(shù)乘G的第2行，加…，加xL數(shù)乘G的第L行。換句話說(shuō)，任何一個(gè)碼字都是生成矩陣G的線性組合。命題4當(dāng)u(1)和u(2)都是碼字，u(1)+u(2)也是碼字。（線性分組碼的碼字關(guān)于線性運(yùn)算封閉）證明設(shè)u(1)是信息向量x(1)的碼字：u(1)=x(1)G；u(2)是信息向量x(2)的碼字：u(2)=x(2)G。則u(1)+u(2)=x(1)G+x(2)G=(x(1)+x(2))G，即u(1)+u(2)是信息向量(x(1)+x(2))的碼字。證完。2023/2/515§6.2線性分組碼（命題3和命題4告訴我們，一個(gè)N維向量是一個(gè)碼字，當(dāng)且僅當(dāng)它是生成矩陣G的第1行~第L行的線性組合。還告訴我們，線性分組碼的碼字集合構(gòu)成一個(gè)線性空間。這個(gè)線性空間是幾維的？L維的，因?yàn)樯删仃嘒的第1行~第L行恰好是該線性空間的一組基）命題5設(shè)一個(gè)D元(N,L)線性分組碼的生成矩陣為G。設(shè)另一個(gè)D元(N,L)線性分組碼的生成矩陣為G'=MG，其中M是L階可逆方陣。則兩個(gè)碼的碼字集合完全重合，只是信息向量與碼字的對(duì)應(yīng)關(guān)系不同。換句話說(shuō)，如果把線性分組碼的生成矩陣G做可逆行變換變成另一個(gè)生成矩陣，則不改變碼字集合，只改變信息向量與碼字的對(duì)應(yīng)關(guān)系。2023/2/516§6.2線性分組碼證明（要證明，第一個(gè)碼中任一個(gè)碼字也是第二個(gè)碼中的碼字；第二個(gè)碼中任一個(gè)碼字也是第一個(gè)碼中的碼字）設(shè)在第一個(gè)碼中，u是信息向量x的碼字：u=xG；則在第二個(gè)碼中，u是信息向量xM-1的碼字：u=xM-1MG=xM-1G'。設(shè)在第二個(gè)碼中，u是信息向量x的碼字：u=xG'；則在第一個(gè)碼中，u是信息向量xM的碼字：u=xMM-1G'=xMG。證完。

2023/2/517§6.2線性分組碼線性分組碼的特例：系統(tǒng)碼定義(p178)

D元(N,L)線性分組碼的生成矩陣為G=[PL×(N-L),IL]，其中IL是L階單位陣，PL×(N-L)是L×(N-L)階矩陣。則稱此碼為系統(tǒng)碼。此時(shí)信息向量(x1,x2,…,xL)的碼字是(u1,u2,…,uN)=(x1,x2,…,xL)G=((x1,x2,…,xL)PL×(N-L),x1,x2,…,xL)。碼字的后L位恰好是信息向量(x1,x2,…,xL)，稱為碼字的信息位。稱碼字的前N-L位為碼字的一致校驗(yàn)位。2023/2/518§6.2線性分組碼例

此二元(7,4)碼是線性分組碼，生成矩陣G是由信息向量(1000)、(0100)、(0010)、(0001)的碼字組成的4行2023/2/519§6.2線性分組碼例此二元(5,3)線性分組碼的生成矩陣是2023/2/520§6.3線性分組碼的校驗(yàn)矩陣線性分組碼的校驗(yàn)矩陣定理(p179)

對(duì)于D元(N,L)線性分組碼的生成矩陣G（G是L×N階矩陣），必存在一個(gè)(N-L)×N階矩陣H，（1）H是滿行秩的；（2）GHT=OL×(N-L)。（HT是H的轉(zhuǎn)置矩陣，OL×(N-L)是全0的L×(N-L)階矩陣。不證明。這方面的知識(shí)屬于有限域上的線性代數(shù)）定義(p179)

由上述定理所描述的矩陣H稱為D元(N,L)線性分組碼的校驗(yàn)矩陣。2023/2/521§6.3線性分組碼的校驗(yàn)矩陣有以下的結(jié)論。（1）一個(gè)線性分組碼有很多校驗(yàn)矩陣。一個(gè)校驗(yàn)矩陣H經(jīng)過(guò)可逆行變換變?yōu)镠

'，

H

'是同一個(gè)線性分組碼的另一個(gè)校驗(yàn)矩陣。（2）固定一個(gè)校驗(yàn)矩陣H。則一個(gè)N維向量u是一個(gè)碼字，當(dāng)且僅當(dāng)：uHT=全0的N-L維行向量。（3）設(shè)一個(gè)D元(N,L)線性分組碼的生成矩陣G，校驗(yàn)矩陣H。則H是一個(gè)D元(N,N-L)線性分組碼的生成矩陣，G是此碼的一個(gè)校驗(yàn)矩陣。稱這兩個(gè)碼互為對(duì)偶碼。D元(N,L)線性分組碼D元(N,N-L)線性分組碼生成矩陣G校驗(yàn)矩陣H生成矩陣H校驗(yàn)矩陣G2023/2/522§6.3線性分組碼的校驗(yàn)矩陣（怎樣由生成矩陣G計(jì)算出校驗(yàn)矩陣H？）（4）設(shè)D元(N,L)線性分組碼是系統(tǒng)碼，生成矩陣為G=[P,IL]，其中IL是L階單位陣，P是L×(N-L)階矩陣。則校驗(yàn)矩陣可以取為H=[IN-L,-PT]，其中IN-L是N-L階單位陣，PT是P

的轉(zhuǎn)置矩陣。證明GHT=[P,IL][IN-L,-PT]T=P-P=OL×(N-L)。證完。（5）設(shè)D元(N,L)線性分組碼的生成矩陣經(jīng)過(guò)可逆行變換后變?yōu)閇P,IL]，則校驗(yàn)矩陣也可以取為H=[IN-L,-PT]。2023/2/523§6.3線性分組碼的校驗(yàn)矩陣2023/2/524§6.5譯碼方法和糾錯(cuò)能力線性分組碼的糾錯(cuò)譯碼準(zhǔn)則定義

(已知)一個(gè)N維向量u的Hamming重量定義為它的對(duì)應(yīng)位置值不等于0的位數(shù)。記為w(u)。兩個(gè)N維向量u(1)和u(2)的Hamming距離定義為它們的對(duì)應(yīng)位置值不相同的位數(shù)。記為d(u(1),u(2))。顯然有以下的結(jié)論d(u(1),u(2))=w(u(1)-u(2))。三角不等式：d(u(1),u(3))≤d(u(1),u(2))+d(u(2),u(3))?；騱(u(1)-u(3))≤w(u(1)-u(2))+w(u(2)-u(3))。2023/2/525§6.5譯碼方法和糾錯(cuò)能力設(shè)GF(D)上的D元(N,L)線性分組碼，生成矩陣為G。將信息向量x編碼，得到碼字u=xG。將碼字u輸入信道。信道的輸出值為y。使用最小距離準(zhǔn)則：給定輸出值y，尋找碼字c使d(y,c)最小。將輸出值y譯為碼字c。當(dāng)c=u時(shí)，就實(shí)現(xiàn)了正確譯碼。直接使用最小距離準(zhǔn)則的困難：需要將DL個(gè)碼字與輸出值y的Hamming距離進(jìn)行對(duì)比，才能找到碼字c使d(y,c)最小。計(jì)算量大。(窮舉搜索)2023/2/526編碼-譯碼過(guò)程圖示。其中

x(1)、x(2)、x(3)、x(4)是各個(gè)信息向量；

c(1)、c(2)、c(3)、c(4)是各個(gè)對(duì)應(yīng)碼字。2023/2/527§6.5譯碼方法和糾錯(cuò)能力實(shí)用糾錯(cuò)譯碼算法的預(yù)備知識(shí)：差錯(cuò)向量和伴隨式定義6.1.8

設(shè)信道的輸入為碼字u；信道的輸出值為向量y。稱向量e=y-u為差錯(cuò)向量，或差錯(cuò)圖樣。（請(qǐng)注意：①此時(shí)y=u+e；u=y-e；向量的加減法是對(duì)應(yīng)分量的(modD)加減法。②在信道的輸出端，只能得到輸出向量y，并不能得到差錯(cuò)向量e，因此不能得到輸入碼字u。）定義6.1.9(p195)設(shè)H是校驗(yàn)矩陣。對(duì)于N維行向量t，記s=tHT并稱N-L維行向量s為N維行向量t的伴隨式。2023/2/528§6.5譯碼方法和糾錯(cuò)能力有以下的結(jié)論。（1）N維行向量t是一個(gè)碼字，當(dāng)且僅當(dāng)t的伴隨式是一個(gè)全0的N-L維行向量。（這是已知的結(jié)論）（2）設(shè)信道的輸入碼字u，輸出向量y，差錯(cuò)向量e=y-u，則e的伴隨式等于y的伴隨式。證明eHT=(y-u)HT=yHT-uHT=yHT。證完。結(jié)論（2）的注解：在信道的輸出端，雖然不能得到差錯(cuò)向量，卻能計(jì)算出差錯(cuò)向量的伴隨式：它恰好等于輸出向量的伴隨式。換句話說(shuō)，設(shè)輸出向量為y，并計(jì)算出y的伴隨式s=yHT。則此時(shí)雖然不能確切地得到差錯(cuò)向量，但任何一個(gè)“可能的差錯(cuò)向量”e都滿足方程eHT=s2023/2/529§6.5譯碼方法和糾錯(cuò)能力（3）設(shè)輸出向量為y，并計(jì)算出了y的伴隨式s=yHT。t是任意一個(gè)滿足方程s=tHT的N維行向量。則：y-t是一個(gè)碼字

。證明(y-t)HT=yHT-tHT=s-s=全0的N-L維行向量，因此y-t是一個(gè)碼字。證完。結(jié)論（3）的注解：當(dāng)輸入碼字為該y-t，差錯(cuò)向量為該t時(shí)，輸出向量必然為該y。換句話說(shuō)，此時(shí)的t就是一個(gè)“可能的差錯(cuò)向量”。結(jié)論（2）和結(jié)論（3）的綜合結(jié)論：設(shè)輸出向量y，并計(jì)算出了y的伴隨式s=yHT。則此時(shí)所有“可能的差錯(cuò)向量”，恰好就是方程s=tHT的所有解t。2023/2/530§6.5譯碼方法和糾錯(cuò)能力（4）設(shè)輸出向量為y，并計(jì)算出了y的伴隨式s=yHT。則此時(shí)所有“可能的差錯(cuò)向量”，恰好就是任何一個(gè)“可能的差錯(cuò)向量”加上全體碼字。換句話說(shuō)，此時(shí)所有“可能的差錯(cuò)向量”，恰好就是方程s=tHT的任何一個(gè)固定解t加上全體碼字。（證明思想：非齊次通解=非齊次特解+齊次通解）（5）每個(gè)伴隨式所對(duì)應(yīng)的“可能的差錯(cuò)向量”共有DL個(gè)。伴隨式是N-L維行向量，因此有DN-L個(gè)不同的伴隨式。不同的伴隨式所對(duì)應(yīng)的“可能的差錯(cuò)向量”不會(huì)重合。DLDN-L=DN。定義在以s為伴隨式的全體“可能的差錯(cuò)向量”中，取一個(gè)Hamming重量最小的向量稱為s的陪集首，記為e(s)。（在以s為伴隨式的全體“可能的差錯(cuò)向量”中，Hamming重量最小的向量或許有不止一個(gè)。任意選擇一個(gè)作為陪集首e(s)即可）2023/2/531§6.5譯碼方法和糾錯(cuò)能力（6）對(duì)信道的輸出向量y，計(jì)算伴隨式s=yHT，以s為地址查找陪集首e(s)，計(jì)算u=y-e(s)。則u就是在所有碼字中與y的Hamming距離最小的碼字。證明首先，注意到e(s)是一個(gè)“可能的差錯(cuò)向量”。因此uHT=yHT-e(s)HT=s-s=全0的N-L維行向量，說(shuō)明u=y-e(s)是一個(gè)碼字。其次，對(duì)任意另一個(gè)碼字c，(y-c)HT=yHT-cHT=yHT=s。這就是說(shuō)，(y-c)是另外一個(gè)“可能的差錯(cuò)向量”。另一方面，(y-u)=e(s)是以s為伴隨式的所有“可能的差錯(cuò)向量”中Hamming重量最小的。所以w(y-u)≤w(y-c)，即d(y,u)≤w(y,c)。證完。2023/2/532§6.5譯碼方法和糾錯(cuò)能力實(shí)用糾錯(cuò)譯碼算法預(yù)計(jì)算對(duì)每個(gè)伴隨式（即N-L維行向量）s，尋找s的陪集首e(s)，并以s為地址存儲(chǔ)e(s)。（預(yù)計(jì)算的總體計(jì)算量很大，但有許多技巧可以大幅度地減少計(jì)算量）現(xiàn)場(chǎng)糾錯(cuò)譯碼

（1）對(duì)信道的輸出向量y，計(jì)算伴隨式s=yHT。（2）以s為地址查找陪集首e(s)。（3）將輸出向量y譯為碼字u=y-e(s)。結(jié)束。u就是在所有碼字中與y的Hamming距離最小的碼字。2023/2/533§6.5譯碼方法和糾錯(cuò)能力現(xiàn)場(chǎng)糾錯(cuò)譯碼的計(jì)算量計(jì)算量最大的是第（2）步。因?yàn)閟是N-L維行向量，所以查找s的計(jì)算量是logDN-L=(N-L)logD

（而不是DN-L）?？傊?，計(jì)算量遠(yuǎn)遠(yuǎn)小于直接使用最小距離準(zhǔn)則的計(jì)算量DL。2023/2/534§6.5譯碼方法和糾錯(cuò)能力線性分組碼的檢錯(cuò)能力和糾錯(cuò)能力首先我們發(fā)現(xiàn)，能否正確譯碼并不依賴于輸入的是什么碼字，僅僅依賴于真正的差錯(cuò)向量是什么。顯然P(正確譯碼)=P(真正的差錯(cuò)向量是某個(gè)陪集首)。其次我們可以定義更加簡(jiǎn)單的檢錯(cuò)能力和糾錯(cuò)能力。定義6.1.3

線性分組碼的最小Hamming距離定義為兩個(gè)不同碼字的Hamming距離的最小值，記為dmin。線性分組碼的最小Hamming重量定義為非全0碼字的Hamming重量的最小值，記為wmin。2023/2/535§6.5譯碼方法和糾錯(cuò)能力引理1

dmin=wmin。證明設(shè)兩個(gè)不同的碼字u(1)和u(2)，使得dmin=d(u(1),u(2))=w(u(1)-u(2))。注意到(u(1)-u(2))是一個(gè)非全0碼字，所以dmin≥wmin。設(shè)一個(gè)非全0碼字u，使得wmin=w(u)=w(u-全0碼字)=d(u,全0碼字)。所以dmin≤wmin。證完。2023/2/536§6.5譯碼方法和糾錯(cuò)能力引理2

設(shè)信道的輸入為碼字u，信道的輸出為向量y，差錯(cuò)向量（注：真正的差錯(cuò)向量）為e=y-u。則（1）當(dāng)w(e)<dmin，yHT肯定不是全0的N-L維向量，因而發(fā)現(xiàn)信道傳輸錯(cuò)誤。（2）當(dāng)w(e)≤[(dmin-1)/2]（下方取整），由上述實(shí)用糾錯(cuò)譯碼算法肯定將y譯為真正的輸入碼字u，而不會(huì)將y譯為其它碼字。2023/2/537§6.5譯碼方法和糾錯(cuò)能力證明（1）當(dāng)w(e)<dmin，e肯定不是碼字。因此yHT=eHT≠全0的N-L維向量。（2）當(dāng)w(e)≤[(dmin-1)/2]（下方取整），則y與任意另一個(gè)碼字c的Hamming距離d(c,y)≥d(c,u)-d(y,u)（三角不等式）≥dmin-d(y,u)=dmin-w(e)≥dmin-[(dmin-1)/2]>[(dmin-1)/2]

≥w(e)=d(y,u)因此，所有碼字中，u與y的Hamming距離最小。證完。2023/2/538§6.5譯碼方法和糾錯(cuò)能力引理3

設(shè)差錯(cuò)向量（注：真正的差錯(cuò)向量）為e。當(dāng)w(e)>[(dmin-1)/2]（下方取整），由上述實(shí)用糾錯(cuò)譯碼算法未必將輸出向量譯為真正的輸入碼字。舉例取兩個(gè)碼字u，c，恰好滿足d(c,u)=dmin。（請(qǐng)注意，這樣的兩個(gè)碼字u，c存在！）取向量y滿足：d(y,u)=[(dmin-1)/2]+1>[(dmin-1)/2]；d(c,u)=d(c,y)+d(y,u)。（三角不等式變?yōu)榈仁剑ㄕ?qǐng)注意，這樣的向量y存在?。┐藭r(shí)d(c,y)=d(c,u)-d(y,u)=dmin-{[(dmin-1)/2]+1}=dmin-1-[(dmin-1)/2]。2023/2/539d(y,u)=[(dmin-1)/2]+1；

d(c,y)=dmin-1-[(dmin-1)/2]。當(dāng)dmin是奇數(shù)時(shí)，d(y,u)=(dmin-1)/2+1，d(c,y)=(dmin-1)/2，故d(c,y)<d(y,u)。當(dāng)dmin是偶數(shù)時(shí)，d(y,u)=dmin/2，d(c,y)=dmin/2，故d(c,y)=d(y,u)。這就是說(shuō)，如果輸入碼字u，輸出向量y，則當(dāng)dmin是奇數(shù)時(shí)，將y譯為c而不是u；當(dāng)dmin是偶數(shù)時(shí)，將y譯為c或u都符合最小距離準(zhǔn)則。2023/2/540§6.5譯碼方法和糾錯(cuò)能力對(duì)引理2和引理3的解釋設(shè)信道真正的輸入碼字為u，信道的輸出向量為y，真正的差錯(cuò)向量為e=y-u。采用實(shí)用糾錯(cuò)譯碼算法：接收y→計(jì)算伴隨式s=yHT→以s為地址查找e(s)→計(jì)算c=y-e(s)→認(rèn)為陪集首e(s)就是差錯(cuò)向量；認(rèn)為c就是輸入碼字。引理2告訴我們，如果w(e)≤[(dmin-1)/2]

，則e(s)=e，因而c=u。引理3告訴我們，如果w(e)>[(dmin-1)/2]

，則未必e(s)=e，因而未必c=u。換句話說(shuō)，如果w(e)≤[(dmin-1)/2]

，則e一定是s=eHT的陪集首；如果w(e)>[(dmin-1)/2]

，則e未必是s=eHT的陪集首。2023/2/541§6.5譯碼方法和糾錯(cuò)能力定理6.5.4

記真正的差錯(cuò)向量為e。記t是一個(gè)非負(fù)整數(shù)。如果（1）當(dāng)w(e)≤t時(shí)總是能夠正確譯碼，（2）當(dāng)w(e)>t時(shí)并不總是能夠正確譯碼，則t

=[(dmin-1)/2]。推論記真正的差錯(cuò)向量為e。事件“總是能夠正確譯碼”定義為“w(e)≤[(dmin-1)/2]”。則“總是能夠正確譯碼”的概率為2023/2/542§6.5譯碼方法和糾錯(cuò)能力定理6.5.4說(shuō)明，dmin是線性分組碼糾錯(cuò)能力的一個(gè)指標(biāo)。dmin越大，[(dmin-1)/2]就越大，“總是能夠正確譯碼”的概率也越大。當(dāng)N比L大得越多，碼字在所有N維向量中占的比例越小，越容易使得dmin大。問(wèn)題是，當(dāng)N和L都確定時(shí)，如何設(shè)計(jì)碼使得dmin大。糾正一種誤解：dmin越大，“總是能夠正確譯碼”的概率越大。決不能說(shuō)：dmin越大，正確譯碼的概率越大。

（??P185,式子6.5.8）2023/2/543§6.5譯碼方法和糾錯(cuò)能力例

二元（6，3）線性分組碼，生成矩陣G已經(jīng)給出。求一致校驗(yàn)矩陣H；碼字集合；譯碼預(yù)計(jì)算（簡(jiǎn)化計(jì)算量）。

顯然是系統(tǒng)碼。2023/2/544§6.5譯碼方法和糾錯(cuò)能力信息向量→碼字000→000000100→011100010→101010001→110001110→110110101→101101011→011011111→0001112023/2/545§6.5譯碼方法和糾錯(cuò)能力伴隨式s→對(duì)應(yīng)的所有“可能的差錯(cuò)向量”e000→000000，011100，101010，110001，110110，101101，011011，000111100→100000，111100，001010，010001，010110，001101，111011，100111010→010000，001100，111010，100001，100110，111101，001011，010111001→001000，010100，100010，111001，111110，100101，010011，001111110→000100，011000，101110，110101，110010，101001，011111，000011101→000010，011110，101000，110011，110100，101111，011001，000101011→000001，011101，101011，110000，110111，101100，011010，000110111→100100，111000，001110，010101，010010，001001，111111，100011伴隨式s→陪集首e(s)000→000000100→100000010→010000001→001000110→000100101→000010011→000001111→1001002023/2/546§6.5譯碼方法和糾錯(cuò)能力dmin=3；[(dmin-1)/2]=1。當(dāng)真正的差錯(cuò)向量的Hamming重量不超過(guò)1時(shí)，總是能夠正確譯碼；當(dāng)真正的差錯(cuò)向量的Hamming重量超過(guò)1時(shí)，未必總是能夠正確譯碼?？偸悄軌蛘_譯碼的概率為(1-p)6+6(1-p)5p。正確譯碼的概率為(1-p)6+6(1-p)5p+(1-p)4p2。（p185,式6.5.8）若p=10-2，則(1-p)6=0.9415；

(1-p)6+6(1-p)5p=0.9986；

(1-p)6+6(1-p)5p+(1-p)4p2=0.9987。2023/2/547§6.5譯碼方法和糾錯(cuò)能力設(shè)信道的輸出向量為y=(111111)。計(jì)算伴隨式s=yHT=(111)。以s為地址查找e(s)=(100100)。計(jì)算c=y-e(s)=(111111)-(100100)=(011011)。信息向量為(011)。2023/2/548§6.4、§6.6、§6.7、§6.8一些特殊的線性分組碼二元Hamming碼N=2m-1，L=2m-1-m，即二元(2m-1，2m-1-m)線性分組碼。其校驗(yàn)矩陣是如下的m×(2m-1)階矩陣H：H的(2m-1)列恰好是(2m-1)個(gè)非全0的m維向量。因此：校驗(yàn)矩陣H的任意一列不是全0的m維向量；校驗(yàn)矩陣H的任意兩列互不相同；校驗(yàn)矩陣H的某三列的和為全0的m維向量。換句話說(shuō)，重量為1、重量為2的2m-1維向量都不是碼字，而某些重量為3的2m-1維向量是碼字。再換句話說(shuō)，Hamming碼的dmin=3。再換句話說(shuō)，當(dāng)差錯(cuò)向量的重量不超過(guò)1時(shí)，肯定能夠正確譯碼。編碼效率為R=(2m-1-m)/(2m-1)

。（編碼效率大）2023/2/549§6.4、§6.6、§6.7、§6.8一些特殊的線性分組碼定義

如果存在一個(gè)t，使得任一個(gè)接收向量y，都有唯一的碼字u滿足d(y,u)≤t，則稱該碼為t階完備碼。命題當(dāng)一個(gè)(N，L)線性分組碼是t階完備碼時(shí)，所有不同伴隨式所對(duì)應(yīng)的陪集首恰好是所有重量不超過(guò)t的N維向量。注意：不同伴隨式的個(gè)數(shù)為2N-L，重量不超過(guò)t的N維向量的個(gè)數(shù)為定理

二元Hamming碼（它是二元(2m-1，2m-1-m)線性分組碼）是1階完備碼。（2m=1+2m-1）2023/2/550§6.4、§6.6、§6.7、§6.8一些特殊的線性分組碼Hadamard碼從Hadmard矩陣的行中選擇碼字可以構(gòu)造出Hadamad碼。Hadmard矩陣Mn是一個(gè)n×n階矩陣，其中n=2m。該矩陣滿足有一行為全0行，其余的行有2m-1個(gè)0，2m-1個(gè)1。任意兩行有2m-1個(gè)位置不同，2m-1個(gè)位置相同。如何構(gòu)造Hadmard矩陣？看如下的遞歸方法。2023/2/551§6.4、§6.6、§6.7、§6.8一些特殊的線性分組碼以Hadmard矩陣Mn的所有行作為所有的碼字，得到的碼就是Hadamad碼。Hadamad碼的參數(shù)如下：共有n個(gè)碼字，因此共有n個(gè)信息，因此信息長(zhǎng)為logn=m。碼長(zhǎng)為n。編碼效率為R=m/n=m/2m。（編碼效率小）任何兩個(gè)碼字的Hamming距離都等于2m-1=n/2。因此dmin=2m-1=n/2。Mn的任意m個(gè)非全0行都是線性無(wú)關(guān)的，因此生成矩陣可能是Mn的任意m個(gè)非全0行構(gòu)成的m×n階矩陣。（？）2023/2/552§6.4、§6.6、§6.7、§6.8一些特殊的線性分組碼Golay碼Golay碼是線性(23,12)碼，最小距離為7。將其增加一個(gè)全校驗(yàn)位擴(kuò)展為二元線性（24,12）碼，最小距離為8，稱為擴(kuò)展Golay碼。表6.4.1給出了Golay碼和擴(kuò)展Golay碼的重量分布。循環(huán)碼定義6.6.1(p188)一個(gè)二元(N,L)線性分組碼C，若對(duì)任意c=(c0,c1,c2,…,cN-1)∈C，恒有c'=(cN-1,c0,c1,…,cN-2)∈C，則稱C為二元循環(huán)碼。2023/2/553§6.4、§6.6、§6.7、§6.8一些特殊的線性分組碼二元循環(huán)碼的產(chǎn)生過(guò)程取二元域GF(2)=({0,1},(mod2)加法,(mod2)乘法)。取GF(2)上的N次多項(xiàng)式1+xN。取多項(xiàng)式1+xN的（在GF(2)上的）一個(gè)N-L次因式g(x)：g(x)=g0+g1x1+g2x2+…+gN-L

xN-L。取以下的L×N矩陣G作為二元(N,L)線性分組碼C的生成矩陣，則該碼一定就是一個(gè)二元循環(huán)碼。（主教材中有證明）2023/2/554§6.4、§6.6、§6.7、§6.8一些特殊的線性分組碼例6.6.1(p190)~例6.6.2(p192)取N=7。則（在GF(2)上）：

1+x7=(1+x)(1+x+x3)(1+x2+x3)。若取g(x)=1+x+x3

，則產(chǎn)生的二元(7,4)線性分組碼C一定就是一個(gè)二元循環(huán)碼，生成矩陣為2023/2/555§6.4、§6.6、§6.7、§6.8一些特殊的線性分組碼如此產(chǎn)生的二元循環(huán)碼的譯碼設(shè)接收向量為y=(y0,y1,y2,…,yN-1)。記y(x)=y0+y1x1+y2x2+…+yN-1xN-1

。用g(x)除y(x)，得余式s(x)=s0+s1x1+s2x2+…+sN-L-1xN-L-1

。則此時(shí)：除式y(tǒng)(x)=q(x)g(x)+s(x)也可以表示成y(x)≡s(x)(modg(x))。余式s(x)的次數(shù)一定不超過(guò)N-L-1。N-L維向量s=(s0,s1,s2,…,sN-L-1)就是接收向量y的伴隨式。（因而不需要校驗(yàn)矩陣）2023/2/556習(xí)題課6.1設(shè)有4個(gè)消息al，a2，a3

和a4被編成為長(zhǎng)為5的二元碼的00000，01101，10111，l1010。(a)試給出碼的一致校驗(yàn)關(guān)系。(b)若通過(guò)轉(zhuǎn)移概率為p<1/2的BSC傳送，試給出最佳譯碼表及相應(yīng)的譯碼錯(cuò)誤概率表示式。(c)若碼通過(guò)BEC信道傳送，試問(wèn)可恢復(fù)幾個(gè)刪除?其最佳譯碼表應(yīng)如何配置？(d)一般，最小距離為dmin的線性碼，可恢復(fù)幾個(gè)刪除?2023/2/557習(xí)題課(a)首先需要驗(yàn)證該碼是線性碼：01101‘+’10111=l1010。其次需要給出該碼的生成矩陣和校驗(yàn)矩陣：最后該碼的一致校驗(yàn)關(guān)系為：對(duì)任意碼字(x0x1x2x3x4)，恒有x0+x1+x2=0，x0+x3=0，x0+x1+x4=0。2023/2/558習(xí)題課(b)通過(guò)轉(zhuǎn)移概率為p<1/2的BSC傳送。如果直接按照“最小距離準(zhǔn)則”來(lái)求最佳譯碼表，則最佳譯碼表為接收向量譯為00000，00001，00010，00100，01000，10000，10100，10001。0000001101，01100，01111，01001，00101，11101，11001，11100。0110110111，10110，10101，10011，11111，00111，00011，00110。1011111010，11011，11000，11110，10010，01010，01110，01011。

l10102023/2/559習(xí)題課求“譯碼錯(cuò)誤概率表示式”，可以有多種含義。本題應(yīng)該理解為以下的含義，而不應(yīng)該理解為別的含義：2023/2/560求最佳譯碼表，當(dāng)然也可以采用標(biāo)準(zhǔn)方法，先求可能的差錯(cuò)向量、伴隨式、陪集首的關(guān)系：可能的差錯(cuò)向量伴隨式陪集首00000，01101，10111，11010。0000000000001，01100，10110，11011。0010000100010，01111，10101，11000。0100001000100，01001，10011，11110。1000010001000，00101，11111，10010。1010100010000，11101，00111，01010。1111000010100，11001，00011，01110。0111010010001，11100，00110，01011。110100012023/2/561習(xí)題課根據(jù)公式：“接收向量”-“陪集首”=“所要譯為的碼字”，得到的最佳譯碼表仍然是接收向量譯為00000，00001，00010，00100，01000，10000，10100，10001。0000001101，01100，01111，01001，00101，11101，11001，11100。0110110111，10110，10101，10011，11111，00111，00011，00110。1011111010，11011，11000，11110，10010，01010，01110，01011。

l10102023/2/562習(xí)題課求“譯碼錯(cuò)誤概率表示式”，第一種的理解是：2023/2/563習(xí)題課求“譯碼錯(cuò)誤概率表示式”，第二種的理解是：2023/2/564(c)若碼通過(guò)BEC信道傳送，則至少可恢復(fù)dmin-1=2個(gè)刪除。因此，當(dāng)接收向量中有不超過(guò)2個(gè)刪除時(shí)，對(duì)應(yīng)譯碼值是顯然的。當(dāng)接收向量中有大于2個(gè)刪除時(shí)，對(duì)應(yīng)譯碼值比較復(fù)雜。(d)一般，最小距離為dmin的線性碼，可恢復(fù)dmin-1個(gè)刪除。理由很簡(jiǎn)單：一個(gè)碼字，它的dmin-1個(gè)分量“模糊不清”，根據(jù)該碼字的其它N-(dmin-1)個(gè)分量來(lái)唯一