臺灣博碩士論文加值系統

在廣播系統中，很多數位訊號的應用都利用直接錯誤更正碼，它是將多餘的資訊加上原本訊號，以利於被通道干擾之訊號能偵測並更正。在多種錯誤更正碼被發展出來中，以編碼效率及硬體複雜度而言，里德所羅門碼被證實是較好的錯誤更正碼。至今，里德所羅門碼以在廣播系統中被廣泛使用，如在ETSI數位地面電視廣播系統(DVB-T)標準的通道編碼規格，RS(204，188，8) 。

本論文主要是針對數位地面電視廣播系統標準的通道編碼規格來作硬體實現。以Verilog硬體描述語言，並透過Modelsim軟體進行模擬，確認我們的RS(204，188，8)程式可更正錯誤後，在利用合成軟體Synplify合成RTL硬體。

Many digital signaling applications in broadcasting use Forward Error Correction, a technique in which redundant information is added to the signal to allow the receiver to detect and correct errors that may have occurred in transmission. Many different types of code have been devised for this purpose, but Reed-Solomon codes have proved to be a good compromise between efficiency and complexity. Reed-Solomon error correction has several applications in broadcasting, in particular forming part of the specification for the ETSI digital terrestrial television standard, known as DVB-T.

In this thesis, we applied the specification for the ETSI digital terrestrial television standard(DVB-T) to realize the hardware implementation of Reed-Solomon decoder. Using Verilog Hardware Description Language and simulating by software “Modelsim” to confirm our program of RS(204,188,8) are fine and can correct errors which result from bad channel. Then, synthesizing logic-RTL by Synplify.

目錄
中文摘要....................................................................................................................... I
英文摘要......................................................................................................................Ⅱ
致謝..............................................................................................................................III
目錄………………………………………………………………………………..…Ⅳ
圖目錄………………………………………………………………………………..Ⅵ
表目錄………………………………………………………………………….…... Ⅷ
第一章 緒論 1
1.1 簡介 1
1.2 數位通訊系統 2
1.3 錯誤保護及更正碼的簡介、類別與發展 3
1.4 論文架構 4
第二章 地面數位電視廣播系統介紹 6
2.1 數位電視廣播簡介與發展 6
2.2 DVB-T系統傳輸的標準規格 9
2.2.1 MPEG-2訊息源編碼與多工器 9
2.2.2 資料隨機擾碼（Data Randomizer） 10
2.2.3 外編碼（Outer Coder） 11
2.2.4 外間插（Outer Interleaver） 12
2.2.5 內編碼（Inner Coding） 13
2.2.6 內間插（Inner Interleaver） 15
2.2.7 訊號星雲圖與調變（Signal Constellations and Mapping） 16
2.2.8 COFDM調變（COFDM Modulation） 16
2.2.9 圖框結構（Frame Adaptation） 18
2.2.10 導引信號與TPS信號（Pilot & TPS Signal） 19
2.2.11 OFDM原理 23
2.2.12 保護間隔插入（Guard Interval Insertion） 24
第三章 里德所羅門碼編解碼原理與流程 37
3.1 加洛瓦場（Galois Field）元素的建立與基本運算 37
3.1.1 場的性質與加洛瓦場（Galois Field）元素的建立 37
3.1.2 加洛瓦場（Galois Field）基本四則運算 39
3.2 里德所羅門碼（Reed-Solomon Code）定義與參數 41
3.3 里德所羅門碼之編碼 42
3.4 里德所羅門碼之解碼 44
3.4.1 計算徵狀值（Syndrome Computation） 48
3.4.2 求出錯誤位置多項式（Error Location Polynomial）與錯誤值多項式（Error Magnitude Polynomial） 47
3.4.3 尋找錯誤位置之方法（Chien Search） 50
3.4.4 尋找錯誤值大小方法（Forney Algorithm） 50
第四章 里德所羅門碼解碼電路與模擬結果 53
4.1 里德所羅門碼解碼器之運作流程與硬體架構 53
4.2 硬體電路設計 55
4.2.1 加洛瓦場加減法器 55
4.2.2 加洛瓦場乘法器 56
4.2.3 加洛瓦場除法器 57
4.2.4 癥狀計算（Syndrome）硬體架構 57
4.2.5 計算錯誤位置多項式與錯誤值多項式（BM）硬體架構 58
4.2.6 秦式搜尋（Chien Search）硬體架構 60
4.2.7 錯誤值計算（Forney）硬體架構 60
4.3 電路合成與模擬 61
第五章 結論 79
參考文獻 81
圖目錄
圖1.1 基本數位通訊系統方塊圖 5
圖1.2傳輸系統方塊圖（from ITU J.83） 5
圖2.1 DVB-T系統方塊圖 26
圖2.2 傳輸流封包的加擾 26
圖2.3 隨機擾亂器之二進位數列產生器 26
圖2.4 傳輸流封包的RS編碼 27
圖2.5 迴旋間插與解迴旋間插 27
圖2.6 17行12列RAM矩陣 27
圖2.7 編碼率的基本迴旋間插碼 28
圖2.8 可變迴旋碼和內間插編碼方塊 28
圖2.9 QPSK、16QAM或64QAM輸入位元-輸出調變符號間的映射 29
圖2.10 QPSK、16QAM與64QAM的映射與星雲圖 30
圖2.11 OFDM載波圖框結構 31
圖2.12 導引波與訊號載波立體圖 31
圖2.13 PRBS序列產生器 32
圖2.14 COFDM中的保護間隔插入 32
圖3.1 模數二的加法跟乘法表 36
圖3.2 里德所羅門碼的定義 42
圖3.3 里德所羅門編碼器電路。 43
圖3.4 里德所羅門碼解碼流程圖 52
圖4.1 標準代數解碼法流程 63
圖4.2 RS解碼器電路概略圖 64
圖4.3 加洛瓦場GF（ ）中的Full Multiplier 65
圖4.4 加洛瓦場GF（ ）中的乘法反元素表 66
圖4.5 單一癥狀計算器電路圖 67
圖4.6 16組平行運算之癥狀計算器方塊。 67
圖4.7 合成的單一癥狀計算器 68
圖4.8 合成的癥狀計算器方塊圖 69
圖4.9（a） BM電路架構圖 70
圖4.9（b） BM電路架構圖 70
圖4.10 合成的BM電路方塊圖 71
圖4.11 秦式搜尋第i格（cell） 72
圖4.12更正錯誤能力t=8時, 秦式搜尋電路架構 72
圖4.13 合成的秦式搜尋電路方塊圖 73
圖4.14 錯誤值計算（Forney）的硬體架構 73
圖4.15 合成的錯誤值計算電路方塊圖 74
圖4.16 里德所羅門碼解碼器之波形圖 74
圖4.17 每個區塊電路所需之Timing......................................................75
圖4.18 three-stage pipeling of RS decoder...............................................75
圖4.19 合成的里德所羅門碼解碼器電路方塊圖 76
圖4.20 DVB-T之里德所羅門碼解碼器的RTL 76
圖4.21 DVB-T之里德所羅門碼解碼器的TECH.View 77
圖4.22 合成之使用資源報告 77
圖4.23 合成之Timing報告 78

表目錄
表2.1 迴旋碼類型 32
表2.2 I0-I5之He(w) 33
表2.3 2k與8k模式的OFDM參數 33
表2.4 TPS載波位置編號 33
表2.5 TPS訊號與格式 34
表2.6 OFDM超圖框內傳輸封包數目內編碼率 34
表2.7 DVB-T MHz保護間隔 34
表3.1 本質多項式 所建立之GF(2^m) 38
表4.1 乘法器硬體與唯讀記憶體之比較[3] 64

[1] Lee, J.S.; Sunwoo, M.H.; Oh, S.K.,“Design of DSP instructions and their hardware architecture for a Reed-Solomon codec,” IEEE Signal Processing Systems., pp.103 – 108, Oct. 2002.
[2] ESTI, “Digital Video Broadcasting (DVB); Framing Structure,Channel Coding and Modulation for Digital Terrestrial Television”, European Telecommunication Standard EN300744 v1.4.1, 2001
[3] C.K.P. Clarke, “Reed-Solomon error correction,”BBC R&D White Paper, WHP 031,July 2002.
[4] Martin Bossert, “Channel Coding for Telecommunications”. John Wiley & Sons Ltd, 1999.
[5] E.M. Popovici, P. Fitzpatrick, “Reed-Solomon Codes for Optical Communications”. Microelectronics, 2002. MIEL 2002. 23rd International Conference on, Volume: 2, 2002. pp.613 – 616.
[6] H. Lee, “An Area-Efficient Euclidean Algorithm Block for Reed-Solomon Decoder”. VLSI, 2003. Proceedings. IEEE Computer Society Annual Symposium on , 2003. pp. 209 –210.
[7] E. Berlekamp, “Algebraic Coding Theory”. New York: McGraw-Hill 1968.
[8] Robert J. McEliece, “Finite Fields for Computer Scientists and Engineers”. Kluwer Academic Publishers, 1987.
[9] Sergei V. Fedorenko and Peter V. Trifonov, “ Finding Roots of Polynomials Over Finite Fields,” IEEE Transactions on Communications, Vol. 50, No. 11, pp. 1709-1711, November 2002.
[10] S. Lin, D. J. Costello, Jr., “Error Control Coding: Fundamentals and Applications”, Prentice-Hill, 1983.
[11] E. R. Berlekamp, “Bit-Serial Reed-Solomon Encoders,” IEEE Trans. Inform. Theory, vol. IT-28, no. 6, pp. 869-874, Nov. 1982.
[12] H. M. Shao, T. K. Truong, L. J. Deutsch, J. H. Yuen, and I. S. Reed, “A VLSI Design of a Pipeline Reed-Solomon Decoder,” IEEE Transactions on Computers., vol. C-34, no. 5, pp. 393-402, May 1985.
[13] C. C. Wang, T. K. Truong, H. M. Shao, L. J. Deutsch, J. K. Omura, and I. S. Reed, “VLSI Architectures for Computing Multiplications and Inverses in GF(2m),” IEEE Transactions on Computers., vol. C-34, no. 8, pp. 709-716, Aug. 1985.
[14] S.T.J. Fenn, M. Benaissa, and D. Taylor, “GF(2m) multiplication and division over the dual basis,” IEEE Trans. Comput., vol. 45, no. 3, pp. 319-327, March 1996.
[15] R. Furness, M. Benaissa, S.T.J. Fenn, “GF(2m) multiplication over triangular basis for design of Reed-Solomon codes,” Computers and Digital Techniques, IEE Proceedings- , vol. 145 issue 6 , pp. 437 -443, Nov 1998
[16] Wicker and Bhargava, “Reed-Solomon Codes and Their Applications,” IEEE Press, 1994.
[17] I.S. Reed and G. Solomon, “Polynomial Codes over Certain Finite Fields, ” J. Soc. Ind. Apple. Math. 8,pp. 200-204, June 1860.
[18] Stephen B. Wicker, “Error Control Systems for Digital Communication and Storage,” Prentice Hall, 1995.
[19] G. Fettweis, M. Hassner, “A Combine Reed-Solomon Encoder and Syndrome Generator with Small Hardware Complexity,” Circuits and Systems, ISCAS 92 Proceedings, vol. 4, pp. 1871-1874, 1992.
[20] R. Blahut, “Theory and Practice of Error Control Codes,” Addison-Wesley Co., 1983.
[21] S. Choomchuay and B. Arambepola, “Time domain algorithms and architectures for Reed-Solomon decoding,” Proc. Inst. Elect. Eng. I, Commun., Speed and Vis., vol. 140, pp. 189-196, June 1993.
[22] Research on Reed-Solomon Decoder—Design and Implementation
張錫嘉 國立交通大學電子工程學係電子研究所博士論文, 2000
[23] Study on a SIP Synthesizer of Reed-Solomon Decoder Using a Fast Root Searching Circuit
黃柏涵 國立交通大學電機與控制工程研究所碩士論文, 2001