Computer Architecture

Lecturer: S. Shifran
safrullashifran@gmail.com
+94 768701466
Senior Software QA Engineer (Accel Digital - Australia)
B.Sc in IS & Master in IT ® - University of Colombo
Lesson 03(A) –
Logic Gates
What are Logic Gates?

●Basic building blocks of a digital

circuit
●Data processing on the circuit is
controlled using transistors
●Output depends on the logic gate
and the input
●Input is one of two states – high or
low
●Output is one of two states – high
What are Logic Gates?
●There are three basic types
of logic gate.

●NOT gate
●AND gate
●OR gate
 Inversion (NOT)

A Q

0 1
Logic:
1 0

5
 AND
❖In order for current to flow, both
switches must be closed
○ Logic notation A•B = C
(Sometimes AB = C)

A B C
0 0 0
0 1 0
1 0 0
1 1 1

10
 OR

❖Current flows if either switch is closed

○ Logic notation A + B = C

A B C
0 0 0
7 0 1 1
1 0 1
1 1 1
8
Find the Boolean algebra expression for the
following system.

Simplify and draw the relevant logic circuit and the truth table
for the below given equations.
1. AB+ABC+BC
2. BC+ABD
3. AB+BC+AC 9
4. BC+ABC+B+A
 Properties of AND and OR
● Commutation
o A+B=B+A
o A•B=B•A

Same as

10

Same as
 Commutation Circuit

A•B B•A

11

A+B B+A
 Properties of AND and OR
● Associative Property
❖ A + (B + C) = (A + B) + C

=
❖ A • (B • C) = (A • B) • C

12
 Properties of AND and OR

Distributive Property
A + B • C = (A + B) • (A + C)
A+B•C

A B C Q
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
13
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
 Distributive Property

(A + B) • (A + C)

A B C Q
0 0 0 0
0 0 1 0
0 1 0 0

14
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
 Exclusive OR (XOR)

Either A or B, but not both

A B S
This is sometimes called the
inequality detector, because the 0 0 0
result will be 0 when the inputs are the 1 0 1
15 same and 1 when they are different.
0 1 1
The truth table is the same as for
1 1 0
S on Binary Addition. S = A  B
 Getting the XOR

Two ways of getting S = 1 A B S

0 0 0
1 0 1
0 1 1
1 1 0
16
 Circuit for XOR

17

Accumulating our results: Binary addition is the

result of XOR plus AND
Binary Counting
Use 1 for ON
Use 0 for OFF

= 00101011

So our example has 25 + 23 + 21 + 20 = 32 + 8 + 2 + 1 = 43

18
 Counting in Binary

1 1 11 1011 21 10101
2 10 12 1100 22 10110
3 11 13 1101 23 10111
4 100 14 1110 24 11000
5 101 15 1111 25 11001
6 110 16 10000 26 11010

19
7 111 17 10001 27 11011
8 1000 18 10010 28 11100
9 1001 19 10011 29 11101
10 1010 20 10100 30 11110
 NAND (NOT AND)

A B Q
0 0 1
0 1 1
20
1 0 1
1 1 0
 NOR (NOT OR)

A B Q
0 0 1
0 1 0
21
1 0 0
1 1 0
DeMorgan’s Theorem

A NAND gate is equivalent to an inversion followed by an

OR

22

A NOR gate is equivalent to an inversion followed by an AND

DeMorgan Truth Table

A B
0 0 1 1 1 1
0 1 1 1 0 0
1 0 1 1 0 0
1 1 0 0 0 0
NAND NOR 23
 Exclusive NOR

A B Q
0 0 1
24 0 1 0
Equality Detector
1 0 0
1 1 1
 Summary

Summary for all 2-input gates

Inputs Output of each gate

A B AND NAND OR NOR XOR XNOR

0 0 0 1 0 1 0 1

0 1 0 1 1 0 1 0
25
1 0 0 1 1 0 1 0

1 1 1 0 1 0 0 1
Three input OR

26
Logic Gates and Symbols

AND

27
NAND
More Gates and Symbols

OR

NOR
28

NOT
And More

XOR

29
NXOR
 Integrated Circuits (ICs)
● An Integrated Circuit is a small silicon semiconductor
crystal(chip), containing the electronic components for
digital gates.

● Various gates are interconnected inside the chip to form the

required circuits.

● Chip is mounted in a ceramic or plastic container and

connections are welded by thin gold wires to the external
pins to form the integrated circuit.
Combinational Logic
▪ Also called combinatorial logic
▪ A type of logic circuit whose output is a
function of the present input only
 Half Adder
▪ Finds the sum of two bits

▪ The sum can be found

using the XOR operation
and the carry using the
AND operation
Full Adder
▪ We can change our half adder into to a full adder
by including gates for processing the carry bit
▪ The truth table for a full adder is:
Converting a Half Adder into a Full
Adder
Ripple-carry Adder (I)
▪ Just as we combined half adders to make a full
adder, full adders can be connected in series
⮚ The carry bit “ripples” from one adder to the next;
hence, this configuration is called a ripple-carry adder

O15 O1 O0
 Decoder
▪ Selects a memory location according a binary value
placed on the address lines of a memory bus
▪ Decoders with n inputs can select any of 2n locations
2-to-4 Decoder

If x = 0 and y = 1,
which output line
is enabled?
4-to-1 Multiplexer

If S0 = 1 and S1 = 0,
which input is
selected as output?
Sequential Logic – Memory
 Sequential Logic Circuits
▪ Combinational logic circuits are perfect for situations
which require the immediate application of a Boolean
function to a set of inputs
▪ But, here are times when we need a circuit to change
its value with consideration to its current state as well
as its inputs
⮚ These circuits have to “remember” their current state
▪ Sequential logic circuits provide this functionality
 Sequencing Events
▪ Sequential logic circuits require a means by which
events can be sequenced
⮚ State changes are controlled by clocks
> A “clock” is a special circuit that sends electrical pulses
through a circuit
⮚ Clocks produce electrical waveforms such as this one

⮚ State changes occur in sequential circuits only when

the clock ticks
 Feedback in Sequential Logic Circuits
▪ Sequential circuits rely on feedback to retain their
state values
▪ Feedback in digital circuits occurs when an output is
looped back to the input
⮚ Example,

If Q is 0 it will always be 0, if it is 1, it will always be 1

 SR Flip-flop (Set-Reset) (I)

• The behavior of an SR
flip-flop is described by
a characteristic table
– Q(t) output at time t
– Q(t+1) output after the
next clock pulse
SR Flip-flop: Block Diagram
S and R Q andQ =
Flip-flops are often input output
drawn like this in
block diagrams S Q
CK

CK is read/write (“clock” R Q
because this input is
connected to the computer’s
processor clock)
SR Flip-flop (II)
▪ The SR flip-flop has three inputs: S, R and Q(t)
⮚ When both S and R are 1, the SR flip-flop is unstable