第八章 差錯控制編碼

第八章差錯控制編碼8.1引言8.2差錯控制編碼的基本原理

8.3常用的簡單編碼8.4線性分組碼8.5循環(huán)碼8.6其它差錯控制編碼簡介數(shù)字編碼的兩種類型：1、信源編碼：提高有效性、信號如何數(shù)字化（PCM、DM等）2、信道編碼：為了降低誤碼，提高可靠性。8.1引言一、差錯控制編碼的目的二、傳輸中產(chǎn)生誤碼的原因1、隨機(jī)起伏噪聲：誤碼隨機(jī)、統(tǒng)計獨立（高斯白噪聲）2、突發(fā)干擾：誤碼集中出現(xiàn)（脈沖干擾、衰落）3、混合干擾：既有隨機(jī)誤碼又有突發(fā)誤碼。三、解決途徑5、采用信道編碼（差錯控制編碼）1、合理設(shè)計基帶信號傳輸碼型，2、合理選擇調(diào)制、解調(diào)方式，3、加大發(fā)送功率，4、采用頻域、時域均衡。1、檢錯重發(fā)法ARQ(AutomaticRepeatRequest)：四、差錯控制方法2、前向糾錯法FEC(ForwordErrorCorrection)3、反饋校驗法發(fā)收有錯碼無錯碼雙向信道發(fā)收是否有錯雙向信道效率低發(fā)收自己糾正單向信道設(shè)備復(fù)雜信源編碼器緩沖器重發(fā)控制雙向信道解碼器

指令產(chǎn)生

輸出緩沖

收信者正確時輸出錯誤時刪除4、混合糾錯法HEC(HybridErrorCorrection)圖1自動請求ARQ方框圖一、差錯控制編碼的基本概念：1、幾個名詞解釋：碼距：兩個碼字對應(yīng)位上數(shù)字不同的個數(shù)；（漢明距離）

例如11000與10011之間的距離d=3000、011、101、110（3，2）011的碼重為2， 000與011的碼距為2最小碼距：碼組集中各碼距的最小值。碼字：由若干個碼元組成的序列。例：1011001稱為一個碼字。結(jié)論：線性分組碼中，最小碼距等于最小碼重8.2差錯控制編碼的基本原理碼組：由多個碼字構(gòu)成的集合。例：{00,01,10,11}。碼重/漢明重量：碼字中“1”的個數(shù)；例：碼字10110，碼重w=3。2、差錯控制編碼的基本原理（1）舉例：發(fā)短信、天氣預(yù)報（3）基本原理：k位信息碼+r位監(jiān)督碼＝n位編碼。（4）編碼效率：η＝k/n=1-r/n。

若2個信息碼元中加1個監(jiān)督碼元，編碼效率2/3。（2）基本思想：在發(fā)送信息時，加入某種關(guān)聯(lián)性－某種約束關(guān)系。8.2差錯控制編碼的基本原理舉例：1、2位碼只能表示4種組合。00（晴）01（云）10（陰）11（雨）2、假如用3位二進(jìn)制數(shù)字來傳送這4種信息000（晴）011（云）101（陰）110（雨）接收端不能檢錯，也不能糾錯。那么，若任一組碼組有一個或多個發(fā)生錯碼，變成另一信息碼組。接收端此時有可能發(fā)現(xiàn)一個或三個錯碼，但不能發(fā)現(xiàn)兩個錯碼。返回（3）、基本原理：00（晴）01（云）10（陰）11（雨）000（晴）011（云）101（陰）110（雨）信息位監(jiān)督位信息碼加若干監(jiān)督碼的編碼集合，用表示。：信息碼元的數(shù)目，：碼組的總位數(shù)表示監(jiān)督碼元的數(shù)目其結(jié)構(gòu)為：信息碼+監(jiān)督碼返回二、最小碼距d0與糾錯能力的關(guān)系：8.2差錯控制編碼的基本原理1、重復(fù)碼：用來發(fā)送天氣預(yù)報

舉例：結(jié)論：糾錯能力與碼的位數(shù)有關(guān)。怎么樣的關(guān)系呢？(1)檢測e個隨機(jī)錯誤，則要求碼的最小距離d0≥e+1;(2)糾正t個隨機(jī)錯誤，則要求碼的最小距離d0≥2t+1;(3)糾正t個同時檢測e個隨機(jī)錯誤，則要求碼的最小距離d0≥t+e+1，(e>t)。2、最小碼距d0與糾錯能力的關(guān)系：三、差錯控制編碼的分類：從用途、監(jiān)督關(guān)系、碼字結(jié)構(gòu)、信息處理等方面分類舉例：1、2位碼只能表示4種組合。00（晴）01（云）10（陰）11（雨）2、假如用3位二進(jìn)制數(shù)字來傳送這4種信息000（晴）011（云）101（陰）110（雨）接收端不能檢錯，也不能糾錯。那么，若任一組碼組有一個或多個發(fā)生錯碼，變成另一信息碼組。接收端此時有可能發(fā)現(xiàn)一個或三個錯碼，但不能發(fā)現(xiàn)兩個錯碼。它只能檢測錯誤，而不能糾正錯誤。若要想能糾正錯誤，還要增加冗余度。000、101、110011接收端發(fā)送端錯一個錯三個100肯定出錯了（禁用碼組）000錯兩個011、110、101正確不能肯定出錯（許用碼組）3、若用3位碼表示2種信息，000（晴）111（雨）接收端此時有可能發(fā)現(xiàn)一個錯碼并能糾正它，或發(fā)現(xiàn)二個以下錯碼不能糾正，不能發(fā)現(xiàn)三個錯誤。000接收端發(fā)送端錯一個100肯定出錯了，且能糾錯（禁用碼組）A、若錯一位，則能確定發(fā)端的碼。000錯三個111正確不能肯定出錯B、若錯碼不超過二位，則不能確定發(fā)端的碼。000111接收端發(fā)送端錯一個錯兩個100肯定出錯了，不能糾錯返回8.3常用的簡單編碼1、奇偶監(jiān)督碼奇偶監(jiān)督碼可分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼，兩者的原理相同。（1）偶數(shù)監(jiān)督碼：監(jiān)督位只有一位，使得碼組中“1”的個數(shù)為偶數(shù)，即滿足為監(jiān)督位它能檢測奇數(shù)個錯碼，無糾錯能力。例收端：10011011，則可能發(fā)生了奇數(shù)個錯碼00011011、1101101101111011發(fā)端可能為錯一位錯三位（2）奇數(shù)監(jiān)督碼：監(jiān)督位也只有一位，使得碼組中“1”的個數(shù)為奇數(shù)，即滿足它也能檢測奇數(shù)個錯碼，無糾錯能力。編碼效率：(n-1)/n應(yīng)用：適用于一般隨機(jī)錯誤的檢測2、二維奇偶監(jiān)督碼行監(jiān)督列監(jiān)督碼組1）原理：2）舉例：3）檢錯能力：4）編碼效率：5）特點：適合檢測突發(fā)誤碼。3、恒比碼碼組中“1”（或“0”）的個數(shù)相同。也即它們的比保持恒定。接收端計算碼組中“1”的個數(shù)即可知道有無誤碼。優(yōu)點：適合用來傳輸電傳機(jī)或鍵盤設(shè)備產(chǎn)生的信息。舉例：5取3恒比碼－我國電傳機(jī)，7取3恒比碼－國際電傳電報2）舉例：4行7列信息組的水平垂直偶校驗碼為：發(fā)往線路順序：

01110010|00101011|01010110|10101010|10100101

第1字符

第2字符

第3字符

第4字符

偶校驗字符

返回4、正反碼（能糾正一位錯碼）1）、編碼規(guī)則：監(jiān)督位數(shù)與信息位數(shù)相同?！?”的個數(shù)決定監(jiān)督碼元是否與信息碼元相同或相反。舉例：電報通信（105)若有奇數(shù)個“1”，則監(jiān)督碼元與信息碼元相同若有偶數(shù)個“1”，則監(jiān)督碼元與信息碼元相反110011100110001011102）、解碼原理：A、信息位與監(jiān)督位按位模2加合成碼字校驗碼字B、合成碼字校驗碼字的規(guī)則若收到碼字的信息位有奇數(shù)個“1”，合成碼字就是校驗碼字若收到碼字的信息位有偶數(shù)個“1”，合成碼字的反碼是校驗碼字3）、由校驗碼字來檢錯糾錯：全“0”無錯碼4個“1”，1個“0”一位錯碼，其位置為校驗碼中“0”的位置一位錯碼，其位置為監(jiān)督碼中“1”的位置4個“0”，1個“1”其他錯碼多于一位8.4線性分組碼一、什么是線性分組碼？（1）封閉性：任何兩個許用碼字之和，仍為一許用碼字。2、兩個重要性質(zhì)分組碼:先給信息碼分組，然后給每組信息碼附加若干監(jiān)督碼的編碼。1、基本概念代數(shù)碼:建立在代數(shù)學(xué)基礎(chǔ)上的編碼。線性碼:信息位與監(jiān)督位由線性代數(shù)方程組聯(lián)系在一起。是代數(shù)碼線性分組碼:信息碼分組后，定長信息碼與監(jiān)督碼由線性代數(shù)方程組聯(lián)系在一起而形成的編碼。如漢明碼、循環(huán)碼等。（2）最小碼距＝最小碼重（全“0”碼除外）3、編碼效率二、線性分組碼的編碼原理2）若監(jiān)督位增加一位，有2個監(jiān)督關(guān)系式，校正因子有4種組合若1種代表無錯，其余3種可以用來指示錯碼的3個不同位置。S的值只有兩種，代表有錯和無錯兩種信息（檢錯）但不能指出錯碼的位置。（監(jiān)督關(guān)系式、校正因子）1）奇偶監(jiān)督碼中，接收端計算：3）若有r位監(jiān)督位，可以指示錯碼個不同位置1、一般原理結(jié)論：碼長n,信息位k,監(jiān)督位為r=n-k，若它能指示n個錯碼位置則：（或）舉例：（74）漢明碼r=3可以指示7個錯碼位置1）（74）應(yīng)該有3個校正因子，8種組合，7個錯碼位置信息位監(jiān)督位2）若錯碼位置010100011001110101111那么：3）正確的監(jiān)督關(guān)系為：4）可得16個許用碼字P222

表8-75）漢明碼還可糾錯例8-4-1二、線性分組碼的編碼原理2、監(jiān)督方程與監(jiān)督矩陣H3、生成方程與生成矩陣G監(jiān)督矩陣H單位方陣生成矩陣G結(jié)論：典型陣H的各行一定是線性無關(guān)的，非典型陣可以經(jīng)線性變換后化成典型陣。根據(jù)A?HT=0，用于接收端檢、糾錯典型陣典型陣二、線性分組碼的編碼原理4、監(jiān)督矩陣H與生成矩陣G的關(guān)系結(jié)論：生成矩陣的每一行都是碼字，利用生成矩陣G可以產(chǎn)生整個碼組，即三、線性分組碼的譯碼原理2、校正子S1、錯誤圖樣E3、結(jié)論接收碼元中只錯一位時，計算出的校正子S總是和典型陣H的某一列相同，可判斷錯誤發(fā)生在哪個碼元。（糾單個錯）例8-4-2P2258.5循環(huán)碼1、定義：是常用的線性分組碼，其檢、糾錯能力強(qiáng)，編譯碼設(shè)備不復(fù)雜的碼。有嚴(yán)密的代數(shù)理論基礎(chǔ)，以生成多項式作為收發(fā)雙方的約束關(guān)系。由于碼組內(nèi)任一碼字經(jīng)循環(huán)移位后仍為該碼組中的一個碼字，所以稱為循環(huán)碼。1）封閉性3、碼字多項式來表示碼字與碼字多項式有一一對應(yīng)關(guān)系表示方法：一、循環(huán)碼的基本概念2、特點：3）循環(huán)性：任一許用碼組經(jīng)循環(huán)移位后仍為一許用碼組。2）最小碼距等于最小碼重（全“0”碼除外）舉例：循環(huán)性：若T(x)是長為n的許用碼字多項式，則按模運算后，也是許用碼字多項式4、生成多項式是一個能整除xn+1且常數(shù)項為1的r（r=n-k)次多項式，是(n,k)循環(huán)碼集合中（除全“0”碼外）冪次最低的多項式，它有唯一性，由生成多項式可以產(chǎn)生循環(huán)碼的全部碼字。5、生成矩陣多項式G(x)、生成矩陣G由生成矩陣可以得到所有的循環(huán)碼字(n,k)循環(huán)碼中前（k-1)位都是0，那么…

都是碼字多項式，且線性無關(guān)。把這些多項式寫成矩陣的形式，即把系數(shù)寫成矩陣形式生成矩陣G(若非典型陣)典型陣G線性變換二、循環(huán)碼的編碼1）用乘。相當(dāng)于在信息碼元后面加個0；2）用除，得到商Q（x)和余式r(x)3）編出的碼組為11011000001100000+101=11001011、編碼步驟并發(fā)送4）舉例：已知（7，3）循環(huán)碼，m(x)=x2+x，g(x)=x4+x2+x+1，求經(jīng)CRC編碼后的發(fā)送碼字2、編碼電路的實現(xiàn)軟件－有延時，但成本低硬件－實時性強(qiáng)，但有設(shè)備成本編碼電路三、循環(huán)碼的譯碼收到碼多項式R(x)，用g(x)做除法，若r’(x)＝0，則無錯，否則有錯。1、譯碼原理舉例：P228

例8-5-22、譯碼電路的實現(xiàn)軟件－有延時，但成本低硬件－實時性強(qiáng)，但有設(shè)備成本由r’(x)找錯誤圖樣，最后糾錯。即：四、循環(huán)碼的檢查能力（1）可檢測出所有奇數(shù)位錯；（2）可檢測出所有雙比特錯；（3）可檢測出所有小于、等于校驗位長度的突發(fā)錯。結(jié)論：是一種檢糾錯能力和編碼效率達(dá)到最佳折中的編碼。在數(shù)據(jù)通信和計算機(jī)網(wǎng)絡(luò)中得到了廣泛應(yīng)用。五、幾種常用的CRC校驗碼生成多項式：8.6其它差錯控制編碼簡介8.6.1BCH碼1、何為BCH碼？

BCH碼是由博斯（Bose）、查德胡里（Chaudhuri）和霍昆格姆（Hocquenghem）名字的開頭字母命名的，有嚴(yán)密的代數(shù)理論，糾多個隨機(jī)錯的CRC碼。根據(jù)所要求的糾錯能力t，可求生成多項式g(x)，很容易構(gòu)造出BCH碼，譯碼也易實現(xiàn)。2、BCH碼分類－－本原BCH碼：①碼長為，m為正整數(shù)；②它的生成多項式由若干m階或以m階的因子為最高階的多項式相乘而構(gòu)成。

－－非本原BCH碼：①碼長是的一個因子；②它的生成多項式中不含有最高次數(shù)為m的本原多項式。

8.6.2卷積碼1、問題的提出：分組碼是把k個信息比特的序列編成n個比特的碼字，每個碼字的n-k個校驗位僅與本碼組的k個信息位有關(guān)，而與其他碼字無關(guān)。為了達(dá)到一定的糾錯能力和編碼效率，分組碼的碼字長度一般都比較大。是否有既要求n、k較小，又要求糾錯能力較強(qiáng)的編碼呢？