Friday, March 6, 2009

BCD and Binary Conversions

This article is to demonstrate a technique in converting from a standard unsigned integer and into a binary number. Although, this process is rarely complicated, there does rise the occasion where one does need an alternative method.

The current method usually relies on standard libraries or a simple mathematical process. Hexadecimal is converted easily to decimal by multiplying each digit by a power of 16 and adding the results.

However
, large numbers can easily surpass the registers that Intel has given us to with. This renders the provided multiplication and division built in functions unusable.

The first solution many get is to replicate multiplication and division by hand.
                   _25_
ie: 105 / 5 = 5 )105

10
5
This solution is carried out by placing integers into an array and treating the entire process as a series of subtraction. This process gets the jobs done but it negligent of space considering that each digit is represent by 8-bits. The number is therefore in BCD (Binary Coded Decimal).

A BCD is simply every digit converted into its binary equivalent and concatenated. However, the numbers do not actually represent the number in binary.

ie: 765 = 0x2FD = 0b1011111101 = BCDx0111 0110 0101

In this example the binary is two digits short than the BCD, but the advantages of binary can be seen as the numbers get larger. The problems compile trying to add or subtract BCD.

ie 765 = BCDx0111 0110 0101
+426 = BCDx0100 0010 0110
1191 = BCDx1011 1000 1011
11 9 11
6 6

1 0001 1001 0001
1 1 9 1
However, BCD can only represent up to decimal 9, therefore any number greater than five must be added by six. This creates an addition nightmare, and creates tremendous overhead with carrying additional bits. Imagine this process when carrying out division "by hand" method.

If BCD was converted into binary, this would be no problem.

765 = 0b1011111101
426 = 0b0110101010
1191=0b10010100111
The easiest method is a technique I found on hardware conversion from Hex to BCD. This articles technique solves the problem by easily converting the largest set of number to binary without relying on multiplication or division.

Shift and Add-3 Algorithm

  1. Shift the binary number left one bit.
  2. If 8 shifts have taken place, the BCD number is in the Hundreds, Tens, and Units column.
  3. If the binary value in any of the BCD columns is 5 or greater, add 3 to that value in that BCD column.
  4. Go to 1.


Demonstration on Hex to BCD: 0xE


Demonstration on Hex to BCD: 0xFF

The reverse is similar.
  1. Shift bit right.
  2. If bit is greater than 5, subtract three.
  3. Repeat.
The remaining problem is converting unsigned ints to compressed BCD. An unsigned int would be stored such as 6 = 0x0000 0000 0000 0110. The solution is to shift the bits into the unsigned int four bits at a time. Thus having a an array of compressed numbers within unsigned ints. Thus you can think of your array as looking at a long number in binary format through blinders. Think of 16bit real mode, it can only access 64k of memory at a time. Thus you would be accessing your array one "word" at a time.

References:

http://www.engr.udayton.edu/faculty/jloomis/ece314/notes/devices/binary_to_BCD/bin_to_BCD.html


No comments:

Post a Comment