Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-10-29
2001-04-17
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S752000
Reexamination Certificate
active
06219816
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a Reed-Solomon encoding device and method and, in particular, to such device and method adapted to error correction of a desired number of blocks not fewer than two.
In data communication, a redundancy signal is generally appended to data (information signal) to be transmitted so that a data error occurring in a transmission path can be detected and corrected at a receiving end. As the redundancy signal to be appended to the information signal, a Reed-Solomon code is widely known.
Examples of a device for carrying out Reed-Solomon encoding are disclosed in Japanese Unexamined Patent Publications (JP-A) Nos. 59-226951 (226951/1984), 60-73752 (73752/1985), and 9-36753 (36753/1997). However, each of these publications discloses no more than a Reed-Solomon encoding device adapted to error correction of a single block or two blocks at most.
In contrast, as a Reed-Solomon encoding circuit adapted to error correction of a desired number of blocks not fewer than two, a circuit using a polynomial division circuit is disclosed in “Essence of Error Correction Encoding Technique” (supervised by Hideki Imai, Japan Industrial Technology Center, 1986), page 30 (hereinafter called a conventional example 1). In addition, a circuit for successively processing input signals in a systolic array structure is disclosed in “A Construction Method for Reed-Solomon Codec Suitable for VLSI Design” (Proceedings of Institute of Electronics, Information, Communication Engineers of Japan, Vol. J71-A, pp. 751-759) (hereinafter called a conventional example 2).
FIG. 1
is a block diagram showing a structure of the Reed-Solomon encoding circuit in the conventional example 1.
The Reed-Solomon encoding circuit of the conventional example 1 comprises a division circuit which is composed of exclusive-OR circuits
531
through
53
n,
Galois field multiplication circuits
541
through
54
n,
and D flop-flops
551
through
55
n,
and which calculates a formula obtained by dividing a polynomial corresponding to an input signal by a generator polynomial. Note that multipliers of the Galois field multiplication circuits
541
through
54
n
are determined from coefficients of the generator polynomial F(x) represented by Equation (1).
F
(
x
)=(
x+&agr;
)(
x+&agr;
2
)(
x+&agr;
3
) . . . (
x+&agr;
m
) (1)
In the above-mentioned Reed-Solomon encoding circuit, a selector
52
is responsive to a count value of a counter
51
and selects either the input information signal or an output signal of the D flop—flop
55
n
as a selector output. Thus, the selector
52
successively outputs the information signal and a Reed-Solomon code as a redundancy code. Herein, by controlling which one is to be outputted from the selector
52
with reference to the count value of the counter
51
, it is possible to produce the Reed-Solomon code permitting error correction of a desired number of blocks.
FIG. 2
is a block diagram showing a structure of the Reed-Solomon encoding circuit in the conventional example 2.
As illustrated in the figure, the Reed-Solomon encoding circuit in the convention example 2 comprises a division circuit formed by connecting in cascade a plurality of processing elements PE illustrated in
FIG. 3
, instead of the division circuit composed of the exclusive-OR circuits
531
through
53
n,
the Galois field multiplication circuits
541
through
54
n,
and the D flop-flops
551
through
55
n
illustrated in FIG.
1
.
However, in each of the circuits in the conventional examples 1 and 2, the information signal is supplied one byte by one byte. Every time when the information signal is supplied, orders or degrees are lowered by one at a time. After completion of input of the information signal, redundancy signals corresponding to respective terms of a remainder polynomial as a result of calculation are successively outputted. Therefore, it takes a long time before completion of the Reed-Solomon encoding.
SUMMARY OF THE INVENTION
It is therefore an object of this invention to provide a Reed-Solomon encoding device and method adapted to error correction of a desired number of blocks not fewer than two and capable of carrying out high-speed encoding by parallel processing.
According to a first aspect of this invention, there is provided a Reed-Solomon encoding device which is supplied with an input signal containing N data signal blocks in each single frame for carrying out a division of dividing by a generator polynomial a polynomial corresponding to the input data signal to produce K redundancy signal blocks corresponding to a remainder obtained by the division and which comprises:
signal output means for outputting the N data signal blocks by J blocks at a time in a time division fashion successively from those corresponding to higher orders in the corresponding polynomial;
adder means, J in number, for calculating, with respect to J data signal blocks outputted from the signal output means and J calculated blocks obtained by a predetermined operation based upon J preceding data signal blocks outputted from the signal output means at a preceding timing, a sum of a pair of the data signal and the calculated blocks corresponding in their orders to each other;
operating means, J in number, responsive to J sum blocks calculated by the J adder means, respectively, for carrying out the predetermined operation to produce the J calculated blocks which correspond to orders lower by J levels than those of the J sum blocks calculated by the J adder means, respectively, and which are supplied to the J adder means, respectively; and
selective output means, J in number, for outputting (N÷J) times J data signal blocks supplied from the signal output means and subsequently outputting (K÷J) times J calculated blocks produced by the J operating means;
N, K, and J being natural numbers where J is a measure (or a divisor) of both of N and K.
With the above-mentioned Reed-Solomon encoding device, it is possible to process the data signal by J blocks at a time in parallel and to produce K redundancy signal blocks successively by J blocks at a time. It is therefore possible to perform high-speed processing as fast as J times as compared with the conventional Reed-Solomon encoding device. Furthermore, as far as N, K, and J are natural numbers where J is a measure of both of N and K, the Reed-Solomon encoding device is capable of producing a Reed-Solomon code permitting error correction even in K is equal to 4 or more, i.e., permitting multiple error correction more than triple error correction.
The Reed-Solomon encoding device according to the first aspect may further comprise:
((N+K)÷J)-ary counting means for counting up at an interval equal to that of output timings of the data signal blocks from the signal output means. In this event:
the J selective output means successively output J data signal blocks supplied from the signal output means when the count value of the counting means is between 0 and (N÷J−1) and successively output J calculated blocks produced by the J operating means when the count value of the counting means is between (N÷J) and ((N+K)÷J−1).
According to a second aspect of this invention, there is provided a Reed-Solomon encoding device which is supplied with an input signal containing N data signal blocks in each single frame for carrying out a division of dividing by a generator polynomial a polynomial corresponding to the input data signal to produce K redundancy signal blocks corresponding to a remainder obtained by the division and which comprises:
auxiliary block appending means for appending I auxiliary blocks to the N data signal blocks;
signal output means for outputting the (N+I) data signal blocks, including the auxiliary blocks appended by the auxiliary block appending means, by J blocks at a time in a time division fashion successibley from those corresponding to higher orders in the corresponding polynomial;
adder means, J in number, for calculat
De'cady Albert
Foley & Lardner
Lamarre Guy
NEC Corporation
LandOfFree
Device and method for carrying out Reed-Solomon encoding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device and method for carrying out Reed-Solomon encoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device and method for carrying out Reed-Solomon encoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2539151