0
\$\begingroup\$

We all know the Double Dabble algorithm, it works great for Binary to BCD conversion, but what about a BCD to binary algorithm or decoder? I am trying to make a calculating machine but I could not come up or find algorithms for BCD to binary conversion, I need one as soon as possible. Help is very appreciated.

Edit: I am sorry, I did not do a very good job at specifying the details of this question. I will keep this in mind the next time I ask. Thank you all for your answers :)!

\$\endgroup\$
  • \$\begingroup\$ "What about...?" Isn't really a question. Can you precisely ask something that we can answer? \$\endgroup\$ – Marcus Müller Apr 6 '18 at 15:59
  • 1
    \$\begingroup\$ Can you think of a straight-forward algorithm? Such as multiplying the decimal digits by a corresponding power of 10? \$\endgroup\$ – Eugene Sh. Apr 6 '18 at 16:18
  • 1
    \$\begingroup\$ "We all know the Double Dabble algorithm..." Quite a bold assumption there. I've never heard of it... Do you mind explaining it to us? \$\endgroup\$ – KingDuken Apr 6 '18 at 16:18
  • 2
    \$\begingroup\$ @KingDuken My though too, but was embarrassed to admit :) \$\endgroup\$ – Eugene Sh. Apr 6 '18 at 16:19
  • \$\begingroup\$ "shift-add-three" in reverse becomes "minus-three-shift". Where you minus three if any 4-bit chunk you find is greater or equal to 8. \$\endgroup\$ – Tom Carpenter Apr 6 '18 at 16:48
1
\$\begingroup\$

You are familiar with Double Dabble (shift-add-three):

Shift-Add-3

The nice thing about this algorithm is that it is 100% reversible. You can use the same algorithm to convert from BCD to binary by reversing the operations.

The typical steps are:

  • Check each group of digits:
    • If >= 5, then Add 3
    • Else stay the same
  • Left shift the input into the digits

To reverse these operations, you perform them in the reverse order

  • Right shift the digits into the output
  • Check each group of digits:
    • If >= 8, then Minus 3
    • Else stay the same

So the example becomes:

Minus-3-Shift

\$\endgroup\$
  • \$\begingroup\$ While this is a good answer from Tom, it doesn't meet the specifications and what the Collatz Problem that you just told me about... This entire page with answers and comments trying to understand what you were talking about is creating a large mess LOL. \$\endgroup\$ – KingDuken Apr 6 '18 at 17:13
  • \$\begingroup\$ @KingDuken The question is not about the Collatz conjecture nut just about the input to the machine computing it. Don't take it personally :) \$\endgroup\$ – Eugene Sh. Apr 6 '18 at 17:14
  • \$\begingroup\$ It does @KingDuken, Tom's answer is the best so far. Sorry for my vagueness though. \$\endgroup\$ – Konrad Zuse Apr 6 '18 at 17:14
  • \$\begingroup\$ @EugeneSh. LOL :) aw shucks \$\endgroup\$ – KingDuken Apr 6 '18 at 17:15
  • \$\begingroup\$ I may be missing how this applies with 491. After one of the shifts, there are two BCD digits suddenly requiring -3 at the same time. \$\endgroup\$ – jonk Apr 6 '18 at 17:21
2
\$\begingroup\$

For a single digit, BCD is binary; you can use it as-is.

For the tens digit, you need to multiply the BCD representation by 1010b (10d) and add it to the units digit. You can do that with two adders. Since the maximum value will be 99, the result will be 7 bits wide, with the least-significant bit coming directly from the units digit; the adders themselves will be 4 and 6 bits wide.

For the hundreds digit and higher, you could proceed analogously, multiplying by the binary representation of 100, 1000, etc and summing the partials. This will give you a purely combinatorial circuit, albeit one that's not necessarily very fast in terms of gate-delays.

Alternatively, you could build a sequential circuit which operates one digit at a time, starting with the most significant. At each step you multiply the running total by 1010b, then add the next digit. The adders will need to be wider than in the "tens digit" example above, but the total amount of hardware should be less. This is a logical method for handling calculator keypad input, since the digits will be supplied in the correct sequence anyway.

\$\endgroup\$
1
\$\begingroup\$

I know don't know what the Double Dabble Algorithm is but after looking it up, I've come to the conclusion that it has to do with shifting in registers. In fact, this looks like something I recently learned in my graduate course in digital communication systems: The Convolutional Encoder where you send each bit from left to right.

Digressing... Anyways if you want to convert BCD to binary, you simply take each segment of the BCD, find the decimal value, and convert it to binary.

Let me show you an example:

BCD Value: 0011 0110 0001

Take each segment an convert it to decimal: 0011 -> 3, 0110 -> 6, 0001 -> 1
The decimal value you get from the BCD value is: 361

Convert 361 to binary: 361 -> 0101101001

This is the easiest way to convert BCD to binary. There are other algorithms out there like creating your own LUT (look-up table) which might be more practical for machine purposes. I also ran into this interesting integrated circuit that converts BCD to binary and vice versa. Try looking at this and maybe it can give you a good idea on how to implement this with hardware.

\$\endgroup\$
  • \$\begingroup\$ Yes, but I need to implement this in hardware and computers don't understand our decimal digits. I cannot use a look up table because 16 bits have 64K possible combinations, which would take a lot of time to build. @KingDuken \$\endgroup\$ – Konrad Zuse Apr 6 '18 at 16:50
  • 2
    \$\begingroup\$ You didn't specify this in your question. How was I supposed to know? :) When you ask questions on here, make sure you are as specific as possible about what you're trying to accomplish. \$\endgroup\$ – KingDuken Apr 6 '18 at 16:56
  • \$\begingroup\$ Oh, okay. I joined yesterday and this was my first question, sorry for vagueness. \$\endgroup\$ – Konrad Zuse Apr 6 '18 at 16:58
  • \$\begingroup\$ Well, I actually addressed the "Convert 361 to binary" thing in my first comment. Just multiply each digit by a power of 10 and add them up. Easy to do in the hardware. The multiplication can be done by small LUTs. \$\endgroup\$ – Eugene Sh. Apr 6 '18 at 16:59
  • \$\begingroup\$ There's really no info in the hardware implementation that you need! Are the bcd digits coming in serially, parallel? What about the bits of the output? Is this clocked logic (in which case youd really only need a 10-LUT and a fixed ×10 multiplier) or does it need to be combinatorial? \$\endgroup\$ – Marcus Müller Apr 6 '18 at 17:02
0
\$\begingroup\$

Since you asked for hardware here is some psuedo-verilog. We assume that the input comes one digit at a time, most significant digit first.

always @posedge(clk) begin
  if (digitstrobe) begin
    if (firstdigit) begin
      result <= digit;
    end else begin
      result <= (result * 10) + digit;
    end
  end
end
\$\endgroup\$
  • \$\begingroup\$ Thank you, @Peter Green! Though I appreciate Tom Carpenter's solution a bit more, this one is also good for a sequential implementation. \$\endgroup\$ – Konrad Zuse Apr 6 '18 at 17:12
  • \$\begingroup\$ It's not necessary to distinguish the first digit from the rest, as long as you initialise the running result to zero before accepting any digits. The first step will then be "(0 * 10) + most-significant-digit". \$\endgroup\$ – Chromatix Apr 6 '18 at 17:16
  • \$\begingroup\$ Indeed, you could have a version with a reset input instead of a firstdigit input. You need something to end work on one number and start work on the next though. \$\endgroup\$ – Peter Green Apr 6 '18 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.