Simulation, and visualization

As part of my project, I've written a few C++ programs, the most interesting of which, is a CA-simulator, which I'm using as a reference for my hardware implementation. This simulator runs the CAs for a set number of generations, and outputs the results in text form, so that it can be compared to the results in the hardware implementation.

Now, reading thousands of binary digits in text becomes rather unwieldy quite fast, so I also wrote a simple program that converts the text output to BMP, for easier comparison. An added bonus here, is that the hardware implementation is itself simulated in ModelSim, which allows me to output the intermediate states in text form. (Following some helpfull hints from this forum thread.) The format that my C++ simulator outputs is designed to mimic the same file format that ModelSim uses, this way I can create BMPs from both, for comparison.

In my last post I mentioned Rule 30, now, let's see how my simulator-output looks for Rule 30:

Here time flows from top to bottom, and each line represents a generation of the CA.

Note the line at the top, this stems from the solution I've chosen for loading initial data into the grid of CA's:

I put the column I want to load as the neighbours of the left-most cells (in this case we're working one-dimensionally, so the column is actually a single value. Then the rules for the grid are held to be "take on the value that your left-hand neighbour has", thus essentially shifting the values into the grid.

When the values are finally shifted into the grid (roughly 1/3 from the top), the grid starts to follow the Rule 30-ruleset, with the edges of the grid being set to 0.

This way of representing the CAs allows for a quick visual inspection that it tends to follow the intended behaviour, and thus allows for easy comparison with the hardware implementation.

It's worth mentioning though, that the CA-system does not really allow reading from anything but the edges, but for testing purposes we cheat a little, both in C++, and in ModelSim, so that we can read the actual values. In a proper setup, we would have to work only based on what we can read from the edges, but even then, we can actually read the entire grid, given that we do the following:

1. Allow the grid's rightmost cells to be read
2. Make the grid "wrap", so that the rightmost cells have the leftmost cells as their neighbours and vice verca
3. Use the same "shift rule" as for loading
4. Read every column, and apply the rule to get the next column.

Thus, the entire grid can actually be read, even in a proper "non-cheating" implementation.

So, what are Cellular Automata anyway?

Cellular Automata are simply a set of "cells" that change their state depending on their neighbours state. If a set of neighbours had a certain state in one generation, then their state in the next generation is defined by their state in the previous generation.

As an example, say you have five cells with this state in generation n:

0,0,0,1,0

And that we only worry about the immediate neighbours of each cell, what is their state in generation n +1?

To figure out what each cell's state is supposed to be in the next generation, we're going to have to define a set of "rules". That is, a table of neighbour-configurations and the corresponding next state, an example of this would be:

000 -> 1 (Read: Left neighbour is 0, Cell itself is 0, and Right neighbour is 0, then next state for this cell is 1)

For a full example of our selected set of cells we'll follow Rule 30 (named so according to the Wolfram classification scheme), which we can get from http://en.wikipedia.org/wiki/Rule_30#Rule_set.

The rules say that any cell that has a neighbour-configuration of 100,011,010 or 001, should be 1 in the next generation, and otherwise it should be 0. The middle digit in these configurations represent the cell itself, from this we can read that any cell that is 1 will become 0 unless either none of it's neighbours, or only it's right hand neighbour are 1. (Correspondingly, any 0-cell will become 1 if exactly one of it's neighbours are 1)

One question that is still not covered though: What are the neighbours of the edge-cells? Here we have a few options:

1. We could say that they only have one neighbour (but then our rules wouldn't be generic) 
2. We could let them "wrap", i.e. the leftmost node has the rightmost node as it's left neighbour, and vice verca
3. We could make their neighbours a constant value (i.e. always 1 or always 0).

For this demonstration, we'll pick option 3, and let the edge cells have a constant 0-neighbour.

So, let's step through our five cells from right to left (numbering them from the left, to follow a convention that i'll come back to later):

Generation n + 1:

Cell 5: 0, neighbour-configuration: 000, next state: 0

Cell 4: 0, neighbour-configuration: 000, next state: 0

Cell 3: 0, neighbour-configuration: 001, next state: 1

Cell 2: 0, neighbour-configuration: 010, next state: 1

Cell 1: 0, neighbour-configuration: 100, next state: 1

This yields:

0,0,1,1,1

Now, following the same rules a few generations:

Gen n + 2: 0,1,1,0,0

Gen n + 3: 1,1,0,1,0

Gen n + 4: 1,0,0,1,1

Gen n + 5: 1,1,1,1,0

Gen n + 6: 1,0,0,1,1

...

Now, it's important to note one detail here, the neighbour-states that go into defining the state in generation (n+1) MUST be the states from generation n, thus we must take care when working with CA's, so that we don't use the state from generation (n+1) untill we're starting work on creating generation (n+2).

What is this?

My name is Einar Johan Trøan Sømåen, I'm currently attending the final year of my Masters degree in Computer Science at the Norwegian University of Science and Technology.

As my pre-master-thesis project I'm creating a Cellular Automata Accellerator for SHMAC. This blog is mostly intended to be a place for me to braindump while I pull together the final parts of this project.

Some interesting test-results, and solutions to problems as I encounter them, is probably what I'll put here.