Building Math Hardware

(c) Copyright 2016 Coert Vonk

Parameterized Adder and Subtractor in Verilog

The inquiry “How do computers do Math?” introduced the carry-propagate adder and the borrow-propagate subtractor. Here we will recapitulate and implement these using Verilog HDL.\(\)

Carry-propagate adder

The full adder (fa) forms the basic building block. This full adder adds two 1-bit values a and b to the incoming carry (ci), and outputs a 1-bit sum (s) and a 1-bit outgoing carry (co). The circuit and Boolean equations, shown below, give the relations between these inputs and outputs.
1-bit full adder
$$\begin{aligned} s&=a \oplus b \oplus c_i\\ c_o&=a \cdot b + c_i \cdot (a \oplus b) \end{aligned}$$
To build a n-bit propagate-adder, we combine n fa blocks. The circuits adds the least significant bits and passes the carry on to the next bit, and so on. Combining the output bits forms the sum s. The circuit shown below gives an example of a 4-bit carry-propagate adder.
4-bit carry-propagate adder
We describe the circuit using array instantiation. In this a[] and b[] are the summands, ci[] is the in-coming carry, co[] is the out-going carry and s[] is the sum. >math_adder_fa_block fa [N-1:0] ( .a ( a ), .b ( b ), .ci ( {c[N-2:0], 1’b0} ), .s ( s[N-1:0] ), .co ( {s[N], c[N-2:0]}) ); The compiler will optimize the fa blocks with forced inputs, but most fa blocks will compile to a RTL netlist as shown below.
(c) Copyright 2016 Coert Vonk
1-bit full adder (fa) block in RTL
The 4-bit adder compiles into the daisy chained fa blocks as shown.
(c) Copyright 2016 Coert Vonk
4-bit carry-propagate adder in RTL
The complete Verilog HDL code along with the test bench and constraint files are available through GitHub for the Xilinx (Spartan-6 LX9) and Altera (Cyclone IV DE0-Nano) boards.

Results

The propagation delay \(t_{pd}\) depends on size N and the value of operands. For a given size N, adding the value 1 to an operand that contains all zeroes causes the longest propagation delay. The worst-case propagation delays for the Altera Cyclone IV on the DE0-Nano are found using the post-map Timing Analysis tool. The exact values depend on the model and speed grade of the FPGA, the silicon itself, voltage and the die temperature.
Propagation delay in propagate-carry adder
\(N\) Timing Analysis Measured
slow 85°C slow 0°C fast 0°C actual
4-bits 6.9 ns 6.2 ns 4.3 ns
8-bits 8.6 ns 7.6 ns 5.4 ns
16-bits 15.7 ns 13.9 ns 9.7 ns
27-bits 20.2 ns 18.0 ns 12.3 ns
32-bits 26.0 ns 23.2 ns 15.7 ns
42-bits 30.2 ns 26.9 ns 18.1 ns
Propagation delay in propagate-carry adder

Borrow-propagate subtractor

Similar to addition, the simplest subtraction method is borrow-propagate, as introduced in Chapter 7 of the inquiry “How do computers do Math?”. Again, we will start by building a 1-bit subtractor (fs). The inputs a and b represent the 1-bit binary numbers being added. Output d, the difference. li and lo are the incoming and outgoing borrow/loan signals. The outputs d and lo can be expressed as a function of the inputs. The difference d is an Exclusive-OR function, just as the sum was for addition.
1-bit full subtractor
$$\begin{aligned} d&=a \oplus b \oplus l_i\\ l_o&=\overline{a} \cdot b + l_i \cdot (\overline{a \oplus b}) \end{aligned}$$
To build a 4-bit subtractor we combine four of these building blocks.
4-bit borrow-propagate subtractor
The implementation of the borrow-propagate subtractor is very similar to the adder shown earlier and is left as an exercise for the reader.

Combined adder and subtractor

Another method to subtract is based around the fact that \(a – b = a + (-b)\). This allows us to build a circuit that can add or subtract. When the operation input op equals 1, it subtracts b from a, otherwise it adds the values. Under two’s complement, subtracting b is the same as adding the bit-wise complement of b and adding 1. The inputs b is negated by inverting its bits (using an XOR with signal op), and 1 is added by setting the least significant carry input to 1. We can build this a 4-bit adder/subtractor using fa blocks as shown below, where r is the result.
(c) Copyright 2016 Coert Vonk
4-bit combined adder and subtractor
Note that the circuit also includes a overflow detection for two’s complement. Overflow occurs when c2 differs from the final carry-out c3. In all these ripple carry adder and subtractors, the carry propagates from the lowest to the highest bit position. This propagation causes a delay that is linear with the number bits. The next chapter explores faster circuits.
Student at MVHS
I see education as the foundation upon which entrepreneurs are able to build innovative organizations and execute their vision for the future.

Leave a Reply

Your email address will not be published. Required fields are marked *

 

This site uses Akismet to reduce spam. Learn how your comment data is processed.