Power decoding Reed-Solomon codes up to the Johnson radius

Johan Rosenkilde

doi:10.3934/amc.2018005

Article Contents

2018, Volume 12, Issue 1: 81-106. Doi: 10.3934/amc.2018005

This issue Previous Article Construction of optimal low-hit-zone frequency hopping sequence sets under periodic partial Hamming correlation Next Article Singleton bounds for R-additive codes

Power decoding Reed-Solomon codes up to the Johnson radius

Johan Rosenkilde

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

Received: March 2016

Revised: September 2017

Published: February 2018

Abstract / Introduction Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 94B35, 11T71; Secondary: 41A28, 41A21, 94A55.

Citation:

Full Text(HTML)

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} $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

	A. Ahmed , R. Koetter and N. R. Shanbhag , VLSI architectures for soft-decision decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 57 (2011) , 648-667.
	M. Alekhnovich , Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 51 (2005) , 2257-2265.
	G. Baker and P. Graves-Morris, Padé Approximants, Cambridge Univ. Press, 1996.
	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.
	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.
	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.
	P. Beelen , T. Høholdt , J. 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.
	E. R. Berlekamp, Algebraic Coding Theory, Aegean Park Press, 1968.
	A. Bostan , C.-P. Jeannerod and E. Schost , Solving structured linear systems with large displacement rank, Th. Comp. Sc., 407 (2008) , 155-181.
	M. Chowdhury , C.-P. Jeannerod , V. Neiger , E. Schost and G. Villard , Faster algorithms for multivariate interpolation with multiplicities and simultaneous polynomial approximations, IEEE Trans. Inf. Theory, 61 (2015) , 2370-2387.
	H. Cohn and N. Heninger , Approximate common divisors via lattices, Proc. ANTS, 1 (2012) , 271-293.
	H. Cohn and N. Heninger , Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding, Adv. Math. Commun., 9 (2015) , 311-339.
	P. Fitzpatrick , On the key equation, Inf. Theory, 41 (1995) , 1290-1302.
	S. Gao, A new algorithm for decoding Reed-Solomon codes, in Communications, Information and Network Security, Springer, 2003, 55-68.
	P. Giorgi, C. Jeannerod and G. Villard, On the complexity of polynomial matrix computations, in Proc. ISSAC, 2003,135-142.
	S. Gupta , S. Sarkar , A. Storjohann and J. Valeriote , Triangular basis decompositions and derandomization of linear algebra algorithms over, J. Symb. Comp., 47 (2012) , 422-453.
	V. Guruswami and M. Sudan , Improved decoding of Reed-Solomon codes and algebraic-geometric codes, IEEE Trans. Inf. Theory, 45 (1999) , 1757-1767.
	S. M. Johnson , A new upper bound for error-correcting codes, IEEE Trans. Inf. Theory, 46 (1962) , 203-207.
	T. Kailath, Linear Systems, Prentice-Hall, 1980.
	R. Koetter and A. Vardy, A complexity reducing transformation in algebraic list decoding of Reed-Solomon codes, in Proc. IEEE ITW, 2003.
	R. Koetter and A. Vardy , Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 49 (2003) , 2809-2825.
	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.
	K. Lee and M. E. O'Sullivan , List decoding of Hermitian codes using Gröbner bases, J. Symb. Comp., 44 (2009) , 1662-1675.
	W. Li, J. S. R. Nielsen and V. R. Sidorenko, On decoding of interleaved Chinese remainder codes, in Proc. MTNS, 2014.
	M. Mohamed, S. Rizkalla, H. Zoerlein and M. Bossert, Deterministic compressed sensing with power decoding for complex Reed-Solomon codes, in Proc. SCC, 2015.
	T. Mulders and A. Storjohann , On lattice reduction for polynomial matrices, J. Symb. Comp., 35 (2003) , 377-401.
	V. Neiger, Fast computation of shifted Popov forms of polynomial matrices via systems of modular polynomial equations, 2016.
	V. Neiger, J. Rosenkilde and E. Schost, Fast computation of the roots of polynomials over the ring of power series, in Proc. ISSAC, 2017.
	J. S. R. Nielsen, Generalised multi-sequence shift-register synthesis using module minimisation, in Proc. IEEE ISIT, 2013,882-886.
	J. S. R. Nielsen, List Decoding of Algebraic Codes, Ph. D thesis, Technical Univ. Denmark, 2013.
	J. S. R. Nielsen, Power decoding of Reed-Solomon codes revisited, in Proc. ICMCTA, 2014.
	J. S. R. Nielsen, Power decoding of Reed-Solomon up to the johnson radius, in Proc. ACCT, 2014.
	J. S. R. Nielsen and P. Beelen , Sub-quadratic decoding of one-point Hermitian codes, IEEE Trans. Inf. Theory, 61 (2015) , 3225-3240.
	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.
	Z. Olesh and A. Storjohann, The vector rational function reconstruction problem, in Proc. WWCA, 2006,137-149.
	S. Puchinger and J. Rosenkilde, Decoding of interleaved Reed-Solomon codes using improved power decoding, in Proc. ISIT, 2017,356--360.
	J. Rosenkilde and A. Storjohann, Algorithms for simultaneous Padé approximations, in Proc. ISSAC, 2016,405-412.
	J. Rosenkilde and A. Storjohann, Algorithms for simultaneous Hermite Padé approximations, in preparation, extension of [37].
	R. Roth, Introduction to Coding Theory, Cambridge Univ. Press, 2006.
	R. Roth and G. Ruckenstein , Efficient decoding of Reed-Solomon codes beyond half the minimum distance, IEEE Trans. Inf. Theory, 46 (2000) , 246-257.
	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.
	G. Schmidt , V. 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.
	V. Sidorenko and M. Bossert , Fast skew-feedback shift-register synthesis, Des. Codes Crypt., 70 (2014) , 55-67.
	V. Sidorenko and G. Schmidt , A linear algebraic approach to multisequence shift-register synthesis, Probl. Inf. Transm., 47 (2011) , 149-165.
	W. A. Stein et al, SageMath Software, http://www.sagemath.org
	A. Storjohann , High-order lifting and integrality certification, J. Symb. Comp., 36 (2003) , 613-648.
	M. Sudan , Decoding of Reed-Solomon codes beyond the error-correction bound, J. Complexity, 13 (1997) , 180-193.
	Y. Sugiyama , M. Kasahara , S. Hirasawa and T. Namekawa , A method for solving key equation for decoding Goppa codes, Inf. Control, 27 (1975) , 87-99.
	P. Trifonov and M. Lee , Efficient interpolation in the Wu list decoding algorithm, IEEE Trans. Inf. Theory, 58 (2012) , 5963-5971.
	J. von zur Gathen and J. Gerhard, Modern Computer Algebra, 3rd edition, Cambridge Univ. Press, 2012.
	A. Wachter-Zeh , A. Zeh and M. Bossert , Decoding interleaved Reed-Solomon codes beyond their joint error-correcting capability, Des. Codes Crypt., 71 (2012) , 261-281.
	Y. Wu , New list decoding algorithms for Reed-Solomon and BCH codes, IEEE Trans. Inf. Theory, 54 (2008) , 3611-3630.
	A. Zeh , C. 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.
	A. Zeh, A. Wachter and M. Bossert, Unambiguous decoding of generalized Reed-Solomon codes beyond half the minimum distance, in Proc. IZS, 2012.