US4142174A
Expired / Lapsed
US
⏱️ 0.0 years remaining
High speed decoding of Reed-Solomon codes
Assignee: International Business Machines Corp
•
Filing: 1977-08-15
•
Granted: 1979-02-27
•
Expires: 1997-08-15
Abstract
Abstract This specification covers a simplified and high speed decoding scheme for Reed-Solomon codes capable of correcting up to three symbol errors in code words made up of k data and n-k check symbols where each symbol consists of m binary bits of information. In such a code the error location polynomial σ (x) = x e + σ 1 x e-1 . . . . σ e where e equals the number of symbol errors and the coefficient of σ(x) are related to the error syndromes S i by the equation S.sub.i+e + σ.sub.1 S.sub.i+e-1 +. . . . + σ.sub.e-1 S.sub.i+1 + σ e S i = 0. The decoder first tests if S 0 = 0. If S 0 ≠ 0, the assumption is made that a single symbol error has occurred. The decoder quickly verifies this by determining if S 2 + σS 1 = 0 and S 3 + σS 2 = 0 when σ = S 1 /S 0 . If the error is not a single symbol error the decoder goes on to determine if a double symbol error has occurred and then goes on to determine if there are triple symbol errors if it turns out that a double symbol error has not occurred.
Inventors
- 👤 Chin L. Chen
- 👤 Mu Y. Hsiao
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 02:32
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15; H03M13/151; G; G11; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1806; G11B20/1809; G11B20/1833
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
237 words
In a decoder for an error detection and correction system using a Reed-Solomon code for detection and correcting a plurality of errors in codewords made up of k data and n-k check symbols each symbol made up of m binary bits of information so that the error location polynomial σ(x) = x e + σ 1 x e-1 · + . . . . σ e where e is the number of errors and the coefficients of σ(x) are related to the error syndromes S i generated by the decoder by the equation S i+e +σ 1 S 1+e-1 + . . . . + σ e-1 + σ e S i = 0 where the syndromes are field elements α i of GF(2 m ) an improved error correction and polynomial calculator for determining the number of errors in the codewords after the decoder determines that at least one error exists comprising, means for determining if S 0 ≠ 0, means for setting σ = S 1 /S 0 when S 0 ≠ 0, means for determining if S 2 + σS 1 = 0 and S 3 + σS 2 = 0 when σ = S 1 /S 0 and, means for providing an indication that one symbol error has occurred when S 2 + σS 1 = 0 and S 3 + σS 2 = 0 with σ = S 1 /S 0 .
Claim 2
Dependent Claim
237 words
In a decoder for an error detection and correction system using a Reed-Solomon code for detection and correcting a plurality of errors in codewords made up of k data and n-k check symbols each symbol made up of m binary bits of information so that the error location polynomial σ(x) = x e + σ 1 x e-1 · + . . . . σ e where e is the number of errors and the coefficients of σ(x) are related to the error syndromes S i generated by the decoder by the equation S i+e +σ 1 S 1+e-1 + . . . . + σ e-1 + σ e S i = 0 where the syndromes are field elements α i of GF(2 m ) an improved error correction and polynomial calculator for determining the number of errors in the codewords after the decoder determines that at least one error exists comprising, means for determining if S 0 ≠ 0, means for setting σ = S 1 /S 0 when S 0 ≠ 0, means for determining if S 2 + σS 1 = 0 and S 3 + σS 2 = 0 when σ = S 1 /S 0 and, means for providing an indication that one symbol error has occurred when S 2 + σS 1 = 0 and S 3 + σS 2 = 0 with σ = S 1 /S 0 .
Claim 3
Dependent Claim
144 words
The decoder for the error detection and correction system of claim 1 including, means for determining if S 3 + σS 2 ≠ 0 where S 2 + σS 1 = 0 with σ = S 1 /S 0 and if so providing an indication that three symbols are in error or means for determining if S 0 = 0 and S 1 ≠ 0 or if S 2 + σS 1 ≠ 0 and if D = 0 when σ 1 = (S 1 S 2 + S 0 S 3 )/Δ and σ 2 = (S 1 S 3 + S 2 2 )/Δ where Δ = S 1 2 + S 0 S 2 and D = S 4 + σ 1 S 3 + σ 2 S 2 and if so providing an indication that two symbols are in error.
Claim 4
Dependent Claim
104 words
The decoder for the error detection and correction system of claim 1 including; means for determining if D ≠ 0 when S 0 = 0 and S 1 ≠ 0 or when S 2 + σS 1 ≠ 0 where σ 1 = (S 1 S 2 + S 0 S 3 )/Δ and σ 2 = (S 1 S 3 + S 2 2 )/Δ and Δ = S 1 2 + S 0 S 2 and D = S 4 + σ 1 S 3 + σ 2 S 2 and if so providing an indication that three symbol errors have occurred.
Claim 5
Dependent Claim
98 words
The decoder for the error detection and correction system of claim 2 including; means for determining if D = 0 when S 0 = 0 and S 1 = 0 or when S 0 ≠ 0 and S 2 = σS 1 ≠ 0 where σ 1 = (S 1 S 2 + S 0 S 3 )/Δ and σ 2 = (S 1 S 3 + S 2 2 )/Δ and Δ = S 1 2 + S 0 S 2 and D = S 4 + σ 1 S 3 + σ 2 S 2 .
Claim 6
Dependent Claim
41 words
The decoder for the error detection and correction system of claim 1 including, means for determining if S 2 ≠ 0 when S 1 = S 0 = 0 and if so providing an indication that three symbols are in error.
Claim 7
Dependent Claim
56 words
The decoder for the error detection and correction system of claim 1 including, means for determining if S 3 ≠ 0 or S 4 ≠ 0, or S 5 ≠ 0 when S 0 = S 1 = S 2 = 0 and if so providing an indication that more than three symbol errors have occurred.
Claim 8
Dependent Claim
22 words
The decoder for the error detection and correction system of claim 1 where m = 8 and n - k = 6.
Claim 9
Dependent Claim
67 words
The decoder for the error correction and detection system of claim 1 wherein said means recited in claim 1 in total includes a buffer for storing said syndromes, addition means, multiplication and division means and test for zero means for operating on said syndromes; sequencer means for controlling the order and steps of said operation; and a log buffer means for storing partial results from said operations.
Claim 10
Dependent Claim
45 words
The decoder for the error correction and detection system of claim 8 wherein said multiplication and division means includes a read-only memory buffer that stores tables for the logarithm and anti-logarithms of field elements α i of GF(2 m ) for performing 1's complement addition.
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) | 1982-02-26 | 1982-08-28 | 1983-02-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1986-02-26 | 1986-08-28 | 1987-02-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1990-02-26 | 1990-08-28 | 1991-02-27 | $7700.00 | Window Closed / Lapsed |