Developers Club geek daily blog

2 years, 7 months ago
In advance I will warn: it is a lot of pictures.

In this article it will be a question of implementation of the game "Life" on logical elements in the Atanua simulator.

The game "Life" is, perhaps, one of the most recognizable cellular automatons. About it it is written not one article including on Habrakhabr. Once too became interested in it, but somehow for a long time did not last.

I will remind what is "Life":
There is some matrix from cages which is called "Universe" (ideally infinite). On each iteration (called in "days") any cage can be "live" or "dead", and its status depends on the previous iteration by the following rules:

  • The cage comes to life if in its neighborhood there are 3 living cells.
  • The cage continues to live if in its neighborhood 2 or 3 cages are live.
  • In other cases the cage dies.

8 cages surrounding it are considered as the neighborhood of a cage (see the two-dimensional neighborhood of Moore about 1).

It is possible to learn about "Zhizna" in Wikipedia in more detail.

Heard somewhere later that modern computers have restriction in speed caused including existence of some communication channel between memory and a computing kernel. As a solution it was offered to collect the considering memory. I already definitely do not remember, whether I remembered about "Life", whether it was mentioned in that article, but I wanted to simulate it in the logic diagram (if to be exact, then in a matrix of identical schemes). Why "Life"? Its prevalence and popularity, and also that fact that "Universes" in it are Turing complete that allows to make on it any calculations were basic reasons and to solve various problems. It turns out, on the basis of this cellular automaton it is possible to create the computer.

As the tool the Atanua simulator (official site) as quite easy in mastering and displays a status of all lines was selected. Finally the following turned out:

Scheme of one cell
The game "Life" on logical elements

One convenient feature of the Atanua simulator is that it is possible to connect schemes as, some kind of, chips in other projects. I also used it, having collected a matrix for debugging and experiments.

Cell array
The game "Life" on logical elements

For more detailed consideration upper left corner:

The game "Life" on logical elements

The r button is used for reset of the scheme. The buttons signed as "0" are used for installation of a cell in a live status. I want to notice, reset by repeated clicking is not implemented yet. 3 lower grounding are used as scheme limiters that various artifacts did not appear. In Atanua the wire can have 4 statuses:

  • dark green: log. 0;
  • light green: log. 1;
  • red: it is not correctly connected;
  • white: it is not connected (an indefinite status).

At the same time, if on an input of logical element the indefinite status is given, then some can distinguish it as 0, and some as 1. For this purpose also limiters in the form of installation of not used outputs in 0 were put.

Do not pay attention to upper grounding. The original version of the scheme demanded initialization for what this output and was used. Now is a rudiment (not to remake a matrix), and its status can be any. One more wire leaving outside drawing is an output of a clock signal. It goes to a set of generators on which tested maximum speed.

Now is more detailed about the scheme of a cell. Because of problems with quality of screenshots, I will give drawings of separate nodes.

Register


The game "Life" on logical elements

In drawing the bit looped shift register on the D triggers which acts as memory is given 2nd above. One not good moment which I still should correct is connected with it: during operating time the scheme as if blinks as in an active status (when in this register information, that is in a status of living cell is written) triggers exchange among themselves 0 and 1 and it turns out that on F output (an output on indication of a status, on a LED for example) we have 0, 1 (it is noticeable on video at the end of article). RST is an input of reset. SET – an input of installation of a cell in a status of living cell. As it was already mentioned, reset of a separate cell is not provided yet. At the left on top the clock signal approaches. About the next two wires further.

Check block


The game "Life" on logical elements

In the block of check check on a game condition is performed. On top on the birth, from below on a survival. Feature of this block consists that it can be arranged and under other rules, thereby having organized similar cellular automatons. At the left outputs from adders, from below – those two wires which go to the register approach. They, in fact, are connected in a section of one of interposition circuits of the register.

Adders


The game "Life" on logical elements

Perhaps, the most most and inconsistent part of the scheme are parallel consistently connected adders. Having implemented it, I solved a problem of check of necessary conditions "in a forehead", having summed up all inputs of A0-A7 from the next cells and having checked result for compliance to conditions. In this case inputs of A0+A1+A2, A5+A6+A7, then result of the second sum outputs of A3 and A4 and so on are summed up at first. Finally 6 adders and 1 half-adder turned out finally. It should be noted one of adders it is possible to replace with the half-adder since one of its inputs is not used also. Why I made one grounded input (at the left from below dark green leaving out of drawing limits) – I do not remember. Initially wanted to simplify it by means of DNF or KNF, but to solve Carnot's card 8x8 desires does not arise yet. So I do not exclude, that moment that this module can have an alternative appearance.

C – it is an input of that frequency, has no relation to the scheme of adders, goes to the register. About Init I wrote above – a rudiment from last option.

Result


I do not consider the game "Life" as the worthy cellular automaton for implementation of the considering memory as "program" for such computer will take very many place and is difficult in implementation. But nevertheless the scheme allows on to dream of a chip with implementation of cells of this game. I think it it would be quite interesting, to see hardware implementation of this cellular automaton. And I mean not microcontrollers with the program, and is exclusive on cells from logical elements.

As for the scheme, in it of course there are enough defects, but for experiments quite is enough. Whether I will finish it? Frankly speaking, I do not know how the soul will lay down.

Finally several video with work:

Glider:



Small ship:



Went in and pentadekatlon:



Files with the project on Google Drive.

Some explanation on contents:

live.atanua — a cell;
LiveFieldM.atanua — a matrix;
LiveField.atanua — small array element (8x8) from which was created by LiveFieldM. Edges are not grounded.

For detection to put in one folder. If does not help, edit files in any text editor (on structure, normal XML).

This article is a translation of the original post at habrahabr.ru/post/271457/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: sysmagazine.com@gmail.com.

We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.
Best wishes.

comments powered by Disqus