US5757826A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Word-wise processing for reed-solomon codes
Assignee: Maxtor Corp
•
Filing: 1995-07-12
•
Granted: 1998-05-26
•
Expires: 2015-07-12
Abstract
Abstract A word-wise encoder circuit that processes word formatted data blocks in response to a word clock signal and generates redundancy in accordance with an 8 bit symbol code. The encoder is provided with two parallel data paths, each receiving one of the respective bytes halves of the received data words during one word clock period to implement an 8 bit symbol code in response to a word clock signal. The word-wise encoder replicates, in one word clock period, the state of the registers in a standard sequential encoder after two consecutive bytes have been processed in response to a byte clock. In a preferred embodiment, a word-wise encoder is used to implement a Reed-Solomon data integrity code. In this example, the word-wise encoder generates redundancy that is appended to associated data blocks temporarily stored in a block buffer memory within a data channel to provide a mechanism for detecting data errors caused by the buffer. A reduced hardware implementation of a word-wise encoder circuit is disclosed wherein a special choice of generator polynomial and Galois field representation allows a Galois field multiplier to be eliminated. In this embodiment, the encoder generates two bytes of redundancy per data block and the longest propagation path in the encoder traverses one multiplier and two adders.
Inventors
- 👤 Lisa Fredrickson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 06:58
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15; H03M13/151
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
184 words
A method of encoding blocks of data to generate redundancy information according to an 8 bit symbol length code, the 8 bit symbol length code being a Reed-Solomon code characterized by a generator polynomial g(x)=z 2 -z+α 206 , operating over a Galois field having 256 elements, said Galois field being defined by a Galois field generator polynomial p(x)=x 8 +x 4 +x 3 +x 2 +1 and a Primitive alpha element equal to 02x (hexadecimal), the method comprising the steps of: (a) receiving data blocks comprising a multiplicity of 16 bit data words into an encoder; (b) providing first and second parallel input paths, said first and second paths receiving respective first and second symbols of a received data word during a single word clock period; (c) passing said first and said second symbols through corresponding first and second parallel circuit paths of said encoder during a single word clock period; and (d) generating redundancy information from said encoder representative of said data blocks in accordance with the symbol length code after said series of data words has been passed through said encoder.
Claim 2
Independent Claim
184 words
A method of encoding blocks of data to generate redundancy information according to an 8 bit symbol length code, the 8 bit symbol length code being a Reed-Solomon code characterized by a generator polynomial g(x)=z 2 -z+α 206 , operating over a Galois field having 256 elements, said Galois field being defined by a Galois field generator polynomial p(x)=x 8 +x 4 +x 3 +x 2 +1 and a Primitive alpha element equal to 02x (hexadecimal), the method comprising the steps of: (a) receiving data blocks comprising a multiplicity of 16 bit data words into an encoder; (b) providing first and second parallel input paths, said first and second paths receiving respective first and second symbols of a received data word during a single word clock period; (c) passing said first and said second symbols through corresponding first and second parallel circuit paths of said encoder during a single word clock period; and (d) generating redundancy information from said encoder representative of said data blocks in accordance with the symbol length code after said series of data words has been passed through said encoder.
Claim 3
Dependent Claim
29 words
The method of claim 1 wherein said symbol length code is a data integrity code that protects data blocks stored in a block buffer memory in a data channel.
Claim 4
Dependent Claim
16 words
The method of claim 2 wherein said data channel is in a disk drive storage device.
Claim 5
Dependent Claim
13 words
The method of claim 3 wherein the block of data comprises 512 bytes.
Claim 6
Independent Claim
221 words
A method of encoding block formatted data received by an encoder as a series of 16 bit data words according to an 8 bit symbol length Reed-Solomon code characterized by a generator polynomial g(x)=z 2 -z+α 206 , operating over a Galois field having 256 elements, said Galois field defined by a Galois field generator polynomial p(x)=x 8 +x 4 +x 3 +x 2 +1 and a primitive alpha element equal to 02x (hexadecimal), the method comprising the steps of: (a) transmitting data words of a data block to an input of an encoder circuit; (b) providing a clocking signal to said encoder such that said encoder circuitry operates at one-half the rate associated with a symbol rate of the symbol length code; (c) splitting said transmitted data words into first and second data symbols; (d) transmitting said first and second data symbols over first and second parallel paths within said encoder circuit, each of said first and second paths providing a data path to a storage register, each storage register updated with a new storage value directly from the corresponding data path during each word clock period; and (e) outputting generated redundancy information from said storage registers after said series of data words has been passed trough said encoder, said generated redundancy formed in accordance with the symbol length code.
Claim 7
Independent Claim
221 words
A method of encoding block formatted data received by an encoder as a series of 16 bit data words according to an 8 bit symbol length Reed-Solomon code characterized by a generator polynomial g(x)=z 2 -z+α 206 , operating over a Galois field having 256 elements, said Galois field defined by a Galois field generator polynomial p(x)=x 8 +x 4 +x 3 +x 2 +1 and a primitive alpha element equal to 02x (hexadecimal), the method comprising the steps of: (a) transmitting data words of a data block to an input of an encoder circuit; (b) providing a clocking signal to said encoder such that said encoder circuitry operates at one-half the rate associated with a symbol rate of the symbol length code; (c) splitting said transmitted data words into first and second data symbols; (d) transmitting said first and second data symbols over first and second parallel paths within said encoder circuit, each of said first and second paths providing a data path to a storage register, each storage register updated with a new storage value directly from the corresponding data path during each word clock period; and (e) outputting generated redundancy information from said storage registers after said series of data words has been passed trough said encoder, said generated redundancy formed in accordance with the symbol length code.
Claim 8
Dependent Claim
29 words
The method of claim 5 wherein said symbol length code is a data integrity code that protects data blocks stored in a block buffer memory in a data channel.
Claim 9
Dependent Claim
16 words
The method of claim 6 wherein said data channel is in a disk drive storage device.
Claim 10
Dependent Claim
12 words
The method of claim 7 wherein said data block comprises 512 bytes.
Claim 11
Dependent Claim
253 words
An word-wise encoder comprising: a first input and a second input, said first input receiving a first data byte and said second input receiving a second data byte wherein said first and second data bytes together comprise respective halves of a single data word; a first summing circuit connected to said first input, said first summing circuit adding said first data byte to a first feedback byte to produce a first summing circuit output; a second summing circuit connected to said second input, said second summing circuit adding said second data byte to a second feedback byte to produce a second summing circuit output; a third summing circuit connected to said first summing circuit output and to said second summing circuit output, said third summing circuit adding said first summing circuit output and said second summing circuit output together to produce a third summing circuit output; a first multiplier connected to said third summing circuit output for multiplying said third summing circuit output by a fixed value to arrive at a first product output; a first storage register connected to said first product output; a second multiplier connected to said second summing circuit output for multiplying said second summing circuit output by said fixed value to arrive at a second product output; a fourth summing circuit connected to said second product output and to said third summing circuit output for summing these outputs together to produce a fourth summing circuit output; and a second storage register connected to said fourth summing circuit output.
Claim 12
Dependent Claim
253 words
An word-wise encoder comprising: a first input and a second input, said first input receiving a first data byte and said second input receiving a second data byte wherein said first and second data bytes together comprise respective halves of a single data word; a first summing circuit connected to said first input, said first summing circuit adding said first data byte to a first feedback byte to produce a first summing circuit output; a second summing circuit connected to said second input, said second summing circuit adding said second data byte to a second feedback byte to produce a second summing circuit output; a third summing circuit connected to said first summing circuit output and to said second summing circuit output, said third summing circuit adding said first summing circuit output and said second summing circuit output together to produce a third summing circuit output; a first multiplier connected to said third summing circuit output for multiplying said third summing circuit output by a fixed value to arrive at a first product output; a first storage register connected to said first product output; a second multiplier connected to said second summing circuit output for multiplying said second summing circuit output by said fixed value to arrive at a second product output; a fourth summing circuit connected to said second product output and to said third summing circuit output for summing these outputs together to produce a fourth summing circuit output; and a second storage register connected to said fourth summing circuit output.
Claim 13
Dependent Claim
16 words
The apparatus of claim 9 wherein said first and said second multipliers are Galois field multipliers.
Claim 14
Independent Claim
184 words
A method of encoding blocks of data to generate redundancy information according to an 8 bit symbol length code, the 8 bit symbol length code being a Reed-Solomon code characterized by a generator polynomial g(x)=z 2 -α 152 z+1, operating over a Galois field having 256 elements, said Galois field being defined by a Galois field generator polynomial p(x)=x 8 +x 4 +x 3 +x 2 +1 and a primitive alpha elemnent equal to 02x (hexadecimal), the method comprising the steps of: (a) receiving data blocks comprising a multiplicity of 16 bit data words into an encoder; (b) providing first and second parallel input paths, said first and second paths receiving respective first and second symbols of a received data word during a single word clock period; (c) passing said first and said second symbols through corresponding first and second parallel circuit paths of said encoder during a single word clock period; and (d) generating redundancy information from said encoder representative of said data blocks in accordance with the symbol length code after said series of data words has been passed through said encoder.
Claim 15
Independent Claim
184 words
A method of encoding blocks of data to generate redundancy information according to an 8 bit symbol length code, the 8 bit symbol length code being a Reed-Solomon code characterized by a generator polynomial g(x)=z 2 -α 152 z+1, operating over a Galois field having 256 elements, said Galois field being defined by a Galois field generator polynomial p(x)=x 8 +x 4 +x 3 +x 2 +1 and a primitive alpha elemnent equal to 02x (hexadecimal), the method comprising the steps of: (a) receiving data blocks comprising a multiplicity of 16 bit data words into an encoder; (b) providing first and second parallel input paths, said first and second paths receiving respective first and second symbols of a received data word during a single word clock period; (c) passing said first and said second symbols through corresponding first and second parallel circuit paths of said encoder during a single word clock period; and (d) generating redundancy information from said encoder representative of said data blocks in accordance with the symbol length code after said series of data words has been passed through said encoder.
Claim 16
Dependent Claim
29 words
The method of claim 11 wherein said symbol length code is a data integrity code that protects data blocks stored in a block buffer memory in a data channel.
Claim 17
Dependent Claim
16 words
The method of claim 12 wherein said data channel is in a disk drive storage device.
Claim 18
Dependent Claim
13 words
The method of claim 13 wherein the block of data comprises 512 bytes.
Claim 19
Independent Claim
221 words
A method of encoding block formatted data received by an encoder as a series of 16 bit data words according to an 8 bit symbol length Reed-Solomon code characterized by a generator polynomial g(x)=z 2 -α 152 z+1, operating over a Galois field having 256 elements, said Galois field defined by a Galois field generator polynomial p(x)=x 8 +x 4 +x 3 +x 2 +1 and a primitive alpha element equal to 02x (hexadecimal), the method comprising the steps of: (a) transmitting data words of a data block to an input of an encoder circuit; (b) providing a clocking signal to said encoder such that said encoder circuitry operates at one-half the rate associated with a symbol rate of the symbol length code; (c) splitting said transmitted data words into first and second data symbols; (d) transmitting said first and second data symbols over first and second parallel paths within said encoder circuit, each of said first and second paths providing a data path to a storage register, each storage register updated with a new storage value directly from the corresponding data path during each word clock period; and (e) outputting generated redundancy information from said storage registers after said series of data words has been passed through said encoder, said generated redundancy formed in accordance with the symbol length code.
Claim 20
Independent Claim
221 words
A method of encoding block formatted data received by an encoder as a series of 16 bit data words according to an 8 bit symbol length Reed-Solomon code characterized by a generator polynomial g(x)=z 2 -α 152 z+1, operating over a Galois field having 256 elements, said Galois field defined by a Galois field generator polynomial p(x)=x 8 +x 4 +x 3 +x 2 +1 and a primitive alpha element equal to 02x (hexadecimal), the method comprising the steps of: (a) transmitting data words of a data block to an input of an encoder circuit; (b) providing a clocking signal to said encoder such that said encoder circuitry operates at one-half the rate associated with a symbol rate of the symbol length code; (c) splitting said transmitted data words into first and second data symbols; (d) transmitting said first and second data symbols over first and second parallel paths within said encoder circuit, each of said first and second paths providing a data path to a storage register, each storage register updated with a new storage value directly from the corresponding data path during each word clock period; and (e) outputting generated redundancy information from said storage registers after said series of data words has been passed through said encoder, said generated redundancy formed in accordance with the symbol length code.
Claim 21
Dependent Claim
29 words
The method of claim 14 wherein said symbol length code is a data integrity code that protects data blocks stored in a block buffer memory in a data channel.
Claim 22
Dependent Claim
16 words
The method of claim 15 wherein said data channel is in a disk drive storage device.
Claim 23
Dependent Claim
13 words
The method of claim 16 wherein the block of data comprises 512 bytes.
References Cited (Backward Citations)
US4413340A
Cited
US4680764A
Cited
US4777635A
Cited
US5140596A
Cited
US5241546A
Cited
US5422895A
Cited
US5471485A
Cited
US5383204A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-25 | 2001-11-24 | 2002-05-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-25 | 2005-11-24 | 2006-05-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-25 | 2009-11-24 | 2010-05-26 | $7700.00 | Window Closed / Lapsed |