Forced sequence sequential decoding: a concatenated coding systemwith iterated sequential inner decoding

We describe a new concatenated decoding scheme based on iterations between an inner sequentially decoded convolutional code of rate R=1/4 and memory M=23, and block interleaved outer Reed-Solomon (RS) codes with nonuniform profile. With this scheme decoding with good performance is possible as low as E_b/N₀=0.6 dB, which is about 1.25 dB below the signal-to-noise ratio (SNR) that marks the cutoff rate for the full system. Accounting for about 0.45 dB due to the outer codes, sequential decoding takes place at about 1.7 dB below the SNR cutoff rate for the convolutional code. This is possible since the iteration process provides the sequential decoders with side information that allows a smaller average load and minimizes the probability of computational overflow. Analytical results for the probability that the first RS word is decoded after C computations are presented. These results are supported by simulation results that are also extended to other parameters     

A versatile time-domain Reed-Solomon decoder

A versatile Reed-Solomon (RS) decoder structure based on the time-domain decoding algorithm (transform decoding without transforms) is developed. The algorithm is restructured, and a method is given to decode any RS code generated by any generator polynomial. The main advantage of the decoder structure is its versatility, that is, it can be programmed to decode any Reed-Solomon code defined in Galois field (GF) 2^m with a fixed symbol size m. This decoder can correct errors and erasures for any RS code, including shortened and singly extended codes. It is shown that the decoder has a very simple structure and can be used to design high-speed single-chip VLSI decoders. As an example, a gate-array-based programmable RS decoder is implemented on a single chip. This decoder chip can decode any RS code defined in GF (2⁵) with any code word length and any number of information symbols. The decoder chip is fabricated using low-power 1.5-μ, two-layer-metal, HCMOS technology     

RS码译码器综述

ＲＳ码是差错控制领域中一类重要的线性分组码，由于具有很强的纠随机错和突发错的能力，被广泛应用于各种差错控制系统中，本文从ＲＳ译码算法，ＲＳ译码器的ＶＬＳＩ结构和ＲＳ码系统性能三方面论述了ＲＳ译码器的发展现状，并展望了译码器的未来发展方向。     

之型码和级联之型码

本文介绍了一种新型的纠错码，称之为“之型码”。之型码可以形成非常简捷的软输入/软输出译码规则，我们在Max-Log-MAP(MLM)译码方法的基础上提出了一种译码规则，这一译码规则的计算复杂度为每次迭代计算单位信息比特大约需要20次加法运算操作。在仿真实验中，我们用最优译码器和更简捷的次最优译码器进行译码时，其性能在误比特率为10^-5处分别距香农理论极限仅0.9dB和1.4dBH。此外，上述码字与2维turbo码相比具有更低的误码基底值（error floor）。     

Turbo encoding and decoding of Reed-Solomon codes through binary decomposition and self-concatenation

This paper presents a two-stage turbo-coding scheme for Reed-Solomon (RS) codes through binary decomposition and self-concatenation. In this scheme, the binary image of an RS code over GF(2/sup m/) is first decomposed into a set of binary component codes with relatively small trellis complexities. Then the RS code is formatted as a self-concatenated code with itself as the outer code and the binary component codes as the inner codes in a turbo-coding arrangement. In decoding, the inner codes are decoded with turbo decoding and the outer code is decoded with either an algebraic decoding algorithm or a reliability-based decoding algorithm. The outer and inner decoders interact during each decoding iteration. For RS codes of lengths up to 255, the proposed two-stage coding scheme is practically implementable and provides a significant coding gain over conventional algebraic and reliability-based decoding algorithms.     

自由空间光通信中LT码的编码技术研究

为了克服大气湍流对自由空间光通信(FSO)链路的影响,将LT码应用到FSO系统中,并结合基于部分信息LT码的修正转移鲁棒孤子分布(ISRSD),模拟了不同大气湍流强度信道,采用不同的编码方案进行模拟比较,结果表明:与RS码相比,误码率为10-4时,LT码获得大约2 dB的编码增益;相比于RSD,ISRSD能使译码开销降低1％～2％,且LT码采用ISRSD后,误码率为10-7时,系统获得0.2～0.5 dB的编码增益.     

Finite Precision Analysis for Space-Time Decoding

Low complexity optimal (or nearly optimal) decoders for space-time codes have recently been under intensive investigation. For example, recent works by Sirianunpiboon and others show that the Silver code and the Golden code can be decoded optimally (or nearly optimally) with quadratic decoding complexity. Fast decodability makes them very attractive in practice. In implementing these decoders, floating-point to fixed-point conversion (FFC) needs to be carefully undertaken to minimize hardware cost while retaining decoding performance. The process of quantization for fixed-point representations is often ignored by research community and lacks investigation, and so FFC is often conducted heuristically based on simulations. This paper studies the effects of quantization to space-time coded systems from an information theoretic perspective. It shows the analytical relationship between quantization error and decoding performance deterioration. This paper also proposes a general finite precision implementation methodology including two FFC criteria for space-time coded systems within an integer optimization framework. As a particular example, this paper examines the finite precision implementation of the quadratic optimal decoding algorithm of the Silver code. However, our methodology and techniques can be applied to general space-time codes.      

High-Speed RS(255, 239) Decoder Based on LCC Decoding

Algebraic Soft-Decision Decoding (ASD) of Reed–Solomon (RS) codes provides higher coding gain over the conventional hard-decision decoding (HDD), but involves high computational complexity. Among the existing ASD methods, the Low Complexity Chase (LCC) decoding is the one with the lowest implementation cost. LCC decoding is based on generating 2 ^η test vectors, where η symbols are selected as the least reliable symbols for which hard-decision or the second more reliable decision are employed. Previous decoding algorithms for LCC decoders are based on interpolation and re-encoding techniques. On the other hand, HDD algorithms such as the Berlekamp–Massey (BM) algorithm or the Euclidean algorithm, despite of their low computational complexity, are not considered suitable for LCC decoding. In this paper, we present a new approach to LCC decoding based on one of these HDD algorithms, the inversion-less Berlekamp–Massey (iBM) algorithm, where the test vectors are selected for correction during decoding on occurrence of hard-decision decoding failure. The proposed architecture when applied to a RS(255, 239) code with η=3, saves a 20.5% and 2% of area compared to the LCC with factorization and a factorization-free decoder, respectively. In both cases, the latency is reduced by 34.5%, which is an increase of throughput rate in the same percentage since the critical path is the same in all the competing architectures. So an efficiency of at least 56% in terms of area-delay product can be obtained, compared with previous works. A complete RS(255, 239) LCC decoder with η=3 has been coded in VHDL and synthesized for implementation in Vitex-5 FPGA device, and by using SAED 90 nm standard cell library as well, and find a decoding rate of 710 Mbps and 4.2 Gbps and area of 2527 slices and 0.36 mm², respectively.     

迭代译码的级联Reed-Solomon乘积码与卷积码

该文提出用Reed Solomon(RS)乘积码作为外码,卷积码作为内码的级联码方案并且内外码间用Congruential向量生成的交织图案对RS码符号进行重排列。对此级联码采用的迭代译码基于成员码的软译码算法。当迭代次数达到最大后,通过计算RS码的校正子,提出一种纠正残余错误的方法,进一步提高了系统的误比特性能。仿真结果表明,在AWGN信道中与迭代译码的级联RS/卷积码相比,当误比特率为1e-5时,新系统的编码增益大约有0.4 dB。     

The capacity of binary channels that use linear codes and decoders

This paper analyzes the performance of concatenated coding systems operating over the binary-symmetric channel (BSC) by examining the loss of capacity resulting from each of the processing steps. The techniques described in this paper allow the separate evaluation of codes and decoders and thus the identification of where loss of capacity occurs. They are, moreover, very useful for the overall design of a communications system, e.g., for evaluating the benefits of inner decoders that produce side information. The first two sections of this paper provide a general technique (based on the coset weight distribution of a binary linear code) for calculating the composite capacity of the code and a BSC in isolation. The later sections examine the composite capacities of binary linear codes, the BSC, and various decoders. The composite capacities of the (8,4) extended Hamming, (24, 12) extended Golay, and (48, 24) quadratic residue codes appear as examples throughout the paper. The calculations in these examples show that, in a concatenated coding system, having an inner decoder provide more information than the maximum-likelihood (ML) estimate to an outer decoder is not a computationally efficient technique, unless generalized minimum-distance decoding of an outer code is extremely easy. Specifically, for the (8,4) extended Hamming and (24, 12) extended Golay inner codes, the gains from using any inner decoder providing side information, instead of a strictly ML inner decoder, are shown to be no greater than 0.77 and 0.34 dB, respectively, for a BSC crossover probability of 0.1 or less, However, if computationally efficient generalized minimum distance decoders for powerful outer codes, e.g., Reed-Solomon codes, become available, they will allow the use of simple inner codes, since both simple and complex inner codes have very similar capacity losses     

Near-optimum decoding of product codes: block turbo codes

This paper describes an iterative decoding algorithm for any product code built using linear block codes. It is based on soft-input/soft-output decoders for decoding the component codes so that near-optimum performance is obtained at each iteration. This soft-input/soft-output decoder is a Chase decoder which delivers soft outputs instead of binary decisions. The soft output of the decoder is an estimation of the log-likelihood ratio (LLR) of the binary decisions given by the Chase decoder. The theoretical justifications of this algorithm are developed and the method used for computing the soft output is fully described. The iterative decoding of product codes is also known as the block turbo code (BTC) because the concept is quite similar to turbo codes based on iterative decoding of concatenated recursive convolutional codes. The performance of different Bose-Chaudhuri-Hocquenghem (BCH)-BTCs are given for the Gaussian and the Rayleigh channel. Performance on the Gaussian channel indicates that data transmission at 0.8 dB of Shannon's limit or more than 98% (R/C>0.98) of channel capacity can be achieved with high-code-rate BTC using only four iterations. For the Rayleigh channel, the slope of the bit-error rate (BER) curve is as steep as for the Gaussian channel without using channel state information     

Efficient Generalized Minimum-distance Decoders of Reed-Solomon Codes

Generalized minimum distance (GMD) decoding of Reed–Solomon (RS) codes can correct more errors than conventional hard-decision decoding by running error-and-erasure decoding multiple times for different erasure patterns. The latency of the GMD decoding can be reduced by the Kötter’s one-pass decoding scheme. This scheme first carries out an error-only hard-decision decoding. Then all pairs of error-erasure locators and evaluators are derived iteratively in one run based on the result of the error-only decoding. In this paper, a more efficient interpolation-based one-pass GMD decoding scheme is studied. Applying the re-encoding and coordinate transformation, the result of erasure-only decoding can be directly derived. Then the locator and evaluator pairs for other erasure patterns are generated iteratively by applying interpolation. A simplified polynomial selection scheme is proposed to pass only one pair of locator and evaluator to successive decoding steps and a low-complexity parallel Chien search architecture is developed to implement this selection scheme. With the proposed polynomial selection architecture, the interpolation can run at the full speed to greatly increase the throughput. After efficient architectures and effective optimizations are employed, a generalized hardware complexity analysis is provided for the proposed interpolation-based decoder. For a (255, 239) RS code, the high-speed interpolation-based one-pass GMD decoder can achieve 53% higher throughput than the Kötter’s decoder with slightly more hardware requirement. In terms of speed-over-area ratio, our design is 51% more efficient. In addition, compared to other soft-decision decoders, the high-speed interpolation-based GMD decoder can achieve better performance-complexity tradeoff.     

A reduced-complexity sequence detector with soft outputs forpartial-response channels

Data transmission in a binary partial-response channel is often accomplished using a concatenated code consisting of an inner modulation code and an outer error-correcting code (ECC). We consider two inner decoders for such a code, each consisting of a reduced-complexity sequence detector modified to provide an estimate of the reliability of each bit. These reliability values are then used by the outer decoder to achieve improved performance. Although one of these decoders is considerably simpler than the other, their performances were comparable in the cases we considered. Both achieve considerable improvement over a decoder that uses hard-decision decoding of the inner code     

Low Complexity Soft Decoder for Nordstrom-Robinson Code With Application to the Chinese DTTB Standard

Nordstrom-Robinson (NR) code followed by 4 quadrature-amplitude modulation (4QAM) mapping is one of the working modes in the Chinese digital television terrestrial broadcasting (DTTB) standard, where the outer code is a low-density parity-check (LDPC) code. Since LDPC decoders usually accept soft rather than hard inputs for better error performance, soft NR decoders are highly recommended. In this paper, several novel low-complexity soft NR decoders are proposed with excellent error performance. Simulation results show that the proposed algorithm based on the maximum, second and third maximum (MST) cross correlation values achieves very low complexity at the cost of performance loss only about 0.1 dB at bit error rate (BER) of $10^{-6}$ , under both additive white Gaussian noise (AWGN) and independent Rayleigh fading channels, compared to the ideal maximum a posteriori (MAP) decoder.      

Belief propagation decoding of Reed-Solomon codes; a bit-level soft decision decoding algorithm

In this article we propose the application of Belief Propagation (BP) algorithm as a novel bit-level soft decision decoding (SDD) technique for Reed-Solomon (RS) codes. A brief tutorial on Belief Propagation algorithm is presented. A central issue in the application of BP algorithm to decoding RS codes is the construction of a sparse parity check matrix for the binary image of the code. It is demonstrated that Vardy's technique may be applied to find a sparse parity check matrix for RS codes. However, this technique is not applicable to all cases. The BP algorithm is applied to two test codes. In one case, simulation models show that the BP algorithm outperforms the hard decision Euclidean decoding by more than 2 dB of additional coding gain. The results with the second test code are not as promising.     

Zigzag codes and concatenated zigzag codes

This paper introduces a family of error-correcting codes called zigzag codes. A zigzag code is described by a highly structured zigzag graph. Due to the structural properties of the graph, very low-complexity soft-in/soft-out decoding rules can be implemented. We present a decoding rule, based on the Max-Log-APP (MLA) formulation, which requires a total of only 20 addition-equivalent operations per information bit, per iteration. Simulation of a rate-1/2 concatenated zigzag code with four constituent encoders with interleaver length 65 536, yields a bit error rate (BER) of 10^-5 at 0.9 dB and 1.3 dB away from the Shannon limit by optimal (APP) and low-cost suboptimal (MLA) decoders, respectively. A union bound analysis of the bit error probability of the zigzag code is presented. It is shown that the union bounds for these codes can be generated very efficiently. It is also illustrated that, for a fixed interleaver size, the concatenated code has increased code potential as the number of constituent encoders increases. Finally, the analysis shows that zigzag codes with four or more constituent encoders have lower error floors than comparable turbo codes with two constituent encoders     

RS码与LDPC码的联合迭代译码

针对RS码与LDPC码的串行级联结构,提出了一种基于自适应置信传播(ABP)的联合迭代译码方法.译码时,LDPC码置信传播译码器输出的软信息作为RS码ABP译码器的输入;经过一定迭代译码后,RS码译码器输出的软信息又作为LDPC译码器的输入.软输入软输出的RS译码器与LDPC译码器之间经过多次信息传递,译码性能有很大提高.码长中等的LDPC码采用这种级联方案,可以有效克服短环的影响,消除错误平层.仿真结果显示:AWGN信道下这种基于ABP的RS码与LDPC码的联合迭代译码方案可以获得约0.8 dB的增益.     

Variable shortened-and-punctured Reed-Solomon codes for packet loss protection

Techniques using Reed-Solomon (RS) codes to recover lost packets in digital video/audio broadcasting and packet switched network communications are reviewed. Usually, different RS codes and their corresponding encoders/decoders are designed and utilized to meet different requirements for different systems and applications. We incorporate these techniques into a variable RS code and present encoding and decoding algorithms suitable for the variable RS code. A mother RS code can be used to produce a variety of RS codes and the same encoder/decoder can be used for all the derivative codes, with adding/detecting zeros, removing some parity symbols and adding erasures. A VLSI implementation for erasure decoding of the variable RS code is described and the achievable performance is quantitatively analyzed. A typical example shows that the signal processing speed is up to 2.5 Gbits/second and the processing delay is less than one millisecond, when integrating the decoder on a single chip. Therefore, the proposed algorithm and the encoder/decoder can universally be utilized for different applications with various requirements, such as transmission data rate, packet length, packet loss protection capacity, as well as layered protection and adaptive redundancy protection in DVB/DAB, Internet and mobile Internet communications.     

Graph-based iterative decoding algorithms for parity-concatenatedtrellis codes

We construct parity-concatenated trellis codes in which a trellis code is used as the inner code and a simple parity-check code is used as the outer code. From the Tanner-Wiberg-Loeliger (1981, 1996) graph representation, several iterative decoding algorithms can be derived. However, since the graph of the parity-concatenated code contains many short cycles, the conventional min-sum and sum-product algorithms cannot achieve near-optimal decoding. After some simple modifications, we obtain near-optimal iterative decoders. The modifications include either (a) introducing a normalization operation in the min-sum and sum-product algorithms or (b) cutting the short cycles which arise in the iterative Viterbi algorithm (IVA). After modification, all three algorithms can achieve near-optimal performance, but the IVA has the least average complexity. We also show that asymptotically maximum-likelihood (ML) decoding and a posteriori probability (APP) decoding can be achieved using iterative decoders with only two iterations. Unfortunately, this asymptotic behavior is only exhibited when the bit-energy-to-noise ratio is above the cutoff rate. Simulation results show that with trellis shaping, iterative decoding can perform within 1.2 dB of the Shannon limit at a bit error rate (BER) of 4×10^-5 for a block size of 20000 symbols. For a block size of 200 symbols, iterative decoding can perform within 2.1 dB of the Shannon limit     

Memory-Reduced Maximum A Posteriori Probability Decoding for High-Throughput Parallel Turbo Decoders

Wireless communication standards make use of parallel turbo decoder for higher data rate at the cost of large hardware resources. This paper presents a memory-reduced back-trace technique, which is based on a new method of estimating backward-recursion factors, for the maximum a posteriori probability (MAP) decoding. Mathematical reformulations of branch-metric equations are performed to reduce the memory requirement of branch metrics for each trellis stage. Subsequently, an architecture of MAP decoder and its scheduling based on the proposed back trace as well as branch-metric reformulation are presented in this work. Comparative analysis of bit-error-rate (BER) performances in additive white Gaussian noise channel environment for MAP as well as parallel turbo decoders are carried out. It has shown that a MAP decoder with a code rate of 1/2 and a parallel turbo decoder with a code rate of 1/3 have achieved coding gains of 1.28 dB at a BER of 10\(^{-5}\) and of 0.4 dB at a BER of 10\(^{-4}\), respectively. In order to meet high-data-rate benchmarks of recently deployed wireless communication standards, very large scale integration implementations of parallel turbo decoder with 8–64 MAP decoders have been reported. Thereby, savings of hardware resources by such parallel turbo decoders based on the suggested memory-reduced techniques are accounted in terms of complementary metal oxide semiconductor transistor count. It has shown that the parallel turbo decoder with 32 and 64 MAP decoders has shown hardware savings of 34 and 44 % respectively.