Muxes, Adders, Comparators, and Gates

Question

This question is actually from one of my previous discussions, which I still don't understand how to implement. The goal is to use abstraction to design a circuit, which converts two-digit ASCII decimal numbers into 2’s complement representation.

"Recall that characters in ASCII are represented with seven bits and that the decimal digits are 0x30 (the digit 0) through 0x39 (the digit 9)."

In addition to the comparator and adder, one or more zero extention units, one or more muxes, and gates and wires are to be used.

Basically, what are the key steps and concepts which I must know to arrive at a solution to this design problem? I'm sort of aware of how an adder works, as I've done some bit-slice problems with control units to implement different functions, but I don't know how to put all of this together.

Answer 1

The steps I usually follow to find the solution are explained here. (Disclaimer:I am not an expert here.)

1. Derive the input-out relationship

The first step is to understand and express the input-output relationship in some form. You can express this relation in a convenient form. Some of the standard forms are

• mathematical expression
• truth table
• logical expression
• any combination of above

Taking your question as an example,

If 011xxxx and 011yyyy be the input digits. The last four bits of these digits represent their binary values. So xxxxyyyy is the BCD representation of the number. Converting this BCD to binary is the required operation here. And this can be done by adding lower BCD digit with ten times the upper digit. ie,

$$\mathtt{output = 1010\times xxxx + yyyy}$$

So we have obtained the input output relation here. But we don't have a multiplier to implement this relationship.

2. Re-formulate the relation in terms of available hardware

Multiplying with \$1010\$ can be done by shifting and adding as given below:

$$\mathtt{1010\times xxxx = xxxx000 + xxxx0}$$

OR

$$\mathtt{output = xxxx000 + xxxx0 + yyyy}$$

So here we have obtained the input output relationship in terms of available hardware. A 7-bit adder can do the addition. zero extension units can do the zero-padding.

Pad a zero in front of answer to make it in 2's complement form.

3. Circuit diagram/ block diagram

Once we have the input-output relation, then replacing the operators in the expression with the corresponding block/module will give you the circuit diagram.

Answer 2

Nidhin used multiplication, I'm going to use just the opposite (division) but it will really be just a bunch of subtractions, easy to do with an adder.

First, I'm going to assume all of the ASCII digits have been converted to BCD (binary coded decimal) by anding off the 0x30 (making each of the digits 4 bits instead of 8).

Let's take a couple of examples. Convert 26 (decimal) to 1A (hex)

0010 0110 => 0001 1010

The rightmost digit of our answer has a "weight" of 1, and the left digit a "weight" of 16. This because there are two four bit "nibbles" in the answer and the weight of the 5th bit is 16:

128   64   32   16       8   4   2   1

So we will be repeatedly subtracting 16 and use the number of successful subtractions as the left digit of the answer. What's left becomes the right digit.

If we subtract 16 from 26, we get ten. Since we can only do this once (without it going negative), the left digit becomes 1 and the right digit is A (10).

     26
    -16 -> 1 (since we did this once)
     ---
     10 -> A     so the answer is 1A or 0001 1010

(done because 10 < 16)

A longer example:

Convert 92 (decimal) to 5C (hex).

1001 0010 => 0101 1100

     92
    -16
    ---
     76
    -16
    ---
     60
    -16
    ---
     44
    -16
    ---
     28
    -16 -> 5 (since we subtracted 5 times, this is where the counter would be useful)
    ---
     12 -> C      so the answer is 5C or 0101 1100

(done because 12 < 16)

Note that although I am showing decimal arithmetic (e.g. 92 - 16) this is really being done in BCD -- a 4-bit nibble for each ASCII digit.

So subtracting 16 from 92 actually needs to done using a BCD adder. It's not as complicated as it seems, here's an example:

   1001 0010    92
 - 0001 0110    16
  ----------
   1000 1100    80 + -4  because it's negative, we'll add 10 back and propagate the carry
   0001 1010
  ----------
   0111 0110    76, which is the correct answer (see above)