CRC16浅析

CRC即循环冗余校验码(Cyclic Redundancy Check),是数据通信领域中最常用的一种查错校验码。奇偶校验虽然简单,但是漏检率太高,而CRC则要低的多,所以大多数都是使用CRC来校验。CRC也称为多项式码。

任何一个由二进制数位串组成的代码,都可以唯一的与一个只含有0和1两个系数的多项式建立一一对应的关系。如:1010111对应的多项式为X^6 + X^4 + X^2 + X + 1。

CRC码是利用事先约定好的多项式G(x)来得到的。k位要发送的信息位可对应于一个(k - 1)次多项式K(x),r位冗余位则对应于一个(r - 1)次多项式R(x)。k位信息位和r位冗余位组成的码字多项式为T(x) = x^r * K(x) + R(x)。因为补上了r位冗余为,所以K(x)要乘以x^r。

由信息位产生冗余位的编码过程,即已知K(x)求R(x)的过程。通过约定好的r次多项式G(x),最高项X^r的系数恒定为1,即r bit为1。然后用X^r * K(x) 去除以G(x),得到的余式就是R(x)。除法是模2除法,即使用异或运算。当被除数逐位除完时,最后得到的比除数少一位的余数,此余数即为冗余位。将其添加在信息位后面。

这里以K(x) = x^6 + x^4 + x^3 + 1为例(信息位即为1011001),设G(x) = x^4 + x^3 + 1(11001),则r = 4,x^4 * K(x) (即低位补r个0:10110010000)。

模2除法求余式R(x)的过程如下:

即冗余位为1010,R(x) = x^3 + x;

 

常见问题:

0,为什么带CRC的码字的余数为0,即校验成功?

1,多项式公式的代码

例如多项式公式:x16 + x12 + x5 + 1的代码是‭0001 0001 0000 0010 0001‬,即0x11021。次方为第几个bit,0次方等于1。

 

2,为什么多项式的最高项可以不写?

例:CRC-16/xmodem的多项式公式为:x16+x12+x5+1。即多项式为0x11021,但一般记为0x1021。多项式公式最高和最低位要求为1。下面以求0x03的crc为例,手动算出crc。

0x03的多项式为 K(x) = x+1;而G(x) = x16+x12+x5+1,用最高项x16*K(x)=x17+x16,用其除(模2除法)以G(x)求余。

 

 0011 0000  0000  0000  0000
     10 0010  0000  0100  001 
     01 0010  0000  0100  0010
       1 0001  0000  0010  0001 

      0 0011  0000  0110  0011

 

得crc为0x3063。由于多项式的最高位的1总是与被除数的最高位1异或得0,所以只要将信息位左移一位,再与去掉最高项的多项式异或即可(crc = (crc << 1) ^poly;)。

 

3,为什么有的要将多项式0x8005反转,写成0xA001?

由于CRC模型有很多,不只体现在多项式的不同,还有输入值,输出值的操作上,对其进行反转等。例如CRC16_CCITT,就要对其输入,输出值进行反转。如果要对其进行反转,势必会加重其运算效率。所以为了提高效率,可以把多项式反转一下。例如:0x8005 -> 0xA001,然后对信息位从最低位开始右移异或即可。

 

 

 

 

#include<stdio.h>
#include<stdbool.h>typedef unsigned short u16;const u16 crc16_table[256] = { 0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440,0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40,0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841,0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40,0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41,0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641,0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040,0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240,0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441,0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41,0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840,0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41,0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40,0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640,0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041,0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240,0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441,0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41,0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840,0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41,0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40,0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640,0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041,0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241,0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440,0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40,0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841,0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40,0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41,0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641,0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040
};unsigned char char_invert(unsigned char ch)
{char i;unsigned char invert = 0;for (i = 0; i < 8; i++) {if (ch & 0x1)invert |= 0x01 << (7-i);ch >>= 1;}return invert;
}u16 short_invert(u16 sh)
{char i;u16 invert = 0;for (i = 0; i < 16; i++) {if (sh & 0x1)invert |= 0x01 << (15-i);sh >>= 1;}return invert;
}u16 crc16(u16 crc, u16 poly, bool input_invert, bool output_invert, u16 output_xor, unsigned char *buf, u16 len)
{unsigned char i;while (len--) {if (input_invert)crc ^= (char_invert((*buf++)) << 8);elsecrc ^= ((*buf++) << 8);for (i = 0; i < 8; i++) {if (crc & 0x8000) crc = (crc << 1) ^poly;elsecrc <<= 1;}}if (output_invert)return short_invert(crc)^output_xor;return crc^output_xor;
}u16 crc16_ibm(unsigned char *buf, u16 len)
{return crc16(0x0, 0x8005, true, true, 0x0,buf, len);
}u16 crc16_modbus(unsigned char *buf, u16 len)
{return crc16(0xffff, 0x8005, true, true, 0x0, buf, len);
}u16 crc16_ccitt(unsigned char *buf, u16 len)
{return crc16(0x0, 0x1021, true, true, 0x0, buf, len);
}u16 crc16_xmodem(unsigned char *buf, u16 len)
{return crc16(0x0, 0x1021, false, false, 0x0, buf, len);
}u16 crc16_x25(unsigned char *buf, u16 len)
{return crc16(0xffff, 0x1021, true, true, 0xffff, buf, len);
}static u16 crc16_byte(u16 crc, const unsigned char data)
{   return (crc >> 8) ^ crc16_table[(crc ^ data) & 0xff];
}u16 crc16_tab(u16 crc, unsigned char const *buffer, size_t len)
{while (len--)crc = crc16_byte(crc, *buffer++);return crc;
}


...

 

 

 

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/350990.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

【Linux】关于Linux中的权限

文章目录 前言Linux权限文件访问者的分类&#xff08;人&#xff09;文件类型和访问权限&#xff08;事物属性&#xff09;文件类型基本权限 目录的权限粘滞位权限的总结 前言 前面我们已经知道。Linux下有两种用户&#xff1a;超级用户&#xff08;root&#xff09;、普通用户…

Linux ALSA音频驱动二:ALSA驱动注册

在系统/dev/snd下可查看注册成功的声卡信息&#xff0c;如下所示。 ubuntuubuntu:~$ ls -l /dev/snd total 0 drwxr-xr-x 2 root root 60 4月 7 09:22 by-path crw-rw---- 1 root audio 116, 2 4月 7 09:22 controlC0 // 通路控制 crw-rw---- 1 root audio 116,…

CRC编码

循环冗余校验&#xff08;Cyclic Redundancy Check&#xff0c; CRC) 原理:先在要发送的帧后面附加一个二进制数,(用来校验的校验码);生成一个新帧发送给接收端 附加的二进制数要求&#xff1a;使所生成的新帧能与发送端和接收端共同选定的某个特定数整除 运算&#xff1a;这里…

CLR简介

CLR简介 什么是CLR CLR英文全称Common Language Runtime&#xff0c;即公共语言运行时。 乍一看到这个概念确实不明白&#xff0c;什么是语言运行时&#xff1f; 简单来说&#xff0c;就是一个程序运行所需要的环境&#xff0c;包括各种资源、各种操作等等。 通常来说&…

CRF概述

主要参考 1.李航统计学习方法 2.一个声音好听的小姐姐的讲解视频https://www.bilibili.com/video/av752902225/ 3. 白板推导系列视频 https://www.bilibili.com/video/BV19t411R7QU?p1 一、背景介绍 1、背景算法介绍 HMM&#xff0c;隐马尔可夫模型&#xff0c;是生成模…

CRC-16

文章目录 A.1 CRC16 算法A.1.1 CRC16 算法参数设置A.1.2 LengthA.1.3 CounterA.1.4 Data IDA.1.5 CRCA.1.6 CRC16 算法示例A.1.7 CRC16 算法推荐(查表法)A.1.8 CRC16 实例(查表法) A.1 CRC16 算法 A.1.1 CRC16 算法参数设置 CRC16 算法中要求了 Counter、Data ID、CRC 等参数…

CRF

随机场&#xff1a;由若干个子集组成的一个整体&#xff0c;而每个子集都按照某个分布随机赋予一个值&#xff0c;这个场就叫随机场。 马尔科夫随机场&#xff1a;随机场中某一位置的赋值仅与其相邻位置的赋值有关&#xff0c;和与其不相邻位置的赋值无关。 CRF是马尔科夫随机…

crc(crc是什么职业)

CRC的特点是什么&#xff1f; 在诸多检错手段中&#xff0c;CRC是最著名的一种&#xff0c;其特点是:检错能力极强&#xff0c;开销小&#xff0c;易于用编码器及检测电路实现 CRC的特点有哪些呢&#xff1f; CRC的全称是循环冗余校验&#xff0c;其特点是:检错能力极强&#x…

CRC16

CRC选择 当数据帧长度在8bits-128bits范围内时&#xff0c;推荐CRC-8(CRC-8能够减少额外比特的开销&#xff0c;且有更好的性能表现) 当数据帧长度在128bits-2048bits范围内时&#xff0c;推荐CRC-12&#xff0c;CRC-16&#xff0c;CRC-CCITT(CRC-12额外比特的开销更小&#x…

linux中ls -l出的crw brw lrw代表什么?

原文链接&#xff1a;https://www.cnblogs.com/victorywr/p/15725170.html 每次使用ls -al 查看文件信息&#xff0c;都只看rw-rw-rw- &#xff08;权限为666&#xff09;&#xff0c;忽略最前面的c/b/l&#xff0c;今天了解一下&#xff1a; linux中c表示字符设备文件&#xf…

一款红队批量脆弱点搜集工具

功能 指纹识别:调用“三米前有香蕉皮“前辈工具&#xff0c;他的工具比finger好用 寻找资产中404&#xff0c;403&#xff0c;以及网页中存在的其他薄弱点&#xff0c;以及需要特定路径访问的资产 后续会把nuclei加进来 目前只有windows可以用 使用 第一次使用脚本请运行p…

【机器学习】正则化详解和过拟合的解决

https://blog.csdn.net/weixin_45434953/article/details/130970273 上一篇文章的例子中&#xff0c;如果使用一个四次多项式去拟合房价函数&#xff0c;会导致过拟合问题 而正则化是解决过拟合的一个方法。右图过拟合是因为其三次方项和四次方项的影响&#xff0c;我们再回顾…

改进YOLOv8 | 主干网络篇 | YOLOv8 更换骨干网络之 GhostNet | 从廉价操作中获取更多特征

论文地址:https://arxiv.org/abs/1911.11907 代码地址:https://github.com/huawei-noah/ghostnet 由于内存和计算资源有限,在嵌入式设备上部署卷积神经网络(CNN)很困难。特征图中的冗余是那些成功的神经网络的重要特征,但在神经架构设计中很少研究。本文提出了一种新的G…

【测试入门】测试用例经典设计方法 —— 因果图法

01、因果图设计测试用例的步骤 1、分析需求 阅读需求文档&#xff0c;如果User Case很复杂&#xff0c;尽量将它分解成若干个简单的部分。这样做的好处是&#xff0c;不必在一次处理过程中考虑所有的原因。没有固定的流程说明究竟分解到何种程度才算简单&#xff0c;需要测试…

妙啊!真实模拟面试 — 面试官究竟会怎么问 数据库索引呢?

什么是索引&#xff1f; 面试官&#xff1a;我看你项目中有做过 SQL 优化&#xff0c;那我们今天就来聊聊索引吧。 &#xff08;索引能问些啥&#xff0c;无非是索引的概念、索引的使用规则、索引的分类、索引的原理。嘻嘻~我早有准备&#xff09; 我&#xff1a;数据库中的…

一道面试题:餐馆模拟

前阵子遇到一个面试题&#xff0c;当时没有做出来&#xff0c;后来断断续续的用了一周的时间做了出来&#xff0c;但感觉也不完全对&#xff0c;先来看看题目&#xff0c;稍后再讨论。 问题 模拟一个餐馆&#xff0c;三个厨师&#xff0c;二个服务员&#xff0c;厨师单独做菜…

AI模拟面试官项目实战 | 项目概述

&#x1f3af;摘要 看完本文&#xff0c;你可能有如下收获&#xff1a; 了解该项目的预览效果、了解技术栈、系统设计以及教程食用指南 ⭐️⭐️该收获仅供参考&#xff0c;真实收获以实物为准&#x1f607;&#x1f607; ☀️系统概述 【AI模拟面试官】是一个模拟线上面试的…

软件测试面试题【2021模拟面试整理版(含答案)】

点击上方蓝色“程序员一凡”&#xff0c;选择“设为星标” 主页点击“领取资料”获取整理好的学习资源 一、问题预测 \1. 让简单介绍下自己&#xff08;每次面试开场&#xff09; \2. 让说下自己会的内容 \3. 看了哪些书籍&#xff08;有问到&#xff09; \4. 了解过哪些技…

Java程序员模拟面试,解析面试困扰和建议

模拟面试&#xff0c;相信大多数程序员都没有经历过&#xff0c;甚至还有从来没听说针对面试的辅导或者模拟面试啥的&#xff0c;所有的面试经验都来源于网上写的一些文章&#xff0c;然后再在面试的时候通过各种碰壁去揣测面试官在想啥。 前言 前几天组织了一次模拟面试直播&…

模拟面试题一

一、选择题 1、python不支持的数据类型有 A、charB、intC、floatD、list 1 参考答案&#xff1a;A 参考答案 2、打印输出结果&#xff1a;x "foo"y 2print(x y)A.foo B.foofoo C.foo2 D.2 E.An exception is thrown 1 D &#xff1a;一个是字符串&#…