BCH codes

Finite fields

Basic roots

• 1 is root of f(x) ⇒ 1+x is divisor/factor of f(x)
• g(0) = 0 ⇒ x is divisor/factor of g(x)

primitive irreducible polynomial: not divisor of $1+x^{m}$ for m < 2ⁿ-1

in a field, if ab = 0, then a = 0 or b = 0

To make Kⁿ into field, define multiplication in Kⁿ modulo an irreducible polynomial of degree n (gives you GF(2ⁿ)).

Minimal polynoms

Order of nonzero element α ∈ GF(2ⁿ) is smallest positive int m such that $\alpha^{m} = 1$

Minimal polynomial of α ∈ GF(2ⁿ) is polynomial in K[x] of min degree with α as root

$\alpha^{m} = 1$ ⇒ α is root of $1+x^{m}$

Facts about minimal polynomials

• If
  • a ≠ 0 in GF(2ⁿ)
  • & $m_{a} (x)$ minimal polynomial of a
• Then $m_{a} (x)$ is:
  • irreducible over K
  • factor of polynomial f over K where f(a) = 0
  • unique min polynomial
  • factor of $1+x^{2^{r}-1}$

To find min polynomial, find linear combination of {1, a, a², …, $a^{r}$} which sums to 0

Roots of minimal polynomials

• If a ∈ GF(2ⁿ) with min polynomial $m_{a (x)}$
• then roots of $m_{x}$ are {a, a², a⁴, …, $a^{2^{r-1}}$}

Cyclic Hamming codes

primitive polynomial degree r is generator polynomial of a cyclic Hamming code of length $2^{r}-1$.

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).

• if c cyclic code length n, generator g(x), and $a \in GF(2^{r})$ is root of g(x)
• then ∀ c(x) ∈ C, c(x) = 0 so $m_{a} (x)$ divisor of c(x)

BCH codes

Why? Quite easy decoding, class of BCH codes is extensive.

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.

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ⁿ.

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).

Decoding BCH codes

Have code ($2^{r}-1$, $2^{r}-2r-1$, 5).

$H = \begin{bmatrix} \beta_{0} & \beta_{0} \\ \beta & \beta^{3} \\ \dots & \dots \\ \beta^{2^{r}-2} & \beta^{3(2^{r}-2)} \end{bmatrix}$

with β primitive element in $GF(2^{r})$. g(x) = m₁(x) m₃(x)

w received. then syndrome of w = wH = [w(β), w(β³)] = [s₁, s₃] where s₁ and s₃ words length r.

• if no error, wH = 0, so s₁, = s₃ = 0
• if one error, error polynomial is $e(x) = x^{i}$
  • ⇒ wH = eH = [e(β), e(β³)] = $[\beta^{i}, \beta^{3i}]$ = [s₁, s₃]
  • ⇒ s₁³ = s₃
• if two errors in positions i and j, then $e(x) = x^{i} + x^{j}$
  • ⇒ wH = eH = [e(β), e(β³)] = [s₁, s₃] = $[\beta^{i}+\beta^{j}, \beta^{3i}+\beta^{3j}]$
  • $\frac{s_{3}}{s_{1}} + s_{1}^{2} = \beta^{i+j}$
  • find error positions by solving error locator polynomial $x^{2} + s_{1} x + (\frac{s_{3}}{s_{1}} + s_{1}^{2}) = 0$

To decode:

1. Calculate syndrome wH = [s₁, s₃] = [w(β), w(β³)]
2. If s₁ = s₃ = 0, no errors, so c = w
3. If s₁ = 0 and s₃ ≠ 0, ask for retransmission
4. If s₁³ = s₃, correct single error at position i, where $s_{1} = \beta^{i}$
5. Form equation $x^{2} + s_{1} x + (\frac{s_{3}}{s_{1}} + s_{1}^{2}) = 0$
6. If has two distinct roots $\beta^{i}, \beta^{j}$, correct at positions i and j.
7. If not, at least 3 errors occurred, ask for retransmission.