Digital Electronics and Embedded Systems

Boolean function minimization

Boolean function minimization means rewriting a function in an equivalent form that uses the fewest terms and, among those, the fewest literals. Start from the canonical form. A sum of minterms lists every input combination that makes the output 1, and a product of maxterms lists every combination that makes the output 0. To convert a product of sums into minterms, find the input values that make each sum factor equal to 0. Those values are the zeros of the function, and the remaining rows are its ones.

Three identities do most of the work. Absorption gives A+AB=A and A+\overline{A}B=A+B. Consensus removes a term that is already covered by two others, as in AB+\overline{A}C+BC=AB+\overline{A}C. De Morgan's theorems give \overline{AB}=\overline{A}+\overline{B} and \overline{A+B}=\overline{A}\,\overline{B}. A NAND output is therefore the sum of complemented inputs, so two forms of the same output can be equal without looking identical. A function can be complemented, simplified, and complemented back, which is often the fastest route when the complement is simpler.

In a NOR network, complementing both inputs of a NOR gate yields the AND of the original variables, since \overline{\overline{A}+\overline{B}}=AB. Tracing each gate with this rule reduces the network to a single expression.

On a Karnaugh map, group adjacent 1s into rectangles whose sizes are powers of two. Each largest possible group is a prime implicant. An essential prime implicant covers at least one minterm that no other prime implicant covers, and it must appear in the minimal form. The remaining minterms are covered with the fewest prime implicants. A term that covers only minterms already covered by others is redundant, even if it has fewer literals than other terms.

Groups of two, four, or eight minterms that differ in one, two, or three variables eliminate those variables. For example, \sum m(1,3,5,7) on three variables equals C, because the four minterms all have C=1.

• Canonical form — a sum of minterms or product of maxterms that lists every row of the truth table. e.g., F=\sum m(0,3) on two variables is \overline{A}\,\overline{B}+AB.
• Prime implicant — a product term that cannot be reduced further while still implying the function. e.g., \overline{A} in \overline{A}B+\overline{A}\,\overline{B} is a prime implicant.
• Redundant term — a term whose minterms are all covered by other terms, so it may be removed.

ADC resolution and quantization

The resolution of an ADC is the smallest change in the analog input that changes the output code. For an N-bit converter with full-scale voltage V_{FS}, the step size is usually written as q=V_{FS}/2^N. Some texts instead use V_{FS}/(2^N-1) so that the full-scale input corresponds to the all-ones code. The convention given in a problem decides which formula applies, so check the definition before calculating.

Quantization error is the difference between the actual input and the nearest output level. For an ideal uniform quantizer the error is bounded by \pm q/2, so a 10-bit converter in which the step is 10 mV has a maximum error of \pm 5 mV.

The number of bits needed is found from the number of distinguishable levels L=V_{FS}/\Delta, where \Delta is the required resolution. The smallest integer N satisfying 2^N \ge L is the answer. Data rate follows from sampling and word length. A band-limited signal of bandwidth B is sampled at the Nyquist rate f_s=2B, and an N-bit output stream carries N f_s bits per second.

An MSB changes only when the input crosses the mid-scale level, and the LSB toggles at every quantization step. Therefore a change of one step does not always flip the MSB, but it always flips the LSB.

For an ideal N-bit converter driven by a full-scale sine wave, the signal-to-quantization-noise ratio is \text{SQNR}=6.02N+1.76 dB. Each additional bit adds about 6 dB.

• Resolution (LSB) — the step size q; not the same as accuracy, since gain and offset errors are separate. e.g., an 8-bit converter for 0 to 5 V has q=5/256\approx 19.5 mV.
• Quantization error — the error from rounding to the nearest code, bounded by \pm q/2 for an ideal converter.
• SQNR — signal-to-quantization-noise ratio, 6.02N+1.76 dB for a full-scale sine input.

Memory interfacing and address decoding

A memory block of 2^k byte locations uses k address lines to select a location inside the chip. The remaining higher-order address lines are decoded to generate the chip select. A 16 KB memory has 2^{14} locations, so it uses A13 to A0, and A19 to A14 (or the upper lines of the bus) are available for decoding.

A block of size 2^k bytes can be mapped only to base addresses that are multiples of 2^k. A 16 KB block therefore starts at a multiple of 4000\text{H}. A start address that is not such a multiple cannot be mapped contiguously when only the upper address lines are decoded.

The active-low chip select is built by ORing the complemented address bits that must be 0 for the block to be selected. For example, a block enabled only when A15 = 0 and A14 = 1 has \overline{CS}=A_{15}+\overline{A_{14}}. Note that an OR of true bits asserts the chip select when any of those bits is 1, so the bits must be complemented.

A memory whose data width is 8 bits can be connected to either byte lane of a 16-bit bus. It can be accessed through the upper lanes D15 to D8 with byte transfers, so a data-width mismatch alone does not prevent interfacing.

• Full decoding — all upper address lines are decoded, so each location has exactly one address.
• Partial decoding — some upper lines are ignored, which makes the same chip appear at several addresses (aliasing).
• Example — an 8 KB block at 6000H is selected when A15 = 0, A14 = 1 and A13 = 1, so \overline{CS}=A_{15}+\overline{A_{14}}+\overline{A_{13}}.

Multiplexer function realization

A 2^n:1 multiplexer with select lines S_{n-1}\ldots S_0 and data inputs I_i computes F=\sum_i m_i(S)\,I_i, where m_i(S) is the minterm of the select lines that equals i. The MSB of the select code is the most significant select line, and the LSB is the least significant. Confusing these two selects gives the wrong function.

To realize a function, write each data input as a function of the variables that are not on the select lines. Each input then contributes the minterms of the select lines that point to it, multiplied by that input function. This method is equivalent to a minterm table and is faster than full simplification.

For example, let S_1=A, S_0=B, I_0=C, I_1=0, I_2=1 and I_3=\overline{C}. Then F=\overline{A}\,\overline{B}C+A\overline{B}+AB\overline{C}. A constant 0 input contributes nothing, and a constant 1 input contributes its full minterm.

A MUX can be cascaded. An outer MUX selects between the output of an inner MUX and a constant or another input. For instance, a 4:1 MUX with data inputs 0, 1, 1, 0 realizes P\oplus Q, and an outer 2:1 MUX selected by R can pass this XOR or a constant to give Y=R+(P\oplus Q).

• Select line order — S_1 is the MSB and S_0 is the LSB, so I_2 is selected by S_1S_0=10.
• Data input as function — an input may be a variable, a constant, or a logic expression, and each one is ANDed with its select minterm.

Synchronous sequential circuit analysis

To analyze a synchronous sequential circuit, first write the input (excitation) equation for each flip-flop from the logic diagram. Then use each flip-flop's characteristic equation to compute the next state from the present state and inputs. All flip-flops share one clock edge, so every next state is computed from the present values, not from values produced during the same edge. Tabulate the present-to-next state transitions and draw the state diagram starting from the reset state.

The characteristic equations are Q^+=D for a D flip-flop, Q^+=T\oplus Q for a T flip-flop, and Q^+=JQ'+K'Q for a JK flip-flop. The JK flip-flop with J=K=1 toggles, and with J=K=0 holds.

A multiplexer in front of a flip-flop is a common hold/shift control. With the select line at 0 the flip-flop holds its value, and with the select at 1 it takes the value from the previous stage, so a chain of such stages forms a shift register. The output is a function of the present state for a Moore machine, and of the present state and inputs for a Mealy machine.

After the transitions are tabulated, the output at each state is read from the output logic. Only states reachable from reset matter for the sequence, while unreachable states may still affect the design.

• Excitation equation — the input expression of a flip-flop, such as a function of the present state that is applied to J or T.
• Next state — the value Q(t+1) obtained by substituting the excitation into the characteristic equation.
• State sequence — the path the circuit follows from reset, used to find the cycle and the output sequence.

Synchronous counter modulus analysis

The modulus of a counter is the number of distinct states in its main cycle. To find it, compute the next-state table from the excitation equations, starting from each possible present state, and follow the transitions until a state repeats. The number of states on the repeating loop is the modulus.

A self-correcting counter has unused states that flow into the main cycle after one or more clocks. A counter in which an unused state forms its own cycle does not function as a counter, because it can lock up. A counter may therefore look like a modulus-N counter from reset and still fail if its unused states are not checked.

A synchronous counter that is forced to return to zero when it reaches a chosen state has a modulus equal to the number of states between zero and that state, inclusive of zero. Using the next-state logic instead of an asynchronous clear avoids glitches and gives the modulus directly.

If the counter's terminal output has a period of N clock cycles, the output frequency is f_{out}=f_{clk}/N. A control input may change the feedback path so that the same counter has different cycle lengths, and the output frequency changes accordingly.

• Modulus — the cycle length N of the counter, so that a mod-N counter divides the clock frequency by N.
• Unused state — a state not in the main cycle; its behavior decides whether the counter is self-correcting.
• Terminal count — the state at which the cycle restarts, often used as a carry output.

Shift register operation

A shift register moves its stored bits one position per clock edge. In a right-shift register each stage takes the value of the stage on its left, the leftmost stage takes the serial input, and the rightmost bit leaves as the serial output. A left shift works the same way in the opposite direction. The shift control selects whether the register shifts or holds its contents.

To trace a shift register, write down the state before each clock edge and move every bit to its neighbor at once. The serial input enters the vacant end, and the bit that leaves the register is lost unless it is recorded.

For example, if a 4-bit right-shift register holds 1001 and the serial input is 0, after one clock it holds 0100. The leftmost bit is replaced by the serial input, the other bits move one place right, and the rightmost 1 is discarded.

Several shift registers can be connected so that the serial output of one feeds the serial input of the next, which passes data from one register to another. A feedback path, often through an XOR gate taken from the stored bits, turns the register into a linear feedback shift register that produces a long pseudo-random sequence. Each new value fed back is the XOR of selected stored bits.

• Serial shift — each clock moves the data by one place, so n clocks move a bit through n stages.
• Serial vs parallel — a serial input fills the register bit by bit, while a parallel load sets all stages at once.
• Feedback — XOR of stage outputs fed to the input forms a sequence generator rather than a simple delay line.