 |
Journal of Integer Sequences, Vol. 4 (2001), Article 01.1.1 |
|
|
Journal of Integer Sequences, Vol. 4 (2001), Article 01.1.1 |
Abstract: This paper might fairly be said to fall between three stools: the presentation and justification of a number of related computational methods associated with LFSR sequences, including finding the order, recurrence and general term; the exploration of tutorial examples and survey of applications; and a rigorous treatment of one topic, the recursive construction of the number wall, which we believe has not previously appeared.
The Number Wall is the table of Toeplitz determinants associated with a sequence over an arbitrary integral domain, particularly Z, Fp, R, and their polynomial and series extensions by many variables. The relation borne by number walls to LFSR (linear recurring shift register) sequences is analogous to that borne by difference tables to polynomial sequences: They can be employed to find the order and recurrence (Section 3), or to compute further terms and express the general term explicitly (Section 10) -a lthough other more elaborate methods may be more efficient (Sections 8 and 12).
Much of the paper collects and summarizes relevant classical theory in Formal Power Series (Section 1), Linear Recurrences (Section 2), Padé Blocks (essentially) (Section 3), Vandermonde Interpolation (Section 8), and Difference Tables (Section 9). A `frame' relation between the elements of the number wall containing zeros (a non-normal C-table, in Padé terminology) is stated and proved (Section 4), with the resulting recursive generation algorithm and some special cases (Section 5); the consequences of basing the wall on this algorithm instead are explored (Section 6), and a cellular automaton is employed to optimize it in linear time (Section 7).
The connections between number walls and classical Padé tables are discussed briefly (Section 11), with other associated areas (Linear Complexity, QD Algorithm, Toda Flows, Berlekamp-Massey) reviewed even more briefly (Section 12). Among topics covered incidentally are the explicit number wall for an LFSR, in particular for a diagonal binomial coefficient (Section 8); dealing with high-degree `polynomials' over finite fields, fast computation of LFSR order over Fp, and the wall of a linear function of a given sequence (Section 9). There are numerous examples throughout, culminating in a final gruelingly extensive one (Section 13).
Keywords: Number Wall, Zero Window, Persymmetric, Toeplitz Matrix, Hankel Determinant, Linear Complexity, Finite Field, Cryptographic Security, LFSR, Extrapolation, Toda Flow, Linear Recurring Sequence, Difference Equation, Zero-Square Table, QD Method, Vandermonde, Formal Laurent Series, Padé Table.
AMS Subject Classification: 94A55, 65D05, 11C20, 65-04, 68Q15, 68Q68, 41A21.
Received January 1, 2001; revised version received September 25, 2001. Published in Journal of Integer Sequences, October 7, 2001.
Return to Journal of Integer Sequences home page