SR Latch, D Latch and arrays.

Introduction

Links to previous posts: Part 1 Part 2 Part 3 Part 4 Part 5 Part 6 Part 7

Now that we have a nice GUI, we can finally look into memory devices.

SR Latch

The most basic memory device that can be made with NAND logic is the SR Latch. It has two inputs: S (set) and R (reset). When S is 1 the output is set to 1, and when R is 1 the output is set to 0. Otherwise, when S=0 and R=0, the output doesn’t change. Therefore, it can be summarized by the following truth table:

S R  Qnext
0 0  Q
0 1  0
1 0  1
1 1  1

The S=1 R=1 combination is usually invalid, but here the set signal takes priority.

We can build a SR Latch using only 2 NAND gates:

With the caveat that the inputs must be negated.

component nSnRLatch(n_S, n_R) -> (Q, n_Q) {
    Nand(n_S, n_Q) -> Q;
    Nand(n_R, Q) -> n_Q;
}
component SRLatch(E, S, R) -> Q {
    Nand(E, S) -> n_S;
    Nand(E, R) -> n_R;
    nSnRLatch(n_S, n_R) -> (Q, n_Q);
}

I recorded a short video to show it in action, but embedding it was too difficult so if you want to see it click here:

https://i.imgur.com/RWHww0e.gifv

We can see how the n_Q output is incorrect when n_S = 0 and n_R = 0, the invalid S=1 R=1 combination. But as long as we don’t use the n_Q output we can define S=1 R=1 to be equivalent to S=1 R=0, because both options set Q to 1.

D Latch

Truth table:

E D  Qnext
0 0  Q
0 1  Q
1 0  0
1 1  1

Or, simplifying:

E Qnext
0 Q
1 D

This means, keep the current state when Enable = 0, and load new Data when Enable = 1.

A D Latch can be easily built using a SR Latch: we just need to set S=1 when E=1 and D=1, and R=1 when E=1 and D=0.

component DLatch(E, D) -> Q {
    Nand(D, E) -> n_S;
    Nand(n_S, E) -> n_R;
    nSnRLatch(n_S, n_R) -> (Q, n_Q);
}

The D Latch is useful when we have more than 1 bit of data. We can easily make a 4-bit register by combining 4 D Latches:

component Reg4(E, D3, D2, D1, D0) -> (Q3, Q2, Q1, Q0) {
    DLatch(E, D3) -> Q3;
    DLatch(E, D2) -> Q2;
    DLatch(E, D1) -> Q1;
    DLatch(E, D0) -> Q0;
}

This way we just have to connect the data we want to store, and connect some control signal to enable, and we can easily store all the data we want.

Now if we wanted to make a 8-bit register…

component Reg8(E, D7, D6, D5, D4, D3, D2, D1, D0) -> (Q7, Q6, Q5, Q4, Q3, Q2, Q1, Q0) {
    Reg4(E, D7, D6, D5, D4) -> (Q7, Q6, Q5, Q4);
    Reg4(E, D3, D2, D1, D0) -> (Q3, Q2, Q1, Q0);
}

… we can just use 2 4-bit registers, but writing each input is becoming tedious.

Arrays

The obvious solution is to implement arrays. The code would simplify to:

component Reg8(E, D[8]) -> Q[8] {
    Reg4(E, D[7:4]) -> Q[7:4];
    Reg4(E, D[3:0]) -> Q[3:0];
}

A lot nicer, but this syntax has one flaw:

component Reg8(E, D[8]) -> Q[8] {
    Reg4(E, D[7], D[6], D[5], D[4]) -> (Q[7], Q[6], Q[5], Q[4]);
    Reg4(E, D[3], D[2], D[1], D[0]) -> (Q[3] ,Q[2], Q[1], Q[0]);
}

D[8] can mean “an array of 8 elements”, or it can mean “the bit in position 8 in array D”. Depending on the context, Not(D[8]) -> Q[8] negates one bit, or defines a component which negates 8 bits. A simple way to avoid this problem is to change the array definition syntax. For example:

component Reg8(E, D[7:0]) -> Q[7:0] {
    Reg4(E, D[7:4]) -> Q[7:4];
    Reg4(E, D[3:0]) -> Q[3:0];
}

This would make it more consistent.

The other problem is a technical one. Imagine what would happen if we mistakenly change the order of the inputs:

component Reg4(D[3:0], E) -> Q[3:0] {
    ...
}

component Reg8(E, D[7:0]) -> Q[7:0] {
    Reg4(E, D[7:4]) -> Q[7:4];
    Reg4(E, D[3:0]) -> Q[3:0];
}

Now Reg8 will not work as expected, because Reg4 is defined as D3, D2, D1, D0, E while it is used as E, D3, D2, D1, D0. This should obviously be an error, but it depends on the implementation.

There are two options: treat everything as a Bit, as we are doing above, or treat everything as an array. The second option would mean that Reg4 is defined as:

component Reg4(D[3:0], E[0:0]) -> Q[3:0] { }

So the call in Reg8 would try to assing D[7:4] to E[0:0], which will obviously fail.

The next problem is why stop at 1D arrays, what about higher dimensions? For example, a component which holds 16 8-bit registers which can be read all at once:

component Reg8x16(enable, select[3:0], data[7:0]) -> regs[15:0][7:0] { }

Until now we always assumed that D[0] is one bit, since the only way to use arrays is to define a range, like D[3:0], but now regs[0] is a 8-bit register! This could be fixed by making regs[0] invalid syntax, in favor of regs[0][7:0]. But this opens even more questions, should we allow regs[15:0][7], which returns the MSB of each register? And should that be a 1D array with 15 elements, or a 2D array with one element in each “row”, making it 15x1? Anyway, any N-dimensional array can be simplified to a 1D array, a 15x8 array is equivalent to a 120 element array. So maybe making the 1D array the most basic type is a good idea?

Internally, we can represent each argument independently, as enable, select[3:0], data[7:0], but we can also merge the 3 inputs into one: inputs[12:0] = (enable, select[3:0], data[7:0]). Until now we have worked with Vec<Bit> to represent the inputs, which is equivalent to inputs[12:0], but we can switch to Vec<Vec<Bit>>, which would be (clk[0:0], select[3:0], data[7:0]).

And what about one-element arrays? clk[0:0] is a one-element array, equivalent to just clk.

Anyway, all this design choices can wait, because I found a very easy way to implement arrays: literally replace D[3:0] with D$3, D$2, D$1, D$0. This way we treat everything as a bit, so there is no “type safety” preventing us from making mistakes, but that will be fixed in future language revisions, first I would like to actually try it and write some programs.

You can see the full implementation here:

https://github.com/Badel2/comphdl/compare/48a936e...7fadaaa

The changes in the grammar are the following:

• Introduce numbers, and ranges:

pub Range: (u64, u64) = {
    "[" <a: Number> ":" <b: Number> "]" => (a, b)
};
pub Number: u64 = {
    r"[0-9]+" => <>.parse().unwrap()
};

• Since we introduced numbers, variables can not start with a number:

r"([_\pL][_0-9\pL]*)" => format!("{}", <>),

• Introduce a BitArray, which is either a Word, or Word Range: either x or x[3:0]. Here is the magic that expands x[3:0] into x$3, x$2, x$1, x$0.

pub BitArray: Vec<String> = {
    Word => vec![<>],
    <w: Word> <r: Range> => {
        let mut i = r.0;
        if i == r.1 {
            return vec![w];
        }
        let mut v = vec![];
        let isign = if r.0 < r.1 { 1 } else { -1 };
        while i != r.1 {
            v.push(format!("{}${}", w, i));
            // Use wrapping add because instead of subtracting 1
            // we add -1, which would otherwise panic because of overflow
            i = i.wrapping_add(isign as u64);
        }
        v.push(format!("{}${}", w, i));
        v
    },
};

pub BitArrayArgs = Comma<BitArray>;

• Replace VarArgs with BitArrayArgs, turn the Vec<Vec<String>> into Vec<String> using flat_map.

"(" <BitArrayArgs> ")" => <>.into_iter().flat_map(|x| x).collect() 

And basically that’s the whole implementation, plus a few tests and bug fixes.

GUI changes

I have decided to use a real text editor instead of a textarea, because not being able to press tab to indent was too frustrating. I have chosen ACE , mainly because it is the one used in the Rust Playground. It has so much features that it haven’t explored them all, but I managed to integrate it so there it is.

Unfortunately this means slower load times for the demo, but I guess most people have a better internet connection than me so they won’t mind.

I have also added basic support for GET parameters in the URL, so we can share code by adding ?code=component asdf() { ... } to the URL.

Other supported parameters are top, which sets the top component name, and example which automatically loads an example. Nothing too complicated yet.

Conclusion

Now with arrays, we can create bigger circuits a lot easier. I hope that soon we will begin to create some bigger examples to fully test the language.

Start playing with the demo: https://badel2.github.io/comphdl/demo/v08/

You can play with the code from this post by clicking here .

Part 8