American Institute of Mathematical Sciences

Advanced
August  2012, 6(3): 259-272. doi: 10.3934/amc.2012.6.259

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

Fernando Hernando 1, , Tom Høholdt 2, and  Diego Ruano 3,

1. 

Department of Mathematics, Universidad Jaume I, Campus Riu Sec, 12071, Castellón de la plana, Spain
2. 

DTU-Mathematics, Technical University of Denmark, Matematiktorvet, Building 303, 2800 Kgs. Lyngby, Denmark
3. 

Department of Mathematical Sciences, Aalborg University, Fr. Bajersvej 7G, 9920-Aalborg Øst, Denmark

Received  March 2011 Revised  January 2012 Published  August 2012

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: list decoding, quasi-cyclic code., Linear code, matrix-product code.
Mathematics Subject Classification: Primary: 94B05; Secondary: 94B3.
Citation: Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259
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.  doi: 10.1016/j.jsc.2010.03.010.  Google Scholar

[2]

T. Blackmore and G. H. Norton, Matrix-product codes over $\mathbb F_q$,, Appl. Algebra Engrg. Comm. Comput., 12 (2001), 477.  doi: 10.1007/PL00004226.  Google Scholar

[3]

I. I. Dumer, Concatenated codes and their multilevel generalizations,, in, (1998), 1911.   Google Scholar

[4]

P. Elias, List decoding for noisy channels,, Rep. No. 335, (1957).   Google Scholar

[5]

V. Guruswami and A. Rudra, Better binary list decodable codes via multilevel concatenation,, IEEE Trans. Inform. Theory, 55 (2009), 19.  doi: 10.1109/TIT.2008.2008124.  Google Scholar

[6]

V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes,, IEEE Trans. Inform. Theory, 45 (1999), 1757.  doi: 10.1109/18.782097.  Google Scholar

[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.  doi: 10.1007/s00200-009-0113-5.  Google Scholar

[8]

F. Hernando and D. Ruano, New linear codes from matrix-product codes with polynomial units,, Adv. Math. Commun., 4 (2010), 363.  doi: 10.3934/amc.2010.4.363.  Google Scholar

[9]

T. Kasami, A Gilbert-Varshamov bound for quasi-cyclic codes of rate 1/2,, IEEE Trans. Inform. Theory, IT-20 (1974).  doi: 10.1109/TIT.1974.1055262.  Google Scholar

[10]

K. Lally, Quasicyclic codes - some practical issues,, in, (2002).   Google Scholar

[11]

K. Lally and P. Fitzpatrick, Algebraic structure of quasicyclic codes,, Discrete Appl. Math., 111 (2001), 157.  doi: 10.1016/S0166-218X(00)00350-4.  Google Scholar

[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.  doi: 10.1016/j.jsc.2008.01.002.  Google Scholar

[13]

R. R. Nielsen and T. Høholdt, Decoding Reed-Solomon codes beyond half the minimum distance,, in, (2000), 221.   Google Scholar

[14]

F. Özbudak and H. Stichtenoth, Note on Niederreiter-Xing's propagation rule for linear codes,, Appl. Algebra Engrg. Comm. Comput., 13 (2002), 53.  doi: 10.1007/s002000100091.  Google Scholar

[15]

W. C. Schmid and R. Schürer, "Mint,'', Dept. of Mathematics, ().   Google Scholar

[16]

J. M. Wozencraft, List decoding,, in, (1958), 90.   Google Scholar

show all references

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.  doi: 10.1016/j.jsc.2010.03.010.  Google Scholar

[2]

T. Blackmore and G. H. Norton, Matrix-product codes over $\mathbb F_q$,, Appl. Algebra Engrg. Comm. Comput., 12 (2001), 477.  doi: 10.1007/PL00004226.  Google Scholar

[3]

I. I. Dumer, Concatenated codes and their multilevel generalizations,, in, (1998), 1911.   Google Scholar

[4]

P. Elias, List decoding for noisy channels,, Rep. No. 335, (1957).   Google Scholar

[5]

V. Guruswami and A. Rudra, Better binary list decodable codes via multilevel concatenation,, IEEE Trans. Inform. Theory, 55 (2009), 19.  doi: 10.1109/TIT.2008.2008124.  Google Scholar

[6]

V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes,, IEEE Trans. Inform. Theory, 45 (1999), 1757.  doi: 10.1109/18.782097.  Google Scholar

[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.  doi: 10.1007/s00200-009-0113-5.  Google Scholar

[8]

F. Hernando and D. Ruano, New linear codes from matrix-product codes with polynomial units,, Adv. Math. Commun., 4 (2010), 363.  doi: 10.3934/amc.2010.4.363.  Google Scholar

[9]

T. Kasami, A Gilbert-Varshamov bound for quasi-cyclic codes of rate 1/2,, IEEE Trans. Inform. Theory, IT-20 (1974).  doi: 10.1109/TIT.1974.1055262.  Google Scholar

[10]

K. Lally, Quasicyclic codes - some practical issues,, in, (2002).   Google Scholar

[11]

K. Lally and P. Fitzpatrick, Algebraic structure of quasicyclic codes,, Discrete Appl. Math., 111 (2001), 157.  doi: 10.1016/S0166-218X(00)00350-4.  Google Scholar

[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.  doi: 10.1016/j.jsc.2008.01.002.  Google Scholar

[13]

R. R. Nielsen and T. Høholdt, Decoding Reed-Solomon codes beyond half the minimum distance,, in, (2000), 221.   Google Scholar

[14]

F. Özbudak and H. Stichtenoth, Note on Niederreiter-Xing's propagation rule for linear codes,, Appl. Algebra Engrg. Comm. Comput., 13 (2002), 53.  doi: 10.1007/s002000100091.  Google Scholar

[15]

W. C. Schmid and R. Schürer, "Mint,'', Dept. of Mathematics, ().   Google Scholar

[16]

J. M. Wozencraft, List decoding,, in, (1958), 90.   Google Scholar

[1]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046
[2]

Akbar Mahmoodi Rishakani, Seyed Mojtaba Dehnavi, Mohmmadreza Mirzaee Shamsabad, Nasour Bagheri. Cryptographic properties of cyclic binary matrices. Advances in Mathematics of Communications, 2021, 15 (2) : 311-327. doi: 10.3934/amc.2020068
[3]

San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038
[4]

Nitha Niralda P C, Sunil Mathew. On properties of similarity boundary of attractors in product dynamical systems. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021004
[5]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012
[6]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012
[7]

Eric Foxall. Boundary dynamics of the replicator equations for neutral models of cyclic dominance. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1061-1082. doi: 10.3934/dcdsb.2020153
[8]

Buddhadev Pal, Pankaj Kumar. A family of multiply warped product semi-Riemannian Einstein metrics. Journal of Geometric Mechanics, 2020, 12 (4) : 553-562. doi: 10.3934/jgm.2020017
[9]

Guido Cavallaro, Roberto Garra, Carlo Marchioro. Long time localization of modified surface quasi-geostrophic equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020336
[10]

Yanhong Zhang. Global attractors of two layer baroclinic quasi-geostrophic model. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021023
[11]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018
[12]

Jann-Long Chern, Sze-Guang Yang, Zhi-You Chen, Chih-Her Chen. On the family of non-topological solutions for the elliptic system arising from a product Abelian gauge field theory. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3291-3304. doi: 10.3934/dcds.2020127
[13]

Ömer Arslan, Selçuk Kürşat İşleyen. A model and two heuristic methods for The Multi-Product Inventory-Location-Routing Problem with heterogeneous fleet. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021002
[14]

Bing Sun, Liangyun Chen, Yan Cao. On the universal $ \alpha $-central extensions of the semi-direct product of Hom-preLie algebras. Electronic Research Archive, , () : -. doi: 10.3934/era.2021004
[15]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[16]

Wenmeng Geng, Kai Tao. Large deviation theorems for dirichlet determinants of analytic quasi-periodic jacobi operators with Brjuno-Rüssmann frequency. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5305-5335. doi: 10.3934/cpaa.2020240
[17]

Jianfeng Huang, Haihua Liang. Limit cycles of planar system defined by the sum of two quasi-homogeneous vector fields. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 861-873. doi: 10.3934/dcdsb.2020145
[18]

Jingjing Wang, Zaiyun Peng, Zhi Lin, Daqiong Zhou. On the stability of solutions for the generalized vector quasi-equilibrium problems via free-disposal set. Journal of Industrial & Management Optimization, 2021, 17 (2) : 869-887. doi: 10.3934/jimo.2020002
[19]

S. Sadeghi, H. Jafari, S. Nemati. Solving fractional Advection-diffusion equation using Genocchi operational matrix based on Atangana-Baleanu derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020435
[20]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (74)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences