Hello FPGAmigos ! In my previous post, I shared My First Project Using Chisel. However, maybe it is too much for a first beginner project. Therefore, in this post, we will explore a simpler project called “Rule 90.” Rule 90 can be considered as a step before the LED Chaser project I previously shared (regarding difficulty, not in nature). Maybe I will cover a blinker in the future, but let’s focus on Rule 90 for now.

I chose Rule 90 because it is simple yet scientifically interesting. It is a type of cellular automata (CA), which are computational models consisting of a grid of cells that can be in one of several states. These cells are updated at discrete intervals based on rules that consider the states of neighboring cells.

Cellular automata have been extensively studied in various scientific fields, including physics, biology, computer science, and mathematics. They have been used to model a wide range of phenomena such as fluid flow, pattern formation, and the behavior of living organisms.

One of the most famous CAs is the Game of Life, created by John Conway in 1970. I will definitely cover this in a future article, so stay tuned!

Another notable CA is Rule 110, which is a one-dimensional CA capable of universal computation (Turing complete). Rule 110 is simple to describe with only three rules but can exhibit complex behavior. I have designed it just after Rule90, and I will share it with you soon.

Today, we will focus on Rule 90, another one-dimensional CA.

The Rule 90

Rule 90 is a one-dimensional cellular automaton that can be handled using an array or vector of bits. The cells in this automaton can either be DEAD (0) or ALIVE (1). To determine the state of a cell in the next cycle, we use an XOR operation between its two neighbors.

Here is a truth table to illustrate this:

Rule 90 gets its name from the binary representation of the next state column, which is 01011010 in binary and 90 in decimal.

I will continue to use my Alchitry CU board with the IO element shield, which provides access to 24 aligned LEDs. For my implementation of Rule 90, I will use 24 cells.

The code

You can find my Chisel code for Rule 90 on my GitHub page. If you prefer to work with Verilog, I encourage you to try implementing Rule 90 using HDLBits and then compare your Verilog code with my Chisel version.

// 1.
class cellAutomataBundle(numCells: Int) extends Bundle{
    // 2. 
    val i_cells = Input(Vec(numCells, UInt  (1.W)))
    val o_cells = Output(Vec(numCells, UInt(1.W)))
}

1. Firstly, I utilized Chisel’s ability to create bundles and instantiate them in my other modules. Since both Rule 90 and Rule 110 require 24 LEDs, I decided to reuse the same bundle for both of them.

2. Secondly, since each cell is a bit, I organized them as a vector of 24 “single” bits rather than a 24-bit UInt. I found it easier to handle the cells in this way.

The rule 90 module:

class Rule90(numCells: Int) extends Module {
    // 1.  
    val io = IO(new cellAutomataBundle(numCells))
    // 2.
    for(idx <- 0 until numCells){
        // 3.
        val previous_idx = Math.floorMod(idx - 1, numCells)
        val next_idx     = Math.floorMod(idx + 1, numCells)
        // 4.
        io.o_cells(idx) := RegNext(io.i_cells(previous_idx) ^ io.i_cells(next_idx), 0.U)   
    }
}

1. In the `Rule90` module, I create a new instance of `cellAutomataBundle` in the first line of the module. This allows me to reuse the bundle that I previously defined.

2. Next, I use a simple for loop from 0 to 23 to describe the next state of each cell.

3. Inside the loop, I define the previous and next indexes which correspond to the two neighbors of a cell. I use the `floorMod` function to ensure that the first and last cell of the vector are considered neighbors. Topologically our colony of cells is a circle, not a segment.

4. I calculate the XOR between the two neighbors using `io.i_cells(previous_idx) ^ io.i_cells(next_idx)`. Then, I use `RegNext`, a Chisel function, to instantiate a register for the expression I put as the first argument. The second argument is the initial value of the register, which is 0 in this case.

However, in order to display Rule 90 on LEDs, we need to address two additional problems. Firstly, we need to initialize the cells. Secondly, if we connect this module directly to the LEDs, we will only see LEDs with dim brightness, because the FPGA frequency is 100MHz, resulting in 100 million generations of cells per second. To address this issue, we need to use a PulseGenerator.

The pulse generator:

class PulseGenerator(pulsePeriod: Int) extends Module{
    val io = IO(new Bundle{
        val pulse = Output(UInt(1.W))
    })
    // 1.
    val pulse = RegInit(0.U(log2Ceil(pulsePeriod).W))
    // 2.
    pulse := Mux(pulse===pulsePeriod.U, 0.U, pulse+1.U)
    // 3.
    io.pulse := pulse===pulsePeriod.U
}

The `PulseGenerator` module generates a pulse with a specific period. It takes a `pulsePeriod` parameter as input, which represents the desired period of the pulse.

1. In the first line of the module, I use `RegInit` to instantiate a register. The parameter is the initial value with the width of it. Here, the initial value is 0 with a bit size necessary (log2Ceil) to count until `pulsePeriod`.

2. I use a `Mux` to create a counter that increments by one until it reaches `pulsePeriod`, at which point it resets to 0 and starts counting again. The output of the `Mux` is the input of the `Mux` incremented by one. The input of the `Mux` is the register named `pulse` most of the time and 0 when the value in `pulse` register is equal to `pulsePeriod`. This creates a free counter (count without stopping) until `pulsePeriod`, then restarts at 0 and continues in a loop.

3. Finally, the pulse of our `PulseGenerator` is asserted when `pulse===pulsePeriod.U`, which by the design of the counter only lasts one cycle every `pulsePeriod` cycles.

The top:

class AlchitryCUTop extends Module {
    val io = IO(new Bundle{
        val ledPins = Output(Vec(24, UInt(1.W)))
    })
    val fpgaFreq = 100000000
    val numLeds  = 24

    // the alchitry CU board has an active low reset
    val reset_n = !reset.asBool
    withReset(reset_n){
        val rule90          = Module(new Rule90(numLeds))
        val next_generation = Module(new PulseGenerator(fpgaFreq))
        for(idx <- 0 until numLeds){
            //                        2.        1.                       3.                        
            rule90.io.i_cells(idx) := RegEnable(rule90.io.o_cells(idx), (Random.nextInt(100)%2).U, next_generation.io.pulse.asBool)
        }
        // 4.
        io.ledPins <> rule90.io.o_cells
    }
}

In the `AlchitryCUTop` module, I create an instance of `Rule90` and `PulseGenerator` modules. Since the Alchitry CU board has an active low reset, I instantiate these modules inside the `withReset(reset_n)` brackets.

1. I connect the input `i_cells` of the `Rule90` module to its output `o_cells`. I could have named `i_cells` “old_generation” and `o_cells` “new_generation” for clarity.

2. I use `RegEnable`, which creates a register with an enable (see What is a DFF? if you’re not familiar with this term). It is similar to `RegNext`, but with a third parameter for the enable. Here, the enable is the pulse of the `PulseGenerator` module with a `pulsePeriod` equal to the `fpgaFreq`. This allows us to have a new generation of cell every second, which is much easier to follow with your eyes than 100 million per second.

3. I initialize my register with a random value (0 or 1) provided by the Scala standard library `scala.util`.

4. Lastly, I connect the output of `Rule90` to the LEDs by using `io.ledPins <> rule90.io.o_cells`.

Here the pins constraints, if you don’t want to read the schematics:

set_io clock P7
set_io reset P8
set_io io_ledPins_0 G14
set_io io_ledPins_1 F14
set_io io_ledPins_2 E12
set_io io_ledPins_3 E14
set_io io_ledPins_4 D14
set_io io_ledPins_5 C14
set_io io_ledPins_6 B14
set_io io_ledPins_7 A12
set_io io_ledPins_8 C10
set_io io_ledPins_9 C9
set_io io_ledPins_10 A11
set_io io_ledPins_11 A10
set_io io_ledPins_12 A7
set_io io_ledPins_13 A6
set_io io_ledPins_14 A4
set_io io_ledPins_15 A3
set_io io_ledPins_16 A2
set_io io_ledPins_17 A1
set_io io_ledPins_18 C3
set_io io_ledPins_19 D3
set_io io_ledPins_20 B1
set_io io_ledPins_21 C1
set_io io_ledPins_22 D1
set_io io_ledPins_23 E1

Result

Our tiny colony of cells living an happy life :

One pretty initialization with the Rule90 is to replace the random initialization(4.) by only a one in the middle :

//                                                      =>     only a 1 on led 12    <= 
rule90.io.i_cells(idx) := RegEnable(rule90.io.o_cells(idx), if (idx==12) 1.U else 0.U, next_generation.io.pulse.asBool)

Rule 90 has indeed a fractal behavior as shown here:

Conclusion

I hope you enjoyed this project! Rule 90 has simple rules, is easy to design, and belongs to a very deep and interesting field of science. These factors make it an excellent way to pique the curiosity of beginners and young learners (at least it does for me).

I believe that this kind of problem is a good candidate for learning any HDL. I hope this article gave you a better understanding of Chisel. If you would like me to explore another HDL, please let me know in the comments.

Thank you for reading! If you enjoyed this article, please bookmark, share, and comment. See you next time!