( 您好!臺灣時間:2021/04/20 19:06
字體大小: 字級放大   字級縮小   預設字形  


研究生(外文):Che-Wei Chang
論文名稱(外文):The IC design of a Long BCH code
  • 被引用被引用:0
  • 點閱點閱:292
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0

記憶體之錯誤更正碼設計已有一些相關研究。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 57
[1]Shu Lin, Daniel J. Costello,Jr., Error Control Coding, second ED, Prentice Hall.
[2]Robert H. Morelos-Zaragoza., The art of error correcting coding, Wiley, 2002.
[3]Jyh-Huei Guo and Chin-Liang Wang, “systolic array implementation of Euclid’s algorithm for inversion and division in GF(2^m),” IEEE, 1996.
[4]Yanni Chen , Keshab K. Parhi., “Small Area efficient parallel decoder architecture for long BCH codes,” IEEE Transaction on VLSI systems, vol. 12, No. 5, MAY, 2004.
[5]Arash Reyhani-Masoleh, M. Anwar Hasan, “Low Complexity Bit Parallel Architecture for Polynomial Basis Multiplication over ,” IEEE Transaction on Computers, vol.53, No. 8, AUGUST 2004.
[6]E.D. Mastrovito, “VLSI Designs for Multiplication over Finite Fields ,” Proc. Sixth Symp. Applied Algebra, Algebraic Algorithm, and Error Correcting Codes (AAECC-6), pp. 297-309, July1988.
[7]E.D. Mastrovito, “VLSI Architectures for Computation in Galois Fields” Ph D thesis, Linkoping Univ. Linkoping, Sweden, 1991.
[8]L. Song, M.-L. Yu, and M. S. Shaffer, “10- and 40-Gb/s forward error correction devices for optical communications” IEEE J. Solid-State Circuits, vol. 37, pp. 351-354.
[9]H. C. Chang, C. C. Lin, and C. Y. Lee, “A low power Reed-Solomon decoder for STM-16 optical communications “ in IEEE proc. Asia-Pacific Conf. ASIC, 2002, pp. 351-354.
[10]M. Potkonjak, M. B. Srivastava, and A. P. Chandrakasan, “Multiple constant multiplications: Efficient and versatile framework and algorithms for exploring common sub-expression elimination” IEEE Trans. Computer-Aided Design, vol. 15, pp. 151-165, Feb. 996.
[11]Hanho Lee, Meng-Lin Yu, Leilei Song “VLSI Design of Reed-Solomon Decoder Architectures” ISCAS 2000-IEEE International Symposium on Circuits and Systems, May 28-31, 2000.
[12]H. M. Shao, T. K. Truong, L. J. Deutsch, J. H. Yuen and I. S. Reed, “A VLSI Design of a Pipeline Reed-Solomon Decoder” IEEE Trans. on Computers, Vol. C-34, No. 5, pp. 393-403, May 1985.
[13]R.P. Brent and H.T. Kung, “Systolic VLSI arrays for polynomial GCD computations,” Dep. Comput. Sci., Carnegie-Mellon Univ., Pittsburgh, PA, Rep., 1982.
[14]Howard M. Shao, T. K. Truong, Leslie J. Deutsch, Joseph H. Yuen and Irving S. Reed, “A VLSI design of a pipeline Reed-Solomon decoder” IEEE Transactions on computers, vol. c-34, No.5, May 1985.
[15]Stephen B. Wicker, “Error control systems for digital communication and storage,” Prentice hall international, Inc.
[16]D. Rossi, C. Metra, B. Ricco,“Fast and compact error correcting scheme for reliable multilevel Flash memories”, IEEE International Workshop on Memory Technology, Design and Testing, MTDT 2002, Italy.
[17]R. Blahut, “Theory and Practice of Error Control Codes,” Addison-Wesley Co., 1983.
第一頁 上一頁 下一頁 最後一頁 top
1. 3.仲秋月,〈兩岸關係之研究--從柯林頓訪問中國大陸談起〉《中正學刊》,1998年11月, 頁164-169。
2. 24.邱政宗,〈美國與中國簽署加入WTO雙邊協議的經過與影響〉,《立法院院聞》,28卷11期,民89,頁111-126。
3. 21.金中燮,〈從「文明衝突論」到「民主和平論」─「非西方」如何成為威脅?〉,《東亞季刊》,民國87年春季,頁14。
4. 20.金惠珍,〈亞太區域多邊合作的發展與美國的角色〉,《美歐月刊》,民85,卷11期5,頁39-50。
5. 17.蔡瑋,〈由F-16軍售案看當前的美國─台灣─中共三角關係〉,《美國月刊》,民國81年11月,頁23-33。
6. 13.蔡瑋,〈美國與中共的關係:理想和現實的抉擇〉,《美國月刊》,1994年1月,頁52-63。
7. 12.張雅君,〈從圍堵理論剖析美國與中共的關係〉,《美歐月刊》,1995年12月,頁20-32。
8. 4.唐仁俊,〈兩岸關係中的美國因素〉,《中華戰略學刊》,1999年12月,頁71-105。
9. 16.李華夏,〈兩岸在WTO架構的調查〉,《經濟情勢暨評論》,民87年8月,頁156-164。
10. 14.裘兆琳,〈柯林頓政府對華新政策之決策過程探討〉,《美歐月刊》,1994年12月,頁4-17。
11. 11.張雅君,〈理想主義下布希對中共政策的困境〉,《美國月刊》,1992年1月,頁46-57。
12. 10.裘兆琳,〈美國續予中共最惠國待遇問題:府會之爭個案研究,1990-1992〉,《歐美研究》,民國82年6月,頁1-59。
13. 9.戴東清,〈兩岸關係中的民主問題〉,《共黨問題研究》,2001年2月,頁6-12。
14. 8.蔡政文,〈兩岸關係之發展: 中共對臺策略及我國因應之道〉《國立中山大學社會科學季刊》,1997年春,頁1-13。
15. 6.黃介正,〈美國政策研究智庫之特質與我應有之認識〉,《國家政策論壇民》,2001年12月,頁111-114。
系統版面圖檔 系統版面圖檔