Digital Logic Test 1

A̅⋅B + A.B̅ + A.B

= A̅ . B + A(B̅ + B)

∵ B̅ + B = 1

= A̅.B + A

∵ x + yz = (x + y).(x + z)

= (A + A̅).(A + B)

= (A + B)

• Functionally complete operations set is a set of logic functions from which any arbitrary Boolean logic function can be realized.
• Examples of functionally complete operation set are:

1. OR gate, NOT gate 
2. AND gate, NOT gate
3.  NOR gate
4. NAND gate
5.  2:1 MUX

• Any super-set of the above examples will also form a functionally complete operations set.

Explanation:

Option 2: AND gates, XOR gates and 1

A ⊕ B = AB̅ + A̅.B

F(A, B) = AB̅ + A̅.B 

By taking  B = 1

F(A, 1) = A1̅  + A̅.1 = A̅ 

AND gate, NOT gate are functionally complete operations set.

Functionally complete operations set is sufficient to implement any arbitrary Boolean function

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.

Concept:

Range of numbers in 2’s complement form with n bit: - 2^n-1 to + (2^n-1 - 1)

Range of numbers in signed form with n bit: (- 2n-1  - 1) to + (2n-1 - 1)

Calculation:

For 2’s complement

- 2n-1 ≤ -128

 2n-1 ≥ 128 

2n-1⁼ ≥ 2⁷

n ≥ 7 + 1 ≥ 8

minimum value of n is 8.

For signed form:

- (2n-1 - 1) ≤ -128

 2n-1 ≥ 128  + 1 ≥  129

n ≥ 9

Therefore the minimum number of bits required to represent -12810 in 2's complement form and signed form respectively are

Concept: 

A decoder with k input lines has 2^k output lines.

Calculation:

The memory is byte-addressable. So 64 KB = 2¹⁶ B.

16 × 2¹⁶ decoders.

So, the number of input lines (p) = 16

Number of output lines (q) = 2^p = 2¹⁶ = 65536

∴ p + q = 16 + 65536 = 65552 

Decimal conversion → binary → Hexadecimal (4 bit)

Decimal conversion → binary → Octal (3 bit)

(ABCDEF98)₁₆ = (1010 1011 1100 1101 1110 1111 1001 1000)₂

(010 101 011 110 011 011 110 111 110 011 000)₂ = (25363367630)₈

Concept:

32-bit floating-point representation of a binary number in IEEE- 754 is

Calculation:

Binary number is

0 0110010 01101100000000000000000

Here, sign bit is 0. So, number is positive.

Exponent bits = E = 01100100 = 100 (in decimal)

Mantissa bits M = 01101100000000000000000

In IEEE-754 format, 32-bit (single precision)

(-1)^s × 1.M × 2^{E – 127}

= (-1)⁰ × 1. 011011 × 2^{100 – 127}

= 1. 011011 × 2^-27

= (1 + 2^-2 + 2^-3 + 2^-5 + 2^-6) × 2^-27

= 1.421875 × 2^-27

= 22.75 × 2^-31

\(\overline {P + \bar Q + PQ} = \overline {{\rm{P}} + \left( {{\rm{\bar Q}} + {\rm{Q}}} \right).\left( {{\rm{\bar Q}} + {\rm{P}}} \right)} \)

\({\rm{F}}\left( {{\rm{P}},{\rm{\;Q}}} \right) = \overline {{\rm{P}} + {\rm{\bar Q}} + {\rm{P\;}}} = {\rm{\bar P}}.{\rm{Q}}\)

\({\rm{F}}\left( {{\rm{M}},{\rm{\;\bar N}}} \right) = {\rm{\bar M}}.{\rm{\bar N\;}}\)

a ⊙ b = a̅b̅ + ab

a ⊕ b = a̅b + ab̅

a̅ ⊕ b̅ = ab̅ + a̅b = a ⊕ b

a ⊙ b̅ = a̅b + ab̅ = a ⊕ b

a̅ ⊙ b = ab̅ + a̅ b = a ⊕ b

a ⊕ b̅ = a̅b̅ + ab = a ⊙ b

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

K – map:

Let f(A, B, C, D) = B + AD + CD

f(A, B, C, D) = B + (A + C)D

∴ f(A, B, C, D) = (A + C)D + B

(146)_b + (313)_b-2 = (246)₈

b² + 4b + 6 + 3(b-2)² + (b-2) + 3 = 2× 8² + 4×8 + 6

4b² – 7b + 19 = 166

 4b² – 7b – 147 = 0

4b² – 28b + 21b – 147 = 0

4b(b –  7) + 21(b – 7) = 0

(b – 7).(4b + 21) = 0

∴ b = 7 or b = -21 ÷ 4

Since b cannot be negative or in fraction

∴ b = 7

Alternate Method:

Substitute and check the result

b = 7

(146)₇ + (313)_7-2 = (246)₈

LHS = (146)₇ + (317)_7-2

 (146)₇ = 1 × 7² + 4 ×7¹ + 6 × 7⁰ = 49 + 28 + 6 = (83)₁₀

(313)₅ = 3 × 5² + 1 × 5 + 7× 5⁰ = 75 + 5 + 3 = (83)₁₀

LHS = (83)₁₀ + (83)₁₀ = (166)₁₀  

RHS = (246)₈

= 2 × 8² + 4 ×8¹ + 6 × 8⁰

= 128 + 32 + 6 = (166)₁₀  

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

Let’s name the circuit for our convenience.

A, B, C, and D are assumed output of the above given gates:

A = X1.Y̅1

B = X1 ⊙Y1 

C = X0.Y̅0

D = B.C

Z = A + D

Truth table

As it can be seen, wherever X > Y, Z = 1.

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 

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).

Concept:

 In IEEE- 754 single precision format, a floating-point number is represented in 32 bits.

Sign bit value 0 means positive number, and 1 means a negative number.

The floating-point number can be obtained by formula: ± 1. M × 2^(E-127)

Data:

Content of R1: 0x 42200000               (0x means Hexadecimal notation)

Content of R2: 0x C1200000

Calculation:

Content of R1 in Hex (0x) is 42200000. After converting into binary, it can be represented in IEEE- 754 format as:

Sign bit is 0 i.e. the number is positive

Biased Exponent (E’) = 100 0010 0 = 132

Normalized Mantissa (M) = 010 0000 0000 0000 0000 0000 = .25

Therefore, the number in register R1 = + 1.25 * 2^(132-127) = 1.25 × 32 = 40

Content of R2 in Hex (0x) is C1200000. After converting into binary, it can be represented in IEEE- 754 format as:

Sign bit is 1 i.e. the number is negative

Biased Exponent (E’) = 100 0001 0 = 130

Normalized Mantissa (M) = 010 0000 0000 0000 0000 0000 = .25

Therefore, the number in register R1 = - 1.25 * 2^(130-127) = -1.25 * 8 = -10

R3 = R1/R2 = 40/-10 = -4

Since the number is negative, Sign bit (MSB) = 1

Converting 4 into binary of a floating point gives: (100.0)₂

Representing it into normalized form gives:  (1.000000….) × 2²

Therefore, Mantissa is 23 bits of all 0s

Biased Exponent (E’) = E+ 127 = 2+127 = 129 = (10000001)₂

It can be represented in IEEE- 754 format as:

Converting it into Hex format gives: 0x C0800000

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 ({0, 1}) elements. So, number of such functions will be 2¹⁶ = 65,536

Concept:

 Output of T flip flop will change when T = 1 and remain same when T = 0

Excitation table for T flip flop

From this table, 

T0 = 0

T1 = Q̅1.Q̅0 + Q1Q0 = Q1 ⊙ Q0

n bit Up-counter counts from 0 to 2ⁿ – 1

x > y

From x to 2ⁿ – 1 number of pulses needed = (2ⁿ – 1) – x

From 2ⁿ – 1 to 0 number of pulses needed = 1

From 0 to y umber of pulses needed = y – 0 = y