FAST RATIONAL INTERPOLATION, REED-SOLOMON DECODING, AND THE LINEAR COMPLEXITY PROFILES OF SEQUENCES

Authors
BLACKBURN SR
Citation
Sr. Blackburn, FAST RATIONAL INTERPOLATION, REED-SOLOMON DECODING, AND THE LINEAR COMPLEXITY PROFILES OF SEQUENCES, IEEE transactions on information theory, 43(2), 1997, pp. 537-548
Citations number
27
Categorie Soggetti
Information Science & Library Science","Engineering, Eletrical & Electronic
Journal title
IEEE transactions on information theory → ACNP
ISSN journal
00189448
Volume
43
Issue
2
Year of publication
1997
Pages
537 - 548
Database
ISI
SICI code
0018-9448(1997)43:2<537:FRIRDA>2.0.ZU;2-P
Abstract
An asymptotically fast algorithm for solving the generalized rational interpolation problem is presented, This problem has been studied as p art of system theory and is related to the solution of the classical a nd Welch-Berlekamp key equations which arise in Reed-Solomon decoding, The algorithm can also be used to compute the linear complexity profi le of a binary sequence of length m using only O(m(log m)(2) log log m ) bit operations.