Digital Circuits: Logic, Arithmetic and Sequential Design

Combinational circuit propagation delay

Propagation delay is the time between a change at an input and the moment the output reaches its new stable value. In a combinational network, the delay of a path is the sum of the gate delays along it, and the worst-case delay of the circuit is the largest such sum over all paths that can actually carry a transition. A path of this kind is called sensitizable: every side input of every gate on it must be set to a value that lets the transition pass. A structurally longest path can be false, because the side-input requirements of its gates contradict each other. For example, one signal may need to be 0 at one multiplexer input and 1 at another input of the same select line at the same time. The longest sensitizable path, not the longest structural path, fixes the maximum delay.

In a loop of cross-coupled gates, a simple path visits each gate at most once, so the critical delay of a two-NAND latch is the sum of the two gate delays along that path.

For a synchronous path between two flip-flops, the clock period must cover the clock-to-Q delay, the combinational delay and the setup time, so T_{clk} \ge t_{cq} + t_{logic} + t_{setup} and f_{max} = 1/T_{clk,min}. With t_{cq}=2 ns, t_{logic}=1 ns and t_{setup}=2 ns, the minimum period is 5 ns, which gives a maximum frequency of 200 MHz.

When the combinational delay is longer than one clock period, the logic output is still changing when the next edge arrives, so the value sampled at an edge reflects inputs from several cycles earlier. Such circuits must be analysed by tracking delayed values edge by edge in a timing table, not by assuming one-cycle behaviour.

MUX-based logic function implementation

A 2^n{:}1 multiplexer with select lines S_{n-1},\dots,S_0 computes Y=\sum_k m_k(S)\,I_k, where m_k is the minterm of the select lines whose binary value is k. The select lines therefore act as the variables of a function, and each data input holds the function value for one combination of those variables. The standard design method is to choose n of the function's variables as selects, expand the function into cofactors, and tie each data input to 0, 1, a remaining variable or its complement.

• Constant data input — tying I_k to 0 or 1 fixes the value of that minterm. For example, I_0=0, I_1=X and select S give Y=SX.
• Complemented data input — a data input equal to \overline{B} inverts the selected variable, which is how XOR is built.

The XOR function A\oplus B is obtained from a 2:1 MUX with select A, I_0=B and I_1=\overline{B}, because A=0 passes B and A=1 passes \overline{B}.

A 4:1 MUX with select lines C and D realizes C\oplus D when its data inputs, in index order, are 0, 1, 1, 0, since the output then follows the XOR truth table row by row.

A 2:1 MUX whose data inputs are 0 and P with select Q gives Y=\overline{Q}\cdot0+QP=PQ, which is the AND function.

After expansion, a MUX expression must be simplified with Boolean identities. For instance, \overline{z}+xyz=\overline{z}+xy, because the term xyz is absorbed: when z=0 both sides equal 1, and when z=1 both sides equal xy.

Flip-flop frequency division and duty cycle

A flip-flop wired as a toggle element (a T flip-flop, a JK flip-flop with J=K=1, or a D flip-flop with \overline{Q} fed back to D) changes state at every active clock edge and holds otherwise. Its output period is therefore two clock periods, so the frequency is halved. Cascading n such stages divides the frequency by 2^n, and the output of the k-th stage has frequency f/2^k.

The duty cycle of a toggled output is 50%, because the output is high for exactly one input period out of every two. The duty cycle of the clock does not carry over to the output.

A negative-edge JK flip-flop with J=K=1 toggles on every falling clock edge, so a 10 Hz input gives a 5 Hz output.

Two D flip-flops connected in a ring, with one output fed to the other D input and the complement of the other output fed back, form a twisted ring (Johnson) counter. With n flip-flops this counter has a period of 2n clock cycles, so each output has frequency f/(2n). For n=2 the output frequency is f/4.

Essential prime implicants of K-map

A prime implicant is a product term formed from a group of adjacent 1s on a K-map that cannot be enlarged further while staying inside the on-set (with don't cares allowed). An essential prime implicant is a prime implicant that covers at least one minterm that no other prime implicant covers, so every minimal sum-of-products must include it. The procedure is to list all prime implicants, find the primes that are the only cover of some minterm, select them, and then cover the remaining minterms with as few primes as possible.

For example, take F(A,B,C)=\sum m(0,1,3,7). The prime \overline{A}\,\overline{B} (minterms 0 and 1) is essential because minterm 0 has no other cover. The prime BC (minterms 3 and 7) is essential because minterm 7 has no other cover. The prime \overline{A}C (minterms 1 and 3) is not essential, since both of its minterms are covered by the essential primes, so F=\overline{A}\,\overline{B}+BC.

In a four-variable map the same test applies: a prime that is the only cover of a corner minterm of a 2×2 block must appear in every minimal form.

A candidate expression is a valid form only if every product term implies the function, meaning all its minterms lie in the on-set, and the terms together cover every on-set minterm. Overlap between terms is allowed, but a term that includes an off-set minterm makes the expression wrong.

Number base conversion

A numeral (d_k\dots d_1d_0)_r in base r equals \sum_i d_i r^i, and each digit must satisfy 0\le d_i\le r-1. The smallest admissible base for a given numeral is therefore one more than its largest digit. For example, (247)_8 is not valid in base 7, and its value in decimal is 2\cdot8^2+4\cdot8+7=167.

To check whether two numerals written in different bases denote the same quantity, expand each as a polynomial in its own base and compare the results. Candidate bases are tested in order, starting above the largest digit that appears in either numeral.

Boolean algebra equivalence

Two Boolean expressions are equivalent when they take the same value for every combination of inputs. Equivalence is shown by applying identities or by comparing truth tables.

• Absorption — x+xy=x, so any term that already contains x as a factor adds nothing.
• Distributive law — (x+y)(x+z)=x+yz, obtained from x+xz+xy+yz by absorption.
• Complement-absorption — x+\overline{x}y=x+y.

To show that two expressions are not equivalent, it is enough to find one input combination where they differ. For instance, x+yz and x+z differ at x=0, y=0, z=1, where the first gives 0 and the second gives 1.

CMOS NOT gate implementation

A CMOS inverter pairs a pMOS pull-up transistor with an nMOS pull-down transistor. Its noise margins are NM_H=V_{OH}-V_{IH} and NM_L=V_{IL}-V_{OL}. They depend on the switching threshold V_M, which moves with the ratio of the pMOS and nMOS strengths. The two margins are therefore equal only for a particular sizing, and they are not equal in general. Sizing is a design choice, not a property that forces the margins to match.

Dynamic power is consumed when the load capacitance is charged and discharged, P_{dyn}=\alpha C_L V_{DD}^2 f, so it is not zero during switching. Static power is ideally zero because one transistor is off in each steady state.

With the input at logic high, V_{in}=V_{DD}, the pMOS is off, the output is pulled near 0 V, and the nMOS has V_{GS}=V_{DD} with a small V_{DS}. Since V_{DS}<V_{GS}-V_T, the nMOS operates in the linear (triode) region.

Electron mobility \mu_n sets the transconductance parameter k_n'=\mu_n C_{ox} and therefore the drive current that discharges the load, so higher mobility shortens the switching time.

Universal gate realization of basic gates

A universal gate can realise every Boolean function. Consider a two-input gate with output Y=A+\overline{B}, together with the constants 0 and 1. The basic gates are built as follows.

• NOT — setting A=0 gives Y=\overline{B}, so the gate acts as an inverter.
• OR — A+B=A+\overline{\overline{B}}, so OR is the gate with its B input first inverted by the NOT just built.
• AND — De Morgan's law gives AB=\overline{\overline{A}+\overline{B}}, so AND is built from NOT and OR.
• NAND and NOR — each is the complement of AND or OR, and a NOT is available, so both can be realised.