Les codes algébriques principaux et leur décodage

Daniel Augot

Les cours du CIRM (2010)

  • Volume: 1, Issue: 2, page 31-74
  • ISSN: 2108-7164

How to cite


Augot, Daniel. "Les codes algébriques principaux et leur décodage." Les cours du CIRM 1.2 (2010): 31-74. <http://eudml.org/doc/116370>.

author = {Augot, Daniel},
journal = {Les cours du CIRM},
language = {fre},
number = {2},
pages = {31-74},
publisher = {CIRM},
title = {Les codes algébriques principaux et leur décodage},
url = {http://eudml.org/doc/116370},
volume = {1},
year = {2010},

AU - Augot, Daniel
TI - Les codes algébriques principaux et leur décodage
JO - Les cours du CIRM
PY - 2010
VL - 1
IS - 2
SP - 31
EP - 74
LA - fre
UR - http://eudml.org/doc/116370
ER -


  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), 297-300 
  2. E.F. Assmus, J.D. Key, Polynomial codes and finite geometries, Handbook of coding theory II (1998), PlessV.S.V. Zbl0980.94038MR1667952
  3. Elwyn R. Berlekamp, Algebraic coding theory, (1968), McGraw-Hill Zbl0988.94521MR238597
  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 24 (1978), 384-386 Zbl0377.94018MR495180
  5. Richard E. Blahut, Fast Algorithms for Digital Signal Processing, (1985), Addison-Wesley Zbl0579.94001MR777867
  6. Richard E. Blahut, Algebraic Codes for Data Transmission, (2002), Cambridge University Press Zbl1204.94002
  7. J. Bruck, M. Naor, The hardness of decoding linear codes with preprocessing, IEEE Transactions on Information Theory 36 (1990), 381-385 Zbl0704.94022MR1052788
  8. Qi Cheng, Hard Problems of Algebraic Geometry Codes, (2005) Zbl1308.94113
  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 (2008), 283-293, Springer-Verlag, Berlin, Heidelberg Zbl1153.94468MR2500279
  10. Chien-Yu Chien, I. M. Duursma, Geometric Reed-Solomon codes of length 64 and 65 over F 8 , Information Theory, IEEE Transactions on 49 (2003), 1351-1353 Zbl1063.94107MR1984834
  11. R. T. Chien, Cyclic decoding procedures for Bose-Chaudhuri-Hocquenghem codes, IEEE Transactions on Information Theory 10 (1964), 357-363 Zbl0125.09503
  12. David Cox, John Littel, Donal O’Shea, Ideals, Varieties and Algorithms, (1992), Springer MR1189133
  13. G. L. Feng, T. R. N. Rao, Decoding algebraic-geometric codes up to the designed minimum distance, Information Theory, IEEE Transactions on 39 (1993), 37-45 Zbl0765.94021MR1211489
  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 37 (1991), 1274-1287 Zbl0734.94008MR1136665
  15. G. Forney, On decoding BCH codes, Information Theory, IEEE Transactions on 11 (1965), 549-557 Zbl0143.41401MR189923
  16. Philippe Gaborit, Gilles Zemor, Asymptotic improvement of the Gilbert-Varshamov bound for binary linear codes, Information Theory, 2006 IEEE International Symposium on (2006), 287-291 Zbl1318.94120
  17. Peter Gemmell, Madhu Sudan, Highly resilient correctors for polynomials, Information Processing Letters 43 (1992), 169-174 Zbl0767.68075MR1187182
  18. V. D. Goppa, Codes that are associated with divisors, Problemy Pereda ci Informacii 13 (1977), 33-39 Zbl0415.94005MR497293
  19. V. Guruswami, M. Sudan, On representations of algebraic-geometry codes, Information Theory, IEEE Transactions on 47 (2001), 1610-1613 Zbl1002.94041MR1830110
  20. V. Guruswami, A. Vardy, Maximum-likelihood decoding of Reed-Solomon codes is NP-hard, Information Theory, IEEE Transactions on 51 (2005), 2249-2256 Zbl1310.94210MR2246360
  21. Venkatesan Guruswami, Algorithmic results in list decoding, (2007), Now Publishers Inc Zbl1203.94139MR2453147
  22. Venkatesan Guruswami, List Decoding of Binary Codes - A Brief Survey of Some Recent Results, Coding and Cryptology 5557 (2009), 97-106, Springer Berlin Heidelberg, Berlin, Heidelberg Zbl1248.94123
  23. Venkatesan Guruswami, Anindya C. Patthak, Correlated algebraic-geometric codes : Improved list decoding over bounded alphabets, Mathematics of computation (2007) Zbl1150.94013MR2353961
  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), 1-10, ACM, New York, NY, USA Zbl1301.94157MR2277125
  25. Venkatesen Guruswami, Madhu Sudan, Extensions to the Johnson bound, (2001) 
  26. R. W. Hamming, Error detecting and error correcting codes, (1950) MR35935
  27. Tom Høholdt, Ruud Pellikaan, On the decoding of algebraic-geometric codes, IEEE Transactions on Information Theory 41 (1995), 1589-1614 Zbl0847.94012MR1391018
  28. T. Høholdt, J. H. van Lint, R. Pellikaan, Handbook of Coding Theory, I (1998), 871-961, Elsevier Zbl0922.94015
  29. Jørn Justesen, Tom Høholdt, Bounds on list decoding of MDS codes, IEEE Transactions on Information Theory 47 (2001), 1604-1609 Zbl0997.94030MR1830109
  30. R. Kotter, A fast parallel implementation of a Berlekamp-Massey algorithm for algebraic-geometric codes, IEEE Transactions on Information Theory 44 (1998), 1353-1368 Zbl0994.94037MR1665770
  31. F. J. Macwilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes, (1983), North Holland Zbl0657.94010
  32. Jim Massey, Shift-register synthesis and BCH decoding, IEEE Transactions on Information Theory 15 (1969), 122-127 Zbl0167.18101MR242556
  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 51 (2005), 3856-3871 Zbl1317.94158MR2239003
  34. Robert J. McEliece, The Guruswami-Sudan Decoding Algorithm for Reed-Solomon Codes, (2003) 
  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 41 (1995), 1733-1751 Zbl0861.94031MR1391032
  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 41 (1995), 1672-1677 Zbl0847.94013MR1391026
  37. Shojiro Sakata, Finding a Minimal Set of Linear Recurring Relations Capable of Generating a Given Finite Two-Dimensional Array, J. Symb. Comput. 5 (1988), 321-337 Zbl0647.68044MR946587
  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 357 (1988), 356-376, MoraTeoT. Zbl0675.13012MR1008512
  39. Shojiro Sakata, Finding a minimal polynomial vector set of a vector of nD arrays, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (1991), 414-425, Springer-Verlag Zbl0782.94007MR1229338
  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), 207-216, IEEE Computer Society, Washington, DC, USA 
  41. J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM 27 (1980), 701-717 Zbl0452.68050MR594695
  42. Claude E. Shannon, A mathematical theory of Communication, The Bell system technical journal 27 (1948), 379-423 Zbl1154.94303MR26286
  43. Mohammad A. Shokrollahi, Hal Wasserman, Decoding algebraic geometric codes, Proceedings of the IEEE Information Theory Workshop, 1998 (1998), 40-41 Zbl1027.68605
  44. Henning Stichtenoth, Algebraic Function Fields and Codes, (1993), Springer Zbl0816.14011MR1251961
  45. Madhu Sudan, Decoding of Reed-Solomon Codes beyond the Error-Correction Bound, Journal of Complexity 13 (1997), 180-193 Zbl0872.68026MR1449766
  46. Michael A. Tsfasman, Serguei G. Vlǎduţ, Th. Zink, Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound, Math. Nachr. 109 (1982), 21-28 Zbl0574.94013MR705893
  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), 92-109, ACM Press Zbl0962.68060MR1715628
  48. Joachim von zur Gathen, Jürgen Gerhard, Modern Computer Algebra, (1999), Cambridge University Press Zbl0936.11069MR1689167
  49. B. E. Wahlen, J. Jimenez, Performance comparison of Hermitian and Reed-Solomon codes, MILCOM 97 Proceedings 1 (1997), 15-19 vol.1 
  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 54 (2008), 3611-3630 Zbl1329.94103MR2451017
  52. Richard Zippel, Probabilistic algorithms for sparse polynomials, Symbolic and Algebraic Computation : EUROSAM ’79 72 (1979), 216-226, Springer Zbl0418.68040MR575692

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.