Performance Analysis of Algebraic Soft-Decision Decoding of Reed–Solomon Codes

We investigate the decoding region for algebraic soft-decision decoding (ASD) of Reed–Solomon (RS) codes in a discrete, memoryless, additive-noise channel. An expression is derived for the error correction radius within which the soft-decision decoder produces a list that contains the transmitted codeword. The error radius for ASD is shown to be larger than that of Guruswami–Sudan (GS) hard-decision decoding for a subset of low and medium-rate codes. These results are also extended to multivariable interpolation in the sense of Parvaresh and Vardy.      

Low-Latency Factorization Architecture for Algebraic Soft-Decision Decoding of Reed–Solomon Codes

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.     

Backward Interpolation Architecture for Algebraic Soft-Decision Reed–Solomon Decoding

Recently developed algebraic soft-decision (ASD) decoding of Reed-Solomon (RS) codes have attracted much interest due to the fact that they can achieve significant coding gain with polynomial complexity. One major step of ASD decoding is the interpolation. Available interpolation algorithms can only add interpolation points or increase interpolation multiplicities. However, backward interpolation, which eliminates interpolation points or reduces interpolation multiplicities, is indispensable to enable the reusing of interpolation results in the following two scenarios: 1) interpolation needs to be carried out on multiple test vectors, which share common entries and 2) iterative ASD decoding where interpolation points have decreasing multiplicities. Examples for these cases are the low-complexity chase (LCC) decoding and bit-level generalized minimum distance (BGMD) decoding. With lower complexity, these algorithms can achieve similar or higher coding gain than other practical ASD algorithms. In this paper, we propose novel backward interpolation schemes and corresponding efficient implementation architectures for LCC and BGMD decoding through constructing equivalent GrOumlbner bases. The proposed architectures share computational units with forward interpolation architectures. Hence, the area overhead for incorporating the backward interpolation is very small. Substantial area saving or speedup can be achieved by using the backward interpolation. When the proposed architecture is applied to the LCC decoding of a (255, 239) RS code with eta = 3, the area is reduced to 39% of those required by prior architectures. In terms of speed/area ratio, the proposed architecture is 48% more efficient than the best available architecture. For the BGMD decoding of the same code, the proposed architecture can achieve around 20% higher efficiency.     

Efficient VLSI Architecture for Soft-Decision Decoding of Reed–Solomon Codes

Reed–Solomon (RS) codes have very broad applications in digital communication and storage systems. The recently developed algebraic soft-decision decoding (ASD) algorithms of RS codes can achieve substantial coding gain with polynomial complexity. Among the ASD algorithms with practical multiplicity assignment schemes, the bit-level generalized minimum distance (BGMD) decoding algorithm can achieve similar or higher coding gain with lower complexity. ASD algorithms consist of two major steps: the interpolation and the factorization. In this paper, novel architectures for both steps are proposed for the BGMD decoder. The interpolation architecture is based on the newly proposed Lee-O'Sullivan (LO) algorithm. By exploiting the characteristics of the LO algorithm and the multiplicity assignment scheme in the BGMD decoder, the proposed interpolation architecture for a (255, 239) RS code can achieve 25% higher efficiency in terms of speed/area ratio than prior efforts. Root computation over finite fields and polynomial updating are the two main steps of the factorization. A low-latency and prediction-free scheme is introduced in this paper for the root computation in the BGMD decoder. In addition, novel coefficient storage schemes and parallel processing architectures are developed to reduce the latency of the polynomial updating. The proposed factorization architecture is 126% more efficient than the previous direct root computation factorization architecture.      

Applications of Algebraic Soft-Decision Decoding of Reed–Solomon Codes

Efficient soft-decision decoding of Reed–Solomon codes is made possible by the Koetter–Vardy (KV) algorithm which consists of a front-end to the interpolation-based Guruswami–Sudan list decoding algorithm. This paper approaches the soft-decision KV algorithm from the point of view of a communications systems designer who wants to know what benefits the algorithm can give, and how the extra complexity introduced by soft decoding can be managed at the systems level. We show how to reduce the computational complexity and memory requirements of the soft-decision front-end. Applications to wireless communications over Rayleigh fading channels and magnetic recording channels are proposed. For a high-rate (RS 9225,239) Reed–Solomon code, 2–3 dB of soft-decision gain is possible over a Rayleigh fading channel using 16-quadrature amplitude modulation. For shorter codes and at lower rates, the gain can be as large as 9 dB. To lower the complexity of decoding on the systems level, the redecoding architecture is explored which uses only the appropriate amount of complexity to decode each packet. An error-detection criterion based on the properties of the KV decoder is proposed for the redecoding architecture. Queuing analysis verifies the practicality of the redecoding architecture by showing that only a modestly sized RAM buffer is required.     

A Fast Algorithm for the Syndrome Calculation in Algebraic Decoding of Reed–Solomon Codes

In this paper, Fedorenko and Trifonov's procedure is applied to evaluate the syndrome of the received word in time-domain Reed-Solomon decoders. This application leads to a substantial reduction of the computational complexity of the syndrome polynomial for correcting both errors and erasures. Moreover, simulation results for this new syndrome method are given.     

Error Exponents for Two Soft-Decision Decoding Algorithms of Reed–Muller Codes

Error exponents are studied for recursive and majority decoding of general Reed–Muller (RM) codes ${rm RM}(r,m)$ used on the additive white Gaussian noise (AWGN) channels. Both algorithms have low complexity and correct many error patterns whose weight exceeds half the code distance. Decoding consists of multiple consecutive steps, which repeatedly recalculate the input symbols and determine different information symbols using soft-decision majority voting. For any code ${rm RM}(r,m)$, we estimate the probabilities of the information symbols obtained in these recalculations and derive the analytical upper bounds for the block error rates of the recursive and majority decoding. In the case of a low noise, we also obtain the lower bounds and show that the upper bounds are tight. For a higher noise, these bounds closely approach our simulation results.      

Filterbank Decompositions for (Non)-Systematic Reed–Solomon Codes With Applications to Soft Decoding

This paper focuses on Reed-Solomon (RS) codes, which are the most widespread classical error correcting codes. Recently, we have shown that an finite-impulse response (FIR) critically subsampled filterbank representation can be derived for some RS codes. However, this work only addresses RS codes with a non-coprime codeword and dataword length, seriously limiting its practical usability. In this paper, an alternative purely algebraic method is presented to construct such a filterbank. Apart from providing additional insight into the algebraic structure of (non-systematic) RS codes, this method is suited to eliminate the non-coprimeness constraint mentioned before. Using this filterbank decomposition, a RS code is broken into smaller subcodes that can subsequently be used to build a soft-in soft-out (SISO) RS decoder. It is shown how any RS code, written as an FIR filterbank, can be SISO decoded using the filterbank based decoder. Owing to the importance of systematic RS codes, it is shown that any systematic RS code can be decoded using the FIR filterbank decomposition. This leads to better decoding performance in addition with a slightly lower complexity. A further extension towards systematic RS codes is also presented in this paper resulting in an infinite-impulse response critically subsampled filterbank representation.     

Collaborative Decoding of Interleaved Reed–Solomon Codes and Concatenated Code Designs

Interleaved Reed-Solomon codes are applied in numerous data processing, data transmission, and data storage systems. They are generated by interleaving several codewords of ordinary Reed-Solomon codes. Usually, these codewords are decoded independently by classical algebraic decoding methods. However, by collaborative algebraic decoding approaches, such interleaved schemes allow the correction of error patterns beyond half the minimum distance, provided that the errors in the received signal occur in bursts. In this work, collaborative decoding of interleaved Reed-Solomon codes by multisequence shift-register synthesis is considered and analyzed. Based on the framework of interleaved Reed-Solomon codes, concatenated code designs are investigated, which are obtained by interleaving several Reed-Solomon codes, and concatenating them with an inner code.     

High-Speed Interpolation Architecture for Soft-Decision Decoding of Reed–Solomon Codes

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     

Reliability-Based Forward Recursive Algorithms for Algebraic Soft-Decision Decoding of Reed--Solomon Codes

We propose efficient forward recursive algorithms for algebraic soft-decision list decoding of Reed-Solomon codes, which utilize channel reliability information, and outperform the Koetter-Vardy (KV) algorithm with lower decoding latency. We evaluate the performance of the proposed decoding algorithms on additive white Gaussian noise and partial response channels. Simulation results show that we can achieve better performance on a modified extended-extended partial response class 4 channel than on the best possible performance of the KV algorithm, as given by the asymptotic bound for high-rate codes.     

分组码的软判决伪序列译码

本文提出一种在形式上类似于卷积码的序列译码的一般线性分组码的软判决伪序列译码算法，利用广义限译码原理及二元有向树的性质与分枝限搜索技术，降低了译码复杂性，其设备复杂度小于Ｃｈａｓｅ译码器，模拟结果表明，该算法的误码输出性能接近维持比较最大似然译码，好于ＣｈａｓｅⅡ算法，且译码速度与ＣｈａｓｅⅡ算法接近。     

Reed–Solomon and Simplex Codes for Peak-to-Average Power Ratio Reduction in OFDM

New schemes for peak-to-average power ratio reduction in orthogonal frequency-division multiplexing (OFDM) systems are proposed. Reed–Solomon (RS) and simplex codes are employed to create a number of candidates, from which the best are selected. Thereby, in contrast to existing approaches, the codes are arranged over a number of OFDM frames rather than over the carriers, hence a combination of the principles of multiple signal representation with selection (as done in selected mapping) and the use of channel coding is present. In particular, in multiple-antenna transmission, the proposed schemes do not cause any additional delay, but due to the utilization of the dimension space, additional gains can be achieved. Moreover, the schemes are very flexible; due to the selection step, any criterion of optimality can be taken into account. Besides multiple-antenna transmission, packet transmission is briefly considered, which, moreover, covers the appealing similarities with incremental redundancy check schemes in automatic repeat request (ARQ) applications and with decoding of codes transmitted over the erasure channel. The performance of the schemes is (using some approximations) derived analytically and is covered by numerical results that are in very good agreement with the theory. Significant gains can be achieved with these very flexible and versatile methods.      

Soft IP Compiler for a Reed‐Solomon Decoder

In this paper, we present a soft IP compiler for the Reed‐Solomon decoder that generates a fully synthesizable VHDL core exploiting characteristic parameters and design constraints that we newly classify for the soft IP. It produces a structural design with an estimable regular architecture based on a finite state machine with a datapath (FSMD). Since characteristic parameters provide different design points on the design space, using one of two simple procedures called the constructive search with area increment (CSAI) and constructive search with speed decrement (CSSD) for design space exploration, the core compiler makes it possible for an IP user to create the Reed‐Solomon decoder with appropriate sub‐architectures without synthesizing many models. Experimental results show that the IP compiler can apply to several industry standards.     

Reduced Complexity Interpolation Architecture for Soft-Decision Reed–Solomon Decoding

Reed-Solomon (RS) codes are one of the most widely utilized block error-correcting codes in modern communication and computer systems. Compared to hard-decision decoding, soft-decision decoding offers considerably higher error-correcting capability. The Koetter-Vardy (KV) soft-decision decoding algorithm can achieve substantial coding gain, while maintaining a complexity polynomial with respect to the code word length. In the KV algorithm, the interpolation step dominates the decoding complexity. A reduced complexity interpolation architecture is proposed in this paper by eliminating the polynomial updating corresponding to zero discrepancy coefficients in this step. Using this architecture, an area reduction of 27% can be achieved over prior efforts for the interpolation step of a typical (255, 239) RS code, while the interpolation latency remains the same     

Architecture and Implementation of an Interpolation Processor for Soft-Decision Reed–Solomon Decoding

Reed-Solomon codes are powerful error-correcting codes that can be found in many digital communications standards. Recently, there has been an interest in soft-decision decoding of Reed-Solomon codes, incorporating reliability information from the channel into the decoding process. The Koetter-Vardy algorithm is a soft-decision decoding algorithm for Reed-Solomon codes which can provide several dB of gain over traditional hard-decision decoders. The algorithm consists of a soft-decision front end to the interpolation-based Guruswami-Sudan list decoder. The main computational task in the algorithm is a weighted interpolation of a bivariate polynomial. We propose a parallel architecture for the hardware implementation of bivariate interpolation for soft-decision decoding. The key feature is the embedding of both a binary tree and a linear array into a 2-D array processor, enabling fast polynomial evaluation operations. An field-programmable gate array interpolation processor was implemented and demonstrated at a clock frequency of 23 MHz, corresponding to decoding rates of 10-15 Mb/s     

Modified Low-Complexity Chase Soft-Decision Decoder of Reed–Solomon Codes

Silicon-on-Insulator CMOS fabrication technologies are now available that offer a number of unique advantages including the availability of multiple simultaneous transistor thresholds. This paper proposes and analyzes a number of circuits for a reconfigurable array organization based on a balanced ternary logic system in which the logic set {− 1, 0, + 1} maps directly to equivalent voltage levels {−1V, 0V, +1V}. A number of low-power, high-speed components, such as a ternary buffer, flip-flop and look-up table, are described and simulated based on the characteristics of a commercially available silicon-on-sapphire process. A brief analysis indicates that the circuits will be capable of operating at the 22 nm technology node and beyond. A simple example of a Sigma-Delta Modulated FIR filter is mapped to the array and some preliminary estimates are made of its performance and area based on both 3-input and 4-input look-up tables. The simulated ternary array is shown to be capable of operating at clock speeds of more than 200 MHz such that it will readily support standard video bandwidths at useful over-sampling ratios.     

A Simplified Step-by-Step Decoding Algorithm for Parallel Decoding of Reed–Solomon Codes

A simplified parallel step-by-step decoding algorithm is proposed for decoding Reed-Solomon (RS) codes. It uses new method to calculate the determinants of the temporarily changed syndrome matrices, based on the property of these matrices determined in this paper. By using the proposed method, the calculations of the determinants of the temporarily changed syndrome matrices become much simpler and thus the computational complexity of the step-by-step decoding algorithm is significantly reduced.