介绍

1. 通信的数学基础：信息论，通信的可靠性。
2. 通信和纠错的数学模型

发送方：原始信息（声音、文字、图像、数据）$\rarr$ 脉冲电信号（有限多状态）

m个状态表示为$0,1,\cdots,m-1$(有限域)，模m作加减乘运算（模m同余类环）
$F^n_q$:$F_q$上n维向量空间，$q^n$个不同向量。

例：$F^3_2$中有8个向量，可表示为$0,1,\cdots,7$这8个信息（000,100,010,110,001,101,011,111）。

信道：途径为大气、网络等。

例1（奇偶校验码）把每个向量后面加上1位（0或1），使新的码字有偶数个1，均变成长为4的二元向量
$0=(0000)\quad1=(1001)\quad2=(0101)\quad3=(1100)\\ 4=(0011)\quad5=(1010)\quad6=(0110)\quad7=(1111)$

特点：不同码字至少有2位不同

• 长为4的二元变量有16个，只有上述8个是有意义的
• 比如 （1100）$\rarr$ (1110) 能发现错误但不能纠错
• 传输速度为原来的4/3，效率为原来的3/4

例2（重复码）把每个信息重复3遍$0=(000000000),1=(100100100),\cdots,7=(111111111)$

特点：不同码字至少有3位不一样。长为9的二元向量共有512个，只有8个有意义。

• 比如：(101101101)$\rarr$(1011$\color{red}1$1101) 可以发现错误，纠错译码为(101101101)
• 可检查2位错误，纠正1位错误，效率为原来的1/3.

纠错码的本质

• 1.降低通信效率，提高通信纠错能力。
• 2.通过相异位进行检错与纠错。

带纠错功能的通信系统的数学模型

涉及的数学工具

• 初等数论、线性代数、抽象代数（群环域）
• 组合学、代数几何、代数数论、群表示论

习题1（书号的纠错编码）

标准书号：将每本书编成$F_{11}=\{0,1,\cdots,10\}$上的十位数字，前9位用0到9的数字，若末位是10则表示为X，例如：ISBN 0-19-859617-0

十位数字满足：$\sum_{i=1}^{10}ia_i\equiv0(mod~11)$, 上例书号有$\sum_{i=1}^{10}ia_i=253\equiv0(mod~11)$

下面证明可以检查任何1位发生错误
若第i位发生错误，$a_i$变为$a'_i$，则一定有求和式$\not\equiv0(mod~11)$
反证：$ia_i\equiv x(mod~11)$，假设$ia'_i\equiv x(mod~11)$，则$i(a_i-a'_i)\equiv0(mod~11)$，而$(i,11)=1$，则$11|(a_i-a'_i)$，但$a_i,a'_i$取自$0,1,\cdots,10$，不可能成立。

可以检查任何2位数字发生置换的错误（当$i\neq q$时，若$a_i,a_j$对调）

反证：若无法检测出错误，则满足调换后的和式仍同余于0，其他位数字均不变。设$ia_i+ja_j\equiv x(mod~11)$，对调后有$ia_j+ja_i\equiv x(mod~11)$，则$(i-j)(a_i-a_j)\equiv0(mod~11)$，而$(i-j,11)=1$，则$11|(a_i-a_j)$，同上矛盾。

基本概念

定义1 $F^n_q$表示有限域$F_q$上的n维向量空间。$F_q^n$的每个非空子集$C$都叫作一个$q$元码，$n$叫作该码的码长，$C$中向量叫作码字。
用$K$表示$C$中码字个数，即$K=|C|$，则$1\leq K\leq q^n$.
$k=\log_qK$叫作码$C$的信息位数（$k$为实数$0\leq k\leq n$）.
$\frac{k}{n}$叫作码$C$的效率（或叫信息率）。

定义2 设$a=(a_1,\cdots,a_n)$和$b=(b_1,\cdots,b_n)$是$F^n_q$中两个向量，则向量$a$的Hamming权定义为非零向量$a_i$的个数，表示成$\omega_H(a)$或$\omega(a)$即$\omega_H(a)=\#\{i|1\leq i\leq n,a_i\neq0\}$.向量a和b之间的Hamming距离指它们相异位的个数，表示成$d_H(a,b)$或$d(a,b)$即$d_H(a,b)=\#\{i|1\leq i\leq n,a_i\neq b_i\}=\omega_H(a-b)$

性质(1) $d(a,b)\geq0,d(a,b)=0\lrArr a=b$
$\hphantom{--}$(2)$d(a,b)=d(b,a)$
$\hphantom{--}$(3)$d(a,c)\leq d(a,b)+d(b,c)$

定义3 设$C$是码长为n的q元码，$K=|C|\geq2$，定义$C$的最小距离为不同码字之间Hamming距离的最小值，表示成$d(C)$即$d=d(C)=min\{d(c,c')|c,c'\in C,c\neq c'\}$

定理1 如果纠错码$C$的最小距离为$d$，则$C$可检查$\leq d-1$位错，可纠正$\leq[\frac{d-1}2]$.

证明：（1）可以检查$d-1$位错
$\qquad$设发出码字为c，错位不超过$d-1$，即错误向量$\varepsilon$满足$1\leq\omega(\varepsilon)\leq d-1$，收到的向量为$v=c+\varepsilon$且$v\neq c$，所以$d(c,v)=\omega(v-c)=\omega(\varepsilon)\leq d-1$. 由于对每个码字$c'\neq c,d(c',c)\geq d$，所以$v$不为$c'$，则$v$不是码字，即判断出错.

(2) 可以纠正[(d-1)/2]位错
$\qquad$设$1\leq\omega(\varepsilon)\leq[(d-1)/2]$，此时$d(c,v)=\omega(\varepsilon)\leq[(d-1)/2]$，对每个码字$c'\neq c$，由三角不等式$d(c',v)\geq d(c',c)-d(c,v)\geq d-[(d-1)/2]>[(d-1)/2]$，即$c$是唯一与$v$最近的码字，将$v$译成$c$是正确纠错。

• 对每个固定的有限域$F^n_q$，q元纠错码$C$有三个基本参数：
  (1) 码长n
  (2) 码字个数$K=|C|$（或信息位数$k=\log_qK$）
  (3) 最小距离$d=d(C),1\leq d\leq n$

基本研究课题

(1) 构造性能良好的纠错码，要求效率与纠错能力越大越好；
(2) 研制工程上实用的译码算法。

在纠错码理论中，对q元纠错码进行分类，同一类纠错码有相同的$n,K,d$，主要有一下三种：
（1）分量置换 对于集合$\{1,2,\cdots,n\}$的每个置换$\sigma$，把每个码字$c=\{c_1,c_2,\cdots,c_n\}$变成$\sigma(c)=\{c_{\sigma(1)},\cdots,c_{\sigma(n)}\}$

(2) 元素置换 $f$是$F_q$到$F_q$的一一映射，把每个码字$c=\{c_1,c_2,\cdots,c_n\}$变成$f(c)=\{f(c_1),f(c_2),\cdots,f(c_n)\}$

(3) 码的平移 设$C\subset F_q^n$，对每个$v\in F^n_q,C'=\{c+v|v\in C\}$

通过有限次上述三种变换可以得到的码称为等价的码。