Skip to main content
Contents Embed Dark Mode Prev Up Next \(\require{mathtools}\setcounter{MaxMatrixCols}{15}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\GF}{\mathrm{GF}}
\DeclareMathOperator{\Span}{Span}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\rk}{rk}
\DeclareMathOperator{\wt}{wt}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\char}{char}
\DeclareMathOperator{\GRS}{GRS}
\DeclareMathOperator{\RS}{RS}
\newcommand{\transpose}[1]{#1^{\top}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\bm}{\mathbf{m}}
\newcommand{\bs}{\mathbf{s}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\balpha}{\boldsymbol{\alpha}}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\newcommand{\fillinmath}[1]{\mathchoice{\underline{\displaystyle \phantom{\ \,#1\ \,}}}{\underline{\textstyle \phantom{\ \,#1\ \,}}}{\underline{\scriptstyle \phantom{\ \,#1\ \,}}}{\underline{\scriptscriptstyle\phantom{\ \,#1\ \,}}}}
\)
Handout GRS & RS Codes
This handout collects the various definitions and facts about GRS and RS codes for reference as you work on problems.
Definition 73 . GRS Codes.
Let \(F=\GF(q)\text{.}\) The code locators are \(\balpha=(\alpha_1,\ldots,\alpha_n)\) a set of distinct non-zero elements of \(F\text{.}\) The column multipliers are \(\bv=(v_1,\ldots,v_n)\) a set of non-zero (possibly repeated) elements of \(F\text{.}\) Then the generalized Reed Solomon code \(\GRS_{n,k}(\balpha,\bv)\) is the \([n,k,n-k+1]_q\) code with canonical parity-check matrix
\begin{equation*}
H_{\mathrm{GRS}} = \begin{bmatrix}
1 \amp 1 \amp \ldots \amp 1 \\
\alpha_1 \amp \alpha_2 \amp \ldots \amp \alpha_n \\
\vdots \amp \vdots \amp \vdots \amp \vdots \\
\alpha_1^{n-k-1} \amp \alpha_2^{n-k-1} \amp \ldots \amp \alpha_n^{n-k-1}
\end{bmatrix}\begin{bmatrix}
v_1 \amp 0 \amp \ldots \amp 0 \\
0 \amp v_2 \amp \ldots \amp 0 \\
\vdots \amp \vdots \amp \ddots \amp \vdots \\
0 \amp 0 \amp\ldots \amp v_n
\end{bmatrix}\text{.}
\end{equation*}
\(\GRS_{n,k}(\balpha,\bv)\) is called
singly-extended if one of the code locators is allowed to be
\(0\text{,}\) primitive if
\(n=q-1\) (so that the code locators are
\(F^*\) ),
narrow-sense if the column multipliers are equal to the code locators i.e.
\(v_i=\alpha_i\text{,}\) and
normalized if
\(v_i=1\text{.}\)
The canonical generator matrix is
\begin{equation*}
G_{\GRS} = \begin{bmatrix}
1 \amp 1 \amp \ldots \amp 1 \\
\alpha_1 \amp \alpha_2 \amp \ldots \amp \alpha_n \\
\vdots \amp \vdots \amp \vdots \amp \vdots \\
\alpha_1^{k-1} \amp \alpha_2^{n-1} \amp \ldots \amp \alpha_n^{k-1}
\end{bmatrix}\begin{bmatrix}
u_1 \amp 0 \amp \ldots \amp 0 \\
0 \amp u_2 \amp \ldots \amp 0 \\
\vdots \amp \vdots \amp \ddots \amp \vdots \\
0 \amp 0 \amp\ldots \amp u_n
\end{bmatrix}
\end{equation*}
where \(u_i^{-1}=v_i \prod_{j\neq i}(\alpha_i-\alpha_j)\text{.}\) When the code is primitive this simplifies to \(u_i=\alpha_i/v_i\text{.}\)
Definition 74 . RS Codes.
Let \(F=\GF(q), n \mid q-1, b\in \Z\text{.}\) Fix an element \(\alpha \in F\) with \(|\alpha|=n\text{.}\) Then the Reed-Solomon code \(\RS_{n,k}(\alpha)\) is \([n,k,n-k+1]_q\) code \(\GRS_{n,k}(\balpha,\bv)\) with
\begin{equation*}
\alpha_j=\alpha^{j-1} \quad v_j=\alpha^{b(j-1)},\qquad 1\leq j \leq n\text{.}
\end{equation*}
It has canonical parity check matrix
\begin{equation*}
H_{\RS} = \begin{bmatrix}
1 \amp \alpha^b \amp \ldots \amp \alpha^{b(n-1)} \\
1 \amp \alpha^{b+1} \amp \ldots \amp \alpha^{(b+1)(n-1)} \\
\vdots \amp \vdots \amp \vdots \amp \vdots \\
1 \amp \alpha^{b+d-2} \amp \ldots \amp \alpha^{(b+d-2)(n-1)} \\
\end{bmatrix}\text{.}
\end{equation*}
The roots of the code are \(\{\alpha^b,\alpha^{b+1},\ldots,\alpha^{b+d-2}\}\text{.}\) The generator polynomial is
\begin{equation*}
g(x)=\prod_{i=0}^{d-2} (x-\alpha^{b+i})\text{.}
\end{equation*}
We have \(\bc\in \RS_{n,k}(\alpha)\) if and only if \(g(x)\mid c(x)\) where \(c(x)\) is the polynomial in \(F[x]\) with \(\bc\) as its coefficient vector.
Table 75. Representation of \(\GF(2^3)\) as \(\mathbb{F}_2[\beta]/(\beta^3+\beta+1)\)
\(-\infty\) \(0\) 000
\(\beta^0\) \(1\) 100
\(\beta^1\) \(\beta\) 010
\(\beta^2\) \(\beta^2\) 001
\(\beta^3\) \(1+\beta \) 110
\(\beta^4\) \(\beta + \beta^2\) 011
\(\beta^5\) \(1 + \beta + \beta^2\) 111
\(\beta^6\) \(1+\beta^2 \) 101
