Computational & Technology Resources
an online resource for computational,
engineering & technology publications 

CivilComp Proceedings
ISSN 17593433 CCP: 84
PROCEEDINGS OF THE FIFTH INTERNATIONAL CONFERENCE ON ENGINEERING COMPUTATIONAL TECHNOLOGY Edited by: B.H.V. Topping, G. Montero and R. Montenegro
Paper 39
On the Interleaved Sequences Generated by Cellular Automata A. Peinado
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", CivilComp Press, Stirlingshire, UK, Paper 39, 2006. doi:10.4203/ccp.84.39
Keywords: pseudorandom generator, cellular automata, cryptography.
Summary
Pseudorandom sequence generators are widely used in communications and
cryptography [6]. The simplest devices employed to implement such generators are
the linear feedback shift registers (LFSR). These devices consist of n flipflops,
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 flipflop contributing to the linear feedback. The maximal length of these sequences is 2^{n}1 and it is obtained when the feedback polynomial is primitive. Furthermore, maximal length sequences (msequences) present an excellent statistical distribution satisfying the Golomb postulates [2]. The main disadvantage is that they are easily predictable, i.e., from 2^{n} known consecutive bits the entire (2^{n}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 [1]. 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) nonlinear combination of these devices, and (ii) nonlinear filtering on the output sequence produced by a single device. These two techniques have determined many configurations [6]. 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 [3] 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 [7] As a consequence of this study, a procedure to obtain the configurations producing maximal sequence length with high linear complexity is established. References
purchase the fulltext of this paper (price £20)
go to the previous paper 
