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.     

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.     

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     

Serial concatenated TCM with an inner accumulate code - part II: density-evolution analysis

In a companion paper, we showed the existence of decoding thresholds for maximum-likelihood (ML) decoding of a serial concatenated trellis-coded modulation (SCTCM) system with one or more inner accumulate codes. In this paper, we compute the decoding thresholds for an iterative, non-ML decoder by density evolution (DE), assuming infinite blocklengths. We also derive a stability condition for the particular case of an outer parity-check code and a single inner accumulate code. We show that, for equiprobable signaling, the bit-wise log-likelihood ratio densities for higher order constellations are symmetric. Furthermore, when used in DE, these densities can be averaged without significantly affecting the resulting threshold values. For an outer single parity-check code, the lowest decoding thresholds are achieved with two inner accumulate codes. For an outer repeat code, a single inner accumulate code gives the lowest thresholds. At code rates r/sub c/>2/3, the decoding thresholds for the SCTCM system are within 1 dB of the constellation-constrained channel capacity for additive white Gaussian noise channels, and within 1.5 dB for independent, identically distributed Rayleigh channels. Simulation results verify the computed thresholds.     

Code characteristic matching for iterative decoding of serially concatenated codes

The design of serially concatenated codes has yet been dominated by optimizing asymptotic slopes of error probability curves. We propose mutual information transfer characteristics for soft in/soft out decoders to design serially concatenated codes based on the convergence behavior of iterative decoding. The exchange of extrinsic information is visualized as a decoding trajectory in the Extrinsic Information Transfer Chart (exit chart). By finding matching pairs of inner and outer decoder transfer characteristics we are able to construct serially concatenated codes whose iterative decoder converges towards low bit error rate at signal- to- noise ratios close to the theoretical limits.     

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     

Low complexity concatenated coding schemes for digital satellite communications

A study of reduced complexity concatenated coding schemes, for commercial digital satellite systems with low-cost earth terminals, is reported. The study explored trade-offs between coding gain, overall rate and decoder complexity, and compared concatenated schemes with single codes. It concentrated on short block and constraint length inner codes, with soft decision decoding, concatenated with a range of Reed-Solomon outer codes. The dimension of the inner code was matched to the outer code symbol size, and appropriate interleaving between the inner and outer codes was used. Very useful coding gains were achieved with relatively high-rate, low-complexity schemes. For example, concatenating the soft decision decoded (9,8) single parity check inner code with the CCSDS recommended standard Reed-Solomon outer code gives a coding gain of 4.8dB at a bit error probability of 10^?5, with an overall rate of 0-78.     

Improving the distance properties of turbo codes using a third component code: 3D turbo codes - [transactions letters]

Thanks to the probabilistic message passing performed between its component decoders, a turbo decoder is able to provide strong error correction close to the theoretical limit. However, the minimum Hamming distance (d_min) of a turbo code may not be sufficiently large to ensure large asymptotic gains at very low error rates (the so-called flattening effect). Increasing the d_min of a turbo code may involve using component encoders with a large number of states, devising more sophisticated internal permutations, or increasing the number of component encoders. This paper addresses the latter option and proposes a modified turbo code in which a fraction of the parity bits are encoded by a rate-1, third encoder. The result is a noticeably increased d_min, which improves turbo decoder performance at low error rates. Performance comparisons with turbo codes and serially concatenated convolutional codes are given.     

Capacity and cutoff rate calculations for a concatenated codingsystem

A model is developed for a concatenated coding system, and from it the overall channel cutoff rate and capacity is found using random coding arguments. The effects of interleaving between the inner and outer codes and of the availability of side information to the outer decoder are considered. The performance of several specific concatenated coding systems is calculated and used for comparison with the random coding result. From the analysis, a number of general conclusions regarding the design of concatenated coding systems are presented. All the results are derived assuming a block inner code     

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.     

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     

Extended Hamming and BCH soft decision decoders for mobile dataapplications

A methodology is presented for the design and development of efficient trellis-based soft decision decoders for extended Hamming and BCH codes. A new metric for noncoherent discriminator detection is proposed that substantially improves the performance of trellis-based decoders over additive white Gaussian noise (AWGN) channels. Minimal edge trellises are then presented for the class of extended Hamming codes and the (32, 21) extended BCH code. The latter is in extensive use in narrow-band wireless data systems. An automatic request (ARQ) protocol is described that allows the soft decision decoders to outperform their hard decision counterparts in both reliability and throughput     

Even more efficient bounded-distance decoding of the hexacode, theGolay code, and the Leech lattice

We present a new bounded-distance decoding algorithm for the hexacode, which requires at most 34 real operations in the worst case, as compared to 57 such operations in the best previously known decoder. The new algorithm is then employed for bounded-distance decoding of the Leech lattice and the Golay code. The error-correction radius of the resulting decoders is equal to that of a maximum-likelihood decoder. The resulting decoding complexity is at most 331 real operations for the Leech lattice and at most 121 operations for the Golay code. For all the three codes-the hexacode, the Golay code, and the Leech lattice-the proposed decoders are considerably more efficient than any decoder presently known     

Optimal binary vector quantization via enumeration of coveringcodes

Binary vector quantization (BVQ) refers to block coding of binary vectors under a fidelity measure. Covering codes were studied as a means of lattice BVQ. But a further source coding problem hidden in the equivalence of covering codes has seemingly eluded attention. Given a d-dimensional hypercube (code space), equivalent covering codes of the same covering radius but of different codewords have different expected BVQ distortions for a general probability mass function. Thus one can minimize, within the code equivalence, the expected distortion over all different covering codes. This leads a two-stage optimization scheme for BVQ design. First we use an optimal covering code to minimize the maximum per-vector distortion at a given rate. Then under the minmax constraint, we minimize the expected quantization distortion. This minmax constrained BVQ method (MCBVQ) controls both the maximum and average distortions, and hence improves subjective quality of compressed binary images, MCBVQ also avoids poor local minima that may trap the generalized Lloyd method. The [7,4] Hamming code and [8,4] extended Hamming code are found to be particularly suitable for MCBVQ on binary images. An efficient and simple algorithm is introduced to enumerate all distinct [7,4] Hamming/[8,4] extended Hamming codes and compute the corresponding expected distortions in optimal MCBVQ design. Furthermore, MCBVQ using linear covering codes has a compact codebook and a fast syndrome-encoding algorithm     

An average weight-distance enumerator for binary expansions ofReed-Solomon codes

An average Hamming weight enumerator is derived for the codewords at each Hamming distance from a received pattern in the set of all possible binary expansions of a Reed-Solomon code. Since these codes may be decoded by list decoders, such as those studied by Sudan (1997), the enumerator can be used to estimate the average number of codewords in the list returned by such a decoder     

On the probability of symbol error in Viterbi decoders

An upper bound is derived on the probability that at least one of a sequence of B consecutive bits at the output of a Viterbi (1979) decoder is in error. Such a bound is useful for the analysis of concatenated coding schemes employing an outer block code over GF(2^B) (typically a Reed-Solomon (RS) code), an inner convolutional code, and a symbol (GF(2^B)) interleaver separating the two codes. The bound demonstrates that in such coding schemes a symbol interleaver is preferable to a bit interleaver. It also suggests a new criterion for good inner convolutional codes     

On maximum likelihood soft decoding of some binary self-dual codes

Efficient algorithms are derived for maximum likelihood (ML) soft-decision decoding of some binary self-dual codes. A family of easily decodable self-dual codes is derived by modifying a known F₂₄, which has a weight distribution resembling that of the [24, 12, 8] Golay code G₂₄. The ML decoding of F₂₄ is accomplished by only 227 real additions, compared to 651 required for G₂₄, yet the error rates of the two decoders are similar for moderate noise conditions     

Performance analysis and design criteria for finite-alphabet source-channel codes

Efficient compression of finite-alphabet sources requires variable-length codes (VLCs). However, in the presence of noisy channels, error propagation in the decoding of VLCs severely degrades performance. To address this problem, redundant entropy codes and iterative source-channel decoding have been suggested, but to date, neither performance bounds nor design criteria for the composite system have been available. We calculate performance bounds for the source-channel system by generalizing techniques originally developed for serial concatenated convolutional codes. Using this analysis, we demonstrate the role of a recursive structure for the inner code and the distance properties of the outer code. We use density evolution to study the convergence of our decoders. Finally, we pose the question: Under a fixed rate and complexity constraint, when should we use source-channel decoding (as opposed to separable decoding)? We offer answers in several specific cases. For our analysis and design rules, we use union bounds that are technically valid only above the cutoff rate, but interestingly, the codes designed with union-bound criteria perform well even in low signal-to-noise ratio regions, as shown by our simulations as well as previous works on concatenated codes.