AP CSP: Data Representation and Compression

Everything you see, hear, or create on a computer—from a simple text message to a complex video game—is ultimately a series of ones and zeros. Understanding how we map the rich world of information onto this simple binary system is a foundational pillar of computer science. It explains storage limits, processing power, and how we can efficiently transmit vast amounts of data across the globe.

The Binary Foundation: Bits and Bytes

All digital data is represented in binary. The smallest unit of data is a bit (binary digit), which can have a value of either 0 or 1. A single bit is a switch, representing two states: on/off, true/false, or yes/no. Alone, it holds very little information. However, when you combine bits, the amount of information you can represent grows exponentially. A group of 8 bits is called a byte, which is the standard fundamental unit for measuring data size (e.g., Kilobyte, Megabyte, Gigabyte).

The key relationship is between the number of bits and the number of unique combinations or states they can represent. For $n$ bits, you can represent $2^n$ unique values. For example:

• 1 bit: $2^1=2$ states (0 or 1).
• 4 bits (a nibble): $2^4=16$ unique combinations.
• 1 byte (8 bits): $2^8=256$ unique combinations.

This formula, $2^n$, defines the information capacity of a binary sequence. It determines everything from the range of numbers we can store to the number of colors we can display.

Representing Different Data Types

Computers use standardized encoding schemes to translate different types of information into binary patterns that can be stored and processed.

Integers: Whole numbers are often stored using straightforward binary conversion. For example, the decimal number 13 is $1101$ in binary ($(1\ast 8)+(1\ast 4)+(0\ast 2)+(1\ast 1)$). With one byte (8 bits), you can represent unsigned integers from 0 ($00000000$) to 255 ($11111111$). For negative numbers or larger ranges, systems like two's complement are used.

Characters: Text is represented by assigning a unique binary number to each letter, digit, and symbol. ASCII (American Standard Code for Information Interchange) is a classic scheme using 7 bits (128 characters), sufficient for English. Unicode (commonly implemented as UTF-8) is a modern, expansive standard that uses variable numbers of bytes (1 to 4) to represent over a million unique characters, covering every world language and emoji. The letter 'A' is 65 in decimal, which is $01000001$ in a standard 8-bit byte.

Colors: In a digital image, color is typically defined by mixing levels of red, green, and blue (the RGB model). Each color component is assigned a numeric intensity value. A common scheme uses 1 byte (8 bits) per color component, allowing 256 intensity levels for red, 256 for green, and 256 for blue. The bit depth here is 24 bits per pixel (8 bits * 3 colors). Using our formula, this allows for $2^{24}$, or about 16.7 million, possible colors for a single pixel. A pure red pixel might be represented as (255, 0, 0), stored in binary as 11111111 00000000 00000000.

Audio: Sound waves are analog, meaning they are continuous. To store them digitally, we must take samples of the sound wave's amplitude at regular intervals, a process called analog-to-digital conversion. Each sample's amplitude is rounded to the nearest representable value, a step called quantization. The sample rate (samples per second) and bit depth (bits per sample) determine the audio quality and file size. Higher rates and depths capture sound more accurately but create more data.

Lossless Compression

Compression reduces the size of a data file. Lossless compression reduces file size without losing any original information. After decompression, the data is bit-for-bit identical to the original. It works by finding and eliminating statistical redundancy.

• Run-Length Encoding (RLE): This simple method replaces sequences (runs) of identical data values with a single value and a count. It's highly effective for images with large areas of solid color. For example, the pixel row "white, white, white, white, black, black" could be encoded as "4 white, 2 black."
• Dictionary-Based Methods (e.g., LZW): These algorithms build a dictionary of frequently occurring patterns (like common sequences of characters in text or patterns in an image) as they read the data. They then replace each pattern with a shorter dictionary code. File formats like .zip, .png, and .gif use lossless compression.

Lossless compression is essential for text, source code, and data files where every single bit must be preserved. However, there is a limit to how much it can compress, determined by the inherent entropy (randomness) of the data.

Lossy Compression

Lossy compression significantly reduces file size by permanently removing some data, specifically information deemed less important to human perception. The decompressed file is an approximation of the original, not an exact copy.

The goal is to achieve compression ratios (original size / compressed size) that are much higher than lossless methods allow, with minimal perceptible loss in quality. This is possible because human senses are imperfect.

• Images (JPEG): The JPEG format transforms color data into a format where the human eye's sensitivity to fine color detail is lower than its sensitivity to brightness. It then discards high-frequency color information that you are less likely to notice. High compression leads to artifacts like blurring or blockiness.
• Audio (MP3, AAC): MP3 compression uses psychoacoustic modeling. It identifies and removes sounds that are masked by louder sounds at similar frequencies or that fall outside the typical range of human hearing. Silences are also compressed heavily.
• Video (MPEG, H.264, H.265): Video compression is profoundly lossy and complex. It uses both spatial compression (compressing individual frames like a JPEG) and temporal compression. Temporal compression saves space by only storing the changes between consecutive frames (called interframe compression), rather than storing every full frame.

Lossy compression is ideal for multimedia (photos, music, streaming video) where perfect fidelity is less critical than manageable file sizes for storage and transmission.

Common Pitfalls

1. Confusing Bits and Bytes: A frequent error is misinterpreting data sizes. Internet speed is often measured in bits per second (Mbps), while file size is measured in bytes (MB). Since there are 8 bits in a byte, a 100 Mbps connection does not download a 100 MB file in one second; it takes about 8 seconds. Always check the units.
2. Assuming More Bits Always Means Better Quality: While a higher bit depth for images or audio generally increases potential quality, it also increases file size. There is a point of diminishing returns where the human senses cannot perceive the improvement. The optimal choice balances quality with efficiency for the intended use.
3. Misapplying Compression Types: Using lossy compression on a text file or software executable would corrupt it, making it unreadable or unusable. Conversely, using lossless compression on a photograph will not reduce its size nearly as much as a judicious lossy compression would. Always match the compression technique to the data type and purpose.
4. Overlooking Metadata: When discussing file sizes, students often forget about metadata—the data about the data. This includes information like the image's dimensions, the audio file's sample rate, the camera used, or the document's author. Metadata is stored alongside the core content and contributes to the overall file size.

Summary

• Binary is Universal: All digital data—numbers, text, images, sound—is ultimately stored and processed as sequences of bits (0s and 1s).
• Capacity is Exponential: The amount of information $n$ bits can represent is $2^n$ unique states. This principle governs everything from color depth to memory addressing.
• Encoding is a Translation: Standards like ASCII/Unicode (text), RGB (color), and sampling/quantization (audio) provide the rules for converting real-world information into binary numbers.
• Lossless vs. Lossy: Lossless compression (e.g., ZIP, PNG) reduces size without data loss and is used where integrity is critical. Lossy compression (e.g., JPEG, MP3) achieves much greater size reduction by removing less-perceptible data, ideal for multimedia.
• Trade-offs are Key: Computer science constantly navigates trade-offs: file size versus quality, processing power versus speed, and storage cost versus fidelity. Understanding data representation makes you literate in these fundamental digital trade-offs.