GATE Computer Science Engineering(CSE) 2027 Test: Boolean Operations Free

Look-ahead carry generator gives output in constant time if the fan in = number of inputs.  

For example, it will take  O(1) to calculate   , if the OR gate with 5 inputs is present.
If we have 8 inputs, and OR gate with 2 inputs, to build an OR gate with 8 inputs, we will need 4 gates in level-1, 2 in level-2 and 1 in level-3. Hence 3 gate delays, for each level.
Similarly, an n-input gate constructed with 2-input gates, the total delay will be O(log n).
Hence answer is option B.

in case of -1  we get bit sequence 11111111 adding this we get a carry upto carry flag,so largest time to ripple !

For N = 64 bits
Suppose you want to build a 64 bit adder then you need 16 4-bit ALU and 16 4-bit carry generator, at this point there will be 16 carries that will ripple through these 16 ALU modules, to speed up the adder we need to get rid of these 16 rippling carries, now we can again use 4 4-bit carry generator to generate these 16 carries, now we have only 4 carries to ripple through, again we can use the same trick to minimize the rippling of these 4 carries, we can use an additional 4-bit carry generator which will generate these carry and we are done :) there will be no more propagation of carry among the ALU modules.
So the we have used 3 level of 4-bit carry generator, and the time taken to add 64 bits will be proportional to 3 which is log₄64.
So in general to add N-bits it takes Log₄N time.

For LSB addition we do not need a full adder for addition of subsequent bits we need full adders since carry from previous addition has to be fed into the addition operation

It would take 6 time units.


XOR can be implemented in 2 levels; level-1 ANDs and Level-2 OR. Hence it would take 2 time units to calculate  P_i and S_i 
The 4-bit addition will be calculated in 3 stages


Level-2 we get the carries by computing the disjunction (OR).
3. (2 time units) Finally we compute the Sum in 2 time units, as its an XOR operation.
Hence the total is 2 + 2 + 2 = 6 time units.

In a N X M array multiplier we have N * M AND gates and (M-1) N bit adders used.
Total delay in N X M (N>=M) array multiplier due to AND gate in partial products at all level is just 1 unit AND gate delay as the operation is done parallel wise at each step. Now delays at level 1 to (M-1) is = (M-1)*delay due to 1 unit of N bit adder.  Therefore the maximum gate delay is O(M) but here M=N therefore O(N).

Take A = A1 A2 A3 A4
B =   B1 B2 B3 B4 

Now to multiply these two numbers.  
1 and gate require b1 multiply with a1 a2 a3 a4. 
1 and gate require b2 multiply with a1 a2 a3 a4. 
1 and gate require b3 multiply with a1 a2 a3 a4.
1 and gate require b4 multiply with a1 a2 a3 a4.  
 Now 3 or gate require.
Total 7 gates are required for 4 bit take n bit u find 2n-1.
So time complexity will be = ϴ(n)

A Boolean function of 4 variables is a function from a set 2⁴ = 16 of elements (all combinations of 4 variables) to a set of 2  elements. So, number of such functions will be 2¹⁶ = 65,536

Statement 1 :  x + y + z = 1
Till now, all the options are possible.

Statement 2 : x y = 0
Since LHS ≠ 0, B is not possible.

Statement 3 : x z + w = 1
Since LHS ≠ 1, A and D are not possible.

Statement 4 : x y + z’ w’ = 0
Thus, C is the correct option.

These are properties of XOR function. 

The expression Y = AB' + (A' + B)C can be simplified using Boolean algebra rules. First, distribute C across the terms in the parentheses: Y = AB' + (A' + B)C = AB' + A'C + BC. This expression AB' + A'C + BC represents the fully simplified form according to Boolean algebra.

From A + B = 1 and AB = 0
We get either of A,b is 1 and another is 0.
Now AC = BC ,here C has to be 0 (because A,b  has different values)
C = 0
Now A + C = 1
So, A = 1 and Ab = 0, So,  B = 0
So we get
A = 1, B = 0 , C = 0
These are the values.

(A’B + CD’)’ = (A’B)'(CD’)’ = (A” + B’)(C’ + D”) = (A + B’)(C’ + D).

The expression for Associative property is given by A+(B+C) = (A+B)+C & A*(B*C) = (A*B)*C.
The expression for Commutative property is given by A+B = B+A & A*B = B*A.
The expression for Distributive property is given by A+BC=(A+B)(A+C) & A(B+C) = AB+AC.

x'y' + x'y = x'(y+y') = x'
x' + xy = x' + y

So, the equivalent expression will be A'C + AC' + AB' 

P:
Y * Z = Y * (X*Y)
= Y * (XY + X'Y')
= Y (XY + X'Y') + Y' (XY + X'Y')'
= XY + Y' ((X' + Y') (X+ Y))
= XY + Y' (X'Y + XY')
= XY + XY'
= X(Y + Y')
= X
So, P is valid.
Q: 
X * Z = X * (X*Y)
= X * (XY + X'Y')
= X (XY + X'Y') + X' (XY + X'Y')'
= XY + X' ((X' + Y') (X+ Y))
= XY + X' (X'Y + XY')
= XY + X'Y
= Y(X + X')
= Y
So, Q is also valid.
R:
X * Y * Z = (X * Y) * (X * Y)
= (XY + X'Y') * (XY + X'Y')
= (XY + X'Y') (XY + X'Y') + (XY + X'Y')' (XY + X'Y')'
= (XY + X'Y') + (XY + X'Y')' (Since, AA = A)  = 1 (Since A + A' = 1)
So, R is also valid. 
Hence, D choice.

The expression for Associative property is given by A + (B + C) = (A + B) + C & A * (B * C) = (A * B) * C. 
The expression for Commutative property is given by A + B = B + A & A * B = B * A. 
The expression for Distributive property is given by A + BC = (A + B)(A + C) & A(B + C) = AB + AC.

A: means both are either true OR both are false. then it will be true = ExNOR
B & C: Whenever any one of the literal is complemented then ExOR can be turned to ExNOR and complement sign on the literal can be removed. So these two also represents ExNOR operation of x and y.
Hence, the correct answer is option D it is the ExOR operation b/w the two.

XOR is associative and commutative. Also,

Option C (wx'(y+xz')+w'.x')y = (wx'y+wx'xz'+w'x')y  =
xx' = 0.
So
Wx'y+w'x'y = x'y(w+w') = x'y

1. Every logic gate follows Commutative law.
2. AND, OR, Ex-OR, EX-NOR follows Associative law also. NAND, NOR doesn’t follow Associative law.

x OR 1 = 1 and so x NOR 1 = 0.

Partial product is calculated by using bit pair recording in booths algorithm, which is improvement technique used in booths algorithm. Here we consider 3 bits at a time for getting the partial product. This eliminates the worst case behaviour of normal Booth's algorithm.
"100" corresponds to -2M and "111" corresponds to 0 -2 X(i+1) + x (i) + X(i-1)

The worst case of an implementation using Booth’s algorithm is when pairs of 01s or 10s occur very frequently in the multiplier.

There are 2 ways for answering This questions.
Way 1 -> Convert 57 to Binary & Get 2's complement. It is "11000111" & Attach one extra 0 to right of it
110001110

To calculate booth code subtract right digit from left digit in every consecutive 2 digits.
So 11-> 0 , 10 -> +1, .. finally 10 -> +1