In this thesis, a new design methodology for pipeline FFT processor has been proposed. The pipeline FFT processor can achieve high throughput rate, and is very suitable for those systems where the continuous data sequences that call for the FFT processing enter systems sample by sample sequentially. However, the traditional pipeline FFT design based on the common single delay feed-back approach suffers low hardware utilization for the butterfly unit. In addition, the resulted transformed sequence is in the form of bit-reverse order which is not suitable for some FFT applications such as OFDM (Orthogonal Frequency Division Multiplexing). Therefore, this thesis proposes a novel pipelined FFT design by first splitting the input sequence into two data streams, which can then be applied to the FFT data-path based on the feed-forward dual-delay path data commutator. The resulted FFT architecture can achieve full butterfly utilization such that the required number of adders can be reduced by almost a half. One potential drawback of the proposed approach is that some additional large storage buffer is required at the last stage. However, the additional storage buffer can be re-organized and merged with the output reordering buffer together such that the normal-order transformed output sequence can be generated. The proposed approach has been applied to the design of 8-K point FFT in this thesis. The 8-K FFT architecture proposed in this thesis is designed based on the radix- 2^4 algorithm such that the required number of general complex number multipliers can be minimized to three. The multiplication of is realized by the dedicated constant multiplier architecture. By proper data partition and allocation, the large buffer required for many data commutator and the output reordering buffer can both be efficiently realized by multi-bank single-port memory modules. The other salient features of the 8-K FFT also include the table reduction for twiddle factors as well as the optimized variable internal data representation. The proposed FFT processor has been implemented by the TSMC 0.18um 1P6M CMOS process technology with core area of 8.74 which is the smallest design reported in the literature for normal sequential input/output order FFT.

No description available.

ITC/USA 2005 Conference Proceedings / The Forty-First Annual International Telemetering Conference and Technical Exhibition / October 24-27, 2005 / Riviera Hotel & Convention Center, Las Vegas, Nevada / In GPS receiver the acquisition process generates two important parameters: the initial carrier frequency and the initial phase of the C/A code. In this paper two different methods for acquisition are mainly discussed: serial search in the time domain and FFT search in the frequency domain. Frequency domain acquisition involves using the Fast Fourier Transform (FFT) to convert the GPS signals into the frequency domain. One fast and easy-to-implement algorithm for averaging correlation is implemented and explained in detail. The FFT search method is both simulated in Matlab and evaluated in Altera Stratix DSP development board.

No description available.

<p>GPGPU is a collective term for research involving general computation on graphics cards. A modern graphics card typically provides more than ten times the computational power of an ordinary PC processor. This is a result of the high demands for speed and image quality in computer games.</p><p>This thesis investigates the possibility of exploiting this computational power for image processing purposes. Three well known methods where implemented on a graphics card: FFT (Fast Fourier Transform), KLT (Kanade Lucas Tomasi point tracking) and the generation of scale pyramids. All algorithms where successfully implemented and they are tree to ten times faster than correspondning optimized CPU implementation.</p>

Biomolecular structure and interactions in aqueous environment are determined by a complicated interplay between physical and chemical forces including solvation, electrostatics, van der Waals forces, the hydrophobic effect and covalent bonding. Among them, electrostatics has been of particular interest due to its long-range nature and the tradeoff between desolvation and interaction effects [1]. In addition, electrostatic interactions play a significant role within a biomolecule as well as between biomolecules, making the balance between the two vital to the understanding of macromolecular systems. As a result, much effort has been devoted to accurate modeling and simulation of biomolecule electrostatics. One important application of this work is to compute the structure of electrostatic interactions for a biomolecule in an electrolyte solution, as well as the potential that the molecule generates in space. There are two valuable uses for these simulations. First, it provides a full picture of the electrostatic energetics of a biomolecular system, improving our understanding of how electrostatics contributes to stability, specificity, function, and molecular interaction [2]. Second, these simulations serve as a tool for molecular design, since electrostatic complementarity is an important feature of interacting molecules. Through examination of the electrostatics and potential field generated by a protein molecule, for example, it may be possible to suggest improvements to other proteins or drug molecules that interact with it, or perhaps even design new interacting molecules de novo [3]. There are two approaches in simulating a protein macromolecule in an aqueous solution with nonzero ionic strength. Discrete/atomistic approaches based on Monte-Carlo or molecular dynamics simulations treat the macromolecule and solvent explicitly at the atomic level. Therefore, an enormous number of solvent molecules are required to provide reasonable accuracy, especially when electric fields far away from macroscopic surface are of interest, leading to computational infeasibility. In this work, we adopt instead an approach based on a continuum description of the macromolecule and solvent. Although the continuum model of biomolecule electrostatics is widely used, the numerical techniques used to evaluate the model do not exploit fast solver approaches developed for analyzing integrated circuit interconnect. I will describe the formulation used for analyzing biomolecule electrostatics, and then derive an integral formulation of the problem that can be rapidly solved with precorrected-FFT method [4]. / Singapore-MIT Alliance (SMA)

This thesis describes the work related to an interferer rejection system employing frequency analysis and cancellation through phase-opposed signal injection. The first device in the frequency analysis chain, an analog fast Fourier transform application-specific integrated circuit (ASIC), was improved upon. The second device, a chained fast Fourier transform followed by a frequency analysis module employing cross-correlation for signal detection was specified, designed and implemented in VHDL.

The discovery of Carbon Nanotubes and their ability to produce X-rays can usher in a new era in Computed Tomography (CT) technology. These devices will be lightweight, flexible and portable. The proposed device, currently under development, is envisioned as a flexible band of tiny X-ray emitters and detectors. The device is wrapped around an appendage and a CT image is obtained. However, current CT reconstruction algorithms can only be used if the geometry of the CT device is regular (usually circular). We present an efficient and accurate reconstruction technique that is unconstrained by the geometry of the CT device. Indeed the geometry can be both regular and highly irregular. To evaluate the feasibility of reconstructing a CT image from such a device, a simulated test bed was built to generate simulated CT ray sums of an image. This data was then used in our reconstruction method. We take this output data and grid it according to what we would expect from a parallel-beam CT scanner. The Filtered Back Projection can then be used to perform reconstruction. We have also included data inaccuracies as is expected in "real world" situations. Observations of reconstructions, as well as quantitative results, suggest that this simple method is efficient and accurate.

FFT-based digital spectral analyzer has become more and more widely used as a result of the development of Digital Signal Processing (DSP) techniques. Modern Analog-to-Digital Converters (ADC) and processors have made it possible to make fast measurements with a limited number of hardware.   In this thesis, a design of a simple low-cost FFT-based digital spectrum analyzer was presented. The author discusses the design of each components of the system in qualitatively and quantitatively. The report presents the whole system design in detail which contains filter design, micro-controller design, UART transmission design and MATLAB GUI design. Some satisfying measurement result of the system were presented in the paper. The system can provide fast measurement with good accuracy. But the measured result has a limited range and resolution of the display is not very high. At last, the advantages and disadvantages of the system was discussed which is considered as guidelines for further work.

This paper presents a reconfigurable FFT architecture for variable length andmultistreaming WiMax wireless standard. The architecture processes 1 streamof 2048-pt FFT, up to 2 streams of 1024-pt FFT or up to 4 streams of 512-ptFFT. The architecture consists of 11 SDF pipelined stages and radix-2 butterflyis calculated in each stage. The sampling frequency of the system is varied inaccordance with FFT length. The wordlength and buffer length in each stage isconfigurable depending on the FFT length. Latch-free clock gating technique isused to reduce power consumption.The architecture is synthesized for Virtex-6 XCVLX760 FPGA. Experimentalresults show that the architecture achieves the throughput as required by theWiMax standard and the design has additional features compared to the previousapproaches. The design used 1% of the total available FPGA resources andmaximum clock frequency of 313.67 MHz was achieved.