US4185269A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Error correcting system for serial by byte data
Assignee: International Business Machines Corp
•
Filing: 1978-06-30
•
Granted: 1980-01-22
•
Expires: 1998-06-30
Abstract
Abstract A system is disclosed for generating a plurality of error correcting check ECC bytes from a block of data presented to the system in serial by byte form. The system employs a plurality of ECC channels which operate in parallel with the channels generating check bytes from interleaved subsets of the data block. One channel generates an ECC parity check byte for each interleaved subset while another channel generates an ECC locator check byte for each interleaved subset of data. The ECC locator check byte for each subset represents the parity or modulo 2 sum of bit positions which are selected systematically in accordance with a predefined m sequence which is unique to each channel that generates locator check bytes. Error patterns greater than the number of bits in one byte are correctable, as are error patterns which are less than the number of bits in one byte but extend across byte boundaries of two adjacent bytes in different subsets.
Inventors
- 👤 Paul Hodges
- 👤 Werner J. Schaeuble
- 👤 Paul L. Shaffer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 23:32
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
282 words
A system for generating error correcting check bytes for a block of data having a relatively large number of data bytes each consisting of k bits, said system comprising: (1) first and second check byte generating units, each of which includes means for generating at least one k bit check byte for at least two predefined interleaved subsets of data bytes in said data block wherein each said predefined subset includes no more than 2 k -1 data bytes; (2) each said k bit check byte generated by said first unit representing a parity check byte for a different said predefined subset to provide for the subsequent generation of an error pattern syndrome byte for said subset from said parity check byte; (3) each said k bit check byte generated by said second unit representing an error locator check byte for a different said predefined subset to provide for the subsequent generation of an error locator syndrome byte for said subset from said error locator check byte; (4) each said k bit check byte generated by said units corresponding to one of 2 k unique k bit binary permutations; (5) each bit of each said locator check byte representing the results of summing modulo 2 preselected bit positions of data bytes in a subset; (6) said preselected bit positions being selected in accordance with a systematic approach which results in said error locator syndrome byte having a bit pattern which is indicative of the location in said subset of an error pattern corresponding to said error pattern syndrome byte. (7) whereby an error in said data block within one byte or spanning two adjacent bytes each in a different subset are correctable.
Claim 2
Independent Claim
282 words
A system for generating error correcting check bytes for a block of data having a relatively large number of data bytes each consisting of k bits, said system comprising: (1) first and second check byte generating units, each of which includes means for generating at least one k bit check byte for at least two predefined interleaved subsets of data bytes in said data block wherein each said predefined subset includes no more than 2 k -1 data bytes; (2) each said k bit check byte generated by said first unit representing a parity check byte for a different said predefined subset to provide for the subsequent generation of an error pattern syndrome byte for said subset from said parity check byte; (3) each said k bit check byte generated by said second unit representing an error locator check byte for a different said predefined subset to provide for the subsequent generation of an error locator syndrome byte for said subset from said error locator check byte; (4) each said k bit check byte generated by said units corresponding to one of 2 k unique k bit binary permutations; (5) each bit of each said locator check byte representing the results of summing modulo 2 preselected bit positions of data bytes in a subset; (6) said preselected bit positions being selected in accordance with a systematic approach which results in said error locator syndrome byte having a bit pattern which is indicative of the location in said subset of an error pattern corresponding to said error pattern syndrome byte. (7) whereby an error in said data block within one byte or spanning two adjacent bytes each in a different subset are correctable.
Claim 3
Dependent Claim
27 words
The system recited in claim 1 further including means for supplying said first and second check byte generating units with each said byte of said data block.
Claim 4
Dependent Claim
24 words
The system recited in claim 2 in which said means supplies each said byte of said data in parallel to each of said units.
Claim 5
Dependent Claim
35 words
The combination recited by claim 1 further including a third check byte generating unit identical to said second unit except that different said preselected bit positions are selected in accordance with a different systematic approach.
Claim 6
Dependent Claim
18 words
The system recited in claim 4 in which each said systematic approach coresponds to a different m sequence.
Claim 7
Dependent Claim
53 words
The system recited in claim 1 in which each said generating unit includes: a first register; a plurality of individually addressable registers; means for transferring the contents of said first register selectively to one of said addressable registers; and means for transferring the contents of said addressable registers selectively to said first register.
Claim 8
Dependent Claim
20 words
The combination recited in claim 6 in which said addressable registers of each said unit comprise a random access memory.
Claim 9
Dependent Claim
26 words
The combination recited in claim 7 further including addressing means for said addressable registers comprising a two-stage counter for simultaneously addressing each said random access memory.
Claim 10
Dependent Claim
39 words
The system recited in claim 6 further including means for combining each byte of data of said data block with the contents of a selected one of said addressable registers and for storing the results in said first register.
Claim 11
Dependent Claim
18 words
The combination recited in claim 9 further including means for addressing one addressable register in each unit simultaneously.
Claim 12
Dependent Claim
26 words
The system recited in claim 10 further including means for sequencing said addressing means one address as each new data byte is entered into said register.
Claim 13
Dependent Claim
30 words
The system recited in claim 11 further including means for transferring the contents of said addressable registers to an external device immediately after the last byte of said data block.
Claim 14
Dependent Claim
45 words
The system recited in claim 12 in which said transferring means further includes means for sequentially transferring out check bytes from said addressable registers of said unit to an external unit prior to transferring out the contents of the addressable registers of said other unit.
Claim 15
Dependent Claim
32 words
The system recited in claim 9 in which said combining means of each said generating unit operates to sum modulo 2 a data byte and said contents of said selected addressable register.
Claim 16
Dependent Claim
49 words
The system recited in claim 14 in which said combining means of one of said units further includes means for transferring the contents of a selected one of said addressable registers to said first register rotated one position and from said first register back to said selected addressable register.
Claim 17
Dependent Claim
47 words
The combination recited in claim 15 in which said transferring means further includes logic means operable in response to the value of one digit position of said selected addressable register for combining said transferred contents with a predetermined feedback pattern prior to entry into said first register.
Claim 18
Dependent Claim
27 words
The system recited in claim 14 in which one of said units includes means for selectively shifting (or rotating) the contents of said addressable register one position.
Claim 19
Dependent Claim
20 words
The system recited in claim 17 further including logic means for combining said shifted contents with a predetermined binary pattern.
Claim 20
Dependent Claim
33 words
The system recited in claim 18 further including means responsive to the value of one selected bit position of the contents of said addressable register to control the operation of said logic means.
References Cited (Backward Citations)
US3163848A
Cited
US3478313A
Cited
US3725859A
Cited
US3745526A
Cited
US3825893A
Cited
US3913068A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1983-01-21 | 1983-07-23 | 1984-01-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1987-01-21 | 1987-07-23 | 1988-01-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1991-01-21 | 1991-07-23 | 1992-01-22 | $7700.00 | Window Closed / Lapsed |