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