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

Question 6 of 6: Buses, Memory Space and Address Decoding

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

Notes on this paper

Paper format. National Exams, May 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 all questions are worth 12 marks. An excitation table for the RS/JK/T/D flip-flops and a table of basic Boolean identities are supplied on the last page of the paper. 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 (Ch. 2), combinational design (Ch. 4), synchronous sequential logic (Ch. 5), registers and counters (Ch. 6), memory and address decoding (Ch. 7).
J. F. Wakerly, Digital Design: Principles and Practices, 5th ed. — canonical forms and minimisation (Ch. 3–4), counters and shift registers (Ch. 8).
C. Hamacher, Z. Vranesic, S. Zaky and N. Manjikian, Computer Organization and Embedded Systems, 6th ed. — bus structure and addressing (Ch. 2), stacks (§2.6), memory system organisation and chip-select decoding (Ch. 8).

Convention used throughout. In the address/data expressions a prime denotes complement ($\overline{A}$ is written A′ in the figures, where SVG text cannot carry an overbar). Hexadecimal constants keep the Motorola dollar-sign notation of the exam paper, written here as $7A01 in prose so that it cannot be mistaken for a mathematics delimiter.

Question 6: Buses, Memory Space and Address Decoding (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.

Item	Value
Address bus	20 lines, A19–A0
Data bus	16 lines, D15–D0 (a 16-bit CPU)
Memory to be fitted	512 KByte
Memory device	64K × 16 (65 536 locations, 16 bits wide)
Marks	(a) 2, (b) 3, (c) i 3, (c) ii 2, (c) iii 2

Find. Two qualitative bus differences; the total memory space in KByte and MByte with its hexadecimal address range; and the chip count, decoding logic and per-chip address allocation for the 512 KByte subsystem.

Approach. Treat the address bus as the selector and the data bus as the payload, then size the memory space as (number of addresses) × (bytes delivered per address). For part (c), divide the required capacity by the capacity of one device to get the chip count, give every chip the low address lines it needs internally, and use the leftover high lines as the decoder input that generates the chip selects.

(a) Two differences between the address bus and the data bus.

Direction of flow. The address bus is unidirectional: addresses are generated by the bus master — normally the CPU — and are received by memory and by peripherals, never the reverse. Its drivers therefore sit only at the CPU end. The data bus is bidirectional: the same lines carry data from memory to the CPU during a read and from the CPU to memory during a write, so every device attached to it needs a tri-state driver and the bus protocol must guarantee that exactly one driver is enabled at a time.

Meaning of the information. A pattern on the address bus is a location identifier — it names where in the memory or I/O map the transaction is to take place, and its width therefore fixes the size of the address space. A pattern on the data bus is the content of that location, an operand or an instruction whose interpretation depends entirely on context, and its width fixes how much information moves per bus cycle rather than how much can be addressed. The two widths are consequently independent design parameters: widening the address bus buys capacity, widening the data bus buys bandwidth.

(b) Memory space of the system.

Count the addressable locations. Each of the 20 address lines is an independent binary digit, so the number of distinct addresses the CPU can emit is $$N = 2^{20} = 1\,048\,576 = 1\text{M locations}$$
Convert locations to bytes. The data bus is 16 bits wide, so one bus cycle at one address transfers a 16-bit word, that is 2 bytes. The total space is therefore $$S = N \times 2\ \text{bytes} = 2\,097\,152\ \text{bytes}$$ $$S = \frac{2\,097\,152}{1024} = \boxed{2048\ \text{KByte} = 2\ \text{MByte}}$$ The justification asked for is exactly this product: the address bus width sets the number of locations and the data bus width sets the size of each location.
State the address range. Twenty binary digits require five hexadecimal digits, since $20/4 = 5$. The lowest address is all zeros and the highest is all ones: $$\text{lowest} = \text{00000}_{16}, \qquad \text{highest} = \text{FFFFF}_{16}$$ Checking, $FFFFF $= 2^{20} - 1 = 1\,048\,575$, one less than the location count, as it must be.

Check: word-organised addressing is assumed. The chips specified in part (c) are 16 bits wide and are shown connected to the full D15–D0 bus, with no byte-select strobes anywhere in the figure. Each address therefore selects one complete 16-bit word, which is the reading used above and which makes part (c) close exactly: four chips of 64K words are 256K words, which is 512 KByte. If instead the machine were byte-addressable with A0 selecting a byte within a word, the space would be $2^{20}$ bytes $= 1024$ KByte $= 1$ MByte, the chips would connect to A19–A1, and a pair of byte strobes would be required. The figure supplies neither, so the word-organised interpretation is the self-consistent one and is carried through below.

(c) Building a 512 KByte memory subsystem.

(c-i) Capacity of one chip, and the chip count. A 64K × 16 device holds $$64\text{K} \times 16\ \text{bits} = 65\,536 \times 2\ \text{bytes} = 131\,072\ \text{bytes} = 128\ \text{KByte}$$ so the number required for 512 KByte is $$n = \frac{512\ \text{KByte}}{128\ \text{KByte}} = \boxed{4\ \text{chips}}$$ Because every chip is already as wide as the data bus, the expansion is purely in depth: the four chips are stacked in the address dimension, not paralleled in the data dimension. Their combined capacity is $4 \times 64\text{K} = 256\text{K}$ words, which is one quarter of the 1M-word space the 20-line bus can reach.

Fill in the blanks beside and inside the chips. Each chip has $64\text{K} = 2^{16}$ internal locations and therefore needs 16 address inputs, which are taken from the bottom of the bus; each chip is 16 bits wide and takes the whole data bus:

Blank in the figure	Value	Reason
Address lines per chip	A15–A0 (/16)	$2^{16} = 64\text{K}$ internal locations
Data lines per chip	D15–D0 (/16)	Chip is 16 bits wide; matches the CPU word
Address bus width	/20	A19–A0 as given
Data bus width	/16	D15–D0 as given
Lines left for decoding	A19, A18, A17, A16	$20 - 16 = 4$ high-order lines

(c-ii) Design the decoding logic. Four chips need four mutually exclusive selects, so $\log_2 4 = 2$ address lines choose between them; the natural choice is the two lines immediately above the chips' own inputs, A17 and A16, because using contiguous lines makes each chip occupy one contiguous block. The two remaining lines A19 and A18 do not select between chips but decide whether the 512 KByte block is being addressed at all, so they form an enable term. Placing the block at the bottom of the map means enabling on $\overline{A_{19}}\,\overline{A_{18}}$. With active-low chip selects the four expressions are $$\overline{\text{CS}_0} = \overline{\overline{A_{19}}\,\overline{A_{18}}\,\overline{A_{17}}\,\overline{A_{16}}}, \qquad \overline{\text{CS}_1} = \overline{\overline{A_{19}}\,\overline{A_{18}}\,\overline{A_{17}}\,A_{16}}$$ $$\overline{\text{CS}_2} = \overline{\overline{A_{19}}\,\overline{A_{18}}\,A_{17}\,\overline{A_{16}}}, \qquad \overline{\text{CS}_3} = \overline{\overline{A_{19}}\,\overline{A_{18}}\,A_{17}A_{16}}$$ In hardware this is a 2-to-4 line decoder with active-low outputs driven by A17 and A16 and enabled by $\overline{A_{19}}\,\overline{A_{18}}$ — a single 74x139 half, or four 4-input NAND gates with the appropriate inverters. The reasoning behind each connection class is: the low 16 lines go to every chip in parallel because each chip must be able to reach any of its own 64K locations; the next 2 lines go only to the decoder because their job is to pick one chip; the top 2 lines go only to the decoder enable because their job is to keep the block from responding anywhere else in the 1M-word space. Exactly one CS is low for any address in the block, so exactly one chip drives the data bus and no contention can occur.
Question 6(c) - 512 KByte subsystem: four 64K x 16 chips decoded by A17-A16, enabled by A19'.A18'.

(c-iii) Address range of each chip. Each chip owns $64\text{K} = \text{10000}_{16}$ consecutive word addresses, starting at zero:

Chip	A17 A16	Lowest address	Highest address	Size
0	0 0	$00000	$0FFFF	64K words = 128 KByte
1	0 1	$10000	$1FFFF	64K words = 128 KByte
2	1 0	$20000	$2FFFF	64K words = 128 KByte
3	1 1	$30000	$3FFFF	64K words = 128 KByte

The populated block therefore runs from $00000 to $3FFFF, which is $4 \times 65\,536 = 262\,144$ word locations, i.e. 512 KByte as required, and the remaining three quarters of the map ($40000 to $FFFFF) is left free for further memory or for I/O. $$\boxed{\,4 \text{ chips spanning } \text{00000}_{16}\text{ to }\text{3FFFF}_{16},\quad \overline{\text{CS}_k} = \overline{\overline{A_{19}}\,\overline{A_{18}}\cdot m_k(A_{17},A_{16})}\,}$$

Check: the figure prints six chip outlines, not four. The drawing supplies a 3 × 2 array of blank 64K × 16 devices with dashed continuation marks on both buses, which is a template rather than a specification — part (c-i) asks "how many chips are needed?" precisely because the answer is fewer than the number drawn. Four chips are populated and connected as above; the remaining two outlines are left unused. Had the intent been to populate all six, the capacity would have been 768 KByte, which is not the figure named in the question.

Part	Quantity	Result
(a)	Direction	Address bus unidirectional (CPU out); data bus bidirectional (tri-state)
(a)	Meaning	Address = location identifier (sets capacity); data = contents (sets bandwidth)
(b)	Locations	$2^{20} = 1\,048\,576$ word locations
(b)	Memory space	2 097 152 bytes = 2048 KByte = 2 MByte
(b)	Address range	$00000 to $FFFFF
(c-i)	Chip capacity / count	128 KByte each; 4 chips for 512 KByte
(c-i)	Chip connections	A15–A0 and D15–D0 to every chip
(c-ii)	Decoding	2-to-4 decoder on A17, A16, enabled by $\overline{A_{19}}\,\overline{A_{18}}$; CS active low
(c-iii)	Chip ranges	$00000–$0FFFF, $10000–$1FFFF, $20000–$2FFFF, $30000–$3FFFF

Topic. Bus organisation, memory-space arithmetic and chip-select decoding.

Key relations. Addressable locations $= 2^{(\text{address lines})}$. Memory space in bytes $= 2^{(\text{address lines})} \times (\text{data lines}/8)$. Chips required $= (\text{required capacity})/(\text{capacity per chip})$. Address lines per chip $= \log_2(\text{locations per chip})$; decoder inputs $= \log_2(\text{chip count})$; any lines left over form the enable. Number of hexadecimal digits $= (\text{address lines})/4$.

Why this works. The address space partitions cleanly because the capacity of each device is a power of two: the low-order lines index within a device and the high-order lines index between devices, so no address arithmetic is needed anywhere in the hardware, only a decoder. This is the whole reason memory devices are built in power-of-two sizes. Choosing the decoder lines to be contiguous with the chips' own address lines is what makes each chip occupy one unbroken block; picking non-adjacent lines would still work electrically but would interleave the chips through the map in a way that complicates every later software decision. Leaving the top lines as an enable rather than as further select bits is what confines the subsystem to a defined window and prevents the block from being aliased sixteen times across the full 1M-word space — incomplete decoding of that kind is a classic source of bugs in which a peripheral later added at a high address is shadowed by RAM.

Common pitfall. Computing the chip count from bit capacity rather than byte capacity, or forgetting that a 16-bit-wide chip on a 16-bit bus contributes depth only. A 64K × 16 device is 128 KByte, not 64 KByte, so the answer is four chips, not eight. The second pitfall is leaving A19 and A18 unconnected: the memory would then answer at four different places in the map, and any future device placed above $3FFFF would collide with it.

Source. Hamacher et al., Computer Organization and Embedded Systems, 6th ed., §2.2 (bus structure), Ch. 8 (memory system organisation, address decoding, memory-chip expansion); Mano & Ciletti, Digital Design, 6th ed., §7.2–7.3 (RAM organisation and address decoding).

← Question 5 Back to the paper →