Memory interfacing and address decoding

Why it exists

A processor has an address bus, a data bus and a few control lines. Memory comes as chips of a fixed size and width, and a system needs more words (a larger address space), more bits per word (a wider data bus), and often a mixture of RAM, ROM and I/O devices. Memory interfacing is the wiring and the small amount of logic that makes a set of chips look like one memory at the right addresses. The central tool is the address decoder, which turns the high-order address bits into a chip select for exactly one chip. GATE asks for the number of chips, the address lines of each chip, the address range of each chip, the decoder, and what happens when the decoding is incomplete.

Prerequisites

You need the decoder with its enable input.

Precise definitions

Buses. The address bus carries the address from the processor to the memory ($n$ lines address $2^n$ locations). The data bus carries data in both directions ($w$ lines give $w$-bit words). The control bus carries signals such as read, write and a clock or ready line.

Memory chip. A chip of $2^k$ words of $b$ bits has $k$ address lines $A_{k-1} \ldots A_0$, $b$ data lines, a chip select (CS or enable) input that makes the chip respond (otherwise its data lines are disconnected), and read/write control. A $16\text{K} \times 8$ chip has 14 address lines and 8 data lines.

Building a bigger memory.

• More bits per word (wider). Put chips side by side: all chips receive the same address and chip select, and each supplies a different slice of the data bus. Two $16\text{K} \times 8$ chips make $16\text{K} \times 16$.
• More words (deeper). Chips share the low address lines, the data lines and the read/write lines, and each has its own chip select, driven by a decoder from the high-order address bits. Four $16\text{K} \times 8$ chips make $64\text{K} \times 8$.
• Number of chips for a memory of $W$ words $\times$ $B$ bits from chips of $w \times b$: $\dfrac{W}{w} \times \dfrac{B}{b}$ (the depth factor times the width factor). Example: $64\text{K} \times 16$ from $16\text{K} \times 8$ chips needs $4 \times 2 = 8$ chips.

Address decoding. The address lines split into two parts: the low-order lines, as many as the chip has, go to every chip and select the location inside it; the remaining high-order lines go to a decoder whose outputs are the chip selects. For a $64\text{K}$ space (16 address lines) built from four $16\text{K}$ chips, $A_{13} \ldots A_0$ go to the chips and $A_{15}A_{14}$ go to a 2-to-4 decoder: chip 0 covers $0000_{16}$ to $3\text{FFF}_{16}$, chip 1 $4000$ to $7\text{FFF}$, chip 2 $8000$ to $\text{BFFF}$, chip 3 $\text{C000}$ to $\text{FFFF}$.

Address map. The table of which address range belongs to which chip or device. A device's range must not overlap another's.

Full and partial decoding. In full decoding every address line is used, so each location has exactly one address. In partial decoding some high-order lines are not connected to the decoder; a location then responds to several addresses (aliases or foldback), $2^d$ of them if $d$ lines are ignored. It needs fewer gates but wastes address space and the unused combinations cannot be given to other devices.

Memory-mapped I/O and isolated I/O. With memory-mapped I/O the device registers occupy addresses of the ordinary memory address space, read and written by ordinary load and store instructions; the address decoder produces a device select for their range. With isolated (port-mapped) I/O there is a separate I/O address space and special IN and OUT instructions with their own control signal (I/O interface).

Interleaving. To let several memory modules work at once, consecutive addresses are spread across banks. With low-order interleaving the bank number is the low address bits ($\text{bank} = \text{address} \bmod m$ for $m$ banks), so a run of consecutive words hits each bank in turn and the accesses overlap; with high-order interleaving each bank holds a contiguous block (this is just the deep construction above).

How it works

The animation decodes five addresses in a 64 KB space made of four 16 KB chips: the two high bits select the chip and the remaining 14 bits go to the chip. The last step shows partial decoding, where $A_{15}$ is not connected: the same chip and location answer to the address and to the address 0x8000 below it.

chip select = A15 A14   (2-to-4 decoder)
chip address lines = A13 .. A0

Worked examples

#include <stdio.h>
 
/* a 64 KB space built from 16 KB chips: A15 A14 go to a 2-to-4 decoder, A13..A0 go to every chip */
static int chip_of(unsigned a) { return (int)(a >> 14); }
static unsigned inside(unsigned a) { return a & 0x3FFF; }
/* partial decoding: only A14 is used, A15 is ignored */
static int chip_partial(unsigned a) { return (int)((a >> 14) & 1); }
 
int main(void) {
    int count[4] = {0, 0, 0, 0}, ok = 1;
    for (unsigned a = 0; a < 65536; a++) {
        int c = chip_of(a);
        count[c]++;
        ok = ok && a >= (unsigned)c * 16384u && a < ((unsigned)c + 1) * 16384u && inside(a) == a - (unsigned)c * 16384u;
    }
    printf("full decoding: addresses per chip %d %d %d %d, ranges consistent: %d\n", count[0], count[1], count[2], count[3], ok);
    printf("chip 2 covers 0x%04X to 0x%04X\n", 2 * 16384, 3 * 16384 - 1);
    int c2[2] = {0, 0}, alias = 0;
    for (unsigned a = 0; a < 65536; a++) {
        c2[chip_partial(a)]++;
        alias += chip_partial(a) == chip_partial(a ^ 0x8000) && inside(a) == inside(a ^ 0x8000);
    }
    printf("partial decoding (A15 ignored): chips seen %d and %d times; %d of 65536 addresses have an alias 0x8000 away\n", c2[0], c2[1], alias);
    /* how many chips and which address lines */
    long total_words = 64 * 1024, chip_words = 16 * 1024;
    int width = 16, chip_width = 8;
    printf("64K x 16 from 16K x 8 chips: %ld chips (%ld deep x %d wide), %d address lines per chip\n", (total_words / chip_words) * (width / chip_width), total_words / chip_words, width / chip_width, 14);
    return 0;
}

full decoding: addresses per chip 16384 16384 16384 16384, ranges consistent: 1
chip 2 covers 0x8000 to 0xBFFF
partial decoding (A15 ignored): chips seen 32768 and 32768 times; 65536 of 65536 addresses have an alias 0x8000 away
64K x 16 from 16K x 8 chips: 8 chips (4 deep x 2 wide), 14 address lines per chip

Cheat box

Traps and GATE patterns

Connections

The chip select decoder is a decoder with enable. The memory it builds is the main-memory level of the hierarchy, made from the chip types of RAM and ROM. Device registers placed in the address map are reached by programmed I/O, and DMA lets a device master the same buses.

PYQs

A 4 kilobyte (KB) byte-addressable memory is
realized using four 1 KB memory blocks. Two
input address lines (IA4 and IA3) are connected
to the chip select (CS) port of these memory
blocks through a decoder as shown in the figure.
The remaining ten input address lines from IA11-
IA0 are connected to the address port of these
blocks. The chip select (CS) is active high.

The input memory addresses (IA11-IA0), in
decimal, for the starting locations (Addr = 0 ) of
each block (indicated as X1, X2, X3, X4 in the
figure) are among the options given below.
Which one of the following options is
CORRECT?

The chip select logic for a certain DRAM chip in a
memory system design is shown below. Assume that
the memory system has 16 address lines denoted by
A15 to A0. What is the range of address (in
hexadecimal) of the memory system that can get
enabled by the chip select (CS) signal?

A 32 -bit wide main memory unit with a capacity of
1 GB is built using 256M × 4-bit DRAM chips.
The number of rows of memory cells in the DRAM
chip is 214 .The time taken to perform one refresh
operation is 50 nanoseconds.The refresh period is 2
milliseconds.The percentage(rounded to the
closest integer)of the time available for performing
the memory read/write operations in the main
memory unit is   .
Computer Organization and Architecture

A processor can support a maximum memory of 4
GB, where the memory is word-addressable (a
word consists of two bytes). The size of address bus
of the processor is at least   bits.

How many 32k × 1 RAM chips are needed to
provide a memory capacity of 256 K-bytes?

Consider a main memory system that consists of 8
memory modules attached to the system bus, which
is one word wide. When a write request is made, the
bus is occupied for 100 nanoseconds (ns) by the
data, address, and control signals. During the same
100 ns, and for 500 ns thereafter, the addressed
memory module executes one cycle accepting and
storing the data. The (internal) operation of different
memory modules may overlap in time, but only one
request can be on the bus at any time. The maximum
number of stores (of one word each) that can be
initiated in 1 millisecond is
.

If there are m input lines and n output lines for a
decoder that is used to uniquely address a byte
addressable 1 KB RAM, then the minimum value of
m + n is ____.

Consider the main memory system that consists of 8
memory modules attached to the system bus, which is
one word wide. When a write request is made, the bus
is occupied for 100 ns by the data, address, and
control signals. During the same 100 ns, and for 500
ns thereafter, the addressed memory module executes
one cycle accepting and storing the data. The internal
operation of different memory modules may overlap
in time, but only one request can be on the bus at any
time. The maximum number of stores (of one word
each) that can be initiated in 1 millisecond is ______

OPERATING SYSTEMS

Self-check

Revision card

References