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

CRC 实现算法太难理解了

  •  1
     
  •   zhilincom · 2023-03-31 04:53:29 +08:00 · 1638 次点击
    这是一个创建于 588 天前的主题,其中的信息可能已经有所发展或是发生改变。

    几乎所有教程讲的原理都是把数据看成一串很长的 01 组成的二进制数,计算时按 bit 逐位右移异或多项式,refin=true 时需要把整串数据反转再计算。(这些理解起来不难,并且我也手算了 n 多次都能和计算器结果符合上。)

    但是实际实现代码却是按字节计算,refin=false refout=false 时 byte 左移异或多项式,refin=true refout=true 时 byte 右移异或多项式的反转值。

    目前仅能勉强理解 refin=false refout=false 的情况,在数据中间插入任意个 0 不影响最后的计算结果,所以每个字节左移补 0 异或多项式不会影响结果。

    现在实在无法理解的是 refin=true refout=true 的情况,

    以下面代码为例:

    	/******************************************************************************
    	 * Name:    CRC-5/ITU           x5+x4+x2+1
    	 * Poly:    0x15
    	 * Init:    0x00
    	 * Refin:   True
    	 * Refout:  True
    	 * Xorout:  0x00
    	 * Note:
    	 *****************************************************************************/
    	public static byte crc5_itu(byte[] data,int offset,int length){
    		byte i;
    		byte crc = 0;                // Initial value
    		length += offset;
    		for(int j=offset;j<length;j++) {
    			crc ^= data[j];                 
    			for (i = 0; i < 8; ++i){
    				if ((crc & 1) == 0)
    					crc = (byte) ((crc&0xff) >> 1);
    				else
    					crc = (byte) (((crc&0xff) >> 1) ^ 0x15);// 0x15 = (reverse 0x15)>>(8-5)
    			}
    		}
    		return (byte) (crc & 0x1f);
    	}
    

    refin=true refout=true 时为什么反转的是多项式且 CRC 右移?并且最后的结果也不用反转?

    这几天看了 n 多文章,代码也敲了 n 多遍,运行的每一步都和手算过程一一对照,也实现了完全按 bit 左移异或的代码(和手算过程完全一致,而非按字节计算的方式),仍然难以理解。

    后面还有查表法的原理也看的不明不白,只理解了异或算法遵循结合律所以中间一部分计算过程可以预先计算存表,数据来的时候可以直接查表简化计算过程。

    8 条回复    2023-03-31 19:41:06 +08:00
    JKeita
        1
    JKeita  
       2023-03-31 09:04:07 +08:00
    算法这种东西,未必要理解,就像物理数学公式只要记住就行。推导很难的。
    IwfWcf
        2
    IwfWcf  
       2023-03-31 09:06:17 +08:00
    [1]: https://blog.csdn.net/pl0020/article/details/82760761 "(原创) CRC 计算流程分析( RefIn ,Init ,RefOut ,XorOut )"
    [2]: https://stackoverflow.com/questions/62009020/how-to-format-a-byte-array-to-a-16bit-crc-check-for-a-modbus-frame "How to format a byte array to a 16bit CRC check for a Modbus frame?"
    [3]: https://www.jianshu.com/p/654891ade9d5 "CRC 算法,从原理到实现 - 简书"
    [4]: https://www.lammertbies.nl/comm/info/crc-calculation "On-line CRC calculation and free library - Lammert Bies"
    [5]: https://www.gigacalculator.com/calculators/crc-calculator.php "CRC Calculator - calculate CRC-32, CRC-16 or CRC-8 hash"
    [6]: https://en.wikipedia.org/wiki/Cyclic_redundancy_check "Cyclic redundancy check - Wikipedia"
    [7]: https://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks "Computation of cyclic redundancy checks - Wikipedia"
    [8]: https://www.rndtool.info/CRC-step-by-step-calculator/ "CRC step-by-step Calculator - RndTool.info"

    您好,这是必应。我可以用中文和您交流。😊

    根据我的搜索结果,CRC (循环冗余校验)是一种基于多项式除法的错误检测算法[^1^][6]。CRC 计算的参数包括多项式、初始值、输入反转、输出反转和异或输出[^2^][2]。

    当输入反转( RefIn )为真时,表示在计算之前,将每个字节内的位顺序进行反转[^3^][3]。当输出反转( RefOut )为真时,表示在计算结束后,将 CRC 寄存器的值作为一个整体进行反转[^3^][3]。

    为什么要进行反转呢?这是因为不同的设备或协议可能对数据的位顺序有不同的约定,所以需要通过反转来保证 CRC 计算的一致性[^4^][1]。

    至于为什么 CRC 右移,这是因为 CRC 计算是模拟二进制除法的过程,而除法中被除数是右移与除数对齐的[^1^][6]。

    最后的结果不用反转是因为输出反转已经完成了这个操作,再次反转就会恢复原来的顺序[^4^][1]。
    cyp0633
        3
    cyp0633  
       2023-03-31 11:20:42 +08:00
    @IwfWcf 删了吧,会 ban 的
    IwfWcf
        4
    IwfWcf  
       2023-03-31 12:55:11 +08:00
    @cyp0633 没法删除……刚知道这个规则,不会再发,请不要举报,谢谢
    zhilincom
        5
    zhilincom  
    OP
       2023-03-31 16:26:37 +08:00
    @JKeita #1 已经彻底放弃理解了。
    zhilincom
        6
    zhilincom  
    OP
       2023-03-31 16:40:18 +08:00
    @IwfWcf #2 new bing 的正确率还是堪忧,之前问过 new bing 具体的计算过程,结果它转换数据为二进制是正确的,给的多项式却是错误的,但是最后计算结果竟然又是正确的,至于每一步的过程值也只是囫囵过去。AI 总能以很自信的口吻说出错误的信息,让人很难判断。
    xiadengmaX1
        7
    xiadengmaX1  
       2023-03-31 17:58:01 +08:00
    zhilincom
        8
    zhilincom  
    OP
       2023-03-31 19:41:06 +08:00
    @xiadengmaX1 #7 这篇我看过,我就是跟着这篇以及其他几篇学的手算 CRC 的过程,它也只讲了按位运算的算法,后面就直接给了个 C 语言按字节计算的代码,中间从按位计算扩展到到按字节计算对算法的改变完全没有讲,所以才让人困扰。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1029 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 19:17 · PVG 03:17 · LAX 11:17 · JFK 14:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.