里德所羅門碼之運算分析

Abstract

里德所羅門碼因具有良好更正叢集錯誤之能力而成為目前許多通訊系統所選用的錯誤更正碼。本論文將由演算法的基礎理論到運算電路分析來探討里德所羅門碼的編解碼機制，解碼端主要以有效率的代數硬式決策解碼演算法為研究對象，因為在硬體設計複雜度的考量下，硬式決策解碼器仍是最佳選擇，也是至今常被大家採用的解碼器。解碼程序繁複，於計算徵狀值流程後，在此我們以最廣為人知的Berlekamp-Massey演算法、Chien's search演算法和Forney演算法為分析要點。本論文將以詳細分析編解碼器之各個演算法單元的運算電路為主軸，再搭配使用C語言來進行編解碼器的運算設計與驗證，並利用Verilog硬體描述語言來進行硬體設計，最後再透過ModelSim軟體來驗證模擬結果之正確性。

Because of the capability to correct burst errors, Reed-Solomon codes are known as one of the widespread error-correction codes in many communication systems currently. In this thesis, we research Reed-Solomon codec from basic theory of algorithms to analysis of operational circuit. For the decoding, the efficient algebraic hard-decision decoding algorithms are our main subject, since the hard-decision decoder is still the best and widely-used one so far in consideration of hardware complexity. We primarily analyze well-known Berlekamp-Massey Algorithm, Chien’s search Algorithm, and Forney Algorithm after syndrome computation for the complicated decoding procedure. The object of this thesis is the detailed analysis for the operational circuits of each algorithm module in the codec. We use C language and Verilog HDL to design and verify the codec function respectively. Finally, some ModelSim simulations are performed in order to validate the correctness of each module.