Formula Sheets: Combinational Circuits | Digital Logic - Computer Science Engineering (CSE) PDF Download

 Page 1


Com binational Circuits F orm ula Sheet
Com b inational Circuits Basics
• Definition : Digital circuits where output dep ends only on curren t inputs, no memory .
• Comp onen ts : Logic gates (AND, OR, NOT, NAND, NOR, X OR), m ultiplexers, deco ders, en-
co ders, arithmetic units.
• T ruth T able : 2
n
ro ws for n inputs, maps inputs to m outputs.
• Propagation Dela y : T
circuit
=
?
T
gate
i
along critical path, e.g., AND: 1-2 ns, X OR: 2-3 ns.
• Gate Coun t : N
gates
˜
N
literals
2
for 2-input gates, impacts area S
circuit
.
• P o w er Consumption : P
circuit
=
?
(C
gate
i
·V
2
·f) , whereC
gate
i
is gate capacitance,V is v oltage,
f is frequency .
Enco d ers and Deco ders
• Enco der :
– Con v erts 2
n
inputs to n -bit binary output, e.g., 8:3 enco der.
– Output Bits: n =?log
2
N
inputs
? .
– Gate Coun t: N
gates
˜ 2
n
·n for priorit y enco der, few er for simple enco de r.
– Dela y: T
enco der
˜T
OR
·?log
2
2
n
? , t ypically 2-5 ns.
• Deco der :
– Con v erts n -bit input to 2
n
outputs, e.g., 3:8 deco der.
– Output Lines: N
outputs
= 2
n
.
– Gate Coun t: N
gates
˜n·2
n
(AND gates) + n (NOT gates).
– Dela y: T
deco der
=T
NOT
+T
AND
, t ypically 2-4 ns.
• Enable Signal : A dds con trol, T
enable
=T
AND
, no extra dela y if in tegrated.
Multiplexer and Dem ultiplexer
• Multiplexer (MUX) :
– Selects 1 of 2
n
inputs using n select lines, e.g., 4:1 MUX.
– Gate Coun t: N
gates
˜ 2
n
·(n+1) for 2-input AND/OR gates.
– Dela y: T
MUX
=T
AND
+T
OR
·?log
2
2
n
? , e.g., 3-6 ns for 4:1 MUX.
– F unction: f =
?
(I
i
·S
i
) , where I
i
is input, S
i
is select term (min term).
• Dem ultiplexer (DEMUX) :
– Routes 1 input to 2
n
outputs using n select lines, e.g., 1:4 DEMUX.
– Gate Coun t: N
gates
˜ 2
n
·(n+1) for AND gates.
– Dela y: T
DEMUX
=T
NOT
+T
AND
, t ypically 2-4 ns.
– F unction: Out
i
= Input·S
i
, where S
i
is select min term.
• Implemen tation : MUX/DEMUX can implemen t an y function, N
gates
? 2
n
.
1
Page 2


Com binational Circuits F orm ula Sheet
Com b inational Circuits Basics
• Definition : Digital circuits where output dep ends only on curren t inputs, no memory .
• Comp onen ts : Logic gates (AND, OR, NOT, NAND, NOR, X OR), m ultiplexers, deco ders, en-
co ders, arithmetic units.
• T ruth T able : 2
n
ro ws for n inputs, maps inputs to m outputs.
• Propagation Dela y : T
circuit
=
?
T
gate
i
along critical path, e.g., AND: 1-2 ns, X OR: 2-3 ns.
• Gate Coun t : N
gates
˜
N
literals
2
for 2-input gates, impacts area S
circuit
.
• P o w er Consumption : P
circuit
=
?
(C
gate
i
·V
2
·f) , whereC
gate
i
is gate capacitance,V is v oltage,
f is frequency .
Enco d ers and Deco ders
• Enco der :
– Con v erts 2
n
inputs to n -bit binary output, e.g., 8:3 enco der.
– Output Bits: n =?log
2
N
inputs
? .
– Gate Coun t: N
gates
˜ 2
n
·n for priorit y enco der, few er for simple enco de r.
– Dela y: T
enco der
˜T
OR
·?log
2
2
n
? , t ypically 2-5 ns.
• Deco der :
– Con v erts n -bit input to 2
n
outputs, e.g., 3:8 deco der.
– Output Lines: N
outputs
= 2
n
.
– Gate Coun t: N
gates
˜n·2
n
(AND gates) + n (NOT gates).
– Dela y: T
deco der
=T
NOT
+T
AND
, t ypically 2-4 ns.
• Enable Signal : A dds con trol, T
enable
=T
AND
, no extra dela y if in tegrated.
Multiplexer and Dem ultiplexer
• Multiplexer (MUX) :
– Selects 1 of 2
n
inputs using n select lines, e.g., 4:1 MUX.
– Gate Coun t: N
gates
˜ 2
n
·(n+1) for 2-input AND/OR gates.
– Dela y: T
MUX
=T
AND
+T
OR
·?log
2
2
n
? , e.g., 3-6 ns for 4:1 MUX.
– F unction: f =
?
(I
i
·S
i
) , where I
i
is input, S
i
is select term (min term).
• Dem ultiplexer (DEMUX) :
– Routes 1 input to 2
n
outputs using n select lines, e.g., 1:4 DEMUX.
– Gate Coun t: N
gates
˜ 2
n
·(n+1) for AND gates.
– Dela y: T
DEMUX
=T
NOT
+T
AND
, t ypically 2-4 ns.
– F unction: Out
i
= Input·S
i
, where S
i
is select min term.
• Implemen tation : MUX/DEMUX can implemen t an y function, N
gates
? 2
n
.
1
Arithmetic Circuits
• Half A dder :
– Inputs: A,B ; Outputs: Sum S =A?B , Carry C =A·B .
– Gate Coun t: N
gates
= 2 (1 X OR, 1 AND).
– Dela y: T
HA
=T
X OR
, t ypically 2-3 ns.
• F ull A dder :
– Inputs: A,B,C
in
; Outputs: SumS =A?B?C
in
, CarryC
out
= (A·B)+(B·C
in
)+(A·C
in
) .
– Gate Coun t: N
gates
= 5 (2 X OR, 2 AND, 1 OR).
– Dela y: T
F A
= 2·T
X OR
, t ypically 4-6 ns.
• n-Bit Ripple Carry A dder :
– Dela y: T
R CA
=n·T
F A
, linear, e.g., 32-bit: 128-192 ns.
– Gate Coun t: N
gates
=n·5 .
• Carry Lo okahead A dder (CLA) :
– Propagate: P
i
=A
i
?B
i
, Generate: G
i
=A
i
·B
i
.
– Carry: C
i+1
=G
i
+P
i
·C
i
.
– Dela y: T
CLA
=O(logn) , e.g., 32-bit: 10-20 ns.
– Gate Coun t: N
gates
˜ 3n+logn , higher than R CA.
• Subtractor : Uses 2’s complemen t, A-B =A+B +1 , same dela y as adder.
• Arithmetic Circuit P o w er : P
arithmetic
?n·P
gate
, reduced b y CLA for sp eed.
Static Hazards
• Definition : Un w an ted glitc h in output due to gate dela ys during input transition.
• T yp es :
– Static-1 Hazard: Output should sta y 1, glitc hes to 0.
– Static-0 Hazard: Output should sta y 0, glitc hes to 1.
• Detection : K-Map analysis, hazard exists if adjacen t 1’s (or 0’s) not co v ered b y same implican t.
• Elimination : A dd redundan t implican ts, e.g., for f =AB +AC , add BC to co v er hazard.
• Extra Gates : N
hazard-fix
˜N
hazards
, increases N
gates
but ensures stabilit y .
• Dela y Impact : T
hazard-free
=T
circuit
+T
AND
, minimal if optimized.
P erformance Metrics
• Circuit Dela y : T
circuit
= max(T
path
i
) , critical path determines sp eed, minimized b y CLA, MUX
optimization.
• Gate Coun t : N
gates
?N
literals
, reduced b y K-Map minimization, impacts S
circuit
.
• P o w er Consumption : P
circuit
=N
gates
·C
gate
·V
2
·f , lo w er with few er gates.
• Area : S
circuit
?N
gates
·S
gate
, optimized b y e?icien t enco ding/deco ding.
• Hazard-F ree E?iciency : E
hazard
=
T circuit
T
hazard-free
, ideally˜ 1 with minimal N
gates
increase.
• Complexit y : C
circuit
=N
inputs
·N
outputs
·N
gates
, reduced b y mo dular design (MUX, enco der).
2
Page 3


Com binational Circuits F orm ula Sheet
Com b inational Circuits Basics
• Definition : Digital circuits where output dep ends only on curren t inputs, no memory .
• Comp onen ts : Logic gates (AND, OR, NOT, NAND, NOR, X OR), m ultiplexers, deco ders, en-
co ders, arithmetic units.
• T ruth T able : 2
n
ro ws for n inputs, maps inputs to m outputs.
• Propagation Dela y : T
circuit
=
?
T
gate
i
along critical path, e.g., AND: 1-2 ns, X OR: 2-3 ns.
• Gate Coun t : N
gates
˜
N
literals
2
for 2-input gates, impacts area S
circuit
.
• P o w er Consumption : P
circuit
=
?
(C
gate
i
·V
2
·f) , whereC
gate
i
is gate capacitance,V is v oltage,
f is frequency .
Enco d ers and Deco ders
• Enco der :
– Con v erts 2
n
inputs to n -bit binary output, e.g., 8:3 enco der.
– Output Bits: n =?log
2
N
inputs
? .
– Gate Coun t: N
gates
˜ 2
n
·n for priorit y enco der, few er for simple enco de r.
– Dela y: T
enco der
˜T
OR
·?log
2
2
n
? , t ypically 2-5 ns.
• Deco der :
– Con v erts n -bit input to 2
n
outputs, e.g., 3:8 deco der.
– Output Lines: N
outputs
= 2
n
.
– Gate Coun t: N
gates
˜n·2
n
(AND gates) + n (NOT gates).
– Dela y: T
deco der
=T
NOT
+T
AND
, t ypically 2-4 ns.
• Enable Signal : A dds con trol, T
enable
=T
AND
, no extra dela y if in tegrated.
Multiplexer and Dem ultiplexer
• Multiplexer (MUX) :
– Selects 1 of 2
n
inputs using n select lines, e.g., 4:1 MUX.
– Gate Coun t: N
gates
˜ 2
n
·(n+1) for 2-input AND/OR gates.
– Dela y: T
MUX
=T
AND
+T
OR
·?log
2
2
n
? , e.g., 3-6 ns for 4:1 MUX.
– F unction: f =
?
(I
i
·S
i
) , where I
i
is input, S
i
is select term (min term).
• Dem ultiplexer (DEMUX) :
– Routes 1 input to 2
n
outputs using n select lines, e.g., 1:4 DEMUX.
– Gate Coun t: N
gates
˜ 2
n
·(n+1) for AND gates.
– Dela y: T
DEMUX
=T
NOT
+T
AND
, t ypically 2-4 ns.
– F unction: Out
i
= Input·S
i
, where S
i
is select min term.
• Implemen tation : MUX/DEMUX can implemen t an y function, N
gates
? 2
n
.
1
Arithmetic Circuits
• Half A dder :
– Inputs: A,B ; Outputs: Sum S =A?B , Carry C =A·B .
– Gate Coun t: N
gates
= 2 (1 X OR, 1 AND).
– Dela y: T
HA
=T
X OR
, t ypically 2-3 ns.
• F ull A dder :
– Inputs: A,B,C
in
; Outputs: SumS =A?B?C
in
, CarryC
out
= (A·B)+(B·C
in
)+(A·C
in
) .
– Gate Coun t: N
gates
= 5 (2 X OR, 2 AND, 1 OR).
– Dela y: T
F A
= 2·T
X OR
, t ypically 4-6 ns.
• n-Bit Ripple Carry A dder :
– Dela y: T
R CA
=n·T
F A
, linear, e.g., 32-bit: 128-192 ns.
– Gate Coun t: N
gates
=n·5 .
• Carry Lo okahead A dder (CLA) :
– Propagate: P
i
=A
i
?B
i
, Generate: G
i
=A
i
·B
i
.
– Carry: C
i+1
=G
i
+P
i
·C
i
.
– Dela y: T
CLA
=O(logn) , e.g., 32-bit: 10-20 ns.
– Gate Coun t: N
gates
˜ 3n+logn , higher than R CA.
• Subtractor : Uses 2’s complemen t, A-B =A+B +1 , same dela y as adder.
• Arithmetic Circuit P o w er : P
arithmetic
?n·P
gate
, reduced b y CLA for sp eed.
Static Hazards
• Definition : Un w an ted glitc h in output due to gate dela ys during input transition.
• T yp es :
– Static-1 Hazard: Output should sta y 1, glitc hes to 0.
– Static-0 Hazard: Output should sta y 0, glitc hes to 1.
• Detection : K-Map analysis, hazard exists if adjacen t 1’s (or 0’s) not co v ered b y same implican t.
• Elimination : A dd redundan t implican ts, e.g., for f =AB +AC , add BC to co v er hazard.
• Extra Gates : N
hazard-fix
˜N
hazards
, increases N
gates
but ensures stabilit y .
• Dela y Impact : T
hazard-free
=T
circuit
+T
AND
, minimal if optimized.
P erformance Metrics
• Circuit Dela y : T
circuit
= max(T
path
i
) , critical path determines sp eed, minimized b y CLA, MUX
optimization.
• Gate Coun t : N
gates
?N
literals
, reduced b y K-Map minimization, impacts S
circuit
.
• P o w er Consumption : P
circuit
=N
gates
·C
gate
·V
2
·f , lo w er with few er gates.
• Area : S
circuit
?N
gates
·S
gate
, optimized b y e?icien t enco ding/deco ding.
• Hazard-F ree E?iciency : E
hazard
=
T circuit
T
hazard-free
, ideally˜ 1 with minimal N
gates
increase.
• Complexit y : C
circuit
=N
inputs
·N
outputs
·N
gates
, reduced b y mo dular design (MUX, enco der).
2
Applications and Concepts
• Enco ders/Deco ders : Used in address deco ding, data compression, T
deco der
critical for memory
systems.
• Multiplexers : F unction generators, data r outing, N
gates
? 2
n
, v ersatile for com binational logic.
• Arithmetic Circuits : Core of ALUs, T
CLA
«T
R CA
for high-sp eed CPUs.
• Static Hazards : Critical in reliable circuit design, eliminated via K-Map for glitc h-free op eration.
• Com binational Logic : Used in ALUs, con trol units, data paths,T
circuit
impacts CPU cycle time.
• Mo dular Design : MUX/DEMUX reduce N
gates
, impro v e scalabilit y in large circuits.
3