底层网络数据传输检验方法

[nowheremanx]

最近在学网络通讯，学到 CRC 之类的数据检验方法。这些是普通软件工程师无法触及到的底层问题，挺有意思的。

如果是一个 byte 的数据，也就是 8 个 bit ，假定一个 bit 的出错概率是 p 。那么我浪费一点数据空间，肯定是做到检验的效果。

一个 bit 拿来检验，肯定是能 parity check 了。ABCDEFG(H)，最后一个 bit 的 0/1 状态给前面的数据补足，形成偶数个 1 或者奇数个 1 。这个缺点就是无法检验偶数个错误的情况。 求这种情况下，检验出错误发生的概率。

两个 bit 拿来检验，土方法自然是 1 对 3 ，每 4 个 bit 形成一个组合进行 parity check ，比如 ABCDEF(GH)。数学比较差，直觉就是算出 4 个 bit 组合的检验成功的概率，然后做个 1-p(miss)xp(miss)计算。对于 4 个 bit 的概率，我手动枚举相加好像比 7+1 的情况简单很多。两个检验 bit 的位置似乎不影响概率，但是实际应用上有讲究吗？比如 ABC(D)EFG(H)会不会更好？

最后还有个问题，想求问 2 个 bit 还有更好的方法吗？ CRC 算法复杂一点，但是好像因为 bit 太少，性能不太能提升。


一算概率就糊涂，过来请教一下，谢谢。

[lysS]

crc 算是最简单的了， 上层一般只拿它来当哈希用。差错恢复还有 rs 码那些，其实异或，checksum 都能做到差错恢复

[dode]

还有海明码

[wy315700]

8b/10b 编码可以了解下，坏一个 bit 可以自动修复

[null177]

还有 LDPC,SSD 上常用的,接近香农极限
另外还有 Turbo 码和 Polor 码

[laminux29]

这些验证方法本质上是一个大集合对小集合的满射但非单射，所以自然存在重复情况。曾经在某数据中心分析流量，链路层最高能达到 3%的错误率。

完美验证方法异构+双射。异构的意思是数据需要进行变换，来防止数据在相同硬件位置与路线，遭遇相同故障。双射是满射+单射，相当于一条数据再发一次。

[nowheremanx]

@null177 对对对，我满脑子都在想是不是和“香农极限”有关。 像楼上说的，复杂的算法很多，但我现在主要是纠结 8-bit 空间如何做到最优的差错。

[julyclyde]

@laminux29 确定满嘛？我觉得都不一定满

[mightybruce]

这不是工程领域需要研究的， 感兴趣要去啃信息论和编码理论的书，前提还要会抽象代数知识。我以前没少算这些，除非你是做安全或分布式存储系统开发的，你大概率是不会遇到的。

[mightybruce]

数据验证日常生活都多得很， 你的身份证如果有一位是填错的，也是可以纠正的
条形码和二维码都有一定的纠错能力。
Reed-Solomon Codes——RS 纠错码在存储中用得多。

[mightybruce]

编码理论是一本非常厚的数学书，密密麻麻都是公式和计算。里面就有要讨论的伽罗华域(Galois Fields)，码字，编码空间、编码距离、线性码、非线性码这些。