Efficient Reconfigurable Vandermonde Matrix Inverter for Erasure-Correcting Generalized Integrated Interleaved Decoding

被引:0
作者
Tang, Yok Jye [1 ]
Zhang, Xinmiao [1 ]
机构
[1] Ohio State Univ, Dept Elect & Comp Engn, Columbus, OH 43210 USA
来源
2022 IEEE WORKSHOP ON SIGNAL PROCESSING SYSTEMS (SIPS) | 2022年
基金
美国国家科学基金会;
关键词
Erasure-correcting decoding; generalized integrated interleaved codes; Reed-Solomon codes; Vandermonde matrix inversion; REED-SOLOMON CODES;
D O I
10.1109/SIPS55645.2022.9919241
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Generalized integrated interleaved (GII) codes constructed using Reed-Solomon (RS) codes enable local erasure correction with low complexity and are essential to shorten the failure recovery latency in hyper-scale distributed storage. Erasure corrections for storage systems are usually done by multiplying the inverse of a Vandermonde matrix to the syndrome vector. Previous Vandermonde matrix inversion architectures suffer from long latency. Besides, the GII decoding rounds have increasing erasure-correcting capability. Using a Vandermonde inverter dedicated for worst-case erasure correction leads to low hardware efficiency. This paper first proposes a low-latency Vandermonde matrix inverter architecture. By exploiting the regularity of our proposed architecture, an efficient re-configurable inverter supporting matrices of variable sizes is also developed to increase the efficiency of GII-RS erasure-correcting decoding. For 8 x 8 matrix inversion over GF(2(8)), our proposed architecture reduces the latency by 77% with similar complexity compared to the previous design. Our reconfigurable inverter for an example GII code achieves 64% and 32% reductions on latency and area, respectively, compared to the best alternative design.
引用
收藏
页码:168 / 173
页数:6
相关论文
共 16 条
[1]   A 124-Gb/s Decoder for Generalized Integrated Interleaved Codes [J].
Li, Wenjie ;
Lin, Jun ;
Wang, Zhongfeng .
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS, 2019, 66 (08) :3174-3187
[2]   An Encoding Algorithm of Triply Extended Reed-Solomon Codes With Asymptotically Optimal Complexities [J].
Lin, Sian-Jheng .
IEEE TRANSACTIONS ON COMMUNICATIONS, 2018, 66 (08) :3235-3244
[3]   FFT Algorithm for Binary Extension Finite Fields and Its Application to Reed-Solomon Codes [J].
Lin, Sian-Jheng ;
Al-Naffouri, Tareq Y. ;
Han, Yunghsiang S. .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2016, 62 (10) :5343-5358
[4]   PIPELINE INTERLEAVING AND PARALLELISM IN RECURSIVE DIGITAL-FILTERS .1. PIPELINING USING SCATTERED LOOK-AHEAD AND DECOMPOSITION [J].
PARHI, KK ;
MESSERSCHMITT, DG .
IEEE TRANSACTIONS ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 1989, 37 (07) :1099-1117
[5]  
Plank J., 2014, UTEECS14721
[6]   A novel method for combining algebraic decoding and iterative processing [J].
Tang, Xiangyu ;
Koetter, Ralf .
2006 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, VOLS 1-6, PROCEEDINGS, 2006, :474-+
[7]   Fast En/Decoding of Reed-Solomon Codes for Failure Recovery [J].
Tang, Yok Jye ;
Zhang, Xinmiao .
IEEE TRANSACTIONS ON COMPUTERS, 2022, 71 (03) :724-735
[8]   Low-Complexity Implementation of RAID Based on Reed-Solomon Codes [J].
Trifonov, P. .
ACM TRANSACTIONS ON STORAGE, 2015, 11 (01)
[9]   Generalized Integrated Interleaved Codes [J].
Wu, Yingquan .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2017, 63 (02) :1102-1119
[10]   Fast Nested Key Equation Solvers for Generalized Integrated Interleaved Decoder [J].
Xie, Zhenshan ;
Zhang, Xinmiao .
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS, 2021, 68 (01) :483-495