高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

大位宽情况下的回滚式循环冗余校验算法

罗宇 郭家松

罗宇, 郭家松. 大位宽情况下的回滚式循环冗余校验算法[J]. 电子与信息学报, 2021, 43(4): 1057-1063. doi: 10.11999/JEIT200141
引用本文: 罗宇, 郭家松. 大位宽情况下的回滚式循环冗余校验算法[J]. 电子与信息学报, 2021, 43(4): 1057-1063. doi: 10.11999/JEIT200141
Yu LUO, Jiasong GUO. Rollback Cyclic Redundancy Check Algorithm in High Bit-width[J]. Journal of Electronics & Information Technology, 2021, 43(4): 1057-1063. doi: 10.11999/JEIT200141
Citation: Yu LUO, Jiasong GUO. Rollback Cyclic Redundancy Check Algorithm in High Bit-width[J]. Journal of Electronics & Information Technology, 2021, 43(4): 1057-1063. doi: 10.11999/JEIT200141

大位宽情况下的回滚式循环冗余校验算法

doi: 10.11999/JEIT200141
详细信息
    作者简介:

    罗宇:女,1979年生,工程师,研究方向为数据通信、教育信息化

    郭家松:男,1974年生,助理研究员,研究方向为通信技术、老龄心理及老年工作信息化

    通讯作者:

    罗宇 yluo@bjtu.edu.cn

  • 中图分类号: TN919

Rollback Cyclic Redundancy Check Algorithm in High Bit-width

  • 摘要: 为解决大位宽变长数据包情况下包尾数据的循环冗余校验(CRC)32算法处理存在的臃肿低效问题,将循环冗余校验算法变换为矩阵线性运算,利用逆矩阵反向回滚运算,得到正确的CRC运算结果;并在FPGA上进行了实验验证。结果表明:回滚运算的算法可行,并且实现简单,资源占用少。在512 bit位宽的情况下,回滚算法使得资源占用降低到了传统算法的15%;综合耗时降低到了传统算法的30%,布局/布线的耗时降低到了传统算法的40%。
  • 图  1  报文尾有无效字节

    图  2  传统实现

    图  3  1 bit运算矩阵

    图  4  8 bit运算矩阵

    图  5  8 bit逆运算矩阵

    图  6  硬件实现

    图  7  传统实现方式

    图  8  回滚实现方式

    表  1  实验环境

    项目规格备注
    器件厂家/型号Altera/ 5CEFA7U19C7Cyclone–V系列
    开发软件Quartus II 13.1 (64–bit)V13.1
    开发平台便携PC机
    操作系统Win10
    CPUCore–8250U4核
    主频1.6 GHz
    内存8 GBDDR4
    下载: 导出CSV

    表  2  传统算法与回滚算法对比

    项目传统算法回滚算法
    资源占用(ALM)317934427
    综合耗时(s)750201
    布局布线耗时(s)18872
    下载: 导出CSV
  • 王新梅, 肖国镇. 纠错码: 原理与方法[M]. 西安: 西安电子科技大学出版社, 1991.

    WANG Xinmei and XIAO Guozhen. Error Correcting Code: Principleand Method[M]. Xi’an: Xidian University Publisher, 1991.
    王琼, 罗亚洁, 李思舫. 基于分段循环冗余校验的极化码自适应连续取消列表译码算法[J]. 电子与信息学报, 2019, 41(7): 1572–1578. doi: 10.11999/JEIT180716

    WANG Qiong, LUO Yajie, and LI Sifang. Polar adaptive successive cancellation list decoding based on segmentation cyclic redundancy check[J]. Journal of Electronics &Information Technology, 2019, 41(7): 1572–1578. doi: 10.11999/JEIT180716
    刘璐, 武明亮, 何俊强. 基于循环冗余校验码的差错控制分析与实现[J]. 成都大学学报: 自然科学版, 2011, 30(1): 82–85. doi: 10.3969/j.issn.1004-5422.2011.01.024

    LIU Lu, WU Mingliang, and HE Junqiang. Implementation of error control based on cyclic redundancy check[J]. Journal of Chengdu University:Natural Science Edition, 2011, 30(1): 82–85. doi: 10.3969/j.issn.1004-5422.2011.01.024
    肖艳艳, 何晓雄. 基于FPGA的CRC算法的串行和并行实现[J]. 合肥工业大学学报: 自然科学版, 2016, 39(10): 1362–1366. doi: 10.3969/j.issn.1003-5060.2016.10.013

    XIAO Yanyan and HE Xiaoxiong. Serial and parallel implementation of CRC algorithm based on FPGA[J]. Journal of Hefei University of Technology:Natural Science, 2016, 39(10): 1362–1366. doi: 10.3969/j.issn.1003-5060.2016.10.013
    夏忠海, 任勇峰, 贾兴中, 等. 基于FPGA的CRC查表法设计及优化[J]. 电测与仪表, 2017, 54(3): 54–59, 88. doi: 10.3969/j.issn.1001-1390.2017.03.010

    XIA Zhonghai, REN Yongfeng, JIA Xingzhong, et al. Design and optimization of CRC look-up table method based on the FPGA[J]. Electrical Measurement &Instrumentation, 2017, 54(3): 54–59, 88. doi: 10.3969/j.issn.1001-1390.2017.03.010
    左飞飞, 杜英森, 刘剑霏. 基于递推法的CRC-32校验码并行改进算法[J]. 探测与控制学报, 2019, 41(1): 97–101.

    ZUO Feifei, DU Yingsen, and LIU Jianfei. Improved parallel algorithm for CRC-32 check code based on recursive method[J]. Journal of Detection &Control, 2019, 41(1): 97–101.
    DONG Xiguang and He Yongqiang. CRC algorithm for embedded system based on table lookup method[J]. Microprocessors and Microsystems, 2020, 74: 103049. doi: 10.1016/j.micpro.2020.103049
    DUBROVA E and MANSOURI S S. A BDD-based approach to constructing LFSRs for parallel CRC encoding[C]. 2012 IEEE 42nd International Symposium on Multiple-valued Logic, Victoria, Canada, 2012: 128–133. doi: 10.1109/ISMVL.2012.20.
    徐展琦, 裴昌幸, 董淮南. 一种通用多通道并行CRC计算及其实现[J]. 南京邮电大学学报: 自然科学版, 2008, 28(2): 53–57.

    XU Zhanqi, PEI Changxing, and Dong Huainan. Generalized CRC computation algorithm with multiple channels and its implementation[J]. Journal of Nanjing University of Posts and Telecommunications:Natural Science, 2008, 28(2): 53–57.
    QAQOS N N. Optimized FPGA implementation of the CRC using parallel pipelining architecture[C]. 2019 International Conference on Advanced Science and Engineering, Zakho - Duhok, Iraq, 2019: 46–51. doi: 10.1109/ICOASE.2019.8723800.
    WU Chuxiong and SHI Haifeng. Design and implementation of parallel CRC algorithm for fibre channel on FPGA[J]. The Journal of Engineering, 2019(21): 7827–7830. doi: 10.1049/joe.2019.0727
    朱正鹏, 朱旭锋, 李宾, 等. 一种位宽可变的CRC校验算法及硬件实现[J]. 航天控制, 2019, 37(2): 42–48.

    ZHU Zhengpeng, ZHU Xufeng, LI Bin, et al. Data width variable CRC verification algorithm and hardware implementation[J]. Aerospace Control, 2019, 37(2): 42–48.
    张友亮, 刘志军, 马成海, 等. 万兆以太网MAC层控制器的FPGA设计与实现[J]. 计算机工程与应用, 2012, 48(6): 77–79. doi: 10.3778/j.issn.1002-8331.2012.06.023

    ZHANG Youliang, LIU Zhijun, MA Chenghai, et al. Design and implementation of 10-Gigabit Ethernet MAC controller based on FPGA[J]. Computer Engineering and Applications, 2012, 48(6): 77–79. doi: 10.3778/j.issn.1002-8331.2012.06.023
    孔德伟, 袁国顺, 刘小强. 基于FPGA的万兆以太网链路的设计与实现[J]. 微电子学与计算机, 2019, 36(12): 21–25. doi: 10.19304/j.cnki.issn1000-7180.2019.12.005

    KONG Dewei, YUAN Guoshun, and LIU Xiaoqiang. The design and implementation of 10 Gigabit Ethernet link based on FPGA[J]. Microelectronics &Computer, 2019, 36(12): 21–25. doi: 10.19304/j.cnki.issn1000-7180.2019.12.005
    LI Bin, HUANG Zhiping, SHAO Jingsu, et al. Implementation of CRC in 10-Gigabit Ethernet Based on FPGA[J]. Applied Mechanics and Materials, 2014, 599–601: 1548–1552. doi: 10.4028/www.scientific.net/AMM.599-601.1548
    袁征, 冶晓隆, 郭超. 基于FPGA的10G以太网并行CRC设计[J]. 计算机工程与设计, 2014, 35(5): 1510–1515. doi: 10.3969/j.issn.1000-7024.2014.05.003

    YUAN Zheng, YE Xiaolong, and GUO Chao. Implementation of parallel CRC for 10 gigabit Ethernet based on FPGA[J]. Computer Engineering and Design, 2014, 35(5): 1510–1515. doi: 10.3969/j.issn.1000-7024.2014.05.003
    陈容, 陈岚, HAIDER W A. 基于公式递推法的可变计算位宽的循环冗余校验设计与实现[J]. 电子与信息学报, 2020, 42(5): 1261–1267. doi: 10.11999/JEIT190503

    CHEN Rong, CHEN Lan, and HAIDER W A. Design and implementation of cyclic redundancy check with variable computing width based on formula recursive algorithm[J]. Journal of Electronics &Information Technology, 2020, 42(5): 1261–1267. doi: 10.11999/JEIT190503
  • 加载中
图(8) / 表(2)
计量
  • 文章访问数:  2236
  • HTML全文浏览量:  925
  • PDF下载量:  71
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-03-03
  • 修回日期:  2020-06-13
  • 网络出版日期:  2020-07-16
  • 刊出日期:  2021-04-20

目录

    /

    返回文章
    返回