Digital Logic and Number Representation

IEEE 754 floating-point representation

IEEE 754 single precision stores a real number in 32 bits: a sign bit S, an 8-bit exponent field E, and a 23-bit fraction field F. For a normalized number the value is (-1)^{S} \times 1.F \times 2^{E-127}, where 127 is the bias that keeps the stored exponent unsigned. The significand 1.F has an implicit leading 1 that is never stored, and the fraction bits f_1 f_2 \ldots f_{23} contribute f_1 2^{-1} + f_2 2^{-2} + \cdots on top of that 1. Decoding follows a fixed order: read the sign bit, convert the exponent field to decimal and subtract 127, then build the significand from the fraction bits. When a value is given in hexadecimal, first expand it to 32 bits; the leftmost bit is the sign and the next eight bits form the exponent. Once register contents are decoded into exact real values, a candidate identity such as C = A + B can be tested directly, because a false identity shows up as a nonzero difference. Linear relations among decoded values are checked in the same way.

Special encodings decide the extreme values:

• Bias — the stored exponent equals the true exponent plus 127, so a true exponent of 3 is stored as 130 and a true exponent of -2 is stored as 125.
• Zero and denormalized numbers — an exponent field of all zeros marks zero or a denormalized value with no implicit leading 1, so it is never a normalized number.
• NaN and infinity — an exponent field of all ones marks infinity when the fraction is zero and NaN when the fraction is nonzero, so an all-ones exponent is never a finite number.
• Largest finite value — exponent 11111110 with all fraction bits set gives (2 - 2^{-23}) \times 2^{127}, about 3.4 \times 10^{38}.
• Smallest normalized positive value — exponent 00000001 with a zero fraction gives 1.0 \times 2^{-126}, about 1.18 \times 10^{-38}, because a zero fraction means the significand is exactly 1.0.

Arithmetic on this format works through the same fields. Multiplying by a power of two changes only the exponent, so the fraction bits stay unchanged, and the sign of a product is the XOR of the operand signs. Addition first needs equal exponents: the smaller operand's significand is shifted right by the exponent difference, the significands are added, and the result is normalized and rounded, which can discard low-order bits. For example, 1.0 \times 2^{3} + 1.0 \times 2^{1} becomes 1.0 \times 2^{3} + 0.25 \times 2^{3} after alignment, giving 1.25 \times 2^{3}.

Boolean algebra simplification and complement

Boolean simplification rests on a few identities that every reduction uses. Absorption gives X + XY = X and X + \bar{X}Y = X + Y. Consensus removes a redundant term: XY + \bar{X}Z + YZ = XY + \bar{X}Z, because YZ is covered by the other two terms. De Morgan's laws give the complement of any expression, \overline{XY} = \bar{X} + \bar{Y} and \overline{X + Y} = \bar{X}\bar{Y}, and the distributive law expands a product of sums. To read a function off a gate diagram, write the output of each gate as an expression and then simplify; De Morgan converts a NAND into an OR of complements, and absorption then shortens the sum.

A don't-care minterm is an input combination whose output the specification leaves open, so a minimal form may use it freely. When a function is fixed only on some combinations, the literal count of the minimal sum-of-products depends on how the open combinations are assigned.

The sum-of-minterms list and the product-of-maxterms list use the same index set in complementary ways: a function F = \sum m(S) equals \prod M(S'), where S' is the set of indices not in S. The zeros of a function therefore give its maxterm list. A majority function, which is 1 when at least two inputs are 1, illustrates this and also shows dependence: a variable matters if some setting of the other variables makes changing it change the output.

A candidate minimal sum-of-products is verified by expanding each product term into minterms. The union must equal the on-set exactly: an expression that covers an extra 0-cell or leaves a 1-cell uncovered is wrong, even if it has fewer terms.

The exclusive-OR P \oplus Q = P\bar{Q} + \bar{P}Q is 1 when the inputs differ, and its complement XNOR is 1 when they are equal. Complementing one input of an XOR complements the output, so \bar{P} \oplus Q = \overline{P \oplus Q}, while complementing both inputs leaves the XOR unchanged.

• Absorption — X + XY = X removes a term that is already covered by a shorter term.
• Consensus — the term YZ in XY + \bar{X}Z + YZ can be dropped.
• Complement — apply De Morgan's laws to the whole expression, not term by term.

Multiplexer implementation of Boolean functions

A 2^n-to-1 multiplexer routes the data input I_k to its output, where k is the binary number formed by the select lines. A function of n + m variables can be built by connecting the m remaining variables, their complements, or the constants 0 and 1 to the data inputs. This follows Shannon's expansion, F = \bar{x}\,F_{x=0} + x\,F_{x=1}, in which each cofactor is a function of the remaining variables.

The procedure has three steps. Choose the select variables, compute for each select setting the cofactor of F as a function of the leftover variable, and place each cofactor (0, 1, the variable, or its complement) in the data input whose index matches the select setting. Then check the result against the truth table. A two-level tree works the same way: a second-level multiplexer chooses between two first-level outputs, so the overall function is a composition of these cofactors.

If two data inputs of a multiplexer carry the same constant, the output for those select settings is that constant regardless of the other select lines. Counting the input combinations that give a fixed output therefore reduces to counting the cases in which the relevant data input is selected.

When each function is written as its list of 1-minterms, gates act on sets: AND is intersection, OR is union, XOR is symmetric difference, and NOT is complement. Applying these operations to a network of gates gives the output set quickly.

A decoder combined with a multiplexer works as follows. An active-high decoder raises exactly one line for each input combination, and the multiplexer passes the data input chosen by its select lines. To count the input combinations giving output 1, count for each data input the combinations of the other variables that make it 1, then sum over the select values.

• Select line order — the first select line is the most significant bit of the index k.
• Data input — a function of the leftover variables that is connected to one multiplexer input.
• Cofactor — the function obtained by fixing some variables to 0 or 1.

Number base conversion

A number in base b with digits d_k \ldots d_0 has the value \sum_i d_i b^i, and every digit must be less than b. Digits above 9 are written as letters: A is 10, B is 11, C is 12, D is 13, E is 14, and F is 15. A conversion between two non-decimal bases is done in two steps: expand the source digits with powers of the source base to obtain the decimal value, then convert that value to the target base. A base-3 string converted this way gives a decimal value, which is then written in hexadecimal by repeated division by 16.

A digit string after the radix point has negative powers: (0.b_1 b_2 \ldots)_2 = \sum_i b_i 2^{-i}. A finite binary fraction therefore converts to a finite decimal sum, and its decimal digits can be matched term by term.

Radix changes follow the same pattern. For example, (203)_4 = 2 \cdot 16 + 0 \cdot 4 + 3 = 35, and dividing 35 by 6 gives 35 = 5 \cdot 6 + 5, so (203)_4 = (55)_6. Converting a radix-4 numeral to radix 5 is done the same way, through decimal.

When several values written in different bases are compared, convert each one to decimal and compare the results. A radix-5 value such as 224_5 has decimal value 2 \cdot 25 + 2 \cdot 5 + 4 = 64, and the same test applied to radix-7, radix-8 and hexadecimal candidates decides which are equal.

• Positional value — each digit is weighted by a power of the base, with the rightmost digit having weight b^0.
• Repeated division — dividing an integer by the target base repeatedly and reading the remainders in reverse gives the target representation.
• Hexadecimal digits — one hex digit stands for four bits, so the letters A to F must be read as 10 to 15 when comparing values.

Synchronous sequential circuit design

A synchronous sequential circuit changes its state only at the active clock edge, and its next state and outputs are functions of the present state and the inputs. A Mealy machine's output depends on both the present state and the current input, whereas a Moore machine's output depends on the state alone. A design begins by deciding what the state must remember, then writing a transition table, and finally deriving the flip-flop input equations.

A state that stores the previous input bit is often enough. For a circuit that replaces the first 1 of each run of 1s with a 0, the next state is simply the current input, t = b, and the output is y = sb, which is 1 only when the current bit and the previous bit are both 1. This output is produced on the same clock edge as the state change.

For a D flip-flop, the next state equals the D input, so D_i = Q_i^{+} must be derived from the transition table. For a T flip-flop, Q^{+} = T \oplus Q. To derive the D inputs of a saturating up/down counter, write the next state of each bit separately for input 0 and input 1, then combine the two cases using the input variable and its complement.

A state diagram may contain states that cannot be reached from the initial state; they never affect the observed behaviour. Only the cycle reached from the initial state matters when counting states.

With n flip-flops there are at most 2^n distinct states, and the number of distinct states visited before the sequence returns to the initial state equals the length of that cycle. A cycle that contains all 2^n states is called a maximal-length sequence.

• Mealy output — y = f(\text{state}, \text{input}), so the output can change within a clock period as the input changes.
• Excitation equation — the expression that gives the flip-flop input needed to reach the next state.
• Unreachable state — a state with no transition path from the initial state.

Two's complement overflow detection

An n-bit two's complement integer represents the values from -2^{n-1} to 2^{n-1} - 1. A 4-bit register therefore holds -8 to +7, and a 5-bit register holds -16 to +15. The most significant bit has weight -2^{n-1}, so a pattern with leading 1 is negative. Any integer result outside this range, whether above the maximum or below the minimum, is an arithmetic overflow or underflow.

Overflow is detected from signs or carries. For addition, overflow occurs only when both operands have the same sign and the result has the opposite sign; equivalently, it occurs when the carry into the most significant bit differs from the carry out of it. For subtraction, A - B is treated as A + (-B): overflow requires A and B to have different signs and the result to have a sign different from A.