林茂昭臺灣大學：電信工程學研究所張哲濰Chang, Che-WeiChe-WeiChang2007-11-272018-07-052007-11-272018-07-052005http://ntur.lib.ntu.edu.tw//handle/246246/58912由於新一代的快閃記憶體儲存單元越來越小，資料的干擾問題和維持問題卻變的越來越嚴重，也因此降低了記憶體的可靠度。因此錯誤更正碼得研究也越來越重要。 記憶體之錯誤更正碼設計已有一些相關研究。BCH 和 RS 碼是其中兩種最有效的代數碼也是最廣泛使用的方式。在不同之錯誤型態及不同之訊息位元數、檢查位元數等考量之下有多種不同之設計。本論文針對位元已經過擾亂器(interleaver)之處理且錯誤發生率可視為獨立(independent)之情形，考慮BCH(8191,8087,t=8)作編解碼設計。此系統中整合各種先進的架構，其中平行架構可以應用在徵狀(syndrome)區塊及Chien 搜尋區塊減少時脈週期數目，使用修正的歐幾里德的演算法可以解出關鍵方程式，還有分組匹配演算法可以有效降低Chien搜尋區塊乘法器的複雜度，最後將以Xilinx FPGA模擬其效能。In new-generation Flash memories, issues such as disturbs and data retention become more and more critical as a consequence of reduced cell size, and hence it will decrease the reliability of memories. Then, the research of error control coding becomes very important. There are already some researchs of the hardware design of error correcting code in storage equipments. BCH and RS codes form the core of the most powerful known algebraic codes and are widely used .In this thesis, we focus on the encoder/decoder design of BCH(8191,8087,t=8) code under the condition that the error probabily of all bits are independent due to interleaver operation. We integrate various advanced architecture in our system. The parallel architecture is used to syndrome block and Chien search block in order to reduce system’s clock cycles. Modified Euclidean algorithm is chosen to solve the key equation. And group matching algorithm is to minimize the complexity of the multipliers in Chien search architecture. Finally, the encoder/decoder architecture will be confirmed and simulated by XilinxFPGA.Chapter 1.Introduction 1 Chapter 2.Overview of BCH codes 5 2-1.BCH codes 5 2-2.Encoder of BCH code 5 2-3.Decoder of BCH code 8 2-3-1.Syndrome polynomial 9 2-3-2.Key equation 9 A.Greatest Common Divisor (GCD) 11 B.Euclidean algorithm 12 C.Modified Euclidean Algorithm 13 D.Extended GCD Problem 14 2-3-3.Chien search 16 Chapter 3.Hardware Design of BCH the code 17 3-1.Hardware design of multiplier 17 3-1-1.Polynomial Basis Multiplication over 17 3-1-2.Low complexity bit parallel (LCBP) multiplier 20 3-2.BCH encoder architecture 23 3-3.BCH decoder architecture 24 3-3-1.Syndrome generator 24 3-3-2.Solving key equation 26 A.Euclidean algorithm 26 B.Modified Euclidean algorithm architecture 27 3-3-3.Chien search architecture 29 A.Iterative Matching Algorithm 32 B.Concept of Group Matching 3 Chapter 4.Simulation Results 39 4-1.Multiplier 39 4-2.Encoder 41 4-3.Decoder 42 4-3-1.Syndrome generator 42 4-3-2.Modified Euclidean algorithm 44 4-3-3.Chien search 46 4-3-4.Encode/Decode Module and Correct Module 50 4-4.Results 52 Chapter 5.Conclusions 55 Bibliography 57473508 bytesapplication/pdfen-US碼設計硬體BCHcodeICthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/58912/1/ntu-94-R92942070-1.pdf