计算机网络与计算机组成原理的交叉知识点之一就是校验码:奇偶校验码、海明校验码、循环冗余校验码。
码距
检验原理即添加多余的位数,D->DR,其中R为差错检测与纠正比特(冗余信息),基础学科中用到的大多是线性编码。
码距,能区分两个数据的最少位数。比如我们使用二进制,11(3)和10(2),能区分它们的最少位数是1位,即码距为1。在检错码中,如果编码集的码距ds = r+1,那么可以检测r位的差错。
比如我们在奇偶校验码中,在一串数据的最后一位添上冗余位,110(3)和100(2),能区分它们的最少位数是2位,即码距为2,因此它能检验1位错。
奇偶校验码
在末尾添上1个冗余位,使得整个数字串有奇(偶)数个1。只能检验奇数位错,检错率50%,不能纠错。
扩展:
二维奇偶校验:检测奇数位差错、部分偶数位差错,纠正同一行/列的奇数位错。
海明码
https://blog.csdn.net/lhc1105/article/details/39619643
这篇文讲得相当好,就不自己总结了。
补充一点:纠错d位,需要码距2d+1位;检错d位,需要码距d+1位。
循环冗余码
循环冗余码是一种检错能力更强大的差错编码,广泛应用于实际网络中。
它将数据比特D视为一个二进制数,选择一个r+1位的比特模式(生成比特模式),即生成多项式G,通过<D,r位0>与G的模二除法得到r位的CRC比特R,满足<D,R>可以整除G。
上图来自哈工大PPT,侵删。