The goal of designing memory
other than registers is to maximize the amount of space available without
sacrificing too much speed. Thus, memory designers seek to pack bits as closely
together as possible. They do this by reducing the number of transistors per
bit, making the transistors smaller, and by using special processes that allow
devices to be oriented vertically rather than horizontally on the wafer.
Typically the more that is done to make the bits smaller, the longer it takes
to access them. Thus, we can trade off using more and larger transistors to
increase memory speed versus a loss in storage capacity. Systems typically
include a combination of slow, dense memory and faster, lower capacity memory.
Static random access memory
(SRAM) is built much like a register in that it uses a feedback loop to hold a
value. However it is not master-slave. The feedback loop usually consists of
six transistors or sometimes four. An SRAM retains its contents as long as
power is applied -- it continuously consumes power to maintain its contents. It
is slower than a register because it is built with small transistors that can't
carry as much current as those in a gate. Because the transistors are so small,
they are overwhelmed by the current required to read out their contents, and
the value of a bit cell is lost when it is output. This is called destructive
readout, and it requires that the data be rewritten after reading.
Dynamic RAM (DRAM) uses fewer
transistors (three or even just one). This explains why DRAMs have more
capacity than SRAMs (usually by a factor of 4). It stores a charge in a
capacitor and then reads it back out using a special amplification circuit. The
charge can dissipate gradually over time (perhaps a millisecond) and so the
contents of memory must be read out and rewritten periodically to avoid losing
them. Fortunately, the memory chips themselves provide ways to do this
refreshing internally as long as they are set to the proper mode and clocked a
certain number of times. Like SRAM, DRAM uses destructive readout.
DRAM consumes power only when
data is being read, written or refreshed, making it a cooler technology.
However, DRAM is also slower than SRAM because the special amplification needed
to sense the stored charge is time consuming. During a refresh operation, the
data is unavailable, but refresh takes only about 1 to 2% of the available time
because the internal refresh circuitry reads out an entire column of bits to a
buffer register and then writes them all back. Thus, the refresh time is
proportional to the number of rows of bits in the RAM.
Data in a block of memory
bits in a RAM is selected by breaking the address into a column and a row
number. The column number is sent first, and clocking the RAM fetches an entire
column of bits out to a buffer register. Then the row number is used to select
the particular bit from the register. If data is being fetched from a series of
adjacent addresses with the same column number, then the first clock cycle can be
skipped, and data can be read directly from the buffer at least twice as fast.
DRAM can be augmented with
small blocks of SRAM on the same chip to enhance its performance. The SRAM
caches recently used columns so that they can be fetched without the column
read delay.
Although processor speeds have increased steadily, the speed of memory has not kept pace. Thus, processors must wait for many cycles to retrieve values from memory. This has resulted in multiple levels of cache memory, and new approaches to transmitting data at higher speeds between memory and processor chips.
Given that a modern system
contains typically 128 MB of memory, there are 1G bits present. These are
accessed at a rate of perhaps 300 million times per second. Given these large
numbers, the probability that an error will occur is fairly high. By adding
redundant information to the stored data, we can detect errors and in some
cases also correct them.
The key to this capability is
the Hamming distance between combinations of code words, where a code word is a
data value combined with the redundant information. Take for example, the two
words 0001 and 1000. These differ in two bits, and thus they have a Hamming
distance of 2. With this distance, we can detect any single bit error in either
of these two words. Flipping any one of their bits produces a code that is not
one of them. Flipping two bits may also produce erroneous codes, but if the
right two are flipped then the one code becomes the other and no error can be
detected.
We can construct codes with
many more values so that all of the valid values are at least two bits apart.
This is most directly done by taking an existing data word and adding an extra
bit that is always set or cleared so as to make the number of bits in the code
odd (or even). This type of code is called a parity code, and can detect a
single bit error.
Whenever we have a Hamming
distance of D for every combination of code words, we can detect D - 1 error
bits. You can determine the Hamming distance for a set of code words by
comparing every pair of codes and counting the number of different bits. The
smallest number of different bits among all of the pairings is the Hamming
distance for the entire code (the pair with the least number of different bits
is the weak link in the code, since it takes only that many bits to confuse one
for the other).
If the Hamming distance for a
set of code words is at least 3, we can correct for any single bit error. A
single bit error is just one away from a valid code word, and since every other
code word is 2 bits away from the erroneous code word, we correct the error and
get back to the only word that is just one bit away. Of course, if multiple
bits flip, we may mistakenly correct to the wrong code word. However, for a
distance of 3, we can tell if two bits were flipped, so it would take a pretty
big (3- bit) error to fool the correction system.
This kind of code is called
SECDED (Single Error Correction, Double Error Detection). Given a number of
errors that we would like to correct, what Hamming distance is required for the
code? This is easy when we think in terms of distances geometrically. If you
want to be able to go at least E distance away from a point in space yet always
have it be the closest point to you, what distance has to separate all of the
points? 2E + 1 = D So, to correct 5-bit errors, we would have to use a code
with a Hamming distance of 11.
As an aside, suppose you are
transmitting a lot of data over phone lines and you know that they can have
bursts of errors due to noise, but never more than 500 bits worth. How could
you use a SECDED code to correct for this? Arrange the data in blocks of 500
words. Send all of their first bits, then all of their second bits, etc. If an error
burst occurs it will only damage a single bit in each word. You can then run
through the words at the other end, using the SECDED method to correct each of
their 1-bit errors.
© Copyright 1995, 1996, 2001 Charles C. Weems Jr.
All rights reserved.
Back to Chip Weems' home page.
Back to Computer Science Department home page.