A new bound on the minimum distance of cyclic codes using small-minimum-distance cyclic codes

详细信息    查看全文

• 作者：Alexander Zeh (1) (2)
  Sergey Bezzateev (3)
  
• 关键词：BCH bound ; Bound on the minimum distance ; Cyclic code ; Decoding ; Hartmann–Tzeng bound ; 94A24 ; 94B35 ; 94B15 ; 94A55
• 刊名：Designs, Codes and Cryptography
• 出版年：2014
• 出版时间：May 2014
• 年：2014
• 卷：71
• 期：2
• 页码：229-246
• 全文大小：446 KB
• 参考文献：1. Bose R.C., Chaudhuri D.K.R.: On a class of error correcting binary group codes. Inf. Control 3(1), 68-9 (1960) CrossRef
  2. Charpin P., Tiet?v?inen A., Zinoviev V.: On binary cyclic codes with minimum distance / d?=?3. Probl. Inf. Transm. 33(4), 287-96 (1997)
  3. Charpin P., Tiet?v?inen A., Zinoviev V.: On the minimum distances of non-binary cyclic codes. Des. Codes Cryptogr. 17, 81-5 (1999) CrossRef
  4. Duursma I.M., Koetter R.: Error-locating pairs for cyclic codes. IEEE Trans. Inf. Theory 40(4), 1108-121 (2002) CrossRef
  5. Feng G.L., Tzeng K.K.: Decoding cyclic and BCH codes up to actual minimum distance using nonrecurrent syndrome dependence relations. IEEE Trans. Inf. Theory 37(6), 1716-723 (1991) CrossRef
  6. Forney G.: On decoding BCH codes. IEEE Trans. Inf. Theory 11(4), 549-57 (1965) CrossRef
  7. Hartmann C.: Decoding beyond the BCH bound. IEEE Trans. Inf. Theory 18(3), 441-44 (1972) CrossRef
  8. Hartmann C., Tzeng K.: Generalizations of the BCH bound. Inf. Control 20(5), 489-98 (1972) CrossRef
  9. Hartmann C., Tzeng K.: Decoding beyond the BCH bound using multiple sets of syndrome sequences. IEEE Transactions on 20(2) (1974)
  10. Hocquenghem A.: Codes Correcteurs d’Erreurs. Chiffres (Paris) 2, 147-56 (1959)
  11. van Lint J., Wilson R.: On the minimum distance of cyclic codes. IEEE Trans. Inf. Theory 32(1), 23-0 (1986) CrossRef
  12. Massey J.: Reversible codes. Inf. Control 7(3), 369-80 (1964) CrossRef
  13. Reed I.S., Solomon G.: Polynomial codes over certain finite fields. J. Soc. Ind. Appl. Math. 8(2), 300-04 (1960) CrossRef
  14. Roos C.: A generalization of the BCH bound for cyclic codes, including the Hartmann-Tzeng bound. J. Comb. Theory Ser. A 33(2), 229-32 (1982) CrossRef
  15. Roos C.: A new lower bound for the minimum distance of a cyclic code. IEEE Trans. Inf. Theory 29(3), 330-32 (1983) CrossRef
  16. Sugiyama Y., Kasahara M., Hirasawa S., Namekawa T.: A method for solving key equation for decoding Goppa codes. Inf. Control 27(1), 87-9 (1975) CrossRef
  17. Zeh A., Wachter-Zeh A., Bezzateev S.: Decoding cyclic codes up to a new bound on the minimum distance. IEEE Trans. Inf. Theory 58(6), 3951-960 (2012) CrossRef
  18. Zetterberg L.H.: Cyclic codes from irreducible polynomials for correction of multiple errors. IRE Trans. Inf. Theory 8(1), 13-0 (1962) CrossRef
  
• 作者单位：Alexander Zeh (1) (2)
  Sergey Bezzateev (3)
  
  1. Institute of Communications Engineering, University of Ulm, Ulm, Germany
  2. INRIA Saclay-?le-de-France, école Polytechnique ParisTech, Palaiseau Cedex, France
  3. Saint Petersburg State University of Airspace Instrumentation, St. Petersburg, Russia
  
• ISSN：1573-7586

文摘

A new bound on the minimum distance of q-ary cyclic codes is proposed. It is based on the description by another cyclic code with small minimum distance. The connection to the BCH bound and the Hartmann–Tzeng (HT) bound is formulated explicitly. We show that for many cases our approach improves the HT bound. Furthermore, we refine our bound for several families of cyclic codes. We define syndromes and formulate a Key Equation that allows an efficient decoding up to our bound with the Extended Euclidean Algorithm. It turns out that lowest-code-rate cyclic codes with small minimum distances are useful for our approach. Therefore, we give a sufficient condition for binary cyclic codes of arbitrary length to have minimum distance two or three and lowest code-rate.