基于bch碼的快閃存儲(chǔ)器控制器設(shè)計(jì)bch（含外文翻譯）

1、<p>　　畢 業(yè) 論 文（設(shè) 計(jì)）</p><p><b>　　論文（設(shè)計(jì)）題目：</b></p><p>　　快閃存儲(chǔ)器控制器設(shè)計(jì)</p><p>　　姓 名 </p><p>　　學(xué) 號(hào) </p><p>　　學(xué) 院

2、 </p><p><b>　　專 業(yè) </b></p><p>　　年 級(jí) </p><p>　　指導(dǎo)老師 </p><p>　　2012年 5 月 4 日</p><p><b>　　目錄</b&

3、gt;</p><p><b>　　目錄1</b></p><p><b>　　摘要3</b></p><p>　　Abstract4</p><p><b>　　第1章 引言5</b></p><p>　　1.1 快閃存儲(chǔ)器簡介5<

4、/p><p>　　1.2 閃存中的糾錯(cuò)碼（ECC）技術(shù)5</p><p>　　1.3 論文的研究內(nèi)容與組織結(jié)構(gòu)6</p><p>　　第2章 ECC整體設(shè)計(jì)8</p><p>　　2.1 ECC簡介8</p><p>　　2.2 功能要求8</p><p>　　2.3 本章總結(jié)

5、10</p><p>　　第3章 BCH碼11</p><p>　　3.1 伽羅華域11</p><p>　　3.2 BCH碼的編碼13</p><p>　　3.3 BCH碼的解碼16</p><p>　　3.3.1 伴隨式的求解方法16</p><p>　　3.3.2

6、錯(cuò)誤位置多項(xiàng)式的高速求解法18</p><p>　　3.3.3 全并行錢氏搜索機(jī)20</p><p>　　3.4 本章總結(jié)21</p><p>　　第4章 BCH編解碼器的設(shè)計(jì)23</p><p>　　4.1 BCH編碼器23</p><p>　　4.2 BCH解碼器25</p>&

7、lt;p>　　4.2.1 伴隨式計(jì)算模塊26</p><p>　　4.2.2 錯(cuò)誤位置多項(xiàng)式計(jì)算模塊28</p><p>　　4.2.3 錢氏搜索機(jī)31</p><p>　　4.3 ECC模塊的驗(yàn)證32</p><p>　　4.4 本章總結(jié)33</p><p>　　第5章 總結(jié)35<

8、/p><p><b>　　謝辭36</b></p><p><b>　　參考文獻(xiàn)37</b></p><p>　　附錄A 英文翻譯原文39</p><p>　　附錄 B 譯文48</p><p><b>　　摘要</b></p>&

9、lt;p>　　論文對(duì)于 flash存儲(chǔ)器控制器的設(shè)計(jì)，主要是針對(duì)于其中的錯(cuò)誤檢查與糾錯(cuò)（ECC）模塊.ECC模塊是存儲(chǔ)器控制器的核心模塊，主要對(duì)輸入和輸出數(shù)據(jù)進(jìn)行編解碼并糾正其中的錯(cuò)誤。</p><p>　　本論文中的ECC模塊主要采用了BCH（15，7，2）碼。對(duì)于編碼采用了線性反饋電路移位寄存器的方法，對(duì)于解碼采用了三個(gè)模塊：伴隨式計(jì)算模塊、錯(cuò)誤位置多項(xiàng)式模塊和錢氏搜索機(jī)。BCH碼以其較強(qiáng)的糾錯(cuò)能力和構(gòu)

10、造方便的優(yōu)點(diǎn)，在無線尋呼和無線數(shù)據(jù)通信中被廣泛應(yīng)用。利用單片機(jī)用軟件的方法實(shí)現(xiàn)BCH（15，7，2）碼的ECC模塊很多資料都已經(jīng)介紹。但由于采用單片機(jī)以軟件的方法實(shí)現(xiàn)，其譯碼器具有速度慢、系統(tǒng)穩(wěn)定性差等缺點(diǎn)，本論文介紹了采用FPGA設(shè)計(jì)的采用BCH(15,7,2)碼的ECC模塊。先對(duì)ECC模塊進(jìn)行VHDL代碼的編寫，然后利用ALTERA的QUARTUS II集成開發(fā)環(huán)境進(jìn)行了綜合、仿真。采用硬件的方法實(shí)現(xiàn)的ECC模塊具有速度快、性能穩(wěn)定

11、以及易于大規(guī)模集成等優(yōu)點(diǎn)。</p><p>　　關(guān)鍵詞：快閃存儲(chǔ)器控制器；ECC模塊；BCH碼；FPGA；</p><p><b>　　Abstract</b></p><p>　　This thesis mainly introduced the module of the error correction code(ECC), which

12、is the most important module in the flash controller. The module of ECC can accomplish the event that encode the data-in and decode the data-out and correct the error data. </p><p>　　The module of ECC use th

13、e BCH(15,7,2) code in this thesis. For the encode, the module of linear feedback shift register can make it work. For the decode, it has three modules: finding polynomials, finding the coefficient of the error  loc

14、ator polynomial and chien. Because of its strong ability of correcting errors and convenient construction ,the BCH code is widely used in the radio paging and Wireless data communication. Much material has introduced t

15、he way of accomplishing the BCH(15,7,2) </p><p>　　Keywords: flash controller ; ECC ; BCH code ; FPGA</p><p><b>　　第1章 引言</b></p><p>　　1.1 快閃存儲(chǔ)器簡介</p><p>　

16、　在當(dāng)今數(shù)字技術(shù)飛速發(fā)展的時(shí)代，flash因其非易失性和可擦除性，以及具有更小的體積、更快的寫入和擦除速度、更多的可擦除次數(shù)以及更低廉的每比特價(jià)格等特點(diǎn)得到了迅速發(fā)展，在數(shù)碼相機(jī)、手機(jī)、移動(dòng)存儲(chǔ)卡、掌上電腦和MP3播放器等設(shè)備中得到廣泛的使用。</p><p>　　隨著flash單片存儲(chǔ)容量的不斷提升和當(dāng)前flash擦寫速度的不斷提高，數(shù)據(jù)存儲(chǔ)與讀取的可靠性變得越來越低，迫切需要一種實(shí)時(shí)、高速的技術(shù)對(duì)flash中

17、存儲(chǔ)和讀取的數(shù)據(jù)進(jìn)行糾錯(cuò)以保證數(shù)據(jù)的可靠性。</p><p>　　在flash的差錯(cuò)類型設(shè)計(jì)中錯(cuò)誤是以位的形式分散在整個(gè)數(shù)據(jù)塊中的，所以具有可控、隨機(jī)錯(cuò)誤糾錯(cuò)能力的BCH碼適用于flash的糾錯(cuò)。</p><p>　　目前大部分flash的PER為，為使PER低于這個(gè)行業(yè)安全標(biāo)準(zhǔn)，需要的糾錯(cuò)能力為15 bit左右。因此必須提高編碼譯碼器的糾錯(cuò)能力。</p><p>

18、　　1.2 閃存中的糾錯(cuò)碼（ECC）技術(shù)</p><p>　　ECC校驗(yàn)是一種內(nèi)存糾錯(cuò)技術(shù)，它是現(xiàn)在比較先進(jìn)的內(nèi)存錯(cuò)誤檢查和更正手段。ECC是“Error Checking and Correcting”的簡寫，中文名稱是“錯(cuò)誤檢查和糾正”。ECC是一種能夠?qū)崿F(xiàn)“錯(cuò)誤檢查和糾正”的技術(shù)，ECC內(nèi)存就是應(yīng)用了這種技術(shù)的內(nèi)存，一般多應(yīng)用在服務(wù)器及圖形工作站上，這將使整個(gè)電腦系統(tǒng)在工作時(shí)更加趨于安全穩(wěn)定。</p

19、><p>　　在ECC技術(shù)出現(xiàn)以前，內(nèi)存中應(yīng)用最多的是奇偶校驗(yàn)（Parity）。但Parity有個(gè)缺點(diǎn)，當(dāng)內(nèi)存查到某個(gè)數(shù)據(jù)有錯(cuò)誤時(shí)，并不一定能確定在哪一個(gè)位，也就不一定能修正錯(cuò)誤，所以帶有奇偶校驗(yàn)的內(nèi)存的主要功能僅僅是“發(fā)現(xiàn)錯(cuò)誤”，并能糾正部分簡單的錯(cuò)誤。</p><p>　　Parity內(nèi)存是通過在原來數(shù)據(jù)位的基礎(chǔ)上增加一個(gè)數(shù)據(jù)位來檢查當(dāng)前8位數(shù)據(jù)的正確性，但隨著數(shù)據(jù)位的增加Parity用來

20、檢驗(yàn)的數(shù)據(jù)位也成倍增加，就是說當(dāng)數(shù)據(jù)位為16位時(shí)它需要增加2位用于檢驗(yàn)，當(dāng)數(shù)據(jù)位為32位時(shí)則需增加4位，依此類推。特別是當(dāng)數(shù)據(jù)量非常大時(shí)，數(shù)據(jù)出錯(cuò)的幾率也就越大，對(duì)于只能糾正簡單錯(cuò)誤的奇偶檢驗(yàn)的方法就顯得力不從心了，因此出現(xiàn)了一種新的錯(cuò)誤檢查與糾正（ECC）技術(shù)，這種技術(shù)也是在原來的數(shù)據(jù)位上外加校驗(yàn)位來實(shí)現(xiàn)的。不同的是兩者增加的方法不一樣，這也就導(dǎo)致了兩者的主要功能不一樣。它與Parity不同的是如果數(shù)據(jù)位是8位，則需要增加5位來進(jìn)行E

21、CC錯(cuò)誤檢查和糾正，數(shù)據(jù)位每增加一倍，ECC只增加一位檢驗(yàn)位，也就是說當(dāng)數(shù)據(jù)位為16位時(shí)ECC位為6位，32位時(shí)ECC位為7位，數(shù)據(jù)位為64位時(shí)ECC位為8位，依此類推，數(shù)據(jù)位每增加一倍，ECC位只增加一位?？傊?，在內(nèi)存中ECC能夠容許錯(cuò)誤，并可以將錯(cuò)誤更正，使系統(tǒng)得以持續(xù)正常的操作，不致因錯(cuò)誤而中斷，且ECC具有自動(dòng)更正的能力。 </p><p>　　1.3 論文的研究內(nèi)容與組織結(jié)構(gòu)</p>&

22、lt;p>　　隨著快閃存儲(chǔ)器工藝技術(shù)的不斷進(jìn)步，快閃存儲(chǔ)器單元的可靠性嚴(yán)重下降，因此通過設(shè)計(jì)方法提高系統(tǒng)的可靠性變得愈加嚴(yán)重。糾錯(cuò)碼作為一種能夠有效提高系統(tǒng)可靠性的技術(shù)，雖然廣發(fā)應(yīng)用于通信系統(tǒng)中，但快閃存儲(chǔ)器在數(shù)據(jù)存儲(chǔ)過程中產(chǎn)生錯(cuò)誤的機(jī)制與通信系統(tǒng)在數(shù)據(jù)傳輸過程中產(chǎn)生錯(cuò)誤的機(jī)制并不同，因而兩者的錯(cuò)誤率特點(diǎn)有著明顯的差別。隨著快閃存儲(chǔ)器的不斷使用，錯(cuò)誤比特率呈現(xiàn)出單調(diào)遞增的趨勢(shì)?？扉W存儲(chǔ)器中的糾錯(cuò)系統(tǒng)必須采用硬件實(shí)現(xiàn)?？扉W存儲(chǔ)器的隨

23、機(jī)訪問時(shí)間短，對(duì)解碼器的解碼延遲，數(shù)據(jù)吞吐量等指標(biāo)有著非常苛刻的要求，ECC有更強(qiáng)的糾錯(cuò)性能和動(dòng)態(tài)可調(diào)節(jié)的能力。</p><p>　　論文的后續(xù)章節(jié)就應(yīng)用于快閃存儲(chǔ)器控制器中的ECC模塊進(jìn)行了深入的分析和研究。采用了BCH(15,7,2)碼，可對(duì)7位的信息碼糾正2比特的錯(cuò)誤，生成15位的碼字。</p><p><b>　　第1章是引言。</b></p>

24、<p>　　第2章主要介紹整個(gè)ECC模塊的頂層原理圖設(shè)計(jì)，介紹頂層模塊的組成以及各個(gè)底層模塊在頂層模塊中的位置和作用。</p><p>　　第3章主要介紹ECC模塊中BCH編解碼器的原理和相應(yīng)的運(yùn)算。</p><p>　　第4章主要介紹ECC模塊中BCH編解碼器的電路結(jié)構(gòu)設(shè)計(jì)，對(duì)于編碼器采用了線性反饋移位寄存器的方法，避免了復(fù)雜的除法運(yùn)算。對(duì)于解碼器采用了三級(jí)流水線的方法，先對(duì)解

25、碼器的三個(gè)模塊：伴隨式計(jì)算模塊、錯(cuò)誤位置多項(xiàng)式計(jì)算模塊和錢氏搜索機(jī)進(jìn)行設(shè)計(jì)，再將三個(gè)模塊與編碼器進(jìn)行連接，并進(jìn)行了仿真驗(yàn)證。其中，伴隨式計(jì)算模塊采用了線性反饋移位寄存器的方法；錯(cuò)誤位置多項(xiàng)式計(jì)算模塊采用了基于PETERSON矩陣的直接求解法，整個(gè)電路有AND和XOR邏輯實(shí)現(xiàn)，設(shè)計(jì)簡單，速度高；錢氏搜索機(jī)采用了全并行的方法，由XOR樹實(shí)現(xiàn)，提高了速度。</p><p>　　第5章為本論文的總結(jié)。</p>

26、<p>　　第2章 ECC整體設(shè)計(jì)</p><p>　　2.1 ECC簡介 </p><p>　　ECC第一次提出是在1948年Claude Shannon的論文“A Mathematical Theory of Communication ” 中，經(jīng)過幾十年的發(fā)展，ECC技術(shù)目前已廣發(fā)應(yīng)用于通信系統(tǒng)、無線應(yīng)用、光盤存儲(chǔ)等領(lǐng)域。ECC技術(shù)的原理是：向原始的

27、信息數(shù)據(jù)中添加冗余位，進(jìn)行編碼；對(duì)接收到的信息，利用冗余位能夠找出接收信息中的錯(cuò)誤位置，并進(jìn)行糾正，從而恢復(fù)原始的存儲(chǔ)數(shù)據(jù)，這個(gè)過程也稱為解碼。糾錯(cuò)碼通常分為兩大類：線性碼和卷積碼。線性碼的特點(diǎn)是進(jìn)行數(shù)據(jù)處理的單位是碼字（codeword）,碼字是具有固定長度的信息塊。一個(gè)n位線性碼的碼字是由原始的k位信息加上相應(yīng)的冗余位組成，如圖2.1所示。另外，對(duì)于線性碼，碼字中每位信息受到的噪聲相互獨(dú)立，因此碼字中的錯(cuò)誤具有隨機(jī)性的特點(diǎn)。相反，卷

28、積碼是將信息數(shù)據(jù)看成連續(xù)的比特流，因而卷積進(jìn)行數(shù)據(jù)處理的單位是比特。在存儲(chǔ)系統(tǒng)中，存儲(chǔ)器以碼字為單位進(jìn)行數(shù)據(jù)的寫入和讀取操作的，因而采用線性碼實(shí)現(xiàn)存儲(chǔ)系統(tǒng)的糾錯(cuò)。本論文所關(guān)注的是線性碼在快閃存儲(chǔ)器控制器中的應(yīng)用。本論文所采用的BCH碼就是線性碼的一種。 </p><p>　　圖2.1 ECC碼字的組成</p><p><b>　　2.2 功能要求</b>

29、</p><p>　　應(yīng)用于快閃存儲(chǔ)器中的ECC模塊主要由編碼器和解碼器兩部分組成。本論文中的ECC技術(shù)采用了BCH(15,7,2)碼。</p><p>　　BCH（15，7，2）碼實(shí)現(xiàn)對(duì)7位的信息碼字進(jìn)行2位的糾錯(cuò)，生成8位的校驗(yàn)碼。將7位的數(shù)據(jù)寫入到閃存時(shí)，首先編碼器產(chǎn)生相應(yīng)的冗余位，形成一個(gè)15位的碼字。讀取時(shí)，解碼器搜索碼字中的錯(cuò)誤，并在其糾錯(cuò)能力范圍內(nèi)糾正相應(yīng)的錯(cuò)誤，從而恢復(fù)正確

30、的數(shù)據(jù)信息，輸出7位的信息碼。論文中的ECC整體設(shè)計(jì)如圖2.2所示。</p><p>　　圖2.2 快閃存儲(chǔ)器控制器的ECC系統(tǒng)</p><p>　　編碼器主要對(duì)輸入信息進(jìn)行編碼，對(duì)輸入的7比特信息位按照BCH碼的標(biāo)準(zhǔn)增加8比特的校驗(yàn)位組成一個(gè)15比特的碼字，含有2比特的糾錯(cuò)能力。編碼器采用線性反饋移位寄存器的方法實(shí)現(xiàn)，實(shí)現(xiàn)數(shù)據(jù)的串行輸入和串行輸出。</p><p

31、>　　對(duì)數(shù)據(jù)進(jìn)行編碼之后，當(dāng)輸出數(shù)據(jù)時(shí)，需要先進(jìn)行解碼和糾錯(cuò)。BCH解碼器能夠?qū)崿F(xiàn)解碼和糾錯(cuò)的功能。本論文中的BCH解碼器包括三個(gè)模塊：伴隨式計(jì)算模塊，錯(cuò)誤位置多項(xiàng)式系數(shù)計(jì)算模塊和錢氏搜索機(jī)模塊。</p><p>　　伴隨式模塊的作用是通過接收碼字和校驗(yàn)矩陣來計(jì)算伴隨式S,伴隨式也是采用線性反饋移位寄存器的方法實(shí)現(xiàn)，實(shí)現(xiàn)對(duì)數(shù)據(jù)的串行輸入和串行輸出。由于錯(cuò)誤位置多項(xiàng)式系數(shù)采用的是并行輸入，而它的輸入是伴隨式模

32、塊的輸出，所以在伴隨式模塊和錯(cuò)誤位置多項(xiàng)式模塊之間加了一個(gè)串并轉(zhuǎn)換電路。實(shí)現(xiàn)了端口的匹配。</p><p>　　錯(cuò)誤位置多項(xiàng)式系數(shù)采用了直接求解法，整個(gè)電路有AND和XOR邏輯組成，編碼簡單，易于實(shí)現(xiàn)。錯(cuò)誤位置多項(xiàng)式系數(shù)模塊的輸入是伴隨式模塊的輸出經(jīng)串并轉(zhuǎn)換電路后的輸出，使用的是并行輸入和并行輸出。</p><p>　　解碼部分的最后一個(gè)模塊式錢氏搜索機(jī)。本論文采用了全并行的方法實(shí)現(xiàn)錢氏搜

33、索。錢氏搜索機(jī)的作用是尋找錯(cuò)誤位置多項(xiàng)式的根，便于確定錯(cuò)誤的位置并糾正碼字中的錯(cuò)誤。錢氏搜索模塊是由XOR邏輯實(shí)現(xiàn)的。</p><p><b>　　2.3 本章總結(jié)</b></p><p>　　本章介紹了快閃存儲(chǔ)器控制器的ECC模塊的頂層電路設(shè)計(jì)。介紹了ECC的組成和ECC的各模塊的功能和在ECC中的位置。介紹了各個(gè)模塊的實(shí)現(xiàn)方法和中間轉(zhuǎn)換電路。</p>

34、<p><b>　　第3章 BCH碼</b></p><p>　　二進(jìn)制BCH碼是建立在伽羅華域(Galois field, GF)的基礎(chǔ)上的，本章將詳細(xì)闡述BCH碼編解碼的原理。</p><p><b>　　3.1 伽羅華域</b></p><p>　　閃存中存儲(chǔ)的數(shù)據(jù)信息均為二進(jìn)制數(shù)，因而應(yīng)用在閃存中

35、的BCH碼為二進(jìn)制BCH碼。二進(jìn)制BCH碼建立在伽羅華域(GF)的基礎(chǔ)上。伽羅華域是有限域，因Evariste Galois 首先發(fā)明而得名，其數(shù)學(xué)理論廣泛的應(yīng)用在糾錯(cuò)碼系統(tǒng)、密碼系統(tǒng)中。下面首先介紹伽羅華域的相關(guān)理論。</p><p>　　伽羅華域是有限域，其數(shù)學(xué)理論屬于群論范疇。伽羅華域有以下性質(zhì)：</p><p>　　伽羅華域具有有限性。伽羅華域中有有限個(gè)元素。</p>

36、<p>　　伽羅華域具有封閉性。伽羅華域定義了“加”和“乘”兩種操作。將域中任意兩個(gè)元素進(jìn)行相加或相乘的結(jié)果仍然是這個(gè)域中的元素，其中，域中有一個(gè)零元素“0”，對(duì)域中的任意元素,有；域中有一個(gè)單位元素 “1”，對(duì)域中任意元素，有。</p><p>　　伽羅華域具有可逆性。對(duì)于域中的任意元素，存在可逆的逆加元素，使得；存在可逆的逆乘元素，使得。</p><p>　　伽羅華域滿足

37、結(jié)合律，交換律和分配律。</p><p><b>　　結(jié)合律：；；</b></p><p><b>　　交換律： ；；</b></p><p><b>　　分配律：；</b></p><p>　　閃存中存儲(chǔ)的數(shù)據(jù)為二進(jìn)制數(shù)，因此應(yīng)用于閃存中的糾錯(cuò)碼技術(shù)均基于階伽羅華域，其中為伽

38、羅華域的度(degree)，這時(shí)伽羅華域可以表示為。</p><p>　　是的擴(kuò)域，是最簡單的有限域，只有兩個(gè)元素，其上的加法和乘法就是布爾加法和布爾乘法。即</p><p>　　表3.1 中的加法和乘法運(yùn)算 </p><p>　　共有個(gè)元素。中存在一個(gè)稱為本原域元素的，使得構(gòu)成伽羅華域中的全部個(gè)非零個(gè)元素。其中</p><p>　　

39、定義3.1：對(duì)于，如果滿足，則稱為伽羅華域的本原元。</p><p>　　定義3.2：表示一組多項(xiàng)式的集合，其中多項(xiàng)式的系數(shù)為中的元素。結(jié)果多項(xiàng)式除了常數(shù)和本身外，不能再被其他多項(xiàng)式除盡，則稱多項(xiàng)式為不可約多項(xiàng)式。</p><p>　　定義3.3： 對(duì)于最高次冪為的不可約多項(xiàng)式，若是的因子，并且的最小值為，則稱為上的本原多項(xiàng)式。</p><p>　　定義3.4：中任

40、一元素的最小多項(xiàng)式定義為以該元素為根的具有最小階數(shù)的多項(xiàng)式。的本原多項(xiàng)式是本原域元素的最小多項(xiàng)式。</p><p>　　通過上述的定義可以看出，為的根，即。令 </p><p>　　，由于上的減法操作等同于加法操作，可以得到：，該式表明，對(duì)于伽羅華域中的任何一個(gè)元素()，可以轉(zhuǎn)換為一個(gè)最高次冪不超過的多項(xiàng)式。因此伽羅華域中的元素可以有三種表示形式：指數(shù)形式，多項(xiàng)式形式，以及由多項(xiàng)式各項(xiàng)系數(shù)

41、組成的二進(jìn)制矢量表達(dá)式。作為例子，表3.2中給出上一些元素的三種表達(dá)方式。對(duì)于，本原多項(xiàng)式為。</p><p>　　表3.2 上元素不同的表達(dá)方式</p><p>　　3.2 BCH碼的編碼</p><p>　　BCH碼是循環(huán)碼的一個(gè)重要子類，它具有糾多個(gè)錯(cuò)誤的能力，BCH碼有嚴(yán)密的代數(shù)理論，是目前研究的最透徹的一類碼。BCH 碼是1959 年由Hocquen

42、ghem、1960 年由Bose和Chandhari 分別獨(dú)立提出的。BCH碼是糾正多個(gè)隨機(jī)錯(cuò)誤的循環(huán)碼，可以用生成多項(xiàng)式的根來描述。 </p><p>　　給定任一有限域及其擴(kuò)域， 其中是素?cái)?shù)或素?cái)?shù)的冪， 為某一正整數(shù)。 若碼元取自上的一循環(huán)碼，它的生成多項(xiàng)式的根集合中含有以下個(gè)連續(xù)根：1、、…… 時(shí)， 則由生成的循環(huán)碼稱為進(jìn)制BCH碼。 </p><p>　　設(shè)和分別是()元素的最小多

43、項(xiàng)式和級(jí)， 則BCH碼的生成多項(xiàng)式和碼長分別是： </p><p><b>　　(3.1) </b></p><p><b>　　(3.2)</b></p><p>　　其中為的最小多項(xiàng)式，LCM表示最小公倍數(shù) (least common multiple)。 </p><

44、p>　　如果生成多項(xiàng)式的根中，有一個(gè)中的本原域元素， 則， 稱這種碼長的BCH碼為本原BCH碼；否則，稱為非本原BCH碼。 中元素的級(jí)一定是的因子，所以非本原BCH碼的碼長也一定是的因子。</p><p>　　二進(jìn)制BCH碼是建立在域上的，加法可以用異或表示，除法可以用移位表示。BCH(n，k, t)碼的定義如下：</p><p>　　碼字長度： </p>&l

45、t;p><b>　　數(shù)據(jù)的長度： </b></p><p>　　校驗(yàn)信息的長度： </p><p>　　糾錯(cuò)能力： 所有小于或等于位錯(cuò)誤的情況。</p><p>　　有些情況下實(shí)際應(yīng)用中的信息數(shù)據(jù)長度并不恰好等于BCH（n, k，t）碼定義中的信息數(shù)據(jù)長度。例如，在快閃存儲(chǔ)器中通常信息個(gè)數(shù)為而根據(jù)上述BCH碼的定義所計(jì)算

46、出的,在這種情況下，可以使用縮短的BCH碼。</p><p>　　所謂縮短的BCH碼，是指在BCH(n, k, t)碼的碼字中使最高位的個(gè)信息位均置為0，這樣傳輸時(shí)就可以不用送它們，只要傳遞后面的位碼字即可，這樣構(gòu)成了一個(gè)（,）的碼，稱為BCH的縮短碼。需要指出的是BCH縮短碼有著與BCH碼同樣的糾錯(cuò)能力，均為,即BCH(n-p, k-p, t)。</p><p>　　此外，BCH碼屬于循

47、環(huán)碼。循環(huán)碼是線性碼的一個(gè)重要子類，顧名思義，循環(huán)碼的碼字具有循環(huán)的特性。其循環(huán)特性使它的編碼算法變得比較簡單，編碼電路也易于實(shí)現(xiàn)。</p><p>　　對(duì)于二進(jìn)制BCH碼，和的最小多項(xiàng)式相同，所以式（3.1）可以寫成如式(3.3)的形式：</p><p><b>　　(3.3)</b></p><p>　　由于最小多項(xiàng)式的最高次冪為,所以生成

48、多項(xiàng)式的最高次冪為.同時(shí)BCH碼為循環(huán)碼，因此對(duì)于任何BCH碼的碼字，都是的倍式，即。</p><p>　　假設(shè)BCH的信息數(shù)據(jù)為，其對(duì)應(yīng)的多項(xiàng)式為；</p><p>　　相應(yīng)的生成多項(xiàng)式為：；</p><p>　　碼字為，則碼字多項(xiàng)式可以表示為 </p><p>　?。?.4）

49、 </p><p>　　式中。顯然的最高次冪小于，通過移項(xiàng)上式可以變?yōu)椋?。其?shí)就是BCH碼中的冗余位多項(xiàng)式。另外，在伽羅華域中，減法操作等同于加法操作，將等式兩邊同除以，可以得到計(jì)算的表達(dá)式： </p><p><b>　　(3.5)</b></p><p>　　所以BCH(15,7，2)碼的編碼的產(chǎn)生步

50、驟為：</p><p><b>　　將信息多項(xiàng)式預(yù)乘;</b></p><p>　　將除以,得余式，此余式就是編碼需要得到的校驗(yàn)位多項(xiàng)式;</p><p>　　得到循環(huán)碼的碼字多項(xiàng)式為的形式。</p><p>　　由上述BCH（15，7，2）碼編碼的產(chǎn)生過程可以看出：構(gòu)造一個(gè)BCH（15，7，2）碼的關(guān)鍵是要找出該碼的生

51、成多項(xiàng)式。當(dāng)碼長及糾錯(cuò)能力給定后可以用MATLAB求出生成多項(xiàng)式。下面是求解生成多項(xiàng)式的MATLAB代碼：</p><p>　　Gen_gf=bchgenpoly(15,7).</p><p>　　3.3 BCH碼的解碼</p><p>　　3.3.1 伴隨式的求解方法</p><p>　　如前所述，BCH碼的生成多項(xiàng)式是個(gè)最小多項(xiàng)式的乘

52、積，因而含有個(gè)連續(xù)冪次的根：。而BCH碼的碼字又是生成多項(xiàng)式的倍式，因此碼字也是這些連續(xù)冪次的根，即： </p><p>　　for (3.6)</p><p><b>　　寫成矩陣的形式為：</b></p><p><b>　　(3.7) </b></p><p>　　其

53、中H定義為BCH碼的檢驗(yàn)矩陣，為碼字矢量。</p><p>　　設(shè)接收到的碼字多項(xiàng)式為：，則BCH碼伴隨式S的定義如下： </p><p><b>　　(3.8)</b></p><p>　　如果個(gè)伴隨式均為零，則說明接收到的碼字沒有錯(cuò)誤，反之，則說明接收到的碼字中有錯(cuò)誤。</p>

54、<p>　　此外，伴隨式S還可以通過另外一種方法獲得：先用對(duì)應(yīng)的最小多項(xiàng)式除接收到的碼字多項(xiàng)式：</p><p>　　for (3.9)</p><p>　　再根據(jù)最小多項(xiàng)式的定義，可以得到，將上式移項(xiàng)帶入后得：</p><p>　　for (3.10)</p><p>　　可以看出，對(duì)于伴隨式的每一個(gè)分量，式(

55、3.8)和(3.10)的表達(dá)式一致，因此兩種方法均可以用來計(jì)算伴隨式。另外，對(duì)于式(3.9)求解伴隨式的運(yùn)算與BCH編碼的表達(dá)式(3.5) 有著相似的數(shù)學(xué)表達(dá)式，都需要多項(xiàng)式的除法運(yùn)算。因此硬件實(shí)現(xiàn)也有著相似的電路結(jié)構(gòu)，在電路中均采用線性反饋移位寄存器結(jié)構(gòu)實(shí)現(xiàn)。</p><p>　　本論文中求解BCH(15,7,2)碼的伴隨式，采用的是式(3.9)，即通過線性反饋移位寄存器的方法來求得伴隨式S。但是硬件實(shí)現(xiàn)與式(

56、3.5)不同。BCH編碼是先將輸入量乘以因子進(jìn)行除法取余操作，而伴隨式的產(chǎn)生是直接將接收量進(jìn)行除法取余操作。這在電路實(shí)現(xiàn)上反映出的差別是前者電路的輸入端與最高位的寄存器進(jìn)行相加后形成反饋信號(hào)，并連接到最低位的寄存器上，而后者電路的輸入端則是與最低位的寄存器相加后形成反饋信號(hào)。最終寄存器中的內(nèi)容就是伴隨式的值。由于BCH碼是二進(jìn)制BCH碼，因而偶數(shù)項(xiàng)的伴隨式等于前項(xiàng)伴隨式的平方，即。所以可以減少計(jì)算量和復(fù)雜度。</p>&l

57、t;p>　　上述BCH(15,7,2)是建立在伽羅華域上的，最小多項(xiàng)式可以用 MATLAB生成，其中產(chǎn)生最小多項(xiàng)式的代碼為：</p><p><b>　　m=4,t=2;</b></p><p>　　x=gf(2,m);</p><p>　　for i=1:2 :(2*t-1)</p><p>　　min

58、pol_gf=minpol(x^i);</p><p><b>　　end；</b></p><p><b>　　得到，。</b></p><p>　　3.3.2 錯(cuò)誤位置多項(xiàng)式的高速求解法</p><p>　　BCH解碼中的錯(cuò)誤位置多項(xiàng)式為：</p><p><b&

59、gt;　　(3.11)</b></p><p>　　錯(cuò)誤位置多項(xiàng)式的個(gè)根就是碼字中錯(cuò)誤位置的倒數(shù)。錯(cuò)誤位置多項(xiàng)式的系數(shù)與伴隨式分量之間的關(guān)系有下列牛頓恒等式給出：</p><p>　　(3.12) </p><p>　　該步的任務(wù)就是通過上述牛頓恒等式，計(jì)算出的各項(xiàng)系數(shù)。1960年P(guān)eterson首次提出了通過矩陣運(yùn)算求解多項(xiàng)式系數(shù)的方

60、法，然而由于需要計(jì)算矩陣的逆運(yùn)算，實(shí)現(xiàn)較為復(fù)雜。1966年Berlekamp提出了采用迭代運(yùn)算求解多項(xiàng)式系數(shù)的方法，1969年Massey將此算法進(jìn)行了簡化，使其實(shí)現(xiàn)比較簡單，成為了著名的B-M(Berlekamp-Massey)算法。該算法的核心思想是：先給出最低次多項(xiàng)式，讓其系數(shù)滿足第一個(gè)牛頓恒等式；在檢驗(yàn)是否滿足第二個(gè)牛頓恒等式，若不滿足，則向中添加一個(gè)修正項(xiàng)構(gòu)成，以滿足第二個(gè)牛頓恒等式；反之則使，迭代過程一直進(jìn)行下去，直到得到為

61、止。B-M算法中需要求逆運(yùn)算，而求逆運(yùn)算的硬件實(shí)現(xiàn)較為復(fù)雜，為了便于硬件實(shí)現(xiàn)，后來者對(duì)Berlekamp迭代算法進(jìn)行了相應(yīng)的改進(jìn)，并提出了免求逆的運(yùn)算，目前較為廣泛的是RiBM(Reformulated Inversionless B-M)算法，RiBM算法具有硬件實(shí)現(xiàn)時(shí)單元結(jié)構(gòu)有很好的規(guī)則性的優(yōu)點(diǎn)。</p><p>　　本論文中的BCH(15,7,2)碼的錯(cuò)誤位置多項(xiàng)式的表達(dá)式，如下：</p>&

62、lt;p><b>　?。?.13）</b></p><p>　　通常求解錯(cuò)誤位置多項(xiàng)式的系數(shù)的方法是采用RiBM算法。RiBM算法的核心思想是將本次時(shí)鐘周期計(jì)算出的值與上一個(gè)時(shí)鐘周期的值進(jìn)行比較，根據(jù)比較的結(jié)果決定下一個(gè)時(shí)鐘周期表達(dá)式系數(shù)的值，這樣經(jīng)過2t個(gè)時(shí)鐘周期的迭代，最后計(jì)算出關(guān)鍵方程系數(shù)的值。顯然，這種RiBM算法，不適于閃存高速解碼的要求，因此，我們提出了一種直接求解法來計(jì)算

63、錯(cuò)誤位置多項(xiàng)式的系數(shù)。</p><p>　　直接求解法的數(shù)學(xué)理論源于Peterson矩陣。Peterson矩陣是Peterson于1960年提出的矩陣求解錯(cuò)誤位置多項(xiàng)式系數(shù)的方法，Peterson矩陣的表達(dá)式為式(3.14)，可以看出，求解σ需要用到矩陣的逆運(yùn)算，并且隨著糾錯(cuò)位數(shù)t的增加，矩陣運(yùn)算復(fù)雜度急劇增加，因此實(shí)際應(yīng)用中的BCH碼譯碼時(shí)沒有采用Peterson矩陣的方法。</p><p&

64、gt;<b>　　(3.14)</b></p><p>　　然而，對(duì)于t=2的BCH（15,7,2）碼，Peterson矩陣的變量很少，因此一個(gè)可行的方法是根據(jù)矩陣方程直接求解出系數(shù)、的值。采用這種直接求解法時(shí)，求解出的關(guān)鍵系數(shù)和的表達(dá)式為</p><p><b>　　(3.15)</b></p><p>　　因此，錯(cuò)誤位

65、置多項(xiàng)式的表達(dá)式為</p><p><b>　　(3.16)</b></p><p>　　可見，通過采用直接求解法，避免了傳統(tǒng)RiBM算法的迭代過程，然而上述表達(dá)式中仍然存在著伽羅華域的除法運(yùn)算，除法運(yùn)算的硬件復(fù)雜度高、延遲大。為了進(jìn)一步減少解碼的延遲，需要通過正確的且適當(dāng)?shù)淖儞Q消除伽羅華域的除法運(yùn)算。</p><p>　　有文獻(xiàn)證明，對(duì)于任意

66、的BCH碼，如果碼字中存在錯(cuò)誤，則有，因此可以將上述等式的兩邊同時(shí)乘以系數(shù)，從而消除了伽羅華域的除法運(yùn)算，生成的新表達(dá)式為 ：</p><p><b>　　(3.17) </b></p><p>　　BCH解碼的最后一步錢氏搜索是在伽羅華域中尋找錯(cuò)誤位置多項(xiàng)式的根，也就是滿足的。顯然，當(dāng), 同樣也有，因此錯(cuò)誤位置多項(xiàng)式經(jīng)過消除除法的變換后與變換前有著相同的根，也就是仍

67、搜索到相同的錯(cuò)誤位置，從而保證了消除除法變換的正確性。在伽羅華域上，每個(gè)伴隨式矢量都可以表示成相對(duì)應(yīng)的多項(xiàng)式的形式：</p><p>　　根據(jù)伽羅華域的封閉性，可以求出系數(shù)，如下：</p><p><b>　　(3.18)</b></p><p><b>　　(3.19)</b></p><p>&

68、lt;b>　?。?.20）</b></p><p>　　可以看出，上述的系數(shù)計(jì)算表達(dá)式中只包含了模2的加法運(yùn)算和模2的乘法運(yùn)算，而模2的加法運(yùn)算和乘法運(yùn)算可以分別用XOR邏輯和AND邏輯實(shí)現(xiàn)。因此，對(duì)于應(yīng)用于t=2的BCH（15,7,2）碼，采用直接求解法計(jì)算錯(cuò)誤位置多項(xiàng)式的系數(shù)時(shí)，消除了傳統(tǒng)RiBM算法的迭代運(yùn)算及伽羅華域復(fù)雜的除法運(yùn)算，使最終可以用組合邏輯電路中的XOR和AND邏輯就能夠?qū)崿F(xiàn)

69、多項(xiàng)式系數(shù)的求解，最終實(shí)現(xiàn)了高速的系數(shù)求解。</p><p>　　3.3.3 全并行錢氏搜索機(jī)</p><p>　　BCH解碼的最后一步就是尋找錯(cuò)誤位置。錯(cuò)誤位置多項(xiàng)式的根就是錯(cuò)誤位置的倒數(shù)。然而，工程上實(shí)現(xiàn)的求解伽羅華域的多項(xiàng)式的根非常困難。1964年華裔科學(xué)家錢聞天了易于工程實(shí)現(xiàn)的求解根的方法。其思想是將求解錯(cuò)誤位置多項(xiàng)式的根轉(zhuǎn)化為檢驗(yàn)錯(cuò)誤位置多項(xiàng)式的根。將伽羅華域的元素()依次帶入

70、到錯(cuò)誤位置多項(xiàng)式中，如果該元素是的根，即存在，那么就可以找到碼字中的一個(gè)錯(cuò)誤，錯(cuò)誤位置為，這種方法稱為錢氏搜索（Chien search），已成為BCH解碼過程中尋找錯(cuò)誤位置多項(xiàng)式的最常用的方法。錢氏搜索機(jī)的運(yùn)行過程如下：對(duì)接收到的碼字多項(xiàng)式，先檢驗(yàn)第一位比特是不是有錯(cuò)誤，也就是檢查是否為的根，即 </p><p>　　如果，則比特為錯(cuò)誤的比特，否則該比特正確。由于錢氏搜索的方法是從第一位比特開始檢

71、測，一直遍歷到整個(gè)碼字空間，因此具有逐位譯出，先譯先出的特點(diǎn)。這一特點(diǎn)也使得BCH譯碼的過程可以采用三級(jí)流水線的方法實(shí)現(xiàn)，從而顯著的提高了譯碼器的吞吐率，通過錢氏搜索機(jī)尋找出碼字中的所有錯(cuò)誤用矢量表示，將與接收到的矢量相加，便完成了BCH的譯碼。</p><p>　　下面針對(duì)于BCH(15,7,2)碼，對(duì)錢氏搜索機(jī)做一介紹。</p><p>　　對(duì)于BCH(15,7,2)碼，計(jì)算出錯(cuò)誤位置

72、多項(xiàng)式的系數(shù)之后，就進(jìn)入錢氏搜索。錢氏搜索通過在伽羅華域中搜尋多項(xiàng)式的根來確定錯(cuò)誤位置，表達(dá)式如下：</p><p>　　for (3.21)</p><p>　　假設(shè)通過搜索發(fā)現(xiàn)，那么就是錯(cuò)誤的位置。</p><p><b>　　3.4 本章總結(jié)</b></p><p>　　本章首先介紹了伽羅華域的基本

73、概念和相應(yīng)的理論，接著介紹了BCH碼編碼的原理和編碼的實(shí)現(xiàn)步驟。對(duì)于BCH碼解碼，采用了三級(jí)流水線的形式，所以分別介紹了伴隨式計(jì)算的原理和方法、錯(cuò)誤位置多項(xiàng)式的高速求解的方法和并行錢氏搜索機(jī)的方法。</p><p>　　第4章 BCH編解碼器的設(shè)計(jì)</p><p>　　本章將闡述BCH碼編碼器的設(shè)計(jì)，采用了線性反饋移位寄存器（linear feedback shift register）

74、的電路結(jié)構(gòu)來實(shí)現(xiàn)串行BCH(15,7,2)碼編碼器的設(shè)計(jì)。論文中ECC模塊的BCH(15,7,2)碼解碼器的設(shè)計(jì)采用了三級(jí)流水線的方法，解碼分三個(gè)模塊：伴隨式模塊、錯(cuò)誤位置多項(xiàng)式模塊、錢氏搜索模塊。論文先對(duì)各個(gè)模塊進(jìn)行設(shè)計(jì)和VHDL代碼的編寫，仿真通過后，將解碼器與編碼器連接起來，實(shí)現(xiàn)總的功能。利用這種方法實(shí)現(xiàn)編解碼，運(yùn)算程序大為簡化，具有解碼速度快，硬件實(shí)現(xiàn)復(fù)雜度低等特點(diǎn)。</p><p>　　4.1 BCH

75、編碼器</p><p>　　BCH碼的編碼可以用硬件實(shí)現(xiàn)也可以用軟件實(shí)現(xiàn)，硬件實(shí)現(xiàn)法速度快，適用于實(shí)時(shí)處理，但是需要反復(fù)實(shí)驗(yàn)，制作周期長；用軟件實(shí)現(xiàn)，可以利用計(jì)算機(jī)模擬，節(jié)省時(shí)間，提高效率，但是運(yùn)行速度慢，需要尋找最佳算法進(jìn)行最優(yōu)化。BCH碼是線性循環(huán)碼的一種，其編碼方式和一般的循環(huán)碼編碼方式相同，容易實(shí)現(xiàn)的方式是將信息碼多項(xiàng)式升次冪后除以生成多項(xiàng)式，然后將所得余式置于升冪后的信息多項(xiàng)式之后，即采用式(3.5)的

76、方法進(jìn)行編碼。</p><p>　　將生成多項(xiàng)式和信息碼字帶入式(3.5), 就可構(gòu)造BCH(15,7，2)循環(huán)碼的編碼方式。求解需要伽羅華域的除法運(yùn)算，除法電路通常是使用線性反饋移位寄存器來實(shí)現(xiàn)的。BCH(15,7，2)循環(huán)碼編碼器的電路結(jié)構(gòu)如圖4.1所示。</p><p>　　圖4.1 BCH（15，7，2）碼的編碼器的電路結(jié)構(gòu)圖</p><p>　　圖中

77、代表模2的相加，可以用異或門實(shí)現(xiàn)。第一步：當(dāng)rst=1時(shí)，信息數(shù)據(jù)移入線路中，同時(shí)送出。信息從線路的前段移入等價(jià)于用乘信息多項(xiàng)式。當(dāng)k位信息數(shù)據(jù)全部移入線路，在寄存器中的個(gè)數(shù)據(jù)就夠成了余項(xiàng)，所以它們就是校驗(yàn)碼。第二步：移出校驗(yàn)碼，并把它們送出。這個(gè)校驗(yàn)碼與k個(gè)信息一起構(gòu)成一個(gè)完整的數(shù)據(jù)碼字。</p><p>　　BCH（15,7,2）碼編碼器電路模塊包括輸入數(shù)據(jù)data_in,輸出數(shù)據(jù)data_out,控制信號(hào)r

78、st,時(shí)鐘信號(hào)clk和除法電路五部分組成。當(dāng)rst=1時(shí)，實(shí)現(xiàn)對(duì)數(shù)據(jù)的編碼，rst=0時(shí)實(shí)現(xiàn)復(fù)位。BCH(15,7,2)的電路框圖如圖4.2所示。</p><p>　　圖4.2 BCH（15，7，2）碼的編碼器的電路框圖</p><p>　　電路的工作方式如下：先使得控制信號(hào)rst=1，反饋回路開始工作，每個(gè)時(shí)鐘周期串行輸入1位的信息data_in，這樣經(jīng)過8個(gè)時(shí)鐘周期，各寄存器的值就是

79、BCH碼字的冗余位，此時(shí)改變控制信號(hào)，令rst=0,再經(jīng)過n-k個(gè)時(shí)鐘周期就可以輸出冗余位，這樣就生成BCH(15,7,2)碼的一個(gè)長度為15的碼字。</p><p>　　對(duì)于BCH(15,7,2)碼，輸入0011001，經(jīng)過編碼后輸出001100111110110，利用ALTERA的QUARTUSII軟件對(duì)BCH(15,7,2)碼編碼器的進(jìn)行時(shí)序仿真，結(jié)果如圖4.3所示。</p><p>

80、;　　圖4.3 BCH(15,7,2)碼編碼器的時(shí)序仿真結(jié)果 </p><p>　　對(duì)于BCH(15,7,2)碼,輸入信息位0011000，經(jīng)過編碼后輸出001100000100111，利用ALTERA的QUARTUSII軟件對(duì)BCH(15,7,2)碼編碼器的時(shí)序進(jìn)行仿真，結(jié)果如圖4.4所示：</p><p>　　圖4.4 BCH(15,7,2)碼編碼器的時(shí)序仿真結(jié)果</p&g

81、t;<p>　　以上仿真結(jié)果看出，第2到8個(gè)時(shí)鐘周期輸出的是信息碼，第9到16個(gè)時(shí)鐘輸出的校驗(yàn)碼，實(shí)現(xiàn)了串行輸入和串行輸出。</p><p>　　4.2 BCH解碼器</p><p>　　論文采用了三級(jí)流水線的方法進(jìn)行BCH(15,7,2)碼的解碼碼，解碼分三個(gè)模塊：伴隨式模塊、錯(cuò)誤位置多項(xiàng)式模塊、錢氏搜索模塊。</p><p>　　4.2.1 伴

82、隨式計(jì)算模塊</p><p>　　根據(jù)上一章的介紹，伴隨式的求解方法有兩種。一種是基于矩陣的運(yùn)算，一種是除法運(yùn)算。除法運(yùn)算可以采用線性反饋移位寄存器的方法來實(shí)現(xiàn)，簡單，復(fù)雜度低。所以本論文的伴隨式的求解是用線性反饋移位寄存器實(shí)現(xiàn)的。</p><p>　　根據(jù)式(3.9)，采用線性反饋移位寄存器的方法來構(gòu)建BCH(15,7,2)碼伴隨式產(chǎn)生器，電路結(jié)構(gòu)圖如圖4.5所示。</p>

83、<p>　　伴隨式S1產(chǎn)生器的電路結(jié)構(gòu)圖</p><p>　　b. 伴隨式S3產(chǎn)生器的電路結(jié)構(gòu)圖</p><p>　　圖4.5 伴隨式產(chǎn)生器的電路結(jié)構(gòu)圖</p><p>　　開始時(shí)4級(jí)移位寄存器中的寄存數(shù)據(jù)全部清零；接著輸入接收的碼字，同時(shí)輸出，經(jīng)過16個(gè)周期后，寄存器內(nèi)的數(shù)據(jù)就是錯(cuò)誤位置多項(xiàng)式；最后通過移位，再經(jīng)過4個(gè)周期，伴隨式的值被移出。<

84、/p><p>　　伴隨式產(chǎn)生器模塊包括輸入數(shù)據(jù)data_in,實(shí)際上是編碼器的輸出，時(shí)鐘信號(hào)clk, 控制信號(hào)rst, 輸出數(shù)據(jù)data_out和除法電路五部分,當(dāng)rst=0時(shí)實(shí)現(xiàn)復(fù)位，當(dāng)rst=1時(shí)，由輸入15位信息，求出伴隨式S，模塊結(jié)構(gòu)如圖4.6。</p><p>　　圖4.6 伴隨式S1產(chǎn)生器的電路模塊圖</p><p>　　圖4.7 伴隨式S3產(chǎn)生器的電路模塊

85、圖</p><p>　　電路的工作方式如下：先使得控制信號(hào)rst=1，反饋回路開始工作，每個(gè)時(shí)鐘周期串行輸入1位的輸入信息data_in，這樣經(jīng)過16個(gè)時(shí)鐘周期，各寄存器的值就是伴隨式的值，此時(shí)改變控制信號(hào)，令rst=0,再經(jīng)過4個(gè)周期就可以輸出伴隨式。</p><p>　　對(duì)于圖4.3中的輸出序列001100111110110，伴隨式為：0000，利用ALTERA的QUARTUSII軟件

86、對(duì)BCH(15,7,2)碼的伴隨式產(chǎn)生器的時(shí)序進(jìn)行仿真，結(jié)果如圖4.8所示。</p><p><b>　　(S1)</b></p><p><b>　　( S3)</b></p><p>　　圖4.8 BCH(15,7,2)碼的伴隨式產(chǎn)生器的時(shí)序仿真結(jié)果</p><p>　　從圖4.8看出，第2到

87、第16個(gè)周期輸出的是編碼器編碼后的碼字，即編碼器的輸出，第17到第20個(gè)周期輸出的是伴隨式。</p><p>　　4.2.2 錯(cuò)誤位置多項(xiàng)式計(jì)算模塊</p><p>　　對(duì)于BCH（15，7，2）碼，m=4，在伽羅華域上，使用上一章介紹的直接求解法，根據(jù)式(3.18)，(3.19),(3.20),可以得到系數(shù)的RTL級(jí)電路圖，如圖4.9所示，該電路基本上是用XOR和AND邏輯實(shí)現(xiàn)了求解錯(cuò)

88、誤位置多項(xiàng)式的功能。</p><p>　　圖4.9 BCH（15，7，2）碼中錯(cuò)誤位置多項(xiàng)式系數(shù)的電路實(shí)現(xiàn)</p><p>　　錯(cuò)誤位置多項(xiàng)式模塊包括輸入數(shù)據(jù), 實(shí)際是伴隨式產(chǎn)生器模塊的輸出data_out1、data_out3，時(shí)鐘信號(hào)clk, 控制信號(hào)rst， 輸出數(shù)據(jù)data_out 。當(dāng)rst=0時(shí)實(shí)現(xiàn)復(fù)位，當(dāng)rst=1時(shí)，由輸入的4位信息，求出錯(cuò)誤位置多項(xiàng)式的系數(shù)。內(nèi)部電路由X

89、OR和AND邏輯實(shí)現(xiàn)。BCH(15,7,2)碼中錯(cuò)誤位置多項(xiàng)式系數(shù)的模塊圖如圖4.10所示。</p><p>　　圖4.10 BCH（15，7，2）碼中錯(cuò)誤位置多項(xiàng)式系數(shù)的模塊圖</p><p>　　電路的工作方式如下：當(dāng)rst=1時(shí)，并行輸入,在時(shí)鐘上升沿時(shí)輸出錯(cuò)誤位置多項(xiàng)式的系數(shù)。</p><p>　　設(shè)伴隨式=1010,=0110,輸出是1010，1000，

90、1001，則利用ALTERA的QUARTUSII軟件對(duì)BCH(15,7,2)碼錯(cuò)誤位置多項(xiàng)式模塊的時(shí)序仿真結(jié)果如圖4.11所示</p><p>　　圖4.11 BCH(15,7,2)碼錯(cuò)誤位置多項(xiàng)式模塊的時(shí)序仿真結(jié)果</p><p>　　從圖4.11可以看出，對(duì)于給定的經(jīng)過大約18ns后開始得到正確的。</p><p>　　4.2.3 錢氏搜索機(jī)</p&

91、gt;<p>　　通常采用反饋寄存器的電路實(shí)現(xiàn)方式實(shí)現(xiàn)錢氏搜索，這需要較多的時(shí)鐘周期才能完成，為了滿足閃存對(duì)高速解碼的要求，本論文中將錢氏搜索進(jìn)行了并行化，采用了全并行的錢氏搜索的實(shí)現(xiàn)方法，其電路結(jié)構(gòu)為全并行的XOR-樹構(gòu)成的組合邏輯。先計(jì)算至這15個(gè)多項(xiàng)式中各項(xiàng)的結(jié)果，經(jīng)過求和計(jì)算后輸出，將求和結(jié)果與相應(yīng)的碼字進(jìn)行異或，即在一個(gè)時(shí)鐘周期內(nèi)完成了碼字的糾錯(cuò)。</p><p>　　全并行錢氏搜索機(jī)的電

92、路模塊包括輸入data_in ,實(shí)際是編碼器輸出的數(shù)據(jù)，復(fù)位rst,時(shí)鐘信號(hào)clk,錯(cuò)誤位置多項(xiàng)式的系數(shù)d0、d1、d2和糾錯(cuò)后的輸出data_out七部分，如圖4.12所示。</p><p>　　圖4.12 全并行錢氏搜索機(jī)的電路模塊圖</p><p>　　當(dāng)rst=0時(shí)，實(shí)現(xiàn)復(fù)位，模塊的輸出為零；當(dāng)rst=1時(shí)，實(shí)現(xiàn)對(duì)輸入數(shù)據(jù)進(jìn)</p><p>　　行XOR 和

93、AND邏輯運(yùn)算后，輸出結(jié)果，及最后解碼并糾錯(cuò)后的結(jié)果。</p><p>　　利用ALTERA的QUARTUS軟件對(duì)BCH(15,7,2)碼錢氏搜索機(jī)模塊的時(shí)序仿真結(jié)果如圖4.12所示</p><p>　　圖4.12 BCH(15,7,2)碼錢氏搜索機(jī)模塊的時(shí)序仿真結(jié)果</p><p>　　4.3 ECC模塊的驗(yàn)證</p><p>　　第三

94、章和本章前幾個(gè)章節(jié)介紹了BCH（15，7，2）碼的編碼和解碼的方法和相應(yīng)的電路設(shè)計(jì)。本節(jié)主要完成這兩個(gè)模塊的總的設(shè)計(jì)，實(shí)現(xiàn)數(shù)據(jù)的編解碼。</p><p>　　首先，將各個(gè)模塊進(jìn)行連接，在時(shí)序上進(jìn)行統(tǒng)一。由于錯(cuò)誤位置多項(xiàng)式的系數(shù)模塊和錢氏搜索模塊的輸入是并行輸入，而與此對(duì)應(yīng)的相應(yīng)的伴隨式模塊和編碼模塊的輸出是串行輸出，所以首先通過移位寄存器進(jìn)行了串并的轉(zhuǎn)換，再將相應(yīng)的端口進(jìn)行相連。</p><p

95、>　　快閃存儲(chǔ)器控制器中的ECC的各模塊設(shè)計(jì)完成后，將各模塊連接成一個(gè)頂層模塊，如圖 4.13所示。</p><p>　　圖4.13 ECC頂層模塊原理圖</p><p>　　對(duì)整個(gè)模塊進(jìn)行驗(yàn)證：</p><p>　　輸入碼字：0011001</p><p>　　經(jīng)過大約103.5ns后，輸出解碼后的碼字：001101</p

96、><p>　　仿真結(jié)果如圖4.14所示：</p><p>　　圖4.14 頂層模塊仿真結(jié)果</p><p>　　從仿真結(jié)果可以看出：最后輸出了解碼后的碼字：0011001.</p><p><b>　　4.4 本章總結(jié)</b></p><p>　　論文介紹的BCH(15,7,2)碼編碼器是利用線性

97、反饋移位寄存器的方法實(shí)現(xiàn)的，采用了串行輸入和串行輸出的方式。然后寫出相應(yīng)的VHDL代碼，生成了相應(yīng)的模塊圖，并在FPGA上進(jìn)行了仿真。</p><p>　　論文中的解碼方法與原先的查找表方法不同，解碼器分為三個(gè)模塊：解伴隨計(jì)算式、解錯(cuò)誤位置多項(xiàng)式計(jì)算模塊和錢氏搜索機(jī)。其中，伴隨式計(jì)算模塊采用了線性反饋移位寄存器電路實(shí)現(xiàn)，解錯(cuò)誤位置多項(xiàng)式計(jì)算模塊采用了基于Peterson矩陣的直接求解法實(shí)現(xiàn)，錢氏搜索機(jī)采用了全并行

98、的方法實(shí)現(xiàn)。</p><p>　　求解伴隨式，首先要求解最小多項(xiàng)式，最小多項(xiàng)式可以由MATLAB自動(dòng)求出；直接求法求解錯(cuò)誤位置多項(xiàng)式的系數(shù)只用AND和XOR邏輯，避免了迭代運(yùn)算，消除了伽羅華域的除法運(yùn)算，最終實(shí)現(xiàn)了高速的系數(shù)求解；求解錯(cuò)誤位置多項(xiàng)式的根，采用了全并行的方法，提高了解碼速度。</p><p>　　本章先對(duì)BCH碼編解碼器的各個(gè)模塊進(jìn)行設(shè)計(jì)，接著給出了相應(yīng)的電路模塊圖，并進(jìn)行了

99、相應(yīng)的仿真結(jié)果。</p><p><b>　　第5章 總結(jié)</b></p><p>　　隨著快閃存儲(chǔ)器存儲(chǔ)單元尺寸不斷縮小、存儲(chǔ)容量不斷增加、以及多電平技術(shù)的廣發(fā)使用，快閃存儲(chǔ)器的存儲(chǔ)單元發(fā)生錯(cuò)誤的概率越來越大，所以必須加強(qiáng)快閃存儲(chǔ)器控制器的糾錯(cuò)能力和糾錯(cuò)速度。</p><p>　　本論文對(duì)于 flash存儲(chǔ)器控制器的設(shè)計(jì)，主要是針對(duì)于其中的

100、錯(cuò)誤檢查與糾錯(cuò)（ECC）模塊.ECC模塊是存儲(chǔ)器控制器的核心模塊，主要實(shí)現(xiàn)對(duì)輸入和輸出數(shù)據(jù)進(jìn)行編解碼、糾正數(shù)據(jù)的錯(cuò)誤。首先，論文的每一章節(jié)，先對(duì)編解碼的基礎(chǔ)知識(shí)進(jìn)行介紹，然后對(duì)相應(yīng)的模塊做出了設(shè)計(jì)，并進(jìn)行了仿真和驗(yàn)證。對(duì)于BCH（15，7，2）碼，編碼采用了線性反饋移位寄存器的方法，避免了傳統(tǒng)方法中的除法運(yùn)算，簡單易實(shí)現(xiàn)，實(shí)現(xiàn)了串行數(shù)據(jù)的輸入和串行數(shù)據(jù)的輸出；解碼采用了三級(jí)流水線操作，分三個(gè)模塊：伴隨式模塊，錯(cuò)誤位置多項(xiàng)式模塊和錢氏搜索

101、模塊。其中伴隨式模塊也是采用了線性反饋移位寄存器的方法，錯(cuò)誤位置多形式模塊沒有采用傳統(tǒng)的RIBM算法，而是采用了直接求解的算法，由XOR 和 AND邏輯實(shí)現(xiàn)，設(shè)計(jì)簡單，提高了速度，錢氏搜索采用了全并行的方法，其電路結(jié)構(gòu)為全并行的XOR-樹構(gòu)成的組合邏輯，在一個(gè)時(shí)鐘周期內(nèi)完成了碼字的糾錯(cuò)，大大提高了速度。</p><p>　　論文中的設(shè)計(jì)，采用了模塊化的手法，先對(duì)各模塊進(jìn)行設(shè)計(jì)，最后將各模塊連接起來，在時(shí)序上進(jìn)行統(tǒng)

102、一，形成一個(gè)頂層模塊。并對(duì)每一個(gè)模塊和頂層模塊進(jìn)行了仿真，得到了預(yù)期的仿真結(jié)果。</p><p><b>　　謝辭</b></p><p>　　本研究作為我的畢業(yè)論文是在教授精心指導(dǎo)和大力支持下完成的，他淵博的知識(shí)、開闊的視野和敏銳的思維給了我深深的啟迪，論文凝結(jié)著他的汗水。王教授以其嚴(yán)謹(jǐn)求實(shí)的治學(xué)態(tài)度、孜孜以求的敬業(yè)精神和大膽創(chuàng)新的進(jìn)取精神深深感染了我，對(duì)我今后的工

103、作和學(xué)習(xí)也產(chǎn)生了深遠(yuǎn)影響，在此，我要向他表示衷心的感謝。</p><p>　　另外，本論文在選題及整個(gè)研究過程中還得到本專業(yè)研究生三年級(jí)學(xué)生秦盼學(xué)姐的悉心指導(dǎo)，她們多次詢問論文進(jìn)程，幫我開拓思路，為我指點(diǎn)迷津，精心點(diǎn)撥，熱忱鼓勵(lì)，為我完成這篇論文提供了巨大的幫助。</p><p>　　最后，要向我的父親、母親致謝！“父兮生我，母兮鞠我，拊我蓄我，長我育我，顧我復(fù)我，出入腹我，欲報(bào)之德，昊天

104、罔極”，十月懷胎生我，含辛茹苦養(yǎng)我，長大又教我勤奮盡責(zé)、正直做人，這生我、養(yǎng)我、教我之恩，縱有三生我也無以回報(bào)！畢業(yè)后還要讀研，又要遠(yuǎn)離你們了，我在心中默默祈禱：希望你們能夠平安，健康。</p><p>　　現(xiàn)在，經(jīng)過幾個(gè)月的努力，我終于完成了我的畢業(yè)設(shè)計(jì)，這篇論文就是我的成果。在這個(gè)過程中，我要特別感謝我的導(dǎo)師王祖強(qiáng)老師，感謝他的悉心指導(dǎo)，感謝他給我的幫助和支持，謝謝！</p><p>

105、<b>　　參考文獻(xiàn)</b></p><p>　　[1] Liu W, Rho J, Sung W. Low-power high-throughput BCH error correction VLSI design for multi-level cell NAND flash memories. Proc. IEEE workshop on Signal Processing Sys

106、tems Design and Implementation,2006:303-308.</p><p>　　[2] Duann N. Error correcting techniques for future NAND flash memory in SSD applications Proceedings of Flash Memoty Summit,2009.</p><p>

107、　　[3] Vigoda B. Lyric error correction for flash memory. Proceeding of Flash Memory Sunnit,2010.</p><p>　　[4] Parhi K. K. Eliminating the Fan-out Bottleneck in Parallel long BCH Encoders, IEEE Trans. Circ

108、uits &Systems I,2004,51:512-516.</p><p>　　[5] Choi H, Liu W, Sung W. et al, VLSI implementation of BCH error correction for multilevel cell NAND flash memory. IEEE Trans. Very Large Scale Integr . (VLSI

109、)Systems,2010,18(5):843-847.</p><p>　　[5] 王雪強(qiáng). 快閃存儲(chǔ)器的低壓高可靠性技術(shù)研究[博士學(xué)位論文]. 北京： 清華大學(xué)微電子與納電子研究所， 2011.</p><p>　　[6] 許錦.NAND FLASH 快速BCH編解碼算法及硬件實(shí)現(xiàn)[碩士學(xué)位論文].上海：復(fù)旦大學(xué)電子與通信工程，2008.</p><p>　　[

110、7] 王杰，沈海濱.NAND Flash 控制器的BCH編/譯碼器設(shè)計(jì).杭州：浙江大學(xué)超大規(guī)模集成電路設(shè)計(jì)研究所，2010.</p><p>　　[8] 汪建國.BCH編譯碼器的設(shè)計(jì)及驗(yàn)證[碩士學(xué)位論文].上海：上海交通大學(xué)電子信息與電氣工程學(xué)院，2010.</p><p>　　[9] 張軍，王志功，胡慶生，肖潔.高速并行BCH(2184,2040)編碼器的VLSI優(yōu)化設(shè)計(jì).南京：東南大學(xué)

111、，2006.</p><p>　　[10]胡江.基于FPGA的BCH(23,11)碼編譯碼器的實(shí)現(xiàn).寧波：浙江萬里學(xué)院，2006.</p><p>　　[11]孫延鵬，李軒，王麗.基于FPGA的BCH(31,21)碼譯碼器的設(shè)計(jì).沈陽：沈陽航空工業(yè)學(xué)院電子工程系，2003.</p><p>　　[12] 陳志，黃世震，曾獻(xiàn)君.BCH解碼器面積優(yōu)化的VLSI設(shè)計(jì).福州