Primary school teaches our students methods for addition, subtraction, multiplication and division. Computer hardware implements similar methods and performs them with astounding speed. This enables applications such as computer vision, process control, encryption, hearing aids, video compression to dubious practices as high-frequency trading.
This article describes how to build such hardware. In such, it is a sequel to the inquiry “How do Computers do Math?” that in chapter 7
introduced conceptual circuits using logic gates. We will model the various math operations using digital gates. Here we combine the gates into circuits and describe them using the Verilog Hardware Description Language (HDL). These Verilog HDL descriptions are compiled and mapped to a Field Programmable Gate Array (FPGA).
Working knowledge of the Verilog HDL is assumed. To learn more about Verilog HDL, I recommend the book FPGA Prototyping with Verilog Examples, an online class
or lecture slides
. To help you get up to speed with the development boards, wrote Getting Started documents for two popular Altera
We aim to study algorithms to implement the algorithms in generic VLSI, and as such do will not use the highly optimized carry chain connections present on many FPGAs.
Hail to the FPGA
Let’s take this moment to honor the virtues of the FPGA. A FPGA can do many things at the same time and still respond immediately to input events. It is generally more complicated to create and debug the same logic in a FPGA compared to a microprocessor. Because of the challenges that FPGA development poses, many systems combine FPGAs and microprocessors to get the best of both worlds. For example, to recognize objects in a video stream, one would implement the pre-processing (noise removal, normalization, edge detection) in an FPGA, but the higher-level logic on a CPU or DSP.
With a FPGA, you can put massive parallel structures in place. For example, an high-speed data stream can be distributed across the whole FPGA chip to be processed in parallel, instead of having a microprocessor deal with it sequentially.
FPGAs can accelerate machine learning algorithms, video encoding, custom algorithms, compression, indexing and cryptography. By implements a soft microprocessor as part of the FPGA it can also handle high level protocols such as handle board management, protocol bridging and security tasks. [IEEExplore
The first chapter describes the demonstration setup. Remaining chapters implement the concepts introduced in the inquiry How do Computers do Math?
- Adder (and subtractor)
- Faster adder (and subtractor)
- Faster multiplier
- Square root
The code examples were tested on an Altera “Cyclone IV E” FPGA using Quartus Prime 16.1. Earlier code iterations used a Xilinx “Spartan-6” with their ISE Design Suite. The Verilog descriptions should work equally well on other boards or environments.
For debugging, we used gate level simulation. In the real world, a DSLogic Logic Analyzer proved valuable in diagnosing problems.