computer system architecture for control system.ppt

Computer

1. COMPUTER SYSTEM
ACHITECTURE

2. Digital Logic Circuts
Chapter one

3. 3
Agenda
In this chapter :
1-1 Digital Computers
1-2 Logic Gates
1-3 Boolean Algebra,
1-4 Map Simplification
1-5 Combinational Circuits
1-6 Flip Flops
1-7 Sequential Circuits

4. 4
1-1 Digital Computers
Digital
The digital computer is a digital system that performs . The word
digital implies that the information in the information in the
computer is represented by variables that take a limited number
of discrete values.
BIT
Digital computer use the binary number system ,which has two
digits :0 and 1. A binary digit is called a bit .Information is
represented in digital computers in groups of bits .
In contrast to the common decimal numbersthat employ the base
10 system ,binary numbers use a base 2 system with two digits
:0 and 1 .The decimal equivalent of a binary number can be
found by expanding it into a power series with a base of 2 .

5. 5
For example , the binary number 1001011 represents a
quantity that can be converted to decimal number by
multiplying each bit by the base 2 raised to an integer power
as follows
1x2
6
+ 0x2
5
+ 0x2
4
+ 1x2
3
+ 0x2
2
+ 1x2
1
+ 1x2
0
= 75
The seven bits 1001011 represent a binary number whose
decimal equivalent is 75.
A computer system is sometimes subdivided into
functional entities hardware and software.
The hardware of the computer consists of all the electronic
components and electromechanical devices that comprise
the physical entity of the device. Computer software
consists of the instructions and data that the computer
manipulates to perform various data-processing tasks.

6. 6
Program
A sequence of instructions for the computer is called a program .
The data that are manipulated by the program constitute the data
base .
A computer system is composed of its hardware and the system
software available for its use . The system software of a
computer consists of a collection of programs whose purpose is
to make more effective use of the computer .The programs
included in a systems software package referred to as the
operating system .They are distinguished from application
programs written by the user for the purpose of solving
particular problems.

7. 7
Computer hardware
The hardware of the computer is usually divided into three major parts, as
shown in following fig .The central pressing unit (CPU) contains an
arithmetic and logic unit for manipulating data and executing
instructions. It is called random-access memory (RAM) because the CPU
can access any location in memory at random and retrieve the binary
information within a fixed interval of time .The input and output
processor (IOP) contains electronic circuits for communicating and
controlling the transfer of information between the computer and the
outside world .The input and output devices connected to the computer
included keyboards, printers, terminals, magnetic disk drives ,and other
communication devices .

8. 8
Binary and Decimal Numbers
Binary
1010 = 1x2
3
+ 0x2
2
+ 1x2
1
+ 0x2
0
0, 1, 10, 11 …
Called “Base-2”
Decimal
7,392 = 7x10
3
+ 3x10
2
+ 9x10
1
+ 2x10
0
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 …
Called “Base-10”
Octal
Based-8 : (0, 1, 2, 3, 4, 5, 6, 7)
Hexadecimal
Based-16 : (0, 1, 2, 3, 4, 5, 6, 7, 8 ,9 ,A ,B ,C ,D ,E ,F)
Reading : Mano. Chapter 1

9. 9
Binary Numbers: Operations
Summation
Multiplication
Subtraction
101101
+100111
----------
1010100
101101
-100111
----------
000110
1011
101
----------
1011
0000 .
1011 . .
----------
110111

10. 10
Binary Numbers: Conversions 1
(1010.011)
2= 2
3
+ 2
1
+ 2
-2
+ 2
-3
= (10.375)
10
(10.375)
10=
= (1010.011)
2
10/2 = 5 (reminder 0)
5/2 = 2 (reminder 1)
2/2 = 1 (reminder 0)
1/2 = 0 (reminder 1)
.
0.375x2 = 0.75 (integer 0)
0.75x2 = 1.5 (integer 1)
0.5x2 = 1.0 (integer 1)

11. 11
Binary Numbers: Conversions 2
Octal (2
3
= 8)
(10110001101011.111100000110)
2
(26153.7406)
8
Hexadecimal (2
4
= 16)
(10110001101011.111100000110)
2
(2C6B.F06)
16
10 110 001 101 011.111 100 000 110
2 6 1 5 3 . 7 4 0 6
10 1100 0110 1011.1111 0000 0110
2 C 6 B . F 0 6

12. 12
Complements
The complement of 012398 is
9’s complement (diminished radix complement)
•987601
10’s complement (radix complement)
•987602 = 987601 + 1
The complement of 1101100 is
1’s complement
2’s complement0010100
0010011

13. 13
Subtraction with Complement
10’s complement
Subtract 72532 –3250
2’s complement
Subtract 1010100 -1000011
72532
10’s complement: +96750
---------
Sum: 169282
Remove end carry: -100000
---------
Answer: 69282
1010100
2’s complement: +0111101
---------
Sum: 10010001
Remove end carry: -10000000
---------
Answer: 0010001

14. 14
Signed Binary Numbers 1
Due to hardware limitation of computers,
we need to represent the negative values
using bits. Instead of a “+”and “-”signs.
Conventions:
0for positive
1for negative

15. 15
Signed Binary Numbers 2
(9)
10= (0000 1001)
2
1. Signed magnitude:
(-9)
10= (1000 1001)
2
Changing the first “sign bit”to negative
2. Signed 1’s complement:
(-9)
10= (1111 0110)
2
Complementing all bits including sign bit
3. Signed 2’s complement:
(-9)
10= (1111 0111)
2
Taking the 2’s complement of the positive number

16. 16
Binary Codes 1
Alphanumeric Codes
Baudot Code (in Teletype
transmission)
•5 bit per character for 58 characters
(with 2 modes: letters & figures)
IBM’s BCD (Binary Coded Decimal)
•6 bit per character for 64 characters
•[Mano p. 17-20]
IBM’s EBCDIC (Extended Binary
Coded Decimal Interchange Code)
•8 bits per character similar to ASCII

17. 17
Binary Codes 2
Alphanumeric Codes
Gray Code
•[Reading Mano p. 21-22]
The ASCII (American Standard Code for
Information Interchange)
•7 bits per character to code 128 characters
including special characters ($ = 0100010)
•[Reading Mano p. 22-24]
Error detecting code
Even & Odd parity [Reading Mano p.24]

18. 18
Binary Logic
Binary Logic: Consists of Binary Variables and
Logical Operations
Basic Logical Operations:
AND
OR
NOT
Truth tables: Table of all possible combinations of
variables to show relation between values

19. 19
Logical Operation: AND
Value “1”only if all
inputs are “1”
Acts as electrical
switches in series
Denote by “. ” X Y X.Y
0 0 0
0 1 0
1 0 0
1 1 1

20. 20
Logical Operation: OR
Value “1”if any of the
inputs is “1”
Acts as electrical
switches in parallel
Denote by “+”
X Y X+Y
0 0 0
0 1 1
1 0 1
1 1 1

21. 21
Logical Operation: NOT
Reverse the value of input
Denote by complement sign ( !x or x’or x ).
Also called “inverter”
X X’
0 1
1 0

22. 22
Logic Gates
Is electronic digital circuits (logic circuits)
[Mano p.29-30]
Is blocks of hardware Called “digital circuits”,
“switching circuits”, “logic circuits”or simply “gates”

23. 23
X-OR Gates

24. 24
Input-Output Signals

25. 25
Binary Signals Levels
Acceptable level
of deviation
Nominal level
State of transition
Volts
3
2
1
0.5
0
-0.5
4
Logic 1
Logic 0

26. 26
Positive and negative logic

27. 27
Transfer of information with registers

28. 28
Example of Binary information system

29. 29
Exercises
Problem 1-2
Problem 1-3
Problem 1-10
Problem 1-16
My Advise :
Do all problems p: 30-31, Mano

30. 30
Boolean Algebra & Logic Gates
Chapter 2

31. 31
Agenda
Basic definitions
Proprieties of Boolean
Algebra
Boolean Functions
Canonical and standard
Forms
Reading
•Mano: Ch 2
Objectives
Understanding the
canonical forms
Maxterms and minterms
Simplifying Boolean
expression and functions

32. 32
Boolean Algebra
The mathematical system that operate with
binary values (George Boole (1854) )
Is the algebraic structure defined on a set of
elements with two binary operators +(OR)
and .(AND)
Reading :
Mano Chapter 2

33. 33
Operator precedence
Parenthesis
NOT
AND
OR

34. 34
Property of Boolean Algebra1
Closure
Obtaining a unique elements (which are the
membersof Boolean set)
Associative Law
(X*Y)*Z = X*(Y*Z)
(X+Y)+Z = X+(Y+Z)
Commutative Law
X*Y = Y*X
X+Y = Y+X

35. 35
Property of Boolean Algebra2
Identity Element
e*X=X*e=X
0+X=X+0=X
Inverse
X* X’ =0
X+ X’=1
Distributive Law
X*(Y+Z)=(X*Y)+(X*Z)
X+(Y.Z)=(X+Y).(X+Z)

36. 36
Basic Theorems
Duality
Huntington (1904) postulate that of an
algebraic expression, we can simply
interchange OR and AND operator and replace
1 by 0 and 0 by 1
[We will discuss this more in future sessions
when you enter the realm of digital design]

37. 37
Boolean Functions 1
F
1=x+y’.z
F
2=x.y.z’
X Y Z F
1 F
2
0 0 0 0 0
0 0 1 1 0
0 1 0 0 0
0 1 1 0 0
1 0 0 1 0
1 0 1 1 0
1 1 0 1 1
1 1 1 1 0

38. 38
Boolean Functions 2
HW : give the truth table of Functions F1 and F2

39. 39
Complement of a Function
De Morgan
(X+Y)’= X’.Y’
(A+B+C)’
= (A+X)’with X=B+C
= A’X’ (De Morgan)
= A’.(B+C)’
= A’.(B’C’) (De Morgan)
= A’.B’.C’ (Associative)

40. 40
Canonical Forms
Binary Variable can either be:
Normal Form (x)
Complement Form (x’)
Refer to your book (page 45)
For 3 binary variables (x, y, z) there are 8
possibility of response for AND operation
(minterms) and 8 possibility of OR operation
(maxterms)

41. 41
Minterms #1
“Minterms”or “Standard Product”
2 Binary Variable (X & Y) will form 2
n=2
Minterms
X’Y’, X’Y, XY’, XY
AND Terms (“product”)
Any Boolean function can be expressed as
a sum of Minterms(Table 2-4, page 45)
F1=x’y’z + xy’z’+ xyz
F1=m
1+ m
4+ m
7

42. 42
Minterms #2
Example 2-4 (page 46)
F = A + B’C
F = A (B + B’)+ B’C
F = AB + AB’+ B’C
F = AB (C + C’)+ AB’(C + C’)+ B’C
F = ABC + ABC’+ AB’C + AB’C’+ B’C
F = ABC + ABC’+ AB’C + AB’C’+ (A + A’)B’C
F = ABC + ABC’+ AB’C+ AB’C’+ AB’C+ A’B’C
F = ABC + ABC’+ AB’C + AB’C’+ A’B’C
F = m7 + m6 + m5 + m4 + m1
• (Table 2-5, page 47)
Sum of Minterms

43. 43
Maxterms
“Maxterms”or “Standard Sums”
2 Binary Variables (X & Y) will form 2
n=2
Maxterms
X’+Y’, X’+Y, X+Y’, X+Y
OR Terms (“sum”)
Any Boolean function can be expressed as a
product of Maxterms
F2=(x+y+z)(x+y+z’)(x+y’+z)(x’+y+z)
F2=M
0 . M
1 . M
2 . M
4

44. 44
Minterms & Maxterms #1
Minterms
X’Y’, X’Y, XY’, XY
Maxterms
X’+Y’, X’+Y, X+Y’, X+Y
Each Maxterms is the complement of its
corresponding Minterms & vice versa
Remember De Morgan?
Take a look at the next slide

45. 45
Minterms & Maxterms #2
Minterms Maxterms
xyz Term Desig. Term Desig.
000 x’y’ z’ m
0 x + y + zM
0
001 x’y’z m
1 x + y + z’ M
1
010 x’y z’ m
2 x + y’+ z M
2
011 x’y z m
3 x + y’+ z’ M
3
100 x y’z’ m
4 x’+ y + zM
4
101 x y’z m
5 x’+ y + z’ M
5
110 x y z’ m
6 x’+ y’ + z M
6
111 x y z m
7 x’+ y’+ z’ M
7

46. 46
Standard Forms
Doesn’t have to consists of all variables
Sum of Products : F
1= y’+ xy + x’yz’
Products of Sum : F
2= x (y’+ z) (x’ + y + z’)

47. 47
Implementation with tow and three levels

48. 48
Other Logic Operations
Boolean Operator Operator Symbol Name Comments
F0 = 0 Null Binary Constant 0
F1 = xy x.y AND x and y
F2 = xy’ x/y Inhibition x but not y
F3 = x Transfer x
F4 = x’y y/x Inhibition y but not x
F5 = y Transfer y
F6 = xy’+ x’y xy Exclusive OR x or y but not both
F7 = x + y x+y OR x or y
F8 = (x + y)’ xy NOR Not OR
F9 = xy + x’y’ (xy)’ Equivalence x equals y
F10 = y’ y’ Complement Not y
F11 = x + y X y Implication If y then x
F12 = x’ x’ Complement Not x
F13 = x’+ y X y Implication If x than y
F14 = (xy)’ xy NAND Not AND
F15 = 1 Identity Binary Constant 1

49. 49
Common Logic Gates
AND
OR
Inverter
Buffer
NAND
NOR
XOR
XNOR
Figure 2-5 (page 54)

50. 50
Exercises
HW :
Problems 2-1 until 2-23 Mano

51. 51
Gate Level Minimization
Chapter 3

52. 52
Agenda
Simplification of
Boolean Functions
(The K-Map Method)
Don’t Care Condition
Synthesis with NAND
& NOR Gate
Brief on Gate
Implementation
Main Reading
•Mano: Ch 3
Objectives
Understand the procedure of
simplifying Boolean
functions
Understand and able to
perform the K-Map method
Understand the Don’t Care
Condition and their place in
K-Map Method
Understand and able to
implement design in NAND
and NOR Gate
Understand the basic of Gate
Implementation

53. 53
The Map Method
Provides a simple straightforward procedure
for minimizing Boolean functions
Proposed by Veitch (Veitch Diagram),
modified by Karnaugh (Karnaugh Map)
Why bother?
•Simplifying the function = minimizing the
amount of gates
•Industrial requirements for efficiency in
mass production

54. 54
2-Variable Map
The Map represents a visual diagram of all possible
ways a function may be expressed in a standard form

55. 55
2-Variable Map
Representing Function in the map
•F= x.y F= x+y = x’y + xy’+ xy

56. 56
3-Variable Map
The Map represents a visual diagram of all possible
ways a function may be expressed in a standard form

57. 57
3-Variable Map : Example F(x,y,z)

58. 58
3-Variable Map :
Other Examples F(x,y,z)

59. 59
Simplifying using the Map
F = A’C + A’B + AB’C + BC
Plot the expression
Find minimum
adjacent squares
•Prime Implicant
•Essential Prime Implicant
Draw them
Write the expression
F = C + A’B
A
BC
0100
0
1
A
B
1011
C
1
1
1
1
1

60. 60
4-Variable Map

61. 61
Simplifying using the Map
Take the Boolean Function
F = A’C + A’B + AB’C + BC
What form is it? Canonical or Standard?
Express it in sum of Minterms
F = A'B'C + A'BC + A'BC' + AB'C + ABC
You don’t have to do this step, we can just jump it
Find the minimal sum of product expression

62. 62
Want to Proof it?
F
1= A’C + A’B + AB’C + BC
F
1= A’C + A’B + AB’C + BC
F
1= C (A’ + AB’+ B) + A’B
F
1= C (A’[B + B’] + AB’+ [A + A’] B) + A’B
F
1= C (A’B + A’B’+ AB’+ AB + A’B) + A’B
F
1= C (A’B’+ AB’ + AB + A’B) + A’B
F
1= C ( [A’ + A] B’+ [A + A’]B) + A’B
F
1= C (B’+ B) + A’B
F
1= C + A’B

63. 63
4-Variable Maps (Example)
F(w,x,y,z) =
∑(0,1,2,4,5,6,8,9,
12,13,14)
0000, 0001, 0010,
0100, 0101, 0110,
1000, 1001, 1100,
1101, 1110

64. 64
Product of Sum Simplification
F(w,x,y,z) =
∑(0,1,2,4,5,6,8,9,
12,13,14)
0000, 0001, 0010,
0100, 0101, 0110,
1000, 1001, 1100,
1101, 1110
1
wx
yz
0100
00
01
w
y
1011
z
1 0 1
11
10
x
1 1 0 1
1 1 0 1
1 1 0 0

65. 65
Product of Sum Simplification
F' = yz+wx’y
F=(F’)’
F=(yz + wx’y)’
F=(yz)’(wx’y)’
F=(y’+z’)(w’+x+y’)
1
wx
yz
0100
00
01
w
y
1011
z
1 0 1
11
10
x
1 1 0 1
1 1 0 1
1 1 0 0

66. 66
Are they the Same?
F = y' + w'z' + xz'
F'= yz + wx'y
(F’)’
(yz + wx’y)’
(yz)’(wx’y)’
(y’+z’)(w’+x+y’)
y'w' + y'x + y'y' + z'w' + z'x + z'y'
y'(w' + x + z' + y') + z'w' + z'x
y'+ z'w' + z'x
Product of Sum Simplification
Normal Simplification (Sum of Product)

67. 67
5-Variable Map

68. 68
5-variable Map

69. 69
Product of sums simplification

70. 70
Don’t Care Conditions :
Sometimes a certain combination of inputs will
never be evaluated by your digital system, thus a
“Don’t care”is placed for those valuation
E.g. consider a BCD (Binary Coded Decimal) number,
there are 4 binary variables b
3,b
2,b
1,b
0that represents
decimal 0 to 9. design a system that detect if the
BCD input given is divisible with 3
•4 bits has 16 combinations, but only 10 are used to
represent decimal 0 to 9, the remaining combinations are
not used.
•System will produce 1 if the BCD is divisible by 3.

71. 71
Don’t Care Example
DecimalBinary
Represe
ntation
b
3
b
2
b
1
b
0
f
0 00000
1 00010
2 00100
3 00111
4 01000
5 01010
6 01101
7 01110
8 10000
9 10011
Unused1010d
Unused1011d
Unused1100d
Unused1101d
Unused1110d
unused1111d
0
b
1
b
0
0100
00
01
1011
0 1 0
11
10
0 0 0 1
d d d d
0 1 d d
b
3
b
2

72. 72
Simplifying With Don’t Cares
b
2b
1b
0’+b
2’b
1b
0+b
3b
0
You can either use or not use
the don’t care cell
(it can be treated like a “1” if
it can produce more efficient
result)
0
b
1b
0
0100
00
01
1011
0 1 0
11
10
0 0 0 1
d d d d
0 1 d d
b
3
b
2

73. 73
So What Does Don’t Care Means?
We simply don’t care what the function
values are for the unused input valuation
Denote by “d”or “x”
Keep in mind to use as minimum amount of
terms as possible

74. 74
Example with don’t Care condition

75. 75
Implementation of Logic Gates
Inverter
NOR
NAND
In the market, logic gates are more commonly
implemented using NAND and NOR gates rather
than AND & OR
Because It is easier to manufactured

76. 76
NOT, AND & OR Gates
implementation using NANDx
x
y
x
y
X'
xy
(x’y’)’ = x+y
NOT
AND
OR

77. 77
NAND Gate’s Symbols
NAND Gate as Universal Gate
Any gate can be represented using NAND
Implemented as if AND-Invert or Invert-OR
(xyz)' = x' + y' + z'
=

78. 78
Two-Level Implementation
F = AB + CDA
B
C
D
F
Read the
summary of
procedure in
Page 85 (top)A
B
C
D
F A
B
C
D
F

79. 79
Two-Level Implementation
F = AB + CDA
B
C
D
F
Read the
summary of
procedure in
Page 85 (top)A
B
C
D
F A
B
C
D
F
Level-1
Level-2

80. 80
Exclusive OR Function

81. 81
Gates Implementation : example

82. 82
Summary
General Procedure implementation
Obtain the Boolean Function
Simplify the Function using K-Map
Convert all AND into NAND using
AND-Invert symbols
Convert all OR into NAND using
Invert-OR symbols
Check all the Bubbles in the diagram, add Inverter
if necessary

83. 83
Brief
Other Implementations
NOR implementation
As the Dual of NAND operation
Wired Logic implementation
(refer to your book page 89)

84. 84
Brief
XOR & Parity Checking
Observed XOR implementation
(page 95)
Mostly used in Parity generator and parity
checking purpose in a computer architecture

85. 85
Design Procedure
Problem is stated
Number of available input and required
output is determined
Input and output are assigned letter symbol
Truth table is derived to show relationships
among variables (including don’t care)
Simplified Boolean function is obtained
Logic diagram is drawn

86. 86
1.Problem is stated
We wish to design a Code Conversion
Logic from BCD (Binary Coded Decimal)
to Excess-3 Code
The Converter may act as an interface for 2
different data communication systems

87. 87
2.Input & output Determined
The input lines will supply BCD input :
 BCD is a 4 bit binary system 4 bits
The output lines should produce Excess-3
Code output :
 Excess-3 is a 4 bit binary system 4 bits

88. 88
3.Letter Symbol Assigned
Input: BCD : (A, B, C, D)
Output: Excess-3 : (W, X, Y, Z)

89. 89
4. The following truth Table is Derived
Input BCD Output Excess Three code
0 0 0 0 0 0 1 1
0 0 0 1 0 1 0 0
0 0 1 0 0 1 0 1
0 0 1 1 0 1 1 0
0 1 0 0 0 1 1 1
0 1 0 1 1 0 0 0
0 1 1 0 1 0 0 1
0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 1
1 0 0 1 1 1 0 0
1 0 1 0 d d d d
1 0 1 1 d d d d
1 1 0 0 d d d d
1 1 0 1 d d d d
1 1 1 0 d d d d
1 1 1 1 d d d d

90. 90
5.Simplify Boolean Function
For output Z : Z = D'

91. 91
5.Simplify Boolean Function
For output Y :Y = CD + C'D'

92. 92
For output X
X = BC + B'D + BC'D'
5.Simplify Boolean Function

93. 93
5.Simplify Boolean Function
For output W
W = A + BC + BD

94. 94
6. Boolean Function
Simplified Boolean Function
Z = D'
Y = CD + C'D'
X = B'C + B'D + BC'D'
W = A + BC + BD
Implementation Equation
Z = D'
Y = CD + (C+D)'
X = B‘(C+D) + B (C+D)'
W = A + B(C+D)

95. 95
6.Draw Logic Diagram

96. 96
Consideration in Design
Minimum number of gates
Minimum number of input to a gate
Minimum propagation time of signal through circuit
Minimum number of interconnections
Limitation of the driving capabilities of each gates

97. 97
Analysis Procedure
The “analysis” is the reverse of “design” :
Make sure that it is a combinational and not a
sequential. Indicated by No Feedback loop.
Proceed to create Boolean Function or Truth
Table. If Boolean function is supplied, the
K-map can be directly derived.
The simplified Boolean function can then be
written down.

98. 98
Multilevel Logic Circuit #1
Universal Gate (NAND) :
NAND is called Universal Gate, because it can
derived all gate with NAND gate.

99. 99
Explanation
Conduct your design steps following this guideline:
Identify the input and output relation
Write the required functions (Boolean expressions)
Simplify and optimized your expression using the
Karnough-Map
Write the simplified functions (Boolean expressions)
Implement your design using the appropriate gates and
draw the designs (you may use the appropriate logic
gate IC, e.g. AND, OR, NAND, NOR, XOR)
Build & test your design on a proto-board powered by
a batteries or Dc-adapter
Do necessary adjustments

100. 100
Exercises:
Simplify the following Boolean functions in
Sum of products
Products of sum
Draw the implementation for each one
(with AND and OR gates respectively):
F(A,B,C,D) = ∑(0,1,2,5,8,9,10)
F(X,Y,Z) = ∑( 1,3,5,7)

101. 101
Combinational Logic : Definition
Combinational Logic is a logical circuit
consists of logic gates whose outputs at
any time are determined directly from the
present combination of inputs without
regard to previous inputs
Combinational Circuit
A
B

102. 102
Common Combinational Logic
Binary Adders
Half-Adders
Full-Adders
Binary Substractors
Half-Substractors
Full-Substractors
Decoders/Encoders
Multiplexers

103. 103
Binary Adders
One of the basic arithmetic process in
computer system
One that performs the addition of 2 bits is
Half–Adder
One that performs the addition in 3 bits (2
significant bits and a previous carry) is called
Full–Adder

104. 104
Half-Adder
2 Input & 2 output
The truth table
Thus the Boolean
Function is
S = x'y+xy';
C = xy
The function cannot be
further simplified
X Y C S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
Truth Table

105. 105
Half-Adder Implementations

106. 106
Full–Adder Truth Table
3 Input (x & y as the input
and z as the previous
carry), & 2 output (s, c)
The truth table is :
X Y Z C S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1

107. 107
Full-Adder Map

108. 108
Full–Adder Simple Implementation
Logic Expression
S = x'y'z+x'yz'+xy'z'+xyz
C = xy + xz + yz
Implementation

109. 109
Full–Adder Implementation

110. 110
Full–Adder Other Implementation
S=xxoryxorz

111. 111
Full–Adder Application

112. 112
Synchronous Sequential Logic
•Flip-flops
rev

113. 113
Sequential Logic
In practice there is a lot of digital system that requires
memory elements
Where the next sequence of output depends on the previous
output.
Since more than one parts exist, we need to synchronize
them.Combinational
Circuit
Memory
Elements
Inputs Outputs
Non-combinational Circuit
A
B

114. 114
Flip-flops
The Memory
The memory elements used in Clocked
Sequential Circuits are called Flip-Flops
A Flip-Flops is a Binary Cells capable of
storing one bit of information

115. 115
RS Flip-flop / RS Latch
Is the basic Flip-Flop circuit
S = Set, R = Reset
Also called direct-coupled RS flip-flop or
SR latchR (reset)
S (set)
Q
Q'
1
2
NCNC00
0101
Q’QRS
No Change
(after S=1, R=0)0100
(after S=0, R=1)1000
1010
0011 Race Condition

116. 116
RS Flip-flop/RS Latch Timing DiagramR (reset)
S (set)
Q
Q'
1
2 Time
S
Q ?
?Q'
R
SRQQ’
00NCNC
0101
1010
1100Race

117. 117
RS Flip-flop ImplementationsR (reset)
S (set)
Q
Q'
1
2
NCNC00
0011
1000
1010
0100
0101
Q’QRS
(after S=0, R=1)
(after S=1, R=0)
No Change
1001
NCNC11
1100
0111
0110
1011
Q’QRS
(after S=0, R=1)
(after S=1, R=0)
No Change
Race
Race
S (set)
R (reset)
Q
Q'
1
2

118. 118
Synchronization
Synchronization is achieved using a timing
device called Master-Clock Generator,
which generates a periodic train of Clock
PulsesPulse Width
Period
0 1 0 1 0 1 0
This clock is
used to trigger
the components.

119. 119
Clock Pulse Triggers
Positive Pulse
Transition/Edge
Negative Pulse
Transition/Edge
Positive
Level1
0
Positive Edge
Negative Edge
01 0 10 1

120. 120
Clocked Flip-flops
Synchronous sequential circuits that use
clock pulses in the inputs of memory
elements are called Clocked Sequential
Circuits
Clocked Flip-Flop is the memory part of the
Sequential Circuit which is driven by a clock
pulse

121. 121
Clocked RS Flip-flop #1
Clock Pulse (CP) as an enable signal for the
other two inputs
If CP goes to 1, information from the S or R
input is allowed to reach outputQ
Q'
1
2
S
R
CP
3
4

122. 122
Clocked RS Flip-flop #2Q
Q'
1
2
S
R
CP
3
4
C S R Q
(t+1)
0 X X No Change
1 0 0 No Change
1 0 1 0 (Reset)
1 1 0 1 (Set)
1 1 1 Intermediate/
Not Stable/
RaceQ
Q
SET
CLR
S
R

123. 123
Indeterminate Condition
Problem in RS Flip-Flop
The indeterminate condition
(CP=1, R=1, S=1)
This place gate 3 & 4 to 0 and place 1 in both Q and Q’
When CP goes back to 0, it is not possible to determine the
next state
It become a
race between
Gate 3 & 4’s
responses
Should be
avoidedQ
Q'
1
2
S
R
CP
3
4

124. 124Q
Q'
1
2
D
CP
3
4
5
D Flip-flops (Gated D Latch)
Eliminates the indeterminate state in
RS Flip-Flop, by ensuring R & S
will never have same value
C D Q
(t+1)
0X No Change
1 0 0 (Reset)
1 1 1 (Set)Q
Q
SET
CLR
D

125. 125
JK Flip-flops #1
Is the refinement of RS
flip-flop
J is Set, K is Reset
If both is 1, the output
togglesK
CP
J
Q
Q' 11
1 1
00 01 11 10
0
1Q
K
JJK
Q
Q J K Q
(t+1)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0
Q
(t+1)=JQ’+K’Q

126. 126
JK Flip-flops #2
Because of the feedback connection, a CP pulse
that remains in the 1 state while both J & K equals
to 1 will cause the output to complement again
and repeat complementing until the pulse goes
back to 0
Thus the CP has to have a time duration shorter than the
propagation delay time of the flip-flop
This restriction is eliminated in Master-Slave or edge-
triggered Flip-flop

127. 127
T Flip-flops
The T flip-flop works on the same
principals with JK flip-flop
But instead of having 2 inputs, it has only one
that will cause the Q to toggles between normal
and complement formT
CP
Q
Q'
Q T Q
(t+1)
0 0 0
0 1 1
1 0 1
1 1 0

128. 128
Master-Slave Flip-flops #1
Constructed from 2 separate flip-flops, the
master and slave
The Master and Slave never enabled at the
same time due to inverted clockQ
Q
SET
CLR
S
R
S
CP
Q
Q
SET
CLR
S
RR
Q
Q'
y
y '
Master SlaveCP
S
y
Q

129. 129
Master-Slave Flip-flops #2
Thus, any input changes during the first clock
cycle will effect the master, but not the slave
Then the result of the master will determine the
output of the slave on the next clock
•And during that clock, any input changes to the
master will not effect the slave (because the master
is already disabled again)Q
Q
SET
CLR
S
R
S
CP
Q
Q
SET
CLR
S
RR
Q
Q'
y
y '
Master Slave

130. 130
Edge-Triggered Flip-flops
D-type positive-edge-triggered flip-flop
The edge
of transition
triggers the output
change Certain
threshold levelQ
Q'
5
6
1
2
3
4
S
R
D
CP

131. 131
Exercise 4
Problem 5-1
Problem 5-3

132. 132
Sequential Circuits
A Sequential Circuits is aninterconnection Of flip–flopsand
gates . The gates by themselves constitute a combinational
circuits ,but when included with the flip-flops, the overall
circuit is classified as Sequential Circuits .The block diagram of
a clocked sequential circuits is shown in the following fig
Flip-Flop Equations
An example ofa sequentialcircuit is shown in the following
fig

133. 133
It has one input variable x ,one output
variable y ,and tow clocked D flip-flop .The
AND gates, OR gates ,and inverter from the
combinational logic part of the circuit .

134. 134
Input equation
DA=AX+BX
D
B=A
\
X Y=AX
\
+BX
\

135. 135
Y=AX
\
+BX
\
STATE TABLE
DA=AX+BX
DB=A
\
X
Present state
Next state
State table
X Input
Present state for A and B
Next statefor A and B

136. 136
n Input
m flip-flop
P output
m clomps for present state ,n clomps for Input
m clomps for next state, p clomps for output state
2
m+n
lines
STATE TABLE STATE DIAGRAM
DA=AX+BX
D
B=A
\
X Y=AX
\
+BX
\

137. 137
Anatomy of a State Diagram
State is represented by a
circle containing the state’s
binary
The transition is represented
by the directed lines
The label “1/0”means that
with the input 1 the state
will change to the other
state (following the arrow)
and the output produced is 000
01
10
11
0/0
1/0
1/0
1/0
1/0
0/1
0/1
0/1

138. 138
State Table : Drawing the State
Diagram from State Table00
01
10
11
0/0
1/0
1/0
1/0
1/0
0/1
0/1
0/1
Current in Next out
ABXABY
000000
001010
010001
011110
100001
101100
110001
111100

139. 139
DESIGN EXAMPLE
We wish to design clocked sequential circuit that
goes through a sequence of repeated binary states
00 , 01, 10 and 11 . When an external input x is
equal to 1 . The state of the circuit remains
unchanged when x=0
This type of circuit is called a 2-bit binary counter
because the state sequence is identical to the count
sequence of tow binary digits.

140. 140
State diagram for binary counter

141. 141
Q(t)Q
(t+1) J K
0 0 0 X
0 1 1 X
1 0 X 1
1 1 X 0
Q(t+1)=JQ’+K’Q

142. 142
J
A=BX K
A=BX
J
B=X K
B=X

143. 143

144. 144
CHAPTER TWO
DIGITAL COMPONENTS
Integrated Circuits
Families
TTL Transistor transistor Logic
ECL Emitter coupled Logic
MOS Metal-oxide semiconductor
CMOSComplementary Metal-oxide semiconductor

145. 145
Decoders
3-TO-8
N-INPUT-A0,A1,A2 -
2
n
=8 OUTPUT D0-D7 and Enable

146. 146
2-to –4 line decoder with NAND

147. 147
Decoder Expansion
Figure 2-3

148. 148
Encoders
Table 2-2
A
0=D
1+D
3+D
5+D
7
A
1=D
2+D
3+D
6+D
7
A
2=D
4+D
5+D
6+D
7

149. 149
Multiplexers
Figure 2-4

150. 150
Table 2-3
Figure 2-5

151. 151
Registers
Figure 2-6

152. 152
Figure 2-7 4-bit register with parallel load

153. 153
Shift Registers
Figure 2-8

154. 154
Figure 2-9
Bidirectional Shift Registers with parallel load

155. 155
Binary Counters
n flip-flop counter from 0 to 2
n-1
Figure 2-10

156. 156
Synchronous counter up counter
Asynchronous counter Down counter

157. 157
Table 2-5
Memory unit
A memory unit is a collection of cells together with associated circuits
needed to transfer information in and out of storage .
The memory stores binary information in groups of bits called words .a
word in memory is an entity of bits that move in and out of storage as
unit . A memory word is a group of 1s and 0s and may represent a
number, an instruction code , one or more alphanumeric characters or
any other binary –coded information .a\group of eight bits is called a
byte .most computer memories used words whose number of bits is a
multiple of 8 . Thus a 16 bit word contains two bytes , and a 32 bit
word is made up of four bytes . The capacity of memory in commercial
computer is usually stated as total number of bytes that can be stored.
The internal structure of a memory unit is specified by the number of
words contains and the number of bits in each word .special input lines
called address lines select one particular word .Each word in memory
is assigned an identification number , called an address starting from 0
and continuing with 1,2,3 up to 2
k
-1where k is the number of address
lines

158. 158
The selection of a specific word inside the memory is done by
applying the k-bit binary address to the address lines . A
decoder inside the memory accepts this address and opens the
paths needed to select the bits of the specified word .computer
memories may range from 1024 words , requiring an address of
10 bitts, to 2
32
words requiring 32 addresses bits
. It is customary to refer to the number of words (or bytes ) in a
memory with one of the letters k (kilo), M (mega) or G (giga)
K is equal to 2
10
,M is equal to 2
20
, and G is equal to 2
30
.Thus
64K = 2
16
, and 4G = 2
32
.
Tow major types of memories are used in
computer systems : random access memory
(RAM) and read –only memory (ROM)

159. 159
Random access memory (RAM)
Memory cells that can
be accessed for
information transfer to
or from any desired
random location is a
RAM
A Word is group of
bits, which is the
entity of bits that
move in and out of
storage as a unitMemory Unit
2
k
words
n bit per wowrd
write
Read
n data input lines
n data output lines
k address lines

160. 160
Read –only memory (ROM)
A ROM has k address input lines to select one of
2k=m words of memory and n output lines , one for
each bit of the word .

161. 161
Decoders #1
Decodes/convert information from one
format into another format
Usually if the input is n-bits, the output is no
greater than 2
n
-bits
Example:
•Binary to BCD decoders
•BCD to excess-3 decoders
•Binary to 7 segment decoders
•…. MORE ….

162. 162
Decoders: Binary-to-7 Segment #1
Display the decimal digits in a recognizable
format to us
Each segment is a LED (Light Emitting Diodes)
that can either be On (1) or Off (0)a
b
c
d
g
f
e
On Off

163. 163
Decoders Binary-to-7 Segment #2a
b
c
d
g
f
e
On Off Binary
to
7-Segments
1
13 x 7
decoders
0
0
1
1
1
1
1
1

164. 164
Encoders
Encoders perform the opposite of Decoders and
usually work in pairs
Perform the opposite operation of decoders
Have more input lines than output lines3 x 7
Decoder
7 x 3
Encoder

165. 165
Registers#4:
Register in a Sequential-Logic
In a more complex sequential logic, the
register take the role of memory component
in sequential logic circuit, which holds n-
bits of informationRegister
Combinational
Circuit
CP
Inputs
Next - state Value

166. 166
Counters
A Counter is a special type of register that
goes through a predetermined sequence of
states upon the application of input pulses
The combinational circuit around the flip-
flops controls the predetermined sequence

167. 167
Ripple Counters
(Asynchronous Counters)
Implemented using T
or JK flip-flop with
output of each FF
connected to the CP of
the next
The FF holding the
least significant bit
receive the incoming
inputJ
Q
Q
K
SET
CLR
J
Q
Q
K
SET
CLR
J
Q
Q
K
SET
CLR
J
Q
Q
K
SET
CLR
Count Pulse
Logic 1
A
4
A
3
A
2
A
1

168. 168
Ripple Counters
(Asynchronous Counters)J
Q
Q
K
SET
CLR
J
Q
Q
K
SET
CLR
J
Q
Q
K
SET
CLR
J
Q
Q
K
SET
CLR
Count Pulse
Logic 1
A
4
A
3
A
2
A
1
A
4A
3A
2A
1
0000
0001
0010
0011
0100
0101
0110
0111
1000

169. 169
State Diagram#1
The transition is
represented by the
directed lines
The level 1/0 means
that with the input 1
the state will change
and the output
produced is 000
01
10
11
0/0
1/0
1/0
1/0
1/0
0/1
0/1
0/1

170. 170
State Diagram #2: State Table00
01
10
11
0/0
1/0
1/0
1/0
1/0
0/1
0/1
0/1
CurrentinNextout
ABXABY
000000
001010
010001
011110
100001
101100
110001
111100

171. 171
The Implementationx
y
Q
Q
SET
CLR
D
Q
Q
SET
CLR
D
CP
A
A'
B
B'

172. 172
BCD Ripple Counter0000 0001 0010 0011 0100
1001 1000 0111 0110 0101
State Diagram A
4
A
3
A
2
A
1
CP
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
0
0
0
1
0
0
1
1
0
1
0
Timing Diagram J
Q
Q
K
SET
CLR
J
Q
Q
K
SET
CLR
J
Q
Q
K
SET
CLR
J
Q
Q
K
SET
CLR
Count Pulse
Logic 1
A
4
A
3
A
2
A
1

173. 173
Synchronous Counters
Distinguished from
ripple counters that the
CP is applied
simultaneously to all
of the flip-flopJ
Q
Q
K
SET
CLR
J
Q
Q
K
SET
CLR
J
Q
Q
K
SET
CLR
J
Q
Q
K
SET
CLR
Count Enable
CP
A
4
A
3
A
2
A
1
To Next Stage

174. 174
Timing Sequences
The sequence of operations in a digital
system are specified by a control unit
The timing sequence in the control unit can
be easily generated by using a counters or
shift register

175. 175Memory Unit
2
k
words
n bit per wowrd
write
Read
n data input lines
n data output lines
k address lines
RAM (Random Access Memory)
Memory cells that
can be accessed for
information transfer
to or from any
desired random
location is a RAM
A Word is group of
bits, which is the
entity of bits that
move in and out of
storage as a unit

176. 176
Memory Decoding
A memory unit will requires a decoding
circuits to selectthe memory word specified
by the input addressQ
Q
SET
CLR
S
R
input
Output
Select
Read/Write
S
R
BCinput Output
Select
Read/Write

177. 177BC BC BC
BC BC BC
BC BC BC
BC BC BC
Word 0
Word 1
Word 2
Word 3
D
0
D
1
D
2
D
3
2 x 4
Decoder
Address
Inputs
Memory
Enable
Read/Write
Data Inputs
Data Output

178. 178
Error Correcting Codes
The complexity of memory array may cause
occasional errors in storing and retrieving the
binary information
Error Correcting Codes tries to improve the
reliability of the memory unit
The code generate multiple check bits that are
stored with the data word in the memory, which is
also called Parity Bit
More on Error Correction Scheme on Data
Communication Section

179. 179
Exercise #6
Design a combinational logic circuit which
function as a BCD to 7-Segment decoder to
convert the decimal digit in BCD to the
appropriate code for the selection of
segments in a display indicator used for
displaying the decimal digit in a familiar
form(BCD to 7 Segment Decoder) using a
minimum number of NAND gates
Due dates is on the NEXT Class Session

180. 180
The 7 Segment
Display the decimal digits in a recognizable
format to us
Each segment is a LED (Light Emitting
Diodes) that can either be On (1) or Off (0)a
b
c
d
g
f
e
On Off

181. 181
Input & Output
Binary Coded Decimal
4 bits input (w, x, y, z)
7 Segment
7 bits output (a, b, c, d, e, f, g)
Each controls the on or off of one segment

182. 182
What You Should Do
Draw the Truth Table
Plot the K-Map
Write down the Simplified Boolean Function
Draw the Implementation Diagram (using the
Gates)
Construct the Gates using the appropriate ICs and
on the test bed
Write the Report for all your design step
Present your report & system in front of the class

183. 183
Project #2 -#1
Continuing from Project #1 and with your
knowledge on the synchronous sequential logic,
add a clock generator and add:
Option 1: Parallel Loader (1 Adder & Subtractor, 2
Multipliers)
Option 2: Serial Loader (1 Adder & Subtractor, 2
Multipliers)
For each of the variables used in the ALU you
designed in Project #1 (thus, you will have to
construct 2 loaders per group, 1 loader for each of
the variable).

184. 184
Project #2 -#2
Deliverables
Document all the steps in a report and prepare a
presentation of the steps done, problems
encountered and steps taken to overcome them,
the test results and demonstration of the
construction.

185. 185
Project #3 -#1
Construct an ALU that will calculate the
determinant of a matrix:
Use the Synchronous Sequential Logic to
sequence the steps of the calculation and
combine the Multipliers and Adders &
Substractors that you constructed on Project #1
with the Loader you construct in Project #2. cbda
dc
ba
..det 







186. 186
Project #3 -#2
Thus to complete this step of the project you will
have to merge your groups by selecting other
groups that construct the required parts:
1 (one) group that did Adder & Subtractor
2 (two) groups that did Multiplier
Select groups with the same loader (all parallel
loader or all serial loader)
You may need to construct additional
combinational or sequential logic circuits in order
to complete the project.