臺灣博碩士論文加值系統

循環碼是被廣泛應用在數位通訊系統的糾錯碼。有一些方法如代數、歐基理德和步階解碼演算法被發展出來解循環碼。本論文提出新的步階解碼法來降低解循環碼的運算複雜度。首先一種低複雜度步階解碼演算法被提出來解t個錯的二位元BCH 碼。步階解碼法省略錯誤位置多項式係數和求根的計算，所以它的複雜度比標準代數解碼法低。然而傳統步階解碼法並未嘗試去降低矩陣運算量，而本文提出的方法藉由邏輯分析，可以將傳統步階解碼法判斷接收的一個位元訊息是否錯誤簡化成一個簡單式，其所需要的矩陣運算大約只有傳統方法的一半。應用本新解碼法，我們也提出一個簡單規則的步階解碼演算法，進一步降低步階解碼法中的矩陣及乘法運算。此外，我們將這種解碼法應用在 (23, 12, 7) 格雷碼解碼，可以有效的降低運算複雜度。最後，本論文提出一種結合步階解碼法與QAM系統解RS碼的低複雜度演算法，由於傳統RS步階解碼法需要較高的疊代及徵候矩陣運算，所以在高解碼能力時無法被廣泛使用，而相較於傳統RS步階解碼法，本文提出的方法在解碼時只要以(2m-1)分之一倍的疊代次數測試錯誤值，所以它的運算複雜度低於傳統RS步階解碼法。

Among the many error-correcting codes, cyclic codes are widely employed in digital communication system. Some decoding techniques have been proposed for decoding the cyclic codes, such as the standard algebraic algorithm, the Euclid’s algorithm and the step-by-step algorithm. To reduce the computational complexity, novel step-by-step decoding algorithms are proposed in this thesis. To begin with, a low-complexity step-by-step decoding algorithm for t-error-correcting binary Bose-Chaudhuri-Hocquenghem (BCH) codes is proposed. The step-by-step decoding method avoids calculating the coefficients and searching for the roots of the error-location polynomial, so it is less complex than the standard algebraic method. However, the conventional step-by-step decoding algorithm has not tried to reduce the number of matrix-calculations. By using logical analysis, the determination whether a received bit is erroneous in the new scheme as the conventional step-by-step decoding algorithm can be further simplified into general functions. The new decoder requires only approximately half of the matrix calculations as the conventional step-by-step decoder. Based on the new decoder, we obtain a simple rule and propose a novel step-by-step decoding algorithm. The decoder significantly reduces the matrix calculations and the operations of multiplication compared with the previous algorithms. Moreover, the proposed method can be applied to decode the (23, 12, 7) Golay code. The computational complexity can be reduced significantly using this scheme. Finally, this dissertation proposes a low-complexity decoding algorithm for Reed-Solomon codes which combines a modified step-by-step decoder with 2m-QAM system. The conventional step-by-step decoding algorithm has not been widely employed for RS code with large error-correcting capability, since the calculation of the iteration and syndrome matrix determinant. The computational complexity of this decoder is less than the conventional step-by-step decoder, since it reduces the computations of iteration-calculation of testing the error values by a factor of (2m-1).

Contents

摘要............................................................................................................................ ......Ⅰ
Abstract ............................................................................................................................. Ⅱ
誌謝 ................................................................................................................................... Ⅳ
Contens ...............................................................................................................................Ⅴ
List of Tables ..................................................................................................................... Ⅷ
List of Figures ................................................................................................................... Ⅷ
Chapter 1 Introduction 1
1.1 Historical Overviews 3
1.2 The Motivation of the Disseration 6
1.3 Organization of the Dissertation 7
Chapter 2 Preliminaries 9
2.1 Linear Block Codes 9
2.1.1 Vector Spaces and Subspaces 11
2.1.2 Decoding Task 12
2.1.3 Decoder Implementation 23
2.2 Cyclic Codes 25
2.2.1 The Generator Polynomial 28
2.2.2 Systematic Cyclic Code 30
2.3 Hamming Codes and BCH Codes 31
2.3.1 Decoding of BCH Codes 33
2.4 Reed-Solomon Codes 38
2.5 Golay Codes 40
2.5.1 Two-error correcting algorithm 41
2.5.2 Algebraic decoding algorithm 43
Chapter 3 Low-Complexity Step-by-Step Decoding for Binary BCH Codes ...... 47
3.1 Overview 47
3.2 Preliminaries 49
3.3 Proposed Decoding Algorithm 53
3.4 Illustrative Example 61
3.5 Summary of this Chapter 63
Chapter 4 A Simple Decoder of Binary BCH Codes 64
4.1 Decoding Algorithm 64
4.2 Decoder Architecture 69
4.3 Example of Decoding of Binary (15, 5) BCH Code 70
4.4 Summary of this Chapter 72
Chapter 5 Decoding for Golay Codes 74
5.1 Overview 74
5.2 Preliminaries 75
5.3 Proposed Decoding Algorithm 78
5.4 Decoder Architecture 80
5.5 Illustrative Example 83
5.6 Summary of this Chapter 84
Chapter 6 A Low-Complexity Decoding of Reed-Solomon Decoder Combined
with 2m-QAM System 85
6.1 Overview 85
6.2 Preliminaries 86
6.3 Proposed Decoding Algorithm 88
6.4 Summary of this Chapter 92
Chapter 7 Conclusion and Future Works 94
Appendix 96
References 100
作 者 簡 歷 104

References

[1]. S. Lin and D. J. Costello, Jr., Error Control Coding: Fundamentals and Applications, 2nd edition. Englewood Cliffs, NJ: Prentice-Hall, Inc., 2004.
[2]. B. Sklar, Digital Communications: Fundamentals and Applications, 2nd edition. Englewood Cliffs, NJ: Prentice-Hall Inc., 2001.
[3]. C. E. Shannon, “A matliematical theory of communication,” Bell System Technical Journal, pp. 379-127, 1948.
[4]. A. Hocquenghem, “Codes correcteurs d'erreurs,” Chiffres (Paris), vol. 2. pp. 147-156, September 1959.
[5]. R. Bose and D. Ray-Chaudhuri, “On a class of error correcting binary group codes,” Information and Control, vol. 3, pp. 68-79, March 1960.
[6]. R. Bose and D. Ray-Chaudhuri, “Further results on error correcting binary group codes,” Information and Control, vol. 3, pp. 279-290, September 1960.
[7]. W. Peterson, “Encoding and error correction procedures tor the Bose-Chaudhuri codes,” IEEE Transactions on Information Theon, vol. IT-6. pp. 459-470, September 1960.
[8]. J. Wolf, “Efficient maximum likelihood decoding of linear block codes using a trellis,” IEEE Transactions on Information Theory, vol. IT-24, pp. 76-80, January 1978.
[9]. B. Honary and G. Markarian, Trellis Decoding of Block Codes. Dordrecht, The Netherlands: Kluwer Academic, 1997.
[10]. S. Lin, T. Kasami. T. Fujiwara, and M. Fossorier, Trellises and Trellis-based Decoding Algorithms for Linear Block Codes. Norwell, MA, USA: Kiliwer Academic, 1998.
[11]. G. Fomey, “Coset Codes-Part II: Binary Lattices and Related Codes,” IEEE Transactions on Information Theory, vol. 34, pp. 1 152-1 187, September 1988.
[12]. H. Manoiikian and B. Honary, “BCJR trellis construction for binary linear block codes,” IEE Proceedings, Com-munications, vol. 144, pp. 367-371, December 1997.
[13]. T. Kasami, T. Takata, T. Fujiwara, and S. Lin, “On complexity of trellis structure of linear block codes,” IEEE Transactions on information Theory, vol. 39. pp. 1057-1937, May 1993.
[14]. T. Kasami, T. Takata, T. Fujiwara, and S. Lin, “On the optimum bit orders with respect to the state complexity of trellis diagrams for binary linear codes,” IEEE Transactions on Information Theory, vol. 39. pp. 242-245, January 1993.
[15]. D. Chase, “A class of algorithms for decoding block codes with channel measurement information,” IEEE Transactions on Infonrultion Theory, vol. IT-18. pp. 170-182, January 1972.
[16]. D. Gorenstein and N. Zierler, “A class of cyclic linear error-correcting codes in pm symbols,” Journal of the Society of Industrial and Applied Mathematics., vol. 9. pp. 107-214, June 1961.
[17]. I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields,” Journal of the Society of industrial and Applied Mathematics., vol. 8. pp. 300-304, June 1960.
[18]. E. Berlekamp, “On decoding binary Bose-Chaudhuri-Hocquenghern codes,” IEEE Transactions on information Theory, vol. II, pp. 577-579, 1965.
[19]. E. Berlekamp, Algebraic Coding Theory. New York, USA: McGraw-Hill, 1968.
[20]. J. Massey, “Step-by-step decoding of the Bose-Chaudhuri-Hocquenghem codes,” IEEE Transactions on Information Theory, vol. 11. pp. 580-585, 1965.
[21]. J. Massey, “Shift-register synthesis and BCH decoding,” IEEE Transactions on Information Theory, vol. IT-15. pp. 122-127, January 1969.
[22]. M. Oh and P. Sweeney, “Bit-level soft-decision sequential decoding for Reed Solomon codes,” in Workshop on Coding and Cryptography. (Paris, France), January 1999.
[23]. M. Oh and P. Sweeney, “Low complexity soft-decision sequential decoding using hybrid permutation for RS codes,” in Seventh IMA Conference on Cryptography and Coding, (Royal Agricultural College, Cirencester. UK). December 1999.
[24]. D. Burgess, S. Wesemeyer, and P. Sweeney, “Soft-decision decoding algorithms for RS codes,” in Seventh IMA Conference on Cryptography and Coding, (Royal Agricultural College, Cirencester. UK). December 1999.
[25]. Consultative Committee for Space Data Systems, Blue Book: Recommendations for Space Didards: Telemetry Channel Coding, May 1984.
[26]. European Telecommunication Standard Institute (ETSI), Digital Video Broadcasting (DVB); Framing structure, channel coding and modulation for MVDS at 10GHz and above, ETS 300 748 ed., October 1996. http://www.etsi.org/.
[27]. J. L. Massey, “Step-by-step decoding of the Bose-Chaudhuri- Hocquenghem codes,” IEEE Trans. Info. Theory, vol. IT-11, pp. 580-585, 1965.
[28]. S. W. Wei and C. H. Wei, “A high-speed real-time binary BCH decoder,” IEEE Trans. Circuits and Systems for Video Technology, vol. 3, no. 2, pp. 138-147, 1993.
[29]. R. G. Gallager, Information Theory and Reliable Communication. New York: Wiley, 1968.
[30]. R. E. Blahut, Fast Algorithms for Digital Signal Processing. Reading, MA:Addison-Wesley, 1985.
[31]. R. C. Bose and D. K. Ray-Chadhuri, “On a class of error correcting binary group codes,” Inform. Contr., vol. 3, pp. 68–79, Mar. 1960.
[32]. I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields,” SIAM J. Appli. Math. vol. 8, pp. 300–304, 1960.
[33]. S. B. Wicker and V. K. Bhargava, Ed., Reed-Solomon Codes and Their Applications. New York: IEEE Press, 1994.
[34]. R. C. Singleton, “Maximum distance Q-nary codes,” IEEE Trans. Inform.Theory, vol. IT-10, no. 2, pp. 116–118, Apr. 1964.
[35]. S. B. Wicker, Error Control Systems for Digital Communication and Storage. Englewood Cliffs, NJ: Prentice Hall, 1994.
[36]. Elia, M., “Algebraic decoding of the (23,12,7) Golay code,” IEEE Trans., IT-33 1987.
[37]. C. L. Chr, S. L. Su and S. W. Wu, “A Low-Complexiy Step-by-Step Decoding Algorithm for Binary BCH Codes”, IEICE Trans., Fundamentals, Vol. E88-A, No.1, 2005.
[38]. Golay, M.J.E., “Notes on digital coding”, Proc. IEEE, vol. 37, p. 657, 1949.
[39]. E. H. Lu, and T. Chang, “New decoder for double-error-correcting binary BCH codes,” IEE Proc-Commun. vol. 143, no. 3, pp. 129-132, 1996.
[40]. R. T. Chien and V. Lum, “On Golay’s perfect codes and step-by-step decoding,” IEEE Trans. Inform. Theory, vol. IT-12, pp. 403-404, 1966.
[41]. S. W. Wei, and C.H. Wei, “On high-speed decoding of the (23, 12, 7) Golay code”, IEEE Trans. Inform. Theory, IT-36, (3). pp. 692-695, 1990.
[42]. E. D. Mastrovito, “VLSI architectures for computations in Galois fields”. PhD thesis (dissertation 242), Linkoping Studies in Science and Technology, Linkoping, 1991.
[43]. B. A. Laws, Jr. and C. K. Rushforth, “A cellular-array multiplier for GF(2m),” IEEE Trans. Comput., vol. C-20. pp. 1573-1578, 1971.
[44] T. C. Chen, C. H. Wei and S. W. Wei, “A Two-Stage Reed-Solomon Decoder for Coded 2^m-QAM Systems,” 2000 IEEE Asia Pacific Conference on Circuits and Systems, pp. 223-226, Tianjin, China, Dec. 4-6, 2000.