commit af576c4fa0f50ee1cd48201315409f1a4dd1259a
parent e5bfadbaa5b6117a488df95cdbb0abecac410c84
Author: Alex Balgavy <alex@balgavy.eu>
Date: Fri, 26 Feb 2021 15:26:27 +0100
Coding & crypto notes
Diffstat:
13 files changed, 454 insertions(+), 320 deletions(-)
diff --git a/content/coding-and-cryptography/_index.md b/content/coding-and-cryptography/_index.md
@@ -3,7 +3,11 @@ title = "Coding and Cryptography"
+++
# Table of Contents
-1. [Lecture 1](lecture-1)
-2. [Lecture 2](lecture-2)
-3. [Lecture 3](lecture-3)
-4. [Lecture 4](lecture-4)
+1. [Introduction, basic concepts](introduction-basic-concepts)
+2. [Linear codes](linear-codes)
+3. [Perfect & related codes](perfect-related-codes)
+4. [Cyclic linear codes](cyclic-linear-codes)
+ - [Euclidian algorithm](euclidian-algorithm)
+6. [BCH codes](bch-codes)
+
+<!-- vim: set sua+=.md: -->
diff --git a/content/coding-and-cryptography/abbrevs.vim b/content/coding-and-cryptography/abbrevs.vim
@@ -0,0 +1,20 @@
+Ab pn{,s} polynomial{,s}
+Ab mat{,s} matri{x,ces}
+Ab lin{in,dep} linearly {in,}dependent
+Ab col{,s} column{,s}
+Ab msg{,s} message{,s}
+Ab degg degree
+Ab gen generator
+Ab lin linear
+Ab parcheck parity check
+Ab syn{,s} syndrome{,s}
+Ab irred irreducible
+Ab corresp corresponding
+Ab prod{,s} product{,s}
+Ab iter iteration
+Ab repd represented
+Ab cw codeword
+Ab len length
+Ab dim dimension
+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
@@ -0,0 +1,39 @@
++++
+title = 'BCH Codes'
+template = 'page-math.html'
++++
+
+# 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}}$}
diff --git a/content/coding-and-cryptography/cyclic-linear-codes.md b/content/coding-and-cryptography/cyclic-linear-codes.md
@@ -0,0 +1,93 @@
++++
+title = 'Cyclic linear codes'
+template = 'page-math.html'
++++
+
+# Cyclic linear codes
+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.
+
+set of polynomials over K is K[x].
+
+polynomial division:
+- f(x) = q(x) h(x) + r(x), where q(x) quotient and r(x) remainder
+- long division like normal, but arithmetic in K (so xor the terms)
+
+a code length n can be represented as set of polynomials over K of degree max n-1.
+- e.g. codeword 0101 ≡ 0(1) + 1(x) + 0(x²) + 1(x³) = x + x³
+
+If f(x) ≡ g(x) (mod h(x)), then
+- f(x) + p(x) ≡ g(x) + p(x) (mod h(x))
+- f(x) p(x) ≡ g(x) p(x) (mod h(x))
+
+Cyclic shift π(v) of word v is when you move the last digits of v to the beginning (a rotation of the word).
+
+Code is cyclic if rotating a codeword yields another codeword
+
+To prove a code is cyclic, show that π(v) ∈ C for each word v in a basis for C.
+
+To construct cyclic code: pick word v, form set S of all of its cyclic shifts, define C as linear span of S (\<S\>).
+
+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}$
+
+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
+
+Generator polynomial: unique nonzero polynomial of min degree in C
+
+If g(x) generator polynomial for cyclic C, and n-k = deg(g(x)),
+- C has dimension K
+- codewords corresponding to $g(x), x g(x), \dots, x{k-1} g(x)$ are basis for C
+- c(x) ∈ C ⇔ g(x) divisor of every codeword c(x)
+
+g(x) generator polynomial ⇔ g(x) divides 1+xⁿ
+- g(x) = gcd(v(x), 1+xⁿ)
+- easy way to find: put basis or generator matrix in RREF with last k columns leading, min degree row is the generator polynomial
+
+## Generator parity check for cyclic codes
+Simplest generator matrix is rows of cyclic shifts: $\begin{bmatrix} g(x) \\\\ x g(x) \\\\ \dots \\\\ x^{n-1} g(x) \end{bmatrix}$
+
+The k info digits to be encoded are represented by message polynomial a(x).
+
+Encoding is polynomial multiplication a(x) g(x) yielding c(x).
+
+parity check: ith row $r_i$ is word corresponding to $r_{i} (x) = x^{i} mod g(x)$
+
+syndrome polynomial s(x) = w(x) mod g(x), provided w is the codeword
+
+## Finding cyclic codes
+To find linear cyclic code length n dimension k, find factor of 1+xⁿ with degree n-k.
+
+irreducible polynomial: if not product of two polynomials in K[x] both with deg ≥ 1 (sort of like a 'prime polynomial')
+
+e.g. for n = 6, factor 1+x⁶ into irreducible factors and form all products of factors except 1 and 1+x⁶.
+
+Idempotent polynomial: I(x) = I(x)² (mod 1+xⁿ)
+
+**Basic factoring**
+- If $n = 2^{r} s$:
+- then $1+x^{n} = (1+x^{s})^{2^{r}}$.
+
+**The number of cyclic codes**
+- If s odd & $1+x^{s}$ product of z irreducible polynomials
+- Then
+ - $(2^{r}+1)^{z}$ linear cyclic codes length n
+ - $(2^{r}+1)^{z}-2$ proper linear cyclic codes length n
+
+How to factor:
+1. Partition $Z_{n} = \lbrace 0, 1, \dots, n-1 \rbrace$ into "classes"
+ - $c_{i} = \lbrace s = 2^{j} \cdot i (\mod n) | j = 0, 1, \dots, r \rbrace$ where $1 = 2^{r} \mod n$
+2. For each class $c_{i}$, form polynomial $c_{i} (x) = \sum_{j \in c_{i}} x^{j}$.
+3. Find all idempotent polynomials: I(x) = a₀ c₀ + a₁ c₁ + a₂ c₂ + …
+4. Find corresponding generator polynomials g(x) = gcd(I(x), 1+xⁿ)
+
+## Dual cyclic codes
+**Multiplication of polynomials & dot product of vectors**
+- If a ↔ a(x), b ↔ b(x), b' ↔ b'(x) = xⁿ b(x⁻¹) mod 1+xⁿ
+- then a(x) b(x) mod 1+xⁿ = 0 iff ∀k = 0..n-1, $\pi^{k} (a) \cdot b\' = 0$
+
+**Dual code for cyclic linear code**
+- If:
+ - C linear cyclic code length n dimension k generator g(x)
+ - & 1+xⁿ = g(x) h(x)
+- Then:
+ - $C^{\perp}$ cyclic code, dimension n-k, generator $x^{k} h(x^{-1})$.
+
diff --git a/content/coding-and-cryptography/euclidian-algorithm.md b/content/coding-and-cryptography/euclidian-algorithm.md
@@ -0,0 +1,24 @@
++++
+title = 'Euclidian algorithm'
+template = 'page-math.html'
++++
+
+# Euclidian algorithm
+Use this if you want the gcd of two polynomials.
+
+Iterative, at each step K is the iteration counter, Q is the quotient, and R is the remainder. S and T give you the multiplication factors.
+
+Let's say we want gcd of f(x) and g(x), with deg(f) ≥ deg(g):
+
+<table>
+<tr> <th>K</th> <th>Q</th> <th>R</th> <th>S(x)</th> <th>T(x)</th> </tr>
+<tr> <td>0</td> <td>-</td> <td>f(x)</td> <td>1</td> <td>0</td> </tr>
+<tr> <td>1</td> <td>f(x) / g(x)</td> <td>g(x)</td> <td>0</td> <td>1</td> </tr>
+<tr> <td>2</td> <td>g(x) / R₂</td> <td>rem( f(x)/g(x) )</td> <td>q₁ s₁ + s₀</td> <td>q₁ t₁ + t₀</td> </tr>
+<tr> <td>3</td> <td>R₂ / R₃</td> <td>rem( g(x)/R₂ )</td> <td>q₂ s₂ + s₁</td> <td>q₂ t₂ + t₁</td> </tr>
+<tr> <td>4</td> <td>R₃ / R₄</td> <td>rem( R₂/R₃ )</td> <td>q₃ s₃ + s₂</td> <td>q₃ t₃ + t₂</td> </tr>
+<tr> <td></td> <td></td> <td><b>0</b></td> <td>⇒ R₄ is the gcd</td> <td></td> </tr>
+</table>
+
+This solves the equation r(x) = t(x) f(x) + s(x) g(x) as R₄ = t₄ f + s₄ g.
+
diff --git a/content/coding-and-cryptography/introduction-basic-concepts.md b/content/coding-and-cryptography/introduction-basic-concepts.md
@@ -0,0 +1,72 @@
++++
+title = "Introduction, basic concepts"
+template = "page-math.html"
++++
+
+# Introduction, basic concepts
+Some definitions:
+- digit: 0, 1
+- word: sequence of digits
+- length: digits in word (|word|)
+- binary code: set C of words
+
+assumptions about transmission channel:
+- length of sent == length of received
+- easy to find beginning of first word
+- noise scattered randomly (not in bursts)
+
+properties of binary channel:
+- symmetric if 0 and 1 transmitted with same accuracy
+- reliability: probability that digit sent == digit received
+ - we assume ½ ≤ p < 1
+
+information rate of code (length n) = $\frac{1}{n} \log_{2} |C|$
+
+## Most likely codeword
+Let $\phi_{p} (v,w)$ be probability that if word v sent over BSC with reliability p, word w is received.
+
+$\phi_{p} (v, w) = p^{n-d} (1-p)^d$ if v and w disagree in d positions.
+
+if v₁ and w disagree in d₁, and v₂ and w in d₂, then $\phi_{p} (v_{1}, w) \leq \phi_{p} (v_{2}, w)$ iff d₁ ≥ d₂.
+- English: the most likely word disagrees in least digits
+
+## Weight and distance
+
+K = {0, 1}, $K^{n}$ = set of all binary words of length n
+
+(Hamming) weight: number of ones
+
+(Hamming) distance: number of differing digits between words
+
+## Max likelihood decoding (MLD)
+Complete:
+- if one word min distance, decode to that
+- else, arbitrarily select one of closest
+
+Incomplete:
+- if one word min distance, decode to that
+- else, ask for retransmission
+ - look for smallest weight in error patterns with C, e.g. 0+w and 1+w
+ - retransmit if same weight
+
+Reliability: probability that if v sent over BSC of prob b, then IMLD concludes that v was sent
+
+$\theta_{p} (c, v) = \sum_{w \in L(v)} \phi_{p} (v, w)$ where $L(v) = \lbrace words \in K^{n} \enspace \| \enspace \text{IMLD correctly concludes v sent} \rbrace$
+
+## Error-detecting codes
+error pattern is u = v + w if v ∈ C sent and w ∈ Kⁿ received.
+
+error detected if u is not a codeword.
+error patterns that can't be detected are sums of codewords
+
+distance of code: smallest d(v, w) ∀v,w.
+
+Code of dist d at least detects patterns of weight d-1, there's at least one pattern of weight d not detected.
+
+t-error-detecting code if detects pattern weight max t, and does not detect at least one pattern of weight t+1.
+so code with dist d is "d-1 error-detecting code"
+
+## Error-correcting codes
+Code C corrects error pattern u if ∀v ∈ C, v+u closer to v than any other word
+
+Code of dist d corrects all error patterns $weight \leq \frac{d-1}{2}$, at least one pat weight $1+\frac{d-1}{2}$ not corrected.
diff --git a/content/coding-and-cryptography/lecture-1.md b/content/coding-and-cryptography/lecture-1.md
@@ -1,55 +0,0 @@
-+++
-title = "Lecture 1"
-template = "page-math.html"
-+++
-
-Some definitions:
-- digit: 0, 1
-- word: sequence of digits
-- length: digits in word (|word|)
-- binary code: set C of words
-
-assumptions about transmission channel:
-- length of sent == length of received
-- easy to find beginning of first word
-- noise scattered randomly (not in bursts)
-
-properties of binary channel:
-- symmetric if 0 and 1 transmitted with same accuracy
-- reliability: probability that digit sent == digit received
- - we assume ½ ≤ p < 1
-
-information rate of code (length n) = $\frac{1}{n} \log_{2} |C|$
-
-## Most likely codeword
-Let $\phi_{p} (v,w)$ be probability that if word v sent over BSC with reliability p, word w is received.
-
-$\phi_{p} (v, w) = p^{n-d} (1-p)^d$ if v and w disagree in d positions.
-
-if v₁ and w disagree in d₁, and v₂ and w in d₂, then $\phi_{p} (v_{1}, w) \leq \phi_{p} (v_{2}, w)$ iff d₁ ≥ d₂.
-- English: the most likely word disagrees in least digits
-
-## Weight and distance
-
-K = {0, 1}, $K^{n}$ = set of all binary words of length n
-
-(Hamming) weight: number of ones
-
-(Hamming) distance: number of differing digits between words
-
-## Max likelihood decoding (MLD)
-Complete:
-- if one word min distance, decode to that
-- else, arbitrarily select one of closest
-
-Incomplete:
-- if one word min distance, decode to that
-- else, ask for retransmission
- - look for smallest weight in error patterns with C, e.g. 0+w and 1+w
- - retransmit if same weight
-
-Reliability: probability that if v sent over BSC of prob b, then IMLD concludes that v was sent
-
-$\theta_{p} (c, v) = \sum_{w \in L(v)} \phi_{p} (v, w)$ where $L(v) = \lbrace words \in K^{n} \enspace \| \enspace \text{IMLD correctly concludes v sent} \rbrace$
-
-
diff --git a/content/coding-and-cryptography/lecture-2.md b/content/coding-and-cryptography/lecture-2.md
@@ -1,104 +0,0 @@
-+++
-title = "Lecture 2"
-template = "page-math.html"
-+++
-
-## Error-detecting codes
-error pattern is u = v + w if v ∈ C sent and w ∈ Kⁿ received.
-
-error detected if u is not a codeword.
-error patterns that can't be detected are sums of codewords
-
-distance of code: smallest d(v, w) ∀v,w.
-
-Code of dist d at least detects patterns of weight d-1, there's at least one pattern of weight d not detected.
-
-t-error-detecting code if detects pattern weight max t, and does not detect at least one pattern of weight t+1.
-so code with dist d is "d-1 error-detecting code"
-
-## Error-correcting codes
-Code C corrects error pattern u if ∀v ∈ C, v+u closer to v than any other word
-
-Code of dist d corrects all error patterns $weight \leq \frac{d-1}{2}$, at least one pat weight $1+\frac{d-1}{2}$ not corrected.
-
-## Linear codes
-Code linear v+w is word in C when v and w in C.
-
-dist of linear code = min weight of any nonzero codeword.
-
-vector w is linear combination of vectors $v_{1} \dots v_{k}$ if scalars $a_1 \dots a_k$ st. $w = a_{1} v_{1} + \dots + a_{k} v_{k}$
-
-linear span \<S\> is set of all linear comb of vectors in S.
-
-For subset S of Kⁿ, code C = \<S\> is: zero word, all words in S, all sums.
-
-## Scalar/dot product
-$\begin{aligned}
-v &= (a_{1} \dots a_{n}) \\\\
-w &= (b_{1} \dots b_{n}) \\\\
-v \dot w &= a_{1} b_{1} + \dots + a_{n} b_{n}
-\end{aligned}$
-
-- orthogonal: v ⋅ w = 0
-- v orthogonal to set S if ∀w ∈ S, v ⋅ w = 0
-- $S^{\perp}$ orthogonal complement: set of vectors orthogonal to S
-
-For subset S of vector space V, $S^{\perp}$ subspace of V.
-
-if C = \<S\>, $C^{\perp} = S^{\perp}$ and $C^{\perp}$ is _dual code_ of C.
-
-To find $C^{\perp}$, compute words whose dot with elements of S is 0.
-
-## Linear independence
-linearly dependent $S = {v_{1} \dots v_{k}}$ if scalars $a_1 \dots a_k$ not all zero st. $a_{1} v_{1} + \dots + a_{k} v_{k} = 0$.
-
-If all scalars have to be zero ⇒ linearly independent.
-
-Largest linearly independent subset: eliminate words that are linear combination of others, iteratively.
-
-## Basis
-Any linearly independent set B is basis for \<B\>
-
-Nonempty subset B of vectors from space V is basis for V if:
-1. B spans V
-2. B is linearly independent
-
-dimension of space is number of elements in any basis for the space.
-
-linear code dimension K contains $2^{K}$ codewords.
-
-$\dim C + \dim C^{\perp} = n$
-
-if ${v_{1} + \dots + v_{k}}$ is basis for V, any vector in V is linear combination of ${v_{1} + \dots + v_{k}}$.
-
-Basis for C = \<S\>:
-1. make matrix A where rows are words in S
-2. find REF of A by row operations
-3. read nonzero rows
-
-Basis for C:
-1. make matrix A where rows are words in S
-2. find REF of A
-3. locate leading cols
-4. original cols corresponding to leading cols are basis
-
-Basis for $C^{\perp}$ ("Algorithm 2.5.7"):
-1. make matrix A where rows are words in S
-2. Find RREF
-3. $\begin{aligned}
- G &= \text{nonzero rows of RREF} \\\\
- X &= \text{G without leading cols} \\\\
- H &= \begin{cases}
- \text{rows corresponding to leading cols of G} &\text{are rows of X} \\\\
- \text{remaining rows} &\text{are rows of identity matrix}
- \end{cases}
- \end{aligned}$
-4. Cols of H are basis for $C^{\perp}$
-
-## Matrices
-product of A (m × n) and B (n × p) is C (m × p), where row i col j is dot product (row i of A) ⋅ (col i of B).
-
-leading column: contains leading 1
-
-row echelon form: zero rows of all at bottom, leading 1s stack from right.
-- reduced REF: each leading col has exactly one 1
diff --git a/content/coding-and-cryptography/lecture-3/index.md b/content/coding-and-cryptography/lecture-3/index.md
@@ -1,87 +0,0 @@
-+++
-title = "Lecture 3"
-template = 'page-math.html'
-+++
-
-## Generating matrices & encoding
-
-- rank of matrix over K: num of nonzero rows in any REF
-- dim k of code C: dim of C as subspace of Kⁿ
- - if C has length n and dist d -- C is (n, k, d) linear code
-- if C linear code of length n and dim k, any matrix whose rows are basis for C is generator matrix for C (must have k rows, n cols, rank k)
-- G generator matrix ⇔ rows of G linearly independent
-- to find a generator matrix, put codewords in matrix and reduce, then take nonzero rows
-
-if G generator matrix for linear code C length n and dimension k, then v = u G ranges over all $2^{K}$ words in C $\forall u \text{length} k \in 2^{k}$
-- → C = { words u G, u in $K^{K}$ }
-- → u₁ G = u₂ G ⇔ u₁ = u₂
-
-info rate of (n, k, d) code: $\frac{\log_{2} (2^{k})}{n} = \frac{k}{n}$
-
-## Parity check matrices
-H parity check matrix for linear code C if columns form basis for dual code $C^{\perp}$.
-- if C length n dimension k, parity check matrix has n rows, n-k columns, n-k rank
-- H parity check ⇔ columns H linearly independent
-- if H parity check matrix for C length n, then C = {words v ∈ Kⁿ | v H = 0}
-
-Matrix G generating and H parity check iff:
-1. rows of G linearly independent
-2. columns of H linearly independent
-3. rows(G) + columns(H) = columns(G) = rows(H)
-4. G H = 0
-
-H parity check for C ⇔ $H^{T}$ generator for $C^{\perp}$
-
-$H ^{T} G ^{T} = (G H) ^{T} = 0$
-
-
-
-## Equivalent codes
-- if $G = [I_{k}, X]$, G in standard form and generator for linear code length n dimension k with standard form G, then first K digits in codeword v = u G form word u in $K^{K}$ ("information digits")
-- you can always permute C and rearrange every word
-- any linear code C equivalent to linear code C' having generator matrix in standard form
-
-## Distance of linear code
-H parity check for linear code C.
-
-C has distance d ⇔ any set d-1 rows of H linearly independent & at least one set d rows of H linearly dependent
-
-## Cosets
-for C linear code length n, u any word length n: coset of C determined by u = C + u = {v + u | v ∈ C}
-
-for C linear code length n, u and v words length n:
-- u ∈ C + v → c + u = C + v
-- u ∈ C + u
-- u + v ∈ C → u and v in same coset
-- u + v ∉ C → u and v in different cosets
-- either C + u = C + v, or the two have no common words
-- |C + u| = |C|
-- C dimension k → exists $2^{n-k}$ different cosets of C, each with $2^{k}$ words
-- C is one of cosets
-
-## MLD for linear codes
-when word w received, choose word u of least weight in coset c + w. conclude that v = w + u sent.
-
-for C linear code length n, H parity check for C, w and u words in Kⁿ:
-- w H = 0 ⇔ w codeword in C
-- w H = u H ⇔ w and u in same coset of C
-- u error pattern in received w → u H sum rows of H corresponding to position where errors in transmission
-- syndrome word w in Kⁿ: w H in $K^{n-k}$
-
-coset leader: word of least weight in coset.
-
-standard decoding array (SDA) matches coset leader u to syndrome u H.
-
-constructing SDA:
-1. list all cosets for code, elect leaders
-2. find parity check H for code
-3. calculate syndromes u H
-
-decoding w received:
-1. calculate syndrome w H
-2. find coset leader u next to syndrome w H = u H in SDA
-3. conclude v = w + u sent
-
-IMLD:
-- num words closest to w = num least weight error patterns in c + w
-- cosets with more than 1 least weight are omitted.
diff --git a/content/coding-and-cryptography/lecture-4.md b/content/coding-and-cryptography/lecture-4.md
@@ -1,70 +0,0 @@
-+++
-title = 'Lecture 4'
-template = 'page-math.html'
-+++
-## Perfect & related codes
-bounds for codes:
-- if ints t ≤ n and word v length n, then num words length n of max distance t from v is $\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{t}$. If t = n, then 2ⁿ.
-- all words of distance t from word v: add to v all words weight t
-- Hamming bound: C length n and distance d = 2t + 1 or 2t + 2, then $|C| = \frac{2^{n}}{\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{t}}$ (i.e. max num of words length n distance d in code)
-- singleton bound: for (n, k, d) linear code, d-1 ≤ n-k
-- for (n, k, d) linear code:
- - d = n-k+1
- - every (n-k) rows of the parity check matrix are linearly independent
- - every k columns of generator matrix are linearly independent
- - C is MDS
-- there exists code length n dimension k distance d if $\binom{n-1}{0} + \binom{n-1}{1} + \dots + \binom{n-1}{d-2} \lt 2^{n-k}$
-
-
-### Perfect codes
-perfect code: if length n, distance d = 2t+1, $|C| = \frac{2^{n}}{\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{t}}$
-
-if C nontrivial perfect code length n, distance d = 2t+1, then n=23 and d=7, or n=2ᴿ-1 for some R ≥ 2 and d=3
-
-if C perfect code length n distance d = 2t+1, then corrects all error patterns weight ≤ t and no others.
-
-### Hamming codes
-Hamming code length 2ᴿ-1 if n = 2ᴿ-1, R ≥ 2, parity check matrix rows consist of all nonzero vectors length R
-
-- has dimension 2ᴿ-1-R, contains $2^{2^{R}-1-R}$ codewords
-- has distance d=3
-- is a perfect single error correcting code
-
-## Cyclic linear codes
-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.
-
-set of polynomials over K is K[x].
-
-polynomial division:
-- f(x) = q(x) h(x) + r(x), where q(x) quotient and r(x) remainder
-- long division like normal, but arithmetic in K (so xor the terms)
-
-a code length n can be represented as set of polynomials over K of degree max n-1.
-- e.g. codeword 0101 ≡ 0(1) + 1(x) + 0(x²) + 1(x³) = x + x³
-
-If f(x) ≡ g(x) (mod h(x)), then
-- f(x) + p(x) ≡ g(x) + p(x) (mod h(x))
-- f(x) p(x) ≡ g(x) p(x) (mod h(x))
-
-Cyclic shift π(v) of word v is when you move the last digits of v to the beginning (a rotation of the word).
-
-Code is cyclic if rotating a codeword yields another codeword
-
-To prove a code is cyclic, show that π(v) ∈ C for each word v in a basis for C.
-
-To construct cyclic code: pick word v, form set S of all of its cyclic shifts, define C as linear span of S (\<S\>).
-
-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}$
-
-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
-
-Generator polynomial: unique nonzero polynomial of min degree in C
-
-If g(x) generator polynomial for cyclic C, and n-k = deg(g(x)),
-- C has dimension K
-- codewords corresponding to $g(x), x g(x), \dots, x{k-1} g(x)$ are basis for C
-- c(x) ∈ C ⇔ g(x) divisor of every codeword c(x)
-
-g(x) generator polynomial ⇔ g(x) divides 1+xⁿ
-- g(x) = gcd(v(x), 1+xⁿ)
-- easy way to find: put basis or generator matrix in RREF with last k columns leading, min degree row is the generator polynomial
diff --git a/content/coding-and-cryptography/lecture-3/conversion.svg b/content/coding-and-cryptography/linear-codes/conversion.svg
diff --git a/content/coding-and-cryptography/linear-codes/index.md b/content/coding-and-cryptography/linear-codes/index.md
@@ -0,0 +1,168 @@
++++
+title = "Linear codes"
+template = "page-math.html"
++++
+
+# Linear codes
+Code linear v+w is word in C when v and w in C.
+
+dist of linear code = min weight of any nonzero codeword.
+
+vector w is linear combination of vectors $v_{1} \dots v_{k}$ if scalars $a_1 \dots a_k$ st. $w = a_{1} v_{1} + \dots + a_{k} v_{k}$
+
+linear span \<S\> is set of all linear comb of vectors in S.
+
+For subset S of Kⁿ, code C = \<S\> is: zero word, all words in S, all sums.
+
+## Scalar/dot product
+$\begin{aligned}
+v &= (a_{1} \dots a_{n}) \\\\
+w &= (b_{1} \dots b_{n}) \\\\
+v \dot w &= a_{1} b_{1} + \dots + a_{n} b_{n}
+\end{aligned}$
+
+- orthogonal: v ⋅ w = 0
+- v orthogonal to set S if ∀w ∈ S, v ⋅ w = 0
+- $S^{\perp}$ orthogonal complement: set of vectors orthogonal to S
+
+For subset S of vector space V, $S^{\perp}$ subspace of V.
+
+if C = \<S\>, $C^{\perp} = S^{\perp}$ and $C^{\perp}$ is _dual code_ of C.
+
+To find $C^{\perp}$, compute words whose dot with elements of S is 0.
+
+## Linear independence
+linearly dependent $S = {v_{1} \dots v_{k}}$ if scalars $a_1 \dots a_k$ not all zero st. $a_{1} v_{1} + \dots + a_{k} v_{k} = 0$.
+
+If all scalars have to be zero ⇒ linearly independent.
+
+Largest linearly independent subset: eliminate words that are linear combination of others, iteratively.
+
+## Basis
+Any linearly independent set B is basis for \<B\>
+
+Nonempty subset B of vectors from space V is basis for V if:
+1. B spans V
+2. B is linearly independent
+
+dimension of space is number of elements in any basis for the space.
+
+linear code dimension K contains $2^{K}$ codewords.
+
+$\dim C + \dim C^{\perp} = n$
+
+if ${v_{1} + \dots + v_{k}}$ is basis for V, any vector in V is linear combination of ${v_{1} + \dots + v_{k}}$.
+
+Basis for C = \<S\>:
+1. make matrix A where rows are words in S
+2. find REF of A by row operations
+3. read nonzero rows
+
+Basis for C:
+1. make matrix A where rows are words in S
+2. find REF of A
+3. locate leading cols
+4. original cols corresponding to leading cols are basis
+
+Basis for $C^{\perp}$ ("Algorithm 2.5.7"):
+1. make matrix A where rows are words in S
+2. Find RREF
+3. $\begin{aligned}
+ G &= \text{nonzero rows of RREF} \\\\
+ X &= \text{G without leading cols} \\\\
+ H &= \begin{cases}
+ \text{rows corresponding to leading cols of G} &\text{are rows of X} \\\\
+ \text{remaining rows} &\text{are rows of identity matrix}
+ \end{cases}
+ \end{aligned}$
+4. Cols of H are basis for $C^{\perp}$
+
+## Matrices
+product of A (m × n) and B (n × p) is C (m × p), where row i col j is dot product (row i of A) ⋅ (col i of B).
+
+leading column: contains leading 1
+
+row echelon form: zero rows of all at bottom, leading 1s stack from right.
+- reduced REF: each leading col has exactly one 1
+
+## Generating matrices & encoding
+- rank of matrix over K: num of nonzero rows in any REF
+- dim k of code C: dim of C as subspace of Kⁿ
+ - if C has length n and dist d -- C is (n, k, d) linear code
+- if C linear code of length n and dim k, any matrix whose rows are basis for C is generator matrix for C (must have k rows, n cols, rank k)
+- G generator matrix ⇔ rows of G linearly independent
+- to find a generator matrix, put codewords in matrix and reduce, then take nonzero rows
+
+if G generator matrix for linear code C length n and dimension k, then v = u G ranges over all $2^{K}$ words in C $\forall u \text{length} k \in 2^{k}$
+- → C = { words u G, u in $K^{K}$ }
+- → u₁ G = u₂ G ⇔ u₁ = u₂
+
+info rate of (n, k, d) code: $\frac{\log_{2} (2^{k})}{n} = \frac{k}{n}$
+
+## Parity check matrices
+H parity check matrix for linear code C if columns form basis for dual code $C^{\perp}$.
+- if C length n dimension k, parity check matrix has n rows, n-k columns, n-k rank
+- H parity check ⇔ columns H linearly independent
+- if H parity check matrix for C length n, then C = {words v ∈ Kⁿ | v H = 0}
+
+Matrix G generating and H parity check iff:
+1. rows of G linearly independent
+2. columns of H linearly independent
+3. rows(G) + columns(H) = columns(G) = rows(H)
+4. G H = 0
+
+H parity check for C ⇔ $H^{T}$ generator for $C^{\perp}$
+
+$H ^{T} G ^{T} = (G H) ^{T} = 0$
+
+
+
+## Equivalent codes
+- if $G = [I_{k}, X]$, G in standard form and generator for linear code length n dimension k with standard form G, then first K digits in codeword v = u G form word u in $K^{K}$ ("information digits")
+- you can always permute C and rearrange every word
+- any linear code C equivalent to linear code C' having generator matrix in standard form
+
+## Distance of linear code
+H parity check for linear code C.
+
+C has distance d ⇔ any set d-1 rows of H linearly independent & at least one set d rows of H linearly dependent
+
+## Cosets
+for C linear code length n, u any word length n: coset of C determined by u = C + u = {v + u | v ∈ C}
+
+for C linear code length n, u and v words length n:
+- u ∈ C + v → c + u = C + v
+- u ∈ C + u
+- u + v ∈ C → u and v in same coset
+- u + v ∉ C → u and v in different cosets
+- either C + u = C + v, or the two have no common words
+- |C + u| = |C|
+- C dimension k → exists $2^{n-k}$ different cosets of C, each with $2^{k}$ words
+- C is one of cosets
+
+## MLD for linear codes
+when word w received, choose word u of least weight in coset c + w. conclude that v = w + u sent.
+
+for C linear code length n, H parity check for C, w and u words in Kⁿ:
+- w H = 0 ⇔ w codeword in C
+- w H = u H ⇔ w and u in same coset of C
+- u error pattern in received w → u H sum rows of H corresponding to position where errors in transmission
+- syndrome word w in Kⁿ: w H in $K^{n-k}$
+
+coset leader: word of least weight in coset.
+
+standard decoding array (SDA) matches coset leader u to syndrome u H.
+
+constructing SDA:
+1. list all cosets for code, elect leaders
+2. find parity check H for code
+3. calculate syndromes u H
+
+decoding w received:
+1. calculate syndrome w H
+2. find coset leader u next to syndrome w H = u H in SDA
+3. conclude v = w + u sent
+
+IMLD:
+- num words closest to w = num least weight error patterns in c + w
+- cosets with more than 1 least weight are omitted.
diff --git a/content/coding-and-cryptography/perfect-related-codes.md b/content/coding-and-cryptography/perfect-related-codes.md
@@ -0,0 +1,30 @@
++++
+title = 'Perfect & related codes'
+template = 'page-math.html'
++++
+# Perfect & related codes
+bounds for codes:
+- if ints t ≤ n and word v length n, then num words length n of max distance t from v is $\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{t}$. If t = n, then 2ⁿ.
+- all words of distance t from word v: add to v all words weight t
+- Hamming bound: C length n and distance d = 2t + 1 or 2t + 2, then $|C| = \frac{2^{n}}{\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{t}}$ (i.e. max num of words length n distance d in code)
+- singleton bound: for (n, k, d) linear code, d-1 ≤ n-k
+- for (n, k, d) linear code:
+ - d = n-k+1
+ - every (n-k) rows of the parity check matrix are linearly independent
+ - every k columns of generator matrix are linearly independent
+ - C is MDS
+- there exists code length n dimension k distance d if $\binom{n-1}{0} + \binom{n-1}{1} + \dots + \binom{n-1}{d-2} \lt 2^{n-k}$
+
+## Perfect codes
+perfect code: if length n, distance d = 2t+1, $|C| = \frac{2^{n}}{\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{t}}$
+
+if C nontrivial perfect code length n, distance d = 2t+1, then n=23 and d=7, or n=2ᴿ-1 for some R ≥ 2 and d=3
+
+if C perfect code length n distance d = 2t+1, then corrects all error patterns weight ≤ t and no others.
+
+## Hamming codes
+Hamming code length 2ᴿ-1 if n = 2ᴿ-1, R ≥ 2, parity check matrix rows consist of all nonzero vectors length R
+
+- has dimension 2ᴿ-1-R, contains $2^{2^{R}-1-R}$ codewords
+- has distance d=3
+- is a perfect single error correcting code
