Title: Part II / Coding and Cryptography
Tags: Error::Control::Codes Linear::Codes Cyclic::Codes Cryptography Noiseless::Coding Entropy Introduction::to::Coding

Q: Definition. A discrete memoryless channel (DMC) is [...] The channel matrix is [...]
A: a channel for which \[P_{ij} = P(b_j \text{ received } | a_i \text{ sent })\]is the same each time a channel is used and it is independent of the past and future uses.; the r x s matrix with entires \(p_{ij}\).

Q: Definition. Let \(\Sigma_1, \Sigma_2\) be two alphabets. A code is [...] are called codewords.
A: a function \(f: \Sigma_1 \to \Sigma_2^*\). The strings \(f(x), x \in \Sigma\)

Q: Definition. A code f is decipherable if [...]
A: f* is injective.

Q: Notation. If \(|\Sigma_1| =m , |\Sigma_2| = a\) then we say f is an a-ary code of size m. A prefix-free code is [...]
A: a code where no codeword is a prefix of any other.

Q: Theorem. Kraft's Inequality. Let \(|\Sigma_1| = m, |\Sigma_2| = a\). A prefix-free code \(f: \Sigma_1 \to \Sigma_2^*\) with word lengths \(s_1, \dots , s_m\) exists iff \(\sum_{i=1}^m a^{-s_i} \le 1\).
A: \((\implies)\)Consider a tree where each node has a descendents, labelled by the elements of \(\Sigma_2\). Each codeword corresponds to a node, the path from the root to this node spelling out the codeword. Assuming f is prefix-free no codeword is the is the ancestor of any other. Now view the tree as a network with water being pumped in at constant rate and dividing the flow equally at each node. The total amount of water with extract at the codewords is \(\sum_{i=1}^m a^{-s_i}\) which is therefore \(\le 1\).
(\(\impliedby\))Conversely, we can construct a prefix-free code with word lengths \(s_1, \dots , s_m\) WLOG \(s_1 \le \dots \le s_m\). We pick codewords \(s_1 , s_2, \dots \) sequentially ensuring previous codewords are not prefixes. Suppose there is no valid choice for the rth codeword. Then constructing the tree as above gives \[\sum_{i=1}^{r-1}a^{-s_i} = 1\]contradicting our assumption. So we can construct a prefix-free code.

Q: Theorem. McMillan. Every decipherable code satisfies Kraft's inequality.
A: Let \(f:\Sigma_1 \to \Sigma_2^*\) be a decipherable code with word lengths \(s_1 ,\dots, s_m\) and \(s = \max_{1 \le i \le m} s_i\). Let \(r\in \mathbb{N}\) \[(\sum_{i=1}^m a^{-s_i})^r = \sum_{l=1}^{rs} b_l a^{-l}\]where \(b_l\) is the number of ways of choosing r codewords with total length l. \[f \text{ decipherable} \implies b_l \le |\Sigma_2^l| = a^l\]Then \((\sum_{i=1}^m a^{-s_i})^r \le \sum_{l=1}^{rs} a^l a^{-l} = rs \implies \sum_{i=1}^m a^{-s_i} \le (rs)^{1/r} \to 1\) as \(r \to \infty\)
Therefore \(\sum_{i=1}^m a^{-s_i} \le 1\)

Q: Corollary. A decipherable code with prescribed word lengths exists iff [...]
A: there exists a prefix-free code with the same word lengths.

Q: Definition. The entropy of X is \[[...]\]
A: H(X) = H(p_1, \dots , p_n)= -\sum_{i=1}^n p_i \log_2 p_i

Q: Lemma. Gibbs' inequality. Let \(p_1, \dots , p_n\) and \(q_1, \dots , q_n\) be probability distributions. Then \[-\sum_{i=1}^n p_i \log p_i \le - \sum_{i=1}^n p_i \log q_i\]with equality iff \(p_i = q_i\).
A: We prove for \(\ln\) and divide by \(\ln 2\) at the end.
Note, \(\ln x \le x-1\) with equality iff \(x =1\)
Let \(I = \{1 \le i \le n : p_i \neq 0\}\)
\[\ln(q_i / p_i) \le q_i / p_i - 1 \; \; \; \forall i \in I\]\[\sum_{i \in I} p_i \ln (q_i / p_i) \le \sum_{i \in I} q_i - \sum_{i \in I}p_i \le 0\]\[\implies - \sum_{i \in I} p_i \ln (p_i) \le - \sum_{i \in I} p_i \ln (q_i)\]Equality holds if \(q_i / p_i = 1\) and \(\sum_{i \in I} q_i = 1, q_i = p_i\)

Q: Corollary. \(H(p_1, \dots , p_n) \le \log n\) with equality iff \(p_1 = \dots = p_n = 1/n\)
A: Take \(q_1 = \dots = q_n = 1/n\) in Gibbs' inequality.

Q: Definition. A Bernoulli or memoryless source is [...] The expected word length of a code \(f\) with word lengths \(s_1 , \dots , s_m\) is \([...]\).
A: a sequence of i.i.d random variables for each \(\mu \in \Sigma_1\) \(P(X_i = \mu)\) is independent of i and of all past and future symbols emitted.; E(S) = \sum_{i=1}^m p_i s_i

Q: Definition. A code \(f: \Sigma_1 \to \Sigma_2^*\) is optimal if [...]
A: it has the shortest possible expected word lengths among decipherable codes.

Q: Theorem. Shannon's Noiseless Coding Theorem. The minimum expected word length of a decipherable code \(f: \Sigma_1 \to \Sigma_2^*\) satisfies \[\frac{H(X)}{\log(a)} \le E(S) \le \frac{H(X)}{\log(a)} + 1\]
A: The lower bound is given by combining Gibbs' and Kraft inequalities.
Taking \(q_i = a^{-s_i}/C\) where \(C = \sum_{i=1}^m a^{-s_i} \le 1\)
So \(\sum q_i = 1\)\[H(X) = - \sum_{i=1}^m p_i \log p_i \le -\sum_{i=1}^m p_i \log q_i = \sum_{i=1}^m(p_i s_i) \log a + \log C\]which gives the lower bound by dividing, and equality iff \(p_i = a^{-s_i} \) for some integers \(s_i\).
For the upper bound let \(s_i = \lceil -\log_a p_i \rceil\). We have \(-\log_a p_i \le s_i -\log_a p_i +1 \implies a^{-s_i} \le p_i \implies \sum_{i=1}^m a^{-s_i} = 1\)
So by Theorem 1.1 there exists a prefix free code with word lengths \(s_1 , \dots , s_m\).
Also \[E(S) = \sum_{i=1}^m p_i s_i < \sum_{i=1}^m p_i (-\log_a p _i + 1) = \frac{H(X)}{\log a} + 1\]

Q: What is Shannon-Fano coding?
A: Set \(s_i = \lceil -\log_a p_i \rceil\) and construct a prefix-free code with word lengths \(s_1 , \dots , s_m\) by taking the \(s_i\) in increasing order ensuring that previous codewords are not prefixes.
The Kraft inequality ensures there is enough room.

Q: What is Huffman Coding?
A: For simplicity take a = 2. WLOG \(p_1 \ge p_2 \ge \dots \ge p_m\)
Huffman coding is defined inductively
If \(m=2\), assign codewords 0 and 1
If \(m > 2\) find a Hufmann coding in the case of probabilities \(\mu_1 , \dots , \nu\) with \(p_1 , p_2, \dots , p_{m-1}+p_m\).
Append 0 (resp 1) to the codeword for \(\nu\) to give a codeword for \(\mu_{m-1}\)(resp \(\mu_m\))

Q: Lemma. Suppose \(\mu_1 , \dots , \mu_m \in \Sigma_1\) are emitted with probabilities \(p_1 , \dots , p_m\). Let f be an optimal prefix-free code with word lengths \(s_1 , \dots , s_m\)
(i)If \(p_i > p_j\) then \(s_i \le s_j\)
(ii) \(\exists \) 2 codewords of maximal length which are equal up to the last digit
A: (i)If not swap ith and jth codewords decreasing expected length
(ii)If not, then either there is only one codeword of maximal length or any two codewords of maximal length differ before the last digit. In either case, delete the last digit of each codeword of maximal length. This maintains prefix-free, contradicting optimality

Q: Theorem. Huffman codings are optimal. \((a = 2)\)
A: We show by induction on m that any Huffman code of size m is optimal.
\(m=2\): codewords 0 and 1 so optimal
\(m>2\): Source \(X_m\) emits \(\mu_1, \dots , \mu_m\) w probabilities \(p_1 \ge \dots \ge p_m\)
Source \(X_{m-1}\) emits \(\mu_1 , \dots , \mu_{m-2}, \nu\) with probabilities \(p_1 , \dots , p_{m-2}, p_{m-1} + p_m\)
We construct Huffman coding for \(f_{m-1}\) for \(X_{m-1}\) and extend to a Huffman coding \(f_m\) for \(X_m\). Then, the expected codeword length satisfies \[E(S_m) = E(S_{m-1}) + p_{m-1} + p_m\]Let \(f_m'\) be an optimal code for \(X_m\), where \(f_m'\) is prefix-free
By the Lemma, by shuffling codewords we may assume the last two codewords of \(f_m'\) are of maximal length and differ only in the last digit, say \(y0\) and \(y1\), for some string y.
We define a code \(f_{m-1}'\) for \(X_{m-1}\) with \[f_{m-1}'(\mu_i) = f_m'(\mu_i) \; \; 1 \le i \le m-2\]\[f_{m-1}'(\nu) = y\]Then \(f_{m-1}'\) is a prefix-free code and the expected word length satisfies \[E(S_m') = E(S_{m-1}') + p_{m-1} + p_m\]So using induction hypothesis we have \[f_{m-1} \text{ optimal} \implies E(S_{m-1}) \le E(S_{m-1}') \implies E(S_m) \le E(S_m ') \implies f_m \text{ optimal}\]

Q: Definition. A source \(X_1, X_2 ,\dots\) satisfies the Asymptotic Equipartition Property(AEP) with constant \(H \ge 0\) if[...]
A: \[\forall \epsilon > 0 \; \exists n_0(\epsilon) \; s.t. \; \forall n \ge n_0(\epsilon) \; \; \exists \text{a 'typical set' } T_n \subset \Sigma^n\]s.t. \[(i) P((X_1 , \dots , X_n) \in T_n) > 1-\epsilon\]\[(ii)2^{-n(H+\epsilon)} \le p(x_1 , \dots , x_n) \le 2^{-n(H-\epsilon)} \;\; \forall (x_1 , \dots , x_n) \in T_n\]
Back Extra: Idea is to encode high probability typical sequences carefully and encode the low probability atypical sequences arbitrarily.

Q: Definition. A source \(X_1 , X_2 , \dots\) is reliably encodeable at rate r if [...]
A: \(\exists A_n \subseteq \Sigma^n\) for each n s.t. \[\frac{\log |A_n|}{n} \to r \; \; \;\text{ as } n \to \infty\]\[P((X_1, \dots , X_n) \in A_n) \to 1 \; \; \; \text{ as }n \to \infty\]
Back Extra: So in principle you can encode ar rate almost r, with negligible error, for long enough sequences.

Q: Definition. The information rate H of a source is [...]
A: the infimum of all rates at which it is reliably encodeable.

Q: Definition. A source \(X_1 , X_2, \dots\) satisfies AEP if for some \(H \ge 0\) \[[...]\]
A: \frac{-1}{n} \log p(X_1, \dots , X_n) \to^p H \text{ as } n\to \infty

Q: Definition. An [n,m] binary code is [...] The information rate of C is[...]
A: a subset \(C \subseteq \{0.1\}^n\) of size m.; \(\rho(c) = \frac{\log m}{n}\).
Back Extra: We say C has length n. The elements of C are called codewords.

Q: Definition. The error rate depends on the decoding rules. We consider 3 possible rules[...]
A: 1. The ideal observer decoding rule decodes \(x \in \{0,1\}^n\) as the codeword \(c \in C\) maximising \(\mathbb{P}(c \text{ sent} | x \text{ received})\).
2. The maximum likelihood decoding rule decodes \(x \in \{0,1\}^n\) as \(c \in C\) maximising \(P(x \text{ received} | c \text{ sent})\)
3. The minimum distance decoding rules decodes \(x \in \{0,1\}^n \) as \(c \in C\) minimising \(\#\{1 \le i \le n : X_i \neq C_i\}\)

Q: Lemma. If all messages are equally likely then ideal observer and maximum likelihood decoding rules agree.
A: By Bayes we have \[P(\text{c sent | x received}) = \frac{P(\text{c sent, x received})}{P(\text{x received})} = \frac{P(\text{c sent})}{P(\text{x received})} \cdot P(\text{x received | c sent}) \]We suppose \(P(\text{c sent})\) is independent of c so for fixed x maximising \(P(\text{c sent | x received})\) is the same as maximising \(P(\text{x received | c sent})\)

Q: Lemma. If \(p<1/2\) then maximum likelihood and minimum distance agree.
A: Suppose \(d(x,c) = r\)
\(P(\text{x received | c sent}) = p^r(1-p)^{n-r} = (1-p)^n (\frac{p}{1-p})^r\)
Since \(p < 1/2, p/(1-p) < 1\). So choosing c to maximise likelihood is same as minimising r.

Q: Definition. C is d-error detecting if c[...] C is e-error correcting if [...]
A: hanging at most d letters of a codeword cannot give you another codeword.; knowing that the string received has at most e errors is sufficient to determine which codeword has been sent.

Q: Definition. Let \(x \in \mathbb{F}_2^n\) and \(r \ge 0\). The closed Hamming ball with centre x and radius r is \[[...]\]
A: B(x,r) = \{y \in \mathbb{F}_2^n : d(x,y) \le r\}
Back Extra: The volume is \[V(n,r) = |B(x,r)| = \sum_{i=0}^r {n \choose i}\]

Q: Lemma. Hamming's Bound. If \(C \subseteq \mathbb{F}_2^n\) is e-error correcting then \[|C| \le \frac{2^n}{V(n,e)}\]
A: Since C is e-error correcting the Hamming balls \(B(c,e)\) are disjoint for \(c \in C\) \[\implies \sum_{c \in C} |B(c,e)| \le |F_2^n|\]\[\implies |C| \le \frac{2^n}{V(n,e)}\]

Q: Definition. An [n,m]-code which can correct e-errors is called perfect if \[[...]\]
A: m = \frac{2^n}{V(n,e)}

Q: Definition. \[A(n,d) = [...]\]
A: \max \{m : \exists [n,m,d] - code\}
Back Extra: Size of largest code with parameters n and d.
\(A(n,1) = 2^n\)
\(A(n,n) = 2\)

Q: Proposition. \[\frac{2^n}{V(n,d-1)} \le A(n,d) \le \frac{2^n}{V(n , \lfloor \frac{d-1}{2} \rfloor)}\]Upper bound is Hamming's, lower is GSV
A: Let C be a code of length n and min distance d of largest possible size. Then \(\not \exists x \in F_2^n\) s.t. \(d(x,c) \ge d \quad \forall c\in C\) otherwise we would replace C with \(C \cup \{x\}\)
\[\implies F_2^n \subseteq \bigcup_{c \in C} B(c,d-1)\]\[\implies 2^n \le |C| V(n,d-1)\]\[\implies \frac{2^n}{V(n,d-1)} \le |C|\]

Q: Proposition. Let \(0 < \delta < 1/2\). Then
\[(i) \quad \log V(n , \lfloor n \delta \rfloor) \le nH(\delta)\]\[(ii)\quad \frac{\log A(n, \lfloor n\delta \rfloor)}{n} \ge 1 - H(\delta)\]
A: \((i ) \implies (ii)\)
\[GSV \text{ bound} \implies A(n,\lfloor n\delta \rfloor) \ge \frac{2^n}{V(n, \lfloor n\delta \rfloor -1)} \ge \frac{2^n}{V(n, \lfloor n\delta \rfloor)}\]\[\implies \log A(n, \lfloor n\delta \rfloor)\ge n - \log V(n, \lfloor n\delta \rfloor) \ge n - nH(\delta)\]\[\implies \frac{\log A(n, \lfloor n\delta \rfloor)}{n} \ge 1 - H(\delta)\]\((i)\) \[1 = (\delta + (1-\delta))^n = \sum_{i=0}^n {n \choose i} \delta^i(1-\delta)^{n-i}\ge \sum_{i=0}^{\lfloor nd \rfloor} {n \choose i} \delta^i (1-\delta)^{n-i}\]\[\ge (1-\delta)^n \sum_{i = 0}^{\lfloor n\delta \rfloor} {n \choose i} (\frac{\delta}{1- \delta})^i \ge (1-\delta)^n \sum_{i=0}^{\lfloor n\delta \rfloor} {n \choose i} (\frac{\delta}{1-\delta})^{n \delta}\]\[1 \ge \delta^{n\delta}(1-\delta)^{n(1-\delta)} V(n, n \delta)\]\[\implies 0 \ge n(\delta \log \delta + (1-\delta)\log (1- \delta)) + \log V(n ,n \delta)\]\[\implies \log V(n,\delta) \le nH(\delta)\]

Q: Definition. A channel can transmit reliably at rate R if [...]
A: \(\exists \) a sequence of codes \(C_1 , C_2 , \dots\) where \(C_n\) is a code of length n and size \(\lfloor 2^{nR} \rfloor\) such that \(\hat{e}(C_n) \to 0\) as \(n \to \infty\)
Back Extra: The (operational) channel capacity is the supremum over all reliable transmission rates.

Q: Lemma. The Hamming distance is a metric on \(F_2^n\).
A: Clearly \(d(x,y) \ge0 \) and equal 0 iff x = y.
Also symmetric.
Need to check triangle inequality. \[\{1 \le i \le n : x_i \neq z_i\} \subseteq \{1 \le i \le n: x_i \neq y_i\} \cup \{1 \le i \le n: y_i \neq z_i\}\]which gives us the inequality.

Q: Definition. The minimum distance of a code C is [...] An \([n,m]\) code with minimum distance d is sometimes called an \([n,m,d]\) code.
A: the smallest Hamming distance between distinct codewords.

Q: Lemma. Let C be a code with minimum distance d. \[(i)\quad \text{C is (d-1)-error detecting, but cannot detect d errors}\]\[(ii) \quad \text{C is} \lfloor (d-1)/2 \rfloor\text{- error correcting, but cannot correct all sets of} \lfloor (d-1)/2\rfloor + 1 \text{ errors}.\]
A: (i) If \(x \in F_2^n\) and \(c \in C\) with \(1 \le d(x,c) \le d-1\), then \(x \neq C\) so errors detected. Suppose \(c_1 , c_2 \in C\) with \(d(c_1 , c_2 ) = d\). Then \(c_1\) can be corrupted to \(c_2\) with just d errors, this set of errors will not be detected.
(ii)Let \(e = \lfloor (d-1)/2 \rfloor\), so \(e \le (d-1)/2 < e+1\), so \(2e < d \le 2(e+1)\). Let \(x \in F_2^n\). If \(\exists c_1 \in C\) with \(d(x, c_1 ) \le e\), we want to show \(d(x,c_2) > e \quad \forall c_2 \in C, c_2 \neq c_1\)
By triangle inequality \(d(x,c_2 ) \ge d(c_1, c_2) - d(x,c_1) \ge d-e > e\)
So C is e-error correcting.
Let \(c_1, c_2 \in C \) with \(d(e_1 , e_2) = d\). Let \(x \in F_2^n\) differ from \(c_1\) in precisely \(e+1\) places where \(c_1 \)and \(c_2\) differ. Then \(d(x, c_1) = e+1\), \(d(x, c_2) = d - (e+1) \le e+1\). So C cannot correct \(e+1\) errors.

Q: Lemma. Let \(\epsilon > 0\). A BSC with error probability p is used to send n digits. Then \[P(\text{BSC makes } \ge n(p+\epsilon) \text{ errors}) \to 0 \text{ as } n\to \infty\]
A: Let \[\mu_i = \begin{cases}1 & \text{if ith digit is mistransmitted} \\ 0 & \text{otherwise}\end{cases}\]\(\mu_1, \mu_2, \dots\) are i.i.d random variables. \(E(\mu_i) = p\). \[P(\text{BSC makes } \ge n(p+\epsilon) \text{ errors}) = P(\sum_{i=1}^n \mu_i \ge n(p+ \epsilon)) \le P(|\frac{1}{n} \sum_{i=1}^n \mu_i - p| \ge \epsilon) \to 0 \quad WLLN\]

Q: Proposition. The capacity of a BSC w/ error probability <1/4 is \(\neq 0\).
A: We prove reliable encoding at rate \(R = 1-H(\delta) > 0\) where \(2p < \delta < 1/2\)
Let \(C_n\) be the largest code of length n and minimum distsance \(\lfloor n\delta \rfloor\)
Therefore \[|C_n| = A(n, \lfloor n\delta \rfloor) \ge 2^{n(1- H(\delta))} = 2^{nR}\]Replacing \(C_n\) by a subcode gives \(|C_n| = \lfloor 2^{nR} \rfloor\) and still minimum distance \(\ge \lfloor n\delta \rfloor\)
Using minimum distance decoding \[\hat{e}(C_n) \le P(\text{BSC makes } \ge \lfloor \frac{\lfloor n\delta \rfloor - 1}{2} \rfloor + 1 \text{ errors}) \le P(\text{BSC makes } \ge \frac{n\delta - 1}{2} \text{ errors})\]Pick \(\epsilon > 0 \) s.t. \(p + \epsilon < \delta/2\)
Then \((n \delta - 1)/2 = n(\delta/2 - 1/2n) > n(p + \epsilon)\) for n sufficiently large
Therefore \(\hat{e}(C_n) \le P(\text{BSC makes }\ge n(p+\epsilon) \text{ errors}) \to0\) as \(n \to \infty\)

Q: Definition. The joint entropy of X and Y is \[H(X,Y) = [...]\]The conditional entropy of X given Y is \[H(X|Y) =[...]\]
A: - \sum_{x \in \Sigma_1} \sum_{y \in \Sigma_2} P(X = x, Y = y) \log (P(X = x, Y=y)); \sum_{y \in \Sigma_2} P(Y = y)H(X | Y = y)

Q: Lemma. \[H(X,Y) \le H(X) + H(Y) \]with equality iff X and Y are independent
A: \(\Sigma_1 = \{x_1 , \dots , x_m\}, \Sigma_2 = \{y_1 , \dots , y_n\}\)
\(p_{ij} = P(X = x_i , Y = y_j), p_i = P(X = x_i), q_j = p(Y = y_j)\)
Apply Gibbs' inequality with distributions \(p_{ij}\) and \(p_i q_j\)\[- \sum p_{ij} \log (p_{ij}) \le - \sum p_{ij} \log(p_i q_j) = -\sum_i (\sum_j p_{ij}) \log p_i - \sum_j (\sum_i p_{ij}) \log q_j = -\sum_i p_i \log p_i - \sum q_j \log q_j\]i.e. \(H(X,Y) \le H(X) + H(Y)\)
Equality iff \(p_{ij} = p_i q_j \forall i,j\) iff \(X,Y\) independent.

Q: Lemma. \[H(X,Y) = H(X|Y) + H(Y)\]
A: \[H(X|Y) = -\sum_{y \in \Sigma_2} \sum_{x \in \Sigma_1} P(X = x| Y = y) P(Y = y)\log P(X = x| Y=y)\]\[= - \sum_{y \in \Sigma_2} \sum_{x \in \Sigma_1} P(X= x , Y = y) \log \frac{P(X = x, Y= y)}{P(Y = y)}\]
\[ = -\sum_{y \in \Sigma_2} \sum_{x \in \Sigma_1} P(X = x, Y = y) \log P(X = x, Y=y) + \sum_y (\sum_x P(X = x,Y=y) \log P(Y = y)) = H(X,Y) - H(Y)\]

Q: Corollary. \(H(X|Y) \le H(X)\) with equality iff X,Y are independent
A: Since \(H(X | Y) = H(X,Y) - H(Y)\) this is equivalent to \(H(X,Y) \le H(X) + H(Y)\) with equality iff X and Y independent.

Q: Lemma. \[H(X|Y) \le H(X | Y,Z) + H(Z)\]
A: We expand \(H(X,Y,Z)\) in two different ways.
(i)\(H(X,Y,Z) = H(Z | X,Y) + H(X | Y) + H(Y)\)
(ii) \(H(X,Y,Z) = H(X | Y,Z) + H(Z|Y) + H(Y)\)
Since \(H(Z|X,Y) \ge 0 \implies H(X|Y) \le H(X | Y,Z) + H(Z,Y) \le H(X | Y,Z) + H(Z)\)

Q: Lemma. Fano's Inequality. X,Y random variables taking values in alphabet \(\Sigma, |\Sigma| = m\). Let \( p = P(X \neq Y)\). Then \[H(X|Y) \le H(p) + p\log (m-1)\]
A: Let \(Z = \begin{cases} 1 & \text{if }X \neq Y \\ 0 & \text{if } X = Y \end{cases}\)
\[H(X|Y) \le H(X | Y,Z) + H(Z)\]Now \(H(X| Y=y, Z = 0) = 0\), \(H(Z|Y=y, Z = 1) \le \log m-1\)
So \(H(X|Y,Z) = \sum_{y,z} P(Y=y, Z=z)H(X| Y=y, Z=z) \le \sum_y P(Y=y, Z=1)\log (m-1)\)
So putting these together gives the result

Q: Definition. X,Y random variables. The mutual information is \[[...]\]
A: I(X ; Y) = H(X) - H(X|Y)
Back Extra: The amount of information about X conveyed by Y. equal to \[H(X) + H(Y) - H(X,Y) \ge 0\]so its symmetric.

Q: Definition. Consider a DMC. Let X take values in \(\Sigma_1, |\Sigma_1| = m\), with probabilities \(p_1 , \dots ,p_m\). Let Y be a r.v. output when channel is given input X. The information channel capacity is \[[...]\]
A: \max_X I(X ; Y)

Q: Lemma. The nth extension of a DMC with info capacity C has info capacity nC.
A: We take r.v. input \(X_1 \dots X_n = X\) producing r.v. output \(Y_1 \dots Y_n = Y\)
Now \(H(Y | X) = \sum_{x \in \Sigma_1^n} P(X = x)H(Y | X = x)\)
Since channle is memoryless \[H(Y | X = x) = \sum_i H(Y_i | X = x) = \sum_i H(Y_i | X_i)\]So \(H(Y|X) = \sum_x P(X= x)\sum_i H(Y_i | X_i = x_i) = \sum_i \sum_u H(Y_i | X_i = u)P(X_i = u) = \sum_{i=1}^n H(Y_i | X_i)\)
Now \(H(Y) \le H(Y_1) + \dots + H(Y_n)\)
Thus \(I(X ; Y) = H(Y) - H(Y|X) \le \sum_i H(Y_i - H(Y_i | X_i)) = \sum_{i=1}^n I(X_i ; Y_i) \le nC\)
We get equality if \(Y_1 ,\dots , Y_n\) are independent. This can be achieved by taking \(X_1 , \dots , X_n\) independent and choosing the probability distribution s.t. \(I(X_i ; Y_i) = C\).

Q: Proposition. For a DMC \[\text{operational capacity} \le \text{information capacity}\]
A: Let C be the information capacity. Suppose we can transmit reliably at rate \(R > C\), ie, there is a sequence of codes \((C_n)_{n \ge 1}\) with \(C_n\) of length n and size \(\lfloor 2^{nR} \rfloor\) s.t. \(\hat{e}(C_n) \to 0\) as \(n \to \infty\)
Max error probability \(\hat{e}(C_n) = \max_{c \in C_n} P(\text{error | c sent})\)
Error probability \(e(C_n) = \frac{1}{|C_n|} \sum_{c \in C_n} P(\text{error | c sent})\)
Clearly \(e(C_n) \le \hat{e}(C_n)\)
Take r.v. input X equidistributed over \(C_n\). Let Y be the r.v. output when X is transmitted and decoded.
So \(e(C_n) = P(X \neq Y) = p\) say
\[H(X) = \log |C_n| \ge nR - 1 \quad \text{for n suff. large}\]\[H(X|Y) \le H(p) + p \log(|C_n| - 1) \quad \text{Fano's inequality}\]\[I(X,Y) = H(X) - H(X | Y) \implies nC \ge nR -1 -(1+pnR)\]
\[npR \ge n(R-C) - 2\]\[\implies p \ge \frac{n(R-C) -2}{nR}\]which doesn't tend to 0. Contradiction.

Q: Proposition. Consider a BSC, error probability p. Let \(R < 1 - H(p)\). Then \(\exists\) a sequence of codes \((C_n)_{n \ge 1}\) of length n and size \(\lfloor 2^{nR} \rfloor\) s.t. \(e(C_n) \to 0\) as \(n \to \infty\)
A: Idea- construct codes by picking codewords at random
WLOG \(p < 1/2\), so \(\exists \epsilon > 0\) s.t. \(R < 1 - H(p + \epsilon)\). We use minimum distance decoding (in case of tie make arbitrary choice)
Let \(m = \lfloor 2^{nR} \rfloor\). We pick an \([n,m]-code\) C at random (i.e. each with probability \(\frac{1}{{2^n \choose m}}\)), say \(C = \{c_1 , \dots , c_m\}\)
Choose \(1 \le i \le m\) at random (i.e. each with probability \(\frac{1}{m}\))We send \(c_i\) through the channel and get output Y.
It will suffice to show \[P(Y \text{ is not decoded as }c_i) \to 0 \text{ as } n \to \infty\]Let \(r = \lfloor n (p + \epsilon) \rfloor\)
\(P(Y\text{ is not decoded as }c_i) \le P(c_i \not \in B(Y,r)) + P(\{c_i\} \subset B(Y,r) \cap C)\)
(i)\(P(d(c_i, Y) > r) = P(\text{BSC makes >r errors}) = P(\text{BSC makes }n(p+ \epsilon) \text{ errors}) \to 0\)
(ii)If \(j \neq i\), \(P(c_j \in B(Y,r) | c_i \in B(Y,r)) = \frac{V(n,r) - 1}{2^n - 1} \le \frac{V(n,r)}{2^n}\)
So \(P(\{c_i\} \subset B(Y,r) \cap C) \le \frac{(m-1)V(n,r)}{2^n} \le 2^{nR}2^{nH(p+\epsilon)}2^{-n} = 2^{n(R-(1-H(p+\epsilon)))} \to 0\) as \(n \to \infty\) since \(R < 1 - H(p + \epsilon)\)

Q: Proposition. Consider a BSC with error prob p. Let \(R < 1 - H(p)\). Then \(\exists\) a sequence of codes \((C_n)_{n \ge 1}\) with \(C_n\) of length n, size \(\lfloor 2^{nR} \rfloor\) and \(\hat{e}(C_n) \to 0\) as \(n \to \infty\)
A: Pick \(R'\) such that \(R < R' < 1-H(p)\). By prop 2.17 we construct a sequence of codes \((C_n')_{n \ge 1}\) with \(C_n'\) of length n, size \(\lfloor 2^{nR'} \rfloor\) and \(e(c_n) \to 0\) as \(n \to \infty\)
Throwing out the worst half of the codewords in \(C_n'\), gives a code \(C_n\) with \(\hat{e}(C_n) \le 2e(C_n')\) so \(\hat{e}(c_n) \to 0\) as \(n \to \infty\)
Note \(C_n\) has length n and size \(\lfloor 2^{nR' - 1} \rfloor\)
But \(2^{nR' - 1} = 2^{n(R' - 1/n)} > 2^{nR}\) for n sufficiently large
We can replace \(C_n\) by a subcode of size \(\lfloor 2^{nR} \rfloor\) and still get \(\hat{e}(C_n) \to 0\) as \(n \to \infty\)

Q: Definition. A code \(C \in F_2^n\) is linear if
[...]
The rank of a linear code C is [...]
A: (i) \(0 \in C\)
(ii) \(x,y \in C \implies x+y \in C\); its dimension as an \(F_2\)-vector space.
Back Extra: A code of length n and rank k is called an (n,k)-code

Q: Lemma. Let \(P \subseteq F_2^n\) be a subset. Then \[C = \{x \in F_2^n : p \cdot x = 0 \quad \forall p \in P\}\]is a linear code
A: (i)\(0 \in C\), since \( p \cdot 0 = 0 \quad \forall p \in P\)
(ii) If \(x,y \in C\), then \(p \cdot(x+y) = p\cdot x + p \cdot y = 0 \implies x+y \in C\)
P is called a set of parity checks or a parity check code

Q: Definition. Let \(C \subset F_2^n\) be a linear code. The dual code is\[[...]\]
A: C^{\perp} = \{x \in F_2^n : x \cdot y = 0 \quad \forall y \in C\}

Q: Lemma. \(\dim C + \dim C^{\perp} = n\)
Warning: can have \(C \cap C^{\perp} \neq \{0\}\)
A: \(V = F_2^n\), \(V^* = \{\text{linear maps} : V \to F_2\}\)
Consider \(\phi : V \to V^*, x \mapsto \theta_x\) where \(\theta_x : y \mapsto x\cdot y\)
\(\phi\) a linear maps
Suppose \(x \in \ker \phi\), then \(x \cdot y = 0 \quad \forall y \in V\)
Taking \(y = e_i = (0,0,\dots,0,1,0,\dots,0)\) gives \(x_i = 0\)
So \(\ker \phi = \{0\}\)
Since \(\dim V = \dim V^*\) it follows that \(\phi\) is an isomorphism
Then \(\phi(C^{\perp}) = \{\theta \in V^* : \theta(x) = 0 \quad \forall x \in C\} = \text{annihilator of C} = C^0\)
\[\implies \dim C + \dim (\phi(C^{\perp})) = n\]\[\implies \dim C + \dim C^{\perp} = n\]

Q: Corollary. \((C^{\perp})^{\perp} = C\) for any linear code C. In particular, any linear code is a parity check code
A: Let \(x \in C\). Then \(x \cdot y = 0 \quad \forall y \in C^{\perp} \implies x \in (C^{\perp})^{\perp} \) ie. \(C \le (C^{\perp})^{\perp}\)
Also \(\dim (C^{\perp})^{\perp} = \dim C \implies C = (C^{\perp})^{\perp}\)

Q: Definition. Let C be an (n,k)-linear code
(i)A generator matrix for C is [...]
(ii) A parity check matrix for C is [...] It is an (n-k) x n matrix.
A: a k x n matrix whose rows are a basis for C; a generator matrix for \(C^{\perp}\).

Q: Lemma. Every (n,k)-linear code is equivalent to a linear code with generator matrix of form \((I_k | B )\)
A: We can perform row operations
- swap two rows
- add one row to another
By Gaussian elimination we get G, the generator maatrix, in row echelon form
eg \[G = \left ( \begin{matrix}1 & * & * & \dots \\ 0 & 1 & * & \dots \\ 0 & 0 & 0 & 1 & \dots \\ \dots\end{matrix} \right )\]ie. \(\exists l (1) < l(2 ) < \dots < l(k)\) such that \(G_{ij} = 0 \) if \(j < l(i) \) and \(1 \) if \(j = l(i)\)
Permuting the columns of G gives an equivalent code, wlog \(l(i) = i\)
More row operations put G in the form required.

Q: Lemma. An (n,k)-linear code with generator matrix \(G = (I_k | B)\) has parity check matrix \(H = (-B^T | I_{n-k})\)
A: Since \(GH^T = (I_k | B)(\frac{-B}{I_{n-k}}) = -B + B = 0\)
So rows of H generate a subcode of \(C^{\perp}\)
But \(\dim(C^{\perp}) = n-k = rk(H)\) since H has \(I_{n-k}\) as a submatrix
Therefore the rows of H are a basis for \(C^{\perp} \) as required.

Q: Lemma. The minimum distance of a linear code C is the minimum weight of a non-zero codeword
A: Let \(x,y \in C\). \(d(x,y)= d(x-y,0) = d(x+y,0) = w(x+y)\)
Note \(x,y \) distinct \(\iff x + y \neq 0\)
So \(d(C) = \min_{x,y \in C} d(x,y) = \min_{0 \neq z \in C} w(z)\)

Q: Definition. The weight \(w(C)\) of a linear code C is [...]
A: the minimum weight of a non-zero codeword.
Back Extra: Same as minimum distance by previous proof

Q: Lemma. Let C be a linear code with parity check matrix H. Then \(w(C)= d\) iff
(i) any (d-1) columns are linear independent
(ii) some d columns are linearly dependent
A: Suppose C has length n. Then \(C = \{x \in F_2^n : Hx = 0\}\). If H has columns \(v_1 , \dots , v_n\) then \((x_1 , \dots , x_n) \in C \iff \sum x_i v_i = 0 \)
ie. codewords 'are' dependence relations between columns of H.

Q: Lemma. The Hamming \((n,n-d)\) linear code C has minimum distance \(d(C) = 3\) and is a perfect 1-error correcting code
A: Any two columns of H, the parity check matrix of C, are linearly independent, but exists 3 columns that are linearly dependent. \(d(C) = 3\) by previous lemma.
\(\lfloor (3-1)/2 \rfloor = 1\) error correcting.
\[\frac{2^n}{V(n,e)} = \frac{2^n}{1+2^d - 1} = 2^{n-d} = |C|\]So it is perfect too.

Q: Definition. Let \(C_1, C_2\) be linear codes of length n with \(C_2 \subset C_1\), ie, \(C_2\) is a subcode of \(C_1\). The bar product \[[...]\]
A: C_1 | C_2 = \{(x|x+y), x \in C_1, y \in C_2\}
Back Extra: It is a linear code of length 2n.

Q: Lemma. \(C_1, C_2\) as above
(i) \(rk(C_1 | C_2) = rk(C_1) + rk(C_2)\)
(ii)\(w(C_1 | C_2) = \min \{2w(C_1), w(C_2)\}\)
A: (i)Let \(x_1, \dots, x_k\) be a bsis for \(C_1\). Let \(y_1 , \dots , y_l\) basis for \(C_2\)
Then \(\{(x_i | x_i) : 1 \le i \le k\} \cup \{(0 | y_j) : 1 \le j \le l\}\) is a bsis for \(C_1 | C_2\), hence \(rk(C_1 | C_2) = rk(C_1) + rk(C_2)\)
(ii) Let \(x \in C_1, y \in C_2\), not both zero
if \(y \neq 0, w(x | x+y) = w(x) + w(x+y)\ge w(y) \ge w(C_2)\)
if \(y = 0, x \neq 0 : w(x |x) =2w(x) \ge 2w(C_1)\)
So the weight is bigger than the min of those two.
But we can achieve both of them so \(w(C_1 | C_2) = \min \{2w(C_1), w(C_2)\}\)

Q: Definition. Let \(0 \le r \le d\). Reed-Muller code RM(d,r) of order r and length \(n = 2^d\) is [...]
A: the vector subspace of \(F_2^n\) spanned by \(v_0 = (1,1,\dots , 1)\) and wedge products of at most r of the \(v_i\) where \(v_i = 1_{H_i} , H_i = \{p \in X : ith \text{ coordinate of p is zero}\}\)

Q: Theorem.
(i)The vectors \(v_{i_1} \wedge \dots \wedge v_{i_s}\) for \(1 \le i_1 < \dots <i_s \le d\) and \(0 \le s \le d\) are a basis for \(F_2^n\)
(ii) \(RM(d,r)\) has rank \(\sum_{s=0}^r {d \choose s}\)
(iii)\(RM(d,r) = RM(d-1,r) | RM(d-1, r-1)\)
(iv) \(RM(d,r)\) has weight \(2^{d-r}\)
A: (i) We have a set of \(\sum_{s=0}^d {d \choose s} = (1+1)^d = 2^d = n\) vectors
So it suffices to show they span \(F_2^n\), equivalently \(RM(d,d) = F_2^n\)
Let \(p \in X\). Let \(y_i = \begin{cases} v_i & \text{if ith coordinate of p equal to 0} \\ v_i + v_0 & \text{if ith coordinate of p equal to 1}\end{cases}\)
Then \(\mathbb{1}_{p} = y_1 \wedge y_2 \wedge \dots \wedge y_d\)
Expanding, using distributive law, gives that \(\mathbb{1}_{\{p\}} \in RM(d,d) \)
But the \(1_{\{p\}}\) for \(p \in X\) span \(F_2^n\) therefore \(RM(d,d) = F_2^n\)
(ii) By definition \(RM(d,r)\) is spanned by vectors \(v_{i_1} \wedge \dots \wedge v_{i_s}\) with \(1 \le i_1 < \dots < i_s \le d\) and \(0 \le s \le r\). By (i) these vectors are linearly independent so a basis. There are \(\sum_{s=0}^r {d \choose s}\) such vectors
(iii) We order \(X = F_2^d\) such that \(v_d = (0,\dots , 0 | 1 \dots 1)\) with \(2^{d-1} \) 0s and \(2^{d-1}\) 1s and \(v_i = (v_i' | v_i')\) for \(1 \le i \le d-1\)
Let \(z \in RM(d,r)\). It is a sum of wedge products of \(v_0 , \dots, v_d\)
\(\implies z = x + (y \wedge v_d)\) where x and y are sums of wedge products of \(v_0 , \dots , v_{d-1}\)
We have \(x = (x' | x')\) some \(x' \in RM(d-1,r)\), \(y = (y' | y') \) some \(y' \in RM(d-1,r-1)\)
So, \(z = (x' | x') + (y' | y') \wedge (0 \dots 0 | 1 \dots 1) = (x' | x' + y') \in RM(d-1,r) | RM(d-1,r-1)\)
(iv) RM(d,0) is the repetition code of length \(2^d\), has weight \(2^{d-0}\)
\(RM(d,d) = F_2^n\) by (i) it has weight \(1 = 2^{d-d}\)
If \(0 < r < d\) we use (iii) and induction on d.
By induction \(RM(d-1,r)\) has weight \(2^{d-1-r}\) and \(RM(d-1,r-1)\) has weight \(2^{d-r}\)
Since our weight is the min of twice the first and the second, we get \(RM(d,r)\) has weight \(2^{d-r}\)

Q: Lemma. Let I be an ideal in ring R and let \(q : R \to R/I\) be the quotient map. Then there is a bijection between the set of ideals \(J \subseteq R\) containing I and the set of ideals in \(R/I\)
A: Bijection is given by \(J \mapsto q(J) = J / I\) and the inverse \(K \mapsto q^{-1}(K) = \{r \in R : q(r) \in K\}\)

Q: Definition. An ideal \( I \unlhd R\) is [...] An ideal is principal if [...] A field is [...]
A: an additive subgroup, closed under external multiplication so if \(a \in I, r \in R\) then \(ra \in I\).; it is generated by one element.; a commutative ring with a multiplicative identity such that every nonzero element has a multiplicative inverse.
Back Extra: If all ideals are principal the ring is called a Principal Ideal Domain, PID

Q: Proposition. (i) Let q be a prime power. Then \(\exists \alpha \in F_q\) [...] \(\alpha\) is called a primitive element.
(ii) \(F_{pr}\) is a subfield of \(F_{ps}\) iff \([...]\)
(iii) Let \(f(x) \in F_q[x]\). Then \(\exists r \ge 1\) such that f(x) factors completely into linear factors
A: (not unique) such that \(F_q^* = F_q / \{0\} = \{1, \alpha , \dots , \alpha^{q-2}\}\) ie \(F_q^* \cong C_{q-1}\) under multiplication.; r | s

Q: Lemma. Let F be a field and \(f(x) = \sum_{i=0}^n a_i x^i \in F[x]\)
Define \(f'(x) = \sum_{i=1}^n ia_i x^{i-1} \in F[x]\)
Let \(a \in F.\) If \((x-a)^2 | f(x)\) then \(f(a) = f'(a) = 0\)
A: We have \(f(x) = (x-a)^2 g(x)\) so \(f'(x) = 2(x-a)g(x) + (x-a)^2 g(x)\) so the result follows.

Q: Definition. \(C \subset F_2^n\) is a cyclic code if [...]
A: it is linear and \[(a_0, \dots , a_{n-1}) \in C \implies (a_1 , a_2 , \dots , a_{n-1}, a_0) \in C\]
Back Extra: We identify \(F_2^n\) with \(\frac{F_2[x]}{(x^n - 1)}\) via \[\pi : (a_0, \dots , a_{n-1}) \mapsto a_0 + a_1 x + \dots + a_{n-1}x^{n-1} \mod{x^n - 1}\]

Q: Lemma. A code \(C \subset F_2^n\) is cyclic iff \(\mathcal{C} = \pi(C)\) satisfies
(i) \(0 \in \mathcal{C}\)
(ii) \(f,g \in \mathcal{C}\) then \(f + g \in \mathcal{C}\)
(iii)\(f \in \mathcal{C}, g \in F_2[x] \implies gf \in \mathcal{C}\)
A: (i) and (ii) by linearity of C
(iii) If \(f(x) = a_0 + a_1 x + \dots + a_{n-1}x^{n-1}\)
Then \(x f(x) = a_{n-1} + a_0 x + \dots + a_{n-2}x^{n-1} \mod{x^n - 1}\)
So C cyclic iff \(f(x) \in \mathcal{C} \implies xf(x) \in \mathcal{C}\) ie (iii) holds for \(g(x) = x\)
Repeating gives \(x^rf(x) \in \mathcal{C}\). Then use (ii) to get result.
So C is a cyclic code of length n iff \(\mathcal{C}\) is an ideal in \(F_2[x] / (x^n - 1)\)

Q: Definition. A generator polynomial \(g(x)\) for a cyclic code C is [...]
A: a polynomial \(g(x) | x^n - 1\) s.t. \[C = \{f(x)g(x) \mod x^n - 1 | f(x) \in F_2[x]\}\]

Q: Theorem. Every cyclic code has a generator polynomial
A: C is an ideal in \(F_2[x] / (x^n - 1)\)
So \(C = J / (x^n - 1)\) for some \((x^n - 1) \subset J \unlhd F_2[x]\)
But \(F_2[x] \) is a PID, so every ideal is principal
So \(J = (g(x))\) some \(g(x) \in F_2[x]\). Then \[(x^n-1) \subseteq (g(x)) \implies g(x) | x^n - 1\]Note generator polynomials are unique if we insist they are monic(automatic given we are working over \(F_2\))

Q: Corollary. There is a bijection between cyclic codes of length n and factors of \(x^n - 1\) in \(F_2[x]\)
A: True since every cyclic code has a unique generator polynomial

Q: Lemma. C cyclic code of length n with generator polynomial \(g(x) = a_0 + a_1 x + \dots + a_k x^k(a_k \neq 0)\)
Then \(g(x), xg(x), \dots , x^{n-k -1}g(x)\) is a basis for C.
A: LI: Suppose \(f(x)g(x) \equiv 0 \mod (x^n-1)\) for some \(f(x) \in F_2[x]\) with \(\deg(f) \le n-k-1\)
As \(\deg (fg) \le n-1 \implies f(x) g(x) = 0 \implies f(x) = 0\)
Spanning: Let \(p(x) \in F_2[x]\), representing an element of C.
WLOG \(\deg (p(x)) < n\). Then \(p(x) = f(x)g(x)\) for some \(f(x) \in F_2[x]\) with \(\deg (f) = \deg (p) - \deg (g) < n-k\)
\(\implies\)p(x) is in span of \(g(x), xg(x) , \dots , x^{n-k-1}g(x)\)

Q: Definition. The parity check polynomial \(h(X)\) is defined by \([...]\)
A: g(x)h(x) = x^n - 1
Back Extra: Rows of G are orthogonal to rows of H. ith row of G times j th row of H gives coefficient of \(x^{n-k + (j-1)} \) in \(g(x)h(x)\)

Q: Lemma. The parity check polynomial is the generator polynomial for [...]
A: the 'reverse' of \(C^{\perp}\) where we reverse all codewords.

Q: Definition. Let \(F_2 \subset K, A \subset \{x \in K : x^n = 1\}\). The cyclic code of length n defined by A is \[[...]\]
A: C = \{f(x) \mod x^n - 1 : f(\alpha) = 0 \quad \forall \alpha \in A\}
Back Extra: Note \(f(x) \equiv 0 \in C\)
If \(f,g \in C \quad (f+g)(\alpha) = f(\alpha) + g(\alpha) = 0\)
\(f \in C, f(\alpha) = 0 \implies \alpha f(\alpha) =0 \implies xf(x) \in C\) ie C is cyclic code

Q: Definition. Let \(F_2 \subset K, \) n odd and \(\alpha \in K\) primitive nth root of unity. The cyclic code with defining set \([...]\) is called a BCH-code with design distance \(\delta.\)
A: A = \{\alpha , \alpha^2 , \dots, \alpha^{\delta-1}\}
Back Extra: The minimal polynomial for \(\alpha\) over \(F_2\) is the polynomial of least degree satisfied by \(\alpha\)
The generator polynomial \(g(x)\) for BCH code C is \(lcm\{m_1(x) , \dots , m_{\delta - 1}(x)\}\) where \(m_i(x)\) is the minimal polynomial for \(\alpha \) over \(F_2\).

Q: Lemma. Vandermande determinant. \[\left | \begin{matrix} 1 & 1 & \dots & 1 \\ x_1 & x_2 & \dots & x_n \\ x_1^2 & x_2^2 & \dots & x_n^2 \\ \vdots & \vdots & & \vdots \\ x_1^{n-1} & x_2^{n-1} & \dots & x_n^{n-1}\end{matrix} \right | = [...]\]
A: \prod_{1\le j \le i \le n} (x_i - x_j)
Back Extra: Work in \(Z[x_1, \dots , x_n]\). Note  \(i = j\)  makes LHS = 0 therefore  \((x_i - x_j) | LHS \quad \forall i\neq j \implies RHS|LHS\)
But both polynomials have degree  \(n \choose 2\) and coefficient of  \( x_2 x_3^2 \dots x_n^{n-1}\) is 1 therefore  LHS = RHS.

Q: Theorem. The minimum distance of a BCH code is at least the design distance.
A: Consider the \((\delta - 1) \times n \) matrix \[H = \left ( \begin{matrix} 1 & \alpha & \alpha^2 & \dots & \alpha^{n-1} \\ 1 & \alpha^2 & \alpha^4 & \dots & \alpha^{2(n-1)} \\ \vdots & \vdots & \vdots & & \vdots \\1 & \alpha^{\delta - 1} & \alpha^{2(\delta - 1)} & \dots & \alpha^{(\delta - 1)(n-1)}\end{matrix} \right )\]Vandermende, pulling out factors \(\implies\)any \(\delta - 1\) columns of H are linearly independent
But a codeword in C is a dependence relation between the columns of H \(\implies w(C) \ge \delta\)

Q: Definition. The error-locator polynomial is [...]
A: \[\sigma(x) = \prod_{i \in \xi}(1-\alpha^ix)\]where \(r(x) = c(x) +e(x)\) and \(\xi = \{0\le i \le n-1 : e_i \neq0\}\)

Q: Theorem. \(\sigma(x)\) has constant term 1, and satisfies \[\sigma(x)\sum_{j=1}^{2t} r(\alpha^j)x^j \equiv w(x) \mod x^{2t+1}\]where \(w(x)\) is a polynomial of degree \(\le t\). Moreover \(\sigma(x)\) is the unique polynomial of least degree satisfying the above.
A: Let \(w(x) = -x\sigma'(x) = \sum_{i \in \mathcal{E}} \alpha^i x \prod_{j \in \mathcal{E}, j \neq i} (1-\alpha^j x)\)
So \(w(x)\) is a polynomial of degree equal to \(\deg \sigma\)
 We work in \(K[[x]]\) the ring of formal power series, ie elements of the form \(\sum_{i=0}^{\infty} \beta_i x^i, \beta_i \in K\)
Note, \[\frac{1}{1-\alpha^ix} = \sum_{n=0}^{\infty}(\alpha^i x)^n \in K[[x]]\]So, \[\frac{w(x)}{\sigma(x)} = \sum_{i \in \mathcal{E}}\frac{\alpha^ix}{1-\alpha^ix} = \sum_{i \in \mathcal{E}} \sum_{j = 1}^{\infty} (\alpha^ix)^j\]\[=\sum_{j=1}^{\infty} \sum_{i \in \mathcal{E}} (\alpha^ix)^j = \sum_{j=1}^{\infty}(\sum_{i \in \mathcal{E}} (\alpha^j)^i)x^j = \sum_{j=1}^{\infty} e(\alpha^j)x^j\]\[\implies w(x) = (\sum_{j=1}^{\infty}e(\alpha^j)x^j)\sigma(x)\]By definition of C we have \(c(\alpha^j) = 0\) for \(1 \le j \le \delta - 1\) so for \(1 \le j \le 2t\). So \(r(\alpha^j) = c(\alpha^j)\) for \(1 \le j \le 2t\)
Thus \(\sigma(x) \sum_{j=1}^{2t} r(\alpha^j)x^j \equiv w(x) \mod x^{2t+1}\) and \(\deg w(x) = \deg \sigma(x) \le t\)
Now to show uniqueness. Note \(\sigma(x)\) has distinct nonzero roots, so \(\sigma(x)\) and \(w(x) = -x\sigma'(x)\) are coprime. Suppose \(\tilde{\sigma}(x)\) and \(\tilde{w}(x)\) are another solution.
Assume \(\deg (\tilde{\sigma}) \le \deg \sigma\). Then \[\sigma(x)\tilde{w}(x) \equiv \tilde{\sigma}(x)w(x) \mod x^{2t+1}\]But \(\sigma, \tilde{\sigma}, w, \tilde{w} \) all have degree \(\le t\). So \(\sigma(x)\tilde{w}(x) = \tilde{\sigma}(x)w(x)\)
Since \(\sigma(x) \) and \(w(x)\) are coprime \(\implies \sigma(x) | \tilde{\sigma}(x)\)
But \(\deg \tilde{\sigma} \le \deg{\sigma}\) so \(\tilde{\sigma}\) is a scalar multiple of \(\sigma\) and both have constant term 1 so \(\sigma = \tilde{\sigma}\)

Q: Definition. A general feedback shift register is [...] A linear feedback shift register [...] The stream associated to the inital fill \(y_0 , \dots , y_{d-1}\) is the sequence [...]
A: a function \(f: F_2^d \to F_2^d\) of the form \[f(x_0, \dots , x_{d-1}) = (x_1, \dots , x_{d-1}, c(x_0, \dots , x_{d-1}))\]where \(c : F_2^d \to F_2\) is a function.; has c linear. i.e. \[c(x_0, \dots , x_{d-1}) = a_0x_0 + \dots +a_{d-1}x_{d-1} \quad \text{for some } a_i \in F_2\]; \(y_0 , y_1, \dots \) where \[y_n = a_{d-1}y_{n-1} + a_{d-2}y_{n-2} + \dots + a_1 y_{n-d+1} + a_0 y_{n-d} \quad \forall n \ge d\]or more generally \[y_n = c(y_{n-d}, y_{n-d+1}, \dots , y_{n-1})\]

Q: Definition. The stream produced by a LFSR is a recurrence relation. The feedback (auxiliary) polynomial is \[[...]\]
A: P(x) = x^d + a_{d-1}x^{d-1} + \dots + a_1x+ a_0

Q: Definition. A sequence \(x_0 , x_1 , \dots \) of elements in \(F_2\) has generating function \[[...]\]
A: G(X) = \sum_{j=0}^{\infty} x_j X^j \in F_2[[X]]

Q: Theorem. The stream \(x_0, x_1, \dots\) comes from a LFSR with feedback polynomial \(P(X)(a_0 \neq 0)\) iff \[G(X) = \frac{B(X)}{A(X)}\]where \(A(X)\) is the reverse of \(P(X)\) and \(B(X)\) a polynomial with \(\deg B < \deg A \)
A: Suppose \(P(X) = a_d X^d + \dots + a_1 X + a_0\) with \(a_d = 1\)
Then \(A(X) = a_0 X^d + \dots + a_d\)
So \(A(X)G(X) = (\sum_{i=0}^d a_{d-i}X^i)(\sum_{j=0}^{\infty} x_j X^j)\)
So \(A(X)G(X) \) is a polynomial of \(\deg < d\) iff coeff of \(X^r\) in \(A(X)G(X) = 0 \forall r \ge d\)
\(\iff \sum_{i=0}^da_{d-i}x_{r-i} = 0 \;\forall r\ge d \iff (x_n)_{n \ge 0}\) comes from a LFSR with feedback polynomial \(P(X)\)

Q: Definition. A cryptosystem consists of [...]
A: sets \(\mathcal{M, C, K}\) and functions \[e: \mathcal{M \times K \to C}\]\[d: \mathcal{C \times K \to M}\]s.t. \(d(e(m,k),k) = m \quad \forall m \in \mathcal{M}, \forall k \in \mathcal{K}\)
Back Extra: \(\mathcal{M}\) is all possible unencrypted messages
\(\mathcal{C}\) is all possible encrypted messages
\(\mathcal{K}\) is all possible keys

Q: Definition. (i) The key equivocation is \([...]\)
(ii) The message equivocation is \([...]\)
A: H(K|C); H(M|C)

Q: Lemma. \[H(M|C) \le H(K|C)\]
A: Since \(M = d(C,K)\) we know \(H(M|C,K) = 0\)
Then \(H(K|C) = H(K,C) - H(C) = H(M,K,C) - H(M|K,C) - H(C) = H(K|M,C) +H(M,C) - H(C) = H(K|M,C) + H(M|C)\)

Q: Definition. The unicity distance, U, is [...]
A: the least \(n>0\), if it exists, such that \(H(K|C^{(n)}) = 0\). Otherwise we say that U is infinite.
Back Extra: In words it is the least length of ciphertext required to uniquely determine the key.

Q: Lemma. Let \(x_0, x_1, \dots\) be a sequence produced by a LFSR of length d. Then \(\exists M,N \le 2^d - 1\) such that \(x_{r+N} = x_r \quad \forall r \ge M\)
A: Let \(v_i = (x_i , x_{i+1}, \dots , x_{i+d-1})\), so \(f: F_2^d \to F_2^d\), \(v_i \to v_{i+1}\)
If some \(v_i = 0\), then sequence is eventually all zeros(since f is linear), so lemma is true.
So assume all \(v_i \neq 0\), \(0 \le i \le 2^{d}- 1\), then \(v_0, v_1, \dots , v_{2^d - 1}\) are \(2^d\) elements in \(F_2^d \setminus \{0\}\) which has size \(2^d - 1\)
Therefore \(v_a = v_b\) for some \(0 \le a < b \le 2^d - 1\)
Let \(M = a, N = b-a\)
Show by induction \(v_{r+N} = v_r, \forall r \ge M\)
By construction \(v_{M+N} = V_M\)
Then \(v_{r+1 + N} = f(v_{r+N}) = f(v_r) = v_{r+1} \implies x_{r+N }= x_r \quad \forall r \ge M\)

Q: Definition. An algorithm runs in polynomial time if [...]
A: the number of operation is \(\le C(\text{input size})^d\) for some constants c and d.

Q: Lemma. Suppose \(p=4k-1\) is prime, and d an integer. If \(x^2 \equiv d \mod p\) is soluble then a solution is given by \(x\equiv d^k \mod p\)
A: If \(d = 0\) we are done.
Assume \(d \not \equiv 0\) then \(d^{2k-1}\equiv x^{2(2k-1) }\equiv x^{p-1} \equiv 1 \mod p\) by Fermat's Little Theorem
\(\implies (d^k)^2 \equiv d \mod p\)

Q: Lemma. (i) p an odd prime, \(d \not \equiv 0 \mod p\). If \(x^2 \equiv d \mod p \) is soluble then there are exactly two solutions
(ii) Suppose \(N = pq\), and p,q distinct odd primes and \(\gcd(d ,N) = 1\). If \(x^2 \equiv d \mod N\) is soluble, then there are exactly 4 solutions
A: (i) \(x^2 \equiv y^2 \mod p \implies p| x-y \quad or \quad p|x+y \implies x \equiv \pm y\)
(ii) SUppose \(x_0\) is a solution. By \(CRT\) there are solutions with \[x \equiv \pm x_0 \mod p\]\[x \equiv \pm x_0 \mod q\]for any 4 choices of \(\pm \) signs. By (i) these are all solutions

Q: Theorem. Breaking the Rabin code is essentially as difficult as factoring N
A: We have seen that if we can factor N, then we can decrypt the Rabin code
Conversely, suppose we have an algorithm for extracting square roots \(\mod N\). We pick \(x \mod N\) at random
We use the algorithm to find \(y\) s.t. \(x^2 \equiv y^2 \mod N\)
Then with probability \(1/2\), \(x \not \equiv \pm y\mod N\)
Then \(\gcd(x-y, N)\) is a non-trivial factor of N
If not, repeat with a new random choice of x. After r trials probability of failure is \(1/2^r\) which can be made arbitrarily small.

Q: How does RSA work?
A: Suppose N is the product of two large distinct primes.
We pick an integer \(e, (e,N) = 1\). Solve for \(d \) s.t. \(d e \equiv 1 \mod \phi(N)\)
Public key: \((N,e)\)
Prive key: \((N,d)\)
Message m is encrypted as \(c \equiv m^d\)
Ciphertext decrypted as \(m_1 \equiv c^d \mod N\)
Euler-Fermat tells us that \(m \equiv m_1 \mod N\)

Q: Theorem. Let \(N = pq, \) with p,q odd distinct primes.
Suppose \(\phi(N) | 2^a b\), b odd. Let \(1 \le x \le N\) with \((x,N) = 1\)
(i) If \(o_p(x^b) \neq o_q(x^b)\) then \(\exists 0 \le t \le a\) s.t. \(\gcd(x^{2^t b} - 1, N)\) is a nontrivial factor of N
(ii) The number of x satisfying (i) is \(\ge \phi(N) / 2\)
A: (i) Let \(y \equiv x^b \mod N\)
So \(y^{2^a} \equiv 1 \mod N\)
So \(o_p(y)\) and \(o_q(y)\) are powers of 2
We're given \(o_p(y) \ne o_q(y)\). Swapping p and q if needed we get, \[y^{2^t } \equiv 1 \mod p\]\[y^{2^t} \not \equiv 1 \mod q\]for some \(0 \le t \le a\) \(\implies \gcd(y^{2^t} - 1, N) = p\) as required.
(ii) Recall \((Z / NZ)^* = \{x + N\mathbb{Z} : 1 \le x \le N, (x,N) = 1\}\)
Want \(X = \#\{x \in (Z / NZ)^* : o_p(x^b) \neq o_q(x^b)\} \ge \frac{1}{2} |(Z / NZ)^*| = \frac{\phi(N)}{2}\)
CRT gives a bijection \[(Z/NZ)^* \leftrightarrow (Z / pZ)^* \times (Z / qZ)^*\]\[x \mapsto (x \mod p, x \mod q)\]We show that if we partition \((Z /pZ)^*\) into subsets according the the value of \(o_p(x^b)\) then each subset has size \(\le \frac{1}{2}|(Z / pZ)^*| = \frac{p-1}{2}\)
This suffices since if \(y \in (Z / qZ)^*\) then \[\# \{x \in (Z / p Z)^* : o_p(x^b) \neq o_q(y^b)\} \ge \frac{p-1}{2}\]\(\implies X \ge \frac{1}{2}(p-1)(q-1)\)
We exhibit a subset with size exactly \(\frac{1}{2}|(Z / pZ)^*|\)
Let g be a primitive root \(\mod p\), then \((g^b)^{2a} \equiv 1 \mod p \implies o_p(g^b)\) is a power of 2
If \(x - g^{\delta}\) then \(x^b =(g^b)^{\delta}\) and \(o_p(x^b) = \begin{cases} o_p (g^b) & \delta \text{ odd} \\ \le \frac{1}{2}o_p(g^b) & \delta \text{ even} \end{cases}\)
\(\implies \{g^{\delta} | \delta \text{ odd}\}\) is the required subset.

Q: Corollary. Finding the RSA private key from the public key is essentially as difficult as factoring N
A: If we know how to factor N we can compute \(\phi(N)\) and then solve for \(d \)
Conversely, if we know d and e, then \(de \equiv 1 \mod \phi(N) \implies \phi(N) | de - 1\). We write \(de -1 = 2^a b\) and use previous theorem to factor N. The probability of failure after r random choices of x is \(< 1/2^r\)

Q: How does Diffie-Hellman Key exchange work?
A: Parties A and B wish to agree a secret key for communcation, let p be a large prime and g a primitive root mod p.
Then A chooses a number \(\alpha \) and sends \(g^{\alpha} \mod p\) to B and B does the same with some \(\beta\)
Then \(K = (g^{\alpha})^{\beta} = (g^{\beta})^{\alpha}\) is the secret key

Q: What is the ElGamal Signature Scheme?
A: \(p\) large prime
\(g\) primitive root \(\mod p\)
A chooses a random integer \(1 < u < p\)
Public key: \(p,g,y = g^u \mod p\)
Private key: \(u\)
Let \(h: \mathcal{M} \to \{1,2, \dots , p-1\}\) be a collision resistant hash function
To send a message A chooses a random exponent \(k\) with \((k,p-1)=1\) and computes \(1 \le r \le p-1, 1\le s \le p-2\) satisfying
(i) \(r \equiv g^k \mod p\)
(ii) \(h(m) \equiv ur + ks \mod p-1\)
They sign the message \(m, (r,s)\)
B accepts the signature if \(g^{h(m)} \equiv y^r \times r^s \mod p\)