zbMATH — the first resource for mathematics

Interpolation in list decoding of Reed-Solomon codes. (English. Russian original) Zbl 1136.94323
Probl. Inf. Transm. 43, No. 3, 190-198 (2007); translation from Probl. Peredachi Inf. 43, No. 3, 28-38 (2007).
Summary: We consider the problem of efficient implementation of two-dimensional interpolation in the Guruswami-Sudan list decoding algorithm for Reed-Solomon codes. We show that it can be implemented by computing the product of ideals of interpolation polynomials constructed for subsets of interpolation points. A method for fast multiplication of coprime zero-dimensional ideals is proposed.
94A60 Cryptography
94B60 Other types of codes
PDF BibTeX Cite
Full Text: DOI
[1] Elias, P., List Decoding for Noisy Channels, Tech. Report of the Research Laboratory of Electronics, MIT, 1957, no. 335.
[2] Guruswami, V. and Sudan, M., Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes, IEEE Trans. Inform. Theory, 1999, vol. 45, no. 6, pp. 1757–1767. · Zbl 0958.94036
[3] Koetter, R. and Vardy, A., Algebraic Soft-Decision Decoding of Reed-Solomon Codes, IEEE Trans. Inform. Theory, 2003, vol. 49, no. 11, pp. 2809–2825. · Zbl 1301.94159
[4] Nielsen, R.R. and Hoholdt, T., Decoding Reed-Solomon Codes Beyond Half the Minimum Distance, in Coding Theory, Crytography and Related Areas (Proc. ICCC’98, Guanajuato, Mexico), Berlin: Springer, 1999, pp. 221–236. · Zbl 1017.94530
[5] Ma, J., Trifonov, P., and Vardy, A., Divide-and-Conquer Interpolation for List Decoding of Reed-Solomon Codes, in Proc. 2004 IEEE Int. Sympos. on Information Theory, Chicago, USA, p. 387.
[6] Koetter, R., Ma, J., Vardy, A., and Ahmed, A., Efficient Interpolation and Factorization in Algebraic Soft-Decision Decoding of Reed-Solomon Codes, in Proc. 2003 IEEE Int. Sympos. on Information Theory, Yokohama, Japan, p. 365.
[7] Roth, R. and Ruckenstein, G., Efficient Decoding of Reed-Solomon Codes Beyond Half the Minimum Distance, IEEE Trans. Inform. Theory, 2000, vol. 46, no. 1, pp. 246–257. · Zbl 1001.94046
[8] Cox, D., Little, G., and O’shea, D., Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, New York: Springer, 1997, 2nd ed. Translated under the title Idealy, mnogoobraziya i algoritmy, Moscow: Mir, 2000.
[9] Kailath, T., Linear Systems, Englewood Cliffs: Prentice-Hall, 1980. · Zbl 0454.93001
[10] Becker, T. and Weispfenning, V., Gröbner Bases: A Computational Approach to Commutative Algebra, New York: Springer, 1993. · Zbl 0772.13010
[11] Sauer, T., Polynomial Interpolation of Minimal Degree and Gröbner Bases, Gröbner Bases and Applications, Buchberger, B. and Winkler, F., Eds., London Math. Soc. Lecture Note Ser., vol. 251, Cambridge: Cambridge Univ. Press, 1998, pp. 483–494. · Zbl 0898.41001
[12] Marinari, M.G., Moller, H.M., and Mora, T., Gröbner Bases of Ideals Defined by Functionals with an Application to Ideals of Projective Points, Appl. Algebra Engrg. Comm. Comput., 1993, vol. 4, no. 2, pp. 103–145. · Zbl 0785.13009
[13] Blahut, R.E., Fast Algorithms for Digital Signal Processing, Reading: Addison-Wesley, 1985. Translated under the title Bystrye algoritmy tsifrovoi obrabotki signalov, Moscow: Mir, 1989.
[14] Blahut, R.E., Theory and Practice of Error Control Codes, Reading: Addison-Wesley, 1983. Translated under the title Teoriya i praktika kodov, kontroliruyushchikh oshibki, Moscow: Mir, 1986.
[15] Faugere, J.-C., Gianni, P., Lazard, D., and Mora, T., Efficient Computation of Zero-Dimensional Gröbner Bases by Change of Ordering, J. Symbolic Comput., 1993, vol. 16, no. 4, pp. 329–344. · Zbl 0805.13007
[16] Basiri, A. and Faugere, J.-C., Changing the Ordering of Gröbner Bases with LLL: Case of Two Variables, in Proc. Int. Sympos. on Symbolic and Algebraic Computation, Philadelphia, USA 2003, pp. 23–29. · Zbl 1072.68645
[17] Alekhnovich, M., Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes, IEEE Trans. Inform. Theory, 2005, vol. 51, no. 7, pp. 2257–2265. · Zbl 1282.94101
[18] Trifonov, P., On the Interpolation Step in the Guruswami-Sudan List Decoding Algorithm for Reed-Solomon Codes, in Proc. 10th Int. Workshop on Algebraic and Combinatorial Coding Theory, Zvenigorod, Russia, 2006, pp. 269–272.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.