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* = 2^{N}^{–1} *a _{N}*

_{–1}+ … + 2

^{n}*a*+ … + 2

_{n}*a*

_{1}+

*a*

_{0}(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 11011011_{2}.

The number *A* is defined by a sum:

* A* = *B _{M}*

*p*+ … +

_{M}*B*

_{m}*p*+ … +

_{m}*B*

_{1}

*p*

_{1}+

*p*(2)

_{0}The constants *B _{m}* 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.

*b*_{0} = 10 *B*_{1} = *b*_{0} = 10

*b*_{1} = 10 *B*_{2} = *b*_{1} *B*_{1} = 100

…

*b _{m}*

_{–1}= 10

*B*=

_{m}*b*

_{m}_{–1}

*B*

_{m}_{–1}= 10

^{m}(3)…

The decimal system is not the only interesting system. For example, time, in base 60. Now, *p*_{0}, *p*_{1}, and *p*_{2} are seconds, minutes, and hours respectively.

*b*_{0} = 60 *B*_{1} = *b*_{0} = 60

*b*_{1} = 60 *B*_{2} = *b*_{1} *B*_{1} = 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 *p*_{0} and *p*_{1} together are seconds in the decimal system, *p*_{2} and *p*_{3} are minutes, and *p*_{4} shows hours.

*b*_{0} = 10 *B*_{1} = *b*_{0} = 10

*b*_{1} = 6 *B*_{2} = *b*_{1} *B*_{1} = 60

*b*_{2} = 10 *B*_{3} = *b*_{2} *B*_{2} = 600

*b*_{3} = 6 *B*_{4} = *b*_{3} *B*_{3} = 3600 (5)

Another system’s constants could be *b*_{0} = 12 and *b*_{1} = 3; A is length in inches, while *p*_{2}, *p*_{1}, and *p*_{0} are yards, feet, and inches respectively.

Later in the text, a ternary system will be discussed. It has the following base constants:

*b*_{0} = 3 *B*_{1} = *b*_{0} = 3

*b*_{1} = 3 *B*_{2} = *b*_{1} *B*_{1} = 9

…

*b _{m}*

_{–1}= 3

*B*=

_{m}*b*

_{m}_{–1}

*B*

_{m}_{–1}= 3

^{m}(6)…

When numerical systems are discussed, then the places *p _{m}* are integers, which are limited to the interval

0 ≤ *p _{m}* <

*b*(7)

_{m}*p _{m}* must be less than the corresponding base constant

*b*. For decimal,

_{m}*p*is an integer: 0 ≤

_{m}*p*< 10. But the sum (2)

_{m}holds true also when places *p _{m}* 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 *B _{m}* belong to the decimal system (3). The equation (2) holds even when

*p*

_{0}= 255,

*p*

_{1}= 0, and

*p*

_{2}= 0. This is an extreme. It holds also when

*p*

_{0}= 25,

*p*

_{1}= 13, and

*p*

_{2}= 1. But normally, the values are

*p*

_{0}= 5,

*p*

_{1}= 5, and

*p*

_{2}= 2. That is, 0xFF = 255.

In code or hardware for conversion between bases, *R _{m}* bits of memory are allocated for each place

*p*. Usually, nibbles (

_{m}*R*= 4) or bytes (

_{m}*R*= 8) are used. The allocated memory is big enough when 2

_{m}

^{Rm}*≥*

*b*holds. Still, the allocated chunk of memory should be a bit larger to provide some space for bit carrying. Thus, the place

_{m}*p*is an integer that is limited to the interval 0 ≤

_{m}*p*< 2

_{m}*.*

^{Rm}Additional space in *p _{m}* eases bit carrying from

*p*to

_{m }*p*

_{m}_{+1}. What is this bit carrying? It is executed when

*p*

_{m}_{+1}is incremented by one (a bit) and

*p*is decremented by the base constant

_{m}*b*. Decrementing is possible as long as

_{m}*p*≥

_{m}*b*. Let us have a binary number

_{m}*A*= 0xDB and base constants

*b*of the decimal system (3). Then, let the places be

_{m}*p*

_{2}= 2,

*p*

_{1}= 0, and

*p*

_{0}= 19. We can see that the equation (2) holds. We can also see that at least five bits are necessary to store

*p*

_{0}. To carry from

*p*

_{0}to

*p*

_{1}, the place

*p*

_{1}is incremented by 1 and

*p*

_{0}is decremented by

*b*

_{0}= 10. The

*p*

_{0}and

*p*

_{1}are adjusted. Now, the places are

*p*

_{2}= 2,

*p*

_{1}= 1, and

*p*

_{0}= 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 *p _{m}*

_{+1}is incremented. In the other step, the base constant

*b*is subtracted from

_{m}*p*. The two steps can be reduced into one by combining the two places

_{m}*p*

_{m}_{+1}and

*p*into one number 2

_{m}

^{Rm}p_{m}_{+1}+

*p*

_{m}. 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 2

*–*

^{Rm}*b*

_{m}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

*b*.

_{m}* p _{m}* ≥

*b*, (2

_{m}

^{Rm}*p*

_{m}_{+1}+

*p*

_{m}) + (2

*–*

^{Rm}*b*

_{m}) = 2

*(*

^{Rm}*p*

_{m}_{+1}+ 1) + (

*p*–

_{m}*b*

_{m}) (8)

The order of adjusting places *p _{m}* in (2) plays no role. Either pair of places

*p*

_{0},

*p*

_{1}or

*p*,

_{M}*p*

_{M}_{–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

*p*

_{0}upwards. This way, no

*p*needs to be adjusted twice. By repeating adjustments, values of individual

_{m}*p*'s are made smaller until the condition (7) is valid for all

*p*. The places

_{m}*p*are considered adjusted then.

_{m}Conversion of binary to some other system is possible by bit carrying only. The initial binary number *A* is moved into *p*_{0}, 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 *p _{m}*, too.

* B _{M}*

*p*(

_{M}*i*= 0) + … +

*B*

_{m}*p*(

_{m}*i*= 0) + … +

*B*

_{1}

*p*

_{1}(

*i*= 0) +

*p*

_{0}(

*i*= 0) = 0 (9)

Now, the equation is multiplied by two. At the same time, bit *a _{N}*

_{–1}, which is the MSb of

*A*in (1), is added to

*p*

_{0}. In assembler, this is done by left rotate through carry on

*A*and

*p*

_{0}. 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(*B _{M}*

*p*(

_{M}*i*= 0) + … +

*B*

_{m}*p*(

_{m}*i*= 0) + … +

*B*

_{1}

*p*

_{1}(

*i*= 0) +

*p*

_{0}(

*i*= 0)) +

*a*

_{N}_{–1}=

*a*

_{N}_{–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.

* B _{M}*

*p*(

_{M}*i*= 1) + … +

*B*

_{m}*p*(

_{m}*i*= 1) + … +

*B*

_{1}

*p*

_{1}(

*i*= 1) +

*p*

_{0}(

*i*= 1) =

*a*

_{N}_{–1}(11)

Now, shifting and adjusting take place again.

*B _{M}*

*p*(

_{M}*i*= 2) + … +

*B*

_{m}*p*(

_{m}*i*= 2) + … +

*B*

_{1}

*p*

_{1}(

*i*= 2) +

*p*

_{0}(

*i*= 2) = 2

*a*

_{N}_{–1}+

*a*

_{N}_{–2}(12)

The sequence is repeated *N*-times.

* B _{M}*

*p*(

_{M}*i*=

*N*) + … +

*B*

_{m}*p*(

_{m}*i*=

*N*) + … +

*B*

_{1}

*p*

_{1}(

*i*=

*N*) +

*p*

_{0}(

*i*=

*N*) = 2

^{N}^{–1}

_{ }

*a*

_{N}_{–1}+ … + 2

*a*

_{1}+

*a*

_{0}(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]

**Related articles**:

- Perform hexadecimal-to-BCD conversion in firmware
- Conversion circuit handles binary or BCD
- C routine speeds decimal-to-binary conversion>
- Ternary DAC: Greater resolution, less bits
- Technique increases low-cost DAC's resolution
- Trits vs. Bits: 5-Trit ternary DAC has (almost) 8-bit resolution and high PSRR

—*Mitja Rihtaršič** has an MSc degree and has been designing BLDC motor controllers and electronics used in compressed air equipment.*