Error rate estimation of low-density parity-check codes on binary symmetric channels using cycle enumeration

The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |E_J| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |E_J|, one would need to perform the direct enumeration of error patterns with weight ι ⩽ J. The complexity of enumeration increases exponentially with J, essentially as η^J, where η is the code block length. This limits the application of direct enumeration to codes with small η and J. In this letter, we approximate J and |E_J | by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.     

Iterative Decoding of Multiple-Step Majority Logic Decodable Codes

We investigate the performance of iterative decoding algorithms for multistep majority logic decodable (MSMLD) codes of intermediate length. We introduce a new bit-flipping algorithm that is able to decode these codes nearly as well as a maximum-likelihood decoder on the binary-symmetric channel. We show that MSMLD codes decoded using bit-flipping algorithms can outperform comparable Bose-Chaudhuri-Hocquenghem (BCH) codes decoded using standard algebraic decoding algorithms, at least for high bit-flip rates (or low and moderate signal-to-noise ratios (SNRs)).     

Estimation of Bit and Frame Error Rates of Finite-Length Low-Density Parity-Check Codes on Binary Symmetric Channels

A method for estimating the performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms on binary symmetric channels (BSCs) is proposed. Based on the enumeration of the smallest weight error patterns that cannot be all corrected by the decoder, this method estimates both the frame error rate (FER) and the bit error rate (BER) of a given LDPC code with very good precision for all crossover probabilities of practical interest. Through a number of examples, we show that the proposed method can be effectively applied to both regular and irregular LDPC codes and to a variety of hard-decision iterative decoding algorithms. Compared with the conventional Monte Carlo simulation, the proposed method has a much smaller computational complexity, particularly for lower error rates.     

Iteratively maximum likelihood decodable spherical codes and amethod for their construction

The authors propose a class of spherical codes which can be easily decoded by an efficient iterative maximum likelihood decoding algorithm. A necessary and sufficient condition for a spherical code to be iteratively maximum likelihood decodable is formulated. A systematic construction method for such codes based on shrinking of Voronoi corners is analyzed. The base code used for construction is the binary maximal length sequence code. The second-level construction is described. Computer simulation results for selected codes constructed by the proposed method are given     

Decoder error and failure probabilities for Reed-Solomon codes:decodable vectors method

In this letter, formulas for the total number of decodable and undecodable vectors are derived for a general (n,k) q-ary linear block code. These formulas are used to find the probabilities of decoder error and decoder failure for Reed-Solomon codes under errors-and-erasures decoding. The resulting analytical expressions are computationally efficient and allow accurate calculation of very small values of decoder failure probabilities. The formulas are used to analyze the performance of type-I hybrid automatic-repeat-request (HARQ) protocols with two decoding diameters     

Decoding spherical codes for the Gaussian channel

A decoding algorithm for permutation codes that is equivalent to maximum-likelihood decoding, but less complex than the correlation decoder, is presented. A general construction for iteratively maximum-likelihood decodable (IMLD) codes is proved and used to construct IMLD codes for every dimension n. D. Slepian (1965) defined permutation modulation codes and presented an efficient algorithm for their decoding. Slepian's decoding scheme is one of the principal components of the permutation code decoding algorithm presented     

Two-dimensional Fire codes

To improve the reliability of two-dimensional information, codes that can correct two-dimensional bursts (or spots) may be useful. In this paper a class of two-dimensional burst-correcting codes, called two-dimensional Fire codes, is proposed. The definition of these codes is a natural extension of that of the conventional Fire codes. The two-dimensional Fire code is a two-dimensional cyclic code designed for single two-dimensional burst correction. Several important properties such as the burst-correcting capability and the positions of the check symbols are presented. Also, encoding and decoding methods are presented. It is shown that the encoding and decoding are easily implemented by using two-dimensional feedback shift registers.     

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     

Construction of Constrained Codes for State-Independent Decoding

Constrained sequence codes are widely used to meet constraints imposed by digital storage and communication systems. This paper develops an algorithm for the construction of constrained codes that admit state-independent decoding. By partitioning the code into a group of alphabets, one for each state, a codebook is developed using this algorithm that will allow the code to be decoded at the receiver without the need for state information. Finally, we use this algorithm to construct DCfree runlength-limited (RLL) codes, and we present two highly efficient state-independent decodable DC-free RLL codes.     

On the application of approximate APP decoding to digital videotransmission

For transmitting compressed digital video, the authors propose using threshold decodable block codes with large block length, and a posteriori probability (APP) soft decision decoding. A new approximation of the weight function associated with APP soft decision decoding of threshold decodable codes is presented. When the number of components in the parity equations is large, the new method gives excellent error performance, whereas there is a substantial degradation in the performance of the least reliable symbol approximation presented by Tanaka et al. (1980) and others. The effect of feedback on the performance of the APP decoder is also analyzed. It is shown that if the performance criterion is word error rate rather than bit error rate, feedback of previously decoded bits is essential to obtain all possible coding gain from the soft decision decoder. Finally, the performance of the proposed coding scheme is compared to the performance of a concatenated coding system with the same rate     

循环汉明码编译码器的设计与FPGA实现

分析了循环码的特性,提出一种循环汉明码编译码器的设计方案。编译码器中编码采用除法电路,译码采用梅吉特译码器,易于工程应用。对编译码器在FPGA上进行了实现,通过参数化设置,具有较高的码率,适用于(255,247)及其任意缩短码的循环汉明码,并给出了译码器的仿真和测试结果。结果表明:编译码器运行速率高、译码时延小,在Virtex-5芯片上,最高工作时钟频率大于270 MHz。在码组错误个数确定的系统应用中,可以有效降低误码率,一般可将误码率降低一个量级。实践表明,该设计具有很强的工程实用价值。     

High-rate burst-error-correcting recurrent codes (Corresp.)

A bound and construction are presented for high-rate burst-error-correcting recurrent codes. The bound is an upper bound on the block length in terms of the total redundancy used in decoding, the redundancy per block, and the burst length. The construction uses a block-code parity-check matrix as the first block of the recurrent code parity-check matrix. For a block code it is typical to find that only a portion of the redundancy need be used to detect a burst. Any block code for which this is true can be used in the construction. The recurrent code is then related as follows to the block code from which it is constructed. 1) The recurrent code block length is the same as the block-code block length. 2) The total redundancy used in decoding the recurrent code is the same as the block-code redundancy per block. 3) The recurrent code redundancy per block is the same as the block-code redundancy required for burst detection only. 4) The recurrent code is of higher rate than the block code. 5) The recurrent code requires a guard space between bursts but otherwise corrects the same bursts as the block code. It is shown that, when certain well-known cyclic codes are used in the construction, the resulting recurrent codes are close to the upper bound.     

Collaborative Decoding of Interleaved Reed–Solomon Codes and Concatenated Code Designs

Interleaved Reed-Solomon codes are applied in numerous data processing, data transmission, and data storage systems. They are generated by interleaving several codewords of ordinary Reed-Solomon codes. Usually, these codewords are decoded independently by classical algebraic decoding methods. However, by collaborative algebraic decoding approaches, such interleaved schemes allow the correction of error patterns beyond half the minimum distance, provided that the errors in the received signal occur in bursts. In this work, collaborative decoding of interleaved Reed-Solomon codes by multisequence shift-register synthesis is considered and analyzed. Based on the framework of interleaved Reed-Solomon codes, concatenated code designs are investigated, which are obtained by interleaving several Reed-Solomon codes, and concatenating them with an inner code.     

On the construction of a class of majority-logic decodable codes

The attractiveness of majority-logic decoding is its simple implementation. Several classes of majority-logic decodable block codes have been discovered for the past two decades. In this paper, a method of constructing a new class of majority-logic decodable block codes is presented. Each code in this class is formed by combining majority-logic decodable codes of shorter lengths. A procedure for orthogonalizing codes of this class is formulated. For each code, a lower bound on the number of correctable errors with majority-logic decoding is obtained. An upper bound on the number of orthogonalization steps for decoding each code is derived. Several majority-logic decodable codes that have more information digits than the Reed-Muller codes of the same length and the same minimum distance are found. Some results presented in this paper are extensions of the results of Lin and Weldon [11] and Gore [12] on the majority-logic decoding of direct product codes.     

On type-B1 burst-error-correcting convolutional codes

Two new classes of type-B1 burst-error-correcting convolutional codes are introduced. One of them requires a shorter length of guard space and a smaller number of shift register stages than optimum type-B2 codes used for type-B1 burst correction. Another class of codes improves the required number of shift register stages considerably when the correctable burst length is very large. In addition, these codes require a very short length of additional guard space to restore the decoder to correct operation after a decoding failure. Both classes of codes are derived in a straightforward manner and their implementations are also very simple. Thus, we can avoid type-B2 code procedures to correct type-B1 bursts. The codes derived here result in the more efficient and simply implemented type-B1 burst-correcting convolutional codes.     

Bit error probability calculations for convolutional codes withshort constraint lengths on very noisy channels

A technique for estimating convolutional code performance on very noisy channels is considered. Specifically, the performance of short constraint length codes operating near the channel cutoff rate is estimated. Decoding convolutional codes with a sliding window decoder (SWD) are considered. This decoder is an optimal (maximum likelihood) symbol decoder as the window size grows toward infinity, while the Viterbi decoder is the maximum-likelihood sequence estimator. The difference in the decoded BERs (bit error rates) between the two decoders is very small and approaches zero asymptotically as the channel BER decreases. Therefore, an estimate on the decoded BER for the SWD can also be used as an estimate of the decoded BER for Viterbi decoding     

Multiple-bases belief-propagation decoding of high-density cyclic codes

We introduce a new method for decoding short and moderate-length linear block codes with dense paritycheck matrix representations of cyclic form. This approach is termed multiple-bases belief-propagation. The proposed iterative scheme makes use of the fact that a code has many structurally diverse parity-check matrices, capable of detecting different error patterns. We show that this inherent code property leads to decoding algorithms with significantly better performance when compared to standard belief-propagation decoding. Furthermore, we describe how to choose sets of parity-check matrices of cyclic form amenable for multiple-bases decoding, based on analytical studies performed for the binary erasure channel. For several cyclic and extended cyclic codes, the multiple-bases belief propagation decoding performance can be shown to closely follow that of the maximum-likelihood decoder.     

Variants of decoding of unsystematic cyclic codes

It is considered two variants of syndrome decoding of unsystematic cyclic codes with decoding errors correction for output symbols of decoder, which is recursive or non-recursive filter of decoded coding symbols.     

Algebraic Decoding of the $(89, 45, 17)$ Quadratic Residue Code

Recently, an algebraic decoding algorithm suggested by Truong (2005) for some quadratic residue codes with irreducible generating polynomials has been designed that uses the inverse-free Berlekamp–Massey (BM) algorithm to determine the error-locator polynomial. In this paper, based on the ideas of the algorithm mentioned above, an algebraic decoder for the $(89, 45, 17)$ binary quadratic residue code, the last one not decoded yet of length less than $100$ , is proposed. It was also verified theoretically for all error patterns within the error-correcting capacity of the code. Moreover, the verification method developed in this paper can be extended for all cyclic codes without checking all error patterns by computer simulations.      

Reed-Solomon codes for correcting phased error bursts

A code structure is introduced that represents a Reed-Solomon (RS) code in two-dimensional format. Based on this structure, a novel approach to multiple error burst correction using RS codes is proposed. For a model of phased error bursts, where each burst can affect one of the columns in a two-dimensional transmitted word, it is shown that the bursts can be corrected using a known multisequence shift-register synthesis algorithm. It is further shown that the resulting codes posses nearly optimal burst correction capability, under certain probability of decoding failure. Finally, low-complexity systematic encoding and syndrome computation algorithms for these codes are discussed. The proposed scheme may also find use in decoding of different coding schemes based on RS codes, such as product or concatenated codes.