第5章 差錯(cuò)控制

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

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

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

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í)也稱為連

5、環(huán)碼。按照信息碼元在編碼后是否保持原形式不變來(lái)分為系統(tǒng)碼和非系統(tǒng)碼（1）系統(tǒng)碼：編碼后的信息碼元保持原樣不變（2）非系統(tǒng)碼：編碼后的信息碼元改變了原來(lái)的信號(hào)形式下一頁(yè)上一頁(yè)三、差錯(cuò)分析的基本概念三、差錯(cuò)分析的基本概念危害數(shù)據(jù)傳輸?shù)脑肼曈袃深悾阂活愂请S機(jī)噪聲：包括熱噪聲、散彈噪聲以及傳輸媒介引起的噪聲等，引起隨機(jī)差錯(cuò)；另一類是脈沖噪聲：是指突然發(fā)生的噪聲，包括雷電、開關(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ī)噪聲

6、突發(fā)差錯(cuò)是指一串串，甚至是成片出現(xiàn)的差錯(cuò)，差錯(cuò)之間有相關(guān)性，差錯(cuò)出現(xiàn)是密集的。（存在這種突發(fā)錯(cuò)誤的信道稱為突發(fā)信道或有記憶信道）產(chǎn)生的原因：脈沖噪聲下一頁(yè)上一頁(yè)l錯(cuò)誤圖樣：l假設(shè)發(fā)送端發(fā)送的序列為A，經(jīng)信道傳輸后，接收端接收的序列為B，信道的錯(cuò)誤圖樣為E。lE=A+B，實(shí)際上是A異或B。因此，在錯(cuò)誤圖樣E中，0表示在傳輸中未發(fā)生錯(cuò)誤，1表示在傳輸中發(fā)生了錯(cuò)誤，表示錯(cuò)誤的碼元。l如果已知錯(cuò)誤圖樣，就可確定差錯(cuò)類型。一般來(lái)說(shuō)，錯(cuò)誤比較集中（1的密度大）的叫做突發(fā)差錯(cuò)；錯(cuò)誤比較分散的叫做隨機(jī)差錯(cuò)。為了便于劃分突發(fā)差錯(cuò)與隨機(jī)差錯(cuò)的界限，可以通過(guò)錯(cuò)誤密度或者突發(fā)長(zhǎng)度來(lái)劃分。l突發(fā)長(zhǎng)度指第一個(gè)錯(cuò)誤碼元與最

7、后一個(gè)錯(cuò)誤碼元之間的碼元數(shù)目。錯(cuò)誤密度是指第一個(gè)錯(cuò)誤碼元至最后一個(gè)錯(cuò)誤碼元之間的錯(cuò)誤碼元數(shù)與他們之間的總碼元數(shù)之比。下一頁(yè)上一頁(yè)例如：A：1 1 1 1 1 1 1 1 1 1B：1 0 0 1 0 0 1 1 1 1E：0 1 1 0 1 1 0 0 0 0則突發(fā)長(zhǎng)度為5，錯(cuò)誤密度為4/5返回下一頁(yè)上一頁(yè)5.2 檢錯(cuò)和糾錯(cuò)的基本概念一、基本概念一、基本概念1、碼長(zhǎng)：碼字的碼元數(shù)目，例如(n，k)分組碼的碼長(zhǎng)為n 2、碼重：指碼字中“1”的數(shù)目，記作W(A)。例如：W(110110)=4 3、碼距：又稱漢明距，兩個(gè)等長(zhǎng)碼對(duì)應(yīng)位不同的數(shù)目，記作d(A，B)， 例如：A=110110，B=1010

8、11，則d(A，B)=4 4、碼距與碼重的關(guān)系：d(A，B)=W (A+B) 返回目錄下一頁(yè)上一頁(yè)5、最小碼距又稱最小漢明距， (n，k)分組碼總共有2k個(gè)碼字，記作Ai（i=0,1,2k-1）,則這些碼字兩兩之間都有一個(gè)碼距，定義該(n，k)分組碼的最小碼距為 ：例如：有一碼組集合1 0 1 1 11 1 0 0 10 0 0 1 01 1 0 1 0l則該碼組的最小碼距為2。12 , 2 , 1 , 0; 12 , 2 , 1 , 0),(dmin0 kkjijijiAAd333422下一頁(yè)上一頁(yè)二、檢錯(cuò)和糾錯(cuò)的基本概念二、檢錯(cuò)和糾錯(cuò)的基本概念檢錯(cuò)：驗(yàn)證收到的碼字是否是需用碼字即可發(fā)現(xiàn)錯(cuò)誤

9、糾錯(cuò)：能判斷出錯(cuò)誤發(fā)生的位置，將其糾正下一頁(yè)上一頁(yè)三、（三、（n, k）分組碼的糾檢錯(cuò)能力）分組碼的糾檢錯(cuò)能力一個(gè)(n，k)分組碼的糾檢錯(cuò)能力由其最小碼距決定 ：1、要在一個(gè)碼組中檢出e個(gè)誤碼，要求 即任一碼組產(chǎn)生小于等于e個(gè)誤碼時(shí)，都不會(huì)變成另一準(zhǔn)用碼組。C Ci iC Cj je e1 1d dminmin下一頁(yè)上一頁(yè) 2、 要在一個(gè)碼組中能糾正t個(gè)誤碼，要求 d0 2t1 將以t為半徑的“球”內(nèi)所有的禁用碼組均判為球心中的準(zhǔn)用 碼組，可糾正t個(gè)以內(nèi)的錯(cuò)誤。C Ci iC Cj jt t1 1t td dminmin下一頁(yè)上一頁(yè) 3、 要在一個(gè)碼組中能糾正t個(gè)誤碼，同時(shí)檢出e (e t)

10、個(gè)誤碼 d0 et1 當(dāng)誤碼數(shù)小于等于t時(shí)，可糾正誤碼； 當(dāng)誤碼數(shù)大于t小于等于e時(shí)，不會(huì)落入另一碼組的糾錯(cuò)范 圍內(nèi)。C Ci iC Cj jt t1 1t td dm mi in ne e返回下一頁(yè)上一頁(yè)5.3 基于信道編碼的差錯(cuò)控制方式l在數(shù)據(jù)通信系統(tǒng)中，差錯(cuò)控制方式可以分為四種：反饋糾錯(cuò)（ARQ）、前向糾錯(cuò)（FEC）、混合糾錯(cuò)（HEC）和信息反饋（IRQ）四種。返回目錄下一頁(yè)上一頁(yè)一、檢錯(cuò)重發(fā)或反饋糾錯(cuò)（一、檢錯(cuò)重發(fā)或反饋糾錯(cuò)（ARQ）1、思路這種差錯(cuò)控制方式在發(fā)送端對(duì)數(shù)據(jù)序列進(jìn)行分組編碼，加入一定多余碼元使之具有一定的檢錯(cuò)能力，成為能夠發(fā)現(xiàn)錯(cuò)誤的碼組。接收端收到碼組后，按一定規(guī)則對(duì)其進(jìn)

11、行有無(wú)錯(cuò)誤的判別，并把判決結(jié)果（應(yīng)答信號(hào)）通過(guò)反向信道送回發(fā)送端。如有錯(cuò)誤，發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端認(rèn)為已正確接收到信息為止。下一頁(yè)上一頁(yè)2、重發(fā)方式在具體實(shí)現(xiàn)檢錯(cuò)重發(fā)系統(tǒng)時(shí)，通常有3 種形式：停止等候重發(fā)返回重發(fā)選擇重發(fā)下一頁(yè)上一頁(yè)（1）停止等候重發(fā)發(fā)送端每發(fā)送一個(gè)碼組，就停下來(lái)等候，發(fā)送端在Tw時(shí)間內(nèi)發(fā)送一個(gè)碼組，然后等候，等候時(shí)間為Td，再發(fā)送下一個(gè)碼組，TdTw+反饋時(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ā)送下一

12、個(gè)碼組；如果發(fā)送出錯(cuò)，則發(fā)送應(yīng)答信號(hào)為NAK，要求重發(fā)這個(gè)出錯(cuò)的碼組。示例動(dòng)畫演示下一頁(yè)上一頁(yè)（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è)碼組開始，把已經(jīng)發(fā)送出去的第2、3、4、5、6個(gè)碼組都要重發(fā)。示例動(dòng)畫演示下一頁(yè)上一頁(yè)（3）選擇重發(fā)發(fā)送端連續(xù)發(fā)送一個(gè)碼組

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

14、l若錯(cuò)誤超出糾錯(cuò)碼糾錯(cuò)能力,只好將其拋棄3、應(yīng)用l移動(dòng)通信系統(tǒng) 下一頁(yè)上一頁(yè)三、混合糾錯(cuò)檢錯(cuò)（三、混合糾錯(cuò)檢錯(cuò)（HEC） l1、思路l混合糾錯(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ā)。下一頁(yè)上一頁(yè)2、特點(diǎn)l集合了ARQ和FEC的優(yōu)點(diǎn)，在保證系統(tǒng)較高的有效性的同時(shí),大幅度提高了整個(gè)系統(tǒng)的可靠性3、應(yīng)用l移動(dòng)通信系統(tǒng) ，數(shù)據(jù)傳輸系統(tǒng)下一頁(yè)上一頁(yè)四、信息反饋（四、信息反饋（IRQ）1、思路l接收端把收到的數(shù)

15、據(jù)序列全部由反向信道送回發(fā)端，發(fā)端比較發(fā)送的數(shù)據(jù)序列與送回的數(shù)據(jù)序列，從而發(fā)現(xiàn)是否有錯(cuò)誤，并把認(rèn)為錯(cuò)誤的數(shù)據(jù)序列的原數(shù)據(jù)再次傳送，直到發(fā)端沒有發(fā)現(xiàn)錯(cuò)誤為止。2、特點(diǎn)l不需要糾錯(cuò)、檢錯(cuò)的編譯碼器，設(shè)備簡(jiǎn)單。l 需要和前向信道相同的反向信道，實(shí)時(shí)性差。l 發(fā)送端需要一定容量的存儲(chǔ)器以存儲(chǔ)發(fā)送碼組，環(huán)路時(shí)延越大，數(shù)據(jù)速率越高，所需存儲(chǔ)容量越大。返回下一頁(yè)上一頁(yè)5.4 常用的簡(jiǎn)單信道編碼l5.4.1 奇偶監(jiān)督碼l5.4.2 行列監(jiān)督碼l5.4.3 恒比碼l5.4.4 重復(fù)碼l5.4.5 正反碼返回目錄下一頁(yè)上一頁(yè)碼重為奇數(shù)或偶數(shù)的(n , n-1)系統(tǒng)分組碼)(0)(11010模二偶監(jiān)督模二奇監(jiān)督ni

16、iniiaa： 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)督碼返回下一頁(yè)上一頁(yè)對(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)督碼返回下一頁(yè)上一頁(yè)該碼的特點(diǎn)是碼字中1，0數(shù)目恒定，亦即1，0數(shù)目之比恒定。電傳通信中普遍采用3：2碼，又稱

17、5中取3碼，如下所示 國(guó)際上通用的ARQ電報(bào)通信系統(tǒng)中，采用7中取3碼。 5.4.3 恒比碼下一頁(yè)上一頁(yè)恒比碼的優(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ù)字序列返回下一頁(yè)上一頁(yè)(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)中。

18、重復(fù)碼只有一位信息碼元，監(jiān)督碼元是信息碼元的重復(fù)，所以僅有兩個(gè)碼字；5.4.4 重復(fù)碼返回下一頁(yè)上一頁(yè)該碼型多用于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 正反碼下一頁(yè)上一頁(yè)譯碼規(guī)則：首先將收到的碼字重的信息位和監(jiān)督位按對(duì)應(yīng)位作模2運(yùn)算，得到一個(gè)5位碼組，若該碼字中有奇數(shù)個(gè)1，則將其

19、作為校驗(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。下一頁(yè)上一頁(yè) 正反碼錯(cuò)誤判決表 校驗(yàn)碼組的

20、形式錯(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返回下一頁(yè)上一頁(yè)5.5 漢明碼及線性分組碼l5.5.1 線性分組碼l5.5.2 漢明碼返回目錄下一頁(yè)上一頁(yè)5.5.1 線性分組碼一、線性分組碼的定義一、線性分組碼的定義l線性碼是指信息位和監(jiān)督位滿足一組線性方程的碼；分組碼是監(jiān)督碼僅對(duì)本碼組起監(jiān)督作用，既是線性碼又是分組碼稱為線性分組碼。（n, k）線性分組碼，其碼字通常記作： A=an-1 an-2 a0 1n下一頁(yè)上一頁(yè)二、線性分組

21、碼的性質(zhì)二、線性分組碼的性質(zhì)（1）封閉性：指碼中任意兩許用碼組之和仍為一許用碼組。（2）線性分組碼中必有一個(gè)全0碼組（3）碼的最小距離等于非零碼的最小重量例：已知一個(gè)線性分組碼的碼組集合為： 000000，001110，010101，011011，100011，101101，110110，111000求該碼組集合的漢明距離。解：根據(jù)線性分組碼的性質(zhì)可以求出此碼組集合的漢明距離為3。下一頁(yè)上一頁(yè)三、線性分組碼編碼三、線性分組碼編碼1、生成矩陣對(duì)于一個(gè)（n, k）線性分組碼，其生成矩陣G是k行n列的矩陣，只要有k個(gè)線性無(wú)關(guān)的n元行矢量，都可以構(gòu)成生成矩陣G，生成矩陣不同，則得到的分組碼也不同。nk

22、nkkknnkgggggggggG1, 10, 10, 11, 110101,00100110ggg下一頁(yè)上一頁(yè)2、編碼原理已知(n, k)線性分組碼A=an-1 an-2 a0 1n，其信息碼組M=mk-1 mk-2 m1 m0 1k ，則編碼過(guò)程為：1, 10, 10, 11, 110101,00100021nkkknnkkgggggggggmmmMGA下一頁(yè)上一頁(yè)例：假設(shè)一個(gè)(6，3)分組碼生成矩陣為： 101100110010101011G編碼過(guò)程為： 1011001100101010110121020122012mmmmmmmmmmmmmMGA下一頁(yè)上一頁(yè)信息碼組M m2 m1 m0

23、碼字A a5 a4 a3 a2 a1 a0信息碼組M m2 m1 m0碼字A a5 a4 a3 a2 a1 a00 0 00 0 10 1 00 1 10 0 0 0 0 00 0 1 1 0 10 1 0 0 1 10 1 1 1 1 01 0 01 0 11 1 01 1 11 1 0 1 0 11 1 1 0 0 01 0 0 1 1 01 0 1 0 1 1根據(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)督位附加于其后

24、，則需要將生成矩陣G進(jìn)行典型化。下一頁(yè)上一頁(yè)生成矩陣典型化101100110010101011G101100110010011001G101100110010011001011202012012mmmmmmmmmmmmMGA編碼過(guò)程下一頁(yè)上一頁(yè)(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 a00 0 00 0 10 1 00 1 10 0 0 0 0 00 0 1 1 0 10 1 0 0 1 10 1 1 1 1 01 0 01 0 11 1 01

25、1 11 0 0 1 1 01 0 1 0 1 11 1 0 1 0 11 1 1 0 0 0011202012012345mmmmmmmmmaaaaaaA下一頁(yè)上一頁(yè)注意到系統(tǒng)碼中前k位即信息元，將其寫成線性方程組的形式034145235aaaaaaaaa監(jiān)督關(guān)系 000034145235aaaaaaaaa0100110010011001101012345aaaaaa下一頁(yè)上一頁(yè)監(jiān)督矩陣 監(jiān)督關(guān)系一般表達(dá) 100110010011001101H0THA0TAH或生成矩陣典型陣一般形式nkrkknkrkkkrrQIqqqqqqqqqG1, 11 , 10, 11, 111101, 001001

26、00000100001下一頁(yè)上一頁(yè)(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)置得： QIMMGAkTTkTTTMQIMGA下一頁(yè)上一頁(yè)即此時(shí)的系數(shù)矩陣，即監(jiān)督矩陣為 01000001000010211, 11, 11,01 , 111010, 11000aaaqqqqqqqqqnnrkrrkk1000001000011, 11, 11,01 , 111010, 11000rkrrkkqqqqqqqqqH下一頁(yè)上一頁(yè)生成矩陣和監(jiān)督距陣的關(guān)系(n，k

27、)碼的一般編碼過(guò)程0rkrkrrkrkkrkTrTkTQQIQQIIQQIIQQIGH0TGH0THG或 即 根據(jù)需要選定一監(jiān)督關(guān)系確定H陣； 求由H距陣和陣的關(guān)系確定G陣； 由A=MG生成所有碼字。 生成矩陣和監(jiān)督矩陣是正交下一頁(yè)上一頁(yè)3、伴隨式與檢錯(cuò)原理所謂錯(cuò)誤圖樣E，是由發(fā)送碼字A和接收碼字B進(jìn)行異或運(yùn)算得到，若E0，說(shuō)明傳輸無(wú)錯(cuò)，即碼字A與B相同，但是錯(cuò)誤圖樣只能夠反映的是信道噪聲的情況，接收端是不能依據(jù)其來(lái)檢錯(cuò)。實(shí)際上，判斷傳輸是否出錯(cuò)，可以將接收到的碼字B跟分組碼的碼字進(jìn)行比較，如果B是分組碼(n,k)的碼字，說(shuō)明傳輸無(wú)錯(cuò)。因此，這里定義了個(gè)伴隨式S錯(cuò)碼的碼字，判決傳輸出不是該錯(cuò)碼

28、的碼字，判決傳輸無(wú)是該)(0)(0knBknBBHST，伴隨式S和錯(cuò)誤圖樣E的關(guān)系 TTTTTEHEHAHHEABHS)(下一頁(yè)上一頁(yè)(6，3)分組碼的監(jiān)督矩陣為： 伴隨式 100110010011001101H034145235012345012100110010011001101bbbbbbbbbbbbbbbHBsssSTT下一頁(yè)上一頁(yè) (6，3)分組碼伴隨式計(jì)算電路 下一頁(yè)上一頁(yè)4、舉例（1）已知某線形碼監(jiān)督矩陣為 試列出所有的許用碼組下一頁(yè)上一頁(yè)（2）設(shè)（7，4）線形碼的生成矩陣：當(dāng)信息位為0001時(shí)，試求其后的監(jiān)督位。（3）求上題的監(jiān)督矩陣。返回下一頁(yè)上一頁(yè)5.5.2 漢明碼一、概念

29、一、概念漢明距是最早發(fā)現(xiàn)的具有糾錯(cuò)能力的碼，是一種編碼效率較高的分組碼，也是一種線性碼。對(duì)于任何的整數(shù)，必存在一個(gè)(n，k) 漢明碼，碼長(zhǎng)n和監(jiān)督元數(shù)目r=n-k滿足n=2r-1下一頁(yè)上一頁(yè)二、特點(diǎn)二、特點(diǎn)1、可以糾正一位傳輸錯(cuò)誤，且d0=32、碼長(zhǎng)和監(jiān)督元的關(guān)系：n=2r-1記為：（n，k）（ 2r-1，2r-1-r ） 漢明碼的編碼效率：rrrnk212下一頁(yè)上一頁(yè)將監(jiān)督矩陣記成列矢量的形式，H=h0 h1 hn-2 hn-1，則 0111, 11, 11,01 , 111010, 110000121100000100001eeeeqqqqqqqqqHEssssSrknnrkrrkkTrr

30、T10211201nnnnTeeeeShhhh單個(gè)錯(cuò)誤（所有的ei只有一位為1）時(shí)的伴隨式恰好與H的一個(gè)列矢量對(duì)應(yīng)，只要H的各個(gè)列矢量不為0矢量，且各不相同，則可以糾正單個(gè)錯(cuò)誤。三、伴隨式和錯(cuò)誤圖樣的關(guān)系三、伴隨式和錯(cuò)誤圖樣的關(guān)系下一頁(yè)上一頁(yè)四、實(shí)例分析四、實(shí)例分析(7，4)漢明碼漢明碼 首先其監(jiān)督矩陣，此時(shí)監(jiān)督矩陣為H37， 3位二進(jìn)制碼元的組合有8種： 000、001、010、011、100、101、110、111其中不全為零的7個(gè)正好可用作監(jiān)督矩陣的列,可得到監(jiān)督矩陣： 下一頁(yè)上一頁(yè)任意調(diào)換監(jiān)督矩陣各列位置并不影響碼的糾錯(cuò)能力，將其轉(zhuǎn)化成典型陣的形式，并由其可以得到生成矩陣G 10101

31、0111001101111000H100110101010110010111H1101000101010001100101110001G由A=MG得到其所有的碼字，如下表所示： 下一頁(yè)上一頁(yè)假設(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 a00 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 10 0 0

32、0 0 0 00 0 0 1 0 1 10 0 1 0 1 0 10 0 1 1 1 1 00 1 0 0 1 1 00 1 0 1 1 0 10 1 1 0 0 1 10 1 1 1 0 0 01 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 11 0 0 0 1 1 11 0 0 1 1 0 01 0 1 0 0 1 01 0 1 1 0 0 11 1 0 0 0 0 11 1 0 1 0 1 01 1 1 0 1 0 01 1 1 1 1 1 1下一頁(yè)上一頁(yè)下表給出了該（7，4）漢明碼單個(gè)錯(cuò)誤的錯(cuò)誤圖樣與其對(duì)應(yīng)的伴隨式，可以發(fā)現(xiàn)

33、伴隨式正是監(jiān)督矩陣的每一列，且該列的位置恰好是碼元出錯(cuò)的位置。 由于S不是全零，可判斷傳輸出錯(cuò)，而ST=0 1 1T，是監(jiān)督矩陣H的第4列,這正是錯(cuò)誤碼元發(fā)生的位置,因此可以得到錯(cuò)誤圖樣為E=0001000，進(jìn)而按B+E即可糾錯(cuò)。 1101110111100110101010110010111TTHBS下一頁(yè)上一頁(yè)錯(cuò)誤位置錯(cuò)誤圖樣Ee6 e5 e4 e3 e2 e1 e0伴隨式Ss2 s1 s0無(wú)錯(cuò)0 0 0 0 0 0 00 0 0b00 0 0 0 0 0 10 0 1b10 0 0 0 0 1 00 1 0b20 0 0 0 1 0 01 0 0b30 0 0 1 0 0 00 1 1b

34、40 0 1 0 0 0 01 0 1b50 1 0 0 0 0 01 1 0b61 0 0 0 0 0 01 1 1返回下一頁(yè)上一頁(yè)5.6 循環(huán)碼一、概念一、概念循環(huán)碼是一類重要的線性分組碼，若(an-1 an-2 a0)是循環(huán)碼的一個(gè)碼組，則循環(huán)移位后的碼組： (an-2 an-3 a0 an-1) (an-3 an-4 an-1 an-2) (a0 an-1 a2 a1)仍然是該編碼中的碼組。 返回目錄下一頁(yè)上一頁(yè)一個(gè)(7，3)系統(tǒng)循環(huán)碼 碼表如下所示：信息碼組Mm2 m1 m0碼字Aa6 a5 a4 a3 a2 a1 a0信息碼組Mm2 m1 m0碼字Aa6 a5 a4 a3 a2 a

35、1 a00 0 00 0 10 1 00 1 10 0 0 0 0 0 00 0 1 0 1 1 10 1 0 1 1 1 00 1 1 1 0 0 11 0 01 0 11 1 01 1 11 0 0 1 0 1 11 0 1 1 1 0 01 1 0 0 1 0 11 1 1 0 0 1 0表中第表中第2 2碼組向右移一位即得到第碼組向右移一位即得到第5 5碼組；第碼組；第5 5碼組向右移一碼組向右移一位即得到第位即得到第7 7碼組。碼組。 下一頁(yè)上一頁(yè)二、循環(huán)碼特點(diǎn)二、循環(huán)碼特點(diǎn)（1）封閉性：指碼中任意兩許用碼組之和仍為一許用碼組（2）線性分組碼中必有一個(gè)全0碼組（3）碼的最小距離等于非

36、零碼的最小重量（4）循環(huán)性：循環(huán)碼中任一許用碼字經(jīng)循環(huán)移位后，得到的新碼字仍為它的一個(gè)許用碼字。 下一頁(yè)上一頁(yè)三、循環(huán)碼的數(shù)學(xué)表示法三、循環(huán)碼的數(shù)學(xué)表示法1、碼多項(xiàng)式(n，k)循環(huán)碼中，為了便于描述與計(jì)算，經(jīng)常使用n-1次碼多項(xiàng)式來(lái)表示碼字，碼字A =an-1 an-2 a1 a0 ，它對(duì)應(yīng)的碼多項(xiàng)式為：上式中x 的值沒有任何意義，僅用它的冪代表碼元的位置01222211)(axaxaxaxaxAnnnn下一頁(yè)上一頁(yè)例如A4=0111001，對(duì)應(yīng)的碼多項(xiàng)式為 ：11001110)(345234564xxxxxxxxxxAA4向左循環(huán)移1位得A7=1110010，這相當(dāng)于將A4(x)乘以x，即

37、xxxxxxAxA45647)()(25677)(xxxxxxAA7向左循環(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)式 下一頁(yè)上一頁(yè)2、整數(shù)的按模運(yùn)算在整數(shù)運(yùn)算中，有模n運(yùn)算。例如，在模2運(yùn)算中，有1 + 1 = 2 0 (模2),1 + 2 = 3 1 (模2),2 3 = 6 0 (模2)。一般說(shuō)來(lái)，若一個(gè)整數(shù)m可以表示為式中，Q為整數(shù)，則在模n運(yùn)算下，有m p (模n)所以，在模n運(yùn)算下，一個(gè)整數(shù)m等于它被n除得的余數(shù)。npnpQnm,下一頁(yè)上一頁(yè)3、碼多

38、項(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 + 1 x4 +x2 + 1 x4 + x x2 +x +1 )()()()(xRxQxNxF）（模)()()(xNxRxF）（模) 1(133xx）（模) 1(113224xxxxx下一頁(yè)上一頁(yè)4、循環(huán)碼的數(shù)學(xué)表示法在循環(huán)碼中，設(shè)A(x)是一個(gè)長(zhǎng)度為n的碼組，即若則A (x)也是該編碼中的一個(gè)碼組。 例： 一循環(huán)碼為1100101，即 若給定 i =

39、3，則有 上式對(duì)應(yīng)的碼組為0101110，它正是A(x)向左移3位的結(jié)果。結(jié)論：一個(gè)長(zhǎng)為n的循環(huán)碼必定為按模(xn + 1)運(yùn)算的一個(gè)余式。 ）（模) 1()( )(nixxAxAx012211)(axaxaxaxAnnnn1)(256xxxxA）（模) 1()(723535893xxxxxxxxxxTx下一頁(yè)上一頁(yè)其計(jì)算過(guò)程如下 ：)() 1(1)(672567xAxxxxxxA模1111256725677xxxxxxxxxxxxxxA4567)(例如：下一頁(yè)上一頁(yè)四、生成多項(xiàng)式和生成矩陣四、生成多項(xiàng)式和生成矩陣1、生成多項(xiàng)式如果一種碼的所有碼多項(xiàng)式都是多項(xiàng)式g(x)的倍式，則稱g(x)為該

40、碼的生成多項(xiàng)式。在(n,k)循環(huán)碼中任意碼多項(xiàng)式A(x)都是最低次碼多項(xiàng)式的倍式。如(7,3)循環(huán)碼中， 1)()(2341xxxxAxg)()()(0)(270 xgxxAxgxA其它碼多項(xiàng)式都是g(x)的倍式， 即 下一頁(yè)上一頁(yè)在循環(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”的(nk)次多項(xiàng)式，而且這個(gè)g(x)還是這種(n, k)碼中次數(shù)為(nk)的唯一一個(gè)多項(xiàng)式。因?yàn)槿绻袃蓚€(gè)，則由碼的封閉性，把這兩個(gè)相加也應(yīng)該是一個(gè)碼組

41、，且此碼組多項(xiàng)式的次數(shù)將小于(nk)，即連續(xù)“0”的個(gè)數(shù)多于(k1)。顯然，這是與前面的結(jié)論矛盾的。我們稱這唯一的(nk)次多項(xiàng)式g(x)為碼的生成多項(xiàng)式。一旦確定了g(x)，則整個(gè)(n, k)循環(huán)碼就被確定了。下一頁(yè)上一頁(yè)因此，一個(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。 下一頁(yè)上一頁(yè)g(x) 、xg(x)、x2g(x)、xk-1g(x)是(n，k)循環(huán)碼的k個(gè)線性無(wú)關(guān)的碼字，所以可得其生成距陣G，用碼多項(xiàng)式表示G的各行： 2、生成矩陣若信息碼組M=

42、mk-1 mk-2 m0，則：)()()()()(21xgxxgxgxxgxxGkk)()()()()()(012211xgmxxgmxgxmxgxmxMGxAkkkk)()()(012211xgxMxgmxmxmxmkkkk下一頁(yè)上一頁(yè)例如：上表中的編碼為(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)號(hào)信息位信息位監(jiān)督位監(jiān)督位碼組編碼組編號(hào)號(hào)信息位信息位監(jiān)督位監(jiān)督位A6a5a4a3a2a1a0a6a5a

43、4A3a2a1a01000000051001011200101116101110030101110711001014011100181110010下一頁(yè)上一頁(yè)將此g(x)代入上矩陣，得到上式不符合G = Ik Q形式，所以它不是典型生成矩陣。但它經(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)。 1110100011101000111011)()()()(2423523462xxxxxxxxxxxxgxxgxgxxG下一頁(yè)上一頁(yè)3、舉例說(shuō)明已知循環(huán)碼的生成多項(xiàng)為 ，當(dāng)信息位

44、為1000時(shí)，寫出它的監(jiān)督位和整個(gè)碼組。解：由生成多項(xiàng)式可知n-k=3，而k=4，所以n71)(3xxxg1)()()()()()()()()(3242353462321xxxxxxxxxxxxgxxgxgxxgxxgxxgxgxxgxxGkk下一頁(yè)上一頁(yè)0001001001011011G011110100000 第1行+第3行+第4行 第1行0001001001011000G011110100101 第2行+第4行 第2行 0001001001001000G011110111101 非典型典型當(dāng)信息位為1000時(shí)，整個(gè)碼組為下一頁(yè)上一頁(yè)10003456GaaaaA00010010010010

45、000111101111011000101監(jiān)督位為 101下一頁(yè)上一頁(yè)系統(tǒng) (n，k)循環(huán)碼碼字： 編碼原理用碼多項(xiàng)式來(lái)表示為： 五、循環(huán)碼的編碼五、循環(huán)碼的編碼A =an-1 an-2 an-k ar-1 a1 a0 = mk-1 mk-2 m0 ar-1 a1 a0 01112211)(axaxaxaxaxaxArrknknnnnn011102211)(axaxaxmxmxmrrknkkkk)()(xrxxMkn下一頁(yè)上一頁(yè)式中M(x)是信息碼組碼多項(xiàng)式，所以只需要確定r(x) 已知循環(huán)碼的所有碼字都能夠被g(x)整除，r(x)可由下式確定：(n，k)循環(huán)碼的生成多項(xiàng)式為： )x(g)()(模knxxMxr 編碼器1)(12211 xgxgxgxxgrrr其