US3714629A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Double error correcting method and system
Assignee: International Business Machines Corp
•
Filing: 1971-06-01
•
Granted: 1973-01-30
•
Expires: 1991-06-01
Abstract
Abstract A cyclic code is encoded for double error correction in accordance with the following parity check matrix: WHERE THE CODE LENGTH N IS GIVEN BY 2M-1 AND Alpha IS A PRIMITIVE ELEMENT OF GF(2m) represented by a binary column vector. Decoding of the coded message requires establishing a one to one correspondence between n2+n/2 distinct error patterns and the corresponding syndromes. The n2+n/2 distinct syndromes are mapped into n+1/2 fixed syndromes by an arithmetic operation as follows: The syndrome is obtained in two parts for an error in each of digit positions i and j given by: This syndrome is mapped into: There are only n+1/2 distinct values of S'' to cover all possible single and double errors. The error positions resulting from the corresponding S'' are then mapped into actual error locations i and j.
Inventors
- 👤 S Hong
- 👤 A Patel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 12:35
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
116 words
In a system for correcting double errors utilizing a message encoded for transmission according to the matrix: where the code length n is given by 2m-1 and Alpha is a primitive element of GF(2m) represented by a binary column vector, a decoding means for the encoded received message comprising: syndrome generation means for generating a syndrome indicative of errors in digit position i and j of said received message, said syndrome being generated in the following form: means for mapping said syndrome S into a basic syndrome S'' having the following form: further means for mapping the error positions corresponding to the basic syndrome S'' into error locations i and j where the errors are corrected.
Claim 2
Dependent Claim
116 words
In a system for correcting double errors utilizing a message encoded for transmission according to the matrix: where the code length n is given by 2m-1 and Alpha is a primitive element of GF(2m) represented by a binary column vector, a decoding means for the encoded received message comprising: syndrome generation means for generating a syndrome indicative of errors in digit position i and j of said received message, said syndrome being generated in the following form: means for mapping said syndrome S into a basic syndrome S'' having the following form: further means for mapping the error positions corresponding to the basic syndrome S'' into error locations i and j where the errors are corrected.
Claim 3
Dependent Claim
116 words
In a system for correcting double errors utilizing a message encoded for transmission according to the matrix: where the code length n is given by 2m-1 and Alpha is a primitive element of GF(2m) represented by a binary column vector, a decoding means for the encoded received message comprising: syndrome generation means for generating a syndrome indicative of errors in digit position i and j of said received message, said syndrome being generated in the following form: means for mapping said syndrome S into a basic syndrome S'' having the following form: further means for mapping the error positions corresponding to the basic syndrome S'' into error locations i and j where the errors are corrected.
Claim 4
Dependent Claim
116 words
In a system for correcting double errors utilizing a message encoded for transmission according to the matrix: where the code length n is given by 2m-1 and Alpha is a primitive element of GF(2m) represented by a binary column vector, a decoding means for the encoded received message comprising: syndrome generation means for generating a syndrome indicative of errors in digit position i and j of said received message, said syndrome being generated in the following form: means for mapping said syndrome S into a basic syndrome S'' having the following form: further means for mapping the error positions corresponding to the basic syndrome S'' into error locations i and j where the errors are corrected.
Claim 5
Dependent Claim
34 words
In a system according to claim 1, wherein said syndrome generation means includes syndrome decoding means for decoding said syndrome in two parts S1 and S3 as field elements Beta and gamma , respectively.
Claim 6
Dependent Claim
56 words
In a system according to claim 2, wherein said means for mapping said syndrome S into a basic syndrome S'' includes binary encoding means for encoding field elements Beta , 1/ Beta 3 and gamma with m bit binary numbers representing P, (-3p) mod n and q, respectively, where Beta Alpha p and gamma Alpha q.
Claim 7
Dependent Claim
36 words
IN a system according to claim 3, wherein said means for mapping said syndrome S into a basic syndrome S'' further includes a first binary adding means for adding q + (-3p) mod n which k.
Claim 8
Dependent Claim
44 words
In a system according to claim 4, wherein said means for mapping said syndrome S into a basic syndrome S'' further including a table generating means for generating predetermined values of i'' and j'' for the various k''s determined by said first adding means.
Claim 9
Dependent Claim
56 words
In a system according to claim 5, wherein said further means for mapping the error positions corresponding to the basic syndrome S'' into error locations i and j include a second and third binary adding means for adding i'' + p mod n which equals i and j'' + p mod n which equals j, respectively.
Claim 10
Dependent Claim
55 words
In a system according to claim 6, wherein said further means for mapping the error positions corresponding to the basic syndrome S'' into error locations i and j include a binary number decoding means for decoding the binary numbers i and j into error position pointers for indicating the locations of the positions in error.
Claim 11
Dependent Claim
22 words
In a system according to claim 2, wherein said syndrome decoding means includes uncorrectable error recognizing means represented by Beta phi .
Claim 12
Dependent Claim
22 words
In a system according to claim 2, wherein said syndrome decoding means includes single error recognizing means operable when gamma Beta 3.
Claim 13
Dependent Claim
25 words
In a system according to claim 4, wherein said first binary adding means has the output thereof assigned a 0 value if gamma phi .
Claim 14
Dependent Claim
37 words
In a system according to claim 5 wherein said table generating means includes further uncorrectable error recognizing means when i'' j'' 0 which indicates an invalid value of k and provides an output indicating an uncorrectable error.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1976-01-30 | 1976-07-31 | 1977-01-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1980-01-30 | 1980-07-31 | 1981-01-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1984-01-30 | 1984-07-31 | 1985-01-30 | $7700.00 | Window Closed / Lapsed |