填充半径和堆积半径

线性空间$GF(q{)}^n$中的关于$v\text{v}v$的半径为$t$的汉明球（Hamming Sphere），它是一个集合，包含所有的与$v\text{v}v$有至多$t$个不同分量的点。体积定义为包含的点数：
$$V(t;q)=\sum _{i=0}^t\left(\genfrac{}{}{0ex}{}{n}{i}\right)(q-1{)}^i$$
汉明球不像（欧几里得）球，它使用的距离是汉明距离，只关心不同位置的数量。

填充半径（packing radius）：令所有码字$c\text{c}c\in \mathcal{C}$上都有相同整数半径的汉明球，不断增大半径，直到继续增大会导致汉明球相交。

覆盖半径（covering radius）：令所有码字$c\text{c}c\in \mathcal{C}$上都有相同整数半径的汉明球，不断减小半径，直到继续减小会导致存在$v\text{v}v\in GF(q{)}^n$不落在任何一个汉明球内部。

完美码（perfect code）：关于码字的汉明球可以完全覆盖整个空间，同时这些汉明球不相交。即，填充半径等于覆盖半径。

Hamming Bound：对于任意$(n,k,d{)}_q$码，有
$$k\le n-{\log }_q\left(\sum _{i=0}^t\left(\genfrac{}{}{0ex}{}{n}{i}\right)(q-1{)}^i\right),t=\lfloor (d-1)/2\rfloor$$

易知，完美码达到汉明界，码率为
$$R=\frac{k}{n}=1-\frac{{\log }_{q}V(t;q)}{n}$$

全部的非平凡完美码为：

• Hamming Code：$((q^m-1)/(q-1),(q^m-1)/(q-1)-m)$汉明码

• Golay Code：$(23,12,7)$二元格雷码，$(11,6,5)$三元格雷码

Hamming Code

设计思路

定理：编码$\mathcal{C}$包含汉明重量为$w$的非零码字$⟺$校验矩阵$H$中存在线性相关的$w$列。推出，码$\mathcal{C}$的最小距离$d_{min}$等于$H$中线性相关的最少列数。

思路：一个$GF(q)$上的$m$元组，它包含$q^m$种可能。由非零元按列组合，得到校验矩阵$H$。为了使得编码的极小距离至少为$3$，需要$H$中的任意$2$列线性不相关，因此要$GF(q{)}^m$的每个一维子空间中只能选取至多一个向量。最终，$H\in GF(q{)}^{m\times (q^m-1)/(q-1)}$

汉明码（Hamming Code）：将$n=(q^m-1)/(q-1)$，$(n,n-m)$线性码叫做汉明码。

作为循环码

大多数汉明码是循环码，其构造方法为：

1. 令$\alpha$是$GF(q^m)$的本原元，$\beta ={\alpha }^{q-1}$，那么$ord(\beta )=(q^m-1)/(q-1)$，记$n=(q^m-1)/(q-1)$
2. 计算$\beta$的极小多项式$g(x)|x^n-1$，因此$g(x)$是$n$长循环码的生成多项式。
3. $\beta$是$g(x)$的零点，因此校验矩阵为$H=[{\beta }^0,{\beta }^1,\cdots ,{\beta }^{n-1}]$
4. 容易看出，$H$作为$GF(q)$上矩阵，它的形状是$m\times n$的，因此得到的循环码是$(n,n-m)$线性码（就是汉明码）。

定理：令$\alpha$是$GF(q^m)$的本原元，$\beta ={\alpha }^{q-1}$，构造校验矩阵$H=[{\beta }^0,{\beta }^1,\cdots ,{\beta }^{n-1}]$，对应的$GF(q)$上$n=(q^m-1)/(q-1)$长的循环码，有
$$d_{min}\ge 3⟺gcd(n,q-1)=1⟺gcd(m,q-1)=1$$
定理：汉明码是可以纠正$1$位错（error correction）、检出$2$位错（error detection）的完美码。

非循环汉明码的例子：$GF(4)$上的$(21,18)$汉明码，因为$gcd(21,4-1)=3$

Golay Code

格雷码（？）这是 Golay Code（一种纠错码），不是 Gray Code（一种编码，任意两个相邻的代码只有一位二进制数不同），专有名词翻译好难啊 ╮(╯﹏╰)╭

$(23,12,7)$二元格雷码（binary Golay code），其生成多项式为：
$$g(x)=x^{11}+x^{10}+x^6+x^5+x^4+x^2+1\in GF(2)[x]$$
容易计算它的互反多项式（reciprocal polynomial），
$$\tilde{g}(x)=x^{11}+x^9+x^7+x^6+x^5+x+1\in GF(2)[x]$$
且满足
$$(x-1)g(x)\tilde{g}(x)=x^{23}-1$$
由于$g,\tilde{g}$都是不可约多项式，因此只有两个$(23,12)$二元循环码。且由$g(x)$生成的码$\mathcal{C}$（cyclic Golay code）和由$\tilde{g}(x)$生成的码${\mathcal{C}}^{\prime }$（reciprocal cyclic Golay code）同构，确切地$c(x)\in \mathcal{C}⟺\tilde{c}(x)\in {\mathcal{C}}^{\prime }$

定理1：二元格雷码的任意非零码字的汉明重量至少是$5$，并且其中的任意偶数重量都被$4$整除。即，二元格雷码是$(23,12,7)$线性码。

定理2：$(23,12,7)$二元格雷码是可以纠正$3$位错误的完美码（perfect triple-error-correcting code），$(11,6,5)$三元格雷码是可以纠正$2$位错误的完美码（perfect ternary Golay code），这两个编码是唯二的可纠正至少$2$位错误的非平凡完美码。

Cyclic Redundancy Codes

突发错误

一个$t$长的循环突发错误（cyclic burst）是指，一个长度为$t$的循环连续分量，它的第一位和最后一位非零。它可以被描述为$e(x)=x^{i}b(x)\mathrm{m}\mathrm{o}\mathrm{d}{x}^n-1$，其中$b(x)$是度数为$t-1$且常数项非零的某多项式。

如果一个循环码$\mathcal{C}$的生成多项式为$g(x)$，且对于所有的长度至多为$t$的突发错误$e(x)$，使得校验子$s(x)=R_{g(x)}[e(x)]$两两不同，那么我们说循环码$\mathcal{C}$能够纠正长度至多为$t$的所有循环突发错误。

假设$(n,k)$循环码$\mathcal{C}$可以纠正长度至多为$t$的所有循环突发错误，那么可以通过交叉符号（interleaving the symbols）来构造一个$(jn,jk)$循环码${\mathcal{C}}^{\prime }$，它可以纠正长度至多为$jt$的所有循环突发错误：假设$\mathcal{C}$的生成多项式是$g(x)|x^n-1$，则${\mathcal{C}}^{\prime }$的生成多项式是$g(x^j)|x^{jn}-1$

CRC

循环码常被用来检出随机错误（error detection，不必纠正）， 这时常被叫做循环冗余码（cyclic redundancy codes）

循环冗余码可以写作由$g(x)=(x+1)p(x)\in GF(2)[x]$生成的循环码，其中$p(x)$是度数为$m$的本原多项式。因此，它是$(2^m-1,2^m-m-2)$循环码。

注意到$x+1|c(x)$，而$x+1$的汉明重量为$2$，因此码字的重量都是偶数。另外$p(x)|c(x)$，因此它符合汉明码字的性质。即：循环冗余码是汉明码的偶数重量的码字，其最小距离为$d_{min}=4$

校验方法：简单计算除法，$s(x)=R_{g(x)}[c(x)+e(x)]$，检查校验子$s(x)$是否为零。

定理：最小距离为$d_{min}$的$(n,k)$二元循环码，它可以检出所有的重量小于$d_{min}$的错误（因为非零码字的汉明重量不小于$d_{min}$），以及检出所有的长度小于$n-k$的循环突发错误（这会使得$R_{g(x)}[b(x)]\ne 0$，因为$\mathrm{deg}g=n-k$）