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

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

1、基本思路

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

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

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

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

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

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

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

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

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

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

例如：有一碼組集合

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

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

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

1、要在一個碼組中檢出e個誤碼，要求

d0e＋1

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

d0

2t＋1

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

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

d0e＋t＋1

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

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

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

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

三、混合糾錯檢錯（HEC）

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

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

發(fā)送端需要一定容量的存儲器以存儲發(fā)送碼組，環(huán)路時延越大，數(shù)據(jù)速率越高，所需存儲容量越大。返回5.4常用的簡單信道編碼5.4.1奇偶監(jiān)督碼5.4.2行列監(jiān)督碼5.4.3恒比碼5.4.4重復碼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)督碼返回對水平方向(共L行)和垂直方向(共M列),同時進行奇偶監(jiān)督的碼，記作（LM+L+M+1,LM）。(66，50)行列監(jiān)督碼的一個碼字(偶監(jiān)督)該碼具有很強的糾檢錯能力，常用于短波散射信道等信道干擾比較嚴重的通信中。5.4.2行列監(jiān)督碼返回該碼的特點是碼字中1，0數(shù)目恒定，亦即1，0數(shù)目之比恒定。電傳通信中普遍采用3：2碼，又稱5中取3碼，如下所示

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

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

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

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

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

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

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

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

編碼過程為：

信息碼組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進行典型化。生成矩陣典型化編碼過程(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)系一般表達或生成矩陣典型陣一般形式(n，k)分組碼碼字可表示為：(n，k)碼的一般編碼過程A=[an-1

an-2…an-k

ar-1

…a1

a0]=[mk-1

mk-2…m0

ar-1

…a1

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

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

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

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

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

伴隨式

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

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

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

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

返回5.5.2漢明碼一、概念

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

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

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

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

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

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

假設(shè)發(fā)送端的碼字是A15=1111111，傳輸過程中第4位a3出現(xiàn)了錯誤，即接收的碼字是B=1110111此時對應(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）漢明碼單個錯誤的錯誤圖樣與其對應(yīng)的伴隨式，可以發(fā)現(xiàn)伴隨式正是監(jiān)督矩陣的每一列，且該列的位置恰好是碼元出錯的位置。

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

e5

e4

e3

e2

e1

e0]伴隨式S[s2

s1

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

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

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

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

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

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

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

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

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

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

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

mp(模n)

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

因為 x x3+1x4+x2+1 x4+x x2+x+1

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

若給定i=3，則有

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

其計算過程如下：例如：四、生成多項式和生成矩陣1、生成多項式

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

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

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

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

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

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

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

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

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

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

第2行+第4行第2行

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

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

an-2…an-k

ar-1

…a1

a0]=[mk-1

mk-2