How do you write a logic function to determine if one 2s complement binary number is less than another?

Question

Working on logic design in class, and I'm trying to figure out how to write a specific logic function [and by write, I mean something along the lines of (x NOR y) OR (a NOR b), for example]

It asks to assume 2 variables, X and Y, both of which consist of 3 bits (x2,x1,x0, and y2,y1,y0). I need to write a logic function that is true if and only if X < Y, assuming that they are signed 2's complement numbers.

I have somewhat of an idea of how to form a logic circuit that accomplishes this by subtracting and checking if the result is negative, which would use full-adders to add X to Y's inverse plus 1. I'm just struggling to figure out how to actually write that down in the form I stated above.

Edit: I really wasn't able to wrap my head around how to write this down as a function, so I went and made an adder/subtractor using a logic gate simulator:

and I worked up from bit 0, piecing together each logic equation:

Bit 0's sum is:

(x0 XOR y0') XOR (Cin0)

Bit 0's carry out is:

(Sum w/o carry-in) XOR (x0 AND y0')

Which is the same as:

((x0 XOR y0') AND (Cin0)) OR (x0 AND y0')

That then becomes the carry-in (Cin) of bit 1:

((x1 XOR y1') AND (((x0 XOR y0') AND (Cin0)) OR (x0 AND y0'))) OR (x1 AND y1'))

Then finally, for bit 2 (the sign bit), I dropped the carry out, plugging in bit 1's carry out to bit 2's carry in:

(x2 XOR y2') XOR (((x1 XOR y1') AND (((x0 XOR y0') AND (Cin0)) OR (x0 AND y0'))) OR (x1 AND y1'))

The first carry-in, Cin0, is 1 for the purpose of converting from a signed 2s complement number. Then the function just checks whether or not the sign bit is on or off, b/c if x - y is negative, then x < y.

I did x = -1 and y = 3 for an example (in 2s complement, those are 111 and 011 respectively)

I feel like this is all really, really convoluted though, and I can't help but wonder if I've messed up somewhere along the way, or if I'm overthinking this. I just can't visualize how the logic works without... well, visuals.

Answer 1

This page shows you the formula for a one-bit subtractor with borrows in and out. You can use this as a building block for a three-bits subtractor: https://www.geeksforgeeks.org/full-subtractor-in-digital-logic/.

$$D=(A\oplus B)\oplus B_{\text{in}}\\B_{\text{out}}=((\lnot A)\land (B_{\text{in}}\lor B))\lor(B\land B_{\text{in}})$$

You can eliminate the intermediate borrow variables if you want.

Answer 2

For each bit, you can XOR to check if they are different (if they are not, then no need to compare) and if they are different, you can use the value in Y (if (X,Y) is (0,1) we need to return true) and or the results together. If all the XORs return 0, the two numbers are equal. Now to implement your specific question, you just need to OR the different results together.

Answer 3

If you have just two bit values A and B, then(A > B) = A AND NOT B, and (A >= B) = A OR NOT B.

With two bits A1,A2 and B1,B2 (A > B) = (A1 > B1) OR (A1 >= B1) AND (A2 > B2), (A >= B) = (A1 > B1) OR (A1 >= B1) AND (A2 >= B2).

You can add more bits in the same way. Creating a circuit, you’d check what logic is repeated.