差错控制编码课件

差錯控制編碼10.1引言一.有3種方法（1）檢錯重發（ARQ）1.將資訊碼分組，為每組資訊碼附加若干監督碼的編碼，稱為分組碼。（系統碼）碼組=資訊位+監督位（2）前向糾錯（FEC）（3）混合糾錯（HEC）二.基本概念2.分組碼的表示：符號（n，k）n——碼組的總位數k——碼組中資訊碼元的數目r=n-k——監督碼元的數目3.編碼效率R越大，資訊位比重大，有效性越高。4.分類：p275

（1）根據已編碼組中資訊碼元與監督碼元之間的函數關係，可分為線性碼和非線性碼。若資訊碼元與監督碼元之間的關係呈線性，即滿足一組線性方程式，則稱為線性碼。（2）根據資訊碼元與監督碼元之間的約束方式不同，可分為分組碼和卷積碼。分組碼的監督碼元僅與本碼組的資訊碼元有關，卷積碼的監督碼元不僅與本碼組的資訊碼元有關，而且與前面碼組的資訊碼元有約束關係。（3）根據編碼後資訊碼元是否保持原來的形式，可分為系統碼和非系統碼。在系統碼中，編碼後的資訊碼元保持原樣，而非系統碼中的資訊碼元則改變了原來的信號形式。（4）根據編碼的不同功能，可分為檢錯碼和糾錯碼。（5）根據糾、檢錯誤類型的不同，可分為糾、檢隨機性錯誤的碼和糾、檢突發性錯誤的碼。（6）根據碼元取值的不同、可分為二進位碼和多進制碼。本章只介紹二進位糾、檢錯編碼。誤碼率一定時，非編碼系統需要的輸入信噪比與采用了糾錯編碼系統所需的輸入信噪比之間的差值。（用dB表示）（1）碼組中“1”的個數稱為碼組的重量。（w）例：10011w=301101d=45.編碼增益6.碼重、碼距（2）兩個等長碼組之間的對應位不同的位數，稱為碼距。又稱為漢明距離。（d）（3）某種編碼中各個碼組之間的距離的最小值稱為最小碼距（）7.e—檢錯能力t—糾錯能力（1）時能檢出e個或e個以下錯碼。（2）（3）

時能糾正t個或t個以下錯碼。時能檢出t個或e個以下錯碼。例12-1已知8個碼組為：（O00000），（001110），（010101），（011011），（100011），（1O1101），（110110），（111000），（1）求以上碼組的最小碼距；（2）若此8個碼組用於檢錯，可檢出幾位錯？（3）若用於糾錯碼，能糾幾位？（4）若同時用於糾錯和檢錯，糾錯、檢錯性能如何？

（1）（2）（3）（4）例12-2已知兩碼組（0000）和（1111），若該碼組用於檢錯，能檢出幾位錯碼？若用於糾錯，能糾正幾位錯碼？若同時用於糾錯和檢錯，問各能糾、檢幾位錯碼？

（1）（2）（3）一.奇偶監督碼在資訊為後加一位校驗位10.2常用的簡單編碼

奇監督碼偶監督碼特點：只能檢測出奇數個錯碼，不能檢測出偶數二.二維奇偶監督碼行監督位列監督位特點：（1）能檢測出每一行（列）中的奇數個或偶數個錯碼，但不能檢測出行列同時成偶數個出現的錯碼。（2）能檢測突發性錯誤（成串錯碼）。（3）能糾正錯碼。

三.恒比碼：p277碼組中均含有相同數目的“1”或“0”特點：能檢測出組碼中奇數個及部分偶數個碼元得錯誤。（“1”錯成“0”和“0”錯成“1”不能檢測。

四.正反碼例：資訊位：11001監督位：11001

資訊位：10001監督位：011101.編碼規則：（1）當資訊位中有奇數個1時，監督位是資訊位的簡單重複。（2）當資訊位中有偶數個1時，監督位是資訊位的反碼。例：1100111001=000001000101110=111112.解碼方法（1）將碼組中的資訊碼與監督碼進行模2加得合成碼組。（2）若資訊碼中有奇數個1，則合成碼組即為檢驗碼組。若資訊碼中有偶數個1，則合成碼組的反碼即為檢驗碼組。（3）觀察檢驗碼組中1的個數，按p278進行檢錯和糾錯。10.3線性分組碼一.以（7，4）分組碼為例碼字：A=（）其中資訊位：監督位：若分組碼可用下列線性方程組表示：（“+”為模2加）則：該分組碼為（7，4）線性分組碼（共有16個碼字）性質：（1）封閉性：任意2個許用碼組之和（模2加）仍為一個許用碼組。（2）有零元：（3）有負元：（4）結合律成立：（任一碼字即為本身的負元）二.監督矩陣H將上例中的式子改寫為：用矩陣表示為：並記為：H陣可表示為：（階）（階單位陣）矩陣H稱為（7，4）線性分組碼得監督矩陣。上式也稱為典型監督矩陣。若不是典型監督矩陣要用初等變換化成典型矩陣。三.生成矩陣G

若資訊碼元已知，通過監督矩陣可以求出監督碼元。用矩陣表示：或

將上式擴展可以由已知資訊碼元求得整個碼組。令：G稱為生成矩陣典型監督矩陣和典型生成矩陣存在以下關係式：例：（7，4）全部碼字為：四.伴隨式（校正子）S

設發送碼字為，接收碼字為，由於干擾，雜訊可能引入誤差，使接收碼組與發送碼組不同，因此有，其中是傳輸中產生的錯誤行矩陣。對於二進位碼元有:E矩陣中哪一位碼元為1就表示接收碼字中對應位有錯。E稱為錯誤圖樣。模2

在接收端用H來檢測接收B中的錯碼。令：－伴隨式或校正子：如果B與A相同，則：否則：又

表示校正子S僅與通道的錯誤圖樣E有關，而與發送的碼字A無關。五.如何利用S完成糾錯對（7，4）線性分組碼設B中最高位有錯，錯誤圖樣它的轉置恰好是典型H陣的第一列。同理可求出：若次高位有錯，即恰好是H的第二列。

因此，在接收碼組中只錯一位碼元情況下，計算出的校正子S總是和典型監督矩陣中的某一行相同。例：與第三列相同正確碼組為：六.漢明碼

漢明碼是一種可以糾正單個隨機錯誤的線性分組碼。它的最小碼距，監督元位數，碼長，資訊元位數，編碼效率當r很大時，，因此是一種高效碼。

上例中的（7，4）線性分組碼就是漢明碼，並且任意調換H矩陣中各列的結果不會影響糾，檢錯能力。10.4迴圈碼一.概念1.迴圈碼：線性分組碼（1）封閉性（2）迴圈性：迴圈碼中任一許用碼組經過迴圈移位之後，所得到的碼組仍為一許用碼組。

2.碼多項式迴圈碼的一許用碼組可表示為：其中：x為碼元位置標記，不考慮其取值。碼元只取“1”或“0”。

例:(7，3）迴圈碼中第二個碼組

如何實現移位：乘一個x相當於碼左移一位。3.按模運算若（的次數小於）則：稱為按模運算後的餘式。例：4.規律（1）迴圈碼中，將許用碼組左移一位得到的碼字記為：。其碼多項式為：可以證明：（2）根據迴圈碼的定義，均為許用碼字。因此下列結論：若是許用碼字，則在按模運算下，也是許用碼字。即：若則也是許用碼字。例:(7，3）迴圈碼則：那麼其碼字為。二.生成多項式與生成矩陣G1.(n，k)迴圈碼碼組集合中（全“0”除外）最高階數最小的多項式[（n-k）階]稱為生成多項式，記為g(x)。2.集合中其他碼多項式都是運算下的餘式。即可以由生成多項式g(x)產生迴圈碼的全部碼字。3.生成矩陣G迴圈碼的生成矩陣多項式可以寫成以（7，3）迴圈碼為例經線性變換，將G整理成典型生成矩陣。整個碼組可表示為：任意一個碼多項式都能被g(x)整除。三.監督多項式、監督矩陣1.對於(n，k)迴圈碼，可分解成g(x)和其他因式的乘積。記為：稱h(x)為監督多項式，其矩陣形式為：以（7，3）迴圈碼為例2.對於（7，3）迴圈碼，g(x)的最高次為4所以，有兩種方案第一種方案：碼字：第二種方案：碼字：例:已知(7，4）迴圈碼的生成多項式為（1）求典型生成矩陣和典型監督矩陣；（2）輸入資訊碼為11001011，求編碼後的系統碼；（3）全部碼組；（4）糾、檢錯能力

解：四.編碼電路1.對於(n，k)迴圈碼中，可用多項式表示為：其中：m(x)為不大於（k-1）次的多項式，代表資訊碼元。

r(x)為不大於(r-1)次的多項式，代表監督碼元。

或：該式提供了迴圈碼編碼的數學依據。2.步驟：（1）資訊多項式m(x)左移n-k位。（相當於）（2）求其模g(x)的餘式r(x)（3）餘式的係數作監督碼元，附加在資訊碼元之後形成迴圈碼。例:已知(7，3）迴圈碼的生成多項式為求資訊位為101時的碼字。

3.編碼電路門1門2

首先，四級移位寄存器清零，三位資訊碼元到來時，門1斷開，門2接通，直接輸出資訊元。第3次移位脈衝來時將除法電路運算所得的餘數存入四級移位寄存器，第4~7次移位時，門2斷開，門1接通，輸出監督碼元（即餘數）。當一個碼字輸出完畢後就將移位寄存器清零，等待下一組資訊碼元輸入後重新編碼。4.解碼（1）只檢錯設發送碼組為A，接收碼組為B。B不出錯時，有B(x)=A(x)則：