新生课论文.doc

学习校正码理论与应用的体会
——数学与统计学院 信息与计算科学1401班 刘赵婧
校验码通常是一组数字的最后一位，由前面的数字通过某种运算得出，用以检验该组数字的正确性。常见的校验码有中华人民共和国居民身份证的最后一位、ISBN号码的最， A∈Zn,向量(x1,x2, …,xm) ，有时可不加逗点，特别是当取具体的0或1时，一般不加逗点，例如（0101）．
定义3 在制码法中如果在收到的n位码字中有k位或k位以下的错误时，能知道收到的码字有错，则说此种制码法能检定k位错误，若能校正此k位错误，则说此种制码法能校正k位错误。
表2中的输送码，能检定一位错误，但不能校正一位错误．
定义4 (汉明(Hamming)距离) 设X，Y为中的两个元，规定X与Y之间的距离为H(X，Y)=X,Y中不相同的数码个数．
例如：X=(1010)，Y=(1001)，因X与Y第三、四位共有二位不相同，故H(X，Y)=2，
若令0=(0,0, …,0) ，则 H(X，0)=X中含1的个数，用|x|表示．
令 X=(x1,x2,…,xn)， Y=(y1,y2,…,yn)，加减按向量的加减定义，即
X+Y=(x1+ y1,x2+ y2,…,xn +yn)，
在上式中， l±1=0±0=0，1±0=0±1=1．也就是说，如果与相同，则它们的差为0，否则为1。一些不熟悉抽象代数的人也许会觉得1+1=0很怪，但如抽象地把0、1分别对应“偶”、“奇”两个概念，就容易理解了熟悉抽象代数的人知道这样的定义加上一般的乘法, 使得{0，1}成为一个域，这样Zn就作成一个向量空间了。不难看出，若Zn的一个非空子集A对加法封闭，则A就作成一个子空间。
由上面的讨论，可以看出X、Y的距离等于X+Y中1的个数，且容易得到下面的一些性质。
定理1　设X,Y,U ∈Zn,则
(1)　 X+Y=X-Y，注意由此可得X+X=X-X=0 　，从而； X=-X
(2)　 X≠Y，则X+Y ≠ 0；
(3)　 H(X，Y)= |X-Y|；
(4) H(X，Y) ≤ H(X，Y) +H(X，Y)(三角不等式)
Zn的子集的离散度(disperse)。
定义5　设A⊂Zn ，称　
　 d(A)=min|X-Y|, X≠Y, X,Y∈A
为A的离散度。即d(A)为A中不同元素间距离的最小值。
定理2　若A为的一个子空间，则
d(A)=min|X|, 0≠X∈A。
证明　只需加法封闭，因X+Y可以A中的元素表示。
3　检错码
定理3　设A为一码表，则它能检验出至多k位错误d(A)≥k+1。
证明 　设d(A)≥k+1，X1为X之误传，因
|X1-X|≤k ，而d(A)≥k+1，故X1不在A中，必定有错。
若d(A)≤k，则存在X、Y∈A， |X-Y|≤k，故Y可以为X的原像之误传，与假设允许k个错误的要求不合。
由定理3可知若要检定输送的码字是否有一个或一个以下的错误，得要有d(A)≥2，若不加检定码，A的元素皆为信息码，则d(A)=l，不可能检定错误．因此我们至少要加一位检定数码．现在要证明只要加一位检定数码就足以检定一位的错误，因此表2中的重复输送是不必要的．令O(X)表X的1的奇偶数(Parity)，容易证明下面的定理．
定理