通信原理-CT8差錯(cuò)控制編碼課件

8.1差錯(cuò)控制編碼的基本概念8.2線性分組碼8.3循環(huán)碼第8章差錯(cuò)控制編碼返回主目錄8.1差錯(cuò)控制編碼的基本概念第8章差錯(cuò)控制編1概述差錯(cuò)控制編碼：信道編碼在數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼和信道編碼。信源編碼是為了提高數(shù)字信號(hào)的有效性以及為了使模擬信號(hào)數(shù)字化而采取的編碼。信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。數(shù)字信號(hào)在傳輸過(guò)程中，加性噪聲、碼間串?dāng)_等都會(huì)產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射功率，降低接收設(shè)備本身的噪聲，以及合理選擇調(diào)制、解調(diào)方法等。此外，還必須采用信道編碼技術(shù)。概述差錯(cuò)控制編碼：信道編碼28.1.1差錯(cuò)控制方式圖8-1差錯(cuò)控制方式8.1.1差錯(cuò)控制方式圖8-1差錯(cuò)控制方式31.前向糾錯(cuò)方式前向糾錯(cuò)方式記作FEC(ForwordErrorCorrection)。發(fā)端發(fā)送能夠糾正錯(cuò)誤的碼，收端收到信碼后自動(dòng)地糾正傳輸中的錯(cuò)誤。其特點(diǎn)是單向傳輸，實(shí)時(shí)性好，但譯碼設(shè)備較復(fù)雜。

1.前向糾錯(cuò)方式4

2.檢錯(cuò)重發(fā)方式檢錯(cuò)重發(fā)又稱自動(dòng)請(qǐng)求重傳方式，記作ARQ(AutomaticRepeatRequest)。由發(fā)端送出能夠發(fā)現(xiàn)錯(cuò)誤的碼，由收端判決傳輸中無(wú)錯(cuò)誤產(chǎn)生，如果發(fā)現(xiàn)錯(cuò)誤，則通過(guò)反向信道把這一判決結(jié)果反饋給發(fā)端，然后，發(fā)端把收端認(rèn)為錯(cuò)誤的信息再次重發(fā)，從而達(dá)到正確傳輸?shù)哪康?。其特點(diǎn)是需要反饋信道，譯碼設(shè)備簡(jiǎn)單，對(duì)突發(fā)錯(cuò)誤和信道干擾較嚴(yán)重時(shí)有效，但實(shí)時(shí)性差，主要在計(jì)算機(jī)數(shù)據(jù)通信中得到應(yīng)用。2.檢錯(cuò)重發(fā)方式53.混合糾錯(cuò)方式混合糾錯(cuò)方式記作HEC(HybridErrorCorrection)是FEC和ARQ方式的結(jié)合。發(fā)端發(fā)送具有自動(dòng)糾錯(cuò)同時(shí)又具有檢錯(cuò)能力的碼。收端收到碼后，檢查差錯(cuò)情況，如果錯(cuò)誤在碼的糾錯(cuò)能力范圍以內(nèi)，則自動(dòng)糾錯(cuò)，如果超過(guò)了碼的糾錯(cuò)能力，但能檢測(cè)出來(lái)，則經(jīng)過(guò)反饋信道請(qǐng)求發(fā)端重發(fā)。這種方式具有自動(dòng)糾錯(cuò)和檢錯(cuò)重發(fā)的優(yōu)點(diǎn)，可達(dá)到較低的誤碼率，因此，近年來(lái)得到廣泛應(yīng)用。3.混合糾錯(cuò)方式6另外，按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨機(jī)信道、突發(fā)信道和混合信道。恒參高斯白噪聲信道是典型的隨機(jī)信道，其中差錯(cuò)的出現(xiàn)是隨機(jī)的，而且錯(cuò)誤之間是統(tǒng)計(jì)獨(dú)立的。具有脈沖干擾的信道是典型的突發(fā)信道，錯(cuò)誤是成串成群出現(xiàn)的，即在短時(shí)間內(nèi)出現(xiàn)大量錯(cuò)誤。短波信道和對(duì)流層散射信道是混合信道的典型例子，隨機(jī)錯(cuò)誤和成串錯(cuò)誤都占有相當(dāng)比例。對(duì)于不同類型的信道，應(yīng)采用不同的差錯(cuò)控制方式。另外，按照噪聲或干擾的變化規(guī)律，可把信道分為78.1.2糾錯(cuò)碼的分類(1)根據(jù)糾錯(cuò)碼各碼組信息元和監(jiān)督元的函數(shù)關(guān)系，可分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線性方程式，則稱為線性碼，否則為非線性碼。(2)根據(jù)上述關(guān)系涉及的范圍，可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關(guān)；卷積碼中的碼元不僅與本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)。(3)根據(jù)碼的用途，可分為檢錯(cuò)碼和糾錯(cuò)碼。檢錯(cuò)碼以檢錯(cuò)為目的，不一定能糾錯(cuò)；而糾錯(cuò)碼以糾錯(cuò)為目的，一定能檢錯(cuò)。8.1.2糾錯(cuò)碼的分類88.1.3幾種簡(jiǎn)單的檢測(cè)碼(1)奇偶監(jiān)督碼。(2)二維奇偶監(jiān)督碼。(3)重復(fù)碼。(4)恒比碼。(5)ISBN國(guó)際統(tǒng)一圖書編號(hào)。

8.1.3幾種簡(jiǎn)單的檢測(cè)碼91奇偶監(jiān)督碼奇偶監(jiān)督碼是在原信息碼后面附加一個(gè)監(jiān)督元，使得碼組中“1”的個(gè)數(shù)是奇數(shù)或偶數(shù)。奇偶監(jiān)督碼分為奇監(jiān)督（校驗(yàn)）碼和偶監(jiān)督（校驗(yàn)）碼。1奇偶監(jiān)督碼奇偶監(jiān)督碼是在原信息碼后面附10設(shè)碼字A=［an-1,an-2,…,a1,a0］，對(duì)偶監(jiān)督碼有奇監(jiān)督碼情況相似，只是碼組中“1”的數(shù)目為奇數(shù)，即滿足條件而檢錯(cuò)能力與偶監(jiān)督碼相同。奇偶監(jiān)督碼的編碼效率R為設(shè)碼字A=［an-1,an-2,…,a1,a0］，對(duì)偶監(jiān)督碼112二維奇偶監(jiān)督碼2二維奇偶監(jiān)督碼12

碼字中1的數(shù)目與0的數(shù)目保持恒定比例的碼稱為恒比碼。由于恒比碼中，每個(gè)碼組均含有相同數(shù)目的1和0，因此恒比碼又稱等重碼，定1碼。這種碼在檢測(cè)時(shí)，只要計(jì)算接收碼元中1的數(shù)目是否正確，就知道有無(wú)錯(cuò)誤。

目前我國(guó)電傳通信中普遍采用3∶2碼，又稱“5中取3”的恒比碼，即每個(gè)碼組的長(zhǎng)度為5，其中3個(gè)“1”。這時(shí)可能編成的不同碼組數(shù)目等于從5中取3的組合數(shù)10，這10個(gè)許用碼組恰好可表示10個(gè)阿拉伯?dāng)?shù)字，如下表所示。而每個(gè)漢字又是以四位十進(jìn)制數(shù)來(lái)代表的。實(shí)踐證明，采用這種碼后，我國(guó)漢字電報(bào)的差錯(cuò)率大為降低。3重復(fù)碼4恒比碼（定比碼、等重碼、范德倫碼）

碼字中1的數(shù)目與0的數(shù)目保持恒定比例13七三定比碼（七單位碼）用于國(guó)際電報(bào)系統(tǒng)，碼長(zhǎng)為7，其中1的個(gè)數(shù)為3。這種碼的許用碼字為：3∶2恒比碼五三定比碼（五單位碼）用于國(guó)內(nèi)電報(bào)系統(tǒng)，碼長(zhǎng)為5，其中1的個(gè)數(shù)為3。這種碼的許用碼字為：代表26個(gè)英文字母和一些符號(hào)。代表國(guó)內(nèi)電報(bào)系統(tǒng)中的數(shù)字0~9。而每個(gè)漢字又是以四位十進(jìn)制數(shù)來(lái)代表的。七三定比碼（七單位碼）用于國(guó)際電報(bào)系統(tǒng)，碼長(zhǎng)為7，其中1的個(gè)148.1.4檢錯(cuò)和糾錯(cuò)的基本原理1.分組碼分組碼一般可用(n,k)表示。其中，k是每組二進(jìn)制信息碼元的數(shù)目，n是編碼碼組的碼元總位數(shù)，又稱為碼組長(zhǎng)度，簡(jiǎn)稱碼長(zhǎng)。n-k=r為每個(gè)碼組中的監(jiān)督碼元數(shù)目。簡(jiǎn)單地說(shuō)，分組碼是對(duì)每段k位長(zhǎng)的信息組以一定的規(guī)則增加r個(gè)監(jiān)督元，組成長(zhǎng)為n的碼字。在二進(jìn)制情況下，共有2k個(gè)不同的信息組，相應(yīng)地可得到2k個(gè)不同的碼字，稱為許用碼組。其余2n-2k個(gè)碼字未被選用，稱為禁用碼組。krn8.1.4檢錯(cuò)和糾錯(cuò)的基本原理1.分15在分組碼中，非零碼元的數(shù)目稱為碼字的漢明(Hamming)重量，簡(jiǎn)稱碼重。例如，碼字10110，碼重w=3。兩個(gè)等長(zhǎng)碼組之間相應(yīng)位取值不同的數(shù)目稱為這兩個(gè)碼組的漢明(Hamming)距離，簡(jiǎn)稱碼距。例如11000與10011之間的距離d=3。碼組集中任意兩個(gè)碼字之間距離的最小值稱為碼的最小距離，用dmin表示。最小碼距是碼的一個(gè)重要參數(shù)，它是衡量碼檢錯(cuò)、糾錯(cuò)能力的依據(jù)。在分組碼中，非零碼元的數(shù)目稱為碼字的漢明(H16如果線性分組碼(n,k)碼位信息位沒(méi)有變化，與信息碼元排列相同，并且與監(jiān)督位分開(kāi)，稱為系統(tǒng)碼，否則稱為非系統(tǒng)碼。信息元監(jiān)督元如果線性分組碼(n,k)碼位信息位沒(méi)有變化，與信息碼元排列相172.檢錯(cuò)和糾錯(cuò)能力若分組碼碼字中的監(jiān)督元在信息元之后，而且是信息元的簡(jiǎn)單重復(fù)，則稱該分組碼為重復(fù)碼。它是一種簡(jiǎn)單實(shí)用的檢錯(cuò)碼，并有一定的糾錯(cuò)能力。例如(2,1)重復(fù)碼，兩個(gè)許用碼組是00與11，d0=2，收端譯碼，出現(xiàn)01、10禁用碼組時(shí)，可以發(fā)現(xiàn)傳輸中的一位錯(cuò)誤。如果是(3,1)重復(fù)碼，兩個(gè)許用碼組是000與111,d0=3;當(dāng)收端出現(xiàn)兩個(gè)或三個(gè)1時(shí)，判為1，否則判為0。此時(shí)，可以糾正單個(gè)錯(cuò)誤，或者該碼可以檢出兩個(gè)錯(cuò)誤。2.檢錯(cuò)和糾錯(cuò)能力若分組碼碼字中的監(jiān)督18碼的最小距離dmin直接關(guān)系著碼的檢錯(cuò)和糾錯(cuò)能力；對(duì)于任一(n,k)分組碼，若要在碼字內(nèi):若檢測(cè)e個(gè)錯(cuò)誤，則要求dmin≥e+1;若糾正t個(gè)錯(cuò)誤，則要求dmin≥2t+1;若糾正t個(gè)錯(cuò)誤，同時(shí)發(fā)現(xiàn)e個(gè)錯(cuò)誤，則要求dmin≥t+e+1;t<e;e+12t+1t+e+1C1C2C’1C2C1C’1eettC1C2etC’1碼的最小距離dmin直接關(guān)系著碼的檢錯(cuò)和糾錯(cuò)193.編碼效率

用差錯(cuò)控制編碼提高通信系統(tǒng)的可靠性，是以降低有效性為代價(jià)換來(lái)的。我們定義編碼效率R來(lái)衡量有效性:R=k/n其中,k是信息元的個(gè)數(shù)，n為碼長(zhǎng)。對(duì)糾錯(cuò)碼的基本要求是:檢錯(cuò)和糾錯(cuò)能力盡量強(qiáng)；編碼效率盡量高；編碼規(guī)律盡量簡(jiǎn)單。實(shí)際中要根據(jù)具體指標(biāo)要求，保證有一定糾、檢錯(cuò)能力和編碼效率，并且易于實(shí)現(xiàn)。3.編碼效率208.2線性分組碼現(xiàn)以(7,4)分組碼為例來(lái)說(shuō)明線性分組碼的特點(diǎn)。設(shè)其碼字為A=［a6

a5

a4

a3

a2

a1

a0］，其中前4位是信息元，后3位是監(jiān)督元，可用下列線性方程組來(lái)描述該分組碼，產(chǎn)生監(jiān)督元。8.2線性分組碼現(xiàn)以(7,4)分組碼為21(7,4)碼的碼字表(7,4)碼的碼字表221監(jiān)督矩陣H和生成矩陣G

線性方程組為：1監(jiān)督矩陣H和生成矩陣G23其中,P為r×k階矩陣，Ir為r×r階單位矩陣?？梢詫懗蒆=［PIr］形式的矩陣稱為典型監(jiān)督矩陣。

HCT=0T，說(shuō)明H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來(lái)作為判斷接收碼字C是否出錯(cuò)的依據(jù)。并簡(jiǎn)記為H稱為監(jiān)督矩陣

其中,P為r×k階矩陣，Ir為r×r階單位矩24若把監(jiān)督方程補(bǔ)充為下列方程若把監(jiān)督方程補(bǔ)充為下列方程25可改寫為矩陣形式即：可改寫為矩陣形式即：26通信原理-CT8差錯(cuò)控制編碼課件27[C]=[m][G]系統(tǒng)碼的生成矩陣也稱為典型生成矩陣[G]=[Ik,Q]，[G]為k×n矩陣，[Q]為k×r矩陣，[Ik]為k×k單位陣。

[H][C]T=[0]系統(tǒng)碼的監(jiān)督矩陣也稱為基本監(jiān)督矩陣[H]=[PIr]，[H]為r×n矩陣，[P]為r×k矩陣，[Ir]為r×r單位陣。[H][G]T=[0]，同時(shí)有：[G][H]T=[0]稱[H]與[G]為正交矩陣，由[PIr][IkQ]T=[0]

[P+QT]=[0]，即[P]=[Q]T[Q]=[P]T

P矩陣與Q矩陣互為轉(zhuǎn)置矩陣。[C]=[m][G]282伴隨式(校正子)S

設(shè)發(fā)送碼組C=［an-1,an-2,…,a1,a0］，在傳輸過(guò)程中可能發(fā)生誤碼。接收碼組R=［bn-1,bn-2,…,b1,b0］，則收發(fā)碼組之差定義為錯(cuò)誤圖樣E，也稱為誤差矢量，即其中E=［en-1,en-2,…,e1,e0］，且當(dāng)bi=ai

當(dāng)bi≠ai

令S=RHT，稱為伴隨式或校正子。2伴隨式(校正子)S設(shè)發(fā)送碼組C=［an-29(7,4)分組碼S與E的對(duì)應(yīng)關(guān)系(7,4)分組碼S與E的對(duì)應(yīng)關(guān)系30[循環(huán)碼定義]：一個(gè)(n,k)線性分組碼C，如果碼組中的一個(gè)碼字的循環(huán)移位也是這個(gè)碼組中的一個(gè)碼字，則稱C為循環(huán)碼。稱為具有循環(huán)自閉性。C(0)={cn-1,cn-2,……c1,c0}∈CC(1)={cn-2,cn-3,……c0,cn-1}∈C[循環(huán)碼的多項(xiàng)式描述]：循環(huán)碼可以用監(jiān)督矩陣和生成矩陣描述，但更多地用域上多項(xiàng)式來(lái)描述，一個(gè)(n,k)循環(huán)的碼字矢量C(0)用一個(gè)n-1次多項(xiàng)式描述，可以表示為：C(x)=cn-1xn-1+cn-2xn-2+……+c1x+c0這個(gè)多項(xiàng)式稱為碼字多項(xiàng)式。碼字矢量的循環(huán)移位可以用x乘上C(x)后的模(xn+1)來(lái)表示。xC(x)=x(cn-1xn-1+cn-2xn-2+……+c1x+c0)=cn-1xn+cn-2xn-1+……+c1x2+c0x=cn-2xn-1+……+c1x2+c0x+cn-1(模xn+1)模xn+1相當(dāng)于xn+1=0；xn=18.3循環(huán)碼[循環(huán)碼定義]：8.3循環(huán)碼31(7,4)系統(tǒng)循環(huán)碼的編碼及碼字多項(xiàng)式如下表：g(x)=x3+x+1可以看出：每個(gè)碼字的循環(huán)移位仍然屬于這個(gè)碼組。并不是說(shuō)碼組是由一個(gè)碼字的循環(huán)移位構(gòu)成的，本例中是由四個(gè)碼字的循環(huán)移位構(gòu)成的。8.3循環(huán)碼(7,4)系統(tǒng)循環(huán)碼的編碼及碼字多項(xiàng)式如下表：g(x)=x3328.3循環(huán)碼(7,3)循環(huán)碼8.3循環(huán)碼(7,3)循環(huán)碼33在一個(gè)(n,k)循環(huán)碼中，有且僅有一個(gè)次數(shù)為n-k=r的碼字多項(xiàng)式，記為：g(x)=xr+gr-1xr-1+……+g1x+1同時(shí)：每個(gè)碼字多項(xiàng)式都是g(x)的倍式；每個(gè)次數(shù)小于等于n-1的g(x)的倍式必為一個(gè)碼字多項(xiàng)式。這時(shí)稱g(x)的(n,k)碼的生成多項(xiàng)式。[生成多項(xiàng)式的性質(zhì)]：是循環(huán)碼C中次數(shù)最低的非零碼字多項(xiàng)式，并且是唯一的，其次數(shù)為r=n-k。令g(x)=xr+gr-1xr-1+……+g1x+g0為一個(gè)(n,k)循環(huán)碼C中最低次數(shù)碼字多項(xiàng)式，則其常數(shù)項(xiàng)必為g0=1。(n,k)循環(huán)碼的生成多項(xiàng)式g(x)是xn+1的因式。在一個(gè)(n,k)循環(huán)碼中，有且僅有一個(gè)次數(shù)為n-k=r的碼字34在代數(shù)理論中，為了便于計(jì)算，常用碼多項(xiàng)式表示碼字。(n,k)循環(huán)碼的碼字，其碼多項(xiàng)式(以降冪順序排列)為[系統(tǒng)循環(huán)碼的編碼方法]：已知循環(huán)碼的生成矩陣,可以按以下步驟產(chǎn)生系統(tǒng)循環(huán)碼。首先定義以下多項(xiàng)式：m(x)=mk-1xk-1+mk-2xk-2+……+m1x+m0為信息碼字多項(xiàng)式；c(x)=cn-1xn-1+cn-2xn-2+……+c1x+c0為循環(huán)碼字多項(xiàng)式；g(x)=xr-1+gr-2xr-2+……+g1x+1為生成多項(xiàng)式；系統(tǒng)碼的編碼分為三步：用xn-k乘上m(x);用g(x)除以xn-km(x)，得到模g(x)的余式r(x)c(x)=xn-km(x)+r(x)為系統(tǒng)循環(huán)碼的碼字多項(xiàng)式。在代數(shù)理論中，為了便于計(jì)算，常用碼多項(xiàng)式表示碼字。(35[例]:(7,4)循環(huán)碼的生成多項(xiàng)式為g(x)=x3+x+1求m=[1010]的循環(huán)碼。解：m(x)=x3+x,xn-k=x3;xn-km(x)=x3(x3+x)=x6+x4r(x)=x+1C(x)=xn-km(x)+r(x)=x6+x4+x+1[C]=[1010011][例]:(7,4)循環(huán)碼的生成多項(xiàng)式為g(x)=x3+x+36[非系統(tǒng)循環(huán)碼的編碼方法]：已知循環(huán)碼的生成矩陣，可以方便的求出非系統(tǒng)循環(huán)碼，C(x)=m(x)g(x)。[例]:m=[1101]g(x)=x3+x+1C(x)=(x3+x2+1)(x3+x+1)=x6+x4+x3+x5+x3+x2+x3+x+1=x6+x5+x4+x3+x2+x+1[C]=[1111111]m=[0101];c(x)=(x2+1)(x3+x+1)=x5+x3+x2+x3+x+1=x5+x2+x+1[C]=[0100111][非系統(tǒng)循環(huán)碼的編碼方法]：37[循環(huán)碼的生成矩陣]：循環(huán)碼可以用域上多項(xiàng)式描述，也可以用生成矩陣描述。已知g(x)為循環(huán)碼C中的一個(gè)碼字多項(xiàng)式，由循環(huán)碼的循環(huán)特性可知，可以證明：在(n,k)循環(huán)碼的碼字多項(xiàng)式中，g(x),xg(x),……xk-1g(x)等k個(gè)碼字多項(xiàng)式必是線性無(wú)關(guān)（相互獨(dú)立的）的。根據(jù)線性空間的特性，可知，它們是一個(gè)k維子空間的基底，即由它們的線性組合可以生成這個(gè)k維子空間的2k個(gè)碼字。再根據(jù)線性分組碼生成矩陣的定義，它的行向量是由k個(gè)線性無(wú)關(guān)的碼字構(gòu)成的，可以得到(n,k)循環(huán)碼的一個(gè)多項(xiàng)式矩陣為：[循環(huán)碼的生成矩陣]：38通信原理-CT8差錯(cuò)控制編碼課件39例如(7,3)循環(huán)碼，n=7,k=3,r=4,其生成多項(xiàng)式及生成矩陣分別為例如(7,3)循環(huán)碼，n=7,k=3,r=4,其生成多40[非系統(tǒng)循環(huán)碼編碼電路]：非系統(tǒng)循環(huán)碼的產(chǎn)生為：C(x)=m(x)g(x),可知其編碼器為如下：D0D1D2m(x)C(x)x1x3x2[非系統(tǒng)循環(huán)碼編碼電路]：D0D1D2m(x)C(x)x1x41監(jiān)督多項(xiàng)式及監(jiān)督矩陣為了便于對(duì)循環(huán)碼編譯碼，通常還定義監(jiān)督多項(xiàng)式，令

其中g(shù)(x)是常數(shù)項(xiàng)為1的r次多項(xiàng)式，是生成多項(xiàng)式；h(x)是常數(shù)項(xiàng)為1的k次多項(xiàng)式，稱為監(jiān)督多項(xiàng)式。同理，可得監(jiān)督矩陣H

監(jiān)督多項(xiàng)式及監(jiān)督矩陣其中g(shù)(x)是常數(shù)項(xiàng)為1的r次多項(xiàng)42是h(x)的逆多項(xiàng)式。例如(9，3)循環(huán)碼，g(x)=x4+x3+x2+1，則其中是h(x)的逆多項(xiàng)式。例如(9，3)循環(huán)碼，g(x)=x4+43通信原理-CT8差錯(cuò)控制編碼課件44編碼方法和電路在編碼時(shí)，首先要根據(jù)給定的(n,k)值選定生成多項(xiàng)式g(x)，即應(yīng)在xn+1的因式中選一r=n-k次多項(xiàng)式作為g(x)。設(shè)編碼前的信息多項(xiàng)式m(x)為循環(huán)碼的碼多項(xiàng)式可表示為編碼方法和電路在編碼時(shí)，首先要根據(jù)給定的(45圖(7,3)循環(huán)碼編碼電路圖(7,3)循環(huán)碼編碼電路46表(7,3)循環(huán)碼的編碼過(guò)程表(7,3)循環(huán)碼的編碼過(guò)程47[系統(tǒng)碼編碼器]：為了構(gòu)成系統(tǒng)碼，可知C(x)=xn-km(x)+r(x)r(x)=xn-km(x)/g(x)[模g(x)]以(7,4)漢明碼為例：g(x)=x3+x+1編碼器電路如圖所示：它由r=n-k級(jí)移位寄存器構(gòu)成。輸入m(x)門1D0D1D2門2或門1xx2x31xx3x3C(x)[系統(tǒng)碼編碼器]：輸入m(x)門1D0D1D2門2或門1xx48[系統(tǒng)循環(huán)碼的生成矩陣與監(jiān)督矩陣]：[系統(tǒng)循環(huán)碼的生成矩陣與監(jiān)督矩陣]：49通信原理-CT8差錯(cuò)控制編碼課件50[大數(shù)邏輯譯碼器]：(門限譯碼器)S0S1S2S3大數(shù)門>2輸出7級(jí)緩存器A2A3A1C(x)C(x)R(x)[大數(shù)邏輯譯碼器]：(門限譯碼器)S0S1S2S3大數(shù)門>251其工作過(guò)程如下：由(7,3)循環(huán)碼生成多項(xiàng)式g(x)=x4+x3+x2+1的除法電路，計(jì)算R(x)的校驗(yàn)子多項(xiàng)式S(x)。n=7次移位后得到校驗(yàn)子(s0,s1,s2,s3)，存在校驗(yàn)子移位寄存器中，此時(shí)，R(x)已全部進(jìn)入7級(jí)緩存器中。停止譯碼器輸入，并開(kāi)始對(duì)rn-1=r6進(jìn)行檢查，也就是檢查A1=s3，A2=s1，A3=s2+s0中1的個(gè)數(shù)。如果1的個(gè)數(shù)為3，大數(shù)門輸出1。此時(shí)，緩存器移位一次，輸出r6，對(duì)它進(jìn)行糾錯(cuò)，如果1的個(gè)數(shù)小于3，大數(shù)門無(wú)輸出，r6直接輸出。除法電路循環(huán)移位一次，對(duì)r5進(jìn)行檢查，此時(shí)校驗(yàn)子寄存器中的內(nèi)容是對(duì)r5的計(jì)算結(jié)果。如果大數(shù)門輸出1，則對(duì)r5進(jìn)行糾錯(cuò)，否則，r5直接輸出。重復(fù)上述步驟，直至n=7次為止；第n=7次移位完畢后，如果校驗(yàn)子除法電路的狀態(tài)為全0，則說(shuō)明R(x)中的錯(cuò)誤是可以糾正的，否則說(shuō)明是不可糾正的。若是不可糾正的，譯碼器送出一個(gè)信號(hào)至用戶，表示R(x)有誤。然后重新清洗譯碼器的初始狀態(tài)，準(zhǔn)備接收第二各碼字。圖中的虛線是把大數(shù)門輸出的1反饋到除法電路的輸入端，以消除該錯(cuò)誤碼元對(duì)除法電路的影響。其工作過(guò)程如下：52[捕錯(cuò)譯碼

]8級(jí)緩存器7級(jí)緩存器門1門5門2門3門4W(Si(x))≤2檢測(cè)電路R(x)C(x)[捕錯(cuò)譯碼]8級(jí)緩存器7級(jí)緩存器門1門5門2門3門4W(S53譯碼過(guò)程如下：譯碼前所有移位寄存器和緩存器都為全0狀態(tài)，門2，門3開(kāi)，門1，門4，門5關(guān)。n=15次移位后，接收碼字的R(x)的15個(gè)碼元全部進(jìn)入15級(jí)緩存器，信息元在前7級(jí)，監(jiān)督元在后8級(jí)，同時(shí)進(jìn)入除法電路，得到校驗(yàn)子多項(xiàng)式S0(x)。如果S0(x)=0，說(shuō)明無(wú)錯(cuò)，打開(kāi)門5，輸出接收碼字。如果S0(x)≠0，說(shuō)明有錯(cuò)，進(jìn)行以下各步。此時(shí)門2關(guān)，門1開(kāi)，如果W(S0(x))≤2，檢測(cè)電路輸出有效，把門4打開(kāi)，把門3關(guān)閉，此時(shí)除法電路移位寄存器中的內(nèi)容就是接收碼字的后8位的錯(cuò)誤圖樣，只要接收碼字只錯(cuò)2位或2位以下，后8位錯(cuò)誤圖樣就等于全部錯(cuò)誤圖樣。這時(shí)移位15次，除法電路的狀態(tài)S0(x)=EP(x)通過(guò)門4與接收碼字的后8位逐次相加，完成糾錯(cuò)。然后門1關(guān)，門5開(kāi)，再移位15次，輸出接收碼字。如果W(S0(x))>2，則15級(jí)緩存器和除法電路都循環(huán)移位一次，再次檢測(cè)，若仍大于2，則繼續(xù)移位，當(dāng)移位I次后，檢測(cè)到W(S0(x))≤2，則說(shuō)明已經(jīng)檢測(cè)出錯(cuò)誤圖樣已進(jìn)入緩存器的后8位。這時(shí)門3關(guān)閉，門4打開(kāi)，繼續(xù)移位n-I次，進(jìn)行糾錯(cuò)。最后門1關(guān)，門2，門5開(kāi)，再移位15次輸出正確的接收碼字。從以上步驟中可以看出，譯碼器完成一個(gè)碼字的譯碼，共需要3n次移位。這里介紹的是捕錯(cuò)譯碼器的基本原理，若要實(shí)現(xiàn)連續(xù)譯碼，還要進(jìn)行一些改進(jìn)，一方面力圖使譯碼器電路簡(jiǎn)單化，另一方面提高譯碼速度，減少移位次數(shù)。譯碼過(guò)程如下：54[梅吉特(Meggit)譯碼器

]D0D1D2r07級(jí)移位寄存器r6門R(x)C(x)[梅吉特(Meggit)譯碼器]D0D1D2r07級(jí)55這個(gè)譯碼器上面是一個(gè)g(x)除法電路，下面是一個(gè)7級(jí)移位寄存器作為緩存器，中間的反相器和一個(gè)與門組成了(101)校驗(yàn)子識(shí)別電路。譯碼過(guò)程如下：開(kāi)始譯碼時(shí)門打開(kāi)，移位寄存器內(nèi)容位全0。收到的碼字多項(xiàng)式位R(x)=r6x6+…+r0由高次到低次分別輸入到7級(jí)緩存器和除法電路，7次移位后，緩存器存入整個(gè)碼字，除法電路[S(x)=E(x)/g(x),E(x)=x6]得到校驗(yàn)子S0=[s2,s1,s0]。這時(shí)門關(guān)上進(jìn)行譯碼。如果S0(x)=x6=x2+1[modg(x)]，這時(shí)[101]識(shí)別電路輸出為1，表明r6為有錯(cuò)。這時(shí)譯碼器繼續(xù)移位，通過(guò)[101]識(shí)別電路可以將r6位的錯(cuò)誤糾正。在糾錯(cuò)的同時(shí)，[101]識(shí)別電路的輸出又反饋到除法電路的輸入端，以消除錯(cuò)誤碼元對(duì)除法電路的下一個(gè)校驗(yàn)子計(jì)算的影響。校驗(yàn)子產(chǎn)生電路開(kāi)始在無(wú)輸入的情況下移位，相當(dāng)于開(kāi)始產(chǎn)生xjS(x)。本電路中，輸入R(x)第7次移位后產(chǎn)生了校驗(yàn)子S0，第8次移位時(shí)對(duì)r6進(jìn)行糾正，同時(shí)將[101]識(shí)別電路的輸出的1輸入到除法電路的輸入端，結(jié)果使除法電路的寄存器狀態(tài)為[000]，消除了e6的影響。下面我們看一下，利用這個(gè)電路能否糾正其它錯(cuò)誤圖樣的接收碼字。如果E(x)=x5,表明e5=1或E=[0100000]，這時(shí)經(jīng)過(guò)前7次移位后得到的校驗(yàn)子多項(xiàng)式為S0(x)=x5[modg(x)]=x2+x+1，這時(shí)除法電路的移位寄存器狀態(tài)為[111]，[101]識(shí)別電路的輸出為0，說(shuō)明r6正確，不必糾正。第8次移位后，r5移位到緩存器的最右端。同時(shí)校驗(yàn)子除法電路的結(jié)果根據(jù)定理可知：（通過(guò)電路分析也可以看出）S1(x)=xS0(x)=xE(x)=x6[modg(x)]=x2+1[modg(x)]產(chǎn)生[101]狀態(tài)；這時(shí)[101]識(shí)別電路輸出1，對(duì)r5進(jìn)行糾正?？梢钥吹剑醚h(huán)碼的循環(huán)特性，可以簡(jiǎn)化譯碼器的復(fù)雜性。從上述譯碼過(guò)程中可以看到，(n,k)循環(huán)碼的譯碼器譯一個(gè)碼字共需要2n次移位，不能實(shí)現(xiàn)連續(xù)譯碼，為了實(shí)現(xiàn)連續(xù)譯碼，可以再加一套除法電路，這個(gè)譯碼器上面是一個(gè)g(x)除法電路，下面是一個(gè)7級(jí)移位寄存568.1差錯(cuò)控制編碼的基本概念8.2線性分組碼8.3循環(huán)碼第8章差錯(cuò)控制編碼返回主目錄8.1差錯(cuò)控制編碼的基本概念第8章差錯(cuò)控制編57概述差錯(cuò)控制編碼：信道編碼在數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼和信道編碼。信源編碼是為了提高數(shù)字信號(hào)的有效性以及為了使模擬信號(hào)數(shù)字化而采取的編碼。信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。數(shù)字信號(hào)在傳輸過(guò)程中，加性噪聲、碼間串?dāng)_等都會(huì)產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射功率，降低接收設(shè)備本身的噪聲，以及合理選擇調(diào)制、解調(diào)方法等。此外，還必須采用信道編碼技術(shù)。概述差錯(cuò)控制編碼：信道編碼588.1.1差錯(cuò)控制方式圖8-1差錯(cuò)控制方式8.1.1差錯(cuò)控制方式圖8-1差錯(cuò)控制方式591.前向糾錯(cuò)方式前向糾錯(cuò)方式記作FEC(ForwordErrorCorrection)。發(fā)端發(fā)送能夠糾正錯(cuò)誤的碼，收端收到信碼后自動(dòng)地糾正傳輸中的錯(cuò)誤。其特點(diǎn)是單向傳輸，實(shí)時(shí)性好，但譯碼設(shè)備較復(fù)雜。

1.前向糾錯(cuò)方式60

2.檢錯(cuò)重發(fā)方式檢錯(cuò)重發(fā)又稱自動(dòng)請(qǐng)求重傳方式，記作ARQ(AutomaticRepeatRequest)。由發(fā)端送出能夠發(fā)現(xiàn)錯(cuò)誤的碼，由收端判決傳輸中無(wú)錯(cuò)誤產(chǎn)生，如果發(fā)現(xiàn)錯(cuò)誤，則通過(guò)反向信道把這一判決結(jié)果反饋給發(fā)端，然后，發(fā)端把收端認(rèn)為錯(cuò)誤的信息再次重發(fā)，從而達(dá)到正確傳輸?shù)哪康?。其特點(diǎn)是需要反饋信道，譯碼設(shè)備簡(jiǎn)單，對(duì)突發(fā)錯(cuò)誤和信道干擾較嚴(yán)重時(shí)有效，但實(shí)時(shí)性差，主要在計(jì)算機(jī)數(shù)據(jù)通信中得到應(yīng)用。2.檢錯(cuò)重發(fā)方式613.混合糾錯(cuò)方式混合糾錯(cuò)方式記作HEC(HybridErrorCorrection)是FEC和ARQ方式的結(jié)合。發(fā)端發(fā)送具有自動(dòng)糾錯(cuò)同時(shí)又具有檢錯(cuò)能力的碼。收端收到碼后，檢查差錯(cuò)情況，如果錯(cuò)誤在碼的糾錯(cuò)能力范圍以內(nèi)，則自動(dòng)糾錯(cuò)，如果超過(guò)了碼的糾錯(cuò)能力，但能檢測(cè)出來(lái)，則經(jīng)過(guò)反饋信道請(qǐng)求發(fā)端重發(fā)。這種方式具有自動(dòng)糾錯(cuò)和檢錯(cuò)重發(fā)的優(yōu)點(diǎn)，可達(dá)到較低的誤碼率，因此，近年來(lái)得到廣泛應(yīng)用。3.混合糾錯(cuò)方式62另外，按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨機(jī)信道、突發(fā)信道和混合信道。恒參高斯白噪聲信道是典型的隨機(jī)信道，其中差錯(cuò)的出現(xiàn)是隨機(jī)的，而且錯(cuò)誤之間是統(tǒng)計(jì)獨(dú)立的。具有脈沖干擾的信道是典型的突發(fā)信道，錯(cuò)誤是成串成群出現(xiàn)的，即在短時(shí)間內(nèi)出現(xiàn)大量錯(cuò)誤。短波信道和對(duì)流層散射信道是混合信道的典型例子，隨機(jī)錯(cuò)誤和成串錯(cuò)誤都占有相當(dāng)比例。對(duì)于不同類型的信道，應(yīng)采用不同的差錯(cuò)控制方式。另外，按照噪聲或干擾的變化規(guī)律，可把信道分為638.1.2糾錯(cuò)碼的分類(1)根據(jù)糾錯(cuò)碼各碼組信息元和監(jiān)督元的函數(shù)關(guān)系，可分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線性方程式，則稱為線性碼，否則為非線性碼。(2)根據(jù)上述關(guān)系涉及的范圍，可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關(guān)；卷積碼中的碼元不僅與本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)。(3)根據(jù)碼的用途，可分為檢錯(cuò)碼和糾錯(cuò)碼。檢錯(cuò)碼以檢錯(cuò)為目的，不一定能糾錯(cuò)；而糾錯(cuò)碼以糾錯(cuò)為目的，一定能檢錯(cuò)。8.1.2糾錯(cuò)碼的分類648.1.3幾種簡(jiǎn)單的檢測(cè)碼(1)奇偶監(jiān)督碼。(2)二維奇偶監(jiān)督碼。(3)重復(fù)碼。(4)恒比碼。(5)ISBN國(guó)際統(tǒng)一圖書編號(hào)。

8.1.3幾種簡(jiǎn)單的檢測(cè)碼651奇偶監(jiān)督碼奇偶監(jiān)督碼是在原信息碼后面附加一個(gè)監(jiān)督元，使得碼組中“1”的個(gè)數(shù)是奇數(shù)或偶數(shù)。奇偶監(jiān)督碼分為奇監(jiān)督（校驗(yàn)）碼和偶監(jiān)督（校驗(yàn)）碼。1奇偶監(jiān)督碼奇偶監(jiān)督碼是在原信息碼后面附66設(shè)碼字A=［an-1,an-2,…,a1,a0］，對(duì)偶監(jiān)督碼有奇監(jiān)督碼情況相似，只是碼組中“1”的數(shù)目為奇數(shù)，即滿足條件而檢錯(cuò)能力與偶監(jiān)督碼相同。奇偶監(jiān)督碼的編碼效率R為設(shè)碼字A=［an-1,an-2,…,a1,a0］，對(duì)偶監(jiān)督碼672二維奇偶監(jiān)督碼2二維奇偶監(jiān)督碼68

碼字中1的數(shù)目與0的數(shù)目保持恒定比例的碼稱為恒比碼。由于恒比碼中，每個(gè)碼組均含有相同數(shù)目的1和0，因此恒比碼又稱等重碼，定1碼。這種碼在檢測(cè)時(shí)，只要計(jì)算接收碼元中1的數(shù)目是否正確，就知道有無(wú)錯(cuò)誤。

目前我國(guó)電傳通信中普遍采用3∶2碼，又稱“5中取3”的恒比碼，即每個(gè)碼組的長(zhǎng)度為5，其中3個(gè)“1”。這時(shí)可能編成的不同碼組數(shù)目等于從5中取3的組合數(shù)10，這10個(gè)許用碼組恰好可表示10個(gè)阿拉伯?dāng)?shù)字，如下表所示。而每個(gè)漢字又是以四位十進(jìn)制數(shù)來(lái)代表的。實(shí)踐證明，采用這種碼后，我國(guó)漢字電報(bào)的差錯(cuò)率大為降低。3重復(fù)碼4恒比碼（定比碼、等重碼、范德倫碼）

碼字中1的數(shù)目與0的數(shù)目保持恒定比例69七三定比碼（七單位碼）用于國(guó)際電報(bào)系統(tǒng)，碼長(zhǎng)為7，其中1的個(gè)數(shù)為3。這種碼的許用碼字為：3∶2恒比碼五三定比碼（五單位碼）用于國(guó)內(nèi)電報(bào)系統(tǒng)，碼長(zhǎng)為5，其中1的個(gè)數(shù)為3。這種碼的許用碼字為：代表26個(gè)英文字母和一些符號(hào)。代表國(guó)內(nèi)電報(bào)系統(tǒng)中的數(shù)字0~9。而每個(gè)漢字又是以四位十進(jìn)制數(shù)來(lái)代表的。七三定比碼（七單位碼）用于國(guó)際電報(bào)系統(tǒng)，碼長(zhǎng)為7，其中1的個(gè)708.1.4檢錯(cuò)和糾錯(cuò)的基本原理1.分組碼分組碼一般可用(n,k)表示。其中，k是每組二進(jìn)制信息碼元的數(shù)目，n是編碼碼組的碼元總位數(shù)，又稱為碼組長(zhǎng)度，簡(jiǎn)稱碼長(zhǎng)。n-k=r為每個(gè)碼組中的監(jiān)督碼元數(shù)目。簡(jiǎn)單地說(shuō)，分組碼是對(duì)每段k位長(zhǎng)的信息組以一定的規(guī)則增加r個(gè)監(jiān)督元，組成長(zhǎng)為n的碼字。在二進(jìn)制情況下，共有2k個(gè)不同的信息組，相應(yīng)地可得到2k個(gè)不同的碼字，稱為許用碼組。其余2n-2k個(gè)碼字未被選用，稱為禁用碼組。krn8.1.4檢錯(cuò)和糾錯(cuò)的基本原理1.分71在分組碼中，非零碼元的數(shù)目稱為碼字的漢明(Hamming)重量，簡(jiǎn)稱碼重。例如，碼字10110，碼重w=3。兩個(gè)等長(zhǎng)碼組之間相應(yīng)位取值不同的數(shù)目稱為這兩個(gè)碼組的漢明(Hamming)距離，簡(jiǎn)稱碼距。例如11000與10011之間的距離d=3。碼組集中任意兩個(gè)碼字之間距離的最小值稱為碼的最小距離，用dmin表示。最小碼距是碼的一個(gè)重要參數(shù)，它是衡量碼檢錯(cuò)、糾錯(cuò)能力的依據(jù)。在分組碼中，非零碼元的數(shù)目稱為碼字的漢明(H72如果線性分組碼(n,k)碼位信息位沒(méi)有變化，與信息碼元排列相同，并且與監(jiān)督位分開(kāi)，稱為系統(tǒng)碼，否則稱為非系統(tǒng)碼。信息元監(jiān)督元如果線性分組碼(n,k)碼位信息位沒(méi)有變化，與信息碼元排列相732.檢錯(cuò)和糾錯(cuò)能力若分組碼碼字中的監(jiān)督元在信息元之后，而且是信息元的簡(jiǎn)單重復(fù)，則稱該分組碼為重復(fù)碼。它是一種簡(jiǎn)單實(shí)用的檢錯(cuò)碼，并有一定的糾錯(cuò)能力。例如(2,1)重復(fù)碼，兩個(gè)許用碼組是00與11，d0=2，收端譯碼，出現(xiàn)01、10禁用碼組時(shí)，可以發(fā)現(xiàn)傳輸中的一位錯(cuò)誤。如果是(3,1)重復(fù)碼，兩個(gè)許用碼組是000與111,d0=3;當(dāng)收端出現(xiàn)兩個(gè)或三個(gè)1時(shí)，判為1，否則判為0。此時(shí)，可以糾正單個(gè)錯(cuò)誤，或者該碼可以檢出兩個(gè)錯(cuò)誤。2.檢錯(cuò)和糾錯(cuò)能力若分組碼碼字中的監(jiān)督74碼的最小距離dmin直接關(guān)系著碼的檢錯(cuò)和糾錯(cuò)能力；對(duì)于任一(n,k)分組碼，若要在碼字內(nèi):若檢測(cè)e個(gè)錯(cuò)誤，則要求dmin≥e+1;若糾正t個(gè)錯(cuò)誤，則要求dmin≥2t+1;若糾正t個(gè)錯(cuò)誤，同時(shí)發(fā)現(xiàn)e個(gè)錯(cuò)誤，則要求dmin≥t+e+1;t<e;e+12t+1t+e+1C1C2C’1C2C1C’1eettC1C2etC’1碼的最小距離dmin直接關(guān)系著碼的檢錯(cuò)和糾錯(cuò)753.編碼效率

用差錯(cuò)控制編碼提高通信系統(tǒng)的可靠性，是以降低有效性為代價(jià)換來(lái)的。我們定義編碼效率R來(lái)衡量有效性:R=k/n其中,k是信息元的個(gè)數(shù)，n為碼長(zhǎng)。對(duì)糾錯(cuò)碼的基本要求是:檢錯(cuò)和糾錯(cuò)能力盡量強(qiáng)；編碼效率盡量高；編碼規(guī)律盡量簡(jiǎn)單。實(shí)際中要根據(jù)具體指標(biāo)要求，保證有一定糾、檢錯(cuò)能力和編碼效率，并且易于實(shí)現(xiàn)。3.編碼效率768.2線性分組碼現(xiàn)以(7,4)分組碼為例來(lái)說(shuō)明線性分組碼的特點(diǎn)。設(shè)其碼字為A=［a6

a5

a4

a3

a2

a1

a0］，其中前4位是信息元，后3位是監(jiān)督元，可用下列線性方程組來(lái)描述該分組碼，產(chǎn)生監(jiān)督元。8.2線性分組碼現(xiàn)以(7,4)分組碼為77(7,4)碼的碼字表(7,4)碼的碼字表781監(jiān)督矩陣H和生成矩陣G

線性方程組為：1監(jiān)督矩陣H和生成矩陣G79其中,P為r×k階矩陣，Ir為r×r階單位矩陣?？梢詫懗蒆=［PIr］形式的矩陣稱為典型監(jiān)督矩陣。

HCT=0T，說(shuō)明H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來(lái)作為判斷接收碼字C是否出錯(cuò)的依據(jù)。并簡(jiǎn)記為H稱為監(jiān)督矩陣

其中,P為r×k階矩陣，Ir為r×r階單位矩80若把監(jiān)督方程補(bǔ)充為下列方程若把監(jiān)督方程補(bǔ)充為下列方程81可改寫為矩陣形式即：可改寫為矩陣形式即：82通信原理-CT8差錯(cuò)控制編碼課件83[C]=[m][G]系統(tǒng)碼的生成矩陣也稱為典型生成矩陣[G]=[Ik,Q]，[G]為k×n矩陣，[Q]為k×r矩陣，[Ik]為k×k單位陣。

[H][C]T=[0]系統(tǒng)碼的監(jiān)督矩陣也稱為基本監(jiān)督矩陣[H]=[PIr]，[H]為r×n矩陣，[P]為r×k矩陣，[Ir]為r×r單位陣。[H][G]T=[0]，同時(shí)有：[G][H]T=[0]稱[H]與[G]為正交矩陣，由[PIr][IkQ]T=[0]

[P+QT]=[0]，即[P]=[Q]T[Q]=[P]T

P矩陣與Q矩陣互為轉(zhuǎn)置矩陣。[C]=[m][G]842伴隨式(校正子)S

設(shè)發(fā)送碼組C=［an-1,an-2,…,a1,a0］，在傳輸過(guò)程中可能發(fā)生誤碼。接收碼組R=［bn-1,bn-2,…,b1,b0］，則收發(fā)碼組之差定義為錯(cuò)誤圖樣E，也稱為誤差矢量，即其中E=［en-1,en-2,…,e1,e0］，且當(dāng)bi=ai

當(dāng)bi≠ai

令S=RHT，稱為伴隨式或校正子。2伴隨式(校正子)S設(shè)發(fā)送碼組C=［an-85(7,4)分組碼S與E的對(duì)應(yīng)關(guān)系(7,4)分組碼S與E的對(duì)應(yīng)關(guān)系86[循環(huán)碼定義]：一個(gè)(n,k)線性分組碼C，如果碼組中的一個(gè)碼字的循環(huán)移位也是這個(gè)碼組中的一個(gè)碼字，則稱C為循環(huán)碼。稱為具有循環(huán)自閉性。C(0)={cn-1,cn-2,……c1,c0}∈CC(1)={cn-2,cn-3,……c0,cn-1}∈C[循環(huán)碼的多項(xiàng)式描述]：循環(huán)碼可以用監(jiān)督矩陣和生成矩陣描述，但更多地用域上多項(xiàng)式來(lái)描述，一個(gè)(n,k)循環(huán)的碼字矢量C(0)用一個(gè)n-1次多項(xiàng)式描述，可以表示為：C(x)=cn-1xn-1+cn-2xn-2+……+c1x+c0這個(gè)多項(xiàng)式稱為碼字多項(xiàng)式。碼字矢量的循環(huán)移位可以用x乘上C(x)后的模(xn+1)來(lái)表示。xC(x)=x(cn-1xn-1+cn-2xn-2+……+c1x+c0)=cn-1xn+cn-2xn-1+……+c1x2+c0x=cn-2xn-1+……+c1x2+c0x+cn-1(模xn+1)模xn+1相當(dāng)于xn+1=0；xn=18.3循環(huán)碼[循環(huán)碼定義]：8.3循環(huán)碼87(7,4)系統(tǒng)循環(huán)碼的編碼及碼字多項(xiàng)式如下表：g(x)=x3+x+1可以看出：每個(gè)碼字的循環(huán)移位仍然屬于這個(gè)碼組。并不是說(shuō)碼組是由一個(gè)碼字的循環(huán)移位構(gòu)成的，本例中是由四個(gè)碼字的循環(huán)移位構(gòu)成的。8.3循環(huán)碼(7,4)系統(tǒng)循環(huán)碼的編碼及碼字多項(xiàng)式如下表：g(x)=x3888.3循環(huán)碼(7,3)循環(huán)碼8.3循環(huán)碼(7,3)循環(huán)碼89在一個(gè)(n,k)循環(huán)碼中，有且僅有一個(gè)次數(shù)為n-k=r的碼字多項(xiàng)式，記為：g(x)=xr+gr-1xr-1+……+g1x+1同時(shí)：每個(gè)碼字多項(xiàng)式都是g(x)的倍式；每個(gè)次數(shù)小于等于n-1的g(x)的倍式必為一個(gè)碼字多項(xiàng)式。這時(shí)稱g(x)的(n,k)碼的生成多項(xiàng)式。[生成多項(xiàng)式的性質(zhì)]：是循環(huán)碼C中次數(shù)最低的非零碼字多項(xiàng)式，并且是唯一的，其次數(shù)為r=n-k。令g(x)=xr+gr-1xr-1+……+g1x+g0為一個(gè)(n,k)循環(huán)碼C中最低次數(shù)碼字多項(xiàng)式，則其常數(shù)項(xiàng)必為g0=1。(n,k)循環(huán)碼的生成多項(xiàng)式g(x)是xn+1的因式。在一個(gè)(n,k)循環(huán)碼中，有且僅有一個(gè)次數(shù)為n-k=r的碼字90在代數(shù)理論中，為了便于計(jì)算，常用碼多項(xiàng)式表示碼字。(n,k)循環(huán)碼的碼字，其碼多項(xiàng)式(以降冪順序排列)為[系統(tǒng)循環(huán)碼的編碼方法]：已知循環(huán)碼的生成矩陣,可以按以下步驟產(chǎn)生系統(tǒng)循環(huán)碼。首先定義以下多項(xiàng)式：m(x)=mk-1xk-1+mk-2xk-2+……+m1x+m0為信息碼字多項(xiàng)式；c(x)=cn-1xn-1+cn-2xn-2+……+c1x+c0為循環(huán)碼字多項(xiàng)式；g(x)=xr-1+gr-2xr-2+……+g1x+1為生成多項(xiàng)式；系統(tǒng)碼的編碼分為三步：用xn-k乘上m(x);用g(x)除以xn-km(x)，得到模g(x)的余式r(x)c(x)=xn-km(x)+r(x)為系統(tǒng)循環(huán)碼的碼字多項(xiàng)式。在代數(shù)理論中，為了便于計(jì)算，常用碼多項(xiàng)式表示碼字。(91[例]:(7,4)循環(huán)碼的生成多項(xiàng)式為g(x)=x3+x+1求m=[1010]的循環(huán)碼。解：m(x)=x3+x,xn-k=x3;xn-km(x)=x3(x3+x)=x6+x4r(x)=x+1C(x)=xn-km(x)+r(x)=x6+x4+x+1[C]=[1010011][例]:(7,4)循環(huán)碼的生成多項(xiàng)式為g(x)=x3+x+92[非系統(tǒng)循環(huán)碼的編碼方法]：已知循環(huán)碼的生成矩陣，可以方便的求出非系統(tǒng)循環(huán)碼，C(x)=m(x)g(x)。[例]:m=[1101]g(x)=x3+x+1C(x)=(x3+x2+1)(x3+x+1)=x6+x4+x3+x5+x3+x2+x3+x+1=x6+x5+x4+x3+x2+x+1[C]=[1111111]m=[0101];c(x)=(x2+1)(x3+x+1)=x5+x3+x2+x3+x+1=x5+x2+x+1[C]=[0100111][非系統(tǒng)循環(huán)碼的編碼方法]：93[循環(huán)碼的生成矩陣]：循環(huán)碼可以用域上多項(xiàng)式描述，也可以用生成矩陣描述。已知g(x)為循環(huán)碼C中的一個(gè)碼字多項(xiàng)式，由循環(huán)碼的循環(huán)特性可知，可以證明：在(n,k)循環(huán)碼的碼字多項(xiàng)式中，g(x),xg(x),……xk-1g(x)等k個(gè)碼字多項(xiàng)式必是線性無(wú)關(guān)（相互獨(dú)立的）的。根據(jù)線性空間的特性，可知，它們是一個(gè)k維子空間的基底，即由它們的線性組合可以生成這個(gè)k維子空間的2k個(gè)碼字。再根據(jù)線性分組碼生成矩陣的定義，它的行向量是由k個(gè)線性無(wú)關(guān)的碼字構(gòu)成的，可以得到(n,k)循環(huán)碼的一個(gè)多項(xiàng)式矩陣為：[循環(huán)碼的生成矩陣]：94通信原理-CT8差錯(cuò)控制編碼課件95例如(7,3)循環(huán)碼，n=7,k=3,r=4,其生成多項(xiàng)式及生成矩陣分別為例如(7,3)循環(huán)碼，n=7,k=3,r=4,其生成多96[非系統(tǒng)循環(huán)碼編碼電路]：非系統(tǒng)循環(huán)碼的產(chǎn)生為：C(x)=m(x)g(x),可知其編碼器為如下：D0D1D2m(x)C(x)x1x3x2[非系統(tǒng)循環(huán)碼編碼電路]：D0D1D2m(x)C(x)x1x97監(jiān)督多項(xiàng)式及監(jiān)督矩陣為了便于對(duì)循環(huán)碼編譯碼，通常還定義監(jiān)督多項(xiàng)式，令

其中g(shù)(x)是常數(shù)項(xiàng)為1的r次多項(xiàng)式，是生成多項(xiàng)式；h(x)是常數(shù)項(xiàng)為1的k次多項(xiàng)式，稱為監(jiān)督多項(xiàng)式。同理，可得監(jiān)督矩陣H

監(jiān)督多項(xiàng)式及監(jiān)督矩陣其中g(shù)(x)是常數(shù)項(xiàng)為1的r次多項(xiàng)98是h(x)的逆多項(xiàng)式。例如(9，3)循環(huán)碼，g(x)=x4+x3+x2+1，則其中是h(x)的逆多項(xiàng)式。例如(9，3)循環(huán)碼，g(x)=x4+99通信原理-CT8差錯(cuò)控制編碼課件100編碼方法和電路在編碼時(shí)，首先要根據(jù)給定的(n,k)值選定生成多項(xiàng)式g(x)，即應(yīng)在xn+1的因式中選一r=n-k次多項(xiàng)式作為g(x)。設(shè)編碼前的信息多項(xiàng)式m(x)為循環(huán)碼的碼多項(xiàng)式可表示為編碼方法和電路在編碼時(shí)，首先要根據(jù)給定的(101圖(7,3)循環(huán)碼編碼電路圖(7,3)循環(huán)碼編碼電路102表(7,3)循環(huán)碼的編碼過(guò)程表(7,3)循環(huán)碼的編碼過(guò)程103[系統(tǒng)碼編碼器]：為了構(gòu)成系統(tǒng)碼，可知C(x)=xn-km(x)+r(x)r(x)=xn-km(x)/g(x)[模g(x)]以(7,4)漢明碼為例：g(x)=x3+x+1編碼器電路如圖所示：它由r=n-k級(jí)移位寄存器構(gòu)成。輸入m(x)門1D0D1D2門2或門1xx2x31xx3x3C(x)[系統(tǒng)碼編碼器]：輸入m(x)門1D0D1D2門2或門1xx104[系統(tǒng)循環(huán)碼的生成矩陣與監(jiān)督矩陣]：[系統(tǒng)循環(huán)碼的生成矩陣與監(jiān)督矩陣]：105通信原理-CT8差錯(cuò)控制編碼課件106[大數(shù)邏輯譯碼器]：(門限譯碼器)S0S1S2S3大數(shù)門>2輸出7級(jí)緩存器A2A3A1C(x)C(x)R(x)[大數(shù)邏輯譯碼器]：(門限譯碼器)S0S1S2S3大數(shù)門>2107其工作過(guò)程如下：由(7,3)循環(huán)碼生成多項(xiàng)式g(x)=x4+x3+x2+1的除法電路，計(jì)算R(x)的校驗(yàn)子多項(xiàng)式S(x)。n=7次移位