Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-12-23
2002-01-22
Lee, Thomas (Department: 2182)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S491000, C714S781000, C714S784000, C714S785000
Reexamination Certificate
active
06341297
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a syndrome polynomial calculating circuit and a Reed-Solomon decoding circuit. More particularly, it relates to a Reed-Solomon decoding circuit, preferably applied to a system exemplified by a high-speed large-capacity optical communication system, for which a high throughput is a requirement, and to a syndrome polynomial calculating circuit used in the Reed-Solomon decoding circuit.
BACKGROUND OF THE INVENTION
Conventionally, for a Reed-Solomon decoding circuit, there is known a method of sequentially processing input signals by a systolic array structure as disclosed in a literature “VLSI-oriented Reed Solomon Coding and Decoding System”, Journal of the Society of Electronic Information Communication, Vol.J.71-A, pp.751 to 759.
In the system disclosed in the above literature, a unit structure termed PE, shown in
FIG. 5
, is used for processing. Referring to
FIG. 5
, seven signals A, B, C, D, E, I and J are entered as input signals, of which the signals A, B, D and E are sent to a selector
501
, that is also fed with control signals S
1
and S
2
. A first output of the selector
501
is sent to a second D-flipflop (D-F/F)
508
, while a second output thereof is branched into three which are entered to a first input of a first Galois field multiplication circuit
502
and to an input of the first D-flipflop
505
(D-F/F) and are output to an output G.
A third output of the selector
501
is branched into three which are entered to a first input of a second Galois field multiplication circuit
503
and to an input of the fifth D-flipflop
507
(D-F/F) and are output to an output H.
An input signal I is entered to a second input of the first Galois field multiplication circuit
502
, while an input signal J is entered to a second input of the second Galois filed multiplication circuit
503
.
An output of the first Galois filed multiplication circuit
502
is entered to a first input of an exclusive OR circuit
504
, while an output of the second Galois filed multiplication circuit
503
is entered to a second input of the exclusive OR circuit
504
.
Outputs of the first to fifth D-F/Fs
505
,
508
,
506
,
509
and
507
are issued as outputs O, R, Q, T and P, respectively.
In the conventional example, a variety of processing operations is performed on the PE as a unit. A syndrome polynomial calculating unit, an Euclidean algorithm method, Chain solution and an error value calculation unit are implemented by interconnecting PEs.
The syndrome polynomial calculating unit is implemented by interconnecting (K+1) PEs in series, a to a
(K+1)
. Also, C is fixed at “0”, J is fixed at “0” and an output of P of a previous stage PE is entered to B. In this case, a Q-output of the PE of the last stage becomes an output of the syndrome polynomial.
As for outputs of a selector, C and B are selected in the first PE as outputs of X and Y, respectively. In the following PEs, A and B are selected as X and Y, respectively.
In the Euclidean algorithm calculating unit, (K+2) PEs are connected in series, and outputs of respective previous stage(s) R, Q and T are entered to A, C and B of the next stage(s).
In the individual PEs, outputs of H and G are entered to a respective register which holds initially entered values. The register holds the value during calculation processing to enter the values to inputs I and J, respectively, as shown in FIG.
7
.
Also, outputs O and P are sent to inputs D and E, respectively. In the initial stage PE, the calculated results of the syndrome polynomial are entered to A, while C is fixed at “0”, and “1” is entered only at the initial bit of B.
In the respective PEs, signals selected by the selectors are changed depending on the processing results of the previous stage(s). That is, for the respective PEs, the mode is changed to nop, reDuceA and reDuceB, depending on the order number of the output signals R, Q and T. In keeping therewith, A and B are selected for X and Y, respectively, in the downstream side selector in the case of nop. In the case of reDuceA, C and B are selected for X and Y, respectively, whereas, in the case of reDuceB, A and C are selected for X and Y, respectively.
This outputs an error position polynomial and an error value polynomial from R and Q of the last-stage PE, respectively.
In the downstream side, two PEs are configured as a reciprocal calculating circuit of the Galois field, as shown in FIG.
8
. To I, J, A and B are entered polynomials calculated by the Euclidean algorithm method and differentiated values thereof. An output Q of the initial stage PE is sent to a Galois field reciprocal calculating circuit, an output of which is sent to an input B of the next stage PE. In this case, the signal of an output Q of the last stage PE serves as the information of the error position and the error value, by which the error values are corrected.
SUMMARY OF THE DISCLOSURE
However, if, with the above-described conventional technique, high-speed signals are to be decoded, the syndrome circuit needs to be operated by clocks of the same rate as the signal. Thus, for processing a large capacity signal of the order of Gb/s, the signals are time-divisionally multiplexed to an allowable processing speed prior to processing. This raises a problem of an increased device scale.
There is raised a further problem of signal delay caused by signal separation.
Since the Euclidean algorithm circuit, Chain solution circuit or the error value calculation unit can be operated also at a speed slower than the signal speed, speedup of the processing speed of the syndrome circuit is crucial in decoding.
In view of the above-mentioned problems, it is an object of the present invention to provide a syndrome polynomial calculation circuit and Reed Solomon compounding circuit capable of performing a high-speed operation.
For accomplishing the above object, a first aspect of the present invention provides a Galois field substitution circuit which includes first to jth Galois field multiplication circuits, and a (J+1) input exclusive OR circuit. A first block of j blocks of input time-divisionally multiplexed signals is entered to a first input of the exclusive OR gate, second to jth block signals are entered to the first to (j−1)th Galois field multiplication circuits, and outputs of the first to (j−1)th Galois field multiplication circuits are entered to second to jth inputs of the exclusive OR gate.
The Galois field substitution circuit also includes a latch circuit for latching an output of the exclusive OR gate with input clock signals, a counter for setting a control output signal to logical 1 on counting the input clock signals by one frame, and a gating circuit for selectively outputting an output of the latch circuit based on the control output signal of the counter.
An output of the latch circuit is entered to the jth Galois field multiplication circuit, and an output of the jth Galois field multiplication circuit is connected to a (j+1)st input of the exclusive OR gate. A multiplication circuit of each Galois field is designed such that the power of the Galois field “a” is p to jp. The output of the latch circuit and the counter are reset at a time point of inputting of the one-frame signal.
In a syndrome polynomial calculating circuit according to a second aspect of the present invention, j-blocks of input signals are branched into two signal portions, one of which is entered to second to (j+1)th D-flipflops and the other of which is entered to the Galois field substitution circuits. K of the circuits are connected in series, with outputs of each of the Galois field substitution circuits being entered to a logical sum circuit. An output of the logical sum circuit is issued as an output of the syndrome polynomial calculating circuit.
In a third aspect of the present invention, there is provided a Reed-Solomon decoding circuit which includes the syndrome polynomial calculating circuit aforementioned, a Euclidean algorithm calculating circuit, first to Kth Chain solution
Foley & Lardner
Lee Thomas
Mai Rijue
NEC Corporation
LandOfFree
Parallel processing syndrome calculating circuit and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parallel processing syndrome calculating circuit and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel processing syndrome calculating circuit and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2847107