Abstract
近幾年來,由於代數幾何技巧的引進,使得代數幾何碼成為資訊理論之一重要研究方向.狹義的說,代數幾何碼可視為現今被工業界廣泛使用之里德-所羅門碼的推廣.代數幾何碼的理論研究包括編碼及解碼演算法則.代數幾何碼的解碼程序和BCH碼的解碼程序類似,基本上可分為四個步驟:計算徵狀 (syndrome)值,找出錯誤位置多項式,找出多項式的根,計算伴隨錯誤位置的錯誤值大小.這些步驟在本篇論文中都加以一一詳細探討. Feng-Rao理論是一個在代數幾何碼解碼上相當成功的演算法則.然而到目前為止尚未有人提出這個演算法則的硬體架構.在本篇論文中,我們改良Feng- Rao演算法則使得其更具有平行架構,硬體實現更加容易.由於平行處理,因此解碼速度可以加快.此外,透過充份利用徵狀(syndrome)矩陣的對稱性質,我們大大降低此架構的硬體複雜度.我們所提出的這套心臟收縮式陣列架構的硬體複雜度為t^3/6+t^2/2-2t/3+gt,式中t為此碼的錯誤更正能力,g(genus)則由選定曲線所決定.這樣的硬體複雜度相當於對一個大小為t的方陣作高斯消去法所需的乘法個數.在我們所提出的這個架構中,控制電路很簡單.同時藉由Synopsys所發行的套裝軟體輔助,我們已經完成一些產生必要控制訊號的線路.另外,我們也提出一套可以執行在Feng-Rao演算法則中不可或缺的多數決 (majority voting scheme) 線路.Feng-Rao algorithm is a successful algorithm for the decodingof algebraic-geometric (AG) codes. However, there is noimplementation of this algorithm up to now. In this thesis, wehave modified the Feng-Rao algorithm to have more parallelismand developed a systolic array architecture for VLSIimplementation. The symmetry property of the syndrome matrixhas been exploited to reduce the complexity of thisarchitecture. The complexity of our proposed systolic arrayarchitecture is t^3/6+(1+g')t^2/2+[(g-3)g'/2-2/3+g]t, which iscomparable to that elimination on a square matrix with matrixsize equal to t, where t is the error-correcting capability ofa code, g is the genus of the curve, and g'=\floor(g-1/2). Thecontrol circuit in oursimple. Besides, we have also proposed acircuitry to perform the majority voting scheme needed in theFeng-Rao algorithm with the consideration that the candidatesare q-ary symbols.