PatentDe  


Dokumentenidentifikation DE19918610A1 26.10.2000
Titel Korrelationsverfahren minimalen Aufwands mit der Methode des Stapelns
Anmelder Hilberg, Wolfgang, Dr.-Ing., 64401 Groß-Bieberau, DE;
Wolf, Stefan, Dipl.-Ing., 64367 Mühltal, DE
Erfinder Hilberg, Wolfgang, Dr.-Ing., 64401 Groß-Bieberau, DE;
Wolf, Stefan, Dipl.-Ing., 64367 Mühltal, DE
DE-Anmeldedatum 23.04.1999
DE-Aktenzeichen 19918610
Offenlegungstag 26.10.2000
Veröffentlichungstag im Patentblatt 26.10.2000
IPC-Hauptklasse G01R 29/00
IPC-Nebenklasse H04L 25/08   H04Q 9/00   
Zusammenfassung Es werden Schaltungen beschrieben, mit denen man eine Korrelation ohne Multiplikatoren in einer äußerst kurzen Zeit und mit einem sehr geringen Aufwand durchführen kann. Hierbei werden sowohl Morse-Thue-Folgen als auch modifizierte Fibonacci-Folgen eingesetzt.

Beschreibung[de]

Die Erfindung betrifft eine Korrelationsschaltung nach dem Oberbegriff des Anspruchs 1.

Eine solche Schaltung wird bei der Übertragung von Signalen verwendet, bei der außer dem Nutzsignal auch ein starkes Rauschsignal vorhanden ist. Durch die Einführung von Korrelationsmethoden kann man das Rauschen weitgehend eliminieren und das Nutzsignal gewinnen. Es ist bekannt, das Korrelationsverfahren so zu gestalten, daß es eine Realisierung des Korrelationsintegrals bzw. einer entsprechenden Korrelationssumme darstellt. Hierbei werden Produkte aus diskreten Werten des Empfangssignals mit denen des Referenzsignals (Schlüssel) gebildet und summiert. Die Summe dieser Produkte ist ein Maß dafür, wie gut das Eingangssignal mit dem Referenzsignal korreliert ist, d. h. wie genau beide übereinstimmen.

Nachteilig ist bei der konventionellen Methode ist, daß die Schaltung viele Multiplizierer enthalten muß. Das ist einerseits sehr aufwendig und das Multiplizieren und Addieren vieler Ausdrücke kostet zudem auch noch sehr viel Zeit.

Der Erfindung liegt die Aufgabe zugrunde, die Korrelation mit einer einfacheren als der konventionellen Schaltungsanordnung zu realisieren und die für eine Korrelation benötigte Zeit zu minimieren. Dabei wird Bezug genommen auf die Anmeldung P 198 18 694.0 (Korrelationsermittlung durch Stapeln von Impulsen) vom 25. 4. 98, in der schon gezeigt wurde, daß man mit Hilfe von Morse-Thue-Folgen und einem sog. Stapeln von Impulsen grundsätzlich bessere Korrelationsergebnisse erhalten kann als mit dem Korrelationsintegral oder der Korrelationssumme, weil beim Stapeln die Summe der Absolutbeträge gebildet wird, die wesentlich größer sein kann als die Summe der Produkte. In der vorliegenden Anmeldung wird ergänzend noch gezeigt, daß man den Aufwand durch geeignete Schaltungen weiter verringern und die benötigte Verarbeitungszeit durch Parallelisierung auf ein Minimum reduzieren kann.

Die Aufgabe wird erfindungsgemäß durch die kennzeichnenden Merkmale des Anspruchs 1 gelöst. In den Unteransprüchen sind weitere Ausgestaltungen der Erfindung enthalten.

Kapitel 1. Einleitung

Heute ist es im Bereich der Technik immer noch ein weitverbreitetes Problem, Informationen zwischen zwei Punkten übertragen zu müssen, zwischen denen keine Kabelverbindung möglich ist.

Beispiele für Anwendungen, bei denen dieses Problem auftritt, sind Fernsteuerungen, die entweder Funkwellen oder Infrarotlicht als Übertragungsmedien nutzen, miniaturisierte Kommunikationsgeräte wie Pager und Mobiltelefone, aber auch Lichtschranken, die eine Unterbrechung eines Lichtstrahls durch ein Hindernis feststellen sollen.

Solchen Anwendungen steht häufig nur Energie in geringer Menge zur Verfügung. Die Sendeleistung der Geräte ist deshalb beschränkt. Das bedeutet, daß der Signal/Rauschabstand auf der Empfängerseite gering sein wird. Um eine Verbesserung des Signal/Rauschabstands und damit der möglichen Reichweite zu erzielen, ist in der Technik die Nutzung von Korrelationsverfahren verbreitet. Beispiele für ihren Einsatz sind das Satellitennavigationssystem GPS oder geplante Mobiltelefonnetze wie das amerikanische IS95-Netz.

Grundlage all dieser Verfahren ist, die zu übertragenden Daten in verschiedene Symbolfolgen endlicher Länge zu codieren, die sowohl dem Sender als auch dem Empfänger bekannt sind.

In der Literatur finden sich eine Vielzahl von Untersuchungen über Symbolfolgen, die sich für die Datenübertragung eignen. Dabei wird meistens der Schwerpunkt auf eine hohe Korrelationsgüte der Symbolfolgen oder eine effiziente Nutzung der zur Verfügung stehenden Bandbreite des Übertragungskanals gelegt.

Der Einsatz von Korrelationsverfahren hat aber seinen Preis. Korrelatoren erfordern einen hohen schaltungstechnischen Aufwand oder, wenn sie in Software realisiert werden sollen, eine hohe Rechenleistung.

Für die beiden oben angegebenen Beispielfälle Satellitennavigation und Mobiltelefone ist dieser Aufwand kein Problem, da der Systempreis der Geräte hoch ist und für diese Geräte spezielle Chips hergestellt werden können, die den preislichen Aufwand bei der Massenproduktion verringern.

Für Geräte im Niedrigpreissegment scheiden Standardkorrelationsverfahren wegen des Aufwandes aber aus. Ein Fernsteuersender oder Empfänger, der einen Komplettpreis (ab Hersteller) von weniger als 20.- DM haben darf, enthält weder eine ausreichend leistungsfähige CPU, um Korrelationen in Software auszuführen, noch erlaubt das knappe Budget eine aufwendige Lösung in Hardware.

In dieser Arbeit sollen Korrelationsverfahren deshalb unter einem anderen Blickwinkel betrachtet werden. Nicht eine optimale Korrelationsgüte der Symbolfolgen, sondern eine Minimierung des zur Erzeugung und Wiedergewinnung der Symbolfolgen nötigen Rechenaufwandes soll das Ziel sein. Durch eine Vereinfachung der nötigen Operationen und der Verringerung ihrer Anzahl soll eine Implementierung auch auf preiswerten Microcontrollern als Softwarelösung oder in preiswerter Hardware wie programmierbaren Gate-Arrays möglich sein. Die im folgenden vorgestellten Konzepte sollen keinen Ersatz für Anwendungen darstellen, bei denen Rechenleistung reichlich vorhanden ist, um eine hinsichtlich des Störabstandes oder der Bandbreite optimierte Übertragung zu erreichen. Sie sollen die Möglichkeiten eines Korrelationsempfängers auch in Bereichen nutzbar machen, in denen dies bisher aus Aufwandsgründen unmöglich war.

Nach einer Beschreibung der mathematischen Grundlagen der Korrelation soll zuerst ein Überblick über Korrelationsverfahren gegeben werden, wie sie derzeit im industriellen Einsatz sind. Im Anschluß daran werden Parameter entwickelt, die einen Vergleich der Eignung der verschiedenen untersuchten Verfahren zur Informationsübertragung ermöglichen sollen.

In Kapitel 3 wird eine vereinfachte Struktur vorgestellt, die mit beliebigen Zahlenfolgen arbeiten kann, aber ohne aufwendige Multiplikationen auskommt. Realisierungsmöglichkeiten dieses Verfahrens werden anhand von Beispielimplementierungen in Hard- und Software vorgestellt.

Im Anschluß daran werden verschiedene Zahlenfolgen untersucht, deren einfache Bildungsgesetze eine iterative Decodierung mit sehr geringem Rechenaufwand ermöglichen.

Abschließend werden die beschriebenen Verfahren tabellarisch und grafisch einander gegenübergestellt. Dabei wird insbesondere auf den Rechenaufwand des Verfahrens, die Güte der Korrelation und die allgemeine Verwendbarkeit eingegangen.

Ergänzend findet man einen Anhang, in dem die Quelltexte der in MatLab durchgeführten Software-Simulationen, Quelltexte der Beispielimplementierungen in C++ und die VHDL- Quelltexte der beschriebenen einfachen Korrelationsverfahren abgedruckt sind.

Kapitel 2. Grundlagen

In den zunächst folgenden Abschnitten werden die wichtigsten Begriffe erläutert, die zum Verständnis der weiteren Kapitel nötig sind und die bekannte Ansätze zur Informationsübertragung durch Symbolfolgen darstellen.

Die Grundidee aller Korrelationsverfahren ist die Verwendung von Wissen über das vom Sender zu erwartende Signal. Wenn wir zum Beispiel versuchen, einen in einer lauten (stark gestörten) Umgebung sprechenden Menschen zu verstehen, so geht das meist recht gut, wenn er unsere Muttersprache spricht. Weniger gut, wenn er eine von uns nur unvollkommen beherrschte Fremdsprache spricht. Noch einfacher fällt uns das Verstehen, wenn wir den Zusammenhang der Rede kennen. In den Fällen, in denen uns das Verstehen leicht fällt, kann das menschliche Gehirn Vorwissen einbringen, welche Worte zu erwarten sind und diese dann auch in der gestörten "Übertragung" eindeutig wiedererkennen.

In der Technik werden dazu vom Sender unterschiedliche, endlich lange Zahlenfolgen ausgesendet, die sowohl der Sender als auch der Empfänger kennen. Dies kann mit der gemeinsamen Muttersprache im obigen Gespräch verglichen werden. Der Empfänger kann dann gezielt im empfangenen Signal nach Signalabschnitten suchen, die dieser Zahlenfolge ähneln. Zur technischen Realisierung benötigt er daher ein Verfahren, das ein Maß für die Ähnlichkeit liefert.

2.1 Definition der Korrelationsfunktion

Die Impulskorrelationsfunktion ist ein solches Maß für die Ähnlichkeit zweier Signale. Als Ausgangspunkt für die Definition der Ähnlichkeit wird die Differenz der Signale herangezogen.

Je geringer die Differenz zweier Signale, um so ähnlicher müssen sie sein.

Gegeben seien zwei Signale x(t) und y(t) mit endlicher Energie, die man auch Energiesignale nennt [Lük92]. Energiesignale sind Signale, die ein begrenztes Integral über den Zeitraum von -∞ bis +∞ haben.





Wenn x(t) und y(t) die Bedingung der endlichen Energie erfüllen, so ist auch ihr Differenzsignal Δ(t) = x(t)-y(t) ein Energiesignal. Seine Energie kann als Maß für die Ähnlichkeit der beiden Signale verwendet werden.





Um das Ähnlichkeitsmaß von der Energie der einzelnen Signale unabhängig zu machen, werden die Signale üblicherweise so normiert, daß ihre Energien den Wert Eins annehmen: xn(t) = x(t)/√Ex und yn(t) = y(t)/√Ey. Dann gilt





Mit diesem normierten Abweichungsmaß wird dann der Korrelationskoeffizient definiert als





Da beim technischen Einsatz die genaue zeitliche Lage der Funktionen nicht bekannt ist, muß noch die Möglichkeit einer zeitlichen Verschiebung dieser beiden Signale gegeneinander ermöglicht werden. Ein Auftragen des Korrelationskoeffizienten über alle möglichen Verschiebungen ergibt dann die Korrelationsfunktion.





Die Korrelationsfunktion liefert Ergebnisse im Bereich zwischen -1 und 1. Hierbei steht ein Wert von 1 für eine maximale Ähnlichkeit der Signale (sie sind identisch) und ein Wert von minus 1 für die maximale Unterschiedlichkeit dieser Signale (dieser Wert tritt auf, wenn y(t) bis auf das Vorzeichen mit x(t) übereinstimmt).

2.2 Die Impulskorrelationsfunktion zeitdiskreter Signale

Wenn man die Korrelationsfunktion zeitdiskreter Signale bestimmen möchte, so läßt sich eine Gleichung angeben, die äquivalent zu Gleichung 2.5 ist. Anstelle des Integrals tritt nun eine Summe über das Produkt der einzelnen zeitdiskreten Abtastwerte. Die Abtastwerte ergeben sich durch die äquidistante Abtastung des kontinuierlichen Eingangssignals im Abstand von Δt (n = t/Δt). In den folgenden Gleichungen wurden die Signale im Gegensatz zu Gleichung 2.5 nicht normiert. Man erhält die sogenannte Kreuzkorrelation





Die Korrelationsfunktion ist wegen der fehlenden Normierung beschränkt durch



xy(n)| ≤ √ ≙ (2.7)

Bei der Übertragung eines Signals x(k) von einem Sender zu einem Empfänger, bei der auf der Übertragungsstrecke starkes Rauschen hinzukommt, wird in der Regel angenommen, daß das empfangene Signal ≙(k) sowohl die Nutzinformation als auch die Störungen enthält. Um den Störanteil durch die Kreuzkorrelation zu eliminieren, wird man dann die Funktion y(k) als (Decodierungs-) Schlüssel beim Empfänger benutzen, wobei der Schlüssel gleich dem rauschfreien Signal gewählt wird (x(k) = y(k)). Voraussetzung ist dabei meist, daß das Signal x(k) bzw. der Schlüssel y(k) als eine zufällige oder pseudozufällige Folge diskreter Werte mit einer genügend großen Länge festgelegt wird. Nur dann kann sich eine Folge gleichwahrscheinlicher Störanteile, summiert über die Länge des Signals bzw. des Schlüssels, im Ergebnis nahezu wieder aufheben. Genauere Aussagen lassen sich nur dann machen, wenn die statistischen Parameter des Störsignals bekannt sind (z. B. weißes Rauschen). Hier sollen aber keine Annahmen über die Eigenschaften möglicher Störungen getroffen werden. Aus diesen Gründen wird in den folgenden Formeln für die Kreuzkorrelation und die Autokorrelation der Störanteil in dem empfangenen Signal ≙(k) nicht mehr explizit genannt, d. h. man betrachtet lediglich den rauschfreien Kern x(k) der empfangenen Signale.

2.3 Die Autokorrelationsfunktion zeitdiskreter Signale

In technischen Anwendungen ist die eindeutige Bestimmung des Anfangs eines gesendeten Signals, zum Beispiel einer Folge von Impulsen, von besonderem Interesse.

Es ist also zu untersuchen, wie ähnlich eine Funktion zu sich selbst ist. Dabei muß eine Funktion zu allen verschobenen Versionen von sich selbst möglichst unähnlich sein.

Setzen wir jetzt x(k) = y(k) in 2.6 ein, so ergibt sich als diskrete Autokorrelationsfunktion:





Auch die Autokorrelation ist beschränkt durch:



xx(n)| ≤ Ex = φxx(0) (2.9)

Der größte Wert der Autokorrelation tritt also genau dann auf, wenn die Folgen nicht gegeneinander verschoben werden, also





2.4 Alternative Definition über die Faltung von Signalen

Wenn man die Gleichung der Kreuzkorrelation





mit der Gleichung vergleicht, die die Faltung zweier Signale beschreibt [OpS92]





so erkennt man eine weitgehende Übereinstimmung. Nur die Abtastreihenfolge der zweiten Funktion ist bei der Faltungsgleichung vertauscht. Man kann durch die beiden folgenden Gleichungen einen Zusammenhang zwischen Korrelation und Faltung beschreiben:





Eine Schaltung, die zwei Signale x und y falten kann, läßt sich somit auch zur Berechnung der Korrelation einsetzen, wenn die Abtastreihenfolge des Referenzsignals umkehrt.

2.5 Periodische und aperiodische Korrelationsfunktionen von Zahlenfolgen

Sowohl die kontinuierlichen als auch die zeitdiskreten Funktionen x und y aus den vorigen Abschnitten waren im Bereich von -∞ bis +∞ definiert. In der Technik muß man jedoch mit zeitlich beschränkten Folgen arbeiten. Diese Folgen X sind nur in einem Bereich von 0 bis N-1 definiert.

Um das Korrelationsverhalten solcher Zahlenfolgen zu beurteilen, ist es nun interessant, wie der Bereich außerhalb von 0 bis N-1 definiert worden ist.

Eine Möglichkeit ist, alle Werte außerhalb dieses Bereichs als 0 zu definieren. Damit erhält man den aperiodischen Fall:





In diesem Fall ist das Produkt in der Korrelationsgleichung immer 0, wenn die Zahlenfolgen um einen Betrag größer oder gleich N gegeneinander verschoben werden. Eine Zahlenfolge der Länge N hat somit eine aperiodische Autokorrelationsfunktion der Länge 2N-1. Es ergibt sich dann für die Autokorrelationsfunktion folgender Ausdruck:





Dieser Fall beschreibt das Verhalten, wenn vom Sender die Zahlenfolge alleine, ohne weitere direkt vorangehende oder direktfolgende Signale ausgesendet wird.

Im Fall der Anwendung zur Datenübertragung werden die Zahlenfolgen jedoch häufig direkt aufeinanderfolgend ausgesendet. Dann kann man sich die Zahlenfolge unendlich oft wiederholt vorstellen. Wir bezeichnen dies als den periodischen Fall:



xper(k) = X(kmodN) (2.18)

In diesem Fall ist auch die Autokorrelationsfunktion periodisch mit der Länge N:





Dieser Fall beschreibt das Verhalten, wenn die Zahlenfolgen vom Sender direkt aufeinanderfolgend ausgesendet werden, also die verschobene Folge in die nächste, gleichartige Folge hineinreicht.

2.6 Kriterien zur Bewertung von Zahlenfolgen zur Informationsübertragung

Die Autokorrelationsfunktion kann man dazu verwenden, die Eignung einer Zahlenfolge für die Informationsübertragung zu bewerten.

Wünschenswert für die Informationsübertragung ist eine Autokorrelationsfunktion, die ein ausgeprägtes Maximum bei einem Verschiebewert von n = 0 aufweist und für die bei allen anderen n nur sehr kleine Werte auftreten.

Aus der Literatur sind die sogenannten perfekten Folgen bekannt [Lük92]. Bei diesen Folgen hat die Autokorrelationsfunktion für alle Verschiebewerte von n≠0 den Wert 0. Dieser Fall kann nur bei der periodischen Autokorrelationsfunktion auftreten. Binärfolgen mit perfekter periodischer Autokorrelationsfunktion sind nur für eine Länge von N = 4 bekannt. Diese Folge lautet:



s(n) = 1, 1, 1, -1 (2.20)

In [Bau71] wird gezeigt, daß bis zu einer Länge von N = 12100 keine weiteren perfekten Binärfolgen existieren.

Sehr nahe an diesem Optimalfall liegen die mit rückgekoppelten Schieberegistern erzeugten PRN-Folgen (Pseudo Random Noise), bei denen die Autokorrelationsfunktion für alle Werte n≠0 nur einen Wert von 1 aufweist.

Zur Bewertung der Abweichung der Korrelationsfunktion der zu untersuchenden Folge von einer perfekten Folge sind zwei Gütemaße gebräuchlich:

2.6.1 Abstand des Hauptmaximums zu den Nebenmaxima

Der Wert HNV sei definiert als das Verhältnis des Hauptmaximums der Autokorrelationsfunktion zum betragsgrößten Nebenmaximum [Lük92]:





Das HNV beschreibt also die impulsartigen Eigenstörungen, die am Ausgang eines Korrelators durch verschobene Eingangssignale auftreten. Diese Störungen wirken sich besonders in der Synchronisationsphase aus, da der Empfänger auf ein Nebenmaximum einrasten könnte, wenn dieses betragsmäßig zu nahe am Hauptmaximum liegt.

2.6.2 Energie der Autokorrelationsfunktion

Ein zweites wichtiges Kriterium ist der sogenannte Merit-Faktor MF, der als das Verhältnis der Energie des Hauptmaximums der Autokorrelationsfunktion zu der Energie des Restes der Autokorrelationsfunktion definiert wird [Lük92]:





Der Merit-Faktor beschreibt die rauschartigen Eigenstörungen durch verschobene Eingangssignale. Diese Störungen können zum Beispiel durch Mehrwegeempfang entstehen und zu einer falschen Quantisierung des Ausgangssignals des Korrelators im eingerasteten Fall führen.

2.6.3 Gutes periodisches wie auch aperiodisches Verhalten

Da nicht immer exakt vorhergesagt werden kann, welche Signalfolgen nach der Aussendung der die Information tragenden Zahlenfolge auftreten, sollte diese ein gutes periodisches Korrelationsverhalten haben, da dieser Fall bei der direkt aufeinanderfolgenden Übertragung von Symbolen auftritt.

Der Fall, daß nach Aussendung einer Zahlenfolge vom Sender keine weitere gesendet wird, kann entweder durch den Entwurf des Systems ausgeschlossen werden, oder die Zahlenfolge muß auch ein gutes aperiodisches Korrelationsverhalten aufweisen. Da die Codierung der zu übertragenden Information häufig durch Invertieren der Zahlenfolgen erfolgt, muß auch ein dritter Fall berücksichtigt werden: Wie verhält sich die Korrelationsfunktion, wenn immer abwechselnd invertierte und nichtinvertierte Zahlenfolgen ausgesendet werden. Probleme, die in diesem Fall auftreten können, werden im Kapitel über die Morse-Thue-Folge ausführlich beschrieben.

2.7 Aufbau eines Standard-Korrelators in Hardware

In der technischen Anwendung wird oft eine binäre Wertefolge verwendet. Die zu übertragende Information wird dann häufig in der Polarität der Signalfolge codiert. Das heißt, daß sowohl zur Übertragung einer binären 0 als auch zur Übertragung einer binären 1 dieselbe Signalfolge genutzt wird, allerdings wird sie in einem von beiden Fällen vor der Übertragung invertiert. Das Blockschaltbild eines solchen Senders ist in Fig. 1 dargestellt. In dem Beispiel wird die Information 101 mit Folgen der Form 1001 codiert. Zur Invertierung wird eine Exklusiv-Oder-Schaltung verwendet.

Der Takt, mit dem die Modellfolge erzeugt wird, ist höher als der Takt der Datenerzeugung. So werden für ein Datensymbol eine oder mehrere Wiederholungen der Codefolge übertragen. Durch die Synchronisation zwischen Folgen- und Datenerzeugung wird dafür gesorgt, daß die Datensymbole immer an den Grenzen der Codefolge wechseln.

Im Empfänger wird dann das empfangene Signal mit derselben Folge korreliert, die im Sender zur Codierung des Signals verwendet wurde. Nach erfolgter Korrelation kann die übertragene Information aus dem Vorzeichen der Korrelationsmaxima wiedergewonnen werden.

Für den Empfänger ist somit nicht der Verlauf der Korrelationsfunktion interessant, sondern nur das Vorzeichen der Maxima. Das Blockschaltbild eines solchen Empfängers ist in Fig. 2 dargestellt.

Die Zahlenwerte in der Figur stehen für die diskreten, abgetasteten Eingangsamplituden des Empfängers. Sie wurden zum einfacheren Verständnis als dezimale Werte dargestellt.

Die einfachste Schaltung zur Berechnung der Korrelation zwischen Referenzsignal m und gestörtem Eingangssignal x:





besteht aus einem Multiplizierer zur Berechnung des Produktes, aus einem Abtastwert des Eingangssignals x(k) mit einem Abtastwert des Referenzsignals m(k), einem Akkumulator zur Aufsummierung der Multiplikationsergebnisse und einem Generator zur Erzeugung des empfängerseitigen Referenzsignals. Der Codegenerator erzeugt eine zyklische Wiederholung des Referenzsignals:





Nach Maßgabe des Parameters n kann das Referenzsignal gegen das Eingangssignal verschoben werden. Die Schaltung berechnet in aufeinanderfolgenden Takten nicht den Verlauf der kompletten Korrelationsfunktion, sondern nur einen bestimmten Wert der Korrelationsfunktion (für einen einzigen Verschiebewert n).

Die Schaltung in Fig. 3 kann die Korrelation nicht selbständig durchführen. Sie ist auf die Steuerung durch einen Prozessor angewiesen. Zur Ermittlung der Korrelationsfunktion muß dieser die folgenden Schritte ausführen:

  • 1. Einstellen eines Verschiebewertes n
  • 2. Löschen des Akkumulatorregisters
  • 3. N (oder ein vielfaches von N) Eingangstakte warten
  • 4. Auslesen des Akkumulatorregisters
  • 5. Bewerten des Ergebnisses und, wenn nötig, Verändern des Verschiebewertes n
  • 6. weiter mit 2

Beim Betrieb eines Korrelationsempfängers muß zwischen zwei Betriebsfällen unterschieden werden:

  • 1. Nach dem Einschalten hat der Empfänger keine Information über die zeitliche Lage seines Referenzsignals in Bezug zu dem Signal des Senders. Er beginnt mit der Aquisitionsphase, in der der Empfänger versucht, auf das Eingangssignal zu synchronisieren. In der Aquisitionsphase muß der Empfänger ermitteln, für welchen Verschiebewert sich das Maximum der Korrelationsfunktion ergibt. Dies läuft auf ein Durchprobieren aller möglichen N Verschiebewerte hinaus.
  • 2. Wenn die zeitliche Synchronisation in der Aquisitionsphase hergestellt wurde, beginnt die Trackingphase, in der der Empfänger versucht, dem Eingangssignal zu folgen. In der Trackingphase muß der Empfänger nur noch Verschiebungen ausgleichen, die durch eine Abweichung der Taktgeber bei Sender und Empfänger oder möglicherweise durch Dopplerverschiebungen (bei bewegten Sendern oder Empfängers) entstehen. Dies wird häufig durch eine zusätzliche Korrelation mit zwei zeitlich um einen geringen Betrag verschobenen Versionen des Referenzsignals erzielt. Eine Version eilt der Sollphase voraus, die andere der Sollphase nach (die sogenannten Early- und Late-Signale). Durch Vergleich der Korrelationsergebnisse dieser drei Signale kann der Empfänger ermitteln, ob und in welcher Richtung die Signale des Senders abwandern. Das Prinzip dieses Verfahrens ist in Fig. 4 dargestellt.

    Hierbei wird angenommen, daß jede Bitstelle der Folge durch einen Rechteckimpuls einer endlichen Dauer dargestellt wird. Die Korrelationsspitze bei zwei solchen gegeneinander verschobenen Impulsen ist bekanntlich ein Dreieck. Im Falle einer optimalen Synchronisation befindet sich der Korrelationswert des On-Time-Signals auf der Spitze des Dreiecks, und die Werte für die verschobenen Early- und Late-Signale liegen ungefähr gleich hoch auf den Flanken des Dreiecks. Dieser Fall ist in der mittleren Figur dargestellt. Bei einer nicht optimalen Synchronisation verschiebt sich der Korrelationswert des On-Time-Signals von der Spitze weg. Jetzt kann durch einen Vergleich der Amplituden des Early- und Late-Signals festgestellt werden, in welche Richtung die Verschiebung erfolgt ist und wie diese korrigiert werden kann. Die Breite des Dreiecks in den Abbildungen entspricht dem Doppelten der Länge eines Bits der zur Übertragung verwendeten Symbolfolge.

2.8 Aufwandsprobleme mit dem Standardkorrelator

Zur Bewertung des Aufwandes können zwei unterschiedliche Aufwandsmaße herangezogen werden.

  • 1. Der schaltungstechnische Aufwand eines Empfängers.
  • 2. Der zeitliche Aufwand zur Erfassung des Eingangssignals (Länge der Aquisitionsphase).

Zuerst soll hier das zweite Maß betrachtet werden: Da der Empfänger in der Aquisitionsphase alle möglichen Verschiebungen von Eingangs- und Referenzsignal ausprobieren muß (siehe vorherigen Abschnitt), hängt der Zeitaufwand von der Länge des Referenzsignals N und der Taktrate TBIT ab, mit der die einzelnen Symbole des Referenzsignals ausgesendet werden. Die Übertragung einer einzelnen Folge dauert:



Tseq = N.TBIT (2.25)

Da jetzt noch N verschiedene mögliche Verschiebewerte durchprobiert werden müssen, dauert eine komplette Berechnung der Korrelationsfunktion somit



Taq = N.N.TBIT (2.26)

Am Beispiel des GPS-Systems mit einer Taktrate von 1,023 MHz und einer Folgenlänge von 1023 Bit dauert die Aquisitionsphase somit:





Wenn jetzt noch zusätzliche Unbekannte hinzukommen, wie beim GPS-System eine unbekannte Dopplerverschiebung oder die Notwendigkeit, die Signale von mehreren Satelliten gleichzeitig zu empfangen, kann die Aquisitionsphase auch mehrere Minuten dauern.

Die Betriebszeit des Senders (und des Empfängers) muß somit mindestens der Länge der Aquisitionsphase des Empfängers entsprechen.

Dies kann bei batteriebetriebenen Geräten, wie Mobiltelefonen oder Pagern, die nicht kontinuierlich Daten übertragen oder empfangen wollen, schnell zu einer Erschöpfung des Energievorrates führen.

Mögliche Lösungen zur Verringerung des Zeitaufwands bis zur Synchronisation werden in den folgenden drei Abschnitten dargestellt.

2.8.1 Nutzung einer dem FIR-Filter ähnlichen Struktur

Wenn man sich den Zusammenhang zwischen Korrelation und Faltung aus Abschnitt 2.4 betrachtet, so ist es naheliegend, eine Schaltung zu nutzen, die das Eingangssignal mit einem zeitlich gespiegelten Referenzsignal faltet. Eine Möglichkeit ist der Einsatz eines FIR-Filters. Dieses führt eine Faltungsoperation zwischen dem Eingangssignal und der Impulsantwort des Filters durch.

Für eine Folge der Länge N ist ein Filter mit einer Länge von N Taps (Tap = Stufe aus Verzögerungsglied, Multiplizierer und Addierer) nötig.

Diese Lösung bietet sich nur bei kurzen Folgenlängen und geringen Bitbreiten an, da der Aufwand schnell in nicht mehr vertretbare Größen ansteigt. Bekannt sind solche Korrelatoren aus der Radartechnik [Höl84].

2.8.2 Parallele Korrelatoren

Ein alternativer Ansatz besteht darin, alle möglichen Verschiebungen zwischen Eingangssignal und Referenzsignal parallel von mehreren gleichartigen Korrelatoren berechnen zu lassen. Bei k Korrelatoren muß jeder nur noch N/k Verschiebungen durchprobieren. Damit sinkt die Zeitdauer der Aquisitionsphase auf ein k-tel der Zeit, die ein einzelner Korrelator benötigen würde.

Im kommerziellen Einsatz befinden sich solche Korrelatoren mit bis zu 12 parallelen Kanälen. Nach erfolgter Synchronisation ist aber nur noch für drei Korrelatoren eine sinnvolle Aufgabe vorhanden (Korrelation mit On-Time, Early und Late-Signalen), die restlichen Stufen sind überflüssig.

In Fig. 6 steht jeder der 12 mit "Tracking Module Channel n" bezeichneten Funktionsblöcke für einen kompletten Korrelator. Die restlichen Funktionsblöcke dienen dem Transport der Daten von und zu den Korrelatoren.

Diese Lösung wird zum Beispiel in kommerziellen GPS-Empfängern eingesetzt, da die zusätzlichen Kanäle hier auch im späteren Trackingbetrieb von Nutzen sind (bei der Suche nach weiteren Satelliten und dem gleichzeitigen Empfang mehrerer Satelliten). Der Zeitgewinn ist allerdings bei langen Folgen deutlich kleiner als bei der ersten Lösung in Abschnitt 2.8.1. Zusätzlich steigt auch der Bedarf an Rechenleistung proportional zu der Anzahl der Kanäle, da die Steuerung der Hardware durch den Prozessor des Systems erfolgen muß.

2.8.3 Ermittlung der Korrelationsfunktion mit Hilfe von Transformationen

Eine weitere Möglichkeit zur Verringerung des Aufwandes bei der Berechnung der Faltung zwischen Eingangssignal und Referenzsignal besteht darin, die Faltung nach einer Integraltransformation durch eine Multiplikation im Frequenzbereich durchzuführen.

Eine Faltung im Zeitbereich läßt sich durch eine Multiplikation im Frequenzbereich durchführen:



x(n).y(n)⊶X(n)Y(n) (2.28)

Das heißt, die Faltungsoperation läßt sich durch eine Transformation der Signale in den Frequenzbereich, eine Multiplikation der transformierten Signale und eine anschließende Rücktransformation in den Zeitbereich durchführen (Fig. 7).

Wenn sich das Referenzsignal nicht ändert oder es nur eine beschränkte Anzahl von verschiedenen Referenzsignalen gibt, kann direkt die in den Frequenzbereich transformierte Version gespeichert werden. Dann ist nur noch die Hin- und Rücktransformation und die Multiplikation der Signale nötig.

Wenn zur Berechnung der Transformationen in den Frequenzbereich eine Radix 2 FFT eingesetzt wird [Ste84], die einen Rechenaufwand von N ld(N) hat, so benötigt die Berechnung der kompletten Korrelationsfunktion einen Aufwand von N+2 N ld(N) Multiplikationen. Bei längeren Folgen ist dies eine deutliche Einsparung gegenüber den N2 Multiplikationen, die für eine direkte Berechnung nötig wären. Die Verringerung des Aufwandes beträgt dabei ungefähr N/ld(N) oder 100 zu 1 bei einer Folgenlänge von 1024.

Damit bietet sich diese Lösung für eine Softwarerealisierung mittels eines Signalprozessors an, da Signalprozessoren durch ihre Hardwareausstattung die Berechnung des Produktes von Zahlenfolgen und die Berechnung der nötigen Transformationen unterstützen. Eine Realisierung eines Korrelators mit kurzer Aquisitionsphase auf einem Signalprozessorsystem ist in [Vog95] am Beispiel eines Empfängers für die DCF77 Phasenmodulation dargestellt.

Um einen Korrelator durch Transformation in Hardware zu realisieren, ist der Aufwand aufgrund der vielen zur Berechnung der Fouriertransformation benötigten Multiplikationen immer noch sehr hoch.

Anstelle der Fouriertransformation kann auch eine andere Transformation eingesetzt werden, welche die Bedingung erfüllt, daß eine Multiplikation im Transformationsbereich einer Faltung in Originalbereich entspricht. Ein Beispiel für eine Klasse von Transformationen, die sich wegen des Verzichts auf Multiplikationen gut für eine Realisierung in Hardware eignet, sind die zahlentheoretischen Transformationen (NTT Number Theoretic Transforms) [MWMT97]. Aufgrund ihrer Eigenschaft, daß die benötigte Bitbreite mit der Länge der Transformation ansteigt (mit 32-Bit-Arithmetik läßt sich bei einer NTT mit α von 2 nur eine Transformation der Länge 64 realisieren, für eine Transformation der Länge 1024 wäre eine 512-Bit-Arithmetik erforderlich), erfordern NTTs bei längeren Transformationen jedoch komplexe, mehrdimensionale Strukturen.

Solange keine Vereinfachungen an den Berechnungsvorschriften vorgenommen werden, kann von den beiden Aufwandsmaßen immer nur eines auf Kosten des anderen optimiert werden. Geringer Aufwand bedeutet eine lange Aquisitionsphase und umgekehrt.

Kapitel 3. Entwicklung von Lösungen mit geringerem Rechenaufwand

Nachdem im vorangegangenen Kapitel die mathematischen Grundlagen der Korrelation und bekannte Konzepte zum Aufbau eines Korrelationsempfängers beschrieben wurden, sollen in den folgenden Abschnitten Vereinfachungen an den Gleichungen zur Berechnung der Korrelation durchgeführt werden. Ziel ist es, Strukturen zu finden, die ohne aufwendige Operationen wie Multiplikationen auskommen.

3.1 Übergang zu zweiwertigen Referenzsignalen

Bei einer schnellen Hardwarerealisierung fallen insbesondere der Platzbedarf für die Multiplizierer ins Gewicht. Für einen Korrelator einer Folge der Länge K als FIR-Filter werden K-1 Addierer und K Multiplizierer benötigt. Im Gegensatz zu Addierern, deren Platzbedarf linear mit der Bitbreite wächst (ein N-Bit-Addierer hat somit einen Platzbedarf von N Funktionsblöcke. Die Größe eines Funktionsblockes hängt von der verwendeten Addiererstruktur und der gewählten Technologie ab. Bei Verwendung von XilinX-FPGA-Bausteinen kann ein Funktionsblock einem CLB gleichgesetzt werden), benötigt ein N×N-Multiplizierer einen Platzbedarf von N2 Funktionsblöcken. Der Platzbedarf steigt proportional zum Quadrat der Bitbreite.

Der schaltungstechnische Aufwand für den kompletten Korrelator ist dann durch



A = (K - 1)N + KN2 ≈ K(N+1)N (3.1)



Funktionsblöcke gegeben.

Um diesen Platzbedarf zu verringern, kann die Auflösung des Referenzsignals verringert werden. Wenn weniger als N Bit genutzt werden, verringert sich der Aufwand für die Multiplikation entsprechend (d. h. wenn die Auflösung des Referenzsignals halbiert wird, sinkt der Aufwand auf ein Viertel). Wenn dieser Weg in Gedanken weitergegangen wird, kann das Referenzsignal auf die Information beschränkt werden, ob das Signal größer oder kleiner als Null ist. Das Referenzsignal enthält dann nur noch die Vorzeicheninformation des Originalsignals.





Dieses Referenzsignal m(i) ist dann ein zweiwertiges (binäres) Signal. Aber x(k) muß nicht binär sein. Es ist im allgemeinen eine analoge Größe.

Zur Speicherung dieses zweiwertigen Referenzsignals wird nur noch ein Bit benötigt. Die Multiplikation wird durch eine Stufe ersetzt, die in Abhängigkeit des Referenzsignals das entsprechend verzögerte Eingangssignal entweder unverändert läßt oder invertiert.

Dies ist in Fig. 8 dargestellt. Für die mit S1-SN bezeichneten Funktionsblöcke kommen anstelle der platzintensiven Multiplizierer jetzt nur noch einfache Inverter zum Einsatz. Im Falle analoger Signale x(k) müssen das dann lineare Inverter sein.

Das Maximum der Korrelation ergibt sich dann im Unterschied zu Gleichung 2.10 jetzt zu





Für Werte von |x| < 1 führt das zu entsprechend höheren Maximalwerten.

Aus Fig. 8 und seiner Beschreibung kann man ein allgemeines Prinzip ableiten, das "Stapeln" genannt werden soll:

Die Abtastwerte des empfangenen Signals werden in Abhängigkeit eines Referenzsignals (Schlüssels) so mit positiven oder negativen Vorzeichen versehen und addiert, daß im Falle der optimalen Korrelation ein maximales Ergebnis entsteht, das der Summe der diskreten Absolutwerte entspricht.

Abhängig davon, ob die Invertierung mit in die Addierer integriert werden kann oder nicht, beträgt der schaltungstechnische Aufwand für den vereinfachten Korrelator nur noch



A = (K - 1)N + KN ≈ 2KN (3.4)



Funktionsblöcke für den Fall einer getrennt notwendigen Invertierung, oder



A = (K - 1)N ≈ KN (3.5)



Funktionsblöcke für den Fall einer Invertierung in den Addiererstufen.

Wenn zum Beispiel das Referenzsignal bei den Standardverfahren mit 8 Bit quantisiert ist, dann sinkt der Aufwand bei einem Übergang zu einem binären Referenzsignal auf ca. 10%. Benutzt man in der Schaltung nur noch Addierer oder Subtrahierer, so ändert sich der Schaltungsaufwand nicht direkt, aber das Design wird regulärer.

3.2 Korrelationsermittlung durch Stapeln von Impulsen

Eine günstige Realisierung des Prinzips des Stapelns aus Abschnitt 3.1, besteht darin, daß nur noch Subtrahierer benutzt werden. Wenn die Zahlenfolge gleichanteilsfrei ist, so enthält sie genauso viele positive wie negative Werte. Dann kann jeweils ein positiver und ein negativer Wert zu einem Paar zusammengefaßt werden. Wenn jetzt die beiden Werte eines Paares so voneinander abgezogen werden, daß wieder gleich viele positive wie negative Werte entstehen, dann hat die Ergebnisfolge die gleiche Struktur wie die Originalfolge. Der Betrag der Subtraktionsergebnisse ist bei dieser Operation größer als der Betrag der Eingangswerte. Dieser Vorgang kann jetzt iterativ so lange wiederholt werden, bis nur noch ein einziger, sehr großer Wert übrigbleibt (Fig. 9).

Die Paare müssen nicht wie in diesem Beispiel unmittelbar benachbart sein. Es ist auch jede andere Zusammenfassung möglich, bei der die Beträge der Differenzen größer sind als die Beträge der Einzelimpulse (Forderung 1) und die gleichzeitig als Ergebnis wieder eine gleichanteilsfreie Folge erzeugen (Forderung 2).

Um die Paare zu bilden, bieten sich zwei Verfahren an. Die Werte des Eingangssignals können in einer ersten Stufe in ihrem Vorzeichen angepaßt oder zeitlich verschoben werden. Dann werden in weiteren Stufen nur noch Subtraktionen durchgeführt.

In Fig. 10 ist dargestellt, woher das Verfahren seinen Namen hat. Wenn man sich die Eingangsimpulse als Bauklötze vorstellt, so werden durch die Differenzbildungen Schritt für Schritt immer größere "Impulsstapel" erzeugt. Für die Figur wurde immer der erste Impuls der zweiten Signalhälfte von dem ersten Impuls der ersten Signalhälfte abgezogen. Dann wurde dieselbe Operation auf die entstehende, kürzere Folge angewendet und so weiter.

An der Anzahl der nötigen Operationen ändert sich im Vergleich zu einem Korrelator mit zweiwertigem Referenzsignal nichts. Trotzdem ist dieses Verfahren günstig für die Anwendung, da sich die immer wiederholenden Operationen durch eine einfache Programmstruktur oder die gute Nutzung von Vektorarithmetikeinheiten wie der MMX-Einheit der neueren Intel- Pentium®-Prozessoren auszeichnen. Diese Recheneinheit kann dieselbe Operation mit einem Befehl auf bis zu acht Datenworten ausführen. Auf eine Softwareimplementierung auf einem Intel-Pentium®-Prozessor mit MMX-Einheit wird in Abschnitt 3.4 eingegangen.

Um ein beliebiges Eingangssignal in die für das Stapelverfahren nötige Form zu bringen, können die Impulse entweder zeitlich umsortiert werden oder in einem Vorverarbeitungsschritt durch Invertierungen in die passende Polarität umgewandelt werden.

Ob die Signale besser durch Invertierungen oder zeitliches Verschieben in eine passende Form überführt werden können, hängt von der Form des Eingangssignals ab.

Der eigentliche Stapelvorgang erfordert ein gleichanteilfreies Signal. Wenn auch das binäre Referenzsignal gleichanteilfrei ist, erscheint es günstig, die Anpassung durch eine zeitliche Umsortierung der Eingangsimpulse durchzuführen, da dies keine zusätzlichen arithmetischen Operationen erfordert.

Wenn das Referenzsignal einen Gleichanteil besitzt oder ein variables Referenzsignal gefordert wird (z. B. für einen Codevielfachzugriff [HILi97]), sind (einstellbare) Inverterstufen die bessere Lösung.

Dieses Verfahren läßt sich einfach sowohl in Hard- als auch in Software realisieren. Eine mögliche Realisierung in Hardware ist in Fig. 11 dargestellt. Zuerst werden die zeitdiskreten Eingangssignale in einem Schieberegister zwischengespeichert. Bevor in den Funktionsblöcken "Differenzenbildungen" und "Detektion des Maximums" der eigentliche Stapelvorgang abläuft, wird im Block "Differenzen mit Hilfe des Vertauschungsschlüssels" die erste Differenzenbildung mit durch den Vertauschungsschlüssel verwürfelten Indizes durchgeführt.

Eine weitere Möglichkeit ist der Einsatz des Verfahrens in einer nichtdigitalen Umgebung. In diesem Fall wird aus dem Schieberegister in Fig. 11 eine Verzögerungsleitung, und aus den digitalen Subtrahierern werden analoge Differenzenverstärker. Eine solche Realisierung ist besonders für Signale interessant, die außerhalb des Frequenzbereichs liegen, der mit digitalen Schaltungen verarbeitet werden kann.

Dieses Prinzip kommt auch bei der speziell angepaßten Version für die Morse-Thue-Folge in Abschnitt 5.3 zum Einsatz. In diesem Fall kann auf den Vertauschungsschlüssel verzichtet werden, da die Eingangsfolge schon die gewünschte Form hat.

3.3 Beispiel eines Stapeldecoders mit Vertauschen

Im folgenden soll am Beispiel einer relativ kurzen PRN-Folge der Ablauf des Stapeldecoders mit Vertauschen erläutert werden. Die im Beispiel verwendete Folge basiert auf der M- Sequenz (eine M-Sequenz (von Maximum-Length Sequence) ist die längste, sich nicht wiederholende Binärfolge, die mit einem N-Bit-Schieberegister erzeugt werden kann. Sie hat eine Länge von 2N-1), die mit einem rückgekoppelten Schieberegister der Länge 4 erzeugt werden kann. Diese Folge hat eine Länge von 15 und lautet:



1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 -1

Diese Zahlenfolge eignet sich direkt noch nicht für den Einsatz in einem Stapeldecoder, da sie nicht gleichspannungsfrei ist (die Folge enthält 8 mal den Wert 1 und 7 mal den Wert -1). Um zu einer gleichspannungsfreien Folge zu kommen, soll die Folge hier, ähnlich dem Verfahren, das bei dem Zeitzeichensender DCF77 verwendet wird [Hetz93], um einen zusätzlichen -1- Wert am Anfang der Folge ergänzt werden. Die komplette Folge sieht also so aus:



-1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 -1

Die mit MatLab berechnete periodische Autokorrelationsfunktion dieser veränderten Folge ist in Fig. 12 dargestellt.

Die Nebenwerte dieser Folge sind größer als bei der Original-PRN-Folge, aber mit einem HNV von 4 ist die Folge immer noch gut zur Datenübertragung geeignet (bei längeren Folgen fällt der Anstieg der Nebenwerte nicht so stark auf, wie bei der kurzen Beispielfolge). In Fig. 13 ist jetzt der Ablauf des Stapeldecoders mit der Beispielfolge dargestellt. In der ersten Zeile ist die Beispielfolge abgebildet. Durch die Pfeile wird die Vertauschung dargestellt, mit der die (pseudo-)zufällige Zahlenfolge in eine MT-Folge (siehe auch Kapitel 4) umgewandelt wird, die die Eigenschaft hat, daß man immer ihre hintere von ihrer vorderen Hälfte vorzeichenrichtig abziehen kann. Der gezeigte Vertauschungsschlüssel ist nur einer von vielen möglichen und wurde danach ausgewählt, daß möglichst viele Folgenwerte an ihrer Position bleiben.

Wenn jetzt die Eingangswerte in der ersten Zeile verschoben werden, erscheinen am Ausgang des Decoders die weiteren Werte der Korrelationsfunktion.

3.4 Softwareimplementierungen eines Stapeldecoders

Um den Vorteil des Stapelkorrelators auf einer SIMD-Architektur (Single Instruction Multiple Data) zu demonstrieren, wurde eine Implementierung in C++ mit einer Implementierung mit dem MMX-Befehlssatz der Firma Intel verglichen.

Die MMX-Einheit wurde von Intel implementiert, um die Ablaufgeschwindigkeit von rechenintensiven Algorithmen aus dem Grafik- und Multimediabereich zu erhöhen. Bei diesen Anwendungen ist es in vielen Fällen erforderlich, die gleiche Operation (z. B. eine Differenzbildung oder eine Skalierung) auf viele Operanden (z. B. Bildpunkte) anzuwenden. Deshalb wurde für diese Anwendungen der Befehlssatz der CPU um Operationen erweitert, die eine Operation auf bis zu acht Operanden gleichzeitig anwenden. Dieses Prinzip wurde auch schon in den Vektorrechnern der "Großrechnerzeit" zur Beschleunigung von Algorithmen eingesetzt. Alle MMX-Befehle können Ganzzahloperanden mit einer Breite von 8 bis 32 Bit und Vektorlängen von 32 oder 64 Bit verarbeiten. Je nach Breite der Einzeloperanden können bis zu acht Operationen (64 Bit Vektorlänge erlauben 8 Operationen auf 1 Byte langen Operanden) mit einem Befehl ausgeführt werden. Dadurch kann die Ausführungszeit eines Algorithmus im Idealfall auf ein Achtel gesenkt werden.

Die Implementierung des Stapeldecoders ist eine solche "ideale" Anwendung. Da nach dem ersten Schritt, in dem die Vertauschungen durchgeführt wurden, nur noch eine Operation (die Subtraktion) auf alle Operanden angewendet wird, kann die Anwendung großen Nutzen aus dem MMX-Befehlssatz ziehen.

Es wurden zwei verschiedene Versionen des Stapeldecoders realisiert und mit der Laufzeit einer Implementierung in der Programmiersprache C++ verglichen.

Die erste, flexiblere Implementierung erlaubt es, die Länge der zu verarbeitenden Folgen durch Übergabeparameter einzustellen. Es wurden Routinen entwickelt, die mit 8 oder 16 Bit breiten Operanden (char und short in C++) arbeiten können. Die C++-Version des Faltungsdecoders unterscheidet sich von der MMX-Version nur in der innersten Routine, die in der C++-Version in Abhängigkeit von der Operandenbreite vier oder acht Subtraktionen in einer Schleife ausführt. In der MMX-Version ist diese innerste Schleife in Assembler codiert.

Die zweite Implementierung ist auf Folgen der Länge 64 festgelegt und soll die maximale Beschleunigung demonstrieren, die durch Einsatz der MMX-Befehle möglich ist. Da jeder MMX-Befehl hier gleichzeitig 8 Bytes bearbeitet, sinkt die Anzahl der nötigen Befehle, und es kann hier auf Schleifen und Vergleiche verzichtet werden (Loop Unrolling).

Eine genauere Beschreibung des Programms und ein Abdruck des Quellcodes des Programms finden sich in Anhang D.1.

Zum Verständnis der Werte in Tabelle 1 sei hier nur so viel gesagt, daß die (eigentlich unmöglichen) negativen Werte auf Seiteneffekten der MMX-Befehle des verwendeten Prozessors beruhen.

Alle Zeiten wurden auf einer Zweiprozessormaschine mit zwei Pentium-MMX-Prozessoren mit 166 MHz gemessen. Vergleichsmessungen auf einer Einprozessormaschine ergaben vergleichbare Resultate. Alle Zeiten sind in Sekunden für 100.000 Schleifendurchläufe angegeben. Tabelle 1 Laufzeiten der verschiedenen Implementierungen des universellen Stapeldecoders mit 16-Bit-Operanden und einer Folgenlänge von 1024



Die Zeiten sind in Fig. 15 nochmals grafisch dargestellt. Man erkennt deutlich die kürzere Laufzeit der MMX-Routinen (die linken fünf Meßpunkte) im Vergleich mit den C++- Versionen.

Man kann deutlich sehen, daß es einen großen Einfluß auf die Laufzeiten hat, ob die Daten im Cache des Prozessors vorhanden sind oder nicht. Wenn man aber die jeweils besten Zeiten vergleicht, die die C++- und die MMX-Version unter gleichen Randbedingungen erreichen (in der Tabelle grau hinterlegt), kann man eine Verringerung der Rechenzeit auf ca. 25-35% erkennen. Dies entspricht recht gut dem theoretischen Wert von einer Reduzierung der Rechenzeit auf 25% bei der Parallelausführung von vier Operationen.

Wenn man sich auf relativ kurze Folgen von bis zu 64 Werten beschränkt, bei denen 8 Bit zur Darstellung der Werte ausreichen, so kann man den Geschwindigkeitsgewinn zwischen einer Implementierung in C++- und einer optimierten MMX-Version deutlich erhöhen. In der zweiten Beispielimplementierung in Tabelle 2 und Fig. 16 wurde eine auf die Bearbeitung von Folgen mit 64 Werten optimierte Version erstellt. Die Routine verzichtet auf Schleifen, um eine maximale Ablaufgeschwindigkeit zu erzielen.

Da die MMX-Befehle gleichzeitig bis zu acht Werte bearbeiten, hält sich der hierfür benötigte Platz in Grenzen. Die durch das lineare Programm erhöhte Codegröße fällt bei solch kurzen Folgen nicht ins Gewicht. Bei der C++-Version ist ein "Loop Unrolling" aus Gründen der Codegröße nicht praktikabel.

Alle Zeiten sind wieder in Sekunden, diesmal aber für 1.000.000 Schleifendurchläufe angegeben. Der Quellcode dieses Programms ist in Anhang D.2 abgedruckt. Tabelle 2 Laufzeit der verschiedenen Implementierungen des optimierten Stapeldecoders mit 8-Bit-Operanden und einer Folgenlänge von 64



Bei diesem Programm ist das Auftreten der Laufzeitanomalie unabhängig von den Optimierungen des Compilers. Wenn man hier die realistische Zeit ihr die optimierte MMX- Version mit der besten Laufzeit der C++-Version vergleicht (in der Tabelle wieder grau hinterlegt), so ergibt sich für die MMX-Version eine Laufzeit, die um den Faktor zwanzig kleiner ist als die der C++-Version. Davon entfällt ein Faktor von 8 auf die Beschleunigung durch die Parallelverarbeitung und der Rest auf den Geschwindigkeitsgewinn durch das "Loop-Unrolling".

Auf entsprechenden Maschinenarchitekturen, wie der Intel-MMX-Architektur oder Signalprozessoren mit einer SIMD-Architektur, kann durch Einsatz des Stapelverfahrens ein deutlicher Laufzeitvorsprung erzielt werden.

Kapitel 4. Die Morse-Thue-Folge

Nachdem im vorangehenden Kapitel Methoden untersucht wurden, um den Aufwand zum Aufbau eines Korrelationsempfängers durch Modifikationen am Referenzsignal und der Berechnungsreihenfolge zu verringern, soll in diesem Kapitel untersucht werden, ob der Rechenaufwand nicht noch weiter verringert werden kann, wenn zur Codierung der Information Folgen mit einfachen, bekannten Bildungsgesetzen verwendet werden. Als erste solche Folge soll die Morse-Thue-Folge untersucht werden.

Die Morse-Thue-Folge wurde von Axel Thue im Jahre 1912 [Thu1] bei seiner Beschäftigung mit formalen Sprachen entdeckt. Dieselbe Folge wurde von Marston Morse [Mor1] im Jahre 1917 bei der Untersuchung der Dynamik von Geodäten (auf einer Oberfläche ist ein Geodät das Gegenstück einer geraden Linie in der Ebene. Bei der Bewegung entlang eines Geodäten auf der Oberfläche glauben wir, dem direktesten Pfad zu folgen. Zum Beispiel sind die Geodäten auf einer Kugel die Breitengrade) auf Oberflächen wiederentdeckt.

4.1 Erzeugung

Zur Erzeugung der Morse-Thue-Folge sind verschiedene Verfahren in der Literatur geläufig. Sie seien hier einmal aufgezählt:

  • 1. Durch invertiertes Anhängen. Beginnend mit einer einzelnen 1 wird die Folge durch inverses Anhängen der bestehenden Folge verlängert: Aus 1 wird 10, aus 10 wird 1001, aus 1001 wird 10010110 usw.
  • 2. Das n. Symbol der Morse-Thue-Folge läßt sich aus der ungeraden Parität der Binärdarstellung von n ermitteln: p(0) = 0, p(1) = 1, p(2) = 1. . .
  • 3. Mit der Darstellung pn = (-1)t mit t als Anzahl der Einsen in der Binärdarstellung von n ergibt sich eine Morse-Thue-Folge mit den binären Symbolen 1 und -1.

Alle folgenden Verfahren sind mit 0 und 1 als Symbolen angegeben. Durch einfaches Ersetzen können sie in die 1 und -1-Version umgewandelt werden.

  • 1. In Abwandlung von 2. kann man auch wie folgt vorgehen: Sei n eine Binärzahl und n0 bis nk ihre Binärstellen, was man auch so schreiben kann n = (nk, . . ., n0)2, so ergibt sich 2n = (nk, . . ., n0,0)2 und 2n+1 = (nk, . . ., n0,1)2. Das Symbol mi an der Stelle i der Morse-Thue- Folge erhält man rekursiv aus:



    m0 = 0

    m2n = mn

    m2n+1 = 1-mn

  • 2. Für Mathematiker ist ein anderer Ansatz bekannter. Hier benutzt man L-Systeme zur Beschreibung von Symbolfolgen. L-Systeme sind dynamische symbolische Systeme, die 1968 von A. Lindenmayer [Lin68] zur Beschreibung biologischer Wachstumsprozesse entwickelt wurden. L-Systeme werden mit den folgenden Bestandteilen beschrieben:

Dem Alphabet

Das Alphabet V ist eine endliche Menge an formalen Symbolen wie Buchstaben (a, b, c. . .) oder binären Symbolen (0, 1).

Den Axiomen

Das Axiom, auch Initiator genannt, ist eine Kette ω von Symbolen aus V. Die Menge von Ketten, auch Worte genannt, aus V wird mit V* bezeichnet. Mit V = {a, b, c} sind Beispiele für Worte aabca, caab oder bbc. . . Die Länge eines Wortes |ω| ist die Anzahl von Symbolen in diesem Wort.

Den Produktionen

Eine Produktion (oder Umwandlungsregel) ist eine Abbildung eines Symbols α&isin;V zu einem Wort ω&isin;V*. Diese Regeln werden in der folgenden Notation geschrieben:



p: α → ω

Möglich sind auch Abbildungen von α in ein leeres Wort (geschrieben &empty;) oder auf α selbst. Wenn für ein Symbol α&isin;V keine Produktion existiert, wird angenommen, daß es auf sich selbst abgebildet wird. In diesem Fall ist α eine Konstante des L-Systems.

Die Beschreibung des Morse-Thue-L-Systems sieht folgendermaßen aus:



V = {0, 1}



ω = 1



p1: 0 → 01



p2: 1 → 10.



D. h. von einer gegebenen Folge wird jede 0 durch 01 und jede 1 durch 10 ersetzt usw.

4.2 Eigenschaften

Die Morse-Thue-Folge weist einige Besonderheiten auf:

  • 1. Eine Folge der Länge 2N enthält immer genauso viele 0 wie 1 Symbole, d. h. wenn im Übertragungskanal die Symbole 1 und 0 mit komplementären Pegeln (z. B. ±1 V) codiert werden, ist die Morse-Thue-Folge gleichspannungsfrei.
  • 2. Eine Folge der Länge 2N kann man N-1 mal summieren oder integrieren und erhält dabei stets ein gleichspannungsfreies Ergebnis.
  • 3. Mit jeder Integration der Folge halbiert sich die Anzahl der Vorzeichenwechsel in der Folge.
  • 4. Es gibt in der Morse-Thue-Folge keine Teilfolge der Form 111 oder 000 [MH1], d. h. nach spätestens zwei Symbolen erfolgt ein Symbolwechsel.
  • 5. Auch wenn sich die Morse-Thue-Folge nie komplett wiederholt, also nicht periodisch ist, kann gezeigt werden, daß jede Teilfolge der Morse-Thue-Folge der Längen in einer Teilfolge der Länge N (üblicherweise viel größer als n) wieder auftritt. Als Abschätzung für N kann folgendes angenommen werden: Sei k die kleinste ganze Zahl, bei der 2k ≥ n gilt, dann kann garantiert werden, daß in jeder Folge der Länge 2k+4 die Folge ω der Länge n enthalten ist. Die Morse-Thue-Folge weist somit eine hohe Redundanz auf.
  • 6. Entfernt man jeden zweiten Wert aus einer Morse-Thue-Folge, so entsteht wieder eine Morse-Thue-Folge.
  • 7. Die Morse-Thue-Folge ist eine besonders einfache eindimensionale fraktale Funktion [HIL91].

4.3 Autokorrelationsfunktion der Morse-Thue-Folge

In Abschnitt 2.6 wurde die Autokorrelationsfunktion als wichtiges Hilfsmittel zur Bewertung der Eignung einer Folge für die Datenübertragung vorgestellt. Zur Bewertung der Morse- Thue-Folge ist in Fig. 17 die Autokorrelationsfunktion der Morse-Thue-Folge dargestellt.

Man erkennt, daß die Autokorrelationsfunktion der Morse-Thue-Folge von dem gewünschten Ideal einer Funktion mit einem einzigen Maximum und minimalen Nebenwerten deutlich abweicht. Trotzdem ist der Abstand des höchsten Maximums von dem nächsthöheren Nebenmaximum mit einem Faktor zwei für viele Anwendungen noch ausreichend hoch, um im technischen Einsatz eine sichere Unterscheidung des Hauptmaximums von den Nebenmaxima zu ermöglichen.

Kapitel 5. Decoder für die Morse-Thue-Folge

In den folgenden Abschnitten sollen verschiedene Möglichkeiten beschrieben werden, um binäre Informationen, die in Form von Morse-Thue-Folgen dargestellt werden, auf der Empfängerseite wieder in die Ursprungsform zurückzuwandeln.

5.1 Decodierung durch Integration

Die Grundidee dieses Verfahrens, das zuerst in [HILi96] vorgeschlagen wurde, ist es, die Morse-Thue-Folge durch wiederholte Integration zu decodieren. Entstanden ist die Idee aus der Beschäftigung mit der sogenannten hut-Funktion. Diese wurde von W. Hilberg 1971 [HIL71] bei der Untersuchung von Impulsen, die sich durch Integration oder Differentiation in einem veränderten Zeitmaßstab reproduzieren, entdeckt. Die hut-Funktion läßt sich durch vielmalige Integration einer Folge von Impulsen beliebiger Form gewinnen, deren Vorzeichen der Morse-Thue-Folge gehorcht. Im Bereich der diskreten Werte 1 und -1 entspricht das einem wiederholten Aufsummieren der Werte der Morse-Thue-Folge. Bezeichnet man mit D eine aufsummierte Morse-Thue-Folge, numeriert ihre Werte mit dem Index i und unterscheidet mit dem Index j die Ebenen (die Anzahl der bisher durchgeführten Summationen) des Decoders (Di,0 entspricht dabei der originalen Morse-Thue-Folge), so ergibt sich:





In den folgenden Figuren sind die Ergebnisse der einzelnen Decoderebenen für eine Folge der Länge 256 dargestellt, die wie folgt beginnt:



+1 -1 -1 +1 -1 +1 +1 -1 -1 +1 +1 -1 +1 -1 -1 +1. . .

Man kann deutlich die beiden Eigenschaften 2 (Gleichspannungsfreiheit der ersten N-1 Ebenen) und 3 (Halbierung der Vorzeichenwechsel) aus Abschnitt 4.2 erkennen.

Die Information kann nun in dem Vorzeichen des Startwertes der Morse-Thue-Folge übertragen werden, so wie es auch bei Modulationen mit PRN-Folgen üblich ist.

Die Übertragung des eine Information tragenden Bitmusters 10110 ergibt nach 8 Integrationen die folgenden Ergebnisse, siehe Fig. 27:

Man erkennt deutlich, daß die Werte der übertragenen Bits in den Vorzeichen der bei der Summation entstehenden "Hüte" steckt.

5.2 Stabilitätsprobleme des Integraldecoders

Das oben beschriebene Verfahren der Demodulation durch wiederholte Summation weist eine wesentliche Schwachstelle auf. Es ist nämlich sehr anfällig für zusätzliche Gleichspannungskomponenten im Signal oder seinen Integralen. Auch wenn die Morse-Thue-Folge selbst in allen Integralen gleichspannungsfrei ist (siehe Abschnitt 4.2), können sich Störkomponenten im Signal katastrophal aufsummieren [Kerk91].

Um ein bekanntes Beispiel aus der Praxis zu nehmen, wurde für die weitere Untersuchung als Störsignal die PRN-Folge verwendet, die zur Datenübertragung beim Langwellensender DCF77 dient. Diese Pseudozufallszahlenfolge wird mit einem rückgekoppelten Schieberegister erzeugt, ist gleichspannungsfrei und besitzt eine Länge von 512 Bit [Hetz93]. In den folgenden Figuren wird allein dieses Störsignal mehrfach aufsummiert.

Die Störung hat sich nach der vierten Summation auf Werte im Bereich von 107 aufsummiert, während bei der Morse-Thue-Folge, wie in Fig. 22 gezeigt, nach ebenfalls vier Summationen die Maximalwerte noch kleiner als 100 sind.

Der aus diesen Ergebnissen in der oben genannten Studienarbeit gezogene Schluß, die Morse- Thue-Folge eigne sich nicht zur Informationsübertragung, ist allerdings voreilig. Wie im Folgenden gezeigt wird, ist nur das dort untersuchte Verfahren ungeeignet.

In den folgenden Abschnitten soll ein neues Verfahren zur Decodierung der Morse-Thue- Folge vorgestellt werden, das die Instabilitäten des Integrationsverfahrens nicht aufweist.

5.3 Decodierung durch rekursives Stapeln

Die Idee des im Rahmen dieser Arbeit entwickelten Morse-Thue-Stapeldecoders [Wol98] entstand aus der Umkehrung des Generierungsprozesses der Morse-Thue-Folge. Die Folge, die durch wiederholtes invertiertes Anhängen entstanden ist, kann durch wiederholtes Teilen und Subtrahieren decodiert werden. Dieser Ablauf soll anhand von Fig. 33 erläutert werden.

Dazu sei in der ersten Zeile eine Folge von empfangenen Werten X0 bis X7 gegeben. Sie enthalte sowohl die gesendete Morse-Thue-Folge als auch mögliche Störungen. Man subtrahiert nun die Symbole der zweiten Hälfte von den Symbolen der ersten Hälfte, siehe die zweite Zeile. Man erhält dann in der dritten Zeile eine Folge, die genau halb so viele Werte enthält wie die ursprüngliche Folge. Im nächsten Schritt wird auch bei dieser Folge die zweite Hälfte von der ersten abgezogen. Diese Operation wird solange ausgeführt, bis nur noch ein einzelner Wert übrig ist.

Der Wert, den man als Endergebnis erhält, ist die Kreuzkorrelation zwischen den Werten der empfangenen Folge (eine Morse-Thue-Folge plus eventuelle Störungen) und der Morse-Thue- Folge selbst:





Ein Beispiel für die Signale, die sich am Ausgang eines Stapeldecoders ergeben, wenn eine Nutzinformation 1010 empfangen wird, wobei jedes Bit durch eine Morse-Thue-Folge der Länge 256 codiert ist, ist in Fig. 34 dargestellt.

Zum Vergleich ist in Fig. 35 der Zeitverlauf auch mit der klassischen Korrelationsformel im Programm MatLab berechnet worden. Die Figur unterscheidet sich von der vorangehenden Figur am Anfang und am Ende, da MatLab die verschobenen Folgen dort mit zusätzlichen Nullen auffüllt.

Als weiteres Beispiel für die Ergebnisse am Ausgang des Stapeldecoders ist in Fig. 36 das Ergebnis bei einer ungestörten Übertragung der mit Morse-Thue-Folgen codierten Information 1001 dargestellt. Dabei ist deutlich zu erkennen, daß bei der Übertragung einer Folge gleicher Nutz-Bitwerte (im Beispiel 00) ein zusätzliches Maximum am Ausgang des Decoders entsteht. Diesen Effekt kann man sich einfach veranschaulichen, wenn man sich die Aneinanderreihung von zwei Morse-Thue-Folgen ansieht. Eine Morse-Thue-Folge der Länge 4 sieht so aus: 1001. Zwei solche Folgen hintereinander übertragen ergeben dann 10011001. Der unterstrichene Teil in der Mitte stellt auch wieder eine Morse-Thue-Folge der Länge 4 dar. Sie führt zu dem in Fig. 36 erkennbaren Phantommaximum im halben zeitlichen Abstand. Man kann es deshalb leicht erkennen und eliminieren.

Wenn man den Aufwand für die Berechnung des Endergebnisses betrachtet, so sind bei einer Folge der Länge n nur n-1 Subtraktionen (siehe Fig. 33) erforderlich. Vergleicht man diesen Aufwand mit dem, der zur Berechnung der Kreuzkorrelation zweier Folgen der Länge n erforderlich ist (n Multiplikationen und n-1 Additionen), so erkennt man klar den Vorteil der Nutzung der Morse-Thue-Folge, da die für Microcontroller sehr zeitaufwendigen Multiplikationen wegfallen. Beim Einsatz von digitalen Signalprozessoren, die auf die Ausführung von MAC (Multiply and Accumulate) Befehlen optimiert sind, ist dieser Vorteil nicht vorhanden. Bei einer Realisierung in Hardware ist die Morse-Thue-Folge aber wieder im Vorteil, da Multiplikationen in Hardware sehr platzaufwendig sind (der Platzaufwand steigt mit dem Quadrat der Wortbreite).

5.4 Schneller Algorithmus für die Decodierung durch rekursives Stapeln

Das im vorherigen Abschnitt beschriebene Verfahren entspricht dem Einsatz des in Abschnitt 3.2 beschriebenen Stapelverfahrens für die Morse-Thue-Folge.

Auch wenn im Gegensatz zu den bekannten Korrelationsmethoden keine Multiplikationen benutzt werden müssen, und es somit auf einem leistungsarmen Microcontroller implementierbar ist - was schon einen deutlichen Vorteil bedeutet - läßt sich der Rechenaufwand nochmals deutlich verringern.

Wenn man das Stapelergebnis zu einem Zeitpunkt t und dem Zeitpunkt t+1 betrachtet, was in Fig. 37 für eine Folge der Länge 8 dargestellt ist, so erkennt man, daß sich nur die Elemente an den Stufengrenzen verändert haben. Die Felder, die nicht durch einfache Verschiebungen entstanden sind, wurden in der Figur grau hinterlegt. Alle anderen Felder sind nur durch eine Verschiebung um eine Position nach links entstanden. Dies ermöglicht eine Berechnung des decodierten Wertes zum Zeitpunkt t+1 aus den Zwischenergebnissen, die zum Zeitpunkt t vorliegen, nur durch Verschieben und Verändern der Werte an den Stufengrenzen. Um also von den Zwischenergebnissen, die im Stapel zum Zeitpunkt t auf den Stapel zum Zeitpunkt t+1 zu kommen, müssen nur noch die Subtraktionen ausgeführt werden, deren Ergebnis in Fig. 37 grau hinterlegt ist. Alle anderen Subtraktionsergebnisse wurden schon in den vorangegangenen Zeitschritten berechnet und können durch eine einfache Verschiebung an ihre neue Position im Stapel gebracht werden. In dem Beispiel sinkt so die Anzahl der erforderlichen Subtraktionen von 7 auf 3. Da die Anzahl der Werte in einer Stufe mit wachsender Folgenlänge schnell steigt, ist bei längeren Folgen die Einsparung noch deutlicher.

Da eine Folge der Längen nur ld(n) Stufengrenzen aufweist, entsteht auch für lange Folgen nur ein minimaler Rechenaufwand. Eine Folge der Länge 65536 ließe sich mit einem Rechenaufwand von nur 16 Subtraktionen decodieren.

Die Werte, die in den unteren Ebenen des Stapels liegen, werden für die weiteren Berechnungen nicht mehr benötigt und müssen deshalb auch nicht gespeichert werden. Zur Berechnung reicht so ein einfaches (Speicher-)Feld. Im Beispiel sind diese nicht mehr verwendeten Werte: x0, x1, x2, x3, x0-x4, x1-x5 und x0-x4-x2+x6.

Eine Berechnung mit nur einem Feld könnte dann, wie in Fig. 38 dargestellt aussehen. Hierbei wurden die einzelnen Schritte, die zur iterativen Berechnung des nächsten Korrelationswertes erforderlich sind, untereinander aufgetragen. In der ersten Zeile ist der Zustand des Feldes zum Zeitpunkt 0 dargestellt. Im zweiten Schritt wurden alle Elemente des Feldes um eine Position verschoben, um Platz für den neu dazugekommenen Abtastwert x8 zu schaffen. In den unteren drei Zeilen werden nacheinander die drei Subtraktionen dargestellt, welche die noch nicht berechneten Werte (die grau hinterlegten aus Fig. 37) ermitteln. In der letzten Zeile liegt das fertige Ergebnis des Stapels zum Zeitpunkt 1 vor.

Alle bisher beschriebenen Prinzipien lassen sich sowohl in Hardware als auch in Software realisieren. Eine mögliche Realisierung in Hardware ist in Fig. 39 dargestellt. Die Rechtecke stehen für Verzögerungsglieder (Speicher) und die Kreise für Subtrahiererstufen. In der Figur ist zur Verdeutlichung die Belegung der Speicherglieder mit den empfangenen Werten zu einem Zeitpunkt angegeben. Die Funktionsweise entspricht der oben angegebenen Form der Berechnung mit einem Feld. Die direkten Verbindungspfeile zwischen den Speichergliedern entsprechen dem Schiebevorgang aus Fig. 38. Wenn sich ein Subtrahierer zwischen zwei Blöcken befindet, so entspricht dies einer der Subtraktionen aus Fig. 38. Da in Hardware alle Operationen parallel ausgeführt werden können, sind sie alle in einer einzigen Figur dargestellt.

5.5 Beschreibung des schnellen Stapeldecoders in VHDL

Um eine digitale Schaltung zu beschreiben, bietet sich entweder die Beschreibung als Schaltplan oder die Beschreibung in textueller Form an. Die Beschreibung durch einen Schaltplan ist sicher die bei Ingenieuren bekanntere Version. Ein Schaltplan beschreibt jedoch immer nur die Realisierung mit einer festen Bitbreite und einer festen Folgenlänge.

Die Beschreibung in einer Hardwarebeschreibungssprache wie VHDL ermöglicht es dem Benutzer, die von ihm benötigten Parameter durch einfache, dokumentierte Änderungen an einer zentralen Stelle einzustellen.

Als Beispiel soll hier die Beschreibung des schnellen Stapeldecoders in der Hardwarebeschreibungssprache VHDL dienen. Die kompletten Quelltexte sind in Anhang B abgedruckt.

Die Beschreibung verteilt sich auf 4 Dateien: Tabelle 3 Die Quelldateien des Stapeldecoders



Anstelle der Konstanten in der Datei constants.vhd bietet die Sprache VDHL eigentlich die Möglichkeit der "generischen Parameter" (Über generische Parameter kann z. B. eine allgemeine Beschreibung eines Addierers entwickelt werden, bei der die gewünschte Bitbreite bei der Nutzung in einer anderen VHDL-Beschreibung festgelegt wird. So können mit einer Beschreibung 3, 7 oder 81-Bit Addierer erzeugt werden.), über die sich Parameter wie z. B. die Bitbreite anpassen ließen. Leider unterstützen die verwendeten Synthesewerkzeuge solche Parameter nur für untergeordnete Module. Die Module der obersten Schicht, die dann in einem Schaltplan mit den Ein- und Ausgängen des Bausteins verbunden werden, dürfen keine solchen Parameter haben.

Die erstellte VHDL-Beschreibung läßt sich mit gängigen VHDL-Simulatoren testen. Dazu steht in der Datei Test_FMT.vhd eine einfache Testumgebung aus einem Generator für die Morse-Thue-Folge und dem schnellen Stapeldecoder zur Verfügung. Diese Testumgebung kann aufgrund der verwendeten Takterzeugung durch verzögerte Zuweisungen nicht in Hardware synthetisiert werden.

Die einzelnen Module (Generator und Decoder) lassen sich aber synthetisieren. Testweise wurde dafür ein Decoder für Folgen der Länge 8 in einem XilinX FPGA realisiert.

In den VHDL-Beschreibungen wurde bewußt auf technologiespezifische Konstruktionen verzichtet. Über solche technologiespezifische Konstruktionen kann zum Beispiel das On- Chip-RAM der XilinX-FPGAs genutzt werden. So ließe sich durch das Ersetzen von mehreren Registern gegen Dual-Port-RAMs bei längeren Folgen der Platzbedarf der Schaltung deutlich verringern. Solche Beschreibungen lassen sich aber nur noch auf einer vorgegebenen Technologie synthetisieren. Deshalb wurde hier zugunsten der Universalität der Beschreibung darauf verzichtet.

5.6 Verhalten des Stapeldecoders bei gestörten Signalen 5.6.1 Niederfrequente Störungen und Gleichspannungsstörungen

Bei dem Stapelverfahren treten in der Morse-Thue-Folge genauso viele positive wie negative Werte auf. Daher sind Gleichspannungskomponenten oder niederfrequente Störungen, die sich in Abschnitt 5.2 noch so katastrophal auswirkten, jetzt grundsätzlich eliminiert. Dieses Verhalten des Stapeldecoders soll anhand von Fig. 40 verdeutlicht werden. Dort steht c für einen konstanten, dem Signal überlagerten Gleichanteil.

Schon nach einer Subtraktionsstufe sind die Störungen verschwunden.

5.6.2 Rechnersimulationen mit Rauschstörungen

Im praktischen Einsatz treten neben Gleichspannungsstörungen, die meist im Empfänger entstehen, als weitere wichtige Störkomponente Rauschsignale auf. Diese werden dem Nutzsignal sowohl auf dem Übertragungsweg vom Sender zum Empfänger überlagert als auch von den analogen Baugruppen von Sender und Empfänger erzeugt.

In den folgenden Figuren wurde die Morse-Thue-Folge mit einem gleichverteilten diskreten Rauschsignal unterschiedlicher Amplitude überlagert. Die diskrete Morse-Thue-Folge (das Nutzsignal) hat in allen Bildern eine Amplitude von 1. Die Amplitude des Rauschsignals wurde von 0 in der ersten Figur (Nr. 41) bis auf einen Wert von 8 in der letzten Figur (Nr. 44) gesteigert.

Bei der Überlagerung mit 4-facher Amplitude (Fig. 43) ist mit bloßem Auge das Nutzsignal noch leicht zu erkennen. Bei 8-facher Amplitude (Fig. 44) kommen die Störspitzen in den Bereich der Nutzsignale, eine Erkennung ist problematisch.

Um den Zusammenhang zwischen der sicheren Erkennung von Signalen bei hohen Rauschamplituden und der Länge der Morse-Thue-codierten Nutzsignale besser einschätzen zu können, wurden noch weitere Untersuchungen durchgeführt. Die Fig. 45-47 zeigen Ausgangssignale, wenn der Stapeldecoder nur mit einem im Bereich von -1 bis 1 gleichverteilten Rauschen ohne Nutzsignal angesteuert wurde. Die Summationslänge des Decoders wurde im Bereich von 256 bis 4096 verändert.

Man kann erkennen, daß sich die Amplitude des Rauschsignals am Decoderausgang bei einer Vervierfachung der Decoderlänge verdoppelt (oder bei einer Verdoppelung der Decoderlänge nur um den Faktor √2 ansteigt [Lük75]). Da sich die Amplitude eines Nutzsignals bei einer Vervierfachung der Decoderlänge vervierfachen würde, verdoppelt sich bei vierfacher Decoderlänge der Signal/Rausch-Abstand.

Das Stapelverfahren ist somit bezüglich der Rauschunterdrückung genauso wirksam, wie es das bekannte aufwendigere klassische Korrelationsverfahren bei binären Referenzsignalen ist.

Kapitel 6. Mit der Morse-Thue-Folge verwandte Funktionsmengen

Nachdem für die Morse-Thue-Folge eine einfache, iterative Decodierungsvorschrift entwickelt werden konnte, sollen in den folgenden Abschnitten weitere Folgen daraufhin untersucht werden, ob für sie ähnliche Strukturen existieren. Vielleicht existieren Folgen, die bei einem vergleichbaren Rechenaufwand eine bessere Korrelationsgüte bieten. Um diese Folgen zu finden, soll im folgenden Kapitel zuerst die Menge der Rademacher- und Walsh- Funktionen [BEU75] untersucht werden, da zu dieser Funktionsmenge auch die Morse-Thue- Folge gehört.

6.1 Rademacher-Funktionen

Eine wichtige, unvollständige aber orthogonale Menge von Funktionen sind die Rademacher- Funktionen [RAD22]. Sie bestehen aus einer Reihe von Rechteckimpulsen oder Rechteckfunktionen mit einem Tastverhältnis von 50%. Die Funktionen nehmen nur die beiden diskreten Werte von +1 und -1 an. Die ersten 6 Rademacher-Funktionen sind in Fig. 48 dargestellt. Die erste Funktion, R(0,t) ist 1 für das ganze Zeitintervall 0<t<T.

Die nächste und alle folgenden Funktionen sind Rechteckfunktionen mit ungerader Symmetrie bezüglich der Mittelachse. Die Unvollständigkeit der Funktionsmenge kann gezeigt werden, wenn wir eine Summe von mehreren Rademacher-Funktionen betrachten. Diese zusammengesetzte Funktion wird auch wieder eine ungerade Funktion sein. Funktionen mit gerader Symmetrie, die für eine vollständige Funktionsmenge erforderlich sind, können nicht erzeugt werden.

Rademacher-Funktionen haben zwei Argumente n und t. R(n,t) hat 2n-1 Rechteckperioden in dem normalisierten Zeitintervall 0<t<1. Rademacher-Funktionen können aus Sinusfunktionen, die an denselben Stellen Nulldurchgänge haben, durch die folgende Gleichung gebildet werden:



R(n,t) = sign[sin(2nπt)] (6.1)

Rademacher-Funktionen sind wichtig, da andere vollständige Funktionsmengen, wie die Walsh-Funktionen, von ihnen abgeleitet werden können.

6.2 Walsh-Funktionen

Die Walsh-Funktionen bilden eine geordnete Menge von Rechteckfunktionen, die auch nur zwei diskrete Werte +1 und -1 annehmen. Walsh-Funktionen bilden eine Menge orthogonaler Funktionen. Im Gegensatz zu den Rademacher-Funktionen besitzen die Walsh-Funktionen kein Tastverhältnis von 50 Prozent. So wie bei einem Satz von Sinus-/Cosinusfunktionen oder den Rademacher-Funktionen werden zwei Argumente benötigt, um die komplette Funktionsmenge zu beschreiben. Zum einen eine Zeitvariable t und zum anderen eine Ordnungsnummer n, die der Frequenz in einer Menge von Sinusfunktionen entspricht. Die Funktionen werden geschrieben als



WAL(n,t) (6.2)

Für die meisten Anwendungen wird ein solcher Satz von Funktionen mit steigender Anzahl von Nulldurchgängen in einem vorgegebenen Zeitintervall sortiert. In Fig. 49 sind die ersten 32 Walsh-Funktionen entsprechend angeordnet. Man erkennt, daß von unten nach oben gesehen zur Mittelachse ungerade und gerade Funktionen paarweise aufeinanderfolgen. In der Literatur wird diese Anordnung oft auch Sequenzanordnung genannt. Sequenz ist ein Terminus, der von Harmuth [HAR72] vorgeschlagen wurde, um eine periodische Wiederholungsrate zu beschreiben, die unabhängig von der Wellenform ist. Sie ist definiert als "eine Hälfte der Anzahl der Nulldurchgänge in einem Einheitszeitintervall".

Die allgemein verwendete Einheit Frequenz kann in diesem Zusammenhang als ein spezielles Sequenzmaß für Sinusfunktionen betrachtet werden.

Eine alternative Bezeichnung zu WAL wurde von Harmuth vorgeschlagen, bei der die zusammengehörenden ungeraden und geraden Walsh-Funktionen paarweise zusammengefaßt werden. Die Terme werden in Anlehnung an SIN und COS mit CAL und SAL bezeichnet.





Bei dieser Beschreibung wird die Ähnlichkeit der Walsh-Funktionen zu einer Serie von Sinus- und Cosinusfunktionen noch deutlicher.

6.2.1 Sortierung der Funktionen in der Menge

Zur Sortierung der Walsh-Funktionen innerhalb der Funktionsmenge sind zwei Sortiervorschriften verbreitet.

Gewünscht ist eine Sortierung nach der Anzahl der Nulldurchgänge der Funktionen, die eine Ähnlichkeit zu der gewohnten Sortierung anderer orthogonaler Funktionen (z. B. Sinusfunktionen) aufweist, die aber andererseits bei der Berechnung der Funktionen einfach zu handhaben ist. Keine der beiden unten beschriebenen Vorschriften erfüllt beide Anforderungen. Da sie die beiden bekanntesten Vorschriften sind, sollen sie hier trotzdem vorgestellt werden:

  • 1. Die "Sequenzanordnung" (auch geordnete Form, Walsh-Ordnung, Walsh-Kaczmarz- Ordnung).

    Dies ist Walsh's ursprüngliche Anordnung für seine Funktionen, WAL(n,t). Er sortierte die Teilfunktionen nach ihrer Anzahl an Nulldurchgängen. Dies entspricht einer Sortierung nach der Frequenz bei Sinusfunktionen, wo die Funktionen auch nach ihrer Anzahl an Nulldurchgängen geordnet werden.

    Der Vorteil dieser Sortierung ist das abwechselnde Auftreten von CAL- und SAL- Funktionen in der geordneten Menge, die die Verwandtschaft zu den Sinus- und Cosinustermen in der Fourier-Analyse unterstreicht.
  • 2. Die "natürliche Ordnung" (auch Normalordnung, Binärordnung, Paley-Ordnung). Diese Sortierung entsteht bei der Erzeugung durch aufeinanderfolgende Rademacher- Funktionen. Sie wurde zuerst von Paley [PAL32] verwendet und wird deshalb auch Paley- Ordnung PAL(n,t) genannt. In Fig. 50 sind die ersten 32 Walsh-Funktionen entsprechend angeordnet. Diese Sortierung hat einige Vorteile bei der Analyse und Berechnung der Funktionen.

Die Sequenzanordnung wird in der Übertragungstechnik und in der Signalverarbeitung sowie in der Spektralanalyse bevorzugt, die natürliche Ordnung wegen der einfacheren Berechnung im Bereich der theoretischen Mathematik und der Bildübertragung.

Der Zusammenhang zwischen "Sequenzanordnung" und "natürlicher Ordnung" entspricht, wie später gezeigt wird, dem Zusammenhang zwischen Zahlen, die in Binär- und in Gray- Code codiert sind.

6.2.2 Generierung der Walsh-Funktionen

Die Funktionsmenge kann auf verschiedene Arten erzeugt werden, die jeweils ihre eigenen Vor- und Nachteile haben. Die folgenden vier Möglichkeiten sollen hier näher beschrieben werden:

  • - durch Differenzengleichungen
  • - durch Produkte von Rademacher-Funktionen
  • - durch die Hadamard-Matrix
  • - durch Boolsche Synthese

Bei der Erzeugung durch Differenzengleichungen entstehen die Funktionen direkt in Sequenzanordnung, bei den anderen Verfahren in natürlicher Ordnung.

6.2.2.1 Erzeugung durch Differenzengleichungen

Die Walsh-Funktionen können durch die folgende Differentialgleichung beschrieben werden:





oder für N diskrete Punkte gleichen Abstands mit N = 2p und n = 0, 1, . . . N-1:





Die Operation, die diese Differenzengleichungen beschreiben, ist eine Kompression der vorherigen Walsh-Funktion WAL(j,2n), invertiert oder nichtinvertiert in die linke Hälfte der neuen Funktion und ein Anhängen derselben invertierten Walsh-Funktion WAL(j,2n) in der rechten Hälfte.

6.2.2.2 Erzeugung durch Rademacher-Funktionen

Rademacher-Funktionen wurden in Abschnitt 6.1 vorgestellt. Obwohl sie eine unvollständige Funktionenmenge bilden, ist es möglich, aus ihnen Funktionen mit gerader und ungerader Symmetrie zu bilden. Insbesondere die vollständige Menge von Walsh-Funktionen in natürlicher Ordnung kann als Produkt ausgewählter Rademacher-Funktionen dargestellt werden.





Wobei bi die Binärstellen von n sind:



n = bm2m + bm-12m-1 + . . . + b121 + b020 (6.7).

bi = 0 oder 1

Zum Beispiel kann PAL(10,t) geschrieben werden als



PAL(10,t) = R(4,t)R(2,t) (6.8)

Die oben angegebenen Darstellungen gehen von Rademacher-Funktionen mit den beiden diskreten Werten -1 und +1 aus. Wenn -1 durch eine binäre 0 und +1 durch eine binäre 1 ersetzt wird, ergibt sich eine weitere Darstellung der Walsh-Funktionen zu:





wobei die Addition Modulo 2 durchgeführt werden muß:



0 ⊕ 0 = 0

1 ⊕ 0 = 1

0 ⊕ 1 = 1

1 ⊕ 1 = 0

Wenn die Walsh-Funktionen nicht in der natürlichen Ordnung, sondern in Sequenzordnung erzeugt werden sollen, müssen in der Gleichung anstelle der bi, den Stellen der Binärdarstellung von n, die gi, die Stellen der Graycodedarstellung von n, eingesetzt werden.





Wobei gi die Graycodestellen von n sind:



n = (gm, gm-1, . . ., g1, g0) (6.11)

gi = bi ⊕ bi-1 ⊕ entspricht der Modulo 2 Addition (EXOR)

Zum Beispiel kann WAL(10,t) geschrieben werden als



10 = (1,0,1,0)b

10 = (1, 1, 1, 1)g (6.12)

WAL(10,t) = R(4,t) R(3,t) R(2,t) R(1, t)

Da Rademacher-Funktionen auch durch die Vorzeichen von Sinustermen dargestellt werden können, ist es möglich, auch die Walsh-Funktionen als Vorzeichen eines Produktes von Sinus- und Cosinustermen darzustellen. Ross und Kelly [RK72] haben einen allgemeinen Ausdruck für die Darstellung von WAL(n,t) in Abhängigkeit der Binärdarstellung von n angegeben:





wieder mit



n = bm2m + bm-12m-1 + . . . + b121 + b020 (6.14)



bi = 0 oder 1

6.2.2.3 Erzeugung durch Hadamard-Matrizen

Eine Hadamard-Matrix [HAD93] ist eine quadratische Matrix, deren Elemente nur +1 und -1 sind und deren Zeilen (und Spalten) orthogonal zueinander sind. In einer zur Hauptdiagonalen symmetrischen Hadamard-Matrix können Zeilen (und Spalten) vertauscht werden, oder die Vorzeichen einer Zeile (oder Spalte) vertauscht werden, ohne die Orthogonalitätseigenschaften zu verändern. Dadurch ist es möglich, eine symmetrische Hadamard-Matrix zu erzeugen, deren erste Zeile und Spalte an jeder Stelle nur den Wert +1 enthalten. Die so erhaltene Matrix wird Normalform der Hadamard-Matrix genannt. Die kleinste Hadamard- Matrix ist die Hadamard-Matrix zweiter Ordnung.





Matrizen höherer Ordnung können durch den rekursiven Zusammenhang



HN = HN/2 &otimes; H2 (6.16)



dargestellt werden. Hier bezeichnet &otimes; das Kronecker-Produkt und N muß eine Zweierpotenz sein.

Das Kronecker-Produkt bedeutet das Ersetzen jedes Elementes der linken Matrix durch die rechte Matrix. Die nächsten zwei Hadamard-Matrizen sind somit:





und





Der Zusammenhang zwischen Hadamard-Matrizen und abgetasteten Walsh-Funktionen ist dadurch gegeben, daß die Zeilen einer Hadamard-Matrix den Walsh-Funktionen in natürlicher Ordnung entsprechen, wenn die Zeilennummern in bit-reversed (Bit-Reversing tritt auch bei der Berechnung der FFT auf. Es bedeutet, daß die Reihenfolge der einzelnen Binärstellen vertauscht wird. So wird aus 4 (100) durch Bit-Reversing die Zahl 1 (001) oder 5 (101) bleibt 5 (101)) Darstellung geschrieben werden.

6.2.2.4 Erzeugung durch Boolsche-Synthese

Diese Form der Beschreibung der Walsh-Funktionen wurde von Gibbs [GIB70] entwickelt. Er definiert die diskrete Walsh-Funktion WAL(i,t) als Produkt:





mit



n = (np,p-1, . . . n2,n1)2 (6.20)

t = (t1,t2, . . . tk-1,tk)2

Da die diskrete Wälsh-Funktion WAL(n,t) nur p Werte enthält und da für alle k>p gilt nk = 0, kann WAL(n,t) durch das Ersetzen von 1 durch eine Boolsche 0 und -1 durch eine Boolsche 1 auch als N-bit langer Boolscher Vektor geschrieben werden:





wobei T eine ganze Zahl ist, die aus den ersten p Binärstellen von t gebildet wird.

Da die Walsh-Funktionen symmetrisch sind:



WAL(n,T) = WAL(T,n) (6.22)



gilt auch:





Ein kompletter Satz von N Walsh-Funktionen kann als binäre N×N-Matrix geschrieben werden. Der Ausdruck in Klammern in den Gleichungen 6.21 und 6.23 stellt die Umwandlung vom binären in den Gray-Code dar. Diese Gleichungen können somit auch als





oder als





geschrieben werden.

Wobei g T|K das k-te Bit der Graycodedarstellung von T ist.

Diese Form der Herleitung der Walsh-Funktionen ist für eine Erzeugung in Hardware günstig, da eine Modulo-2-Addition einem Boolschen EXOR und eine Modulo-2-Multiplikation einer Boolschen UND-Verknüpfung entspricht. Damit ist eine Umsetzung der obigen Gleichungen in eine logische Schaltung direkt möglich.

6.3 Beziehung der Morse-Thue-Folge zu den Walsh-Funktionen

Wenn man die Menge der Walsh-Funktionen betrachtet, so erkennt man, daß die Morse- Thue-Folge in der Funktionsmenge in verschiedenen Zeitmaßstäben auftritt, siehe Fig. 51.

Bei der hier verwendeten Notation MTF(n,T) entspricht n der Anzahl der invertierten Anhängevorgänge, die zur Erzeugung dieser Morse-Thue-Folge nötig waren. In der Figur wird auch der Zusammenhang von PAL(i,T) und MTF(n,T) deutlich:



MTF(n,T) = PAL(2n-1,T) (6.26)

6.4 Untersuchung der Korrelationseigenschaften der Walsh-Funktionen

Eine Frage, die sich bei der engen Verwandtschaft der Morse-Thue-Folge und der Walsh- Funktionen ergibt ist, ob es in der Menge der Walsh-Funktionen Folgen mit besseren Korrelationseigenschaften als die der Morse-Thue-Folge gibt.

In Fig. 52 wurden die Autokorrelationsfunktionen der ersten 32 Walsh-Funktionen aufgetragen. Zur Generierung der Funktionen wurde die in MatLab vorhandene Funktion zur Erzeugung von Hadamard-Matrizen verwendet. Die Funktionen sind also in bitreverser Paley- Ordnung aufgetragen (siehe auch Abschnitt 6.2.2.3).

Mit bloßem Auge ist ein Abnehmen der Nebenmaxima mit steigender Ordnungszahl erkennbar. Dies ist auch in der folgenden Figur, in der der Betrag der Autokorrelationsfunktionen aufgetragen wurde, zu sehen:

Um diesen optischen Eindruck zu überprüfen, soll nun das in Abschnitt 2.6 beschriebene Bewertungskriterium des Verhältnisses des Haupt- zum nächstkleineren Nebenmaximum angewandt werden.

Dazu wurden in Fig. 54 für die ersten 32 Walsh-Funktionen das Haupt- zu Nebenmaximum- Verhältnis (HNV) über der Ordnungsnummer (n) der Funktion aufgetragen.

Die Funktionen mit dem größten HNV von 2 sind in dieser Darstellung die Funktionen mit der Ordnungszahl 31 und 30: Dies entspricht in Paley-Ordnung den Funktionen PAL(31,t) und PAL(15,t), die beide Morse-Thue-Folgen sind.

Alle weiteren Folgen aus der Menge der ersten 32 Walsh-Funktionen weisen ein ungünstigeres HNV auf. Ein Einsatz der anderen Walsh-Funktionen zur Datenübertragung erscheint damit nicht sinnvoll.

Kapitel 7. Weitere Folgen mit einfachen Bildungsgesetzen

Nach der Entwicklung der einfachen iterativen Berechnungsvorschrift für die Korrelationsfunktion der Morse-Thue-Folge und der Untersuchung der mit ihr verwandten Funktionen sollen in diesem Kapitel weitere Folgen, die ähnlich einfache Bildungsgesetze wie die Morse- Thue-Folge haben, daraufhin untersucht werden, ob sie sich zur Informationscodierung eignen.

7.1 Die Fibonacci-Folge

Die Fibonacci-Folge ist nach ihrem Entdecker Leonardo Fibonacci (Fibonacci, die Kurzform von filius Bonacci (Sohn von Bonacci), ist auch unter den Namen Leonardo von Pisa, Leonardo Pisano und Leonardo Bigollo (Leonardo der Reisende) bekannt.), einem der größten Mathematiker des Mittelalters, benannt, der zwischen 1175 und 1250 gelebt hat. Er gehörte zu den ersten Mathematikern in Europa, die anstelle des römischen Zahlensystems die heute gebräuchlichen arabischen Zahlen verwendete. Die nach ihm benannte Zahlenfolge entwickelte Fibonacci aus dem folgenden Problem:

Auf einer Wiese befinden sich zwei neugeborene Hasen, ein Männchen und ein Weibchen. Die Hasen werden nach einem Monat geschlechtsreif, und am Ende ihres zweiten Lebensmonats wirft das Weibchen zwei Junge, wieder ein Männchen und ein Weibchen. Nehmen wir an, daß die Hasen nie sterben und geschlechtsreife Weibchen in jedem weiteren Monat wieder ein Paar Junge (ein Männchen und ein Weibchen) werfen. Wie viele Hasenpaare ergeben sich von Monat zu Monat und wieviele werden am Ende eines Jahres auf der Wiese leben?

Für unsere Anwendungen ist nicht die Anzahl der Hasen an den Monatsenden, sondern die Verteilung dieser Anzahl auf junge und alte Hasen interessant. Um das Problem in eine computergerechte Form zu bringen, sollen junge Hasenpaare als 0 und erwachsene Hasenpaare als 1 geschrieben werden (junge Hasenpaare müssen zwei Monate, alte Hasenpaare nur einen Monat auf Nachwuchs warten).

Die ersten Fibonacci-Folgen sind also:



F1 = 0 ein junges Hasenpaar

F2 = 1 ein altes Hasenpaar

F3 = 10 ein altes Hasenpaar mit Jungen

F4 = 101 ein altes Hasenpaar mit Jungen und ein weiteres altes Hasenpaar usw.

In den seit Fibonacci vergangenen Jahrhunderten hat die Wissenschaft unter anderem im Bereich der Botanik viele Probleme gefunden, die sich nach den Gesetzen der Fibonacci- Folge verhalten.

Wenn über die Fibonacci-Folge geschrieben wird, ist meistens nicht die Zahlenfolge (die Menge an jungen und erwachsenen Hasenpaaren 0, 1, 10, 101) direkt gemeint, sondern die Reihe der Fibonacci-Zahlen (1, 1, 2, 3, 5, 8, 13 . . .). Jede Fibonacci-Zahl setzt sich immer aus der Summe ihrer beiden Vorgänger zusammen. Der Zusammenhang zwischen den Fibonacci- Folgen und den Fibonacci-Zahlen ist, daß die N-te Fibonacci-Zahl der Länge der N-ten Fibonacci-Folge entspricht.

7.1.1 Erzeugung der Fibonacci-Folge

So wie sich eine Fibonacci-Zahl aus der Summe ihrer beiden Vorgänger ergibt, so ergibt sich eine Fibonacci-Folge aus der Aneinanderhängung ihrer beiden Vorgänger.

Um eine kompakte Schreibweise zu erhalten, soll in den folgenden Abschnitten folgende Notation verwendet werden: Mit X+Y ist ein Anhängen der Folge Y an die Folge X gemeint, mit X-Y ist ein Anhängen der invertierten Folge Y an die Folge X gemeint.

Mit dieser Notation läßt sich dieses Verfahren durch die folgenden Rekursionsgleichungen beschreiben:



F0 = 0

F1 = 1

F2 = F1 + F0

F3 = F2 + F1



Fn = Fn-1 + Fn-2

Der Anfangswert kann statt mit 0 auch mit -1 angesetzt werden, was dann zu den komplementären Variablen -1 und +1 führt.

In der Literatur taucht auch manchmal eine Version mit umgekehrter Reihenfolge auf. Sie erzeugt eine unterschiedliche Folge mit gleichartigen Eigenschaften:



F0 = 0

F1 = 1

F2 = F0 + F1

F3 = F1 + F2



Fn = Fn-2 + Fn-1

Alternativ kann die Fibonacci-Folge auch als L-System beschrieben werden. Wenn wir uns wieder an Fibonaccis ursprüngliches Beispiel mit den Hasen erinnern, so beschreibt das L-System das Erwachsenwerden der Hasen (p1) und die Vermehrung der Hasen (p2). Die Beschreibung der Fibonacci-Folge als L-System sieht folgendermaßen aus:



V = {0, 1}

ω = 0

p1: 0 → 1

p2: 1 → 01

Die Anwendung dieser Regeln bei der Erzeugung der ersten fünf Fibonacci-Folgen ist in der folgenden Figur dargestellt.

7.1.2 Eigenschaften

Die Fibonacci-Folge weist die folgenden Eigenschaften auf:

  • 1. Die Fibonacci-Folge ist nicht gleichspannungsfrei.
  • 2. Die Fibonacci-Folge enthält Fn-2 Symbole 0 und Fn-1 Symbole 1. Dies entspricht einem Gleichanteil von Fn-3.
  • 3. Die Fibonacci-Folge besitzt weder eine gerade noch eine ungerade Symmetrie.
  • 4. Durch jedes Anhängen wächst die Länge um einen Faktor zwischen eins und zwei.
  • 5. Die Fibonacci-Folge ist eine fraktale Folge, d. h. die Fibonacci-Folge enthält Kopien von sich selbst in unterschiedlichen Zeitmaßstäben. Die Fibonacci-Folge weist wie die Morse- Thue-Folge eine hohe Redundanz auf.
  • 6. Die Fibonacci-Folge wiederholt sich nie.
  • 7. In der Fibonacci-Folge tritt nie eine Folge 111 oder 00 auf.

7.1.3 Längenwachstum der Fibonacci-Folge

Im Gegensatz zur Morse-Thue-Folge, die ihre Länge mit jedem Anhängen verdoppelt, ist das Längenwachstum der Fibonacci-Folge nicht konstant. In Fig. 56 ist das Längenwachstum der Fibonacci-Folge aufgetragen, verstanden als Faktor der Längen zwischen aufeinanderfolgenden Folgen.

Der Faktor des Längenwachstums der Fibonacci-Folge konvergiert für große Längen gegen einen Wert von ca. 1.6. Der genaue Wert entspricht der Zahl Φ = 1.61803398. . . (Zahl des goldenen Schnittes). Der Zusammenhang zwischen den Fibonacci-Zahlen und der Zahl Φ wird in Abschnitt 8.3.1, bei den Gleichungen zur direkten Berechnung der Fibonacci-Zahlen, genauer beschrieben.

7.1.4 Die Autokorrelationsfunktion der Fibonacci-Folge

In Abschnitt 2.6 wurde die Autokorrelationsfunktion als wichtiges Hilfsmittel zur Bewertung der Eignung einer Folge für die Datenü bertragung vorgestellt. Zur Bewertung der Fibonacci- Folge ist in Fig. 57 die Autokorrelationsfunktion der Fibonacci-Folge dargestellt.

Die Autokorrelationsfunktion der Fibonacci-Folge erreicht für keines der beiden Bewertungskriterien aus Abschnitt 2.6 ein zufriedenstellendes Ergebnis. Der Abstand des Hauptmaximums zu den nächstgrößeren Nebenmaxima ist gering (HNV ≈ 1.2), und die Energie aller Nebenwerte zusammen ist deutlich höher als die Energie des Hauptwertes.

Aufgrund des ungünstigen Autokorrelationsverhaltens eignet sich die Fibonacci-Folge so nicht zur Datenübertragung. Wenn man die Bildungsregeln betrachtet, so läßt sich dies auch einfach nachvollziehen. Durch das unveränderte Anhängen enthält die Fibonacci-Folge eine große Redundanz. Teile der Folge treten unverändert an anderen Stellen wieder auf. Im folgenden Abschnitt soll untersucht werden, ob das Korrelationsverhalten der Folge durch eine Veränderung der Bildungsgesetze verbessert werden kann. Dabei soll der Einfluß von Invertierungen beim Anhängen, die ja auch in den Erzeugungsregeln der Morse-Thue-Folge eine Rolle spielten, untersucht werden.

7.2 Die modifizierte Fibonacci-Folge

Die Fibonacci-Folge hat ein für die Informationsübertragung unbefriedigendes Korrelationsverhalten. Im Rahmen dieser Arbeit wurde eine Modifikation der Fibonacci-Folge entwickelt, die ein deutlich besseres Korrelationsverhalten aufweist. Es soll in den folgenden Abschnitten gezeigt werden, daß sich dies durch kleine Änderungen an den Bildungsregeln erreichen läßt.

7.2.1 Erzeugung der modifizierten Fibonacci-Folge

Ein erster Ansatz ist, wie bei der Morse-Thue-Folge alle Anhängevorgänge invertiert durchzuführen. Dazu muß auch die Startbedingung angepaßt werden, sonst entsteht eine Folge aus lauter gleichen Folgengliedern.



F0 = 1

F1 = 1

F2 = F0 - F1 Modifikation A

F3 = F1 - F2



Fn = Fn-2 - Fn-1

Die entstehende Folge besitzt leider dieselben schlechten Korrelationseigenschaften wie die Original Fibonacci-Folge, wie Simulationen ergaben.

Eine Verbesserung ergibt sich erst, wenn man die Rekursionsgleichungen zur Beschreibung der Fibonacci-Folge so verändert, daß in jedem zweiten Schritt ein invertiertes Anhängen erfolgt:





Weitere äquivalente Möglichkeiten zur Erzeugung dieser Folge sind:





oder





7.2.2 Eigenschaften der modifizierten Fibonacci-Folge
  • 1. Die modifizierte Fibonacci-Folge weist eine zur Mitte ungerade Symmetrie auf.
  • 2. Die modifizierte Fibonacci-Folge ist nicht gleichspannungsfrei.
  • 3. Durch jedes Anhängen wächst die Länge um einen Faktor zwischen eins und zwei.
  • 4. Die modifizierte Fibonacci-Folge ist eine fraktale Folge, d. h. sie enthält Kopien von sich selbst in unterschiedlichen Zeitmaßstäben.
  • 5. Die modifizierte Fibonacci-Folge wiederholt sich nie.
7.2.3 Die Autokorrelationsfunktion der modifizierten Fibonacci-Folge

Um das Ergebnis der Änderung zu überprüfen, sind in den beiden folgenden Figuren einmal die Autokorrelationsfunktion der modifizierten Fibonacci-Folge der Länge 144 (Fig. 58) und zum anderen die Kreuzkorrelation der modifizierten Fibonacci-Folge mit einer Informationsfolge -1 -1 1 1 -1 dargestellt, bei der jedes Bit mit einer modifizierten Fibonacci- Folge der Länge 144 codiert wurde (Fig. 59).

Im Vergleich zu der Morse-Thue-Folge aus Kapitel 4 ist bei der modifizierten Fibonacci- Folge sowohl das Haupt- zu Nebenmaximum-Verhältnis als auch der Merit-Faktor günstiger.

Man kann erkennen, daß sich wie bei der Morse-Thue-Folge bei aufeinanderfolgenden gleichen codierten Bitwerten die Nebenmaxima vergrößern. Da das Haupt- zu Nebenmaximum-Verhältnis der modifizierten Fibonacci-Folge günstiger ist, sind die Nebenmaxima aber immer noch deutlich kleiner als die Hauptmaxima. Die Gefahr einer Fehlsynchronisation ist geringer als bei der Morse-Thue-Folge.

7.2.4 Bewertung

Durch die geringfügige Veränderung der Bildungsregeln hat sich das Korrelationsverhalten der Fibonacci-Folge deutlich verbessert. Der Abstand des Haupt- zum größten Nebenmaximum bleibt auch im ungünstigsten Fall, der aufeinanderfolgenden Übertragung von zwei gleichen Bitwerten auf einem Wert von ca. 2. Auch die Energie aller Nebenwerte ist deutlich zurückgegangen. Die genauen Werte finden sich in dem späteren Vergleich in Tabelle 7 (Seite 81).

Insgesamt ist das Korrelationsverhalten besser als das der Morse-Thue-Folge. Da es aber immer noch deutlich ungünstiger als das von (Pseudo-)Zufallsfolgen ist, muß, damit ein Einsatz in der Datenübertragung sinnvoll ist, auch für die modifizierte Fibonacci-Folge eine "schnelle" Struktur wie für die Morse-Thue-Folge vorhanden sein.

Im folgenden Abschnitt soll deshalb untersucht werden, ob sich auch für diese modifizierte Fibonacci-Folge eine einfache Decoderstruktur wie für die Morse-Thue-Folge finden läßt.

Kapitel 8. Decoder für die modifizierte Fibonacci-Folge

Da die modifizierte Fibonacci-Folge wie die Morse-Thue-Folge durch wiederholtes Anhängen erzeugt wird, sollte es auch hier eine Möglichkeit geben, die Korrelation durch ein Umkehren des Generierungsprozesses zu bestimmen. Durch die kompliziertere Vorschrift wird allerdings auch der Decoder komplizierter.

8.1 Ein einfacher Stapeldecoder für die modifizierte Fibonacci-Folge

Zur Erzeugung der modifizierten Fibonacci-Folge (wie auch für die ursprüngliche Fibonacci- Folge) existieren zwei Versionen. Bezeichnet man Fn-2 und Fn-1 als Teilfolgen, so folgt bei der einen Version auf die kürzere Teilfolge (Fn-2) die längere Teilfolge (Fn-1). Bei der anderen Version ist es gerade umgekehrt.

8.1.1 Erzeugung mit der längeren Teilfolge am Ende

Wenn man den Generierungsprozeß in der Version mit der längeren Teilfolge am Ende der neuen Folge betrachtet (Modifikation C), der in Fig. 60 grafisch dargestellt ist, so kann man durch Untereinanderschreiben der einzelnen Teile der Folge auch einen Decoder entwickeln.

Diese Umkehrung der Erzeugung ist in Fig. 61 dargestellt. Es muß immer der vordere Teil der Folge vom Ende des hinteren Teils abgezogen werden. So ergibt sich eine vorzeichenrichtige Subtraktion der Werte und am Ende die gewünschte maximale Korrelationssumme von 13 im gewählten Beispiel.

8.1.2 Erzeugung mit der kürzeren Teilfolge am Ende

Die zweite Version des Generierungsprozesses hängt die kürzere Teilfolge am Ende der neuen Folge an (Modifikation D). Bei dieser Version, die in Fig. 62 grafisch dargestellt ist, kann man auch durch Untereinanderschreiben der einzelnen Teile der Folge einen Decoder entwickeln.

Wenn man die entstehende Folge mit der aus Fig. 60 vergleicht, so unterscheiden sich die entstehenden Folgen nur im Vorzeichen. Dieses hat seine Ursache in der ungeraden Symmetrie der modifizierten Fibonacci-Folge.

Die Umkehrung dieser Erzeugung ist in Fig. 63 dargestellt. Auch hier ergibt sich bei einer vorzeichenrichtigen Subtraktion der Werte am Ende wieder die gewünschte maximale Korrelationssumme von (-)13.

8.2 Entwicklung eines schnellen Decoders für die modifizierte Fibonacci-Folge

Die Entwicklung eines schnellen Decoders für die modifizierte Fibonacci-Folge verläuft analog zur Entwicklung des schnellen Decoders für die Morse-Thue-Folge. Zuerst werden die Decoderstapel zu zwei benachbarten Zeitpunkten verglichen. Werte, die in den oberen Lagen des Decoderstapels liegen, stehen für kompliziertere Berechnungen. Deshalb dürfen Werte immer nur über die Stufengrenzen "hochgeschoben" werden. Für den Fibonacci-Decoder bedeutet dies, daß, wenn die erste Generierungsvorschrift verwendet wird, die neuen Werte links an die vorhandene Wertefolge angefügt werden müssen. Dies entspricht einer zeitlichen Spiegelung der Folge. Bei der Decodierung entsprechend der zweiten Form ist diese Spiegelung nicht nötig. Um Platz in der Figur zu sparen, wurden die Zwischenergebnisse nicht in der Form X9-X1 geschrieben, sondern mit den Buchstaben Y, Z . . . B bezeichnet.

Dabei gelten für eine Folge der Länge 13, die im Beispiel verwendet wird, die folgenden Zusammenhänge:



Yn = Xn+8 - Xn

Zn = Yn+2 - Xn+5

An = Zn+1 - Yn

Bn = An+1 - Zn

Rn = Bn - An

Die Offsets ergeben sich aus den Längendifferenzen der Fibonacci-Folgen.

Die Werte, die sich verändert haben, sind grau hinterlegt. Alle anderen Werte wurden nur verschoben. In dem Beispiel in Fig. 64 sind somit nur 5 Subtraktionen anstelle der 12 Subtraktionen nötig, Allgemein gilt: Zur Ermittlung des nächsten Wertes bei einer Fibonacci- Folge der Ordnung N sind N-1 Subtraktionen erforderlich. Wie auch bei der Morse-Thue- Folge kann die Berechnung mit nur einem Datenfeld durchgeführt werden. Dies ist in Fig. 65 dargestellt.

Die Positionen, bei denen die Subtraktionen durchgeführt werden müssen, lassen sich allgemein durch den folgenden Pseudocode beschreiben.



StageMax = iFIB(Length)

Für alle Stage im Bereich 1 . . . StageMax

Point1 = Length - FIB (Stage - 2)

Point2 = Length - FIB (Stage) (8.1)

XPoint1 = XPoint1-1 - XPoint2

Für alle anderen i im Bereich 1 . . . Length

Xi = Xi-1

Am Beispiel einer Folge der Länge 13 bedeutet das:



X1 -5 = X1 -5 -1 - X1-1 oder X8 = X7 - X

X1 - = X1 - -1 - X1 -8 oder X1 = X9 - X5

X1 -2 = X1 -2-1 - X1 -5 oder X11 = X1 - X8 (8.2)

X1 -1 = X1 -1-1 - X1 - oder X12 = X11 - X1

X1 - = X1 - -1 - X1 -2 oder X1 = X12 - X11

für alle anderen Xi gilt Xi = Xi-1

Man erhält so genau die 5 in Fig. 65 mit Pfeilen eingezeichneten Subtraktionen.

Da sich die Werte, bei denen die Subtraktionen durchgeführt werden müssen, aus den Fibonacci-Zahlen ergeben, ist es schwierig, eine universelle Hardwarebeschreibung zu entwickeln, wie dies bei der Morse-Thue-Folge in Abschnitt 5.4 möglich war. Für eine allgemeine Lösung müssen die Positionen, an denen die Subtraktionen durchgeführt werden sollen, durch eine Funktion bestimmt werden, welche die einzelnen Fibonacci-Zahlen ermittelt.

Bei einer Realisierung in einer Hardwarebeschreibungssprache wird diese Berechnung einmalig bei der Synthese durchgeführt. Für eine feste Länge kann ein "Fibonacci-Korrelator" genauso einfach wie ein "Morse-Thue-Korrelator" in Hardware realisiert werden.

8.3 Beispielimplementierung eines schnellen Fibonacci-Decoders

Zu Demonstrationszwecken wurde ein Decoder für die modifizierte Fibonacci-Folge einmal in C++ und zum anderen in VHDL implementiert. Wie im letzten Abschnitt erläutert, ergeben sich die Stufengrenzen aus den Längen der beiden Teilfolgen, aus denen sich die jeweilige Stufe zusammensetzt. Zum Entwickeln allgemeiner Beschreibungen ist eine Gleichung zur direkten Berechnung der Fibonacci-Zahlen erforderlich. Im folgenden sollen Funktionen vorgestellt werden, die eine direkte Berechnung der n-ten Fibonacci-Zahl FIB(n) ermöglichen. Auch die Umkehrfunktion iFIB(z), die die Position der Fibonacci-Zahl z in der Menge angibt, läßt sich mit diesen Gleichungen berechnen.

8.3.1 Direkte Berechnung der Fibonacci-Zahlen

Eine geschlossene Gleichung zur Berechnung von FIB(n) (der n-ten Fibonacci-Zahl) ist spätestens seit dem Jahr 1730 bekannt. Damals wurde die Gleichung von dem Mathematiker J. P. M. Binet [KNO98] entwickelt, dessen Namen sie heute trägt. In [KN73] wird behauptet, daß die Gleichung schon fast 100 Jahre vorher von A. de Moivre (1667-1754) beschrieben wurde. Sie basiert auf den Konstanten des Goldenen Schnittes phi φ und Phi Φ.

Diese Zahlen sind die Lösungen der Gleichungen





oder ausgerechnet:





Sowohl φ als auch Φ sind irrationale Zahlen. Weitere Eigenschaften von φ und Φ sind:



Φn = Φn-1 + Φn-2

φn = φn-1 + φn-2 (8.5)

φn = Φ-n

Mit diesen beiden Konstanten läßt sich die n-te Fibonacci-Zahl schreiben als [KNO98-2]:





Trotz der irrationalen Zahlen in der Gleichung liefert sie für ganzzahligen immer ein ganzzahliges Ergebnis. Da φ kleiner als 1 ist, geht der Term φn für größer werdende N gegen 0. Deshalb kann die Gleichung durch Runden auf ganze Zahlen vereinfacht werden zu:





8.3.2 Direkte Berechnung der nächsten Fibonacci-Zahl

Um iterativ aus einer Fibonacci-Zahl die nächste errechnen zu können, ohne die Rekursionsgleichung benutzen zu müssen und so alle vorherigen Fibonacci-Zahlen zu berechnen, eignet sich die folgende Gleichung [KNO98-2]





8.3.3 Direkte Berechnung der vorhergehenden Fibonacci-Zahl

Genauso einfach kann iterativ aus einer Fibonacci-Zahl die vorhergehende errechnet werden, ohne die Rekursionsgleichung benutzen zu müssen. Da FIB(n) immer eine ganze Zahl ist, kann die obige Gleichung durch Nutzung der Rekursionsgleichung einfach umgestellt werden zu:





8.3.4 Ein Fibonacci-Decoder in VHDL und C++

Obwohl die in den vorangehenden Abschnitten beschriebenen Gleichungen zur Berechnung der Fibonacci-Zahlen eine allgemeine VHDL-Beschreibung ermöglichen sollten, ergibt sich dabei ein wesentliches Problem: Die zur Verfügung stehenden VHDL-Simulatoren können mit Fließkommazahlen, die zur Berechnung der Gleichungen nötig sind, zwar umgehen, aber die Synthesewerkzeuge können keine mit Fließkommazahlen verarbeiten. Um eine synthetisierbare Beschreibung zu erhalten, wurden die Funktionen FIB und iFIB über Tabellen realisiert. In die Tabellen wurden die ersten 13 Fibonaccizahlen (Zahlen bis 144) eingetragen. Der Bereich der erlaubten Werte ist somit auf 1 bis 13 (FIB) oder 1 bis 144 (iFIB) beschränkt. Für die Berechnung von Folgen, die länger als 144 sind, müßten die Tabellen und Konstanten im VHDL-Quelltext entsprechend erweitert und angepaßt werden.

Eine weitere Schwierigkeit trat auf, weil das Synthesetool Aurora der Firma Viewlogic die allgemeine Beschreibung des Decoders aufgrund eines internen Fehlers nicht synthetisieren kann. In dem VHDL-Quelltext des Decoders existieren deshalb zwei Versionen des Decoderkerns. In der allgemeinen Version werden die Stufengrenzen mit den Funktionen FIB und iFIB berechnet. Diese Version kann zur Simulation oder mit dem VHDL-Synthesetool der Firma Synopsis genutzt werden. Bei einer Änderung der Folgenlänge müssen nur die Konstanten in constants.vhd angepaßt werden. Die zweite Version nutzt nicht die Funktionen FIB und iFIB, sondern arbeitet mit Konstanten. Die Version im Quelltext ist auf eine Folgenlänge 13 ausgelegt. Wenn eine andere Folgenlänge benutzt werden soll, müssen neben den Änderungen in constants.vhd auch die zusätzlichen Subtrahierer im Decoderkern entsprechend der allgemeinen Beschreibung hinzugefügt oder entfernt werden.

Der Generator für die modifizierte Fibonacci-Folge wurde durch einen Zähler und eine Look- Up-Tabelle realisiert. Auch hier muß die Tabelle für die modifizierte Fibonacci-Folge bei einer Änderung der Folgenlänge angepaßt werden.

Für die VDHL-Version gilt sonst dasselbe wie für die VDHL-Beschreibung des Morse-Thue- Decoders. Die einzelnen Module (Generator und Decoder) lassen sich synthetisieren. Es wurde versuchsweise ein Decoder für Folgen der Länge 13 in einem XilinX-FPGA realisiert, um die Beschreibungen zu überprüfen. Auch in diesen VHDL-Beschreibungen wurde wieder auf proprietäre Konstruktionen verzichtet.

Die komplette Beschreibung verteilt sich auf 5 Dateien: Tabelle 4 Die Quelldateien des Fibonacci-Decoders



Die Quelltexte sind im Anhang C abgedruckt.

Kapitel 9. Vergleich der Verfahren

Kein Verfahren kann alle Wünsche, die an den "idealen Korrelator" gestellt werden, erfüllen. Deshalb ist es wichtig, aus den vorgestellten Verfahren ein, für das jeweilige Einsatzgebiet passendes auszuwählen.

Um einen Vergleich der vorgestellten Verfahren zu erleichtern, sind in den folgenden Tabellen die wichtigsten Kenngrößen wie Aufwand, Flexibilität und Güte der verschiedenen Verfahren einander gegenübergestellt.

So kann ein zu den jeweiligen Anforderungen in Bezug auf Leistung und Kosten passendes Verfahren gefunden werden.

9.1 Gegenüberstellung des Aufwandes

Ein wichtiger Parameter bei der Entwicklung von kostengünstigen Lösungen ist der Aufwand zur Realisierung des jeweiligen Verfahrens. In Tabelle 5 sind die Werte für die beiden Aufwandsmaße Hard- oder Softwareaufwand auf der einen und Zeitbedarf auf der anderen Seite aufgelistet.

Die Parameter in Tabelle 5 sind die Folgenlänge N und die Eingangsbitbreite B. Bei mehrkanaligen Verfahren ist k die Anzahl der Kanäle. Tabelle 5 Arithmetischer Aufwand der verschiedenen Korrelationsverfahren



Man kann die Verfahren anhand der Tabelle in vier Gruppen einteilen:

  • 1. Standardverfahren, die Multiplizierer erfordern und einen proportional zum Quadrat der Folgenlänge N steigenden Zeitaufwand haben (1, 2).
  • 2. Standardverfahren, die Multiplizierer erfordern und einen proportional zur Folgenlänge N steigenden Schaltungsaufwand haben (3, 4).
  • 3. Die vereinfachten Verfahren, die keinen Multiplizierer erfordern und einen proportional zur Folgenlänge steigenden Schaltungsaufwand haben. Von den Stapelverfahren wird hier nur die optimale Version mit Vertauschen betrachtet (5, 6).
  • 4. Die spezialisierten Verfahren, die keinen Multiplizierer erfordern und einen proportional zum Logarithmus der Folgenlänge steigenden Schaltungsaufwand haben (7, 8).

Wenn man als Gesamtmaß eine Kombination aus Schaltungsaufwand und Zeitaufwand wählt, erkennt man deutlich, daß die spezialisierten Verfahren den geringsten Aufwand unter den vorgestellten Verfahren haben. Sie ermöglichen es, bei gleichem Rechenaufwand mit deutlich längeren Folgen zu arbeiten und so eine bessere Unterdrückung von Rauschstörungen zu erzielen, die dem Signal überlagert sind.

9.2 Gegenüberstellung der Flexibilität

Nicht alle vorgestellten Verfahren lassen sich universell, d. h. für beliebige Zahlenfolgen, einsetzen. In der folgenden Tabelle wird eine Übersicht aller vorgestellten Verfahren und ihrer Einsatzgebiete dargestellt. Tabelle 6 Einsatzbereiche der verschiedenen vorgestellten Korrelationsverfahren



Die schnellen Verfahren erlauben also nur die Nutzung eines Übertragungskanals durch einen einzigen Anwender. Wenn ein Codevielfachzugriff erwünscht ist, müßte für diese Verfahren für jede Zahlenfolge ein spezieller Decoder realisiert werden. In diesem Anwendungsfall ist es günstiger, ein universelleres Verfahren zu verwenden.

9.3 Gegenüberstellung der Korrelationsgüten

Da die schnellen Verfahren an eine bestimmte Zahlenfolge gebunden sind, ist hier ein Vergleich der Korrelationsgüte der unterschiedlichen Zahlenfolgen interessant. Für die aufwendigeren flexiblen Verfahren kann die Zahlenfolge frei gewählt werden, so daß bei diesen Verfahren eine Angabe der Gütewerte keinen Sinn macht. In Tabelle 7 sind sowohl die Werte für den periodischen als auch für den aperiodischen Fall berechnet. Bei den periodischen Werten wurde sowohl ein Übergang mit zwei identischen Folgen als auch der Übergang zu einer invertierten Folge betrachtet. Der ungünstigere von beiden Werten wurde in die Tabelle aufgenommen. Man erkennt, daß generell die Werte für den periodischen Fall schlechter sind. Zum Vergleich wurden die Werte auch für die Pseudozufallszahlenfolge ermittelt, die beim Zeitzeichensender DCF 77 zur Informationsübertragung verwendet wird. Sie kann als Anhaltspunkt für Werte dienen, die bei den universellen Verfahren mit freier Wahl der Zahlenfolge erreichbar sind. Alle Werte wurden mit MatLab und den im Anhang abgedruckten Hilfsfunktionen ermittelt. Tabelle 7 Korrelationsgüte der untersuchten Zahlenfolgen



Man erkennt deutlich, daß der einfache Stapeldecoder mit Vertauschen die besten Gütewerte in Bezug auf die Eigenstörungen erzielt.

9.4 Grafische Einordnung der Verfahren

Um einen einfacheren Überblick über die Einordnung der vorgestellten Verfahren zu erhalten, können die einzelnen Ordnungskriterien Aufwand, Eigenstörungen und Unterdrückung von Rauschstörungen grafisch gegeneinander aufgetragen werden.

9.4.1 Eigenstörungen der Zahlenfolgen

Um eine Größenanpassung der Werte zu erzielen, wurden die Werte für den Merrit-Faktor in der Grafik mit einem Faktor von 10 multipliziert. So liegen die Werte in derselben Größenordnung wie der HNV-Werte. In der Figur stehen große Balken für bessere Werte.

Man erkennt deutlich, daß sich mit (pseudo-)zufälligen Zahlenfolgen, die mit dem einfachen Stapeldecoder mit Vertauschen verwendet werden können, die besten Gütewerte in Bezug auf die Eigenstörungen erzielen lassen.

9.4.2 Rechenaufwand

In Fig. 67 ist die Länge der Folge aufgetragen, die sich mit dem jeweiligen Verfahren (schneller Morse-Thue-Decoder, schneller Fibonacci-Decoder, Stapeldecoder mit Vertauschen) mit einer vorgegebenen Anzahl an Subtraktionen verarbeiten läßt.

Die Länge der Folge ist ein Maß für die Unterdrückung störender Rauschsignale. Durch eine Vervierfachung der Folgenlänge verdoppelt sich der Abstand des Korrelationsmaximums von den Rauschstörungen.

Aus der Figur erkennt man deutlich, daß die schnellen Verfahren die größten Folgenlängen bei gleichem Aufwand unter den verglichenen Verfahren haben. Sie ermöglichen es, bei gleichem Rechenaufwand mit deutlich längeren Folgen zu arbeiten und so eine bessere Unterdrückung von Rauschstörungen zu erzielen, die dem Signal überlagert sind. Der schnelle Morse-Thue-Decoder erlaubt bei 12 Operationen eine Folgenlänge von 4096, der schnelle Fibonacci-Decoder eine Folgenlänge von 377 und der Stapeldecoder eine Folgenlänge von 13. Damit ist die Rauschunterdrückung beim schnellen Morse-Thue-Decoder ca. 4 mal besser als beim schnellen Fibonacci-Decoder und ca. 10 mal besser als beim Stapeldecoder. Dafür sind bei diesen die Eigenstörungen geringer (siehe vorhergehenden Abschnitt).

Kapitel 10. Zusammenfassung und Ausblick

In der vorliegenden Arbeit wurden Verfahren untersucht, die es ermöglichen, eine Berechnung der Korrelationsfunktion in Echtzeit auf leistungsschwachen Systemen durchzuführen. Korrelationsverfahren ermöglichen es zum Beispiel, im Bereich der Satellitenkommunikation oder im Bereich der Mobilkommunikation auch über Kanäle mit schlechtem Signal-/Rauschabstand Daten zu übertragen. Dies erfordert derzeit jedoch leistungsfähige Hardware. Um Korrelationstechniken zum Beispiel in Pagern oder Fernsteuerungen einsetzen zu können, ist ein Verfahren erforderlich, das vergleichbare Ergebnisse mit niedrigem Aufwand liefert. Dann kann der Gewinn an Signal-/Rauschabstand, den Korrelationsverfahren bieten, auch in Systemen erreicht werden, die aus Kosten- oder Energiegründen bisher auf einen Korrelator verzichten müssen.

Im Überblick wurden die mathematischen Grundlagen der Korrelationsverfahren eingeführt und Bewertungsmaße für diese Verfahren definiert. Anschließend wurden Konzepte vorgestellt, die sich schon im technischen Einsatz befinden und anhand der Bewertungsmaße beurteilt.

Als Weiterentwicklung der bekannten Verfahren wurde im Rahmen dieser Arbeit (im Kapitel 3) eine vereinfachte Korrelatorstruktur entwickelt, die ohne aufwendige Multiplikationen auskommt und nur einfache Operationen wie Subtraktionen erfordert. Dieses Verfahren mit Vertauschen der Eingangswerte wurde "Stapeldecoder" genannt. Der Stapeldecoder erlaubt die Nutzung von beliebigen binären Referenzsignalen entlang der Zeitachse auf einfacher Hardware. Er benötigt für die Berechnung eines Wertes der Korrelationsfunktion einer Folge der Länge N jeweils O(N) einfache Operationen. Ein Einsatz dieses Verfahrens erlaubt die Nutzung beliebiger binärer (oder binarisierbarer) Folgen auf einfachen Mikrocontrollern oder in preiswerter programmierbarer Hardware.

Im zweiten Teil der Arbeit (in den Kapiteln 4 bis 8) wurde für ausgewählte Zahlenfolgen diese Struktur weiterentwickelt. Diese "schneller Stapeldecoder" genannte Weiterentwicklung ermöglicht die iterative Berechnung der Korrelationsergebnisse aus vorhandenen Zwischenergebnissen. Diese iterative Berechnung erfordert noch weniger Operationen als die einfachen Stapelverfahren. Es reichen O(ld(N)) Operationen zur Berechnung eines Wertes der Korrelationsfunktion. Dies ermöglicht auch für sehr lange Codefolgen oder für höhere Datenraten einen minimalen Rechen- oder Schaltungsaufwand im Decoder. Beispielhaft wurden Decoder für zwei solche Zahlenfolgen in Hard- und Software implementiert und simuliert.

Da ein "idealer Korrelator" nicht existiert, muß für jeden speziellen Einsatz der optimale Kompromiß gefunden werden. Um dies zu erleichtern, wurden als Abschluß der Arbeit (in Kapitel 9) die untersuchten Verfahren tabellarisch und grafisch einander gegenübergestellt. Mit Hilfe dieses Katalogs von Lösungsvorschlägen für den Bereich von preiswerten und energiesparenden Systemen kann eine passende Lösung anhand der Vergleichstabellen leicht gefunden werden.

Mit den hier vorgestellten Verfahren ist eine Basis geschaffen worden, um die Vorteile der Korrelationsverfahren bei der Datenübertragung auch im Low-Cost-Bereich einzuführen.

Da die Verfahren mit dem geringsten Rechenaufwand fest an eine bestimmte Zahlenfolge gebunden sind, könnte man nach weiteren Zahlenfolgen suchen. Durch eine erweiterte Suche lassen sich eventuell Folgen finden, die ein noch besseres Verhältnis von Aufwand zu Übertragungsgüte aufweisen als es die Folgen haben, die in dieser Arbeit untersucht wurden.

Im Bereich der Realisierung eines Stapeldecoders in Hardware ist eine Weiterentwicklung der hier vorgestellten Hardwarebeschreibungen im Hinblick auf eine bessere Nutzung der Möglichkeiten von programmierbarer Hardware wünschenswert. Eine solche Anpassung der auf allen Bausteinen einsetzbaren Beschreibungen im Hinblick auf die besonderen Fähigkeiten einer einzelnen Familie programmierbarer Bausteine erlaubt die bessere Ausnutzung der einzusetzenden Bausteine. Durch eine solche bessere Anpassung an die Zieltechnologie kann die benötigte Chipfläche zum Teil deutlich verringert werden. Kapitel 11. Literaturverzeichnis [AS98] Stiller A.; Klotz am Bein. Von "Flaws" und anderen Pentium-Performance- Pannen; c't 3/98; S. 126-127; 1998

[Bau71] Baumert L. D.; Cyclic difference sets; Springer-Verlag; 1971

[BEU75] Beuchamp K. B.; Walsh Functions and their Applications; Academic Press; 1975

[GIB70] Gibbs J. E.; Discrete complex Walsh transforms; 1970 Proceedings: Applications of Walsh Functions; Washington D. C; AD707431; 1970

[HAD93] Hadamard M. J.; Resolution d'une question relative aux déterminantes; Bull. Sci. Math. A17 (1893); 240-246; 1893

[HAR72] Harmuth H. F.; Transmission of Information by Orthogonal Functions; 2nd Edition (1972); Springer-Verlag Berlin; 1972

[Hetz93] Hetzel P.; Zeitinformation und Normalfrequenz; telekom praxis Heft 1/1993; S. 25-36; 1993

[HIL71] Hilberg W.; Impulse und Impulsfolgen, die durch Integration oder Differentiation in einem veränderten Zeitmaßstab reproduziert werden; AEÜ Band 25 (1971); Seiten 39-48; 1971

[HIL91] Hilberg W.; Mehrdimensionale Morse-Thue-Folgen; Physik in unserer Zeit, 22 Jahrgang 1991; Seiten 24-28; 1991

[HILi96] Hilberg W.; Ein neues Datenübertragungsverfahren mit einer besonderen Codierung im Zeitbereich für sehr kleine Signal/Rausch-Verhältnisse; Institutsbericht 195/96 THD; 1996

[HILi97] Hilberg W.; Eine alternative Methode zur Trennung von kleinen Nutzsignalen und großen statistischen Störsignalen; Institutsbericht 204/97 THD; 1997

[Höl84] Hölzler E., Holzwarth H.; Pulstechnik Band II; Springer-Verlag; Seiten 426 ff.; 1984

[Kerk91] Kerkmann S.; Untersuchung eines neuen Modulationsverfahrens mit Hilfe der hut-Funktion durch Rechnersimulation; Studienarbeit DT469 THD; 1991

[KN73] Knuth Donald E.; The art of computer programming, Volume 1; Addison Wesley; Section 1.2.8; 1973

[KNO98] Knott R.; Fibonacci Numbers and the Golden Section; Web-based Paper http:/ /www.ee.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html; 1998

[KNO98-2] Knott R.; Fibonacci and Phi Formulae; Web-based Paper http:/ /www.ee.surrey.ac.uklPersonal/R.Knott/Fibonacci/FibPhiFormulae.ps.gz: 1998

[Lin68] Lindenmayer A.; Mathematical Models for Cellular Interactions; Journal of Theoretical Biology, Jahrgang 1968; Seiten 280-315; 1968

[Lük75] Lüke H. D.; Signalübertragung; Springer-Verlag; S. 155-1556; 5. Auflage 1992

[Lük92] Luke H. D.; Korrelationssignale; Springer-Verlag; 1992

[MH1] Morse M., Hedlund G. A.; Unending chess, symbolic dynamics, and a problem in semigroups; Duke Math. J.; 11: 1-7; 1944

[Mor1] Morse M.; Selected Papers; Springer-Verlag New York; 1981

[MWMT97] Meyer-Bäse U., Wolf S. et al.; High-Performance Implementation of Convolution on Multiple Field-Programmable Gate Array Boards Using Number Theoretic Transforms Defined Over the Eisenstein Residue Number System; SPIE Proceedings Vol. 3068; 1997

[OpS92] Oppenheim A., Schafer R.; Zeitdiskete Signalverarbeitung; Oldenbourg Verlag; S. 201 ff; 1992

[PAL32] Paley R. E.; A Remarkable set of orthogonal functions; Proc. London Math. Soc. 32 (1932); 241-279; 1932

[PLES95] Plessey Data Sheet GP2021; Plessey Semiconductors; S. 8; 1995

[RAD22] Rademacher H.; Einige Sätze von allgemeinen Orthogonalfunktionen; Math. Annal. 87 (1992); 122-138; 1992

[RK72] Ross L, Kelly J. J.; A new method for representing Walsh functions; 1972 Proceedings: Applications of Walsh Functions; Washington D. C; AD744650; 1972

[Ste84] Stearns S. D.; Digitale Verarbeitung analoger Signale; Oldenbourg Verlag; S. 105 ff; 1984.

[Thu1] Thue A.; Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen; Norske Vid.-Akad. Oslo; Mat.-Natur. Kl. Skr. (N. S.), (1); 1912.

[Vog95] Vogel R.; Decodierung der DCF 77 Phasenmodulation durch Periodendauerkorrelation; Studienarbeit ST671, THD; 1995

[Wol98] Wolf S.; Modulation mit der Morse-Thue Folge; Institutsbericht 208/98 TUD; 1998

[XIL98] The Programmable Logic Data Book 1998; XilinX; S. 4-11 ff.; 1998

Anhang A. MatLab-Quelltexte der Simulationen A.1 Hilfsfunktionen zur Bestimmung der Korrelationsgüte

Die folgenden MatLab-Funktionen ermitteln das Haupt- zu Nebenverhältnis und den Merrit- Faktor der übergebenen Zahlenfolge.

Achtung! Um auch mit mehreren aufeinanderfolgenden Folgen arbeiten zu können, vergleicht die Funktion HNV den betragsmäßig größten Wert mit dem nächstkleineren Wert. Die Funktion liefert also bei Folgen mit einem HNV von 1 ein falsches (zu großes) Ergebnis! HNV.m



MF.m



A.2 Erzeugung der Morse-Thue-Folge

Die folgende MatLab-M-Datei enthält eine Funktion, mit der eine Morse-Thue-Folge der Längen erzeugt werden kann. Sie wird in den MatLab-Quelltexten der verschiedenen Decoder verwendet. MorseThue.m



A.3 Decodierung durch Integration

Die folgenden MatLab-M-Dateien simulieren einen Decoder nach dem Integrationsprinzip. SumUp.m



MTFIntegral.m



A.4 Decodierung durch Stapeln

Die folgende MatLab-M-Datei simuliert einen Decoder nach dem Stapelverfahren. MTFFold.m



A.5 Schnelle Decodierung durch Stapeln

Die folgende MatLab-M-Datei simuliert einen schnellen Stapeldecoder. Aufgrund der langsamen MatLab-Funktionen zum Verschieben des Speicherfeldes ist die Simulation nicht schneller als MTFFold. Es soll nur das Prinzip verdeutlicht werden. MTFFastFold.m



A.6 Simulationsfiles zum Testen der Morse-Thue-Decoder

Die folgenden MatLab-M-Dateien untersuchen das Verhalten des Decoders mit verschiedenen Eingangssignalen. MTFFastTest.m



MTFNoiseTest.m



NurNoiseTest.m



A.7 Simulationsfiles zur Untersuchung der Fibonacci-Folge

Die folgende MatLab-M-Datei stellt die periodische und die aperiodische Autokorrelationsfunktion der Fibonacci-Folge grafisch dar. FiTest.m



A.8 Simulationsfiles zur Untersuchung der modifizierten Fibonacci-Folge

Die folgenden drei MatLab-M-Dateien stellen verschiedene Möglichkeiten dar, die modifizierte Fibonacci-Folge zu erzeugen. Sie unterscheiden sich in den Anfangsbedingungen und der Reihenfolge des Anhängens. FiTest2.m



FiTest3.m



FiTest4.m



A.9 MatLab-Quelldateien zur Untersuchung der Walsh-Funktionen

Die folgende MatLab-Datei erzeugt die Menge der Walsh-Funktionen. Sie benutzt dazu die in MatLab vorhandene Funktion zum Erzeugen einer Hadamard-Matrix.

Dann ermittelt sie die Autokorrelationsfunktion der Walsh-Funktionen, stellt diese dar und ermittelt für alle Funktionen das Haupt- zu Nebenverhältnis. Hadtest.m



Anhang B. VHDL-Quelltexte des Morse-Thue- Stapeldecoders

In den folgenden Abschnitten sind die Beschreibungen des Stapeldecoders in der Hardwarebeschreibungssprache VHDL abgedruckt. Die Quellen sind im Simulator überprüft und lassen sich mit entsprechenden Werkzeugen wie Aurora von ViewLogic oder VHDLExpress von Synopsis für FPGAs der Firma XilinX synthetisieren. Die Quelltexte enthalten keine technologiespezifischen Konstrukte und sollten sich auch für andere Zieltechnologien eignen.

Durch den Einsatz solcher technologiespezifischen Konstrukte (z. B. Nutzung des on chip RAM der XilinX XC4000 Familie [XIL98]) ließe sich eine deutlich ressourcenschonendere Version erstellen.

B.1 constants.vhd

In dieser Quelldatei werden die Folgenparameter und die interne Wortbreite des Morse-Thue- Stapeldecoders festgelegt. Alternativ können diese Parameter auch als generische Parameter an die Entity FMT übergeben werden. Dann ist die Beschreibung allerdings nicht mehr direkt mit ViewLogic Aurora oder Synopsis VHDLExpress synthetisierbar, da diese Pakete in der äußersten Entity keine generischen Parameter erlauben.

Einige Parameter sind voneinander abhängig (z. B. MT_Length und MT_BitLength). Der Zusammenhang der Parameter ist in den Kommentaren erklärt.

Dieser Quelltext ist synthetisierbar.





B.2 FMT.vhd

Dies ist der Quelltext des eigentlichen Morse-Thue-Stapeldecoders. Die Länge der Folge und die interne Bitbreite werden in constants.vhd definiert. Alternativ könnten diese Parameter auch als generische Parameter an FMT übergeben werden. Die dafür nötige Zeile ist im Quelltext auskommentiert.

Dieser Quelltext ist synthetisierbar.









B.3 MT_Gen.vhd

MT_Gen dient der Erzeugung einer Morse-Thue-Folge. Intern wird die Folge durch Berechnung der Parität (EXOR) eines N-Bit-Zählers gebildet.

Dieser Quelltext ist synthetisierbar.





B.4 Test_FMT.vhd

Dieser Quelltext enthält eine Testumgebung für den Stapeldecoder und den Morse-Thue- Generator.

Durch Anpassung des Prozesses INPUTS kann die Information verändert werden, die codiert durch die Morse-Thue-Folgen übertragen werden soll.

Dieser Quelltext ist nicht synthetisierbar.









Anhang C. VHDL-Quelltexte des Fibonacci- Stapeldecoders

In den folgenden Abschnitten sind die Beschreibungen des Fibonacci-Stapeldecoders in der Hardwarebeschreibungssprache VHDL abgedruckt. Die Quellen sind im Simulator überprüft und lassen sich mit entsprechenden Werkzeugen wie Aurora von ViewLogic oder VHDLExpress von Synopsis für FPGAs der Firma XilinX synthetisieren. Die Quelltexte enthalten keine technologiespezifischen Konstrukte und sollten sich auch für andere Zieltechnologien eignen.

Auch hier ließe sich durch den Einsatz von technologiespezifischen Konstrukten eine deutlich ressourcenschonendere Version implementieren.

C.1 constants.vhd

In dieser Quelldatei werden die Folgenlänge und die interne Wortbreite des Fibonacci- Stapeldecoders festgelegt.

Einige Parameter sind voneinander abhängig (z. B. FIB_Length und FIB_BitLength). Der Zusammenhang der Parameter ist in den Kommentaren erklärt. Die Konstanten FIB 1-FIB 12 werden nur in der für ViewLogic angepaßten Version benötigt.

Dieser Quelltext ist synthetisierbar.









C.2 FibFktn.vhd

In dieser Quelldatei werden die Umrechnungsfunktionen für Fibonacci-Zahlen definiert.

Die Funktionen werden für die allgemeine Beschreibung des Decoders benötigt.

Die gewählte Implementierung basiert auf einer Umrechnungstabelle. Der Bereich der Werte, die umgerechnet werden können, ist durch die Größe der Tabellen beschränkt. Wenn der Wertebereich vergrößert werden soll, muß die Tabelle erweitert und die Konstanten am Anfang des Quelltextes angepaßt werden.

Dieser Quelltext ist synthetisierbar.









C.3 FibDec.vhd

Dies ist der Quelltext des eigentlichen Fibonacci-Stapeldecoders. Die Länge der Folge und die interne Bitbreite werden in constants.vhd definiert. Im Quelltext sind zwei Versionen des Decoderkerns implementiert. Eine der beiden Versionen muß auskommentiert bleiben. In der abgedruckten Version wird die allgemeine Beschreibung verwendet. Wenn Aurora von ViewLogic zur Synthese verwendet wird, muß die alternative Version verwendet werden, da Aurora die allgemeine Version nicht synthetisieren kann.

Dieser Quelltext ist synthetisierbar.













C.4 Fib-Gen.vhd

Fib-Gen dient der Erzeugung einer modifizierten Fibonacci-Folge. Intern wird die Folge durch das Auslesen einer Tabelle, die von einem Zähler angesteuert wird, gebildet.

Dieser Quelltext ist synthetisierbar.









C.5 Test_FIB.vhd

Dieser Quelltext enthält eine Testumgebung für den Fibonacci-Stapeldecoder und den Fibonacci-Generator.

Durch Anpassung des Prozesses INPUTS kann die Information verändert werden, die, codiert durch die modifizierten Fibonacci-Folgen, übertragen werden soll.

Dieser Quelltext ist nicht synthetisierbar.









Anhang D. C++-Quelltexte der Stapeldecoder

In den folgenden Abschnitten sind die Listings des Stapeldecoders in der Programmiersprache C++ abgedruckt. Es wird jeweils eine Implementierung in C++ einer Implementierung in Assembler unter Nutzung der Intel MMX-Befehle gegenübergestellt. Die Quellen sind durch Vergleich der Ergebnisse beider Versionen überprüft. Die Untersuchungen wurden mit Microsoft Visual G++ in der Version 5.0 mit installiertem Service-Pack 3 durchgeführt. Die C++-Implementierung sollte sich ohne Änderungen auf andere Plattformen portieren lassen. Bei der MMX-Version müssen möglicherweise die Inline-Assembler-Zeilen angepaßt werden.

Das Hauptprogramm ruft die Routinen in einer Schleife mehrfach auf, um eine Laufzeitmessung der Routinen zu erleichtern. Zuerst wird die Laufzeit der Meßschleife ermittelt, um diesen Overhead von den Zeiten der C++- und MMX-Version subtrahieren zu können. Dabei ergeben sich Anomalitäten, da das Programm die Schleife mit den MMX- Routinen schneller abarbeitet als die leere Schleife (siehe Tabelle 1). Dieses eigentlich unmögliche Verhalten wird zusätzlich von den Optimierungseinstellungen des Compilers stark beeinflußt. Es kann aber durch ein schnelleres Füllen der Prozessorcaches erklärt werden. Der Einfluß der größeren Cachefüllgeschwindigkeit der MMX-Befehle kann in der Beispielimplementierung durch die Routine MMX_Prepare untersucht werden, die alle Werte einmal mit MMX-Befehlen liest. Durch den zusätzlichen Aufruf der Routine halbiert sich die benötigte Zeit im Vergleich zur leeren Schleife (Pentium-Prozessoren haben ein ähnliches Verhalten bei Fließkomma-Befehlen [AS98]).

Über die Präprozessorsymbole FAST_CACHEFILL und DO_NOT_OPTIMIZE_MAIN können die Auswirkungen dieses abweichenden Cachefüllverhaltens der MMX-Befehle im Vergleich mit den normalen Ladebefehlen untersucht werden. D.1 MMX Fold































D.2 Optimal MMX Fold
























Anspruch[de]
  1. 1. Korrelationsschaltung, mit einem Schieberegister, dem diskrete Signalwerte unterschiedlichen Vorzeichens zugeführt werden, dadurch gekennzeichnet, daß die diskreten Signalwerte von dem Schieberegister (nach Abb. 8) unmittelbar parallel liegenden Schaltungen zugeführt werden, die das Vorzeichen der Signalwerte mit negativer Amplitude umkehren, so daß eine nachgeordnete Summationsschaltung die Summe der Absolutwerte aller im Schieberegister enthaltenen Signalwerte bildet.
  2. 2. Korrelationsschaltung nach Anspruch 1, dadurch gekennzeichnet, daß die Vorzeichenumkehrschaltung (nach Abb. 8) aus einem Umschalter und einem invertierenden Verstärker besteht.
  3. 3. Korrelationsschaltung nach den Ansprüchen 1 und 2, dadurch gekennzeichnet, daß als Vorzeichenumkehrschaltung eine der bekannten Schaltungen für die Betragsbildung verwendet wird.
  4. 4. Korrelationsschaltung nach den Ansprüchen 1 bis 3, dadurch gekennzeichnet, daß die Vorzeichenumkehrschaltungen nach Maßgabe einer modifizierten Fibonacci-Folge (Abb. 61 bis 65) eingestellt werden.
  5. 5. Korrelationsschaltung nach den Ansprüchen 1 bis 3, dadurch gekennzeichnet, daß die Vorzeichenumkehrschaltungen nach Maßgabe einer Rademacher-, Walsh- oder Hadamard- Folge eingestellt werden.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com