Binary Coded Decimal (BCD) 101: Part 1

Ideally, the developer would now like to simply "tag" any functions to be accelerated and then press the "Go" button. Still in our ideal world, any functions that are to be implemented on the general-purpose processor would be run through the standard compiler. Meanwhile, any functions targeted for hardware acceleration would be automatically translated into RTL, synthesized, and run through the FPGA vendor's place-and-route engines. The resulting configuration file would be automatically loaded into the FPGA. Also, the system would insert any appropriate interfaces allowing the software application to call the FPGA hardware, pass data to the hardware, and access results from the hardware.

With the exception of "tagging" the functions to be accelerated, all of this should be completely invisible to the application developer. In reality, we aren't quite there yet. However, a number of companies are very, very close. These include – but aren't limited to – Celoxica with Handel-C (www.celoxica.com), Impulse Accelerated Technologies with Impulse C (www.impulsec.com), Mitrionics with Mitrion-C (www.mitrion.com), Nallatech with DIME-C (www.nallatech.com), and SRC Computers with Carte C (www.srccomputers.com).

A decimal arithmetic IP library
So, we now have a standard for decimal arithmetic, a variety of hardware platforms, and a selection of reasonably robust tools. The only thing missing is a library of decimal arithmetic IP cores that can be accessed by the various design and development tools. In order to achieve the highest performance and quality, these cores need to be created by FPGA experts.

And so we come to the OpenFPGA group (www.openfpga.org), whose mission is to: "Promote the use of Field Programmable Gate Arrays in high level and enterprise applications by collaboratively defining, developing and sharing critical information, technologies and best practices."

One of OpenFPGA's working groups is the CoreLib team. As team leader Dan Poznanovic told the author: "This group is in charge of defining the macros / functional units / IP cores – whatever you want to call them." The idea is to create a standardized description of cores and core libraries that can be used by – and will work interchangeably across – all of the engines in the tool chain. Currently they are working on defining the standard itself; once this is completed, the team will turn its attention to defining and creating libraries of application-specific cores, and one of these libraries may well target decimal arithmetic.

In the meantime. . . the folks at Dillon Engineering have a rather cunning tool called ParaCore Architect, which facilitates the design of highly parameterized IP cores. These are the guys who used two FPGAs to implement a two-dimensional FFT algorithm that would have required more than 100 PowerPC cores (a version of this implementation was used by the folks at SETI in their ongoing search for extraterrestrial intelligence). I talked to the president of Dillon Engineering, Tom Dillon, who told me that his team are very interested in using ParaCore Architect to implement a suite of decimal IP cores. . . they are just waiting for someone to call them and ask them to do so.

Summary
So there we have it. Decimal arithmetic is not only alive and kicking, it's poised to start jumping up and down, waving its metaphorical arms around, and making a lot of noise. Hardware platforms that combine general-purpose processors with FPGA-based accelerators are a perfect fit for this type of application. Initially, the biggest end users of this technology will be in the financial and commercial markets, but I wouldn't be surprised to see it appearing in other arenas also.

There is just one small fly in the soup. How many of us actually remember the nitty-gritty details associated with decimal formats such as Binary Coded Decimal (BCD). Of course, we all remember the fundamental mapping of 0 (decimal) = 0000 (binary), 1 = 0001, 2 = 0010, up to 9 = 1001. But what about things like ten's complement representations and ten's complement arithmetic? For example, a 2-digit BCD value can span the range #00 to #99 (where we'll use the hash '#' character to indicate a BCD value). In the case of an unsigned (always positive) representation, these values can be used to represent 0 to +99 in decimal. By comparison, in the case of a signed (ten's complement) representation, these values would represent –50 to +49 in decimal.

How does this work? Well, #00 through #49 represent positive values of 0 through 49 in decimal, respectively; #50 represents –50 in decimal; #51 represents –50 + 1 = –49; #52 represents –50 + 2 = –48; and so forth up to #99, which represents –50 + 49 = –1. The point is that, if we want to play in this emerging market, we're going to have to re-learn the rules of the game (see also the Further Reading topic below. Until next time, have a good one!

Further reading and example code

• IBM fellow Mike Cowlishaw has an incredibly useful website focused on Decimal Arithmetic. Apart from a wealth of information in its own right, this site provides numerous links to other sources.
• In Part 2 of this series (coming next week), we plunge headfirst into the nitty-gritty details of using BCD (and related decimal codes) to represent – and perform calculations on – unsigned integers, signed (ten's complement) integers, and fixed- and floating-point values.
• With regard to our own simple 8-bit virtual microprocessor – the DIY Calculator – if you go to the Programs and Routines page you'll find a suite of variable-length, packed BCD subroutines (written in our simple assembly language). These include add, subtract, multiply, and divide functions, some support functions, and a simple four-function calculator program that calls these routines. (You can download a free version of the Virtual DIY Calculator from the Downloads page.)
• When he heard I was writing this article, reader Paul Butler emailed me to say that a few years ago he wrote some VHDL and started some simple experiments with BCD in FPGA targets. Paul has kindly provided these routines for us all to play with under the GNU General Public License (vhdl-bcd-package.zip). Paul does note that: "You should beware that I've done little to verify the correctness of the code, but I think it's correct enough to serve as an example."

If you have any code you'd like to share, or any websites you'd care to recommend, please email me and I'll add them to the above list.

Clive "Max" Maxfield is president of TechBites Interactive, a marketing consultancy firm specializing in high technology. Max is the author and co-author of a number of books, including Bebop to the Boolean Boogie (An Unconventional Guide to Electronics), The Design Warrior's Guide to FPGAs (Devices, Tools, and Flows), and How Computers Do Math featuring the pedagogical and phantasmagorical virtual DIY Calculator.

Widely regarded as being an expert in all aspects of computing and electronics (at least by his mother), Max was once referred to as "an industry notable" and a "semiconductor design expert" by someone famous who wasn't prompted, coerced, or remunerated in any way. Max can be reached at [email protected].