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.     

The serial concatenation of rate-1 codes through uniform random interleavers

Until the analysis of repeat accumulate codes by Divsalar et al. (1998), few people would have guessed that simple rate-1 codes could play a crucial role in the construction of "good" binary codes. We construct "good" binary linear block codes at any rate r<1 by serially concatenating an arbitrary outer code of rate r with a large number of rate-1 inner codes through uniform random interleavers. We derive the average output weight enumerator (WE) for this ensemble in the limit as the number of inner codes goes to infinity. Using a probabilistic upper bound on the minimum distance, we prove that long codes from this ensemble will achieve the Gilbert-Varshamov (1952) bound with high probability. Numerical evaluation of the minimum distance shows that the asymptotic bound can be achieved with a small number of inner codes. In essence, this construction produces codes with good distance properties which are also compatible with iterative "turbo" style decoding. For selected codes, we also present bounds on the probability of maximum-likelihood decoding (MLD) error and simulation results for the probability of iterative decoding error.     

Decoding of Expander Codes at Rates Close to Capacity

The decoding error probability of codes is studied as a function of their block length. It is shown that the existence of codes with a polynomially small decoding error probability implies the existence of codes with an exponentially small decoding error probability. Specifically, it is assumed that there exists a family of codes of length N and rate R=(1-epsiv)C (C is a capacity of a binary-symmetric channel), whose decoding probability decreases inverse polynomially in N. It is shown that if the decoding probability decreases sufficiently fast, but still only inverse polynomially fast in N, then there exists another such family of codes whose decoding error probability decreases exponentially fast in N. Moreover, if the decoding time complexity of the assumed family of codes is polynomial in N and 1/epsiv, then the decoding time complexity of the presented family is linear in N and polynomial in 1/epsiv. These codes are compared to the recently presented codes of Barg and Zemor, "Error Exponents of Expander Codes", IEEE Transactions on Information Theory, 2002, and "Concatenated Codes: Serial and Parallel", IEEE Transactions on Information Theory, 2005. It is shown that the latter families cannot be tuned to have exponentially decaying (in N) error probability, and at the same time to have decoding time complexity linear in N and polynomial in 1/epsiv     

An analysis of the block error probability performance of iterative decoding

Asymptotic iterative decoding performance is analyzed for several classes of iteratively decodable codes when the block length of the codes N and the number of iterations I go to infinity. Three classes of codes are considered. These are Gallager's regular low-density parity-check (LDPC) codes, Tanner's generalized LDPC (GLDPC) codes, and the turbo codes due to Berrou et al. It is proved that there exist codes in these classes and iterative decoding algorithms for these codes for which not only the bit error probability P/sub b/, but also the block (frame) error probability P/sub B/, goes to zero as N and I go to infinity.     

Non-sequential decoding algorithm for hard iterative turbo product codes - [transactions letters]

In this letter, we propose a new decoding algorithm to improve the bit error rate performance of the hard-input hard-output (HIHO) turbo product codes (TPC) with hard iterative decoding. The proposed algorithm iteratively, but not sequentially, decodes the received TPC blocks based on the reliability of the constituent codes. Simulation results confirm a noticeable coding gain improvement using the proposed decoding process with respect to standard HIHO TPC decoding. An efficient implementation of the new technique offers a negligible additional complexity when the channel-bit error probability is less than 10^?2.     

Truncation Error Probability in Viterbi Decoding

An upper bound on the bit error probability due to truncation of the path length in Viterbi decoding is obtained for any given convolutional code. This bound is then used to determine the path length at which the additional error probability due to truncation becomes negligible compared to the maximum likelihood decoding error probability. These results are tested by simulation using several short constraint length codes.     

Turbo码概率-代数联合解码算法

Turbo码采用修正的BAHL et al.算法实现解码.这是一种基于软值的概率迭代解码算法.本文在保持Turbo码迭代软解码算法优点的基础上,充分利用Turbo码编码器结构这一确知条件,结合代数解码原理,提出了一种Turbo码概率-代数联合解码算法.该算法结合了概率解码和代数解码的优点,又有效避免了误差传播的发生,使Turbo码的纠错性能在原经典算法的基础上得到进一步的提高.该算法不仅为降低Turbo码的比特误码率和误差地板值提供了一种新的研究途径,而且因其更好的纠错性能而具有十分明显的实用价值.仿真实验结果显示,在比特误码率(BER)为10^-3~10^-4时,与经典Turbo码解码算法相比,采用该算法能获得0.1dB左右的编码增益.     

Word error rate for group codes detected by correlation and other means

General expressions for the probability of word error for several encoding/detection schemes using group codes are derived. Correlation detection, digital decoding, straight Wagner codes, "Wagnerized" codes, and direct transmission are covered. Specific results are given for each in the case where the additive channel noise is white and Gaussian. A good indication of the relative amounts of power required by two schemes operating at the same error rate is available from an asymptotic relationship as the signal-to-noise ratio approaches infinity. Numerical results are presented for three easily implemented codes.     

On the complexity of minimum distance decoding of long linear codes

We suggest a decoding algorithm of q-ary linear codes, which we call supercode decoding. It ensures the error probability that approaches the error probability of minimum-distance decoding as the length of the code grows. For n→∞ the algorithm has the maximum-likelihood performance. The asymptotic complexity of supercode decoding is exponentially smaller than the complexity of all other methods known. The algorithm develops the ideas of covering-set decoding and split syndrome decoding     

Variable-bit-rate speech transmission using punctured convolutionalcodes

Rate (n-1)/n punctured convolutional codes are very effective in conjunction with embedded differential pulse code modulation (EDPCM) in variable-bit-rate speech transmission. The authors investigate the performance of this variable-bit-rate EDPCM system in terms of probability of bit error and audio signal-to-noise ratio (SNR) versus channel SNR in an additive white Gaussian noise and Rayleigh fading channel using soft-decision decoding for specific sets of code generators of punctured convolutional codes. The results show that different sets of code generators affect the performance in terms of both the probability of bit error and the audio SNR. Improvements were obtained in the cases of Gaussian nonfading and Rayleigh fading channels using soft-decision decoding     

Rateless Codes With Unequal Error Protection Property

In this correspondence, a generalization of rateless codes is proposed. The proposed codes provide unequal error protection (UEP). The asymptotic properties of these codes under the iterative decoding are investigated. Moreover, upper and lower bounds on maximum-likelihood (ML) decoding error probabilities of finite-length LT and Raptor codes for both equal and unequal error protection schemes are derived. Further, our work is verified with simulations. Simulation results indicate that the proposed codes provide desirable UEP. We also note that the UEP property does not impose a considerable drawback on the overall performance of the codes. Moreover, we discuss that the proposed codes can provide unequal recovery time (URT). This means that given a target bit error rate, different parts of information bits can be decoded after receiving different amounts of encoded bits. This implies that the information bits can be recovered in a progressive manner. This URT property may be used for sequential data recovery in video/audio streaming     

On the performance of rate 1/2 convolutional codes with QPSK onRician fading channels

Consideration is given to the bit error probability performance of rate 1/2 convolutional codes in conjunction with quaternary phase shift keying (QPSK) modulation and maximum-likelihood Viterbi decoding on fully interleaved Rician fading channels. Applying the generating function union bounding approach, an asymptotically tight analytic upper bound on the bit error probability performance is developed under the assumption of using the Viterbi decoder with perfect fading amplitude measurement. Bit error probability performance of constraint length K=3-7 codes with QPSK is numerically evaluated using the developed bound. Tightness of the bound is examined by means of computer simulation. The influence of perfect amplitude measurement on the performance of the Viterbi decoder is observed. A performance comparison with rate 1/2 codes with binary phase shift keying (BPSK) is provided     

Waterfall performance analysis of finite-length LDPC codes on symmetric channels

An efficient method for analyzing the performance of finite-length low-density parity-check (LDPC) codes in the waterfall region, when transmission takes place on a memoryless binary-input output-symmetric channel is proposed. This method is based on studying the variations of the channel quality around its expected value when observed during the transmission of a finite-length codeword. We model these variations with a single parameter. This parameter is then viewed as a random variable and its probability distribution function is obtained. Assuming that a decoding failure is the result of an observed channel worse than the code?s decoding threshold, the block error probability of finite-length LDPC codes under different decoding algorithms is estimated. Using an extrinsic information transfer chart analysis, the bit error probability is obtained from the block error probability. Different parameters can be used for modeling the channel variations. In this work, two of such parameters are studied. Through examples, it is shown that this method can closely predict the performance of LDPC codes of a few thousand bits or longer in the waterfall region.     

Lowering Error Floor of LDPC Codes Using an Improved Parallel WBF Algorithm

In weighted bit‐flipping‐based algorithms for low‐density parity‐check (LDPC) codes, due to the existence of overconfident incorrectly received bits, the metric values of the corresponding bits will always be wrong in the decoding process. Since these bits cannot be flipped, decoding failure results. To solve this problem, an improved parallel weighted bit flipping algorithm is proposed. Specifically, a reliability‐saturation strategy is adopted to increase the flipping probability of the overconfident incorrectly received bits. Simulation results show that the error floor of LDPC codes is greatly lowered.     

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     

Free distance bounds for convolutional codes

The best asymptotic bounds presently known on free distance for convolutional codes are presented from a unified point of view. Upper and lower bounds for both time-varying and fixed codes are obtained. A comparison is made between bounds for nonsystematic and systematic codes which shows that more free distance is available with nonsystematic codes. This result is important when selecting codes for use with sequential or maximum-likelihood (Viterbi) decoding since the probability of decoding error is closely related to the free distance of the code. An ancillary result, used in proving the lower bound on free distance for time-varying nonsystematic codes, furnishes a generalization of two earlier bounds on the definite decoding minimum distance of convolutional codes.     

Tightened Upper Bounds on the ML Decoding Error Probability of Binary Linear Block Codes

The performance of maximum-likelihood (ML) decoded binary linear block codes is addressed via the derivation of tightened upper bounds on their decoding error probability. The upper bounds on the block and bit error probabilities are valid for any memoryless, binary-input and output-symmetric communication channel, and their effectiveness is exemplified for various ensembles of turbo-like codes over the additive white Gaussian noise (AWGN) channel. An expurgation of the distance spectrum of binary linear block codes further tightens the resulting upper bounds     

DSD (double soft decision) concatenated FEC scheme in mobilesatellite communication systems

In order to realize a higher-code-gain forward error correction scheme in mobile satellite communication systems, a novel concatenated coding scheme employing soft decision decoding for not only inner codes but also outer codes (double soft decision, or DSD, concatenated forward error correction scheme) is proposed. Soft-decision outer decoding can improve the bit error probability of inner decoded data. In this scheme, likelihood information from an inner Viterbi decoder is used in the decoding of outer codes. A technique using the path memory circuit status 1.0 ratio for likelihood information is proposed, and is shown to be the most reliable even though it requires the simplest hardware among the alternative methods. A computer simulation clarifies that the DSD scheme improves Pe performance to one-third of that of the conventional hard-decision outer decoding. Moreover, to reduce the interleaving delay time in fading channels or inner decoded data of concatenated codes, a parallel forward error correction scheme is proposed     

Coding for Parallel Channels: Gallager Bounds and Applications to Turbo-Like Codes

The transmission of coded communication systems is widely modeled to take place over a set of parallel channels. This model is used for transmission over block-fading channels, rate-compatible puncturing of turbo-like codes, multicarrier signaling, multilevel coding, etc. New upper bounds on the maximum-likelihood (ML) decoding error probability are derived in the parallel-channel setting. We focus on the generalization of the Gallager-type bounds and discuss the connections between some versions of these bounds. The tightness of these bounds for parallel channels is exemplified for structured ensembles of turbo codes, repeat-accumulate (RA) codes, and some of their recent variations (e.g., punctured accumulate-repeat-accumulate codes). The bounds on the decoding error probability of an ML decoder are compared to computer simulations of iterative decoding. The new bounds show a remarkable improvement over the union bound and some other previously reported bounds for independent parallel channels. This improvement is exemplified for relatively short block lengths, and it is pronounced when the block length is increased. In the asymptotic case, where we let the block length tend to infinity, inner bounds on the attainable channel regions of modern coding techniques under ML decoding are obtained, based solely on the asymptotic growth rates of the average distance spectra of these code ensembles.     

一种基于之型分量码的系统GLDPC码

本文以规则低密度生成矩阵码为基础,构建了一种以之型码为分量码的系统广义低密度奇偶校验(Generalized Low-Density Parity-Check,GLDPC)码,称为ZS-GLDPC码.该码具有线性编码复杂度,可采用和积译码算法实现迭代译码,其译码复杂度低于以汉明码为分量码的GLDPC码.在均匀交织器的前...