# Doing Math in FPGAs, Part 2 (BCD)

Binary coded decimal is not used as much as it once was, but we can still find it hither and yon -- mostly in applications where the data will be directly driving a display.

In my previous blog, I rambled on about some simple ways to multiply and divide by 10 in any general-purpose device, not just in an FPGA. In the comments, I was asked why in the heck I would even consider doing such a thing (as opposed to sticking with binary representations). Well, the answer is along the lines of "We are base-10 creatures living in a base-10 world." Much of what we do is related to the decimal system, so we often find the need to multiply and divide by 10. Let's figure out some ways to do it quickly and efficiently. Sometimes this can lead to things that work better in the base-2 world of numerical machines.

I think I mentioned this last time, but my quick investigation into such frivolity didn't work out for me. I didn't find an easier way to do the math. It was time for me to get back in the box and conform to binary (drat).

What to do? There are plenty of ways to represent real numbers in a binary system. I would guess the three most common are probably binary coded decimal (BCD), floating point, and fixed point. Each has its strengths and weaknesses, depending on your end game. As such, I guess this issue will feature a brief discussion of these three representations and perhaps will touch on their strengths, weaknesses, and implementations.

Let's start with BCD. It's not used as much as it once was, but we can still find it hither and yon -- mostly in applications where the data will be directly driving a display of some sort (e.g., a seven-segment display). And this, of course, is the beauty of BCD. The individual digits not only represent the decimal system with which we are naturally comfortable, but they can also be treated as separate circuits for mathematical operations. There's another positive ramification to this representation: We can represent any number exactly if we are willing to allocate the bits to do so. For instance, 0.2 in BCD is 0.2, but in binary, it might be 00110011... (in, say, a fractional-only fixed-point representation).

Let's take a quick look at just what BCD is. There are, in fact, multiple formats for this representation, but (ignoring compressed and uncompressed) the most common usage is shown in the following table.

Now that we know what it is, how do we use it? In an FPGA, I would imagine that the most likely use might be in output and input encoding to some external (human) user. With that thought in mind, let's talk about how we might go about interfacing to the outside world.

Let's consider the case where we want to do all our manipulations in binary. In this case, we will want to convert our BCD encoded data into binary. This can be achieved as illustrated below.

We start off with a binary value of zero, and then we add each BCD digit multiplied by its decimal power. Of course, those multipliers might be pretty big, but if we get clever, maybe we can use the x10 schemes we discussed in my previous blog to our advantage and replace these complex multiplications in a pipelined configuration of shifts and adds. I'll leave it you to ponder on that for a while and figure out how to do it for yourself.

Once we're done with our binary machinations/manipulations, we might want to display the result to a seven-segment display. Unfortunately, binary doesn't map directly to BCD, does it?

To translate from binary to BCD, we can employ the shift-and-add-3 algorithm:

- Left-shift the (n-bit) binary number one bit.
- If n shifts have taken place, the number has been fully expanded, so exit the algorithm.
- If the binary value of any of the BCD columns is greater than or equal to 5, add 3.
- Return to (1).

As an example, let's use the nine-bit number 100101110 (302 decimal) and run it through our algorithm.

In some cases, maybe we shouldn't even bother converting back and forth between binary and BCD. Doing math with BCD is fairly straightforward. As an added benefit, we can treat each digit as a (mostly) separate circuit. Let's talk about addition, which is performed as follows.

- Align the decimal points (if necessary).
- Starting from the right (the one's digit), add the two numbers.
- If the result is greater than 9 OR the result generates a carry, then add 6.
- Propagate the carry to the next digit.
- If all digits have been added, we're done.
- Go to (2).

As an example, let's use our algorithm to add 93 and 79. (It does not matter which order you perform the adds, so long as you check between each for the out-of-bounds condition.)

Author

KarlS01 1/21/2014 2:35:31 PM

double dz = 56.75 * 2.3; // 130.5249999999998

int dx = 5675, dy = 23;

int dw = 5675 * 23 / 1000; // 130 ,,, 3 decimal points

int ddy = dx * dy % 1000; // 525 ,,, compiler rounded up

int ddyy = dx * dy % 1000000; // 130525 ( too many zeroes)

Just as on paper, ignore thr decimal point but count decimal points to choose the divisor, divide gets integer quotient and modulo gets numerator of the fraction.

Author

tom-ii 1/21/2014 12:42:41 PM

The concerns about precision seem seem exaggerated even in financial calculations. There are rounding methods such that insignifican amounts are discarded.I've seen the repeated additions and other mathematical operations rapidly create some ugly mistakes. I once had a CS class that focused specifically on this, and ways to work within the constraints of the hardware to overcome these errors. It can take a fair amount of massaging!

Author

tom-ii 1/21/2014 12:39:55 PM

But yes, you're right that the author wants to take the10's complementof 5940 to express it as -4060.Indeed, I'm sure this is what the author meant... ;)

Author

KarlS01 1/21/2014 11:54:12 AM

The concerns about precision seem seem exaggerated even in financial calculations. There are rounding methods such that insignifican amounts are discarded.

Given all the complexity of floating point HW, Why not convert the decimal to Hex/Binary and do the algorithm as if doing decimal with pencil and paper then output the whole number part and fractional part converted from binary to decimal?

Too bad this site has no capability to attach anything technical.

Author

sa_penguin 12/28/2013 3:44:39 AM

Binary Coded Kilo: uses 10 bits, has 24 "bad" codes for 1000 "good" or 2.4% overhead. That equates to 2 bits saved in the code.

The version I saw was in a DDS [Numerically Controlled Oscillator]. 32 bits make 4,000,000,000 instead of 4,294,967,296. So a 200MHz oscillator gave a frequency strep of

precisely0.05 Hz instead of 0.046566128731 Hz [ie. subject to oscillator drift, not rounding error]Author

betajet 12/27/2013 8:37:32 PM

But yes, you're right that the author wants to take the

10's complementof 5940 to express it as -4060.Author

dferbas 12/27/2013 7:30:22 PM

I think there is a typo in the article on its 2nd page - instead of "Taking the nine's complement of 5,940 gives .." I think there should be "Taking the 109's complement of 5,940 gives..."

The nine's complement of 5940 gives 4059, to get ten's complement we need to add 1, which finally gives 4060. Also the difference to the first computation 4337 - 277 is that we need to add the +1 to the result (use 109's complement) because the result is negative.

If everybody knows this, sorry to disturb :-).

Author

KarlS01 12/27/2013 11:33:22 AM

This is for 32 bit binary. Recently they have done a lot with floating point, but I did not follow up.

I don't think decimal instructions are available in any RISC. In fact floating point often requires an optional co processor and there is a sign, exponent, mantissa to deal with.

The whole thing is such a mess that converting to hex and formatting output seems easier. Yeah, you need a computer, compiler, etc.

Author

tom-ii 12/27/2013 9:28:38 AM

I primarily hope to not prove the old addage about letting people think yu a fool, vice opening your mouth and proving you're one... But then, I freely admit that I am, indeed, an idiot, so just keep that in mind, okay?

:)

Author

tom-ii 12/27/2013 9:26:43 AM

Is multiply by 1000 done with 1000 additions and divide by 1000 done with 1000 subtractions?Well, no. I was kind of waving my hands and glossing over dirty details. Certainly one way to do it is to do repeated additions or subtractoins (you can do division via addition, as well). When you get down into the guts of the computing machinery, though, we can go about this in different ways - look at the way we do these operations by hand, and we can do things similarly in the computer.

In BCD it's a little harder, but we can do the following type of thing, where each digit has its own combinational cloud to do the multiplication:

From Wikipedia:

So let's talk about pure binary as an example. For multiplication, you can actually synthesize a 2N-bit combinational cloud to do your multiplications. Lacking that, you can build a state machine that's pretty easy, as binary is a special case. From the same Wikipedia page:

So, you can see we can do a multiply in (potentially) a lot less operations than just adding them all up.

I mentioned combinationall clouds, so let's touch on that a bit. For all possible N-bit multiplications, a truth table can be made, and a set of discrete logic implemented to perform that multiplication. I will point you to this paper for a quick overview - they show how to implement a 4-bit combinational multiplier and its complexity. The modern synthesis tools appear to be able to create a multiplier of at least 32 bits with no issue (I've not tried anything bigger), and modern FPGAs have dedicated multiplier circuits in them (or so it would seem), but I don't know how many bits wide they are.