1\documentclass{article}
  2\usepackage[utf8]{inputenc}
  3\usepackage{amsfonts}
  4% \usepackage{yfonts} % WIP
  5\usepackage{amsthm}
  6\usepackage{amsmath}
  7\usepackage{mathrsfs}
  8\usepackage{enumerate}
  9\usepackage{hyperref}
 10\usepackage{amssymb}
 11\usepackage{tikz} % diagram
 12
 13\begin{filecontents}[overwrite]{algebraic-coding-theory-notes.bib}
 14@misc{hill,
 15  author = {Raymond Hill},
 16  title = {{A First Course in Coding Theory}},
 17  year = {1986}
 18}
 19@misc{lint,
 20  author = {J.H. van Lint},
 21  title = {{Introduction to Coding Theory}},
 22  year = {1981}
 23}
 24\end{filecontents}
 25\nocite{*}
 26
 27
 28\theoremstyle{definition}
 29
 30\newtheorem{innerdefn}{Definition}
 31\newenvironment{defn}[1]
 32{\renewcommand\theinnerdefn{#1}\innerdefn}
 33{\endinnerdefn}
 34
 35\newtheorem{innerthm}{Theorem}
 36\newenvironment{thm}[1]
 37{\renewcommand\theinnerthm{#1}\innerthm}
 38{\endinnerthm}
 39
 40\newtheorem{innerlemma}{Lemma}
 41\newenvironment{lemma}[1]
 42{\renewcommand\theinnerlemma{#1}\innerlemma}
 43{\endinnerlemma}
 44
 45\newtheorem{innerprop}{Proposition}
 46\newenvironment{prop}[1]
 47{\renewcommand\theinnerprop{#1}\innerprop}
 48{\endinnerprop}
 49
 50\newtheorem{innercor}{Corollary}
 51\newenvironment{cor}[1]
 52{\renewcommand\theinnercor{#1}\innercor}
 53{\endinnercor}
 54
 55\newtheorem{innereg}{Example}
 56\newenvironment{eg}[1]
 57{\renewcommand\theinnereg{#1}\innereg}
 58{\endinnereg}
 59
 60\newtheorem{innerex}{Exercise}
 61\newenvironment{ex}[1]
 62{\renewcommand\theinnerex{#1}\innerex}
 63{\endinnerex}
 64
 65% custom shortcuts
 66\newcommand{\Vnq}{V(n, q)}
 67
 68\title{Algebraic Coding Theory}
 69\author{arnaucube}
 70\date{2026}
 71
 72\begin{document}
 73
 74\maketitle
 75
 76\begin{abstract}
 77    Notes taken while studying Algebraic Coding Theory, mostly from Hill book \cite{hill} and Lint book \cite{lint}.
 78
 79    Usually while reading books and papers I take handwritten notes in a notebook, this document contains some of them re-written to $LaTeX$.
 80
 81    The proofs may slightly differ from the ones from the books, since I try to extend them for a deeper understanding.
 82\end{abstract}
 83
 84\tableofcontents
 85
 86
 87\section{Vector spaces over finite fields, quick recap}
 88Let $q$ be a prime power. 
 89
 90$\Vnq$: set $GF(q)^n$ of all ordered $n$-tuples over $GF(q)$. $\Vnq$ is a
 91vector space.
 92
 93A 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
 94$$a_1 v_1 + a_2 v_2 + \ldots + a_r v_r = 0$$
 95
 96They are \emph{linear independent} if
 97$$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$$
 98
 99Let $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$.
100
101A generating set of $C$ which is also linearly independent is called a \emph{basis} of $C$.
102
103\begin{thm}{4.3}
104  Suppose $\{v_1, v_2, \ldots, v_k\}$ is a basis of a subspace $C$ of $\Vnq$. Then  
105  \begin{enumerate}[i.]
106  \item every vector of $C$ can be expressed uniquely as a linear combination of the basis vectors.
107  \item $C$ contains exactly $q^k$ vectors.
108  \end{enumerate}
109\end{thm}
110\begin{proof}
111  \begin{enumerate}[i.]
112\item suppose vector $x \in C$ such that
113$$x = a_1 v_1 + a_2 v_2 + \cdots + a_k v_k$$
114$$x = b_1 v_1 + b_2 v_2 + \cdots + b_k v_k .$$
115
116then
117$$(a_1-b_1)v_1 + (a_2-b_2)v_2 + \cdots + (a_k-b_k)v_k = 0 .$$
118
119But the set $\{v_1, v_2, \ldots, v_k\}$ is linearly independent, and so
120$$a_i - b_i = 0 \quad \text{for } i = 1,2,\ldots,k,$$
121i.e.,
122$$a_i = b_i \quad \text{for } i = 1,2,\ldots,k.$$
123
124\item By (i), the $q^k$ vectors
125$$\sum_{i=1}^{k} a_i v_i \qquad (a_i \in \mathrm{GF}(q))$$
126are precisely the distinct vectors of $C$.
127\end{enumerate}
128\end{proof}
129
130
131\section{Linear codes}
132The theorems of this section are from \cite{hill} and follow the original enumeration of the book.
133
134Note about notation:\\
135A $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.
136
137\subsection{Some definitions}
138Let $q$ be a prime power. View $(F_q)^n$ as the vector space $\Vnq$.
139
140\begin{defn}{}[Linear code over GF(q)]
141  A \emph{linear code over $GF(q)$} is a subspace of $\Vnq$, with $n \geq 0$.
142\end{defn}
143
144Thus $C \subseteq \Vnq$ is a linear code iff
145\begin{enumerate}[i.]
146  \item $u+v \in C ~~ \forall u,v \in C$
147  \item $au \in C ~~ \forall u \in C,~ a \in GF(q)$
148\end{enumerate}
149
150If $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).
151
152\begin{defn}{}[Weight]
153  Weight, $w(x)$, of a vector $x \in \Vnq$ is the number of non-zero entries of $x$.
154\end{defn}
155
156\begin{lemma}{5.1}\label {h.5.1}
157  if $x,y \in \Vnq$, then $d(x,y)=w(x-y)$.
158\end{lemma}
159\begin{proof}
160  the vector $x-y$ has non-zero entries in preceisely those places where $x$ and $y$ differ.
161\end{proof}
162
163\begin{thm}{5.2}
164  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)$.
165\end{thm}
166\begin{proof}
167  $\exists~ x,y \in C$ s.th. $d(C)=d(x,y)$.
168
169  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$).
170
171  On the other hand, for $x \in C$,\\
172  $w(C)=w(x)=d(x,0) \geq d(C)$, since $0 \in C$.
173
174  Hence, $d(C) \geq w(C)$ and $w(C) \geq d(C) ~~\Longrightarrow~ d(C)=w(C)$.
175\end{proof}
176
177
178\begin{defn}{}[Generator matrix (GM)]
179  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.
180\end{defn}
181
182\subsection{Equivalence}
183
184\begin{thm}{5.4}
185  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:
186  \begin{enumerate}
187    \item[R1.] permutation of the rows
188    \item[R2.] multiplication of a row by a non-zero scalar
189    \item[R3.] addition of a scalar multiple of one row to another
190    \item[C1.] permutation of the columns
191    \item[C2.] multiplication of any column by a non-zero scalar
192  \end{enumerate}
193\end{thm}
194
195\begin{thm}{5.5} \label{h.5.5}
196  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 ]$
197  where $I_k$ is the $k \times k$ identity matrix, and $A$ is a $k \times (n-k)$ matrix.
198\end{thm}
199
200\subsection{Encoding with a linear code}
201Let $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.
202
203Iddentify these messages with the $q^k$ tuples of $V(k,q)$.
204
205Encoding:\\
206msg vector: $u=u_1 u_2 \ldots u_k$; rows of $G$: $r_1 r_2 \ldots r_k$. Encode
207$$uG = \sum^k_{i=1} u_i r_i \in C$$
208ie. $uG$ is a codeword of $C$; a linear combination of the rows of the GM.
209
210Encoding function:
211\begin{align*}
212  V(k,q) &\longrightarrow C \subseteq \Vnq\\
213  u &\longmapsto uG
214\end{align*}
215
216If $G$ is in standard form (\ref{h.5.5}), $G= [I_k | A]$ with $A=[a_{ij}]$, then encoding $u$ is:
217$$x=uG = x_1x_2 \ldots x_k x_{k+1} \ldots x_n$$
218where
219\begin{align*}
220  &x_i=u_i ~~\text{for}~ 1 \leq i \leq k, ~\text{message digits}\\
221  &x_{k+i}=\sum^k_{j=1}~ a_ji u_j ~~\text{for}~ 1 \leq i \leq n-k, ~\text{check digits}\\
222\end{align*}
223
224the check digits add redundancy to gie protection against noise.
225
226\subsection{Decoding with a linear code}
227Codeword $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$.
228
229\subsubsection{Cosets}
230Cosets here are similar to the ones from typical group theory, just from another perspective.
231
232\begin{defn}{}[Coset]
233  Let $C$ a $[n,k]$-code over $GF(q)$ and $a \in \Vnq$.
234  Then the set $a + C = \{a+x | x\in C\}$ is called a \emph{coset} of $C$.
235\end{defn}
236
237\begin{defn}{}[Coset leader]
238  the vector having minimum weight in a coset is called the \emph{coset leader}.
239\end{defn}
240
241\begin{lemma}{6.3} \label{h.6.3}
242  Let $a+C$ a coset of $C$ and $b \in a+C$. Then $b+C=a+C$.
243\end{lemma}
244\begin{proof}
245  since $b \in a+C ~~\Longrightarrow~~ b=a+x$ for some $x \in C$.
246  If $b+y \in b+C$ then
247  $$b+y=(a+x)+y = a+(x+y) \in a+C$$
248
249  For the other direction, if $a+x \in a+C$ then
250  $$a+x=(b-x)+z = b+(z-x) \in b+C$$
251  hence $a+C \subseteq b+C$.
252
253  Therefore $b+C = a+C$.
254\end{proof}
255
256\begin{thm}{6.4}[Lagrange] \label{h.6.4}
257  suppose $C \subseteq \Vnq$ is a $[n,k]$-code over $GF(q)$. Then
258  \begin{enumerate}[i.]
259    \item evvery vector of $\Vnq$ is in some coset of $C$
260    \item every coset contains exactly $q^k$ vectors
261    \item two cosets either are disjoint or coincide (partial overlap is impossible)
262  \end{enumerate}
263\end{thm}
264\begin{proof}
265  \begin{enumerate}[i.]
266    \item if $a\in \Vnq$ then $a=a+0 \in a+C$
267    \item the map
268      \begin{align*}
269        C &\longrightarrow a+C ~\forall~ x \in C\\
270        x &\longmapsto a+x
271      \end{align*}
272      is a one-to-one map, hence $|a+C| = |C| = q^k$.
273    \item by contradiction, suppose cosets $a+C,~ b+C$ overlap. Then for some vector $v$,
274      $$v \in (a+C) \cap (b+C)$$
275      thus for some $x,y \in C$, $v=a+x=b+y$.
276
277      Hence $b=a+(x-y) \in a+C$, thus by Lemma \ref{h.6.3} we have $b+C=a+C$.
278  \end{enumerate}
279\end{proof}
280
281\begin{cor}{}
282  \ref{h.6.4} shows that $\Vnq$ is partitioned into disjoint cosets of $C$:
283  $$\Vnq = (0+C) \cup (a_1+C) \cup \ldots \cup (a_s +C)$$
284  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.
285\end{cor}
286
287\begin{eg}{6.5} \label{h.6.5}
288  Let $C$ be the binary $[4,2]$-code with generator matrix
289$$
290G = \begin{pmatrix}
2911 & 0 & 1 & 1 \\
2920 & 1 & 0 & 1
293\end{pmatrix}
294$$
295
296ie.
297$C = \{0000,\, 1011,\, 0101,\, 1110\}$.
298
299Then the cosets of $C$ are
300\begin{align*}
301  0000 + C &= C \text{ itself}\\
302  1000 + C &= \{1000,\, 0011,\, 1101,\, 0110\}\\
303  0100 + C &= \{0100,\, 1111,\, 0001,\, 1010\} = 0001+C\\
304  0010 + C &= \{0010,\, 1001,\, 0111,\, 1100\}
305\end{align*}
306
307by Lemma \ref{h.6.3}: $0001 \in 0100 + C$, thus $0001+C=0100+C$.
308\end{eg}
309
310\subsection{Probability of error correction (in binary linear codes)}
311To evaluate how good a code is, must calculate the \emph{probability} that a received vector will be decoded as the codeword which was sent.
312
313Let $p$ be the symbol error probability.
314
315Probability that the error vector is agiven vector of weight $i$ is $p^i (1-p){n-i}$.
316
317\begin{thm}{6.7}
318  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$.
319
320  Then the probability $P_{corr}(C)$ that a received vector decoded by means of a standard array is the codeword which was sent is
321  $$P_{corr}(C) = \sum_{i=0}^n \alpha_i \cdot p^i(1-p)^{n-i}$$
322\end{thm}
323
324\begin{eg}{6.8}
325  $[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
326  $$P_{corr}(C) = (1-p)^4 + 3 p(1-p)^3 = (1-p)^3 (1+2p)$$
327\end{eg}
328
329\begin{lemma}{6.9}[Remark 6.9]\label{remark.6.9}
330  if $d(C)=2t+1$ or $d(C)=2t+2$, then $C$ can correct any $t$ errors.
331
332  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$.
333\end{lemma}
334
335\begin{defn}{}[Rate]
336  $[n, k]$-code $C$ uses $n$ symbols to send $k$ message symbols; it has \emph{rate} $R(C)=k/n$.
337
338  A good code will have a high rate.
339\end{defn}
340
341\begin{defn}{}[Capacity]
342  the \emph{capacity} $\mathscr{C}(p)$ of a binary symmetric channel with symbol error probability $p$ is
343  $$\mathscr{C}(p) = 1+ p \cdot \log_2{(p)} + (1-p) \cdot \log_2{(1-p)}$$
344\end{defn}
345
346
347\begin{thm}{6.12}[Shanon's theorem]
348  channel binary symmetric with symbol error probability $p$.
349
350  Let $R < \mathscr{C}(p)$.
351
352  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$.
353\end{thm}
354
355\begin{defn}{}[$P_{symb}$]
356  $P_{symb}$ denotes the average probability that a message symbol is in error after decoding.
357\end{defn}
358
359\begin{thm}{6.14}
360  let $C$ a binary [n,k]-code and let $A_i$ denote the number of codewords of $C$ of weight $i$.
361
362  Then, if $C$ is used for error detection, the probability of an incorrect message being undetected is
363  $$P_{undetec}(C) = \sum_{i=1}^n A_i \cdot p^i (1-p)^{n-i}$$
364\end{thm}
365
366\begin{eg}{6.15}
367  for the code of \ref{h.6.5},
368  $$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$$
369\end{eg}
370
371
372
373\vspace{0.5cm}
374
375\subsection{Exercises}
376\begin{ex}{5.1}
377  is the binary (11, 24, 5)-code linear?
378\end{ex}
379\begin{proof}
380  recall: a q-ary linear $[n,k,d]$-code is also a q-ary $(n, q^k, d)$-code, but
381  the opposite is not always true.
382
383  $\Longrightarrow~ (11, 24, 5)$-code to be linear it would mean that $24=q^k$.
384
385  Since it is binary, $q=2$. But $24 \neq 2^k$, so it can not be linear.
386\end{proof}
387
388\begin{ex}{5.2}
389  $E_n$ is the code of all even-weight vectors of $V(n,2)$, which is linear.
390  What are the parameters $[n, k, d]$ of $E_n$? Write a GM for $E_n$ in standard
391  form.
392\end{ex}
393\begin{proof}
394  $$E_n = \{ x \in V(n, 2) | w(x) ~\text{is even} \}$$
395
396  $\longrightarrow$ is the binary even-weight ode (the single parity-check code);\\
397  it's linear since
398  \begin{itemize}
399    \item the zero vector has even weight
400    \item over $GF(2)$, the sum of two even-weight vectors has even weight
401  \end{itemize}
402
403  Recall: $F_q^n \Longleftrightarrow \Vnq$, so $V(n, 2) \cong F_2^n$
404
405  $$\Longrightarrow~ E_n = \{ (x_1, \ldots, x_n) \in F_2^n | x_1 + \ldots + x_n = 0 \}$$
406
407  minimum distance is $2$, since
408  \begin{itemize}
409    \item no word of weight 1 is in $E_n$
410    \item words of weight 2 are in $E_n$
411  \end{itemize}
412
413  Therefore, parameters are $[n, n-1, 2]$
414
415  GM:
416  $$G=\left[ I_{n-1} | 1 \right]$$
417
418  which generates vectors of the form
419  $$(a_1, \ldots, a_{n-1}, a_1+\ldots+a_{n-1})$$
420\end{proof}
421
422\begin{ex}{5.5}
423  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.
424\end{ex}
425\begin{proof}
426  let $C_e,~ C_o$ be subsets of $C$ with even and odd weights respectively.
427
428  So that $C = C_e \cup C_o$ (disjoint union).
429
430  For binary vectors $x,y$:
431  $$w(x+y) = w(x) + w(y) \pmod 2$$
432
433  ie. over $F_2$, the parity of the weight is additive:
434  \begin{align*}
435    even + even &= even\\
436    even + odd &= odd\\
437    odd + odd &= even
438  \end{align*}
439
440  Now we have two possible cases:
441  \begin{itemize}
442    \item $C$ has no odd weighted codewords:\\
443      $C_0 = \emptyset,~ \forall x \in C$ $x$ is even weighted
444    \item $C$ has at least one odd-weighted codeword:\\
445      let $u \in C_o$, consider the map
446      \begin{align*}
447        \phi: C_e &\longrightarrow C_o\\
448        c &\longmapsto c+u
449      \end{align*}
450      with $c \in C_e,~ u \in C_o,~ \phi(c) \in C_o$.
451
452      $\phi$ is bijective, since $\phi(\phi(c))=(c+u)+u=c$,
453
454      so $\phi$ is it's own inverse; hence $|C_e| = |C_o|$.
455
456      Since $C=C_e \cup C_e$, half codewords are even weighted and half odd.
457  \end{itemize}
458\end{proof}
459
460\begin{ex}{6.1}
461  construct standard arrays for codes having each of the GMs:
462
463  $$G_1 = \begin{pmatrix}
464    1 & 0 \\
465    0 & 1
466    \end{pmatrix} ~~~
467    G_2 = \begin{pmatrix}
468      1 & 0 & 1\\
469      0 & 1 & 1
470        \end{pmatrix}
471    $$
472\end{ex}
473\begin{proof}
474  recall: for a binary code with GM $G$, the code $C$ consists of all binary linear combinations of the rows of $G$.
475
476  For $G_1$:\\
477  rows: $r_1=(1,0),~r_2=(0,1))$. A codeword is any linear combination:
478  $$u G_1= a \cdot r_1 + b \cdot r_2,~~ \text{with}~ a,b \in \{0,1\}$$
479
480  4 combinations:\\
481  \begin{align*}
482    0 \cdot r_1 + 0 \cdot r_2 &= (0,0)\\
483    1 \cdot r_1 + 0 \cdot r_2 &= (1,0)\\
484    0 \cdot r_1 + 1 \cdot r_2 &= (0,1)\\
485    1 \cdot r_1 + 1 \cdot r_2 &= (1,0)+(0,1) = (1,1)
486  \end{align*}
487  $$\Longrightarrow~ C_1 = \{00, 10, 01, 11\}$$
488  $$\text{standard array:}~ 00~01~10~11$$
489
490
491  \vspace{0.5cm}
492  For $G_2$:\\
493  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\}$.
494
495  4 combinations:\\
496  \begin{align*}
497    0 \cdot r_1 + 0 \cdot r_2 &= (0,0,0)\\
498    1 \cdot r_1 + 0 \cdot r_2 &= (1,0,1)\\
499    0 \cdot r_1 + 1 \cdot r_2 &= (0,1,1)\\
500    1 \cdot r_1 + 1 \cdot r_2 &= (1,0,1)+(0,1,1) = (1,1,0)
501  \end{align*}
502
503  $$\Longrightarrow~ C_2 = \{000, 101, 011, 110\}$$
504  $\Longrightarrow~$ so the 1st row of the standard array is: $000~101~011~110$.
505
506  Now, pick a non used vector: $001$, add it to the code $C_2$:
507  \begin{align*}
508    001 + C_2_i&\\
509    001 + 000 &= 001\\
510    001 + 101 &= 100\\
511    001 + 011 &= 010\\
512    001 + 110 &= 111
513  \end{align*}
514  $\Longrightarrow$ 2nd row of the standard array: $001~100~010~111$
515
516  Thus the standard array is
517  \begin{align*}
518    000~101~011~110\\
519    001~100~010~111
520  \end{align*}
521  ie. $2^3=8$ vectors, a $V(3,2)$ vector space.
522\end{proof}
523
524\begin{ex}{6.4}
525  $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$.
526\end{ex}
527\begin{proof}
528  From \ref{remark.6.9}, if $d(C)=2t+1$ (or $2t+2$) $Longrightarrow~ C$ can correct any $t$ errors.
529
530  Hence every vector of weight $\leq t$ is a coset leader and so $\alpha_i = \binom{n}{i}$ for $0 \leq i \leq t$.
531
532  \begin{equation}
533    P_{corr}(C) = \sum_{i=0}^n \alpha_i \cdot p^i(1-p)^{n-i}
534    \label{6.4.eq.1}
535  \end{equation}
536
537  where $\alpha_i$ is the number of coset leaders of weight $i$
538
539  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.
540
541  $$\Longrightarrow~ P_{err}(C) = \sum_{i=0}^n \left( \binom{n}{i} - \alpha_i \right) p^i (1-p)^{n-i}$$
542
543
544  \vspace{0.5cm}
545  Alternatively from \ref{6.4.eq.1}:\\
546  $$P_{err}(C) = 1 - P_{corr}(C) = 1 - \sum_{i=0}^n \alpha_i \cdot p^i(1-p)^{n-i}$$
547
548  Notice that
549  $$\sum_{i=0}^n \binom{n}{i} p^i (1-p)^{n-i} = (p + (1-p))^n = 1^n = 1$$
550
551  thus
552  \begin{align*}
553    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}\\
554               &= \sum_{i=0}^n \left( \binom{n}{i} - \alpha_i \right) p^i (1-p)^{n-i}
555  \end{align*}
556
557  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.
558
559  Thus
560  \begin{align*}
561    P_{err}(C) &= \sum_{i=0}^n \left( \binom{n}{i} - \alpha_i \right) p^i (1-p)^{n-i}\\
562               &= \left( \binom{n}{t+1} - \alpha_{t+1} \right) p^{t+1} (1-p)^{n-t+1} + \ldots
563  \end{align*}
564  where the $\ldots$ represent the terms with $p^{t+2}$ and higher.
565
566  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.
567
568  Hence,
569  $$P_{err}(C) = \left( \binom{n}{t+1} - \alpha_{t+1} \right) \cdot p^{t+1}$$
570\end{proof}
571
572\bibliographystyle{unsrt}
573\bibliography{algebraic-coding-theory-notes.bib}
574
575\end{document}