臺灣博碩士論文加值系統

在科技快速進步的時代，無線化通訊科技也隨之蓬勃發展，例如手機通訊，WIMAX無線網路等。然而，雜訊干擾與資料錯誤遺失的問題也較以往嚴重。為了更正雜訊對資料所造成的錯誤與遺失，具有錯誤更正能力的「錯誤更正碼」在通訊系統中扮演著重要之角色。
Gao演算法則為Reed Solomon (RS)解碼法則中最簡單之一。 本研究以VHDL語言實現Gao演算法則，並下載至Xilinx VirtexII 嵌入式系統上加以驗證。在驗證過程中，首先擷取出語音檔數值，編碼後加入隨機亂數模擬資料傳輸時的雜訊干擾，並將受影響數值藉由個人電腦RS232界面傳送至嵌入式系統，進行Gao解碼器(實現Gao演算法則的硬體)運作，隨後將其結果傳回電腦。與原始的聲音作對照比較，以驗證此嵌入式系統的正確性。

In this modern era, the wireless communication technology has been vigorously developed, such as cell phone communication, WIMAX communication network and so on. However, the noise disturbance and data error and loss are more serious than ever. The technology of powerful error control coding plays an important role in these modern communication systems.
Gao’s algorithm is one of the simplest decoding algorithms to decode Reed Solomon codes. In this study, such a decoding algorithm is realized with VHDL, and downloaded into a Xillinx Virtex II embedded system for verification. In the verification course, firstly audio data in a certain song are fetched and encoded. These encoded data are interfered by random noises and then sent into Gao’s decoder, which is the hardware implantation of Gao’s algorithm, in the embedded system via an RS232 interface in a personal computer. After Gao’s decoding has performed, the decoded sequences are sent back in order to compare the original audio data and verify if the performance of this Gao’s decoder is exact or not.

目錄

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

第一章　緒論
1.1 前言．．．．．．．．．．．．．．．．．．．．1
1.2 研究動機．．．．．．．．．．．．．．．．．．2
1.3 全文架構．．．．．．．．．．．．．．．．．．2
第二章　Reed-Solomon碼原理
2.1 Reed-Solomon碼基本介紹．．．．．．．．．．．4
2.2 Reed-Solomon編碼演算法則．．．．．．．．．．6
2.2.1 生成多項式．．．．．．．．．．．．．．．6
2.2.2 Reed-Solomon編碼演算法則．．．．．．．．6
2.3 Reed-Solomon解碼演算法則．．．．．．．．．．8
2.4 Berlekamp-Massey演算法範例．．．．．．．．．11

第三章　Gao演算法實現Reed-Solomon編解碼
3.1 Gao演算法則概論．．．．．．．．．．．．．．16
3.2 Gao演算法則架構．．．．．．．．．．．．．．16
3.2.1 Gao編碼法則．．．．．．．．．．．．．．16
3.2.2 Gao解碼法則．．．．．．．．．．．．．．17
3.3 Gao演算法範例．．．．．．．．．．．．．．．18
3.4 Gao與Berlekamp-Massey編碼法則特色．．．．．24
3.4.1 Gao與Berlekamp-Massey編碼法則比較．．．24
3.4.2 Berlekamp-Massey解碼法則複雜度．．．．．25
3.4.3 Gao解碼法則複雜度．．．．．．．．．．．37
3.4.4 Gao與Berlekamp-Massey複雜度比較．．．．44
第四章　硬體實現與系統實驗設計
4.1 Reed-Solomon軟體模擬與嵌入式系統實現．．．．45
4.2 Reed-Solomon硬體電路實現．．．．．．．．．．48
4.3實驗流程設計與驗證．．．．．．．．．．．．．57
第五章　結論及未來展望
5.1 研究流程與解決問題．．．．．．．．．．．．．63
5.2 結論及未來展望．．．．．．．．．．．．．．．64
參考文獻．．．．．．．．．．．．．．．．．．．．．．．．66





圖目錄

圖1-1通訊系統．．．．．．．．．．．．．．．．．．．．．1
圖2-1線性方塊碼．．．．．．．．．．．．．．．．．．．．3
圖2-2 Parity Check Symbols．．．．．．．．．．．．．．．．7
圖2-3 Reed-Solomon編碼電路．．．．．．．．．．．．．．．8
圖2-4 Reed-Solomon 編碼電路．．．．．．．．．．．．．12
圖2-5通道雜訊干擾．．．．．．．．．．．．．．．．．．．13
圖3-1通道出現雜訊干擾．．．．．．．．．．．．．．．．．19
圖3-2 Gao解碼法則概念．．．．．．．．．．．．．．．．．23
圖3-3 Berlekamp-Massey演算法則流程圖．．．．．．．．．．25
圖3-4 Gao演算法則流程圖．．．．．．．．．．．．．．．．37
圖4-1嵌入式控制系統．．．．．．．．．．．．．．．．．．46
圖4-2超級終端機介面．．．．．．．．．．．．．．．．．．47
圖4-3加法電路圖．．．．．．．．．．．．．．．．．．．．49
圖4-4乘法電路圖．．．．．．．．．．．．．．．．．．．．50
圖4-5編碼器示意圖．．．．．．．．．．．．．．．．．．．51
圖4-6編碼電路方塊圖．．．．．．．．．．．．．．．．．．52
圖4-7 Interpolation電路方塊圖．．．．．．．．．．．．．．53
圖4-8 Partial gcd電路方塊圖．．．．．．．．．．．．．．．54
圖4-9 Long division電路方塊圖．．．．．．．．．．．．．．55
圖4-10 Gao演算法則電路方塊圖．．．．．．．．．．．．．56
圖4-11設計實驗流程圖．．．．．．．．．．．．．．．．．57
圖4-12語音檔開啟．．．．．．．．．．．．．．．．．．．58
圖4-13編碼前的資料處理．．．．．．．．．．．．．．．．59
圖4-14 Gao編碼處理．．．．．．．．．．．．．．．．．．59
圖4-15雜訊干擾比對．．．．．．．．．．．．．．．．．．60
圖4-16錯誤更正後聲音檔．．．．．．．．．．．．．．．．61
圖4-17受干擾未更正聲音檔．．．．．．．．．．．．．．．61
圖4-18原始聲音檔．．．．．．．．．．．．．．．．．．．62
圖4-19受干擾錯誤更正後聲音檔．．．．．．．．．．．．．62

















表目錄

表 2-1 Reed-Solomon碼參數說明．．．．．．．．．．．．．．4
表2-2 的對照表．．．．．．．．．．．．．．．．．．5
表 2-3 Berlekamp-Massey疊代運算的初始化．．．．．．．．．9
表2-4 編碼電路時脈運作．．．．．．．．．．．．．．．12
表2-5 代數與回授電路複雜度比較．．．．．．．．．．．13
表2-6 疊代運算初始化．．．．．．．．．．．．．．．．14
表2-7 疊代運算流程．．．．．．．．．．．．．．．．．14
表 3-1 的對照表．．．．．．．．．．．．．．．．．．18
表 3-2 Partial gcd運算初始化．．．．．．．．．．．．．．．22
表 3-3 Partial gcd運算過程．．．．．．．．．．．．．．．．22
表 3-4 Gao編碼與Berlekamp-Massey編碼法則特色．．．．．．24
表 3-5特徵值 計算複雜度．．．．．．．．．．．．．．．．26
表 3-6差異參數 計算複雜度．．．．．．．．．．．．．．．28
表 3-7 修正複雜度．．．．．．．．．．．．．．．．．30
表 3-8錯誤位置計算複雜度．．．．．．．．．．．．．．．．31
表 3-9估算多項式 計算複雜度．．．．．．．．．．．．．32
表3-10錯誤樣本 計算複雜度．．．．．．．．．．．．．．34
表3-11錯誤更正的計算複雜度．．．．．．．．．．．．．．35
表 3-12 Berlekamp-Massey解碼法則複雜度．．．．．．．．．36
表 3-13 Interpolation高斯消去法複雜度．．．．．．．．．．．40
表 3-14 Partial gcd運算流程．．．．．．．．．．．．．．40
表3-15 Partial gcd運算流程．．．．．．．．．．．．．41
表3-16 Partial gcd的 的計算複雜度．．．．．．．．．．．42
表3-17 Partial gcd運算過程．．．．．．．．．．．．．．．．42
表3-18 Partial gcd的 的計算複雜度．．．．．．．．．．．43
表3-19 Partial gcd運算複雜度．．．．．．．．．．．．．．．43
表3-20 Long division運算複雜度．．．．．．．．．．．．．43
表3-21 Gao解碼法則複雜度．．．．．．．．．．．．．．．44
表 3-22 Gao與Berlekamp-Massey解碼法則複雜度比較．．．．44
表 4-1 符元對應數字表．．．．．．．．．．．．．．．47
表4-2 加法電路 時脈運作．．．．．．．．．49
表4-3 乘法電路 時脈運作．．．．．．．．．50

參考文獻

[1]Shuhong Gao, “A NEW AlGORITHM FOR DECODING REED-SOLOMON CODES”
[2]Sergei V. Fedorenko, Member “A simple algorithm for decoding Reed-Solomon codes and its relation to the Welch-Berlekamp algorithm”
[3]S. Lin and D.J. Costello, Jr, “Error Control Coding”, 2nd edition Prentice Hall, 2004
[4]黃偉凱,“Implementation of Euclidean Algorithm Based on Embedded System”, 大葉大學電信工程學系碩士班碩士論文, 2007
[5]劉紹漢、林灶生, “VHDL晶片設計，使用ISE、Modelsim發展系統”, 全華科技圖書, 台北,2004。
[6]唐佩忠, “ VHDL與數位邏輯設計” ,高立圖書,2004
[7]王小川, “語音訊號處理”, 全華科技圖書, 出版二刷2005年2月。
[8]劉紹漢、林灶生, “SOC系統晶片設計使用Xilinx EDK”,全華科技圖書, 2006年7月。
[9]劉紹漢、林灶生, “FPGA晶片設計與專題製作”, 全華科技圖書, 2004年6月。