Multiplex communications – Generalized orthogonal or special mathematical techniques – Fourier transform
Reexamination Certificate
1998-04-29
2001-05-29
Ton, Dang (Department: 2661)
Multiplex communications
Generalized orthogonal or special mathematical techniques
Fourier transform
Reexamination Certificate
active
06240062
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to a signal processing apparatus and a signal processing method. More particularly, the invention relates to a signal processing apparatus and a signal processing method which are heavily used in, for example, fast FOURIER transform.
2. Description of the Related Art
Fast FOURIER transform (FFT) used in, for example, Digital Video Broadcasting-Terrestrial (DVB-T), is implemented by repeating complex calculations, which are referred to as “butterfly calculations”.
In butterfly calculations, the number of data items that are calculated simultaneously varies according to the number, which is referred to as the “cardinal number”. The number of repetitions of the butterfly calculations at one time in FFT is also determined by the cardinal number.
Generally, for various reasons of convenience (for example, the simplicity of the construction), a butterfly calculating circuit system having a cardinal number of four is frequently used. However, if the number of data to be subjected to FFT calculations (which is referred to as “the point number of FFT”) is other than four to the power of n, FFT cannot be performed using only the butterfly calculations of a cardinal number of four.
In this case, it is necessary to add butterfly calculations of a cardinal number of two to a butterfly calculating circuit system having a cardinal number of four. Accordingly, in terms of the configuration of the circuitry, the addition of a butterfly calculating circuit system having a cardinal number of two is required.
FIGS. 5A and 5B
respectively illustrate an example of a known butterfly calculating circuit system having a cardinal number of four and an example of a conventional butterfly calculating circuit system having a cardinal number of two.
The butterfly calculating circuit system having a cardinal number of four shown in
FIG. 5A
is formed of complex multiplication circuits
1
through
3
and complex addition circuits
4
through
7
. The signal lines connecting the black dots on the left side of FIG.
5
A and the complex addition circuits
4
through
7
on the right side of
FIG. 5A
are used to multiply input complex data by 1, −1, j, and −j and to output the multiplied data. Input data IA
0
through IA
3
indicate complex data. IB
1
through IB
3
indicate complex constant data, which is, for example, stored in a ROM, read, and supplied.
The operation of the above-described known butterfly calculating circuit system is as follows.
The complex multiplication circuits
1
through
3
multiply IA
1
by IB
1
, IA
2
by IB
2
, and IA
3
by IB
3
, respectively, and output the multiplied data.
The input data IA
0
is input into the complex addition circuits
4
and
5
. An output of the complex multiplication circuit
1
is multiplied by 1, −j, 1, and j, and the multiplied values are respectively input into the complex addition circuits
4
through
7
. An output of the complex multiplication circuit
2
is multiplied by 1, −1, 1, and −1, and the multiplied values are respectively input into the complex addition circuits
4
through
7
. An output of the complex multiplication circuit
3
is multiplied by 1, j, −1, and −j, and the multiplied values are respectively input into the complex addition circuits
4
through
7
.
The complex addition circuits
4
through
7
add the input data IA
0
to the outputs of the complex multiplication circuits
1
through
3
multiplied by constants (1, −1, J, and −j) and output the added values as O
0
through O
3
, respectively.
According to the above-described circuit system, butterfly calculations of a cardinal number of four can be performed.
An example of the configuration of a butterfly calculating circuit system having a cardinal number of two is described below with reference to FIG.
5
B.
The butterfly calculating circuit system is formed, as shown in
FIG. 5B
, of a complex multiplication circuit
8
and complex addition circuits
9
and
10
. IA
0
and IA
1
indicate input data, and IB
1
represents constant data stored in, for example, a ROM.
The operation of the above example is as follows.
The input data IA
0
is input into the complex addition circuits
9
and
10
. The input data IA
1
and the constant data IB
1
are input into the complex multiplication circuit
8
in which the data IA
1
and IB
1
are complex-multiplied. The multiplied data is then supplied to the complex addition circuit
9
, and is also supplied to the complex addition circuit
10
after being multiplied by −1.
The complex addition circuit
9
adds the input data IA
0
to the output of the complex multiplication circuit
8
and outputs the resulting data as O
0
. Moreover, the complex addition circuit
10
adds the input data IA
0
to the output of the complex multiplication circuit
8
multiplied by −1 and outputs the resulting data as O
1
.
According to the foregoing configuration of the circuit system, butterfly calculations of a cardinal number of two can be performed.
When the point number is other than four to the power of n, it is necessary to form FFT circuitry by using both the butterfly calculating circuit system having a cardinal number of four and the butterfly calculating circuit system having a cardinal number of two. This enlarges the resulting circuitry by an amount equal to a butterfly calculating circuit system having a cardinal number of two (which is the circuit system shown in
FIG. 5B
) over FFT circuitry whose point number is four to the power of n. Moreover, a butterfly calculating circuit system having a cardinal number of two is used only in part of the FFT processing, and it is thus burdensome to separately form a circuit system, which is not frequently used.
SUMMARY OF THE INVENTION
Accordingly, in view of the above background, it is an object of the present invention to eliminate the need to separately form a butterfly calculating circuit system having a cardinal number of two in FFT circuitry whose point number is other than four to the power of n, thereby effectively using resources of FFT circuitry.
According to one aspect of the present invention, there is provided a FFT calculating apparatus having input means for receiving a signal which provides an instruction to perform a butterfly calculation of a cardinal number of two or a butterfly calculation of a cardinal number of four. Selection means select predetermined data in accordance with the signal input from the input means. Switching means switch predetermined data between a real number portion and an imaginary number portion in accordance with the signal input from the input means. Sign inversion means invert a sign of the real number portion or the imaginary number portion of predetermined data in accordance with the signal input from the input means. In the above calculating apparatus, a pair of butterfly calculations of a cardinal number of two are simultaneously performed when a signal which provides an instruction to perform a butterfly calculation of a cardinal number of two is input from the input means. On the other hand, when a signal which provides an instruction to perform a butterfly calculation of a cardinal number of four is input from the input means, a single butterfly calculation having a cardinal number of four is performed.
More specifically, in the foregoing FFT calculating apparatus, upon inputting from the input means a control signal which provides an instruction to perform a butterfly calculation of a cardinal number of two or a cardinal number of four, selectors, which serve as the selection means, change the connecting states of the respective signal lines of the circuitry as required. Selectors, which serve as the switching means, switch, in accordance with the control signal, the data of the respective elements of the circuitry between the real number portion and the imaginary number portion as required. Further, sign inversion circuits, which serve as the sign inversion means, invert, in accordance w
Ikeda Yasunari
Kozaki Yasunari
Lerner David Littenberg Krumholz & Mentlik LLP
Sony Corporation
Ton Dang
LandOfFree
Fast fourier transform calculating apparatus and fast... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast fourier transform calculating apparatus and fast..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast fourier transform calculating apparatus and fast... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2445593