Review of Digital Design

Fundamentals



Bit: A binary digit; can have a value of 0 or 1


Logic gate: A digital circuit that manipulates bits. A logic gate
takes one or more bits as input(s) and generates one bit as the
output.

A logic gate can be represented pictorially by its logic symbol.
The function performed by a logic gate can also be expressed
algebraically, or in terms of a Truth Table.

Logic diagram: A diagram showing an interconnection of logic
symbols.

Truth table
Truth table: The truth table gives the input-output
relation of a logic gate or logic circuit in tabular
form.
It specifies the output bit(s) for each possible input
bit combination.
A circuit with n binary inputs has 2
n
different input
combinations.
A binary value of 0 is sometimes referred to as L
(low) or F (false).
A binary value of 1 is sometimes referred to as H
(high) or T (true).

Minterm
Minterm: One specific combination of input
bits, out of the 2
n
different input
combinations.
A truth table of n binary inputs has 2
n

minterms and an output is specified for each
minterm.

Logic Gates
Logic Symbols:

1
0
0
1
out A
1 1 1
0 1 0
0 0 1
0 0 0
Out A B
Logic Gates
1 1 1
1 1 0
1 0 1
0 0 0
Out A B
0 1 1
1 1 0
1 0 1
0 0 0
Out A B
Logic Gates
0 1 1
1 1 0
1 0 1
1 0 0
Out A B
0 1 1
0 1 0
0 0 1
1 0 0
Out A B
Logic Gates
1 1 1
0 0 1
0 1 0
1 0 0
Out B A
Digital Circuit Representation
The truth table, logic diagram and algebraic expression are
three different ways of representing a digital circuit and given
one form the other representations of the circuit can be
derived.

The truth table representation of a Boolean function is unique,
but the same function may have more than one logic or
algebraic representation.

EXAMPLE: Given the following logic diagram, obtain the
corresponding truth table and algebraic expression.
Digital Circuit Representation
0 1 1 1
0 1 1 0
1 1 0 1
0 1 0 0
0 0 1 1
0 0 1 0
1 0 0 1
1 0 0 0
Out A B C
Basic Identities of Boolean algebra

K-Map
The complexity of a digital circuit depends on
the complexity of the corresponding algebraic
expression.
The karnaugh map (k-map) provides a simple
straightforward procedure for simplifying
Boolean expressions and thereby obtaining
simpler digital circuits.
K-Map
A diagram made up of squares, where each
square represents a minterm.
The output (0 or 1) for a specific minterm is
inserted in the corresponding square in the k-
map.
A function with n variables has a kmap with
2
n
squares.
Properties of k-maps
Each row (or column) in the k-map is labelled
by one or more bits, representing the values of
the corresponding variables for that row (or
column).
The minterm corresponding to a particular
square in the k-map (belonging to the i
th

column and j
th
row) is obtained by taking the
values of the variables associated with the i
th

column and j
th
row.

00 01 11 10
0

1
AB
C
00 01 11 10
00

01

11

10
AB
CD
For example the shaded squares in figure 1 (a) and (b) correspond to minterms
111 and 0110 respectively.
Rules for simplifying k-maps
1. Plot a Boolean function on to a k-map by inserting
1s in those squares where the corresponding
minterm has an output of 1.

2. Combine adjacent 1s into groups such that:
i) a group contains only 1s
ii) the number of squares in a group is a power of 2
iii) the group is not part of a single larger group




Rules for simplifying k-maps
3.Keep choosing additional groups until all the
1s in the k-map are covered i.e. each 1 is part
of at least one group. Choose the groups in
such a way that the total number of groups
needed to cover all the 1s is minimized.
4.Obtain an algebraic product term for each
group.
5.Obtain the final solution by a logical OR of all
the terms from step 4.
Some definitions:
Implicant: A group of 2
k
adjacent 1s in a k-
map.
Prime Implicant (PI): An implicant which is
not completely covered by a single larger
implicant.
Essential Prime Implicant: A prime implicant
where at least one minterm is not covered by
any other prime implicant.
Examples
A B C F
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0
1
0
0
0
0
1
1
1
00 01 11 10
0
1
AB
C
A`B`
F=A`C`+B`C
Essential PI
Non-Essential PI
Example
A B C D F
0 0 0 0 0
0 0 0 1 0
0 0 1 0 1
0 0 1 1 0
0 1 0 0 1
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 0
1 1 1 1 1
1
1
1
1
0
1
1
1
1
0
0
1
0
0
0
00 01 11 10
00

01


11

10
AB
CD
F=AD+AB`+BC`D`+A`CD`
OR
F=AD+ AC`+ A`BD`+B`CD`
Non-Essential PI
Essential PI
1

Dont Cares
A truth table can be expressed in compact form by simply
specifying the minterms for which the output is 1.
For some functions, there may be certain input conditions for
which we dont care what output is. This situation is
represented by putting a d in the output for the
corresponding minterms.
Dont care outputs may be treated as either a 0 or a 1, in order
to obtain a minimized circuit.
All minterms which are not in the given list(s) are assumed
to have an output of 0.

Function with Dont cares


a) F has three inputs A,B, and C.
b) The outputs corresponding to minterms 0,2,6
are 1.
c) The outputs corresponding to minters 1,3,5 are
dont cares
d) The outputs for all remaining minterms (4 and 7)
are 0.
Examples:
Obtain a minimized SOP expression for the
following functions. Also, list all the prime
implicants and indicate which ones are
essential.

1 1 1 0
d d 0 d
F
00 01 11 10
AB
C
0
1
F= A+BC
Prime Implicants
A(essential)
BC(essential)
00 01 11 10
00

01

11

10
CD
AB
Prime Implicants

BCD(Essential)
ABC(Essential)
BD
ABC
ACD
F = BD + BCD + ABC
0 0 0 1
d 0 0 d
d 0
d
1
0 1 1 0
Product of sums (POS)
A POS expression for a function F can be
obtained by grouping the 0,s in the k-map for
F and then
(i) Obtain a SOP expression for F and
complement it OR
(ii) Directly obtain the POS expression by
examining the selected groups.

1 1 0 1
d 1 0 1
0 d 0 0
1 1 0 1
00 01 11 10
00

01

11

10
CD
AB
Prime Implicants of F
AB (Essential)
CD(Essential)
ABD
F=AB+CD
F=(AB+CD)
F=(AB).(CD)
F=(A+B).(C+D)
Final POS expression
The same final expression can also be obtained by directly examining the groups.
1 0 1 1
1 0 1 1
0 0 1 0
1 0 1 1
00 01 11 10
00

01

11

10
CD
AB
Prime Implicants of F
AB (Essential)
BCD(Essential)
ACD
F=AB+BCD

F=(AB+BCD)
F=(AB).(BCD)
F=(A+B).(B+C+D)
Final POS expression
The same final expression can also be obtained by directly examining the groups.
Multi-output functions

A multi-output function is treated similar to a
single output function,
A separate k-map and Boolean expression
needs to be derived for each of the outputs.
Example: full adder (FA) circuit which has 3
inputs - the 2 bits (A and B) to be added and a
carry in (C
in
) and has 2 outputs a sum (S) and
a carry out to the next stage (C
out
).

Full Adder
A B Cin Cout S
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0 0
0 1
0 1
1 0
0 1
1 0
1 0
1 1
0 1 0 1
1 0 1 0
00 01 11 10
0
1
AB
C
S
0 0 1 0
0 1 1 1
00 01 11 10
0
1
AB
C
Cout
S=ABC + ABC+ABC+ABC
S= A B C
C
out
=AB+BC+AC
Decoder
Converts binary information from n inputs to
upto 2
n
outputs.
If some input combinations are unused, the
number of outputs may be less.
For each input combination, only one output
is active and all other outputs are inactive.
A decoder may also have an enable input (E), as shown below.

Examples: Design a 2-4 decoder (without enable input).
a) Truth Table
A1 A0 D0 D1 D2 D3
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1
b) K-maps
1 0
0 0
0 0
1 0
0 1
0 0
0 0
0 1
D0
D1
D2
D3
0 1
0 1
0 1
0 1
0
1
0
1
0
1
0
1
A1
A0
A0
A0
A0
A1
A1
A1
D0=A1A0
D2=A1A0
D1=A1A0
D3=A1A0
Decoder Expansion:
Smaller decoders can be combined to form a larger one.
Example: Construct a 3-8 decoder using 2-4 decoders.
Multiplexer
A combinational circuit which takes information from one of
2
n
input lines and transfers it to a single output line.
The particular input line chosen is determined by n select
lines.
Example
S I1 I0 F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
Design a 2-to-1 multiplexer with two input lines and one select line
Truth table
k-maps
0 0 1 0
1 1 1 0
0 0 01 1 1 10
0
1
f
I0
S,I1
f = SI1 + SI0
Multiplexer Expansion
Smaller multiplexers can be combined to form a larger one.
Example: Construct a 4-to-1 multiplexer using 2-to-1 multiplexers.
Encoders
An encoder performs the inverse operation of
a decoder.
It has (up to) 2
n
inputs and n outputs.
Each input line is mapped to a specific
combination of output lines.
Only one input line can be high at any given
time.
Example:
I3 I2 I1 I0 A0 A1
0 0 0 1 0 0
0 0 1 0 0 1
0 1 0 0 1 0
1 0 0 0 1 1
A 4-to-2 encoder
Flipflops and Sequential Circuits
Combinational circuits: Digital circuits
where the output depends only on the current
inputs. They consist of a interconnection of
logic gates.

Sequential circuits: Output depends on the
previous output state as well as the current
inputs.
Flipflops and Sequential Circuits
Flipflops: Basic storage element, capable of
storing previous state (0 or 1). A flipflop can
store 1 bit of information and is the basic
building block of sequential circuits.
Flipflops and Sequential Circuits
Edge-triggered flipflop: State changes occur only during a
positive (0 to1) or negative (1 to 0) clock transition. The
corresponding flipflops are called positive or negative edge-
triggered flipflops respectively.

The output (Next State) of a flipflop depends on
Present State and
Current inputs and is described in a characteristics table.

Characteristic table: Specifies the next state, based on present
state and current inputs.
SR-FLIPFLOP

Next
State Q(t+1)
Present
StateQ(t)
Input
SR
0 0 00
Indeterminate 11
1 1 10
1 0 10
0 1 01
0 0 01
1 1 00
JK-FLIPFLOP
0 1 11
1
Next
State Q(t+1)
Present
StateQ(t)
Input
S R
0 0 00
0 11
1 1 10
1 0 10
0 1 01
0 0 01
1 1 00
D-FLIPFLOP
Next
State
Q(t+1)
Present
StateQ(t)
Input
D
0 0 0
1 1 1
1 0 1
0 1 0
T-FLIPFLOP
Next
State Q(t+1)
Present
StateQ(t)
Input
T
0 0 0
0 1 1
1 0 1
1 1 0
Sequential Circuit Analysis
Complete the state table, for the following circuit.

1 1 1 1 1 1 1
1 1 1 1 1 1 0
1 1 1 1 1 0 1
1 0 0 1 1 0 0
1 1 1 1 0 1 1
0 1 1 0 0 1 0
1 0 0 1 0 0 1
0 0 0 0 0 0 0
next state
A B
flipflop inputs
D
A
D
B
present state input
A B X
D
A
= AX +B; D
B
= X + A;

Sequential Circuit Analysis
0 0 1 1 1 1 1
0 0 1 1 1 1 0
1 0 1 1 1 0 1
1 1 0 1 1 0 0
0 1 1 1 0 1 1
1 1 1 0 0 1 0
1 0 0 1 0 0 1
0 0 0 0 0 0 0
next state
A B
flipflop inputs
T
A
T
B
present state input
A B X
(ii) Complete the state table If T-flipflops are used.
. T
A
= AX +B; T
B
= X + A;
SR-FLIPFLOP JK-FLIPFLOP
Inputs
S R
Next
state
Q(t+1)
Present
State
Q(t)
0
1
0
d
d
0
1
0
1
0
1
0
1
1
0
0
Inputs
J K
Next state
Q(t+1)
Present
State
Q(t)
0
1
d
d
d
d
1
0
1
0
1
0
1
1
0
0
Excitation Tables
D-FLIPFLOP T-FLIPFLOP
1
Inputs
D
Next
state
Q(t+1)
Present
State
Q(t)
0
1
0
1
0
1
0
1
1
0
0
Inputs
T
Next state
Q(t+1)
Present
State
Q(t)
0
1
1
0
1
0
1
0
1
1
0
0
Excitation Tables
Sequential Circuit Design
The excitation tables give the required inputs to the flipflop
for a specific change of state. The steps to be followed in the
design of sequential circuits are as follows:

1. Draw the state diagram from the problem specification
2. Choose the type of flipflop to be used.
3. Fill in the excitation table of the circuit using the selected flipflops.
4. Obtain k-maps for each flipflop input.
5. Simplify the k-maps to obtain Boolean expressions for each flipflop input.
6. Draw the logic diagram of the circuit (if required).
Design a sequential circuit going through the following sequence of states: 0 -> 1 -
> 3 -> 5 -> 6 -> 2 -> 7 -> 4 -> 0
010
011 001
111 110
000
101 100
(a) Draw the state diagram of the circuit.
Example
Excitation Table
1 1 0 0 0 1 1 1 1
0 0 1 0 1 0 1 1 0
1 1 0 0 1 1 1 0 1
0 0 1 0 0 0 1 0 0
0 1 1 1 0 1 0 1 1
1 0 1 1 1 1 0 1 0
0 1 0 1 1 0 0 0 1
1 0 0 1 0 0 0 0 0
FlipFlop inputs
T
A
T
B
T
C
Next State
A B C
Present state
A B C
K-Map
0 0 1 0
1 1 1 0
00 01 11 10
0

1
AB
C
T
A
T
A
=AB + AC
T
B
1 1 1 1
0 0 0 0
00 01 11 10
AB
0
1
C
T
B
= C
1
0
1
0
0
1
0
1
00 01 11 10
0
1
AB
C
T
C
T
C
=AC+AC
1 1 0 0 0 1 1 1 1
0 0 1 0 1 0 1 1 0
1 1 0 0 1 1 1 0 1
0 0 1 0 0 0 1 0 0
0 1 1 1 0 1 0 1 1
1 0 1 1 1 1 0 1 0
0 1 0 1 1 0 0 0 1
1 0 0 1 0 0 0 0 0
FlipFlop inputs
T
A
T
B
T
C
Next State
A B C
Present state
A B C
More examples of sequential circuit synthesis.
Design a two bit
sequential circuit
with an external
input x, such that
the circuit counts
up when x=0 and
counts down when
x=1. Use D
flipflops.
a) Draw state
diagram
00
X=0
X=1
X=1
X=1
X=1
X=0
X=0
X=0
00 01
11 10
Excitation Table
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
Present
state

A B x
Next State

A B
FlipFlop Inputs

DA DB
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 0 0
1 0 0 1 1
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1
00
X=0
X
=
1
X=1
X=1
X=1
X=0
X=0
X=0
00 01
11 10
K-maps
0 1 0 1
1 0 1 0
AB
x
DA
00 01 11 10
0
1
1 0 0 1
1 0 0 1
00 01 11 10
0
1
AB
DB
x
DA= ABx+ ABx+ABx+ABx
DB= B
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
Present
state

A B x
Next
State

A B
FlipFlop
Inputs

DA DB
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 0 0
1 0 0 1 1
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1
Draw the logic diagram.
2. Design a sequential circuit, using T flipflops, that has the following
state diagram
1/0
0/0
1/0
0/0
0/1
1/0
1/0
0/0
A B
D
C
A = 00
B = 01
C = 10
D = 11
Fill in the excitation table corresponding to the above sequential
circuit, using T flipflops.
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
Present State

Q1 Q2 X
Next State

Q1 Q2
FlipFlop Inputs

T1 T2
Output
0 0 0 0 0 0
0 0 1 0 0 0
0 1 0 1 1 0
0 1 1 0 0 0
1 0 0 0 1 0
1 0 1 1 0 0
1 1 0 0 1 1
1 1 1 0 1 0
1/0
0/0
1/0
0/0
0/1
1/0
1/0
0/0
A B
D
C
Fill in the K-maps and obtain a Boolean expression for each flipflop
input.
0 1 1 1
0 0 1 0
Q1Q2
x
T1
00 01 11 10
0
1
0 1 1 0
1 0 0 1
00 01 11 10
0
1
T2
x
T1= Q1Q2 + Q1x + Q2x
T2= Q2x + Q2x
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
Present
State

Q1 Q2 X
Next
State

Q1
Q2
FlipFlop
Inputs

T1 T2
Output
0 0 0 0 0 0
0 0 1 0 0 0
0 1 0 1 1 0
0 1 1 0 0 0
1 0 0 0 1 0
1 0 1 1 0 0
1 1 0 0 1 1
1 1 1 0 1 0
Draw the logic diagram.
Registers
A group of flipflops, where each flipflop stores 1 bit of
information.
A n-bit register consists of n flipflops and can store any
binary information of n bits.
May have combinational circuits associated with each
flipflop, for simple data processing operations such as
LOAD, INR, INV etc.
The flipflops hold binary information and the combinational
circuits control how and when new information is transferred
to the register.
Registers
Figure 1 shows a simple 4-bit register with parallel load. A positive clock
transition will load all 4 values I3 - I0 into the register.
In a digital system a clock generator supplies a
continuous set of clock pulses.
A separate control signal (LOAD) is required to
determine which clock pulse affects the data in a
register.
When LOAD = 1, a new value is loaded into the
register.
When LOAD = 0, the contents of the register
remains unchanged.
Shift Registers
A register capable of shifting binary information in
one or both directions.
It consists of a chain of flipflops in cascade, with the
output of one stage connected to the input of the next
stage.
All flipflops receive a common clock pulse.
A shift register that can shift in both directions is
called a bidirectional shift register.
Shift registers

Counters
A register that can go through a
predetermined sequence of states upon the
application of input pulses is called a counter.
Counters are widely used in digital systems
for counting number of occurrences of events,
generating timing and control information etc.
Binary Counters
A binary counter is one which follows a
simple binary sequence.
A n-bit binary counter can count from 0 to 2
n

- 1.
A down counter counts in the reverse order.
Capacity of Memory
Total number of bytes that can be stored in the
memory.
Capacity = no. of words X no. of bytes per
word.
Address lines are used to select one particular
word in memory.
A memory with 2
k
locations requires k
address lines.
Examples
(i) How many address and data lines
*
are needed for a 64k X
8 bit memory.
64k = 2
6
X 2
10
= 2
16
.
So, 16 address lines are needed.
wordlength = 8 bits. So, 8 data lines are needed.
(ii) How many address and data lines are needed for a 16M X
4 byte memory.
16M = 2
4
X 2
20
= 2
24
.
So, 24 address lines are needed.
wordlength = 4 bytes = 32 bits. So, 32 data lines are needed


*
Assume the entire word is accessed as a unit.
Random Access Memory (RAM)
Memory cells from any location can be
accessed directly.
Process of locating a word in memory is the
same and takes the same amount of time for
each location.
RAM is capable of both READ and WRITE
operations.
Steps for accessing a memory location
in a RAM
1) Apply address to address lines
2) Apply data bits to input data lines (for
WRITE operation only)
3) Activate READ/WRITE control line
4) Read data from data output lines (for
READ operation only)