February  2018, 12(1): 81-106. doi: 10.3934/amc.2018005

Power decoding Reed-Solomon codes up to the Johnson radius

Technical University of Denmark, Department of Applied Mathematics and Computer Science, Matematiktorvet 1, 2800 Kgs. Lyngby, Denmark

Received  March 2016 Revised  September 2017 Published  March 2018

Power decoding, or "decoding using virtual interleaving" is a technique for decoding Reed-Solomon codes up to the Sudan radius. Since the method's inception, it has been an open question if it is possible to use this approach to decode up to the Johnson radius - the decoding radius of the Guruswami-Sudan algorithm. In this paper we show that this can be done by incorporating a notion of multiplicities. As the original Power decoding, the proposed algorithm is a one-pass algorithm: decoding follows immediately from solving a shift-register type equation, which we show can be done in quasi-linear time. It is a "partial bounded-distance decoding algorithm" since it will fail to return a codeword for a few error patterns within its decoding radius; we investigate its failure behaviour theoretically as well as give simulation results.

Citation: Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005
References:
[1]

A. AhmedR. Koetter and N. R. Shanbhag, VLSI architectures for soft-decision decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 57 (2011), 648-667.   Google Scholar

[2]

M. Alekhnovich, Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 51 (2005), 2257-2265.   Google Scholar

[3]

G. Baker and P. Graves-Morris, Padé Approximants, Cambridge Univ. Press, 1996.  Google Scholar

[4]

M. V. Barel and A. Bultheel, A general module theoretic framework for vector M-Padé and matrix rational interpolation, Numerical Algorithms, 3 (1992), 451-461.   Google Scholar

[5]

B. Beckermann and G. Labahn, A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matr. Anal. Appl., 15 (1994), 804-823.   Google Scholar

[6]

P. Beelen and K. Brander, Key equations for list decoding of Reed-Solomon codes and how to solve them, J. Symb. Comp., 45 (2010), 773-786.   Google Scholar

[7]

P. BeelenT. HøholdtJ. S. R. Nielsen and Y. Wu, On rational interpolation-based list-decoding and list-decoding binary Goppa codes, IEEE Trans. Inf. Theory, 59 (2013), 3269-3281.   Google Scholar

[8]

E. R. Berlekamp, Algebraic Coding Theory, Aegean Park Press, 1968.  Google Scholar

[9]

A. BostanC.-P. Jeannerod and E. Schost, Solving structured linear systems with large displacement rank, Th. Comp. Sc., 407 (2008), 155-181.   Google Scholar

[10]

M. ChowdhuryC.-P. JeannerodV. NeigerE. Schost and G. Villard, Faster algorithms for multivariate interpolation with multiplicities and simultaneous polynomial approximations, IEEE Trans. Inf. Theory, 61 (2015), 2370-2387.   Google Scholar

[11]

H. Cohn and N. Heninger, Approximate common divisors via lattices, Proc. ANTS, 1 (2012), 271-293.   Google Scholar

[12]

H. Cohn and N. Heninger, Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding, Adv. Math. Commun., 9 (2015), 311-339.   Google Scholar

[13]

P. Fitzpatrick, On the key equation, Inf. Theory, 41 (1995), 1290-1302.   Google Scholar

[14]

S. Gao, A new algorithm for decoding Reed-Solomon codes, in Communications, Information and Network Security, Springer, 2003, 55-68. Google Scholar

[15]

P. Giorgi, C. Jeannerod and G. Villard, On the complexity of polynomial matrix computations, in Proc. ISSAC, 2003,135-142.  Google Scholar

[16]

S. GuptaS. SarkarA. Storjohann and J. Valeriote, Triangular basis decompositions and derandomization of linear algebra algorithms over, J. Symb. Comp., 47 (2012), 422-453.   Google Scholar

[17]

V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon codes and algebraic-geometric codes, IEEE Trans. Inf. Theory, 45 (1999), 1757-1767.   Google Scholar

[18]

S. M. Johnson, A new upper bound for error-correcting codes, IEEE Trans. Inf. Theory, 46 (1962), 203-207.   Google Scholar

[19]

T. Kailath, Linear Systems, Prentice-Hall, 1980.  Google Scholar

[20]

R. Koetter and A. Vardy, A complexity reducing transformation in algebraic list decoding of Reed-Solomon codes, in Proc. IEEE ITW, 2003. Google Scholar

[21]

R. Koetter and A. Vardy, Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 49 (2003), 2809-2825.   Google Scholar

[22]

K. Lee and M. E. O'Sullivan, List decoding of Reed-Solomon codes from a Gröbner basis perspective, J. Symb. Comp., 43 (2008), 645-658.   Google Scholar

[23]

K. Lee and M. E. O'Sullivan, List decoding of Hermitian codes using Gröbner bases, J. Symb. Comp., 44 (2009), 1662-1675.   Google Scholar

[24]

W. Li, J. S. R. Nielsen and V. R. Sidorenko, On decoding of interleaved Chinese remainder codes, in Proc. MTNS, 2014. Google Scholar

[25]

M. Mohamed, S. Rizkalla, H. Zoerlein and M. Bossert, Deterministic compressed sensing with power decoding for complex Reed-Solomon codes, in Proc. SCC, 2015. Google Scholar

[26]

T. Mulders and A. Storjohann, On lattice reduction for polynomial matrices, J. Symb. Comp., 35 (2003), 377-401.   Google Scholar

[27]

V. Neiger, Fast computation of shifted Popov forms of polynomial matrices via systems of modular polynomial equations, 2016.  Google Scholar

[28]

V. Neiger, J. Rosenkilde and E. Schost, Fast computation of the roots of polynomials over the ring of power series, in Proc. ISSAC, 2017.  Google Scholar

[29]

J. S. R. Nielsen, Generalised multi-sequence shift-register synthesis using module minimisation, in Proc. IEEE ISIT, 2013,882-886. Google Scholar

[30]

J. S. R. Nielsen, List Decoding of Algebraic Codes, Ph. D thesis, Technical Univ. Denmark, 2013. Google Scholar

[31]

J. S. R. Nielsen, Power decoding of Reed-Solomon codes revisited, in Proc. ICMCTA, 2014. Google Scholar

[32]

J. S. R. Nielsen, Power decoding of Reed-Solomon up to the johnson radius, in Proc. ACCT, 2014. Google Scholar

[33]

J. S. R. Nielsen and P. Beelen, Sub-quadratic decoding of one-point Hermitian codes, IEEE Trans. Inf. Theory, 61 (2015), 3225-3240.   Google Scholar

[34]

R. R. Nielsen and T. Høholdt, Decoding Reed-Solomon codes beyond half the minimum distance, in Coding Theory, Cryptography and Related Areas, Springer, 1998,221-236.  Google Scholar

[35]

Z. Olesh and A. Storjohann, The vector rational function reconstruction problem, in Proc. WWCA, 2006,137-149.  Google Scholar

[36]

S. Puchinger and J. Rosenkilde, Decoding of interleaved Reed-Solomon codes using improved power decoding, in Proc. ISIT, 2017,356--360. Google Scholar

[37]

J. Rosenkilde and A. Storjohann, Algorithms for simultaneous Padé approximations, in Proc. ISSAC, 2016,405-412.  Google Scholar

[38]

J. Rosenkilde and A. Storjohann, Algorithms for simultaneous Hermite Padé approximations, in preparation, extension of [37].  Google Scholar

[39]

R. Roth, Introduction to Coding Theory, Cambridge Univ. Press, 2006. Google Scholar

[40]

R. Roth and G. Ruckenstein, Efficient decoding of Reed-Solomon codes beyond half the minimum distance, IEEE Trans. Inf. Theory, 46 (2000), 246-257.   Google Scholar

[41]

G. Schmidt, V. Sidorenko and M. Bossert, Decoding Reed-Solomon codes beyond half the minimum distance using shift-register synthesis, in Proc. IEEE ISIT, 2006,459-463. Google Scholar

[42]

G. SchmidtV. Sidorenko and M. Bossert, Syndrome decoding of Reed-Solomon codes beyond half the minimum distance based on shift-register synthesis, IEEE Trans. Inf. Theory, 56 (2010), 5245-5252.   Google Scholar

[43]

V. Sidorenko and M. Bossert, Fast skew-feedback shift-register synthesis, Des. Codes Crypt., 70 (2014), 55-67.   Google Scholar

[44]

V. Sidorenko and G. Schmidt, A linear algebraic approach to multisequence shift-register synthesis, Probl. Inf. Transm., 47 (2011), 149-165.   Google Scholar

[45]

W. A. Stein et al, SageMath Software, http://www.sagemath.org Google Scholar

[46]

A. Storjohann, High-order lifting and integrality certification, J. Symb. Comp., 36 (2003), 613-648.   Google Scholar

[47]

M. Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound, J. Complexity, 13 (1997), 180-193.   Google Scholar

[48]

Y. SugiyamaM. KasaharaS. Hirasawa and T. Namekawa, A method for solving key equation for decoding Goppa codes, Inf. Control, 27 (1975), 87-99.   Google Scholar

[49]

P. Trifonov and M. Lee, Efficient interpolation in the Wu list decoding algorithm, IEEE Trans. Inf. Theory, 58 (2012), 5963-5971.   Google Scholar

[50]

J. von zur Gathen and J. Gerhard, Modern Computer Algebra, 3rd edition, Cambridge Univ. Press, 2012.  Google Scholar

[51]

A. Wachter-ZehA. Zeh and M. Bossert, Decoding interleaved Reed-Solomon codes beyond their joint error-correcting capability, Des. Codes Crypt., 71 (2012), 261-281.   Google Scholar

[52]

Y. Wu, New list decoding algorithms for Reed-Solomon and BCH codes, IEEE Trans. Inf. Theory, 54 (2008), 3611-3630.   Google Scholar

[53]

A. ZehC. Gentner and D. Augot, An interpolation procedure for list decoding Reed-Solomon codes based on generalized key equations, IEEE Trans. Inf. Theory, 57 (2011), 5946-5959.   Google Scholar

[54]

A. Zeh, A. Wachter and M. Bossert, Unambiguous decoding of generalized Reed-Solomon codes beyond half the minimum distance, in Proc. IZS, 2012. Google Scholar

show all references

References:
[1]

A. AhmedR. Koetter and N. R. Shanbhag, VLSI architectures for soft-decision decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 57 (2011), 648-667.   Google Scholar

[2]

M. Alekhnovich, Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 51 (2005), 2257-2265.   Google Scholar

[3]

G. Baker and P. Graves-Morris, Padé Approximants, Cambridge Univ. Press, 1996.  Google Scholar

[4]

M. V. Barel and A. Bultheel, A general module theoretic framework for vector M-Padé and matrix rational interpolation, Numerical Algorithms, 3 (1992), 451-461.   Google Scholar

[5]

B. Beckermann and G. Labahn, A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matr. Anal. Appl., 15 (1994), 804-823.   Google Scholar

[6]

P. Beelen and K. Brander, Key equations for list decoding of Reed-Solomon codes and how to solve them, J. Symb. Comp., 45 (2010), 773-786.   Google Scholar

[7]

P. BeelenT. HøholdtJ. S. R. Nielsen and Y. Wu, On rational interpolation-based list-decoding and list-decoding binary Goppa codes, IEEE Trans. Inf. Theory, 59 (2013), 3269-3281.   Google Scholar

[8]

E. R. Berlekamp, Algebraic Coding Theory, Aegean Park Press, 1968.  Google Scholar

[9]

A. BostanC.-P. Jeannerod and E. Schost, Solving structured linear systems with large displacement rank, Th. Comp. Sc., 407 (2008), 155-181.   Google Scholar

[10]

M. ChowdhuryC.-P. JeannerodV. NeigerE. Schost and G. Villard, Faster algorithms for multivariate interpolation with multiplicities and simultaneous polynomial approximations, IEEE Trans. Inf. Theory, 61 (2015), 2370-2387.   Google Scholar

[11]

H. Cohn and N. Heninger, Approximate common divisors via lattices, Proc. ANTS, 1 (2012), 271-293.   Google Scholar

[12]

H. Cohn and N. Heninger, Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding, Adv. Math. Commun., 9 (2015), 311-339.   Google Scholar

[13]

P. Fitzpatrick, On the key equation, Inf. Theory, 41 (1995), 1290-1302.   Google Scholar

[14]

S. Gao, A new algorithm for decoding Reed-Solomon codes, in Communications, Information and Network Security, Springer, 2003, 55-68. Google Scholar

[15]

P. Giorgi, C. Jeannerod and G. Villard, On the complexity of polynomial matrix computations, in Proc. ISSAC, 2003,135-142.  Google Scholar

[16]

S. GuptaS. SarkarA. Storjohann and J. Valeriote, Triangular basis decompositions and derandomization of linear algebra algorithms over, J. Symb. Comp., 47 (2012), 422-453.   Google Scholar

[17]

V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon codes and algebraic-geometric codes, IEEE Trans. Inf. Theory, 45 (1999), 1757-1767.   Google Scholar

[18]

S. M. Johnson, A new upper bound for error-correcting codes, IEEE Trans. Inf. Theory, 46 (1962), 203-207.   Google Scholar

[19]

T. Kailath, Linear Systems, Prentice-Hall, 1980.  Google Scholar

[20]

R. Koetter and A. Vardy, A complexity reducing transformation in algebraic list decoding of Reed-Solomon codes, in Proc. IEEE ITW, 2003. Google Scholar

[21]

R. Koetter and A. Vardy, Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 49 (2003), 2809-2825.   Google Scholar

[22]

K. Lee and M. E. O'Sullivan, List decoding of Reed-Solomon codes from a Gröbner basis perspective, J. Symb. Comp., 43 (2008), 645-658.   Google Scholar

[23]

K. Lee and M. E. O'Sullivan, List decoding of Hermitian codes using Gröbner bases, J. Symb. Comp., 44 (2009), 1662-1675.   Google Scholar

[24]

W. Li, J. S. R. Nielsen and V. R. Sidorenko, On decoding of interleaved Chinese remainder codes, in Proc. MTNS, 2014. Google Scholar

[25]

M. Mohamed, S. Rizkalla, H. Zoerlein and M. Bossert, Deterministic compressed sensing with power decoding for complex Reed-Solomon codes, in Proc. SCC, 2015. Google Scholar

[26]

T. Mulders and A. Storjohann, On lattice reduction for polynomial matrices, J. Symb. Comp., 35 (2003), 377-401.   Google Scholar

[27]

V. Neiger, Fast computation of shifted Popov forms of polynomial matrices via systems of modular polynomial equations, 2016.  Google Scholar

[28]

V. Neiger, J. Rosenkilde and E. Schost, Fast computation of the roots of polynomials over the ring of power series, in Proc. ISSAC, 2017.  Google Scholar

[29]

J. S. R. Nielsen, Generalised multi-sequence shift-register synthesis using module minimisation, in Proc. IEEE ISIT, 2013,882-886. Google Scholar

[30]

J. S. R. Nielsen, List Decoding of Algebraic Codes, Ph. D thesis, Technical Univ. Denmark, 2013. Google Scholar

[31]

J. S. R. Nielsen, Power decoding of Reed-Solomon codes revisited, in Proc. ICMCTA, 2014. Google Scholar

[32]

J. S. R. Nielsen, Power decoding of Reed-Solomon up to the johnson radius, in Proc. ACCT, 2014. Google Scholar

[33]

J. S. R. Nielsen and P. Beelen, Sub-quadratic decoding of one-point Hermitian codes, IEEE Trans. Inf. Theory, 61 (2015), 3225-3240.   Google Scholar

[34]

R. R. Nielsen and T. Høholdt, Decoding Reed-Solomon codes beyond half the minimum distance, in Coding Theory, Cryptography and Related Areas, Springer, 1998,221-236.  Google Scholar

[35]

Z. Olesh and A. Storjohann, The vector rational function reconstruction problem, in Proc. WWCA, 2006,137-149.  Google Scholar

[36]

S. Puchinger and J. Rosenkilde, Decoding of interleaved Reed-Solomon codes using improved power decoding, in Proc. ISIT, 2017,356--360. Google Scholar

[37]

J. Rosenkilde and A. Storjohann, Algorithms for simultaneous Padé approximations, in Proc. ISSAC, 2016,405-412.  Google Scholar

[38]

J. Rosenkilde and A. Storjohann, Algorithms for simultaneous Hermite Padé approximations, in preparation, extension of [37].  Google Scholar

[39]

R. Roth, Introduction to Coding Theory, Cambridge Univ. Press, 2006. Google Scholar

[40]

R. Roth and G. Ruckenstein, Efficient decoding of Reed-Solomon codes beyond half the minimum distance, IEEE Trans. Inf. Theory, 46 (2000), 246-257.   Google Scholar

[41]

G. Schmidt, V. Sidorenko and M. Bossert, Decoding Reed-Solomon codes beyond half the minimum distance using shift-register synthesis, in Proc. IEEE ISIT, 2006,459-463. Google Scholar

[42]

G. SchmidtV. Sidorenko and M. Bossert, Syndrome decoding of Reed-Solomon codes beyond half the minimum distance based on shift-register synthesis, IEEE Trans. Inf. Theory, 56 (2010), 5245-5252.   Google Scholar

[43]

V. Sidorenko and M. Bossert, Fast skew-feedback shift-register synthesis, Des. Codes Crypt., 70 (2014), 55-67.   Google Scholar

[44]

V. Sidorenko and G. Schmidt, A linear algebraic approach to multisequence shift-register synthesis, Probl. Inf. Transm., 47 (2011), 149-165.   Google Scholar

[45]

W. A. Stein et al, SageMath Software, http://www.sagemath.org Google Scholar

[46]

A. Storjohann, High-order lifting and integrality certification, J. Symb. Comp., 36 (2003), 613-648.   Google Scholar

[47]

M. Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound, J. Complexity, 13 (1997), 180-193.   Google Scholar

[48]

Y. SugiyamaM. KasaharaS. Hirasawa and T. Namekawa, A method for solving key equation for decoding Goppa codes, Inf. Control, 27 (1975), 87-99.   Google Scholar

[49]

P. Trifonov and M. Lee, Efficient interpolation in the Wu list decoding algorithm, IEEE Trans. Inf. Theory, 58 (2012), 5963-5971.   Google Scholar

[50]

J. von zur Gathen and J. Gerhard, Modern Computer Algebra, 3rd edition, Cambridge Univ. Press, 2012.  Google Scholar

[51]

A. Wachter-ZehA. Zeh and M. Bossert, Decoding interleaved Reed-Solomon codes beyond their joint error-correcting capability, Des. Codes Crypt., 71 (2012), 261-281.   Google Scholar

[52]

Y. Wu, New list decoding algorithms for Reed-Solomon and BCH codes, IEEE Trans. Inf. Theory, 54 (2008), 3611-3630.   Google Scholar

[53]

A. ZehC. Gentner and D. Augot, An interpolation procedure for list decoding Reed-Solomon codes based on generalized key equations, IEEE Trans. Inf. Theory, 57 (2011), 5946-5959.   Google Scholar

[54]

A. Zeh, A. Wachter and M. Bossert, Unambiguous decoding of generalized Reed-Solomon codes beyond half the minimum distance, in Proc. IZS, 2012. Google Scholar

Table 1.  Simulation results. $P_f(\tau)$ denotes the observed probability of decoding failure (no result or wrong result) with random errors of weight exactly $\tau$. $\tau_{\rm bnd}$ indicates the number of errors ${\epsilon}$ for which Proposition 5 yields a bound $< 1$ (where applicable); in parentheses is if the probability estimate of (7) is used instead.
$[n,k]_q$ $(s,\ell)$ $\tau_{\text{Pow}}$ ${{P}_{f}}(\left\lfloor {{\tau }_{\text{Pow}}} \right\rfloor -1)$ $P_f(\left\lfloor{{\tau_{\text{Pow}}}} \right\rfloor)$ $P_f(\left\lfloor{{\tau_{\text{Pow}}}} \right\rfloor + 1)$ $\tau_{\rm bnd}$
$[21, 3]_{23}$ $(6,19)$ $14\,{}^{1}\!\!\diagup\!\!{}_{20}\;$ $ 7.43 \times 10^{-3} $ $ 1.97 \times 10^{-1} $ $ 1 $
$[24, 7]_{25}$ $(2,3)$ $10\,{}^{1}\!\!\diagup\!\!{}_{4}\;$ $0$ $ 2.27 \times 10^{-3} $ $ 1 $ 8 (9)
$[32, 10]_{37}$ $(2,4)$ $13$ $0$ $ 2.78 \times 10^{-2} $ $ 1 $
$[64, 27]_{64}$ $(2,3)$ $20\,{}^{1}\!\!\diagup\!\!{}_{4}\;$ $0$ $ 3.10 \times 10^{-4} $ $ 1 $ 19 (19)
$[68, 31]_{71}$ $(3,4)$ $20$ $0$ $0$ $ 1$
$[125, 51]_{125}$ $(4,6)$ $42$ $0$ $0$ $ 1$
$[256, 63]_{256}$ $(2,4)$ $116\,{}^{2}\!\!\diagup\!\!{}_{5}\;$ $0$ $0$ $ 1- 3.00 \times 10^{-4} $
$[n,k]_q$ $(s,\ell)$ $\tau_{\text{Pow}}$ ${{P}_{f}}(\left\lfloor {{\tau }_{\text{Pow}}} \right\rfloor -1)$ $P_f(\left\lfloor{{\tau_{\text{Pow}}}} \right\rfloor)$ $P_f(\left\lfloor{{\tau_{\text{Pow}}}} \right\rfloor + 1)$ $\tau_{\rm bnd}$
$[21, 3]_{23}$ $(6,19)$ $14\,{}^{1}\!\!\diagup\!\!{}_{20}\;$ $ 7.43 \times 10^{-3} $ $ 1.97 \times 10^{-1} $ $ 1 $
$[24, 7]_{25}$ $(2,3)$ $10\,{}^{1}\!\!\diagup\!\!{}_{4}\;$ $0$ $ 2.27 \times 10^{-3} $ $ 1 $ 8 (9)
$[32, 10]_{37}$ $(2,4)$ $13$ $0$ $ 2.78 \times 10^{-2} $ $ 1 $
$[64, 27]_{64}$ $(2,3)$ $20\,{}^{1}\!\!\diagup\!\!{}_{4}\;$ $0$ $ 3.10 \times 10^{-4} $ $ 1 $ 19 (19)
$[68, 31]_{71}$ $(3,4)$ $20$ $0$ $0$ $ 1$
$[125, 51]_{125}$ $(4,6)$ $42$ $0$ $0$ $ 1$
$[256, 63]_{256}$ $(2,4)$ $116\,{}^{2}\!\!\diagup\!\!{}_{5}\;$ $0$ $0$ $ 1- 3.00 \times 10^{-4} $
[1]

Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311

[2]

Yujuan Li, Guizhen Zhu. On the error distance of extended Reed-Solomon codes. Advances in Mathematics of Communications, 2016, 10 (2) : 413-427. doi: 10.3934/amc.2016015

[3]

Peter Beelen, David Glynn, Tom Høholdt, Krishna Kaipa. Counting generalized Reed-Solomon codes. Advances in Mathematics of Communications, 2017, 11 (4) : 777-790. doi: 10.3934/amc.2017057

[4]

Antonio Cafure, Guillermo Matera, Melina Privitelli. Singularities of symmetric hypersurfaces and Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (1) : 69-94. doi: 10.3934/amc.2012.6.69

[5]

José Moreira, Marcel Fernández, Miguel Soriano. On the relationship between the traceability properties of Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (4) : 467-478. doi: 10.3934/amc.2012.6.467

[6]

Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485

[7]

Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046

[8]

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

[9]

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007

[10]

Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443

[11]

Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505

[12]

Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433

[13]

Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer. The secrecy capacity of the arbitrarily varying wiretap channel under list decoding. Advances in Mathematics of Communications, 2019, 13 (1) : 11-39. doi: 10.3934/amc.2019002

[14]

Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385

[15]

Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83

[16]

Holger Boche, Rafael F. Schaefer. Arbitrarily varying multiple access channels with conferencing encoders: List decoding and finite coordination resources. Advances in Mathematics of Communications, 2016, 10 (2) : 333-354. doi: 10.3934/amc.2016009

[17]

Jonas Eriksson. A weight-based characterization of the set of correctable error patterns under list-of-2 decoding. Advances in Mathematics of Communications, 2007, 1 (3) : 331-356. doi: 10.3934/amc.2007.1.331

[18]

Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179

[19]

Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419

[20]

Anas Chaaban, Vladimir Sidorenko, Christian Senger. On multi-trial Forney-Kovalev decoding of concatenated codes. Advances in Mathematics of Communications, 2014, 8 (1) : 1-20. doi: 10.3934/amc.2014.8.1

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (50)
  • HTML views (125)
  • Cited by (0)

Other articles
by authors

[Back to Top]