Salagean-bidir-lin-rec20090615.pdf (217.95 kB)
Download file

An algorithm for computing minimal bidirectional linear recurrence relations

Download (217.95 kB)
journal contribution
posted on 28.05.2014, 11:15 authored by Ana SalageanAna Salagean
We consider the problem of computing a linear recurrence relation (or equivalently a linear feedback shift register) of minimum order for a finite sequence over a field, with the additional requirement that not only the highest but also the lowest coefficient of the recurrence is nonzero. Such a recurrence relation can then be used to generate the sequence in both directions (increasing or decreasing order of indices), so we call it bidirectional. If the field is finite, a sequence is periodic if and only if it admits a bidirectional linear recurrence relation. For solving the above problem we propose an algorithm similar to the Berlekamp-Massey algorithm and prove its correctness. We describe the set of all solutions to this problem and show that if a sequence admits more than one linear recurrence relation then it admits a bidirectional one. We also prove some properties regarding the bidirectionality of the recurrences of the prefixes of the sequence.

History

School

  • Science

Department

  • Computer Science

Citation

SALAGEAN, A.M., 2009. An algorithm for computing minimal bidirectional linear recurrence relations. IEEE Transactions on Information Theory, 55 (10), pp.4695-4700.

Publisher

© IEEE

Version

AM (Accepted Manuscript)

Publication date

2009

Notes

© 2009 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. A preliminary version of this work was presented at the IEEE International Symposium on Information Theory 2008, Toronto, Canada.

ISSN

0018-9448

Language

en