Pseudorandom Number Generators Based on Asynchronous Cellular Automata and Cellular Automata With Inhomogeneous Cells

Pseudorandom Number Generators Based on Asynchronous Cellular Automata and Cellular Automata With Inhomogeneous Cells

DOI: 10.4018/978-1-5225-2773-2.ch006


The sixth chapter deals with the construction of pseudo-random number generators based on a combination of two cellular automata, which were considered in the previous chapters. The generator is constructed based on two cellular automata. The first cellular automaton controls the location of the active cell on the second cellular automaton, which realizes the local state function for each cell. The active cell on the second cellular automaton is the main cell and from its output bits of the bit sequence are formed at the output of the generator. As the first cellular automaton, an asynchronous cellular automaton is used in this chapter, and a synchronous cellular automaton is used as the second cellular automaton. In this case, the active cell of the second cellular automaton realizes another local function at each time step and is inhomogeneous. The algorithm for the work of a cell of a combined cellular automaton for implementing a generator and its hardware implementation are presented.
Chapter Preview

Models And Algorithms Of Pseudorandom Number Generator Operation

We have considered the possibility of building a pseudorandom number generator based on a cellular automata. In fact, this cellular automata is a key element of the pseudorandom number generator and also determines its behavior. The changes its state is carried out by the internal organization of the cellular automata. However, the interaction of a several cellular automata is curious. Until now, are not shown and the various options to influence the behavior of one cellular automata by other CA are not considered.

How CAs can influence each other's behavior?

  • 1.

    The CA can change the state of all the cells.

  • 2.

    CA may change the state of the selected cell at each time step.

  • 3.

    CA can modify the structure of the neighborhood of one or all of the cells.

  • 4.

    CA can modify the local transfer function of one of CA cells, or all of the CA cells.

  • 5.

    CA can change the location of the main cells or of the inhomogeneous cells.

Thus, the above influence the cellular automata on cellular automata will be begin from dividing them onto controlled cellular automata (cellular automata, which receives control signals) and the control cellular automata (the cellular automata, which generates control signals).

Let us consider the influence of ACA on the HCA. Both of those cellular automata in the previous sections are considered. The first ACA operates as an asynchronous cellular automata. It has only one active cell changes its state at each time step of the ACA work. The second HCA function as a classic cellular automata with inhomogeneous cells.

The outputs of the each ACA cell to the control inputs of the respective HCA cells are connected. The ACA output signals change the behavior of the corresponding HCA cell. The simplest example of the PRNG controlling based on the HCA is a change in the location of the major HCA cell. The main HCA cell generates a sequence of bits at each time step. The first ACA influences on the coordinates of the main HCA cells by changing of the coordinates location of the active ACA cell. This allows to enter the additional uncertainty in the distribution of elements in the output sequence.

In this case, the active cell may be an inhomogeneous cell, and we can remove the constant comparison of current the HCA states with HCA state arrays, which at the previous time steps are formed. This increases the performance of the generator.

The behavior of the HCA cells can be described by the same model that in the previous sections is proposed. All the HCA cells change their state, but only one active cell generates the next bit sequence at the output at any given time step. At the same time, the active cell changes its location in each subsequent time step. An example of the operation of such cellular automata is shown on the Figure 1.

Figure 1.

An example of the functioning of a complex cellular automata

From the figure, we see that each subsequent bit of the formed sequence is calculated by the formula.

. (1)

This model shows that the output bit at time step t depends on the value of the active cell output signal with the coordinates (i, j), and on the signal at one of the active inputs of this cell. If , the cell with the coordinates (i, j) becomes into the active state and the data output of this cell to the output of the pseudorandom number generator is connected at time step t. The situation of the connection of the information output of the active cell to the output of the pseudorandom number generator is shown on the Figure 2.

Figure 2.

The graphical representation of the cells connection situation to the output of the pseudorandom number generator

Complete Chapter List

Search this Book: