第5章 差錯(cuò)控制

數(shù)據(jù)通信原理計(jì)通學(xué)院通信工程系2014年9月——for計(jì)算機(jī)12級(jí)第5章差錯(cuò)控制與信道編碼目的要求理解差錯(cuò)控制的基本方法和檢錯(cuò)、糾錯(cuò)碼構(gòu)成的基本原理。掌握信道編碼的基本原理；了解常用檢錯(cuò)碼的特性；掌握線性分組碼的一般特性；掌握漢明碼以及循環(huán)碼的編譯碼及其實(shí)現(xiàn)原理；了解卷積碼的基本概念。本章是本課程的重點(diǎn)。授課內(nèi)容5.1差錯(cuò)控制的基本概念及原理5.2檢錯(cuò)和糾錯(cuò)的基本概念5.3基于信道編碼的差錯(cuò)控制方式5.4常用的簡(jiǎn)單信道編碼5.5漢明碼及線性分組碼5.6循環(huán)碼5.7卷積碼返回目錄一、差錯(cuò)控制

所謂差錯(cuò)控制是通過(guò)某種方法，發(fā)現(xiàn)并糾正傳輸中出現(xiàn)的錯(cuò)誤。它是數(shù)據(jù)通信系統(tǒng)中提高傳輸可靠性，降低系統(tǒng)傳輸誤碼率的有效措施。5.1差錯(cuò)控制的基本概念及原理返回目錄二、信道編碼的基本概念

1、基本思路

在發(fā)送端被傳送的信息碼序列的基礎(chǔ)上，按照一定的規(guī)則加入若干“監(jiān)督碼元”后進(jìn)行傳輸，這些加入的碼元與原來(lái)的信息碼序列之間存在著某種確定的約束關(guān)系。在接收數(shù)據(jù)時(shí)，檢驗(yàn)信息碼元與監(jiān)督碼元之間的既定的約束關(guān)系，如該關(guān)系遭到破壞，則在接收端可以發(fā)現(xiàn)傳輸中的錯(cuò)誤，乃至糾正錯(cuò)誤。

信息碼+監(jiān)督碼=碼組，稱差錯(cuò)控制編碼或糾錯(cuò)編碼或信道編碼

（加的監(jiān)督碼越多，差錯(cuò)控制能力越強(qiáng)）2、編碼效率 將信息序列按照k位碼元的長(zhǎng)度分成若干個(gè)信息碼組M，再將信息碼組輸入到信道編碼器，信道編碼器按照一定的算法，產(chǎn)生一個(gè)新的n位碼字A輸出，n>k； 所謂編碼效率是指信道編碼后碼字中信息碼元的數(shù)目與碼字總碼元數(shù)目之比，記為k/n。3、許用碼字和禁用碼字

信息碼組M由k個(gè)二進(jìn)制碼元（即比特）組成，所以就有2k個(gè)M；A長(zhǎng)度為n，n位長(zhǎng)度的碼字共有2n個(gè)，信道編碼實(shí)質(zhì)是通過(guò)一定的規(guī)則，從2n個(gè)長(zhǎng)度為n的碼字中選擇了其中的2k個(gè)，每個(gè)被選中的碼字稱為許用碼字；未被選中的2n-2k個(gè)n長(zhǎng)的碼字稱為禁用碼字，反映冗余大小。4、信道編碼的分類按碼組的功能分為檢錯(cuò)碼和糾錯(cuò)碼按監(jiān)督碼與信息碼元之間的關(guān)系分為線性碼和非線性碼（1）線性碼：是指監(jiān)督碼元與信息碼元之間的關(guān)系是線性關(guān)系，即可用一組線性代數(shù)方程聯(lián)系起來(lái)（2）非線性碼：指的是二者是非線性關(guān)系按照對(duì)信息碼元處理方法的不同分為分組碼和卷積碼（1）分組碼：是將信息劃分為k個(gè)碼元一組。然后由這k個(gè)碼元按照一定的規(guī)則產(chǎn)生r，從而組成長(zhǎng)度n的碼組＝k個(gè)信息碼元＋r個(gè)監(jiān)督碼元。分組碼一般用符號(hào)(n,k)表示，；（2）在卷積碼中，每組的監(jiān)督碼元不但與本碼組的信息碼元有關(guān)，而且還與前面若干組信息碼元有關(guān)。即不是分組監(jiān)督，而是每個(gè)監(jiān)督碼元對(duì)它的前后碼元都實(shí)行監(jiān)督，前后相連，因此有時(shí)也稱為連環(huán)碼。按照信息碼元在編碼后是否保持原形式不變來(lái)分為系統(tǒng)碼和非系統(tǒng)碼（1）系統(tǒng)碼：編碼后的信息碼元保持原樣不變（2）非系統(tǒng)碼：編碼后的信息碼元改變了原來(lái)的信號(hào)形式三、差錯(cuò)分析的基本概念

危害數(shù)據(jù)傳輸?shù)脑肼曈袃深悾阂活愂请S機(jī)噪聲：包括熱噪聲、散彈噪聲以及傳輸媒介引起的噪聲等，引起隨機(jī)差錯(cuò)；另一類是脈沖噪聲：是指突然發(fā)生的噪聲，包括雷電、開(kāi)關(guān)引起的瞬態(tài)變化以及機(jī)電交換機(jī)的撥號(hào)脈沖等，引起突發(fā)差錯(cuò)。

根據(jù)這兩類噪聲差錯(cuò)可以分為兩種類型：

隨機(jī)差錯(cuò)，又稱獨(dú)立差錯(cuò)，是指那些獨(dú)立地、稀疏地和互不相關(guān)地發(fā)生的差錯(cuò)。（存在這種差錯(cuò)的信道稱為隨機(jī)信道或無(wú)記憶信道）

產(chǎn)生的原因：隨機(jī)噪聲

突發(fā)差錯(cuò)是指一串串，甚至是成片出現(xiàn)的差錯(cuò)，差錯(cuò)之間有相關(guān)性，差錯(cuò)出現(xiàn)是密集的。（存在這種突發(fā)錯(cuò)誤的信道稱為突發(fā)信道或有記憶信道）

產(chǎn)生的原因：脈沖噪聲錯(cuò)誤圖樣：假設(shè)發(fā)送端發(fā)送的序列為A，經(jīng)信道傳輸后，接收端接收的序列為B，信道的錯(cuò)誤圖樣為E。E=A+B，實(shí)際上是A異或B。因此，在錯(cuò)誤圖樣E中，0表示在傳輸中未發(fā)生錯(cuò)誤，1表示在傳輸中發(fā)生了錯(cuò)誤，表示錯(cuò)誤的碼元。如果已知錯(cuò)誤圖樣，就可確定差錯(cuò)類型。一般來(lái)說(shuō)，錯(cuò)誤比較集中（1的密度大）的叫做突發(fā)差錯(cuò)；錯(cuò)誤比較分散的叫做隨機(jī)差錯(cuò)。為了便于劃分突發(fā)差錯(cuò)與隨機(jī)差錯(cuò)的界限，可以通過(guò)錯(cuò)誤密度或者突發(fā)長(zhǎng)度來(lái)劃分。突發(fā)長(zhǎng)度指第一個(gè)錯(cuò)誤碼元與最后一個(gè)錯(cuò)誤碼元之間的碼元數(shù)目。錯(cuò)誤密度是指第一個(gè)錯(cuò)誤碼元至最后一個(gè)錯(cuò)誤碼元之間的錯(cuò)誤碼元數(shù)與他們之間的總碼元數(shù)之比。例如：A：1111111111B：1001001111E：0110110000則突發(fā)長(zhǎng)度為5，錯(cuò)誤密度為4/5返回5.2檢錯(cuò)和糾錯(cuò)的基本概念一、基本概念1、碼長(zhǎng)：碼字的碼元數(shù)目，例如(n，k)分組碼的碼長(zhǎng)為n2、碼重：指碼字中“1”的數(shù)目，記作W(A)。 例如：W(110110)=43、碼距：又稱漢明距，兩個(gè)等長(zhǎng)碼對(duì)應(yīng)位不同的數(shù)目，記作d(A，B)，例如：A=110110，B=101011，則d(A，B)=44、碼距與碼重的關(guān)系：d(A，B)=W(A+B)返回目錄5、最小碼距 又稱最小漢明距，

(n，k)分組碼總共有2k個(gè)碼字，記作Ai（i=0,1,…,2k-1）,則這些碼字兩兩之間都有一個(gè)碼距，定義該(n，k)分組碼的最小碼距為：

例如：有一碼組集合

10111 11001 00010 11010則該碼組的最小碼距為2。333422二、檢錯(cuò)和糾錯(cuò)的基本概念

檢錯(cuò)：驗(yàn)證收到的碼字是否是需用碼字即可發(fā)現(xiàn)錯(cuò)誤 糾錯(cuò)：能判斷出錯(cuò)誤發(fā)生的位置，將其糾正三、（n,k）分組碼的糾檢錯(cuò)能力

一個(gè)(n，k)分組碼的糾檢錯(cuò)能力由其最小碼距決定：

1、要在一個(gè)碼組中檢出e個(gè)誤碼，要求

d0e＋1

即任一碼組產(chǎn)生小于等于e個(gè)誤碼時(shí)，都不會(huì)變成另一準(zhǔn)用碼組。2、要在一個(gè)碼組中能糾正t個(gè)誤碼，要求

d0

2t＋1

將以t為半徑的“球”內(nèi)所有的禁用碼組均判為球心中的準(zhǔn)用碼組，可糾正t個(gè)以內(nèi)的錯(cuò)誤。

3、要在一個(gè)碼組中能糾正t個(gè)誤碼，同時(shí)檢出e(et)個(gè)誤碼

d0e＋t＋1

當(dāng)誤碼數(shù)小于等于t時(shí)，可糾正誤碼；當(dāng)誤碼數(shù)大于t小于等于e時(shí)，不會(huì)落入另一碼組的糾錯(cuò)范圍內(nèi)。返回5.3基于信道編碼的差錯(cuò)控制方式在數(shù)據(jù)通信系統(tǒng)中，差錯(cuò)控制方式可以分為四種：反饋糾錯(cuò)（ARQ）、前向糾錯(cuò)（FEC）、混合糾錯(cuò)（HEC）和信息反饋（IRQ）四種。返回目錄一、檢錯(cuò)重發(fā)或反饋糾錯(cuò)（ARQ）1、思路 這種差錯(cuò)控制方式在發(fā)送端對(duì)數(shù)據(jù)序列進(jìn)行分組編碼，加入一定多余碼元使之具有一定的檢錯(cuò)能力，成為能夠發(fā)現(xiàn)錯(cuò)誤的碼組。接收端收到碼組后，按一定規(guī)則對(duì)其進(jìn)行有無(wú)錯(cuò)誤的判別，并把判決結(jié)果（應(yīng)答信號(hào)）通過(guò)反向信道送回發(fā)送端。如有錯(cuò)誤，發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端認(rèn)為已正確接收到信息為止。2、重發(fā)方式在具體實(shí)現(xiàn)檢錯(cuò)重發(fā)系統(tǒng)時(shí)，通常有3種形式：停止等候重發(fā)返回重發(fā)選擇重發(fā)（1）停止等候重發(fā)

發(fā)送端每發(fā)送一個(gè)碼組，就停下來(lái)等候，發(fā)送端在Tw時(shí)間內(nèi)發(fā)送一個(gè)碼組，然后等候，等候時(shí)間為Td，再發(fā)送下一個(gè)碼組，Td>Tw+反饋時(shí)間；收端判斷下是否有錯(cuò)，會(huì)發(fā)送一個(gè)應(yīng)答信號(hào)給發(fā)送端，發(fā)送端收到信號(hào)（可以是承認(rèn)信號(hào)也可以是否認(rèn)信號(hào)）后，讓發(fā)送端在下一個(gè)發(fā)送時(shí)間內(nèi)發(fā)送碼組，如果發(fā)送無(wú)錯(cuò)，則發(fā)送應(yīng)答信號(hào)為ACK，讓發(fā)送端接著發(fā)送下一個(gè)碼組；如果發(fā)送出錯(cuò)，則發(fā)送應(yīng)答信號(hào)為NAK，要求重發(fā)這個(gè)出錯(cuò)的碼組。示例動(dòng)畫演示（2）返回重發(fā)

發(fā)送端連續(xù)發(fā)送一個(gè)碼組，一邊發(fā)送，一邊等候接收端的應(yīng)答信號(hào)。接收端檢驗(yàn)，如果發(fā)現(xiàn)無(wú)錯(cuò)，則發(fā)送應(yīng)答信號(hào)ACK，則繼續(xù)發(fā)送碼組；如果發(fā)現(xiàn)有錯(cuò)，則發(fā)送應(yīng)答信號(hào)NAK，如果這個(gè)碼組出錯(cuò)，那么發(fā)送端要求這個(gè)錯(cuò)誤碼組以后已經(jīng)發(fā)送的碼組都要重發(fā)。比如接收端第2個(gè)碼組出錯(cuò)，那么接收端返回NAK應(yīng)答信號(hào)時(shí)，發(fā)送端正在發(fā)送第6個(gè)碼組，等第6個(gè)碼組發(fā)送完，發(fā)送端要從這個(gè)有錯(cuò)的碼組，即第2個(gè)碼組開(kāi)始，把已經(jīng)發(fā)送出去的第2、3、4、5、6個(gè)碼組都要重發(fā)。示例動(dòng)畫演示（3）選擇重發(fā) 發(fā)送端連續(xù)發(fā)送一個(gè)碼組，一邊發(fā)送，一邊等候接收端的應(yīng)答信號(hào)。接收端檢驗(yàn)，如果發(fā)現(xiàn)無(wú)錯(cuò)，則發(fā)送應(yīng)答信號(hào)ACK，則繼續(xù)發(fā)送碼組；如果發(fā)現(xiàn)有錯(cuò)，則發(fā)送應(yīng)答信號(hào)NAK，如果這個(gè)碼組出錯(cuò)，發(fā)送端只需要重發(fā)這個(gè)出錯(cuò)的碼組。

示例動(dòng)畫演示3、特點(diǎn)編碼效率比較高，對(duì)信道的適應(yīng)能力強(qiáng)重發(fā)導(dǎo)致信道的有效利用率較低，通信的實(shí)時(shí)性較差譯碼設(shè)備較簡(jiǎn)單4、應(yīng)用數(shù)據(jù)通信系統(tǒng)二、前向糾錯(cuò)（FEC）1、思路前向糾錯(cuò)系統(tǒng)中，發(fā)送端的信道編碼器將輸入數(shù)據(jù)序列變換成能夠糾正錯(cuò)誤的碼，接收端的譯碼器根據(jù)編碼規(guī)律檢驗(yàn)出錯(cuò)誤的位置并自動(dòng)糾正。2、特點(diǎn)無(wú)需重發(fā)，實(shí)時(shí)性好編碼效率較低，譯碼設(shè)備比較復(fù)雜若錯(cuò)誤超出糾錯(cuò)碼糾錯(cuò)能力,只好將其拋棄3、應(yīng)用移動(dòng)通信系統(tǒng)

三、混合糾錯(cuò)檢錯(cuò)（HEC）

1、思路混合糾錯(cuò)檢錯(cuò)方式是前向糾錯(cuò)方式和檢錯(cuò)重發(fā)方式的結(jié)合。在這種系統(tǒng)中，發(fā)送端發(fā)出同時(shí)具有檢錯(cuò)和糾錯(cuò)能力的碼，接收端收到碼后，檢查錯(cuò)誤情況，如果錯(cuò)誤少于糾錯(cuò)能力，則自行糾正；如果干擾嚴(yán)重，錯(cuò)誤很多，超出糾正能力，但能檢測(cè)出來(lái)，則經(jīng)反向信道要求發(fā)端重發(fā)。2、特點(diǎn)集合了ARQ和FEC的優(yōu)點(diǎn)，在保證系統(tǒng)較高的有效性的同時(shí),大幅度提高了整個(gè)系統(tǒng)的可靠性3、應(yīng)用移動(dòng)通信系統(tǒng)，數(shù)據(jù)傳輸系統(tǒng)四、信息反饋（IRQ）1、思路接收端把收到的數(shù)據(jù)序列全部由反向信道送回發(fā)端，發(fā)端比較發(fā)送的數(shù)據(jù)序列與送回的數(shù)據(jù)序列，從而發(fā)現(xiàn)是否有錯(cuò)誤，并把認(rèn)為錯(cuò)誤的數(shù)據(jù)序列的原數(shù)據(jù)再次傳送，直到發(fā)端沒(méi)有發(fā)現(xiàn)錯(cuò)誤為止。2、特點(diǎn)不需要糾錯(cuò)、檢錯(cuò)的編譯碼器，設(shè)備簡(jiǎn)單。

需要和前向信道相同的反向信道，實(shí)時(shí)性差。

發(fā)送端需要一定容量的存儲(chǔ)器以存儲(chǔ)發(fā)送碼組，環(huán)路時(shí)延越大，數(shù)據(jù)速率越高，所需存儲(chǔ)容量越大。返回5.4常用的簡(jiǎn)單信道編碼5.4.1奇偶監(jiān)督碼5.4.2行列監(jiān)督碼5.4.3恒比碼5.4.4重復(fù)碼5.4.5正反碼返回目錄碼重為奇數(shù)或偶數(shù)的(n,n-1)系統(tǒng)分組碼

ITU-T建議——同步數(shù)據(jù)傳輸使用偶監(jiān)督——異步數(shù)據(jù)傳輸使用奇監(jiān)督監(jiān)督關(guān)系：假設(shè)將（n，n-1）的奇偶監(jiān)督碼的碼字記作：an-1,an-2,…,a1,a0，其中a0為監(jiān)督碼元，其余為信息碼元，則各碼元滿足：5.4.1奇偶監(jiān)督碼返回對(duì)水平方向(共L行)和垂直方向(共M列),同時(shí)進(jìn)行奇偶監(jiān)督的碼，記作（LM+L+M+1,LM）。(66，50)行列監(jiān)督碼的一個(gè)碼字(偶監(jiān)督)該碼具有很強(qiáng)的糾檢錯(cuò)能力，常用于短波散射信道等信道干擾比較嚴(yán)重的通信中。5.4.2行列監(jiān)督碼返回該碼的特點(diǎn)是碼字中1，0數(shù)目恒定，亦即1，0數(shù)目之比恒定。電傳通信中普遍采用3：2碼，又稱5中取3碼，如下所示

國(guó)際上通用的ARQ電報(bào)通信系統(tǒng)中，采用7中取3碼。

5.4.3恒比碼恒比碼的優(yōu)點(diǎn)：（1）簡(jiǎn)單（2）能檢測(cè)出單個(gè)和奇數(shù)個(gè)錯(cuò)誤，還能部分檢測(cè)出偶數(shù)個(gè)錯(cuò)誤（3）適于傳輸電傳機(jī)或其他鍵盤設(shè)備所產(chǎn)生的數(shù)字、字母和符號(hào)；但不適用于信源來(lái)的二進(jìn)制隨機(jī)數(shù)字序列返回(3，1)重復(fù)碼兩個(gè)碼字為000和111，其最小碼距為3；(n，1)重復(fù)碼也只有全0碼和全1碼兩個(gè)碼字，其最小碼距為n，卻有2n-2個(gè)禁用碼組，隨著碼長(zhǎng)的增大，其冗余也變得很大；該碼隨碼長(zhǎng)增加，具有很強(qiáng)的糾檢錯(cuò)能力，但其編碼效率的急劇下降；重復(fù)碼并不是一種優(yōu)秀的編碼方案，僅用于速率很低的數(shù)據(jù)通信系統(tǒng)中。重復(fù)碼只有一位信息碼元，監(jiān)督碼元是信息碼元的重復(fù)，所以僅有兩個(gè)碼字；5.4.4重復(fù)碼返回該碼型多用于10單位碼的前向糾錯(cuò)設(shè)備中，可以糾正一位錯(cuò)誤，發(fā)現(xiàn)全部?jī)蓚€(gè)以下的錯(cuò)誤，以及大部分兩個(gè)以上的錯(cuò)誤，其本質(zhì)就是五單位碼的重復(fù)；編碼規(guī)則：信息碼組中1的數(shù)目為奇數(shù)時(shí)，監(jiān)督碼是信息碼的重復(fù)即正碼；信息碼組中1的數(shù)目為偶數(shù)時(shí)，監(jiān)督碼是信息碼的反碼。例如：M=11001，則對(duì)應(yīng)得碼字為1100111001M=11101，則對(duì)應(yīng)得碼字為11101000105.4.5正反碼

譯碼規(guī)則： 首先將收到的碼字重的信息位和監(jiān)督位按對(duì)應(yīng)位作模2運(yùn)算，得到一個(gè)5位碼組，若該碼字中有奇數(shù)個(gè)1，則將其作為校驗(yàn)碼組，若有偶數(shù)個(gè)1，則取其反碼作為校驗(yàn)碼組。然后，按照下表進(jìn)行糾檢錯(cuò)譯碼。 例如：0110101101，則合出碼組為00000，信息元中有3個(gè)1，奇數(shù)，所以檢驗(yàn)碼組即合成碼組00000，對(duì)應(yīng)表，則傳輸正確。 如0101010111，則合成碼組為11101，因?yàn)樾畔⒃?個(gè)1，偶數(shù)，所以校驗(yàn)碼為合成碼組的反碼，00010，則對(duì)照表，監(jiān)督元有1位出錯(cuò)，在校驗(yàn)碼組中1對(duì)應(yīng)的位置，即監(jiān)督元10111中斜體1出錯(cuò)。 如0111010110，則合成碼組為11000，信息元中有3個(gè)1，則校驗(yàn)碼組等于合成碼組，11000，則錯(cuò)誤情況判斷：傳輸出錯(cuò)，且錯(cuò)誤位數(shù)大于1。

正反碼錯(cuò)誤判決表校驗(yàn)碼組的形式錯(cuò)誤情況判斷1全“0”傳輸正確24個(gè)“1”，1個(gè)“0”信息元有1位出錯(cuò)，在校驗(yàn)碼組中“0”對(duì)應(yīng)的位置34個(gè)“0”，1個(gè)“1”監(jiān)督元有1位出錯(cuò)，在校驗(yàn)碼組中“1”對(duì)應(yīng)的位置4其它形式傳輸出錯(cuò)，且錯(cuò)誤位數(shù)大于1返回5.5漢明碼及線性分組碼5.5.1線性分組碼5.5.2漢明碼返回目錄5.5.1線性分組碼一、線性分組碼的定義線性碼是指信息位和監(jiān)督位滿足一組線性方程的碼；分組碼是監(jiān)督碼僅對(duì)本碼組起監(jiān)督作用，既是線性碼又是分組碼稱為線性分組碼。（n,k）線性分組碼，其碼字通常記作：

A=[an-1an-2…a0]1×n二、線性分組碼的性質(zhì)（1）封閉性：指碼中任意兩許用碼組之和仍為一許用碼組。（2）線性分組碼中必有一個(gè)全0碼組（3）碼的最小距離等于非零碼的最小重量例：已知一個(gè)線性分組碼的碼組集合為：

000000，001110，010101，011011，100011，101101，110110，111000求該碼組集合的漢明距離。解：根據(jù)線性分組碼的性質(zhì)可以求出此碼組集合的漢明距離為3。三、線性分組碼編碼1、生成矩陣 對(duì)于一個(gè)（n,k）線性分組碼，其生成矩陣G是k行n列的矩陣，只要有k個(gè)線性無(wú)關(guān)的n元行矢量，都可以構(gòu)成生成矩陣G，生成矩陣不同，則得到的分組碼也不同。2、編碼原理

已知(n,k)線性分組碼A=[an-1an-2…a0]1×n，其信息碼組M=[mk-1mk-2…m1m0]1×k

，則編碼過(guò)程為：例：假設(shè)一個(gè)(6，3)分組碼生成矩陣為：

編碼過(guò)程為：

信息碼組M[m2

m1

m0]碼字A[a5

a4

a3

a2

a1

a0]信息碼組M[m2

m1

m0]碼字A[a5

a4

a3

a2

a1

a0]000001010011000000001101010011011110100101110111110101111000100110101011根據(jù)編碼原理，輸入信息碼組M，得到相應(yīng)的碼字A。該(6，3)碼是非系統(tǒng)碼，信息元m2、m0、m1分別出現(xiàn)在碼字A的第1、3、5位，而2、4、6位是編碼器產(chǎn)生的監(jiān)督碼元其碼表為：要想得到系統(tǒng)碼，即碼組A中，信息位不變，監(jiān)督位附加于其后，則需要將生成矩陣G進(jìn)行典型化。生成矩陣典型化編碼過(guò)程(6，3)系統(tǒng)分組碼表

監(jiān)督元與信息元之間的一般關(guān)系

信息碼組M[m2

m1

m0]碼字A[a5

a4

a3

a2

a1

a0]信息碼組M[m2

m1

m0]碼字A[a5

a4

a3

a2

a1

a0]000001010011000000001101010011011110100101110111100110101011110101111000注意到系統(tǒng)碼中前k位即信息元，將其寫成線性方程組的形式監(jiān)督關(guān)系

監(jiān)督矩陣

監(jiān)督關(guān)系一般表達(dá)或生成矩陣典型陣一般形式(n，k)分組碼碼字可表示為：(n，k)碼的一般編碼過(guò)程A=[an-1

an-2…an-k

ar-1

…a1

a0]=[mk-1

mk-2…m0

ar-1

…a1

a0]對(duì)上式兩邊同時(shí)進(jìn)行矩陣轉(zhuǎn)置得：

即此時(shí)的系數(shù)矩陣，即監(jiān)督矩陣為

生成矩陣和監(jiān)督距陣的關(guān)系(n，k)碼的一般編碼過(guò)程或即

根據(jù)需要選定一監(jiān)督關(guān)系確定H陣；求由H距陣和Ｇ陣的關(guān)系確定G陣；由A=M·G生成所有碼字。生成矩陣和監(jiān)督矩陣是正交3、伴隨式與檢錯(cuò)原理

所謂錯(cuò)誤圖樣E，是由發(fā)送碼字A和接收碼字B進(jìn)行異或運(yùn)算得到，若E＝0，說(shuō)明傳輸無(wú)錯(cuò)，即碼字A與B相同，但是錯(cuò)誤圖樣只能夠反映的是信道噪聲的情況，接收端是不能依據(jù)其來(lái)檢錯(cuò)。實(shí)際上，判斷傳輸是否出錯(cuò)，可以將接收到的碼字B跟分組碼的碼字進(jìn)行比較，如果B是分組碼(n,k)的碼字，說(shuō)明傳輸無(wú)錯(cuò)。因此，這里定義了個(gè)伴隨式S伴隨式S和錯(cuò)誤圖樣E的關(guān)系(6，3)分組碼的監(jiān)督矩陣為：

伴隨式

(6，3)分組碼伴隨式計(jì)算電路

4、舉例（1）已知某線形碼監(jiān)督矩陣為

試列出所有的許用碼組（2）設(shè)（7，4）線形碼的生成矩陣：

當(dāng)信息位為0001時(shí)，試求其后的監(jiān)督位。（3）求上題的監(jiān)督矩陣。

返回5.5.2漢明碼一、概念

漢明距是最早發(fā)現(xiàn)的具有糾錯(cuò)能力的碼，是一種編碼效率較高的分組碼，也是一種線性碼。對(duì)于任何的整數(shù)，必存在一個(gè)(n，k)漢明碼，碼長(zhǎng)n和監(jiān)督元數(shù)目r=n-k滿足n=2r-1二、特點(diǎn)

1、可以糾正一位傳輸錯(cuò)誤，且d0=3 2、碼長(zhǎng)和監(jiān)督元的關(guān)系：n=2r-1

記為：（n，k）＝（2r-1，2r-1-r） 漢明碼的編碼效率：將監(jiān)督矩陣記成列矢量的形式，H=[h0h1…h(huán)n-2hn-1]，則單個(gè)錯(cuò)誤（所有的ei只有一位為1）時(shí)的伴隨式恰好與H的一個(gè)列矢量對(duì)應(yīng)，只要H的各個(gè)列矢量不為0矢量，且各不相同，則可以糾正單個(gè)錯(cuò)誤。三、伴隨式和錯(cuò)誤圖樣的關(guān)系四、實(shí)例分析——(7，4)漢明碼

首先其監(jiān)督矩陣，此時(shí)監(jiān)督矩陣為H3×7，3位二進(jìn)制碼元的組合有8種：

000、001、010、011、100、101、110、111其中不全為零的7個(gè)正好可用作監(jiān)督矩陣的列,可得到監(jiān)督矩陣：

任意調(diào)換監(jiān)督矩陣各列位置并不影響碼的糾錯(cuò)能力，將其轉(zhuǎn)化成典型陣的形式，并由其可以得到生成矩陣G由A=MG得到其所有的碼字，如下表所示：

假設(shè)發(fā)送端的碼字是A15=1111111，傳輸過(guò)程中第4位a3出現(xiàn)了錯(cuò)誤，即接收的碼字是B=1110111此時(shí)對(duì)應(yīng)的伴隨式為：

信息碼組Mm3

m2

m1

m0碼字Aa6

a5

a4

a3

a2

a1

a0信息碼組Mm3

m2

m1

m0碼字Aa6

a5

a4

a3

a2

a1

a000000001001000110100010101100111000000000010110010101001111001001100101101011001101110001000100110101011110011011110111110001111001100101001010110011100001110101011101001111111下表給出了該（7，4）漢明碼單個(gè)錯(cuò)誤的錯(cuò)誤圖樣與其對(duì)應(yīng)的伴隨式，可以發(fā)現(xiàn)伴隨式正是監(jiān)督矩陣的每一列，且該列的位置恰好是碼元出錯(cuò)的位置。

由于S不是全零，可判斷傳輸出錯(cuò)，而ST=[011]T，是監(jiān)督矩陣H的第4列,這正是錯(cuò)誤碼元發(fā)生的位置,因此可以得到錯(cuò)誤圖樣為E=0001000，進(jìn)而按B+E即可糾錯(cuò)。錯(cuò)誤位置錯(cuò)誤圖樣E[e6

e5

e4

e3

e2

e1

e0]伴隨式S[s2

s1

s0]無(wú)錯(cuò)0000000000b00000001001b10000010010b20000100100b30001000011b40010000101b50100000110b61000000111返回5.6循環(huán)碼一、概念

循環(huán)碼是一類重要的線性分組碼，若(an-1an-2…a0)是循環(huán)碼的一個(gè)碼組，則循環(huán)移位后的碼組：

(an-2an-3…a0an-1) (an-3an-4…an-1an-2) …… (a0an-1…a2a1)仍然是該編碼中的碼組。

返回目錄一個(gè)(7，3)系統(tǒng)循環(huán)碼碼表如下所示：信息碼組Mm2m1m0碼字Aa6a5a4a3a2a1a0信息碼組Mm2m1m0碼字Aa6a5a4a3a2a1a000000101001100000000010111010111001110011001011101111001011101110011001011110010表中第2碼組向右移一位即得到第5碼組；第5碼組向右移一位即得到第7碼組。

二、循環(huán)碼特點(diǎn)（1）封閉性：指碼中任意兩許用碼組之和仍為一許用碼組（2）線性分組碼中必有一個(gè)全0碼組（3）碼的最小距離等于非零碼的最小重量（4）循環(huán)性：循環(huán)碼中任一許用碼字經(jīng)循環(huán)移位后，得到的新碼字仍為它的一個(gè)許用碼字。

三、循環(huán)碼的數(shù)學(xué)表示法1、碼多項(xiàng)式

(n，k)循環(huán)碼中，為了便于描述與計(jì)算，經(jīng)常使用n-1次碼多項(xiàng)式來(lái)表示碼字，碼字A=[an-1an-2…a1

a0]，它對(duì)應(yīng)的碼多項(xiàng)式為：

上式中x的值沒(méi)有任何意義，僅用它的冪代表碼元的位置例如A4=0111001，對(duì)應(yīng)的碼多項(xiàng)式為：A4向左循環(huán)移1位得A7=1110010，這相當(dāng)于將A4(x)乘以x，即

A7向左循環(huán)移1位得A6=1100101，但若將A7(x)乘以x得到多項(xiàng)式為對(duì)于(7，3)循環(huán)碼的碼多項(xiàng)式，其最高次數(shù)不能超過(guò)6，解決該問(wèn)題的辦法是對(duì)上式作模x7+1運(yùn)算得余作為碼多項(xiàng)式2、整數(shù)的按模運(yùn)算在整數(shù)運(yùn)算中，有模n運(yùn)算。例如，在模2運(yùn)算中，有

1+1=20(模2),1+2=31(模2),23=60(模2)。一般說(shuō)來(lái)，若一個(gè)整數(shù)m可以表示為式中，Q為整數(shù)，則在模n運(yùn)算下，有

mp(模n)

所以，在模n運(yùn)算下，一個(gè)整數(shù)m等于它被n除得的余數(shù)。3、碼多項(xiàng)式的按模運(yùn)算 若任意一個(gè)多項(xiàng)式F(x)被一個(gè)n次多項(xiàng)式N(x)除，得到商式Q(x)和一個(gè)次數(shù)小于n的余式R(x)，即則在按模N(x)運(yùn)算下，有這時(shí)，碼多項(xiàng)式系數(shù)仍按模2運(yùn)算。例1：x3被(x3+1)除，得到余項(xiàng)1，即例2：

因?yàn)? x x3+1x4+x2+1 x4+x x2+x+1

4、循環(huán)碼的數(shù)學(xué)表示法 在循環(huán)碼中，設(shè)A(x)是一個(gè)長(zhǎng)度為n的碼組，即 若則A(x)也是該編碼中的一個(gè)碼組。例：一循環(huán)碼為1100101，即

若給定i=3，則有

上式對(duì)應(yīng)的碼組為0101110，它正是A(x)向左移3位的結(jié)果。 結(jié)論：一個(gè)長(zhǎng)為n的循環(huán)碼必定為按模(xn+1)運(yùn)算的一個(gè)余式。

其計(jì)算過(guò)程如下：例如：四、生成多項(xiàng)式和生成矩陣1、生成多項(xiàng)式

如果一種碼的所有碼多項(xiàng)式都是多項(xiàng)式g(x)的倍式，則稱g(x)為該碼的生成多項(xiàng)式。在(n,k)循環(huán)碼中任意碼多項(xiàng)式A(x)都是最低次碼多項(xiàng)式的倍式。如(7,3)循環(huán)碼中，其它碼多項(xiàng)式都是g(x)的倍式，即

在循環(huán)碼中除全“0”碼組外，再?zèng)]有連續(xù)k位均為“0”的碼組。否則，在經(jīng)過(guò)若干次循環(huán)移位后將得到k位信息位全為“0”，但監(jiān)督位不全為“0”的一個(gè)碼組。這在線性碼中顯然是不可能的。 因此，g(x)必須是一個(gè)常數(shù)項(xiàng)不為“0”的(n－k)次多項(xiàng)式，而且這個(gè)g(x)還是這種(n,k)碼中次數(shù)為(n－k)的唯一一個(gè)多項(xiàng)式。因?yàn)槿绻袃蓚€(gè)，則由碼的封閉性，把這兩個(gè)相加也應(yīng)該是一個(gè)碼組，且此碼組多項(xiàng)式的次數(shù)將小于(n－k)，即連續(xù)“0”的個(gè)數(shù)多于(k－1)。顯然，這是與前面的結(jié)論矛盾的。 我們稱這唯一的(n－k)次多項(xiàng)式g(x)為碼的生成多項(xiàng)式。一旦確定了g(x)，則整個(gè)(n,k)循環(huán)碼就被確定了。

因此，一個(gè)多項(xiàng)式為(n,k)循環(huán)碼的生成多項(xiàng)式g(x)必須符合以下三個(gè)條件： （1）g(x)是xn-1的一個(gè)因式； （2）g(x)是一個(gè)n-k次多項(xiàng)式； （3）g(x)多項(xiàng)式中必有一個(gè)常數(shù)項(xiàng)1。

g(x)、xg(x)、x2g(x)、…、xk-1g(x)是(n，k)循環(huán)碼的k個(gè)線性無(wú)關(guān)的碼字，所以可得其生成距陣G，用碼多項(xiàng)式表示G的各行：

2、生成矩陣若信息碼組M=[mk-1mk-2…m0]，則：例如：

上表中的編碼為(7,3)循環(huán)碼，n=7,k=3,n–k=4，其中唯一的一個(gè)(n–k)=4次碼多項(xiàng)式代表的碼組是第二碼組0010111，與它對(duì)應(yīng)的碼多項(xiàng)式即生成多項(xiàng)式為：

g(x)=x4+x2+x+1。

碼組編號(hào)信息位監(jiān)督位碼組編號(hào)信息位監(jiān)督位A6a5a4a3a2a1a0a6a5a4A3a2a1a01000000051001011200101116101110030101110711001014011100181110010將此g(x)代入上矩陣，得到上式不符合G=[IkQ]形式，所以它不是典型生成矩陣。但它經(jīng)過(guò)線性變換后，不難化成典型陣。將該矩陣典型化之后，再按照A=MG編碼才能得到(7，3)系統(tǒng)循環(huán)碼；實(shí)際應(yīng)用中，系統(tǒng)循環(huán)碼的編譯碼通常是由g(x)經(jīng)過(guò)簡(jiǎn)單的代數(shù)運(yùn)算來(lái)實(shí)現(xiàn)。

3、舉例說(shuō)明 已知循環(huán)碼的生成多項(xiàng)為，當(dāng)信息位為1000時(shí)，寫出它的監(jiān)督位和整個(gè)碼組。解：由生成多項(xiàng)式可知n-k=3，而k=4，所以n＝7

第1行+第3行+第4行第1行

第2行+第4行第2行

非典型典型當(dāng)信息位為1000時(shí)，整個(gè)碼組為監(jiān)督位為101系統(tǒng)(n，k)循環(huán)碼碼字：

編碼原理用碼多項(xiàng)式來(lái)表示為：五、循環(huán)碼的編碼A=[an-1

an-2…an-k

ar-1

…a1

a0]=[mk-1

mk-2