Number Representations, Boolean Minimisation and Combinational CMOS Logic

A fixed-point number is an integer with an agreed binary point, and it is the format almost all real signal processing hardware actually uses, so it is worth being fluent in. In the common Q7 form a byte holds one sign bit and seven fractional bits, so the representable values run from −1.0 to +1 − 2^(−7) = 0.9921875 in steps of 2^(−7) = 0.0078125. The spacing is constant across the whole range — that is the defining property, and it is why a fixed-point filter has a flat quantisation noise floor. The price is range: multiply two Q7 numbers and the product is Q14, needing 16 bits, and every practical implementation must then decide whether to round, truncate or saturate.

A floating-point number buys range by making the spacing grow with magnitude. IEEE 754 single precision spends 32 bits as 1 sign, 8 exponent, 23 significand, stores the exponent biased by 127, and does not store the leading 1 of a normalised significand at all — that implied bit is a free 24th bit of precision. Encode +0.15625 and every step is exact, which makes it a good pattern to be able to reproduce: 0.15625 = 5/32, which is 0.00101 in binary, which normalises to 1.01 × 2^(−3). So the sign bit is 0, the exponent field is −3 + 127 = 124 = 01111100, and the significand field is 01 followed by twenty-one zeros. The complete word is 0 01111100 01000000000000000000000. Reverse the process on any pattern by remembering that the stored exponent E means a scale of 2^(E − 127) and the stored fraction f means a significand of 1.f.

Boolean algebra is worth learning as a set of moves with a purpose, and for EC the purpose is usually transistor count. In static CMOS, one literal in a product term is one nMOS transistor in the pull-down network and one pMOS in the pull-up network, so deleting a literal deletes two transistors and deleting a term deletes a whole branch. That makes literal count, not term count, the honest measure of what a simplification bought. The identities that keep paying are few: De Morgan, (A + B)′ = A′B′ and (AB)′ = A′ + B′, which is how you move between an AND-OR form and the NAND-only or NOR-only form a CMOS library actually offers; absorption, A + AB = A; the redundancy law A + A′B = A + B; and consensus, AB + A′C + BC = AB + A′C, whose middle term is the one a Karnaugh map shows as covered twice over.

Two structural facts round the algebra off. NAND and NOR are each functionally complete: tie a NAND's inputs together and it is an inverter, follow a NAND with that inverter and it is an AND, and De Morgan supplies OR — so a whole design can be built from one cell type, which is exactly what a real standard-cell library prefers because one cell means one characterised delay and one mask set. And XOR is not a primitive: A ⊕ B = AB′ + A′B = (A + B)(AB)′, which matters because the arithmetic circuits later in this chapter are built almost entirely from XOR, and its cost in transistors is the cost of the adder.

A Karnaugh map is a truth table redrawn so that physically adjacent squares differ in exactly one variable, which is why a rectangular group of 2^k ones can be written as a product term with k variables deleted. Take f(A,B,C,D) = Σm(1,3,7,11,15) with don't cares at 0, 2 and 5, and lay the map out with AB down the side in the order 00, 01, 11, 10 and CD across the top in the same order. Row AB = 00 holds minterms 0, 1, 3, 2 in that column order; row 01 holds 4, 5, 7, 6; row 11 holds 12, 13, 15, 14; row 10 holds 8, 9, 11, 10. Fill it in and three groups appear: the column CD = 11 is all ones and gives CD; the pair of columns CD = 01 and CD = 11 in the top two rows gives A′D using the don't care at 5; and the top-left square of four gives A′B′ using the don't cares at 0 and 2.

Now separate the two questions a map answers. A prime implicant is a group that cannot be made any larger, which is a local fact about one group: CD cannot grow to D because that would need minterms 9 and 13, and neither is a one or a don't care. This function has exactly three prime implicants — CD, A′D and A′B′. An essential prime implicant is one that is the only cover of some minterm, which is a global fact about the whole function: minterm 11 sits in CD alone, so CD is essential, while minterm 1 sits in both A′D and A′B′, so neither of those is forced. The consequence is that this function has two different minimal expressions, f = CD + A′D and f = CD + A′B′, each with two terms and four literals, and both are fully correct answers. A question that says the minimal form has assumed something the map does not guarantee.

One more map is worth carrying, because it teaches a pattern rather than a procedure. g(A,B,C,D) = Σm(0,2,5,7,8,10,13,15) looks scattered when you write the minterms out, and on the map it forms two groups of four that no beginner spots: every one has either B = 0 with D = 0, or B = 1 with D = 1. So g = B′D′ + BD, which is (B ⊕ D)′ — the XNOR of two of the four variables, with A and C irrelevant. A checkerboard on a Karnaugh map is always an XOR or XNOR, never a two-literal product, and recognising it saves the minute a question spends trying to draw rectangles round diagonal ones.

This is the sub-item the EC syllabus names and a computer-science digital section does not, so treat it as compulsory rather than as background. A static CMOS gate is two networks between the output node and the rails. The pull-down network is nMOS transistors between the output and ground, and it conducts when the output should be 0. The pull-up network is pMOS transistors between the output and V_DD, and it conducts when the output should be 1. The two are duals: series in one is parallel in the other. Because an nMOS conducts when its gate is high and pulls the output low, the gate is inherently inverting — series nMOS realises (A·B)′ and never A·B, and there is no static CMOS AND gate at all, only a NAND followed by an inverter.

Counting transistors then becomes mechanical, and it is the most common question type on this sub-item. An n-input NAND or NOR takes 2n transistors, one nMOS and one pMOS per input. A complex gate takes two transistors per literal in its expression, provided the expression is written in the inverted form the gate naturally produces. So Y = (A·(B + C))′ needs a pull-down of A in series with B parallel C, three nMOS; its dual pull-up is A in parallel with B in series with C, three pMOS; six transistors in one gate, and one gate delay. Ask for the non-inverted Y = A·(B + C) and you must add an inverter, so eight transistors and two gate delays — the standard reason a designer pushes inversions back through a network with De Morgan until the bubbles cancel rather than paying for them.

Delay follows from the same picture, and one number is enough to make it concrete. Model the conducting network as an average on-resistance R charging or discharging a load capacitance C_L. The output moves exponentially, so the fifty-per-cent point arrives after 0.69·R·C_L. With R = 2 kΩ and C_L = 50 fF, that is 0.69 × 2000 × 50 × 10^(−15) = 69 ps. Two readings matter. First, delay is proportional to load, which is why fanout appears in every timing question. Second, a two-input NAND has two nMOS in series, so its effective R is about twice an inverter's for the same width — that is the origin of the rule of thumb that a gate with more inputs is slower, and it is the circuit-level fact behind the critical-path arithmetic in the next chapter.

A half adder takes two bits and produces S = A ⊕ B and C_out = A·B. A full adder takes a carry in as well, and its two outputs are S = A ⊕ B ⊕ C_in and C_out = A·B + C_in·(A ⊕ B). That second form of the carry is worth writing exactly as shown, because it names the two mechanisms every fast adder exploits: a stage generates a carry when A·B = 1 regardless of what arrives, and it propagates an incoming carry when A ⊕ B = 1. Cascade n full adders with each carry-out wired to the next carry-in and you have a ripple-carry adder — minimal hardware, and a delay that grows linearly with the word length.

Put numbers on that, because the exam does. Suppose each full adder needs 0.8 ns from its carry-in to its carry-out and 0.6 ns from its carry-in to its sum. In a 16-bit ripple-carry adder the carry produced by stage 0 appears at 0.8 ns, the carry into stage 15 therefore appears at 15 × 0.8 = 12.0 ns, and that stage's sum bit settles 0.6 ns later, at 12.6 ns. The carry-out of the whole adder is later still, at 16 × 0.8 = 12.8 ns, so 12.8 ns is the honest worst-case delay of the block and the number a timing question wants. Notice what the answer does not depend on: the data. The worst case is a pattern that makes every stage propagate — 0000000000000001 plus 1111111111111111 is the classic — while typical data settles far sooner, which is why a synchronous design must be clocked for the worst case and never for the average.

A code converter is a combinational block that re-labels the same information, and the one EC asks about most is binary to Gray, because Gray code is what a shaft encoder or a flash ADC actually emits. Its defining property is that consecutive codes differ in exactly one bit, so a reading taken while the encoder is between two positions can be wrong by at most one step instead of by anything at all. The converter is pure XOR: G_3 = B_3 and G_i = B_(i+1) ⊕ B_i for the rest. Convert 1011, which is decimal 11: G_3 = 1, G_2 = 1 ⊕ 0 = 1, G_1 = 0 ⊕ 1 = 1, G_0 = 1 ⊕ 1 = 0, so the Gray code is 1110. Going back is a running XOR in the other direction: B_3 = G_3 = 1, then B_2 = B_3 ⊕ G_2 = 0, B_1 = B_2 ⊕ G_1 = 1, B_0 = B_1 ⊕ G_0 = 1, recovering 1011. Note the structural difference, because it is examinable: binary to Gray needs n − 1 independent XOR gates and has one gate delay, while Gray to binary is a chain and its delay grows with n.

A multiplexer selects one of 2^k data inputs with k select lines, and Shannon expansion turns it into a general logic element. Drive the selects with some of the variables; each data input then carries the residual function of whatever variables are left. Realise f(A,B,C) = Σm(1,2,4,7) on a 4-to-1 multiplexer with A and B as selects. For AB = 00 the map holds minterms 0 and 1, whose outputs are 0 and 1, so the residual is C. For AB = 01, minterms 2 and 3 give 1 and 0, so the residual is C′. For AB = 10, minterms 4 and 5 give 1 and 0, so C′ again. For AB = 11, minterms 6 and 7 give 0 and 1, so C. The four data inputs are therefore C, C′, C′, C — and the function itself was A ⊕ B ⊕ C, the odd-parity function, which is worth recognising from its minterm list alone.

A decoder is the same idea run backwards: an n-to-2^n decoder raises exactly one output for each input combination, so it emits every minterm at once. One OR gate across the selected outputs then realises any single function of n variables, and several OR gates realise several functions of the same inputs without repeating any logic — which is precisely how a small read-only memory implements a truth table, and the link forward to the memories in the next chapter. Two practical details matter in questions. Real decoders are usually active low, so the selected line goes to 0 and the collecting gate becomes a NAND rather than an OR. And the enable input is what allows cascading: a 3-to-8 decoder with an enable can be grown into a 4-to-16 by using the fourth address bit to enable one of two devices, which is the same trick that selects one memory chip out of several.