On Multisequence Shift Register Synthesis and Generalized-Minimum-Distance Decoding of Reed-Solomon Codes
✍ Scribed by N. Kamiya
- Publisher
- Elsevier Science
- Year
- 1995
- Tongue
- English
- Weight
- 618 KB
- Volume
- 1
- Category
- Article
- ISSN
- 1071-5797
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper. it is shown that the problem of generalized-minimum-distance (GMD) decoding of Reed-Solomon (RS) codes can be reduced to the problem of multisequence shift register synthesis, and a simple algorithm is presented that yields a solution for this problem by finding, for (k=1,2, \ldots). the shortest linear feedback shift register that can generate each of the first (k) sequences of a special kind of multisequence. The algorithm is based on the well-known Berlekamp-Massey algorithm for a single-sequence problem and is only a little more complex than it. Also presented is a GMD decoding algorithm for RS codes which employs the proposed multisequence shift register synthesis algorithm and whose complexity is less than (3 n d+8 d^{2}) for the code length (n) and the minimum distance (d). This GMD decoding algorithm provides an allernative to algorithms based on the WelchBerlekamp algorithm. O 1995 Acadtmic Press. Imc.