Parity Checker

CSE 4205: Digital Logic Design

Aashnan Rahman
Junior Lecturer
Department of Computer Science and Engineering (CSE)
Islamic University of Technology
 01

Revisiting a few topics

2
Topics Covered
● NAND and NOR implementation
● SoP/Pos – 2 level implementation
● XOR and XNOR

3
NAND Implementation
To facilitate the conversion to NAND logic, it is convenient to define an alternative
graphic symbol for the NAND gate.
● AND-invert: Consists of an AND gate followed by a small bubble (i.e., complement)
● Invert-OR: Consists of an OR gate preceded by a bubble in each input
(i.e., complements each input)
Both of them are equal because of De Morgan's theorem

4
 NAND Implementation
1. Simplify the function and express it in SOP form
2. To implement the first level gates, all product terms of the expression (having at least two
variables) drawn with NAND gates. Inputs of these NAND gates will be the same literals of the
previous terms.
3. Draw another single NAND gate (representing invert-OR) in the second level with inputs coming
from outputs of the first level gates
4. A term having a single-variable term requires an inverter in the first level. However, if that
variable is complemented, it can be connected directly to the input of the second level NAND
gate.

5
NAND Implementation

6
NOR Implementation
NOR operation is the dual of NAND operation
● All procedures and rules for NOR logic are the dual of the corresponding procedures
and rules developed for NAND logic
● Another universal gate to implement any logic circuit

7
NOR Implementation
To show that any function can be implemented with NOR gate, we need only to show that
AND, OR and NOT gates obtained with NOR gates alone

Note: One-input NOR gate behaves exactly like an inverter.

8
NOR Implementation
• To facilitate the conversion to NOR logic, it is convenient to define
an alternative graphic symbol for the NOR gate
• OR-invert: Consists of an OR gate followed by a small bubble (i.e., complement)
• Invert-AND: Consists of an AND gate preceded by a bubble in each input
(i.e., complements each input)
• Both of them are equal because of De Morgan's theorem
• Useful for analysis and design NOR circuits

9
2 level NOR Implementation
• For two level NOR implementation, initially the function must
be simplified in POS form
• Note: Simplified POS expression can be obtained by combining all 0s
and complementing that expression
• OR gate will be replaced by OR-invert NOR gate in the first level and
AND gate will be replaced by invert-AND NOR gate in second level
• As Bubble denotes complementation, two cascaded bubbles will
be cancelled by each other
• But, if there is a single-variable term in first level of
implementation, an inverter will be required for that term
• We can replace that inverter changing the input variable into its
complement (i.e., x will be x’ in the input)

10
2 level NOR Implementation
1. Simplify the function and express it in POS form
2. To implement the first level gates, all sum terms of the expression
(having at least two variables) drawn with NOR gates
• Inputs of these NOR gates will be the same literals of the previous terms
3. Draw another single NOR gate (representing invert-AND) in the
second level with inputs coming from outputs of the first level gates
4. A term having a single variable requires an inverter in the first level.
However, if that variable is complemented, it can be connected
directly to the input of the second level NOR gate

11
2 level NOR Implementation

12
Multi Level NAND Implementation
• Standard form in SOP or POS expression can be implemented in a two-level implementation
• But sometimes, three or more level getting structure are also observed in digital systems

• There are two approaches to design a multi-level NAND circuits:

1. Express the Boolean function in terms of AND, OR and NOT operators
2. Two alternative ways:
• Approach 1: All the AND, OR and NOT gates would be converted to its corresponding NAND representation
• Approach 2: Convert each AND to AND-invert and each OR to Invert-OR gates
3. There should have two cascaded bubbles or inverters who will cancel each other
• Otherwise, one extra inverter should be inserted, or input variables should be complemented

13
Multi Level NAND Implementation

14
Multi Level NAND Implementation

15
Multi Level NOR Implementation
• There are two approaches to design a multi level NOR circuits:
1. Express the Boolean function in terms of AND, OR and NOT operators
2. Two alternative ways:
• Approach 1: All the AND, OR and NOT gates would be converted to its
corresponding NOR representation
• Approach 2: Convert each AND to invert-AND and each OR to OR-invert gates
3. There should have two cascaded bubbles or inverters who will cancel each
other
• Otherwise, one extra inverter should be inserted, or input variables
should be complemented

16
Multi Level NOR Implementation

17
 02

XOR and XNOR

18
Usage of XOR and XNOR
• Only a limited number of Boolean functions can be expressed with
XOR and XNOR gates
• In some digital system designs, they could be used
• Specially, they are useful in -
• Arithmetic operations (e.g., add, subtract, etc.)
• Logical operation (e.g., complement)
• Error detection and correction (e.g., parity generator and checker)
• Gray code conversion
• XOR gate is used extensively, XNOR could be implemented as
XOR-inverter.

19
Odd Function
• Basically, two input XOR gate could be defined as difference function
• But, if we increase the number of input to three or more, definition will be changed
• Example:

• Here, three input XOR gate produces 1 if only one variable is 1 or all three variables are 1
• Definition: A multiple input XOR gate operates as an odd function i.e. an odd number of
inputs should be 1.
• An n–variable XOR function is an odd function defined as the logical sum of the 2n/2 minterms whose binary
numerical values have an odd number of 1s

20
Odd and Even Function

21
 03

Parity Checker

22
Parity Generator and Checker
• XOR function is very useful for error detection and
correction codes
• Parity bit is an extra bit which is usually included with
original message during transmission for error detection
• Parity Generator – the circuit that generates the parity bit in the
transmitter
• Parity Checker – the circuit that checks the parity in the receiver
• Example:
• Consider a three bit message (e.g. x, y, z) to be transmitted
together with an even parity bit (e.g. P)

23
Parity Generator and Checker

24
Parity Generator and Checker
•

25
Thank You !!
Feel free to ask any questions

26