Linear & Cyclic Codes

Cheatsheet Content

Linear Block Codes A linear block code $(n, k)$ encodes $k$ message bits into $n$ codeword bits. Key properties are: Linearity: The sum (modulo 2) of any two codewords is also a codeword. This means codewords form a $k$-dimensional subspace of $F_2^n$. Generator Matrix ($G$): A $k \times n$ matrix. A message $m$ is encoded as $c = mG$. For systematic codes, $G = [I_k | P]$, where $I_k$ is the $k \times k$ identity matrix. Parity-Check Matrix ($H$): An $(n-k) \times n$ matrix. A vector $c$ is a valid codeword if $cH^T = 0$. For systematic codes, $H = [P^T | I_{n-k}]$. Minimum Distance ($d_{min}$): The smallest Hamming distance between any two distinct codewords. For linear codes, it's the minimum Hamming weight of any non-zero codeword. It determines error detection ($d_{min}-1$) and correction ($t = \lfloor (d_{min}-1)/2 \rfloor$) capabilities. Cyclic Codes Cyclic codes are a special class of linear block codes with an additional property, simplifying their implementation: Cyclic Property: If $c = (c_0, c_1, \dots, c_{n-1})$ is a codeword, then its cyclic shift $c' = (c_{n-1}, c_0, \dots, c_{n-2})$ is also a codeword. Polynomial Representation: Codewords are represented as polynomials over $GF(2)$. A codeword $c$ corresponds to $c(x) = c_0 + c_1x + \dots + c_{n-1}x^{n-1}$. Generator Polynomial ($g(x)$): Each $(n, k)$ cyclic code is defined by a unique generator polynomial $g(x)$ of degree $n-k$, which is a factor of $x^n+1$. All codewords $c(x)$ are multiples of $g(x)$. Systematic Encoding: For a message $m(x)$, the codeword $c(x)$ is formed by calculating parity bits $p(x)$ such that $c(x) = p(x) + x^{n-k}m(x)$ is divisible by $g(x)$. This is done by finding the remainder $p(x)$ when $x^{n-k}m(x)$ is divided by $g(x)$. PN (Pseudo-Noise) Sequences A Pseudo-Noise (PN) sequence is a deterministic binary sequence generated by a Linear Feedback Shift Register (LFSR) that exhibits properties similar to a truly random sequence. Used in spread spectrum, cryptography, and ranging. Properties of PN Sequences (Maximal Length Sequences) 1. Length (Period) For an $m$-stage LFSR, the maximum length is $L = 2^m - 1$. The sequence is periodic. 2. Balance Property In each period, the number of '1's is $(L+1)/2$ and the number of '0's is $(L-1)/2$. 3. Run Property Runs are consecutive identical bits. Distribution of run lengths is predictable (e.g., one run of 1s of length $m$, one run of 0s of length $m-1$). 4. Autocorrelation Property The normalized autocorrelation $R(\tau)$ is 1 for $\tau = 0$ and $-1/L$ for $\tau \neq 0$, showing a sharp peak. Vital for synchronization. 5. Shift-and-Add Property The modulo-2 sum of a PN sequence and its shifted version is another shifted version of the same sequence. 6. Randomness Characteristics Statistically random (uniform distribution, no patterns, low correlation). Slow FHSS (Frequency Hopping Spread Spectrum) In Slow FHSS, the data rate is significantly higher than the hop rate ($R_b > R_h$). Multiple data symbols are transmitted per hop frequency. Offers good interference rejection, but is less robust if jammers predict hops. Key: Multiple bits per hop. Fast FHSS (Frequency Hopping Spread Spectrum) In Fast FHSS, the hop rate is equal to or greater than the data symbol rate ($R_h \ge R_b$). Each data symbol is transmitted across multiple frequency hops. Provides enhanced resistance to jamming and interference due to frequency diversity. Key: Multiple hops per bit/symbol. DSSS BPSK System Direct Sequence Spread Spectrum (DSSS) with BPSK spreads data by multiplying it with a high-rate Pseudo-Noise (PN) sequence, then BPSK modulates a carrier. This expands the signal bandwidth ($R_c \gg R_b$), making it robust against interference/jamming and enabling Code Division Multiple Access (CDMA). Transmitter Data Modulation: Binary data ($d(t)$) converted to bipolar ($\pm 1$). Spreading: Bipolar data multiplied by high-rate PN sequence $c(t)$. Output $s(t) = d(t) \cdot c(t)$. Bandwidth expands from $R_b$ to $R_c$. BPSK Modulation: Spread signal $s(t)$ phase-modulates a carrier: $x(t) = A \cdot s(t) \cdot \cos(2\pi f_c t)$. Receiver Demodulation & Despreading: Received signal multiplied by synchronized carrier, then by an identical, synchronized PN sequence $c(t)$. This recovers $d(t)$ and spreads interference. Filtering & Decision: Low-pass filter recovers original data, removing spread interference. Decision device reconstructs bits. Advantages High Interference/Jamming Resistance. Enables CDMA. Low Probability of Intercept/Detection (LPI/LPD).