Ilovepdf Merged
Ilovepdf Merged
Ilovepdf Merged
bn-1 bn-2 b1 b0
Sign Magnitude
• A problem: Two different representations for zero.
+0: 0 00..000 and -0: 1 00..000
• Basic idea:
– Positive numbers are represented exactly as in sign-magnitude form.
– Negative numbers are represented in 1’s complement form.
• How to compute the 1’s complement of a number?
– Complement every bit of the number (1 to 0, and 0 to 1).
– Most Significant Bit (MSB) will indicate the sign of the number (0: positive, 1:
negative).
d) The sign bit can be copied as many times as required in the beginning to extend
the size of the number (called sign extension).
X = 00101111 (8-bit number, value = +47) X = 10100011 (8-bit number, value = -93)
Sign extend to 32 bits: Sign extend to 32 bits:
00000000 00000000 00000000 00101111 11111111 11111111 11111111 10100011
3 :: 0011
Assume 4-bit representations.
-5 :: 1010
1101 = -2 Since there is no carry, the result is
negative.
1101 is the 1’s complement of
0010, that is, it represents –2.
6 :: 0110
Assume 4-bit representations.
-2 :: 1110
1 0100 = +4 Presence of carry indicates that
the result is positive.
3 :: 0011
-5 :: 1011 Assume 4-bit representations.
1110 = -2 Since there is no carry, the result is
negative.
1110 is the 2’s complement of
0010, that is, it represents –2.
+ + + + + +
1 1 1 0 1 1
g5 g4 g3 g2 g1 g0
8 1 1 1 0 0 0 0 p1 1 0 1 0 1 0 1
9 0 0 1 1 0 0 1
1 2 3 4 5 6 7 8 9
b1 b2 b3 b4 b5 b6 b7 b8 b9 p4 0 0 0 0 0 0 0 1 1
p1 p2 m1 p3 m2 m3 m4 p4 m5 p3 0 0 0 1 1 1 1 0 0
p2 0 1 1 0 0 1 1 0 0
p1 1 0 1 0 1 0 1 0 1
A A’
A
A.B
B
A
A+B
B
A
(A.B)’
B
A
(A+B)’
B
A
AB
B
A
(AB)’
B
Switch open:
• No current flows.
• Light is OFF.
Switch closed:
• Current flows.
V
• Light is ON.
Digital Value 0 1
Noise Margin
Gate = 1 Gate = 0
Gate = 0 Gate = 1
In Out
0 1
1 0
A B Out
0 0 1
0 1 1
1 0 1
1 1 0
C D Out
0 0 1
0 1 0
1 0 0
1 1 0
A B Out
0 0 0
0 1 0
1 0 0
1 1 1
C D Out
0 0 0
0 1 1
1 0 1
1 1 1
4-to-1 multiplexer:
• If S0 = 0 and S1 = 0, then Z = A
2-to-1 multiplexer:
• If S0 = 1 and S1 = 0, then Z = B
• If S0 = 0, then Z = A • If S0 = 0 and S1 = 1, then Z = C
• If S0 = 1, then Z = B • If S0 = 1 and S1 = 1, then Z = D
MUX
C-1 C-1
Control Cross Port
Signal (A) SOA-2 (A.B’)
10-12 nm
• Example:
– f (x, y, z) = x’.y + x.y.z True minterms are: x’.y.z’, x’.y.z, x.y.z
– f (x, y, z) = (x + y) . (y +z) True maxterms are: x+y+z, x+y+z’, x’+y+z
• We can derive two canonical representations directly from the truth table:
a) Canonical sum-of-products (also called disjunctive normal form)
b) Canonical product-of-sums (also called conjunctive normal form)
BC BC
A 00 01 11 10 A 00 01 11 10
0 0 0 1 3 2
1 1 4 5 7 6
BC
A 00 01 11 10
0 1 1
1 1 1
BC
A 00 01 11 10
0 1 1 1 1
1 1
BC
A 00 01 11 10
0 1 1 1 1
1 1 1
BC
A 00 01 11 10
0 1 1 1
1 1 1 1
BC BC
A 00 01 11 10 A 00 01 11 10
0 1 1 0 1
1 1 1 1 1 1 1
CD CD
AB 00 01 11 10 AB 00 01 11 10
00 00 0 1 3 2
01 01 4 5 7 6
11 11 12 13 15 14
10 10 8 9 11 10
CD
AB 00 01 11 10
00 1
01 1 1 1
11 1
10 1
CD
AB 00 01 11 10
00 1 1
01 1 1 1
11 1 1
10 1
CD
AB 00 01 11 10
00 1 1
01 1 1
11 1 1
10 1 1
CD
AB 00 01 11 10
00 1 1
01 1 1
11 1 1
10 1 1
CD
AB 00 01 11 10
00 1
01 1 1 1
11 1 1 1
10 1
A1
A0 S2
2‐bit Adder S1
B1 S0
B0
CD
AB 00 01 11 10
00 1 X
01 1
11 1 1 X X
10 1 1 X
CD
AB 00 01 11 10
00 1 X
01 X 1
11 X
10 X 1
10 1 1
01 1 1
11 1
10 1
CDE CDE
AB 000 001 011 010 110 111 101 100 AB 000 001 011 010 110 111 101 100
00 00 0 1 3 2 6 7 5 4
01 01 8 9 11 10 14 15 13 12
11 11 24 25 27 26 30 31 29 28
10 10 16 17 19 18 22 23 21 20
2. The set of all essential prime implicants must be contained in any irredundant
sum‐of‐products expression.
3. Any prime implicant covered by the sum of the essential prime implicants
must not be contained in an irredundant sum‐of‐products expression.
10 1 10 0 0 0
A S
B FA
Cin Cout
1111110 Carry
0111111 Number A
+ 0000001 Number B
1000000 Sum S
FAn-1
Cn-1
…… C3
FA2
C2
FA1
C1
FA0
C0
Delay for C1 = 2δ
Cn Sn-1 S2 S1 S0 Delay for C2 = 4δ
Delay for Cn-1 = 2(n-1)δ
Two numbers: An-1…A2A1A0 and Bn-1…B2B1B0 Delay for Cn = 2nδ
Input carry: C0
Delay for S0 = 3δ
Sum: Sn-1…S2S1S0
Delay for S1 = 2δ + 3δ = 5δ
Output carry: Cn
Delay for S2 = 4δ + 3δ = 7δ
Delay for Sn-1 = 2(n-1)δ + 3δ = (2n+1) δ
Delay is proportional to n
FAn-1
Cn-1
…… C3
FA2
C2
FA1
C1
FA0
C0 = 1
Cn Sn-1 S2 S1 S0
…
Sn-1 S2 S 1 S0
i-1 i i
Ci+1 = Gi + Gk Pj + C0 Pj
k=0 j=k+1 j=0
C3
P2
G2
C2 P1
G1
P0
C1 G0
C0
Gi and Pi Generator 3δ
G3 P3 G2 P2 G1 P1 G0 P0
C3 C2 C1 C0
C4 Total Time = 8δ
S3 S2 S1 S0
Problem: Carry propagation between modules still slows down the adder
n TCLA TRCA
4 8δ 9δ
16 10δ 33δ TCLA = (6 + 2 log4 n ) δ
32 12δ 65δ
64 12δ 129δ
TRCA = (2n + 1) δ
128 14δ 257δ
256 14δ 513δ
A set of full adders generate carry The sum and carry vectors are
and sum bits in parallel added later (with proper shifting)
Cn-1 Sn-1 C2 S2 C1 S1 C0 S0
The carry input of the full adder is used as the third input
m=3
CSA m=6
CSA
m=4
CSA CSA
CSA
S0 S1 Sm-
1
D0
2-to-1 f
D1 MUX
S0
f = S0’.D0 + S0.D1
S0 S1 1 1 X X X 0 0
1 1 X X X 1 1
2-to-1 f
S0 MUX
D2
2-to-1
D3 MUX S1
S0
Dn-1
S0 S1 Sm-
1
D0
IN 1-to-2
DEMUX D1
S0
D0 = S0’.IN
D1 = S0.IN
D0
IN 1-to-2 D1
DEMUX D2
D3
S0 S1
D0 = S1’.S0’.IN D2 = S1.S0’.IN
D1 = S1’.S0.IN D3 = S1.S0.IN
D1 D0 f0 f1 f2 f3
f0
D0 0 0 1 0 0 0
2-to-4 f1
f2 0 1 0 1 0 0
decoder
D1 1 0 0 0 1 0
f3
1 1 0 0 0 1
f0 = D1’.D0’ f2 = D1.D0’
f1 = D1’.D0 f3 = D1.D0
G D1 D0 f0 f1 f2 f3
f0 0 0 0 1 0 0 0
D0
2-to-4 f1 0 0 1 0 1 0 0
decoder f2 0 1 0 0 0 1 0
D1
f3
0 1 1 0 0 0 1
1 X X 0 0 0 0
G f0 = D1’.D0’.G’ f2 = D1.D0’.G’
f1 = D1’.D0.G’ f3 = D1.D0.G’
Decoders
f4
2-to-4 f5
decoder f6
f7 f8
2-to-4 2-to-4 f9
decoder f10
decoder f1
1
f1
2-to-4 f21
decoder f31
f41
5
2-to-4
y z
f0 f1
w f1 f2
x f2 f3
y f3 f4
z f4
BCD-to-Decimal f5
Decoder f5
f6
f6
Enable f7
f7
f8
f8
f9
f9
Enable
(c) Logic diagram.
A
A
x1 B F
x2 BCD to C G B
7-segment D
x3 E
decoder
F
x4 G E C
A1A2
B1B2 00 01 11 10 2-bit Comparator
00 EQ GT GT GT
01 LT EQ GT GT
GT EQ LT
11 LT LT EQ LT GT = A1A2B2’ + A2B1’B2’ + A1B1’
10 LT LT GT EQ EQ = A1’A2’B1’B2’ + A1’A2B1’B2 + A1A2’B1B2’ + A1A2B1B2
LT = A2’B1B2 + A1’A2’B2 + A1’B1
1 0 0 1 0 0 1 1
Low High
child child
b’c’ + bc c
Variable ordering: a, b, c
b b
c c c c
1 0 0 1 0 1 0 1
x x x
y z y z y z
x x x
y z y z y z
y y
x2 x2 x2 x2
0 1 0 1 0 1 0 1
x3 x3 x3 x3 x3 x3 x3
x3 1 0 0
0 1 0 1 0 1 0 1 0 1
1 1
0 1 0 1 0 1 1 1 0
0 1
x1 1 x1
0 1
x2 x2 0
1 0 x2
0
0
x3 1 1 x3 1 1
0 0
0 1 0 1
• Complementation.
– Given a BDD for a function f, the BDD for f′ can be obtained by simply interchanging
the terminal nodes.
• Equivalence check.
– Two functions f and g are equivalent if their BDDs (under the same variable
ordering) are the same.
a b a b
h x h x h x
ah + bh = (a+b)h
y z y z y z
f f
x x
0 1
f g
f g
0 1
h
g
h
f g f
An example ===>
a ab′
0 1
b a
c d
c b
d
0 1
0 1
= 1 ⊕ x1 ⊕ x2 ⊕ x3
x2 w2 T y
wn
xn
x1
0 0 1 1 1
-1 0 1 0 2 1
x2 2 _
1
2
y 0 1 1 3 1
1 1 0 0 -1 0
x3
1 0 1 0 0
1 1 0 1 1
1 1 1 2 1
• A straightforward approach:
– Obtain inequality constraints from each row of the truth table.
– Solve the set of 2n simultaneous inequalities.
• A property:
– Let f (x1,x2, …,xn) be realized by V1 = {w1,w2, …,wj, …,wn;T}.
– If xj is complemented, f can be realized by V2 = {w1,w2, …,-wj, …,wn;T-wj} with inputs
x1, x2, …, xj’, …, xn .
– From V1:
Vin1 = Vout2
S’ S R Q Q’
0 0 No change No change
0 1 0 1
1 0 1 0
R’ 1 1 ? ? Invalid
S’
E S R Q Q’
0 X X NC NC
1 0 0 NC NC
1 0 1 0 1
1 1 0 1 0
1 1 1 ? ?
E D Q Q’
0 X NC NC
1 0 0 1
1 1 1 0
CLK
CLK
D Q Characteristic equation:
Q(t+1) = D
CK
Q’
Negative edge triggered
A simple solution.
Width of the pulse depends on
the delay of the NOT gate. Drawback: circuit-
We can use any odd number of dependent delay
NOT gates.
• All these taken together determines the maximum speed with which the
circuit can operate.
– Typically specified in terms of the clock frequency.
• Setup time (tsetup): Amount of time the input to a flip-flop must be stable before
the clock transitions high (for positive-edge triggered), or transitions low (for
negative-edge triggered).
• Hold time (thold): Amount of time the input to a flip-flop must be stable after the
clock transitions high (for positive-edge triggered), or transitions low (for negative-
edge triggered).
D Q tw
CLK
CLK Tp-lh
Q Tp-hl
IN
tsetup tsetup
CLK
Q0
tp-lh tp-hl
Q1
The correct
scenario CLK
thold thold
• Ideally, the clock signal should arrive all flip-flops at exactly the same time.
– In practice, clock skew exists.
• It tskew denotes the maximum possible clock skew, then the minimum time
period should also include this tolerance.
– Tmin = tpFF + tpCOMB + tsetup + tskew
– Clock frequency can reduce further.
Delay of NOT = 1
Delay of AND, OR = 2
X
B
Delay of NOT = 1
Delay of NAND, NOR = 2
• Example:
– A circuit to detect 3 or more 1’s in a serial bit stream.
– The bits are applied serially in synchronism with a clock.
– The output will become 1 whenever it detects 3 or more consecutive 1’s in the
stream.
PI NS NS Output Mealy
F/F PS P
Logic Logic Machine
O
PI NS NS PS Output
P Moore
F/F
Logic Logic Machine
O
0/0 0/1
1/1
X
Z EVEN ODD
clk
Initial 1/0
state
reset
1/0
1/0 0/0
0/0 1/0 1/0
S0 S1 S2 S3
0/0
reset 0/1
S1 S6 S2 S3, 011
φ/010 φ/110 S3 S4, 100
S2 S5 S4 S5, 101
φ/011 φ/101 S5 S6, 110
S6 S7, 111
S3 S4
φ/100 S7 S0, 000
…….. φ/0000
φ/0000
S0 S3 S6 S12 S9 S10
φ/0011 φ/0110 φ/1100 φ/1001 φ/1010
φ/100
Switching Circuits & Logic Design 12
END OF LECTURE 37
00/0 01/0
NS, Z
01/1 10/0 PS
10/1 11/0 11/1 X = 00 X = 01 X = 10 X = 11
A B A A, 0 A, 1 A, 1 B, 0
00/1 B A, 1 B, 0 B, 0 B, 1
NS, Z PS NS Output Z
PS
X = 00 X = 01 X = 10 X = 11 X1X2 00 01 10 11 00 01 10 11
0 0, 0 0, 1 0, 1 1, 0 0 0 0 0 1 0 1 1 0
1 0, 1 1, 0 1, 0 1, 1 1 0 1 1 1 1 0 0 1
1 11 1 1 1 1 1 1
y Y
Y = X1X2 + X1y + X2y Z = X1 ⊕ X2 ⊕ y
y NS (Y) Output Z
00 01 10 11 00 01 10 11
0 0 0 0 1 0 1 1 0
1 0 1 1 1 1 0 0 1
1 1 0 0X 0X 0X 10 0 1 1 0
1 10 00 00 00 1 0 0 1
R=0
0/0
0/1
PS NS Output Z y1y2 T1 T2 Z
X=0 X=1 X=0 X=1 X=0 X=1 X=0 X=1
00 01 00 0 0 00 01 00 0 0
01 01 10 0 0 01 00 11 0 0
10 01 11 0 0 10 11 01 0 0
11 01 00 1 0 11 10 11 1 0
1 1 1 1 1 1 1 1 1
T1 = X’ y1 + X y2 T2 = X’ y2’ + y1 y2’ + X y2 Z = X’ y1 y2
PS NS Output Z y1y2 J1 K1 J2 K2 Z
X=0 X=1 X=0 X=1 X=0 X=1 X=0 X=1
00 01 00 0 0 00 0X 1X 0X 0X 0 0
01 01 10 0 0 01 0X X0 1X X1 0 0
10 01 11 0 0 10 X1 1X X0 1X 0 0
11 01 00 1 0 11 X1 X0 X1 X1 1 0
C x x C x x After first
Initial
pass
A-D A-F A-F
D x D C-E x
C-E E-H E-H
C-E
E x x x E x x A-D x
A-D
E-F C-F E-F C-F
F x x x F x x x
B-D A-B B-D A-B
B-D A-B B-D A-B
G B-F x x x G B-F x x x
C-H E-H C-H E-H
C-E C-F C-E C-F
H x x x A-G x H x x x A-G x
D-G B-G D-G B-G
A B C D E F G A B C D E F G
PS NS, z PS NS, z
X =0 X=1 X =0 X=1
A B, 0 A, 0 S0 S3, 0 S1, 0
B C, 0 D, 1 S1 S3 0 S0, 1
C A, 0 C, 1 S2 S0, 0 S2, 1
D C, 0 B, 0 S3 S2, 0 S3, 0
N1 N2
• Assume that circuit A can only generate two possible output sequences, x = 100 and 110.
• After the sequence is received, the output of B will be z = 0 if 100 was received, and z = 1
if 110 was received.
– Assume that circuit C ignores the value of z at all other times.
0,0 S2
PS NS, z
t t1 t2 t0 t1 t2 0,-
x=0 x=1 1,-
0 S0 S1
x= 1 0 0 z - - 0 S0 -, - S1, - 1,-
= S1 S2, - S3, -
0,1 S3
1 input/output
Possible 1 0 - -
sequences 1 S2 S0, 0 -, -
S3 S0, 1 -, -
Switching Circuits & Logic Design 7
• We can fill up the don’t cares suitably, so that the number of states can be reduced
using row matching.
0,0 1,-
0,0 S2 1,-
S1 x S0 S1
0,-
1,- 0,1
S0 S1 S2 ✓ x
1,-
0,1 S3 S3 x S2-S0 x
PS NS, z
PS NS, z S0 S1 S2 x=0 x=1
x=0 x=1
S0, S2 are equivalent S0 S0, 0 S1, -
S0 S0, 0 S1, -
S1, S3 are equivalent S1 S0, 1 S1, -
S1 S2, 1 S3, -
S2 S0, 0 S1, -
S3 S0, 1 S3, -
Switching Circuits & Logic Design 8
END OF LECTURE 41
4
Q
CLK
To clock inputs of the flip-flops
LOAD
D1 D Q Q1
CLK
CLR
ENABLE
’
CLR
’
D1 X Q1
Dk X Qk
CLK/LOAD
Dk X X Qk
CLK/LOAD ENABLE
X
Refresh operation is
CLK’ carried out in every
clock period when
D1 X X Q1 CLK = 0.
CLK/LOAD ENABLE
CLK
SI
Q1 0 1 1 0 1
Q2 1 0 1 1 0
Q3 0 1 0 1 1
Q4 1 0 1 0 1
CLK
Q1
Q2
Q3
Q4’
CLK
Clocks 1 2 3 4 5 6 7 8 9
Q1 0 1 1 1 1 0 0 0 0 … … A 4-bit Johnson counter.
Q2 0 0 1 1 1 1 0 0 0 … … Assume the initial state
Q3 0 0 0 1 1 1 1 0 0 … … Q1Q2Q3Q4 = 0 0 0 0.
Q4 0 0 0 0 1 1 1 1 0 … …
D1 Q1 D2 Q2 D3 Q3 D4 Q4
CLK
S1 S1 S1
MUX MUX MUX
S0 S0 S0
D1 Q1 D2 Q2 D3 Q3
CLK
A 3-bit universal shift register
D1 Q1 D2 Q2 D3 Q3 D4 Q4
CLK
CLK
CLK pulses 0 1 2 3 4 5 6 7 8 9 10 11
Q1 0 1 1 1 1 0 1 0 1 0 0 0 …
Q2 0 0 1 1 1 1 0 0 0 1 0 0 …
Q3 0 0 0 1 1 1 1 1 0 0 1 0 …
Q4 1 0 0 0 1 1 1 1 1 0 0 1 …
LdP LdB
LdA A P B
clrP decB
X Y
COMP
ADDER eqz
done
eqz
clk
LdA A B LdB
Aout Bout
X lt gt eq Y
DATA PATH data_in
SUBTRACTOR
SubOut
clk
< > S2 S5
Aout : Bout
= LT
X = Bout X = Aout GT
LT GT
S3 Y = Aout done = 1 Y = Bout S4
B = SubOut A = SubOut S3 GT S4
S5 LT
Q0 Q1 Q2 Q3
CLK
Q0
Q1
Q2
Q3
1 T0 Q0 1 T1 Q1 1 T2 Q2
CLK
CLR’ CLR’ CLR’
Q0 Q1 Q2
CLK
Q0
Q1
Q2
1 T0 Q0 1 T1 Q1 1 T2 Q2 1 T3 Q3
CLK
Q0 Q1 Q2 Q3
f/M
VOUT
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011
D
Digital Input Signal
D/A Converter
Analog Output
Digital Input
Analog Output
Digital Input
-1/2*VLSB
Settling
Time
Time
D0
8R
D0 D1 D2 D3 Voltage
Follower
2R 2R 2R 2R
+ VOUT
2R R R R -
2R
Vx = V / 2
2R 2R 2R 2R
Vx Vx
2R R R R 2R
2R 2R 2R 2R 2R 2R
Vx Vx
2R R R R 2R R
GND GND
Thevenin’s Vx = V / 4
theorem 2R 2R
+V/2 Vx +V/2 Vx
R R 2R
GND
Vx = V / 8
2R
+V/4 Vx
2R
2R 2R 2R 2R 2R 2R 2R
Vx +V/2 Vx
2R R R R 2R R R
2R 2R 2R 2R
VA
+ VOUT
2R R R R -
Thus, VA α D.
For an N-bit DAC, the contribution of the k-th input Dk on the output voltage will be V / 2N-k
2000
1000
0
0.000 0.001 0.002 0.003 0.004 0.005 0.006 0.007 0.008
Time (sec)
2000
1000
0
0.000 0.001 0.002 0.003 0.004 0.005 0.006 0.007 0.008
Time (sec)
2000
1000
0
0.000 0.001 0.002 0.003 0.004 0.005 0.006 0.007 0.008
Time (sec)
Voltage (V)
1.5
Voltage (V)
0 1.0
0 2 4 6 8 10
-1 0.5
-2 0.0
Voltage (V)
1.5
Voltage (V)
0 1.0
0 2 4 6 8 10
-1 0.5
-2 0.0
-3 0.0 0.2 0.4 0.6 0.8 1.0
Time (ms)
Frequency (kHz)
Voltage (V)
1.5
Voltage (V)
0 1.0
0 2 4 6 8 10
-1 0.5
-2 0.0
-3 0.0 0.2 0.4 0.6 0.8 1.0
Time (ms)
Frequency (kHz)
10
ADC count
6
0
0 2 4 6 8 10 12
-2
Vin
4
– Offset
2 – Integral non-linearity
0 – Differential non-linearity
0 2 4 6 8 10 12
-2
Vin
Vout 80
6 Ideal
Linear (Vout) 60
4
40
2
0 Non Linearity 20
0 5 10 15
0
Vin 0 20 40 60 80 100 120
• Non linearity: maximum difference between the best linear fit and the
ideal curve
Vmax 101.5
1 LSB = 101
2n
Frequency
100.5
Ideal Frequency
n − bit ADC
100
Measured frequency
99.5
99
98.5
0 20 40 60 80
ADC count
Vin
D
DAC
Components required:
a) Opamp based integrator
b) Electronically controlled switches
c) Binary counter
d) Clock
e) Control logic
f) Voltage comparator
0 1
1 1 1 1
00 1 w 1
Static-1 logic hazard,
x but no function hazard.
01 1 1 f
y 1
11 1 1 1
z
w 1
10 1 1 1 1 z
w 1
00 1
x
y 1 1
01 1 1
z
11 1 1 1 w 1
z
10 1 1 1 1 w 1 1
y 1
y 1
01 1 1 f
z
Example: solid arrow G1
(1110 0111)
11 1 1 1 w
z
10 1 1 1 1 w
y 1
00 1 w 00 1 w
x 1 x 1
01 1 1 y 1 01 1 1 1
f y
z f
z
11 1 1 1 G1 11 1 1 1
w w
y 0 0
z
10 1 1 1 1 10 1 1 1 1 z
w
w
y 1
y 1
00 0 0 1 1 00 0 0 1 1 00 0 0 1 1
01 0 1 1 1 01 0 1 1 1 01 0 1 1 1
11 1 1 1 1 11 1 1 1 1 11 1 1 1 1
0 1 1 0 1 1 0 1 1
10 1 10 1 10 1
Required Cubes
(a) Required cubes. (b) Privileged c ubes. (c) Prime implicants with no
dhf-
illegal intersecti ons.wy’ wy xy‘z w‘yz w‘x’y
wx wx
yz 00 01 11 10 yz 00 01 11 10 PI
00 0 0 1 1 00 0 0 1 1
w X X
01 0 1 1 1 01 0 1 1 1
yz X
An 11 1 1 1 1 11 1 1 1 1
x‘y X
Example 10 1 0 1 1 10 1 0 1 1
xy‘z X
(d) Prime implicant xz has an (e) Prime implicant xz reduced to
illegal intersection. dhf-prime implicant xy z.
Hazard-free sum-of-products:
w + yz + x’y + xy’z
• Fault Coverage: Percentage of the total number of logical faults that can
be tested using a given test set T.
• Thus, verifying the state table of the sequential circuit for testing is infeasible.
– Need some mechanism to enhance the controllability and observability of the
state variables.
– Design for Testability is a standard technique that is used in practice.
• Fault Modeling
– Abstract the physical defects and define a suitable logical fault model.
– Limits / simplifies the scope of test generation.
• Test Generation
– Given a circuit and a set of faults F, determine a set of test vectors T that
detects all faults in F.
• Fault Simulation
– Given a circuit, a set of faults F, and a set of test vectors T, determine the
faults in F that are tested by the vectors in T.
Circuit
Input patterns Under Output response
Test
• Here we assume that some of the circuit lines are permanently fixed at
logic-0 or logic-1 due to some failures.
• Very popular fault model, as it can model many realistic physical failures.
– Faults on a line A are denoted as: A s-a-0 or A/0, and A s-a-1 or A/1.
– Fanout stems and fanout branches are considered as separate lines.
F1
A F
B
F2
B2 E
A1 D
A A2 C C1
B F
B1 C2
B2 E
• Some properties of faults that occur in gates can help us in reducing the
effective number of faults to be considered.
• Some techniques used for fault collapsing:
a) Fault equivalence
b) Fault dominance
• Inputs:
– A circuit netlist.
– A fault list F.
• Output(s):
– A set of test vectors T to detect the faults in F.
– A list of undetected faults.
xi df(X) = 1
dxi
• The set of test vectors that can detect the fault xi /1 is given by
xi’ df(X) = 1
dxi
xi or xi’ df(X)/dxi
A
E
B H
C1 F Z
C C2 G
D
A
E
B 0 H
C1 F Z
C C2 G
D
A reverse logic value is
applied at the site of the
fault.
A
E
B 0 H
C1 F 1 Z
0
C C2 G
D Propagate the fault
effect to the output by
applying non-controlling
values to the side inputs
of gates along the path.
A 0
E
B 0 H
0
C1 F 1 Z
0 0
C 0 C2 G
D X Back-trace towards the
primary inputs and
assign values to gate
Test Vector: {0 0 0 X} inputs as required.
• Design technique that makes test generation and test application easier
and cost-effective.
• Mainly addresses the difficulty of testing sequential circuits.
– Difficult to control and observe the internal flip-flops.
• DFT techniques help in making the internal flip-flops easily controllable
and observable.
– Basically converts the sequential circuit test generation problem to
combinational circuit test generation problem.
MUX Q
SD
Logic overhead
CK
Master-Slave D flip-flop
SFF
TC
SCANIN
Required I1 S1 O1 N1
inputs to be I2 S2 O2 N2
applied
I3 S3 O3 N3
… … … …
PI
I1 I2
PO
O1 O2
SCANOUT N1 N2
• Specifies the total number of clock cycles required to apply all the test
patterns and observe the responses.
– PS has to be shifted in serially in the scan shift register through SCANIN.
– NS has to be shifted out serially through SCANOUT.
• The flip-flops in the scan register must be tested prior to the application of
the test vectors.
– Apply a shift sequence 0 0 1 1 0 0 1 1 … of length ns+4.
– Produces all possible transitions in the flip-flops.
• Thus, total scan test length is:
(ns + 1) nc + ns + (ns + 4)
• Example: ns = 2000, nc = 500 Test length = 106
• We add extra hardware to the chip for test generation and response
evaluation.
– Done on chip.
– Additional hardware overhead.
• Only a few external pins to control BIST operation.
– Input pin: TEST CONTROL (TC)
– Output pin: GOOD/BAD
%
Fault
Coverage
Type-2 LFSR
D1 D2 D3 + D4
1. The period of {an} is p = 2n-1, that is, ap+i = ai, for all i ≥ 0.
2. Starting from any nonzero state, the LFSR that generates {an} goes
through all 2n-1 states before repeating.
3. The number of 1’s differs from the number of 0’s by one.
4. If a window of width n is slid along an m-sequence, then each of the 2n-1
nonzero binary n-tuples is seen exactly once in a period.
5. In every period of an m-sequence, one-half the runs have length 1, one-
fourth have length 2, one-eighth have length 3, and so on.
Output Response
X0 X1 X2 X3 X4
Remainder Polynomial ::
F(X) = X3 + X2 + 1
+ D0 + D1 + D2 + D3 + D4