The hybrid list decoding and Chase-like algorithm of Reed-Solomon codes.
Loading...
Date
2005
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Reed-Solomon (RS) codes are powerful error-correcting codes that can be found in a
wide variety of digital communications and digital data-storage systems. Classical
hard decoder of RS code can correct t = (dmin -1) /2 errors where dmin = (n - k+ 1)
is the minimum distance of the codeword, n is the length of codeword and k is the
dimension of codeword. Maximum likelihood decoding (MLD) performs better
than the classical decoding and therefore how to approach the performance of
the MLD with less complexity is a subject which has been researched extensively.
Applying the bit reliability obtained from channel to the conventional decoding
algorithm is always an efficient technique to approach the performance of MLD,
although the exponential increase of complexity is always concomitant. It is definite
that more enhancement of performance can be achieved if we apply the bit
reliability to enhanced algebraic decoding algorithm that is more powerful than
conventional decoding algorithm.
In 1997 Madhu Sudan, building on previous work of Welch-Berlekamp, and others,
discovered a polynomial-time algorithm for decoding low-rate Reed- Solomon
codes beyond the classical error-correcting bound t = (dmin -1) /2. Two years later
Guruswami and Sudan published a significantly improved version of Sudan's algorithm
(GS), but these papers did not focus on devising practical implementation.
The other authors, Kotter, Roth and Ruckenstein, were able to find realizations for
the key steps in the GS algorithm, thus making the GS algorithm a practical instrument
in transmission systems. The Gross list algorithm, which is a simplified one
with less decoding complexity realized by a reencoding scheme, is also taken into
account in this dissertation. The fundamental idea of the GS algorithm is to take
advantage of an interpolation step to get an interpolation polynomial produced by
support symbols, received symbols and their corresponding multiplicities. After
that the GS algorithm implements a factorization step to find the roots of the interpolation
polynomial. After comparing the reliability of these codewords which
are from the output of factorization, the GS algorithm outputs the most likely
one. The support set, received set and multiplicity set are created by Koetter Vardy
(KV) front end algorithm. In the GS list decoding algorithm, the number
of errors that can be corrected increases to tcs = n - 1 - lJ (k - 1) n J. It is easy
to show that the GS list decoding algorithm is capable of correcting more errors
than a conventional decoding algorithm.
In this dissertation, we present two hybrid list decoding and Chase-like algorithms.
We apply the Chase algorithms to the KV soft-decision front end. Consequently,
we are able to provide a more reliable input to the KV list algorithm. In
the application of Chase-like algorithm, we take two conditions into consideration,
so that the floor cannot occur and more coding gains are possible. With an increase
of the bits that are chosen by the Chase algorithm, the complexity of the hybrid
algorithm increases exponentially. To solve this problem an adaptive algorithm
is applied to the hybrid algorithm based on the fact that as signal-to-noise ratio
(SNR) increases the received bits are more reliable, and not every received sequence
needs to create the fixed number of test error patterns by the Chase algorithm. We
set a threshold according to the given SNR and utilize it to finally decide which
unreliable bits are picked up by Chase algorithm. However, the performance of the
adaptive hybrid algorithm at high SNRs decreases as the complexity decreases. It
means that the adaptive algorithm is not a sufficient mechanism for eliminating
the redundant test error patterns.
The performance of the adaptive hybrid algorithm at high SNRs motivates us
to find out another way to reduce the complexity without loss of performance.
We would consider the two following problems before dealing with the problem
on hand. One problem is: can we find a terminative condition to decide which
generated candidate codeword is the most likely codeword for received sequence
before all candidates of received set are tested? Another one is: can we eliminate
the test error patterns that cannot create more likely codewords than the generated
codewords? In our final algorithm, an optimality lemma coming from the Kaneko
algorithm is applied to solve the first problem and the second problem is solved by a
ruling out scheme for the reduced list decoding algorithm. The Gross list algorithm
is also applied in our final hybrid algorithm. After the two problems have been
solved, the final hybrid algorithm has performance comparable with the hybrid
algorithm combined the KV list decoding algorithm and the Chase algorithm but
much less complexity at high SNRs.
Description
Thesis (M.Sc.Eng.)-University of KwaZulu-Natal, 2005
Keywords
Reed-Solomon codes., Error-correcting codes (Information theory), Algorithms., Theses--Electronic engineering.