A coded ARQ scheme with the generalized Viterbi algorithm

A coded automatic repeat request (ARQ) scheme based on a generalized Viterbi decoding algorithm is proposed. The scheme utilizes the error propagation, which is commonly observed in reduced-complexity decoding, as a means of error detection. It is shown that a small undetectable error probability is obtained with a small retransmission probability for a discrete memoryless channel, contrary to the conventional convolutionally coded ARQ schemes with Viterbi decoding where a compromise between the retransmission probability and the undetectable error probability must be reached     

Comparison of decoding algorithms of binary linear block codes inRayleigh fading channels with diversity reception

The word error probability of binary linear block codes is evaluated in Rayleigh fading channels with diversity reception for three decoding algorithms: error correction (EC), error/erasure correction (EEC), and maximum likelihood (ML) soft decoding algorithms. The performance advantage of EEC over EC in the required average SNR decreases as the number of diversity channels increases. The performance advantage of EEC over EC does not depend on the specific value of word error probability although the advantage of ML soft decoding over EC increases for lower word error probability     

Sequential decoding of systematic and nonsystematic convolutional codes with arbitrary decoder bias

This paper presents several results involving Fano's sequential decoding algorithm for convolutional codes. An upper bound to theath moment of decoder computation is obtained for arbitrary decoder biasBanda leq 1. An upper bound on error probability with sequential decoding is derived for both systematic and nonsystematic convolutional codes. This error bound involves the exact value of the decoder biasB. It is shown that there is a trade-off between sequential decoder computation and error probability as the biasBis varied. It is also shown that for many values ofB, sequential decoding of systematic convolutional codes gives an exponentially larger error probability than sequential decoding of nonsystematic convolutional codes when both codes are designed with exponentially equal optimum decoder error probabilities.     

An analysis of sequential decoding for specific time-invariant convolutional codes

A new analysis of the computational effort and the error probability of sequential decoding is presented, which is based entirely on the distance properties of a particular convolutional code and employs no random-coding arguments. An upper bound on the computational distributionP(C_{t}>N_{t})for a specific time-invariant code is derived, which decreases exponentially with the column distance of the code. It is proved that rapid column-distance growth minimizes the decoding effort and therefore also the probability of decoding failure or erasure. In an analogous way, the undetected error probability of sequential decoding with a particular fixed code is proved to decrease exponentially with the free distance and to increase linearly with the number of minimum free-weight codewords. This analysis proves that code construction for sequential decoding should maximize column-distance growth and free distance in order to guarantee fast decoding, a minimum erasure probability, and a low undetected error probability.     

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     

Estimation of the exponent of the decoding error probability for a special generalized LDPC code

A special construction of a generalized low-density parity-check (LDPC) code and a low-complexity algorithm for his code decoding are proposed. A lower estimate of the exponent of the decoding error probability is obtained for the considered code and the decoding algorithm. This estimate leads the conclusion that, in an ensemble of considered LDPC codes, there are codes with rates as high as the code capacity and the exponent of the decoding error probability exceeds zero.     

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.     

Error Exponents for Recursive Decoding of Reed–Muller Codes on a Binary-Symmetric Channel

Error exponents are studied for recursive decoding of Reed-Muller (RM) codes and their subcodes used on a binary-symmetric channel. The decoding process is first decomposed into similar steps, with one new information bit derived in each step. Multiple recursive additions and multiplications of the randomly corrupted channel outputs plusmn1 are performed using a specific order of these two operations in each step. Recalculated random outputs are compared in terms of their exponential moments. As a result, tight analytical bounds are obtained for decoding error probability of the two recursive algorithms considered in the paper. For both algorithms, the derived error exponents almost coincide with simulation results. Comparison of these bounds with similar bounds for bounded distance decoding and majority decoding shows that recursive decoding can reduce the output error probability of the latter two algorithms by five or more orders of magnitude even on the short block length of 256. It is also proven that the error probability of recursive decoding can be exponentially reduced by eliminating one or a few information bits from the original RM code     

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     

Universal decoding for finite-state channels

Universal decoding procedures for finite-state channels are discussed. Although the channel statistics are not known, universal decoding can achieve an error probability with an error exponent that, for large enough block length (or constraint length in case of convolutional codes), is equal to the random-coding error exponent associated with the optimal maximum-likelihood decoding procedure for the given channel. The same approach is applied to sequential decoding, yielding a universal sequential decoding procedure with a cutoff rate and an error exponent that are equal to those achieved by the classical sequential decoding procedure.     

Error probability and free distance bounds for two-user tree codes on multiple-access channels

Two-user tree codes are considered for use on an arbitrary two-user discrete memoryless multiple-access channel (MAC). A two-user tree Is employed to achieve true maximum likelihood (ML) decoding of two-user tree codes on MAC's. Each decoding error event has associated with it a configuration indicating the specific time slots in which a decoding error has occurred for the first user alone, for the second user alone, or for both users simultaneously. Even though there are many possible configurations, it is shown that there are five fundamental configuration types. An upper bound on decoding error probability, similar to Liao's result for two-user block codes, is derived for sets of error events having a particular configuration. The total ML decoding error probability is bounded using a union bound first over all configurations of a given type and then over the five configuration types. A two-user tree coding error exponent is defined and compared with the corresponding block coding result for a specific MAC. It is seen that the tree coding error exponent is larger than the block coding error exponent at all rate pairs within the two-user capacity region. Finally, a new lower bound on free distance for two-user codes is derived using the same general technique used to bound the error probability.     

Asymptotically optimal soft decision decoding algorithms for Hamming codes

Asymptotically optimal soft decision decoding algorithms for d = 3 and d = 4 Hamming codes are given and analysed. Only error sequences with probability exponent larger than that of maximum-likelihood decoding are corrected. Upper bounds on the block error probability for the Gaussian channel are given.     

Theoretical analysis of the error correction performance ofmajority-logic-like vector symbol codes

The average codeword success probability of the majority-logic-like vector symbol (MLLVS) code is derived for the following two cases: (1) single-pass decoding and (2) upper bound of multipass decoding, when the received word has more than (J-1) symbol errors, where J is the number of check sum equations. The MLLVS code has been simulated by Metzner (1996), and it was concluded that the average error correcting capability of MLLVS codes exceed the decoding capability of Reed-Solomon codes, but is achieved with less complexity. Additionally, for codes that have larger structures, the error correcting capability is sustained even further with a high probability of decoding success through multipass decoding procedures. The mathematical derivations of the error correction performance beyond (J-1) symbol errors serve as theoretical proof of the MLLVS code error correcting capability that was shown only through simulation results until now by Metzner. One characteristic feature of this derivation is that it does not assume any specific inner code usage, enabling the derived decoding probability equations to be easily applied to any inner code selected, of a concatenated coding structure     

A new probability decoding scheme based on genetic algorithm for FEC codes in optical transmission systems

Based on the genetic algorithm(GA),a new genetic probability decoding(GPD) scheme for forward error correction(FEC) codes in optical transmission systems is proposed.The GPD scheme can further offset the quantification error of the hard decision by making use of the channel interference probability and statistics information to restore the maximal likelihood transmission code word.The theoretical performance analysis and the simulation result show that the proposed GPD scheme has the advantages of lower decoding complexity,faster decoding speed and better decoding correction-error performance.Therefore,the proposed GPD algorithm is a better practical decoding algorithm.     

Generalized minimum distance decoding

We introduce a new distance measure which permits likelihood information to be used in algebraic minimum distance decoding techniques. We give an efficient decoding algorithm, and develop exponential bounds on the probability of not decoding correctly. In one application, this technique yields the same probability of error as maximum likelihood decoding.     

Bounds on the maximum-likelihood decoding error probability oflow-density parity-check codes

We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent     

An algorithm for calculating the exact bit error probability of a binary linear code over the binary symmetric channel

An efficient algorithm for calculating the ith bit error probability of a binary linear code over the binary symmetric channel (BSC) is presented. It is proved that the exact ith bit error probability of maximum-likelihood (ML) decoding, bounded distance decoding, and symbol-wise maximum a posteriori probability (MAP) decoding can be obtained with time complexity O(n2/sup n-k/), where n and k denote the length and the dimension of the target code. The proposed methods are applicable to any binary linear code with redundancy up to nearly 25-30 bits with a typical personal computer.     

Improved Analysis of List Decoding and Its Application to Convolutional Codes and Turbo Codes

A list decoder generates a list of more than one codeword candidates, and decoding is erroneous if the transmitted codeword is not included in the list. This decoding strategy can be implemented in a system that employs an inner error correcting code and an outer error detecting code that is used to choose the correct codeword from the list. Probability of codeword error analysis for a linear block code with list decoding is typically based on the "worst case" lower bound on the effective weights of codewords for list decoding evaluated from the weight enumerating function of the code. In this paper, the concepts of generalized pairwise error event and effective weight enumerating function are proposed for evaluation of the probability of codeword error of linear block codes with list decoding. Geometrical analysis shows that the effective Euclidean distances are not necessarily as low as those predicted by the lower bound. An approach to evaluate the effective weight enumerating function of a particular code with list decoding is proposed. The effective Euclidean distances for decisions in each pairwise error event are evaluated taking into consideration the actual Hamming distance relationships between codewords, which relaxes the pessimistic assumptions upon which the traditional lower bound analysis is based. Using the effective weight enumerating function, a more accurate approximation is achieved for the probability of codeword error of the code with list decoding. The proposed approach is applied to codes of practical interest, including terminated convolutional codes and turbo codes with the parallel concatenation structure     

失真补偿量化索引调制水印的性能分析

该文分析了基于量化索引调制的失真补偿水印方案中量化步长的伸缩因子与失真度、鲁棒性和检测误码率之间的关系。在高分辨率量化的假设前提下,推导出失真补偿量化索引调制水印算法在加性高斯白噪声信道下的误码率计算公式,并提出了一个失真-鲁棒性函数来度量算法的抗噪鲁棒性和失真度与鲁棒性之间的代价关系。通过计算机仿真,比较了不同失真补偿量化索引调制水印方案下算法的失真-鲁棒性能和误码率性能;并以一段音频数据三级小波细节系数为载体嵌入水印信息,统计检测时的位错误率。实验结果验证了在低量化步长范围内,理论预测误码率与实验检测误码率较为吻合,失真-鲁棒性函数能够很好地度量高分辨率量化前提下的算法抗噪鲁棒性和失真度与鲁棒性之间的代价关系。     

Performance evaluation of low-density parity-check codes on partial-response channels using density evolution

A method to evaluate the performance of a low-density parity-check (LDPC) code on partial-response (PR) channels in terms of the noise threshold and decoding error is presented. Given a particular codeword or assuming an independent and uniformly distributed (i.u.d.) codeword for transmission, the density-evolution algorithm is used to compute the probability density function of messages passing in the decoding process, from which the decoding error is extracted. This estimated i.u.d. decoding error is used to approximate the decoding error of an ensemble of LDPC codes on arbitrary PR channels. Comparison with simulation results shows that it is a very good approximation for the simulated codes, provided their length is large enough.