第五章 差錯(cuò)控制與信道編碼

第五章差錯(cuò)控制與信道編碼第一頁，共九十二頁，編輯于2023年，星期五內(nèi)容簡介——差錯(cuò)控制就是通過某種方法，發(fā)現(xiàn)并糾正數(shù)據(jù)傳輸中出現(xiàn)的錯(cuò)誤。差錯(cuò)控制技術(shù)是提高數(shù)據(jù)傳輸可靠性的重要手段之一，現(xiàn)代數(shù)據(jù)通信中使用的差錯(cuò)控制方式大都是基于信道編碼技術(shù)來實(shí)現(xiàn)的，本章對(duì)差錯(cuò)控制的基本概念以及常用的信道編碼方案作了比較詳細(xì)的論述。返回結(jié)束第二頁，共九十二頁，編輯于2023年，星期五學(xué)習(xí)要求1.理解差錯(cuò)控制的基本概念及其原理等；2.掌握信道編碼的基本原理；3.了解常用檢錯(cuò)碼的特性；4.掌握線性分組碼的一般特性；5.掌握漢明碼以及循環(huán)碼的編譯碼及其實(shí)現(xiàn)原理；6.了解卷積碼的基本概念。返回結(jié)束第三頁，共九十二頁，編輯于2023年，星期五學(xué)習(xí)目錄返回5.1概述5.2常用的簡單信道編碼5.3線性分組碼5.4卷積碼結(jié)束第四頁，共九十二頁，編輯于2023年，星期五5.1概述——差錯(cuò)控制是數(shù)據(jù)通信系統(tǒng)中提高傳輸可靠性，降低系統(tǒng)傳輸誤碼率的有效措施。本節(jié)將介紹差錯(cuò)控制和信道編碼的基本原理、差錯(cuò)控制的實(shí)現(xiàn)方式等內(nèi)容。

5.1.1差錯(cuò)控制

5.1.2信道編碼

5.1.3基于信道編碼的差錯(cuò)控制方式本節(jié)內(nèi)容提要：第五頁，共九十二頁，編輯于2023年，星期五5.1.1差錯(cuò)控制差錯(cuò)控制——通過某種方法，發(fā)現(xiàn)并糾正傳輸中出現(xiàn)的錯(cuò)誤。香農(nóng)信道編碼定理——在具有確定信道容量的有擾信道中，若以低于信道容量的速率傳輸數(shù)據(jù)，則存在某種編碼方案，可以使傳輸?shù)恼`碼率足夠小。基于信道編碼的差錯(cuò)控制——在發(fā)送端根據(jù)一定的規(guī)則，在數(shù)據(jù)序列中按照一定的規(guī)則附加一些監(jiān)督信息，接收端根據(jù)監(jiān)督信息進(jìn)行檢錯(cuò)或者糾錯(cuò)。第六頁，共九十二頁，編輯于2023年，星期五5.1.1差錯(cuò)控制隨機(jī)錯(cuò)誤

——主要由起伏噪聲引起，錯(cuò)誤碼元分布比較分散且彼此統(tǒng)計(jì)獨(dú)立；突發(fā)錯(cuò)誤——主要由脈沖噪聲引起，錯(cuò)誤碼元分布集中且彼此具有某種相關(guān)性。錯(cuò)誤圖樣差錯(cuò)分析E中，“0”表示正確，“1”表示錯(cuò)誤第七頁，共九十二頁，編輯于2023年，星期五隨機(jī)錯(cuò)誤錯(cuò)誤圖樣5.1.1差錯(cuò)控制突發(fā)錯(cuò)誤錯(cuò)誤圖樣第八頁，共九十二頁，編輯于2023年，星期五5.1.2信道編碼——在不采用信道編碼的時(shí)候，進(jìn)入信道的數(shù)據(jù)碼元相互獨(dú)立，一旦發(fā)生錯(cuò)誤，將無法發(fā)現(xiàn)。例如氣象臺(tái)向電視臺(tái)傳輸氣象信息。不可靠數(shù)據(jù)傳輸系統(tǒng)第九頁，共九十二頁，編輯于2023年，星期五5.1.2信道編碼——將信息序列按照k位碼元的長度分成若干個(gè)信息碼組M，再將信息碼組輸入到信道編碼器，信道編碼器按照一定的算法，產(chǎn)生一個(gè)新的n位碼字A輸出，n>k；——收端根據(jù)A中的相關(guān)性判斷接收是否正確，并將其恢復(fù)成M?！幋a效率為k/n，即所謂編碼效率是指信道編碼后碼字中信息碼元的數(shù)目與碼字總碼元數(shù)目之比。信道編碼的基本思想第十頁，共九十二頁，編輯于2023年，星期五5.1.2信道編碼信道編碼的冗余——信息碼組M由k個(gè)二進(jìn)制碼元（即比特）組成，所以就有2k個(gè)M；——A長度為n，n位長度的碼字共有2n個(gè)，信道編碼實(shí)質(zhì)是通過一定的規(guī)則，從2n個(gè)長度為n的碼字中選擇了其中的2k個(gè)，每個(gè)被選中的碼字稱為許用碼字；——未被選中的2n-2k個(gè)n長的碼字稱為禁用碼字，反映冗余大小。第十一頁，共九十二頁，編輯于2023年，星期五5.1.2信道編碼對(duì)本節(jié)開始時(shí)的例子采用(2，1)重復(fù)碼:11”----晴,“00”---雨許用碼組為:“11”和“00”,禁用碼組為：“01”和“10”

此時(shí)接收端可以發(fā)現(xiàn)單個(gè)錯(cuò)誤，但不能糾正錯(cuò)誤也不能發(fā)現(xiàn)2位錯(cuò)誤，如下圖所示：實(shí)例分析I第十二頁，共九十二頁，編輯于2023年，星期五5.1.2信道編碼對(duì)本節(jié)開始時(shí)的例子采用(3，1)重復(fù)碼:111”----晴,“000”---雨許用碼組為:111和000

禁用碼組為：001、010、011、100、101、110

將這種編碼用來檢錯(cuò)時(shí)，可以發(fā)現(xiàn)兩位以內(nèi)的錯(cuò)誤將這種編碼用來糾錯(cuò)，可以糾正一位錯(cuò)誤，如下圖所示：實(shí)例分析II第十三頁，共九十二頁，編輯于2023年，星期五5.1.2信道編碼如此譯碼的原因是信道中錯(cuò)一位的概率遠(yuǎn)遠(yuǎn)大于錯(cuò)多位的概率例如要把該（3，1）重復(fù)碼在有一條誤碼率為10-5的信道傳輸，則：

——錯(cuò)一位的概率為：P1=C31Pe(1－Pe)2=3×10-5——錯(cuò)二位的概率為：P2=C32Pe2(1－Pe)

=3×10-10——錯(cuò)三位的概率為：P3=Pe3=10-15這種譯碼方法稱為極大似然譯碼法,其基本原理為:構(gòu)造一個(gè)極大似然函數(shù)L,從2k個(gè)許用碼組中找到一個(gè)碼字Ci，當(dāng)Ｌ=Ci時(shí),函數(shù)L可以取得最大值,則認(rèn)為C=Ci。第十四頁，共九十二頁，編輯于2023年，星期五5.1.2信道編碼線性碼和非線性碼——若f(·)是線性函數(shù)稱為線性碼——若f(·)是非線性函數(shù)則稱為非線性編碼信道編碼的分類信道編碼器函數(shù)關(guān)系式為：分組碼和卷積碼——分組碼：每個(gè)信息碼組M通過運(yùn)算產(chǎn)生對(duì)應(yīng)的A

，記作(n，k)——卷積碼：每個(gè)A是由m(m<2k)個(gè)M聯(lián)合運(yùn)算得到，記作(n，k，m)第十五頁，共九十二頁，編輯于2023年，星期五5.1.2信道編碼系統(tǒng)碼和非系統(tǒng)碼檢錯(cuò)碼、糾錯(cuò)碼和糾檢錯(cuò)碼——若A中的前k位或者后k位就是信息碼組M，則稱這種編碼為系統(tǒng)碼，否則稱為非系統(tǒng)碼。第十六頁，共九十二頁，編輯于2023年，星期五5.1.2信道編碼幾個(gè)概念碼長

——碼字的碼元數(shù)目，例如(n，k)分組碼的碼長為n

碼重

——指碼字中“1”的數(shù)目，記作W(A)。例如W(110110)=4碼距（漢明距）

——兩個(gè)等長碼對(duì)應(yīng)位不同的數(shù)目，記作d(A，B)，例如A=110110，B=101011，則d(A，B)=4碼距與碼重的關(guān)系

——d(A，B)=W(A+B)第十七頁，共九十二頁，編輯于2023年，星期五5.1.2信道編碼最小碼距（最小漢明距）——一個(gè)(n，k)分組碼的糾檢錯(cuò)能力由其最小碼距決定：————當(dāng)最小碼距d0≥e+1時(shí)，能夠發(fā)現(xiàn)e個(gè)錯(cuò)誤碼元————當(dāng)最小碼距d0≥2t+1時(shí)，能夠糾正t個(gè)錯(cuò)誤碼元————當(dāng)最小碼距d0≥t+e+1時(shí)，能夠糾正t個(gè)錯(cuò)誤碼元，同時(shí)發(fā)現(xiàn)e個(gè)錯(cuò)誤碼元(e>t)——(n，k)分組碼總共有2k個(gè)碼字，記作Ai（i=0,1,…,2k-1）,則這些碼字兩兩之間都有一個(gè)碼距，定義該(n，k)分組碼的最小碼距為：第十八頁，共九十二頁，編輯于2023年，星期五5.1.3基于信道編碼的差錯(cuò)控制方式前向糾錯(cuò)（FEC:ForwardErrorCorrection）方式原理——采用糾錯(cuò)碼,收端發(fā)現(xiàn)錯(cuò)誤后自動(dòng)糾正。特點(diǎn)——無需重發(fā)，解碼延遲固定，實(shí)時(shí)性好——無需反饋信道，能用于單向傳輸信道，特別適用于單點(diǎn)向多點(diǎn)同時(shí)傳送的方式——編碼效率較低，需較大的冗余度（通常約25-50%）,譯碼設(shè)備比較復(fù)雜——糾錯(cuò)碼須與信道特性相匹配，對(duì)信道變化的適應(yīng)性較差——若錯(cuò)誤超出糾錯(cuò)碼糾錯(cuò)能力,只好將其拋棄應(yīng)用——移動(dòng)通信系統(tǒng)

第十九頁，共九十二頁，編輯于2023年，星期五5.1.3基于信道編碼的差錯(cuò)控制方式反饋重傳（ARQ:AutomaticRepeatRequest）方式原理——采用檢錯(cuò)碼，接收端發(fā)現(xiàn)錯(cuò)誤后，給發(fā)送端一個(gè)反饋信號(hào)，要求重新發(fā)送，直到正確為止。特點(diǎn)——編碼效率比較高，只需少量的冗余碼（約5-20%）就能獲得極低的傳輸誤碼率；對(duì)信道的適應(yīng)能力強(qiáng)——必須有反饋信道，故不能用于單向傳輸系統(tǒng)和同播系統(tǒng)——控制規(guī)程和過程比較復(fù)雜——重發(fā)導(dǎo)致信道的有效利用率較低，通信的實(shí)時(shí)性較差——由于反饋重傳的隨機(jī)性，故不適于實(shí)時(shí)傳輸系統(tǒng)第二十頁，共九十二頁，編輯于2023年，星期五5.1.3基于信道編碼的差錯(cuò)控制方式反饋重傳（ARQ:AutomaticRepeatRequest）方式工作方式——發(fā)送等待——連續(xù)工作方式——混合方式應(yīng)用——數(shù)據(jù)通信系統(tǒng)第二十一頁，共九十二頁，編輯于2023年，星期五5.1.3基于信道編碼的差錯(cuò)控制方式混合糾錯(cuò)（HEC:HybridErrorCorrection）方式原理——采用糾檢錯(cuò)碼，是ARQ和FEC方式的折衷方案特點(diǎn)——集合了ARQ和FEC的優(yōu)點(diǎn)，在保證系統(tǒng)較高的有效性的同時(shí),大幅度提高了整個(gè)系統(tǒng)的可靠性應(yīng)用——移動(dòng)通信系統(tǒng)，數(shù)據(jù)傳輸系統(tǒng)（特別是在使用衛(wèi)星信道等高時(shí)延、大容量的信道傳輸數(shù)據(jù)信號(hào)時(shí)更具優(yōu)勢）第二十二頁，共九十二頁，編輯于2023年，星期五5.1.3基于信道編碼的差錯(cuò)控制方式信息反饋（IRQ:InformationRepeatRequest）方式原理——也稱回程校驗(yàn)方式，在發(fā)端來檢測錯(cuò)誤。特點(diǎn)——無需采用糾檢錯(cuò)編碼，故設(shè)備和控制由于規(guī)程較簡單；需一條與前向信道相同的反饋信道；由于采用發(fā)端檢錯(cuò)，相當(dāng)于信息傳輸距離增加一倍，可能導(dǎo)致額外的差錯(cuò)和重傳；可能使整個(gè)通信系統(tǒng)的傳信率很低；收發(fā)兩端需較大容量的存儲(chǔ)器來存儲(chǔ)傳輸信息。第二十三頁，共九十二頁，編輯于2023年，星期五5.2常用的簡單信道編碼本節(jié)內(nèi)容提要：——檢錯(cuò)碼在ARQ系統(tǒng)中使用，其生成方式簡單，易于實(shí)現(xiàn)，檢錯(cuò)效果較好，因此得到廣泛的應(yīng)用，本節(jié)將介紹奇偶校驗(yàn)碼、行列監(jiān)督碼、恒比碼、正反碼的編譯碼規(guī)則、特性以及應(yīng)用情況。

5.2.1奇偶監(jiān)督碼

5.2.2行列監(jiān)督碼

5.2.3恒比碼

5.2.4重復(fù)碼

5.2.5正反碼第二十四頁，共九十二頁，編輯于2023年，星期五5.2.1奇偶監(jiān)督碼

奇偶監(jiān)督碼——碼重為奇數(shù)或偶數(shù)的(n,n-1)系統(tǒng)分組碼

ITU-T建議——同步數(shù)據(jù)傳輸使用偶監(jiān)督——異步數(shù)據(jù)傳輸使用奇監(jiān)督能檢查出傳輸碼組中的所有奇數(shù)個(gè)錯(cuò)誤

監(jiān)督關(guān)系——假設(shè)將（n，n-1）的奇偶監(jiān)督碼的碼字記作：an-1,an-2,…,a1,a0，其中a0為監(jiān)督碼元，其余為信息碼元，則各碼元滿足：第二十五頁，共九十二頁，編輯于2023年，星期五5.2.2行列監(jiān)督碼行列監(jiān)督碼（水平垂直一致校驗(yàn)碼或方陣碼）——對(duì)水平方向(共L行)和垂直方向(共M列),同時(shí)進(jìn)行奇偶監(jiān)督的碼，記作（LM+L+M+1,LM）。——(66，50)行列監(jiān)督碼的一個(gè)碼字

——該碼具有很強(qiáng)的糾檢錯(cuò)能力，常用于短波散射信道等信道干擾比較嚴(yán)重的通信中。第二十六頁，共九十二頁，編輯于2023年，星期五5.2.2行列監(jiān)督碼行列監(jiān)督碼（水平垂直一致校驗(yàn)碼或g方陣碼）——根據(jù)按列或按行的次序傳輸，分別能發(fā)現(xiàn)小于等于M+1或L+1長度的突發(fā)性錯(cuò)誤；——可以檢出某些偶數(shù)個(gè)隨機(jī)誤差；——當(dāng)傳輸差錯(cuò)數(shù)正好為4的倍數(shù)，而且構(gòu)成矩形的四個(gè)角，則不能發(fā)現(xiàn)這類差錯(cuò)。第二十七頁，共九十二頁，編輯于2023年，星期五5.2.3恒比碼

恒比碼（等比碼，定比碼，等重碼）——從所有一定長度的二進(jìn)制序列中選取“1”數(shù)目相同的序列作為碼字；——該碼的特點(diǎn)是碼字中1，0數(shù)目恒定，亦即1，0數(shù)目之比恒定?！壳拔覈妭魍ㄐ胖衅毡椴捎?：2碼，又稱5中取3碼，如下所示

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

——可以檢測所有奇數(shù)個(gè)錯(cuò)誤和部分偶數(shù)個(gè)錯(cuò)誤。

——主要優(yōu)點(diǎn)是簡單易實(shí)現(xiàn)。

第二十八頁，共九十二頁，編輯于2023年，星期五5.2.4重復(fù)碼——(3，1)重復(fù)碼兩個(gè)碼字為000和111，其最小碼距為3；——(n，1)重復(fù)碼也只有全0碼和全1碼兩個(gè)碼字，其最小碼距為n，卻有2n-2個(gè)禁用碼組，隨著碼長的增大，其冗余也變得很大；——該碼隨碼長增加，具有很強(qiáng)的糾檢錯(cuò)能力，但其編碼效率的急劇下降；——重復(fù)碼并不是一種優(yōu)秀的編碼方案，僅用于速率很低的數(shù)據(jù)通信系統(tǒng)中。

重復(fù)碼——重復(fù)碼只有一位信息碼元，監(jiān)督碼元是信息碼元的重復(fù)，所以僅有兩個(gè)碼字；第二十九頁，共九十二頁，編輯于2023年，星期五5.2.5正反碼正反碼——該碼型多用于10單位碼的前向糾錯(cuò)設(shè)備中，可以糾正一位錯(cuò)誤，發(fā)現(xiàn)全部兩個(gè)以下的錯(cuò)誤，以及大部分兩個(gè)以上的錯(cuò)誤，其本質(zhì)就是五單位碼的重復(fù)；

編碼規(guī)則——信息碼組中1的數(shù)目為奇數(shù)時(shí)，監(jiān)督碼是信息碼的重復(fù)即正碼；信息碼組中1的數(shù)目為偶數(shù)時(shí)，監(jiān)督碼是信息碼的反碼。

譯碼方法——首先將收到的碼字中的信息位和監(jiān)督位按對(duì)應(yīng)位作模2運(yùn)算，得到一個(gè)5位碼組，若該碼字中有奇數(shù)個(gè)1，則將其作為校驗(yàn)碼組，若有偶數(shù)個(gè)1，則取其反碼作為校驗(yàn)碼組。然后，按照下表進(jìn)行糾檢錯(cuò)譯碼第三十頁，共九十二頁，編輯于2023年，星期五5.2.5正反碼正反碼錯(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第三十一頁，共九十二頁，編輯于2023年，星期五5.3線性分組碼本節(jié)內(nèi)容提要：——本節(jié)將對(duì)線性分組碼的特點(diǎn)、編譯碼規(guī)則以及應(yīng)用情況作介紹，主要包括以下四方面內(nèi)容。

5.3.1基本概念

5.3.2線性分組碼編碼

5.3.3漢明碼

5.3.4循環(huán)碼第三十二頁，共九十二頁，編輯于2023年，星期五5.3.1基本概念1．有限域——定義了加法“+”和乘法“·”兩種運(yùn)算的有限集合；——q個(gè)元素的有限域又稱為伽羅瓦域，記作GF(q)；——對(duì)域的逆元操作又演繹出了減法“－”和除法運(yùn)算“÷”，域具有封閉特性域中總包含惟一的加法恒等元“0”和乘法恒等元“1”第三十三頁，共九十二頁，編輯于2023年，星期五5.3.1基本概念域中任意元素存在惟一的加法逆元域中任意非零元都存在惟一的乘法逆元于是減法和除法運(yùn)算可定義為：域中元素滿足交換律、結(jié)合律和分配律運(yùn)算規(guī)則：第三十四頁，共九十二頁，編輯于2023年，星期五5.3.1基本概念

GF(q)中定義的是模q的加法和乘法，例如GF(2)的運(yùn)算表如表所示：+01001110·01000101加法運(yùn)算表乘法運(yùn)算表第三十五頁，共九十二頁，編輯于2023年，星期五5.3.1基本概念2．矢量空間——所有n維矢量組成的集合就構(gòu)成了n維矢量空間Vn；——矢量對(duì)矢量的加法構(gòu)成一個(gè)加法交換群，即滿足封閉性、結(jié)合律和交換律，有恒等元和逆元。——滿足分配律

——滿足結(jié)合律——對(duì)于相乘恒等元有

矢量空間的性質(zhì)——8PSK調(diào)制時(shí)給出的信號(hào)點(diǎn)矢量圖，就是定義在GF(2)上的3維矢量空間V3

V3={000，001，010，011，100，101，110，111}

第三十六頁，共九十二頁，編輯于2023年，星期五5.3.1基本概念集合S中存在全零矢量（0,0,…,0），即零元；集合S中任何兩個(gè)矢量和仍在該集合中，即滿足封閉性。子空間——如果n維矢量空間Vn的一個(gè)子集S，滿足以下條件，則稱其為Vn的一個(gè)子空間：矢量與碼字的關(guān)系——一個(gè)碼長為n的碼字可以看成是一個(gè)有n個(gè)元素的矢量；——所有2n個(gè)n長碼字就構(gòu)成了定義在GF(2)(兩個(gè)元素：0、1的伽羅瓦域)上的n維矢量空間Vn

；——對(duì)于一個(gè)(n，k)線性分組碼，其編碼過程是從GF(2)上的n維矢量空間Vn中，尋找其中遵循某種編碼規(guī)則的一個(gè)子空間，而這個(gè)子空間中的所有碼字正好構(gòu)成了一個(gè)加法交換群，所以線性分組碼又稱為群碼。第三十七頁，共九十二頁，編輯于2023年，星期五5.3.1基本概念3．線性分組碼性質(zhì)封閉性

具有零元——即具有全零碼，記作A0。

具有負(fù)元——若Ai+Aj

=A0則稱其互為負(fù)元，（n,k）中Ai是它本身的負(fù)元。

滿足結(jié)合率和交換率第三十八頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼1．生成距陣矢量的線性無關(guān)——若Vn中k個(gè)矢量A1,A2,…,Ak，當(dāng)且僅當(dāng)，i=1,2,…,k時(shí)下式成立空間的基——在任意一個(gè)矢量空間或者子空間中，至少存在一組線性無關(guān)的矢量，可以張成這個(gè)空間,這一組矢量稱為該空間的基，基中矢量的數(shù)目稱為空間的維數(shù)。第三十九頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼實(shí)例分析——v1=(1000)，v2=(0100)，v3=(0010)，v4=(0001)線性無關(guān)的，作為基，張成一個(gè)4維矢量空間V4：第四十頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼

生成矩陣——矩陣G的每行矢量是基中的矢量，故稱之為生成矩陣；——由其可以得到矢量空間中的全部矢量；——上例中選取的基得到的生成矩陣恰好是4階單位矩陣，實(shí)際上線性無關(guān)的行矢量都可以作為生成矩陣的行矢量。2．編碼原理線性分組碼標(biāo)記——（n，k）線性分組碼，其碼字通常記作：

A=[an-1

an-2…a0]1×n——信息碼組M記作：

M=[mk-1

mk-2…m1

m0]1×k

第四十一頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼——生成矩陣G記作：編碼過程第四十二頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼實(shí)例——假設(shè)一個(gè)(6，3)分組生成矩陣為：——編碼過程為：第四十三頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼——該(6，3)碼是非系統(tǒng)碼，信息元m2、m0、m1分別出現(xiàn)在碼字A的第

1、3、5位，而2、4、6位是編碼器產(chǎn)生的監(jiān)督碼元，其碼表為：信息碼組M[m2

m1

m0]碼字A[a5

a4

a3

a2

a1

a0]信息碼組M[m2

m1

m0]碼字A[a5

a4

a3

a2

a1

a0]000001010011000000001101010011011110100101110111110101111000100110101011第四十四頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼——生成矩陣典型化實(shí)例分析3．系統(tǒng)碼編碼原理——編碼過程第四十五頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼——(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第四十六頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼——注意到系統(tǒng)碼中前k位即信息元，將其寫成線性方程組的形式——監(jiān)督關(guān)系第四十七頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼——監(jiān)督矩陣——監(jiān)督關(guān)系一般表達(dá)或生成矩陣典型陣一般形式第四十八頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼——(n，k)分組碼碼字可表示為：

(n，k)碼的一般編碼過程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)置得：第四十九頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼——也即——此時(shí)的系數(shù)矩陣，即監(jiān)督矩陣為第五十頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼——生成矩陣和監(jiān)督距陣的關(guān)系——(n，k)碼的一般編碼過程或即根據(jù)需要選定一監(jiān)督關(guān)系確定H陣；由H陣和Ｇ陣的關(guān)系確定G陣；由A=M·G生成所有碼字。

第五十一頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼——伴隨式S和錯(cuò)誤圖樣E的關(guān)系伴隨式——二者并不是一一對(duì)應(yīng)的關(guān)系，因?yàn)殄e(cuò)誤圖樣有2n種表現(xiàn)形式，而伴隨式僅有2r種表現(xiàn)形式，（注意r=n-k<n），且其中

S=0說明傳輸無錯(cuò)，這在該(n，k)分組碼用于檢錯(cuò)時(shí)已足夠。但發(fā)生了錯(cuò)誤卻不能檢出是完全有可能的，例如封閉性錯(cuò)誤。4．伴隨式與檢錯(cuò)原理第五十二頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼——(6，3)分組碼的監(jiān)督矩陣為：實(shí)例分析——伴隨式第五十三頁，共九十二頁，編輯于2023年，星期五5.3.2線性分組碼編碼——(6，3)分組碼伴隨式計(jì)算電路第五十四頁，共九十二頁，編輯于2023年，星期五5.3.3漢明碼——將監(jiān)督矩陣記成列矢量的形式，H=[h0

h1…h(huán)n-2

hn-1]，則漢明碼定義——伴隨式和錯(cuò)誤圖樣的關(guān)系——單個(gè)錯(cuò)誤時(shí)的伴隨式恰好與H的一個(gè)列矢量對(duì)應(yīng)，只要H的各個(gè)列矢量不為0矢量，且各不相同，則可以糾正單個(gè)錯(cuò)誤。第五十五頁，共九十二頁，編輯于2023年，星期五5.3.3漢明碼——漢明碼的另一種描述方式：對(duì)于任何的整數(shù)，必存在一個(gè)(n，k)

漢明碼，碼長n和監(jiān)督元數(shù)目r=n-k滿足n=2r-1(除去全零情況)漢明碼特點(diǎn)——可以糾正一位傳輸錯(cuò)誤，且d0=3，——碼長和監(jiān)督元的關(guān)系：n=2r-1實(shí)例分析——(7，4)漢明碼

——首先構(gòu)造其監(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)督矩陣：第五十六頁，共九十二頁，編輯于2023年，星期五5.3.3漢明碼——任意調(diào)換監(jiān)督矩陣各列位置并不影響碼的糾錯(cuò)能力，——將其轉(zhuǎn)化成典型陣的形式，并由其可以得到生成矩陣G——由A=MG得到其所有的碼字，如下表所示：第五十七頁，共九十二頁，編輯于2023年，星期五5.3.3漢明碼——假設(shè)發(fā)送端的碼字是A15=1111111，——傳輸過程中第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

a0000000010010001101000101011001110000

0000001

0110010

1010011

1100100

1100101

1010110

0110111

000100010011010101111001101111011111000

1111001

1001010

0101011

0011100

0011101

01011101001111

111第五十八頁，共九十二頁，編輯于2023年，星期五5.3.3漢明碼——下表給出了該（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ò)。第五十九頁，共九十二頁，編輯于2023年，星期五5.3.3漢明碼——完備性定義漢明碼完備碼性錯(cuò)誤位置錯(cuò)誤圖樣E[e6

e5

e4

e3

e2

e1

e0]伴隨式S[s2

s1

s0]無錯(cuò)0000000000b00000001001b10000010010b20000100100b30001000011b40010000101b50100000110b61000000111第六十頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——一個(gè)(7，3)系統(tǒng)循環(huán)碼碼表如下所示：1．基本概念——一類具有循環(huán)移位特性的線性分組碼，即其中的一個(gè)碼字經(jīng)過循環(huán)移位后仍然是該分組碼的碼字定義信息碼組Mm2

m1

m0碼字Aa6

a5

a4

a3

a2

a1

a0信息碼組Mm2

m1

m0碼字Aa6

a5

a4

a3

a2

a1

a000000101001100000000010111010111001110011001011101111001011101110011001011110010第六十一頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——例如A4=0111001，對(duì)應(yīng)的碼多項(xiàng)式為：碼多項(xiàng)式——(n，k)循環(huán)碼中，為了便于描述與計(jì)算，經(jīng)常使用n-1次碼多項(xiàng)式來表示碼字，碼字A=[an-1

an-2…a1

a0]，它對(duì)應(yīng)的碼多項(xiàng)式為：——A4向左循環(huán)移1位得A7=1110010，這相當(dāng)于將A4(x)乘以x，即第六十二頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——對(duì)于(7，3)循環(huán)碼的碼多項(xiàng)式，其最高次數(shù)不能超過6，解決該問題的辦法是對(duì)上式作模x7+1運(yùn)算：——A7向左循環(huán)移1位得A6=1100101，但若將A7(x)乘以x得到多項(xiàng)式為——其計(jì)算過程如下：第六十三頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼2．生成多項(xiàng)式和生成矩陣——(n，k)循環(huán)碼中的r=n-k次碼多項(xiàng)式，其次數(shù)最低（0元除外）；——其它所有的碼多項(xiàng)式都能被g(x)整除；——并且g(x)是xn+1的一個(gè)因式。生成多項(xiàng)式g(x)——例如本節(jié)前面給出的(7，3)循環(huán)碼，其生成多項(xiàng)式為：第六十四頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——若g(x)含有(x+1)因式，對(duì)應(yīng)的(n，k)系統(tǒng)循環(huán)碼，能夠檢出所有奇數(shù)個(gè)錯(cuò)誤；

(n，k)系統(tǒng)循環(huán)碼檢錯(cuò)能力與g(x)的關(guān)系——若g(x)含有常數(shù)項(xiàng)1因式，且不能整除xe+1，則對(duì)應(yīng)的(n，k)系統(tǒng)循環(huán)碼，能夠檢出所有的兩位錯(cuò)誤；——若g(x)含有常數(shù)項(xiàng)1因式，對(duì)應(yīng)的(n，k)系統(tǒng)循環(huán)碼，能夠檢出所有突發(fā)長度r的突發(fā)錯(cuò)誤，并且對(duì)突發(fā)長度等于r+1的突發(fā)錯(cuò)誤的漏檢率為2-(r-1)，對(duì)突發(fā)長度大于r+1的突發(fā)錯(cuò)誤的漏檢率為2-r。第六十五頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——CRC-12：標(biāo)準(zhǔn)生成多項(xiàng)式——CRC-16：——CRC-CCITT：——CRC-32：第六十六頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——g(x)、xg(x)、x2g(x)、…、xk-1g(x)是(n，k)循環(huán)碼的k個(gè)線性無關(guān)的碼字，所以可得其生成距陣G，用碼多項(xiàng)式表示G的各行：生成矩陣G——若信息碼組M=[mk-1

mk-2…m0]，則：第六十七頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——上式同時(shí)提供了循環(huán)碼的一種編碼方法，但由其得到的循環(huán)碼是非系統(tǒng)碼，因?yàn)榇藭r(shí)生成矩陣不是典型陣。——例如本節(jié)前面給出的(7，3)循環(huán)碼，——將該矩陣典型化之后，再按照A=MG編碼才能得到表本節(jié)前面給出的系統(tǒng)(7，3)循環(huán)碼；——實(shí)際應(yīng)用中，系統(tǒng)循環(huán)碼的編譯碼通常是由g(x)經(jīng)過簡單的代數(shù)運(yùn)算來實(shí)現(xiàn)。第六十八頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——系統(tǒng)(n，k)循環(huán)碼碼字：編碼原理——用碼多項(xiàng)式來表示為：3．編碼A=[an-1

an-2…an-k

ar-1

…a1

a0]=[mk-1

mk-2…m0

ar-1

…a1

a0]第六十九頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——式中M(x)是信息碼組碼多項(xiàng)式，所以只需要確定r(x)——已知循環(huán)碼的所有碼字都能夠被g(x)整除，r(x)可由下式確定：——(n，k)循環(huán)碼的生成多項(xiàng)式為：編碼器——其中r=n-k，則該(n，k)系統(tǒng)循環(huán)碼的編碼電路如下圖所示：第七十頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——r級(jí)線性移位寄存器的初始狀態(tài)為全零，所有開關(guān)均向下連通；——在寄存器時(shí)鐘的控制下進(jìn)行k次移位，輸出M(x)的系數(shù)(即信息碼組)，同時(shí)實(shí)現(xiàn)除法電路的功能；編碼器工作過程第七十一頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——所有開關(guān)向下連通，輸入下一組信息重復(fù)上述過程。實(shí)例分析——所有開關(guān)均倒向上方連通，在寄存器時(shí)鐘的控制下再經(jīng)過r=n-k

次移位，將監(jiān)督元輸出到信道；——本節(jié)前面給出的(7，3)循環(huán)碼生成多項(xiàng)式：g(x)=x4+x2+x+1

由其可得編碼電路如下圖所示：第七十二頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——假設(shè)M=110，編碼器工作過程如下表所示輸入移位寄存器狀態(tài)反饋輸出R1R2R3R4f0000000m2m1m0110111100101010111110a6a5a4信息元0000000010000100001001010101a3a2a1a0監(jiān)督元第七十三頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——現(xiàn)在檢驗(yàn)上表編碼結(jié)果，因?yàn)镸=110，所以——即所得的碼字為A=1100101。第七十四頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——系統(tǒng)循環(huán)碼的每一個(gè)碼字都能夠被生成多項(xiàng)式g(x)整除：檢錯(cuò)譯碼原理——發(fā)送端發(fā)送的碼字為3．譯碼——接收的碼字為——錯(cuò)誤圖樣——伴隨式第七十五頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——可以證明：——若S等于0判定傳輸無錯(cuò)，否則判定傳輸出錯(cuò)?！獧z錯(cuò)譯碼原理圖：第七十六頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼——寄存器置零，開關(guān)S向下連通；——在寄存器時(shí)鐘的控制下經(jīng)n次移位后將接收碼字B輸入，此時(shí)寄存器中存儲(chǔ)的即伴隨式

(n，k)循環(huán)碼伴隨式計(jì)算電路其工作過程如下：——將開關(guān)向上打開，經(jīng)r=n-k次移位讀出伴隨式。第七十七頁，共九十二頁，編輯于2023年，星期五5.3.4循環(huán)碼糾錯(cuò)譯碼原理——確定循環(huán)碼的糾錯(cuò)能力;——根據(jù)[模g(x)]計(jì)算伴隨式，若