Error correction circuit

Claim 2

An error correction circuit comprising: a buffer memory for storing a plurality of interleaved data streams, each having as an external code an RS code for correcting an error in data and as an internal code a CRC for detecting an error in data; an interface for untying said interleaved data streams; a Galois field operation circuit for carrying out Galois field arithmetic operations on a syndrome of said RS code and determining an error value based on an error location for effecting correction; an RS code sequence circuit for computing said syndrome to find an error location from results of said Galois field arithmetic operations by a Chien search; a CRC coding sequence circuit for coding and computing said CRC, said RS code sequence circuit and said CRC coding sequence circuit being connected in parallel to together form a sequence circuit; and a control circuit for controlling said interface, said Galois field operation circuit, said RS code sequence circuit, and said CRC coding sequence circuit and outputting a control signal for selecting either said RS code sequence circuit or said CRC coding sequence circuit for operation.

Claim 3

The error correction circuit of claim 1, wherein; the plurality of interleaved data streams comprises a like plurality of interleaved code streams; said CRC coding sequence circuit dtermines a first CRC check symbol of a first code stream in said interleaved code streams, which is stored in said Galois field operation circuit; said CRC coding sequence circuit determines a second CRC check symbol of a second code stream, which is logically added to said first CRC check symbol and stored; and means for carrying out, on each successive code stream other than the first and second code streams, determining of an additional CRC check symbol of an additional such successive code stream, which is logically added to said first CRC check symbol and stored, for the number of times equal to the number of interleaved code streams less two and, in coding, writing a resulting CRC check symbol in said Galois field operation circuit in a CRC check symbol portion of said buffer memory while, in decoding, comparing said CRC check symbol with a CRC check code in said buffer memory for detecting an error.

Claim 4

The error correction circuit of claim 1, wherein said CRC coding sequence circuit comprises: first means, responsive to a first code stream of said interleaved data streams, for determining a first CRC check symbol for the first code stream; second means, responsive to a second code stream of said interleaved data streams, for determining a second CRC check symbol for the second code stream; means for logically adding the second CRC check symbol to the first CRC check symbol; additional means, responsive to all code streams of said interleaved data streams, for determining corresponding CRC check symbols respectively therefor; and additional adding means for logically adding and additional CRC check symbols to said logically added first and second CRC check symbols.

Claim 5

The error correction circuit of claim 1, wherein said CRC coding sequence circuit comprises: a first AND gate having a first input connected to the output of said control circuit; a first plurality of registers each connected to be controlled by said control circuit; a first plurality of combining means, each said combining means having a first input connected to the output of a corresponding one of said registers; and a first plurality of multiplication means, each of said multiplication means having an input connected to an output of said AND gate, one of said multiplication means being connected to an input of one of said registers, each of said other multiplication means being connected to a second input of a corresponding one of said combining means, each said multiplication means being for producing a signal representative of an input signal applied thereto multiplied by a predetermined power of a constant, wherein one of said combining means has an output connected to a second input of said AND gate and a second input connected to receive input data and at its first input is also connected to provide output data from another of said registers, and wherein each of the other combining means has an output connected to an input of a corresponding one of all but said one of said registers.

Claim 6

The error correction circuit of claim 1 or 2 or 3 or 4 wherein, in coding, said CRC coding sequence circuit computes said CRC check symbol including said CRC check code portion in said buffer memory after said CRC check code portion in said buffer memory is cleared.

Claim 7

The error correction circuit of claim 1 or 2 or 3 or 4, wherein, in decoding, said CRC coding sequence circuit computes said CRC check symbol including said CRC check code portion of said buffer memory; said Galois field operation circuit computes another CRC check symbol on said CRC check code portion of said buffer memory and logically adds said another CRC check symbol to said CRC check symbol of said CRC coding sequence circuit to eliminate any influence of said CRC check code on said CRC check symbol; said CRC check symbol being compared with said CRC check code in the buffer memory to detect an error.

Claim 8

The error correction of claim 4, wherein said first plurality of combining means comprises a first plurality of OR gates.

Claim 9

The error correction circuit of claim 4, wherein said first plurality of combining means comprises a first plurality of exclusive-OR gates.

Claim 10

The error correction circuit of claim 4, wherein said first plurality of combining means comprises a first plurality of logical adders.

Claim 11

The error correction circuit of claim 1, wherein said control circuit comprises control means for producing said control signal such that for each code stream, said RS code sequence circuit is first selected by said control means to compute an RS code syndrome of that code stream, said CRC coding sequence circuit is then selected by said control means to determine from the syndrome a CRC check symbol for that code stream.

Claim 12

The error correction circuit of claim 10, wherein, in coding, said CRC coding sequence circuit computes said CRC check symbol including said CRC check code portion in said buffer memory after said CRC check code portion in said buffer memory is cleared.

Claim 13

The error correction circuit of claim 10, wherein, in decoding, said CRC coding sequence circuit computes said CRC check symbol including said CRC check code portion of said buffer memory; said Galois field operation circuit computes another CRC check symbol on said CRC check code portion of said buffer memory and logically adds said another CRC symbol to said CRC check symbol of said CRC coding sequence circuit to eliminate any influence of said CRC check code on said CRC check symbol; said CRC check symbol being compared with said CRC check code in the buffer memory to detect an error.

Claim 14

The error correction circuit of claim 10, wherein said CRC coding sequence circuit comprises: first means, responsive to a first code stream of said interleaved data streams, for determining a first CRC check symbol for the first code stream; second means, responsive to a second code stream of said interleaved data streams, for determining a second CRC check symbol for the second code stream; means for logically adding the second CRC check symbol to the first CRC check symbol; additional means, responsive to all code streams of said interleaved data streams, for determining corresponding CRC check symbols respectively therefor; and additional adding means for logically adding said additional CRC check symbols to said logically added first and second CRC check symbols.

Claim 15

The error correction circuit of claim 10, wherein said CRC coding sequence circuit comprises: a first AND gate having a first input connected to the output of said control circuit; a first plurality of registers each connected to be controlled by said control circuit; a first plurality of combining means, each said combining means having a first input connected to the output of a corresponding one of said registers; and a first plurality of multiplication means, each of said multiplication means having an input connected to an output of said AND gate, one of said multiplication means being connected to an input of one of said registers, each of said other multiplication means being connected to a second input of a corresponding one of said combining means, each said multiplication means being for producing a signal representative of an input signal applied thereto multiplied by a predetermined power of a constant, wherein one of said combining means has an output connected to a second input of said AND gate and a second input connected to receive input data and at its first input is also connected to provide output data from another of said registers, and wherein each of the other combining means has an output connected to an input of a corresponding one of all but said one of said registers.

Claim 16

The error correction circuit of claim 14, wherein said first plurality of combining means comprises a first plurality of OR gates.

Claim 17

The error correction circuit of claim 14, wherein said first plurality of combining means comprises a first plurality of exclusive-OR gates.

Claim 18

The error correction circuit of claim 14, wherein said first plurality of combining means comprises a first plurality of logical adders.

Claim 19

The error correction circuit of claim 1, wherein said Galois field arithmetic operations comprise addition, subtraction, multiplication and division in a Galois field.

Claim 22

The error correction method of claim 19, further comprising the step of: between said step of determining the error location polynomial and error value polynomial and said step of determining the CRC check symbol, in the CRC coding sequence circuit determining from the error location polynomial and the error value polynomial the error location of the code word.

Claim 23

The error correction method of claim 20, wherein said apparatus further comprises a buffer memory for storing a plurality of interleaved data streams, each of the streams having as an external code an RS code for correcting an error in data and as an internal code a CRC for detecting an error in data, and an interface interfacing the buffer memory to the Galois field operation circuit, the CRC coding sequence circuit and the RS code sequence circuit and connected to the control circuit for control thereby, the interface being for untying the interleaved data streams, wherein said step of determining the error value comprises: in the Galois field operation circuit, determining from the error location the error value of the code word and correcting the code word.

Claim 24

The error correction method of claim 19, wherein said method further comprises the steps of: in the Galois field operation circuit, logically adding the CRC check symbols together as each subsequent CRC check symbol is generated to produce a sum CRC check symbol; after a CRC check symbol for each code stream is generated and logically added into said sum CRC check symbol, logically adding, in the Galois field operation circuit, said sum CRC check symbol to the CRC check symbol of the RS code to produce a full CRC check symbol; and comparing, in the Galois field operation circuit, the full CRC check symbol with a CRC check symbol in the buffer memory.