math/algebraic-coding-theory-notes.tex
algebraic-coding-theory-notes.texRaw
1\documentclass{article}
2\usepackage[utf8]{inputenc}
3\usepackage{amsfonts}
4% \usepackage{yfonts} % WIP
5\usepackage{amsthm}
6\usepackage{amsmath}
7\usepackage{mathrsfs}
8\usepackage{enumerate}
9\usepackage{hyperref}
10\usepackage{amssymb}
11
12\usepackage{tikz} % diagram
13\usetikzlibrary{calc}
14
15\begin{filecontents}[overwrite]{algebraic-coding-theory-notes.bib}
16@misc{hill,
17 author = {Raymond Hill},
18 title = {{A First Course in Coding Theory}},
19 year = {1986}
20}
21@misc{lint,
22 author = {J.H. van Lint},
23 title = {{Introduction to Coding Theory}},
24 year = {1981}
25}
26
27@misc{vanddetproof,
28 title = {Vandermonde determinant proof},
29 author = {Pedro Tamaroff},
30 howpublished = "\url{https://math.stackexchange.com/questions/525334/vandermonde-determinant-by-induction}",
31}
32
33@misc{vanddetproof2,
34 title = {Abstract Algebra, Theory and Applications. \emph{sec.22.2}},
35 author = {Thomas W. Judson},
36}
37
38@misc{commutativealgebranotes,
39 title = {Commutative Algebra Notes},
40 howpublished = "\url{https://github.com/arnaucube/math/blob/master/commutative-algebra-notes.pdf}",
41}
42\end{filecontents}
43\nocite{*}
44
45
46\theoremstyle{definition}
47
48\newtheorem{innerdefn}{Definition}
49\newenvironment{defn}[1]
50{\renewcommand\theinnerdefn{#1}\innerdefn}
51{\endinnerdefn}
52
53\newtheorem{innerthm}{Theorem}
54\newenvironment{thm}[1]
55{\renewcommand\theinnerthm{#1}\innerthm}
56{\endinnerthm}
57
58\newtheorem{innerlemma}{Lemma}
59\newenvironment{lemma}[1]
60{\renewcommand\theinnerlemma{#1}\innerlemma}
61{\endinnerlemma}
62
63\newtheorem{innerprop}{Proposition}
64\newenvironment{prop}[1]
65{\renewcommand\theinnerprop{#1}\innerprop}
66{\endinnerprop}
67
68\newtheorem{innercor}{Corollary}
69\newenvironment{cor}[1]
70{\renewcommand\theinnercor{#1}\innercor}
71{\endinnercor}
72
73\newtheorem{innereg}{Example}
74\newenvironment{eg}[1]
75{\renewcommand\theinnereg{#1}\innereg}
76{\endinnereg}
77
78\newtheorem{innerex}{Exercise}
79\newenvironment{ex}[1]
80{\renewcommand\theinnerex{#1}\innerex}
81{\endinnerex}
82
83\newtheorem{innerrem}{Remark}
84\newenvironment{remark}[1]
85{\renewcommand\theinnerrem{#1}\innerrem}
86{\endinnerrem}
87
88\newtheorem{innerintu}{Intuition}
89\newenvironment{intuition}[1]
90{\renewcommand\theinnerintu{#1}\innerintu}
91{\endinnerintu}
92
93\newtheorem{innerconj}{Conjecture}
94\newenvironment{conj}[1]
95{\renewcommand\theinnerconj{#1}\innerconj}
96{\endinnerconj}
97
98% custom shortcuts
99\newcommand{\Vnq}{V(n, q)}
100
101\title{Algebraic Coding Theory}
102\author{arnaucube}
103\date{2026}
104
105\begin{document}
106
107\maketitle
108
109\begin{abstract}
110 Notes taken while studying Algebraic Coding Theory, mostly from Hill's book \cite{hill} and Lint's book \cite{lint}.
111
112 Usually while reading books and papers I take handwritten notes in a notebook, this document contains some of them re-written to $LaTeX$.
113
114 The proofs may slightly differ from the ones from the books, since I try to extend them for a deeper understanding.
115\end{abstract}
116
117\tableofcontents
118
119
120\section{Vector spaces over finite fields, quick recap}
121Let $q$ be a prime power.
122
123$\Vnq$: set $GF(q)^n$ of all ordered $n$-tuples over $GF(q)$. $\Vnq$ is a
124vector space.
125
126A 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
127$$a_1 v_1 + a_2 v_2 + \ldots + a_r v_r = 0$$
128
129They are \emph{linear independent} if
130$$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$$
131
132Let $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$.
133
134A generating set of $C$ which is also linearly independent is called a \emph{basis} of $C$.
135
136\begin{thm}{4.3}
137 Suppose $\{v_1, v_2, \ldots, v_k\}$ is a basis of a subspace $C$ of $\Vnq$. Then
138 \begin{enumerate}[i.]
139 \item every vector of $C$ can be expressed uniquely as a linear combination of the basis vectors.
140 \item $C$ contains exactly $q^k$ vectors.
141 \end{enumerate}
142\end{thm}
143\begin{proof}
144 \begin{enumerate}[i.]
145\item suppose vector $x \in C$ such that
146$$x = a_1 v_1 + a_2 v_2 + \cdots + a_k v_k$$
147$$x = b_1 v_1 + b_2 v_2 + \cdots + b_k v_k .$$
148
149then
150$$(a_1-b_1)v_1 + (a_2-b_2)v_2 + \cdots + (a_k-b_k)v_k = 0 .$$
151
152But the set $\{v_1, v_2, \ldots, v_k\}$ is linearly independent, and so
153$$a_i - b_i = 0 \quad \text{for } i = 1,2,\ldots,k,$$
154i.e.,
155$$a_i = b_i \quad \text{for } i = 1,2,\ldots,k.$$
156
157\item By (i), the $q^k$ vectors
158$$\sum_{i=1}^{k} a_i v_i \qquad (a_i \in \mathrm{GF}(q))$$
159are precisely the distinct vectors of $C$.
160\end{enumerate}
161\end{proof}
162
163\vspace{1.0cm}
164
165\section{Linear codes}
166The theorems of this section are from \cite{hill} and follow the original enumeration of the book.
167
168Note about notation:\\
169A $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.
170
171\subsection{Some definitions}
172Let $q$ be a prime power. View $(F_q)^n$ as the vector space $\Vnq$.
173
174\begin{defn}{}[Linear code over GF(q)]
175 A \emph{linear code over $GF(q)$} is a subspace of $\Vnq$, with $n \geq 0$.
176\end{defn}
177
178Thus $C \subseteq \Vnq$ is a linear code iff
179\begin{enumerate}[i.]
180 \item $u+v \in C ~~ \forall u,v \in C$
181 \item $au \in C ~~ \forall u \in C,~ a \in GF(q)$
182\end{enumerate}
183
184If $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).
185
186\begin{defn}{}[Weight]
187 Weight, $w(x)$, of a vector $x \in \Vnq$ is the number of non-zero entries of $x$.
188\end{defn}
189
190\begin{lemma}{5.1}\label {h.5.1}
191 if $x,y \in \Vnq$, then $d(x,y)=w(x-y)$.
192\end{lemma}
193\begin{proof}
194 the vector $x-y$ has non-zero entries in preceisely those places where $x$ and $y$ differ.
195\end{proof}
196
197\begin{thm}{5.2} \label{5.2}
198 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)$.
199\end{thm}
200\begin{proof}
201 $\exists~ x,y \in C$ s.th. $d(C)=d(x,y)$.
202
203 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$).
204
205 On the other hand, for $x \in C$,\\
206 $w(C)=w(x)=d(x,0) \geq d(C)$, since $0 \in C$.
207
208 Hence, $d(C) \geq w(C)$ and $w(C) \geq d(C) ~~\Longrightarrow~ d(C)=w(C)$.
209\end{proof}
210
211
212\begin{defn}{}[Generator matrix (GM)]
213 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.
214\end{defn}
215
216\subsection{Equivalence}
217
218\begin{thm}{5.4}
219 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:
220 \begin{enumerate}
221 \item[R1.] permutation of the rows
222 \item[R2.] multiplication of a row by a non-zero scalar
223 \item[R3.] addition of a scalar multiple of one row to another
224 \item[C1.] permutation of the columns
225 \item[C2.] multiplication of any column by a non-zero scalar
226 \end{enumerate}
227\end{thm}
228
229\begin{thm}{5.5} \label{h.5.5}
230 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 ]$
231 where $I_k$ is the $k \times k$ identity matrix, and $A$ is a $k \times (n-k)$ matrix.
232\end{thm}
233
234\subsection{Encoding with a linear code}
235Let $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.
236
237Iddentify these messages with the $q^k$ tuples of $V(k,q)$.
238
239Encoding:\\
240msg vector: $u=u_1 u_2 \ldots u_k$; rows of $G$: $r_1 r_2 \ldots r_k$. Encode
241$$uG = \sum^k_{i=1} u_i r_i \in C$$
242ie. $uG$ is a codeword of $C$; a linear combination of the rows of the GM.
243
244Encoding function:
245\begin{align*}
246 V(k,q) &\longrightarrow C \subseteq \Vnq\\
247 u &\longmapsto uG
248\end{align*}
249
250If $G$ is in standard form (\ref{h.5.5}), $G= [I_k | A]$ with $A=[a_{ij}]$, then encoding $u$ is:
251$$x=uG = x_1x_2 \ldots x_k x_{k+1} \ldots x_n$$
252where
253\begin{align*}
254 &x_i=u_i ~~\text{for}~ 1 \leq i \leq k, ~\text{message digits}\\
255 &x_{k+i}=\sum^k_{j=1}~ a_ji u_j ~~\text{for}~ 1 \leq i \leq n-k, ~\text{check digits}\\
256\end{align*}
257
258the check digits add redundancy to gie protection against noise.
259
260\subsection{Decoding with a linear code}
261Codeword $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$.
262
263\subsubsection{Cosets}
264Cosets here are similar to the ones from typical group theory, just from another perspective.
265
266\begin{defn}{}[Coset]
267 Let $C$ a $[n,k]$-code over $GF(q)$ and $a \in \Vnq$.
268 Then the set $a + C = \{a+x | x\in C\}$ is called a \emph{coset} of $C$.
269\end{defn}
270
271\begin{defn}{}[Coset leader]
272 the vector having minimum weight in a coset is called the \emph{coset leader}.
273\end{defn}
274
275\begin{lemma}{6.3} \label{h.6.3}
276 Let $a+C$ a coset of $C$ and $b \in a+C$. Then $b+C=a+C$.
277\end{lemma}
278\begin{proof}
279 since $b \in a+C ~~\Longrightarrow~~ b=a+x$ for some $x \in C$.
280 If $b+y \in b+C$ then
281 $$b+y=(a+x)+y = a+(x+y) \in a+C$$
282
283 For the other direction, if $a+x \in a+C$ then
284 $$a+x=(b-x)+z = b+(z-x) \in b+C$$
285 hence $a+C \subseteq b+C$.
286
287 Therefore $b+C = a+C$.
288\end{proof}
289
290\begin{thm}{6.4}[Lagrange] \label{h.6.4}
291 suppose $C \subseteq \Vnq$ is a $[n,k]$-code over $GF(q)$. Then
292 \begin{enumerate}[i.]
293 \item evvery vector of $\Vnq$ is in some coset of $C$
294 \item every coset contains exactly $q^k$ vectors
295 \item two cosets either are disjoint or coincide (partial overlap is impossible)
296 \end{enumerate}
297\end{thm}
298\begin{proof}
299 \begin{enumerate}[i.]
300 \item if $a\in \Vnq$ then $a=a+0 \in a+C$
301 \item the map
302 \begin{align*}
303 C &\longrightarrow a+C ~\forall~ x \in C\\
304 x &\longmapsto a+x
305 \end{align*}
306 is a one-to-one map, hence $|a+C| = |C| = q^k$.
307 \item by contradiction, suppose cosets $a+C,~ b+C$ overlap. Then for some vector $v$,
308 $$v \in (a+C) \cap (b+C)$$
309 thus for some $x,y \in C$, $v=a+x=b+y$.
310
311 Hence $b=a+(x-y) \in a+C$, thus by Lemma \ref{h.6.3} we have $b+C=a+C$.
312 \end{enumerate}
313\end{proof}
314
315\begin{cor}{}
316 \ref{h.6.4} shows that $\Vnq$ is partitioned into disjoint cosets of $C$:
317 $$\Vnq = (0+C) \cup (a_1+C) \cup \ldots \cup (a_s +C)$$
318 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.
319\end{cor}
320
321\begin{eg}{6.5} \label{h.6.5}
322 Let $C$ be the binary $[4,2]$-code with generator matrix
323$$
324G = \begin{pmatrix}
3251 & 0 & 1 & 1 \\
3260 & 1 & 0 & 1
327\end{pmatrix}
328$$
329
330ie.
331$C = \{0000,\, 1011,\, 0101,\, 1110\}$.
332
333Then the cosets of $C$ are
334\begin{align*}
335 0000 + C &= C \text{ itself}\\
336 1000 + C &= \{1000,\, 0011,\, 1101,\, 0110\}\\
337 0100 + C &= \{0100,\, 1111,\, 0001,\, 1010\} = 0001+C\\
338 0010 + C &= \{0010,\, 1001,\, 0111,\, 1100\}
339\end{align*}
340
341by Lemma \ref{h.6.3}: $0001 \in 0100 + C$, thus $0001+C=0100+C$.
342\end{eg}
343
344\subsection{Probability of error correction (in binary linear codes)}
345To evaluate how good a code is, must calculate the \emph{probability} that a received vector will be decoded as the codeword which was sent.
346
347Let $p$ be the symbol error probability.
348
349Probability that the error vector is agiven vector of weight $i$ is $p^i (1-p){n-i}$.
350
351\begin{thm}{6.7}
352 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$.
353
354 Then the probability $P_{corr}(C)$ that a received vector decoded by means of a standard array is the codeword which was sent is
355 $$P_{corr}(C) = \sum_{i=0}^n \alpha_i \cdot p^i(1-p)^{n-i}$$
356\end{thm}
357
358\begin{eg}{6.8}
359 $[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
360 $$P_{corr}(C) = (1-p)^4 + 3 p(1-p)^3 = (1-p)^3 (1+2p)$$
361\end{eg}
362
363\begin{remark}{6.9}\label{remark.6.9}
364 if $d(C)=2t+1$ or $d(C)=2t+2$, then $C$ can correct any $t$ errors.
365
366 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$.
367\end{remark}
368
369\begin{defn}{}[Rate]
370 $[n, k]$-code $C$ uses $n$ symbols to send $k$ message symbols; it has \emph{rate} $R(C)=k/n$.
371
372 A good code will have a high rate.
373\end{defn}
374
375\begin{defn}{}[Capacity]
376 the \emph{capacity} $\mathscr{C}(p)$ of a binary symmetric channel with symbol error probability $p$ is
377 $$\mathscr{C}(p) = 1+ p \cdot \log_2{(p)} + (1-p) \cdot \log_2{(1-p)}$$
378\end{defn}
379
380
381\begin{thm}{6.12}[Shanon's theorem]
382 channel binary symmetric with symbol error probability $p$.
383
384 Let $R < \mathscr{C}(p)$.
385
386 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$.
387\end{thm}
388
389\begin{defn}{}[$P_{symb}$]
390 $P_{symb}$ denotes the average probability that a message symbol is in error after decoding.
391\end{defn}
392
393\begin{thm}{6.14}
394 let $C$ a binary [n,k]-code and let $A_i$ denote the number of codewords of $C$ of weight $i$.
395
396 Then, if $C$ is used for error detection, the probability of an incorrect message being undetected is
397 $$P_{undetec}(C) = \sum_{i=1}^n A_i \cdot p^i (1-p)^{n-i}$$
398\end{thm}
399
400\begin{eg}{6.15}
401 for the code of \ref{h.6.5},
402 $$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$$
403\end{eg}
404
405
406
407\vspace{0.5cm}
408
409\subsection{Exercises}
410\begin{ex}{5.1}
411 is the binary (11, 24, 5)-code linear?
412\end{ex}
413\begin{proof}
414 recall: a q-ary linear $[n,k,d]$-code is also a q-ary $(n, q^k, d)$-code, but
415 the opposite is not always true.
416
417 $\Longrightarrow~ (11, 24, 5)$-code to be linear it would mean that $24=q^k$.
418
419 Since it is binary, $q=2$. But $24 \neq 2^k$, so it can not be linear.
420\end{proof}
421
422\begin{ex}{5.2} \label{ex.5.2}
423 $E_n$ is the code of all even-weight vectors of $V(n,2)$, which is linear.
424 What are the parameters $[n, k, d]$ of $E_n$? Write a GM for $E_n$ in standard
425 form.
426\end{ex}
427\begin{proof}
428 $$E_n = \{ x \in V(n, 2) | w(x) ~\text{is even} \}$$
429
430 $\longrightarrow$ is the binary even-weight ode (the single parity-check code);\\
431 it's linear since
432 \begin{itemize}
433 \item the zero vector has even weight
434 \item over $GF(2)$, the sum of two even-weight vectors has even weight
435 \end{itemize}
436
437 Recall: $F_q^n \Longleftrightarrow \Vnq$, so $V(n, 2) \cong F_2^n$
438
439 $$\Longrightarrow~ E_n = \{ (x_1, \ldots, x_n) \in F_2^n | x_1 + \ldots + x_n = 0 \}$$
440
441 minimum distance is $2$, since
442 \begin{itemize}
443 \item no word of weight 1 is in $E_n$
444 \item words of weight 2 are in $E_n$
445 \end{itemize}
446
447 Therefore, parameters are $[n, n-1, 2]$
448
449 GM:
450 $$G=\left[ I_{n-1} | 1 \right]$$
451
452 which generates vectors of the form
453 $$(a_1, \ldots, a_{n-1}, a_1+\ldots+a_{n-1})$$
454\end{proof}
455
456\begin{ex}{5.5}
457 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.
458\end{ex}
459\begin{proof}
460 let $C_e,~ C_o$ be subsets of $C$ with even and odd weights respectively.
461
462 So that $C = C_e \cup C_o$ (disjoint union).
463
464 For binary vectors $x,y$:
465 $$w(x+y) = w(x) + w(y) \pmod 2$$
466
467 ie. over $F_2$, the parity of the weight is additive:
468 \begin{align*}
469 even + even &= even\\
470 even + odd &= odd\\
471 odd + odd &= even
472 \end{align*}
473
474 Now we have two possible cases:
475 \begin{itemize}
476 \item $C$ has no odd weighted codewords:\\
477 $C_0 = \emptyset,~ \forall x \in C$ $x$ is even weighted
478 \item $C$ has at least one odd-weighted codeword:\\
479 let $u \in C_o$, consider the map
480 \begin{align*}
481 \phi: C_e &\longrightarrow C_o\\
482 c &\longmapsto c+u
483 \end{align*}
484 with $c \in C_e,~ u \in C_o,~ \phi(c) \in C_o$.
485
486 $\phi$ is bijective, since $\phi(\phi(c))=(c+u)+u=c$,
487
488 so $\phi$ is it's own inverse; hence $|C_e| = |C_o|$.
489
490 Since $C=C_e \cup C_e$, half codewords are even weighted and half odd.
491 \end{itemize}
492\end{proof}
493
494\begin{ex}{6.1}
495 construct standard arrays for codes having each of the GMs:
496
497 $$G_1 = \begin{pmatrix}
498 1 & 0 \\
499 0 & 1
500 \end{pmatrix} ~~~
501 G_2 = \begin{pmatrix}
502 1 & 0 & 1\\
503 0 & 1 & 1
504 \end{pmatrix}
505 $$
506\end{ex}
507\begin{proof}
508 recall: for a binary code with GM $G$, the code $C$ consists of all binary linear combinations of the rows of $G$.
509
510 For $G_1$:\\
511 rows: $r_1=(1,0),~r_2=(0,1))$. A codeword is any linear combination:
512 $$u G_1= a \cdot r_1 + b \cdot r_2,~~ \text{with}~ a,b \in \{0,1\}$$
513
514 4 combinations:
515 \begin{align*}
516 0 \cdot r_1 + 0 \cdot r_2 &= (0,0)\\
517 1 \cdot r_1 + 0 \cdot r_2 &= (1,0)\\
518 0 \cdot r_1 + 1 \cdot r_2 &= (0,1)\\
519 1 \cdot r_1 + 1 \cdot r_2 &= (1,0)+(0,1) = (1,1)
520 \end{align*}
521 $$\Longrightarrow~ C_1 = \{00, 10, 01, 11\}$$
522 $$\text{standard array:}~ 00~01~10~11$$
523
524
525 \vspace{0.5cm}
526 For $G_2$:\\
527 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\}$.
528
529 4 combinations:
530 \begin{align*}
531 0 \cdot r_1 + 0 \cdot r_2 &= (0,0,0)\\
532 1 \cdot r_1 + 0 \cdot r_2 &= (1,0,1)\\
533 0 \cdot r_1 + 1 \cdot r_2 &= (0,1,1)\\
534 1 \cdot r_1 + 1 \cdot r_2 &= (1,0,1)+(0,1,1) = (1,1,0)
535 \end{align*}
536
537 $$\Longrightarrow~ C_2 = \{000, 101, 011, 110\}$$
538 $\Longrightarrow~$ so the 1st row of the standard array is: $000~101~011~110$.
539
540 Now, pick a non used vector: $001$, add it to the code $C_2$:
541 \begin{align*}
542 001 + C_{2_i}&\\
543 001 + 000 &= 001\\
544 001 + 101 &= 100\\
545 001 + 011 &= 010\\
546 001 + 110 &= 111
547 \end{align*}
548 $\Longrightarrow$ 2nd row of the standard array: $001~100~010~111$
549
550 Thus the standard array is
551 \begin{align*}
552 000~101~011~110\\
553 001~100~010~111
554 \end{align*}
555 ie. $2^3=8$ vectors, a $V(3,2)$ vector space.
556\end{proof}
557
558\begin{ex}{6.4}
559 $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$.
560\end{ex}
561\begin{proof}
562 From \ref{remark.6.9}, if $d(C)=2t+1$ (or $2t+2$) $Longrightarrow~ C$ can correct any $t$ errors.
563
564 Hence every vector of weight $\leq t$ is a coset leader and so $\alpha_i = \binom{n}{i}$ for $0 \leq i \leq t$.
565
566 \begin{equation}
567 P_{corr}(C) = \sum_{i=0}^n \alpha_i \cdot p^i(1-p)^{n-i}
568 \label{6.4.eq.1}
569 \end{equation}
570
571 where $\alpha_i$ is the number of coset leaders of weight $i$
572
573 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.
574
575 $$\Longrightarrow~ P_{err}(C) = \sum_{i=0}^n \left( \binom{n}{i} - \alpha_i \right) p^i (1-p)^{n-i}$$
576
577
578 \vspace{0.5cm}
579 Alternatively from \ref{6.4.eq.1}:
580 $$P_{err}(C) = 1 - P_{corr}(C) = 1 - \sum_{i=0}^n \alpha_i \cdot p^i(1-p)^{n-i}$$
581
582 Notice that
583 $$\sum_{i=0}^n \binom{n}{i} p^i (1-p)^{n-i} = (p + (1-p))^n = 1^n = 1$$
584
585 thus
586 \begin{align*}
587 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}\\
588 &= \sum_{i=0}^n \left( \binom{n}{i} - \alpha_i \right) p^i (1-p)^{n-i}
589 \end{align*}
590
591 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.
592
593 Thus
594 \begin{align*}
595 P_{err}(C) &= \sum_{i=0}^n \left( \binom{n}{i} - \alpha_i \right) p^i (1-p)^{n-i}\\
596 &= \left( \binom{n}{t+1} - \alpha_{t+1} \right) p^{t+1} (1-p)^{n-t+1} + \ldots
597 \end{align*}
598 where the $\ldots$ represent the terms with $p^{t+2}$ and higher.
599
600 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.
601
602 Hence,
603 $$P_{err}(C) = \left( \binom{n}{t+1} - \alpha_{t+1} \right) \cdot p^{t+1}$$
604\end{proof}
605
606
607\vspace{1.0cm}
608
609\section{Dual code, PCM and Syndrome}
610
611\subsection{Dual code}
612
613\begin{defn}{}[Orthogonal]
614 Inner product:
615 $$u \cdot v = u_1 v_1 + \ldots + u_n \cdot v_n = \sum_{i=1}^n u_i v_i$$
616 If $u \cdot v = 0$, then $u$ and $v$ are called \emph{orthogonal}.
617\end{defn}
618
619\begin{lemma}{7.1} \label{7.1}
620 for any $u,v,w \in \Vnq$ and $\lambda, \mu \in GF(q)$,
621 \begin{enumerate}[i.]
622 \item $u \cdot v = v \cdot u$
623 \item $(\lambda u + \mu v) \cdot w = \lambda(u \cdot w) + \mu (v \cdot w)$
624 \end{enumerate}
625\end{lemma}
626\begin{proof}
627 (at exercise \ref{ex.7.1}).
628\end{proof}
629
630\begin{defn}{}[Dual code]
631 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.
632 $$C^{\perp} = \{ v \in \Vnq ~|~ v \cdot u = 0 ~\forall~ u \in C \}$$
633\end{defn}
634
635\begin{lemma}{7.2} \label{7.2}
636 $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.
637 $$v \in C^\perp \Longleftrightarrow v \cdot G^T = 0$$
638\end{lemma}
639\begin{proof}
640 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$).
641
642 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
643 $$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$$
644
645 $\Longrightarrow~$ hence $v$ is orthogonal to every codeword of $C$, and so is in $C^\perp$.
646\end{proof}
647
648
649\begin{thm}{7.3}
650 $C$ a $[n,k]$-code over $GF(q)$. Then the dual code $C^\perp$ of $C$ is a linear $[n, n-k]$-code.
651\end{thm}
652\begin{proof}
653 \begin{enumerate}[i.]
654 \item first show that $C^\perp$ is a linear code:
655
656 let $v_1,v_2 \in C^\perp$ and $\lambda, \mu \in GF(q)$. Then $\forall u \in C$,
657 \begin{align*}
658 (\lambda v_1 + \mu v_2) \cdot u &= \lambda (v_1 \cdot u) + \mu (v_2 \cdot u)\\
659 &\text{notice that $v_1,v_2 \in C^\perp$, so}\\
660 &\text{that $v_1,v_2$ are orthogonal with $u$}\\
661 &\text{hence $(v_1 \cdot u)$ and $(v_2 \cdot u)$ are $0$}\\
662 &= \lambda \cdot 0 + \mu \cdot 0 = 0
663 \end{align*}
664
665 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.
666
667 \item Next, show that $C^\perp$ has dimension $n-k$:
668
669 Let $G=[g_{ij}]$ be a GM of $C$.
670
671 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
672 $$\sum_{j=1}^{m} g_{ij} v_j = 0, ~\forall~ i = [k]$$
673
674 $\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:
675
676 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:
677
678$$C = \begin{pmatrix}
679 1 & \ldots & 0 & a_{1,1} & \ldots & a_{1, n-k} \\
680 \vdots & & \vdots & \vdots & & \vdots \\
681 0 & \ldots & 1 & a_{k,1} & \ldots & a_{k, n-k} \\
682\end{pmatrix}$$
683
684Then
685$$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 \}$$
686
687For 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$.
688
689Hence $|C^\perp| = q^{n-k}$, therefore $dim(C^\perp) = n-k$.
690 \end{enumerate}
691\end{proof}
692
693\begin{thm}{7.5} \label{7.5}
694 for any $[n,k]$-code $C$, $(C^\perp)^\perp = C$.
695\end{thm}
696\begin{proof}
697 clearly $C \subseteq (C^\perp)^\perp$, since every vector in $C$ is orthogonal to every vector in $C^\perp$.
698
699 But $dim((C^\perp)^\perp) = n - (n - k ) = k = dim(C)$, therefore $C=(C^\perp)^\perp$.
700\end{proof}
701
702
703\subsection{PCM (parity-check matrix)}
704
705\begin{defn}{}[PCM]
706 A \emph{parity-check matrix} (PCM) $H$ for a $[n,k]$-code $C$ is a generator matrix of $C^\perp$.
707
708 $\Longrightarrow~H$ is a $(n-k) \times n$ matrix satisfying $GH^T=0$.
709\end{defn}
710
711From \ref{7.2} and \ref{7.5},\\
712if $H$ a PCM of $C$, then
713$$C = \{ x \in \Vnq ~|~ xH^T=0 \}$$
714
715$\Longrightarrow$ Any linear code is completely specified by a PCM.
716
717\vspace{0.5cm}
718
719\begin{intuition}{}
720 \begin{enumerate}[i.]
721 \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.
722 \item{dual-code:} orthogonal "shadow", see $C$ as a plane through 3D origin; $C^\perp$ is the (normal vector) line emerging from the plane.
723
724 Rows of the PCM are the basis for the dual-code $C^\perp$ $\Longrightarrow$ ie. the rules that define $C$ are themselves a code.
725 \end{enumerate}
726\end{intuition}
727
728\vspace{0.5cm}
729\begin{thm}{7.6} \label{7.6}
730 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}]$.
731
732 eg.
733$$G = \begin{bmatrix}
734 1 & \ldots & 0 & a_{1,1} & \ldots & a_{1, n-k} \\
735 \vdots & & \vdots & \vdots & & \vdots \\
736 0 & \ldots & 1 & a_{k,1} & \ldots & a_{k, n-k} \\
737\end{bmatrix}$$
738
739$$H = \begin{bmatrix}
740 -a_{1,1} & \ldots & -a_{1, n-k} & 1 & \ldots & 0 \\
741 \vdots & & \vdots & \vdots & & \vdots \\
742 -a_{k,1} & \ldots & -a_{k, n-k} & 0 & \ldots & 1 \\
743\end{bmatrix}$$
744which, in binary, the minus signs are unnecessary.
745\end{thm}
746
747\begin{defn}{}[Standard form]
748 a PCM that is $H = [B ~|~ I_{n-k}]$
749\end{defn}
750
751\subsection{Syndrome}
752\begin{defn}{}[Syndrome]
753 let $H$ a PCM of a $[n,k]$-code $C$.
754
755 Then $\forall~ y \in \Vnq$, the $1 \times (n-k)$ row vector
756 $$S(y) = y H^T$$
757 is called the \emph{syndrome} of $y$.
758\end{defn}
759
760\begin{remark}{}
761 \begin{enumerate}[i.]
762 \item for $h_1, h_2, \ldots, h_{n-k}$ being rows of $H$, then
763 $$S(y) = (y \cdot h_1, y \cdot h_2, \ldots, y \cdot h_{n-k})$$
764 \item $S(y)=0 \Longleftrightarrow y \in C$
765 \end{enumerate}
766\end{remark}
767
768\begin{intuition}{}
769 Syndrome is the "sympthom" of the error. It ignores the valid part of the message and isolates the noise.
770
771 $$S(y) = y H^T = (c+e)H^T = \underbrace{cH^T}_{0} + eH^T = 0+eH^T = e H^T$$
772
773 Syndrome allows the receiver to identify what went wrong without knowing what was originally sent.
774\end{intuition}
775
776\begin{lemma}{7.8}
777 two vectors $u,v$ are the same ocset of $C$ iff they have the same syndrome.
778\end{lemma}
779\begin{proof}
780 if $u,v$ in the same coset of $C$
781 \begin{align*}
782 &\Longrightarrow u+C = v+C\\
783 &\Longrightarrow u-v \in C\\
784 &\Longrightarrow (u-v)H^T =0\\
785 &\Longrightarrow uH^T =v H^T\\
786 &\Longrightarrow S(u) = S(v)
787 \end{align*}
788\end{proof}
789
790\begin{cor}{7.9}
791 There is a one-to-one ccorrespondence between cosets and syndromes.
792
793 $\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$.
794\end{cor}
795
796\begin{eg}{7.10}
797 (from example \ref{h.6.5})
798 $$G= \begin{bmatrix}
799 1 & 0 & 1 & 1\\
800 0 & 1 & 0 & 1
801 \end{bmatrix}$$
802 by \ref{7.6},
803 $$H= \begin{bmatrix}
804 1 & 0 & 1 & 0\\
805 1 & 1 & 0 & 1
806 \end{bmatrix}$$
807
808 Hence the syndromes of the coset leaders are
809 \begin{align*}
810 S(0000) &= 00\\
811 S(1000) &= 11\\
812 S(0100) &= 01\\
813 S(0010) &= 10\\
814 \end{align*}
815
816 The standard array becomes:
817
818 $$
819 \begin{matrix}
820 coset leaders & & & & syndromes\\
821 0000 & 1011 & 0101 & 1110 & 00\\
822 1000 & 0011 & 1101 & 0110 & 11\\
823 0100 & 1111 & 0001 & 1010 & 01\\
824 0010 & 1001 & 0111 & 1100 & 10
825 \end{matrix}
826 $$
827
828 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.
829
830 Locate $y$ in the corresponding row and decode as the codeword at the top of the column containing $y$.
831
832
833 $\longrightarrow$ in practice: \emph{syndrome lookup table}:
834 $$
835 \begin{matrix}
836 \text{syndrome}~ z & \text{coset leader}~ f(z)\\
837 00 & 0000\\
838 11 & 1000\\
839 01 & 0100\\
840 10 & 0010
841 \end{matrix}
842 $$
843
844 decoding procedure:
845 \begin{enumerate}
846 \item receive $y$, calculate $S(y)=y H^T$
847 \item let $z=S(y)$, locate $z$ in the first column of the looku table
848 \item decode $y$ as $y-f(z)$
849 \end{enumerate}
850\end{eg}
851
852\subsection{Incomplete decoding}
853For $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.
854
855$\longrightarrow$ Arrange the cosets in order of increasing weight of the coset leaders.
856
857Divide the array into a top part and a bottom part; top: cosets whose leaders have weights $\leq t$.
858
859\begin{itemize}
860 \item[-] If $y$ in top part: decode as usual (assuming $\leq t$ errors).
861 \item[-] If $y$ in bottom part: conclude that $>t$ errors have occurred, ask for retransmission.
862\end{itemize}
863
864\subsection{Exercises}
865
866\begin{ex}{7.1} \label{ex.7.1}
867 prove Lemma \ref{7.1}
868\end{ex}
869\begin{proof}
870 For any $u,v,w \in \Vnq$ and $\lambda, \mu \in GF(q)$,
871 \begin{enumerate}[i.]
872 \item $u \cdot v = v \cdot u$
873 $$u \cdot v = \sum_{i=1}^n u_i \cdot v_i = \sum_{i=1}^n v_i \cdot u_i = v \cdot u$$
874 \item $(\lambda u + \mu v) \cdot w = \lambda(u \cdot w) + \mu (v \cdot w)$
875 \begin{align*}
876 (\lambda u + \mu v) w &= \sum(\lambda u_i + \mu v_i) w_i\\
877 &= \sum (\lambda u_i w_i + \mu v_i w_i)\\
878 &= \sum (\lambda u_i w_i) + \sum (\mu v_i w_i)\\
879 &= \lambda \sum(u_i w_i) + \mu \sum (v_i w_i)\\
880 &= \lambda \cdot (u \cdot w) + \mu \cdot (v \cdot w)
881 \end{align*}
882 \end{enumerate}
883\end{proof}
884
885\begin{ex}{7.2}
886 prove that if $E_n$ is the binary even weight code of length $n$, then
887 $E_n^\perp$ is the repetition code of length $n$.
888\end{ex}
889\begin{proof}
890 from exercise \ref{ex.5.2}:
891 $$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 \}$$
892
893 GM of $E_n$:
894 $$G = \left[ I_{n-1} \,\middle|\,
895 \begin{matrix}
896 1 \\ \vdots \\ 1
897 \end{matrix}
898 \right]$$
899
900 thus, by \ref{7.6}, PCM is $H=\begin{bmatrix}1&1&\cdots&1\end{bmatrix}$.
901
902 If $H$ is a PCM for $C$, then the rows of $H$ generate $C^\perp$.
903
904 Therefore
905 $$E_n^\perp = <\underbrace{[1~1~\cdots~1]}_{generator}>$$
906
907 then it's codewords are:
908 \begin{align*}
909 0 \cdot (1, \ldots, 1) &= (0, \ldots, 0)\\
910 1 \cdot (1, \ldots, 1) &= (1, \ldots, 1)
911 \end{align*}
912
913 $$\Longrightarrow~ E_n^\perp = \{00\ldots 00,~ 11 \ldots 1 \}$$
914 ie. the repetition code of length $n$.
915\end{proof}
916
917\begin{ex}{7.4}
918 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.
919\end{ex}
920\begin{proof}
921 Let $e$ the error, $y$ the vector received, and $x$ the original codeword. Then $y=x+e$.
922
923 Then
924 $$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$$
925
926 So,
927 $$S(y)^T = e^T H = \sum_{j=1}^n e_j \cdot H_j$$
928 where $H_j$ is the $j$-th column of $H$.
929\end{proof}
930
931
932\begin{ex}{7.6}
933
934 Let $C$ be the ternary linear code with GM
935 $$G = \begin{bmatrix}
936 1 & 1 & 1 & 0 \\
937 2 & 0 & 1 & 1
938 \end{bmatrix}$$
939
940 \begin{enumerate}
941 \item[(a)] Find a generator matrix in standard form.
942 \item[(b)] Find a parity check matrix (PCM) for $C$ in standard form.
943 \item[(c)] Use syndrome decoding to decode the received vectors:
944 $2122, 1201, 2222$
945 \end{enumerate}
946\end{ex}
947\begin{proof}
948 \begin{enumerate}[(a)]
949 \item
950 $$
951 \begin{bmatrix}
952 1 & 1 & 1 & 0 \\
953 2 & 0 & 1 & 1
954 \end{bmatrix}
955 \rightarrow
956 \begin{bmatrix}
957 1 & 1 & 1 & 0 \\
958 0 & 1 & 2 & 1
959 \end{bmatrix}
960 \rightarrow
961 \begin{bmatrix}
962 1 & 0 & 2 & 2 \\
963 0 & 1 & 2 & 1
964 \end{bmatrix}
965 $$
966 thus $
967 G=\begin{bmatrix}
968 1 & 0 & 2 & 2 \\
969 0 & 1 & 2 & 1
970 \end{bmatrix}
971 $ is PCM in standard form.
972
973 \item
974 since $
975 G=\begin{bmatrix}
976 1 & 0 & 2 & 2 \\
977 0 & 1 & 2 & 1
978 \end{bmatrix}
979 $
980 then
981 $$
982 H =
983 \begin{bmatrix}
984 -2 & -2 & 1 & 0 \\
985 -2 & -1 & 0 & 1
986 \end{bmatrix}
987 =
988 \begin{bmatrix}
989 1 & 1 & 1 & 0 \\
990 1 & 2 & 0 & 1
991 \end{bmatrix}
992 $$
993
994 \item
995 $$
996 S(y) = y H^T=S(y) = (y \cdot h_1,\; y \cdot h_2).
997 $$
998 w/ $h_i$ the rows of $H$.
999
1000 compute the lookup table (syndrome table):
1001 $$
1002 \begin{array}{c|c}
1003 e & S(e) \\
1004 \hline
1005 0000 & 00 \\
1006 1000 & 11 \\
1007 2000 & 22 \\
1008 0100 & 12 \\
1009 0200 & 21 \\
1010 0010 & 10 \\
1011 0020 & 20 \\
1012 0001 & 01 \\
1013 0002 & 02
1014 \end{array}
1015 $$
1016 left: weight-$1$ errors, since we're over $F_3$; right: coset leaders for the 9 cosets.
1017
1018 \begin{enumerate}[i.]
1019 \item $y = 2121$:
1020 $$
1021 S(y) =
1022 \begin{bmatrix}
1023 2 & 1 & 2 & 1
1024 \end{bmatrix}
1025 \begin{bmatrix}
1026 1 & 1 \\
1027 1 & 2 \\
1028 1 & 0 \\
1029 0 & 1
1030 \end{bmatrix}
1031 =
1032 [5,5] \equiv [2,2].
1033 $$
1034
1035 $S(y)=[2,2]$, corresponds (in the table) to $e = 2000$.
1036
1037 $$\Longrightarrow~ c = y - e = 2121 - 2000 = 0121$$
1038
1039 \item $y = 1201$
1040 $$
1041 S(y) =
1042 \begin{bmatrix}
1043 1 & 2 & 0 & 1
1044 \end{bmatrix}
1045 H^T
1046 = [3, 6] = [0,0].
1047 $$
1048
1049 corresponds to $e = 0000$
1050 $$\Longrightarrow~ c = y-e = 1201$$
1051
1052 \item $y = 2222$
1053 $$
1054 S(y) =
1055 \begin{bmatrix}
1056 2 & 2 & 2 & 2
1057 \end{bmatrix}
1058 H^T
1059 = [6,8] = [0,2].
1060 $$
1061
1062 corresponds to $e = 0002$
1063
1064 $$\Longrightarrow~ c = y - e = 2222 - 0002 = 2220$$
1065 \end{enumerate}
1066 \end{enumerate}
1067\end{proof}
1068
1069
1070\vspace{1.0cm}
1071
1072\section{Hamming Codes}
1073
1074\begin{defn}{}[Binary Hamming Code]
1075 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)$.
1076
1077 The code having $H$ as its PCM is called a \emph{binary Hamming code}, denoted $Ham(r,2)$.
1078\end{defn}
1079
1080
1081\begin{remark}{}
1082 $Ham(r, 2)$ has length $n=2^r-1$ and dimension $k = n-r$.
1083
1084 Redundancy of the code: $r=n-k$, the number of check symbols in each codeword.
1085\end{remark}
1086
1087
1088\begin{ex}{8.1}
1089 \begin{enumerate}[i.]
1090 \item $r = 2$: $H = \begin{bmatrix}1 & 1 & 0\\ 1 & 0 & 1 \end{bmatrix}$
1091
1092 by Theorem \ref{7.6}, $G = [1\ 1\ \underbrace{1}_{I}]$
1093
1094 so $Ham(2, 2)$ is just the binary triple repetition code.
1095
1096 \item $r = 3$: a PCM for $Ham(3, 2)$ is
1097 $$H =
1098 \begin{bmatrix}
1099 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
1100 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
1101 1 & 0 & 1 & 0 & 1 & 0 & 1
1102 \end{bmatrix}$$
1103
1104 (have taken columns in the natural order of increasing binary numbers from 1 to 7)
1105
1106 $H$ in standard form: rearrange columns:
1107 $$H =
1108 \begin{bmatrix}
1109 0 & 1 & 1 & 1 & 1 & 0 & 0 \\
1110 1 & 0 & 1 & 1 & 0 & 1 & 0 \\
1111 1 & 1 & 0 & 1 & 0 & 0 & 1
1112 \end{bmatrix}$$
1113
1114 by Theorem \ref{7.6}, a generator matrix for $Ham(3, 2)$ is
1115 $$
1116 G =
1117 \begin{bmatrix}
1118 1 & 0 & 0 & 0 & 0 & 1 & 1 \\
1119 0 & 1 & 0 & 0 & 1 & 0 & 1 \\
1120 0 & 0 & 1 & 0 & 1 & 1 & 0 \\
1121 0 & 0 & 0 & 1 & 1 & 1 & 1
1122 \end{bmatrix}
1123 $$
1124 \end{enumerate}
1125\end{ex}
1126
1127
1128\begin{thm}{8.2}
1129 the binary Hamming code $Ham(r,2)$, for $r \geq 2$,
1130 \begin{enumerate}
1131 \item is a $[2^r -1, 2^r-1-r]$-code
1132 \item has minimum distance $3$ (hence is single-error-correcting)
1133 \item is a \emph{perfect code}
1134 \end{enumerate}
1135\end{thm}
1136
1137\vspace{0.5cm}
1138
1139\begin{lemma}{}[Decoding with a binary Hamming code]
1140$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$.
1141
1142Let $j$-th column of H be the binary representation of $j$. Decoding algorithm:
1143\begin{enumerate}
1144 \item receive vector $y$, calculate its syndrome: $S(y)=yH^T$
1145 \item if $S(y)=0$, assume $y=c$ (original sent codeword)
1146 \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.
1147\end{enumerate}
1148\end{lemma}
1149
1150
1151\begin{eg}{}
1152$H =
1153\begin{bmatrix}
11540 & 0 & 0 & 1 & 1 & 1 & 1 \\
11550 & 1 & 1 & 0 & 0 & 1 & 1 \\
11561 & 0 & 1 & 0 & 1 & 0 & 1
1157\end{bmatrix}$,
1158if $y = 1101011$ then
1159
1160$$S(y) = y \cdot H^T = 110$$
1161
1162$\Longrightarrow~6$-th position, and so we decode $y$ as $1101001$
1163\end{eg}
1164
1165\subsection{Extended binary Hamming codes}
1166$\hat{Ham}(r,2)$, obtained from $Ham(r,2)$ by adding an overall parity-check.
1167
1168Not ideal for complete decoding, but good for incomplete decoding (correct any single error and detect any double error).
1169
1170\vspace{1.0cm}
1171
1172Let $H$ be a PCM for $Ham(r,2)$. A PCM $\hat{H}$ for $\hat{Ham}(r,2)$:
1173$$\hat{H}=
1174\begin{bmatrix}
1175 & & & 0 \\
1176 & H & & \vdots\\
1177 & & & 0 \\
1178 1 & \cdots & 1 & 1
1179\end{bmatrix}
1180$$
1181
1182If $H$ is taken with columns in increasing order of binary numbers, we have a neat incomplete decoding algorithm:
1183\begin{eg}{8.3}
1184 $r=3,~ \hat{Ham}(3,2)$. Received $y$, $S(y)=y \hat{H}^T = (s_1, s_2, s_3, s_4)$
1185 \begin{enumerate}[i.]
1186 \item if $s_4=0$ and $(s_1,s_2,s_3)=0$: assume no errors
1187 \item if $s_4=0$ and $(s_1,s_2,s_3) \neq 0$: assume $\geq 2$ errors and ask retransmission
1188 \item if $s_4=1$ and $(s_1,s_2,s_3)=0$: assume $1$ error in the last position
1189 \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)$
1190 \end{enumerate}
1191\end{eg}
1192
1193\vspace{1.0cm}
1194
1195\begin{thm}{8.4} \label{8.4}
1196 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.
1197\end{thm}
1198\begin{proof}
1199 by \ref{5.2}, min. distance of $C$ (ie. $d(C)$) = smallest of the weights of the non-zero codewords.
1200
1201 Let $x=x_1 x_2 \ldots x_n \in \Vnq$, then
1202 \begin{align*}
1203 x \in C &\Longleftrightarrow xH^T=0\\
1204 &\Longleftrightarrow x_1 H_1 + x_2 H_2 + \ldots + x_n H_n = 0
1205 \end{align*}
1206 where $H_i$ denote the columns of $H$.
1207
1208 $\Longrightarrow$ each codeeword $x$ of weight $d$ corresponds with a set of $d$ linearly dependent columns of $H$.
1209
1210 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
1211 $$x_{i_1} H_{i_1} + x_{i_2} H_{i_2} + \ldots + x_{i_{d-1}} H_{i_{d-1}}= 0$$
1212
1213 But then, the vector
1214 $$x = (0 \ldots 0 x_{i_1} 0 \ldots x_{i_2} 0 \ldots 0 x_{i_{d-1}} 0 \ldots 0)$$
1215 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$.
1216\end{proof}
1217
1218\subsection{q-ary Hamming codes}
1219For $C$ a inear code with $d(C)=3$ (min.dist), any $2$ columns of a PCM $H$ must be linearly independent
1220
1221$\Longrightarrow$ columns of $H$ must be non-zero, and no column can be a scalar multiple of another
1222
1223Any $0 \neq v \in V(r,q)$ vector has $q-1$ non-zero scalar multiples, forming the set
1224$$\{ \lambda v ~|~ \lambda \in GF(q), \lambda \neq 0 \}$$
1225
1226$\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}.
1227
1228$\longrightarrow$ two vectors are scalar multiples of each other if they are in the same class
1229
1230By choosing one vector from each class, obtain a set of $\frac{q^r-1}{q-1}$ vectors, where not two are linearly dependent.\\
1231\hspace*{2em} By Theorem \ref{8.4}, taking these as columns of $h$ gives a PCM for a
1232$$\left[\frac{q^r-1}{q-1}, \frac{q^r-1}{(q-1)-r}, 3 \right] \text{-code}$$
1233
1234\hspace*{2em} $\Longrightarrow$ called \emph{q-ary Hamming code}, $Ham(r, q)$.
1235
1236$\longrightarrow$ PCM is unique up to permutation of columns\\
1237\hspace*{2em}$\Longrightarrow$ Hamming codes are linear codes
1238
1239
1240\vspace{0.5cm}
1241
1242\begin{thm}{8.6}
1243 $Ham(r, q)$ is a perfect single-error-correcting code.
1244\end{thm}
1245\begin{proof}
1246 $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}$.
1247
1248 With $t=1$, the LHS of the sphere-packing bound becomes
1249 $$q^{n-r} \cdot (1 + n(q-1)) = q^{n-r} \cdot (1 + q^r -1) = q^n$$
1250 which is the RHS, so $Ham(r, q)$ is a perfect code.
1251\end{proof}
1252
1253\paragraph{Decoding q-ary Hamming code}
1254Since Ham is perfect single-error correcting code, the coset leaders, other than $0$, are the vectors of weight $1$.
1255
1256Syndrome of such coset leader:
1257$$S(0 \ldots 0 ~b~ 0 \ldots 0) = (0 \ldots 0 ~b~ 0 \ldots 0) \cdot H^T = b \cdot H_j^T$$
1258where $H_j$ is the $j$-th column of $H$, and $b$ is at the $j$-th position of $y$.
1259
1260Decode:
1261\begin{itemize}
1262 \item[-] given received $y$, calculate $S(y)=y H^T$
1263 \item[-] if $S(y)=0$, assume no errors
1264 \item[-] if $S(y)\neq 0$, then $S(y) = b \cdot H_j^T$ for some $b$ and $j$\\
1265 correct by: subtract $b$ from the $j$-th entry of $y$.
1266\end{itemize}
1267
1268Example:
1269$$q=5,~ H= \begin{bmatrix}0 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 2 & 3 & 4 \end{bmatrix},~ y=203031$$
1270
1271Then,
1272\begin{align*}
1273 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\\
1274 &= 2 \cdot [0~1] + 3 \cdot [1~1] + 3 \cdot [1~3] + 1 \cdot [1~4]\\
1275 &= [0~2] + [3~3] + [3~9] + [1~4]\\
1276 &= [7~8] = [2~3] = \underbrace{2}_{b} \cdot \underbrace{[1~4]}_{H_6^T} \pmod{5}
1277\end{align*}
1278
1279$\Longrightarrow$ error is in position $6$-th, with magnitude $b=2$\\
1280\hspace*{2em} $\Longrightarrow$ subtract $b$ from the $j$-th entry of $y$: $1-2 \pmod{5} = -1 \pmod{5} = 4$,\\
1281\hspace*{2em} therefore $y'=203034$.
1282
1283\section{MLCT - Main Linear Coding Theory problem}
1284A good $(n,M,d)$-code has
1285\begin{itemize}
1286 \item small $n$, for fast transmission of messages
1287 \item large $M$, to enable transmission of a wide variety of messages
1288 \item large $d$, to correct many errors
1289\end{itemize}
1290
1291Denote by $A_q(n, d)$ the largest $M$ such that $\exists$ a $q$-ary $(n, M, d)$-code.
1292
1293\begin{thm}{2.7}
1294 Suppose $d$ is odd. Then a binary $(n, M, d)$-code exists iff a binary $(n + 1, M, d + 1)$-code exists.
1295\end{thm}
1296\begin{proof}
1297 % TODO
1298\end{proof}
1299
1300\begin{cor}{2.8}
1301 If $d$ is odd, then $A_2(n+1, d+1)=A_2(n, d)$.
1302
1303 Equivalently, if $d$ is even, then $A_2(n, d) = A_2(n-1,d-1)$.
1304\end{cor}
1305
1306% TODO Lemma 2.10
1307
1308
1309\begin{defn}{}[Sphere]
1310 $\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
1311 $$\{ v \in F_q^n ~|~ d(u, v) \leq r \}$$
1312\end{defn}
1313
1314\begin{thm}{1.9 \& 2.12}
1315 a code $C$ can
1316 \begin{enumerate}[i.]
1317 \item detect up to $s$ errors in any codeword if $d(C) \geq s+1$
1318
1319 \item correct up to $t$ errors in any codeword if $d(C) \geq 2t + 1$
1320
1321 This is, the spheres of radius $t$ centered on the codewords of $C$ are disjoint (ie. have no overlap).
1322
1323 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.
1324 \end{enumerate}
1325
1326
1327\begin{center}
1328\begin{tikzpicture}[scale=0.8]
1329 \def\r{1.5}
1330 \def\eps{0.2}
1331
1332 % left: overlapping spheres
1333 \begin{scope}[shift={(-5,0)}]
1334 \coordinate (A) at (0,0);
1335 \coordinate (B) at (2,0);
1336
1337 \draw (A) circle (\r);
1338 \draw (B) circle (\r);
1339
1340 \fill (A) circle (2pt);
1341 \fill (B) circle (2pt);
1342
1343 \node[below] at (A) {$x$};
1344 \node[below] at (B) {$x'$};
1345
1346 \draw (A) -- ($(A)+(0,\r)$);
1347 \node at ($(A)+(0.2,0.7*\r)$) {$t$};
1348
1349 \draw (B) -- ($(B)+(-0.5*\r,0.866*\r)$);
1350 \node at ($(B)+(-0.3*\r,0.5*\r)$) {$t$};
1351
1352 % point y
1353 \fill (1,0.3) circle (2pt);
1354 \node[right] at (1,0.3) {$y$};
1355 \end{scope}
1356
1357
1358 % right: disjoint spheres
1359 \begin{scope}[shift={(3,0)}]
1360 \coordinate (C) at (0,0);
1361 \coordinate (D) at ({2*\r+\eps},0);
1362 \coordinate (E) at ({(\r+\eps/2)}, {sqrt(3)*(\r+\eps/2)});
1363
1364 \draw (C) circle (\r);
1365 \draw (D) circle (\r);
1366 \draw (E) circle (\r);
1367
1368 \fill (C) circle (2pt);
1369 \fill (D) circle (2pt);
1370 \fill (E) circle (2pt);
1371
1372 \node[below] at (C) {$x$};
1373 \node[below] at (D) {$x'$};
1374 \node[above] at (E) {$x''$};
1375
1376 \draw (C) -- ($(C)+(0,\r)$);
1377 \node at ($(C)+(0.2,0.7*\r)$) {$t$};
1378
1379 \draw (D) -- ($(D)+(-\r,0)$);
1380 \node at ($(D)+(-0.6*\r,0.3)$) {$t$};
1381
1382 \draw (E) -- ($(E)+(0,-\r)$);
1383 \node at ($(E)+(0.2,-0.7*\r)$) {$t$};
1384
1385 % point y
1386 \fill (0.5,0.3) circle (2pt);
1387 \node[right] at (0.5,0.3) {$y$};
1388 \end{scope}
1389
1390\end{tikzpicture}
1391\end{center}
1392
1393\end{thm}
1394
1395
1396\begin{defn}{}[Perfect codes]
1397 A code which achieves the sphere-packing bound is called a \emph{perfect code}.
1398 Thus, for a perfect $t$-error-correcting code, the $M$ spheres of radius $t$
1399 centred on codewords ‘fill’ the whole space $F_q^n$ without overlapping.
1400
1401 In other words, every vector in $F_q^n$ is at distance $\leq t$ from exactly one codeword.
1402\end{defn}
1403
1404\vspace{1.0cm}
1405
1406\begin{thm}{}[MLCT problem (Version 1)]
1407 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)$.
1408\end{thm}
1409
1410\begin{remark}{}
1411 \emph{redundancy} $r$ of an $[n, k, d]$-code is just $r=n-k$ (the number of check symbols in a codeword).
1412\end{remark}
1413
1414\begin{thm}{}[MLCT problem (Version 2)]
1415 For given redundancy $r$, find the maximum length $n$ such that $\exists$ an $[n, n-r, d]$-code over $GF(q)$.
1416\end{thm}
1417
1418
1419\begin{defn}{}[$(n,s)$-set]
1420 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.
1421
1422 Denote $max_s(r,q)$ the largest value of $n$ for which $\exists$ a $(n,s)$-set
1423 in $V(r,q)$.\\
1424 ie.
1425 \begin{itemize}
1426 \item $(n,s)$-set: $n$ vectors with $s$ of them lin. independent
1427 \item $max_s(r,q)$: max $n$ for which $\exists~ (n,s)$-set
1428 \end{itemize}
1429\end{defn}
1430
1431\begin{defn}{}[Packing problem]
1432 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.
1433\end{defn}
1434
1435\begin{thm}{14.1} \label{14.1}
1436There exists an $[n,n-r,d]$-code over $GF(q)$ iff $\exists$ an $(n, d-1)$-set in $V(r, q)$.
1437\end{thm}
1438\begin{proof}
1439 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)$.
1440
1441 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$.
1442\end{proof}
1443
1444\begin{cor}{14.2}
1445 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)$.
1446\end{cor}
1447
1448$\Longrightarrow$ the MLCT problem (V2) is the same as the packing problem of finding $max_{d-1}(r, q)$.
1449
1450\subsection{The projective geometry PG(r-1,q)}
1451Let the vector space
1452$$V(r,q)= \{ (a_1, a_2, \ldots, a_r) ~|~ a_i \in GF(q) \}$$
1453
1454\begin{defn}{}[Projective Geometry]
1455 $PG(r-1, q)$
1456 \begin{itemize}
1457 \item \emph{points} are the one-dimensional subspaces of $V(r, q)$
1458 \item \emph{lines} are the two-dimensional subspaces of $V(r, q)$
1459 \end{itemize}
1460
1461 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.
1462
1463 So if $a=(a_1, a_2, \ldots, a_r) \in P$, then $P= \{ \lambda a ~|~ \lambda \in GF(q) \}$.
1464
1465 $\Longrightarrow$ for $a=(a_1, a_2, \ldots, a_r),~b=(b_1, b_2, \ldots, b_r) \in P$, then
1466 $$a=b ~\text{in}~ PG(r-1,q) ~\text{iff}~ a=\lambda b ~\text{in}~ V(r,q)$$
1467 for some non-zero scalar $\lambda$.
1468\end{defn}
1469
1470\begin{lemma}{14.6}
1471 in $PG(r-1,q)$,
1472 \begin{enumerate}
1473 \item number of points is $\frac{q^r-1}{q-1}$
1474 \item any two points lie on exactly one line
1475 \item each line contains exactly $q+1$ points
1476 \item each point lies on $\frac{q^{r-1} -1}{q-1}$ lines
1477 \end{enumerate}
1478\end{lemma}
1479\begin{proof}
1480 \begin{enumerate}
1481 \item number of points is $\frac{q^r-1}{q-1}$:\\
1482 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}$
1483
1484 \item any two points lie on exactly one line:\\
1485 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.
1486
1487 \item each line contains exactly $q+1$ points:\\
1488 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
1489 $$\frac{q^2 -1}{q-1}=q+1$$
1490
1491 \item each point lies on $\frac{q^{r-1} -1}{q-1}$ lines:\\
1492 let $t$ be the number of lines on which a point $P$ lies. Let the set
1493 $$X=\{(Q,L) ~|~ Q ~\text{is a point}~ \neq P,~ L~\text{is a line containing both}~ P ~\text{and}~ Q \}$$
1494
1495 Count the members of $X$ in two ways:
1496
1497 for each of the $\frac{q^r -1}{q-1} -1$ choices of $Q$, $\exists !$ line containing $P$ and $Q$. Thus,
1498 $$|X|=\frac{q^r-1}{q-1} -1 = \frac{q^r-q}{q-1}$$
1499
1500 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$.
1501
1502 Thus, $|X|=tq$,
1503 $$\Longrightarrow tq = \frac{q^r-q}{q-1}, ~~~~ \Longrightarrow t=\frac{q^{r-1}-1}{q-1}$$
1504 \end{enumerate}
1505\end{proof}
1506
1507\begin{defn}{}[Projective plane]
1508 The $PG(2,q)$ is called the \emph{projective plane} over $GF(q)$.
1509\end{defn}
1510
1511\section{MDS Codes}
1512
1513\begin{thm}{15.1}
1514 a $[n, n-r, d]$-code satisfies $d \leq r+1$.
1515\end{thm}
1516\begin{proof}
1517 let $C$ a $[n, n-r, d]$-code, let $G=[ I_{n-r} ~|~ A]$ be a standard form GM of $C$.
1518
1519 Since $A$ has $r$ columns, the codewords whicch are rows of $G$ have weight $\leq r+1$, ie. $w(C) \leq r+1$.
1520
1521 The result follows from Theorem \ref{5.2},
1522 \begin{align*}
1523 &\Longrightarrow~ w(C)=d(C)\\
1524 &\Longrightarrow~ d(C) \leq r+1.
1525 \end{align*}
1526\end{proof}
1527
1528\begin{defn}{}[MDS]
1529 a $[n, n-r, r+1]$-code,\\
1530 \hspace*{2em}ie. a linear cocde of redundancy $r$ whose min. distance is $r+1$,\\
1531 is called a \emph{maximum distance separable code}, MDS.
1532
1533 $\longrightarrow$ by Theorem \ref{14.1}, max length of a MDS code over $GF(q)$ is $max_r(r,q)$, the largest size of a $(n,r)$-set in $V(r,q)$.
1534\end{defn}
1535
1536\begin{conj}{15.2}
1537 if $2 \leq r \leq q$, then $max_r(r,q)=q+1$
1538
1539 (except $max_3(3,q)=max_{q-1}(q-1,q)=q+2$ if $q=2^h$)
1540\end{conj}
1541
1542\begin{thm}{15.3}
1543 if $r\geq q$, then $max_r(r,q)=r+1$. Any MDS code of redundancy $r\geq q$ is equivalent to a repetition code of length $r+1$.
1544\end{thm}
1545\begin{proof}
1546 repetition code of length $r+1$: a $[r+1, 1, r+1]$-code with GM $[1~1~\cdots~1]$.
1547
1548 Hence $max_r(r,q) \geq r+1$.
1549
1550 Also, any $[r+1, 1, r+1]$-code is equivalent to a repetition code.
1551
1552 Suppose $r \geq q$ and by contradiction that $max_r(r,q) \geq r+2$.
1553
1554 Then, $\exists$ a $[r+2, 2, r+1]$-code $C$ over $GF(q)$.
1555
1556 $\longrightarrow~C$ must be equivalent to a code having GM:
1557 $$G=
1558 \begin{bmatrix}
1559 1 & 0 & 1 & 1 & \ldots & 1\\
1560 0 & 1 & a_1 & a_2 & \ldots & a_r
1561 \end{bmatrix}
1562 $$
1563
1564 in order that any linear combination of the rows of $G$ has weight at least $r+1$ with $0 \neq a_i \in GF(q)$.
1565
1566 This implies $r \leq q-1$, contradiction.
1567\end{proof}
1568
1569\begin{remark}{}
1570 the only binary MDS codes are\\
1571 $V(n,2)$, the even weighted codes $E_n$, and repetition codes.
1572\end{remark}
1573
1574\begin{thm}{15.4}
1575 let $2 \leq r \leq q$, let $a_1, a_2, \ldots, a_{q-1} \in GF(q)$ nonzero.
1576
1577 Then,
1578 $$
1579 H =
1580 \begin{bmatrix}
1581 1 & 1 & \ldots & 1 & 1 & 0\\
1582 a_1 & a_2 & \ldots & a_{q-1} & 1 & 0\\
1583 a_1^2 & a_2^2 & \ldots & a_{q-1}^2 & 1 & 0\\
1584 & & & & \vdots & \vdots\\
1585 \vdots & \vdots & & \vdots & 0 & 0\\
1586 a_1^{r-1} & a_2^{r-1} & \ldots & a_{q-1}^{r-1} & 0 & 1
1587 \end{bmatrix}
1588 $$
1589
1590 is the PCM of a MDS $[q+1, q+1-r, r+1]$-code.
1591
1592 Equivalently, the columns of $H$ form a $(q+1)$-arc in $PG(r-1, q)$.
1593\end{thm}
1594\begin{proof}
1595 the determinant of a matrix formed by any $r$ columns of $H$ is equal to the determinant of a Vandermonde matrix, and so is non-zero (see a proof of this at section \ref{sec:vandermondedet}).
1596 Thus any $r$ columns of $H$ are linearly independent.
1597\end{proof}
1598
1599\begin{cor}{15.7}
1600 The dual code of a MDS code is also MDS.
1601\end{cor}
1602\begin{cor}{15.8}
1603 $\exists$ a MDS $[n,k]$-code over $GF(q)$ iff $\exists$ a MDS $[n, n-k]$-code over $GF(q)$.
1604\end{cor}
1605
1606
1607\subsection{Vandermonde determinant} \label{sec:vandermondedet}
1608
1609This section contains a simple proof of the Vandermonde matrix determinant. The proof was found in \cite{vanddetproof}, here it is written with small modifications and expanded. A different proof can be found in \cite{vanddetproof2}.
1610
1611\begin{lemma}{}[Vandermonde determinant]
1612$$
1613\det~V(x_1, ..., x_n) = \det
1614\begin{pmatrix}
1615 1 & x_1 & x_1^2 & \ldots & x_1^{n-1} \\
1616 1 & x_2 & x_2^2 & \ldots & x_2^{n-1} \\
1617 1 & x_3 & x_3^2 & \ldots & x_3^{n-1} \\
1618 \vdots & \vdots & \vdots & & \vdots\\
1619 1 & x_n & x_n^2 & \ldots & x_n^{n-1} \\
1620\end{pmatrix}
1621= \prod_{j < i} (x_i - x_j)
1622$$
1623\end{lemma}
1624
1625\begin{proof}
1626
1627The equation is true for $n = 2$, as we have:
1628
1629$$
1630\det~V(x_1, x_2) = \det
1631\begin{pmatrix}
1632 1 & x_1\\
1633 1 & x_2
1634\end{pmatrix}
1635= x_2 - x_1
1636$$
1637
1638We now assume that $n \ge 3$. Starting with column $n$ and ending at column $2$, we successively apply the following operation: subtract $x_1$ times column $i-1$ from column $i$. The determinant remains the same and the resulting matrix is:
1639
1640$$
1641= \det
1642\begin{pmatrix}
1643 1 & x_1-(x_1 \cdot 1) & x_1^2 - (x_1 \cdot x_1) & \ldots & x_1^{n-1} - (x_1 \cdot x_1^{n-2}) \\
1644 1 & x_2-(x_1 \cdot 1) & x_2^2 - (x_1 \cdot x_2) & \ldots & x_2^{n-1} - (x_1 \cdot x_2^{n-2}) \\
1645 1 & x_3-(x_1 \cdot 1) & x_3^2 - (x_1 \cdot x_3) & \ldots & x_3^{n-1} - (x_1 \cdot x_3^{n-2}) \\
1646 \vdots & \vdots & \vdots & & \vdots\\
1647 1 & x_n-(x_1 \cdot 1) & x_n^2 - (x_1 \cdot x_n) & \ldots & x_n^{n-1} - (x_1 \cdot x_n^{n-2}) \\
1648\end{pmatrix}
1649$$
1650$$
1651= \det
1652\begin{pmatrix}
1653 1 & 0 & 0 & \ldots & 0 \\
1654 1 & (x_2 - x_1) & x_2(x_2 - x_1) & \ldots & x_2^{n-2}(x_2 - x_1) \\
1655 1 & (x_3 - x_1) & x_3(x_3 - x_1) & \ldots & x_3^{n-2}(x_3 - x_1) \\
1656 \vdots & \vdots & \vdots & & \vdots \\
1657 1 & (x_n - x_1) & x_n(x_n - x_1) & \ldots & x_n^{n-2}(x_n - x_1) \\
1658\end{pmatrix}
1659$$
1660
1661Applying the Laplace expansion along the first row and factoring out the scalar multiples $(x_i - x_1)$ in each column, we obtain:
1662
1663$$
1664= \det
1665\begin{pmatrix}
1666 x_2-x_1 & x_2^2 - x_1 x_2 & x_2^3 - x_1 x_2^2 & \ldots & x_2^{n-1} - x_1 x_2^{n-2} \\
1667 x_3-x_1 & x_3^2 - x_1 x_3 & x_3^3 - x_1 x_3^2 & \ldots & x_3^{n-1} - x_1 x_3^{n-2} \\
1668 \vdots & \vdots & \vdots & & \vdots\\
1669 x_n-x_1 & x_n^2 - x_1 x_n & x_n^3 - x_1 x_n^2 & \ldots & x_n^{n-1} - x_1 x_n^{n-2} \\
1670\end{pmatrix}
1671$$
1672
1673in each row, factor out $(x_i - x_1)$
1674
1675$$
1676= \det
1677\begin{pmatrix}
1678 1(x_2-x_1) & x_2(x_2 - x_1) & x_2^2(x_2 - x_1) & \ldots & x_2^{n-2}(x_2 - x_1) \\
1679 1(x_3-x_1) & x_3(x_3 - x_1) & x_3^2(x_3 - x_1) & \ldots & x_3^{n-2}(x_3 - x_1) \\
1680 \vdots & \vdots & \vdots & & \vdots\\
1681 1(x_n-x_1) & x_n(x_n - x_1) & x_n^2(x_n - x_1) & \ldots & x_n^{n-2}(x_n - x_1) \\
1682\end{pmatrix}
1683$$
1684$$
1685= \prod_{2 \leq i \leq n} (x_i - x_1) ~~\det
1686\begin{pmatrix}
1687 1 & x_2 & x_2^2 & \ldots & x_2^{n-2} \\
1688 1 & x_3 & x_3^2 & \ldots & x_3^{n-2} \\
1689 \vdots & \vdots & \vdots & & \vdots\\
1690 1 & x_n & x_n^2 & \ldots & x_n^{n-2} \\
1691\end{pmatrix}
1692$$
1693
1694now, by induction
1695
1696$$
1697= \prod_{i=2}^n (x_i - x_1) ~~\cdot \prod_{2 \leq j < i \leq n} (x_i - x_j) ~~= \prod_{1 \leq j < i \leq n} (x_i - x_j)
1698$$
1699\end{proof}
1700
1701
1702\vspace{1.0cm}
1703
1704\section{Cyclic Codes}
1705This section contains notes both from Hill \cite{hill} and Lint \cite{lint} books. Hill's notes are enumerated as $X.Y$ while Lint's notes as $X.Y.Z$.
1706
1707\subsection{Recap on ideals}
1708More about ideals at the \emph{Commutative Algebra notes} \cite{commutativealgebranotes}.
1709\vspace{0.6cm}
1710
1711In the cyclic codes context, we're interested in ideals because
1712\begin{itemize}
1713 \item cyclic codes are ideals of $R_n = \mathbb{F}_q[x]/(x^n-1)$.
1714 \item $R_n$ is a PID: every ideal in $R_n$ is principal.
1715\end{itemize}
1716
1717\vspace{0.6cm}
1718
1719\begin{defn}{}[ideal]
1720 $I \subset R$ ($R$ ring) such that $0 \in I$ and $\forall x \in I,~ r \in R,~ xr, rx \in I$.\\
1721 \hspace*{2em} ie. $I$ absorbs products in $R$.
1722\end{defn}
1723
1724\begin{defn}{}[prime ideal]
1725 if $a, b \in R$ with $ab \in P$ and $P \neq R$ ($P$ a prime ideal), implies $a \in P$ or $b \in P$.
1726\end{defn}
1727
1728\begin{defn}{}[principal ideal]
1729 generated by a single element, $(a)$.
1730
1731 $(a)$: principal ideal, the set of all multiples $xa$ with $x \in R$.
1732\end{defn}
1733
1734\begin{defn}{}[prime spectrum - $Spec(A)$]
1735 set of prime ideals of $A$. ie.
1736
1737 $$Spec(A) = \{ P ~|~ P \subset A~ \text{is a prime ideal} \}$$
1738\end{defn}
1739
1740\begin{defn}{}[integral domain]
1741 Ring in which the product of any two nonzero elements is nonzero.
1742
1743 ie. no zerodivisors.
1744
1745 ie. $\forall~ 0 \neq a,~ 0 \neq b \in A,~ ab \neq 0 \in A$.
1746
1747 Every field is an integral domain, not the converse.
1748\end{defn}
1749
1750\begin{defn}{}[principal ideal domain - PID]
1751 integral domain in which every ideal is principal. ie.
1752 ie. $\forall I \subset R,~ \exists~ a \in I$ such that $I = (a) = \{ ra ~|~ r \in R \}$.
1753\end{defn}
1754
1755
1756\vspace{1.0cm}
1757
1758\subsection{Cyclic Codes intro}
1759
1760\begin{defn}{}[cyclic code]
1761 a code $C$ is cyclic if
1762 \begin{enumerate}[i.]
1763 \item $C$ is a linear code
1764 \item any cyclic shift of a codeword is also a codeword\\
1765 ie. when $a_0 a_1 \ldots a_{n-1} \in C$,\\
1766 then so $a_{n-1} a_0 a_1 \ldots a_{n-2} \in C$.
1767 \end{enumerate}
1768\end{defn}
1769
1770\begin{remark}{}[Notation]
1771 From now on,
1772 $$F_q = \mathbb{F}_q = GF(q)$$
1773
1774 $F_q[x]$ is a ring; and for $f(x)$ irreducible in $F_q[x]$, then $\frac{F_q[x]}{f(x)}$ is a field.
1775
1776 From now on,
1777$$f(x) = x^n -1 ~~~\Longrightarrow~~ F_q[x]/(x^n-1) = R_n$$
1778
1779 \vspace{0.6cm}
1780 Observe:\\
1781 since $x^n \cong 1 \bmod{x^n -1}$, to reduce any polynomial by modulo $x^n-1$ can just replace $x^n$ by $1$, $x^{n+1}$ by $x$, $x^{n+2}$ by $x^2$, etc.
1782
1783 \vspace{0.6cm}
1784 Correspondence:
1785 $$a_0 a_1 \ldots a_{n-1} \in V(n,q) ~\Longleftrightarrow~ a(x)=a_0 + a_1 x + \ldots + a_{n-1} x^{n-1} \in R_n$$
1786
1787 In $R_n$,
1788 \begin{align*}
1789 x \cdot a(x) &= a_0 \cdot x + a_1 x^2 + \ldots + \underbrace{a_{n-1} x^n}_{=a_{n-1}\cdot 1}\\
1790 &=a_{n-1} + a_0 x + \ldots + a_{n-2} \cdot x^{n-1} \in R_n
1791 \end{align*}
1792
1793 ie. $a_{n-1} a_0 a_1 \ldots a_{n-2} \in V(n, q)$
1794
1795 \vspace{0.6cm}
1796 In $R_n$:
1797 \begin{itemize}
1798 \item[$\rightarrow$] multiply by $x$ corresponds to performing a single cyclic shift
1799 \item[$\rightarrow$] multiply by $x^m$ corresponds to a cyclcic shift through $m$ positions
1800 \end{itemize}
1801\end{remark}
1802
1803
1804\vspace{1.0cm}
1805\begin{thm}{12.6}[Algebraic characterization of cyclic codes] \label{12.6}
1806 a code $C \in R_n$ is a cyclic code iff
1807 \begin{enumerate}[i.]
1808 \item $a(x),b(x) \in C ~\Longrightarrow~ a(x)+b(x) \in C$
1809 \item $a(x) \in C$ and $r(x) \in R_n ~\Longrightarrow~ r(x) a(x) \in C$\\
1810 ie. $C$ closed under multiplication by any element of $R_n$
1811 \end{enumerate}
1812\end{thm}
1813\begin{proof}
1814 \begin{enumerate}[i.]
1815 \item let $C \in R_n$ cyclic code, then $C$ is linear, so (i) holds.
1816 \item let $a(x) \in C$ and $r(x) = r_0 + r_1 x + \ldots + r_{n-1} x^{n-1} \in R_n$.
1817
1818 Since mult. by $x$ corresponds to a cyclic shift, then $x \cdot a(x) \in C$, thus
1819 $$x \cdot (x \cdot a(x)) = x^2 \cdot a(x) \in C$$
1820 and so on.
1821
1822 Hence,
1823 $$r(x) \cdot a(x) = r_0 \cdot a(x) + r_1 \cdot x \cdot a(x) + \ldots + r_{n-1} \cdot x^{n-1} \cdot a(x) \in C$$
1824 since each summand is in $C$; thus (ii) holds.
1825
1826 \vspace{0.5cm}
1827 Conversely, suppose (i) and (ii) hold;\\
1828 taking $r(x)$ to be a scalar, the conditions imply that $C$ is linear.\\
1829 Taking $r(x)=x$, in (ii) shows that $C$ is cyclic.
1830 \end{enumerate}
1831\end{proof}
1832
1833\vspace{0.8cm}
1834\begin{remark}{}
1835 \begin{enumerate}[i.]
1836 \item Cyclic codes are the ideals of the ring $R_n$.
1837 \item Every ideal in $R_n$ is a \emph{principal ideal}.\\
1838 ie. $R_n$ is a PID.
1839 \end{enumerate}
1840\end{remark}
1841
1842\vspace{0.5cm}
1843\begin{thm}{6.1.3}
1844 a linear code $C$ in $\mathbb{F}_q^n$ is cyclic iff $C$ is an ideal in $\mathbb{F}_q[x]/(x^n -1)$.
1845\end{thm}
1846\begin{proof}
1847 If $C$ ideal in $\mathbb{F}[x]/(x^n -1)$ and $c(x)=c_0 + c_1 x + \ldots + c_{n-1}x^{n-1} \in C$, then
1848 \begin{align*}
1849 x \cdot c(x) &= c_0 x + c_1 x \cdot x + \ldots + \underbrace{c_{n-1} x^{n-1} \cdot x}_{=c_{n-1} \cdot 1 \pmod{x^n-1}}\\
1850 &= c_{n-1} + c_0 x + c_1 x^2 + \ldots + c_{n-2} x^{n-1} \in C\\
1851 \Longrightarrow&~ (c_{n-1}, c_0, c_1, \ldots, c_{n-2}) \in C
1852 \end{align*}
1853
1854 \vspace{0.5cm}
1855 Conversely, if $C$ cyclic, then $\forall c(x) \in C,~ x \cdot c(x) \in C$.
1856
1857 Therefore $x^i \cdot c(x) \in C ~\forall i \in [n]$
1858
1859 and since $C$ is linear, $a(x) \cdot c(x) \in C$
1860
1861 ie.
1862 $$a_0 \cdot c(x) + a_1 \cdot x \cdot c(x) + a_2 \cdot x^2 \cdot c(x) + \ldots + a_{n-1} \cdot x^{n-1} \cdot c(x) \in C$$
1863 $\forall a(x) \in \mathbb{F}_q[x]/(x^n-1)$.
1864\end{proof}
1865
1866\begin{cor}{}
1867 $\mathbb{F}_q[x]/(x^n -1)$ is a PID (Principal Ideal Domain).
1868
1869 Thus $C$ consists of the multiples of $g(x) \in C$ monic and of lowest degree.
1870
1871 Therefore,
1872 \begin{itemize}
1873 \item[$\Longrightarrow$] $g(x)$ is the \emph{generator polynomial} (more at \ref{12.9}) of $C$: $C= \langle g(x) \rangle$.
1874 \item[$\Longrightarrow$] $g(x)$ is divisor of $x^n -1$, ie. $g(x) | (x^n-1)$.\\
1875 since otherwise $gcd(x^n-1, g(x))$ would be a polynomial in $C$ with degree $< deg(g(x))$, a contradiction.
1876
1877 \end{itemize}
1878\end{cor}
1879\vspace{0.5cm}
1880
1881\vspace{1.0cm}
1882Let $f(x) \in R_n$, $\langle f(x) \rangle$ the subset of $R_n$ consisting of all multiples of $f(x)$ (reduced modulo $x^n-1$). ie.
1883$$\langle f(x) \rangle = \{ r(x) \cdot f(x) ~|~ r(x) \in R_n \}$$
1884
1885
1886\begin{thm}{12.7}
1887 for any $f(x) \in R_n$, the set $\langle f(x) \rangle$ is a cyclic code; named the \emph{code generated by $f(x)$}.
1888\end{thm}
1889\begin{proof}
1890 check conditions (i), (ii) of Theorem \ref{12.6}:
1891 \begin{enumerate}[i.]
1892 \item if $a(x)f(x),~ b(x)f(x) \in \langle f(x) \rangle$ then
1893 $$a(x)f(x)+b(x)f(x)= (a(x)+ b(x)) f(x) \in \langle f(x) \rangle$$
1894
1895 \item if $a(x)f(x) \in \langle f(x) \rangle$ and $r(x) \in R_n$, then
1896 $$r(x) (a(x)f(x))= (r(x) \cdot a(x)) f(x) \in \langle f(x) \rangle$$
1897 \end{enumerate}
1898\end{proof}
1899
1900\begin{eg}{12.8}
1901 $C=\langle 1+x^2 \rangle \in R_3$, with $GF(2)$.
1902
1903 $R_3$ has $2^3=8$ elements.
1904
1905 Multiply $1+x^2$ by each of the 8 elements of $R_3$ (reducing modulo $x^3-1$), obtaining 4 distinct codewords:
1906 $$0, 1+x, 1+x^2, x+x^2$$
1907 Thus $C$ is the code $\{ 000, 110, 101, 011 \}$.
1908\end{eg}
1909
1910
1911\subsection{Generator polynomial and check polynomial}
1912
1913\begin{thm}{12.9} \label{12.9}
1914 let $C$ a nonzero cyclic coded in $R_n$. Then
1915 \begin{enumerate}[i.]
1916 \item $\exists !~ g(x)$ monic, of smallest degree in $C$
1917 \item $C=\langle g(x) \rangle$
1918 \item $g(x)$ is a factor of $x^n -1$
1919 \end{enumerate}
1920\end{thm}
1921\begin{proof}
1922 \begin{enumerate}[i.]
1923 \item $\exists !~ g(x)$ monic, of smallest degree in $C$:\\
1924 let $g(x), h(x) \in C$ monic and of smallest degree. Then $g(x)-h(x) \in C$ with smaller degree, which is a contradiction if $g(x) \neq h(x)$
1925
1926 \item $C=<g(x)>$:\\
1927 let $a(x) \in C$. By division algorithm for $F_q[x]$,
1928 $$a(x) = q(x) g(x) + r(x)$$
1929 with $deg(r(x)) < deg(g(x))$.
1930
1931 But $r(x) = a(x) - q(x)g(x) \in C$ by the properties of cyclic codes (Theorem \ref{12.6}, $a,g \in C$ and $C$ an ideal)
1932
1933 By minimality of $deg(g(x))$, must have $r(x) = 0$, therefore
1934 $$a(x) \in \langle g(x) \rangle \forall a(x) \in C$$
1935 $$\Longrightarrow~ C=\langle g(x) \rangle$$
1936
1937 \item $g(x)$ is a factor of $x^n -1$:\\
1938 by division algorithm,
1939 $$x^n -1 = q(x) g(x) + r(x)$$
1940 with $deg(r(x)) < deg(g(x))$.
1941
1942 But then $r(x) = -q(x) g(x) \bmod{x^n -1}$, ie. $r(x)$ is a multiple of $g(x)$, and so $r(x) \in \langle g(X) \rangle$.
1943
1944 By the minimality of $deg(g(x))$, we must have $r(X)=0$, which implies
1945 $$x^n -1 = q(x) \cdot g(x) + 0$$
1946 $\Longrightarrow~ g(x)$ is a factor of $(x^n-1)$.
1947 \end{enumerate}
1948\end{proof}
1949
1950
1951\begin{defn}{}[Generator polynomial]
1952 let $C$ cyclic code, monic polynomial of least ddegree (given by Theorem \ref{12.9}) is called the \emph{generator polynomial} of $C$.
1953
1954 Remark $C$ may contain other polynomials than the generator polynomial which also generate $C$.
1955\end{defn}
1956
1957
1958\begin{eg}{12.10}
1959 All cyclic codes of length $3$:\\
1960 ie. ideals in $\mathbb{F}_2[x]/(x^3-1) ~\Longrightarrow$ factor $x^3-1$ in $\mathbb{F}_2$, every cyclic code corresponds to a divisor of $x^3-1$.
1961
1962 $$x^3-1 = (x+1) \cdot (x^2+x+1)$$
1963 so by Theorem \ref{12.9}(ii):
1964
1965 \begin{center}
1966 \begin{tabular}{ c c c }
1967 generator poly & code in $R_3$ & Corresponding code in $V(3,2)$\\
1968 \hline
1969 1 & all of $R_3$ & all of $V(3,2)$ \\
1970 $x+1$ & $\{0, 1+x, x+x^2,1+x^2\}$ & $\{000, 110, 011, 101\}$ \\
1971 $x^2+x+1$ & $\{0, 1+x+x^2\}$ & $\{000, 111\}$ \\
1972 $x^3-1$ & $\{0\}$ & $\{000\}$
1973 \end{tabular}
1974 \end{center}
1975
1976 Notice that the 2nd column contains the multiples $\pmod{x^3-1}$ of the polynomials at the 1st column.
1977\end{eg}
1978
1979\begin{lemma}{12.11}
1980 let $g(x)=g_0 + g_1 + \ldots + g_r x^r$ be the generator polynomial. Then $g_0$ is nonzero.
1981\end{lemma}
1982\begin{proof}
1983 by contradiction, let $g_0=0$. Then $x^{n-1} \cdot g(x) = x^{-1} \cdot g(x) \in C$ with degree $r-1$.
1984
1985 This contradicts minimality of $deg(g(x))$; thus $g_0 \neq 0$.
1986\end{proof}
1987
1988\begin{thm}{12.12} \label{12.12}
1989 let $C$ cyclic code with generator polynomial $g(x) = g_0 + g_1 x + \ldots + g_r x^r$. Then $dim(C)=n-r$, and a GM for $C$ is
1990 $$
1991 G= \begin{pmatrix}
1992 g_0 & g_1 & g_2 & \cdots & g_r & 0 & 0 & \cdots & 0\\
1993 0 & g_0 & g_1 & g_2 & \cdots & g_r & 0 & \cdots & 0\\
1994 0 & 0 & g_0 & g_1 & g_2 & \cdots & g_r & \cdots & 0\\
1995 & \vdots & & & & & & \vdots\\
1996 0 & 0 & \cdots & 0 & g_0 & g_1 & g_2 & \cdots & g_r\\
1997 \end{pmatrix}
1998 $$
1999\end{thm}
2000\begin{proof}
2001 the $n-r$ rows of $G$ are linear independent because the echelon of nonzero $g_0$'s with $0$'s below.
2002
2003 These $n-r$ represent the codewords $g(x), x \cdot g(x), x^2 g(x), \ldots, x^{n-r-1}g(x)$.
2004
2005 It remains to show that every codeword in $C$ can be expressed as a linear combination of them.
2006
2007 From Theorem \ref{12.9}.(ii), if $a(x) \in C$ then $a(x)=q(x)\cdot g(x)$ for $q(x) \in \mathbb{F}_q[x]$.
2008
2009 Since $deg(a(x)) <n,~~ deg(q(x)) < n-r$.
2010
2011 Hence
2012 \begin{align*}
2013 q(x)g(x) &= (q_0+q_1 x + \ldots + q_{n-r-1} x^{n-r-q}) \cdot g(x)\\
2014 &= q_0 g(x)+q_1 x g(x) + \ldots + q_{n-r-1} x^{n-r-q} g(x)
2015 \end{align*}
2016 which is the desired linear combination.
2017\end{proof}
2018
2019
2020\begin{defn}{}[check polynomial]
2021 For generator polynomial $g(x)$, which we know is a factor of $x^n -1$.
2022
2023 Then, the \emph{check polynomial} $h(x)$ is such that
2024 $$x^n-1 = g(x) h(x)$$
2025
2026 Since $g(x)$ is monic, so also is $h(x)$. By Theorem \ref{12.12},
2027 $$deg(g(x)) = n-k ~~\Longrightarrow~~ deg(h(x))=k$$
2028\end{defn}
2029
2030\begin{thm}{12.14} \label{12.14}
2031 $c(x) \in R_n$ is $c(x) \in C$ iff $c(x) \cdot h(x) =0$.
2032\end{thm}
2033\begin{proof}
2034 in $R_n: ~ g(x) \cdot h(x) = x^n -1 = 0 \bmod{x_n -1}$,\\
2035 hence
2036 $$c(x) \in C ~\stackrel{implies}{\Longrightarrow}~ c(x) = a(x) \cdot g(x)$$
2037 for some $a(x) \in R_n$.
2038
2039 \begin{align*}
2040 \Longrightarrow~ c(x) \cdot h(x) &= \overbrace{a(x) \cdot g(x)}^{c(x)} \cdot h(x)\\
2041 (\text{note that}~ g(x) &\cdot h(x)=0)\\
2042 &= a(x) \cdot 0 = 0
2043 \end{align*}
2044 $\Longrightarrow~ c(x) \cdot h(x) = 0$ as stated.
2045
2046
2047 \vspace{0.6cm}
2048 Conversely, suppose $c(x) \cdot h(x) = 0$.
2049
2050 By division algorithm, $c(x) = q(x) \cdot g(x) + r(x)$ with $deg(r) < n-k$.
2051
2052 Then, $c(x) \cdot h(x) = 0$ implies
2053 \begin{align*}
2054 (q(x) \cdot g(x) + r(x)) \cdot h(x) &= 0\\
2055 q(x) \cdot g(x) \cdot h(x) + r(x) \cdot h(x) &= 0\\
2056 \text{recall}~ g(x)\cdot h(x) = x^n -1,~ \text{thus,}&\\
2057 0 + r(x) \cdot h(x) &=0\\
2058 r(x) \cdot h(x) &= 0\\
2059 \text{ie.} r(x) \cdot h(x) = 0 \pmod{x^n-1}
2060 \end{align*}
2061
2062 But $deg(r(x) \cdot h(x)) < n-k +k = n$, so $r(x) \cdot h(x)= 0$ in $\mathbb{F}_q$.
2063
2064 Hence $r(x)=0$, thus
2065 \begin{align*}
2066 c(x) &= q(x) \cdot g(x) \in C\\
2067 &\Longrightarrow~ c(x) \in C
2068 \end{align*}
2069
2070 since $C$ is an ideal of $R_n$ and $g(x) \in C$ and $q(x) \in R_n$.
2071\end{proof}
2072
2073\begin{thm}{12.15}
2074 $C$ cyclic $[n,k]$-code with check polynomial
2075 $$h(x) = h_0 + h_1 x + \ldots + h_k x^k$$
2076
2077 Then
2078 \begin{enumerate}[i.]
2079 \item a PCM for $C$ is
2080 $$H =
2081 \begin{bmatrix}
2082 h_k & h_{k-1} & h_{k-2} & \cdots & h_0 & 0 & 0 & \cdots & 0\\
2083 0 & h_k & h_{k-1} & h_{k-2} & \cdots & h_0 & 0 & \cdots & 0\\
2084 0 & 0 & h_k & h_{k-1} & h_{k-2} & \cdots & h_0 & \cdots & 0\\
2085 & \vdots & & & & & & \vdots\\
2086 0 & 0 & \cdots & 0 & h_k & h_{k-1} & h_{k-2} & \cdots & h_0\\
2087 \end{bmatrix}
2088 $$
2089
2090 \item $C^\perp$ is a cyclic code generated by
2091 $$\bar{h}(x)=h_k + h_{k-1} x + \ldots + h_0 x^k$$
2092 \end{enumerate}
2093\end{thm}
2094
2095\vspace{1.0cm}
2096\subsection{Maximal and minimal cyclic codes}
2097
2098Let $x^n-1 = f_1(x) \cdot f_2(x) \cdot \ldots \cdot f_t(x)$, with $f_i(x)$ irreducible polynomials.
2099
2100\begin{defn}{6.1.6}[maximal and minimal cyclic codes]
2101 the cyclic code generated by $f_i(x)$ is called a \emph{maximal cyclic code} (since it's a maximal ideal), denoted $M_i^+$.
2102
2103 The code generated by $(x^n-1)/f_i(x)$ is called a \emph{minimal cyclic code}, denoted $M_i^-$. Also named \emph{irreducible code}.
2104
2105 \vspace{0.6cm}
2106 ie.
2107 $$M_i^+= \langle f_i(x) \rangle, ~~~~ M_i^-= \big\langle \frac{(x^n-1)}{f_i(x)} \big\rangle$$
2108\end{defn}
2109
2110\vspace{0.5cm}
2111
2112\begin{defn}{}[Zeros of a cyclic code]
2113 Let $x^n-1= f_1(x) \cdot \ldots \cdot f_t(x)$. Let $\beta_i$ be a zero of $f_i(x)$ in some extension field $E \supset \mathbb{F}_q$,\\
2114 \hspace*{2em}ie. $f_i(\beta_i)=0$, with $f_i(x)$ the minimal polynomial of $\beta_i$.
2115\end{defn}
2116
2117$\Longrightarrow~ M_i^+$ is the set of polynomials $c(x)$ for which $c(\beta_i)=0$.
2118
2119\vspace{0.5cm}
2120
2121Specify a cyclic code by requiring all codewords to have certain zeros, ie.\\
2122let the set $\alpha_1, \alpha_2, \ldots, \alpha_s$; define the code $C$ by
2123$$c(x) \in C ~\text{iff}~ c(\alpha_i)=0 ~\forall i \in [s]$$
2124then $C$ cyclic, and the generator polynomial is the lcm of the minimal polynomials of $\alpha_1, \alpha_2, \ldots, \alpha_s$.
2125
2126
2127\vspace{0.6cm}
2128Take the $sm \times n$ matrix with columns $1, \alpha_i, \alpha_i^2, \ldots,
2129\alpha_i^{n-1}$, denoted $H$, with entries in $\mathbb{F}_q$. Then
2130
2131\begin{align*}
2132 cH^T&=0, ~\text{with}~ c=(c_0, c_1, \ldots, c_{n-1})\\
2133 c(\alpha_i)&=0 ~\forall i \in [s], ~\text{with}~ c(x) \in C
2134\end{align*}
2135
2136
2137\subsection{Hamming cyclic codes}
2138\begin{thm}{6.3.1}
2139 let $n := (q^m - 1)/(q-1)$, let $\beta$ a primitive $n$-th root of unity in $\mathbb{F}_{q^m}$. Let $(m, q-1)=1$.
2140
2141 The cyclic code $C:= \{ c(x) | c(\beta)=0 \}$ is equivalent to the $[, n-m]$ Hamming code over $\mathbb{F}_q$.
2142\end{thm}
2143\begin{proof}
2144 since $n=(q-1) \cdot (q^{m-2} + 2 q^{m-3} + \ldots + m-1) + m$ have $(n, q-1) = (m, q-1) = 1$.
2145
2146 Therefore $\beta^{i(q-1)} \neq 1 ~\forall i \in [n]$, ie. $\beta^i \neq \mathbb{F}_q ~\forall i \in [n]$.
2147
2148 Columns of $H$, which are the representations of $1, \beta, \beta^2, \ldots, \beta^{n-1}$ as vectors in $\mathbb{F}_{q^m}$, are pairwise linearly independent over $\mathbb{F}_q$.
2149
2150 So $H$ is the PCM of an $[n, n-m]$ Hamming code.
2151\end{proof}
2152
2153\begin{eg}{6.3.2}
2154 smallest extension of $\mathbb{F}_2$ which contains a primitive 9-th root of unity is $\mathbb{F}_{2^6}$.
2155
2156 Let $\alpha$ a primitive element of the field, then $\alpha^63=1$ ,and $\beta := \alpha^7$ is a primitive 9-th root of unity.
2157
2158 Then, the minimal polynomial of $\beta$ has the zeros
2159 $$\beta, \beta^2, \beta^4, \beta^8, \beta^{16}=\beta^7, \beta^{14}=\beta^5$$
2160
2161 $\Longrightarrow$ min. polynomial: $(x^9 - 1)/(x^3 -1) = x^6 + x^3 + 1$.
2162
2163 So $(x^9-1) = \underbrace{(x-1)}_{f_1(x)} \underbrace{(x^2+x+1)}_{f_2(x)} \underbrace{(x^6+x^3 + 1)}_{f_3(x)}$.
2164
2165 The code $M_3^+$ has pairwise independent columns in $H$, ie. min.distance $\geq 3$.
2166
2167 $M_3^+$ consists of codewords $(c_0 c_1 c_2 ~~ c_0 c_1 c_2 ~~ c_0 c_1 c_2)$, so $d=3$.
2168
2169 The code $M_3^-$ has check polynomial $x^6 + x^3 + 1$, so it's a $[9, 6]$-code.
2170
2171 Since $x^3-1 \in M_3^-$ (is a codeword), the distance is $2$.
2172\end{eg}
2173
2174
2175\subsection{Idempotent of a cyclic code}
2176
2177\begin{thm}{6.4.1}
2178 $\exists!~ c(x) \in C$ which is an identity element for $C$.
2179\end{thm}
2180\begin{proof}
2181 let $g(x)$ generator polynomial, $h(x)$ check polynomial.
2182
2183 ie. $g(x) \cdot h(x) = x^n -1$ in $\mathbb{F}_q[x]$.
2184
2185 Since $x^n -1$ has no multiple zeros (ie. has simple zeros),\\
2186 \hspace*{2em} we have $(g(x), h(x))=1$, hence by the Bezout identity:
2187 $$\exists~ a(x), b(x) \in \mathbb{F}_q[x] ~\text{s.th.}~ a(x) g(x) + b(x) h(x) = gcd(g, h)=1$$
2188
2189 Define $c(x) := a(x) g(x) = 1-b(x) h(x)$.
2190
2191 Clearly $c(x) \in C$. Furthermore, if $p(x) g(x) \in C$ (ie. $p(x)\cdot g(x)$ is any codeword in $C$), then
2192 \begin{align*}
2193 c(x) p(x) g(x) &= \underbrace{(1-b(x)h(x))}_{c(x)} p(x) g(x)\\
2194 &= p(x)g(x) - b(x)h(x)p(x)g(x)\\
2195 &(recall: g(x)h(x)=x^n-1)\\
2196 &= p(x) g(x) - b(x) p(x) \underbrace{g(x) h(x)}_{=x^n-1}\\
2197 &= p(x) g(x) \pmod{x^n -1}
2198 \end{align*}
2199
2200 So $c(x)$ is an identity element for $C$, and hence is unique.
2201\end{proof}
2202
2203Recall:
2204\begin{itemize}
2205 \item[nilpotent] $a \in A$ s.th. $a^n=0$ for $n>0$
2206 \item[idempotent] $e \in A$ s.th. $e^2 = e$
2207\end{itemize}
2208
2209\begin{defn}{6.4.2}[primitive idempotent]
2210 the idempotent of an irreducible cyclic code $M_i^-$ is called a \emph{primitive idempotent}, denoted by $\theta_i(x)$.
2211\end{defn}
2212
2213\begin{thm}{6.4.3}
2214 if $C_1, C_2$ are cyclic codes with idempotents $c_1(x), c_2(x)$, then
2215 \begin{enumerate}[i.]
2216 \item $C_1 \cap C_2$ has idempotent $c_1(x) \cdot c_2(x)$
2217 \item $C_1 + C_2$, ie. the set of all words $a+b$ with $a \in C_1,~ b \in C_2$, has idempotent $c_1(x) + c_2(x) + c_1(x) \cdot c_2(x) \in C_1+C_2$.
2218 \end{enumerate}
2219\end{thm}
2220
2221\begin{thm}{6.4.4}
2222 for the primitive idempotent we have:
2223 \begin{enumerate}[i.]
2224 \item $\theta_i(x) \theta_j(x)=0$ if $i \neq j$
2225 \item $\sum_{i=1}^t \theta_i(x) = 1$
2226 \item $1+ \theta_{i_1}(x) + \theta_{i_2}(x) + \ldots + \theta_{i_r}(x)$ is the idempotent of the code with generator $f_{i_1}(x) \cdot f_{i_2}(x) \cdot \ldots \cdot f_{i_r}(x)$.
2227 \end{enumerate}
2228\end{thm}
2229
2230\subsection{Trace representation}
2231
2232\begin{defn}{1.1.29}
2233 $q=p^r$, trace: $Tr: \mathbb{F}_q \longrightarrow \mathbb{F}_p$.
2234
2235 If $\zeta \in \mathbb{F}_q$, then
2236 $$Tr(\zeta) := \zeta + \zeta^p + \zeta^{p^2} + \ldots + \zeta^{p^{r-1}} \in \mathbb{F}_p$$
2237\end{defn}
2238
2239\begin{thm}{1.1.30} \label{1.1.30}
2240 properties of the trace function:
2241 \begin{enumerate}[i.]
2242 \item $\forall \zeta \in \mathbb{F}_q, ~~ Tr(\zeta) \in \mathbb{F}_p$
2243 \item there are elements $\theta \in \mathbb{F}_p$ such that $Tr(\zeta) \neq 0$
2244 \item $Tr$ is a linear mapping.
2245 \end{enumerate}
2246\end{thm}
2247\begin{proof}
2248 \begin{enumerate}[i.]
2249 \item by definition $(Tr(\zeta))^p = Tr(\zeta)$
2250 \item the equation $x + x^p + \ldots + x^{p^{r-1}}=0$ can not have $q$ roots in $\mathbb{F}_q$
2251 \item since $(\zeta + \eta)^p = \zeta^p + \eta^p$ and $\forall a \in \mathbb{F}_p$ we have $a^p = a$
2252 \end{enumerate}
2253\end{proof}
2254
2255\begin{cor}{}
2256 $Tr$ takes every value $p^{-1}q$ times, and the polynomial $x + x^p + \ldots + x^{p^{r-1}}$ is a product of minimal polynomials.
2257\end{cor}
2258
2259\begin{thm}{6.5.1}
2260 let $k$ be the multiplicative order of $p mod n$, $q = p^k$, $\beta$ a primitive n-th root of unity in $\mathbb{F}_q$.
2261
2262 Then the set
2263 $$V := \{ c(\zeta) := ( Tr(\zeta),~ Tr(\zeta \beta),~ \ldots,~ Tr(\zeta \beta^{n-1})) ~|~ \zeta \in \mathbb{F}_q \}$$
2264 is an $[n, k]$ irreducible code over $\mathbb{F}_p$.
2265\end{thm}
2266\begin{proof}
2267 by Theorem \ref{1.1.30}, $V$ is a linear code, and $c(\zeta \beta^-1)$ is a cyclic shift of $c(\zeta)$; hence $V$ is a cyclic code.
2268
2269 Since $\beta$ is in no subfield of $\mathbb{F}_q$, we know that $\beta$ is a zero of an irreducible polynomial $h(x) = h_0 + h_1 x + \ldots + h_k x^k$.
2270
2271 If $c(\zeta) = (c_0, c_1, \ldots, c_{n-1})$, then
2272 $$\sum_{i=0}^k c_i h_i = Tr(\zeta h(\beta)) = Tr(0) = 0$$
2273 since $\beta$ is a zero of $h(x)$, so that $h(\beta)=0$.
2274
2275
2276 So we observer $c(x) h(x) = 0$, from Theorem \ref{12.14} this means that $h(x)$ is the check polynomial,\\
2277 ie. we have a parity check equation for the code $V$.
2278
2279 Since $h(x)$ irreducible, $x^k \cdot h(x^{-1})$ is the check polynomial for $V$, therefore, $V$ is an irreducible cyclic $[n, k]$-code.
2280\end{proof}
2281
2282\subsection{Mattson-Solomon Polynomial}
2283
2284\begin{defn}{}[Mattson-Solomon polynomial]
2285Let $\beta$ primitive n-th root of unity in the extension field $E$ of $\mathbb{F}_q$.
2286
2287Let $T$ the set of polynomials over $E$ with degree at most $n-1$, ie.
2288$$T = \{ p(x) \in E ~|~ deg(p(x)) \leq n-1 \}$$
2289
2290Define $\Phi: T \longrightarrow T$ as:
2291
2292let $a(x) \in T$, then $A(X) = (\Phi_a)(X)$ is defined by
2293$$A(X) := \sum_{j=1}^n a(\beta^j) X^{n-j}$$
2294
2295If $a=(a_0, a_1, \ldots, a_{n-1})$, the polynomial $A(X)$ obtained from $a_0 + a_1 x + \ldots a_{n-1} x^{n-1}$ is called the \emph{Mattson-Solomon polynomial} of the vector $a$.
2296\end{defn}
2297
2298\begin{lemma}{6.5.3} \label{6.5.3}
2299 the inverse of $\Phi$ is given by
2300 $$a(x) = n^{-1}(\Phi A)(x^{-1}) \pmod{x^n -1}$$
2301\end{lemma}
2302\begin{proof}
2303 $$A(\beta^k) = \sum_{j=1}^n \sum_{i=0}^{n-1} a_i \beta^{ij} \beta^{-kj} = \sum_{i=0}^{n-1} a_i \sum_{j=1}^n \beta^{(i-k)j}=n a_k$$
2304\end{proof}
2305
2306\begin{remark}{}
2307 Notation:
2308 \begin{itemize}
2309 \item[] $\circ$: multiplication of polynomials $mod (x^n -1)$
2310 \item[] $*$: defined by
2311 $$(\sum a_i x^i) * (\sum b_i x^i) := \sum a_i b_i x^i$$
2312 \end{itemize}
2313
2314 $\Phi$ is an isomorphism of the ring $(T, +, \circ)$ onto the ring $(T, +, *)$.
2315\end{remark}
2316
2317\begin{lemma}{6.5.4} \label{6.5.4}
2318 let $V$ a cyclic code over $\mathbb{F}_q$ generated by
2319 $$g(x) = \prod_{k \in K} (x - \beta^k)$$
2320
2321 Suppose $\{1, 2, \ldots, d-1 \} \subset K$ and $a \in V$.
2322
2323 Then the degree of the Mattson-Solomon polynomial $A$ of $a$ is at most $n-d$.
2324\end{lemma}
2325\begin{proof}
2326 $a(\beta^j) = 0$ for $j \in [d]$ since $g(x)|a(x)$.
2327
2328 Thus at the equation $A(X) := \sum_{j=1}^n a(\beta^j) X^{n-j}$, it will be $0$ between $1 \leq j \leq d-1$, so that degree is $n-d$.
2329\end{proof}
2330
2331\begin{thm}{6.5.5} \label{6.5.5}
2332 if there are $r$ n-th roots of unity which are zeros of the Mattson-Solomon polynomial $A$ of a word $a$, then $w(a) = n-r$.
2333\end{thm}
2334\begin{proof}
2335 consequence of Lemma \ref{6.5.3}.
2336\end{proof}
2337
2338
2339
2340\vspace{1.0cm}
2341\section{BCH Codes}
2342
2343\begin{defn}{6.6.1}[BCH Code]
2344 a cyclic code of length $n$ over $\mathbb{F}_q$ is called \emph{BCH code of designed distance $\delta$} if its generator $g(x)$ is the lcm of the minimal polynomials of $\beta^l, \beta^{l+1}, \ldots, \beta^{l+\delta-2}$ for some $l$, where $\beta$ is a primitive n-th root of unity.
2345\end{defn}
2346
2347Usually $l=1$; if $n=q^m-1$ (ie. $\beta$ a primitive element of $\mathbb{F}_q^m$), then the BCH code is called \emph{primitive}.
2348
2349
2350\begin{thm}{6.6.2}[BCH Bound] \label{6.6.2}
2351 the minimum distance of a BCH code with designed distance $d$ is $\geq d$.
2352\end{thm}
2353\begin{proof}
2354 wlog. take $l=1$. By Lemma \ref{6.5.4}, the degree of the Mattson-Solomon polynomial $A$ of a codeword $c$ is $deg(A) \leq n-d$.
2355
2356 Therefore, in theorem \ref{6.5.5} we have $r \leq n-d$, ie. $w(c) \geq d$.
2357
2358 (recall: $r$ is the amount of n-th roots of unity which are zeros of the M-S polynomial $A$)
2359\end{proof}
2360
2361
2362\begin{defn}{}[Defining set]
2363 If $A = \{ \alpha^{i_1}, \ldots, \alpha^{i_l} \}$ is a set of n-th roots of unity such that
2364 $$c(x) \in C \Longleftrightarrow \forall \zeta \in A ~ c(\zeta)=0$$
2365 we say that $A$ is the \emph{defining set} for $C$.
2366
2367 If $A$ is the \emph{maximal} defining set for $C$, we call $A$ \emph{complete}.
2368\end{defn}
2369
2370\begin{defn}{6.6.3}
2371 $M(A)$ or $M(\alpha^{i_1}, \ldots, \alpha^{i_l})$: matrix $l \times n$ that has $1, \alpha^{i_k}, \alpha^{2 i_k}, \ldots, \alpha^{(n-1)i_k}$ as its k-th rows, ie.
2372
2373 $$M(A) = \begin{bmatrix}
2374 1 & \alpha^{i_1} & \alpha^{2 i_1} & \cdots & \alpha^{(n-1) i_1}\\
2375 1 & \alpha^{i_2} & \alpha^{2 i_2} & \cdots & \alpha^{(n-1) i_2}\\
2376 \vdots & & & & \vdots\\
2377 1 & \alpha^{i_l} & \alpha^{2 i_l} & \cdots & \alpha^{(n-1) i_l}\\
2378 \end{bmatrix}
2379 $$
2380
2381 $M(A)$ is the PCM corresponding to $A$.
2382\end{defn}
2383
2384
2385
2386\begin{thm}{6.6.13}
2387 The primitive binary BCH code $C$ of length $n=2^m-1$ and designed distance $\delta = 2^l -1$ has minimum distance $\delta$.
2388\end{thm}
2389\begin{cor}{6.6.14}
2390 a primitive BCH code of designed distance $\delta$ has distance $d \leq 2 \delta -1$.
2391\end{cor}
2392\begin{cor}{6.6.16}
2393 the minimum weight of a primitive binary BCH code is odd.
2394\end{cor}
2395
2396
2397
2398
2399\section{Reed-Solomon Codes}
2400
2401\begin{defn}{6.8.1}[Reed-Solomon code]
2402 a \emph{Reed-Solomon code} (RS code) is a primitive BCH code of length $n=q-1$ over $\mathbb{F}_q$.
2403
2404 With generator
2405 $$g(x) = \prod_{i=1}^{d-1} (x - \alpha^i)$$
2406 where $\alpha$ is primitive in $\mathbb{F}_q$.
2407\end{defn}
2408
2409\begin{remark}{}observe:\\
2410 \begin{itemize}
2411 \item by \ref{6.6.2}, minimum distance $\geq d$
2412 \item by 6.2, has dimension $k=n-d+1$
2413 \end{itemize}
2414 Therefore, Corollary 5.2.2 implies that minimum distance is $d$ and the RS code is a MDS.
2415
2416 This is useful for when errors are in bursts (ie. several errors together).
2417\end{remark}
2418
2419\vspace{0.6cm}
2420Let $n=q-1$, $\alpha$ a primitive element of $\mathbb{F}_q$.
2421
2422$$a=(a_0, a_1, \ldots, a_{k-1}) \in \mathbb{F}_q^k \Longleftrightarrow a(x) = a_0 + a_1 x + \ldots + a_{k-1}x^{k-1}$$
2423
2424Then
2425$$C= \{ (c_0, c_1, \ldots, c_{n-1}) ~|~ c_i = a(\alpha^i),~ 0 \leq i <n,~ a \in \mathbb{F}_q^k \}$$
2426is the RS code with $d = n - k +1$.
2427
2428To see it: $C$ is cyclic. By definition of $C$ and Lemma \ref{6.5.3}, implies that a codeword $c$ has $n \cdot a(x)$ as its Mattson-Solomon polynomial.
2429
2430Since $deg(a(x)) \leq k-1$,
2431$$c(\alpha^i) = 0 ~~\forall i \in [1, n-k]$$
2432
2433Extend the words of $C$ by adjoining a symbol $c_n = a(0)$, then
2434$$\sum_{i=0}^n c_i = a_0 q = 0$$
2435$\Longrightarrow~$ we obtain $\overline{C}$.
2436
2437
2438If $c_n=0$, ie. $c(1)=0$, then the word has weight $\geq n-k+2$. Also true if $c_n \neq 0$.
2439$\Longrightarrow~$ so $\overline{C}$ is also a MDS code.
2440
2441
2442\begin{defn}{6.8.2}
2443 the generalized R-S code, $GRS_k(a, v)$, has codewords all
2444 $$(v_1 f(\alpha_1), v_2 f(\alpha_2), \ldots, v_n f(\alpha_n))$$
2445 where $f$ runs through the set of polynomials of degree $<k$ in $\mathbb{F}_{q^m}[X]$, ie. $f \in \mathbb{F}_{q^m}[X]^{<k}$.
2446\end{defn}
2447
2448A GRS and its dual are MDS codes.
2449
2450\begin{thm}{6.8.3}
2451 the dual of an MDS code is also an MDS code.
2452\end{thm}
2453\begin{proof}
2454 let $G=(I_k~ P)$ be GM of $C$.
2455
2456 Since $C$ has min. weight $d$, every set of $d-1=n-k$ columns of the PCM $H:=(-P^T ~ I_{n-k})$ is linearly independent.
2457
2458 Hence every square submatrix of $H$ is nonsingular, ie. no codeword of $C^{\perp}$ has $n-k$ zeros.
2459
2460 So $C^{\perp}$ is an $[n, n-k, k+1]$ code, ie. MDS.
2461\end{proof}
2462
2463
2464
2465\vspace{1.0cm}
2466\subsection{Example of Hamming code (cyclic) and of Reed-Solomon code (cyclic and MDS)}
2467
2468\paragraph{(7,4)-Hamming code over $\mathbb{F}_2$}
2469
2470$$(n, k) \Longrightarrow~ n=7 (\text{length}), k=4 (\text{message length})$$
2471
2472Generator polynomial: $g(x) = x^3 + x +1$.
2473
2474Parity bits: $r=3$
2475
2476Message: $m(x) \in \mathbb{F}_2[X]^{\leq 3}$, encoded as $c(x) = m(x) g(x) \pmod{(x^7-1)}$
2477
2478eg: for $m(x) = x^3 + x + 1$,
2479$$c(x) = (x^3 + x +1) \cdot (x^3 +x+1) \pmod({x^7-1}) = x^6 + x^2 + 1$$
2480$$\Longrightarrow~ c=(1000101)$$
2481
2482Hamming code is cyclic:\\
2483when $c(x) \in C$, then $x \cdot c(x) \pmod({x^n-1}) \in C$,
2484
2485because $C=\langle g(x) \rangle$, ie. all codewords are multiples of $g(x)$,
2486
2487so for $c(x) = m(x) \cdot g(x)$, then
2488$$x \cdot c(x) = x \cdot m(x) \cdot g(x)$$
2489is still a multiple of $g(x)$, hence a valid codeword.
2490
2491
2492\paragraph{(6,4)-Reed-Solomon code over $\mathbb{F}_7$}
2493
2494$$n=6,~ k=4,~ \text{minimum distance:}~ d=n-k+1 = 6-4+1 = 3$$
2495
2496Choose a primitive element, $\alpha=3 \in \mathbb{F}_7$.
2497
2498Generator polynomial:
2499\begin{align*}
2500 g(x) &= (x-\alpha) \cdot (x - \alpha^2)\\
2501 &= x^2 -2x -3x +6\\
2502 &= x^2 -5x +6 = x^2 +2x +6 \pmod{7}
2503\end{align*}
2504
2505message: $m(x) = 1 + 2x + x^2 + x^3$
2506
2507Then,
2508\begin{itemize}
2509 \item[cyclic form:] $c(x) = m(x) g(x) \pmod{(x^6-1)}$\\
2510 $c(x) \in C$ iff $c(\alpha^i)=0 ~\forall~ i \in [n-k]$
2511\item[evaluation form:] $c = (m(1), m(\alpha), m(\alpha^2), \ldots, m(\alpha^6))$
2512\end{itemize}
2513
2514RS code is cyclic. And it is MDS:
2515\begin{itemize}
2516 \item a polynomial of degree $<k$ is uniquely determined by $k$ points
2517 \item if two polynomials agree in $k$ positions, are the same polynomial\\
2518 $\Longrightarrow$ maximum number of equal positions between distinct codewords $= k-1$
2519\end{itemize}
2520
2521Therefore, $d=n-(k-1) = n-k+1$, ie. Singleton bound (with equality!).
2522
2523
2524
2525
2526\bibliographystyle{unsrt}
2527\bibliography{algebraic-coding-theory-notes.bib}
2528
2529\end{document}