臺灣博碩士論文加值系統

在本論文中，提出一種可以更正達到五個錯的(47, 24, 11)二元平方剩餘碼(binary quadratic residue)的有效的查表法解碼演算法(table lookup decoding algorithm)。此查找表解碼演算法的主要觀念是根據徵狀值的權重(weight)，減少大小查找表的徵狀值解碼器(syndrome decoder together with a reduced-size lookup table)，以及Reed等人的移位搜尋(shift search)法。因此，查找表的大小以及在有限體中計算的複雜度可以大大的降低。在本論文中所提出的一種新的濃縮查找表(condensed lookup table)，此濃縮查找表所需記憶體的大小由36.6 K位元組所組成，它只需要大約完整查找表(full lookup table)大小的0.24%，或是Chen等人所提出的查找表大小的3.4%。模擬的結果證明本論文所提出的查找表解碼演算法的解碼速度比其它的演算法快。此外，此演算法也可延伸去更正其它的二元平方剩餘碼或循環碼，只要碼長及濃縮查找表的大小適當就可以。此演算法也適用在硬體或韌體的執行上。

In this dissertation, an efficient table lookup decoding algorithm (TLDA) is presented to correct up to five possible errors in a binary systematic (47, 24, 11) quadratic residue (QR) code. The main idea of the TLDA is based on the weight of syndrome, the syndrome decoder together with a reduced-size lookup table (RSLT), and the shift-search method given by Reed et al. Thus, the size of the lookup table and computational complexity in a finite field can be significantly reduced. The memory size of the proposed condensed lookup table (CLT) consists of only 36.6 Kbytes and is only about 0.24% of the full lookup table (FLT) and about 3.4% of the lookup table given by Chen et al., respectively. These facts lead to significant reduction of computational time and the decoding complexity. A simulation result shows that the decoding speed of the proposed TLDA is much faster than all existing decoding algorithms. Moreover, it can be extended to decode all QR codes, including the class of the cyclic codes when the code length is moderate. The CLT makes this new decoding algorithm suitable for hardware or firmware implementations.

Dedication I
Acknowledgments II
Abstract (Chinese) III
Abstract (English) IV
Contents VI
List of Figures VIII
List of Tables IX
Chapter 1 Introduction 1
1.1 Research Background 2
1.2 Structure of the Dissertation 5
Chapter 2 Mathematical Preliminaries of QR Codes 6
2.1 The Basic Theory of Galois Fields 6
2.2 Polynomial Arithmetic over Galois Fields 11
2.3 Linear Block Codes 16
2.4 Cyclic Codes 19
2.4.1 General Properties of Cyclic Codes 19
2.4.2 Encoding of Cyclic Codes 21
2.5 QR Codes 27
2.5.1 Generator Polynomial 27
2.5.2 Syndrome Computation and Error-Locator Polynomial 28
Chapter 3 An Improved Algebraic Decoding Algorithm of the Binary (47, 24, 11) QR Code 31
3.1 Background of the Binary (47, 24, 11) QR Code 31
3.2 Algebraic Decoding Algorithm Developed by He et al. 33
3.3 An Improved Algebraic Decoding Algorithm 38
3.3.1 The Modified Coefficients of f(S5) and g(S5) 39
3.3.2 The Improved Fast Algebraic Decoding Algorithm 39
3.3.3 Fast Method for Computing the Inverse and Multiplication in GF(2^m) 40
Chapter 4 Table Lookup Decoding Algorithm 42
4.1 Syndrome Decoder with a Reduced-Size Lookup Table 42
4.2 The Proposed Table Lookup Decoding Algorithm 47
4.2.1 Construction of the Condensed Lookup Table 48
4.2.2 The Modified Shift-Search Algorithm 50
4.2.3 Decoding Algorithm of the Binary (47, 24, 11) QR Code 51
Chapter 5 Simulation Results 60
Chapter 6 Conclusions and Future Work 62
Appendix A 63
Appendix B 67
Bibliography 86
List of Figures
Figure 4.2.3.1 Flowchart of the proposed TLDA for the binary systematic (47, 24, 11) QR code 54
List of Tables
Table 2.2.1 Representation of the elements of GF(2^3) generated by x^3 + x + 1 = 0 13
Table 2.2.2 Representation of the elements of vectors over GF(2^3) 14
Table 2.3.1 The codewords of binary systematic Hamming code 18
Table 2.4.1.1 Hamming code is a cyclic code 20
Table 2.4.2.1 Non-systematic encoding of the binary (7, 4, 3) Hamming code by using Eq. (2.4.2.1) 22
Table 2.4.2.2 Non-systematic encoding of the binary (7, 4, 3) Hamming code by using Eq. (2.4.2.4) 23
Table 2.4.2.3 Systematic encoding of the binary (7, 4, 3) Hamming code by using Eq. (2.4.2.6) 25
Table 2.4.2.4 Systematic encoding of the binary (7, 4, 3) Hamming code by using Eq. (2.4.2.9) 26
Table 2.5.1 The parameters of some binary QR codes 27
Table 3.1.1 The values of indices 33
Table 5.1 Computing time to decode the (47, 24, 11) QR code (in us) 60
Table 5.2 Required memory size of the CLT for different QR codes under n < 100 61
Table B.1 The syndromes corresponding to error patterns in the RSLT (or CLT for 1 <= t <= 4) 67
Table B.2 The syndromes in ascending order corresponding to error patterns in the RSLT 78
Table B.3 The syndromes in ascending order corresponding to error patterns in the CLT 81

[1]Blaum, M. and Bruck, J. (1990). Decoding the Golay code with Venn diagrams, IEEE Transactions on Information Theory, Vol. 36, No. 4, pp. 906–910.
[2]Chang, H. C., Lee, H. P., Lin, T. C. and Truong, T. K. (2008). A Weight Method of Decoding the (23, 12, 7) Golay Code Using Reduced Lookup Table, 2008 International Conference On Communication, Circuits and Systems (ICCCAS 2008), pp. 01-05, Xiamen University, Fujian Province, China.
[3]Chen, X., Reed, I. S. and Truong, T. K. (1994). Decoding the (73, 37, 13) quadratic residue code, IEE Proc.-Comput. Digit. Tech., Vol. 141, pp. 253-258.
[4]Chen, X., Reed, I. S., Helleseth, T. and Truong, T. K. (1994). Use of Gröbner bases to decode binary cyclic codes up to the true minimum distance, IEEE Transactions on Information Theory, Vol. 40, No. 5, pp. 1654–1661.
[5]Chen, Y. H., Truong, T. K., Chang, Y., Lee, C. D. and Chen, S. H. (2007). Algebraic Decoding of Quadratic Residue Codes Using Berlekamp-Massey Algorithm, Journal of Information Science and Engineering (JISE), Vol. 23, pp. 127-145.
[6]Chen, Y. H., Truong, T. K., Huang, C. H. and Chien, C. H. (2009). A Lookup Table Decoding of Systematic (47, 24, 11) Quadratic Residue Code, Information Sciences, Vol. 179, No. 14, pp. 2470-2477.
[7]Dubney, G., Reed, I. S., Truong, T. K. and Yang, J. (2009). Decoding the (47, 24, 11) Quadratic Residue Code Using Bit-Error Probability Estimates, IEEE Transactions on Communications, Vol. 57, No. 7, pp.1986-1993.
[8]Duursma, I. M. and Kötter, R. (1994). Error-locating pairs for cyclic codes, IEEE Transactions on Information Theory, Vol. 40, pp. 1108–1121.
[9]Elia, M. (1987). Algebraic decoding of the (23, 12, 7) Golay code, IEEE Transactions on Information Theory, Vol. 33, pp. 150-151.
[10]Feng, G. L. and Tzeng, K. K. (1994). A new procedure for decoding cyclic and BCH codes up to actual minimum distance, IEEE Transactions on Information Theory, Vol. 40, pp. 1364–1374.
[11]Gilberg, R. F. and Forouzan, B. A. (2001). Data Structures: A Pseudo code Approach with C++, Course Technology.
[12]Golay, M. J. E. (1949). Notes on digital coding, Proc. IRE, Vol. 37, p.657.
[13]Hamming, R. W. (1950). Error detecting and error correcting codes, Bell System Technical Journal, Vol. 29, pp. 147-160.
[14]He, R., Reed, I. S., Truong, T. K. and Chen, X. (2001). Decoding the (47, 24, 11) quadratic residue code, IEEE Transactions on Information Theory, Vol. 47, pp. 1181–1186.
[15]Kasami, T. (1964). A decoding procedure for multiple-error-correcting cyclic codes, IEEE Transactions on Information Theory, Vol. IT-10, pp. 134–138.
[16]Lee, H. P., Chang, H. C., Lin, T. C., Truong, T. K. (2008). A Weight Method of Decoding the binary BCH Code, The 8th International Conference on Intelligent Systems Design and Applications (ISDA-2008), Vol. 3, pp.545-549, Kaohsiung City.
[17]Lin, T. C., Chang, H. C., Lee, H. P. and Truong, T. K. (2010). On the decoding of the (24, 12, 8) Golay code, Information Sciences, Vol. 180, No. 23, pp. 4729-4736, Dec. 2010.
[18]Lin, T. C., Chang, H. C., Lee, H. P., Chu, S. I., Truong, T. K. (2010). Decoding of the (31, 16, 7) Quadratic Residue Code, Journal of the Chinese Institute of Engineers (JCIE), Vol. 33, No. 4, pp. 573-580.
[19]Lin, T. C., Chu, S. I., Chang, H. C. and Lee, H. P. (2009). Decoding the (31, 16, 7) Quadratic Residue Code in GF(2^5), The 4th International Conference on Computer Science and Education (ICCSE 2009), Nanning, China.
[20]Lin, T. C., Lee, H. P., Chang, H. C., Chu, S. I. and Truong, T. K. (2010). High speed decoding of the binary (47, 24, 11) quadratic residue code, Information Sciences, Vol. 180, No. 20, pp. 4060-4068.
[21]Lin, T. C., Truong, T. K., Lee, H. P. and Chang, H. C. (2009). Algebraic decoding of the (41, 21, 9) Quadratic Residue code, Information Sciences, Vol. 179, No. 19, pp. 3451-3459.
[22]MacWilliams, F. J. and Sloan, N. J. A. (1977). The Theory of Error-Correcting Codes, Amsterdam, The Netherlands: North-Holland.
[23]Pless, V. (1998). Introduction to the theory of error-correcting codes, 3rd ed., New York: Wiley.
[24]Prange, E. (1958). Some cyclic error-correcting codes with simple decoding algorithms, Air Force Cambridge Research Center-TN-58-156, Cambridge, MA.
[25]Reed, I. S., Truong, T. K., Chen, X. and Yin, X. (1992). The algebraic decoding of the (41, 21, 9) quadratic residue code, IEEE Transactions on Information Theory, Vol. 38, No. 3, pp. 974-986.
[26]Reed, I. S., Yin, X. and Truong, T. K. (1990). Algebraic decoding of the (32, 16, 8) quadratic residue code, IEEE Transactions on Information Theory, Vol. 36 pp. 876–880.
[27]Reed, I. S., Yin, X., Truong, T. K. and Holmes, J. K. (1990). Decoding the (24, 12, 8) Golay code, IEE Proceedings, Vol. 137, pp. 202-206.
[28]Su, W. K., Shih, P. Y., Lin, T. C. and Truong, T. K. (2008). Decoding of the (48, 24, 12) Extended Quadratic Residue Code up to Six Errors, International Conference On Communication, Circuits and Systems (ICCCAS 2008), pp.01-05, Xiamen University, Fujian Province, China.
[29]Truong, T. K., Chang, Y., Chen, Y. H. and Lee, C. D. (2005). Algebraic Decoding of (103, 52, 19) and (113, 57, 15) Quadratic Residue Codes, IEEE Transactions on Communications, Vol. 53, No. 5, pp. 749-754.
[30]Truong, T. K., Chang, Y., Reed, I. S., Cheng H. Y. and Lee, C. D. (2003). Algebraic Decoding of (71, 36, 11), (79, 40, 15), and (97, 49, 15) Quadratic Residue Codes, IEEE Transactions on Communications, Vol. 51, No. 9, pp. 1463-1473.
[31]Truong, T. K., Shih, P. Y., Su, W. K., Lee, C. D. and Chang, Y. (2008). Algebraic Decoding of the (89, 45, 17) Quadratic Residue Code, IEEE Transactions on Information Theory, Vol. 54, No. 11, pp. 5005-5011.
[32]Wang, C., Truong, T. K., Omura, J. K., Reed, I. S. and Shao, H. M. (1985). VLSI architectures for computing multiplications and inverses in GF(2m), IEEE Transactions on Computers, Vol. C-34, No. 8, pp. 709-717.
[33]Wicker, S. B. (1995). Error Control Systems for Digital Communication and Storage, Prentice Hall.
[34]Wolfmann, J. (1983). A permutation decoding of the (24, 12, 8) Golay code, IEEE Transactions on Information Theory, Vol. IT-29, No. 5, pp. 748-750.