List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes

Fernando Hernando; Tom Høholdt; Diego Ruano

doi:10.3934/amc.2012.6.259

Article Contents

2012, Volume 6, Issue 3: 259-272. Doi: 10.3934/amc.2012.6.259

This issue Previous Article Next Article Wet paper codes and the dual distance in steganography

List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes

1.
Department of Mathematics, Universidad Jaume I, Campus Riu Sec, 12071, Castellón de la plana
2.
DTU-Mathematics, Technical University of Denmark, Matematiktorvet, Building 303, 2800 Kgs. Lyngby
3.
Department of Mathematical Sciences, Aalborg University, Fr. Bajersvej 7G, 9920-Aalborg Øst

Received: March 2011

Revised: January 2012

Published: August 2012

Abstract / Introduction Related Papers Cited by

Abstract

A list decoding algorithm for matrix-product codes is provided when $C_1, ..., C_s$ are nested linear codes and $A$ is a non-singular by columns matrix. We estimate the probability of getting more than one codeword as output when the constituent codes are Reed-Solomon codes. We extend this list decoding algorithm for matrix-product codes with polynomial units, which are quasi-cyclic codes. Furthermore, it allows us to consider unique decoding for matrix-product codes with polynomial units.

Keywords:

Mathematics Subject Classification: Primary: 94B05; Secondary: 94B35.

Citation:

Related Papers

Cited by

References

[1]	P. Beelen and K. Brander, Key equations for list decoding of Reed-Solomon codes and how to solve them, J. Symbolic Comput., 45 (2010), 773-786.doi: 10.1016/j.jsc.2010.03.010.
[2]	T. Blackmore and G. H. Norton, Matrix-product codes over $\mathbb F_q$, Appl. Algebra Engrg. Comm. Comput., 12 (2001), 477-500.doi: 10.1007/PL00004226.
[3]	I. I. Dumer, Concatenated codes and their multilevel generalizations, in "Handbook of Coding Theory,'' North-Holland, Amsterdam, (1998), 1911-1988.
[4]	P. Elias, List decoding for noisy channels, Rep. No. 335, Research Laboratory of Electronics, MIT, Cambridge, MA, 1957.
[5]	V. Guruswami and A. Rudra, Better binary list decodable codes via multilevel concatenation, IEEE Trans. Inform. Theory, 55 (2009), 19-26.doi: 10.1109/TIT.2008.2008124.
[6]	V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Trans. Inform. Theory, 45 (1999), 1757-1767.doi: 10.1109/18.782097.
[7]	F. Hernando, K. Lally and D. Ruano, Construction and decoding of matrix-product codes from nested codes, Appl. Algebra Engrg. Comm. Comput., 20 (2009), 497-507.doi: 10.1007/s00200-009-0113-5.
[8]	F. Hernando and D. Ruano, New linear codes from matrix-product codes with polynomial units, Adv. Math. Commun., 4 (2010), 363-367.doi: 10.3934/amc.2010.4.363.
[9]	T. Kasami, A Gilbert-Varshamov bound for quasi-cyclic codes of rate 1/2, IEEE Trans. Inform. Theory, IT-20 (1974), 679.doi: 10.1109/TIT.1974.1055262.
[10]	K. Lally, Quasicyclic codes - some practical issues, in "Proceedings of 2002 IEEE International Symposium on Information Theory,'' 2002.
[11]	K. Lally and P. Fitzpatrick, Algebraic structure of quasicyclic codes, Discrete Appl. Math., 111 (2001), 157-175.doi: 10.1016/S0166-218X(00)00350-4.
[12]	K. Lee and M. E. O'Sullivan, List decoding of Reed-Solomon codes from a Gröbner basis perspective, J. Symbolic Comput., 43 (2008), 645-658.doi: 10.1016/j.jsc.2008.01.002.
[13]	R. R. Nielsen and T. Høholdt, Decoding Reed-Solomon codes beyond half the minimum distance, in "Coding Theory, Cryptography and Related Areas (Guanajuato, 1998),'' Springer, Berlin, (2000), 221-236.
[14]	F. Özbudak and H. Stichtenoth, Note on Niederreiter-Xing's propagation rule for linear codes, Appl. Algebra Engrg. Comm. Comput., 13 (2002), 53-56.doi: 10.1007/s002000100091.
[15]	W. C. Schmid and R. Schürer, "Mint,'' Dept. of Mathematics, University of Salzburg, http://mint.sbg.ac.at/about.php
[16]	J. M. Wozencraft, List decoding, in "Quarterly Progress Report,'' MIT, Cambridge, MA, (1958), 90-95.