Algebraic Shift Register Sequences

Mark Goresky and Andrew Klapper
CAMBRIDGE UNIVERSITY PRESS 2012, 514 PAGES
PRICE (HARDBACK) £60.00 ISBN 978-1-107-01499-2

There are many situations that require sequences with a given set of properties. For example, if the sequences are being used to manage multiple, simultaneous communications within the same medium then we would like a family of sequences with low cross-correlation (so that the individual communications do not ‘bump into each other’): one application of this technique is Code Division Multiple Access (CDMA), which is widely used for mobile phones. Additionally, if the sequence is being used to protect information then we would like it to be in some sense difficult to predict.

A key property that is almost always required is that the sequence be quick and easy to generate, which is where shift registers come in. These relatively simple devices are easy to describe and implement, yet it can be deceptively difficult to demonstrate that a given arrangement has the required properties.

The stated goal of this volume is to simultaneously be a text book and a reference book. It provides a unified approach, based on algebraic methods, that can be applied to linear feedback shift registers as well as a wide range of related sequence generators. Its eighteen chapters, which include exercises, are divided into three parts: algebraically defined sequences; pseudo-random and pseudo-noise sequences; and register synthesis and security measures. Four appendixes provide the algebraic background necessary for the book (e.g. group theory, fields, Galois rings, etc).

The first part contains familiar items like the Fibonacci sequence. Different types of shift register are introduced including: linear feedback shift registers; feedback with carry shift registers; and algebraic feedback shift registers. Here, as elsewhere, the authors’ enthusiasm shines through. We are told that ‘the following lemma concerns a remarkable property’, for example, and later we learn of something that ‘is an amazing fact’.

The concluding chapter in the book’s first part contains a discussion of the implementation of shift registers in circuits. This includes situations where the shift register is better implemented in software as well as cases where it is better implemented in hardware. This concern with practical, rather than just theoretical, aspects informs and enhances much of the book’s content.

The second part of the book begins with a discussion of the term ‘pseudo-random’ – the sequence needs to appear random to an outside observer but it needs to be repeatable, in the sense that it can be faithfully regenerated. The tension between these two requirements (and others that are associated with particular applications) is described well. A range of sequence types are covered in this part of the book, including shift and add sequences, as well as m-sequences. The properties of such sequences are also discussed.

In essence, the third part of the book is concerned with the inverse problem, which tries to produce a generator from only part of a sequence. Predictability, or the lack of it, is obviously an important characteristic here.

The authors take care to balance the detailed mathematics that makes up much of the text with the occasional lighter moment. It is noted, for example, that Hedy Lamarr, the famous actress, is the co-owner of a 1942 patent on frequency hopping for the remote guidance of torpedoes. They also discuss how the properties of m-sequences are exploited in a mind-reading magic trick.

For some readers the book’s exclusive focus on shift registers will be a positive factor. I, however, was somewhat disappointed that other types of pseudo-random sequence generators, like the Mersenne Twister, were not given at least a passing mention. The end of the book was also a slight let down, as it comes to an abrupt halt at the end of the last chapter. The inclusion of a brief summary would probably have been helpful.

These, however, are small points that do not significantly detract from the whole. Shift registers are yet another example of the way that mathematics underpins our modern lifestyle and this book provides everything a reader needs to become familiar with them, their properties and their applications. As such, it comes well recommended.