Soft-Output BEAST Decoding With Application to Product Codes

A Bidirectional Efficient Algorithm for Searching code Trees (BEAST) is proposed for efficient soft-output decoding of block codes and concatenated block codes. BEAST operates on trees corresponding to the minimal trellis of a block code and finds a list of the most probable codewords. The complexity of the BEAST search is significantly lower than the complexity of trellis-based algorithms, such as the Viterbi algorithm and its list generalizations. The outputs of BEAST, a list of best codewords and their metrics, are used to obtain approximate a posteriori probabilities (APPs) of the transmitted symbols, yielding a soft-input soft-output (SISO) symbol decoder referred to as the BEAST-APP decoder. This decoder is employed as a component decoder in iterative schemes for decoding of product and incomplete product codes. Its performance and convergence behavior are investigated using extrinsic information transfer (EXIT) charts and compared to existing decoding schemes. It is shown that the BEAST-APP decoder achieves performances close to the Bahl–Cocke–Jelinek–Raviv (BCJR) decoder with a substantially lower computational complexity.      

Multiple-symbol parallel decoding for variable length codes

In this paper, a multiple-symbol parallel variable length decoding (VLD) scheme is introduced. The scheme is capable of decoding all the codewords in an N-bit block of encoded input data stream. The proposed method partially breaks the recursive dependency related to the VLD. First, all possible codewords in the block are detected in parallel and lengths are returned. The procedure results redundant number of codeword lengths from which incorrect values are removed by recursive selection. Next, the index for each symbol corresponding the detected codeword is generated from the length determining the page and the partial codeword defining the offset in symbol table. The symbol lookup can be performed independently from symbol table. Finally, the sum of the valid codeword lengths is provided to an external shifter aligning the encoded input stream for a new decoding cycle. In order to prove feasibility and determine the limiting factors of our proposal, the variable length decoder has been implemented on an field-programmable gate-array (FPGA) technology. When applied to MPEG-2 standard benchmark scenes, on average 4.8 codewords are decoded per cycle resulting in the throughput of 106 million symbols per second.     

Symbol-by-symbol MAP decoding algorithm for high-rate convolutionalcodes that use reciprocal dual codes

A symbol-by-symbol maximum a posteriori (MAP) decoding algorithm for high-rate convolutional codes applying reciprocal dual convolutional codes is presented. The advantage of this approach is a reduction of the computational complexity since the number of codewords to consider is decreased. All requirements for iterative decoding schemes are fulfilled. Since tail-biting convolutional codes are equivalent to quasi-cyclic block codes, the decoding algorithm for truncated or terminated convolutional codes is modified to obtain a soft-in/soft-out decoder for high-rate quasi-cyclic block codes which also uses the dual code because of complexity reasons. Additionally, quasi-cyclic block codes are investigated as component codes for parallel concatenation. Simulation results obtained by iterative decoding are compared with union bounds for maximum likelihood decoding. The results of a search for high-rate quasi-cyclic block codes are given in the appendix     

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.     

An efficient hybrid decoding algorithm for Reed-Solomon codes based on bit reliability

The paper presents a computationally efficient hybrid reliability-based decoding algorithm for Reed-Solomon (RS) codes. This hybrid decoding algorithm consists of two major components, a re-encoding process and a successive erasure-and-error decoding process for both bit and symbol levels. The re-encoding process is to generate a sequence of candidate codewords based on the information provided by the codeword decoded by an algebraic decoder and a set of test error patterns. Two criteria are used for testing in the decoding process to reduce the decoding computational complexity. The first criterion is devised to reduce the number of re-encoding operations by eliminating the unlikely error patterns. The second criterion is to test the optimality of a generated candidate codeword. Numerical results show that the proposed decoding algorithm can achieve either a near-optimum error performance or an asymptotically optimum error performance.     

Distance based adaptive scaling in suboptimal iterative decoding

This article develops an alternative adaptive iterative Chase (1972) based decoding algorithm for block turbo/product codes. The decoder considers only a small subset of codewords, so that estimates of the extrinsic information are required in some cases. This article develops such an estimate based on code distance properties     

On Rudolph's majority-logic decoding algorithm (Corresp.)

In this correspondence, a modification of Rudolph's one-step majority-logic decoding algorithm is introduced. Using this modification, it is proved that all single-error-correcting codes can be one-step majority decoded.     

A decoding procedure for multiple-error-correcting cyclic codes

A decoding procedure for multiple-error-correcting cyclic codes is described. This method is very simple in principle and the mechanization is easy for short codes with relatively high redundancy. Applications are made to the cyclic Golay code, the Bose-Chaudhuri(63, 45), (31, 16), (31, 11)codes and the(41, 21)cyclic codes. A block diagram for a decoder for the Golay code is shown.     

One-step majority-logic decoding with symbol reliability information (Corresp.)

A method of using reliability information in one-step majority-logic decoders is presented. The idea is, basically, that the received binary digits are corrected in an order such that the least reliable digit is first corrected. With this method the error correction capability of the decoder is extended for large signal-to-noise ratios (SNR's). Different decoding algorithms are used when the number of orthogonal parity-check sums are even and odd, respectively. Computer simulations are presented for some short codes with binary antipodal signals on the additive white Gaussian noise channel.     

A simple taboo-based soft-decision decoding algorithm for expandercodes

We present a simple soft-decision decoding algorithm that modifies Sipser and Spielman's (see IEEE Trans, Inform. Theory, vol.42, p.1710-22, Nov. 1996) hard-decision sequential “bit-flipping” algorithm for decoding expander codes. The algorithm incorporates symbol reliability information and a simple “taboo” function that avoids repeated flipping of the same bit. The two algorithms have comparable simplicity, but simulations show that the soft-decision algorithm results in both improved performance and-because fewer decoding iterations are necessary-improved speed     

Majority-logic-like vector symbol decoding with alternative symbolvalue lists

Majority-logic-like decoding is an outer concatenated code decoding technique using the structure of a binary majority logic code. It is shown that it is easy to adapt such a technique to handle the case where the decoder is given an ordered list of two or more prospective candidates for each inner code symbol. Large reductions in failure probability can be achieved. Simulation results are shown for both block and convolutional codes. Punctured convolutional codes allow a convenient flexibility of rate while retaining high decoding power. For example, a (856, 500) terminated convolutional code with an average of 180 random first-choice symbol errors can correct all the errors in a simple manner about 97% of the time, with the aid of second-choice values. A (856, 500) maximum-distance block code could correct only up to 178 errors based on guaranteed correction capability and would be extremely complex     

MAP decoding of convolutional codes using reciprocal dual codes

A new symbol-by-symbol maximum a posteriori (MAP) decoding algorithm for high-rate convolutional codes using reciprocal dual convolutional codes is presented. The advantage of this approach is a reduction of the computational complexity since the number of codewords to consider is decreased for codes of rate greater than 1/2. The discussed algorithms fulfil all requirements for iterative (“turbo”) decoding schemes. Simulation results are presented for high-rate parallel concatenated convolutional codes (“turbo” codes) using an AWGN channel or a perfectly interleaved Rayleigh fading channel. It is shown that iterative decoding of high-rate codes results in high-gain, moderate-complexity coding     

Bounded minimum distance decoding of unit memory codes

We propose an algorithm for bounded minimum distance decoding of (partial) unit memory codes up to half the “designed” extended row distance. It makes use of a reduced trellis with the nodes found by bounded minimum distance decoding of the block codes used in the unit memory code. The results can be extended to general multimemory codes. The complexity of this algorithm is upper bounded by 2(d¯ ₁^r-2d_α) times the complexity of the bounded minimum distance decoder of the block codes in the unit memory code. Here d_α is the linear increase of the designed extended row distance d¯_i^r     

Advances in the performance of Reed-Solomon codes

This paper presents generalized expressions for the probabilities of correct decoding and decoder error for Reed-Solomon (RS) codes. In these expressions, the symbol error and erasure probabilities are different in each coordinate in a codeword. The above expressions are used to derive the expressions for reliability and delay for Type-I hybrid ARQ (HARQ-I) systems when each symbol in a packet (multiple codewords per packet) has unique symbol error and erasure probabilities. Applications of the above results are demonstrated by analyzing a bursty-correlative channel in which the symbols and codewords within the packet are correlated     

Generalized threshold decoding of convolutional codes

A one-step threshold decoding method previously presented for cyclic block codes is shown to apply generally to linear convolutional codes. It is further shown that this method generalizes in a natural way to allow decoding of the received sequence in its unquantized analog form.     

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.     

Enhanced trellis extracted synchronisation for block codes usinginterleavers

Previously, trellis extracted synchronisation techniques (TEST) have been presented as a purely digital method of providing bit/symbol and word synchronisation for block codes using auxiliary data obtained through trellis decoding. One of the factors affecting the complexity of the algorithm has been that any cyclic properties within the code must be countered by building confidence in a particular synchronisation point. This problem is further exasperated by a long sequence of the all-zeros (or all-ones) codeword, which presents all cyclic shifts as valid codewords. The novel algorithm presented in this Letter uses an interleaver with an inversion to overcome these two problems and significantly reduce the complexity without reducing performance     

Majority-logic-like decoding of vector symbols

The use of the structure of one-step decodable majority logic codes for enhanced and simplified vector symbol decoding, such as outer code decoding of concatenated codes, is proposed. For J equations checking a particular symbol, the technique to be described almost always corrects the symbol if there are J-1 or fewer symbol errors, and often corrects cases of far more than J symbol errors. Ordinarily, majority level decoding with J equations for a symbol corrects the symbol in all cases where there are up to [J/2] errors. The decoding power is comparable to Reed-Solomon codes, but decoding is simpler than for Reed-Solomon codes     

Errors and erasures decoding of BCH and Reed-Solomon codes for reduced M-ary orthogonal signaling

The paper presents a comparison of communication systems using different signal constellation sizes and Reed-Solomon or Bose-Chaudhuri-Hocquengem codes with different rates so that the overall required bandwidth is the same for each system. In these comparisons, the channel symbol size is smaller than the code symbol size, so that a code symbol contains parts of multiple channel symbols. Thus, the normal assumption of independent code symbols does not apply. Instead, consideration must be taken to obtain the best arrangement of channel symbols in each code symbol. Analytical expressions are developed to compare the bit error probability performance of comparable systems, based on individual codewords using errors-only decoding and errors and erasures decoding with transmission over a Rayleigh fading channel.