Game of Life with CMOS logic

Device description

Main blocks

Schematic

So, system time is counted this way:

0,1,2,…16,
0,1,2,…16,

and then eventually

0,1,2,…16,17…127,128…255

and then

0,1,2,…16.

U21 is configured to count on negative system clock edges. All other system is clocked by positive edges. This way, by the time system clock goes high system time is established for half a clock period.

T7-T0 signals mean something system-wide:

System time summary is in this table: Game of Life timing.

Operation of this block

This schematic worked fine when simulated in LTSpice.  You can run it yourself, here is the LTSpice asc file. You’ll also need to install additional libraries for 74HC and CD4000, which are available in the Files zone of LTSpice yahoo group (registration is needed). Only difference btween simuation and real schematic is that T5 is used to trigger monostable instead of T7 – but it’s only to reduce simulation time.

In reality, I made it work, although I had hard time with half-monostable.

Half-monostable

Using half-monostable to measure long time intervals wasn’t the best design decision. I had problems with running monostable with 10uF capacitor, because U21′s output is just not strong enough to recharge capacitor during T7==1 time. Practical C20 value is under 1uF, which leads to several hundred kOhm resistors. In my case it was 235kOhm, and it gave about 3steps per second.

I also could not find suitable variable resistor to adjust time (it would be 470k or so), so I’ve shorted it out.

Having no threshold in U20.4 lead to a lot of oscillations when voltage on it’s input crosses the half of supply. It leads to heavy timing problems. Timing given by this monostable is also very imprecise.

I ended up with an additional board with 555 timer, which worked fairly well. Files: 555 diptrace source555 schematic.pdf. This schematic also allows to change game step time with common 10k variable resistor.

555 monostable schematicAdding 555 as monostable

RC oscillator

This oscillator worked more or less fine, although with jitter visible on oscilloscope. I noticed that it changes frequency when I move my hand closer to the circuit, by up to 2-3 kHz. Not that it is so critical for this design, but in next design I’d probably use 32768Hz quartz oscillator for system clock.

Matrix and Display blocks

Matrix is made of eight 74HC595 SIPO registers.
The Matrix - Game of Life
Their parallel outputs form row data bus C7-C0 (‘C’ stands for ‘column’). U9 (74HC138), demultiplexer with active-low output, enables output of only one register at a time depending on T2-T0.

Registers are also connected in series, input of row 0 (U1) being connected to system-wide SDI line, output of row 7 (U7) – to SDO line.

Data from serial part of ’595 to the parallel part is latched on the falling edge of T7, after whole matrix update is finished. This is very important feature for game of life logic, because generally, until all new data is not loaded into the matrix, data from the previous turn should persist.

Display block is very simple. Foryard ultra-green 8×8 LED matrix with common anode is used. Columns are driven directly with ’595 outputs – their 4mA rated output is enough to drive LED matrix with comfortable brightness. Rows are driven with PNP pull-up transistors.

Display - Game of Life

Both matrix and display worked fine when soldered – there’s just nothing to break. Only pinout of the matrix I bought differs from that in the schematic – I had to make different wiring.

Game of Life logic block

This is probably the main block in the device. Let’s see how it works.
Next Alive logic - Game of Life Operation of this block is done in 8 stages, each completed in two phases. Each stage processes one row of cells and serially loads next step cell values into the matrix. Stage number is T6-T4.

First phase completes in 8 cycles, when T3 is 0. During this phase, data of every row in a matrix appears on C7-C0 bus (selected by T2-T0 lines of time bus).

Registers U16, U17, U18 (HCF4021) latch data of adjacent rows:

U13, U14, U15 select which row to latch – those are demultiplexers with 3-state outputs. Time lines T6-T4 tell those multiplexers which stage is currently running and demultiplexer connects it’s output to one of R7-R0 row selects. When right data to be latched is on the C7-C0 data bus, corresponding Rx signal appears on the inverting output and is latched into the register by the pulse on P/S input. To make pulse on P/S input more precise, it is only active during first half of system clock cycle.

Second phase is completed when T3==1. During this stage P/S inputs of U16-U18 is held low and they operate in serial mode. Serial input of those registers is connected to Q8 output to make data rotate in the registers when clock is applied. And it ticks 8 times during second phase, sequentially showing all 8 updated cells and their neighbours during second stage. As you can see, there are only 3 outputs on these magic registers – perfect for our game of life application.

In the second phase cell state and neighbor states for 8 cells in a row sequentially show up on U16-U18 Q6-Q8 outputs.

Because first data to be loaded into the matrix should be (C7,R7) data, during the first stage (T6..T4==0), row 7 is fetched as the current row, row 6 as previous row, and row 0 as the next row (remember, we create torus topology).

Because we have only Q6,Q7,Q8 outputs, and not Q0,Q7,Q8, data is latched into U16-U18 pre-rotated, so that when the first cell is updated, Q6,Q7,Q8 show state of C6,C7,C0. Which row is latched when is summed in this table: data-selector-truth-table.xls.

Quite easy schematic allows us to determine next cell state:

Two problems popped out when debugging this block.

Otherwise, this block operates quite well.

States block

This block controls operation of the whole system. It is operated by four buttons, implementing finite state machine (FSM) with 6 states.

Game of Life State Diagram
For simplicity, each state is designated by four bits corresponding to distinct actions: Edit, Random, Read, Write, which are outputs of U21.

Random state is split into 2 states, but to detect that random pattern should be inserted, only Random bit needs to be polled.

U21 is a clocked quad D-type latch with normal and inverting outputs, providing a lot of usefu signal which other system blocks may use. Data on U21′s inputs are latched on positive edge of T7. Each next state is defined by previous state, keys pressed and AllOnesDet input from the control block. As all bits of U21 have specific meaning, creating FSM is very easy.

Let’s write down the rules for state transition:

Edit bit: D3 = Q3 ^ (Edit/Run button)

Random bit: D4 = (!Q4 & !Q3 & AllOnesDet) | (!Q4 & Q3 & (Random button))

Read bit: D1 = Q3 & (Read button) & !(Write button)

Write bit: D2 = Q3 & (Write button) & !(Read button)

Read and Write buttons are made mutually exclusive, otherwise Flash access conflict may happen. User may press Random button simultaneously with Read or Write button, but it is not a problem – Random and Read/Write operations are not in conflict.

Some simulations in LTSpice IV for this state machine.

Button presses are debounced with U20 quad R-S latch. It is a clocked debouncer with a rate equal to game rate: when button is pressed, it’s press is remembered until T7 goes high.

Edit block

This block takes data from SDI, knowing how it’s clocked, and outputs it to Edit net. It can invert, edit or randomize data bits as they pass.

Let’s look how data is edited. There are 8 push-buttons for rows and 8 push-buttons for columns. To edit data, user presses one or more column buttons and one or more row buttons. All cells on laying on the crossing of selected rows and columns are toggled once per game step.

Here’s the schematic.

Edit - Game of Life
It is known (or, forethought) that serial clock coming to the Matrix in Edit mode is gated so that it is only active when T3=1. Bits T2-T0 designate column of current bit, and bits T6-T4 designate row. Column bits select one of the inputs of U13 multiplexer, and row bits select U14 multiplexer inputs. Common pin of U13 is connected to VCC, common pin of U14 is pulled to the ground with resistor. When multiplexers select row and column where both buttons are pressed, current flows through resistor and logic one comes to U9.3 XOR gate, making it invert data coming from the Matrix.

Additional clear button changes all bits to 1′s when pressed.

Flash block

Flash block operates AT45DB011D SPI flash, and can operate any flash chip from AT45DB family. This flash was chosen because it’s write operation can be implemented very easy, comparing to other flash memories.

Data is written with the following sequence:

Read is even more complex:

Atmel flash has very small page size (256-512 bytes), and all pages can be written independently, without erasing anything in advance. In this device, one matrix image is written per flash page, starting with address 0, utilizing AT45DB’s fine internal page write and small page size.

Let’s see how write in implemented:

Read is implemented nearly the same:

Flash read/write cycles are summed in this table: gol-flash-working-mode.xls

Address is 8-bit and it is selected with a DIP-switch. Initially, I’ve designed electronic address selector with 2 buttons and two 7-segment LED indicators, but then threw them out of the project not to complicate things. This schematic is here.

It seems that accompanying logic is not completely right in current schematic, so I will recheck it in the next revision.

I did not solder flash block because other blocks worked not very good.

Control block

This block interconnects serial signals from matrix, flash, random generator and editing block. It does little more than that.
Control - Game of Life
It has the following clock inputs:

And it has following data inputs:

Of all these inputs control block generates SDI and SCK signal for the Matrix. You can see whan clock and data is generated in different modes of operation in this table gol-game-working-mode.xls.

Current implementation of control block is buggy. It generates SCK when T7==0, when no update should be done, effectively pushing away valuable data from the Matrix.

Another block on this page detects when all ones were clocked into the matrix during T7==1 state. It is created with two D-triggers (U24). All ones correspond to all dead cells, so it’s nice to detect this state. You can see how this schematic simulates in LTSpice IV here gol-allones-ltspice.xls.

First trigger is set to one when T7 is 0. When T7 is one, data for this trigger is set as it’s previous state logically AND’ed with next data. Upon the falling edge of T7 this information is lathed in the second register. If any 0 was clocked with SCK (alive cell), AllOnesDet will become zero for the next game period.

Random generator

This is a hardware random generator:
Random - Game of Life
It’s idea is flowing in the Internet, but I didn’t solder it and do not know yet if it will work.

I’ve also placed DIP-switch address selector here.

Conclusion

Even not having success with making it running, it was a great experience. I’ve carried out a lot of knowledge. Not only I’ve better understanding of how logic chips work, but I’ve learned the hard way how good PCB and good flux could make my life a lot easier.

I read “CMOS cookbook” by Don Lancaster, which was really great reading, no matter it’s 25+ years old.

I’ve learned to never use half-monostables described in “CMOS cookbook” again. At least, never use them to generate long delays and also to use it with extra caution with a clocked logic. I’d better go for 555 timer, or make a delay with long counters.

I also learned things about PCB fabrication. My project is 2 PCB’s with about 500 pins each, which is more than I’ve done before. Some chips were not available in DIP packages, so I went for SOIC. I should have stayed with DIP where available to make my life easier!

I carefully placed components and then let autorouter to make a layout. I have had selected 0.2 mm traces with 0.2 mm spacing between traces – it’s my board manufacturer’s standard rules. I wanted to make a board with solder mask, but in the end I understood that my mask won’t pass manufacturer’s DRC. So I made boards without mask. It was a great mistake! Debugging this board in really… er… debugging. Any small piece of solder ends in between two traces and creates a short strong enough to make circuit misbehave, but weak enough to find it with a tester.

And last, I will buy good and expensive flux now. I will never use that Chinese “Soldering paste” again. It looks like flux, but it is only good to solder copper cookware. I’ve never notice this before, but a bit of this flux in 0.2 mm gap between traces will create you less than 100k resistance between them. You can never delete this flux from under the chip and without solder mask it was the main disaster for my two boards. In the end I desoldered chips one after another, removed residual flux and soldered them back again – and it basically started working.

Anyway, I’m going to make version 2 and make it really rock!

Tags: , ,

{ 1 comment to read ... please submit second! }

  1. It is very difficult! – Easier to use MC (for exumple: ARM Cortex LPC11XX or STM32F2XX ) and write an algorithm on C.
    Anatoly

{ 0 Pingbacks/Trackbacks }

Leave a Reply

Your email address will not be published. Required fields are marked *

*


4 + = seven

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>