Apparatus for encoding and decoding reed-solomon code

Claim 2

An encoder comprising: a plurality of arithmetic circuits each of which includes: selector means having a plurality of inputs and at least one output, multiplying means over a Galois field which has a plurality of outputs and has the at least one output of said selector means as an input thereof, adder means for adding the outputs of said multiplying means and having an output, and register means for storing the output of said adder means and at least one output of said selector means, wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits to perform the encoding in a pipeline mode.

Claim 3

An encoder according to claim 1, wherein all said arithmetic circuits have the same structure.

Claim 4

A code decoder comprising: a plurality of arithmetic circuits each of which includes: selector means having a plurality of inputs and at least one output, multiplying means over a Galois field which has a plurality of outputs and has the at least one output of said selector means as an input thereof, adder means for adding the outputs of said multiplying means and having an output, and register means for storing the output of said adder means and at least one output of said selector means, wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits to perform the decoding in a pipeline mode.

Claim 5

A code decoder comprising: a plurality of arithmetic circuits each of which includes: selector means having a plurality of inputs and at least one output, multiplying means over a Galois field which has a plurality of outputs and has the at least one output of said selector means as an input thereof, adder means for adding the outputs of said multiplying means and having an output, and register means for storing the output of said adder means and at least one output of said selector means, wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits to perform the decoding in a pipeline mode.

Claim 6

A decoder according to claim 3, wherein all said arithmetic circuits have the same structure.

Claim 7

A decoder comprising: a plurality of arithmetic circuits each of which includes: selector means having a plurality of inputs and at least one output, multiplying means over a Galois field which has a plurality of outputs and has the at least one output of said selector means as an input thereof, adder means for adding the outputs of said multiplying means and having an output, and register means having a plurality of stages for storing the output of said adder means and at least one output of said selector means, said register means feeding at least one output of the plurality of stages back to said selector means, wherein each of said plurality of arithmetic circuits is connected to at least one of the other arithmetic circuits by sending at least one output of the stages of said register means to said selector means of the other arithmetic circuits or by receiving at least one output of the stages of said register means from the other arithmetic circuits as one of the inputs of said selector means.

Claim 8

A decoder comprising: a plurality of arithmetic circuits each of which includes: selector means having a plurality of inputs and at least one output, multiplying means over a Galois field which has a plurality of outputs and has the at least one output of said selector means as an input thereof, adder means for adding the outputs of said multiplying means and having an output, and register means having a plurality of stages for storing the output of said adder means and at least one output of said selector means, said register means feeding at least one output of the plurality of stages back to said selector means, wherein each of said plurality of arithmetic circuits is connected to at least one of the other arithmetic circuits by sending at least one output of the stages of said register means to said selector means of the other arithmetic circuits or by receiving at least one output of the stages of said register means from the other arithmetic circuits as one of the inputs of said selector means.

Claim 9

An encoder which inputs information and outputs parity as a remainder produced by a generator polynomial, said encoder comprising: a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register for storing the output of said adder and at least one output of said selector, wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits to encode perform the encoding in a pipeline mode.

Claim 10

An encoder which inputs information and outputs parity as a remainder produced by a generator polynomial, said encoder comprising: a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register for storing the output of said adder and at least one output of said selector, wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits to encode perform the encoding in a pipeline mode.

Claim 11

A Reed-Solomon code decoder comprising: a syndrome generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register for storing the output of said adder and at least one output of said selector, wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits and said syndrome generator generates from input signals r n-1 , r n-2 , . . . r 1 , r 0 in a pipeline mode a syndrome S j expressed by the following formula: S.sub.j-1 =( . . . ((r.sub.n-1 *α.sup.j +r.sub.n-2)*α.sup.j +r.sub.n-3)* . . . *α.sup.j +r.sub.0.

Claim 12

A Reed-Solomon code decoder comprising: a syndrome generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register for storing the output of said adder and at least one output of said selector, wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits and said syndrome generator generates from input signals r n-1 , r n-2 , . . . r 1 , r 0 in a pipeline mode a syndrome S j expressed by the following formula: S.sub.j-1 =( . . . ((r.sub.n-1 *α.sup.j +r.sub.n-2)*α.sup.j +r.sub.n-3)* . . . *α.sup.j +r.sub.0.

Claim 13

A Reed-Solomon code decoder comprising: a greatest common divisor polynomial generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register for storing the output of said adder and at least one output of said selector, wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits and said greatest common divisor polynomial generator generates a greatest common divisor polynomial from received polynomials in a pipeline.

Claim 14

A Reed-Solomon code decoder comprising: a greatest common divisor polynomial generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register for storing the output of said adder and at least one output of said selector, wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits and said greatest common divisor polynomial generator generates a greatest common divisor polynomial from received polynomials in a pipeline.

Claim 15

A Reed-Solomon code decoder comprising: an error location and error value generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register for storing the output of said adder means and at least one output of said selector means, wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that they are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits and said error location and error value generator detects a location and a value of an error by calculating the value of polynomials in a pipeline.

Claim 16

A Reed-Solomon code decoder comprising: an error location and error value generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register for storing the output of said adder means and at least one output of said selector means, wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that they are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits and said error location and error value generator detects a location and a value of an error by calculating the value of polynomials in a pipeline.

Claim 17

A Reed-Solomon code decoder comprising: an erasure position polynomial generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplying means and having an output, and a register for storing the output of said adder and at least one output of said selector, wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits and said erasure position polynomial generator receives values y i , (i=1, 2, . . . , s) and determines the coefficients of the following polynomial in a pipeline mode: λ(x)=(1-y.sub.1 ·x)·(1-y.sub.2 ·x) . . . (1-y.sub.s ·x).

Claim 18

A Reed-Solomon code decoder comprising: an erasure position polynomial generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplying means and having an output, and a register for storing the output of said adder and at least one output of said selector, wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits and said erasure position polynomial generator receives values y i , (i=1, 2, . . . , s) and determines the coefficients of the following polynomial in a pipeline mode: λ(x)=(1-y.sub.1 ·x)·(1-y.sub.2 ·x) . . . (1-y.sub.s ·x).

Claim 19

A Reed-Solomon code encoder comprising: a code polynomial generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register having a plurality of stages for storing the output of said adder and at least one output of said selector, said register feeding at least one output of the plurality of stages back to said selector, wherein each of said plurality of arithmetic circuits is connected to at least one of other of said plurality of arithmetic circuits by sending at least one output of the stages of said register to said selector of the other arithmetic circuits or by receiving at least one output of the stages of said register from the other arithmetic circuits as one of the inputs of said selector, and wherein said code polynomial generator generates a code polynomial p(x) expressed by the following formula from information i k-1 , i k-2 , . . . , i 0 and a generator polynomial g(x) in a pipeline mode:ps p(x)=I(x)·x.sup.2t mod g(x), where I(x)=i k-1 ·x k-1 +i k-2 ·x k-2 +. . . +i 0 and t represents error-correcting capability.

Claim 20

A Reed-Solomon code encoder comprising: a code polynomial generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register having a plurality of stages for storing the output of said adder and at least one output of said selector, said register feeding at least one output of the plurality of stages back to said selector, wherein each of said plurality of arithmetic circuits is connected to at least one of other of said plurality of arithmetic circuits by sending at least one output of the stages of said register to said selector of the other arithmetic circuits or by receiving at least one output of the stages of said register from the other arithmetic circuits as one of the inputs of said selector, and wherein said code polynomial generator generates a code polynomial p(x) expressed by the following formula from information i k-1 , i k-2 , . . . , i 0 and a generator polynomial g(x) in a pipeline mode:ps p(x)=I(x)·x.sup.2t mod g(x), where I(x)=i k-1 ·x k-1 +i k-2 ·x k-2 +. . . +i 0 and t represents error-correcting capability.

Claim 21

A Reed-Solomon code decoder comprising: a syndrome generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register having a plurality of stages for storing the output of said adder and at least one output of said selector, said register feeding at least one output of the plurality of stages back to said selector, wherein each of said plurality of arithmetic circuits is connected to at least one of other of said plurality of arithmetic circuits by sending at least one output of the stages of said register to said selector of the other arithmetic circuits or by receiving at least one output of the stages of said register from the other arithmetic circuits as one of the inputs of said selector, and wherein said syndrome generator generates a syndrome S j expressed by the following formula from input symbols r n-1 , r n-2 , . . . r 1 , r 0 : S.sub.j-1 =( . . . ((r.sub.n-1 *α.sup.j +r.sub.n-2)*α.sup.j +r.sub.n-2)*α.sup.j +r.sub.n-1) * . . . *α.sup.j +r.sub.1)*α.sup.j +r.sub.0 where j=1, 1+1, . . . 1+2t-1 and 1 indicates a desired integer and t represents error correcting capability.

Claim 22

A Reed-Solomon code decoder comprising: a syndrome generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register having a plurality of stages for storing the output of said adder and at least one output of said selector, said register feeding at least one output of the plurality of stages back to said selector, wherein each of said plurality of arithmetic circuits is connected to at least one of other of said plurality of arithmetic circuits by sending at least one output of the stages of said register to said selector of the other arithmetic circuits or by receiving at least one output of the stages of said register from the other arithmetic circuits as one of the inputs of said selector, and wherein said syndrome generator generates a syndrome S j expressed by the following formula from input symbols r n-1 , r n-2 , . . . r 1 , r 0 : S.sub.j-1 =( . . . ((r.sub.n-1 *α.sup.j +r.sub.n-2)*α.sup.j +r.sub.n-2)*α.sup.j +r.sub.n-1) * . . . *α.sup.j +r.sub.1)*α.sup.j +r.sub.0 where j=1, 1+1, . . . 1+2t-1 and 1 indicates a desired integer and t represents error correcting capability.

Claim 23

A Reed-Solomon code decoder comprising: a greatest common divisor polynomial generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of output and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register having a plurality of stages for storing the output of said adder and at least one output of said selector, said register feeding a least one output of the plurality of stages back to said selector, wherein each of said plurality of arithmetic circuits is connected to at least one of other of said plurality of arithmetic circuits by sending at least one output of the stages of said register to said selector of the other arithmetic circuits or by receiving at least one output of the stages of said register from the other arithmetic circuits as one of the inputs of said selector, and wherein said greatest common divisor polynomial generator generates a greatest common divisor polynomial from received polynomials.

Claim 24

A Reed-Solomon code decoder comprising: a greatest common divisor polynomial generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of output and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register having a plurality of stages for storing the output of said adder and at least one output of said selector, said register feeding a least one output of the plurality of stages back to said selector, wherein each of said plurality of arithmetic circuits is connected to at least one of other of said plurality of arithmetic circuits by sending at least one output of the stages of said register to said selector of the other arithmetic circuits or by receiving at least one output of the stages of said register from the other arithmetic circuits as one of the inputs of said selector, and wherein said greatest common divisor polynomial generator generates a greatest common divisor polynomial from received polynomials.

Claim 25

A Reed-Solomon code decoder comprising: an error position and error value generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register having a plurality of stages for storing the output of said adder and at least one output of said selector, said register feeding at least one output of the plurality of stages back to said selector, wherein each of said plurality of arithmetic circuits is connected to at least one of other of said plurality of arithmetic circuits by sending at least one output of the stages of said register to said selector of the other arithmetic circuits or by receiving at least one output of the stages of said selector from the other arithmetic circuits as one of the inputs of said selector, and wherein said error position and error value generator detects a position and value of an error by calculating the value of polynomials.

Claim 26

A Reed-Solomon code decoder comprising: an error position and error value generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has the at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier and having an output, and a register having a plurality of stages for storing the output of said adder and at least one output of said selector, said register feeding at least one output of the plurality of stages back to said selector, wherein each of said plurality of arithmetic circuits is connected to at least one of other of said plurality of arithmetic circuits by sending at least one output of the stages of said register to said selector of the other arithmetic circuits or by receiving at least one output of the stages of said selector from the other arithmetic circuits as one of the inputs of said selector, and wherein said error position and error value generator detects a position and value of an error by calculating the value of polynomials.

Claim 27

A Reed-Solomon code decoder comprising: an erasure position polynomial generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier means and having an output, and a register having a plurality of stages for storing the output of said adder and at least one output of said selector, said register feeding at least one output of the plurality of stages back to said selector. wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits and said erasure position polynomial generator receives values Y i , (I=1, 2, . . . , s) and determines the coefficients of the following polynomial in a pipeline mode: λ(x)=(1-y.sub.1 ·x)·(1-y.sub.2 ·x) . . . (1-y.sub.s ·x).

Claim 28

A Reed-Solomon code decoder comprising: an erasure position polynomial generator which has a plurality of arithmetic circuits each of which includes: a selector having a plurality of inputs and at least one output, a multiplier over a Galois field which has a plurality of outputs and has at least one output of said selector as an input thereof, an adder for adding the outputs of said multiplier means and having an output, and a register having a plurality of stages for storing the output of said adder and at least one output of said selector, said register feeding at least one output of the plurality of stages back to said selector. wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits and said erasure position polynomial generator receives values Y i , (I=1, 2, . . . , s) and determines the coefficients of the following polynomial in a pipeline mode: λ(x)=(1-y.sub.1 ·x)·(1-y.sub.2 ·x) . . . (1-y.sub.s ·x).

Claim 29

An encoder/decoder comprising: a plurality of arithmetic circuits each of which includes: selector means having a plurality of inputs and at least one output, multiplying means over a Galois field which has a plurality of outputs and has the at least one output of said selector means as an input thereof, adder means for adding the outputs of said multiplying means and having an output, and register means for storing the output of said adder means and at least one output of said selector means, wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is i turn connected in series with the remainder of said circuits to perform the encoding and decoding in a pipeline mode.

Claim 30

An encoder/decoder comprising: a plurality of arithmetic circuits each of which includes: selector means having a plurality of inputs and at least one output, multiplying means over a Galois field which has a plurality of outputs and has the at least one output of said selector means as an input thereof, adder means for adding the outputs of said multiplying means and having an output, and register means for storing the output of said adder means and at least one output of said selector means, wherein said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is i turn connected in series with the remainder of said circuits to perform the encoding and decoding in a pipeline mode.

Claim 31

An encoder comprising: a plurality of arithmetic circuits each of which includes: selector means having a plurality of inputs and at least one output, multiplying means over a Galois field which has a plurality of outputs and has the at least one output of said selector means as an input thereof, adder means for adding the outputs of said multiplying means and having an output, and register means having a plurality of stages for storing the output of said adder means and at least one output of said selector means, said register means feeding at least one output of the plurality of stages back to said selector means, wherein each of said plurality of arithmetic circuits is connected to at least one of other of said plurality of arithmetic circuits by sending at least one output of the stages of said register means to said selector means of the other arithmetic circuits or by receiving at least one output of the stages of said register means from the other arithmetic circuits as one of the inputs of said selector means.

Claim 32

An encoder comprising: a plurality of arithmetic circuits each of which includes: selector means having a plurality of inputs and at least one output, multiplying means over a Galois field which has a plurality of outputs and has the at least one output of said selector means as an input thereof, adder means for adding the outputs of said multiplying means and having an output, and register means having a plurality of stages for storing the output of said adder means and at least one output of said selector means, said register means feeding at least one output of the plurality of stages back to said selector means, wherein each of said plurality of arithmetic circuits is connected to at least one of other of said plurality of arithmetic circuits by sending at least one output of the stages of said register means to said selector means of the other arithmetic circuits or by receiving at least one output of the stages of said register means from the other arithmetic circuits as one of the inputs of said selector means.

Claim 33

An encoder/decoder comprising: a plurality of arithmetic circuits each of which includes: selector means having a plurality of inputs and at least one output, multiplying means over a Galois field which has a plurality of outputs and has the at least one output of said selector means as an input thereof, adder means for adding the outputs of said multiplying means and having an output, and register means having a plurality of stages for storing the output of said adder means and at least one output of said selector means, said registers means feeding at least one output of the plurality of stages back to said selector means, wherein each of said plurality of arithmetic circuits is connected to at least one of other of said plurality of arithmetic circuits by sending at least one output of the stages of said register means to said selector means of the other arithmetic circuits or by receiving at least one output of the stages of said register means from the other arithmetic circuits as one of the inputs of said selector means.

Claim 34

An encoder/decoder comprising: a plurality of arithmetic circuits each of which includes: selector means having a plurality of inputs and at least one output, multiplying means over a Galois field which has a plurality of outputs and has the at least one output of said selector means as an input thereof, adder means for adding the outputs of said multiplying means and having an output, and register means having a plurality of stages for storing the output of said adder means and at least one output of said selector means, said registers means feeding at least one output of the plurality of stages back to said selector means, wherein each of said plurality of arithmetic circuits is connected to at least one of other of said plurality of arithmetic circuits by sending at least one output of the stages of said register means to said selector means of the other arithmetic circuits or by receiving at least one output of the stages of said register means from the other arithmetic circuits as one of the inputs of said selector means.

Claim 35

A decoder comprising: a first unit for generating a syndrome from input signals; a second unit connected to said first unit for calculating an error location polynomial and an error evaluation polynomial on the basis of the syndrome generated by said first unit; a third unit connected to said second unit for estimating an error location and an error value from the error location polynomial and the error evaluation polynomial calculated by said second unit; and a fourth unit connected to said third unit for correcting an error according to the error location and the error value estimated by said third unit, wherein each of said units has at least one arithmetic circuit which includes: selector means having a plurality of inputs and at least one output, multiplying means over a Galois field which has a plurality of output and has the at least one output of said selector means as an input thereof, adder means for adding the outputs of said multiplying means and having an output, and register means for storing the output of said adder means and at least one output of said selector means, where a plurality of said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits to perform decoding in a pipeline mode.

Claim 36

A decoder comprising: a first unit for generating a syndrome from input signals; a second unit connected to said first unit for calculating an error location polynomial and an error evaluation polynomial on the basis of the syndrome generated by said first unit; a third unit connected to said second unit for estimating an error location and an error value from the error location polynomial and the error evaluation polynomial calculated by said second unit; and a fourth unit connected to said third unit for correcting an error according to the error location and the error value estimated by said third unit, wherein each of said units has at least one arithmetic circuit which includes: selector means having a plurality of inputs and at least one output, multiplying means over a Galois field which has a plurality of output and has the at least one output of said selector means as an input thereof, adder means for adding the outputs of said multiplying means and having an output, and register means for storing the output of said adder means and at least one output of said selector means, where a plurality of said arithmetic circuits are arranged such that they are connected in series with each other or such that some of said arithmetic circuits are connected in parallel with each other to form a block which is in turn connected in series with the remainder of said circuits to perform decoding in a pipeline mode.

Claim 37

A decoder comprising: a first unit for generating a syndrome from input signals; a second unit connected to said first unit for calculating an error location polynomial and an error evaluation polynomial on the basis of the syndrome generated by said first unit; a third unit connected to said second unit for estimating an error location and an error value from the error location polynomial and the error evaluation polynomial calculated by said second unit; and a fourth unit connected to said third unit for correcting an error according to the error location and the error value estimated by said third unit, wherein each of said units has at least one arithmetic circuit which includes: selector means having a plurality of inputs and at least one output, multiplying means over a Galois field which has a plurality of outputs and has the at least one output of said selector means as an input thereof, adder means for adding the outputs of said multiplying means and having an output, and register means having a plurality of stages for storing the output of said adder means and at least one output of said selector means, said register means feeding at least one output of the plurality of stages back to said selector means.

Claim 38

A decoder comprising: a first unit for generating a syndrome from input signals; a second unit connected to said first unit for calculating an error location polynomial and an error evaluation polynomial on the basis of the syndrome generated by said first unit; a third unit connected to said second unit for estimating an error location and an error value from the error location polynomial and the error evaluation polynomial calculated by said second unit; and a fourth unit connected to said third unit for correcting an error according to the error location and the error value estimated by said third unit, wherein each of said units has at least one arithmetic circuit which includes: selector means having a plurality of inputs and at least one output, multiplying means over a Galois field which has a plurality of outputs and has the at least one output of said selector means as an input thereof, adder means for adding the outputs of said multiplying means and having an output, and register means having a plurality of stages for storing the output of said adder means and at least one output of said selector means, said register means feeding at least one output of the plurality of stages back to said selector means.