# EE2000 Logic Circuit Design Combinational Circuit Design

EE2000 Logic Circuit Design Combinational circuit design

4.Combinational Circuit Design

Logic circuits for digital systems may be combinational or sequential. A combinational circuit consists of logic gates whose outputs at any time are determined directly from the combination of inputs without regard to previous inputs.

4.1Design procedures

1.The problem is stated.

2.Determine the number of input variables and output variables.

3.The input and output variables are assigned letter symbols.

4.The truth tables that defines the required relationships between inputs and outputs is derived.

5.The simplified Boolean function for each output is obtained.

6.The logic diagram is drawn.

operation / x / y / s / c
0 + 0 = 0 / 0 / 0 / 0 / 0
0 + 1 = 1 / 0 / 1 / 1 / 0
1 + 0 = 1 / 1 / 0 / 1 / 0
1 + 1 = 10 / 1 / 1 / 0 / 1
y /
x / 1
1
y /
x
1

However, s may be represented by XOR function, i.e. s = x  y

So, an half-adder can be represented by the following circuit:

x / y / ci / s / co
0 / 0 / 0 / 0 / 0
0 / 0 / 1 / 1 / 0
0 / 1 / 0 / 1 / 0
0 / 1 / 1 / 0 / 1
1 / 0 / 0 / 1 / 0
1 / 0 / 1 / 0 / 1
1 / 1 / 0 / 0 / 1
1 / 1 / 1 / 1 / 1

Realization using k-map:

yci /
x / 1 / 1
1 / 1
yci /
x / 1
1 / 1 / 1

4.3Subtractor

(a)Half-subtractor

x / y / d / b
0 / 0 / 0 / 0 /
0 / 1 / 1 / 1 /
1 / 0 / 1 / 0
1 / 1 / 0 / 0

(b)Full-subtractor

x / y / bi / d / b
0 / 0 / 0 / 0 / 0
0 / 0 / 1 / 1 / 1
0 / 1 / 0 / 1 / 1
0 / 1 / 1 / 0 / 1
1 / 0 / 0 / 1 / 0
1 / 0 / 1 / 0 / 0
1 / 1 / 0 / 0 / 0
1 / 1 / 1 / 1 / 1
ybi /
x / 1 / 1
1 / 1
ybi
x / 1 / 1 / 1 /
1

M / Operation / Binary form
0 / A + B / A4A3A2A1 + B4B3B2B1
1 / A  B / A4A3A2A1B4B3B2B1

A single full-adder is capable of adding two one-bit numbers and an input carry. In order to add binary numbers with more than one bit, additional full-adders must be employed. So the carry out from previous stage will be fed into the carry input of the next stage.

The above example is a 4-bit parallel adder, where s3s2s1s0 forms the binary sum and co is the carry output.

The parallel adders described previously are ripple carry types in which the carry output of each full-adder stage is connected to the carry input of the next higher stage. A time delay thus occurs because the sum and the carry output of each stage cannot be produced until the input carry appears. This is illustrated in the following example. Assuming that the delay for generating the carry output is m nsec, thus for a 4-bit adder, the total delay will be up to 4m nsec !! The longer the bit length of the adder, the longer the delay. In order to speed up the addition, the generation of carry output will be examined. The method is based on two functions derived from full-adder, called the carry generate (g) and carry propagate (p) functions.

x / y / ci / co
0 / 0 / 0 / 0
0 / 0 / 1 / 0
0 / 1 / 0 / 0
0 / 1 / 1 / 1 / p
1 / 0 / 0 / 0
1 / 0 / 1 / 1 / p
1 / 1 / 0 / 1 / g
1 / 1 / 1 / 1 / g

Conditions for generating g and p

From the above table, we obtain that

g = xyandp =

Most importantly, the carry output co can be obtained by:

co = g + pci

Full-adder 0:co0= g0 + p0 ci0

co1= g1 + p1 ci1

= g1 + p1 co0

= g1 + p1(g0 + p0 ci0)

= g1 + p1 g0 + p1 p0 ci0

co2= g2 + p2 co1

= g2 + p2(g1 + p1 g0 + p1 p0 ci0)

= g2 + p2 g1 + p2 p1 g0 + p2 p1 p0 ci0

co3= g3 + p3 co2

= g3 + p3(g2 + p2 g1 + p2 p1 g0 + p2 p1 p0 ci0)

= g3 + p3 g2 + p3 p2 g1 + p3 p2 p1 g0 + p3 p2 p1 p0 ci0

4.6Code conversion

input BCD / output Excess-3 Code
a / b / c / d / w / x / y / z
0 / 0 / 0 / 0 / 0 / 0 / 1 / 1
0 / 0 / 0 / 1 / 0 / 1 / 0 / 0
0 / 0 / 1 / 0 / 0 / 1 / 0 / 1
0 / 0 / 1 / 1 / 0 / 1 / 1 / 0
0 / 1 / 0 / 0 / 0 / 1 / 1 / 1
0 / 1 / 0 / 1 / 1 / 0 / 0 / 0
0 / 1 / 1 / 0 / 1 / 0 / 0 / 1
0 / 1 / 1 / 1 / 1 / 0 / 1 / 0
1 / 0 / 0 / 0 / 1 / 0 / 1 / 1
1 / 0 / 0 / 1 / 1 / 1 / 0 / 0
cd / cd
ab / ab / 1 / 1 / 1
1 / 1 / 1 / 1
d / d / d / d / d / d / d / d
1 / 1 / d / d / 1 / d / d
w = a + bc + bd /
cd / cd
ab / 1 / 1 / ab / 1 / 1
1 / 1 / 1 / 1
d / d / d / d / d / d / d / d
1 / d / d / 1 / d / d

k-map for the BCD-to-excess-3-code converter

Logic diagram for a BCD-to-excess-3-code converter

4.7Magnitude comparator

A comparator is used to compare the magnitude of two numbers. The output will be one of the three possibilities, i.e., small (s), equal (e) and greater (g). For two 2-digit numbers, A and B, we have the following description:

Variable assignment:

A = a1a0 ,B = b1b0 ,

and the output

z / z2 / z1 / z0
g / 1 / 0 / 0
e / 0 / 1 / 0
s / 0 / 0 / 1

The system hence can be described by the following logical expressions:

Finally, we construct the following truth table:

input / output / input / output
a1 / a0 / b1 / b0 / z2 / z1 / z0 / a1 / a0 / b1 / b0 / z2 / z1 / z0
0 / 0 / 0 / 0 / 0 / 1 / 0 / 1 / 0 / 0 / 0 / 1 / 0 / 0
0 / 0 / 0 / 1 / 0 / 0 / 1 / 1 / 0 / 0 / 1 / 1 / 0 / 0
0 / 0 / 1 / 0 / 0 / 0 / 1 / 1 / 0 / 1 / 0 / 0 / 1 / 0
0 / 0 / 1 / 1 / 0 / 0 / 1 / 1 / 0 / 1 / 1 / 0 / 0 / 1
0 / 1 / 0 / 0 / 1 / 0 / 0 / 1 / 1 / 0 / 0 / 1 / 0 / 0
0 / 1 / 0 / 1 / 0 / 1 / 0 / 1 / 1 / 0 / 1 / 1 / 0 / 0
0 / 1 / 1 / 0 / 0 / 0 / 1 / 1 / 1 / 1 / 0 / 1 / 0 / 0
0 / 1 / 1 / 1 / 0 / 0 / 1 / 1 / 1 / 1 / 1 / 0 / 1 / 0

The output (z2 z1 z0)can be obtained by using k-map

b1b0
a1a0
1 /
1 / 1 / 1
1 / 1
b1b0
a1a0 / 1
1 /
1
1
b1b0
a1a0 / 1 / 1 / 1
1 / 1 /
1

## Timing Diagram

A timing diagram is a graphical representation of input and output signal relationships in a switching network, as might be seen on the display of an oscilloscope or logic analyzer or in a logic simulation program.

Inputs / Outputs
Time / A B C / /
t0 / 0 0 0 / 0 / 0
t1 / 0 0 1 / 1 / 1
t2 / 0 1 0 / 1 / 0
t3 / 0 1 1 / 0 / 1
t4 / 1 0 0 / 0 / 0
t5 / 1 0 1 / 0 / 1
t6 / 1 1 0 / 1 / 1
t7 / 1 1 1 / 1 / 0

Propagation Delay

In addition to logic function, a designer must be concerned with a number of physical characteristics of digital logic circuits, including the following:

• Propagation delays

• Gate fan-in and fan-out restrictions

• Power consumption

• Size and weight

The delay between the time of an input change and the corresponding output change is called a propagation delay.

Two propagation delay parameters are typically specified for a given logic gate:

tPLH = propagation delay time, low- to high-level output

tPHL = propagation delay time, high- to low-level output

In general, a single propagation delay parameter, denoted by tPDis used to approximate both TPLH and TPHL.

Usually,

Propagation delay through a logic gate. (a) Two-input AND gate. (b) ideal (zero) delay. (c) tPD = tPLH = tPHL. (d) tPLHtPHL.

Propagation delays of primitive 74LS series gates.

tPLH / tPHL
Chip / Function / Typical / Maximum / Typical / Maximum
74LS04 / NOT / 9 / 15 / 10 / 15
74LS00 / NAND / 9 / 15 / 10 / 15
74LS02 / NOR / 10 / 15 / 10 / 15
74LS08 / AND / 8 / 15 / 10 / 20
74LS32 / OR / 14 / 22 / 14 / 22

I

In some cases, gate propagation delay may cause undesirable events to occur in a network. These undesirable events are referred to as hazards.

Timing hazards

If the logic gate delay is not considered when designing logic circuit, the output may deviate from its steady-state behavior. The circuit may produce a short pulse, often called a glitch, at a time when steady-state analysis predicts that the output should not change. A hazard is said to exist when a circuit has the possibility of producing such a glitch.

Static hazard

Static 1 hazard – the output may momentarily go to 0 when it should remain 1.

Static 0 hazard – the output may momentarily go to 1 when it should remain 0.

Static 1 hazard Static 0 hazard

Dynamic hazard

The output changes three or more times when it should change from 1 to 0 or from 0 to 1.

Hazard-free circuit

Tabulated method:all prime implants must be included.

Consider the following circuit:

Static-1 hazard (initial conditions x1,x2,x3 = 111; x2: 1  0)

The occurrence of the hazard can be detected by inspecting the map of the particular circuit. Consider the K-map below. The change in x2 from 1 to 0 moves the circuit from minterm 111 to minterm 101. The hazard exists because the change of input results in a different product term covering the two minterms. Minterm 111 is covered by the product term implemented in G1, and minterm 101 is covered by the product term implemented in G2. Whenever the circuit must move from one product term to another, there is a possibility of a momentary interval when neither term is equal to 1, giving rise to an undesirable 0 output.

Hazard may occur. /
Hazard is removed.

The remedy for eliminating a hazard is to enclose the two minterms in question with another product term that overlaps both groupings. This is shown in the K-map before where the two minterms that cause the hazard are combined into one product term. The extra gate in the circuit generates the product term x1x3. In general, hazards in combinational circuits can be removed by covering any two minterms that may produce a hazard with a product term common to both. The removal of hazards requires the addition of redundant gates to the circuit.

1