Well-Posedness, Conditioning and Regularization of Minimization, Inclusion and Fixed-Point Problems

AMS subject classification: 65K10, 49M07, 90C25, 90C48.

Some Fixed Point Theorems for Kannan Mappings

2000 Mathematics Subject Classification: Primary: 47H10; Secondary: 54H25.

Quantization effects in the polyphase N-path IIR structure

Polyphase IIR structures have recently proven themselves very attractive for very high performance filters that can be designed using very few coefficients. This, combined with their low sensitivity to coefficient quantization in comparison to standard FIR and IIR structures, makes them very applicable for very fast filtering when implemented in fixed-point arithmetic. However, although the mathematical description is very simple, there exist a number of ways to implement such filters. In this paper, we take four of these different implementation structures, analyze the rounding noise originating from the limited arithmetic wordlength of the mathematical operators, and check the internal data growth within the structure. These analyses need to be done to ensure that the performance of the implementation matches the performance of the theoretical design. The theoretical approach that we present has been proven by the results of the fixed-point simulation done in Simulink and verified by an equivalent bit-true implementation in VHDL.

Contribuição para o estudo do embarque de uma rede neural artificial em field programmable gate array (FPGA)

This study shows the implementation and the embedding of an Artificial Neural Network (ANN) in hardware, or in a programmable device, as a field programmable gate array (FPGA). This work allowed the exploration of different implementations, described in VHDL, of multilayer perceptrons ANN. Due to the parallelism inherent to ANNs, there are disadvantages in software implementations due to the sequential nature of the Von Neumann architectures. As an alternative to this problem, there is a hardware implementation that allows to exploit all the parallelism implicit in this model. Currently, there is an increase in use of FPGAs as a platform to implement neural networks in hardware, exploiting the high processing power, low cost, ease of programming and ability to reconfigure the circuit, allowing the network to adapt to different applications. Given this context, the aim is to develop arrays of neural networks in hardware, a flexible architecture, in which it is possible to add or remove neurons, and mainly, modify the network topology, in order to enable a modular network of fixed-point arithmetic in a FPGA. Five synthesis of VHDL descriptions were produced: two for the neuron with one or two entrances, and three different architectures of ANN. The descriptions of the used architectures became very modular, easily allowing the increase or decrease of the number of neurons. As a result, some complete neural networks were implemented in FPGA, in fixed-point arithmetic, with a high-capacity parallel processing

DCM Boost interleaved converter for operation in AC and DC to trolleybus application

This paper is based on the development and experimental analysis of a DCM Boost interleaved converter suitable for application in traction systems of electrical vehicles pulled by electrical motors (Trolleybus), which are powered by urban DC or AC distribution networks. This front-end structure is capable of providing significant improvements in trolleybuses systems and in the urban distribution network costs, and efficiency. The architecture of proposed converter is composed by five boost power cells in interleaving connection, operating in discontinuous conduction mode. Furthermore, the converter can operate as AC-DC converter, or as DC-DC converter providing the proper DC output voltage range required by DC or AC adjustable speed drivers. Therefore, when supplied by single-phase AC distribution networks, and operating as AC-DC converter, it is capable to provide high power factor, reduced harmonic distortion in the input current, complying with the restrictions imposed by the IEC 61000-3-4 standards. The digital controller has been implemented using a low cost FPGA and developed totally using a hardware description language VHDL and fixed point arithmetic. Thus, two control strategies are evaluated considering the compliance with input current restrictions imposed by IEC 61000-3-4 standards, the regular PWM modulation and a current correction PWM modulation. In order to verify the feasibility and performance of the proposed system, experimental results from a 15 kW low power scale prototype are presented, operating in DC and AC conditions.

HPF boost interleaved operating in discontinuous conduction mode for trolleybus application

This paper deals with results of a research and development (R&D) project in cooperation with Electric Power Distribution Company in São Paulo (Brazil) regarding the development and experimental analysis of a new concept of power drive system suitable for application in traction systems of electrical vehicles pulled by electrical motors, which can be powered by urban DC or AC distribution networks. The proposed front-end structure is composed by five boost power cells in interleaving connection, operating in discontinuous conduction mode as AC-DC converter, or as DC-DC converter, in order to provide the proper DC output voltage range required by DC or AC adjustable speed drivers. Therefore, when supplied by single-phase AC distribution networks, and operating as AC-DC converter, it is capable to provide high power factor, reduced harmonic distortion in the input current, complying with the restrictions imposed by the IEC 61000-3-4 standards resulting in significant improvements for the trolleybuses systems efficiency and for the urban distribution network costs. Considering the compliance with input current restrictions imposed by IEC 61000-3-4 standards, two digital control strategies were evaluated. The digital controller has been implemented using a low cost FPGA (XC3S200) and developed totally using a hardware description language VHDL and fixed point arithmetic. Experimental results from a 15 kW low power scale prototype operating in DC and AC conditions are presented, in order to verify the feasibility and performance of the proposed system. © 2009 IEEE.

On a Microcomputer Implementation of an Intrusion-detection Algorithm

The main objective of this paper is to discuss various aspects of implementing a specific intrusion-detection scheme on a micro-computer system using fixed-point arithmetic. The proposed scheme is suitable for detecting intruder stimuli which are in the form of transient signals. It consists of two stages: an adaptive digital predictor and an adaptive threshold detection algorithm. Experimental results involving data acquired via field experiments are also included.

Automated wordlength optimization framework for multi-source statistical interval-based analysis of nonlinear systems with control-flow structures

El uso de aritmética de punto fijo es una opción de diseño muy extendida en sistemas con fuertes restricciones de área, consumo o rendimiento. Para producir implementaciones donde los costes se minimicen sin impactar negativamente en la precisión de los resultados debemos llevar a cabo una asignación cuidadosa de anchuras de palabra. Encontrar la combinación óptima de anchuras de palabra en coma fija para un sistema dado es un problema combinatorio NP-hard al que los diseñadores dedican entre el 25 y el 50 % del ciclo de diseño. Las plataformas hardware reconfigurables, como son las FPGAs, también se benefician de las ventajas que ofrece la aritmética de coma fija, ya que éstas compensan las frecuencias de reloj más bajas y el uso más ineficiente del hardware que hacen estas plataformas respecto a los ASICs. A medida que las FPGAs se popularizan para su uso en computación científica los diseños aumentan de tamaño y complejidad hasta llegar al punto en que no pueden ser manejados eficientemente por las técnicas actuales de modelado de señal y ruido de cuantificación y de optimización de anchura de palabra. En esta Tesis Doctoral exploramos distintos aspectos del problema de la cuantificación y presentamos nuevas metodologías para cada uno de ellos: Las técnicas basadas en extensiones de intervalos han permitido obtener modelos de propagación de señal y ruido de cuantificación muy precisos en sistemas con operaciones no lineales. Nosotros llevamos esta aproximación un paso más allá introduciendo elementos de Multi-Element Generalized Polynomial Chaos (ME-gPC) y combinándolos con una técnica moderna basada en Modified Affine Arithmetic (MAA) estadístico para así modelar sistemas que contienen estructuras de control de flujo. Nuestra metodología genera los distintos caminos de ejecución automáticamente, determina las regiones del dominio de entrada que ejercitarán cada uno de ellos y extrae los momentos estadísticos del sistema a partir de dichas soluciones parciales. Utilizamos esta técnica para estimar tanto el rango dinámico como el ruido de redondeo en sistemas con las ya mencionadas estructuras de control de flujo y mostramos la precisión de nuestra aproximación, que en determinados casos de uso con operadores no lineales llega a tener tan solo una desviación del 0.04% con respecto a los valores de referencia obtenidos mediante simulación. Un inconveniente conocido de las técnicas basadas en extensiones de intervalos es la explosión combinacional de términos a medida que el tamaño de los sistemas a estudiar crece, lo cual conlleva problemas de escalabilidad. Para afrontar este problema presen tamos una técnica de inyección de ruidos agrupados que hace grupos con las señales del sistema, introduce las fuentes de ruido para cada uno de los grupos por separado y finalmente combina los resultados de cada uno de ellos. De esta forma, el número de fuentes de ruido queda controlado en cada momento y, debido a ello, la explosión combinatoria se minimiza. También presentamos un algoritmo de particionado multi-vía destinado a minimizar la desviación de los resultados a causa de la pérdida de correlación entre términos de ruido con el objetivo de mantener los resultados tan precisos como sea posible. La presente Tesis Doctoral también aborda el desarrollo de metodologías de optimización de anchura de palabra basadas en simulaciones de Monte-Cario que se ejecuten en tiempos razonables. Para ello presentamos dos nuevas técnicas que exploran la reducción del tiempo de ejecución desde distintos ángulos: En primer lugar, el método interpolativo aplica un interpolador sencillo pero preciso para estimar la sensibilidad de cada señal, y que es usado después durante la etapa de optimización. En segundo lugar, el método incremental gira en torno al hecho de que, aunque es estrictamente necesario mantener un intervalo de confianza dado para los resultados finales de nuestra búsqueda, podemos emplear niveles de confianza más relajados, lo cual deriva en un menor número de pruebas por simulación, en las etapas iniciales de la búsqueda, cuando todavía estamos lejos de las soluciones optimizadas. Mediante estas dos aproximaciones demostramos que podemos acelerar el tiempo de ejecución de los algoritmos clásicos de búsqueda voraz en factores de hasta x240 para problemas de tamaño pequeño/mediano. Finalmente, este libro presenta HOPLITE, una infraestructura de cuantificación automatizada, flexible y modular que incluye la implementación de las técnicas anteriores y se proporciona de forma pública. Su objetivo es ofrecer a desabolladores e investigadores un entorno común para prototipar y verificar nuevas metodologías de cuantificación de forma sencilla. Describimos el flujo de trabajo, justificamos las decisiones de diseño tomadas, explicamos su API pública y hacemos una demostración paso a paso de su funcionamiento. Además mostramos, a través de un ejemplo sencillo, la forma en que conectar nuevas extensiones a la herramienta con las interfaces ya existentes para poder así expandir y mejorar las capacidades de HOPLITE. ABSTRACT Using fixed-point arithmetic is one of the most common design choices for systems where area, power or throughput are heavily constrained. In order to produce implementations where the cost is minimized without negatively impacting the accuracy of the results, a careful assignment of word-lengths is required. The problem of finding the optimal combination of fixed-point word-lengths for a given system is a combinatorial NP-hard problem to which developers devote between 25 and 50% of the design-cycle time. Reconfigurable hardware platforms such as FPGAs also benefit of the advantages of fixed-point arithmetic, as it compensates for the slower clock frequencies and less efficient area utilization of the hardware platform with respect to ASICs. As FPGAs become commonly used for scientific computation, designs constantly grow larger and more complex, up to the point where they cannot be handled efficiently by current signal and quantization noise modelling and word-length optimization methodologies. In this Ph.D. Thesis we explore different aspects of the quantization problem and we present new methodologies for each of them: The techniques based on extensions of intervals have allowed to obtain accurate models of the signal and quantization noise propagation in systems with non-linear operations. We take this approach a step further by introducing elements of MultiElement Generalized Polynomial Chaos (ME-gPC) and combining them with an stateof- the-art Statistical Modified Affine Arithmetic (MAA) based methodology in order to model systems that contain control-flow structures. Our methodology produces the different execution paths automatically, determines the regions of the input domain that will exercise them, and extracts the system statistical moments from the partial results. We use this technique to estimate both the dynamic range and the round-off noise in systems with the aforementioned control-flow structures. We show the good accuracy of our approach, which in some case studies with non-linear operators shows a 0.04 % deviation respect to the simulation-based reference values. A known drawback of the techniques based on extensions of intervals is the combinatorial explosion of terms as the size of the targeted systems grows, which leads to scalability problems. To address this issue we present a clustered noise injection technique that groups the signals in the system, introduces the noise terms in each group independently and then combines the results at the end. In this way, the number of noise sources in the system at a given time is controlled and, because of this, the combinato rial explosion is minimized. We also present a multi-way partitioning algorithm aimed at minimizing the deviation of the results due to the loss of correlation between noise terms, in order to keep the results as accurate as possible. This Ph.D. Thesis also covers the development of methodologies for word-length optimization based on Monte-Carlo simulations in reasonable times. We do so by presenting two novel techniques that explore the reduction of the execution times approaching the problem in two different ways: First, the interpolative method applies a simple but precise interpolator to estimate the sensitivity of each signal, which is later used to guide the optimization effort. Second, the incremental method revolves on the fact that, although we strictly need to guarantee a certain confidence level in the simulations for the final results of the optimization process, we can do it with more relaxed levels, which in turn implies using a considerably smaller amount of samples, in the initial stages of the process, when we are still far from the optimized solution. Through these two approaches we demonstrate that the execution time of classical greedy techniques can be accelerated by factors of up to ×240 for small/medium sized problems. Finally, this book introduces HOPLITE, an automated, flexible and modular framework for quantization that includes the implementation of the previous techniques and is provided for public access. The aim is to offer a common ground for developers and researches for prototyping and verifying new techniques for system modelling and word-length optimization easily. We describe its work flow, justifying the taken design decisions, explain its public API and we do a step-by-step demonstration of its execution. We also show, through an example, the way new extensions to the flow should be connected to the existing interfaces in order to expand and improve the capabilities of HOPLITE.

Design and implementation of generalized topologies of time-interleaved variable bandpass Σ−Δ modulators

In this thesis, novel analog-to-digital and digital-to-analog generalized time-interleaved variable bandpass sigma-delta modulators are designed, analysed, evaluated and implemented that are suitable for high performance data conversion for a broad-spectrum of applications. These generalized time-interleaved variable bandpass sigma-delta modulators can perform noise-shaping for any centre frequency from DC to Nyquist. The proposed topologies are well-suited for Butterworth, Chebyshev, inverse-Chebyshev and elliptical filters, where designers have the flexibility of specifying the centre frequency, bandwidth as well as the passband and stopband attenuation parameters. The application of the time-interleaving approach, in combination with these bandpass loop-filters, not only overcomes the limitations that are associated with conventional and mid-band resonator-based bandpass sigma-delta modulators, but also offers an elegant means to increase the conversion bandwidth, thereby relaxing the need to use faster or higher-order sigma-delta modulators. A step-by-step design technique has been developed for the design of time-interleaved variable bandpass sigma-delta modulators. Using this technique, an assortment of lower- and higher-order single- and multi-path generalized A/D variable bandpass sigma-delta modulators were designed, evaluated and compared in terms of their signal-to-noise ratios, hardware complexity, stability, tonality and sensitivity for ideal and non-ideal topologies. Extensive behavioural-level simulations verified that one of the proposed topologies not only used fewer coefficients but also exhibited greater robustness to non-idealties. Furthermore, second-, fourth- and sixth-order single- and multi-path digital variable bandpass digital sigma-delta modulators are designed using this technique. The mathematical modelling and evaluation of tones caused by the finite wordlengths of these digital multi-path sigmadelta modulators, when excited by sinusoidal input signals, are also derived from first principles and verified using simulation and experimental results. The fourth-order digital variable-band sigma-delta modulator topologies are implemented in VHDL and synthesized on Xilinx® SpartanTM-3 Development Kit using fixed-point arithmetic. Circuit outputs were taken via RS232 connection provided on the FPGA board and evaluated using MATLAB routines developed by the author. These routines included the decimation process as well. The experiments undertaken by the author further validated the design methodology presented in the work. In addition, a novel tunable and reconfigurable second-order variable bandpass sigma-delta modulator has been designed and evaluated at the behavioural-level. This topology offers a flexible set of choices for designers and can operate either in single- or dual-mode enabling multi-band implementations on a single digital variable bandpass sigma-delta modulator. This work is also supported by a novel user-friendly design and evaluation tool that has been developed in MATLAB/Simulink that can speed-up the design, evaluation and comparison of analog and digital single-stage and time-interleaved variable bandpass sigma-delta modulators. This tool enables the user to specify the conversion type, topology, loop-filter type, path number and oversampling ratio.

Effect of inter-edge Coulomb interactions on transport through a point contact in nu=5/2 quantum Hall state

We study transport across a point contact separating two line junctions in a nu = 5/2 quantum Hall system. We analyze the effect of inter-edge Coulomb interactions between the chiral bosonic edge modes of the half-filled Landau level (assuming a Pfaffian wave function for the half-filled state) and of the two fully filled Landau levels. In the presence of inter-edge Coulomb interactions between all the six edges participating in the line junction, we show that the stable fixed point corresponds to a point contact that is neither fully opaque nor fully transparent. Remarkably, this fixed point represents a situation where the half-filled level is fully transmitting, while the two filled levels are completely backscattered; hence the fixed point Hall conductance is given by G(H) = 1/2e(2)/h. We predict the non-universal temperature power laws by which the system approaches the stable fixed point from the two unstable fixed points corresponding to the fully connected case (G(H) = 5/2e(2)/h) and the fully disconnected case (G(H) = 0).

Quantum Algorithms with Fixed Points: The Case of Database Search

The standard quantum search algorithm lacks a feature, enjoyed by many classical algorithms, of having a fixed-point, i.e. a monotonic convergence towards the solution. Here we present two variations of the quantum search algorithm, which get around this limitation. The first replaces selective inversions in the algorithm by selective phase shifts of $\frac{\pi}{3}$. The second controls the selective inversion operations using two ancilla qubits, and irreversible measurement operations on the ancilla qubits drive the starting state towards the target state. Using $q$ oracle queries, these variations reduce the probability of finding a non-target state from $\epsilon$ to $\epsilon^{2q+1}$, which is asymptotically optimal. Similar ideas can lead to robust quantum algorithms, and provide conceptually new schemes for error correction.

Coincidence point theorems in quasi-metric spaces without assuming the mixed monotone property and consequences in G-metric spaces

In this paper, we present some coincidence point theorems in the setting of quasi-metric spaces that can be applied to operators which not necessarily have the mixed monotone property. As a consequence, we particularize our results to the field of metric spaces, partially ordered metric spaces and G-metric spaces, obtaining some very recent results. Finally, we show how to use our main theorems to obtain coupled, tripled, quadrupled and multidimensional coincidence point results.

Common Fixed Points of Generalized Rational Type Cocyclic Mappings in Multiplicative Metric Spaces

The aim of this paper is to present fixed point result of mappings satisfying a generalized rational contractive condition in the setup of multiplicative metric spaces. As an application, we obtain a common fixed point of a pair of weakly compatible mappings. Some common fixed point results of pair of rational contractive types mappings involved in cocyclic representation of a nonempty subset of a multiplicative metric space are also obtained. Some examples are presented to support the results proved herein. Our results generalize and extend various results in the existing literature.

Pata contractions and coupled type fixed points

A new coupled fixed point theorem related to the Pata contraction for mappings having the mixed monotone property in partially ordered complete metric spaces is established. It is shown that the coupled fixed point can be unique under some extra suitable conditions involving mid point lower or upper bound properties. Also the corresponding convergence rate is estimated when the iterates of our function converge to its coupled fixed point.

On contractive cyclic fuzzy maps in metric spaces and some related results on fuzzy best proximity points and fuzzy fixed points

This paper investigates some properties of cyclic fuzzy maps in metric spaces. The convergence of distances as well as that of sequences being generated as iterates defined by a class of contractive cyclic fuzzy mapping to fuzzy best proximity points of (non-necessarily intersecting adjacent subsets) of the cyclic disposal is studied. An extension is given for the case when the images of the points of a class of contractive cyclic fuzzy mappings restricted to a particular subset of the cyclic disposal are allowed to lie either in the same subset or in its next adjacent one.