【文章內(nèi)容簡(jiǎn)介】 d when transmitted through unreliable data channel, pletes the process of reliable datatransmitting through unreliable data channel, reassures the importance of Cyclical Code Encoding. KEY WORDS Cyclical Code, Incapsulating, ErrorCorrecting 循環(huán)碼的數(shù)據(jù)容錯(cuò) 第一章 循環(huán)碼容錯(cuò)概述 3 第一章 循環(huán)碼容錯(cuò)概述 本章主要介紹了數(shù)據(jù)容錯(cuò)技術(shù)的背景及意義，并且討論了該技術(shù)的現(xiàn)狀和發(fā)展前景，就此提出問(wèn)題并確定目標(biāo)，最后就開(kāi)發(fā)此系統(tǒng)所要用到的相關(guān)技術(shù)作簡(jiǎn)要的說(shuō)明。 由于數(shù)字信號(hào)在傳輸過(guò)程中受到干擾的影響，使信號(hào)碼元波形變壞，故傳輸?shù)浇邮斩撕罂赡馨l(fā)生錯(cuò)誤判決。由信道中乘性干擾引起的碼間干擾，通?？梢圆捎镁獾霓k法糾正，而加性干擾的影響則要從其他途徑解決。通常，在設(shè)計(jì)數(shù)字通信系統(tǒng)時(shí)，首先應(yīng)從合理地選擇調(diào)制制度、解調(diào)方法以及發(fā)送功率等方面考慮。若采取上述措施仍難以滿足要求，則 就要考慮采用差錯(cuò)控制措施。 在隨機(jī)信道中，錯(cuò)碼的出現(xiàn)是隨機(jī)的，且錯(cuò)碼之間是統(tǒng)計(jì)獨(dú)立的 [6]。例如，由正態(tài)分布白噪聲引起的錯(cuò)碼就具有這種性質(zhì)。因此，當(dāng)信道中加性干擾主要是這種噪聲時(shí)，就稱這種信道為隨機(jī)信道。在突發(fā)信道中，錯(cuò)碼是成串集中出現(xiàn)的，也就是說(shuō)，在一些短促的時(shí)間區(qū)間內(nèi)會(huì)出現(xiàn)大量錯(cuò)碼，面在這些短促的時(shí)間區(qū)間之間卻又存在較長(zhǎng)的無(wú)錯(cuò)碼區(qū)間。對(duì)于不同類型的信道，應(yīng)采用不同的差錯(cuò)控制技術(shù)。 在實(shí)際應(yīng)用中，數(shù)據(jù)傳輸一般采用系統(tǒng)碼的編碼方式，即在發(fā)送的信息序列之后附加上特定位數(shù)序列的冗余位，該冗余位稱為所發(fā)送的信息序 列的監(jiān)督位。監(jiān)督位一般是由所發(fā)送的信息序列經(jīng)過(guò)恰當(dāng)?shù)淖兓a(chǎn)生。若監(jiān)督位由信息序列經(jīng)過(guò)線性組合得到，則稱得到的碼為線性分組碼。 循環(huán)碼是線性分組碼的一個(gè)重要子類，具有嚴(yán)密的代數(shù)學(xué)理論 [2]。循環(huán)碼“線性”是指任意兩個(gè)循環(huán)碼模 2 相加所得的新碼仍為循環(huán)碼。循環(huán)碼具有線性碼的一般性質(zhì)（即封閉性，指一種線性分組碼的任意兩個(gè)碼組這和仍是該分組碼的另一個(gè)碼組）外，還具有循環(huán)性，即循環(huán)碼中任一碼組循環(huán)一位（將最右端碼元移至左端，或反之）以后，仍為該碼組中的一個(gè)碼組。（ n， k） 循環(huán)碼表示其中信息位為 k，監(jiān)督位為 nk 位。 循環(huán)碼的數(shù)據(jù)容錯(cuò) 第一章 循環(huán)碼容錯(cuò)概述 4 本節(jié)介紹相關(guān)技術(shù)在國(guó)內(nèi)外的己有的發(fā)展。 單片機(jī)應(yīng)用 循環(huán)碼為信道編碼，具有很強(qiáng)的糾、檢錯(cuò)功能，它是建立在嚴(yán)密的數(shù)學(xué)理論基礎(chǔ)之上 [8]。循環(huán)碼具有固定的代數(shù)結(jié)構(gòu)，可以用線性反饋移位寄存器實(shí)現(xiàn)編譯碼電路，所以可以找到很多簡(jiǎn)單的編譯碼方法，目前在數(shù)據(jù)通信上特別是在衛(wèi)星通信中循環(huán)碼得到了廣泛應(yīng)用。 近年來(lái)隨著計(jì)算機(jī)軟件的飛速發(fā)展，許多用實(shí)物實(shí)現(xiàn)的問(wèn)題都可以在軟件上得以實(shí)現(xiàn)。單片機(jī)就是軟件發(fā)展的杰出產(chǎn)物。單片機(jī)具有內(nèi)部資源豐富，性能全面，通用性強(qiáng)，可覆蓋多種應(yīng)用要求的優(yōu)點(diǎn) [4]?；趩纹瑱C(jī)設(shè)計(jì)的電路十分廣泛的應(yīng)用在當(dāng)今的各個(gè)領(lǐng)域中。 以往循環(huán)碼編譯碼電路大多用移位寄存器和模 2 和構(gòu)成的線性時(shí)序網(wǎng)絡(luò)來(lái)完成?；倦娐泛?jiǎn)單，容易實(shí)現(xiàn)。但在體積和功能的擴(kuò)展上受到了限制而不能發(fā)揮更大作用。使用軟件編程方法實(shí)現(xiàn)編譯碼過(guò)程既有簡(jiǎn)化電路，可靠性高、運(yùn)算速度快、體積小等優(yōu)點(diǎn)，又可以擴(kuò)展電路其它功能 [9]。而且可以根據(jù)具體要求任意修改，這是其它硬件電路所無(wú)法相比的。是拋開(kāi)傳統(tǒng)模式的一種新的嘗試。 在由單片機(jī)組成的遙測(cè)、遙控系統(tǒng)中，大多數(shù)直接利用單片機(jī)的串行通信功能進(jìn)行數(shù)據(jù)的傳輸和控制。然而在實(shí)際通信 過(guò)程中，大量的隨機(jī)干擾嚴(yán)重影響了數(shù)據(jù)傳輸?shù)臏?zhǔn)確性，破壞了系統(tǒng)的穩(wěn)定性，使串行通信的誤碼率大到了不可容忍的程度。因此，有前人針對(duì)信道對(duì)于數(shù)據(jù)傳輸?shù)挠绊懀岢隽嘶趩纹瑱C(jī) MCS52單片機(jī)系統(tǒng)的軟件糾錯(cuò)編碼、譯碼方案，并詳細(xì)介紹了其實(shí)現(xiàn)方法。 網(wǎng)絡(luò)應(yīng)用 在網(wǎng)絡(luò)編碼中，還有一種稱為 CRC，即循環(huán)冗余校驗(yàn)碼的多項(xiàng)式編碼，這種編碼的基本思想是：將位串看成是系數(shù)為 0 或 1的多項(xiàng)式。一個(gè) k位的幀看作是一個(gè) k1次多項(xiàng)式的系數(shù)列表，該多項(xiàng)式共有 k 項(xiàng)，從 1?kx 到 0x 。 這樣的多項(xiàng)式認(rèn)為是 k1階多項(xiàng)式。高次（最左邊）位是 1?kx 項(xiàng)的系數(shù)：接下去的位是 2?kx 項(xiàng)的系數(shù)；依此類推 [3]。例如， 110001有 6 位，因此代表了一個(gè)共有 6項(xiàng)的多項(xiàng)式，其系數(shù)為 0、 0、 0 和 1 ，即 045 xxx ?? 。 循環(huán)碼的數(shù)據(jù)容錯(cuò) 第一章 循環(huán)碼容錯(cuò)概述 5 多項(xiàng)式的算術(shù)運(yùn)算采用代數(shù)域理論的規(guī)則，以 2為模來(lái)完成。加法沒(méi)有進(jìn)位，減法沒(méi)有借位。加法和減法都等同于異或 [9]。 當(dāng)使用多項(xiàng)式編碼時(shí)，發(fā)送方和接 收方必須預(yù)先商定一個(gè)生成多項(xiàng)式 [1]。生成多項(xiàng)的最高位和最低位必須是 1。假設(shè)一幀有 m位，它對(duì)應(yīng)于多項(xiàng)式 M(x)，為了計(jì)算它的校驗(yàn)和，該幀必須比生成多項(xiàng)式長(zhǎng)。基本的思想是在幀的尾部追加一個(gè)校驗(yàn)和，使得追加這后的幀所對(duì)應(yīng)的多項(xiàng)式能夠被 G(x)除盡。當(dāng)接收方收到了帶校驗(yàn)和的幀之后，它方式著用 G(x)去除它。如果有余數(shù)的話，則表明傳輸過(guò)程中有錯(cuò)誤 [5]。 循環(huán)碼的數(shù)據(jù)容錯(cuò) 第二章 課題理論介紹 6 第二章 課題理論介紹 本章主要介紹循環(huán)碼的相關(guān)理論依據(jù)及原理。 在線性分 組碼中，有一種重要的碼稱為循環(huán)碼。它是在嚴(yán)密的代數(shù)學(xué)理論基礎(chǔ)上建立起來(lái)的。這種碼的編碼和解碼設(shè)備都不太復(fù)雜，且檢（糾）錯(cuò)的能力較強(qiáng)，目前在理論上和實(shí)踐上都有了較大的發(fā)展。循環(huán)碼除了具有線性碼的一般性質(zhì)外，還具有循環(huán)性，即循環(huán)碼中任一碼組循環(huán)一位（將最右端的碼元移至左端，或反之）以后，仍為該碼中的一個(gè)碼組。在表 中給出一種（ 7， 3）循環(huán)碼的全部碼組。由此表可以直觀看出這種碼的循環(huán)性。例如，表 中的第 2 碼組向右移一位即得到第 5碼組；第 5碼組向右移一位即得到第 7碼組。一般來(lái)說(shuō)，若( 021 aaa nn ????? )是一個(gè)循環(huán)碼組，則 表 碼組編號(hào) 信息位 監(jiān)督位 碼組編號(hào) 信息位 監(jiān)督位 456 aaa 0123 aaaa 456 aaa 0123 aaaa 1 2 3 4 000 001 010 011 0000 0111 1110 1001 5 6 7 8 100 101 110 111 1011 1100 0101 0010 ( 1032 ??? ??? nnn aaaa ) ( 2143 ???? ??? nnnn aaaa ) ( 1210 aaaa n ???? ) 也是該編碼中的碼組。在代數(shù)編碼理論中，為了便于計(jì)算，把這樣的碼組中各碼元當(dāng)作是一個(gè)多項(xiàng)式的系數(shù)，即把一個(gè)長(zhǎng)度為 n 的碼組表示成 012211)( axaxaxaxT nnnn ???????? ???? 公式 () 表 中的任一碼組可以表示為 012233445566)( axaxaxaxaxaxaxT ??????? 公式 () 例如，表中的第 7組可以表示為 循環(huán)碼的數(shù)據(jù)容錯(cuò) 第二章 課題理論介紹 7 11010011)( 25623456 ????????????????? xxxxxxxxxxT 公式 () 這種多項(xiàng)式中， x僅是碼元位置的標(biāo)記，例如上式表示第 7 碼組中 6a 、 5a 、2a 和 0a 為“ 1”，其他均為零。因此我們并不關(guān)心 x 的取值。這種多項(xiàng)式有時(shí)稱為碼多項(xiàng)式。 在整數(shù)運(yùn)算中，有模 n 運(yùn)算。例如，在模 2 運(yùn)算中，有 1+1=2? 0（ 模 2） ，1+2=3? 1（模 2）， 2*3=6? 0（模 2）等。一般來(lái)說(shuō)，若一整數(shù) m 可以表示為 npQnm ?? np? 公式 () 式中 Q—— 整數(shù)。 則在模 n運(yùn)算下，有 pm? (模 n ) 公 式 () 這就是說(shuō)，在模 n運(yùn)算下，一整數(shù) m等于其被 n 除得這余數(shù)。 在碼多項(xiàng)式運(yùn)算中也有類似的按模運(yùn)算。若一任意多項(xiàng)式 F(x)被一 n 次多項(xiàng)式 N(x)除，得到商式 Q(x)和一個(gè)次數(shù)小于 n的余式 R(x)，即 )()()()( xRxQxNxF ?? 公式 () 則寫(xiě)為 )()( xRxF ? (模 )(xN ) 公式 () 這時(shí)，碼多項(xiàng)式系數(shù)仍按模 2 運(yùn)算，即只取值 0 和 1。例如， 3x 被 ( 13?x )除得余項(xiàng) 1，所以有 13?x (模 13?x ) 公式 () 同理 11 224 ????? xxxx (模 13?x ) 公式 () 因?yàn)? xxxxxx????4243 11 12 ??xx 注意，由于在模 2運(yùn)算中，用加法代替了減法，故余項(xiàng)不是 12 ??xx ，是 12 ?? xx 。 循環(huán)碼的數(shù)據(jù)容錯(cuò) 第二章 課題理論介紹 8 在循環(huán)碼中，若 )(xT 是一個(gè)長(zhǎng)為 n 的許用碼組，則 )(xTxi ? 在按模 12 ??xx運(yùn)算下，亦是一個(gè)許用碼組，即若 )()( 39。 xTxTxi ?? (模 1?nx ) 公式 () 則 )(39。 xT 也是一個(gè)許用碼組。其證時(shí)是很簡(jiǎn)單的，因?yàn)槿? 012211)( axaxaxaxT nnnn ???????? ???? 公式 () 則 )1()( 1102211 011112211????????????? ??????????????? ???????????????????nininininniniinininninnixaxaxaxaxa xaxaxaxaxaxTx 模 公式 () 所以這時(shí)有 1110221139。 )( ????????? ????????????? ninininnin axaxaxaxaxT 公式 () 公式 ()中 )(39。 xT 正是公式 ()中 )(xT 代表的碼組向左循環(huán)移位 i 次的結(jié)果。因?yàn)樵鸭俣?)(xT 為一循環(huán)碼，所以 )(39。 xT 也必為該碼中一個(gè)碼組。例如，式 ()中循環(huán)碼 1)( 256 ???? xxxxT 其碼長(zhǎng) n=7?，F(xiàn)給定 i=3，則 )1()1()( 723535892563 ?????????????? xxxxxxxxxxxxxxTx i 模 公式 () 其對(duì)應(yīng)的碼組為 0101110，它正是表 96中第 3碼組。 由上述分析可見(jiàn)，一個(gè)長(zhǎng)為 n 的循環(huán)碼，它必為按模 ( 1?nx )運(yùn)算 的一個(gè)余式。 根據(jù)線性碼的性質(zhì)可知，有了生成矩陣 G，就可以由 k 個(gè)信息位得出整個(gè)碼組，而且生成矩陣 G 的每一行都是一個(gè)碼組 [5]。例如，在式 ()中，若10003456 ?aaaa ，則碼組 A就等于 G的第一行；若 01003456 ?aaaa ，則碼組 A 就等于 G的第二行，等等。由于 G是 k行 n列矩陣，因此，若能找到 k個(gè)已知碼組，就能構(gòu)成矩陣 G。如前所述，這 k 個(gè)已知碼組必須是線性不相關(guān)的，否則，給定的信息位與編出的碼組就不是一一對(duì)應(yīng)的。 在循環(huán)碼中，一個(gè) (n,k)碼有 k2 個(gè)不同碼組。若用 g(x)表示其中前 (k1)位循環(huán)碼的數(shù)據(jù)容錯(cuò) 第二章 課題理論介紹 9 皆為“ 0”的碼組，則 )(,),(),(),( 12 xgxxgxxxgxg k ??都是碼組，而且這 k 個(gè)碼組是線性無(wú)關(guān)的。因此它們可以用來(lái)構(gòu)成此循環(huán)碼的生成矩陣 G。 在循環(huán)碼中除全“ 0”碼組外，再?zèng)]有連續(xù) k 位均為“ 0”的碼組，即連“ 0”的長(zhǎng)度最多只能為 (k1)位 [2]。否則，在經(jīng)過(guò)若干次循環(huán)移們后將得到一個(gè) k 個(gè)信息位全為“ 0”，但監(jiān)督位不全為“ 0”的碼組，這在線性碼中顯然是不可能的。因此 g(x)必須是一個(gè)常數(shù)項(xiàng)不為“ 0” 的 (nk)次多項(xiàng)式，而且，這個(gè) g(x)還是這種 (n,k)碼中次數(shù)為 (nk)的唯一的一個(gè)多項(xiàng)式。因?yàn)槿绻袃蓚€(gè)，則由碼的封閉性，把這兩個(gè)相加也應(yīng)該是一個(gè)碼組，且此碼組多項(xiàng)式的次將小于 (nk)，即連續(xù)“ 0”的個(gè)數(shù)多于 (k1)。顯然，這是與前面的結(jié)論矛盾的，故是不可能的。我們稱這唯一的 (nk)次多項(xiàng)式 g(x)為碼的生成多項(xiàng)式。一量確定了 g(x)，則整個(gè) (n,k)循環(huán)碼就被確定了 [2]。 因此，循環(huán)碼的生成矩陣 G可以寫(xiě)成 ?????????????????????)()()()()(21xgxxgxgxxgxxGkk? 公式 () 例如，在表 所給出的循環(huán)碼中， n=7,k=3,nk=4?？梢?jiàn)，唯一的一個(gè) (nk)=4次碼多項(xiàng)式代表的碼組是第二碼組 0010111，相對(duì)應(yīng)的碼多項(xiàng)項(xiàng)式（即生成多項(xiàng)式） 1)( 24 ???? xxxxg 將此 g(x)代入上式，得到 ???????????)()()()(2xgxxgxgxxG 公式 () 或 ???????????0010 1110101 1101011 100)(xG 公式 () 由于上式不符合公式 ()所示的 ? ?QIG k? 形式，所以此生成矩陣不是典型的。不過(guò)，將矩陣作線性變換，不難化成典型陣。 類似公式 ()，我們可以寫(xiě)出此循環(huán)碼組，即 循環(huán)碼的數(shù)據(jù)容錯(cuò) 第二章 課題理論介紹 10 ? ? ? ? ???????????????? )()()()()()()()( 45262456456 xgaxxgaxgxaxgxxgxgxaaaxGaaaxT )()( 4526 xgaxaxa ??? 公式 () 公式 ()表明，所有碼多項(xiàng)式 T(x)都可被 g(x)整除，而且任一次數(shù)不大于 (k1)的多項(xiàng)式乘 g(x)都是碼多項(xiàng)式。 環(huán)碼的生成多項(xiàng)式 由公式 ()可知，任一循環(huán)碼多項(xiàng)式 T(x)都是 g(x)的倍式，故可以寫(xiě)成 )()()( xgxhxT ?? 公式 () 而生成多項(xiàng)式 g(x)本身也是一個(gè)碼組，即有 )()(39。 xgxT ? 公式 () 由于碼組 )(39。 xT 為一 )( kn? 次多項(xiàng)式，故 )(39。 xTxk 為一 n次多項(xiàng)式。由公式 ()可知， )(39。 xTxk 在模 )1( ?nx 運(yùn)算下亦為一碼組，故可以寫(xiě)成 1)()(1 )(39。 ???? nnk x xTxQx xTx 公式 () 上式左端分子和分母都是 n次多項(xiàng)式，故商式 Q(x)=1，因此，上式可化成 )()1()(39。 xTxxTx nk ??? 公式 () 將公式 ()和公式 ()代入上式，并化簡(jiǎn)后可得 ? ?)()(1 xhxxgx kn ??? 公式 () 公式 ()表明，生成多項(xiàng)式 g(x)應(yīng)該是 ( 1?nx )的一個(gè)因式