Data Storage and Representation Study Notes

Bits and Their Storage

• Definition of a Bit:

  • Inside modern digital computers, information is encoded as patterns of $0$s and $1$s called bits (short for binary digits).

  • Bits are fundamentally abstract symbols whose meaning is determined by the application context. Bit patterns can represent numeric values, alphabetic characters, punctuation marks, images, or audio signals.

• Boolean Operations:

  • Boolean operations manipulate true/false values, where $0$ represents false and $1$ represents true. Named in honor of mathematician George Boole ($1815$–$1864$), a pioneer in mathematical logic.

  • AND Operation: Combines two inputs. Produces an output of $1$ if and only if both inputs are $1$; otherwise, the output is $0$. Represents compound statements of the form $P \text{ AND } Q$ (e.g., "Kermit is a frog AND Miss Piggy is an actress").

  • OR Operation: Combines two inputs. Produces an output of $1$ if at least one input is $1$; produces $0$ only when both inputs are $0$. Represents compound statements of the form $P \text{ OR } Q$

  • XOR (Exclusive OR) Operation: Combines two inputs. Produces an output of $1$ if one input is $1$ and the other is $0$ (i.e., when inputs differ). Produces $0$ if both inputs are identical.

  • NOT Operation: Accepts a single input and inverts it. A $1$ input yields a $0$ output, and a $0$ input yields a $1$ output (e.g., transforming "Fozzie is a bear" into "Fozzie is not a bear").

• Gates and Flip-Flops:

  • Gates: Physical devices that compute Boolean operations given input signals. Gates can be built from gears, mechanical relays, optical devices, or semiconductor transistors in electronic circuits (where $0$ and $1$ are represented by distinct voltage levels).

• Flip-Flops: Fundamental building blocks of computer memory circuits that store a single bit.

  • A flip-flop holds an output state of $0$ or $1$ until a pulse on an input line shifts its state.

  • In a standard flip-flop circuit composed of an OR gate, an AND gate, and a NOT gate, placing a temporary $1$ on the upper input forces the persistent output state to $1$.

  • Placing a temporary $1$ on the lower input forces the persistent output state to 0$.\n\n\n\n\n\n - **Step-by-Step State Transition (Setting Output to 1)**:\n 1. A temporary 1$is applied to the upper input while keeping the lower input at$0.\n 2. The upper 1$forces the OR gate output to$1.\n 3. The NOT gate converts the lower 0$into a$1$, so both inputs to the AND gate become$1.\n 4. The AND gate outputs 1, which feeds back into the second input of the OR gate.\n 5. This feedback loop holds the OR gate output at 1$even after the upper input returns to$0$.

• Abstraction and Hierarchy:

  • Flip-flops can be constructed using alternative gate configurations (such as cross-coupled NOR or NAND gates) while maintaining identical external functional properties.

  • Engineers use lower-level circuits as abstract building blocks to construct higher-level, complex integrated systems without needing to re-evaluate internal component details.

• Very Large-Scale Integration (VLSI): Manufacturing technology that fabricates millions of electronic components and flip-flops onto a single silicon semiconductor wafer (chip).

  • Hexadecimal Notation:

• Bit patterns are called bit strings or bit streams. Reading long binary strings is prone to human error.

• Hexadecimal notation uses a single character to represent a $4$‐bit pattern (nibble).

• Since computer bit strings generally have lengths in multiples of four, hexadecimal provides a concise representation ($16$‐bit pattern reduces to $4$ hexadecimal digits).

• Conversion Mapping Table:

  • 0000 = 0

  • 0001 = 1

  • 0010 = 2

  • 0011 = 3

  • 0100 = 4

  • 0101 = 5

  • 0110 = 6

  • 0111 = 7

  • 1000 = 8

  • 1001 = 9

  • 1010 = A

  • 1011 = B

  • 1100 = C

  • 1101 = D

  • 1110 = E

  • 1111 = F

• Example: 10110101 splits into 1011 (B) and 0101 (5), yielding B5. The $16$‐bit pattern 1010010011001000 maps to A4C8.

Main Memory

• Memory Organization:

  • Main memory is a large reservoir of addressable circuitry organized into small units called cells.

  • Standard cell size is $8\,bits$ ($1\,byte$).

  • Bit Ordering within a Cell:

  • Left end: High-order end / Most significant bit (MSB).

  • Right end: Low-order end / Least significant bit (LSB).

• Addressing System:

  • Each cell is assigned a unique numeric address, numbered sequentially starting from $0$.

  • Ordering allows multi-byte data (e.g., $16\,bit$ integers) to be stored across consecutive memory cells.

• Memory Access Operations:

  • Read Operation: Retrieves the bit pattern stored at a specified address without modifying the contents.

  • Write Operation: Overwrites the cell at a specified address with a new bit pattern.

• Random Access Memory (RAM): Memory architecture allowing individual cells to be accessed directly and independently in any arbitrary sequence.

• Dynamic RAM (DRAM): Stores bits as tiny electric charges that decay rapidly. Requires dynamic refresh circuits to repeatedly recharge cells multiple times per second.

• Synchronous DRAM (SDRAM): Incorporates synchronized timing controls to accelerate memory retrieval speeds.

  • Measuring Memory Capacity:

• Computer memory capacities are designed around powers of two ($2^{10} = 1024$).

• Capacity Units:

  • Kilobyte ($KB$): $1024\,bytes$ ($2^{10}\,bytes$).

  • Megabyte ($MB$): $1,048,576\,bytes$ ($2^{20}\,bytes$ or $1024\,KB$).

  • Gigabyte ($GB$): $1,073,741,824\,bytes$ ($2^{30}\,bytes$ or $1024\,MB$).

  • Terabyte ($TB$): $1,099,511,627,776\,bytes$ ($2^{40}\,bytes$ or $1024\,GB$).

• Standardized IEC Binary Prefixes:

  • To resolve ambiguity with decimal metric prefixes ($1000$, $1,000,000$), standards organizations introduced terms: kibibyte ($KiB$), mebibyte ($MiB$), gibibyte ($GiB$), and tebibyte ($TiB$) to explicitly denote powers of 1024$.\n\n# Mass Storage Systems\n\n- **Overview and Comparison with Main Memory**:\n - Mass storage (secondary storage) includes magnetic disks, optical discs, flash drives, and solid-state drives.\n - Advantages: Non-volatility, massive storage volume, lower cost per bit, and removable physical media capability.\n - Disadvantages: Mechanical motion systems introduce significant latency compared to pure electronic RAM circuitry.\n\n- **Magnetic Systems**:\n - **Hard Disk Drives (HDD)**: Utilize rigid spinning platters coated with magnetic film.\n - **Platters and Tracks**: Read/write heads hover above or below spinning platters, tracing concentric rings called **tracks**.\n - **Cylinders**: The set of aligned tracks across all platter surfaces at a single read/write arm position.\n - **Sectors**: Tracks are divided into continuous arcs called sectors. Each sector stores a fixed block of bits (typically 512\,bytes to a few kilobytes).\n\n\n\n - **Zoned-Bit Recording**: High-capacity disk technology where outer tracks (which have larger circumferences) are partitioned into more sectors than inner tracks. Tracks are grouped into approximately 10 zones.\n - **Disk Performance Metrics**:\n - **Seek Time**: Time required to move the read/write head arm to the target track.\n - **Latency (Rotation Delay)**: Average time required for the target sector to rotate underneath the read/write head (half the rotation period).\n - **Access Time**: Total time spent prior to data transfer: \text{Access Time} = \text{Seek Time} + \text{Latency}.\n - **Transfer Rate**: Rate at which data is transferred to or from the disk surface.\n - **Head Crash**: Operational failure where the read/write head contacts the spinning platter surface due to dust particles or mechanical shock, permanently destroying data and hardware. HDDs are factory sealed.\n - **Legacy Magnetic Media**: Magnetic Tape (high capacity, sequential linear access with long seek times) and Floppy Disks (removable single platter cartridges, low storage density).\n\n- **Optical Systems**:\n - **Compact Disk (CD)**: 12\,cm diameter reflective disk. Read using a laser reflecting off microscopic surface variations.\n - **Format**: Features a single continuous track spiraling outward from the inner hub to the outer edge, divided into sectors holding 2\,KB$of data (corresponding to$\frac{1}{75} second of stereo audio).\n\n\n\n - **Rotation Speed**: Audio CD-DA players adjust rotation speed (constant linear velocity) to maintain uniform data throughput. Computer CD drives run at higher, constant rotational speeds.\n - **Capacities**:\n - Standard CD: 600\,MB$–$700\,MB\n - DVD (Digital Versatile Disk): Uses multiple semi-transparent layers and tighter laser focus to achieve several gigabytes capacity.\n - BD (Blu-ray Disk): Employs a blue-violet laser with shorter wavelength for finer focal precision, providing over 5\times the capacity of a DVD.\n\n- **Flash Memory and Solid-State Storage**:\n - **Flash Memory Technology**: Stores bits by trapping electrons in silicon dioxide micro-chambers via electrical signals. Non-volatile without external power supply.\n - **Operational Limits**: Data must be erased in large blocks rather than individual bytes. Repeated write/erase cycles degrade silicon dioxide chambers over time.\n - **Flash Drives**: Portable, cap-protected USB units providing hundreds of gigabytes of non-volatile storage.\n - **Solid-State Disks (SSD)**: Mass storage units built from flash memory designed as direct drop-in replacements for HDDs. Advantages include shock resistance, silent operation, zero seek/latency delay, and fast access times. Employ **wear-leveling** algorithms to dynamically reallocate write operations across cells.\n - **SD Cards (Secure Digital)**: Compact flash memory cards used in smartphones, digital cameras, and mobile hardware.\n - Standard SD: Up to 2\,GB\n - SDHC (High Capacity): Up to 32\,GB\n - SDXC (Extended Capacity): Exceeds 1\,TB\n\n# Representing Information as Bit Patterns\n\n- **Representing Text**:\n - Text is represented by assigning each character or symbol a unique bit pattern.\n - **ASCII (American Standard Code for Information Interchange)**:\n - Established by ANSI. Uses 7$‐bit patterns to encode English letters (upper and lower case), digits$0$‐$9, punctuation, and control characters (line feed, carriage return, tab).\n - Standard ASCII is padded with a leading 0$to fit$8$‐bit ($1\,byte$) cells, providing$128$base character codes and$128 extended patterns.\n - **ISO Standards**: Extended 8-bit ASCII variants tailored for regional language groups (e.g., adding symbols for European vowels ä, ö, ü, and currency like the British pound £).\n - **Unicode and UTF-8**:\n - Developed to support global multilingual text formatting within a single standard.\n - Unicode assigns unique codes using up to 21\,bits.\n - **UTF-8**: Variable-length encoding standard. Uses 8\,bits$for standard ASCII,$16\,bits$for Asian/Hebrew scripts, and$24\,bits$‐$32\,bits for rare/specialized symbols.\n - **Text Files vs. Word Processing Files**:\n - **Text File**: Plain sequence of character-by-character ASCII or UTF-8 encodings edited by utility text editors.\n - **Word Processor File**: Complex format containing textual ASCII/Unicode strings interspersed with proprietary metadata for font styles, paragraph layout, alignment, and formatting.\n\n- **Representing Numeric Values**:\n - ASCII string encoding of numbers is inefficient (e.g., storing 25$as ASCII text requires$2\,bytes$/$16\,bits$and can only store values up to$99).\n - Pure binary integer representation allows a 16$‐bit pattern to store values from$0$to$65,535.\n - Numeric values are stored using specialized binary encodings: Two's Complement for signed integers and Floating-Point notation for fractional real numbers.\n\n- **Representing Images**:\n - **Bitmap (Raster) Graphics**: Images constructed as a two-dimensional grid of pixels (picture elements).\n - Black-and-white: 1\,bit$per pixel ($0$= black,$1 = white).\n - Grayscale: Typically 1\,byte$($8\,bits$) per pixel ($256 shade levels).\n - RGB Encoding: Uses 3\,bytes$per pixel ($1\,byte$for Red,$1\,byte$for Green,$1\,byte for Blue intensity).\n - Luminance/Chrominance Encoding: Encodes a pixel using Luminance (Y$, brightness/white light) and two color differences: Blue Chrominance ($C_b$) and Red Chrominance ($C_r).\n - **Vector (Geometric) Graphics**: Describes images as collections of geometric primitives (lines, curves, polygons) using analytic geometry.\n - Scalable to any dimension without loss of clarity or pixelation.\n - Standards: TrueType (fonts), PostScript (document rendering), and CAD systems.\n\n- **Representing Sound**:\n - **Sampling Method**: Measures wave amplitude at uniform time intervals.\n - Long-distance telephony: Sample rate of 8000\,samples/second.\n - Audio CD quality: Sample rate of 44,100\,samples/second$with$16\,bits$per sample ($32\,bits$per stereo sample pair), producing over$1\,Mbit per second of audio.\n - **MIDI (Musical Instrument Digital Interface)**:\n - Stores synthesizer commands (note pitch, start time, duration, instrument code, volume) rather than recording the acoustic signal.\n - Extremely compact (e.g., a 2$‐second clarinet note requires$3\,bytes$via MIDI versus over$2,000,000\,bits via PCM sampling).\n\n# The Binary System\n\n- **Binary Positional Notation**:\n - Base 10$positional weights represent powers of ten ($10^0 = 1$,$10^1 = 10$,$10^2 = 100).\n - Base 2$binary weights represent powers of two ($2^0 = 1$,$2^1 = 2$,$2^2 = 4$,$2^3 = 8$,$2^4 = 16$,$2^5 = 32).\n - Decoding binary string 100101_2:\n    1 \times 32 + 0 \times 16 + 0 \times 8 + 1 \times 4 + 0 \times 2 + 1 \times 1 = 37\n\n- **Algorithm for Converting Base 10 Integer to Binary**:\n 1. Divide the integer by 2 and record the remainder.\n 2. Continue dividing the resulting quotient by 2$and recording remainders until quotient equals$0$.

• Read the remainders from bottom to top (last recorded remainder is the MSB).

• Example (Converting $13$ to Binary):

  • $13 \div 2 = 6$ remainder $1$

  • $6 \div 2 = 3$ remainder $0$

  • $3 \div 2 = 1$ remainder $1$

  • $1 \div 2 = 0$ remainder $1$

  • Binary output: $1101_2$.

  • Binary Addition:

• Elementary binary addition rules:

  • $0 + 0 = 0$

  • $0 + 1 = 1$

  • $1 + 0 = 1$

  • $1 + 1 = 10_2$ ($0$ write-down, carry $1$)

  • $1 + 1 + 1 = 11_2$ ($1$ write-down, carry $1$)

  • Binary Fractional Representations:

• Uses a radix point (binary decimal point).

• Fractional column positional values proceed as negative powers of two:     $2^{-1} = \frac{1}{2}$, $2^{-2} = \frac{1}{4}$, $2^{-3} = \frac{1}{8}$, $2^{-4} = \frac{1}{16}$

• Example: Decoding $101.101_2$:     $4 + 0 + 1 + 0.5 + 0 + 0.125 = 5.625$ (or $5\frac{5}{8}$)

Storing Integers

• Two's Complement Notation:

  • Fixed bit-length encoding standard for signed integer arithmetic.

  • Sign Bit: The most significant (leftmost) bit indicates sign ($0$ for non-negative, $1$ for negative).

  • Encoding Non-negative Values: Formatted as plain binary numbers starting with 0$.\n - **Encoding Negative Values (Copy-and-Complement Algorithm)**:\n 1. Write the non-negative binary equivalent for the target magnitude.\n 2. Scan bits right-to-left, copying bits unchanged up to and including the first 1$.

  1. Invert (complement) all remaining bits to the left ($0 \rightarrow 1$, $1 \rightarrow 0$).

  • Example for $-6$ in $4$‐bit system: Positive $6$ is 0110. Copying right-to-left yields 0 then 1. Inverting remaining bits yields 1010.

• Two's Complement Range Limits:

  • For an $n$‐bit system, valid representable values range from $-2^{n-1}$ to 2^{n-1} - 1$.\n - 3$‐bit system:$-4$to$3\n - 4$‐bit system:$-8$to$7\n - 16$‐bit system:$-32,768$to$32,767\n - 32$‐bit system:$-2,147,483,648$to$2,147,483,647\n\n- **Addition and Subtraction in Two's Complement**:\n - Addition is performed using standard binary bit addition. Any carry bit extending beyond the fixed bit length on the left is truncated.\n - Subtraction A - B$is executed by negating$B$into its two's complement form$-B$and calculating$A + (-B).\n\n- **The Problem of Overflow**:\n - Occurs when a arithmetic operation produces a result outside the representable range of the fixed bit pattern.\n - Detected when adding two positive numbers yields a negative sign bit (1$), or adding two negative numbers yields a positive sign bit ($0).\n\n- **Excess Notation**:\n - Fixed bit-length system where bit patterns are listed sequentially in binary order, with the midpoint pattern (starting with a leading 1) assigned to represent zero.\n - An n$‐bit pattern uses a bias offset of$2^{n-1}.\n - 4$‐bit pattern = **Excess 8 Notation** (`1000` =$0$, `1111` =$7$, `0000` =$-8).\n - 5$‐bit pattern = **Excess 16 Notation** (`10000` =$0).\n - 3$‐bit pattern = **Excess 4 Notation** (`100` =$0).\n\n# Storing Fractions\n\n- **Floating-Point Notation Structure**:\n - Encodes real numbers using sign, exponent, and mantissa fields.\n - **8-bit Model Example Layout**:\n - Bit 7$(Sign Bit):$0$for positive,$1 for negative.\n - Bits 6$‐$4$(Exponent Field):$3\,bits stored in Excess 4 notation.\n - Bits 3$‐$0$(Mantissa Field):$4\,bits storing significant binary fractional digits.\n\n- **Decoding Floating-Point Bit Patterns**:\n 1. Extract mantissa field and place a radix point on its left (`.mantissa`).\n 2. Extract exponent field and decode from Excess 4 notation to get exponent value e\n 3. Move the radix point e$places right (if$e > 0$) or left (if$e < 0).\n 4. Apply the sign bit.\n - **Example (Decoding `01101011`)**:\n - Sign bit: 0 (positive).\n - Exponent `110`: Excess 4 representation of +2$.

  • Mantissa .1011 shifted $2$ places right yields $10.11_2 = 2\frac{3}{4}$.

• Normalized Form:

  • Floating-point encodings require the mantissa field to be shifted so that its leading bit is always $1$.

  • Eliminates redundant representations for identical values. Value zero is represented as a bit string of all $0$s.

• Truncation and Round-Off Errors:

  • Occur when the mantissa field lacks sufficient bit capacity to store low-order bits (e.g., attempting to encode $2\frac{5}{8}$ [10.101_2] into a $4$‐bit mantissa drops the trailing $\frac{1}{8}$ bit, truncating value to $2\frac{1}{2}$).

  • Base $10$ fractions like $\frac{1}{10}$ ($0.1$) produce infinitely repeating non-terminating binary fractions, causing unavoidable truncation errors in floating-point representations.

  • Non-associative arithmetic: Adding a very small floating-point number to a very large number can result in the small number being completely truncated. Small numbers should be summed together first.

• Standard IEEE Formats:

  • Single Precision Floating Point: $32\,bits$ total ($1\,bit$ sign, $8\,bits$ exponent, $23\,bits$ mantissa). Precision of approximately $7$ decimal digits.

  • Double Precision Floating Point: $64\,bits$ total ($1\,bit$ sign, $11\,bits$ exponent, $52\,bits$ mantissa). Precision of approximately $15$ decimal digits.

Questions & Discussion

• Questions & Exercises Review:

  • Question: What input bit patterns cause a circuit with an XOR gate feeding an AND gate to produce an output of $1$?

  • Answer: The output of the AND gate is $1$ only when both its inputs are $1$. Therefore, the lower direct input must be $1$, and the XOR gate output must be $1$. The XOR gate produces $1$ when its two inputs differ. Thus, valid input patterns are 101 and 011 (where top two inputs differ and the bottom input is $1$).

  • Question: If a memory cell address $5$ contains value $8$, what is the difference between writing $5$ into cell $6$ versus moving contents of cell $5$ to cell $6$?

  • Answer: Writing $5$ into cell $6$ stores the literal value $5$ at address $6$. Moving contents of cell $5$ into cell $6$ copies the stored value ($8$) from address $5$ into address 6$.\n\n - **Question**: Swap the contents of memory cells 2$and$3. What is wrong with:\n - Step 1: Move contents of cell 2$to cell$3$.

  • Step 2: Move contents of cell $3$ to cell 2$.\n - **Answer**: Step 1 overwrites cell 3$, destroying its original value. To correctly swap, an additional temporary cell (e.g., cell$4) must be used:\n 1. Move contents of cell 2$to cell$4$.

    2. Move contents of cell $3$ to cell 2$.\n 3. Move contents of cell 4$to cell$3$.

  • Question: How many total bits exist in a $4\,KB$ memory?

  • Answer: $4\,KB = 4 \times 1024\,bytes = 4096\,bytes$. Multiplying by $8\,bits/byte$ yields $32,768\,bits$.

  • Question: When recording on a multi-platter disk system, should we fill an entire disk surface before moving to another surface, or fill an entire cylinder before moving to another cylinder?

  • Answer: Fill an entire cylinder first. Moving between tracks on a single cylinder requires only switching read/write head electronics, avoiding physical seek arm motion delays.

  • Question: What ethical implications exist regarding software truncation errors?

  • Answer: Responsibility for software failure or structural damages resulting from numerical truncation involves hardware designers, software architects, programmers, and deployment managers. Considerations include whether software updates/patches were made available, applied, or if software was improperly altered or pirated.