Polynomial coefficient generator

Details Polynomial coefficient generator Polynomial coefficient generator

2000-12-19

2004-02-24

Mai, Tan V. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06697830

ABSTRACT:

CROSS-REFERENCE TO RELATED APPLICATION
This application claims the priority benefit of Taiwan application Ser. No. 89100397, filed Jan. 12, 2000.
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates to a circuit capable of rapidly generating all the sub-coefficients of a polynomial multiplication. More particularly, the present invention relates to a polynomial coefficient generator.
2. Description of Related Art
In the error correction system of CD/DVD-ROM, polynomial multiplication is often conducted. To carry out polynomial multiplication, a multiplication circuit is needed. For example, if a polynomial function involves the multiplication of n first degree terms such as:
F
(
x
)=
f
1
(
x
)
f
2
(2)
f
3
(
x
) . . .
f
n−1
(
x
)
f
n
(
x
);
=(1−
a
1
x
)(1−
a
2
x
)(1−
a
3
x
) . . . (1−
a
n−1
x
)(1−
a
n
x
);
=
c
n
x
n
+c
n−1
x
n−1
+ . . . c
2
x
2
+c
1
x+c
0
;
the operational mode is as follows:
F
1
(
x
)=
f
1
(
x
)=(1−
a
1
x
);
F
2
(
x
)=
F
1
(
x
)
f
2
(
x
)=(1−
a
1
x
)(1−
a
2
x
);
 
F
3
(
x
)=
F
2
(
x
)
f
3
(
x
)=
F
2
(
x
)(1−
a
3
x
);
F
n−1
(
x
)=
F
n−2
(
x
)
f
n−1
(
x
)=
F
n−2
(
x
)(1−
a
n−1
x
);
F
n
(
x
)=
F
n−1
(
x
)
f
n
(
x
)=
F
n−1
(
x
)(1−
a
n
x
).
FIG. 1
is a block diagram showing a conventional polynomial coefficient generator. In the polynomial coefficient generator, a polynomial multiplication unit
4
is constructed for processing polynomial multiplication. Using n=16 as an example, because the constant that results from a polynomial multiplication is always 1 (i.e. c
0
=1), the storage device
6
of the circuit has 16 storage units. Each storage unit is used for holding a coefficient (c
1
~c
16
). Initially, zero is stored in all storage units.
To execute the calculation F
1
(x)=f
1
(x)=(1−a
1
x), the first polynomial sub-coefficient a
1
is stored in the storage unit c
1
while zero is still stored in the rest of the storage units c
2
~c
16
.
To execute the next calculation F
2
(x)=F
1
(x)f
2
(x)=(1−a
1
x)(1−a
2
x), the second polynomial sub-coefficient a
2
is carried into the polynomial multiplication unit
4
and values stored inside the storage units of the storage device
6
are fed back to the polynomial multiplication unit
4
. After a computation inside the polynomial unit
4
, values of the coefficients c
1
=(a
1
+a
2
), c
2
=a
1
a
2
are obtained and c
3
~c
16
are still zero Finally, values of the coefficients are transferred to the storage unit
6
.
Similarly, other polynomial sub-coefficients are sequentially input into the polynomial multiplication unit
4
, and values of coefficients stored in the storage unit
6
are fed back to the polynomial multiplication unit
4
each time for following calculation. The computed values of the coefficients are stored into the storage units c
1
~c
16
of the storage device
6
at the end of each calculation. Hence, all the polynomial coefficients of the polynomial multiplication are obtained after 16 computations.
The complexity of a conventional polynomial multiplication unit is greatly increased if the number of polynomial sub-coefficients is increased. Furthermore, cycles of carrying out each calculation are also increased rapidly with an increase of the number of polynomial sub-coefficient in the multiplication. Hence, a polynomial multiplication unit capable of reducing calculation cycles and circuit complexity is a major design goal.
SUMMARY OF THE INVENTION
Accordingly, one object of the present invention is to provide a polynomial coefficient generator whose input terminal is capable of receiving the polynomial sub-coefficients in a polynomial multiplication sequentially and generating all polynomial coefficients of the polynomial multiplication after necessary cycles.
A second object of this invention is to provide a polynomial coefficient generator capable of performing polynomial multiplication by simple logic circuits.
To achieve these and other advantages and in accordance with the purpose of the invention, as embodied and broadly described herein, the invention provides a polynomial coefficient generator. Polynomial sub-coefficients necessary for a polynomial multiplication are sequentially transferred to the input terminal of an input control device. The sub-coefficients are next transferred from the output terminal of the input control device to a plurality of computational circuits at proper phases of clock cycles. The multiple of computational circuits is also activated by the clock pulses. Each computation circuit is capable of generating a related coefficient. Each computational circuit includes an adder input terminal, a multiplication input terminal and a computational output terminal. The adder input terminal of each computational circuit is coupled to the computational output terminal of the previous computational circuit. The adder input terminal of the first computational circuit and the multiplication input terminals of all the computational circuits are coupled to the output terminal of the input control device. Hence, each computational circuit is able to receive the next coefficient from the input control device through the multiplication input terminal at related phases of clock signals. After the next coefficient is multiplied with its internally stored coefficient, an updated coefficient is output via the computational output terminal. Meanwhile, the adder input terminal of each computational circuit also receives a computed value from the computational output terminal of a previous computational circuit.
In an embodiment of this invention, each computational circuit includes a control device, an adder unit, a multiplication unit and a storage unit. The adder unit adds together the values presented to the first input terminal and the second input terminal and produces a new coefficient to be output from the output terminal of the adder unit. The multiplication unit multiplies together the values presented to the first input terminal and the second input terminal and produces a product to be output from the output terminal of the multiplication unit. The input terminal of the storage unit is coupled to the output terminal of the adder unit for receiving the computed coefficient. The computed coefficient is output from the output terminal of the storage unit. The output terminal of the storage unit is coupled to the second input terminal of the adder unit and the second input terminal of the multiplication unit. The adder input terminal of the computational circuit is the first input terminal of the adder unit. The multiplication input terminal of the computational circuit is the first input terminal of the multiplication unit. The computational output terminal of the computational circuit is the output terminal of the control device. The control device is coupled to the output terminal of the multiplication unit. The value presented to the output terminal of the multiplication unit is output from the output terminal of the control device at proper phases of clock cycles.
It is to be understood that both the foregoing general description and the following detailed description are exemplary, and are intended to provide further explanation of the invention as claimed.


REFERENCES:
patent: 3978326 (1976-08-01), Shimomura
patent: 4845713 (1989-07-01), Zook
patent: 5949695 (1999-09-01), Snell
patent: 6513054 (2003-01-01), Carroll

Affiliated with

Also associated with

Rating

Polynomial coefficient generator does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Polynomial coefficient generator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial coefficient generator will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3335590