Exercise DET-02.04 – Collective fault aggregation (Solution)

Prof. Dr. Thorsten Jungmann (last updated 2026-10-12)

Relates to DET-02 Logic operations

Task

The controller of a heat pump forms the collective fault as the OR of twelve fault bits. Only OR gates with two inputs are available, each with a propagation delay of $t_{\mathrm{pd}}=9\mathrm{ns}$. This exercise is based on a concept check in the textbook by LaMeres [5, p. 111].

a) How many gates does the circuit need?

b) Arrange the gates so that the collective fault is valid as early as possible. How many stages does the circuit then have?

c) What is the propagation delay of the circuit?

◀️ Back to the task

---

Solution

Given

Given explicitly:

• 12 fault bits, combined by OR into the collective fault
• OR gates with two inputs, each with $t_{\mathrm{pd}}=9\mathrm{ns}$

Known:

• Associative property (DET-02); gates with more than two inputs (DET-02)
• Propagation delay of a circuit, stage by stage (DET-02)

Required

a) the number of gates
b) the arrangement in which the collective fault is valid earliest, and its number of stages
c) the propagation delay of the circuit

a) Number of gates

Each OR gate with two inputs combines two signals into one, so that it reduces the number of signals by one. From 12 fault bits to a single collective fault, the number of gates is therefore always the same, however they are arranged:

$$n_{\mathrm{gates}}=12-1=11$$

The circuit needs 11 gates.

b) Arrangement and stages

By the associative property, the fault bits may be grouped in any way (DET-02, 5.4). The collective fault is valid earliest if each stage combines as many signals in pairs as possible:

Stage	Gates	Signals after the stage	Valid after
1	6	6	9 ns
2	3	3	18 ns
3	1	2	27 ns
4	1	1	36 ns

In stage 3, one gate combines two of the three signals of stage 2; the third signal waits for stage 4. The circuit therefore has 4 stages.

Other arrangements with 4 stages are just as good, for example with 4, 4, 2 and 1 gates; what counts is that no path passes through more than 4 gates.

Check: with 3 stages of gates with two inputs, at most $2^3=8$ signals can be combined, fewer than 12; 4 stages are enough for up to $2^4=16$ signals. And $6+3+1+1=11$ gates, as in a) ✓

c) Propagation delay

A gate can switch only when the slowest of its inputs has arrived, so that the delay is found stage by stage (DET-02, 6.3). The gate of the last stage waits for the slower of its inputs: the output of stage 3, valid after 27 ns, and the signal of stage 2 that waited, valid after 18 ns:

$$t_{\mathrm{pd},\mathrm{circuit}}=\max \left(27\mathrm{ns},18\mathrm{ns}\right)+9\mathrm{ns}=36\mathrm{ns}$$

The collective fault is valid 36 ns after a change of a fault bit.

Check: the longest path passes through one gate in each of the 4 stages, so that $t_{\mathrm{pd},\mathrm{circuit}}=4\cdot 9\mathrm{ns}=36\mathrm{ns}$ ✓

Gates with more inputs

With OR gates with four inputs, as in DET-02, 3.4, two stages suffice: three gates with four inputs each and one with three inputs. If, for simplicity, each of these gates again had a propagation delay of 9 ns, the collective fault would be valid after $2\cdot 9\mathrm{ns}=18\mathrm{ns}$.