跳到主要內容

臺灣博碩士論文加值系統

(3.235.227.117) 您好!臺灣時間:2021/08/01 23:25
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:繆今豪
研究生(外文):Miao, Jinhao
論文名稱:二元循環碼解碼法使用新的未知症狀值表示法
論文名稱(外文):Binary Cyclic Decoder Using New Unified Unknown Syndrome Representation
指導教授:金明浩金明浩引用關係李崇道李崇道引用關係
指導教授(外文):Jing, MinghawLee, Chongdao
口試委員:張耀祖金明浩李崇道
口試委員(外文):Chang, YaotsuJing, MinghawLee, Chongdao
口試日期:2012-06-18
學位類別:碩士
校院名稱:義守大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:62
中文關鍵詞:平方剩餘碼拉格朗日內插法中國餘式定理症狀值矩陣關係式
外文關鍵詞:Quadratic Residue CodeLagrange Interpolation FormulaChinese Remainder TheoremUnknown Syndrome Representation
相關次數:
  • 被引用被引用:0
  • 點閱點閱:1263
  • 評分評分:
  • 下載下載:12
  • 收藏至我的研究室書目清單書目收藏:0
近幾年,使用拉格朗日內插法來求一類二元循環碼的未知症狀值的方法已被提出。
本論文中,我們提出兩種新的計算方法都是基於症狀值矩陣關係式的尋找及中國餘式定理,使用這些方法來找出未知症狀值的多項式,此多項式變數是用已知症狀值表示。在症狀值矩陣關係式搜尋的部份,我們撰寫程式,對二元循環碼碼長51以下,進行搜尋並列表。針對於二元循環碼,計算表示未知症狀值多項式的部分,將拉格朗日內插法及提出的兩種新方法進行時間的比較。最後,給予一個 (31, 16, 7) 二元平方剩餘碼使用無反根Berlekamp-Massey 的完整解碼例子。
Recently, the unified unknown syndrome representations to decode a class of binary cyclic codes have been developed by using Lagrange interpolation formula. In this thesis, a new method by combining the syndrome matrix search and Chinese remainder theorem is proposed to express the unified unknown syndrome representation as a rational function in terms of the known syndromes. A computer search has been made to determine the syndrome matrices for binary cyclic codes of lengths less than or equal to 51. Compared to the Lagrange interpolation method, the method presented here substantially reduces the computational time for binary cyclic codes generated by irreducible polynomials. Finally, a complete decoding of the (31, 16, 7) quadratic residue code with inverse-free BerlekampMassey algorithm is given as illustration.
ACKNOWLEDGMENTS I
摘要 II
ABSTRACT III
CONTENTS 1
LIST OF FIGURES III
LIST OF TABLES IV
CHAPTER 1 INTRODUCTION 1
1.1 HISTORY 1
1.2 MOTIVATION 2
1.3 FRAMEWORK 3
CHAPTER 2 MATHEMATICAL BACKGROUND 4
2.1 FINITE FIELD 4
2.1.1 Definition of a Finite Field 4
2.1.2 Definition of Field Operations 4
2.1.3 Prime Finite Field 4
2.1.4 Finite Field GF(2m) 6
2.2 ALGEBRAIC CODING THEORY 8
2.2.1 Cyclic Codes 8
2.2.2 Quadratic Residue Codes 8
2.2.3 Encoding of Cyclic Code 9
2.2.4 Decoding of Cyclic Code 11
CHAPTER 3 DECODING METHOD BY LAGRANGE INTERPOLATION 14
3.1 LAGARANGE INTERPOLATION FORMULA 14
3.2 UNIFIED REPRESENTATIONS OF UNKNOWN SYNDROME 14
3.3 INVERSE-FREE BERLEKAMP-MASSEY ALOGRITHM 16
3.4 CHIEN SEARCH 17
3.5 DECODING ALGORITHM 17
CHAPTER 4 PROPOSED DECODING METHOD 20
4.1 CHINESE REMAINDER THEOREM 20
4.2 POLYNOMIAL IN TERMS OF SYNDROMES 21
4.3 SYNDROME MATRIX 22
4.4 MAIN RESULT 28
4.4.1 Modified Chinese Remainder Theorem 28
4.4.2 Proposed Method 30
4.4.3 Improved Method 33
4.5 VARIATIONS 39
4.6 COMPLEXITY ANALYSIS 43
CHAPTER 5 CONCLUSION 44
BIBLIOGRAPHY 45
APPRNDIX A 47
List of Figures
Figure 1 1 The decoding model by general error locator polynomials (left) and unified unknown syndrome representations (right). 3
Figure 2 1 Systematic encoding of an (n, k) cyclic code 9
Figure 2 2 Simplified model for communication system 11
List of Tables
Table 2 1 MATHEMATICA OPERICATION OF GF(5) 5
Table 2 2 MATHEMATICA OPERICATION OF GF(2) 6
Table 2 3 REPRESENTATION OF 7
Table 2 4 PRIMITIVE POLYNOMIALS 7
Table 2 5 GENERATOR POLYNOMIAL OF BINARY QR CODES. 9
Table 3 1 NUMBERS OF (S_1, S_r) FOR QR CODE WITH LENGTH 15
Table 4 1 SETS OF SYNDROME MATRICES FOR BINARY 32
Table 4 2 ELEMENTS OF 38
Table 4 3 COMPUTATIONAL TIME OF PREDETERMINING UNKNOWN SYNDROME REPRESENTATIONS FOR THREE QUADRATIC RESIDUE CODES 43
Table A 1 〈K_3〉FOR THE (31, 16, 7) QR CODE 47
Table A 2 〈T_3〉FOR THE (31, 16, 7) QR CODE 50
[1]C. D. Lee, Y. Chang, M. H. Jing, and J. H. Miao, “A new method of predetermining unified unknown syndrome representation for decoding binary cyclic codes,” submit to IET Commun., Apr. 2012 (revised Jul. 2012).
[2]E. Prange, “Cyclic Error-Correcting Codes in Two Symbols,” AFCRC-TN-57-103, Air Force Cambridge Research Center, Bedford, Mass., Sept. 1957.
[3]E. R. Berlekamp, Algebraic Decoding Theory, New York: McGraw-Hill, 1968.
[4]G.-L. Feng and K.-K. Tzeng, “A new procedure for decoding cyclic and BCH codes up to actual minimum distance,” IEEE Trans. Inf. Theory, vol. 40, no. 5, pp. 1364-1374, Sep. 1994.
[5]I. S. Reed, M. T. Shih and T. K. Truong, “VLSI design of inverse-free BerleKamp-Massey algorithm,” IEE Proceeding-E, vol. 138, no. 5, pp. 295-298, Sep. 1991
[6]J. L. Massey, “Shift-register synthesis and BCH decoding,” IEEETrans. Inf. Theory, vol. IT-15, no. 1, pp. 122-127, Jan. 1969.
[7]R. He, I. S. Reed, T. K. Truong, and X. Chen, “Decoding the (47, 24, 11) quadratic residue code,” IEEE Trans. Inf. Theory, vol. 47, no. 3, pp. 1181–1186, Mar. 2001.
[8]R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications. New York: Cambridge Univ. Press, 1986.
[9]T. K. Truong, P. Y. Shih, W. K. Su, C. D. Lee, and Y. Chang, “Algebraic decoding of (89, 45, 17) quadratic residue code,” IEEE Trans. Inf. Theory, vol. 54, no. 11, pp. 5005-5011, Nov. 2008.
[10]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 Trans. Commun., vol. 53, no. 5, pp. 749-754, May 2005.
[11]Y. Chang and C. D. Lee, “Algebraic decoding of a class of binary cyclic codes via Lagrange interpolation formula,” IEEE Trans. Inf. Theory, vol. 56, no. 1, pp. 130-139, Jan. 2010.
[12]Y. Chang, T. K. Truong, I. S. Reed, H. Y. Cheng, and C. D. Lee, “Algebraic decoding of (71, 36, 11), (79, 40, 15), and (97, 49, 15) quadratic residue codes,” IEEE Trans. Commun., vol. 51, no. 9, pp. 1463-1473, Sep. 2003.
[13]Y. H. Chen, T. K. Truong, Y. Chang, C. D. Lee, and S. H. Chen, “Algebraic decoding of quadratic residue codes using inverse-free Berlekamp-Massey algorithm,” J. Inf. Sci. Eng., vol. 23, pp. 127-145, Jan. 2007.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top