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