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}
\makeatletter
\@ifundefined{char}{
\DeclareMathOperator{\char}{char}
}{}
\makeatother
\DeclareMathOperator{\GRS}{GRS}
\DeclareMathOperator{\RS}{RS}
\DeclareMathOperator{\BCH}{BCH}
\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}}
\renewcommand{\vec}[1]{\boldsymbol{#1}}
\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 Decoding Schemes
Algorithm 98 . Sugiyama’s Algorithm for GRS Decoding.
Let
\(C\) be an
\([n,k,d]_q\) GRS code with code locators
\(\alpha_1,\alpha_2,\dots,\alpha_n\) and column multipliers
\(v_1,v_2,\dots,v_n\text{.}\) Let
\(\by=\bc+\be\) be a received word.
Syndrome computation: compute the polynomial \(S(x)=\sum_{\ell=0}^{d-2} S_{\ell} x^{\ell}\) where
\begin{equation*}
S_{\ell}=\sum_{j=1}^n y_j v_j \alpha_j^{\ell}, \quad \ell=0,1,\dots,d-2\text{.}
\end{equation*}
Solving the key equation: Apply the extended Euclidean algorithm with inputs
\begin{equation*}
a(x)=x^{d-1} \quad \text{and} \quad b(x)=S(x)
\end{equation*}
to produce
\begin{equation*}
\Lambda(x)=t_h(x) t_h(0)^{-1} \quad \text{and} \quad \Gamma(x)=r_h(x) t_h(0)^{-1}\text{,}
\end{equation*}
where \(h\) is the smallest index such that \(\deg(r_h) \lt \frac{d-1}{2}\text{.}\)
Find error locations: Use Chien search (or other root-finding algorithm) to find the roots of
\(\Lambda(x)\text{.}\)
Find error values: use Forney’s algorithm to compute the error values by
\begin{equation*}
e_j = \begin{cases}
-\dfrac{\alpha_j}{v_j} \dfrac{\Gamma(\alpha_j^{-1})}{\Lambda'(\alpha_j^{-1})} \amp \text{if } \Lambda(\alpha_j^{-1})=0 \\
0 \amp \text{otherwise}
\end{cases}
\end{equation*}
for \(j=1,2,\dots,n\text{.}\)
Algorithm 99 . Extended Euclidean Algorithm.
Let \(a(x)\) and \(b(x)\) be polynomials over a field \(F\text{.}\) This algorithm outputs polynomials \(s(x),t(x),d(x)\) such that
\begin{equation*}
s(x)a(x)+t(x)b(x)=d(x)=\gcd(a(x),b(x))\text{.}
\end{equation*}
The notation \(f(x)\ \mathrm{div}\ g(x)\) means the quotient part of the division of \(f(x)\) by \(g(x)\text{.}\)
Initialize \(i=1\) and
\begin{align*}
r_{-1}(x)\amp=a(x) \amp r_0(x)\amp=b(x)\\
s_{-1}(x)\amp=1 \amp s_0(x)\amp=0\\
t_{-1}(x)\amp=0 \amp t_0(x)\amp=1\text{.}
\end{align*}
Compute
\begin{align*}
q_i(x) \amp = r_{i-2}(x)\ \mathrm{div}\ r_{i-1}(x) \quad (\text{the quotient of dividing } r_{i-2}(x) \text{ by } r_{i-1}(x)) \\
r_i(x) \amp = r_{i-2}(x) - q_i(x)r_{i-1}(x) \quad (\text{the remainder of dividing } r_{i-2}(x) \text{ by } r_{i-1}(x)) \\
s_i(x) \amp = s_{i-2}(x)-q_i(x)s_{i-1}(x)\\
t_i(x) \amp = t_{i-2}(x)-q_i(x)t_{i-1}(x) \text{.}
\end{align*}
If \(r_i(x)=0\text{,}\) output
\begin{equation*}
s_{i-1}(x), t_{i-1}(x), r_{i-1}(x)
\end{equation*}
and stop. Otherwise, increment \(i\) and return to step 2.
Algorithm 100 . Berlekamp-Welch Decoding for GRS Codes.
Let
\(C\) be an
\([n,k,d]_q\) GRS code with code locators
\(\alpha_1,\alpha_2,\dots,\alpha_n\) and column multipliers
\(v_1,v_2,\dots,v_n\text{.}\) Let
\(\by=\bc+\be\) be a received word. Let the column multipliers of the dual code be
\(u_1,u_2,\dots,u_n\text{.}\) Set
\(e=\lfloor(d-1)/2\rfloor\text{.}\)
Define polynomials
\(E(x)=x^e+\sum_{i=0}^{e-1} e_i x^i\) and
\(Q(x)=\sum_{j=0}^{e+k-1} q_j x^j\text{.}\)
Solve the system of \(2e+k-1=n\) equations in the \(2e+k-1=n\) coefficients of \(E(x)\) and \(Q(x)\) given by
\begin{equation*}
Q(\alpha_i)=\frac{y_i}{u_i} E(\alpha_i) \quad i=1,\ldots,n
\end{equation*}
Compute the possible message polynomial
\(P(x)=Q(x)/E(x)\) and check if
\(d_H(\vec{u}P(\balpha),\by)\leq e\text{.}\) If the distance is at most
\(e\text{,}\) return
\(P(x)\) as the recovered message. Otherwise, declare too many errors occurred to decode.
