In this thesis, the design and implementation of a Portable Feedback Active Noise Controller Headphone System, which is based on Texas Instruments TMS320VC5416PGE120 Fixed Point DSP, is described. Problems resulted from fixed-point implementation of LMS algorithm and delays existing in digital ANC implementation are determined. Effective solutions to overcome the aforementioned problems are proposed based on the literature survey. Design of the DSP based control card is explained and crucial points about analog-digital-mixed board design for noise sensitive applications are explained. Filtered input LMS algorithm, filtered input normalized LMS algorithm and filtered input sign-sign LMS algorithm are implemented as adaptation algorithms. The advantages and disadvantages of using modified LMS algorithms are indicated. The selection of the parameters of these algorithms is based on theoretical results and experiments. The real time performances of different adaptation algorithms are compared with each other as well as with a commercial analog ANC headphone under different types of artificial and natural noise signals. Moreover, practical conditions such as put on - put off case and dynamic range overflow case are handled with additional software implementations. It is shown that adaptive ANC systems improve the noise reduction significantly when the noise is within a narrow frequency range and this reduction can be applied to a wider frequency range. It is also shown that the problems of digitally implemented adaptive filters which are based on tracking capability, stability, dynamic range and portability can be fixed to challenge with the analog commercial ANC systems.

The realisation of signal processing algorithms in fixed-point offers substantial performance advantages over floating-point realisations. However, it is widely acknowledged that the task of realising algorithms in fixed-point is a challenging one with limited tool support. This thesis examines various aspects related to the translation of algorithms, given in infinite precision or floating-point, into fixed-point. In particular, this thesis reports on the implementation of a given algorithm, an EDFA (Erbium-Doped Fibre Amplifier) control algorithm, on a FPGA (Field Programmable Gate Array) using fixed-point arithmetic. An analytical approach is proposed that allows the automated realisation of algorithms in fixedpoint. The technique provides fixed-point parameters for a given floating-point model that satisfies a precision constraint imposed on the primary output of the algorithm to be realised. The development of a simulation framework based on this analysis allows fixed-point designs to be generated in a shorter time frame. Albeit being limited to digital algorithms that can be represented as a data flow graph (DFG), the approach developed in the thesis allows for a speed up in the design and development cycle, reduces the possibility of error and eases the overall effort involved in the process. It is shown in this thesis that a fixed-point realisation of an EDFA control algorithm using this technique produces results that satisfy the given constraints.

Thesis (MSc)--University of Stellenbosch, 2005. / ENGLISH ABSTRACT: The majority of tra c on the Internet uses the Transmission Control Protocol (TCP) as a transport layer protocol for the end-to-end control of information transfer. Measurement, simulation and analytical models are the techniques and tools that can be used to understand and investigate the Internet and its performance. Measurements can only be used to explore existing network scenario or otherwise become costly and in exible with the growth and complexity of the Internet. Simulation models do not scale with the growth of network capacities and the number of users. Computationally e cient analytical models are therefore important tools for investigating, designing, dimensioning and planning IP (Internet Protocol) networks. Existing analytical models of TCP performance are either too simple to capture the internal dynamics of TCP or are too complex to be used to analyze realistic network topologies with several bottleneck links. The literature shows that the xed point algorithm (FPA) is a very useful way of solving analytical models of Internet performance. This thesis presents fast and accurate analytical models of TCP performance with the FPA used to solve them. Apart from what is observed in experimental literature, no comprehensive proof of the convergence and uniqueness of the FPA is given. In this thesis we show how the FPA of analytical models of reliable Internet protocols such as TCP converges to a unique xed point. The thesis speci es the conditions necessary in order to use the FPA for solving analytical models of reliable Internet protocols. We also develop a general implementation algorithm of the FPA of analytical models of TCP performance for realistic and arbitrary network topologies involving heterogenous TCP connections crossing many bottleneck links. The models presented in this thesis give Internet performance metrics, assuming that only basic network parameters such as the network topology, the number of TCP connections, link capacity, distance between network nodes and router bu er sizes are known. To obtain the performance metrics, TCP and network sub{models are used. A closed network of :=G=1 queues is used to develop each TCP sub-model where each queue represents a state of a TCP connection. An M=M=1=K queue is used for each network sub{model which represents the output interface of an IP router with a bu er capacity of K 􀀀��������1 packets. The two sub-models are iteratively solved. We also give closed form expressions for important TCP performance values and distributions. We show how the geometric, bounded geometric and truncated geometric distributions can be used to model reliable protocols such as TCP. We give models of the congestion window cwnd size distribution by conditioning on the slow start threshold ssthresh distribution and vice-versa. We also present models of the probabilities of TCP timeout and triple duplicate ACK receptions. Numerical results based on comparisons against ns2 simulations show that our models are more accurate, simpler and computationally more e cient than another well known TCP model. Our models can therefore be used to rapidly analyze network topologies with several bottlenecks and obtain detailed performance metrics. / AFRIKAANSE OPSOMMING: Die meerderheid van die verkeer op die Internet gebruik die Transmission Control Protocol (TCP) as `n vervoer laag protokol vir die einde-tot-einde kontrole van inligting oordrag. Meting, simulasie en analitiese modelle is die tegnieke en gereedskap wat gebruik kan word om die Internet te ondersoek en verstaan. Meting kan slegs gebruik word om bestaande netwerke scenarios te verken. Meting is duur en onbuigsaam met die groei en samegesteldheid van die Internet. Simulasie modelle skaal nie met die groei van netwerk kapasiteit en gebruikers nie. Analitiese modelle wat berekening e ektief is is dus nodige gereedskap vir die ondersoek, ontwerp, afmeting en beplanning van IP (Internet Protocol) netwerke. Bestaande analitiese TCP modelle is of te eenvoudig om die interne dinamiek van die TCP saam te vat of hulle is te ingewikkeld om realistiese netwerk topologie met heelwat bottelnek skakels te analiseer. Literatuur toon dat die xed point algorithm (FPA) baie handig is vir die oplos van analitiese modelle van Internet verrigting. In hierdie tesis word vinnige en akkurate analitiese modelle van TCP verrigting opgelos deur FPA weergegee. Buiten wat deur eksperimentele literatuur aangedui word is daar geen omvattende bewyse van die konvergensie en uniekheid van die FPA nie. In hierdie tesis word aangedui hoe die FPA van analitiese modelle van betroubare Internet protokolle soos die TCP konvergeer na `n unieke vaste punt. Hierdie tesis spesi seer die voorwaardes benodig om die FPA te gebruik vir die oplos van analitiese modelle van realistiese Internet protokolle. `n Algemene uitvoer algoritme van die FPA van analitiese modelle van TCP vir realistiese en arbitr^ere netwerk topogra e insluitende heterogene TCP konneksies oor baie bottelnek skakels is ontwikkel. Die model in hierdie tesis gee Internet verrigting metodes met die aanname dat slegs basiese netwerk parameters soos netwerk topologie, die aantal TCP konneksies, die konneksie kapasiteit, afstand tussen netwerk nodusse en die roete bu er grotes bekend is. Om die verrigting metodes te verkry, word TCP en netwerk sub-modelle gebruik. `n Geslote netwerk van :=G=1 rye is gebruik om elke TCP sub-model, waar elke ry 'n toestand van `n TCP konneksie voorstel, te ontwikkel. `n M=M=1=K ry is gebruik vir elke netwerk sub-model wat die uitset koppelvlak van `n IP roetemaker met `n bu er kapasiteit van K 􀀀������� 1 pakkies voorstel. Die twee submodelle word iteratief opgelos. Geslote vorm uitdrukkings vir belangrike TCP verrigting waardes en verspreidings word gegee. Daar word getoon hoe geometriese, begrensde geometriese en geknotte geometriese verspreidings gebruik kan word om betroubare protokolle soos die TCP te modelleer. Modelle van die kongestie venster cwnd grootte verspreiding word gegee deur die kondisionering van die stadige aanvang drempel ssthresh verspreiding en andersom. Modelle van die voorspelling van TCP tyduit en trippel duplikaat ACK resepsie word weergegee. Numeriese resultate gebaseer op vergelykings met ns2 simulasies wys dat ons modelle meer akkuraat, eenvoudiger en berekeningsgewys meer e ektief is as ander wel bekende TCP modelle. Ons modelle kan dus gebruik word vir vinnig analise van netwerk topologie met verskeie bottelnekke en om gedetailleerde verrigting metodes te bekom.

Pour réduire les coûts des systèmes embarqués, ces derniers sont livrés avec des micro-processeurs peu puissants. Ces processeurs sont dédiés à l'exécution de tâches calculatoires dont certaines, comme la transformée de Fourier rapide, peuvent s'avérer exigeantes en termes de ressources de calcul. Afin que les implémentations de ces algorithmes soient efficaces, les programmeurs utilisent l'arithmétique à virgule fixe qui est plus adaptée aux processeurs dépourvus d'unité flottante. Cependant, ils se retrouvent confrontés à deux difficultés: D'abord, coder en virgule fixe est fastidieux et exige que le programmeur gère tous les détails arithmétiques. Ensuite, et en raison de la faible dynamique des nombres à virgule fixe par rapport aux nombres flottants, les calculs en fixe sont souvent perçus comme intrinsèquement peu précis. La première partie de cette thèse propose une méthodologie pour dépasser ces deux limitations. Elle montre comment concevoir et mettre en œuvre des outils pour générer automatiquement des programmes en virgule fixe. Ensuite, afin de rassurer l'utilisateur quant à la qualité numérique des codes synthétisés, des certificats sont générés qui fournissent des bornes sur les erreurs d'arrondi. La deuxième partie de cette thèse est dédiée à l'étude des compromis lors de la génération de programmes en virgule fixe pour les briques d'algèbre linéaire. Des données expérimentales y sont fournies sur la synthèse de code pour la multiplication et l'inversion matricielles. / To be cost effective, embedded systems are shipped with low-end micro-processors. These processors are dedicated to one or few tasks that are highly demanding on computational resources. Examples of widely deployed tasks include the fast Fourier transform, convolutions, and digital filters. For these tasks to run efficiently, embedded systems programmers favor fixed-point arithmetic over the standardized and costly floating-point arithmetic. However, they are faced with two difficulties: First, writing fixed-point codes is tedious and requires that the programmer must be in charge of every arithmetical detail. Second, because of the low dynamic range of fixed-point numbers compared to floating-point numbers, there is a persistent belief that fixed-point computations are inherently inaccurate. The first part of this thesis addresses these two limitations as follows: It shows how to design and implement tools to automatically synthesize fixed-point programs. Next, to strengthen the user's confidence in the synthesized codes, analytic methods are suggested to generate certificates. These certificates can be checked using a formal verification tool, and assert that the rounding errors of the generated codes are indeed below a given threshold. The second part of the thesis is a study of the trade-offs involved when generating fixed-point code for linear algebra basic blocks. It gives experimental data on fixed-point synthesis for matrix multiplication and matrix inversion through Cholesky decomposition.

Neste trabalho demonstram-se os teoremas de ponto fixo de Brouwer e Kakutani com o objetivo de provar a existência do equilíbrio de Nash em jogos finitos em forma normal. No primeiro capítulo apresentam-se as definições de teoria dos jogos, começando com jogos finitos em forma normal e terminando com o conceito de equilíbrio de Nash. Na primeira seção do capítulo dois desenvolve-se a teoria de simplexes, em Rn, e se demonstra o teorema de Brouwer. Na seção seguinte, são relacionadas as propriedades de semi-continuidade superior e gráfico fechado em set functions, para então provar os teoremas de Celina e von Neumann que, em conjunto com o teorema de Brouwer, resultam no teorema de Kakutani no fim da seção. Como último resultado é demonstrado o teorema de existência do equilíbrio de Nash em jogos finitos em forma normal através do teorema de Kakutani, mostrando que o equilíbrio de Nash é um ponto fixo de uma set function. / In this work, the fixed-point theorems of Kakutani and Brouwer are proved with the intention of showing the existence of Nash equilibrium in finite normal-form games. In the first chapter the needed definitions of game theory are shown, starting with finite normal-form games and ending with the concept of Nash equilibrium. In the first section of chapter two, simplex theory in Rn is developed and then the Brouwer fixer point theorem is proved. In the next section, some relations of upper hemi-continuity and closed graph in set functions are shown, then proving the theorems of Celina and von Neumann that, along with Brouwer theorem, result in Kakutani fixed-point theorem in the end of the section. As the last result, the existence of Nash equilibrium in finite normal-form games is proved through Kakutani’s theorem, relating the Nash equilibrium to the fixed-point of a set function.

No description available.

L’objectif de ce travail de thèse est d’étudier quelques problèmes elliptiques et paraboliques d’écoulement de fluides non Newtoniens incompressibles et non isothermes gouvernés par l’équation aux dérivées partielles de Stokes avec la condition de Tresca sur une partie du bord quand la viscosité dépend à la fois de la température, de la vitesse et du module du tenseur des taux de déformations. Dans le premier chapitre, on a fait une introduction générale. Dans le deuxième chapitre, nous nous intéressons au couplage entre le système de Stokes et l’équation de la chaleur en régime stationnaire. On montre l’existence de la solution de l’inéquation variationnelle décrivant le système de Stokes pour une température donnée quand la viscosité dépend à la fois de la température, de la vitesse et du module du tenseur des taux de déformations en utilisant la méthode de monotonie pour la vitesse et le théorème de De Rham pour la pression. Dans un deuxième temps, on étudie l’existence et l’unicité de la température solution de l’équation de la chaleur avec un terme L1(Ω) au second membre quand la viscosité dépend à la fois de la température, de la vitesse et du module du tenseur des taux de déformations. On montre ensuite l’existence de la solution du problème variationnel couplé avec la viscosité dépend de la température et du module du tenseur des taux de déformations, en utilisant le théorème de point fixe de Schauder. Dans le troisième et le quatrième chapitre, on traite l’existence et l’unicité de la solution du système de Stokes en régime instationnaire quand la viscosité dépend de la température et du module du tenseur des taux de déformations dans les cas p = 2, p > 2 et 6 5 < p < 2 en utilisant la notion des semi-groupes et la méthode de monotonie pour la vitesse et le théorème de De Rham pour la pression. Par contre, lorsque la viscosité dépend de plus de la vitesse on obtient seulement l’existence par le théorème de point fixe de Schauder / The objective of this thesis is to study some elliptic and parabolic problems of the non-Newtonian flow of an incompressible and non isothermal fluid governed by partial differential equation of Stokes with Tresca’s condition on a part of the boundary when the fluid viscosity depends on temperature and also on the modulus of strain rate tensor and the velocity of the fluid. In the first chapter, we did a general introduction. In the second chapter, we consider the coupling between the Stokes systemand the heat equation in steady state. We prove the existence of a solution of the variational inequality describing the Stokes system when the fluid viscosity depends on temperature and also on the modulus of strain rate tensor and the velocity of the fluid of a given temperature by using the monotony methods for the velocity and De Rham’s theorem for the pressure. We study the existence and uniqueness of the temperature solution of the heat equation with L1 (Ω) term to the second member when the fluid viscosity depends on temperature and also on the modulus of strain rate tensor and the velocity of the fluid. We show the existence of a solution of the coupled variational problem when the fluid viscosity depends on temperature and also on the modulus of strain rate tensor by using Schauder fixed point theorem. In the third and the fourth chapter, we treate the existence and uniqueness of a solution of the Stokes system in unsteady state when the fluid viscosity depends only on temperature and on the modulus of strain rate tensor in the cases p = 2, p > 2 and 6 5 < p < 2 by using the notion of semigroup and monotony methods for the velocity and De Rham’s theorem for the pressure. However, when the fluid viscosity depends also on the velocity of the fluid we obtain only the existence by Schauder fixed point theorem

Les modèles de pile de sable sont une sous-classe d'automates cellulaires. Bak et al. les ont introduit en 1987 comme une illustration de la notion intuitive d'auto-organisation critique.Le modèle de pile de sable Kadanoff est un système dynamique discret non-linéaire imagé par des grains cubiques se déplaçant de colonne parfaitement empilée en colonne parfaitement empilée. Pour un paramètre p fixé, une règle d'éboulement est appliquée jusqu'à atteindre une configuration stable, appelée point fixe : si la différence de hauteur entre deux colonnes consécutives est strictement supérieure à p, alors p grains chutent de la colonne de gauche, un retombant sur chacune des p colonnes adjacentes sur la droite.A partir d'une règle locale simple, décrire et comprendre le comportement macroscopique des piles de sable s'avère très rapidement compliqué. La difficulté consiste en la prise en compte simultanée des modalités discrète et continue du système : vue de loin, une pile de sable s'écoule comme un liquide ; mais de près, lorsque l'on s'attache à décrire exactement une configuration, les effets de la dynamique discrète doivent être pris en compte. Si par exemple nous ajoutons un unique grain à une configuration stable, celui-ci déclenche une avalanche qui ne modifie que la couche supérieure de la pile, mais dont la taille est très difficile à prédire car sensible au moindre changement sur la configuration.En analogie avec un sablier, nous nous intéressons en particulier à la séquence des points fixes atteints par l'ajout répété d'un nombre fini de grains à une même position, et à l'émergence de structures étonnamment régulières.Après avoir établi une conjecture sur l'émergence de motifs de vague sur les points fixes, nous nous pencherons dans un premier temps sur une procédure inductive de calcul des points fixes. Chaque étape de l'induction correspond au calcul d'une avalanche provoquée par l'ajout d'un nouveau grain, et nous en proposerons une description simple. Cette étude sera prolongée par la définition de trace des avalanches sur une colonne i, qui capture dans un mot d'un alphabet fini l'information nécessaire à la reconstitution du point fixe pour les colonnes à la droite de l'indice i. Des liens entre les traces à des indices successifs seront alors exploités, liens qui permettent de conclure l'émergence de traces régulières, pour lesquelles la reconstitution du point fixe implique la formation des motifs de vague observés. Cette première approche est concluante pour le plus petit paramètre conjecturé jusqu'ici, p=2.L'étude du cas général que nous proposons passe par la construction d'un nouveau système mêlant différentes représentations des points fixes, qui sera analysé par l'association d'arguments d'algèbre linéaire et combinatoires (liés respectivement aux modalités continue et discrète des piles de sable). Ce résultat d'émergence de régularités dans un système dynamique discret fait appel à des techniques nouvelles, dont la compréhension d'un élément de preuve reste en particulier à raffiner, ce qui permet d'envisager un cadre plus général d'appréhension de la notion d'émergence. / Sandpile models are a subclass of Cellular Automata. Bak et al. introduced them in 1987 for they exemplify the intuitive notion of Self-Organized Criticality.The Kadanoff sandpile model is a non-linear discrete dynamical system illustrating the evolution of cubic sand grains from nicely packed columns to nicely packed columns. For a fixed parameter p, a rule is applied until reaching a stable configuration, called a fixed point : if the height difference between two consecutive columns is strictly greater than p, then p grains fall from the left column, one landing on each of the p adjacent columns on the right.From a simple local rule, to describe and understand the macroscopic behavior of sandpiles is very quickly challenging. The difficulty consists in the simultaneous study of continuous and discrete aspects of the system: on a large scale, a sandpile flows like a liquid; but on a small scale, when we want to describe exactly the shape of a fixed point, the effects of the discrete dynamic must be taken into account. If for example we add a single grain on a stabilized sandpile, it triggers an avalanche that roughly changes only the upper layer of the configuration, but which size is hard to predict because it is sensitive to the tiniest change of the configuration.In analogy with an hourglass, we are particularly interested in the sequence of fixed points reached after adding a finite number of grains on one position, with the aim of explaining the emergence of surprisingly regular patterns.After conjecturing the emergence of wave patterns on fixed points, we firstly consider an inductive procedure for computing fixed points. Each step of the induction corresponds to the computation of an avalanche triggered by the addition of a new grain, for which we propose a simple description. This study is carried on with the definition of the trace of avalanches on a column i, which catches in a word among a finite alphabet enough information in order to reconstruct the fixed point on the right of index i. Links between traces on successive columns are then investigated, links allowing to conclude the emergence of regular traces, whose fixed point's reconstruction involves the appearance and maintain of the wave patterns observed. This first approach is conclusive for the smallest conjectured parameter so far, p=2.The study of the general case goes through the design of a new system meddling in different representations of fixed points, which will be analyzed via an association of arguments of linear algebra and combinatorics (respectively corresponding to the continuous and discrete modalities of sandpiles). This result stating the emergence of regularities in a discrete dynamical system put new technics into light, for which the comprehension of a particular point in the proof remains to be increased. This motivates the consideration of a more general frame of work tackling the notion of emergence.

<p>The advanced signal processing systems of today require extreme data throughput and low power consumption. The only way to accomplish this is to use parallel processor architecture.</p><p>The aim of this thesis was to evaluate the use of parallel processor architecture in baseband signal processing. This has been done by implementing three demanding algorithms in LTE on Ambric Am2000 family Massively Parallel Processor Array (MPPA). The Ambric chip is evaluated in terms of computational performance, efficiency of the development tools, algorithm and I/O mapping.</p><p>Implementations of Matrix Multiplication, FFT and Block Interleaver were performed. The implementation of algorithms shows that high level of parallelism can be achieved in MPPA especially on complex algorithms like FFT and Matrix multiplication. Different mappings of the algorithms are compared to see which best fit the architecture.</p>

In almost all works in the literature there are several results showing asymptotic relationships between the solutions of x&prime / &prime / = f (t, x) (0.1) and the solutions 1 and t of x&prime / &prime / = 0. More specifically, the existence of a solution of (0.1) asymptotic to x(t) = at + b, a, b &isin / R has been obtained. In this thesis we investigate in a systematic way the asymptotic behavior as t &rarr / &infin / of solutions of a class of differential equations of the form (p(t)x&prime / )&prime / + q(t)x = f (t, x), t &ge / t_0 (0.2) and (p(t)x&prime / )&prime / + q(t)x = g(t, x, x&prime / ), t &ge / t_0 (0.3) by the help of principal u(t) and nonprincipal v(t) solutions of the corresponding homogeneous equation (p(t)x&prime / )&prime / + q(t)x = 0, t &ge / t_0. (0.4) Here, t_0 &ge / 0 is a real number, p &isin / C([t_0,&infin / ), (0,&infin / )), q &isin / C([t_0,&infin / ),R), f &isin / C([t_0,&infin / ) &times / R,R) and g &isin / C([t0,&infin / ) &times / R &times / R,R). Our argument is based on the idea of writing the solution of x&prime / &prime / = 0 in terms of principal and nonprincipal solutions as x(t) = av(t) + bu(t), where v(t) = t and u(t) = 1. In the proofs, Banach and Schauder&rsquo / s fixed point theorems are used. The compactness of the operator is obtained by employing the compactness criteria of Riesz and Avramescu. The thesis consists of three chapters. Chapter 1 is introductory and provides statement of the problem, literature review, and basic definitions and theorems. In Chapter 2 first we deal with some asymptotic relationships between the solutions of (0.2) and the principal u(t) and nonprincipal v(t) solutions of (0.4). Then we present existence of a monotone positive solution of (0.3) with prescribed asimptotic behavior. In Chapter 3 we introduce the existence of solution of a singular boundary value problem to the Equation (0.2).