Daily Prep 17

Section Daily Prep 17

Today we begin our study of decoding for GRS codes. We will start with the key equation and use Sugiyama’s algorithm to solve it and decode.

🔗

Subsection Learning Objectives

Subsubsection Basic Learning Objectives

Objectives

Before our class meeting, you should use the resources below to be able to learn the following. You should be reasonably fluent with these; we’ll answer some questions on them in class but not reteach them in detail.

🔗

Define the syndrome polynomial, the error locator polynomial, and the error evaluator polynomial, and the key equation for GRS decoding.
🔗

🔗
State and explain the high-level steps of the GRS decoding algorithm.
🔗

🔗

🔗

Subsubsection Advanced Learning Objectives

Objectives

During our class meeting, we will work on learning the following. Fluency with these is not expected or required before class.

🔗

Use Sugiyama’s variant of the Euclidean algorithm to solve the key equation of GRS decoding and find the ELP and EEP.
🔗

🔗
Use Chien search and Forney’s algorithm to find the error locations and error values from the ELP and EEP.
🔗

🔗
Use the GRS decoding algorithm to decode a received word.
🔗

🔗

🔗

Subsection Resources for Learning

Use these resources to prepare for class and answer the questions below.

Hall, GRS codes notes, Section 5.2, pp. 67-74
🔗

🔗
Roth, Sections 6.1-6.3.0, 6.4-6.6, pp. 183-186, 191-195
🔗

🔗

🔗

Figure 48. Reference Video for GRS Decoding

🔗

Subsection Important Terms

Definition 49. Syndrome Polynomial.

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{.}\) The syndrome polynomial for a received word \(\by=\bc+\be\) is the polynomial

\begin{equation*} S(x) = \sum_{\ell=0}^{d-2} S_{\ell} x^{\ell} \end{equation*}

where \(\bs=(S_0, S_1,\dots, S_{d-2})=H_{\GRS}\transpose{\by}\text{.}\)

🔗

Definition 50. Error Locator Polynomial.

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{.}\) The error locator polynomial (ELP) for a received word \(\by=\bc+\be\) is the polynomial

\begin{equation*} \Lambda(x) = \prod_{j\in J} (1-\alpha_j x) \end{equation*}

where \(J\) is the set of error locations in \(\by\text{.}\)

🔗

Definition 51. Error Evaluator Polynomial.

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{.}\) The error evaluator polynomial (EEP) for a received word \(\by=\bc+\be\) is the polynomial

\begin{equation*} \Gamma(x) = \sum_{j\in J} e_j \alpha_j \prod_{m\in J\setminus\{j\}} (1-\alpha_{m} x) \end{equation*}

where \(J\) is the set of error locations in \(\by\text{.}\)

🔗

Definition 52. Key Equation.

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{.}\) The key equation for a received word \(\by=\bc+\be\) is

\begin{gather} \Lambda(x) S(x) \equiv \Gamma(x) \pmod{x^{d-1}} \text{.}\tag{1} \end{gather}

🔗

Prev Top Next