第十章差錯控制編碼1第十章差錯控制編碼1引言信源編碼，目的是實現模擬信號數字化信道編碼，目的是提高數字通信的可靠性差錯率是信噪比的函數信道編碼，差錯控制編碼，抗干擾編碼信道編碼過程：信息碼元序列＋監督碼元→編碼碼組信道譯碼過程：編碼碼組→檢錯或糾錯→信息碼元序列2引言信源編碼，目的是實現模擬信號數字化210.1差錯控制編碼的基本概念10.1.1?差錯控制方式10.1.2?差錯控制編碼分類10.1.3?幾種簡單的檢錯碼10.1.4?檢錯和糾錯的基本原理310.1差錯控制編碼的基本概念10.1.1?差錯控制方式310.1.1差錯控制方式常用的差錯控制方式有三種：前向糾錯（FEC:forwarderrorcorrection）發送能糾錯的碼，在譯碼時自動發現并糾正傳輸中的錯誤只需正向信道，實時性好編譯碼設備復雜，適合單向信道和一發多收系統檢錯重發（ARQ:automaticrepeatrequest）發送端發出能夠檢錯的碼，接收端檢驗，接收端發出反饋應答信號，發送端重新傳輸直到正確接收為止工作原理簡單，正向信道+反向信道，傳輸效率低混合糾錯（HEC:hybriderrorcorrection）前向糾錯方式和檢錯重發方式的結合與折衷外層先采用前向糾錯，當前向糾錯不能解決問題時，內層再采用檢錯重發。410.1.1差錯控制方式常用的差錯控制方式有三種：4

（a）FEC方式（b）ARQ方式（c）HEC方式5（a）5

檢錯重發的三種方式

停發等候重發返回重發選擇重發6檢停發等候重發返回重發選擇重發6

10.1.2差錯控制編碼分類在編碼前先把信息序列分為k位一組（稱為信息碼），然后附加m位監督碼，形成n=k+m位的碼組。1、按信息碼和附加監督碼間的檢驗關系線性碼：監督碼是信息碼的線性組合非線性碼：監督碼是信息碼的非線性組合2、按信息碼和監督碼間的約束方式分組碼：監督碼僅與本碼組的信息碼有關卷積碼：監督碼與之前的若干個信息碼組的碼元有約束關系710.1.2差錯控制編碼分類710.1.3幾種簡單的檢錯碼1.奇偶監督碼編碼方法把信息碼元先分組，在每組最后加一位監督碼元，使該碼組中1的數目為奇數或偶數奇數時稱為奇校驗碼偶數時稱為偶校驗碼偶校驗碼許用碼組為000，011，101，110禁用碼組為001，010，100，111奇校驗碼禁用碼組為000，011，101，110許用碼組為001，010，100，111810.1.3幾種簡單的檢錯碼1.奇偶監督碼8

一般情況下：設碼組長為n，且為：則偶校驗時有：奇校驗時有：譯碼方法(與編碼方法相對應)不滿足校驗關系，傳輸一定錯誤！奇偶校驗只能發現奇數個(單個)錯誤，不能檢測出偶數個錯誤。編碼方法簡單且實用性強，適用于檢測隨機零星錯碼滿足校驗關系，傳輸一定準確嗎？9一般情況下：92.二維奇偶監督碼將奇偶校驗碼的若干碼組排列成矩陣每一碼組寫成一行m個碼組m行m個監督位構成了一監督位列按列的方向增加第二維校驗位n個監督位構成了一監督位行檢錯能力檢出所有行和列中的奇數個差錯能檢出大多數偶數個差錯檢測突發錯碼也有一定的適應能力方陣碼，交織碼102.二維奇偶監督碼檢錯能力10

3.重復碼

重復碼是在每位信息碼元之后，再簡單重復多次的編碼；接收端譯碼時采用多數表決法。4.恒比碼

從固定碼長的碼組中選擇那些1和0的比例恒定的碼組作為許用碼組，如五單位保護電碼等。5.ISBN國際統一圖書編號2007年作了修改113.重復碼2007年作了修改11

10.1.4檢錯與糾錯的基本原理差錯編碼的基本思想是在被傳輸的信息中附加監督碼，用信息的冗余度來實現檢錯和糾錯。例如：000、001、010、011、100、101、110、111用來傳遞信息，則無法檢錯；000、011、101、110用來傳遞信息可以檢一位錯，但無法糾錯；000、111用來傳遞信息可以檢一位或兩位錯碼，還可以糾一位錯碼。可見，碼組間的差異與糾檢錯能力十分重要。1210.1.4檢錯與糾錯的基本原理12

定義1：碼組中非零碼元的數目稱為碼組的重量，簡稱碼重。定義2：兩碼組中對應碼位上具有不同碼元的數目稱為兩碼組的距離，簡稱碼距，又叫漢明距。最小漢明距離dmin決定糾檢錯能力例8種碼組000、001、010、011、100、101、110、111均為許用碼組時，最小碼距為1在選4種碼組000、011、101、110為許用碼組情況下，最小碼距為2采用2種許用碼組000、111時，最小碼距為313定義1：碼組中非零碼元的數目稱為碼組的重量，簡稱碼下圖為碼距的幾何解釋三種編碼組合，其漢明距分別為1，2，3。14下圖為碼距的幾何解釋14

對于分組碼，一般有如下結論：(1)在一個碼組內檢測e個誤碼，要求；(2)在一個碼組內糾正t個誤碼，要求；(3)在一個碼組內糾正t個誤碼，同時檢測個誤碼，要求。差錯控制編碼提高了通信系統的可靠性，也降低了有效性。為衡量有效性，定義編碼效率。k是編碼前碼組中的碼元數，即信息碼元數；n是編碼后碼組中的碼元數，它包含了校驗碼元。15對于分組碼，一般有如下結論：15

10.2線性分組碼線性碼組中的監督碼是信息碼元的線性組合。線性碼具有封閉性，即任意兩個許用碼組之和（模2加），結果仍為一許用碼組。設n位分組碼用表示，k位信息碼用表示，記該碼組為(n,k)碼。將碼組和信息碼組用行矩陣表示出來，則有：

1610.2線性分組碼16

n=k+m，n：編碼以后的位數k：編碼以前的位數，即信息碼m=n-k：監督位或校驗位17n=k+m，17

寫成矩陣形式，有，G為生成矩陣(k*n)，且：

設則k行k+m=n列18寫成矩陣形式，有，矩陣P的重要意義①與監督位或校驗位相對應②編碼的根據③譯碼的根據，檢糾錯的根據矩陣P如何選擇？編碼前信息碼組有k位碼元，k位碼元共有種組合編碼后碼組有n位碼元，n位碼元共有種組合，矩陣P可有多種選擇較強的檢錯或糾錯能力實現方法盡可能簡單且編碼效率高在數學上已經證明線性碼的最小碼距正好等于非零碼的最小碼重為了估算線性碼的差錯控制能力應首先求出碼組的最小碼距19矩陣P的重要意義①與監督位或校驗位相對應19

例10-1已知(6,3)碼的生成矩陣為G，試求：(1)編碼碼組和各碼組的碼重；(2)最小碼距及其差錯控制能力。

解?(1)由3位碼組成的信息碼組矩陣為D：20例10-1已知(6,3)碼的生成矩陣為G，試求：(1)編

由式，得碼組矩陣為：

信息碼組、編碼碼組及碼重如下表所示：信息碼組編碼碼組碼重W信息碼組編碼碼組碼重W0000000000100100101300100111031011010114010010011311011011040110111014111111000321由式，得碼組矩陣為：21

由前表可知，非零碼組的最小碼重為：所以最小碼距為：因此，該碼有糾1錯，或檢2錯，或糾一錯同時檢一錯的能力。

22由前表可知，非零碼組的最小碼重為：22

譯碼原理

由可知，或寫成設，則有。任何線性分組碼碼組都應該滿足上述關系信息碼與監督碼間的校驗關系完全取決于HH矩陣稱為校驗矩陣或監督矩陣，是譯碼的關鍵！23譯碼原理23發送碼組A在傳輸過程中可能發生誤碼，設接收到的碼組為B=[bn-1bn-2…b0]則B–A=EE=[en-1en-2…e0]錯誤圖樣也可寫作B=A+E24發送碼組A在傳輸過程中可能發生誤碼，設接收到的碼組為B=[b接收端計算校正子為錯誤圖樣與校正子之間有確定的關系25接收端計算校正子為25例設且有3

個接收碼組驗證3個接收碼組是否發生差錯？若在某碼組中有錯碼，錯碼的校正子是什么？然后再指出發生錯碼的碼字中，哪位有錯？26例設解：1）若無錯，則錯誤圖樣為0，S為0

B1無錯B2錯B3錯2）∵S2=H第1列∴E=[100000]第1位錯同理S3=H第3列∴E=[001000]第3位錯27解：1）若無錯，則錯誤圖樣為0，S為0

B1無錯B2錯B3錯

10.3循環碼10.3.1循環碼的特點及表達式循環碼是一種系統分組碼，前k位是信息碼，后r位是監督碼。不僅具有封閉性，還具有循環性，即一許用碼組經循環移位后得到另一個許用碼組。設是一個循環碼組，則可將之表示為：

上式稱為碼多項式。2810.3循環碼28

碼組C移位1次得到的仍是碼組，它可寫成：

不難驗證：類似地，碼組C經i次移位后，得到的新的碼組是除以的余式。也就是說，在模意義下，若c(x)是碼多項式，則都是碼多項式。循環碼的編碼過程也可用多項式來描述。29碼組C移位1次得到的仍是碼組，它可寫成：29循環冗余編碼CRC在數據鏈路層傳送的幀中，廣泛使用了循環冗余檢驗CRC的檢錯技術。假設待傳送的數據M=1010001101（共kbit）。我們在M的后面再添加供差錯檢測用的nbit冗余碼一起發送。冗余碼的計算用二進制的模2運算進行2n乘M的運算，這相當于在M后面添加n個0。得到的(k+n)bit的數除以事先選定好的長度為(n+1)bit的數P，得出商是Q而余數是R，余數R比除數P至少要少1個比特。30循環冗余編碼CRC在數據鏈路層傳送的幀中，廣泛使用了循環冗余3131冗余碼的計算舉例設n=5,P=110101，M=1010001101模2運算的結果是：商Q=1101010110，余數R=01110。將余數R作為冗余碼添加在數據M的后面發送出去，即發送的數據是101000110101110，或2nM+R。32冗余碼的計算舉例設n=5,P=110101，循環冗余檢驗的原理說明

1101010110

←

Q

商

除數

P→

110101101000110100000

←

2nM被除數

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

余數33循環冗余檢驗的原理說明循環冗余檢驗的原理說明只要得出的余數R不為0，就表示檢測到了差錯。但這種檢測方法并不能確定究竟是哪一個或哪幾個比特出現了差錯。一旦檢測出差錯，就丟棄這個出現差錯的幀。只要經過嚴格的挑選，并使用位數足夠多的除數P，那么出現檢測不到的差錯的概率就很小很小。34循環冗余檢驗的原理說明只要得出的余數R不為0，就表示353510.4卷積碼引言卷積碼是非分組碼。它充分利用了各組之間的相關性，信息碼的碼長k和卷積碼的碼長n都比較小。卷積碼的性能在許多實際應用情況下優于分組碼，而且設備也較簡單。通常它更適用于前向糾錯，在高質量的通信設備中已得到廣泛應用。3610.4卷積碼引言36卷積碼中編碼后的n個碼元不僅與當前段的k個信息有關，而且也與前面（N-1）段的信息有關，編碼過程中相互關聯的碼元為nN個。因此，這N段時間內的碼元數目nN通常被稱為這種碼的約束長度。由于與前面m段規定時間內的信息位有關，這里的m＝N-1通常用（n，k，m）表示卷積碼。37卷積碼中編碼后的n個碼元不僅與當前段的k個信息有關，例如：卷積碼的n=2，k=1，m=2，因此，它的約束長度nN=n×(m+1)=2×3=6。

38例如：卷積碼的n=2，k=1，m=假如輸入的信息為D=[11010]，為了使信息D全部通過移位寄存器，還必須在信息位后面加3個零。表列出了對信息D進行卷積編碼時的狀態。描述卷積碼的方法：圖解表示和解析表示。卷積碼的譯碼方法可分為代數譯碼和概率譯碼兩大類。

39假如輸入的信息為D=[11010]，為了使信息D第十章差錯控制編碼40第十章差錯控制編碼1引言信源編碼，目的是實現模擬信號數字化信道編碼，目的是提高數字通信的可靠性差錯率是信噪比的函數信道編碼，差錯控制編碼，抗干擾編碼信道編碼過程：信息碼元序列＋監督碼元→編碼碼組信道譯碼過程：編碼碼組→檢錯或糾錯→信息碼元序列41引言信源編碼，目的是實現模擬信號數字化210.1差錯控制編碼的基本概念10.1.1?差錯控制方式10.1.2?差錯控制編碼分類10.1.3?幾種簡單的檢錯碼10.1.4?檢錯和糾錯的基本原理4210.1差錯控制編碼的基本概念10.1.1?差錯控制方式310.1.1差錯控制方式常用的差錯控制方式有三種：前向糾錯（FEC:forwarderrorcorrection）發送能糾錯的碼，在譯碼時自動發現并糾正傳輸中的錯誤只需正向信道，實時性好編譯碼設備復雜，適合單向信道和一發多收系統檢錯重發（ARQ:automaticrepeatrequest）發送端發出能夠檢錯的碼，接收端檢驗，接收端發出反饋應答信號，發送端重新傳輸直到正確接收為止工作原理簡單，正向信道+反向信道，傳輸效率低混合糾錯（HEC:hybriderrorcorrection）前向糾錯方式和檢錯重發方式的結合與折衷外層先采用前向糾錯，當前向糾錯不能解決問題時，內層再采用檢錯重發。4310.1.1差錯控制方式常用的差錯控制方式有三種：4

（a）FEC方式（b）ARQ方式（c）HEC方式44（a）5

檢錯重發的三種方式

停發等候重發返回重發選擇重發45檢停發等候重發返回重發選擇重發6

10.1.2差錯控制編碼分類在編碼前先把信息序列分為k位一組（稱為信息碼），然后附加m位監督碼，形成n=k+m位的碼組。1、按信息碼和附加監督碼間的檢驗關系線性碼：監督碼是信息碼的線性組合非線性碼：監督碼是信息碼的非線性組合2、按信息碼和監督碼間的約束方式分組碼：監督碼僅與本碼組的信息碼有關卷積碼：監督碼與之前的若干個信息碼組的碼元有約束關系4610.1.2差錯控制編碼分類710.1.3幾種簡單的檢錯碼1.奇偶監督碼編碼方法把信息碼元先分組，在每組最后加一位監督碼元，使該碼組中1的數目為奇數或偶數奇數時稱為奇校驗碼偶數時稱為偶校驗碼偶校驗碼許用碼組為000，011，101，110禁用碼組為001，010，100，111奇校驗碼禁用碼組為000，011，101，110許用碼組為001，010，100，1114710.1.3幾種簡單的檢錯碼1.奇偶監督碼8

一般情況下：設碼組長為n，且為：則偶校驗時有：奇校驗時有：譯碼方法(與編碼方法相對應)不滿足校驗關系，傳輸一定錯誤！奇偶校驗只能發現奇數個(單個)錯誤，不能檢測出偶數個錯誤。編碼方法簡單且實用性強，適用于檢測隨機零星錯碼滿足校驗關系，傳輸一定準確嗎？48一般情況下：92.二維奇偶監督碼將奇偶校驗碼的若干碼組排列成矩陣每一碼組寫成一行m個碼組m行m個監督位構成了一監督位列按列的方向增加第二維校驗位n個監督位構成了一監督位行檢錯能力檢出所有行和列中的奇數個差錯能檢出大多數偶數個差錯檢測突發錯碼也有一定的適應能力方陣碼，交織碼492.二維奇偶監督碼檢錯能力10

3.重復碼

重復碼是在每位信息碼元之后，再簡單重復多次的編碼；接收端譯碼時采用多數表決法。4.恒比碼

從固定碼長的碼組中選擇那些1和0的比例恒定的碼組作為許用碼組，如五單位保護電碼等。5.ISBN國際統一圖書編號2007年作了修改503.重復碼2007年作了修改11

10.1.4檢錯與糾錯的基本原理差錯編碼的基本思想是在被傳輸的信息中附加監督碼，用信息的冗余度來實現檢錯和糾錯。例如：000、001、010、011、100、101、110、111用來傳遞信息，則無法檢錯；000、011、101、110用來傳遞信息可以檢一位錯，但無法糾錯；000、111用來傳遞信息可以檢一位或兩位錯碼，還可以糾一位錯碼。可見，碼組間的差異與糾檢錯能力十分重要。5110.1.4檢錯與糾錯的基本原理12

定義1：碼組中非零碼元的數目稱為碼組的重量，簡稱碼重。定義2：兩碼組中對應碼位上具有不同碼元的數目稱為兩碼組的距離，簡稱碼距，又叫漢明距。最小漢明距離dmin決定糾檢錯能力例8種碼組000、001、010、011、100、101、110、111均為許用碼組時，最小碼距為1在選4種碼組000、011、101、110為許用碼組情況下，最小碼距為2采用2種許用碼組000、111時，最小碼距為352定義1：碼組中非零碼元的數目稱為碼組的重量，簡稱碼下圖為碼距的幾何解釋三種編碼組合，其漢明距分別為1，2，3。53下圖為碼距的幾何解釋14

對于分組碼，一般有如下結論：(1)在一個碼組內檢測e個誤碼，要求；(2)在一個碼組內糾正t個誤碼，要求；(3)在一個碼組內糾正t個誤碼，同時檢測個誤碼，要求。差錯控制編碼提高了通信系統的可靠性，也降低了有效性。為衡量有效性，定義編碼效率。k是編碼前碼組中的碼元數，即信息碼元數；n是編碼后碼組中的碼元數，它包含了校驗碼元。54對于分組碼，一般有如下結論：15

10.2線性分組碼線性碼組中的監督碼是信息碼元的線性組合。線性碼具有封閉性，即任意兩個許用碼組之和（模2加），結果仍為一許用碼組。設n位分組碼用表示，k位信息碼用表示，記該碼組為(n,k)碼。將碼組和信息碼組用行矩陣表示出來，則有：

5510.2線性分組碼16

n=k+m，n：編碼以后的位數k：編碼以前的位數，即信息碼m=n-k：監督位或校驗位56n=k+m，17

寫成矩陣形式，有，G為生成矩陣(k*n)，且：

設則k行k+m=n列57寫成矩陣形式，有，矩陣P的重要意義①與監督位或校驗位相對應②編碼的根據③譯碼的根據，檢糾錯的根據矩陣P如何選擇？編碼前信息碼組有k位碼元，k位碼元共有種組合編碼后碼組有n位碼元，n位碼元共有種組合，矩陣P可有多種選擇較強的檢錯或糾錯能力實現方法盡可能簡單且編碼效率高在數學上已經證明線性碼的最小碼距正好等于非零碼的最小碼重為了估算線性碼的差錯控制能力應首先求出碼組的最小碼距58矩陣P的重要意義①與監督位或校驗位相對應19

例10-1已知(6,3)碼的生成矩陣為G，試求：(1)編碼碼組和各碼組的碼重；(2)最小碼距及其差錯控制能力。

解?(1)由3位碼組成的信息碼組矩陣為D：59例10-1已知(6,3)碼的生成矩陣為G，試求：(1)編

由式，得碼組矩陣為：

信息碼組、編碼碼組及碼重如下表所示：信息碼組編碼碼組碼重W信息碼組編碼碼組碼重W0000000000100100101300100111031011010114010010011311011011040110111014111111000360由式，得碼組矩陣為：21

由前表可知，非零碼組的最小碼重為：所以最小碼距為：因此，該碼有糾1錯，或檢2錯，或糾一錯同時檢一錯的能力。

61由前表可知，非零碼組的最小碼重為：22

譯碼原理

由可知，或寫成設，則有。任何線性分組碼碼組都應該滿足上述關系信息碼與監督碼間的校驗關系完全取決于HH矩陣稱為校驗矩陣或監督矩陣，是譯碼的關鍵！62譯碼原理23發送碼組A在傳輸過程中可能發生誤碼，設接收到的碼組為B=[bn-1bn-2…b0]則B–A=EE=[en-1en-2…e0]錯誤圖樣也可寫作B=A+E63發送碼組A在傳輸過程中可能發生誤碼，設接收到的碼組為B=[b接收端計算校正子為錯誤圖樣與校正子之間有確定的關系64接收端計算校正子為25例設且有3

個接收碼組驗證3個接收碼組是否發生差錯？若在某碼組中有錯碼，錯碼的校正子是什么？然后再指出發生錯碼的碼字中，哪位有錯？65例設解：1）若無錯，則錯誤圖樣為0，S為0

B1無錯B2錯B3錯2）∵S2=H第1列∴E=[100000]第1位錯同理S3=H第3列∴E=[001000]第3位錯66解：1）若無錯，則錯誤圖樣為0，S為0

B1無錯B2錯B3錯

10.3循環碼10.3.1循環碼的特點及表達式循環碼是一種系統分組碼，前k位是信息碼，后r位是監督碼。不僅具有封閉性，還具有循環性，即一許用碼組經循環移位后得到另一個許用碼組。設是一個循環碼組，則可將之表示為：

上式稱為碼多項式。6710.3循環碼28

碼組C移位1次得到的仍是碼組，它可寫成：

不難驗證：類似地，碼組C經i次移位后，得到的新的碼組是除以的余式。也就是說，在模意義下，若c(x)是碼多項式，則都是碼多項式。循環碼的編碼過程也可用多項式來描述。68碼組C移位1次得到的仍是碼組，它可寫成：29循環冗余編碼CRC在數據鏈路層傳送的幀中，廣泛使用了循環冗余檢驗CRC的檢錯技術。假設待傳送的數據M=1010001101（共kbit）。我們在M的后面再添加供差錯檢測用的nbit冗余碼一起發送。冗余碼的計算用二進制的模2運算進行2n乘M的運算，這相當于在M后面添加n個0。得到的(k+n)bit的數除以事先選定好的長度為(n+1)bit的數P，得出商是Q而余數是R，余數R比除數P至少要少1個比特。69循環冗余編碼CRC在數據鏈路層傳送的幀中，廣泛使用了循環冗余7031冗余碼的計算舉例設n=5,P=110101，M=1010001101模2運算的結果是：商Q=1101010110，余數R=01110。將余數R作為冗余碼添加在數據M的后面發送出去，即發送的數據是101000110101110，或2nM+R。71冗余碼的計算舉例設n=5,P=110101，循環冗余檢驗的原理說明

1101010110

←

Q

商

除數

P→

110101101000110100000

←

2nM被除數

110101

111011