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

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

卷積碼（連環(huán)碼或鏈碼）

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

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

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

179.2線性分組碼信息碼組碼組滿足關(guān)系：C中的n個元素是由D信息碼組碼組滿目關(guān)系：18信息碼組碼組滿目關(guān)系：18將碼組C表示成矩陣形式為：由上式，矩陣G可分為兩個矩陣：19將碼組C表示成矩陣形式為：由上式，矩陣G可分為兩個矩陣：1將碼組C表示成矩陣形式為：結(jié)論：碼組C，前k位D為信息位，后m位是監(jiān)督位或校驗位。20將碼組C表示成矩陣形式為：結(jié)論：碼組C，前k位D為信息位，后例9-1已知（6，3）碼的生成矩陣為試求：（1）編碼碼組和各個碼的碼重；（2）最小碼距dmin和該碼的差錯控制能力。21例9-1已知（6，3）碼的生成矩陣為試求：21解：（1）由3位碼組成的信息碼組矩陣為由式（9-10）可求出碼組矩陣為22解：（1）由3位碼組成的信息碼組矩陣為由式（9-10）可求出信息碼組、編碼碼組及碼重如表9-2所示。23信息碼組、編碼碼組及碼重如表9-2所示。23（2）由表9-2可知，非零碼組的最小碼重為：Wmin=3最小碼距為：Dmin=3因此，該碼有糾1錯，或檢2錯，或糾1錯同時檢1錯的能力。24（2）由表9-2可知，非零碼組的最小碼重為：24譯碼：表示成矩陣形式為：定義校驗矩陣（監(jiān)督矩陣）：25譯碼：表示成矩陣形式為：定義校驗矩陣（監(jiān)督矩陣）：25設(shè)接收碼組：定義伴隨式：已知：可得糾錯后的碼組C為：結(jié)論：以上方法構(gòu)成的線性分組碼中，能糾正單個錯誤的線性分組碼稱為漢明碼。26設(shè)接收碼組：定義伴隨式：已知：可得糾錯后的碼組C為：結(jié)論：以例9-2按照例9-1生成矩陣G，列出S與E的對照表。當收到碼組時，解出對應(yīng)的信息碼組D。

27例9-2按照例9-1生成矩陣G，列出S與E的對照表。當解：已知生成矩陣G為所以監(jiān)督矩陣H為28解：已知生成矩陣G為所以監(jiān)督矩陣H為28所以接收向量R不正確。29所以接收向量R不正確。29伴隨矩陣ST與監(jiān)督矩陣H的第二列相同。所以錯誤圖樣E為：30伴隨矩陣ST與監(jiān)督矩陣H的第二列相同。30線性分組碼的碼長n、信息位k和監(jiān)督位m之間應(yīng)滿足不等式：取等號時，為漢明碼，此時，有關(guān)系式：對于一般情況：31線性分組碼的碼長n、信息位k和監(jiān)督位m之間應(yīng)滿足不等式：取等漢明碼的編碼效率為：對于一般情況，校驗位數(shù)m應(yīng)滿足不等式：32漢明碼的編碼效率為：對于一般情況，校驗位數(shù)m應(yīng)滿足不等式：39.3循環(huán)碼 9.3.1循環(huán)碼的特點及表達： 循環(huán)性是指任一碼組循環(huán)一位后仍然是該編碼中的一個碼組。例：一種(7,3)循環(huán)碼的全部碼組如下 表中第2碼組向右移一位即得到第5碼組；第5碼組向右移一位即得到第7碼組。碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位A6a5a4a3a2a1a0a6a5a4A3a2a1a01000000051001011200101116101110030101110711001014011100181110010339.3循環(huán)碼碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位A一般情況 若(an-1

an-2…a0)是循環(huán)碼的一個碼組，則循環(huán)移位后的碼組： (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可以表示為34一般情況34碼組C移位1次得到仍然是碼組，其表達式為：上式恰好是除以后的余式，即：運算過程如下式：35碼組C移位1次得到仍然是碼組，其表達式為：上式結(jié)論：碼組C移位i次，相應(yīng)的碼組多項式是除以的余式。36結(jié)論：碼組C移位i次，相應(yīng)的碼組多項式是一個k位的信息碼組,信息多項式為：假設(shè)碼組表示為：即：將c(x)提高一次，可得：上式還可表示為：則最終可表示為：37一個k位的信息碼組8.4差錯控制編碼對系統(tǒng)系統(tǒng)的改善已知：若在T時間內(nèi)傳送k位信息碼元無編碼系統(tǒng)：差錯編碼系統(tǒng)：結(jié)論：編碼系統(tǒng)比無編碼系統(tǒng)在信道中的信息速率高n/k倍，傳輸帶寬大n/k倍，信噪比低n/k倍。編碼系統(tǒng)在信道傳輸?shù)恼`比特率高于無編碼系統(tǒng)388.4差錯控制編碼對系統(tǒng)系統(tǒng)的改善已知：若在T時間內(nèi)傳

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

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

卷積碼（連環(huán)碼或鏈碼）

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

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

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

569.2線性分組碼信息碼組碼組滿足關(guān)系：C中的n個元素是由D信息碼組碼組滿目關(guān)系：57信息碼組碼組滿目關(guān)系：18將碼組C表示成矩陣形式為：由上式，矩陣G可分為兩個矩陣：58將碼組C表示成矩陣形式為：由上式，矩陣G可分為兩個矩陣：1將碼組C表示成矩陣形式為：結(jié)論：碼組C，前k位D為信息位，后m位是監(jiān)督位或校驗位。59將碼組C表示成矩陣形式為：結(jié)論：碼組C，前k位D為信息位，后例9-1已知（6，3）碼的生成矩陣為試求：（1）編碼碼組和各個碼的碼重；（2）最小碼距dmin和該碼的差錯控制能力。60例9-1已知（6，3）碼的生成矩陣為試求：21解：（1）由3位碼組成的信息碼組矩陣為由式（9-10）可求出碼組矩陣為61解：（1）由3位碼組成的信息碼組矩陣為由式（9-10）可求出信息碼組、編碼碼組及碼重如表9-2所示。62信息碼組、編碼碼組及碼重如表9-2所示。23（2）由表9-2可知，非零碼組的最小碼重為：Wmin=3最小碼距為：Dmin=3因此，該碼有糾1錯，或檢2錯，或糾1錯同時檢1錯的能力。63（2）由表9-2可知，非零碼組的最小碼重為：24譯碼：表示成矩陣形式為：定義校驗矩陣（監(jiān)督矩陣）：64譯碼：表示成矩陣形式為：定義校驗矩陣（監(jiān)督矩陣）：25設(shè)接收碼組：定義伴隨式：已知：可得糾錯后的碼組C為：結(jié)論：以上方法構(gòu)成的線性分組碼中，能糾正單個錯誤的線性分組碼稱為漢明碼。65設(shè)接收碼組：定義伴隨式：已知：可得糾錯后的碼組C為：結(jié)論：以例9-2按照例9-1生成矩陣G，列出S與E的對照表。當收到碼組時，解出對應(yīng)的信息碼組D。

66例9-2按照例9-1生成矩陣G，列出S與E的對照表。當解：已知生成矩陣G為所以監(jiān)督矩陣H為67解：已知生成矩陣G為所以監(jiān)督矩陣H為28所以接收向量R不正確。68所以接收向量R不正確。29伴隨矩陣ST與監(jiān)督矩陣H的第二列相同。所以錯誤圖樣E為：69伴隨矩陣ST與監(jiān)督矩陣H的第二列相同。30線性分組碼的碼長n、信息位k和監(jiān)督位m之間應(yīng)滿足不等式：取等號時，為漢明碼，此時，有關(guān)系式：對于一般情況：70線性分組碼的碼長n、信息位k和監(jiān)督位m之間應(yīng)滿足不等式：取等漢明碼的編碼效率為：對于一般情況，校驗位數(shù)m應(yīng)滿足不等式：71漢明碼的編碼效率為：對于一般情況，校驗位數(shù)m應(yīng)滿足不等式：39.3循環(huán)碼 9.3.1循環(huán)碼的特點及表達： 循環(huán)性是指任一碼組循環(huán)一位后仍然是該編碼中的一個碼組。例：一種(7,3)循環(huán)碼的全部碼組如下 表中第2碼組向右移一位即得到第5碼組；第5碼組向右移一位即得到第7碼組。碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位A6a5a4a3a2a1a0a6a5a4A3a2a1a01000000051001011200101116101