In this paper, a new approach for decoding low-rate Reed-Solomon codes beyond half the minimum distance is considered and analyzed. The maximum error correcting radius coincides with the error correcting radius of the Sudan algorithm published in 1997. However, unlike the Sudan Algorithm, the approach described here is not a list decoding algorithm, and is not based on polynomial interpolation. The algorithm in this paper is rather syndrome based, like classical algebraic decoding algorithms. The computational complexity of the new algorithm is of the same order as the complexity of the well-known Berlekamp-Massey algorithm. To decode errors beyond half the minimum distance, the new decoder is allowed to fail for some high-weight error patterns with a very small probability.

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.

Reed-Solomon codes have become one of the most popular classes of error correcting codes, since they can be decoded very efficiently up to half their minimum distance using syndrome-based techniques. Modern interpolation-based decoding algorithms like the Sudan algorithm allow for decoding error patterns beyond half the minimum distance in polynomial time. Recently, a syndrome-based decoding algorithm has been proposed, which virtually extends a Reed-Solomon code into an Interleaved Reed-Solomon (IRS) code. This method is competitive to the classical Sudan algorithm. In this paper, a new method for decoding IRS codes is described, which combines the idea of syndrome extension and the idea of collaboratively decoding IRS codes to increase the decoding radius of low-rate IRS codes.

The problem of linear shift-register synthesis for a single sequence is solved by the well known Berlekamp-Massey algorithm. The problem of multi-sequence shift-register synthesis is already addressed by Feng and Tzeng. The Feng-Tzeng algorithm can be considered as a generalization of the Berlekamp-Massey algorithm which takes a set of t different sequences of length N and yields a linear shift-register of length l capable of generating all t sequences. However, for the case of multiple sequences of varying length, the Feng-Tzeng algorithm generally does not give the correct solution. We demonstrate this by means of an example and explain, why the Feng-Tzeng algorithm does not work properly in the unequal length case. We propose a modification of the fundamental iterative algorithm (FIA) from Feng and Tzeng, which overcomes the problem with varying length sequences. Based on this algorithm we derive an efficient Berlekamp-Massey like algorithm for solving the multi-sequence shift-register synthesis problem for sequences of varying length

It is known, that interleaved Reed-Solomon codes can be decoded algebraically beyond half the minimum distance using collaborative decoding strategies. Based on the same principles, we suggest a new effective algebraic decoding method, which is able to decode a single low rate Reed-Solomon code beyond half the minimum distance. This new algorithm is based on multi-sequence shift-register synthesis, and is able to correct errors within a correcting radius similar to the Sudan algorithm. In contrast to the Sudan algorithm, which may obtain a list of codewords, our algorithm yields a decoding failure if there does not exist a unique solution. However, the probability of such a failure is very small

In this paper, an algorithm for low-density parity-check (LDPC) codes with reduced complexity is presented. The complexity reduction is achieved by calculating a linear function for updating the check nodes in each iteration, instead of an exponential and logarithmic function. The parameters of the linear function are optimized by density evolution. Simulation results show that there is nearly no loss in the performance by using this approximation compared to the exact calculation of the belief propagation decoding algorithm, even for very large block lengths.

Decoding strategies based on ordered statistics have proven to be powerful in decoding binary linear block codes. However, for q-ary codes, the existing decoding methods are not suited very well, since the required reprocessing steps, which try all possible changes in several code symbols, cause a high computational complexity. This complexity can be reduced by using short lists of the most reliable symbols instead of trying all q possibilities. In this paper we investigate, in which situations such short lists are most effective and how they should be applied to improve the decoding performance. We present a decoding method for a simple concatenated scheme, in which we create lists by the decoder of a binary inner code and apply them to the q-ary symbols of an outer Reed-Solomon code

Interleaved Reed-Solomon codes allow the correction of errors beyond half the minimum code distance if the errors are not distributed independently in the received signal but occur in bursts. Therefore, these codes are mainly considered for applications in channels, that cause correlated error patterns, i.e., error bursts. However, they can also be quite interesting for memoryless channels causing independent random errors, if they are applied in concatenated code designs. We present such concatenated codes with several outer Reed-Solomon codewords and demonstrate the gain, that can be obtained by interleaved Reed-Solomon decoding in comparison to independently decoding the several words of the underlying Reed-Solomon codes.

A polyalphabetic (or mixed) block code is a set of codewords of finite length, where every symbol of a codeword belongs to its own alphabet. In contrast to previous publications we consider a general case, where we do not assume any algebraic structure of the alphabets and the codes. Upper and lower bounds on the cardinality of a polyalphabetic code with given Hamming distance are obtained. Some constructions of polyalphabetic codes are suggested based on known codes. Encoding and decoding of the polyalphabetic codes, obtained in this way, can be done using encoding and decoding algorithms for the mother code. Using this constructions, codes are obtained, that reach the upper Singleton type bound.

To find the best path in a trellis, the Viterbi algorithm can be used. We present an algorithm to find not only the best, but a sorted list of the /spl lscr/ best paths. Our algorithm is based on the Viterbi algorithm and iteratively applies a back-tracing procedure to find the /spl lscr/ best paths.