Mersenne banner
no. 2
Les codes algébriques principaux et leur décodage
Les cours du CIRM, Tome 1 (2010) no. 2, pp. 31-74.
Publié le :
DOI : 10.5802/ccirm.8 
@article{CCIRM_2010__1_2_31_0,
     author = {Daniel Augot},
     title = {Les codes alg\'ebriques principaux et leur d\'ecodage},
     journal = {Les cours du CIRM},
     pages = {31--74},
     publisher = {CIRM},
     volume = {1},
     number = {2},
     year = {2010},
     doi = {10.5802/ccirm.8},
     language = {fr},
     url = {https://ccirm.centre-mersenne.org/articles/10.5802/ccirm.8/}
}
TY  - JOUR
AU  - Daniel Augot
TI  - Les codes algébriques principaux et leur décodage
JO  - Les cours du CIRM
PY  - 2010
SP  - 31
EP  - 74
VL  - 1
IS  - 2
PB  - CIRM
UR  - https://ccirm.centre-mersenne.org/articles/10.5802/ccirm.8/
DO  - 10.5802/ccirm.8
LA  - fr
ID  - CCIRM_2010__1_2_31_0
ER  - 
%0 Journal Article
%A Daniel Augot
%T Les codes algébriques principaux et leur décodage
%J Les cours du CIRM
%D 2010
%P 31-74
%V 1
%N 2
%I CIRM
%U https://ccirm.centre-mersenne.org/articles/10.5802/ccirm.8/
%R 10.5802/ccirm.8
%G fr
%F CCIRM_2010__1_2_31_0
Daniel Augot. Les codes algébriques principaux et leur décodage. Les cours du CIRM, Tome 1 (2010) no. 2, pp. 31-74. doi : 10.5802/ccirm.8. https://ccirm.centre-mersenne.org/articles/10.5802/ccirm.8/

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

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

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

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

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

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

[7] J. Bruck; M. Naor 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 | MR | Zbl

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

[9] Qi Cheng; Daqing Wan 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) (2008), pp. 283-293 | DOI | Zbl

[10] Chien-Yu Chien; I. M. Duursma 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 | DOI | Zbl

[11] R. T. Chien 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 | DOI | MR | Zbl

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

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

[14] Gui-Liang Feng; Kenneth K. Tzeng 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 | DOI | MR | Zbl

[15] G. Forney 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 | DOI | MR | Zbl

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

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

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

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

[20] V. Guruswami; A. Vardy 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 | DOI | MR | Zbl

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

[22] Venkatesan Guruswami List Decoding of Binary Codes - A Brief Survey of Some Recent Results, Coding and Cryptology (Lecture Notes in Computer Science), Volume 5557 (2009), pp. 97-106 | DOI | MR

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

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

[25] Venkatesen Guruswami; Madhu Sudan 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] R. W. Hamming Error detecting and error correcting codes (1950) no. 2 (Technical report) | Zbl

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

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

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

[30] R. Kotter 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 | MR | Zbl

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

[32] Jim Massey 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 | DOI | MR | Zbl

[33] Hajime Matsui; Shojiro Sakata; Masazumi Kurihara; Seiichi Mita 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 | DOI | MR | Zbl

[34] Robert J. McEliece 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] K. Saints; C. Heegard 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 | MR | Zbl

[36] S. Sakata; J. Justesen; Y. Madelung; H. E. Jensen; T. Hoholdt 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 | MR | Zbl

[37] Shojiro Sakata 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 | DOI | MR | Zbl

[38] Shojiro Sakata 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 (Lecture Notes in Computer Science), Volume 357 (1988), pp. 356-376 http://www.springerlink.de/content/f0x1555h6j45434g/?p=d4bb0721df29430fa6e821864bf56c74&pi=29 | DOI | Zbl

[39] Shojiro Sakata Finding a minimal polynomial vector set of a vector of nD arrays, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Lecture Notes in Computer Science) (1991) no. 539, pp. 414-425 http://www.springerlink.de/content/pg410014070155k3/?p=a12e1b268dae4dbe9e3c9d4400e8f0cf&pi=38 | DOI

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

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

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

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

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

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

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

[47] Alexander Vardy 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 (1997), pp. 92-109 | DOI | Zbl

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

[49] B. E. Wahlen; J. Jimenez 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 | DOI

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

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

[52] Richard Zippel Probabilistic algorithms for sparse polynomials, Symbolic and Algebraic Computation : EUROSAM ’79 (Lecture Notes in Computer Science), Volume 72 (1979), pp. 216-226 | DOI | MR | Zbl

Cité par Sources :