commit b90fde1173bb05f889f62e69f4c01c8119ced91d
parent af576c4fa0f50ee1cd48201315409f1a4dd1259a
Author: Alex Balgavy <alex@balgavy.eu>
Date: Tue, 2 Mar 2021 23:20:42 +0100
Update coding notes
Diffstat:
1 file changed, 15 insertions(+), 0 deletions(-)
diff --git a/content/coding-and-cryptography/bch-codes.md b/content/coding-and-cryptography/bch-codes.md
@@ -37,3 +37,18 @@ To find min polynomial, find linear combination of {1, a, a², …, $a^{r}$} whi
**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ⁿ.
