Shift registers are at the heart of cryptography and error-correction. In cryptography they are the main tool for
generating long pseudorandom binary sequences which can be used as keys for two communicating parties in symmetric
cryptography. Practically all military cryptography makes use of them. Shift registers are also fundamental in signal
analysis and frequency hopping, most recently in connection with European GPS codes.
The subject has a chequered history. One of the pioneers was a famous Hollywood star who, in her day, was known as the
worlds most beautiful woman and wrote one of the earliest patents on frequency hopping which was developed by the US
military. We speak of the Austrian-born Hedwig Maria Eva Kiesler, otherwise known as Hedy Lamarr. The development
of spread spectrum technology was first proposed by Lamarr using frequency hopping. She obtained a patent after coming
to Hollywood in 1942 and turned it over to the US government as a contribution to the war effort. Shortly after the patent
expired in 1959 Sylvania digitize the synchronization to supply secure communication during the Cuban missile crisis.
This paper presents a user-friendly, self-contained and comprehensive discussion of the theory of shift registers.
Moreover, we provide several examples (and counterexamples) in support of the theory. In the non-linear case we study
the relationship between truth tables and de Bruijn sequences. In the linear case, we use a matrix-theoretic approach to
describe the situations when the output is periodic and when it is not periodic. Section three describes additional
periodicity properties, using the Cayley-Hamilton theorem and the theory of error-correcting codes.
In Section six, we prove a fundamental result to the effect that, for non-singular shift registers of length k, the entire
output is uniquely determined by any 2k consecutive bits of the output sequence. Although the result is part of the folk
lore, it is certainly not well understood and there appears to be a lack of any rigorous proof in the literature. An additional
bonus of our proof here is that it can be adapted to provide a new algorithm for demonstrating a little-known, and
remarkable fact. Namely, we provide the most general method for constructing two quite different shift registers of the
same length that produce identical output sequences! A new result concerning such shift registers is also sketched in