The Number-Wall Algorithm: an LFSR Cookbook
W. F. Lunnon · 2001
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 §3, or to compute further terms and express the general term explicitly §10 (although other more elaborate methods may be more efficient §12, §8). Much of the paper collects and summarizes relevant classical theory in Formal Power Series §1, Linear Recurrences §2, Padé Blocks (essentially) §3, Vandermonde Interpolation §8, and Difference Tables §9. A ‘frame ’ relation between the elements of the number wall containing zeros (a non-normal C-table, inPadé terminology) is stated and proved §4, with the resulting recursive generation algorithm and some special cases