US3745526A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Shift register error correcting system
Assignee: International Business Machines Corp
•
Filing: 1971-12-20
•
Granted: 1973-07-10
•
Expires: 1991-12-20
Abstract
Abstract An error correcting system is provided for a parallel track or parallel channel information handling system in which the information is divided into blocks of bytes of b-bits each. The information is encoded by attaching a plurality of check bytes in accordance with an H matrix consisting of a predetermined number of submatrices, each of which operates on distinct partitioned portions of the message bytes. Each of the submatrices are concatenated iteratively by b so that the matrix H can be designated by submatrices Hr,b; H(r b) , b; H(r 2b) ,b. . . H(2b c) ,b where r kb c and 0 < OR = c < r. Each partitioned portion of the message is operated on by a pair of shift registers to generate the check byte contribution of the respective partition. Each pair of shift registers operates on the bits of a byte in parallel and the shift registers in each partition operate in unison. The partial check bytes from the respective pairs of shift registers are modulo 2 added to obtain the check byte. Likewise, a pair of shift registers are associated with each partition of the information so that the partial syndrome byte outputs can be modulo 2 added with the respective check bits to obtain the syndrome byte. The partition in error is determined by detecting the first non-zero syndrome byte. The byte in error is located by loading the subsequent syndrome bytes of the partition in error into the corresponding shift register and shifting until the contents match the first non-zero syndrome byte, the number of shifts being indicative of the byte in error.
Inventors
- 👤 S Hong
- 👤 A Patel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 23:38
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/19
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
200 words
An error correction system for correcting up to b-adjacent errors in a b-bit byte of a byte-oriented binary message comprising: encoding means for operating on said b-bit bytes of said binary message in parallel; said encoding means including a plurality of pairs of shift registers; b input means for each shift register of each of said pairs of shift registers; means for distributing different portions of said B-bit byte message to said input means of different pairs of said shift registers in accordance with submatrices defining partitions of the message in a H matrix; output means from each stage of each pair of said plurality of pairs of shift registers; modulo two adding means for combining said output means from said plurality of pairs of shift registers; a plurality of registers for accumulating the results of said modulo two adding means thereby providing the check bytes for encoding the binary message in accordance with the matrix H, said check bytes being added to said binary message to form the encoded message; utilization means for utilizing the encoded message; means for decoding the encoded message after utilization thereof; and means for correcting the errors found as a result of said decoding.
Claim 2
Dependent Claim
200 words
An error correction system for correcting up to b-adjacent errors in a b-bit byte of a byte-oriented binary message comprising: encoding means for operating on said b-bit bytes of said binary message in parallel; said encoding means including a plurality of pairs of shift registers; b input means for each shift register of each of said pairs of shift registers; means for distributing different portions of said B-bit byte message to said input means of different pairs of said shift registers in accordance with submatrices defining partitions of the message in a H matrix; output means from each stage of each pair of said plurality of pairs of shift registers; modulo two adding means for combining said output means from said plurality of pairs of shift registers; a plurality of registers for accumulating the results of said modulo two adding means thereby providing the check bytes for encoding the binary message in accordance with the matrix H, said check bytes being added to said binary message to form the encoded message; utilization means for utilizing the encoded message; means for decoding the encoded message after utilization thereof; and means for correcting the errors found as a result of said decoding.
Claim 3
Dependent Claim
46 words
An error correction system according to claim 1, wherein each pair of shift registers operates in parallel on the bits of bytes of respective portions of said binary message defined by its respective submatrix, said pairs of shift registers operating on its respective portions in unison.
Claim 4
Dependent Claim
66 words
An error correction system according to claim 2, wherein the first shift register of each pair of said shift registers includes a modulo two addition circuit for each stage of said register and a feedback connection from the output means from each stage of said register to said respective modulo two addition circuit to perform the modulo two addition of successive incoming bits of the bytes.
Claim 5
Dependent Claim
110 words
An error correction system according to claim 3, wherein the second shift register of each pair of said shift registers includes a modulo two addition circuit at the input to the first b stages of said shift register and at the input to the stages having a corresponding term in the generator polynomial; feedback means from the last stage of said shift register to the modulo two addition circuits having a corresponding term in the generator polynomial, the b-bit byte message is connected in parallel to the modulo two addition circuits of the first b stages which provides modulo two addition of the incoming byte to the shift register content.
Claim 6
Dependent Claim
139 words
An error correction system according to claim 1, wherein said means for decoding includes a further plurality of pairs of shift registers; b input means for each shift register of each of said pairs of shift registers; means for distributing different portions of said b-bit byte message received from said utilization means to said input means of different pairs of said shift registers in accordance with submatrices defining partitions of the message in an H matrix; output means from each stage of each pair of said plurality of pairs of shift registers; modulo two adding means for combining said output means from said plurality of pairs of shift registers and said check bits; and a plurality of registers for accumulating the results of said modulo two adding means thereby providing the syndrome bits which are grouped into syndrome bytes.
Claim 7
Dependent Claim
97 words
An error correction system according to claim 1, wherein said decoding means includes means for identifying the partition in error which comprises a logic circuit for producing a first group of outputs indicative of the first non-zero byte in the syndrome when the subsequent bytes are non-zero, a second group of outputs indicative of the first non-zero byte in the syndrome when all other bytes are zero indicating the error is in the check byte corresponding to said first non-zero byte of the syndrome and a third output indicating that all bytes in the syndrome are zero.
Claim 8
Dependent Claim
104 words
An error correcting system according to claim 6, wherein said decoding means includes means for locating the byte in error within said identified partition in error comprising means for transferring said first, non-zero syndrome byte into said second shift register of said pair of shift registers associated with said partition indicated to Be in error, means for shifting said second shift register until the contents thereof match the said subsequent non-zero syndrome bytes remaining, and means for counting the number of shifts required to obtain said match, said count being indicative of the byte in error within the partition indicated to be in error.
Claim 9
Dependent Claim
63 words
An error correction system according to claim 1, wherein said means for correcting the bits in error in said indicated byte includes a plurality of EXCLUSIVE OR circuits, each having as an input thereto a different one of the bits of each of the utilized message bytes and the corresponding bits resulting from said decoding means, the output therefrom being the corrected bits.
Claim 10
Dependent Claim
116 words
An error correction system according to claim 1, wherein said encoding and decoding means are connected in accordance with a matrix H which comprises a plurality of submatrices Hr,b; H(r b), b; H(r 2b),b. . . H(2b c),b generated by means of a primitive polynomial of degree r-jb where j 1,2,3 . . . ; each successive submatrix being concatenated iteratively by successive steps of b, said submatrices forming partitions in said H matrix, a check bit partition is appended to the last of said partitions, an identity matrix Ir is contained within said check bit partition thereby forming the H matrix for determining the connections for the encoding and decoding means for said binary message.
Claim 11
Dependent Claim
62 words
An error correction system according to claim 9, wherein the encoding and decoding means connected in accordance with each of said submatrices Hr,b; H(r b),b; H(r 2b),b . . . H(2b c),b is separately capable of b-adjacent error correction and the matrix H formed thereby is capable of b-adjacent error correction of longer binary messages using the minimum number of check bits.
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 |