現(xiàn)代通信原理與技術(shù)第09章差錯控制編碼

1、第九章 差錯控制編碼9.1 引言9.2 糾錯編碼的基本原理9.3 常用的簡單編碼9.4 線性分組碼9.5 循環(huán)碼9.1 引言由于數(shù)字信號在傳輸過程中受到干擾的影響，使信號碼元波形變壞，故傳輸?shù)浇邮斩撕罂赡馨l(fā)生錯誤判決。由信道中乘性干擾引起的碼間干擾，通?？梢圆捎镁獾霓k法糾正，而加性干擾的影響則要從其它途徑解決。差錯控制編碼即是減少加性干擾造成錯誤判決的措施之一。信道編碼的主要原理：在傳輸信息的同時加入信息冗余，通過信息冗余來達到信道差錯控制的目的?；舅悸罚涸诎l(fā)送端將被傳輸?shù)男畔⒏郊由弦恍┍O(jiān)督碼元，多余的碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)（約束）。接收端按照既定的規(guī)則校驗信息碼元與監(jiān)

2、督碼元之間的關(guān)系，一旦傳輸發(fā)生差錯，則信息碼元與監(jiān)督碼元的關(guān)系就受到破壞，從而接收端可以發(fā)現(xiàn)錯誤乃至糾正錯誤。 錯誤的類型隨機錯誤：發(fā)生的位置是隨機的，而且數(shù)字序列中前后之間是否發(fā)生錯誤，彼此無關(guān)。多數(shù)情況下是獨立的單個數(shù)據(jù)發(fā)生錯誤。以隨機錯誤為主的信道稱為隨機信道 。突發(fā)錯誤：在一些短促的時間區(qū)間內(nèi)錯誤突發(fā)出現(xiàn)，密集成群，而在這些短促的時間區(qū)間之間卻又存在較長的無錯碼區(qū)間。以這種突發(fā)錯誤為主要錯誤形式的信道稱為突發(fā)信道。產(chǎn)生突發(fā)錯碼的主要原因之一是脈沖干擾，而信道中的衰落現(xiàn)象也是產(chǎn)生突發(fā)錯碼的另一主要原因。差錯控制方法檢錯重發(fā)法：接收端在收到的信碼中檢測出（發(fā)現(xiàn)）錯碼時，即設(shè)法通知發(fā)送端重發(fā)

3、，直到正確收到為止。前向糾錯法：接收端不僅能在收到的信碼中發(fā)現(xiàn)有錯碼，還能夠解定錯碼的位置，糾正錯碼。反饋校驗法：接收端將收到的信碼原封不動地轉(zhuǎn)發(fā)回發(fā)送端，發(fā)送端將其與原發(fā)送信碼比較，如果發(fā)現(xiàn)錯誤，則重發(fā)。自動要求重發(fā)系統(tǒng)ARQ系統(tǒng)（ Automatic Report reQuest）ARQ系統(tǒng)的三種工作過程差錯控制編碼分類 在信息碼元序列中加入監(jiān)督碼元就稱為差錯控制編碼，也稱為糾錯編碼。不同的編碼方法，有不同的檢錯或糾錯能力。一般地，編碼中增加的監(jiān)督碼元越多，檢（糾）錯的能力就越強。差錯控制編碼原則上是以降低信息傳輸速率為代價來換取傳輸可靠性的提高。 分 類： 功能不同分：檢錯碼、糾錯碼、和

4、糾刪碼； 信息碼元和附加的監(jiān)督碼元之間的檢驗關(guān)系分：線性碼和非線性碼； 信息碼元和監(jiān)督碼元之間的約束方式分：分組碼和卷積碼； 信息碼元在編碼后是否保持原來的形式不變分：系統(tǒng)碼和非系統(tǒng)碼； 糾正錯誤的類型分：糾正隨機錯誤碼和糾正突發(fā)錯誤碼； 編碼的數(shù)學(xué)方法分：代數(shù)碼、幾何碼和算術(shù)碼； 實例一： “明天14：0016：00開會” “明天10：0016：00開會” 改：“明天下午14：0016：00開會” “明天下午10：0016：00開會” 改：“明天下午14：0016：00兩個小時開會” 9.2 糾錯編碼的基本原理實例二：000(晴) 001(云) 010(陰) 011(雨) 100(雪) 10

5、1(霜) 110(霧) 111(雹)000(晴) 011(云) 101(陰) 110(雨)000(晴) 111(雨)二 糾錯碼的基本概念分組碼將輸入的信息分成不同的組，對各組信息分別獨立編碼，附加若干監(jiān)督碼的編碼集合，為分組碼。分組碼一般用符號(n,k)表示，其中k是每組二進信息碼元的數(shù)目，n是編碼組的總位數(shù)，又稱為碼組長度（碼長），n-k=r為每碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)目。分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組成長n的碼字。在二進制情況下，共有2k個不同的信息組，相應(yīng)地可得到2k個不同的碼字，稱為許用碼組；其余2n-2k個碼字未被選用，稱為禁用碼組。 an-1

6、an-2 ar ar-1 a0k個信息位r個監(jiān)督位碼長n=k+r在分組碼中，碼組（碼字或碼矢）中碼元的數(shù)目，稱為碼組的長度（簡稱碼長）；碼組中把“1”的數(shù)目（即非0的數(shù)目）稱為碼組的重量（簡稱碼重）； 碼長、碼重和碼距 碼長、碼重和碼距 在分組碼中，把“1”的數(shù)目稱為碼組的重量，而把兩個碼組對應(yīng)位上數(shù)字不同的位數(shù)稱為碼組的距離，簡稱碼距，又稱漢明(Hamming)距離。某種編碼中各個碼組間距離的最小值稱為最小碼距（d0）。三 檢錯、糾錯能力任一(n,k)分組碼，若要在碼字內(nèi)： 檢測e個隨機錯誤，則要求碼的最小距離 ； 糾正t個隨機錯誤，則要求碼的最小距離 ； 糾正t個同時檢測e( )個隨機錯誤

7、，則要求碼的最小距離 ； 10 ed120 tdte 10etd碼距與檢錯和糾錯能力的關(guān)系四 編碼效率編碼效率R來衡量有效性：對糾錯碼的要求：檢錯和糾錯能力盡量強；編碼效率盡量高；編碼規(guī)律盡量簡單。 nkR 9.3 常用的幾種簡單分組碼 奇偶監(jiān)督碼二維奇偶監(jiān)督碼恒比碼正反碼9.3.1 奇偶監(jiān)督碼奇偶監(jiān)督碼可分為奇監(jiān)督碼和偶監(jiān)督碼兩種，兩者的原理相同。在偶(奇)數(shù)監(jiān)督碼中，無論信息位有多少 ，監(jiān)督位只有一位，它使碼組中“1”的個數(shù)為偶(奇)數(shù)，即滿足 an-1 an-2 a0=0(1) 式中a0為監(jiān)督位，其它為信息位。在接收端，將碼組中各碼元模2加，若結(jié)果為“1”(“0”)就說明存在錯碼，為“0

8、”(“1”)就認(rèn)為無錯。9.3.2 二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼又稱方陣碼。它是把奇偶監(jiān)督碼的若干碼組排列成矩陣，每一碼組寫成一行，然后再按列的方向增加第二維監(jiān)督位。9.3.3 恒比碼（等重碼或定1碼） 在恒比碼中，每個碼組均含有相同數(shù)目的“1”（和“0”）。由于“1”的數(shù)目和“0”的數(shù)目之比保持恒定，故得此名。這種碼在檢測時，只要計算接收碼組中“1”的數(shù)目是否對，就知道有無錯誤。恒比碼的主要優(yōu)點是簡單和適于用來傳輸電傳機或其它鍵盤設(shè)備產(chǎn)生的字母和符號。對于信源來的二進隨機數(shù)字序列，這種碼就不適合使用了。 “5中取3”恒比碼：（我國電傳通信中用） 阿拉伯?dāng)?shù)字保護電碼國際電碼阿拉伯?dāng)?shù)字保護電碼國

9、際電碼123450101111001101101101000111111011100110000010100000167890101011110001110100110110110101111000110000011011019.3.4 正反碼正反碼是一種簡單的能夠糾正錯碼的編碼。其監(jiān)督位數(shù)目與信息位數(shù)目相同，監(jiān)督碼元與信息碼元相同（是信息碼的重復(fù)）或者相反（是信息碼的反碼），則由信息碼中“1”的個數(shù)而定。長度為10的正反碼具得糾正一位錯碼的能力，并能檢測全部兩位以下的錯碼和大部分兩位以上的錯碼。9.3.5 ISBN國際統(tǒng)一圖書編號 國內(nèi)外出版的圖書封底右下角印有諸如ISBN 0-1315-2

10、447-X形式的國際統(tǒng)一圖書編號，這種編號也是一種檢錯碼。第一位數(shù)字是國家代碼，“0”美國及其他英語國家出版物；“7”中國；“1315”代表出版公司；“2447”代表書名編號；“X（羅馬字）”校驗位。 9.4 線性分組碼線性分組碼，是指信息位和監(jiān)督位滿足一組線性方程，即其編碼規(guī)則可用一組線性方程來描述的分組碼。線性碼有一個重要性質(zhì)，就是它具有封閉性。即線性碼中的任意兩個碼組之各仍為該碼中的一個碼組。線性碼又稱群碼。一 基本概念在(n,k)線性分組碼中，每一個監(jiān)督元都是碼組中某些信息元按模2和而得到。例（7，4）分組碼，設(shè)其碼字為A=a6 a5 a4 a3 a2 a1 a0，其中前4位是信息元，

11、后3位是監(jiān)督元，可用下列線性方程組描述該分組碼，產(chǎn)生監(jiān)督元。 346035614562aaaaaaaaaaaa經(jīng)計算可得（7，4）碼的全部碼字 。表91 （7，4）碼的碼字表 序號碼 字序號碼 字信 息 元監(jiān) 督 元信 息 元 監(jiān) 督 元00 0 0 00 0 081 0 0 01 1 110 0 0 10 1 191 0 0 11 0 020 0 1 01 0 1101 0 1 00 1 030 0 1 11 1 0111 0 1 10 0 140 1 0 01 1 0121 1 0 00 0 150 1 0 11 0 1131 1 0 10 1 060 1 1 00 1 1141 1 1

12、01 0 070 1 1 10 0 0151 1 1 11 1 1二 監(jiān)督矩陣H和生成矩陣G1 監(jiān)督矩陣H： 設(shè)（7，4）漢明碼的碼字它有三個監(jiān)督元，可建立三個互相獨立的監(jiān)督關(guān)系式： 0123456aaaaaaaA 000034613562456aaaaaaaaaaaa 矩陣形式： 0001001101010101100101110123456aaaaaaaTTAH00THA簡記為： 或： 其中 是A的轉(zhuǎn)置， 是 的轉(zhuǎn)置， 是H的轉(zhuǎn)置； 稱為（7，4）漢明碼的監(jiān)督矩陣。(n,k)線性分組碼的監(jiān)督矩陣H由r行n列組成，這r行是線性無關(guān)的。 TAT00000 TH10011010101011001

13、0111H系統(tǒng)碼的監(jiān)督矩陣可寫成如下形式： 稱為典型監(jiān)督矩陣。是r*r的單位矩陣，p是r*k的矩陣。上監(jiān)督矩陣H有： 100110101010110010111rIpHrpIH 110110110111p2 生成矩陣G：若將監(jiān)督方程補充為下列方程：346035614562445566aaaaaaaaaaaaaaaaaa345601234561101101101111000010000100001aaaaaaaaaaa其中，TTTaaaaGA3456GaaaaA3456變換為： 1101000101010001100101110001G = 稱為生成矩陣。由生成矩陣及信息組可產(chǎn)生出全部碼字。G由

14、K行n列組成，每一行是一個碼字，K行線性無關(guān)。系統(tǒng)碼的生成矩陣可寫成： 稱為典型生成矩陣。由典型生成矩陣得出的碼組A中，信息位不變，監(jiān)督位附加于其后，這種碼稱為系統(tǒng)碼。 TkkPIQIG三 伴隨式（校正子）S設(shè)發(fā)送碼組接收碼組則發(fā)送碼組和接收碼組之差為：它是傳輸中產(chǎn)生的錯碼行矩陣：其中： 0121aaaaAnn0121bbbbBnn)2(模EAB0121eeeeEnniiiiiababe當(dāng)當(dāng), 1, 0可寫成： 。令 ，稱為伴隨式或校正子。由于E為1*n，為n*r矩陣，所以S為1*r的矩陣，即r列的行矩陣： EABTBHS TTTTTEHEHAHHEABHS)(0121ssssSnn按照上述方

15、法構(gòu)造的糾正單個錯誤的線性分組碼稱為漢明碼。其特點：碼長：信息碼位： 監(jiān)督碼位：r=n-k=m；最小碼距：d0=3；糾錯能力：t=1。 12mn12mkm漢明碼的編碼效率：漢明碼能糾正一個錯碼，則要求： 2r-1 n 或2r k+r+1漢明碼的編碼效率等于：K/n=(2r-1-r)/(2r-1)=1-r/(2r-1)=1-r/n可見，漢明碼是一種高效碼。四 系統(tǒng)碼與非系統(tǒng)碼設(shè)信息位為 ，若編碼后的碼組為： ，其中， 是監(jiān)督位，則稱這種碼為系統(tǒng)碼。即系統(tǒng)碼經(jīng)過編碼后的碼組中前k個是信息位，后n-k是監(jiān)督位。若不存在上述關(guān)系，則稱為非系統(tǒng)碼。knnnaaa210121aaaaaknknnn01aa

16、knTPQ 0TGH只有系統(tǒng)碼才有關(guān)系：系統(tǒng)碼和非系統(tǒng)碼均有：。 9.5 循 環(huán) 碼一 定義及特點 循環(huán)碼是一類特殊的線性分組碼，特點是循環(huán)性。所謂循環(huán)碼（Cyclic Code）就是任何一個碼字循環(huán)右移一位后所得到的仍是一個合法碼字，也就是說這個碼在循環(huán)位移運算下具有封閉性。在代數(shù)理論中，常用碼多項式表示碼字。(n,k)循環(huán)碼的碼字，其碼多項式（以降冪順序排列）： 012211)(axaxaxaxAnnnn例1 （7，3）循環(huán)碼：序號 碼 字0123456700001111001100110101010101011010011010010011110001100110例2 （7，3）循環(huán)碼碼

17、組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010（7，3）循環(huán)碼00000000010111100101111001011110010 01011101011100 0111001二 生成多項式及生成矩陣 若一種碼的所有碼多項式都是多項式g(x)的倍式，則稱g(x)為該碼的生成多項式。在(n,k)循環(huán)碼中任意碼多項式A(x)都是最低次碼倍式。因此，循環(huán)碼中次數(shù)最低的多項式（全0碼字除外）就是生成多項式g(x)?？梢宰C明，g

18、(x)是常數(shù)項為1的r=n-k次多項式，是xn+1的一個因式。 循環(huán)碼的生成矩陣常用多項式的形式來表示： )()()()()(21xgxxgxgxxgxxGkk1)(111xgxgxxgrrr其中 例:（7，3）循環(huán)碼，n=7，k=3，r=4，其生成多項式及生成矩陣分別為： 1)()(2341xxxxAxg1)()()()(23434524562xxxxxxxxxxxxgxxgxgxxG101110001011100010111G三 監(jiān)督多項式及監(jiān)督矩陣監(jiān)督多項式定義：其中，g(x)是常數(shù)項為1的r次多項式，是生成多項式；h(x)是常數(shù)項為1的k次多項式； 1)()(1111xhxhxxgxx

19、hkkkn監(jiān)督矩陣H定義： )()()()()(*2*1xhxxhxhxxhxxHknkn1)(12211*xhxhxhxxhkkkk是h(x)的逆多項式； 例：（7，3）循環(huán)碼， 1)(234xxxxg則： 1)(1)(237xxxgxxh1)(3*xxxh1)(324235346xxxxxxxxxxxxH1101000011010000110100001101H即：四 循環(huán)碼的編碼方法和電路1 循環(huán)碼的編碼方法根據(jù)給定的(n,k)值選定生成多項式g(x)，即應(yīng)在xn+1的因式中選一r=n-k次多項式作為g(x)。設(shè)m(x)為信息碼多項式，其次數(shù)小于k； 12231)(axaxaxaxmkk編碼步驟：（1）用xn-k乘m(x)；（2）用g(x)除xn-km(x) ，得到商Q(x)和余式r(x)，即： ，將余式r(x)加于信息位之后作為監(jiān)督位，得到的多項式必為一碼多項式；（3）編出的碼組： T(x)= xn-km(x)+r(x) )()()()()(xgxrxQxgxmxkn例：（7，3）碼編碼器：2 循環(huán)碼的解碼方法 接收端譯碼的目的是檢錯和糾錯。檢錯：將接收碼組R(x)用原生成多項式g(x)去除，以余式r(x)是否為零判別碼組中有無錯碼。糾錯：（1）用生成多項式g(x)除接收碼組R(x)，得出余項