Y - TU Delft
Download
Report
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
xy = 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
xy = 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
xy
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