In this talk we consider various algorithms for decoding BCH/RS/Goppa codes, in particular the euclidean algorithm, the Berlekamp-Massey algorithm and the Welch-Berlekamp algorithm. We focus on relationships of these algorithms with interpolation methods in system theory. We note that the problem statements in the two areas can be different: from a system theoretic point of view rational interpolating functions with common factors between numerator and denominator are undesirable whereas common factors can be required in some decoding problems. We investigate these different perspectives, incorporating the recently developed algorithm by Blackburn (1997) which makes a strong link with system theory by extending the Welch-Berlekamp algorithm to a multiple-point rational interpolation algorithm.

References:

S.R. Blackburn,"A generalized rational interpolation problem and the solution of the WB algorithm" in Designs, Codes and Cryptography, 11, pp. 223-234 (1997).

M. Kuijper, "Further results on the use of a generalized B-M algorithm for BCH decoding beyond the designed error-correcting capability", to appear in Proceedings of the 13th AAECC Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, Hawaii, USA, November 1999.

M. Kuijper, "Partial realization and the euclidean algorithm", IEEE Trans. Aut. Control, 44, No. 5, pp. 1013-1016 (1999).

M. Kuijper, "The Berlekamp-Massey algorithm, error-correction, keystreams and modeling", in Dynamical Systems, Control, Coding, Computer Vision: New trends, Interfaces, and Interplay, G. Picci, D. S. Gilliam eds., Birkhauser's series ``Progress in Systems and Control Theory'', pp. 301-320 (1999).

M. Kuijper, "An algorithm for constructing a minimal partial realization in the multivariable case", Systems & Control Letters, 31, pp. 225-233 (1997).

M. Kuijper and J.C. Willems, "On constructing a shortest linear recurrence relation", IEEE Trans. Aut. Control, 42, pp. 1554-1558 (1997).

Material used during the talk