DE3789116T2 - Prozessor zur zweidimensionalen diskreten cosinustransformation. - Google Patents

Description

Gebiet der Erfindung
• Die Erfindung bezieht sich auf einen Prozessor, um Raumbereichssignale, z. B. Videosignale, in Frequenzbereichssignale mittels eines mathematischen Verfahrens, das als eine diskrete Cosinustransformation (DCT) bekannt ist, umzuwandeln.
Hintergrund der Erfindung
• Die DCT wird als die effektivste Technik unter den verschiedenen Transformations-Codiermethoden zur Abbildungskomprimierung oder Videobandbreitenkomprimierung betrachtet. Eine DCT ähnelt einer diskreten Fouriertransformation (DFT), umfaßt jedoch nur einen Cosinusterm. Um auf diese Weise eine Bandbreitenkomprimierung zu erreichen, kann ein quadratischer Block digital kodierter Bildelemente oder Pixel mittels eines zweidimensionalen (N·N) DCT-Prozessors, dem der N·N-Block von Pixeldaten zugeführt wird, in den Frequenzbereich transformiert werden, wobei die Eingangsdatenmatrix mit einer N·N-diskreten Cosinusmatrix multipliziert wird, um eine Zwischenmatrix zu erhalten. Danach wird die transponierte Zwischenmatrix mit derselben diskreten Cosinusmatrix multipliziert, um die gewünschte zweidimensionale transformierte Matrix zu erhalten. Die Elemente der transformierten Matrix können dann quantisiert werden, und nur der aktivste Term darin muß übertragen werden. Bei dem Empfänger wird eine inverse Transformation durchgeführt, um das ursprüngliche Videosignal im Raumbereich wiederherzustellen. Bei einer N·N-DCT ergibt ein größeres N eine bessere Komprimierungsrate, erfordert jedoch mehr Berechnungen.
• Matrix-Multiplikation umfaßt das Bilden eines inneren Produkts zweier N·1- Vektoren, um ein einzelnes Produktmatrixelement zu erhalten. Deshalb muß jedes Element einer Zeile der Eingangsmatrix mit je einem entsprechenden Element einer Spalte der Cosinusmatrix multipliziert und die Produkte addiert werden, um ein einzelnes Produktmatrixelement zu erhalten. Deshalb müssen für die Transformation eines 16·16-Blocks von Pixeln 16 Produkte addiert werden, um ein einzelnes Element oder einen Koeffizienten der Zwischenmatrix und der transformierten Matrix zu erhalten, wobei jedes von ihnen 256 Elemente besitzt. Viele schnelle Algorithmen wurden hergeleitet, um die Zahl der nötigen Berechnungen zu reduzieren. Zum Beispiel ist die DCT-Matrix in mehrere kleine Matrizen zerlegt worden, was zu Schmetterlingsstrukturen führt. Diese Schmetterlingsstrukturen reduzieren die Berechnung bedeutend, benötigen jedoch immer noch viele Multiplizierer hoher Geschwindigkeit, die einen großen Siliziumbereich für eine IC-Implementierung benötigen, und führen zu unschönen Zwischenverbindungen, schlechter Leitwegführung auf Chips und zu einer unregelmäßigen Form. Eine Matrix-Zerlegungstechnik, die nicht DCT- sondern Hadamard- und Haar-Transformationen benutzt, ist in einem Artikel mit dem Titel "Real-Time Orthogonal Transformation of Colour-Television Pictures" im Philips Technical Review, Ausgabe 38, NF. 415,1978179, S. 119-130 beschrieben. In dem beschriebenen System werden Addition und Subtraktion, die in den Transformationen benötigt werden, parallel durch schnelle Algorithmen, die darin in den Fig. 10 und 11 dargestellt sind, ausgeführt.
• All diese Faktoren machen VLSI-Implementierung (Implementierung mit sehr hohem Integrationsgrad) von Schmetterlingsstrukturen sehr ineffizient. Ein Beispiel für VLSI-Implementierung der DCT, die eine solche Struktur verwendet, ist in einem Artikel mit dem Titel "A Discrete Fourier-Cosine Transform Chip" in IEEE Journal on Selected Areas in Communication, Januar 1986, S. 49-61 beschrieben. Der sich ergebende Chip, der darin in Fig. 17 gezeigt ist, umfaßt viele Multiplizierer, nutzt den Siliciumbereich nicht effektiv und kann nur eine eindimensionale 8·1- Transformation implementieren. Die zweidimensionale Transformation enthält zwei eindimensionale Transformationen und benötigt eine temporäre Speicherung für Zwischenergebnisse und die Matrixtransposition, weshalb sie viel komplexer als die eindimensionale Transformation ist. Auch wird in einem Artikel mit dem Titel "A Pipelined Distributed Arithmetic PFFT Processor" in IEEE Transactions on Computers, Ausgabe C-32, Nr. 12, Dezember 1983, S. 1128-1136 eine Primärfaktor- Fourier-Tranformation (PFFT) beschrieben, die das Zerlegen der diskreten Fourier-Transformation in einen Satz von relativ kurzen Primärlängentransformationen entwickelt und eine Matrix-Zerlegungstechnik wie der oben beschriebenen Typ ist.
• Die Implementierung der PFFT verwendet eine verteilte Arithmetik, die Verweistabellen umfaßt, die in ROMs gespeichert sind. Die Eingangsschaltungsanordnung zum Übergeben der in ROMs gespeicherten Daten an die Verweistabellen umfaßt eine "Winkel-Dreh"-Schaltung, ein paar RAMs, einen Wortauswahlzähler und einen "Leitungs-Signalspeicher". Eine Technik zum Reduzieren der Größe eines ROMs durch Hinzufügen besonders kleiner ROMs und eines Addierers ist ebenfalls darin in Fig. 8 enthalten.
• Unsere beanspruchte Erfindung ist eine Reaktion auf eine Notwendigkeit für die Echtzeitverarbeitung einer zweidimensionalen DCT, die effizient durch eine VLSI- Technologie nach dem Stand der Technik implementiert werden kann. Unsere Erfindung sieht eine Echtzeitverarbeitung einer 16·16-DCT auf einem einzelnen Chip vor. Dies bedeutet, daß der Prozessor 16·16 Matrizen für das Anlegen an einen Quantisierer mit der selben Rate, mit der die 16·16 Eingangsmatrizen durch die Videokamera erzeugt wurden, zur Verfügung stellen muß. Der Prozessor sollte in der Lage sein, mit einer Eingangs-Abtast- oder Pixel-Rate von 14,3 MHz umzugehen, die eine Rate ist, die häufig in digitalen Videosystemen mit aktueller MOS- Technologie verwendet wird. Aufgrund der großen Zahl von benötigten Berechnungen kann Echtzeitverarbeitung mit dieser Rate nur durch Ausnützen inhärenter Gleichzeitigkeit und Parallelität in der Architektur erreicht werden. Auch da die Siliziumbereiche und die Entwicklungsbemühung, die zum Implementieren eines Algorithmus benötigt werden, sehr stark von dem Grad der Regelmäßigkeit der Architektur abhängig sind, kann man erkennen, daß die Herausforderung der effizienten VLSI-Implementierung einer DCT darin besteht, eine Architektur zu entwickeln, die die gewaltige Zahl von Multiplikationen, die bei einer herkömmlichen Struktur benötigt wird, verwirklichen kann.
Zusammenfassung der Erfindung
• Anstelle einer Umsetzung schneller Algorithmen in Silizium, verwenden wir, entsprechend unserer beanspruchten Erfindung, eine mit einer Dezimierung der Frequenz kombinierte verteilte Arithmetik, bit-serielle und bit-parallele Datenstrukturen und Partialsummen, um gleichzeitig und mit minimaler ROM-Größe innere Vektorprodukte zu implementieren. Neuartige Eingangs-/Ausgangs-Schaltungsanordnungen und effiziente Matrixtranspositions-Schaltungsanordnungen sind ausgedacht worden. Daraus ergibt sich eine Architektur (oder Schaltungsanordnung) mit einer sehr regelmäßigen Struktur und ohne Multiplizierer. Dies ist möglich, weil die inhärenten Eigenschaften der Transformationsoperationen, nämlich (1) die Tranformationsmatrixelemente Konstanten sind, die die Verwendung der verteilten Arithmetik vorsehen, wobei Speicher-Verweistabellen oder Festwertspeicher (ROMs) durch Multiplizierer ersetzt sind, und (2) die Matrix-Vektorprodukte durch mehrere gleichzeitige innere Vektorprodukte verwirklicht werden. Die Dezimierung der Frequenz und Partialsummen werden dazu verwendet, die Größe der benötigten Verweistabellen zu reduzieren. Die bit-serielle Struktur wird dazu verwendet, die Dezimierung der Frequenz zu implementieren, so daß der Siliziumbereich möglichst klein ist und die Leitwegführung außerordentlich vereinfacht wird. Das Ergebnis ist ein zweidimensionaler DCT-Prozessor, der nur aus Speichern, Addierern und Registern besteht; keine Multiplizierer werden benötigt. Die Regelmäßigkeit des hochgleichzeitigen Betriebs der Schaltungsanordnung erlaubt eine modulare Entwicklung, ein ideales Merkmal für VLSI-Implementierung. Auch verbindet die Architektur sehr vorteilhaft bit-serielle und bit-parallele Schaltungsanordnungen. Unsere neuartige Architektur kann auch an andere zweidimensionale lineare Operationen angepaßt werden.
• Unser zweidimensionaler DCT-Prozessor umfaßt einen eindimensionalen (N·1)- Spalten-DCT-Eingangsprozessor, an den die N·N Eingangsdaten nacheinander Spalte für Spalte angelegt werden. Der Eingangs- oder Spaltenprozessor wurde entwickelt, um die Spaltentransformation der Eingangsdaten in einer Schaltungsanordnung zu erzeugen, die eine verteilte Arithmetik mit den zusätzlichen Merkmalen der Dezimierung der Frequenz und Partialsummen verwendet, um die Zahl der benötigten ROMs zu reduzieren. Der N·1-Eingangsprozessor ist mit N Schaltungen versehen, von denen jede einen Festwertspeicher (ROM) und einen hintereinander geschalteten Akkumulator umfaßt, und die RACs genannt werden. Die Akkumulatoren berechnen gleichzeitig die Elemente der Spaltentransformation durch Verschieben und Addieren der Daten, die von den ROMs abgefragt werden. Der resultierende Zwischenvektor ist in einer Zeile eines N·N-Transpositionsspeichers gespeichert, der einen RAM umfaßt. Jede Spalte der Datenmatrix liegt an den N·1- Eingangsprozessor der Reihe nach an, um die N·N-Zwischenmatrix (Y) zu erzeugen, die das Produkt (XtC) der Transposition der Datenmatrix (Xt) und der diskreten Cosinusmatrix (C), die durch die Konstanten, die in dem ROM gespeichert sind, dargestellt werden, ist. Die hochgestellten Zeichen "t" bezeichnen die Transpositionen der Matrizen. Ein zweiter oder N·1-Zeilen-DCT-Ausgangsprozessor wird dann verwendet, um die eindimensionale N·1-DCT für jede Spalte von XtC zu berechnen, die aus der Speicherung im Speicher ausgelesen werden. Das Ergebnis dieser zweiten oder Reihen-Transformationsoperation ist deshalb CtXC, was die gewünschte zweidimensionale N·N-DCT ist. Der Prozessor ist mit einer Steuerschaltung versehen, die Takt- und andere Steuer-Signale liefert, um den Betrieb der beschriebenen Komponenten zu steuern.
• Der N·1-DCT-Eingangsprozessor umfaßt ein N-stufiges Eingangsregister, an das die Eingangsdaten nacheinander auf n&sub1; parallelen Leitungen angelegt werden, wobei n&sub1; die Zahl der Bits pro Wort oder Pixel der Eingangsdaten ist. Sobald sich das Eingangsregister mit einer Spalte von Daten füllt, wird die gesamte Spalte gleichzeitig in bit-parallelem Format zu einem Halteregister verschoben und das Eingangsregister beginnt dann die nächste Spalte von Daten zu sammeln. Die Daten in jeder der N Stufen des Halteregisters werden dann gleichzeitig Bit für Bit, mit dem niedrigstwertigen Bit zuerst, herausgeschoben. Die N-Bit-Worte, die so gebildet werden, werden in zwei N/2-Bit-Worte umgewandelt, als Teil einer Technik, die als erststufige Dezimierung der Frequenz bekannt ist, und die sich ergebenden N/2-Bit-Worte werden dazu benutzt, alle ROMs der RACs gleichzeitig zu adressieren. Da die erststufige Dezimierung die n&sub1; vorzeichenlosen Eingangsdaten in (n&sub1;+2)-Bit Zweierkomplement-Zahlen umwandelt, wird die gleiche Operation n&sub1;+2-mal wiederholt und die n&sub1;+2 Worte, die aus jedem ROM ausgelesen werden werden nacheinander zu den Inhalten des Akkumulators hinzuaddiert, der einen Schieberegister mit einer festverdrahteten 1-Bit-Rechtsverschiebung umfaßt. Das Vorzeichenbit, das ein Teil des Datenworts ist, führt an Stelle einer Addition zu einer Subtraktion. Der aufsummierte Ausgang eines jeden dieser RACs umfaßt, nachdem jede Spalte von Ausgangsdaten erzeugt worden ist, einen einzelnen Koeffizienten oder ein Element der Spaltentransformation. Die Inhalte aller RACs werden gleichzeitig und in bit-parallelem Format an ein N-stufiges Ausgangsregister übertragen, nach welchem die Inhalte daraus nacheinander in eine Zeile (oder Spalte) des Transpositionsspeichers auf n&sub2;-parallelen Leitungen verschoben werden. Nachdem der N·N-Speicher auf diese Art gefüllt ist, liest der zweite oder N·1- Zeilen-DCT-Ausgangsprozessor die Matrix aus, die in dem RAM-Speicher Spalte für Spalte (oder Zeile für Zeile) gespeichert ist, so daß die Transposition von XtC erreicht wird. Der zweite N·1-DCT erzeugt dann die gewünschte zweidimensionale N·N-DCT auf die gleiche Weise, auf die es der erste oder DCT-Eingangsprozessor tut. Beide N·1-Prozessoren könnten ähnliche Schaltungen umfassen, mit der Ausnahme daß mehrere Bits benötigt werden könnten, um die Daten an dem zweiten N·1-Prozessor anzulegen.
• Der neuartige zweidimensionale N·N-Prozessor umfaßt einen ersten N·1-DCT- Prozessor, an den die Transposition eines N·N-Blocks der Eingangsdaten durch spaltenweises Lesen der ursprünglichen Matrix angelegt wird, wobei der erste N·1-Prozessor eine Einrichtung umfaßt, um gleichzeitig N innere Vektorprodukte für jede Spalte der Eingangsdaten zu berechnen, die eine verteilte Arithmetik benutzen, wobei die Konstanten der diskreten N·N-Cosinusmatrix in N RACs gespeichert werden, wobei jede von ihnen ein ROM plus einem Akkumulator umfaßt, wobei die ROMs durch N/2-bit-Worte adressiert sind, die aus den Datenworten der Spalten der Eingangsdaten gewonnen werden. Die so aus den ROMs ausgelesenen Worte werden in einem Schieberegister durch eine Schiebe- und Addier- Operation aufaddiert, wobei der Ausgang eines jeden der N RACs ein unterschiedliches Element oder einen Koeffizienten einer Reihe (oder Spalte) einer N·N- Zwischenmatrix umfaßt, welcher die N·1-Transformationen des Blocks der Eingangsdaten umfaßt. Es ist eine Schaltungsanordnung vorgesehen, um die Zwischenmatrix in einem N·N-RAM-Array zu speichern und dann dessen Transponierte in einen zweiten N·1-DCT-Prozessor auszulesen, der die gewünschte zweidimensionale N·N-DCT mittels einer Schaltungsanordnung erzeugt, ähnlich der, die dazu verwendet wird, die oben genannte N·N-Zwischenmatrix zu erzeugen. Es ist eine geeignete Steuerschaltungsanordnung vorgesehen, um die benötigten Steuersignale zu erzeugen.
• Es ist deshalb eine Aufgabe der Erfindung, einen zweidimensionalen diskreten Cosinustransformations(DCT)-Prozessor vorzusehen, der ein Paar von eindimensionalen DCT-Prozessoren benutzt, um die zweidimensionale DCT einer N·N- Matrix von Eingangsdaten durch ein Reihen-Spalten-Dekompositionsverfahren zu bestimmen, der aufweist: einen ersten N·1-DCT-Prozessor, der die eindimensionale Transformation der Eingangsdatenmatrix spaltenweise berechnet, um eine eindimensionale N·N-Zwischentransformations-Matrix zu erhalten, einen N·N-Transpositionsspeicher zum Speichern der Zwischentransformations-Matrix, und einen zweiten N·1-DCT-Prozessor, der die eindimensionale Transformierte der Transponierten der Zwischentransformations-Matrix berechnet, die in dem Transpositionsspeicher gespeichert ist, um die gewünschte zweidimensionale DCT zu erhalten; worin beide der N·1-DCT-Prozessoren aufweisen: ein N-stufiges Eingangsregister, an das eine Spalte der Eingangsdatenmatrix oder eine Reihe oder Spalte der gespeicherten Zwischentransformations-Matrix in einem bit-seriellen Format eingegeben wird, ein N-stufiges Halteregister, dessen Stufen mit den entsprechenden Stufen des Eingangsregisters verbunden sind, und eine Einrichtung zur Übertragung des Inhalts des Eingangsregisters in einem bit-parallelen Format an das Halteregister zu jeder Zeit, wenn das Eingangsregister sich füllt, eine Einrichtung, die mit dem Halteregister verbunden ist, um gleichzeitig N innere Vektorprodukte zu berechnen, wobei die Einrichtung Schaltungseinrichtungen aufweist, die mit dem Halteregister verbunden sind, um eine Dezimierung (Dezimation) der Frequenzen der ersten Stufe zu implementieren, um dadurch ein Paar von N/2-Bit- Wörtern von den N-Bit-Wörtern zu produzieren, die von dem Halteregister empfangen werden, N RACs, die mit der Schaltungseinrichtung verbunden sind, wobei jedes RAC einen oder mehrere Festwertspeicher (ROMs) und einen Akkumulator aufweist, und worin jedes der RACs durch das eine oder das andere der N/2-Bit- Wörter adressiert wird, ein N-stufiges Ausgangsregister, das jedes seiner Stufen mit dem entsprechenden Akkumulator von jedem entsprechenden RAC verbunden hat, und eine Einrichtung, um gleichzeitig die N berechneten inneren Vektorprodukte zu dem Ausgangsregister zu übertragen.
• Eine weitere Aufgabe der Erfindung ist: ein N·1 diskreter Cosinustransformations- Prozessor, der aufweist: ein N-stufiges Eingangsregister, dem eine Spalte oder Zeile der Eingangsdaten in einem bit-seriellen Format zugeführt werden kann, ein N-stufiges Halteregister, dessen Stufen mit den entsprechenden Stufen des Eingangsregisters verbunden sind, und eine Einrichtung zur Übertragung der Inhalte des Eingangsregisters in bit-parallelem Format immer dann zu dem Halteregister zu übertragen, wenn sich das Eingangsregister füllt, verteilte Arithmetikschaltungen, die mit dem Halteregister verbunden sind, um zeitlich zusammenfallend die N inneren Vektorprodukte zu berechnen, wobei die verteilten Arithmetikschaltungen erste Dezimationsstufen in Frequenzschaltungen aufweisen, die mit dem Ausgang des Halteregisters verbunden sind, die Dezimation in der Frequenzschaltung eine Einrichtung aufweist, um ein Paar von N/2-Bit-Wörtern von jedem N-Bit-Wort zu schaffen, das von dem Halteregister empfangen wird, die verteilte arithmetische Schaltung weiterhin N RACs aufweist, von denen jede einen oder mehrere Festwertspeicher (Read Only Memories ROMs) plus einen Akkumulator aufweist, wobei die RACs mit dem Ausgang der Dezimation in der Frequenzschaltung verbunden sind, und ein Ausgangsregister, von dem jedes seiner Stufen mit dem entsprechenden Akkumulator von jedem der RACs verbunden hat, das Ausgangsregister eine Einrichtung zum Empfang der inneren Vektorprodukte von den Akkumulatoren in bit-parallelem Format und eine Einrichtung, um die inneren Produkte in bitseriellem Format auszugeben, aufweist.
Kurze Beschreibung der Zeichnungen
• Fig. 1 zeigt die Verbindungen, die benötigt werden, wenn unsere Erfindung auf einem einzelnen Chip implementiert wird.
• Fig. 2 zeigt ein Gesamt-Blockschaubild einer Ausführungsform unserer Erfindung.
• Fig. 3 zeigt einen DCT-Prozessor, der eine verteilte Arithmetik oder andere Merkmale verwendet.
• Fig. 4 ist ein Blockschaubild eines RAC.
• Fig. 5 ist ein Blockschaubild eines DCT-Prozessors, der eine Dezimierung der Frequenz verwendet.
• Fig. 6 ist ein Schaubild eines RACs, das keine Partialsummen verwendet.
• Fig. 7 und 8 sind Schaubilder von RACs, die Partialsummen verwenden.
• Fig. 9 ist ein Gesamtschaubild der N·1 DCTs aus Fig. 2.
Detaillierte Beschreibung
• Die diskrete Cosinustransformation (DCT) ist eine orthogonale Transformation, die aus einem Satz von Basisvektoren besteht, die ausprobierte Cosinusfunktionen sind. Die DCT-Transformationsmatrix N-ter Ordnung C, ist definiert durch:
• mit k = 1, 2, 3, . . . N, l = 2, 3, . . . N und ck,l = N-½ für l = 1. Um eine Bandbreitenkomprimierung mittels der DCT zu erreichen, müssen die Blöcke der N·N-Videodaten in der Form vorzeichenloser binärkodierter Pixel einer zweidimensionalen Transformation unterworfen werden. Die zweidimensionale DCT N-ter Ordnung ist definiert als:
• Y = CtXC (2)
• Hierbei ist Y die transformierte Matrix, X sind die Daten oder die Video-Pixel-Matrix und Ct ist die Transponierte der diskreten Cosinusmatrix C, die durch Gleichung (1) definiert ist.
• Die Implementierung einer zweidimensionalen N·N-DCT kann durch ein Verfahren nach Stand der Technik, das als die Reihen-Spalten-Dekompositionstechnik bekannt ist, geschaffen werden; vergleiche dazu das Buch mit dem Titel "Multidimensional Digital Signal Processing", von Dudgeon und Mersereau in Prentice Hall Signal Processing Series, 1984. In dieser Technik nach Stand der Technik wird die zweidimensionale DCT durch zwei sequentielle eindimensionale DCTs geschaffen, wobei die Datenmatrix an die erste eindimensionale DCT zeilenweise angelegt wird. In unserer Erfindung wird eine Variante dieser Technik verwendet, wobei, wie oben angegeben, die Transponierte der Datenmatrix erhalten und an den ersten eindimensionalen DCT-Prozessor durch spaltenweises anstatt zeilenweises Lesen angelegt wird, so daß die Transponierte der Datenmatrix erhalten wird. Dies führt zu einer vereinfachten Schaltungsanordnung. Deshalb ist in der vorliegenden Erfindung der Ausgabewert des ersten eindimensionalen N·1- DCT-Prozessors XtC, der vorübergehend in dem Transpositionsspeicher gespeichert wird, und eine weitere N·1-DCT wird dann von der Transponierten der gespeicherten Matrix berechnet, um die erwünschte zweidimensionale DCT (Y) der Gleichung (2) zu erhalten. Wenn Geschwindigkeit nicht wichtig ist, können die zwei N·1-DCT-Berechnungen von der gleichen Schaltungsanordnung zeitlich verzahnt werden, aber in dem vorliegenden Fall, in dem Echtzeitoperation verlangt wird, werden zwei N·1-Prozessoren verwendet.
• Fig. 1 ist ein Schaubild, das unsere Erfindung auf einem einzelnen Chip implementiert darstellt. Die Anschlüsse an diesen Chip umfassen die Vorspannung Vcc, die Masse, einen Probetakt und ein Start-eines-Blocks-Aktivierungssignal. Die Eingangsdaten werden parallel über n&sub1; parallele Leitungen, eine für jedes Bit der Pixelworte, angelegt. Die transformierten Ausgangsdaten können n&sub3; parallele Leitungen für die längeren transformierten Worte umfassen. Die Eingangs- und Ausgangsdaten werden kontinuierlich mit der Probetakt-Rate in den und aus dem Chip geschoben.
• Fig. 2 zeigt den Gesamtaufbau unserer Erfindung, die den ersten oder N·1- Spalten-DCT 3 umfaßt, an den die Eingangsdaten auf n&sub1; parallelen Leitungen anliegen; die Ausgabedaten des DCT 3 werden temporär zeilen- oder spaltenweise in dem N·N Transpositionsspeicher 5 gespeichert, der wie gezeigt einen Direktzugriffsspeicher (RAM) mit separaten Eingangs- und Ausgangsanschlüssen umfaßt. Die n&sub2; parallelen Leitungen vom DCT 3 zum Speicher 5 umfassen abhängig von der benötigten Genauigkeit normalerweise mehr Bits, als die Eingangsdaten. Die gespeicherte Matrix wird (abhängig davon, wie die Zwischenmatrix gespeichert wurde) spalten- oder zeilenweise an den zweiten oder N·1-Zeilen-DCT 7 über n&sub2; parallele Leitungen angelegt. Die Transponierte der gespeicherten Matrix wird deshalb ausgelesen. Die transformierten Ausgangsdaten werden über n&sub3; parallele Leitungen vom zweiten N·1-DCT-Prozessor erhalten. Eine Zeitablauf- und Steuerschaltung 9 besitzt ein Taktsignal und das Start-eines-Blocks-Aktivierungssignal, das von der externen Schaltungsanordnung daran angelegt wird, und eine Schaltung 9 liefert mehrere Zeitablauf- und Steuersignale 11 und 12 an die Verarbeitungsschaltungsanordnung. Die Lese/Schreibe-Adreß- und Steuer-Schaltung 16 empfängt die Steuersignale 12 von der Schaltung 9 und legt über die Leitungen 14 geeignete Lese/Schreibe-Adressen und andere Steuersignale an den Speicher 5 an.
• Jeder der oben genannten inneren Vektorprodukte umfaßt eine Summation von N Produkten. Es kann mathematisch gezeigt werden, daß diese Berechnung ohne Multiplizierer unter Verwendung von Verweistabellen, die ROMs umfassen, realisiert werden kann, wobei die benötigten Koeffizienten der transformierten Matrizen durch Verschieben und Addieren der Verweistabellenwerte erhalten werden, die von den ROMs erhalten werden. Diese Rechentechnik, die auch nach Stand der Technik bekannt ist, ist als verteilte Arithmetik bekannt. Die ROMs und die Akkumulatoren, in denen die Verschiebungen und Additionen stattfinden, umfassen Einheiten, die RACs genannt werden, und jedes RAC speichert die Konstanten, die eine unterschiedliche Spalte der diskreten Cosinusmatrix darstellt.
• Die Fig. 3 und 4 zeigen einen N·1-DCT, der verdeutlicht, wie eine verteilte Arithmetik arbeitet und auch einige der Schaltungsmerkmale verdeutlicht, die in unserer Erfindung verwendet werden. Nach Fig. 3 umfaßt das Eingaberegister 13 N Stufen Q&sub1;-QN. Jede Spalte von Pixeln oder anderer zweidimensionalen Daten x1,k . . . XN,k, wird an die Stufe Q&sub1; des Registers 13 in bit-parallelem Format mit der Daten- oder Taktrate 1/T angelegt. Durch das spaltenweise Lesen der Pixeldatenmatrix wird deren Transformierte geschaffen. Digitale Videopixeldaten werden normalerweise in vorzeichenlose 8-Bit-Worte kodiert, wobei jedes die Helligkeit eines Pixels darstellt. Daher würden die Dateneingänge über 8 (oder n&sub1;) parallele Leitungen an Q&sub1; anliegen, und jede Registerstufe Q&sub1;-QN würde 8 (oder n&sub1;) parallele Bits umfassen. Nach N Taktzyklen würde die Spalte komplett in die N Stufen des Registers 13 geladen werden. Zu dieser Zeit würden die Steuersignale 11a und 11b von der Schaltung 9 in Fig. 2 alle 8 (oder n&sub1;) Bit-Worte von Q&sub1;-QN in die entsprechenden Stufen R&sub1;-RN des Halteregisters 15 übertragen. Die nächste Spalte der Eingangsdaten würde dann beginnen, das Eingaberegister vollzufüllen, während die restliche Schaltungsanordnung eine gleichzeitige Berechnung von N inneren Vektorprodukten durchführt, um die eindimensionale Transformation der Daten in dem Halteregister zu erhalten. Durch die Durchführung dieser gleichzeitigen Berechnung werden die Daten in dem Halteregister Bit für Bit mit dem niedrigstwertigen Bit zuerst als Reaktion auf das Steuersignal 11c herausgeschoben. Die N Leitungen von den N Stufen des Registers 15 bilden einen N-Bit-Bus, dessen Leitungen alle an N verschiedenen RACs (RAC(1)-RAC(N)) anliegen. Deshalb wird in jedem Taktzyklus ein unterschiedliches N-Bit-Wort dazu verwendet, gleichzeitig die ROMs zu adressieren, die ein Teil eines jeden RACs sind. Das RAC (1) hat in seinem ROM 2N Konstanten, die alle möglichen Kombinationen von Koeffizienten der ersten Spalte der Matrix C darstellen. Wenn zum Beispiel die ersten Spaltenkoeffizienten c1,1, c2,1, c3,1, . . . , CN,1 sind, dann würde das ROM all diese Koeffizienten und alle möglichen Summen von diesen einzeln speichern, zum Beispiel c1,1+c2,1, c1,1+c3,1, c1,1+CN1, c1,1+c2,1+c3,1, usw., bis zu und einschließlich der Summe all dieser Spaltenkoeffizienten. Zum Beispiel kann für N = 4 die Berechnung jedes Elements ykl der Spaltentransformation wie folgt dargestellt werden: c1,1 (110101001) + c&sub2;&sub1; (00101010) + c3,1 (11001111) + c4,1 (10101110). Dabei stellen die 8-Bit-Worte verschiedene Datenpixel dar, die eine Spalte von Daten bilden. In diesem Beispiel würden die niedrigstwertigen Bits aller Datenworte das Wort 1010 bilden. Dieses Wort würde aus dem ROM von RAC (1) den gespeicherten Wert c1,1+c3,1 auslesen, der, wie in Fig. 4 gezeigt, an das Schieberegister 25 des RACs (1) angelegt werden würde. Im nächsten Taktzyklus würde, abhängig davon, welches RAC adressiert wird und welches das N-Codewort ist, das nächst höchstwertige Codeelement aller Datenworte an alle RACs angelegt werden, um verschiedene Werte aus diesen auszulesen. Dieses ausgelesene Wort wird ebenfalls an das Schieberegister über die ADD/SUB-Schaltung 23 in Fig. 4 angelegt, wobei es zu den vorherigen Inhalten des Schieberegisters addiert wird, die zu der ADD/SUB- Schaltung mit einer 1-Bit-Rechtsverschiebung zurückgeleitet werden. Deshalb speichert nach der zweiten Adressierung des ROMs 21 das Schieberegister 25 darin die Summe der zwei ausgelesenen Worte, wobei das erste mit 1/2 gewichtet wird (oder durch 2 dividiert wird), um die Tatsache widerzuspiegeln, daß es ein Bit eines Datenworts geringerer Bedeutung darstellt. Dieses Verfahren wird für jedes Bit des Datenworts wiederholt. Die ADD/SUB-Schaltung 23 führt eine ADD (Addition) für die regulären Datenbits und eine SUB (Subtraktion) für das Vorzeichenbit aus. Die Schlußsummation aller solchermaßen von dem ROM abgefragten und gewichteten Worte gleicht einem Koeffizienten der Produktmatrix oder der eindimensionalen Transformation. Nachdem die erste Spalte der Eingangsdaten auf diese Weise erzeugt worden ist, nimmt zum Beispiel der Ausgabewert von RAC (1) den Wert y1,1 an, wenn die Elemente der Produktmatrix XtC yk,l sind, und ebenso nimmt der Ausgang von RAC (N) den Wert y1,N an. Deshalb wird die gesamte erste Reihe der Produktmatrix XtC an den RAC-Ausgängen nach Beendigung dieser Berechnung verfügbar sein. Entsprechend dem Steuersignal 11d von der Schaltung 9, werden dann die angesammelten Inhalte yk,l-yk,N jedes RACs gleichzeitig parallel über n&sub2; (oder n&sub3;) parallele Leitungen in die Stufen U&sub1;-UN des Ausgaberegisters 19 geladen, der ähnlich dem Eingaberegister mit einem zusätzlichen Multiplexer mit zwei Eingängen ist. Die Inhalte des Registers 19 würden dann entsprechend dem Steuersignal 11e nacheinander aus dessen Stufe U&sub1; auf n&sub2; (oder n&sub3;) parallelen Leitungen zum Transpositionsspeicher oder zum zweidimensionalen Prozessorausgang herausgeschoben. Wenn N = 16 ist, würden zum Beispiel 16 Taktzyklen benötigt werden, um das Eingaberegister 13 mit einer Spalte von Daten zu füllen; deshalb würde alle 16 Zyklen die Steuerschaltung 9 so gesteuert werden, damit sie das Signal 11b ausgibt, um die Übertragung der Spalte von Daten an das Halteregister 15 zu bewirken. Das Register 19 kann seine Inhalte yk,l seriell herausschieben, während die RACs die nächste Zeile der Produktmatrix berechnen und die Eingaberegister Eingabedaten sammeln. Wie in Fig. 4 gezeigt, wird der Ausgabewert des ROMs 21 eine Wortlänge von n&sub4;-Bits besitzen, die durch die Länge der in dem ROM gespeicherten Worte festgelegt ist. Das Signal 11f, das von der Schaltung 9 an der Schaltung 23 angelegt wird, legt fest, ob diese Schaltung eine Addition oder Subtraktion ausführt. Die Steuersignale 11g und 11h, die an das Schieberegister 25 angelegt werden, sind rückgesetzte und parallel geladene Signale.
• Die Schaltungsanordnung beider eindimensionaler DCT-Prozessoren sind gleich, mit Ausnahme der Zahl der Bits pro Wort. Wie in Fig. 2 gezeigt, hat der erste Prozessor eine Eingabewortlänge n&sub1; und eine Ausgabewortlänge von n&sub2;. Der zweite DCT-Prozessor 7 hat Eingabe- und Ausgabewortlängen von n&sub2; bzw. n&sub3;.
• Obwohl die Schaltungsanordnung in Fig. 3 und 4 keine Multiplizierer benötigt, weist sie schwere Einschränkungen aufgrund der Zahl der Konstanten, die in jedem ihrer ROMs gespeichert werden müssen, auf. Wenn zum Beispiel N = 16 ist, ist die Zahl der Worte, die für jedes ROM jedes RACs benötigt wird, 2¹&sup6; oder 65.536. ROMs dieser Größe sind mit der derzeitigen VLSI-Technologie nicht machbar, wenn der gesamte Prozessor auf einem einzelnen Chip implementiert ist. Zwei Methoden sind übernommen worden, um die ROM-Größe zu reduzieren, wobei beide nur eine bescheidene zusätzliche Schaltungsanordnung benötigen. Die erste Methode ist eine Variante der Technik der Dezimierung der Frequenz, die nach Stand der Technik in herkömmlichen schnellen Fourier-Transformationens (FFT)-Algorithmen verwendet worden ist. Das (k,l)-te Element der Produktmatrix Y = XtC ist durch folgende Gleichung gegeben:
• Hierbei ist k der k-te Spaltenvektor von X und l der l-te Spaltenvektor von C. Unter Bezugnahme auf die N·N-DCT-Transformationsmatrix C, die in Gleichung (1) definiert ist, kann gezeigt werden, daß für geradzahlige N, ck,l + cN+1-k,l für l = 1, 3, . . . N-1 und ck,l = -cN+1-k,l für l = 2, 4, . . . N. Mit diesen Beziehungen wird Gleichung (3):
• für l = 1, 3 . . . N-1, wobei Uk,m = xm,k+xN-m+1,1,k, und
• für l = 2, 4 . . . N, mit vk,m = xm,k-xN-m+1,k. Die Gleichungen (4) und (5) lassen darauf schließen, daß, wenn die Variablen u und v die ursprüngliche Datenfolge ersetzen, die Summation von 1 bis N zur Summation von 1 bis N/2 wird. Deshalb wird die Zahl der Datenbits, die benötigt werden, um jedes ROM zu adressieren, um einen Faktor 2, und die Zahl der benötigten gespeicherten Worte um einen Faktor 2N/2 reduziert. Prinzipiell kann diese Technik der Dezimierung der Frequenz auf mehr Stufen ausgeweitet werden, so wie es die meisten FFT Algorithmen tun. Jedoch könnten die Ersparnisse wegen der zunehmenden darin verwickelten Unregelmäßigkeiten, nicht lohnend sein. Um die modulare Struktur zu erhalten, wurde deshalb nur die erststufige Dezimierung angewendet. Dieses Merkmal der Erfindung ist in Fig. 5 dargestellt.
• In Fig. 5 sind N/2 serielle Addierer 31 vorgesehen, um die Variablen u aus N/2 verschiedenen Paaren der ursprünglichen Datensequenzen von dem Register 15 zu erzeugen. Wie gezeigt, wird die Variable uk,1 durch Addition von x1,k und xN,k gebildet, uk,2 aus x2,k plus xN-1,k, und uk,N/2 aus xN/2,k plus xN/2+1,k. Die gleichen Paare von EingabedateneIementen werden in N/2 seriellen Ein-Bit-Subtrahierern 33 voneinander abgezogen, um die neuen Variablen vk,l, vk,2 . . . vk,N/2 zu erhalten. Deshalb umfassen die Paare von Datenelementen jeder Eingabedaten-Spalte die Elemente von der ersten und letzten Zeile der Spalten, die Elemente von der zweiten und der vorletzten Zeile der Spalten, die Elemente von der dritten und drittletzten Zeile der Spalten, usw. Die Eingabedatenbits xk,l in Fig. 5 würden Bit für Bit (in bit-seriellem Format) von einem Halteregister wie in Fig. 3 erhalten werden und die Ausgabedaten der seriellen Addierer und Subtrahierer 31 und 33 würden Bit für Bit erscheinen, um zwei N/2-Leitungs-Busse zu bilden, wobei jeder Bus die Eingabedaten zweier verschiedener Gruppen von N/2-RACs bildet. Der N/2-Leitungs- Bus 34, der mit den Addierern 31 verbunden ist, besitzt die ungeradzahligen RACs, 1, 3, N-1, die damit verbunden sind, und diese RACs berechnen alle Elemente der inneren Vektorprodukte der ungeradzahligen Spalten, z. B., yk,1, yk,3, yk,N-1. Der N/2-Leitungs-Bus 36, der mit den Subtrahierschaltungen 33 verbunden ist, besitzt die damit verbundenen geradzahligen RACs 2, 4, N, die die Elemente der geradzahligen Spalten der inneren Vektorprodukte berechnen.
• Die Benutzung einer erststufigen Dezimierungs-Schaltung wie in Fig. 5, wird die Größe eines jeden ROMs auf 256 Worte für eine 16·16-Matrix reduzieren, da jedes RAC nun durch ein 8-Bit-Wort adressiert wird.
• Die Erfindung verwendet eine zusätzliche Technik, um die ROM-Größe weiter zu reduzieren. Diese zusätzliche Technik basiert auf der Beobachtung, daß die Summationen über den Index die Zahl der Datenpunkte in den Gleichungen (4) und (5), in Partialsummen aufgespaltet werden können. Wenn wir gewählt haben, (3) in zwei Partialsummen zu zerlegen, dann wird
• ist.
• Beachte, daß die Summation in F&sub1; und F&sub2; nur N/2 Eingabeproben anstelle von N Proben umfaßt. Durch die derartige Zerlegung wird jedes ROM mit 2N Worten durch zwei kleinere ROMs mit 2N/2 Worten ersetzt. Genauer gesagt, werden die Datenworte am Eingang jedes RACs in zwei Gruppen zerlegt, wobei die erste Gruppe aus den Bits von 1 bis N/2 und die zweite Gruppe aus den Bits von den Datennummern (N/2)+1 bis N besteht. Deshalb werden die Worte, die normalerweise benutzt werden, um das RAC zu adressieren, in zwei gleiche Teile zerlegt, die die erste und zweite Hälfte davon umfassen. Jedes der kleineren Worte wird dazu benutzt, einzelne ROMs zu adressieren, und die ROM-Ausgabedaten werden parallel addiert und die Summe an den Akkumulator angelegt. Die Zahl der Partialsummen, die diese Zerlegungstechnik benutzen, kann jede geradzahlige Zahl sein. Für N = 16 wird jedes ROM durch zwei kleinere ROMs ersetzt. Wenn N = 32, kann jedes ROM durch vier ROMs ersetzt werden, wobei in diesem Fall eine zusätzliche Additionsstufe benötigt wird. Für N = 8 wird keine Zerlegung benötigt, da die ROM- Größe schon sehr klein ist.
• Die Implementierung der RACs, die sowohl die Partialsummentechnik als auch die Technik der erststufigen Dezimierung der Frequenz nutzt, ist in den Fig. 6, 7 und 8 für 8·1, 16·1 bzw. 36·1 DCTs gezeigt. Das RAC in Fig. 6 für einen 8·1- DCT mit einem Merkmal der erststufigen Dezimierung der Frequenz, wie das in Figur 5, würde zwei Vier-Codeelement-Busse umfassen, die die ROMs adressieren. Jedes ROM 37 speichert nur 2&sup4; oder 16 Worte und deshalb werden keine Partialsummen benötigt, wobei die Ausgangsdaten des ROMs 37 durch die ADD/SUB- Schaltung 39 und das Schieberegister 11 an den Ausgang 43 angelegt ist. Das 16·1-DCT-RAC in Fig. 7 würde als ein Ergebnis des Dezimierungsmerkmals zwei 8-Bit-Busse besitzen, die, wie oben erklärt, in zwei 4-Bit-Worte zerlegt werden würden, die an zwei gleiche 16-Wort-ROMs 45 und 47 angelegt werden. Der Addierer 49 würde die aus den zwei ROMs ausgelesenen n&sub4;-Bit-Worte aufsummieren, um ein einzelnes n&sub4;+1-Bit-Wort zu erhalten, das an den Akkumulator angelegt wird, der die ADD/SUB-Schaltung 51 umfaßt, wobei das Schieberegister 53 und der 1-Bit-Rechtsverschiebungsrückleitungsweg zwischen dem Ausgang des Schieberegisters und dem Addierer-Subtrahierer 51 ist. Die RAC-Ausgabedaten an 55 würden Worte mit n&sub2; (oder n&sub3;) Bits umfassen, die ein wenig länger wären als n&sub4;&sbplus;&sub1; Bits.
• Das 32·1-DCT-RAC in Fig. 8 umfaßt einen 16-Bit-Leitungs-Eingangsbus, der in vier 4-Bit-Worte zerlegt ist, um vier ähnliche ROMs 61, 63, 65 und 67 zu adressieren, wobei jedes davon 16 Worte speichert. Die n&sub4;-Bit-Worte am Ausgang der ROMs 61 und 63 werden im Addierer 69 addiert, und die ähnlichen Worte von den ROMs 65 und 67 werden an den Addierer 71 angelegt. Diese zwei Addierer haben ihre Ausgabedaten der Reihe nach an den Addierer 73 angelegt, der seine Ausgabedaten an den Akkumulator angelegt hat, der genauso funktioniert, wie der vorher beschriebene, um ein Element eines inneren Vektorprodukts zu berechnen.
• Durch Kombination dieser zwei Techniken kann die benötigte ROM-Größe mit nur einer bescheidenen Vergrößerung der Schaltungsanordnung außerordentlich reduziert werden. Zum Beispiel für N = 16 benötigt die direkte Implementierung eines zweidimensionalen 16·16-DCTs 2¹&sup6;·16·2 = 2²¹ Worte des ROMs. Auf der anderen Seite benötigt die Schaltung in Fig. 7 bei Benutzung der zwei Techniken, die oben beschrieben sind, nur 2&sup4;·2·16·2 = 2¹&sup0;, also näherungsweise 1K Worte des ROMs. Mit dieser ROM-Größe ist die neuartige Schaltungsanordnung der vorliegenden Erfindung nicht nur machbar, sondern sehr effizient, was IC-Realisierung betrifft.
• Fig. 9 ist ein Gesamt-Blockschaubild des N·1-DCTs mit dem Merkmal der Dezimierung der Frequenz. Das Schaubild in Fig. 9 hebt die Regelmäßigkeit und die Modularität dieser Schaltungsentwicklung hervor. In dieser Figur umfaßt das Eingaberegister N Stufen Q&sub1;-QN, wobei jede n&sub1; (oder n&sub2;) Bits umfaßt, abhängig davon, ob die Schaltung den ersten oder zweiten N·1-DCT-Prozessor in Fig. 2 umfaßt, wobei die Eingangsspalten der Daten x1,k, x2,k . . . xN,k an Q&sub1; über n&sub1; (oder n&sub2;) parallelen Leitungen anliegen. N/2 serielle Addierer 81 und eine ähnliche Zahl von seriellen Subtrahierern 83 sind vorgesehen und jeder besitzt ein Paar einzelner Leitungen von den Stufen R&sub1;-RN des Halteregisters, das damit verbunden ist. Der N/2-Bit-Bus 85 umfaßt Bits, die aus den Addierern 81 gewonnen werden, und der N/2-Bit-Bus 87 umfaßt Bits vom Subtrahierer 83. Beachte, daß der Addierer und der Subtrahierer, die die ersten Bits uk,l und vk,l beider N/2-Bit-Busse erzeugen, beide mit der ersten und letzten Halteregisterstufe R&sub1; und RN verbunden sind. Ebenso sind der Addierer und der Subtrahierer, die das zweite Bit eines jeden Worts auf den zwei Bussen erzeugen, mit der zweiten und der vorletzten Halteregisterstufe R&sub2; und RN-1 verbunden, usw. Indem man dieser logischen Regel folgt, wird das letzte Bit auf jedem Bus aus dem Addierer und Subtrahierer ausgelesen, die mit den Halteregisterstufen N/2 und (N/2)+1 verbunden sind. Die N RACs in Fig. 9 sind in numerischer Ordnung angeordnet, wobei die ungeradzahligen mit dem Bus 85 verbunden sind, der mit allen Addierern 81 verbunden ist, und alle geradzahligen RACs sind mit allen Subtrahierern 83 über den Bus 87 verbunden. Die Spaltentransformationskoeffizienten yk,1, yk,2, . . . yk,N werden gleichzeitig von den RAC- Ausgängen bit-parallel zu den Stufen U&sub1;-UN des Ausgaberegisters verschoben, so wie in der vorherigen Ausführungsform, und die Inhalte dieser Registers werden dann nacheinander herausgeschoben.
• Die Bereitstellung von Eingabe-, Ausgabe- und Halteregistern als Teil der N·1- DCT-Prozessoren minimiert die Zahl der Chip- (oder IC-) Eingabe/Ausgabe-Pins und vereinfacht die Leitwegführung, da jedes Register-Array nur mit seinen Nachbarn kommuniziert. Auch erleichtert diese Schaltungsanordnung einen gleichzeitigen Betrieb, in dem fast alle Schaltungen gleichzeitig verschiedene Aufgaben während des Betriebs ausführen. Dies ist erforderlich, wenn Echtzeitverarbeitung auf einem einzelnen Chip erreicht werden soll. Weiterhin reduziert die Benutzung einer bit-seriellen Struktur zur Implementierung der erststufigen Dezimierung der Frequenz die benötigte Schaltungsanordnung und vereinfacht die Leitwegführung.
• Durch eine geeignete Steuerung der Lese- und Schreib-Adressen des Transpositonsspeichers werden nur N·N Worte des RAMs sowohl zum Speichern der Zwischenergebnisse (oder Matrix) als auch zum Ausführen in der Matrix-Transposition benötigt, die beim Auslesen der gespeicherten Zwischenergebnisse benötigt wird. Der Transpositionsspeicher (oder RAM) umfaßt 16·16 Worte, wenn N = 16 ist, und besitzt einzelne Lese- und Schreibeanschlüsse, wie in Fig. 2 gezeigt. Da die Zwischenergebnisse des gegenwärtigen Blocks kontinuierlich von dem ersten N·1- Prozessor in den Speicher geschrieben werden, während die Zwischenergebnisse des vorherigen Blocks kontinuierlich in den zweiten N·1-Prozessor ausgelesen werden, muß die Lese/Schreibeoperation so durchgeführt werden, daß keine Information zerstört wird, bevor sie ausgelesen wird. Ein Weg um das zu erreichen, ist, die Lese/Schreibe-Steuerung und die Adressen so auszubilden, daß jede Probe (oder Wort) in die gleiche Speicherstelle geschrieben wird, aus der die Probe des vorherigen Blocks ausgelesen worden ist. Auf diese Weise benötigt jede Lese- und Schreiboperation einen halben Taktzyklus (T/2). Ein anderer Weg ist, sie so anzuordnen, daß die Schreibadresse hinter der Leseadresse um eine Zeile oder eine Spalte zurück bleibt. Auf diese Weise kann jede Lese- und Schreibeoperation einen vollen Zyklus (T) durchfahren, wobei jedoch zwei Sätze von Adreßdecodern benutzt werden müssen.
• Um die erwünschte Matrixtransposition zu erreichen, werden die Daten aus dem Speicher 5 spaltenweise ausgelesen, falls der vorherige Block in das RAM zeilenweise geschrieben worden ist, und umgekehrt. Wenn zum Beispiel für N = 16 die Daten des vorherigen Blocks in das RAM in der Folge 0, 1, 2, 3, . . . usw. geschrieben werden, werden die Daten dann in der Folge 0, 16, 32, 48, . . . usw. ausgelesen und zur gleichen Zeit die Daten des vorliegenden Blocks in der gleichen Folge (0, 16, 32, 48, usw.) in das RAM geschrieben. Im nächsten Block lesen/schreiben die Daten wieder in der Folge 0, 1, 23, . . . usw. und die Operation wiederholt sich. Die Adressen können durch einen 8-Bit-Zähler erzeugt werden, und die Änderung der Sequenz kann leicht durch Abänderung der 4 höchstwertigen Bits und der 4 niedrigstwertigen erreicht werden. Diese Schaltungsanordnung wäre ein Teil der Schaltung 16 in Fig. 2. Das Starten-eines-Blocks-Aktivierungssignal wird dazu verwendet, die Adresse der Lese/Schreibeoperation zurückzusetzen. Beachte, daß der Zähler, der für die derartige Steuerung der RAM-Adresse benötigt wird, so aufgebaut werden kann, daß er einen Addierer und ein Register benutzt, wobei das Steuerungssignal durch ein ROM erzeugt wird.
• In diesem zweidimensionalen Prozessor ist n&sub1; = 8 für die meisten Anwendungen. Die Wortlängen für n&sub2;, n&sub3; und n&sub4; werden durch Computersimulation der Schaltung festgelegt, in der viele Bilder digitalisiert und deren Pixel entsprechend der vorliegenden Schaltungsanordnung transformiert werden und die inverse Transformation dann ausgeführt und die Bilder reproduziert werden. Man hat herausgefunden, daß mit n&sub2; = 12, n&sub3; = 16 und n&sub4; = 9 eine sehr hohe Genauigkeit erreicht wird. Für manche Anwendungen wie zum Beispiel Video mit einer geringen Bit-Rate, wobei solch hohe Genauigkeit nicht benötigt wird, kann die Zahl der Bits für n&sub2;, n&sub3; und n&sub4; um 1 oder 2 reduziert werden.

Claims (6)

1. Zweidimensionaler diskreter Cosinustransformations (DCT)-Prozessor, der ein Paar von eindimensionalen DCT-Prozessoren benutzt, um die zweidimensionale DCT einer N·N-Matrix von Eingangsdaten durch ein Reihen-Spalten-Dekompositionsverfahren zu bestimmen, der aufweist:

einen ersten N·1 DCT-Prozessor (3) der die eindimensionale Transformation der Eingangsdatenmatrix spaltenweise berechnet, um eine eindimensionale N·N-Zwischentransformations- Matrix zu erhalten,

einen N·N-Transpositionsspeicher (5) zum Speichern der Zwischentransformations-Matrix, und

einen zweiten N·1-DCT-Prozessor (7), der die eindimensionale Transformierte der Transponierten der Zwischentransformations-Matrix berechnet, die in dem Transpositionsspeicher gespeichert ist, um die gewünschte zweidimensionale DCT zu erhalten;

worin beide der N·i-DCT-Prozessoren aufweisen:

ein N-stufiges Eingangsregister (13), an das eine Spalte, der Eingangsdatenmatrix oder eine Reihe oder Spalte der gespeicherten Zwischentransformationsmatrix in einem bit-seriellen Format eingegeben wird,

ein N-stufiges Halteregister (15), dessen Stufen mit den entsprechenden Stufen des Eingangsregisters verbunden sind, und eine Einrichtung zur Übertragung des Inhalts des Eingangsregisters in einem bit-parallelen Format an das Halteregister zu jeder Zeit, wenn das Eingangsregister sich füllt,

eine Einrichtung, die mit dem Halteregister verbunden ist, um gleichzeitig N innere Vektorprodukte zu berechnen, wobei die Einrichtung Schaltungseinrichtungen (31, 33, 34, 36) aufweist, die mit dem Halteregister verbunden sind, um eine Dezimation erster Stufe der Frequenz zu implementieren, um dadurch ein Paar von N/2-Bitwörtern von den N-Bitwörtern zu produzieren, die von dem Halteregister empfangen werden,

N RACs (17), die mit der Schalteinrichtung verbunden sind, wobei jedes RAC eines oder mehrere Read Only Memories ROMs (37) und einen Akkumulator (39, 41) aufweist, und worin jedes der RACs durch das eine oder das andere der N/2-Bitwörter adressiert wird,

ein N-stufiges Ausgangsregister (19) das jedes seiner Stufen mit dem entsprechenden Akkumulator von jedem entsprechenden RAC verbunden hat, und

eine Einrichtung, um gleichzeitig die N berechneten inneren Vektorprodukte zu dem Ausgangsregister zu übertragen.

2. Zweidimensionaler DCT-Prozessor nach Anspruch 1, worin die RACs mit einer Teilsummeneinrichtung ausgerüstet sind, worin jedes der RACs zwei oder mehrere ROMs (45, 47) umfaßt, von denen jedes durch einen verschiedenen Abschnitt von einem oder dem anderen der N/2-Bitwörter adressiert wird, die von der Schaltungseinrichtung erhalten werden, jedes der RACs weiterhin eine Einrichtung (49) zum Addieren der von den zwei oder mehreren ROMs wiedergewonnen Wörter und eine Einrichtung aufweist, um die resultierenden addierten Wörter an den mit den RACs verbundenen Akkumulator anzulegen.

3. Prozessor nach Anspruch 1, in dem N 16 ist, und in dem die Matrix der Eingangsdaten in 8-bit-binären Wörtern codierte Video-Pixeln enthält, und in dem die Schaltung auf einem einzigen Chip implementiert ist.

4. Zweidimensionaler DCT-Prozessor nach Anspruch 1, worin der Transpositionsspeicher ein N·N Random Access Memory (RAM) Array mit getrennten Lese- und Schreibeanschlüssen und eine damit verbundene Lese-/Schreibekontrollschaltung (16) enthält, und worin der Ausgang des ersten DCT-Prozessors in einer abwechselnden Weise Zeilen- und Spaltenweise gelesen wird und der Eingang des zweiten DTC-Prozessors in einer abwechselnden Weise aus dem Speicher Zeilen- und Spaltenweise durch die Kontrollschaltung derart gelesen wird, daß die Transposition der gespeicherten Matrix zur Anwendung an den zweiten N·1-DCT-Prozessor erzielt wird.

5. N·1 diskrete Cosinustransformation Prozessor, der aufweist:

ein N-stufiges Eingangsregister (13), dem eine Spalte oder Zeile der Eingangsdaten in einem bit-seriellen Format zugeführt werden kann,

ein N-stufiges Halteregister (15), dessen Stufen mit den entsprechenden Stufen des Eingangsregisters verbunden sind, und eine Einrichtung zur Übertragung der Inhalte des Eingangsregisters in bit-parallelem Format immer dann zu dem Halteregister zu übertragen, wenn sich das Eingangsregister füllt,

verteilte Arithmetikschaltungen (31, 33, 34, 36), die mit dem Halteregister verbunden sind, um zeitlich zusammenfallend die N-inneren Vektorprodukte zu berechnen, wobei die verteilen Arithmetikschaltungen erste Dezimationsstufen in Frequenzschaltungen aufweisen, die mit dem Ausgang des Halteregisters verbunden sind, die Decimation in der Frequenzschaltung eine Einrichtung aufweist, um ein Paar von N/2-3itwörtern von jedem N-Bitwort zu schaffen, das von dem Halteregister empfangen wird,

die verteilte arithmetische Schaltung weiterhin N RACs (17) aufweist, von denen jede eines mehrere Read Only Speicher ROMs (37) plus einen Akkumulator (39, 41) aufweisen, wobei die RACs mit dem Ausgang der Dezimation in der Frequenzschaltung verbunden sind, und

ein Ausgangsregister (19), von dem jedes seiner Stufen mit dem entsprechenden Akkumulator von jedem der RACs verbunden hat, das Ausgangsregister eine Einrichtung zum Empfang der inneren Vektorprodukte von den Akkumulatoren in bit-parallelem Format und eine Einrichtung, um die inneren Produkte in bit-seriellem Format auszugeben, aufweist.

6. DCT-Prozessor nach Anspruch 5, worin jeder der RACs mit einer Partialsummeneinrichtung versehen ist, worin jeder RAC zwei oder mehrere ROMs (45, 47) aufweist, von denen jedes durch einen verschiedenen Teil des einen oder des anderen der N/2-Bitwörter adressiert wird, die von der Dezimation des Frequenzschaltkreises empfangen werdend jedes RAC weiterhin eine Einrichtung (49) zur Addition der Wörter, die von den zwei oder mehreren ROMs durch die verschiedenen Anteile der N/2-Bitwörter wiedergewonnen werden, und eine Einrichtung aufweist, um die resultierenden addierten Wörter an dem zu dem RAC zugeordneten Akkumulator anzulegen.