【文章內(nèi)容簡(jiǎn)介】 間 比如一位重復(fù)發(fā)幾次，或一段消息重復(fù)發(fā)幾遍，或根據(jù)接收端的反饋重發(fā)受損信息組，像ARQ—automatic repeat request 系統(tǒng)那樣。第二，頻帶 插入冗余位后傳輸效率下降，若要保持有用信息的速率不變，最直接的方法就是增大符號(hào)傳遞速率(波特率)，結(jié)果就占用了更大的帶寬。比如采用二進(jìn)制(8,4)分組碼而保持頻帶利用率等于每赫茲每秒1個(gè)符號(hào)不變，則編碼后符號(hào)速率增大一倍，所占帶寬也增大一倍。第三，功率 采用多進(jìn)制符號(hào)，比如用一個(gè)8進(jìn)制ASK符號(hào)代替一個(gè)4進(jìn)制ASK符號(hào)來(lái)傳送2bit信息，可騰出位置另傳1冗余位。但為了維持信號(hào)集各點(diǎn)之間的距離不變，8進(jìn)制ASK符號(hào)的平均功率肯定比4進(jìn)制ASK符號(hào)的平均功率要大，這就是動(dòng)用冗余的功率資源來(lái)傳輸冗余比特。第四，設(shè)備復(fù)雜度 加大碼長(zhǎng)N，采用網(wǎng)格編碼調(diào)制(TCM)，是在功率、帶寬受限信道中實(shí)施糾錯(cuò)編碼的有效方法；其代價(jià)是算法復(fù)雜度的提高，需動(dòng)用設(shè)備資源。噪聲均化就是讓差錯(cuò)隨機(jī)化，以便更符合編碼定理的條件從而得到符合編碼定理的結(jié)果。噪聲均化的基本思想是設(shè)法將危害較大的，較為集中的噪聲干擾分?jǐn)傞_(kāi)來(lái)，使不可恢復(fù)的信息損傷最小。這是因?yàn)樵肼暩蓴_的危害大小不僅與噪聲總量有關(guān)，而且與其分布有關(guān)。舉例來(lái)說(shuō)，二進(jìn)制(7，4)漢明碼能糾一個(gè)差錯(cuò)，假設(shè)噪聲在14碼元(兩碼字)上產(chǎn)生2個(gè)差錯(cuò)，那么差錯(cuò)的不同分布將產(chǎn)生不同的后果。如果2個(gè)差錯(cuò)集中在前7碼元(同一碼字)上，該碼字將出錯(cuò)。如果差錯(cuò)分散在前、后兩個(gè)碼字，每碼字承受一個(gè)差錯(cuò)，則每碼字差錯(cuò)的個(gè)數(shù)都沒(méi)有超出起糾錯(cuò)能力范圍，這兩個(gè)碼字將全部正確解碼。由此可見(jiàn)：集中的噪聲干擾(稱之為突發(fā)差錯(cuò))的危害甚于分散的噪聲干擾(稱之為隨機(jī)差錯(cuò))。噪聲均化正是將差錯(cuò)均勻分?jǐn)偨o各個(gè)碼字，達(dá)到提高總體差錯(cuò)控制能力的目的?！〕Ｓ脵z錯(cuò)碼與糾錯(cuò)碼　等重碼等重碼又叫恒比碼, 其特點(diǎn)是編碼集中每個(gè)編碼組中“1”和“0”的個(gè)數(shù)保持恒定比例。該碼能檢測(cè)奇數(shù)個(gè)差錯(cuò), 故在實(shí)際中常運(yùn)用反饋重發(fā)方式使差錯(cuò)明顯減少, 因此又稱為數(shù)字保護(hù)碼。這種碼除了“1”錯(cuò)成“0”和“0”錯(cuò)成“1”成對(duì)性錯(cuò)誤外, 其他錯(cuò)誤均能發(fā)現(xiàn), 故它有很強(qiáng)的檢錯(cuò)能力[9]。　群計(jì)數(shù)和水平計(jì)數(shù)所謂計(jì)數(shù)就是統(tǒng)計(jì)要傳送字符信息中“1”的個(gè)數(shù),將此計(jì)數(shù)值作為校驗(yàn)位附加在該字符信息之后傳遞,例如: 一個(gè)7單位字符為1001011, 該字符中, “1”的個(gè)數(shù)為4, 則傳送的碼字為1001011100。這種碼的檢錯(cuò)能力很強(qiáng), 除了“0”錯(cuò)成“1”和“1”錯(cuò)成“0”成對(duì)性錯(cuò)誤和信息位與校驗(yàn)位的對(duì)偶性錯(cuò)誤外, 其他形式的錯(cuò)誤均能檢出[9]?！『Ｃ鞔a海明碼是由海明實(shí)現(xiàn)的一位糾錯(cuò)碼, 其碼字位是按順序編號(hào)的, 即從左向右為l, 2, …, n。凡為2的冪數(shù)位(即l，2，4，16，32…) 均為校驗(yàn)位, 其它位為信息位。碼字位中的校驗(yàn)位取值是使一些位的集合(包括校驗(yàn)位在內(nèi))的奇偶性為奇(或?yàn)榕?,一位代碼位可加入若干個(gè)奇偶性的計(jì)算中。為了知道第k位信息位是由哪些校驗(yàn)位加以校驗(yàn)的, 只要將k表示為冪數(shù)和, 例如: 15=1+2+4+8,27=1+2+8+16, 即該位信息位就由展開(kāi)式中這些校驗(yàn)位加以校驗(yàn)。當(dāng)一個(gè)碼被接收端所接收時(shí), 將接收器的計(jì)數(shù)器置為0, 然后檢查每個(gè)校驗(yàn)位k, 看它是否有正確值。如不正確就把校驗(yàn)碼位號(hào)k加到計(jì)數(shù)器中, 當(dāng)計(jì)數(shù)器的結(jié)果不為0時(shí), 表示該碼字有錯(cuò), 該計(jì)數(shù)器的值就是錯(cuò)誤的信息位號(hào), 只要把該位的值取反, 就可達(dá)到糾錯(cuò)的目的。例如: 發(fā)現(xiàn)第1, 2, 4, 8位有錯(cuò), 就知道第15位信息位有錯(cuò), 將第15位的數(shù)值取反, 即可糾錯(cuò)。海明碼只能糾正一位錯(cuò), 但也可用它來(lái)糾突發(fā)錯(cuò)。其方法是: 將K個(gè)碼字排列成一個(gè)矩陣, 每個(gè)碼字占一行。為糾正突發(fā)錯(cuò), 發(fā)送時(shí)從左到右按列進(jìn)行, 一次一列, 一列K位發(fā)送完再發(fā)送第二列, 直到最后一列。到達(dá)接收端再按列重新構(gòu)造此矩陣。如果發(fā)生了長(zhǎng)度為K(一連錯(cuò)K位) 的突發(fā)錯(cuò), 則矩陣中K個(gè)碼字中的每一個(gè)都有一位錯(cuò), 而海明碼能糾正一位錯(cuò), 所以整塊數(shù)據(jù)就能得到糾正。這種方法是用KI個(gè)校驗(yàn)位來(lái)糾正KN個(gè)數(shù)據(jù)塊所產(chǎn)生的一個(gè)長(zhǎng)度不大于K位的突發(fā)錯(cuò)　卷積碼以上提到碼的都是分組碼, 它們的特點(diǎn)是將輸入的信息序列分割成長(zhǎng)度為k的組, 在編碼時(shí), 將一組k個(gè)信息序列變成長(zhǎng)度為n的碼字序列。在一個(gè)碼字中, nk個(gè)校驗(yàn)碼元僅本組的k個(gè)信息碼元有關(guān), 而與其它組的信息碼元無(wú)關(guān)。譯碼時(shí), 也僅從本碼字碼元內(nèi)提取有關(guān)的譯碼信息, 而與其它各組無(wú)關(guān)。卷積碼則與分組碼截然不同。它先是將信息序列分成長(zhǎng)度為k的一個(gè)個(gè)小組, 長(zhǎng)度為n的每個(gè)子組碼字(稱為子碼) 包括k個(gè)信息碼元,nk個(gè)校驗(yàn)碼元(也稱監(jiān)督碼元) 。這nk個(gè)校驗(yàn)碼元, 不僅與本組的k個(gè)信息碼元有關(guān), 而且也與前面若干個(gè)子組的信息碼元有關(guān)。本組的信息碼元不僅決定本組的校驗(yàn)碼元, 而且也參與決定以后若干組的校驗(yàn)碼元。譯碼時(shí), 不但從該時(shí)刻收到的碼組中提取譯碼信息, 而且還利用以后若干時(shí)刻內(nèi)所收到的碼組來(lái)提取有關(guān)信息?！z錯(cuò)碼與糾錯(cuò)碼　糾錯(cuò)碼在了解糾錯(cuò)碼之前，先了解一個(gè)基本概念：海明距離。通常一幀包括m個(gè)數(shù)據(jù)(報(bào)文)位和r個(gè)冗余位或者校驗(yàn)位。設(shè)整個(gè)長(zhǎng)度為n(即n=m+r)，則此長(zhǎng)度為n的單元通常被稱作n位碼字。給出的任意兩個(gè)碼字，如10001001和10110001，可以確定它們有多少個(gè)對(duì)應(yīng)位不同。在此例中有3位不同。為了確定有多少位不同，只須對(duì)兩個(gè)碼字做異或運(yùn)算，然后計(jì)算結(jié)果中1的個(gè)數(shù)。兩個(gè)碼字中不同位的個(gè)數(shù)，稱為海明距離(Hamming Distance)。其重要性在于，假如兩個(gè)碼字具有海明距離d，則需要d個(gè)位差錯(cuò)才能將其中一個(gè)碼字轉(zhuǎn)化成另一個(gè)。一種編碼的校驗(yàn)和糾錯(cuò)能力取決于它的海明距離。為了檢測(cè)出d比特錯(cuò)，需要使用d+1的編碼；因?yàn)閐個(gè)單比特錯(cuò)決不可能將一個(gè)有效的碼字轉(zhuǎn)變成另一個(gè)有效的碼字。當(dāng)接收方看到無(wú)效的碼字，它就能明白發(fā)生傳輸錯(cuò)誤。同樣，為了糾正d比特錯(cuò)，必須使用距離為2d+1的編碼，這是因?yàn)橛行Тa字的距離遠(yuǎn)到即使發(fā)生d個(gè)變化，這個(gè)發(fā)生了變化的碼字仍然比其它碼字都接近原始碼字。作為糾錯(cuò)碼的一個(gè)簡(jiǎn)單例子，考慮如下只有4個(gè)有效碼字的代碼：0000000000、0000011111111100000和1111111111這種代碼的距離為5，也就是說(shuō)，它能糾正雙比特錯(cuò)誤。假如碼字0000000111到達(dá)后，接收方知道原始碼字應(yīng)該為0000011111。但是，如果出現(xiàn)了三位錯(cuò)，而將0000000000變成0000000111，則差錯(cuò)將不能正確糾正?！z錯(cuò)碼檢錯(cuò)碼有時(shí)也用于數(shù)據(jù)傳輸[5]。例如，當(dāng)信道為單工方式，無(wú)法要求重傳的情況下，大多數(shù)采用檢錯(cuò)碼與重傳的方式。假設(shè)信道的出錯(cuò)是孤立的信道的誤碼率為，每位數(shù)據(jù)塊的大小為100位。為1000位的數(shù)據(jù)塊糾錯(cuò)，需要10個(gè)校驗(yàn)位；1兆的數(shù)據(jù)位將需要10000個(gè)校驗(yàn)位。若只需要檢測(cè)一個(gè)數(shù)據(jù)塊的一位錯(cuò)誤，每塊一個(gè)奇偶位就夠了。每傳送1000個(gè)數(shù)據(jù)塊就需要額外傳送一個(gè)數(shù)據(jù)塊。錯(cuò)誤檢錯(cuò)+重傳方式的整個(gè)開(kāi)銷，僅僅是每兆數(shù)據(jù)只有2001位，而海明碼為10000位。假若在一個(gè)塊上只加一個(gè)奇偶位，這是難以接受的。改進(jìn)的措施可以采取將每個(gè)數(shù)據(jù)塊組成n位寬k行高的長(zhǎng)方形矩陣進(jìn)行發(fā)送。對(duì)每一列的奇偶位分別進(jìn)行計(jì)算，附加在矩陣上，作為矩陣的最后一行，然后按行進(jìn)行發(fā)送。當(dāng)塊到達(dá)后，接收方檢測(cè)所有的奇偶位。如果任何一個(gè)出錯(cuò)了，就需要重新傳送整個(gè)塊。這種方法能夠檢測(cè)到單個(gè)程度為n的突發(fā)錯(cuò)誤，因?yàn)槊恳涣兄挥幸晃桓淖兞?。然而如果第一位變反，最后一位變反，且所有其它位都正確，則長(zhǎng)度為n+1的突發(fā)差錯(cuò)將不會(huì)被檢測(cè)到。假如一個(gè)塊被一個(gè)長(zhǎng)的突發(fā)差錯(cuò)或者短的突發(fā)差錯(cuò)所破壞，那么這個(gè)出錯(cuò)塊被接受的概率不應(yīng)該是2n?！z錯(cuò)碼與糾錯(cuò)碼的關(guān)系下面以(7 ，4)線形分組碼的構(gòu)筑方法來(lái)說(shuō)明檢錯(cuò)碼是如何過(guò)渡到糾錯(cuò)碼的。設(shè)某信息經(jīng)信源編碼后成為16個(gè)由0和1組成的4位代碼組信息，即16=2，k=4。為了糾正一個(gè)錯(cuò)誤，r=2不行，因?yàn)閚=4+2=6，校驗(yàn)矩陣只有2行6列。但是，為使伴隨式能定出錯(cuò)誤的位置，要求6列各不相同。位r=2顯然不夠用。若r=3，則=8，全零列是不能用的(因?yàn)榘殡S式等于零已對(duì)應(yīng)于無(wú)錯(cuò))，剩下的非零7列可用來(lái)構(gòu)成一致校驗(yàn)矩陣。例如可?。? (22)該碼的編碼方法如下：==如當(dāng)消息為1010時(shí)：= (23)將： 式(22)和式(23)代入式： =0 得：=1+0+1=0, =1+0+0=1, =1+1+0=0；即計(jì)算得碼字為1010010；同理可計(jì)算出其他信息位的碼字?！”菊滦〗Y(jié)本章介紹了糾錯(cuò)碼的基礎(chǔ)概念重點(diǎn)介紹了糾錯(cuò)碼的基礎(chǔ)概念和差錯(cuò)控制方式　以及它們的分類，提出了糾錯(cuò)碼的基本原理和分析方法，對(duì)糾錯(cuò)碼和檢錯(cuò)碼進(jìn)行了區(qū)別和聯(lián)系進(jìn)行了分析。第3章 BCH糾錯(cuò)碼的編碼和譯碼原理 第3章 BCH糾錯(cuò)碼的編碼和譯碼原理BCH碼由博斯(Bose)、查德胡里(Chaudhuri)和霍昆格姆(Hocquenghem)提出，并以三個(gè)人名字的開(kāi)頭字母命名；是迄今為止發(fā)現(xiàn)的最好的線形分組碼之一。該碼有嚴(yán)格的代數(shù)結(jié)構(gòu)，是直至目前研究的最為詳盡、了解的最為透徹、取得成果最多的一類碼。特別是該碼的生成多項(xiàng)式g(x)與最小的距離d之間有密切的關(guān)系，可以根據(jù)d的要求，很容易的構(gòu)造出好碼，且編碼、譯碼電路容易實(shí)現(xiàn)。 BCH碼的特點(diǎn)BCH碼可以是二進(jìn)制碼,也可以是非二進(jìn)制的，作為本原循環(huán)碼的一個(gè)重要子類，其最基本的特點(diǎn)是它的生成多項(xiàng)式g(x)包含2t個(gè)連續(xù)冪次的根。理論上(BCH碼限定理)已有證明：若生成多項(xiàng)式含有2t個(gè)連續(xù)冪次的根，則該碼的最小距離≥2t+1，也就是說(shuō)該碼的糾錯(cuò)能力是int[(－1)／2]=t。BCH碼的出現(xiàn)為通信系統(tǒng)設(shè)計(jì)者在糾錯(cuò)能力、碼長(zhǎng)和碼率的選擇和控制上提供了很大的靈活性，一旦要求的糾錯(cuò)能力t給定，只要算出2t個(gè)連續(xù)冪次的根所對(duì)應(yīng)的多項(xiàng)式作為生成多項(xiàng)式，就可以得到糾錯(cuò)能力符合要求的碼　BCH碼的生成多項(xiàng)式若生成的多項(xiàng)式具有如下形式[8]：g(D)=LCM[m(D),m(D),…,m(D)]這里t為糾錯(cuò)個(gè)數(shù)，m(D)為最小多項(xiàng)式，LCM表示取最小公倍式，則由此生成的循環(huán)碼稱之為BCH碼。該碼的最小碼距d≥2t+1,能糾正t個(gè)錯(cuò)誤。BCH碼的碼長(zhǎng)為n=－1或－1的因子。碼長(zhǎng)為n=－1的BCH碼稱為本原BCH碼，碼長(zhǎng)為－1因子的BCH碼稱為非本原BCH碼。對(duì)于糾t個(gè)錯(cuò)誤的本原BCH碼，其生成多項(xiàng)式為：g(D)= m(D) m(D)…m(D)。糾正單個(gè)錯(cuò)誤的本原BCH碼就是循環(huán)漢明碼?！CH碼的幾種常見(jiàn)碼(1)戈雷碼(Golay)(23，12)碼是一個(gè)特殊的非本原BCH碼，稱為戈雷碼，它的最小碼距為7，能糾正3個(gè)錯(cuò)誤，其生成多項(xiàng)式g(D)=D+D+D+D+D+D+1，它也是目前為止發(fā)現(xiàn)的唯一能糾正多個(gè)錯(cuò)誤的完備碼。(2)擴(kuò)展形式 實(shí)際應(yīng)用中，為了得到偶數(shù)碼長(zhǎng)，并增加檢錯(cuò)能力，可以在BCH碼的生成多項(xiàng)式中乘D+1，從而得到(n+1,k+1)擴(kuò)展BCH碼。擴(kuò)展BCH碼相當(dāng)于將原有BCH碼再加上一位偶校驗(yàn)，它不再有循環(huán)性。(3)縮短形式幾乎所有的循環(huán)碼都存在其另一種縮短形式(n－k ,k－s)。在實(shí)際應(yīng)用中，可能需要不同的碼長(zhǎng)，且該碼長(zhǎng)不是－1或－1的因子，我們可以從(－1，k)碼中挑出前s位為0的碼組構(gòu)成新的碼，這種碼的監(jiān)督位數(shù)不變，因此糾錯(cuò)能力保持不變，但是它沒(méi)有了循環(huán)性。 BCH碼的編碼原理BCH碼1959年由Hocquenghem、1960年由Bose和Chandhari分別獨(dú)立提出。對(duì)于GF(2)循環(huán)碼的生成多項(xiàng)式g(x)，若在某個(gè)擴(kuò)域空間GF()含有2t個(gè)連續(xù)冪次的根，則由g(x)生成的(n ,k)循環(huán)碼稱之為二進(jìn)制本原BCH碼。其中：n=－1.根據(jù)分析存在：若BCH碼生成多項(xiàng)式g(x)另含有2t個(gè)連續(xù)冪次的根，則該碼的最小距離=INT[(－1)／2]。設(shè)計(jì)給定碼字長(zhǎng)度n，信息長(zhǎng)度k，糾錯(cuò)能力t的BCH碼關(guān)鍵是在GF()擴(kuò)域?qū)ふ遥?=0的n－k個(gè)根(共有n個(gè)根)，其中包含2t個(gè)連續(xù)冪次的根：其次，確定各個(gè)根對(duì)應(yīng)的GF(2)基域既約多項(xiàng)式；再之求各既約多項(xiàng)式的最小公倍數(shù)可得到滿足條件的BCH碼生成多項(xiàng)式g(x)。令a為伽羅華域的本原元，令(x)為域元素的最小多項(xiàng)式，則糾正t個(gè)錯(cuò)誤的BCH碼生成多項(xiàng)式為： g(x)=LCM[(x),(x),…,(x)]由生成多項(xiàng)式g(x)，可得到生成矩陣相乘BCH碼序列：c(x)=+x+…+ 信道接收端的硬判決序列b(x)=+x+…+,所以信道干擾迭加的錯(cuò)誤圖樣為e(x)=b(x)c(x) BCH碼的結(jié)構(gòu)及BCH碼的一般編譯方法BCH碼作為循環(huán)碼的一個(gè)重要子類，它具有同時(shí)糾正多個(gè)錯(cuò)誤的能力，并且BCH碼有嚴(yán)密的代數(shù)理論，是目前研究最透徹的一類碼。它的生成多項(xiàng)式與最小碼距之間有密切的關(guān)系，人們可以根據(jù)所要求的糾錯(cuò)能力t很容易構(gòu)造出BCH碼，它們的譯碼器也容易實(shí)現(xiàn)，是線性分組碼中應(yīng)用最普遍的一類碼?！CH碼的結(jié)構(gòu)BCH碼屬于循環(huán)碼的一個(gè)子類，易于實(shí)現(xiàn)編碼，并且有明確的代數(shù)結(jié)構(gòu)和高效譯碼方案，是糾多個(gè)錯(cuò)誤的高效碼。BCH碼是循環(huán)碼，故可以用生成多項(xiàng)式來(lái)定義。令a擴(kuò)充域GF(2)中的本原元素。應(yīng)將糾t上差錯(cuò)的BCH碼的生成多項(xiàng)式選得使連續(xù)的2t個(gè)，… ， 都是它的根， 即它們也是每個(gè)碼字的根。按上述定義得到的碼叫做本原BCH碼。對(duì)于任何正整數(shù)m和t，存在一個(gè)下列參數(shù)的二元BCH碼：碼長(zhǎng)：n=1；一致校驗(yàn)位數(shù)目：nk≦mt ；最小距離：d≧2t+1。對(duì)于BCH(31，21)碼來(lái)說(shuō)，該碼的生成多項(xiàng)式為:g(x)=x+x+x+x+x+x+1，n=31，k=21，t=2　多元BCH碼BCH碼是一類能糾正多個(gè)隨機(jī)錯(cuò)誤的循環(huán)碼，因此研究BCH碼應(yīng)該從循環(huán)碼的生成多項(xiàng)式入手。碼組符號(hào)取自多元域GF(q),q為某一素?cái)?shù)的冪，糾正t個(gè)錯(cuò)誤的多元BCH碼的生成多項(xiàng)式是以GF(q)域的擴(kuò)張域G(q)上的2t個(gè)相鄰元素為根的多項(xiàng)式：g(x)=(xa)(xa)…(xa)式中的a, a