Advanced decoding algorithms for Reed-Solomon/Convolutional concatenated codes

The evaluation of the union bound for theber of Reed-Solomon/Convolutional concatenated codes indicates that their performance might largely improve through the application of soft iterative decoders. This paper presents an iterative decoding algorithm for concatenated codes consisting of an outer Reed-Solomon code, a symbol interleaver and an inner convolutional code. The performance improvement for iterative and non-iterative decoders is evaluated. Existing solutions for the different decoding stages and their interfaces are discussed and their performance is compared. A new procedure is proposed to define the feedback signal from the output of the Reed-Solomon decoder to the input of the convolutional decoder, which captures the reliability information that can be inferred from errors-and-era-suresrs decoders and includes the “state pinning” approach as a particular case. The decoding schemes are applied to the specificdvb-s concatenated code.     

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     

Coupled Decoding of Block-Convolutional Concatenated Codes

Straightforward implementation of a maximum likelihood decoder implies a complexity that grows algebraically with the inverse of error probability. Forney has suggested an approach, concatenation, for which error probability decreases exponentially with increasing complexity. This paper presents the results of an evaluation of a particular concatenation system, structurally similar to the hybrid system of Falconer, employing a Reed-Solomon outer code and an inner convolutional code. The inner decoder is a Viterbi decoder of constraint length less than the corresponding encoding constraint length (nonmaximum likelihood). The outer decoder assumes one of three possible forms, all employing the likelihood information developed by the inner decoder to assist in outer decoding. Error corrections and erasure fill-ins achieved by the outer decoder are fed back to the inner decoder. Performance is evaluated through computer simulation. The three outer decoders are found to provide approximately the same performance, all yielding low error probabilities at rates somewhat above Rcompof sequential decoding and at signal energy to noise density ratios per information bit around 1.7 dB.     

Concatenated LDGM codes with single decoder

We propose a design criterion for serially concatenated LDGM codes which require a single decoder and a bit-interleaver. The inner LDGM code can be obtained by expanding the rows of the parity check matrix of the outer LDGM code. The resulting codes can be decoded using only the inner LDGM decoder with slight modification. Simulation results show that the performance of the proposed codes is almost the same as that of serially concatenated LDGM code's using both the inner and the outer decoders.     

Low-floor decoders for LDPC codes

One of the most significant impediments to the use of LDPC codes in many communication and storage systems is the error-rate floor phenomenon associated with their iterative decoders. The error floor has been attributed to certain subgraphs of an LDPC code?s Tanner graph induced by so-called trapping sets. We show in this paper that once we identify the trapping sets of an LDPC code of interest, a sum-product algorithm (SPA) decoder can be custom-designed to yield floors that are orders of magnitude lower than floors of the the conventional SPA decoder. We present three classes of such decoders: (1) a bi-mode decoder, (2) a bit-pinning decoder which utilizes one or more outer algebraic codes, and (3) three generalized-LDPC decoders. We demonstrate the effectiveness of these decoders for two codes, the rate-1/2 (2640,1320) Margulis code which is notorious for its floors and a rate-0.3 (640,192) quasi-cyclic code which has been devised for this study. Although the paper focuses on these two codes, the decoder design techniques presented are fully generalizable to any LDPC code.     

A soft-output decoding algorithm for concatenated systems

In order to fully utilize the SDD (soft-decision decoding) capacity of the outer codes in a concatenated system, reliability information on the inner decoder outputs (called soft outputs) needs to be provided to the outer decoder. This paper shows that a modified MAP algorithm can be effectively and accurately used to generate such information. In the course of the presentation, a metric based on the reliability information is proposed for the outer decoder. This metric has the Euclidean metric on AWGN channels as its special case, which leads to the concept of generalized SDD (GSDD). Several practical concerns regarding the proposed soft-output decoder are addressed through theoretical analysis and simulation: the effect of finite decoding depth, computational complexity, range overflow, and scaling. Comparisons to previous work on soft-output decoders are made     

Design of low-density parity check codes for MIMO systems with doubly-iterative receivers

In this paper, the Multiple Input Multiple Output (MIMO) doubly-iterative receiver which consists of the Probabilistic Data Association detector (PDA) and Low-Density Parity-Check Code (LDPC) decoder is developed. The receiver performs two iterative decoding loops. In the outer loop, the soft information is exchanged between the PDA detector and the LDPC decoder. In the inner loop, it is exchanged between variable node and check node decoders inside the LDPC decoder. On the light of the Extrinsic Information Transfer (EXIT) chart technique, an LDPC code degree profile optimization algorithm is developed for the doubly-iterative receiver. Simulation results show the doubly-receiver with optimized irregular LDPC code can have a better performance than the one with the regular one.     

Iterative sequential decoding

It is shown that use of a two-stage decoding procedure consisting simply of an inner stage of block decoding and an outer stage employing a single sequential decoder does not result in an improvement in the computational overflow problem for the sequential decoder. Improvement can, however, result from use of multiple sequential decoders or use of a single sequential decoder with appropriate scrambling. Although the performance improvement resulting from application of these techniques to the additive white Gaussian noise channel is not significant, implementation and rate advantages make iterative sequential decoding techniques worth pursuing. Ia particular, with these techniques, a sequential decoder for a binary symmetric channel can be used regardless of the physical channel characteristics. Such a "universal" decoder is expected to be both simple and capable of high rate operation.     

Concatenated Coding Systems Employing a Unit-Memory Convolutional Code and a Byte-Oriented Decoding Algorithm

Concatenated coding systems utilizing a convolutional code as the inner code and a Reed-Solomon code as the outer code are considered. In order to obtain very reliable communications over a very noisy channel with relatively modest coding complexity, it is proposed to concatenate a byte-oriented unit-memory convolutional code with an RS outer code whose symbol size is one byte. It is further proposed to utilize a real-time minimal-byte-error probability decoding algorithm, together with feedback from the outer decoder, in the decoder for the inner convolutional code. The performance of the proposed concatenated coding system is studied, and the improvement over conventional concatenated systems due to each additional feature is isolated.     

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.     

High rate concatenated coding systems using bandwidth efficienttrellis inner codes

High-rate concatenated coding systems with bandwidth-efficient trellis inner codes and Reed-Solomon (RS) outer codes are investigated for application in high-speed satellite communication systems. Two concatenated coding schemes are proposed. In one the inner code is decoded with soft-decision Viterbi decoding, and the outer RS code performs error-correction-only decoding (decoding without side information). In the other the inner code is decoded with a modified Viterbi algorithm, which produces reliability information along with the decoded output. In this algorithm, path metrics are used to estimate the entire information sequence, whereas branch metrics are used to provide reliability information on the decoded sequence. This information is used to erase unreliable bits in the decoded output. An errors-and-erasures RS decoder is then used for the outer code. The two schemes have been proposed for high-speed data communication on NASA satellite channels. The rates considered are at least double those used in current NASA systems, and the results indicate that high system reliability can still be achieved     

On decoding concatenated codes

The correcting properties of concatenated codes with parallel decoding over an additive channel are investigated. The ith inner decoder's output is a codeword if the Euclidean distance between the received vector and some codeword is less than Δ_i and an erasure otherwise. The outer decoders correct errors and erasures. The error-correcting capability, which is taken to be the minimum length of any noise vector that can cause an error, is obtained for a bank of z inner and outer decoders as a function of the thresholds used. The set of thresholds that maximize the error-correcting capability is also found. It is shown that for a small number of branches, the error-correcting capability is nearly as large as any decoder     

Selective serial concatenation of turbo codes

A serial concatenation scheme consisting of a Bose-Chaudhuri-Hocquenghem (BCH) outer code and a turbo inner code is proposed. We first establish that only a small number of bit positions at the turbo decoder output are likely to be in error at high signal-to-noise ratios. A double-error correcting BCH outer code is used to protect these particular error prone bits. Simulation results for an additive white Gaussian noise (AWGN) channel show that the bit-error rate (BER) floor of the turbo code can be lowered by using this serial concatenation scheme. The proposed technique offers higher throughput efficiency and lower complexity than other serial concatenation schemes     

Turbo decoder

We propose an adaptive channel SNR estimation algorithm required for the iterative MAP decoding of turbo decoders. The proposed algorithm uses the extrinsic values generated within the iterative MAP decoder to update the channel SNR estimate toward its optimum value per each decoder iteration or per each turbo code frame     

Distributed source coding for satellite communications

Inspired by mobile satellite communications systems, we consider a source coding system which consists of multiple sources, multiple encoders, and multiple decoders. Each encoder has access to a certain subset of the sources, each decoder has access to certain subset of the encoders, and each decoder reconstructs a certain subset of the sources almost perfectly. The connectivity between the sources and the encoders, the connectivity between the encoders and the decoders, and the reconstruction requirements for the decoders are all arbitrary. Our goal is to characterize the admissible coding rate region. Despite the generality of the problem, we have developed an approach which enables us to study all cases on the same footing. We obtain inner and outer bounds of the admissible coding rate region in terms of Γ_N * and Γ¯_N*, respectively, which are fundamental regions in the entropy space defined by Yeung (1991). So far, there has not been a full characterization of Γ_N*, so these bounds cannot be evaluated explicitly except for some special cases. Nevertheless, we obtain an alternative outer bound which can be evaluated explicitly. We show that this bound is tight for all the special cases for which the admissible coding rate region is known. The model we study in this paper is more general than all previously reported models on multilevel diversity coding, and the tools we use are new in multiuser information theory     

Differential space-time turbo codes

Serial concatenation of simple error control codes and differential space-time modulation is considered. Decoding is performed iteratively by passing symbol-wise a posteriori probability values between the decoders of the inner space-time code and the outer code. An extrinsic information transfer analysis is used to predict thresholds for outer convolutional codes of various memory orders and a simple outer parity-check code. This parity-check code is well matched to the inner differential space-time code and achieves a bit-error rate (BER) of 10/sup -6/ less than 2 dB from the Shannon capacity of the fast fading multiple antenna channel. The differential space-time code can also be used to generate a priori information in the absence of channel knowledge. This information can be exploited by a channel estimator inserted into the decoding iteration. It is demonstrated that the inner space-time code provides soft training symbols from periodically inserted training symbols. The reliability of these soft training symbols does not depend on the speed of the channel variations, but on the structure of the inner code and the signal-to-noise ratio (SNR). Simulation studies confirm these findings and show that the proposed system with no initial channel knowledge achieves a performance very close to that of the system with perfect channel knowledge.     

Toward low LDPC-code floors: a case study

While LDPC codes have been widely acclaimed in recent years for their near-capacity performance, they have not found their way into many important applications. For some cases, this is due to their increased decoding complexity relative to the classical coding techniques. For other cases, this is due to their inability to reach very low bit error rates (e.g., 10?12) at low signal-to-noise ratios (SNRs), a consequence of the errorrate floor phenomenon associated with iterative LDPC decoders. In the present paper, we make strides in the low-floor problem by identifying the weaknesses of the code under study and applying compensatory counter-measures. These counter-measures include: modifying the code itself, modifying the decoder, or adding a properly designed outer algebraic code. Our results demonstrate that each of these techniques can successfully lower an LDPC code?s floor, and that, for the code under study, an outer BCH code appears to be particularly effective. All of our results are based on FPGA decoder simulations and so they are reliable and repeatable.     

A 0.18-$muhbox m$CMOS Analog Min-Sum Iterative Decoder for a (32,8) Low-Density Parity-Check (LDPC) Code

Current-mode circuits are presented for implementing analog min-sum (MS) iterative decoders. These decoders are used to efficiently decode the best known error correcting codes such as low-density parity-check (LDPC) codes and turbo codes. The proposed circuits are devised based on current mirrors, and thus, in any fabrication technology that accurate current mirrors can be designed, analog MS decoders can be implemented. The functionality of the proposed circuits is verified by implementing an analog MS decoder for a (32,8) LDPC code in a 0.18-mum CMOS technology. This decoder is the first reported analog MS decoder. For low signal to noise ratios where the circuit imperfections are dominated by the noise of the channel, the measured error correcting performance of this chip in steady-state condition surpasses that of the conventional floating-point discrete-time synchronous MS decoder. When data throughput is 6 Mb/s, loss in the coding gain compared to the conventional MS decoder at BER of 10^-3 is about 0.3 dB and power consumption is about 5 mW. This is the first time that an analog decoder has been successfully tested for an LDPC code, though a short one     

Optimizations of a Hardware Decoder for Deep-Space Optical Communications

The National Aeronautics and Space Administration has developed a capacity approaching modulation and coding scheme that comprises a serial concatenation of an inner accumulate pulse-position modulation (PPM) and an outer convolutional code [or serially concatenated PPM (SCPPM)] for deep-space optical communications. Decoding of this code uses the turbo principle. However, due to the nonbinary property of SCPPM, a straightforward application of classical turbo decoding is very inefficient. Here, we present various optimizations applicable in hardware implementation of the SCPPM decoder. More specifically, we feature a Super Gamma computation to efficiently handle parallel trellis edges, a pipeline-friendly ";maxstar top-2"; circuit that reduces the max-only approximation penalty, a low-latency cyclic redundancy check circuit for window-based decoders, and a high-speed algorithmic polynomial interleaver that leads to memory savings. Using the featured optimizations, we implement a 6.72 megabits-per-second (Mbps) SCPPM decoder on a single field-programmable gate array (FPGA). Compared to the current data rate of 256 kilobits per second from Mars, the SCPPM coded scheme represents a throughput increase of more than twenty-six fold. Extension to a 50-Mbps decoder on a board with multiple FPGAs follows naturally. We show through hardware simulations that the SCPPM coded system can operate within 1 dB of the Shannon capacity at nominal operating conditions.     

Neural network decoding of the block Markov superposition transmission

A neural network (NN)-based decoding algorithm of block Markov superposition transmission (BMST) was researched.The decoders of the basic code with different network structures and representations of training data were implemented using NN.Integrating the NN-based decoder of the basic code in an iterative manner,a sliding window decoding algorithm was presented.To analyze the bit error rate (BER) performance,the genie-aided (GA) lower bounds were presented.The NN-based decoding algorithm of the BMST provides a possible way to apply NN to decode long codes.That means the part of the conventional decoder could be replaced by the NN.Numerical results show that the NN-based decoder of basic code can achieve the BER performance of the maximum likelihood (ML) decoder.For the BMST codes,BER performance of the NN-based decoding algorithm matches well with the GA lower bound and exhibits an extra coding gain.