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.

The main goal of this thesis is to design and implement the high performance processor core for completing those digital signal processing algorithms applied at the DVB-T systems. The DSP must support the signal flow in time. Completing the FFT algorithm at 8192 input signal points instantaneously is the most important key. In order to achieve the time demand of FFT and the DSP frequency must be as lower as possible, the way is to increase the degree of instruction level parallelism (ILP). The thesis designs a VLIW architecture processing core called DVB-T DSP to support instruction parallelism with enough execution units. The thesis also uses the software pipelining to schedule the loop to achieve the highest ILP when used to execute FFT butterfly operations. Furthermore, in order to provide the smooth data stream for pipeline, the thesis designs a mechanism to improve the modulo addressing, called extended modulo addressing, will collect the discrete vectors into one continuous vector. This is a big problem that the program size is bigger than other processor architecture at the VLIW processor architecture. In order to solve the problem, this thesis proposes an instruction compression mechanism, which can increase double program density and does not affect the processor execution efficiency. The simulation result shows that DVB-T DSP can achieve the time demand of FFT at 133Mhz. DVB-T DSP also has good performance for other digital signal processing algorithms.

¡@¡@A single chip of variable length FFT processor is presented in this thesis. This processor can be applied for the applications with 128/256/512/1024/2048-point FFT. This processor is based on SDF (single path delay feedback) pipeline architecture with radix-2^3 computation element. The number of bits for input data and twiddle factors is carefully selected by system simulation to meet the requirements of OFDM system. In addition, we propose a feedback twiddle factor generator to instead the lookup table for twiddle factors to reduce the storage size of memory. The FFT processor is carried out by CMOS 0.35£gm 2P4M process with core area 3.381x3.3625 mm^2. In the gate level simulation, the output data rate of this FFT processor is above 22.72MHz, so the processor can meet the requirement of IEEE 802.16e standard.

Aνάπτυξη αποδοτικών αρχιτεκτονικών για την υλοποίηση του (FFT/IFFT) για εφαρμογές ασυρμάτων τοπικών δικτύων. Ανάπτυξη Αρχιτεκτονικών υψηλής παραμετροποιήσης ως πρός διαφορετικούς παράγοντες όπως το μέγεθος του μετασχηματισμού, τα εύρη σε αριθμό δυαδικών ψηφίων των εισόδων, των εξόδων και των συντελεστών. Βελτιστοποίηση άλλων βασικών παραγόντων κόστους υλοποίησης όπως η επιφάνεια και η ισχύς. / Sufficient development for the FFT/iFFT implementation in Wireless Local Networks (wLANs). Specific architectural development was established in order to achieve constraints in different factors such as the size of the transform or the dual input-output digits´ width. Improvement in basic factors was also achieved, in order to gain low cost implementation in sueface and power.

abstract: Multidimensional (MD) discrete Fourier transform (DFT) is a key kernel algorithm in many signal processing applications, such as radar imaging and medical imaging. Traditionally, a two-dimensional (2-D) DFT is computed using Row-Column (RC) decomposition, where one-dimensional (1-D) DFTs are computed along the rows followed by 1-D DFTs along the columns. However, architectures based on RC decomposition are not efficient for large input size data which have to be stored in external memories based Synchronous Dynamic RAM (SDRAM). In this dissertation, first an efficient architecture to implement 2-D DFT for large-sized input data is proposed. This architecture achieves very high throughput by exploiting the inherent parallelism due to a novel 2-D decomposition and by utilizing the row-wise burst access pattern of the SDRAM external memory. In addition, an automatic IP generator is provided for mapping this architecture onto a reconfigurable platform of Xilinx Virtex-5 devices. For a 2048x2048 input size, the proposed architecture is 1.96 times faster than RC decomposition based implementation under the same memory constraints, and also outperforms other existing implementations. While the proposed 2-D DFT IP can achieve high performance, its output is bit-reversed. For systems where the output is required to be in natural order, use of this DFT IP would result in timing overhead. To solve this problem, a new bandwidth-efficient MD DFT IP that is transpose-free and produces outputs in natural order is proposed. It is based on a novel decomposition algorithm that takes into account the output order, FPGA resources, and the characteristics of off-chip memory access. An IP generator is designed and integrated into an in-house FPGA development platform, AlgoFLEX, for easy verification and fast integration. The corresponding 2-D and 3-D DFT architectures are ported onto the BEE3 board and their performance measured and analyzed. The results shows that the architecture can maintain the maximum memory bandwidth throughout the whole procedure while avoiding matrix transpose operations used in most other MD DFT implementations. The proposed architecture has also been ported onto the Xilinx ML605 board. When clocked at 100 MHz, 2048x2048 images with complex single-precision can be processed in less than 27 ms. Finally, transpose-free imaging flows for range-Doppler algorithm (RDA) and chirp-scaling algorithm (CSA) in SAR imaging are proposed. The corresponding implementations take advantage of the memory access patterns designed for the MD DFT IP and have superior timing performance. The RDA and CSA flows are mapped onto a unified architecture which is implemented on an FPGA platform. When clocked at 100MHz, the RDA and CSA computations with data size 4096x4096 can be completed in 323ms and 162ms, respectively. This implementation outperforms existing SAR image accelerators based on FPGA and GPU. / Dissertation/Thesis / Ph.D. Electrical Engineering 2012

Submitted by Eduarda Figueiredo (eduarda.ffigueiredo@ufpe.br) on 2015-03-06T15:05:20Z No. of bitstreams: 2 teseTCAgilson2012digital.pdf: 1787853 bytes, checksum: 4942f4072dad835d860eb3e2ccfdcecf (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-06T15:05:20Z (GMT). No. of bitstreams: 2 teseTCAgilson2012digital.pdf: 1787853 bytes, checksum: 4942f4072dad835d860eb3e2ccfdcecf (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2012-04-27 / Encontrar a forma mais e ciente de resolver um problema aritmético e desenvolver algoritmos cada vez melhores é uma grande preocupação dos cientistas, matemáticos e engenheiros projetistas. Economizar operações aritméticas signi ca diminuir o tamanho do hardware, reduzir o consumo de energia e baixar custos de produção. Um algoritmo otimizado minimiza essas três variáveis destacadas. Nesta tese é introduzida a teoria para se obter algoritmos otimizados para qualquer transformada linear. Uma aplicação direta dessa teoria resulta na construção da transformada rápida de Fourier otimizada, a qual atinge o número mínimo possível de multiplicações, sendo mais e ciente do que qualquer algoritmo conhecido na literatura, para computar a transformada discreta de Fourier.

O presente trabalho descreve a implementação do algoritmo discreto da FFT-2D, numa rede de transputers. Primeiramente a implementação seqüencial do algoritmo é analisado, em seguida são apresentados algumas técnicas de paralelização, bem como sua aplicação no algoritmo da FFT-2D. Finalmente são apresentados os resultados do desempenho obtido por redes compostas de um, dois e quatro transputers / The present work describes the implementation of the discrete FFT-2D algorithm in a distributed transputer network. First a seqüencial implementation of the algorithm is presented. Then some parallelization techniques are analyzed and applied to the FFT-2D algorithm. Finally the obtained performance is presented for networks containing one, two and four transputers

Baseando-se em um sistema com um grau de liberdade, é apresentada neste trabalho a equação de movimento, bem como a sua resolução através das Transformadas de Fourier e da Transformada Rápida de Fourier (FFT). Através da análise da forma como são feitas as integrações nas transformadas, foram estudados e aplicados os ponderadores de Newton-Cotes na resolução da equação de movimento, de forma a aumentar substancialmente a precisão dos resultados em comparação com a forma convencional da Transformada de Fourier. / Based on a single degree of freedom model, this work shows the equation of motion, as well as its solution with the Fourier Transform and the Fast Fourier Transform (FFT). Through the analysis of the methods used in the Fourier Integral, the Newton-Cotes quadratures formulas were studied and applied for the solving of the equation of motion, in order to substantially increase the precision of the results in comparison to the usual Fourier Transform.

The FFT is an efficient algorithm for computing the DFT. It drastically reduces the cost of implementing the DFT on digital computing systems. Nevertheless, the FFT is still computationally intensive, and continued technological advances of computers demand larger and faster implementations of this algorithm. Past attempts at producing high-performance, and small FFT implementations, have focused on custom hardware (ASICs and FPGAs). Ultimately, the most efficient have been single-chipped, streaming I/O, pipelined FFT architectures. These architectures increase computational concurrency through the use of hardware pipelining. Streaming I/O, pipelined FFT architectures are capable of accepting a single data sample every clock cycle. In principle, the maximum clock frequency of such a circuit is limited only by its critical delay path. The delay of the critical path may be decreased by the addition of pipeline registers. Nevertheless this solution gives diminishing returns. Thus, the streaming I/O, pipelined FFT is ultimately limited in the maximum performance it can provide. Attempts have been made to map the Parallel FFT algorithm to custom hardware. Yet, the Parallel FFT was formulated and optimized to execute on a machine with multiple, identical, processing elements. When executed on such a machine, the FFT requires a large expense on communications. Therefore, a direct mapping of the Parallel FFT to custom hardware results in a circuit with complex control and global data movement. This thesis proposes the Hybrid Architecture Parallel FFT (HAPFFT) as an alternative. The HAPFFT is an improved formulation for building Parallel FFT custom hardware modules. It provides improved performance, efficient resource utilization, and reduced design time. The HAPFFT is modular in nature. It includes a custom front-end parallel processing unit which produces intermediate results. The intermediate results are sent to multiple, independent FFT modules. These independent modules form the back-end of the HAPFFT, and are generic, meaning that any prexisting FFT architecture may be used. With P back-end modules a speedup of P will be achieved, in comparison to an FFT module composed solely of a single module. Furthermore, the HAPFFT defines the front-end processing unit as a function of P. It hides the high communication costs typically seen in Parallel FFTs. Reductions in control complexity, memory demands, and logical resources, are achieved. An extraordinary result of the HAPFFT formulation is a sublinear area-time growth. This phenomenon is often also called superlinear speedup. Sublinear area-time growth and superlinear speedup are equivalent terms. This thesis will subsequently use the term superlinear speedup to refer to the HAPFFT's outstanding speedup behavior. A further benefit resulting from the HAPFFT formulation is reduced design time. Because the HAPFFT defines only the front-end module, and because the back-end parallel modules may be composed of any preexisting FFT modules, total design time for a HAPFFT is greatly reduced

O presente trabalho descreve a implementação do algoritmo discreto da FFT-2D, numa rede de transputers. Primeiramente a implementação seqüencial do algoritmo é analisado, em seguida são apresentados algumas técnicas de paralelização, bem como sua aplicação no algoritmo da FFT-2D. Finalmente são apresentados os resultados do desempenho obtido por redes compostas de um, dois e quatro transputers / The present work describes the implementation of the discrete FFT-2D algorithm in a distributed transputer network. First a seqüencial implementation of the algorithm is presented. Then some parallelization techniques are analyzed and applied to the FFT-2D algorithm. Finally the obtained performance is presented for networks containing one, two and four transputers