commit 81ec40fcc4cf24c1a1b1eae1d64088ed59b46ad0
parent 8221db5b13d2970fab26db27724b9f6920a56f55
Author: Alex Balgavy <alex@balgavy.eu>
Date: Wed, 17 Feb 2021 20:45:58 +0100
Update coding & cryptography notes
Diffstat:
5 files changed, 450 insertions(+), 2 deletions(-)
diff --git a/content/coding-and-cryptography/_index.md b/content/coding-and-cryptography/_index.md
@@ -5,4 +5,5 @@ 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)
diff --git a/content/coding-and-cryptography/lecture-2.md b/content/coding-and-cryptography/lecture-2.md
@@ -82,7 +82,7 @@ Basis for C:
3. locate leading cols
4. original cols corresponding to leading cols are basis
-Basis for $C^{\perp}$:
+Basis for $C^{\perp}$ ("Algorithm 2.5.7"):
1. make matrix A where rows are words in S
2. Find RREF
3. $\begin{aligned}
diff --git a/content/coding-and-cryptography/lecture-3/conversion.svg b/content/coding-and-cryptography/lecture-3/conversion.svg
@@ -0,0 +1,290 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<svg
+ xmlns:dc="http://purl.org/dc/elements/1.1/"
+ xmlns:cc="http://creativecommons.org/ns#"
+ xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
+ xmlns:svg="http://www.w3.org/2000/svg"
+ xmlns="http://www.w3.org/2000/svg"
+ xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
+ xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
+ width="110.04422mm"
+ height="57.965954mm"
+ viewBox="0 0 110.04422 57.965954"
+ version="1.1"
+ id="svg8"
+ inkscape:version="1.0.2 (e86c8708, 2021-01-15)"
+ sodipodi:docname="conversion.svg">
+ <defs
+ id="defs2">
+ <marker
+ style="overflow:visible"
+ id="marker1582"
+ refX="0"
+ refY="0"
+ orient="auto"
+ inkscape:stockid="Arrow1Lend"
+ inkscape:isstock="true">
+ <path
+ transform="matrix(-0.8,0,0,-0.8,-10,0)"
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1pt;stroke-opacity:1"
+ d="M 0,0 5,-5 -12.5,0 5,5 Z"
+ id="path1580" />
+ </marker>
+ <marker
+ style="overflow:visible"
+ id="Arrow1Lend"
+ refX="0"
+ refY="0"
+ orient="auto"
+ inkscape:stockid="Arrow1Lend"
+ inkscape:isstock="true"
+ inkscape:collect="always">
+ <path
+ transform="matrix(-0.8,0,0,-0.8,-10,0)"
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1pt;stroke-opacity:1"
+ d="M 0,0 5,-5 -12.5,0 5,5 Z"
+ id="path1088" />
+ </marker>
+ <marker
+ style="overflow:visible"
+ id="Arrow1Lstart"
+ refX="0"
+ refY="0"
+ orient="auto"
+ inkscape:stockid="Arrow1Lstart"
+ inkscape:isstock="true">
+ <path
+ transform="matrix(0.8,0,0,0.8,10,0)"
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1pt;stroke-opacity:1"
+ d="M 0,0 5,-5 -12.5,0 5,5 Z"
+ id="path1085" />
+ </marker>
+ <rect
+ x="31.003265"
+ y="23.519718"
+ width="41.694046"
+ height="27.261492"
+ id="rect835" />
+ <rect
+ x="31.003265"
+ y="23.519718"
+ width="41.694046"
+ height="27.261492"
+ id="rect835-2" />
+ <rect
+ x="31.003265"
+ y="23.519718"
+ width="41.694046"
+ height="27.261492"
+ id="rect859" />
+ <rect
+ x="31.003265"
+ y="23.519718"
+ width="41.694046"
+ height="27.261492"
+ id="rect835-29" />
+ <rect
+ x="31.003265"
+ y="23.519718"
+ width="41.694046"
+ height="27.261492"
+ id="rect1001" />
+ <rect
+ x="31.003265"
+ y="23.519718"
+ width="41.694046"
+ height="27.261492"
+ id="rect835-2-8" />
+ <rect
+ x="31.003265"
+ y="23.519718"
+ width="41.694046"
+ height="27.261492"
+ id="rect1045" />
+ <rect
+ x="31.003265"
+ y="23.519718"
+ width="41.694046"
+ height="27.261492"
+ id="rect835-2-5" />
+ <rect
+ x="31.003265"
+ y="23.519718"
+ width="41.694046"
+ height="27.261492"
+ id="rect1045-6" />
+ <marker
+ style="overflow:visible"
+ id="Arrow1Lend-8"
+ refX="0"
+ refY="0"
+ orient="auto"
+ inkscape:stockid="Arrow1Lend"
+ inkscape:isstock="true">
+ <path
+ transform="matrix(-0.8,0,0,-0.8,-10,0)"
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1pt;stroke-opacity:1"
+ d="M 0,0 5,-5 -12.5,0 5,5 Z"
+ id="path1088-7" />
+ </marker>
+ <marker
+ style="overflow:visible"
+ id="marker1582-8"
+ refX="0"
+ refY="0"
+ orient="auto"
+ inkscape:stockid="Arrow1Lend"
+ inkscape:isstock="true">
+ <path
+ transform="matrix(-0.8,0,0,-0.8,-10,0)"
+ style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1pt;stroke-opacity:1"
+ d="M 0,0 5,-5 -12.5,0 5,5 Z"
+ id="path1580-6" />
+ </marker>
+ </defs>
+ <sodipodi:namedview
+ id="base"
+ pagecolor="#ffffff"
+ bordercolor="#666666"
+ borderopacity="1.0"
+ inkscape:pageopacity="0.0"
+ inkscape:pageshadow="2"
+ inkscape:zoom="1.5421429"
+ inkscape:cx="309.95832"
+ inkscape:cy="258.96677"
+ inkscape:document-units="mm"
+ inkscape:current-layer="layer1"
+ inkscape:document-rotation="0"
+ showgrid="false"
+ inkscape:window-width="1902"
+ inkscape:window-height="1040"
+ inkscape:window-x="1449"
+ inkscape:window-y="9"
+ inkscape:window-maximized="0" />
+ <metadata
+ id="metadata5">
+ <rdf:RDF>
+ <cc:Work
+ rdf:about="">
+ <dc:format>image/svg+xml</dc:format>
+ <dc:type
+ rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
+ <dc:title></dc:title>
+ </cc:Work>
+ </rdf:RDF>
+ </metadata>
+ <g
+ inkscape:label="Layer 1"
+ inkscape:groupmode="layer"
+ id="layer1"
+ transform="translate(-22.990194,-36.885252)">
+ <text
+ xml:space="preserve"
+ id="text833"
+ style="font-size:4.93888999999999978px;line-height:1.25;font-family:sans-serif;-inkscape-font-specification:'sans-serif, Normal';letter-spacing:0px;white-space:pre;shape-inside:url(#rect835);"
+ transform="matrix(1.1558852,0,0,1.2891948,11.426986,16.683468)"><tspan
+ x="31.003906"
+ y="28.02543"><tspan
+ style="shape-inside:url(#rect835)">H</tspan><tspan
+ style="font-size:65%;baseline-shift:sub">C</tspan><tspan
+ style="shape-inside:url(#rect835)">⟂</tspan></tspan></text>
+ <text
+ xml:space="preserve"
+ id="text833-6"
+ style="font-size:4.93888999999999978px;line-height:1.25;font-family:sans-serif;-inkscape-font-specification:'sans-serif, Normal';letter-spacing:0px;white-space:pre;shape-inside:url(#rect835-2);"
+ transform="matrix(1.1558852,0,0,1.2891948,66.454458,16.494922)"><tspan
+ x="31.003906"
+ y="28.02543"><tspan
+ style="shape-inside:url(#rect835-2)">G</tspan><tspan
+ style="font-size:65%;baseline-shift:sub">C</tspan><tspan
+ style="shape-inside:url(#rect835-2)">⟂</tspan></tspan></text>
+ <text
+ xml:space="preserve"
+ id="text833-8"
+ style="font-size:4.93888999999999978px;line-height:1.25;font-family:sans-serif;-inkscape-font-specification:'sans-serif, Normal';letter-spacing:0px;white-space:pre;shape-inside:url(#rect835-29);"
+ transform="matrix(1.1558852,0,0,1.2891948,12.352031,47.360597)"><tspan
+ x="31.003906"
+ y="28.02543"><tspan
+ style="shape-inside:url(#rect835-29)">G</tspan><tspan
+ style="font-size:65%;baseline-shift:sub">C</tspan></tspan></text>
+ <text
+ xml:space="preserve"
+ id="text833-6-3"
+ style="font-size:4.93888999999999978px;line-height:1.25;font-family:sans-serif;-inkscape-font-specification:'sans-serif, Normal';letter-spacing:0px;white-space:pre;shape-inside:url(#rect835-2-8);"
+ transform="matrix(1.1558852,0,0,1.2891948,67.991836,47.745705)"><tspan
+ x="31.003906"
+ y="28.02543"><tspan
+ style="shape-inside:url(#rect835-2-8)">H</tspan><tspan
+ style="font-size:65%;baseline-shift:sub">C</tspan></tspan></text>
+ <path
+ style="fill:none;stroke:#000000;stroke-width:0.265;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;marker-end:url(#Arrow1Lend)"
+ d="M 58.333332,81.8402 H 101.05392"
+ id="path1083" />
+ <text
+ xml:space="preserve"
+ style="font-size:4.9389px;line-height:1.25;font-family:sans-serif;-inkscape-font-specification:'sans-serif, Normal';letter-spacing:0px;stroke-width:0.264583"
+ x="81.684685"
+ y="40.661774"
+ id="text1395"><tspan
+ sodipodi:role="line"
+ id="tspan1393"
+ x="81.684685"
+ y="40.661774"
+ style="text-align:center;text-anchor:middle;stroke-width:0.264583">"basis for C⟂" </tspan><tspan
+ sodipodi:role="line"
+ x="81.684685"
+ y="47.132256"
+ style="text-align:center;text-anchor:middle;stroke-width:0.264583"
+ id="tspan1432">(Algorithm 2.5.7)</tspan></text>
+ <path
+ style="fill:none;stroke:#000000;stroke-width:0.265;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;marker-end:url(#Arrow1Lend-8)"
+ d="M 101.39693,51.127451 H 58.676348"
+ id="path1083-1" />
+ <text
+ xml:space="preserve"
+ style="font-size:4.9389px;line-height:1.25;font-family:sans-serif;-inkscape-font-specification:'sans-serif, Normal';letter-spacing:0px;stroke-width:0.264583"
+ x="77.894569"
+ y="87.360626"
+ id="text1395-4"><tspan
+ sodipodi:role="line"
+ id="tspan1393-9"
+ x="77.894569"
+ y="87.360626"
+ style="text-align:center;text-anchor:middle;stroke-width:0.264583">"basis for C⟂" </tspan><tspan
+ sodipodi:role="line"
+ x="77.894569"
+ y="93.831108"
+ style="text-align:center;text-anchor:middle;stroke-width:0.264583"
+ id="tspan1432-5">(Algorithm 2.5.7)</tspan></text>
+ <path
+ style="fill:none;stroke:#000000;stroke-width:0.264583px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#marker1582)"
+ d="M 50.612743,54.387255 V 75.833332"
+ id="path1572" />
+ <text
+ xml:space="preserve"
+ style="font-size:4.9389px;line-height:1.25;font-family:sans-serif;-inkscape-font-specification:'sans-serif, Normal';letter-spacing:0px;stroke-width:0.264583"
+ x="22.990194"
+ y="63.823528"
+ id="text1622"><tspan
+ sodipodi:role="line"
+ id="tspan1620"
+ x="22.990194"
+ y="63.823528"
+ style="stroke-width:0.264583">Transpose</tspan></text>
+ <path
+ style="fill:none;stroke:#000000;stroke-width:0.264583px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#marker1582-8)"
+ d="M 105.34314,76.690649 V 55.244572"
+ id="path1572-7" />
+ <text
+ xml:space="preserve"
+ style="font-size:4.9389px;line-height:1.25;font-family:sans-serif;-inkscape-font-specification:'sans-serif, Normal';letter-spacing:0px;stroke-width:0.264583"
+ x="107.84795"
+ y="65.636864"
+ id="text1622-1"><tspan
+ sodipodi:role="line"
+ id="tspan1620-8"
+ x="107.84795"
+ y="65.636864"
+ style="stroke-width:0.264583">Transpose</tspan></text>
+ </g>
+</svg>
diff --git a/content/coding-and-cryptography/lecture-3/index.md b/content/coding-and-cryptography/lecture-3/index.md
@@ -0,0 +1,87 @@
++++
+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
@@ -0,0 +1,70 @@
++++
+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
