This is the first of a series of posts about writing a digital logic simulator in Rust. The goal is to be able to create and simulate a component-based circuit.

Introduction

What are digital circuits? Some “electronics” that operate on digital signals. Digital signals can only have discrete values, in contrast with analog signals.

But what is a component-based circuit? Usually, digital circuits are made out of other integrated circuits (also known as microchips). If you have ever seen the inside of a usb flash drive, or maybe a RAM stick, they have this flat black boxes surrounded with pins. But aren’t all digital circuits “component-based”? Well, yes, but these components are made out of transistors, not out of other components. The goal of this post series is to make big components out of smaller components, all the way up to a simple microprocessor.

Unfortunately we can’t play with hardware, so we will have to make our own simulator. Of course there are already hundreds of digital logic simulators, but using an existing one wouldn’t be a challenge.

I will be using the Rust programming language, but you can follow this post with a basic understanding of any other programming language, as long as it has functions I guess. By this I mean there won’t be anything Rust-specific in this post.

Let’s begin!

Let’s start with representing a digital bit. It can be either true (high) or false (low), but using a boolean wouldn’t be fun so we create an enum instead:

enum Bit {
    L, // Low, false, 0
    H, // High, true, 1
}

Now we need some way to play with this bits, some function that transforms a 1 into a 0, some kind of logic gate. One of the most basic logic gates is the NOT gate. It’s pretty simple: if the input is 0 the output is 1, and if the input is 1 the output is 0. This can be represented with the following table:

// NOT gate
// input = output
[L] = [H]
[H] = [L]

That table is called the truth table. But the NOT gate alone isn’t very useful, let’s introduce more logic gates. The AND gate is pretty simple, it’s true when all of its inputs are true:

// AND gate
// inputs = output
[L, L] = [L]
[L, H] = [L]
[H, L] = [L]
[H, H] = [H]

If we combine the AND gate with a NOT gate at its output, we get a NAND gate. It’s basically the inverse of the AND gate, its output is 0 when all of its inputs are 1, and 0 otherwise. Here is the NAND truth table:

// NAND gate
[L, L] = [H]
[L, H] = [H]
[H, L] = [H]
[H, H] = [L]

This gate may not seem very useful, but in fact it’s a universal logic gate. That means we can implement any logical function using only NAND gates. Therefore, if we implement a NAND gate we won’t have to implement any other gates, they could be implemented as combinations of NAND gates! So let’s do it.

fn nand2(a: Bit, b: Bit) -> Bit {
    match (a, b) {
        (Bit::L, Bit::L) => Bit::H,
        (Bit::L, Bit::H) => Bit::H,
        (Bit::H, Bit::L) => Bit::H,
        (Bit::H, Bit::H) => Bit::L,
    }
}

The Rust syntax may not be familiar to you so I’ll explain this one. We define a function called nand2, with two inputs a and b, both of type Bit, and this function returns one output of type Bit. The match statement represents the truth table, on the left we have the expected values of a and b, and on the right the correponding output.

To prove that the NAND is a universal gate, we will implement another logic gate using only NANDs. Let’s implement the AND gate. Since a NAND is just a negated AND, if we negate it again we will get a simple AND, just like negating a number twice gets you the number back:

fn and2(a: Bit, b: Bit) -> Bit {
    let x = nand2(a, b);
    nand2(x, x)
}

We are using the NAND with x as the only (repeated) input, which basically negates it. We must use it that way because we haven’t created a 1-input NAND gate yet, but as we see we don’t even need it. In Rust when the last line of a function doesn’t have a semicolon, it’s the same as return nand2(x, x);. You may think I’m cheating because that one was pretty obvious, but don’t worry, soon we will make more complicated stuff.

The idea is to create new components out of existing components, using those new components to make even more complex ones. The problem is that we need a nice way to chain gates together, creating complex components with simple interfaces.

Abstraction

Since a component is just like a function, a black box where we enter inputs and we receive an output, let’s implement it like that:

trait Component {
    fn update(&mut self, input: &[Bit]) -> Vec<Bit>;
}

This defines the Component “trait”. In other languages it can be implemented as an interface, or maybe even a parent class. Basically it defines a common trait for many objects. For now our Components will only have to implement the update function, which takes &[Bit] (an array of Bits) and returns Vec<Bit> (also an array of Bits), because sometimes we want to have more than one output. &mut self means that we call this function on some instance, as:

let output = nand.update(input);

So let’s re-implement our NAND gate as a Component. Since the update function accepts any number of inputs, we will have to modify our NAND. We could use recursion to implement a n-input NAND using the 2-input NAND, but there is a simpler method. Since the output of the NAND is H (1) when any of the inputs is L (0), we can just search the input array for any L:

fn nand(input: &[Bit]) -> Vec<Bit> {
    if input.iter().any(|&a| a == Bit::L) {
        vec![Bit::H]
    } else {
        vec![Bit::L]
    }
}

And just like that, we have a generic n-input NAND gate. vec![] is a macro that defines a vector, in this case with only one element since we want our output to be 1 bit. And that weird any function basically searches for values a that satisfy a == Bit::L.

But we can’t just implement the Component trait for a function, we need to create some type. We will use the following struct:

struct Nand {
    num_inputs: usize,
}
impl Nand {
    fn new(num_inputs: usize) -> Nand {
        Nand { num_inputs }
    }
}

Now when creating a NAND gate we have to call Nand::new(n), where n is the number of inputs. The type of n is usize, which is an unsigned integer. We could avoid that n and use the n-input NAND for everything but this way we are dealing with “real” gates, not some abstract functions. For the purposes of this posts, we will want our gates to have a defined number of inputs and outputs.

Let’s finally implement Component:

impl Component for Nand {
    fn update(&mut self, input: &[Bit]) -> Vec<Bit> {
        assert_eq!(self.num_inputs, input.len());
        if input.iter().any(|&a| a == Bit::L) {
            vec![Bit::H]
        } else {
            vec![Bit::L]
        }
    }
}

The only difference is that now we check the number of inputs using the assert_eq! macro, which checks if two elements are equal, and if they aren’t it panics and aborts the program. The update function doesn’t need to take &mut self, &self would be enough (because we don’t want to change (mutate) the number of inputs after creating a gate), but more complex components will need &mut self.

So let’s do something to try this code, this time it will be a 2-input OR gate. The OR gate output is true when any of its inputs is true. We will use the following identity, which can be implemented using 3 NAND gates:

A OR B == NOT(A) NAND NOT(B)

struct Or2 {
    nand_a: Nand,
    nand_b: Nand,
    nand_c: Nand,
}
impl Or2 {
    fn new() -> Or2 {
        Or2 {
            nand_a: Nand::new(1),
            nand_b: Nand::new(1),
            nand_c: Nand::new(2),
        }
    }
}
impl Component for Or2 {
    fn update(&mut self, input: &[Bit]) -> Vec<Bit> {
        assert_eq!(input.len(), 2);
        let a = input[0];
        let b = input[1];
        let not_a = self.nand_a.update(&[a])[0];
        let not_b = self.nand_b.update(&[b])[0];
        // not_a nand not_b == a or b
        self.nand_c.update(&[not_a, not_b])
    }
}

Try it online: playground link

And here is the truth table, as one would expect from an OR gate:

[L, L] = [L]
[L, H] = [H]
[H, L] = [H]
[H, H] = [H]

If you look at the code above you may think that this way is worse than the old generic nand function approach. You also may be wondering why we create two identical 1-input NANDs when one would be enough. The point is to not think about NAND gates, but about components. We could replace the 1-input NANDs with other 1-input and 1-output components and the code wouldn’t change. The only problem is that the connections between those components are fixed in the code. That will be our goal: a generic component interconnection, a way to give our program a list of components and connections between them, and simulate the circuit as a whole.

Conclusion.

We have seen various ways of implementing a NAND gate, and using this gate as a building block for more complex components. In the next post we will see a different (even more complicated) way to implement the OR gate, which hopefully will lead us to a generic way of representing a series of interconnected components.

Other posts

Part 2