commit f46ddba72420911c8cc8e17a0c195581668fce7d
parent b90fde1173bb05f889f62e69f4c01c8119ced91d
Author: Alex Balgavy <alex@balgavy.eu>
Date: Thu, 11 Mar 2021 15:11:22 +0100
Coding & crypto notes
Diffstat:
4 files changed, 103 insertions(+), 1 deletion(-)
diff --git a/content/coding-and-cryptography/_index.md b/content/coding-and-cryptography/_index.md
@@ -9,5 +9,5 @@ title = "Coding and Cryptography"
4. [Cyclic linear codes](cyclic-linear-codes)
- [Euclidian algorithm](euclidian-algorithm)
6. [BCH codes](bch-codes)
-
+7. [Reed-Solomon codes](reed-solomon-codes)
<!-- vim: set sua+=.md: -->
diff --git a/content/coding-and-cryptography/abbrevs.vim b/content/coding-and-cryptography/abbrevs.vim
@@ -16,5 +16,7 @@ Ab repd represented
Ab cw codeword
Ab len length
Ab dim dimension
+Ab cyc cyclic
+Ab erpat{,s} error pattern{,s}
iab sup <backspace>^{}<left>
iab sub <backspace>_{}<left>
diff --git a/content/coding-and-cryptography/bch-codes.md b/content/coding-and-cryptography/bch-codes.md
@@ -52,3 +52,37 @@ 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.
diff --git a/content/coding-and-cryptography/reed-solomon-codes.md b/content/coding-and-cryptography/reed-solomon-codes.md
@@ -0,0 +1,66 @@
++++
+title = 'Reed-Solomon Codes'
+template = 'page-math.html'
++++
+
+# Reed-Solomon Codes
+## Codes over $GF(2^{r})$
+$GF(2^{r})[x]$: all polynomials with coefficients from $GF(2^{r})$.
+
+Let $a_{1} \dots a_{n}$ be distinct nonzero elements of $GF(2^{r})$, then $g(x) = (a_{1}+x)(a_{2}+x)\dots (a_{t}+x)$ generates linear cyclic code length $2^{r}-1$ over $GF(2^{r})$.
+
+Let C be linear code length n over $GF(2^{r})$. Then every codeword c(x) can be written uniquely as m(x)g(x) for some m(x) in $GF(2^{r})[x]$ of degree n - deg(g(x)), and g9x) divides f(x) iff f(x) codeword and g(x) divides 1+xⁿ.
+
+Let g(x) degree n-k.
+If g(x) generates linear cyclic code C over $GF(2^{r})$ length $n = 2^{r}-1$ and dimension k, then
+
+$G = \begin{bmatrix} g(x) \\\\ xg(x) \\\\ \vdots \\\\ x^{k-1} g(x) \end{bmatrix}$ and there are $(2^{r})^{k}$ codewords.
+
+## Reed-Solomon codes
+Let $a_{1} \dots a_{n}$ be nonzero elements of $GF(2^{r})$.
+
+$\det
+\begin{bmatrix}
+1 & a_{1} & a_{1}^{2} & \dots & a_{1}^{t-1} \\\\
+1 & a^{2} & a_{2}^{2} & \dots & a_{2}^{t-1} \\\\
+\vdots & \vdots & \vdots & \vdots & \vdots \\\\
+1 & a_{t} & a_{t}^{2} & \dots & a_{t}^{t-1}
+\end{bmatrix} = \prod_{1 \leq j < i \leq t} (a_{i} + a_{j})$
+
+Let $g(x) = (\beta^{m+1} + x)(\beta^{m+2}+x) \dots (\beta^{m+\delta-1}+x)$ be generator of linear cyclic code C over $GF(2^{r})$ of length $n = 2^{r}-1$, where β is primitive element in $GF(2^{r})$ and m is some int.
+Then d(C) ≥ δ.
+
+If C = RS($2^{r}$, δ), then:
+- $n = 2^{r}-1$
+- $k = 2^{r}-δ$
+- d = δ
+- $|C| = 2^{rk}$
+- d = n - k + 1, so RS codes are MDS codes
+
+For int s with 1 ≤ s < $2^{r}-\delta$ and code RS($2^{r}$, δ), shortened code is when take codewords with zeros in last s positions and delete last s positions (or also set of polynomials of deg less than $n - s = 2^{r} - 1 - s$).
+
+$G(x) = \begin{bmatrix} g(x) \\\\ xg(x) \\\\ \vdots \\\\ x^{k-s-1} g(x) \end{bmatrix}$
+
+Let C(s) be shortened RS($2^{r}$, δ), then:
+- $n(s) = 2^{r}-1-s$
+- $k(s) = 2^{r} - \delta - s$
+- $d(s) = \delta$
+
+## Decoding Reed-Solomon codes
+error locations: coordinates where most likely error pattern is nonzero, referred to by error location number.
+
+error magnitude of a location is element of $GF(2^{r})$ occurring in coordinate of most likely error pattern
+
+0. Suppose sent word in RS($2^{r}$, δ) with generator $g(x) = (\beta^{m+1}+x) \dots (\beta^{m+\delta-1} + x)$ and w received.
+Let t = ⌊(δ - 1) / 2⌋.
+1. Calculate $s_{j} = w(\beta^{j})$ for m+1 ≤ j ≤ m+2t
+2. Set e = t and find rank of extended matrix M'
+3. Let e be that rank, solve for $\sigma_{0} \dots \sigma_{e-1}$ the system $M \begin{bmatrix} \sigma_{0} \\\\ \vdots \\\\ \sigma_{e-1} \end{bmatrix} = \begin{bmatrix} s_{m+e+1} \\\\ s_{m+e+2} \\\\ s_{m+2e} \end{bmatrix}$
+4. Find roots of $\sigma_{A}(x) = \sigma_{0} + \sigma_{1} x + \dots + x^{e}$. These roots are location numbers.
+5. Solve for $b_{1} \dots b_{e}$ the system
+$\begin{bmatrix}
+a_{1}^{m+1} & a_{2}^{m+1} & \dots & a_{e}^{m+1} \\\\
+\vdots & \vdots & \vdots & \vdots \\\\
+a_{1}^{m+e} & a_{2}^{m+e} & \dots & a_{e}^{m+e}
+\end{bmatrix} \begin{bmatrix} b_{1} \\\\ b_{2} \\\\ \vdots \\\\ b_{e} \end{bmatrix}
+= \begin{bmatrix} s_{m+1} \\\\ s_{m+2} \\\\ \vdots \\\\ s_{m+e} \end{bmatrix}$ yielding the error magnitudes.
