差錯(cuò)控制編碼

會(huì)計(jì)學(xué)1差錯(cuò)控制編碼2023年1月18日28.1差錯(cuò)控制編碼的基本概念數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼和信道編碼。信源編碼是為了提高數(shù)字通信的有效性，以及為了使模擬信號(hào)數(shù)字化而采取的編碼。信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。數(shù)字信號(hào)在傳輸?shù)倪^程中，加性噪聲、碼間串?dāng)_等都會(huì)產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射功率，降低接收設(shè)備本身的噪聲，以及合理選擇調(diào)制、解調(diào)方法等。此外，還可以采用信道編碼技術(shù)。第1頁/共48頁2023年1月18日3差錯(cuò)控制編碼的基本思想：在發(fā)送端根據(jù)要傳輸?shù)臄?shù)字序列（信息碼元）按一定的規(guī)律加入多余碼元，使原來不相關(guān)的數(shù)字序列變?yōu)橄嚓P(guān)，然后把這些多余碼元和有關(guān)的信息碼元一起傳送，接收端根據(jù)信息碼元與多余碼元之間的相關(guān)規(guī)則進(jìn)行檢驗(yàn)，從而發(fā)現(xiàn)錯(cuò)誤。這時(shí)，或者通過反饋信道要求對(duì)方重發(fā)有錯(cuò)的信息，以進(jìn)行糾錯(cuò)；或者由接收端的譯碼器自動(dòng)把錯(cuò)誤糾正。這些多余碼元稱為校驗(yàn)元或監(jiān)督元。它的加入不改變信息本身，也就是說，它不傳送新的信息，它的作用只是使信道譯碼器能夠檢測(cè)和糾正差錯(cuò)，從而控制系統(tǒng)差錯(cuò)概率，提高可靠性但這是以系統(tǒng)的有效性為代價(jià)的。第2頁/共48頁2023年1月18日48.1.1差錯(cuò)控制方式第3頁/共48頁2023年1月18日5前向糾錯(cuò)方式前向糾錯(cuò)方式記作FEC（ForwordErrorCorrection）發(fā)端編碼器將數(shù)字信息按一定規(guī)則附加多余碼元，組成有糾錯(cuò)能力的碼，發(fā)端發(fā)送能夠糾正錯(cuò)誤的碼；收端譯碼器按預(yù)先規(guī)定的規(guī)則譯碼；若發(fā)現(xiàn)錯(cuò)誤，確定其出錯(cuò)位置并進(jìn)行糾正。優(yōu)點(diǎn)：?jiǎn)蜗騻鬏?，只有正向信道；適合于只能提供單向信道的場(chǎng)合；一點(diǎn)發(fā)送多點(diǎn)接收的同播方式；譯碼延遲固定，適用于實(shí)時(shí)傳輸系統(tǒng)。缺點(diǎn)：編譯碼設(shè)備復(fù)雜，為了糾正較多的錯(cuò)誤，需要附加的多余碼元較多，因而傳輸效率較低。第4頁/共48頁2023年1月18日6檢錯(cuò)重發(fā)方式又稱自動(dòng)請(qǐng)求重傳方式，記作ARQ（AutomaticRepeatRequest）。發(fā)端編碼器將數(shù)字信息按一定規(guī)則附加多余碼元，使之具有一定的檢錯(cuò)能力，收端譯碼器按一定規(guī)則對(duì)數(shù)據(jù)碼元組進(jìn)行錯(cuò)誤判決，并把判決結(jié)果形成應(yīng)答信號(hào)，通過反饋信道回送到發(fā)端，發(fā)端根據(jù)收到的應(yīng)答信號(hào)，把收端認(rèn)為有錯(cuò)的那組數(shù)據(jù)碼元再次重傳，直到碼元組無錯(cuò)為止。優(yōu)點(diǎn)：只需要少量的多余碼元就能獲得極低的輸出誤碼率，并且其成本和復(fù)雜性均比前向糾錯(cuò)低缺點(diǎn)。缺點(diǎn)：必須提供反向信道；不能進(jìn)行同播（一點(diǎn)發(fā)多點(diǎn)收），收發(fā)端應(yīng)有緩沖存儲(chǔ)器和控制器；此外當(dāng)信道干擾較大時(shí)，整個(gè)系統(tǒng)可能處在重傳循環(huán)中，因而通信效率降低，信息傳輸連貫性差，不適于實(shí)時(shí)傳輸系統(tǒng)，主要在計(jì)算機(jī)通信中應(yīng)用。常用的檢錯(cuò)重發(fā)系統(tǒng)有三種，即停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā)。第5頁/共48頁第6頁/共48頁2023年1月18日8混合糾錯(cuò)方式混合糾錯(cuò)方式記作HEC（HybridErrorCorrection）發(fā)端發(fā)送具有自動(dòng)糾錯(cuò)同時(shí)又具有檢錯(cuò)能力的碼。收端收到碼后，檢查差錯(cuò)情況，如果錯(cuò)誤在碼的糾錯(cuò)能力范圍以內(nèi)，則自動(dòng)糾錯(cuò)，如果超過了碼的糾錯(cuò)能力但能檢測(cè)出來，則經(jīng)過反饋信道請(qǐng)求發(fā)端重發(fā)。這種方式具有自動(dòng)糾錯(cuò)和檢錯(cuò)重發(fā)的優(yōu)點(diǎn)，可達(dá)到較低的誤碼率，因此，近年來得到廣泛應(yīng)用。在實(shí)際通信系統(tǒng)中，選擇那種差錯(cuò)控制方式，要視具體情況而定，可以根據(jù)信源的性質(zhì)，信息傳輸?shù)奶攸c(diǎn)信道干擾的種類和對(duì)誤碼率的要求而適當(dāng)選擇差錯(cuò)控制方式。第7頁/共48頁2023年1月18日98.1.2差錯(cuò)控制編碼的分類根據(jù)信息元和監(jiān)督元的函數(shù)關(guān)系，可分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線性方程式，則稱為線性碼，否則為非線性碼。

根據(jù)上述關(guān)系涉及的范圍，可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關(guān)；卷積碼中的碼元不僅與本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)。根據(jù)碼的用途，可分為檢錯(cuò)碼和糾錯(cuò)碼。檢錯(cuò)碼以檢錯(cuò)為目的，不一定能糾錯(cuò)；而糾錯(cuò)碼以糾錯(cuò)為目的，一定能檢錯(cuò)。第8頁/共48頁2023年1月18日108.1.3幾種簡(jiǎn)單的檢錯(cuò)碼(1)奇偶監(jiān)督碼設(shè)碼字A=［an-1,an-2,…,a1,a0］，對(duì)偶監(jiān)督碼有：an-1⊕

an-2⊕…⊕

a1⊕

a0=0奇監(jiān)督碼情況相似，只是碼組中“1”的數(shù)目為奇數(shù)，即滿足條件：an-1⊕

an-2⊕…⊕

a1⊕

a0=1而檢錯(cuò)能力與偶監(jiān)督碼相同。第9頁/共48頁2023年1月18日11奇偶監(jiān)督碼編碼方法：把信息碼元分組，在每組信息碼元的后面附加一位監(jiān)督碼元，使得碼組中1的數(shù)目為奇數(shù)或偶數(shù)即可編碼規(guī)則：碼組長(zhǎng)度n；信息位n-1特點(diǎn)：是一種能發(fā)現(xiàn)奇數(shù)個(gè)差錯(cuò)的分組碼；n較大，即編碼碼組較長(zhǎng)時(shí)，編碼效率接近于1;（n-1）/n

——

信息碼元比碼組碼元適用于檢測(cè)隨機(jī)的零星錯(cuò)碼——加性白噪聲造成的第10頁/共48頁2023年1月18日128.1.3幾種簡(jiǎn)單的檢錯(cuò)碼(2)二維奇偶監(jiān)督碼(6,11)行列監(jiān)督碼第11頁/共48頁2023年1月18日13二維奇偶監(jiān)督碼編碼方法：把碼元排成方陣，按行列進(jìn)行奇偶校驗(yàn)

——分別附加一位監(jiān)督碼元特點(diǎn)：不僅可檢測(cè)每行（每列）中奇數(shù)個(gè)錯(cuò)誤，而且可通過水平監(jiān)督和垂直監(jiān)督來確定錯(cuò)碼的位置糾正僅一行（一列）出現(xiàn)的奇數(shù)個(gè)錯(cuò)誤通過水平監(jiān)督和垂直監(jiān)督的關(guān)系可以發(fā)現(xiàn)單行中出現(xiàn)的偶數(shù)個(gè)錯(cuò)誤；但不能發(fā)現(xiàn)構(gòu)成矩形的4個(gè)錯(cuò)誤碼元適用于突發(fā)差錯(cuò)——由突發(fā)干擾（突發(fā)脈沖，如：閃電，電火花等）在短時(shí)間內(nèi)錯(cuò)碼成串出現(xiàn)，在某一行中出現(xiàn)多個(gè)錯(cuò)碼第12頁/共48頁2023年1月18日148.1.3幾種簡(jiǎn)單的檢錯(cuò)碼(3)重復(fù)碼在每位信息碼元之后，用簡(jiǎn)單重復(fù)多次的方法編碼。例：重復(fù)兩次時(shí)，用111傳輸1碼，用000傳輸0碼

編碼方法：每位信息碼元簡(jiǎn)單重復(fù)多次；收端譯碼采用多數(shù)表決法；例：重復(fù)2次特點(diǎn)：糾正1個(gè)錯(cuò)，檢出2個(gè)錯(cuò)第13頁/共48頁2023年1月18日158.1.3幾種簡(jiǎn)單的檢錯(cuò)碼(4)恒比碼碼字中1的數(shù)目與0的數(shù)目保持恒定比例的碼稱為恒比碼。這種碼在檢測(cè)時(shí)，只要計(jì)算接收碼元中1的數(shù)目是否正確，就知道有無錯(cuò)誤。

第14頁/共48頁2023年1月18日16恒比碼例：5中取3恒比碼——用于電報(bào)電碼每個(gè)碼組長(zhǎng)度為5，共有25=32種不同的碼組，其中有3個(gè)1的碼組為可用碼組，共有10種——表示10個(gè)阿拉伯?dāng)?shù)字，用它拼成漢字（每4阿拉伯?dāng)?shù)字組成1個(gè)漢字電碼）；其余的22個(gè)為禁用碼組。特點(diǎn)：簡(jiǎn)單；除了1錯(cuò)為0與0錯(cuò)為1成對(duì)出現(xiàn)（對(duì)換性）差錯(cuò)不能檢測(cè)外，其它任何奇數(shù)個(gè)或偶數(shù)個(gè)錯(cuò)碼都可以被檢測(cè)出來。只適用于傳輸種類較少且有固定代碼的字符，而不適用于表示由信源來的二進(jìn)制隨機(jī)，數(shù)字序列。第15頁/共48頁2023年1月18日178.1.3幾種簡(jiǎn)單的檢錯(cuò)碼(4)ISBN國(guó)際統(tǒng)一圖書編號(hào)例ISBN0－471－02977－7第16頁/共48頁2023年1月18日188.1.4檢錯(cuò)和糾錯(cuò)的基本原理如用三位二進(jìn)制編碼來代表八個(gè)字母

000A 100 E 001 B 101 F 010 C 110 G 011 D 111 H不管哪一位發(fā)生錯(cuò)誤，都會(huì)使傳輸字母錯(cuò)誤如用三位字母?jìng)魉膫€(gè)字母000A 011 B 101 C 110 D發(fā)生一位錯(cuò)誤，準(zhǔn)用碼字將變成禁用碼字，接收端就能知道出錯(cuò)，但是不能糾錯(cuò)。如果進(jìn)一步將許用碼組限制為兩種000A111B－檢錯(cuò)和糾錯(cuò)能力是用信息量的冗余度來換取的。第17頁/共48頁2023年1月18日19檢錯(cuò)和糾錯(cuò)的基本原理檢錯(cuò)和糾錯(cuò)能力是用信息量的冗余度換取的——與碼組之間的差別有關(guān)；不同的編碼方法和形式，檢錯(cuò)和糾錯(cuò)能力不同。例：n=3，共有8種組合，都用于傳輸消息，在傳輸過程中若發(fā)生一個(gè)誤碼，則一種碼組就會(huì)錯(cuò)誤地變成另一種碼組，但接收端卻不能發(fā)現(xiàn)錯(cuò)誤，因?yàn)槿魏我粋€(gè)碼組都是許用碼組。第18頁/共48頁

在差錯(cuò)控制編碼中，定義碼組中非零碼元的數(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ù)。第19頁/共48頁2023年1月18日21最小碼距與檢錯(cuò)糾錯(cuò)能力的關(guān)系

碼組內(nèi)的距離反映了碼組之間的差別，最小距離越大，說明兩個(gè)碼組間的最小差別越大，或者說其中一個(gè)碼組錯(cuò)為另一個(gè)碼組的可能性就越小，那么其檢錯(cuò)和糾錯(cuò)能力也就越強(qiáng)，因此可以說最小碼距是衡量一種糾錯(cuò)編碼的檢錯(cuò)，糾錯(cuò)能力大小的標(biāo)準(zhǔn)。第20頁/共48頁

碼的最小距離直接關(guān)系著碼的檢錯(cuò)和糾錯(cuò)能力；任一(n,k)分組碼，若要在碼字內(nèi):(1)檢測(cè)e個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離dmin≥e+1;(2)糾正t個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離dmin≥2t+1;(3)糾正t個(gè)同時(shí)檢測(cè)e(≥t)個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離dmin≥t+e+1。t1eAB第21頁/共48頁2023年1月18日23用差錯(cuò)控制編碼提高通信系統(tǒng)的可靠性，是以降低有效性為代價(jià)換來的。我們定義編碼效率R來衡量有效性:Rc=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)。編碼效率第22頁/共48頁2023年1月18日248.2線性分組碼線性分組碼的構(gòu)成將信息序列劃分為等長(zhǎng)(k位)的序列段共有2k個(gè)不同的序列段，在每一信息段之后，附加m位監(jiān)督元，構(gòu)成長(zhǎng)度n=k+m的分組碼(n，k)監(jiān)督元與信息碼元為線性關(guān)系第23頁/共48頁2023年1月18日25例信息元長(zhǎng)度k=3共有2k=8個(gè)不同的信息組每組信息組加4個(gè)監(jiān)督元，構(gòu)成一個(gè)長(zhǎng)度為7的(7，3)線性分組碼。設(shè)：每組信息元為C1C2C3監(jiān)督元為C4C5C6C7根據(jù)下列線性方程組求監(jiān)督元C4=C1+C3C5=C1+C2+C3C6=C1+C2C7=C2+C3第24頁/共48頁2023年1月18日26例

(7，3)碼有8個(gè)信息組，信息組按上方程組求得每個(gè)信息組的4個(gè)監(jiān)督元，得到(7，3)碼的所有8個(gè)碼字信息組碼元00000000000010011101010010011101101110101001001110101101001111011010011111110100重要特性，線性碼有封閉性

第25頁/共48頁2023年1月18日278.2線性分組碼設(shè)分組碼由n位碼組構(gòu)成，記為c1，c2，…，cn，信息碼組由k位碼組成，記為d1，d2，…，dk。則該分組碼記為（n，k）碼。碼組和信息碼組可用行矩陣C和D表示若為線性分組碼，C中的n個(gè)元素都是由D中的k個(gè)元素經(jīng)線性組合形成的?？捎靡宦?lián)立方程表示為第26頁/共48頁將碼組C寫成矩陣形式矩陣G稱為生成矩陣，它是一個(gè)k×n的矩陣第27頁/共48頁2023年1月18日29生成矩陣G第28頁/共48頁2023年1月18日30生成矩陣GIk

單位矩陣，k行k列(kxk階)P矩陣，k行m列(kxm階)編碼前k位，編碼后有n位，2n>2k；選擇P矩陣，可得到有較強(qiáng)檢錯(cuò)糾錯(cuò)能力，實(shí)現(xiàn)方法盡可能簡(jiǎn)單，編碼效率又高的線性分組碼由于線性碼具有封閉性，故任何二個(gè)碼組之間的距離必須與某一個(gè)碼組中“1”的個(gè)數(shù)相等，而碼組中非零碼元的數(shù)目“1”的個(gè)數(shù)為碼組的重量（碼重）所以線性碼任意二個(gè)碼字之間的距離必須等于碼中某一個(gè)碼字的重量——線性碼最小碼距正好等于非零碼的最小碼重估算線性碼的差錯(cuò)控制能力：求最小碼距——最小碼重第29頁/共48頁2023年1月18日31例已知（6，3）碼的生成距陣，求：編碼碼組第30頁/共48頁2023年1月18日32監(jiān)督矩陣H校驗(yàn)矩陣或監(jiān)督矩陣H：mxn階PT:m行k列

k+m=n列第31頁/共48頁2023年1月18日33伴隨式（校正子）S

設(shè)發(fā)送碼組C=［cn-1,cn-2,…,c1,c0］，在傳輸過程中可能發(fā)生誤碼。接收碼組R=［rn-1,rn-2,…,r1,r0］，則收發(fā)碼組之差定義為錯(cuò)誤圖樣E，也稱為誤差矢量，即E=R–C=［en-1,en-2,…,e1,e0］，且

當(dāng)ri=ci

當(dāng)ri≠ci

令S=RHT，稱為伴隨式或校正子

S=RHT=CHT⊕

EHT=EHT

S只與錯(cuò)誤圖形有關(guān)，與發(fā)送的碼組C無關(guān)

HT

：nxm階；E：1xn階；S：1xm階；S=[s1s2

……sm]

解得誤差矢量E，求得糾錯(cuò)后的碼組C=R⊕E第32頁/共48頁2023年1月18日34檢錯(cuò)與糾錯(cuò)檢錯(cuò)：當(dāng)碼組出現(xiàn)錯(cuò)誤S為非零矢量糾錯(cuò)：

S=RHT=CHT⊕EHT=EHT

S與E之間有著確定的線性關(guān)系——由H矩陣確定（也就是與G（P）矩陣有關(guān)）S=[s1s2

……sm]共有2m種不同的形式，除全0外，可代表2m-1種有錯(cuò)誤的圖形信息碼組有2k個(gè)錯(cuò)誤圖形，有多種不同的形式可能有2k種解答；為了選擇正確的結(jié)果，要使用最大似然比準(zhǔn)則，選擇與R最相似的C（與R距離最小的碼組——E是1碼最小的矢量）。第33頁/共48頁2023年1月18日35例：（6，3）碼第34頁/共48頁2023年1月18日36S與E對(duì)照表ES

000000000100000101010000011001000110000100100000010010000001001100010111

（6，3）碼具有糾1位錯(cuò)的能力發(fā)生1個(gè)錯(cuò)誤的情況：

S是HT的第i行，說明R中第i位產(chǎn)生了錯(cuò)誤，可以把它糾正發(fā)生2個(gè)錯(cuò)誤的情況：除S=111對(duì)應(yīng)第1，5位有錯(cuò)其它的雙錯(cuò)不能得到糾正

例：

接收碼組R[111011]

第35頁/共48頁2023年1月18日37查表法譯碼器的原理S=RHT=CHT⊕EHT=EHT算出伴隨式S與最小碼重的差錯(cuò)矢量E的對(duì)照表，提供譯碼使用第36頁/共48頁2023年1月18日38漢明碼按上述方法構(gòu)造的能糾正單個(gè)錯(cuò)誤的線性分組碼稱為漢明碼。對(duì)于線性分組碼，為了指示所有單錯(cuò)位置和無錯(cuò)的情況，必須滿足不等式漢明碼具有以下特點(diǎn)：漢明碼的編碼效率第37頁/共48頁2023年1月18日39漢明界如果碼組有糾t個(gè)差錯(cuò)的能力，則應(yīng)能指出無錯(cuò)、單錯(cuò)到t個(gè)差錯(cuò)所有可能的情況，校驗(yàn)位數(shù)m應(yīng)滿足不等式：－漢明界，是糾正t個(gè)差錯(cuò)的一個(gè)必要條件第38頁/共48頁2023年1月18日408.3循環(huán)碼特點(diǎn)線性分組碼循環(huán)性——任一許用碼字經(jīng)過循環(huán)移位后，得到的碼組仍為一個(gè)許用碼組如是循環(huán)碼的一許用碼組則也是一許用碼組移位i次得到也是許用碼組第39頁/共48頁2023年1月18日418.3.1循環(huán)碼的特點(diǎn)及表達(dá)碼多項(xiàng)式表示以此類推，碼組C移位i次，相應(yīng)的碼多項(xiàng)式c(i)(x)是xi·c(x)除以（xn+1)后的余式。在模（xn+1)意義下，若c(x)是碼多項(xiàng)式，則xic(x)都是碼多項(xiàng)式。第40頁/共48頁2023年1月18日42循環(huán)碼的編碼過程一個(gè)k位的信息碼組可用信息多項(xiàng)式表示假設(shè)碼組多項(xiàng)式可表示為如果(χn+1)是g(χ)的倍式C（1）(χ)=χd(χ)g(χ)+aC1g(χ)=[χd(χ)+aC1]g(χ)=d1(χ)g(χ)d1(χ)對(duì)應(yīng)某個(gè)信息碼組第41頁/共48頁2023年1月18日43生成多項(xiàng)式g(χ)

(χn+1)是g(χ)的倍式，且g(χ)為n-k次多項(xiàng)式，所以對(duì)(χn+1)進(jìn)行因式分解，便可得到相應(yīng)的g(χ)。對(duì)(χn+1)進(jìn)行因式分解可由計(jì)算機(jī)完成，有表格給出。由信息多項(xiàng)式求解碼多項(xiàng)式

C(χ)=d(χ)g(χ)

n-1次k-1次n-k次第42頁/共48頁2023年1月18日44例(7，4)——n=7

k=4

m=n-k=3g(χ)應(yīng)為(χ7+1

)的3次因式χ７

+1=(χ+1)(χ３+

χ+1)(χ３+

χ２+1)g1(χ)=(χ３+

χ+1)g2(χ)=(χ３+

χ２+1)D=[1010]——d(χ)=(χ３+

χ)C1(χ)=d(χ)g1(χ)=(χ３+

χ)(χ３+

χ+1)

=χ６+

χ３+

χ２+

χ

——

C1=[1001110]C2(χ)=d(χ)g2(χ)=(χ３+

χ)(χ３+

χ２+1)

=χ６+

χ５+

χ４+

χ

——

C２

=[1110010]注：

1.不同的生成多項(xiàng)式得到不同的碼組

2.由此編碼法得到的不是系統(tǒng)碼（前4位不是D=[1010]）