Algebraic and Combinatorial Algorithms for Translinear Network Synthesis

Algebraische und Kombinatorische Algorithmen zur Synthese Translinearer Netzwerke

  • This thesis contains the mathematical treatment of a special class of analog microelectronic circuits called translinear circuits. The goal is to provide foundations of a new coherent synthesis approach for this class of circuits. The mathematical methods of the suggested synthesis approach come from graph theory, combinatorics, and from algebraic geometry, in particular symbolic methods from computer algebra. Translinear circuits form a very special class of analog circuits, because they rely on nonlinear device models, but still allow a very structured approach to network analysis and synthesis. Thus, translinear circuits play the role of a bridge between the "unknown space" of nonlinear circuit theory and the very well exploited domain of linear circuit theory. The nonlinear equations describing the behavior of translinear circuits possess a strong algebraic structure that is nonetheless flexible enough for a wide range of nonlinear functionality. Furthermore, translinear circuits offer several technical advantages like high functional density, low supply voltage and insensitivity to temperature. This unique profile is the reason that several authors consider translinear networks as the key to systematic synthesis methods for nonlinear circuits. The thesis proposes the usage of a computer-generated catalog of translinear network topologies as a synthesis tool. The idea to compile such a catalog has grown from the observation that on the one hand, the topology of a translinear network must satisfy strong constraints which severely limit the number of "admissible" topologies, in particular for networks with few transistors, and on the other hand, the topology of a translinear network already fixes its essential behavior, at least for static networks, because the so-called translinear principle requires the continuous parameters of all transistors to be the same. Even though the admissible topologies are heavily restricted, it is a highly nontrivial task to compile such a catalog. Combinatorial techniques have been adapted to undertake this task. In a catalog of translinear network topologies, prototype network equations can be stored along with each topology. When a circuit with a specified behavior is to be designed, one can search the catalog for a network whose equations can be matched with the desired behavior. In this context, two algebraic problems arise: To set up a meaningful equation for a network in the catalog, an elimination of variables must be performed, and to test whether a prototype equation from the catalog and a specified equation of desired behavior can be "matched", a complex system of polynomial equations must be solved, where the solutions are restricted to a finite set of integers. Sophisticated algorithms from computer algebra are applied in both cases to perform the symbolic computations. All mentioned algorithms have been implemented using C++, Singular, and Mathematica, and are successfully applied to actual design problems of humidity sensor circuitry at Analog Microelectronics GmbH, Mainz. As result of the research conducted, an exhaustive catalog of all static formal translinear networks with at most eight transistors is available. The application for the humidity sensor system proves the applicability of the developed synthesis approach. The details and implementations of the algorithms are worked out only for static networks, but can easily be adopted for dynamic networks as well. While the implementation of the combinatorial algorithms is stand-alone software written "from scratch" in C++, the implementation of the algebraic algorithms, namely the symbolic treatment of the network equations and the match finding, heavily rely on the sophisticated Gröbner basis engine of Singular and thus on more than a decade of experience contained in a special-purpose computer algebra system. It should be pointed out that the thesis contains the new observation that the translinear loop equations of a translinear network are precisely represented by the toric ideal of the network's translinear digraph. Altogether, this thesis confirms and strengthenes the key role of translinear circuits as systematically designable nonlinear circuits.
  • Diese Arbeit enthält die mathematische Behandlung translinearer Schaltungen, einer speziellen Klasse analoger mikroelektronischer Schaltungen. Das Ziel ist, die Grundlagen für eine neue Synthesemethodik für diese Klasse von Schaltungen zu legen. Die mathematischen Methoden des vorgeschlagenen Ansatzes bedienen sich der Graphentheorie, der Kombinatorik, und der Algebraischen Geometrie, letzterer in Form symbolischer Methoden aus der Computeralgebra. Eine besondere Klasse analoger Schaltungen bilden translinare Schaltungen deswegen, weil sie auf nichtlinearen Bauteilmodellen beruhen, aber trotzdem eine sehr strukturierte Herangehensweise an Netzwerkanalyse und -synthese erlauben. Daher kommt translinearen Schaltungen die Rolle einer "Brücke" zwischen dem "unbekannten Weite" nichtlinearer Schaltungen und der wohlbekannten aber beschränkten Welt linearer Schaltungen zu. Die nichtlinearen Gleichungen, die das Verhalten translinearer Schaltungen beschreiben, besitzen eine feste algebraische Struktur, die aber vielseitig genug ist, theoretisch nahezu jede gewünschte nichtlineare Funktionalität abdecken zu können. Ausserdem bieten translineare Schaltungen einige technische Vorteile wie hohe Funktionsdichte, niedrige Versorgungsspannung und Temperaturunabhängigkeit. Diese einzigartige Kombination von Eigenschaften ist der Grund, dass viele Autoren translineare Netzwerke als den Schlüssel zu systematischen Synthesemethoden für nichtlineare Schaltunge betrachten. Es wird die Benutzung eines Computer-erzeugten Katalogs von translinearen Netzwerktopologien als Synthesewerkzeug vorgeschlagen. Die Idee, einen solchen Katalog zusammenzustellen, ist aus der Beobachtung erwachsen, dass die Topologie einer translinearen Schaltung einerseits strenge Bedingungen erfüllen muss, so dass die Zahl der möglichen Topologien insbesondere für Netzwerke mit wenigen Transistoren beschränkt ist, und dass andererseits die Schaltungstopologie das Verhalten der Schaltung zumindest bei statischen Schaltungen bereits festlegt. Obwohl die möglichen Topologien stark eingeschränkt sind, ist es eine nichttriviale Aufgabe, einen solchen Katalog zu erstellen. Zur Lösung dieser Aufgabe werden Techniken aus der Kombinatorik adaptiert. In dem Katalog von Netzwerktopologien können prototypische Netzwerkgleichungen für jede Topologie mit abgelegt werden. Wenn eine Schaltung mit einem bestimmten Verhalten entworfen werden soll, kann man dann den Katalog nach einem Netzwerk durchsuchen, dessen Gleichungen zu dem vorgesehenen Verhalten passen. In diesem Zusammenhang tauchen zwei algebraische Probleme auf: Um die Gleichungen eines Netzwerks handhabbar zu machen, muss eine Elimination von Variablen durchgeführt werden, und zum Testen ob eine Prototyp-Gleichung aus dem Katalog und eine vorgegebene Gleichung des gewünschten Verhaltens "zusammen passen", muss ein kompliziertes polynomiales Gleichungssystem gelöst werden, wobei die Lösungen aus einer vorgegebenen endlichen Menge ganzer Zahlen stammen sollen. Hochentwickelte Algorithmen der Computeralgebra werden in beiden Fällen zum Durchführen der symbolischen Berechnungen eingesetzt. Alle erwähnten Algorithmen sind mittels C++, Singular und Mathematica implementiert worden, und es wird die Anwendung auf das Design einer Schaltung im Kern eines Luftfeuchtigkeitssensor-Systems der Analog Microelectronics GmbH, Mainz, demonstriert. Als weiteres Ergebnis der Forschungsarbeiten steht ein vollständiger Katalog aller statischen formalen translinearen Netzwerke mit bis zu acht Transitoren zur Verfügung. Die Details und Implementierungen der entwickelten Algorithmen sind zwar nur fü statische Netzwerke ausgeführt, können aber leicht für dynamische Netzwerke verallgemeinert werden. Während die Implementierung der kombinatorischen Algorithmen "stand-alone" Software darstellt, die ohne besondere Hilfsmittel oder Spezialbibliotheken in C++ entwickelt wurde, beruht die Implementierung der algebraischen Algorithmen, nämlich die symbolische Behandlung der Netzwerkgleichungen und die Suche nach Netzwerken mit geeigneten Gleichungen auf der weit entwickelten Gröbnerbasis-Engine von Singular, und somit auf mehr als einer Dekade an Erfahrungen, die mit diesem spezialisierten Computeralgebra-System gemacht wurden. Besondere Erwähnung verdient die in dieser Arbeit enthaltene neue Beobachtung, dass die translinearen Schleifengleichungen eines translinearen Netzwerks genau durch das torische Ideal des gerichteten translinearen Graphen des Netzwerks repräsentiert werden. Insgesamt bestärkt diese Arbeit die Schlüsselrolle translinearer Schaltungen als systematisch designbare nichtlineare Schaltungen.

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:David Ilsen
URN (permanent link):urn:nbn:de:hbz:386-kluedo-20592
Advisor:Gert-Martin Greuel
Document Type:Doctoral Thesis
Language of publication:English
Year of Completion:2005
Year of Publication:2005
Publishing Institute:Technische Universität Kaiserslautern
Granting Institute:Technische Universität Kaiserslautern
Acceptance Date of the Thesis:2006/05/19
Tag:Netzwerksynthese ; analoge Mikroelektronik ; nichtlineare Netzwerke; translineare Schaltungen
combinatorics; computeralgebra; network synthesis; nonlinear circuits; translinear circuits
GND-Keyword:Computeralgebra; Kombinatorik ; Mikroelektronik
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:510 Mathematik
MSC-Classification (mathematics):05A99 None of the above, but in this section
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
94C05 Analytic circuit theory
94C15 Applications of graph theory [See also 05Cxx, 68R10]

$Rev: 12793 $