Data Storage Lecture Slides PDF

DATA STORAGE L EC T U R E S L I D ES A R E A DA P T E D / M O D I F I E D F RO M S L I D ES P ROV I D E D BY T H E T E X T B O O K , C O M P U T E R S C I E N C E : A N OV E RV I E W BY J. G L E N N B RO O K S H EA R A N D D E N N I S B RY LOW P U B L I S H E R P EA RS O N Data Storage  Bits and T...

DATA STORAGE L EC T U R E S L I D ES A R E A DA P T E D / M O D I F I E D F RO M S L I D ES P ROV I D E D BY T H E T E X T B O O K , C O M P U T E R S C I E N C E : A N OV E RV I E W BY J. G L E N N B RO O K S H EA R A N D D E N N I S B RY LOW P U B L I S H E R P EA RS O N Data Storage  Bits and Their Storage  Main Memory  Representing Information as Bit Patterns  The Binary System  Storing Integers  Storing Fractions  Data Compression  Communications Errors  Mass Storage 2 Bits and Bit Patterns  Bit: Binary Digit (0 or 1)  Bit Patterns are used to represent information. ◦ Numbers ◦ Text characters ◦ Images ◦ Sound ◦ And others 3 Boolean Operations  Boolean Operation: An operation that manipulates one or more true/false values  Specific operations ◦ AND ◦ OR ◦ XOR (exclusive or) ◦ NOT 4 Boolean Operations 5 Gates  Gate: A device that computes a Boolean operation ◦ Often implemented as (small) electronic circuits ◦ Provide the building blocks from which computers are constructed ◦ VLSI (Very Large Scale Integration) 6 A pictorial representation of gates 7 Quiz What are the names of these gates? 8 Quiz What input bit patterns will cause the following circuit to produce output of 1? 9 Flip-flops  Flip-flop: A circuit built from gates that can store one bit. ◦ One input line is used to set its stored value to 1 ◦ One input line is used to set its stored value to 0 ◦ While both input lines are 0, the most recently stored value is preserved 10 A simple flip-flop circuit 11 Setting the output of a flip-flop to 1 12 Setting the output of a flip-flop to 1 13 Setting the output of a flip-flop to 1 14 Quiz 15 Another flip-flop 16 Quiz 17 Quiz 18 Activity 19 Hexadecimal Notation  Hexadecimal notation: A shorthand notation for long bit patterns ◦ Divides a pattern into groups of four bits each ◦ Represents each group by a single symbol  Example: 10100011 becomes A3 20 The hexadecimal coding system 21 Quiz 22 Main Memory Main Memory Cells  Cell: A unit of main memory (typically 8 bits which is one byte) ◦ Most significant bit: the bit at the left (high-order) end of the conceptual row of bits in a memory cell ◦ Least significant bit: the bit at the right (low-order) end of the conceptual row of bits in a memory cell 24 The organization of a byte-size memory cell 25 Main Memory Addresses  Address: A “name” that uniquely identifies one cell in the computer’s main memory ◦ The names are actually numbers. ◦ These numbers are assigned consecutively starting at zero. ◦ Numbering the cells in this manner associates an order with the memory cells. 26 Memory cells arranged by address 27 Memory Terminology  Random Access Memory (RAM): Memory in which individual cells can be easily accessed in any order  Dynamic Memory (DRAM): RAM composed of volatile memory 28 Measuring Memory Capacity  Kilobyte: 210 bytes = 1024 bytes ◦ Example: 3 KB = 3 times1024 bytes  Megabyte: 220 bytes = 1,048,576 bytes ◦ Example: 3 MB = 3 times 1,048,576 bytes  Gigabyte: 230 bytes = 1,073,741,824 bytes ◦ Example: 3 GB = 3 times 1,073,741,824 bytes  Terabyte  Petabyte  Exabyte  Kibi-, Mebi-, Gibi-,.. 29 Representing Information as Bit Patterns Representing Text  Each character (letter, punctuation, etc.) is assigned a unique bit pattern. ◦ ASCII: Uses patterns of 7-bits to represent most symbols used in written English text ◦ ISO developed a number of 8 bit extensions to ASCII, each designed to accommodate a major language group ◦ Unicode: Uses patterns of 16-bits to represent the major symbols used in languages world wide (UTF-8, UTF-16,…) 31 The message “Hello.” in ASCII 32 Representing Numeric Values  Binary notation: Uses bits to represent a number in base two  Limitations of computer representations of numeric values ◦ Overflow: occurs when a value is too big to be represented ◦ Truncation: occurs when a value cannot be represented accurately 33 Representing Images  Bit map techniques ◦ Pixel: short for “picture element” ◦ RGB ◦ Luminance and chrominance  Vector techniques ◦ Scalable ◦ TrueType and PostScript 34 Representing Sound  Sampling techniques ◦ Used for high quality recordings ◦ Records actual audio  MIDI ◦ Used in music synthesizers ◦ Records “musical score” 35 Representing Sound The sound wave represented by the sequence 0, 1.5, 2.0, 1.5, 2.0, 3.0, 4.0, 3.0, 0 36 Quiz 37 The Binary System The Binary System  The traditional decimal system is based on powers of ten.  The Binary system is based on powers of two. 39 The base ten and binary systems 40 Decoding the binary representation 100101 41 Algorithm for finding the binary representation of a positive integer 42 Applying the algorithm 43 The binary addition facts 44 Decoding the binary representation 45 Quiz 46 Quiz 47 Quiz 48 Storing Integers Storing Integers  Two’s complement notation: The most popular means of representing integer values  Excess notation: Another means of representing integer values  Both can suffer from overflow errors. 50 Two’s complement notation systems  leftmost bit: sign bit  1: negative  0: positive  Complement: changing all the 0s to 1s, all the 1s to 0s. 0110 and 1001 are complements. 51 Two’s complement notation systems 52 Coding the value -6 in two’s complement notation using four bits 53 Addition problems converted to two’s complement notation 54 Quiz 55 Quiz 56 Quiz 57  Min and max of signed integers n minimum maximum 8 -27 = -128 27 - 1 = +127 16 -215 = -32,768 215 - 1 = +32,767 32 -231 = -2,147,483,648 231 - 1 = +2,147,483,647 64 -263 = - 263-1 = 9,223,372,036,854,775,808 +9,223,372,036,854,775,807 58 Min and max of unsigned integers n Minimum Maximum 8 0 28 - 1 = 255 16 0 216 - 1 = 65,535 32 0 232 -1 = 4,294,967,295 64 0 264 - 1 = 18,446,744,073,709,551,615 59 An excess eight conversion table 60 An excess notation system using bit patterns of length three 61 Storing Fractions Storing Fractions  Floating-point Notation: Consists of a sign bit, a mantissa field, and an exponent field. ◦ Mantissa: also fraction/significand  Related topics include ◦ Normalized form ◦ Truncation errors 63 Floating-point notation components 64 Encoding the value 2 5⁄8 65 IEEE-754 32-bit Single-Precision Floating-Point Numbers  Exponent: excess-127 (bias-127)  Fraction: implicit leading bit (before radix point). N = (-1)^S x 1.F x 2^(E-127) 66  IEEE-754 32-bit Single-Precision Floating-Point Numbers  Suppose that IEEE-754 32-bit floating-point representation pattern is 0 10000000 110 0000 0000 0000 0000 0000. Sign bit S = 0 ⇒ positive number E = 1000 0000B = 128D Fraction is 1.11B (with an implicit leading 1) = 1 + 1×2^-1 + 1×2^-2 = 1.75D The number is +1.75 × 2^(128-127) = +3.5D 67  IEEE-754 32-bit Single-Precision Floating- Point Numbers Suppose that IEEE-754 32-bit floating-point representation pattern is 1 01111110 100 0000 0000 0000 0000 0000. Sign bit S = 1 ⇒ negative number E = 0111 1110B = 126D Fraction is 1.1B (with an implicit leading 1) = 1 + 2^-1 = 1.5D The number is -1.5 × 2^(126-127)=-0.75D 68 IEEE-754 64-bit Double-Precision Floating-Point Numbers  Exponent: excess-1023  Fraction: implicit leading bit (before radix point). N = (-1)^S x 1.F x 2^(E-1023) 69 Min and Max of Floating-Point Numbers Precision Min Max Single 1.1754 x 10-38 3.40282 x 1038 Double 2.2250 x 10-308 1.7976 x 10308 70 Data Compression Data Compression  Lossy versus lossless  Run-length encoding  Frequency-dependent encoding (Huffman codes)  Relative encoding  Dictionary encoding (Includes adaptive dictionary encoding such as LZW encoding.) 72 Compressing Images  GIF: Good for cartoons  JPEG: Good for photographs  TIFF: Good for image archiving 73 Compressing Audio and Video  MPEG ◦ High definition television broadcast ◦ Video conferencing  MP3 ◦ Temporal masking ◦ Frequency masking 74 Communication Errors Communication Errors  Parity bits (even versus odd)  Checkbytes  Error correcting codes 76 The ASCII codes for the letters A and F adjusted for odd parity 77 An error-correcting code  Hamming distance (of two bit patterns): ◦ Number of bits in which the patterns differ.  Example: ◦ Hamming(000000, 001111) = 4 ◦ Hamming(10101100, 01100100) = 3 78 An error-correcting code 79 Decoding the pattern 010100 80 Quiz 81 Quiz 82 Quiz 83 Mass Storage Mass Storage  On-line versus off-line  Typically larger than main memory  Typically less volatile than main memory  Typically slower than main memory  Typically lower cost than main memory 85 Mass Storage Systems  Magnetic Systems ◦ Disk ◦ Tape  Optical Systems ◦ CD ◦ DVD  Flash Technology ◦ Flash Drives ◦ Secure Digital (SD) Memory Card 86 Source: Wikipedia 87 Source: Wikipedia 88 Source: Wikipedia 89 A magnetic disk storage system 90 A magnetic disk storage system  Data stored on a spinning disk  Disk divided into concentric rings (sectors)  Read/write head moves from one ring to another while disk spins  Access time depends on ◦ Time to move head to correct sector ◦ Time for sector to spin to data location  Fixed number of sectors are placed in a track. 91 A magnetic disk storage system  Seek time ◦ Time needed to position the read/write head over the correct track  Latency ◦ Time for the beginning of the desired sector to rotate under the read/write head  Transfer time ◦ Time for the entire sector to pass under the read/write head and have its contents read into or written from memory 92 A magnetic disk storage system  Given: ◦ Rotation speed = 7,200 rev/min=120 rev/sec = 8.33 msec/rev ◦ Arm movement time = 0.02 msec to move to an adjacent track ◦ On average, the read/write head must move about 300 tracks ◦ Number of tracks/surface = 1,000 ◦ Number of sectors/track = 64 ◦ Number of bytes/sector = 1,024  Seek time ◦ Best case = 0 msec; ◦ Worst case = 999*0.02=19.98 msec ◦ Average case = 300*0.02 = 6 msec 93 A magnetic disk storage system  Given: ◦ Rotation speed = 7,200 rev/min=120 rev/sec = 8.33 msec/rev ◦ Arm movement time = 0.02 msec to move to an adjacent track ◦ On average, the read/write head must move about 300 tracks ◦ Number of tracks/surface = 1,000 ◦ Number of sectors/track = 64 ◦ Number of bytes/sector = 1,024  Latency ◦ Best case = 0 msec; ◦ Worst case = 8.33 msec ◦ Average case = 4.17 msec 94 A magnetic disk storage system  Given: ◦ Rotation speed = 7,200 rev/min=120 rev/sec = 8.33 msec/rev ◦ Arm movement time = 0.02 msec to move to an adjacent track ◦ On average, the read/write head must move about 300 tracks ◦ Number of tracks/surface = 1,000 ◦ Number of sectors/track = 64 ◦ Number of bytes/sector = 1,024  Transfer time ◦ 1/64 * 8.33 msec = 4.17 msec 95 Magnetic tape storage 98 CD storage 99