The chapter describes the basic models and paradigms for constructing asynchronous cellular automata with one active cell. The rules for performing local state functions and local transition functions are considered. The basic cell structures during the transmission of active signals for various local transmission functions are presented. The option is considered when the cell itself selects among the cells in the neighborhood of the cell, a cell that will become active in the next time step, and also the structure with active cells under control is considered. The analysis of cycles that occur in cellular automata with one active cell is carried out, and approaches to eliminating cycles are formulated. Cell structures are constructed and recommendations for their modeling in modern CAD are formulated.
TopModel Of A Cellular Automata With A Single Active Cell
Cellular automata with one active cell belong to the ACA family, in which only one cell at a time changes its state. In this case, at each subsequent moment of time, the cell, which is in a predetermined neighborhood with the active cell at the current time, changes its state.
An active cell is a cell that at the current time can perform a local state function (LSF). In accordance with LSF, an active cell forms its new information state or remains in its current state. Also, an active cell (AC) implements a local transition function (LTF) to select AC at the next time (Bilan, 2017; Bilan, Bilan, & Bilan, 2015; Bilan, Bilan, & Bilan, 2017; Bilan, et al 2016).
AC is characterized by the fact that it forms an information signal (a state signal at the current moment of time) and an additional signal of the active state. The signal of the active state indicates that at the next moment in time one of the cells in the neighborhood will go into the active state. The generalized cell structure of such a cellular automaton on Figure 1 is shown.
Figure 1. Block diagram of an ACA cell with one active cell
The cell contains information inputs (Xdata), which are connected to the information outputs (Qinf) of all cells in the neighborhood, inputs of active states (Xact), which are connected to the corresponding outputs of the active states (Qact) of the cells. Each cell also contains (but may not contain) a synchronization input (CLK).
Depending on the active state transmission mode, the number of active outputs may vary. If a mode is used in which the active cell itself selects the next active cell from the cells in the neighborhood, then the number of active outputs is greater than 1. In this case, the cell contains n active inputs Xact,1,…, Xact,n (were n – the number of neighborhood cells), the number of which is equal to the number of cells in the neighborhood. In the case when each cell in the neighborhood of the active cell itself determines its next state of activity, then the active output of Qact can be one. In this case, the cell contains n active inputs Xact,1,…, Xact,n.
According to the presented graphical interface of the cell (Figure 1), the following models can describe the cell.
,
(4),
(5) were
– local state function of cell.
Model (4) implements the first active state transmission mode, and model (5) implements the second active state transmission mode. An example of the functioning of an ACA with one active cell on Figure 2 is shown.
Figure 2. An example of the functioning of an ACA with one active cell