數(shù)據(jù)通信編碼糾錯(cuò)

1、糾錯(cuò)編碼方式的簡介2.1奇偶監(jiān)督碼奇偶校驗(yàn)碼也稱奇偶監(jiān)督碼，它是一種最簡單的線性分組檢錯(cuò)編碼方式。其方法是首先把信源編碼后的信息數(shù)據(jù)流分成等長碼組，在每一信息碼組之后加 入一位（1比特）監(jiān)督碼元作為 奇偶檢驗(yàn)位，使得總碼長n（包括信息位k和監(jiān)督 位1）中的碼重為偶數(shù)（稱為偶校驗(yàn)碼）或?yàn)槠?數(shù)（稱為奇校驗(yàn)碼）。如果在傳輸過 程中任何一個(gè)碼組發(fā)生一位（或奇數(shù)位）錯(cuò)誤，則收到的 碼組必然不再符合奇偶 校驗(yàn)的規(guī)律，因此可以發(fā)現(xiàn)誤碼。奇校驗(yàn)和偶校驗(yàn)兩者具有完全相同的工作原理和檢錯(cuò)能力，原則上采用任一種都是可以的。由于每兩個(gè)1的模2相加為0，故利用模2加法可以判斷一個(gè)碼組中碼重是 奇數(shù)或是偶數(shù)。模2加法等

2、同于“異或”運(yùn)算?，F(xiàn)以偶監(jiān)督為例。對于偶校驗(yàn)，應(yīng)滿足口”1國口 1巾=°故監(jiān)督位碼元a 0可由下式求出：6二珀 巾 線國國_ 2）不難理解，這種奇偶校驗(yàn)編碼只能檢出單個(gè)或奇數(shù)個(gè)誤碼，而無法檢知偶數(shù) 個(gè)誤碼，對于連續(xù)多位的突發(fā)性誤碼也不能檢知，故檢錯(cuò)能力有限，另外，該編 碼后碼組的最小碼距為八=2，故沒有糾錯(cuò)碼能力。奇偶監(jiān)督碼常用于反饋糾錯(cuò)法。2.2行列監(jiān)督碼行列監(jiān)督碼是二維的奇偶監(jiān)督碼，又稱為矩陣碼，這種碼可以克服奇偶監(jiān)督碼不能發(fā)現(xiàn)偶數(shù) 個(gè)差錯(cuò)的缺點(diǎn)，并且是一種用以糾正突發(fā)差錯(cuò)的簡單糾正編碼。其基本原理與簡單的奇偶監(jiān)督碼相似，不同的是每個(gè)碼元要受到縱和橫的兩 次監(jiān)督。具體編 碼方法如

3、下：將若干個(gè)所要傳送的碼組編成一個(gè)矩陣，矩陣中 每一行為一碼組，每行的最后 加上一個(gè)監(jiān)督碼元，進(jìn)行奇偶監(jiān)督，矩陣中的每一列則由不同碼組相同位置的碼元組成，在每列最后也加上一個(gè)監(jiān)督碼元，進(jìn)行奇偶監(jiān)督。如果用X表示信息位，用 表示監(jiān)督位，由矩陣 碼 的結(jié)構(gòu)可如圖 6-5所示，這樣，它的一致監(jiān)督關(guān)系按行及列組成 。每一行每一列都是一個(gè) 奇 偶 監(jiān)督碼，當(dāng)某一行（或某一列）出現(xiàn)偶數(shù)個(gè)差錯(cuò)時(shí)，該行（或該列）雖不能發(fā)現(xiàn)， 但只要差錯(cuò)所 在的列（或行），沒有同時(shí)出現(xiàn)偶數(shù)個(gè)差錯(cuò)，則這種差錯(cuò)仍然可以 被發(fā)現(xiàn)。矩陣碼不能發(fā)現(xiàn) 的差錯(cuò)只有這樣一類：差錯(cuò)數(shù)正好為 4倍數(shù)，而且差 錯(cuò)位置正好構(gòu)成矩形的四個(gè)角，如圖 6-

4、 5中所示有：的差錯(cuò)情況。因此，矩 陣碼發(fā)現(xiàn)錯(cuò)碼的能力是十分強(qiáng)的，它的 編碼效率當(dāng)然比奇偶監(jiān)督碼要低。2.3恒比碼恒比碼又稱為定比碼。在恒比碼中，每個(gè)碼組“ 1”和0”都保持固定的比例，故 得此名。這種碼在檢測時(shí)，只要計(jì)算接收到的碼組中“ 1”的數(shù)目是否對就知道有 無錯(cuò)氓在我國用電傳機(jī)傳輸漢字時(shí)，只使用阿拉伯?dāng)?shù)字代表漢字。這時(shí)采用的所謂“保護(hù)電碼”就是3 2”或稱5“中取3”的恒比碼,即每個(gè)碼組的長度為5， 其中1 ”的個(gè)數(shù)總是3,而0”的個(gè)數(shù)總是2。如表6 2所示。表6 2數(shù)字字普通的五單恒比符位碼碼0101111001111011211001101131000004010101101500

5、0010001111010111106101010711100011180110009000111001001101101101本來以5位碼元組成的碼組總共可以有 25=32種，而恒比碼規(guī)定只有確切地含有3個(gè)T, 2個(gè)0”的那些碼組為準(zhǔn)用碼組，而有3個(gè)1 ”，2個(gè)0”的5 cj = -=10位碼組共有多少？這是5中 取3”求組合的算法，組合數(shù)為':,一 般情況下， 從n中取m”(m v n)恒比碼的碼組數(shù)為:由此可以看出，恒比碼實(shí)際上是n個(gè)碼元傳送 匚比特信息，例如上述3 :2(即5中取2(恒比碼，用5位碼只傳10種信息。每個(gè)碼組的信息量為有5-3.3=1.7bit作為代價(jià)付出恒比碼適

6、用于傳輸字母和符號(hào)2.4漢明碼漢明碼屬于線性分組編碼方式，大多數(shù)分組碼屬于線性編碼，其基本原理是,使信息碼元與 監(jiān)督碼元通過線性方程式聯(lián)系起來。線性碼建立在代數(shù)學(xué)群論的 基礎(chǔ)上，各許用碼組的集合 構(gòu)成代數(shù)學(xué)中的群，故又稱為群碼(1) 校驗(yàn)子和監(jiān)督關(guān)系式我們先回顧一下按式(2 2)條件構(gòu)成的偶數(shù)監(jiān)督碼。由于我們使用了一位監(jiān)督碼C0，它就 能和信息碼一起構(gòu)成一個(gè)代數(shù)式，在接收端解碼時(shí)，我們實(shí)際上是在計(jì)算若S=0，就認(rèn)為無錯(cuò)碼。若S=1，就認(rèn)為有錯(cuò)碼。上式就是一致監(jiān)督關(guān)系式S稱為“校驗(yàn)子(。由于校驗(yàn)子S的取值只有這樣兩種，它就只能代表有錯(cuò)和無 錯(cuò)兩種信息，而不能指出錯(cuò) 碼的位置。我們不難推想，如監(jiān)督

7、位增加一位，變成兩位，則能增加一個(gè)類似于式（2 - 3）的 監(jiān)督關(guān)系式。兩個(gè)校驗(yàn)子的可能值有4 種組合00，01，10 ,11。故能表示4種不同的信息，其 中一種表示無錯(cuò)，其 余三種就有可能用來指示一位錯(cuò)碼的 3種不同位置。同理，r個(gè)監(jiān)督關(guān)系式能 指示一位錯(cuò)碼的 r1）個(gè)可能位置。一般說來，若碼長為n,信息碼為k，則監(jiān)督碼數(shù)r=n-k。若希望用r個(gè)監(jiān)督碼構(gòu)造出r個(gè)監(jiān)督 關(guān)系式來指示一位錯(cuò)碼的n種可能位置，則要求：'1 '' ' 1 '下面通過一個(gè)例子來說明如何具體構(gòu)造這些監(jiān)督關(guān)系式。設(shè)分組碼（n、k）中k=4，為了能糾正一位錯(cuò)碼，按式（2 4）可知，要求

8、監(jiān)督碼數(shù) r3，現(xiàn)取r =3，貝U n=k+r=4+3=7，這是一種（7、4）分組碼。我們用勺；氏 表示這7個(gè)碼 元，I®二，表示三個(gè)監(jiān)督關(guān)系式中的校驗(yàn)子，則I： 的值與錯(cuò)碼位置 的對應(yīng)關(guān)系可以規(guī)定如表6 3，（當(dāng)然也可以規(guī)定成另一種對 應(yīng)關(guān)系，這不影響討論一般性 ）。按表6 3的規(guī)定，僅當(dāng)有一個(gè)錯(cuò)碼位置在"時(shí)，校驗(yàn)子S1為1，否則S1為o，這就意味著-'恥四個(gè)碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系:錯(cuò)碼位置錯(cuò)碼位置001101010110100111011000無錯(cuò)碼同理 構(gòu)成偶數(shù)監(jiān)督關(guān)系:以及I: = *構(gòu)成偶數(shù)監(jiān)督關(guān)系:sa6 ©a4 ©cp監(jiān)督碼的確定在發(fā)

9、送端編碼時(shí)，信息碼心的值決定于輸入信號(hào)，是隨機(jī)的。而 監(jiān)督碼則應(yīng)根據(jù)信息碼的取值按監(jiān)督關(guān)系式?jīng)Q定。即監(jiān)督碼的取值應(yīng)使 上三式 中I： 的值為o，表示編成的碼組中無錯(cuò)碼：由上式移項(xiàng)解出監(jiān)督碼：（在模2加法中，移項(xiàng)后沒有負(fù)號(hào)）已知信息碼后，直接按上式可算出監(jiān)督碼，計(jì)算結(jié)果得出16個(gè)碼組列于表6-4信息碼監(jiān)督碼信息碼監(jiān)督碼0000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111(3)解碼過程接收端收到每個(gè)碼組后，按下述順序解碼。先按式

10、 (2-4)(2 6)計(jì)算出 再按表6 3判斷錯(cuò)誤情況。例如，若接收碼組為 0000011，按式(24)(2 6)計(jì)算得：_I _ 二 _ 由于 m- I ,查表 6 3 可知有一錯(cuò)碼為a 3：(4)汙蘋字施彖空沢嗎丁曲蝎沁慾翌n=1-r/n當(dāng)n很大時(shí)，效率是很高的。2.5循環(huán)碼(CRC)(1)循環(huán)碼是一種重要的線性碼，它有三個(gè)主要數(shù)學(xué)特征： 循環(huán)碼具有循環(huán)性，即循環(huán)碼中任一碼組循環(huán)一位(將最右端的碼移至左 端)以后，仍為 該碼中的一個(gè)碼組。 循環(huán)碼組中任兩個(gè)碼組之和(模 2)必定為該碼組集合中的一個(gè)碼組。 循環(huán)碼每個(gè)碼組中，各碼元之間還存在一個(gè)循環(huán)依賴關(guān)系，b代表碼元，則有肪=£田

11、縮1(2) 用多項(xiàng)式碼作為檢驗(yàn)碼的編解碼過程用多項(xiàng)式碼作為檢驗(yàn)碼時(shí)，發(fā)送器和接收器必須具有相同的生成多項(xiàng)式(Generator Polynom ial)G(x)，其最高、最低項(xiàng)系數(shù)必須為 1。CRC編碼過程 是將要發(fā)送的二進(jìn)制序列看作是多項(xiàng) 式的系數(shù)，除以生成多項(xiàng)式，然后把余數(shù) 掛在原多項(xiàng)式之后。CRC譯碼過程是接收方用同一生成多項(xiàng)式除以接收到的 CRC編碼，若余數(shù)為零，則傳輸無錯(cuò)。編碼譯碼方法： 令r為生成多項(xiàng)式G(x)的階，將r個(gè)0”附加在信息(數(shù)據(jù))元的低端，使其長度變?yōu)閗+r位，相應(yīng)于多項(xiàng)式+''"''； - g(x)mod 2，得余數(shù)； 與余

12、數(shù)對應(yīng)位異或，得編碼信息 T(x)。例數(shù)據(jù)信息數(shù)據(jù)信息11M(X)生成式10011G(X),R=4加4個(gè)0”之后110K 5%(X)1110余數(shù)待發(fā)送的編碼110T(X) 接收器收到發(fā)來的編碼信息后，用同一個(gè)生成多項(xiàng)式G(x)除以編碼信息，若余數(shù)為零，則表示接收到正確的編碼信息，否則有錯(cuò)。 把收到的正確編碼信息T(x)去掉尾部r位，即得數(shù)據(jù)信息M(x)(3) 多項(xiàng)式碼檢錯(cuò)能力及生成多項(xiàng)式 G(x)的選擇原則設(shè)接收到的信息不是發(fā)送的編碼信息 T(x)，而是T(x)+E(x)。例+匯二癌三恚壬11 T(x)-E(x)=T(x)+E(x)其中，11為T(x)00 為 E(x)若接收到的有差錯(cuò)的編碼信

13、息為T(x)+E(x)，用G(x)除以T(x)+E(x)，則得余數(shù)為E(x)/G(x)的余數(shù)，因?yàn)門(x)/G(x)余數(shù)為零，所以T(x)+E(x) /G(x)E(x)/G(x)這時(shí)應(yīng)該有余數(shù)，若無余數(shù)則檢不出錯(cuò)。有r位校驗(yàn)位的多項(xiàng)式碼將能檢測所有w r位的突發(fā)錯(cuò)，故只要k-1 v r，就能 檢測出所有突發(fā) 錯(cuò)，這是一個(gè)很有用的結(jié)論。生成多項(xiàng)式G(x)的國際標(biāo)準(zhǔn)有：CRC 12CRC 16CRC CCITTCRC 16和CRC CCITT兩種生成多項(xiàng)式生成的 CRC碼可以捕捉一位錯(cuò)、二位錯(cuò)、具有奇數(shù)個(gè)錯(cuò) 的全部錯(cuò)誤，可以捕捉突發(fā)錯(cuò)長度小于16的全部錯(cuò)誤、 長度為17的突發(fā)錯(cuò)的9999 8%、長

14、度為18以上的突發(fā)錯(cuò)的99997%。CRC 16和CRC CCITT可以用硬件實(shí)現(xiàn)。CRC編碼硬件電路的實(shí)現(xiàn)設(shè)數(shù)據(jù)1010多項(xiàng)式匚-生成多項(xiàng)式系數(shù)1011多項(xiàng)式 屮川系數(shù) 1010000多項(xiàng)式 f 1 1余式系數(shù)011多項(xiàng)式k(X)=X+1CRC編碼信息組從高位端輸入的CRC編碼電路，如圖6-6所示，其工作原理是：首先 門1關(guān)閉，門2開通，依次輸入的信息元1010 一面經(jīng)或門H直接輸出，同時(shí) 送往除法電路進(jìn)行除法運(yùn)算。4次移位后除法電路完成了運(yùn)算，得余式系數(shù)為 011 ”，即為監(jiān)督元。第5個(gè)移位脈沖開始門1開通，門2關(guān)閉，斷開了反饋， 移位3次把移位寄存器中的3位余項(xiàng)作為監(jiān)督元附在信息元后 面

15、，發(fā)出的碼字 就是1010011，最后門1關(guān)閉，門2開通，對下一信息組再行編碼。有關(guān)工作 過 程見表6 5表6 5圖6 6所示電路的工作過程移動(dòng)脈沖輸入輸出注（初始狀態(tài)）000門1關(guān)閉門2打開110112011031100門12.6 RS碼(Reed Solo mon 里德索羅門碼)RS碼是一種重要的線性分組編碼方式。它對突發(fā)性錯(cuò)誤有較強(qiáng)的糾錯(cuò)能力,被DVB標(biāo)準(zhǔn)采用(1)在RS編碼過程中，各符號(hào)不是直接出現(xiàn)，而是每個(gè)符號(hào)要乘以某個(gè)基本 元素的幕次方后 再模2力卩，如圖6 7 ：| |(2)在循環(huán)碼中欲檢查是否有錯(cuò)是用碼字除一個(gè)多項(xiàng)式，而在RS碼中，欲檢 出一系列誤碼則需要用碼字除一定數(shù)量的一次

16、多項(xiàng)式。如果要糾正七個(gè)錯(cuò)誤，那 么碼字必須 被2t個(gè)不同的一次多項(xiàng)式整除，例如被 x+a n的一次多項(xiàng)式整 除，這里的n取值直到2t的所 有整數(shù)值，a是基本元素，例如a為010，輸入 5個(gè)符號(hào)，每個(gè)符號(hào)3比特，與相應(yīng)的元素相乘 后直接模2加輸出，因?yàn)橛袃?種系數(shù)，所以得到二個(gè)校檢子，兩個(gè)校驗(yàn)式為：©Z? ® C尸Q§ = a1E®a1 PaQ = 0下面舉一個(gè)簡單例子說明糾錯(cuò)過程在無差錯(cuò)時(shí)，S 0=0，S 1=0，有如下關(guān)系:碼字A101B100式中CDEPQ'=010100111100100000當(dāng)接收到的符號(hào)有錯(cuò)時(shí)通過計(jì)算也可以得到與符號(hào)有關(guān)

17、的錯(cuò)誤圖形，這時(shí)有錯(cuò)的 碼加撇，一是錯(cuò)誤圖形，真正的D=D + =101+00仁100。但錯(cuò)誤的位置將 由s 1決定，這要利用，T<的關(guān)系。A101B100C010D101E111P100Q1000001校驗(yàn)子的增加導(dǎo)致糾錯(cuò)能力的加強(qiáng)，通過 門：的運(yùn)算可以確定差錯(cuò) 的位子， 幷&和和:盡管門；都是同一個(gè)錯(cuò)誤的不同圖形，但因：匸八次方的 各接收符號(hào)模2加得 到的，而' -的k恰好是乘'-I :'j :(4)RS碼的生成多項(xiàng)式從上面的例子可以看出，為了糾正一個(gè)符號(hào)錯(cuò)，要 2個(gè)符號(hào)的檢測碼，一個(gè) 用來確定位置，一個(gè)用來糾錯(cuò)。一般來說糾t個(gè)錯(cuò)誤需要2t個(gè)檢驗(yàn)符，這

18、時(shí)要 計(jì)算2t個(gè)等式，確定t個(gè)位置和 糾t個(gè)錯(cuò)。能糾t個(gè)符號(hào)的RS碼生成多項(xiàng)式 為按照DVB的CATV標(biāo)準(zhǔn)RS碼生成多項(xiàng)式為：g(x) = (x + 2°)(j+2l)(x+2a)- (x + 2w)RSi 】RS(204，188，8)即分組碼符號(hào)長度為204個(gè)，188個(gè)信息符號(hào)，可糾錯(cuò)8個(gè)。2.7連環(huán)碼(卷積碼)連環(huán)碼是一種非分組碼，通常它更適用于前向糾錯(cuò)法，因?yàn)槠湫阅軐τ谠S多實(shí)際情況常優(yōu)于 分組碼，而且設(shè)備簡單。 這種連環(huán)碼在它的信碼元中也有 插入的監(jiān)督碼元但并不實(shí)行分組監(jiān)督，每一個(gè)監(jiān)督碼元都要對前后的信息單元 起監(jiān)督作用，整個(gè)編解碼過程也是一環(huán)扣一環(huán)，連鎖地進(jìn)行下去。這種碼提出至今還不到三十年，但是近十余年的發(fā)展表明，連環(huán)碼的糾錯(cuò)能力不亞于甚至 優(yōu)于分組碼。這一小節(jié)只介紹一種最簡單的連環(huán)碼，以便了解連環(huán)碼的基本概 念口圖6 8是連環(huán)碼的一種最簡單的編碼器。它由兩個(gè)移位寄存器，一個(gè)模2加法器及一個(gè)電 子開關(guān)組成。工作過程是：移位寄存器按信息碼的速度工 作，輸入一位信息碼，電子開關(guān)倒 換一次，即前半拍接通a端，后半拍接通b 端。因此，若輸入信息為則輸出連環(huán)碼為一，其中b”為監(jiān)督碼元。按圖6 8結(jié)構(gòu)可得：模2可見，這個(gè)連環(huán)碼的結(jié)構(gòu)是：“信息碼元某、監(jiān)督碼元、信息碼