Salagean-bidir-lin-rec20090615.pdf (217.95 kB)
Download fileAn algorithm for computing minimal bidirectional linear recurrence relations
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