Patent US3745525A successfully refreshed from Google Patents.
US3745525A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Error correcting system
Assignee: International Business Machines Corp
•
Filing: 1971-12-15
•
Granted: 1973-07-10
•
Expires: 1991-12-15
Abstract
Abstract An error correcting system is provided for information sequences divided into bytes of b bits each. The information is encoded in accordance with an H matrix consisting of a predetermined number of submatrices, each of which operates on distinct partitioned portions of the sequence of message bytes. Each of the submatrices are concatenated iteratively by b so that the submatrices can be designated by Hr,b; H(r b),b; H(r 2b),b . . . H(2b c),b where r kb+c and 0 < OR = c < r. Bytes of check bits are generated in accordance with the H matrix and are added to the message sequence before utilization. A syndrome is generated from the information, after it is utilized, in accordance with said H matrix and, after being decoded, generates error pointers which indicate which of the bits in a byte of the message sequence are in error. The bits identified as being in error are corrected.
Inventors
- 👤 S Hong
- 👤 A Patel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 19:39
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/19
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
156 words
An error correction system for correcting up to b-adjacent errors in a b bit byte of a byte oriented binary message comprising: means for encoding a sequence of message bytes by adding a plurality of check bytes to the message in accordance with the matrix H which contains submatrices each of which operates on distinct partitioned portions of the sequence of message bytes; means for utilizing said encoded sequence of message bytes; means for decoding the utilized sequence of message bytes; said decoding means including a syndrome generator for generating a plurality of syndrome bytes from said received message sequence in accordance with said matrix H; syndrome decoding means for decoding each byte of said syndrome; error pointer generating means responsive to said syndrome decoding means for indicating the bits in error within a single byte when all other bytes are error free; and means for correcting the bits in error determined by said error pointers.
Claim 2
Dependent Claim
156 words
An error correction system for correcting up to b-adjacent errors in a b bit byte of a byte oriented binary message comprising: means for encoding a sequence of message bytes by adding a plurality of check bytes to the message in accordance with the matrix H which contains submatrices each of which operates on distinct partitioned portions of the sequence of message bytes; means for utilizing said encoded sequence of message bytes; means for decoding the utilized sequence of message bytes; said decoding means including a syndrome generator for generating a plurality of syndrome bytes from said received message sequence in accordance with said matrix H; syndrome decoding means for decoding each byte of said syndrome; error pointer generating means responsive to said syndrome decoding means for indicating the bits in error within a single byte when all other bytes are error free; and means for correcting the bits in error determined by said error pointers.
Claim 3
Dependent Claim
70 words
An error correction system according to claim 1, wherein said means for encoding a sequence of message bytes includes a logical EXCLUSIVE OR circuit for each bit in a byte, the logical EXCLUSIVE OR circuit being common to the same bit in all bytes of a partition of the message, each of said common bit logical EXCLUSIVE OR circuits producing an output which is a bit in a check byte.
Claim 4
Dependent Claim
61 words
An error correction system according to claim 1, wherein said encoding means matrix H submatrices are each generated according to a primitive generator polynomial of degree r-jb (j 1, 2, . . . ), generating the elements of Galois Field GF(2r jb) where r is the number of check bits, b is the byte length, and r > or = 2b.
Claim 5
Dependent Claim
48 words
An error correction system according to claim 3, wherein said encoding means matrix H submatrices are iteratively concatenated, the iteration being in steps of b and the concatenation extending to the smallest submatrix H(2b c),b where r kb+c check bits and 0 < or = c < b.
Claim 6
Dependent Claim
50 words
An error correction system according to claim 4, wherein each of the encoding means matrix H submatrices define a check byte partition in the H matrix, said check bytes generated in accordance with said H matrix are attached to the end of said encoded message forming the check byte partition.
Claim 7
Dependent Claim
85 words
An error correction system according to claim 1, wherein said syndrome generator includes a logical EXCLUSIVE OR circuit for each bit in each byte of the message and each bit in each byte of the check bytes, the logical EXCLUSIVE OR circuit being common to the same bit in all bytes of a partition of the message and the corresponding bit in the corresponding check byte, each of said common bit logical OR circuits producing an output which is a bit in a syndrome byte.
Claim 8
Dependent Claim
41 words
An error correction system according to claim 1, wherein said syndrome decoding means for decoding each byte of said syndroMe includes a plurality of AND and NOT gates for converting b syndrome bits into all possible binary combinations of b bits.
Claim 9
Dependent Claim
141 words
An error correction system according to claim 7, wherein said error pointer generating means responsive to said syndrome decoding means includes a plurality of AND gates, one for each bit in each byte plus 2b-1-b additional AND gates per byte, the inputs to the plurality of AND gates from the syndrome decoder circuits are determined in accordance with the binary sequences of the columns of the matrix H representing the byte being decoded, the additional AND gates having inputs determined in accordance with the modulo 2 sum of the corresponding bits in the respective columns of the byte, and OR circuits each having as an input thereto the output of one of said pluraltiy of AND circuits and the output of said additional AND circuits to produce an output therefrom indicative of an error in the corresponding bit of said byte.
Claim 10
Dependent Claim
52 words
An error correction system according to claim 1, wherein said means for correcting the bits in error includes a plurality of EXCLUSIVE OR circuits each having as an input thereto one of the error pointer bits and the corresponding bit from said utilized message, the output therefrom being the corrected information bit.
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-07-09 | 1977-01-08 | 1977-07-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1980-07-09 | 1981-01-08 | 1981-07-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1984-07-09 | 1985-01-08 | 1985-07-10 | $7700.00 | Window Closed / Lapsed |