【文章內(nèi)容簡介】 ； G稱為典型生成矩陣 ， 非典型生成矩陣經(jīng)過行列運算可以轉化為典型生成矩陣 。 第 4 信 道 編 線性分組碼的監(jiān)督方程與監(jiān)督矩陣 H 若將式 ()編碼方程中后四位監(jiān)督方程改寫， 可得 ??????????????????????????????????????????????000062151042103202121610105210210420203cccccccccccccccmmcccmmccccmmmcccmmc（ ） 第 4 信 道 編 將上述線性方程寫成如下矩陣形式 ???????????????????????????????????????????????????000010001100100011001011100011016543210ccccccc即 TT OHC ?或 OCH ?T() 第 4 信 道 編 其中 ， CT是碼空間 C的轉置 ， OT是 O=［ 0000］ 的轉置 ， HT是 H的轉置 。 ][1000010000100001101111100111rIPH ??????????????? （ ） 第 4 信 道 編 H稱為監(jiān)督矩陣 。 一旦給定 H， 信息碼元和監(jiān)督碼元之間的關系也就確定了 。 H為 r n 階矩陣 ， H矩陣每行之間是彼此線性無關的 。 P為 r k(4 3)階矩陣 ， Ir為 r r（ 4 4） 階單位矩陣 。 寫成 H=［ P Ir］ 形式的矩陣稱為典型監(jiān)督矩陣 。 由式 ()和() 可以看出 … ?QT110011110111PQ ????????????（ ） 其中 PT是 P的轉置。 第 4 信 道 編 根據(jù)以上推導可以看出 ， 監(jiān)督矩陣 H與生成矩陣 G之間存在一一對應的關系 ， 即 )()()()(TTPIQIGIQIPHkkrr????????（ ） （ ） 只要生成矩陣 G確定了 ， 監(jiān)督矩陣 H也就確定了；反之亦然 。顯然 ， 線性分組碼可以由生成矩陣 G或監(jiān)督矩陣 H完全確定 。 編碼時通常采用生成矩陣 G， 譯碼時通常采用監(jiān)督矩陣 H。 Q為 k r階矩陣； Ik為 k階單位矩陣； P為 r k 階矩陣， Ir為 r r 階單位矩陣 第 4 信 道 編 校正子 (伴隨式 )S與譯碼 假設發(fā)送碼組 C=(c6c5c4c3c2c1c0)， 在傳輸過程中可能發(fā)生誤碼 ， 接收碼組 B=(b6b5b4b3b2b1b0)， 則發(fā)送碼組與接收碼組之差定義為錯誤圖樣 E， 也稱為誤差矢量 ， 即 E=B－ C=B+C， 其中E=(e6e5e4e3e2e1e0)， 且 ??????iiiii cbcbe,0,1 i=0, 1, … , 6 （ ） 第 4 信 道 編 當 ei=0時 ， 表示該位接收碼元正確；當 ei =1時 ， 表示該位接收碼元有錯 。 令 S=BHT， 稱為伴隨式或校正子 。 當接收端譯碼時 ， 用監(jiān)督矩陣 H進行校驗 ， 計算校正子 S， 即 TTTTT )( EHEHHCHCEBHS ?????? 由于 CHT=0， 因此校正子 S只與錯誤圖樣 E有關 ， 與發(fā)送碼字 C無關 。 由此可見 ， 校正子 S與錯誤圖樣之間有確定的線性變換關系 。 接收端譯碼器的任務就是從校正子 S確定錯誤圖樣 E，然后從接收到的碼字中減去錯誤圖樣 。 圖 4 8 給出了譯碼過程框圖 。 （ ) 第 4 信 道 編 圖 48 譯碼過程框圖 BH T ＝ 0EC B 否 計算E輸出B ＋ E編碼m Gm是輸出 BC?第 4 信 道 編 1. 完備碼 對于 (n,k)線性分組碼 ， 它有 2k個碼字 ， 2r個校正子 ， 若該碼要糾正小于等于 t個隨機錯誤 ， 則必須滿足 ????????tiintnnnr CCCC02112 ?第 4 信 道 編 滿足上式條件的線性分組碼稱為漢明碼 。 式 ()指出了 n、 r與 t之間的關系 。 若式 ()的等式成立 ， 則該線性分組碼稱為完備碼 。 顯然 ， 漢明碼是一種完備碼 。 能滿足 ， 已發(fā)現(xiàn)的二進制完備碼有 t=1的漢明碼 ， t=3的 (23， 12)高萊 (Golay)碼 。 ???tiinr C02第 4 信 道 編 2. 漢明碼是一種常用的線性分組碼 ， 也是糾錯能力 t=1的完備碼 。 漢明碼的主要特點有： (1) 給定監(jiān)督碼元數(shù) r， 就能確定漢明碼的碼長為 n=2r－ 1， 信息碼元數(shù)為 k=2r－ r－ 1。 當 r=3， 4， 5， 6， …時 ， 分別有 (7， 4)， (15， 11)， (31， 26)， (63， 5)， …漢明碼 。 (2) 最小碼距 d0=3，可以糾正一位錯碼， 常用于 FEC系統(tǒng)。 (3) 編碼效率為 。 可以看出 ， 當 r(或 n)很大時 ， R趨于 1， 顯然 ， 漢明碼是一種高效 碼 。 1212?????rr rnkR第 4 信 道 編 3. 高萊碼 高萊碼是二進制 (23, 12)線性分組碼 ， 最小碼距 d0=7， 糾錯能力 t=3， 由于 22312=2048=1+C123+C223+C323， 故也是完備碼 。 在 (23, 12)碼上添加一位監(jiān)督位即得二進制線性 (24, 12)高萊碼 ，最小碼距 d0=8。 第 4 信 道 編 循 環(huán) 碼 循環(huán)碼的概念 它是線性分組碼中最重要的一個子類 。 目前 ， 實用差錯控制編碼中所使用的線性分組碼幾乎都是循環(huán)碼或循環(huán)碼的子類 。 循環(huán)碼除了具有 (n,k)線性分組碼的一般性質外 ， 還具有循環(huán)性 ， 即若將其任意一個碼字 (1,2,… ,c1,c0)的碼元向右或向左循環(huán)移一位 ， 所得的 (c0,1,2,… ,c1)或 (2,… ,c1,c0,1)仍然是碼字 ，表 44是一種 (7， 3)循環(huán)碼的全部碼字和碼多項式 。 第 4 信 道 編 表 44 （ 7， 3）循環(huán)碼 第 4 信 道 編 循環(huán)碼的生成多項式和生成矩陣 1. 循環(huán)碼的生成多項式 如果一種碼的所有碼多項式都是多項式 g(x)的倍式 ， 則稱g(x)為該碼的生成多項式 。 循環(huán)碼的碼多項式都是最低次碼多項式 g(x)的倍式 。 第 4 信 道 編 問題是如何確定任意一個 (n,k)循環(huán)碼的生成多項式 g(x)， 例如 ， (x7+1)可以分解為： x7+1=(x+1)(x3+x2+1)(x3+x+1)。 為了求出 (7， 3)循環(huán)碼的生成多項式 g(x)， 需要從中找到一個 r=n－ k=7－ 3=4次的因子 。 不難看出 ， 這樣的因子有兩個： ① (x+1)(x3+x2+1)=x4+x2+x+1； ② (x+1)(x3+x+1)=x4+x3+x2+1。 這兩個因子都可以作為生成多項式。 注意選用不同的生成多項式，所產(chǎn)生的循環(huán)碼的碼字不同。 第 4 信 道 編 (n,k) 循環(huán)碼的生成多項式滿足下面三條性質： (1) g(x)是一個（ n－ k）次多項式。 (2) g(x)的常數(shù)項不為 0。 (3) g(x)是 xn+1的一個因子。 第 4 信 道 編 2. 循環(huán)碼的生成矩陣 循環(huán)碼的生成矩陣 G常用多項式的形式來表示，即 ?????????????????????)()()()()(21xgxxgxgxxgxxGkk?（ ） 第 4 信 道 編 例如表 43所示的 (7， 3)循環(huán)碼 ， n=7,k=3, r=4， 其生成多項式 g(x)=x4+x3+x2+1， 代入式 ()可得 ???????????????????????????????1)()()()(23434524562xxxxxxxxxxxxgxxgxgxxG???????????100010101110111011001G即 第 4 信 道 編 顯然 ， G不是典型形式的生成矩陣 ， 但經(jīng)過簡單的變換就很容易化為典型形式的生成矩陣 ， 即 ???????????110011111101100010001G第 4 信 道 編 循環(huán)碼的編碼方法可歸納如下： (1) 用 xr乘以 m(x)。 該運算的作用是在信息碼元后附加上 r個“ 0”。 例如在 (7， 3)碼中信息碼組為 (110)， 它可以寫成m(x)=x2+x；由于 r=n－ k=7－ 3=4， 所以 xrm(x)=x4(x2+x)=x6+x5，它表示碼組 1100000， 即信息碼元后附加四個 “ 0”。 (2) 用 g(x)除以 xrm(x)， 得到商 Q(x)和余式 R(x)， 即 )()()()()(xgxRxQxgxmx r ??（ ） 循環(huán)碼的編碼方法 第 4 信 道 編 若選定 g(x)=x4+x2+x+1，則有 11)1(1)()(24222456?????????????xxxxxxxxxxxxgxmx r（ ） 即 Q(x)=x2+x+1， R(x)=x2+1。 上式等效于 1011 11011111011 11100 000 ?? （ ） 第 4 信 道 編 (3) 編碼器輸出的碼字為 C(x)=xrm(x)+R(x)=1100000+101=110010 () 第 4 信 道 編 (略 ） 1. 由于任一碼多項式 C(x)都應能被生成多項式 g(x)整除 ， 因此在接收端可以將接收碼組 B(x) 用生成多項式去除 ，即 。 當傳輸過程中沒有發(fā)生差錯時 ， 接收碼組與發(fā)送碼組相同 (C(x)=B(x))， 即接收碼組 B(x)必定能被 g(x)整除 ， 即 R(x)=0。 當傳輸過程中發(fā)生差錯時 ， C(x)≠B(x)， B(x)除以 g(x)時必定除不盡而有余項 ， 即 R(x)≠0。 因此 ， 可以用余項 R(x)是否為零來判定碼組中是否有差錯 。 )()()()()(xgxRxQxgxB ??第 4 信 道 編 BCH碼 BCH碼是一種非常重要的循環(huán)碼 ， 它在編碼理論研究和實際應用上占有重要地位 。 BCH碼的重要性體現(xiàn)在： ① 它有嚴密的代數(shù)結構 ， 是目