What is double dabble?
Double dabble, also called the shift-and-add-3 algorithm, converts a binary number into binary-coded decimal (BCD), where each decimal digit is stored in its own 4 bits. It only uses shifts, comparisons, and adding 3, so it's cheap to build in hardware. It's the usual way to drive 7-segment displays from an FPGA or microcontroller.
How the algorithm works
Put the BCD digits (all starting at 0) to the left of the binary input, forming one long register. Then, once for every input bit:
- Check: look at each 4-bit BCD digit. If it's 5 or more, add 3 to it.
- Shift: shift the whole register left by 1 bit.
After as many shifts as there are input bits, the BCD digits hold the decimal value.
Why add 3 when a digit is ≥ 5?
Shifting left doubles a digit. A digit of 5 or more becomes 10 or more, which isn't a valid decimal digit,
but a 4-bit group won't carry into the next group until it reaches 16. Adding 3 before the shift adds 6 after it,
and 10 + 6 = 16, so the carry lands in the next digit exactly when it should in decimal.
Example: 7 shifted gives 14 (1110, wrong), but 7 + 3 = 10 shifted gives 1 0100: tens 1, ones 4.
Worked example: 243
243 is 11110011 in binary (8 bits), so there are 8 shifts. Checks that change nothing are left out.
| Step | Hundreds | Tens | Ones | Input |
|---|---|---|---|---|
| Start | 0000 | 0000 | 0000 | 11110011 |
| Shift 1 | 0000 | 0000 | 0001 | 1110011 |
| Shift 2 | 0000 | 0000 | 0011 | 110011 |
| Shift 3 | 0000 | 0000 | 0111 | 10011 |
| Ones 7 ≥ 5, +3 | 0000 | 0000 | 1010 | 10011 |
| Shift 4 | 0000 | 0001 | 0101 | 0011 |
| Ones 5 ≥ 5, +3 | 0000 | 0001 | 1000 | 0011 |
| Shift 5 | 0000 | 0011 | 0000 | 011 |
| Shift 6 | 0000 | 0110 | 0000 | 11 |
| Tens 6 ≥ 5, +3 | 0000 | 1001 | 0000 | 11 |
| Shift 7 | 0001 | 0010 | 0001 | 1 |
| Shift 8 | 0010 | 0100 | 0011 | |
| Result | 2 | 4 | 3 |
How many BCD digits do I need?
An n-bit input needs ⌈n · log102⌉ ≈ ⌈0.301n⌉ digits: 3 digits for 8 bits (max 255), 5 digits for 16 bits (max 65535), 10 digits for 32 bits. The algorithm always takes exactly n shifts.
Double dabble in Verilog
A combinational 8-bit to 3-digit BCD converter, doing the same check-then-shift loop as the visualizer:
module bin2bcd (
input [7:0] bin,
output reg [11:0] bcd // {hundreds, tens, ones}
);
integer i;
always @* begin
bcd = 12'd0;
for (i = 7; i >= 0; i = i - 1) begin
if (bcd[3:0] >= 5) bcd[3:0] = bcd[3:0] + 4'd3;
if (bcd[7:4] >= 5) bcd[7:4] = bcd[7:4] + 4'd3;
if (bcd[11:8] >= 5) bcd[11:8] = bcd[11:8] + 4'd3;
bcd = {bcd[10:0], bin[i]}; // shift left, bring in next input bit
end
end
endmodule