A modified Blahut algorithm for decoding Reed-Solomon codes beyond half the minimum distance

A modification of the Blahut algorithm is proposed for decoding of Reed-Solomon codes beyond half the minimum distance. An effective method is offered for the searching of unknown discrepancies needed for analytical continuation of the Berlekamp-Massey algorithm through two additional iterations. This reduces the search time by 2(q-1)n/((n+t+1)(n-t)) times, compared with the Blahut algorithm. An architecture of a searcher for unknown discrepancies is given. The coding gain of the proposed algorithm is shown for some practical codes.     

Reduced-search soft-decision trellis coding of linear block codes (Corresp.)

Algorithms for the soft-decision decoding of linear block codes are presented. These algorithms perform a reduced complexity search through a trellis derived from the parity check matrix of an(n, k)linear block code. The computational complexity of the algorithms is considerably reduced from that of a full maximum-likelihood algorithm. We demonstrate the trade-off between complexity and efficiency of the algorithms through computer simulation.     

An erasures-and-errors decoding algorithm for Goppa codes (Corresp.)

An erasures-and-errors decoding algorithm for Goppa codes is presented. Given the Goppa polynomial and the modified syndrome polynomial, a modified key equation is solved using Euclid's algorithm to determine the error locator polynomial and the errata evaluator polynomial.     

A feedback decoding scheme for linear convolutional codes (Corresp.)

A decoding scheme, with feedback, for linear convolutional codes is given. The scheme when applied to linear nonsystematic convolutional codes requires no post-decoding processing involving memory to retrieve the information sequences. This implies that no additional errors occur that are due only to the information retrieving process.     

Efficient optimal decoding of linear block codes (Corresp.)

An optimal soft decision (maximum likelihood) decoding scheme for linear block codes is described which works in the code domain and is relatively simple. It can be simplified further by considering more channel measurement information. Furthermore, optimal decoder complexity can be traded for asymptotically optimum performance.     

New decoding algorithm for Reed - Muller codes (Corresp.)

We interpret Reed-Muller codes in terms of superimposition and present a new decoding algorithm for Reed-Muller codes. Before presenting this algorithm, we propose a decoding algorithm for a class of simple iterated codes (SI codes) that will play an important role in our new decoding algorithm. Finally, we compare our algorithm with the conventional algorithm for the cyclic Reed-Muller codes from the standpoint of decoding delay.     

On the Lin-Weldon majority-logic decoding algorithm for product codes (Corresp.)

It is shown that a majority-logic decoding algorithm proposed by Lin and Weldon for the product of anL-step and a one-step orthogonalizable code is incomplete whenLis greater than unity. An improvement is presented to overcome this disadvantage in the binary case.     

An asymptotic Hamming bound on the feedback decoding minimum distance of linear tree codes (Corresp.)

An asymptotic Hamming bound for tree codes is derived. This bound is not new, it has been obtained earlier by Pinsker. However, Markov chains were used by Pinsker in its proof whereas more direct methods are used here.     

Generalized minimum distance decoding on majority logic decodable codes (Corresp.)

Generalized minimum distance decoding schemes are found for majority logic decodable codes. These decoding schemes are parallel to the classical majority logic decoding schemes and thus can be easily implemented.     

Optimal decoding of linear codes for minimizing symbol error rate (Corresp.)

The general problem of estimating the a posteriori probabilities of the states and transitions of a Markov source observed through a discrete memoryless channel is considered. The decoding of linear block and convolutional codes to minimize symbol error probability is shown to be a special case of this problem. An optimal decoding algorithm is derived.     

Strengthened lower bound on definite decoding minimum distance for periodic convolutional codes (Corresp.)

A new lower bound on definite decoding minimum distance for the class of systematic binary periodic convolutional codes is presented. The bound is everywhere stronger than Wagner's bound and has the same form as the bound obtained by Massey for the class of systematic binary fixed convolutional codes. The bound is also shown to apply to a specific subclass of simply implemented periodic codes for which Wagner's bound also holds.     

Error-erasure decoding of product codes (Corresp.)

Two error-erasure decoding algorithms for product codes that correct all the error-erasure patterns guaranteed correctable by the minimum Hamming distance of the product code are given. The first algorithm works when at least one of the component codes is majority-logic decodable. The second algorithm works for any product code. Both algorithms use the decoders of the component codes.     

High-speed decoding of BCH codes (Corresp.)

A general algorithm is derived for the calculation of the error location polynomial in decoding a Bose-Chaudhuri-Hocquenguem (BCH) code. A shorter decoding time is required by the algorithm for low-weight errors because only a subset of the syndrome equations are to be satisfied. The application of the general algorithm to Berlekamp's algorithm is also presented.     

Maximalq-nary linear codes with large minimum distance (Corresp.)

This correspondence presents a complete solution to the problem of constructing maximalq-nary codes, for any word lengthnand minimum distancedin the regionqd geq (q - 1)n. Several interesting results regarding the interdependence of these codes are developed, which reveal the unique structure of the code spaces of the regionqd geq (q - 1)n. Some new maximal codes are obtained for the regionqd < (q - 1)n.     

On a class of arithmetic codes and a decoding algorithm (Corresp.)

Multiple-error-correcting arithmetic codes which are nonlinear are constructed by residue encoding. A simple algorithm is given for correcting multiple errors which makes use of continued fractions.     

Improved decoding algorithms for arithmetic residue codes (Corresp.)

Two classes of arithmetic codes constructed in residue number systems are considered, and decoding algorithms based on the convergents of continued fractions are presented. The advantages of the proposed algorithms over those previously known are discussed.     

On encoding and decoding maps for group codes (Corresp.)

The problem of minimizing mean-square error when digital data is encoded into the elements of a group code via an encoding map a and the received elements of the group code are decoded via a decoding mapbetais considered. This problem has been solved under the restriction thatbeta = alpha^{-1}. It is shown that the same solution still obtains when this restriction is removed.     

On the complexity of decoding Goppa codes (Corresp.)

It is shown that i) erasures-and-errors decoding of Goppa codes can be done usingO(n log^{2} n)arithmetic operations, ii) long primitive binary Bose-Chaudhuri-Hocquenghem (BCH) codes can be decoded usingO(n log n)arithmetic operations, and iii) Justesen's asymptotically good codes can be decoded usingO(n^{2})bit operations. These results are based on the application of efficient computational techniques to the decoding algorithms recently discovered by Sugiyama, Kasahara, Hirasawa, and Namekawa.     

On the complexity of decoding Reed-Solomon codes (Corresp.)

Certainq-ary Reed-Solomon codes can be decoded by an algorithm requiring onlyO(q log^{2} q)additions and multiplications inGF(q).     

A decoding algorithm for binary block codes andJ-ary output channels (Corresp.)

A search algorithm is described to decode long binary block codes of any rate for the memoryless binary inputJ-ary output channel. It can be used directly to perform maximum-likelihood decoding or in a constrained version that gives considerably fewer searches at a small sacrifice in performance. Simulation results are given for a rate-l/2 code of length 128 and minimum Hamming distance 22 on the quantized Gaussian channel.