# From Binary To BCD…And Back Again (Part 1)

Binary coded decimal (BCD) is a way of representing numbers in a computer as decimal rather than binary digits. Most commonly 4 bits are used to represent each digit since 4 bits can contain the numbers 0-9 and it allows two digits to be packed into a single byte.

For those who still enjoy assembly language programming the conversion from binary to BCD is not an uncommon operation. The algorithm is well known and is usually referred to as Add 3 – Shift.

While I’ve seen the algorithm described in many places, I haven’t yet run across an explanation of how it’s derived. Turns out it’s not very difficult.

**The Basic Algorithm**

The best description I’ve run across for this algorithm is “you calculate the value of the binary number but do the calculations using decimal values.”

You may recall that a binary number can be represented as a polynomial in the form:

In PIC assembly language, for an 8 bit value and a binary accumulator, the code to calculate this value woud look like:

; Load the registers movlw d'204 ; load the binary register movwf BIN_REGISTER ; clrf ACC_REGISTER ; clear the result accumulator movlw d'8 ; load the counter movwf COUNTER ; ; Rotate bits ROTATE rlf BIN_REGISTER, 1 ; rotate number to the left, ; putting hi bit into carry rlf ACC_REGISTER, 1 ; rotate carry into accumulator low bit decfsz COUNTER, 1 ; decrement the counter goto ROTATE ; back to the top of the loop END ...

For a decimal accumulator, the code is similar but you need a separate register for each digit. You shift the individual digits to the left to multiply by 2, then check for carrys. If a digit it greater than 10, subtract 10 and add 1 to the next higher digit.

; Load the registers movlw d'204 ; load the binary register movwf BIN_REGISTER ; clrf DEC0_REGISTER ; clear decimal digit 0 clrf DEC1_REGISTER ; clear decimal digit 1 clrf DEC2_REGISTER ; clear decimal digit 2 movlw d'8 ; load the counter ; Rotate bits ROTATE rlf BIN_REGISTER, 1 ; rotate number to the left, ; putting hi bit into carry rlf DEC0_REGISTER, 1; rotate decimal digit 0 rlf DEC1_REGISTER, 1; rotate decimal digit 1 rlf DEC2_REGISTER, 1; rotate decimal digit 2 DIGIT0 movf DEC0_REGISTER, 0; move decimal digit to acc addlw d'246 ; is it >= 10? btfss status, c ; skip if >= 10 goto DIGIT1 ; jump to next digit incf DEC1_REGISTER ; increment next digit movwf DEC0_REGISTER ; move value back to the register DIGIT1 movf DEC1_REGISTER, 0; move decimal digit to acc addlw d'246 ; is it >= 10? btfss status, c ; skip if >= 10 goto DIGIT2 ; jump to the next digit incf DEC2_REGISTER ; increment next digit movwf DEC1_REGISTER ; move value back to the register DIGIT2 decfsz COUNTER, 1 ; decrement the counter goto ROTATE ; back to the top of the loop END ...

You could stop here but there are some optimizations that can be done. For example, we know that any accumulator holding a digit of 5 or greater will have a carry once it’s multiplied by 2. To take advantage of this, check the value of each digit. If it’s 5 or greater set that register’s most significant bit (MSB). When you perform the shift, that flag will rotate into the carry and the carry flag from the previous digit will rotate into the least significant bit (LSB). This same trick can be used to shift the MSB of the original binary value into the LSB of the lowest decimal digit. Making this optimization, the code becomes:

; Load the registers movlw d'204 ; load the binary register movwf BIN_REGISTER ; clrf DEC0_REGISTER ; clear decimal digit 0 clrf DEC1_REGISTER ; clear decimal digit 1 clrf DEC2_REGISTER ; clear decimal digit 2 movlw d'8 ; load the counter ; Set the flag bits ROTATE movf DEC0_REGISTER, 0; move decimal digit to acc addlw d'251 ; is it >= 5? btfsc status, c ; skip if < 5 bsf DEC0_REGISTER, 7; set the MSB movf DEC1_REGISTER, 0; move decimal digit to acc addlw d'251 ; is it >= 5? btfsc status, c ; skip if < 5 bsf DEC1_REGISTER, 7; set the MSB ; Rotate the bits rlf BIN_REGISTER, 1 ; rotate number to the left, ; putting hi bit into carry rlf DEC0_REGISTER, 1; rotate decimal digit 0 rlf DEC1_REGISTER, 1; rotate decimal digit 1 rlf DEC2_REGISTER, 1; rotate decimal digit 2 decfsz COUNTER, 1 ; decrement the counter goto ROTATE ; back to the top of the loop ; Check for digits > 10 movf DEC0_REGISTER, 0; move decimal digit to acc addlw d'246 ; is it >= 10? btfsc status, c ; skip if < 10 movwf DEC0_REGISTER ; move value back to the register movf DEC1_REGISTER, 0; move decimal digit to acc addlw d'246 ; is it >= 10? btfsc status, c ; skip if < 10 movwf DEC1_REGISTER ; move value back to the register ; Update the counter decfsz COUNTER, 1 ; decrement the counter goto ROTATE ; back to the top of the loop END ...

The next optimization is to combine the digit adjustment with setting the flag. We already said any register with a value of 5 or greater will have a carry once it’s multiplied by 2. It will also have 10 subtracted after the shift. So we’ll combine the two and, rather than subtract 10 after the shift, we’ll subtract 5 before the shift. The code becomes:

; Load the registers movlw d'204 ; load the binary register movwf BIN_REGISTER ; clrf DEC0_REGISTER ; clear decimal digit 0 clrf DEC1_REGISTER ; clear decimal digit 1 clrf DEC2_REGISTER ; clear decimal digit 2 movlw d'7 ; load the counter ; Set the flag bits ROTATE DIGIT0 movf DEC0_REGISTER, 0; move decimal digit to acc addlw d'251 ; is it >= 5? btfss status, c ; skip if >= 5 goto DIGIT1 ; jump to next digit iorlw d'128 ; set the MSB movwf DEC0_REGISTER ; move value back to register DIGIT1 movf DEC1_REGISTER, 0; move decimal digit to acc addlw d'251 ; is it >= 5? btfss status, c ; skip if >= 5 goto SHIFT_BITS ; jump to next digit iorlw d'128 ; set the MSB movwf DEC1_REGISTER ; move value back to register ; Shift the bits SHIFT_BITS rlf BIN_REGISTER, 1 ; rotate number to the left, ; putting hi bit into carry rlf DEC0_REGISTER, 1; rotate decimal digit 0 rlf DEC1_REGISTER, 1; rotate decimal digit 1 rlf DEC2_REGISTER, 1; rotate decimal digit 2 decfsz COUNTER, 1 ; decrement the counter goto ROTATE ; back to the top of the loop ; Update the counter decfsz COUNTER, 1 ; decrement the counter goto ROTATE ; back to the top of the loop END ...

So after all that, where does Add 3 – Shift come from? Each time through the loop, if a register’s value is greather than 5, 5 is subtracted and the MSB set. Setting the MSB is the same as adding 128 so we’re really adding 123.

This is for an 8 bit register. But as I mentioned at the beginning, BCD is normally done using 4 bit registers. In that case, setting the MSB is the same as adding 8. So add 8, subtract 5 (in other words, add 3) and shift.

- Posted in: Uncategorized
- Tagged: Algorithms