Memory

MEMORY

Bits. The basic unit of memory is the binary digit ot bit. It contains 0 or 1. Some computers use "Binary Coded Decimal" (BCD). Four bits are used to store numbers from 0 (0000) to 9 (1001). This is easier to understand but inefficient as it wastes storage space. For example the number 1944 in Bin BCD can store numbers from 0 to 9999C D would be as shown below.

In Binary, the number would be 1 1 1 1 0 0 1 1 0 0. 13 bits for B.C.D. and 10 bits for binary. For conversion method, click below.

Binary

Sixteen bits in BCD can store numbers from 0 to 9999 (10,000 combinations). In Binary not using the sign bit, the numbers stored are fro 0 to 2¹⁶ - 1 or 65,536 combinations, which makes it a lot more economical. However a still more efficient method is to have 10 rather than two combinations. Then 4 such bites can store numbers from 0 to 9999.

Memories consists of a number of cells (or locations) each of which can store a piece of information. Each cell has a number called its address.. n cells can have addresses from 0 to n-1. Each cell has the same number of bits. So, if a cell has k bits, there are 2^k combinations. A 96-bit memory can be organized as 12 cells each of 8 bits, or as 8 cells each of 12 bits, or as 6 cells each of 16 bits. If an address has m bits, the maximum number of cells addressable is 2^m.

Error-Correcting codes

Due to voltage spikes or surges, bits can be demagnetized leading to changes in memory. Error detecting cods have been devised to guard against occurrences. We add check bits. A memory word consisting of m data bits will have r check bits, resulting in a codeword n = m + r bits. An algorithm to detect the wrong bit was devised by

Richard Wesley Hamming

Comparing two binary code words, we can see how many bits are different by conducting an exclusive OR and counting the number of 1 bits. The number of bit positions in which two codeword differ is called the Hamming distance. A simple example would be to add a single parity bit to the data. The bit is chosen so that if we add all the bits Including the parity bit) the total would be even. Now, if any bit is changed, the total would be odd, and we know that an error has occurred. But if two bits are changed, we would not know. In addition, we would not know which bit has changed. Hamming's code (algorithm) can be used to construct error correcting codes for any size memory word. The number of parity (check) bits required depends on the word size. The table below explains that:

n	Word Size	Check Bits	Total Size	Percent Overhead
	2ⁿ	n + 1	Word Size + Check Bits	Check bits/word size * 100
0	1	1	2	1/1*100 = 100%
1	2	2	4	2/2*100 = 100%
2	4	3	7	3/4*100 = 75%
3	8	4	12	4/8*100 = 50%
4	16	5	21	5/16*100 = 31.25%
5	32	6	38	6/32*100 = 18.75%
6	64	7	71	7/64*100 = 10.9375%
7	128	8	136	8/128*10 = 6.25%
8	256	9	265	9/256*100 = 3.5156%
9	512	10	522	10/522*100 = 1.9157%

Notice that as the size of the word increases, the percent overhead decreases.

For example take a word 1 1 1 1 0 0 0 0 1 0 1 0 1 1 1 0
This is a word of size 16 (There are 16 bits in the word), which is 2⁴. So the number of check (parity) bits required would be 4 + 1 = 5 and the total size would be 16 + 5 = 21. The parity bits are in position 1, 2, 4, 8, and 16 (powers of 2) So the first step is to write the word in positions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15.1 7, 18, 19, 20, and 21 leaving positions 1, 2, 4, 8, and 16 blank.

__ __ 1 __ 1 1 _1 __ 0 0 0 0 1 0 1 __ 0 1 1 1 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Bit 1 checks bits 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21. (take 1, skip 1 and so on)
Bit 2 checks bits 2, 3, 6, 7, 10, 11, 14, 15, 18, 19. (take 2, skip 2 and so on)
Bit 4 checks bits 4, 5, 6, 7, 12, 13, 14, 15, 20, 21. (take 4, skip 4 and so on)
Bit 8 checks bits 8, 9, 10, 11, 12, 13, 14, 15. (take 8, skip 8 and so on)
Bit 16 checks bits 16, 17, 18, 19, 20, 21 (take 16, skip 16 and so on)

Also note that 3 = 1 + 2, so 3 is checked by bits 1 and 2. 5 is 1 + 4, so bit 5 is checked by bits 1 and 4. 6 is 2 + 4 and is checked by 2 and 4. 7 is 1 + 2 + 4, so is checked by 1, 2, and 4. 9 is 1 + 8 and so on. So to know which check bit is used, find the check bits which when summed give you the bit to be checked.

For bit 1, the total of the bits it checks is 1 + 1 + 1 + 0 + 0 + 1 + 1 + 0 + 1 + 0 = 6. This is even, so bit 1 is 0.
For bit 2, the total of the bits it checks is 1 + 1 + 1 + 0 + 0 + 0 + 1 + 1 + 1 = 6. This is even, so bit 2 is 0.
For bit 4, the total of the bits it checks is 1 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 0 = 6. This is even, so bit 4 is 0.
For bit 8, the total of the bits it checks is 0 + 0 + 0 + 0 + 1 + 0 + 1 = 2. This is even, so bit 8 is 0.
For bit 16, the total of the bits it checks is 0 + 1 + 1 + 1 + 0 = 3. This is odd, so bit 16 is 1. So the word is stored in memory as:

0 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 0 1 1 1 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
now the grand total for bits 1, 2, 4, 8, and 16 will be even.

Bit 1 = 0 + 1 + 1 +1 + 0 + 0 + 1 + 1 + 0 + 1 + 0 = 6
Bit 2 = 0 + 1 + 1 + 1 + 0 + 0 + 0 + 1 + 1 + 1 = 6
Bit 4 = 0 + 1 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 0 = 6
Bit 8 = 0 + 0 + 0 + 0 + 0 + 1 + 0 + 1 = 2
Bit 16 = 1 + 0 + 1 + 1 + 1 + 0 = 4

If the word somehow changes to

0 0 1 0 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Bit 1 becomes 0 + 1 + 1 +1 + 0 + 1 + 1 + 1 + 0 + 1 + 0 = 7 which is odd
Bit 2 becomes 0 + 1 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 1 = 7 which is odd
Bit 4 becomes 0 + 1 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 0 = 6 which is even
Bit 8 becomes 0 + 0 + 0 + 1 + 0 + 1 + 0 + 1 = 3 which is odd
Bit 16 becomes 1 + 0 + 1 + 1 + 1 + 0 = 4 which is even.

All bits must be even, so bits 1, 2, and 8 are incorrect. Since 1 + 2 + 8 = 11, we know that bit 11 has been changed. Hamming's code will not only let us know that a bit has been changed but which bit has changed.

The characters that we type in is stored as a byte (that is why it is also called a character). For instance, the letter "A" is stored as 0100 0001. To Conserve space, the characters are sometimes represented as Octal or Hexadecimal. The code used is the American Standard Code for Information Interchange (ASCII pronounced Askey) For a complete listing of all characters in all formats, please click below:

ASCII table

My ASCII Chart

    0   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F

0  NUL SOH STX ETX EOT ENQ ACK BEL BS  HT  LF  VT  FF  CR  SO  SI

1  DLE DC1 DC2 DC3 DC4 NAK SYN ETB CAN EM  SUB ESC FS  GS  RS  US

2   SP  !   "   #   $   %   &   '   (   )   *   +   ,   -   .   /

3   0   1   2   3   4   5   6   7   8   9   :   ;   <   =   >   ?

4   @   A   B   C   D   E   F   G   H   I   J   K   L   M   N   O

5   P   Q   R   S   T   U   V   W   X   Y   Z   [   \   ]   ^   _

6   `   a   b   c   d   e   f   g   h   i   j   k   l   m   n   o

7   p   q   r   s   t   u   v   w   x   y   z   {   |   }   ~ DEL

Here's a link to a decimal-to-ASCII chart.

Cache Memory

CPUs are faster than memories. Memory designers have concentrated on increasing capacity not speed. After the CPU issues a memory request, it will not get the word it needs for many CPU cycles. There are two solutions. One is to start memory READs when they are encountered but continue executing and stall the CPU if an instruction tries to use the memory word before it has arrived. The other solution is to require compilers not to generate code to use words before they have arrived. Often after a LOAD there is nothing else to do, so the compiler is forced to insert NOP (no operation) instructions, which do nothing, but occupy a slot and waste time. Engineers can build fast memories, but they have to be located on the CPU chip (going over the bus to memory is slow). This makes the chip bigger and expensive. So the choice is a small amount of fast memory or a large amount of slow memory.

Cache (from the French cacher, to hide) is a small fast memory. It keeps the most heavily used memory words. When the CPU needs a word, it looks first in the cache. If the word is not there, it checks the main memory. If a substantial fraction of the words are in cache, the access time is reduced. Success or failure depends on what fraction of the words are in cache. Programs do not access their memories completely at random. The next memory reference will be in the general vicinity of the previous one. Except for branches and procedure calls, instructions are fetched from consecutive locations in memory. In loops, a limited number of instructions are repeatedly executed.

Locality Principle is when memory references are made in any short time interval using a small fraction of the total memory. When a word is referenced, it and some of its neighbors are brought from slow memory into the cache, so that the next time it is required, it can be accessed quickly. If a word is read or written k times in a short interval, the computer will need 1 reference to slow memory and k - 1 references to fast memory. The larger k is, the better the overall performance. If c is the cache access time, m is the main memory access time, and h is the hit ratio, the fraction of all references that can be satisfied out of cache. h = (k - 1)/k. Miss ratio is 1 - h. Mean access time = c + (1 - h)m. if h = 1 access time = c and all references are in cache. If h = 0, access time = c + m. First an unsuccessful check of c nd then do the memory reference. Memory reference can be started in parallel with cache search, so is a cache miss occurs, the memory cycle is already on.

SECONDARY MEMORY

The main memory is always too small. There is a memory hierarchy. At the top are the CPU registers, which can be accessed at full CPU speed. Next comes the cache memory, which ranges from 32 KB to a few megabytes. Next is main memory, from 16 MB to tens of gigabytes. Then come magnetic disks for permanent storage. Finally there is magnetic tape and optical disks for archival storage. As we move down the hierarchy, the access time gets bigger. CPU registers can be accessed in a few nanoseconds. Cache memories take a small multiple of CPU registers. Main memory needs a few tens of nanoseconds. Disk access times are at least 10 msec, and tape and optical disk times are measured in seconds. But the storage capacity increases. CPU registers store 128 bytes, caches a few megabytes, main memories tens to thousands megabytes, magnetic disks a few gigabytes to tens of gigabytes. Tapes and optical disks are kept off-line, so they have unlimited capacity. Number of bits per dollar also increases. Main memory is measured in dollars/megabyte, magnetic disk storage in pennies/megabyte, and magnetic tape in dollars/gigabyte or less.

Magnetic disks

A magnetic disk consists of one or more aluminum platters with a magnetizable coating. They are 3 to 12 cm in diameter. A disk head containing an induction coil floats just over the surface, resting on a cushion of air (it touches the surface on floppy disks). When a current passes through the head, it magnetizes the surface just beneath the head, aligning the magnetic particles facing left or right depending on the polarity of the drive current. When the head passes over a magnetizes area, a positive or negative current is induced in the head, making it possible to read back the previously stored bits. Thus as the platter rotates under the head, a stream of bits can be written and later read back. The circular sequence of bits written as the disk makes a complete rotation is called a track. Each track is divided up into fixed-length sectors, containing 512 data bytes, preceded by a preamble that allows the head to be synchronized before reading or writing. Following the data is an Eror-Correcting Code (ECC), either a Hamming code, or a code that can correct multiple errors called a Reed-Solomon Code Between consecutive sectors is a intersector gap. The formatted capacity is 85% of unformatted capacity.

Disks have moveable arms capable of moving in and out to different radial distances from the spindle about which the platter rotates. At each radial distance, a different track can be written. Tracks are a series of concentric circles about the spindle. Disks have between 800 and 2000 tracks per centimeter, so track widths are 5 to 10 microns (! micron = 1/1000 mm). The track is a ring of magnetized material with small guard areas separating from adjoining tracks. Disks have a density of 50,000 to 100,000 bits/cm. So a bit is 50 times as big in the radial direction as along the circumference. Disks are sealed in the factory. They are called Winchester disks The name Winchester comes from the Winchester repeating rifles. When 10M hard disks were in use, the goal was to produce the one that would hold 30M of data and access it in 30 milliseconds. That project was known under the name 30/30 project which reminded about the famous Winchester repeating rifle with the same name popular in the days of the Old West.
Disks have multiple platters stacked vertically. Each surface has its own arm and head. All the arms are ganged together so they move to different radial positions all at once. The set of tracks at a given radial position is called a cylinder. To read or write a sector, the arm is moved to the right radial position called seek. This takes 5 to 15 msec except 1 msec in consecutive tracks. Rotational latency is a delay until the desired sector rotates under the head. Disks rotate at 3600, 5400, or 7200, or 10,800 RPM, so the average delay (half a rotation) is 4 to 8 msec. Transfer time depends on the linear density and rotation speed. With transfer rates of 5 t 20 MB/sec, a 512-byte sector takes 25 to 100 micro seconds.

As disks rotate at 60 to 120 revolutions/sec, they get hot and expand, changing their physical geometry. Drives have to recalibrate their positioning by forcing the heads all the way in or out. Outer tracks have more linear distance around than inner ones do. Cylinders are divided into zones (10 to 30 per drive) and the number of sectors is increased in each zone moving outward from the innermost track. Disk controller is a chip that controls the drive. The controller's tasks include accepting commands from the software, such as READ, WRITE, and FORMAT, controlling the arm motion, detecting and correcting errors, and converting 8-bit bytes read from memory into a serial bit stream and vice versa.

Floppy disks

Diskette or Floppy disk is a small removable medium. The early ones were flexible. Floppy disk heads touch the surface, so the media and heads wear out. So personal computers retract the heads and stop the rotation when a drive is not reading or writing. When the next read or write command is encountered, there is a delay of half a second while the motor gets up to speed.

Parameters	LD 5.25"	HD 5.25"	LD 3.5"	HD 3.5"
Size (inches)	5.25	5.25	3.5	3.5
Capacity (bytes)	360K	1.2M	720K	1.44M
Tracks	40	80	80	80
Sectors/track	9	15	9	18
Heads	2	2	2	2
Rotations/min	300	360	300	300
Data rate (kbps)	250	500	250	500
Type	Flexible	Flexible	Rigid	Rigid

LD is low density, HD is high density.

Problems: Page and 115 116. Nos. 14, 15, and 34

Solutions:

No. 14 From 0 to 9 the codes are: 0000000, 1101001, 0101010, 1000011, 1001100, 0100101, 1100110, 0001111, 1110000, and 0011001.

No. 15. The last bit is the parity bit that is added. From 0 to 9: 00000, 00011, 00101, 00110, 01001, 01010, 01100, 01111, 10001, and 10010.

No. 34. It says I LOVE YOU.

Top of the Page