How a CPU Adds Decimal Numbers
Date: 10/22/2000 at 17:31:08 From: Farina Subject: 8-bit CPU Hi, Dr. Math. Can you help me? How does an 8-bit CPU add up two four-digit numbers and why does it take four operations to do so? Please explain.
Date: 10/23/2000 at 14:00:01 From: Doctor TWE Subject: Re: 8-bit CPU Hi Farina - thanks for writing to Dr. Math. Are you referring to 4-digit _decimal_ numbers? I'll assume that the numbers are stored in normal Binary Coded Decimal (BCD), and that you want the result in BCD as well. (Note that there are other forms of Binary Coded Decimal, like Excess-3 code, 2'421 code, or BCD Gray code, but the most commonly used form is 8421 BCD, called normal BCD or simply BCD.) First, let me briefly explain BCD. In BCD, each digit of a decimal number is represented by a 4-bit value (similar to the way hexadecimal digits are represented by 4-bit groups in "pure" binary). Since decimal only has the digits 0 through 9, only the following values are valid "4-bit groups" in BCD: DEC BCD DEC BCD 0 0000 5 0101 1 0001 6 0110 2 0010 7 0111 3 0011 8 1000 4 0100 9 1001 The combinations 1010, 1011, 1100, 1101, 1110, and 1111 are invalid because they don't add up to a decimal digit. Since each decimal digit requires 4 BCD bits, we need 16 bits to represent a 4-digit decimal value. Your CPU, however, can only work with 8 bits at a time. So we'll need to break up the numbers into two parts (bytes) and work with one byte at a time. Let's call the bytes (or the registers where the bytes are stored) A1 and A0 for the first number - with A1 being the more significant byte (MSB) and A0 being the less significant (LSB.) Let's call the bytes B1 and B0 for the second number - again letting B1 be the more significant byte and B0 the less significant. For example, let's say we want to add the numbers: 2483 + 1795 ------ The 2483 would be represented as 0010 0100 1000 0011 (I'll put spaces in between each group of 4 bits for readability) and so: A1 = 0010 0100 A0 = 1000 0011 The 1795 would be represented as 0001 0111 1001 0101 and so: B1 = 0001 0111 B0 = 1001 0101 When adding large numbers with pencil and paper, we start with the least significant digits (the units place) and work our way from right to left. Similarly, our CPU will begin with the LSBs and work over to the MSBs. First we'll add the LSBs; A0 + B0: 1 111 <- carry bits 1000 0011 + 1001 0101 ------------ 1 0001 1000 Note that the CPU will do a straight binary addition. The answer is 0001 1000 (18 decimal) with a carry-out of 1. The carry-out is stored as the "C-flag" in a register, usually called the Condition Code Register (CCR) or Status Register (SR), depending on the CPU's manufacturer. Of course, this answer is wrong: 83 + 95 = 178, not 118. Why did it get the wrong result? Because when it added the 8 and the 9 in the tens digit, it got 17 and carried 16 of them into the carry-out. (This is because it did the addition in pure binary.) It should have only carried 10, not 16, into the carry out, so to compensate, we'll add 6 back into the tens digit (0110 0000 in BCD), like this: 1 111 1000 0011 + 1001 0101 ------------ 1 0001 1000 + 0110 0000 ------------ 1 0111 1000 That's better. Let's store that as S0. Now the MSBs. We'll add A1 + B1: _____ Carry-over from the LSBs (in the C-flag) / v 1111 0010 0100 + 0001 0111 ----------- 0011 1100 This time, we got the answer 0011 1100, but that doesn't make sense in BCD (1100 is an invalid 4-bit group in BCD.) Why? Because again the CPU did the addition in pure binary. When it added 4 + 7 + 1 it got 12 and represented it in binary as 1100. But for BCD it should have carried 10 of them over to the tens digit and only kept 0010 (2 in decimal). To "force" the half-carry (i.e. the carry from the 4th bit to the 5th), we'll add 6 to the units digit (0000 0110 in BCD) to make the group of 10 that should have been carried a group of 16 that the CPU will carry: 1111 0010 0100 + 0001 0111 ----------- 0011 1100 + 0000 0110 ----------- 0100 0010 Let's store that as S1. Now we have our answer in S1 and S0: 0100 0010 0111 1000, or 4278 decimal. How do we know if and when to use "fudge factors" like the 0110 0000 and 0000 0110 that we used here? Most CPUs have either a "BCD Mode" that will automatically determine the proper fudge factor and add it after every ADD (or ADC - Add with Carry) operation, or they have a special instruction like DAA (Decimal Adjust Accumulator). Here are the rules the CPU uses when determining what "fudge factor" to add: (The H is the half-carry flag and the C is the carry-out flag.) 1. If H = 1 or the last 4 bits > 1001, add 0000 0110 2. If C = 1 of the first 4 bits > 1001, add 0110 0000 Note that both can occur (thus adding 0110 0110), and the first step can cause the second to occur - that's why they must be tested sequentially. Sometimes no adjustment is necessary. Here's a bit of pseudocode that adds two 4-digit BCD values. A1, A0, B1 and B0 are registers that are storing the inputs as defined above, and S1 and S0 are registers that are storing the outputs also as defined above: : LDA A0 ; Load accumulator with LSB of addend ADD B0 ; Add LSB of augend to accumulator DAA ; Add "fudge factor" to adjust result to BCD STA S0 ; Store LSB of sum LDA A1 ; Load accumulator with MSB of addend ADC B1 ; Add MSB of augend to accumulator with carry from LSB DAA ; Add "fudge factor" to adjust result to BCD STA S1 ; Store MSB of sum : I hope this helps. If you have any more questions, write back. - Doctor TWE, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.