# Muxes, Adders, Comparators, and Gates

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.

• can the input represent a negative number? Mar 5, 2015 at 5:53
• I think the problem deals strictly with positive numbers, as the hex numbers are the decimal numbers 1-9. Mar 5, 2015 at 6:11
• Can we use more than one adder? Mar 5, 2015 at 6:15
• Yes. In general, I think the problem calls for multiples of components. Mar 5, 2015 at 6:22
• Could you solve the rpoblem in a programming language, for instance C? Mar 5, 2015 at 6:32

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.

• Although you claim you're not an expert, this is a well formulated solution. Still, I'm confused on where the 1010 came from. Mar 5, 2015 at 6:56
• The representation $56$ in decimal means that the value is $5\times10+6$. So its value in hex will be $5\times A+6 = 38$, in octal will be $5\times 12+6 = 70$ and it will be $101\times 1010+110 = 111000$ in binary. Mar 5, 2015 at 7:09

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)

• This is also a correct way of doing this. In all, the final formulation that I obtained was the following: (T-x30)x10 + (U-x30). Mar 8, 2015 at 14:47
• @OmarAyala The subtractions of 0x30 are unnecessary. All that’s needed to “massage” the input is bit selection and zero extension. The circuit needs two adders and some wires, that’s it. You could literally implement it with 4 x MC14008 (each adder 4 bits wide) on a breadboard, and some wires! Fixed format optional minus support would add two 4063 magnitude comparators to detect the minus, and 10 xor gates, so 3x4070. It would still fit on a breadboard :) The whole thing could also be implemented with nothing but 4041 and 4066 used as muxes, and would be somewhat faster but use 100 chips :( Nov 8, 2022 at 23:22

ASCII digits have the lowest 4 bits already in BCD form, so nothing needs to be done there - just extract those lower 4 bits from each 8 bit ASCII value.

To multiply the more significant (left) digit by 10, you can instead multiply separately by 2 and 8, and add these products to the BCD value of the first digit. Such multiplication is shifting, or, more simply: connecting the addends to the correct bits of the adder inputs. Shifts in this approach are free!

So, assuming the ASCII inputs are H[7:0], L[7:0], the output is L[3:0] + H[3:0]×2 + H[3:0]×8 = L[3:0] + (H[3:0] SHL 1) + (H[3:0] SHL 3). The first adder needs a 6-bit output width. The second one - 7-bit output width. The range of the output is 0 to +99.

To add an optional ASCII leading minus at position S, compare S[7:0] to ASCII minus code. The comparator’s = (equals) input means “negate digit inputs”. That would control the inverters (XOR gates) to negate the input values. See this excellent answer for details. All three inputs to the adders have to be sign extended to the width of the adder they feed. The range of the 8-bit output output is then -99 to +99.