In this thesis, fast Viterbi Decoder algorithms for a multi-core system are studied. New parallel Viterbi algorithms for decoding convolutional codes are proposed based on tail biting trellises. The performances of the new algorithms are first evaluated by MATLAB and then Eagle (E-UTRA algorithms for LTE) link level simulations where the optimal parameter settings are obtained based on various simulations. One of the algorithms is proposed for implementation in the product due to its good BLER performance and low implementation complexity. The new parallel algorithm is then implemented on target DSPs for Ericsson internal multi-core system to decode the PUSCH (Physical Uplink Shared Channel) CQI (Channel Quality Indicator) in LTE (Long Term Evolution). And the performance of the new algorithm in the real multi-core system is compared against the current implementation regarding both cycle and memory consumption. As a fast decoder, the proposed parallel Viterbi decoder is computationally efficient which reduces significantly the decoding latency and solves memory limitation problems on DSP.

No description available.

No description available.

Synthetic Aperture Radar (SAR) is a type of radar system that can generate high-resolution images with which one can detect subtle changes on the scale of centimetres from space. It can operate in any weather condition and during both day and night, making it unique compared to optical sensors. SAR is used for applications such as environmental monitoring, surveillance, and earth observation. Its ability to penetrate clouds and, to some extent, vegetation, allows for insights into terrain, vegetation structure, and even subsurface features. The importance of modelling the generated data of a SAR system before initiating the construction and development of it cannot be overstated. This thesis presents the implementation of the Reverse BackProjection Algorithm (RBPA) designed to generate raw SAR data efficiently and accurately. The RBPA stands out with its flexibility, enabling researchers and designers to simulate and gauge the SAR system's effectiveness under diverse scenarios. This provides an easy way of fine-tuning configurations for distinct needs concerning scene geometries, orbits, and radar designs. Two versions of the RBPA were implemented, differing slightly in the theoretical approach of azimuth defocusing. On top of this, a bistatic mode and Terrain Observation by Progressive Scans (TOPS) acquisition mode was also implemented. The inclusion of these two modes were specifically due to their relevance for the upcoming European Space Agency (ESA) SAR mission, Harmony. The addition of the TOPS mode required a comprehensive design of the antenna framework. Moreover, this implementation also paves the way for simpler integration of modes in the future. The two versions of the RBPA were profiled, revealing the optimal system and parameter configurations.

No description available.

Advanced enough quantum computers promise to revolutionise fields such as cryptography, drug discovery and simulations of complex systems. Quantum computers are built on qubits which are fragile and susceptible to error-inducing interference, which is called noise. The aim of this study was to examine the effects of varying levels of noise interference on the success rate and runtimes of a quantum computer circuit design built to implement Shor’s quantum factorisation algorithm. This was conducted using the Qiskit framework for quantum computer simulation and custom noise model creation. Our results show a correlation between the level of noise interference on a circuit and the probability of getting the correct measurement. We also found a greater impact of readout errors on the success rates, one-qubit depolarising errors on runtimes and that two-qubit depolarising errors greatly affected both, which was also discussed in the study. Our findings are in line with previous research and help to highlight the importance of minimising errors on critical quantum logic gates in an algorithm. / Tillräckligt avancerade kvantdatorer lovar att revolutionera områden så som kryptografi, utveckling av nya läkemedel och simulering av komplexa system. Kvantdatorer är uppbyggda av qubits vilka är ömtåliga och mottagliga mot felinducerande interferens, vilket kallas brus. Målet med denna studie var att utforska effekten av varierande brusnivåers interferens på lyckade försök samt körtiden av en kvantdatorkrets designad för att implementera Shors algoritm. Detta gjordes med Qiskits ramverk för kvantdatorsimulering och anpassningsbara brusmodeller. Våra resultat visar en korrelation mellan nivån av brusinterferens på en krets och sannolikheten av att få den korrekt mätningen. Vi fann även en större påverkan av avläsningsfel på kvoten lyckade försök, en-qubit depolariserande fel på körtid och att två-qubit depolariserande fel hade en stor påverkan på båda, vilket vi även diskuterat i studien. Våra resultat är i linje med tidigare studier och hjälper till att lyfta fram vikten av att minimera inducerade fel på kritiska logiska grindar i en kvantdatoralgoritm.

No description available.

Anomaly detection has been one of the most important applications of datamining, widely applied in industries like financial, medical,telecommunication, even manufacturing. In many scenarios, data are in theform of streaming in a large amount, so it is preferred to analyze the datawithout storing all of them. In other words, the key is to improve the spaceefficiency of algorithms, for example, by extracting the statistical summary ofthe data. In this thesis, we study the PRAAG algorithm, a collective anomalydetection algorithm based on quantile feature of the data, so the spaceefficiency essentially depends on that of quantile algorithm.Firstly, the master thesis investigates quantile summary algorithms thatprovides quantile information of a dataset without storing all the data point.Then, we implement the selected algorithms and run experiments to test theperformance. Finally, the report focuses on experimenting on PRAAG tounderstand how the parameters affect the performance and compare it withother anomaly detection algorithms.In conclusion, GK algorithm provides a more space efficient way to estimatequantiles than simply storing all data points. Also, PRAAG is effective in termsof True Prediction Rate (TPR) and False Prediction Rate (FPR), comparingwith a baseline algorithm CUSUM. In addition, there are many possibleimprovements to be investigated, such as parallelizing the algorithm. / Att upptäcka avvikelser har varit en av de viktigaste tillämpningarna avdatautvinning (data mining). Det används stor utsträckning i branscher somfinans, medicin, telekommunikation, och även tillverkning. I många fallströmmas stora mängder data och då är det mest effektivt att analysera utanatt lagra data. Med andra ord är nyckeln att förbättra algoritmernasutrymmeseffektivitet till exempel genom att extraheraden statistiskasammanfattning avdatat. PRAAGär en kollektiv algoritm för att upptäckaavvikelser. Den ärbaserad på kvantilenegenskapernai datat, såutrymmeseffektiviteten beror i huvudsak på egenskapernahoskvantilalgoritmen.Examensarbetet undersöker kvantilsammanfattande algoritmer som gerkvantilinformationen av ett dataset utan att spara alla datapunkter. Vikommer fram till att GKalgoritmenuppfyllervåra krav. Sedan implementerarvialgoritmerna och genomför experiment för att testa prestandan. Slutligenfokuserar rapporten påexperiment på PRAAG för att förstå hur parametrarnapåverkar prestandan. Vi jämför även mot andra algoritmer för att upptäckaavvikelser.Sammanfattningsvis ger GK ett mer utrymmeseffektiv sätt att uppskattakvantiler än att lagra alla datapunkter. Dessutom är PRAAG, jämfört med enstandardalgoritm (CUSUM), effektiv när det gäller True Prediction Rate (TPR)och False Prediction Rate (FPR). Det finns fortfarande flertalet möjligaförbättringar som ska undersökas, t.ex. parallelisering av algoritmen.

<p>The main part of this thesis is concerned with detailed explanation of a newly proposed Markov random field-based de-interlacing algorithm. Previous works, assume a first or higher-order Markovian spatial inter-dependency between the pixel intensity values. In accord with the specific interpolation problem in hand, they try to approximate the Markov random field parameters using available original pixels. Then using the approximate model, they define an objective function such as energy function of the MRF to be optimized. The efficiency and accuracy of the optimization step is as important as the effectiveness of definition of the cost (objective function) as well as the MRF model.\\ \indent The major concept that distinguishes the newly proposed algorithm with the aforementioned MRF-based models is the definition of the MRF not over the intensity domain but over interpolator (interpolation method) domain. Unlike previous MRF-based models which try to estimate a two-dimensional array of pixel values, this new method estimates an MRF of interpolation function (interpolators) associated with the 2-D array of pixel intensity values.\\ \indent With some modifications, one can utilize the proposed model in different related fields such as image and video up-conversion, view interpolation and frame-rate up-conversion. To prove this potential of the proposed MRF-based model, we extend it to an image up-scaling algorithm. This algorithm uses a simplified version of the proposed MRF-based model for the purpose of image up-scaling by a factor of two in each spatial direction. Simulation results prove that the proposed model obtains competing performance results when applied in the two interpolation problems of video de-interlacing and image up-scaling.</p> / Master of Applied Science (MASc)

Adaptive filtering techniques are used in a wide range of applications, including echo cancellation, adaptive equalization, adaptive noise cancellation, and adaptive beamforming. The performance of an adaptive filtering algorithm is evaluated based on its convergence rate, misadjustment, computational requirements, and numerical robustness. We attempt to improve the performance by developing new adaptation algorithms and by using "unconventional" structures for adaptive filters. Part I of this dissertation presents a new adaptation algorithm, which we have termed the Normalized LMS algorithm with Orthogonal Correction Factors (NLMS-OCF). The NLMS-OCF algorithm updates the adaptive filter coefficients (weights) on the basis of multiple input signal vectors, while NLMS updates the weights on the basis of a single input vector. The well-known Affine Projection Algorithm (APA) is a special case of our NLMS-OCF algorithm. We derive convergence and tracking properties of NLMS-OCF using a simple model for the input vector. Our analysis shows that the convergence rate of NLMS-OCF (and also APA) is exponential and that it improves with an increase in the number of input signal vectors used for adaptation. While we show that, in theory, the misadjustment of the APA class is independent of the number of vectors used for adaptation, simulation results show a weak dependence. For white input the mean squared error drops by 20 dB in about 5N/(M+1) iterations, where N is the number of taps in the adaptive filter and (M+1) is the number of vectors used for adaptation. The dependence of the steady-state error and of the tracking properties on the three user-selectable parameters, namely step size, number of vectors used for adaptation (M+1), and input vector delay D used for adaptation, is discussed. While the lag error depends on all of the above parameters, the fluctuation error depends only on step size. Increasing D results in a linear increase in the lag error and hence the total steady-state mean-squared error. The optimum choices for step size and M are derived. Simulation results are provided to corroborate our analytical results. We also derive a fast version of our NLMS-OCF algorithm that has a complexity of O(NM). The fast version of the algorithm performs orthogonalization using a forward-backward prediction lattice. We demonstrate the advantages of using NLMS-OCF in a practical application, namely stereophonic acoustic echo cancellation. We find that NLMS-OCF can provide faster convergence, as well as better echo rejection, than the widely used APA. While the first part of this dissertation attempts to improve adaptive filter performance by refining the adaptation algorithm, the second part of this work looks at improving the convergence rate by using different structures. From an abstract viewpoint, the parameterization we decide to use has no special significance, other than serving as a vehicle to arrive at a good input-output description of the system. However, from a practical viewpoint, the parameterization decides how easy it is to numerically minimize the cost function that the adaptive filter is attempting to minimize. A balanced realization is known to minimize the parameter sensitivity as well as the condition number for Grammians. Furthermore, a balanced realization is useful in model order reduction. These properties of the balanced realization make it an attractive candidate as a structure for adaptive filtering. We propose an adaptive filtering algorithm based on balanced realizations. The third part of this dissertation proposes a unit-norm-constrained equation-error based adaptive IIR filtering algorithm. Minimizing the equation error subject to the unit-norm constraint yields an unbiased estimate for the parameters of a system, if the measurement noise is white. The proposed algorithm uses the hyper-spherical transformation to convert this constrained optimization problem into an unconstrained optimization problem. It is shown that the hyper-spherical transformation does not introduce any new minima in the equation error surface. Hence, simple gradient-based algorithms converge to the global minimum. Simulation results indicate that the proposed algorithm provides an unbiased estimate of the system parameters. / Ph. D.