nach oben

Designs, Codes and Cryptography

Erschienen in:

01.11.2014

Multi-trial Guruswami–Sudan decoding for generalised Reed–Solomon codes

verfasst von: Johan S. R. Nielsen, Alexander Zeh

Erschienen in: Designs, Codes and Cryptography | Ausgabe 2/2014

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

An iterated refinement procedure for the Guruswami–Sudan list decoding algorithm for Generalised Reed–Solomon codes based on Alekhnovich’s module minimisation is proposed. The method is parametrisable and allows variants of the usual list decoding approach. In particular, finding the list of closest codewords within an intermediate radius can be performed with improved average-case complexity while retaining the worst-case complexity. We provide a detailed description of the module minimisation, reanalysing the Mulders–Storjohann algorithm and drawing new connections to both Alekhnovich’s algorithm and Lee–O’Sullivan’s. Furthermore, we show how to incorporate the re-encoding technique of Kötter and Vardy into our iterative algorithm.

Vorheriger Artikel More differentially 6-uniform power functions

Nächster Artikel Paillier-based publicly verifiable (non-interactive) secret sharing

Alekhnovich M.: Linear diophantine equations over polynomials and soft decoding of Reed–Solomon codes. IEEE Trans. Inf. Theory 51(7), 2257–2265 (2005).

Bassalygo L.A.: New upper bounds for error-correcting codes. Prob. Inf. Trans. 1(4), 41–44 (1965).

Beelen P., Brander K.: Key equations for list decoding of Reed–Solomon codes and how to solve them. J. Symb. Comput. 45(7), 773–786 (2010).

Beelen P., Høholdt T., Nielsen J.S.R., Wu Y.: On rational interpolation-based list-decoding and list-decoding binary Goppa codes. IEEE Trans. Inf. Theory 59(6), 3269–3281 (2013).

Bernstein D.J.: List decoding for binary Goppa codes. In: IWCC, LNCS, vol. 6639, pp. 62–80. Springer, Heidelberg (2011).

Brander K.: Interpolation and list decoding of algebraic codes. Ph.D. thesis, Technical University of Denmark (2010).

Cassuto Y., Bruck J., McEliece R.: On the average complexity of Reed–Solomon list decoders. IEEE Trans. Inf. Theory 59(4), 2336–2351 (2013).

Chowdhury M.F.I., Jeannerod C.P., Neiger V., Schost E., Villard G.: Faster algorithms for multivariate interpolation with multiplicities and simultaneous polynomial approximations. arXiv:1402.0643 (2014). http://arxiv.org/abs/1402.0643.

von zur Gathen J., Gerhard J.: Modern Computer Algebra. Cambridge University Press, Cambridge (2003).

10.

Giorgi P., Jeannerod C., Villard G.: On the complexity of polynomial matrix computations. In: Proceedings of International Symposium on Symbolic and Algebraic Computation, pp. 135–142. ACM (2003).

11.

Guruswami V., Sudan M.: Improved decoding of Reed–Solomon codes and algebraic geometry codes. IEEE Trans. Inf. Theory 45(6), 1757–1767 (1999).

12.

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

13.

Kötter R., Vardy A.: A complexity reducing transformation in algebraic list decoding of Reed–Solomon codes. In: IEEE Information Theory Workshop (ITW), pp. 10–13. Paris, France (2003).

14.

Kötter R., Vardy A.: Algebraic soft-decision decoding of Reed–Solomon codes. IEEE Trans. Inf. Theory 49(11), 2809–2825 (2003).

15.

Kötter R., Ma J., Vardy A.: The re-encoding transformation in algebraic list-decoding of Reed–Solomon codes. IEEE Trans. Inf. Theory 57(2), 633–647 (2011).

16.

Lee K., O’Sullivan M.E.: List decoding of Reed–Solomon codes from a Gröbner basis perspective. J. Symb. Comput. 43(9), 645–658 (2008).

17.

Lenstra A.: Factoring multivariate polynomials over finite fields. J. Comput. Syst. Sci. 30(2), 235–248 (1985).

18.

Mulders T., Storjohann A.: On lattice reduction for polynomial matrices. J. Symb. Comput. 35(4), 377–401 (2003).

19.

Nielsen J.S.R.: List decoding of algebraic codes. Ph.D. thesis, Technical University of Denmark, Kongens Lyngby (2013).

20.

Nielsen J.S.R., Zeh A.: Multi-trial Guruswami–Sudan decoding for generalised Reed–Solomon codes. In: Workshop on Coding and Cryptography (2013).

21.

Roth R., Ruckenstein G.: Efficient decoding of Reed–Solomon codes beyond half the minimum distance. IEEE Trans. Inf. Theory 46(1), 246–257 (2000).

22.

Stein W., et al.: Sage Mathematics Software (Version 5.13, Release Date: 2013-12-15). The Sage Development Team (2013). http://www.sagemath.org.

23.

Sudan M.: Decoding of Reed–Solomon codes beyond the error-correction bound. J. Complex. 13(1), 180–193 (1997).

24.

Tang S., Chen L., Ma X.: Progressive list-enlarged algebraic soft decoding of Reed–Solomon codes. IEEE Commun. Lett. 16(6), 901–904 (2012).

25.

Zeh A., Gentner C., Augot D.: An interpolation procedure for list decoding Reed–Solomon codes based on generalized key equations. IEEE Trans. Inf. Theory 57(9), 5946–5959 (2011).

Titel: Multi-trial Guruswami–Sudan decoding for generalised Reed–Solomon codes
verfasst von: Johan S. R. Nielsen
Alexander Zeh
Publikationsdatum: 01.11.2014
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 2/2014
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-014-9951-7

Springer Professional

Multi-trial Guruswami–Sudan decoding for generalised Reed–Solomon codes

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 2/2014

Exponents of polar codes using algebraic geometric code kernels

On transform-domain error and erasure correction by Gabidulin codes

Distinguisher-based attacks on public-key cryptosystems using Reed–Solomon codes

Connections between Construction D and related constructions of lattices

Improved algorithms for finding low-weight polynomial multiples in and some cryptographic applications

A matrix approach for constructing quadratic APN functions

Premium Partner