Digital Electronics 1st Year (Unit 1)

Lecture Topic 1.3.1

CO1(REMEMBERING): To identify the different types of digital circuits and their difference and to illustrate the various

types of gates.

CO2(UNDERSTANDING): To understand the various elements of digital system and to implement their applications.
LOGIC GATES

Introduction to basic Logic Gate

1. Most logic gates have two inputs and one output and at any given moment, every terminal is in one of the two binary conditions either low (0) or high (1), represented by different voltage levels. The logic state of a terminal change often, as the circuit processes data. In most logic gates, the low state is approximately zero volts(0 V), while the high state is approximately five volts positive (+5 V).

There are seven basic logic gates: AND, OR, XOR, NOT, NAND, NOR, and NOR.

AND Gate (.)

The AND gate is so named because, if 0 is called “false” and 1 is called “true,” the gate acts in the same way as the logical “and” operator. The following illustration and table show the circuit symbol and logic combinations for an AND gate. (In the symbol, the input terminals are at left and the output terminal is at right.) The output is “true” when both inputs are “true.” Otherwise, the output is “false.” In other words, the output is 1 only when both inputs one AND two are 1.

Boolean Expression: – A.B = Q.

The Multi-Input Logic AND Gate

Because the Boolean expression for the logic AND function is defined as (.), which is a binary operation, AND gates can be cascaded together to form any number of individual inputs. However, commercial available AND gate IC’s are only available in standard 2, 3, or 4-input packages. If additional inputs are required, then standard AND gates will be cascaded together to obtain the required input value, for example.

OR Gate (+)

The OR gate gets its name from the fact that it behaves after the fashion of the logical inclusive “or.” The output is “true” if either or both of the inputs are “true.” If both inputs are “false,” then the output is “false.” In other words, for the output to be 1, at least input one OR two must be 1.

Boolean Expression: – A+B = Q.

NOT Gate (‘ )

Inverting NOT gates are single input device which have an output level that is normally at logic level “1” and goes “LOW” to a logic level “0” when its single input is at logic level “1”, in other words it “inverts” (complements) its input signal. The output from a NOT gate only returns “HIGH” again when its input is at logic level “0”.

Boolean Expression: – A = A’

 XOR Gate (Å)

The XOR gate stands for the Exclusive-OR gate. This gate is a special type of gate used in different types of computational circuits. Apart from the AND, OR, NOT, NAND, and NOR gate, there are two special gates, i.e., Ex-OR and Ex-NOR. These gates are not basic gates in their own and are constructed by combining with other logic gates. Their Boolean output function is significant enough to be considered as a complete logic gate. The XOR and XNOR gates are the hybrids gates.

Boolean Expression:- = A Å B

 XNOR Gate

The XNOR gate is the complement of the XOR gate. It is a hybrid gate. Simply, it is the combination of the XOR gate and NOT gate. The output level of the XNOR gate is high only when both of its inputs are the same, either 0 or 1. The symbol of the XNOR gate is the same as XOR, only complement sign is added. Sometimes, the XNOR gate is also called the Equivalence gate.

Boolean Expression:- = AʘB

The logic function implemented by a 2-input Ex-NOR gate is given as “when both A AND B are the SAME” will give an output at Q. In general, an Exclusive-NOR gate will give an output value of logic “1” ONLY when there are an EVEN number of 1’s on the inputs to the gate (the inverse of the Ex-OR gate) except when all its inputs are “LOW”. Then an Ex-NOR function with more than two inputs is called an “even function” or modulo-2-sum (Mod-2-SUM), not an Ex-NOR. This description can be expanded to apply to any number of individual inputs as shown below for a 3-input Exclusive-NOR gate.

UNIVERSAL GATES

Individual logic gates can be connected together to form a variety of different switching functions and combinational logic circuits. As we have seen through this Digital Logic tutorial section, the three most basic logic gates are the: AND, OR and NOT gates, and given this set of logic gates it is possible to implement all of the possible Boolean switching functions, thus making them a “full set” of Universal Logic Gates. There are two universal gates:

• NAND
• NOR

NAND Gate

The NAND gate is a special type of logic gate in the digital logic circuit. The NAND gate is the universal gate. It means all the basic gates such as AND, OR, and NOT gate can be constructed using a NAND gate. The NAND gate is the combination of the NOT-AND gate. The output state of the NAND gate will be low only when all the inputs are high. Simply, this gate returns the complement result of the AND gate.

Boolean Expression: – Q = A.B

NOR Gate

The NOR gate is also a universal gate. So, we can also form all the basic gates using the NOR gate. The NOR gate is the combination of the NOT-OR gate. The output state of the NOR gate will be high only when all of the inputs are low. Simply, this gate returns the complement result of the OR gate.

Boolean Expression:- A+B = Q

---

Lecture Topic 1.3.2

CO1(REMEMBERING): To identify the different types of digital circuits and their difference and to illustrate the various types of gates.

CO2(UNDERSTANDING): To understand the various elements of digital system and to implement their applications.Boolean Theorems of Boolean Algebra

 Fundamental Concepts of Boolean algebra:

Boolean algebra is a division of mathematics which deals with operations on logical values and incorporates binary variables in digital electronics. Boolean algebra is a logical algebra in which symbols are used to represent logic levels. Since the logic levels are generally associated with the symbols 1 and 0, whatever letters are used as variables that can take the values of 1 or 0. Boolean algebra has only two mathematical operations, addition and multiplication. These operations are associated with the OR gate and the AND gate, respectively.

Important rules used in Boolean algebra

• Variable used can have only two values. Binary 1 for HIGH and Binary 0 for LOW.
• Complement of a variable is represented by an overbar (-). Thus, complement of variable Bis represented as . Thus if B = 0 then =1 and B = 1 then =0.
• ORing of the variables is represented by a plus (+) sign between them. For example ORing of A, B, C is represented as A+ B + C.
• Logical ANDing of the two or more variable is represented by writing a dot between them such as A.B.C. Some time the dot may be omitted like ABC.

Boolean Theorems/Laws

In order to simplify the digital logical expressions and circuits, the Boolean equations and expressions representing that logic must be simplified. So, to simplify the Boolean equations and expression, there are some laws and theorems proposed.

AND Law: These laws use the AND operation. Therefore they are called AND laws.

• A .0 = 0
• A. 1 = A
• AA = A
• A. A¯=0

OR Law: These laws use the OR operation. Therefore they are called OR laws.

• A + 0 = A
• A + 1 = 1
• A + A = A
• A+A¯=1

Annulment law – A variable ANDed with 0 gives 0, while a variable ORed with 1 gives 1, i.e.,

• A.0 = 0
• A + 1 = 1

Identity law – In this law variable remain unchanged it is ORed with ‘0’ or ANDed with ‘1’, i.e.,

• A.1 = A
• A + 0 = A

Idempotent law – A variable remain unchanged when it is ORed or ANDed with itself, i.e.,

• A + A = A
• A.A = A

Complement law – In this Law if a complement is added to a variable it gives one, if a variable is multiplied with its complement it results in ‘0’, i.e.,

• A + A’ = 1
• A.A’ = 0

Double negation law – A variable with two negation its symbol gets cancelled out and original variable is obtained, i.e.

• ((A)’)’=A

Commutative law – Any binary operation which satisfies the following expression is referred to as a commutative operation. Commutative law states that changing the sequence of the variables does not have any effect on the output of a logic circuit. A variable order does not matter in this law, i.e.,

• A + B = B + A
• A.B = B.A

Associative law – It states that the order in which the logic operations are performed is irrelevant as their effect is the same. the order of operation does not matter if the priority of variables are same like ‘*’ and ‘/’, i.e.,

• A+(B+C) = (A+B)+C
• A.(B.C) = (A.B).C

Distributive law – This law governs opening up of brackets, i.e.,

• A.(B+C) = (A.B)+(A.C)
• A+(B.C) = (A+B).(A+C)

Figure: Logic Gate Implementation of laws.

Absorption law -This law involved absorbing the similar variables, i.e.,

• A.(A+B) = A
• A + AB = A

De Morgan law – the operation of an AND or OR logic circuit is unchanged if all inputs are inverted, the operator is changed from AND to OR, the output is inverted, i.e.,

• (A.B)’ = A’ + B’
• (A+B)’ = A’.B’

Example : De Morgans Law

Expression:

Duality law – Duality principle states that “The Dual of the expression can be achieved by replacing the AND operator with OR operator, along with replacing the binary variables, such as replacing 1 with 0 and replacing 0 with 1.This law explains that, replacing the variables doesn’t change the value of the Boolean function.

Proof

If we have the Boolean equation like A + B = 0, then the equation formed by replacing the variable 0 with 1 and replacing the OR operator with AND operator is A * B = 1. This means both the Boolean functions are represents the operation of logic circuit. As per Duality principle, if A, B are two variables then both the equations A + B = 0 and A * B = 1 are true in case of same logic circuit.

 Application of Boolean laws:

• A set of rules or Laws of Boolean Algebra expressions have been invented to help reduce the number of logic gates needed to perform a particular logic operation resulting in a list of functions or theorems.
• By reducing the number of logic gates over all delay of the circuit also reduces hence make digital circuits to operate faster with lesser number of logical gates.
• Boolean algebra provides the basis for analyzing the validity of logical propositions because it captures the two-valued character (binary) of statements that may be either true or false
• In particular, by taking the variables to represent values of on and off (or 0 and1),Boolean algebra is used to design and analyze digital switching circuitry, such as that found in personal computers, pocket calculators, CD players, cellular telephones, and a host of other electronic products.

Examples: Simplify :Y= (A+C) (AD+AD) +AC+C

Sol. Expression along with Rule(s) Used                                                      

Y= (A + C)(AD + AD) + AC + C…………… ……..Original Expression

 = (A + C)A(D + D) + AC + C…………………..using Distributive law.

 = (A + C)A + AC + C…………………………..using Complement, Identity.

= A((A + C) + C) + C …………………………..Commutative, Distributive.

Y= A.(A + C) + C……………………………………… Associative, Idempotent.

  =  AA + AC + C ……………………………………..Distributive.

  = A + (A + 1) C ……………………………………….Idempotent, Identity, Distributive.

 Y =A + C ……………………………..………………. Identity, twice.

You can also use distribution law above and from starting A (A+C)+C to reach the same result by another route.

Example: Simplify the following expression: C+BC’

Sol. Given: C+BC’

According to Demorgan’s law, we can write the above expressions as

= C+(B’+C’)

From Commutative law:

= (C+C’)+B’

From Complement law

= 1+B’ = 1

Therefore, C+BC’=1

SUMMARY:

1. Boolean Algebra
2. Boolean Laws
3. Expression Minimization

---

Lecture 1.3.3

Sum of Products and Product of Sums, Canonical form

All Boolean expression can be expressed in either SOP (Sum of Product) or POS (Product of SUM). 

 y = AB’ + BC’ is the SOP form

In above equation firstly AND gate is used then all are ORed with each other .in this expression each ANDed term is termed as Minterm (m_i).

            Y= (A + B’)(B + C’) is the POS form

In above equation, each literal is firstly ORed and then all are ANDed. Each ORed term is called as Maxterm (M_i). Literal means either a variable or its complement.

Canonical Form:

If each minterm/ maxterm is having all the literal (variable or its complement), then it is called as Canonical or Standard Form.

Y = ABC + AB’C + A’BC

Y = (A+B+C)(A’+B+C)(A+B’+C’)

In above equations, each is having all literal so these are on canonical SOP and canonical POS respectively.

Conversion into canonical SOP form: For SOP form, replace missing variable with 1 then 1 can be changed to variable using Boolean identity A+A’=1then do simplification by Boolean algebra.

Example: Convert Y= ABC +B’C’ + A’B’ into canonical SOP form.

If expression is be converted into canonical form:

For POS form, replace missing variable with 0 then 0 can be changed to variable using Boolean identity AA’=0, apply distributive law after that do simplification by Boolean algebra.

Example:  Convert Y= (A’+B’+C’) (A+C’) into canonical POS form.

Applications: In modern area, we want everything should be compact like:

• Mobile Phone
• Integrated Circuits
• Microcontroller
• Laptop etc.

Not only electronics gadgets, we are focusing on maximum applications can be performed by each IC, so to obtain this number of components should be reduced. For reduction K map is one method by which we can reduce number of gates used for a particular circuit. 

*Nanotechnology is the best example.

 SUMMARY:

1. SOP
2. POS
3. Canonical Forms

---

Lecture 1.3.4

CO(REMEMBERING): To identify the different types of digital circuits and their difference and to illustrate the various types of gates.

CO(UNDERSTANDING): To understand the various elements of digital system and to implement their applications.

CO(APPLYING): To solve the basic problems related to different types of digital circuits and to calculate it using various numerical problems.

Karnaugh Map

Boolean Simplification is divided into two types:

• Boolean Algebra
• K – map

Karnaugh maps (K-maps) are graphical method for the simplification of Boolean functions.

           K- maps consists of cell

Where no. of cells =2ⁿ   as n being no. of input variables

K-map cells are arranged so that adjacent cells differ in only one bit position (based on gray code).

 K maps for SOP & POS form shown below:  

Cell number can be written as in each cell, note down the values of variables as ABCD according to variables in K map. Change the binary into decimal values, which will be the cell number in K-map. For SOP form according to minterms, 1 should be filled in cell, whereas 0 should be filled in cells for POS form as given in questions.

K- maps according to number of variables:

According to number of variables, SOP & POS form , k-maps are drawn below:

 For two variables:             

For SOP form and For POS form

 For three variables:

 For SOP form and POS form

 For four variables:

For SOP form and POS form

Steps to solve expression using K map

•  Draw the Karnaugh map depending on variables as given in question.
• Identify minterms (SOP ) and Maxterms (POS) as given in problem.
• For SOP put 1’s in blocks of K map according to minterms.
• For POS put 0’s in blocks of K map according to maxterms.
• Make groups/pairs containing total terms in power of 2 like (2,4,8,16) Try to make the largest possible pair.
• Find product terms with variables (that are unchanged along rows and columns) for each group and sum up for SOP form.
• Find sum terms with variables (that are unchanged along rows and column ) for each group and ANDED them for POS form.

Pairing Rules of K map

1. Adjust cells can be paired. Pairing involves 2(pair), 4 (Quad) & 8 (Octet) cells
2. Corner elements can be paired. 
3. Outermost rows as well as outermost columns can be paired respectively.
4. Try to make largest possible pair as shown.
5.  Groups may overlap.
6. Diagonal pair is not possible.
7. Make sure in each pair, there must be at least one unpaired 1(sop) or 0(pos).

 Example: Simply y=∑m(1, 3,4,5,7) using K map.

Output Expression: Y = C + AB’

Example: Simply F(A,B,C,D) = ∑ m( 2,3,8,10,11,12,14,15) using K – map and realize the circuit using AOI gates. 

Don’t Care Condition:

The “Don’t Care” conditions allow us to replace the empty cell of a K-Map to form a grouping of the variables. While forming groups of cells, we can consider a “Don’t Care” cell as either 1 or 0 or we can simply ignore that cell. Therefore, “Don’t Care” condition can help us to form a larger group of cells.

A Don’t Care cell is represented by a cross(X) in K-Maps.

Examples: F = ∑m(1, 5, 6, 12, 13, 14) + d(4)

                   F(A, B, C, D) = M(6, 7, 8, 9) +Փ (10, 11, 12, 13, 14, 15)

Applications of Topic: In modern area, we want everything should be compact like:

• Mobile Phone
• Integrated Circuits
• Microcontroller
• Laptop etc.

Not only electronics gadgets, but we are also focusing on maximum applications can be performed by each IC, so to obtain this number of components should be reduced. For reduction K map is one method by which we can reduce number of gates used for a particular circuit. 

*Nanotechnology is the best example.

 SUMMARY:

1. Simplification of Boolean Expression using K-Map
2. K Map for SOP
3. K Map for POS
4. K Map with Don’t Care