fbpx
Wikipedia

Double dabble

January 07, 2023

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

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 of the double dabble binary to BCD converter

// 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 converter, 18-bit example.[4]


Reverse double dabble

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 principle steps of the algorithm:

The principle 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

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

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

  • Lookup table – an alternate approach to perform conversion

References

  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, S2CID 36909518
  2. ^ (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, 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

  • Falconer, Charles "Chuck" B. (2004-04-16). . Archived from the original on 2009-03-25.

January 07, 2023
double, dabble, computer, science, double, dabble, algorithm, used, convert, binary, numbers, into, binary, coded, decimal, notation, also, known, shift, algorithm, implemented, using, small, number, gates, computer, hardware, expense, high, latency, contents,. 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 Contents 1 Algorithm 2 Parametric Verilog implementation of the double dabble binary to BCD converter 3 Reverse double dabble 3 1 Reverse double dabble example 4 Historical 5 See also 6 References 7 Further readingAlgorithm EditThe 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 of the double dabble binary to BCD converter 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 lt 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 lt W 4 i i 1 iterate on structure depth for j 0 j lt i 3 j j 1 iterate on structure width if bcd W i 4 j 4 gt 4 if gt 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 converter 18 bit example 4 Reverse double dabble EditThe 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 principle steps of the algorithm The principle steps of the algorithms Double dabble Binary to BCD Reverse double dabble BCD to binary For each group of input four bits If group gt 5 add 3 to groupLeft shift into the output digits Right shift into the output binaryFor each group of four input bits If group gt 8 subtract 3 from groupReverse 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 24310Historical EditIn 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 EditLookup table an alternate approach to perform conversionReferences Edit 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 S2CID 36909518 Binary to BCD Converter Double Dabble Binary to BCD Conversion Algorithm PDF Archived from the original PDF on 2012 01 31 Vestias 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 S2CID 28360570 a b Abdelhadi Ameer 2019 07 07 AmeerAbdelhadi Binary to BCD Converter retrieved 2020 03 03 Godse Deepali A Godse Atul P 2008 Digital Techniques Pune India Technical Publications p 4 ISBN 978 8 18431401 4 Further reading EditFalconer Charles Chuck B 2004 04 16 An Explanation of the Double Dabble Bin BCD Conversion Algorithm Archived from the original on 2009 03 25 Retrieved from https en wikipedia org w index php title Double dabble amp oldid 1128823048, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.