Pseudorandom Number Generators Based on Asynchronous Cellular Automata

Pseudorandom Number Generators Based on Asynchronous Cellular Automata

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


The fourth chapter deals with the use of asynchronous cellular automata for constructing high-quality pseudo-random number generators. A model of such a generator is proposed. Asynchronous cellular automata are constructed using the neighborhood of von Neumann and Moore. Each cell of such an asynchronous cellular state can be in two states (information and active states). There is only one active cell at each time step in an asynchronous cellular automaton. The cell performs local functions only when it is active. At each time step, the active cell transmits its active state to one of the neighborhood cells. An algorithm for the operation of a pseudo-random number generator based on an asynchronous cellular automaton is described, as well as an algorithm for working a cell. The hardware implementation of such a generator is proposed. Several variants of cell construction are considered.
Chapter Preview

Asynchronous Cellular Automaton Model For The Realization Of A Random Number Generator

The analysis of known CA showed that the one-dimensional ECA does not implement a high-quality PRNG as a single homogeneous source of pseudo-random numbers. All ECA cells change their state for a given function of local transitions in each subsequent time step. HCA based on the one-dimensional CA also have a number of weaknesses. As mentioned earlier, one-dimensional CA may be replaced on the LFSR (Schneier, 1996; Bardell, 1990).

It is more promising to look at two-dimensional CAs. We can use a synchronous or asynchronous CA. In this section, we will look at the structure and principles of the asynchronous cellular automata functioning of with one active cell (ACA active cells may be more).

The asynchronous cellular automata with one active cell is determined as a normal two-dimensional classical CA, in which all the cells are set to perform the same function of local transition (LTF), and only one cell performs LTF and resets its state at each subsequent time step.

One cell ACA performs local transition function among all the other cells and resets its state at the current time step, is called the active cell.

Also it is called an active cell if it has an active state. Each cell asynchronous cellular automata is in the main information state. This state is determined by the state of the cell signal. For a hardware implementation asynchronous cellular automata important information state determined by the state of memory cell element (flip-flop) and by the value of the signal at its output. In addition, each asynchronous cellular automata cell may be having additional active state. In hardware implementation, is considered that a cell is located in an active state, if an additional memory element (additional trigger) have logic “1” state.

We know the possible states of asynchronous cellular automata cells. However, we do not yet know the rules of the transition asynchronous cellular automata cells in the active state. At this point in time the two variants of the transition is determined by author.

  • 1.

    An active cell at the current time itself determines which neighborhood goes into the active state in a next time.

  • 2.

    Each cell belonging to the neighborhood of the active cell decides to move it to an active state or not.

The first version of the transition of cells in an active state is determined by the function of transmission in active state (FTAS). Arguments of the function of transmission in active state of the active cell are the information cells states signals, which belong to the neighborhood of the active cell at the current time. In this case, the cell becomes active; if on the one of the active input the signal of logical “1” state is presented. This is the only condition for the transition cells in the active state. The cell becomes active at the next moment and does not depend on the basic information cells states of the surrounding area at the current time.

The second variant of cells transition to an active state next time step is characterized in that the cell analyzing basic information states of own neighborhood cells and cell analyzes additional active state own neighborhood cells. If one of the active cells inputs has a logical “1” signal (this means that one of the neighborhood cells is active), the cell performs the local transition function over the main information states of its neighborhood cells. If LTF give the result of the logical “1”, then the cell becomes active the next time step.

The function of transmission in active state and local transition function for both the active state transmission options are selected by experimentally or analytically. Generalized structure of the cell behavior in such ACA is shown on Figure 1.

Figure 1.

The behavioral ACA cell interface

The cell has an initial setting input, N data inputs (Х1,…, ХN) and N of active inputs (С1,…,СN). Also, the cell contains the main data output and N active outputs (У1,…, УN). Such ACA cells interface allows to realize both the transfer active state modes from cell to cell. The difference is in the implementation of the internal structure of the cell for each mode.

Complete Chapter List

Search this Book: