\documentclass[10pt]{article}
\usepackage{amsfonts,amsthm,amsmath,amssymb}
\usepackage{fullpage}
\newcommand{\eps}{\epsilon}
\newcommand{\code}[1]{\left[#1\right]}
\DeclareMathOperator{\Tr}{Tr}
\begin{document}
\input{preamble.tex}
\handout{CS 229r Essential Coding Theory, Lecture 8}{Feb 16, 2017}{Instructor: Madhu Sudan}{Scribes: Yi-Hsiu Chen}{Lecture 8}
\section{Overview}
Today, we introduce two families of codes, (1) \emph{Dual BCH code} and (2) \emph{Algebraic geometry codes}, which could be better than a random bound (Gilbert-Varshamov bound) in some proper settings of parameters.
The codes rely on two mappings called \emph{trace} and \emph{norm}, which map an element form a large field to a small field.
Also the B\'ezout Theorem is needed.
\subsection{Parameters}
As usual, we have the following parameters.
\begin{itemize}
\item $k$: message length.
\item $\delta$: relative distance $\delta = \frac{1}{2}-\eps$,
\item $n$: code length
\end{itemize}
In this lecture we will mostly focus on the case that $k\to\infty$ and $\eps\to 0$.
The question we are asking is, what is the smallest $n$ we can get? (e.g.,~in the form of $\frac{k^{\alpha}}{\eps^{\beta}}$)
\subsection{Review of known bounds}
\begin{itemize}
\item The existential bound (random code) gives us $n = \frac{k}{\eps^2}$.
\item Concatenation of Reed-Solomon code and Hadamard code: $\code{n, 2\eps n, (1-2\eps)n}_n\circ\code{n, \log_2n, n/2}_2 \Rightarrow [n^2, 2\eps n\log n, n^2(1/2-\eps)]_2$ gives us $n = \frac{k^2}{\eps^2}$
\end{itemize}
\section{Dual BCH Code}
First, we introduce a mapping function, \emph{trace}
\subsection{Trace Function}
\begin{definition}
The trace function $\Tr:\bbF_{q^\ell}\to\bbF_{q}$ is defined by a polynomial $\in \bbF_{q^\ell}[x]$ as follows.
\[\Tr(x) \overset{\rm def}{=} x + x^q + x^{q^2} + \cdots + x^{q^{\ell-1}}\]
\end{definition}
Some properties of $\Tr$:
\begin{itemize}
\item $\Tr(rx + y) = r\Tr(x) + \Tr(y)$.
\item The image of $\Tr$ is contained by $\bbF_q$. This can be shown by observing that
\[\forall~\alpha\in\bbF_{q^\ell}~,~~\Tr(\alpha)^q = \left(\alpha + \cdots + \alpha^{q^{\ell-1}}\right)^q = \alpha^q + \alpha^{q^2} + \cdots \alpha^{q^{\ell}}
= \Tr(\alpha) \pmod{x^{q^\ell} - x}\]
\end{itemize}
\begin{exercise}
$\Tr: F_{q^\ell} \to F_q$ is a uniform mapping ($q^{\ell-1}$ to $1$).
\end{exercise}
\subsection{Dual BCH Code with degree $t$}
We start from a low degree of polynomial over a big field $\bbF_{n}$ where $n = 2^{\ell}$.
As in Reed-Solomon code, we evaluate the function over the entire domain.
\[m(x) = \sum_{i = 0}^{t-1} m_i x^i \mbox{ where } m_i\in\bbF_{2^\ell}\]
The coefficients can also be treated as $t\cdot \ell = (t \log n)$ elements over $\bbF_2$.
We then apply the trace function $\Tr:\bbF_{2^\ell}\to\bbF_2$ on $m(x)$ to define the encoding function.
That gives us a code $\code{n, t\log n, d}_2$ where $d$ is to be decided.
To determine the distance $d$, we use the following theorem. (Proof is omitted)
\begin{theorem}
If $f$ is a degree $r$ polynomial over $\bbF_n$ where $n = p^{\ell}$, then
\[\left|(\# \mbox{zeros of } \Tr\circ f) - \frac{n}{p}\right| \leq \frac{2(p-1)(r-1)}{p}\cdot\sqrt{n}.\]
\end{theorem}
Especially we consider the case that $p = 2$.
That gives us the distance
\[d = n-\left(\frac{n}{2} + (r-1)\sqrt{n}\right) = n\left(\frac{1}{2}-\frac{r-1}{\sqrt{n}}\right).\]
Let $k = t\log n$, then it gives us $n \approx k^2/ (\eps^2\log^2(k/\eps))$, which is better than the constructive bound we had.
\section{Algebraic Geometry Code}
\subsection{Motivation}
Recall that in the Reed Muller code, we evaluate a multinomial function $f$ over $\bbF_q^m$.
Apparently, there are lots of redundancy.
For instance, by seeing part of a line, the rest can be inferred.
The ``redundancy'' is needed in an error-correcting code.
However, we can try to remove some evaluation points to reduce the redundancy, which let us keep the same distance, but shorter code.
Algebraic geometry provides us a way to choose points.
\subsection{History}
The concept of algebraic geometric code was first conceived by Goppa~\cite{Goppa}.
Then Tsfasman, Vladut and Zink~\cite{TVZ} provide the code fulfilling the following theorem.
\begin{theorem}
For all even prime power $q$, for all $n, k\in\bbN$, there exists a code over $\bbF_{q}$ with length $n$, dimension $k$, and distance $n-k-\frac{n}{\sqrt{q}-1}$.
\end{theorem}
Then the code is simplified recently by Garcia and Stichtenoth~\cite{GH}, which we will mention the construction without showing the distance in Section~\ref{subsec:gs-code}.
Note that it could be better than a random code when $q \geq 49$.
\subsection{Norm function}
\begin{definition}
Norm function $N:\bbF_{q^\ell}\to\bbF_{q}$ is defined as
\[N(x) = x^{1+q+q^2+\cdots + q^{\ell-1}}.\]
\end{definition}
\begin{exercise}
Show the following properties of a norm function $N:\bbF_{q^\ell}\to\bbF_{q}$.
\begin{itemize}
\item $N(xy) = N(x)N(y)$.
\item $\forall~\alpha\in\bbF_{q^{\ell}}~,~~N(\alpha)^\ell = N(\alpha)\pmod{(x^{q^\ell}-x)}$, which means the image of $N$ is contained by $\bbF_q$.
\item $N$ is a $(1 + q + \cdots + q^{\ell-1})$ to $1$ mapping. That is, for all $\beta\in\bbF_{q^{\ell}}$ $\#\{\alpha: N(\alpha) = \beta\} = 1 + q + \cdots + q^{\ell-1}$.
\end{itemize}
\end{exercise}
\subsection{Code over the Hermitian Curve}
Let a polynomial $R(x, y) = N(x) - \Tr(y)$, then the Hermitian Curve $H$ over $\bbF_{q^2}$ is defined as
\[H = \{(\alpha, \beta)\in \bbF_{q^2}^2 \mid R(\alpha, \beta) = 0\}.\]
The size of $H$ is exactly $q^3$, which can be seen by considering each fixed $\beta$.
Now we can define a code on the curve $C_r$ where $r\leq q$ to be evaluations of polynomial with degree $\leq r$ over $H$.
The number of coefficients is at least $r^2/2$, so $k \geq r^2/2$, and the code length is $n = |H| = q^3$.
To calculate the distance, we need the B\'ezout's Theorem (in a plane).
\begin{theorem}
If $f, g\in \bbF[x, y]$ are of degree $D_1$ and $D_2$ respectively, then either $f$ and $g$ have a common factor,
or they have at most $D_1D_2$ common zeros.
\end{theorem}
The degree of $R$ is $q+1$ and the degree of $f$ is $r$.
Since $R$ is irreducible and $r < q+1$, $f$ and $R$ can have at most $r(q+1)$ common factors.
Therefore, the distance $d$ is at least $n-r(q+1)$.
Summarily, we get the code $\code{q^3, r^2/2, q^3-r(q+1)}_{q^2}$, or $\code{q^3, q^2/2, q^3-q(q+1)}_{q^2}$ if we let $r = q$.
Note that the size of the alphabet $q^2$ is smaller than the code length.
Does that mean it gives us a code better than Reed-Solomon code?
To compare it clearer, we concatenate them to Hadamard code $\code{q^2, \log(q^2), \frac{1}{2}q^2}_2$.
That gives us $\code{q^5, r^2/2, q^5(\frac{1}{2}-\frac{r}{2q^2}(1+\frac{1}{q}))}_2$.
Set $\eps = \frac{r}{q^2}$, $k = r^2/2$, it yields $n \approx \frac{k^{5/4}}{\eps^{5/2}}$.
Consider the case that $\eps = 1/k$, then $n \approx k^{15/4}$ which is better than the known constructive bound! ($n = k^4$, e.g., Concatenating Reed-Solomon and Hadamard).
\subsection{Garcia-Stichtenoth Codes}\label{subsec:gs-code}
We define the set $S$ as follows,
\[S \overset{\rm def}{=} \{(\alpha_1...\alpha_n) | P_1(\overline{\alpha}) = 0, \dots, P_m(\overline{\alpha}) = 0\}\]
where $P_i(\alpha) = \Tr(\alpha_{i+1}) = N(\alpha_i)/\Tr(\alpha_i)$ and $\Tr, N: \bbF_{q^2}-> \bbF_q$
There are $q^2-q$ choices of $\alpha_1$, $q$ choices of $\alpha_2$ $\dots$ $q$ choices of $\alpha_m$, so $q^{m+1}(1-1/q)$ points in total.
Then the code is constructed by evaluations of a polynomial on $S$.
%%%%%%%%
\bibliographystyle{alpha}
\bibliography{lect08}
\end{document}