cyclic-linear-codes.md (3810B)
1 +++ 2 title = 'Cyclic linear codes' 3 template = 'page-math.html' 4 +++ 5 6 # Cyclic linear codes 7 polynomial degree n over K: $a_{0} + a_{1} x + \dots + a_{n} x^{n}$ where coefficients $a_{0} \dots a_{k}$ are elements of K. 8 9 set of polynomials over K is K[x]. 10 11 polynomial division: 12 - f(x) = q(x) h(x) + r(x), where q(x) quotient and r(x) remainder 13 - long division like normal, but arithmetic in K (so xor the terms) 14 15 a code length n can be represented as set of polynomials over K of degree max n-1. 16 - e.g. codeword 0101 ≡ 0(1) + 1(x) + 0(x²) + 1(x³) = x + x³ 17 18 If f(x) ≡ g(x) (mod h(x)), then 19 - f(x) + p(x) ≡ g(x) + p(x) (mod h(x)) 20 - f(x) p(x) ≡ g(x) p(x) (mod h(x)) 21 22 Cyclic shift π(v) of word v is when you move the last digits of v to the beginning (a rotation of the word). 23 24 Code is cyclic if rotating a codeword yields another codeword 25 26 To prove a code is cyclic, show that π(v) ∈ C for each word v in a basis for C. 27 28 To construct cyclic code: pick word v, form set S of all of its cyclic shifts, define C as linear span of S (\<S\>). 29 30 Given word v length n, let corresponding polynomial v(x), then cyclic shifts of v correspond to polynomials $x^{i} v(x) \mod 1 + x^{n}$ 31 32 If C cyclic and v ∈ C, then for any polynomial a(x), c(x) = a(x) v(x) mod (1 + xⁿ) is codeword in C 33 34 Generator polynomial: unique nonzero polynomial of min degree in C 35 36 If g(x) generator polynomial for cyclic C, and n-k = deg(g(x)), 37 - C has dimension K 38 - codewords corresponding to $g(x), x g(x), \dots, x{k-1} g(x)$ are basis for C 39 - c(x) ∈ C ⇔ g(x) divisor of every codeword c(x) 40 41 g(x) generator polynomial ⇔ g(x) divides 1+xⁿ 42 - g(x) = gcd(v(x), 1+xⁿ) 43 - easy way to find: put basis or generator matrix in RREF with last k columns leading, min degree row is the generator polynomial 44 45 ## Generator parity check for cyclic codes 46 Simplest generator matrix is rows of cyclic shifts: $\begin{bmatrix} g(x) \\\\ x g(x) \\\\ \dots \\\\ x^{n-1} g(x) \end{bmatrix}$ 47 48 The k info digits to be encoded are represented by message polynomial a(x). 49 50 Encoding is polynomial multiplication a(x) g(x) yielding c(x). 51 52 parity check: ith row $r_i$ is word corresponding to $r_{i} (x) = x^{i} mod g(x)$ 53 54 syndrome polynomial s(x) = w(x) mod g(x), provided w is the codeword 55 56 ## Finding cyclic codes 57 To find linear cyclic code length n dimension k, find factor of 1+xⁿ with degree n-k. 58 59 irreducible polynomial: if not product of two polynomials in K[x] both with deg ≥ 1 (sort of like a 'prime polynomial') 60 61 e.g. for n = 6, factor 1+x⁶ into irreducible factors and form all products of factors except 1 and 1+x⁶. 62 63 Idempotent polynomial: I(x) = I(x)² (mod 1+xⁿ) 64 65 **Basic factoring** 66 - If $n = 2^{r} s$: 67 - then $1+x^{n} = (1+x^{s})^{2^{r}}$. 68 69 **The number of cyclic codes** 70 - If s odd & $1+x^{s}$ product of z irreducible polynomials 71 - Then 72 - $(2^{r}+1)^{z}$ linear cyclic codes length n 73 - $(2^{r}+1)^{z}-2$ proper linear cyclic codes length n 74 75 How to factor: 76 1. Partition $Z_{n} = \lbrace 0, 1, \dots, n-1 \rbrace$ into "classes" 77 - $c_{i} = \lbrace s = 2^{j} \cdot i (\mod n) | j = 0, 1, \dots, r \rbrace$ where $1 = 2^{r} \mod n$ 78 2. For each class $c_{i}$, form polynomial $c_{i} (x) = \sum_{j \in c_{i}} x^{j}$. 79 3. Find all idempotent polynomials: I(x) = a₀ c₀ + a₁ c₁ + a₂ c₂ + … 80 4. Find corresponding generator polynomials g(x) = gcd(I(x), 1+xⁿ) 81 82 ## Dual cyclic codes 83 **Multiplication of polynomials & dot product of vectors** 84 - If a ↔ a(x), b ↔ b(x), b' ↔ b'(x) = xⁿ b(x⁻¹) mod 1+xⁿ 85 - then a(x) b(x) mod 1+xⁿ = 0 iff ∀k = 0..n-1, $\pi^{k} (a) \cdot b\' = 0$ 86 87 **Dual code for cyclic linear code** 88 - If: 89 - C linear cyclic code length n dimension k generator g(x) 90 - & 1+xⁿ = g(x) h(x) 91 - Then: 92 - $C^{\perp}$ cyclic code, dimension n-k, generator $x^{k} h(x^{-1})$. 93