我们希望通过通道可靠地将消息（以位表示）传输到目的地。传输过程中可能会出现错误，我们希望检测和纠正这些传输错误。为了做到这一点，我们必须在传输的消息中引入一些冗余。
我们看到Shannon’s Noisy Coding Theorem告诉我们，如果冗余度高于一定水平（受通道噪音约束），那么我们可以随着块长度的增加将错误概率（检测到发送的错误消息）减少到零。
该证明是基于随机编码，这不是很实用。为了易于编码和解码，我们的编码/解码功能需要优良的结构。我们将研究一类称为线性分组码的代码，因为它们的结构提供了几个优点。线性性将使我们更容易地分析代码的错误纠正能力。此外，使用矩阵来编码/解码消息比随机码本容易得多，并且可以简洁地描述代码。
两个概念：
- Error detection：编码可以检测错误，但我们不知道错误在接收序列中的位置。
- Error correction：我们知道错误在哪里，并且可以纠正错误的位位置。
在代码最多可以纠正t个错误的情况下，如果序列包含超过t个错误，解码器可能会解码到错误的信息序列。
任意两个比特串之间的汉明距离$d_H$是2个字符串不同的比特数。例如，码字$c_1=(101101)$和$c_2=(100110)$之间的汉明距离$d_H$是3。表示$d^*$是代码$C$的任何两个不同码字之间的最小汉明距离
码字之间最小距离为$d^*$的代码可以检测$d^*-1$错误，并可以纠正$\frac{d^*-1}{2}$错误。因此，要纠正一个错误，代码的最小距离必须至少为3。
线性码意味着$c\left(m+m^{\prime}\right)=c(m)+c\left(m^{\prime}\right)$，因此有
$e_i, 1 \leq i \leq k$构成了消息空间的基础，$e_i$的码字完全描述了线性码。因此，不需要带有$2^k$条目的代码本。我们仅需要一个矩阵即可
我们可以假设生成矩阵$G$采取特定形式。事实上，如果我们在$G$上执行基本行操作（在$Z_2$上，这意味着我们将一行添加到另一行），我们不会更改代码中的码字集合。我们甚至可以在不从根本上改变代码属性的情况下对列进行排列。因此，使用高斯消除，我们可以假设$G$采取更简单的形式：
其中$S$是$k \times(n-k)$。
假设我们的矩阵$G$生成单纠错代码，因此没有权重1或2的码字，$G$的奇偶校验部分$S$必须满足以下2个条件：
- $S$中每行的权重必须至少为2，因为$I$部分的每一行正好有一个权重。
- 没有两行$S$是相同的。否则，将这两行相加将给出一个权重2的码字。
汉明编码是单个纠错线性块代码，具有$(n, k)=\left(2^m-1,2^m-1-m\right)$，其中$m=n-k$是代码中的检查位数。最简单的非平凡代码是$m=3$，即$(7,4)$ Hamming代码。
之所以$k=2^m-1-m$
$2^m$减去汉明重量为0和1的码字
我们知道如何用任何线性代码进行编码。由消息$m$生成的码字只是$c=m G$。但是解码怎么样？如果没有引入错误，第一个$k$位构成消息。但可能已经引入了错误。当只有一个错误时，正如我们现在所显示的那样，解码很容易。
对于每个生成器矩阵$G=[I S]$，都有一个奇偶校验矩阵$H$定义
由于$S$的大小为$k \times(n-k)$，我们的单位矩阵大小为$(n-k) \times(n-k)$，$H$的大小为$n \times(n-k)$。重要的观察是$G H=S+S=0$，因此$c=m G$满足$c H=m G H=0$。这意味着，如果有错误，并且我们收到了$\tilde{c}=c+e_i$，我们可以通过计算$\tilde{c} H$找到错误$e_i$，因为这应该是$c H+e_i H=e_i H$。因此，$\tilde{c} H$必须是$H$的行之一，该行的索引指示哪个位已损坏。一旦我们知道哪个位已损坏，我们就可以恢复消息。