X

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}*

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}*

The constants *B _{m}* depend on the numerical system. In decimal, these are products of base constants

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

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

…

*b _{m}*

…

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}*

…

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

0 ≤ *p _{m}* <

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

holds true also when places *p _{m}* take values beyond the interval (7)! It is not even necessary that

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

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

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

As said, the bit carrying consists of two steps. In one step, the place *p _{m}*

* p _{m}* ≥

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

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}*

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

2(*B _{M}*

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}*

Now, shifting and adjusting take place again.

*B _{M}*

The sequence is repeated *N*-times.

* B _{M}*

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.*