微機(jī)原理第10章

1、1通通 信信 原原 理理第第10章章 差錯(cuò)控制編碼差錯(cuò)控制編碼 2第10章 差錯(cuò)控制編碼10.1 概述概述差錯(cuò)控制編碼（差錯(cuò)控制編碼（糾錯(cuò)編碼或信道編碼糾錯(cuò)編碼或信道編碼）目的：克服由信道噪聲等加性干擾引起的誤碼，提高傳目的：克服由信道噪聲等加性干擾引起的誤碼，提高傳 輸?shù)目煽啃?。輸?shù)目煽啃?。原理：發(fā)端加上信道編碼器原理：發(fā)端加上信道編碼器-信息碼元序列信息碼元序列+ +監(jiān)督碼元監(jiān)督碼元 收端加上信道譯碼器收端加上信道譯碼器-檢錯(cuò)、糾錯(cuò)檢錯(cuò)、糾錯(cuò) 差錯(cuò)控制編碼（差錯(cuò)控制編碼（糾錯(cuò)編碼糾錯(cuò)編碼）是以犧牲有效性來(lái)?yè)Q取傳輸是以犧牲有效性來(lái)?yè)Q取傳輸 可靠性的提高?？煽啃缘奶岣?。 3第10章 差錯(cuò)控制編

2、碼n差錯(cuò)控制方式差錯(cuò)控制方式u信道分類(lèi)：從差錯(cuò)控制角度看信道分類(lèi)：從差錯(cuò)控制角度看隨機(jī)信道：錯(cuò)碼的出現(xiàn)是隨機(jī)的（白噪聲）隨機(jī)信道：錯(cuò)碼的出現(xiàn)是隨機(jī)的（白噪聲） 突發(fā)信道：錯(cuò)碼是成串集中出現(xiàn)（脈沖干擾）突發(fā)信道：錯(cuò)碼是成串集中出現(xiàn)（脈沖干擾）混合信道：既存在隨機(jī)錯(cuò)碼又存在突發(fā)錯(cuò)碼混合信道：既存在隨機(jī)錯(cuò)碼又存在突發(fā)錯(cuò)碼 u差錯(cuò)控制技術(shù)的種類(lèi)差錯(cuò)控制技術(shù)的種類(lèi)檢錯(cuò)重發(fā)（檢錯(cuò)重發(fā)（ARQ）前向糾錯(cuò)前向糾錯(cuò) (FEC)反饋校驗(yàn)反饋校驗(yàn)檢錯(cuò)刪除檢錯(cuò)刪除 4第10章 差錯(cuò)控制編碼n自動(dòng)要求重發(fā)自動(dòng)要求重發(fā)(ARQ)系統(tǒng)系統(tǒng)u3種種ARQ系統(tǒng)系統(tǒng)p停止等待停止等待ARQ系統(tǒng)系統(tǒng) 數(shù)據(jù)按分組發(fā)送。每發(fā)送一組數(shù)據(jù)

3、后發(fā)端等待接數(shù)據(jù)按分組發(fā)送。每發(fā)送一組數(shù)據(jù)后發(fā)端等待接收端的確認(rèn)收端的確認(rèn)(ACK)答復(fù)，然后再發(fā)送下一組數(shù)據(jù)。答復(fù)，然后再發(fā)送下一組數(shù)據(jù)。圖中的第圖中的第3組接收數(shù)據(jù)有誤，接收端發(fā)回一個(gè)否認(rèn)組接收數(shù)據(jù)有誤，接收端發(fā)回一個(gè)否認(rèn)(NAK)答復(fù)。這時(shí)，發(fā)送端將重發(fā)第答復(fù)。這時(shí)，發(fā)送端將重發(fā)第3組數(shù)據(jù)。組數(shù)據(jù)。系統(tǒng)是工作在半雙工狀態(tài)，時(shí)間沒(méi)有得到充分利系統(tǒng)是工作在半雙工狀態(tài)，時(shí)間沒(méi)有得到充分利用，傳輸效率較低。用，傳輸效率較低。 接收碼組接收碼組ACKACKACKACKNAKNAKACKACKACKACKNAKNAKACKACKt t1 12 23 33 34 45 55 5發(fā)送碼組發(fā)送碼組1 12

4、 23 33 34 45 55 56 6t t有錯(cuò)碼組有錯(cuò)碼組有錯(cuò)碼組有錯(cuò)碼組5第10章 差錯(cuò)控制編碼p拉后拉后ARQ系統(tǒng)系統(tǒng)發(fā)送端連續(xù)發(fā)送數(shù)據(jù)組，接收端對(duì)于每個(gè)接收到的發(fā)送端連續(xù)發(fā)送數(shù)據(jù)組，接收端對(duì)于每個(gè)接收到的數(shù)據(jù)組都發(fā)回?cái)?shù)據(jù)組都發(fā)回確認(rèn)確認(rèn)(ACK)或或否認(rèn)否認(rèn)(NAK)答復(fù)。答復(fù)。 例如，圖中第例如，圖中第5組接收數(shù)據(jù)有誤，則在發(fā)送端收到第組接收數(shù)據(jù)有誤，則在發(fā)送端收到第5組接收的否認(rèn)答復(fù)后，從第組接收的否認(rèn)答復(fù)后，從第5組開(kāi)始重發(fā)數(shù)據(jù)組。組開(kāi)始重發(fā)數(shù)據(jù)組。在這種系統(tǒng)中需要對(duì)發(fā)送的數(shù)據(jù)組和答復(fù)進(jìn)行編號(hào)，在這種系統(tǒng)中需要對(duì)發(fā)送的數(shù)據(jù)組和答復(fù)進(jìn)行編號(hào)，以便識(shí)別。這種系統(tǒng)需要雙工信道以便識(shí)別

5、。這種系統(tǒng)需要雙工信道 。接收數(shù)據(jù)接收數(shù)據(jù)有錯(cuò)碼組有錯(cuò)碼組有錯(cuò)碼組有錯(cuò)碼組9 91010 11111010 111112122 21 14 43 36 65 57 79 98 85 57 76 6ACKACK1 1NAKNAK5 5NAKNAK9 9ACKACK5 5發(fā)送數(shù)據(jù)發(fā)送數(shù)據(jù)5 57 76 69 95 52 21 14 43 36 67 79 98 81010 11111010 1111 1212重發(fā)碼組重發(fā)碼組重發(fā)碼組重發(fā)碼組6第10章 差錯(cuò)控制編碼p選擇重發(fā)選擇重發(fā)ARQ系統(tǒng)系統(tǒng)它只重發(fā)出錯(cuò)的數(shù)據(jù)組，因此進(jìn)一步提高了傳輸它只重發(fā)出錯(cuò)的數(shù)據(jù)組，因此進(jìn)一步提高了傳輸效率。效率。接收數(shù)據(jù)

6、接收數(shù)據(jù)有錯(cuò)碼組有錯(cuò)碼組有錯(cuò)碼組有錯(cuò)碼組9214365759810 11131412發(fā)送數(shù)據(jù)發(fā)送數(shù)據(jù)995852143671011131412重發(fā)碼組重發(fā)碼組重發(fā)碼組重發(fā)碼組NAK9ACK1NAK5ACK5ACK97第10章 差錯(cuò)控制編碼uARQ的主要優(yōu)點(diǎn)（的主要優(yōu)點(diǎn)（和前向糾錯(cuò)方法相比）：和前向糾錯(cuò)方法相比）：p監(jiān)督碼元較少即能使誤碼率降到很低，即碼率較高；監(jiān)督碼元較少即能使誤碼率降到很低，即碼率較高；p檢錯(cuò)的計(jì)算復(fù)雜度較低；檢錯(cuò)的計(jì)算復(fù)雜度較低；p檢錯(cuò)用的編碼方法和加性干擾的統(tǒng)計(jì)特性基本無(wú)關(guān)，檢錯(cuò)用的編碼方法和加性干擾的統(tǒng)計(jì)特性基本無(wú)關(guān)，能適應(yīng)不同特性的信道。能適應(yīng)不同特性的信道。uARQ

7、的主要缺點(diǎn)的主要缺點(diǎn)：p需要雙向信道來(lái)重發(fā)，不能用于單向信道，也不能用需要雙向信道來(lái)重發(fā)，不能用于單向信道，也不能用于一點(diǎn)到多點(diǎn)的通信系統(tǒng)。于一點(diǎn)到多點(diǎn)的通信系統(tǒng)。p因?yàn)橹匕l(fā)而使因?yàn)橹匕l(fā)而使ARQ系統(tǒng)的傳輸效率降低。系統(tǒng)的傳輸效率降低。p在信道干擾嚴(yán)重時(shí)，可能發(fā)生因不斷反復(fù)重發(fā)而造成在信道干擾嚴(yán)重時(shí)，可能發(fā)生因不斷反復(fù)重發(fā)而造成事實(shí)上的通信中斷。事實(shí)上的通信中斷。p在要求實(shí)時(shí)通信的場(chǎng)合，例如電話(huà)通信，往往不允許在要求實(shí)時(shí)通信的場(chǎng)合，例如電話(huà)通信，往往不允許使用使用ARQ法。法。8第10章 差錯(cuò)控制編碼uARQ系統(tǒng)的原理方框圖系統(tǒng)的原理方框圖9第10章 差錯(cuò)控制編碼 上述的差錯(cuò)控制，接收端如何識(shí)

8、別有無(wú)錯(cuò)碼？上述的差錯(cuò)控制，接收端如何識(shí)別有無(wú)錯(cuò)碼？ 采用差錯(cuò)控制編碼（采用差錯(cuò)控制編碼（糾錯(cuò)編碼糾錯(cuò)編碼） 發(fā)端加上信道編碼器發(fā)端加上信道編碼器-信息碼元序列信息碼元序列+ +監(jiān)督碼元監(jiān)督碼元 監(jiān)督碼元監(jiān)督碼元：發(fā)送端在信息碼元序列中增加的：發(fā)送端在信息碼元序列中增加的 一些冗余碼元一些冗余碼元 收端加上信道譯碼器收端加上信道譯碼器-檢錯(cuò)、糾錯(cuò)檢錯(cuò)、糾錯(cuò) 不同的編碼方法，有不同的檢錯(cuò)或糾錯(cuò)能力不同的編碼方法，有不同的檢錯(cuò)或糾錯(cuò)能力 本章重點(diǎn)討論常用的信道編碼和譯碼方法本章重點(diǎn)討論常用的信道編碼和譯碼方法 10第10章 差錯(cuò)控制編碼l10.2 糾錯(cuò)編碼的基本原理糾錯(cuò)編碼的基本原理 例如：用例如

9、：用1 1位二進(jìn)制碼可表示位二進(jìn)制碼可表示2 2種天氣，種天氣， 0-晴，晴， 1-雨雨 這種編碼這種編碼( (只有信息位只有信息位) )無(wú)檢、糾錯(cuò)能力無(wú)檢、糾錯(cuò)能力。（。（0 1或或1 0） 若用若用00-晴，晴， 11-雨雨 ，（，（01、10為禁用碼組）。為禁用碼組）。 這種編碼這種編碼( (附加附加1 1位監(jiān)督位位監(jiān)督位) )可檢可檢1 1位錯(cuò)。位錯(cuò)。 （00 10或或11 01） 若用若用000-晴，晴， 111-雨雨 ，（其它為，（其它為禁用碼組）。禁用碼組）。 這種編碼這種編碼( (附加附加2 2位監(jiān)督位位監(jiān)督位) )可糾可糾1 1位錯(cuò)，檢位錯(cuò)，檢2 2位和位和2 2位以下錯(cuò)。位

10、以下錯(cuò)。 可見(jiàn)：信息碼可見(jiàn)：信息碼+ +冗余的監(jiān)督碼元冗余的監(jiān)督碼元-檢錯(cuò)和糾錯(cuò)能力檢錯(cuò)和糾錯(cuò)能力11第10章 差錯(cuò)控制編碼u 糾錯(cuò)編碼的分類(lèi)糾錯(cuò)編碼的分類(lèi) (1) 線(xiàn)性碼和非線(xiàn)性碼線(xiàn)性碼和非線(xiàn)性碼 (2) 分組碼和卷積碼分組碼和卷積碼 。 (3) 檢錯(cuò)碼和糾錯(cuò)碼。檢錯(cuò)碼和糾錯(cuò)碼。 (4) 系統(tǒng)碼和非系統(tǒng)碼。系統(tǒng)碼和非系統(tǒng)碼。12第10章 差錯(cuò)控制編碼u分組碼的結(jié)構(gòu)分組碼的結(jié)構(gòu)p將信息碼分組，為每組信息碼附加若干監(jiān)督碼的編碼將信息碼分組，為每組信息碼附加若干監(jiān)督碼的編碼稱(chēng)為稱(chēng)為分組碼分組碼 。p在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。 p信息

11、位和監(jiān)督位的關(guān)系：舉例如下信息位和監(jiān)督位的關(guān)系：舉例如下信息位信息位監(jiān)督位監(jiān)督位晴晴00000 0云云01011 1陰陰10101 1雨雨11110 013第10章差錯(cuò)控制編碼分組碼的一般結(jié)構(gòu)分組碼的一般結(jié)構(gòu)u分組碼的符號(hào)：分組碼的符號(hào)：(n, k)pn 碼組的總位數(shù)，又稱(chēng)為碼組的長(zhǎng)度（碼長(zhǎng)），碼組的總位數(shù)，又稱(chēng)為碼組的長(zhǎng)度（碼長(zhǎng)），pk 碼組中信息碼元的數(shù)目，碼組中信息碼元的數(shù)目，pn k r 碼組中的監(jiān)督碼元數(shù)目，或稱(chēng)監(jiān)督位數(shù)目。碼組中的監(jiān)督碼元數(shù)目，或稱(chēng)監(jiān)督位數(shù)目。u編碼效率編碼效率(簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)碼率碼率) ： R = k/ / n = 1- r/ / nu冗余度冗余度：r /k = (n-

12、k)/k an 1an 2arar 1a0時(shí) 間k個(gè) 信 息 位r個(gè) 監(jiān) 督 位碼 長(zhǎng)nkr14第10章差錯(cuò)控制編碼u分組碼的碼重和碼距分組碼的碼重和碼距p碼重碼重：碼組中：碼組中“1”的數(shù)目稱(chēng)為碼組的重量，簡(jiǎn)稱(chēng)碼重。的數(shù)目稱(chēng)為碼組的重量，簡(jiǎn)稱(chēng)碼重。 例如：碼組例如：碼組1011001的碼重為的碼重為4p碼距碼距：兩個(gè)碼組中對(duì)應(yīng)位上數(shù)字不同的位數(shù)稱(chēng)為：兩個(gè)碼組中對(duì)應(yīng)位上數(shù)字不同的位數(shù)稱(chēng)為 碼組的距離，簡(jiǎn)稱(chēng)碼距。碼距又稱(chēng)漢明距離。碼組的距離，簡(jiǎn)稱(chēng)碼距。碼距又稱(chēng)漢明距離。 例如：例如：“000”晴，晴，“011”云，云，“101”陰陰 “110”雨，任意兩個(gè)碼組的距離均為雨，任意兩個(gè)碼組的距離均為

13、2。p最小碼距最小碼距：把某種編碼中各個(gè)碼組之間距離的最小值：把某種編碼中各個(gè)碼組之間距離的最小值稱(chēng)為最小碼距稱(chēng)為最小碼距(d0)。例如，上面編碼的最小碼距。例如，上面編碼的最小碼距d0 = 2。p最小碼距是一個(gè)重要參數(shù)，它直接關(guān)系到某種編碼的最小碼距是一個(gè)重要參數(shù)，它直接關(guān)系到某種編碼的檢錯(cuò)、糾錯(cuò)能力檢錯(cuò)、糾錯(cuò)能力。 15第10章 差錯(cuò)控制編碼u碼距的幾何意義碼距的幾何意義p每個(gè)碼組的每個(gè)碼組的3個(gè)碼元的值個(gè)碼元的值(a1, a2, a3)就是此立方體各頂點(diǎn)的就是此立方體各頂點(diǎn)的坐標(biāo)。而上述碼距概念在此圖中就對(duì)應(yīng)于各頂點(diǎn)之間沿立坐標(biāo)。而上述碼距概念在此圖中就對(duì)應(yīng)于各頂點(diǎn)之間沿立方體各邊行走的

14、幾何距離。方體各邊行走的幾何距離。p由此圖可以直觀(guān)看出，上例中由此圖可以直觀(guān)看出，上例中4個(gè)準(zhǔn)用碼組之間的距離均個(gè)準(zhǔn)用碼組之間的距離均為為2。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a116第10章 差錯(cuò)控制編碼u碼距和檢糾錯(cuò)能力的關(guān)系碼距和檢糾錯(cuò)能力的關(guān)系 最小碼距最小碼距d d0 0直接關(guān)系著碼的檢錯(cuò)和糾錯(cuò)能力；任一直接關(guān)系著碼的檢錯(cuò)和糾錯(cuò)能力；任一( (n,k) )分組碼，若要在碼字內(nèi)分組碼，若要在碼字內(nèi): : (1) 檢測(cè)檢測(cè)e個(gè)隨機(jī)錯(cuò)碼，則要求最小碼距個(gè)隨機(jī)錯(cuò)碼，則要求最小碼距 d0e+1; (2) 糾正

15、糾正t個(gè)隨機(jī)錯(cuò)碼，則要求最小碼距個(gè)隨機(jī)錯(cuò)碼，則要求最小碼距d02t+1; (3) 糾正糾正t t個(gè)同時(shí)檢測(cè)個(gè)同時(shí)檢測(cè)e( (t) )個(gè)隨機(jī)錯(cuò)碼，則要求最小個(gè)隨機(jī)錯(cuò)碼，則要求最小碼距碼距 d0t+e+1。 17第10章 差錯(cuò)控制編碼u碼距和檢糾錯(cuò)能力的關(guān)系碼距和檢糾錯(cuò)能力的關(guān)系 【證【證1】設(shè)一個(gè)碼組】設(shè)一個(gè)碼組A位于位于O點(diǎn)。若碼組點(diǎn)。若碼組A中發(fā)生一個(gè)錯(cuò)碼，中發(fā)生一個(gè)錯(cuò)碼，則我們可以認(rèn)為則我們可以認(rèn)為A的位置將移動(dòng)至以的位置將移動(dòng)至以O(shè)點(diǎn)為圓心，以點(diǎn)為圓心，以1為為半徑的圓上某點(diǎn)，但其位置不會(huì)超出此圓。半徑的圓上某點(diǎn)，但其位置不會(huì)超出此圓。 若碼組若碼組A中發(fā)生兩位錯(cuò)碼，則其位置不會(huì)超出以中

16、發(fā)生兩位錯(cuò)碼，則其位置不會(huì)超出以O(shè)點(diǎn)為圓點(diǎn)為圓心，以心，以2為半徑的圓。因此，只要最小碼距不小于為半徑的圓。因此，只要最小碼距不小于3，碼，碼組組A發(fā)生兩位以下錯(cuò)碼時(shí)，發(fā)生兩位以下錯(cuò)碼時(shí)，不可能變成另一個(gè)準(zhǔn)用不可能變成另一個(gè)準(zhǔn)用碼組，因而能檢測(cè)錯(cuò)碼碼組，因而能檢測(cè)錯(cuò)碼的位數(shù)等于的位數(shù)等于2。 0123BA漢明距離漢明距離ed018第10章 差錯(cuò)控制編碼 【證【證2】圖中畫(huà)出碼組】圖中畫(huà)出碼組A和和B的距離為的距離為5。碼組。碼組A或或B若發(fā)生不若發(fā)生不多于兩位錯(cuò)碼，則其位置均不會(huì)超出半徑為多于兩位錯(cuò)碼，則其位置均不會(huì)超出半徑為2以原位置為圓以原位置為圓心的圓。這兩個(gè)圓是不重疊的。判決規(guī)則為：若

17、接收碼組心的圓。這兩個(gè)圓是不重疊的。判決規(guī)則為：若接收碼組落于以落于以A為圓心的圓上就判決收到的是碼組為圓心的圓上就判決收到的是碼組A，若落于以，若落于以B為圓心的圓上就判決為碼組為圓心的圓上就判決為碼組B。這樣，就能夠糾這樣，就能夠糾正兩位錯(cuò)碼。正兩位錯(cuò)碼。 BtA漢明距離漢明距離012345td019第10章 差錯(cuò)控制編碼 若這種編碼中除碼組若這種編碼中除碼組A和和B外，還有許多種不同碼組，外，還有許多種不同碼組，但任兩碼組之間的碼距均不小于但任兩碼組之間的碼距均不小于5，則以各碼組的位置為中，則以各碼組的位置為中心以心以2為半徑畫(huà)出之圓都不會(huì)互相重疊。這樣，每種碼組如為半徑畫(huà)出之圓都不會(huì)

18、互相重疊。這樣，每種碼組如果發(fā)生不超過(guò)兩位錯(cuò)碼都將能被糾正。因此，當(dāng)最小碼距果發(fā)生不超過(guò)兩位錯(cuò)碼都將能被糾正。因此，當(dāng)最小碼距d05時(shí)，能夠糾正時(shí)，能夠糾正2個(gè)錯(cuò)碼，且最多能糾正個(gè)錯(cuò)碼，且最多能糾正2個(gè)。若錯(cuò)碼達(dá)個(gè)。若錯(cuò)碼達(dá)到到3個(gè)，就將落入另一圓上，從而發(fā)生錯(cuò)判。故一般說(shuō)來(lái)，個(gè)，就將落入另一圓上，從而發(fā)生錯(cuò)判。故一般說(shuō)來(lái)，為糾正為糾正t個(gè)錯(cuò)碼，最小碼距應(yīng)不小于個(gè)錯(cuò)碼，最小碼距應(yīng)不小于(2t + 1)。20第10章 差錯(cuò)控制編碼p圖中碼組圖中碼組A和和B之間距離為之間距離為5。按照檢錯(cuò)能力公式，最多能檢。按照檢錯(cuò)能力公式，最多能檢測(cè)測(cè)4個(gè)錯(cuò)碼，即個(gè)錯(cuò)碼，即e = d0 1 = 5 1 = 4，

19、按照糾錯(cuò)能力公式糾錯(cuò)，按照糾錯(cuò)能力公式糾錯(cuò)時(shí)，能糾正時(shí)，能糾正2個(gè)錯(cuò)碼。但是，不能同時(shí)作到兩者，因?yàn)楫?dāng)錯(cuò)個(gè)錯(cuò)碼。但是，不能同時(shí)作到兩者，因?yàn)楫?dāng)錯(cuò)碼位數(shù)超過(guò)糾錯(cuò)能力時(shí)，該碼組立即進(jìn)入另一碼組的圓內(nèi)而碼位數(shù)超過(guò)糾錯(cuò)能力時(shí)，該碼組立即進(jìn)入另一碼組的圓內(nèi)而被錯(cuò)誤地被錯(cuò)誤地“糾正糾正”了。例如，碼組了。例如，碼組A若錯(cuò)了若錯(cuò)了3位，就會(huì)被誤認(rèn)位，就會(huì)被誤認(rèn)為碼組為碼組B錯(cuò)了錯(cuò)了2位造成的結(jié)果，從而被位造成的結(jié)果，從而被錯(cuò)錯(cuò)“糾糾”為為B。這就。這就是說(shuō)，檢錯(cuò)和糾錯(cuò)是說(shuō)，檢錯(cuò)和糾錯(cuò)公式不能同時(shí)成立公式不能同時(shí)成立或同時(shí)運(yùn)用?；蛲瑫r(shí)運(yùn)用。 BtA漢明距離012345td021第10章 差錯(cuò)控制編碼 所以，為

20、了在可以糾正所以，為了在可以糾正t個(gè)錯(cuò)碼的同時(shí)，能夠檢測(cè)個(gè)錯(cuò)碼的同時(shí)，能夠檢測(cè)e個(gè)個(gè)錯(cuò)碼，就需要像下圖所示那樣，使某一碼組（譬如碼組錯(cuò)碼，就需要像下圖所示那樣，使某一碼組（譬如碼組A）發(fā)生發(fā)生e個(gè)錯(cuò)誤之后所處的位置，與其他碼組（譬如碼組個(gè)錯(cuò)誤之后所處的位置，與其他碼組（譬如碼組B）的糾錯(cuò)圓圈至少距離等于的糾錯(cuò)圓圈至少距離等于1，不然將落在該糾錯(cuò)圓上從而，不然將落在該糾錯(cuò)圓上從而發(fā)生錯(cuò)誤地發(fā)生錯(cuò)誤地“糾正糾正”。因此，由此圖可以直觀(guān)看出，要求。因此，由此圖可以直觀(guān)看出，要求最小碼距最小碼距這種糾錯(cuò)和檢錯(cuò)結(jié)合的工作方式簡(jiǎn)稱(chēng)這種糾錯(cuò)和檢錯(cuò)結(jié)合的工作方式簡(jiǎn)稱(chēng)糾檢結(jié)合糾檢結(jié)合。 ABe1tt漢明距離)(

21、10teted22第10章 差錯(cuò)控制編碼這種工作方式是自動(dòng)在糾錯(cuò)和檢錯(cuò)之間轉(zhuǎn)換的。當(dāng)錯(cuò)碼這種工作方式是自動(dòng)在糾錯(cuò)和檢錯(cuò)之間轉(zhuǎn)換的。當(dāng)錯(cuò)碼數(shù)量少時(shí)，系統(tǒng)按前向糾錯(cuò)方式工作，以節(jié)省重發(fā)時(shí)間，數(shù)量少時(shí)，系統(tǒng)按前向糾錯(cuò)方式工作，以節(jié)省重發(fā)時(shí)間，提高傳輸效率；當(dāng)錯(cuò)碼數(shù)量多時(shí)，系統(tǒng)按反饋重發(fā)方式提高傳輸效率；當(dāng)錯(cuò)碼數(shù)量多時(shí)，系統(tǒng)按反饋重發(fā)方式糾錯(cuò)，以降低系統(tǒng)的總誤碼率。所以，它適用于大多數(shù)糾錯(cuò)，以降低系統(tǒng)的總誤碼率。所以，它適用于大多數(shù)時(shí)間中錯(cuò)碼數(shù)量很少，少數(shù)時(shí)間中錯(cuò)碼數(shù)量多的情況。時(shí)間中錯(cuò)碼數(shù)量很少，少數(shù)時(shí)間中錯(cuò)碼數(shù)量多的情況。23第10章 差錯(cuò)控制編碼l10.3 糾錯(cuò)編碼的性能糾錯(cuò)編碼的性能n系統(tǒng)帶寬

22、和信噪比的矛盾系統(tǒng)帶寬和信噪比的矛盾u由上節(jié)所述的糾錯(cuò)編碼原理可知，為了減少接收錯(cuò)由上節(jié)所述的糾錯(cuò)編碼原理可知，為了減少接收錯(cuò)誤碼元數(shù)量，需要在發(fā)送信息碼元序列中加入監(jiān)督誤碼元數(shù)量，需要在發(fā)送信息碼元序列中加入監(jiān)督碼元。這樣作的結(jié)果使發(fā)送序列增長(zhǎng)，冗余度增大。碼元。這樣作的結(jié)果使發(fā)送序列增長(zhǎng)，冗余度增大。若仍須保持發(fā)送信息碼元速率不變，則傳輸速率必若仍須保持發(fā)送信息碼元速率不變，則傳輸速率必須增大，因而增大了系統(tǒng)帶寬。系統(tǒng)帶寬的增大將須增大，因而增大了系統(tǒng)帶寬。系統(tǒng)帶寬的增大將引起系統(tǒng)中噪聲功率增大，使信噪比下降。信噪比引起系統(tǒng)中噪聲功率增大，使信噪比下降。信噪比的下降反而又使系統(tǒng)接收碼元序列

23、中的錯(cuò)碼增多。的下降反而又使系統(tǒng)接收碼元序列中的錯(cuò)碼增多。一般說(shuō)來(lái)，采用糾錯(cuò)編碼后，誤碼率總是能夠得到一般說(shuō)來(lái)，采用糾錯(cuò)編碼后，誤碼率總是能夠得到很大改善的。改善的程度和所用的編碼有關(guān)很大改善的。改善的程度和所用的編碼有關(guān)。24第10章 差錯(cuò)控制編碼u編碼性能舉例編碼性能舉例p未采用糾錯(cuò)編碼時(shí)，未采用糾錯(cuò)編碼時(shí)，若接收信噪比等于若接收信噪比等于7dB，編碼前誤碼率，編碼前誤碼率約為約為8 10-4，圖中，圖中A點(diǎn)，在采用糾錯(cuò)編碼點(diǎn)，在采用糾錯(cuò)編碼后，誤碼率降至約后，誤碼率降至約4 10-5，圖中，圖中B點(diǎn)。這樣，點(diǎn)。這樣，不增大發(fā)送功率就能不增大發(fā)送功率就能降低誤碼率約一個(gè)半降低誤碼率約一個(gè)半

24、數(shù)量級(jí)。數(shù)量級(jí)。10-610-510-410-310-210-1編碼后PeCDEAB信噪比信噪比 (dB)25第10章 差錯(cuò)控制編碼l10.4 簡(jiǎn)單的實(shí)用編碼簡(jiǎn)單的實(shí)用編碼n10.4.1 奇偶監(jiān)督碼奇偶監(jiān)督碼 奇偶監(jiān)督碼是在原信息碼后面附加奇偶監(jiān)督碼是在原信息碼后面附加一個(gè)監(jiān)督一個(gè)監(jiān)督位位，使得碼組中，使得碼組中“1”的個(gè)數(shù)是奇數(shù)或偶數(shù)。奇偶的個(gè)數(shù)是奇數(shù)或偶數(shù)。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。 奇偶監(jiān)督碼可檢測(cè)出奇偶監(jiān)督碼可檢測(cè)出奇數(shù)個(gè)奇數(shù)個(gè)錯(cuò)碼，它的編碼錯(cuò)碼，它的編碼效率效率R為為 nnR/ )1( 26第10章 差錯(cuò)控制編碼設(shè)碼字設(shè)碼字A=an-1,an

25、-2,a1,a0，對(duì)對(duì)偶監(jiān)督偶監(jiān)督碼有碼有 0121aaaaSnn 監(jiān)督碼元監(jiān)督碼元a0可以由下式確定可以由下式確定 1210aaaann 接收端譯碼時(shí)就是計(jì)算接收端譯碼時(shí)就是計(jì)算00121 aaaann若若S為為“0”，則判定為無(wú)錯(cuò)碼則判定為無(wú)錯(cuò)碼；若若S為為“1”，則判定該碼則判定該碼組經(jīng)傳輸后有奇數(shù)個(gè)錯(cuò)碼組經(jīng)傳輸后有奇數(shù)個(gè)錯(cuò)碼。 S稱(chēng)為校正子稱(chēng)為校正子27第10章 差錯(cuò)控制編碼 奇監(jiān)督碼情況相似，只是碼組中奇監(jiān)督碼情況相似，只是碼組中“1”的數(shù)目為奇數(shù)，的數(shù)目為奇數(shù)，即滿(mǎn)足條件即滿(mǎn)足條件而檢錯(cuò)能力與偶監(jiān)督碼相同而檢錯(cuò)能力與偶監(jiān)督碼相同。 例如，在例如，在A(yíng)SCII碼中，通常采用碼中，通常

26、采用7位二進(jìn)制碼元來(lái)表位二進(jìn)制碼元來(lái)表示示128種字符。傳輸時(shí)再加上一個(gè)奇偶監(jiān)督位，種字符。傳輸時(shí)再加上一個(gè)奇偶監(jiān)督位，8 8位碼組。位碼組。 這種編碼能檢測(cè)奇數(shù)個(gè)錯(cuò)碼這種編碼能檢測(cè)奇數(shù)個(gè)錯(cuò)碼 10121 aaaann28第10章 差錯(cuò)控制編碼n10.4.2 二維奇偶監(jiān)督碼（方陣碼）二維奇偶監(jiān)督碼（方陣碼）u二維奇偶監(jiān)督碼的構(gòu)成二維奇偶監(jiān)督碼的構(gòu)成圖中圖中a01 a02 a0m為為m行行奇偶監(jiān)督碼中的奇偶監(jiān)督碼中的m個(gè)監(jiān)督位個(gè)監(jiān)督位。cn-1 cn-2 c1 c0為按為按列列進(jìn)行第二次編碼所增加的進(jìn)行第二次編碼所增加的監(jiān)督位監(jiān)督位，們構(gòu)成了一監(jiān)督位行。們構(gòu)成了一監(jiān)督位行。11111210222

27、2121012101210nnnnmmmmnnnnaaaaaaaaacccc aaa29第10章差錯(cuò)控制編碼110010100000100001101001111000011100111000001010101010111000111100二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼(66 , 50) 30第10章 差錯(cuò)控制編碼u二維奇偶監(jiān)督碼的性能二維奇偶監(jiān)督碼的性能p這種編碼有可能這種編碼有可能檢測(cè)偶數(shù)檢測(cè)偶數(shù)個(gè)錯(cuò)碼。因?yàn)槊啃械谋O(jiān)督位個(gè)錯(cuò)碼。因?yàn)槊啃械谋O(jiān)督位雖然不能用于檢測(cè)本行中的偶數(shù)個(gè)錯(cuò)碼，但按列的方雖然不能用于檢測(cè)本行中的偶數(shù)個(gè)錯(cuò)碼，但按列的方向有可能由向有可能由cn-1 cn-2 c1 c0等監(jiān)督位

28、檢測(cè)出來(lái)。有一些等監(jiān)督位檢測(cè)出來(lái)。有一些偶數(shù)錯(cuò)碼不可能檢測(cè)出來(lái)。例如，構(gòu)成矩形的偶數(shù)錯(cuò)碼不可能檢測(cè)出來(lái)。例如，構(gòu)成矩形的4個(gè)錯(cuò)碼。個(gè)錯(cuò)碼。p這種二維奇偶監(jiān)督碼適于檢測(cè)突發(fā)錯(cuò)碼。因?yàn)橥话l(fā)錯(cuò)這種二維奇偶監(jiān)督碼適于檢測(cè)突發(fā)錯(cuò)碼。因?yàn)橥话l(fā)錯(cuò)碼常常成串出現(xiàn)，隨后有較長(zhǎng)一段無(wú)錯(cuò)區(qū)間。碼常常成串出現(xiàn)，隨后有較長(zhǎng)一段無(wú)錯(cuò)區(qū)間。p由于方陣碼只對(duì)構(gòu)成矩形四角的錯(cuò)碼無(wú)法檢測(cè)，故其由于方陣碼只對(duì)構(gòu)成矩形四角的錯(cuò)碼無(wú)法檢測(cè)，故其檢錯(cuò)能力較強(qiáng)。檢錯(cuò)能力較強(qiáng)。 p二維奇偶監(jiān)督碼不僅可用來(lái)檢錯(cuò)，還可以用來(lái)二維奇偶監(jiān)督碼不僅可用來(lái)檢錯(cuò)，還可以用來(lái)糾正糾正一一些些錯(cuò)碼錯(cuò)碼。 例如，僅在一行中有奇數(shù)個(gè)錯(cuò)碼時(shí)。例如，僅在一行中有奇數(shù)

29、個(gè)錯(cuò)碼時(shí)。31第10章 差錯(cuò)控制編碼n 10.4.3 恒比碼恒比碼u在恒比碼中，在恒比碼中，每個(gè)碼組均含有相同數(shù)目的每個(gè)碼組均含有相同數(shù)目的“1”（和（和“0”）。）?！?”的數(shù)目與的數(shù)目與“0”的數(shù)目之比保持恒定，的數(shù)目之比保持恒定，故得此名。故得此名。u這種碼在檢測(cè)時(shí)，只要計(jì)算接收碼組中這種碼在檢測(cè)時(shí)，只要計(jì)算接收碼組中“1”的數(shù)目的數(shù)目是否對(duì)，就知道有無(wú)錯(cuò)碼。是否對(duì)，就知道有無(wú)錯(cuò)碼。u恒比碼的主要優(yōu)點(diǎn)是簡(jiǎn)單和適于用來(lái)傳輸電傳機(jī)或恒比碼的主要優(yōu)點(diǎn)是簡(jiǎn)單和適于用來(lái)傳輸電傳機(jī)或其他鍵盤(pán)設(shè)備產(chǎn)生的字母和符號(hào)。對(duì)于信源來(lái)的二其他鍵盤(pán)設(shè)備產(chǎn)生的字母和符號(hào)。對(duì)于信源來(lái)的二進(jìn)制隨機(jī)數(shù)字序列，這種碼就不適

30、合使用了。進(jìn)制隨機(jī)數(shù)字序列，這種碼就不適合使用了。32第10章 差錯(cuò)控制編碼 3:2 恒比碼恒比碼阿拉伯?dāng)?shù)字阿拉伯?dāng)?shù)字碼字碼字阿拉伯?dāng)?shù)字阿拉伯?dāng)?shù)字碼字碼字10101161010121100171110031011080111041101091001150011100110133第10章 差錯(cuò)控制編碼n10.4.4 正反碼正反碼 它是一種簡(jiǎn)單的能夠糾正錯(cuò)碼的編碼。其中的監(jiān)督它是一種簡(jiǎn)單的能夠糾正錯(cuò)碼的編碼。其中的監(jiān)督位數(shù)目與信息位數(shù)目相同。位數(shù)目與信息位數(shù)目相同。 其編碼規(guī)則為其編碼規(guī)則為：當(dāng)信息位中有奇數(shù)個(gè)當(dāng)信息位中有奇數(shù)個(gè)“1”時(shí)，監(jiān)督位是信息位的重復(fù)；時(shí)，監(jiān)督位是信息位的重復(fù)；當(dāng)信息位中有

31、偶數(shù)個(gè)當(dāng)信息位中有偶數(shù)個(gè)“1”時(shí)，監(jiān)督位是信息位的反碼。時(shí)，監(jiān)督位是信息位的反碼。 例如例如:若信息位為若信息位為11001，則正反碼為，則正反碼為11001 11001； 若信息位為若信息位為10001, 則正反碼為則正反碼為10001 01110。34第10章 差錯(cuò)控制編碼u正反碼的解碼正反碼的解碼p在上例中，先將接收碼組中信息位和監(jiān)督位按模在上例中，先將接收碼組中信息位和監(jiān)督位按模 2 相相加，得到一個(gè)加，得到一個(gè)5位的合成碼組。然后，由此合成碼組產(chǎn)位的合成碼組。然后，由此合成碼組產(chǎn)生一個(gè)校驗(yàn)碼組。生一個(gè)校驗(yàn)碼組。p若接收碼組的信息位中有奇數(shù)個(gè)若接收碼組的信息位中有奇數(shù)個(gè)“1”，則合成碼

32、組就，則合成碼組就是校驗(yàn)碼組；若接收碼組的信息位中有偶數(shù)個(gè)是校驗(yàn)碼組；若接收碼組的信息位中有偶數(shù)個(gè)“1”，則取合成碼組的反碼作為校驗(yàn)碼組。則取合成碼組的反碼作為校驗(yàn)碼組。p最后，觀(guān)察校驗(yàn)碼組中最后，觀(guān)察校驗(yàn)碼組中“1”的個(gè)數(shù)，按下表進(jìn)行判決的個(gè)數(shù)，按下表進(jìn)行判決及糾正可能發(fā)現(xiàn)的錯(cuò)碼。及糾正可能發(fā)現(xiàn)的錯(cuò)碼。 35第10章 差錯(cuò)控制編碼p校驗(yàn)碼組和錯(cuò)碼的關(guān)系校驗(yàn)碼組和錯(cuò)碼的關(guān)系例如，若發(fā)送碼組為例如，若發(fā)送碼組為1100111001，接收碼組中，接收碼組中無(wú)錯(cuò)無(wú)錯(cuò)碼，碼，則合成碼組應(yīng)為則合成碼組應(yīng)為11001 11001=00000。由于接收碼組。由于接收碼組信息位中有奇數(shù)個(gè)信息位中有奇數(shù)個(gè)“1”

33、，所以校驗(yàn)碼組就是，所以校驗(yàn)碼組就是00000。按。按上表判決，結(jié)論是無(wú)錯(cuò)碼。上表判決，結(jié)論是無(wú)錯(cuò)碼。 校驗(yàn)碼組的組成校驗(yàn)碼組的組成錯(cuò)碼情況錯(cuò)碼情況1全為全為“0”無(wú)錯(cuò)碼無(wú)錯(cuò)碼2有有4個(gè)個(gè)“1”和和1個(gè)個(gè)“0”信息碼中有信息碼中有1位錯(cuò)碼，其位置對(duì)應(yīng)校驗(yàn)碼組中位錯(cuò)碼，其位置對(duì)應(yīng)校驗(yàn)碼組中“0”的位置的位置3有有4個(gè)個(gè)“0”和和1個(gè)個(gè)“1”監(jiān)督碼中有監(jiān)督碼中有1位錯(cuò)碼，其位置對(duì)應(yīng)校驗(yàn)碼組中位錯(cuò)碼，其位置對(duì)應(yīng)校驗(yàn)碼組中“1”的位置的位置4其他組成其他組成錯(cuò)碼多于錯(cuò)碼多于1個(gè)個(gè)36第10章 差錯(cuò)控制編碼p若傳輸中產(chǎn)生了差錯(cuò)，使接收碼組變成若傳輸中產(chǎn)生了差錯(cuò)，使接收碼組變成1000111001，則合成

34、，則合成碼組為碼組為10001 1100101000。由于接收碼組中信息位有偶。由于接收碼組中信息位有偶數(shù)個(gè)數(shù)個(gè)“1”，所以校驗(yàn)碼組應(yīng)取合成碼組的反碼，即，所以校驗(yàn)碼組應(yīng)取合成碼組的反碼，即10111。按上表判斷信息位中左邊第按上表判斷信息位中左邊第2位為錯(cuò)碼。位為錯(cuò)碼。p若接收碼組為若接收碼組為1001111001，則合成碼組為，則合成碼組為10011 1100101010，校驗(yàn)碼組與其相同，按上表判斷，這時(shí)錯(cuò)碼多于，校驗(yàn)碼組與其相同，按上表判斷，這時(shí)錯(cuò)碼多于1個(gè)。個(gè)。p上述長(zhǎng)度為上述長(zhǎng)度為10的正反碼具有糾正的正反碼具有糾正1位錯(cuò)碼的能力，并能檢測(cè)位錯(cuò)碼的能力，并能檢測(cè)全部全部2位以下的錯(cuò)

35、碼和大部分位以下的錯(cuò)碼和大部分2位以上的錯(cuò)碼。位以上的錯(cuò)碼。37第10章 差錯(cuò)控制編碼l 10.5 線(xiàn)性分組碼線(xiàn)性分組碼n基本概念基本概念u代數(shù)碼代數(shù)碼：建立在代數(shù)學(xué)基礎(chǔ)上的編碼。建立在代數(shù)學(xué)基礎(chǔ)上的編碼。u線(xiàn)性碼線(xiàn)性碼：按照一組線(xiàn)性方程構(gòu)成的代數(shù)碼。在線(xiàn)：按照一組線(xiàn)性方程構(gòu)成的代數(shù)碼。在線(xiàn)性碼中信息位和監(jiān)督位是由一些線(xiàn)性代數(shù)方程聯(lián)性碼中信息位和監(jiān)督位是由一些線(xiàn)性代數(shù)方程聯(lián)系著的。系著的。u線(xiàn)性分組碼線(xiàn)性分組碼：按照一組線(xiàn)性方程構(gòu)成的分組碼：按照一組線(xiàn)性方程構(gòu)成的分組碼 。 例如在例如在(7，4)線(xiàn)性分組碼中，信息碼每四位一組線(xiàn)性分組碼中，信息碼每四位一組進(jìn)行編碼，即輸入信息碼元長(zhǎng)度進(jìn)行編碼，

36、即輸入信息碼元長(zhǎng)度k=4；編碼器輸；編碼器輸出碼組長(zhǎng)度出碼組長(zhǎng)度n=7，監(jiān)督碼元長(zhǎng)度，監(jiān)督碼元長(zhǎng)度r = n-k = 7- 4 = 3；編碼效率編碼效率R = k/n = 4/7。 38第10章 差錯(cuò)控制編碼n漢明碼漢明碼能夠能夠糾正糾正1位錯(cuò)碼位錯(cuò)碼且編碼效率較高的一種線(xiàn)性分組碼且編碼效率較高的一種線(xiàn)性分組碼u漢明碼的構(gòu)造原理。漢明碼的構(gòu)造原理。p在偶數(shù)監(jiān)督碼中，由于使用了一位監(jiān)督位在偶數(shù)監(jiān)督碼中，由于使用了一位監(jiān)督位a0，它和信，它和信息位息位an-1 a1一起構(gòu)成一個(gè)代數(shù)式：一起構(gòu)成一個(gè)代數(shù)式：在接收端解碼時(shí)，實(shí)際上就是在計(jì)算在接收端解碼時(shí)，實(shí)際上就是在計(jì)算若若S = 0，就認(rèn)為無(wú)錯(cuò)碼；

37、若，就認(rèn)為無(wú)錯(cuò)碼；若S = 1，就認(rèn)為有錯(cuò)碼?，F(xiàn)，就認(rèn)為有錯(cuò)碼?，F(xiàn)將上式稱(chēng)為將上式稱(chēng)為監(jiān)督關(guān)系式監(jiān)督關(guān)系式，S稱(chēng)為稱(chēng)為校正子校正子。 1200nnaaa120nnSaaa39第10章 差錯(cuò)控制編碼p若監(jiān)督位變成兩位，則能增加一個(gè)類(lèi)似的監(jiān)督關(guān)系式。由若監(jiān)督位變成兩位，則能增加一個(gè)類(lèi)似的監(jiān)督關(guān)系式。由于兩個(gè)校正子的可能值有于兩個(gè)校正子的可能值有4中組合：中組合： 00，01，10，11，故，故能表示能表示4種不同的信息。若用其中種不同的信息。若用其中1種組合表示無(wú)錯(cuò)，則其種組合表示無(wú)錯(cuò)，則其余余3種組合就有可能用來(lái)指示一個(gè)錯(cuò)碼的種組合就有可能用來(lái)指示一個(gè)錯(cuò)碼的3種不同位置。同種不同位置。同理，理，

38、r個(gè)監(jiān)督關(guān)系式能指示個(gè)監(jiān)督關(guān)系式能指示1位錯(cuò)碼的位錯(cuò)碼的(2r 1)個(gè)可能位置。個(gè)可能位置。p一般來(lái)說(shuō)，若一般來(lái)說(shuō)，若碼長(zhǎng)為碼長(zhǎng)為n，信息位數(shù)為信息位數(shù)為k，則，則監(jiān)督位數(shù)監(jiān)督位數(shù)rnk。如果希望用。如果希望用r個(gè)監(jiān)督位構(gòu)造出個(gè)監(jiān)督位構(gòu)造出r個(gè)監(jiān)督關(guān)系式來(lái)指示個(gè)監(jiān)督關(guān)系式來(lái)指示1位位錯(cuò)碼的錯(cuò)碼的n種可能位置，則要求種可能位置，則要求下面通過(guò)一個(gè)例子來(lái)說(shuō)明如何具體構(gòu)造這些監(jiān)督關(guān)系式。下面通過(guò)一個(gè)例子來(lái)說(shuō)明如何具體構(gòu)造這些監(jiān)督關(guān)系式。2121rrnkr 或或40第10章 差錯(cuò)控制編碼p例：設(shè)例：設(shè)分組碼分組碼(n, k)中中k = 4，為了糾正，為了糾正1位錯(cuò)碼，由上式可知，位錯(cuò)碼，由上式可知，要

39、求監(jiān)督位數(shù)要求監(jiān)督位數(shù) r 3。若取。若取 r = 3，則，則n = k + r = 7。我們用。我們用a6 a5 a0表示這表示這7個(gè)碼元，用個(gè)碼元，用S1、S2和和S3表示表示3個(gè)監(jiān)督關(guān)系式中個(gè)監(jiān)督關(guān)系式中的校正子，則的校正子，則S1、S2和和S3的值與錯(cuò)碼位置的對(duì)應(yīng)關(guān)系可以規(guī)的值與錯(cuò)碼位置的對(duì)應(yīng)關(guān)系可以規(guī)定如下表所列：定如下表所列：S1 S2 S3錯(cuò)碼位置錯(cuò)碼位置S1 S2 S3錯(cuò)碼位置錯(cuò)碼位置001a0101a4010a1110a5100a2111a6011a3000無(wú)錯(cuò)碼無(wú)錯(cuò)碼41第10章 差錯(cuò)控制編碼由表中規(guī)定可見(jiàn)，僅當(dāng)一位錯(cuò)碼的位置在由表中規(guī)定可見(jiàn)，僅當(dāng)一位錯(cuò)碼的位置在a2 、a

40、4、a5或或a6時(shí)，時(shí)，校正子校正子S1為為1；否則；否則S1為零。這就意味著為零。這就意味著a2 、a4、a5和和a6四四個(gè)碼元構(gòu)成個(gè)碼元構(gòu)成偶數(shù)監(jiān)督偶數(shù)監(jiān)督關(guān)系：關(guān)系：同理，同理， a1、a3、a5和和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系：構(gòu)成偶數(shù)監(jiān)督關(guān)系：以及以及a0、a3、a4 和和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系構(gòu)成偶數(shù)監(jiān)督關(guān)系16542Saaaa26531Saaaa36430Saaaa 42第10章 差錯(cuò)控制編碼在發(fā)送端編碼時(shí)，信息位在發(fā)送端編碼時(shí)，信息位a6、a5、a4和和a3的值決定于輸入信號(hào)，的值決定于輸入信號(hào)，因此它們是隨機(jī)的。監(jiān)督位因此它們是隨機(jī)的。監(jiān)督位a2、a1和和a0應(yīng)根據(jù)信息位的取值按應(yīng)根據(jù)

41、信息位的取值按監(jiān)督關(guān)系來(lái)確定，即監(jiān)督位應(yīng)使上監(jiān)督關(guān)系來(lái)確定，即監(jiān)督位應(yīng)使上3式中式中S1、S2和和S3的值為的值為0（表示編成的碼組中應(yīng)無(wú)錯(cuò)碼）：（表示編成的碼組中應(yīng)無(wú)錯(cuò)碼）：上式經(jīng)過(guò)移項(xiàng)運(yùn)算，解出監(jiān)督位上式經(jīng)過(guò)移項(xiàng)運(yùn)算，解出監(jiān)督位給定信息位后，可以直接按上式算出監(jiān)督位，給定信息位后，可以直接按上式算出監(jiān)督位， 結(jié)果見(jiàn)下表：結(jié)果見(jiàn)下表：654265316430000aaaaaaaaaaaa 265416530643aaaaaaaaaaaa 監(jiān)督方程監(jiān)督方程43第10章 差錯(cuò)控制編碼信息位信息位a6 a5 a4 a3監(jiān)督位監(jiān)督位a2 a1 a0信息位信息位a6 a5 a4 a3監(jiān)督位監(jiān)督位a2

42、a1 a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111144第10章 差錯(cuò)控制編碼接收端收到每個(gè)碼組后，先計(jì)算出接收端收到每個(gè)碼組后，先計(jì)算出S1、S2和和S3，再查表，再查表判斷錯(cuò)碼情況。判斷錯(cuò)碼情況。例如，若接收碼組為例如，若接收碼組為0000011，按上述公式計(jì)算可得：，按上述公式計(jì)算可得： S1 = 0，S2 = 1，S3 = 1。S1 S2 S3 等于等于011，故查表可知，故查表可知在在 a3位有位有1錯(cuò)碼

43、。錯(cuò)碼。 按照上述方法構(gòu)造的碼稱(chēng)為按照上述方法構(gòu)造的碼稱(chēng)為漢明碼漢明碼。表中所列的表中所列的(7, 4)漢明碼的最小碼距漢明碼的最小碼距d0 = 3。因此，這種碼能。因此，這種碼能夠夠糾正糾正1個(gè)個(gè)錯(cuò)碼或錯(cuò)碼或檢測(cè)檢測(cè)2個(gè)錯(cuò)碼。個(gè)錯(cuò)碼。由于碼率由于碼率k/n = (n - r) /n =1 r/n，故當(dāng)，故當(dāng)n很大和很大和r很小時(shí)，碼很小時(shí)，碼率接近率接近1。可見(jiàn)，?？梢?jiàn)，漢明碼是一種高效碼。漢明碼是一種高效碼。 45第10章 差錯(cuò)控制編碼n線(xiàn)性分組碼的一般原理線(xiàn)性分組碼的一般原理u線(xiàn)性分組碼的構(gòu)造線(xiàn)性分組碼的構(gòu)造pH矩陣矩陣上面上面(7, 4)漢明碼的例子有漢明碼的例子有現(xiàn)在將上面它改寫(xiě)為現(xiàn)

44、在將上面它改寫(xiě)為上式中已經(jīng)將上式中已經(jīng)將“ ”簡(jiǎn)寫(xiě)成簡(jiǎn)寫(xiě)成“+”。 654265316430000aaaaaaaaaaaa 654321065432106543210111010001101010010110010aaaaaaaaaaaaaaaaaaaaa 46第10章 差錯(cuò)控制編碼上式可以表示成如下矩陣形式：上式可以表示成如下矩陣形式：上式還可以簡(jiǎn)記為上式還可以簡(jiǎn)記為H AT = 0T 或或 A HT = 0654321065432106543210111010001101010010110010aaaaaaaaaaaaaaaaaaaaa 65432101110100011010100210

45、110010aaaaaaa （模模 ）47第10章 差錯(cuò)控制編碼H AT = 0T 或或A HT = 0式中式中 A = a6 a5 a4 a3 a2 a1 a00 = 000右上標(biāo)右上標(biāo)“T”表示將矩陣轉(zhuǎn)置。例如，表示將矩陣轉(zhuǎn)置。例如，HT是是H的轉(zhuǎn)置，即的轉(zhuǎn)置，即HT的第一行為的第一行為H的第一列，的第一列，HT的第二行為的第二行為H的第二列等等。的第二列等等。將將H稱(chēng)為稱(chēng)為監(jiān)督矩陣監(jiān)督矩陣。 只要監(jiān)督矩陣只要監(jiān)督矩陣H給定，編碼時(shí)監(jiān)督位和信息位的關(guān)系就完給定，編碼時(shí)監(jiān)督位和信息位的關(guān)系就完全確定了全確定了。 101100111010101110100H48第10章 差錯(cuò)控制編碼H矩陣的性

46、質(zhì)矩陣的性質(zhì)： 1) H的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，它等于監(jiān)督位的的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，它等于監(jiān)督位的數(shù)目數(shù)目r。H的每行中的每行中“1”的位置表示相應(yīng)碼元之間存在的位置表示相應(yīng)碼元之間存在的監(jiān)督關(guān)系。例如，的監(jiān)督關(guān)系。例如，H的第一行的第一行1110100表示監(jiān)督位表示監(jiān)督位a2是由是由a6 a5 a4之和決定的。之和決定的。H矩陣可以分成兩部分，例如矩陣可以分成兩部分，例如 式中，式中，P為為r k階矩陣，階矩陣，Ir為為r r階單位方陣。我們將階單位方陣。我們將具有具有P Ir形式的形式的H矩陣稱(chēng)為矩陣稱(chēng)為典型陣典型陣。 2) 由代數(shù)理論可知，由代數(shù)理論可知，H矩陣的各行應(yīng)該是線(xiàn)性

47、無(wú)關(guān)的。矩陣的各行應(yīng)該是線(xiàn)性無(wú)關(guān)的。rPIH00110110101101100111049第10章 差錯(cuò)控制編碼pG矩陣矩陣： 上面漢明碼例子中的監(jiān)督位公式上面漢明碼例子中的監(jiān)督位公式 也可以改寫(xiě)成矩陣形式：也可以改寫(xiě)成矩陣形式：265416530643aaaaaaaaaaaa 6251403111011011011aaaaaaa 50第10章 差錯(cuò)控制編碼或者寫(xiě)成或者寫(xiě)成式中，式中，Q為一個(gè)為一個(gè)k r階矩陣，它為階矩陣，它為P的轉(zhuǎn)置的轉(zhuǎn)置，即，即 Q = PT 上式表示，在信息位給定后，用信息位的行矩陣乘矩上式表示，在信息位給定后，用信息位的行矩陣乘矩 陣陣Q就產(chǎn)生出監(jiān)督位。就產(chǎn)生出監(jiān)督位

48、。6251403111011011011aaaaaaa 21065436543111110101011a a aa a a aa a a aQ 51第10章 差錯(cuò)控制編碼我們將我們將Q的左邊加上的左邊加上1個(gè)個(gè)k k階單位方陣，就構(gòu)成階單位方陣，就構(gòu)成1個(gè)矩陣個(gè)矩陣G G稱(chēng)為稱(chēng)為生成矩陣生成矩陣，因?yàn)橛伤梢援a(chǎn)生整個(gè)碼組，即有，因?yàn)橛伤梢援a(chǎn)生整個(gè)碼組，即有 或者或者因此，因此，如果找到了碼的生成矩陣如果找到了碼的生成矩陣G，則編碼的方法就完全確定了。，則編碼的方法就完全確定了。具有具有Ik Q形式的生成矩陣稱(chēng)為形式的生成矩陣稱(chēng)為典型生成矩陣典型生成矩陣。由典型生成矩陣得。由典型生成矩陣得出的

49、碼組出的碼組A中，信息位的位置不變，監(jiān)督位附加于其后。這種形式中，信息位的位置不變，監(jiān)督位附加于其后。這種形式的碼稱(chēng)為的碼稱(chēng)為系統(tǒng)碼系統(tǒng)碼。 1000 1110100 1100010 1010001 011kGQ I I65432106543a a a a a a aa a a aG6543Aa a a aG52第10章 差錯(cuò)控制編碼G矩陣的性質(zhì)矩陣的性質(zhì)：1) G矩陣的各行是線(xiàn)性無(wú)關(guān)的。矩陣的各行是線(xiàn)性無(wú)關(guān)的。 任一碼組任一碼組A都是都是G的各行的線(xiàn)性組合。的各行的線(xiàn)性組合。G共有共有k行，若它行，若它們線(xiàn)性無(wú)關(guān)，則可以組合出們線(xiàn)性無(wú)關(guān)，則可以組合出2k種不同的碼組種不同的碼組A，它恰是，它

50、恰是有有k位信息位的全部碼組。若位信息位的全部碼組。若G的各行有線(xiàn)性相關(guān)的，的各行有線(xiàn)性相關(guān)的，則不可能由則不可能由G生成生成2k種不同的碼組了。種不同的碼組了。2)G的各行本身就是一個(gè)碼組。的各行本身就是一個(gè)碼組。 如果已有如果已有k個(gè)線(xiàn)性無(wú)關(guān)的碼組，則可以用其作為生成矩個(gè)線(xiàn)性無(wú)關(guān)的碼組，則可以用其作為生成矩陣陣G，并由它生成其余碼組。，并由它生成其余碼組。53第10章 差錯(cuò)控制編碼p錯(cuò)碼矩陣和錯(cuò)誤圖樣錯(cuò)碼矩陣和錯(cuò)誤圖樣 發(fā)送的碼組發(fā)送的碼組A在傳輸中可能由于干擾引入差錯(cuò)，故接收在傳輸中可能由于干擾引入差錯(cuò)，故接收碼組一般說(shuō)來(lái)與碼組一般說(shuō)來(lái)與A不一定相同。不一定相同。若設(shè)接收碼組為一若設(shè)接收

51、碼組為一n列的行矩陣列的行矩陣B，即，即則發(fā)送碼組和接收碼組之差為則發(fā)送碼組和接收碼組之差為B A = E (模模2)它就是傳輸中產(chǎn)生的它就是傳輸中產(chǎn)生的錯(cuò)碼錯(cuò)碼行行矩陣矩陣 式中式中 0121bbbbBnn 0121eeeeEnn iiiiiababe當(dāng)當(dāng), 1, 054第10章 差錯(cuò)控制編碼因此，若因此，若ei = 0，表示該接收碼元無(wú)錯(cuò)；，表示該接收碼元無(wú)錯(cuò)； 若若ei = 1，則表示該接收碼元有錯(cuò)。，則表示該接收碼元有錯(cuò)。 B A = E 可以改寫(xiě)成可以改寫(xiě)成 B = A + E例如，若發(fā)送碼組例如，若發(fā)送碼組A = 1000111，錯(cuò)碼矩陣，錯(cuò)碼矩陣E = 0000100，則接收碼組

52、則接收碼組B = 1000011。錯(cuò)碼矩陣有時(shí)也稱(chēng)為錯(cuò)碼矩陣有時(shí)也稱(chēng)為錯(cuò)誤圖樣錯(cuò)誤圖樣。55第10章 差錯(cuò)控制編碼p校正子校正子S當(dāng)接收碼組有錯(cuò)時(shí)，當(dāng)接收碼組有錯(cuò)時(shí)，E 0，將，將B當(dāng)作當(dāng)作A代入公式代入公式(A H T = 0)后，該式不一定成立。在未超過(guò)檢錯(cuò)能力時(shí)，上式不成后，該式不一定成立。在未超過(guò)檢錯(cuò)能力時(shí)，上式不成立，即其右端不等于立，即其右端不等于0。假設(shè)這時(shí)該式的右端為。假設(shè)這時(shí)該式的右端為S，即，即B H T = S將將B = A + E代入上式，可得代入上式，可得S = (A + E) H T = A H T + E H T由于由于A(yíng) HT = 0，所以，所以S = E H

53、T式中式中S稱(chēng)為校正子。它能用來(lái)指示錯(cuò)碼的位置。稱(chēng)為校正子。它能用來(lái)指示錯(cuò)碼的位置。S和錯(cuò)碼和錯(cuò)碼E之間有確定的線(xiàn)性變換關(guān)系。若之間有確定的線(xiàn)性變換關(guān)系。若S和和E之間一一之間一一對(duì)應(yīng)，則對(duì)應(yīng)，則S將能代表錯(cuò)碼的位置。將能代表錯(cuò)碼的位置。56第10章 差錯(cuò)控制編碼u線(xiàn)性分組碼的性質(zhì)線(xiàn)性分組碼的性質(zhì)p封閉性封閉性：線(xiàn)性碼中的任意兩個(gè)碼組之和仍為這種碼中的一：線(xiàn)性碼中的任意兩個(gè)碼組之和仍為這種碼中的一個(gè)碼組。個(gè)碼組。 若若A1和和A2是兩個(gè)碼組，則有是兩個(gè)碼組，則有A1 HT = 0,A2 HT = 0 將上兩式相加，得出將上兩式相加，得出 A1 HT + A2 HT = (A1 + A2) HT

54、 = 0所以所以(A1 + A2)也是一個(gè)碼組。也是一個(gè)碼組。p兩個(gè)碼組兩個(gè)碼組(A1和和A2)之間的距離必定是另一個(gè)碼組之間的距離必定是另一個(gè)碼組(A1 + A2)的重量（即的重量（即“1”的數(shù)目）。的數(shù)目）。 因此，因此，最小碼距就是最小碼重最小碼距就是最小碼重。57第10章 差錯(cuò)控制編碼l10.6 循環(huán)碼循環(huán)碼n10.6.1 循環(huán)碼原理循環(huán)碼原理 循環(huán)碼循環(huán)碼是是具有具有循環(huán)性循環(huán)性的的線(xiàn)性分組碼線(xiàn)性分組碼。 循環(huán)碼中任意一碼組向右或向左循環(huán)移一位以后，循環(huán)碼中任意一碼組向右或向左循環(huán)移一位以后， 仍是該碼的一個(gè)碼組。仍是該碼的一個(gè)碼組。 循環(huán)碼的編譯碼設(shè)備較簡(jiǎn)單，檢糾錯(cuò)能力較強(qiáng)，循環(huán)碼

55、的編譯碼設(shè)備較簡(jiǎn)單，檢糾錯(cuò)能力較強(qiáng)， 廣泛應(yīng)用。廣泛應(yīng)用。58第10章 差錯(cuò)控制編碼(7, 3) 循環(huán)碼循環(huán)碼 碼組編號(hào)碼組編號(hào)碼碼 組組碼組編號(hào)碼組編號(hào)碼碼 組組1000 0000 5100 10112001 01116101 11003010 11107110 01014011 10018111 001059第10章 差錯(cuò)控制編碼u碼多項(xiàng)式碼多項(xiàng)式p碼組的多項(xiàng)式表示法碼組的多項(xiàng)式表示法把碼組中各碼元當(dāng)作是一個(gè)多項(xiàng)式的系數(shù)，即把一個(gè)長(zhǎng)把碼組中各碼元當(dāng)作是一個(gè)多項(xiàng)式的系數(shù)，即把一個(gè)長(zhǎng)度為度為n的碼組的碼組 表示成表示成例如：碼組例如：碼組1100101（n=7）的碼多項(xiàng)式為）的碼多項(xiàng)式為這種多

56、項(xiàng)式中，這種多項(xiàng)式中，x僅是碼元位置的標(biāo)記，例如上式表示僅是碼元位置的標(biāo)記，例如上式表示碼組中碼組中a6、a5、a2和和a0為為“1”，其他均為，其他均為0。因此我們并。因此我們并不關(guān)心不關(guān)心x的取值。的取值。 121210( )nnnnT xaxaxa xa 65432652( )11001011T xxxxxxxxxx 1210(,)nnaaa a 60第10章 差錯(cuò)控制編碼p 碼多項(xiàng)式的按模運(yùn)算碼多項(xiàng)式的按模運(yùn)算在整數(shù)運(yùn)算中，有模在整數(shù)運(yùn)算中，有模n運(yùn)算。例如，在模運(yùn)算。例如，在模2運(yùn)算中，有運(yùn)算中，有1 + 1 = 2 0 (模模2)1 + 2 = 3 1 (模模2) 2 3 = 6

57、0 (模模2)一般說(shuō)來(lái)，若一個(gè)整數(shù)一般說(shuō)來(lái)，若一個(gè)整數(shù)m可以表示為可以表示為式中，式中，Q 整數(shù)，則在模整數(shù)，則在模 n 運(yùn)算下，有運(yùn)算下，有 m p (模模n)即，即，在模在模 n 運(yùn)算下，一個(gè)整數(shù)運(yùn)算下，一個(gè)整數(shù)m等于它被等于它被 n 除得的余數(shù)。除得的余數(shù)。 ,mpQpnnn 61第10章 差錯(cuò)控制編碼碼多項(xiàng)式運(yùn)算中也有類(lèi)似的按模運(yùn)算。碼多項(xiàng)式運(yùn)算中也有類(lèi)似的按模運(yùn)算。 若一任意多項(xiàng)式若一任意多項(xiàng)式F(x)被一被一 n 次多項(xiàng)式次多項(xiàng)式N(x)除，除，得到商式得到商式Q(x)和一個(gè)次數(shù)小于和一個(gè)次數(shù)小于n的余式的余式R(x)，即，即則寫(xiě)為則寫(xiě)為碼多項(xiàng)式系數(shù)仍按模碼多項(xiàng)式系數(shù)仍按模2運(yùn)算，

58、即系數(shù)只取運(yùn)算，即系數(shù)只取 0 和和1。( )( ) ( )( )F xN x Q xR x ( )( )( )F xR xN x （模模）62第10章 差錯(cuò)控制編碼例如例如：F(x)=x4+x2+1被被N(x)=x3+1除除，得到余式得到余式R(x)=x2+x+1，xxxxx 424311x12 xx即：即：x4+x2+1 x2+x+1（模模(x3+1)。63第10章 差錯(cuò)控制編碼u循環(huán)碼的碼多項(xiàng)式循環(huán)碼的碼多項(xiàng)式p在循環(huán)碼中，若在循環(huán)碼中，若T(x)是一個(gè)長(zhǎng)為是一個(gè)長(zhǎng)為n的許用碼組的許用碼組，若，若則則T (x)也是該編碼中的一個(gè)許用碼組也是該編碼中的一個(gè)許用碼組。 【證證】 （模（模(x

59、n + 1)）所以，這時(shí)有所以，這時(shí)有( )( )(1)inxT xTxx （模模）121210( )nnnnT xaxaxa xa 121112110( )inininiinnnixT xaxaxaxa xa x 1211201( )nniinininn iT xaxaxa xaxa 1211201nniinininn iaxaxa xaxa T (x)正是正是T(x)代表的碼組向左循環(huán)移位代表的碼組向左循環(huán)移位i次的結(jié)果。次的結(jié)果。因?yàn)榧俣ㄒ驗(yàn)榧俣═(x)是循環(huán)碼的一個(gè)碼組，所以是循環(huán)碼的一個(gè)碼組，所以T (x)也必為該碼的一個(gè)碼組。也必為該碼的一個(gè)碼組。64第10章 差錯(cuò)控制編碼例如，循

60、環(huán)碼組例如，循環(huán)碼組(1100101)其碼長(zhǎng)其碼長(zhǎng)n = 7?，F(xiàn)給定?，F(xiàn)給定i = 3，則，則 其對(duì)應(yīng)的碼組為其對(duì)應(yīng)的碼組為0101110，它正是原碼組左移，它正是原碼組左移3位的結(jié)果。位的結(jié)果。652( )1T xxxx3365298535327( )(1)(1)xT xxxxxxxxxxxxxx （模模）65第10章 差錯(cuò)控制編碼u循環(huán)碼的生成多項(xiàng)式和生成矩陣循環(huán)碼的生成多項(xiàng)式和生成矩陣p由公式由公式可知，有了生成矩陣可知，有了生成矩陣G，就可以由，就可以由k個(gè)信息位得出整個(gè)碼組，個(gè)信息位得出整個(gè)碼組，而且生成矩陣而且生成矩陣G的每一行都是一個(gè)碼組。的每一行都是一個(gè)碼組。 若能找到若能找到