# A logic function that is true iff the first operand is less than the second operand

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.

• Are you sure you copied the TA's answer correctly? If the last clause was $(x_{0}\;\mathrm{XOR}\; y_{0})'$ instead of $(x_{0}'\cdot y_{0})$ (and the rest was the same), you'd get a 3-bit answer for (c). – Luke Mathieson Mar 28 '15 at 9:16
• Maybe the TA was getting a little lazy and didn't write out the full XOR symbol, but it definitely looked like ⋅ to me. He was discussing the other two solutions a bit more in depth than part (c) so I feel pretty confident that I wasn't writing down a solution for part (c). – entimaniac Mar 28 '15 at 16:05
• Are you asking your homeworks in here! – M a m a D Mar 29 '15 at 8:59

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.

• If anyone wants to say, yes, that is correct, that would be appreciated too. – entimaniac Mar 28 '15 at 22:13
• In part (a), shouldn't the (a XOR b) clauses be negated - for example by the second line you know that you don't have y3 =1 and x3 = 0, so you need x3 = y3 (0 or 1, but they have to be the same). For part (b), you should have three parts, y3=0 and x3=1 is a yes (y3 is positive, x3 is negative), y3=0, x3=0, then do part (a) starting at y2/x3, and y3=1,x3=1, do part (a) starting at y2/x2, but reverse the roles of y and x (you want y2y1y0 < x2x1x0). In part (c), you're missing the negations again. – Luke Mathieson Mar 28 '15 at 22:47
• Good catch on the xor negation! Thank you for that! I've updated the answer to show that. Now I understand what you are saying needs to be checked in part (b), but after updating the XORs, are not all states checked already? I found an example problem similar to this one which seems to use the same pattern in part (b) and part (a) besides the first case, as I have done here. problem 7 at this link: people.cs.pitt.edu/~baiocchi/CS0447_S10/sols/hw3-sol.html – entimaniac Mar 29 '15 at 6:30
• Problem & part B is exactly what you want. It mixes the positive a negative cases, and only does it for 3 bit numbers, but the system is the same. – Luke Mathieson Mar 29 '15 at 6:51