AQA GCSE Computer Science: Data Representation and Compression

Fundamentals of Data Compression

• Definition of Data Compression: The application of algorithms to reduce the total physical size (number of bits) required to store or transmit digital files.

• Definition of Decompression: The reciprocal process by which compressed data is reconstructed back into its original or usable format.

• Primary Drivers for Compression:

  • Minimizing physical storage requirements on local disks and remote servers.

  • Reducing transmission time across computer networks and the internet.

  • Enabling real-time streaming of rich multimedia data (sound, images, video) across bandwidth-constrained network infrastructures.

• The High-Definition (HD) Video Bandwidth Problem:

  • Display Specifications: A standard High-Definition television (HD TV) image possesses a pixel resolution of $1920\text{px} \times 1080\text{px}$.

  • Pixel Density per Frame: This produces approximately $2.1\text{ megapixels}$ ($2073600\text{ pixels}$) per frame.

  • Colour Depth: Operating at a standard $24\text{-bit colour}$ depth ($3\text{ bytes}$ per pixel), each raw uncompressed frame requires:     $2073600\text{ pixels} \times 24\text{ bits} = 49766400\text{ bits} \approx 50\text{ megabits}$

  • Frame Rate: Standard broadcast television operates at $25\text{ frames per second}$.

  • Bandwidth Demand: Transmitting raw, uncompressed video at this fidelity requires:     $50\text{ megabits per frame} \times 25\text{ frames per second} = 1.25\text{ gigabits per second (Gb/s)}$

  • Network Limitations: Average residential broadband connections in the United Kingdom typically operate under $70\text{ Mb/s}$. Streaming uncompressed HD video ($1250\text{ Mb/s}$) across a $70\text{ Mb/s}$ network connection is physically impossible without aggressive data compression algorithms.

Compression Categories: Lossy vs. Lossless

• Lossy Compression:

  • Mechanism: Permanently identifies and eliminates redundant, imperceptible, or less critical data from the file.

  • Permanence: Discarded data is permanently lost and cannot be recovered upon decompression.

  • Primary Usage: Media formats where minor data variations are negligible to human perception, including photography, consumer audio, and video streams.

  • Inapplicability to Code and Text: Lossy compression cannot be used for computer software, executable code, databases, or text documents. Removing even single characters or instructions corrupts the syntax, causing syntax errors or critical program failure.

• Digital Artefacts in Lossy Media:

  • Definition: Perceptual distortions, imperfections, or errors introduced into digital images, audio, or video as a direct consequence of lossy compression discarding data.

  • Noise: Visible speckling or fringing commonly appearing along sharp borders between contrasting colours.

  • Blocking: Distinct square or rectangular pixel grids ("macroblocking") appearing when compression algorithms approximate large clusters of adjacent pixels.

• Lossless Compression:

  • Mechanism: Retains all underlying data without discarding any information. Algorithms detect repeated patterns and encode them compactly without losing original precision.

  • Reversibility: When uncompressed, the reconstructed file matches the original bit-for-bit with $100\%$ fidelity.

  • Primary Usage: Executable computer code, textual documentation, sensitive database files, and specialized image formats requiring preservation of sharp edges or transparency (e.g., PNG, TIFF, GIF).

Run Length Encoding (RLE)

• Underlying Principles:

  • A basic form of lossless compression that exploits continuous sequences of identical data elements ("runs").

  • Instead of recording each individual recurring value, RLE records a frequency/data pair containing the frequency (the number of consecutive identical items) followed by the actual data value.

• Worked Example 1: Block Pattern Encoding:

  • Given a run consisting of $12$ consecutive orange pixels followed by $6$ consecutive cyan pixels:

  • Uncompressed recording requires storing all $18$ individual colour states.

  • RLE records the sequence as two frequency/data pairs: $12 \times \text{orange}$, $6 \times \text{cyan}$.

• Worked Example 2: Single-Row Monochrome Bitstream:

  • Convention: Let $1 = \text{white}$ and $0 = \text{black}$.

  • Raw Pixel Stream: $1111000000000000$

  • Uncompressed Length: $16\text{ bits}$.

  • Analysis of Runs: Contains a run of four $1\text{s}$ followed by a run of twelve $0\text{s}$.

  • RLE Frequency/Data Representation: Recorded as $4\text{ }1\text{ }12\text{ }0$.

• Worked Example 3: Two-Dimensional Monochrome Icon Grid:

  • Grid Dimensions: $5\text{ pixels} \times 5\text{ pixels}$ ($25\text{ pixels}$ total).

  • Uncompressed Row Representation ($1 = \text{white}$, $0 = \text{black}$):

  • Row 1: $11110$

  • Row 2: $11110$

  • Row 3: $00000$

  • Row 4: $00000$

  • Row 5: $00000$

  • Contiguous Serialized Bitstream:     $1111011110000000000000000$

  • Run Sequence Derivation:

  • First run: four $1\text{s}$

  • Second run: one $0$

  • Third run: four $1\text{s}$

  • Fourth run: sixteen continuous $0\text{s}$ (one from row 2 plus fifteen across rows 3, 4, and 5)

  • Encoded RLE String:     $4\text{ }1\text{ }1\text{ }0\text{ }4\text{ }1\text{ }16\text{ }0$

Dictionary-Based Text Compression

• Operational Mechanism:

  • Lossless text compression technique that identifies recurring words, phrases, or character patterns throughout a text document.

  • Constructs an indexed lookup table (a "dictionary") where each distinct text pattern is assigned a compact numeric binary code (pointer).

  • The text is then replaced by the sequence of corresponding index codes, followed by the dictionary table.

• Worked Case Study: "An eye for an eye, a tooth for a tooth."

  • Character Count: The phrase contains $38\text{ characters}$ (including spaces and punctuation).

  • Uncompressed ASCII Storage: Using an $8\text{-bit ASCII}$ standard ($1\text{ byte}$ per character):     $38\text{ characters} \times 8\text{ bits} = 304\text{ bits} = 38\text{ bytes}$

  • Encoded Index Sequence:     $\begin{matrix} 1 & 2 & 3 & 4 & 2 & 5 & 6 & 7 & 3 & 6 & 7 & 0 \end{matrix}$

  • Binary Encoded Sequence ($4\text{-bit}$ pointers):     $0001\text{ }0010\text{ }0011\text{ }0100\text{ }0010\text{ }0101\text{ }0110\text{ }0111\text{ }0011\text{ }0110\text{ }0111\text{ }0000$

  • Compressed Text Bit Size:     $12\text{ pointers} \times 4\text{ bits} = 48\text{ bits} = 6\text{ bytes}$

  • Storage Comparison: The encoded token stream requires only $6\text{ bytes}$, which represents approximately $16\%$ of the original text payload (exclusive of dictionary overhead storage).

Huffman Coding: Principles and Tree Construction

• Core Algorithm Concept:

  • A variable-length lossless prefix encoding algorithm invented by David Huffman.

  • Analyzes the frequency of each distinct character within a body of text.

  • Most frequently used characters are assigned the shortest binary paths near the root node of a binary tree.

  • Least frequently occurring characters are placed deepest within the binary tree and assigned longer binary bitstrings.

  • Avoids prefix ambiguity: no assigned character code is ever a prefix of another character code.

• Analysis of "SHE SELLS SEA SHELLS":

  • Frequency Breakdown:

  • S: $6$

  • E: $4$

  • L: $4$

  • Space: $3$

  • H: $2$

  • A: $1$

  • Total Characters: $20$

  • Huffman Binary Tree Path Assignments:

  • S is encoded as $11$

  • E is encoded as $00$

  • L is encoded as $01$

  • Space is encoded as $101$

  • H is encoded as $1001$

  • A is encoded as $1000$

  • Sample Word Encoding:

  • The word LEASH is encoded as:       $01\text{ }00\text{ }1000\text{ }11\text{ }1001$       Total bits used: $2 + 2 + 4 + 2 + 4 = 14\text{ bits}$.

  • Complete Sentence Encoding:

  • Encoded sequence for SHE SELLS SEA SHELLS:       $11\text{ }1001\text{ }00\text{ }101\text{ }11\text{ }00\text{ }01\text{ }01\text{ }11\text{ }101\text{ }11\text{ }00\text{ }1000\text{ }101\text{ }11\text{ }1001\text{ }00\text{ }01\text{ }01\text{ }11$

  • Total bit length: $49\text{ bits}$.

  • Comparison with Standard 7-Bit ASCII:

  • Original sentence contains $20\text{ characters}$.

  • $7\text{-bit ASCII}$ total size:       $20\text{ characters} \times 7\text{ bits} = 140\text{ bits}$

  • Huffman encoded size: $49\text{ bits}$.

  • Overall lossless reduction:       $\frac{140\text{ bits} - 49\text{ bits}}{140\text{ bits}} \times 100\% = \frac{91}{140} \times 100\% = 65\%$ reduction in file size.

• Step-by-Step Tree Construction: "JANE BINNED NINE BAD BANANAS"

  • Frequency Table Compilation:

  • Character count verification: Total string length is $28\text{ characters}$.

  • J: $1$

  • S: $1$

  • I: $2$

  • D: $2$

  • B: $3$

  • E: $3$

  • Space: $4$

  • A: $5$

  • N: $7$

  • Verification: $1 + 1 + 2 + 2 + 3 + 3 + 4 + 5 + 7 = 28$.

  • Step 1: Combine the Lowest Frequency Pair (J and S)

  • Identify nodes with lowest weights: J ($1$) and S ($1$).

  • Form a new bottom-up subtree with root weight $1 + 1 = 2$, with J and S as leaf children.

  • Step 2: Combine the Next Lowest Pair (I and D)

  • Identify nodes with next lowest weights: I ($2$) and D ($2$).

  • Note: The existing subtree [J, S] also has weight $2$. One could pair I or D with that subtree, but pairing I and D creates a distinct subtree of weight $2 + 2 = 4$.

  • Step 3: Merge Character B with Subtree [J, S]

  • Lowest available weights are subtree [J, S] (weight $2$) and characters B (weight $3$) or E (weight $3$).

  • Pair B ($3$) with subtree [J, S] ($2$) under a new parent node of weight $2 + 3 = 5$.

  • Step 4: Merge Character E with Subtree [I, D]

  • Character E ($3$) is combined with subtree [I, D] ($4$).

  • Create a parent node of weight $3 + 4 = 7$.

  • Step 5: Combine Space and Character A

  • The remaining single leaf nodes with lowest weights are Space ($4$) and A ($5$).

  • Combine into an independent subtree of weight $4 + 5 = 9$.

  • Step 6: Merge Subtrees [J, S, B] and [I, D, E]

  • Subtree [J, S, B] has weight $5$. Subtree [I, D, E] has weight $7$. Character N has weight $7$.

  • Joining subtree [J, S, B] ($5$) with subtree [I, D, E] ($7$) produces a balanced branch of combined weight $5 + 7 = 12$.

  • Step 7: Merge Character N and Subtree [Space, A]

  • Character N ($7$) is combined with subtree [Space, A] ($9$) to form a branch of weight $7 + 9 = 16$.

  • Step 8: Construct the Final Root Node

  • Merge branch $12$ and branch $16$ under the primary root node: $12 + 16 = 28$.

  • The root node value ($28$) matches the total character count of the original message.

  • Step 9: Branch Weight Assignment

  • Traverse the tree from top to bottom: assign binary digit 0 to every left-hand branch and binary digit 1 to every right-hand branch.

• Huffman Tree Structural Properties:

  • Different choices when breaking ties between identical frequencies produce alternate tree shapes.

  • Regardless of which valid pairing order is chosen, the resulting Huffman trees remain optimal and prefix-free.

Practical Network Transmission, Streaming, and Buffering

• System Benefits of Data Compression:

  • Packet Reduction: Smaller overall file payloads decompose into fewer data packets, leading directly to reduced transmission times across wide area networks.

  • Network Congestion Relief: Lower packet counts minimize traffic congestion across network routers and backbones.

  • Faster Downloads: Drastically cuts latency and transfer durations for video, web graphics, and audio payloads (including VoIP telecommunication protocols).

  • Bandwidth Allowance Efficiency: Maximizes the utility of metered mobile or broadband monthly data caps.

  • Storage Optimization: Frees storage space on web servers and local solid-state/magnetic disk drives.

• Music Track Download Case Study: "Dancing Queen" by ABBA:

  • Track Length: $3\text{ minutes } 51\text{ seconds} = 231\text{ seconds}$.

  • Compressed MP3 Stream Calculation:

  • MP3 streaming bitrate: $128\text{ kbps}$.

  • Total bits transmitted: $231\text{ s} \times 128\text{ kbps} = 29568\text{ kbits}$.

  • File size in megabytes: $\frac{29568}{1024 \times 8} \approx 3.6\text{ MB}$.

  • Uncompressed CD Audio Stream Calculation:

  • Standard CD audio bitrate: $1411\text{ kbps}$.

  • Total bits transmitted: $231\text{ s} \times 1411\text{ kbps} = 325941\text{ kbits}$.

  • File size in megabytes: $\frac{325941}{1024 \times 8} \approx 39.8\text{ MB}$.

  • Performance Gain: The MP3 compressed file downloads $11.5\text{ times}$ faster and saves approximately $36\text{ MB}$ of bandwidth compared to CD audio.

• Video Streaming Mechanics and Buffering:

  • Real-Time Playback Requirement: Streaming multimedia functions only when data reaches the client device at or faster than the rate at which it is decoded and rendered.

  • Root Cause of Buffering: Buffering delays occur whenever downstream network download throughput drops below the designated playback bitrate of the media stream.

  • Mitigation Strategies:

  • Pre-buffering: Prior to initiating playback, client applications cache an initial reservoir of video frames to absorb transient jitter, latency spikes, or temporary bandwidth drops.

  • Adaptive Bitrate Streaming: Content Delivery Networks (CDNs) continuously monitor client connection stability; if congestion or slow throughput is detected, the server dynamically switches downstream delivery to an alternative, lower-bitrate compressed video stream.

Standard File Formats and Compression Schemes

• Comparative Reference Table: