1\documentclass{article}
  2\usepackage[utf8]{inputenc}
  3\usepackage{amsfonts}
  4% \usepackage{yfonts} % WIP
  5\usepackage{amsthm}
  6\usepackage{amsmath}
  7\usepackage{enumerate}
  8\usepackage{hyperref}
  9\usepackage{amssymb}
 10\usepackage{tikz} % diagram
 11
 12\begin{filecontents}[overwrite]{algebraic-coding-theory-notes.bib}
 13@misc{hill,
 14  author = {Raymond Hill},
 15  title = {{A First Course in Coding Theory}},
 16  year = {1986}
 17}
 18@misc{lint,
 19  author = {J.H. van Lint},
 20  title = {{Introduction to Coding Theory}},
 21  year = {1981}
 22}
 23\end{filecontents}
 24\nocite{*}
 25
 26
 27\theoremstyle{definition}
 28
 29\newtheorem{innerdefn}{Definition}
 30\newenvironment{defn}[1]
 31{\renewcommand\theinnerdefn{#1}\innerdefn}
 32{\endinnerdefn}
 33
 34\newtheorem{innerthm}{Theorem}
 35\newenvironment{thm}[1]
 36{\renewcommand\theinnerthm{#1}\innerthm}
 37{\endinnerthm}
 38
 39\newtheorem{innerlemma}{Lemma}
 40\newenvironment{lemma}[1]
 41{\renewcommand\theinnerlemma{#1}\innerlemma}
 42{\endinnerlemma}
 43
 44\newtheorem{innerprop}{Proposition}
 45\newenvironment{prop}[1]
 46{\renewcommand\theinnerprop{#1}\innerprop}
 47{\endinnerprop}
 48
 49\newtheorem{innercor}{Corollary}
 50\newenvironment{cor}[1]
 51{\renewcommand\theinnercor{#1}\innercor}
 52{\endinnercor}
 53
 54\newtheorem{innereg}{Example}
 55\newenvironment{eg}[1]
 56{\renewcommand\theinnereg{#1}\innereg}
 57{\endinnereg}
 58
 59\newtheorem{innerex}{Exercise}
 60\newenvironment{ex}[1]
 61{\renewcommand\theinnerex{#1}\innerex}
 62{\endinnerex}
 63
 64% custom shortcuts
 65\newcommand{\Vnq}{V(n, q)}
 66
 67\title{Algebraic Coding Theory}
 68\author{arnaucube}
 69\date{2026}
 70
 71\begin{document}
 72
 73\maketitle
 74
 75\begin{abstract}
 76    Notes taken while studying Algebraic Coding Theory, mostly from Hill book \cite{hill} and Lint book \cite{lint}.
 77
 78    Usually while reading books and papers I take handwritten notes in a notebook, this document contains some of them re-written to $LaTeX$.
 79
 80    The proofs may slightly differ from the ones from the books, since I try to extend them for a deeper understanding.
 81\end{abstract}
 82
 83\tableofcontents
 84
 85
 86\section{Vector spaces over finite fields, quick recap}
 87Let $q$ be a prime power. 
 88
 89$\Vnq$: set $GF(q)^n$ of all ordered $n$-tuples over $GF(q)$. $\Vnq$ is a
 90vector space.
 91
 92A 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
 93$$a_1 v_1 + a_2 v_2 + \ldots + a_r v_r = 0$$
 94
 95They are \emph{linear independent} if
 96$$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$$
 97
 98Let $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$.
 99
100A generating set of $C$ which is also linearly independent is called a \emph{basis} of $C$.
101
102\section{Linear codes}
103The theorems of this section are from \cite{hill} and follow the original enumeration of the book.
104
105\subsection{Some definitions}
106Let $q$ be a prime power. View $(Fq)^n$ as the vector space $\Vnq$.
107
108\begin{defn}{}[Linear code over GF(q)]
109  A \emph{linear code over $GF(q)$} is a subspace of $\Vnq$, with $n \geq 0$.
110\end{defn}
111
112Thus $C \subseteq \Vnq$ is a linear code iff
113\begin{enumerate}[i.]
114  \item $u+v \in C ~~ \forall u,v \in C$
115  \item $au \in C ~~ \forall u \in C,~ a \in GF(q)$
116\end{enumerate}
117
118If $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).
119
120\begin{defn}{}[Weight]
121  Weight, $w(x)$, of a vector $x \in \Vnq$ is the number of non-zero entries of $x$.
122\end{defn}
123
124\begin{lemma}{5.1}\label {h.5.1}
125  if $x,y \in \Vnq$, then $d(x,y)=w(x-y)$.
126\end{lemma}
127\begin{proof}
128  the vector $x-y$ has non-zero entries in preceisely those places where $x$ and $y$ differ.
129\end{proof}
130
131\begin{thm}{5.2}
132  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)$.
133\end{thm}
134\begin{proof}
135  $\exists~ x,y \in C$ s.th. $d(C)=d(x,y)$.
136
137  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$).
138
139  On the other hand, for $x \in C$,\\
140  $w(C)=w(x)=d(x,0) \geq d(C)$, since $0 \in C$.
141
142  Hence, $d(C) \geq w(C)$ and $w(C) \geq d(C) ~~\Longrightarrow~ d(C)=w(C)$.
143\end{proof}
144
145
146\begin{defn}{}[Generator matrix (GM)]
147  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.
148\end{defn}
149
150\subsection{Equivalence}
151
152\begin{thm}{5.4}
153  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:
154  \begin{enumerate}
155    \item[R1.] permutation of the rows
156    \item[R2.] multiplication of a row by a non-zero scalar
157    \item[R3.] addition of a scalar multiple of one row to another
158    \item[C1.] permutation of the columns
159    \item[C2.] multiplication of any column by a non-zero scalar
160  \end{enumerate}
161\end{thm}
162
163\begin{thm}{5.5} \label{h.5.5}
164  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 ]$
165  where $I_k$ is the $k \times k$ identity matrix, and $A$ is a $k \times (n-k)$ matrix.
166\end{thm}
167
168\subsection{Encoding with a linear code}
169Let $C$ a $[n,k]$-code over $GF(q)$ with GM $G$. $C$ contains $q^k$ codewords $\Longrightarrow$ can be used to comunicate any one of $q^k$ distinct messages.
170
171Iddentify these messages with the $q^k$ tuples of $V(k,q)$.
172
173Encoding:\\
174msg vector: $u=u_1 u_2 \ldots u_k$; rows of $G$: $r_1 r_2 \ldots r_k$. Encode
175$$uG = \sum^k_{i=1} u_i r_i \in C$$
176ie. $uG$ is a codeword of $C$; a linear combination of the rows of the GM.
177
178Encoding function:
179\begin{align*}
180  V(k,q) &\longrightarrow C \subseteq \Vnq\\
181  u &\longmapsto uG
182\end{align*}
183
184If $G$ is in standard form (\ref{h.5.5}), $G= [I_k | A]$ with $A=[a_{ij}]$, then encoding $u$ is:
185$$x=uG = x_1x_2 \ldots x_k x_{k+1} \ldots x_n$$
186where
187\begin{align*}
188  &x_i=u_i ~~\text{for}~ 1 \leq i \leq k, ~\text{message digits}\\
189  &x_{k+i}=\sum^k_{j=1}~ a_ji u_j ~~\text{for}~ 1 \leq i \leq n-k, ~\text{check digits}\\
190\end{align*}
191
192the check digits add redundancy to gie protection against noise.
193
194\subsection{Decoding with a linear code}
195Codeword $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$.
196
197\subsubsection{Cosets}
198Cosets here are similar to the ones from typical group theory, just from another perspective.
199
200\begin{defn}{}[Coset]
201  Let $C$ a $[n,k]$-code over $GF(q)$ and $a \in \Vnq$.
202  Then the set $a + C = \{a+x | x\in C\}$ is called a \emph{coset} of $C$.
203\end{defn}
204
205\begin{defn}{}[Coset leader]
206  the vector having minimum weight in a coset is called the \emph{coset leader}.
207\end{defn}
208
209\begin{lemma}{6.3} \label{h.6.3}
210  Let $a+C$ a coset of $C$ and $b \in a+C$. Then $b+C=a+C$.
211\end{lemma}
212\begin{proof}
213  since $b \in a+C ~~\Longrightarrow~~ b=a+x$ for some $x \in C$.
214  If $b+y \in b+C$ then
215  $$b+y=(a+x)+y = a+(x+y) \in a+C$$
216
217  For the other direction, if $a+x \in a+C$ then
218  $$a+x=(b-x)+z = b+(z-x) \in b+C$$
219  hence $a+C \subseteq b+C$.
220
221  Therefore $b+C = a+C$.
222\end{proof}
223
224\begin{thm}{6.4}[Lagrange] \label{h.6.4}
225  suppose $C \subseteq \Vnq$ is a $[n,k]$-code over $GF(q)$. Then
226  \begin{enumerate}[i.]
227    \item evvery vector of $\Vnq$ is in some coset of $C$
228    \item every coset contains exactly $q^k$ vectors
229    \item two cosets either are disjoint or coincide (partial overlap is impossible)
230  \end{enumerate}
231\end{thm}
232\begin{proof}
233  \begin{enumerate}[i.]
234    \item if $a\in \Vnq$ then $a=a+0 \in a+C$
235    \item the map
236      \begin{align*}
237        C &\longrightarrow a+C ~\forall~ x \in C\\
238        x &\longmapsto a+x
239      \end{align*}
240      is a one-to-one map, hence $|a+C| = |C| = q^k$.
241    \item by contradiction, suppose cosets $a+C,~ b+C$ overlap. Then for some vector $v$,
242      $$v \in (a+C) \cap (b+C)$$
243      thus for some $x,y \in C$, $v=a+x=b+y$.
244
245      Hence $b=a+(x-y) \in a+C$, thus by Lemma \ref{h.6.3} we have $b+C=a+C$.
246  \end{enumerate}
247\end{proof}
248
249\begin{cor}{}
250  \ref{h.6.4} shows that $\Vnq$ is partitioned into disjoint cosets of $C$:
251  $$\Vnq = (0+C) \cup (a_1+C) \cup \ldots \cup (a_s +C)$$
252  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.
253\end{cor}
254
255\begin{eg}{6.5} \label{h.6.5}
256  Let $C$ be the binary $[4,2]$-code with generator matrix
257$$
258G = \begin{pmatrix}
2591 & 0 & 1 & 1 \\
2600 & 1 & 0 & 1
261\end{pmatrix}
262$$
263
264ie.
265$C = \{0000,\, 1011,\, 0101,\, 1110\}$.
266
267Then the cosets of $C$ are
268\begin{align*}
269  0000 + C &= C \text{ itself}\\
270  1000 + C &= \{1000,\, 0011,\, 1101,\, 0110\}\\
271  0100 + C &= \{0100,\, 1111,\, 0001,\, 1010\} = 0001+C\\
272  0010 + C &= \{0010,\, 1001,\, 0111,\, 1100\}
273\end{align*}
274
275by Lemma \ref{h.6.3}: $0001 \in 0100 + C$, thus $0001+C=0100+C$.
276\end{eg}
277
278\subsection{Probability of error correction (in binary linear codes)}
279To evaluate how good a code is, must calculate the \emph{probability} that a received vector will be decoded as the codeword which was sent.
280
281Let $p$ be the symbol error probability.
282
283Probability that the error vector is agiven vector of weight $i$ is $p^i (1-p){n-i}$.
284
285\begin{thm}{6.7}
286  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$.
287
288  Then the probability $P_{corr}(C)$ that a received vector decoded by means of a standard array is the codeword which was sent is
289  $$P_{corr}(C) = \sum_{i=0}^n \alpha_i \cdot p^i(1-p)^{n-i}$$
290\end{thm}
291
292\begin{eg}{6.8}
293  $[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
294  $$P_{corr}(C) = (1-p)^4 + 3 p(1-p)^3 = (1-p)^3 (1+2p)$$
295\end{eg}
296
297\begin{lemma}{6.9}[Remark 6.9]
298  if $d(C)=2t+1$ or $d(C)=2t+2$, then $C$ can correct any $t$ errors.
299
300  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$.
301\end{lemma}
302
303\begin{defn}{}[Rate]
304  $[n, k]$-code $C$ uses $n$ symbols to send $k$ message symbols; it has \emph{rate} $R(C)=k/n$.
305
306  A good code will have a high rate.
307\end{defn}
308
309\begin{defn}{}[Capacity]
310  the \emph{capacity} $\mathfrak{C}(p)$ of a binary symmetric channel with symbol error probability $p$ is
311  $$\mathfrak{C}(p) = 1+ p \cdot \log_2{(p)} + (1-p) \cdot \log_2{(1-p)}$$
312\end{defn}
313
314\begin{thm}{6.12}[Shanon's theorem]
315\end{thm}
316
317
318\bibliographystyle{unsrt}
319\bibliography{algebraic-coding-theory-notes.bib}
320
321\end{document}