大二上，计组原理笔记（3）2.6数据校验码

前言：
我的个人听课记录，毕竟是初学，错误在所难免，我知道了错误会改正更新，欢迎指导也欢迎一起讨论学习。

2.6 数据校验码

{n,r}即{k+r,r}

2.6.1 奇偶校验码（k+1，k）

1.简单奇偶校验
只能检错，不能纠错。且只能检错奇位错误，不能确定出错的位置。

2.交叉奇偶校验

可检错也可纠错了。

例：偶校验

0101 ——> 0
1111 ——> 1
||||     |
1011 ——> 1

可以判断第二行第四列出错，所以信息应该是：01011110，于是计算机可以进行纠错。

2.6.2海明码（汉明码）

有两种形式：（6，3）（7，4）
可设密码

M=D × \times × G中，D是信息码，G是生成矩阵。（生成矩阵可以自己设定,由此决定这可以来设密码）
G={ I_k，P }
H={ P^T, I_m}, H 是校验矩阵，
校验子：S=B × \times × H^T
例题：（6，3）

                |1 1 0 1 0 1| 
生成矩阵为：G=   |0 1 0 0 1 1|
                |0 0 1 1 0 1|
                
（1）将101进行编码，
   （101）* G=111000  （异或运算）
    3位的信息码一共有八种，各自 * G得到对应的海明码编码。
（2）已知生成的编码为 A= 110101，求它的信息码 m 。
    设 m =(m2,m1,m0)
    则 m * G = ( m2,m^m1,m0,m2^m0,m1,m2^m1^m0 )(^为异或）
    若 m 用 a5a4a3a2a1a0 表示，
    则m2=a5=1,m1=a2=0,m0=a3=0,所以 m=100
(3)得到的编码 B= 100101，对其检纠错并译码。
   第一步：保证G中Ik为“单位矩阵”，即只有主对角线是1.所以需要将G进行r1^r2（异或）运算得到
       |1 0 0 1 1 0|                 
   G=  |0 1 0 0 1 1|   
       |0 0 1 1 0 1|    
   第二步：求H的转置行列式  HT          
                  |110|                     
                  |011|
    HT(H的转置）=  |101|
                  |100|
                  |010|
                  |011|                                  
    第三步：求校验子                                    
     S=B*HT=011
   第四步：找出正确编码。
      由纠错表可知011代表a3出错，（记住111代表不止一位出错，无法纠错。）
   于是我们知道正确的编码是 A= 101101
   （由（2）得）则m2=a5=1,m1=a2=0,m0=a3=1,所以 m=101
ps:（2）中编码为A，（3）中编码为B，是有区别的。
一般用A表示代表没有错，不用检纠错；B表示不确定，就需要检纠错。

（6，3）检纠错能力：检错两位，纠错1位。

2.6.3循环冗余校验码（CRC）

不能设密码了。

例题：（7，4）
（1）选择生成多项式为1011，把4位有效信息1100编成CRC码。
准备一：
表示生成多项式：1011=X³+X¹+X⁰=X³+X+1
准备二：
表示信息码：1100=X³+X²
准备三：
确定2^n-k : X^7-4 = X³
计算：
求校验码：
r(x)=(X³+X²) X³mod (X³+X+1)=x,
x代表10，要三位，则补0，即010
出结果：1100 010

（2）若收到 B=1101010，是否出错？
准备一：
表示生成多项式：1011=X³+X+1
准备二：
表示B= X⁶+X⁵+X³+X
计算：
（ X⁶+X⁵+X³+X ）mod ( X³+X+1 )
= x+1
x+1代表11，空位补0，即011
结果：011不是0，出错了。

例：求“A”，用CRC（7，4）表示。
A的ASCII码是41，即
01000001，分成四位有两份。
0100用CRC表示有7位，
0001用CRC表示有7位，
但计算机中存储两个字节，16位，于是补0.
0 （ 0100CRC）7位 | 0 （0001CRC）7位
一共就有16位了。
·
·
·
·
·
·