Processors & memory formulas

A ROM with n address inputs and m data outputs stores a complete truth table, so it implements any m Boolean functions of the same n variables: each address is one input combination and each word holds the m outputs for it. Example: a squarer for a 4-bit unsigned input (largest output $15^2=225$, which needs 8 bits) needs a $16\times 8$ ROM, 128 bits.

R = number of rows (one refresh operation per row); $T_{\text{ref}}$ = period within which every row must be refreshed. Spread evenly, one row is refreshed every $t_{\text{row}}$.

$t_{rc}$ = duration of one row-refresh cycle. The same fraction applies to burst refresh (all rows back to back) and to distributed refresh.

n = number of address lines, m = number of data lines (word size). Divide by 8 for bytes.

Address lines depend only on the number of words; data lines depend only on the word size.

Target memory $W\times B$ (words $\times$ bits) built from $w\times b$ chips: $W/w$ banks, each $B/b$ chips wide. If either ratio is not a whole number, round it up.

For a contiguous block with $W/w$ a power of 2: the k decoder inputs are the address lines immediately above the chip's own lines, and each decoder output drives the $\overline{\text{CS}}$ of one bank.

Size in addressable units: 1K = 400H, 2K = 800H, 4K = 1000H, 8K = 2000H, 16K = 4000H, 32K = 8000H.

u = number of address lines that are neither chip lines nor used in the select logic.

$N_{\text{op}}$ distinct operations coded in one fixed-width opcode field.

p opcode bits, r register fields for $N_R$ registers, and a bits of address, displacement or immediate fields (a memory-address field for $2^a$ addressable units needs a bits).

Fixed-length instructions in two classes. The class with more operands has a p-bit opcode and $N_2$ instructions, using $N_2$ of the $2^p$ patterns; each unused pattern is extended by the f bits of the operand field that the class with fewer operands does not need, giving at most $N_{1,\max }$ instructions in that class.

${\text{PC}}_{\text{next}}$ = address of the instruction after the branch (the PC has already advanced during fetch), unless a question states that the offset is added to the branch's own address; d = q-bit 2's-complement offset in bytes. If the offset counts words or instructions, multiply d by their size first.

$\overline{B}$ = bitwise complement of B; the +1 enters as the adder's carry-in. The adder's carry-out is then 1 when $A\ge B$ (unsigned), that is, it is the complement of the borrow; some processors, the 8085 among them, store the borrow in the carry flag instead.

n-bit addition: $C_{n-1}$ = carry into the MSB (bit n−1), $C_n$ = carry out of the MSB. Equivalently, an addition overflows when both operands have the same sign and the result has the opposite sign, and adding operands of opposite sign never overflows; a subtraction $A-B$ overflows when A and B have opposite signs and the result's sign differs from A's.

An 8-bit signed value runs from −128 to +127.

$N_{\text{sig}}$ control signals (one bit each); c = condition-select bits $=\lceil {\log }_2(\text{number of selectable conditions, counting unconditional})\rceil$; a = next-address bits $=\lceil {\log }_2(\text{control-memory words})\rceil$.

A group of k mutually exclusive signals; the extra code means none of them is active. If a question states that one signal of the group is always active, use $\lceil {\log }_{2}k\rceil$.

In bits.

IC = instructions executed, CPI = average clock cycles per instruction. Speed comparisons use the ratio of execution times. MIPS rating $=f_{\text{clk}}/(\text{CPI}\times 10^6)$.

${\tau }_i$ = delay of stage i, ${\tau }_{\text{latch}}$ = inter-stage register delay.

k cycles for the first instruction to pass through, then one completion per cycle; no stalls.

$t_{\text{np}}$ = non-pipelined time per instruction; unless stated, the sum of the stage delays without latch delay. As $n\to \infty$, $S\to t_{\text{np}}/\tau$.

Holds when $t_{\text{np}}=k\tau$: equal stage delays, no latch overhead, no stalls. With $t_{\text{np}}$ taken as the sum of the stage delays, the speed-up of a k-stage pipeline never exceeds k.

Efficiency is defined here as S/k. For balanced stages with no latch delay and no stalls it equals $n/(k+n-1)$, the fraction of stage slots doing useful work; some questions define efficiency directly as that fraction, so check which is meant. Throughput is in instructions per unit time.

Sum each hazard's frequency times its stall cycles. For branches the term is $f_{\text{br}}\times p\times b$, with p = fraction of branches that pay the penalty (taken, or mispredicted) and b = penalty in cycles.

$N_{\text{stall}}$ = total stall (bubble) cycles in the run, for an in-order pipeline in which each stall cycle delays every later instruction by one cycle.

The first form is general; the second assumes $t_{\text{np}}=k\tau$.

s = number of the stage (IF = 1) at the end of which both the branch outcome and the target are known: resolved in ID gives 1 bubble, in EX 2, in MEM 3.

A 6 MHz crystal gives a 3 MHz clock and a T-state of 333.3 ns. Execution time = total T-states × T.

MVI C, N (7); LOOP: DCR C (4); JNZ LOOP (10 when taken, 7 on the final pass). N = 1 to 255; loading 00H gives 256 passes (use N = 256), because DCR takes 00H to FFH.

LXI B, N (10); LOOP: DCX B (6); MOV A, C (4); ORA B (4); JNZ LOOP (10/7). The MOV and ORA are needed because DCX sets no flags. N = 1 to 65535; loading 0000H gives 65536 passes (use N = 65536).

RST n (n = 0 to 7) gives 0000H, 0008H, ..., 0038H. The hardware interrupts follow the same rule with fractional n: TRAP (4.5) → 0024H, RST 5.5 → 002CH, RST 6.5 → 0034H, RST 7.5 → 003CH.

Classic 8051: one machine cycle = 12 oscillator periods. In mode 1 the 16-bit timer counts up from $N_0$ and sets its overflow flag TF on FFFFH → 0000H; this delay ignores the instructions that load and start the timer. At 12 MHz, a 1 ms delay needs 1000 counts, so load 65536 − 1000 = 64536 = FC18H.

$f_{\max }$ = highest frequency in the filtered signal, $f_s$ = sampling rate per channel, $N_{\text{ch}}$ channels sharing one ADC. The converter must also satisfy $f_{\text{ADC}}\le 1/(t_{\text{acq}}+t_{\text{conv}})$ (sample-and-hold acquisition time plus conversion time).

Convention used here: $V_{FS}$ is the full input range, divided into $2^n$ steps; the $\Delta /2$ error bound is for a rounding converter. If a question defines $V_{FS}$ as the voltage of the all-ones code (common for DACs), use $\Delta =V_{FS}/(2^n-1)$.

Full-scale sinusoidal input (peak-to-peak equal to the full range $V_{FS}$, with $\Delta =V_{FS}/2^n$), quantisation noise uniformly distributed with power ${\Delta }^2/12$. Each extra bit adds about 6 dB.

Successive approximation: one clock per bit (some devices add a cycle; follow the question). Flash: one comparator per threshold, the fastest type. A counting (ramp) ADC needs up to $2^n-1$ clocks.