通信原理第十二章差錯控制編碼通信原理第十二章差錯控制編碼本章內容結構12.1引言12.2常用的簡單編碼12.3線性分組碼12.4循環碼12.5卷積碼本章內容結構12.1引言12.1引言一.差錯控制方法(3)混合糾錯（HEC）(1)檢錯重發（ARQ）(2)前向糾錯（FEC）12.1引言一.差錯控制方法(3)混合糾錯（HEC）(1.將信息碼分組，為每組信息碼附加若干監督碼的編碼，稱為分組碼。（系統碼）碼組=信息位+監督位二.基本概念1.將信息碼分組，為每組信息碼附加若干監督碼的編碼，稱2.分組碼的表示：符號（n，k）n——碼組的總位數k——碼組中信息碼元的數目r=n-k——監督碼元的數目3.編碼效率R越大，信息位比重大，有效性越高。2.分組碼的表示：符號（n，k）n——碼組的總位數k—4.分類：

（1）根據已編碼組中信息碼元與監督碼元之間的函數關系，可分為線性碼和非線性碼。若信息碼元與監督碼元之間的關系呈線性，即滿足一組線性方程式，則稱為線性碼。（2）根據信息碼元與監督碼元之間的約束方式不同，可分為分組碼和卷積碼。分組碼的監督碼元僅與本碼組的信息碼元有關，卷積碼的監督碼元不僅與本碼組的信息碼元有關，而且與前面碼組的信息碼元有約束關系。（3）根據編碼后信息碼元是否保持原來的形式，可分為系統碼和非系統碼。在系統碼中，編碼后的信息碼元保持原樣，而非系統碼中的信息碼元則改變了原來的信號形式。4.分類：（1）根據已編碼組中信息碼元與監督碼元之間的函（4）根據編碼的不同功能，可分為檢錯碼和糾錯碼。（5）根據糾、檢錯誤類型的不同，可分為糾、檢隨機性錯誤的碼和糾、檢突發性錯誤的碼。（6）根據碼元取值的不同、可分為二進制碼和多進制碼。本章只介紹二進制糾、檢錯編碼。（4）根據編碼的不同功能，可分為檢錯碼和糾錯碼。本章只介紹二誤碼率一定時，非編碼系統需要的輸入信噪比與采用了糾錯編碼系統所需的輸入信噪比之間的差值。（用dB表示）采用不同的編碼會得到不同的編碼增益，但編碼增益的提高要以增加系統帶寬或復雜度來換取。

（1）碼組中“1”的個數稱為碼組的重量。（w）5.編碼增益6.碼重、碼距誤碼率一定時，非編碼系統需要的輸入信（3）某種編碼中各個碼組之間的距離的最小值稱為最小碼距（）

例：10011w=301101（2）兩個等長碼組之間的對應位不同的位數，稱為碼距。又稱為漢明距離。（d）d=4例：100110110101010d1=4d0=3d2=3d3=3（3）某種編碼中各個碼組之間的距離的最小值稱為最小碼距（天津工業大學信息學院《通信原理》（1）時能檢出e個或e個以下錯碼。（2）（3）時能糾正t個或t個以下錯碼。時能檢出t個或e個以下錯碼。7.e—檢錯能力t—糾錯能力天津工業大學信息學院《通信原理》（1）時能檢例12-1已知8個碼組為：（O00000），（001110），（010101），（011011），（100011），（1O1101），（110110），（111000），（1）求以上碼組的最小碼距；（2）若此8個碼組用于檢錯，可檢出幾位錯？（3）若用于糾錯碼，能糾幾位？（4）若同時用于糾錯和檢錯，糾錯、檢錯性能如何？

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

（1）（2）（3）例12-2已知兩碼組（0000）和（1111），若該碼組用一.奇偶監督碼在信息位后加一位校驗位12.2常用的簡單編碼

奇監督碼偶監督碼特點：只能檢測出奇數個錯碼，不能檢測出偶數個錯碼一.奇偶監督碼在信息位后加一位校驗位12.2常用的簡單二.二維奇偶監督碼行監督位列監督位二.二維奇偶監督碼行監督位列監督位特點：（1）能檢測出每一行（列）中的奇數個或偶數個錯碼，但不能檢測出行列同時成偶數個出現的錯碼。（2）能檢測突發性錯誤（成串錯碼）。（3）能糾正錯碼。

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

不能檢測）。數字0123456789碼字01101010111100110110110100011110101111000111010011特點：（1）能檢測出每一行（列）中的奇數個或偶數個錯碼，但不

四.正反碼例：信息位：11001監督位：11001

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

若信息碼元已知，通過監督矩陣可以求出監督碼元。用矩陣表示：或三.生成矩陣G若信息碼元已知，通過監督矩陣

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

設發送碼字為，接收碼字為，由于干擾，噪聲可能引入誤差，使接收碼組與發送碼組不同，因此有，其中是傳輸中產生的錯誤行矩陣。對于二進制碼元有:E矩陣中哪一位碼元為1就表示接收碼字中對應位有錯。E稱為錯誤圖樣。模2四.伴隨式（校正子）S設發送碼字為

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

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

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

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

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

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

12.4循環碼一.概念1.循環碼：例:(7，3）循環碼中第二個碼組

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

解：例:已知(7，4）循環碼的生成多項式為解：四.編碼電路1.對于(n，k)循環碼中，可用多項式表示為：其中：m(x)為不大于（k-1）次的多項式，代表信息碼元。

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

或：四.編碼電路1.對于(n，k)循環碼中，可用多項式表該式提供了循環碼編碼的數學依據。2.步驟：（1）信息多項式m(x)左移n-k位。（相當于）（2）求其模g(x)的余式r(x)（3）余式的系數作監督碼元，附加在信息碼元之后形成循環碼。該式提供了循環碼編碼的數學依據。2.步驟：（1）信息多項式例:已知(7，3）循環碼的生成多項式為求信息位為101時的碼字。

例:已知(7，3）循環碼的生成多項式為3.編碼電路門1門2

首先，四級移位寄存器清零，三位信息碼元到來時，門1斷開，門2接通，直接輸出信息元。第3次移位脈沖來時將除法電路運算所得的余數存入四級移位寄存器，第4~7次移位時，門2斷開，門1接通，輸出監督碼元（即余數）。當一個碼字輸出完畢后就將移位寄存器清零，等待下一組信息碼元輸入后重新編碼。3.4.解碼（1）只檢錯設發送碼組為A，接收碼組為B。B不出錯時，有B(x)=A(x)則：能整除。余數不為0時，B有錯。4.解碼（1）只檢錯設發送碼組為A，接收碼組為B。B不出錯框圖：（2）糾錯用B(x)除以g(x)得到余式按余式用查表的方法或通過某種運算得到E(x)。框圖：（2）糾錯用B(x)除以g(x)得到余式例：12-6令為(7，4)循環碼的生成多項式。(1)求出該循環碼的生成矩陣和監督矩陣；(2)若兩個信息碼組分別為(1001)和(0110),求出這兩個循環碼組；(3)畫出其編碼器原理框圖。解：（1）例：12-6令為(7，4)循環碼（2）（3）（2）（3）（4）（4）通信原理第十二章差錯控制編碼通信原理第十二章差錯控制編碼本章內容結構12.1引言12.2常用的簡單編碼12.3線性分組碼12.4循環碼12.5卷積碼本章內容結構12.1引言12.1引言一.差錯控制方法(3)混合糾錯（HEC）(1)檢錯重發（ARQ）(2)前向糾錯（FEC）12.1引言一.差錯控制方法(3)混合糾錯（HEC）(1.將信息碼分組，為每組信息碼附加若干監督碼的編碼，稱為分組碼。（系統碼）碼組=信息位+監督位二.基本概念1.將信息碼分組，為每組信息碼附加若干監督碼的編碼，稱2.分組碼的表示：符號（n，k）n——碼組的總位數k——碼組中信息碼元的數目r=n-k——監督碼元的數目3.編碼效率R越大，信息位比重大，有效性越高。2.分組碼的表示：符號（n，k）n——碼組的總位數k—4.分類：

（1）根據已編碼組中信息碼元與監督碼元之間的函數關系，可分為線性碼和非線性碼。若信息碼元與監督碼元之間的關系呈線性，即滿足一組線性方程式，則稱為線性碼。（2）根據信息碼元與監督碼元之間的約束方式不同，可分為分組碼和卷積碼。分組碼的監督碼元僅與本碼組的信息碼元有關，卷積碼的監督碼元不僅與本碼組的信息碼元有關，而且與前面碼組的信息碼元有約束關系。（3）根據編碼后信息碼元是否保持原來的形式，可分為系統碼和非系統碼。在系統碼中，編碼后的信息碼元保持原樣，而非系統碼中的信息碼元則改變了原來的信號形式。4.分類：（1）根據已編碼組中信息碼元與監督碼元之間的函（4）根據編碼的不同功能，可分為檢錯碼和糾錯碼。（5）根據糾、檢錯誤類型的不同，可分為糾、檢隨機性錯誤的碼和糾、檢突發性錯誤的碼。（6）根據碼元取值的不同、可分為二進制碼和多進制碼。本章只介紹二進制糾、檢錯編碼。（4）根據編碼的不同功能，可分為檢錯碼和糾錯碼。本章只介紹二誤碼率一定時，非編碼系統需要的輸入信噪比與采用了糾錯編碼系統所需的輸入信噪比之間的差值。（用dB表示）采用不同的編碼會得到不同的編碼增益，但編碼增益的提高要以增加系統帶寬或復雜度來換取。

（1）碼組中“1”的個數稱為碼組的重量。（w）5.編碼增益6.碼重、碼距誤碼率一定時，非編碼系統需要的輸入信（3）某種編碼中各個碼組之間的距離的最小值稱為最小碼距（）

例：10011w=301101（2）兩個等長碼組之間的對應位不同的位數，稱為碼距。又稱為漢明距離。（d）d=4例：100110110101010d1=4d0=3d2=3d3=3（3）某種編碼中各個碼組之間的距離的最小值稱為最小碼距（天津工業大學信息學院《通信原理》（1）時能檢出e個或e個以下錯碼。（2）（3）時能糾正t個或t個以下錯碼。時能檢出t個或e個以下錯碼。7.e—檢錯能力t—糾錯能力天津工業大學信息學院《通信原理》（1）時能檢例12-1已知8個碼組為：（O00000），（001110），（010101），（011011），（100011），（1O1101），（110110），（111000），（1）求以上碼組的最小碼距；（2）若此8個碼組用于檢錯，可檢出幾位錯？（3）若用于糾錯碼，能糾幾位？（4）若同時用于糾錯和檢錯，糾錯、檢錯性能如何？

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

（1）（2）（3）例12-2已知兩碼組（0000）和（1111），若該碼組用一.奇偶監督碼在信息位后加一位校驗位12.2常用的簡單編碼

奇監督碼偶監督碼特點：只能檢測出奇數個錯碼，不能檢測出偶數個錯碼一.奇偶監督碼在信息位后加一位校驗位12.2常用的簡單二.二維奇偶監督碼行監督位列監督位二.二維奇偶監督碼行監督位列監督位特點：（1）能檢測出每一行（列）中的奇數個或偶數個錯碼，但不能檢測出行列同時成偶數個出現的錯碼。（2）能檢測突發性錯誤（成串錯碼）。（3）能糾正錯碼。

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

不能檢測）。數字0123456789碼字01101010111100110110110100011110101111000111010011特點：（1）能檢測出每一行（列）中的奇數個或偶數個錯碼，但不

四.正反碼例：信息位：11001監督位：11001

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

若信息碼元已知，通過監督矩陣可以求出監督碼元。用矩陣表示：或三.生成矩陣G若信息碼元已知，通過監督矩陣

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

設發送碼字為，接收碼字為，由于干擾，噪聲可能引入誤差，使接收碼組與發送碼組不同，因此有，其中是傳輸中產生的錯誤行矩陣。對于二進制碼元有:E矩陣中哪一位碼元為1就表示接收碼字中對應位有錯。E稱為錯誤圖樣。模2四.伴隨式（校正子）S設發送碼字為

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

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

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

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

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

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

12.4循環碼一.概念1.循環碼：例:(7，3）循環碼中第二個碼組

如何實現移位：乘一個x相當于碼左移一位。3.按模運算若（的次數小于）則：稱為按模運算后的余式。例:(7，3）循環碼中第二個碼組如何實現移位：乘一個x例：4.規律（1）循環碼中，將許用碼組左移一位得到的碼字記為：。其碼多項式為：可以證明：例：4.規律（1）循環碼中，將許用碼組（2）根據循環碼的定義，均為許用碼字。因此下列結論：若是許用碼字，則在按模運算下，也是許用碼字。即：若則也是許用碼字。例:(7，3）循環碼則：那么其碼字為。（2）根據循環碼的定義，二.生成多項式與生成矩陣G1.(n，k)循環碼碼組集合中（全“0”除外）最高階數最小的多項式[（n-k）階]稱為生成多項式，記為g(x)。2.集合中其它碼多項式都是運算下的余式。即可以由生成多項式g(x)產生循環碼的全部碼字。二.生成多項式與生成矩陣G1.(n，k)循環碼碼組集3.生成矩陣G循環碼的生成矩陣多項式可以寫成以（7，3）循環碼為例經線性變換，將G整理成典型生成矩陣。3.生成矩陣G循環碼的生成矩陣多項式可以寫成以（7，3）整個碼組可表示為：任意一個碼多項式都能被g(x)整除。整個碼組可表示為：任意一個碼多項式都能被g(x)整除。三.監督多項式、監