The game "Life" on the logical elements
I will warn in advance: quite a lot of pictures.
This article focuses on the implementation of the game "Life" on the logical elements in the simulator "Atanua".
The game "Life" is perhaps one of the most recognizable cellular automata. About her written not one article, including on Habrahabr . Once, too, became interested in her, but somehow it did not last long.
Later I heard somewhere that modern computers have a speed limit caused, including the presence of a certain communication channel between the memory and the computing core. As a solution, it was proposed to collect counting memory. I don’t remember exactly whether I myself remembered about Life, or whether it was mentioned in that article, but I wanted to model it in a logical scheme (to be exact, in the matrix of identical schemes). Why just “Life”? The main reasons were its prevalence and fame, as well as the fact that the “universes” in it are Turing-complete, which makes it possible to perform any calculations on it and to solve various tasks. It turns out that a computer can be created on the basis of this cellular automaton.
The Atanua simulator ( official site ) was chosen as a tool, as it is fairly easy to learn and displays the status of all lines. The end result is the following:
One convenient feature of the Atanua simulator is that it is possible to connect the circuits as, of a kind, chips to other projects. This I took advantage of, collecting a matrix for debugging and experiments.
For a more detailed view of the upper left corner:
The “r” button is used to reset the circuit. Buttons signed as “0” are used to set the cell to the live state. I want to note, reset by pressing again is not implemented. The 3 lower grounds are used as limiters of the circuit so that various artifacts do not appear. In Atanua, a wire can have 4 states:
At the same time, if an indeterminate state is applied to the input of a logic element, then some may recognize it as 0, and some as 1. For this, limiters were set in the form of setting unused pins to 0.
Do not pay attention to top grounding. The initial version of the scheme required initialization, for which this output was used. Currently, this is a rudiment (so as not to alter the matrix), and its state can be any. Another wire extending beyond the edge of the figure is the clock output. He goes to a set of generators, which tested the maximum speed.
Now more about the cell layout. Due to quality problems with screenshots, I will give pictures of individual nodes.
The figure above shows a 2-bit looped shift register on D triggers, which acts as a memory. One not a good moment is connected with it, which I have yet to correct: during operation, the circuit flashes, as in the active state (when information is recorded in this register, that is, in the living cell state), triggers exchange 0 and 1 it turns out that at output F (exit to the status indication, to the LED for example) we have either 0, then 1 (this is noticeable in the video at the end of the article). RST is a reset input. SET - input of the cell installation to the living cell state. As already mentioned, a separate cell reset is not yet provided. At the top left is the clock signal. About the next two wires further.
In the check block, a check on the condition of the game is carried out. From above on birth, from below on survival. The peculiarity of this block is that it can be adjusted to other rules, thereby organizing similar cellular automata. On the left are the outputs from the adders, from the bottom - the same two wires that go to the register. They are, in fact, connected in the context of one of the transfer lines of the register.
Perhaps the largest and most controversial part of the scheme are parallel-connected totalizers. Having implemented it, I solved the problem of checking the necessary conditions "on the forehead," summing up all the inputs A0-A7 from neighboring cells and checking the result for compliance with the conditions. In this case, the inputs A0 + A1 + A2, A5 + A6 + A7 are summed up first, then the results of the second sum are the conclusions A3 and A4 and so on. In the end, it turned out eventually 6 adders and 1 half-adder. It is worth noting one of the adders can also be replaced by a half adder, since one of its inputs is not used. Why did I make one grounded input (on the left below the dark green one that goes beyond the limits of the figure) - I do not remember. Initially, I wanted to simplify it with the help of DNF or CNF, but deciding on a Karno map of 16x16 does not yet arise. So I do not exclude the fact that this module may have an alternative form.
C is the input of such a frequency; it has no relation to the adder circuit; it goes to the register. About Init, I wrote above - a rudiment from the previous version.
I do not consider the game “Life” to be a worthy cellular automaton for realizing counting memory, since the “program” for such a computer will take quite a lot of space and is difficult to implement. But still, the scheme allows us to dream of a chip with the implementation of the cells of this game. I think it would be quite interesting to see the hardware implementation of this cellular automaton. And I mean not microcontrollers with a program, but exclusively on cells from logical elements.
As for the scheme, there are certainly enough flaws in it, but for experiments it is quite enough. Will I refine it? Honestly, I do not know how the soul will fall.
Finally, a few videos with the work:
Glider:
Small ship:
Pentadekatlon fit in:
Files with the project on Google Drive.
Some explanation on the content:
live.atanua - cell;
LiveFieldM.atanua - matrix;
LiveField.atanua is a small matrix element (8x8) from which LiveFieldM was created. The edges are not grounded.
To detect folded in one folder. If it does not help, edit the files in any text editor (in structure, plain XML).
This article focuses on the implementation of the game "Life" on the logical elements in the simulator "Atanua".
The game "Life" is perhaps one of the most recognizable cellular automata. About her written not one article, including on Habrahabr . Once, too, became interested in her, but somehow it did not last long.
Let me remind you what “Life” is:
There is a certain matrix of cells, which is called the "universe" (ideally, infinite). At each iteration (called “days”), any cell can be “alive” or “dead”, and its condition depends on the previous iteration according to the following rules:
')
The surrounding cells are considered to be 8 surrounding cells (see Moore’s two-dimensional neighborhood of order 1 ).
More information about the "Life" can be found in Wikipedia .
')
- A cell comes to life if there are 3 living cells in its vicinity.
- A cell continues to live if 2 or 3 cells are alive in its neighborhood.
- In other cases, the cell dies.
The surrounding cells are considered to be 8 surrounding cells (see Moore’s two-dimensional neighborhood of order 1 ).
More information about the "Life" can be found in Wikipedia .
Later I heard somewhere that modern computers have a speed limit caused, including the presence of a certain communication channel between the memory and the computing core. As a solution, it was proposed to collect counting memory. I don’t remember exactly whether I myself remembered about Life, or whether it was mentioned in that article, but I wanted to model it in a logical scheme (to be exact, in the matrix of identical schemes). Why just “Life”? The main reasons were its prevalence and fame, as well as the fact that the “universes” in it are Turing-complete, which makes it possible to perform any calculations on it and to solve various tasks. It turns out that a computer can be created on the basis of this cellular automaton.
The Atanua simulator ( official site ) was chosen as a tool, as it is fairly easy to learn and displays the status of all lines. The end result is the following:
Single cell layout
One convenient feature of the Atanua simulator is that it is possible to connect the circuits as, of a kind, chips to other projects. This I took advantage of, collecting a matrix for debugging and experiments.
Cell matrix
For a more detailed view of the upper left corner:
The “r” button is used to reset the circuit. Buttons signed as “0” are used to set the cell to the live state. I want to note, reset by pressing again is not implemented. The 3 lower grounds are used as limiters of the circuit so that various artifacts do not appear. In Atanua, a wire can have 4 states:
- dark green: log. 0;
- light green: log. one;
- red: not properly connected;
- white: not connected (undefined state).
At the same time, if an indeterminate state is applied to the input of a logic element, then some may recognize it as 0, and some as 1. For this, limiters were set in the form of setting unused pins to 0.
Do not pay attention to top grounding. The initial version of the scheme required initialization, for which this output was used. Currently, this is a rudiment (so as not to alter the matrix), and its state can be any. Another wire extending beyond the edge of the figure is the clock output. He goes to a set of generators, which tested the maximum speed.
Now more about the cell layout. Due to quality problems with screenshots, I will give pictures of individual nodes.
Register
The figure above shows a 2-bit looped shift register on D triggers, which acts as a memory. One not a good moment is connected with it, which I have yet to correct: during operation, the circuit flashes, as in the active state (when information is recorded in this register, that is, in the living cell state), triggers exchange 0 and 1 it turns out that at output F (exit to the status indication, to the LED for example) we have either 0, then 1 (this is noticeable in the video at the end of the article). RST is a reset input. SET - input of the cell installation to the living cell state. As already mentioned, a separate cell reset is not yet provided. At the top left is the clock signal. About the next two wires further.
Check block
In the check block, a check on the condition of the game is carried out. From above on birth, from below on survival. The peculiarity of this block is that it can be adjusted to other rules, thereby organizing similar cellular automata. On the left are the outputs from the adders, from the bottom - the same two wires that go to the register. They are, in fact, connected in the context of one of the transfer lines of the register.
Adders
Perhaps the largest and most controversial part of the scheme are parallel-connected totalizers. Having implemented it, I solved the problem of checking the necessary conditions "on the forehead," summing up all the inputs A0-A7 from neighboring cells and checking the result for compliance with the conditions. In this case, the inputs A0 + A1 + A2, A5 + A6 + A7 are summed up first, then the results of the second sum are the conclusions A3 and A4 and so on. In the end, it turned out eventually 6 adders and 1 half-adder. It is worth noting one of the adders can also be replaced by a half adder, since one of its inputs is not used. Why did I make one grounded input (on the left below the dark green one that goes beyond the limits of the figure) - I do not remember. Initially, I wanted to simplify it with the help of DNF or CNF, but deciding on a Karno map of 16x16 does not yet arise. So I do not exclude the fact that this module may have an alternative form.
C is the input of such a frequency; it has no relation to the adder circuit; it goes to the register. About Init, I wrote above - a rudiment from the previous version.
Total
I do not consider the game “Life” to be a worthy cellular automaton for realizing counting memory, since the “program” for such a computer will take quite a lot of space and is difficult to implement. But still, the scheme allows us to dream of a chip with the implementation of the cells of this game. I think it would be quite interesting to see the hardware implementation of this cellular automaton. And I mean not microcontrollers with a program, but exclusively on cells from logical elements.
As for the scheme, there are certainly enough flaws in it, but for experiments it is quite enough. Will I refine it? Honestly, I do not know how the soul will fall.
Finally, a few videos with the work:
Glider:
Small ship:
Pentadekatlon fit in:
Files with the project on Google Drive.
Some explanation on the content:
live.atanua - cell;
LiveFieldM.atanua - matrix;
LiveField.atanua is a small matrix element (8x8) from which LiveFieldM was created. The edges are not grounded.
To detect folded in one folder. If it does not help, edit the files in any text editor (in structure, plain XML).
Source: https://habr.com/ru/post/271457/
All Articles