US4843607A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multiple error trapping
Assignee: Eastman Kodak Co
•
Filing: 1987-12-17
•
Granted: 1989-06-27
•
Expires: 2007-12-17
Abstract
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.
Inventors
- 👤 Po Tong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 05:56
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/033; H03M13/05; H03M13/13; H03M13/17
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
158 words
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.
Claim 2
Dependent Claim
158 words
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.
Claim 3
Dependent Claim
39 words
The error trapping decoder of claim 1 wherein said permuting means specifies said successive sets of virtual check locations by successively permuting the locations of the previous set of r virtual check locations in accordance with a predetermined pattern.
Claim 4
Dependent Claim
35 words
The error trapping decoder of claim 2 wherein said predetermined pattern corresponds to a cyclic difference set and wherein said predetermined number is two, whereby said error trapping decoder is a double error trapping decoder.
Claim 5
Dependent Claim
40 words
The error trapping decoder of claim 3 wherein said codeword is an RS(31,25) codeword and wherein said predetermined pattern of virtual check locations is established by permuting the codeword location 26≧31 to codeword locations 0, 4, 10, 23, 24, 26.
Claim 6
Dependent Claim
63 words
The error trapping decoder of claim 3 wherein said computing means comprises a Reed-Solomon encoder means for generating r remainder symbols from said received codeword and a translation matrix means for transforming said r remainder symbols into r virtual remainder symbols corresponding to said r virtual check locations, and wherein said permuting means comprise means for shifting the contents of said encoder means.
Claim 7
Dependent Claim
86 words
The error trapping decoder of claim 3 wherein said computing means comprises a virtual message encoder means for generating said set of r virtual check symbols, said permuting means comprise a circular shift register connected to said virtual message encoding means and said adding means comprise r zero detectors adapted to detect whenever one of said r virtual check symbols is not zero and r Galois field adders each adapted to add one of said virtual check symbols to a corresponding symbol in said received codeword.
Claim 8
Dependent Claim
25 words
The error trapping decoder of claim 1 wherein said permuting means specifies said successive sets of virtual check locations in accordance with random permutations thereof.
Claim 9
Dependent Claim
63 words
The error trapping decoder of claim 1 wherein said computing means comprises a Reed-Solomon encoder means for generating r remainder symbols from said received codeword and a translation matrix means for transforming said r remainder symbols into r virtual remainder symbols corresponding to said r virtual check locations, and wherein said permuting means comprise means for shifting the contents of said encoder means.
Claim 10
Dependent Claim
86 words
The error trapping decoder of claim 1 wherein said computing means comprises a virtual message encoder means for generating said set of r virtual check symbols, said permuting means comprise a circular shift register connected to said virtual message encoding means and said adding means comprise r zero detectors adapted to detect whenever one of said r virtual check symbols is not zero and r Galois field adders each adapted to add one of said virtual check symbols to a corresponding symbol in said received codeword.
Claim 11
Independent Claim
119 words
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.
Claim 12
Independent Claim
119 words
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.
Claim 13
Dependent Claim
33 words
The method of claim 10 wherein the successive sets of r virtual check locations of said specifying step correspond to rotations of a set pattern of virtual check locations through said received codeword.
Claim 14
Dependent Claim
39 words
The method of claim 11 wherein said predetermined pattern of virtual check locations correspond to a cyclic difference set, and wherein said predetermined limited number of non-zero virtual check symbols is two, whereby said method accomplishes double error trapping.
Claim 15
Independent Claim
134 words
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.
Claim 16
Independent Claim
134 words
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.
Claim 17
Dependent Claim
44 words
The method of claim 13 wherein said transforming step transforms said r predetermined check locations to codeword locations corresponding to a cyclic difference set, and wherein said predetermined limited number of non-zero virtual check symbols is two, whereby said method accomplishes double error trapping.
Claim 18
Independent Claim
86 words
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.
Claim 19
Independent Claim
86 words
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.
Claim 20
Dependent Claim
41 words
The method of claim 15 wherein said predetermined pattern of virtual check locations corresponds to a cyclic difference set, and wherein said predetermined number of non-zero virtual check symbols is two, whereby said method is a double error trapping decoding method.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-06-26 | 1992-12-26 | 1993-06-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-06-26 | 1996-12-26 | 1997-06-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-06-26 | 2000-12-26 | 2001-06-27 | $7700.00 | Window Closed / Lapsed |