1

My Task

I'm working on an extra work question our teacher assigned us from the book. Design a combinatorial circuit that compares two 4-bit unsigned numbers A and B to see whether B is greater than A. The circuit has one output X, so that X = 1 if A < B and X = 0 if A = B or A > B.

My Ideas

I had 2 ideas, but neither are very good. 1 was to get 2's complement version of A(positive) and B(negative). I could then add them together and if we had a negative, it would be obvious that B is greater than A. The leading bit would be 1 so I would just negate the leading bit and have that be my output. Else it would output 1. This is almost a solution, but I don't think it would work if we had A = B because then the leading bit would be 0 but we would have an output of 1 which would indicate A>B when in fact A = B.

My second idea was to split each number into 4 bits, and compare the bits of each number and find out that way. This would require a 256 row truth table though, and I'd rather just not answer the question than write that out.

Neither of my approaches really seem feasible(I don't even feel as though they accomplish the task). Can anyone suggest a hint as to what would be a good approach or idea to accomplish this task? (Not looking for a full out solution, just something to get me started)

Dunka
  • 113
  • 3
  • 9
  • Your truth table will have far fewer than 256 actual rows, since only 1 of every 4 conditions can be true. – Ignacio Vazquez-Abrams Mar 01 '15 at 02:03
  • @IgnacioVazquez-Abrams as in, it's only true when A = 1 and B = 0, otherwise we have A=B or A – Dunka Mar 01 '15 at 02:20
  • I count 12 rows. Lesser significant bits don't matter it the more significant bits determine the result. – Ignacio Vazquez-Abrams Mar 01 '15 at 02:26
  • @IgnacioVazquez-Abrams I'm kind of confused by that statement, the LSB sometimes determine the which is greater like 0000 vs 0001 – Dunka Mar 01 '15 at 02:32
  • But never with 0b1000 vs. 0b0000 through 0b0111. – Ignacio Vazquez-Abrams Mar 01 '15 at 02:35
  • So there are ranges where the MSB can tell us which value is bigger. And I don't have to worry about what value the other bits are(they become don't care inputs). But how would I find all these ranges? – Dunka Mar 01 '15 at 02:49
  • By thinking about it. 1s toward the MSB means that you can ignore all lesser bits. – Ignacio Vazquez-Abrams Mar 01 '15 at 02:57
  • If you want to compare your answer to an optimized result, you can look at the internal diagram of ICs designed for this purpose (eg. 74HCxx). I don't think this violates the spirit of not doing homework for the OP as they still have to show the work in deriving the result. – Spehro Pefhany Mar 01 '15 at 03:13
  • @SpehroPefhany thanks for the suggestion but I'm not really sure what an IC is – Dunka Mar 01 '15 at 03:18
  • Integrated circuit. Look up [74HC85](http://www.nxp.com/documents/data_sheet/74HC_HCT85_CNV.pdf) when you have got your answer. – Spehro Pefhany Mar 01 '15 at 03:26

2 Answers2

3

If you want to find the largest number between two unsigned numbers A and B, all you need to look at is the most significant bit where the bits in A and B are not the same, the larger number is the number that will have a '1' at that point and the smaller number will be the number that will have a '0' at that point. e.g if

$$ \text{A} = 1100\\ \text{B} = 1011 $$

then A is bigger than B because at the most significant bit where the bit number's aren't the same (bit index 2 in this case) A is 1 and B is 0.

So to solve this problem, we can start by defining a variable X\$_i\$, where X\$_i\$ is high if i) the bits of A and B in the current bit index are not the same, ii) all bits of A and B have been the same in all indexes greater that the current index and iii) the bit of value of B in the current index, B\$_i\$, is high.Using this logic we can extract the values of X\$_i\$ = {X\$_3\$ X\$_2\$ X\$_1\$ X\$_0\$} as being

$$ X_3 = B_3(A_3 \mathbin{\oplus} B_3) \\ X_2 = B_2(A_2 \mathbin{\oplus} B_2) .\overline{(A_3 \mathbin{\oplus} B_3)} \\ X_1 = B_1(A_1 \mathbin{\oplus} B_1) .\overline{(A_2 \mathbin{\oplus} B_2)} . \overline{(A_3 \mathbin{\oplus} B_3)} \\ X_0 = B_0(A_0 \mathbin{\oplus} B_0) . \overline{(A_1 \mathbin{\oplus} B_1)}. \overline{(A_2 \mathbin{\oplus} B_2)} . \overline{(A_3 \mathbin{\oplus} B_3)} $$

we can then get our final result X as

$$ X = X_3 + X_2 + X_1 + X_0 $$

KillaKem
  • 1,740
  • 2
  • 13
  • 26
  • What I ended up doing was saying, we have three possibilities: AB,A=B. Made a truth table and K-map for those three possibilities and reduced it down to f = A>B. I ended up only needing a circuit to determine equality and a circuit to determine if A>B(We need the equality circuit to determine A>B). – Dunka Mar 02 '15 at 01:27
3

Actually in some applications your lookup table idea would be how it's done. It uses a fair amount of read-only memory to accomplish the task, but has the advantage of all solutions being found within a single read cycle.

You are correct in that this lookup table would have 256 entries. You have a total of 8 bits in that each can be any value. 28 = 256.

Another way to think about this problem is to figure out what you'd need to know at any one bit position to decide the answer. Suppose you knew whether the higher order digits were greater than, less than, or equal. In the case of greater than or less than, the digits to your left have already determined the outcome. In the case of equal to, your bit will determine the outcome if they are different.

Now come up with the logic that takes in the three possible states from the higher bits, the two bits it has to compare, and produces the three possible states out to pass to the same logic for the next bit down. You should be able to construct a logic circuit using this method that works on arbitrarily large numbers, with the time to find the solution proportional to the number of bits in the numbers. Also note that the top bit is a special case. You can think of it as implicitly knowing all bits to the left are equal.

Olin Lathrop
  • 310,974
  • 36
  • 428
  • 915