Hello FPGAmigos! In our last session, we explored the Rule 90, a basic cellular automaton that required only a XOR and pulse generator to create an impressive LED garland. Today, we will delve into a slightly more complexe cellular automaton, namely Rule 110.

The rule 110

Rule 110 is a one-dimensional cellular automaton that consists of cells that are either DEAD (0) or alive (1). The next state of a cell is determined by its own state and the state of its two neighbors, unlike Rule 90, where the state of the cell is dependent only on its neighbors and not itself.

There are three conditions that lead to the death of a cell in Rule 110:

Overpopulation: If the cell and its two neighbors are alive (1), then the cell dies (0).

Underpopulation: If the cell is dead (0) and its two neighbors are also dead (0), then the cell remains dead.

The left is bad? : If only the left cell is alive, then the cell remains dead.

In any other condition, the cell either remains alive or becomes alive (1).

Below is the truth table of Rule 110:

The code

You can find the code for this on my GitHub WsAZGkE6vu%^eNzX8D!8page. If you’re interested in designing it in Verilog, I encourage you to try it out on HDLBits.

class Rule110(numCells: Int) extends Module{
    // 1.
    val io = IO(new cellAutomataBundle(numCells))
    val biomeStates  = RegInit(VecInit(Seq.fill(numCells)(0.U(3.W))))
    // 2.
    for(idx <- 0 until numCells){
        val previous_idx = Math.floorMod(idx - 1, numCells)
        val next_idx     = Math.floorMod(idx + 1, numCells)
        // 3.
        biomeStates(idx) := io.i_cells(previous_idx) ## io.i_cells(idx) ## io.i_cells(next_idx)
        when(biomeStates(idx)===0.U || biomeStates(idx)===4.U || biomeStates(idx)===7.U){
            io.o_cells(idx):= 0.U
        }.otherwise{
            io.o_cells(idx):= 1.U
        }
    }
}

1. Similar to the implementation of Rule90, a cellAutomataBundle is created to reuse in other Rule implementations.

2. A for loop is used to ensure that the last cell and the first cell are neighbors, just like in the Rule90 implementation.

3. The ## operator from Chisel3 is used to concatenate the three cells (represented here by three wires) into an unsigned integer of three bits. By converting the states of the three cells into an unsigned integer, we can simplify the death conditions into numbers. For instance, overpopulation is represented by 111 in binary, which is equal to 7 in decimal. Similarly, underpopulation is represented by 000, which becomes 0. The condition for the only left cell being alive is 100, which also becomes 7.

The top:

class AlchitryCUTop extends Module {
    val numCells = 24
    val io = IO(new Bundle{
        val ledPins = Output(Vec(numCells, UInt(1.W)))
    })
    // the alchitry CU board has an active low reset
    val reset_n = !reset.asBool
    val fpgafreq = 100000000

    withReset(reset_n){
        val cellular_automata = Module(new OneModuleToRuleThemAll(numCells))
        val next_generation = Module(new PulseGenerator(fpgafreq))
        for(idx <- 0 until numCells){
            // 1.
            cellular_automata.io.i_cells(idx) := RegEnable(cellular_automata.io.o_cells(idx), if (idx==numCells-1) 1.U else 0.U, next_generation.io.pulse.asBool)
        }
        io.ledPins <> cellular_automata.io.o_cells
    }
}

Here is the Rule110 colony living:

1. It also have a fractal behavior like Rule90. Whith this iniatialisation in the top level :

rule110.io.i_cells(idx) := RegEnable(rule110.io.o_cells(idx), if (idx==numCells-1) 1.U else 0.U, next_generation.io.pulse.asBool)

Since we have already covered Rule90, this article might seem a little light. However, we can extend the concept and create a RuleAny automaton with just a few modifications.

class OneModuleToRuleThemAll(numCells: Int) extends Module{
    val io = IO(new cellAutomataBundle(numCells))
    // 1.
    val biomeStates        = RegInit(VecInit(Seq.fill(numCells)(0.U(3.W))))
    val deathConditions    = List(0.U, 2.U, 5.U, 7.U) // RULE 90
    val numDeathConditions = deathConditions.length
    val judges             = List.fill(numCells*numDeathConditions)(Module(new EqualityChecker(3)))
    val verdicts           = List.fill(numCells)(Module(new ReduceOr(numDeathConditions)))
    // 2.
    for(idx <- 0 until numCells){
        val previous_idx = Math.floorMod(idx - 1, numCells)
        val next_idx     = Math.floorMod(idx + 1, numCells)
        biomeStates(idx) := io.i_cells(previous_idx) ## io.i_cells(idx) ## io.i_cells(next_idx)
        // 3. 
        for(death <- 0 until numDeathConditions){
            judges(idx*numDeathConditions+death).io.input1:=biomeStates(idx)
            judges(idx*numDeathConditions+death).io.input2:=deathConditions(death)
            verdicts(idx).io.inputs(death) := judges(idx*numDeathConditions+death).io.output
        }
        io.o_cells(idx) := !verdicts(idx).io.output
    }
}

1. The purpose of biomeStates is to store the 24 neighborhoods, and deathConditions represents the conditions under which the next state of a cell will be dead (0). For this example, the Rule90 condition is used. judges and verdicts are lists of modules that we will cover next.

2. The first part of the loop is the same as in Rule90. It uses a modulo to ensure a circular topology.

3. For the second part of the loop, we need to check if the biome meets the death condition. Judges check whether biomeStates meet a death condition, while verdicts take all the results from the judges. If a death condition is met (result = 1), then the cell must die (state = 0), hence the inverter. Here’s how it works:

a. We create judges by instantiating EqualityChecker modules, which compare the biomeStates with each of the deathConditions.

b. We then create verdicts by instantiating ReduceOr modules, which take all the results from the judges. If a death condition is met (result = 1), then ReduceOr returns 1 on its output IO.

c. Finally, we set the output of the OneModuleToRuleThemAll module to be the negation of the output from verdicts.

Here is the code for EqualityChecker and ReduceOR:

class EqualityChecker(width: Int) extends Module {
    val io = IO(new Bundle{
        val input1 = Input(UInt(width.W))
        val input2 = Input(UInt(width.W))
        val output = Output(UInt(1.W))
    })
    io.output:= io.input1 === io.input2
}

class ReduceOr(nbValue:Int) extends Module {
    val io = IO(new Bundle{
        val inputs       = Input(Vec(nbValue, UInt(1.W)))
        val output     = Output(UInt(1.W))
    })

    io.output := io.inputs.asUInt.orR // cast our vec as UInt and make an or reduce operation
}

Regarding point 3 of the OneModuleToRuleThemAll, I must admit that I encountered some difficulty. I wanted to create a beautiful one-liner to showcase the power of Chisel, but this approach made me think like a software engineer, and I forgot that I was working on hardware. After several attempts, I ended up drawing my idea on a piece of paper, naming my modules, and this helped me solve the problem : I needed to create modules. This highlights a potential caveat of Chisel: while it offers many software-like features, we must always remember that we are working with hardware. Therefore, it is essential to think “hardware first” when working with Chisel (or any HDL). If possible, it is better to create intermediate modules like EqualityChecker and ReduceOr to make the design more modular and easy to understand. Having several identifiable modules is better than having an unreadable one-liner.

With this code, you can simulate any RuleN. Although I am not aware of any other interesting rules besides Rule90 and Rule110, creating parametrized and generic designs is always funny.

Thank you for reading until the end! If you found this article helpful, please consider bookmarking, sharing, or leaving a comment.