The intense requirements for high processing rates of multidimensional Digital Signal Processing systems in practical applications justify the Application Specific Integrated Circuits designs and parallel processing implementations. In this dissertation, we propose novel theories, methodologies and architectures in designing high-performance VLSI implementations for general multidimensional multirate Digital Signal Processing systems by exploiting the parallelism within those applications. To systematically exploit the parallelism within the multidimensional multirate DSP algorithms, we develop novel transformations including (1) nonlinear I/O data space transforms, (2) intercalation transforms, and (3) multidimensional multirate unfolding transforms. These transformations are applied to the algorithms leading to systematic methodologies in high-performance architectural designs. With the novel design methodologies, we develop several architectures with parallel and distributed processing features for implementing multidimensional multirate applications. Experimental results have shown that those architectures are much more efficient in terms of execution time and/or hardware cost compared with existing hardware implementations.

This report describes the design and implementation of a fixed audio equalizer based on a scheme where parts of the signal spectrum are downsampled and treated differently for the purpose of reducing the computational complexity and memory requirements. The primary focus has been on finding a way of taking an equalizer based on a simple minimum-phase FIR filter and transform it to the new type of equalizer. To achieve this, a number of undesireable effects such as aliasing distortion and upsampling imaging had to be considered and dealt with. In order to achieve a good amplitude response of the system, optimization procedures were used. As part of the thesis, a cost-effective implementation of the filter has been made for an FPGA, in order to verify that the scheme is indeed usable for equalizing an audio signal.

The intense requirements for high processing rates of multidimensional Digital Signal Processing systems in practical applications justify the Application Specific Integrated Circuits designs and parallel processing implementations. In this dissertation, we propose novel theories, methodologies and architectures in designing high-performance VLSI implementations for general multidimensional multirate Digital Signal Processing systems by exploiting the parallelism within those applications. To systematically exploit the parallelism within the multidimensional multirate DSP algorithms, we develop novel transformations including (1) nonlinear I/O data space transforms, (2) intercalation transforms, and (3) multidimensional multirate unfolding transforms. These transformations are applied to the algorithms leading to systematic methodologies in high-performance architectural designs. With the novel design methodologies, we develop several architectures with parallel and distributed processing features for implementing multidimensional multirate applications. Experimental results have shown that those architectures are much more efficient in terms of execution time and/or hardware cost compared with existing hardware implementations.

A haptic system is a robotic computer interface which aims to provide tactile feedback for human operators when they manipulate virtual environments (VEs) or remote environments (REs). The tactile feedback is emulated by applying forces, vibrations, or motions to the human users through a haptic device/interface, e.g. a robot arm. Transparency and stability are two important criteria for designing a haptic system. Transparency is related to the realism of user's touch sensation and stability guarantees the safety of the user while interacting with VEs/REs. Because of the nature of the human tactile sensory system, a transparent haptic system demands an update rate greater than 500 Hz, i.e. most commercial haptic devices work at 1 KHz. On the other hand, many haptic applications are multirate systems. The multirate property of a haptic system is due to either the slow update rate of the VE or the impairments of computer networks such as limited transmission bandwidth or packet loss. Wave transformation is wildly used in teleoperation to cope with both constant and varying time delays. This work aims to use wave transformation to tackle the challenges imposed by multirate property of a haptic system. First, passive multirate wave variables control (PMWVC) is introduced. PMWVC guarantees the passivity of the communication channels through which the fast haptic device is connected to the slow VE/RE. It is shown that to maintain the passivity of the system, aliasing should be avoided in the communication channels, i.e. by using anti-aliasing filters. Next, PMWVC strategy is applied to two different applications: i) multiuser cooperative haptics and ii) haptic interaction with an unknown VE. In the first application, two users at two different locations manipulate a common virtual object simulated on a central server. The users are connected to the central server through a LAN network. The second application is a single user application in which PMWVC is used to connect the haptic device to an unknown slowly updated VE. Since in this application the VE is unknown, the computational delay of the VE significantly affects the stability of the overall system. To tackle this problem, a nonlinear algorithm based on passivity analysis is proposed. In both examples, numerical and experimental results validating the analytical results are provided. The results show that by using PMWVC, it is possible to significantly improve the performance of a multirate haptic system in terms of transparency and stability. The second half of this work is devoted to improving the performance of PMWVC in all frequency ranges. In order to study the performance of PMWVC, lifting is used to convert the multirate haptic system to a unirate system. By using this technique, it is shown that velocity estimation plays a critical role in a haptic application with PMWVC, especially in high frequencies. Considering this fact, a method for designing a passive velocity filter in wave domain is proposed. Finally, a filter bank structure is introduced which enables utilizing a local model in conjunction with PMWVC. In this structure, the outgoing signal sent to the VE is split into two frequency ranges. Low frequency content of the signal is fed to the original VE and high frequency content of the signal is sent to the local model. By using lifting the performance of the proposed structure is studied. The results show that the proposed method improves the transparency of the system in all frequency ranges and unlike utilizing a local model in power domain, it does not impose any restriction on the stability of the system. / Graduate / 0548 / 0544 / 0771 / nyasrebi@uvic.ca

This thesis is concerned with the issues of design and optimisation of digital filters and multirate filter banks. The main focus and contribution of this thesis is to apply the genetic algorithm (GA) technique and to draw some comparison with the standard gradient and non-gradient based optimisation methods. The finite word length (FWL) constraint affects the accuracy of a real-time digital filter requency response. For the case of digital filters, this study is concerned with the optimisation of FWL coefficients using genetic algorithms. Some comparative study with the simple hill climber algorithms is also included. The outcome of this part of the study demonstrates a substantial improvement of the new results when compared with the simply rounded FWL coefficient frequency response. The FWL coefficient optimisation process developed in the earlier Chapters is extended to the field of multirate filter banks. All multirate filter banks suffer from the problems of amplitude, phase and aliasing errors and, therefore, constraints for perfect reconstruction (PR) of the input signal can be extensive. The problem, in general, is reduced to relaxing constraints at the expense of errors and finding methods for minimising the errors. Optimisation techniques are thus commonly used for the design and implementation of multirate filter banks. In this part of the study, GAs have been used in two distinct stages. Firstly, for the design optimisation so that the overall errors are minimised and secondly for FWL coefficient optimisation of digital filters that form the sub-band filters of the filter bank. This process leads to an optimal realisation of the filter bank that can be applied to specific applications such as telephony speech signal coding and compression. One example of the optimised QMF bank was tested on a real-time DSP target system and the results are reported. The multiple M-channel uniform and non-uniform filter banks have also been considered in this study for design optimisation. For a comparative study of the GA optimised results of the design stage of the filter bank, other standard methods such as the gradient based quasi-Newton and the non-gradient based downhill Simplex methods were also used. In general, the outcome of this part of study demonstrates that a hybrid approach of GA and standard method was the most efficient and effective process in generating the best results.

Global Positioning Systems (GPS) is undergoing stunning changes and upgrades which will enhance the Civil and Military users. This modernization included new satellite signals for Civil and Military purposes which benefits the fundamental signal acquisition and tracking of the GPS receiver. These new signals enable a new family of alternatives for mitigating the ionospheric errors that currently limit the GPS accuracy [16]. A new Civil signal L2 Civil (L2C) was commissioned on the L2 frequency which could have ionospheric error elimination capability, with better cross correlation, Data recovery performance, and threshold tracking. The complex structure of the signal calls for new Acquisition approaches which are implementable with limited computational burden. This thesis proposes an Acquisition methodology to acquire the Code phase offset and Carrier frequency offset of the L2C signal which can be implemented in real time. The algorithm employs a serial code search for Code Phase by retaining the original sampling frequency `fs' and implements a FFT search for carrier frequency offset with a reduced sampling frequency of `fs/M' where `M' is the decimation rate. Multirate Filters are employed for reducing the sampling frequency. After the Acquisition is performed, the values are passed onto the Phase Lock Loop (PLL) and Delay Lock Loop (DLL) to further synchronize the Code Phase and Carrier frequency. The algorithm was tested on a real data set for the performance evaluation of Acquisition and Tracking, and the navigation bits were extracted and the results discussed.

Digital Wireless communications has been one of the fastest growing communication techniques during the last decade. Today there exists several different communication systems that use wireless techniques. They share one common property that they transmit data through a radio interface. The radio channel is a tough channel that will both distort and disturb the transmitted signal in various ways. In Jörgen Nordberg's PhD-thesis "Signal Enhancement in Wireless Communications Systems" several different signal enhancement schemes are presented. They have the objective to minimize the impact of the channel. The main part of this thesis presents work on interference cancellation, i.e. how to reduce the impact of other interfering signals on the channel of interest. This is achieved by utilizing the spatial domain, i.e. the receiver is using several antennas to receive the transmitted signals. By using a multitude of antennas techniques like spatial diversity, adaptive antenna arrays, signal separation and beamforming can be applied to combat the interfering signals. In the single antenna case there is often a need to do channel equalization. Since, channel equalization is an inverse filtering, it will often result in estimation of equalization filter parameters of very high order. To reduce the both the complexity and improve the convergence speed of the equalization filter parameter estimation subband processing techniques can be used. In this case the received signal is separated up into different frequency bands (subbands) and decimated according to the bandwidth of the signal. The channel equalization problem is then solved for each subband at a lower sampling rate. Hence, the channel equalization problem is transformed from estimating the parameters of a high order filter into estimating several filter of much lower order. / Ett av områdena inom telekommunikation som har ökat mest de senaste åren är radio kommunikation. Det finns många olika varianter av trådlösa radio system, men de har alla en sak gemensamt, de överför information/data via ett radiogränssnitt. Signaler som sänds över en radiokanal kommer på grund av många olika anledningar att bli störda eller distorderade. I Jörgen Nordbergs doktorsavhandling ?Signal Enhancement in Wireless Communication Systems? presenteras flera metoder för att förbättra kvaliten i de mottagna signalerna vilket ger betydande kvalitetsförbättring. Huvuddelen av denna doktorsavhandling behandlar interferensundertrycking, d.v.s. hur man undertrycker oönskad störning på den egna radiokanalen. Dessa metoder är baserade på användning av flera antenner i mottagaren. Genom att ta emot signalerna med flera antenner så kan metoder såsom diversitetskombinering, adaptiva antenner, lobformning, signal separation användas för att förbättra kvaliteten i den mottagna signalen. Om mottagaren har en antenn så behövs oftast kanalutjämning för att förbättra den mottagna signalen och undertrycka intersymbolinterferens. Eftersom kanalutjämning är en typ av inversfiltrering leder detta ofta till estimering av filterparametrar av hög ordning. Estimeringsproblem av hög ordning leder ofta till komplexitetsproblem och konvergensproblem hos estimerings algoritmen. För att motverka dessa problem så presenteras i denna avhandling en kanalutjämnare som är baserad på subbandsteknik. I denna kanalutjämnare så delas den mottagna signalen upp i flera frekvensband (subband) som decimeras till en takt som motsvarar subbandets bandbredd varefter filterparametrarna estimeras i denna lägre takt. Därvid har estimeringsproblemet delats upp i flera små problem som kan hanteras enklare.

No description available.

Numerical simulation is necessary to understand natural phenomena, make assessments and predictions in various research and engineering fields, develop new technologies, etc. New algorithms are needed to take advantage of the increasing computational resources and utilize the emerging hardware and software infrastructure with maximum efficiency. Adaptive numerical discretization methods can accommodate problems with various physical, scale, and dynamic features by adjusting the resolution, order, and the type of method used to solve them. In applications that simulate real systems, the numerical accuracy of the solution is typically just one of the challenges. Measurements can be included in the simulation to constrain the numerical solution through a process called data assimilation in order to anchor the simulation in reality. In this thesis we investigate adaptive discretization methods and data assimilation approaches for large-scale numerical simulations. We develop and investigate novel multirate and implicit-explicit methods that are appropriate for multiscale and multiphysics numerical discretizations. We construct and explore data assimilation approaches for, but not restricted to, atmospheric chemistry applications. A generic approach for describing the structure of the uncertainty in initial conditions that can be applied to the most popular data assimilation approaches is also presented. We show that adaptive numerical methods can effectively address the discretization of large-scale problems. Data assimilation complements the adaptive numerical methods by correcting the numerical solution with real measurements. Test problems and large-scale numerical experiments validate the theoretical findings. Synergistic approaches that use adaptive numerical methods within a data assimilation framework need to be investigated in the future. / Ph. D.

Mathematical models involving ordinary differential equations (ODEs) play a critical role in scientific and engineering applications. Advances in computing hardware and numerical methods have allowed these models to become larger and more sophisticated. Increasingly, problems can be described as multiphysics and multiscale as they combine several different physical processes with different characteristics. If just one part of an ODE is stiff, nonlinear, chaotic, or rapidly-evolving, this can force an expensive method or a small timestep to be used. A method which applies a discretization and timestep uniformly across a multiphysics problem poorly utilizes computational resources and can be prohibitively expensive. The focus of this dissertation is on "multimethods" which apply different methods to different partitions of an ODE. Well-designed multimethods can drastically reduce the computation costs by matching methods to the individual characteristics of each partition while making minimal concessions to stability and accuracy. However, they are not without their limitations. High order methods are difficult to derive and may suffer from order reduction. Also, the stability of multimethods is difficult to characterize and analyze. The goals of this work are to develop new, practical multimethods and to address these issues. First, new implicit multirate Runge–Kutta methods are analyzed with a special focus on stability. This is extended into implicit multirate infinitesimal methods. We introduce approaches for constructing implicit-explicit methods based on Runge–Kutta and general linear methods. Finally, some unique applications of multimethods are considered including using surrogate models to accelerate Runge–Kutta methods and eliminating order reduction on linear ODEs with time-dependent forcing. / Doctor of Philosophy / Almost all time-dependent physical phenomena can be effectively described via ordinary differential equations. This includes chemical reactions, the motion of a pendulum, the propagation of an electric signal through a circuit, and fluid dynamics. In general, it is not possible to find closed-form solutions to differential equations. Instead, time integration methods can be employed to numerically approximate the solution through an iterative procedure. Time integration methods are of great practical interest to scientific and engineering applications because computational modeling is often much cheaper and more flexible than constructing physical models for testing. Large-scale, complex systems frequently combine several coupled processes with vastly different characteristics. Consider a car where the tires spin at several hundred revolutions per minute, while the suspension has oscillatory dynamics that is orders of magnitude slower. The brake pads undergo periods of slow cooling, then sudden, rapid heating. When using a time integration scheme for such a simulation, the fastest dynamics require an expensive and small timestep that is applied globally across all aspects of the simulation. In turn, an unnecessarily large amount of work is done to resolve the slow dynamics. The goal of this dissertation is to explore new "multimethods" for solving differential equations where a single time integration method using a single, global timestep is inadequate. Multimethods combine together existing time integration schemes in a way that is better tailored to the properties of the problem while maintaining desirable accuracy and stability properties. This work seeks to overcome limitations on current multimethods, further the understanding of their stability, present new applications, and most importantly, develop methods with improved efficiency.