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

第九章差錯控制編碼9.1引言9.2糾錯編碼的基本原理9.3常用的簡單編碼9.4線性分組碼9.5循環(huán)碼第九章差錯控制編碼9.1引言19.1引言由于數(shù)字信號在傳輸過程中受到干擾的影響，使信號碼元波形變壞，故傳輸?shù)浇邮斩撕罂赡馨l(fā)生錯誤判決。由信道中乘性干擾引起的碼間干擾，通?？梢圆捎镁獾霓k法糾正，而加性干擾的影響則要從其它途徑解決。差錯控制編碼即是減少加性干擾造成錯誤判決的措施之一。9.1引言由于數(shù)字信號在傳輸過程中受到干擾的影響，使信號碼2信道編碼的主要原理：在傳輸信息的同時加入信息冗余，通過信息冗余來達到信道差錯控制的目的?；舅悸罚涸诎l(fā)送端將被傳輸?shù)男畔⒏郊由弦恍┍O(jiān)督碼元，多余的碼元與信息碼元之間以某種確定的規(guī)則相互關聯(lián)（約束）。接收端按照既定的規(guī)則校驗信息碼元與監(jiān)督碼元之間的關系，一旦傳輸發(fā)生差錯，則信息碼元與監(jiān)督碼元的關系就受到破壞，從而接收端可以發(fā)現(xiàn)錯誤乃至糾正錯誤。信道編碼的主要原理：在傳輸信息的同時加入信息冗余，通過信息冗3錯誤的類型隨機錯誤：發(fā)生的位置是隨機的，而且數(shù)字序列中前后之間是否發(fā)生錯誤，彼此無關。多數(shù)情況下是獨立的單個數(shù)據(jù)發(fā)生錯誤。以隨機錯誤為主的信道稱為隨機信道。突發(fā)錯誤：在一些短促的時間區(qū)間內(nèi)錯誤突發(fā)出現(xiàn)，密集成群，而在這些短促的時間區(qū)間之間卻又存在較長的無錯碼區(qū)間。以這種突發(fā)錯誤為主要錯誤形式的信道稱為突發(fā)信道。產(chǎn)生突發(fā)錯碼的主要原因之一是脈沖干擾，而信道中的衰落現(xiàn)象也是產(chǎn)生突發(fā)錯碼的另一主要原因。錯誤的類型隨機錯誤：發(fā)生的位置是隨機的，而且數(shù)字序列中前后之4差錯控制方法檢錯重發(fā)法：接收端在收到的信碼中檢測出（發(fā)現(xiàn)）錯碼時，即設法通知發(fā)送端重發(fā)，直到正確收到為止。前向糾錯法：接收端不僅能在收到的信碼中發(fā)現(xiàn)有錯碼，還能夠解定錯碼的位置，糾正錯碼。反饋校驗法：接收端將收到的信碼原封不動地轉(zhuǎn)發(fā)回發(fā)送端，發(fā)送端將其與原發(fā)送信碼比較，如果發(fā)現(xiàn)錯誤，則重發(fā)。差錯控制方法檢錯重發(fā)法：接收端在收到的信碼中檢測出（發(fā)現(xiàn)）錯5自動要求重發(fā)系統(tǒng)——ARQ系統(tǒng)（AutomaticReportreQuest）自動要求重發(fā)系統(tǒng)——ARQ系統(tǒng)（AutomaticRe6ARQ系統(tǒng)的三種工作過程ARQ系統(tǒng)的三種工作過程7差錯控制編碼分類?在信息碼元序列中加入監(jiān)督碼元就稱為差錯控制編碼，也稱為糾錯編碼。不同的編碼方法，有不同的檢錯或糾錯能力。一般地，編碼中增加的監(jiān)督碼元越多，檢（糾）錯的能力就越強。?差錯控制編碼原則上是以降低信息傳輸速率為代價來換取傳輸可靠性的提高。差錯控制編碼分類?在信息碼元序列中加入監(jiān)督碼元就稱為差錯控8分類：功能不同分：檢錯碼、糾錯碼、和糾刪碼；信息碼元和附加的監(jiān)督碼元之間的檢驗關系分：線性碼和非線性碼；信息碼元和監(jiān)督碼元之間的約束方式分：分組碼和卷積碼；信息碼元在編碼后是否保持原來的形式不變分：系統(tǒng)碼和非系統(tǒng)碼；糾正錯誤的類型分：糾正隨機錯誤碼和糾正突發(fā)錯誤碼；編碼的數(shù)學方法分：代數(shù)碼、幾何碼和算術碼；

分類：9實例一：“明天14：00~16：00開會”“明天10：00~16：00開會”改：“明天下午14：00~16：00開會”“明天下午10：00~16：00開會”改：“明天下午14：00~16：00兩個小時開會”9.2糾錯編碼的基本原理實例一：9.2糾錯編碼的基本原理10實例二：000(晴)001(云)010(陰)011(雨)100(雪)101(霜)110(霧)111(雹)000(晴)011(云)101(陰)110(雨)000(晴)111(雨)實例二：000(晴)001(云)010(陰)011(雨11二糾錯碼的基本概念

分組碼將輸入的信息分成不同的組，對各組信息分別獨立編碼，附加若干監(jiān)督碼的編碼集合，為分組碼。分組碼一般用符號(n,k)表示，其中k是每組二進信息碼元的數(shù)目，n是編碼組的總位數(shù)，又稱為碼組長度（碼長），n-k=r為每碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)目。二糾錯碼的基本概念

分組碼將輸入的信息分成不同的組，對各12分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組成長n的碼字。在二進制情況下，共有2k個不同的信息組，相應地可得到2k個不同的碼字，稱為許用碼組；其余2n-2k個碼字未被選用，稱為禁用碼組。an-1an-2…arar-1…a0k個信息位r個監(jiān)督位碼長n=k+r分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組成13在分組碼中，碼組（碼字或碼矢）中碼元的數(shù)目，稱為碼組的長度（簡稱碼長）；碼組中把“1”的數(shù)目（即非0的數(shù)目）稱為碼組的重量（簡稱碼重）；碼長、碼重和碼距

在分組碼中，碼組（碼字或碼矢）中碼元的數(shù)目，稱為碼組的長度（14碼長、碼重和碼距

在分組碼中，把“1”的數(shù)目稱為碼組的重量，而把兩個碼組對應位上數(shù)字不同的位數(shù)稱為碼組的距離，簡稱碼距，又稱漢明(Hamming)距離。某種編碼中各個碼組間距離的最小值稱為最小碼距（d0）。碼長、碼重和碼距在分組碼中，把“1”的數(shù)目稱為碼組的重量，15三檢錯、糾錯能力任一(n,k)分組碼，若要在碼字內(nèi)：檢測e個隨機錯誤，則要求碼的最小距離；糾正t個隨機錯誤，則要求碼的最小距離；糾正t個同時檢測e()個隨機錯誤，則要求碼的最小距離；三檢錯、糾錯能力任一(n,k)分組碼，若要在碼字內(nèi)：16碼距與檢錯和糾錯能力的關系碼距與檢錯和糾錯能力的關系17四編碼效率編碼效率R來衡量有效性：對糾錯碼的要求：檢錯和糾錯能力盡量強；編碼效率盡量高；編碼規(guī)律盡量簡單。四編碼效率編碼效率R來衡量有效性：189.3常用的幾種簡單分組碼

奇偶監(jiān)督碼二維奇偶監(jiān)督碼恒比碼正反碼9.3常用的幾種簡單分組碼奇偶監(jiān)督碼199.3.1奇偶監(jiān)督碼奇偶監(jiān)督碼可分為奇監(jiān)督碼和偶監(jiān)督碼兩種，兩者的原理相同。在偶(奇)數(shù)監(jiān)督碼中，無論信息位有多少，監(jiān)督位只有一位，它使碼組中“1”的個數(shù)為偶(奇)數(shù)，即滿足an-1an-2…a0=0(1)式中a0為監(jiān)督位，其它為信息位。在接收端，將碼組中各碼元模2加，若結(jié)果為“1”(“0”)就說明存在錯碼，為“0”(“1”)就認為無錯。9.3.1奇偶監(jiān)督碼奇偶監(jiān)督碼可分為奇監(jiān)督碼和偶監(jiān)督碼兩種209.3.2二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼又稱方陣碼。它是把奇偶監(jiān)督碼的若干碼組排列成矩陣，每一碼組寫成一行，然后再按列的方向增加第二維監(jiān)督位。9.3.2二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼又稱方陣碼。它是把奇219.3.3恒比碼（等重碼或定1碼）

在恒比碼中，每個碼組均含有相同數(shù)目的“1”（和“0”）。由于“1”的數(shù)目和“0”的數(shù)目之比保持恒定，故得此名。這種碼在檢測時，只要計算接收碼組中“1”的數(shù)目是否對，就知道有無錯誤。恒比碼的主要優(yōu)點是簡單和適于用來傳輸電傳機或其它鍵盤設備產(chǎn)生的字母和符號。對于信源來的二進隨機數(shù)字序列，這種碼就不適合使用了。9.3.3恒比碼（等重碼或定1碼）在恒比碼中，每個碼組均22

“5中取3”恒比碼：（我國電傳通信中用）

阿拉伯數(shù)字保護電碼國際電碼阿拉伯數(shù)字保護電碼國際電碼12345010111100110110110100011111101110011000001010000016789010101111000111010011011011010111100011000001101101“5中取3”恒比碼：（我國電傳通信中用）阿拉伯數(shù)字保護電239.3.4正反碼正反碼是一種簡單的能夠糾正錯碼的編碼。其監(jiān)督位數(shù)目與信息位數(shù)目相同，監(jiān)督碼元與信息碼元相同（是信息碼的重復）或者相反（是信息碼的反碼），則由信息碼中“1”的個數(shù)而定。長度為10的正反碼具得糾正一位錯碼的能力，并能檢測全部兩位以下的錯碼和大部分兩位以上的錯碼。9.3.4正反碼正反碼是一種簡單的能夠糾正錯碼的編碼。249.3.5ISBN國際統(tǒng)一圖書編號

國內(nèi)外出版的圖書封底右下角印有諸如ISBN0-1315-2447-X形式的國際統(tǒng)一圖書編號，這種編號也是一種檢錯碼。第一位數(shù)字是國家代碼，“0”——美國及其他英語國家出版物；“7”——中國；“1315”——代表出版公司；“2447”——代表書名編號；“X（羅馬字）”——校驗位。9.3.5ISBN國際統(tǒng)一圖書編號國內(nèi)外出版的圖書封底右259.4線性分組碼線性分組碼，是指信息位和監(jiān)督位滿足一組線性方程，即其編碼規(guī)則可用一組線性方程來描述的分組碼。線性碼有一個重要性質(zhì)，就是它具有封閉性。即線性碼中的任意兩個碼組之各仍為該碼中的一個碼組。線性碼又稱群碼。9.4線性分組碼線性分組碼，是指信息位和監(jiān)督位滿足一組線性26一基本概念在(n,k)線性分組碼中，每一個監(jiān)督元都是碼組中某些信息元按模2和而得到。例（7，4）分組碼，設其碼字為A=[a6a5a4a3a2a1a0]，其中前4位是信息元，后3位是監(jiān)督元，可用下列線性方程組描述該分組碼，產(chǎn)生監(jiān)督元。一基本概念在(n,k)線性分組碼中，每一個監(jiān)督元都是碼組中27經(jīng)計算可得（7，4）碼的全部碼字。表9—1（7，4）碼的碼字表

序號碼字序號碼字信息元監(jiān)督元信息元監(jiān)督元00000000810001111000101191001100200101011010100103001111011101100140100110121100001501011011311010106011001114111010070111000151111111經(jīng)計算可得（7，4）碼的全部碼字。序碼字序碼28二監(jiān)督矩陣H和生成矩陣G1監(jiān)督矩陣H：設（7，4）漢明碼的碼字它有三個監(jiān)督元，可建立三個互相獨立的監(jiān)督關系式：二監(jiān)督矩陣H和生成矩陣G1監(jiān)督矩陣H：29

矩陣形式：

簡記為：或：

矩陣形式：簡記為：或：30

其中是A的轉(zhuǎn)置，是的轉(zhuǎn)置，是H的轉(zhuǎn)置；稱為（7，4）漢明碼的監(jiān)督矩陣。(n,k)線性分組碼的監(jiān)督矩陣H由r行n列組成，這r行是線性無關的。其中是A的轉(zhuǎn)置，是的31系統(tǒng)碼的監(jiān)督矩陣可寫成如下形式：稱為典型監(jiān)督矩陣。是r*r的單位矩陣，p是r*k的矩陣。上監(jiān)督矩陣H有：系統(tǒng)碼的監(jiān)督矩陣可寫成如下形式：322生成矩陣G：若將監(jiān)督方程補充為下列方程：2生成矩陣G：若將監(jiān)督方程補充為下列方程：33其中，變換為：

G=

其中，變換為：G=34稱為生成矩陣。由生成矩陣及信息組可產(chǎn)生出全部碼字。G由K行n列組成，每一行是一個碼字，K行線性無關。系統(tǒng)碼的生成矩陣可寫成：稱為典型生成矩陣。由典型生成矩陣得出的碼組A中，信息位不變，監(jiān)督位附加于其后，這種碼稱為系統(tǒng)碼。稱為生成矩陣。由生成矩陣及信息組可產(chǎn)生出全部碼字。G由K行35三伴隨式（校正子）S設發(fā)送碼組接收碼組則發(fā)送碼組和接收碼組之差為：它是傳輸中產(chǎn)生的錯碼行矩陣：其中：三伴隨式（校正子）S設發(fā)送碼組36可寫成：。令，稱為伴隨式或校正子。由于E為1*n，為n*r矩陣，所以S為1*r的矩陣，即r列的行矩陣：可寫成：。令37按照上述方法構造的糾正單個錯誤的線性分組碼稱為漢明碼。其特點：碼長：信息碼位：監(jiān)督碼位：r=n-k=m；最小碼距：d0=3；糾錯能力：t=1。

按照上述方法構造的糾正單個錯誤的線性分組碼稱為漢明碼。其特點38漢明碼的編碼效率：?漢明碼能糾正一個錯碼，則要求：2r-1≥n或2r≥k+r+1?漢明碼的編碼效率等于：K/n=(2r-1-r)/(2r-1)=1-r/(2r-1)=1-r/n?可見，漢明碼是一種高效碼。漢明碼的編碼效率：39四系統(tǒng)碼與非系統(tǒng)碼設信息位為，若編碼后的碼組為：，其中，是監(jiān)督位，則稱這種碼為系統(tǒng)碼。即系統(tǒng)碼經(jīng)過編碼后的碼組中前k個是信息位，后n-k是監(jiān)督位。若不存在上述關系，則稱為非系統(tǒng)碼。四系統(tǒng)碼與非系統(tǒng)碼設信息位為40只有系統(tǒng)碼才有關系：系統(tǒng)碼和非系統(tǒng)碼均有：。

只有系統(tǒng)碼才有關系：系統(tǒng)碼和非系統(tǒng)碼均有：。419.5循環(huán)碼一定義及特點循環(huán)碼是一類特殊的線性分組碼，特點是循環(huán)性。所謂循環(huán)碼（CyclicCode）就是任何一個碼字循環(huán)右移一位后所得到的仍是一個合法碼字，也就是說這個碼在循環(huán)位移運算下具有封閉性。在代數(shù)理論中，常用碼多項式表示碼字。(n,k)循環(huán)碼的碼字，其碼多項式（以降冪順序排列）：9.5循環(huán)碼一定義及特點42例1（7，3）循環(huán)碼：序號碼字0123456700001111001100110101010101011010011010010011110001100110例1（7，3）循環(huán)碼：序碼字43例2（7，3）循環(huán)碼碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010例2（7，3）循環(huán)碼碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督44（7，3）循環(huán)碼0000000→0010111→1001011→1100101→1110010—0101110←1011100←0111001←（7，3）循環(huán)碼0000000→45二生成多項式及生成矩陣

若一種碼的所有碼多項式都是多項式g(x)的倍式，則稱g(x)為該碼的生成多項式。在(n,k)循環(huán)碼中任意碼多項式A(x)都是最低次碼倍式。因此，循環(huán)碼中次數(shù)最低的多項式（全0碼字除外）就是生成多項式g(x)?？梢宰C明，g(x)是常數(shù)項為1的r=n-k次多項式，是xn+1的一個因式。

二生成多項式及生成矩陣若一種碼的所有碼多項式都是多項式46循環(huán)碼的生成矩陣常用多項式的形式來表示：其中

循環(huán)碼的生成矩陣常用多項式的形式來表示：其中47例:（7，3）循環(huán)碼，n=7，k=3，r=4，其生成多項式及生成矩陣分別為：例:（7，3）循環(huán)碼，n=7，k=3，r=4，其生成多項式及48三監(jiān)督多項式及監(jiān)督矩陣監(jiān)督多項式定義：其中，g(x)是常數(shù)項為1的r次多項式，是生成多項式；h(x)是常數(shù)項為1的k次多項式；

三監(jiān)督多項式及監(jiān)督矩陣監(jiān)督多項式定義：49監(jiān)督矩陣H定義：

是h(x)的逆多項式；

監(jiān)督矩陣H定義：是h(x)的逆多項式；50例：（7，3）循環(huán)碼，

則：

即：例：（7，3）循環(huán)碼，則：即：51四循環(huán)碼的編碼方法和電路1循環(huán)碼的編碼方法根據(jù)給定的(n,k)值選定生成多項式g(x)，即應在xn+1的因式中選一r=n-k次多項式作為g(x)。?設m(x)為信息碼多項式，其次數(shù)小于k；四循環(huán)碼的編碼方法和電路1循環(huán)碼的編碼方法52編碼步驟：（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)編碼步驟：53例：（7，3）碼編碼器：例：（7，3）碼編碼器：542循環(huán)碼的解碼方法接收端譯碼的目的是檢錯和糾錯。?檢錯：將接收碼組R(x)用原生成多項式g(x)去除，以余式r(x)是否為零判別碼組中有無錯碼。?糾錯：（1）用生成多項式g(x)除接收碼組R(x)，得出余項r(x)；（2）按余式用查表的方法或通過某種運算確定錯碼位置；（3）糾正錯碼。2循環(huán)碼的解碼方法接收端譯碼的目的是檢錯和糾錯。55循環(huán)碼的糾檢錯能力：?已知循環(huán)碼由g(x)生成，所以g(x)就決定了由它生成的循環(huán)碼的糾檢錯能力。?循環(huán)碼有著極強的糾檢錯能力，在通信和計算機系統(tǒng)中有著廣泛的應用。循環(huán)碼的糾檢錯能力：56結(jié)論1：若生成多項式g(x)的項數(shù)大于1，則由其所生成的循環(huán)碼能夠檢測所有的單個錯誤。結(jié)論2：若生成多項式g(x)含有因式(1+x)，則由其生成的循環(huán)碼能夠檢測所有奇數(shù)個錯誤。結(jié)論3：若碼長n不大于g(x)的周期l，則由g(x)所生成的循環(huán)碼能檢測所有單個錯誤和兩個錯誤，即dmin≥3，或者說至少能夠糾正所有單個錯誤。結(jié)論1：57?所謂多項式的周期，就是使該多項式能夠除得盡xl+1的最小正整數(shù)l。如果多項式的次數(shù)為r，且其周期l=2r-1，則稱該多項式為本原多項式。結(jié)論4：設g(x)的次數(shù)為r，則由g(x)所生成的循環(huán)碼能夠檢測長度b≤r的突發(fā)錯誤。?所謂多項式的周期，就是使該多項式能夠除得盡xl+1的最小正583常用的循環(huán)碼①國際電報電話咨詢委員會（CCITT）推薦的CRC-CCITT，用于8單位國際5號字母表傳輸時，用生成多項式g(x)=x16+x12+x5+1生成循環(huán)碼。②美國二進制同步系統(tǒng)中采用CRC-16，生成多項式為g(x)=x16+x15+x2+1，用于8單位碼傳輸檢錯；采用CRC-12，生成多項式為g(x)=x12+x11+x3+x2+x+1，用于6單位碼傳輸檢錯。3常用的循環(huán)碼59③局域網(wǎng)中廣泛應用的CRC-32，生成多項式為g(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1。③局域網(wǎng)中廣泛應用的CRC-32，生成多項式為g(x)=x360第九章差錯控制編碼9.1引言9.2糾錯編碼的基本原理9.3常用的簡單編碼9.4線性分組碼9.5循環(huán)碼第九章差錯控制編碼9.1引言619.1引言由于數(shù)字信號在傳輸過程中受到干擾的影響，使信號碼元波形變壞，故傳輸?shù)浇邮斩撕罂赡馨l(fā)生錯誤判決。由信道中乘性干擾引起的碼間干擾，通?？梢圆捎镁獾霓k法糾正，而加性干擾的影響則要從其它途徑解決。差錯控制編碼即是減少加性干擾造成錯誤判決的措施之一。9.1引言由于數(shù)字信號在傳輸過程中受到干擾的影響，使信號碼62信道編碼的主要原理：在傳輸信息的同時加入信息冗余，通過信息冗余來達到信道差錯控制的目的。基本思路：在發(fā)送端將被傳輸?shù)男畔⒏郊由弦恍┍O(jiān)督碼元，多余的碼元與信息碼元之間以某種確定的規(guī)則相互關聯(lián)（約束）。接收端按照既定的規(guī)則校驗信息碼元與監(jiān)督碼元之間的關系，一旦傳輸發(fā)生差錯，則信息碼元與監(jiān)督碼元的關系就受到破壞，從而接收端可以發(fā)現(xiàn)錯誤乃至糾正錯誤。信道編碼的主要原理：在傳輸信息的同時加入信息冗余，通過信息冗63錯誤的類型隨機錯誤：發(fā)生的位置是隨機的，而且數(shù)字序列中前后之間是否發(fā)生錯誤，彼此無關。多數(shù)情況下是獨立的單個數(shù)據(jù)發(fā)生錯誤。以隨機錯誤為主的信道稱為隨機信道。突發(fā)錯誤：在一些短促的時間區(qū)間內(nèi)錯誤突發(fā)出現(xiàn)，密集成群，而在這些短促的時間區(qū)間之間卻又存在較長的無錯碼區(qū)間。以這種突發(fā)錯誤為主要錯誤形式的信道稱為突發(fā)信道。產(chǎn)生突發(fā)錯碼的主要原因之一是脈沖干擾，而信道中的衰落現(xiàn)象也是產(chǎn)生突發(fā)錯碼的另一主要原因。錯誤的類型隨機錯誤：發(fā)生的位置是隨機的，而且數(shù)字序列中前后之64差錯控制方法檢錯重發(fā)法：接收端在收到的信碼中檢測出（發(fā)現(xiàn)）錯碼時，即設法通知發(fā)送端重發(fā)，直到正確收到為止。前向糾錯法：接收端不僅能在收到的信碼中發(fā)現(xiàn)有錯碼，還能夠解定錯碼的位置，糾正錯碼。反饋校驗法：接收端將收到的信碼原封不動地轉(zhuǎn)發(fā)回發(fā)送端，發(fā)送端將其與原發(fā)送信碼比較，如果發(fā)現(xiàn)錯誤，則重發(fā)。差錯控制方法檢錯重發(fā)法：接收端在收到的信碼中檢測出（發(fā)現(xiàn)）錯65自動要求重發(fā)系統(tǒng)——ARQ系統(tǒng)（AutomaticReportreQuest）自動要求重發(fā)系統(tǒng)——ARQ系統(tǒng)（AutomaticRe66ARQ系統(tǒng)的三種工作過程ARQ系統(tǒng)的三種工作過程67差錯控制編碼分類?在信息碼元序列中加入監(jiān)督碼元就稱為差錯控制編碼，也稱為糾錯編碼。不同的編碼方法，有不同的檢錯或糾錯能力。一般地，編碼中增加的監(jiān)督碼元越多，檢（糾）錯的能力就越強。?差錯控制編碼原則上是以降低信息傳輸速率為代價來換取傳輸可靠性的提高。差錯控制編碼分類?在信息碼元序列中加入監(jiān)督碼元就稱為差錯控68分類：功能不同分：檢錯碼、糾錯碼、和糾刪碼；信息碼元和附加的監(jiān)督碼元之間的檢驗關系分：線性碼和非線性碼；信息碼元和監(jiān)督碼元之間的約束方式分：分組碼和卷積碼；信息碼元在編碼后是否保持原來的形式不變分：系統(tǒng)碼和非系統(tǒng)碼；糾正錯誤的類型分：糾正隨機錯誤碼和糾正突發(fā)錯誤碼；編碼的數(shù)學方法分：代數(shù)碼、幾何碼和算術碼；

分類：69實例一：“明天14：00~16：00開會”“明天10：00~16：00開會”改：“明天下午14：00~16：00開會”“明天下午10：00~16：00開會”改：“明天下午14：00~16：00兩個小時開會”9.2糾錯編碼的基本原理實例一：9.2糾錯編碼的基本原理70實例二：000(晴)001(云)010(陰)011(雨)100(雪)101(霜)110(霧)111(雹)000(晴)011(云)101(陰)110(雨)000(晴)111(雨)實例二：000(晴)001(云)010(陰)011(雨71二糾錯碼的基本概念

分組碼將輸入的信息分成不同的組，對各組信息分別獨立編碼，附加若干監(jiān)督碼的編碼集合，為分組碼。分組碼一般用符號(n,k)表示，其中k是每組二進信息碼元的數(shù)目，n是編碼組的總位數(shù)，又稱為碼組長度（碼長），n-k=r為每碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)目。二糾錯碼的基本概念

分組碼將輸入的信息分成不同的組，對各72分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組成長n的碼字。在二進制情況下，共有2k個不同的信息組，相應地可得到2k個不同的碼字，稱為許用碼組；其余2n-2k個碼字未被選用，稱為禁用碼組。an-1an-2…arar-1…a0k個信息位r個監(jiān)督位碼長n=k+r分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組成73在分組碼中，碼組（碼字或碼矢）中碼元的數(shù)目，稱為碼組的長度（簡稱碼長）；碼組中把“1”的數(shù)目（即非0的數(shù)目）稱為碼組的重量（簡稱碼重）；碼長、碼重和碼距

在分組碼中，碼組（碼字或碼矢）中碼元的數(shù)目，稱為碼組的長度（74碼長、碼重和碼距

在分組碼中，把“1”的數(shù)目稱為碼組的重量，而把兩個碼組對應位上數(shù)字不同的位數(shù)稱為碼組的距離，簡稱碼距，又稱漢明(Hamming)距離。某種編碼中各個碼組間距離的最小值稱為最小碼距（d0）。碼長、碼重和碼距在分組碼中，把“1”的數(shù)目稱為碼組的重量，75三檢錯、糾錯能力任一(n,k)分組碼，若要在碼字內(nèi)：檢測e個隨機錯誤，則要求碼的最小距離；糾正t個隨機錯誤，則要求碼的最小距離；糾正t個同時檢測e()個隨機錯誤，則要求碼的最小距離；三檢錯、糾錯能力任一(n,k)分組碼，若要在碼字內(nèi)：76碼距與檢錯和糾錯能力的關系碼距與檢錯和糾錯能力的關系77四編碼效率編碼效率R來衡量有效性：對糾錯碼的要求：檢錯和糾錯能力盡量強；編碼效率盡量高；編碼規(guī)律盡量簡單。四編碼效率編碼效率R來衡量有效性：789.3常用的幾種簡單分組碼

奇偶監(jiān)督碼二維奇偶監(jiān)督碼恒比碼正反碼9.3常用的幾種簡單分組碼奇偶監(jiān)督碼799.3.1奇偶監(jiān)督碼奇偶監(jiān)督碼可分為奇監(jiān)督碼和偶監(jiān)督碼兩種，兩者的原理相同。在偶(奇)數(shù)監(jiān)督碼中，無論信息位有多少，監(jiān)督位只有一位，它使碼組中“1”的個數(shù)為偶(奇)數(shù)，即滿足an-1an-2…a0=0(1)式中a0為監(jiān)督位，其它為信息位。在接收端，將碼組中各碼元模2加，若結(jié)果為“1”(“0”)就說明存在錯碼，為“0”(“1”)就認為無錯。9.3.1奇偶監(jiān)督碼奇偶監(jiān)督碼可分為奇監(jiān)督碼和偶監(jiān)督碼兩種809.3.2二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼又稱方陣碼。它是把奇偶監(jiān)督碼的若干碼組排列成矩陣，每一碼組寫成一行，然后再按列的方向增加第二維監(jiān)督位。9.3.2二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼又稱方陣碼。它是把奇819.3.3恒比碼（等重碼或定1碼）

在恒比碼中，每個碼組均含有相同數(shù)目的“1”（和“0”）。由于“1”的數(shù)目和“0”的數(shù)目之比保持恒定，故得此名。這種碼在檢測時，只要計算接收碼組中“1”的數(shù)目是否對，就知道有無錯誤。恒比碼的主要優(yōu)點是簡單和適于用來傳輸電傳機或其它鍵盤設備產(chǎn)生的字母和符號。對于信源來的二進隨機數(shù)字序列，這種碼就不適合使用了。9.3.3恒比碼（等重碼或定1碼）在恒比碼中，每個碼組均82

“5中取3”恒比碼：（我國電傳通信中用）

阿拉伯數(shù)字保護電碼國際電碼阿拉伯數(shù)字保護電碼國際電碼12345010111100110110110100011111101110011000001010000016789010101111000111010011011011010111100011000001101101“5中取3”恒比碼：（我國電傳通信中用）阿拉伯數(shù)字保護電839.3.4正反碼正反碼是一種簡單的能夠糾正錯碼的編碼。其監(jiān)督位數(shù)目與信息位數(shù)目相同，監(jiān)督碼元與信息碼元相同（是信息碼的重復）或者相反（是信息碼的反碼），則由信息碼中“1”的個數(shù)而定。長度為10的正反碼具得糾正一位錯碼的能力，并能檢測全部兩位以下的錯碼和大部分兩位以上的錯碼。9.3.4正反碼正反碼是一種簡單的能夠糾正錯碼的編碼。849.3.5ISBN國際統(tǒng)一圖書編號

國內(nèi)外出版的圖書封底右下角印有諸如ISBN0-1315-2447-X形式的國際統(tǒng)一圖書編號，這種編號也是一種檢錯碼。第一位數(shù)字是國家代碼，“0”——美國及其他英語國家出版物；“7”——中國；“1315”——代表出版公司；“2447”——代表書名編號；“X（羅馬字）”——校驗位。9.3.5ISBN國際統(tǒng)一圖書編號國內(nèi)外出版的圖書封底右859.4線性分組碼線性分組碼，是指信息位和監(jiān)督位滿足一組線性方程，即其編碼規(guī)則可用一組線性方程來描述的分組碼。線性碼有一個重要性質(zhì)，就是它具有封閉性。即線性碼中的任意兩個碼組之各仍為該碼中的一個碼組。線性碼又稱群碼。9.4線性分組碼線性分組碼，是指信息位和監(jiān)督位滿足一組線性86一基本概念在(n,k)線性分組碼中，每一個監(jiān)督元都是碼組中某些信息元按模2和而得到。例（7，4）分組碼，設其碼字為A=[a6a5a4a3a2a1a0]，其中前4位是信息元，后3位是監(jiān)督元，可用下列線性方程組描述該分組碼，產(chǎn)生監(jiān)督元。一基本概念在(n,k)線性分組碼中，每一個監(jiān)督元都是碼組中87經(jīng)計算可得（7，4）碼的全部碼字。表9—1（7，4）碼的碼字表

序號碼字序號碼字信息元監(jiān)督元信息元監(jiān)督元00000000810001111000101191001100200101011010100103001111011101100140100110121100001501011011311010106011001114111010070111000151111111經(jīng)計算可得（7，4）碼的全部碼字。序碼字序碼88二監(jiān)督矩陣H和生成矩陣G1監(jiān)督矩陣H：設（7，4）漢明碼的碼字它有三個監(jiān)督元，可建立三個互相獨立的監(jiān)督關系式：二監(jiān)督矩陣H和生成矩陣G1監(jiān)督矩陣H：89

矩陣形式：

簡記為：或：

矩陣形式：簡記為：或：90

其中是A的轉(zhuǎn)置，是的轉(zhuǎn)置，是H的轉(zhuǎn)置；稱為（7，4）漢明碼的監(jiān)督矩陣。(n,k)線性分組碼的監(jiān)督矩陣H由r行n列組成，這r行是線性無關的。其中是A的轉(zhuǎn)置，是的91系統(tǒng)碼的監(jiān)督矩陣可寫成如下形式：稱為典型監(jiān)督矩陣。是r*r的單位矩陣，p是r*k的矩陣。上監(jiān)督矩陣H有：系統(tǒng)碼的監(jiān)督矩陣可寫成如下形式：922生成矩陣G：若將監(jiān)督方程補充為下列方程：2生成矩陣G：若將監(jiān)督方程補充為下列方程：93其中，變換為：

G=

其中，變換為：G=94稱為生成矩陣。由生成矩陣及信息組可產(chǎn)生出全部碼字。G由K行n列組成，每一行是一個碼字，K行線性無關。系統(tǒng)碼的生成矩陣可寫成：稱為典型生成矩陣。由典型生成矩陣得出的碼組A中，信息位不變，監(jiān)督位附加于其后，這種碼稱為系統(tǒng)碼。稱為生成矩陣。由生成矩陣及信息組可產(chǎn)生出全部碼字。G由K行95三伴隨式（校正子）S設發(fā)送碼組接收碼組則發(fā)送碼組和接收碼組之差為：它是傳輸中產(chǎn)生的錯碼行矩陣：其中：三伴隨式（校正子）S設發(fā)送碼組96可寫成：。令，稱為伴隨式或校正子。由于E為1*n，為n*r矩陣，所以S為1*r的矩陣，即r列的行矩陣：可寫成：。令97按照上述方法構造的糾正單個錯誤的線性分組碼稱為漢明碼。其特點：碼長：信息碼位：監(jiān)督碼位：r=n-k=m；最小碼距：d0=3；糾錯能力：t=1。

按照上述方法構造的糾正單個錯誤的線性分組碼稱為漢明碼。其特點98漢明碼的編碼效率：?漢明碼能糾正一個錯碼，則要求：2r-1≥n或2r≥k+r+1?漢明碼的編碼效率等于：K/n=(2r-1-r)/(2r-1)=1-r/(2r-1)=1-r/n?可見，漢明碼是一種高效碼。漢明碼的編碼效率：99四系統(tǒng)碼與非系統(tǒng)碼設信息位為，若編碼后的碼組為：，其中，是監(jiān)督位，則稱這種碼為系統(tǒng)碼。即系統(tǒng)碼經(jīng)過編碼后的碼組中前k個是信息位，后n-k是監(jiān)督位。若不存在上述關系，則稱為非系統(tǒng)碼。四系統(tǒng)碼與非系統(tǒng)碼設信息位為100只有系統(tǒng)碼才有關系：系統(tǒng)碼和非系統(tǒng)碼均有：。

只有系統(tǒng)碼才有關系：系統(tǒng)碼和非系統(tǒng)碼均有：。1019.5循環(huán)碼一定義及特點循環(huán)碼是一類特殊的線性分組碼，特點是循環(huán)性。所謂循環(huán)碼（CyclicCode）就是任何一個碼字循環(huán)右移一位后所得到的仍是一個合法碼字，也就是說這個碼在循環(huán)位移運算下具有封閉性。在代數(shù)理論中，常用碼多項式表示碼字。(n,k)循環(huán)碼的碼字，其碼多項式（以降冪順序排列）：9.5循環(huán)碼一定義及特點102例1（7，3）循環(huán)碼：序號碼字0123456700001111001100110101010101011010011010010011110001100110例1（7，3）循環(huán)碼：序碼字103例2（7，3）循環(huán)碼碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010例2（7，3）循環(huán)碼碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督104（7，3）循環(huán)碼0000000→0010111→1001011→1100101→1110010—0101110←1011100←0111001←（7，3）循環(huán)碼0000000→105二生成多項式及生成矩陣

若一種碼的所有碼多項式都是多項式g(x)的倍式，則稱g(x)為該碼的生成多項式。在(n,k)循環(huán)碼中任意碼多項式A(x)都是最低次碼倍式。因此，循環(huán)碼中次數(shù)最低的多項式（全0碼字除外）就是生成多項式g(x)?？梢宰C明，g(x)是常數(shù)項為1的r=n-k次多項式，是xn+1的一個因式。

二生成多項式及生成矩陣若一種碼的所有碼多項式都是多項式