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 9
Today we will continue our discussion of bounds on the maximum size of a code with fixed length and minimum distance. Last time we saw some necessary conditions for the existence of a code with given parameters, and today we will see a sufficient condition.
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 Gilbert-Varshamov bound for general codes and apply it to determine the existence of codes with given parameters.
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 Gilbert-Varshamov bound for linear codes and apply it to determine the existence of codes with given parameters.
State the Distance of a Random Linear Code theorem and be able to use it to determine the probability that a random code meets the Gilbert-Varshamov bound.
Discuss expectations and deal-breakers for teamwork in groups.
Subsection Resources for Learning
Use these resources to prepare for class and answer the questions below.
Guruswami, Rudra, & Sudan, Section 4.2, pp. 74-78
Subsection Important Terms
Theorem 36 . Gilbert-Varshamov Bound for General Codes.
Let \(n,M,d\) be positive integers. If
\begin{equation*}
M\cdot V_q(n,d-1) \lt q^n \text{,}
\end{equation*}
then there exists an \((n,M,d)_q\) code.
Equivalently,
\begin{equation*}
\mathcal{A}_q(n,d) \geq \frac{q^n}{V_q(n,d-1)}\text{.}
\end{equation*}
