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.

  • $\begingroup$ 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). $\endgroup$ – Luke Mathieson Mar 28 '15 at 9:16
  • $\begingroup$ 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). $\endgroup$ – entimaniac Mar 28 '15 at 16:05
  • $\begingroup$ Are you asking your homeworks in here! $\endgroup$ – 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)'
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.

  • $\begingroup$ If anyone wants to say, yes, that is correct, that would be appreciated too. $\endgroup$ – entimaniac Mar 28 '15 at 22:13
  • $\begingroup$ 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. $\endgroup$ – Luke Mathieson Mar 28 '15 at 22:47
  • $\begingroup$ 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 $\endgroup$ – entimaniac Mar 29 '15 at 6:30
  • $\begingroup$ 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. $\endgroup$ – Luke Mathieson Mar 29 '15 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.