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}
\DeclareMathOperator{\char}{char}
\DeclareMathOperator{\GRS}{GRS}
\DeclareMathOperator{\RS}{RS}
\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{\bzero}{\mathbf{0}}
\newcommand{\balpha}{\boldsymbol{\alpha}}
\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 6
Today we will discuss 1-error correcting codes in detail. We start with the construction of the binary Hamming codes, which are a family of 1-error correcting linear codes with very nice properties. In class, we’ll talk about using Proposition 2.3.7 to construct general 1-error correcting linear codes from their parity-check matrices, and we’ll also discuss the efficient decoding algorithm for 1-error correcting linear codes. Finally, we’ll generalize the binary Hamming codes to
\(q\) -ary Hamming codes.
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 binary Hamming codes and be able to construct their parity-check matrices.
Explain why binary Hamming codes are 2-error detecting and 1-error correcting.
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.
Construct 1-error correcting linear codes using parity-check matrices.
State and use the efficient decoding algorithm for 1-error correcting linear codes.
State the definition and construct general
\(q\) -ary Hamming codes.
Subsection Resources for Learning
Use these resources to prepare for class and answer the questions below.
Guruswami, Rudra, & Sudan, Sections 2.4-2.5, pp. 39-42
Roth, Section 2.3, pp. 29-32
Vanstone & van Oorschot, Sections 3.3-3.5, pp 60-68
