THE MAGAZINE FOR COMPUTER APPLICATIONS
Circuit Cellar Online offers articles illustrating creative solutions
and unique applications through complete projects, practical
tutorials, and useful design techniques.

CHARMING ADDERS

IMPLEMENTING AN ADDER IN AN FPGA
by Ingo Cyliax

Start ı Implementing ı Adder Architecture ı Lessons Learned ı Sources and PDF

ADDER ARCHITECTURE

The first adder I designed is called a ripple adder. The carry ripples down each adder stage until it reaches the last stage. Itıs a simple adder but not efficient, especially if the word is long.

There are other adder architectures you can design with. One of these is the carry look-ahead adder. In a nutshell, this adder tries to compute the carries that are needed in later stages. However, this introduces more logic than a pure-ripple adder. A compromise is to build small-to-medium size look-ahead adder blocks and use ripple carry between the stages.

Iım going to use the following notation: C_I is the carry input for the i-th stage, A_I and B_I are the two inputs, and S_I is the sum. The first stage is easy:

S₀ = A₀ XOR B₀ XOR C₀

C1 = (A₀ ı C₀) + (B₀ ı C₀) + (A₀ ı B₀)

The second stage is:

S1 = A1 XOR B1 XOR C1

C2 = C1 ı (A1 + B1) + (A1 ı B1)

Collect the C1 term and substitute:

S1 = A1 XOR B1 XOR ((A₀ ı C₀) + (B₀ ı C₀) + (A₀ ı B₀))

C2 = ((A₀ ı C₀) + (B₀ ı C₀) + (A₀ ı B₀)) ı (A1 + B1) + (A1 ı B1)

Well, you get the idea. This gets messy fast. Figure 4 shows a 4-bit carry look-ahead adder implementation. Itıs easy to get lost. I made two or three mistakes before getting it right. To build a 16-bit adder, I chained four of the 4-bit adders together, as seen in Figure 5.

(click here for figure)	Figure 4ıA 4-bit carry look-ahead adder. The strategy is to generate the carry at each stage in parallel directly dependent on the inputs.
(click here for figure)	Figure 5ıA 16-bit adder built up from 4-bit carry look-ahead adder cells. Itıs a compromise to use small carry look-ahead adders and then wire them up as a ripple carry between the stages.

Implementing a 16-bit carry look-ahead in the same part, I get 36 CLBs, and the design runs at 26.2 MHz. As expected, itıs bigger but only a little faster. It turns out that, for 4-bit carry look-ahead adders, much of the logic gets absorbed and packed in four input LUTs similar to the ripple carry adder implementation and, therefore, doesnıt buy you much over a ripple adder. The effect would have been greater if I built an 8-bit carry look-ahead section instead of the 4-bit sections. However, an 8-bit carry look-ahead adder is huge and difficult to enter by hand without making some mistakes.

THE SERIAL ADDER

As I have pointed out in earlier articles, designing with FPGAs opens many interesting design permutations. Letıs look at what it would take to implement a serial adder (see Figure 6). FPGAs have fast register architectures, and all the logic required fits into a single CLB. There is a register that stores the carry, so instead of chaining the carry from stage to stage, the carry stays in one place and data is shifted through each stage.

(click here for figure)

Figure 6ıA single bit serial adder can be constructed efficiently, especially if the operands are already in bit serial format. Single bit adders also run fast.

When I implemented this design, I got 25 CLBs that run at 98 MHz. The CLBs contain the shift registers for the input and output, but only one CLB actually contains adder logic. This is the one that is associated with the carry register. At 98 MHz, a 16-bit adder will effectively run at about 6 MHz, however, itıs small. If the data is already in serial form (LSB first), the input shift registers can be eliminated, and the adder will implement in 2 CLBs and run at over 200 MHz.

It took me the better part of two days to implement and test these adders from scratch, and the results havenıt been spectacular. Maybe I should have used the 16-bit adder in the library.

The design implements in 25 CLBs, running at 78.5 MHz! Howıs this possible? The adder circuit in the library uses fast carry chains that are a feature in the architecture. Each adjacent CLB has a special connection with logic to generate carry for the next stage and use the carry from the previous stage (see Figure 7). Clearly, this is the way to go. Each adder bit in the schematic has a special configuration block symbol that is used to configure the CLB, telling it where to get its inputs from and how to route the output. Also, special blocks are used to place the CLBs. They will be placed into columns, so the carry chain can be used.

(click here for figure)

Figure 7ıThe implementation of the 16-bit fast adders from the vendor library. These adders use a fast carry chain, which is a feature of the architecture, and directives to floor-plan the CLBs so they line up in columns.

PREVIOUS • NEXT