Digital Logic

Number systems and conversion

Positional notation in any base, converting between decimal, binary, octal and hexadecimal (integers and fractions), when a fraction stops, and how many digits or bits a number needs.

Sign-magnitude, 1's and 2's complement

How a fixed number of bits represents negative numbers: the three systems, their ranges, the two zeros, negation, sign extension, shifts, excess-K and the radix complements used in subtraction.

Fixed-point arithmetic and overflow

Adding and subtracting fixed-width numbers: the carry, overflow, sign and zero flags, how to detect overflow, signed and unsigned comparison from the flags, the width of sums and products, and fixed-point fractions (Q formats).

IEEE 754 floating point

The single and double precision formats: sign, biased exponent and fraction fields, normal numbers, denormals, zero, infinity and NaN, ranges and precision, rounding, and how to encode and decode a number by hand.

Boolean algebra and identities

The algebra of two values: postulates, the laws and identities (De Morgan, absorption, consensus), duality versus complement, XOR, the count of Boolean functions, and algebraic simplification.

SOP, POS, minterms and maxterms

The standard ways to write a Boolean function: minterms and maxterms with their numbering, canonical sum of minterms and product of maxterms, converting between them, complements, don't cares and counting.

Logic gates and universal gates

The basic gates and their truth tables, why NAND and NOR are universal, building NOT, AND, OR and XOR from NAND only, two-level NAND-NAND and NOR-NOR circuits, gate counting and fan-in.

Karnaugh maps

Minimising a Boolean function on a Karnaugh map: Gray-code layout, groups and wrap-around, prime and essential prime implicants, don't cares, products of sums, and the situations where the answer is not unique.

Design of combinational circuits

What makes a circuit combinational, how to analyse one and how to design one from a specification: truth table, don't cares, minimisation, shared terms across outputs, cost and delay, and two-level versus factored forms.

Adders and subtractors

Half and full adders and subtractors, the ripple-carry adder and its delay, carry lookahead, the adder-subtractor with overflow detection, the incrementer and the BCD adder.

Multiplexers and demultiplexers

Selecting one of 2^n inputs with n select lines, the output equation, building larger multiplexers from smaller ones, implementing Boolean functions with a multiplexer using Shannon expansion, universality, and the demultiplexer.

Decoders, encoders and comparators

Decoders (n to 2^n, with enable, active-low, built from smaller ones), implementing functions with a decoder and OR gates, encoders and the priority encoder, and magnitude comparators.

Latches and flip-flops

The memory elements of digital circuits: the SR latch, the gated and D latch, edge-triggered D, JK and T flip-flops, characteristic tables and equations, the race-around problem, setup and hold times.

Excitation tables and flip-flop conversion

The excitation table of each flip-flop type (which inputs produce a wanted transition), and the procedure for building one type from another, with all twelve conversions derived and checked.

Registers and shift registers

Registers built from D flip-flops, parallel load, the four shift-register types, the universal shift register, shifts and rotates and what they mean arithmetically, and serial addition.

Synchronous and asynchronous counters

Counters from flip-flops: ripple (asynchronous) counters and their glitches and delay, synchronous counters and their design with excitation tables, modulus and frequency division, up-down counters, and the ring and Johnson counters.

FSM design: Mealy and Moore

Finite state machines as sequential circuits: Moore and Mealy outputs and their timing, state diagrams and tables, analysis and design procedures, state reduction, state assignment, and the clock period limit.

Tabular method (Quine-McCluskey)

Minimising a Boolean function without a map: list the minterms in binary, group them by the number of ones, combine neighbouring groups that differ in one bit until nothing combines, read off the prime implicants, build the prime implicant chart, take the essential primes, delete dominated rows and columns, and settle what is left with Petrick's method; don't cares, products of sums, ties between minimum covers, and what the method costs.

Floating-point arithmetic and precision

Adding, subtracting and multiplying IEEE 754 numbers: the result is the exact answer rounded to the nearest float (ties to even), obtained in hardware by aligning the exponents, adding with guard, round and sticky bits, normalising and rounding; special values, the spacing of floats and when a small number is lost, cancellation, and why floating-point addition is not associative.