| Class / Patent application number | Description | Number of patent applications / Date published |
|---|
| 708404000 | Fast Fourier Transform (i.e., FFT) | 82 |
| 20080208944 | DIGITAL SIGNAL PROCESSOR STRUCTURE FOR PERFORMING LENGTH-SCALABLE FAST FOURIER TRANSFORMATION - A digital signal processor structure by performing length-scalable Fast Fourier Transformation (FFT) discloses a single processor element (single PE), and a simple and effective address generator are used to achieve length-scalable, high performance, and low power consumption in split-radix-2/4 FFT or IFFT module. In order to meet different communication standards, the digital signal processor structure has run-time configuration to perform for different length requirements. Moreover, its execution time can fit the standards of Fast Fourier Transformation (FFT) or Inverse Fast Fourier Transformation (IFFT). | 08-28-2008 |
| 20080215656 | FAST FOURIER TRANSFORM CIRCUIT AND FAST FOURIER TRANSFORM METHOD - A fast Fourier transform circuit includes a computation component, an extraction component and a setting component. The extraction component, at each step of the computation, extracts, from computation result data points calculated by the computation component, data in a pre-specified range with a number of bits the same as a predetermined number of bits, which is an effective range for a butterfly computations. The setting component sets the data points of the predetermined number of bits which have been extracted by the extraction component to serve as input data when butterfly computations of a next step are to be performed by the computation component. | 09-04-2008 |
| 20080256159 | Multi-Stream Fft for Mimo-Ofdm Systems - The present invention proposes a signal processor for Fast Fourier Transformation, FFT, of M | 10-16-2008 |
| 20080288568 | Low power Fast Hadamard transform - Fast Hadamard transforms (FHT) are implemented using a pipelined architecture having an input stage, a processing stage, and an output stage, the FHT having a single internal loop back between the output stage and the input stage, the processing stage having at least one Hadamard processing unit. The FHT implementations provided both forward and inverse transformations, and, lossless normalized and lossfull unnormalized transformations, while the FHT implementation includes only multiplexers, demultiplexer, latches, and shift registers, and while, the processing unit stage includes processing units using only shift registers and effective adders, for fast, low power, and low weight Hadamard transform implementations. | 11-20-2008 |
| 20080288569 | PIPELINED FFT PROCESSOR WITH MEMORY ADDRESS INTERLEAVING - An interleaver for use with transform processors provides an address generator allowing for implementation using a reduced memory foot print, and permitting interleaving of an input sequence while minimizing latency. | 11-20-2008 |
| 20080307026 | Memory Address Generating Method and Twiddle Factor Generator Using the Same - 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. | 12-11-2008 |
| 20080320069 | VARIABLE LENGTH FFT APPARATUS AND METHOD THEREOF - The invention discloses a variable length FFT apparatus and a method thereof. The FFT apparatus includes a split-radix based FFT unit and a multiplexing unit. The split-radix based FFT unit has a plurality of processing elements cascaded in a series. The multiplexing unit is coupled to the split-radix based FFT unit, and is for selectively bypassing at least one of the processing elements according to the size of input data when the split-radix based FFT unit performs the FFT computation on the input data. The FFT apparatus of the present invention therefore has a simple structure and is flexible for any FFT size. | 12-25-2008 |
| 20090006516 | Methods and systems for processing and displaying data - Methods and systems of processing and displaying data that include obtaining and processing time-time data to obtain an in-phase sum of the time-time data, and of providing and utilizing the in-phase sum of the time-time data to generate a graphical display of the Radon sum of the time-time data. The in-phase sum of the time-time data may be provided for display, for example, by outputting a data signal suitable for generating a graphical representation of the in-phase sum of the time-time data, and the output data signal may be utilized to generate a graphical representation of the in-phase sum of the time-time data. | 01-01-2009 |
| 20090013021 | VARIABLE LENGTH FFT SYSTEM AND METHOD - The present invention discloses a variable length fast Fourier transform (FFT) system and a method for performing the FFT system in a global navigation satellite system (GNSS) signal acquisition and tracking, which includes a memory and a number of processing elements. Based on the GNSS signal tracking, the variable length FFT system performs a first FFT operation together with a first data length. Based on the GNSS signal acquisition, the variable length FET system is divided into several FFT subsystems to simultaneously perform different operations with various data lengths different from the first data length. Thus, the variable length FFT system can enhance the hardware utility and increase throughputs. | 01-08-2009 |
| 20090037506 | RECEIVING APPARATUS AND METHOD - A FFT circuit performs M×R×Q-point fast Fourier transform of received signals, wherein M is an over-sampling rate of the received signals, Q is a chip repetition unit and R is a chip repetition rate. A weighting multiplier multiplies a frequency component having frequency component number equal to an integral multiple of R among M×R×Q frequency components output from the fast Fourier transform circuit by a weighting coefficient for propagation channel equalization, and multiplies the frequency components other than the integral multiple of R. An inverse fast Fourier transform circuit receives outputs of weighting multiplier and performs inverse fast Fourier transform of the frequency component having a frequency number equal to the integral multiple of R. | 02-05-2009 |
| 20090049112 | INTERLEAVED METHOD FOR PARALLEL IMPLEMENTATION OF THE FAST FOURIER TRANSFORM - The present invention generally relates to a method for computing a Fast Fourier Transform (FFT). In one embodiment, the present invention relates to an interleaved method for computing a Fast Fourier Transform (FFT). | 02-19-2009 |
| 20090055459 | FREQUENCY-DOMAIN EQUALIZER - A digital signal processing structure includes a processing unit configured to perform a fast Fourier transformation of length N on signal samples of word length WL, wherein the processing unit is configured to vary during operation the values of N and WL_in in a reverse fashion with respect to one another. A frequency-domain equalizer includes a length N, wherein the value of N is variable during operation. | 02-26-2009 |
| 20090063604 | Vdsl2 Transmitter/Receiver Architecture - The invention suggests a novel pipeline FFT/IFFT architecture that not only produces time-domain samples (after IFFT) but also pushes time-domain samples into FFT in a time-based sequential order. This reduces external memory requirement for buffering the time-domain samples. Also the design is based on a mixed radix-2 and radix-22 algorithm aiming at reducing number of multipliers and adders. Compared with other FFT/IFFT design methodologies such as radix-4, it achieves the minimum multiplier use, the minimum adder use and the minimum operating memory use. On the other hand, the design architecture not only can support different FFT/IFFT size required by different VDSL2 profiles but also utilizing a novel pipeline control mechanism to reduce logic switching at low-speed profiles. This effectively further reduces the power consumption at lower profiles and enables our VDSL2 digital chipsets to compete with ADSL2+ systems in terms of power consumption. | 03-05-2009 |
| 20090077150 | METHOD AND SYSTEM FOR CONTROLLING A VOLTAGE WAVEFORM - A method of automating a process for controlling a voltage waveform applied to an object is provided. A first waveform for applying to the object is received. A first FFT of the first waveform is calculated. A second waveform for input to the waveform generator is determined based on the first waveform. The determined second waveform is sent to a waveform generator. A third waveform is received that is measured across the object based on a waveform generated by the waveform generator. A second FFT of the received third waveform is calculated. The third waveform is compared with the first waveform to determine a convergence status of the third waveform. If the determined convergence status is not converged, an updated waveform is calculated based on the first FFT and the second FFT and the process is repeated with the updated waveform as the determined second waveform. | 03-19-2009 |
| 20090106341 | Dynamically Reconfigurable Shared Baseband Engine - A reconfigurable processing block for use in a communications system capable of supporting multiple communication formats. The reconfigurable processing block comprises a plurality of modular processing elements. The processing elements comprise a pn-code generating means, a twiddle factor generating means, coefficient memory means, input data memory means, output data memory means, delay means, complex multiply means, complex add means, complex subtract means and control means which controls how the processing elements are interconnected. The controlling means is arranged such that it controls the reconfigurable processing block so that it selectively implements one of a radix-2 butterfly core, a pn-correlator, an auto-correlator and a complex adder. | 04-23-2009 |
| 20090112959 | Single-cycle FFT butterfly calculator - In accordance with exemplary embodiments, a Fast Fourier Transform (FFT) architecture includes elements that perform a radix-2 FFT butterfly in one processor clock cycle at steady state. Some exemplary implementations of the FFT architecture incorporate register and data path elements that relieve memory bandwidth limitations by pairing operands consumed by and results generated by two adjacent butterflies in the overall N-point FFT operation. | 04-30-2009 |
| 20090150470 | FAST FOURIER TRANSFORMATION CIRCUIT - Provided is a fast Fourier transformation circuit capable of optimizing an operation resource while matching a plurality of communication systems. In this circuit, an FFT circuit ( | 06-11-2009 |
| 20090172062 | EFFICIENT FIXED-POINT IMPLEMENTATION OF AN FFT - A fast Fourier transform (FFT) is performed on first-fourth input data points. Real and imaginary portions of the first input data point are stored in first and second registers. Real and imaginary portions of the second input data point are stored in third and fourth registers. Real and imaginary portions of the third input data point are stored in fifth and sixth registers. Real and imaginary portions of the fourth input data point are stored in seventh and eighth registers. Operations are performed in place in the first-eight registers and in a ninth register to generate a first-fourth output data points stored in the registers that represent an FFT of the first-fourth input data points. The radix-4 FFT may be cascaded to perform higher bit-level FFTs on sets of data points. Furthermore, the data points may be reordered between cascaded radix-4 FFTs to enable efficient use of memory. | 07-02-2009 |
| 20090248774 | REUSE ENGINE WITH TASK LIST FOR FAST FOURIER TRANSFORM AND METHOD OF USING THE SAME - An improved processing engine for performing Fourier transforms includes an instruction processor configured to process sequential instruction software commands and a Fourier transform engine coupled to the instruction processor. The Fourier transform engine is configured to perform Fourier transforms on a serial stream of data. The Fourier transform engine is configured to receive configuration information and operational data from the instruction processor via a set of software tasks. | 10-01-2009 |
| 20090248775 | APPARATUS AND METHOD FOR AREA AND SPEED EFFICIENT FAST FOURIER TRANSFORM (FFT) PROCESSORING WITH RUNTIME AND STATIC PROGRAMMABILITY OF NUMBER OF POINTS - An apparatus and method for area and speed efficient fast Fourier transform (FFT) processing comprising mapping a one-dimensional DFT to a multi-dimensional representation; re-indexing the multi-dimensional representation as a radix 2 | 10-01-2009 |
| 20090254598 | Folding of Input Data Values to a Transform Function - A method of processing a set of input data values comprises the steps of providing said input data values serially to circuitry comprising a number of memory elements; and performing in said circuitry a transform function to obtain a set of transformed data values. The method further comprises the steps of delaying a subset of said set of input data values under use of said memory elements; providing a modified set of data values by adding individual delayed data values to individual non-delayed data values from said set of input data values; and performing said transform function on said modified set of data values. In this way a transform function can be evaluated at fewer output data values than available input data values without increasing the memory requirements considerably. | 10-08-2009 |
| 20090259706 | Method for establishing a simulating signal suitable for estimating a complex exponential signal - A method for establishing a simulating signal suitable for estimating a complex exponential signal includes the following computer-implemented steps: sampling a time domain signal of a physical system to obtain a sampling signal; transforming the sampling signal to a frequency domain signal using Fast Fourier Transform; determining parameters of the frequency domain signal; establishing a simulating signal; establishing a target function which is a deviation of the simulating signal from the sampling signal; obtaining correcting factors; iterating the target function using a gradient method and the correcting factors to obtain three sets of iterated signal parameters; obtaining corrected parameters using quadratic interpolation; and using the corrected parameters to correct the simulating signal, and establishing an updated target function. The simulating signal can be used to estimate dynamic behavior of the physical system if the updated target function converges to a tolerable range. | 10-15-2009 |
| 20100011043 | FAST FOURIER TRANSFORM ARCHITECTURE - A last fourier transform architecture has parallel data processing paths. Input data is applied to the parallel data processing paths in a repeating sequence, and processed in those paths. Data sequencers are used to combine the outputs from the data processing paths into the required sequence. | 01-14-2010 |
| 20100011044 | Device and method for determining and applying signal weights - The solution X | 01-14-2010 |
| 20100011045 | Device and method for applying signal weights to signals - Signal weights corresponding to an initial system of equations with a block coefficient matrix T | 01-14-2010 |
| 20100011046 | APPARATUS AND METHOD FOR VARIABLE FAST FOURIER TRANSFORM - The present invention relates to an apparatus and method for variable fast Fourier transform. According to an embodiment of the present invention, two n-point fast Fourier transform (FFT) processors are used to generate two n-point FFT output data or one | 01-14-2010 |
| 20100017452 | MEMORY-BASED FFT/IFFT PROCESSOR AND DESIGN METHOD FOR GENERAL SIZED MEMORY-BASED FFT PROCESSOR - For a large size FFT computation, this invention decomposes it into several smaller sizes FFT by decomposition equation and then transform the original index from one dimension into multi-dimension vector. By controlling the index vector, this invention could distribute the input data into different memory banks such that both the in-place policy for computation and the multi-bank memory for high-radix structure could be supported simultaneously without memory conflict. Besides, in order to keep memory conflict-free when the in-place policy is also adopted for I/O data, this invention reverses the decompose order of FFT to satisfy the vector reverse behavior. This invention can minimize the area and reduce the necessary clock rate effectively for general sized memory-based FFT processor design. | 01-21-2010 |
| 20100030831 | MULTI-FPGA TREE-BASED FFT PROCESSOR - A fast Fourier transform (FFT) computation system comprises a plurality of field programmable gate arrays (FPGAs), a plurality of initial calculations modules, a plurality of butterfly modules, a plurality of external interfaces, and a plurality of FPGA interfaces. The FPGAs may include a plurality of configurable logic elements that may be configured to perform mathematical calculations for the FFT. The initial calculations modules may be formed from the configurable logic elements and may be implemented according to a split-radix tree architecture that includes a plurality of interconnected nodes. The initial calculations modules may perform the initial split-radix calculations of the FFT. The butterfly modules may be formed from the configurable logic elements and may be implemented according to the split-radix tree architecture to perform at least a portion of the FFT computation in an order that corresponds to the connection of the nodes of the split-radix tree architecture. The FPGA interfaces are included in each FPGA and allow communication between the FPGAs. The external interfaces are also included in each FPGA and allow communication with one or more external devices in order to receive data which requires an FFT computation and to transmit the FFT computation results. | 02-04-2010 |
| 20100070551 | FOURIER TRANSFORM PROCESSING AND TWIDDLE FACTOR GENERATION - In a data processing system, having a twiddle factor unit, a method for performing a mixed-radix discrete Fourier transform (DFT) having a block size, N, and a maximum block size, Nmax, wherein the maximum block size includes a radix that is not a power of 2 is provided. The method includes receiving a delta value at an input of the twiddle factor unit, the delta value representing a ratio of a modified maximum bock size to the block size, wherein the modified maximum block size is a power of 2. The method further includes using the delta value to obtain a step size for generating indices of a look-up table stored within the twiddle factor unit, wherein the look-up table stores real and imaginary components of twiddle factors corresponding to a set of block sizes of the DFT. | 03-18-2010 |
| 20100082722 | Methods and Apparatuses for Detection and Estimation with Fast Fourier Transform (FFT) in Orthogonal Frequency Division Multiplexing (OFDM) Communication Systems - Methods and apparatuses are provided for a fast Fourier transform (FFT)/inverse fast Fourier transform (IFFT) architecture that not only allows for efficient computation of N-point FFT/IFFT transform (N=2 | 04-01-2010 |
| 20100088356 | FAST COMPUTATION OF GENERAL FOURIER TRANSFORMS ON GRAPHICS PROCESSING UNITS - Described is a technology for use with general discrete Fourier transforms (DFTs) performed on a graphics processing unit (GPU). The technology is implemented in a general library accessed through GPU-independent APIs. The library handles complex and real data of any size, including for non-power-of-two data sizes. In one implementation, the radix-2 Stockham formulation of the fast Fourier transform (FFT) is used to avoid computationally expensive bit reversals. For non-power of two data sizes, a Bluestein z-chirp algorithm may be used. | 04-08-2010 |
| 20100094920 | DEVICE AND METHOD FOR EXECUTING FOURIER TRANSFORM - A Fourier transform device generates a first sequence according to an input sequence based on a stored lookup table, and generates an output sequence by performing a butterfly operation on the first sequence a plurality of times. Therefore, hardware capacity and power consumption of the Fourier transform device can be reduced | 04-15-2010 |
| 20100106758 | COMPUTING DISCRETE FOURIER TRANSFORMS - A system described herein includes a selector component that receives input data that is desirably transformed by way of a Discrete Fourier Transform, wherein the selector component selects one of a plurality of algorithms for computing the Discrete Fourier Transform from a library based at least in part upon a size of the input function. An evaluator component executes the selected one of the plurality of algorithms to compute the Discrete Fourier Transform, wherein the evaluator component causes leverages shared memory of a processor to compute the Discrete Fourier Transform. | 04-29-2010 |
| 20100106759 | Methods and apparatus for reordering data - A data reordering system for determining addresses associated with a vector of transformed data and corresponding method of reordering transformed data, where the data reordering system includes: a first transform function coupled to a data vector and operable to provide the vector of transformed data; a reordering function, including a plurality of counters, that is operable to determine a plurality of offset addresses, with a, respective, offset address for each element in the vector of transformed data; and an adder operable to add a base address that corresponds to the first address to the each, respective, offset address to provide a sequence of addresses suitable for accessing the vector of transformed data to provide a re-sequenced vector of transformed data. | 04-29-2010 |
| 20100153479 | APPARATUS FOR SETTING UP START POINT OF FAST FOURIER TRANSFORM AND METHOD THEREOF - Disclosed are a fast Fourier transform (FFT) start point setting apparatus, and a method thereof. An FFT start point according to a synchronization acquisition result is moved to a CP direction by a predetermined sample offset and perform FFT. | 06-17-2010 |
| 20100161699 | HIGH-SPEED DISCRETE FOURIER TRANSFORM APPARATUS AND METHOD THEREOF - Provided are a high-speed Discrete Fourier Transform (DFT) apparatus and a method thereof. The high-speed DFT apparatus includes a zero padding unit, a Fast Fourier Transform (FFT) unit, and a preamble index decision unit. The zero padding unit receives a first input signal having a length of a prime number and changes the first input signal into a second input signal having a length of an exponentiation of 2. The FFT unit performs a FFT on the second input signal outputted from the zero padding unit. The preamble index decision unit detects a preamble index from an output signal from the FFT unit. | 06-24-2010 |
| 20100169402 | FAST FOURIER TRANSFORM PROCESSOR - An FFT processor is disclosed, which includes a first multi-pipelined MDC unit, a second multi-pipelined MDC unit and a switching network. The first multi-pipelined MDC unit and the second multi-pipelined MDC unit respectively employ a plurality of MDC circuits to change the positions of the delayers thereof in parallel way. By changing the operation time sequence of the signals in the first multi-pipelined MDC unit and the second multi-pipelined MDC unit, the first multi-pipelined MDC unit is able to directly send the operation results to the second multi-pipelined MDC unit through the switching network. | 07-01-2010 |
| 20100174769 | In-Place Fast Fourier Transform Processor - An N-point Fast Fourier Transform (FFT) using mixed radix stages with in-place data sample storage may be performed by decomposing N into a product of R sequential mixed radix stages of radix-r(i). N data samples are partitioned into at least B memory banks, where B is equal to a largest radix of the R radix stages. Each input data sample to each radix-r(i) butterfly comes from r(i) different memory banks and the output data samples are written to the same memory locations in the r(i) memory banks. Determining from which memory bank the input data samples and output data samples of the butterflies are stored is done based on the radix size and sequential position of the radix stage. Determining the address of the input data samples and the output data samples within each memory bank is based on the radix size and sequential position of the radix stage. | 07-08-2010 |
| 20100179978 | FFT-BASED PARALLEL SYSTEM WITH MEMORY REUSE SCHEME - A method may include storing N number of Fast Fourier Transform (FFT) data points into x-memories, N and x being integers greater than one, and the x-memories having a total memory capacity equivalent to store the N number of FFT data points, and reading K FFT data points of the N number of FFT data points from each of the x-memories so that the N number of FFT data points are read, K being an integer greater than one. The method may further include performing parallel radix-m FFTs on the x*K number of FFT data points, multiplying the x*K number of FFT data points by twiddle factors to obtain resultants, shifting the resultants, and writing back the shifted resultants of the x*K number of FFT data points to the x-memories. The method may also include repeating the reading, the multiplying, the shifting and the writing back until the N number of FFT data points have been completely transformed into an FFT resultant, and where there is x*K number of FFT data points available for processing during every repetition, and outputting the FFT resultant. | 07-15-2010 |
| 20100185715 | Method and Device for Transform Computation - A method of operating a data-processing unit to produce a transform comprises calculating first and second output data values based at least on first and second input data values. The method comprises reading the first and second input data values from locations of a first buffer, the locations being determined by first and second read addresses based on first and second read indices. The method also comprises writing the first and second output data values to adjacent memory locations of a second buffer during a single write cycle. Furthermore, the method comprises reading third and fourth input data values from locations of the second buffer, the locations being determined by third and fourth read addresses determined by swapping at least two of the bits of the first and second read indices respectively. A data-processing unit for producing a transform, a transform-computation unit and an electronic apparatus are also described. | 07-22-2010 |
| 20100191792 | Signal Processing with Fast S-Transforms - The ability to examine the frequency content of a signal is critical in a variety of fields, and many techniques have been proposed to fill this need, including the Fourier and wavelet family of transforms. One of these, the S-transform, is a Fourier based transform that provides simultaneous time and frequency information similar to the wavelet transform but uses sinusoidal basis functions to produce true frequency and globally referenced phase measurements. It has been shown to be useful in several medical imaging applications but its use is limited due to high computational requirements of the original, continuous form. The described embodiments include a general framework for describing linear time-frequency transforms, using the Fourier, wavelet and S-transforms as examples. As an illustration of the utility of this formalism, a fast discrete S-transform algorithm is developed that has the same computational complexity as the fast Fourier transform. | 07-29-2010 |
| 20100223312 | CORDIC-BASED FFT AND IFFT APPARATUS AND METHOD - Provided two CORDIC processors, each including: two input ports representing real and imaginary input ports; and two output ports representing real and imaginary output ports; wherein real and imaginary parts of a first input signal are applied to the imaginary input ports of the first and second CORDIC processors; real and imaginary parts of a second input signal are applied to the real input ports of the first and second CORDIC processors; the first and second CORDIC processors rotate the respective input signals applied thereto by 45 degrees in the clockwise direction; respective data from the real output ports of said first and second CORDIC processors constitute real and imaginary parts of a first output signal; and respective data from the imaginary output ports of said first and second CORDIC processors constitute real part and imaginary part of a second output signal. | 09-02-2010 |
| 20100299383 | PIPELINED FFT CIRCUIT AND TRANSFORM METHOD THEREOF - A pipelined FFT circuit used for processing a sequential input data with a set of N samples comprises a data division unit, a data-preprocessing unit and M sets of data computation unit. The data division unit is used for dividing the sequential input data into a first input data stream and a second input data stream. The data-preprocessing unit receives the first and second input data streams and orders the first input data stream to an odd number-index data stream, the second input data stream to an even number-index data stream respectively. Each of the data computation units has a data switch and a butterfly computator connected with the data switch, where M=log | 11-25-2010 |
| 20110099216 | SYSTEM AND METHOD FOR CONFIGURABLE MIXED RADIX FFT ARCHITECTURE FOR MULTIMODE DEVICE - A configurable fast Fourier transforms (FFT) apparatus to compute radix-2 and non-radix-2 calculations. The configurable FFT apparatus includes a data input, a data output, an interconnect, and a configuration manager. The data input retrieves an input data segment from a memory device. The data output stores processed data to the memory device. The interconnect routes radix FFT signals of multi-type radix configurations from the data input to the data output. The configuration manager dynamically configures the interconnect according to a determination of a current radix configuration. | 04-28-2011 |
| 20110153706 | FAST FOURIER TRANSFORM ARCHITECTURE - A fast Fourier transform (FFT) architecture operable to transform data of variable point size includes a plurality of input ports, a plurality of memory elements, a crosspoint switch, a plurality of processing elements, and a plurality of output ports. The inputs ports read time-domain data from an external source. The memory elements store input data, intermediate calculation results, and output data. The crosspoint switch allows data to flow from any one architecture component to any other architecture component. The processing elements perform the FFT calculation. The output ports write frequency-domain data to an external source. | 06-23-2011 |
| 20110225224 | Efficient Complex Multiplication and Fast Fourier Transform (FFT) Implementation on the ManArray Architecture - Efficient computation of complex multiplication results and very efficient fast Fourier transforms (FFTs) are provided. A parallel array VLIW digital signal processor is employed along with specialized complex multiplication instructions and communication operations between the processing elements which are overlapped with computation to provide very high performance operation. Successive iterations of a loop of tightly packed VLIWs are used allowing the complex multiplication pipeline hardware to be efficiently used. In addition, efficient techniques for supporting combined multiply accumulate operations are described. | 09-15-2011 |
| 20110289130 | FFT COMPUTING APPARATUS AND POWER COMPUTING METHOD - In an FFT computing apparatus, a computation-unit switching detection unit detects timing at which a complex multiplication is not being carried out in said butterfly computation of FFT computation, and a complex-multiplication power-computation unit switches computation between complex multiplication and power computation, based on a detection result by said computation-unit switching detection unit. The complex-multiplication power-computation unit performs power computation at timing at which complex multiplication is not carried out in said butterfly computation of FFT computation. | 11-24-2011 |
| 20120005249 | Method and processing apparatus for implementing IFFT by using FFT - A method for realizing IFFT by FFT is provided, which comprises: performing a left mirror permutation on an input data sequence, then performing FFT, and dividing the result with N, so as to obtain IFFT processing data; or performing FFT on an input data sequence, then performing a left mirror permutation on the result of FFT and being divided by N, so as to obtain IFFT processing data; the left mirror permutation is: inverting the sequence of the other data except the first data; the N is the length of the input data sequence. Also, an IFFT processing apparatus comprising an FFT computing unit and a left mirror permutation unit is provided. | 01-05-2012 |
| 20120011184 | APPARATUS AND METHOD FOR SPLIT-RADIX-2/8 FAST FOURIER TRANSFORM - An SR-2/8 FFT apparatus includes a memory, an SRFFT processor and a control unit. The control unit includes an input control block, an SRFFT control block and an output control block. The input control block loads memory banks with the input data in a first order, such that the SRFFT processor is able to retrieve data from the memory banks simultaneously in a single clock cycle. The SRFFT control block determines a decomposition structure of a 2 | 01-12-2012 |
| 20120016923 | Circuit and method for implementing FFT/IFFT transform - A circuit and a method for implementing Fast Fourier Transform (FFT)/Inverse Fast Fourier Transform (IFFT) are provided. The method includes: determining the number m of iterations, depth dl of the first and second Random Access Memories (RAMs), depth d | 01-19-2012 |
| 20120041996 | Parallel pipelined systems for computing the fast fourier transform - The present invention relates to the design and implementation of parallel pipelined circuits for the fast Fourier transform (FFT). In this invention, an efficient way of designing FFT circuits using folding transformation and register minimization techniques is proposed. Based on the proposed scheme, novel parallel-pipelined architectures for the computation of complex fast Fourier transform are derived. The proposed architecture takes advantage of under utilized hardware in the serial architecture to derive L-parallel architectures without increasing the hardware complexity by a factor of L. The proposed circuits process L consecutive samples from a single-channel signal in parallel. The operating frequency of the proposed architecture can be decreased which in turn reduces the power consumption. The proposed scheme is general and suitable for applications such as communications, biomedical monitoring systems, and high speed OFDM systems. | 02-16-2012 |
| 20120131081 | Hybrid Fast Fourier Transform - A hybrid fast Fourier transform (FFT) combines a prime-factor algorithm (PFA) with a Cooley-Tukey algorithm (CTA). The combining includes performing combined permutations and combined weight multiplications during CTA processing using permutations and weights derived from the PFA processing and the CTA processing to improve efficiency. The combined permutations can include the last permutation of the PFA processing combined with the first permutation of the CTA processing. The combined weights can include multiplying weights resulting from a permutation that was omitted during PFA processing by “twiddle” factors generated during CTA processing. The combined weights can be pre-computed and stored in table where they can be applied during CTA processing. | 05-24-2012 |
| 20120143936 | RADIX-8 FIXED-POINT FFT LOGIC CIRCUIT CHARACTERIZED BY PRESERVATION OF SQUARE ROOT-i OPERATION - A system and method to reduce roundoff error of Fast Fourier transform (FFT) operation. Data which comes out as an irrational number (a square root) out of twiddle factors on a complex plane, included in a butterfly operation (8 | 06-07-2012 |
| 20120166507 | METHOD AND APPARATUS OF PERFORMING FAST FOURIER TRANSFORM - Disclosed are a method and apparatus of performing a fast Fourier transform (FFT). The apparatus include a plurality of single-path delay feedback (SDF) butterfly blocks which performs butterfly operations, respectively; a plurality of memories which are connected to the SDF butterfly blocks, respectively; and a controller which controls the plurality of SDF butterfly blocks, wherein the plurality of SDF butterfly blocks are connected in a pipeline structure and thus output from one SDF butterfly block is input to a following SDF butterfly block. | 06-28-2012 |
| 20120166508 | FAST FOURIER TRANSFORMER - A fast Fourier transformer (FFT) includes a radix-2 butterfly unit configured to perform a butterfly operation on input data; a buffer unit configured to buffer data outputted from the radix-2 butterfly unit and output the buffered data to the radix-2 butterfly unit; a multiplexing unit configured to selectively output a twiddle factor; and a constant multiplier configured to multiply the data outputted from the radix-2 butterfly unit by the twiddle factor outputted from the multiplexing unit. | 06-28-2012 |
| 20120221617 | Methods and apparatus for fast matrix multiplication and fast solving of matrix equations based on generalized convolution - A method of fast matrix multiplication and a method and apparatus for fast solving of a matrix equation are disclosed. They are useful in many applications including image blurring, deblurring, and 3D image reconstruction, in 3D microscopy and computer vision. The methods and apparatus are based on a new theoretical result—the Generalized Convolution Theorem (GCT). Based on GCT, matrix equations that represent certain linear integral equations are first transformed to equivalent convolution integral equations through change of variables. Then the resulting convolution integral equations are evaluated or solved using the Fast Fourier Transform (FFT). Evaluating a convolution integral corresponds to matrix multiplication and solving a convolution integral equation corresponds to solving the related matrix equation through deconvolution. Carrying-out these convolution and deconvolution operations in the Fourier domain using FFT speeds up computations significantly. These results are applicable to both one-dimensional and multi-dimensional integral equations. | 08-30-2012 |
| 20120254273 | Information Processing Apparatus, Control Method Thereof, Program, and Computer-Readable Storage Medium - The present invention provides technologies for implementing a high-speed Fast Fourier Transform (FFT) algorithm with a small memory. An information processing apparatus for performing a radix-2 FFT on a data sequence comprises storage means, reading means, a plurality of butterfly operation means, writing means, and control means, wherein each stage of the FFT operation includes a plurality of operation steps, and at every operation step the control means controls each of the means so that: the reading means reads from the storage means sets of data elements referred by storage addresses A, A+1, A+2 | 10-04-2012 |
| 20120278373 | DATA REARRANGING CIRCUIT, VARIABLE DELAY CIRCUIT, FAST FOURIER TRANSFORM CIRCUIT, AND DATA REARRANGING METHOD - A data rearranging circuit includes variable delay means and control means. The variable delay means, by imparting a delay of a number of delay cycles that differs for each input cycle and moreover for each port to each unit of data of a data group that is applied as input to a plurality of ports and in a plurality of cycles, switches the order of the data in the same port and supplies the data as the data group at a predetermined delay. The control means supplies control information that includes the number of delay cycles used in the variable delay means. | 11-01-2012 |
| 20130046805 | Precision Measurement of Waveforms Using Deconvolution and Windowing - The invention consists of new ways of constructing a Measuring Matrices (MMs) including time deconvolution of Digital Fourier Transforms DFTs. Also, windowing functions specifically designed to facilitate time deconvolution may be used, and/or the DFTs may be performed in specific non-periodic ways to reduce artifacts and further facilitate deconvolution. These deconvolved DFTs may be used alone or correlated with other DFTs to produce a MM. | 02-21-2013 |
| 20130046806 | FAST FOURIER TRANSFORM CIRCUIT - Disclosed is a fast Fourier transform circuit capable of high-speed reading and writing of data processed in the individual stages of a fast Fourier transform calculation without segmenting memory. The circuit is provided with: a calculation unit which performs the fast Fourier calculations with digital Fourier transforms as structural elements; memory for storing the input/output data of the calculation unit; and a means for controlling the writing of calculation results from the calculation unit to the memory such that the order of reading data from the memory is the same at each stage in the multi-stage calculation performed on the data being processed by the calculation unit. | 02-21-2013 |
| 20130254251 | COMMUNICATION APPARATUS AND COMMUNICATION METHOD - A series generator divides a data series having an autocorrelation property equally into a certain number to generate subdata series. A modulator multiplies a predetermined amplitude coefficient and a unique number by each element of the subdata series, respectively, and rearranges the subdata series and synthesizes the rearranged subdata series to generate the modulation data. An IFFT unit performs an IFFT on the modulation data. The calculator divides the calculation result equally into the certain number to generate the sub calculation results, and multiplies an equalization coefficient by each element of the sub calculation results. A synthesizer generates a baseband signal by arranging the sub calculation results, so that an arranged position corresponds to a position at the time of being divided equally, and synthesizing the arranged result. A transmitter generates the transmission signal and transmits it to another apparatus via an antenna. | 09-26-2013 |
| 20130304784 | SIGNAL PROCESSING METHOD AND DEVICE - A data processing method is disclosed, including: twiddling input data, so as to obtain twiddled data; pre-rotating the twiddled data by using a symmetric rotate factor, where the rotate factor is a·W | 11-14-2013 |
| 20140082039 | Interleaved Method for Parallel Implementation of the Fast Fourier Transform - The present invention generally relates to a method for computing a Fast Fourier Transform (FFT). In one embodiment, the present invention relates to an interleaved method for computing a Fast Fourier Transform (FFT). | 03-20-2014 |
| 20140089366 | Techniques for Improving the Efficiency of Mixed Radix Fast Fourier Transform - Techniques for implementing mixed-radix FFT on SIMD vector processors efficiently for the latest standard in wireless communication technology by dynamically reordering stages are provided. In one aspect, a mixed-radix FFT implementation method for vector processors is provided which includes the following steps. Input data is decomposed into segments of factors based on a size of the input data, wherein the decomposing is performed in one or more stages, and wherein at each of the stages the input data is processed in blocks using one or more FFT butterfly computations for each of the blocks. The stages in which the decomposing is performed are reordered to insure complete utilization of the vector processors. The butterfly computations for one or more of the blocks are reordered to insure that the input data have memory addresses which are next to each other and contiguous. | 03-27-2014 |
| 20140089367 | Techniques for Improving the Efficiency of Mixed Radix Fast Fourier Transform - Techniques for implementing mixed-radix FFT on SIMD vector processors efficiently for the latest standard in wireless communication technology by dynamically reordering stages are provided. In one aspect, a mixed-radix FFT implementation method for vector processors is provided which includes the following steps. Input data is decomposed into segments of factors based on a size of the input data, wherein the decomposing is performed in one or more stages, and wherein at each of the stages the input data is processed in blocks using one or more FFT butterfly computations for each of the blocks. The stages in which the decomposing is performed are reordered to insure complete utilization of the vector processors. The butterfly computations for one or more of the blocks are reordered to insure that the input data have memory addresses which are next to each other and contiguous. | 03-27-2014 |
| 20140089368 | Device with capability of processing FFT radix 2 butterfly operation and operation method thereof - The disclosure provides a device with a capability of processing a Fast Fourier Transform Algorithm (FFT) radix 2 butterfly operation and an operation method thereof, the device at least includes a latch, a complex multiplier, a complex adder-subtractor, a switch and a complex conjugate Arithmetic Logical Unit (ALU). The complex operation unit of the disclosure has a simple structure. The parallel processing array composed of the complex operation unit has the capability of efficiently processing vectors and the FFT operation. | 03-27-2014 |
| 20140089369 | MULTI-GRANULARITY PARALLEL FFT COMPUTATION DEVICE - A multi-granularity parallel FFT computation device including three memories, a butterfly computation device, a state control unit, a data reversing network and a first selector. The three memories are each a multi-granularity parallel memory, and store butterfly group data and twiddle factors corresponding to the butterfly group data. The butterfly computation device perform computations of a butterfly group based on the butterfly group data outputted from the first selector and the corresponding twiddle factors outputted from one of the memories, and write a computation result back to the other two memories. The device can read butterfly group data and corresponding twiddle factors in parallel from the multi-granularity parallel memories with a specific R/W granularity. No memory conflict will occur in the read operation, and no additional process is required for sorting the read/written data. | 03-27-2014 |
| 20140181168 | METHOD AND APPARATUS FOR REDUCED MEMORY FOOTPRINT FAST FOURIER TRANSFORMS - Generally, this disclosure describes a method and apparatus for reduced memory footprint fast Fourier transforms (FFTs). An apparatus may include intermediate factor circuitry configured to generate an intermediate factors vector including a number of intermediate factors in response to a request to generate an FFT of an N-point input data set, N composite, wherein N is equal to a product of a number of nonunity integer factors, the number of intermediate factors is related to the nonunity integer factors of N and the number of intermediate factors is less than N. The apparatus may include intermediate result circuitry configured to reconstruct a subset of twiddle factors based at least in part on an element by element product of a first subset of the intermediate factors vector and a complex conjugate of a second subset of the intermediate factors vector, wherein the twiddle factors are complex roots of unity. | 06-26-2014 |
| 20140195578 | FAST FOURIER TRANSFORM CIRCUIT - A multiplexer receives a plurality of data streams transmitted in parallel on a time axis, and outputs partial data of each data stream every unit time in determined data stream order. A butterfly computation section at a first stage receives as second input data the partial data outputted from the multiplexer. A delay section corresponding to the butterfly computation section at the first stage receives in the data stream order the partial data outputted from the multiplexer, delays the partial data, and outputs the partial data as first input data for the butterfly computation section at the first stage. | 07-10-2014 |
| 20140280420 | VECTOR PROCESSING ENGINES HAVING PROGRAMMABLE DATA PATH CONFIGURATIONS FOR PROVIDING MULTI-MODE RADIX-2X BUTTERFLY VECTOR PROCESSING CIRCUITS, AND RELATED VECTOR PROCESSORS, SYSTEMS, AND METHODS - Vector processing engines (VPEs) having programmable data path configurations for providing multi-mode Radix-2 | 09-18-2014 |
| 20140280421 | FFT ACCELERATOR - An FFT operation is performed by dividing n time-domain input points into a plurality of groups of m points, performing a plurality of constant-geometry butterfly operations on each of the groups of m points, and finally performing at least one in-place butterfly operation on the group of n points. | 09-18-2014 |
| 20140280422 | SYSTEM, METHOD, APPARATUS, AND COMPUTER PROGRAM PRODUCT FOR CALCULATING A SAMPLED SIGNAL - A method, apparatus, and computer program product for calculating a sampled signal are disclosed. A method in accordance with the disclosure may include determining discrete samples of a continuous signal having a finite spectrum and using a function series expansion to calculate at least a portion of the continuous signal over the discrete samples. In accordance with some embodiments, an original signal may be calculated over discrete samples with arbitrary accuracy. Polyphase filtering is not used in some embodiments. Some embodiments can be used for arbitrary, including irrational, variation of the sampling rate of the signal with a bounded spectrum. Some embodiments provide for much faster calculation than direct application of the Kotelnikov (Nyquist-Shannon) theorem. In some embodiments, the calculation may be performed according to the disclosed theorem but, instead of discrete signal convolutions with kernels having different phases, a function series expansion may be used. | 09-18-2014 |
| 20140324936 | PROCESSOR FOR SOLVING MATHEMATICAL OPERATIONS - Processors and methods for solving mathematical equations are disclosed herein. An embodiment of the processor includes a hardware device that calculates coefficients based on a mathematical operation that is to be performed. An indexing device transmits the coefficients to and from a look up table. A hardware multiplier multiplies certain coefficients by the derivative of a function related to the mathematical operation. A hardware adder adds a first coefficient to the product of a second coefficient and the first order derivative of the function. | 10-30-2014 |
| 20140330880 | METHODS AND DEVICES FOR MULTI-GRANULARITY PARALLEL FFT BUTTERFLY COMPUTATION - A method and device for multi-granularity parallel FFT butterfly computation. The method and device read data and twiddle factors for computation in one butterfly group from the input buffers and the twiddle factor buffer at a time, perform multi-stage butterfly computation in parallel using uniform butterfly representations, and write the results back to the input buffers. The method and device greatly reduce the frequency for accessing the memory, improve speed for butterfly computation, and reduce power consumption. The method and device achieve multi-granularity butterfly computation of various data formats in a parallel and efficient manner. The method and device can specify the parallel granularity and data format for butterfly computation according to particular applications, and are applicable to FFT butterfly computation of balanced and unbalanced groups. | 11-06-2014 |
| 20140337401 | DATA ACCESS METHOD AND DEVICE FOR PARALLEL FFT COMPUTATION - The present disclosure provides A data access method and device for parallel FFT computation. In the method, FFT data and twiddle factors are stored in multi-granularity parallel memories, and divided into groups throughout the computation flow according to a uniform butterfly representation. Each group of data involves multiple butterflies that support parallel computation. Meanwhile, according to the butterfly representation, it is convenient to generate data address and twiddle factor coefficient address for each group. With different R/W granularities, it is possible to read/write data and corresponding twiddle factors in parallel from the multi-granularity memories. The method and device further provide data access devices for parallel FFT computation. In the method and device, no conflict will occur during read/write operations of memories, and no extract step is required for sorting the read/written data. Further, the method and device can flexibly define the parallel granularity according to particular applications. | 11-13-2014 |
| 20140365547 | MIXED-RADIX PIPELINED FFT PROCESSOR AND FFT PROCESSING METHOD USING THE SAME - Disclosed herein are a mixed-radix pipelined Fast Fourier Transform (FFT) processor and an FFT processing method using the same. The mixed-radix pipelined Fast Fourier Transform (FFT) processor includes a first radix chain, a second radix chain, an input buffer, and an output buffer. The first radix chain includes first radix processors that are connected in series to each other. The second radix chain includes second radix processors that are connected in series to each other, and is connected in series to the first radix chain. The input buffer performs index mapping on a sequence input to the first radix chain. The output buffer generates a final FFT output by performing index mapping on a sequence generated using outputs of one or more of the first and second radix chains. | 12-11-2014 |
| 20150113030 | NOVEL APPROACH FOR SIGNIFICANT IMPROVEMENT OF FFT PERFORMANCE IN MICROCONTROLLERS - A system includes a memory bank and a control unit. The control unit is configured to perform FFT computations based on Merged radix-2 butterfly calculations by performing FFT computations over N input items, and to access the memory bank for (½×log | 04-23-2015 |
| 20150301986 | FAST FOURIER TRANSFORM CIRCUIT, FAST FOURIER TRANSFORM PROCESSING METHOD, AND PROGRAM RECORDING MEDIUM - Provided is a fast Fourier transform circuit including: a first butterfly circuit and a second butterfly circuit which perform butterfly calculations corresponding to calculation bit-widths being different from each other; and a control means which controls selection of the first and second butterfly circuits in accordance with any one of a plurality of operation modes including: a first operation mode in which a calculation is performed by both of the first and second butterfly circuits; and a second operation mode in which a calculation is performed by any one of the first and second butterfly circuits. | 10-22-2015 |
| 20150339264 | PROCESSING DEVICE AND METHOD FOR PERFORMING A STAGE OF A FAST FOURIER TRANSFORM - A data processing device and a method for performing second or next stage of an N point Fast Fourier Transform is suggested. The processing device comprises an input operand memory unit and an input buffer comprising a plurality of addressable memory cells arranged in lines and columns. Furthermore, the device comprises a number of radix-P operation units for producing output operands that are buffered in an output buffer. Input operands are read from the input operand memory unit and buffering into the input buffer. The input operands are stored and fetched from the input buffer according to a reordering scheme that allows efficient parallel processing of the operands by the butterflies and the buffering of subsequent input operands. | 11-26-2015 |
| 20160092399 | FOLDED BUTTERFLY MODULE, PIPELINED FFT PROCESSOR USING THE SAME, AND CONTROL METHOD OF THE SAME - A folded butterfly module performs a radix-2 | 03-31-2016 |
| 20160124904 | PROCESSING DEVICE AND METHOD FOR PERFORMING A ROUND OF A FAST FOURIER TRANSFORM - A data processing device and a method for performing a round of an N point Fast Fourier Transform are described. The round comprises computing N output operands on the basis of N input operands by applying a set of N/P radix-P butterflies to the N input operands, wherein P is greater or equal two and the input operands are representable as N/(M*P)̂ | 05-05-2016 |
| 20160132461 | HIGH PERFORMANCE IMPLEMENTATION OF THE FFT BUTTERFLY COMPUTATION - This invention is a FFT butterfly circuit. This circuit includes four temporary data registers connected to three memories. The three memories include read/write X and Y memories and a read only twiddle coefficient memory. A multiplier-accumulator forms a product and accumulates the product with one of two accumulator registers. A register file with plural registers is loaded from one of the accumulator registers or the fourth temporary data register. An adder/subtracter forms a selected one of a sum of registers or a difference of registers. A write buffer with two buffers temporarily stores data from the adder/subtracter before storage in the first or second memory. The X and Y memories must be read/write but the twiddle memory may be read only. | 05-12-2016 |
