US4504948A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Syndrome processing unit for multibyte error correcting systems
Assignee: International Business Machines Corp
•
Filing: 1982-12-29
•
Granted: 1985-03-12
•
Expires: 2002-12-29
Abstract
Abstract A syndrome processing unit for a multibyte error correcting system is disclosed in which logical circuitry for performing product operation on selected pairs of 8-bit syndrome bytes and exclusive-OR operations on selected results of the product operations are selectively combined to define usable cofactors that correspond to coefficients of an error locator polynomial corresponding to a selected codeword if the codeword contains less than the maximum number of errors for which the system has been designed.
Inventors
- 👤 Arvind M. Patel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 22:50
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/1833
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
261 words
In an apparatus for processing syndrome bytes in a multibyte error correcting system of the type wherein each character is represented by a byte consisting of a unique combination of "b" binary bits, and write check bytes are generated as data is being written on a storage medium, and read check bytes are generated when the data is read from the storage medium, and the apparatus is operable to correct up to t errors in a selected codeword containing up to 2 b character positions by processing 2t syndrome bytes, each containing "b" bits which were generated by combining write check bytes and read check bytes that correspond to the modulo 2 sum of bit positions of said codeword that were selected systematically in accordance with a parity check matrix reflecting the roots α a , α a+1 , α a+2 , . . . , α a+2t-1 of a generator polynomial where α is an element of the finite field of 2 b elements, the combination comprising: (1) syndrome generating means for generating 2t syndrome bytes from said selected codeword as it is read from the storage medium; and (2) circuit means responsive to said 2t syndrome bytes for developing t+1 coefficients Δ for an error locator polynomial corresponding to said selected codeword, said circuit means being characterized by logic means responsive to predetermined combinations of said syndrome bytes to produce cofactors corresponding to coefficients Δ of the error locator polynomial when less than t errors occur, and combining circuitry for selectively combining said cofactor signal when t errors occur.
Claim 2
Dependent Claim
261 words
In an apparatus for processing syndrome bytes in a multibyte error correcting system of the type wherein each character is represented by a byte consisting of a unique combination of "b" binary bits, and write check bytes are generated as data is being written on a storage medium, and read check bytes are generated when the data is read from the storage medium, and the apparatus is operable to correct up to t errors in a selected codeword containing up to 2 b character positions by processing 2t syndrome bytes, each containing "b" bits which were generated by combining write check bytes and read check bytes that correspond to the modulo 2 sum of bit positions of said codeword that were selected systematically in accordance with a parity check matrix reflecting the roots α a , α a+1 , α a+2 , . . . , α a+2t-1 of a generator polynomial where α is an element of the finite field of 2 b elements, the combination comprising: (1) syndrome generating means for generating 2t syndrome bytes from said selected codeword as it is read from the storage medium; and (2) circuit means responsive to said 2t syndrome bytes for developing t+1 coefficients Δ for an error locator polynomial corresponding to said selected codeword, said circuit means being characterized by logic means responsive to predetermined combinations of said syndrome bytes to produce cofactors corresponding to coefficients Δ of the error locator polynomial when less than t errors occur, and combining circuitry for selectively combining said cofactor signal when t errors occur.
Claim 3
Dependent Claim
40 words
The combination recited in claim 1 in which said logic means for producing said cofactors comprises a plurality of product blocks each of which is operable to multiply two "b" bit vector input signals to provide a product output signal.
Claim 4
Dependent Claim
31 words
The combination recited in claim 2 in which said logic means further includes means comprising a plurality of exclusive-OR gates for combining selected said product output signals to produce said cofactors.
Claim 5
Dependent Claim
22 words
The combination recited in claim 2 including means for connecting the output of said syndrome generating means to selected said product blocks.
Claim 6
Dependent Claim
46 words
The combination recited in claim 3 in which said combining means comprises another plurality of said product blocks and means for supplying selected said cofactors and selected said syndromes to said another plurality of said product blocks to provide a second set of product output signals.
Claim 7
Dependent Claim
33 words
The combination recited in claim 5 including another plurality of exlusive-OR gates for combining selected ones of said second set of product output signals to produce a set of t+1 error parameter signals.
Claim 8
Dependent Claim
38 words
The combination recited in claim 6 further including logic means for selecting either said t+1 error parameter signals for said error coefficients or said cofactors for said coefficients in accordance with the number of errors in said codeword.
Claim 9
Dependent Claim
11 words
The combination recited in claim 1 in which "b" is 8.
Claim 10
Dependent Claim
25 words
The combination recited in claim 1 in which said circuit means is implemented in integrated circuit technology to correct t errors employing 2t syndrome bytes.
Claim 11
Dependent Claim
25 words
The combination recited in claim 1 in which said syndrome generating means generates 2(t-x) syndrome bytes and said circuit means corrects up to (t-x) errors.
Claim 12
Independent Claim
219 words
A method for processing syndrome bytes in a multibyte error correcting system operable to detect up to t errors in a selected codeword containing up to 2 b character positions, where each character is represented by a byte consisting of a unique combination of "b" binary bits, by processing 2t syndrome bytes, each containing "b" bits which were generated by combining write check bytes and read check bytes generated respectively when data is written into and read from a storage medium, said check bytes corresponding to the modulo 2 sum of bit positions of said codeword that were selected systematically in accordance with a parity check matrix reflecting the roots α a , α a+1 , α a+2 , . . . , α a+2t-1 of a generator polynomial where α is an element of the finite field of 2 b elements, the method comprising the steps of: (1) generating 2t syndrome bytes by reading said selected codeword; and (2) developing t+1 coefficients Δ for an error locator polynomial corresponding to said selected codeword by logically combining predetermined combinations of said syndrome bytes to produce cofactors corresponding to coefficients Δ of the error locator polynomial when less than t errors occur, and selectively combining said cofactor bytes with selected syndromes when t errors occur to provide said t+1 coefficients.
Claim 13
Independent Claim
219 words
A method for processing syndrome bytes in a multibyte error correcting system operable to detect up to t errors in a selected codeword containing up to 2 b character positions, where each character is represented by a byte consisting of a unique combination of "b" binary bits, by processing 2t syndrome bytes, each containing "b" bits which were generated by combining write check bytes and read check bytes generated respectively when data is written into and read from a storage medium, said check bytes corresponding to the modulo 2 sum of bit positions of said codeword that were selected systematically in accordance with a parity check matrix reflecting the roots α a , α a+1 , α a+2 , . . . , α a+2t-1 of a generator polynomial where α is an element of the finite field of 2 b elements, the method comprising the steps of: (1) generating 2t syndrome bytes by reading said selected codeword; and (2) developing t+1 coefficients Δ for an error locator polynomial corresponding to said selected codeword by logically combining predetermined combinations of said syndrome bytes to produce cofactors corresponding to coefficients Δ of the error locator polynomial when less than t errors occur, and selectively combining said cofactor bytes with selected syndromes when t errors occur to provide said t+1 coefficients.
Claim 14
Dependent Claim
43 words
The method recited in claim 11 in which said step of developing includes multiplying pairs of selected syndromes as "b" bit vectors to produce a plurality of product output signals and exclusive-ORing selected pairs of said product output signals to produce said cofactors.
Claim 15
Dependent Claim
57 words
The method recited in claim 12 further including multiplying each said cofactor with a different preselected syndrome byte as "b" bit vectors to produce a second set of product output signals and exlusive-ORing selected pairs of said second plurality of product output signals to provide error parameter signals corresponding to said coefficients when t errors are present.
Claim 16
Dependent Claim
27 words
The method recited in claim 13 further including the step of examining a selected error parameter signal to determine if t errors has occurred in said codeword.
Claim 17
Dependent Claim
21 words
The method recited in claim 14 in which a cofactor signal is also examined if less than t errors has occurred.
Claim 18
Dependent Claim
221 words
Circuit means for processing syndromes from a multibytes error correcting system operable to correct up to t errors in a selected codeword containing up to 2 b character positions, where each character is represented by a byte consisting of a unique combination of "b" binary bits, by processing 2t syndrome bytes, each containing "b" bits which were generated by combining write check bytes and read check bytes generated respectively during writing of data onto and reading of data from a storage medium, and which check bytes correspond to the modulo 2 sum of bit positions of said codeword that were selected systematically in accordance with a parity check matrix reflecting the roots α a , α a+1 , α a+2 , . . . , α a+2t-1 of a generator polynomial where α is an element of the finite field of 2 b elements, said circuit means responsive to said 2t syndrome bytes for developing t+1 coefficients Δ for a error locator polynomial corresponding to the selected codeword, said circuit means being characterized by logic means responsive to predetermined combinations of said syndrome bytes to produce cofactors corresponding to coefficients Δ of the error locator polynomial when less than t errors occur, and combining circuitry for selectively combining said cofactor signals when all t errors occur to produce said t+1 coefficients.
Claim 19
Dependent Claim
221 words
Circuit means for processing syndromes from a multibytes error correcting system operable to correct up to t errors in a selected codeword containing up to 2 b character positions, where each character is represented by a byte consisting of a unique combination of "b" binary bits, by processing 2t syndrome bytes, each containing "b" bits which were generated by combining write check bytes and read check bytes generated respectively during writing of data onto and reading of data from a storage medium, and which check bytes correspond to the modulo 2 sum of bit positions of said codeword that were selected systematically in accordance with a parity check matrix reflecting the roots α a , α a+1 , α a+2 , . . . , α a+2t-1 of a generator polynomial where α is an element of the finite field of 2 b elements, said circuit means responsive to said 2t syndrome bytes for developing t+1 coefficients Δ for a error locator polynomial corresponding to the selected codeword, said circuit means being characterized by logic means responsive to predetermined combinations of said syndrome bytes to produce cofactors corresponding to coefficients Δ of the error locator polynomial when less than t errors occur, and combining circuitry for selectively combining said cofactor signals when all t errors occur to produce said t+1 coefficients.
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) | 1988-03-11 | 1988-09-10 | 1989-03-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1992-03-11 | 1992-09-10 | 1993-03-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1996-03-11 | 1996-09-10 | 1997-03-12 | $7700.00 | Window Closed / Lapsed |