单片机CRC快速算法 (1)
19:37:41&&&来源:21ic
CRC（循环冗余码）检验技术广泛应用于测控及通信领域。在很多情况下，CRC计算是靠专用的硬件来实现的，但是对于小型低成本的系统来说，若要在没有这些硬件的支持下实现CRC检验，首先要解决的就是如何通过软件高效快速地完成CRC计算的问题，也就是算法的问题。
这里将提供两种算法，它们稍有不同，一种适用于程序空间大一些的51系列等单片机，另一种适用于程序空间的使用条件十分苛刻的PIC单片机。这些按字节进行计算，仅使用查表和简单的异或运算等操作，所以，计算过程相当简捷，而计算速度却很快。
下面先简述一下CRC原理，然后再以CRC-CCITT标准生成多项式为例对算法进行说明，并给出一个51系列单片机子程序和一个PIC单片机子程序。
2　CRC原理
CRC检验原理实际上就是在一个p位二进制数据序列之后附加一个r位二进制检验码(序列),从而构成一个总长为n＝p＋r位的二进制序列，例如，p位二进制数据序列D＝[dp-1dp-2 ......d1d0]，r位二进制检验码R＝[rr-1 rr-2....r1 r0]，所得到的这个n位二进制序列就是M＝[dp-1dp-2 ......d1d0 rr-1 rr-2....r1 r0]； 附加在数据序列之后的这个检验码与数据序列的内容之间存在着某种特定的关系。如果因干扰等原因使数据序列中的某一位或某些位发生错误，这种特定关系就会被破坏,因此,通过检查这一关系, 就可以实现对数据正确性的检验。
校验码R是通过对数据序列D进行二进制除法取余式运算得到的，它被一个称为生成多项式的（r＋1）位二进制序列G＝[gr gr-1 .... g1 g0]来除，用多项式形式表示为
其中，xrD(x)表示将数据序列D左移r位（即在D的末尾再增加r个0位），Q(x)代表这一除法所得的商，R(x)就是所需的余式。这一运算关系还可以用式（2）来表达
其中，Re[ ]表示对括号内的式子进行取余式运算。 检验码的编码计算如上所述，而检验过程则是对M序列直接进行除法取余式运算，即
（3） 或表示为
（4） 所得到的余式R(x)若为零则表示数据正确，否则认为发生错误。
3 快速算法的基本思路 这里仅以CRC-CCITT标准生成多项式为例进行说明。CRC-CCITT是一个17位生成多项式G＝[1 10 0001]，用多项式形式表示为G(x)＝x16＋x12＋x5＋1，由它产生的检验码R的二进制位数是16位（2字节）。 单片机的操作是以字节形式进行的，所以，算法应以字节为单位进行运算。这里将把用字节构成的二进制序列称为“字节序列”，显然，单片机的数据序列、检验码以及它俩组成的序列M都是字节序列，或者说是“多字节序列”。 实际上，这种算法所要解决的问题就是如何对多字节序列进行除法取余式运算的问题。3.1 多字节序列运算规律 首先设一个由i个字节 m1、m2、......、mi-1、mi 构成的8×i位二进制序列，并用字节形式表示它为Mi ＝[ m1 m2 ...... mi-1 mi ]，然后再截取Mi的前（i-1）个字节构成一个Mi-1序列，Mi-1＝[ m1 m2 ...... mi-1 ]，这两个序列之间的关系可以用多项式表示为Mi(x)＝x 8Mi-1(x)＋mi(x)，其中，mi(x)是字节mi的二进制多项式表示形式，而x8Mi-1(x)表示将Mi-1序列左移一个字节。 对于序列Mi-1来说，
(5) 其中，二字节序列余式Ri-1＝［hi-1 li-1］。 而对于Mi序列来说，可得
(6) 这一结果的前一项为一整数，所以它与余式无关，这样，余式只可能出现在后一项中。因此，对x8Ri-1(x)＋mi(x)取余式运算就等价于对Mi(x)的取余式运算,用式（4）的形式表示为
(7) x8Ri-1(x)+mi(x)代表一个由Ri-1和mi共同组成的三字节序列[ hi-1 li-1 mi]，而且对这个三字节序列的取余式运算就等于对Mi序列的取余式运算，其结果就是Mi序列的余式Ri＝[ hi li ]。同理可得，对于一个Mi+１序列（它比Mi序列多一个字节mi+1）来说，对三字节序列[ hi li mi+1]的运算就等价于对Mi+1序列的运算，其结果就是Mi+1序列的余式Ri+1＝[ hi+1 li+1 ]。 显然，这反映出一种如图1所示的递推运算的规律。可见，每一次递推运算都是对一个三字节序列的计算，所以，如何简单快捷地对三字节序列进行计算是这种算法的又一个关键。
编辑：什么鱼
本文引用地址：
本周热门资源推荐
EEWORLD独家技术小站：
& 时间：8月22日 10:00 - 11:30
& 时间：8月30日 10:00 - 11:30
& 时间：8月24日 14:00 - 15:30
& 时间：9月12日 10:00 - 11:30
张飞电子工程师速成全集
10天掌握PCB AD画板
教你高速PCB项目整体设计
如何设计STM32单片机系统？
物联网操作系统从写到用
讲师：华清远见
讲师：林超文
讲师：郑振宇
讲师：李述铜
移入鼠标可放大二维码
实验结果与性质分析题 - 基于74LS194的m序列发生器设计
来源：网络整理 作者：日 11:17
[导读] 在m序列产生原理的基础上，利用2片74LS194级联及少量门电路，采用手动置数和自启动2种方法设计了2种m序列发生器电路，然后分析比较了2种电路的产生原理．最后分析了实验结果，验证了m序列的均衡性、游程分布特性及移位相加性．电路性能稳定可靠，已作为数字信号源成功应用于通信原理实验中
　　3.实验结果与性质分析
　　3．1实验结果
　　这里只分析方案2的电路，由图5可知，其初始状态为a7＝a5＝a4＝a3＝a2＝a1＝a0＝0，a6＝1．当m序列发生器利用全0状态重新置数实现自启动时，它能生成长度为255的m序列．如下所示：
　　邀an妖＝
　　100&00．
　　由于示波器显示的波形长度有限，不能一次性显示255位m序列波形［5］．图6为255位m序列的部
　　分波形图．第1路波形为8kHz时钟，第2路波形是产生的m序列部分波形，对应于序列中的引号内部分。
　　3．2性质分析
　　3.2.1m序列的均衡性
　　m序列每一周期中1的个数比0的个数多1个．由于p＝2n－1为奇数，因而在每一周期中1的个数为偶数，即（p＋1）/2＝2n－1；而0的个数为奇数，即（p－1）蛐2＝2n－1－1．当p足够大时，在一个周期中1与0出现的次数基本相等．本设计中的8级m序列中p＝255，1的个数为128，0的个数为127，即0与1出现的概率几乎相等．
　　3.2.2m序列的游程分布
　　将一个序列中取值（1或0）相同连在一起的元素合称为一个游程．在一个游程中元素的个数称为游程长度．统计分析产生序列特性．
　　对于游程长度0＜k&6，全部游程如下：长度为1的0游程和1游程分别出现32次；长度为2的0游程和1游程分别出现16次；长度为3的0游程和1游程分别出现8次；长度为4的0游程和1游程分别出现4次；长度为5的0游程和1游程分别出现2次；长度为6的0游程和1游程分别出现1次；长度为7的0游程出现1次；长度为8的1游程出现1次，如表2所示。
　　m序列的一个周期中，游程总数为128．其中长度为1的游程个数占游程总数的1蛐2；长度为2的游程个数占游程总数的1蛐4；长度为3的游程个数占游程总数的1蛐8；&&一般地，长度为k的游程个数占游程总数的2－k＝2k，其中1&k&（n－2），而且，在长度为k的游程中，连1游程与连0游程各占一半，长为（n－1）的游程是连0游程，长为n的游程是连1游程。
　　3.2.3移位相加特性（线性叠加性）
　　m序列和其位移序列模2和后所得序列仍是该m序列的某个位移序列．设mr是周期为p的m序列mp经过r次延迟移位后的序列，那么有mp茌mr＝ms，其中ms为mp某次延迟移位后的序列。
　　本设计产生的序列为mp，
　　0000妖．
　　mp延迟1位后得到序列mr，
　　000妖．
　　mp与mr模2和后所得序列ms，
　　mr＝邀1
　　000妖．
　　由运算结果可以看到，ms为mp延迟25位后的序列．
　　4、结语
　　文中给出的 2 种 m 序列产生电路经实际硬件测试，输出信号波形符 合 m 序 列 的 均 衡 性、游 程 分 布特性、移位相加性等性质．结果表明：采用 74LS194 加上少量外围芯片，可以方便、准确地产生 m 序列．文中给出的设计方法调试方便，电路性能稳定可靠，具有实际应用价值，已作为数字信号源成功应用于通信原理实验箱。
关注电子发烧友微信
有趣有料的资讯及技术干货
下载发烧友APP
打造属于您的人脉电子圈
关注发烧友课堂
锁定最新课程活动及技术直播
声明：电子发烧友网转载作品均尽可能注明出处，该作品所有人的一切权利均不因本站而转移。
作者如不同意转载，既请通知本站予以删除或改正。转载的作品可能在标题或内容上或许有所改动。
74LS194相关文章
74LS194相关下载
m序列相关文章
m序列相关下载
伪随机序列相关文章
伪随机序列相关下载
论坛精华干货
供应链服务
版权所有 (C) 深圳华强聚丰电子科技有限公司
电信与信息服务业务经营许可证：粤B2-豆丁微信公众号
君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口豆丁微信公众号
君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
m序列发生器的设计与实现
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口 上传我的文档
 上传文档
 下载
 收藏
粉丝量：12
本人部分资料来自网络，请注意保护知识产权，请您下载后勿作商用，只可学习交流使用。 本人如有侵犯作者权益，请作者联系本人删除。
 下载此文档
基于m序列的LTI系统脉冲响应测试--毕业论文
下载积分：2000
内容提示：基于m序列的LTI系统脉冲响应测试--毕业论文
文档格式：DOCX|
浏览次数：11|
上传日期： 20:13:59|
文档星级：
全文阅读已结束，如果下载本文需要使用
 2000 积分
下载此文档
该用户还上传了这些文档
基于m序列的LTI系统脉冲响应测试--毕业论文
关注微信公众号