22-Elec-A4 Digital Systems and Computers · December 2013

Question 6 of 6: Memory System Sizing and Bus Widths

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

Paper format. National Exams, December 2013 — 07-Elec-A4 Digital Systems & Computers. Three hours, closed book (one approved Casio or Sharp calculator). Six questions are printed; any five constitute a complete exam and every question is worth 12 marks, with the per-part split printed in the marking scheme on page 1 (Q1 and Q5 are 3+3+3+3; Q2 is 4+4+4; Q3 and Q6 are 6+6; Q4 is 8+2+2). An excitation table for the RS/JK/T/D flip-flops and a table of 22 basic Boolean identities are supplied on the last page. All six questions are solved below, because this set is a study resource rather than a timed sitting.

Reference texts.

M. M. Mano and M. D. Ciletti, Digital Design: With an Introduction to the Verilog HDL, VHDL, and SystemVerilog, 6th ed. — Boolean algebra and K-maps (Ch. 2–3), combinational MSI design with multiplexers and decoders (Ch. 4), synchronous sequential logic and flip-flop excitation (Ch. 5), registers and counters (Ch. 6), memory and programmable logic (Ch. 7).
J. F. Wakerly, Digital Design: Principles and Practices, 5th ed. — canonical forms, minimisation and timing hazards (Ch. 3–4), PLD architectures (Ch. 5), counters (Ch. 8).
C. Hamacher, Z. Vranesic, S. Zaky and N. Manjikian, Computer Organization and Embedded Systems, 6th ed. — bus structure and I/O (Ch. 3), polling versus interrupts (§3.2), serial interfaces (§3.5), memory system organisation and chip-select decoding (Ch. 8).

Notation used throughout. A prime and an overbar both denote complement: $\overline{A}$ in the mathematics, A′ in the figures, where SVG text cannot carry an overbar. The variable order in every K-map is the order printed in the question, with the leftmost variable as the most significant bit, so minterm and maxterm indices match the question's numbering exactly.

Question 6: Memory System Sizing and Bus Widths (12 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given.

Quantity	Part (a)	Part (b)
Total capacity	256 KB	32 KB
CPU word size	8 bits	16 bits
Accessed in one operation	8 bits	16 bits
Chips available	128K×1, 64K×4, 256K×8, 128K×4	8K×4
Convention	$1\text{K} = 2^{10} = 1024$; KB = kilobyte = 8 kilobits

Find. The chip count for each candidate device, with justification, and then the address-bus and data-bus widths for the 16-bit system.

Approach. Treat every memory build as two independent expansions. Word-width expansion places chips side by side so that their data pins concatenate to the CPU word, and is fixed by the ratio of word width to chip width. Word-count (capacity) expansion stacks those groups into banks selected by a chip-select decoder driven by the high address lines, and is fixed by the ratio of total words to chip words. The chip count is the product, and the total-bit count is the independent arithmetic check.

(a) 256 KB, 8-bit system (6 marks)

Establish the target in bits. The requirement that eight bits be delivered in one operation means the memory is organised as 262,144 locations of one byte each: $$256\ \text{KB} = 256 \times 1024 = 262{,}144\ \text{bytes} = 2{,}097{,}152\ \text{bits}, \qquad 2^{18} = 262{,}144$$ so 18 address lines reach every byte. This total-bit figure is the check every case below must satisfy.
Case i — 128K × 1. Each chip returns a single bit per access, so eight chips must be read in parallel to assemble one byte, all sharing the same 17 address lines ($128\text{K}=2^{17}$) with their single data pins wired to the eight separate data-bus lines. That group is 128K × 8 = 128 KB, which is half the requirement, so two such banks are needed, selected by address line $A_{17}$: $$8 \times 2 = \boxed{16\ \text{chips}} \qquad \text{check: } 16 \times 131{,}072 = 2{,}097{,}152\ \text{bits} \checkmark$$
Case ii — 64K × 4. Two chips side by side give the eight-bit width (one supplying the low nibble, one the high), forming a 64K × 8 = 64 KB bank on 16 address lines. Four banks are needed, decoded from $A_{17}A_{16}$: $$2 \times 4 = \boxed{8\ \text{chips}} \qquad \text{check: } 8 \times 262{,}144 = 2{,}097{,}152\ \text{bits} \checkmark$$
Case iii — 256K × 8. One chip is already both the full width and the full depth, so a single device satisfies the specification with no chip-select decoding of any kind — its own 18 address pins span the whole space: $$1 \times 1 = \boxed{1\ \text{chip}} \qquad \text{check: } 1 \times 2{,}097{,}152 = 2{,}097{,}152\ \text{bits} \checkmark$$
Case iv — 128K × 4. Two chips side by side give the byte width, forming a 128K × 8 = 128 KB bank on 17 address lines; two banks cover 256 KB, decoded from $A_{17}$: $$2 \times 2 = \boxed{4\ \text{chips}} \qquad \text{check: } 4 \times 524{,}288 = 2{,}097{,}152\ \text{bits} \checkmark$$

Every case delivers the same 2,097,152 bits, as it must — the chip counts differ only because the bits are packaged differently. The trend is the expected one: wider and deeper chips mean fewer packages, less board area, simpler decoding and lower cost, which is why case iii is the design a modern engineer would choose if the part exists at the right price.

Figure 6.1 — case i, the most instructive arrangement: eight 128K × 1 chips in parallel form one byte-wide bank, and two banks stacked under a chip-select decoder give 256 KB.

(b) 32 KB, 16-bit system from 8K × 4 chips (6 marks)

i. Chip count. The CPU word is 16 bits and each chip is 4 bits wide, so four chips side by side are required to deliver a whole word in one operation, giving a bank of 8K words × 16 bits = 8K × 2 bytes = 16 KB. The target of 32 KB therefore needs two such banks: $$4 \times 2 = \boxed{8\ \text{chips}}$$ The bit check confirms it: $32\ \text{KB} = 32{,}768\ \text{bytes} = 262{,}144\ \text{bits}$, and each 8K × 4 chip holds $8192 \times 4 = 32{,}768$ bits, so $262{,}144 / 32{,}768 = 8$ chips exactly, with the four-wide-by-two-deep arrangement being the only one that also satisfies the single-operation word access.
ii. Address-bus width. A 16-bit processor that fetches a full word per access addresses words, not bytes, and 32 KB is $$\frac{32\ \text{KB}}{2\ \text{bytes/word}} = 16\text{K words} = 16{,}384 = 2^{14}$$ so the address bus needs $$\boxed{14\ \text{address lines } (A_0 \ldots A_{13})}$$ Thirteen of them ($A_0\ldots A_{12}$, since $8\text{K}=2^{13}$) go to every chip, and the fourteenth, $A_{13}$, drives the chip-select decoder that picks between the two banks.
iii. Data-bus width. The data bus must carry a complete CPU word in one transfer, and the four chips of a bank present their nibbles simultaneously: $$\boxed{16\ \text{data lines}}$$

Figure 6.2 — the 32 KB, 16-bit system: four 8K × 4 chips concatenate their nibbles into a 16-bit word, and $A_{13}$ selects between the two banks.

Check: word-addressed versus byte-addressed, part (b)(ii). The answer of 14 lines assumes the processor addresses the memory in 16-bit words, which is what "CPU word size = 16 bits" together with "16-bit memory system" implies and is the answer the marking scheme expects. If instead the processor were byte-addressable in the manner of the 68000 — able to select the high or low byte within a word — the space would contain $32{,}768 = 2^{15}$ individually addressable bytes and the bus would carry 15 lines, with $A_0$ (or a pair of byte-enable strobes) choosing the byte and $A_1 \ldots A_{14}$ selecting the word. State whichever convention is assumed; the chip count and the data-bus width are unaffected either way.

Part	Chip	Arrangement	Chips
(a) i	128K × 1	8 wide × 2 banks	16
(a) ii	64K × 4	2 wide × 4 banks	8
(a) iii	256K × 8	1 wide × 1 bank	1
(a) iv	128K × 4	2 wide × 2 banks	4
(b) i	8K × 4	4 wide × 2 banks	8
(b) ii	Address bus (16K words)		14 lines
(b) iii	Data bus (one CPU word)		16 lines

Topic. Memory system construction by width and depth expansion, and the resulting bus widths.

Key relations. Chips per bank (width) $= \dfrac{\text{CPU word bits}}{\text{chip data bits}}$; banks (depth) $= \dfrac{\text{total words}}{\text{chip words}}$; total chips = product of the two; address lines $= \log_2(\text{addressable locations})$, of which $\log_2(\text{chip words})$ go to every chip and the remainder to the chip-select decoder; data lines = CPU word size.

Why this works. A memory chip is a two-dimensional resource — so many locations, so many bits at each — and a memory system must match both dimensions of the processor's demand independently. Widening is done by wiring chips in parallel on a common address so that they respond together and their data pins concatenate; deepening is done by giving each group its own chip-select derived from the address lines the chips themselves do not use, so that exactly one group drives the bus at a time. The two expansions are orthogonal, which is why the chip count is simply their product, and why the total-bit arithmetic is invariant across all four cases of part (a) — a genuinely useful check, because it catches an error in either dimension.

Common pitfall. The dominant error is mixing bits and bytes: computing $256\text{ KB}/128\text{K} = 2$ chips for case i, having forgotten that the chip is one bit wide, not one byte. Always convert the requirement to bits before dividing, then confirm the arrangement separately. The second trap is part (b)(ii): dividing 32 KB by 1 byte to get 15 lines when the processor accesses 16-bit words, or conversely quoting 13 lines because that is the width each individual chip needs. The third is forgetting that the high address lines feeding the decoder are still part of the CPU's address bus even though no chip sees them directly.

Source. Hamacher, Vranesic, Zaky & Manjikian, Computer Organization and Embedded Systems, 6th ed., §8.2 (memory-chip organisation and building larger modules); Mano & Ciletti, Digital Design, 6th ed., §7.2–7.4 (RAM organisation, address decoding, memory expansion).

← Question 5 Back to the paper →