bch-codes.md (3691B)
1 +++ 2 title = 'BCH Codes' 3 template = 'page-math.html' 4 +++ 5 6 # BCH codes 7 ## Finite fields 8 **Basic roots** 9 - 1 is root of f(x) ⇒ 1+x is divisor/factor of f(x) 10 - g(0) = 0 ⇒ x is divisor/factor of g(x) 11 12 primitive irreducible polynomial: not divisor of $1+x^{m}$ for m < 2ⁿ-1 13 14 in a field, if ab = 0, then a = 0 or b = 0 15 16 To make Kⁿ into field, define multiplication in Kⁿ modulo an irreducible polynomial of degree n (gives you GF(2ⁿ)). 17 18 ## Minimal polynoms 19 Order of nonzero element α ∈ GF(2ⁿ) is smallest positive int m such that $\alpha^{m} = 1$ 20 21 Minimal polynomial of α ∈ GF(2ⁿ) is polynomial in K[x] of min degree with α as root 22 23 $\alpha^{m} = 1$ ⇒ α is root of $1+x^{m}$ 24 25 **Facts about minimal polynomials** 26 - If 27 - a ≠ 0 in GF(2ⁿ) 28 - & $m_{a} (x)$ minimal polynomial of a 29 - Then $m_{a} (x)$ is: 30 - irreducible over K 31 - factor of polynomial f over K where f(a) = 0 32 - unique min polynomial 33 - factor of $1+x^{2^{r}-1}$ 34 35 To find min polynomial, find linear combination of {1, a, a², …, $a^{r}$} which sums to 0 36 37 **Roots of minimal polynomials** 38 - If a ∈ GF(2ⁿ) with min polynomial $m_{a (x)}$ 39 - then roots of $m_{x}$ are {a, a², a⁴, …, $a^{2^{r-1}}$} 40 41 ## Cyclic Hamming codes 42 primitive polynomial degree r is generator polynomial of a cyclic Hamming code of length $2^{r}-1$. 43 44 decoding: if generator polynomial primitive $m_{a} (x)$ and w(x) received, then w(x) = c(x) + e(x) where c(c) is codeword and $e(x) = x^{j}$ (j is the position of 1 in e). 45 46 - if c cyclic code length n, generator g(x), and $a \in GF(2^{r})$ is root of g(x) 47 - then ∀ c(x) ∈ C, c(x) = 0 so $m_{a} (x)$ divisor of c(x) 48 49 ## BCH codes 50 Why? Quite easy decoding, class of BCH codes is extensive. 51 52 For any positive ints r and t, $t \leq 2^{r-1} - 1$, exists BCH length $n = 2^{r-1}$ which is t-error correcting and dimension k = n - r t. 53 54 The 2-error correcting BCH length $2^{r-1}$ is cyclic linear code generated by $g(x) = m_{\beta} (x) m_{\beta^{2}} (x)$, with β primitive element in GF($2^{r}$) and r ≥ 4. g(x) is generator for cyclic code because $n = 2^{r}-1$ and g(x) divides 1+xⁿ. 55 56 For integer r ≥ 4 there is 2-error correcting BCH code for length $n = 2^{r} - 1$, dimension $k = 2^{r}-2r-1$, distance d = 5, having generator polynomial m₁(x) nm₃(x). 57 58 ## Decoding BCH codes 59 Have code ($2^{r}-1$, $2^{r}-2r-1$, 5). 60 61 $H = \begin{bmatrix} 62 \beta_{0} & \beta_{0} \\\\ 63 \beta & \beta^{3} \\\\ 64 \dots & \dots \\\\ 65 \beta^{2^{r}-2} & \beta^{3(2^{r}-2)} 66 \end{bmatrix}$ 67 68 with β primitive element in $GF(2^{r})$. 69 g(x) = m₁(x) m₃(x) 70 71 w received. then syndrome of w = wH = [w(β), w(β³)] = [s₁, s₃] where s₁ and s₃ words length r. 72 - if no error, wH = 0, so s₁, = s₃ = 0 73 - if one error, error polynomial is $e(x) = x^{i}$ 74 - ⇒ wH = eH = [e(β), e(β³)] = $[\beta^{i}, \beta^{3i}]$ = [s₁, s₃] 75 - ⇒ s₁³ = s₃ 76 - if two errors in positions i and j, then $e(x) = x^{i} + x^{j}$ 77 - ⇒ wH = eH = [e(β), e(β³)] = [s₁, s₃] = $[\beta^{i}+\beta^{j}, \beta^{3i}+\beta^{3j}]$ 78 - $\frac{s_{3}}{s_{1}} + s_{1}^{2} = \beta^{i+j}$ 79 - find error positions by solving error locator polynomial $x^{2} + s_{1} x + (\frac{s_{3}}{s_{1}} + s_{1}^{2}) = 0$ 80 81 To decode: 82 1. Calculate syndrome wH = [s₁, s₃] = [w(β), w(β³)] 83 2. If s₁ = s₃ = 0, no errors, so c = w 84 3. If s₁ = 0 and s₃ ≠ 0, ask for retransmission 85 4. If s₁³ = s₃, correct single error at position i, where $s_{1} = \beta^{i}$ 86 5. Form equation $x^{2} + s_{1} x + (\frac{s_{3}}{s_{1}} + s_{1}^{2}) = 0$ 87 6. If has two distinct roots $\beta^{i}, \beta^{j}$, correct at positions i and j. 88 7. If not, at least 3 errors occurred, ask for retransmission.