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.

Description:
BACKGROUND OF THE INVENTION 
     This invention relates to performing Discrete Fourier Transform operations in integrated circuit devices, and particularly in programmable integrated circuit devices such as programmable logic devices (PLDs). 
     Discrete Fourier Transforms (DFTs) are a type of Fourier transform may be used in signal processing applications to analyze the frequencies contained in a sampled signal, to solve partial differential equations, and to perform other operations such as convolutions or multiplying large integers. DFTs can be used to construct Fast Fourier Transforms (FFTs). In addition, smaller DFTs can be used to construct larger DFTs. This makes DFTs particularly useful for calculating FFTs in dedicated digital signal processing (DSP) circuit blocks in integrated circuit devices such as programmable logic devices (PLDs), because individual smaller DFTs can be computed in individual DSP blocks. 
     SUMMARY OF THE INVENTION 
     The present invention relates to reduction in the resources needed to perform a DFT operation by replacing floating-point multiplication operations with fixed-point operations. This can be done because the number of twiddle factors in a DFT calculation is relatively small, and they are within a small number of bits of each other. Therefore, instead of using floating-point multipliers to compute the DFT, fixed-point multipliers can be used. The needed precision is obtained by storing multiple copies of each twiddle factor, with each copy shifted by a different amount. The difference between the exponents of the values to be multiplied is used as an index into the twiddle factor storage to retrieve the appropriately shifted twiddle factor. 
     Therefore, in accordance with the present invention, there is provided circuitry for performing Discrete Fourier Transforms. 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. 
     A method of configuring such circuitry on a programmable device, a programmable device so configurable, and a machine-readable data storage medium encoded with software for performing the method, are also provided. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Further features of the invention, its nature and various advantages will be apparent upon consideration of the following detailed description, taken in conjunction with the accompanying drawings, in which like reference characters refer to like parts throughout, and in which: 
         FIG. 1  shows the logical structure of a radix 4 Discrete Fourier Transform; 
         FIG. 2  shows a known improvement of the logical structure of  FIG. 1 ; 
         FIG. 3  shows the logical structure of a radix 4 Discrete Fourier Transform according to one embodiment of the present invention; 
         FIG. 4  is a simplified block diagram of an implementation of the logical structure of  FIG. 3  according to an embodiment of the present invention; 
         FIG. 5  is a simplified block diagram of an implementation of calculation of an address offset in connection with the implementation of  FIG. 4 ; 
         FIG. 6  shows the logical structure of a radix 4 Discrete Fourier Transform according to another embodiment of the present invention; 
         FIG. 7  is a cross-sectional view of a magnetic data storage medium encoded with a set of machine-executable instructions for performing the method according to the present invention; 
         FIG. 8  is a cross-sectional view of an optically readable data storage medium encoded with a set of machine executable instructions for performing the method according to the present invention; and 
         FIG. 9  is a simplified block diagram of an illustrative system employing a programmable logic device incorporating the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     A radix 4 DFT has four complex inputs (R 1 ,I 1 ), (R 2 ,I 2 ), (R 3 ,I 3 ) and (R 4 ,I 4 ). As can be seen in  FIG. 1 , in the calculation  100  of the first bin ({1,1,1,1}), the real parts are all added together using adders  101 ,  102 ,  103  and the imaginary parts are all added together using adders  111 ,  112 ,  113 . This portion of the DFT requires only adders. The real output  104  is calculated as the difference  105  between the product  106  of the real sum  103  and the real twiddle factors  107 , and the product  116  of the imaginary sum  113  and the imaginary twiddle factors  117 . The imaginary output  114  is calculated as the sum  115  of the product  126  of the real sum  103  and the imaginary twiddle factors  117 , and the product  136  of the imaginary sum  113  and the real twiddle factors  107 . Except for the multipliers  106 ,  116 ,  126 ,  136 , the operations can be carried out using adders. 
     The additional bins of a radix 4 DFT are calculated by applying {1,−j,−1,j}, {1,−1,1,−1} and {1,j,−1,−j} to the input values. In floating-point operations, negations are easily implemented (e.g., by inverting the sign bit). Similarly, multiplication by j is accomplished by swapping the real and imaginary components of a number, which may be implemented using multiplexers as well as exclusive-OR functions. Therefore, the additional bins may be carried out with a structure similar to  FIG. 1 , with these additional functions added (not shown). 
     In the case of a radix 16 DFT, two radix 4 stages would be required. The complex multiplier on the output of the first stage would have a limited number of complex twiddle factors applied—W 0 , W 1 , W 2 , W 3 , W 4 , W 6 , W 9 , where Wx=e −2jπx/16 . 
     The operators shown in  FIG. 1  may be floating-point operators in accordance with the IEEE754-1985 standard for floating-point calculations.  FIG. 2  shows how the computation of  FIG. 1  may be computed using fewer resources by using floating-point operators as described in copending, commonly-assigned U.S. patent application Ser. No. 11/625,655, filed Jan. 22, 2007, in which floating-point numbers are maintained in unnormalized form most of the time, being normalized either (a) for output in accordance with the aforementioned IEEE754-1985 standard, or (b) where loss of precision may occur. 
     Thus, additions  201 ,  202 ,  203 ,  211 ,  212 ,  213  are floating-point operators but values are not normalized during those operations. However, the resulting sums are normalized at  206 ,  216  before the multiplication stage  205 . Within multiplication stage  205 , multipliers  215 ,  225 ,  235 ,  245 , adder  255  and subtractor  265  are floating-point operators, but values are not normalized during those operations. However, the results are normalized at  207 ,  217  for output at  204 ,  214 . This may result in a reduction in resource use of about 50% as compared to the implementation of  FIG. 1 . 
     It may be observed that after normalization blocks  206 ,  216 , both the real and imaginary mantissas are within a factor of two or each other, although their exponents may be different. The twiddle factors for the complex multiplications before the next DFT block will likely have a small number of values as well. For example, for a radix 16 DFT having two radix 4 DFT stages, the decimal magnitudes of the values that make up the real and imaginary twiddle factors are 1, 0.9239, 0.7071, and 0.3827, which are all within two bits of each other when expressed as binary numbers. 
     As a result, if multipliers somewhat larger than the precision of the floating-point mantissa are available, the complex multiplications can be implemented using mostly fixed-point arithmetic, saving additional resources. 
     In an embodiment according to the present invention, 36-bit multipliers, which are normally used for single-precision floating-point multiplication, are available, along with memory for storage of multiple twiddle factors. In accordance with this embodiment of the invention, the twiddle factors for a DFT calculation may be converted to fixed-point numbers by storing each twiddle factor as multiple fixed-point copies shifted by different amounts. The DFT input remains the only floating-point input to the calculation. The exponent difference between the input and the twiddle factor can determined and used as an index to look up the appropriately shifted twiddle factor from the twiddle factor memory, without any loss of precision. 
     This logical construct  300  is shown in  FIG. 3 . As in the case of  FIG. 2 , additions  201 ,  202 ,  203 ,  211 ,  212 ,  213  are floating-point operators but values are not normalized during those operations. Once again, the resulting sums are normalized at  206 ,  216  before the multiplication stage  305 . In multiplication stage  305 , multipliers  315 ,  325 ,  335 ,  345 , adder  355  and subtractor  365  are fixed-point operators. The outputs of multipliers  315 ,  325 ,  335 ,  345  have their relative values aligned with each other, so that they may be added or subtracted by adder  355  and subtractor  365 . 
     The alignment of the multiplier outputs may be accomplished by shifting the twiddle factors. The amount of shift of each twiddle factor will be the difference between the exponents of the multiplier inputs. In one embodiment, for each multiplier pair (i.e., the pair that generates the real output and the pair that generates the imaginary output) one twiddle factor will not be shifted, and the other will be shifted. Although logically this may be represented by the shifters shown in  FIG. 3 , one physical implementation is shown in  FIG. 4 , as discussed below. 
     The larger output value would be a normalized data value, multiplied by a twiddle factor close to unity (i.e., within two bits magnitude of unity). Therefore, there will be a possible normalization required on the output, but in the case of a radix 16 DFT decomposed into radix 4 subsections as discussed above, there would be a maximum of 3 bits of normalization. The output exponent  308  may be calculated from the largest exponent after the normalizations  206 ,  216 , which may be adjusted by the output mantissa normalization value. The exponent value prior to any adjustment also is used as the index to select the appropriately-shifted twiddle factors at  309 . 
     Logical construct  300  may not save much logic, although it could reduce latency. However, a physical embodiment  400  of logical construct  300  is shown in  FIG. 4 . The arrangement of unnormalized floating-point adders  201 ,  202 ,  203 ,  211 ,  212 ,  213 , normalization modules  206 ,  216 , and fixed-point multipliers  315 ,  325 ,  335 ,  345 , adder  355  and subtractor  365  is the same as in logical construct  300 . 
     Memory  401  is provided for the real twiddle factors, while memory  402  is provided for the imaginary twiddle factors. Because of the limited number of twiddle factors for most large DFT constructions—e.g., 10 twiddle factors (4 of which may be unique) for the first stage in a radix 16 DFT, and 51 twiddle factors (about 35 of which may be unique) for the first stage in a radix 64 DFT, the shifts can all be precomputed and stored in memory. For example, in an integrated circuit device such as a programmable logic device from the STRATIX® family of programmable logic devices available from Altera Corporation, a sufficient number of embedded memory modules is provided on the device to serve this function. Each of memories  401 ,  402  may include a plurality of such embedded memory modules, as needed. However, for ease of illustration, each of memories  401 ,  402  is shown in  FIG. 4  as a single memory module. 
     In the example shown, each of memories  401 ,  402  is a dual-port memory. Accordingly, each may be addressed by a respective pair of addresses  411 ,  421  and  412 ,  422 . The members of each address pair may be considered the upper and lower portions of a single address, with lower address portion  411 ,  412  identifying which of the several twiddle factors is being accessed, and upper address portion  421 ,  422  identifying which of the shifted versions of that twiddle factor is being accessed. The generation of the addresses is performed as follows: 
     The real output has two multiplications—realdata×realtwiddle and imaginarydata×imaginarytwiddle. Address 1 will be used to access the real and imaginary twiddles for this case. 
     To calculate the real offset of Address 1 (the offset to the real twiddle memory), the exponent of the real data is subtracted from the exponent of the imaginary data. If this number is zero or positive (imaginary exponent&gt;real exponent) then this is the offset value (and also the shift value). If this number is negative (real exponent&gt;imaginary exponent), then this number is zeroed. 
     To calculate the imaginary offset of Address 1 (the offset to the imaginary twiddle memory), the exponent of the imaginary data is subtracted from the exponent of the real data. If this number is zero or positive (real exponent&gt;imaginary exponent) then this is the offset value (and also the shift value). If this number is negative (imaginary exponent&gt;real exponent), then this number is zeroed. 
     The imaginary output has two multiplications—realdata×imaginarytwiddle and imaginarydata×realtwiddle. Address 2 will be used to access the real and imaginary twiddles for this case. 
     To calculate the real offset of Address 2 (the offset to the imaginary twiddle memory), the exponent of the real data is subtracted from the exponent of the imaginary data. If this number is zero or positive (imaginary exponent&gt;real exponent) then this is the offset value (and also the shift value). If this number is negative (real exponent&gt;imaginary exponent), then this number is zeroed. 
     To calculate the imaginary offset of Address 2 (the offset to the real twiddle memory), the exponent of the imaginary data is subtracted from the exponent of the real data. If this number is zero or positive (real exponent&gt;imaginary exponent) then this is the offset value (also the shift value). If this number is negative (imaginary exponent&gt;real exponent), then this number is zeroed. 
     As can be seen, both the Address 1 and Address 2 calculations are the same. The real offset goes to Read Address 1 of the real twiddle memory, and to Read Address 2 of the imaginary twiddle memory. The imaginary offset goes to Read Address 2 of the real twiddle memory, and to Read Address 1 of the imaginary twiddle memory. The logic  500  for computing the real and imaginary offsets is shown in  FIG. 5 . 
     As can be seen, imaginary offset  501  is computed by subtracting at  503  the exponent  505  of the imaginary data from the exponent  506  of the real data. The result  513  is ANDed at  508  with the inverse  507  of its most significant bit  523 , which zeroes result  501  if result  513  is negative. Similarly, real offset  502  is computed by subtracting at  553  the exponent  506  of the real data from the exponent  505  of the imaginary data. The result  563  is ANDed at  558  with the inverse  557  of its most significant bit  573 , which zeroes result  502  if result  563  is negative. 
     In an alternative embodiment  600  shown in  FIG. 6 , instead of full normalization  206 ,  216  as in  FIG. 4 , the respective shift amounts needed to normalize real input  601  and imaginary input  611  are determined by Count Leading Zeroes modules  602 ,  612 , and the smaller shift (i.e., the shift needed to normalize the larger of values  601 ,  611 ), as selected by comparing the leading-zero counts at  603 , is used in shifters  604 ,  614  to left-shift both inputs  601 ,  611 . Therefore, one of inputs  601 ,  611  will retain its full magnitude, but the other of inputs  601 ,  611  will retain only its partial magnitude. However, because, as discussed above, the twiddle factors are all of approximately the same order of magnitude, and assuming a device such as a programmable logic device from the aforementioned STRATIX® family, when multipliers  615 ,  625 ,  635 ,  645  are 36 bits wide, accuracy of a single-precision (23-bit mantissa) value can be maintained even if it is right-shifted. 
     As an example of an implementation of the present invention, consider a 1K streaming FFT. Traditionally, this would be implemented using five radix 4 stages, the first four of which will require complex multipliers. There will be 256 elements, requiring a total of thousands of twiddle factors. 
     Using the present invention, a 1K streaming FFT could be implemented using a radix 16 stage, a radix 4 stage and radix 16 stage. The first radix 16 stage would use an optimized internal complex multiplier, with a standard complex multiplier on the output. Alternatively, an optimized complex multiplier could be used on the output. With 64 complex twiddle factors, this would require about (32 or 36)×64=about 2,000 complex twiddle factor memory locations when all of the shifts have been pre-calculated. The next radix 4 stage could use an optimized complex multiplier, as there would only be 16 twiddle factors, or a total of about (32 or 36)×16=about 512 complex twiddle factor memory locations when all of the shifts have been pre-calculated. The final radix 16 stage would use an internal optimized complex multiplier, with about the same number of twiddle factors as the first stage. 
     Instructions for carrying out a method according to this invention for programming a programmable device to perform DFTs may be encoded on a machine-readable medium, to be executed by a suitable computer or similar device to implement the method of the invention for programming or configuring PLDs or other programmable devices to perform addition and subtraction operations as described above. For example, a personal computer may be equipped with an interface to which a PLD can be connected, and the personal computer can be used by a user to program the PLD using a suitable software tool, such as the QUARTUS® II software available from Altera Corporation, of San Jose, Calif. 
       FIG. 7  presents a cross section of a magnetic data storage medium  800  which can be encoded with a machine executable program that can be carried out by systems such as the aforementioned personal computer, or other computer or similar device. Medium  800  can be a floppy diskette or hard disk, or magnetic tape, having a suitable substrate  801 , which may be conventional, and a suitable coating  802 , which may be conventional, on one or both sides, containing magnetic domains (not visible) whose polarity or orientation can be altered magnetically. Except in the case where it is magnetic tape, medium  800  may also have an opening (not shown) for receiving the spindle of a disk drive or other data storage device. 
     The magnetic domains of coating  802  of medium  800  are polarized or oriented so as to encode, in manner which may be conventional, a machine-executable program, for execution by a programming system such as a personal computer or other computer or similar system, having a socket or peripheral attachment into which the PLD to be programmed may be inserted, to configure appropriate portions of the PLD, including its specialized processing blocks, if any, in accordance with the invention. 
       FIG. 8  shows a cross section of an optically-readable data storage medium  810  which also can be encoded with such a machine-executable program, which can be carried out by systems such as the aforementioned personal computer, or other computer or similar device. Medium  810  can be a conventional compact disk read-only memory (CD-ROM) or digital video disk read-only memory (DVD-ROM) or a rewriteable medium such as a CD-R, CD-RW, DVD-R, DVD-RW, DVD+R, DVD+RW, or DVD-RAM or a magneto-optical disk which is optically readable and magneto-optically rewriteable. Medium  810  preferably has a suitable substrate  811 , which may be conventional, and a suitable coating  812 , which may be conventional, usually on one or both sides of substrate  811 . 
     In the case of a CD-based or DVD-based medium, as is well known, coating  812  is reflective and is impressed with a plurality of pits  813 , arranged on one or more layers, to encode the machine-executable program. The arrangement of pits is read by reflecting laser light off the surface of coating  812 . A protective coating  814 , which preferably is substantially transparent, is provided on top of coating  812 . 
     In the case of magneto-optical disk, as is well known, coating  812  has no pits  813 , but has a plurality of magnetic domains whose polarity or orientation can be changed magnetically when heated above a certain temperature, as by a laser (not shown). The orientation of the domains can be read by measuring the polarization of laser light reflected from coating  812 . The arrangement of the domains encodes the program as described above. 
     A PLD  90  programmed according to the present invention may be used in many kinds of electronic devices. One possible use is in a data processing system  900  shown in  FIG. 9 . Data processing system  900  may include one or more of the following components: a processor  901 ; memory  902 ; I/O circuitry  903 ; and peripheral devices  904 . These components are coupled together by a system bus  905  and are populated on a circuit board  906  which is contained in an end-user system  907 . 
     System  900  can be used in a wide variety of applications, such as computer networking, data networking, instrumentation, video processing, digital signal processing, or any other application where the advantage of using programmable or reprogrammable logic is desirable. PLD  90  can be used to perform a variety of different logic functions. For example, PLD  90  can be configured as a processor or controller that works in cooperation with processor  901 . PLD  90  may also be used as an arbiter for arbitrating access to a shared resources in system  900 . In yet another example, PLD  90  can be configured as an interface between processor  901  and one of the other components in system  900 . It should be noted that system  900  is only exemplary, and that the true scope and spirit of the invention should be indicated by the following claims. 
     Various technologies can be used to implement PLDs  90  as described above and incorporating this invention. 
     It will be understood that the foregoing is only illustrative of the principles of the invention, and that various modifications can be made by those skilled in the art without departing from the scope and spirit of the invention. For example, the various elements of this invention can be provided on a PLD in any desired number and/or arrangement. One skilled in the art will appreciate that the present invention can be practiced by other than the described embodiments, which are presented for purposes of illustration and not of limitation, and the present invention is limited only by the claims that follow.