Unit I Part two DIGITAL LOGIC

I) Logic gates:

Apart from the arithmetic operations, there are logical operations involved in the processing. The logical operations
involve some elements. These elements are NOT, OR and AND. NOT is the opposite of negation or inversion.
Negation of True is False. OR is another logical element which represents either – or. AND is another logical element
which represents two together.
So following are the basic logical elements: AND , OR, NOT
In 1854 George Boole invented symbolic logic. This is known today as Boolean algebra. Each variable in Boolean
algebra has either of two values. - True or False. The purpose of this two-state algebra was to solve logic problems.
As we saw before the computers think in terms of binary (high or low) it is appropriate to say logic is the core of
computers. To implement this logic circuits are used. In the logic circuits Gates are used. A Gate is a small circuit
with one or more input signals but only one output signal. Gates are digital circuits (two-state).
There are several gates such as OR, AND, Inverter, etc. Each has symbol to represent them. Let us see them one by
one.
AND Gates
The AND Gate has two or more input signals but only one output signal. All the inputs must be high to get a high
output. If we have two inputs to this AND gate and both the inputs are high then the output will be high otherwise
the output will be low. All the possible inputs and outputs are shown in the following table.

Truth Table

A B Y
0 0 0
0 1 0 A Y=A.B
1 0 0 Y
B
1 1 1
AND Gate symbol
AND function

OR Gates
The OR gates has two or more input signals but only one output signal. If any input signal is high, the output signal is
high. If we have two inputs to this OR gate and any of the two inputs is high then the output will be high. This can be
shown in a table below with all the possible inputs and corresponding outputs.
Truth Table

A B Y
A
0 0 0 Y=A+B
0 1 1 B Y
1 0 1 b
1 1 1 b
OR Gate symbol OR
function
NOT or Inverter:
A Low input produces a high output, and a high input produces low output. In binary format if the input is 0 the
output will be 1 and if the input is 1 then the output will be 0. The table shows the input and output possibilities.
Input Output
0 1 Y=A
1 0
NOT Gate symbol NOT function

Unit III Digital Logic Page 1

 NAND Gate
NAND Gate is a combination of an AND gate with an inverter. An AND Gate followed by an inverter.

A A
B Y B Y

Whatever the output of the AND gate, it will be inverted by the inverter. This is the formation of NAND gate. The
sign and the table is shown below. The NAND operation is called Universal Operation or gate.

Y = AB
A B Y
NAND Sign 0 0 1
0 1 1
1 0 1
1 1 0

NOR Gate
NOR Gate is a combination of an OR gate with an inverter. An NOR Gate followed by an inverter.
The NOR operation is also a Universal Operation or Gate.
A
Y
B

Y = A+B
A B Y
NOR Sign 0 0 1
0 1 0
1 0 0
1 1 0

Exclusive OR Gate
An OR Gate recognizes with one or more 1s as inputs and gives output as 1. The Exclusive-OR is different; it
recognizes only that have odd number of 1s. The following table shows different inputs and outputs.

A B Y (Output)
Y= A XOR B 0 0 0
Y= A B 0 1 1
Ex-OR sign 1 0 1
1 1 0

XOR GATE Input Output

Y Y=A B+A B
B

Unit III Digital Logic Page 2

 A
B Y

Exclusive NOR Gate or XNOR

Exclusive NOR Gate is abbreviated as XNOR. This is logically equivalent to and XOR gate followed by an inverter.
Following figure shows the XNOR gate and the table of input and outputs.

A A
B Y B Y

Y= A ENOR B A B Y
Y= A B 0 0 1
Ex-NOR sign 0 1 0
1 0 0
1 1 1

LIST OF LOGIC GATE ICS

There are different Integrated Circuit (IC) technologies are used to implement the basic logic gates
ICs

CMOS TTL ECL

They are CMOS (Complementary Metal – Oxide Semiconductor), TTL (Transistor – Transistor Logic) and ECL (Emitter –
Coupled Logic).

II) Flip flops:

The flip flop is a bistable device. It exists in one of two states and, in the absence of input, remains in that state. Thus,
the flip flop can function as a 1 bit memory.

The flip flop has two outputs, which are always the complementary of each other, these are generally labelled Q and Q

The S-R Flip flop:

The circuits has two inputs, s(Set) and R (Reset) and two outputs Q and Q and consists of two NOR gates connected in a
feedback arrangement.

First, Let us show that the circuit is bistable. Assume that both S and R are 0 and that Q is 0. The inputs to the lower NOR
gate are Q = 0 and S = 0. Thus, the output Q = 1 means that the inputs to the upper NOR gate are Q=1 and R=0, which
has the output Q = 0.

Unit III Digital Logic Page 3

 Thus, the state of the circuit is internally consistent and remains stable as long as S = R = 0. A similar line of reasoning
shows that the state Q = 1, Q = 0 is also stable for R = S = 0.

Thus, this circuit can function as a 1-bit memory. Suppose that S changes to the value 1. Now the inputs to the lower
NOR gate are S =1 , Q =0. After some time delay t, the output of the lower NOR gate will be Q = 0.

R characteristic Table
Q

S R Qn+1

0 1 Qn

0 1 0

1 0 1

S Q 1 1 --

So, at this point in time, the inputs to the upper NOR gate become R=0 , Q = 0. After another gate delay of t, the output Q
becomes 1. This is again a stable state. The inputs to the lower gate are now S = 1, Q =1, which maintain the output Q=0.
As long as S =1 and R =0, the outputs will remain Q =1, Q = 0. Furthermore, if S returns to 0, the outputs will remain
unchanged.
Observe that the inputs S = 1, R =1 are not allowed, because these would produce an inconsistent output ( both Q and Q
equal 0).
Clocked S-R Flip-Flop:
The output of the S-R latch changes, after a brief time delay, in response to a change in the input. This is referred to as
asynchronous operation. More typically, events in the digital computer are synchronized to a clock pulse, so that changes
occur only when a clock pulse occurs. This type of device is referred to as a clocked S-R flip-flop. Note that the R and S
inputs are passed to the NOR gates only during the clock pulse.
R

Clock

D Flip – Flop:
One problem with S-R flip flop is that the condition R = 1, S = 1 must be avoided. One way to do this is to allow just a
single input. The D flip flop accomplishes this. By using an inverter, the two AND gates are guaranteed to be the
opposite of each other.
The D flip flop is sometimes referred to as the data flip flop because it is, in effect, storage for one bit of data. the output
of the D flip flop is always equal to the most recent value applied to the input. Hence, it remembers and produces the
last input. It is also referred to as the delay flip flop, because it delays a 0 or 1 applied to its input for a single clock pulse.

D Qn+1 clk
0 0

Unit III Digital Logic Page 4

 1 1
Q
D

J-K Flip-Flop:
Like the S-R flip flop, it has 2 inputs. However, in this case all possible combinations of input values are valid. In its
characteristic table, we can note that the first three combinations are the same as for the S-R flip-flop. With no input,
the output is stable. The J input alone performs a set function, causing the output to be 1; the K input alone performs a
reset function, causing the output to be 0. When both J and K are 1, the function performed is referred to as the toggle
function: the output is reversed.
Characteristic Table:

K J K Qn+1
Q
0 1 Qn

Clock 0 1 0

1 0 1
Q
1 1 Qn
J

iii) Latches
A flip flop in its simplest form is called a latch. A latch stores a binary bit 1 or 0. The unclocked simple flip-flops and D flip
flops fall under the category of latches. An n-bit latch consists of n-number single bit latches. It stores a binary word of n
bits. The n-bits of the binary word are transferred to the latch simultaneously in parallel. In a latch there is no facility to
read its contents. The latches are temporary storage devices. They are ideally suited for storing information between
processing units and I/O units or indicator units. The examples of latch ICs are:
74100 – 8 bit bistable latches
74259 – 8 bit addressable latches
7477 – 4 bit bistable latches

iv) Registers
A register is a digital circuit used within the CPU to store one or more bits of data. Two basic types of registers are
commonly used: Parallel registers and shift registers.

Parallel Registers:
A parallel register consists of a set of 1-bit memories that can be read or written simultaneously. It is used to store data.
The 8 bit register of figure illustrates the operation of a parallel register using D flip flops. A control signal, labelled load,
controls writing into the register from signal lines, D11 through D18. These lines might be the output of multiplexers, so
that data from a variety of sources can be loaded into the register.
Data Lines

D18 D17 D16 D15 D14 D13 D12 D11

D Q D Q D Q D Q D Q D Q D Q D Q

CLK CLK CLK CLK CLK CLK CLK CLK

CLk ----
Load---

Unit III Digital Logic Page 5

 D08 D07 D06 D05 D04 D03 D02 D01

Output Lines
--8-bit Parallel Register--
Shift Registers:
A Shift register accepts and / or transfers information serially. Consider, for example, the figure, which shows a 5-bit
shift register constructed from clocked D flip-flops. Data are input only to the leftmost flip-flop. With each clock pulse,
data are shifted to the right one position, and the rightmost bit is transferred out.

Serial In D Q Serial Out

D Q D Q D Q D Q

CLK CLK CLK CLK CLK

Clock
--5-bit Shift Register--
Shift registers can be used to interface to serial I/O devices. In addition, they can be used within the ALU to
perform logical shift and rotate functions.

v) Buffers/Drivers and counters

The function of a buffer/driver is to increase the output current/voltage ratings. When the output current of a digital
device is insufficient to drive another device which is to be connected to the output terminal of the device, a buffer is
employed to amplify the current. A buffer is a current amplifier. For an inverting buffer a bubble is placed at the output
point of triangle. Sometimes, an increased voltage is required to drive relays, lamps etc., the device is said to be a buffer
only when the manufacturers optimize the design for high current output.
For example, IC 7426 is a quad 2-input NAND buffer. Its NAND gates are optimized for high current output.

INPUT OUTPUT INPUT OUTPUT

-buffer- - Inverter buffer -

Counters:
A counter is a register whose value is easily incremented by 1 modulo the capacity of the register. Thus, a register made
up of n flip flops can count up to 2 n-1. When the counter is incremented beyond its maximum value, it is set to 0. An
example of a counter in the CPU is the program counter.
Counters can be designated as asynchronous or synchronous, depending on the way in which they operate.
Asynchronous counters are relatively slow because the output of one flip flop triggers a change in the status of the next
flip flop.
In synchronous counter, all of the flip flops change state at the same time. This type is much faster, it is the kind used in
CPUs.
Ripple Counter:
An asynchronous counter is also referred to as a ripple counter, because the change that occurs to increment the
counter starts at one end and ripples through to the other end.

High

J Q J Q J Q J Q
Clock CLK CLK CLK CLK

K Q K Q K Q K Q

Unit III Digital Logic Page 6

 Q0 Q1 Q2 Q3

---Sequential Circuit----

In the illustrated implementation, the counter is incremented with each clock pulse. The J and K inputs to each flip flop
are held at a constant 1. This means that, when there is a clock pulse, the output at Q will be inverted ( 1 to 0; 0 to 1).
Note that the change in state is shown as occurring with the falling edge of the clock pulse; this is known as an edge-
triggered flip flop. If one looks at patterns of output for this counter, it can be seen that it cycles through 0000,
0001, ......1110,1111,0000 and so on.

Synchronous counters: the ripple counter has the disadvantage of the delay involved in changing value. To overcome
this disadvantage, CPUs make use of synchronous counters, in which all of the flip-flops of the counter change at the
same time.

High
J C J B J A

CLK CLK CLK

K C K B K A

Clock
--Design of a Synchronous counter--

For a 3 bit counter, three flip flops will be needed. Let us use JK flipflops. Label the uncomplemented output of the three
flip flops A, B,C respectively, with C representing the lease significant bit.

vi) Digital Multiplexers/Data selectors

A digital multiplexer has N inputs and only one output. By applying control signals anyone input can be made available
at the output terminal. It is also called data selector. The control signals are applied to the select lines to select the
desired input.
Examples :
IC 74150 – 1 of 16 Data selectors /Multiplexers
IC 74152 – 1 of 8 Data selectors/Multiplexers

D0
DIGITAL
D1
MULTIPLEXER
INPUT D2 OUTPUT SIGNAL
SIGNALS .
.
DN

SELECT LINES
FIG: DIGITAL MULTIPLEXER
vii) Digital Demultiplexers/Decoders
A digital demultiplexer has 1 input and N outputs. The meaning of demultiplexer is one into many. By applying control
signals the input signal can be made available at anyone of output terminals. It performs reverse operation of a
multiplexer.

Unit III Digital Logic Page 7

 Example : IC 74154 is a 1 to 16 demultiplexer/4 to 16 decoder.

D0
DIGITAL
D1
DEMULTIPLEXER
INPUT D2 OUTPUT SIGNAL
SIGNALS .
.
DN

SELECT LINES
FIG: DIGITAL DEMULTIPLEXER

viii) Boolean Algebra

Boolean Algebra is mathematical system for formulating logical statements with symbols so that problems can be solved
in a manner to ordinary algebra.
Boolean algebra is the mathematics of digital systems
A basic knowledge in the Boolean algebra required to study and analysis of logic circuits.
It is a convenient and systematic way of expressing and analyzing the operations of logic circuits.

Rule Number Boolean Expression

1 A+0=A
2 A+1=1
3 A.0=0
4 A.1 =A
5 A+A=A
6 A+Ā=1
7 A .A = A
8 A . Ā =0
9
Ā=A
10 A + AB =A
11 A +AB = A + B
12 (A + B) (A + C) = A + BC

Commutative Law : A+B=B+A AB = BA

Associative Law : A+(B+C) = (A+B)+C A(BC) = (AB)C
Distributive law: A(B+C) = AB + AC A +(BC) = (A+B). (A+C)
De morgan’s Theorems : A + B = A . B A.B = A + B

ix) Karnaugh Map Method

The Karnaugh map method is a graphical technique for simplifying Boolean functions. It is a two-dimensional of a Truth
Table. It provides a simpler method for minimizing logic expressions. The map method is ideally suited for four or less
variables.
A Karnaugh map for n variables is made up of 2 n squares. Each square designates a product term of a Boolean
expression. For product terms which are present in the expression, 1s are written in the corresponding squares; 0s are
written in those squares which correspond to product terms not present in the expression.

Unit III Digital Logic Page 8

 Consider a map of two variables:

A A A 0 1
B

B 0 A B AB

1 A B AB
B

In the map, 0 represents A , and 1 represents A. Similarly, for variable B.

For example, for the Boolean functions Y = A B + AB

0 1

1
0

1
1

Example : simplify Y= A B + AB

0 1

0 1 1 B

Two adjacent squares containing 1 have been grouped together. To show the grouping, they have been encircled. For
simplification we have to see that which variable is common to both squares. In this case B is common to both as the
1st row is for B .
So their simplification will result Y = B
This can be verified also algebraically as follows:
Y= A B + A B

= B ( A + A)
=
B

So the variable which is common to adjacent squares is selected, and the variable which is not common is discarded.

Example : simplify Y= A B + AB + A B
0 1

0 1 1 A

1 1 B
Unit III Digital Logic Page 9
 1

Simplification result Y= A B + AB + AB =B+A

The result obtained by map method can also be verified algebraically as follows:

Y= A B + AB + AB

= A B + AB + AB + AB

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

Karnaugh Map for Three variables:

A B A B A B A B
C
A B C A B C A B C AB C

C A B C A B C ABC A BC

The ordering of the variables, ie., 00,01,11,10 is in gray code.

AB
C 00 01 11 10

0 A B C A B C A B C AB C

1 A B C A B C ABC A BC

Example: simplifying the function Y = AB C + ABC

AB
C 00 01 11 10

0 1 AB

1 1

The simplified function will be Y = AB

Example: simplifying the function Y = A B C + A B C + A B C

Unit III Digital Logic Page 10

 AB
C 00 01 11 10

0 1 1 AC

1 1 A B

Unit III Digital Logic Page 11

 The simplified function will be Y = A B + A C

x) Combinational and Sequential circuits

There are two types of logic circuits – combinational and sequential. A combinational circuit is one in which the state of
the output at any instant is entirely determined by the states of the inputs at that time.
Combinational circuits are those logic circuits whose operations can be completely described by a truth table / Boolean
expression. A combinational circuit is realized using AND, OR, NOT gates (or NAND OR NOR gates).
Examples of combinational circuits are: adder, subtractors, code converters, decoders, encoders, digital multiplexers,
demultiplexers, programmable logic arrays, ROMs etc.,
A sequential circuit consists of a combinational logic and storage elements. The output of a sequential circuit is not only a
function of a present inputs but also of past inputs. The state of the storage elements depends upon the preceding inputs
and the preceding states of the elements. Therefore, the output of a sequential circuit becomes a function of both the
present inputs and the present internal states of the sequential circuit. To realize sequential circuits in addition to AND,
OR and NOT gates, flip-flops are also required.
Examples of sequential circuits are: registers, shift registers, counters, etc.,
The two major uses of sequential circuits in digital systems are:
1) As memories to store information while processing
2) As control circuits to generate control signals which are essential to select and enable a sequence of data
transfer or data processing steps in the execution of multistep tasks.
The sequential circuits which employ clock are called synchronous sequential circuits. In a synchronous sequential circuit
all memory elements are clocked latches or clocked flip flops. The design and operation of sequential circuits is greatly
simplified by the use of clock signals.
The sequential circuits which do not employ clock are known as unclocked or asynchronous sequential circuits.
Unclocked sequential circuits are difficult to design and therefore, they are relatively uncommon.

xi) Arithmetic Circuits

Arithmetic operations, such as addition, subtraction, multiplication, division etc., are performed by a digital computer,
calculator or other digital system. Logic circuits for some important arithmetic operations are half-adder and full adder.

HALF ADDER:
A logic circuit which performs addition of two binary bits is called a half-adder.
Truth table for the addition of two binary bits.

Inputs Outputs
A B Sum S Carry C
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

It is concluded that the sum is equal to A XOR B. It means that the outputs of an EXCLUSIVE-OR gate will give the sum. The
carry is equal to A AND B. The output of an AND gate will give the carry.

S= A B + A B
A Sum
=A B Sum
S S
HALF
C=AB B S A
ADDER

Unit III Digital Logic Page 12

 Carry
B
C
Carry
C

Full Adder

A logic circuit which performs addition of three binary bits is called a Full-adder.
A full adder can be built using two half adders and an OR gate.

Inputs Outputs
A B C Sum S Carry C
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

A Carry
HALF
ADDER Carry

B Sum A
Y
HALF Carry
ADDER
Sum

--Full Adder—

---------

Unit III Digital Logic Page 13