Generation of binary sequences with controllable complexity

Complexity of a binary sequence is measured by the amount of the sequence required to define the remainder. It is shown that, while maximum length(L = 2^r - 1)sequences fromr-stage linear logic feedback generators have minimum complexity, it is a simple matter to use such sequences as bases for deriving other more complex sequences of the same length. The complexity is controllable up to maximum complexity, which means that no fractional part of a sequence will define the remainder. It is demonstrated that, from the2^L /Lcyclically distinct sequences of lengthL, most of which are highly complex, it is possible to select a priori those with acceptable noiselike statistics. Practical schemes based on the Langford problem are given for implementing large quantities of such sequences.