在資訊蓬勃發展的時代，確保資訊在傳輸和儲存過程中的正確性變得相當重
要。由於快閃記憶體的製程和存取壽命有密切關係，同一區塊存取的次數過多，
該區塊發生資料錯誤的機率相對高。為了確保可以讀取到正確的訊息，糾錯碼在
快閃記憶體上的應用是一個有經濟效益的選擇，其中以BCH 碼最佳。然而傳統序
列式BCH 編解碼不利於大量訊息的即時傳輸，平行化BCH 編解碼法遂漸受到重
視。
傳統平行化BCH 解碼演算法是利用生成多項式的根帶入訊息多項式以取得
症狀值，再用症狀值求得錯誤位置多項式，後利用Chien 演算法搜尋出錯誤位置
並進行錯誤資訊改正，此計算過程相當複雜且費時。本論文提出一種直接由接收
到的訊息求得錯誤位置的演算方式；首先建立訊息位置、症狀值與錯誤位置間的
相對應關係，再利用此相對應關係簡化解碼過程，以達到較佳的平行解碼架構。
解碼效益的評估，將就該解碼方式所需的電晶體數量，和所需的邏輯閘數量進行
面積與延遲的比較。

Development in the information, make sure the information correct is very
important in the transmission and storage process. Because the process of flash
memory, if access to the same block too many times, easy error occurred on the block.
To ensure that the right message can be read, error-correcting codes is very important
in the application of flash memory, which BCH code optimization. However, the
traditional serial BCH code is not good at a large number of real-time transmission of
the message, parallelizing BCH code becomes quite important.
Traditional parallel BCH decoding algorithm is used the root of generator
polynomial into the message polynomial for syndrome and use the syndrome to
calculator key equation, final use chien’s search to search the error location and
correct, this calculation very complex and long time. This paper presents an directly
algorithms to find the error location from the received message; First, create a
relationship between the information, syndrome and the error location. Using this
relationship then simplify the decoding process to the fastest parallel decoding
architecture. This paper presents an directly algorithms to find the error location from
the received message; First, create a relationship between the information, syndrome
and the error location. Using this relationship then simplify the decoding process to
achieve a better parallel decoding architecture. About benefit evaluation of decoding,
we against the number of transistor required in this decoding method and the required
number of logic gate to compare area and delay.

中文摘要-------------------------------------- I
英文摘要-------------------------------------- II
誌謝------------------------------------------III
圖目錄-----------------------------------------VI
表目錄---------------------------------------- VII
第一章 緒論------------------------------------- 1
1.1 研究動機--- -------------------------------- 1
1.2 糾錯碼簡介---------------------------------- 3
1.3 論文架構簡介--------------------------------- 5
第二章 理論背景----------------------------------- 6
2.1 群(Group)--------------------------------- 6
2.2 環(Ring)------------------------------------- 6
2.3 場(Field)----------------------------------- 7
2.4 二元場(Binary Field)------------------------- 8
2.5 延展二元場(Extension Field)------------------- 9
第三章 BCH 碼之編解碼介紹 -------------------------- 14
3.1 BCH 碼基本定義-------------------------------- 14
3.2 BCH 編碼 ------------------------------------ 16
3.3 BCH 解碼------------------------------------- 17
3.3.1 症狀值多項式(Syndrome polynomial)------------- 17
3.3.2 錯誤位置多項式σ(x)(error location polynomial)-- 18
3.3.3 Berlekamp-Massey algorithm------------------- 21
3.3.4 Chien 找尋演算法(Chien-search Algorithm)------- 26
3.4 BCH 碼之基本編解碼流程---------------------------- 27
3.5 BCH 碼解碼實現之相關文獻-------------------------- 28
第四章 平行化BCH 解碼器的直接解碼法--------------------- 29
4.1 症狀值計算器(Syndrome Calculator)----------------- 29
4.2 錯誤位置解碼器(Error Location Decoder)------------ 32
4.3 傳統解碼法與直接解碼法比較-------------------------- 36
4.3.1 傳統解碼法--------------------------------------- 36
4.2.2 直接解碼法--------------------------------------- 37
第五章 實驗結果----------------------------------------- 38
5.1 硬體成本計算---------------------------------------- 38
5.2 速度延遲分析---------------------------------------- 49
第六章 結論-------------------------------------------- 51
6.1 結論 --------------------------------------------- 51
6.2 未來展望------------------------------------------ 51
參考文獻----------------------------------------------- 53

[1]S. Lin and D. J. Costello, Error Control Coding: Fundamentals and Applications, Prentice-Hall Inc., Englewood Cliffs, NJ, second edition, 2004.
[2] Tood K. Moon, Error Correction Coding: Mathematical Methods and Algorithms, John Wiley& Sons, New York, 2005 in Proc. IEEE Int’ Solid-State Cir. Conf. (ISSCC), 2006, pp. 497–506.
[3] Yunghsiang S. Han “Decoding BCH/RS Codes
[4] J. L . Massey, “Shift-register synthesis and BCH decoding”, IEEE Trans. on Information Theory,vol. 15, pp. 122–127, 1969.
[5] Strukov, “The area and latency tradeoffs of binary bit-parallel BCH 54 decoders for prospective nanoelectronic memories,” in Proc. ACSSC Papers, May 2007, pp. 1183–1187.
[6] Wang Xueqiang, Member, IEEE, Pan Liyang, Wu Dong, Hu Chaohong, and
Zhou Runde” A High-Speed Two-Cell BCH Decoder for ErrorCorrecting
in MLC NOR Flash Memories”