Kaiserslautern - Fachbereich Elektrotechnik und Informationstechnik
Refine
Year of publication
- 2003 (5) (remove)
Document Type
- Doctoral Thesis (5) (remove)
Has Fulltext
- yes (5)
Keywords
- Mobilfunk (2)
- mobile radio (2)
- Bitvektor (1)
- CAD (1)
- CDMA (1)
- Empfangssignalverarbeitung (1)
- Entwurfsautomation (1)
- Erfüllbarke (1)
- Joint Transmission (1)
- Layout (1)
Faculty / Organisational entity
We present new algorithms and provide an overall framework for the interaction of the classically separate steps of logic synthesis and physical layout in the design of VLSI circuits. Due to the continuous development of smaller sized fabrication processes and the subsequent domination of interconnect delays, the traditional separation of logical and physical design results in increasingly inaccurate cost functions and aggravates the design closure problem. Consequently, the interaction of physical and logical domains has become one of the greatest challenges in the design of VLSI circuits. To address this challenge, we propose different solutions for the control and datapath logic of a design, and show how to combine them to reach design closure.
As the sustained trend towards integrating more and more functionality into systems on a chip can be observed in all fields, their economic realization is a challenge for the chip making industry. This is, however, barely possible today, as the ability to design and verify such complex systems could not keep up with the rapid technological development. Owing to this productivity gap, a design methodology, mainly using pre designed and pre verifying blocks, is mandatory. The availability of such blocks, meeting the highest possible quality standards, is decisive for its success. Cost-effective, this can only be achieved by formal verification on the block-level, namely by checking properties, ranging over finite intervals of time. As this verification approach is based on constructing and solving Boolean equivalence problems, it allows for using backtrack search procedures, such as SAT. Recent improvements of the latter are responsible for its high capacity. Still, the verification of some classes of hardware designs, enjoying regular substructures or complex arithmetic data paths, is difficult and often intractable. For regular designs, this is mainly due to individual treatment of symmetrical parts of the search space by backtrack search procedures used. One approach to tackle these deficiencies, is to exploit the regular structure for problem reduction on the register transfer level (RTL). This work describes a new approach for property checking on the RTL, preserving the problem inherent structure for subsequent reduction. The reduction is based on eliminating symmetrical parts from bitvector functions, and hence, from the search space. Several approaches for symmetry reduction in search problems, based on invariance of a function under permutation of variables, have been previously proposed. Unfortunately, our investigations did not reveal this kind of symmetry in relevant cases. Instead, we propose a reduction based on symmetrical values, as we encounter them much more frequently in our industrial examples. Let \(f\) be a Boolean function. The values \(0\) and \(1\) are symmetrical values for a variable \(x\) in \(f\) iff there is a variable permutation \(\pi\) of the variables of \(f\), fixing \(x\), such that \(f|_{x=0} = \pi(f|_{x=1})\). Then the question whether \(f=1\) holds is independent from this variable, and it can be removed. By iterative application of this approach to all variables of \(f\), they are either all removed, leaving \(f=1\) or \(f=0\) trivially, or there is a variable \(x'\) with no such \(\pi\). The latter leads to the conclusion that \(f=1\) does not hold, as we found a counter-example either with \(x'=0\), or \(x'=1\). Extending this basic idea to vectors of variables, allows to elevate it to the RTL. There, self similarities in the function representation, resulting from the regular structure preserved, can be exploited, and as a consequence, symmetrical bitvector values can be found syntactically. In particular, bitvector term-rewriting techniques, isomorphism procedures for specially manipulated term graphs, and combinations thereof, are proposed. This approach dramatically reduces the computational effort needed for functional verification on the block-level and, in particular, for the important problem class of regular designs. It allows the verification of industrial designs previously intractable. The main contributions of this work are in providing a framework for dealing with bitvector functions algebraically, a concise description of bounded model checking on the register transfer level, as well as new reduction techniques and new approaches for finding and exploiting symmetrical values in bitvector functions.
In Anbetracht der ständig steigenden Nachfrage nach Mobilkommunikation einerseits und der nur begrenzt zur Verfügung stehenden Ressource Frequenzspektrum andererseits müssen Mobilfunksysteme der dritten Generation (3G) eine hohe Frequenzökonomie haben. Dies trifft insbesondere auf die Abwärtsstrecken dieser Systeme zu, in denen auch paketorientierte Dienste mit hohen Datenraten angeboten werden sollen. Seitens der Basisstationen kann die spektrale Effizienz der Abwärtsstrecke durch das Verwenden mehrelementiger adaptiver Sendeantennen erhöht werden. Hierzu sind leistungsfähige Signalverarbeitungskonzepte erforderlich, die die effektive Kombination der adaptiven Antennen mit der eingesetzten Sendeleistungsregelung ermöglichen. Die wichtigsten Aspekte beim Entwerfen von Signalverarbeitungskonzepten für adaptive Sendeantennen sind das Gewährleisten mobilstationsspezifischer Mindestdatenraten sowie das Reduzieren der aufzuwendenden Sendeleistungen. Die vorliegende Arbeit trägt dazu bei, den Einsatz mehrantennenelementiger adaptiver Sendeantennen in Mobilfunksystemen der dritten Generation voranzutreiben. Existierende Konzepte werden dargestellt, vereinheitlicht, analysiert und durch eigene Ansätze des Autors erweitert. Signalverarbeitungskonzepte für adaptive Antennen benötigen als Wissensbasis zumindest einen gewissen Grad an Kenntnis über die Mobilfunkkanäle der Abwärtsstrecke. Beim für den FDD-Modus angedachten 3G-Teilstandard WCDMA ergibt sich das Problem, daß wegen des Frequenzversatzes zwischen der Auf- und der Abwärtsstrecke die Ergebnisse der Kanalschätzung in der Aufwärtsstrecke nicht direkt zum Einstellen der adaptiven Sendeantennen verwendet werden können. Eine Möglichkeit, in FDD-Systemen an den Basisstationen ein gewisses Maß an Kenntnis über die räumlichen Eigenschaften der Mobilfunkkanäle der Abwärtsstrecke verfügbar zu machen, besteht im Ausnutzen der an den Basisstationen ermittelbaren räumlichen Korrelationsmatrizen der Mobilfunkkanäle der Aufwärtsstrecke. Diese Vorgehensweise ist nur dann sinnvoll, wenn die relevanten Einfallsrichtungen der Aufwärtsstrecke mit den relevanten Abstrahlungsrichtungen der Abwärtsstrecke übereinstimmen. Für diesen Fall wird in der vorliegenden Arbeit ein aufwandsgünstiges Verfahren zum Anpassen der adaptiven Sendeantennen erarbeitet, das nicht auf komplexen Richtungsschätzalgorithmen beruht. Eine verläßlichere Methode, an den Basisstationen ein gewisses Maß an Kenntnis über die räumlichen Eigenschaften der Mobilfunkkanäle der Abwärtsstrecke verfügbar zu machen, ist das Signalisieren von Kanalzustandsinformation, die an den Mobilstationen gewonnen wird, über einen Rückkanal an die versorgende Basisstation. Da dieses Rücksignalisieren zeitkritisch ist und die Übertragungskapazität des Rückkanals begrenzt ist, wird in der vorliegenden Arbeit ein aufwandsgünstiges Verfahren zum Vorverarbeiten und Rücksignalisieren von Kanalzustandsinformation erarbeitet.
Empfängerorientierte Übertragungsverfahren sind dadurch gekennzeichnet, daß der im Sender zu verwendende Signalverarbeitungsalgorithmus an den im Empfänger verwendeten Signalverarbeitungsalgorithmus angepaßt ist. Dies geschieht meist mit zusätzlicher Kanalinformation, die nur am Sender und nicht am Empfänger verfügbar ist. In empfängerorientierten Systemen kann man besonders einfache Algorithmen in den Empfängern realisieren, die im Falle einer Abwärtsstreckenübertragung eines Mobilfunksystems, in den Mobilstationen sind. Dies ist mit geringen Produktionskosten und geringem Energieverbrauch der Mobilstationen verbunden. Um dennoch eine gewisse Güte der Datenübertragung zu gewährleisten, wird bei der Empfängerorientierung mehr Aufwand in der Feststation des Mobilfunksystems betrieben. Die derzeit verwendeten und für die dritte Mobilfunkgeneration (UMTS) vorgesehenen Übertragungsverfahren sind senderorientiert. Das bedeutet, daß der Signalverarbeitungsalgorithmus im Empfänger an den Signalverarbeitungsalgorithmus des Senders angepaßt ist. Auch bei der Senderorientierung wird meist die Kanalinformation in den Anpassungsprozeß im Empfänger einbezogen. Zum Gewinnen der Kanalinformation sind Testsignale notwendig, anhand der die Kanalinformation geschätzt werden kann. Solche Testsignale können in der Abwärtsstrecke eines empfängerorientierten Mobilfunksystems entfallen. Anstelle der Testsignale kann man Daten übertragen und somit die Datenrate im Vergleich zu senderorientierten Systemen erhöhen. Um die Performanz von Übertragungsverfahren beurteilen zu können, sind geeignete Kriterien notwendig. Meist werden zur Beurteilung Bitfehlerwahrscheinlichkeiten oder Signal-Stör-Verhältnisse verwendet. Da die Höhe der aufzuwendenden Sendeenergie nicht nur technisch, sondern auch gesellschaftlich ein wichtiger Aspekt zukünftiger Mobilfunksysteme ist, wird vom Verfasser das Kriterium der Energieeffizienz vorgeschlagen. Die Energieeffizienz beurteilt das Zusammenspiel von Signalverarbeitungsalgorithmen des Senders und des Empfängers unter Berücksichtigung der Kanaleigenschaften. Dabei wird die nutzbare Empfangsenergie auf die investierte Sendeenergie bezogen. Anhand der ermittelten energieeffizienzen und analytischen Betrachtungen in der vorliegenden Arbeit kann man den Schluß ziehen, daß empfängerorientierte Übertragungsverfahren für die Abwärtsstreckenübertragung in Mobilfunksystemen den senderorientierten vorzuziehen sind, wenn an der Feststation relativ viele und an den Mobilstationen relativ wenige Antennen zur Verfügung stehen. Dies ist bereits heute der Fall und auch in zukünftigen Mobilfunksystemen zu erwarten. Ferner eröffnet das am Rande untersuchte kanalorientierte Übertragungsverfahren, bei dem die Signalverarbeitungsalgorithmen des Sender und des Empfängers an die Kanalinformation angepaßt werden, ein weites Feld für zukünftige Forschungsvorhaben.
Mobilfunksysteme sind interferenzbegrenzt. Eine signifikante Steigerung der Leistungsfähigkeit künftiger Mobilfunksysteme kann daher nur durch den Einsatz von Verfahren zum Reduzieren der schädlichen Wirkung von Interferenz erreicht werden. Eine besonders attraktive Klasse von Verfahren, die dieses leisten, sind jene der gemeinsamen Empfangssignalverarbeitung, wobei bisher der systematische Entwurf und die systematische Analyse solcher Verfahren für CDMA-Mobilfunksysteme mit infiniter oder quasi-infiniter Datenübertragung - eine im Hinblick auf die derzeit in Betrieb gehenden zellularen Mobilfunksysteme der dritten Generation besonders interessierende Klasse von künftigen Mobilfunksystemen - noch unklar ist. Die vorliegende Arbeit liefert einen Beitrag zur Systematisierung des Entwurfs- und Optimierungsprozesses von Verfahren zur gemeinsamen Empfangssignalverarbeitung für Mobilfunksysteme der genannten Art. Zu diesem Zweck wird gezeigt, daß sich die Aufgabe der gemeinsamen Empfangssignalverarbeitung in die fünf Teilaufgaben Blockbilden, Datenzuordnen, Interblock-Signalverarbeitung, Intrablock-Signalverarbeitung und Kombinieren & Entscheiden zerlegen läßt. Nachdem in einem ersten Schritt alle fünf Teilaufgaben klar definiert und gegeneinander abgegrenzt werden, erfolgt in einem zweiten Schritt für jede Teilaufgabe die Entwicklung von Lösungsvorschlägen, die nach gewissen Kriterien optimal bzw. suboptimal sind. Zur Lösung jeder einzelnen Teilaufgabe werden neuartige Vorgehensweisen vorgeschlagen, wobei dabei sowohl die Optimierung der Leistungsfähigkeit der jeweiligen Vorgehensweisen als auch Belange, die für die praktische Realisierbarkeit relevant sind, im Vordergrund stehen. Eine Schlüsselrolle kommt den Verfahren der Intrablock-Signalverarbeitung zu, deren Aufgabe darin besteht, ausgehend von Ausschnitten des Empfangssignals Schätzungen von Daten zu ermitteln, die zu dem jeweiligen Ausschnitt beitragen. Die vorgeschlagenen Verfahren der Intrablock-Signalverarbeitung beruhen im wesentlichen auf iterativen Versionen bekannter linearer Schätzer, die um einen nichtlinearen Schätzwertverbesserer erweitert werden. Der nichtlineare Schätzwertverbesserer nutzt dabei A-priori-Information, wie z.B. die Kenntnis des Datensymbolalphabetes und der A-priori-Wahrscheinlichkeiten der zu übertragenden Daten, zum Erhöhen der Zuverlässigkeit der zu ermittelnden Datenschätzungen. Die verschiedenen Versionen der iterativ realisierten linearen Schätzer und verschiedene Schätzwertverbesserer bilden eine Art Baukastensystem, das es erlaubt, für viele Anwendungsfälle ein maßgeschneidertes Verfahren zur Intrablock-Signalverarbeitung zu konstruieren. Aufbauend auf dem entwickelten systematischen Entwurfsprinzip wird abschließend für ein exemplarisches CDMA-Mobilfunksystem mit synchronem Mehrteilnehmerzugriff ein darauf zugeschnittenes Verfahren zur gemeinsamen Empfangssignalverarbeitung vorgeschlagen. Die dargelegten Simulationsergebnisse zeigen, daß ausgehend von derzeit favorisierten nicht dem Prinzip der gemeinsamen Empfangssignalverarbeitung folgenden Verfahren zum Schätzen der übertragenen Daten in typischen Mobilfunkszenarien durch Einsetzen des vorgeschlagenen Verfahrens zur gemeinsamen Empfangssignalverarbeitung die Anzahl der gleichzeitig aktiven CDMA-Codes um nahezu eine Größenordnung erhöht werden kann, ohne dabei die bei einem vorgegebenen Signal-Stör-Verhältnis am Referenzempfänger beobachtbare Zuverlässigkeit der ermittelten Schätzungen zu verschlechtern. Deshalb ist der Einsatz von Verfahren zur gemeinsamen Empfangssignalverarbeitung eine vielversprechende Maßnahme zur Kapazitätssteigerung künftiger Mobilfunksysteme.