臺灣博碩士論文加值系統

Reed-Solomon(RS)碼是一個功能強大的錯誤更正碼，其優點是對隨機型或連續型錯誤進行改錯能力，目前可應用在許多的系統上。Feng-Tzeng演算法則是Berlekamp-Massey演算法則的延伸型，適用於RS解碼的演算法。針對一矩陣，Feng-Tzeng演算法則可產生最短的線性相依多項式。
在本研究中，我們以VHDL實現Feng-Tzeng演算法則，並下載至Xilinx VirtexII 嵌入式系統上加以驗證。在驗證過程中，首先設定某一數值，編碼後加入隨機亂數模擬雜訊的干擾，並將受影響數值藉由個人電腦RS232界面傳送至嵌入式系統。經由Feng-Tzeng演算法則，再進行錯誤位置與錯誤值的計算。當找出錯誤樣本後，進行更正錯誤的運作，隨後再將改正後資料傳回個人電腦，並與原設定數值比較，以驗證Feng-Tzeng演算法則合成電路的正確性。

The Reed-Solomon (RS) ode is a kind of powerful error control code, which can correct burst errors and the random errors. RS codes have been applied in many systems. The Feng-Tzeng algorithm is an extension of the Berlekamp-Massey, and it is used to decode RS codes. This algorithm can produce a shortest polynomial linearly dependent on a given matrix.
In this thesis, the Feng-Tzeng algorithm is realized with VHDL, which is downloaded the Xilinx VirtexII embedded system for verification. Firstly, a codeword of an RS code is generated and interfered by random noises and then sent into an embedded system via an RS232 interface in a personal computer. After the Feng-Tzeng decoder, which is the hardware of Feng-Tzeng decoding, has performed, the decoded sequence is sent back in order to compare the original data and verify if the performance of this Feng-Tzeng decoder is exact or not.

封面內頁
簽名頁
授權書．．．．．．．．．．．．．．．．．．．．．．．．．iii
中文摘要．．．．．．．．．．．．．．．．．．．．．．．．iv
英文摘要．．．．．．．．．．．．．．．．．．．．．．．．v
誌謝．．．．．．．．．．．．．．．．．．．．．．．．．．vi
目錄．．．．．．．．．．．．．．．．．．．．．．．．．．vii
圖目錄．．．．．．．．．．．．．．．．．．．．．．．．．ix
表目錄．．．．．．．．．．．．．．．．．．．．．．．．．xi

第一章　緒論
1-1 前言．．．．．．．．．．．．．．．．．．．．1
1-2錯誤碼簡介．．．．．．．．．．．．．．．．．2
1-3 全文架構．．．．．．．．．．．．．．．．．．4
第二章　有限場元素的基本運算
2-1群與場．．．．．．．．．．．．．．．．5
2-1-1 群(Group)．．．．．．．．．．．．．．5
2-1-2場(Field)．．．．．．．．．．．．．．．7
2-2有限場 的基本運算．．．．．．．．．．．． 12
2-2-1加法(Addition)與減法(Subtraction)．．．． 12
2-2-2 乘法(Multiplication)．．．．．．．．． ．． 13
2-2-3乘法反元素與除法．．．．．．． ．．．．13
第三章 Feng-Tzeng演算法原理與流程
3-1前言．．．．．．．．．．．．．．．．．．．．． 14
3-2里德所羅門碼(Reed-Solomon)演算法．．．．．． 14
3-2-1里德所羅門碼編碼演算法則．．．．．．．． 15
3-2-2里德所羅門碼解碼演算法則．．．．．．．． 18
3-3 Feng-Tzeng演算法．．．．．．．．．．． ．．．21
3-4分析與比較．．．．．．．．．．．．．．．．．31
第四章 Feng-Tzeng演算法電路與模擬結果
4-1硬體電路設計．．．．．．．．．．．．．．．．40
4-1-1加法器．．．．．．．．．．．．．．．．． 40
4-1-2Mastrovito乘法器．．．．．．．．．．．． 41
4-2 實驗流程設計與驗證．．． ．．．．．．．．． 47
第五章　結論．．．．．．．．．．．．．．．．．．．．． 51
參考文獻．．．．．． ．．．．．．．．．．．．．．．．．52

[1]Gui-Liang Feng and Kenneth K.Tzeng “A Generalization of the Berlekamp-Massey Alogorithm for Multisequence Shift-Register Synthesis with Applications to Decoding Cyclic Code” IEEE Transactions Information Theory,VOL.37,NO.5.SEPTEMBER 1991 , pp.1274-1286
[2]S.Lin and D.J. Costello, Jr, “Error Control Coding”, 2nd edition Prentice Hall, 2004
[3]Nicola Petra,Davide De Caro Antonio G.M Strollo “A Novel Architecture for Galois Fields Multipliers Based on Mastrovito Scheme” IEEE Transactions On Computers，VOL.56,NO.11,NOVEMBER 2007,pp1470-1475
[4]黃維凱,” 用嵌入式系統實現歐基里德演算法”大葉大學電信工程學系碩士班碩士論文 ,2007
[5]陳政雄”A Low-complexity VLSI architecture of the Reed-Solomon codec”中正大學 電機工程研究所,2001
[6]張志瑋,“適用於數位通訊系統之里德所羅門編解碼模組”,中正大學 電機工程研究所碩士論文 ,2003
[7]謝瑋霖,“適用於數位電視之里德所羅門編解碼硬體實做”,中央大學 通訊工程研究所碩士論文 ,2005
[8]陳宗佑,”以嵌入式系統實現里德所羅門關聯性錯誤解碼器” 大葉大學 電信工程學系碩士班碩士論文 ,2007
[9]唐珮忠”VHDL與數位邏輯設計”高立圖書有限公司,2004
[10]林灶生.劉紹漢”最新VHDL晶片設計使用ISE、MODELSIM發展
系統”全華科技圖書股份有限公司,2005
[11]周文正”以FPGA為基礎完成二位元BCH code 步階式解碼電路之實現”大葉大學 電信工程學系碩士班碩士論文 ,2006