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\ \,}}}}
\)
Section Daily Prep 21
This is an outline of the topics we covered in the first week of class.
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.
State the definition and give examples of cyclic shift, cyclic codes.
Apply the properties of polynomials
\(x^n-1\) with
\(\gcd(n,q)=1\) to find factorizations and roots.
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.
State the definition and give examples of generator polynomial, check polynomial.
Recognize Reed-Solomon codes as cyclic codes.
Subsection Resources for Learning
Use these resources to prepare for class and answer the questions below.
Roth, Sections 7.5, 8.1, pp.229-231, 242-247
Vanstone & van Oorschot, Sections 5.1-5.3, pp 147-157
Figure 66. Reference Video for Cyclic Codes
Figure 67. Reference Video for Properties of Polynomials \(x^n-1\)
Subsection Important Terms and Results
Definition 68 . Cyclic Codes.
A code \(C\) is called cyclic if it is closed under cyclic shifts, i.e.
\begin{equation*}
(c_0\, c_1\, \dots \, c_{n-1}) \in C \Leftrightarrow (c_{n-1}\, c_0\, c_1\, \dots\, c_{n-2}) \in C\text{.}
\end{equation*}
Proposition 69 . Properties of \(x^n-1\) in \(\F_q[x]\) .
If \(d=\gcd(n,q)\text{,}\) then
\begin{equation*}
x^n-1=(x^d-1)^q\text{.}
\end{equation*}
Otherwise, suppose \(\gcd(n,q)=1\) and let \(m\) be the smallest positive integer such that \(n \mid q^m-1\text{.}\) Then the following hold
Simple Roots. The polynomial
\(x^n-1\) has simple roots in any extension field of
\(\F_q\text{.}\)
Splitting Field. The splitting field of
\(x^n-1\) over
\(\F_q\) is
\(\F_{q^m}\text{.}\)
Factorization over \(\F_q\text{.}\) We have
\begin{equation*}
x^n-1 = \prod_{M_{\alpha}(x)} M_{\alpha}(x)\text{,}
\end{equation*}
where \(M_{\alpha}\) ranges over the distinct minimal polynomials with respect to \(\F_q\) of the elements in a splitting field of \(x^n-1\) of order dividing \(n\text{.}\)
Definition 70 . Cyclotomic Cosets.
The exponents
\begin{equation*}
\{s,sq,sq^2,\dots,sq^{t-1}\}
\end{equation*}
where \(t\) is the smallest positive integer such that \(sq^t\equiv s \pmod{n}\) of a conjugacy class of roots of \(x^n-1\) with \(\gcd(n,q)\) are called a cyclotomic coset mod n over GF(q) .
