第八章差錯控制編碼8.1差錯控制編碼的基本概念信道編碼：目的：提高數字通信的可靠性。方法：以一定的編碼規格附加一些監督碼元(增加多余比特)，以發現或糾正錯誤。差錯控制：包括信道編碼在內的一切糾正錯誤手段。產生錯碼的原因：碼間串擾信噪比降低1第八章差錯控制編碼8.1差錯控制編碼的基8.1.1差錯控制方式檢錯重發（ARQ）：停發等候重發返回重發選擇重發特點：能發現錯碼，但是不能確定錯碼的位置。通信系統需要有雙向信道。前向糾錯（FEC）：利用加入的差錯控制碼元，不但能夠發現錯碼，還能糾正錯碼。優點：不要求重發，接收信號時延小，實時性好。缺點：對糾錯碼要求高，糾錯能力強影響編譯碼設備復雜化。適用范圍：單向信道和廣播方式。

混合糾錯（HEC）：內層使用FEC方式，外層采用ARQ方式，在實時性和編碼復雜性介于檢錯重發系統和前向糾錯系統之間。適用范圍：環路延遲大的高速數據傳輸系統。28.1.1差錯控制方式2前向糾錯(FEC)檢錯重發(ARQ)混合糾錯(HEC)3前向糾錯(FEC)檢錯重發(ARQ)混合糾錯(HEC)3停發等候重發返回重發選擇重發4停發等候重發返回重發選擇重發4ARQ和前向糾錯比較：優點監督碼元較少，即碼率較高檢錯的計算復雜度較低能適應不同特性的信道缺點需要雙向信道。不適用于一點到多點的通信系統或廣播系統。傳輸效率降低，可能因反復重發而造成事實上的通信中斷。558.1.2差錯控制編碼分類按信息碼元和附加的監督碼元之間的檢驗關系分為：線性碼非線性碼按信息碼元和附加的監督碼元之間的約束關系分為：分組碼

卷積碼（連環碼或鏈碼）

68.1.2差錯控制編碼分類68.1.3幾種簡單的檢錯碼1、一維奇偶監督碼奇偶監督碼－分為奇數監督碼和偶數監督碼兩類。在奇偶監督碼中，監督位只有1位。偶數監督碼中，此監督位使碼組中“1”的個數為偶數： 式中，an-1為監督位，其他位為信息位。奇數監督碼中，此監督位使碼組中“1”的個數為奇數：檢錯能力－能夠檢測奇數個錯碼。不能檢驗偶數個錯碼78.1.3幾種簡單的檢錯碼檢錯能力－能夠檢測奇數個錯2、二維奇偶監督碼（方陣碼）有可能檢測偶數個錯碼適合檢測突發錯碼………………………82、二維奇偶監督碼（方陣碼）………3、重復碼

在每位信息碼元之后，用簡單重復多次的方法編碼接收端譯碼采用多數表決法檢錯能力－取決于碼元重復位數9檢錯能力－取決于碼元重復位數94、恒比碼從某確定碼長的碼組中挑選那些1和0的比例為恒定值的碼組作為許用碼。檢測時，只計算接收碼組中1的數目是否正確，就可知道是否出錯。例如：我國郵電部門采用的五單位數字保護電碼檢錯能力－能夠檢測所有奇數個錯碼及部分偶數個錯碼104、恒比碼例如：我國郵電部門采用的五單位數字保護電碼檢錯能5、ISBN國際統一圖書編號

例如：圖書編號格式：ISBN0-471-02977-7115、ISBN國際統一圖書編號例如：圖書編號格式：I8.1.4檢錯和糾錯的基本原理檢錯和糾錯能力是用信息量的冗余度來換取的。分組碼舉例設：有一種由3個二進制碼元構成的編碼，它共有23=8種 不同的可能碼組： 000–晴001–云010–陰011–雨 100–雪101–霜110–霧111–雹 這時，若一個碼組中發生錯碼，則將收到錯誤信息。若在此8種碼組中僅允許使用4種來傳送天氣，例如：令 000–晴011–云101–陰110–雨 為許用碼組，其他4種不允許使用，稱為禁用碼組。 這時，接收端有可能發現（檢測到）碼組中的一個錯碼。這種編碼只能檢測錯碼，不能糾正錯碼。若規定只許用兩個碼組：例如 000–晴111–雨 就能檢測兩個以下錯碼，或糾正一個錯碼。 128.1.4檢錯和糾錯的基本原理12首先了解差錯編碼中的幾個重要概念：（1）碼重：碼組中非零碼元的數目（2）碼距（漢明距）：兩個碼組中對應碼位上具有不同碼元的位數（3）最小碼距13首先了解差錯編碼中的幾個重要概念：（1）碼重：碼組中非零碼元例如：3位碼組結論：碼距為從一個頂點沿立方體各邊到另一個頂點多經過的最少邊數14例如：3位碼組結論：碼距為從一個頂點沿立方體各邊到另一個頂點（1）在一個碼組內檢測e個誤碼，要求最小碼距：（2）在一個碼組內糾正t個誤碼，要求最小碼距：（3）在一個碼組內糾正t個誤碼，同時檢測e個誤碼，要求最小碼距：對于分組碼來說，有以下結論：15（1）在一個碼組內檢測e個誤碼，要求最小碼距：（2）在一個碼衡量編碼效率，定義：編碼能力對比：差錯控制能力相同時，要求編碼效率盡可能大，譯碼方式盡可能簡單。16衡量編碼效率，定義：編碼能力對比：168.2線性分組碼基本概念代數碼－利用代數關系式產生監督位的編碼線性分組碼－代數碼的一種，其監督位和信息位的關系由線性代數方程決定重要性質：封閉性——任意兩個許用碼組之和（逐位模2加）仍為一個許用碼組信息碼組碼組滿足關系：C中的n個元素是由D中k個元素線性組合形成。C中前k位與D中k個元素相同，后n-k位是D中k個元素線性組合

178.2線性分組碼信息碼組碼組滿足關系：C中的n個元素是由D信息碼組碼組滿目關系：18信息碼組碼組滿目關系：18將碼組C表示成矩陣形式為：由上式，矩陣G可分為兩個矩陣：19將碼組C表示成矩陣形式為：由上式，矩陣G可分為兩個矩陣：1將碼組C表示成矩陣形式為：結論：碼組C，前k位D為信息位，后m位是監督位或校驗位。20將碼組C表示成矩陣形式為：結論：碼組C，前k位D為信息位，后譯碼：表示成矩陣形式為：定義校驗矩陣（監督矩陣）：21譯碼：表示成矩陣形式為：定義校驗矩陣（監督矩陣）：21設接收碼組：定義伴隨式：已知：可得糾錯后的碼組C為：結論：以上方法構成的線性分組碼中，能糾正單個錯誤的線性分組碼稱為漢明碼。22設接收碼組：定義伴隨式：已知：可得糾錯后的碼組C為：結論：以線性分組碼的碼長n、信息位k和監督位m之間應滿足不等式：取等號時，為漢明碼，此時，有關系式：對于一般情況：23線性分組碼的碼長n、信息位k和監督位m之間應滿足不等式：取等漢明碼的編碼效率為：對于一般情況，校驗位數m應滿足不等式：24漢明碼的編碼效率為：對于一般情況，校驗位數m應滿足不等式：28.3循環碼 8.3.1循環碼的特點及表達： 循環性是指任一碼組循環一位后仍然是該編碼中的一個碼組。例：一種(7,3)循環碼的全部碼組如下 表中第2碼組向右移一位即得到第5碼組；第5碼組向右移一位即得到第7碼組。碼組編號信息位監督位碼組編號信息位監督位A6a5a4a3a2a1a0a6a5a4A3a2a1a01000000051001011200101116101110030101110711001014011100181110010258.3循環碼碼組編號信息位監督位碼組編號信息位監督位A一般情況 若(an-1

an-2…a0)是循環碼的一個碼組，則循環移位后的碼組： (an-2

an-3…a0

an-1) (an-3

an-4…an-1

an-2) …… (a0

an-1…a2

a1)仍然是該編碼中的碼組。多項式表示法 一個長度為n的碼組(an-1

an-2…a0)可以表示成

上式中x的值沒有任何意義，僅用它的冪代表碼元的位置。 例：碼組1100101可以表示為26一般情況26碼組C移位1次得到仍然是碼組，其表達式為：上式恰好是除以后的余式，即：運算過程如下式：27碼組C移位1次得到仍然是碼組，其表達式為：上式結論：碼組C移位i次，相應的碼組多項式是除以的余式。28結論：碼組C移位i次，相應的碼組多項式是一個k位的信息碼組,信息多項式為：假設碼組表示為：即：將c(x)提高一次，可得：上式還可表示為：則最終可表示為：29一個k位的信息碼組8.4差錯控制編碼對系統系統的改善已知：若在T時間內傳送k位信息碼元無編碼系統：差錯編碼系統：結論：編碼系統比無編碼系統在信道中的信息速率高n/k倍，傳輸帶寬大n/k倍，信噪比低n/k倍。編碼系統在信道傳輸的誤比特率高于無編碼系統308.4差錯控制編碼對系統系統的改善已知：若在T時間內傳

8.4差錯控制編碼對系統系統的改善已知：若在T時間內傳送k位信息碼元無編碼系統：差錯編碼系統：結論：編碼系統比無編碼系統的誤碼組率低318.4差錯控制編碼對系統系統的改善已知：若在T時間內傳第八章差錯控制編碼8.1差錯控制編碼的基本概念信道編碼：目的：提高數字通信的可靠性。方法：以一定的編碼規格附加一些監督碼元(增加多余比特)，以發現或糾正錯誤。差錯控制：包括信道編碼在內的一切糾正錯誤手段。產生錯碼的原因：碼間串擾信噪比降低32第八章差錯控制編碼8.1差錯控制編碼的基8.1.1差錯控制方式檢錯重發（ARQ）：停發等候重發返回重發選擇重發特點：能發現錯碼，但是不能確定錯碼的位置。通信系統需要有雙向信道。前向糾錯（FEC）：利用加入的差錯控制碼元，不但能夠發現錯碼，還能糾正錯碼。優點：不要求重發，接收信號時延小，實時性好。缺點：對糾錯碼要求高，糾錯能力強影響編譯碼設備復雜化。適用范圍：單向信道和廣播方式。

混合糾錯（HEC）：內層使用FEC方式，外層采用ARQ方式，在實時性和編碼復雜性介于檢錯重發系統和前向糾錯系統之間。適用范圍：環路延遲大的高速數據傳輸系統。338.1.1差錯控制方式2前向糾錯(FEC)檢錯重發(ARQ)混合糾錯(HEC)34前向糾錯(FEC)檢錯重發(ARQ)混合糾錯(HEC)3停發等候重發返回重發選擇重發35停發等候重發返回重發選擇重發4ARQ和前向糾錯比較：優點監督碼元較少，即碼率較高檢錯的計算復雜度較低能適應不同特性的信道缺點需要雙向信道。不適用于一點到多點的通信系統或廣播系統。傳輸效率降低，可能因反復重發而造成事實上的通信中斷。3658.1.2差錯控制編碼分類按信息碼元和附加的監督碼元之間的檢驗關系分為：線性碼非線性碼按信息碼元和附加的監督碼元之間的約束關系分為：分組碼

卷積碼（連環碼或鏈碼）

378.1.2差錯控制編碼分類68.1.3幾種簡單的檢錯碼1、一維奇偶監督碼奇偶監督碼－分為奇數監督碼和偶數監督碼兩類。在奇偶監督碼中，監督位只有1位。偶數監督碼中，此監督位使碼組中“1”的個數為偶數： 式中，an-1為監督位，其他位為信息位。奇數監督碼中，此監督位使碼組中“1”的個數為奇數：檢錯能力－能夠檢測奇數個錯碼。不能檢驗偶數個錯碼388.1.3幾種簡單的檢錯碼檢錯能力－能夠檢測奇數個錯2、二維奇偶監督碼（方陣碼）有可能檢測偶數個錯碼適合檢測突發錯碼………………………392、二維奇偶監督碼（方陣碼）………3、重復碼

在每位信息碼元之后，用簡單重復多次的方法編碼接收端譯碼采用多數表決法檢錯能力－取決于碼元重復位數40檢錯能力－取決于碼元重復位數94、恒比碼從某確定碼長的碼組中挑選那些1和0的比例為恒定值的碼組作為許用碼。檢測時，只計算接收碼組中1的數目是否正確，就可知道是否出錯。例如：我國郵電部門采用的五單位數字保護電碼檢錯能力－能夠檢測所有奇數個錯碼及部分偶數個錯碼414、恒比碼例如：我國郵電部門采用的五單位數字保護電碼檢錯能5、ISBN國際統一圖書編號

例如：圖書編號格式：ISBN0-471-02977-7425、ISBN國際統一圖書編號例如：圖書編號格式：I8.1.4檢錯和糾錯的基本原理檢錯和糾錯能力是用信息量的冗余度來換取的。分組碼舉例設：有一種由3個二進制碼元構成的編碼，它共有23=8種 不同的可能碼組： 000–晴001–云010–陰011–雨 100–雪101–霜110–霧111–雹 這時，若一個碼組中發生錯碼，則將收到錯誤信息。若在此8種碼組中僅允許使用4種來傳送天氣，例如：令 000–晴011–云101–陰110–雨 為許用碼組，其他4種不允許使用，稱為禁用碼組。 這時，接收端有可能發現（檢測到）碼組中的一個錯碼。這種編碼只能檢測錯碼，不能糾正錯碼。若規定只許用兩個碼組：例如 000–晴111–雨 就能檢測兩個以下錯碼，或糾正一個錯碼。 438.1.4檢錯和糾錯的基本原理12首先了解差錯編碼中的幾個重要概念：（1）碼重：碼組中非零碼元的數目（2）碼距（漢明距）：兩個碼組中對應碼位上具有不同碼元的位數（3）最小碼距44首先了解差錯編碼中的幾個重要概念：（1）碼重：碼組中非零碼元例如：3位碼組結論：碼距為從一個頂點沿立方體各邊到另一個頂點多經過的最少邊數45例如：3位碼組結論：碼距為從一個頂點沿立方體各邊到另一個頂點（1）在一個碼組內檢測e個誤碼，要求最小碼距：（2）在一個碼組內糾正t個誤碼，要求最小碼距：（3）在一個碼組內糾正t個誤碼，同時檢測e個誤碼，要求最小碼距：對于分組碼來說，有以下結論：46（1）在一個碼組內檢測e個誤碼，要求最小碼距：（2）在一個碼衡量編碼效率，定義：編碼能力對比：差錯控制能力相同時，要求編碼效率盡可能大，譯碼方式盡可能簡單。47衡量編碼效率，定義：編碼能力對比：168.2線性分組碼基本概念代數碼－利用代數關系式產生監督位的編碼線性分組碼－代數碼的一種，其監督位和信息位的關系由線性代數方程決定重要性質：封閉性——任意兩個許用碼組之和（逐位模2加）仍為一個許用碼組信息碼組碼組滿足關系：C中的n個元素是由D中k個元素線性組合形成。C中前k位與D中k個元素相同，后n-k位是D中k個元素線性組合

488.2線性分組碼信息碼組碼組滿足關系：C中的n個元素是由D信息碼組碼組滿目關系：49信息碼組碼組滿目關系：18將碼組C表示成矩陣形式為：由上式，矩陣G可分為兩個矩陣：50將碼組C表示成矩陣形式為：由上式，矩陣G可分為兩個矩陣：1將碼組C表示成矩陣形式為：結論：碼組C，前k位D為信息位，后m位是監督位或校驗位。51將碼組C表示成矩陣形式為：結論：碼組C，前k位D為信息位，后譯碼：表示成矩陣形式為：定義校驗矩陣（監督矩陣）：52譯碼：表示成矩陣形式為：定義校驗矩陣（監督矩陣）：21設接收碼組：定義伴隨式：已知：可得糾錯后的碼組C為：結論：以上方法構成的線性分組碼中，能糾正單個錯誤的線性分組碼稱為漢明碼。53設接收碼組：定義伴隨式：已知：可得糾錯后的碼組C為：結論：以線性分組碼的碼長n、信息位k和監督位m之間應滿足不等式：取等號時，為漢明碼，此時，有關系式：對于一般情況：54線性分組碼的碼長n、信息位k和監督位m之間應滿足不等式：取等漢明碼的編碼效率為：對于一般情況，校驗位數m應滿足不等式：55漢明碼的編碼效率為：對于一般情況，校驗位數m應滿足不等式：28.3循環碼 8.3.1循環碼的特點及表達： 循環性是指任一碼組循環一位后仍然是該編碼中的一個碼組。例：一種(7,3)循環碼的全部碼組如下 表中第2碼組向右移一位即得到第5碼組；第5碼組向右移一位即得到第7碼組。碼組編號信息位監督位碼組編號信息位監督位A6a5a4a3a2a1a0a6a5a4A3a2a1a01000000051001011200101116101110030101110711001014011100181110010568.3循環碼碼組編號信息位監督位碼組編號信息位監督位A一般情況 若(an-1