Computational & Technology Resources
an online resource for computational,
engineering & technology publications
PROCEEDINGS OF THE FIFTH INTERNATIONAL CONFERENCE ON ENGINEERING COMPUTATIONAL TECHNOLOGY
Edited by: B.H.V. Topping, G. Montero and R. Montenegro
On the Interleaved Sequences Generated by Cellular Automata
Department of Communication Engineering, University of Málaga, Spain
A. Peinado, "On the Interleaved Sequences Generated by Cellular Automata", in B.H.V. Topping, G. Montero, R. Montenegro, (Editors), "Proceedings of the Fifth International Conference on Engineering Computational Technology", Civil-Comp Press, Stirlingshire, UK, Paper 39, 2006. doi:10.4203/ccp.84.39
Keywords: pseudorandom generator, cellular automata, cryptography.
Pseudorandom sequence generators are widely used in communications and cryptography . The simplest devices employed to implement such generators are the linear feedback shift registers (LFSR). These devices consist of n flip-flops, whose contents are updated simultaneously controlled by a master clock. The content of every cell is moved to the next cell, while the content of the leftmost cell is computed by means of a linear function applied on the contents of several cells.
The period length of the sequences generated by LFSR depends on the linear feedback applied, which can be described by means of a polynomial. The coefficients of this characteristic polynomial represent the flip-flop contributing to the linear feedback. The maximal length of these sequences is 2n-1 and it is obtained when the feedback polynomial is primitive. Furthermore, maximal length sequences (m-sequences) present an excellent statistical distribution satisfying the Golomb postulates . The main disadvantage is that they are easily predictable, i.e., from 2n known consecutive bits the entire (2n-1) sequence can be reproduced.
Several proposals have been presented to improve the randomness of these sequences. In this sense, the unidimensional cellular automata (CA) is proposed by many auhors . However, the randomness of CA sequences suffers from similar problems to that of LFSR.
In order to overcome this weakness, two techniques has been traditionally applied: (i) non-linear combination of these devices, and (ii) non-linear filtering on the output sequence produced by a single device. These two techniques have determined many configurations . On the other hand, a different technique has been proposed by several authors: dynamical modifications (in execution time) of the CA/LFSR configuration [4,5]. This approach seems to be conceptually simpler, although it is equivalent to a configuration in which several maximal length generators are combined. This kind of generators are named programmable CA (or programmable LFSR). In the case of LFSR, the characteristic polynomial is modified producing longer and more robust sequences. Each configuration employed corresponds to a primitive polynomial. In the case of CA, the characteristic matrix is also modified to obtain similar results.
In any case, the properties of these sequences can be analyzed from the characteristic matrix of the CA or the LFSR. This matrix is computed taking into account the matrices of every individual configuration applied to the device.
On the other hand, Gong  proposed a model based on interleaved sequences to study most of the existing pseudorandom generators. This model allows us to obtain the period and the linear complexity of the sequences generated.
In this paper, the model propose by Gong is applied to several programmable CA. where a particular class of programmable CA is studied. This CA corresponds to the implementation of certain quadratic functions in the Galois field 
As a consequence of this study, a procedure to obtain the configurations producing maximal sequence length with high linear complexity is established.
purchase the full-text of this paper (price £20)