维普资讯 http://www.cqvip.com ２００６年第５期 福建 电脑 １４７ 利用数组简单实现ＣＲＣ循环冗余校验码 殷卫霞．季恒 ｆ泰州师范高等专科学较信息科学系江苏泰州２２５３００） 【摘要】：详细分析了ＣＲＣ循环冗余枝验的核心思想，利用Ｃ语言中构造类型——数组采实现ＣＲＣ的缟、解码。 【关键词１：数组、差错检测、循环冗余枝验、生成多项式 在计算机网络技术中链路层的基本服务都是在一个单独的 ＤＲ『ｄ＋卜１１ ＤＲ［０１ 通信链路上将一个数据报从一个节点移到相邻的节点．在传输 过程中我们应能够保证它是可靠的，但在实际应用中。由于信号 ③将Ｄ｝２与Ｇ异或。初始将数组ＤＲ。从高到底取ｒ＋ｌ位 的衰减和电磁噪声的干扰会引起比特差错（当发送方发送一桢 元索与Ｇ数组对应元索进行ＸＯＲ。用一临时数组ｔｅｍｐ。长度为 中的某个比特为１．一个节点的接收方可能会错误的判断该比 ｒ十１。用来存放ＸＯＲ下的结果。判断ｔｅｍｐ的高位有儿个零．便将 特为０）。因此在发送节点的帧上设置检错位，让接收节点执行 ｔｅｍｐ左移几位，然后低位补ＤＲ数组中未进行ＸＯＲ的元索，如 差错检测。以确保传输的可靠。 此重复ＸＯＲ操作．直到ＤＲ［０］并且ｔｅｍｐ的最高位元索为０为 １．ＣＲＣ核心思想 止．ＣＲＣ码即为ｔｅｍｐ数组的后ｒ位元索所表示的０、ｌ代码 现今广泛使朋的一种差错检测技术是基于循环冗余校验码 ｆ０ ＸＯＲ ０＝０ １ＸＯＲ １－－０ ０ Ｘ０Ｒ ｌ＝１ １ＸＯＲ ０－１） 的（Ｃｙｃｌｉｃ Ｒｅｄｕｎｄａｎｃｙ Ｃｈｅｃｋ。ＥＲＥ），ＣＲＣ码又被称为多项式 编码，把要发送的位串看成一个多项式。该多项式的系数是位串 中的值０和１，在位串上的操作认为是对多项式的算术操作。比 如：传输的一帧数据报文Ｄ为：１０１０１１０１（８位）。那么我们可以将 其看作这样的一个多项式：ｘ＋ｘ＋ｘ＋ｘ＋１：发送方和接收方约定有 一共同的＋１位ｒ模式Ｇ（多项式 （ｘ１）——称之为生成多项式， 并且约定Ｇ的最高位为１，发送方采用模２运算求出ＥＲＥ码。 并将数据加上求出的ＥＲＥ传输给接收方。接收方用根据约定好 一匹 的Ｇ去除接收的数据。若所除余数为０。则表示接收正确，若余 ｃＲｃ码 数不为０。那么接收方要求发送方重发。直到接收正确为止。 ２．算法分析 １编码 图２ １）ＣＲＣ计算是在模２下进行的，在二进制算术运算中，乘 ２．解码 法与除法是相同的．只是所需的加或减运算中不要进位或借位。 接收方校验时拿接收的数据Ｒ（ｄ＋ｒ位）与Ｇ相除，这也是 这就等同于按位进行异或（ＸＯＲ）。发送方如何计算出Ｒ呢，在这 二进制的模２操作，不需借位或进位，因此也是ＸＯＲ，它的程序 里我们希望找到一个Ｒ．使得对于ｎ有： 思想与编码中ＸＯＲ相同。若结果能够除尽，即最后算得ｔｅｍｐ中 Ｄ・２ ＸＯＲ Ｒ＝ｎ Ｇ 全为０。则接收无误，若不为０，则接收错误，请求重新发送。 我们对此式进行一个运算：两端都异或Ｒ．这样便可得到：Ｄ｝２ｒ＝ 程序设计（ｖｃ实现。部分代码） ｎ Ｇ ＸＯＲ Ｒ。用Ｃ除Ｄ｝２ｒ。余数是Ｒ。则这样可以将Ｒ计算为： ＯＯＵｎｔ＝￣Ｊｌ计数最多要相异或的次数 Ｉｔ＝（Ｄ｝２ ）％Ｃ ｐ＝ｌｌ； ・————一ｄ 位—————－＋・——一ｒ位——＋ ｆｏｒ（ｉ－－４；ｉ＞＝０；ｉ一＿】 ｔｅｍｐ［ｉｌ＝ＤＲ［ｐ一＿】；，，用ＤＲ［ＩＩＩ—Ｄ ７】初嫡化ｔｅｍｐ敦组 ｗｈｉｌｅ（ｃｏｕｎｔ＜ｆ６） ，，判断有没超出最多要比较的次数，在这里除去最后 一次的丰Ｈ异或操作 Ｉ‘ ｆ０ｒ（ｉａｒ：ｉ＞ －－） Ｄ ２ ＸＯＲ Ｒ（图１） ｌｅｎ ｙＩＵｒ（１ｅｍ￣ｌｉｌ．Ｇｉｌ１）：，，将ｔｅｍｐ与Ｃ对应元素相异或．异或结果 ２）具体步骤（假设输入的是以十进制的数值作为要发送的 存于ｔｅｍｐ中 数据Ｄ．Ｇ生成多项式也是十进制的形式） ｔｅｍＤ最高元素０去除，其他元素左移一位．ｗｈｉｌｅ（！ｔｅｍｐ【４】＆＆（ｆ，＞＝０９），，判断ｔ并且将从ＤＲ中取出一元素Ｄ Ｐ】ｅｍｐ中最高元素是否为＿０．若为 垮 放在 现在我们用数组这样的数据组织形式来实现ＥＲＥ的求解。 ｔｅｍｐ的最低位 在这里将相异或的操作对象存于数组中．相异或实际就是对应 【ｆｏｒ（ｉ－－４：ｉ＞＝ｌ；ｉ￣） 数组的元素进行一定的操作。 ｔｅｒｎｐ［ｉ］－＇ｔｅｍｐ［ｉ—ｌ】； 将数据Ｄ（ｄ位）和生成多项式Ｇ（ｒ＋ｌ位）转换为二进制，分 ｔｅｍｐｉ０］＝ＤＲＩｐ一＿】；ｏｏｕｎｔ＋＋Ｉｌ 】 别采用数组来存放转换后的０、１代码 数据Ｄ（８位） ｉｆ（ｔｅｍｐ［４］） Ｄ『［＝＝ｄ一１工二１ ］［二［工二二［二∞Ｄ『０１ ｛ｆｏｒ（ｉ＝４；ｉ＞＝０；ｉ一）ｔｅｍｐ［ｉ］＝ａｒｒａｙｘｏｒ（ｔｅｍｐ［ｉ］，Ｇ【ｉ ／／最后一次相与结果若ｔｅｍｐ最高位为１，则再进行异或一次，因 生成多项式Ｇ（５位） 为Ｇ的最高需有意义，它须为１，因此再相异或一次，结果才是 Ｇｉ［］ｒｌ ［＝＝］［］［工］ ｑｏ】 真正得到的余数 ｍ—Ｒ＝０； ②将数据Ｄ向左移ｒ位，得到Ｄ ２，即将数组Ｄ［ｄｌｌ￣左移ｒ ｆｏｒ（ｉ＝３；ｉ＞＝０；ｉ－－） 位。长度扩展为ｄ＋ｒ。数组的第一个元素到第ｒ个元素都为０。 ｛Ｒ［ｉ］＝ｔｅｍｐ［ｉ］； ｍＲ＝ｍ＿Ｒ＋Ｒ［ｉｌ＊（ｉｎｔ）（ｐｏｗ（２。ｉ））；ｌ，／将求出的ａ［ｉ】化为十进 —（下转第１３６页） 维普资讯 http://www.cqvip.com １３６ 福建 电脑 ２００６年第５期 事务服务需在高可靠性和额外系统开销间作出选择 ＣＯＲＢＡ支撑服务包括：工厂发现服务、通道发现服务、终结 者服务、多对象操作服务、心跳服务。其中最为重要和复杂的是 多对象操作服务．实现了ＴＭＮ的过滤和范围选择功能。工厂发 现服务用于创建对象 终结者服务删除被管对象 通道发现服务 为事件使用者列出所注册的通道。心跳服务检查通知通道和通 信网状况。 ３－３－３ ＣＯＲＢＡ／ＣＭＩＰ网关 设计ＣＯＲＢＡ／ＣＭＩＰ网关的目标如下：ＣＯＲＢＡ管理能通过 ＣＭＩＰ代理访问ＯＳＩ的管理对象。提供ＩＤＬ到ＣＭＩＳ操作（Ｍ— 基于ＣＯＲＢＡ的ＴＭＮ通用框架为其上的ＣＯＲＢＡ管理应用 提供了统一的锊理接口。而不必考虑ＣＭＩＰ的复杂性 实现了信 息模型转换、管理功能映射、协议转换网关等功能，为分布异构 的电信网络提供了统一高效的管理手段。 ４．总结 ＣＯＲＢＡ的面向对象和分布特性为电信网管提供了新的解 决方案．但ＣＯＲＢＡ适于实现业务管理层和事务管理层的管理 功能，而在网络管理层和网元管理层。传统的基于ＯＳＩ的ＴＭＮ 仍占有较大优势。需要在两者之间进行集成和互操作。本文根据 集成ＣＯＲＢＡ和ＴＭＮ的关键问题和ＪＩＤＭ规范．构建了通用集 ＧＥＴ、Ｍ—ＳＥＴ、Ｍ—ＣＲＥＡＴ、Ｍ—ＤＥＬＥＴＥ、Ｍ—ＡＣ￣ＯＮ）的映射，支持 成框架，讨论了ＧＤＭＯ／ＡＳＮ．１．到ＩＤＬ转换器、ＣＯＲＢＡ服务实现 ＣＭＩＰ的范围选择和过滤功能．从ＣＭＩＰ代理接受事件并发送给 ＴＭＮ功能和ＣＯＲＢＡ／ＣＭＩＰ网关的设计方案。今后。基于ＯＳＩ的 管理应用，提供位置和分布透明性。 ＴＭＮ将向基于ＤＰＥ的ＴＩＮＡ体系结构的ＴＭＮ演进．ＣＯＲＢＭ ＣＯＲＢＡ／ＣＭＩＰ网关主要由Ａｇｅｎｔ代理、ＭＯ工厂、Ｍ０代理、 ＴＭＮ集成框架将过渡到纯ＣＯＲＢＡ方案。 事件报告和应答处理五个功能部分组成．各部分用ＩＤＬ接Ｅｌ实 现。其功能结构见图３。ＭＯ代理与ＣＭＩＰ代理中的对象对应，其 参考文献： ｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｍａｎａｇｅｍｅｎｔ Ｎｅｔｗｏｒｋ Ｐ！ｅｃｏｍｍｅｎｄａｔｉｏｍ． 实例可调用访问ＯＳＩ的ＭＯ实例的方法 Ａｇｅｎｔ代理允许应用访 １．ＩＴＵ—Ｔ ＴｅｌＩＴＵ—Ｔ ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ｓｅｒｉｅｓ Ｍ．３０ｘｘ．１９９３－１９９７ 问Ｍ０代理．ＣＭＩＰ代理的应答也通过Ａｇｅｎｔ代理返回应用。ＭＯ Ｔｈｅ Ｃｏｍｍｏｎ Ｏｂｉｅｃｔ Ｒｅｑｕｅｓｔ Ｂｒｏｋｅｒ．Ａｒｃｈｉ：ｔｅｃｔｕｒｅ ａｎｄ Ｓｐｅｃｉｆｉ— 工厂用于创建Ｍ０代理实例。应答处理用于有多条应答信息的 ２．ｏＭＧ．ｃａｔｉｏｎ．ｒｅｖ．２．２．Ｆｅｂ．１９９８ 情况。 ３．ＪＩＤＭＸｏＪＩＤＭ ｗｏｒｋｉｎｇ ｇｒｏｕｐ．Ｉｎｔｅｒ—Ｄｏｍａｉｎ Ｍａｎａｇｅｍｅｎｔ：Ｓｐｅｃｉｉｆｃａｔｉｏｎ １ＤＬ Ｓｋｅｌｅｔｅ“ ．ｒｅｖ．２．２．Ｍａｒ．１９９７ （ 三 ０户自定义功一 ４．ＩＴＵ—Ｔ Ｒｅｔｏｕｃｈｄａｔｉｏｎ Ｑ．８１６．ＣｏＲＢＡ—Ｂａｓｅｄ ＴＭＮ Ｓｅｒｖｉｃｅｓ． ５．ＩＴＵ—Ｔ Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ Ｘ．７８０．ＴＭＮ Ｇｕｉｄｅｌｉｎｅｓ ｆｏｒ Ｄｅｆｉｎｉｎｇ ＣＯＰ．－ ＯＳＩ管理设施（包括ＪＩ∞管理世施） ＢＡ Ｍａｎａｇｅｄ Ｏｂｊｅｃｔｓ． ６．Ｊｕａ．Ｐａｖｏｎ。Ｕｎｉｖｅｍｉｄａｄ Ｃｏｍｐｌｕｔｅｍｅ Ｍａｄｒｉｄ．Ｂｕｉｌｄｉｎｇ ｔｅｌｅｃｏｍｍｕｎｉｃａ— ｄｏｎｓ Ｍａｎａｇｅｍｅｎｔ Ａｐｐｌｉｃａｔｉｏｍ Ｗｉｔｈ ＣＯＲＢＡ．ＩＥＥＥ ＣＯＭＭＵＮＩＣＡ＿ ＴＩｏＮＳ ＳＵＲＶＥＹＳ 亘 协议转换 ｃＭＩＰ协议栈 亘三二） ７．ｆ美Ｊ Ｍｉｃｈｉ Ｈｅｒｍｉｎｇ Ｓｔｅｖｅ Ｖｉｎｏｓｋｉ著。待垒梧绦科吕志民译。基于 Ｃ＋＋ＣＯＲＢＡ高级蝙程．清华大学出版社 ８．【美】ＯＭＧ蝙著．韦乐平薛君敖孟洛民主持蝙译。ＣＯＲＢＡ系统结 构、原理与规范．电子工业出版社 ＋－＋．－－￣－． 图３ ＣＯＲＢＭＣＭＩＰ网关 。 一—＋，－—＋．－ 。●一－—＋， ＋一＋一十－＋－＋－＋ ＋一十一＋－＋－－Ｉ－－＋ ＋＊＋ 一（上接第１４７页） 制．使得到ＣＲＣ的十进制形式 ｍ＿ｓｅｎｄ＝ｍｄａｔａ８＜＜４＊ｍＲ； ＿—４．思考与小结 数组是一种常用的数据结构。可以看成是有序数据的集合． （在实验中发送数据Ｄ以为８位，生成多项式Ｇ为５位为例） 系统在运行时为其开辟连续的存储空间．这就为访问它中的成 实验数据：发送数据１７３（１０１０１１０１、 员提供了方便和快捷的方法。本文从简单易懂的角度出发利用 生成多项式１８（１００１０） 数组这一对相同性质数据的有效的处理途径．实现循环冗余码 实验结果：ＣＲＣ为：４（０１００）传送数据为：２２７２ 的求解。对于ＣＲＣ的实现实际应用中我们可以用寄存器来实 （１０１０１ １Ｏ１Ｏ１０ｏ） 现，这样速度会更快。而且可以并行实现；也可以采用硬件来实 现。那么在这里主要用数组这样的构造类型帮助我们更深的理 懈它的原理 参考文献： １．】ａｍｅｓ Ｆ．Ｋｕｒｏｓｅ Ｋｅｉｔｈ Ｗ．Ｒｏｓｓ（ＣＯＭＰＵＴＥＲ． ＮＥＴｗｏＲＫＩＮＧ一一Ａ Ｔｏｐ—Ｄｏｗｎ Ａｐｐｒｏａｃｈ Ｆｅａｔｕｒｉｎｇ ｔｈｅ Ｉｎｔｅｍｅｔ｝ Ｈｉｇｈｅｒ Ｅｄｕｃａｔｉｏｎ Ｐｒｅｓｓ。Ｐｅａｒｓｏｎ Ｅｄｕｃａｔｉｏｎ ３８９－－３９１ ２．谭浩强《Ｃ程序设计第二Ｊ跹＞清华大学出版社 ３．杜杏菁、刘春梅《循环冗余枝验算法分析及实现）华北科技学院报 图３ ２００５ 模２过程： ｂ ０ ｌ ．０ ｌ ０ Ｉ ｌ ２１ｌ ｌ Ｌ一 Ｌ＿ —— Ｊ ．！— ｌ ｌ ｉ ｌ ０ Ｌ望Ｊ ｌ １ ！ ！— —一— —．—旦 Ｉ ｏ ｕ Ｏ ＾ ０ Ｊ １ ｌ ０ ０ ｌ ０ Ｉ－—』Ｌ— ——— ——＿三Ｌ ｌ ０ Ｉ ｌ ｏ Ｉ １２ｌ ｏ ｌ 口 ｔ广—蕊蕊露孺露蕊霹 ｑｔ￣ｌＲ．Ｃ Ｗ 图４