Quantum Corporation

Maxtor Corporation

Other

Diana L Langer

Lih-Jyh Weng

Bruce Douglas Buch

Ba-Zhong Shen

Bruce A Leshay

Nick Horgan

Justin J Koller

Timothy Proch

Michael D Leis

Cecil Macgregor

A parallel input/output combined encoding and syndrome generating system encodes two information symbols per clock cycle, and thereafter, produces two redundancy symbols per clock cycle. For an n-symbol code word with 2k information symbols c , to c , the symbols c , c , c . . . are supplied, in turn, to a first input line while the symbols c , c , c , . . . are supplied, in turn, to a second input line. In a first clock cycle, the symbol c is combined with the contents of the R registers, where R is the number of redundancy symbols, and the contents are multiplied by the respective roots of the generator polynomial. The products then are combined with the paired symbol c and the resulting sums are multiplied also by the roots of the generator polynomial. These products are then summed in a chain of R adders and the respective registers are appropriately updated with the results of the encoding of the two symbols. During the next clock cycle, the next pair of information symbols are encoded, with c supplied to the first input line and c supplied to the second input line, and so forth. During the k clock cycle, when the last of the pairs of information symbols are being encoded, the system produces the first two redundancy symbols. The first redundancy symbol is the update value for the last register r , and the system then manipulates the update value, to produce the second redundancy symbol in the same clock cycle. The pair of redundancy symbols are next fed back to the two input lines and encoded, as discussed above. For decoding, the chain of R feedback adders is broken, and each set of adders and multipliers operates separately to update the associated register with the results of the manipulation of two code word symbols per clock cycle.

Parallel input output combined system for producing error correction code redundancy symbols and error syndromes

A non-volatile storage subsystem comprises a media I/O controller, a media access channel, and movable storage media. A non-volatile disk storage subsystem bas a read channel coupling a disk controller to a disk head assembly. A read channel interfacing subsystem is provided as part of the storage subsystem, and the read channel interfacing subsystem interfaces a disk controller to the read channel. The read channel interfacing subsystem comprises a set of process units and a pipeline manager.

Data transfer scheme for efficiently moving data through a high latency media access channel

An n-stage pipelined combined encoder and syndrome generator system includes n stages that are essentially identical. Each of the stages includes two associated delay circuits, namely, a first delay circuit in a chain of feedback adders that operate as a feedback path during encoding, and a second delay circuit in a data input line. During encoding operations, the delay circuits in the feedback adder chain segment the chain of j feedback adders into n stages of j/n adders, and the delay circuits in the data input line delay the data symbols by the latencies associated with the respective stages. The delay circuits thus simultaneously provide to the various stages the corresponding data symbols and propagating sums. After the last data symbol is encoded, the ECC symbols are available after a time lag associated with the j/n adders in the last stage. During syndrome generation operations, the feedback adders are essentially decoupled from one another by AND gates that are included in the feedback path and switches in the data input line bypass the delay circuits, to avoid introducing latency into the syndrome generation operations.

Pipelined combined system for producing error correction code symbols and error syndromes for large ECC redundancy

A system for producing a quotient B/A, where A and B are elements of GF(2,), 2M&plus;1 is prime and 2 is a primitive element of GF(2M&plus;1), first determines A,and then multiplies B by A,. The system uses a (2M&plus;1)-bit representation for A and produces, directly from A, an element C&equals;A,, where C also is an element of GF(2,) which is a subfield of GF(2,). The system produces M&plus;1 bits to represent C by performing bit manipulations that are equivalent to permuting the (2M&plus;1)-bits to produce A,and multiplying the permuted bits by A. The bit manipulations are: c,&equals;&Sgr;a,a,; c,&equals;&Sgr;a,a,. . . c,&equals;&Sgr;a,a,where the a,'s and c,'s are the coefficients of A and C, respectively. The system retrieves C,from a (2,&minus;1)-element lookup table and multiplies C,&equals;A,by A,to produce A,. This multiplication is performed as the exclusive-OR'ing of M&plus;1 sums of cyclically shifted copies of A,, which is a permutation of the 2,&plus;1 bits of A. The multiplication of B by A,is also performed as the exclusive-OR'ing of cyclically shifted copies of a (2M&plus;1)-bit representation of B.

Circuit for determining multiplicative inverses in certain galois fields

A method of data transfer in a data processing system having at least one source buffer and at least one destination buffer. The source buffer includes a plurality of data blocks, each data block having an address and being for storage of data including an identifier uniquely identifying that data block. The destination buffer includes a plurality of data blocks corresponding to the data blocks of the source buffer, each destination block having an address and being for storage of data. Each source block identifier is a function of a corresponding destination block address. Transferring data from the source buffer to the destination buffer includes: (a) obtaining the address of a data block in the destination buffer to transfer data into; (b) obtaining the address of a corresponding data block in the source buffer to transfer data from; and (c) checking the integrity of said addresses before data transfer, including: (i) retrieving the source block identifier in the source block via the source block address; (ii) generating an expected identifier value for the source block from the address of the destination block via said function relation between the source block identifier and the destination block address; (iii) comparing the expected identifier value with the retrieved identifier value; and (iv) if there is a mismatch, signaling an error condition representing corruption of one or more of the source block and the destination block addresses.

Method for preventing transfer of data to corrupt addresses

A Galois field multiplier for GF(2.sup.n), with n=2m, multiplies two n-bit polynomials to produce a(x)*b(x)=a(x)b(x) mod g(x), where g(x) is a generator polynomial for the Galois field and '*' represents multiplication over the Galois field, by treating each polynomial as the sum of two m-bit polynomials:

Galois field multiplier

A Reed-Solomon error-correction coding (ECC) scheme selectively supports two different-length codes to optimize the trade-off between error performance and the amount of disk space required to store protection symbols. The encoder contains two sets of alpha multipliers; part of one set is multiplexed with the other depending on which code is being used. Also, a shift register within the encoder is selectively lengthened or shortened depending on the code. The code pair is selected so that the generator polynomial of the shorter code is a complete divisor of the generator polynomial of the longer code. Thus, one code is a sub-code of the other. Accordingly, the ECC system is able to use the same syndrome calculator for each code. The error-correction decoder uses those syndromes that correspond to the roots of the generator polynomial of the code being used.

ECC system supporting different-length Reed-Solomon codes whose

An encoder in a data processing system generates, from a single m-bit coset leader constant, or symbol, a coset leader, which is a series of k m-bit symbols that resembles a random sequence of km bits. The encoder encodes the m-bit initial coset leader constant in a linear feedback shift register that is characterized by a maximum length polynomial over GF(2). The constants are produced by the register at the same times as the error correction symbols are produced by the encoder. The corresponding constants and symbols are then XOR'd together before the symbols are concatenated with the data symbols to form a code word for recording. A decoder similarly generates the coset leader from the initial constant. The decoder XOR's these constants with the error correction symbols in a retrieved code word as part of a demodulation operation. If the head was in synchronism with the stored information during a read operation, XOR'ing the k coset leader constants with the error correction symbols of the retrieved code word removes the coset leader from these symbols, and thus, reproduces the original error correction symbols. Otherwise, the XOR operation combines the coset leader with a shifted version of itself and introduces into the retrieved code word a number of errors that exceeds the error correction capability of the error correction code used to encode the data. In the preferred embodiment, the linear feedback shift register is characterized by the maximum length polynomial X.sup.9 +X.sup.8 +X.sup.7 +X.sup.3 +X.sup.2 +1 over GF(2), and the m-bit initial coset leader constant is 100001011.

Method and apparatus for protecting data from mis-synchronization errors

A method and system for verifying the integrity of data written to a mass memory medium. A local memory is directed by local memory control logic to store a data block that is received from a host microprocessor and that is to be written to the mass memory medium. The data block comprises a sequence of data symbols. An ECC encoder encodes the stored data block with error correction data. The error correction data comprises a sequence of error correction symbols that are appended to the data symbols. The data and error correction symbols are stored in the mass memory and immediately retrieved. An ECC decoder receives the retrieved data and error correction symbols from the mass memory and the data and error correction symbols of the encoded data block from the encoder. In response, the decoder generates an error status signal when more than a predetermined threshold number of the retrieved data and error correction symbols are improperly stored in the mass memory. The local memory control logic receives the error status signal and generates in response a second error status signal. The host microprocessor receives the second error status signal and generates in response remedial action signals.

Growing community of inventors

Northborough, MA, United States of America

Diana L Langer