Shift and add sequences are important because (a) they arise naturally as m-sequences (see Section 3.9.1 and Section 10) or related sequences (see Chapter 11 and Chapter 12), (b) they often have ideal autocorrelation properties (see Proposition 9.1.3), and (c) they are often (punctured) de Bruijn sequences (see Theorem 9.4.1). At one time it was thought that all shift and add sequences were m-sequences, but this has turned out to be false [13, 65, 211]. See the discussion in Section 9.2 below. In this chapter we develop a complete description of the set of all shift and add sequences. In Chapter 12 we describe a class of (algebraic) shift registers that may be used to generate “good” shift and add sequences over non-prime fields. In this chapter we also consider a “with carry” version of the shift and add property and develop a complete description of all sequences with this property.

Basic properties

Let G be a finite Abelian group and let a = (a0, a1, …) be a periodic sequence of elements from G. Let T be the minimal period of a. For any integer τ, 0 ≤ τ < T, let aτ be the τ shift of a, that is, aτ = (aτ, aτ+1, …). If b is another periodic sequence with period T, then let a+b be the sequence (a0+b0, a1+b1, …).