線性碼及其應(yīng)用.ppt

定義2碼字X x1x2 xn的漢明重量是碼字中非零碼元的位數(shù) 用W X 表示 例如 W 1001 2 W 11010 3 由定義1和定義2知D X Y W X Y 定義3一組碼字C包括若干碼字C1 C2 Cn 所有這些碼字相互間碼距的最小的數(shù)值 稱為該碼組的最小碼距d 簡稱碼距d d minD Ci Cj minW Ci Cj i j 1 2 N i j 例如C 0111100 1011011 1101001 d 3 說明 為盡量避免碼字受到干擾而出錯 總是希望碼字間有盡可能大的距離 最小碼距代表了一個碼組中最不利的情況 從安全出發(fā) 往往選用最小碼距來分析碼的檢錯糾錯能力 第二節(jié)檢錯能力與糾錯能力 1 碼距為1時 能保證碼字的唯一性 但不能檢錯和糾錯 2 碼距為2時 能檢查出一位錯誤 但無法糾錯 3 碼距為3時 能檢查出一位或兩位錯誤 并且還可糾正一位錯誤 例 設(shè)碼長為3 取000 111作為碼字 其余為禁用碼字 如接收端收到001 它是禁用碼字 知道出錯 由于001與000相差一個碼元 與111相差兩個碼元 根據(jù)最大似然譯碼原則將001譯為000 最大似然譯碼原則 當(dāng)Ci為若干個發(fā)送碼字中的一個 R為接收碼字 若條件概率P R Ci 為最大 則認(rèn)為碼字Ci就是發(fā)送碼字 結(jié)論 一 要檢出碼字中任意e個碼元錯誤 必須使最小碼距d滿足d e 1 二 要糾正碼字中任意t個碼元錯誤 必須使最小碼距d滿足d 2t 1 三 要糾正碼字中任意t個碼元錯誤 并同時發(fā)現(xiàn)e個錯誤 e t 則最小碼距d滿足d t e 1 當(dāng)碼距d 2t 1時 碼長為n的一個許用碼字中可糾正的錯誤類型總數(shù)為 許用碼字?jǐn)?shù)Q 2 n 第三節(jié)寄偶監(jiān)督碼 寄偶監(jiān)督碼是最簡單的一種檢錯碼 是目前計算機系統(tǒng)用得最多的一種差錯控制碼 寄偶監(jiān)督碼的編碼方式 是在n 1位信息元 Cn 1 Cn 2 C1 后面附加1位監(jiān)督元C0 使得碼字中 1 的數(shù)目保持為奇數(shù)或偶數(shù) 奇數(shù)監(jiān)督 對應(yīng)的監(jiān)督方程為 Cn 1 Cn 2 C1 C0 1 偶數(shù)監(jiān)督 對應(yīng)的監(jiān)督方程為 Cn 1 Cn 2 C1 C0 0 P169表5 1列出了用七位ASCII碼表示的十個數(shù)字符號的寄偶校驗位 判別方法 接收端收到編好的寄偶監(jiān)督碼后 用與發(fā)送端相同的規(guī)則檢查 1 的個數(shù)是否仍保持奇數(shù)或偶數(shù) 從而確定傳輸過程中是否有錯誤 特點 能發(fā)現(xiàn)一位碼元或所有奇數(shù)位碼元出錯的情況 但不能糾正任何錯誤以及發(fā)現(xiàn)偶數(shù)位碼元錯誤 簡單寄偶碼的效率高 n 1 n 寄偶監(jiān)督碼的實現(xiàn) 1 硬件法 采用模二相加的異或電路 C1 C2 C3 C4 C5 C6 C7 C0 C0 2 軟件法 見P170圖5 6的流程圖 為了改進差錯控制性能 引入二維寄偶監(jiān)督碼 水平 垂直寄偶監(jiān)督碼 方陣碼 縱橫寄偶監(jiān)督碼 就是在水平方向進行寄偶監(jiān)督的同時 再按垂直方向進行一次寄偶監(jiān)督 如P171圖5 7 圖5 8 二維水平 斜向寄偶監(jiān)督碼 二維寄偶監(jiān)督碼特點 能檢出每一行或每一列的兩位或偶數(shù)位錯誤 可以用水平 垂直兩個方向上的監(jiān)督碼元 來確定單個錯誤碼元的位置 從而進行糾正 但它無法檢出四個錯誤碼元構(gòu)成矩形 或平行四邊形 四個頂點的錯誤圖樣 也無法檢出雙向成偶的錯誤圖樣 第五節(jié)監(jiān)督矩陣與生成矩陣 設(shè)有待編碼的消息序列為M m1m2 mk 對應(yīng)的信息元序列 X1X2 Xk 為了進行差錯控制 我們按線性代數(shù)關(guān)系來添加監(jiān)督碼元序列 Xk 1Xk 2 Xn 則稱此碼長n 信息元數(shù)k的碼字序列 X1X2 Xk Xk 1Xk 2 Xn 為線性分組碼 記為 n k 如果其最小碼距為d 也可記為 n k d 或 n k d 其中監(jiān)督元數(shù)r n k 用線性的監(jiān)督方程組來表示 a11X1 a12X2 a1kXk Xk 1 a21X1 a22X2 a2kXk Xk 2 ar1X1 ar2X2 arkXk Xn 式中加號均表示模二加 或 a11X1 a12X2 a1kXk Xk 1 0 0 0 a21X1 a22X2 a2kXk 0 Xk 2 0 0 ar1X1 ar2X2 arkXk 0 0 Xn 0 若用矩陣表示 則 a11a12 a1k10 0 a21a22 a2k01 0 ar1ar2 ark00 1 X1X2 XkXk 1 Xk 0 簡寫為HX T 0 T H 監(jiān)督矩陣 X T 行矩陣X X1X2 Xn 的轉(zhuǎn)置矩陣 例5 1一個 7 3 碼的信息元 X1X2X3 和監(jiān)督元 X4X5X6X7 間的監(jiān)督方程組為 X1 X3 X4 0X1 X2 X3 X5 0X1 X2 X6 0X2 X3 X7 0 求出對應(yīng)信息元的監(jiān)督元 解 列出各種信息元組合 依據(jù)監(jiān)督方程組求出對應(yīng)監(jiān)督元如下表所示 信息元 監(jiān)督元 編成碼字 000001010011100101110111 00001101011110101110001110010100 00000000011101010011101110101001110101001111010011110100 還可以寫出監(jiān)督矩陣形式 HX 011000 1110100 1100010 0110001 T X1X2X3X4X5X6X7 0000 說明 1 編碼中 往往在多種可能的碼字排列中 選取少量的許用碼字 2 任意兩個碼字逐位模二加 可以得到另一個碼字 這種特性叫做封閉性 它是線性碼的重要特點 3 由封閉性知 兩個碼字的碼距 就是另一個碼字的碼重 所以 該組碼字的最小碼距就等于碼字中碼的最小重量 4 監(jiān)督矩陣H A Ir A為rxk階矩陣 Ir為r階單位陣 r n k H起監(jiān)督是否是碼字的作用 5 在線性碼組中 如果有一個碼重為W的碼字 則在H中必有與之相應(yīng)的W列相加等于0 固稱此W列線性相關(guān) 如果要求碼組的最小碼距為d 即要求碼字的最小碼重為d 則H中至少有d列相加之和為0 任意小于或等于d 1列線性無關(guān) 例如 例題中0011101是碼字 碼重為4 它應(yīng)該滿足監(jiān)督方程組 即 HX T 011000 1110100 1100010 0110001 0011101 1101 1000 0100 0001 0000 下面討論一下監(jiān)督矩陣H與生成矩陣G的關(guān)系 HX T A Ir X1X2 Xk Xk 1Xk 2 Xn 0 T 或 A X1X2 Xk Ir Xk 1Xk 2 Xk 0 T 則 Xk 1Xk 2 Xn A X1X2 Xk A mk m1m2 令 X1X2 Xk Ik mk m1m2 X1X2 Xk Ik A m1m2 mk 兩邊取轉(zhuǎn)置得 X MG X M為行矩陣的形式 G Ik A T 稱為生成矩陣 利用G可由M直接生成碼X 以前面的例題為例 知道A 可求出 A T 11001111101 Ik 00010001 設(shè)有信息元組m1m2m3 101則由X MG求出對應(yīng)碼字 1010011 G 100111001001110011101 可以觀察G的三行分別是例5 1求出的第5 3 2個碼字 這三個碼字組成的G 能使求出的碼字信息元在前 監(jiān)督元在后 即構(gòu)成的是系統(tǒng)碼 如選其他三個碼字組合成G 得出的碼字信息元與監(jiān)督元將是交錯排列 即非系統(tǒng)碼 由H A In k G Ik A T 則HG A In k A A 0 T Ik A 由這個等式可知G的每一行都是一個碼字 生成矩陣G和監(jiān)督矩陣H的關(guān)系 一個 n k 碼字的監(jiān)督矩陣H 正好是另一個 n n k n r 碼字的生成矩陣G 反之亦然 我們稱 n n k 碼是 n k 碼的對偶碼 可以用下面這個圖反映G和H的關(guān)系 注意理解 1001110 0100110 0011101 1011000 1110100 1100010 0010001 k r k r 此處有H 7 4 G 7 3 或H 7 3 G 7 4 如H 7 4 G 7 3 1001110 0100110 0011101 可以通過矩陣變換將上面矩陣化為典型監(jiān)督矩陣形式 第六節(jié)伴隨式與標(biāo)準(zhǔn)陣列 設(shè)發(fā)送的碼序列X X1X2 Xi Xn 接收的碼序列Y Y1Y2 Yi Yn 兩者的差別E Y X e1e2 ei en 稱為差錯序列或錯誤圖樣 用監(jiān)督矩陣來校驗接收到的碼字時 有 HY H X E HX HE T T T T HE T X是碼字 HX 0 T 令S HY HE T T T 則S EH T S稱為伴隨式 或校驗子 用它來檢查接收碼字中的錯誤 P182 184用例5 1的監(jiān)督矩陣為例討論了接收端可能遇到的幾種錯誤情況 可以看出一種碼的檢錯和糾錯能力受碼距的限制 超過此限度就會檢不出錯誤 或者造成誤判 注意S是一個r維的行矩陣 標(biāo)準(zhǔn)陣列問題 設(shè)有一個 n k 線性碼 它共有2個碼字C0 C1 C2 C 1 將它排列成下表所示形式 其中零碼矢C0放在第一列 它的下面放置各種錯誤圖樣 當(dāng)監(jiān)督元有n k個時 在C0下放有2 1個錯誤圖樣 在C0以后各碼字C1 C2 C2 1的同一列下 各放置一些元素 這些元素為該列碼字與相應(yīng)行的錯誤圖樣模二相加而成 我們稱同一行的這些元素為陪集 C0下面那些錯誤圖樣稱為陪集首 每一行對應(yīng)著唯一的一個伴隨式 如果將標(biāo)準(zhǔn)陣列預(yù)先存儲在接收端 則當(dāng)接收到某個錯誤碼字序列時 可以按照相應(yīng)的陪集位于哪一列 而依據(jù)最大似然法則將其譯成該列之首的那個碼字 k 2 k n k k 注意理解下表中錯誤圖樣與伴隨式的關(guān)系 C0C1C2 C2 1伴隨式S k E2E2 C1E2 C2 E2 C2 1 k E3E3 C1E3 C2 E3 C2 1 k E2E2 C1E2 C2 E2 C2 1 n k n k n k n k k 例5 2設(shè)碼字X X1X2X3X4X5 中X1 X2為監(jiān)督元 監(jiān)督矩陣為 H 100010111 列出標(biāo)準(zhǔn)陣列 判斷碼字10010是否是正確碼字 如果不是則它應(yīng)該譯為的正確碼字是多少 解 第一步根據(jù)H求出所有許用碼字C0 C1 C7 第二步確定錯誤圖樣的個數(shù)及形式 以及伴隨式S的形式 第三步列出標(biāo)準(zhǔn)陣列表 C0C1C2C3C4C5C6C7伴隨式0000000011001010011011001110101110011111S 001000011100001000101110111110110001101101 010000101101101011101000110010101001011110 100001001110101101100100101010011000111111 碼字10010顯然不是正確碼字 檢查它在陪集中位于C5這一列 因而按最大似然法則 將它改正錯誤后譯為C5 即11010 說明 采用這種方法譯碼 需要存儲2個陪集元素 n為碼長 如果利用陪集首所列的錯誤圖樣和伴隨式一一對應(yīng)的關(guān)系列表則只需存2個陪集首 因而可以節(jié)省許多存儲量 n n k 例如 發(fā)送碼字為11010 接收端錯誤地接收為11110 由公式 S HY T T 100010111 11110 01 查出陪集首為00100 固原發(fā)送碼字為11110 00100 11010 但是當(dāng) n k 碼的碼長n較大時即使只存儲2個陪集首及伴隨式 譯碼器所需內(nèi)存仍然相當(dāng)大 因此尋求好的譯碼方法和簡化譯碼設(shè)備是編碼理論和應(yīng)用中的重要課題 n k 第七節(jié)漢明碼 漢明碼是一類能糾正一位錯誤的線性碼 此類碼及其變型廣泛應(yīng)用于計算機存儲系統(tǒng)和數(shù)據(jù)通信中 對于任意正整數(shù)m 3 存在具有下列參數(shù)的漢明碼 碼長 n 2 1 m 信息位數(shù) k 2 m 1 m 監(jiān)督位數(shù) r n k m 最小碼距 dmin 3 糾錯位數(shù)tc 1 例5 3取m 3 則n 7 k 4 為 n k 7 4 漢明碼 如監(jiān)督方程組為 x2 x3 x4 x5x1 x3 x4 x6x1 x2 x4 x7 則監(jiān)督矩陣為 HX T 01111000110101101001 x1x2x7 0 T G 000011010010100101100001111 如果將監(jiān)督位設(shè)在x1 x2和x4 我們可以把題中給出的監(jiān)督方程組等價變換 得到下面方程組 x5 x6 x7 x4x3 x6 x7 x2x3 x5 x7 x1 H 0001111 0110011 1010101 則在輸出端求出譯碼用的伴隨式的碼元 S HY s1 x4 x5 x6 x7s2 x2 x3 x6 x7s3 x1 x3 x5 x7 根據(jù)公式S HE得出 7 4 漢明碼的一種校驗表 如下表示 T T T 錯位指示 伴隨式 s1 s2 s3 無錯 x1 x2 x3 x4 x5 x6 x7 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 由上表可見 輸出檢錯時很方便 因為由伴隨式的各碼元的值正好得出等于錯誤位置的二進制數(shù) 例如 當(dāng)信息元為x3x5x6x7 1100 可求出對應(yīng)的監(jiān)督元x1x2x4 011 最后的碼字x1x2x3x4x5x6x7 0111100假設(shè)傳輸過程中x7發(fā)生了錯誤 則接收端接收到錯誤碼字x1x2x3x4x5x6x7 0111101 求出伴隨式的碼元值s1s2s3 111 二進制數(shù)為7 由上表可以判斷錯誤的位置在第七位x7 通過將x7取反 進行糾錯得到正確碼字 注意 漢明碼是糾正一位錯的完備碼 如果將漢明碼的參數(shù)tc 1 n 2 1 Q 2 且k 2 m 1代入前面講的求最大許用碼字?jǐn)?shù)的公式 可以發(fā)現(xiàn)等式兩邊正好相等 所以稱漢明碼為完備碼 它表明碼的m位監(jiān)督元的2種表達形式 正好全部用來指示碼長n 2 1位的每一位上的錯誤 再加上完全無錯的一種情況 因此監(jiān)督元的利用是最充分的 m k m m m 第九節(jié)卷積碼的基本概念 卷積碼是伊萊亞斯 Elias 1955年提出來的 它的特點是 每一段時間內(nèi)所編出的幾個碼元不但與此段時間內(nèi)進入的K個信息元有關(guān) 而且也與前面幾段 如m段 時間內(nèi)的信息元有關(guān) 1 編碼電路 下圖是一個卷積碼的編碼電路 D D 輸入 輸出 1 2 j 1 j 2 設(shè)剛開始工作時 D1 D2的狀態(tài)為0 輸入信息元m1 1 求出相應(yīng)的監(jiān)督元P1 1 1 P1 2 1 則送入信道的第一段碼字為111 再輸入信息元m2 0 求出相應(yīng)的監(jiān)督元P2 1 1 P2 2 0 第二段碼字為010 如果每一段時間內(nèi)送入k個信息元 編碼電路送出n個碼元 稱n個碼元的一段為子碼 當(dāng)輸入信息元為mj mj 1 mj 2 時 送出的子碼序列為Cj Cj 1 Cj 2 mj Pj 1 Pj 2 mj 1 Pj 1 1 Pj 1 2 mj 2 Pj 2 1 Pj 2 2 可見第j段時間內(nèi)所編成的子碼Cj不僅與本段中輸入的信息元mj有關(guān) 而且也與前面兩個子碼Cj 1 Cj 2有關(guān) 對后面的兩個子碼Cj 1 Cj 2也有影響 這種子碼之間具有一環(huán)與一環(huán)相連的特點 因而卷積碼稱為連環(huán)碼 前面講的每一個子碼的監(jiān)督元 是本段時間內(nèi)輸入的信息組與前面m 2個子碼的信息組的線性模二和 也就是與 m 1 k個信息元發(fā)生線性關(guān)系 此處k 1 固卷積碼編出的也是線性碼 m稱為編碼存儲級數(shù) N m 1 稱為編碼約束度 編碼約束長度定義為 N m 1 n A n k m 卷積碼表示有k個輸入 n個輸出 存儲級數(shù)為m的線性碼 如果將移位寄存器和模二相加器間的關(guān)系以及信息元序列都用多項式形式來表示 則卷積編碼運算可以化為多項式的代數(shù)運算 例如書P198介紹了一個k 1 n 2的卷積碼編碼電路 2監(jiān)督矩陣 將前面的 3 1 2 卷積碼的兩個監(jiān)督方程改寫為矩陣形式 0 mj 2 0 Pj 2 1 0 Pj 2 2 1 mj 1 0 Pj 1 1 0 Pj 1 2 1 mj 1 Pj 1 0 Pj 2 0 1 mj 2 0 Pj 2 1 0 Pj 2 2 0 mj 1 0 Pj 1 1 0 Pj 1 2 1 mj 0 Pj 1 1 Pj 2 0 用矩陣表示 000100110100000101 mj 2Pj 2 1Pj 2 2mj 1Pj 1 1Pj 1 2mjPj 1Pj 2 0 000100110100000101 其中h 0 0 稱為基本監(jiān)督矩陣 且 01 10 11 0 0000 001 3第一截分組碼 由前面的編碼電路可以看出 每一個信息元影響的子碼數(shù)目是有限的 因此在譯某個碼元時 只需要在一個約束長度內(nèi)來考慮 假設(shè)編碼約束度N m 1