Article Contents
Article Contents

# Power decoding Reed-Solomon codes up to the Johnson radius

• 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.

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

 Citation:

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

Tables(1)