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