Low-complexity real-time signal processing for wireless communications

Abstract

Signalverarbeitungsalgorithmen moderner Mobilkommunikationssysteme stellen sehr hohe Anforderungen an die Rechenleistung der zugrunde liegenden Hardware bei eng begrenztem Platz und Leistungsverbrauch.<br />Diese Algorithmen müssen aber in Echtzeit ausgeführt werden, da sonst Dienste wie z.B. die Sprachtelephonie gar nicht möglich wären. Diese beiden Anforderungen an Signalverarbeitungsalgorithmen---Bewältigung eines hohen Rechenaufwandes und Echtzeitfähigkeit---schließen sich aber oft gegenseitig aus. Die vorliegende Dissertation liefert Lösungen dieses Problems, indem die Komplexität von Signalverarbeitungsalgorithmen auf Kosten der Rechengenauigkeit reduziert wird. Das ist vor allem dann interessant, wenn die Genauigkeit der zugrunde liegenden Hardware oder die Anforderungen an die Rechengenauigkeit des Algorithmus limitiert sind.<br />Der erste Teil der Dissertation beschäftigt sich mit der Echtzeitsimulation von geometriebasierten Kanalmodellen. Derartige Kanalmodelle werden oft zur Simulation von MIMO (Multiple-Input Multiple-Output) Kanälen eingesetzt, da sie die räumliche Struktur der Mobilfunkkanäle implizit berücksichtigen. Solche Modelle erfordern allerdings eine sehr hohe Rechenleistung, da für jeden Ausbreitungspfad, für jeden Zeitpunkt sowie auch für jede Frequenz eine komplexe Exponentialfunktion ausgewertet werden muss. Auf Echtzeit-Kanalsimulatoren ist daher die Anzahl der Pfade limitiert, die simuliert werden kann.<br />Zeitvariante, frequenzselektive MIMO Kanäle können mathematisch als vierdimensionale Folgen beschrieben werden, wobei die einzelnen Dimensionen die Zeit, die Frequenz, den Raum am Sender und den Raum am Empfänger repräsentieren. In den meisten Mobilkommunikationssystemen sind diese Folgen bandlimitiert: In der Zeit durch die maximale Dopplerverschiebung, in der Frequenz durch die maximale Verzögerung im Kanal und im Raum durch die Aufspreizung der Ein- bzw. Ausfallswinkel.<br />Für eine block-basierte Kanalsimulation müssen indexlimitierte Teile dieser Folgen ausgewertet werden. Man kann zeigen, dass solche indexlimitierten Teile einer bandlimitierten Folge einen Unterraum niedriger Dimension aufspannen. Derselbe Unterraum wird auch von mehrdimensionalen DPS (discrete prolate spheroidal) Folgen aufgespannt.<br />Ein wichtiger Beitrag dieser Arbeit ist ein neuer Algorithmus zur approximativen Berechnung der Projektion eines geometriebasierten Kanalmodells auf diesen Unterraum in O(1) Operationen.<br />Der Approximationsfehler kann über die Unterraumdimension kontrolliert werden. Dadurch lässt sich Rechenaufwand und Genauigkeit des Kanalmodells auf die zugrunde liegende Hardware abstimmen. Auf einer Hardware mit 16 bit Fixpunktarithmetik lässt sich dadurch der Rechenaufwand im Vergleich zu einer konventionellen "Sum-of-sinusoids" Methode um mehr als eine Größenordung reduzieren.<br />Der zweite Teil der Dissertation geht auf die Entwicklung und die Simulation von Empfängerarchitekturen von modernen Mobilfunksystemen ein. Spezielles Augenmerk wird dabei auf Empfängerarchitekturen mit geringer Komplexität und Robustheit gegenüber Interferenz gelegt.<br />Zuerst untersuchen wir den Durchsatz verschiedener Empfängerarchitekturen des HSDPA (High Speed Downlink Packet Access) Systems von UMTS mittels einer Matlab Simulationsumgebung. Das hat den Vorteil, dass Algorithmen schnell und einfach in einer höheren Programmiersprache umgesetzt werden können. Ein herkömmlicher Rake-Empfänger, ein Rake-Empfänger mit Interferenzunterdrückung und ein LMMSE (Linear Minimum Mean Square Error) Entzerrer werden untersucht. Wir zeigen, dass ein LMMSE Entzerrer auf Kosten eines höheren Rechenaufwands einen höheren Durchsatz als ein Rake-Empfänger erzielt. Der Rechenaufwand kann jedoch erheblich reduziert werden, wenn man einen iterativen Krylov-Algorithmus zum Lösen des entstehenden Gleichungssystems einsetzt.<br />Viele Effekte, die in einer Hardwareimplementierung auftreten, können bei einer reinen Software-Simulation nicht berücksichtigt werden. Daher zeigen wir in einem zweiten Beispiel die Entwicklung und Implementierung eines GSM-Empfängers mit Intelligenten Antennen auf einer speziellen Signalverarbeitungshardware. Der Empfänger muss ein generalisiertes Eigenwertproblem in Echtzeit lösen. Wir zeigen, wie dieses Problem numerisch in Fixpunktarithmetik gelöst werden kann. Darüber hinaus zeigen wir Ergebnisse die mit dem ARC SmartSim Kanalsimulator erzielt worden sind.

Many signal processing algorithms in modern wireless communication systems come with a very high computational complexity. Moreover, these algorithms must be implemented in real time. Since the computational performance of digital signal processors is limited, these two requirements---dealing with arithmetic complexity and real-time constraints---are often mutually exclusive. This thesis tries to solve this problem by trading the complexity of signal processing algorithms for accuracy. This approach is feasible if the accuracy of the underlying hardware or the accuracy requirements of the algorithm's result is limited.<br />The first part of this thesis deals with the real-time simulation of geometry-based channel models. Geometry-based channel models implicitly model the spatial structure of the channel and are thus ideally suited for simulating MIMO (multiple-input multiple-output) systems. However, such models are computationally expensive, since for every propagation path, every time instance, and every delay or frequency bin, a complex exponential has to be evaluated. On a real-time hardware channel simulator the number of paths $P$ that can be simulated is thus limited by the available processing power.<br />Time-variant, frequency-selective MIMO channels can be described as four-dimensional sequences, where the dimensions represent time, frequency, space at the receiver, and space at the transmitter. In wireless communication systems, such sequences are bandlimited by the maximum Doppler frequency in time, by the maximum delay of the channel in frequency, by the angle of arrival spread in the space at the receiver, and by the angle of departure spread at the space at the transmitter.<br />For block based channel simulation, index-limited parts of these four-dimensional sequences need to be evaluated. It can be shown, that such index-limited parts span a low-dimensional subspace. The same subspace is spanned by the multidimensional discrete prolate spheroidal (DPS) sequences.<br />An important contribution of this thesis is a new algorithm that allows to compute the projection of a geometry-based channel model onto the DPS subspace in O(1) arithmetic operations. By adjusting the dimension of the subspace it is possible to trade complexity for accuracy. On a 16 bit fixed-point arithmetic processor, the computational complexity can be reduced by more than one order of magnitude compared to conventional sum-of-sinusoids implementations.<br />The second part of this thesis addresses the development and simulation of receiver architectures for state-of-the-art wireless communication systems. Special emphasis is put on low-complexity receiver designs and robustness of the algorithm against interference.<br />First, the throughput performance of different receiver architectures for the High Speed Downlink Packet Access (HSDPA) subsystem of UMTS are investigated using a Matlab simulation environment. The advantage of this approach is that ideas can be quickly implemented in a high-level language using a broad range of toolboxes. A conventional rake receiver, a rake receiver with interference cancelation, and a receiver employing a linear minimum mean square error (LMMSE) equalizer are investigated. It is shown that a LMMSE equalizer at the receiver achieves higher throughput than a conventional rake receiver, at the cost of higher complexity. As a consequence, an iterative algorithm based on Krylov subspace projections is introduced, which approximates the LMMSE equalizer with negligible loss of performance. Computational complexity as well as storage requirements are strongly reduced.<br />Not all effects occurring on the final hardware, such as fixed-point issues and real-time constraints, can be taken into account in a software simulation. Therefore, in a second example, a GSM receiver employing multiple antennas is developed and implemented directly on a DSP board. The smart antenna algorithm requires the solution of an eigenvalue problem in real-time. It is shown how to solve this eigenvalue problem numerically on a fixed-point processor. Real-time simulation results obtained with the ARC SmartSim channel simulator are described.<br />