Fundamentals of the DFT (fft) Algorithms
In this article, a physical explanation of the fundamentals of the DFT (fft) algorithms is presented in terms of waveform decomposition. After reading the article and trying the examples, the reader is expected to gain a clear understanding of the basics of the mysterious DFT (fft) algorithms.
Optimization of Synthesis Oversampled Complex Filter Banks
An important issue with oversampled FIR analysis filter banks (FBs) is to determine inverse synthesis FBs, when they exist. Given any complex oversampled FIR analysis FB, we first provide an algorithm to determine whether there exists an inverse FIR synthesis system. We also provide a method to ensure the Hermitian symmetry property on the synthesis side, which is serviceable to processing real-valued signals. As an invertible analysis scheme corresponds to a redundant decomposition, there is no unique inverse FB. Given a particular solution, we parameterize the whole family of inverses through a null space projection. The resulting reduced parameter set simplifies design procedures, since the perfect reconstruction constrained optimization problem is recast as an unconstrained optimization problem. The design of optimized synthesis FBs based on time or frequency localization criteria is then investigated, using a simple yet efficient gradient algorithm.
Hybrid Floating Point Technique Yields 1.2 Gigasample Per Second 32 to 2048 point Floating Point FFT in a single FPGA
Hardware Digital Signal Processing, especially hardware targeted to FPGAs, has traditionally been done using fixed point arithmetic, mainly due to the high cost associated with implementing floating point arithmetic. That cost comes in the form of increased circuit complexity. The increase circuit complexity usually also degrades maximum clock performance. Certain applications demand the dynamic range offered by floating point hardware, and yet require the speeds and circuit density usually associated with fixed point hardware. The Fourier transform is one DSP building block that frequently requires floating point dynamic range. Textbook construction of a pipelined floating point FFT engine capable of continuous input entails dozens of floating point adders and multipliers. The complexity of those circuits quickly exceeds the resources available on a single FPGA. This paper describes a technique that is a hybrid of fixed point and floating point operations designed to significantly reduce the overhead for floating point. The results are illustrated with an FFT processor that performs 32, 64, 128, 256, 512, 1024 and 2048 point Fourier transforms with IEEE single precision floating point inputs and outputs. The design achieves sufficient density to realize a continuous complex data rate of 1.2 Gigasamples per second data throughput using a single Virtex4-SX55-10 device.
Audio Time-Scale Modification
Audio time-scale modification is an audio effect that alters the duration of an audio signal without affecting its perceived local pitch and timbral characteristics. There are two broad categories of time-scale modification algorithms, time-domain and frequency-domain. The computationally efficient time-domain techniques produce high quality results for single pitched signals such as speech, but do not cope well with more complex signals such as polyphonic music. The less efficient frequencydomain techniques have proven to be more robust and produce high quality results for a variety of signals; however they introduce a reverberant artefact into the output. This dissertation focuses on incorporating aspects of time-domain techniques into frequency-domain techniques in an attempt to reduce the presence of the reverberant artefact and improve upon computational demands. From a review of prior work it was found that there are a number of time-domain algorithms available and that the choice of algorithm parameters varies considerably in the literature. This finding prompted an investigation into the effects of the choice of parameters and a comparison of the various techniques employed in terms of computational requirements and output quality. The investigation resulted in the derivation of an efficient and flexible parameter set for use within time-domain implementations. Of the available frequency-domain approaches the phase vocoder and timedomain/ subband techniques offer an efficiency and robustness advantage over sinusoidal modelling and iterative phase update techniques, and as such were identified as suitable candidates for the provision of a framework for further investigation. Following from this observation, improvements in the quality produced by time-domain/subband techniques are realised through the use of a bark based subband partitioning approach and effective subband synchronisation techniques. In addition, computational and output quality improvements within a phase vocoder implementation are achieved by taking advantage of a certain level of flexibility in the choice of phase within such an implementation. The phase flexibility established is used to push or pull phase values into a phase coherent state. Further improvements are realised by incorporating features of time-domain algorithms into the system in order to provide a ‘good’ initial set of phase estimates; the transition to ‘perfect’ phase coherence is significantly reduced through this scheme, thereby improving the overall output quality produced. The result is a robust and efficient time-scale modification algorithm which draws upon various aspects of a number of general approaches to time-scale modification.
Signal Processing Requirements for WiMAX (802.16e) Base Station
802.16e provides specifications for non line of sight, mobile wireless communications in the frequency range of 2-6 GHz. It is well implemented by using OFDMA as its physical layer scheme. The OFDM symbol time (sT) is to be selected depending on the channel conditions, available bandwidth and, simulations provide a means of selecting right values of sTin different channel conditions. Additionally it has been shown that certain values of sT outperform others in all conditions, thus invalidating their use. Moreover, a solution proposed by INTEL is also analyzed. One of the major requirements of OFDM is high synchronization. Detecting the timing offset of a new mobile user, entering the network, which is not time aligned using cross-correlation and ‘auto-correlation’ in time domain and cross-correlation in frequency domain at the base station has been simulated. Results point that the processing load can be significantly reduced by using frequency domain correlation of the received data or by using ‘auto-correlation’ followed by cross-correlation on localized data. The use of adaptive antenna system in 802.16e improves the system performance, where beamforming is implemented in the direction of desired user. Capon’s method and MUSIC method have been simulated to compute the direction of arrival for OFDMA uplink. A new user, while in the ranging process, transmits data with unknown time offset and unknown direction. The thesis describes the procedure to find the two unknown one after another.
Acoustic Echo Cancellation using Digital Signal Processing
Acoustic echo cancellation is a common occurrence in todays telecommunication systems. It occurs when an audio source and sink operate in full duplex mode, an example of this is a hands-free loudspeaker telephone. In this situation the received signal is output through the telephone loudspeaker (audio source), this audio signal is then reverberated through the physical environment and picked up by the systems microphone (audio sink). The effect is the return to the distant user of time delayed and attenuated images of their original speech signal. The signal interference caused by acoustic echo is distracting to both users and causes a reduction in the quality of the communication. This thesis focuses on the use of adaptive filtering techniques to reduce this unwanted echo, thus increasing communication quality. Adaptive filters are a class of filters that iteratively alter their parameters in order to minimise a function of the difference between a desired target output and their output. In the case of acoustic echo in telecommunications, the optimal output is an echoed signal that accurately emulates the unwanted echo signal. This is then used to negate the echo in the return signal. The better the adaptive filter emulates this echo, the more successful the cancellation will be. This thesis examines various techniques and algorithms of adaptive filtering, employing discrete signal processing in MATLAB. Also a real-time implementation of an adaptive echo cancellation system has been developed using the Texas Instruments TMS320C6711 DSP development kit.
A Prototype Laboratory Environment for Digital Signal Processing Using Simulink and a Texas Instrument DSP Device
Normally, when a model is designed from building blocks in Simulink, the simulation is performed within the Simulink environment. A test of the design in a real-time environment requires that source code is generated, compiled and downloaded to the target hardware. As a first attempt to bridge this software gap, this thesis describes and evaluates a prototype laboratory environment, which directly links Simulink to a Texas Instrument DSP device. The prototype system converts graphical models and makes available various real-time signal processing algorithms, such as adders, delays, FFTs, IIR filters and multipliers. Future work is to consider modification of the prototype to allow for feedback in the graphical models and to find an efficient way of handling signal processing algorithms where variable buffer lengths are required.
Efficient Digital Fiilters
What would you do in the following situation? Let ’ s say you are diagnosing a DSP system problem in the field. You have your trusty laptop with your development system and an emulator. You figure out that there was a problem with the system specifications and a symmetric FIR filter in the software won ’ t do the job; it needs reduced passband ripple, or maybe more stopband attenuation. You then realize you don ’ t have any filter design software on the laptop, and the customer is getting angry. The answer is easy: You can take the existing filter and sharpen it. Simply stated, filter sharpening is a technique for creating a new filter from an old one [1] – [3] . While the technique is almost 30 years old, it is not generally known by DSP engineers nor is it mentioned in most DSP textbooks.
Interaction with Sound and Pre-Recorded Music: Novel Interfaces and Use Patterns
Computers are changing the way sound and recorded music are listened to and used. The use of computers to playback music makes it possible to change and adapt music to different usage situations in ways that were not possible with analog sound equipment. In this thesis, interaction with pre-recorded music is investigated using prototypes and user studies. First, different interfaces for browsing music on consumer or mobile devices were compared. It was found that the choice of input controller, mapping and auditory feedback influences how the music was searched and how the interfaces were perceived. Search performance was not affected by the tested interfaces. Based on this study, several ideas for the future design of music browsing interfaces were proposed. Indications that search time depends linearly on distance to target were observed and examined in a related study where a movement time model for searching in a text document using scrolling was developed. Second, work practices of professional disc jockeys (DJs) were studied and a new design for digital DJing was proposed and tested. Strong indications were found that the use of beat information could reduce the DJ’s cognitive workload while maintaining flexibility during the musical performance. A system for automatic beat extraction was designed based on an evaluation of a number of perceptually important parameters extracted from audio signals. Finally, auditory feedback in pen-gesture interfaces was investigated through a series of informal and formal experiments. The experiments point to several general rules of auditory feedback in pen-gesture interfaces: a few simple functions are easy to achieve, gaining further performance and learning advantage is difficult, the gesture set and its computerized recognizer can be designed to minimize visual dependence, and positive emotional or aesthetic response can be achieved using musical auditory feedback.
Interaction with Sound and Pre-Recorded Music: Novel Interfaces and Use Patterns
Computers are changing the way sound and recorded music are listened to and used. The use of computers to playback music makes it possible to change and adapt music to different usage situations in ways that were not possible with analog sound equipment. In this thesis, interaction with pre-recorded music is investigated using prototypes and user studies. First, different interfaces for browsing music on consumer or mobile devices were compared. It was found that the choice of input controller, mapping and auditory feedback influences how the music was searched and how the interfaces were perceived. Search performance was not affected by the tested interfaces. Based on this study, several ideas for the future design of music browsing interfaces were proposed. Indications that search time depends linearly on distance to target were observed and examined in a related study where a movement time model for searching in a text document using scrolling was developed. Second, work practices of professional disc jockeys (DJs) were studied and a new design for digital DJing was proposed and tested. Strong indications were found that the use of beat information could reduce the DJ’s cognitive workload while maintaining flexibility during the musical performance. A system for automatic beat extraction was designed based on an evaluation of a number of perceptually important parameters extracted from audio signals. Finally, auditory feedback in pen-gesture interfaces was investigated through a series of informal and formal experiments. The experiments point to several general rules of auditory feedback in pen-gesture interfaces: a few simple functions are easy to achieve, gaining further performance and learning advantage is difficult, the gesture set and its computerized recognizer can be designed to minimize visual dependence, and positive emotional or aesthetic response can be achieved using musical auditory feedback.
An application of neural networks to adaptive playout delay in VoIP
The statistical nature of data traffic and the dynamic routing techniques employed in IP networks results in a varying network delay (jitter) experienced by the individual IP packets which form a VoIP flow. As a result voice packets generated at successive and periodic intervals at a source will typically be buffered at the receiver prior to playback in order to smooth out the jitter. However, the additional delay introduced by the playout buffer degrades the quality of service. Thus, the ability to forecast the jitter is an integral part of selecting an appropriate buffer size. This paper compares several neural network based models for adaptive playout buffer selection and in particular a novel combined wavelet transform/neural network approach is proposed. The effectiveness of these algorithms is evaluated using recorded VoIP traces by comparing the buffering delay and the packet loss ratios for each technique. In addition, an output speech signal is reconstructed based on the packet loss information for each algorithm and the perceptual quality of the speech is then estimated using the PESQ MOS algorithm. Simulation results indicate that proposed Haar-Wavelets-Packet MLP and Statistical-Model MLP adaptive scheduling schemes offer superior performance.
IMPLEMENTATION OF PERIODOGRAM SMOOTHING OF NOISYIMPLEMENTATION OF PERIODOGRAM SMOOTHING OF NOISY SIGNALS USING TMS320C6713 DSK
Periodogram Smoothing is a technique of power spectrum estimation. The discrete Fourier transform of a digital signal simply resolves the frequency components. The algorithm is implemented on Texas Instruments’ TMS320C6713 DSP Starter Kit (DSK). This is a 32-bit floating-point digital signal processor running at 225 MHz. The programs are basically written in the C programming language. However, those sections of code which are time-critical and memory-critical are written in assembly language of C6713. A MATLAB™ graphical user interface is also provided. The MATLAB™ program calls C programs loaded in Code Composer Studio (CCS). The C programs in turn call the assembly programs when required.
Design and implementation of odd-order wave digital lattice lowpass filters, from specifications to Motorol DSP56307EVM module
This thesis is dedicated to applying and developing explicit formulas for the design and implementation of odd-order lattice Lowpass wave digital filters (WDFs) on a Digital Signal Processor (DSP), such as a Motorola DSP56307EVM (Evaluation Module). The direct design method of Gazsi for filter types such as Butterworfh, Chebyshev, inverse Chebyshev, and Cauer (Elliptic) provides a straightforward method for calculating the coefficients without an extensive knowledge of digital signal processing. A program package to design and implement odd-order WDFs, including detailed procedures and examples, is presented in this thesis and includes not only the calculations of the coefficients, but also the simulation on a MATLAB platform and an implementation on a Motorola DSP56307EVM board. It is very quick, effective and convenient to obtain the coefficients when the user enters a few parameters according to the general specifications; to verify the characteristics of the designed filter; to simulate the filter on the MATLAB platform; to implement the filter on the DSP board; and to compare the results between the simulation and the implementation.
Implementing IS-95, the CDMA Standard, on TMS320C6201 DSP
IS-95 is the present U.S. 2nd generation CDMA standard. Currently, the 2nd generation CDMA phones are produced by Qualcomm. Texas Instruments (TI) has ASIC design for Viterbi Decoder on C54x. Several of the components in the forward link process are also implemented in hardware. However, having to design a specific hardware for a particular application is expensive and time consuming. Thus, the possibility of the alternative implementations is of great interest to both customers and TI itself. This research has achieved in successful implementation of IS-95 entirely in software on TI fixed-point DSP TMS320C6201, and met the real time constraint. IS-95 system, the industrial standard for CDMA, is a very complicated system and extremely computationally demanding. The transmission rate for an IS-95 system is 1.2288 Mcps. This research project includes all the major components of the demodulation process for the forward link system: PN Descrambling, Walsh Despreading, Phase Correction & Maximal Ratio Combining, Deinterleaver, Digital Automatic Gain Control, and Viterbi Deccc:r. The entire demodulation process is done completely in C. That makes it a very attractive alternative implementation in the future applications. It is well known that ASIC design is not only expensive and but also time consuming, programming in assembly is easier and cheaper, but programming in C is a much easier and efficient way out, in particular, for general computer engineers. During the whole process, efforts have been devoted on developing various specific techniques to optimize the design for all the components involved. These developments are successfully achieved by making the best use of the following techniques: to simplify the algorithms first before programming, to look for regularity in the problem, to work toward the Compiler's full efficiency, and to use C intrinsics whenever possible. All these attributes together make the implementation scheme great for DSP applications. The benchmark results compare very well to the TI-internal hand scheduled assembly performance of the same type of decoders. The estimated percentage usage of all the components (excluding PN) is only 21.18% of the total CPU cycles available (4,000 K), which is very efficient and impressive.
An Advanced Signal Processing Toolkit for Java applications
The aim of this study is to examine the capability, performance, and relevance of a signal processing toolkit in Java, a programming language for Web-based applications. Due to the simplicity, ease and application use of the toolkit and with the advanced Internet technologies such as Remote Method Invocation (RMI), a spectral estimation applet has been created in the Java environment. This toolkit also provides an interactive and visual approach in understanding the various theoretical concepts of spectral estimation and shows the need to create more application applets to better understand the various concepts of signal and image processing. This study also focuses on creating a Java toolkit for embedded systems, such as Personal Digital Assistants (PDAs), embedded Java board, and supporting integer precision, and utilizing COordinate Rotation DIgital Computer (CORDIC) algorithm, both aimed to provide good performance in resource-limited environments. The results show a feasibility and necessity of developing a standardized Application Programming Interface (API) for the fixed-point signal processing library.
A Two-Level Reconfigurable Cell Array for Digital Signal Processing
Reconfigurable hardware has become an attractive option for implementing digital signal processing, especially in systems that require both high performance and flexibility. This thesis presents a novel two-level reconfigurable architecture targeted toward systems with these requirements. The architecture supports a large orthogonal design space whereby designers can customize the word length, amount of parallelism, number of functional units, and functional unit connectivity to meet the needs of the application. On the upper level, algorithms are mapped onto an array of 4-bit cells and a hierarchical interconnection fabric. The interconnection structure contains a mesh of 4-bit busses for local data transfer, as well as an H-tree for communicating results between functional units. On the lower level, each cell contains a small matrix of elements that collectively implement all necessary operations. The matrix of elements has only two configurations: one optimized for mathematical functions such as multiply-accumulates, and the other optimized for memory operations. The system also contains pipeline latches to maximize clock rate and throughput. Circuit simulations indicate that the architecture achieves a clock frequency of 200 MHz in a modest 0.25-μm CMOS technology. An initial prototype of the reconfigurable cell has been fabricated in 0.5-μm CMOS and tested for functionality. The estimated execution time for a 16-bit, 256-point Fast Fourier Transform shows a speedup ranging from 1.6 to 14 compared to contemporary digital signal processors.
Blind Adaptive Dereverberation of Speech Signals Using a Microphone Array
In this thesis, we present a blind adaptive speech dereverberation method based on the use of a reduced mutually referenced equalizers (RMRE) criterion. The method is based on the idea of the inversion of single-input multiple-output FIR linear systems, and as such requires the use of multiple microphones. However, unlike many traditional microphone array methods, there is no need for a specific array configuration or geometry. The RMRE method finds a subset of equalizers for a given delay in a single step, without the need for the typical channel estimation step. This makes the method practical in terms of implementation and avoids the pitfalls of the more complicated two step dereverberation approach, typical in many inversion methods. Additionally, only the second-order statistics of the signals recorded by the microphones are used, without the need for utilizing higher-order statistics information typically needed when the channsls have a nonminimum phase response, as is the case with room impulse responses. We present simulations and experimental results that demonstrate the applicability of the method when the input is speech, and show that in the noiseless case, perfect dereverberation can be achieved. We also evaluate its performance in the presence of noise, and we present a possible way to modify the proposed RMRE to work for very low SNR values. We also explore the problems when model-order mismatches are present, and demonstrate that the under-modeling of the channel impulse responses order can be combated by increasing the number of microphones. For order over-estimation, we will show that RMRE can handle such errors with no modification.
Ignal Enhancement Using Time-Frequency Based Denoising
This thesis investigates and compares time and wavelet-domain denoising techniques where received signals contain broadband noise. We consider how time and wavelet-domain denoising schemes and their combinations compare in the mean squared error sense. This work applies Wiener prediction and Median filtering as they do not require any prior signal knowledge. In the wavelet-domain we use soft or hard thresholding on the detail coefficients. In addition, we explore the effect of these wavelet-domain thresholding techniques on the coefficients associated with cycle-spinning and the newly proposed recursive cycle-spinning scheme. Finally, we note that thresholding does not make an attempt to de-noise coefficients that remain after thresholding; therefore we apply time domain techniques to the remaining detail coefficients from the first level of decomposition in an attempt to de-noise them further prior to reconstruction. This thesis applies and compares these techniques using a mean squared error criterion to identify the best performing in a robust test signal environment. We find that soft thresholding with Stein’s Unbiased Risk Estimate (SURE) thresholding produces the best mean squared error results in each test case and that the addition of Wiener prediction to the first level of decomposition coefficients leads to a slightly enhanced performance. Finally, we illustrate the effects of denoising algorithms on longer data segments.
Noise covariance properties in Dual-Tree Wavelet Decompositions
Dual-tree wavelet decompositions have recently gained much popularity, mainly due to their ability to provide an accurate directional analysis of images combined with a reduced redundancy. When the decomposition of a random process is performed – which occurs in particular when an additive noise is corrupting the signal to be analyzed – it is useful to characterize the statistical properties of the dual-tree wavelet coefficients of this process. As dual-tree decompositions constitute overcomplete frame expansions, correlation structures are introduced among the coefficients, even when a white noise is analyzed. In this paper, we show that it is possible to provide an accurate description of the covariance properties of the dual-tree coefficients of a wide-sense stationary process. The expressions of the (cross-) covariance sequences of the coefficients are derived in the one and two-dimensional cases. Asymptotic results are also provided, allowing to predict the behaviour of the second-order moments for large lag values or at coarse resolution. In addition, the crosscorrelations between the primal and dual wavelets, which play a primary role in our theoretical analysis, are calculated for a number of classical wavelet families. Simulation results are finally provided to validate these results.
