From Binary To BCD…And Back Again (Part 2)
In the previous post I described the algorithm for converting a binary number to binary-coded-decimal (BCD). In this post I’ll describe an algorithm for doing the reverse; converting a BCD number to binary.
The algorithm is based on repeated division and is best explained by example. Begin with a decimal number and divide by 2. The remainder becomes the high order bit in the binary number, the quotient carries forward. Repeat the process for the required number of bits. The table below shows an example for the decimal number 204.
| Quotient | Remainder | Binary Number |
|---|---|---|
| 204 | ||
| 102 | 0 | 0 |
| 51 | 0 | 00 |
| 25 | 1 | 100 |
| 12 | 1 | 1100 |
| 6 | 0 | 01100 |
| 3 | 0 | 001100 |
| 1 | 1 | 1001100 |
| 0 | 1 | 11001100 |
For a BCD number start at the most significant digit (MSD). Shift right to divide by two, moving the least-significant bit (LSB) into the carry. Since the remainder after dividing by 2 is the LSB, add 10 to the next significant digit if the carry is set and repeat. Limiting ourselves to number in the range from 0 – 255 (8 bits), in PIC assembly language with 8-bit registers this would look like:
; Load the registers
movlw d'2 ; load BCD digit 2
movwf DEC2_REGISTER ;
movlw d'0 ; load BCD digit 1
movwf DEC1_REGISTER ;
movsw d'4 ; load BCD digit 0
movwf DEC0_REGISTER ;
clrf BIN_REGISTER ; clear the binary register
movlw d'8 ; load the counter
movwf COUNTER ;
; Perform the division
DIVIDE
DIGIT2
bcf status, c ; clear the carry
rrf DEC2_REGISTER,1 ; rotate digit to the right, putting LSB into carry
btfss status, c ; skip if there is a remainder
goto DIGIT1 ; jump to the next digit
movf DEC1_REGISTER,0 ; get the next digit
addlw d'10 ; add 10
movwf DEC1_REGISTER ; move it back
DIGIT1
bcf status, c ; clear the carry
rrf DEC1_REGISTER,1 ; rotate digit to the right, putting LSB into carry
btfss status, c ; skip if there is a remainder
goto DIGIT0 ; jump to the next digit
movwf DEC0_REGISTER,0 ; get the next digit
addlw d'10 ; add 10
movwf DEC0_REGISTER ; move it back
DIGIT0
bcf status, c ; clear the carry
rrf DEC0_REGISTER,1 ; rotate the digit to the right, putting LSB into carry
; Update the counter.
BINARY
rrf BIN_REGISTER,1 ; rotate remainder into the binary register
decfsz COUNTER, 1 ; decrement the counter
goto DIVIDE ; back to the top of the loop
...
Note that as written, this will not work with 4-bit BCD numbers because adding 10 to a digit could potentially move it outside the range of 0 – 15. However, like the Binary to BCD algorithm, there is an optimization to be performed that will allow it work with 4-digit BCD.
Instead of checking the carry flag and adding 10 before shifting the next digit, perform all the shifts up front. As mentioned previously, the remainder of division by 2 is simply the register’s least-significant bit (LSB), which, after the shift, becomes the MSB of the next digit’s register. After performing the shifts, check each register’s MSB. If it’s set there was a carry. Clear the MSB and add 5 (because we’ve already done the division via the shift, it’s 5 instead of 10). The code becomes:
; Load the registers
movlw d'2 ; load decimal digit 2
movwf DEC2_REGISTER ;
movlw d'0 ; load decimal digit 1
movwf DEC1_REGISTER ;
movsw d'4 ; load decimal digit 0
movwf DEC2_REGISTER ;
clrf BIN_REGISTER ; clear the binary register
movlw d'8 ; load the counter
movwf COUNTER ;
; Perform the division
; Shift the registers
DIVIDE
bcf status,c ; clear the carry
rrf DEC2_REGISTER,1 ; rotate digit to the right
rrf DEC1_REGISTER,1 ; rotate digit to the right
rrf DEC0_REGISTER,1 ; rotate digit to the right
rrf BIN_REGISTER,1 ; rotate binary number to the right
; Clear the MSB and add 5 if MSB is set.
; You don't have to check digit 2 because it will always have
; been zero shifted into its MSB.
DIGIT1
movwf DEC1_REGISTER,0 ; move digit to the acc
btfss DEC1_REGISTER,7 ; skip if MSB is set
goto DIGIT0 ; jump to the next digit
andlw h'7f ; clear the MSB
addlw d'5 ; add 5
movwf DEC1_REGISTER ; move the digit back
DIGIT0
movwf DEC0_REGISTER,0 ; move digit to the acc
btfss DEC0_REGISTER,7 ; skip if MSB is set
goto BINARY
andlw h'7f ; clear the MSB
addlw d'5 ; add 5
movwf DEC0_REGISTER ; move the digit back
; Update the counter.
BINARY
decfsz COUNTER, 1 ; decrement the counter
goto DIVIDE ; back to the top of the loop
...
As written this code is for 8 bit registers. However, the algorithm is compatible with 4-bit BCD since the value in any of the 4-bit registers will always be in the range from 0 – 15.
If you think about it, this algorithm nicely complements the binary-to-BCD algorithm. For binary-to-BCD you subtract 5 before setting a register’s MSB. For this case, you clear the MSB and add 5. Makes it easy to remember too.
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.
Fixing CH340 Problems On A NodeMCU V3 Board
A while back I bought a couple of NodeMCU V3 boards via EBay. They’ve sat among my “projects waiting to happen” until I pulled them out this past week intending to install MicroPython on one of them. However, when I connected the boards to my Linux laptop’s USB port they weren’t recognized. This board uses the CH340G USB-to-UART chip and when I ran dmesg I saw the errors shown below:
This is not an uncommon problem if the number of people posting questions with similar errors is any indication. Some saw it as a software driver problem. Some indicated changing to a different USB cable or using a powered hub fixed the problem. I believed it was a hardware problem since removing and reinserting the USB cable would occasionally result in different errors.
This was confirmed when I noticed the laptop would recognize the CH340G with no errors if I flexed the board’s microUSB connector while pressing the reset button. I suspect the problem was caused by a solder bridge on the board below the USB connector or a problem in the connector itself but ultimately the question was, how to fix it?
First I tried to reflow the connector’s solder using a hot air gun. When that didn’t work I decided to replace the connector with something a bit more substantial.
The result is shown below. The microUSB connector was removed and replaced with a 4 pin header attached to the board using super glue. The header pins were connected to appropriate locations on the NodeMCU board using wire-wrap wire as shown in the photo and specified in the accompanying list.
| Header Pin | Name | USB Wire Color | Board Connection |
|---|---|---|---|
| 1 | USB GND | Black | AMS1117 (3.3V Reg) Pin 1 |
| 2 | USB D+ | Green | CH340G Pin 5 |
| 3 | USB D- | White | CH340G Pin 6 |
| 4 | USB 5V | Red | AMS1117 (3.3V Reg) Pin 3 |
Replacing the NodeMCU’s microUSB connector means a custom programming cable is needed for the board. That was easily accomplished by cutting the end off an old USB cable and replacing it with a 1X4 crimp connector. Now when the board is plugged in the laptop’s USB port the CH340G is recognized with no errors.
If you’re careful you may be able to just remove the existing microUSB connector and replace it with a new one. However, the board traces below the connector are tiny and pull up easily. Ultimately, it may be easier (and lesss frustrating) to go with with pin header replacement in the first place.
