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

罗宇; 郭家松

doi:10.11999/JEIT200141

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

doi: 10.11999/JEIT200141

罗宇^1, ,,
郭家松²

1.
北京交通大学经济管理学院　北京　100044
2.
北京交通大学离退休干部处　北京　100044

详细信息

作者简介:
罗宇：女，1979年生，工程师，研究方向为数据通信、教育信息化

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

通讯作者:
罗宇　yluo@bjtu.edu.cn

中图分类号: TN919
计量
- 文章访问数: 2096
- HTML全文浏览量: 792
- PDF下载量: 65
- 被引次数: 0
出版历程
- 收稿日期: 2020-03-03
- 修回日期: 2020-06-13
- 网络出版日期: 2020-07-16
- 刊出日期: 2021-04-20

Rollback Cyclic Redundancy Check Algorithm in High Bit-width

Yu LUO^{1
, ,},
Jiasong GUO²

1.
School of Economics and Management; Beijing Jiaotong University, Beijing 100044, China
2.
Department of Retirement, Beijing Jiaotong University, Beijing 100044, China

摘要

摘要: 为解决大位宽变长数据包情况下包尾数据的循环冗余校验(CRC)32算法处理存在的臃肿低效问题，将循环冗余校验算法变换为矩阵线性运算，利用逆矩阵反向回滚运算，得到正确的CRC运算结果；并在FPGA上进行了实验验证。结果表明：回滚运算的算法可行，并且实现简单，资源占用少。在512 bit位宽的情况下，回滚算法使得资源占用降低到了传统算法的15%；综合耗时降低到了传统算法的30%，布局/布线的耗时降低到了传统算法的40%。
- 循环冗余校验 /
- FPGA /
- 矩阵线性运算 /
- 回滚
Abstract: In order to overcome the complicated implementation to process tail data in high bit-width Cyclic Redundancy Check(CRC) calculation for variable length packet, linear matrix computation is used to investigate CRC inverse calculation. And a rollback algorithm is introduced to simplify the regular algorithm. Then the experiment is conducted to implement the rollback algorithm in Altera FPGA device. The results show that rollback algorithm utilizes fewer resource and is more easily to implement. In 512 bit data width variable length CRC calculation implement in FPGA, the resource utilization is decreased to 15% of regular algorithm by applying rollback algorithm. Synthesis time is decreased to 30%, and Place&Route time is deceased to 40%. It is concluded that the new rollback algorithm has great advantage.
- Cyclic Redundancy Check(CRC) /
- FPGA /
- Matrix linear computation /
- Rollback

HTML全文

图 1 报文尾有无效字节

下载: 全尺寸图片幻灯片

图 2 传统实现

下载: 全尺寸图片幻灯片

图 3 1 bit运算矩阵

下载: 全尺寸图片幻灯片

图 4 8 bit运算矩阵

下载: 全尺寸图片幻灯片

图 5 8 bit逆运算矩阵

下载: 全尺寸图片幻灯片

图 6 硬件实现

下载: 全尺寸图片幻灯片

图 7 传统实现方式

下载: 全尺寸图片幻灯片

图 8 回滚实现方式

下载: 全尺寸图片幻灯片

表 1 实验环境

项目	规格	备注
器件厂家/型号	Altera/ 5CEFA7U19C7	Cyclone–V系列
开发软件	Quartus II 13.1 (64–bit)	V13.1
开发平台	便携PC机	–
操作系统	Win10	–
CPU	Core–8250U	4核
主频	1.6 GHz	–
内存	8 GB	DDR4

下载: 导出CSV

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

项目	传统算法	回滚算法
资源占用(ALM)	31793	4427
综合耗时(s)	750	201
布局布线耗时(s)	188	72

下载: 导出CSV

参考文献(17)

王新梅, 肖国镇. 纠错码: 原理与方法[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

施引文献

资源附件(0)

访问统计