線性分組碼課件

第七章：線性分組碼§7.1

分組碼的概念§7.2線性分組碼§7.4循環(huán)碼§7.5卷積碼2022/11/251第七章：線性分組碼§7.1分組碼的概念2022/10/1§7.1分組碼的概念設信道是一個D元字母輸入/D元字母輸出的DMC信道，字母表為{0,1,…,D-1}。其信道轉移概率矩陣為D×D矩陣傳輸錯誤的概率為

p。信道容量為C=logD-H(p)-plog(D-1)。2022/11/252§7.1分組碼的概念設信道是一個D元字母輸入/D元字母§7.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/11/253§7.1分組碼的概念對隨機變量序列X1X2…進行的信道編§7.1分組碼的概念預備知識1：有限域設D是一個素數(shù)。于是字母表{0,1,…,D-1}中的所有字母關于(modD)加法、(modD)乘法構成了一個代數(shù)結構，稱作有限域，記作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)=ab+ac(modD)。注：GF(D)上的線性代數(shù)完全類似于實數(shù)域上的線性代數(shù)。2022/11/254§7.1分組碼的概念預備知識1：有限域2022/10/1§7.1分組碼的概念例：取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。方陣是否可逆？回答是肯定的，因為2022/11/255§7.1分組碼的概念例：取D=2，則GF(2)=({0,§7.1分組碼的概念該方陣的逆矩陣是什么？怎樣計算？做聯(lián)合可逆行變換：2022/11/256§7.1分組碼的概念該方陣的逆矩陣是什么？怎樣計算？做§7.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/11/257§7.1分組碼的概念例：取D=3，則GF(3)=({0,§7.1分組碼的概念可逆行變換2022/11/258§7.1分組碼的概念可逆行變換2022/10/118§7.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/11/259§7.1分組碼的概念例：域GF(D)上的一個L行N列的矩§7.1分組碼的概念預備知識2：有限域上的分組碼當D是素數(shù)時，分組碼可以充分利用有限域GF(D)的代數(shù)運算，使得編碼和譯碼更加簡便。2022/11/2510§7.1分組碼的概念預備知識2：有限域上的分組碼2022§7.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/11/2511§7.2線性分組碼定義取GF(D)上的一個L行N列的§7.2線性分組碼線性分組碼的代數(shù)結構命題1不同的信息向量對應不同的碼字。（因為變換u=xG是單射）命題2生成矩陣G的第1行是信息向量(1,0,0,…,0)的碼字；生成矩陣G的第2行是信息向量(0,1,0,…,0)的碼字；…生成矩陣G的第L行是信息向量(0,…,0,0,1)的碼字。2022/11/2512§7.2線性分組碼線性分組碼的代數(shù)結構2022/10/1§7.2線性分組碼命題3信息向量(x1,x2,…,xL)的碼字是：x1數(shù)乘G的第1行，加x2數(shù)乘G的第2行，加…，加xL數(shù)乘G的第L行。命題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/11/2513§7.2線性分組碼命題3信息向量(x1,x2,…§7.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/11/2514§7.2線性分組碼（命題3和命題4告訴我們，一個N維向量§7.2線性分組碼證明（要證明，第一個碼中任一個碼字也是第二個碼中的碼字；第二個碼中任一個碼字也是第一個碼中的碼字）設在第一個碼中，u是信息向量x的碼字：u=xG；則在第二個碼中，u是信息向量xM-1的碼字：u=xM-1MG=xM-1G’。設在第二個碼中，u是信息向量x的碼字：u=xG’；則在第一個碼中，u是信息向量xM的碼字：u=xMM-1G’=xMG。證完。

2022/11/2515§7.2線性分組碼證明（要證明，第一個碼中任一個碼字§7.2線性分組碼線性分組碼的特例：系統(tǒng)碼定義(p192)

D元(N,L)線性分組碼的生成矩陣為G=[PL×(N-L),IL]，其中IL是L階單位陣，PL×(N-L)是(N-L)×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/11/2516§7.2線性分組碼線性分組碼的特例：系統(tǒng)碼2022/10§7.2線性分組碼例6.1.2(p190)此二元(7,4)碼是線性分組碼，生成矩陣G是由信息向量(1000)、(0100)、(0010)、(0001)的碼字組成的4行2022/11/2517§7.2線性分組碼例6.1.2(p190)此二元(7§7.2線性分組碼例6.1.4(p192)此二元(5,3)線性分組碼的生成矩陣是2022/11/2518§7.2線性分組碼例6.1.4(p192)此二元(5§7.2線性分組碼線性分組碼的一致校驗矩陣定理(p193)

對于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ù)）定義6.1.7(p193)

由上述定理所描述的矩陣H稱為D元(N,L)線性分組碼的一致校驗矩陣。2022/11/2519§7.2線性分組碼線性分組碼的一致校驗矩陣2022/10§7.2線性分組碼有以下的結論。（1）一個線性分組碼有很多一致校驗矩陣。一個一致校驗矩陣H經(jīng)過可逆行變換變?yōu)镠’，

H’是同一個線性分組碼的另一個一致校驗矩陣。（2）一個N維向量u是一個碼字，當且僅當：uHT=全0的N-L維行向量。（3）設一個D元(N,L)線性分組碼的生成矩陣G，一致校驗矩陣H。則H是一個D元(N,N-L)線性分組碼的生成矩陣，G是此碼的一致校驗矩陣。稱這兩個碼互為對偶碼。2022/11/2520§7.2線性分組碼有以下的結論。2022/10/1120§7.2線性分組碼（怎樣由生成矩陣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/11/2521§7.2線性分組碼（怎樣由生成矩陣G計算出一致校驗矩陣H§7.2線性分組碼線性分組碼的糾錯譯碼準則定義6.1.2