New Scalable Decoder Architectures for Reed–Solomon Codes
New Scalable Decoder Architectures for Reed–Solomon Codes
复制标题
DOI：
10.1109/tcomm.2015.2445759
复制
发表时间：
2015-06
影响因子：
8.3
通讯作者：
Yingquan Wu
中科院分区：
文献类型：
--
作者：
Yingquan Wu
本文设计了一种新的RS码可扩展译码器结构，包括纯错译码、错擦除译码和单扩展RS码的可扩展译码三个部分。新的错误唯一的解码器设计通过无逆Berlekamp-Massey算法（IBMA）的算法变换。首先利用IBMA产生的误差定位多项式Λ（x）和辅助多项式B（x），将Horiguchi-Koetter公式推广到误差大小的估计，有效地消除了误差估计多项式的计算。接下来，我们设计了一个增强的并行无逆Berlekamp-Massey算法（ePIBMA），有效地利用了广义Horiguchi-Koetter公式。与现有的基于IBMA或欧几里德算法的常规结构的3 t或更多单元相比，衍生的ePIBMA结构仅需要2 t + 1（t表示纠错能力）个收缩单元。此外，它可以字面上作为一个线性反馈移位寄存器编码器。通过对无求逆Blahut算法（IBA）的算法变换，设计了新的纠错译码器。所提出的分裂并行无逆Blahut算法（SPIBA）仅产生2 t + 1个收缩单元，这与仅错误解码器ePIBMA的数目相同。该任务分为两个单独的步骤，计算的互补errorerasure评估器多项式，其次是计算错误擦除定位器多项式，都利用SPIBA。令人惊讶的是，它具有完全相同的细胞数量和字面上相同的复杂性和吞吐量作为建议的错误只有解码器架构ePIBMA;它采用了33%的硬件减少，并在同一时间实现了两倍以上的速度吞吐量，比串行架构IBA。我们进一步提出了一个统一的并行无逆Blahut算法（UPIBA），通过将错误唯一解码器ePIBMA的关键优点到SPIBA。rderivative UPIBA架构的复杂度和吞吐量与ePIBMA和SPIBA在字面上相同，而在仅错误解码上与ePIBMA以及在错误擦除解码上与SPIBA几乎同样有效地执行。UPIBA还继承了ePIBMA和SPIBA的动态省电功能。实际上，UPIBA对于错误擦除解码的即时实现呈现出高度吸引力。最后，我们证明了所提出的解码器，即，ePIBMA、SPIBA和UPIBA可以神奇地迁移到解码单个扩展RS码，除了在其关键路径上添加额外的多路复用器之外，附加功能可以忽略不计。据作者所知，这是第一次，一个高吞吐量的解码器，单扩展RS码的探索。
In this paper, we devise new scalable decoder architectures for Reed-Solomon (RS) codes, comprising three parts: error-only decoding, error-erasure decoding, and their decoding for singly extended RS codes. New error-only decoders are devised through algorithmic transformations of the inversionless Berlekamp-Massey algorithm (IBMA). We first generalize the Horiguchi-Koetter formula to evaluate error magnitudes using the error locator polynomial Λ(x) and the auxiliary polynomial B(x) produced by IBMA, which effectively eliminates the computation of error evaluator polynomial. We next devise an enhanced parallel inversionless Berlekamp-Massey algorithm (ePIBMA) that effectively takes advantage of the generalized Horiguchi-Koetter formula. The derivative ePIBMA architecture requires only 2t + 1 (t denotes the error correction capability) systolic cells, in contrast with 3t or more cells of the existing regular architectures based on IBMA or the Euclidean algorithm. Moreover, it may literally function as a linear-feedback-shift-register encoder. New error-erasure decoders are devised through algorithmic transformations of the inversionless Blahut algorithm (IBA). The proposed split parallel inversionless Blahut algorithm (SPIBA) yields merely 2t + 1 systolic cells, which is the same number as the error-only decoder ePIBMA. The task is partitioned into two separate steps, computing the complementary errorerasure evaluator polynomial followed by computing error-erasure locator polynomial, both utilizing SPIBA. Surprisingly, it has exactly the same number of cells and literally the same complexity and throughput as the proposed error-only decoder architecture ePIBMA; it employs 33% less hardware and at the same time achieves more than twice faster throughput, than the serial architecture IBA. we further propose a unified parallel inversionless Blahut algorithm (UPIBA) by incorporating the key virtues of the error-only decoder ePIBMA into SPIBA. The complexity and throughput of the rderivative UPIBA architecture are literally the same as ePIBMA and SPIBA, while performing almost equally efficiently as ePIBMA on error-only decoding and as SPIBA on error-erasure decoding. UPIBA also inherits the dynamic power saving feature of ePIBMA and SPIBA. Indeed, UPIBA renders highly attractive for on-the-fly implementation of error-erasure decoding. We finally demonstrate that the proposed decoders, i.e., ePIBMA, SPIBA, and UPIBA, can be magically migrated to decode singly extended RS codes, with negligible add-ons, except that an extra multiplexer is added to their critical paths. To the author's best knowledge, this is the first time that a high-throughput decoder for singly extended RS codes is explored.