Fast fourier transform apparatus and method

• US 6,434,583 B1
• Filed: 09/15/1999
• Issued: 08/13/2002
• Est. Priority Date: 05/20/1996
• Status: Expired due to Term

• Current Assignee: HTC Corporation
• Original Assignee: ADC Telecommunications Incorporated (TE Connectivity Limited)
• Inventors: Geile, Michael J., Solum, Jeff, Downs, Matt, Hill, Terrance J., Enfield, Debra Lea, Ferris, Tammy, Roberts, Harold A., Berg, Darrell, Opoczynski, Adam, Anderson, Brian D., Smigelski, Thomas, Russell, David S., Brede, Jeffrey, Tucker, Thomas C., Nelson, Calvin G., Wadman, Mark S., Hall, Joe, Samant, Niranjan R., Kirscht, Robert J., Logajan, John M., Chiappetta, Joseph F., Herrmann, James J., Boualouang, Somvay, Sarnikowski, Scott, Fort, Michael J., Lou, Heng, Dapper, Mark J., Buska, Steven P., Elpers, Mark D.
• Primary Examiner(s): CUMMING, WILLIAM D
• Application Number:
  US09/396,650
• Time in Patent Office: 1,063 Days
• Field of Search: 708/622, 708/404, 708/409
• US Class Current: 708/409
• CPC Class Codes: G06F 17/14 Fourier, Walsh or analogous domain transformations , e.g. Laplace, Hilbert, Karhunen-Loeve, transforms for correlation function computation G06F17/156; spectrum analysers G01R23/16
• CPC Class Codes: G06F 17/142 Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/356 Unequal error protection [UEP]
• CPC Class Codes: H04B 10/272 Star-type networks or tree-type networks
• CPC Class Codes: H04H 20/69 Optical systems
• CPC Class Codes: H04H 20/77 using carrier waves
• CPC Class Codes: H04H 20/78 CATV [Community Antenna Television] systems
• CPC Class Codes: H04H 20/79 using downlink of the CATV systems, e.g. audio broadcast via CATV network
• CPC Class Codes: H04H 20/80 having frequencies in two or more frequency bands, e.g. medium wave and VHF
• CPC Class Codes: H04H 60/11 Arrangements for counter-measures when a portion of broadcast information is unavailable
• CPC Class Codes: H04H 60/86 accessed over CATV networks
• CPC Class Codes: H04H 60/96 CATV systems for accessing the Internet H04H60/86
• CPC Class Codes: H04H 60/97 using uplink of the CATV systems
• CPC Class Codes: H04J 14/0298 with sub-carrier multiplexing [SCM]
• CPC Class Codes: H04J 3/14 Monitoring arrangements for SDH/SONET rings H04J3/085
• CPC Class Codes: H04K 1/00 Secret communication
• CPC Class Codes: H04K 3/226 Selection of non-jammed channel for communication spectrum sharing arrangements H04W16/14; selection of wireless resources by user or terminal H04W72/02
• CPC Class Codes: H04K 3/255 based on redundancy of transmitted data, transmission path or transmitting source
• CPC Class Codes: H04L 1/004 by using forward error control H04L1/0618 takes precedence; coding, decoding or code conversion, for error detection or correction H03M13/00
• CPC Class Codes: H04L 1/0045 : Arrangements at the receiver end
• CPC Class Codes: H04L 1/0057 : Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/0071 : Use of interleaving interleaving per se H03M13/27
• CPC Class Codes: H04L 1/24 : Testing correct operation
• CPC Class Codes: H04L 12/10 : Current supply arrangements
• CPC Class Codes: H04L 12/12 : Arrangements for remote connection or disconnection of substations or of equipment thereof
• CPC Class Codes: H04L 12/2801 : Broadband local area networks
• CPC Class Codes: H04L 12/44 : Star or tree networks
• CPC Class Codes: H04L 2001/0093 : Point-to-multipoint
• CPC Class Codes: H04L 2027/0036 : using a recovered symbol clock
• CPC Class Codes: H04L 2027/0057 : quadrature phase
• CPC Class Codes: H04L 2027/0067 : Phase error detectors
• CPC Class Codes: H04L 25/03866 : using scrambling
• CPC Class Codes: H04L 27/2601 : Multicarrier modulation systems
• CPC Class Codes: H04L 27/2614 : Peak power aspects
• CPC Class Codes: H04L 27/2631 : with polyphase implementation
• CPC Class Codes: H04L 27/2634 : Inverse fast Fourier transform [IFFT] or inverse discrete Fourier transform [IDFT] modulators in combination with other circuits for modulation
• CPC Class Codes: H04L 27/2647 : Arrangements specific to the receiver only equalisation H04L27/01
• CPC Class Codes: H04L 27/2652 : with polyphase implementation
• CPC Class Codes: H04L 27/26524 : Fast Fourier transform [FFT] or discrete Fourier transform [DFT] demodulators in combination with other circuits for demodulation
• CPC Class Codes: H04L 27/2654 : Filtering per subcarrier, e.g. filterbank multicarrier [FBMC]
• CPC Class Codes: H04L 27/2655 : Synchronisation arrangements
• CPC Class Codes: H04L 27/2657 : Carrier synchronisation
• CPC Class Codes: H04L 27/2662 : Symbol synchronisation
• CPC Class Codes: H04L 27/34 : Amplitude- and phase-modulated carrier systems, e.g. quadrature-amplitude modulated carrier systems
• CPC Class Codes: H04L 41/0213 : Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/064 : involving time analysis
• CPC Class Codes: H04L 41/0896 : Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 43/00 : Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/022 : by sampling
• CPC Class Codes: H04L 43/067 : using time frame reporting
• CPC Class Codes: H04L 43/0811 : by checking connectivity
• CPC Class Codes: H04L 43/0817 : by checking functioning
• CPC Class Codes: H04L 43/0823 : Errors, e.g. transmission errors
• CPC Class Codes: H04L 43/0829 : Packet loss
• CPC Class Codes: H04L 43/0847 : Transmission error
• CPC Class Codes: H04L 43/0852 : Delays
• CPC Class Codes: H04L 43/0858 : One way delays
• CPC Class Codes: H04L 43/0864 : Round trip delays
• CPC Class Codes: H04L 43/0882 : Utilisation of link capacity
• CPC Class Codes: H04L 43/16 : Threshold monitoring
• CPC Class Codes: H04L 5/0007 : the frequencies being orthogonal, e.g. OFDM(A), DMT
• CPC Class Codes: H04L 5/0037 : Inter-user or inter-terminal allocation
• CPC Class Codes: H04L 5/0044 : allocation of payload
• CPC Class Codes: H04L 5/023 : Multiplexing of multicarrier modulation signals multicarrier modulation H04L27/2601
• CPC Class Codes: H04L 5/14 : Two-way operation using the same type of signal, i.e. duplex
• CPC Class Codes: H04L 5/143 : for modulated signals H04L5/1469 takes precedence
• CPC Class Codes: H04L 5/1484 : operating bytewise
• CPC Class Codes: H04M 7/006 : Networks other than PSTN/ISDN providing telephone service, e.g. Voice over Internet Protocol (VoIP) , including next generation networks with a packet-switched transport layer H04L65/00 takes precedence; aspects not specific to the type of network H04M3/00; special services in those networks H04M3/42
• CPC Class Codes: H04M 9/027 : Frequency division multiplex systems
• CPC Class Codes: H04N 21/2221 : being a cable television head-end CATV in broadcast systems H04H20/78
• CPC Class Codes: H04N 21/2383 : Channel coding or modulation of digital bit-stream, e.g. QPSK modulation arrangements for detecting or preventing errors in the information received by adapting the channel coding H04L1/0009; analogue front ends or means for connecting modulators, demodulators or transceivers to a transmission line H04L27/0002
• CPC Class Codes: H04N 21/2385 : Channel allocation H04N21/266 takes precedence; Bandwidth allocation H04N21/24 takes precedence ; allocation of channels according to the instantaneous demands of the users in time-division multiplex systems H04J3/1682; admission control, resource allocation in open networks H04L12/5692; arrangements for maintenance or administration in data switching networks involving bandwidth and capacity management H04L41/0896; negotiating bandwidth in wireless networks H04W28/16
• CPC Class Codes: H04N 21/2402 : Monitoring of the downstream path of the transmission network, e.g. bandwidth available traffic monitoring in data switching networks H04L43/00; monitoring data switching networks utilization H04L43/0876
• CPC Class Codes: H04N 21/4382 : Demodulation or channel decoding, e.g. QPSK demodulation analog front ends or means for connecting modulators, demodulators or transceivers to a transmission line H04L27/0002
• CPC Class Codes: H04N 21/6118 : involving cable transmission, e.g. using a cable modem
• CPC Class Codes: H04N 21/6137 : involving transmission via a telephone network, e.g. POTS
• CPC Class Codes: H04N 21/6168 : involving cable transmission, e.g. using a cable modem
• CPC Class Codes: H04N 7/17309 : Transmission or handling of upstream communications
• CPC Class Codes: H04N 7/22 : Adaptations for optical transmission
• CPC Class Codes: H04W 24/00 : Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 24/08 : Testing, supervising or monitoring using real traffic
• CPC Class Codes: Y02D 30/50 : in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A apparatus for providing a Fast Fourier Transform (FFT) and an inverse FFT is provided. The apparatus comprises a radix-N core. The radix-N core includes at least N multipliers. The radix-N core also includes a twiddle-factor lookup table that stores complex twiddle-factors. The twiddle-factor lookup table is coupled to one input of each of the multipliers. The radix-N core also includes a conversion random access memory (RAM) that stores transform points. The conversion RAM is coupled to another input of each of the multipliers. The radix-N core also includes an array of at least N-times-N adder-subtracter-accumulators.

Claims

1. An apparatus for providing a Fast Fourier Transform to convert a signal between time and frequency domains comprising:

a radix-N core, the radix-N core including;

at least N multipliers;

a twiddle-factor lookup table storing complex twiddle factors, the twiddle-factor lookup table coupled to one input of each one of the multipliers;

a conversion random access memory storing transform points, the conversion random access memory coupled to another input of each one of the multipliers;

an array of at least N-times-N adder-subtractor-accumulators;

a set of holding latches that hold both a real and imaginary portion respectively of a first transform point, and

wherein a fetch of a real portion of a first twiddle factor from the twiddle-factor lookup table is interleaved in time with a fetch of an imaginary portion of the first twiddle factor, and

two substantially simultaneous first and second multiply operations take place in the N multipliers to multiply the real portion of first twiddle factor by the real and imaginary portion respectively of the first transform point, and

two substantially simultaneous third and fourth multiply operations take place in the N multipliers to multiply the imaginary portion of the first twiddle factor by the real and imaginary portion respectively of the first transform point.

2. The apparatus according to claim 1, wherein:

the at least N multipliers include at least 2×

N multipliers;

the array of at least N-times-N adder-subtractor-accumulators are used to accumulate real portions of results,

and further comprising

an array of at least N-times-N adder-subtractor-accumulators that are used to accumulate imaginary portions of the results.

3. The apparatus according to claim 2, wherein:

at least some of the adder-subtractor-accumulators have at least four operand inputs.

4. The apparatus according to claim 1, wherein:

the at least N multipliers include at least 2×

N multipliers;

the array of at least N-times-N adder-subtractor-accumulators are used to accumulate real portions of results,

and further comprising

an array of at least N-times-N adder-subtractor-accumulators that are used to accumulate imaginary portions of the results.

5. The apparatus according to claim 4, wherein:

at least some of the adder-subtractor-accumulators have at least four operand inputs.

6. An apparatus for providing a Fast Fourier Transform to convert a signal between time and frequency domains comprising:

a radix-4 butterfly core, the radix-4 butterfly core including;

at least eight multipliers;

a twiddle-factor lookup table storing complex twiddle factors, the twiddle-factor lookup table coupled to one input of each one of the multipliers;

a conversion random access memory storing transform points, the conversion random access memory coupled to another input of each one of the multipliers;

an array of at least thirty-two adder-subtractor-accumulators coupled to outputs of the multipliers, each adder-subtractor-accumulator capable of performing at least a five-way addition/subtraction operation;

a sequencer coupled to the twiddle-factor lookup table, to the conversion random access memory, and to the adder-subtractor-accumulators in order to control normal and transposed butterfly operations;

a set of holding latches that hold both a real and imaginary portion respectively of a first, second, third and fourth transform point, and

wherein a fetch of real portions of a first, second, third and fourth twiddle factors from the twiddle-factor lookup table is interleaved in time with a fetch of imaginary portions of the first, second, third and fourth twiddle factors, and

eight substantially simultaneous first, second, third, fourth, fifth, sixth, seventh and eighth multiply operations take place in the eight multipliers to multiply the real portion of the first twiddle factor by the real and imaginary portion respectively of the first transform point,

the real portion of the second twiddle factor by the real and imaginary portion respectively of the second transform point,

the real portion of the third twiddle factor by the real and imaginary portion respectively of the third transform point, and

the real portion of the fourth twiddle factor by the real and imaginary portion respectively of the fourth transform point, and

eight substantially simultaneous ninth, tenth, eleventh, twelfth, thirteenth, fourteenth, fifteenth and sixteenth multiply operations take place in the eight multipliers to multiply

the imaginary portion of the first twiddle factor by the real and imaginary portion respectively of the first transform point,

the imaginary portion of the second twiddle factor by the real and imaginary portion respectively of the second transform point,

the imaginary portion of the third twiddle factor by the real and imaginary portion respectively of the third transform point, and

the imaginary portion of the fourth twiddle factor by the real and imaginary portion respectively of the fourth transform point.

7. The apparatus according to claim 6, wherein:

at least sixteen of the at least thirty-two adder-subtractor-accumulators are used to accumulate real portions of results, and

at least sixteen of the at least thirty-two adder-subtractor-accumulators are used to accumulate imaginary portions of the results.

8. The apparatus according to claim 7, wherein:

at least some of the adder-subtractor-accumulators have at least four operand inputs.

9. The apparatus according to claim 6, wherein:

at least sixteen of the at least thirty-two adder-subtractor-accumulators are used to accumulate real portions of results, and

at least sixteen of the at least thirty-two adder-subtractor-accumulators are used to accumulate imaginary portions of the results.

10. The apparatus according to claim 9, wherein:

at least some of the adder-subtractor-accumulators have at least four operand inputs.

11. A method for providing a Fast Fourier Transform to convert a signal between time and frequency domains comprising the steps of:

fetching substantially simultaneously both the real and imaginary portions of at least a first and second transform point;

fetching substantially simultaneously the real portions of at least a first and second twiddle factor, sequential with fetching substantially simultaneously the imaginary portions of at least the first and second twiddle factor;

multiplying substantially simultaneously the real portions of at least a first and second twiddle factor by the real and imaginary portions of at least a first and second transform point to generate a first, second, third and fourth product, sequential with multiplying substantially simultaneously the imaginary portions of at least the first and second twiddle factor by the real and imaginary portions of at least a first and second transform point to generate a fifth, sixth, seventh and eighth product;

holding in latches the real and imaginary portions of the at least a first and second transform point so that the real and imaginary portions of the at least a first and second transform point can be used in both of said multiplying steps;

accumulating the first, second, third and fourth products into four separate values;

accumulating the fifth, sixth, seventh and eighth products with the four separate values;

accumulating the first, second, third and fourth products into two separate values;

accumulating the fifth, sixth, seventh and eighth products with the two separate values;

during a first pass;

accumulating the first, second, third and fourth products into two separate values; and

accumulating the fifth, sixth, seventh and eighth products with the two separate values; and

during a second pass;

accumulating the first, second, third and fourth products into four separate values; and

accumulating the fifth, sixth, seventh and eighth products with the four separate values.