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

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

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

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

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

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

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

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

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

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

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

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

12、數(shù)對應位異或，得編碼信息 T(x)。例數(shù)據(jù)信息數(shù)據(jù)信息11M(X)生成式10011G(X),R=4加4個0”之后110K 5%(X)1110余數(shù)待發(fā)送的編碼110T(X) 接收器收到發(fā)來的編碼信息后，用同一個生成多項式G(x)除以編碼信息，若余數(shù)為零，則表示接收到正確的編碼信息，否則有錯。 把收到的正確編碼信息T(x)去掉尾部r位，即得數(shù)據(jù)信息M(x)(3) 多項式碼檢錯能力及生成多項式 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)若接收到的有差錯的編碼信

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

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

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

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

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

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