热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

深入解析循环冗余校验(CRC)算法的核心机制与应用

循环冗余校验(CRC)算法是一种广泛应用于数据通信和存储系统中的错误检测技术。该算法通过计算数据块的校验值,能够有效检测数据在传输或存储过程中的任何改动或损坏。具体而言,CRC算法利用多项式除法生成一个固定长度的校验码,该码被附加到原始数据之后,接收端通过重新计算并对比校验码来验证数据的完整性。例如,在发送15位的二进制信息时,通过预定义的生成多项式进行计算,确保数据的准确性和可靠性。

Cyclic Redundancy Check循环冗余检验,是基于数据计算一组效验码,用于核对数据传输过程中是否被更改或传输错误。

算法原理

假设数据传输过程中需要发送15位的二进制信息g=101001110100001,这串二进制码可表示为代数多项式g(x) = x^14 + x^12 + x^9 + x^8 + x^7 + x^5 + 1,其中g中第k位的值,对应g(x)中x^k的系数。将g(x)乘以x^m,既将g后加m个0,然后除以m阶多项式h(x),得到的(m-1)阶余项r(x)对应的二进制码r就是CRC编码。

h(x)可以自由选择或者使用国际通行标准,一般按照h(x)的阶数m,将CRC算法称为CRC-m,比如CRC-32、CRC-64等。国际通行标准可以参看http://en.wikipedia.org/wiki/Cyclic_redundancy_check

g(x)和h(x)的除运算,可以通过g和h做xor(异或)运算。比如将11001与10101做xor运算:

      

明白了xor运算法则后,举一个例子使用CRC-8算法求101001110100001的效验码。CRC-8标准的h(x) = x^8 + x^7 + x^6 + x^4 + x^2 + 1,既h是9位的二进制串111010101。 

      

经过迭代运算后,最终得到的r是10001100,这就是CRC效验码。

通过示例,可以发现一些规律,依据这些规律调整算法:

1. 每次迭代,根据gk的首位决定b,b是与gk进行运算的二进制码。若gk的首位是1,则b=h;若gk的首位是0,则b=0,或者跳过此次迭代,上面的例子中就是碰到0后直接跳到后面的非零位。

               


2. 每次迭代,gk的首位将会被移出,所以只需考虑第2位后计算即可。这样就可以舍弃h的首位,将b取h的后m位。比如CRC-8的h是111010101,b只需是11010101。 

      

3.
每次迭代,受到影响的是gk的前m位,所以构建一个m位的寄存器S,此寄存器储存gk的前m位。每次迭代计算前先将S的首位抛弃,将寄存器左移一位,同时将g的后一位加入寄存器。若使用此种方法,计算步骤如下: 

      

※蓝色表示寄存器S的首位,是需要移出的,b根据S的首位选择0或者h。黄色是需要移入寄存器的位。S'是经过位移后的S。

 

查表法

同样是上面的那个例子,将数据按每4位组成1个block,这样g就被分成6个block。

      

下面的表展示了4次迭代计算步骤,灰色背景的位是保存在寄存器中的。 

      

经4次迭代,B1被移出寄存器。被移出的部分,不我们关心的,我们关心的是这4次迭代对B2和B3产生了什么影响。注意表中红色的部分,先作如下定义:

   B23 = 00111010
   b1 = 00000000
   b2 = 01010100
   b3 = 10101010
   b4 = 11010101
   b' = b1 xor b2 xor b3 xor b4

4次迭代对B2和B3来说,实际上就是让它们与b1,b2,b3,b4做了xor计算,既:

   B23 xor b1 xor b2 xor b3 xor b4

可以证明xor运算满足交换律和结合律,于是:

   B23 xor b1 xor b2 xor b3 xor b4 = B23 xor (b1 xor b2 xor b3 xor b4) = B23 xor b'

b1是由B1的第1位决定的,b2是由B1迭代1次后的第2位决定(既是由B1的第1和第2位决定),同理,b3和b4都是由B1决定。通过B1就可以计算出b'。另外,B1由4位组成,其一共2^4有种可能值。于是我们就可以想到一种更快捷的算法,事先将b'所有可能的值,16个值可以看成一个表;这样就可以不必进行那4次迭代,而是用B1查表得到b'值,将B1移出,B3移入,与b'计算,然后是下一次迭代。

      

可看到每次迭代,寄存器中的数据以4位为单位移入和移出,关键是通过寄存器前4位查表获得
,这样的算法可以大大提高运算速度。

上面的方法是半字节查表法,另外还有单字节和双字节查表法,原理都是一样的——事先计算出2^8或2^16个b'的可能值,迭代中使用寄存器前8位或16位查表获得b'。

反向算法

之前讨论的算法可以称为正向CRC算法,意思是将g左边的位看作是高位,右边的位看作低位。G的右边加m0,然后迭代计算是从高位开始,逐步将低位加入到寄存器中。在实际的数据传送过程中,是一边接收数据,一边计算CRC码,正向算法将新接收的数据看作低位。

逆向算法顾名思义就是将左边的数据看作低位,右边的数据看作高位。这样的话需要在g的左边加m0h也要逆向,例如正向CRC-16算法h=0x4c11db8,逆向CRC-16算法h=0xedb88320b的选择0还是h,由寄存器中右边第1位决定,而不是左边第1位。寄存器仍旧是向左位移,就是说迭代变成从低位到高位。


推荐阅读
  • 本文探讨了在Lumen框架中实现自定义表单验证功能的方法与挑战。Lumen的表单验证机制默认返回无状态的JSON格式API响应,这给初学者带来了一定的难度。通过深入研究Validate类,作者分享了如何有效配置和使用自定义验证规则,以提升表单数据的准确性和安全性。 ... [详细]
  • 在高清节目的高比特率传输过程中,使用外接USB硬盘进行时间平移(timeshift)时,出现了性能不足和流数据丢失的问题。通过深入研究,我们发现通过对图像组(GOP)和图像头(I-frame)的精确定位技术进行优化,可以显著提升系统的性能和稳定性。本研究提出了改进的图像组与图像头定位算法,有效减少了数据丢失,提高了流媒体传输的效率和质量。 ... [详细]
  • 在处理大规模并发请求时,传统的多线程或多进程模型往往无法有效解决性能瓶颈问题。尽管它们在处理小规模任务时能提升效率,但在高并发场景下,系统资源的过度消耗和上下文切换的开销会显著降低整体性能。相比之下,Python 的 `asyncio` 模块通过协程提供了一种轻量级且高效的并发解决方案。本文将深入解析 `asyncio` 模块的原理及其在实际应用中的优化技巧,帮助开发者更好地利用协程技术提升程序性能。 ... [详细]
  • 在当前各种算法实现和开源软件包层出不穷的背景下,算法对程序员的重要性是否有所减弱?回顾历史,早期程序员必须熟练掌握算法并频繁自行编写。然而,随着技术的发展,算法逐渐成为一种“商品”,现代开发者更多依赖现成的库和商业算法解决方案。有观点认为,机器学习领域中,许多算法已经被高度封装,不再需要深入理解其背后的数学原理。然而,这种趋势也引发了关于技术深度与广度平衡的讨论,强调了基础理论知识在应对复杂问题时的不可替代性。 ... [详细]
  • 2019年后蚂蚁集团与拼多多面试经验详述与深度剖析
    2019年后蚂蚁集团与拼多多面试经验详述与深度剖析 ... [详细]
  • 如何构建基于Spring MVC框架的Java Web应用项目
    在构建基于Spring MVC框架的Java Web应用项目时,首先应创建一个新的动态Web项目。接着,需将必要的JAR包导入至WebContent/WEB-INF/lib目录下,确保包括Spring核心库及相关依赖。如遇缺失的JAR包,可向社区求助或通过Maven等工具自动下载。正确配置后,即可开始搭建应用结构与功能模块。 ... [详细]
  • JVM参数设置与命令行工具详解
    JVM参数配置与命令行工具的深入解析旨在优化系统性能,通过合理设置JVM参数,确保在高吞吐量的前提下,有效减少垃圾回收(GC)的频率,进而降低系统停顿时间,提升服务的稳定性和响应速度。此外,本文还将详细介绍常用的JVM命令行工具,帮助开发者更好地监控和调优JVM运行状态。 ... [详细]
  • 本文深入探讨了 HTML 中的 `margin` 属性,详细解析了其基本特性和应用场景。文章不仅介绍了 `margin` 的基本概念,还重点讨论了垂直外边距合并现象,并分析了 `margin` 在块级元素与内联元素中的不同表现。通过实例和代码示例,帮助读者全面理解 `margin` 的使用技巧和常见问题。 ... [详细]
  • Java新手求助:如何优雅地向心仪女生索要QQ联系方式(附代码示例与技巧)
    在端午节后的闲暇时光中,我无意间在技术社区里发现了一篇关于如何巧妙地向心仪女生索取QQ联系方式的文章,顿时感到精神焕发。这篇文章详细介绍了源自《啊哈!算法》的方法,不仅图文并茂,还提供了实用的代码示例和技巧,非常适合 Java 新手学习和参考。 ... [详细]
  • 点云技术初探(三):PCL基础知识与学习路径指南本文首先介绍了点云库(PCL)的基本概念,PCL是一个在前人点云研究成果基础上发展而来的大型跨平台开源C++编程库,旨在为点云数据处理提供全面的支持。文章详细阐述了PCL的核心功能及其在三维数据处理、特征提取、分割与配准等方面的应用,并为初学者提供了系统的学习路径和资源推荐,帮助读者快速掌握PCL的使用方法。 ... [详细]
  • 深入解析OSI七层架构与TCP/IP协议体系
    本文详细探讨了OSI七层模型(Open System Interconnection,开放系统互连)及其与TCP/IP协议体系的关系。OSI模型将网络通信过程划分为七个层次,每个层次负责不同的功能,从物理层到应用层逐步实现数据传输和处理。通过对比分析,本文揭示了OSI模型与TCP/IP协议在结构和功能上的异同,为理解现代网络通信提供了全面的视角。 ... [详细]
  • 在 Linux 系统中,`/proc` 目录实现了一种特殊的文件系统,称为 proc 文件系统。与传统的文件系统不同,proc 文件系统主要用于提供内核和进程信息的动态视图,通过文件和目录的形式呈现。这些信息包括系统状态、进程细节以及各种内核参数,为系统管理员和开发者提供了强大的诊断和调试工具。此外,proc 文件系统还支持实时读取和修改某些内核参数,增强了系统的灵活性和可配置性。 ... [详细]
  • 深入解析零拷贝技术(Zerocopy)及其应用优势
    零拷贝技术(Zero-copy)是Netty框架中的一个关键特性,其核心在于减少数据在操作系统内核与用户空间之间的传输次数。通过避免不必要的内存复制操作,零拷贝显著提高了数据传输的效率和性能。本文将深入探讨零拷贝的工作原理及其在实际应用中的优势,包括降低CPU负载、减少内存带宽消耗以及提高系统吞吐量等方面。 ... [详细]
  • 深入解析:RKHunter与AIDE在入侵检测中的应用与优势
    本文深入探讨了RKHunter与AIDE在入侵检测领域的应用及其独特优势。通过对比分析,详细阐述了这两种工具在系统完整性验证、恶意软件检测及日志文件监控等方面的技术特点和实际效果,为安全管理人员提供了有效的防护策略建议。 ... [详细]
  • 内网传送门【题目分析】在本次NOIP模拟赛中,题目主要考察了排列树与组合数学的综合应用,特别是拓扑排序的计算方法。题目的核心在于如何高效地求解树结构中的所有可能拓扑排序方案数,这对参赛者的算法设计和数学基础提出了较高要求。通过深入解析每个节点的排列组合关系,可以逐步构建出完整的解题思路。 ... [详细]
author-avatar
常奕尧
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有