信息論與編碼理論基礎第六章

信息論與編碼理論基礎第六章第一頁，共六十九頁，2022年，8月28日2023/1/181§6.1分組碼的概念設信道是一個D元字母輸入/D元字母輸出的DMC信道，字母表為{0,1,…,D-1}。其信道轉移概率矩陣為D×D矩陣傳輸錯誤的概率為

p。信道容量為C=logD-H(p)-plog(D-1)。第二頁，共六十九頁，2022年，8月28日2023/1/182§6.1分組碼的概念對隨機變量序列X1X2…進行的信道編碼為(N,L)碼：(X1X2…XL)→(U1U2…UN)=C(X1X2…XL)。這個(N,L)碼又稱為(N,L)分組碼。已經(jīng)有結論：當設備所確定的編碼速率R<C/H(X)時，存在(N,L)分組碼，使得實際編碼速率(信息率L/N)任意接近R，譯碼錯誤的概率任意接近0。問題是：怎樣構造這樣的分組碼？這樣的分組碼的編碼、譯碼計算量會不會太大？（這才是研究分組碼的含義）

第三頁，共六十九頁，2022年，8月28日2023/1/183§6.1分組碼的概念預備知識1：有限域設D是一個素數(shù)。于是字母表{0,1,…,D-1}中的所有字母關于(modD)加法、(modD)乘法構成了一個封閉的代數(shù)結構，稱作有限域，又稱作Galois域，記作GF(D)：GF(D)=({0,1,…,D-1},(modD)加法,(modD)乘法)。即（1）({0,1,…,D-1},(modD)加法)構成交換群（Abel群）。（2）({1,…,D-1},(modD)乘法)構成交換群（Abel群）。（3）分配律成立：a(b+c)(modD)=ab+ac(modD)。第四頁，共六十九頁，2022年，8月28日2023/1/184§6.1分組碼的概念注1：如果D不是素數(shù)，({0,1,…,D-1},(modD)加法,(modD)乘法)不是有限域，只是有限環(huán)。注2：有限域GF(D)上的線性代數(shù)完全類似于實數(shù)域上的線性代數(shù)，線性代數(shù)的所有內容都在“加法”和“乘法”基礎上得到。元素的“加法”負元；非0元的“乘法”逆元；一組向量是否“線性無關”的概念以及所有等價的判別方法；矩陣的“秩”的概念以及所有計算方法；方陣是否“可逆”的所有判別方法；求方陣的“逆陣”的所有算法；關于對稱矩陣的所有結論；等等。注3：有限域GF(D)與實數(shù)域的區(qū)別是：傳統(tǒng)的“逼近”、“極限”的概念消失了。第五頁，共六十九頁，2022年，8月28日2023/1/185例：取D=2，則GF(2)=({0,1},(mod2)加法,(mod2)乘法)。運算規(guī)則為：

0+0=1+1=0，0+1=1，0×0=0×1=0，1×1=1。方陣是否可逆？回答是肯定的。兩種不同的判別方法都能夠證明它是可逆的：（1）它經(jīng)過可逆行變換能夠變成單位陣；（2）它的行列式不等于0。（等于1?。┑诹?，共六十九頁，2022年，8月28日2023/1/186§6.1分組碼的概念該方陣的逆矩陣是什么？怎樣計算？做聯(lián)合可逆行變換：第七頁，共六十九頁，2022年，8月28日2023/1/187§6.1分組碼的概念例：取D=3，則GF(3)=({0,1,2},(mod3)加法,(mod3)乘法))。運算規(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。矩陣是不是滿行秩的？換句話說，此矩陣的三個行向量是不是在域GF(3)上線性無關的？再換句話說，能否保證此矩陣的各行的任何非0線性組合都不是全0的4維向量？再換句話說，此矩陣能否通過一些可逆行變換變成一個“階梯陣”？第八頁，共六十九頁，2022年，8月28日2023/1/188§6.1分組碼的概念可逆行變換第九頁，共六十九頁，2022年，8月28日2023/1/189§6.1分組碼的概念例：域GF(D)上的一個L行N列的矩陣（L×N階的矩陣）G，設它是滿行秩的（當然此時有L≤N）。則變換(u1,u2,…,uN)=(x1,x2,…,xL)G一定是單射(即(x1,x2,…,xL)的不同值一定變換為(u1,u2,…,uN)的不同值)。證明設u(1)=x(1)G，u(2)=x(2)G，且x(1)≠x(2)。要證明u(1)≠u(2)。根據(jù)線性性質，u(1)-u(2)=(x(1)-x(2))G，因為(x(1)-x(2))≠全0的L維向量，所以(x(1)-x(2))G是G的各行的非0線性組合。G滿行秩，所以(x(1)-x(2))G≠全0的N維向量。所以u(1)≠u(2)。第十頁，共六十九頁，2022年，8月28日2023/1/1810§6.1分組碼的概念預備知識2：有限域上的分組碼當D是素數(shù)時，分組碼可以充分利用有限域GF(D)的代數(shù)運算，使得編碼和譯碼更加簡便。第十一頁，共六十九頁，2022年，8月28日2023/1/1811§6.2線性分組碼定義取GF(D)上的一個L行N列的矩陣G，它是滿行秩的。(N,L)分組碼定義為(u1,u2,…,uN)=(x1,x2,…,xL)G其中(x1,x2,…,xL)是信息向量，(u1,u2,…,uN)是對應的碼字。（1）稱此碼為D元(N,L)線性分組碼。（2）稱矩陣G為此碼的生成矩陣。第十二頁，共六十九頁，2022年，8月28日2023/1/1812§6.2線性分組碼線性分組碼的代數(shù)結構命題1不同的信息向量對應不同的碼字。（因為矩陣G是滿行秩的，所以變換u=xG是單射）命題2生成矩陣G的第1行是信息向量(1,0,0,…,0)的碼字；生成矩陣G的第2行是信息向量(0,1,0,…,0)的碼字；…生成矩陣G的第L行是信息向量(0,…,0,0,1)的碼字。第十三頁，共六十九頁，2022年，8月28日2023/1/1813§6.2線性分組碼命題3信息向量(x1,x2,…,xL)的碼字是：x1數(shù)乘G的第1行，加x2數(shù)乘G的第2行，加…，加xL數(shù)乘G的第L行。換句話說，任何一個碼字都是生成矩陣G的線性組合。命題4當u(1)和u(2)都是碼字，u(1)+u(2)也是碼字。（線性分組碼的碼字關于線性運算封閉）證明設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))的碼字。證完。第十四頁，共六十九頁，2022年，8月28日2023/1/1814§6.2線性分組碼（命題3和命題4告訴我們，一個N維向量是一個碼字，當且僅當它是生成矩陣G的第1行~第L行的線性組合。還告訴我們，線性分組碼的碼字集合構成一個線性空間。這個線性空間是幾維的？L維的，因為生成矩陣G的第1行~第L行恰好是該線性空間的一組基）命題5設一個D元(N,L)線性分組碼的生成矩陣為G。設另一個D元(N,L)線性分組碼的生成矩陣為G'=MG，其中M是L階可逆方陣。則兩個碼的碼字集合完全重合，只是信息向量與碼字的對應關系不同。換句話說，如果把線性分組碼的生成矩陣G做可逆行變換變成另一個生成矩陣，則不改變碼字集合，只改變信息向量與碼字的對應關系。第十五頁，共六十九頁，2022年，8月28日2023/1/1815§6.2線性分組碼證明（要證明，第一個碼中任一個碼字也是第二個碼中的碼字；第二個碼中任一個碼字也是第一個碼中的碼字）設在第一個碼中，u是信息向量x的碼字：u=xG；則在第二個碼中，u是信息向量xM-1的碼字：u=xM-1MG=xM-1G'。設在第二個碼中，u是信息向量x的碼字：u=xG'；則在第一個碼中，u是信息向量xM的碼字：u=xMM-1G'=xMG。證完。

第十六頁，共六十九頁，2022年，8月28日2023/1/1816§6.2線性分組碼線性分組碼的特例：系統(tǒng)碼定義(p178)

D元(N,L)線性分組碼的生成矩陣為G=[PL×(N-L),IL]，其中IL是L階單位陣，PL×(N-L)是L×(N-L)階矩陣。則稱此碼為系統(tǒng)碼。此時信息向量(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位為碼字的一致校驗位。第十七頁，共六十九頁，2022年，8月28日2023/1/1817§6.2線性分組碼例

此二元(7,4)碼是線性分組碼，生成矩陣G是由信息向量(1000)、(0100)、(0010)、(0001)的碼字組成的4行第十八頁，共六十九頁，2022年，8月28日2023/1/1818§6.2線性分組碼例此二元(5,3)線性分組碼的生成矩陣是第十九頁，共六十九頁，2022年，8月28日2023/1/1819§6.3線性分組碼的校驗矩陣線性分組碼的校驗矩陣定理(p179)

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

由上述定理所描述的矩陣H稱為D元(N,L)線性分組碼的校驗矩陣。第二十頁，共六十九頁，2022年，8月28日2023/1/1820§6.3線性分組碼的校驗矩陣有以下的結論。（1）一個線性分組碼有很多校驗矩陣。一個校驗矩陣H經(jīng)過可逆行變換變?yōu)镠

'，

H

'是同一個線性分組碼的另一個校驗矩陣。（2）固定一個校驗矩陣H。則一個N維向量u是一個碼字，當且僅當：uHT=全0的N-L維行向量。（3）設一個D元(N,L)線性分組碼的生成矩陣G，校驗矩陣H。則H是一個D元(N,N-L)線性分組碼的生成矩陣，G是此碼的一個校驗矩陣。稱這兩個碼互為對偶碼。D元(N,L)線性分組碼D元(N,N-L)線性分組碼生成矩陣G校驗矩陣H生成矩陣H校驗矩陣G第二十一頁，共六十九頁，2022年，8月28日2023/1/1821§6.3線性分組碼的校驗矩陣（怎樣由生成矩陣G計算出校驗矩陣H？）（4）設D元(N,L)線性分組碼是系統(tǒng)碼，生成矩陣為G=[P,IL]，其中IL是L階單位陣，P是L×(N-L)階矩陣。則校驗矩陣可以取為H=[IN-L,-PT]，其中IN-L是N-L階單位陣，PT是P

的轉置矩陣。證明GHT=[P,IL][IN-L,-PT]T=P-P=OL×(N-L)。證完。（5）設D元(N,L)線性分組碼的生成矩陣經(jīng)過可逆行變換后變?yōu)閇P,IL]，則校驗矩陣也可以取為H=[IN-L,-PT]。第二十二頁，共六十九頁，2022年，8月28日2023/1/1822§6.3線性分組碼的校驗矩陣第二十三頁，共六十九頁，2022年，8月28日2023/1/1823§6.5譯碼方法和糾錯能力線性分組碼的糾錯譯碼準則定義

(已知)一個N維向量u的Hamming重量定義為它的對應位置值不等于0的位數(shù)。記為w(u)。兩個N維向量u(1)和u(2)的Hamming距離定義為它們的對應位置值不相同的位數(shù)。記為d(u(1),u(2))。顯然有以下的結論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))。或w(u(1)-u(3))≤w(u(1)-u(2))+w(u(2)-u(3))。第二十四頁，共六十九頁，2022年，8月28日2023/1/1824§6.5譯碼方法和糾錯能力設GF(D)上的D元(N,L)線性分組碼，生成矩陣為G。將信息向量x編碼，得到碼字u=xG。將碼字u輸入信道。信道的輸出值為y。使用最小距離準則：給定輸出值y，尋找碼字c使d(y,c)最小。將輸出值y譯為碼字c。當c=u時，就實現(xiàn)了正確譯碼。直接使用最小距離準則的困難：需要將DL個碼字與輸出值y的Hamming距離進行對比，才能找到碼字c使d(y,c)最小。計算量大。(窮舉搜索)第二十五頁，共六十九頁，2022年，8月28日2023/1/1825編碼-譯碼過程圖示。其中

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

c(1)、c(2)、c(3)、c(4)是各個對應碼字。第二十六頁，共六十九頁，2022年，8月28日2023/1/1826§6.5譯碼方法和糾錯能力實用糾錯譯碼算法的預備知識：差錯向量和伴隨式定義

設信道的輸入為碼字u；信道的輸出值為向量y。稱向量e=y-u為差錯向量，或差錯圖樣。（請注意：①此時y=u+e；u=y-e；向量的加減法是對應分量的(modD)加減法。②在信道的輸出端，只能得到輸出向量y，并不能得到差錯向量e，因此不能得到輸入碼字u。）定義(p195)設H是校驗矩陣。對于N維行向量t，記s=tHT并稱N-L維行向量s為N維行向量t的伴隨式。第二十七頁，共六十九頁，2022年，8月28日2023/1/1827§6.5譯碼方法和糾錯能力有以下的結論。（1）N維行向量t是一個碼字，當且僅當t的伴隨式是一個全0的N-L維行向量。（這是已知的結論）（2）設信道的輸入碼字u，輸出向量y，差錯向量e=y-u，則e的伴隨式等于y的伴隨式。證明eHT=(y-u)HT=yHT-uHT=yHT。證完。結論（2）的注解：在信道的輸出端，雖然不能得到差錯向量，卻能計算出差錯向量的伴隨式：它恰好等于輸出向量的伴隨式。換句話說，設輸出向量為y，并計算出y的伴隨式s=yHT。則此時雖然不能確切地得到差錯向量，但任何一個“可能的差錯向量”e都滿足方程eHT=s第二十八頁，共六十九頁，2022年，8月28日2023/1/1828§6.5譯碼方法和糾錯能力（3）設輸出向量為y，并計算出了y的伴隨式s=yHT。t是任意一個滿足方程s=tHT的N維行向量。則：y-t是一個碼字

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

（1）對信道的輸出向量y，計算伴隨式s=yHT。（2）以s為地址查找陪集首e(s)。（3）將輸出向量y譯為碼字u=y-e(s)。結束。u就是在所有碼字中與y的Hamming距離最小的碼字。第三十二頁，共六十九頁，2022年，8月28日2023/1/1832§6.5譯碼方法和糾錯能力現(xiàn)場糾錯譯碼的計算量計算量最大的是第（2）步。因為s是N-L維行向量，所以查找s的計算量是logDN-L=(N-L)logD

（而不是DN-L）。總之，計算量遠遠小于直接使用最小距離準則的計算量DL。第三十三頁，共六十九頁，2022年，8月28日2023/1/1833§6.5譯碼方法和糾錯能力線性分組碼的檢錯能力和糾錯能力首先我們發(fā)現(xiàn)，能否正確譯碼并不依賴于輸入的是什么碼字，僅僅依賴于真正的差錯向量是什么。顯然P(正確譯碼)=P(真正的差錯向量是某個陪集首)。其次我們可以定義更加簡單的檢錯能力和糾錯能力。定義

線性分組碼的最小Hamming距離定義為兩個不同碼字的Hamming距離的最小值，記為dmin。線性分組碼的最小Hamming重量定義為非全0碼字的Hamming重量的最小值，記為wmin。第三十四頁，共六十九頁，2022年，8月28日2023/1/1834§6.5譯碼方法和糾錯能力引理1

dmin=wmin。證明設兩個不同的碼字u(1)和u(2)，使得dmin=d(u(1),u(2))=w(u(1)-u(2))。注意到(u(1)-u(2))是一個非全0碼字，所以dmin≥wmin。設一個非全0碼字u，使得wmin=w(u)=w(u-全0碼字)=d(u,全0碼字)。所以dmin≤wmin。證完。第三十五頁，共六十九頁，2022年，8月28日2023/1/1835§6.5譯碼方法和糾錯能力引理2

設信道的輸入為碼字u，信道的輸出為向量y，差錯向量（注：真正的差錯向量）為e=y-u。則（1）當w(e)<dmin，yHT肯定不是全0的N-L維向量，因而發(fā)現(xiàn)信道傳輸錯誤。（2）當w(e)≤[(dmin-1)/2]（下方取整），由上述實用糾錯譯碼算法肯定將y譯為真正的輸入碼字u，而不會將y譯為其它碼字。第三十六頁，共六十九頁，2022年，8月28日2023/1/1836§6.5譯碼方法和糾錯能力證明（1）當w(e)<dmin，e肯定不是碼字。因此yHT=eHT≠全0的N-L維向量。（2）當w(e)≤[(dmin-1)/2]（下方取整），則y與任意另一個碼字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距離最小。證完。第三十七頁，共六十九頁，2022年，8月28日2023/1/1837§6.5譯碼方法和糾錯能力引理3

設差錯向量（注：真正的差錯向量）為e。當w(e)>[(dmin-1)/2]（下方取整），由上述實用糾錯譯碼算法未必將輸出向量譯為真正的輸入碼字。舉例取兩個碼字u，c，恰好滿足d(c,u)=dmin。（請注意，這樣的兩個碼字u，c存在?。┤∠蛄縴滿足：d(y,u)=[(dmin-1)/2]+1>[(dmin-1)/2]；d(c,u)=d(c,y)+d(y,u)。（三角不等式變?yōu)榈仁剑ㄕ堊⒁?，這樣的向量y存在?。┐藭rd(c,y)=d(c,u)-d(y,u)=dmin-{[(dmin-1)/2]+1}=dmin-1-[(dmin-1)/2]。第三十八頁，共六十九頁，2022年，8月28日2023/1/1838d(y,u)=[(dmin-1)/2]+1；

d(c,y)=dmin-1-[(dmin-1)/2]。當dmin是奇數(shù)時，d(y,u)=(dmin-1)/2+1，d(c,y)=(dmin-1)/2，故d(c,y)<d(y,u)。當dmin是偶數(shù)時，d(y,u)=dmin/2，d(c,y)=dmin/2，故d(c,y)=d(y,u)。這就是說，如果輸入碼字u，輸出向量y，則當dmin是奇數(shù)時，將y譯為c而不是u；當dmin是偶數(shù)時，將y譯為c或u都符合最小距離準則。第三十九頁，共六十九頁，2022年，8月28日2023/1/1839§6.5譯碼方法和糾錯能力對引理2和引理3的解釋設信道真正的輸入碼字為u，信道的輸出向量為y，真正的差錯向量為e=y-u。采用實用糾錯譯碼算法：接收y→計算伴隨式s=yHT→以s為地址查找e(s)→計算c=y-e(s)→認為陪集首e(s)就是差錯向量；認為c就是輸入碼字。引理2告訴我們，如果w(e)≤[(dmin-1)/2]

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

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

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

，則e未必是s=eHT的陪集首。第四十頁，共六十九頁，2022年，8月28日2023/1/1840§6.5譯碼方法和糾錯能力定理

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

=[(dmin-1)/2]。推論記真正的差錯向量為e。事件“總是能夠正確譯碼”定義為“w(e)≤[(dmin-1)/2]”。則“總是能夠正確譯碼”的概率為第四十一頁，共六十九頁，2022年，8月28日2023/1/1841§6.5譯碼方法和糾錯能力定理說明，dmin是線性分組碼糾錯能力的一個指標。dmin越大，[(dmin-1)/2]就越大，“總是能夠正確譯碼”的概率也越大。當N比L大得越多，碼字在所有N維向量中占的比例越小，越容易使得dmin大。問題是，當N和L都確定時，如何設計碼使得dmin大。糾正一種誤解：dmin越大，“總是能夠正確譯碼”的概率越大。決不能說：dmin越大，正確譯碼的概率越大。

（??P185,式子）第四十二頁，共六十九頁，2022年，8月28日2023/1/1842§6.5譯碼方法和糾錯能力例

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

顯然是系統(tǒng)碼。第四十三頁，共六十九頁，2022年，8月28日2023/1/1843§6.5譯碼方法和糾錯能力信息向量→碼字000→000000100→011100010→101010001→110001110→110110101→101101011→011011111→000111第四十四頁，共六十九頁，2022年，8月28日2023/1/1844§6.5譯碼方法和糾錯能力伴隨式s→對應的所有“可能的差錯向量”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→100100第四十五頁，共六十九頁，2022年，8月28日2023/1/1845§6.5譯碼方法和糾錯能力dmin=3；[(dmin-1)/2]=1。當真正的差錯向量的Hamming重量不超過1時，總是能夠正確譯碼；當真正的差錯向量的Hamming重量超過1時，未必總是能夠正確譯碼。總是能夠正確譯碼的概率為(1-p)6+6(1-p)5p。正確譯碼的概率為(1-p)6+6(1-p)5p+(1-p)4p2。（p185,式）若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。第四十六頁，共六十九頁，2022年，8月28日2023/1/1846§6.5譯碼方法和糾錯能力設信道的輸出向量為y=(111111)。計算伴隨式s=yHT=(111)。以s為地址查找e(s)=(100100)。計算c=y-e(s)=(111111)-(100100)=(011011)。信息向量為(011)。第四十七頁，共六十九頁，2022年，8月28日2023/1/1847§6.4、§6.6、§6.7、§6.8一些特殊的線性分組碼二元Hamming碼N=2m-1，L=2m-1-m，即二元(2m-1，2m-1-m)線性分組碼。其校驗矩陣是如下的m×(2m-1)階矩陣H：H的(2m-1)列恰好是(2m-1)個非全0的m維向量。因此：校驗矩陣H的任意一列不是全0的m維向量；校驗矩陣H的任意兩列互不相同；校驗矩陣H的某三列的和為全0的m維向量。換句話說，重量為1、重量為2的2m-1維向量都不是碼字，而某些重量為3的2m-1維向量是碼字。再換句話說，Hamming碼的dmin=3。再換句話說，當差錯向量的重量不超過1時，肯定能夠正確譯碼。編碼效率為R=(2m-1-m)/(2m-1)

。（編碼效率大）第四十八頁，共六十九頁，2022年，8月28日2023/1/1848§6.4、§6.6、§6.7、§6.8一些特殊的線性分組碼定義

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

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

xN-L。取以下的L×N矩陣G作為二元(N,L)線性分組碼C的生成矩陣，則該碼一定就是一個二元循環(huán)碼。（主教材中有證明）第五十三頁，共六十九頁，2022年，8月28日2023/1/1853§6.4、§6.6、§6.7、§6.8一些特殊的線性分組碼例(p190)~例(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一定就是一個二元循環(huán)碼，生成矩陣為第五十四頁，共六十九頁，2022年，8月28日2023/1/1854§6.4、§6.6、§6.7、§6.8一些特殊的線性分組碼如此產(chǎn)生的二元循環(huán)碼的譯碼設接收向量為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

。則此時：除式y(tǒng)(x)=q(x)g(x)+s(x)也可以表示成y(x)≡s(x)(modg(x))。余式s(x)的次數(shù)一定不超過N-L-1。N-L維向量s=(s0,s1,s2,…,sN-L-1)就是接收向量y的伴隨式。（因而不需要校驗矩陣）第五十五頁，共六十九頁，2022年，8月28日2023/1/1855習題課6.1設有4個消息al，a2，a3

和a4被編成為長為5的二元碼的00000，01101，10111，l1010。(a)試給出碼的一致校驗關系。(b)若通過轉移概率為p<1/2的BSC傳送，試給出最佳譯碼表及相應的譯碼錯誤概率表示式。(c)若碼通過BEC信道傳送，試問可恢復幾個刪除?其最佳譯碼表應如何配置？(d)一般，最小距離為dmin的線性碼，可恢復幾個刪除?第五十六頁，共六十九頁，2022年，8月28日2023/1/1856習題課(a)首先需要驗證該碼是線性碼：01101‘+’10111=l1010。其次需要給出該碼的生成矩陣和校驗矩陣：最后該碼的一致校驗關系為：對任意碼字(x0x1x2x3x4)，恒有x0+x1+x2=0，x0+x3=0，x0+x1+x4=0。第五十七頁，共六十九頁，2022年，8月28日2023/1/1857習題課(b)通過轉移概率為p<1/2的BSC傳送。如果直接按照“最小距離準則”來求最佳譯碼表，則最佳譯碼表為接收向量譯為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。

l1010第五十八頁，共六十九頁，2022年，8月28日2023/1/1858習題課求“譯碼錯誤概率表示式”，可以有多種含義。本題應該理解為以下的含義，而不應該理解為別的含義：第五十九頁，共六十九頁，2022年，8月28日2023/1/1859求最佳譯碼表，當然也可以采用標準方法，先求可能的差錯向量、伴隨式、陪集首的關系：可能的差錯向量伴隨式陪集首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。11010001第六十頁，共六十九頁，2022年，8月28日2023/1/1860習題課根據(jù)公式：“接收向量”-“陪集首”=“所要譯為的碼字”