Linear complexity profiles and jump complexity

The linear complexity of a sequence, which is defined as the length of the shortest linear feedback shift-register (LFSR) that can generate the sequence, is a widely used sequence complexity measure in cryptographic applications. It is, however, also well-known that the linear complexity does have limitations as a complexity measure; for instance, the highly ''noncomplex'' sequence 0(n-1)1 (0(i) denotes a sequence of i zeroes) has a maximum possible linear complexity among sequences of length ii. The linear complexity profile of a sequence, which is defined as the sequence of the linear complexities of the non-empty prefixes of the sequence, can provide a better insight into sequence complexity. In this letter, the expected number of changes (''jumps'') in the linear complexity profile of a truly random binary sequence is determined and the variance is given. It is intended to introduce a new sequence complexity measure - the jump complexity - as the number of changes in the linear complexity profile of a sequence. (C) 1997 Elsevier Science B.V.