This thesis introduces a novel application of factor graphs to the domain of analog circuits. It proposes a technique of leveraging factor graphs for performing statistical yield analysis of analog circuits that is much faster than the standard Monte Carlo/Simulation Program With Integrated Circuit Emphasis (SPICE) simulation techniques. We have designed a tool chain to model an analog circuit and its corresponding factor graph and then use a Gaussian message passing approach along the edges of the graph for yield calculation. The tool is also capable of estimating unknown parameters of the circuit given known output statistics through backward message propagation in the factor graph. The tool builds upon the concept of domain-specific modeling leveraged for modeling and interpreting different kinds of analog circuits. Generic Modeling Environment (GME) is used to design modeling environment for analog circuits. It is a configurable tool set that supports creation of domain-specific design environments for different applications. This research has developed a generalized methodology that could be applied towards design automation of different kinds of analog circuits, both linear and nonlinear. The tool has been successfully used to model linear amplifier circuits and a nonlinear Metal Oxide Semiconductor Field Effect Transistor (MOSFET) circuit. The results obtained by Monte Carlo simulations performed on these circuits are used as a reference in the project to compare against the tool's results. The tool is tested for its efficiency in terms of time and accuracy against the standard results.

As wireless communication systems continue to push the limits of energy and spectral efficiency, increased demands are placed on the capabilities of the receiver. At the same time, the computational resources available for processing received signals will continue to grow. This opens the door for iterative algorithms to play an increasing role in the next generation of communication receivers. In the context of receivers, the goal of iterative probabilistic processing is to approximate maximum a posteriori (MAP) symbol-by-symbol detection of the information bits and estimation of the unknown channel or signal parameters. The sum-product algorithm is capable of efficiently approximating the marginal posterior probabilities desired for MAP detection and provides a unifying framework for the development of iterative receiver algorithms. However, in some applications the sum-product algorithm is computationally infeasible. Specifically, this is the case when both continuous and discrete parameters are present within the model. Also, the complexity of the sum-product algorithm is exponential in the number of variables connected to a particular factor node and can be prohibitive in multi-user and multi-antenna applications. In this dissertation we identify three key problems which can benefit from iterative probabilistic processing, but for which the sum-product algorithm is too complex. They are (1) joint synchronization and detection in multipath channels with emphasis on frame timing, (2) detection in co-channel interference and non-Gaussian noise, and (3) joint channel estimation and multi-signal detection. This dissertation presents the advances we have made in iterative probabilistic processing in order to tackle these problems. The motivation behind the work is to (a) compromise as little as possible on the performance that is achieved while limiting the computational complexity and (b) maintain good theoretical justification to the algorithms that are developed. / Ph. D.

Wireless sensor networks (WSNs) consist of a large number of sensor nodes, capable of on-board sensing and data processing, that are employed to observe some phenomenon of interest. With their desirable properties of flexible deployment, resistance to harsh environment and lower implementation cost, WSNs envisage a plethora of applications in diverse areas such as industrial process control, battle- field surveillance, health monitoring, and target localization and tracking. Much of the sensing and communication paradigm in WSNs involves ensuring power efficient transmission and finding scalable algorithms that can deliver the desired performance objectives while minimizing overall energy utilization. Since power is primarily consumed in radio transmissions delivering timing information, clock synchronization represents an indispensable requirement to boost network lifetime. This dissertation focuses on deriving efficient estimators and performance bounds for the clock parameters in a classical frequentist inference approach as well as in a Bayesian estimation framework. A unified approach to the maximum likelihood (ML) estimation of clock offset is presented for different network delay distributions. This constitutes an analytical alternative to prior works which rely on a graphical maximization of the likelihood function. In order to capture the imperfections in node oscillators, which may render a time-varying nature to the clock offset, a novel Bayesian approach to the clock offset estimation is proposed by using factor graphs. Message passing using the max-product algorithm yields an exact expression for the Bayesian inference problem. This extends the current literature to cases where the clock offset is not deterministic, but is in fact a random process. A natural extension of pairwise synchronization is to develop algorithms for the more challenging case of network-wide synchronization. Assuming exponentially distributed random delays, a network-wide clock synchronization algorithm is proposed using a factor graph representation of the network. Message passing using the max- product algorithm is adopted to derive the update rules for the proposed iterative procedure. A closed form solution is obtained for each node's belief about its clock offset at each iteration. Identifying the close connections between the problems of node localization and clock synchronization, we also address in this dissertation the problem of joint estimation of an unknown node's location and clock parameters by incorporating the effect of imperfections in node oscillators. In order to alleviate the computational complexity associated with the optimal maximum a-posteriori estimator, two iterative approaches are proposed as simpler alternatives. The first approach utilizes an Expectation-Maximization (EM) based algorithm which iteratively estimates the clock parameters and the location of the unknown node. The EM algorithm is further simplified by a non-linear processing of the data to obtain a closed form solution of the location estimation problem using the least squares (LS) approach. The performance of the estimation algorithms is benchmarked by deriving the Hybrid Cramer-Rao lower bound (HCRB) on the mean square error (MSE) of the estimators. We also derive theoretical lower bounds on the MSE of an estimator in a classical frequentist inference approach as well as in a Bayesian estimation framework when the likelihood function is an arbitrary member of the exponential family. The lower bounds not only serve to compare various estimators in our work, but can also be useful in their own right in parameter estimation theory.

This thesis introduces normal factor graphs under a new semantics, namely, the exterior function semantics. Initially, this work was motivated by two distinct lines of research. One line is ``holographic algorithms,'' a powerful approach introduced by Valiant for solving various counting problems in computer science; the other is ``normal graphs,'' an elegant framework proposed by Forney for representing codes defined on graphs. The nonrestrictive normality constraint enables the notion of holographic transformations for normal factor graphs. We establish a theorem, called the generalized Holant theorem, which relates a normal factor graph to its holographic transformation. We show that the generalized Holant theorem on one hand underlies the principle of holographic algorithms, and on the other reduces to a general duality theorem for normal factor graphs, a special case of which was first proved by Forney. As an application beyond Forney's duality, we show that the normal factor graphs duality facilitates the approximation of the partition function for the two-dimensional nearest-neighbor Potts model. In the course of our development, we formalize a new semantics for normal factor graphs, which highlights various linear algebraic properties that enables the use of normal factor graphs as a linear algebraic tool. Indeed, we demonstrate the ability of normal factor graphs to encode several concepts from linear algebra and present normal factor graphs as a generalization of ``trace diagrams.'' We illustrate, with examples, the workings of this framework and how several identities from linear algebra may be obtained using a simple graphical manipulation procedure called ``vertex merging/splitting.'' We also discuss translation association schemes with the aid of normal factor graphs, which we believe provides a simple approach to understanding the subject. Further, under the new semantics, normal factor graphs provide a probabilistic model that unifies several graphical models such as factor graphs, convolutional factor graphs, and cumulative distribution networks.

This thesis introduces normal factor graphs under a new semantics, namely, the exterior function semantics. Initially, this work was motivated by two distinct lines of research. One line is ``holographic algorithms,'' a powerful approach introduced by Valiant for solving various counting problems in computer science; the other is ``normal graphs,'' an elegant framework proposed by Forney for representing codes defined on graphs. The nonrestrictive normality constraint enables the notion of holographic transformations for normal factor graphs. We establish a theorem, called the generalized Holant theorem, which relates a normal factor graph to its holographic transformation. We show that the generalized Holant theorem on one hand underlies the principle of holographic algorithms, and on the other reduces to a general duality theorem for normal factor graphs, a special case of which was first proved by Forney. As an application beyond Forney's duality, we show that the normal factor graphs duality facilitates the approximation of the partition function for the two-dimensional nearest-neighbor Potts model. In the course of our development, we formalize a new semantics for normal factor graphs, which highlights various linear algebraic properties that enables the use of normal factor graphs as a linear algebraic tool. Indeed, we demonstrate the ability of normal factor graphs to encode several concepts from linear algebra and present normal factor graphs as a generalization of ``trace diagrams.'' We illustrate, with examples, the workings of this framework and how several identities from linear algebra may be obtained using a simple graphical manipulation procedure called ``vertex merging/splitting.'' We also discuss translation association schemes with the aid of normal factor graphs, which we believe provides a simple approach to understanding the subject. Further, under the new semantics, normal factor graphs provide a probabilistic model that unifies several graphical models such as factor graphs, convolutional factor graphs, and cumulative distribution networks.

The most commonly used localisation methods, such as GPS, rely on external signals to generate an estimate of the location. There is a need of systems which are independent of external signals in order to increase the robustness of the localisation capabilities. In this thesis a visual-inertial SLAM-based localisation system which utilises detailed map, image, IMU, and odometry data, is presented and evaluated. The system utilises factor graphs through Georgia Tech Smoothing and Mapping (GTSAM) library, developed at the Georgia Institute of Technology. The thesis contributes with performance evaluations for different camera and landmark settings in a localisation system based on GTSAM. Within the visual SLAM field, the thesis also contributes with a sparse landmark selection and a low image frequency approach to the localisation problem. A variety of camera-related settings, such as image frequency and amount of visible landmarks per image, are used to evaluate the system. The findings show that the estimate improve with a higher image frequency, and does also improve if the image frequency was held constant along the tracks. Having more than one landmark per image result in a significantly better estimate. The estimate is not accurate when only using one distant landmark throughout the track, but it is significantly better if two complementary landmarks are identified briefly along the tracks. The estimate can also handle time periods where no landmarks can be identified while maintaining a good estimate.

This thesis addresses the problem of inference in factor graphs, especially the LDPC codes, almost solved by message-passing algorithms. In particular, the Belief Propagation algorithm (BP) is investigated as a particular message-passing algorithm whose suboptimality is discussed in the case where the factor graph has a loop-like topology. From the equivalence between the BP and the Bethe approximation in statistical physics that is generalized to the region-based approximation, is detailed the Generalized Belief Propagation algorithm (GBP), a message-passing algorithm between clusters of the factor graph. It is experimentally shown to surpass the BP in the cases where the clustering deals with the harmful topological structures that prevents the BP from rightly decoding any LDPC code, namely the trapping sets. We do not only confront the BP and the GBP algorithms according to their performance from the point of view of the channel coding with the error-rate, but also according to their dynamical behaviors for non-trivial error-events for which both algorithms can exhibit chaotic beahviors. By means of classical and original dynamical quantifiers, it is shown that the GBP algorithm can overcome the BP algorithm.

Orientador: Jaime Portugheis / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T20:11:55Z (GMT). No. of bitstreams: 1 Cunha_DanielCarvalhoda_D.pdf: 2995961 bytes, checksum: 3bbce0e569994999c363151f6510cef1 (MD5) Previous issue date: 2006 / Resumo: Em varios sistemas de transmissão passa-faixa, uma recepção coerente satisfatória é dificil de ser alcancada. Para alguns destes sistemas, é comum supor que a rotaçãoo de fase introduzida pelo canal é constante durante um bloco de L simbolos e que ela varia de maneira independente de bloco a bloco. Este canal é denominado canal não-coerente de bloco. Investigamos a capacidade de um canal não-coerente de bloco utilizando a modulação M-APSK (do inglês, M-ary Amplitude Phase Shift Keying). Apresentamos a caracterização da distribuição de entrada que atinge a capacidade e obtivemos limitantes superiores e inferiores para a mesma. Adicionalmente, desenvolvemos um algoritmo que simultaneamente fornece a distribuição de entrada e os parametros da modulação M-APSK que maximizam a informação mutua com recepção coerente. A investigação da capacidade mostrou que o aumento de L faz a capacidade não-coerente convergir para a coerente. Alem disso, o uso de codificação diferencial torna a convergência mais rapida. Motivados por este comportamento, apresentamos um esquema de codificação eficiente em faixa. Este esquema é formado pela concatenação serial de um codigo LDPC (do ingles, Low-Density Parity Check ), um entrela¸cador e um codificador diferencial. Para o esquema apresentado, o receptor iterativo é descrito por um grafo-fator. Os desempenhos do esquema com diferentes tamanhos de codigos LDPC são comparados / Abstract: Coherent reception is not possible for many bandpass transmission systems. In some of these systems, it is commonly assumed that the unknown carrier phase rotation is constant over a block of L symbols and it is independent from block to block. This channel is denominated blockwise noncoherent channel. The blockwise noncoherent channel capacity using M-ary Amplitude and Phase Shift Keying (M-APSK) modulation is investigated. The characterization of the input distribution achieving capacity is presented. Upper and lower bounds to this capacity are derived. In addition, an algorithm for simultaneously computing the input distribution and the M-APSK constellation parameters which maximizes the mutual information with coherent reception is developed. The investigation of the capacity showed that as L increases, the noncoherent capacity converges to the coherent one. Besides that, the use of differential encoding makes this convergence faster. Motivated by this fact, a bandwidth efficient coding scheme is presented. This scheme is composed of a serial concatenation of a Low-Density Parity Check (LDPC) code, an interleaver, and a differential encoder. For this scheme, the iterative receiver is described by a factor graph. The scheme performances for different lengths of LDPC codes are compared. / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica

Dans cette thèse, nous étudions le problème de l'inférence bayésienne dans les graphes factoriels, en particulier les codes LDPC, quasiment résolus par les algorithmes de message-passing. Nous réalisons en particulier une étude approfondie du Belief Propagation (BP) dont la question de la sous-optimalité est soulevée dans le cas où le graphe factoriel présente des boucles. A partir de l'équivalence entre le BP et l'approximation de Bethe en physique statistique qui se généralise à l'approximation basée régions, nous détaillons le Generalized Belief Propagation (GBP), un algorithme de message-passing entre des clusters du graphe factoriel. Nous montrons par des expériences que le GBP surpasse le BP dans les cas où le clustering est réalisé selon les structures topologiques néfastes qui empêchent le BP de bien décoder, à savoir les trapping sets. Au-delà de l'étude des performances en termes de taux d'erreur, nous confrontons les deux algorithmes par rapport à leurs dynamiques face à des événements d'erreur non triviaux, en particulier lorsqu'ils présentent des comportements chaotiques. Par des estimateurs classiques et originaux, nous montrons que l'algorithme du GBP peut dominer l'algorithme du BP. / This thesis addresses the problem of inference in factor graphs, especially the LDPC codes, almost solved by message-passing algorithms. In particular, the Belief Propagation algorithm (BP) is investigated as a particular message-passing algorithm whose suboptimality is discussed in the case where the factor graph has a loop-like topology. From the equivalence between the BP and the Bethe approximation in statistical physics that is generalized to the region-based approximation, is detailed the Generalized Belief Propagation algorithm (GBP), a message-passing algorithm between clusters of the factor graph. It is experimentally shown to surpass the BP in the cases where the clustering deals with the harmful topological structures that prevents the BP from rightly decoding any LDPC code, namely the trapping sets. We do not only confront the BP and the GBP algorithms according to their performance from the point of view of the channel coding with the error-rate, but also according to their dynamical behaviors for non-trivial error-events for which both algorithms can exhibit chaotic beahviors. By means of classical and original dynamical quantifiers, it is shown that the GBP algorithm can overcome the BP algorithm.

<p>We present a detailed study on application of factor<br />graphs and the belief propagation (BP) algorithm to the<br />power system state estimation (SE) problem. We start<br />from the BP solution for the linear DC model, for which<br />we provide a detailed convergence analysis. Using BPbased<br />DC model we propose a fast real-time state<br />estimator for the power system SE. The proposed<br />estimator is easy to distribute and parallelize, thus<br />alleviating computational limitations and allowing for<br />processing measurements in real time. The presented<br />algorithm may run as a continuous process, with each<br />new measurement being seamlessly processed by the<br />distributed state estimator. In contrast to the matrixbased<br />SE methods, the BP approach is robust to illconditioned<br />scenarios caused by significant differences<br />between measurement variances, thus resulting in a<br />solution that eliminates observability analysis. Using the<br />DC model, we numerically demonstrate the performance<br />of the state estimator in a realistic real-time system<br />model with asynchronous measurements. We note that<br />the extension to the non-linear SE is possible within the<br />same framework.<br />Using insights from the DC model, we use two different<br />approaches to derive the BP algorithm for the non-linear<br />model. The first method directly applies BP methodology,<br />however, providing only approximate BP solution for the<br />non-linear model. In the second approach, we make a key<br />further step by providing the solution in which the BP is<br />applied sequentially over the non-linear model, akin to<br />what is done by the Gauss-Newton method. The resulting<br />iterative Gauss-Newton belief propagation (GN-BP)<br />algorithm can be interpreted as a distributed Gauss-<br />Newton method with the same accuracy as the<br />centralized SE, however, introducing a number of<br />advantages of the BP framework. The thesis provides<br />extensive numerical study of the GN-BP algorithm,<br />provides details on its convergence behavior, and gives a<br />number of useful insights for its implementation.<br />Finally, we define the bad data test based on the BP<br />algorithm for the non-linear model. The presented model<br />establishes local criteria to detect and identify bad data<br />measurements. We numerically demonstrate that the<br />BP-based bad data test significantly improves the bad<br />data detection over the largest normalized residual test.</p> / <p>Glavni rezultati ove teze su dizajn i analiza novih<br />algoritama za re&scaron;avanje problema estimacije stanja<br />baziranih na faktor grafovima i &bdquo;Belief Propagation&ldquo; (BP)<br />algoritmu koji se mogu primeniti kao centralizovani ili<br />distribuirani estimatori stanja u elektroenergetskim<br />sistemima. Na samom početku, definisan je postupak za<br />re&scaron;avanje linearnog (DC) problema kori&scaron;ćenjem BP<br />algoritma. Pored samog algoritma data je analiza<br />konvergencije i predloženo je re&scaron;enje za unapređenje<br />konvergencije. Algoritam se može jednostavno<br />distribuirati i paralelizovati, te je pogodan za estimaciju<br />stanja u realnom vremenu, pri čemu se informacije mogu<br />prikupljati na asinhroni način, zaobilazeći neke od<br />postojećih rutina, kao npr. provera observabilnosti<br />sistema. Pro&scaron;irenje algoritma za nelinearnu estimaciju<br />stanja je moguće unutar datog modela.<br />Dalje se predlaže algoritam baziran na probabilističkim<br />grafičkim modelima koji je direktno primenjen na<br />nelinearni problem estimacije stanja, &scaron;to predstavlja<br />logičan korak u tranziciji od linearnog ka nelinearnom<br />modelu. Zbog nelinearnosti funkcija, izrazi za određenu<br />klasu poruka ne mogu se dobiti u zatvorenoj formi, zbog<br />čega rezultujući algoritam predstavlja aproksimativno<br />re&scaron;enje. Nakon toga se predlaže distribuirani Gaus-<br />Njutnov metod baziran na probabilističkim grafičkim<br />modelima i BP algoritmu koji postiže istu tačnost kao i<br />centralizovana verzija Gaus-Njutnovog metoda za<br />estimaciju stanja, te je dat i novi algoritam za otkrivanje<br />nepouzdanih merenja (outliers) prilikom merenja<br />električnih veličina. Predstavljeni algoritam uspostavlja<br />lokalni kriterijum za otkrivanje i identifikaciju<br />nepouzdanih merenja, a numerički je pokazano da<br />algoritam značajno pobolj&scaron;ava detekciju u odnosu na<br />standardne metode.</p>