The main focus of this thesis is on finding efficient decoding methods for Reed-Solomon (RS) codes, i.e., algorithms with acceptable performance and affordable complexity. Three classes of decoders are considered including sphere decoding, belief propagation decoding and interpolation-based decoding. Originally proposed for finding the exact solution of least-squares problems, sphere decoding (SD) is used along with the most reliable basis (MRB) to design an efficient soft decoding algorithm for RS codes. For an (N, K) RS code, given the received vector and the lattice of all possible transmitted vectors, we propose to look for only those lattice points that fall within a sphere centered at the received vector and also are valid codewords. To achieve this goal, we use the fact that RS codes are maximum distance separable (MDS). Therefore, we use sphere decoding in order to find tentative solutions consisting of the K most reliable code symbols that fall inside the sphere. The acceptable values for each of these symbols are selected from an ordered set of most probable transmitted symbols. Based on the MDS property, K code symbols of each tentative solution can he used to find the rest of codeword symbols. If the resulting codeword is within the search radius, it is saved as a candidate transmitted codeword. Since we first find the most reliable code symbols and for each of them we use an ordered set of most probable transmitted symbols, candidate codewords are found quickly resulting in reduced complexity. Considerable coding gains are achieved over the traditional hard decision decoders with moderate increase in complexity. Due to their simplicity and good performance when used for decoding low density parity check (LDPC) codes, iterative decoders based on belief propagation (BP) have also been considered for RS codes. However, the parity check matrix of RS codes is very dense resulting in lots of short cycles in the factor graph and consequently preventing the reliability updates (using BP) from converging to a codeword. In this thesis, we propose two BP based decoding methods. In both of them, a low density extended parity check matrix is used because of its lower number of short cycles. In the first method, the cyclic structure of RS codes is taken into account and BP algorithm is applied on different cyclically shifted versions of received reliabilities, capable of detecting different error patterns. This way, some deterministic errors can be avoided. The second method is based on information correction in BP decoding where all possible values are tested for selected bits with low reliabilities. This way, the chance of BP iterations to converge to a codeword is improved significantly. Compared to the existing iterative methods for RS codes, our proposed methods provide a very good trade-off between the performance and the complexity. We also consider interpolation based decoding of RS codes. We specifically focus on Guruswami-Sudan (GS) interpolation decoding algorithm. Using the algebraic structure of RS codes and bivariate interpolation, the GS method has shown improved error correction capability compared to the traditional hard decision decoders. Based on the GS method, a multivariate interpolation decoding method is proposed for decoding interleaved RS (IRS) codes. Using this method all the RS codewords of the interleaved scheme are decoded simultaneously. In the presence of burst errors, the proposed method has improved correction capability compared to the GS method. This method is applied for decoding IRS codes when used as outer codes in concatenated codes.

Error-correcting coding has become one integral part in nearly all the modern data transmission and storage systems. Due to the powerful error-correcting capability, Reed-Solomon (RS) codes are among the most extensively used error-correcting codes with applications in wireless communications, deep-space probing, magnetic and optical recording, and digital television. Traditional hard-decision decoding (HDD) algorithms of RS codes can correct as many symbol errors as half the minimum distance of the code. Recently, much attention has been paid to algebraic soft-decision decoding (ASD) algorithms of RS codes. These algorithms incorporate channel probabilities into an algebraic interpolation process. As a result, significant coding gain can be achieved with a complexity that is polynomial in codeword length. Practical ASD algorithms include the Koetter-Vardy, low-complexity Chase (LCC) and bit-level generalized minimum distance (BGMD) decodings. This book focuses on the design of efficient VLSI architectures for ASD decoders.

Algebraic soft-decision decoding (ASD) algorithms of Reed-Solomon (RS) codes have attracted much interest due to their significant coding gain and polynomial complexity. Practical ASD algorithms include the Koetter-Vardy, low-complexity Chase (LCC) and bit-level generalized minimum distance (BGMD) decodings. This thesis focuses on the design of efficient VLSI architectures for ASD decoders. One major step of ASD algorithms is the interpolation. Available interpolation algorithms can only add interpolation points or increase interpolation multiplicities. However, backward interpolation, which eliminates interpolation points or reduces multiplicities, is indispensable to enable the re-using of interpolation results. In this thesis, a novel backward interpolation is first proposed for the LCC decoding through constructing equivalent Grbner bases. In the LCC decoding, 2 test vectors need to be interpolated over. With backward interpolation, the interpolation result for each of the second and later test vectors can be computed by only one backward and one forward interpolation iterations. Compared to the previous design, the proposed backward-forward interpolation scheme can lead to significant memory saving. To reduce the interpolation latency of the LCC decoding, a unified backward-forward interpolation is proposed to carry out both interpolations in a single iteration. With only 40percent area overhead, the proposed unified interpolation architecture can almost double the throughput when large is adopted. Moreover, a reduced-complexity multi-interpolator scheme is developed for the low-latency LCC decoding. The proposed backward interpolation is further extended to the iterative BGMD decoding. By reusing the interpolation results, at least 40 percent of the interpolation iterations can be saved for a (255, 239) code while the area overhead is small. Further speedup of the BGMD interpolation is limited by the inherent serial nature of the interpolation algorithm. In this thesis, a novel interpolation scheme that can combine multiple interpolation iterations is developed. Efficient architectures are presented to integrate the combined and backward interpolation techniques. A combined-backward interpolator of a (255, 239) code is implemented and can achieve a throughput of 440 Mbps on a Xilinx XC2V4000 FPGA device. Compared to the previous fastest implementation, our implementation can achieve a speedup of 64percent with 51percent less FPGA resource. The factorization is another major step of ASD algorithms. In the re-encoded LCC decoding, it is proved that the factorization step can be eliminated. Hence, the LCC decoder can be further simplified. In the reencoded ASD decoders, a re-encoder and an erasure decoder need to be added. These two blocks can take a significant proportion of the overall decoder area and may limit the achievable throughput. An efficient re-encoder design is proposed by computing the erasure locator and evaluator through direct multiplications and reformulating other involved computations. When applied to a (255, 239) code, our re-encoder can achieve 82percent higher throughput than the previous design with 11percent less area. With minor modifications, the proposed design can also be used to implement erasure decoder. After applying available complexity-reducing techniques, complexity comparisons for three practical ASD decoders were carried out. It is derived that the LCC decoder can achieve similar or higher coding gain with lower complexity for high-rate codes. This thesis also provides discussions on how the hardware complexities of ASD decoders change with codeword length, code rate and other parameters.

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.