V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
nowheremanx
V2EX  ›  程序员

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

  •  
  •   nowheremanx · 2023-09-15 13:03:58 +08:00 · 1276 次点击
    这是一个创建于 435 天前的主题,其中的信息可能已经有所发展或是发生改变。
    最近在学网络通讯,学到 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 太少,性能不太能提升。


    一算概率就糊涂,过来请教一下,谢谢。
    10 条回复    2023-09-16 17:46:44 +08:00
    lysS
        1
    lysS  
       2023-09-15 14:05:33 +08:00
    crc 算是最简单的了, 上层一般只拿它来当哈希用。差错恢复还有 rs 码那些,其实异或,checksum 都能做到差错恢复
    dode
        2
    dode  
       2023-09-15 15:47:34 +08:00 via Android
    还有海明码
    wy315700
        3
    wy315700  
       2023-09-15 15:50:45 +08:00
    8b/10b 编码可以了解下,坏一个 bit 可以自动修复
    null177
        4
    null177  
       2023-09-15 17:04:11 +08:00
    还有 LDPC,SSD 上常用的,接近香农极限
    另外还有 Turbo 码和 Polor 码
    laminux29
        5
    laminux29  
       2023-09-15 17:45:21 +08:00
    这些验证方法本质上是一个大集合对小集合的满射但非单射,所以自然存在重复情况。曾经在某数据中心分析流量,链路层最高能达到 3%的错误率。

    完美验证方法异构+双射。异构的意思是数据需要进行变换,来防止数据在相同硬件位置与路线,遭遇相同故障。双射是满射+单射,相当于一条数据再发一次。
    nowheremanx
        6
    nowheremanx  
    OP
       2023-09-15 21:03:40 +08:00
    @null177 对对对,我满脑子都在想是不是和“香农极限”有关。 像楼上说的,复杂的算法很多,但我现在主要是纠结 8-bit 空间如何做到最优的差错。
    julyclyde
        7
    julyclyde  
       2023-09-16 13:12:06 +08:00
    @laminux29 确定满嘛?我觉得都不一定满
    mightybruce
        8
    mightybruce  
       2023-09-16 17:32:39 +08:00
    这不是工程领域需要研究的, 感兴趣要去啃信息论和编码理论的书,前提还要会抽象代数知识。我以前没少算这些,除非你是做安全或分布式存储系统开发的,你大概率是不会遇到的。
    mightybruce
        9
    mightybruce  
       2023-09-16 17:34:49 +08:00
    数据验证日常生活都多得很, 你的身份证如果有一位是填错的,也是可以纠正的
    条形码和二维码都有一定的纠错能力。
    Reed-Solomon Codes——RS 纠错码在存储中用得多。
    mightybruce
        10
    mightybruce  
       2023-09-16 17:46:44 +08:00
    编码理论是一本非常厚的数学书,密密麻麻都是公式和计算。里面就有要讨论的伽罗华域(Galois Fields),码字,编码空间、编码距离、线性码、非线性码这些。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1951 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 00:25 · PVG 08:25 · LAX 16:25 · JFK 19:25
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.