【正文】 H 線性碼的編碼與譯碼 ： 線性碼的譯碼 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 譯碼過程 (1)構(gòu)造 ［ n， k］ 線性碼 C的譯碼表：將 F2n中 2n個向量排成 2nk行 2k列的一個表 ， 表中有一條虛線將 2nk行分成上下兩部分；將 C中的向量排在第 1行 ， 將零碼字排在第 1行的第 1列 ， 并將 C中的 2k1個 非零碼字 任意排在第 1行的第 2列一直到第 2k列；將 F2n關(guān)于 C的 2nk1個不同陪集排成 2nk1行 ， 同一陪集中的 2k個向量排在同一行 ， 并將每個陪集的校驗子放在此行的最左邊作為標(biāo)記；若某陪集中 ， 有唯一的陪集頭 X， 則將此行排在譯碼表中虛線上方 ， 將陪集頭 X排在這一行的第 1列 ， 并將 排在碼字 c同一列；若某陪集中有多個陪集頭 ， 則將該行排在譯碼表中虛線下方 ， 且任取一個陪集頭 X排在該行的第一列 ， 也將 排在碼字 c的同一列 。 XcX ??XcX ?? 線性碼的編碼與譯碼 ： 線性碼的譯碼 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 譯碼過程 (2)根據(jù)譯碼表譯碼：當(dāng)收到字為 A時 ， 先計算 A的校驗子S(A)=AHT， 如果 S(A)=0， 則將 A譯為 A；否則檢查校驗子 S (A)是否在虛線上方 ， 若在虛線上方 ， 則將 A譯為第一行中與 A同列的碼字 c；如果校驗子 S (A)在虛線下方 ， 則無法譯碼 。 線性碼的編碼與譯碼 ： 線性碼的譯碼 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 例 設(shè) C是二元 ［ 6， 3］ 線性碼 ， 其校驗矩陣為 (1) 該列碼 C的譯碼表 (2) 設(shè)收到的字 A1=110110, A2=111111 ， 試譯 A1, A2 解： (1) 求生成矩陣 。 由 HXT=0得線性方程組 ?????????110100101010011001H1 4 5246356000x x xx x xx x x? ? ???? ? ??? ? ? ?? 線性碼的編碼與譯碼 ： 線性碼的譯碼 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 解得該方程組的基礎(chǔ)解系為 則 C的生成矩陣為 當(dāng) 取 中每一個向量時 ， 由 可得 C的所有碼字為 011001,101010,110100 321 ??? ????????????100110010101001011G),( 321 ??? 32F Gc ),( 321 ????),0 0 0 1 1 1()111(),0 1 1 1 1 0()110(),1 0 1 1 0 1()101(),1 1 0 1 0 0()100(),1 1 0 0 1 1()011(),1 0 1 0 1 0()010(),0 1 1 0 0 1()001(),0 0 0 0 0 0()000(76543210????????????????GcGcGcGcGcGcGcGc 線性碼的編碼與譯碼 ： 線性碼的譯碼 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 F26 空間的全部向量 000000 000001 …… 111110 111111 第 1步： 將碼 C中的向量 c排在譯碼表的第一行； 第 2步： 從 F26 中挑一個不包含在譯碼表中的漢明重量最小的向量 X，若該向量不惟一，取 10進(jìn)制值最小，計算其陪集 (X一定是該陪集的陪集頭 )、校驗子； 第 3步： 將該陪集放入譯碼表：若存在惟一陪集頭，放在虛線上方，且將陪集頭 X放在第 1列，第 c列存放 X+c；若陪集頭不惟一，任選一陪集頭 X放在第 1列，重新調(diào)整陪集順序，第 c列存放 X+c； 第 4步： 重復(fù)第 3步，直到 F26 中的全部向量放入譯碼表。 000000 011001 101010 110011 110100 101101 011110 000111 011 000001 011000 101011 110010 110101 101100 011111 000110 101 000010 011011 101000 110001 110110 101111 011100 000101 110 000100 011101 101110 110111 110000 101001 011010 000011 001 001000 010001 100010 111011 111100 100101 010110 001111 111 001100 010101 100110 111111 111000 100001 010010 001011 010 010000 001001 111010 100011 100100 111101 001110 010111 100 100000 111001 001010 010011 010100 001101 111110 101111 線性碼的編碼與譯碼 ： 線性碼的譯碼 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 (2) 譯碼 。 對收到的字 A1=110110 ， 計算 A1 的校驗子S(A1)=A1H=(101)。 ?類似地 ， A2=111111的校驗子為 111， 由于 (111)在虛線下方 ，故無法譯碼 000000 011001 101010 110011 110100 101101 011110 000111 011 000001 011000 101011 110010 110101 101100 011111 000110 101 000010 011011 101000 110001 110110 101111 011100 000101 110 000100 011101 101110 110111 110000 101001 011010 000011 001 001000 010001 100010 111011 111100 100101 010110 001111 111 001100 010101 100110 111111 111000 100001 010010 001011 010 010000 001001 111010 100011 100100 111101 001110 010111 100 100000 111001 001010 010011 010100 001101 111110 101111 線性碼的編碼與譯碼 ： 線性碼的譯碼 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 譯碼正確性證明 定理 上述譯碼方法符合極大似然譯碼原理 。 證明提示： (1)若收到的 A在虛線上方 ， 則存在 c0∈ C使得A=X+c0(X為惟一陪集頭 ) ， A應(yīng)譯為 c0 。 對于任意c(≠c0)∈ C， d(A,c)=d(X+c0,c)= d(X+c0c,0)=wt(X+c0c) wt(X)=d(X,0) =d(X+c0,c0)=d(A,c0) ? 符合極大似然譯碼原理 。 線性碼的編碼與譯碼 ： 線性碼的譯碼 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 (2)若收到的 A在虛線下方 ， 則至少存在兩個陪集頭 X， Y，其漢明重量 wt(X)=wt(Y)同時達(dá)到極小 ， 則存在 c0、 c1 ∈ C使得 A=X+c0(X為第 1列陪集頭 )， Y=X+c1， 此時 d(A,c0)=d(X+c0,c0)= d(X+c0c0,0)=d(X,0)=wt(X) =wt(Y)=wt(X+c1)=d(X+c1,0)=d(X+c0,c0c1)=d(A, c0c1) 因此 A與 c0和 c0c1兩個不同碼字的漢明距離都達(dá)到最小值 ，故無法譯出 。 線性碼的編碼與譯碼 ： 線性碼的譯碼 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 練習(xí) 設(shè) C是二元 ［ 4， 2］ 線性碼 ， 其生成矩陣為 : 求： (1) A1 = (01) , A2 = (11) 的編碼 。 (2)列出碼 C的譯碼表； (3)譯碼 A3 = (1010) , A4 = (0110) 1 0 0 10 1 1 1C??????? 線性碼的編碼與譯碼 ： 線性碼的譯碼