Efficient Architectures for Generalized Integrated Interleaved Decoder

Xinmiao Zhang

doi:10.1109/TCSI.2019.2916698

2019-10-01

PRE

Xinmiao Zhang

Zhenshan Xie *

DOI：10.1109/TCSI.2019.2916698

原文链接

原文求助

摘要

En 中文

Generalized integrated interleaved (GII) codes allow localized decoding of short sub-codewords. They are essential to hyper-speed data storage, communications, and continued scaling of distributed storage. Sub-codewords, which are usually Reed-Solomon (RS) or BCH codewords, are nested to generate codewords of higher correction capabilities. If the decoding of individual sub-codewords fails, the higher-order syndromes from the nested codewords are utilized to correct more errors. GII decoder design faces many challenges. The major ones include: 1) high-speed nested decoding utilizing the higher-order syndromes; 2) efficient updating of higher-order syndromes after sub-codewords are corrected; 3) computation of nested syndromes and matrix inversion for converting them to higher-order sub-codeword syndromes; and 4) efficient architectures capable of addressing the variable correction capabilities of the nested codewords. This paper proposes novel algorithmic reformulations and architectural transformations to address each bottleneck. For an example, GII code that has the same rate and length as eight un-nested (255, 223) RS codes, the proposed GII decoder achieves more than seven orders of magnitude improvement in error-correcting performance with less than 30% area overhead compared to the RS decoder. With a critical path of seven XOR gates, the proposed decoder can easily achieve more than 40 GB/s throughput.

Keyword:

Error-correcting codes

generalized integrated interleaved codes

key equation solver

locally recoverable codes

nested decoding

Reed-Solomon codes

scalable Chien search

syndromes

Vandermonde matrix inversion