• Combinational Logic Timing (Basic)
• Tracing CMOS Circuit (Basic)
• Universal Gates (Basic)
• Full Adder Timing Analysis (Intermediate)
• Combinational Construction Rules (Intermediate)

50.002 Computation Structures
Information Systems Technology and Design
Singapore University of Technology and Design

CMOS Technology

Each topic’s questions are grouped into three categories: basic, intermediate, and challenging. You are recommended to do all basic problem set before advancing further.

Combinational Logic Timing (Basic)

Consider the following combinational logic device.

Each logic gate has the same:

• Propagation delay, tpd= 2ns,
• Contamination delay, tcd=1ns

Compute the overall propagation delay and contamination delay for the circuit.

Tracing CMOS Circuit (Basic)

Draw the truth table for the following CMOS circuitry:

Universal Gates (Basic)

Use only NAND gates to redraw the circuit below. Use as few NAND gates as possible.

Think!

How many MOSFETs do we save by minimising the boolean expression first before realising it into hardware?

Full Adder Timing Analysis (Intermediate)

Refer to the FA circuitry below:

Answer the following questions:

1. Compute the tpd​ and tcd of the full adder above.

2. If we were to put several of these FAs to form an 8-bit ripple-carry adder as shown, compute the tpd and tcd of an 8-bit ripple-carry adder made of 8 of these FA circuits.

   

Video explanation here.

Combinational Construction Rules (Intermediate)

During lecture, we learned a first set of principles that define a combinational device. A combinational device is a circuit element that has:

1. One or more digital inputs.
2. One or more digital outputs.
3. A functional specification that details the value of each output for every possible combination of valid input values.
4. A timing specification consisting (at minimum) of an upper bound tpd on the required time for the device to compute the specified output values from an arbitrary set of stable, valid input values.

We also learned a second set of rules, that a set of interconnected elements is a combinational device if:

1. Each circuit element is combinational.
2. Every input is connected to exactly one output or to some vast supply of 0’s and 1’s.
3. The circuit contains no directed cycles.

Read point (2) carefully. This does NOT mean that a combinational device must just have one output and one input. This means that for each input of a combinational device, it is connected to exactly ONE output of the “previous” device.

In this problem, we ask you to think carefully about why these rules work - in particular, why an acyclic circuit of combinational devices, constructed according to the second principle, is itself a combinational device as defined by the first.

Consider the following 2-input acyclic circuit whose two components, A and B, are each combinational devices.

The propagation delay for each device is specified in nanoseconds:

• Device A tpd: 3ns
• Device B tpd: 2ns

The functional specifications for each component are given as truth tables detailing output values for each combination of inputs, where \(A _{a_0, a_1}\) denotes the output from device A, and \(B _{b_0, b_1}\) denotes the output from device B:

\[\begin{matrix} a_0 & a_1 & A _{a_0, a_1} & b_0​ & b_1 & B_{b_0, b_1}\\ \hline \\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 1 & 1 & 1 & 1\\ \hline \end{matrix}\]

Answer the following questions:

1. Give a truth table for the overall acyclic circuit, i.e. a table that specifies the value of z for each of the possible combinations of input values on x and y.
2. Describe a general procedure by which a truth table can be computed for each output of an arbitrary acyclic circuit containing only combinational components. Hint : construct a functional specification to each circuit node.
3. Specify a propagation delay (the upper bound required for each combinational device) for the circuit.
4. Describe a general procedure by which a propagation delay can be computed for an arbitrary acyclic circuit containing only combinational components. Hint: add a timing specification to each circuit node.
5. Do your general procedures for computing functional specifications and propagation delays work if the restriction to acyclic circuits is relaxed (lifted)? Explain.

Video explanation here.

---