臺灣博碩士論文加值系統

Reed-Solomon糾錯碼 (RS code)的理論大多應用在媒體系統上，尤其在影像壓縮時，資料儲存和傳輸品質很重要。而RS糾錯碼具有高度的檢錯和除錯的能力，它是依據症狀多項式（Syndrome Polynomial），解出資料錯誤位址及大小值，再針對輸入的資料串予以修正，而完成解碼功能。過去的研究多數利用輾轉相除法 (Euclidean Algorithm)，來解資料位址及大小多項式。目前，柏立根演算法[1][27]對於解更多的錯誤有優異表現之外，此解法比輾轉相除法更適合發展硬體。
本論文以實現改良式無倒數柏立根演算法 (Inversionless Berlekamp Massey Algorithm)之硬體系統，解出錯誤位址多項式(Error locator polynomial)，使用軟硬體聯合設計的觀念來發展整個解碼硬體系統。因此，對RS解碼器之發展上，先進行演算法的模擬 (Simulator)，以驗證演算法的正確性，進而實施至硬體模擬 (Emulator)過程，這對硬體和系統的發展有必要性，最後再接續到原型機 (Prototyping System)的發展，縮短由演算法轉換到硬體的實現過程。
本論文提出一組新的基本運算單元，包括乘法器 (Multiplier) 及倒數器（Inversion）模組，其中使用 Reordering和多倍數的演算法，來簡化各模組在線路的複雜度，此兩種演算法對RS解碼器執行速度及所需硬體面積有決定性影響。上述演算方法，應用在四位元之RS解碼器，結果證明解碼的速度可獲得重大的改善，未來對於DVD產品上的運用更具有效益，除此之外更可應用於其他產品之上，例如容錯系統等。

Recently, the Reed-Solomon (RS) code of burst errors correcting has been widely applied to multimedia systems. The syndrome polynomial of RS code is normally used to obtain error locator polynomial. In the past, the most techniques mainly focus on the Euclidean algorithm to calculate the error locator and evaluator polynomial. However, the Berlekamp Massey (BM)[1][27] algorithm may have even better performance on the Reed Solomon (RS) decoder on solving more errors. On the other hand, the IBM algorithm is more suitable in developing of the hardware.
This thesis implements the RS code system and adopts a novel algorithm that is the inversionless Berlekamp Massey. There is no attempt to derive the theory of the inversionless on the Berlekamp Massey algorithm. The algorithm’s verification and simplification are the main stream. A simulator is firstly completed to prove the algorithm. Secondly, the simulator and emulator for the modules and system is designed and developed using the codesign approach. Finally a prototyping system is implemented for the verification of the Reed-Solomon decoder system. In this project, this design approach has decreased the developing time with full success.
This thesis also gives contributions to the design of a new multiplier and a simpler inversion module. These two modules have the advantages on both the speed and area of the RS code system. These modules have been applied to the RS code system and demonstrated the correctness and improvement. There is an 8 to 16-speed capability on the FPGA and it could be even faster if uses ASIC VLSI. It is the hope that the effort could be fruitful to the future DVD products. The results indicate that the system achieves a significant improvement. Furthermore, It can be applied to various products, such as the fault tolerance system.

ACKNOWLEDGEMENTSI
摘 要II
ABSTRACTIII
CONTENTSIV
LIST OF TABLESVIII
CHAPTER 1 INTRODUCTION 1
1.1 THE MOTIVATION 1
1.2 THE PROPOSED METHODS AND CONTRIBUTIONS1
1.3 ORGANIZATION OF THIS THESIS3
CHAPTER 2 MATHEMATICS BACKGROUND4
2.1 ALGEBRAIC STRUCTURE4
2.2 GALOIS FILED6
2.3 THE POLYNOMIAL ALGEBRA STRUCTURE8
CHAPTER 3 THE REED-SOLOMON (RS) CODE9
3.1 ENCODE9
3.1.1 Reed-Solomon Code Design9
3.1.2 The Generator Polynomial10
3.1.3 The Encoder12
3.2 THE DECODER12
3.2.1 Syndrome Evaluation Algorithm13
3.2.2 Finding the Error Locator Polynomial14
3.2.3 Chien search16
3.2.4 Forney Algorithm17
3.3 THE EXAMPLE OF 3-BIT DECODER USING PETERSON ALGORITHM 18
CHAPTER 4 DESIGN APPROACHES22
4.1 SYSTEM DEVELOPMENT METHODOLOGY22
4.2 SYSTEM ENVIRONMENT AND INTERFACE24
4.3 SOFTWARE SIMULATION FOR NEW FRAMEWORK24
4.4 GATE LEVEL EMULATION SYSTEM25
4.5 PROTOTYPING SYSTEM26
4.6 PROTOTYPING SYSTEM AND TEST-BENCH27
CHAPTER 5 ALGORITHM SIMULATION AND HARDWARE EMULATOR29
5.1 RS CODE SIMULATOR29
5.2 THE OPERATING OF FINITE FIELD IN EMULATOR31
5.2.1 The Circuit Parallelism in Emulator Design32
5.2.2 The Operator of Finite Filed34
5.3 VERIFYING RS CODE ALGORITHM PROCEDURE35
5.3.1 Syndrome Computing35
5.3.2 The BM Algorithm36
5.3.3 The Chien Search38
CHAPTER 6 THE DESIGN OF CRITICAL MODULES40
6.1 MULTIPLIER OF THE FINITE FIELD40
6.2 THE DESIGN OF THE BASELINE MULTIPLIER41
6.3 THE DESIGN OF PARALLEL MULTIPLICATION44
6.5 THE SIMPLIFICATION OF INVERSE MODULE47
CHAPTER 7 THE SYSTEM IMPLEMENTATION54
7.1 SYNDROME MODULE54
7.2 SYNDROME BUFFER AND BURST56
7.3 BERLEKAMP MASSEY MODULE57
7.3.1 The Combination of Logic Structure58
7.3.2 Timing Control Module60
7.4 THE CHIEN SEARCH MODULE62
7.6 THE ERROR CORRECTION MODULE63
7.5 THE PIPELINE ISSUE63
CHAPTER 8 THE RESULT AND CONCLUSIONS68
8.1 RESULT68
8.2 CONCLUSIONS71
8.3 FUTURE RESEARCH DIRECTIONS71
REFERENCE73
APPENDX76

[1] I.S. Reed, M.T. Shih, T.K. Truong, “VLSI design of inverse-free Berlekamp-Massey algorithm,” IEE PROCEEDINGS-E, Vol. 138, NO. 5, SEPTEMBER 1991, pp. 295-298.
[2] Shayan, Y.R., Le-ngoc, T. & Bhargava, V.K, ” Design of Reed-Solomon (16,12) code for North American advanced control system,” IEEE Trans. Vehicular Technology, Vol. 39, Nov. 1990,pp. 400-409.
[3] LS. HSU, T.K. Truong, L.J. Deutsch, I.S. Reed, “A comparison of VLSI architecture of finite field multipliers using dual, normal, standard bases,“ IEEE Trans, compute, Vol. 37, June 1988, pp735-751.
[4] Moon Ho Lee, Seung Bae Choi, and Jin Su Chang, “A HIGH SPEED REED-SOLOMON DECODER,” IEEE Trans, Consumer Electronics, vol. 41, No. 4, November 1995, pp. 1142-1149
[5] Masayuki Hattori, Noboru Ohya, Mitsure Sasano, Ken-ichi Sato and Norithisa Shirota, “Improved General Purpose Reed-Solomon Erasure Encoder/Decoder chip,” IEE PROCEEDINGS, Vol.135, Pt. E, No.6, NOVEMBER 1988, pp.318
[6] Truong, Eastman, Reed, Hsu, “simplified procedure for correcting both errors and erasures of Reed-Solomon code using Euclidean algorithm,” IEE PROCEEDINGS, Vol.135, No. 6, Nov 1988.
[7] B.B. ZHOU, “A New Bit-Serial Systolic Multiplier Over GF( ), ” IEEE Trans. COMPUTERS, Vol. 37, No 6, JUNE 1988, pp. 749-751
[8] Tetsuo lwaki, Toshihisa Tanaka*, Eiji Yamada, Tohru Okuda and Taizoh Sasada “ARCHITECTURE OF A HIGH SPEED REED-SOLOMON DECODER,” IEEE Trans. on Consumer Electronics, Vol. 40 No. 1, FEBRUARY 1994, pp. 75-81
[9] S.T.J. Fenn, M.Benaissa, D. Taylor, “Decoding double-error-correcting Reed-Solomon codes,” IEE Proc. Comm. Vol. 142, No. 6, December 1995, pp. 345-348.
[10] Hideki Yamauchi, Hideaki Miyamoto, Takeshi Sakamoto, Tomofumi Watanabe, Hiroyuki Tsuda and Ryuji Yamamura, “A 24X-SPEED CIRC DECODER FOR A CD-DSP/CD-ROM DECODER LSI,” Vol. 43, No.3, AUGUST 1997, pp. 483-490.
[11] Stephan Schulz, Jerzy W. Rozenblit, “Model-Based Codesign,” IEEE Computer, August 1998, pp60-67.
[12] T.R.N. RAO, E. FUJIWARA, “ERROR-CONTROL CODING FOR COMPUTER SYSTEMS”, Prentice-Hall, 1989.
[13] Kevin Skahill, “VHDL FOR PROGRAMMABLE LOGIC”, ADDISON-WESLEY, 1996
[14] Altera Inc., “MAX+PLUS II VHDL”, Manual.
[15] Altera Inc., “MAX+PLUS II AHDL”, Manual.
[16] Stephen B. Wicker, “Error control systems for digital communication and storage”, Prentice hall international, Inc.
[17] Robert J. McEliece, “The Theory of information and coding A Mathematical Framework for communication”, Addison-Wesley Publishing Company, Inc. 1997, pp. 133-198.
[18] RALPH P. GRIMALDI, “DISCRETE AND COMBINATIORIAL MATHMATICS AN APPLIED INRODUCTION”, 3 RD EDITION, Addison —Wesley 1994, pp. 701-722
[19] I.S. Hsu, T.K. Truong, L.J. Deutsch, and E.H. Satorius, “A Comparison of VLSI Architectures for Time and Transform Domain Decoding of Reed—Solomon Codes”, TDA Progress Report 42-92, October-December 1987.
[20] J. S. L.Wong, T.K. Truong, B.D.L. Mulhall, I.S. Reed, “Review of Finite Fields: Applications to Discrete Fourier Transforms and Reed-Solomon Coding”, JPL PUBLICATION 77-23, July 15,1987.
[21] T.K. Truong, J.H. Jeng and K.-C. Hung “Inversionless Decoding of Both Errors and Erasures of Reed-Solomon Code”, IEEE Trans. On Comm. Vol. 46, No. 8, Aug. 1998
[22] C.C.Wang, T.K. Truong, H.M.Shao, L.J. Deutsch, J.K. Omura, and I.S. Reed "VLSI architecture for computing multiplications and inverses in ," IEEE Trans. Computers, Vol C-34, No. 6, August 1985
[23]J.L. Massey and J.K. Omura, "Computational method and apparatus for finite field arithmetic," U.S. Patent application, submitted 1981
[24]M.H. Jing, Y.H. Chen Y.T. Chang and T.K. Truong, “A New VLSI for Implementing the Multiplication and Inverse in the RS-Code,” 1999 4 16 4th Multimedia Tech. and Appl. Symp. I-Shou Univ. Taiwan, pp.304-11
[25] S.-M. Yen “Improved normal basis Inversion in ”, Elec. Letters 30th Jan. 1997 Vol. 33 No. 3 pp.196-7
[26] Y.S. Cho and S.K. Park, "Design of multiplier using its subfields," Elec. Letters, Vol. 34, No 7, April 1998, pp. 650-651
[27] T.K Truong, T.C. Cheng, S.L. Fu, “Reed-Solomon Decoder and VLSI Implementation” US Patent office Application number # 09-133812, August 13, 1998