Radix Conversion: Binary to Decimal Conversions.

Design File DF04, March, 2006

Radix conversion between binary and Binary Coded Decimal formats is not that complicated. Even simple microprocessor with rudimentary arithmetic capability can easily convert between binary and BCD formats.

Notes:

1. Radix Conversion: Binary to Decimal Conversions..

Microprocessors are really neat. You can program them to do all kinds of menial tasks and they patiently execute the task with no complaints, hour after hour, day after day. All they ask in return is a little power - which is easy to supply, and a set of clear instructions - therein lies the problem!

The microprocessor is optimized for speed - not conversation. It speaks a language called binary. We humans on the other hand are thoroughly decimal based, using binary as a communication medium borders on an unnatural act!

We can use a compromise called Binary Coded Decimal or BCD for short. This is simply the digits 0 to 9, represented by four binary bits 0000 - 1001.

Packed BCD is simply two digits per byte. To the microprocessor, a BCD number "looks" like a binary number, and can be manipulated like a binary number. The only problem is that a BCD number is base-10, not base-2, and the same bit patterns represent different number values because they have different radices.

Want we ideally want to do is to input data to the microprocessor in binary coded decimal format and have the microprocessor convert the data into binary format, do its calculations, and convert the results back into binary coded decimal format for us to read.

Actually, radix conversion between binary and decimal is not that complicated. In his book, "Semi-numerical Algorithms," Knuth outlines four of methods of converting between radices, two specifically for integer conversion which we are interested in.

1.1 Method One

Assume we are going from radix b to radix B. Method one is Division by B (using radix-b arithmetic).

"Given an integer number u, we can obtain its rad-B representation
(U_M ... U₁ U₀)B

as follows:

U0 = umodB
U1 = [u/B]modB
U2 = [[u/B]/B]modB
....

stopping when

[...[[u/B]/B].../B] = 0"

"Mod" means the remainder after a division. For example 2 divides into 5 two times with a remainder of 1, so 5 mod 2 = 1

Yikes!, what does that mean? Actually, it is really simple, and best explained by an example.

Suppose we have the decimal Number 93 (b = 10) we want to convert to binary (B = 2). Since b = 10, we use decimal arithmetic.

First we take the whole number we want to convert and divide that number by the base we want to convert to using the radix and the aritmetic of the base of the number we are converting from.

The result is a quotient and a remainder. The remainder is the first digit, or least significant digit of the equivalent number in the new base.

We successively repeat the division operation on the quotient, until the we get a final quotient of zero with a remainder. The remainder is the most significant digit of the equivalent number in the new base.

The entire process is illustrated on the example shown below.

U0                          93 mod 2 = 1
U1                      46 mod 2 = 0
U2                 23 mod 2 = 1
U3             11 mod 2 = 1
U4           5 mod 2 = 1
U5       2 mod 2 = 0
U6   1 mod 2 = 1
U7 0 (stop)
------------------------------------
result =            1  0  1  1  1  0  1

Converting back is a bit tricker, since we must convert using "b" arithmetic, we need to use the binary representation of decimal numbers ( 10 in binary is 1010, 9 in binary is 1001, 3 in binary on 0011), and do our arithmetic in binary.

U0            1011101 mod 1010 = 0011 ( = 3 decimal)
U1         1001 mod 1010 = 1001 ( = 9 decimal)
U3       0 (stop)
---------------------------------
The result is:                 1001 0011 ( = 93 decimal)

The result is in packed BCD, which is a binary representation of a decimal number.

1.2 Method Two

The second method of radix conversion is Multiplication by b (using radix-B arithmetic)

"If u has the radix-b representation

(u_m ... u₁u₀)b

we can use radix-B arithmetic to evaluate the polynomial

u_mb^m + ... +u_mb + u_m = u

in the form

((..(u_mb + u_m-1)b + ... )b + u)b + u₀ "

Yikes again! Actually, this is as simple as the above method. Let me illustrate by an example again.

Suppose we have the binary Number 1011101 (b = 2) we want to convert to decimal (B = 10). Since B = 10, we use decimal arithmetic. First we notice that there are 7 digits.

So if the polynomial is in the form of

u_m + u_m-1 + ... u₀

m must be 6.

u6             1 * 2 * 2 * 2 * 2 * 2 * 2 = 64
u5             + 0 * 2 * 2 * 2 * 2 * 2 = 0
u4             + 1 * 2 * 2 * 2 * 2 = 16
u3             + 1 * 2 * 2 * 2 = 8
u2             + 1 * 2 * 2 = 4
u1             + 0 * 2 = 0
u0             + 1 = 1
------------------------
                    = 93

And converting back to binary since B is 2, we use binary arithmetic:(10 in binary is 1010, 93 in BCD is 10010011)

u1    1001 * 1010 = 1011010
u0                           + 0011
                       --------------------
result =                 1011101

In both cases, it looks like there is going to a lot of adding, dividing and multiplying required. No problem, let's let the microprocessor do it!

2.0 Microprocessor Binary to Binary Coded Decimal Conversions

If you are using a typical eight bit micro, it most likely either does not have multiply or divide hardware, or if it does, it is probably limited to 8 or 16 bits which are not much use if you need say 32 bit accuracy. And of course, being lazy, we want to enter all data in decimal format. We expect the microprocessor to handle all the internal packing and unpacking of the data in binary coded decimal format (BCD).

Binary multiplication and division is pretty simple - it just a left or right shift respectively. These are things any microprocessor can handle easily. The problem for the microprocessor is decimal arithmetic which is not native to the language of the device. However, we can simulate decimal arithmetic which a couple of binary operations.

2.1 Microprocessor Binary to Binary Coded Decimal Conversion

First let's look at binary to binary coded decimal conversion.

To convert binary to BCD, we will use method 2. To do this we need to simulate decimal arithmetic in binary. We can do this first by representing decimal data as PACKED BCD. In binary, four bits of data can encode the numbers 0 - 15. Binary coded decimal, or BCD is simply using four bits of data to represent the numbers 0 - 9 or the decimal digits only. Packed BCD is to store two decimal digits per byte.

Multiplying a BCD number by 2 is just like multiplying a binary number by 2, with the exception that the result for any digit must not exceed 9. If it does we must adjust it by adding 6 to it, then adding any resultant carry to the next digit. We can use a simple algorithm to test this:

digit = digit shifted left by one
test = digit + 6
if carry,
    result = test, add carry to next digit
else
    result = digit

Alternatively, before shifting, add 3 to the digit. If the value is less than 7, no correction will be need, so use the original digit. If the result is greater, keep the correction, when multiplied by 2, it will give the correct result.

test = digit + 3
if test < 8
    digit = digit
else
    digit = test
result = digit shifted left by one

The advantage is this method is that the following shift operation will automatically add the carry to the next digit. This is an important consideration if we are working with large numbers, we only need to work on individual digits and not be concerned with propagating a carry to the top of the entire digit string.

Table 1 shows the conversion process step by step to convert 1011101 binary data to its BCD equivalent, 93 decimal. One thing should be noted, the shift of the mod result bit into the rightmost character of the result IS the add for that step.

2.1 Microprocessor Binary Coded Decimal to Binary Conversion

Now let's look at Binary Coded Decimal to Binary Conversion.

Now that we have Binary to Decimal (BCD) conversion done, let's look at converting BCD to binary. Once again, for a simple microprocessor, the best conversion method is method two. The only catch here is we need to simulate a multiply by 10 using binary arithmetic.

Multiplying by 10 can be done as follows:

result = ((digit*2)*2)*2) + digit*2

as an algorithm:

resultx2 = digit shifted left by one
resultx4 = resultx2 shifted left by one
resultx8 = resultx4 shifted left by one

resultx10 = resultx8 + resultx2

Table 2 shows the conversion process step by step to convert 993 BCD (100110010011)data to its binary equivalent, 1111100001 decimal.

Even the simplest microprocessors can shift and add. Binary to binary coded decimal conversions should not present too much problem. In addition, the conversion process is very repetitive and deterministic. It lends itself very well to a compact implementation.

3.0 Some real Atmel AVR source code.

If the reader is interested in some working Atmel AVR code examples, at the Atmel website http://www.atmel.com/dyn/resources/prod_documents/doc0938.pdf check out AP note AVR204.

This is a register based 16 bit example. It is a quick implementation, register intensive, and not easily expanded to larger data sizes.

For a 32 bit, expandable memory based solution, at the McGourty Associates website check out radix.zip This is a 32 bit solution. It is not as fast as above but is easily expandable to larger data sizes if needed.

Conclusion

While the native language of the microprocessor may be binary, Binary Code Decimal (BCD) data representation is a better medium for Human Interface Design. Even a simple microprocessor with rudimentary arithmetic capability can easily convert between binary and BCD formats.