F²MC-8L/16LX/FR FAMILY

Size: px

Start display at page:

Download "F²MC-8L/16LX/FR FAMILY"

汗窦
7 years ago
Views:

1 富士通半导体 ( 上海 ) 有限公司应用笔记 MCU-AN Z-10 F²MC-8FX 家族 8 位微型控制器 MB95200 系列 CRC 的生成与校验应用笔记

2 修改记录修改记录版本日期作者修改记录 Folix 初稿本手册包含 19 页 1. 本文档记载的产品信息及规格说明如有变动, 恕不预先通知如需最新产品信息和 / 或规格说明, 联系富士通销售代表或富士通授权经销商 2. 基于本文档记载信息或示意图的使用引起的对著作权工业产权或第三方的其他权利的侵害, 富士通不承担任何责任 3. 未经富士通明文批准, 不得对本文档的记载内容进行转让拷贝 4. 本文档所介绍的产品并不旨在以下用途 : 需要极高可靠性的设备, 诸如航空航天装置海底中继器核控制系统或维系生命的医用设施 5. 本文档介绍的部分产品可能是外汇及外贸管理法规定的战略物资 ( 或专门技术 ), 出口该产品或其中部分元件前, 应根据该法获得正式批准版权 2009 富士通半导体 ( 上海 ) 有限公司 MCU-AN Z-10- 第 2 页

3 目录目录修改记录... 2 目录概要什么是 CRC 背景介绍 CRC 原理 CRC 算法模数二进制除法生成多项式 CRC 软件实现逐位实现表查找实现 CRC API CRC 表 CRC 检查注意事项更多信息附录 MCU-AN Z-10 - 第 3 页

4 第 1 章概要 1 概要本文档介绍了什么是 CRC 以及如何通过软件实现 CRC MCU-AN Z-10- 第 4 页

5 第 2 章什么是 CRC 2 什么是 CRC 2.1 背景介绍物理损坏的传输或存储介质可能给数据的传输或存储过程带来不必要的数据修改 ( 不包括第三方的修改, 比如恶意攻击者 ) 要检测这些错误, 需要编写一些错误检测或错误校正代码, 用于从数据集计算出一个值并与数据一起传输或存储很多功能可以在一定程度上用于检测错误, 其中一个是循环冗余校验 (CRC) 它并不绝对安全, 不能检测传输数据中的恶意修改, 但是可以检测一些常见的错误, 如 1/2 位或突发性错误, 并且非常有效不同种类的 CRC 有不同大小的计算值最常见的是计算 32 位值的 CRC32, 但是我们有时使用 CRC16 或 CRC8. 大多数时候, 用户希望计算一个给定数据集的 CRC 有时候 CRC 已经给出, 用户希望修改数据, 以便后来计算 CRC 值这些情况包括固件校验和或者计算数据集的 CRC, 后者可以创建一个 ZIP 文件接下来的章节将介绍和分析计算这些修改的方法 2.2 CRC 原理 CRC 算法循环冗余校验提供了一种误差控制编码方式, 通过受控方式在数据中引入若干冗余来保护数据它是一种常用的且非常有效的在各种网络传输中检测传输错误的方式常见的 CRC 多项式可检测以下错误类型所有单位错误所有双位错误所有奇数错误, 假设限制长度足够任何脉冲时间比多项式长度小的错误多数突发性错误式 1 描述了 CRC 编码原理 (1) V(x) 是传输的 n 位长的数据, 它包括原始数据,U(x) 以及代码字 S(x) ( 也称作 CRC- 和 ) S(x) 是额外添加至信息的位, 用于提供冗余, 以便在传输过程中检测错误 S(x) 的长度表示限制长度最常见的 CRC 多项式的限制长度在 8-32 位之间式 3 可用于计算 S(x) (2) (3) MCU-AN Z-10 - 第 5 页

6 第 2 章什么是 CRC 换句话说,S (x) 是数据流相除产生的余数, 并生成多项式 g (x) 因为所有代码字都可以被 g(x) 整除, 对于实际的代码字, 式 (3) 左侧的余数 S(x) 必须为零实际编码程序在这条线路的接收和发送端是相同的图 2-1 说明了 CRC 的编码 / 解码原则图 2-1: 使用 CRC 算法检测错误的原则如图 2-1 所示,NT 对接收的消息进行 CRC 校验如果 S(x) 为零, 传输没有错误另一个解决方法是只计算消息 U(x) 第一部分的 CRC, 然后在传输端用计算的 S(x) 进行余数相加如果结果非零, 接收方将向发送方请求重新传输模数二进制除法如果要最大化有效信息包的最小加重平均距离, 很明显基于二进制加法的简单校验和算法缺少必需的属性在加法中, 改变其中一个消息位并不能对校验和位产生足够的影响但是我们不用单独开发一个更好的校验和研究员很早以前就发现模数二进制除法是为检验和提供必要属性的最简单的数学运算所有的 CRC 公式都是基于模数二进制除法的简单校验和算法虽然不同 CRC 公式有所不同, 其基本数学运算过程是相同的消息位添加 c 零位 ; 添加的消息被除以一个除数一个预先确定的 c+1 位二进制顺序 ( 也称做生成多项式 ) 是除数校验和是除法运算的 c 位余数换句话说, 生成多项式用于除以添加的消息, 弃用商数, 使用余数作为校验和除法最吸引人的地方就是当消息中很小数量的位变化时, 余数快速变化和, 乘, 商都没有这个特性图 2-2 举例说明了模数 2 除法 MCU-AN Z-10- 第 6 页

7 第 2 章什么是 CRC 图 2-2: 模数 2 二进制除法实例在本实例中, 消息包括八位, 而校验和有四位进行除法运算后, 余数为 0111, 1111, 0101, 1011, 1101, 0001, 0010 最后的余数就是该信息的校验和对大多数人来说, 关于 CRC 最难的事就是如何实现仅仅知道所有的 CRC 算法都是简单的除法并没有多大帮助模数 2 二进制除法并不能很好地映射通用处理器的指令集, 基于加法的校验和算法更直接以 m+c 位为分子,c+1 位为分母的二进制除法算法不能解决问题, 因为没有用于保存操作数的 m+c 或 c+1 位寄存器我们应看到它们各自作为校验和的优缺点 MCU-AN Z-10 - 第 7 页

8 第 2 章什么是 CRC 生成多项式为什么预先设定的用于计算 CRC 的 c+1 位除数叫做生成多项式? 许多关于 CRC 的解释实际上都是在回答这个问题这让其作者和读者了解到无数关于多项式算法和 CRC 应用的数学基础的信息但是学术上的东西对于充分理解并使用 CRC 用处不大, 相反会造成混淆这里我们只能说除数有时也称作生成多项式, 不能随意编造很多有名的生成多项式被用作各种国际通信标准的组成部分如果你对多项式算法有所了解, 应该知道在生成检验和方面部分生成多项式要比其他好推荐使用国际上通用的那些生成多项式表 2-1 列出了某些 16 的最常用的生成器多项式 - 和 32 位 CRCs 切记这个除数的宽度更宽比余数总是一因此, 例如, 您会使用 17 位生成器多项式, 每当需要 16 位校验和表 2-1. 国际标准 CRC 多项式名称生成多项式符号 CRC-CCITT G (x)=x16+x12+x5+1 0x1021 CRC-16 G (x)=x16+x15+x2+1 0x8005 CRC-32 G (x)=x32+x26+x23+x22+x16+x12+x10+x8+x7+x5+x4+x2+x+1 0x104C11DB7 和其他类型的校验和一样,CRC 宽度在算法的错误检测功能方面扮演着重要角色忽略由特殊校验和算法检测到的特殊类型的错误, 我们发现校验和的宽度严格制约了可检测错误的百分比 c 位校验和只能有一个 2c 值因为可能的消息数明显要大很多, 两个或多个消息可能有相同的校验和如果在传输中, 其中一个消息被转换为其他消息, 校验和看上去正确, 而接收端将不知道接收的消息是否有误该错误的发生几率与校验和的宽度直接相关, 发生几率达 1/2 c 因此, 任意误差被检测的概率为 1-1/2 c 重复一遍, 检测任意误差的概率随着校验和宽度的增加而增加 16 位校验和可检测 % 的错误, 而 8 位校验和的错误检测率仅为 % 32 位校验和的检测率最高, 达到 %, 这对于 CRC 和基于加法的校验和都一样不一样的是,CRC 的特殊错误检测率为 100% 例如, 加法校验和无法检测两个相反的位反向 ( 一个变为 0, 一个变为 1) 造成的错误, 而 CRC 却不一样通过使用表 1 中所列出的生成多项式来计算校验和, 可无误检测以下错误类型有任何一位错误的消息有任何两位错误的消息 ( 不管离得多远, 在哪一列, 等等 ) 有任何奇数位错误的消息 ( 不管在哪里 ) 有与校验和等宽的突发性错误的信息 MCU-AN Z-10- 第 8 页

9 第 2 章什么是 CRC 可检测错误的第一级由基于加法的校验和或者甚至一个简单的校验位检测但是, 中间两级的错误代表比其他类型校验和更强的检测能力第四级可检测错误看起来与基于加法的校验和检测的错误类似, 但 CRC 将检测任何奇数位的错误因此宽错误群的检测将限于有偶数位错误的消息所有其他类型的错误的检测概率高达 1-1/2 c MCU-AN Z-10 - 第 9 页

10 第 3 章 CRC 软件实现 3 CRC 软件实现 CRC-16 用于描述 CRC 软件 3.1 逐位实现逐位实现 CRC 计算的方法有很多种一旦一个位被转移至左边, 计算将被执行计算次数 = 总位数 16 下图说明了逐位实现 CRC 计算的流程图 3-1: 逐位 CRC 计算 MCU-AN Z-10- 第 10 页

11 第 3 章 CRC 软件实现 UWORD CRC16_Bitbybit(UCHAR *pmsg,int len) 返回参数 : CRC value. : pmsg,data buffer. len,length of data. 描述示例 : Bit by bit calculate CRC. : UWORD Val; UCHAR datbuf[16]; Val=CRC16_Bitbybit(datbuf,16); UWORD CRC16_Bitbybit(UCHAR *pmsg,int len) UCHAR i,j; UWORD CRC16=0; for(j=0;j<len;j++) pmsg++; for(i=0;i<8;i++,*pmsg<<=1) if(crc16 & 0x8000) CRC16<<=1; CRC16 =(*pmsg & 0x80)>>7; CRC16^=0x8005; else CRC16<<=1; CRC16 =0x8005; MCU-AN Z-10 - 第 11 页

12 第 3 章 CRC 软件实现 3.2 表查找实现基于 8 位表查找的 CRC 计算可显著减少 MCU 的占空比, 使其运行速度更快下图显示了表查找 CRC 计算的流程图 3-2: 表查找实现 MCU-AN Z-10- 第 12 页

13 第 3 章 CRC 软件实现 CRC API UWORD CRC16_Table(UCHAR *pmsg,int len) 返回参数 : CRC value. : pmsg,data buffer. len,length of data. 描述示例 : Table Look calculate CRC. : UWORD Val; UCHAR datbuf[16]; Val=CRC16_Table(datbuf,16); UWORD CRC16_Table(UCHAR *pmsg, int len) UCHAR indx; UWORD CRC16=0; while(len--) indx = CRC16 >> 8; CRC16 <<= 8; CRC16 ^= CRCTable[indx ^ *pmsg++]; return CRC16; MCU-AN Z-10 - 第 13 页

14 第 3 章 CRC 软件实现 void CRC16TableGen () 返回参数描述示例 : None. : None. : Generate CRC table. : CRC16TableGen(); void CRC16TableGen() int i,j; UWORD CRC16; for(i=0;i<256;i++) CRC16=i; CRC16<<=8; for(j=0;j<8;j++) if(crc16&0x8000) CRC16<<=1; CRC16^=0x8005; else CRC16<<=1; CRCTable[i]=CRC16; MCU-AN Z-10- 第 14 页

15 第 3 章 CRC 软件实现 CRC 表 UWORD CRCTable[256]= 0x0000,0x8005,0x800F,0x000A,0x801B,0x001E,0x0014,0x8011, 0x8033,0x0036,0x003C,0x8039,0x0028,0x802D,0x8027,0x0022, 0x8063,0x0066,0x006C,0x8069,0x0078,0x807D,0x8077,0x0072, 0x0050,0x8055,0x805F,0x005A,0x804B,0x004E,0x0044,0x8041, 0x80C3,0x00C6,0x00CC,0x80C9,0x00D8,0x80DD,0x80D7,0x00D2, 0x00F0,0x80F5,0x80FF,0x00FA,0x80EB,0x00EE,0x00E4,0x80E1, 0x00A0,0x80A5,0x80AF,0x00AA,0x80BB,0x00BE,0x00B4,0x80B1, 0x8093,0x0096,0x009C,0x8099,0x0088,0x808D,0x8087,0x0082, 0x8183,0x0186,0x018C,0x8189,0x0198,0x819D,0x8197,0x0192, 0x01B0,0x81B5,0x81BF,0x01BA,0x81AB,0x01AE,0x01A4,0x81A1, 0x01E0,0x81E5,0x81EF,0x01EA,0x81FB,0x01FE,0x01F4,0x81F1, 0x81D3,0x01D6,0x01DC,0x81D9,0x01C8,0x81CD,0x81C7,0x01C2, 0x0140,0x8145,0x814F,0x014A,0x815B,0x015E,0x0154,0x8151, 0x8173,0x0176,0x017C,0x8179,0x0168,0x816D,0x8167,0x0162, 0x8123,0x0126,0x012C,0x8129,0x0138,0x813D,0x8137,0x0132, 0x0110,0x8115,0x811F,0x011A,0x810B,0x010E,0x0104,0x8101, 0x8303,0x0306,0x030C,0x8309,0x0318,0x831D,0x8317,0x0312, 0x0330,0x8335,0x833F,0x033A,0x832B,0x032E,0x0324,0x8321, 0x0360,0x8365,0x836F,0x036A,0x837B,0x037E,0x0374,0x8371, 0x8353,0x0356,0x035C,0x8359,0x0348,0x834D,0x8347,0x0342, 0x03C0,0x83C5,0x83CF,0x03CA,0x83DB,0x03DE,0x03D4,0x83D1, 0x83F3,0x03F6,0x03FC,0x83F9,0x03E8,0x83ED,0x83E7,0x03E2, 0x83A3,0x03A6,0x03AC,0x83A9,0x03B8,0x83BD,0x83B7,0x03B2, 0x0390,0x8395,0x839F,0x039A,0x838B,0x038E,0x0384,0x8381, 0x0280,0x8285,0x828F,0x028A,0x829B,0x029E,0x0294,0x8291, 0x82B3,0x02B6,0x02BC,0x82B9,0x02A8,0x82AD,0x82A7,0x02A2, 0x82E3,0x02E6,0x02EC,0x82E9,0x02F8,0x82FD,0x82F7,0x02F2, 0x02D0,0x82D5,0x82DF,0x02DA,0x82CB,0x02CE,0x02C4,0x82C1, 0x8243,0x0246,0x024C,0x8249,0x0258,0x825D,0x8257,0x0252, 0x0270,0x8275,0x827F,0x027A,0x826B,0x026E,0x0264,0x8261, 0x0220,0x8225,0x822F,0x022A,0x823B,0x023E,0x0234,0x8231, ; 0x8213,0x0216,0x021C,0x8219,0x0208,0x820D,0x8207,0x0202 MCU-AN Z-10 - 第 15 页

16 第 3 章 CRC 软件实现 3.3 CRC 检查 CRC 校验和生成的方法几乎相同在 CRC 校验中, 如果接收的数据块的所有数据 ( 包括 CRC 字节 ) 生成的 CRC 校验代码为零, 表明数据全部正确 MCU-AN Z-10- 第 16 页

17 第 4 章注意事项 4 注意事项在应用中, 用户可以定义不同的 CRC 生成多项式来实现 CRC-8 CRC-16 或者 CRC-32 MCU-AN Z-10 - 第 17 页

18 第 5 章更多信息 5 更多信息关于富士通半导体更多的产品信息, 请访问以下网站 : 英文版本地址 : 中文版本地址 : MCU-AN Z-10- 第 18 页

19 第 6 章附录 6 附录表 2-1. 国际标准 CRC 多项式... 8 图 2-1: 使用 CRC 算法检测错误的原则... 6 图 2-2: 模数 2 二进制除法实例... 7 图 3-1: 逐位 CRC 计算图 3-2: 表查找实现 MCU-AN Z-10 - 第 19 页

F²MC-8L/16LX/FR FAMILY

F²MC-8L/16LX/FR FAMILY 富士通半导体 ( 上海 ) 有限公司应用笔记 MCU-AN-500017-Z-12 F²MC-8FX 家族 8 位微型控制器 MB95200 系列如何在目标板上编程应用笔记修改记录修改记录版本日期作者修改记录 1.0. 2009-2-10 Benjamin. Yang 初稿 1.1. 2009-2-11 Benjamin. Yang 修改 1.2 2010-1-11 Ivan. Xiao