Serial FFT processing unit

• US 4,058,715 A
• Filed: 06/18/1976
• Issued: 11/15/1977
• Est. Priority Date: 06/20/1975
• Status: Expired due to Term

• Current Assignee: Nippon Electric Company Limited (NEC Corporation)
• Original Assignee: Nippon Electric Company Limited (NEC Corporation)
• Inventors: Niwa, Kunihiko
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US05/697,659
• Time in Patent Office: 515 Days
• Field of Search: 235/156, 235/152, 235/164
• US Class Current: 708/404
• CPC Class Codes: G06F 17/142 Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm

Abstract

An FFT processing unit of simplified construction comprises one or more arithmetic stages serially connected. Each stage has a plurality of recursive arithmetic paths each consisting of a delay element, a simplified multiplier for multiplying by ±1 and ±j where j = √-1, and an adder. The adder is supplied with a serial input digital data series and the output is provided to the delay element and multiplier connected in series. A switch successively selects the output signals obtained from the plurality of recursive arithmetic paths. A second multiplier multiplies the signals selected by the switch by predetermined coefficients.

Claims

1. An FFT processing unit comprising one or more serially connected arithmetic stages, each arithmetic stage having

a. a plurality of recursive arithmetic paths, each recursive arithmetic path consisting ofa delay element,

a simplified multiplier means fed with an output signal obtained from said delay element for multiplying said output signal by any one of ±

1 and ±

j where j is equal to √

-1, and

3. an adder means fed with a serial input digital data series and an output signal of the simplified multiplier means at its first and second input terminals, respectively, and feeding its output signal to an input terminal of the delay element,

said recursive arithmetic paths being connected in parallel so that said serial input digital data series are given at their respective input terminals;

b. a switch means for successively selecting output signals obtained from said plurality of recursive arithmetic paths; and

c. a second multiplier means for multiplying input signals given through said switch means by predetermined coefficients.

2. An FFT processing unit as claimed in claim 1 in which said simplified multiplier means selectively passes a multiplicand datum in the intact form, reverses its polarity, interchanges a real term and an imaginary term thereof, or combines these operations.

3. An FFT processing unit as claimed in claim 1 in which said each arithmetic stage further contains a plurality of second delay elements connected in series, both ends and intermediate junction points of the series connected second delay elements being respectively connected to a corresponding first input terminal of the adder means in each recursive arithmetic path and said serial input digital data series being given to an input terminal of the arithmetic stage which is connected to one end of the series connected second delay elements, whereby a particular section of the serial input digital data series may be given to the respective input terminals of said plurality of recursive arithmetic paths at different time points delayed by a given period.

4. An FFT processing unit as claimed in claim 1 wherein the number of recursive arithmetic paths in each arithmetic stage is four.

5. An FFT processing unit as claimed in claim 1 wherein the number of recursive arithmetic paths in each arithmatic stage is two.

6. An FFT processing unit as claimed in claim 1 wherein the number of arithmetic stages is two or more and the last stage is composed of P parallel recursive arithmetic paths where P is not a multiple of four, the outputs of the FFT processing unit appearing sequentially at the outputs of the multiplier means in the recursive arithmetic paths in said last stage.

7. An FFT processing unit comprising one or more serially connected arithmetic stages, each arithmetic stage having

a. a plurality of recursive arithmetic paths, each recursive arithmetic path consisting ofa simplified multiplier means for multiplying by any one of ±

1 and ±

j where j is equal to √

-1,

2. a delay element for delaying an output signal obtained from the simplified multiplier means, and

3. an adder means fed with a serial input digital data series and an output signal of the delay element at its first and second input terminals, respectively, and feeding its output signal to an input terminal of the simplified multiplier means,

said recursive arithmetic paths being connected in parallel so that said serial input digital data series are given at their respective input terminals;

b. a switch means for successively selecting output signals obtained from said plurality of recursive arithmetic paths, and

c. a second multiplier means for multiplying input signals given through the switch means by predetermined coefficients.

8. An FFT processing unit as claimed in claim 7 in which said simplified multiplier means selectively passes a multiplicand datum in the intact form, reverses its polarity, interchanges a real term and imaginary term thereof, or combines these operations.

9. An FFT processing unit as claimed in claim 7 in which said each arithmetic stage further contains a plurality of second delay elements connected in series, both ends and intermediate junction points of the series connected second delay elements being respectively connected to a corresponding first input terminal of the adder means in each recursive arithmetic path, and said serial input digital data series being given to an input terminal of the arithmetic stage which is connected to one end of the series connected second delay elements, whereby a particular section of the serial input data series may be given to the respective input terminals of said plurality of recursive arithmetic paths at different time points delayed by a given period.

10. An FFT processing unit as claimed in claim 7 wherein the number of recursive arithmetic paths in each arithmetic stage is four.

11. An FFT processing unit as claimed in claim 7 wherein the number of recursive arithmetic paths in each arithmetic stage is two.

12. An FFT processing unit as claimed in claim 7 wherein the number of arithmetic stages is two or more and the last stage is composed of P parallel recursive arithmetic paths where P is not a multiple of four, the outputs of the FFT processing unit appearing sequentially at the outputs of the delay means in the recursive arithmetic paths in said last stage.