Jump to content

Double dabble

Edit links
From Wikipedia, the free encyclopedia
(Redirected from Shift-and-add-3 algorithm)

In computer science, the double dabble algorithm is used to convert binary numbers into binary-coded decimal (BCD) notation.[1][2] It is also known as the shift-and-add-3 algorithm, and can be implemented using a small number of gates in computer hardware, but at the expense of high latency.[3]

Algorithm

[edit]

The algorithm operates as follows:

Suppose the original number to be converted is stored in a register that is n bits wide. Reserve a scratch space wide enough to hold both the original number and its BCD representation; n + 4×ceil(n/3) bits will be enough. It takes a maximum of 4 bits in binary to store each decimal digit.

Then partition the scratch space into BCD digits (on the left) and the original register (on the right). For example, if the original number to be converted is eight bits wide, the scratch space would be partitioned as follows: 

Hundreds Tens Ones   Original
  0010   0100 0011   11110011

The diagram above shows the binary representation of 24310 in the original register, and the BCD representation of 243 on the left.

The scratch space is initialized to all zeros, and then the value to be converted is copied into the "original register" space on the right. 

0000 0000 0000   11110011

The algorithm then iterates n times. On each iteration, any BCD digit which is at least 5 (0101 in binary) is incremented by 3 (0011); then the entire scratch space is left-shifted one bit. The increment ensures that a value of 5, incremented and left-shifted, becomes 16 (10000), thus correctly "carrying" into the next BCD digit.

Essentially, the algorithm operates by doubling the BCD value on the left each iteration and adding either one or zero according to the original bit pattern. Shifting left accomplishes both tasks simultaneously. If any digit is five or above, three is added to ensure the value "carries" in base 10.

The double-dabble algorithm, performed on the value 24310, looks like this: 

0000 0000 0000   11110011   Initialization
0000 0000 0001   11100110   Shift
0000 0000 0011   11001100   Shift
0000 0000 0111   10011000   Shift
0000 0000 1010   10011000   Add 3 to ONES, since it was 7
0000 0001 0101   00110000   Shift
0000 0001 1000   00110000   Add 3 to ONES, since it was 5
0000 0011 0000   01100000   Shift
0000 0110 0000   11000000   Shift
0000 1001 0000   11000000   Add 3 to TENS, since it was 6
0001 0010 0001   10000000   Shift
0010 0100 0011   00000000   Shift
   2    4    3
       BCD

Now eight shifts have been performed, so the algorithm terminates. The BCD digits to the left of the "original register" space display the BCD encoding of the original value 243.

Another example for the double dabble algorithm – value 6524410. 

 104  103  102   101  100    Original binary
0000 0000 0000 0000 0000   1111111011011100   Initialization
0000 0000 0000 0000 0001   1111110110111000   Shift left (1st)
0000 0000 0000 0000 0011   1111101101110000   Shift left (2nd)
0000 0000 0000 0000 0111   1111011011100000   Shift left (3rd)
0000 0000 0000 0000 1010   1111011011100000   Add 3 to 100, since it was 7
0000 0000 0000 0001 0101   1110110111000000   Shift left (4th)
0000 0000 0000 0001 1000   1110110111000000   Add 3 to 100, since it was 5
0000 0000 0000 0011 0001   1101101110000000   Shift left (5th)
0000 0000 0000 0110 0011   1011011100000000   Shift left (6th)
0000 0000 0000 1001 0011   1011011100000000   Add 3 to 101, since it was 6
0000 0000 0001 0010 0111   0110111000000000   Shift left (7th)
0000 0000 0001 0010 1010   0110111000000000   Add 3 to 100, since it was 7
0000 0000 0010 0101 0100   1101110000000000   Shift left (8th)
0000 0000 0010 1000 0100   1101110000000000   Add 3 to 101, since it was 5
0000 0000 0101 0000 1001   1011100000000000   Shift left (9th)
0000 0000 1000 0000 1001   1011100000000000   Add 3 to 102, since it was 5
0000 0000 1000 0000 1100   1011100000000000   Add 3 to 100, since it was 9
0000 0001 0000 0001 1001   0111000000000000   Shift left (10th)
0000 0001 0000 0001 1100   0111000000000000   Add 3 to 100, since it was 9
0000 0010 0000 0011 1000   1110000000000000   Shift left (11th)
0000 0010 0000 0011 1011   1110000000000000   Add 3 to 100, since it was 8
0000 0100 0000 0111 0111   1100000000000000   Shift left (12th)
0000 0100 0000 1010 0111   1100000000000000   Add 3 to 101, since it was 7
0000 0100 0000 1010 1010   1100000000000000   Add 3 to 100, since it was 7
0000 1000 0001 0101 0101   1000000000000000   Shift left (13th)
0000 1011 0001 0101 0101   1000000000000000   Add 3 to 103, since it was 8
0000 1011 0001 1000 0101   1000000000000000   Add 3 to 101, since it was 5
0000 1011 0001 1000 1000   1000000000000000   Add 3 to 100, since it was 5
0001 0110 0011 0001 0001   0000000000000000   Shift left (14th)
0001 1001 0011 0001 0001   0000000000000000   Add 3 to 103, since it was 6
0011 0010 0110 0010 0010   0000000000000000   Shift left (15th)
0011 0010 1001 0010 0010   0000000000000000   Add 3 to 102, since it was 6
0110 0101 0010 0100 0100   0000000000000000   Shift left (16th)
   6    5    2    4    4
            BCD

Sixteen shifts have been performed, so the algorithm terminates. The decimal value of the BCD digits is: 6*104 + 5*103 + 2*102 + 4*101 + 4*100 = 65244.

Parametric Verilog implementation

[edit]
// parametric Verilog implementation of the double dabble binary to BCD converter
// for the complete project, see
// https://github.com/AmeerAbdelhadi/Binary-to-BCD-Converter

module bin2bcd
 #( parameter                W = 18)  // input width
  ( input      [W-1      :0] bin   ,  // binary
    output reg [W+(W-4)/3:0] bcd   ); // bcd {...,thousands,hundreds,tens,ones}

  integer i,j;

  always @(bin) begin
    for(i = 0; i <= W+(W-4)/3; i = i+1) bcd[i] = 0;     // initialize with zeros
    bcd[W-1:0] = bin;                                   // initialize with input vector
    for(i = 0; i <= W-4; i = i+1)                       // iterate on structure depth
      for(j = 0; j <= i/3; j = j+1)                     // iterate on structure width
        if (bcd[W-i+4*j -: 4] > 4)                      // if > 4
          bcd[W-i+4*j -: 4] = bcd[W-i+4*j -: 4] + 4'd3; // add 3
  end

endmodule

[4]

Parametric Verilog implementation of the double dabble binary to BCD converte, 18-bit example.
Parametric Verilog implementation of the double dabble binary to BCD converter, 18-bit example.[4]


Reverse double dabble

[edit]

The algorithm is fully reversible. By applying the reverse double dabble algorithm a BCD number can be converted to binary. Reversing the algorithm is done by reversing the principal steps of the algorithm:

The principal steps of the algorithms
Double dabble
(Binary to BCD) 		Reverse double dabble
(BCD to binary)
For each group of input four bits:
   If group >= 5 add 3 to group
Left shift into the output digits 		Right shift into the output binary
For each group of four input bits:
   If group >= 8 subtract 3 from group

Reverse double dabble example

[edit]

The reverse double dabble algorithm, performed on the three BCD digits 2-4-3, looks like this: 

    BCD Input      Binary 
                   Output
   2    4    3
 0010 0100 0011   00000000   Initialization
 0001 0010 0001   10000000   Shifted right
 0000 1001 0000   11000000   Shifted right
 0000 0110 0000   11000000   Subtracted 3 from 2nd group, because it was 9
 0000 0011 0000   01100000   Shifted right
 0000 0001 1000   00110000   Shifted right
 0000 0001 0101   00110000   Subtracted 3 from 3rd group, because it was 8
 0000 0000 1010   10011000   Shifted right
 0000 0000 0111   10011000   Subtracted 3 from 3rd group, because it was 10
 0000 0000 0011   11001100   Shifted right
 0000 0000 0001   11100110   Shifted right
 0000 0000 0000   11110011   Shifted right
==========================
                       24310

Historical

[edit]

In the 1960s, the term double dabble was also used for a different mental algorithm, used by programmers to convert a binary number to decimal. It is performed by reading the binary number from left to right, doubling if the next bit is zero, and doubling and adding one if the next bit is one.[5] In the example above, 11110011, the thought process would be: "one, three, seven, fifteen, thirty, sixty, one hundred twenty-one, two hundred forty-three", the same result as that obtained above.

See also

[edit]
  • Lookup table – an alternate approach to perform conversion

References

[edit]
  1. ^ Gao, Shuli; Al-Khalili, D.; Chabini, N. (June 2012), "An improved BCD adder using 6-LUT FPGAs", IEEE 10th International New Circuits and Systems Conference (NEWCAS 2012), pp. 13–16, doi:10.1109/NEWCAS.2012.6328944, ISBN 978-1-4673-0859-5, S2CID 36909518
  2. ^ "Binary-to-BCD Converter: "Double-Dabble Binary-to-BCD Conversion Algorithm"" (PDF). Archived from the original (PDF) on 2012-01-31.
  3. ^ Véstias, Mario P.; Neto, Horatio C. (March 2010), "Parallel decimal multipliers using binary multipliers", VI Southern Programmable Logic Conference (SPL 2010), pp. 73–78, doi:10.1109/SPL.2010.5483001, ISBN 978-1-4244-6309-1, S2CID 28360570
  4. ^ a b Abdelhadi, Ameer (2019-07-07), AmeerAbdelhadi/Binary-to-BCD-Converter, retrieved 2020-03-03
  5. ^ Godse, Deepali A.; Godse, Atul P. (2008). Digital Techniques. Pune, India: Technical Publications. p. 4. ISBN 978-8-18431401-4.

Further reading

[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Double_dabble&oldid=1224570712"