第四章 差錯(cuò)控制編碼

第四章差錯(cuò)控制編碼4.1引言4.1常用的檢錯(cuò)碼4.3常用的簡單編碼4.4線性分組碼4.5循環(huán)碼4.6卷積碼4.7網(wǎng)格編碼調(diào)制●——主要內(nèi)容4.1概述4.1.1信道編碼4.1.2差錯(cuò)控制方式4.1.3糾錯(cuò)編碼的基本原理4.1引言信源編碼:是為了提高數(shù)字信號的有效性以及為了使模擬信號數(shù)字化而采取的編碼。4.1.1信道編碼信道編碼:是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。差錯(cuò)控制編碼屬信道編碼，要求在滿足有效性前提下，盡可能提高數(shù)字通信的可靠性。目的差錯(cuò)控制的目的是用信道編碼的方法檢測和糾正誤碼，降低誤比特率。前向糾錯(cuò)法（FEC）自動請求重發(fā)法（ARQ）混合糾錯(cuò)(HEC)反饋檢驗(yàn)法4.1.2差錯(cuò)控制方式

1.檢錯(cuò)重發(fā)法（ARQ）(又叫自動請求重傳)

由發(fā)端送出能夠發(fā)現(xiàn)錯(cuò)誤的碼，由收端判決傳輸中無錯(cuò)誤產(chǎn)生，如果發(fā)現(xiàn)錯(cuò)誤，則通過反向信道把這一判決結(jié)果反饋給發(fā)端，然后，發(fā)端把收端認(rèn)為錯(cuò)誤的信息再次重發(fā)，從而達(dá)到正確傳輸?shù)哪康?。?yōu)點(diǎn):是譯碼設(shè)備簡單，對突發(fā)錯(cuò)誤和信道干擾較嚴(yán)重時(shí)有效，可達(dá)到良好的性能缺點(diǎn):需要雙向信道，實(shí)時(shí)性差A(yù)utomaticrepeatrequest

2.前向糾錯(cuò)方式FEC(ForwordErrorCorrection)發(fā)端發(fā)送能夠糾正錯(cuò)誤的碼，收端收到信碼后自動地糾正傳輸中的錯(cuò)誤。優(yōu)點(diǎn):單向傳輸，實(shí)時(shí)性好缺點(diǎn):譯碼設(shè)備較復(fù)雜。

3.混合糾錯(cuò)方式發(fā)端發(fā)送具有自動糾錯(cuò)同時(shí)又具有檢錯(cuò)能力的碼。收端收到碼后，檢查差錯(cuò)情況，如果錯(cuò)誤在碼的糾錯(cuò)能力范圍以內(nèi)，則自動糾錯(cuò)，如果超過了碼的糾錯(cuò)能力，但能檢測出來，則經(jīng)過反饋信道請求發(fā)端重發(fā)。HEC(Hybrid

ErrorCorrection)具有自動糾錯(cuò)和檢錯(cuò)重發(fā)的優(yōu)點(diǎn)，可達(dá)到較低的誤碼率檢錯(cuò)重發(fā)系統(tǒng)根據(jù)工作方式又可分為三種，即停發(fā)等候重發(fā)系統(tǒng)、返回重發(fā)系統(tǒng)和選擇重發(fā)系統(tǒng)隨機(jī)信道:差錯(cuò)的出現(xiàn)是隨機(jī)的，而且錯(cuò)誤之間是統(tǒng)計(jì)獨(dú)立的。按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨機(jī)信道、突發(fā)信道和混合信道。恒參高斯白噪聲信道是典型的隨機(jī)信道具有脈沖干擾的信道是典型的突發(fā)信道突發(fā)信道:錯(cuò)誤是成串成群出現(xiàn)的，即在短時(shí)間內(nèi)出現(xiàn)大量錯(cuò)誤?；旌闲诺?隨機(jī)錯(cuò)誤和成串錯(cuò)誤都占有相當(dāng)比例短波信道和對流層散射信道是混合信道4.1.3糾錯(cuò)編碼的基本原理

例：2位二進(jìn)制數(shù)字構(gòu)成的碼組，共有4種不同的組合。若將其全部利用來表示天氣，則可以表示4種不同的天氣。00(晴)，01(多云)，10(陰)，11(雨)，在信息碼序列中加監(jiān)督碼就稱為差錯(cuò)控制編碼，也叫糾錯(cuò)編碼。不同的編碼方法，有不同的檢錯(cuò)和糾錯(cuò)能力，監(jiān)督碼元越多，檢（糾）錯(cuò)能力越強(qiáng)。

注意糾錯(cuò)碼的分類(1)根據(jù)糾錯(cuò)碼各碼組信息碼元和監(jiān)督碼元的函數(shù)關(guān)系，可分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線性方程式，則稱為線性碼，否則為非線性碼。關(guān)系涉及的范圍，可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息碼元有關(guān)；卷積碼中的碼元不僅與本組的信息碼元有關(guān)，而且還與前面若干組的信息碼元有關(guān)。

根據(jù)碼的用途，可分為檢錯(cuò)碼和糾錯(cuò)碼。檢錯(cuò)碼以檢錯(cuò)為目的，不一定能糾錯(cuò)；糾錯(cuò)碼以糾錯(cuò)為目的，一定能檢錯(cuò)。

按監(jiān)督碼與信息碼的位置關(guān)系分系統(tǒng)碼與非系統(tǒng)碼

(或說根據(jù)編碼后信碼是否保持原來的形式)

1.分組碼(n,k)krnk是每組二進(jìn)制信息碼元的數(shù)目，n是編碼碼組的碼元總位數(shù)又稱為碼組長度，簡稱碼長。n-k=r為每個(gè)碼組中的監(jiān)督碼元數(shù)目。分組碼是對每段k位長的信息組以一定的規(guī)則增加r個(gè)監(jiān)督元，組成長為n的碼字。碼重(weight)一個(gè)碼組中“1”的數(shù)目碼距(distance)兩個(gè)等長碼組之間對應(yīng)位置上不同的位數(shù)，又叫漢明(Hamming)距。最小碼距(碼的最小距離)d０dmin碼組集中任意兩個(gè)碼字之間距離的最小值2.檢錯(cuò)和糾錯(cuò)能力

碼的最小距離d0直接關(guān)系著碼的檢錯(cuò)和糾錯(cuò)能力；任一(n,k)分組碼，若要在碼字內(nèi):(1)檢測e個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離d0≥e+1

ABe1若一種編碼的最小碼距為d0,則能檢出d0-1個(gè)錯(cuò)碼。(2)糾正t個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離d0≥2t+1;AB1tt(3)糾正t個(gè)同時(shí)檢測e(>t)個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離d0≥t+e+1。

t1eAB3.編碼效率編碼效率R來衡量有效性:R=k/n其中,k是信息元的個(gè)數(shù)，n為碼長4.2常用的幾種簡單分組碼4.2.1奇偶監(jiān)督碼

1.中心思想:在原信息碼后面附加一個(gè)監(jiān)督碼元，使得碼組中“1”的個(gè)數(shù)是奇數(shù)或偶數(shù)。假設(shè)一個(gè)碼組長度n（an-1an-2an-3------a0），其中前n-1位是信息碼，最后一位a0為校驗(yàn)位，那么，對于偶校驗(yàn)碼2.檢驗(yàn)關(guān)系式:監(jiān)督碼元a0的取值（0或1）可由下式?jīng)Q定：

對于奇校驗(yàn)碼必須保證

監(jiān)督碼元a0的取值（0或1）可由下式?jīng)Q定：

3.特點(diǎn):

2.檢錯(cuò)能力:只能檢測出奇數(shù)個(gè)錯(cuò)碼不能進(jìn)行糾錯(cuò)。1.d0=22.奇偶監(jiān)督碼的編碼效率R為

當(dāng)n很大時(shí)，編碼效率高3.編譯碼器簡單4.一般用于計(jì)算機(jī)數(shù)據(jù)通信4.2.2二維奇偶監(jiān)督碼(又稱行列監(jiān)督碼，方陣校驗(yàn)碼)1.基本思想：與一維奇偶監(jiān)督碼相似，不同點(diǎn)在于每一個(gè)碼元都要受到縱橫兩個(gè)方向的監(jiān)督。例如：有50個(gè)待發(fā)送的碼元，將它們排成5行10列(5×10)方陣，方陣中每一行是一個(gè)碼組，每行最后加上一個(gè)監(jiān)督碼進(jìn)行行監(jiān)督，同樣在每一列的最后也加上一個(gè)監(jiān)督碼進(jìn)行列監(jiān)督然后按行或按列發(fā)送：2.檢錯(cuò)能力：

接收端按同樣行列排成方陣，發(fā)現(xiàn)不符合行列監(jiān)督規(guī)則的判決有錯(cuò)，其檢錯(cuò)能力(1).能檢出所有行，列中的奇數(shù)個(gè)錯(cuò)誤。(2).能發(fā)現(xiàn)大部分偶數(shù)個(gè)錯(cuò)誤：(3).錯(cuò)碼位置處于矩形四個(gè)角時(shí)檢不出錯(cuò)誤。

3.特點(diǎn)(1)適合檢測突發(fā)錯(cuò)碼(2)一般用于短波系統(tǒng)4.2.3恒比碼(又稱等重碼或定1碼)

1.基本思想：

每個(gè)碼組含有相同數(shù)目的“1”和“0”，即“0”的個(gè)數(shù)與“1”的個(gè)數(shù)的比值恒定，故得此名。這種碼在檢測時(shí)，只要計(jì)算接收碼組中“1”的數(shù)目有無變化，就知道有無錯(cuò)碼。

2.檢錯(cuò)能力：只有當(dāng)1→0和0→1成對出現(xiàn)時(shí)無法檢錯(cuò)，其余情況均能檢錯(cuò)。

∴檢錯(cuò)能力很強(qiáng)

數(shù)字?jǐn)?shù)字保護(hù)電碼123456789001011110011011011010001111010111100011101001101101中國電傳通信保護(hù)碼采用n=5中取w=3的恒比碼。每個(gè)漢字用4位阿拉伯?dāng)?shù)字表示，而每個(gè)數(shù)字用5位二進(jìn)制符號構(gòu)成：

中文電報(bào)編碼首先將每一個(gè)單字編碼為四位十進(jìn)制數(shù)字，再將每一位十進(jìn)制數(shù)字用二進(jìn)制的五單位數(shù)字保護(hù)碼表示。通信

663902071010110101101101001101101110010110111100

國際電報(bào)通信中廣泛采用的是“7中取3碼”，許用碼字共有35個(gè)，可分別表示26個(gè)字母和其它的一些符號。

3、特點(diǎn)非線性分組碼，但不是系統(tǒng)碼檢錯(cuò)功能簡單，編譯碼設(shè)備簡單常用于鍵盤發(fā)送系統(tǒng)4.2.4正反碼1.中心思想

r=k.

編碼的監(jiān)督位數(shù)目與信息位數(shù)目相同，監(jiān)督碼是信息碼的重復(fù)還是反碼，由信息碼中1的個(gè)數(shù)而定。編碼信息碼中含有奇數(shù)個(gè)1重復(fù)信息碼中含有偶數(shù)個(gè)1取反碼譯碼：由校驗(yàn)碼進(jìn)行譯碼信息位⊕監(jiān)督位=合成碼若接收碼組的信息位中有奇數(shù)個(gè)1，則合成的碼組為檢驗(yàn)碼若接收碼組的信息位中有偶數(shù)個(gè)1，則合成的碼組的反碼為檢驗(yàn)碼由合成碼得校驗(yàn)碼收端根據(jù)校驗(yàn)碼組進(jìn)行檢錯(cuò)檢驗(yàn)碼組全為0，無錯(cuò)碼有k-1個(gè)1，1個(gè)0則信息碼組中有一位錯(cuò)碼，其位置對應(yīng)檢驗(yàn)碼組中0的位置有k-1個(gè)0，1個(gè)1則監(jiān)督碼中有一位錯(cuò)碼，其位置對應(yīng)檢驗(yàn)碼組中1的位置其它組合，錯(cuò)碼多于一個(gè)例：收到碼組為10010101102.檢錯(cuò)能力正反碼具有糾正一位錯(cuò)碼的能力，并能檢出全部兩位以下的錯(cuò)碼和部分兩位以上的錯(cuò)碼3.特點(diǎn)1.效率：50﹪因?yàn)閗=r2.常用于電報(bào)通信中4.2.5群計(jì)數(shù)碼群計(jì)數(shù)碼是將信息碼元分組后，計(jì)算每組碼元中1的個(gè)數(shù)，然后將這個(gè)數(shù)目的二進(jìn)制表示為監(jiān)督碼元，一起送往發(fā)送端。例：一組8位的信息碼元為10111001，其中1的個(gè)數(shù)為5個(gè)，于是將101作為監(jiān)督碼元。這樣傳輸?shù)拇a組為10111001101收端只要檢測監(jiān)督碼元所標(biāo)示的1的數(shù)目與信息碼元的1的數(shù)目是否相同來判斷傳輸過程中有無錯(cuò)誤。特點(diǎn)：非線性分組系統(tǒng)碼,群計(jì)數(shù)碼的檢錯(cuò)能力很強(qiáng)，它可以檢測除1變0和0變1成對出現(xiàn)的錯(cuò)誤以外的其他形式的錯(cuò)誤。4.3線性分組碼

線性:監(jiān)督碼元與信息碼元滿足線性關(guān)系分組(n,k)（an-1an-2an-3------a0）一、性質(zhì)1、任意兩許用碼組之和（逐位模2和）仍為一許用碼組，即線性碼具有封閉性。2、最小碼距等于非零碼組中的最小碼重回顧奇偶監(jiān)督碼在接收端解碼時(shí)，實(shí)際上就是在計(jì)算若S＝0，認(rèn)為無錯(cuò)若S＝1，認(rèn)為有錯(cuò)S只有兩種取值，只能代表有、無錯(cuò)兩種信息，不能指出錯(cuò)碼位置。監(jiān)督關(guān)系式校正子在（n,k）碼中，為能糾正一位錯(cuò)誤要求在（n,k）碼中，k=4。為能糾正一位錯(cuò)碼，則r至少應(yīng)為多少？舉例說明如何構(gòu)造監(jiān)督關(guān)系式：上例中，若取r=3，則n=k+r=7。(7,4)線性分組碼（a6a5a4a3a2a1a0)校正子與錯(cuò)碼位置的對應(yīng)關(guān)系如表規(guī)定(也可以另外規(guī)定)。S1S2S3錯(cuò)碼位置S1S2S3錯(cuò)碼位置001a0101a4010a1110a5100a2111a6011a3000無錯(cuò)由表可見，當(dāng)一錯(cuò)碼位置在a2,a4，a5或a6時(shí)校正子S1為1；否則S1為0即構(gòu)成如下關(guān)系由此解出給定信息位后，可直接按上式算出監(jiān)督位監(jiān)督方程信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a000000001000111000101110011000010101101001000111101011001010011011000010101101110101001100111110100011100011111112、監(jiān)督矩陣H和生成矩陣G

改寫為(模2)簡記為

或稱為監(jiān)督矩陣H矩陣的各個(gè)行是線性無關(guān)的行數(shù)=監(jiān)督位數(shù)，列數(shù)=碼字長度典型陣r行n列轉(zhuǎn)置得K行r列Q=PT，在Q矩陣的左邊在加上一個(gè)k×k的單位矩陣，就形成了一個(gè)新矩陣G：

典型形式生成矩陣K行n列稱為生成矩陣生成矩陣G的每一行都是一個(gè)碼組G為典型生成矩陣，則得到的碼為系統(tǒng)碼否則得到的碼為非系統(tǒng)碼例【1】已知線性（6，3）碼的生成矩陣為

求（1）信息碼組為101對應(yīng)的編碼碼組（2）所有許用碼組、各碼組的碼重、最小碼距和該碼的差錯(cuò)控制能力。

例2已知（7，4）碼的生成矩陣為：列出所有許用碼組并求監(jiān)督矩陣?yán)?課后習(xí)題9-61、寫出監(jiān)督方程2、由監(jiān)督方程求出所有許用碼組3、求生成矩陣4、最小碼距？只用于檢錯(cuò)，能檢出幾位錯(cuò)碼？只用于糾錯(cuò)？同時(shí)用于檢錯(cuò)和糾錯(cuò)？若發(fā)送碼組為表示該位接收碼元無錯(cuò)；表示該位接收碼元有錯(cuò)。3、譯碼接收碼組為二者之差為E稱為錯(cuò)誤圖樣

接收端譯碼時(shí)計(jì)算錯(cuò)誤圖樣與校正子之間有確定的關(guān)系無錯(cuò)時(shí)，S等于零有錯(cuò)，S不等于零。校正子(伴隨式)糾錯(cuò)-----------只糾一位錯(cuò)誤時(shí)例4

設(shè)驗(yàn)證3個(gè)接收碼組是否發(fā)生差錯(cuò)？若在某碼組中有錯(cuò)碼，錯(cuò)碼的校正子是什么？然后再指出發(fā)生錯(cuò)碼的碼字中，哪位有錯(cuò)？且有3個(gè)接收碼組解：1）若無錯(cuò)，則錯(cuò)誤圖樣為0，S為0

B1無錯(cuò)B2錯(cuò)B3錯(cuò)2）∵

S2=H第1列∴E=[100000]第1位錯(cuò)同理S3=H第3列∴E=[001000]第3位錯(cuò)例5、已知一（7，4），監(jiān)督碼元和信息碼元之間的關(guān)系為：求（1）信息碼字I=[0011]時(shí)的編碼碼組

（2）

如果接收的碼字B=[1000101]，確定收到的碼組是否有錯(cuò)，并糾正。4、漢明碼（1）碼長滿足（2）最小碼距d0=3（3）編碼效率§4.4

循環(huán)碼循環(huán)碼除具有線性碼的一般性質(zhì)外,還具有循環(huán)性

即任一碼組循環(huán)一位以后，仍為該循環(huán)碼中的一個(gè)許用碼組。一、循環(huán)碼的特點(diǎn)線性分組碼循環(huán)碼舉例——(7,3)循環(huán)碼碼組信息位監(jiān)督位碼組信息位監(jiān)督位編號a6a5a4a3a2a1a0編號a6a5a4a3a2a1a00000000041001011100101115101110020101110611001013011100171110010例如A=0011101A(x)=0x6+0x5+1x4+1x3+1x2+0x1+1x0=x4+x3+x2+12、碼多項(xiàng)式——碼組的多項(xiàng)式表示二、循環(huán)碼的運(yùn)算1、碼多項(xiàng)式的按模運(yùn)算若一個(gè)整數(shù)m,若可以表示為則：m≡

p(模n)多項(xiàng)式F(x)被n次多項(xiàng)式N(x)除，得到商式q(x)和一個(gè)次數(shù)小于n的余式R(x)，即碼多項(xiàng)式系數(shù)仍按模2運(yùn)算，即只取值0和1則寫為F(x)≡

R(x)

(模N(x))例如在循環(huán)碼中，若T(x)是一個(gè)長為n的許用碼組，則在按模運(yùn)算下，亦是一個(gè)許用碼組。則T’（X）也是該編碼碼組中的一個(gè)許用碼組假設(shè)用g（x）表示一個(gè)前k-1位皆為0（第k位不為0）的碼組生成多項(xiàng)式2、循環(huán)碼的生成多項(xiàng)式（1）g(x)是一個(gè)常數(shù)項(xiàng)為1的次多項(xiàng)式；（2）g(x)是的一個(gè)因式；（3）該循環(huán)碼中其它碼多項(xiàng)式都是g(x)的倍式。

任意一碼組多項(xiàng)式可表示為：一個(gè)k位的信息碼組Ｄ＝［dk-1,dk-2,…….d0]信息碼多項(xiàng)式:T(x)=d(x)g(x)d(x)代入T(X)得：不大于n-1次的多項(xiàng)式假如輸入信息碼元mk-1mk-2…m0則例：求（7，4）循環(huán)碼的生成多項(xiàng)式g(x),當(dāng)信息碼組D=[1010]時(shí)，求輸出碼組若能找到k個(gè)線性無關(guān)的碼組,就能構(gòu)成矩陣G。

g(x)、xg(x)，x2g(x)，…，xk-1g(x)都是許用碼組，而且這k個(gè)碼組是線性無關(guān)的。因此可以用來構(gòu)成循環(huán)碼的生成矩陣G。3．循環(huán)碼的生成矩陣G例表9—6的循環(huán)碼,唯一的一個(gè)(n-k)次碼多項(xiàng)式代表的碼組是0010111，相對應(yīng)的碼多項(xiàng)式為因此,循環(huán)碼的生成矩陣G可以寫成這個(gè)生成矩陣不是系統(tǒng)碼的生成矩陣，可以通過行變換，變換成系統(tǒng)碼的生成矩陣。

g(x)＝x4+x2+x+1將此g(x)代入上式，得到三.循環(huán)碼的編