DE69830971T2

DE69830971T2 - Pipelineprozessor für die schnelle Fourier-Transformation

Info

Publication number: DE69830971T2
Application number: DE69830971T
Authority: DE
Inventors: Joel Cambonie
Original assignee: STMicroelectronics SA
Current assignee: STMicroelectronics SA
Priority date: 1997-12-19
Filing date: 1998-12-09
Publication date: 2006-04-27
Anticipated expiration: 2018-12-10
Also published as: US6324561B1; EP0924626B1; DE69830971D1; EP0924626A1; FR2772951B1; FR2772951A1

Description

Die Erfindung betrifft Vorrichtungen einer sogenannten "seriellen" oder "Pipeline"-Architektur zum Berechnen einer Fourier-Transformation und ihre Funktionsweise.
Zahlreiche Implementierungen von Fourier-Transformationen, die für Signalverarbeitungsmikroprozessoren gedacht oder programmiert sind, sind in der Literatur vorgestellt worden. Die meisten dieser Implementierungen verwenden eine Variante des Fachleuten bekannten Cooley-Tukey-Algorithmus, der erlaubt, die Anzahl der für die Berechnung der Fourier-Transformation notwendigen arithmetischen Operationen zu reduzieren. So erlaubt dieser Algorithmus insbesondere, die Berechnung einer schnellen Fourier-Transformation der Anfangsgröße r^p, wobei r gemäß einer von Fachleuten üblicherweise verwendeten Bezeichnung die "Basis" bedeutet, auf die von r Fourier-Transformationen der Größe r^p- ¹ und zusätzliche komplexe Additionen und Multiplikationen zu reduzieren. Durch Wiederholen dieser Reduktion gelangt man zur Berechnung von Fourier-Transformationen der Größe r, die leicht ausführbar sind, insbesondere wenn r gleich 2 oder 4 gewählt wird.
Der Cooley-Tukey-Algorithmus verwendet einen Berechnungsgraphen, der eine allgemein schmetterlingsförmige Struktur, die Fachleuten bekannt ist, erkennen läßt und in der englischen Sprache gewöhnlich mit dem Begriff "butterfly" bezeichnet wird.
Mehrere Hardware-Architekturen sind dann zum Implementieren einer schmetterlingsförmigen Berechnungsstruktur möglich.
Eine erste Lösung besteht darin, einen zur Ausführung einer Berechnung des Schmetterlingstyps fähigen Hardware-Operator pro Schmetterling des Graphen zu realisieren. Jedoch ist eine solche Lösung nur für die Implementierung von Fourier-Transformationen kleiner Größe denkbar.
Eine zweite Lösung besteht darin, nur einen einzigen Hardware-Operator des Schmetterlingstyps zu realisieren, der dazu gedacht ist, die Berechnungen für alle Schmetterlinge aller Stufen des Graphen nacheinander auszuführen. Eine solche Lösung hat den Nachteil, einerseits einen sehr schnellen Hardware-Operator und andererseits einen Eingangsspeicher zu benötigen, der sich von dem Speicher unterscheidet, der dazu dient, die Zwischenergebnisse der Berechnung zu schreiben, und dies, um Zugriffskonflikte zu vermeiden, wenn ein Datenblock in den Operator hineinkommt, während der vorherige Block noch im Verarbeitungsablauf ist. Es ist also notwendig, zwei Speicher für N0 komplexe Wörter vorzusehen, wobei N0 die Anfangsgröße der Fourier-Transformation bezeichnet, was zu einer Gesamtschaltung mit einer bedeutenden Oberfläche führt, insbesondere wenn N0 groß ist.
Eine Zwischenlösung besteht darin, einen Hardware-Operator des Schmetterlingstyps pro Stufe des Graphen zu realisieren, sowie ein Speicherelement, wie beispielsweise Verzögerungsleitungen oder Schieberegister, dessen Funktion es ist, am Eingang des Operators die Daten in der richtigen Reihenfolge unter Berücksichtigung der Schmetterlinge des Graphen der betrachteten Stufe bereitzustellen.
Solche Architekturen sind nach einer von Fachleuten üblicherweise verwendeten Bezeichnung sogenannte "serielle" oder "Pipeline"-Architekturen.
Im einzelnen weist eine elektronische Vorrichtung einer sogenannten "Pipeline-Architektur" zum Berechnen einer Fourier-Transformation mehrere aufeinanderfolgende Verarbeitungsstufen auf, die über interne Datenwege in einer Reihenschaltung zwischen dem Eingang und dem Ausgang der Vorrichtung angeordnet sind. Diese Stufen weisen jeweils einerseits Verarbeitungseinrichtungen, die Fourier-Transformationen, deren Grundgrößen kleiner als die Anfangsgröße sind, an Datenblöcken ausführen können, deren Größen von einer Stufe zur nächsten sukzessive reduziert werden, und andererseits Speichereinrichtungen auf.
Unter "Anfangsgröße" der Fourier-Transformation ist hier und im weiteren Verlauf des Textes die Größe der Blöcke zu verstehen, die am Eingang der Vorrichtung von der ersten Stufe empfangen werden.
Die Grundgrößen der von den verschiedenen Stufen ausgeführten Fourier-Transformationen können identisch und gleich der Basis der Fourier-Transformation sein. Man spricht dann von einer Fourier-Transformation "einheitlicher" Basis. Im Falle einer Fourier-Transformation "gemischter" Basis können sie von einer Stufe zur anderen unterschiedlich sein.
Beispiele solcher Pipeline-Architekturen sind beschrieben in dem Artikel von BI und JONES mit dem Titel "A Pipelined FFT Processor for Word-Sequential Data", IEEE Transactions on Acoustic Speech and Signal Processing, Bd. 37, Nr. 12, Dezember 1989, Seite 1982–1985, und in dem Artikel von BIDET et al. mit dem Titel "A Fast Single-Chip Implementation of 8192 Complex Point FFT", IEEE Journal of Solid-State Circuits, Bd. 30, Nr. 3, März 1995, Seite 300–305.
Die in diesen bekannten Architekturen beschriebenen Speichereinrichtungen weisen Verzögerungsleitungen auf, die sehr einfach zu verwaltende Elemente sind und die den Vorteil haben, allgemein kompakt zu sein (Verwendung von drei Transistoren pro gespeichertem Bit). Jedoch sind diese Elemente nicht immer als Standardzellen in den gebräuchlichen, für die Definition und Konzeption von integrierten Schaltungen verwendbaren Komponentenbibliotheken verfügbar. Ferner hängen ihre elektrischen Eigenschaften von der verwendeten Technologie ab, so daß jedesmal, wenn sich die Technologie weiter entwickelt, die Architektur der Schaltung sorgfältig neu geprüft werden muß.
Außerdem verwenden diese Architekturen Verzögerungsleitungen, deren Speicherkapazität pro Basis-4-Stufe gleich 3N/2 ist, wobei N die Größe der von dieser Stufe verarbeiteten Blöcke ist.
In gewissen Anwendungen, insbesondere in terrestrischen Anwendungen des digitalen Fernsehens, die für die Übertragung eine OFDM-Kodierung (OFDM: Orthogonal Frequency Division Multiplex: Multiplexen mit orthogonaler Frequenzverteilung) verwenden, sind die verschiedenen Symbole, die mit einer Fourier-Transformation verarbeitet werden sollen, durch ein Schutzintervall getrennt. Insbesondere geht in einer OFDM-Anwendung jedem empfangenen Symbol ein Schutzintervall voraus, das faktisch mit dem Endabschnitt des Symbols identisch ist. In dieser Art Anwendung ist es dann besonders vorteilhaft, diese Eigenschaft zu verwenden, um die zeitliche Position der verschiedenen Symbole im hereinkommenden Fluß zu erfassen und aufgrund dieser Tatsache die richtige zeitliche Synchronisation dieser verschiedenen Symbole zu steuern. Dazu führt man allgemein eine Korrelation des Eingangsflusses mit dem letzten empfangenen Symbol und seinem zugehörigen Schutzintervall aus.
Dies erfordert insbesondere ferner die Speicherung eines ganzen Symbols.
Die Architektur mit Verzögerungsleitungen, deren Speicherkapazität pro Stufe gleich 3N/2 ist, erlaubt die Ausführung einer Fourier-Transformation an jedem Symbol und stellt gleichzeitig Daten bereit, die um die Länge eines Symbols zeitlich verzögert sind, was eine Ausführung der gewünschten Korrelation erlaubt.
Die Erfindung zielt insbesondere darauf ab, diesem Problem der notwendigen Speichergröße für die Speicherung jedes letzten empfangenen Symbols eine radikal andere Lösung zuzuführen.
Ein Ziel der Erfindung ist, eine Basis-4-Verarbeitungsstufe einer Pipeline-Vorrichtung (Vorrichtung mit Pipeline-Architektur) zum Berechnen einer Fourier-Transformation vorzuschlagen, die mit sehr hohen Taktfrequenzen arbeiten kann und jedes zuletzt empfangene Symbol speichern kann, und dies unter Minimierung der notwendigen Speichergröße und unter Verwendung herkömmlicher und leicht verfügbarer Speicherelemente, gleich welcher verwendeten Technologie.
Die Erfindung hat außerdem zum Ziel, eine solche Basis-4-Verarbeitungsstufe vorzuschlagen, die sich mit sogenannten "full scan"-Testverfahren, die Fachleuten bekannt sind, ohne weiteres testen läßt.
Die Erfindung hat außerdem zum Ziel, etwaige Schutzintervalle zu berücksichtigen, die verschiedene Symbole trennen, die durch Fourier-Transformation verarbeitet werden sollen, insbesondere in terrestrischen Anwendungen des digitalen Fernsehens, die für die Übertragung eine OFDM-Kodierung (Orthogonal Frequency Division Multiplex) verwenden, und dies sogar, wenn die Länge dieses Schutzintervalls vorab nicht bekannt ist.
Die Erfindung schlägt somit ein Verfahren zur Steuerung einer Basis-4-Verarbeitungsstufe einer elektronischen Pipeline-Vorrichtung bzw. einer Vorrichtung mit sogenannter "Pipeline"-Architektur zur Berechnung einer Fourier-Transformation vor. Eine elektronische Berechnungsvorrichtung in Pipelinearchitektur weist mehrere aufeinanderfolgende Verarbeitungsstufen auf, die in einer Reihenschaltung zwischen dem Eingang und dem Ausgang der Vorrichtung angeordnet sind, wobei diese Stufen jeweils einerseits Verarbeitungseinrichtungen, die Fourier-Transformationen, deren Grundgrößen kleiner als die Anfangsgröße sind, an Datenblöcken ausführen können, deren Größen sukzessiv von einer Stufe zur nächsten reduziert werden, und andererseits Speichereinrichtungen auf.
Eine sogenannte "Basis-4"-Verarbeitungsstufe weist Verarbeitungseinrichtungen auf, die Fourier-Transformationen einer Grundgröße gleich 4 an jedem am Eingang der Stufe empfangenen Datenblock ausführen.
Gemäß einem allgemeinen Merkmal der Erfindung werden für jeden am Eingang der Stufe empfangenen Block aus N Daten nur drei Viertel der Daten des Blocks in den Hauptspeichereinrichtungen gespeichert, die einen Hauptspeicher mit wahlfreiem Zugriff, insbesondere einen statischen Speicher mit einfachem Zugriff, aufweisen, und wird ausgehend von diesen gespeicherten Daten und anderen Daten des Blocks eine Berechnung einer Fourier-Transformation ausgeführt. Ferner wird nur eine Hälfte der empfangenen Daten in Hilfsspeichereinrichtungen gespeichert, die einen Hilfsspeicher mit wahlfreiem Zugriff, beispielsweise ebenfalls einen statischen Speicher mit einfachem Zugriff, aufweisen und werden ausgehend vom Inhalt der Haupt- und Hilfsspeichereinrichtungen alle Daten des Eingangsblocks rekonstruiert, um einen bezüglich des Eingangsblocks zeitlich verzögerten, rekonstruierten Datenblock zu erhalten.
Anschließend ist es möglich, eine Gleitkorrelation zwischen dem Ausgang der Basis-4-Stufe, der die zeitlich verzögerten Daten ausgibt, und den Eingangsdaten auszuführen.
Die Verwendung von Speichern mit wahlfreiem Zugriff (dynamischer Speicher), entweder mit zweifachem Zugriff (mit zwei Ports) oder einfachem Zugriff (mit einem Port, das heißt, Spei cher, die bei jedem internen Takt der Vorrichtung entweder einen Schreibzugriff oder einen Lesezugriff zulassen) erfordert eine spezielle Adreßverwaltung zur Speicherung und Wiederausgabe der gespeicherten Zwischendaten in der richtigen Reihenfolge, wobei die Verwaltung um so komplexer ist, als die Basis der Fourier-Transformation größer als 2 ist, insbesondere wenn sie gleich 4 ist, und geht gegen alle derzeitigen Unterrichtungen auf diesem Gebiet, die die Verwendung von Verzögerungsleitungen oder Schieberegistern vorsehen.
Es ist außerdem beobachtet worden, daß die Verwendung von Speichern mit wahlfreiem Zugriff ermöglichte, die Speicherkapazität der Stufe in Vergleich zur Speicherkapazität, die bei Verwendung von Verzögerungsleitungen erforderlich ist, zu verringern.
Solche Komponenten sind überdies in den gebräuchlichen Komponentenbibliotheken leicht verfügbar, insbesondere in ihrer einfachsten Form (Speicher mit einfachem Zugriff) und sind von der verwendeten Technologie völlig unabhängig und mit sehr hohen Taktfrequenzen vollkommen kompatibel.
So ist gemäß der Erfindung in einer Basis-4-Verarbeitungsstufe die zum Ausführen der Fourier-Transformationen erforderliche Speicherkapazität gleich 3N/4 Daten. Es ist also ein Gewinn an Speicherkapazität von einem Faktor 2 in Vergleich zur Lösung vom Stand der Technik, die die Verwendung von Verzögerungsleitungen vorsieht. Ferner sieht die Erfindung vor, nur eine Zusatzspeicherkapazität von N/2 Daten (ein halbes Symbol) zur Rekonstruktion der N Daten eines Symbols hinzuzufügen. Dies ist umso bemerkenswerter, als gemäß der Erfindung bei der Berechnung der Fourier-Transformation eines Blocks aus N Daten alle im Hauptspeicher gespeicherten Daten (das heißt 3N/4 Daten) entsprechend dem Empfang der restlichen N/4 Daten des Eingangsblocks durch Daten von Zwischenberechnungen ersetzt werden.
Die gesamte Speicherkapazität der Stufe ist also gleich 5N/4, was kleiner ist als diejenige (3N/2) einer Stufe mit Verzögerungsleitungen gemäß dem Stand der Technik.
Gemäß einer Ausführungsform des erfindungsgemäßen Verfahrens empfängt die Stufe nacheinander die N Daten des Blocks, die in vier aufeinanderfolgenden Segmenten angeordnet sind, die jeweils N/4 Daten enthalten. Jedes Datum eines Segments bildet mit den homologen Daten der drei anderen Segmente eine Gruppe aus vier Daten. Die in den ersten drei Segmenten enthaltenen Daten werden entsprechend ihrem Empfang in den Hauptspeichereinrichtungen gespeichert. Entsprechend dem Empfang der im vierten Segment enthaltenen Daten
werden einerseits die im dritten Segment enthaltenen Daten, die in den Hauptspeichereinrichtungen gespeichert sind, sowie andererseits die im vierten Segment enthaltenen Daten in den Hilfsspeichereinrichtungen gespeichert,
wird eine Verarbeitung des Typs "Schmetterling" an jeder dieser Gruppen ausgeführt, um aufeinanderfolgende Gruppen aus vier Zwischendaten auszuarbeiten, die jeweils in vier aufeinanderfolgenden Zwischensegmenten angeordnet sind, und
werden jeweils die in den Hauptspeichereinrichtungen gespeicherten Daten durch die in den drei letzten Zwischensegmenten enthaltenen Daten ersetzt.
Vorteilhaft werden die in den ersten zwei Segmenten enthaltenen Eingangsdaten rekonstruiert, indem sie wieder berechnet werden, während die in den letzten zwei Segmenten enthaltenen Daten rekonstruiert werden, indem sie temporär in Hilfsspeichereinrichtungen gespeichert werden, bevor sie daraus herausgeholt werden.
In einer Ausführungsform der Erfindung, in welcher zwei aufeinanderfolgende Eingangsblöcke durch ein Schutzintervall getrennt sind, werden nacheinander alle Daten des Schutzintervalls entsprechend dem Empfang der Daten des Schutzintervalls in den Hauptspeichereinrichtungen gespeichert. Anschließend werden aufeinanderfolgende Verschiebungen der Speicherorte der Daten des Schutzintervalls ausgeführt, dann werden sie nacheinander aus den Hauptspeichereinrichtungen herausgeholt, um sie nacheinander in den Hilfsspeichereinrichtungen zu speichern, bevor sie nacheinander daraus herausgeholt werden, um ein Schutzintervall wiederherzustellen, das zeitlich verzögert ist und die zwei aufeinanderfolgenden rekonstruierten Blöcke trennt, die selbst bezüglich der zwei Eingangsblöcke zeitlich verzögert sind.
Gemäß einer Ausführungsform werden die aufeinanderfolgenden Verschiebungen der Speicherorte der Daten des Schutzintervalls sowie die Speicherung in den Hilfsspeichereinrichtungen entsprechend dem Empfang der in den ersten drei Segmenten des Eingangsblocks enthaltenen Daten ausgeführt.
Die Erfindung hat außerdem eine elektronische Pipeline-Vorrichtung zur Berechnung einer Fourier-Transformation zum Gegenstand. Gemäß einem allgemeinen Merkmal der Erfindung weist sie mindestens eine Basis-4-Verarbeitungsstufe bzw. eine Verarbeitungsstufe mit einer Basis gleich 4 auf, die am Eingang aufeinanderfolgende Blöcke aus N Daten empfangen kann. Diese Basis-4-Verarbeitungsstufe weist Hauptspeichereinrichtungen auf, die eine Speicherkapazität von 3N/4 Daten haben und einen Hauptspeicher mit wahlfreiem Zugriff aufweisen. Die Stufe weist außerdem Hilfsspeichereinrichtungen auf, die eine Speicherkapazität von N/2 Daten haben und einen Hilfsspeicher mit wahlfreiem Zugriff aufweisen. Diese Stufe weist ferner Hauptverarbeitungseinrichtungen auf, die ausgehend vom Inhalt der Hauptspeichereinrichtungen und N/4 anderen Daten des Blocks Fourier-Transformationen einer Grundgröße 4 an jedem Eingangsblock ausführen. Die Stufe weist außerdem Hilfsverarbeitungseinrichtungen auf, die ausgehend vom Inhalt der Haupt- und Hilfsspeichereinrichtungen alle Daten des Eingangsblocks rekonstruieren, um einen rekonstruierten Datenblock zu erhalten, der bezüglich des Eingangsblocks zeitlich verzögert ist.
Gemäß einer Ausführungsform der Erfindung führen die Hauptverarbeitungseinrichtungen der Basis-4-Stufe jeweils N/4 Verarbeitungen des Schmetterlingstyps an N/4 unterschiedlichen Gruppen aus 4 Daten jedes von dieser Stufe verarbeiteten Datenblocks aus. Die Hauptspeichereinrichtungen weisen einen Hauptspeicher mit wahlfreiem Zugriff und n Hauptregister auf, die jeweils mit dem Hauptspeicher in einer Reihenschaltung angeordnet sind. Der Hauptspeicher kann N/4-(n-1) Wörter aus drei Daten speichern, während jedes Hauptregister ein Wort aus drei Daten speichern kann. Gleichermaßen weisen die Hilfsspeichereinrichtungen einen Hilfsspeicher mit wahlfreiem Zugriff und n Hilfsregister auf, die jeweils mit dem Hilfsspeicher in einer Reihenschaltung angeordnet sind. Der Hilfsspeicher kann N/4-(n-1) Wörter aus zwei Daten speichern, während jedes Hilfsregister ein Wort aus zwei Daten speichern kann.
Obwohl für die Implementierung von Verarbeitungen des Schmetterlingstyps in jeder Stufe unterschiedliche interne Hardware-Architekturen der Hauptverarbeitungseinrichtungen denkbar sind, hat es sich in der Tat als bevorzugt erwiesen, daß die Hauptverarbeitungseinrichtungen der Basis-4-Stufe jeweils N/4 Verarbeitungen des Schmetterlingstyps an N/4 unterschiedlichen Gruppen aus vier Daten jedes von dieser Stufe verarbeiteten Datenblocks ausführen, wobei N die Größe des Blocks ist.
Diese erfindungsgemäßen Hauptverarbeitungseinrichtungen, die also vorsehen, "nur ein einziges Mal" jedes Datum (oder jeden Operanden) des empfangenen Blocks aufzurufen, um die verschiedenen Verarbeitungen des Schmetterlingstyps auszuführen, unterscheiden sich somit insbesondere von dem Hardware-Operator, der in dem oben zitierten Artikel von BIDET et al. verwendet wird und der vorsieht, jeden Operanden mehrere Male aufzurufen, um die Verarbeitungen auszuführen. Die Hauptverarbeitungseinrichtungen einer Basis-4-Stufe gemäß der Erfindung weisen also acht komplexe Addierer und einen Multiplizierer auf, während der Stand der Technik mit Verzögerungsleitungen nur sechs Addierer und einen Multiplizierer vorsieht. Jedoch erlauben diese erfindungsgemäßen Hauptverarbeitungseinrichtungen, weniger Zwischendaten zu speichern, und tragen in Kombination mit der Verwendung eines Speichers mit wahlfreiem Zugriff dazu bei, die Speicherkapazität der Stufe nochmals zu minimieren.
Obwohl es diesbezüglich möglich wäre, vorzusehen, daß die Speichereinrichtungen dieser Stufe einzig und allein aus Speichern mit wahlfreiem Zugriff bestehen, ist es besonders vorteilhaft, jedem Speicher mit wahlfreiem Zugriff eine oder mehrere Registerebenen oder Flipflops zuzuordnen, die jeweils mit dem Speicher in einer Reihenschaltung angeordnet sind. Dies erlaubt in der Tat, den eigentlichen Speicher vom operativen Teils der Stufe zu trennen und automatische Werkzeuge zur Erzeugung von Testvektoren zu verwenden. Diese automatischen Testverfahren, die "Full scan-Verfahren" genannt werden und Fachleuten bekannt sind, bestehen insbesondere darin, alle Flipflops aufzuladen, dann Berechnungen auszuführen und die Daten in die Flipflops wieder einzuschreiben, um den Test auszuführen.
Gemäß einer Ausführungsform der Erfindung weist die Basis-4-Verarbeitungsstufe einen Eingang auf, um im Takt eines ersten Taktsignals ("Symbol"takts) nacheinander die N Daten eines aktuellen Blocks zu empfangen, wobei diese Daten in vier aufeinanderfolgenden Segmenten angeordnet sind, die jeweils N/4 Daten enthalten. Jedes Datum eines Segments bildet mit den homologen Daten der drei anderen Segmente eine Gruppe aus vier Daten. Die Hauptspeichereinrichtungen der Stufe weisen dann ein Addierer/Subtrahierer-Modul auf, das bei jedem Zyklus des ersten Taktsignals eine Verarbeitung des Schmetterlingstyps an jeder der auf diese Weise gebildeten Gruppen ausführen kann, um aufeinanderfolgende Gruppen aus vier Zwischendaten auszuarbeiten, die jeweils in vier aufeinanderfolgenden Zwischensegmenten angeordnet sind. Die Hauptspeichereinrichtungen weisen außerdem ein Multiplizierermodul auf, das bei jedem Zyklus des ersten Taktsignals die Zwischendaten mit vorgegebenen Multiplikatorkoeffizienten multiplizieren kann. Die Verarbeitungsstufe weist auch Hauptsteuereinrichtungen auf, die geeignet sind,
die in den ersten drei Segmenten enthaltenen Daten entsprechend ihrem Empfang zu den Hauptspeichereinrichtungen dieser Stufe zu schicken (die in dem letzten Segment enthaltenen Daten werden nicht gespeichert) und
entsprechend dem Empfang der im vierten Segment enthaltenen Daten jeweils die in den Hauptspeichereinrichtungen gespeicherten Daten durch Zwischendaten zu ersetzen, die in den letzten drei Zwischensegmenten enthalten sind.
Die Hilfsspeichereinrichtungen weisen ein Hilfsrekonstruktionsmodul auf, das die in dem ersten und zweiten Segment enthaltenen Daten wieder berechnen kann, sowie Hilfssteuereinrichtungen. Diese Hilfssteuereinrichtungen sind geeignet, die im dritten Segment enthaltenen und in den Hauptspeichereinrichtungen gespeicherten Daten sowie die im vierten Segment enthaltenen Daten zu den Hilfsspeichereinrichtungen zu schicken, und
sie daraus herauszuholen, um die im dritten und vierten Segment enthaltenen Daten zu rekonstruieren.
Gemäß einer Ausführungsform der Erfindung weisen die Hauptspeichereinrichtungen dieser Stufe ein mit dem Ausgang des Hauptspeichers verbundenes erstes Hauptregister und ein mit dem Eingang des Hauptspeichers verbundenes zweites Hauptregister auf. Der Ausgang des ersten Hauptregisters ist erstens über einen ersten steuerbaren Multiplexer mit dem Eingang des zweiten Hauptregisters verbunden, zweitens mit dem Eingang des Addierer/Subtrahierer-Moduls verbunden und drittens über einen zweiten steuerbaren Multiplexer mit dem Eingang des Multiplizierermoduls verbunden. Der Ausgang des Addierer/Subtrahierer-Moduls ist einerseits über den ersten Multiplexer mit dem Eingang des ersten Hauptregisters verbunden und andererseits über den zweiten Multiplexer mit dem Eingang des Multiplizierermoduls verbunden.
Die Hilfsspeichereinrichtungen weisen ein mit dem Ausgang des Hilfsspeichers verbundenes drittes Hilfsregister und ein mit dem Eingang des Hilfsspeichers verbundenes viertes Hilfsregister auf. Der Ausgang des dritten Hilfsregisters ist erstens über einen dritten steuerbaren Multiplexer mit dem Eingang des vierten Hilfsregisters verbunden. Dieser dritte steuerbare Multiplexer ist außerdem auch am Eingang mit der Eingangsklemme der Stufe sowie mit dem Ausgang des ersten Hauptregisters verbunden. Der Ausgang des dritten Hilfsregisters ist zweitens mit dem Eingang des Hilfsrekonstruktionsmoduls verbunden und drittens mit dem Ausgang zur Ausgabe der rekonstruierten und verzögerten Daten verbunden und dies über einen vierten steuerbaren Multiplexer. Ein Eingang des Hilfsmoduls ist ferner mit einem Ausgang des ersten Hauptregisters verbunden, während der Ausgang des Hilfsrekonstruktionsmoduls mit einem Eingang des vierten Multiplexers verbunden ist.
Die Hauptsteuereinrichtungen und die Hilfssteuereinrichtungen weisen auf:
die vier
einen vom ersten Taktsignal getakteten ersten Modulo-N-Zähler (Schreibzähler), der beim Empfang des ersten Datums jedes Blocks wieder initialisierbar ist,
einen vom ersten Taktsignal getakteten zweiten Modulo-N-Zähler (Lesezähler), der beim Aussenden des ersten Ausgangsdatums der Stufe wieder initialisierbar ist (das heißt, wenn der erste Modulo-N-Zähler den Wert 3N/4 erreicht), und
ein Steuermodul, das ausgehend von den Zählwerten der zwei Zähler die Steuersignale für die vier Multiplexer bereitstellt.
Schließlich weisen die Haupt- und Hilfsverarbeitungseinrichtungen Einrichtungen zum gemeinsamen Adressieren des Hauptspeichers und Hilfsspeichers auf, die einen Modulo-(N/4-1)-Zähler aufweisen (in vorliegendem Fall N/4-(n-1) hier mit n = 2, da es zwei Register pro Speicher gibt).
Wenn in einer Ausführungsform zwei aufeinanderfolgende Eingangsblöcke durch ein Schutzintervall getrennt sind, weisen die Hauptverarbeitungseinrichtungen vorteilhaft Verschiebungseinrichtungen auf, die aufeinanderfolgende Verschiebungen der Speicherorte der Daten des Schutzintervalls im Hauptspeicher ausführen können. Diese Verschiebungseinrichtungen weisen vorteilhaft den (über das zweite Hauptregister mit dem Eingang des Hauptspeichers verbundenen) zweiten Multiplexer auf.
Weitere Vorteile und Merkmale der Erfindung zeigen sich beim Studium von Ausführungsformen der Erfindung, die keineswegs einschränkend sind, und der beiliegenden Zeichnungen:
1 ist eine schematische Übersicht einer erfindungsgemäßen Vorrichtung mit zwei Verarbeitungsstufen;
2 zeigt die Verarbeitungen des Schmetterlingstyps, die gemäß der Erfindung in diesen Stufen ausgeführt werden;
3 ist eine schematische Darstellung der Hardware-Architektur einer Verarbeitungsstufe der Vorrichtung von 1;
4a und 4b zeigen detaillierter gewisse der in 3 gezeigten Einrichtungen;
5 zeigt schematisch Eingangs- und Ausgangsdatenfluß der Vorrichtung unter Berücksichtigung eines Schutzintervalls, sowie einen rekonstruierten Ausgangsfluß, und
6a und 6b sind Zeitablaufdiagramme, die einen Spezialfall der Funktionsweise einer erfindungsgemäßen Vorrichtung darstellen, der ein Schutzintervall zwischen den verschiedenen zu behandelnden Symbolen berücksichtigt.
In 1 bezeichnet das Bezugszeichen DF eine Pipeline-Vorrichtung zur Berechnung einer Fourier-Transformation, die eine Fourier-Transformation einer Anfangsgröße gleich 16 ausführen kann und zwei Basis-4-Verarbeitungsstufen ET0 und ET1 aufweist.
Die Eingangsstufe ET0 empfängt einen Fluß von Symbolen oder Datenblöcken BA, die jeweils sechzehn Daten A₀-A₁₅ aufweisen. Der Ausgang der Stufe ET0 gibt aufeinanderfolgende Blöcke BB aus vier Daten aus, die in der Stufe ET1 verarbeitet werden. Diese Stufe ET1 gibt das dem Eingangssymbol BA entsprechende Ausgangssymbol X₁₅...X₄X₀ aus.
Wenn für eine Basis-4-Verarbeitungsstufe die Größe des am Eingang empfangenen Datenblocks gleich N ist, kann dieser Datenblock allgemein in vier zeitlich aufeinanderfolgend empfangene Segmente aus jeweils N/4 Daten zerlegt werden. Das erste Segment besteht aus den Daten A_i ^K, das zweite Segment besteht aus den Daten A_N/4+i ^K, das dritte Segment besteht aus den Daten A_N/2+i ^K und das vierte Segment besteht aus den Daten A_3N/4+i ^K wobei i von 0 bis N/4-1 läuft und die an jedem empfangenen Datenblock in der Stufe ausgeführte Anzahl von Verarbeitungen des Schmetterlingstyps bedeutet. K stellt den K-ten von der Stufe empfangenen Block dar.
Im übrigen wissen Fachleute, daß s den Rang der betrachteten Stufe bezeichnet, N gleich N0/4^s ist, wobei N0 die Anfangsgröße der Fourier-Transformation ist, das heißt, die Größe jedes von der Eingangsstufe empfangenen Symbols.
Wenn ferner die betrachtete Stufe die erste ist, entspricht der K-te Block dem K-ten empfangenen Symbol.
Wenn dagegen die betrachtete Stufe nicht die erste ist (Rang s unterscheidet sich von Null), spaltet sich jedes Symbol am Eingang der Vorrichtung rekursiv innerhalb jeder Stufe in 4^s Blöcke K auf (K läuft von 0 bis 4^s-1).
2 zeigt den speziellen Fall von sechzehn Daten (N = 16) jedes von der Stufe ET0 empfangenen Blocks.
Die Basis-4-Verarbeitungsstufe führt also N/4 Verarbeitungen des Schmetterlingstyps an N/4 unterschiedlichen Gruppen aus vier Daten aus, die jeweils aus einem Datum des ersten Segments und den homologen Daten der drei anderen Segmente gebildet sind.
In dem speziellen Beispiel von 2 führt die Stufe ET0 aus: eine erste Verarbeitung des Schmetterlingstyps an der Gruppe, die aus den Daten A₀, A₄, A₈ und A₁₂ besteht eine zweite Verarbeitung des Schmetterlingstyps an der Gruppe, die aus den Daten A₁, A₅, A₉ und A₁₃ besteht und so weiter, bis eine vierte Verarbeitung des Schmetterlingstyps an der Gruppe, die aus den Daten A₃, A₇, A₁₁ und A₁₅ besteht.
Die Ergebnisse dieser Verarbeitungen des Schmetterlingstyps sind Zwischendaten, die ebenfalls in vier Zwischensegmenten angeordnet sind, die jeweils N/4 Zwischendaten enthalten.
Im einzelnen enthält das erste Zwischensegment die Zwischendaten A_i ^K*, enthält das zweite Zwischensegment die Zwischendaten A_N/4+i ^K*, enthält das dritte Zwischensegment die Zwischendaten A_N/2+i ^K* und enthält das vierte Zwischensegment die Zwischendaten A_3N/4+i ^K*.
Diese Zwischendaten werden nach den folgenden Formeln (I) bis (IV) gewonnen: Ai K* = Ai K + AN/4+i K + AN/2+i K + A3N/4+i K (I) AN/4+i K* = Ai K – AN/4+i K + AN/2+i K – A3N/4+i K (II) AN/2+i K* = Ai K – jAN/4+i K – AN/2+i K + jA3N/4+i K (III) A3N/4+i K* = Ai K + jAN/4+i K – AN/2+i K – jA3N/4+i K (IV)
In diesen Formeln bezeichnet j die komplexe Zahl, deren Quadrat gleich –1 ist, und i läuft von 0 bis N/4-1.
Diese Zwischendaten werden anschließend mit vorgegebenen Koeffizienten W⁰ (also 1), Wⁱ, W²ⁱ und W³ⁱ gemäß den betrachteten Segmenten multipliziert. Diese Koeffizienten sind klassische komplexe Koeffizienten, die Fachleuten bekannt sind.
Nach Multiplikation mit diesen Koeffizienten W erhält man am Ausgang der Verarbeitungsstufe vier Blöcke BB^4K, BB^4K+1 BB^4K+2, BB^4K+3, die jeweils N/4 Ausgangsdaten B_i ^4K, B_i ^4K+1 B_i ^4K+2, B_i ^4K+3 enthalten, wobei i von 0 bis N/4-1 läuft.
Alle Blöcke BB werden dann nacheinander von den Hauptverarbeitungseinrichtungen der zweiten Stufe ET1 verarbeitet, wobei jeder dieser Blöcke als ein Eingangssymbol für diese zweite Stufe betrachtet wird.
Folglich führen in 2 die Hauptverarbeitungseinrichtungen der Reihe nach eine Verarbeitung des Schmetterlingstyps an den vier Daten jedes Eingangsblocks BB aus, um Zwischendaten B^*, dann Ausgangsdaten zu gewinnen, die in der Tat im vorliegenden Fall das Ergebnis der Fourier-Transformation der Eingangsdaten A sind.
In 3 bezeichnet das Bezugszeichen MTE die Hauptverarbeitungseinrichtungen einer Basis-4-Verarbeitungsstufe der Vorrichtung DF. Diese Einrichtungen MTE weisen eine Eingangsklemme auf, die den aus mehreren Datenblöcken bestehenden Fluß INS empfängt, der entweder von einer externen Einrichtung der Vorrichtung herkommt, falls die betrachtete Stufe die erste ist (in diesem Fall repräsentieren die verschiedenen Blöcke die verschiedenen Symbole, an welchen die Fourier-Transformation auszuführen ist), oder von der vorausgehenden Stufe herkommt. Die Daten, die in jedem der empfangenen Blöcke enthalten sind, werden im Takt eines ersten Taktsignals SMCK bereitgestellt. Die Hauptverarbeitungseinrichtungen MTE werden ihrerseits von einem Grundtaktsignal MCK getaktet, dessen Frequenz entweder doppelt so hoch wie die Frequenz des Signals SMCK oder vier Mal so hoch ist, je nachdem, ob die Verarbeitungseinrichtungen MTE im Verlaufe jedes Zyklus des Signals SMCK entweder den Realteil und den Imaginärteil jedes Datums oder nur den Realteil oder den Imaginärteil empfangen.
Der Ausgangsdatenfluß OUS (nach Fourier-Transformation) wird an einer Ausgangsklemme dieser Verarbeitungsstufe ausgegeben.
Außerdem empfangen die Hauptverarbeitungseinrichtungen MTE ein erstes Steuersignal STBL, das entweder von externen Einrichtungen der Vorrichtung herkommt, falls die betrachtete Stufe die erste ist, oder von der vorausgehenden Stufe herkommt. Dieses Signal STBL zeigt zum Beispiel bei seinem Übergang in den Zustand "1" den Empfang des ersten Datums eines Blocks an. Gleichermaßen schicken die Einrichtungen MTE zur nächsten Stufe ein zweites Steuersignal STNX, das beispielsweise bei seinem Übergang in den Zustand "1" die Ausgabe des aus der Verarbeitung des Eingangsblocks hervorgegangenen ersten Ausgangsdatums anzeigt. Das von der aktuellen Stufe empfangene Signal STBL ist also das von der vorausgehenden Stufe ausgesandte Signal STNX.
Mit diesen Hauptverarbeitungseinrichtungen verbunden, weist die Basis-4-Verarbeitungsstufe Hauptspeichereinrichtungen auf, die hier aus einem statischen Hauptspeicher mit wahlfreiem einfachem Zugriff MM bestehen, der über ein mit dem Ausgang des Hauptspeichers verbundenes erstes Hauptregister oder Flipflop REG1 und über ein mit dem Eingang des Hauptspeichers MM verbundenes zweites Hauptregister oder Flipflop REG2 in einer Schleife mit den Hauptverarbeitungseinrichtungen MTE zurück verbunden ist. Der Speicher MM wird von einem Signal R/W schreib/lesegesteuert. Wenn dieses Signal beispielsweise den Wert "1" hat, handelt es sich um ein Lesen, und wenn es den Wert "0" hat, handelt es sich um ein Schreiben. Außerdem wird der Speicher von einem Adreßzeiger ADD adressiert. Bei jedem Zyklus des Grundtaktsignals MCK erfolgt entweder ein Schreibzugriff oder ein Lesezugriff auf den Speicher MM. Aufgrund dieser Tatsache erfolgt bei jedem Zyklus des ersten Taktsignals SMCK ein Lesezugriff, gefolgt von einem Schreibzugriff auf den Speicher. Das Register REG2 speichert die drei Daten, die im nächsten Taktzyklus in den Hauptspeicher MM geschrieben werden.
Zusätzlich zu diesen Hauptverarbeitungseinrichtungen und diesen Hauptspeichereinrichtungen weist die Basis-4-Stufe auch Hilfsverarbeitungseinrichtungen MTX auf, die mit dem Ausgang des ersten Hauptregisters REG1 verbunden sind und am Ausgang einen Fluß OUD aus rekonstruierten und bezüglich der Eingangsdaten INS zeitlich verzögerten Daten ausgeben.
Diese Hilfsverarbeitungseinrichtungen MTX sind mit Hilfsspeichereinrichtungen verbunden, die hier aus einem statischen Hilfsspeicher mit wahlfreiem einfachem Zugriff MMX bestehen, der über ein mit dem Ausgang des Hilfsspeichers MMX verbundenes drittes Hilfsregister oder Flipflop REG3 und über ein mit dem Eingang des Hilfsspeichers MMX verbundenes viertes Hilfsregister oder Flipflop REG4 in einer Schleife zu den Hilfsverarbeitungseinrichtungen MTX zurück verbunden ist. Dieses vierte Hilfsregister REG4 ist auch mit der Eingangsklemme der Stufe verbunden, um so direkt gewisse Daten des Eingangsflusses zu empfangen, wie detaillierter nachstehend zu sehen ist.
Der Speicher MMX wird von dem gleichen Signal R/W schreib/lesegesteuert. Außerdem wird der Speicher von dem gleichen Adreßzeiger ADD adressiert, der den Hauptspeicher MM adressiert. Somit erfolgt ebenfalls bei jedem Zyklus des ersten Taktsignals SMCK ein Lesezugriff, gefolgt von einem Schreibzugriff auf den Hilfsspeicher MMX.
Die Speicherkapazität der Hauptspeichereinrichtungen der Verarbeitungsstufe ist gleich 3N/4 Daten. Berücksichtigt man, daß zwei Pipeline-Ebenen, das heißt zwei Hauptregister REG1 und REG2, vorhanden sind, ist die Speicherkapazität des Hauptspeichers MM gleich N/4-1 Wörter aus drei Daten, während jedes Register REG1, REG2 ein Wort aus drei Daten speichern kann. Den Hauptspeicher MM kann man sich also als eine Matrix aus N/4-1 Zeilen und 3 Spalten vorstellen.
Die Speicherkapazität der Hilfsspeichereinrichtungen der Verarbeitungsstufe ist gleich N/2 Daten. Berücksichtigt man, daß zwei Pipeline-Ebenen, das heißt zwei Hilfsregister REG3 und REG4, vorhanden sind, ist die Speicherkapazität des Hilfsspeichers MMX gleich N/4-1 Wörter aus zwei Daten, während jedes Hilfsregister REG3, REG4 ein Wort aus zwei Daten speichern kann. Den Hilfsspeicher MMX kann man sich also als eine Matrix aus N/4-1 Zeilen und zwei Spalten vorstellen.
Die Hauptverarbeitungseinrichtungen weisen ein Addierer/Subtrahierer-Modul MD1 auf, das die Berechnung der Zwischendaten gemäß den obigen Formeln (I) bis (IV) erlaubt, sowie ein Multiplizierermodul MD2, das die Multiplikation dieser Zwischendaten mit den geeigneten Koeffizienten W erlaubt. Der Ausgang des Multiplizierermoduls gibt somit den Ausgangsdatenfluß OUS aus.
Die vier Ausgänge 0, 1, 2, 3 des Moduls MD1 stellen jeweils die Zwischendaten A_i ^K*, A_N/4+i ^K*, A_N/2+i ^K*, A_3N/4+i ^K* der vier Zwischensegmente bereit.
Die Eingangsklemme der Stufe, die den Eingangsdatenfluß INS empfängt, sowie die drei Ausgänge 1, 2, 3 des ersten Registers REG1 sind jeweils mit den vier Eingängen 0, 1, 2, 3 des Addierermoduls MD1 verbunden.
Die Eingangsklemme dieser Stufe ist außerdem mit dem Eingang 0 eines ersten Multiplexers MX1 verbunden, der vier Ein gänge hat und dessen drei Ausgänge mit den drei Eingängen des Registers REG2 verbunden sind.
Die drei anderen Eingänge 1, 2 und 3 des ersten Multiplexers MX1 sind sowohl mit den drei Ausgängen 1, 2, 3 des Registers REG1 als auch mit den drei Ausgängen 1, 2 und 3 des Moduls MD1 verbunden.
Der Ausgang 0 des Moduls MD1 ist mit dem Eingang 0 eines zweiten Multiplexers MX2 verbunden, der 4 Eingänge hat und dessen Ausgang mit dem Eingang des Multiplizierermoduls MD2 verbunden ist. Die drei anderen Eingänge 1, 2 und 3 des zweiten Multiplexers sind mit den drei Ausgängen des ersten Registers REG1 verbunden.
Die Daten jedes Eingangsblocks werden von einem ersten Modulo-N-Zähler WRC (Schreibzähler) indexiert, der beispielsweise von 0 bis N-1 in der Frequenz des ersten Taktsignals SMCK zählt. Gleichermaßen werden von einem zweiten Modulo-N-Zähler oder Lesezähler RDC, der beispielsweise auch von 0 bis N-1 in der Frequenz des ersten Taktsignals zählt, die Ausgangsdaten von 0 bis N-1 indexiert.
Diesbezüglich ist anzumerken, daß der Anstieg des ersten Steuersignals STBL auf 1, was den Empfang des ersten Datums des Blocks anzeigt, den Zähler WRC wieder initialisiert, während der Anstieg des zweiten Steuersignals STNX auf 1, was die Ausgabe des ersten Ausgangsdatums signalisiert, den Lesezähler RDC wieder initialisiert. Fachleute werden außerdem bemerkt haben, daß gemäß der Erfindung das zweite Steuersignal STNX in den Zustand 1 geht, wenn der erste Zähler WRC den Wert 3N/4-1 erreicht.
Der Zähler RDC steuert den Multiplexer MX2.
Genauer gesagt, wenn der Zähler RDC von 0 bis N/4-1 zählt, empfängt das Multiplizierermodul MD2 den vom Ausgang 0 des Moduls MD1 bereitgestellten Wert.
Wenn der Zähler RDC von N/4 bis N/2-1 zählt, empfängt das Modul MD2 den am Ausgang 1 des Registers REG1 bereitgestellten Wert.
Wenn der Zähler RDC von N/2 bis 3N/4-1 zählt, empfängt das Modul MD2 den am Ausgang 2 des Registers REG1 bereitgestellten Wert.
Wenn der Zähler RDC von 3N/4 bis N-1 zählt, empfängt das Modul MD2 den am Ausgang 3 des Registers REG1 bereitgestellten Wert.
Die Sinus- und Kosinuswerte der komplexen Koeffizienten W, die im Modul MD2 verwendet werden, sind beispielsweise in einem von dem Lesezähler RDC adressierten ROM-Speicher gespeichert.
Das Adreßsignal ADD des Speichers MM wird von einem Modulo-(N/4-1)-Zähler (zum Zwecke der Vereinfachung hier nicht dargestellt) bereitgestellt, der beispielsweise von 0 bis N/4-2 in der Frequenz des ersten Taktsignals SMCK zählt.
Der Multiplexer MX1 wird seinerseits von einem Steuersignal SC1 gesteuert, dessen Wert von denjenigen der Zähler WRC und RDC abhängt. Diesbezüglich weist die Verarbeitungsstufe Hauptsteuereinrichtungen MCE auf, die ausgehend vom Inhalt der Zähler WRC und RDC das Signal SC1 bereitstellen. Die verschiedenen Verbindungen zwischen dem Register REG2 und den verschiedenen Elementen der Stufe über den Multiplexer MX1 werden nachstehend auf funktionelle Weise detaillierter beschrieben. Ausgehend von dieser funktionellen Beschreibung können Fachleute ohne weiteres die Steuereinrichtungen MCE aus Logikgattern realisieren.
Unter Bezugnahme nun insbesondere auf 4b ist zu sehen, daß die Hilfsverarbeitungseinrichtungen MTX ein Modul MDX aufweisen, das, wie nachstehend detaillierter zu sehen ist, gewisse Daten des Eingangsblocks rekonstruieren wird. Dieses Modul MDX empfängt am Eingang die Ausgänge 2 und 3 des Registers REG1 sowie die Ausgänge des dritten Hilfsregisters REG3. Der Ausgang des Moduls MDX ist über einen vierten Multiplexer MX4, der von einem Steuersignal SC4 gesteuert wird, mit der Hilfsausgangsklemme der Stufe, das heißt, der Ausgangsklemme, die die rekonstruierten und zeitlich verzögerten Daten OUD ausgibt, verbunden.
Die zwei Ausgänge des Registers REG3 sind über einen dritten Multiplexer MX3 mit den zwei Eingängen des Registers REG4 verbunden. Das Register REG4 speichert die Daten, die beim nächsten Taktimpuls in den Hilfsspeicher MMX abgegeben werden.
Das Register REG4 kann über den Multiplexer MX3 auch gewisse Daten des Eingangsflusses INS sowie die vom dritten Ausgang des Registers REG1 ausgegebenen Daten empfangen. Die zwei Ausgänge des Registers REG3 sind außerdem mit den zwei anderen Eingängen des Multiplexers MX4 verbunden.
Die Hilfsverarbeitungseinrichtungen weisen außerdem Hilfssteuereinrichtungen MCX auf, die die zwei Steuersignale SC3 und SC4 für die Multiplexer MX3 und MX4 bereitstellen. Diese zwei Signale SC3 und SC4 hängen von den Werten des Zählers WRC und des Zählers RDC ab. Die Verbindungen zwischen den in dieser 4b dargestellten verschiedenen Elementen und folglich die Steuerung dieser Multiplexer werden nachstehend auf funktionelle Weise detaillierter beschrieben. Entsprechend wie bei den Hauptsteuereinrichtungen MCE können Fachleute unter Berücksichtigung dieser funktionellen Beschreibung die Steuereinrichtungen MCX ohne weiteres aus Logikgattern realisieren. Ferner können die Steuereinrichtungen MCE und MCX, obwohl sie zum Zwecke der Vereinfachung in den 4a und 4b getrennt dargestellt worden sind, in derselben Schaltung verwirklicht sein.
Das Adreßsignal ADD des Hilfsspeichers MMX wird auch von dem gleichen Modulo-(N/4-1)-Zähler bereitgestellt, der in der Frequenz des ersten Taktsignals SMCK beispielsweise von 0 bis N/4-2 zählt.
In bestimmten Anwendungen, insbesondere in digitalen Fernsehempfängern, sind die mehreren am Eingang der Berechnungsvorrichtung DF empfangenen Symbole durch ein Schutzintervall IG (5) voneinander beabstandet, das aus einer mehr oder weniger großen Anzahl Ng von Daten besteht, die im allgemeinen die Kopie von Enddaten des Symbols sind, das auf das Schutzintervall folgt.
5 zeigt den von der Basis-4-Eingangsstufe ET0 empfangenen Symbolfluß. Jedes Symbol ist ein Block aus sechzehn Daten. Der obere Teil von 5 zeigt die beiden ersten empfangenen Blöcke BA⁰ und BA¹, die durch ein Schutzintervall IG getrennt sind und deren jeweiliges erstes Datum durch den Anstieg des Signals STBL auf 1 erkannt wird. Das Schutzintervall IG ist also im vorliegenden Fall die Kopie der Enddaten des Blocks BA¹.
Der Mittelteil von 5 zeigt die entsprechenden Ausgangsblöcke BB. So entsprechen die durch das Signal STNX fest gelegten Blöcke BB⁰ – BB³ dem Block BA⁰, während die Blöcke BB⁴ – BB⁷ dem Block BA¹ entsprechen. Der Block BB⁴ ist durch Daten IIN, die mit denjenigen des Schutzintervalls berechnet worden sind und die keinerlei physikalische Bedeutung haben, von dem Block BB³ getrennt.
Der untere Teil von 5 zeigt den rekonstruierten, bezüglich des Eingangssymbolflusses zeitlich verzögerten und am Ausgang OUD der Verarbeitungsstufe ausgegebenen Symbolfluß. Im weiteren Verlauf des Textes bezeichnet das mit einem Datum oder einem Block verknüpfte Zeichen "!" dieses zeitlich verzögerte Datum oder diesen zeitlich verzögerten Block. Im unteren Teil dieser Figur ist also zu sehen, daß die zwei rekonstruierten Blöcke BA⁰! und BA¹! durch das Schutzintervall IG!, das dem Schutzintervall IG entspricht, voneinander getrennt bleiben. Da dies so ist, wird, wie nachstehend detaillierter zu sehen ist, das Schutzintervall einfach nur verzögert, aber nicht, wie gewisse Daten des Blocks, wieder berechnet. Zeitlich wird das verzögerte Intervall IG! gleichzeitig mit dem Endabschnitt des Blocks BA¹ bereitgestellt, was nach einer Korrelation in herkömmlichen Gleitkorrelationseinrichtungen ein Korrelationsmaximum ergibt.
Unter Bezugnahme insbesondere auf 4a und 4b wird nun detaillierter die Funktionsweise der Verarbeitungseinrichtungen dieser Stufe sowie das Füllen der verschiedenen Speicher beschrieben.
Angenommen, der Speicher MM enthält die Daten A_i ^K, A_N/4+i ^K und A_N/2+i ^K der ersten drei Segmente des Blocks K, die entsprechend ihrem Empfang, das heißt, in dem Maße, wie der Zähler WRC von 0 auf 3N/4-1 zählt, gespeichert worden sind. Im weiteren Verlauf des Textes bezeichnet der Index q zum Zwecke der Vereinfachung die Summe "i+Ng modulo N/4", wobei Ng die Anzahl der Daten des Schutzintervalls IG ist.
Allgemein gilt, wenn der Zähler WRC von 3N/4 bis N-1 zählt, empfänt die Stufe nacheinander am Ein an die Daten A_3N/4+1 ^K des vierten Segments des Blocks. Jedoch werden diese Daten nicht im Speicher MM gespeichert und werden mit den homologen Daten der ersten drei Segmente verwendet, um die Zwischendaten A_i ^K*, A_N/4+i ^K*, A_N/2+i ^K* und A_3N/4+i ^K* der vier Zwischensegmente zu berechnen.
Jedoch werden die Zwischendaten A_i ^K* des ersten Zwischensegments nicht im Hauptspeicher MM gespeichert und werden direkt zum Multiplizierermodul MD2 geschickt.
Dagegen werden entsprechend dem Empfang der Daten des vierten Segments des Blocks K die im Hauptspeicher MM gespeicherten und zu den ersten drei Segmenten des Blocks K gehörenden Daten jeweils durch die vom Modul MD1 berechneten und zu den letzten drei Zwischensegmenten gehörenden Zwischendaten ersetzt.
Außerdem werden entsprechend dem Empfang der Daten des vierten Segments des Blocks K einerseits die Daten des dritten Segments, die im Hauptspeicher MM gespeichert waren, und andererseits die Eingangsdaten des vierten Segments im Hilfsspeicher gespeichert.
Die Funktionsweise wird nun Phase für Phase beschrieben.
Phase 1: Der Wert des Zählers WRC ist gleich 3N/4 und der des Zählers RDC ist null.
Der dritte Ausgang des Registers REG1 wird mit dem ersten Eingang des Registers REG4 verbunden, um dort das Datum A_N/2 ^K zu speichern. Der Eingang 2 des Registers REG4 wird dann mit der Eingangsklemme der Stufe verbunden und empfängt das Datum A_3N/4 ^K. Die Ausgänge 1 und 2 des Registers REG3 enthalten die Daten A_N/2+NgK-1 bzw. A_3N/4+Ng ^K-1 Der Ausgang 2 des Registers REG3 wird dann mit der Ausgangsklemme OUD verbunden, um das rekonstruierte und zeitlich verzögerte Datum A_3N/4+Ng ^K-1! auszugeben.
Phase 2: Der Zähler WRC zählt von 3N/4+1 bis N-1, der Zähler RDC zählt von 1 bis N/4-1 und i läuft von 1 bis N/4-1 im Takt des Zählers WRC.
Dieses Mal ist es der erste Ausgang des Hilfsregisters REG3, der mit dem verzögerten Ausgang OUD verbunden wird, um das Datum des Schutzintervalls G_q ^K-1 auszugeben.
Der zweite Ausgang des Registers REG3 enthält somit das Datum A_3N/4+q ^K-1.
Phase 3: Der Zähler WRC zählt von 0 bis N/4-1, der Zähler RDC zählt von N/4 bis N/2-1 und i läuft von 0 bis N/4-1 im Takt des Zählers WRC.
In dieser Phase entspricht das Initialisieren des Zählers WRC auf Null dem Wert N modulo N dieses Zählers.
Am Eingang der Verarbeitungsstufe werden dann die Daten G_i ^K des Schutzintervalls empfangen. Es ist hier anzumerken, daß diese Daten G_i ^K, die sich auf den Block K beziehen, tatsächlich die Kopie des Endes des Blocks K+1 sind.
Die Ausgänge 1, 2, 3 des Registers REG1 geben jeweils die Zwischendaten A_N/4+i ^K*, A_N/2+i ^K* und A_3N/4+i ^K* aus.
Die Ausgänge 2 und 3 des Registers REG1 werden mit den Eingängen 2 und 3 des Registers REG2 verbunden, um dort die entsprechenden Daten zu speichern. Dagegen wird der Eingang 1 des Registers REG2 mit dem Eingang INS der Stufe verbunden, um die Schutzdaten G_i ^K zu empfangen.
Das Wort (A_N/2+i ^K, A_3N/4+i ^K) wird in das Register REG3 gelesen und zum Register REG4 zurückgeschickt.
Das Hilfsrekonstruktionsmodul rekonstruiert das zeitlich verzögerte Datum A_i ^K! ausgehend von der nachstehenden Formel (V): Ai K! = (AN/2+i K* + A3N/4+i K* )/2 + AN/2+i K (V)
Dieses verzögerte Datum A_i ^k! wird zum Hilfsausgang OUD ausgegeben.
Zu einem gegebenen Zeitpunkt wird beim Empfang des Datums A_i ^K+1 des nächsten Blocks K+1 der Zähler WRC wieder auf Null initialisiert (der Wert von i wird dann ebenfalls wieder auf Null initialisiert). Dagegen hat der Zähler RDC seinerseits den Wert N/2 noch nicht erreicht.
Alles, was für diese Phase 3 beschrieben worden ist, bleibt dann gültig, wenn das Datum G_i ^K durch A_i ^K+1 ersetzt wird und, was die anderen Daten betrifft, der Index i durch den Index q ersetzt wird. Außerdem gibt dann das Hilfsrekonstruktionsmodul das zeitlich verzögerte Datum A_q ^K! aus.
Phase 4: Der Zähler WRC ist immer noch in seiner Zählphase von 0 bis N/4-1, aber der Zähler RDC zählt nun von N/2 bis 3N/4-1.
Das Wort (G_q ^K, A_N/2+q ^K*, A_3N/4+q ^K*) wird in das Register REG1 gelesen.
Das Wort (A_i ^K+1, G_q ^K, A_3N/4+q ^K*) wird in das Register REG2 geschrieben. Die letzten zwei Daten dieses Worts stammen aus dem Register REG1, während das erste Datum aus dem Eingangsfluß stammt.
Das Wort (A_N/2+q ^K, A_3N/4+q ^K) wird in das Register REG3 gelesen und wieder im Register REG4 gespeichert.
Das Datum A_N/4+q ^K! wird im Rekonstruktionsmodul MDX ausgehend von der Formel (VI) rekonstruiert: AN/4+q K! = j(AN/2+q K* – A3N/4+q K*)/2 + A3N/4+q K (VI)
Fachleute werden hier gemerkt haben, daß damit begonnen wurde, die Speicherorte der Daten des Schutzintervalls im Hauptspeicher um eine Spalte nach rechts zu verschieben.
Phase 5: Der Zähler WRC zählt nun von N/4 bis N/2-1, der Zähler RDC zählt noch immer von N/2 bis 3N/4-1 und i läuft von 0 bis N/4-1 im Takt des Zählers WRC.
Das Wort (A_i ^K+1, A_N/2+q ^K*, A_3N/4+q ^K*) wird in das Register REG1 gelesen.
Das Wort (A_i ^K+1, A_N/4+i ^K+1, A_3N/4+q ^K*) wird im Register REG2 gespeichert. Das zweite Datum dieses Worts stammt direkt aus dem Eingangsfluß, während die zwei anderen Daten aus dem Register REG1 stammen.
Das Register REG3 ist immer noch direkt mit dem Register REG4 verbunden. Insbesondere wird das Wort (A_N/2+q ^K, A_3N/4+q ^K) in das Register REG3 gelesen und wieder im Register REG4 gespeichert.
Das Hilfsrekonstruktionsmodul rekonstruiert gemäß der Formel (VI) das zeitlich verzögert Datum A_N/4+q ^K! und schickt es zum Hilfsausgang OUD.
Phase 6: Der Zähler WRC ist noch immer in seiner Zählphase von N/4 bis N/2-1 (i ist nicht auf 0 initialisiert worden) und der Zähler RDC zählt von 3N/4 bis N-1.
Das Wort (A_i ^K+1, G_q ^K, A_3N/4+q ^K*) wird in das Register REG1 gelesen.
Das Wort (A_i ^K+1, A_N/4+i ^K+1, G_q ^K) wird im Register REG2 gespeichert. Das zweite Datum dieses Worts stammt noch immer aus dem Eingangsfluß, während die zwei anderen Daten wieder aus dem Register REG1 stammen.
Fachleute werden auch gemerkt haben, daß hier die Verschiebung einer Spalte von Daten des Schutzintervalls nach rechts fortgesetzt wird.
Die Hilfsregister REG3 und REG4 sind noch immer direkt miteinander verbunden. Insbesondere wird das Wort (A_N/2+q ^K, A_3N/4+q ^K) in das Register REG3 gelesen und im Register REG4 gespeichert.
Dagegen wird der erste Ausgang des Registers REG3 direkt mit dem Ausgang OUD verbunden, um das zeitlich verzögerte Datum A_N/2+q ^K! auszugeben. Fachleute werden also gemerkt haben, daß dieses rekonstruierte Datum nicht wieder berechnet worden ist, sondern einfach aus dem Hilfsspeicher herausgeholt worden ist.
Phase 7: Der Zähler WRC zählt von N/2 bis 3N/4-1, i läuft in diesem Zähltakt von 0 bis N/4-1 und der Zähler RDC zählt noch immer von 3N/4 bis N-1.
Das Wort (A_i ^K+1, A_N/4+i ^K+1, A_3N/4+q ^K*) wird in das Register REG1 gelesen.
Das Wort (A_i ^K+1, A_N/4+i ^K+1, A_N/2+i ^K+1) wird im Register REG2 gespeichert.
Die ersten zwei Daten stammen aus dem Register REG1, während das dritte Datum dieses Worts direkt aus dem Eingangsfluß stammt.
Die zwei Hilfsregister REG3 und REG4 werden direkt miteinander verbunden. Insbesondere wird das Wort (A_N/2+q ^K, A_3N/4+q ^K) in das Register REG3 gelesen und im Register REG4 gespeichert. Der erste Ausgang des Registers REG3 wird direkt mit dem Ausgang OUD verbunden, der das zeitlich verzögerte Datum A_N/2+q ^K! ausgibt.
Phase 8: Der Zähler WRC ist noch immer in seiner Zählphase von N/2 bis 3N/4-1 (i ist nicht wieder auf 0 initialisiert worden), aber der Zähler RDC zählt nun von 0 bis N/4-1, da er nach dem Wert N-1 automatisch wieder auf Null initialisiert wird.
Das Wort (A_i ^K+1, A_N/4+i ^K+1, G_q ^K) wird in das Register REG1 gelesen.
Das Wort (A_i ^K+1, A_N/4+i ^K+1, A_N/2+i ^K+1) wird im Register REG2 gespeichert. Die ersten zwei Daten dieses Worts stammen aus dem Register REG1, während das dritte Datum direkt aus dem Eingangsfluß stammt.
Ferner wird das Datum des Schutzintervalls G_q ^K (Ausgang 3 des Registers REG1) zum Eingang 1 des Registers REG4 geschickt, während der Eingang 2 des Registers REG4 das Datum empfängt, das am Ausgang 2 des Registers REG3 vorliegt, nämlich A_3N/4+q ^K. Das am Ausgang 1 des Registers REG3 gelesene Datum ist das Datum A_N/2+q ^K. Es ist dieses Mal der Ausgang 2 des Registers REG3, der direkt mit dem verzögerten Ausgang OUD verbunden wird.
Fachleute werden hier gemerkt haben, daß das Datum des Schutzintervalls in die Hilfsspeichereinrichtungen übertragen worden ist, bevor es später daraus herausgeholt wird.
Am Ende dieser Phase enthält der Hauptspeicher MM erneut die Daten der ersten drei Segmente des Blocks K+1 und ein kompletter neuer Schreib/Lese-Zyklus kann wieder beginnen (Phase 1).
Fachleute werden gemerkt haben, daß der Wert N_g vorab nicht bekannt sein muß, sofern er in diesem Beispiel kleiner als N/4 bleibt. In der Tat sind es einzig und allein die Übergänge 0, N/4, N/2 und 3N/4 der Zähler WRC und RDC, aus denen die verschiedenen Steuersignale für die verschiedenen Multiplexer ausgearbeitet werden.
Die Tatsache schließlich, daß gemäß der Erfindung das Adressieren des Hauptspeichers und des Hilfsspeichers ausgehend von dem gleichen Adreßzähler gesteuert wird, vereinfacht die Hardware-Ausführung der Speicherebene in hohem Maße.
Die 6a und 6b zeigen Zeitablaufdiagramme für die Verarbeitung der Blöcke BA⁰ und BA¹ in der Eingangsstufe gemäß der vorstehend beschriebenen Funktionsweise. Es ist hier anzumerken, daß die Zeilen REG2 und REG4 in diesen Figuren den gültigen Inhalt am Ausgang dieser Register darstellen, was die Verschiebung um einen Taktzyklus nach rechts in Vergleich zum Wert des Zählers WRC erklärt. Der erste Zählzyklus des Zählers WRC von 0 bis 15 (6a) entspricht einer Phase des anfänglichen Auffüllens des Hauptspeichers MM. Schließlich ist in diesem Beispiel N_g = 3.
Selbstverständlich läßt sich all das, was beschrieben worden ist, auf elektronische Vorrichtungen zur Berechnung von Fourier-Transformationen großer Anfangsgröße verallgemeinern. So sind in den Anwendungen für digitales Fernsehen, die die Ausführung von Fourier-Transformationen von 8192 Punkten erfordern, sechs Basis-4-Stufen, gefolgt von einer herkömmlichen Basis-2-Endstufe, vorgesehen.
In dem Fall, in welchem anstelle von Speichern mit einfachem Zugriff Speicher mit zweifachem Zugriff verwendet werden, wäre die Frequenz des Taktsignals MCK gleich der Frequenz des Taktsignals SMCK (falls bei jedem Zyklus des Signals SMCK der Imaginär- und Realteil jedes Datums empfangen werden) und die Leseadresse der Speicher MM und MMX wäre dann gleich die Schreibadresse verringert um 1.

Claims

Verfahren zur Steuerung einer Basis-4-Verarbeitungsstufe einer Vorrichtung zur Berechnung einer Fourier-Transformation in Pipeline-Architektur, dadurch gekennzeichnet, daß für jeden am Eingang der Stufe empfangenen Block aus N Daten nur drei Viertel der Daten des Blocks in Hauptspeichereinrichtungen (MM), die einen Hauptspeicher mit wahlfreiem Zugriff aufweisen, gespeichert werden und ausgehend von diesen gespeicherten Daten und anderen Daten des Blocks eine Berechnung der Fourier-Transformation ausgeführt wird, und dadurch, daß nur eine Hälfte der empfangenen Daten in Hilfsspeichereinrichtungen (MMX), die einen Hilfsspeicher mit wahlfreiem Zugriff aufweisen, gespeichert werden und ausgehend vom Inhalt der Haupt- und Hilfsspeichereinrichtungen alle Daten des Blocks rekonstruiert werden, um einen rekonstruierten Datenblock (BA!) zu erhalten, der bezüglich des Eingangsblocks (BA) zeitlich verzögert ist.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die Stufe (ET0) die N Daten des Blocks nacheinander empfängt, die in vier aufeinanderfolgenden Segmenten, die jeweils N/4 Daten enthalten, angeordnet sind, wobei jedes Datum eines Segments mit den homologen Daten der drei anderen Segmente eine Gruppe aus vier Daten bildet, dadurch, daß die in den ersten drei Segmenten enthaltenen Daten entsprechend ihrem Empfang in den Hauptspeichereinrichtungen (MM) gespeichert werden, dadurch, daß entsprechend dem Empfang der im vierten Segment enthaltenen Daten die Daten, die im dritten Segment enthalten sind und in den Hauptspeichereinrichtungen (MM) gespeichert sind, sowie die im vierten Segment enthaltenen Daten in den Hilfsspeichereinrichtungen (MMX) gespeichert werden, an jeder dieser Gruppen eine Verarbeitung des "Schmetterlingstyps" ausgeführt wird, um aufeinanderfolgende Gruppen aus vier Zwischendaten (A^*) auszuarbeiten, die jeweils in vier aufeinanderfolgenden Zwischensegmenten angeordnet sind, und die in den Hauptspeichereinrichtungen gespeicherten Daten jeweils durch die in den letzten drei Zwischensegmenten enthaltenen Zwischendaten ersetzt werden.
Verfahren nach Anspruch 2, dadurch gekennzeichnet, daß die in den ersten zwei Segmenten enthaltenen Daten rekonstruiert werden, indem sie wieder berechnet werden, und die in den letzten zwei Segmenten enthaltenen Daten rekonstruiert werden, indem sie temporär in den Hilfsspeichereinrichtungen (MMX) gespeichert werden, bevor sie daraus herausgeholt werden.
Verfahren nach Anspruch 1, 2 oder 3, dadurch gekennzeichnet, daß, wenn zwei aufeinanderfolgende Eingangsblöcke durch ein Schutzintervall (IG) getrennt sind, alle Daten des Schutzintervalls entsprechend dem Empfang der Daten dieses Schutzintervalls nacheinander in den Hauptspeichereinrichtungen gespeichert werden, anschließend aufeinanderfolgende Verschiebungen der Speicherorte der Daten des Schutzintervalls ausgeführt werden, sie dann nacheinander aus den Hauptspeichereinrichtungen (MM) herausgeholt werden, um sie nacheinander in den Hilfsspeichereinrichtungen (MMX) zu speichern, bevor sie daraus nacheinander herausgeholt werden, um ein zeitlich verzögertes Schutzintervall (IG!) wieder herzustellen, das die zwei aufeinanderfolgenden rekonstruierten, bezüglich der zwei Eingangsblöcke zeitlich verzögerten Blöcke trennt.
Verfahren nach den Ansprüchen 2 und 4, dadurch gekennzeichnet, daß die aufeinanderfolgenden Verschiebungen der Speicherorte der Daten des Schutzintervalls (IG) und die Speicherung in den Hilfsspeichereinrichtungen entsprechend dem Empfang der in den ersten drei Segmenten des Eingangsblocks enthaltenen Daten ausgeführt werden.
Elektronische Vorrichtung zur Berechnung einer Fourier-Transformation in Pipeline-Architektur, wobei die Vorrichtung mindestens eine Basis-4-Verarbeitungsstufe (ET0) aufweist, die am Eingang aufeinanderfolgende Blöcke aus N Daten empfangen kann, dadurch gekennzeichnet, daß die Verarbeitungsstufe aufweist: Hauptspeichereinrichtungen (MM), die eine Speicherkapazität von 3N/4 Daten haben und einen Hauptspeicher mit wahlfreiem Zugriff aufweisen, Hilfsspeichereinrichtungen (MMX), die eine Speicherkapazität von N/2 Daten haben und einen Hilfsspeicher mit wahlfreiem Zugriff aufweisen, Hauptverarbeitungseinrichtungen (MTE), die ausgehend vom Inhalt der Hauptspeichereinrichtungen (MM) und N/4 anderen Daten des Blocks Fourier-Transformationen einer Grundgröße gleich 4 an jedem Eingangsblock ausführen, und Hilfsverarbeitungseinrichtungen (MTX), die ausgehend vom Inhalt der Haupt- und Hilfsspeichereinrichtungen alle Daten des Eingangsblocks rekonstruieren, um einen rekonstruierten, bezüglich des Eingangsblocks zeitlich verzögerten Datenblock zu erhalten.
Vorrichtung nach Anspruch 6, dadurch gekennzeichnet, daß die Hauptverarbeitungseinrichtungen (MTE) der Basis-4-Stufe jeweils N/4 Verarbeitungen des Typs "Schmetterling" an N/4 unterschiedlichen Gruppen aus vier Daten jedes von dieser Stufe verarbeiteten Datenblocks ausführen, dadurch, daß die Hauptspeichereinrichtungen (MM) einen Hauptspeicher mit wahlfreiem Zugriff und n Hauptregister (REG1, REG2) aufweisen, die jeweils in Reihe mit dem Hauptspeicher verbunden sind, dadurch, daß der Hauptspeicher (N/4)-(n-1) Wörter aus drei Daten speichern kann, dadurch, daß jedes Hauptregister 1 Wort aus drei Daten speichern kann, dadurch, daß die Hilfsspeichereinrichtungen einen Hilfsspeicher mit wahlfreiem Zugriff (MMX) und n Hilfsregister (REG3, REG4) aufweisen, die jeweils in Reihe mit dem Hilfsspeicher verbunden sind, dadurch, daß der Hilfsspeicher (N/4)-(n-1) Wörter aus zwei Daten speichern kann und dadurch, daß jedes Hilfsregister 1 Wort aus zwei Daten speichern kann.
Vorrichtung nach Anspruch 6 oder 7, dadurch gekennzeichnet, daß die Basis-4-Verarbeitungsstufe (ET0) einen Eingang aufweist, um im Takt eines ersten Taktsignals (SMCK) der Reihe nach die N Daten eines aktuellen Blocks zu empfangen, die in vier aufeinanderfolgenden Segmenten angeordnet sind, die jeweils N/4 Daten enthalten, wobei jedes Datum eines Segments mit den homologen Daten der drei anderen Segmente eine Gruppe aus vier Daten bildet, dadurch, daß die Hauptverarbeitungseinrichtungen (MTE) aufweisen: ein Addierer/Subtrahierer-Modul (MD1), das bei jedem Zyklus des ersten Taktsignals eine Verarbeitung des Typs "Schmetterling" an jeder dieser so gebildeten Gruppen ausführen kann, um aufeinanderfolgende Gruppen aus vier Zwischendaten (A^*) auszuarbeiten, die jeweils in vier aufeinanderfolgenden Zwischensegmenten angeordnet sind, ein Multiplizierermodul (MD2), das bei jedem Zyklus des ersten Taktsignals die Zwischendaten mit vorgegebenen Multiplikatorkoeffizienten multiplizieren kann, und Hauptsteuereinrichtungen (MCE), die die in den ersten drei Segmenten enthaltenen Daten entsprechend ihrem Empfang nacheinander zu den Hauptspeichereinrichtungen (MM) schicken können und entsprechend dem Empfang der im vierten Segment enthaltenen Daten die in den Hauptspeichereinrichtungen gespeicherten Daten jeweils durch die in den letzten drei Zwischensegmenten enthaltenen Zwischendaten ersetzen können, und dadurch, daß die Hilfsverarbeitungseinrichtungen aufweisen: ein Hilfsrekonstruktionsmodul (MDX), das die im ersten und zweiten Segment enthaltenen Daten des Eingangsblocks wieder berechnen kann, und Hilfssteuereinrichtungen (MCX), die die im dritten Segment enthaltenen und in den Hauptspeichereinrichtungen gespeicherten Daten sowie die im vierten Segment enthaltenen Daten zu den Hilfsspeichereinrichtungen schicken können und sie daraus herausholen können, um die im dritten und vierten Segment enthaltenen Daten zu rekonstruieren.
Vorrichtung nach Anspruch 8, dadurch gekennzeichnet, daß die Hauptspeichereinrichtungen ein mit dem Ausgang des Hauptspeichers verbundenes erstes Hauptregister (REG1) und ein mit dem Eingang des Hauptspeichers verbundenes zweites Hauptregister (REG2) aufweisen, dadurch, daß der Ausgang des ersten Hauptregisters erstens über einen ersten steuerbaren Multiplexer (MX1) mit dem Eingang des zweiten Hauptregisters verbunden ist, zweitens mit dem Eingang des Addierer/Subtrahierer-Moduls (MD1) verbunden ist und drittens über einen zweiten steuerbaren Multiplexer (MX2) mit dem Eingang des Multiplizierermoduls (MD2) verbunden ist, dadurch, daß der Ausgang des Addierer/Subtrahierer-Moduls (MD1) einerseits über den ersten Multiplexer (MX1) mit dem Eingang des ersten Hauptregisters (REG1) verbunden ist und andererseits über den zweiten Multiplexer (MX2) mit dem Eingang des Multiplizierermoduls (MD2) verbunden ist, dadurch, daß die Hilfsspeichereinrichtungen ein mit dem Ausgang des Hilfsspeichers verbundenes drittes Hilfsregister (REG3) und ein mit dem Eingang des Hilfsspeichers verbundenes viertes Hilfsregister (REG4) aufweisen, dadurch, daß der Ausgang des dritten Hilfsregisters erstens über einen dritten steuerbaren Multiplexer (MX3), der auch am Eingang mit der Eingangsklemme (INS) der Stufe sowie mit dem Ausgang des ersten Hauptregisters (REG1) verbunden ist, mit dem Eingang des vierten Hilfsregisters verbunden ist, zweitens mit dem Eingang des Hilfsrekonstruktionsmoduls (MDX) verbunden ist und drittens über einen vierten steuerbaren Multiplexer (MX4) mit dem Ausgang zur Ausgabe der rekonstruierten und verzögerten Daten (OUD) verbunden ist, dadurch, daß ein Eingang des Hilfsmoduls (MDX) mit einem Ausgang des ersten Hauptregisters verbunden ist, dadurch, daß der Ausgang des Hilfsrekonstruktionsmoduls mit einem Eingang des vierten Multiplexers verbunden ist, und dadurch, daß die Hauptsteuereinrichtungen (MCE) und die Hilfssteuereinrichtungen (MCX) aufweisen: vier Multiplexer, einen von dem ersten Taktsignal getakteten, beim Empfang des ersten Datums jedes Blocks wieder initialisierbaren ersten Modulo-N-Zähler (WRC), einen von dem ersten Taktsignal getakteten, bei der Ausgabe des ersten Ausgangsdatums der Stufe wieder initialisierbaren zweiten Modulo-N-Zähler (RDC) und ein Steuermodul (MCE, MCX), das ausgehend von den Zählwerten der zwei Zähler die Steuersignale für die vier Multiplexer bereitstellt, und dadurch, daß die Haupt- und Hilfsverarbeitungseinrichtungen gemeinsame Einrichtungen zum Adressieren des Hauptspeichers und des Hilfsspeichers aufweisen, die einen Modulo-(N/4-1)-Zähler aufweisen.
Vorrichtung nach einem der Ansprüche 6 bis 9, dadurch gekennzeichnet, daß, wenn zwei aufeinanderfolgende Eingangsblöcke durch ein Schutzintervall (IG) getrennt sind, die Hauptverarbeitungseinrichtungen Verschiebungseinrichtungen (MX2) aufweisen, die aufeinanderfolgende Verschiebungen der Speicherorte der Daten des Schutzintervalls im Hauptspeicher ausführen können.
Vorrichtung nach den Ansprüchen 9 und 10, dadurch gekennzeichnet, daß die Verschiebungseinrichtungen den zweiten Multiplexer (MX2) aufweisen.