Chapter 1: Data Storage
Bits and their Storage:
The computer uses binary to store data. Binary digits are expressed as 0 or 1. A combination of 0’s and 1’s allows us to store different data. But there must be a scheme. And Boolean operations are the basis to implement binary. The most important Boolean operations are ANDing, ORing, NOTing and XORing (exclusive OR). Examples of their use:
0 0 1 1
AND 0 1 0 1
0 0 0 1
0 0 1 1
OR 0 1 0 1
0 1 1 1
0 0 1 1
XOR 0 1 0 1
0 1 1 0
Based on the above truth table, we can put together gates (the smallest electronic component that are used to build a computer)
Flip-Flops: A Flip-flop is a collection of circuits which allows us to store bits. And a collection of flip-flops into one circuit will allow us to store a collection of bits. The basic design of a Flip-flop includes one AND gate, One OR gate and one NOT gate configured in the following way:
input output
input
Gates & Flip-Flops:
Truth tables are derived from applying boolean algebra to binary inputs. Example, if there are only two inputs – A and B, then there exist 4 possible combination and 16 possible binary functions.
These circuits are built using gates. A gate is a circuit that produces a digital output for one or more digital inputs. The output is a function of the input(s), and the type of function determines the name of the gate. The gate is the standard building block of all digital electronic system. Two of the most important gates are the NAND and NOR gates. But there are other gates such as the AND, OR, NOT, XOR (Exclusive OR). Some examples of these gates are:
OR gate:
A / B / F = A + B0 / 0 / 0
0 / 1 / 1
1 / 0 / 1
1 / 1 / 1
A
B F
AND gate
A / B / F = A . B0 / 0 / 0
0 / 1 / 0
1 / 0 / 0
1 / 1 / 1
A
B F
NOT gate:
A
/ Not A0 / 1
1 / 0
A Not A
The internal construction of the AND gate is to place two transistors in serial connection. And to construct an OR gate the two transistors are placed in parallel.
These are shown in the following diagrams:
AND Power OR
Input 1
Input 1
Input 2
Output
Output
Construction of Truth Table and Circuits.
To construct a truth table, as shown in the above example, we use 0 and 1 for the input and elaborate the amount of output depending upon the amount of input. If there are two inputs, then the truth table will consist of 4 different combinations. And if there are 3 inputs, the truth table will consist of 8 combinations. In fact, if there are N inputs, then the truth table will consist of 2n combinations. By ANDing or Oring these inputs, we can achieve the outputs, as demonstrated in above.
But to create circuits, we use the following algorithm.
1. Create the truth table.
2. Decide what you want for the output.
3. In the output column, identify all 1 bits.
4. Look at the inputs that correspond to the 1 bit output. Change all of the 0’s to 1.
5. Now create an expression combining the inputs (taking into consideration the changed bits.)
6. AND these inputs to get the above mentioned expression.
7. Now combine each of these expression by ORing them.
8. Use this final result to build the circuit.
The following example will demonstrate:
A / B / Output Needed / Cases0 / 0 / 0
1 / 0 / 1 / 1
0 / 1 / 1 / 2
1 / 1 / 0
Note in the output column, we want two 1 bits, where A = 1 and B = 0 for case 1 and A = 0 and B = 1 case 2.
Let’s look at case 1 first. We want to create an expression by using AND to get a 1 as the output, and we know that to get a 1 output from ANDing, both inputs must be 1, so we must get 1 for both inputs. To do so we take the NOT of B so we get A • (not)B.
Now for case 2: We do the same as above, only now we take the NOT of A so we get (not)A • B. If we should apply either of these expressions to the above table (individually of course) only the representative case will be true.
Now we OR these two expressions:
A • (not)B + (not)A • B
To build the circuit and apply the combination 10 to see if the output is 1:
A (1) 0
1 1
B(0) 0 1
0
The Two –Bit Adder:
Because in this case when you are adding two bits, you would need a carry bit which can be 0 or 1, we must therefore have 3 inputs and two outputs (one being the sum and the other being the carry bit) as the following shows:
A / B / C / Sum / Carry0 / 0 / 0 / 0 / 0
0 / 0 / 1 / 1 / 0
0 / 1 / 0 / 1 / 0
0 / 1 / 1 / 0 / 1
1 / 0 / 0 / 1 / 0
1 / 0 / 1 / 0 / 1
1 / 1 / 0 / 0 / 1
1 / 1 / 1 / 1 / 1
As with above, we need to create expressions for the four 1-bits in the sum column:
Case 1 : (not)A • (not)B • C
Case 2: (not)A • B • (not)C
Case 3: A • (not)B • (not)C
Case 4: A • B • C
And Sum = ((not)A • (not)B • C) + ((not)A • B • (not)C) + (A • (not)B • (not)C) + (A • B • C)
Now we need to create expressions for the four 1-bits in the Carry Column:
Case 1 : (not)A • B • C
Case 2: A • (not)B • C
Case 3: A • B • (not)C
Case 4: A • B • C
And Carry = ((not)A • B • C) + (A • (not)B • C) + (A • B • (not)C) + (A • B • C)
Draw the circuit from above expression.
Main Memory:
1. Cells – 8 bits or 1 byte to hold info. Each cell has an address.
Size of memory 220 is 1 megabyte (mb), 230 is 1gb
2. Data stored as high order (most significant bit) and low order (least significant bit). 11100011
3. Random Access Memory (RAM) – addresses can be accessed randomly instead of sequentially.
Mass Storage:
1. Hard disk, floppy, tape, CD, optical disk etc.
2. More storage space but slower.
3. Divided into tracks each of which is divided into sectors. A typical sector stores 512 bytes.
4. Seek time – time to move read/write head to correct track.
5. Latency time – Time for beginning sector to rotate under the head
6. Transfer time – Time for the entire sector to pass under the head and have its content read by the head or data written to the sector.
If we assume the following we can calculate the seek time, latency and transfer time:
Rotation Speed = 7200 rev/min = 1 rev/8.33 msec. (millisecond)
Arm movement time = .02 msec to move to an adjacent track.
Number of tracks per surface = 1000 (0..999)
Number of sectors per track = 50
Number of characters per sector = 512.
1. Seek time:
Best case = 0 msec (no arm movement necessary)
Worst case = 999 x .02 = 19.98 msec (must move from track 0 to 999).
Average case = 400 x .02 = 8.00 msec (assume that on an average the head must
move about 400 tracks).
2. Latency:
Best case = 0 msec (sector is just about to come under head)
Worst case = 8.33 msec (just missed the sector so have to do one rev).
Average case = 4.17 msec (one-half rev)
3. Transfer time:
1/50 x 8.33 msec = .17 msec (the time for one sector to pass under the head)
Best case / Worst case / Average caseSeek time / 0 / 19.98 / 8.00
Latency / 0 / 8.33 / 4.17
Transfer / .17 / .17 / .17
Total / .17 / 28.48 / 12.34
As could be seen, the average access time is about 12 seconds or this could be even less in some cases.
The other type of mass storage uses the sequential access method. In this case, there is no addresses of the data and so the head will have to search the entire disk (in the worst case) sequentially to find the required data. Most disk today are direct access in nature which makes it faster than sequential access.
Sequential access is good when we want to copy an entire disk of data to another (back up) medium.
Overall, i/o devices are very slow when compared to RAM – (RAM access time about 40 nsec whereas disk is about 12 msec a difference with a factor about 300,000 i.e. RAM is about 300,000 times faster than disks).
If this was the entire picture, then often the processor would have to sit and wait for long periods until access is completed, etc. – wasting time. The i/o controller is used to help the situation. This component is used to handle i/o details and to help compensate for time differences. It has a small amount of memory called an i/o buffer. It also consist of enough i/o control and logic processing to handle i/o devices such as the head, paper feed and screen display. It can also transmit to the processor a special hardware signal called an interrupt signal.
For example, if a line of data is to be read from memory and to be displayed on screen, the data would be read and placed in the i/o buffer at the very high speed associated with access from RAM. The processor will now instruct the i/o controller to output the data to the screen which will be much slower. But the processor will not sit and wait for the process to be completed. It would have been freed to do something else while the i/o controller output the data to the screen. When the i/o controller is finished, it will send an interrupt message to the processor telling it that it is finished with its task.
File Storage:
Binary: Representing text.
Representing Numbers.
Representing Images: bit map techniques and vector techniques.
Bit map: image is considered to be a collection of dots (pixels). An image is rep. as a long string of bits to rep. the rows of pixels (where each bit is 1 or 0 depending on the pixel being black or white). For color pixel, each pixel itself is rep. by a collection of bits to rep. its color. Bit map image looks fuzzy if enlarged. To avoid this we use vector imaging – which allows for scaling. The image is created in the form of curves and lines which is “rendered” by a software to produce the final image. But vector techniques cannot produce photographic qualities – that is why bit mapping is used in digital camera.
Representing sounds: Sampling technique is used – for the telephone 8000 sample per second whereby each sample is encoded into binary, transmitted, and then decoded when received. Encoding is generally done using 16 bits per sample – so in 1 second (for 8000 samples) 128000 bits are transmitted. For recording, to get better quality, about 44100 are taken per second and using stereo recording, 32 bits per sample is used. So to store 1 second worth of stereo sound on a CD we need over 1 million bits - sampling the amplitude of the sound wave at regular intervals.
Binary Addition:
Storing Integers:
Storing Fractions: There are different ways of storing fractional numbers. The book suggested using mantissa, exponent and sign as well as using the excess notation code to determine if the exponent is positive or negative. Another and easier method is to use the mantissa, exponent, sign for mantissa and sign for exponent.
The books case: store 25.25 using 16 bits – 1 for sign, 4 for exponent and 11 for mantissa.
Sign = 0
Exponent = .01
Mantissa = 000000011001
Put together:
11001.01 rep 25.25
We therefore need to shift the decimal point 5 places to the left and 5 in excess 4 notation is 1101
So putting all of this together the number 25.25 is stored as:
0110100001100101
extracting the various portion we get: sign = 0 (most significant bit)
mantissa = 0001100101
exponent = 1101 and from excess 4 table = 5
so starting from the leftmost 1 of mantissa, count 5 position to the right, then place decimal => 11001.01
A slightly easier method:
Using the same distribution as above: