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

糾錯編碼方式的簡介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 加法等同于“異或”運算?，F(xiàn)以偶監(jiān)督為例。 對于偶校驗，應(yīng)滿足 故監(jiān)督位碼元a0可由下式求出： (22) 不難理解，這種奇偶校驗編碼只能檢出單個或奇數(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)督。具體編 碼方法如下：將若干個所要傳送的碼組編成一個矩陣，矩陣中每一行為一碼組，每行的最后 加上 一個監(jiān)督碼元，進行奇偶監(jiān)督，矩陣中的每一列則由不同碼組相同位置的碼元組成，在每列 最后也加上一個監(jiān)督碼元，進行奇偶監(jiān)督。如果用表示信息位，用表示監(jiān)督位，由矩陣 碼 的結(jié)構(gòu)可如圖65所示，這樣，它的一致監(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 5中所示有的差錯情況。因此，矩陣碼發(fā)現(xiàn)錯碼的能力是十分強的，它的 編碼效率當然比奇偶監(jiān)督碼要低。 2.3 恒比碼 恒比碼又稱為定比碼。在恒比碼中，每個碼組“1”和“0”都保持固定的比例，故得此名。 這種碼在檢測時，只要計算接收到的碼組中“1”的數(shù)目是否對就知道有無錯誤。 在我國用電傳機傳輸漢字時，只使用阿拉伯數(shù)字代表漢字。這時采用的所謂“保護電碼”就 是“32”或稱“5中取3”的恒比碼，即每個碼組的長度為5，其中“1”的個數(shù)總是3，而 “0”的個數(shù)總是2。如表62所示。表 62數(shù)字字符普通的五單位碼恒比碼 12345111011100110000010100000101011110011011011010001116789010101111000110000011011011010111100011101001101101 本來以5位碼元組成的碼組總共可以有25=32種，而恒比碼規(guī)定只有確切地含有3個“1”， 2個“0”的那些碼組為準用碼組，而有3個“1”，2個“0”的5位碼組共有多少?這是“5中 取3”求組合的算法，組合數(shù)為，一般情況下， 從“n中取m”(mn)恒比碼的碼組數(shù)為： 由此可以看出，恒比碼實際上是n個碼元傳送比特信息，例如上述“32”即 “5中取2”恒比碼，用5位碼只傳10種信息。每個碼組的信息量為，有5-3.3=1.7bit作為代價付出。 恒比碼適用于傳輸字母和符號。2.4 漢明碼 漢明碼屬于線性分組編碼方式，大多數(shù)分組碼屬于線性編碼，其基本原理是，使信息碼元與 監(jiān)督碼元通過線性方程式聯(lián)系起來。線性碼建立在代數(shù)學群論的基礎(chǔ)上，各許用碼組的集合 構(gòu)成代數(shù)學中的群，故又稱為群碼。 (1)校驗子和監(jiān)督關(guān)系式 我們先回顧一下按式(22)條件構(gòu)成的偶數(shù)監(jiān)督碼。由于我們使用了一位監(jiān)督碼C0，它就 能和信息碼一起構(gòu)成一個代數(shù)式，在接收端解碼時，我們實際上是在計算 ， 若S=0，就認為無錯碼。若S=1，就認為有錯碼。上式就是一致監(jiān)督關(guān)系式。S稱為“校驗子 ”。由于校驗子S的取值只有這樣兩種，它就只能代表有錯和無錯兩種信息，而不能指出錯 碼的位置。我們不難推想，如監(jiān)督位增加一位，變成兩位，則能增加一個類似于式(23)的 監(jiān)督關(guān)系式。兩個校驗子的可能值有4種組合00，01，10，11。故能表示4種不同的信息，其 中一種表示無錯，其余三種就有可能用來指示一位錯碼的3種不同位置。同理，r個監(jiān)督關(guān)系 式能指示一位錯碼的()個可能位置。 一般說來，若碼長為n，信息碼為k，則監(jiān)督碼數(shù)r=n-k。若希望用r個監(jiān)督碼構(gòu)造出r個監(jiān)督 關(guān)系式來指示一位錯碼的n種可能位置，則要求： 下面通過一個例子來說明如何具體構(gòu)造這些監(jiān)督關(guān)系式。 設(shè)分組碼(n、k)中k=4，為了能糾正一位錯碼，按式(24)可知，要求監(jiān)督碼數(shù)r3，現(xiàn)取r =3，則n=k+r=4+3=7，這是一種(7、4)分組碼。我們用表示這7個碼 元，表示三個監(jiān)督關(guān)系式中的校驗子，則的值與錯碼位置 的對應(yīng)關(guān)系可以規(guī)定如表63，(當然也可以規(guī)定成另一種對應(yīng)關(guān)系，這不影響討論一般性 )。 按表63的規(guī)定，僅當有一個錯碼位置在時，校驗子S1為1 ，否則S1為0，這就意味著四個碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系： 錯碼位置錯碼位置001101010110100111011000無錯碼同理，構(gòu)成偶數(shù)監(jiān)督關(guān)系： 以及構(gòu)成偶數(shù)監(jiān)督關(guān)系：(2)監(jiān)督碼的確定 在發(fā)送端編碼時，信息碼的值決定于輸入信號，是隨機的。而監(jiān)督 碼則應(yīng)根據(jù)信息碼的取值按監(jiān)督關(guān)系式?jīng)Q定。即監(jiān)督碼的取值應(yīng)使上三式 中的值為0，表示編成的碼組中無錯碼： 由上式移項解出監(jiān)督碼：(在模2加法中，移項后沒有負號) 已知信息碼后，直接按上式可算出監(jiān)督碼，計算結(jié)果得出16個碼組列于表64中。 信息碼監(jiān)督碼信息碼監(jiān)督碼0000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111(3)解碼過程 接收端收到每個碼組后，按下述順序解碼。先按式(2-4)(26)計算出再按表63判斷錯誤情況。例如，若接收碼組為0000011，按式(24)(26)計算得： ， 由于，查表63可知有一錯碼為a3。 (4)漢明碼的效率 漢明碼的編碼效率 =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代表碼元，則有 (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 位，相應(yīng)于多項式； ，得余數(shù)； 與余數(shù)對應(yīng)位異或，得編碼信息T(x)。 例 數(shù)據(jù)信息 數(shù)據(jù)信息 1101011011M(X)生成式10011G(X),R=4加4個“0”之后 11010110110000/G(X)1110余數(shù)待發(fā)送的編碼11010110111110T(X)接收器收到發(fā)來的編碼信息后，用同一個生成多項式G(x)除以編碼信息，若余數(shù)為零， 則表示接收到正確的編碼信息，否則有錯。 把收到的正確編碼信息T(x)去掉尾部r位，即得數(shù)據(jù)信息M(x)。 (3)多項式碼檢錯能力及生成多項式G(x)的選擇原則 設(shè)接收到的信息不是發(fā)送的編碼信息T(x)，而是T(x)+E(x)。 例 有差錯的編碼信息為 1001001011 T(x)-E(x)=T(x)+E(x) 其中，1101011011 為T(x)0100010000 為E(x) 若接收到的有差錯的編碼信息為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) 這時應(yīng)該有余數(shù)，若無余數(shù)則檢不出錯。 有r位校驗位的多項式碼將能檢測所有r位的突發(fā)錯，故只要k-1r，就能檢測出所有突發(fā) 錯，這是一個很有用的結(jié)論。 生成多項式G(x)的國際標準有： CRC12CRC16CRCCCITTCRC16和CRCCCITT兩種生成多項式生成的CRC碼可以捕捉一位錯、二位錯、具有奇數(shù)個錯 的全部錯誤，可以捕捉突發(fā)錯長度小于16的全部錯誤、長度為17的突發(fā)錯的9999 8%、長度為18以上的突發(fā)錯的99997%。CRC16和CRCCCITT可以用硬件實現(xiàn)。 (4)CRC編碼硬件電路的實現(xiàn)設(shè) 數(shù)據(jù)1010多項式 生成多項式系數(shù)1011 多項式系數(shù)1010000 多項式 余式系數(shù)011多項式k(X)=X+1CRC編碼 1010001信息監(jiān)督信息組從高位端輸入的CRC編碼電路，如圖66所示，其工作原理是：首先門1關(guān)閉，門2開 通，依次輸入的信息元1010一面經(jīng)或門H直接輸出，同時送往除法電路進行除法運算。4次移 位后除法電路完成了運算，得余式系數(shù)為“011”，即為監(jiān)督元。第5個移位脈沖開始門1 開通，門2關(guān)閉，斷開了反饋，移位3次把移位寄存器中的3位余項作為監(jiān)督元附在信息元后 面，發(fā)出的碼字就是1010011，最后門1關(guān)閉，門2開通，對下一信息組再行編碼。有關(guān)工作 過程見表65 表65 圖66所示電路的工作過程移動脈沖輸入輸出注(初始狀態(tài))000門1關(guān)閉11011門2打開2011031100門1打開4001150110門2關(guān)閉60100700002.6 RS碼(ReedSolomon里德索羅門碼) RS碼是一種重要的線性分組編碼方式。它對突發(fā)性錯誤有較強的糾錯能力，被DVB標準采用 。 (1)在RS編碼過程中，各符號不是直接出現(xiàn)，而是每個符號要乘以某個基本元素的冪次方后 再模2加，如圖67所示。 (2)在循環(huán)碼中欲檢查是否有錯是用碼字除一個多項式，而在RS碼中，欲檢 出一系列誤碼則需要用碼字除一定數(shù)量的一次多項式。如果要糾正七個錯誤，那么碼字必須 被2t個不同的一次多項式整除，例如被x+an的一次多項式整除，這里的n取值直到2t的所 有整數(shù)值，a是基本元素，例如a為010，輸入5個符號，每個符號3比特，與相應(yīng)的元素相乘 后直接模2加輸出，因為有兩種系數(shù)，所以得到二個校檢子，兩個校驗式為： (3)下面舉一個簡單例子說明糾錯過程在無差錯時，S0=0，S1=0，有如下關(guān)系：碼字A101式中B100C010D100E111P100Q100=000當接收到的符號有錯時通過計算也可以得到與符號有關(guān)的錯誤圖形，這時有錯的 碼加撇，是錯誤圖形，真正的D=D+=101+001=100。但錯誤的位置將由S1決定 ，這要利用的關(guān)系。A101B100C010D101E111P100Q100=001校驗子的增加導致糾錯能力的加強，通過的運算可以確定差錯 的位子，并予以糾正。 盡管都是同一個錯誤的不同圖形，但因次方的各接收符號模2加得 到的，而的k恰好是乘的那一個符號。 (4)RS碼的生成多項式 從上面的例子可以看出，為了糾正一個符號錯，要2個符號的檢測碼，一個用來確定位置， 一個用來糾錯。一般來說糾t個錯誤需要2t個檢驗符，這時要計算2t個等式，確定t個位置和 糾t個錯。能糾t個符號的RS碼生成多項式為 按照DVB的CATV標準 RS碼生成多項式為： RS碼為： 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)碼的基本概念。 圖68是連環(huán)碼的一種最簡單的編碼器。它由兩個移位寄存器，一個模2加法器及一個電 子開關(guān)組成。工作過程是：移位寄存器按信息碼的速度工作，輸入一位信息碼，電子開關(guān)倒 換一次，即前半拍接通a端，后半拍接通b端。因此，若輸入信息為，則 輸出連環(huán)碼為，其中“b”為監(jiān)督碼元。按圖68 結(jié)構(gòu)可得：模2可見，這個連環(huán)碼的結(jié)構(gòu)是：“信息碼元某、監(jiān)督碼元、信息碼元、監(jiān)督碼元。”一個信息