# American Institute of Mathematical Sciences

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:

show all references

##### References:
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