binary representation dd_vahid_sampleslides_Feb06.ppt

logic circuit

1. 1
Digital Design
Copyright © 2006
Frank Vahid
a
0
0
1
1
b
0
1
0
1
F
Inputs Output
a'b'a' b
Converting among Representations
•Can convert from any representation to
any other
•Common conversions
–Equation to circuit (we did this earlier)
–Truth table to equation (which we can
convert to circuit)
•Easy -- just OR each input term that should
output 1
–Equation to truth table
•Easy -- just evaluate equation for each input
combination (row)
•Creating intermediate columns helps
a
0
0
1
1
b
0
1
0
1
F
1
1
0
0
InputsOutputs
F = sum of
a’b’
a’b
Term
F = a’b’ + a’b
c
0
1
0
1
0
1
0
1
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
F
0
0
0
0
0
1
1
1
Q: Convert to equation
a
F = ab’c + abc’ + abc
ab’c
abc’
abc
1
1
0
0
1
0
0
0
0
1
0
0
a
Q: Convert to truth table: F = a’b’ + a’b

2. 2
Digital Design
Copyright © 2006
Frank Vahid
Decoder Example
•New Year’s Eve
Countdown Display
–Microprocessor counts
from 59 down to 0 in
binary on 6-bit output
–Want illuminate one of 60
lights for each binary
number
–Use 6x64 decoder
•4 outputs unused
d0
d1
d2
d3
i0
i1
i2
i3
i4
i5
e
6x64
dcd
d58
d59
d60
d61
d62
d63
0
Happy
New Year
1
2
3
58
59
a
0
1
0
0
0
0
0
0
1
0
0
0
2 21
1
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0 0

3. 3
Digital Design
Copyright © 2006
Frank Vahid
Controller Design: Laser Timer Example
•Step 1: Capture the FSM
–Already done
•Step 2: Create architecture
–2-bit state register (for 4 states)
–Input b, output x
–Next state signals n1, n0
•Step 3: Encode the states
–Any encoding with each state
unique will work
x=1 x=1 x=1
x=0
b
b’
01
00
10 11On2On1
Off
On3
a
a
Inputs: b; Outputs: x
Combinational
logic
State register
s1s0
n1
n0
xb
clk
F
S
M
i
n
p
u
t
s
F
S
M
o
u
t
p
u
t
s

4. 4
Digital Design
Copyright © 2006
Frank Vahid
Controller Design: Laser Timer Example (cont)
•Step 4: Create state table
x=1 x=1 x=1
x=0
b
b’
01
00
10 11On2On1
Off
On3
Inputs: b; Outputs: x
Combinational
logic
Stateregister
s1s0
n1
n0
xb
clk
F
S
M
in
p
u
t
s F
S
M
o
u
t
p
u
t
s
a

5. 5
Digital Design
Copyright © 2006
Frank Vahid
Controller Design: Laser Timer Example (cont)
•Step 5: Implement
combinational logic
Combinational
logic
Stateregister
s1s0
n1
n0
xb
clk
F
S
M
in
p
u
t
s F
S
M
o
u
t
p
u
t
s
a
x = s1 + s0 (note from the table that x=1 if s1 = 1 or
s0 = 1)
n1 = s1’s0b’ + s1’s0b + s1s0’b’ + s1s0’b
n1 = s1’s0 + s1s0’
n0 = s1’s0’b + s1s0’b’ + s1s0’b
n0 = s1’s0’b + s1s0’

6. 6
Digital Design
Copyright © 2006
Frank Vahid
Controller Design: Laser Timer Example (cont)
•Step 5: Implement
combinational logic (cont)
a
x = s1 + s0
n1 = s1’s0 + s1s0’
n0 = s1’s0’b + s1s0’
Combinational
logic
Stateregister
s1s0
n1
n0
xb
clk
F
S
M
in
p
u
t
s F
S
M
o
u
t
p
u
t
s
n1
n0
s0s1
clk
Combinational Logic
State register
b
x

7. 7
Digital Design
Copyright © 2006
Frank Vahid
Register Example using the Load Input:
Weight Sampler
•Scale has two displays
–Present weight
–Saved weight
–Useful to compare
present item with previous
item
•Use register to store
weight
–Pressing button causes
present weight to be
stored in register
•Register contents
always displayed as
“Saved weight,” even
when new present
weight appears
Scale
Saved weight
Weight Sampler
Present weight clk
b
Save
I3I2I1I0
Q3Q2Q1Q0
load3 pounds
0011
0011
3 pounds
0010
2 pounds
1 a

8. 8
Digital Design
Copyright © 2006
Frank Vahid
0
0
0
cos
FA
1 1 1
1 1
0 10
ciba
cos
FA
ciba
10
cos
FA
ciba
0 0 0
11
cos
FA
ciba
(d)
Output after 8ns (4 FA delays)
Carry-Ripple Adder’s Behavior
0
cos
FA
0 0 1
co1
0 10
ciba
cos
FA
ciba
10
cos
FA
ciba
00 1 0 0
11
cos
FA
ciba
(b)
10 1
00 0
0
1
01
1
Outputs after 4ns (2 FA delays)
0
0
cos
FA
1 1
0 1
co2
0 10
ciba
cos
FA
ciba
10
cos
FA
ciba
0 0
11
0
cos
FA
ciba
(c)
Outputs after 6ns (3 FA delays)
a
0111+0001
(answer should be 01000)
1
Correct answer appears after 4 FA delays

9. 9
Digital Design
Copyright © 2006
Frank Vahid
Magnitude Comparator
•How does it
work?
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
Igt
Ieq
Ilt
Stage3
a3b3
ab
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
Stage2
a2b2
ab
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
Stage1
a1b1
ab
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
AgtB
AeqB
AltB
Stage0
a0b0
11 00 10 11
ab
(a)
=
0
1
0
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
Igt
Ieq
Ilt
Stage3
a3b3
ab
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
Stage2
a2b2
ab
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
Stage1
a1b1
ab
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
AgtB
AeqB
AltB
Stage0
a0b0
11 00 10 11
ab
(b)
0
1
0
=
0
1
0
1011 = 1001 ?
0
1
0
Ieq=1 causes this
stage to compare
a

10. 10
Digital Design
Copyright © 2006
Frank Vahid
Magnitude Comparator
•Final answer
appears on the
right
•Takes time for
answer to “ripple”
from left to right
•Thus called
“carry-ripple
style” after the
carry-ripple
adder
–Even though
there’s no
“carry”
involved
1011 = 1001 ?
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
Igt
Ieq
Ilt
Stage3
a3b3
ab
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
Stage2
a2b2
ab
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
Stage1
a1b1
ab
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
AgtB
AeqB
AltB
Stage0
a0b0
11 00 10 11
ab
(c)
0
1
0
1
0
0
>
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
Igt
Ieq
Ilt
Stage3
a3b3
ab
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
Stage2
a2b2
ab
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
Stage1
a1b1
ab
in_gt
in_eq
in_lt
out_gt
out_eq
out_lt
AgtB
AeqB
AltB
Stage0
a0b0
11 00 10 11
ab
(d)
0
1
0
0
1
0
a

11. 11
Digital Design
Copyright © 2006
Frank Vahid
Counter Example: Light Sequencer
•Illuminate 8 lights from right
to left, one at a time, one per
second
•Use 3-bit up-counter to
counter from 0 to 7
•Use 3x8 decoder to
illuminate appropriate light
•Note: Used 3-bit counter
with 3x8 decoder
–NOT an 8-bit counter – why
not?
lights
000001010
3-bit up-counter
cnt
tc c2c1c0
3x8 dcd i2i1i0
unused
1
clk
(1Hz)
d7d6d5d4d3d2d1d0
a

12. 12
Digital Design
Copyright © 2006
Frank Vahid
RTL Example: Bus Interface
WaitMyAddress
Inputs: rd (bit); Q (32 bits); A, Faddr (4 bits)
Outputs: D (32 bits)
Local register: Q1 (32 bits)
rd’
rd
SendData
D = “Z”
Q1 = Q
(A = Faddr)
and rd
((A = Faddr)
and rd)’
D = Q1
•Step 2: Create a datapath
(a) Datapath inputs/outputs
(b) Instantiate declared registers
(c) Instantiate datapath components and
connections
Datapath
Bus interface
Q1_ld
ld
Q1
F Qaddr
44 32
A
D_en
A_eq_Faddr
= (4-bit)
32
32
D
a

13. 13
Digital Design
Copyright © 2006
Frank Vahid
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
S0 S1S2
S1
S2
S3
State Reduction Example
•Given FSM on the right
–Step 1: Mark state pairs having
different outputs as nonequivalent
S0 S1S2
S1
S2
S3
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
S0 S1S2
S1
S2
S3
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
S0 S1S2
S1
S2
S3
S0 S1S2
S1
S2
S3
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
S0 S1S2
S1
S2
S3
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
S0 S1S2
S1
S2
S3
S0 S1S2
S1
S2
S3
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
a

14. 14
Digital Design
Copyright © 2006
Frank Vahid
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
S0 S1S2
S1
S2
S3
State Reduction Example
•Given FSM on the right
–Step 1: Mark state pairs having
different outputs as nonequivalent
–Step 2: For each unmarked state
pair, write the next state pairs for the
same input values
S0 S1S2
S1
S2
S3
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
x=0
(S2, S2)
x’
x’
x=1
(S2, S2)
S0 S1S2
S1
S2
S3
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
x
x
(S3, S1)
x=0
(S2, S2)
S0 S1S2
S1
S2
S3
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
(S3, S1)
x’
x’
(S0, S2)
x=1
S0 S1S2
S1
S2
S3
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
(S0, S2)
x x
(S3, S1)
x=0
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
(S2, S2)
S0 S1S2
S1
S2
S3
(S3, S1)
(S0, S2)
(S3, S1)
x’ x’
(S0, S2)
x=1
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
(S2, S2)
S0 S1S2
S1
S2
S3
(S3, S1)
(S0, S2)
(S3, S1)
(S0, S2)
x
x
(S3, S3)
S0 S1
y=0 y=1
S2
y=1
S3
y=1
x
x x
x’
x’
xx’ x’
Inputs: x; Outputs: y
(S2, S2)
S0 S1S2
S1
S2
S3
(S3, S1)
(S0, S2)
(S3, S1)
(S0, S2)
(S3, S3)
a

15. 15
Digital Design
Copyright © 2006
Frank Vahid
State Encoding: One-Hot Encoding
•One-hot encoding
–One bit per state – a bit being ‘1’
corresponds to a particular state
–Alternative to minimum bit-width
encoding in previous example
–For A, B, C, D: A: 0001, B: 0010, C:
0100, D: 1000
•Example: FSM that outputs 0, 1, 1, 1
–Equations if one-hot encoding:
•n3 = s2; n2 = s1; n1 = s0; x = s3 +
s2 + s1
–Fewer gates and only one level of
logic – less delay than two levels, so
faster clock frequency
00
01
Inputs: none; Outputs: x
x=0
x=1
A
B
11
10
D
C
x=1
x=1
1000
0100
0001
0010
clk
s1
n1
x
s0
n0
State register
clk
n0
s3s2s1s0
n1
n2
n3
State register
x
8
6
4
2
2341
delay (gate-delays)
one-hot
binary
a