Discrete Fourier Transform in an integrated circuit device

• US 8,601,044 B2
• Filed: 03/02/2010
• Issued: 12/03/2013
• Est. Priority Date: 03/02/2010
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US12/715,711
• Publication Number:
  US 20110219052A1
• Time in Patent Office: 1,372 Days
• Field of Search: 708/403, 708/404, 708/405
• US Class Current: 708/403
• CPC Class Codes: G06F 17/141 Discrete Fourier transforms

Abstract

Circuitry performing Discrete Fourier Transforms. The circuitry can be provided in a fixed logic device, or can be configured into a programmable integrated circuit device such as a programmable logic device. The circuitry includes a floating-point addition stage for adding mantissas of input values of the Discrete Fourier Transform operation, and a fixed-point stage for multiplying outputs of the floating-point addition stage by twiddle factors. The fixed-point stage includes memory for storing a plurality of sets of twiddle factors, each of those sets including copies of a respective twiddle factor shifted by different amounts, and circuitry for determining a difference between exponents of the outputs of the floating-point stage, and for using that difference as an index to select from among those copies of that respective twiddle factor in each of the sets.

Claims

1. Circuitry for performing a Discrete Fourier Transform operation, said circuitry comprising:

a floating-point addition stage for adding mantissas of input values of said Discrete Fourier Transform operation; and

a fixed-point stage for multiplying outputs of said floating-point addition stage by twiddle factors, said fixed-point stage comprising;

memory for storing a plurality of sets of twiddle factors, each of said sets including copies of a respective twiddle factor shifted by different amounts, and

circuitry for determining a difference between exponents of said outputs of said floating-point stage, and for using said difference as an index to select from among said copies of said respective twiddle factor in each of said sets.

2. The circuitry of claim 1 wherein said floating-point addition stage comprises at least one adder for adding real parts of said mantissas and at least one adder for adding imaginary parts of said mantissas.

3. The circuitry of claim 2 wherein:

said at least one adder for adding real parts of said mantissas and said at least one adder for adding imaginary parts of said mantissas perform unnormalized additions; and

said floating-point addition stage further comprises a normalization stage for normalizing unnormalized outputs of said at least one adder for adding real parts of said mantissas and at least one adder for adding imaginary parts of said mantissas.

4. The circuitry of claim 3 wherein said normalization stage comprises:

a first normalization module for normalizing output of said at least one adder for adding real parts of said mantissas; and

a second normalization module for normalizing output of said at least one adder for adding imaginary parts of said mantissas.

5. The circuitry of claim 3 wherein said normalization stage comprises:

a first shifter for output of said at least one adder for adding real parts of said mantissas;

a second shifter for output of said at least one adder for adding imaginary parts of said mantissas;

a first count-leading-zeroes module for determining a first number of leading zeroes on output of said at least one adder for adding real parts of said mantissas;

a second count-leading-zeroes module for determining a second number of leading zeroes on output of said at least one adder for adding imaginary parts of said mantissas; and

a comparator for determining which of said first and second numbers of leading zeroes is smaller and for applying said smaller one of said first and second numbers of leading zeroes to each of said first and second shifters as a number of places by which said output of said at least one adder for adding real parts of said mantissas, and said output of said at least one adder for adding imaginary parts of said mantissas, are shifted.

6. The circuitry of claim 2 wherein:

said twiddle factors include real twiddle factors and imaginary twiddle factors; and

said fixed-point stage further comprises;

a first multiplier for multiplying output of said at least one adder for adding real parts of said mantissas by a real twiddle factor;

a second multiplier for multiplying output of said at least one adder for adding imaginary parts of said mantissas by an imaginary twiddle factor;

a subtractor for subtracting output of said second multiplier from output of said first multiplier;

a third multiplier for multiplying output of said at least one adder for adding real parts of said mantissas by an imaginary twiddle factor;

a fourth multiplier for multiplying output of said at least one adder for adding imaginary parts of said mantissas by a real twiddle factor; and

an adder for adding output of said fourth multiplier to output of said third multiplier.

7. The circuitry of claim 1 wherein:

said memory comprises two-port memory storing said plurality of twiddle factors shifted by different amounts;

a first address input of said two-port memory selects one of said respective twiddle factors; and

said difference is a second address input of said two-port memory that selects one of said shifted copies of said one of said respective twiddle factors.

8. A method of configuring a programmable integrated circuit device as circuitry for performing a Discrete Fourier Transform operation, said method comprising:

configuring logic of said programmable integrated circuit device as a floating-point addition stage for adding mantissas of input values of said Discrete Fourier Transform operation; and

configuring logic of said programmable integrated circuit device as a fixed-point stage for multiplying outputs of said floating-point addition stage by twiddle factors, said fixed-point stage comprising;

memory for storing a plurality of sets of twiddle factors, each of said sets including copies of a respective twiddle factor shifted by different amounts, and

circuitry for determining a difference between exponents of said outputs of said floating-point stage, and for using said difference as an index to select from among said copies of said respective twiddle factor in each of said sets.

9. The method of claim 8 wherein:

said configuring logic of said programmable integrated circuit device as a floating-point addition stage comprises configuring logic of said programmable integrated circuit device as at least one adder for adding real parts of said mantissas and at least one adder for adding imaginary parts of said mantissas.

10. The method of claim 9 wherein:

said configuring logic of said programmable integrated circuit device as at least one adder for adding real parts of said mantissas and said at least one adder for adding imaginary parts of said mantissas comprises configuring logic of said programmable integrated circuit device to perform unnormalized additions; and

said configuring logic of said programmable integrated circuit device as a floating-point addition stage comprises configuring logic of said programmable integrated circuit device as a normalization stage for normalizing unnormalized outputs of said at least one adder for adding real parts of said mantissas and at least one adder for adding imaginary parts of said mantissas.

11. The method of claim 10 wherein said configuring logic of said programmable integrated circuit device as a normalization stage comprises:

configuring logic of said programmable integrated circuit device as a first normalization module for normalizing output of said at least one adder for adding real parts of said mantissas; and

configuring logic of said programmable integrated circuit device as a second normalization module for normalizing output of said at least one adder for adding imaginary parts of said mantissas.

12. The method of claim 10 wherein said configuring logic of said programmable integrated circuit device as a normalization stage comprises:

configuring logic of said programmable integrated circuit device as a first shifter for output of said at least one adder for adding real parts of said mantissas;

configuring logic of said programmable integrated circuit device as a second shifter for output of said at least one adder for adding imaginary parts of said mantissas;

configuring logic of said programmable integrated circuit device as a first count-leading-zeroes module for determining a first number of leading zeroes on output of said at least one adder for adding real parts of said mantissas;

configuring logic of said programmable integrated circuit device as a second count-leading-zeroes module for determining a second number of leading zeroes on output of said at least one adder for adding imaginary parts of said mantissas; and

configuring logic of said programmable integrated circuit device as a comparator for determining which of said first and second numbers of leading zeroes is smaller and for applying said smaller one of said first and second numbers of leading zeroes to each of said first and second shifters as a number of places by which said output of said at least one adder for adding real parts of said mantissas, and said output of said at least one adder for adding imaginary parts of said mantissas, are shifted.

13. The method of claim 9 wherein:

said twiddle factors include real twiddle factors and imaginary twiddle factors; and

said configuring logic of said programmable integrated circuit device as a fixed-point stage further comprises;

configuring logic of said programmable integrated circuit device as a first multiplier for multiplying output of said at least one adder for adding real parts of said mantissas by a real twiddle factor;

configuring logic of said programmable integrated circuit device as a second multiplier for multiplying output of said at least one adder for adding imaginary parts of said mantissas by an imaginary twiddle factor;

configuring logic of said programmable integrated circuit device as a subtractor for subtracting output of said second multiplier from output of said first multiplier;

configuring logic of said programmable integrated circuit device as a third multiplier for multiplying output of said at least one adder for adding real parts of said mantissas by an imaginary twiddle factor;

configuring logic of said programmable integrated circuit device as a fourth multiplier for multiplying output of said at least one adder for adding imaginary parts of said mantissas by a real twiddle factor; and

configuring logic of said programmable integrated circuit device as an adder for adding output of said fourth multiplier to output of said third multiplier.

14. The method of claim 8 wherein:

said memory comprises two-port memory storing said plurality of twiddle factors shifted by different amounts;

said configuring logic of said programmable integrated circuit device as a fixed-point stage comprises configuring logic of said programmable integrated circuit device as a first address input of said two-port memory to select one of said respective twiddle factors; and

said configuring logic of said programmable integrated circuit device as a fixed-point stage comprises configuring logic of said programmable integrated circuit device to use said difference as a second address input of said two-port memory that selects one of said shifted copies of said one of said respective twiddle factors.

15. A programmable integrated circuit device comprising:

logic configurable as a floating-point addition stage for adding mantissas of input values of said Discrete Fourier Transform operation; and

logic configurable as a fixed-point stage for multiplying outputs of said floating-point addition stage by twiddle factors, said fixed-point stage comprising;

memory for storing a plurality of sets of twiddle factors, each of said sets including copies of a respective twiddle factor shifted by different amounts, and

circuitry for determining a difference between exponents of said outputs of said floating-point stage, and for using said difference as an index to select from among said copies of said respective twiddle factor in each of said sets.

16. The programmable integrated circuit device of claim 15 wherein:

said logic configurable as a floating-point addition stage comprises logic configurable as at least one adder for adding real parts of said mantissas and at least one adder for adding imaginary parts of said mantissas.

17. The programmable integrated circuit device of claim 16 wherein:

said programmable integrated circuit device as at least one adder for adding real parts of said mantissas and said at least one adder for adding imaginary parts of said mantissas comprises logic configurable to perform unnormalized additions; and

said logic configurable as a floating-point addition stage comprises logic configurable as a normalization stage for normalizing unnormalized outputs of said at least one adder for adding real parts of said mantissas and at least one adder for adding imaginary parts of said mantissas.

18. The programmable integrated circuit device of claim 17 wherein said logic configurable as a normalization stage comprises:

logic configurable as a first normalization module for normalizing output of said at least one adder for adding real parts of said mantissas; and

logic configurable as a second normalization module for normalizing output of said at least one adder for adding imaginary parts of said mantissas.

19. The programmable integrated circuit device of claim 17 wherein said logic configurable as a normalization stage comprises:

logic configurable as a first shifter for output of said at least one adder for adding real parts of said mantissas;

logic configurable as a second shifter for output of said at least one adder for adding imaginary parts of said mantissas;

logic configurable as a first count-leading-zeroes module for determining a first number of leading zeroes on output of said at least one adder for adding real parts of said mantissas;

logic configurable as a second count-leading-zeroes module for determining a second number of leading zeroes on output of said at least one adder for adding imaginary parts of said mantissas; and

logic configurable as a comparator for determining which of said first and second numbers of leading zeroes is smaller and for applying said smaller one of said first and second numbers of leading zeroes to each of said first and second shifters as a number of places by which said output of said at least one adder for adding real parts of said mantissas, and said output of said at least one adder for adding imaginary parts of said mantissas, are shifted.

20. The programmable integrated circuit device of claim 16 wherein:

said twiddle factors include real twiddle factors and imaginary twiddle factors; and

said logic configurable as a fixed-point stage further comprises;

logic configurable as a first multiplier for multiplying output of said at least one adder for adding real parts of said mantissas by a real twiddle factor;

logic configurable as a second multiplier for multiplying output of said at least one adder for adding imaginary parts of said mantissas by an imaginary twiddle factor;

logic configurable as a subtractor for subtracting output of said second multiplier from output of said first multiplier;

logic configurable as a third multiplier for multiplying output of said at least one adder for adding real parts of said mantissas by an imaginary twiddle factor;

logic configurable as a fourth multiplier for multiplying output of said at least one adder for adding imaginary parts of said mantissas by a real twiddle factor; and

logic configurable as an adder for adding output of said fourth multiplier to output of said third multiplier.

21. The programmable integrated circuit device of claim 15 wherein:

said memory comprises two-port memory storing said plurality of twiddle factors shifted by different amounts;

said logic configurable as a fixed-point stage comprises logic configurable as a first address input of said two-port memory to select one of said respective twiddle factors; and

said logic configurable as a fixed-point stage comprises logic configurable to use said difference as a second address input of said two-port memory that selects one of said shifted copies of said one of said respective twiddle factors.

22. A machine-readable data storage medium encoded with machine-executable instructions for configuring a programmable integrated circuit device as circuitry for performing a Discrete Fourier Transform operation, said instructions comprising:

instructions to configure logic of said programmable integrated circuit device as a floating-point addition stage for adding mantissas of input values of said Discrete Fourier Transform operation; and

instructions to configure logic of said programmable integrated circuit device as a fixed-point stage for multiplying outputs of said floating-point addition stage by twiddle factors, said fixed-point stage comprising;

memory for storing a plurality of sets of twiddle factors, each of said sets including copies of a respective twiddle factor shifted by different amounts, and

circuitry for determining a difference between exponents of said outputs of said floating-point stage, and for using said difference as an index to select from among said copies of said respective twiddle factor in each of said sets.

23. The machine-readable data storage medium of claim 22 wherein:

said instructions to configure logic of said programmable integrated circuit device as a floating-point addition stage comprises instructions to configure logic of said programmable integrated circuit device as at least one adder for adding real parts of said mantissas and at least one adder for adding imaginary parts of said mantissas.

24. The machine-readable data storage medium of claim 23 wherein:

said instructions to configure logic of said programmable integrated circuit device as at least one adder for adding real parts of said mantissas and said at least one adder for adding imaginary parts of said mantissas comprises instructions to configure logic of said programmable integrated circuit device to perform unnormalized additions; and

said instructions to configure logic of said programmable integrated circuit device as a floating-point addition stage comprises instructions to configure logic of said programmable integrated circuit device as a normalization stage for normalizing unnormalized outputs of said at least one adder for adding real parts of said mantissas and at least one adder for adding imaginary parts of said mantissas.

25. The machine-readable data storage medium of claim 24 wherein said instructions to configure logic of said programmable integrated circuit device as a normalization stage comprises:

instructions to configure logic of said programmable integrated circuit device as a first normalization module for normalizing output of said at least one adder for adding real parts of said mantissas; and

instructions to configure logic of said programmable integrated circuit device as a second normalization module for normalizing output of said at least one adder for adding imaginary parts of said mantissas.

26. The machine-readable data storage medium of claim 24 wherein said instructions to configure logic of said programmable integrated circuit device as a normalization stage comprises:

instructions to configure logic of said programmable integrated circuit device as a first shifter for output of said at least one adder for adding real parts of said mantissas;

instructions to configure logic of said programmable integrated circuit device as a second shifter for output of said at least one adder for adding imaginary parts of said mantissas;

instructions to configure logic of said programmable integrated circuit device as a first count-leading-zeroes module for determining a first number of leading zeroes on output of said at least one adder for adding real parts of said mantissas;

instructions to configure logic of said programmable integrated circuit device as a second count-leading-zeroes module for determining a second number of leading zeroes on output of said at least one adder for adding imaginary parts of said mantissas; and

instructions to configure logic of said programmable integrated circuit device as a comparator for determining which of said first and second numbers of leading zeroes is smaller and for applying said smaller one of said first and second numbers of leading zeroes to each of said first and second shifters as a number of places by which said output of said at least one adder for adding real parts of said mantissas, and said output of said at least one adder for adding imaginary parts of said mantissas, are shifted.

27. The machine-readable data storage medium of claim 23 wherein:

said twiddle factors include real twiddle factors and imaginary twiddle factors; and

said instructions to configure logic of said programmable integrated circuit device as a fixed-point stage further comprises;

instructions to configure logic of said programmable integrated circuit device as a first multiplier for multiplying output of said at least one adder for adding real parts of said mantissas by a real twiddle factor;

instructions to configure logic of said programmable integrated circuit device as a second multiplier for multiplying output of said at least one adder for adding imaginary parts of said mantissas by an imaginary twiddle factor;

instructions to configure logic of said programmable integrated circuit device as a subtractor for subtracting output of said second multiplier from output of said first multiplier;

instructions to configure logic of said programmable integrated circuit device as a third multiplier for multiplying output of said at least one adder for adding real parts of said mantissas by an imaginary twiddle factor;

instructions to configure logic of said programmable integrated circuit device as a fourth multiplier for multiplying output of said at least one adder for adding imaginary parts of said mantissas by a real twiddle factor; and

instructions to configure logic of said programmable integrated circuit device as an adder for adding output of said fourth multiplier to output of said third multiplier.

28. The machine-readable data storage medium of claim 22 wherein:

said memory comprises two-port memory storing said plurality of twiddle factors shifted by different amounts;

said instructions to configure logic of said programmable integrated circuit device as a fixed-point stage comprises configuring logic of said programmable integrated circuit device as a first address input of said two-port memory to select one of said respective twiddle factors; and

said instructions to configure logic of said programmable integrated circuit device as a fixed-point stage comprises configuring logic of said programmable integrated circuit device to use said difference as a second address input of said two-port memory that selects one of said shifted copies of said one of said respective twiddle factors.