1\documentclass[a4paper]{article}
  2\setlength{\parindent}{0em}
  3\setlength{\parskip}{0.4em}
  4\usepackage{amsmath}
  5\usepackage{amsfonts}
  6\usepackage{amsthm}
  7\usepackage{enumerate}
  8\usepackage[bookmarksopen=true,bookmarks=true]{hyperref}
  9\usepackage{bookmark}
 10\hypersetup{
 11        pdfborder = {0.1 0.1 0.1},
 12%     colorlinks,
 13%     citecolor=black,
 14%     filecolor=black,
 15%     linkcolor=black,
 16%     urlcolor=blue
 17}
 18
 19\usepackage{multicol}
 20\usepackage{graphicx}
 21\usepackage{float}
 22\graphicspath{ {./imgs} }
 23\usepackage{pgf-umlsd} % diagrams
 24\usepackage[UKenglish]{datetime}
 25\newdateformat{DATEMonthYear}{\monthname[\THEMONTH] \THEYEAR}
 26\newdateformat{DATEYearMonthDay}{\THEYEAR-\THEMONTH-\THEDAY}
 27
 28\usepackage{booktabs} % \toprule \midrule ...
 29
 30\theoremstyle{definition}
 31\newtheorem{definition}{Def}[section]
 32\newtheorem{theorem}[definition]{Thm}
 33
 34%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 35
 36
 37\title{Notes on Reed-Solomon codes}
 38\author{arnaucube}
 39\date{January 2023}
 40
 41\begin{document}
 42
 43\maketitle
 44
 45\begin{abstract}
 46	Notes taken while reading about Reed-Solomon codes. Usually while reading papers I take handwritten notes, this document contains some of them re-written to $LaTeX$.
 47
 48	The notes are not complete, don't include all the steps neither all the proofs.
 49\end{abstract}
 50
 51\tableofcontents
 52
 53\section{Reed-Solomon Codes overview}
 54In this section we overview the main ideas presented in the Reed-Solomon paper \cite{reedsolomon} and in Bruce Maggs notes \cite{reedsolomon-bruce}.
 55
 56Reed-Solomon codes appeared in parallel to the BCH codes, and can be described as nonbinary BCH codes. In this section we will focus only in the Reed-Solomon codes, particularly in the encoding and error detection (not correction).
 57
 58\emph{tmp-note}: I feel like it is worth to check Galois theory \& BCH codes before going to Reed-Solomon codes, but due time constraints and our main goal being FRI, probably we should skip it.
 59
 60\subsection{Idea}
 61
 62Let $p(x) = m_0 + m_1 x + \ldots + m_{k-1} x^{k-1}$, where $m_i \in K$ and $k < 2^n$.
 63
 64We map $k$-tuples of $K$ into $2^n$-tuples of $K$, where $K=GF(p^r)$.
 65% Code E maps $k$-tuples of $K$ into $2^n$-tuples of $K$, where $K$ is a field of degree $n$ over the field of two elements $\mathbb{Z}_2$.
 66$$
 67k
 68\begin{cases}
 69    m_0\\
 70    m_1\\
 71    \vdots\\
 72    m_{k-1}
 73\end{cases}
 74\in K~~~~
 75% \stackrel{E}{ \xrightarrow{\hspace*{1cm}} }
 76\xrightarrow{\hspace*{1cm}}
 772^n
 78\begin{cases}
 79    p(0)\\
 80    p(\alpha)\\
 81    p(\alpha^2)\\
 82    \vdots\\
 83    p(1)
 84\end{cases}
 85\in K
 86$$
 87
 88The receiver then, can decode the messages by solving simultaneously any $k$ of the $2^n$ equations
 89
 90\begin{align*}
 91    p(0) &= m_0\\
 92    p(\alpha) &= m_0 + m_1 \alpha + m_2 \alpha^2 + \ldots + m_{k-1} \alpha^{k-1}\\
 93    p(\alpha^2) &= m_0 + m_1 \alpha^2 + m_2 \alpha^4 + \ldots + m_{k-1} \alpha^{2k-2}\\
 94    &~~~\vdots\\
 95    p(1) &= m_0 + m_1 + m_2 + \ldots + m_{k-1}\\
 96\end{align*}
 97
 98This system of equations can be solved, as we can see that any $k$ of the $p(\alpha^j)$ equations are linearly independent since they form a Vandermonde matrix
 99$$
100V =
101\begin{pmatrix}
102    1 & x_1 & x_1^2 & \ldots & x_1^{k-1} \\
103    1 & x_2 & x_2^2 & \ldots & x_2^{k-1} \\
104    1 & x_3 & x_3^2 & \ldots & x_3^{k-1} \\
105    \vdots & \vdots & \vdots &  & \vdots\\
106    1 & x_n & x_n^2 & \ldots & x_n^{k-1} \\
107\end{pmatrix}
108$$
109
110and $\det V$ is a Vandermonde determinant and $\det V \neq 0$ as
111$$
112\det~V = \prod_{j < i} (x_i - x_j)
113$$
114
115See Annex \ref{sec:vandermondedet} for a proof of the Vandermonde determinant.
116
117% The number of combinations of taking $k$ elements from $2^n$ elements (without regard of order) can be expressed by $C_k^{2^n} = \binom{2^n}{k} = \frac{(2^n)!}{k!~(2^n - k)!}$.
118% This is the number of determinations of $(m_0, \ldots, m_{m-1})$ in case of no errors.
119
120% TODO this part needs to be continued & finished.
121
122\subsection{Real world approach}
123In the practical side, instead of transmitting $k+2s$ polynomial evaluations, we send $k$ coefficients + $2s$ evaluations.
124
125This is because we are interested in efficiency in the \emph{common} case, where in most of cases there are no errors and we care more about having a fast check that there are no errors than of the error recovering phase.
126
127Furthermore, in our use case in the context of FRI IOP, we are not interested into decoding but only into detecting errors.
128
129% \subsubsection{The setup}
130% We work on $GF(p^r)$. For $\alpha$ being a primitive element of $GF(p^r)$, we set the generator polynomial
131% 
132% $$
133% g(x) = (x-\alpha) (x-\alpha^2) \cdots (x-\alpha^{2s-1})
134% $$
135% 
136% 
137% THIS part is not coherent with the 'Encoding' section
138% We define
139% $$b(x) = x^{2s} \cdot m(x) \pmod{g(x)}$$
140% 
141% thus, for some $q(x)$,
142% $$x^{2s} m(x) = q(x) g(x) + b(x)$$
143% 
144% Define the codeword $c(x)$ as
145% $$c(x) = x^{2s} \cdot m(x) - b(x)$$
146% UNTIL HERE.
147
148% notice that $c(x)=q(x)g(x)$, thus $c(x)$ is a multiple of $g(x)$.
149% 
150% In order to check if a received codeword $c'(x)$ is correct, we'll check its divisibility by $g(x)$. If the check passes, we extract the first $k$ elements of $c'(x)$.
151
152
153\subsubsection{Encoding}
154
155Let $g(x)$ be the generator polynomial
156$$g(x) = (x-\alpha) (x-\alpha^2) \cdots (x-\alpha^{2s-1})$$
157
158with $\alpha$ being a primitive element of $GF(p^r)$.
159
160The \emph{encoder} wants to map the message $\{ m_0, m_1, \ldots, m_{k-1} \}$ into a polynomial $p(x)$ of degree $<k$ such that
161
162$$p(\alpha_i) = m_i ~~ \forall i\in{0, k-1}$$
163
164so we interpolate taking $\{ m_0, m_1, \ldots, m_{k-1} \}$ as the coefficients of $p(x)$ in order to obtain
165$$p(x) = m_0 + m_1 \cdot x + \cdots + m_{k-1} x^{k-1}$$
166
167Then the encoder computes $c(x) = p(x) \cdot g(x)$, and will output the coefficients of $c(x)$, $\{ c_i \}^k$.
168
169Notice that $c(x)=q(x)g(x)$, thus $c(x)$ is a multiple of $g(x)$.
170
171\subsubsection{Error checking}
172
173The \emph{receiver} starts from the received coefficients $\{c_i'\}^k$ of $c'(x)$. $c'(x)$ may contain errors, which we represent by $e(x) = e_0 + e_1 x + e_2 x^2 + \ldots + e_{k-1} x^{k-1}$, so $c'(x) = c(x) + e(x)$.
174
175In order to check $c(x)\stackrel{?}{=} c'(x)$ (thus, that there are no errors ($e(x) = 0$)), we will do the divisibility check $g(x) | c'(x)$, which if there are no errors the check should pass. This comes from the fact that we've chosen $c(x)$ to be a multiple of $g(x)$.
176If the check passes, we'll extract the first $k$ elements of $c'(x)$.
177
178If $c'(x) / g(x) = 0$, it means that $c'(x)$ is a multiple of $g(x)$, thus $c(x)=c'(x)$, which means that there are no errors.
179
180In practice, checking divisibility by dividing $c'(x)$ by $g(x)$ could be computationally expensive, that's why we do the following approach.
181% so we multiply $c(x)$ by some polynomial $d(x)$, and then we check if $g(x)d(x)$ divides the result.
182% 
183% In this way, instead of checking that $c'(x)/g(x) = 0$, we check that
184% $$c'(x) = d(x) \cdot g(x) = 0 \pmod{x^n - 1}$$
185% 
186% If $c'(x) / g(x) \neq 0$, means that there are errors, such that
187% $$c'(x) = p(x) \cdot g(x) + e(x)$$
188
189\textbf{The check polynomial}
190
191From $g(x) = (x-\alpha) (x-\alpha^2) \cdots (x-\alpha^{2s-1})$, we know that
192$$g(x) = \prod_{i=0}^{2s-1} (x - \alpha^i) = x^{2s} - 1$$
193a proof for $\prod_{i=0}^{n-1} (x - \alpha^i) = x^n - 1$ can be found in \cite{cyclotomicpolyroots}.
194
195Now, let $g'(x)=\prod_{i=0}^{n-1} (x-\alpha^i)$, which for $n=k +2s$, is equivalent to
196
197$$g'(x) = \prod_{i=0}^{n-1} (x-\alpha^i) = \prod_{i=0}^{2s-1} (x-\alpha^i) ~\cdot \prod_{i=2s-1}^{n-1} (x-\alpha^i)$$
198% \begin{align*}
199%     g'(x) = \prod_{i=0}^{n-1} (x-\alpha^i) =& \prod_{i=0}^{2s-1} (x-\alpha^i) ~\cdot \prod_{i=2s-1}^{n-1} (x-\alpha^i)\\
200% =& ~g(x) ~\cdot \prod_{i=2s-1}^{n-1} (x-\alpha^i)
201% \end{align*}
202
203where we see clearly that $g'(x)$ is a multiple of $g(x)$, so, we have that $g(x) | g'(x)$, which is the same than saying that
204$$g(x) | (x^n-1),~for~2s<n$$
205
206From here, as we know that $c(x)$ is a multiple of $g(x)$, we can see that there is a unique polynomial $h(x)$ of degree $n-2s$ such that
207$$g(x) h(x) = x^n - 1$$
208So, $h(x) = (x^n -1) / g(x)$, and we can see that
209
210$$h(x) = (x^n -1)/g(x)= \prod_{2s-1}^{n-1} (x - \alpha^i)$$
211% $$h(x) = (x^n -1)/g(x)=\frac{x^n -1}{x^{2s} -1} = \frac{\prod_0^{n-1} (x-\alpha^i)}{\prod_0^{2s-1} (x-\alpha^i)}$$
212% $$= \frac{\prod_0^{2s-1} (x-\alpha^i) \cdot \prod_{2s-1}^{n-1} (x - \alpha^i)}{\prod_0^{2s-1} (x-\alpha^i)}
213% = \prod_{2s-1}^{n-1} (x - \alpha^i)
214% $$
215
216The degree of $h(x)$ being $n-2s$ can be seen from the fact that $deg(g(x))=2s$ and $deg(x^n -1)=n$, thus
217$$deg(h(x)) = deg((x^n -1)/g(x))=n-2s$$
218which is equal to $k$.
219
220The polynomial $h(x)$ receives the \emph{check polynomial} name.
221
222From here, to determine if $c'(x)$ is a valid codeword we check:
223$$c'(x) \cdot h(x) = 0 \pmod{x^n - 1}$$
224
225
226It is common to choose $n = p^r -1$ such as $n=2^8 - 1$, and $k=223$ (\emph{RS(255, 223)}), over $GF(2^8)$. 
227
228
229
230
231
232
233
234\newpage
235%%%%%% APPENDIX
236
237\appendix
238\section{Vandermonde determinant}
239\label{sec:vandermondedet}
240
241This 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}.
242
243$$
244\det~V(x_1, ..., x_n) = \det
245\begin{pmatrix}
246    1 & x_1 & x_1^2 & \ldots & x_1^{n-1} \\
247    1 & x_2 & x_2^2 & \ldots & x_2^{n-1} \\
248    1 & x_3 & x_3^2 & \ldots & x_3^{n-1} \\
249    \vdots & \vdots & \vdots &  & \vdots\\
250    1 & x_n & x_n^2 & \ldots & x_n^{n-1} \\
251\end{pmatrix}
252= \prod_{j < i} (x_i - x_j)
253$$
254
255\emph{Proof}
256
257The equation is true for $n = 2$, as we have:
258
259$$
260\det~V(x_1, x_2) = \det
261\begin{pmatrix}
262    1 & x_1\\
263    1 & x_2
264\end{pmatrix}
265= x_2 - x_1
266$$
267
268We 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:
269
270$$
271= \det
272\begin{pmatrix}
273    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}) \\
274    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}) \\
275    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}) \\
276    \vdots & \vdots & \vdots &  & \vdots\\
277    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}) \\
278\end{pmatrix}
279$$
280$$
281= \det
282\begin{pmatrix}
283    1      & 0           & 0              & \ldots & 0 \\
284    1      & (x_2 - x_1) & x_2(x_2 - x_1) & \ldots & x_2^{n-2}(x_2 - x_1) \\
285    1      & (x_3 - x_1) & x_3(x_3 - x_1) & \ldots & x_3^{n-2}(x_3 - x_1) \\
286    \vdots & \vdots      & \vdots         &        & \vdots \\
287    1      & (x_n - x_1) & x_n(x_n - x_1) & \ldots & x_n^{n-2}(x_n - x_1) \\
288\end{pmatrix}
289$$
290
291Applying the Laplace expansion along the first row and factoring out the scalar multiples $(x_i - x_1)$ in each column, we obtain: 
292
293$$
294= \det
295\begin{pmatrix}
296    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} \\
297    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} \\
298    \vdots & \vdots & \vdots &  & \vdots\\
299    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} \\
300\end{pmatrix}
301$$
302
303in each row, factor out $(x_i - x_1)$
304
305$$
306= \det
307\begin{pmatrix}
308    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) \\
309    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) \\
310    \vdots & \vdots & \vdots &  & \vdots\\
311    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) \\
312\end{pmatrix}
313$$
314$$
315= \prod_{2 \leq i \leq n} (x_i - x_1) ~~\det
316\begin{pmatrix}
317    1 & x_2 & x_2^2 & \ldots & x_2^{n-2} \\
318    1 & x_3 & x_3^2 & \ldots & x_3^{n-2} \\
319    \vdots & \vdots & \vdots &  & \vdots\\
320    1 & x_n & x_n^2 & \ldots & x_n^{n-2} \\
321\end{pmatrix}
322$$
323
324now, by induction
325
326$$
327= \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)
328$$
329\qed
330
331
332
333
334% Bibliography
335\addcontentsline{toc}{section}{References}
336\bibliography{notes_reed-solomon.bib}
337\bibliographystyle{unsrt}
338
339\end{document}