CS245 - Discrete Structures I: Chapter 4 - Proofs and Error-Correcting Codes

Hierarchy of Modern Systems and the Role of Abstraction

• Modern Computer Systems Architecture: Systems are constructed as a "tower" of stacked layers. Each individual layer is dependent on the layer immediately beneath it to function correctly.

• Real-World Example: A financial transaction on a website relies on a specific hierarchy:     * The Website layer.     * Networking technologies such as $HTTP$, $TCP$, and $IP$.     * Software on the device (Browser).     * The Operating System (OS).     * Physical Hardware.

• The Principle of Abstraction: This fundamental computer science concept allows users and designers to interact with a layer without needing to understand the internal complexities of layers below it. As long as a layer performs its defined job correctly, other layers can build upon it.

• A Tower of Trust: Mathematical proofs serve as the foundation of this trust.     * Definition of a Proof: A convincing argument that establishes a specific claim as a fact.     * The Goal of Proofs: To derive new facts from existing, established facts while successfully persuading the reader of the validity of the new fact.

Fundamental Concepts of Error-Correcting Codes

• Transmission Process Model:     * A sender intends to transmit a message $m$ consisting of $k$ bits.     * The message is converted into a longer $n$-bit codeword ($c$) through an encoding process using a code $C$ (the set of all valid codewords).     * During transmission, the codeword travels through a noisy channel where it may be corrupted, resulting in a received bitstring $c'$.     * The receiver utilizes a decoding process on $c'$ to produce a recovered message $m'$.

• The Ultimate Goal: If the degree of corruption/noise is sufficiently small, the system should ensure that the recovered message is identical to the original message ($m = m'$).

• Code Types:     * Error-detecting codes: These systems can determine if corruption has occurred during transmission but cannot necessarily fix it.     * Error-correcting codes: These systems can both detect that corruption happened and successfully recover the original uncorrupted message.

• The Role of Redundancy: Both systems work by adding extra bits to the original data. This redundancy allows for reliable transmission and storage even in environments prone to data corruption, such as deep-space satellite transmissions susceptible to radiation.

Case Study: Error Detection in Credit Card Numbers

• Scope and Scale: Visa and Mastercard use $16$-digit numbers. Out of all possible combinations, only approximately $10^{15}$ are valid.

• The Check Digit: Validity is determined by a specific arithmetic calculation. If you know any $15$ digits of a card, the $16$th digit (called the "check digit") is mathematically determined.

• Luhn Algorithm (The mod 10 algorithm): Designed to detect common typing mistakes including a single wrong digit, two swapped digits, or single-digit errors.     * Step 1: Starting from the second-to-last digit and moving left, double every second digit.     * Step 2: If the result of doubling is greater than $9$, add the two digits of the result together (e.g., $8 imes 2 = 16 ightarrow 1 + 6 = 7$; $7 imes 2 = 14 ightarrow 1 + 4 = 5$).     * Step 3: Sum all modified digits, the digits that were not doubled, and the check digit.     * Step 4: Check if the total sum is divisible by $10$. A valid number satisfies: $ext{Total} ot ext{equiv} 0 ext{ (mod 10)}$.

• Numerical Example 1 (Valid):     * Card: $4539 ext{ } 1488 ext{ } 0343 ext{ } 6467$     * Doubling every second digit from right: $8, 5, 6, 9, 2, 4, 16, 8, 0, 3, 8, 3, 12, 4, 12, 7$     * Adjusting results $> 9$: $8, 5, 6, 9, 2, 4, 7, 8, 0, 3, 8, 3, 3, 4, 3, 7$     * Sum: $8+5+6+9+2+4+7+8+0+3+8+3+3+4+3+7 = 80$     * $80$ is divisible by $10$, so the number is valid.

• Numerical Example 2 (Invalid):     * Card: $4123 ext{ } 4567 ext{ } 8901 ext{ } 2345$     * Adjusted digits: $8, 1, 4, 3, 8, 5, 3, 7, 7, 9, 0, 1, 4, 3, 8, 5$     * Sum: $76$     * The value $76 ext{ (mod 10)} = 6$. Since it is not $0$, the number is invalid.

Hash Functions and Checksums

• Hash Functions: Map data of arbitrary length to a fixed-size output (the hash value or $h$).     * Mechanism: The sender transmits the message and the hash value $(m, h)$. The receiver calculates the hash of the received message $h' = ext{Hash}(m')$. If $h' = h$, the message is likely correct. If $h' eq h$, an error is detected.     * Capability: Hashes only detect errors; they do not correct them. Cryptographic hashes like $SHA-256$ can detect even a single-bit change with extremely high probability.

• Checksums: A method used for file transfers. A large file is broken into $32$-bit blocks. The blocks are transmitted, followed by a final block representing the bitwise $XOR$ of all previous blocks to verify integrity.

Hamming Distance

• Definition: Let $x, y$ be two $n$-bit strings. The Hamming distance, denoted $ext{Delta}(x, y)$, is the count of positions where the bits differ: $ext{Delta}(x, y) = | ext{curly bracket} i ext{ in } ext{curly bracket} 1, 2, ext{…}, n ext{straight bracket} : x_i eq y_i ext{curly bracket} |$.

• Constraint: The distance is undefined if the strings are of different lengths.

• Calculation Examples:     * $ext{Delta}(011, 101) = 2$ (Positions 1 and 2 differ).     * $ext{Delta}(0011, 0111) = 1$ (Only position 2 differs).     * $ext{Delta}(0000, 1111) = 4$ (All four bits differ).     * $ext{Delta}(10101, 10101) = 0$ (Matches perfectly).

• Mathematical Properties (Metric Properties): For all bitstrings $x, y, z ext{ in } ext{curly bracket} 0, 1 ext{curly bracket}^n$:     * Reflexivity: $ext{Delta}(x, y) = 0$ if and only if $x = y$.     * Symmetry: $ext{Delta}(x, y) = ext{Delta}(y, x)$.     * Triangle Inequality: $ext{Delta}(x, z) ext{ less than or equal to } ext{Delta}(x, y) + ext{Delta}(y, z)$.

Codes, Messages, and Codewords

• Formal Definition of a Code: A code is a set $C ext{ subset or equal to } ext{curly bracket} 0, 1 ext{curly bracket}^n$, where $|C| = 2^k$ for some integer $1 ext{ less than or equal to } k ext{ less than or equal to } n$.

• Terminology:     * Message: Any element of $ext{curly bracket} 0, 1 ext{curly bracket}^k$.     * Codeword: Any element belonging specifically to the set $C$.

• Example Case: A code defined as $C = ext{curly bracket} 000000, 101010, 000111, 100001 ext{curly bracket}$.     * $|C| = 4 = 2^2$, so the message length is $k = 2$. Possible messages are $ext{curly bracket} 00, 01, 10, 11 ext{curly bracket}$.     * Codewords have length $n = 6$.     * This is categorized as a $(6, 2)$ code.

• Redundancy Calculation: In the $(6, 2)$ example, instead of sending $2$ bits, the sender transmits $6$ bits. The extra bits facilitate error management.

Decoding and Errors

• Nearest Neighbor Decoding: If a received bitstring is not in the code, the receiver calculates the distance to all valid codewords and chooses the one with the smallest Hamming distance.     * Scenario: Receive $111110$.         * $ext{Delta}(111110, 000000) = 5$         * $ext{Delta}(111110, 000111) = 4$         * $ext{Delta}(111110, 100001) = 5$         * $ext{Delta}(111110, 101010) = 2$         * Conclusion: Decode as message corresponding to $101010$ (message $11$).

• Operational Dangers:     * Error Detection Failure: A codeword $c$ is corrupted into $c'$, but $c'$ happens to be a separate valid codeword in $C$. The system reports "no error."     * Error Correction Failure: A codeword $c$ is corrupted into $c'$, and $c'$ is closer to an incorrect codeword $c''$ than it is to $c$.

Minimum Distance and Error Theorems

• Minimum Distance ($d$): The smallest Hamming distance between any two distinct codewords in $C$: $d = ext{min} ext{curly bracket} ext{Delta}(x, y) : x, y ext{ in } C ext{ and } x eq y ext{curly bracket}$.

• Code Rate: The ratio between message length ($k$) and codeword length ($n$): $ext{Rate} = rac{k}{n}$. This measures efficiency.

• Trade-off: Higher distance ($d$) increases reliability but typically requires more bits, lowering the rate (efficiency).

• Theorem 4.6 (Detection and Correction): Let $C$ be a code with minimum Hamming distance $d$.     * The code can detect up to $d - 1$ errors.     * The code can correct up to $ext{floor}( rac{d-1}{2})$ errors.

• Specific Odd Distance Theorem: If minimum distance is $2t + 1$, it detects $2t$ errors and corrects $t$ errors.     * Example $d = 9$: $2t + 1 = 9 ightarrow t = 4$. Detects $8$, corrects $4$.     * Example $d = 5$: $2t + 1 = 5 ightarrow t = 2$. Detects $4$, corrects $2$.     * Example $d = 1$: Detects $0$, corrects $0$.

Formal Proof Logic for Theorem 4.6

• Error Detection Proof (Informal): If the minimum distance is $2t + 1$, any corruption of up to $2t$ bits cannot result in another valid codeword because reaching another codeword requires at least $2t + 1$ flips. Thus, we always identify the error.

• Error Correction Proof (Formal):     * Transmitted codeword $x$, received bitstring $c'$, where $ext{Delta}(x, c') ext{ less than or equal to } t$.     * Consider any other codeword $y eq x$.     * Using triangle inequality: $ext{Delta}(c', y) ext{ greater than or equal to } ext{Delta}(x, y) - ext{Delta}(x, c')$.     * Substitute known bounds: $ext{Delta}(c', y) ext{ greater than or equal to } (2t + 1) - t = t + 1$.     * Since $ext{Delta}(x, c') ext{ less than or equal to } t$ and $ext{Delta}(c', y) ext{ greater than or equal to } t+1$, the received string $c'$ is mathematically closer to the original codeword $x$ than any other codeword.

Repetition Codes

• Mechanism: Encode a message $m$ by repeating its bits $ext{ell}$ times.

• Example: A $3$-Repetition code for message $00111$ results in codeword $00111 ext{ } 00111 ext{ } 00111$.

• Lemma 4.11: A Repetition $ext{ell}$ code has:     * $ext{Rate} = rac{1}{ ext{ell}}$.     * $ext{Minimum Distance} = ext{ell}$.

• Proof by Construction: To show code existence (e.g., a code with $k=4, d=3, ext{Rate}=1/3$), we explicitly build the Repetition $3$ code.

The Hamming Code

• Concept: Uses multiple parity bits derived from subsets of the message bits to provide better efficiency than repetition codes while maintaining error protection.

• Parity Function: $ext{parity}(a_1, a_2, ext{…}, a_k) = a_1 ext{ plus-circle } a_2 ext{ plus-circle } ext{…} ext{ plus-circle } a_k$.     * Value is $1$ if there are an odd number of $1$s; value is $0$ if even.

• Hamming (7,4) Code: Encodes a $4$-bit message $ext{angle-bracket} a, b, c, d ext{angle-bracket}$ into a $7$-bit codeword: $ext{angle-bracket} a, b, c, d, b ext{plus-circle} c ext{plus-circle} d, a ext{plus-circle} c ext{plus-circle} d, a ext{plus-circle} b ext{plus-circle} d ext{angle-bracket}$.

• Performance vs. Repetition:     * Repetition $3$ ($k=4$): Codeword length $12$, Distance $3$, Rate $1/3 ext{ approx } 0.33$.     * Hamming (7,4): Codeword length $7$, Distance $3$, Rate $4/7 ext{ approx } 0.57$.

• Optimality:     * Theorem 4.8 (Better News): A code exists with $k=4, d=3, ext{Rate}=4/7$.     * Theorem 4.9 (Bad News): There is no code with $k=4, d=3$ with a rate strictly better than $4/7$. The Hamming code is the theoretical best rate for these parameters.

Questions & Discussion

• Decoding Problem: Given the following Hamming (7,4) received codewords (assuming at most one error in each):     * $0000010$     * $1000000$     * $1011010$     * $1110111$     * Task: Identify the original messages based on the $(7,4)$ encoding scheme provided in the tables and logic above.