Category: Digital Design

Carry Look Ahead Adder | 4-bit Carry Look Ahead Adder

Ripple Carry Adder-

 

Before you go through this article, make sure that you have gone through the previous article on Ripple Carry Adder.

 

In Ripple Carry Adder,

  • Each full adder has to wait for its carry-in from its previous stage full adder.
  • Thus, nth full adder has to wait until all (n-1) full adders have completed their operations.
  • This causes a delay and makes ripple carry adder extremely slow.
  • The situation becomes worst when the value of n becomes very large.
  • To overcome this disadvantage, Carry Look Ahead Adder comes into play.

 

 

In this article, we will discuss about Carry Look Ahead Adder.

 

Carry Look Ahead Adder-

 

  • Carry Look Ahead Adder is an improved version of the ripple carry adder.
  • It generates the carry-in of each full adder simultaneously without causing any delay.
  • The time complexity of carry look ahead adder = Θ (logn).

 

Logic Diagram-

 

The logic diagram for carry look ahead adder is as shown below-

 

 

Carry Look Ahead Adder Working-

 

The working of carry look ahead adder is based on the principle-

The carry-in of any stage full adder is independent of the carry bits generated during intermediate stages.

 

The carry-in of any stage full adder depends only on the following two parameters-

  • Bits being added in the previous stages
  • Carry-in provided in the beginning

 

Now,

  • The above two parameters are always known from the beginning.
  • So, the carry-in of any stage full adder can be evaluated at any instant of time.
  • Thus, any full adder need not wait until its carry-in is generated by its previous stage full adder.

 

Also Read- Full Adder Working

 

4-Bit Carry Look Ahead Adder-

 

Consider two 4-bit binary numbers A3A2A1A0 and B3B2B1B0 are to be added.

Mathematically, the two numbers will be added as-

 

 

From here, we have-

C1 = C0 (A0 ⊕ B0) + A0B0

C2 = C1 (A1 ⊕ B1) + A1B1

C3 = C2 (A2 ⊕ B2) + A2B2

C4 = C3 (A3 ⊕ B3) + A3B3

 

For simplicity, Let-

  • Gi = AiBi where G is called carry generator
  • Pi = Ai ⊕ Bi where P is called carry propagator

 

Then, re-writing the above equations, we have-

C1 = C0P0 + G………….. (1)

C2 = C1P1 + G1 ………….. (2)

C3 = C2P2 + G2 ………….. (3)

C4 = C3P3 + G3 ………….. (4)

 

Now,

  • Clearly, C1, C2 and C3 are intermediate carry bits.
  • So, let’s remove C1, C2 and C3 from RHS of every equation.
  • Substituting (1) in (2), we get C2 in terms of C0.
  • Then, substituting (2) in (3), we get C3 in terms of C0 and so on.

 

Finally, we have the following equations-

  • C1 = C0P0 + G
  • C2 = C0P0P1 + G0P1 + G1
  • C3 = C0P0P1P2 + G0P1P2 + G1P2 + G2
  • C4 =C0P0P1P2P3 + G0P1P2P3 + G1P2P3 + G2P3 + G3

 

These equations are important to remember.

 

These equations show that the carry-in of any stage full adder depends only on-

  • Bits being added in the previous stages
  • Carry bit which was provided in the beginning

 

Trick To Memorize Above Equations-

 

As an example, let us consider the equation for generating carry bit C2.

There are three possible reasons for generation of C2 as depicted in the following picture-

 

 

In the similar manner, we can write other equations as well very easily.

 

Implementation Of Carry Generator Circuits-

 

The above carry generator circuits are usually implemented as-

  • Two level combinational circuits.
  • Using AND and OR gates where gates are assumed to have any number of inputs.

 

Implementation Of C1

 

  • The carry generator circuit for C1 is implemented as shown below.
  • It requires 1 AND gate and 1 OR gate.

 

C1 = C0P0 + G0

 

Implementation Of C2

 

  • The carry generator circuit for C2 is implemented as shown below.
  • It requires 2 AND gates and 1 OR gate.

 

C2 = C0P0P1 + G0P1 + G1

 

Implementation Of C3 & C4

 

Similarly, we implement C3 and C4.

  • Implementation of C3 uses 3 AND gates and 1 OR gate.
  • Implementation of C4 uses 4 AND gates and 1 OR gate.

 

Total number of gates required to implement carry generators (provided carry propagators Pi and carry generators Gi) are-

  • Total number of AND gates required for addition of 4-bit numbers = 1 + 2 + 3 + 4 = 10.
  • Total number of OR gates required for addition of 4-bit numbers = 1 + 1 + 1 + 1 = 4.

 

General Formula-

 

The following formula is used to calculate number of gates required for evaluating all carry bits-

 

For a n-bit carry look ahead adder to evaluate all the carry bits, it requires-

  • Number of AND gates = n(n+1) / 2
  • Number of OR gates = n

 

Advantages of Carry Look Ahead Adder-

 

The advantages of carry look ahead adder are-

  • It generates the carry-in for each full adder simultaneously.
  • It reduces the propagation delay.

 

Disadvantages of Carry Look Ahead Adder-

 

The disadvantages of carry look ahead adder are-

  • It involves complex hardware.
  • It is costlier since it involves complex hardware.
  • It gets more complicated as the number of bits increases.

 

To gain better understanding about Carry Look Ahead Adder,

Watch this Video Lecture

 

Next Article- Neutral Functions

 

Get more notes and other study material of Digital Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Alternative Logic Gates | Bubbled Gates | Logic Gates

Logic Gates-

 

Before you go through this article, make sure that you have gone through the previous article on Logic Gates.

 

We have discussed-

  • Logic gates are the basic building blocks of any digital circuit.
  • Logic gates are classified as-

 

 

In this article, we will discuss about Alternative Logic Gates.

 

Alternative Logic Gates-

 

Alternative logic gate is an alternate logic gate that produces the same output as the original logic gate

and can be used during the unavailability of the original logic gate to serve the same purpose.

 

Alternative logic gates are also called as Alternate Gates.

Alternative logic gates are also called as Bubbled Gates since they contain bubbles in them.

 

The following table shows the original logic gate and its corresponding alternate gate-

 

 

Also Read- Universal Logic Gates

 

Rules To Memorize Alternative Logic Gates-

 

The following rules are helpful in drawing an alternate logic gate for a given logic gate-

 

For AND, NAND, OR & NOR Gates-

 

  • Both the inputs of alternative gate will have bubbles (which represents NOT gate).
  • For AND structured original gate, alternative gate will be OR structured.
  • For OR structured original gate, alternative gate will be AND structured.
  • If bubble is present at the output of original gate, then no bubble will be present at the output of alternative gate.
  • If bubble is not present at the output of original gate, then a bubble will be present at the output of alternative gate.

 

For EX-OR & EX-NOR Gates-

 

  • One of the inputs of alternative gate will have a bubble (which represents NOT gate).
  • For EX-OR structured original gate, alternative gate will be EX-NOR structured.
  • For EX-NOR structured original gate, alternative gate will be EX-OR structured.
  • If bubble is present at the output of original gate, then no bubble will be present at the output of alternative gate.
  • If bubble is not present at the output of original gate, then a bubble will be present at the output of alternative gate.

 

To gain better understanding about Alternative Logic Gates,

Watch this Video Lecture

 

Next Article- Latches & Flip-Flops

 

Get more notes and other study material of Digital Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Self-Dual Functions | Dual Of Boolean Expression

Dual Of Boolean Expression-

 

To get a dual of any Boolean Expression, replace-

  • OR with AND i.e. + with .
  • AND with OR i.e. . with +
  • 1 with 0
  • 0 with 1

 

Dual of Boolean Expression Examples-

 

Following are examples of dual of Boolean Expressions-

 

Example-01:

 

  • Consensus  theorem is xy + x’z + yz = xy + x’z
  • Dual of Consensus theorem is (x + y)(x’ + z)(y + z) = (x + y)(x’ + z)

 

Example-02:

 

  • Boolean expression is xyz + x’yz’ + y’z = 1
  • Dual of the above Boolean expression is (x + y + z)(x’ + y + z’)(y’ + z) = 0

 

Self-Dual Functions-

 

When a function is equal to its dual, it is called as a Self dual function.

 

Example-

 

Consider the function : F (A , B , C) = AB + BC + CA

 

The dual of this function is-

Fd (A , B , C)

= (A + B)(B + C)(C + A)

= AB + BC + CA

 

Clearly, F (A , B , C) = Fd (A , B , C)

∴ F (A , B , C) is a self-dual function.

 

Conditions For Self-Dual Function-

 

The necessary and sufficient conditions for any function to be a self-dual function are-

  • The function must be a Neutral Function.
  • The function must not contain any mutually exclusive terms.

 

Mutually Exclusive Terms

 

Consider we have any term X consisting of some variables.

Then, a term obtained by complementing each variable of term X is called as its mutually exclusive term.

 

Examples-

 

  • (ABC , A’B’C’) are mutually exclusive terms.
  • (AB’C , A’BC’) are mutually exclusive terms.

 

Number of Self-Dual Functions-

 

 

Here n = number of Boolean variables in the function.

 

Explanation-

 

  • For a function to be a self-dual function, the function must be a neutral function.
  • For a function to be a neutral function, number of minterms must be equal to number of maxterms.
  • So, we choose half of the terms i.e. 2n / 2 = 2n-1 terms.
  • Now, for each of these terms, we have two choices whether to include it or not in the self-dual function.

 

So, possible number of self-dual functions

= 2 x 2 x 2 x ……. x 2n-1

= 22^(n-1)

 

Relationship Between Neutral Functions & Self-dual Functions-

 

  • Every self-dual function is surely a neutral function.
  • But every neutral function need not be a self-dual function.

 

 

Important Property of Self-Dual Functions-

 

Self-duality is closed under complementation.

 

Example-

 

  • If the function F (A , B , C) = ∑ (0 , 1 , 2 , 4) is a self-dual function.
  • Then, its complement function F’ (A , B , C) = ∑ (3 , 5 , 6 , 7) will also be a self-dual function.

 

PRACTICE PROBLEM BASED ON SELF-DUAL FUNCTIONS-

 

Problem-

 

Consider the following functions-

  1. F (A , B , C) = ∑ (0 , 2 , 3)
  2. F (A , B , C) = ∑ (0 , 1 , 6 , 7)
  3. F (A , B , C) = ∑ (0 , 1 , 2 , 4)
  4. F (A , B , C) = ∑ (3 , 5 , 6 , 7)

 

Which of the above functions are self-dual functions?

  1. Only (iii)
  2. Only (ii)
  3. Only (iii) and (iv)
  4. All are self-dual functions

 

Solution-

 

Condition-01:

 

According to condition-01, for a function to be a self-dual function, the function must be a neutral function.

 

  • In all the given options, we have functions of 3 variables- A, B and C.
  • So, Neutral function must contain exactly 2n-1 = 23-1 = 4 minterms and 4 maxterms.
  • But Function-(i) contains only 3 minterms. So, it is not a neutral function.
  • Therefore, it can’t be a self-dual function and it gets eliminated.
  • We are now left with three other functions which satisfies condition-01 and are all neutral functions.
  • We will now use 2nd condition to eliminate the incorrect option(s).

 

Condition-02:

 

According to condition-02, a self-dual function must not contain mutually exclusive terms.

First, let us find which terms are mutually exclusive-

 

ABCMinterms
0000A’B’C’
1001A’B’C
2010A’BC’
3011A’BC
4100AB’C’
5101AB’C
6110ABC’
7111ABC

 

  • From here, pairs of mutually exclusive terms are (0,7) , (1,6) , (2,5) , (3,4).
  • Mutually exclusive terms are not allowed in self-dual functions.
  • Therefore, terms inside the pairs can not appear together.
  • But terms 0 and 7 appear together in the function-(ii).
  • So, it can not be a self-dual function.
  • But functions (iii) and (iv) do not contain any mutually exclusive terms.
  • Therefore, functions (iii) and (iv) are self-dual functions.

 

Thus, Option (C) is correct.

 

NOTE-

 

  • Functions (iii) and (iv) are complementary functions.
  • So, if one function is a self-dual function, the other function will also be a self-dual function.
  • This is because self-dual functions are closed under complementation.

 

To gain better understanding about Self-Dual Functions,

Watch this Video Lecture

 

Get more notes and other study material of Digital Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Neutral Functions | Minterms and Maxterms

Minterms and Maxterms-

 

For any function consisting of n Boolean variables,

Number of minterms possible = Number of maxterms possible = 2n

 

Minterms and Maxterms Examples-

 

The examples of minterms and maxterms are-

 

Example-01:

 

For any function consisting of 2 Boolean variables A and B, we have-

  • Number of minterms possible = 22 =  4.
  • Number of maxterms possible = 22 =  4.

 

The following table shows the minterms and maxterms-

 

ABMintermsMaxterms
00A’B’A + B
01A’BA + B’
10AB’A’ + B
11ABA’ + B’

 

Example-02:

 

For any function consisting of 3 Boolean variables A, B and C, we have-

  • Number of minterms possible = 23 =  8.
  • Number of maxterms possible = 23 =  8.

 

The following table shows the minterms and maxterms-

 

ABCMintermsMaxterms
000A’B’C’A + B + C
001A’B’CA + B + C’
010A’BC’A + B’ + C
011A’BCA + B’ + C’
100AB’C’A’ + B + C
101AB’CA’ + B + C’
110ABC’A’ + B’ + C
111ABCA’ + B’ + C’

 

Neutral Functions-

 

A neutral function is a function for which number of minterms and number of maxterms are same.

 

Example-

 

The following function is an example of a neutral function-

f( A, B) = A ⊕ B

 

This is because this function has equal number of minterms and maxterms as shown by the following table-

 

ABA ⊕ B
000
011
101
110

 

Number Of Neutral Functions Possible-

 

 

Here n = Number of Boolean variables in the function.

 

Explanation-

 

  • For n variables, total number of terms possible = number of combinations of n variables = 2n.
  • Since maximum number of terms possible = 2n, so we choose half of the terms i.e 2n / 2 = 2n-1.
  • We assign them the output logic ‘1’.
  • We assign ‘0’ to rest half of the terms.
  • Thus, number of neutral functions possible with n Boolean variables = C ( 2n , 2n-1 ).

 

PRACTICE PROBLEM BASED ON NEUTRAL FUNCTIONS-

 

Problem-

 

Consider any function consisting of 2 Boolean variables A and B-

  1. Calculate the total number of neutral functions that are possible.
  2. Write all the neutral functions.

 

Solution-

 

We know, number of neutral functions possible with n Boolean variables = C ( 2n , 2n-1 ).

 

Substituting n = 2, we get-

Number of neutral functions possible with 2 Boolean variables

= C ( 22 , 22-1 )

= C ( 4 , 2 )

= 6

 

Thus, total 6 Boolean functions are possible with 2 Boolean variables.

The 6 Boolean Functions are-

  • f ( A , B ) = A
  • f ( A , B ) = A’
  • f ( A , B ) = B
  • f ( A , B ) = B’
  • f ( A , B ) = A ⊙ B
  • f ( A , B ) = A ⊕ B

 

VariablesBoolean Functions
ABAA’BB’A⊙BA⊕B
00010110
01011001
10100101
11101010

 

The above table clearly shows that for each function, number of minterms = number of maxterms.

So, they all are neutral functions.

 

To gain better understanding about Neutral Functions,

Watch this Video Lecture

 

Next Article- Self-Dual Functions

 

Get more notes and other study material of Digital Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Universal Logic Gates | NAND Gate | NOR Gate

Logic Gates-

 

Before you go through this article, make sure that you have gone through the previous article on Logic Gates.

 

We have discussed-

  • Logic gates are the basic building blocks of any digital circuit.
  • There are 3 basic logic gates- AND, NOT, OR.
  • Logic gates are classified as-

 

 

In this article, we will discuss about Universal Logic Gates.

 

Universal Logic Gates-

 

Universal logic gates are the logic gates that are capable of implementing any Boolean function

without requiring any other type of gate.

 

They are called as “Universal Gates” because-

  • They can realize all the binary operations.
  • All the basic logic gates can be derived from them.

 

They have the following properties-

  • Universal gates are not associative in nature.
  • Universal gates are commutative in nature.

 

There are following two universal logic gates-

 

 

  1. NAND Gate
  2. NOR Gate

 

1. NAND Gate-

 

  • A NAND Gate is constructed by connecting a NOT Gate at the output terminal of the AND Gate.
  • The output of NAND gate is high (‘1’) if at least one of its inputs is low (‘0’).
  • The output of NAND gate is low (‘0’) if all of its inputs are high (‘1’).

 

Logic Symbol-

 

The logic symbol for NAND Gate is as shown below-

 

 

Truth Table-

 

The truth table for NAND Gate is as shown below-

 

ABY = (A.B)’
001
011
101
110

Truth Table

 

Timing Diagram-

 

The timing diagram for NAND Gate is as shown below-

 

 

2. NOR Gate-

 

  • A NOR Gate is constructed by connecting a NOT Gate at the output terminal of the OR Gate.
  • The output of OR gate is high (‘1’) if all of its inputs are low (‘0’).
  • The output of OR gate is low (‘0’) if any of its inputs is high (‘1’).

 

Logic Symbol-

 

The logic symbol for NOR Gate is as shown below-

 

 

Truth Table-

 

The truth table for NOR Gate is as shown below-

 

ABY = A + B
001
010
100
110

Truth Table

 

Timing Diagram-

 

The timing diagram for NOR Gate is as shown below-

 

 

To gain better understanding about Universal Logic Gates,

Watch this Video Lecture

 

Next Article- Alternative Logic Gates

 

Get more notes and other study material of Digital Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.