math/algebraic-coding-theory-notes.tex
algebraic-coding-theory-notes.texRaw
1\documentclass{article}
2\usepackage[utf8]{inputenc}
3\usepackage{amsfonts}
4% \usepackage{yfonts} % WIP
5\usepackage{amsthm}
6\usepackage{amsmath}
7\usepackage{mathrsfs}
8\usepackage{enumerate}
9\usepackage{hyperref}
10\usepackage{amssymb}
11
12\usepackage{tikz} % diagram
13\usetikzlibrary{calc}
14
15\begin{filecontents}[overwrite]{algebraic-coding-theory-notes.bib}
16@misc{hill,
17 author = {Raymond Hill},
18 title = {{A First Course in Coding Theory}},
19 year = {1986}
20}
21@misc{lint,
22 author = {J.H. van Lint},
23 title = {{Introduction to Coding Theory}},
24 year = {1981}
25}
26
27@misc{vanddetproof,
28 title = {Vandermonde determinant proof},
29 author = {Pedro Tamaroff},
30 howpublished = "\url{https://math.stackexchange.com/questions/525334/vandermonde-determinant-by-induction}",
31}
32
33@misc{vanddetproof2,
34 title = {Abstract Algebra, Theory and Applications. \emph{sec.22.2}},
35 author = {Thomas W. Judson},
36}
37\end{filecontents}
38\nocite{*}
39
40
41\theoremstyle{definition}
42
43\newtheorem{innerdefn}{Definition}
44\newenvironment{defn}[1]
45{\renewcommand\theinnerdefn{#1}\innerdefn}
46{\endinnerdefn}
47
48\newtheorem{innerthm}{Theorem}
49\newenvironment{thm}[1]
50{\renewcommand\theinnerthm{#1}\innerthm}
51{\endinnerthm}
52
53\newtheorem{innerlemma}{Lemma}
54\newenvironment{lemma}[1]
55{\renewcommand\theinnerlemma{#1}\innerlemma}
56{\endinnerlemma}
57
58\newtheorem{innerprop}{Proposition}
59\newenvironment{prop}[1]
60{\renewcommand\theinnerprop{#1}\innerprop}
61{\endinnerprop}
62
63\newtheorem{innercor}{Corollary}
64\newenvironment{cor}[1]
65{\renewcommand\theinnercor{#1}\innercor}
66{\endinnercor}
67
68\newtheorem{innereg}{Example}
69\newenvironment{eg}[1]
70{\renewcommand\theinnereg{#1}\innereg}
71{\endinnereg}
72
73\newtheorem{innerex}{Exercise}
74\newenvironment{ex}[1]
75{\renewcommand\theinnerex{#1}\innerex}
76{\endinnerex}
77
78\newtheorem{innerrem}{Remark}
79\newenvironment{remark}[1]
80{\renewcommand\theinnerrem{#1}\innerrem}
81{\endinnerrem}
82
83\newtheorem{innerintu}{Intuition}
84\newenvironment{intuition}[1]
85{\renewcommand\theinnerintu{#1}\innerintu}
86{\endinnerintu}
87
88\newtheorem{innerconj}{Conjecture}
89\newenvironment{conj}[1]
90{\renewcommand\theinnerconj{#1}\innerconj}
91{\endinnerconj}
92
93% custom shortcuts
94\newcommand{\Vnq}{V(n, q)}
95
96\title{Algebraic Coding Theory}
97\author{arnaucube}
98\date{2026}
99
100\begin{document}
101
102\maketitle
103
104\begin{abstract}
105 Notes taken while studying Algebraic Coding Theory, mostly from Hill book \cite{hill} and Lint book \cite{lint}.
106
107 Usually while reading books and papers I take handwritten notes in a notebook, this document contains some of them re-written to $LaTeX$.
108
109 The proofs may slightly differ from the ones from the books, since I try to extend them for a deeper understanding.
110\end{abstract}
111
112\tableofcontents
113
114
115\section{Vector spaces over finite fields, quick recap}
116Let $q$ be a prime power.
117
118$\Vnq$: set $GF(q)^n$ of all ordered $n$-tuples over $GF(q)$. $\Vnq$ is a
119vector space.
120
121A set of vectors $\{v_1, v_2, \ldots, v_r \}$ is said to be \emph{linear dependent} if $\exists$ scalars $a_1, \ldots, a_r$, not all zero, such that
122$$a_1 v_1 + a_2 v_2 + \ldots + a_r v_r = 0$$
123
124They are \emph{linear independent} if
125$$a_1 v_1 + a_2 v_2 + \ldots + a_r v_r = 0 ~\stackrel{implies}{\Longrightarrow}~ a_1=a_2=\ldots=a_r=0$$
126
127Let $C$ a subspace of $\Vnq$. Then a subset $\{v_1, v_2, \ldots, v_r \} \subseteq C$ is called a \emph{generating set} (or \emph{spanning set}) of $C$ if every vector in $C$ can be expressed as a linear combination of $v_1, \ldots, v_r$.
128
129A generating set of $C$ which is also linearly independent is called a \emph{basis} of $C$.
130
131\begin{thm}{4.3}
132 Suppose $\{v_1, v_2, \ldots, v_k\}$ is a basis of a subspace $C$ of $\Vnq$. Then
133 \begin{enumerate}[i.]
134 \item every vector of $C$ can be expressed uniquely as a linear combination of the basis vectors.
135 \item $C$ contains exactly $q^k$ vectors.
136 \end{enumerate}
137\end{thm}
138\begin{proof}
139 \begin{enumerate}[i.]
140\item suppose vector $x \in C$ such that
141$$x = a_1 v_1 + a_2 v_2 + \cdots + a_k v_k$$
142$$x = b_1 v_1 + b_2 v_2 + \cdots + b_k v_k .$$
143
144then
145$$(a_1-b_1)v_1 + (a_2-b_2)v_2 + \cdots + (a_k-b_k)v_k = 0 .$$
146
147But the set $\{v_1, v_2, \ldots, v_k\}$ is linearly independent, and so
148$$a_i - b_i = 0 \quad \text{for } i = 1,2,\ldots,k,$$
149i.e.,
150$$a_i = b_i \quad \text{for } i = 1,2,\ldots,k.$$
151
152\item By (i), the $q^k$ vectors
153$$\sum_{i=1}^{k} a_i v_i \qquad (a_i \in \mathrm{GF}(q))$$
154are precisely the distinct vectors of $C$.
155\end{enumerate}
156\end{proof}
157
158\vspace{1.0cm}
159
160\section{Linear codes}
161The theorems of this section are from \cite{hill} and follow the original enumeration of the book.
162
163Note about notation:\\
164A $q$-ary linear code $[n, k, d]$-code is also a $q$-ary $(n, q^k, d)$-code, but the opposite is not always true.
165
166\subsection{Some definitions}
167Let $q$ be a prime power. View $(F_q)^n$ as the vector space $\Vnq$.
168
169\begin{defn}{}[Linear code over GF(q)]
170 A \emph{linear code over $GF(q)$} is a subspace of $\Vnq$, with $n \geq 0$.
171\end{defn}
172
173Thus $C \subseteq \Vnq$ is a linear code iff
174\begin{enumerate}[i.]
175 \item $u+v \in C ~~ \forall u,v \in C$
176 \item $au \in C ~~ \forall u \in C,~ a \in GF(q)$
177\end{enumerate}
178
179If $C$ is a $k$-dimensional subspace of $\Vnq$, then the linear code $C$ is called an $[n, k]$-code. (sometimes with minimum distance $d$: $[n, k, d]$-code).
180
181\begin{defn}{}[Weight]
182 Weight, $w(x)$, of a vector $x \in \Vnq$ is the number of non-zero entries of $x$.
183\end{defn}
184
185\begin{lemma}{5.1}\label {h.5.1}
186 if $x,y \in \Vnq$, then $d(x,y)=w(x-y)$.
187\end{lemma}
188\begin{proof}
189 the vector $x-y$ has non-zero entries in preceisely those places where $x$ and $y$ differ.
190\end{proof}
191
192\begin{thm}{5.2} \label{5.2}
193 let $C$ a linear code, let $w(C)$ be the smallest of weights of the non-zero codewords of $C$. Then $d(C)=w(C)$.
194\end{thm}
195\begin{proof}
196 $\exists~ x,y \in C$ s.th. $d(C)=d(x,y)$.
197
198 By Lemma \ref{h.5.1}, $d(C)=w(x-y) \geq w(C)$, since $x-y$ is a codeword of the linear code $C$ (ie. $x-y \in C$).
199
200 On the other hand, for $x \in C$,\\
201 $w(C)=w(x)=d(x,0) \geq d(C)$, since $0 \in C$.
202
203 Hence, $d(C) \geq w(C)$ and $w(C) \geq d(C) ~~\Longrightarrow~ d(C)=w(C)$.
204\end{proof}
205
206
207\begin{defn}{}[Generator matrix (GM)]
208 a $k \times n$ matrix whose rows form a basis of a linear $[n,k]$-code is called a \emph{generator matrix} (GM) of the code.
209\end{defn}
210
211\subsection{Equivalence}
212
213\begin{thm}{5.4}
214 two known $k \times n$ matrices generate equivalent linear $[n,k]$-codes over $GF(q)$ if one matrix can be obtained from the other by a sequence of operations of the following types:
215 \begin{enumerate}
216 \item[R1.] permutation of the rows
217 \item[R2.] multiplication of a row by a non-zero scalar
218 \item[R3.] addition of a scalar multiple of one row to another
219 \item[C1.] permutation of the columns
220 \item[C2.] multiplication of any column by a non-zero scalar
221 \end{enumerate}
222\end{thm}
223
224\begin{thm}{5.5} \label{h.5.5}
225 let $G$ a GM of an $[n, k]$-code. Then by performing the previous operations, $G$ can be transformed to the standard form $[ I_k | A ]$
226 where $I_k$ is the $k \times k$ identity matrix, and $A$ is a $k \times (n-k)$ matrix.
227\end{thm}
228
229\subsection{Encoding with a linear code}
230Let $C$ a $[n,k]$-code over $GF(q)$ with GM $G$. $C$ contains $q^k$ codewords $\Longrightarrow$ can be used to communicate any one of $q^k$ distinct messages.
231
232Iddentify these messages with the $q^k$ tuples of $V(k,q)$.
233
234Encoding:\\
235msg vector: $u=u_1 u_2 \ldots u_k$; rows of $G$: $r_1 r_2 \ldots r_k$. Encode
236$$uG = \sum^k_{i=1} u_i r_i \in C$$
237ie. $uG$ is a codeword of $C$; a linear combination of the rows of the GM.
238
239Encoding function:
240\begin{align*}
241 V(k,q) &\longrightarrow C \subseteq \Vnq\\
242 u &\longmapsto uG
243\end{align*}
244
245If $G$ is in standard form (\ref{h.5.5}), $G= [I_k | A]$ with $A=[a_{ij}]$, then encoding $u$ is:
246$$x=uG = x_1x_2 \ldots x_k x_{k+1} \ldots x_n$$
247where
248\begin{align*}
249 &x_i=u_i ~~\text{for}~ 1 \leq i \leq k, ~\text{message digits}\\
250 &x_{k+i}=\sum^k_{j=1}~ a_ji u_j ~~\text{for}~ 1 \leq i \leq n-k, ~\text{check digits}\\
251\end{align*}
252
253the check digits add redundancy to gie protection against noise.
254
255\subsection{Decoding with a linear code}
256Codeword $x=x_1 x_2 \ldots x_n$, received vector $y=y_1 y_2 \ldots y_n$, error vector $e = y-x=e_1 e_1 \ldots e_n$.
257
258\subsubsection{Cosets}
259Cosets here are similar to the ones from typical group theory, just from another perspective.
260
261\begin{defn}{}[Coset]
262 Let $C$ a $[n,k]$-code over $GF(q)$ and $a \in \Vnq$.
263 Then the set $a + C = \{a+x | x\in C\}$ is called a \emph{coset} of $C$.
264\end{defn}
265
266\begin{defn}{}[Coset leader]
267 the vector having minimum weight in a coset is called the \emph{coset leader}.
268\end{defn}
269
270\begin{lemma}{6.3} \label{h.6.3}
271 Let $a+C$ a coset of $C$ and $b \in a+C$. Then $b+C=a+C$.
272\end{lemma}
273\begin{proof}
274 since $b \in a+C ~~\Longrightarrow~~ b=a+x$ for some $x \in C$.
275 If $b+y \in b+C$ then
276 $$b+y=(a+x)+y = a+(x+y) \in a+C$$
277
278 For the other direction, if $a+x \in a+C$ then
279 $$a+x=(b-x)+z = b+(z-x) \in b+C$$
280 hence $a+C \subseteq b+C$.
281
282 Therefore $b+C = a+C$.
283\end{proof}
284
285\begin{thm}{6.4}[Lagrange] \label{h.6.4}
286 suppose $C \subseteq \Vnq$ is a $[n,k]$-code over $GF(q)$. Then
287 \begin{enumerate}[i.]
288 \item evvery vector of $\Vnq$ is in some coset of $C$
289 \item every coset contains exactly $q^k$ vectors
290 \item two cosets either are disjoint or coincide (partial overlap is impossible)
291 \end{enumerate}
292\end{thm}
293\begin{proof}
294 \begin{enumerate}[i.]
295 \item if $a\in \Vnq$ then $a=a+0 \in a+C$
296 \item the map
297 \begin{align*}
298 C &\longrightarrow a+C ~\forall~ x \in C\\
299 x &\longmapsto a+x
300 \end{align*}
301 is a one-to-one map, hence $|a+C| = |C| = q^k$.
302 \item by contradiction, suppose cosets $a+C,~ b+C$ overlap. Then for some vector $v$,
303 $$v \in (a+C) \cap (b+C)$$
304 thus for some $x,y \in C$, $v=a+x=b+y$.
305
306 Hence $b=a+(x-y) \in a+C$, thus by Lemma \ref{h.6.3} we have $b+C=a+C$.
307 \end{enumerate}
308\end{proof}
309
310\begin{cor}{}
311 \ref{h.6.4} shows that $\Vnq$ is partitioned into disjoint cosets of $C$:
312 $$\Vnq = (0+C) \cup (a_1+C) \cup \ldots \cup (a_s +C)$$
313 where $s=q^{n-k} -1$, and by Lemma \ref{h.6.3} we may take $0, a_1, \ldots, a_s$ to be coset leaders.
314\end{cor}
315
316\begin{eg}{6.5} \label{h.6.5}
317 Let $C$ be the binary $[4,2]$-code with generator matrix
318$$
319G = \begin{pmatrix}
3201 & 0 & 1 & 1 \\
3210 & 1 & 0 & 1
322\end{pmatrix}
323$$
324
325ie.
326$C = \{0000,\, 1011,\, 0101,\, 1110\}$.
327
328Then the cosets of $C$ are
329\begin{align*}
330 0000 + C &= C \text{ itself}\\
331 1000 + C &= \{1000,\, 0011,\, 1101,\, 0110\}\\
332 0100 + C &= \{0100,\, 1111,\, 0001,\, 1010\} = 0001+C\\
333 0010 + C &= \{0010,\, 1001,\, 0111,\, 1100\}
334\end{align*}
335
336by Lemma \ref{h.6.3}: $0001 \in 0100 + C$, thus $0001+C=0100+C$.
337\end{eg}
338
339\subsection{Probability of error correction (in binary linear codes)}
340To evaluate how good a code is, must calculate the \emph{probability} that a received vector will be decoded as the codeword which was sent.
341
342Let $p$ be the symbol error probability.
343
344Probability that the error vector is agiven vector of weight $i$ is $p^i (1-p){n-i}$.
345
346\begin{thm}{6.7}
347 Let $C$ a binary $[n,k]$-code, and for $i=0,1,\ldots,n$ let $\alpha_i$ denote the number of coset leaders of weight $i$.
348
349 Then the probability $P_{corr}(C)$ that a received vector decoded by means of a standard array is the codeword which was sent is
350 $$P_{corr}(C) = \sum_{i=0}^n \alpha_i \cdot p^i(1-p)^{n-i}$$
351\end{thm}
352
353\begin{eg}{6.8}
354 $[n,k]$-code from \ref{h.6.5}, coset leaders are $0000, 1000, 0100, 0010$. Hence $\alpha_0=1,~ \alpha_1=3,~ \alpha_2=\alpha_3=\alpha_4=0$, so
355 $$P_{corr}(C) = (1-p)^4 + 3 p(1-p)^3 = (1-p)^3 (1+2p)$$
356\end{eg}
357
358\begin{remark}{6.9}\label{remark.6.9}
359 if $d(C)=2t+1$ or $d(C)=2t+2$, then $C$ can correct any $t$ errors.
360
361 Hence every vector of weight $\leq t$ is a coset leader and so $\alpha_i=\left( \stackrel{n}{i} \right)$ for $0 \leq i \leq t$.
362\end{remark}
363
364\begin{defn}{}[Rate]
365 $[n, k]$-code $C$ uses $n$ symbols to send $k$ message symbols; it has \emph{rate} $R(C)=k/n$.
366
367 A good code will have a high rate.
368\end{defn}
369
370\begin{defn}{}[Capacity]
371 the \emph{capacity} $\mathscr{C}(p)$ of a binary symmetric channel with symbol error probability $p$ is
372 $$\mathscr{C}(p) = 1+ p \cdot \log_2{(p)} + (1-p) \cdot \log_2{(1-p)}$$
373\end{defn}
374
375
376\begin{thm}{6.12}[Shanon's theorem]
377 channel binary symmetric with symbol error probability $p$.
378
379 Let $R < \mathscr{C}(p)$.
380
381 Then for any $\epsilon >0$, $\exists$ for sufficient large $n$, an $[n,k]$-code $C$ of rate $k/n \geq R$ such that $P_{err}(C) < \epsilon$.
382\end{thm}
383
384\begin{defn}{}[$P_{symb}$]
385 $P_{symb}$ denotes the average probability that a message symbol is in error after decoding.
386\end{defn}
387
388\begin{thm}{6.14}
389 let $C$ a binary [n,k]-code and let $A_i$ denote the number of codewords of $C$ of weight $i$.
390
391 Then, if $C$ is used for error detection, the probability of an incorrect message being undetected is
392 $$P_{undetec}(C) = \sum_{i=1}^n A_i \cdot p^i (1-p)^{n-i}$$
393\end{thm}
394
395\begin{eg}{6.15}
396 for the code of \ref{h.6.5},
397 $$P_{undetec}(C) = \underbrace{1 \cdot p^2 (1-p)^2}_{0101} + \underbrace{2 \cdot p^3(1-p)^{4-3=1} }_{1011,~1110}= p^2 -p^4$$
398\end{eg}
399
400
401
402\vspace{0.5cm}
403
404\subsection{Exercises}
405\begin{ex}{5.1}
406 is the binary (11, 24, 5)-code linear?
407\end{ex}
408\begin{proof}
409 recall: a q-ary linear $[n,k,d]$-code is also a q-ary $(n, q^k, d)$-code, but
410 the opposite is not always true.
411
412 $\Longrightarrow~ (11, 24, 5)$-code to be linear it would mean that $24=q^k$.
413
414 Since it is binary, $q=2$. But $24 \neq 2^k$, so it can not be linear.
415\end{proof}
416
417\begin{ex}{5.2} \label{ex.5.2}
418 $E_n$ is the code of all even-weight vectors of $V(n,2)$, which is linear.
419 What are the parameters $[n, k, d]$ of $E_n$? Write a GM for $E_n$ in standard
420 form.
421\end{ex}
422\begin{proof}
423 $$E_n = \{ x \in V(n, 2) | w(x) ~\text{is even} \}$$
424
425 $\longrightarrow$ is the binary even-weight ode (the single parity-check code);\\
426 it's linear since
427 \begin{itemize}
428 \item the zero vector has even weight
429 \item over $GF(2)$, the sum of two even-weight vectors has even weight
430 \end{itemize}
431
432 Recall: $F_q^n \Longleftrightarrow \Vnq$, so $V(n, 2) \cong F_2^n$
433
434 $$\Longrightarrow~ E_n = \{ (x_1, \ldots, x_n) \in F_2^n | x_1 + \ldots + x_n = 0 \}$$
435
436 minimum distance is $2$, since
437 \begin{itemize}
438 \item no word of weight 1 is in $E_n$
439 \item words of weight 2 are in $E_n$
440 \end{itemize}
441
442 Therefore, parameters are $[n, n-1, 2]$
443
444 GM:
445 $$G=\left[ I_{n-1} | 1 \right]$$
446
447 which generates vectors of the form
448 $$(a_1, \ldots, a_{n-1}, a_1+\ldots+a_{n-1})$$
449\end{proof}
450
451\begin{ex}{5.5}
452 Prove that in a \emph{binary linear code}, either all the codewords have even weight or exactly half have even weight and half odd weight.
453\end{ex}
454\begin{proof}
455 let $C_e,~ C_o$ be subsets of $C$ with even and odd weights respectively.
456
457 So that $C = C_e \cup C_o$ (disjoint union).
458
459 For binary vectors $x,y$:
460 $$w(x+y) = w(x) + w(y) \pmod 2$$
461
462 ie. over $F_2$, the parity of the weight is additive:
463 \begin{align*}
464 even + even &= even\\
465 even + odd &= odd\\
466 odd + odd &= even
467 \end{align*}
468
469 Now we have two possible cases:
470 \begin{itemize}
471 \item $C$ has no odd weighted codewords:\\
472 $C_0 = \emptyset,~ \forall x \in C$ $x$ is even weighted
473 \item $C$ has at least one odd-weighted codeword:\\
474 let $u \in C_o$, consider the map
475 \begin{align*}
476 \phi: C_e &\longrightarrow C_o\\
477 c &\longmapsto c+u
478 \end{align*}
479 with $c \in C_e,~ u \in C_o,~ \phi(c) \in C_o$.
480
481 $\phi$ is bijective, since $\phi(\phi(c))=(c+u)+u=c$,
482
483 so $\phi$ is it's own inverse; hence $|C_e| = |C_o|$.
484
485 Since $C=C_e \cup C_e$, half codewords are even weighted and half odd.
486 \end{itemize}
487\end{proof}
488
489\begin{ex}{6.1}
490 construct standard arrays for codes having each of the GMs:
491
492 $$G_1 = \begin{pmatrix}
493 1 & 0 \\
494 0 & 1
495 \end{pmatrix} ~~~
496 G_2 = \begin{pmatrix}
497 1 & 0 & 1\\
498 0 & 1 & 1
499 \end{pmatrix}
500 $$
501\end{ex}
502\begin{proof}
503 recall: for a binary code with GM $G$, the code $C$ consists of all binary linear combinations of the rows of $G$.
504
505 For $G_1$:\\
506 rows: $r_1=(1,0),~r_2=(0,1))$. A codeword is any linear combination:
507 $$u G_1= a \cdot r_1 + b \cdot r_2,~~ \text{with}~ a,b \in \{0,1\}$$
508
509 4 combinations:
510 \begin{align*}
511 0 \cdot r_1 + 0 \cdot r_2 &= (0,0)\\
512 1 \cdot r_1 + 0 \cdot r_2 &= (1,0)\\
513 0 \cdot r_1 + 1 \cdot r_2 &= (0,1)\\
514 1 \cdot r_1 + 1 \cdot r_2 &= (1,0)+(0,1) = (1,1)
515 \end{align*}
516 $$\Longrightarrow~ C_1 = \{00, 10, 01, 11\}$$
517 $$\text{standard array:}~ 00~01~10~11$$
518
519
520 \vspace{0.5cm}
521 For $G_2$:\\
522 rows: $r_1=(1, 0, 1),~ r_2=(0, 1, 1)$. Codeword: $a \cdot r_1 + b \cdot r_2$ with $a, b \in \{0,1\}$.
523
524 4 combinations:
525 \begin{align*}
526 0 \cdot r_1 + 0 \cdot r_2 &= (0,0,0)\\
527 1 \cdot r_1 + 0 \cdot r_2 &= (1,0,1)\\
528 0 \cdot r_1 + 1 \cdot r_2 &= (0,1,1)\\
529 1 \cdot r_1 + 1 \cdot r_2 &= (1,0,1)+(0,1,1) = (1,1,0)
530 \end{align*}
531
532 $$\Longrightarrow~ C_2 = \{000, 101, 011, 110\}$$
533 $\Longrightarrow~$ so the 1st row of the standard array is: $000~101~011~110$.
534
535 Now, pick a non used vector: $001$, add it to the code $C_2$:
536 \begin{align*}
537 001 + C_{2_i}&\\
538 001 + 000 &= 001\\
539 001 + 101 &= 100\\
540 001 + 011 &= 010\\
541 001 + 110 &= 111
542 \end{align*}
543 $\Longrightarrow$ 2nd row of the standard array: $001~100~010~111$
544
545 Thus the standard array is
546 \begin{align*}
547 000~101~011~110\\
548 001~100~010~111
549 \end{align*}
550 ie. $2^3=8$ vectors, a $V(3,2)$ vector space.
551\end{proof}
552
553\begin{ex}{6.4}
554 $C$ a binary $[n,k]$-code with minimum distance $2t+1$ (or $2t+2$). Given that $p$ is very small, show that an approximate value of $P_{err}(C)$ is $\left( \binom{n}{t+1} - \alpha_{t+1} \right) p^{t+1}$, where $\alpha_{t+1}$ is the number of coset leaders of $C$ of weight $t+1$.
555\end{ex}
556\begin{proof}
557 From \ref{remark.6.9}, if $d(C)=2t+1$ (or $2t+2$) $Longrightarrow~ C$ can correct any $t$ errors.
558
559 Hence every vector of weight $\leq t$ is a coset leader and so $\alpha_i = \binom{n}{i}$ for $0 \leq i \leq t$.
560
561 \begin{equation}
562 P_{corr}(C) = \sum_{i=0}^n \alpha_i \cdot p^i(1-p)^{n-i}
563 \label{6.4.eq.1}
564 \end{equation}
565
566 where $\alpha_i$ is the number of coset leaders of weight $i$
567
568 From the $\binom{n}{i}$ vectors of weight $i$, exactly $\alpha_i$ are coset leaders, so the non coset leaders are $\binom{n}{i} - \alpha_i$. This is when a decoding error happens.
569
570 $$\Longrightarrow~ P_{err}(C) = \sum_{i=0}^n \left( \binom{n}{i} - \alpha_i \right) p^i (1-p)^{n-i}$$
571
572
573 \vspace{0.5cm}
574 Alternatively from \ref{6.4.eq.1}:
575 $$P_{err}(C) = 1 - P_{corr}(C) = 1 - \sum_{i=0}^n \alpha_i \cdot p^i(1-p)^{n-i}$$
576
577 Notice that
578 $$\sum_{i=0}^n \binom{n}{i} p^i (1-p)^{n-i} = (p + (1-p))^n = 1^n = 1$$
579
580 thus
581 \begin{align*}
582 P_{err}(C) &= \sum_{i=0}^n \binom{n}{i} p^i (1-p)^{n-i} - \sum_{i=0}^n \alpha_i \cdot p^i(1-p)^{n-i}\\
583 &= \sum_{i=0}^n \left( \binom{n}{i} - \alpha_i \right) p^i (1-p)^{n-i}
584 \end{align*}
585
586 Now, from \ref{remark.6.9}, $\forall i \leq t,~ \alpha_i = \binom{n}{i}$, thus $\binom{n}{i} - \alpha_i = 0$ for the first $t$ terms in the sum.
587
588 Thus
589 \begin{align*}
590 P_{err}(C) &= \sum_{i=0}^n \left( \binom{n}{i} - \alpha_i \right) p^i (1-p)^{n-i}\\
591 &= \left( \binom{n}{t+1} - \alpha_{t+1} \right) p^{t+1} (1-p)^{n-t+1} + \ldots
592 \end{align*}
593 where the $\ldots$ represent the terms with $p^{t+2}$ and higher.
594
595 Then, since $p$ is very small (by the exercise definition), $(1-p)^{n-t+1} \equiv 1$, and the other higher powers of $p$ are negligible.
596
597 Hence,
598 $$P_{err}(C) = \left( \binom{n}{t+1} - \alpha_{t+1} \right) \cdot p^{t+1}$$
599\end{proof}
600
601
602\vspace{1.0cm}
603
604\section{Dual code, PCM and Syndrome}
605
606\subsection{Dual code}
607
608\begin{defn}{}[Orthogonal]
609 Inner product:
610 $$u \cdot v = u_1 v_1 + \ldots + u_n \cdot v_n = \sum_{i=1}^n u_i v_i$$
611 If $u \cdot v = 0$, then $u$ and $v$ are called \emph{orthogonal}.
612\end{defn}
613
614\begin{lemma}{7.1} \label{7.1}
615 for any $u,v,w \in \Vnq$ and $\lambda, \mu \in GF(q)$,
616 \begin{enumerate}[i.]
617 \item $u \cdot v = v \cdot u$
618 \item $(\lambda u + \mu v) \cdot w = \lambda(u \cdot w) + \mu (v \cdot w)$
619 \end{enumerate}
620\end{lemma}
621\begin{proof}
622 (at exercise \ref{ex.7.1}).
623\end{proof}
624
625\begin{defn}{}[Dual code]
626 given a linear $[n, k]$-code $C$, the \emph{dual code} of $C$, denoted $C^{\perp}$, is defined to be the set of those vectors of $\Vnq$ which are orthogonal to every codeword of $C$. ie.
627 $$C^{\perp} = \{ v \in \Vnq ~|~ v \cdot u = 0 ~\forall~ u \in C \}$$
628\end{defn}
629
630\begin{lemma}{7.2} \label{7.2}
631 $C$ a $[n,k]$-code with GM $G$. Then $v \in \Vnq$ belongs to $C^\perp$ iff $v$ is orthogonal to every row of $G$, ie.
632 $$v \in C^\perp \Longleftrightarrow v \cdot G^T = 0$$
633\end{lemma}
634\begin{proof}
635 let rows of $G$ be $r_1, \ldots, r_k$, suppose $v \cdot r_i = 0 ~\forall i$ (ie. $v$ orthogonal to every row of $G$).
636
637 If $u \in C$ (ie. a codeword of $C$), then $u = \sum_{i=1}^k \lambda_i r_i$ for some scalars $\lambda_i$, so that
638 $$v \cdot u = v \cdot \sum_{i=1}^k \lambda_i r_i = \sum_{i=1}^k \lambda_i \cdot \underbrace{(v \cdot r_i)}_{0} = \sum \lambda_i \cdot 0 = 0$$
639
640 $\Longrightarrow~$ hence $v$ is orthogonal to every codeword of $C$, and so is in $C^\perp$.
641\end{proof}
642
643
644\begin{thm}{7.3}
645 $C$ a $[n,k]$-code over $GF(q)$. Then the dual code $C^\perp$ of $C$ is a linear $[n, n-k]$-code.
646\end{thm}
647\begin{proof}
648 \begin{enumerate}[i.]
649 \item first show that $C^\perp$ is a linear code:
650
651 let $v_1,v_2 \in C^\perp$ and $\lambda, \mu \in GF(q)$. Then $\forall u \in C$,
652 \begin{align*}
653 (\lambda v_1 + \mu v_2) \cdot u &= \lambda (v_1 \cdot u) + \mu (v_2 \cdot u)\\
654 &\text{notice that $v_1,v_2 \in C^\perp$, so}\\
655 &\text{that $v_1,v_2$ are orthogonal with $u$}\\
656 &\text{hence $(v_1 \cdot u)$ and $(v_2 \cdot u)$ are $0$}\\
657 &= \lambda \cdot 0 + \mu \cdot 0 = 0
658 \end{align*}
659
660 Hence $\lambda \cdot v_1 + \mu \cdot v_2 \in C^\perp$, and so $C^\perp$ is linear, since it is closed under linear combinations.
661
662 \item Next, show that $C^\perp$ has dimension $n-k$:
663
664 Let $G=[g_{ij}]$ be a GM of $C$.
665
666 Then by Lemma 7.2, the elements of $C^\perp$ are the vectors $v = (v_1, v_2, \dots, v_n)$, since $v \in C^\perp \Longleftrightarrow v \cdot G^T=0$, satisfying
667 $$\sum_{j=1}^{m} g_{ij} v_j = 0, ~\forall~ i = [k]$$
668
669 $\longrightarrow$ this is a system of $k$ independent homogeneous equations in $n$ unknowns, with solution space $C^\perp$. From linear algebra we know that it has dimension $n-k$. To see it:
670
671 if codes $C_1$ and $C_2$ are equivalent, then $C_1^\perp,~ C_2^\perp$ are also equivalent. Hence is enough to show that $\dim(C^\perp) = n-k$, where $C$ is a standard form GM:
672
673$$C = \begin{pmatrix}
674 1 & \ldots & 0 & a_{1,1} & \ldots & a_{1, n-k} \\
675 \vdots & & \vdots & \vdots & & \vdots \\
676 0 & \ldots & 1 & a_{k,1} & \ldots & a_{k, n-k} \\
677\end{pmatrix}$$
678
679Then
680$$C^\perp = \{ (v_1, \ldots, v_n) \in \Vnq ~\big|~ v_i + \sum_{j=1}^{n-k} a_{i,j} v_{k+j} = 0,~ i=1,2,\ldots,k \}$$
681
682For each of the $q^{n-k}$ choices of $(v_{k+1}, \ldots, v_n),~~ \exists!~ (v_1, v_2, \ldots, v_n) \in C^\perp$.
683
684Hence $|C^\perp| = q^{n-k}$, therefore $dim(C^\perp) = n-k$.
685 \end{enumerate}
686\end{proof}
687
688\begin{thm}{7.5} \label{7.5}
689 for any $[n,k]$-code $C$, $(C^\perp)^\perp = C$.
690\end{thm}
691\begin{proof}
692 clearly $C \subseteq (C^\perp)^\perp$, since every vector in $C$ is orthogonal to every vector in $C^\perp$.
693
694 But $dim((C^\perp)^\perp) = n - (n - k ) = k = dim(C)$, therefore $C=(C^\perp)^\perp$.
695\end{proof}
696
697
698\subsection{PCM (parity-check matrix)}
699
700\begin{defn}{}[PCM]
701 A \emph{parity-check matrix} (PCM) $H$ for a $[n,k]$-code $C$ is a generator matrix of $C^\perp$.
702
703 $\Longrightarrow~H$ is a $(n-k) \times n$ matrix satisfying $GH^T=0$.
704\end{defn}
705
706From \ref{7.2} and \ref{7.5},\\
707if $H$ a PCM of $C$, then
708$$C = \{ x \in \Vnq ~|~ xH^T=0 \}$$
709
710$\Longrightarrow$ Any linear code is completely specified by a PCM.
711
712\vspace{0.5cm}
713
714\begin{intuition}{}
715 \begin{enumerate}[i.]
716 \item{PCM:} $G$ specifies how to build a codeword, the PCM $H$ specifies the rules a vector must follow to be considered a valid codeword.
717 \item{dual-code:} orthogonal "shadow", see $C$ as a plane through 3D origin; $C^\perp$ is the (normal vector) line emerging from the plane.
718
719 Rows of the PCM are the basis for the dual-code $C^\perp$ $\Longrightarrow$ ie. the rules that define $C$ are themselves a code.
720 \end{enumerate}
721\end{intuition}
722
723\vspace{0.5cm}
724\begin{thm}{7.6} \label{7.6}
725 if $G= [I_k | A]$ is the standard form generator matrix of an $[n,k]$-code $C$, then a PCM for $C$ is $H=[-A^T ~|~ I_{n-k}]$.
726
727 eg.
728$$G = \begin{bmatrix}
729 1 & \ldots & 0 & a_{1,1} & \ldots & a_{1, n-k} \\
730 \vdots & & \vdots & \vdots & & \vdots \\
731 0 & \ldots & 1 & a_{k,1} & \ldots & a_{k, n-k} \\
732\end{bmatrix}$$
733
734$$H = \begin{bmatrix}
735 -a_{1,1} & \ldots & -a_{1, n-k} & 1 & \ldots & 0 \\
736 \vdots & & \vdots & \vdots & & \vdots \\
737 -a_{k,1} & \ldots & -a_{k, n-k} & 0 & \ldots & 1 \\
738\end{bmatrix}$$
739which, in binary, the minus signs are unnecessary.
740\end{thm}
741
742\begin{defn}{}[Standard form]
743 a PCM that is $H = [B ~|~ I_{n-k}]$
744\end{defn}
745
746\subsection{Syndrome}
747\begin{defn}{}[Syndrome]
748 let $H$ a PCM of a $[n,k]$-code $C$.
749
750 Then $\forall~ y \in \Vnq$, the $1 \times (n-k)$ row vector
751 $$S(y) = y H^T$$
752 is called the \emph{syndrome} of $y$.
753\end{defn}
754
755\begin{remark}{}
756 \begin{enumerate}[i.]
757 \item for $h_1, h_2, \ldots, h_{n-k}$ being rows of $H$, then
758 $$S(y) = (y \cdot h_1, y \cdot h_2, \ldots, y \cdot h_{n-k})$$
759 \item $S(y)=0 \Longleftrightarrow y \in C$
760 \end{enumerate}
761\end{remark}
762
763\begin{intuition}{}
764 Syndrome is the "sympthom" of the error. It ignores the valid part of the message and isolates the noise.
765
766 $$S(y) = y H^T = (c+e)H^T = \underbrace{cH^T}_{0} + eH^T = 0+eH^T = e H^T$$
767
768 Syndrome allows the receiver to identify what went wrong without knowing what was originally sent.
769\end{intuition}
770
771\begin{lemma}{7.8}
772 two vectors $u,v$ are the same ocset of $C$ iff they have the same syndrome.
773\end{lemma}
774\begin{proof}
775 if $u,v$ in the same coset of $C$
776 \begin{align*}
777 &\Longrightarrow u+C = v+C\\
778 &\Longrightarrow u-v \in C\\
779 &\Longrightarrow (u-v)H^T =0\\
780 &\Longrightarrow uH^T =v H^T\\
781 &\Longrightarrow S(u) = S(v)
782 \end{align*}
783\end{proof}
784
785\begin{cor}{7.9}
786 There is a one-to-one ccorrespondence between cosets and syndromes.
787
788 $\longrightarrow$ for small $n$, it's fast to locate the received vector $y$ in the array, but for large $n$: use syndrome to find which coset (ie. which row of the array) contains $y$.
789\end{cor}
790
791\begin{eg}{7.9}
792 (from example \ref{h.6.5})
793 $$G= \begin{bmatrix}
794 1 & 0 & 1 & 1\\
795 0 & 1 & 0 & 1
796 \end{bmatrix}$$
797 by \ref{7.6},
798 $$H= \begin{bmatrix}
799 1 & 0 & 1 & 0\\
800 1 & 1 & 0 & 1
801 \end{bmatrix}$$
802
803 Hence the syndromes of the coset leaders are
804 \begin{align*}
805 S(0000) &= 00\\
806 S(1000) &= 11\\
807 S(0100) &= 01\\
808 S(0010) &= 10\\
809 \end{align*}
810
811 The standard array becomes:
812
813 $$
814 \begin{matrix}
815 coset leaders & & & & syndromes\\
816 0000 & 1011 & 0101 & 1110 & 00\\
817 1000 & 0011 & 1101 & 0110 & 11\\
818 0100 & 1111 & 0001 & 1010 & 01\\
819 0010 & 1001 & 0111 & 1100 & 10
820 \end{matrix}
821 $$
822
823 so, decoding algorithm: when a vector $y$ is received, calculate $S(y)=yH^T$, locate $S(y)$ in the \emph{syndromes} column of the array.
824
825 Locate $y$ in the corresponding row and decode as the codeword at the top of the column containing $y$.
826
827
828 $\longrightarrow$ in practice: \emph{syndrome lookup table}:
829 $$
830 \begin{matrix}
831 \text{syndrome}~ z & \text{coset leader}~ f(z)\\
832 00 & 0000\\
833 11 & 1000\\
834 01 & 0100\\
835 10 & 0010
836 \end{matrix}
837 $$
838
839 decoding procedure:
840 \begin{enumerate}
841 \item receive $y$, calculate $S(y)=y H^T$
842 \item let $z=S(y)$, locate $z$ in the first column of the looku table
843 \item decode $y$ as $y-f(z)$
844 \end{enumerate}
845\end{eg}
846
847\subsection{Incomplete decoding}
848For $d(C)= 2t +1$ (or $2t+2$), guarantee the correction of $\leq t$ errors in any codewordd and also detect some cases of more than $t$ errors.
849
850$\longrightarrow$ Arrange the cosets in order of increasing weight of the coset leaders.
851
852Divide the array into a top part and a bottom part; top: cosets whose leaders have weights $\leq t$.
853
854\begin{itemize}
855 \item[-] If $y$ in top part: decode as usual (assuming $\leq t$ errors).
856 \item[-] If $y$ in bottom part: conclude that $>t$ errors have occurred, ask for retransmission.
857\end{itemize}
858
859\subsection{Exercises}
860
861\begin{ex}{7.1} \label{ex.7.1}
862 prove Lemma \ref{7.1}
863\end{ex}
864\begin{proof}
865 For any $u,v,w \in \Vnq$ and $\lambda, \mu \in GF(q)$,
866 \begin{enumerate}[i.]
867 \item $u \cdot v = v \cdot u$
868 $$u \cdot v = \sum_{i=1}^n u_i \cdot v_i = \sum_{i=1}^n v_i \cdot u_i = v \cdot u$$
869 \item $(\lambda u + \mu v) \cdot w = \lambda(u \cdot w) + \mu (v \cdot w)$
870 \begin{align*}
871 (\lambda u + \mu v) w &= \sum(\lambda u_i + \mu v_i) w_i\\
872 &= \sum (\lambda u_i w_i + \mu v_i w_i)\\
873 &= \sum (\lambda u_i w_i) + \sum (\mu v_i w_i)\\
874 &= \lambda \sum(u_i w_i) + \mu \sum (v_i w_i)\\
875 &= \lambda \cdot (u \cdot w) + \mu \cdot (v \cdot w)
876 \end{align*}
877 \end{enumerate}
878\end{proof}
879
880\begin{ex}{7.2}
881 prove that if $E_n$ is the binary even weight code of length $n$, then
882 $E_n^\perp$ is the repetition code of length $n$.
883\end{ex}
884\begin{proof}
885 from exercise \ref{ex.5.2}:
886 $$E_n = \{ x \in V(n,2) ~|~ w(x) ~\text{is even} \} = \{ (x_1, \ldots, x_n) \in F_2^n ~|~ x_1 + \ldots + x_n = 0 \}$$
887
888 GM of $E_n$:
889 $$G = \left[ I_{n-1} \,\middle|\,
890 \begin{matrix}
891 1 \\ \vdots \\ 1
892 \end{matrix}
893 \right]$$
894
895 thus, by \ref{7.6}, PCM is $H=\begin{bmatrix}1&1&\cdots&1\end{bmatrix}$.
896
897 If $H$ is a PCM for $C$, then the rows of $H$ generate $C^\perp$.
898
899 Therefore
900 $$E_n^\perp = <\underbrace{[1~1~\cdots~1]}_{generator}>$$
901
902 then it's codewords are:
903 \begin{align*}
904 0 \cdot (1, \ldots, 1) &= (0, \ldots, 0)\\
905 1 \cdot (1, \ldots, 1) &= (1, \ldots, 1)
906 \end{align*}
907
908 $$\Longrightarrow~ E_n^\perp = \{00\ldots 00,~ 11 \ldots 1 \}$$
909 ie. the repetition code of length $n$.
910\end{proof}
911
912\begin{ex}{7.4}
913 for a binary linear code with PCM $H$, show that the transpose of the syndrome of a received vector is equal to the sums of those columns of $H$ corresponding to where the errors occurred.
914\end{ex}
915\begin{proof}
916 Let $e$ the error, $y$ the vector received, and $x$ the original codeword. Then $y=x+e$.
917
918 Then
919 $$S(y) = y H^T = (x+e)H^T = \underbrace{xH^T}_{\substack{0, \text{since $H$}\\ \text{is PCM of $C$}\\ \text{and $x\in C$}}} + eH^T = e H^T$$
920
921 So,
922 $$S(y)^T = e^T H = \sum_{j=1}^n e_j \cdot H_j$$
923 where $H_j$ is the $j$-th column of $H$.
924\end{proof}
925
926
927\begin{ex}{7.6}
928
929 Let $C$ be the ternary linear code with GM
930 $$G = \begin{bmatrix}
931 1 & 1 & 1 & 0 \\
932 2 & 0 & 1 & 1
933 \end{bmatrix}$$
934
935 \begin{enumerate}
936 \item[(a)] Find a generator matrix in standard form.
937 \item[(b)] Find a parity check matrix (PCM) for $C$ in standard form.
938 \item[(c)] Use syndrome decoding to decode the received vectors:
939 $2122, 1201, 2222$
940 \end{enumerate}
941\end{ex}
942\begin{proof}
943 \begin{enumerate}[(a)]
944 \item
945 $$
946 \begin{bmatrix}
947 1 & 1 & 1 & 0 \\
948 2 & 0 & 1 & 1
949 \end{bmatrix}
950 \rightarrow
951 \begin{bmatrix}
952 1 & 1 & 1 & 0 \\
953 0 & 1 & 2 & 1
954 \end{bmatrix}
955 \rightarrow
956 \begin{bmatrix}
957 1 & 0 & 2 & 2 \\
958 0 & 1 & 2 & 1
959 \end{bmatrix}
960 $$
961 thus $
962 G=\begin{bmatrix}
963 1 & 0 & 2 & 2 \\
964 0 & 1 & 2 & 1
965 \end{bmatrix}
966 $ is PCM in standard form.
967
968 \item
969 since $
970 G=\begin{bmatrix}
971 1 & 0 & 2 & 2 \\
972 0 & 1 & 2 & 1
973 \end{bmatrix}
974 $
975 then
976 $$
977 H =
978 \begin{bmatrix}
979 -2 & -2 & 1 & 0 \\
980 -2 & -1 & 0 & 1
981 \end{bmatrix}
982 =
983 \begin{bmatrix}
984 1 & 1 & 1 & 0 \\
985 1 & 2 & 0 & 1
986 \end{bmatrix}
987 $$
988
989 \item
990 $$
991 S(y) = y H^T=S(y) = (y \cdot h_1,\; y \cdot h_2).
992 $$
993 w/ $h_i$ the rows of $H$.
994
995 compute the lookup table (syndrome table):
996 $$
997 \begin{array}{c|c}
998 e & S(e) \\
999 \hline
1000 0000 & 00 \\
1001 1000 & 11 \\
1002 2000 & 22 \\
1003 0100 & 12 \\
1004 0200 & 21 \\
1005 0010 & 10 \\
1006 0020 & 20 \\
1007 0001 & 01 \\
1008 0002 & 02
1009 \end{array}
1010 $$
1011 left: weight-$1$ errors, since we're over $F_3$; right: coset leaders for the 9 cosets.
1012
1013 \begin{enumerate}[i.]
1014 \item $y = 2121$:
1015 $$
1016 S(y) =
1017 \begin{bmatrix}
1018 2 & 1 & 2 & 1
1019 \end{bmatrix}
1020 \begin{bmatrix}
1021 1 & 1 \\
1022 1 & 2 \\
1023 1 & 0 \\
1024 0 & 1
1025 \end{bmatrix}
1026 =
1027 [5,5] \equiv [2,2].
1028 $$
1029
1030 $S(y)=[2,2]$, corresponds (in the table) to $e = 2000$.
1031
1032 $$\Longrightarrow~ c = y - e = 2121 - 2000 = 0121$$
1033
1034 \item $y = 1201$
1035 $$
1036 S(y) =
1037 \begin{bmatrix}
1038 1 & 2 & 0 & 1
1039 \end{bmatrix}
1040 H^T
1041 = [3, 6] = [0,0].
1042 $$
1043
1044 corresponds to $e = 0000$
1045 $$\Longrightarrow~ c = y-e = 1201$$
1046
1047 \item $y = 2222$
1048 $$
1049 S(y) =
1050 \begin{bmatrix}
1051 2 & 2 & 2 & 2
1052 \end{bmatrix}
1053 H^T
1054 = [6,8] = [0,2].
1055 $$
1056
1057 corresponds to $e = 0002$
1058
1059 $$\Longrightarrow~ c = y - e = 2222 - 0002 = 2220$$
1060 \end{enumerate}
1061 \end{enumerate}
1062\end{proof}
1063
1064
1065\vspace{1.0cm}
1066
1067\section{Hamming Codes}
1068
1069\begin{defn}{}[Binary Hamming Code]
1070 let $r$ a positive integer, $H$ a $r \times (2^r -1)$ matrix whose columns are the distinct non-zero vectors of $V(r, 2)$.
1071
1072 The code having $H$ as its PCM is called a \emph{binary Hamming code}, denoted $Ham(r,2)$.
1073\end{defn}
1074
1075
1076\begin{remark}{}
1077 $Ham(r, 2)$ has length $n=2^r-1$ and dimension $k = n-r$.
1078
1079 Redundancy of the code: $r=n-k$, the number of check symbols in each codeword.
1080\end{remark}
1081
1082
1083\begin{ex}{8.1}
1084 \begin{enumerate}[i.]
1085 \item $r = 2$: $H = \begin{bmatrix}1 & 1 & 0\\ 1 & 0 & 1 \end{bmatrix}$
1086
1087 by Theorem \ref{7.6}, $G = [1\ 1\ \underbrace{1}_{I}]$
1088
1089 so $Ham(2, 2)$ is just the binary triple repetition code.
1090
1091 \item $r = 3$: a PCM for $Ham(3, 2)$ is
1092 $$H =
1093 \begin{bmatrix}
1094 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
1095 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
1096 1 & 0 & 1 & 0 & 1 & 0 & 1
1097 \end{bmatrix}$$
1098
1099 (have taken columns in the natural order of increasing binary numbers from 1 to 7)
1100
1101 $H$ in standard form: rearrange columns:
1102 $$H =
1103 \begin{bmatrix}
1104 0 & 1 & 1 & 1 & 1 & 0 & 0 \\
1105 1 & 0 & 1 & 1 & 0 & 1 & 0 \\
1106 1 & 1 & 0 & 1 & 0 & 0 & 1
1107 \end{bmatrix}$$
1108
1109 by Theorem \ref{7.6}, a generator matrix for $Ham(3, 2)$ is
1110 $$
1111 G =
1112 \begin{bmatrix}
1113 1 & 0 & 0 & 0 & 0 & 1 & 1 \\
1114 0 & 1 & 0 & 0 & 1 & 0 & 1 \\
1115 0 & 0 & 1 & 0 & 1 & 1 & 0 \\
1116 0 & 0 & 0 & 1 & 1 & 1 & 1
1117 \end{bmatrix}
1118 $$
1119 \end{enumerate}
1120\end{ex}
1121
1122
1123\begin{thm}{8.2}
1124 the binary Hamming code $Ham(r,2)$, for $r \geq 2$,
1125 \begin{enumerate}
1126 \item is a $[2^r -1, 2^r-1-r]$-code
1127 \item has minimum distance $3$ (hence is single-error-correcting)
1128 \item is a \emph{perfect code}
1129 \end{enumerate}
1130\end{thm}
1131
1132\vspace{0.5cm}
1133
1134\begin{lemma}{}[Decoding with a binary Hamming code]
1135$Ham(r,2)$ is a perfect single-error-correcting code $\Longrightarrow$ the coset leader are precisely the $2^r ~~(=n+1)$ vectors of $V(n, 2)$ of weight $\leq 1$.
1136
1137Let $j$-th column of H be the binary representation of $j$. Decoding algorithm:
1138\begin{enumerate}
1139 \item receive vector $y$, calculate its syndrome: $S(y)=yH^T$
1140 \item if $S(y)=0$, assume $y=c$ (original sent codeword)
1141 \item if $S(y) \neq 0$, assuming a single error, $S(y)$ gives the binary representation of the error position, and the error can be corrected.
1142\end{enumerate}
1143\end{lemma}
1144
1145
1146\begin{eg}{}
1147$H =
1148\begin{bmatrix}
11490 & 0 & 0 & 1 & 1 & 1 & 1 \\
11500 & 1 & 1 & 0 & 0 & 1 & 1 \\
11511 & 0 & 1 & 0 & 1 & 0 & 1
1152\end{bmatrix}$,
1153if $y = 1101011$ then
1154
1155$$S(y) = y \cdot H^T = 110$$
1156
1157$\Longrightarrow~6$-th position, and so we decode $y$ as $1101001$
1158\end{eg}
1159
1160\subsection{Extended binary Hamming codes}
1161$\hat{Ham}(r,2)$, obtained from $Ham(r,2)$ by adding an overall parity-check.
1162
1163Not ideal for complete decoding, but good for incomplete decoding (correct any single error and detect any double error).
1164
1165\vspace{1.0cm}
1166
1167Let $H$ be a PCM for $Ham(r,2)$. A PCM $\hat{H}$ for $\hat{Ham}(r,2)$:
1168$$\hat{H}=
1169\begin{bmatrix}
1170 & & & 0 \\
1171 & H & & \vdots\\
1172 & & & 0 \\
1173 1 & \cdots & 1 & 1
1174\end{bmatrix}
1175$$
1176
1177If $H$ is taken with columns in increasing order of binary numbers, we have a neat incomplete decoding algorithm:
1178\begin{eg}{8.3}
1179 $r=3,~ \hat{Ham}(3,2)$. Received $y$, $S(y)=y \hat{H}^T = (s_1, s_2, s_3, s_4)$
1180 \begin{enumerate}[i.]
1181 \item if $s_4=0$ and $(s_1,s_2,s_3)=0$: assume no errors
1182 \item if $s_4=0$ and $(s_1,s_2,s_3) \neq 0$: assume $\geq 2$ errors and ask retransmission
1183 \item if $s_4=1$ and $(s_1,s_2,s_3)=0$: assume $1$ error in the last position
1184 \item if $s_4=1$ and $(s_1,s_2,s_3) \neq 0$: assume $1$ error in the $j$-th position, where $j$ is the number binary-represented by $(s_1,s_2,s_3)$
1185 \end{enumerate}
1186\end{eg}
1187
1188\vspace{1.0cm}
1189
1190\begin{thm}{8.4} \label{8.4}
1191 suppose $C$ a linear $[n,k]$-code over $GF(q)$ with PCM $H$. Minimum distance of $C$ is $d$ iff any $d-1$ columns of $H$ are linearly independent but some $d$ columns are linearly dependent.
1192\end{thm}
1193\begin{proof}
1194 by \ref{5.2}, min. distance of $C$ (ie. $d(C)$) = smallest of the weights of the non-zero codewords.
1195
1196 Let $x=x_1 x_2 \ldots x_n \in \Vnq$, then
1197 \begin{align*}
1198 x \in C &\Longleftrightarrow xH^T=0\\
1199 &\Longleftrightarrow x_1 H_1 + x_2 H_2 + \ldots + x_n H_n = 0
1200 \end{align*}
1201 where $H_i$ denote the columns of $H$.
1202
1203 $\Longrightarrow$ each codeeword $x$ of weight $d$ corresponds with a set of $d$ linearly dependent columns of $H$.
1204
1205 On the other hand, if $\exists$ a set of $d-1$ lin.dependent columns of $H$, say $H_{i_1}, H_{i_2}, \ldots, H_{i_{d-1}}$, then $\exists~ x_{i_1}, \ldots, x_{i_{d-1}}$ scalars, not all zero, such that
1206 $$x_{i_1} H_{i_1} + x_{i_2} H_{i_2} + \ldots + x_{i_{d-1}} H_{i_{d-1}}= 0$$
1207
1208 But then, the vector
1209 $$x = (0 \ldots 0 x_{i_1} 0 \ldots x_{i_2} 0 \ldots 0 x_{i_{d-1}} 0 \ldots 0)$$
1210 having $x_{i_j}$ in the $j$-th position for $j \in [d-1]$, would satisfy $x H^T=0$, and so would be a non-zero codeword of weight $<d$.
1211\end{proof}
1212
1213\subsection{q-ary Hamming codes}
1214For $C$ a inear code with $d(C)=3$ (min.dist), any $2$ columns of a PCM $H$ must be linearly independent
1215
1216$\Longrightarrow$ columns of $H$ must be non-zero, and no column can be a scalar multiple of another
1217
1218Any $0 \neq v \in V(r,q)$ vector has $q-1$ non-zero scalar multiples, forming the set
1219$$\{ \lambda v ~|~ \lambda \in GF(q), \lambda \neq 0 \}$$
1220
1221$\longrightarrow$ the $q^r -1$ non-zero vectors of $V(r,q)$ may be partitioned into $\frac{q^r-1}{q-1}$ such sets, called \emph{classes}.
1222
1223$\longrightarrow$ two vectors are scalar multiples of each other if they are in the same class
1224
1225By choosing one vector from each class, obtain a set of $\frac{q^r-1}{q-1}$ vectors, where not two are linearly dependent.\\
1226\hspace*{2em} By Theorem \ref{8.4}, taking these as columns of $h$ gives a PCM for a
1227$$\left[\frac{q^r-1}{q-1}, \frac{q^r-1}{(q-1)-r}, 3 \right] \text{-code}$$
1228
1229\hspace*{2em} $\Longrightarrow$ called \emph{q-ary Hamming code}, $Ham(r, q)$.
1230
1231$\longrightarrow$ PCM is unique up to permutation of columns\\
1232\hspace*{2em}$\Longrightarrow$ Hamming codes are linear codes
1233
1234
1235\vspace{0.5cm}
1236
1237\begin{thm}{8.6}
1238 $Ham(r, q)$ is a perfect single-error-correcting code.
1239\end{thm}
1240\begin{proof}
1241 $Ham(r, q)$ is constructed to be a $(n, M, 3)$-code, with $n=\frac{q^r-1}{q-1}$ and $M=q^{n-r}$.
1242
1243 With $t=1$, the LHS of the sphere-packing bound becomes
1244 $$q^{n-r} \cdot (1 + n(q-1)) = q^{n-r} \cdot (1 + q^r -1) = q^n$$
1245 which is the RHS, so $Ham(r, q)$ is a perfect code.
1246\end{proof}
1247
1248\paragraph{Decoding q-ary Hamming code}
1249Since Ham is perfect single-error correcting code, the coset leaders, other than $0$, are the vectors of weight $1$.
1250
1251Syndrome of such coset leader:
1252$$S(0 \ldots 0 ~b~ 0 \ldots 0) = (0 \ldots 0 ~b~ 0 \ldots 0) \cdot H^T = b \cdot H_j^T$$
1253where $H_j$ is the $j$-th column of $H$, and $b$ is at the $j$-th position of $y$.
1254
1255Decode:
1256\begin{itemize}
1257 \item[-] given received $y$, calculate $S(y)=y H^T$
1258 \item[-] if $S(y)=0$, assume no errors
1259 \item[-] if $S(y)\neq 0$, then $S(y) = b \cdot H_j^T$ for some $b$ and $j$\\
1260 correct by: subtract $b$ from the $j$-th entry of $y$.
1261\end{itemize}
1262
1263Example:
1264$$q=5,~ H= \begin{bmatrix}0 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 2 & 3 & 4 \end{bmatrix},~ y=203031$$
1265
1266Then,
1267\begin{align*}
1268 S(y) = y \cdot H^T &= 2 \cdot H_1^T + 3 \cdot H_3^T + 3 \cdot H_5^T + 1 \cdot H_6^T\\
1269 &= 2 \cdot [0~1] + 3 \cdot [1~1] + 3 \cdot [1~3] + 1 \cdot [1~4]\\
1270 &= [0~2] + [3~3] + [3~9] + [1~4]\\
1271 &= [7~8] = [2~3] = \underbrace{2}_{b} \cdot \underbrace{[1~4]}_{H_6^T} \pmod{5}
1272\end{align*}
1273
1274$\Longrightarrow$ error is in position $6$-th, with magnitude $b=2$\\
1275\hspace*{2em} $\Longrightarrow$ subtract $b$ from the $j$-th entry of $y$: $1-2 \pmod{5} = -1 \pmod{5} = 4$,\\
1276\hspace*{2em} therefore $y'=203034$.
1277
1278\section{MLCT - Main Linear Coding Theory problem}
1279A good $(n,M,d)$-code has
1280\begin{itemize}
1281 \item small $n$, for fast transmission of messages
1282 \item large $M$, to enable transmission of a wide variety of messages
1283 \item large $d$, to correct many errors
1284\end{itemize}
1285
1286Denote by $A_q(n, d)$ the largest $M$ such that $\exists$ a $q$-ary $(n, M, d)$-code.
1287
1288\begin{thm}{2.7}
1289 Suppose $d$ is odd. Then a binary $(n, M, d)$-code exists iff a binary $(n + 1, M, d + 1)$-code exists.
1290\end{thm}
1291\begin{proof}
1292 % TODO
1293\end{proof}
1294
1295\begin{cor}{2.8}
1296 If $d$ is odd, then $A_2(n+1, d+1)=A_2(n, d)$.
1297
1298 Equivalently, if $d$ is even, then $A_2(n, d) = A_2(n-1,d-1)$.
1299\end{cor}
1300
1301% TODO Lemma 2.10
1302
1303
1304\begin{defn}{}[Sphere]
1305 $\forall~ u \in F_q^n$ (vector) and any integer $r \geq 0$, the \emph{sphere} of radius $r$ and centre $u$, denoted $S(u, r)$, is the set
1306 $$\{ v \in F_q^n ~|~ d(u, v) \leq r \}$$
1307\end{defn}
1308
1309\begin{thm}{1.9 \& 2.12}
1310 a code $C$ can
1311 \begin{enumerate}[i.]
1312 \item detect up to $s$ errors in any codeword if $d(C) \geq s+1$
1313
1314 \item correct up to $t$ errors in any codeword if $d(C) \geq 2t + 1$
1315
1316 This is, the spheres of radius $t$ centered on the codewords of $C$ are disjoint (ie. have no overlap).
1317
1318 So, if $\leq t$ errors occur, then the received vector $y$ may be different from the sent codeword $x$, hence being different from the centre of the sphere $S(x, t)$, but can not 'escape' from the sphere, so is 'drawn back' to $x$ by nearest neighbour decoding.
1319 \end{enumerate}
1320
1321
1322\begin{center}
1323\begin{tikzpicture}[scale=0.8]
1324 \def\r{1.5}
1325 \def\eps{0.2}
1326
1327 % left: overlapping spheres
1328 \begin{scope}[shift={(-5,0)}]
1329 \coordinate (A) at (0,0);
1330 \coordinate (B) at (2,0);
1331
1332 \draw (A) circle (\r);
1333 \draw (B) circle (\r);
1334
1335 \fill (A) circle (2pt);
1336 \fill (B) circle (2pt);
1337
1338 \node[below] at (A) {$x$};
1339 \node[below] at (B) {$x'$};
1340
1341 \draw (A) -- ($(A)+(0,\r)$);
1342 \node at ($(A)+(0.2,0.7*\r)$) {$t$};
1343
1344 \draw (B) -- ($(B)+(-0.5*\r,0.866*\r)$);
1345 \node at ($(B)+(-0.3*\r,0.5*\r)$) {$t$};
1346
1347 % point y
1348 \fill (1,0.3) circle (2pt);
1349 \node[right] at (1,0.3) {$y$};
1350 \end{scope}
1351
1352
1353 % right: disjoint spheres
1354 \begin{scope}[shift={(3,0)}]
1355 \coordinate (C) at (0,0);
1356 \coordinate (D) at ({2*\r+\eps},0);
1357 \coordinate (E) at ({(\r+\eps/2)}, {sqrt(3)*(\r+\eps/2)});
1358
1359 \draw (C) circle (\r);
1360 \draw (D) circle (\r);
1361 \draw (E) circle (\r);
1362
1363 \fill (C) circle (2pt);
1364 \fill (D) circle (2pt);
1365 \fill (E) circle (2pt);
1366
1367 \node[below] at (C) {$x$};
1368 \node[below] at (D) {$x'$};
1369 \node[above] at (E) {$x''$};
1370
1371 \draw (C) -- ($(C)+(0,\r)$);
1372 \node at ($(C)+(0.2,0.7*\r)$) {$t$};
1373
1374 \draw (D) -- ($(D)+(-\r,0)$);
1375 \node at ($(D)+(-0.6*\r,0.3)$) {$t$};
1376
1377 \draw (E) -- ($(E)+(0,-\r)$);
1378 \node at ($(E)+(0.2,-0.7*\r)$) {$t$};
1379
1380 % point y
1381 \fill (0.5,0.3) circle (2pt);
1382 \node[right] at (0.5,0.3) {$y$};
1383 \end{scope}
1384
1385\end{tikzpicture}
1386\end{center}
1387
1388\end{thm}
1389
1390
1391\begin{defn}{}[Perfect codes]
1392 A code which achieves the sphere-packing bound is called a \emph{perfect code}.
1393 Thus, for a perfect $t$-error-correcting code, the $M$ spheres of radius $t$
1394 centred on codewords ‘fill’ the whole space $F_q^n$ without overlapping.
1395
1396 In other words, every vector in $F_q^n$ is at distance $\leq t$ from exactly one codeword.
1397\end{defn}
1398
1399\vspace{1.0cm}
1400
1401\begin{thm}{}[MLCT problem (Version 1)]
1402 For given length $n$, find the maximum dimension $k$ such that $\exists$ an $[n, k, d]$-code over $GF(q)$. (Then, for this $k, B_q(n, d) = q^k)$.
1403\end{thm}
1404
1405\begin{remark}{}
1406 \emph{redundancy} $r$ of an $[n, k, d]$-code is just $r=n-k$ (the number of check symbols in a codeword).
1407\end{remark}
1408
1409\begin{thm}{}[MLCT problem (Version 2)]
1410 For given redundancy $r$, find the maximum length $n$ such that $\exists$ an $[n, n-r, d]$-code over $GF(q)$.
1411\end{thm}
1412
1413
1414\begin{defn}{}[$(n,s)$-set]
1415 a $(n, s)$-set in $V(r,q)$ is a set of $n$ vectors in $V(r, q)$ with the property that any $s$ of them are linearly independent.
1416
1417 Denote $max_s(r,q)$ the largest value of $n$ for which $\exists$ a $(n,s)$-set
1418 in $V(r,q)$.\\
1419 ie.
1420 \begin{itemize}
1421 \item $(n,s)$-set: $n$ vectors with $s$ of them lin. independent
1422 \item $max_s(r,q)$: max $n$ for which $\exists~ (n,s)$-set
1423 \end{itemize}
1424\end{defn}
1425
1426\begin{defn}{}[Packing problem]
1427 The \emph{packing problem} for $V(r,q)$ is that of determining the values of $max_s(r, q)$ and the optimal $(n,s)$-sets.
1428\end{defn}
1429
1430\begin{thm}{14.1}
1431There exists an $[n,n-r,d]$-code over $GF(q)$ iff $\exists$ an $(n, d-1)$-set in $V(r, q)$.
1432\end{thm}
1433\begin{proof}
1434 let $C$ a $[n, n-r, d]$-code over $GF(q)$ with PCM $H$. Then by Theorem \ref{8.4}, the columns of $H$ form a $(n, d-1)$-set in $V(r, q)$.
1435
1436 On the other hand, let $K$ a $(n, d-1)$-set in $V(r, q)$. If we form a $r \times n$ matrix $H$ with the vectors of $K$ as its columns, by Theorem \ref{8.4}, $H$ is the PCM of a $[n, n-r]$-code whose minimum distance is at least $d$.
1437\end{proof}
1438
1439\begin{cor}{14.2}
1440 for given values $q, d, r$, the largest value of $n$ for which there exists a $[n, n-r, d]$-code over $GF(q)$ is $max_{d-1}(r, q)$.
1441\end{cor}
1442
1443$\Longrightarrow$ the MLCT problem (V2) is the same as the packing problem of finding $max_{d-1}(r, q)$.
1444
1445\subsection{The projective geometry PG(r-1,q)}
1446Let the vector space
1447$$V(r,q)= \{ (a_1, a_2, \ldots, a_r) ~|~ a_i \in GF(q) \}$$
1448
1449\begin{defn}{}[Projective Geometry]
1450 $PG(r-1, q)$
1451 \begin{itemize}
1452 \item \emph{points} are the one-dimensional subspaces of $V(r, q)$
1453 \item \emph{lines} are the two-dimensional subspaces of $V(r, q)$
1454 \end{itemize}
1455
1456 Each point $P \in PG(r-1, q)$, as a subspace of $V(r,q)$ of dimension $1$, is generated by a single non-zero vector.
1457
1458 So if $a=(a_1, a_2, \ldots, a_r) \in P$, then $P= \{ \lambda a ~|~ \lambda \in GF(q) \}$.
1459
1460 $\Longrightarrow$ for $a=(a_1, a_2, \ldots, a_r),~b=(b_1, b_2, \ldots, b_r) \in P$, then
1461 $$a=b ~\text{in}~ PG(r-1,q) ~\text{iff}~ a=\lambda b ~\text{in}~ V(r,q)$$
1462 for some non-zero scalar $\lambda$.
1463\end{defn}
1464
1465\begin{lemma}{14.6}
1466 in $PG(r-1,q)$,
1467 \begin{enumerate}
1468 \item number of points is $\frac{q^r-1}{q-1}$
1469 \item any two points lie on exactly one line
1470 \item each line contains exactly $q+1$ points
1471 \item each point lies on $\frac{q^{r-1} -1}{q-1}$ lines
1472 \end{enumerate}
1473\end{lemma}
1474\begin{proof}
1475 \begin{enumerate}
1476 \item number of points is $\frac{q^r-1}{q-1}$:\\
1477 since each of the $q^r-1$ nonzero vectors in $V(r,q)$ has $q-1$ nonzero scalar multiples, the number of points of $PG(r-1,q)$ is $\frac{q^r-1}{q-1}$
1478
1479 \item any two points lie on exactly one line:\\
1480 if $a,b$ distinct points of $PG(r-1,q)$, then the unique line through them consists of the points $\lambda a + \mu b$, where $\lambda,\mu$ are scalars not both zero.
1481
1482 \item each line contains exactly $q+1$ points:\\
1483 in (ii) there are $q^2-1$ choices for the pair $(\lambda, \mu)$, but we're identifying scalar multiples, so the number of distinct points on the line is
1484 $$\frac{q^2 -1}{q-1}=q+1$$
1485
1486 \item each point lies on $\frac{q^{r-1} -1}{q-1}$ lines:\\
1487 let $t$ be the number of lines on which a point $P$ lies. Let the set
1488 $$X=\{(Q,L) ~|~ Q ~\text{is a point}~ \neq P,~ L~\text{is a line containing both}~ P ~\text{and}~ Q \}$$
1489
1490 Count the members of $X$ in two ways:
1491
1492 for each of the $\frac{q^r -1}{q-1} -1$ choices of $Q$, $\exists !$ line containing $P$ and $Q$. Thus,
1493 $$|X|=\frac{q^r-1}{q-1} -1 = \frac{q^r-q}{q-1}$$
1494
1495 On the other hand, for each of the $t$ lines through $P$, there are (by (iii)) $q$ points $Q$ other than $P$ lying on $L$.
1496
1497 Thus, $|X|=tq$,
1498 $$\Longrightarrow tq = \frac{q^r-q}{q-1}, ~~~~ \Longrightarrow t=\frac{q^{r-1}-1}{q-1}$$
1499 \end{enumerate}
1500\end{proof}
1501
1502\begin{defn}{}[Projective plane]
1503 The $PG(2,q)$ is called the \emph{projective plane} over $GF(q)$.
1504\end{defn}
1505
1506\section{MDS Codes}
1507
1508\begin{thm}{15.1}
1509 a $[n, n-r, d]$-code satisfies $d \leq r+1$.
1510\end{thm}
1511\begin{proof}
1512 let $C$ a $[n, n-r, d]$-code, let $G=[ I_{n-r} ~|~ A]$ be a standard form GM of $C$.
1513
1514 Since $A$ has $r$ columns, the codewords whicch are rows of $G$ have weight $\leq r+1$, ie. $w(C) \leq r+1$.
1515
1516 The result follows from Theorem \ref{5.2},
1517 \begin{align*}
1518 &\Longrightarrow~ w(C)=d(C)\\
1519 &\Longrightarrow~ d(C) \leq r+1.
1520 \end{align*}
1521\end{proof}
1522
1523\begin{defn}{}[MDS]
1524 a $[n, n-r, r+1]$-code,\\
1525 \hspace*{2em}ie. a linear cocde of redundancy $r$ whose min. distance is $r+1$,\\
1526 is called a \emph{maximum distance separable code}, MDS.
1527
1528 $\longrightarrow$ by Theorem \ref{14.1}, max length of a MDS code over $GF(q)$ is $max_r(r,q)$, the largest size of a $(n,r)$-set in $V(r,q)$.
1529\end{defn}
1530
1531\begin{conj}{15.2}
1532 if $2 \leq r \leq q$, then $max_r(r,q)=q+1$
1533
1534 (except $max_3(3,q)=max_{q-1}(q-1,q)=q+2$ if $q=2^h$)
1535\end{conj}
1536
1537\begin{thm}{15.3}
1538 if $r\geq q$, then $max_r(r,q)=r+1$. Any MDS code of redundancy $r\geq q$ is equivalent to a repetition code of length $r+1$.
1539\end{thm}
1540\begin{proof}
1541 repetition code of length $r+1$: a $[r+1, 1, r+1]$-code with GM $[1~1~\cdots~1]$.
1542
1543 Hence $max_r(r,q) \geq r+1$.
1544
1545 Also, any $[r+1, 1, r+1]$-code is equivalent to a repetition code.
1546
1547 Suppose $r \geq q$ and by contradiction that $max_r(r,q) \geq r+2$.
1548
1549 Then, $\exists$ a $[r+2, 2, r+1]$-code $C$ over $GF(q)$.
1550
1551 $\longrightarrow~C$ must be equivalent to a code having GM:
1552 $$G=
1553 \begin{bmatrix}
1554 1 & 0 & 1 & 1 & \ldots & 1\\
1555 0 & 1 & a_1 & a_2 & \ldots & a_r
1556 \end{bmatrix}
1557 $$
1558
1559 in order that any linear combination of the rows of $G$ has weight at least $r+1$ with $0 \neq a_i \in GF(q)$.
1560
1561 This implies $r \leq q-1$, contradiction.
1562\end{proof}
1563
1564\begin{remark}{}
1565 the only binary MDS codes are\\
1566 $V(n,2)$, the even weighted codes $E_n$, and repetition codes.
1567\end{remark}
1568
1569\begin{thm}{15.4}
1570 let $2 \leq r \leq q$, let $a_1, a_2, \ldots, a_{q-1} \in GF(q)$ nonzero.
1571
1572 Then,
1573 $$
1574 H =
1575 \begin{bmatrix}
1576 1 & 1 & \ldots & 1 & 1 & 0\\
1577 a_1 & a_2 & \ldots & a_{q-1} & 1 & 0\\
1578 a_1^2 & a_2^2 & \ldots & a_{q-1}^2 & 1 & 0\\
1579 & & & & \vdots & \vdots\\
1580 \vdots & \vdots & & \vdots & 0 & 0\\
1581 a_1^{r-1} & a_2^{r-1} & \ldots & a_{q-1}^{r-1} & 0 & 1
1582 \end{bmatrix}
1583 $$
1584
1585 is the PCM of a MDS $[q+1, q+1-r, r+1]$-code.
1586
1587 Equivalently, the columns of $H$ form a $(q+1)$-arc in $PG(r-1, q)$.
1588\end{thm}
1589\begin{proof}
1590 the determinant of a matrix formed by any $r$ columns of $H$ is equal to the determinant of a Vandermonde matrix, and so is non-zero (see a proof of this at section \ref{sec:vandermondedet}).
1591 Thus any $r$ columns of $H$ are linearly independent.
1592\end{proof}
1593
1594\begin{cor}{15.7}
1595 The dual code of a MDS code is also MDS.
1596\end{cor}
1597\begin{cor}{15.8}
1598 $\exists$ a MDS $[n,k]$-code over $GF(q)$ iff $\exists$ a MDS $[n, n-k]$-code over $GF(q)$.
1599\end{cor}
1600
1601
1602\subsection{Vandermonde determinant} \label{sec:vandermondedet}
1603
1604This section contains a simple proof of the Vandermonde matrix determinant. The proof was found in \cite{vanddetproof}, here it is written with small modifications and expanded. A different proof can be found in \cite{vanddetproof2}.
1605
1606\begin{lemma}{}[Vandermonde determinant]
1607$$
1608\det~V(x_1, ..., x_n) = \det
1609\begin{pmatrix}
1610 1 & x_1 & x_1^2 & \ldots & x_1^{n-1} \\
1611 1 & x_2 & x_2^2 & \ldots & x_2^{n-1} \\
1612 1 & x_3 & x_3^2 & \ldots & x_3^{n-1} \\
1613 \vdots & \vdots & \vdots & & \vdots\\
1614 1 & x_n & x_n^2 & \ldots & x_n^{n-1} \\
1615\end{pmatrix}
1616= \prod_{j < i} (x_i - x_j)
1617$$
1618\end{lemma}
1619
1620\begin{proof}
1621
1622The equation is true for $n = 2$, as we have:
1623
1624$$
1625\det~V(x_1, x_2) = \det
1626\begin{pmatrix}
1627 1 & x_1\\
1628 1 & x_2
1629\end{pmatrix}
1630= x_2 - x_1
1631$$
1632
1633We now assume that $n \ge 3$. Starting with column $n$ and ending at column $2$, we successively apply the following operation: subtract $x_1$ times column $i-1$ from column $i$. The determinant remains the same and the resulting matrix is:
1634
1635$$
1636= \det
1637\begin{pmatrix}
1638 1 & x_1-(x_1 \cdot 1) & x_1^2 - (x_1 \cdot x_1) & \ldots & x_1^{n-1} - (x_1 \cdot x_1^{n-2}) \\
1639 1 & x_2-(x_1 \cdot 1) & x_2^2 - (x_1 \cdot x_2) & \ldots & x_2^{n-1} - (x_1 \cdot x_2^{n-2}) \\
1640 1 & x_3-(x_1 \cdot 1) & x_3^2 - (x_1 \cdot x_3) & \ldots & x_3^{n-1} - (x_1 \cdot x_3^{n-2}) \\
1641 \vdots & \vdots & \vdots & & \vdots\\
1642 1 & x_n-(x_1 \cdot 1) & x_n^2 - (x_1 \cdot x_n) & \ldots & x_n^{n-1} - (x_1 \cdot x_n^{n-2}) \\
1643\end{pmatrix}
1644$$
1645$$
1646= \det
1647\begin{pmatrix}
1648 1 & 0 & 0 & \ldots & 0 \\
1649 1 & (x_2 - x_1) & x_2(x_2 - x_1) & \ldots & x_2^{n-2}(x_2 - x_1) \\
1650 1 & (x_3 - x_1) & x_3(x_3 - x_1) & \ldots & x_3^{n-2}(x_3 - x_1) \\
1651 \vdots & \vdots & \vdots & & \vdots \\
1652 1 & (x_n - x_1) & x_n(x_n - x_1) & \ldots & x_n^{n-2}(x_n - x_1) \\
1653\end{pmatrix}
1654$$
1655
1656Applying the Laplace expansion along the first row and factoring out the scalar multiples $(x_i - x_1)$ in each column, we obtain:
1657
1658$$
1659= \det
1660\begin{pmatrix}
1661 x_2-x_1 & x_2^2 - x_1 x_2 & x_2^3 - x_1 x_2^2 & \ldots & x_2^{n-1} - x_1 x_2^{n-2} \\
1662 x_3-x_1 & x_3^2 - x_1 x_3 & x_3^3 - x_1 x_3^2 & \ldots & x_3^{n-1} - x_1 x_3^{n-2} \\
1663 \vdots & \vdots & \vdots & & \vdots\\
1664 x_n-x_1 & x_n^2 - x_1 x_n & x_n^3 - x_1 x_n^2 & \ldots & x_n^{n-1} - x_1 x_n^{n-2} \\
1665\end{pmatrix}
1666$$
1667
1668in each row, factor out $(x_i - x_1)$
1669
1670$$
1671= \det
1672\begin{pmatrix}
1673 1(x_2-x_1) & x_2(x_2 - x_1) & x_2^2(x_2 - x_1) & \ldots & x_2^{n-2}(x_2 - x_1) \\
1674 1(x_3-x_1) & x_3(x_3 - x_1) & x_3^2(x_3 - x_1) & \ldots & x_3^{n-2}(x_3 - x_1) \\
1675 \vdots & \vdots & \vdots & & \vdots\\
1676 1(x_n-x_1) & x_n(x_n - x_1) & x_n^2(x_n - x_1) & \ldots & x_n^{n-2}(x_n - x_1) \\
1677\end{pmatrix}
1678$$
1679$$
1680= \prod_{2 \leq i \leq n} (x_i - x_1) ~~\det
1681\begin{pmatrix}
1682 1 & x_2 & x_2^2 & \ldots & x_2^{n-2} \\
1683 1 & x_3 & x_3^2 & \ldots & x_3^{n-2} \\
1684 \vdots & \vdots & \vdots & & \vdots\\
1685 1 & x_n & x_n^2 & \ldots & x_n^{n-2} \\
1686\end{pmatrix}
1687$$
1688
1689now, by induction
1690
1691$$
1692= \prod_{i=2}^n (x_i - x_1) ~~\cdot \prod_{2 \leq j < i \leq n} (x_i - x_j) ~~= \prod_{1 \leq j < i \leq n} (x_i - x_j)
1693$$
1694\end{proof}
1695
1696\bibliographystyle{unsrt}
1697\bibliography{algebraic-coding-theory-notes.bib}
1698
1699\end{document}