Memory address generating method and twiddle factor generator using the same

• US 8,458,241 B2
• Filed: 12/06/2006
• Issued: 06/04/2013
• Est. Priority Date: 12/08/2005
• Status: Expired due to Fees

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Cho, Hui-Rae, Jo, Gweon-Do, Kim, Jin-Up
• Primary Examiner(s): Do, Chat
• Assistant Examiner(s): SANDIFER, MATTHEW D
• Application Number:
  US12/096,774
• Publication Number:
  US 20080307026A1
• Time in Patent Office: 2,372 Days
• Field of Search: 708403-409
• US Class Current: 708/404
• CPC Class Codes: G06F 17/142 Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm
• CPC Class Codes: G06F 9/345 of multiple operands or results addressing multiple banks G06F12/06
• CPC Class Codes: H04L 27/2651 Modification of fast Fourier transform [FFT] or discrete Fourier transform [DFT] demodulators for performance improvement

Abstract

The present invention relates to a memory address generating method and a twiddle factor generator using the memory address generating method in a fast Fourier transform (FFT) system. In the memory address generating method for generating a memory address of a twiddle factor in a fast Fourier transform (FFT) system according to an embodiment of the present invention: a) a temporary address value of a second twiddle factor is induced and generated based on a first twiddle factor; b) a control signal for controlling the system is generated based on the generated temporary address value; and c) a memory address value of the second twiddle factor is generated from the temporary address value.

Claims

1. A twiddle factor generator for generating a final twiddle factor value for an nth twiddle factor in a fast Fourier transform (FFT) system, the twiddle factor generator comprising:

a hardware memory address calculator for generating a temporary address value for the nth twiddle factor, generating a twiddle factor memory address value for the nth twiddle factor based on the temporary address value, and outputting a control signal based on the temporary address value;

a twiddle factor storage unit for storing a twiddle factor value corresponding to the twiddle factor memory address value for the nth twiddle factor, the twiddle factor value generated based on a previously generated twiddle factor value, and outputting the twiddle factor value as a real part and an imaginary part; and

a controller for outputting the final twiddle factor value to the FFT system based on the control signal output from the memory address calculator and the twiddle factor value output from the twiddle factor storage unit,

wherein the memory address calculator generates the temporary address value for the nth twiddle factor by;

calculating a multiplied value by multiplying a sign value of the nth twiddle factor and a parameter value indicating a twiddle factor case; and

adding the multiplied value to a twiddle factor memory address value for an (n-1)th twiddle factor.

2. The twiddle factor generator of claim 1, wherein the controller comprises:

a first switch for switching the real part and the imaginary part of the twiddle factor value based on the control signal and outputting the switched real and imaginary parts;

a sign inverter for inverting signs of the real and imaginary parts of the twiddle factor value output from the twiddle factor storage unit and signs of the switched real and imaginary parts; and

a second switch for performing connection on the sign inverter to invert the signs of the real part and the imaginary part of the twiddle factor value.

3. The twiddle factor generator of claim 1, wherein the twiddle factor case is 0, 1, 2, or 3, and a plurality of twiddle factor memory address values corresponding to the twiddle factor case are sequentially output from the memory address calculator.

4. The twiddle factor generator of claim 3, wherein the control signal is a first control signal or a second control signal based on the temporary address value of the nth twiddle factor and a minimum symmetric point of the (n-1)th twiddle factor.

5. The twiddle factor generator of claim 4, wherein the first control signal is activated when the temporary address value of the nth twiddle factor is equal to or greater than the minimum symmetric point of the (n-1)th twiddle factor, and the second control signal is activated when the temporary address value of the nth twiddle factor is equal to or less than 0.

6. The twiddle factor generator of claim 5, wherein, when the first control signal is activated, the twiddle factor memory address value of the nth twiddle factor is set by subtracting the temporary address value of the nth twiddle factor from the minimum symmetric point of the (n-1)th twiddle factor multiplied by two.

7. The twiddle factor generator of claim 5, wherein, when the second control signal is activated, the twiddle factor memory address value of the nth twiddle factor is set by inverting the sign of the temporary address value of the nth twiddle factor.

8. The twiddle factor generator of claim 5, wherein the real and imaginary parts of the twiddle factor value output from the switch are switched when the first control signal is activated, and a sign of the real part or the imaginary part of the twiddle factor value output from the twiddle factor storage unit is inverted when the second control signal is activated.

9. The twiddle factor generator of claim 1, wherein the twiddle factor storage unit has a dimension obtained by dividing a dimension of the FFT by the minimum symmetric point of the nth twiddle factor and adding 1 thereto.

10. The twiddle factor generator of claim 1, wherein the FFT system performs an FFT operation in a Radix-4 method.

11. A method for generating a twiddle factor memory address value for an nth twiddle factor and a control signal in a fast Fourier transform (FFT) system, the method comprising:

generating a temporary address value of the nth twiddle factor;

generating the control signal for controlling the FFT system based on the temporary address value of the nth twiddle factor; and

outputting, by a hardware memory address calculator, the twiddle factor memory address value for the nth twiddle factor to a twiddle factor storage unit after generating the twiddle factor memory address value based on the temporary address value, and outputting the control signal to a controller,

wherein the generating the temporary address value of the nth twiddle factor comprises;

calculating a multiplied value by multiplying a sign value of the nth twiddle factor and a parameter value indicating a twiddle factor case; and

adding the multiplied value to a twiddle factor memory address value for an (n-1)th twiddle factor,

wherein the twiddle factor storage unit outputs a twiddle factor value corresponding to the twiddle factor memory address value for the nth twiddle factor, the twiddle factor value generated based on a previously generated twiddle factor value, and

wherein the controller outputs a final twiddle factor value to the FFT system based on the control signal output from the memory address calculator and the twiddle factor value output from the twiddle factor storage unit.

12. The method of claim 11, wherein the twiddle factor case is 0, 1, 2, or 3, and a plurality of twiddle factor memory address values corresponding to the twiddle factor case are sequentially output from the memory address calculator.

13. The method of claim 11, wherein, in the generating of the control signal, the control signal is generated as a first control signal when the temporary address value of the nth twiddle factor is equal to or greater than a minimum symmetric point of the (n-1)th twiddle factor, and the control signal is generated as a second control signal when the temporary address value of the nth twiddle factor is equal to or less than 0.

14. The method of claim 13, wherein, the outputting of the twiddle factor memory address value comprises, when the first control signal is generated, setting the twiddle factor memory address value of the nth twiddle factor by subtracting the temporary address value of the nth twiddle factor from the minimum symmetric point of the (n-1)th twiddle factor multiplied by two.

15. The method of claim 13, wherein, the outputting of the twiddle factor memory address value comprises, when the second control signal is generated, setting the twiddle factor memory address value of the nth twiddle factor by inverting a sign of the temporary address value of the nth twiddle factor.

16. The method of claim 13, wherein, in the outputting of the twiddle factor memory address value, when the temporary address value of the nth twiddle factor is less than the minimum symmetric point and greater than 0, the temporary address value of the nth twiddle factor is set as the twiddle factor memory address value of the nth twiddle factor.

17. The method of claim 11, wherein the FFT system performs an FFT operation in a Radix-4 method.

18. A method for generating a final twiddle factor value for an nth twiddle factor in a fast Fourier transform (FFT) system, the method comprising:

generating a temporary address value of the nth twiddle factor;

generating a control signal for controlling the FFT system based on the temporary address value of the nth twiddle factor;

outputting, by a hardware memory address calculator, a twiddle factor memory address value for the nth twiddle factor after generating the twiddle factor memory address value based on the temporary address value, and outputting the control signal;

outputting, from a twiddle factor storage unit, a twiddle factor value corresponding to the twiddle factor memory address value for the nth twiddle factor, the twiddle factor value generated based on a previously generated twiddle factor value; and

outputting the final twiddle factor value to the FFT system based on the control signal output from the memory address calculator and the twiddle factor value output from the twiddle factor storage unit,

wherein the generating the temporary address value of the nth twiddle factor comprises;

calculating a multiplied value by multiplying a sign value of the nth twiddle factor and a parameter value indicating a twiddle factor case; and

adding the multiplied value to a twiddle factor memory address value for an (n-1)th twiddle factor.