Learn the double dabble, and other ins & outs of efficient base conversion.
Conversion of binary to decimal numbers is often needed in firmware. And it’s done easily enough if multiplication and division by ten are acceptable. However, these operations, especially division, may be too resource-hungry for a low cost microcontroller (MCU).
I was therefore pleased to learn about the double dabble algorithm, which converts binary to decimal efficiently; it went into my bag of tricks immediately. Still, I want to tailor it to my needs – to work with any base. To do that, I needed to know how it actually works.
The double dabble belongs to the second of two groups of algorithms (shift-adjust and adjust-shift). Both can be used to convert binary numbers to other formats. Among them, conversion to the time or angle format of HMS is especially useful. Additionally, there have been ternary (base-3)-related designs & discussions on EDN recently to which this Design Idea is applicable.
The conversion begins with a binary number:
A = 2N–1 aN–1 + … + 2n an + … + 2 a1 + a0 (1)
where a‘s are bits. N bits are needed to store the number A. The a‘s are either 0 or 1. An example number is 110110112.
The number A is defined by a sum:
A = BM pM + … + Bm pm + … + B1 p1 + p0 (2)
The constants Bm depend on the numerical system. In decimal, these are products of base constants b as follows in (3). In the definition (2), the p‘s correspond to decimal places.
b0 = 10 B1 = b0 = 10
b1 = 10 B2 = b1 B1 = 100
bm–1 = 10 Bm = bm–1 Bm–1 = 10m (3)
The decimal system is not the only interesting system. For example, time, in base 60. Now, p0, p1, and p2 are seconds, minutes, and hours respectively.
b0 = 60 B1 = b0 = 60
b1 = 60 B2 = b1 B1 = 3600 (4)
Except on mechanical clock dials, time is displayed by Arabic numerals that end at 9, which is far less than 59. Since it is not necessary that all b‘s in the (2) be equal, the solution is simple. To write time with Arabic numerals, the next numerical system (5) is used. Places p0 and p1 together are seconds in the decimal system, p2 and p3 are minutes, and p4 shows hours.
b0 = 10 B1 = b0 = 10
b1 = 6 B2 = b1 B1 = 60
b2 = 10 B3 = b2 B2 = 600
b3 = 6 B4 = b3 B3 = 3600 (5)
Another system’s constants could be b0 = 12 and b1 = 3; A is length in inches, while p2, p1, and p0 are yards, feet, and inches respectively.
Later in the text, a ternary system will be discussed. It has the following base constants:
b0 = 3 B1 = b0 = 3
b1 = 3 B2 = b1 B1 = 9
bm–1 = 3 Bm = bm–1 Bm–1 = 3m (6)
When numerical systems are discussed, then the places pm are integers, which are limited to the interval
0 ≤ pm < bm (7)
pm must be less than the corresponding base constant bm. For decimal, pm is an integer: 0 ≤ pm < 10. But the sum (2)
holds true also when places pm take values beyond the interval (7)! It is not even necessary that p's are integers, but we should keep to the positive integers because, well, MCUs.
Let’s assume that A is a binary number 0xFF and that base constants Bm belong to the decimal system (3). The equation (2) holds even when p0 = 255, p1 = 0, and p2 = 0. This is an extreme. It holds also when p0 = 25, p1 = 13, and p2 = 1. But normally, the values are p0 = 5, p1 = 5, and p2 = 2. That is, 0xFF = 255.
In code or hardware for conversion between bases, Rm bits of memory are allocated for each place pm. Usually, nibbles (Rm = 4) or bytes (Rm = 8) are used. The allocated memory is big enough when 2Rm ≥ bm holds. Still, the allocated chunk of memory should be a bit larger to provide some space for bit carrying. Thus, the place pm is an integer that is limited to the interval 0 ≤ pm < 2Rm.
Additional space in pm eases bit carrying from pm to pm+1. What is this bit carrying? It is executed when pm+1 is incremented by one (a bit) and pm is decremented by the base constant bm. Decrementing is possible as long as pm ≥ bm. Let us have a binary number A = 0xDB and base constants bm of the decimal system (3). Then, let the places be p2 = 2, p1 = 0, and p0 = 19. We can see that the equation (2) holds. We can also see that at least five bits are necessary to store p0. To carry from p0 to p1, the place p1 is incremented by 1 and p0 is decremented by b0 = 10. The p0 and p1 are adjusted. Now, the places are p2 = 2, p1 = 1, and p0 = 9. That is, 0xDB = 219. During the bit carrying, the equation (2) is always valid.
As said, the bit carrying consists of two steps. In one step, the place pm+1 is incremented. In the other step, the base constant bm is subtracted from pm. The two steps can be reduced into one by combining the two places pm+1 and pm into one number 2Rm pm+1 + pm. This number already exists if p's are allocated successively in the MCU's memory. That is, two successive bytes form one unsigned int. Then, a carry constant 2Rm – bm is added to this new number. The effect can be seen in (8). The higher byte is incremented by one and the lower byte is decremented by bm.
pm ≥ bm, (2Rm pm+1 + pm) + (2Rm – bm) = 2Rm(pm+1 + 1) + (pm – bm) (8)
The order of adjusting places pm in (2) plays no role. Either pair of places p0, p1 or pM, pM–1, or any other pair, can be adjusted first. It is because equation (2) holds after any bit carrying. Despite that, it is beneficial that adjustment is executed from p0 upwards. This way, no pm needs to be adjusted twice. By repeating adjustments, values of individual p's are made smaller until the condition (7) is valid for all pm. The places pm are considered adjusted then.
Conversion of binary to some other system is possible by bit carrying only. The initial binary number A is moved into p0, which must be large enough. Then, bit carrying is repeated until the condition (7) is fulfilled for all p's. At this point, the number A is converted. Although this method works, it is inefficient. To speed up the conversion, left shifting, which has the same effect as multiplying by two, is introduced. Then, shifting and bit carrying are executed sequentially. The bit carrying is executed after each shift to keep the needed size of p's as small as possible. At the same time, condition (7) is fulfilled. Because of the sequence, this is called a shift-adjust algorithm.
The algorithm runs in iterations. In the initializing iteration i = 0, all p's are cleared. Because of that, equation (9) is zero. Of course, condition (7) holds for all pm, too.
BM pM(i = 0) + … + Bm pm(i = 0) + … + B1 p1(i = 0) + p0(i = 0) = 0 (9)
Now, the equation is multiplied by two. At the same time, bit aN–1 , which is the MSb of A in (1), is added to p0. In assembler, this is done by left rotate through carry on A and p0. Memory chunks of other p's should be large enough so that p's do not overflow during the shifting. They are shifted individually.
2(BM pM(i = 0) + … + Bm pm(i = 0) + … + B1 p1(i = 0) + p0(i = 0)) + aN–1 = aN–1 (10)
After shifting, (10), the bit carries are repeated until the conditions in (7) are met for all m. Adjusting is not yet needed after the first shift. But to keep to the shift-adjust algorithm, adjusting of p's by bit carrying takes place after each shift. After the first iteration is completed, (7) holds for all m. An equation (11) is obtained, which is an input to the second iteration.
BM pM(i = 1) + … + Bm pm(i = 1) + … + B1 p1(i = 1) + p0(i = 1) = aN–1 (11)
Now, shifting and adjusting take place again.
BM pM(i = 2) + … + Bm pm(i = 2) + … + B1 p1(i = 2) + p0(i = 2) = 2aN–1 + aN–2 (12)
The sequence is repeated N-times.
BM pM(i = N) + … + Bm pm(i = N) + … + B1 p1(i = N) + p0(i = N) = 2N–1 aN–1 + … + 2 a1 + a0 (13)
After the last bit carrying is over, binary number A is on the right side of (13). On the left side, A is converted into numerals of the desired numerical system. These numerals are stored in the p's.
[Continue reading on EDN US: Examples, ternary, & code]
—Mitja Rihtaršič has an MSc degree and has been designing BLDC motor controllers and electronics used in compressed air equipment.