利用快速尋根電路發展之里德所羅門解碼器研究

Abstract

隨著時代不斷的改變與進步，網路通訊漸漸縮短了人與人之間的距離，其除了要求頻寬之外，也必須要求傳輸的正確性，若正確性無法達到一定的水準，會讓訊息產生一定程度的失真，造成使用者的不便。在我們下一代的超高速數位用戶線路（VDSL）應用中，錯誤更正編解碼（ECC）是採用里德所羅門碼（Reed-Solomon Code）的方式，而為了因應VDSL各種所需之規格，必須做到可程式化的硬體，可任意調整其錯誤更正能力。故我們設計了類似矽智財（SIP）合成器，由使用者自行輸入參數使其產生里德所羅門解碼器相關之硬體語言。以往其中尋找錯誤位置的方法，是將所有伽羅瓦場可能的元素，也就是所有可能發生錯誤的位置皆代入做測試，如此的作法，必將花費伽羅瓦場相當大的乘加運算量，時間也需耗費不少。本篇論文中所採用的尋根方式主要精神在於將代根的動作化為求二進位的多元一次聯立方程式，其可大大降低伽羅瓦場運算需求量，且整個尋根的時間也會縮短，這有助於改善里德所羅門解碼輸出的潛伏期。此特點有益於需做位元位置前後調換之里德所羅門解碼器架構，因為位元位置前後調換必須等所有輸出皆就緒才可以動作。

The thesis proposes a SIP (Silicon Intellectual Property) synthesizer of Reed-Solomon decoder with a fast root searching circuit. Given the degree of Galois Field and the capability of error correction, the synthesizer will generate a set of synthesizable RTL codes for realizing the Reed-Solomon decoder. Traditionally, published Reed-Solomon decoders use the Chien search algorithm to find the root of error-locator polynomial that features a simple hardware structure but takes long time to search the roots. For some applications, however, the Chien search algorithm may become a critical path to finish the Reed-Solomon decoding. In this thesis, we apply the BRS algorithm for fast root searching and develop an automatic approach to synthesize the root searching algorithm. As the result, our approach can reduce the latency by at most 47.3 percent and the synthesized SIP can perform the Reed-Solomon decoder correctly.