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

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