Les codes algébriques principaux et leur décodage

Augot, Daniel

Journées Nationales de Calcul Formel. 3 – 7 Mai 2010, Les cours du CIRM, no. 2 (2010), pp. 31-74.

[1] Ashbrook, J. B.; Shanbhag, N. R.; Koetter, R.; Blahut, R. E. Implementation of a Hermitian decoder IC in 0.35 $\mu$m CMOS, Custom Integrated Circuits, 2001, IEEE Conference on. (2001), pp. 297-300 | DOI

[2] Assmus, E.F.; Key, J.D. Polynomial codes and finite geometries, Handbook of coding theory (Pless, V.S.; Huffman, W.C.; Brualdi, R.A., eds.), Volume II, North-Holland, 1998

[3] Berlekamp, Elwyn R. Algebraic coding theory, McGraw-Hill, 1968

[4] Berlekamp, Elwyn R.; McEliece, Robert J.; van Tilborg, Henk C. A. On the inherent intractability of certain coding problems, IEEE Transactions on Information Theory, Volume 24 (1978) no. 3, pp. 384-386

[5] Blahut, Richard E. Fast Algorithms for Digital Signal Processing, Addison-Wesley, 1985

[6] Blahut, Richard E. Algebraic Codes for Data Transmission, Cambridge University Press, 2002

[7] Bruck, J.; Naor, M. The hardness of decoding linear codes with preprocessing, IEEE Transactions on Information Theory, Volume 36 (1990) no. 2, pp. 381-385 http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=52484

[8] Cheng, Qi Hard Problems of Algebraic Geometry Codes, http://arxiv.org/abs/cs.IT/0507026, 2005 | arXiv

[9] Cheng, Qi; Wan, Daqing Complexity of Decoding Positive-Rate Reed-Solomon Codes, ICALP ’08 : Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I (Lecture Notes in Computer Science), Springer-Verlag, Berlin, Heidelberg (2008), pp. 283-293 | DOI

[10] Chien, Chien-Yu; Duursma, I. M. Geometric Reed-Solomon codes of length 64 and 65 over $F_8$, Information Theory, IEEE Transactions on, Volume 49 (2003) no. 5, pp. 1351-1353

[11] Chien, R. T. Cyclic decoding procedures for Bose-Chaudhuri-Hocquenghem codes, IEEE Transactions on Information Theory, Volume 10 (1964) no. 4, pp. 357-363 http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1053699

[12] Cox, David; Littel, John; O’Shea, Donal Ideals, Varieties and Algorithms, Springer, 1992

[13] Feng, G. L.; Rao, T. R. N. Decoding algebraic-geometric codes up to the designed minimum distance, Information Theory, IEEE Transactions on, Volume 39 (1993) no. 1, pp. 37-45 | DOI

[14] Feng, Gui-Liang; Tzeng, Kenneth K. A generalization of the Berlekamp-Massey algorithm for multisequence shift-register synthesis with applications to decoding cyclic codes, IEEE Transactions on Information Theory, Volume 37 (1991) no. 5, pp. 1274-1287

[15] Forney, G. On decoding BCH codes, Information Theory, IEEE Transactions on, Volume 11 (1965) no. 4, pp. 549-557 http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1053825

[16] Gaborit, Philippe; Zemor, Gilles Asymptotic improvement of the Gilbert-Varshamov bound for binary linear codes, Information Theory, 2006 IEEE International Symposium on (2006), pp. 287-291 | DOI

[17] Gemmell, Peter; Sudan, Madhu Highly resilient correctors for polynomials, Information Processing Letters, Volume 43 (1992) no. 4, pp. 169-174 | DOI

[18] Goppa, V. D. Codes that are associated with divisors, Problemy Pereda ci Informacii, Volume 13 (1977) no. 1, pp. 33-39

[19] Guruswami, V.; Sudan, M. On representations of algebraic-geometry codes, Information Theory, IEEE Transactions on, Volume 47 (2001) no. 4, pp. 1610-1613 | DOI

[20] Guruswami, V.; Vardy, A. Maximum-likelihood decoding of Reed-Solomon codes is NP-hard, Information Theory, IEEE Transactions on, Volume 51 (2005) no. 7, pp. 2249-2256 http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1459041

[21] Guruswami, Venkatesan Algorithmic results in list decoding, Now Publishers Inc, 2007

[22] Guruswami, Venkatesan List Decoding of Binary Codes - A Brief Survey of Some Recent Results, Coding and Cryptology (Chee, Yeow M.; Li, Chao; Ling, San; Wang, Huaxiong; Xing, Chaoping, eds.) (Lecture Notes in Computer Science), Volume 5557, Springer Berlin Heidelberg, Berlin, Heidelberg (2009), pp. 97-106 | DOI

[23] Guruswami, Venkatesan; Patthak, Anindya C. Correlated algebraic-geometric codes : Improved list decoding over bounded alphabets, Mathematics of computation (2007)

[24] Guruswami, Venkatesan; Rudra, Atri Explicit capacity-achieving list-decodable codes, STOC ’06 : Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, ACM, New York, NY, USA (2006), pp. 1-10 | DOI

[25] Guruswami, Venkatesen; Sudan, Madhu Extensions to the Johnson bound, http://theory.lcs.mit.edu/Emadhu/papers/johnson.ps, 2001 http://theory.lcs.mit.edu/Emadhu/papers/johnson.ps

[26] Hamming, R. W. Error detecting and error correcting codes (1950) no. 2 (Technical report)

[27] Høholdt, Tom; Pellikaan, Ruud On the decoding of algebraic-geometric codes, IEEE Transactions on Information Theory, Volume 41 (1995) no. 6, pp. 1589-1614

[28] Høholdt, T.; van Lint, J. H.; Pellikaan, R. Algebraic geometry codes, Handbook of Coding Theory, Volume I, Elsevier (1998), pp. 871-961

[29] Justesen, Jørn; Høholdt, Tom Bounds on list decoding of MDS codes, IEEE Transactions on Information Theory, Volume 47 (2001) no. 4, pp. 1604-1609

[30] Kotter, R. A fast parallel implementation of a Berlekamp-Massey algorithm for algebraic-geometric codes, IEEE Transactions on Information Theory, Volume 44 (1998) no. 4, pp. 1353-1368 | DOI

[31] Macwilliams, F. J.; Sloane, N. J. A. The Theory of Error-Correcting Codes, North-Holland Mathematical Library, North Holland, 1983

[32] Massey, Jim Shift-register synthesis and BCH decoding, IEEE Transactions on Information Theory, Volume 15 (1969) no. 1, pp. 122-127 http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1054260

[33] Matsui, Hajime; Sakata, Shojiro; Kurihara, Masazumi; Mita, Seiichi Systolic array architecture implementing Berlekamp-Massey-Sakata algorithm for decoding codes on a class of algebraic curves, IEEE Transactions on Information Theory, Volume 51 (2005) no. 11, pp. 3856-3871

[34] McEliece, Robert J. The Guruswami-Sudan Decoding Algorithm for Reed-Solomon Codes (2003) no. 42-153 http://www.ee.caltech.edu/EE/Faculty/rjm/papers/RSD-JPL.pdf (Technical report)

[35] Saints, K.; Heegard, C. Algebraic-geometric codes and multidimensional cyclic codes : a unified theory and algorithms for decoding using Grobner bases, Information Theory, IEEE Transactions on, Volume 41 (1995) no. 6, pp. 1733-1751 | DOI

[36] Sakata, S.; Justesen, J.; Madelung, Y.; Jensen, H. E.; Hoholdt, T. Fast decoding of algebraic-geometric codes up to the designed minimum distance, Information Theory, IEEE Transactions on, Volume 41 (1995) no. 6, pp. 1672-1677 | DOI

[37] Sakata, Shojiro Finding a Minimal Set of Linear Recurring Relations Capable of Generating a Given Finite Two-Dimensional Array, J. Symb. Comput., Volume 5 (1988) no. 3, pp. 321-337

[38] Sakata, Shojiro N-Dimensional Berlekamp-Massey Algorithm for Multiple Arrays and Construction of Multivariate Polynomials with Preassigned Zeros, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes 6th International Conference, AAECC-6 Rome (Mora, Teo, ed.) (Lecture Notes in Computer Science), Volume 357 (1988), pp. 356-376 http://www.springerlink.de/content/f0x1555h6j45434g/?p=d4bb0721df29430fa6e821864bf56c74&pi=29

[39] Sakata, Shojiro Finding a minimal polynomial vector set of a vector of nD arrays, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Mattson, H. F.; Mora, T.; Rao, T. R. N., eds.) (Lecture Notes in Computer Science), Springer-Verlag (1991) no. 539, pp. 414-425 http://www.springerlink.de/content/pg410014070155k3/?p=a12e1b268dae4dbe9e3c9d4400e8f0cf&pi=38

[40] Sasson, Eli B.; Kopparty, Swastik; Radhakrishnan, Jaikumar Subspace Polynomials and List Decoding of Reed-Solomon Codes, FOCS ’06 : Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, USA (2006), pp. 207-216 | DOI

[41] Schwartz, J. T. Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM, Volume 27 (1980) no. 4, pp. 701-717 | DOI

[42] Shannon, Claude E. A mathematical theory of Communication, The Bell system technical journal, Volume 27 (1948), pp. 379-423

[43] Shokrollahi, Mohammad A.; Wasserman, Hal Decoding algebraic geometric codes, Proceedings of the IEEE Information Theory Workshop, 1998 (1998), pp. 40-41

[44] Stichtenoth, Henning Algebraic Function Fields and Codes, Springer, 1993

[45] Sudan, Madhu Decoding of Reed-Solomon Codes beyond the Error-Correction Bound, Journal of Complexity, Volume 13 (1997) no. 1, pp. 180-193

[46] Tsfasman, Michael A.; Vlǎduţ, Serguei G.; Zink, Th. Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound, Math. Nachr., Volume 109 (1982), pp. 21-28

[47] Vardy, Alexander Algorithmic complexity in coding theory and the minimum distance problem, STOC ’97 : Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, El Paso, United States, ACM Press (1997), pp. 92-109 | DOI

[48] von zur Gathen, Joachim; Gerhard, Jürgen Modern Computer Algebra, Cambridge University Press, 1999

[49] Wahlen, B. E.; Jimenez, J. Performance comparison of Hermitian and Reed-Solomon codes, MILCOM 97 Proceedings, Volume 1 (1997), p. 15-19 vol.1 http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=648657

[50] Welch, Loyd R.; Berlekamp, Elwyn R. Error correction for algebraic block codes, US Patent 4 633 470, 1986

[51] Wu, Y. New List Decoding Algorithms for Reed-Solomon and BCH Codes, Information Theory, IEEE Transactions on, Volume 54 (2008) no. 8, pp. 3611-3630 | DOI

[52] Zippel, Richard Probabilistic algorithms for sparse polynomials, Symbolic and Algebraic Computation : EUROSAM ’79 (Ng, Edward W., ed.) (Lecture Notes in Computer Science), Volume 72, Springer (1979), pp. 216-226