DIGITAL DESIGN

RELICUUS SEMICONDUCTOR PVT LTD

 TABLE OF CONTENTS

BINARY SYSTEMS #

NUMBER SYSTEMS & BINARY CONVERSIONS #

BINARY CALUCULATIONS #
BOOLEAN ALGEBRA & COMBINATIONAL LOGIC GATES #

COMBINATIONAL LOGIC #

ADDERS, SUBTRACTORS & COMPARATORS #

ENCODERS AND DECODERS #
MULTIPLEXERS & DEMULTIPLEXERS #
TRI STATE BUFFERS #

SEQUENTIAL CIRCUITS #

LATCHES #
FLIPFLOPS #
STATE MACHINES & STATE DIAGRAMS #
REGISTERS & SHIFT REGISTERS #
COUNTERS #

MEMORIES #

MEMORIES #
PLDS #
PAL’S #
PLA’S #

1|Page
 BINARY SYSTEMS

Number System
Definition:
The number system are used to quantify the magnitude of something. One way of
quantifying the magnitude of something is by proportional values. This is called analog
representation. The other way of representation of any quantify is numerical (Digital).
The number systems are called position weighted systems, since the weight of each digit
depends on its relative position with in the number.
Base (or) Radix of system:
The base (or) radix of number system is defined as the number of different symbols
(Digits (or) characters) used in that number system.
Types of Number Systems:
1. Binary number system:

 The base value of binary number system is ‘2’ (i,e. r=2).

 The different symbols used in binary number system are 0 to r-1 (i,e. 0 to 1) those
are 0 and 1.
 The decimal equivalent of a binary number (say 10110) is 22, which can be
Verified as follows applying the same pattern as discussed in decimal number system.
Binary number
(10110)2 = 1 × 24 + 0 × 23 + 1 × 22 + 1 × 21 + 0 × 20
= 16 + 0 + 4 + 2 + 0
= (22)10 Decimal number

It is very essential to show the suffix to the numbers which indicates the base of
the number system.

2|Page
Example: Find the decimal equivalent of the binary number 11011001.0101.
Solution:
(11011001.0101)2 = 1 × 27 + 1 × 26 + 0 × 25 + 1 × 24 + 1 × 23 + 0 × 22 + 0 × 21 + 1 × 20
+0× 2-1 + 1 × 2-2 + 0 × 2-3+ 1 × 2-4
= 128 + 64 + 0 + 16 + 8 + 0 + 0 + 1 + 0 + 0.25 + 0 + 0.125
= (217.375)10
Example: Do the following conversions:
(i) (1100110111110.1011)2 to octal
(ii) (110011010110111110.101)2 to hexadecimal
Solution: (i) Binary number: 001 100 110 111 110 . 101 100
Octal Equivalent: 1 4 6 7 6 3 4
So (1100110111110.1011)2 = (14676.34)8

(ii) Binary number: 0011 0011 0101 1011 1110 . 1010

Hexadecimal Equivalent: 3 3 5 B E A
So (110011010110111110.101)2 = (335BE.A)16

2. Octal Number system:

 The base value of octal number system is ‘8’. (i,e. r=8)

 The number of different symbols used in octal number system is 0 to r-1(i,e. 0 to 7)
those are 0,1,2,3,4,5,6,7

Octal number (24)8 = 2 × 81 + 4 × 80

= 16 + 4
= (20)10
Example: Find the decimal equivalent of the octal number 7126.45.
Solution:
(7126.45)8 = 7 × 83 + 1 × 82 + 2 × 81 + 6 × 80 + 4 × 8-1 + 5 × 8-2
= 512 + 64 + 16 + 6 + 0.125 + 0.5 + 0.078125
= (598.703125)10
Example: Do the following conversions:
(2467.534)8 to binary
Octal number: 2 4 6 7 . 5 3 4
Binary Equivalent: 010 100 110 111 . 101 011 100
So (2467.534)8 = (10100110111.1010111)2

3|Page
3. Decimal number system:

 The base value of Decimal number system is ‘10’ (i.e. r=10).

The number of different symbols used in decimal number system are 0 to r-1 (0 to 9) those are
0,1,2,3,4,5,6,7,8,9.

So (127)10 = (1111111)2

Example: Convert the following decimal numbers into octal.

(i) 567 (ii) 1276

4|Page
 So (1276)10 = (2374)8
Example: Convert the following decimal numbers into hexadecimal.
(i) 8537 (ii) 98765

So (8537)10 = (2159)16

So (98765)10 = (181CD) 16

Conversion of Fractional Decimal Number to Binary Number:

Example: Do the following conversions:
(i) (965.125)10 to octal
(ii) (8765.025)10 to hexadecimal

5|Page
 (iii) (6754.05)8 to decimal.

4. Hexa decimal number system:

 The base value of Hexa Decimal number system is ‘16’ (r=16).

Hexa decimal

 The number of different symbols used in Hexa decimal number system are 0 to r-1
(0 to 15) those are 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F.
(17)16 = 1 × (16)1 + 7 × (16)0
=16 + 7

6|Page
 = (23)10

Example: Find the decimal equivalent of the Hexadecimal number 3BC7.46

Solution:
(i). (3BC7.46)16
= 3× (16)3 + 11 × (16)2 + 12 × (16)1 +7 × (16)0 + 4 × (16)-1 + 6 × (16)-2
= 12288 +2816 + 192 + 7 + 0.25 + 0.234375
= (15303.484375)10
(ii) (2AB6E7.5D4)16 to binary

Hexadecimal: 2 A B 6 E 7 . 5 D 4
Binary 0010 1010 1011 0110 1110 0111 . 0101 1101 0100
So (2AB6E7.5D4)16 = (1010101011011011100111.0101110101)2

Example: Convert the hexadecimal number 4AC7.4B in to its equivalent octal

Number.

Solution: The given hexadecimal number is first converted to binary number and then
Converted to octal number.
Hexadecimal: 4 A C 7 . 4 B
Binary: 0100 1010 1100 0111 . 0100 1011

Now (100101011000111.01001011)2 to octal

100101011000111.01001011 = 100 101 011 000 111 . 010 010 110
Octal: 4 5 3 0 7 2 2 6

Thus (4AC7.4B)16 = (45307.226)8

7|Page
 BINARY CALCULATIONS

1’s Compliment:
The compliment of each bit in a binary number is 1’s compliment
For example, 100101is the 1’s compliment of 011010

2’s Compliment:
Adding 1 to the 1’s compliment binary number is 2’s compliment.
For example, the 2’s compliment of binary number 100101 is
100101
011010-------- 1’s compliment
+ 1--------- adding 1 to 1’s compliment number
011011--------- 2’s compliment of 100101
The rule for changing a positive 2’s complement number into a negative 2’s
complement number (or vice versa) is: Complement all the bits and add 1.

2’s Compliment Addition:

Let’s suppose addition of binary numbers 00000111 and 00000100
00000111 7
00000100 +4
(0) 00001011 11

2’s Compliment Subtraction:

Let’s suppose subtraction of binary numbers 00000110 from 00000111
First 2’s compliment the smaller number and add it to the larger number
2’s compliment of 00000110 (6) is 11111110 add it to 00000111
00000111 (7)
11111110 + (-6)
( 1 ) 00000001 (1)

8|Page
 COMBINATIONAL LOGIC GATES AND BOOLEAN ALGEBRA

Introduction to logic gates:

 Logic gates are the building blocks of digital circuits

 Logic gates can only take on 2 values e.g.,
– TRUE or False
– ON or OFF
– 1 or 0
 In electronic circuits the two values can be represented by e.g.,
– High voltage for a 1
– Low voltage for a 0
 Note that since only 2 voltage levels are used, the circuits have greater immunity to electrical
noise

Logic Gates:

 Basic logic circuits with one or more inputs and one output are known as gates.
 Gates are used as the building blocks in the design of more complex digital logic circuits.
 There are several ways of representing logic functions:
– Symbols to represent the gates
– Truth tables
– Boolean algebra
 Logic gates are electronic circuits with a number of inputs and one output. There are three
basic logic gates, namely
1. OR gate,
2. AND gate,
3. NOT gate
 Other logic gates that are derived from these basic gates are
1. NAND gate,
2. NOR gate,
3. EXCLUSIVE-OR gate,
4. EXCLUSIVE-NOR gate

9|Page
AND Gate:

 An AND gate is a logic circuit with two or more inputs and one output that performs AND
operation. The output of an AND gate is HIGH only when all of its inputs are in the HIGH
state. In all other cases, the output is LOW. For a positive logic systems, it means that the
output of the AND gate is a logic ‘1’ only when all of its inputs are in logic ‘1’ state. In all
other cases, the output is logic ‘0’. The logic symbol and the truth table of a two-input AND
gate are shown

 Truth Table of 2 input AND Gate

OR Gate:

 An OR gate is a logic circuit with two or more inputs and one output that performs OR
operation. The output of an OR gate is LOW only when all of its inputs are LOW. For all
other possible input combinations, the output is HIGH. For a positive logic system, the output
of an OR gate is a logic ‘0’ only when all of its inputs are at logic ‘0’. For all other possible
input combinations, the output is a logic ‘1’. The logic symbol and the truth table of a two-
input OR gate are shown in Figure

10 | P a g e
  Truth Table of 2 input OR Gate

NOT Gate:

 A NOT gate, also called an inverter is a one-input, one-output logic circuit whose output is
always the complement of the input. That is, a LOW input produces a HIGH output, and vice
versa. It means that for a positive logic system, a logic ‘0’ at the input produces a logic ‘1’ at
the output, while a logic ‘1’ at the input produces a logic ‘0’ output. It is also known as a
complementing circuit or an inverting circuit. The logic symbol and the truth table of an
inverter are shown in Figure

 Truth Table of 2 input OR Gate:

11 | P a g e
 NAND Gate:

 The term NAND implies NOT-AND. A NAND gate is equivalent to AND gate followed by a
NOT gate. The standard logic symbol for a 2-input NAND gate is shown in Figure. This
symbol is same as AND gate symbol except for a small circle (bubble) on its output. This
circle represents the NOT function.

 The truth Table of a NAND gate is obtained from the truth Table of an AND gate by
complementing the output entries. The output of a NAND gate is a logic ‘0’ when all its
inputs are a logic ‘1’. For all other input combinations, the output is a logic ‘1’. NAND gate
operation is logically expressed as Y = A.B

 Truth Table of 2 input NAND Gate:

NOR Gate:
 The term NOR implies NOT-OR. A NOR gate is equivalent to OR gate followed by a NOT
gate. The standard logic symbol for a 2-input NOR gate is shown in Figure. This symbol is
same as OR gate symbol except for a small circle (bubble) on its output. This circle represents
the not function.

 The truth Table 2.10 of a NOR gate is obtained from the truth Table of an OR gate by
complementing the output entries. The output of a NOR gate is a logic ‘1’ when all its inputs
are logic ‘0’. For all other input combinations, the output is a logic ‘0’. The output of a two-
input NOR gate is logically expressed as Y = A + B

12 | P a g e
 Truth Table of 2 input NAND Gate:

EX-OR Gate (Exclusive-OR gate):

 The Exclusive-OR gate, commonly known as EX-OR gate, is a two input one-output gate.
The logic symbol for the Ex-OR gate is shown in Figure and the truth table for a two-input
EX-OR operation is given in Table

 From the truth table it can be stated that, the output of an EX-OR gate is a logic ‘1’ when the
two inputs are at different logic and a logic ‘0’ when the two inputs are at the same logic

13 | P a g e
 EX-NOR Gate (Exclusive-NOR gate):
 The Exclusive-NOR gate, commonly known as Ex-NOR, is an Ex-OR gate, followed by an
inverter. It has two inputs and one output. The logic symbol for the Ex-NOR gate is shown in
Figure 2.9, and the truth table for the two-input Ex-NOR operation is given in Table

 Truth Table of 2 input NAND Gate:

The output of a two-input EX-NOR gate is a logic ‘1’ when the inputs are same and a logic
‘0’ when they are different

Universal Gates:

 NAND and NOR gates are known as universal gates because any of these two gates is
capable of implementing all other gate functions.

NAND Gate as a Universal Gates:

 The NAND gate can be used to implement the NOT function, AND function, the OR function
and other functions also as explained below.

The NOT Gate using NAND Gate:

 An inverter can be made from a NAND gate by connecting all of the inputs together and
creating, in effect, a single common input, as shown in Figure, for a two-input NAND gate.
Algebraically, we may write
Y = A . B = A . A = A̅

14 | P a g e
 The AND Gate using NAND Gate:
 To construct an AND gate from NAND gates, an inverter or a NOT gate is required to invert
the output of a NAND gate. This inversion cancels out the first inverted operation of NAND
gate and the final result will be AND function as depicted in Figure. Algebraically,

The OR Gate using NAND Gate:

 To construct OR function using only NAND gates, first we transform the OR function as
follows.
Y = A + B = A̅ + B̅ A̅ = A
= A̅ . B̅ (De Morgan’s Theorem)
The above equation is implemented using only NAND gates as shown in the Figure

The NOR Gate using NAND Gate:

We know that Boolean expression for NOR gate is
Y=A+B=A.B (De Morgan’s Theorem)
= A̅ . B̅ A̅ = A

15 | P a g e
The above equation is implemented using only NAND gates, as shown

The EX-OR Gate using NAND Gate:

The Boolean expression for Ex-OR gate is given by
Y = A̅B + AB̅
= A̅B + AB̅ X̅ = X
= (A̅B) . (AB̅) (De Morgan Theorem)
So, five NAND gates are required to implement the Ex-OR gate as shown in Figure

16 | P a g e
 The EX-NOR Gate using NAND Gate:
Ex-NOR gate can be constructed by taking complement of Ex-OR. Tha is, we need one
more NAND gate to implement the Ex-NOR function Figure shows Ex-NOR
implementation using five NAND gates.

NOR Gate as a Universal Gates:

Just like the NAND gate, the NOR gate also may be used to implement all other operations
of Boolean algebra. These are explained in following texts.
The NOT Gate using NOR Gate:
In the same way as the NAND gate described above, an inverter can be made from a NOR
gate by connecting all of the inputs together and creating, in effect, a single common input,
as shown in Figure. Algebraically,

The OR Gate using NOR Gate:

An OR gate can be created by simply inverting the output of a NOR gate as shown in
Figure. Algebraically,

17 | P a g e
The AND Gate using NOR Gate:
AND function can be generated using three NOR gates. We know that Boolean expression
for AND gate is
Y=A.B
= A̅ . B̅ A̅ = A
= A̅ + B̅ (DeMorgan’s Theorem)

The NAND Gate using NOR Gate:

The Boolean expression for NAND gate is
Y=A.B
= A̅ + B̅ (DeMorgan’s Theorem)
= A̅ + B̅ A̅ = A
The above equation is implemented using only NOR gates, as shown in the Figure

18 | P a g e
The EX-OR Gate using NOR Gate:
XOR function may also be implemented by using NOR gates. The Ex-OR operation is given
by

The above expression can be realized using five NOR gates as shown in Figure

The EX-NOR Gate using NOR Gate:

To implement Ex-NOR gate using NOR gates, we just remove the last NOR gates from the
circuit of Ex-OR gates shown in Figure

19 | P a g e
ALTERNATE LOGIC-GATE REPRESENTATIONS:

We have discussed the five basic logic gates (AND, OR, INVERTER, NAND, and NOR)
and the standard symbols used to represent them in a logic circuit diagram. Most of the logic
networks use standard symbols. But in some networks an alternative set of symbols is used
in addition to the standard symbols. Table shows the alternate set of symbols for the five
basic gates

To convert any normal symbol to its corresponding alternate symbol, the following steps are
used
METHODOLOGY: TO CONVERT STANDARD SYMBOL TO ALTERNATE SYMBOL

Step 1: Add bubbles (indication of inversion) at those input or output points where it is not
present.
Step 2: Remove all pre-existing bubbles of the normal symbol, if there is any at the point
(only NOT, NAND and NOR gates)
Step 3: If the existing normal logic symbol is AND, change it to OR, Similarly, if it is OR,
then change it to AND. There is no change for the triangular symbol of NOT gate

20 | P a g e
 Boolean algebra

 In this section we will introduce the laws of Boolean algebra.

 We will then see how it can be used to design combinational logic circuits
 Combinational logic circuits do not have an internal stored state, i.e., they have no memory.
Consequently the output is solely a function of the current inputs.
 Later, we will study circuits having a stored internal state, i.e., sequential logic circuits.

OR GATE:

A+0 A
A+A A
A+1 1
A + A̅ 1

AND GATE:

Ax0 0
AxA A
Ax1 A
A x A̅ 0

AND takes precedence over OR, e.g. A*B + C*D = (A*B) + (C*D)

Boolean algebra laws:

 Commutation law:
 A+B=B+A
 A×B=B×A
 Associative law:
 (A + B) + C = A + (B + C)
 (A × B) C = A (B × C)

 Distributive law:
 A (B + C + ….) = (A × B) + (B × C) + ….
 A + (B × C × ….) = (A + B) (B + C) ….

 Absorption law:
 A + (A × C ) = A
 A (A + C) = A

21 | P a g e
Examples:

 Show
a.(a̅ + b) = a.b
a.(a̅ + b) = a.a̅ + a.b = 0 + a.b = a.b

 Show
a + (a̅.b) = a + b
a + (a̅.b) = (a + a̅).(a + b) =1.(a + b) = a + b

 A useful technique is to expand each term until it includes one instance of each
variable (or its compliment). It may be possible to simplify the expression by cancelling
terms in this expanded form e.g., to prove the absorption rule:
a + (a.b)= a
a.b + a.b̅ + a.b = a.b + a.b̅ = a.(b + b̅ ) = a.1 = a
EXAMPLE:
Simplify
x.y + y̅.z + x.z + x.y.z
x.y.z + x.y.z̅ + x.y̅.z + x̅.y̅.z + x.y.z + x.y̅.z + x.y.z
x.y.z + x.y.z̅ + x.y̅.z + x̅.y̅.z
x.y.(z + z̅) + y̅.z.(x + x̅)
x.y.1+ y̅.z.1
x.y + y̅.z
DE-MORGANS THEOREM:
a + b + c + ….. = a̅ . b̅ . c̅ ….
a . b . c….. = a̅ + b̅ + c̅ + ……

 In a simple expression like a +b + c….. (or ) a . b. c. …..simply change all operators from
OR to AND (or vice versa), complement each term (put a bar over it) and then
complement the whole expression, i.e,
a + b + c +….. = a̅ . b̅ . c̅ .….
a . b . c .….. = a̅ + b̅ + c̅ +….

22 | P a g e
EXAMPLE:

BOOLEAN ANALYSIS OF LOGIC CIRCUITS:

A Boolean function may be transformed from an algebraic expression into a logic diagram
using AND, OR and NOT gates. This is also referred to as AOI logic. Conversely, a logic
circuit can be transformed into Boolean expressions for the analysis

Converting Boolean Expressions to Logic Diagram:

The simplest way to convert a Boolean expression to a logic circuit is to start with the
output and work towards the input. Assume that the expression Y = AB + AC̅ + A̅BC is to
be realized using AOI logic. Start with the final expression AB + AC̅ + A̅BC , we go
through following steps:
METHODOLOGY: TO CONVERT BOOLEAN EXPRESSION TO LOGIC DIAGRAM:

Step 1: The expression Y = AB + AC + ABC contains three terms (AB, AC̅ , A̅BC ) which
are OR together. So, draw an OR gate with three inputs as shown below.

23 | P a g e
Step 2: AB must be the output of an AND gate whose inputs are A and B and AC must be
output of an AND gate whose inputs are A and C. Similarly, ABC must be output of
a 3-input AND gate with inputs A, B and C. We introduce these three AND gates as
shown below

Step 3: Now, C must be the output of an inverter whose input is C and similarly, A will be
the output of an inverter whose input is A. So we put two inverters as shown below.

24 | P a g e
Converting Logic to Boolean Expressions:
Any logic circuit, no matter how complex it is, can be described using Boolean expressions.
To derive the Boolean expression for a given logic circuit, start from the left-most input and
work toward the final output, writing output for each gate. As an example, consider the logic
diagram shown in Figure. We go through the following steps to get the Boolean expression

METHODOLOGY: TO CONVERT LOGIC DIAGRAM TO BOOLEAN EXPRESSION

Step 1: In the logic diagram shown in Figure 2.22, the output of left-most OR gate with
inputs A and B is (A + B).

Step 2: The output of left-most AND gate with inputs C and D is CD.

Step 3: The outputs of the OR gate and AND gate are the inputs of right-most AND gate.
Therefore, the expression for this AND gate is (A + B) CD, which is the final output
expression for the entire circuit.

Logic Simplification:

 As we have seen previously, Boolean algebra can be used to simplify logical expressions.
This results in easier implementation
Note: The DNF and CNF forms are not simplified.

 However, it is often easier to use a technique known as Karnaugh mapping.

Karnaugh Maps:

 Karnaugh Maps (or K-maps) are a powerful visual tool for carrying out simplification and
manipulation of logical expressions having up to 5 variables

 The K-map is a rectangular array of cells

– Each possible state of the input variables corresponds uniquely to one of the cells
– The corresponding output state is written in each cell

25 | P a g e
K-maps example:

 From truth table to K-Map

 Note that the logical state of the variables follows a Gray code, i.e., only one of them
changes at a time
 The exact assignment of variables in terms of their position on the map is not important
 Having plotted the minterms, how do we use the map to give a simplified expression?
 Group terms
• Having size equal to a power of 2, e.g., 2, 4, 8, etc.
• Large groups best since they contain fewer variables
• Groups can wrap around edges and corners

So, the simplified func. is, f = x̅ + y.z as before

K-maps – 4 variables
K maps from Boolean expressions

 See in a 4 variable map:

1 --variable term occupies 8 cells
2 --variable terms occupy 4 cells
3 --variable terms occupy 2 cells, etc.

26 | P a g e
Example:
Plot f = b̅ and f = b̅ . d̅

 Simplify, f = a̅.b.d̅ + b.c.d + a̅.b.c̅.d + c.d

So, the simplified function. is, f = a̅.b + c.d

27 | P a g e
 COMBINATIONAL LOGICS
Binary Adding Circuits

 We will now look at how binary addition may be implemented using combinational logic
circuits. We will consider:
– Half adder
– Full adder
– Ripple carry adder
Half Adder:

 Adds together two, single bit binary numbers a and b (note: no carry input)
 Has the following truth table:

 By inspection:
sum = a̅.b + a.b̅ = a + b
cout = a.b

Full Adder:

 Adds together two, single bit binary numbers a and b (note: with a carry input)
 Has the following truth table:

28 | P a g e
  Alternatively, Which is similar to previous expression except with the OR replaced by
XOR

Ripple Carry Adder:

 We have seen how we can implement a logic to add two, one bit binary numbers (inc.
carry-in).
 However, in general we need to add together two, n bit binary numbers.
 One possible solution is known as the Ripple Carry Adder
 This is simply n, full adders cascaded together
 Example, 4 bit adder,

29 | P a g e
Design of a half subtractor using NAND gates:

 A half subtractor may be designed by the same method as the half adder. The truth table
for the half subtractor is given in table
 In this table X0 and Y0 are the minuend and subtrahend respectively; D0 the difference
of the two bits (X0 & Y0) and B0 is the borrow bit from the next bit. The Boolean
expressions for Difference D0 and borrow bit B0 are given as:

 The realization of these expressions using NAND gates only may, therefore, be given in
figure

 The symbolic representation of half subtractor is given in figure

Design a Full subtractor using NAND gates:

 The truth table for full subtractor is shown in table, in which X1, Y1 are the minuend and
subtrahend respectively and B0 is the borrow bit from the previous bit. The output terms D1
and B1 are the difference bit and borrow to the next bit.
 The Boolean expression for difference D1 is given by:

30 | P a g e
The Boolean expression for the borrow B1 to the next bit is obtained from the K –map shown in
figure

Where D0 is the difference of the half subtractor.

The full subtractor circuit may now be shown to be implemented using NAND gates as
illustrated in figure

The full subtractor is the combination of two half subtractors and gates as shown in figure,

The symbolic representation of full subtractor is given in figure

31 | P a g e
Comparators:
A digital comparator or magnitude comparator is a hardware electronic device that takes two
numbers as input in binary form and determines whether one number is greater than, less than or
equal to the other number. Comparators are used in central processing unit s (CPUs)
and microcontrollers (MCUs)

Note: An XNOR gate is a basic comparator, because its output is "1" only if its two input bits
are equal.
The analog equivalent of digital comparator is the voltage comparator.
Many microcontrollers have analog comparators on some of their inputs that can be read or
trigger an interrupt.

Consider two 4-bit binary numbers A and B so

A = A3 A2 A1 A0
B = B3 B2 B1 B0
Here each subscript represents one of the digits in the numbers.
Equality
The binary numbers A and B will be equal if all the pairs of significant digits of both numbers are
equal, i.e
A3 = B3, A2 = B2, A1 = B1, and A0 = B0
Since the numbers are binary, the digits are either 0 or 1 and the Boolean function for equality
of any two digits Ai and Bi can be expressed as
Xi = Ai Bi + A̅i B̅i
We can also replace it by XNOR gate in digital electronics. Xi is 1 only if Ai and Bi are equal.
For the equality of A and B, all Xi variables (for i=0,1,2,3) must be 1. So the equality condition
of A and B can be implemented using the AND operation as
(A = B) = X3 X2 X1 X0
The binary variable (A=B) is 1 only if all pairs of digits of the two numbers are equal

Inequality
In order to manually determine the greater of two binary numbers, we inspect the relative
magnitudes of pairs of significant digits, starting from the most significant bit, gradually
proceeding towards lower significant bits until an inequality is found. When an inequality is
found, if the corresponding bit of A is 1 and that of B is 0 then we conclude that A>B.

One-bit binary full comparator, equality, inequality, greater than, less than at gate level. Created
using Logisim.

32 | P a g e
Decoders:
A decoder is a logic circuit which has a set of inputs representing a binary number and gives
only one output corresponding to the input number. The decoder activates one output at a time
depending upon the input binary number; all other outputs will be inactive. Figure shows the
functional block diagram of a decoder having N inputs and K outputs. The possible
combinations of N inputs will be 2N = K, so there will be K outputs.

Below figure shows the circuit diagram of 3 – to – 8 line decoder. It will have three input lines
and 23 = 8 output lines. When the three bit binary number is fed to the input of the decoder, as
discussed above one output line corresponding to input binary is activated and all other output
lines will be inactive. It is also called binary to octal decoder or converter because it takes a
binary code as input and activates one of the eight (octal) output lines corresponding to the input
binary code. The 3 – to – 8 can also be referred to as a 1 – of – 8 line decoder, because only one
of the eight outputs is activated at a time. The truth table for 3 – to – 8 line decoder is shown in
table.

It is clear from the above figure that an Enable input line is connected to the fourth input of
each gate. When the Enable input is connected to logic 0, all the gates will be disabled and
force all output to be zero irrespective of the input data (ABC). However, the decoder will
give the required data when the Enable terminal is held at logic 1. The functional block
diagram of 3 to 8 line decoder is shown in below figure

33 | P a g e
Further it is interesting to note that the decoder can function as a demultiplexer. For example a
2:4 line decoder with Enable terminal can be used as a 1:4 DMUX, if the Enable terminal E is
used as the data input line for the DMUX and the two input A & B of the decoder as the select
terminals for the DMUX. It is illustrated in figure

Decoder/Demultiplexer circuits can be expanded to form the larger decoder circuit. For
example two 3:8 line decoders with Enable terminal can be connected to form ba 4:16 line
decoder. Figure shows the construction of a 4:16 line decoder with two 3:8 line decoders.
From this figure it is clear that when the enable terminal E is 0, decoder (1) is enabled and
decoder (2) is disabled. The decoder (1), therefore, gives the outputs as per the value of
ABC. When the enable terminal E is 1, decoder (1) is disabled and decoder (2) is enabled.
The decoder (2) now gives the output as the input values. Here E terminal works as the most
significant bit and C as the least significant bit. So EABC generates the binary input 0000
through 1111.

Encoder:
An encoder a combinational circuit which performs the reverse operation of decoder. The
decoder accepts N bit input code and activates one of the several outlines corresponding to
that code. However, an encoder has a number of input lines, only one of which is activated
at a time. It provides the N bit code at the output corresponding to activated input line. The
decoders studied in the foregoing section were binary to octal, BCD to decimal decoder etc.
The encoders will therefore, be like octal to binary and decimal to BCD encoders. Figure
shows the functional block diagram of an encoder having K inputs and N outputs. In the K
input lines only one line will be high at a time.

34 | P a g e
Decimal – to – BCD Encoder:

The decimal – to – BCD encoder has 10 inputs – one for each decimal digit, and 4
output lines for BCD codes. The logic symbol of this encoder is shown in figure. Table
shows the truth table for decimal to BCD encoder. The expressions for the output variables
with respect to the truth table are given by:

The logic circuit for the decimal – to – BCD encoder with active high inputs is shown in figure

Octal – to – Binary Encoder:

An octal – to – binary encoder (also known as 8 – line to 3 – line encoder) has 8

input lines and provides three bit output lines for producing output code corresponding to
the activated input line. The truth table for octal – to – binary encoder is given in table.
From this table it may be noted that binary output X0 gives the logic 1 if any of the input
digits D1 or D3 or D5 or D7 is at logic 1. Therefore the Boolean expression for X0 is given
by:
X0 = D1 + D3 + D5 + D7
Similarly, the expressions for X1 and X2 may be given as:
X1 = D2 + D3 + D6 + D7
X2 = D4 + D5 + D6 + D7
The logic circuit for the octal – to – binary encoder with active high inputs is shown in
figure

35 | P a g e
Multiplexers:
A multiplexer (MUX) also known as data selector, is a logic circuit which allows the
digital information from multi-inputs to a single output line. The selection of the input data
to be routed to the output line is done by the select terminals.
The number of select terminals depends on the number of input lines to be routed to
output line, given by the general formula as:
2K = N ,
where N is the number of input lines and K is the number of select terminals. In
other words, if there are 4 input lines to be routed to output line, then two select terminals
are needed as 22 = 4 .
The block diagram for 4:1 multiplexer is shown in figure

In which X0, X1 , X2 , X3 are the 4 input lines and S1 , S0 are the select terminals and
X is the output terminal. Normally a strobe terminal or enable terminal (G) is provided in
the MUXs which is normally active-low. The active-low means it performs the operation
when it is low; it also helps to cascade the MUXs. The Boolean function to perform the
multiplexing action is given as:
X X0 S̅1 S̅0 X1 S̅1 S0 X2 S1 S̅0 X3 S1 S0
The output X will follow the input data depending on the select terminals S1 , S0 , as given in the
table

36 | P a g e
Note that only one of the inputs X0, X1, X2, X3 is routed to the output X (one at a time). The
realization of the Boolean function X with NAND gates only is shown in figure

The MUXs are available in the form of the following IC’s:

74157 quadruple two – input multiplexer/data selector.
74151 A eight - input multiplexer/data selector.
74150 sixteen - input multiplexer/data selector.

Eight - input multiplexer/data selector:

Figure shows the logic block diagram for a 8 – input multiplexer/ data selector IC. It
has 8 data inputs X0 through X7, three data select terminals S2 S1, & S0 and an enable
terminal G. when enable terminal G is high, the multiplexer is disabled and output X is zero
irrespective of the select input terminal. However, when the enable terminal G is low the
input data is routed to the output as per data select terminals S2 S1, & S0 as illustrated in
table

37 | P a g e
Expansion of Multiplexers:

For the expansion of number of input terminals of the multiplexers two MUXs may be
cascaded. Two 4:1 MUXs may be cascaded to form 8:1 MUX. Similarly two 8:1 MUXs
may be cascaded to have a 16:1 multiplexer and so on. Figure 6.6 illustrates how two 4:1
MUXs are cascaded to form 8:1 MUX. The enable terminal G of the MUXs in-conjunction
with a NOT gate provides the third select terminal. When S2 is zero the first MUX will be
enabled and inputs X0 through X3 will be routed to its output; and when S2 is 1, the second
MUX will be enabled, X4 through X7 will be routed to the output of the second MUX. The
outputs of the two MUXs are connected to the inputs of an OR gate which then gives the
final output

Applications of Multiplexers:
Primary aim of the MUXs is the multiplexing operation, that is, the selected input is
routed to the output. In addition to this, Implementation of Boolean function can easily be
done with MUXs, since MUXs are available in the form of integrated circuits. The method
of implementing the Boolean function is that the truth table is first constructed for the given
function to be implemented. Then logic 1 is connected to each data input of the multiplexer
corresponding to each combination of the input variables which has 1 in the output column
of the truth table. The logic 0 is, however, connected to the remaining inputs of the MUX.
The variables are connected to the data select inputs of the multiplexer.
The Boolean functions of N – variables can also be implemented by the Multiplexers
of (N – 1) select lines. A function of 4 variables can be implemented with 8:1 multiplexer
having 3 select lines. Let A, B, C, D are the input variables of the function F, which is to be
implemented with a multiplexer. The variable A is the most significant bit and D is the least
significant bit. Variables B, C, D are assumed to be the select terminals for the multiplexer.
The truth table is drawn for the given function. It is well known that in the truth table
variables BCD progresses twice through the sequence 000, 001…. 111; once with A = 0 and
other with A = 1. The connections to be made to the data inputs of the multiplexer,
following rules are observed.
1. A logical 0 is connected to the data input of MUX, if the 0 occurs at the output in the
truth table, both times when MSB is 0 and 1 (other variables having the same value).
2. A logical 1 is connected to the data input of MUX, if the 1 occurs at the output in the
truth table, both times when MSB is 0 and 1 (other variables having the same value).

38 | P a g e
 3. MSB is connected to the data input of MUX, if the output in the truth table is different
both times when MSB is 0 and 1(other variables having the same value); and also output is
the same as the MSB.
4. The complement of the MSB is connected to the data input of MUX, if the output in the
truth table is same both times when MSB is 0 and 1(other variables having the same value);
and also output is the same as the complement of MSB.

De-Multiplexers:
A demultiplexer performs the reverse process of multiplexer; it receives the information on a
single line and steers to several output lines. Demultiplexer can also be called the Data
Distributor as it can transmit the same data to the different lines. It transmits the data to 2N
output lines, for which the select terminals of N bits are required. For example, to transmit
the single data to four output lines (1:4 DMUX), select terminals of two bits are required;
similarly for 1:8 DMUX select terminals of 3 bits are required and so on. The functional
block diagrams of 1:4 DMUX and 1:8 DMUX are shown in figure respectively

In a 1:4 DMUX, let X is the data input which is to be steered to 4 output lines X0,
X1, X2, X3; the select terminals are S1, S0.
If S1S0 = 00 , the input data X will be go to the output X0.
If S1S0 = 01 , the input data X will be go to the output X1.
If S1S0 = 10 , the input data X will be go to the output X2.
If S1S0 = 11 , the input data X will be go to the output X3.
The Boolean expressions for X0, X1, X2, X3 are given by:
X0 = X × S̅1 × S̅0
X1 = X × S̅1× S0
X2 = X × S1 × S̅0
X3 = X × S1 × S0
The implementation of these functions (or 1:4 DMUX) can be done as shown in figure

39 | P a g e
 Tristate Buffer:
A tristate buffer has two inputs: a data input x and a control input c. The control input acts like a
valve. When the control input is active, the output is the input. That is, it behaves just like a
normal buffer. The "valve" is open.

When the control input is not active, the output is "Z". The "valve" is open, and no electrical
current flows through. Thus, even if x is 0 or 1, that value does not flow through.

Here's a truth table describing the

Behavior of an active-high tristate buffer.

In this case, when the output is Z that means it's

High impedance, neither 0, nor 1, i.e., no current.
As usual, the condensed truth table is more enlightening.
As you can see, when c = 1 the valve is open, and z = x. When c = 0 the valve is closed, and z
= Z (e.g., high impedance/no current).

Active-low tri-state buffers

Some tri-state buffers are active low. In an active-low tri-state buffer, c =
0 turns open the valve, while c = 1 turns it off.
Here's the condensed truth table for an active-low tri-state buffer.
As you can see, when c = 0 the valve is open, and z = x. When c = 1 the valve
is closed, and z = Z (e.g., high impedance/no current). Thus, it has the
opposite behavior of a tri-state buffer.

40 | P a g e
 SEQUENTIAL CIRCUITS

The logic circuits discussed previously are known as combinational logic circuits, in
that the output depends only on the condition of the latest inputs.
However, we will now introduce a type of logic where the output
depends not only on the latest inputs, but also on the condition of earlier inputs. These
circuits are known as sequential, and implicitly they contain memory elements. Sequential
logic is used to construct finite state machines, a basic building block in all digital circuitry.
Virtually all circuits in practical digital devices are a mixture of combinational and
sequential logic.

Digital sequential logic circuits are divided into synchronous and asynchronous types.
In synchronous sequential circuits, the state of the device changes only at discrete times in
response to a clock signal. In asynchronous circuits the state of the device can change at any
time in response to changing inputs.
 Synchronous sequential logic
 Asynchronous sequential logic

Asynchronous sequential logic

Asynchronous sequential logic is not synchronized by a clock signal; the outputs of
the circuit change directly in response to changes in inputs. The advantage of asynchronous
logic is that it can be faster than synchronous logic, because the circuit doesn't have to wait
for a clock signal to process inputs. The speed of the device is potentially limited only by
the propagation delays of the logic gates used.
However, asynchronous logic is more difficult to design and is subject to problems not
encountered in synchronous designs. The main problem is that digital memory elements are
sensitive to the order that their input signals arrive; if two signals arrive at a flip-flop or
latch at almost the same time, which state the circuit goes into can depend on which signal
gets to the gate first. Therefore, the circuit can go into the wrong state, depending on small
differences in the propagation delays of the logic gates. This is called a race condition. This
problem is not as severe in synchronous circuits because the outputs of the memory
elements only change at each clock pulse. The interval between clock signals is designed to
be long enough to allow the outputs of the memory elements to "settle" so they are not
changing when the next clock comes. Therefore, the only timing problems are due to
"asynchronous inputs"; inputs to the circuit from other systems which are not synchronized
to the clock signal.

41 | P a g e
Synchronous sequential logic
Nearly all sequential logic today is clocked or synchronous logic. In a synchronous
circuit, an electronic oscillator called a clock (or clock generator) generates a sequence of
repetitive pulses called the clock signal which is distributed to all the memory elements in
the circuit. The basic memory element in sequential logic is the flip-flop. The output of each
flip-flop only changes when triggered by the clock pulse, so changes to the logic signals
throughout the circuit all begin at the same time, at regular intervals, synchronized by the
clock.
The output of all the storage elements (flip-flops) in the circuit at any given time, the
binary data they contain, is called the state of the circuit. The state of a synchronous circuit
only changes on clock pulses. At each cycle, the next state is determined by the current state
and the value of the input signals when the clock pulse occurs.
The main advantage of synchronous logic is its simplicity. The logic gates which
perform the operations on the data require a finite amount of time to respond to changes to
their inputs. This is called propagation delay. The interval between clock pulses must be
long enough so that all the logic gates have time to respond to the changes and their outputs
"settle" to stable logic values, before the next clock pulse occurs. As long as this condition is
met (ignoring certain other details) the circuit is guaranteed to be stable and reliable. This
determines the maximum operating speed of a synchronous circuit.

Flip-Flops:
In electronics, a flip-flop or latch is a circuit that has two stable states and can be used
to store state information. A flip-flop is a bistable multivibrator. The circuit can be made to
change state by signals applied to one or more control inputs and will have one or two
outputs. It is the basic storage element in sequential logic. Flip-flops and latches are
fundamental building blocks of digital electronics systems used in computers,
communications, and many other types of systems.
Flip-flops and latches are used as data storage elements. A flip-flop stores a
single bit (binary digit) of data; one of its two states represents a "one" and the other
represents a "zero". Such data storage can be used for storage of state, and such a circuit is
described as sequential logic. When used in a finite-state machine, the output and next state
depend not only on its current input, but also on its current state (and hence, previous
inputs). It can also be used for counting of pulses, and for synchronizing variably-timed
input signals to some reference timing signal.
Flip-flops can be either simple (transparent or opaque) or clocked (synchronous or
edge-triggered). Although the term flip-flop has historically referred generically to both
simple and clocked circuits, in modern usage it is common to reserve the term flip-
flop exclusively for discussing clocked circuits; the simple ones are commonly
called latches.
Using this terminology, a latch is level-sensitive, whereas a flip-flop is edge-sensitive.
That is, when a latch is enabled it becomes transparent, while a flip flop's output only
changes on a single type (positive going or negative going) of clock edge.

42 | P a g e
S-R Flip Flop
It is basically S-R latch using NAND gates with an additional enable input. It is also
called as level triggered SR-FF. For this, circuit in output will take place if and only if the
enable input (E) is made active. In short this circuit will operate as an S-R latch if E = 1 but
there is no change in the output if E = 0.

Block Diagram

Circuit Diagram

Truth Table

43 | P a g e
Operation

S.N. Condition Operation

1 S = R = 0 : No If S = R = 0 then output of NAND gates 3 and 4 are

change forced to become 1.
Hence R' and S' both will be equal to 1. Since S' and R'
are the input of the basic S-R latch using NAND gates, there
will be no change in the state of outputs.

2 S = 0, R = 1, E = Since S = 0, output of NAND-3 i.e. R' = 1 and E = 1 the

1 output of NAND-4 i.e. S' = 0.
Hence Qn+1 = 0 and Qn+1 bar = 1. This is reset condition.

3 S = 1, R = 0, E = Output of NAND-3 i.e. R' = 0 and output of NAND-4

1 i.e. S' = 1.
Hence output of S-R NAND latch is Qn+1 = 1 and
Qn+1 bar = 0. This is the reset condition.

4 S = 1, R = 1, E = As S = 1, R = 1 and E = 1, the output of NAND gates 3

1 and 4 both are 0 i.e. S' = R' = 0.
Hence the Race condition will occur in the basic NAND
latch.

Master Slave JK Flip Flop:

Master slave JK FF is a cascade of two S-R FF with feedback from the output of
second to input of first. Master is a positive level triggered. But due to the presence of the
inverter in the clock line, the slave will respond to the negative level. Hence when the clock
= 1 (positive level) the master is active and the slave is inactive. Whereas when clock = 0
(low level) the slave is active and master is inactive.

Circuit Diagram

44 | P a g e
 Truth Table

Operation

S.N. Condition Operation

1 J = K = 0 (No When clock = 0, the slave becomes active and master is

change) inactive. But since the S and R inputs have not changed, the slave
outputs will also remain unchanged. Therefore outputs will not
change if J = K =0.

2 J = 0 and K = 1 Clock = 1 − Master active, slave inactive. Therefore outputs of

(Reset) the master become Q1 = 0 and Q1 bar = 1. That means S = 0 and R
=1.
Clock = 0 − Slave active, master inactive. Therefore outputs of
the slave become Q = 0 and Q bar = 1.
Again clock = 1 − Master active, slave inactive. Therefore even
with the changed outputs Q = 0 and Q bar = 1 fed back to master, its
output will be Q1 = 0 and Q1 bar = 1. That means S = 0 and R = 1.
Hence with clock = 0 and slave becoming active the outputs of
slave will remain Q = 0 and Q bar = 1. Thus we get a stable output
from the Master slave.

3 J = 1 and K = 0 Clock = 1 − Master active, slave inactive. Therefore outputs of

(Set) the master become Q1 = 1 and Q1 bar = 0. That means S = 1 and R
=0.
Clock = 0 − Slave active, master inactive. Therefore outputs of
the slave become Q = 1 and Q bar = 0.
Again clock = 1 − then it can be shown that the outputs of the
slave are stabilized to Q = 1 and Q bar = 0.

4 J=K=1 Clock = 1 − Master active, slave inactive. Outputs of master

(Toggle) will toggle. So S and R also will be inverted.
Clock = 0 − Slave active, master inactive. Outputs of slave will
toggle.
These changed output are returned back to the master inputs.
But since clock = 0, the master is still inactive. So it does not respond
to these changed outputs. This avoids the multiple toggling which
leads to the race around condition. The master slave flip flop will
avoid the race around condition.

45 | P a g e
Delay Flip Flop / D Flip Flop
Delay Flip Flop or D Flip Flop is the simple gated S-R latch with a NAND inverter
connected between S and R inputs. It has only one input. The input data is appearing at the
output after some time. Due to this data delay between i/p and o/p, it is called delay flip
flop. S and R will be the complements of each other due to NAND inverter. Hence S = R =
0 or S = R = 1, these input condition will never appear. This problem is avoid by SR = 00
and SR = 1 conditions.

Block Diagram

Circuit Diagram

Truth Table

Operation

S.N. Condition Operation

1 E=0 Latch is disabled. Hence no change in output.

2 E = 1 and D = 0 If E = 1 and D = 0 then S = 0 and R = 1. Hence

irrespective of the present state, the next state is Qn+1 = 0 and
Qn+1 bar = 1. This is the reset condition.

46 | P a g e
 3 E = 1 and D = 1 If E = 1 and D = 1, then S = 1 and R = 0. This will set
the latch and Qn+1 = 1 and Qn+1 bar = 0 irrespective of the
present state.

Toggle Flip Flop / T Flip Flop

Toggle flip flop is basically a JK flip flop with J and K terminals permanently
connected together. It has only input denoted by T as shown in the Symbol Diagram. The
symbol for positive edge triggered T flip flop is shown in the Block Diagram.

Symbol Diagram

Block Diagram:

Truth Table

Operation

S.N. Condition Operation

1 T = 0, J = K = 0 The output Q and Q bar won't change

2 T = 1, J = K = 1 Output will toggle corresponding to every leading edge

of clock signal.

47 | P a g e
Registers:
Flip-flop is a 1 bit memory cell which can be used for storing the digital data. To
increase the storage capacity in terms of number of bits, we have to use a group of flip-flop.
Such a group of flip-flop is known as a Register. The n-bit register will consist of n number
of flip-flop and it is capable of storing an n-bit word.
The binary data in a register can be moved within the register from one flip-flop to
another. The registers that allow such data transfers are called as shift registers. There are
four mode of operations of a shift register.
 Serial Input Serial Output
 Serial Input Parallel Output
 Parallel Input Serial Output
 Parallel Input Parallel Output

Serial Input Serial Output

Let all the flip-flop be initially in the reset condition i.e. Q3 = Q2= Q1 = Q0 = 0. If an
entry of a four bit binary number 1 1 1 1 is made into the register, this number should be
applied to Din bit with the LSB bit applied first. The D input of FF-3 i.e. D3 is connected to
serial data input Din. Output of FF-3 i.e. Q3 is connected to the input of the next flip-flop i.e.
D2 and so on.

Block Diagram

Operation
Before application of clock signal, let Q3 Q2 Q1 Q0 = 0000 and apply LSB bit of the
number to be entered to Din. So Din = D3 = 1. Apply the clock. On the first falling edge of
clock, the FF-3 is set, and stored word in the register is Q3 Q2 Q1 Q0 = 1000.

Apply the next bit to Din. So Din = 1. As soon as the next negative edge of the clock
hits, FF-2 will set and the stored word change to Q3 Q2 Q1 Q0 = 1100.

48 | P a g e
 Apply the next bit to be stored i.e. 1 to Din. Apply the clock pulse. As soon as the third
negative clock edge hits, FF-1 will be set and output will be modified to Q3 Q2 Q1 Q0 =
1110.

Similarly with Din = 1 and with the fourth negative clock edge arriving, the stored
word in the register is Q3 Q2 Q1 Q0 = 1111.

Truth Table

49 | P a g e
Waveforms

Serial Input Parallel Output

 In such types of operations, the data is entered serially and taken out in parallel
fashion.
 Data is loaded bit by bit. The outputs are disabled as long as the data is loading.
 As soon as the data loading gets completed, all the flip-flops contain their required
data, the outputs are enabled so that all the loaded data is made available over all the
output lines at the same time.
 4 clock cycles are required to load a four bit word. Hence the speed of operation of
SIPO mode is same as that of SISO mode.

Block Diagram

Parallel Input Serial Output (PISO)

 Data bits are entered in parallel fashion.

 The circuit shown below is a four bit parallel input serial output register.
 Output of previous Flip Flop is connected to the input of the next one via a
combinational circuit.
 The binary input word B0, B1, B2, B3 is applied though the same combinational circuit.
 There are two modes in which this circuit can work namely - shift mode or load mode.

50 | P a g e
Load mode
When the shift/load bar line is low (0), the AND gate 2, 4 and 6 become active they
will pass B1, B2, B3 bits to the corresponding flip-flops. On the low going edge of clock, the
binary input B0, B1, B2, B3 will get loaded into the corresponding flip-flops. Thus parallel
loading takes place.

Shift mode
When the shift/load bar line is low (1), the AND gate 2, 4 and 6 become inactive.
Hence the parallel loading of the data becomes impossible. But the AND gate 1,3 and 5
become active. Therefore the shifting of data from left to right bit by bit on application of
clock pulses. Thus the parallel in serial out operation takes place.

Block Diagram

Parallel Input Parallel Output (PIPO)

In this mode, the 4 bit binary input B0, B1, B2, B3 is applied to the data inputs D0, D1,
D2, and D3 respectively of the four flip-flops. As soon as a negative clock edge is applied,
the input binary bits will be loaded into the flip-flops simultaneously. The loaded bits will
appear simultaneously to the output side. Only clock pulse is essential to load all the bits.

Block Diagram

51 | P a g e
 Bidirectional Shift Register
 If a binary number is shifted left by one position then it is equivalent to multiplying the
original number by 2. Similarly if a binary number is shifted right by one position then it is
equivalent to dividing the original number by 2.
 Hence if we want to use the shift register to multiply and divide the given binary number,
then we should be able to move the data in either left or right direction.
 Such a register is called bi-directional register. A four bit bi-directional shift register is
shown in fig.
 There are two serial inputs namely the serial right shift data input DR, and the serial left
shift data input DL along with a mode select input (M).

Block Diagram

Operation

S.N. Condition Operation

1 With M = 1 − If M = 1, then the AND gates 1, 3, 5 and 7 are enabled

Shift right whereas the remaining AND gates 2, 4, 6 and 8 will be
operation disabled.
The data at DR is shifted to right bit by bit from FF-3 to
FF-0 on the application of clock pulses. Thus with M = 1 we
get the serial right shift operation.

2 With M = 0 − When the mode control M is connected to 0 then the

Shift left AND gates 2, 4, 6 and 8 are enabled while 1, 3, 5 and 7 are
operation disabled.
The data at DL is shifted left bit by bit from FF-0 to FF-3
on the application of clock pulses. Thus with M = 0 we get the
serial right shift operation.

52 | P a g e
Universal Shift Register
A shift register which can shift the data in only one direction is called a uni-directional
shift register. A shift register which can shift the data in both directions is called a bi-
directional shift register. Applying the same logic, a shift register which can shift the data in
both directions as well as load it parallel, is known as a universal shift register. The shift
register is capable of performing the following operation −
 Parallel loading
 Lift shifting
 Right shifting
The mode control input is connected to logic 1 for parallel loading operation whereas
it is connected to 0 for serial shifting. With mode control pin connected to ground, the
universal shift register acts as a bi-directional register. For serial left operation, the input is
applied to the serial input which goes to AND gate-1 shown in figure. Whereas for the shift
right operation, the serial input is applied to D input.

Block Diagram

53 | P a g e
Counters:
Counter is a sequential circuit. A digital circuit which is used for a counting pulses is
known counter. Counter is the widest application of flip-flops. It is a group of flip-flops with
a clock signal applied. Counters are of two types.
 Asynchronous or ripple counters.
 Synchronous counters.

Asynchronous or ripple counters

The logic diagram of a 2-bit ripple up counter is shown in figure. The toggle (T) flip-
flop are being used. But we can use the JK flip-flop also with J and K connected
permanently to logic 1. External clock is applied to the clock input of flip-flop A and QA
output is applied to the clock input of the next flip-flop i.e. FF-B.

Logical Diagram

Operation

S.N. Condition Operation

1 Initially let both QBQA = 00 initially

the FFs be in the
reset state

2 After 1st negative As soon as the first negative clock edge is applied, FF-
clock edge A will toggle and QA will be equal to 1.
QA is connected to clock input of FF-B. Since QA has
changed from 0 to 1, it is treated as the positive clock edge
by FF-B. There is no change in QB because FF-B is a
negative edge triggered FF.
QBQA = 01 after the first clock pulse.

3 After 2nd negative On the arrival of second negative clock edge, FF-A
clock edge toggles again and QA = 0.
The change in QA acts as a negative clock edge for FF-
B. So it will also toggle, and QB will be 1.
QBQA = 10 after the second clock pulse.

54 | P a g e
 4 After 3rd negative On the arrival of 3rd negative clock edge, FF-A
clock edge toggles again and QA become 1 from 0.
Since this is a positive going change, FF-B does not
respond to it and remains inactive. So QB does not change
and continues to be equal to 1.
QBQA = 11 after the third clock pulse.

5 After 4th negative On the arrival of 4th negative clock edge, FF-A
clock edge toggles again and QA becomes 1 from 0.
This negative change in QA acts as clock pulse for FF-
B. Hence it toggles to change QB from 1 to 0.
QBQA = 00 after the fourth clock pulse.

Truth Table

Synchronous counters
If the "clock" pulses are applied to all the flip-flops in a counter simultaneously, then
such a counter is called as synchronous counter.

2-bit Synchronous up counter

The JA and KA inputs of FF-A are tied to logic 1. So FF-A will work as a toggle flip-
flop. The JB and KB inputs are connected to QA.

Logical Diagram

55 | P a g e
Operation

S.N. Condition Operation

1 Initially let both QBQA = 00 initially.

the FFs be in the
reset state

2 After 1st As soon as the first negative clock edge is applied, FF-
negative clock A will toggle and QA will change from 0 to 1.
edge But at the instant of application of negative clock edge,
QA , JB = KB = 0. Hence FF-B will not change its state. So
QB will remain 0.
QBQA = 01 after the first clock pulse.

3 After 2nd On the arrival of second negative clock edge, FF-A

negative clock toggles again and QA changes from 1 to 0.
edge But at this instant QA was 1. So JB = KB= 1 and FF-B
will toggle. Hence QB changes from 0 to 1.
QBQA = 10 after the second clock pulse.

4 After 3rd On application of the third falling clock edge, FF-A will
negative clock toggle from 0 to 1 but there is no change of state for FF-B.
edge QBQA = 11 after the third clock pulse.

5 After 4th On application of the next clock pulse, QA will change

negative clock from 1 to 0 as QB will also change from 1 to 0.
edge QBQA = 00 after the fourth clock pulse.

Classification of counters
Depending on the way in which the counting progresses, the synchronous or
asynchronous counters are classified as follows −
 Up counters
 Down counters
 Up/Down counters

UP/DOWN Counter
Up counter and down counter is combined together to obtain an UP/DOWN counter.
A mode control (M) input is also provided to select either up or down mode. A
combinational circuit is required to be designed and used between each pair of flip-flop in
order to achieve the up/down operation.
 Type of up/down counters
 UP/DOWN ripple counters
 UP/DOWN synchronous counter

56 | P a g e
UP/DOWN Ripple Counters
In the UP/DOWN ripple counter all the FFs operate in the toggle mode. So either T
flip-flops or JK flip-flops are to be used. The LSB flip-flop receives clock directly. But the
clock to every other FF is obtained from (Q = Q bar) output of the previous FF.
 UP counting mode (M=0) − The Q output of the preceding FF is connected to the
clock of the next stage if up counting is to be achieved. For this mode, the mode
select input M is at logic 0 (M=0).
 DOWN counting mode (M=1) − If M = 1, then the Q bar output of the preceding
FF is connected to the next FF. This will operate the counter in the counting mode.

Example
3-bit binary up/down ripple counter.
 3-bit − hence three FFs are required.
 UP/DOWN − so a mode control input is essential.
 For a ripple up counter, the Q output of preceding FF is connected to the clock input
of the next one.
 For a ripple up counter, the Q output of preceding FF is connected to the clock input
of the next one.
 For a ripple down counter, the Q bar output of preceding FF is connected to the
clock input of the next one.
 Let the selection of Q and Q bar output of the preceding FF be controlled by the
mode control input M such that, If M = 0, UP counting. So connect Q to CLK. If M
= 1, DOWN counting. So connect Q bar to CLK.

Block Diagram

Truth Table

57 | P a g e
Operation

S.N. Condition Operation

1 Case 1 − With If M = 0 and M bar = 1, then the AND gates 1 and 3 in

M = 0 (Up fig. will be enabled whereas the AND gates 2 and 4 will be
counting mode) disabled.
Hence QA gets connected to the clock input of FF-B and
QB gets connected to the clock input of FF-C.
These connections are same as those for the normal up
counter. Thus with M = 0 the circuit work as an up counter.

2 Case 2: With If M = 1, then AND gates 2 and 4 in fig. are enabled

M = 1 (Down whereas the AND gates 1 and 3 are disabled.
counting mode) Hence QA bar gets connected to the clock input of FF-B
and QB bar gets connected to the clock input of FF-C.
These connections will produce a down counter. Thus
with M = 1 the circuit works as a down counter.

Modulus Counter (MOD-N Counter)

The 2-bit ripple counter is called as MOD-4 counter and 3-bit ripple counter is called
as MOD-8 counter. So in general, an n-bit ripple counter is called as modulo-N counter.
Where, MOD number = 2n.

Type of modulus
 2-bit up or down (MOD-4)
 3-bit up or down (MOD-8)
 4-bit up or down (MOD-16)

Application of counters
 Frequency counters
 Digital clock
 Time measurement
 A to D converter
 Frequency divider circuits
 Digital triangular wave generator.

58 | P a g e
Synchronous State Machines
• We have seen how we can use FFs (D-types in particular) to design synchronous counters
• We will now investigate how these principles can be extended to the design of
synchronous state machines (of which counters are a subset)
• We will begin with some definitions and then introduce two popular types of machines

Definitions
 Finite State Machine (FSM) – a deterministic machine (circuit) that produces outputs
which depend on its internal state and external inputs
 States – the set of internal memorized values, shown as circles on the state diagram
 Inputs – External stimuli, labelled as arcs on the state diagram
 Outputs – Results from the FSM

Types of State Machines

 Two types of state machines are in general use, namely Moore machines and Mealy
machines
 In this course we will only look in detail at FSM design using Moore machines,
although for completeness we will briefly describe the structure of Mealy machines

Mealy vs. Moore Machines

 Moore: outputs depend on current state only
 Mealy: outputs depend on current state and inputs
 Ant brain is a Moore Machine
 Output does not react immediately to input change
 We could have specified a Mealy FSM
 Outputs have immediate reaction to inputs
 As inputs change, so does next state, doesn’t commit until clocking event

Specifying Outputs for a Moore Machine

 Output is only function of state
 Specify in state bubble in state diagram
 Example: sequence detector for 01 or 10

59 | P a g e
Specifying Outputs for a Mealy Machine
 Output is function of state and inputs
 Specify output on transition arc between states
 Example: sequence detector for 01 or 10

Comparison of Mealy and Moore Machines

 Mealy Machines tend to have less states
– Different outputs on arcs (n2) rather than states (n)
 Moore Machines are safer to use
– Outputs change at clock edge (always one cycle later)
– In Mealy machines, input change can cause output change as soon as logic is
done – a big problem when two machines are interconnected – asynchronous
feedback
 Mealy Machines react faster to inputs
– React in same cycle – don't need to wait for clock
– In Moore machines, more logic may be necessary to decode state into outputs –
more gate delays after

Machine Schematics

60 | P a g e
Moore Machine - Example
 We will design a Moore Machine to implementation traffic light controller
 In order to visualize the problem it is often helpful to draw the state transition diagram
 This is used to generate the state transition table
 The state transition table is used to generate
– The next state combinational logic
– The output combinational logic (if required)

Example – Traffic Light Controller

 See we have 4 states
 So in theory we could use a minimum of 2 FFs
 However, by using 3 FFs we will see that we do not need to use any output
combinational logic
 So, we will only use 4 of the 8 possible states
 In general, state assignment is a difficult problem and the optimum choice is not always
obvious
 By using 3 FFs (we will use D-types), we can
assign one to each of the required outputs (R, A,
G), eliminating the need for output logic
 We now need to write down the state transition
table We will label the FF outputs R, A and G
 Remember we do not need to explicitly include
columns for FF excitation since if we use D-
types these are identical to the next state

 Unused states, 000, 011, 101 and 111. Since

these states will never occur, we don’t care what
output the next state combinational logic gives for
these inputs. These don’t care conditions can be used
to simplify the required next state combinational
logic
 We now need to determine the next state
combinational logic
 Unused states, 000, 011, 101 and 111.
 For the R FF, we need to determine DR To do this
we will use a K-map

 By inspection we can also see: DA = A̅

and, DG = R.A

61 | P a g e
FSM Problems
 Consider what could happen on power-up
 The state of the FFs could by chance be in one of the unused states
– This could potentially cause the machine to become stuck in some unanticipated
sequence of states which never goes back to a used state
What can be done?
 Check to see if the FSM can eventually enter a known state from any of the unused
states
 If not, add additional logic to do this, i.e., include unused states in the state transition
table along with a valid next state
 Alternatively use asynchronous Clear and Preset FF inputs to set a known (used) state at
power up

Example – Traffic Light Controller

 Does the example FSM self-start?

 Check what the next state logic outputs if we begin in any of the unused states
 Turns out:

Example 2
 We extend Example 1 so that the traffic signals spend extra time for the R and G lights
 Essentially, we need 2 additional states, i.e., 6 in total.
 In theory, the 3 FF machine gives us the potential for sufficient states
 However, to make the machine combinational logic easier, it is more convenient to add
another FF (labelled S), making 4 in total

 See that new FF toggles which makes the next

state logic easier
 As before, the first step is to write down the
state transition table
 Clearly a lot of unused states. When plotting k-
maps to determine the next state logic it is
probably easier to plot 0s and 1s in the map and
then mark the unused states

62 | P a g e
 We will now use k-maps to determine the next state combinational logic
 For the R FF, we need to determine DR

 We can plot k-maps for DA and DG to give:

 By inspection we can also see: Ds = s̅

State Assignment:
 As we have mentioned previously, state assignment is not necessarily obvious or
straightforward
– Depends what we are trying to optimize, e.g.,
 Complexity (which also depends on the implementation technology, e.g., FPGA, 74
series logic chips).
– FF implementation may take less chip area than you may think given their gate level
representation
– Wiring complexity can be as big an issue as gate complexity
 Speed
– Algorithms do exist for selecting the ‘optimizing’ state assignment, but are not
suitable for manual execution
 If we have m states, we need at least FFs (or more informally, bits) to encode the states,
e.g., for 8 states we need a min of 3 FFs
 We will now present an example giving various potential state assignments, some using
more FFs than the minimum.

Sequential State Assignment

 Here we simply assign the states in an increasing natural binary count
 As usual we need to write down the state transition table. In this case we need 5 states,
i.e., a minimum of 3 FFs (or state bits). We will designate the 3 FF outputs as c, b, and a
 We can then determine the necessary next state logic and any output logic.
 By inspection we can see: The required output is from FF b Plot k-maps to determine
the next state logic: For FF a:

63 | P a g e
Sliding State Assignment
 By inspection we can see that we can use any of the FF outputs as the wanted output
 Plot k-maps to determine the next state logic:

 By inspection we can see that:

o For FF b: Db = a
o For FF c: Dc = b

Shift Register Assignment

 As the name implies, the FFs are connected together to form a shift register. In addition,
the output from the final shift register in the chain is connected to the input of the first
FF:
 Consequently the data continuously cycles through the register
 Because of the shift register configuration and also from the state table we can see that:
Da = e
Db = a
Dc = b
Dd = c
De = d
 By inspection we can see that we can use any of the FF
outputs as the wanted output
 See needs 2 more FFs, but no logic and simple wiring

64 | P a g e
One Hot State Encoding

 This is a shift register design style where only FF at a time holds a 1

 Consequently we have 1 FF per state, compared with log2m for sequential assignment
 However, can result in simple fast state machines
 Outputs are generated by OR together appropriate FF outputs

 We will return to the traffic signal example, which recall has 4

states
 For 1 hot, we need 1 FF for each state, i.e., 4 in this case
 The FFs are connected to form a shift register as in the previous
shift register example, however in 1 hot, only 1 FF holds a 1 at
any time
 We can write down the state transition table as follows

 Because of the shift register configuration and also from the

state table we can see that: Da = g, Dg = ra, Dra = r, Dr = a
 To generate the R, A and G output we do the following OR: R
= r + ra, A = ra + a, G=g

65 | P a g e
 MEMORIES
Semiconductor memory is an electronic data storage device, often used as
computer memory, implemented on a semiconductor-based integrated circuit. There are
many different types of implementations using various technologies. Most types of
semiconductor memory have the property of random access, which means that it takes the
same amount of time to access any memory location, so data can be efficiently accessed in
any random order. This contrasts with data storage media such as hard disks and CDs which
read and write data consecutively and therefore the data can only be accessed in the same
sequence it was written. Semiconductor memory also has much faster access times than
other types of data storage; a byte of data can be written to or read from semiconductor
memory within a few nanoseconds, while access time for rotating storage such as hard disks
is in the range of milliseconds. For these reasons it is used for main computer memory
(primary storage), to hold data the computer is currently working on, among other uses.
Shift registers, processor registers, data buffers and other small digital registers that have no
memory address decoding mechanism are not considered as memory although they also
store digital data.
Description:
In a semiconductor memory chip, each bit of binary data is stored in a tiny circuit
called a memory cell consisting of one to several transistors. The memory cells are laid out
in rectangular arrays on the surface of the chip. The 1-bit memory cells are grouped in small
units called words which are accessed together as a single memory address. Memory is
manufactured in word length that is usually a power of two, typically N=1, 2, 4 or 8 bits.
Data is accessed by means of a binary number called a memory address applied to
the chip's address pins, which specifies which word in the chip is to be accessed. If the
memory address consists of M bits, the number of addresses on the chip is 2M, each
containing an N bit word. Consequently, the amount of data stored in each chip is N2M bits.
The memory storage capacity for M number of address lines is given by 2M, which is
usually in power of two: 2, 4, 8, 16, 32, 64, 128, 256 and 512 and measured in kilobits,
megabits, gigabits or terabits, etc. As of 2014 the largest semiconductor memory chips hold
a few gigabits of data, but higher capacity memory is constantly being developed. By
combining several integrated circuits, memory can be arranged into a larger word length
and/or address space than what is offered by each chip, often but not necessarily a power of
two.
The two basic operations performed by a memory chip are "read", in which the data
contents of a memory word is read out (nondestructively), and "write" in which data is
stored in a memory word, replacing any data that was previously stored there. To increase
data rate, in some of the latest types of memory chips such as DDR SDRAM multiple words
are accessed with each read or write operation.
In addition to standalone memory chips, blocks of semiconductor memory are
integral parts of many computer and data processing integrated circuits. For example, the
microprocessor chips that run computers contain cache memory to store instructions
awaiting execution.

66 | P a g e
Types:
RAM (Random-access memory) has become a generic term for any semiconductor
memory that can be written to, as well as read from, in contrast to ROM (below), which can
only be read. All semiconductor memory, not just RAM, has the property of random access.
Volatile memory loses its stored data when the power to the memory chip is turned off.
However it can be faster and less expensive than non-volatile memory. This type is used for
the main memory in most computers, since data is stored on the hard disk while the
computer is off. Major types are
 DRAM (Dynamic random-access memory) which uses memory cells consisting of one
capacitor and one transistor to store each bit. This is the cheapest and highest in density, so
it is used for the main memory in computers. However the electric charge that stores the
data in the memory cells slowly leaks out, so the memory cells must be periodically
refreshed (rewritten) which requires additional circuitry. The refresh process is handled
internally by the computer and is transparent to its user

 FPM DRAM (Fast page mode DRAM) An older type of asynchronous DRAM that
improved on previous types by allowing repeated accesses to a single "page" of memory to
occur at a faster rate. Used in the mid- 1990s.

 EDO DRAM (Extended data out DRAM) An older type of asynchronous DRAM which
had faster access time than earlier types by being able to initiate a new memory access while
data from the previous access was still being transferred. Used in the later part of the 1990s.

 VRAM (Video random access memory) An older type of dual-ported memory once used
for the frame buffers of video adapters (video cards).

 SDRAM (Synchronous dynamic random-access memory) This added circuitry to the

DRAM chip which synchronizes all operations with a clock signal added to the computer's
memory bus. The data on the chip is divided into banks which can each work on a memory
operation simultaneously. This became the dominant type of computer memory by about the
year 2000.

 DDR SDRAM (Double data rate SDRAM) This could transfer twice the data (two
consecutive words) on each clock cycle by double pumping (transferring data on both the
rising and falling edges of the clock pulse). Extensions of this idea are the current (2012)
technique being used to increase memory access rate and throughput. Since it is proving
difficult to further increase the internal clock speed of memory chips, these chips increase
the transfer rate by transferring more data words on each clock cycle

 DDR2 SDRAM transfers 4 consecutive words per internal clock cycle

 DDR3 SDRAM transfers 8 consecutive words per internal clock cycle.
 DDR4 SDRAM transfers 16 consecutive words per internal clock cycle.

67 | P a g e
 RDRAM (Rambus DRAM) an alternate double data rate memory standard that was used
on some Intel systems but ultimately lost out to DDR SDRAM.

 SGRAM (Synchronous graphics RAM) a specialized type of SDRAM made for graphics
adaptors (video cards). It can perform graphics-related operations such as bit masking and
block write, and can open two pages of memory at once.

 PSRAM (Pseudo static RAM) This is DRAM which has circuitry to perform memory
refresh on the chip, so that it acts like SRAM, allowing the external memory controller to be
shut down to save energy. It is used in a few game consoles such as the Wii.

 SRAM (Static random-access memory) which relies on several transistors forming a

digital flip-flop to store each bit. This is less dense and more expensive per bit than DRAM,
but faster and does not require memory refresh. It is used for smaller cache memories in
computers.

 Content-addressable memory this is a specialized type in which, instead of accessing data

using an address, a data word is applied and the memory returns the location if the word is
stored in the memory. It is mostly incorporated in other chips such as microprocessors
where it is used for cache memory.

Nonvolatile memory preserves the data stored in it during periods when the power to
the chip is turned off. Therefore, it is used for the memory in portable devices, which don't have
disks, and for removable memory cards among other uses. Major types are:
ROM (Read-only memory) this is designed to hold permanent data, and in normal
operation is only read from, not written to. Although many types can be written to, the writing
process is slow and usually all the data in the chip must be rewritten at once. It is usually used
to store system software which must be immediately accessible to the computer, such as the
BIOS program which starts the computer, and the software (microcode) for portable devices and
embedded computers such as microcontrollers.
 Mask programmed ROM In this type the data is programmed into the chip during
manufacture, so it is only used for large production runs. It cannot be rewritten with new
data.

 PROM (Programmable read-only memory) in this type the data is written into the chip
before it is installed in the circuit, but it can only be written once. The data is written by
plugging the chip into a device called a PROM programmer.

 EPROM (Erasable programmable read-only memory) in this type the data in it can be
rewritten by removing the chip from the circuit board, exposing it to an ultraviolet light to
erase the existing data, and plugging it into a PROM programmer. The IC package has a
small transparent "window" in the top to admit the UV light. It is often used for prototypes
and small production run devices, where the program in it may have to be changed at the
factory.

68 | P a g e
 EEPROM (Electrically erasable programmable read-only memory) in this type the data
can be rewritten electrically, while the chip is on the circuit board, but the writing process is
slow. This type is used to hold firmware, the low level microcode which runs hardware
devices, such as the BIOS program in most computers, so that it can be updated.

 NVRAM (Flash memory) in this type the writing process is intermediate in speed between
EEPROMS and RAM memory; it can be written to, but not fast enough to serve as main
memory. It is often used as a semiconductor version of a hard disk, to store files. It is used
in portable devices such as PDAs, USB flash drives, and removable memory cards used in
digital cameras and cellphones.

Programmable Logic Devices:

Different gates and other combinational logic circuits available in the form of ICs
are used for the logic designs. In many system designs, the designers use large number of ICs,
since such circuits have several input and output variables. The recent development of
programmable logic devices has presented a cost effective method of realizing such circuits.
The programmable logic devices (PLDs) are medium scale integrated circuits and these devices
can replace a number of standard ICs. Thus PLDs help in designing larger circuit on small space
with ease.
A PLD is a programmable IC which contains large number of interconnected gates,
flip – flops and registers etc. Many of the interconnections are fusible. The connections which
are not required by the designers are fused or broken. Programming of fuse blowing as per the
required circuit pattern is done by the manufacturer or by the customer.
PLDs fall into three categories. They are known as:
(i) Field Programmable Logic Array (FPLA)
(ii) Programmable Array logic
(iii) Programmable Read Only Memory (PROM)
PLDs consist of an array of AND gates followed by an array of OR gates. Both true
and complement form of the input variables are fed to AND array. Simplified procedure is
adopted to represent the internal circuitry of these devices. Below Figure demonstrate the
connection to an AND gate. The circled cross marks ( ) to the input lines shows the fusible
connections to the input lines. If there is no circled cross mark, it indicates that the connection
has been broken or fused. Further, the dot marks ( ) on the input lines show the hard wire
connections to the corresponding input lines. Below Figure indicates a four input AND gate
with fusible connections to A, A, B, B inputs. If the connections are fused to A and B inputs,
then no mark will be shown to these points refer below figure. The output of this AND gate is
A× B. Similarly, the dot marks ( ) to the input lines indicate the hardwire connection to the input
lines. The output of this gate is A× B. Similar connections are used for OR array also.

69 | P a g e
Field Programmable Logic Array (FPLA):
Below Figure demonstrates the basic structure of Field Programmable Logic array
(FPLA). In this logic device, both AND array and OR array are programmable. The circled
cross marks to the input lines of AND and OR gates indicate that these connections are fusible
or programmable. It may be noted from the architecture of the FPLA that when it is not
programmed all the true and complemented variables are connected to the inputs of each AND
gate. The AND gates will give the outputs 0, since X0. X̅0. X1. X̅1 . . . . = 0. The outputs of the
OR gates will also be zero since it is the summation of outputs of all AND gates. So when
FPLA is not programmed all outputs of the device will be zero. Now if the circled cross mark of
some inputs of AND gate are burnt (or programmed to remove fuse), then min-term of the
remaining input variables (or their complements) will be obtained. Similarly by burning the
unused circled cross marks of OR array will give the required outputs in SOP form. So the
programming of the device allows the implementation of arbitrary logic functions in a two level
sum – of – product (SOP) form. The AND array creates the required minterms, while the OR

70 | P a g e
array takes the sum of products to form the outputs. It is very versatile since both AND and OR
arrays are programmable. However, it has some disadvantages; it is more difficult to
manufacture, program or test than other PLD’s
FPLA has a number of input variables, AND gates and OR gates. The actual FPLA
available are specified by p x q x r, where p is the number of input variables, q is the number of
AND gates and r is the number of OR gates (outputs). One FPLA 840 has 14 input variables, 32
AND gates and 6 OR gates.

Example:
Consider a FPLA of 4 input variables, 10 AND gates and 4 OR gates shown in figure How
would it be programmed to implement the logic circuit for 8421 code to cyclic code
converter?

Solution:
Logic circuit for 8421 code to cyclic code has been implemented using AND, OR
and NOT gates. The Boolean expressions for four variables X, Y, Z, and W of cyclic code
given in terms of a, b, c and d variables of 8421 code are reproduced below as:

X=a+b.d+b.c
Y = b . c̅
Z=b+c
W = a̅ . b̅ . c̅ .d + b̅ . c . d̅ + b. c . d + a . d̅

These expressions are realized using FPLA as shown in below figure

71 | P a g e
Programmable Array Logic (PAL):
Another class of Programmable logic devices is the programmable array logic
(PAL) which is widely used and easily programmable. The PAL has an AND array followed by
OR array similar to FPLA, with the difference that the inputs to AND array are programmable
while the inputs to OR gates are hard wired (fixed OR array). Figure 6.47 shows the architecture
of a PAL device having 16 AND gates and four OR gates. Every AND gate can be programmed
to generate any desired product of 6 input variables and their complements. Each OR gate is
hard wire to only four AND outputs. This limits each output function to four min-terms. If the
function requires more than four product terms then one has to use such a PAL which has more
OR inputs. If on the other hand one needs less than four product terms, the unneeded terms to
the input of OR gate are made 0 by not burning (or programming) the corresponding input lines
of AND gates. The PAL structure is the most generic one for the implementation of arbitrary
logic functions.

Example:

Using the PAL shown in figure 6.47, implement the following SOP functions of 4
variables.

Y0 A̅ B̅ C D̅ A̅ B̅ C̅ D AB C̅ D̅ AB C D
Y1 AB̅ C D̅
Y2 A̅ B̅ D C̅
Y3 B̅ C D̅ A̅ B̅ AB C̅ D̅ B C D

72 | P a g e
 Solution:
Below Figure shows the implementation of the given functions using the PAL.

Programmable Read Only Memory (PROM):

Another class of PLDs is programmable read only memory (PROM), in which AND
array is not programmable while OR array is programmable. So connections from input lines to
the AND gates are hard wired, while the connections to the OR gates from the outputs of the
AND array are programmable (each joint is marked with circled cross mark x). If there are N
input variables, then 2N product terms are generated. One AND gate will be used for each
product term, so there will be 2N AND gates or rows. The OR array will be of any number.
Figure shows 16 X 4 PROM. Since 16 = 24, so it will have 4 address or inputs lines and 4 data
outputs. For the programming of OR array, circled cross marks are removed or fused for the
unused product terms and these marks are retained for the used product terms. PROMs find
many applications like the implementation of Boolean functions, code converters and data
storage tables.
Example;

Using 16 X 4 PROM, implement the following functions of 4 variables.

Y0 (A, B, C, D) = Σ (0, 1, 4, 5, 8, 9, 10, 14, 15)
Y1 (A, B, C, D) = Σ (2, 3, 4, 9, 10, 11, 13, 15)
Y2 (A, B, C, D) = Σ (4, 5, 7, 8, 10, 12, 15)
Y3 (A, B, C, D) = Σ (5, 6, 7, 10, 13)

73 | P a g e
Solution:
By making the suitable programming of OR array, the given Boolean functions
are realized using 16 X 4 PROM as shown in figure

74 | P a g e