Computer System Architecture

DR. Howida Youssry

 Digital Computers

Computer Hardware(H/W)
CPU
Memory
Program Memory(ROM)
Memory
Data Memory(RAM)
I/O Device
Input Device: Keyboard, Mouse,
Scanner CPU
Output Device: Printer, Plotter, (control unit &
Display arithmetic unit)
Storage Device(I/O): FDD, HDD,
MOD
Input Interface Output
Device or IOP Device

Figure 1-1 Block Diagram of a digital Computer

 Logic Gates

ADC(Analog to Digital Conversion)

0 : 0.5v
Signal Physical Quantity Binary Information
V, A, F, 거리 Discrete Value 1 : 3v

Gate
The manipulation of binary information is done by logic circuit called
“gate”.
Blocks of H/W that produce signals of binary 1 or 0 when input logic
requirements are satisfied.
Digital Logic Gates : Fig. 1-2
AND, OR, INVERTER, BUFFER, NAND, NOR, XOR, XNOR

x xy x xy x
x
y y
 Name
COMBINATIONAL
Symbol Function Truth Table
GATES
A B X
A X=A•B 0 0 0
AND X or 0 1 0
1 0 0
B X = AB 1 1 1
A A B X
OR X X=A+B 0 0 0
0 1 1
B 1 0 1
1 1 1
A X
I A X X=A 0 1
1 0
A X
Buffer A X X=A 0 0
1 1
A B X
A 0 0 1
NAND X X = (AB)’
0 1 1
1 0 1
B 1 1 0
A B X
A 0 0 1
NOR X X = (A + B)’ 0 1 0
1 0 0
B 1 1 0
A B X
XOR A X=AB 0 0 0
Exclusive OR X or 0 1 1
B X = A’B + AB’ 1 0 1
1 1 0
A B X
XNOR A X = (A  B)’ 0 0 1
Exclusive NOR X or 0 1 0
or Equivalence B X = A’B’+ AB 1 0 0
1 1 1
 Boolean Algebra
Boolean Algebra
Truth
* Algebra with Binary(Boolean) Variable and Logic Operations Table
* Boolean Algebra is useful in Analysis and Synthesis of
Digital Logic Circuits

- Input and Output signals can be

represented by Boolean Variables, and
- Function of the Digital Logic Circuits can be represented by
Logic Operations, i.e., Boolean Function(s) Boolean
- From a Boolean function, a logic diagram Function
can be constructed using AND, OR, and I

Truth Table

* The most elementary specification of the function of a Digital Logic

Circuit is the Truth Table Logic
Diagram
- Table that describes the Output Values for all the combinations
of the Input Values, called MINTERMS
- n input variables --> 2n minterms
 Boolean Algebra

Boolean Function: variable + operation

F(x, y, z) = x + y’z

Truth Table: Fig. 1-3(a) Logic Diagram: Fig. 1-3(b)

Relationship between a function Algebraic Expression
and variable Logic Diagram

x y z F
0 0 0 0 x
0 0 1 1
0 1 0 0 y F
2n Combination
0 1 1 0
Variable n = 3 1 0 0 1 z
1 0 1 1
1 1 0 1
1 1 1 1
Purpose of Boolean Algebra
To facilitate the analysis and design of digital circuit
Boolean function = Algebraic form = convenient tool
Truth table (relationship between binary variables : Fig 1-3a) Algebraic form
Logic diagram (input-output relationship : Fig. 1-3b) Algebraic form
Find simpler circuits for the same function : by using Boolean algebra rules
Boolean Algebra Rule : Tab. 1-1

[1] x + 0 = x [2] x • 0 = 0
[3] x + 1 = 1 [4] x • 1 = x
[5] x + x = x [6] x • x = x
[7] x + x’ = 1 [8] x • X’ = 0
[9] x + y = y + x [10] xy = yx
[11] x + (y + z) = (x + y) + z [12] x(yz) = (xy)z
[13] x(y + z) = xy +xz [14] x + yz = (x + y)(x + z)
[15] (x + y)’ = x’y’ [16] (xy)’ = x’ + y’
[17] (x’)’ = x

[15] and [16] : De Morgan’s Theorem

[ex.1] [ex.2] Fig. 1-6(a)
F= AB’ + C’D + AB’ + C’D F= ABC + ABC’ + A’C
= x + x (let x= AB’ + C’D) = AB(C + C’) + A’C Fig. 1-6(b)
=x = AB + A’C
= AB’ + C’D 1 inverter, 1 AND gate
Fig. 1-4 2 graphic symbols for NOR gate
x x
y (x+y+z)’ y x’ y’z’ =(x+y+z)’
z z

(a) OR-invert (b) invert-AND

Fig. 1-5 2 graphic symbols for NAND gate
x x
y (xyz)’ y (x’+y’+z’) = (xyz)’
z z

(a) AND-invert (b) invert-OR

 EQUIVALENT CIRCUITS
Many different logic diagrams are possible for a given Function

F = ABC + ABC’ + A’C .......…… (1)

= AB(C + C’) + A’C [13] ..…. (2)
= AB • 1 + A’C [7]
= AB + A’C [4] ...…. (3)
A
(1) B
C
F

(2) A
B
F
C

(3) A
B
F
C
 COMPLEMENT OF FUNCTIONS
A Boolean function of a digital logic circuit is represented by only using
logical variables and AND, OR, and Invert operators.

--> Complement of a Boolean function

- Replace all the variables and subexpressions in the parentheses

appearing in the function expression with their respective complements

A,B,...,Z,a,b,...,z  A’,B’,...,Z’,a’,b’,...,z’
(p + q)  (p + q)’

- Replace all the operators with their respective

complementary operators

AND  OR
OR  AND

- Basically, extensive applications of the DeMorgan’s theorem

(x1 + x2 + ... + xn )’  x1’x2’... xn’

(x1x2 ... xn)'  x1' + x2' +...+ xn'

 SIMPLIFICATION
Truth Boolean
Table Function
Unique Many different expressions exist

Simplification from Boolean function

- Finding an equivalent expression that is least expensive to implement

- For a simple function, it is possible to obtain
a simple expression for low cost implementation
- But, with complex functions, it is a very difficult task

Karnaugh Map(K-map) is a simple procedure for

simplifying Boolean expressions.

Truth
Table
Simplified
Karnaugh Boolean
Map Function
Boolean
function
 Map Simplification

Karnaugh Map(K-Map)
Map method for simplifying Boolean expressions
Minterm / Maxterm
Minterm : n variables product ( x=1, x’=0)
Maxterm : n variables sum (x=0, x’=1)
2 variables example
x y Minterm Maxterm
0 0 x'y' m0 x +y M0
0 1 x'y m1 x + y' M1
1 0 x y' m2 x'+ y M2
1 1 x y m3 x'+ y' M3

m0 + m1 + m2 + m3 M0  M1  M2  M3
F = x’y + xy
m1 m3
= ©(1,3) ( m1 + m3 )

= (0,2) (Complement = M0  M2 )
 KARNAUGH MAP
Karnaugh Map for an n-input digital logic circuit (n-variable sum-of-products
form of Boolean Function, or Truth Table) is
- Rectangle divided into 2n cells
- Each cell is associated with a Minterm
- An output(function) value for each input value associated with a
mintern is written in the cell representing the minterm
--> 1-cell, 0-cell

Each Minterm is identified by a decimal number whose binary representation

is identical to the binary interpretation of the input values of the minterm.
Karnaugh Map
x Identification x value
x F
0 0 of the cell 0 0 of F
0 1 1 1
1 0 1 1
F(x) =  (1)

1-cell
y 0 1
x y F x y 0 1
0 0 0 0 0 1 x
0 1 1 0 0 1
1 0 1 1 2 3
1 1 0
1 1 1
F(x,y) =  (1,2)
 KARNAUGH MAP
x y z F
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 0

u v w x F
0 0 0 0 0
0 0 0 1 1
0 0 1 0 0
0 0 1 1 1
0 1 0 0 0
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 0
1 0 1 1 1
1 1 0 0 0
1 1 0 1 0
1 1 1 0 1
1 1 1 1 0

F(u,v,w,x) =  (1,3,6,8,9,11,14)
Ex) F= x + y’z
(1) Truth Table (2) F(x, y,z) = ©(1,4,5,6,7)
x y z F Minterm (3)
y
0 0 0 0 m0
0 0 1 1 m1 0 1 3 2
0 1 0 0 m2
4 5 7 6
0 1 1 0 m3 x

1 0 0 1 m4
1 0 1 1 z
m5
1 1 0 1 m6
1 1 1 1 m7 F= x + y’z
[ex.] F(A,B,C) = ©(3,4,6,7)
F=AC’ + BC

[ex.] F(A,B,C) = ©(0,2,4,5,6)

F=C’ + AB’

[ex.] F(A,B,C,D) = ©(0,1,2,6,8,9,10)

F=B’D’ + B’C’ + A’CD’

Product-of-Sums Simplification
F(A,B,C,D) = ©(0,1,2,5,8,9,10)
F=B’D’ + B’C’ + A’C’D Sum of product

F’=AB + CD + BD’(square marked 0’s)

F’’(F)=(A’ + B’)(C’ + D’)(B’ + D) 전개
Product of Sum
 Combinational Circuits
A connected arrangement of logic gates with a set of inputs and outputs
Fig. 1-15 Block diagram of a combinational circuit

i0 f0
i1 Combinational f1
Circuits

...

...
(Logic Gates)
in fm

A sequential circuit
is an interconnection of F/F and Gate
Clocked synchronous sequential circuit
 Flip-Flops
Combinational Circuit = Gate
Flip-Flop Sequential Circuit = Gate + F/F

The storage elements employed in clocked sequential circuit

A binary cell capable of storing one bit of information
SR(Set/Reset) F/F D(Data) F/F
S
SET S R Q(t+1) D SET
Q
Q 0 0 D Q(t+1)
Q(t) no change
0 0 clear to 0
0 1 0 clear to 0
1 1 set to 1
R Q
1 0 1 set to 1
CLR
Q
CLR 1 1 ? Indeterminate
“no change” condition : Q(t+1)=D
1) Disable Clock
2) Feedback output into input p.52
JK(Jack/King) F/F
T(Toggle) F/F
SET J K Q(t+1)
J Q SET
0 0 Q(t) no change T Q T Q(t+1)
0 1 0 clear to 0 0 Q(t) no change
1 0 1 set to 1 1 Q'(t) Complement
K Q
CLR 1 1 Q(t)' Complement Q
CLR

JK F/F is a refinement of the SR F/F

T=1(J=K=1), T=0(J=K=0) 이면 JK F/F
The indeterminate condition of the SR
type is defined in complement 수식 표현 : Q(t+1)= Q(t)  T xor
 1-7 Sequential Circuits

A sequential circuit is an interconnection of F/F and Gate

Clocked synchronous sequential circuit Combinational Circuit = Gate
Sequential Circuit = Gate + F/F
Input Combinational
Circuit Output
Flip-Flops

Clock

DA D
SET

x Q A

Input Equation CLR

Q A’
DA = Ax + Bx, DB = A’x
Output Equation
y = Ax’ + Bx’ DB D
SET
Q B
Fig. 1-25 Example of a sequential Clock
CLR Q B’
circuit
y