臺灣博碩士論文加值系統

錯誤更正碼對於數位通訊而言，其重要性不言可喻，而RS Code更是目前被廣泛應用於數位通訊與儲存媒體中，做為錯誤更正碼之演算法應用，並更正通道所引起的錯誤。對於叢集錯誤(Bursty Error)與隨機錯誤(Random Error)，RS Code可以提供極佳的錯誤更正能力，因此成為經常使用的通道編碼方式。
本論文著重在解碼器的部分，以修正過的歐基里德演算法(MEA, Modified Euclidean Algorithm)為基礎，並導入線性回饋位移暫存器(LFSR, Linear Feedback Shift Register)的概念：通常使用歐基里德演算法時，會利用最大公因素法，不斷地用遞迴方式找出商和餘數，大量的使用到乘除和加法運算而降低了運算速度，若使LFSR的架構，便可用除法電路來代替，且降低所需各運算器的數目以簡化電路。再加上去除Timing Control限制之方法，並佐以c語言程式驗證，最後用(VHDL, Very High Speed Integrated Circuit Hardware Description Language)模擬出我們所提出的架構。

It is very important that error correct coding for digital communication. RS code is even more popularly application on digital communication and storage medium as error correct coding algorithm and correct the error by channel. For bursty error and random error, RS code can provide excellent error correct capability. So it is used for channel coding usually.
This paper emphasizes on the part of decoder and bases on modified Euclidean algorithm to enter a concept of linear feedback shift register in it. When we use Euclidean algorithm to arithmetic, we often employ great common division to solve quotient and remainder with recursion continuously. It greatly makes use of the operation of addition and multiplication that result in decreasing the speed of calculation. If we use the architecture of LFSR, we could take place of multiplication by division and reduce the number of arithmetic unit to simplify circuit. After that we find the method of ridding of timing control and check with c program. Finally, we simulate the produced architecture by VHDL.

誌謝…………………………………………………………………………………...ii
摘要…………………………………………………………………………………..iii
ABSTRACT………………………………………………………………………….iv
目錄…………………………………………………………………………………...v
表目錄 ……………………………………………………………………………….vii
圖目錄 ………………………………………………………………………………viii
辭彙、符號說明和縮寫……………………………………………….......................x
1. 緒論………………………………………………………………………………1
1.1 前言 1
1.2 編碼通訊簡介 2
1.3 編碼通訊的演進及類別 4
2. Galois Field 原理介紹…………………………………………………………..6
2.1 群及場 6
2.2 Galois Field 建構 11
2.2.1 Galois Field 基本性質 12
2.2.2 Galois Field 運算 13
2.2.3 Galois Field 向量空間 17
3. Reed-Solomon 碼理論…………………………………………………………19
3.1 原理探討 19
3.2 編碼 21
3.3 解碼 23
3.3.1歐幾里德演算法 27
3.3.2 LFSR 導入 33
4. 電路設計與模擬驗證…………………………………………………………..38
4.1 電路設計 38
4.1.1 加法 39
4.1.2 乘法 40
4.1.3 除法 42
4.1.4 餘式電路 43
4.1.5 RS code編碼器 45
4.1.6 Syndrome電路 47
4.2 模擬與驗證 48
4.2.1 解碼架構 48
4.2.2 軟體模擬驗證 49
5. 實驗結果與測試………………………………………………………………..50
5.1 實驗測試 50
5.1.1 RS code (7,3,5)測試 50
5.1.2 RS code (255,223,33)測試 54
5.2 程式燒錄 58
6. 結論與未來展望………………………………………………………………..59
6.1 結論 59
6.2 未來展望 59
參考文獻…………………………………………………………………………….60
自傳………………………………………………………………………………….62

[1]Lin, G. J., “Introduction and Background of Encoding Modulation,” Information and Communication Research Division Chung-Shan Institute of Science and Technology, Taoyuan, R.O.C., pp. 79-96, 2005.
[2]Song, M. K., Kim, E. B., Won H. S., and Kong, M. H., “Architecture for Decoding Adaptive Reed-Solomon Codes with Variable Block Length,” IEEE Trans. on Consumer Electronics, Vol. 48, No. 3, pp. 631-637, August, 2002.
[3]Lee, H., “Modified Euclidean Algorithm block for High Speed Reed-Solomon Decoder,” IEE Electronics Letters Online, Portland, U.S.A., Vol. 37, N0. 14, pp. 903-904, July, 2001.
[4]謝坤宏，“微小化面積里德－所羅門解碼器之設計與實現”，碩士論文，國立交通大學電信工程研究所，新竹，2003。
[5]黃柏涵，“利用快速尋根電路發展之里德所羅門解碼器研究”，碩士論文，國立交通大學電機與控制工程研究所，新竹，2003。
[6]陳政雄，“利用VLSI設計一低複雜度的RS編/解碼架構”，碩士論文，國立中正大學電機工程研究所，嘉義，2001。
[7]黃伊德，“里德-所羅門解碼器之研究”，碩士論文，國立成功大學工程科學研究所，台南，2001。
[8]張志瑋，“適用於數位通訊系統之里德所羅門編解碼模組”，碩士論文，國立中正大學電機工程研究所，嘉義，2003。
[9]陳世俊，“以FPGA為基礎，互補碼調變(CCK)軟性解碼器之實現”，碩士論文，國防大學中正理工學院電子工程研究所，桃園，2005。
[10]袁國元，“利用RS-Code編解碼積體電路實現高可靠度磁碟陣列之研究”，碩士論文，私立義守大學資訊工程研究所，高雄，2000。
[11]楊家禎，“(255,223,33)RS碼與一些二次剩餘碼(QR)的結合分析”，碩士論文，私立義守大學資訊工程研究所，高雄，2003。
[12]劉紹漢、林灶生、劉新民，VHDL晶片設計，全華科技圖書，台北，第7-33頁，2004。
[13]陳榮、陳華，精通VHDL晶片設計，碁峰資訊，台北，第5-12頁，2003。
[14]日向俊二，C/C++辭典，博碩文化，台北，第128頁，2003。
[15]Deitel, H. M. and Deitel, P. J., C How to program, Prentice Hall, Third Edition, New Jersey, pp. 455, 2001.
[16]張錫嘉、林建青，“錯誤更正碼之設計與系統晶片實現”，國立中興大學電機工程學系/孟堯晶片中心系統晶片(SOC)基頻通訊設計研討會，臺中，第41-42頁，2005。
[17]CIC訓練課程，“FPGA Design with ISE Foundation”，國科會國家晶片系統設計中心，新竹，第13-14頁，2004。