The main computational steps in algebraic soft-decoding, as well as Sudan-type list-decoding, of Reed–Solomon codes are bivariate polynomial interpolation and factorization. We introduce a computational technique, based upon re-encoding and coordinate transformation, that significantly reduces the complexity of the bivariate interpolation procedure. This re-encoding and coordinate transformation converts the original interpolation problem into another reduced interpolation problem, which is orders of magnitude smaller than the original one. A formal proof is presented to show that the two interpolation problems are indeed equivalent. An efficient factorization procedure that applies directly to the reduced interpolation problem is also given.

Algebraic soft-decision decoding is a recent break-through in decoding of Reed-Solomon codes and significant decoding gain can be achieved over conventional hard-decision decoding. Bivariate polynomial factorization is an important step of the new decoding algorithm and contributes to a significant portion of the overall decoding latency. In this paper, a novel architecture based on direct root computation is proposed to greatly reduce the factorization latency. Direct root computation is feasible because in most practical applications of algebraic soft-decision decoding of RS codes, sufficient decoding gain can be achieved with a relatively low interpolation cost, which results in bivariate polynomial of small Y-degree. Compared with existing works, not only does our new architecture have a significantly smaller worst-case decoding latency, but it is also more area efficient.

This paper presents an FPGA implementation of a high-speed interpolation processor for algebraic soft-decision decoding of Reed-Solomon codes. In the design, pipelining and parallel processing techniques are exploited to increase the decoding throughput. In addition, different parts of the interpolation processor are properly scheduled to achieve maximum overlap in processing time for the computations occurring at adjacent iterations. Synthesis results show that the FPGA implementation of the interpolation architecture can achieve a throughput of 149Mbps, which is multiple times higher than conventional design.

Algebraic soft-decision decoding (Koetter and Vardy, 2003) is a recent breakthrough in decoding of Reed-Solomon codes and it achieves significant decoding gain over conventional hard-decision decoding. In the bivariate polynomial factorization step of the new decoding algorithm, solving polynomial equations is required and it may contribute to a significant portion of the overall decoding latency. This paper presents a low-latency direct root computation architecture, which should lead to a factorization architecture that is of lower latency and more area efficient

Recently, Lee and O'Sullivan proposed a new interpolation algorithm for algebraic soft-decision decoding of Reed- Solomon codes. In some cases, the Lee-O'Sullivan algorithm turns out to be substantially more efficient than alternative interpolation approaches, such as Koetter's algorithm. Herein, we combine the re-encoding coordinate transformation, originally developed in the context of Koetter's algorithm, with the recent interpolation technique of Lee and O'Sullivan. To this end, we develop a new basis construction algorithm, which takes into account the additional constraints imposed by the reduced interpolation problem that results upon the re-encoding transformation. This reduces the computational and storage complexity of the Lee-O'Sullivan algorithm by orders of magnitude, and makes it directly comparable to Koetter's algorithm in situations of practical importance.

Bivariate polynomial factorization is an important stage of algebraic soft-decision decoding of Reed-Solomon (RS) codes and contributes to a significant portion of the overall decoding latency. With the exhaustive search-based root computation method, factorization latency is dominated by the root computation step, especially for RS codes defined over very large finite fields. The root-order prediction method proposed by Zhang and Parhi only improves average latency, but does not have any effect on the worst-case latency of the factorization procedure. Thus, neither approach is well-suited for delay-sensitive applications. In this paper, a novel architecture based on direct root computation is proposed to greatly reduce the factorization latency. Direct root computation is feasible because in most practical applications of algebraic soft-decision decoding of RS codes, enough decoding gain can be achieved with a relatively low interpolation cost, which results in a bivariate polynomial with low Y-degree. Compared with existing works, not only does the new architecture have a significantly smaller worst-case decoding latency, but it is also more area efficient since the corresponding hardware for routing polynomial coefficients is eliminated.

The most computationally demanding step in soft-decision decoding of RS codes is bivariate polynomial interpolation. The reencoding and coordinate transformation based technique can significantly reduce the computation complexity of the original interpolation problem, thus making the algebraic soft-decision decoder practically feasible. In this paper, an implementation of the reencoding and coordinate transformation procedure is presented. The novelties of our design include a fast algorithm to determine the reencoding points, an area efficient erasure-only RS decoding architecture, and an overlapped scheduling of the various procedures required for the reencoding process to reduce the overall latency. The synthesis result shows that the proposed design is sufficiently fast for any existing or developing interpolation architecture.

Algebraic soft-decision decoding of Reed-Solomon (RS) codes delivers promising coding gains over conventional hard-decision decoding. The most computationally demanding step in the soft-decision decoding is bivariate polynomial interpolation. In this paper, we present a very efficient high speed interpolation architecture based on hybrid data representation. It is shown that the proposed architecture is inherently scalable and can be extensively pipelined to achieve very high clock speed. By further incorporating the maximum overlapping for computations at adjacent iterations, the proposed architecture demonstrates significant advantages over conventional designs. It is estimated that over 1 Gbps data rate can be achieved using the presented work with moderate complexity.

Algebraic soft-decision decoding of Reed-Solomon (RS) codes delivers promising coding gains over conventional hard-decision decoding. The most computationally demanding step in soft-decision decoding of RS codes is bivariate polynomial interpolation. In this paper, we present a hybrid data format-based interpolation architecture that is well suited for high-speed implementation of the soft-decision decoders. It will be shown that this architecture is highly scalable and can be extensively pipelined. It also enables maximum overlap in time for computations at adjacent iterations. It is estimated that the proposed architecture can achieve significantly higher throughput than conventional designs with equivalent or lower hardware complexity

The most computationally demanding step in algebraic soft-decision decoding, as well as Sudan-type list-decoding, of Reed-Solomon codes is bivariate polynomial interpolation. The interpolation problem consists of computing a polynomial Q(X,Y) that passes through a given set of points P with prescribed multiplicities M. We propose a new divide-and-conquer method that can potentially reduce the complexity of interpolation. Specifically, we split the interpolation problem {P,M} into two problems {P1,M1} and {P2,M2}, and then show that the intersection of the corresponding polynomial ideals I(P1,M1)capI(P2,M2) is equal to their product. Our divide-and-conquer approach differs from the one suggested by Feng-Giraud [G.L.Feng, (2002)] in that the interpolation subproblems {P2,M2} and {P2,M2} are solved independently and only afterwards their solutions are merged. This makes it possible to solve these problems in parallel