[Solved]: A logic function that is true iff the first operand is less than the second operand

Problem Detail: 

In my computer organization class I have been given a series of problems. One I'm stuck on currently is below:

Assume that $X$ consists of 4 bits, $x_3 x_2 x_1 x_0$, and $Y$ consists of 4 bits, $y_3 y_2 y_1 y_0$. Write logic functions that are true if and only if

(a) $X < Y$, where $X$ and $Y$ are thought of as unsigned binary numbers.

(b) $X < Y$, where $X$ and $Y$ are thought of as signed (two's complement) numbers.

(c) $X = Y$.

(d) Use a hierarchical approach that can be extended to larger numbers of bits. Show how can you extend it to 8-bit comparison (that is, if $X$ and $Y$ are 8-bit numbers, how to implement the above three comparisons).

For all of them I understand the what makes each case true. I'm even aware of the simple method of writing a truth table and listing out the logic functions that make each case true, however that approach would make a table 256 rows tall.

I'm stuck a bit on how to write out the logic. The real confusion actually comes from the TA in the class. He gave an example using 3-bit numbers. I believe he was using the case of $X < Y$ still. His solution was: $(x_2 \;\mathrm{XOR}\; y_2)' \cdot (x_1 \;\mathrm{XOR}\; y_1)' \cdot (x_0' \cdot y_0)$

Is this the full answer for the case of 3-bit numbers for part (a)? I understand it this solution, but I feel there is more. For example, $(x_2 \;\mathrm{XOR}\; y_2)'$ checks if the most significant bits are equal, which gives reason to move onto the next portion of the function, but if $x_2$ is 0 while $y_2$ is 1, then that means $x$ is smaller and the function needs to become true, but I don't see how that is a possible outcome with that example solution.

Asked By : entimaniac

Answered By : entimaniac

I haven't heard back from my professor or my TA yet, nor has anyone posted a solution yet, but I'm been thinking long and hard. It was a bit of a rush when the TA went over his solution, but maybe I wrote down a partial solution. So going off of that idea, I came up with:

Problem 4: a.  x < y iff unsigned:     x3' . y3 +   (x3 XOR y3)'  .  x2' . y2 +   (x3 XOR y3)'  .  (x2 XOR y2)'  .  x1' . y2 +   (x3 XOR y3)'  .  (x2 XOR y2)'  .  (x1 XOR y2)'  .  x0' . y0 b. x < y iff signed:     x3 . y3' +   (x3 XOR y3)'  .  x2' . y2 +   (x3 XOR y3)'  .  (x2 XOR y2)'  .  x1' . y2 +   (x3 XOR y3)'  .  (x2 XOR y2)'  .  (x1 XOR y2)'  .  x0' . y0 c. x = y iff     (x3 XOR y3)'  .  (x2 XOR y2)'  .  (x1 XOR y2)'  .  (x0 XOR y0)' d. Assume x,y consist of i bits. a.  xi-1' . yi-1 +    (xi-1 XOR yi-1)'  .  xi-2' . yi-2 +    … +   (xi-1 XOR yi-1)'  .   . . .    .  xi-i' . yi-i b.  xi-1 . yi-1' +    (xi-1 XOR yi-1)"  .  xi-2' . yi-2 +    … +    (xi-1 XOR yi-1)'  .   . . .    .  xi-i' . yi-i  c.  (xi-1 XOR yi-1)'  .   . . .    .  (xi-i XOR yi-i)'  Assume i = 8. a.  x8-1' . y8-1 +    (x8-1 XOR y8-1)'  .  x8-2' . y8-2 +    … +    (x8-1 XOR y8-1)"  .   . . .    .  (x8-7 XOR y8-7)'  .  x8-8' . y8-8 b.  x8-1 . y8-1' +    (x8-1 XOR y8-1)'  .  x8-2' . y8-2 +    … +    (x8-1 XOR y8-1)'  .   . . .    .  (x8-7 XOR y8-7)'  .  x8-8' . y8-8  c.  (x8-1 XOR y8-1)'  .   . . .    .  (x8-7 XOR y8-7)'  .  (x8-8 XOR y8-8)' 

If you see anything wrong with this solution, let me know.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40809