Multiple error trapping
First Claim
1. An error trapping decoder adapted to decode a received codeword having r redundant check symbols in r predetermined check locations in said received codeword, said error trapping decoder comprising:
- means responsive to specification of a given set of r virtual check locations different from said r check locations, for computing r virtual check symbols corresponding to said given set of r virtual check locations;
permuting means for specifying to said computing means successive sets of r virtual check locations so that said computing means computes successive sets of r virtual check symbols; and
means, responsive whenever said permuting means specifies a particular set of r virtual check locations for which the corresponding r virtual check symbols are all zero except for no more than predetermined number, for adding the non-zero ones of said particular set of r virtual check symbols to symbols occupying the corresponding virtual check locations in said received codeword, whereby to generate a corrected codeword.
3 Assignments
0 Petitions
Accused Products
Abstract
By translating in accordance with a predetermined permutation the virtual check locations of a virtual message re-encoder, plural erroneous symbols (up to a certain limit) occurring in any pattern in a received codeword may be trapped simultaneously in virtual check locations. By simply adding to them the corresponding virtual check symbols computed by the virtual message re-encoder, the correct codeword is easily obtained. In one embodiment of the invention, any pattern of two erroneous symbols in a codeword of length n may be trapped in this manner by defining the predetermined permutation in accordance with a modulus n cyclic difference set. In this embodiment, for an RS(31, 25) code, the cyclic difference set (0, 4, 10, 23, 24, 26) may be used as the predetermined permutation.
24 Citations
16 Claims
-
1. An error trapping decoder adapted to decode a received codeword having r redundant check symbols in r predetermined check locations in said received codeword, said error trapping decoder comprising:
-
means responsive to specification of a given set of r virtual check locations different from said r check locations, for computing r virtual check symbols corresponding to said given set of r virtual check locations; permuting means for specifying to said computing means successive sets of r virtual check locations so that said computing means computes successive sets of r virtual check symbols; and means, responsive whenever said permuting means specifies a particular set of r virtual check locations for which the corresponding r virtual check symbols are all zero except for no more than predetermined number, for adding the non-zero ones of said particular set of r virtual check symbols to symbols occupying the corresponding virtual check locations in said received codeword, whereby to generate a corrected codeword. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method for decoding a received codeword having r redundant check symbols located in r predetermined check locations in said received codeword, said method comprising:
-
specifying successive sets of r virtual check locations different from said r predetermined check locations; for each set in said successive sets of r virtual check locations, computing r virtual check symbols from appropriate symbols in said received codeword; and whenever said computing step generates a set of r virtual check symbols which are all zero except for no more than a predetermined limited number, adding the non-zero ones of said r virtual check symbols to symbols occupying the corresponding virtual check locations in said received codeword, so as to generate a corrected codeword. - View Dependent Claims (11, 12)
-
-
13. A method for decoding a received codeword having r virtual check symbols located in r predetermined check locations in said received codeword, said method comprising:
-
generating r remainder symbols from said codeword in accordance with a code generator polynomial; transforming said r remainder symbols into r virtual check symbols in accordance with a predetermined set of r virtual check locations; shifting the contents of said encoder by one symbol position and then repeating said generating step and said transforming step; and determining whenever a givens et of said r virtual check symbols obtained during any one of said above steps has no more than a predetermined limited number of non-zero symbols and adding said non-zero ones of said particular set of r virtual check symbols to symbols in corresponding locations in said received codeword. - View Dependent Claims (14)
-
-
15. A method for decoding a received codeword having r check symbols located in r predetermined check locations, said method comprising:
-
shifting a predetermined pattern of virtual check locations through successive translations of said codeword; for each of said translations, computing a corresponding set of virtual check symbols; and whenever no more than a predetermined limited number of said virtual check symbols are non-zero, adding said non-zero ones of said check symbols to the corresponding symbols in said received codeword so as to generate a corrected codeword. - View Dependent Claims (16)
-
Specification