这是一个创建于 427 天前的主题，其中的信息可能已经有所发展或是发生改变。
最近在学网络通讯，学到 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 太少，性能不太能提升。
一算概率就糊涂，过来请教一下，谢谢。
如果是一个 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 太少，性能不太能提升。
一算概率就糊涂，过来请教一下，谢谢。
 |
1
lysS 2023-09-15 14:05:33 +08:00
crc 算是最简单的了， 上层一般只拿它来当哈希用。差错恢复还有 rs 码那些，其实异或，checksum 都能做到差错恢复
|
 |
2
dode 2023-09-15 15:47:34 +08:00 via Android
还有海明码
|
 |
3
wy315700 2023-09-15 15:50:45 +08:00
8b/10b 编码可以了解下，坏一个 bit 可以自动修复
|
 |
4
null177 2023-09-15 17:04:11 +08:00
还有 LDPC,SSD 上常用的,接近香农极限
另外还有 Turbo 码和 Polor 码 |
 |
5
laminux29 2023-09-15 17:45:21 +08:00
这些验证方法本质上是一个大集合对小集合的满射但非单射，所以自然存在重复情况。曾经在某数据中心分析流量，链路层最高能达到 3%的错误率。
完美验证方法异构+双射。异构的意思是数据需要进行变换，来防止数据在相同硬件位置与路线，遭遇相同故障。双射是满射+单射，相当于一条数据再发一次。 |
 |
6
nowheremanx OP @null177 对对对，我满脑子都在想是不是和“香农极限”有关。 像楼上说的，复杂的算法很多，但我现在主要是纠结 8-bit 空间如何做到最优的差错。
|
 |
8
mightybruce 2023-09-16 17:32:39 +08:00
这不是工程领域需要研究的， 感兴趣要去啃信息论和编码理论的书，前提还要会抽象代数知识。我以前没少算这些，除非你是做安全或分布式存储系统开发的，你大概率是不会遇到的。
|
|
9
mightybruce 2023-09-16 17:34:49 +08:00
数据验证日常生活都多得很， 你的身份证如果有一位是填错的，也是可以纠正的
条形码和二维码都有一定的纠错能力。 Reed-Solomon Codes——RS 纠错码在存储中用得多。 |
|
10
mightybruce 2023-09-16 17:46:44 +08:00
编码理论是一本非常厚的数学书，密密麻麻都是公式和计算。里面就有要讨论的伽罗华域(Galois Fields)，码字，编码空间、编码距离、线性码、非线性码这些。
|
Select Language