Luận án Analog Logic: Mạch Tín hiệu Liên tục cho Xử lý Tín hiệu Thống kê - Benjamin Vigoda

Analog Logic: Continuous-Time Analog Circuits for Statistical Signal Processing by Benjamin Vigoda Submitted to the Program in Media Arts and Sciences, School of Architecture and Planning in partial fulfillment of the requirements for the degree of Doctor of Philosophy at the MASSACHUSETTS INSTITUTE OF TECHNOLOGY September 2003 c Massachusetts Institute of Technology 2003. All rights reserved. Program in Media Arts and Sciences, School of Architecture and Planning August 15, 2003 Certified by. Neil Gershenfeld Associate Professor Thesis Supervisor Accepted by.

Lippman Chair, Department Committee on Graduate Students 2 Analog Logic: Continuous-Time Analog Circuits for Statistical Signal Processing by Benjamin Vigoda Submitted to the Program in Media Arts and Sciences, School of Architecture and Planning on August 15, 2003, in partial fulfillment of the requirements for the degree of Doctor of Philosophy Abstract This thesis proposes an alternate paradigm for designing computers using continuous- time analog circuits. Digital computation sacrifices continuous degrees of freedom. A principled approach to recovering them is to view analog circuits as propagat- ing probabilities in a message passing algorithm. Within this framework, analog continuous-time circuits can perform robust, programmable, high-speed, low-power, cost-effective, statistical signal processing.

This methodology will have broad appli- cation to systems which can benefit from low-power, high-speed signal processing and offers the possibility of adaptable/programmable high-speed circuitry at frequencies where digital circuitry would be cost and power prohibitive. Many problems must be solved before the new design methodology can be shown to be useful in practice: Continuous-time signal processing is not well understood. Analog computational circuits known as “soft-gates” have been previously proposed, but a complementary set of analog memory circuits is still lacking. Analog circuits are usually tunable, rarely reconfigurable, but never programmable.

The thesis develops an understanding of the convergence and synchronization of statistical signal processing algorithms in continuous time, and explores the use of linear and nonlinear circuits for analog memory. An exemplary embodiment called the Noise Lock Loop (NLL) using these design primitives is demonstrated to perform direct-sequence spread-spectrum acquisition and tracking functionality and promises order-of-magnitude wins over digital implementations. A building block for the con- struction of programmable analog gate arrays, the “soft-multiplexer” is also pro- posed. Thesis Supervisor: Neil Gershenfeld Title: Associate Professor 3 4 Hans-Andrea Loeliger Thesis Reader Professor of Signal Processing Signal Processing Laboratory of ETH Zurich, Switzerland 5 6 Anantha Chandrakasan Thesis Reader Professor Department of Electrical Engineering and Computer Science, MIT Jonathan Yedidia Thesis Reader Research Scientist Mitsubishi Electronics Research Laboratory Cambridge, MA 7 8 Acknowledgments Thank you to the Media Lab for having provided the most interesting context possible in which to conduct research.

Thank you to Neil Gershenfeld for providing me with the direction opportunity to study what computation means when it is analog and continuous-time; a problem which has intrigued me since I was 13 years old. Thank you to my committee, Anantha Chandrakasan, Hans-Andrea Loeliger, and Jonathan Yedidia for their invaluable support and guidance in finishing the dissertation. Thank you to professor Loeliger’s group at ETH in Zurich, Switzerland for many of the ideas which provide prior art for this thesis, for your support, and especially for your shared love for questions of time and synchronization. Thank you to the Physics and Media Group for teaching me how to make things and to our fearless administrators Susan Bottari and Mike Houlihan for their work which was crucial to the completion of the physical implementations described herein.

Thank you to Bernd Schoner for being a role model and to Matthias Frey, Justin Dauwels, and Yael Maguire for your collaboration and suggestions. Thank you to Saul Griffith, Jon Feldman, and Yael Maguire for your true friend- ship and camaraderie in the deep deep trenches of graduate school. Thank you to Bret Bjurstrom, Dan Paluska, Chuck Kemp, Nancy Loedy, Shawn Hershey, Dan Overholt, John Rice, Rob McCuen and the Flying Karamazov Brothers, Howard, Kristina, Mark, Paul and Rod for putting on the show. Thank you to my parents for all of the usual reasons and then some.

Much of the financial resources for this thesis were provided through the Center for Bits and Atoms NSF research grant number NSF CCR-0122419.1 A New Way to Build Computers .1 Digital Scaling Limits .2 Analog Scaling Limits .2 Statistical Inference and Signal Processing .3 Application: Wireless Transceivers .4 Road-map: Statistical Signal Processing by Simple Physical Systems .5 Analog Continuous-Time Distributed Computing .1 Analog VLSI Circuits for Statistical Inference .2 Analog, Un-clocked, Distributed Computing .1 Entrainment for Synchronization .2 Neuromorphic and Translinear Circuits. 43 2 Probabilistic Message Passing on Graphs 47 2.1 The Uses of Graphical Models .1 Graphical Models for Representing Probability Distributions .2 Graphical Models in Different Fields .3 Factor Graphs for Engineering Complex Computational Systems 50 2.4 Application to Signal Processing .2 Review of the Mathematics of Probability .2 Bayes’ Rule and Conditional Probability Distributions .4 Computing Marginal Probabilities .3 Factor Graph Tutorial .2 Factor Graphs Represent a Factorized Probability Distribution 57 2.4 General Soft-gates .5 Marginalization on a Tree: The Message Passing Metaphor .6 Marginalization on Tree: Variable Nodes Multiply Incoming Messages .8 Graphs with Cycles .4 Probabilistic Message Passing on Graphs .1 A Lower Complexity Way to Compute Marginal Probabilities 66 2.2 The Sum-Product Algorithm .5 Other Kinds of Probabilistic Graphical Models .2 Markov Random Fields .4 Forney Factor Graphs (FFG) .5 Circuit Schematic Diagrams .6 Equivalence of Probabilistic Graphical Models .6 Representations of Messages: Likelihood Ratio and Log-likelihood Ratio 79 2.1 Log-Likelihood Formulation of the Soft-Equals .2 Log-Likelihood Formulation of the Soft-xor .7 Derivation of Belief Propagation from Variational Methods. 81 12 3 Examples of Probabilistic Message Passing on Graphs 83 3.2 Soft Hamming Decoder .2 Decoding with Sum Product Algorithm .3 Optimization of Probabilistic Routing Tables in an Adhoc Peer-to-Peer Network. 93 4 Synchronization as Probabilistic Message Passing on a Graph 101 4.1 The Ring Oscillator .1 Trellis Decoding for Ring Oscillator Synchronization .2 Forward-only Message Passing on the Ring Oscillator Trellis .2 Synchronization to a Linear Feedback Shift Register (LFSR) .1 LFSRs Generate PN-Sequences .2 Applications of LFSR Synchronization .3 Maximum Likelihood LFSR Acquisition .1 Trellis for Maximum-Likelihood LFSR Synchronization .2 Converting a the Trellis to a Factor Graph .3 The Sum Product (Forward-Backward) Algorithm on the LFSR Trellis .4 The Max Product (Viterbi’s) Algorithm .4 Low-Complexity LFSR Acquisition .1 The LFSR Shift Graph .2 “Rolling Up the Shift Graph: The Noise Lock Loop .3 Performance of the Noise Lock Loop (NLL) .5 Joint Marginals Generalize Between the NLL and the trellis.

127 5 Analog VLSI Circuits for Probabilistic Message Passing 131 5.1 Introduction: The Need for Multipliers .2 Multipliers Require Active Elements .3 Active Elements Integrated in Silicon: Transistors .4 Single-Quadrant Multiplier Circuits .1 Multiply by Summing Logarithms .2 Multiply by Controlling Gain: The Differential Pair .5 General Theory of Multiplier Circuits .2 The Translinear Principle .3 Companding Current-Mirror Inputs .7 Figures of Merit .1 Resolution and Power Consumption of Soft-Gates at 1GHz. 151 6 The Sum Product Algorithm in Continuous-Time 155 6.1 Differential Message Passing .2 Von Neuman Stability Analysis of Finite Differences .3 Filtering Probabilities and Likelihoods is Equivalent to Damping160 6.4 Filtering Log-Likelihoods .2 Analog Memory Circuits for Continuous-Time Implementation .1 Active Low-Pass Filters .3 Continuous-Time Dynamical Systems .1 Simple Harmonic Oscillators .3 Continuous-Time LFSR Signal Generator .4 Continuous-Time Synchronization by Injection Locking as Statistical Estimation .1 Synchronization of Simple Harmonic Oscillator by Entrainment 174 6.2 Noise Lock Loop Tracking by Injection Locking .1 Extending Digital Primitives with Soft-Gates .2 Soft Flip-Flop .2 Application to Wireless Transceivers .1 Conventional Wireless Receiver .2 Application to Time-Domain (Pulse-based) Radios. Chandrakasan, MIT EECS, Cambridge, MA .2 Hans-Andrea Loeliger, ETH, Zurich, Switzerland .3 Jonathan Yedidia, Mitsubishi Electronics Research Lab, Cambridge, MA202 8.4 Neil Gershenfeld, MIT Media Lab, Cambridge, MA .5 Biography of Author. 204 15 16 List of Figures 1-1 Analog, distributed and un-clocked design decisions reinforce each other 35 1-2 A design space for computation.

The partial sphere at the bottom rep- resents digital computation and the partial sphere at the top represents our approach. 39 1-3 Chaotic communications system proposed by Mandal et al. 40 2-1 Gaussian distribution over two variables. 48 2-2 Factor graph for computer vision.

49 2-3 Factor graph model for statistical physics. 50 2-4 Factor graph for error correction decoding. 51 2-5 Visualization of joint distribution over random variables x1 , x2 , x3. 54 2-6 Visualization of marginalization over random variables x2 , x3 to find p(x1 = 1).

55 2-7 Visualization of marginalization over 2-dimensional gaussian distribution 56 2-8 Factor graph expressing that binary variables x and y are constrained to be opposite in value. 56 2-9 Factor graph expressing that binary variables x, y, and z are con- strained to sum to zero mod 2. 60 2-10 Factor graph containing a variable node more than one incident edge 61 2-11 Factor graph with more than one kind of constraint node. 62 2-12 Factor graph with incomplete marginalization leaving a “region” node: The basis of Generalized Belief Propagation.

63 2-13 Factor graph with a frustrated cycle. 65 17 2-14 Factor graph with a frustrated cycle and a local evidence node. 65 2-15 Simple acyclic graph. 67 2-16 Left to right: factor graph, MRF, Bayesian network.

70 2-17 The fictional “Asia” example of a Bayesian network, taken from Lau- ritzen and Spiegelhalter 1988. 71 2-18 Message passing with a single equals gate. 76 2-19 Converting a factor graph to a pairwise MRF. 77 2-20 Converting a a factor graph to a Bayesian network.

77 2-21 Converting a MRF to a factor graph. 78 2-22 Converting a Bayesian network to a factor graph. 78 3-1 System state update. 84 3-2 System state update combined with measurements.

84 3-3 Kalman filter update. 86 3-5 Graph representing the codeword constraints. 89 3-6 Graph representing the same codeword constraints. 90 3-8 Receiver graph implementing the codeword constraints.

91 3-9 Symbol for the soft-xor gate. 91 3-10 Random ad hoc peer-to-peer network. There are four interfaces {1, 2, 3, 4} on nodes 1 and 4, and three interfaces{1, 2, 3} on nodes 2 and 3. 93 3-11 Factor graph derived from ad hoc peer-to-peer network.

97 3-12 Factor graph derived from ad hoc peer-to-peer network. There are four interfaces {1, 2, 3, 4} on nodes 1 and 4, and three interfaces{1, 2, 3} on nodes 2 and 3. 98 4-1 Schematic diagram for a ring (relaxation) oscillator. 102 4-2 Factor graph for a ring (relaxation) oscillator.

102 4-3 Factor graph for trellis for synchronization of a ring oscillator. 103 4-4 Trellis section for a ring oscillator. 104 18 4-5 Factor graph for transmit and receive ring oscillators. 107 4-6 4-bin, 2-tap LFSR.

108 4-7 State cycle of a 4-bin, 2-tap LFSR. 111 4-9 DS/CDMA modulation with PN-sequence generated by an LFSR. 113 4-10 DS/CDMA demodulation with PN-sequence generated by an LFSR. 113 4-11 Trellis section for a 4-bin, 2-tap LFSR.

114 4-12 Factor graph for a trellis. 115 4-13 Shift graph for a linear feedback shift register. 118 4-14 Forward-only message passing on shift graph for a linear feedback shift register. 119 4-15 Section of the shift graph for a linear feedback shift register.

120 4-16 System to recursively implement section of the shift graph. 121 4-17 The Noise Lock Loop (NLL). 121 4-18 The Noise Lock Loop (NLL). 122 4-19 2 time-step joint message on the LFSR shift graph.

123 4-20 3 time-step joint message on the LFSR shift graph (recovers the trellis) 124 4-21 Block diagram for a binary counter. 128 4-22 Shift graph for a binary counter .