循環(huán)碼的數(shù)據(jù)容錯畢業(yè)論文.doc

畢業(yè)論文（設(shè)計）題 目：循環(huán)碼的數(shù)據(jù)容錯 循環(huán)碼的數(shù)據(jù)容錯目錄畢業(yè)設(shè)計（論文）原創(chuàng)性聲明和使用授權(quán)說明原創(chuàng)性聲明本人鄭重承諾：所呈交的畢業(yè)設(shè)計（論文），是我個人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。盡我所知，除文中特別加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機(jī)構(gòu)的學(xué)位或?qū)W歷而使用過的材料。對本研究提供過幫助和做出過貢獻(xiàn)的個人或集體，均已在文中作了明確的說明并表示了謝意。作 者 簽 名： 日 期： 指導(dǎo)教師簽名： 日期： 使用授權(quán)說明本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計（論文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計（論文）的印刷本和電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)?？梢圆捎糜坝?、縮印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)校可以公布論文的部分或全部內(nèi)容。作者簽名： 日 期： 學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的研究成果。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫的成果作品。對本文的研究做出重要貢獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。本人完全意識到本聲明的法律后果由本人承擔(dān)。作者簽名： 日期： 年 月 日學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán) 大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。涉密論文按學(xué)校規(guī)定處理。作者簽名：日期： 年 月 日導(dǎo)師簽名： 日期： 年 月 日目錄摘要1ABSTRACT2第一章 循環(huán)碼容錯概述31.1課題研究的目的和意義31.2課題在國內(nèi)外的發(fā)展情況41.2.1單片機(jī)應(yīng)用41.2.2網(wǎng)絡(luò)應(yīng)用4第二章 課題理論介紹62.1循環(huán)碼編碼原理62.2循環(huán)碼的按模運(yùn)算72.3循環(huán)碼的生成矩陣82.4循環(huán)碼的生成多項(xiàng)式10第三章 循環(huán)碼容錯系統(tǒng)需求分析123.1循環(huán)碼內(nèi)部容錯123.1.1參數(shù)n、k的輸入133.1.2生成矩陣G(x)的獲得131.生成多項(xiàng)式的獲得132.生成多項(xiàng)式的選擇143.生成矩陣的生成153.1.3輸出碼組的生成163.1.4錯碼的產(chǎn)生及內(nèi)部容錯進(jìn)行糾正171.干擾串的輸入172.余數(shù)串的獲得173.錯碼串的顯示174.錯碼的內(nèi)部容錯糾正183.2循環(huán)碼相互容錯18第四章 循環(huán)碼容錯系統(tǒng)詳細(xì)設(shè)計204.1開發(fā)環(huán)境說明204.2詳細(xì)設(shè)計204.2.1參數(shù)輸入設(shè)計201.算法實(shí)現(xiàn)202.算法說明204.2.2生成矩陣的設(shè)計201.生成多項(xiàng)式的獲得202.生成矩陣的生成214.2.3生成碼組設(shè)計221.算法實(shí)現(xiàn)222.算法說明234.2.4錯碼的產(chǎn)生及內(nèi)部容錯進(jìn)行糾正231.余數(shù)串的獲得232.內(nèi)部容錯糾正錯碼23I4.2.5相互容錯糾正錯碼241.check()函數(shù)242.bFinalData事件觸發(fā)25第五章 具體實(shí)現(xiàn)及運(yùn)行結(jié)果275.1 循環(huán)碼內(nèi)部容錯285.1.1參數(shù)輸入部分285.1.2生成多項(xiàng)式的獲得295.1.3生成矩陣的獲得295.1.4編碼輸出305.1.5干擾示例305.1.6內(nèi)部容錯糾正315.2 循環(huán)碼相互容錯315.2.1數(shù)據(jù)的錄入315.2.2相互容錯干擾單個數(shù)據(jù)325.2.3相互容錯干擾多個數(shù)據(jù)33第六章 總結(jié)35第七章 致謝37參考文獻(xiàn)38II循環(huán)碼的數(shù)據(jù)容錯摘要摘要在線性分組碼中，有一種重要的碼稱為循環(huán)碼。這種碼的編碼和解碼設(shè)備都不太復(fù)雜，且檢（糾）錯的能力較強(qiáng)。循環(huán)碼具有循環(huán)性，任一碼組循環(huán)一位以后，仍為該碼中的一個碼組。對于傳輸中造成的錯誤，通過查表對比錯誤圖樣的方法，可以很容易地找出錯碼的所在，并將它糾正。鑒于循環(huán)碼的這些優(yōu)勢，目前它在理論上和實(shí)踐中都有較大的發(fā)展。 本文主要介紹，通過循環(huán)碼的編碼，提高了數(shù)據(jù)的可靠性和有效性。在循環(huán)碼的具體實(shí)現(xiàn)上，設(shè)計了自己的算法，實(shí)現(xiàn)了循環(huán)碼的生成、編碼、干擾和糾錯，既體現(xiàn)了循環(huán)碼作為線性分組碼的一般特性，又表現(xiàn)了其可循環(huán)的特殊性。這改善了數(shù)據(jù)在不可靠信道中傳輸信息得不到保證的問題，完成數(shù)據(jù)的在不可靠信道的有效傳輸，驗(yàn)證了循環(huán)碼編碼的重要性。關(guān)鍵字：循環(huán)碼，封閉，糾錯ABSTRACTAmong all those Linear-Block Codes, there is an important one which is called Cyclical Code. This kind of code only requires relatively simple Encoding and Decoding devices, but can provide a truly exceptional error-correcting ability. This so-called Cyclical Code has the ability of cycling, that each legal code block would turn into another legal one by cyclical-moving one single position. However, in order to recorrect the mistakes during the transporting process, we need a Mistake-Graphics Table to make sure where the mistake really is, and then make it right again. With all these advantages, Cyclical Code currently becomes a new and fast-moving technology both theoretically and practically. This paper introduces that, after the encoding process by the Cyclical Code, boyh the reliability and validity of data have been proved. As for the realization part of the cyclic code, Some algorithms have been designed to achieve the formation, encoding, interference and error correction of Cyclical Code, not only show those general characteristics of Linear-Block Codes, but also demonstrat its unique recyclability. This process improves the problems during the data transmitting process, which might be caused when transmitted through unreliable data channel, completes the process of reliable data-transmitting through unreliable data channel, reassures the importance of Cyclical Code Encoding.KEY WORDS- Cyclical Code, Incapsulating, Error-Correcting39循環(huán)碼的數(shù)據(jù)容錯第一章 循環(huán)碼容錯概述第一章 循環(huán)碼容錯概述本章主要介紹了數(shù)據(jù)容錯技術(shù)的背景及意義，并且討論了該技術(shù)的現(xiàn)狀和發(fā)展前景，就此提出問題并確定目標(biāo)，最后就開發(fā)此系統(tǒng)所要用到的相關(guān)技術(shù)作簡要的說明。1.1課題研究的目的和意義由于數(shù)字信號在傳輸過程中受到干擾的影響，使信號碼元波形變壞，故傳輸?shù)浇邮斩撕罂赡馨l(fā)生錯誤判決。由信道中乘性干擾引起的碼間干擾，通?？梢圆捎镁獾霓k法糾正，而加性干擾的影響則要從其他途徑解決。通常，在設(shè)計數(shù)字通信系統(tǒng)時，首先應(yīng)從合理地選擇調(diào)制制度、解調(diào)方法以及發(fā)送功率等方面考慮。若采取上述措施仍難以滿足要求，則就要考慮采用差錯控制措施。在隨機(jī)信道中，錯碼的出現(xiàn)是隨機(jī)的，且錯碼之間是統(tǒng)計獨(dú)立的6。例如，由正態(tài)分布白噪聲引起的錯碼就具有這種性質(zhì)。因此，當(dāng)信道中加性干擾主要是這種噪聲時，就稱這種信道為隨機(jī)信道。在突發(fā)信道中，錯碼是成串集中出現(xiàn)的，也就是說，在一些短促的時間區(qū)間內(nèi)會出現(xiàn)大量錯碼，面在這些短促的時間區(qū)間之間卻又存在較長的無錯碼區(qū)間。對于不同類型的信道，應(yīng)采用不同的差錯控制技術(shù)。在實(shí)際應(yīng)用中，數(shù)據(jù)傳輸一般采用系統(tǒng)碼的編碼方式，即在發(fā)送的信息序列之后附加上特定位數(shù)序列的冗余位，該冗余位稱為所發(fā)送的信息序列的監(jiān)督位。監(jiān)督位一般是由所發(fā)送的信息序列經(jīng)過恰當(dāng)?shù)淖兓a(chǎn)生。若監(jiān)督位由信息序列經(jīng)過線性組合得到，則稱得到的碼為線性分組碼。循環(huán)碼是線性分組碼的一個重要子類，具有嚴(yán)密的代數(shù)學(xué)理論2。循環(huán)碼“線性”是指任意兩個循環(huán)碼模2相加所得的新碼仍為循環(huán)碼。循環(huán)碼具有線性碼的一般性質(zhì)（即封閉性，指一種線性分組碼的任意兩個碼組這和仍是該分組碼的另一個碼組）外，還具有循環(huán)性，即循環(huán)碼中任一碼組循環(huán)一位（將最右端碼元移至左端，或反之）以后，仍為該碼組中的一個碼組。（n，k）循環(huán)碼表示其中信息位為k，監(jiān)督位為n-k位。1.2課題在國內(nèi)外的發(fā)展情況本節(jié)介紹相關(guān)技術(shù)在國內(nèi)外的己有的發(fā)展。1.2.1單片機(jī)應(yīng)用循環(huán)碼為信道編碼，具有很強(qiáng)的糾、檢錯功能，它是建立在嚴(yán)密的數(shù)學(xué)理論基礎(chǔ)之上8。循環(huán)碼具有固定的代數(shù)結(jié)構(gòu)，可以用線性反饋移位寄存器實(shí)現(xiàn)編譯碼電路，所以可以找到很多簡單的編譯碼方法，目前在數(shù)據(jù)通信上特別是在衛(wèi)星通信中循環(huán)碼得到了廣泛應(yīng)用。近年來隨著計算機(jī)軟件的飛速發(fā)展，許多用實(shí)物實(shí)現(xiàn)的問題都可以在軟件上得以實(shí)現(xiàn)。單片機(jī)就是軟件發(fā)展的杰出產(chǎn)物。單片機(jī)具有內(nèi)部資源豐富，性能全面，通用性強(qiáng)，可覆蓋多種應(yīng)用要求的優(yōu)點(diǎn)4?；趩纹瑱C(jī)設(shè)計的電路十分廣泛的應(yīng)用在當(dāng)今的各個領(lǐng)域中。以往循環(huán)碼編譯碼電路大多用移位寄存器和模2和構(gòu)成的線性時序網(wǎng)絡(luò)來完成?；倦娐泛唵?，容易實(shí)現(xiàn)。但在體積和功能的擴(kuò)展上受到了限制而不能發(fā)揮更大作用。使用軟件編程方法實(shí)現(xiàn)編譯碼過程既有簡化電路，可靠性高、運(yùn)算速度快、體積小等優(yōu)點(diǎn)，又可以擴(kuò)展電路其它功能9。而且可以根據(jù)具體要求任意修改，這是其它硬件電路所無法相比的。是拋開傳統(tǒng)模式的一種新的嘗試。在由單片機(jī)組成的遙測、遙控系統(tǒng)中，大多數(shù)直接利用單片機(jī)的串行通信功能進(jìn)行數(shù)據(jù)的傳輸和控制。然而在實(shí)際通信過程中，大量的隨機(jī)干擾嚴(yán)重影響了數(shù)據(jù)傳輸?shù)臏?zhǔn)確性，破壞了系統(tǒng)的穩(wěn)定性，使串行通信的誤碼率大到了不可容忍的程度。因此，有前人針對信道對于數(shù)據(jù)傳輸?shù)挠绊?，提出了基于單片機(jī)MCS-52單片機(jī)系統(tǒng)的軟件糾錯編碼、譯碼方案，并詳細(xì)介紹了其實(shí)現(xiàn)方法。1.2.2網(wǎng)絡(luò)應(yīng)用在網(wǎng)絡(luò)編碼中，還有一種稱為CRC，即循環(huán)冗余校驗(yàn)碼的多項(xiàng)式編碼，這種編碼的基本思想是：將位串看成是系數(shù)為0或1的多項(xiàng)式。一個k位的幀看作是一個k-1次多項(xiàng)式的系數(shù)列表，該多項(xiàng)式共有k項(xiàng)，從到。這樣的多項(xiàng)式認(rèn)為是k-1階多項(xiàng)式。高次（最左邊）位是項(xiàng)的系數(shù)：接下去的位是項(xiàng)的系數(shù)；依此類推3。例如，110001有6位，因此代表了一個共有6項(xiàng)的多項(xiàng)式，其系數(shù)為1、1、0、0、0和1 ，即。多項(xiàng)式的算術(shù)運(yùn)算采用代數(shù)域理論的規(guī)則，以2為模來完成。加法沒有進(jìn)位，減法沒有借位。加法和減法都等同于異或9。當(dāng)使用多項(xiàng)式編碼時，發(fā)送方和接收方必須預(yù)先商定一個生成多項(xiàng)式1。生成多項(xiàng)的最高位和最低位必須是1。假設(shè)一幀有m位，它對應(yīng)于多項(xiàng)式M(x)，為了計算它的校驗(yàn)和，該幀必須比生成多項(xiàng)式長?；镜乃枷胧窃趲奈膊孔芳右粋€校驗(yàn)和，使得追加這后的幀所對應(yīng)的多項(xiàng)式能夠被G(x)除盡。當(dāng)接收方收到了帶校驗(yàn)和的幀之后，它方式著用G(x)去除它。如果有余數(shù)的話，則表明傳輸過程中有錯誤5。循環(huán)碼的數(shù)據(jù)容錯第二章 課題理論介紹第二章 課題理論介紹本章主要介紹循環(huán)碼的相關(guān)理論依據(jù)及原理。2.1循環(huán)碼編碼原理在線性分組碼中，有一種重要的碼稱為循環(huán)碼。它是在嚴(yán)密的代數(shù)學(xué)理論基礎(chǔ)上建立起來的。這種碼的編碼和解碼設(shè)備都不太復(fù)雜，且檢（糾）錯的能力較強(qiáng)，目前在理論上和實(shí)踐上都有了較大的發(fā)展。循環(huán)碼除了具有線性碼的一般性質(zhì)外，還具有循環(huán)性，即循環(huán)碼中任一碼組循環(huán)一位（將最右端的碼元移至左端，或反之）以后，仍為該碼中的一個碼組。在表2.1中給出一種（7，3）循環(huán)碼的全部碼組。由此表可以直觀看出這種碼的循環(huán)性。例如，表2.1中的第2碼組向右移一位即得到第5碼組；第5碼組向右移一位即得到第7碼組。一般來說，若()是一個循環(huán)碼組，則表2.1碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位1234000001010011000001111110100156781001011101111011110001010010()()()也是該編碼中的碼組。在代數(shù)編碼理論中，為了便于計算，把這樣的碼組中各碼元當(dāng)作是一個多項(xiàng)式的系數(shù)，即把一個長度為n的碼組表示成 公式(2.1)表2.1中的任一碼組可以表示為 公式(2.2)例如，表中的第7組可以表示為公式(2.3)這種多項(xiàng)式中，x僅是碼元位置的標(biāo)記，例如上式表示第7碼組中、和為“1”，其他均為零。因此我們并不關(guān)心的取值。這種多項(xiàng)式有時稱為碼多項(xiàng)式。2.2循環(huán)碼的按模運(yùn)算在整數(shù)運(yùn)算中，有模n運(yùn)算。例如，在模2運(yùn)算中，有1+1=20（模2），1+2=31（模2），2*3=60（模2）等。一般來說，若一整數(shù)m可以表示為 公式(2.4)式中Q整數(shù)。則在模n運(yùn)算下，有(模) 公式(2.5)這就是說，在模n運(yùn)算下，一整數(shù)m等于其被n除得這余數(shù)。在碼多項(xiàng)式運(yùn)算中也有類似的按模運(yùn)算。若一任意多項(xiàng)式F(x)被一n次多項(xiàng)式N(x)除，得到商式Q(x)和一個次數(shù)小于n的余式R(x)，即 公式(2.6)則寫為(模) 公式(2.7)這時，碼多項(xiàng)式系數(shù)仍按模2運(yùn)算，即只取值0和1。例如，被()除得余項(xiàng)1，所以有 (模) 公式(2.8)同理(模) 公式(2.9)因?yàn)?注意，由于在模2運(yùn)算中，用加法代替了減法，故余項(xiàng)不是，是。在循環(huán)碼中，若是一個長為n的許用碼組，則在按模運(yùn)算下，亦是一個許用碼組，即若(模) 公式(2.10)則也是一個許用碼組。其證時是很簡單的，因?yàn)槿?公式(2.11)則 公式(2.12)所以這時有 公式(2.13)公式(2.13)中正是公式(2.11)中代表的碼組向左循環(huán)移位i次的結(jié)果。因?yàn)樵鸭俣橐谎h(huán)碼，所以也必為該碼中一個碼組。例如，式(2.3)中循環(huán)碼其碼長n=7。現(xiàn)給定i=3，則公式(2.14)其對應(yīng)的碼組為0101110，它正是表9-6中第3碼組。由上述分析可見，一個長為n的循環(huán)碼，它必為按模()運(yùn)算的一個余式。2.3循環(huán)碼的生成矩陣根據(jù)線性碼的性質(zhì)可知，有了生成矩陣G，就可以由k個信息位得出整個碼組，而且生成矩陣G的每一行都是一個碼組5。例如，在式(2.17)中，若，則碼組A就等于G的第一行；若，則碼組A就等于G的第二行，等等。由于G是k行n列矩陣，因此，若能找到k個已知碼組，就能構(gòu)成矩陣G。如前所述，這k個已知碼組必須是線性不相關(guān)的，否則，給定的信息位與編出的碼組就不是一一對應(yīng)的。在循環(huán)碼中，一個(n,k)碼有個不同碼組。若用g(x)表示其中前(k-1)位皆為“0”的碼組，則都是碼組，而且這k個碼組是線性無關(guān)的。因此它們可以用來構(gòu)成此循環(huán)碼的生成矩陣G。在循環(huán)碼中除全“0”碼組外，再沒有連續(xù)k位均為“0”的碼組，即連“0”的長度最多只能為(k-1)位2。否則，在經(jīng)過若干次循環(huán)移們后將得到一個k個信息位全為“0”，但監(jiān)督位不全為“0”的碼組，這在線性碼中顯然是不可能的。因此g(x)必須是一個常數(shù)項(xiàng)不為“0”的(n-k)次多項(xiàng)式，而且，這個g(x)還是這種(n,k)碼中次數(shù)為(n-k)的唯一的一個多項(xiàng)式。因?yàn)槿绻袃蓚€，則由碼的封閉性，把這兩個相加也應(yīng)該是一個碼組，且此碼組多項(xiàng)式的次將小于(n-k)，即連續(xù)“0”的個數(shù)多于(k-1)。顯然，這是與前面的結(jié)論矛盾的，故是不可能的。我們稱這唯一的(n-k)次多項(xiàng)式g(x)為碼的生成多項(xiàng)式。一量確定了g(x)，則整個(n,k)循環(huán)碼就被確定了2。因此，循環(huán)碼的生成矩陣G可以寫成 公式(2.15)例如，在表2.1所給出的循環(huán)碼中，n=7,k=3,n-k=4?？梢姡ㄒ坏囊粋€(n-k)=4次碼多項(xiàng)式代表的碼組是第二碼組0010111，相對應(yīng)的碼多項(xiàng)項(xiàng)式（即生成多項(xiàng)式）將此g(x)代入上式，得到 公式(2.16)或 公式(2.17)由于上式不符合公式(2.15)所示的形式，所以此生成矩陣不是典型的。不過，將矩陣作線性變換，不難化成典型陣。類似公式(2.17)，我們可以寫出此循環(huán)碼組，即 公式(2.18)公式(2.18)表明，所有碼多項(xiàng)式T(x)都可被g(x)整除，而且任一次數(shù)不大于(k-1)的多項(xiàng)式乘g(x)都是碼多項(xiàng)式。2.4循環(huán)碼的生成多項(xiàng)式由公式(2.18)可知，任一循環(huán)碼多項(xiàng)式T(x)都是g(x)的倍式，故可以寫成 公式(2.19)而生成多項(xiàng)式g(x)本身也是一個碼組，即有 公式(2.20)由于碼組為一次多項(xiàng)式，故為一n次多項(xiàng)式。由公式(2.10)可知，在模運(yùn)算下亦為一碼組，故可以寫成 公式(2.21)上式左端分子和分母都是n次多項(xiàng)式，故商式Q(x)=1，因此，上式可化成 公式(2.22)將公式(2.19)和公式(2.20)代入上式，并化簡后可得 公式(2.23)公式(2.23)表明，生成多項(xiàng)式g(x)應(yīng)該是()的一個因式。這一結(jié)論為我們尋找循環(huán)碼的生成多項(xiàng)式指出了一條道路，即循環(huán)碼的生成多項(xiàng)式應(yīng)該是()的一個()次因式。例如，可以分解為 公式(2.24)為了求(7,3)循環(huán)碼的生成多項(xiàng)式g(x)，要從上式中找到一個(n,k)=4次的因子。不難看出，這樣的因子有兩個，即 公式(2.25) 公式(2.26)以上兩式都可作為生成多項(xiàng)式用。不過，選用的生成多項(xiàng)式不同，產(chǎn)生出的循環(huán)碼組也不同。用公式(2.25)作為生成多項(xiàng)式產(chǎn)生的循環(huán)碼即為表2.1所列。循環(huán)碼的數(shù)據(jù)容錯第三章 循環(huán)碼容錯系統(tǒng)需求分析第三章 循環(huán)碼容錯系統(tǒng)需求分析本章主要介紹本次設(shè)計需要完成的工作及初步系統(tǒng)設(shè)計。分循環(huán)碼內(nèi)部容錯和循環(huán)碼相互容錯兩部分。3.1循環(huán)碼內(nèi)部容錯對于循環(huán)碼的實(shí)際應(yīng)用，前人做過很多的嘗試。但在本次設(shè)計中，無法將所有前人的工作全部實(shí)現(xiàn)。我要做的工作是，實(shí)現(xiàn)循環(huán)碼的生成過程，輸出碼組，并采用內(nèi)部容錯和相互容錯兩種方式對錯誤的數(shù)據(jù)進(jìn)行糾正。工作如下：a.參數(shù)n、k由人工輸入，可自動判斷是否正確；b.依據(jù)因式分解，自行產(chǎn)生G；c.對于任意給定的輸入碼組，可產(chǎn)生正確的輸出碼組；d.對于任意給定的輸入碼組，可檢糾錯；e. 基于循環(huán)碼的數(shù)據(jù)容錯，采用內(nèi)部容錯、相互容錯兩種模式。開始輸入n,kn,k合乎標(biāo)準(zhǔn)得到生成矩陣產(chǎn)生碼組結(jié)束YN圖3.1 整體流程圖接下來，我將按照設(shè)計方案的設(shè)計順序依次說明。3.1.1參數(shù)n、k的輸入此模塊內(nèi)部又包括兩個部分。一是數(shù)據(jù)輸入部分，負(fù)責(zé)數(shù)據(jù)的接收；二是數(shù)據(jù)判斷部分，負(fù)責(zé)斷判輸入數(shù)據(jù)是否合理，如果合理，直接進(jìn)行下面部分，如果不合理，要重新輸入，并繼續(xù)判斷。輸入部分要求輸入兩個數(shù)據(jù)n和k，n是循環(huán)碼的總碼長，k是碼中信息位的長度。通過計算，得到監(jiān)督位數(shù)為r=n-k。判斷依據(jù)是或，如果此式成立，則n，k符合要求，可以繼續(xù)進(jìn)行下面的操作；如果此式不成立，則要重新輸入。流程圖如下：開始輸入n,kn,k合乎標(biāo)準(zhǔn)YN結(jié)束圖3.2 輸入部分流程圖3.1.2生成矩陣G(x)的獲得然而，要得到生成矩陣G(x)，首先要得到的是生成多項(xiàng)式g(x)。每一個生成矩陣G(x)和其生成多項(xiàng)式g(x)是一一對應(yīng)的關(guān)系，也就是說，有一個生成多項(xiàng)式，就有一個對應(yīng)的生成矩陣。因此，我們要先想辦法得到生成矩陣。對于每一組符合條件的n，k組合，它們可以得到的生成多項(xiàng)式可能不是唯一的。因此，我們要把符合條件的生成多項(xiàng)式全部列出來供人選擇。這個模塊包括三個部分。一部分是生成多項(xiàng)式的獲得；一部分是從生成的眾多生成多項(xiàng)式中選擇一個進(jìn)行下面的操作；一部分是根據(jù)所選生成多項(xiàng)式生成相應(yīng)的生成矩陣。其中最重要的是第一部分，生成多項(xiàng)式的生成。1.生成多項(xiàng)式的獲得為了解釋方便，我們這里取n=7，k=3的n,k組合進(jìn)行解釋。若要得到(7,3)循環(huán)碼的生成多項(xiàng)g(x)，由2.1節(jié)的理論介紹，我們知道，就需要找到的次因子，而這種多項(xiàng)式除最高次項(xiàng)項(xiàng)和最低次項(xiàng)項(xiàng)的系數(shù)不能為0外，其它項(xiàng)的系數(shù)均可以為0。因此，所有可能符合條件的這種多項(xiàng)式共有個。我們下面的工作就是在這8個可能符合條件的多項(xiàng)式中篩選出真正符合條件的備選生成多項(xiàng)式。要找到的次因子，其中一個可行的辦法就是用去依次除上面提到的8個多項(xiàng)式，判斷余數(shù)，如果有余數(shù)，也就是說所得到的不余數(shù)為0，那這個多項(xiàng)式不符合條件；相反，如果沒有余數(shù)，也就是說所得到的余數(shù)為0，那這個多項(xiàng)式符合條件，可以作為備選的生成多項(xiàng)式。流程圖如下：開始i=0itotali+rem.n=0列入備選NNYY結(jié)束 圖3.3獲得生成多項(xiàng)式流程圖2.生成多項(xiàng)式的選擇從上一步生成的備選生成多項(xiàng)式中選擇一個進(jìn)行下面的步驟。選擇的方式為1、2、3 。經(jīng)過此步驟后，會有一個生成多項(xiàng)式被出選出，這個生成多項(xiàng)式的長度n為n-k+1。3.生成矩陣的生成根據(jù)上一步的選擇，生成相應(yīng)的生成矩陣。具體做法就是，先在所選生成多項(xiàng)式的前面加上(k-1)個0，也就是先把它的長度變?yōu)閚。然后將這個得到的多項(xiàng)式進(jìn)行移位操作，并且把每一次移位的結(jié)果都記錄下來。從這n個多項(xiàng)式中選出k個符合條件的多項(xiàng)式構(gòu)成生成矩陣G(x)，條件是使得這k個式子的前三列能夠組成k*k的單位方陣。流程圖如下：開始i=0jtem.nnj=tem.n-tem.ktem=leftSlip(dividercho-1,i);i=n) return true;else return false;2.算法說明此函數(shù)用來判斷所輸入的n和k是否合理。判斷的依據(jù)就是在2.2.1中提到的。4.2.2生成矩陣的設(shè)計1.生成多項(xiàng)式的獲得(1)算法實(shí)現(xiàn)for(int i=0;itotal;i+)Tx rem=new Tx();System.out.println(formula.n+formula.n);System.out.println(divideri.n+divideri.n);rem=getRemainder(formula,divideri);if(rem.n=0)String tem;dividerk=divideri;dividerk.chooseable=1;tem=String.valueOf(dividerk.content);tem=tem.substring(0,dividerk.n);tagx.append(tem+n);k+;(2)算法說明這一部分是這個整序的核心。生成多項(xiàng)式的生成影響到所有后面步驟的運(yùn)行。在這部分代碼的最開始，我先定義了一個rem對象，用它來存儲后面兩個多項(xiàng)式相除后所得到的余數(shù)。這個rem也就成我們判斷某一個divider是否合理的依據(jù)。如果這個rem的長度是0，那這個divider就是符合要求的多項(xiàng)式，我們要將它作為候選的生成多項(xiàng)式來對待。對于這個取余數(shù)的操作，我是這樣來定義的。Tx getRemainder(Tx dividend,Tx divider)Tx result=new Tx();if(dividend.ndivider.n)result.setN(dividend.n);result.setK(dividend.k);for(int i=0;iresult.n;i+) result.contenti=dividend.contenti;else result=getRemainder(divide2(dividend,divider),divider);return result;采用“分治”的思想，通過divide2(Tx dividend,Tx divider)這個函數(shù)，每次都對傳來的兩個多項(xiàng)式進(jìn)行一次“模2”的操作，直到最后得到的結(jié)果的長度比divider小為止，才算結(jié)束。這時，我們再去判斷rem，如果這個rem的長度是0，那這個divider就是符合要求的多項(xiàng)式，我們要將它作為候選的生成多項(xiàng)式來對待。2.生成矩陣的生成(1)算法實(shí)現(xiàn)if(dividercho-1.chooseable=1)gxx.setN(dividercho-1.n);gxx.setK(dividercho-1.k);for(int i=0;igxx.n;i+)gxx.contenti=dividercho-1.contenti;dividercho-1.setN(formula.n-1);dividercho-1.setK(formula.k);for(int i=0;idividercho-1.n;i+)tem=leftSlip(dividercho-1,i);for(int j=tem.n-tem.k;jtem.n;j+)if(tem.contentj=1)len+;tem.gxsitio=j;if(len=1) gxtem.n-tem.gxsitio-1=tem;len=0;(2)算法說明如果一個備選的生成多項(xiàng)式被選擇，那它的被選標(biāo)志chooseable就會被置1。這時，我們用另外一個對象gxx來代替原來的divider進(jìn)行下面的操作，把gxx的參數(shù)全部置為選出的divider的參數(shù)。下面要進(jìn)行的操作是把這個gxx作移位，每次左移一位，共移n次，并且把每一次移位的結(jié)果都記錄下來。具體作法是，從每一個多項(xiàng)式的第n-k+1位起開始檢查，一直檢查到第n位，這樣的話，總共有k位數(shù)據(jù)被檢查過。判斷這k個數(shù)據(jù)中1的個數(shù)只有一個，那這一項(xiàng)將被選出來，作為生成矩陣G(x)的一行。以上步驟進(jìn)行完之后，將會有k項(xiàng)被選出來，這k個符合條件的多項(xiàng)式構(gòu)成生成矩陣G(x)，并按使得這k個式子的前三列能夠組成k*k的單位方陣的順序?qū)⑺鼈兣帕袠?gòu)成生成矩陣G(x)。4.2.3生成碼組設(shè)計1.算法實(shí)現(xiàn)for(int i=0;ioutput.n;i+)for(int j=0;joutput.k;j+)if(input.contentj=1&input.contentj=gxj.contenti) tem+;if(tem%2=1) output.contenti=1;else output.contenti=0;tem=0;2.算法說明這部分代碼完成的工作是把輸入的長度為k的純信息位碼轉(zhuǎn)化為長度為n的加上監(jiān)督位的碼。從計算上來說，就是用1行k列的輸入碼乘以k行n列的生成矩陣G(x)。4.2.4錯碼的產(chǎn)生及內(nèi)部容錯進(jìn)行糾正1.余數(shù)串的獲得(1)算法實(shí)現(xiàn)for(int i=0;ioutput.n;i+)Rx.contenti=output.contenti;if(Rx.contenti=tfInterrupt.getText().charAt(i)Rx.contenti=0;else Rx.contenti=1;rx=getRemainder(Rx,gxx);str=String.valueOf(rx.content);str=str.substring(0,Rx.n-Rx.k);labRemainder.setText(str);(2)算法說明這部分代碼的核心還是運(yùn)用