151:
0000 0000 1010 1111011011100000 Add 3 to 10, since it was 7 0000 0000 0000 0001 0101 1110110111000000 Shift left (4th) 0000 0000 0000 0001 1000 1110110111000000 Add 3 to 10, 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 10, since it was 6 0000 0000 0001 0010 0111 0110111000000000 Shift left (7th) 0000 0000 0001 0010 1010 0110111000000000 Add 3 to 10, since it was 7 0000 0000 0010 0101 0100 1101110000000000 Shift left (8th) 0000 0000 0010 1000 0100 1101110000000000 Add 3 to 10, since it was 5 0000 0000 0101 0000 1001 1011100000000000 Shift left (9th) 0000 0000 1000 0000 1001 1011100000000000 Add 3 to 10, since it was 5 0000 0000 1000 0000 1100 1011100000000000 Add 3 to 10, since it was 9 0000 0001 0000 0001 1001 0111000000000000 Shift left (10th) 0000 0001 0000 0001 1100 0111000000000000 Add 3 to 10, since it was 9 0000 0010 0000 0011 1000 1110000000000000 Shift left (11th) 0000 0010 0000 0011 1011 1110000000000000 Add 3 to 10, since it was 8 0000 0100 0000 0111 0111 1100000000000000 Shift left (12th) 0000 0100 0000 1010 0111 1100000000000000 Add 3 to 10, since it was 7 0000 0100 0000 1010 1010 1100000000000000 Add 3 to 10, since it was 7 0000 1000 0001 0101 0101 1000000000000000 Shift left (13th) 0000 1011 0001 0101 0101 1000000000000000 Add 3 to 10, since it was 8 0000 1011 0001 1000 0101 1000000000000000 Add 3 to 10, since it was 5 0000 1011 0001 1000 1000 1000000000000000 Add 3 to 10, since it was 5 0001 0110 0011 0001 0001 0000000000000000 Shift left (14th) 0001 1001 0011 0001 0001 0000000000000000 Add 3 to 10, since it was 6 0011 0010 0110 0010 0010 0000000000000000 Shift left (15th) 0011 0010 1001 0010 0010 0000000000000000 Add 3 to 10, since it was 6 0110 0101 0010 0100 0100 0000000000000000 Shift left (16th) 6 5 2 4 4 BCD
532:
634:
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. In the example above, 11110011, the thought
136:
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
125:
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.
121:
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
150:
10 10 10 10 10 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
618:
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 ==========================
97:
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:
137:
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
547:
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:
140:
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.
594:
BCD Input Binary Output 2 4 3 0010 0100 0011 00000000 Initialization 0001 0010 0001 10000000 Shifted right 0000
635:
process would be: "one, three, seven, fifteen, thirty, sixty, one hundred twenty-one, two hundred forty-three", the same result as that obtained above.
154:
Sixteen shifts have been performed, so the algorithm terminates. The decimal value of the BCD digits is: 6*10 + 5*10 + 2*10 + 4*10 + 4*10 = 65244.
746:
682:
111:
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.
805:
847:
705:
826:
602:
0000 11000000 Subtracted 3 from 2nd group, because it was 9 0000 0011 0000 01100000 Shifted right 0000 0001
852:
79: bits wide. Reserve a scratch space wide enough to hold both the original number and its BCD representation;
51:
729:
Véstias, Mario P.; Neto, Horatio C. (March 2010), "Parallel decimal multipliers using binary multipliers",
57:
56:, and can be implemented using a small number of gates in computer hardware, but at the expense of high
46:
752:
688:
72:
665:
Gao, Shuli; Al-Khalili, D.; Chabini, N. (June 2012), "An improved BCD adder using 6-LUT FPGAs",
591:
The reverse double dabble algorithm, performed on the three BCD digits 2-4-3, looks like this:
535:
Parametric
Verilog implementation of the double dabble binary to BCD converter, 18-bit example.
801:
742:
678:
94:
bits will be enough. It takes a maximum of 4 bits in binary to store each decimal digit.
795:
773:
734:
670:
31:
712:
17:
830:
42:
531:
841:
756:
692:
644:
164:// parametric Verilog implementation of the double dabble binary to BCD converter
674:
738:
706:"Binary-to-BCD Converter: "Double-Dabble Binary-to-BCD Conversion Algorithm""
143:
Another example for the double dabble algorithm – value 65244
38:
667:
IEEE 10th
International New Circuits and Systems Conference (NEWCAS 2012)
108:
in the original register, and the BCD representation of 243 on the left.
610:
00110000 Subtracted 3 from 3rd group, because it was 8 0000 0000
827:"An Explanation of the Double-Dabble Bin-BCD Conversion Algorithm"
530:
647: – an alternate approach to perform conversion
170:// https://github.com/AmeerAbdelhadi/Binary-to-BCD-Converter
101:
Hundreds Tens Ones
Original 0010 0100 0011 11110011
71:
Suppose the original number to be converted is stored in a
580: If group >= 8 subtract 3 from group
104:
The diagram above shows the binary representation of 243
129:
The double-dabble algorithm, performed on the value 243
731:
800:. Pune, India: Technical Publications. p. 4.
571: If group >= 5 add 3 to group
8:
825:Falconer, Charles "Chuck" B. (2004-04-16).
767:
765:
794:Godse, Deepali A.; Godse, Atul P. (2008).
27:Algorithm to convert binary numbers to BCD
227:// bcd {...,thousands,hundreds,tens,ones}
550:
49:(BCD) notation. It is also known as the
657:
775:AmeerAbdelhadi/Binary-to-BCD-Converter
598:0000 11000000 Shifted right 0000
552:The principal steps of the algorithms
7:
614:10011000 Shifted right 0000 0000
606:00110000 Shifted right 0000 0001
68:The algorithm operates as follows:
578:For each group of four input bits:
576:Right shift into the output binary
573:Left shift into the output digits
569:For each group of input four bits:
25:
158:Parametric Verilog implementation
167:// for the complete project, see
772:Abdelhadi, Ameer (2019-07-07),
359:// initialize with input vector
1:
587:Reverse double dabble example
473:// iterate on structure width
416:// iterate on structure depth
117:The algorithm then iterates
675:10.1109/NEWCAS.2012.6328944
869:
114:0000 0000 0000 11110011
18:Shift-and-add-3 algorithm
848:Shift-and-add algorithms
739:10.1109/SPL.2010.5483001
344:// initialize with zeros
161:
630:In the 1960s, the term
536:
562:Reverse double dabble
543:Reverse double dabble
534:
47:binary-coded decimal
553:
133:, looks like this:
41:is used to convert
797:Digital Techniques
733:, pp. 73–78,
669:, pp. 13–16,
551:
537:
853:Binary arithmetic
748:978-1-4244-6309-1
684:978-1-4673-0859-5
584:
583:
16:(Redirected from
860:
834:
829:. Archived from
812:
811:
807:978-8-18431401-4
791:
785:
784:
783:
782:
769:
760:
759:
726:
720:
719:
717:
711:. Archived from
710:
702:
696:
695:
662:
617:
613:
609:
605:
601:
597:
564:(BCD to binary)
559:(Binary to BCD)
554:
525:
522:
519:
516:
513:
510:
507:
504:
501:
498:
495:
492:
489:
486:
483:
480:
477:
474:
471:
468:
465:
462:
459:
456:
453:
450:
447:
444:
441:
438:
435:
432:
429:
426:
423:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
390:
387:
384:
381:
378:
375:
372:
369:
366:
363:
360:
357:
354:
351:
348:
345:
342:
339:
336:
333:
330:
327:
324:
321:
318:
315:
312:
309:
306:
303:
300:
297:
294:
291:
288:
285:
282:
279:
276:
273:
270:
267:
264:
261:
258:
255:
252:
249:
246:
243:
240:
237:
234:
231:
228:
225:
222:
219:
216:
213:
210:
207:
204:
201:
198:
195:
192:
189:
186:
183:
180:
177:
174:
171:
168:
165:
93:
32:computer science
21:
868:
867:
863:
862:
861:
859:
858:
857:
838:
837:
824:
821:
819:Further reading
816:
815:
808:
793:
792:
788:
780:
778:
771:
770:
763:
749:
728:
727:
723:
715:
708:
704:
703:
699:
685:
664:
663:
659:
654:
641:
628:
623:
622:
615:
611:
607:
603:
599:
595:
589:
579:
577:
572:
570:
563:
558:
545:
539:
527:
526:
523:
520:
517:
514:
511:
508:
505:
502:
499:
496:
493:
490:
487:
484:
481:
478:
475:
472:
469:
466:
463:
460:
457:
454:
451:
448:
445:
442:
439:
436:
433:
430:
427:
424:
421:
418:
415:
412:
409:
406:
403:
400:
397:
394:
391:
388:
385:
382:
379:
376:
373:
370:
367:
364:
361:
358:
355:
352:
349:
346:
343:
340:
337:
334:
331:
328:
325:
322:
319:
316:
313:
310:
307:
304:
301:
298:
295:
292:
289:
286:
283:
280:
277:
274:
271:
268:
265:
262:
259:
256:
253:
250:
247:
244:
241:
238:
235:
232:
229:
226:
223:
220:
217:
214:
211:
208:
205:
202:
199:
196:
193:
190:
187:
184:
181:
178:
175:
172:
169:
166:
163:
160:
152:
146:
138:
132:
115:
107:
102:
80:
66:
28:
23:
22:
15:
12:
11:
5:
866:
864:
856:
855:
850:
840:
839:
836:
835:
833:on 2009-03-25.
820:
817:
814:
813:
806:
786:
761:
747:
721:
718:on 2012-01-31.
697:
683:
656:
655:
653:
650:
649:
648:
640:
637:
627:
624:
620:
593:
588:
585:
582:
581:
574:
566:
565:
560:
544:
541:
197:// input width
162:
159:
156:
149:
144:
135:
130:
113:
105:
100:
65:
62:
43:binary numbers
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
865:
854:
851:
849:
846:
845:
843:
832:
828:
823:
822:
818:
809:
803:
799:
798:
790:
787:
777:
776:
768:
766:
762:
758:
754:
750:
744:
740:
736:
732:
725:
722:
714:
707:
701:
698:
694:
690:
686:
680:
676:
672:
668:
661:
658:
651:
646:
643:
642:
638:
636:
633:
632:double dabble
625:
592:
586:
575:
568:
567:
561:
557:Double dabble
556:
555:
549:
542:
540:
533:
529:
157:
155:
148:
141:
134:
127:
123:
120:
112:
109:
99:
95:
91:
87:
83:
78:
74:
69:
63:
61:
59:
55:
53:
52:shift-and-add
48:
44:
40:
37:
36:double dabble
33:
19:
831:the original
796:
789:
779:, retrieved
774:
730:
724:
713:the original
700:
666:
660:
645:Lookup table
631:
629:
590:
546:
538:
528:
494:// if > 4
153:
142:
139:
128:
124:
118:
116:
110:
103:
96:
89:
85:
81:
76:
70:
67:
54:-3 algorithm
50:
35:
29:
842:Categories
781:2020-03-03
652:References
626:Historical
524:endmodule
212:// binary
182:parameter
64:Algorithm
39:algorithm
757:28360570
693:36909518
639:See also
518:// add 3
75:that is
73:register
512:'d3
230:integer
176:bin2bcd
122:digit.
58:latency
804:
755:
745:
691:
681:
245:always
215:output
173:module
34:, the
753:S2CID
716:(PDF)
709:(PDF)
689:S2CID
440:<=
383:<=
281:<=
257:begin
203:input
45:into
802:ISBN
743:ISBN
679:ISBN
616:0111
612:1010
608:0101
604:1000
600:0110
596:1001
485:>
86:ceil
84:+ 4×
735:doi
671:doi
619:243
521:end
503:bcd
497:bcd
482:bcd
419:for
362:for
353:bin
347:bcd
332:bcd
260:for
251:bin
221:bcd
218:reg
206:bin
92:/3)
30:In
844::
764:^
751:,
741:,
687:,
677:,
621:10
476:if
248:@(
224:);
191:18
179:#(
147:.
145:10
131:10
106:10
60:.
810:.
737::
673::
515:;
509:4
506:+
500:=
491:)
488:4
479:(
470:)
467:1
464:+
461:j
458:=
455:j
452:;
449:3
446:/
443:i
437:j
434:;
431:0
428:=
425:j
422:(
413:)
410:1
407:+
404:i
401:=
398:i
395:;
392:4
389:-
386:W
380:i
377:;
374:0
371:=
368:i
365:(
356:;
350:=
341:;
338:0
335:=
329:)
326:1
323:+
320:i
317:=
314:i
311:;
308:3
305:/
302:)
299:4
296:-
293:W
290:(
287:+
284:W
278:i
275:;
272:0
269:=
266:i
263:(
254:)
242:;
239:j
236:,
233:i
209:,
200:(
194:)
188:=
185:W
119:n
90:n
88:(
82:n
77:n
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
