Centre de diffusion de revues académiques mathématiques

 
 
 
 

Les cours du CIRM

Table des matières de ce fascicule | Article précédent | Article suivant
Daniel Augot
Les codes algébriques principaux et leur décodage
Les cours du CIRM, 1 no. 2: Journées Nationales de Calcul Formel (2010), p. 31-74, doi: 10.5802/ccirm.8
Article PDF

Bibliographie

[1] J. B. Ashbrook, N. R. Shanbhag, R. Koetter & R. E. Blahut, Implementation of a Hermitian decoder IC in 0.35 $\mu $m CMOS, in Custom Integrated Circuits, 2001, IEEE Conference on., 2001, p. 297-300 Article
[2] E.F. Assmus & J.D. Key, Polynomial codes and finite geometries, in V.S. Pless, W.C. Huffman, R.A. Brualdi, éd., Handbook of coding theory, North-Holland, 1998  MR 1667952 |  Zbl 0980.94038
[3] Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill, 1968  MR 238597 |  Zbl 0988.94521
[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) no. 3, p. 384-386  MR 495180 |  Zbl 0377.94018
[5] Richard E. Blahut, Fast Algorithms for Digital Signal Processing, Addison-Wesley, 1985  MR 777867 |  Zbl 0579.94001
[6] Richard E. Blahut, Algebraic Codes for Data Transmission, Cambridge University Press, 2002
[7] J. Bruck & M. Naor, “The hardness of decoding linear codes with preprocessing”, IEEE Transactions on Information Theory 36 (1990) no. 2, p. 381-385  MR 1052788 |  Zbl 0704.94022
[8] Qi Cheng, “Hard Problems of Algebraic Geometry Codes”, http://arxiv.org/abs/cs.IT/0507026, Jul 2005
[9] Qi Cheng & Daqing Wan, Complexity of Decoding Positive-Rate Reed-Solomon Codes, in ICALP ’08 : Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, Lecture Notes in Computer Science, Springer-Verlag, 2008, p. 283-293 Article |  MR 2500279 |  Zbl 1153.94468
[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) no. 5, p. 1351-1353  MR 1984834 |  Zbl 1063.94107
[11] R. T. Chien, “Cyclic decoding procedures for Bose-Chaudhuri-Hocquenghem codes”, IEEE Transactions on Information Theory 10 (1964) no. 4, p. 357-363  Zbl 0125.09503
[12] David Cox, John Littel & Donal O’Shea, Ideals, Varieties and Algorithms, Springer, 1992  MR 1189133
[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) no. 1, p. 37-45 Article |  MR 1211489 |  Zbl 0765.94021
[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) no. 5, p. 1274-1287  MR 1136665 |  Zbl 0734.94008
[15] G. Forney, “On decoding BCH codes”, Information Theory, IEEE Transactions on 11 (1965) no. 4, p. 549-557  MR 189923 |  Zbl 0143.41401
[16] Philippe Gaborit & Gilles Zemor, Asymptotic improvement of the Gilbert-Varshamov bound for binary linear codes, in Information Theory, 2006 IEEE International Symposium on, 2006, p. 287-291 Article
[17] Peter Gemmell & Madhu Sudan, “Highly resilient correctors for polynomials”, Information Processing Letters 43 (1992) no. 4, p. 169-174 Article |  MR 1187182 |  Zbl 0767.68075
[18] V. D. Goppa, “Codes that are associated with divisors”, Problemy Pereda ci Informacii 13 (1977) no. 1, p. 33-39  MR 497293 |  Zbl 0415.94005
[19] V. Guruswami & M. Sudan, “On representations of algebraic-geometry codes”, Information Theory, IEEE Transactions on 47 (2001) no. 4, p. 1610-1613 Article |  MR 1830110 |  Zbl 1002.94041
[20] V. Guruswami & A. Vardy, “Maximum-likelihood decoding of Reed-Solomon codes is NP-hard”, Information Theory, IEEE Transactions on 51 (2005) no. 7, p. 2249-2256  MR 2246360
[21] Venkatesan Guruswami, Algorithmic results in list decoding, Now Publishers Inc, 2007  MR 2453147 |  Zbl pre05131516
[22] Venkatesan Guruswami, List Decoding of Binary Codes - A Brief Survey of Some Recent Results, in Yeow M. Chee, Chao Li, San Ling, Huaxiong Wang, Chaoping Xing, éd., Coding and Cryptology, Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2009, p. 97-106 Article |  Zbl pre05585541
[23] Venkatesan Guruswami & Anindya C. Patthak, “Correlated algebraic-geometric codes : Improved list decoding over bounded alphabets”, Mathematics of computation (2007)  MR 2353961 |  Zbl 1150.94013
[24] Venkatesan Guruswami & Atri Rudra, Explicit capacity-achieving list-decodable codes, in STOC ’06 : Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, ACM, 2006, p. 1-10 Article |  MR 2277125
[25] Venkatesen Guruswami & Madhu Sudan, “Extensions to the Johnson bound”, http://theory.lcs.mit.edu/Emadhu/papers/johnson.ps 2001
[26] R. W. Hamming, Error detecting and error correcting codes, Technical report 2, Bell System, 1950  MR 35935
[27] Tom Høholdt & Ruud Pellikaan, “On the decoding of algebraic-geometric codes”, IEEE Transactions on Information Theory 41 (1995) no. 6, p. 1589-1614  MR 1391018 |  Zbl 0847.94012
[28] T. Høholdt, J. H. van Lint & R. Pellikaan, Handbook of Coding Theory, Elsevier, 1998, p. 871-961  Zbl 0922.94015
[29] Jørn Justesen & Tom Høholdt, “Bounds on list decoding of MDS codes”, IEEE Transactions on Information Theory 47 (2001) no. 4, p. 1604-1609  MR 1830109 |  Zbl 0997.94030
[30] R. Kotter, “A fast parallel implementation of a Berlekamp-Massey algorithm for algebraic-geometric codes”, IEEE Transactions on Information Theory 44 (1998) no. 4, p. 1353-1368 Article |  MR 1665770 |  Zbl 0994.94037
[31] F. J. Macwilliams & N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, North Holland, 1983  Zbl 0657.94010
[32] Jim Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15 (1969) no. 1, p. 122-127  MR 242556 |  Zbl 0167.18101
[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) no. 11, p. 3856-3871  MR 2239003
[34] Robert J. McEliece, The Guruswami-Sudan Decoding Algorithm for Reed-Solomon Codes, Technical report 42-153, JPL Interplanetary Network Progress Report, 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) no. 6, p. 1733-1751 Article |  MR 1391032 |  Zbl 0861.94031
[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) no. 6, p. 1672-1677 Article |  MR 1391026 |  Zbl 0847.94013
[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) no. 3, p. 321-337  MR 946587 |  Zbl 0647.68044
[38] Shojiro Sakata, N-Dimensional Berlekamp-Massey Algorithm for Multiple Arrays and Construction of Multivariate Polynomials with Preassigned Zeros, in Teo Mora, éd., Applied Algebra, Algebraic Algorithms and Error-Correcting Codes 6th International Conference, AAECC-6 Rome, Lecture Notes in Computer Science, 1988, p. 356-376  MR 1008512 |  Zbl 0675.13012
[39] Shojiro Sakata, Finding a minimal polynomial vector set of a vector of nD arrays, in H. F. Mattson, T. Mora, T. R. N. Rao, éd., Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Lecture Notes in Computer Science, Springer-Verlag, 1991, p. 414-425  MR 1229338 |  Zbl 0782.94007
[40] Eli B. Sasson, Swastik Kopparty & Jaikumar Radhakrishnan, Subspace Polynomials and List Decoding of Reed-Solomon Codes, in FOCS ’06 : Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 2006, p. 207-216 Article
[41] J. T. Schwartz, “Fast Probabilistic Algorithms for Verification of Polynomial Identities”, Journal of the ACM 27 (1980) no. 4, p. 701-717 Article |  MR 594695 |  Zbl 0452.68050
[42] Claude E. Shannon, “A mathematical theory of Communication”, The Bell system technical journal 27 (1948), p. 379-423  MR 26286 |  Zbl 1154.94303
[43] Mohammad A. Shokrollahi & Hal Wasserman, Decoding algebraic geometric codes, in Proceedings of the IEEE Information Theory Workshop, 1998, 1998, p. 40-41
[44] Henning Stichtenoth, Algebraic Function Fields and Codes, Springer, 1993  MR 1251961 |  Zbl 0816.14011
[45] Madhu Sudan, “Decoding of Reed-Solomon Codes beyond the Error-Correction Bound”, Journal of Complexity 13 (1997) no. 1, p. 180-193  MR 1449766 |  Zbl 0872.68026
[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), p. 21-28  MR 705893 |  Zbl 0574.94013
[47] Alexander Vardy, Algorithmic complexity in coding theory and the minimum distance problem, in STOC ’97 : Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, El Paso, United States, ACM Press, 1997, p. 92-109 Article |  MR 1715628 |  Zbl 0962.68060
[48] Joachim von zur Gathen & Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, 1999  MR 1689167 |  Zbl 0936.11069
[49] B. E. Wahlen & J. Jimenez, Performance comparison of Hermitian and Reed-Solomon codes, in MILCOM 97 Proceedings, 1997, p. 15-19 vol.1
[50] Loyd R. Welch & Elwyn R. Berlekamp, “Error correction for algebraic block codes”, US Patent 4 633 470, December 1986
[51] Y. Wu, “New List Decoding Algorithms for Reed-Solomon and BCH Codes”, Information Theory, IEEE Transactions on 54 (2008) no. 8, p. 3611-3630 Article |  MR 2451017
[52] Richard Zippel, Probabilistic algorithms for sparse polynomials, in Edward W. Ng, éd., Symbolic and Algebraic Computation : EUROSAM ’79, Lecture Notes in Computer Science, Springer, 1979, p. 216-226  MR 575692 |  Zbl 0418.68040
Copyright Cellule MathDoc 2017 | Crédit | Plan du site