Channel Coding

The Fundamental Problem

• A transmitted bit may arrive incorrectly
• Receiver cannot "look harder" to find the error
• Solution: Add carefully designed redundancy
• Structure allows errors to become detectable/correctable

Source vs Channel

• Source Coding: REMOVE redundancy (Compress)
• Channel Coding: ADD useful redundancy (Protect)
• Realm 11 makes information smaller
• Realm 12 makes information safer

Block Code (n, k)

• k = original information bits
• n = total coded bits transmitted
• n - k = added redundancy (parity) bits
• Code Rate R = k/n (higher rate = less redundancy)

Hamming Weight

• The number of non-zero bits in a binary word
• Provides foundation for understanding distance
• Example: 101101 contains four 1s (w = 4)
• Used to evaluate the structure of linear codes

Hamming Distance

• Number of positions where two sequences differ
• d_min: Smallest distance between ANY two valid codewords
• Determines the basic error capability of the code
• The most important concept in the realm

Detection vs Correction

• Detection: "Something is wrong" (Invalid codeword received)
• Correction: "The intended codeword was this one"
• Correction requires significantly more redundancy
• Do not collapse them into the same operation

Geometric Correction

• Imagine valid codewords as points in geometric space
• Noise pushes the received word away from the point
• Nearest-neighbor intuition: select the closest valid point
• If noise pushes it past the halfway mark, an error occurs

Error Capability

• Must memorize exactly based on d_min
• Can DETECT up to: d_min - 1 errors
• Can CORRECT up to: ⌊(d_min - 1)/2⌋ errors
• d_min=5 means Detect 4, Correct 2

Basic Parity

• Add one bit so total 1s follow a chosen rule (Even/Odd)
• Even Parity: Total number of 1s must be even
• Primary use: Detecting single-bit errors
• Fatal Flaw: 2 bit errors cancel the parity effect out

2D Parity

• Arrange data into rows and columns
• Parity exists along multiple dimensions
• Intersection of row/col anomalies identifies corrupted bit
• Transforms detection into basic correction

Linear Block Codes

• Combinations of valid codewords produce valid codewords
• c₁ ⊕ c₂ = c₃ (Modulo-2 addition / XOR)
• Includes classic Hamming codes
• Allows for elegant matrix-based encoding/decoding

G and H Matrices

• Generator Matrix G: Defines how bits are transformed
• Encoding: c = mG
• Parity-Check Matrix H: Defines valid code condition
• Validation: Hcᵀ = 0 (Under modulo-2 arithmetic)

Syndrome Decoding

• Syndrome tells decoder if parity constraints are met
• s = Hrᵀ (Received word multiplied by H)
• s = 0 indicates a valid codeword
• s ≠ 0 identifies the exact location of the error pattern

FEC & Interleaving

• FEC: Correct errors locally without asking for retransmission
• Burst Errors: Clusters of corrupted bits that destroy codes
• Interleaving: Rearranges bits before transmission
• Deinterleaving spreads the burst out, making it correctable

Convolutional & Viterbi

• Unlike Block codes, Convolutional codes introduce MEMORY
• Trellis unfolds encoder state transitions over time
• Viterbi Decoder: Maximum-likelihood path search
• Finds the path with the smallest accumulated distance/metric

16 — The Redundancy Laboratory

The fortress is complete. By understanding Hamming distance and Syndrome decoding, you can now push clean information through a corrupting channel without requesting a retransmission. But all of this relies on abstract 1s and 0s. How do we actually push these logical bits down a physical copper wire or optical fiber? You are now prepared for Realm 13: Baseband & Line Coding.