The fifth chapter deals with the use of hybrid cellular automata for constructing high-quality pseudo-random number generators. A hybrid cellular automaton consists of homogeneous cells and a small number of inhomogeneous cells. Inhomogeneous cells perform a local function that differs from local functions that homogeneous cells realize. The location of inhomogeneous cells and the main cell is chosen in advance. The output of the main cell is the output of a pseudo-random number generator. A hardware implementation of a pseudo-random number generator based on hybrid cellular automata is described. The local function that an inhomogeneous cell realizes is the majority function. The principles of constructing a pseudo-random number generator based on cellular automata with inhomogeneous neighborhoods are described. In such cellular automata, inhomogeneous cells have a neighborhood whose shape differs from that of neighborhoods of homogeneous cells.
TopThe Method And Models Of Pseudorandom Number Generation Based On Cellular Automata With Inhomogeneous Cells
Generators considered above have a number of the structural disadvantages. These generators require the constant additional operations, which for the additional bits of formation are intended. In addition, generators use complex switching circuit for constant connection of the generator output to the output of the active ACA cells. Both generators have a large number of connections, which reduces the reliability of operation.
To eliminate these drawbacks and of increasing of the period of repeating pseudo-random sequence in the work the pseudorandom number generator that contains cellular automata with homogeneous and inhomogeneous cells, is investigated.
The homogeneous cells are called all cellular automata cells, which the same local transition function perform. Inhomogeneous cells are called cells, which perform a different function than local transition function of the homogeneous cells. At the same time an inhomogeneous cells is much less of the homogeneous cells. Such cellular automata else are called as hybrid cellular automata (HCA).
The locations of the cells, as well as their number are an important moment for the initial settings.
Such a pseudorandom number generator consists of one cellular automata. For the operation of the generator is initially being made the advanced settings.
- 1.
The size of cellular automata is being selected.
- 2.
The number of inhomogeneous cells are being selected and their location are being created.
- 3.
The local transition function for homogeneous and inhomogeneous cells are being selected.
- 4.
The cell, whose output is the output of the generator, is being selected.
After the initial settings, a generator starts to generate a pseudo-random bit sequence at the output of the selected cells. At each time step, the homogeneous cells perform local transition function for homogeneous cells and inhomogeneous cells will perform the local transition function for inhomogeneous cells.
In this situation, all homogeneous cells will equally change its state according to the homogeneous local transition function. Only inhomogeneous cells will be changing its state by another law. Homogeneous cell of the cell neighborhood will be change its state under the influence of inhomogeneous cells that constantly makes the changes to state of the cellular automata. In this case, the inhomogeneous cells in the neighborhood of homogeneous cells change their state not as the rest the homogeneous cells of the neighborhood.
Traditional classical cellular automata without inhomogeneous cells lead to short cycles or to the installation of the cellular automata cells in the state of logical “1” or “0”. This situation is shown on Figure 15 (Chapter 2).
This example shows that important is the choice of a local transition functions for homogeneous and inhomogeneous cells. Also good effect gives an increase in the number of the inhomogeneous cells.
However, the hybrid cellular automata as a separate element with simple local transition function can not be used as pseudorandom number generator. To solve this problem allows the constant comparison of the hybrid cellular automata current state with the states obtained at the previous time steps. This approach dramatically increases the spent time on the forming each bit of the pseudo-random sequence. The work of such pseudorandom number generator can be represented by the following model.
,
(1) where