Search code examples
assemblylogiccpuprocessoralu

Digital Comparator with Carry - How to fill the table correctly?

We got a comparator which compares 4 bit binary numbers (A_3, A_2, A_1, A_0 and B_3, B_2, B_1, B_0). The result is the output signal C_i which has the value 1 if A > B.

The arithmetic-circuit is supposed to be made up by connecting 4 identical 1 bit arithmetic-modules. Each of these 1 bit modules have the inputs A_i, B_i, C_i-1 and the output C_i with i=0,1,2,3. So, the carry outputs will be taken of the less significant digit i-1.

Given is A=0100 and B=0010. Fill the following table whereby C_i-1 bit is supposed to be chosen by you in a reasonable way. The carry C_i is 1 exactly when we have A > B.

I filled the table as good as I could but I have no idea how to do it with C_i-1...

I have read in our readings and what it's saying about C_i-1: For the compare-operations <, ≤, ≥, > a subtraction is executed and the result is read from Carry-out C_i-1

So please tell me did I fill the table correctly? Because this is a task from old exam and it has many other sub tasks. If I do the beginning (this table) wrong, then everything else will be wrong too! :(

enter image description here

I choose C_i-1 like that because I look first row A=0 and B=0, so 0-0 = 0 that's why C_i-1 =0. Second row we have A=1 and B=0, 1-0 = 1 so C_i-1=1. Then we have A=0 and B=1, 0-1 = -1 but here is problem with this, if it's correct at all : / Don't know please help me..

Solution

  • The common arithmetic predicates <, ≤, ≥, >, = are normally implemented with a subtraction.

    There are two main ways to perform a subtraction: A) Using a subtraction module or B) Using an adder.

    You didn't specify what kind of 1-bit module are you using, but from the text

    The carry C_i is 1 exactly when we have A > B

    Note that it should be A ≥ B

    we can deduce that they must be adders (full adders to be nitpicking). If they were subtraction modules the carry-out would have been 0 when A≥B because there is no borrow for the MSb when A≥B.

    The subtraction A - B is performed as A + -B where -B is the two's complement of B.
    In turn -B is performed as ~B + 1 where ~B is the NOT of B.
    Thus A - B = A + ~B + 1.

    Getting ~B from B is easy, it's just a matter of using a bunch of NOT gates (in truth they are XOR gates). However an adder only perform addition between two numbers (A and B), not three (A, B and 1).
    We can overcome this issue by noting that if we set C-1, the carry in of the first full-adder, to 1 (when normally is 0 for additions) we can add 1 to the result.

    Thus the table is

            3   2   1   0
----------------------
Ai      0   1   0   0     
Bi      0   0   1   0

Ci-1    1   0   1   1
~Bi     1   1   0   1

Ri      0   0   1   0
Ci      1   1   0   1

    C3 is 1 and indeed 4 ≥ 2.

    We can also try comparing 2 and 4:

           3   2   1   0
----------------------
Ai      0   0   1   0     
Bi      0   1   0   0

Ci-1    0   1   1   1
~Bi     1   0   1   1

Ri      1   1   1   0 
Ci      0   0   1   1

    Here C3 is 0 since 2 < 4 (and the result -2).
    Finally if A = B we have Cn = 1 since A + ~A + 1 = 2n-1 + 1 = 2n where n is the number of bits of the comparator. 2n is a n+1 bits number with only the MSb set, and the MSb is Cn.