4-bit Adder

The joy of the FullAdder is that they can be chained together to add numbers of any size.

We define a module Adder4, which can add together any two 4-bit numbers:

pub mod Adder4 {
    incoming a : Word[4]
    incoming b : Word[4]
    incoming carry_in : Bit

    outgoing sum : Word[4] dependson a, b, carry_in
    outgoing carry_out : Bit dependson a, b, carry_in

    mod fulladder_0 of FullAdder {
        it.a := a[0]
        it.b := b[0]
        it.carry_in := carry_in
    }

    mod fulladder_1 of FullAdder {
        it.a := a[1]
        it.b := b[1]
        it.carry_in := fulladder_0.carry_out
    }

    mod fulladder_2 of FullAdder {
        it.a := a[2]
        it.b := b[2]
        it.carry_in := fulladder_1.carry_out
    }

    mod fulladder_3 of FullAdder {
        it.a := a[3]
        it.b := b[3]
        it.carry_in := fulladder_2.carry_out
        carry_out := it.carry_out
    }

    sum := word(
        fulladder_3.sum,
        fulladder_2.sum,
        fulladder_1.sum,
        fulladder_0.sum,
    )
}

Note

This is the last in a series of three modules which appear in full in Complete Adder Example.

A quick survey of the code shows us that there are three incoming ports: a b and carry_in, and two outgoing ports: sum and carry_out.

However, this time, a b and sum are all Word[4], which means we can pass any 4-bit number. This allows us to add any two numbers between 0 and 15.

The body consists of four FullAdder submodules. But let’s not get ahead of ourselves. Let’s take a closer look.

Indexing

As we look at our first submodule, fulladder_0, find ourselves in a pickle: Both a and b have type Word[4]. But the inputs to FullAdder (also named a and b) have type Bit. How do we connect them together?

The answer is we need to decompose a and b into their constituent bits. The syntax a[0] means “from the word a, extract bit number 0”.

When adding numbers by hand, we line up the digits of the two numbers vertically. In the same way, in Adder4, we line up corresponding pairs of bits:

a[0] and b[0]
a[1] and b[1]
a[2] and b[2]
a[3] and b[3]

Consult this slightly messy diagram for an idea of what goes where:

Note

It’s important to note that indexing like this only works when the index is a constant. If you need dynamic indexing, Virdant provides a different syntax: a[dyn i].

Dynamic indexing is more expensive in terms of hardware. And because it can otherwise lead to undefined behavior, Virdant restricts it to only work for Word[n] where n is a power of 2.

Chaining Full Adders

The operation of Adder4 is based on the four FullAdder which are all chained together.

mod fulladder_2 of FullAdder {
    it.a := a[2]
    it.b := b[2]
    it.carry_in := fulladder_1.carry_out
}

Each FullAdder takes the corresponding pair of bits from a and b. Its carry_in is the carry_out of the previous FullAdder. (The carry_in of the first, of course, is the incoming port carry_in).

Each FullAdder represents a column of the addition. The reason you need a chain is exactly because the “carry” bit carries over to the next column.

Concatenation

The opposite of indexing is concatenation. This is used on the last line of Adder4 to produce the final result.

Virdant uses the syntax word(a, ..., z) to concatenate the values a b c … z together. You can concatenate as many values as you like, and the values you concatenate can be Bits or Words.

The result of word(a, ..., z) will be a Word type. And its size will be computed based on the sum of the sizes of each of the arguments.

For example, because each of the arguments is of type Bit, the multi-line expression

word(
    fulladder_3.sum,
    fulladder_2.sum,
    fulladder_1.sum,
    fulladder_0.sum,
)

is Word[4]. This is good, since it’s being assigned to out, which is also Word[4].

About Adders

The technical name for this style of adder is called a ripple-carry adder. It is the simplest adder circuit.

It’s good to understand that adders are relatively expensive pieces of hardware. The HalfAdder has 2 gates: an AND gate and an XOR gate. That means the FullAdder has 5: two copies of the HalfAdder gives 4 gates, plus an additional OR gate. This brings the total cost of the Adder4 to 4x5 = 20 gates.

If you wanted to build an Adder64, it would require 64 FullAdders, and thus 64x5 = 320 gates(!).

Additionally, ripple carry adders can be a bit slow. Think of it like this: to add two 4-bit numbers, the carry_in has to travel through all four FullAdders. (If you work through carefully, it travels through 8 gates. And each of those takes time.

If you want to do 64-bit addition, though, that’s 64 FullAdders, and thus 128 gates it has to pass through. On an FPGA, this could easily cap your maximum clock frequency.

There are other kinds of adder circuits. The next most famous one is called the carry lookahead adder. It does addition much faster, but at a cost of a higher gate count.

Waveform

I’ll leave this waveform for you to look over.