在通訊系統中，當資料傳輸過程遭受雜訊干擾，則所傳送的資料很有可能因此而產生錯誤。這時必須加入糾錯碼技術，以確保解碼後的資料是正確的。因此，資料傳輸過程中，加入糾錯編碼保護是非常重要的一個步驟。根據不同的傳輸通道，必須選擇其適用的編解碼技術。例如，衛星電視資訊的傳輸必須使用長碼（如低密度奇偶校驗碼）；而快閃記憶體中則適合短碼（如漢明碼）。平方剩餘碼適合短碼應用，因為其在碼長小於100的編碼中，擁有較大的最小距離。平方剩餘碼是一種循環碼，歷史上最早被發展出來的兩種著名的編碼，(7, 4, 3)漢明碼與(23, 12, 7)格雷碼，均是屬於平方剩餘碼。但是，編碼學大師Berlekamp曾指出，平方剩餘碼是好碼，但解碼是個困難的問題。本篇論文提出了一種新的算術解碼概念，稱為特徵值權重解碼法，適用於所有碼長的二元平方剩餘碼。此演算法重要概念在於利用互斥或元件得到所需的特徵值，接下來利用特徵值的權重直接分析出錯誤位置。利用此演算法，所設計的格雷碼解碼器擁有高效能與低複雜度。實驗結果顯示，在Altera Cyclone II FPGA上節省了86.4%空間並增快了22.5%速度；在TSMC 0.18-μm CMOS上節省了91.8%空間並增快了8.3%速度。

In communication systems, the data transmitted through a noisy channel might be corrupted so that it must be protected by error-correcting code to guarantee the decoded data same as the original data. If the communication channels have diffident purposes, diffident encoding and decoding schemes are selected. For example, the long code (e.g. LDPC code) is applied to DVB-S, and the short code (e.g. Hamming code) is applied to flash memory. The quadratic residue (QR) codes have the characteristic of relative large minimum distances when the length of codeword is less than 100. The famous (7, 4, 3) Hamming code and (23, 12, 7) Golay code also belong to the QR codes. However, Berlekamp indicated that these QR codes are good codes but are hard to decode. In this dissertation, we develop a novel arithmetic decoding algorithm, called syndrome-weight decoder, for the QR codes. The key idea is to obtain the needed syndromes which are calculated by XOR operations, and then to get the error positions determined by the weights of syndromes. The parallel architecture for (23, 12, 7) decoder has also been designed. Based on Altera Cyclone II FPGA (resp. TSMC 0.18-μm CMOS standard cell library), the area cost and the time delay are reduced by up to 86.4% (resp. 91.8%) and 22.5% (resp. 8.3%), respectively.

Acknowledgments II
摘要III
Abstract IV
Contents V
List of Figures VII
List of Tables VIII
Chapter 1 Introduction 1
1.1 Historical Background 1
1.2 Motivation 3
1.3 Framework 5
Chapter 2 Mathematical Background 6
2.1 Tragic Talent: Évariste Galois 6
2.2 Algebraic Structure 7
2.3 The Finite Field GF(2m) 10
Chapter 3 Error Correcting Code 13
3.1 Block Codes 13
3.2 Linear Codes 16
3.3 Cyclic Codes 17
3.4 Quadratic Residue Codes 19
Chapter 4 Decoding Algorithm for Golay Decoder 22
4.1 Algebraic Decoding Algorithm 22
4.2 Arithmetic Decoding Algorithm 24
Chapter 5 Novel Quadratic Residue Decoder 31
5.1 Parity-Check Matrices 31
5.2 Universal Arithmetic Decoding Algorithm 37
5.3 Decoding Algorithm for Shortened QR Codes 44
Chapter 6 Hardware Implementation 50
6.1 Architecture 50
6.2 Binary Golay Decoder 51
Chapter 7 Conclusion 56
7.1 Contributions 56
7.2 Future Work 57
References 58
Publication List for Zih-Heng Chen 63
Figure 1-1 Block diagram of a typical communications system. 2
Figure 2-1 Great French mathematician Évariste Galois (1811–1832). 6
Figure 2-2 A note that Galois wrote the night before the duel. 7
Figure 3-1 (a) Block encoding (b) Block decoding. 14
Figure 3-2 Systematic structure of a codeword. 14
Figure 5-1 Systematic structure of a codeword of the QR codes. 38
Figure 6-1 The architecture of the proposed QR decoder. 50
Figure 6-2 The architecture of the proposed binary (23, 12, 7) Golay code. 52
Figure 6-3 The schematic circuit of the proposed binary (23, 12, 7) Golay decoder. 53
Table 2-1 The addition and multiplication tables for GF5. 9
Table 2-2 Representation of the element in GF(2^4). 11
Table 2-3 The addition table for GF(2). 11
Table 3-1 The (7, 4, 3) linear block code. 17
Table 3-2 The (7, 4, 3) cyclic Hamming code generated by g(x) = 1+x+x^3. 19
Table 3-3 The parameters of some binary QR codes. 21
Table 5-1 The combinations of the correctable error patterns. 38
Table 5-3 The (6, 3) shortened Hamming code generated by g(x) = 1+x+x^3. 44
Table 6-1 Implementation and simulation results of the (23, 12, 7) Golay decoder on an Altera Cyclone II FPGA (EP2C35F484C6). 55
Table 6-2 Table 6-2 Implementation and simulation results of the (23, 12, 7) Golay decoder on a TSMC 0.18-μm CMOS standard cell library. 55

[1]A. Hocquenghem, “Codes Correcteurs d''Erreurs,” Chiffres, vol. 2, pp. 147–156, 1959.
[2]A. J. Menezes, I. F. Blake, X. Gao, R. C. Mullin, S. A. Vanstone, and T. Yaghoobian, Applications of Finite Fields, Springer, 1992.
[3]A. Vardy and Y. Be''ery, “More Efficient Soft Decoding of the Golay Codes,” IEEE Transactions on Information Theory, vol. 37, no. 3, pp. 667–672, May 1991.
[4]C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes (1),” in IEEE International Conference on Communications, May 1993, pp. 1064–1070.
[5]C. E. Shannon, “A Mathematical Theory of Communication,” The Bell System Technical Journal, vol. 27, pp. 379–423, 623–656, Jul., Oct. 1948.
[6]C. E. Shannon, “Communication Theory of Secrecy Systems,” The Bell System Technical Journal, vol. 28, no. 4, pp. 656–715, 1949.
[7]C.-D. Lee, Algebraic Decoding and Weight Distributions of Binary Quadratic Residue Codes, Ph.D. dissertation, Department of Information Engineering, I-Shou University, 2006.
[8]C.-D. Lee, Y.-H Chen, and Y. Chang, “A Unified Method for Determining the Weight Enumerators of Binary Extended Quadratic Residue Codes,” IEEE Communications Letters, vol. 13, no. 2, pp. 139–141, Feb. 2009.
[9]C.-L Chr, S.-L. Su, and S.-W. Wu, “Decoding the (23, 12, 7) Golay Code Using a Low-Complexity Scheme,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E89-A, no. 8, pp. 2235–2238, Aug. 2006.
[10]D. M. Gordon, “Minimal Permutation Sets for Decoding the Binary Golay Codes,” IEEE Transactions on Information Theory, vol. IT-28, no. 3, pp. 541–543, May 1982.
[11]D. W. Hardy and C. L. Walker, Applied Algebra: Codes, Ciphers, and Discrete Algorithms, Prentice Hall, 2003.
[12]E. Prange, “Cyclic Error-Correcting Codes in Two Symblos,” Air Force Cambridge Research Center–TN–57–103, Cambridge, Sept.1957.
[13]E. Prange, “Some Cyclic Error-Correcting Codes with Simple Decoding Algorithms,” Air Force Cambridge Research Center–TN–58–156, Cambridge, Apr.1958.
[14]E. R. Berlekamp, Algebraic Coding Theory, Revised Edition (M-6), Aegean Park Press, 1984.
[15]E. T. Bell, Men of Mathematics, Touchstone, 1986.
[16]ETSI EN 302 307, “Digital Video Broadcasting (DVB); Second Generation Framing Structure, Channel Coding and Modulation Systems for Broadcasting, Interactive Services, News Gathering and Other Broadband Satellite Applications (DVB-S2),” 2009.
[17]G. A. Jones and J. M. Jones, Elementary Number Theory, Springer, 1998.
[18]G. C. Kessler, An Overview of Cryptography,http://www.garykessler.net/library/crypto.html
[19]Galois biography,http://www-history.mcs.st-andrews.ac.uk/Biographies/Galois.html
[20]H. P. Ho and P. Sweeney, “Cover Positions and Decoding Complexity of the Golay Code, Using an Extended Kasami Algorithm,” IEEE Communications Letters, vol. 2, no. 12, pp. 324–326, Dec. 1998.
[21]H. P. Ho and P. Sweeney, “Low Complexity Decoding of Cyclic Codes Using an Extended Kasami Algorithm,” Electronics Letters, vol. 34, no. 8, pp. 756–757, Apr. 1998.
[22]I. Boyarinov, I. Martin and B. Honary, “High-Speed Decoding of Extended Golay Code,” IEE Proceedings - Communications, vol. 147, no. 6, pp. 333–336, Dec. 2000.
[23]I. S. Reed and G. Solomon, “Polynomial Codes over Certain Finite Fields,” SIAM Journal on Applied Mathematics, vol. 8, pp. 300–304, Jun. 1960.
[24]I. S. Reed, T. K. Truong, X. Chen, and X. Yin, “The Algebraic Decoding of the (41, 21, 9) Quadratic Residue Code,” IEEE Transactions on Information Theory, vol. 38, no. 3, pp. 974–985, May 1992.
[25]I. S. Reed, X. Yin, and T. K. Truong, “Algebraic Decoding of the (32, 16, 8) Quadratic Residue Code,” IEEE Transactions on Information Theory, vol. 36, no. 4, pp. 876–880, Jul. 1990.
[26]I. S. Reed, X. Yin, T. K. Truong, and J. K. Holmes, “Decoding the (24, 12, 8) Golay code,” IEE Proceedings - Computers and Digital Techniques, vol. 137, no. 3, pp. 202–206, May 1990.
[27]ISO/IEC 18004, Information Technology – Automatic Identification and Data Capture Techniques – QR Code 2005 Bar Code Symbology Specification, Second edition, 2006.
[28]J. Cowley, Communications and Networking: An Introduction, Springer, 2006.
[29]J. L. Anderson, “On Minimal Decoding Sets for the Extended Binary Golay Code,” IEEE Transactions on Information Theory, vol. 38, no. 5, pp. 1560–1561, Sept. 1992.
[30]J. Wolfmann, “A Permutation Decoding of the (24, 12, 8) Golay Code,” IEEE Transactions on Information Theory, vol. IT-29, no. 5, pp. 748–750, Sept. 1983.
[31]J.-F. Ma, “Decoding of the Golay Code,” Electronics Letters, vol. 33, no. 17, pp. 1451–1452, Aug. 1997.
[32]J.-H. Chen, A High-Throughput Diversified AES Design of CAD, Master thesis, Department of Information Engineering, I-Shou University, 2006.
[33]M. Elia and J. Carmelo Interlando, “Quadratic-Residue Codes and Cyclotomic Fields,” Acta Applicandae Mathematicae, vol. 93, no. 1–3, pp. 237–251, Sept. 2006.
[34]M. Elia, “Algebraic Decoding of the (23, 12, 7) Golay Code,” IEEE Transactions on Information Theory, vol. IT-33, no. 1, pp. 150–151, Jan. 1987.
[35]M. J. E. Golay, “Notes on Digital Coding,” Proceedings of the IRE, vol. 37, pp. 657, 1949.
[36]M.-H. Jing, Z.-H. Chen, J.-H. Chen, and Y.-H. Chen, “Reconfigurable System for High-Speed and Diversified AES Using FPGA,” Microprocessors and Microsystems, vol. 31, no. 2, pp. 94–102, Mar. 2007.
[37]National Aeronautics and Space Administration (NASA), http://www.nasa.gov/
[38]National Institute of Standards and Technology, “Announcing the Advanced Encryption Standard (AES),” Federal Information Processing Standards Publication 197, Nov. 2001.
[39]P. Elias, “Coding for Noisy Channels,” IRE Convention Record, Part 4, pp. 37–46, 1955.
[40]P. Gaborit, C.-S. Nedeloaia, and A. Wassermann, “On the Weight Enumerators of Duadic and Quadratic Residue Codes,” IEEE Transactions on Information Theory, vol. 51, no. 1, pp. 402–407, Jan. 2005.
[41]R. C. Bose and D. K. Ray-Chaudhuri, “Further Results on Error Correcting Binary Group Codes,” Information and Control, vol. 3, pp. 279–290, Sept. 1960.
[42]R. C. Bose and D. K. Ray-Chaudhuri, “On a Class of Error Correcting Binary Group Codes,” Information and Control, vol. 3, pp. 68–79, Mar. 1960.
[43]R. G. Gallager, “Low–Density Parity–Check Codes,” IRE Transactions on information theory, vol. 8, no. 1, pp. 21–28, Jan. 1962.
[44]R. He, I. S. Reed, T. K. Truong, and X. Chen, “Decoding the (47, 24, 11) Quadratic Residue Code,” IEEE Transactions on Information Theory, vol. 47, no. 3, pp. 1181–1186, Mar. 2001.
[45]R. T. Chien, ”Cyclic Decoding Procedure for the Bose-Chaudhuri-Hocquenghem Codes,” IEEE Transactions on Information Theory, vol. IT-10, no. 4, pp. 357–363, Oct. 1964.
[46]R. W. Hamming, “Error Detecting and Error Correcting Codes,” The Bell System Technical Journal, vol. 29, no. 2, pp. 147–160, Apr. 1950.
[47]S. B. Wicker, Error Control Systems for Digital Communication and Storage, Prentice Hall, 1994.
[48]S. Lin and D. J. Costello, Error Control Coding, 2nd Edition, Prentice Hall, 2004.
[49]S. Ling and C. Xing, Coding Theory: A First Course, Cambridge University Press, 2004.
[50]S.M. Dodunekov and J.E.M. Nilsson, “Parallel Decoding of the [23, 12, 7] Binary Golay Code,” IEE Proceedings - Computers and Digital Techniques, vol. 141, no. 2, pp. 119–122, Mar. 1994.
[51]S.-W. Wei and C.-H. Wei, “On High-speed Decoding of the (23,12,7) Golay Code,” IEEE Transactions on Information Theory, vol. 36, no. 3, pp. 692–695, May 1990.
[52]T. K. Truong, P. Y. Shih, W. K. Su, C. D. Lee, and Y. Chang, “Algebraic Decoding of the (89, 45, 17) Quadratic Residue Code,” IEEE Transactions on Information Theory, vol. 54, no. 11, pp. 5005–5011, Nov. 2008.
[53]T. K. Truong, Y. Chang, Y. H. Chen, and C. D. Lee, “Algebraic Decoding of (103, 52, 19) and (113, 57, 15) Quadratic Residue Codes,” IEEE Transactions on Communications, vol. 53, no. 5, pp. 749–754, May 2005.
[54]T. Kasami, “A Decoding Procedure for Multiple-Error-Correcting Cyclic Codes,” IEEE Transactions on Information Theory, vol. IT-10, no. 2, pp. 134–138, Apr. 1964.
[55]T.-C. Lin, T.-K. Truong, H.-P. Lee, and H.-C. Chang, “Algebraic Decoding of the (41, 21, 9) Quadratic Residue Code,” Information Sciences, vol. 179, no. 19, pp. 3451–3459, Sept. 2009.
[56]T.-K. Truong, C.-D. Lee, and Y. Chang, “A New Scheme to Determine the Weight Distributions of Binary Extended Quadratic Residue Codes,” IEEE Transactions on Communications, vol. 57, no. 5, pp. 1221–1224, May 2009.
[57]T.-K. Truong, Y. Chang, and C.-D. Lee, “The Weight Distributions of Some Binary Quadratic Residue Codes,” IEEE Transactions on Information Theory, vol. 51, no. 5, pp. 1776–1782, May 2005.
[58]The Evariste Galois Archive, http://www.galois-group.net/
[59]The Unicode Consortium, The Unicode Standard, 5th Edition, Addison-Wesley Professional, 2006
[60]V. D. Goppa, “A New Class of Linear Correcting Codes,” Problemy Peredachi Informatsii, vol. 6, no. 3, pp. 24–30, Sept. 1970.
[61]V. D. Goppa, “Rational Representation of Codes and (L, g)-Codes,” Problemy Peredachi Informatsii, vol. 7, no. 3, pp. 41–49, Sept. 1971.
[62]V. Pless, “Decoding the Golay Codes,” IEEE Transactions on Information Theory, vol. IT-32, no. 4, pp. 561–567, Jul. 1986.
[63]V. Pless, Introduction to the Theory of Error-Correcting Codes, Third Edition, Wiley-Interscience, 1998.
[64]X. Chen, I. S. Reed, and T. K. Truong, “Decoding the (73, 37, 13) Quadratic Residue Code,” IEE Proceedings - Computers and Digital Techniques, vol. 141, no. 5, pp. 253–258, Sept. 1994.
[65]Y. Chang and C.-D. Lee, “Algebraic Decoding of a Class of Binary Cyclic Codes Via Lagrange Interpolation Formula,” IEEE Transactions on Information Theory, vol. 56, no. 1, pp. 130–139, Jan. 2010.
[66]Y. Chang, C.-D. Lee, Z.-H. Chen and J.-H. Chen, “(23, 12, 7) Quadratic Residue Decoder Based on Syndrome-Weight Determination,” Electronics Letters, vol. 44, no. 19, pp. 692–694, Sept. 2008.
[67]Y. Chang, T. K. Truong, I. S. Reed, H. Y. Cheng, and C. D. Lee, “Algebraic Decoding of the (71, 36, 11), (79, 40, 15), and (97, 49, 15) Quadratic Residue Codes,” IEEE Transactions on Communications, vol. 51, no. 9, pp. 1463–1473, Sept. 2003.
[68]Y. Riho and Y. Ito, “Semiconductor Storage Device and Refresh Control Method Therefor,” United States Patent Application 20070230265, 2007.
[69]Y.-H. Chen, T.-K. Truong, C.-H. Huang, and C.-H. Chien, “A Lookup Table Decoding of Systematic (47, 24, 11) Quadratic Residue Code,” Information Sciences, vol. 179, no. 14, pp. 2470–2477, Jun. 2009.
[70]Z.-H. Chen, The Study of Modified Massey-Omura Multiplier and Multiplicative Inversion over Normal Bases, Master thesis, Department of Information Engineering, I-Shou University, 2005.