Transcript Y - TU Delft

Digital Logic
TU-Delft
in1200/04-PDS
1
Unit of Information
Computers consist of digital (binary) circuits
 Unit of information: bit (Binary digIT), e.g. 0
and 1
 There are two interpretations of 0 and 1:

- as data values
- as truth values (true and false)
TU-Delft
in1200/04-PDS
2
Bit Strings

By grouping bits together we obtain bit
strings
- e.g <10001>
which can be given a specific meaning
 For instance, we can represent non-negative
numbers by bitstrings:
0
1
2
3
TU-Delft
<00>
<01>
<10>
<11>
<10>
<00>
<01>
<11>
in1200/04-PDS
3
Boolean Logic

We want a computer that can calculate, i.e
transform strings into other strings:
1 +2 = 3



<01>  <10> = <11>
To calculate we need an algebra being able to use
only two values
George Boole (1854) showed that logic (or symbolic
reasoning) can be reduced to a simple algebraic
system
TU-Delft
in1200/04-PDS
4
Boolean algebra


Rules are the same as school algebra:
x+y = y+x
xy = yx
Commutative Law
x(y+z) = xy + xz
Distibutive Law
(x+y)+z = x+(y+z)
Associative Law
There is, however, one exception:
x.x = x !
TU-Delft
in1200/04-PDS
5
Boolean algebra
To see this we have to find out what the
operations “+” and “.” mean in logic
 First the “.” operation: x.y (or x  y )
 Suppose x means “black things” and y means
“cows”. Then x.y means “black cows”
 Hence “.” implies the class of objects that has
both properties. Also called AND function.

TU-Delft
in1200/04-PDS
6
Boolean algebra
The “+” operation merges independent
objects: x + y (or x  y)
 Hence, if x means “woman” and y means
“man”
 Then x+y means “man and women”
 Also called OR function

TU-Delft
in1200/04-PDS
7
Boolean algebra
Now suppose both objects are identical, for
example x means “cows”
 Then x.x comprises no additional information
 Hence

x.x = x2 = x
x +x = x
TU-Delft
in1200/04-PDS
8
Boolean algebra
Next, we select “0” and “1” as the symbols in
the algebra
 This choice is not arbitrary, since these are
the only number symbols for which holds x2 =
x
 What do these symbols mean in logic?

- “0” : Nothing
- “1” : Universe

So 0.y = 0 and 1.y = y
TU-Delft
in1200/04-PDS
9
Boolean algebra
Also, if x is a class of objects, then 1-x is the
complement of this class
 It holds that x(1-x) = x -x2 = x-x =0
 Hence, a class and its complement have
nothing in common
 We denote 1-x as x instead of the usual x

TU-Delft
in1200/04-PDS
10
Boolean algebra
A nice property of this system that we write
any function f(x) as
f(x) = a.x + b(1-x)
 We can show this by observing that virtually
every mathematical function can be written
in polynomial form, i.e
f(x) = a0 + a1x + a2x2 +….

TU-Delft
in1200/04-PDS
11
Boolean algebra
Now xn = xn-1.x = xn-2.x.x = x
 Hence, f(x) = a0 + a1.x
 Let b = a0 and a = a0 + a1

Then we have f(x) = a.x + b(1-x)
 From this it follows that

f(0) = b
f(1) = a
TU-Delft
in1200/04-PDS
12
Boolean algebra

So
f(x) = f(1).x + f(0).(1-x)
 More dimensional functions can be derived in
an identical way:
f(x,y) = f(1,1).x.y + f(1,0).x(1-y) +
f(0,1).y(1-x) + f(0,0).(1-x)(1-y)
TU-Delft
in1200/04-PDS
13
Binary addition


We apply this on the modulo-2 addition
x
y

0
1
0
1
0
0
1
1
0
1
1
0
xy = x(1-y) + y(1-x) = x.y +x.y
TU-Delft
in1200/04-PDS
14
Binary multiplication


Same for modulo-2 multiplication
x
y

0
1
0
1
0
0
1
1
0
0
0
1
xy = x.y
TU-Delft
in1200/04-PDS
15
Functions
Let X denote bitstring, e.g. <x4 x3 x2 x1 >
 Any polynomial function Y=f(X) can be
constructed using Boolean logic
 Also holds for functions with more arguments
 Functions can be put in table form or in
formula form

TU-Delft
in1200/04-PDS
16
Gates
We use basic components to represent
primary logic operations (called gates)
 Components are made from transistors

x
y
x+y
OR
x
x
y
x.y
AND
x
INVERT
TU-Delft
in1200/04-PDS
17
Networks of gates

We can make networks of gates
x
x.y+x.y
y
xy
EXOR
TU-Delft
in1200/04-PDS
18
Sum of product form
x
y
f
0
1
0
1
0
0
1
1
0
1
1
1
f = x.y +x.y +x.y
simplify
f
x
y
TU-Delft
in1200/04-PDS
19
Minimization of expressions
Logic expressions can often be minimized
 Saves components
 Example:

f = x.y.z + x.y.z + x.y.z + x.y.z
f = x.y(z +z) + (x +x)y.z
f = x.y.1 + 1.y.z
f = x.y + y.z
TU-Delft
in1200/04-PDS
20
Karnaugh maps (1)

Alternative geometrical method
xy
vw
00
00
01
11
10
1
1
0
1
iuh
01
1
1
0
1
11
0
0
0
0
10
1
1
1
0
f = v.x + v.w.x + v.w.y + v.x.y
TU-Delft
in1200/04-PDS
21
Karnaugh maps (2)
Different drawing
y
xy
w
v
x
TU-Delft
in1200/04-PDS
22
don’t cares
Some outputs are indifferent
 Can be used for minimization

TU-Delft
x
y
f
0
1
0
1
0
0
1
1
0
1
d
1
in1200/04-PDS
23
NAND and NOR gates
NAND and NOR gates are universal
 They are easy to realize

x + y = x.y
x.y = x + y
de Morgans Law
TU-Delft
in1200/04-PDS
24
Delay

Every network of gates has delays
transition time
1
input
0
1
output
propagation delay
0
time
TU-Delft
in1200/04-PDS
25
Packaging
Vcc
Gnd
TU-Delft
in1200/04-PDS
26
Making functions
nand gates
A
B
A,B
Y

delay
TU-Delft
Y
ADD
time
in1200/04-PDS
27
Functional Units
It would be very uneconomical to construct
separate combinatorial circuit for every
function needed
 Hence, functional units are parameterized
 A specific function is activated by a special
control string F

TU-Delft
in1200/04-PDS
28
Arithmetic and Logic Unit
A
B
F
add
subtract
compare
or
TU-Delft
f1 f0
0
0
1
1
Y
F
0
1
0
1
F
A
B
F
F
Y
in1200/04-PDS
29
Repeated operations
Y : = Y + Bi, i=1..n
 Repeated addition requires feedback
 Cannot be done without intermediate storage
of results

B
Y
F
F
TU-Delft
in1200/04-PDS
30
Registers
B
Y
F
F
TU-Delft
= storage element
in1200/04-PDS
31
SR flip flop

Storage elements are not transient and are
able to hold a logic value for a certain period
of time
R
S
TU-Delft
Qa
Qb
S
R Qa Qb
0
0
0
1
0
1
1
0
1
0
1
1
0
0
0/1 1/0
in1200/04-PDS
32
Clocks
In many circuits it is very convenient to have
the state changed only at regular points in
time
 This makes design of systems with memory
elements easier
 Also reasoning about the systems behavior is
easier
clock period
 This is done by a clock signal

TU-Delft
in1200/04-PDS
33
D flip flop

D flip flop samples at clock is high and stores
if clock is low
Qn
C
D
TU-Delft
D
Qn+1
0
0
1
1
Qn
in1200/04-PDS
34
Edge triggered flip flops
In reality most systems are built such that the
state only changes at rising edge of the clock
pulse
 We also need a control signal to enable a
change

state change
TU-Delft
in1200/04-PDS
35
Basic storage element
enables a state change
I
R/W
C
C
C
D
Q
O
I
R/W
O
time
TU-Delft
in1200/04-PDS
36
4-bit register
I
R/W
I
I
I
C
C
TU-Delft
D
C
D
C
D
C
D
Q
Q
Q
Q
O
O
O
O
in1200/04-PDS
37
Some basic circuits
A
m
B
Y = A if m=1
Y = B if m=0
MPLEX
Y
Y
Decoder
Only output yA= 1, rest is 0
A
TU-Delft
in1200/04-PDS
38
Decoder
Y
Decoder
Only output yA= 1, rest is 0
A
a1
3
2
1
a1 a2 #y
0 0 0
0 1
1
1 0
2
1 1
3
0
a2
TU-Delft
in1200/04-PDS
39
Multiplexer
A
m
B
Y = A if m=1
Y = B if m=0
MPLEX
Y
b
y
a
m
TU-Delft
in1200/04-PDS
40
Memory
Din
REG1
decoder
Address
R/W
TU-Delft
mplex
Dout
REG2
REG3
REG4
in1200/04-PDS
41
Counter
preset
R/W
MPLEX
REG
INC
0001
output
TU-Delft
in1200/04-PDS
42
Sequential circuits
The counter example shows that systems have
state
 The state of such systems depend on the
current inputs and the sequence of previous
inputs
 The state of a system is the union of the
values of the memory elements of that system

TU-Delft
in1200/04-PDS
43
State diagrams
We call the change from one state to another
a state transition
 Can be represented as a state diagram

code
S0
S1
S2
TU-Delft
0
0
1
0
0
1
0
0
in1200/04-PDS
state
S0
S1
S2
S0
44
Conditional Change
x=0
S0
x=1
Present
state
Next
x=0
State
x=1
S0
S1
S2
S1
S2
S2
S2
S0
S0
S1
S2
TU-Delft
in1200/04-PDS
45
Coding of State
TU-Delft
Present
state
yz
00
Next
x=0
YZ
01
State
x=1
YZ
10
01
10
10
10
00
00
in1200/04-PDS
46
Put in Karnaugh map
y
x
0
1
0
0
Y = x.y + z
Y
d
d
1
1
y
z
Z = x.y.z
= (x+z).y
TU-Delft
x
1
0
0
0
Z
d
d
0
0
z
in1200/04-PDS
47
Scheme
x.y+z
x.y
x
x+z
y
TU-Delft
Q D
Q D
Z
z
(x+z).y
Y
in1200/04-PDS
48
General scheme
Outputs
Inputs
Combinatorial Logic
Delay elements
TU-Delft
in1200/04-PDS
49
Procedure FST
1.
2.
3.
4.
5.
Make State Diagram
Make State Table
Give States binary code
Put state update functions in Karnaugh Map
Make combinatorial circuit to realize functions
TU-Delft
in1200/04-PDS
50