基于公式遞推法的可變計(jì)算位寬的循環(huán)冗余校驗(yàn)設(shè)計(jì)與實(shí)現(xiàn)
doi: 10.11999/JEIT190503
-
1.
中國科學(xué)院微電子研究所 北京 100029
-
2.
中國科學(xué)院大學(xué) 北京 100049
-
3.
三維及納米集成電路設(shè)計(jì)自動(dòng)化技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室 北京 100029
Design and Implementation of Cyclic Redundancy Check with Variable Computing Width Based on Formula Recursive Algorithm
-
1.
Institute of Microelectronics, Chinese Academy of Sciences, Beijing 100029, China
-
2.
University of Chinese Academy of Sciences, Beijing 100049, China
-
3.
Beijing Key Laboratory of Three-dimensional and Nanometer Integrated Circuit Design Automation Technology, Beijing 100029, China
-
摘要:
循環(huán)冗余校驗(yàn)(CRC)與信道編碼的級聯(lián)使用,可以有效改善譯碼的收斂特性。在新一代無線通信系統(tǒng),如5G中,碼長和碼率都具有多樣性。為了提高編譯碼分段長度可變的級聯(lián)系統(tǒng)的譯碼效率,該文提出一種可變計(jì)算位寬的CRC并行算法。該算法在現(xiàn)有固定位寬并行算法的基礎(chǔ)上,合并公式遞推法中反饋數(shù)據(jù)與輸入數(shù)據(jù)的并行計(jì)算,實(shí)現(xiàn)了一種高并行度的CRC校驗(yàn)架構(gòu),并且支持可變位寬的CRC計(jì)算。與現(xiàn)有的并行算法相比,合并算法節(jié)省了電路資源的開銷,在位寬固定時(shí),資源節(jié)約效果明顯,同時(shí)在反饋時(shí)延上也有將近50%的優(yōu)化;在位寬可變時(shí),電路資源的使用情況也有相應(yīng)的優(yōu)化。
-
關(guān)鍵詞:
- 循環(huán)冗余校驗(yàn) /
- 并行算法 /
- 公式遞推法
Abstract:Cyclic Redundancy Check (CRC) is used in cascade with channel coding to improve the convergence of the decoding. In the new generation of wireless communication systems, such as 5G, both code length and code rate are diverse. To improve the decoding efficiency of cascaded systems, a CRC parallel algorithm with variable computing width is proposed in this paper. Based on the existing fixed bit-width parallel algorithm, this algorithm combines the parallel calculation of feedback data and input data in the formula recursive method, realizing a highly parallel CRC check architecture with variable bit-width CRC calculation. Compared with the existing parallel algorithms, the merged algorithm saves the overhead of circuit resources. When the bit-width is fixed, the resource saving effect is obvious, and at the same time, the feedback delay is also optimized by nearly 50%. When the bit-width is variable, the use of resources is also optimized accordingly.
-
表 1 硬件資源開銷
項(xiàng)目 值 頂層實(shí)體名 crc_24 芯片 EP3C5E144C7(Cyclone III) 邏輯器件數(shù) 434/5136(8%) 寄存器數(shù) 26 管腳數(shù) 68/95(72%) 下載: 導(dǎo)出CSV
表 2 仿真測試結(jié)果
總長度
(bit)Num Matlab結(jié)果 仿真結(jié)果 數(shù)據(jù)1 60 7, 24, 29 001111010110111111110110 24’h3d6ff6 數(shù)據(jù)2 65 23, 32, 10 001110000010011011010001 24’h3826d1 數(shù)據(jù)3 70 24, 15, 31 011111100000011111011011 24’h7e07db 下載: 導(dǎo)出CSV
表 3 選用的生成多項(xiàng)式
CRC 生成多項(xiàng)式 CRC-12 ${x^{12}} + {x^{11}} + {x^3} + {x^2} + x + 1$ CRC-16 ${x^{16}} + {x^{15}} + {x^2} + 1$ CRC-32 $\begin{array}{l}{x^{32}} + {x^{26}} + {x^{23}} + {x^{22}} + {x^{16}} + {x^{12}} + {x^{11}} + \\{x^{10}} + {x^8} + {x^7} + {x^5} + {x^4} + {x^2} + x + 1\end{array}$ 下載: 導(dǎo)出CSV
表 4 電路資源和關(guān)鍵路徑長度比較
CRC式子(M=r) 算法 總計(jì) 1 異或 關(guān)鍵路徑 CRC-12(12) 文獻(xiàn)[7] 136 112 9 文獻(xiàn)[8] 120 66 8 文獻(xiàn)[10] – 103 8 文獻(xiàn)[9] 77 53 8 固定 52 43 5 可變 64 78 9 CRC-16(16) 文獻(xiàn)[7] 218 186 10 文獻(xiàn)[8] 188 98 10 文獻(xiàn)[10] – 94 10 文獻(xiàn)[9] 100 60 9 固定 72 54 5 可變 88 101 9 CRC-32(32) 文獻(xiàn)[7] 1031 967 12 文獻(xiàn)[8] 928 518 12 文獻(xiàn)[10] – 675 10 文獻(xiàn)[9] 888 461 12 固定 452 313 6 可變 484 408 11 下載: 導(dǎo)出CSV
-
LI Bin, HUANG Zhiping, SU Shaojing, 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 WANG Bingrui, CHEN Pingping, FANG Yi, et al. The design of vertical RS-CRC and LDPC code for ship-based satellite communications on-the-move[J]. IEEE Access, 2019, 7: 44977–44986. doi: 10.1109/ACCESS.2019.2895746 CAMPOBELLO G, PATANE G, and RUSSO M. Parallel CRC realization[J]. IEEE Transactions on Computers, 2003, 52(10): 1312–1319. doi: 10.1109/TC.2003.1234528 MUTHIAH D and RAJ A A B. Implementation of high-speed LFSR design with parallel architectures[C]. 2012 International Conference on Computing, Communication and Applications, Dindigul, India, 2012: 1–6. HUO Yuanhong, LI Xiaoyang, WANG Wei, et al. High performance table-based architecture for parallel CRC calculation[C]. The 21st IEEE International Workshop on Local and Metropolitan Area Networks, Beijing, 2015: 1–6. BAJARANGBALI and ANAND P A. Design of high speed CRC algorithm for ethernet on FPGA using reduced lookup table algorithm[C]. 2016 IEEE Annual India Conference, Bangalore, India, 2016: 1–6. DERBY J H. High-speed CRC computation using state-space transformations[C]. GLOBECOM’01. IEEE Global Telecommunications Conference, San Antonio, USA, 2001: 166–170. KENNEDY C and REYHANI-MASOLEH A. High-speed CRC computations using improved state-space transformations[C]. 2009 IEEE International Conference on Electro/Information Technology, Windsor, Canada, 2009: 9–14. HU Guanghui, SHA Jin, and WANG Zhongfeng. High-speed parallel LFSR architectures based on improved state-space transformations[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2017, 25(3): 1159–1163. doi: 10.1109/TVLSI.2016.2608921 JUNG J, YOO H, LEE Y, et al. Efficient parallel architecture for linear feedback shift registers[J]. IEEE Transactions on Circuits and Systems Ⅱ: Express Briefs, 2015, 62(11): 1068–1072. doi: 10.1109/tcsii.2015.2456294 CHENG Chao and PARHI K K. High-speed parallel CRC implementation based on unfolding, pipelining, and retiming[J]. IEEE Transactions on Circuits and Systems Ⅱ: Express Briefs, 2006, 53(10): 1017–1021. doi: 10.1109/TCSⅡ.2006.882213 AYINALA M and PARHI K K. High-speed parallel architectures for linear feedback shift registers[J]. IEEE Transactions on Signal Processing, 2011, 59(9): 4459–4469. doi: 10.1109/TSP.2011.2159495 李偉華, 焦秉立. 一種基于分段CRC的LDPC譯碼的改進(jìn)算法[J]. 電子與信息學(xué)報(bào), 2008, 30(5): 1167–1170. doi: 10.3724/SP.J.1146.2006.01763LI Weihua and JIAO Bingli. Improved method for LDPC decoding algorithm aided by segmented cyclic redundancy checks[J]. Journal of Electronics &Information Technology, 2008, 30(5): 1167–1170. doi: 10.3724/SP.J.1146.2006.01763 TUSHA A, DO?AN S, and ARSLAN H. IQI mitigation for narrowband IoT systems with OFDM-IM[J]. IEEE Access, 2018, 6: 44626–44634. doi: 10.1109/ACCESS.2018.2864892 VAN WONTERGHEM J, ALLOUM A, BOUTROS J J, et al. On short-length error-correcting codes for 5G-NR[J]. Ad Hoc Networks, 2018, 79: 53–62. doi: 10.1016/j.adhoc.2018.06.005 RICHARDSON T and KUDEKAR S. Design of low-density parity check codes for 5G new radio[J]. IEEE Communications Magazine, 2018, 56(3): 28–34. doi: 10.1109/MCOM.2018.1700839 王瓊, 羅亞潔, 李思舫. 基于分段循環(huán)冗余校驗(yàn)的極化碼自適應(yīng)連續(xù)取消列表譯碼算法[J]. 電子與信息學(xué)報(bào), 2019, 41(7): 1572–1578. doi: 10.11999/JEIT180716WANG 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 -