State Machine
Now it is finally time to write some code. The swim template project contains some example code in main.spade, feel free to run swim upload to test it if you’d like. However, for this project, we won’t need any of it, so once you are done playing around with it, remove all code from main.spade.
We’ll start off by writing the state machine that generates the drive signals for the rest of the circuit.
For simplicity, the state machine will not take any input control signals, it will start running as soon as the reset signal is turned off, and write data as
For those unfamiliar, a Finite State Machine is less scary than the words make it seem. It is a way to do computation by describing a series of states and how and when to change between the states.
For example, if we want to build a circuit to toggle an LED whenever a short pulse arrives1, our FSM would consist of two states: On and Off. If no pulse arrives, the current state remains. If the pulse arrives, we transition from the current state to the opposite state.
It is usually convenient to look at small FSMs graphically, the following figure shows the states and transitions of the pulse example
ast as possible until the end of time.
State machine entity
Let’s start off with defining an entity that will contain the state machine. This entity will be generic over the index width as discussed previously, and will take a number of LEDs to control as a normal parameter. It returns an ControlSignal which we will discuss in detail at the end of this section.
entity state_gen<#uint IndexWidth>(
clk: clock,
rst: bool,
num_leds: uint<IndexWidth>
) -> OutputControl<uint<IndexWidth>> {
// TODO
}
Let’s work on that // TODO next. Recall that when working in Spade, we always describe the behaviour of our circuit between one clock cycle and the next. However, we want to implement an interface that is time-dependent, so we need to do some thinking. In a high level language, we’d want to do something like
while true {
// Generate the RET signal between every LED update
for t in 0..ret_duration {
output = Ret;
wait_clock_cycle;
}
// Send the LED commands
for i in 0..num_leds {
for bit in 0..24 {
for t in 0..bit_duration {
output = Led(i, bit, t)
wait_clock_cycle;
}
}
}
}Unfortunately, in hardware we cannot simply run a loop as there is no processor which can jump around in the program. Instead, we have to implement this same logic in a different way. Most of the time, this is done by writing a state machine. The exact method is somewhat situation dependent and takes some practice. To be successful at this task, we have two basic constrains: we need enough information to know what state to jump to at all times, and we need enough information to know what output to generate. In Spade, we’ll almost always represent the states with an enum
enum State {
// ...
}
The RET signal
Let’s start off with the first for loop to generate the RET signal. We need to keep track of how long we’ve been in RET, so we know when to jump over to the output generation loop. A good starting point is therefore a state, with a duration
enum State {
Ret{duration: uint<17>},
// ...
}
The state_gen entity we started writing earlier will need an instance of the state enum, which is updated at every clock cycle. A perfect use for the reg statement and match expression:
entity state_gen<#uint IndexWidth>(
clk: clock,
rst: bool,
num_leds: uint<IndexWidth>
) -> OutputControl<uint<IndexWidth>> {
reg(clk) state reset(rst: State::Ret(0)) = match state {
// TODO: Compute next state here
};
}
What happened here? We have a register called state which we update by checking the state in the current clock cycle, to build a circuit that gives the state in the next. Since state depends on itself, it needs to be reset back to an initial value when the FPGA, which is why write reset(rst:. This will make the circuit send the RET signal to the LEDs when starting up, then operate as normal. We could have started emitting LED values too, but this makes the description easier and gives the LEDs a few microseconds to get up and running during power up.
State::Ret(0))
How do we compute the next state in the Ret state? That depends on how long we have been in Ret already. If that time is longer than the minimum time in Ret, we can start emitting LED data, otherwise we’ll stay in the Ret state. We’ll write this logic as
entity state_gen<#uint IndexWidth>(
clk: clock,
rst: bool,
num_leds: uint<IndexWidth>
) -> OutputControl<uint<IndexWidth>> {
reg(clk) state reset(rst: State::Ret(0)) = match state {
State::Ret(duration) => {
if duration >= Tret {
// TODO: First LED state
} else {
State::Ret(trunc(duration + 1))
}
},
// ...
};
}
You may be curious why we needtruncthere. That’s because Spade does not implicitly cast away overflow.duration+1is 1 bit larger thandurationif it overflows. To make it fit back into our state, we truncate the result of the addition, since we know that we have chosen duration to be large enough for it not to be an issue.
Timing
The keen eyed might have noticed Tret there. What is its value? It represents the minimum time that we should emit the ret signal, but duration is in clock cycles. Eventually, Spade might support being generic over clock cycles and allow you to reason about time natively. For now, we need to compute how many clock cycles Tret is manually. This of course depends on the clock frequency, a value which varies between FPGAs boards.
Since we’ll need a few more time dependent parameters down the line, we’ll define a Timing struct which we pass to the modules, which contains the relevant timings. We might write something like this
struct Timing {
Tret: uint<17>,
T0h: uint<12>,
T0l: uint<12>,
T1h: uint<12>,
T1l: uint<12>,
bit_time: uint<12>,
}
However, now the user needs to know what those implementation dependent times are, which probably requires going to the data sheet. To make their life simpler, let’s change it to
struct Timing {
// 280 microseconds
us280: uint<17>,
// 0.4 microseconds
us0_4: uint<12>,
// 0.8 microseconds
us0_8: uint<12>,
// 0.45 microseconds
us0_45: uint<12>,
// 0.85 microseconds
us0_85: uint<12>,
// 1.25 microseconds
us1_25: uint<12>,
}
and update our entity
entity state_gen<#uint IndexWidth>(
clk: clock,
rst: bool,
num_leds: uint<IndexWidth>,
timing: Timing,
) -> OutputControl<uint<IndexWidth>> {
let t_ret = timing.us280;
reg(clk) state reset(rst: State::Ret(0)) = match state {
State::Ret(duration) => {
if duration >= t_ret {
// TODO: First LED state
} else {
State::Ret(trunc(duration + 1))
}
},
// ...
};
}
NOTE: If you’ve been following along with a datasheet, for example the first result on duck duck go, or the first result from google you may be confused by why we use 280 microseconds and not 50. It turns out that the manufacturers of the LEDs updated the protocol at some point without updating model numbers or datasheets. this took quite a few hours of debugging when the code worked on old LEDs, but not a new strip.
Bit signals
To generate the bit signals, i.e. the nested for loop in the example above, we need to keep track of 3 things: which LED we’re working on, which bit on that LED we’re working on, and how long we’ve been in that state. Essentially 1 variable per loop level. We’ll extend the state enum to fit:
enum State<#uint IndexWidth> {
Ret{duration: uint<17>},
Led{idx: uint<IndexWidth>, bit: uint<5>, duration: uint<12>}
}
How do we want the logic to work? At the “innermost level”, if we aren’t done emitting the current bit, we increase the duration by 1. If the duration reaches the bit time, we move on to the next bit, and if we are done with all bits, we move on to the next LED. Finally, if we reached the last LED, we’ll go back to the RET state.
In Spade, we’ll write that as
entity state_gen<#uint IndexWidth>(
clk: clock,
rst: bool,
num_leds: uint<IndexWidth>,
timing: Timing,
) -> OutputControl<uint<IndexWidth>> {
let t_ret = timing.us280;
let t_bit = timing.us1_25;
reg(clk) state reset(rst: State::Ret(0)) = match state {
State::Ret(duration) => {
if duration >= t_ret {
State::Led(0, 0, 0)
} else {
State::Ret(trunc(duration + 1))
}
},
State::Led$(idx, bit, duration) => {
if duration == t_bit {
if bit == 23 {
if idx == trunc(num_leds-1) {
State::Ret(0)
}
else {
State::Led$(idx: trunc(idx+1), bit: 0, duration: 0)
}
}
else {
State::Led$(idx, bit: trunc(bit+1), duration: 0)
}
}
else {
State::Led$(idx, bit, duration: trunc(duration + 1))
}
},
};
}
Spade supports passing arguments to units both by position, i.e. argument 1 is passed to parameter 1, 2 to 2 and so on, and also by name. To specify parameters by name, the calling parenthesis are preceded by$, i.e.State::Led$(idx, bit, duration: trunc(duration + 1))says to pass the variable calledidxto the parameteridx,bittobit, andtrunc(duration + 1)toduration. This works the same way as the rust struct initialization syntax
Output type
We now have a state machine that that goes through the various states needed to drive the LED, but we haven’t output anything from it yet. Recall that we are going to output a general value that specifies where in the LED chain we are which the user can then translate into exact RGB values. This timing information along with the RGB values can be used to generate the final output to push to feed the LEDs.
We might start off with a type like this to describe the output:
enum OutputControl<#uint IndexWidth> {
/// Currently emitting the RET signal
Ret,
/// Currently emitting the specified bit of the color for LED `index`
Led{index: uint<IndexWidth>, bit: uint<5>}
}
We make this enum generic over the width of the LED indices to not waste bits and allow an arbitrary number of LEDs
This enum has a few issues though, so let’s make some improvements.
First, the data coming out of the color translation block will end up being quite similar to this enum, so we can use generics to share some code. The user will translate the index into a color, so we will allow arbitrary payload instead of that index
enum OutputControl<T> {
/// Currently emitting the RET signal
Ret,
/// Currently emitting the specified bit of the color for LED `index`
Led{payload: T, bit: uint<5>}
}
This is enough information to write the color translator, but to generate the output, it would be nice to have some more information. Specifically, because this is a time based interface, we could more easily generate the output waveforms if we knew how long we’ve been emitting the current bit. Let’s add that to the enum
enum OutputControl<T> {
/// Currently emitting the RET signal
Ret,
/// Currently emitting the specified bit of the color for LED `index`
Led{payload: T, bit: uint<5>, duration: uint<12>}
}
If you are curious, the width of the duration field is 12 to support a counter counting from 0 to 1250. This was chosen because the total duration of a data bit is 1.25 microseconds, which takes 1250 clock cycles at 1 GHz, and we are unlikely to run our FPGA above that frequency. Better generics over clock frequencies is something that might happen down the line
Finally, generating the output signal can be done by another match statement. Since State and OutputControl are very similar in this case, the resulting match statement is not very complex:
match state {
State::Ret(_) => OutputControl::Ret(),
State::Led$(idx, bit, duration) =>
OutputControl::Led$(payload: idx, bit, duration)
}
match state {
State::Ret(_) => OutputControl::Ret(),
State::Led$(idx, bit, duration) =>
OutputControl::Led$(payload: idx, bit, duration)
}
Putting it all together, we end up with the following code:
entity state_gen<#uint IndexWidth>(
clk: clock,
rst: bool,
num_leds: uint<IndexWidth>,
timing: Timing,
) -> OutputControl<uint<IndexWidth>> {
let t_ret = timing.us280;
let t_bit = timing.us1_25;
reg(clk) state reset(rst: State::Ret(0)) = match state {
State::Ret(duration) => {
if duration >= t_ret {
State::Led(0, 0, 0)
} else {
State::Ret(trunc(duration + 1))
}
},
State::Led$(idx, bit, duration) => {
if duration == trunc(t_bit - 1) {
if bit == 23 {
if idx == trunc(num_leds-1) {
State::Ret(0)
}
else {
State::Led$(idx: trunc(idx+1), bit: 0, duration: 0)
}
}
else {
State::Led$(idx, bit: trunc(bit+1), duration: 0)
}
}
else {
State::Led$(idx, bit, duration: trunc(duration + 1))
}
},
};
match state {
State::Ret(_) => OutputControl::Ret(),
State::Led$(idx, bit, duration) =>
OutputControl::Led$(payload: idx, bit, duration)
}
}
entity state_gen<#uint IndexWidth>(
clk: clock,
rst: bool,
num_leds: uint<IndexWidth>,
timing: Timing,
) -> OutputControl<uint<IndexWidth>> {
let t_ret = timing.us280;
let t_bit = timing.us1_25;
reg(clk) state reset(rst: State::Ret(0)) = match state {
State::Ret(duration) => {
if duration >= trunc(t_ret -1) {
State::Led(0, 0, 0)
} else {
State::Ret(trunc(duration + 1))
}
},
State::Led$(idx, bit, duration) => {
if duration == trunc(t_bit - 1) {
if bit == 23 {
if idx == trunc(num_leds-1) {
State::Ret(0)
}
else {
State::Led$(idx: trunc(idx+1), bit: 0, duration: 0)
}
}
else {
State::Led$(idx, bit: trunc(bit+1), duration: 0)
}
}
else {
State::Led$(idx, bit, duration: trunc(duration + 1))
}
},
};
match state {
State::Ret(_) => OutputControl::Ret(),
State::Led$(idx, bit, duration) =>
OutputControl::Led$(payload: idx, bit, duration)
}
}
While we hope that the above code will work on the first try, that is rarely the case in practice. The next section will discuss how we can test our design
- 1perhaps a pulse from a button, though some extra circuitry would be needed to turn the “short” pulse of a human pressing the button into a pulse that is “short” for an electronics circuit :)