UC San Diego

Algebraic soft-decision decoding of Reed-Solomon codes delivers promising gain over conventional hard-decision decoding. The major computational steps in algebraic soft- decoding (as well as Sudan-type list-decoding) are bivariate polynomial interpolation and factorization. In this thesis, we present techniques from both algorithmic and VLSI architectural level that greatly reduce the implementation complexity of a soft-decision Reed-Solomon decoder. A divide-and-conquer approach to perform the bivariate polynomial interpolation procedure is discussed in Chapter 3. This method can potentially reduce the interpolation complexity of algebraic soft-decision decoding of Reed-Solomon code. In Chapter 4, a computational technique, based on re-encoding coordinate transformation, is derived that can significantly reduces complexity of bivariate interpolation procedure. With this technique, the original interpolation problem is transformed into another reduced interpolation problem, which could be orders of magnitude smaller than the original one. A rigorous proof is presented to show that the two interpolation problems are equivalent. In addition, an efficient factorization procedure that applies directly to the reduced interpolation problem is given. We apply the re-encoding coordinate transformation technique to the Lee-O'Sullivan interpolation algorithm in Chapter 5. A new basis construction algorithm is developed and it takes into account the additional constraints imposed by the interpolation problem that results upon the re-encoding transformation. The re-encoding coordinate transformation 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. Chapter 6 presents a VLSI design example of the re-encoding coordinate transformation technique introduced in the previous chapter. A fast and optimal algorithm to determine the re- encoding positions and an architecture that enables concurrent processing and eliminates idle time of the various hardware units are proposed. The entire design is synthesized using SMIC's 0.18 -[mu]m library to a total area of 0.51mm2. It has a throughput of approximately 500Mbps. A high-speed interpolation architecture is presented in Chapter 7. This novel architecture applies hybrid data format to represent a finite field number, thus breaks the long critical path delay bottleneck associated with existing architectures. The proposed architecture also enables maximum overlap in time between 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. Bivariate polynomial factorization is an important step of algebraic softdecision decoding of Reed-Solomon codes and contributes to a significant portion of the overall decoding latency. In Chapter 8, 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 our new architecture have a significantly smaller worst-case decoding latency, but it is also more area efficient since the large amount of hardware consumption for routing polynomial coefficients to various polynomial update engines is completely avoided