1 什么是纠错码?
数学家就像法国人一样，无论你对他们讲什么，他们都把它翻译成自己的语言，并且立刻成为一些全新的东西.———歌德(Goethe)
f是本章介绍通信的*一般化的数学模型以及纠错的数学描述.先给出纠错的通俗例子以说明纠错的原理.然后抽象出纠错码的3个基本参数：码长n，信息位数k和*小距离d.讲述纠错码理论*基本的两个问题：构造性质好的纠错码和构造好的纠错译码算法.用进一步的例子表明：构造好码和好的译码算法都是很有学问的，需要利用组合学，数论和代数学等方面的数学工具.
1.1通信和纠错：数学模型
现代人们在生活中的通信方式是多种多样的，如打电话、传送电子邮件以及宇宙飞船将金星图片传回地球等.虽然它们的形式不同，但是它们的数学模型可以表示成以下*简单的形式：
发方把信息x通过信道传给收方.在有线电话系统中，电话线就是传输信息的信道.在唐诗“烽火连三月，家书抵万金”中，烽火台燃起的烽火和邮差(驿站)分别是传递敌人入侵消息和寄送家书的信道.
要发送的信息也可以有不同的形式(声音、文字、图像、数据).在近几十年所发展的数字通信中，各种信息都用物理手段编成离散的脉冲信号发出，而脉冲信号只有有限多个状态.于是，数论便派上了用场.
早在18世纪，大数学家欧拉在研究整数性质的过程中发明了“同余”的概念.后来，另一个大数学家高斯发明了同余式符号，一直沿用至今.设m是正整数.两个整数a和b叫做模m同余，是指m整除a-b，即a-bm是整数.这表示成如下同余式的形式：
a≡b(modm).
在初等数论中，如果非零整数a整除b，则表示成a|b.若a不能整除b，则表示成.于是a≡b(modm)当且仅当m|(a-b)，而这也相当于a=b+ml，其中l是整数.
同余式有像等式一样的类似性质，并且也可以像等式那样作加减乘法：
(1)a≡a(modm);
(2)若a≡b(modm)，则b≡a(modm);
(3)若a≡b(modm)，b≡c(modm)，则a≡c(modm);
(4)若a≡b(modm)，c≡d(modm)，则
a+c≡b+d(modm)，
a-c≡b-d(modm)，
ac≡bd(modm).
但是对于同余式作除法时要小心.例如，2≡6(mod4)，但是两边不能除以2，因为1？3(mod4)，这里a？b(modm)表示a和b模m不同余，即m|/(a-b).事实上，同余式除法有以下结果：
(5)若ad≡bd(modm)并且d和m互素(即d和m的*大公因子为1)，则a≡b(modm).
对一个固定的正整数m，如果把模m与a同余的所有整数放在一起，叫做模m的一个同余类，表示成a.由于每个整数模m必同余于0，当中的一个，所以模m共有m个同余类，它们形成的m元集合表示成Zm.于是对两个整数a和当且仅当a≡b(modm).可以在m元集合Zm中自然地定义加减乘运算：对于整数，那么前面的性质(4)相当于.
类似可知，同余类的加法和乘法运算还满足交换律、结合律与分配律.这样的集合在数学中叫做(交换)环，于是Zm叫做模m同余类环.
性质(5)可以表述如下：
(5′)在Zm中，若a d=b d并且d和m互素，则a=b，即等式两边可以消去d(作除法).
前面的例子取可以表示成，不能消去2而得到1=3，因为2和4不互素.但是若m是一个素数，并且d≠0，这表明d不被p整除.由于p是素数，d必然与p互素.于是可得到a=b.这表明，在Zp中，每个不为0的元素d都可以作为除数.换句话说，在Zp中可以像有理数全体、实数全体或者复数全体那样进行加减乘除四则运算，只有零(0)不能作除数.这样的集合在数学中叫做一个域(field).于是对每个素数p都有一个p个元素的有限域，今后把它改记成Fp.例如，对于p=3，表1.1.1与表1.1.2是域F3={0，1，2}中的加法和乘法运算表.
下面是F3中运算的例子：
由于有限域Fp中可以进行四则运算，通常把通信中的信息用Fp中的p个元素来表示.
表1.1.1
表1.1.2
为了书写方便，在给定素数p之后，把Fp中元素a简记成a.于是在F3中，事实上，通信中使用*多的是二元域F2={0，1}.这是*简单的域，运算为：
现在假设要传递8个信息{赵，钱，孙，李，周，吴，郑，王}.如果每位数字取自二元域F2中的0或1，可以用长为3的8个向量来表示它们：
设想把“钱=(100)”传出，如果信道中出错，如第二位的0变成1，收方收到了(110).这时收方对于出错毫无所知，因为收方可认为没有出错，即发来的是(110)=李，也有可能是第1位
展开
