Skip to main content
Contents Embed Dark Mode Prev Up Next \(\require{mathtools}\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}
\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{\bh}{\mathbf{h}}
\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\ \,}}}}
\)
Section Daily Prep 8
Today we will begin answering the question: how big can a code be, given its block length and minimum distance? In other words, we want to quantify the possible trade-offs between the redundancy of a code and its error-correcting capability.
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 of a Hamming sphere and its volume and the Hamming (sphere-packing) bound.
Apply the Hamming (sphere-packing) bound to determine if a given set of parameters
\((n,M,d)_q\) is possible for a code.
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 Singleton bound for codes, and the linear versions of the Hamming and Singleton bounds.
State the definition and give examples of perfect codes and Maximum Distance Separable (MDS) codes.
Apply multiple bounds to determine if a given set of parameters
\((n,M,d)_q\) is possible for a code.
Subsection Resources for Learning
Use these resources to prepare for class and answer the questions below.
Guruswami, Rudra, & Sudan, Sections 1.6-1.7 and 4.3, pp. 19-22 and 79-80
Roth, Sections 4.1-4.2, pp. 93-97
Subsection Important Terms
Definition 34 . Volume of a Hamming Sphere.
The volume of a Hamming Sphere of radius \(t\) in \(\F_q^n\) about a word \(\bx\) is
\begin{equation*}
V_q(n,t)=|B_t(\bx)|=\sum_{i=0}^t \binom{n}{i}(q-1)^i\text{.}
\end{equation*}
It is the number of words in \(\F_q^n\) that are within Hamming distance \(t\) of \(\bx\text{.}\)
Theorem 35 . Hamming or Sphere-Packing Bound.
Any \((n,M,d)_q\) -code satisfies
\begin{gather*}
M\cdot V_q(n,\lfloor (d-1)/2 \rfloor) \leq q^n \text{.}
\end{gather*}
Equivalently,
\begin{equation*}
\mathcal{A}_q(n,d) \leq \frac{q^n}{\sum_\limits{i=0}^{\lfloor (d-1)/2 \rfloor} \binom{n}{i}(q-1)^i}\text{.}
\end{equation*}
Equivalently, if \(C\) is a code of block length \(n\) and minimum distance \(d\) over \(\F_q\text{,}\) then its dimension \(k\) satisfies
\begin{equation*}
k \leq n - \log_{q}\left( \sum_\limits{i=0}^{\lfloor (d-1)/2 \rfloor} \binom{n}{i}(q-1)^i \right)\text{.}
\end{equation*}
