DE3875979T2

DE3875979T2 - Schaltung zur berechnung des quantisierten koeffizienten der diskreten cosinustransformation von digitalen signalabschnitten.

Info

Publication number: DE3875979T2
Application number: DE8888100692T
Authority: DE
Inventors: Benedetto Riolfo
Original assignee: CSELT Centro Studi e Laboratori Telecomunicazioni SpA
Current assignee: Telecom Italia SpA
Priority date: 1987-01-20
Filing date: 1988-01-19
Publication date: 1993-04-29
Anticipated expiration: 2008-01-20
Also published as: IT8767032A0; EP0275979B1; DE3875979D1; CA1281425C; EP0275979A2; EP0275979A3; JPS63182773A; US4849922A; IT1207346B; JPH0622033B2

Description

Die hier beschriebene Erfindung bezieht sich auf das Gebiet der digitalen Signalcodierung. Speziell besteht sie aus einer Schaltung zum Berechnen der quantisierten Koeffizienten der diskreten Cosinustransformation von digitalen Signalabtastungen, und noch spezieller auf Abtastwertvektoren, bei welchen die diskrete Cosinustransformation noch passender funktioniert. Die Abtastwertvektoren sind eindimensionale Felder, bestehend aus den Abtastwerten von N Pixeln. Sie werden durch die getrennte Abtastung der Leuchtdichte- und der Farbartintensitäten von N Pixeln eines Videoeinzelbildes und deren Anordnen in einer vorgegebenen Reihenfolge, die ihre Positionen in dem Einzelbild berücksichtigt, gebildet.
Auf Blöcke von ein-, zwei- und dreidimensionalen digitalen Signalabtastwerten angewandtes digitales Transformationscodieren wird weit verbreitet in allen Anwendungen benutzt, zum Beispiel in der Videosignalverarbeitung, welche eine spektrale Analyse erfordert, in der Datenkompression und bei der Reduktion der ursprünglichen Signalbandbreite.
Die verschiedenen Arten des Transformationscodierens sind bekannt. Sie beinhalten die Hadamard- oder HCT-(Hochkorrelationstransformation) -Arten, welche auf extrem einfachen Koeffizienten basieren, und die Fouriertransformation, welche komplizierte Gleitkomma-Berechnungen erfordert. Wiederum andere Arten beinhalten die K.L.- oder Slant-Transformationen, welche die optimale Frequenzspektrumsenergieverteilung betreffen.
Zur Zeit jedoch stellt die diskrete Cosinustransformation, ab hier als DCT-Transformation bezeichnet, bei vielen Anwendungen einschließlich der Videosignalverarbeitung, den besten Kompromiß zwischen der effektiven Wiedergabe im Transformationssignalfrequenzspektrum und der Einfachheit der Konstruktion dar.
Im Falle einer eindimensionalen DCT-Transformation auf N N- Basis besteht der wichtigste Vorteil in seiner Rekursion der N reellen Koeffizienten.
Es werden eine Anzahl von DCT-Transformations-Berechnungsalgorithmen benutzt; einige sind auf ihre direkte Herleitung von der Fourier-Transformation gegründet, während andere die Koeffizientenrekursion ausnutzen. Diese Algorithmen dienen alle dem Verringern der Anzahl der Multiplikationen, im Vergleich zur Gesamtzahl von Operationen, die ausgeführt werden müssen (Addition, Akkumulation, Adressieren, Normalisieren, Rundungs- und Abschneide-Operationen); dies macht sie besonders für Software-Anwendungen geeignet, deren wichtigstes Ziel das Verringern der Anzahl von Mikrobefehlszyklen ist.
Von den verschiedenen bekannten eindimensionalen DCT- Transformations-Berechnungsalgorithmen mit N N-Basis ist der Fralick-Chen-Algorithmus der, der die größte Reduktion in der Anzahl der Multiplikationen liefert. Dieser Algorithmus wird in der Schrift "A fast computational algorithm for the discrete cosine transform", W. Chen, C.H. Smith, S.C. Fralick, IEEE Transactions on Communications, Band COM. 25, Nr. 9, September 1977, beschrieben und erfordert eine Anzahl von Operationen gleich:
3N/2(log N-1)+2 Additionen und
N log N-3N/2+4 Multiplikationen.
Andererseits wäre es für die zweidimensionale DCT-Transformation mit N N-Basis möglich, die verteilte Eigenschaft auszunutzen und den Algorithmus für den eindimensionalen Fall, wie etwa den Fralick-Chen Algorithmus, in den beiden orthogonalen Richtungen anzuwenden; auf diesem Wege wäre die Anzahl der auszuführenden Operationen 2N-mal der für den eindimensionalen Fall erforderlichen Anzahl.
Jedoch gibt es einen 2-D-Transformations-Berechnungsalgorithmus, welcher eine weitere Verringerung der Anzahl der Operationen bewirkt. Dieser Algorithmus wird in einer Schrift von M. Vetterli, "Fast 2-D discrete cosine transform", IEEE ICASSP-1985, beschrieben und erfordert folgende Menge an Operationen:
(N N/2) log N+N/3-2N+8/3 Additionen und
(N N 5/2) 10g N+N N/3-6N+62/3 Multiplikationen.
Normalerweise geht jedoch die durch diesen Algorithmus gelieferte drastische Reduktion mit der Anzahl der Operationen von einer entsprechenden Kompliziertheit im Handhaben und Neuordnen der Zwischenergebnisdaten Hand in Hand, was schwerwiegende Speicheradressierungsprobleme beim Entwerfen der Berechnungsschaltungen für diese Algorithmen erzeugt. Außerdem macht die ungleiche Verteilung der Berechnungselemente in diesen Schaltungen, wie Addierer und Multiplizierer, welche unterschiedliche Laufzeiten haben, diese Komponenten ineffizient sowohl wenn man die Reduktion der gesamten Berechnungszeit betrachtet, als auch in Bezug auf die Ausnutzung der Rechenresourcen.
Ungeachtet dessen, ob die Schaltungen für diese Algorithmen für diskrete oder integrierte Komponenten entworfen sind, ist das Hauptproblem stets der Teil der Schaltung, der den Multiplikationsoperationen gewidmet ist.
Dies ist bedingt durch die Schaltungskomplexität, die benötigte Berechnunszeit, die Raumeinnahme und den Leistungsbedarf.
Die bekannteste Anwendung einer N N-Bit-Multiplikationsoperation umfaßt das Konvertieren dieser Operation in eine Reihe von N elementaren N-Bit-Aditions- und Schiebeoperationen. Diese Lösung wurde in Paralleltypmultiplizierern benutzt, mit verschiedenen Schaltungsoptimierungen.
Diese Lösung würde nicht als die effizienteste für die DCT- Transformation erscheinen, gerade wenn eine begrenzte Anzahl von Koeffizienten genutzt werden muß, vorausgesetzt, daß die Anzahl der elementaren Operationen, die ausgeführt werden, hoch ist.
Es könnte ein Versuch gemacht werden, die Multipliziererstrukturen zu vereinfachen durch Benutzen von Konvertierungstabellen, die die ROM- oder PROM-Speicher oder programmierte logische Arrays (PLA), welche die Ergebnisse der Multiplikationen enthalten, direkt durch die Operanden adressieren.
In unserem Fall jedoch können solche Strukturen nicht benutzt werden, da die große Anzahl von Multiplikationskoeffizienten und von Operandenrepräsentationsbits eine unangemessen hohe Speicherkapazität erfordern würden.
Die hier beschriebene DCT-Transformations-Berechnungsschaltung löst diese Probleme, da sie keine Multiplikationsberechnung erfordert oder Multiplizierer benutzt.
Gleichzeitig ermöglicht sie es, platzbedarf, Berechnungszeit und Leistungsbedarf zu reduzieren.
Durch Auswählen einer geeigneten Anordnung der Transformationsmatrix-Koeffizienten, und somit der auszuführenden Operationen, und aufgrund der Art der zur Wiedergabe der Koeffizienten angenommenen Genauigkeit (Anzahl der Bits) wird jede Multiplikation mit Hilfe von Additions- und Schiebeoperationen ausgeführt, welche die am Eingang transformierten Abtastwerte und/oder die Ergebnisse der vorherigen Multiplikationen umfassen. Auf diesem Wege wird die ganze Transformationsoperation im Falle von N=16 durch die Berechnung von 2NN(N-1) gleichen Additionen ausgeführt, oder im Falle von N=8 von N N(2N+1) gleichen Additionen. Obwohl dadurch die Anzahl der auszuführenden Operationen drastisch reduziert ist, wird das Wiederanordnen der zu speichernden verschiedenen Zwischenergebnisse nicht komplizierter und das Erzeugen der Speicheradressierungseinheiten bleibt auch einfach. Diese Schaltungslösung fördert Entwicklungen, die VLSI-Schaltungen benutzen.
Weiterhin kann die gleiche Schaltung dazu benutzt werden, die DCT-Transformation einer beliebigen Anzahl von Dimensionen zu berechnen.
Ein spezieller Gegenstand der Erfindung ist die in Anspruch 1 beschriebene Schaltung zum Berechnen der eindimensionalen DCT- Transformation; diese Schaltung kann als Grundeinheit zum Entwikkeln N-dimensionaler DCT-Transformations-Berechnungsschaltungen benutzt werden.
Die Merkmale der Erfindung werden durch die folgende Beschreibung einer Ausführungsform und verschiedener Multiplikationsschaltungsvarianten erklärt. Die Beispiele sind nicht erschöpfend und beziehen sich auf die angefügte Zeichnung, wobei:
Fig. 1 der Blockschaltplan der hier beschriebenen eindimensionalen DCT-Transformations-Berechnungsschaltung ist;
Fig.n 2, 3, 4 und 5 Ausführungsformen der ERM- und ORM- Blöcke von Fig. 1, welche Multiplikationsoperationen ausführen, zeigen;
Fig. 6 eine Ausführungsform der zweidimensionalen DCT- Transformations-Berechnungsschaltung, die zwei in Fig. 1 gezeigte Schaltungen verwendet, zeigt.
Vor dem Beschreiben der Figuren soll eine kurze theoretische Begründung der in der Schaltung erhaltenen Ergebnisse gegeben werden.
Die eindimensionale DCT-Transformation der diskreten Funktion f(j), mit j = 0, 1, ..., N-1, ist wie folgt definiert:
k = 0, 1 ..., N-1
wobei:
c(k) = 1/2 für k=0
= 1 für k=1, 2, ...., N-1
Die zweidimensionale DCT-Transformation der diskreten Funktion f(i, j) mit i, j = 0, 1 ..., N-1 ist wie folgt definiert:
k = 0, 1, ..., N-1
1 = 0, 1, ..., N-1
wobei:
c(k) = 1/ 2 für k = 0
= 1 für k = 1, 2, ..., N-1
d(1) = 1/ 2 für 1 = 0
= 1 für 1 = 1, 2, ..., N-1
DCT-Transformations-Koeffizienten in den beiden Fällen der Basis N=16 und N=8 sind unten in den Tabellen 1 und 2 gezeigt; die Koeffizienten sind in acht Bits quantifiziert, zum Beispiel sieben Mantissenbits und ein Vorzeichenbit: Tabelle 1 - DCT-Transformation mit Basis N=16 Tabelle 2 - DCT-Transformation mit Basis N=8
In den Tabellen 1 und 2 wird sichtbar, daß es dort verschiedene periodisch wiederkehrende positive oder negative Koeffizientenwerte gibt, welche sich in den Spalten mit einer anderen Reihenfolge und mit einer prinzipiell horizontalen Pseudo-Spiegelung wiederholen, welche zum Verkleinern der Anzahl der auszuführenden Operationen auf die Hälfte ausgenutzt werden kann, und zwar durch Ausführen einer vorausgehenden Addition oder Subtraktion von Abtastwerten im Vergleich zu dem Eingangsabtastwertvektor f(j), in Übereinstimmung mit der folgenden Bedingung:
f(j) + f(N-j-1), wobei j gerade ist
f(j) - f(N-j-1), wobei j ungerade ist.
Der Erfinder hat festgestellt, daß jeder Koeffizient einer Spalte mit Hilfe einer einfachen Additions- und Schiebeoperation aus den vorhergehenden Koeffizienten erhalten werden kann, wobei die ungeraden Matrixzeilen jederzeit von den geraden Zeilen getrennt bleiben; der erste Koeffizient der beiden geraden und ungeraden Zeilen wird in eine Summe von zwei Zweierpotenzwerten aufgeteilt.
Ein mögliches nichtbeschränkendes Beispiel einer solchen Koeffizienten-Aufspaltung für N=16 ist folgendes: Tabelle 3
Wie man sieht, ist der bedeutendste Aspekt dieser Aufspaltung, daß das Ausführen einer Multiplikationsoperation zwischen einem zu transformierenden f(j)-Signalabtastwert und einem Matrixkoeffizienten schlimmstenfalls eine Addition und zwei Verschiebungen (im Fall des Koeffizienten 57) zwischen den im vorhergehenden Schritt erhaltenen Termen erfordert. Wenn eine Verschiebung sofort durch eine geeignete Operandenjustierung ausgeführt werden kann, kann gezeigt werden, daß der ganze Transformationsalgorithmus auf die Berechnung von N N N-Additionen und N N(N-2)-Speicherungen reduziert werden kann, oder mit anderen Worten, auf ungefähr 2NN(N-1) gleiche Additionen.
Koeffizient 70 ist, aus Gründen welche später erklärt werden, mit einem negativen Vorzeichen versehen.
Ein anderes nicht beschränkendes Beispiel dieser Koeffizientenaufspaltung, angewandt auf die Basis N=8, ist folgendes: Tabelle 4
Dieser Fall erfordert eine anfängliche Aufspaltung in Vielfache von 7, welche wiederum in Zweierpotenzfaktoren dividiert werden; die totale Anzahl der gleichen auszuführenden Additionen ist gleich N N(2N+1), welche größer erscheinen würde als der vorhergehende Fall auf der Basis N=16, aber praktisch kleiner ist, da der Wert von N kleiner ist.
Der Transformationsalgorithmus für den eindimensionalen Fall besteht in der Berechnung des Matrixproduktes aus einer Sequenz eines N-elementigen Spaltenvektors (die die Sequenz eines zu transformierenden Eingangssignals repräsentiert) und der Transformationskoeffizientenmatrix der Dimension N N, wobei man einen anderen N-elementigen Spaltenvektor erhält: mit den bekannten oben beschriebenen Schaltungen wird dies üblicherweise durch Multiplizieren und Speichern jedes Eingangsvektorelementes mit allen Termen der entsprechenden Matrixzeile, bei zeilenweisem Fortbewegen innerhalb der Matrix, erreicht.
Stattdessen verwendet der Erfinder die oben beschriebene Beziehung zwischen den verschiedenen Matrixkoeffizienten, um eine Schaltung relativ einfacher Struktur zu entwickeln, welche das Matrixprodukt durch unterschiedliches Ordnen der verschiedenen Zwischenergebnisse mit spaltenweisem Fortbewegen innerhalb der Matrix berechnet. Mit anderen Worten werden für jede Spalte N partielle Beiträge für die N Spalten-Koeffizienten berechnet und gespeichert, aber die N Koeffizienten sind immer in der gleichen, doppelten in Tabelle 3 oder 4 gezeigten Folge adressiert, um die oben beschriebenen Beziehungen zwischen den verschiedenen Koeffizienten auszunutzen.
Nur eine Hälfte der Spalten wird berücksichtigt, weil die andere Hälfte spiegelbildlich ist.
Andererseits ist ein Speicher mit der Kapazität von N Worten für die temporäre Speicherung der Zwischenergebnisse erforderlich, da alle partiellen Beiträge für jede f(k) Komponente gleichzeitig für jeden f(j) Eingangsabtastwert berechnet werden müssen. Außerdem erfordert die zweidimensionale Transformation einen weiteren Speicher mit einer Kapazität von N N Worten zwischen den zwei orthogonalen Transformationsprozessen, da der zweite Transformationsschritt auf die für den eindimensionalen Fall transponierten N Vektoren angewendet werden muß.
Die Größe jedes Wortes ist (log N+Nb+Ns) Bits, wobei log N 4 oder 3 sein kann, Nb in unserem Fall gleich 8 und die Genauigkeit der Koeffizienten ist, und Ns die Genauigkeit der Eingangsabtastwerte ist.
Für das Wiederanordnen der zu speichernden verschiedenen Zwischenergebnisse erlaubt diese Art der Annäherung eine einfache Adreßerzeugung und -behandlung so daß in der weiteren Entwicklung der schaltungsinternen Adressierungseinheit keine weiteren Komplikationen hervortreten.
Fig. 1 ist ein für beide Fälle N=16 und N=8 gültiges Blockdiagrammder eindimensionalen Transformationsberechnungsschaltung.
MEM1 ist ein Speicher, in welchen die N Vektorelemente der zu transformierenden f(j) Abtastwerte geschrieben sind; diese Elemente sind während des Lesens durch eine Adressierungseinheit ADR1 adressiert, so daß die Ausgangsbusse 1 und 2 gleichzeitig Elemente des Index f(j) bzw. f(N-j-1) halten, mit j schrittweise steigend von 0 bis (N/2-1).
SOM1 ist ein normaler Addierer für die Ausgänge 1 und 2 von MEM1, während SOT1 ein normaler Subtrahierer ist, welcher den Ausgang 2 von MEM1 von Ausgang 1 subtrahiert.
RG1 und RG2 sind zwei normale Register zur temporären Speicherung der Ausgänge von SOM1 bzw. SOT1.
ERM und ORM sind zwei zum Pseudomultiplizieren der Eingangsabtastwerte-Vektorelemente mit den Transformationsmatrix-Koeffizienten fähige Schaltungen, gemäß der Erfindung; ERM wird für die geraden Zeilen der Matrix benutzt und erhält die Abtastwerte vom Ausgang 3 von RG1, während ORM für die ungeraden Zeilen benutzt wird und die Abtastwerte vom Ausgang 4 von RG2 erhält.
Mögliche Ausführungsformen von ERM und ORM werden unten untersucht.
RG3 und RG4 sind zwei normale Register für die temporäre Speicherung von Ergebnissen von Operationen, die von den Schaltungen ERM bzw. ORM ausgeführt werden und an den Ausgängen 5 und 6 dieser Schaltungen verfügbar sind. RG3 liefert Daten am Ausgang 8 und RG4 am Ausgang 9.
SMST1 und SMST2 sind zwei normale Addierer/Subtrahierer, welche Eingang 8 zu Eingang 10 und Eingang 9 zu Eingang 11 addieren oder Eingang 8 von Eingang 10 und Eingang 9 von Eingang 11 subtrahieren.
Die Auswahl der Operationen wird vom Block ADR2 gesteuert: die Summierung wird mit den positiven Koeffizienten der Transformation ausgeführt, während die Subtraktion mit den negativen Koeffizienten stattfindet.
MEM2 und MEM3 sind zwei Speicher zum Speichern der partiellen Ergebnisse R(k) der durch SMST1 und SMST2 ausgeführten Summierung/Subtraktion.
MEM2 speichert N/2 partielle Ergebnisse R(2k) in Bezug auf die Beiträge der geraden Koeffizientenmatrixzeilen, während MEM3 N/2 partielle Ergebnisse R(2k+1) der ungeraden Zeilen (0≤k≤N/2-1) speichert.
MEM2 und MEM3 sind linienstrukturiert, mit einer Zeile für jeden Index k.
RG5 und RG6 sind zwei Register zur temporären Speicherung von in den entsprechenden Speichern MEM2 und MEM3 gelesenen partiellen Ergebnissen R(2k) und R(2k+1). Während der Transformationsberechnung sind die verschiedenen partiellen Ergebnisse an den Ausgängen 10 und 11 von RG5 und RG6 vorhanden. Am Ende der Berechnung sind die N Elemente des Transformationsvektors F(k) an den Ausgängen 12 und 13 vorhanden und sind in die geraden Indexelemente F(2k) an Ausgang 12 und die ungeraden Indexelemente F(2k+1) an Ausgang 13 aufgeteilt.
ADR2 ist ein Adreßgenerierungsblock, welcher die Speicher MEM2 und MEM3, die Befehlssignale für die von den Blöcken ERM und ORM ausgeführten Operationen, die SMST1- und SMST2-Operationsauswahlsignale und die RG5- und RG6-Ausgangsauswahlsignale liest und schreibt.
Für jede Spalte der Transformationskoeffizientenmatrix liefert ADR2 immer dieselbe Folge von Befehlsignalen an die Blöcke ERM und ORM zum Ausführen der Sequenz von Operationen, die als Beispiel in den Tabellen 3 und 4 gezeigt sind. Meldungen, welche sich als Funktion einer Matrixspalte ändern, beinhalten die Steuerung der durch SMST1 und SMST2 ausgeführten Operationen und das Adressieren der Speicher MEM2 und MEM3 durch ADR2, um die partiellen Ergebnisse R(2k) und R(2k+1) eines geeigneten Index k zu lesen.
Das ist wegen der verschiedenen Stellung der Koeffizienten mit gleichen absoluten Werten in den verschiedenen Matrixspalten nötig.
Die durch ADR2 generierte MEM2- und MEM3-Adreßlesesequenz kann einfach aus den Tabellen 1, 2, 3 und 4 auf der Basis der folgenden Überlegungen hergeleitet werden.
Die in Fig. 1 gezeigte Schaltung ist in zwei Bereiche aufgeteilt, die sich auf die entsprechenden geraden und ungeraden Zeilen der Koeffizientenmatrix beziehen; die Bereiche arbeiten gleichzeitig.
Deshalb adressiert ADR2 gleichzeitig Paare von verschiedenen Ergebnissen, eins in MEM2 und eins in MEM3.
In beiden Fällen von N=16 und N=8, in den zugeordneten Tabellen 1 oder 2, wird die obere linke Ecke als Ausgangspunkt genommen (Spalte 0, Zeile 0). Für jede Spalte m (0≤m≤N/2-1) adressiert ADR2 MEM2- und MEM3-Positionen des Zeilenindex n (0≤n≤N-1), so daß immer dieselbe Folge von in den Tabellen 3 oder 4 angegebenen Koeffizienten erzeugt wird.
In diesen Tabellen bezieht sich die linksseitige Folge (9, 26, ... oder 7, 25 , 71, ...) immer auf die ungeraden Zeilen, während sich die rechtsseitige Folge (18, 35, ..., oder 7, 49, 91, ...) immer auf die geraden Zeilen bezieht.
Was die Anhäufungen bezüglich der Spalte mit dem letzten Index N/2-1 anbetrifft, so sind die Daten an den Ausgängen 12 und 13 bereits die Endergebnisse der Transformationsoperation, aber in einer ungeordneten doppelten Sequenz, nämlich mit veränderlichem Index k, der von der besonderen Ordnung der Koeffizientenfolge in Tabelle 3 oder 4, in der (N/2-1)-ten Spalte der Tabelle 1 oder 2 abhängt.
Wenn es die priinäre Absicht ist, die Verzögerung, mit der die Schaltung die Transformation berechnet, zu minimieren, kann folglich die letzte Speicherung der Ergebnisse in MEM2 und MEM3 vermieden werden, und diese Ergebnisse können an den Ausgängen 12 und 13 mit Hilfe eines Datenbereit-Signals DR bereitgestellt werden, das von ADR2 am Beginn der letzten Serie der SMST1- und SMST2-Berechnungen, die sich auf die (N/2-1)-te Spalte beziehen, geliefert wird.
In diesem Fall wird einer externen Adressierungseinheit, die in der in Fig. 1 gezeigten Schaltung stromabwärts liegt, die Aufgabe des korrekten Anforderns der Ergebnisse zugewiesen.
Wenn es umgekehrt wichtiger ist, eine korrekt angeordnete Folge der Ergebnisse (mit k linear wachsend) an den Ausgängen der in Fig. 1 gezeigten Schaltung zu erhalten, werden die auf die letzte Spalte bezogenen Berechnungsergebnisse in MEM2 und MEM3 gespeichert.
ADR2 liefert dann das Datenbereit-Signal DR und adressiert MEM2 und MEM3 in alternierender Folge, um eine geordnete Folge von N Komponenten des Transformationsvektors F(k) an den Ausgängen 12 und 13 zur Verfügung zu stellen.
Soweit es die Adreßgenerierung für MEM2 und MEM3 betrifft, kann ADR2 aus zwei Zählern bestehen, einer für MEM2 und einer für MEM3, welche in Folge für jede Matrixspalte von 0 bis N/2-1 zählen, gefolgt von einer Verknüpfungs-Logik, welche die Bitanordnung am Zählerausgang in Beziehung zum Wert von m (z. B. der Spalte) geeignet umwandelt.
Alternativ kann ADR2 aus einem matrixstrukturierten Speicher bestehen, der in auf steigender Folge sequentiell adressiert wird, und zwar als erstes für die Spalten und dann für die Zeilen, und in welchen das Paar von N Werten, die benutzt werden, um MEM2 und MEM3 zu adressieren, in jeder Position geschrieben wird.
Keine dieser Ausführungsformen von ADR2 sollte nach den hier gegebenen Datenbeschreibungen Probleme für Fachmänner aufwerfen.
Obwohl sie in der Figur nicht gezeigt ist, ist eine externe Standard-Synchronisationseinheit, welche ebenfalls keine Probleme für den Techniker mit sich bringen sollte, vorhanden, um ein Taktsignal an die verschiedenen sequentiellen Schaltungen und den ADR2-Block zu liefern. Außerdem beliefert diese Einheit ADR2 mit einem Startsignal zur Berechnung eines Eingangsabtastwertevektors f(j).
In Fig. 1 sind die Blöcke MEM1 und ADR1 kein wesentlicher Teil der DCT-Transformations-Berechnungsschaltung, aber sie stellen ein mögliches Beispiel dar, wie die doppelte Folge von f(j) Vektoren an den Eingängen 1 und 2 erreicht werden kann.
Wenn die in Fig. 1 gezeigte Schaltung unter Benutzen einer integrierten Struktur aufgebaut wird, ist es ratsam, diese Blöcke außerhalb der integrierten Schaltung abzugrenzen. Das ist teilweise so, weil sie Teil von existierenden Schaltungen sein können und die benutzten Techniken somit von dem spezifischen Fall der Anwendung abhängen. Jedoch sollte sichergestellt werden, daß die spezielle Sequenz der Vektor-f(j)-Komponenten wie oben beschrieben an den Eingängen 1 und 2 erhalten wird.
Fig. 2 zeigt ein erstes Beispiel einer Ausführungsform der Blöcke ERM und ORM, die mit einer strichpunktlinie angezeigt sind, für N=8.
ERM besteht aus Schaltungsblöcken MX1, MX2, SH1, SH2, SMST3 und RG7, während ORM aus Schaltungsblöcken MX3, MX4, SH3, SH4, SMST4, RG8, RG9 und RG10 besteht.
MX1 und MX2 sind zwei normale Multiplexer, jeder von ihnen wird vom Ausgang 3 von RG1 (Fig. 1) und Ausgang 15 von RG7 beliefert.
SH1 und SH2 sind zwei Schaltungen, welche die an ihre Eingänge angelegten Daten um eine gegebene variable Anzahl von Eingangspositionen schieben. SH1 empfängt das Ausgangssignal von MX1, während SH2 das Ausgangssignal von MX2 empfängt.
SH1 und SH2 sind Trommelschiebeschaltungen, bestehend aus einer Batterie von Multiplexern, welche eine variable Anzahl von Eingangspositionen in einer kurzen festen Periode (welche die mittlere Datenübertragungszeit durch ihre struktur ist) schieben. Die Anzahl der Schiebepositionen ist durch eine an ihren Kontrolleingang angelegte Bitkombination festgelegt. Diese Schaltungen werden anstelle von normalen Schieberegistern wegen ihrer größeren Schiebegeschwindigkeit benutzt.
Die Ausgänge von SH1 und SH2 sind an einen normalen Addierer- /Subtrahierer SMST3 gebracht, welcher die Eingänge addiert oder den SH2-Ausgang von dem SH1-Ausgang subtrahiert.
Der Ausgang von SMST3 ist Ausgang 5 des ERM-Blocks und ist der Eingang eines normalen Registers RG7, welches die Eingangsdaten über den Empfang eines Ladesignals von Verbindung 7 speichert und dessen Datenausgang mit den Eingängen von MX1 und MX2 verbunden ist.
Die ORM-Blockstruktur ist ähnlich der von ERM und besteht aus zwei Multiplexern MX3 und MX4, gefolgt von zwei Trommelschiebern SH3 und SH4, welche einen Addierer-Subtrahierer SMST4 beliefern; der letztgenannte addiert die Eingänge oder subtrahiert den SH3-Ausgang von dem SH4-Ausgang.
Der Ausgang von SMST4 ist der ORM-Ausgang 6 und ist der Eingang von normalen Registern RG8, RG9 und RG10, welche die Eingangsdaten nach dem Empfangen eines Ladesignals von Verbindung 7 speichern.
MX3 empfängt den RG2-Ausgang 4 (Fig. 1) und den RG8-Ausgang 16, während MX4 den RG2-Ausgang 4, RG9-Ausgang 17 und RG10-Ausgang 18 empfängt.
Der ADR2-Block (Fig. 1) liefert auf der Verbindung 7 die Eingangsselektionssignale der Multiplexer MX1, MX2, MX3 und MX4, die Bitkombinationen, die die Ausdehnung des Verschiebens bestimmen, das von SH1, SH2, SH3 und SH4 ausgeführt wird, die Ladesignale für die Register RG4, RG8, RG9 und RG10 und die Additions/Subtraktionsauswahlsignale für SMST3 und SMST4. Die Zusammensetzung des Teils von ADR2, welcher die Signale auf der Verbindung 7 erzeugt, kann leicht aus der folgenden Beschreibung der ERM- und ORM- Blockoperation hergeleitet werden.
Für jedes Datum an den Eingängen 3 und 4 multipliziert der ERM-Block die Koeffizienten der rechtsseitigen Spalte von Tabelle 3, während ORM die Koeffizienten der linksseitigen Spalte multipliziert, fortschreitend vom Anfang zum Ende der Tabelle.
Um das Datum an Eingang 3 mit dem ersten Koeffizienten (18) zu multiplizieren, sind beide MX1 und MX2 auf den Eingang 3 geschaltet; SH1 schiebt um vier Positionen nach links (Multiplikation mit 16), während SH2 um eine Position schiebt (Multiplikation mit 2); SMST3 addiert dann, während das Ergebnis der Multiplikation mit 18 am Ausgang 5 vorliegt und auch temporär in Register RG7 gespeichert wird und später der Multiplikation des Datums am Eingang 3 mit dem zweiten und dem dritten Koeffizienten (35 und 50) dient. Für den zweiten Koeffizienten (35) ist MX1 durch RG7 auf den Eingang 15 geschaltet und MX2 auf den Eingang 3; SH1 schiebt um eine Position nach links, SH2 schiebt keine Position und SMST3 bildet die Differenz. Für den dritten Koeffizienten (50) ist MX1 auf den Eingang 15 geschaltet und MX2 auf den Eingang 3; SH1 schiebt keine Position, während SH2 fünf Positionen nach links schiebt; SMST3 addiert die zwei Eingänge und das Ergebnis wird in RG7 anstelle seines Vorgängers gespeichert, ebenso wie es am Ausgang 5 verfügbar ist.
Für den vierten Koeffizienten (64) werden MX1 und MX2 auf den Eingang 3 geschaltet; SH1 und SH2 schieben um fünf Positionen nach links und SMST3 bildet die Summe.
Für den fünften Koeffizienten (75) sind MX1 und MX2 auf den Eingang 15 geschaltet; SH1 schiebt um eine Position nach rechts (Division durch 2), während SH2 keine Position schiebt; SMST3 erzeugt die Summe der Eingänge. Für den sechsten Koeffizienten (84) ist MX1 auf den Eingang 15 und MX2 auf den Eingang 3 geschaltet; SH1 schiebt um eine Position, SH2 um vier Positionen nach links; SMST3 bildet die Differenz. Für den siebenten Koeffizienten (89) ist MX1 auf den Eingang 15 und MX2 auf den Eingang 3 geschaltet; SH1 schiebt eine Position nach rechts, SH2 schiebt sechs Positionen nach links, und SMST3 bildet die Summe.
Für den achten Koeffizienten (64) werden die gleichen Operationen wie für den vierten Koeffizienten ausgeführt.
Um das Datum am Eingang 4 mit dem ersten Koeffizienten (9, erste Spalte in Tabelle 3) zu multiplizieren, sind MX3 und MX4 auf den Eingang 4 geschaltet; SH3 schiebt keine Position, SH4 schiebt um drei Positionen nach links (Multiplikation mit 8); SMST4 bildet die Summe und das Ergebnis ist am Ausgang 6 verfügbar und abgesehen davon auch in Register RG8 gespeichert und dient für die nachfolgende Multiplikation mit dem zweiten, dritten und vierten Koeffizienten (26, 43 und 70).
Für den zweiten Koeffizienten (26) ist MX4 auf den Eingang 4 und MX3 auf den Eingang 16 geschaltet; SH3 schiebt um eine Position nach links, SH4 schiebt um drei Positionen nach links; SMST4 bildet die Summe und das Ergebnis wird auch in Register RG9 gespeichert. Für den dritten Koeffizienten (43) ist MX3 auf den Eingang 16 und MX4 auf den Eingang 17 geschaltet; SH3 schiebt keine Position, SH4 schiebt um eine Position nach links; SMST4 bildet die Differenz und das Ergebnis wird in Register RG10 gespeichert. Für den vierten Koeffizienten (-70) ist MX4 auf den Eingang 4 und MX3 auf den Eingang 16 geschaltet; SH3 schiebt um drei Positionen nach links, SH4 schiebt um eine Position nach links und SMST4 bildet die Differenz. Der vierte Koeffizient ist mit einem negativen Vorzeichen versehen, weil es ansonsten nötig sein würde, die Eingänge von SMST4 zu invertieren, was die Schaltung unnötig verkomplizieren würde. Jedoch wird das korrekte Vorzeichen des von ORM berechneten Ergebnisses durch einen geeigneten Additions- oder Subtraktionsbefehl von SMST2 (Fig. 1) wiederhergestellt, ohne die Schaltung weiter zu belasten.
Für den fünften Koeffizienten (80) sind MX3 und MX4 auf den Eingang 4 geschaltet; SH3 und SH4 schieben entsprechend um vier, bzw. sechs Positionen nach links; SMST4 bildet die Summe, und das Ergebnis wird in Register RG8 anstelle des Vorgängers gespeichert.
Für den sechsten Koeffizienten (57) ist MX3 auf den Eingang 16 und MX4 auf den Eingang 17 geschaltet; SH3 schiebt um vier Positionen nach rechts (Division durch 16), SH4 um eine Position nach links und SMST4 bildet die Summe. Für den siebenten Koeffizienten (87) ist MX3 auf den Eingang 4 und MX4 auf den Eingang 18 geschaltet; SH3 schiebt um keine Position. SH4 schiebt um eine Position nach links und SMST4 bildet die Summe.
Für den achten Koeffizienten (90) ist MX3 auf den Eingang 4 und MX4 auf den Eingang 17 geschaltet; SH3 schiebt um sechs Positionen nach links, SH4 schiebt keine Position und SMST4 bildet die Summe.
Die beiden Blöcke ERM und ORM arbeiten gleichzeitig und führen somit eine allgemeine Multiplikation mit Hilfe von zwei Verschiebungen und einer Addition/Subtraktion aus, ebenso speichern sie, wenn nötig, das Ergebnis in einem der Register RG7, ..., RG10.
Fig. 3 zeigt ein zweites Beispiel einer Ausführungsform von ERM und ORM-Blöcken, die durch Strichpunktlinien angezeigt sind, für N=16.
ERM und ORM bestehen aus Paaren von Addierern oder Subtrahierern und Registern; jedes Paar ist dem Produkt eines in Tabelle 3 gegebenen Koeffizienten zugeordnet. Jeder Registerausgang ist an einen Ausgangsmultiplexer und, wo nötig, an den Eingang eines anderen Addierers oder Subtrahierers angeschlossen. Die Eingänge der Addierer oder subtrahierer sind geeignet angeordnet, um die verschiedenen Multiplikationen oder Divisionen zur Potenz von 2, die in Tabelle 3 gezeigt werden, zu erzeugen.
Der Block ADR2 (Fig. 1) steuert nur die Multiplexer, um die zwei Folgen der Produktergebnisse in Übereinstimmung mit den in Tabelle 3 gezeigten Folgen zu erzeugen. ERM erzeugt die Produktfolge für die rechtsseitige Koeffizientenspalte in Tabelle 3, während ORM die produktfolge für die linksseitige Koeffizientenspalte erzeugt.
Betrachtet man den ERM-Block detaillierter, so multipliziert ein Addierer SM1 den ersten Koeffizienten (18) in der rechtsseitigen Spalte der Tabelle 3 und ein Register RG11 speichert das Ergebnis. SM1 empfängt den RG1-Registerausgang 3 (Fig. 1), der am ersten Eingang um vier Positionen nach links und am zweiten Eingang um eine Position nach links (Multiplikation mit 16 und 2)verschoben ist.
Ein Subtrahierer ST1 multipliziert den zweiten Koeffizienten (35) und ein Register RG13 speichert das Ergebnis. ST1 subtrahiert den an den ersten Eingang angelegten Ausgang 3 von dem an den zweiten Eingang angelegten RG11-Ausgang und schiebt um eine Position nach links.
Ein Addierer SM2 multipliziert den dritten Koeffizienten (50) und ein Register RG12 speichert das Ergebnis. SM2 empfängt den um fünf Positionen nach links geschobenen Ausgang 3 und den Ausgang des Registers RG11.
Ein Register RG17 multipliziert den vierten und den achten Koeffizienten (64); tatsächlich empfängt es den um sechs Positionen geschobenen Ausgang 3.
Ein Addierer SM4 multipliziert den fünften Koeffizienten (75) und ein Register RG16 speichert das Ergebnis. SM4 empfängt den Ausgang des Registers RG12, um eine Position nach rechts (Division durch 2) verschoben, am ersten Eingang und unverschoben am zweiten Eingang.
Ein Subtrahierer ST2 multipliziert den sechsten Koeffizienten (84) und ein Register RG14 speichert das Ergebnis. SM3 empfängt den um sechs Positionen nach links geschobenen Ausgang 2 und den um eine Position nach rechts geschobenen (Division durch 2) Ausgang des Registers RG12.
Die Ausgänge der Register RG11, ..., RG17 werden an den 7- Eingangs-Multiplexer MX5 gebracht. Der RG17-Ausgang wird doppelt durch MXS auf den Ausgang 5 geschaltet.
Was den ORM-Block anbetrifft, so multipliziert ein Addierer SM6 den ersten Koeffizienten (9) in der linksseitigen Spalte der Tabelle 3 und ein Register RG19 speichert das Ergebnis. SM6 erhält den um drei Positionen nach links geschobenen Ausgang 4 am ersten Eingang und unverschoben am zweiten Eingang.
Ein Addierer SM7 multipliziert den zweiten Koeffizienten (26) und ein Register RG20 speichert das Ergebnis. SM7 erhält den um drei Positionen nach links geschobenen Ausgang 4 und den um eine Position nach links gestuften Ausgang des Registers RG19.
Ein Subtrahierer ST4 multipliziert den dritten Koeffizienten (43) und ein Register RG23 speichert das Ergebnis. ST4 subtrahiert den Ausgang des Registers RG19 von dem um eine Position nach links geschobenen Ausgang des Registers RG20.
Ein Subtrahierer ST3 multipliziert den vierten Koeffizienten (-70) und ein Register RG21 speichert das Ergebnis. ST3 subtrahiert den um drei Positionen nach links geschobenen Ausgang des Registers RG19 von dem um eine Position nach links geschobenen Ausgang 4. In diesem Fall macht das Koeffizienten-Vorzeichen keinen Unterschied, da es nicht die Schaltungskompliziertheit beeinflußt.
Ein Addierer SMS multipliziert den fünften Koeffizienten (80) und ein Register RG18 speichert das Ergebnis. SM5 erhält den um sechs Positionen nach links verschobenen Ausgang 4 am ersten Eingang und um vier Positionen nach links verschoben am zweiten Eingang.
Ein Addierer SM9 multipliziert den sechsten Koeffizienten (57) und ein Register RG24 speichert das Ergebnis. SM9 erhält den um vier Positionen nach rechts (Division durch 16) verschobenen Ausgang des Registers RG18 und den um eine Position nach links verschobenen Ausgang des Registers RG20.
Ein Addierer SM10 multipliziert den siebenten Koeffizienten (87) und ein Register RG25 speichert das Ergebnis. SM10 erhält den unverschobenen Ausgang 4 und den um eine Position nach links verschobenen Ausgang des Registers RG23.
Ein Addierer SM8 multipliziert den achten Koeffizienten (90) und ein Register RG22 speichert das Ergebnis. SM8 erhält den um sechs Positionen nach links gestuften Ausgang 4 und den unverschobenen Ausgang des Registers RG20.
Die Ausgänge der Register RG18, ..., RG25 werden zu dem 8- Eingangs-Multiplexer MX6 gebracht.
Wie vorher festgehalten, steuert der Block ADR2 (Fig. 1) nur die Multiplexer MX5 und MX6 durch Auswählen, über Steuersignale auf der Verbindung 7, einer geeigneten Aufeinanderfolge von Eingangsverbindungen mit den Ausgängen 5 und 6. Es ist nicht nötig, die Register RG11, RG12, ..., RG25 mit speziellen Ladebefehlen zu versorgen, denn es ist ausreichend, daß die Daten stabil und korrekt zu dem Zeitpunkt an ihren Ausgängen sind, an dem sie von den Multiplexern MX5 und MX6 abgenommen werden. Weiterhin bleiben die Daten stabil an den Ausgängen 3 und 4 der Register RG1 und RG2 (Fig. 1) für die von den Schaltungen ERM und ORM zum Ausführen aller Berechnungen geforderte Zeit, zum Beispiel für die Berechnungen, die sich auf eine Transformationskoeffizientenmatrixspalte beziehen. Folglich ist es ausreichend, das Laden der Register mit Hilfe des normalen Taktsignals zu befehlen, welches zu allen Schaltungsregistern gebracht wird, aber in den Figuren aus Gründen der Einfachheit nicht gezeigt ist, und die verschiedenen Operationsergebnisse pflanzen sich zwischen den verschiedenen in Kaskade geschalteten Registerstufen fort.
Nach dem ersten Taktsignalimpuls halten die Ausgänge der ersten Registerstufe RG11 (ERM-Block) und RG19 (ORM-Block) bereits ein korrektes, stabiles Datum, welches dann über die Multiplexer MX5 und MX6 direkt an die Ausgänge 5 und 6 übertragen wird, und so fort. MX5 und MX6 schalten dann mit dem folgenden Taktsignalimpuls.
Das in Fig. 3 gezeigte Ausführungsbeispiel erfordert die Benutzung einer größeren Anzahl von Komponenten (oder von gleichen logischen Gattern, wenn integrierte Schaltungen verwendet werden) als das in Fig. 2 gezeigte Beispiel, aber es erlaubt höhere Berechnungsgeschwindigkeiten und vereinfacht das Adressieren durch den Block ADR2.
Fig. 4 zeigt ein drittes Ausführungsbeispiel der Blöcke ERM und ORM, die mit einer Strichpunktlinie angezeigt sind, für N=8. Da diese Schaltungslösung der in Fig. 2 gezeigten folgt, wird der Leser für die generellen Überlegungen, die die benutzten Komponenten, den Betrieb und den Steuermodus des Blocks ADR2 (Fig. 1) betreffen, auf die Beschreibung dieser Schaltung verwiesen.
Für jedes Datum an den Eingängen 3 und 4 führt der Block ERM Multiplikationen mit den Koeffizienten in der rechtsseitigen Spalte in Tabelle 4 aus, während ORM mit den Koeffizienten in der linksseitigen Spalte multipliziert, fortschreitend von oben nach unten in Tabelle 4.
Der Block ERM besteht aus zwei Multiplexern MX7 und MX8, einem Trommelschieber SH5, der stromabwärts von MX7 liegt, einem Subtrahierer SMST5, welcher den SH5-Ausgang von dem MX8-Ausgang subtrahiert, und zwei Registern RG27 und RG28, welche den Ausgang 5 von SMST5 speichern können. An seinen Eingängen empfängt MX7 den Ausgang 3 und den Ausgang 20 von RG27; die MX8-Eingänge empfangen den Ausgang 3, einen RG27-Ausgang 20 und einen RG28-Ausgang 21.
Nur ein Trommelschieber ist nötig, da es für die Eingänge des Multiplexers MX8 zur ausreichenden Justierung genügt, die Multiplikationen mit den Zweierpotenzen des ersten Addenden der in der rechtsseitigen Spalte der Tabelle 4 gezeigten Zerlegungen zu erhalten: der um eine Position nach links verschobene (Multiplikation der Koeffizienten 49 und 91 mit 2) Ausgang 21 des Registers RG28 ist an den MX8-Eingang angelegt; die um drei Positionen nach links verschobenen (Multiplikation des Koeffizienten 7 und des Eingangsdatums mit 8) Ausgänge 20 von RG27 und 3 von RG1 (Fig. 1) sind an MX8 angelegt.
Um das Datum am Eingang 3 mit dem ersten Koeffizienten (7) zu multiplizieren, sind MX7 und MX8 an den Eingang 3 geschaltet; SH5 verschiebt um keine Position; der Ausgang von SMST5 ist in RG27 gespeichert und ist nicht in MEM2 (Fig. 1) abgelegt, weil er nur innerhalb von ERM benutzt wird.
Für Operationen mit dem zweiten Koeffizienten (49) sind MX7 und MX8 an den RG27-Ausgang 20 geschaltet; SH5 verschiebt um keine Position; der Ausgang von SMST5 wird in RG28 gespeichert und wird auch vom Ausgang 5 übernommen und in MEM2 (Fig. 1) abgelegt.
Für Operationen mit dem dritten Koeffizienten (91) ist MX7 an den RG27-Ausgang 20 geschaltet und MX8 ist an den RG28-Ausgang 21 geschaltet und SH5 verschiebt um keine Position. Der selbe Zyklus von Operationen wird für den vierten Koeffizienten (91) benutzt; am Ende ist das Ergebnis von SMST5 auch in RG28 gespeichert.
Für Operationen mit dem fünften Koeffizienten (118) ist MX7 an den Ausgang 3 geschaltet, MX8 ist an den RG28-Ausgang 21 geschaltet und SH5 schiebt um sechs Positionen nach links (Multiplikation mit 64).
Der ORM-Block besteht aus zwei Multiplexern MX9 und MX10, gefolgt von zwei Trommelschiebern SH6 und SH7, welche einen Addierer/Subtrahierer SMST6 versorgen, dessen Ausgang 6 auch in zwei Registern RG29 und RG30 gespeichert werden kann. MX9 empfängt den RG2-Ausgang 4 (Fig. 1) und den RG29-Ausgang 22, während MX10 den Ausgang 4 und einen RG30- Ausgang 23 empfängt.
Um das Datum am Eingang 4 mit dem ersten Koeffizienten (7) in der linksseitigen Spalte von Tabelle 4 zu multiplizieren, sind MX9 und MX10 an den RG1-Ausgang 4 (Fig. 1) geschaltet; SH6 schiebt nicht; SH7 schiebt um drei Positionen nach links; SMST6 subtrahiert den SH6- Ausgang von dem SH7-Ausgang; der SMST6-Ausgang wird nur in RG29 gespeichert und wird nicht in MEM2 (Fig. 1) abgelegt, da er nur innerhalb von ORM benutzt wird.
Für Operationen mit dem zweiten Koeffizienten (25) ist MX9 an den RG29-Ausgang 22 geschaltet, und MX10 ist an den Ausgang 4 geschaltet; SH6 schiebt nicht, während SH7 um fünf Positionen schiebt. SMST6 subtrahiert den SH6-Ausgang von dem SH7-Ausgang und der Ausgang wird auch in RG30 gespeichert.
Für Operationen mit dem dritten Koeffizienten (71) ist MX9 an den RG29-Ausgang 22 geschaltet, und MX10 ist an den Ausgang 4 geschaltet; SH6 schiebt nicht, während SH7 um sechs Positionen schiebt, und SMST6 addiert die Ausgänge von SH6 und SH7.
Für Operationen mit dem vierten Koeffizienten (106) ist MX9 an den RG29-Ausgang 22 geschaltet, und MX10 ist an den RG10-Ausgang 23 geschaltet; SH6 schiebt um drei Positionen nach links und SH7 um eine, und SMST6 addiert die Ausgänge von SH6 und SH7.
Für Operationen mit dem fünften Koeffizienten (126) sind MX9 und MX10 an den Ausgang 4 geschaltet; SH6 schiebt um eine Position und SH7 um sieben Positionen nach links, und SMST6 subtrahiert den Ausgang von SH6 vom Ausgang von SH7.
Fig. 5 zeigt ein viertes Beispiel einer Ausführungsform der Blöcke ERM und ORM, die mit Strichpunktlinien angezeigt sind, für N=8.
Da diese Schaltungslösung der in Fig. 3 gezeigten folgt, wird der Leser für generelle Überlegungen, die die benutzten Komponenten, den Betrieb und den Steuermodus des Blocks ADR2 (Fig. 1) betreffen, auf die Beschreibung dieser Schaltung verwiesen.
Für jedes Datum an den Eingängen 3 und 4 führt der Block ERM Multiplikationen mit den Koeffizienten in der rechtsseitigen Spalte der Tabelle 4 aus, während ORM mit den Koeffizienten in der linksseitigen Spalte der Tabelle multipliziert.
In dem Block ERM multipliziert ein Subtrahierer ST6 das Datum am Ausgang 3 von RG1 (Fig. 1) mit dem ersten Koeffizienten (7) in der rechtsseitigen Spalte von Tabelle 4, und das Ergebnis wird im Register RG31 gespeichert.
An seinen beiden Eingängen erhält ST6 den Ausgang 3, am Minuend-Eingang um drei Positionen nach links verschoben.
Der Subtrahierer ST7 multipliziert den zweiten Koeffizienten (49) und das Ergebnis wird in Register RG32 gespeichert. An seinen zwei Eingängen erhält ST7 den Ausgang von RG31, am Minuend-Eingang um drei Positionen verschoben.
Ein Subtrahierer ST8 multipliziert den dritten Koeffizienten (91) und das Ergebnis wird in Register RG33 gespeichert. ST8 subtrahiert den Ausgang von RG31, von dem um eine Position nach links verschobenen Ausgang von RG32.
Ein Subtrahierer ST9 multipliziert den vierten Koeffizienten (118) und das Ergebnis wird in einem Register RG34 gespeichert. ST9 subtrahiert den um sechs Positionen nach links verschobenen Ausgang 3 von dem um eine Position nach links verschobenen Ausgang von RG32.
Die Ausgänge der Register RG32, RG33 und RG34 sind an die Eingänge eines 3-Eingang-Multiplexers MX11 angelegt und werden der Reihe nach mit dem Ausgang 5 verbunden; der Ausgang von RG33 wird doppelt benutzt.
In dem ORM-Block multipliziert der Subtrahierer ST10 das Datum am Ausgang 4 von RG2 (Fig. 1) mit dem ersten Koeffizienten (7) in der linksseitigen Spalte der Tabelle 4 und das Ergebnis wird in einem Register RG35 gespeichert.
An seinen zwei Eingängen empfängt ST10 den Ausgang 4, am Minuend-Eingäng um drei Positionen nach links verschoben.
Ein Subtrahierer ST12 multipliziert den zweiten Koeffizienten (25) und das Resultat wird in einem Register RG37 gespeichert. ST12 subtrahiert den Ausgang von RG35 von dem um fünf Positionen nach links verschobenen Ausgang 4.
Ein Addierer SM12 multipliziert den dritten Koeffizienten (71) und das Ergebnis wird in einem Register RG38 gespeichert. SM12 addiert den um sechs Positionen nach links verschobenen Ausgang 4 zum Ausgang von RG35.
Ein Addierer SM13 multipliziert den vierten Koeffizienten (106) und das Ergebnis wird in einem Register RG39 gespeichert. SM13 addiert den um drei Positionen nach links verschobenen Ausgang von RG35 mit dem um eine Position nach links verschobenen Ausgang von RG37.
Ein Subtrahierer ST11 multipliziert den fünften Koeffizienten (126) und ein Register RG36 speichert das Ergebnis. An seinen zwei Eingängen empfängt ST11 den Ausgang 4, und zwar um sieben Positionen nach links verschoben, am Minuend-Eeingang und um eine Position nach links verschoben am Subtrahend-Eingang.
Die Ausgänge der Register RG36, RG37, RG38 und RG39 sind an die Eingänge eines 4-Eingang-Multiplexers MX12 angelegt und weiterhin mit dem Ausgang 6 verbunden.
Das in Fig. 5 gezeigte Beispiel einer Ausführungsform verlangt die Benutzung einer größeren Anzahl von Komponenten (oder von gleichen logischen Gattern, wenn integrierte Schaltungen verwendet werden) als das in Fig. 4 gezeigte Beispiel, aber es erlaubt höhere Berechnungsgeschwindigkeiten und vereinfacht das Adressieren durch den Block ADR2.
Die in Fig. 1 gezeigte Schaltung kann dazu benutzt werden, um die n-dimensionale DCT-Transformation mit beliebigem n zu berechnen, und mit besonderem Bezug für die Fälle des größten praktischen Interesses: n = 1, 2, 3.
In dem eindimensionalen Fall wurde gezeigt, daß die Schaltung nach Fig. 1 eine Reihe von Berechnungen an einem Eingangsabtastwertevektor ausführt.
In den zwei- und dreidimensionalen Fällen kann andererseits gezeigt werden, daß diese Operationen 2N- bzw. 3N²-mal wiederholt werden.
Die in Fig. 1 gezeigte Schaltung muß folglich erweitert werden, um Speicher zur zwischenzeitlichen Speicherung der Transformationsprodukte und Standardschaltungen für das Adressieren dieser Speicher, welche auch die Funktionen der Blöcke MEM1 und ADR1 (Fig. 1) ausführen können, einzuschließen.
Die von diesem Patent geschützte Schaltung kann vorteilhaft als VLSI-Schaltung ausgeführt sein. Nimmt man eine repräsentative Genauigkeit von 12 Bits für jede Eingangsvektor f(j)-Komponente an und 8 Bits für die Matrixkoeffizienten, kann die Schaltungskomplexität für jede der beschriebenen Varianten abgeschätzt werden.
Für die wie in Fig. 2 gezeigt ausgeführten ERM- und ORM- Blöcke erfordert die Gesamtschaltung rund 3500 gleiche Gatter (zum Beispiel mit HCMOS-Technologie besteht jedes gleichartige Gatter aus vier Transistoren) plus einem 16x24-Bit Akkumulationsspeicher (Blöcke MEM2 und MEM3, Fig. 1). Diese Ausführungsform liefert für jede elementare Operation eine Ausführungszeit von rund 60 ns. Für ERM und ORM-Ausführungsformen, wie in Fig. 3 gezeigt, erfordert die Gesamtstruktur rund 5800 gleichartige Gatter und einen gleichen Akkumulationsspeicher, mit einer Ausführungszeit pro elementarer Operation von rund 20 ns.
ERM- und ORM-Ausführungen, wie in den Fig. 3 und 4 gezeigt, erfordern 2900 bzw. 4000 gleichartige Gatter und einen 8x23Bit- Akkumulationsspeicher; die Ausführungszeiten pro elementarer Operation sind 60 ns bzw. 20 ns.
Fig. 6 zeigt ein Beispiel einer Ausführungsform einer zweidimensionalen DCT-Transformations-Berechnungsschaltung. Sie besteht aus zwei kaskadierten eindimensionalen DCT-Transformations- Berechnungsschaltungen (wie in Fig. 1 gezeigt), die als DCT1 und DCT2 bezeichnet sind, mit einem dazwischenliegenden Speicher MEM4 für die temporäre Speicherung von zwischenzeitlichen Ergebnisvektoren F(k). Der ADR3-Block erzeugt Lese/Schreibadressen für MEM4 und synchronisiert die Adreßgeneratoren ADR1 und ADR2 (Fig. 1) für die Blöcke DCT1 und DCT2. Der Speicher MEM4 ist dazu matrix-strukturiert, N Vektoren F(k) von je N Elementen zu enthalten, und wird in orthogonaler Weise zu der Richtung gelesen, in welcher er geschrieben wurde (Lesen in Spalten und Schreiben in Zeilen oder entgegengesetzt).
Das Ausführen der wie in Fig. 6 gezeigten Schaltung sollte dem Fachmann nach der gegebenen Beschreibung der in Fig. 1 gezeigten Schaltung keine Probleme bereiten.

Claims

1. Schaltung zum Berechnen der diskreten Cosinus-Transformation von f(j)-Abtastwertvektoren der Dimension N(0≤j≤N-1), wobei diese Transformation eine Quadratmatrixbasis der Dimensionen N N mit Koeffizienten hat, die sich in jeder Spalte im Absolutwert wiederholen, deren Ordnung (und in bestimmten Fällen Vorzeichen) jedoch unterschiedlich ist, wobei die Schaltung transformierte F(k) Abtastwertvektoren ergibt, die ebenfalls die Dimension N(0≤k≤N-1) haben, dadurch gekennzeichnet, daß sie aus zwei parallel arbeitenden Schaltungszweigen besteht, von denen der erste für Operationen, die sich auf Koeffizienten in geradzahligen Matrixzeilen beziehen, und der zweite für Koeffizienten in ungeradzahligen Zeilen dient, und die beiden Zweige aus folgenden Bestandteilen bestehen:

- einem ersten Addierer (SOM1) und einem ersten subtrahierer (SOT1), die dem ersten bzw. dem zweiten Zweig angehören und eingangsseitig Paare von Abtastwerten eines F(j)-Vektors mit Index (j) und (N-j-1) empfangen, wobei j auf einanderfolgend von 0 bis N/2-1 ansteigt;

-einer ersten Recheneinheit (ERM) und einer zweiten Recheneinheit (ORM), die dem ersten bzw. dem zweiten Zweig angehören und die für jedes Additions- oder Subtraktionsergebnis, das sie vom ersten Addierer (SOM1) oder vom ersten subtrahierer (SOT1) empfangen, N/2 Teilergebnisse bezugnehmend auf die Matrixspaltenkoeffizienten in geradzahligen bzw. ungeradzahligen Zeilen mit sequentieller Ordnung, die für alle Spalten festgelegt ist, unter den Koeffizienten einer Spalte berechnen und so jedes Teilergebnis durch eine Additions- und Verschiebeoperation erzeugen, die die vorherigen Teilergebnisse und/oder die Eingangsdaten verwendet;

- einem ersten Addierer/Subtrahierer (SMST1) und einem zweiten Addierer/Subtrahierer (SMST2), die dem ersten bzw. dem zweiten Zweig angehören und ein von einem zweiten Eingang (8, 9) empfangenes Teilergebnis, das von der ersten bzw. zweiten Recheneinheit (ERM, ORM) kommt, mit oder von einem von einem ersten Eingang (10, 11) empfangenen Datum, addieren oder subtrahieren, wobei sie die Summe im Fall eines auf einen positiven Koeffizienten bezogenen Teilergebnisses und die Differenz im Fall eines negativen Koeffizienten bilden;

- ersten und zweiten Speichern (MEM2, MEM3), die dem ersten bzw. dem zweiten Zweig angehören, von denen jeder N/2 Teilergebnisse speichern kann, zum Speichern der vom ersten und vom zweiten Addierer/Subtrahierer (SMST1, SMST2) erzielten Rechenergebnisse, wobei die ersten Speicher Teilergebnisse R(2k) speichert, die sich auf geradzahlige Zeilen einer Matrixspalte beziehen, und die zweiten Speicher Teilergebnisse R(2k+1) speichern, die sich auf ungeradzahlige Zeilen beziehen, wobei diese Teilergebnisse Komponenten eines transformierten Abtastwertvektors F(k) an der (N/2-1)-ten Indexspalte sind;

- einer ersten Adressiereinheiten (ADR2), die folgende Signale erzeugt: für die erste und die zweite Recheneinheit (ERM, ORM) erste Steuersignale (7), die die für alle Spalten festgelegte sequentielle Ordnung unter den Koeffizienten einer Spalte bestimmen; Adressen zum Lesen der Teilergebnisse in den ersten und zweiten Speichern (MEM2, MEM3), wobei diese Teilergebnisse dann als Daten zum ersten Eingang des ersten bzw. des zweiten Addierers/Subtrahierers (SMST1, SMST2) geleitet werden, und zu deren fortgeschriebenem erneutem Einspeichern in der selben Position, wobei diese Adressen eine mit der Matrixspalte sich ändernde Folge haben, derart, daß das Teilergebnis R(2k) und R(2k+1) identifiziert wird, dessen Index der Matrixzeile entspricht, die den Koeffizienten enthält, für den die erste und die zweite Recheneinheit (ERM,ORM) die Teilergebnisse erstellen; und operationswählsignale für den ersten und den zweiten Addierer/Subtrahierer (SMST1, SMST2).

2. Schaltung nach Anspruch 1, dadurch gekennzeichnet, daß für N=16 die erste Recheneinheit (ERM) folgende Einzelschaltungen umfaßt:

- einen ersten Multiplexer (MX1) und einen zweiten Multiplexer (MX2), die an einem ersten Eingang den Ausgang (3) des ersten Addierers (SOM1) und an einem zweiten Eingang den Ausgang eines ersten Registers (RG7) empfangen;

- eine erste Schiebeeinheit (SH1) und eine zweite Schiebeeinheit (SH2), die die Ausgänge des ersten bzw. des zweiten Multiplexers empfangen;

- einen dritten Addierer/Subtrahierer (SMST3), der die Ausgänge der ersten und der zweiten Schiebeeinheit zum Addieren oder Subtrahieren des Ausgangs der zweiten Schiebeeinheit (SH2) zum oder vom Ausgang der ersten Schiebeeinheit (SH1) empfängt und dessen Ausgang dem ersten Register (RG7) eingespeist ist und außerdem der Ausgang der ersten Recheneinheit (ERM) ist;

und weiterhin dadurch gekennzeichnet, daß die zweite Recheneinheit (ORM) folgende Einzelschaltungen umfaßt:

- einen dritten Multiplexer (MX3) und einen vierten Multiplexer (MX4), die an einem ersten Eingang den Ausgang (4) des ersten Subtrahierers (SOT1) empfangen und von denen der dritte Multiplexer an einem zweiten Eingang den Ausgang eines zweiten Registers (RG8) und der vierte Multiplexer an einem dritten und einem vierten Eingang die Ausgänge eines dritten Registers (RG9) und eines vierten Registers (RG10) empfängt;

- eine dritte Schiebeeinheit (SH3) und eine vierte Schiebeeinheit (SH4), die die Ausgänge des dritten bzw. des vierten Multiplexers empfangen;

- einen vierten Addierer/Subtrahierer (SMST4), der Ausgänge der vierten Schiebeeinheit und der fünften Schiebeeinheit zum Addieren oder Subtrahieren des Ausgangs der dritten Schiebeeinheit (SH3) zu oder vom Ausgang der vierten Schiebeeinheit (SH4) empfängt und dessen Ausgang das zweite, dritte und vierte Register (RG8, RG9, RG10) speist und der Ausgang der zweiten Recheneinheit (ORM) ist, wobei das erste, das zweite, das dritte und das vierte Register der vorübergehenden Speicherung der vorhergehenden Teilergebnisse dienen.

3. Schaltung nach Anspruch 2, dadurch gekennzeichnet, daß die von den ersten Adressiereinheiten (ADR2) ersten erzeugten Steuersignale (7) die folgende Aufeinanderfolge von durch die erste und die zweite Recheneinheit (ERM, ORM) durchzuführenden Operationen bewirken: für das erste Teilergebnis werden der erste, der zweite, der dritte und der vierte Multiplexer (MX1, MX2, MX3, MX4) auf den ersten Eingang gestellt, die erste, die zweite, die dritte und die vierte Schiebeeinheit (SH1, SH2, SH3, SH4) verschieben um vier, eine, null bzw. drei Stellen nach links in der Richtung von Multiplikationen mit Potenzen von zwei, der dritte und der vierte Addierer/Subtrahierer (SMST3, SMST4) bilden die Summe und das erste und das zweite Register (RG7, RG8) speichern ihre Eingangsdaten; für das zweite Teilergebnis werden der erste, der zweite, der dritte und der vierte Multiplexer auf den zweiten, den ersten, den zweiten bzw. den ersten Eingang gestellt, die erste, die zweite, die dritte und die vierte Schiebeeinheit schieben um eine, null, eine bzw. drei Stellen nach links, der dritte und der vierte Addierer/Subtrahierer bilden die Summe bzw. die Differenz und das dritte Register (RG9) speichert seine Eingangsdaten; für das dritte Teilergebnis werden der erste, der zweite, der dritte und der vierte Multiplexer auf den zweiten, den ersten, den zweiten bzw. den dritten Eingang gestellt, die erste, die zweite, die dritte und die vierte Schiebeeinheit schieben um null, fünf, null bzw. eine Stelle nach links, der dritte Addierer/Subtrahierer bildet die Summe und der vierte die Differenz, und das erste und das vierte Register (RG7, RG10) speichern ihre Eingangsdaten; für das vierte Teilergebnis werden der erste, der zweite und der vierte Multiplexer auf den ersten Eingang und der dritte Multiplexer auf den zweiten Eingang gestellt, die erste, die zweite, die dritte und die vierte Schiebeeinheit schieben um fünf, fünf, drei bzw. eine Stelle nach links, der dritte Addierer/Subtrahierer bildet die Summe und der vierte die Differenz; für das fünfte Teilergebnis werden der erste und der zweite Multiplexer auf den zweiten Eingang und der dritte und der vierte Multiplexer auf den ersten Eingang gestellt, die erste Schiebeeinheit schiebt um ein stelle nach rechts in Richtung einer Division um Potenzen von zwei, die dritte und die vierte Schiebeeinheit schieben um sechs bzw. vier Stellen nach links, der dritte und der vierte Addierer/Subtrahierer bilden die Summe und das zweite Register speichert seine Eingangsdaten; für das sechste Teilergebnis werden der erste, der zweite, der dritte und der vierte Multiplexer auf den zweiten, den ersten, den zweiten bzw. den dritten Eingang gestellt, die erste, die zweite und die vierte Schiebeeinheit schieben um eine, vier bzw. eine Stelle nach links, die dritte Schiebeeinheit schiebt um vier Stellen nach rechts, der dritte Addierer/Subtrahierer bildet die Differenz und der vierte die Summe; für das siebte Teilergebnis werden der erste, der zweite, der dritte und der vierte Multiplexer auf den zweiten, den ersten, den ersten bzw. den vierten Eingang gestellt, die erste Schiebeeinheit schiebt um eine Stelle nach rechts, die zweite und die vierte Schiebeeinheit schieben um sechs Stellen bzw. eine Stelle nach links und der dritte und der vierte Addierer/Subtrahierer bilden die Summe; für das achte Teilergebnis werden der erste, der zweite und der dritte Multiplexer auf den ersten Eingang und der vierte auf den dritten Eingang gestellt, die erste, die zweite und die dritte Schiebeeinheit schieben um fünf, fünf bzw. sechs Stellen nach links und der dritte und der vierte Addierer/Subtrahierer bildet die Summe.

4. Schaltung nach Anspruch 1, dadurch gekennzeichnet, daß für N=16 die erste Recheneinheit (ERM) und die zweite Recheneinheit (ORM) sechs bzw. acht Addierer oder Subtrahierer enthalten, die eine gleiche Anzahl von Teilergebnissen durch geeignete Einstellung ihrer beiden Eingänge erzeugen, ferner sechs bzw. acht Register, die deren Ergebnisse speichern, ein weiteres Register (RG17), das mit dem Eingang der ersten Recheneinheit (ERM) verbunden ist, und Multiplexer, die die Ausgänge der Register empfangen, wobei die von der Adressiereinheit (ADR2) erzeugten ersten Steuersignale (7) nur die Verbindungsfolge der Eingänge der Multiplexer mit ihren Ausgängen bestimmen.

5. Schaltung nach Anspruch 4, dadurch gekennzeichnet, daß die erste Recheneinheit (ERM) die folgende Verbindung zwischen den Addierern oder Subtrahierern unter Zwischenschaltung der Register realisiert: an einen zweiten Addierer (SM1) ist der Ausgang des ersten Addierers (SOM1) angelegt, um eine und um vier Stellen nach links verschoben; an einen dritten Addierer (SM2) sind die Ausgänge des ersten Addierers, um fünf Stellen nach links verschoben, und des zweiten Addierers angelegt; an einen zweiten Subtrahierer (ST1) sind die Ausgänge des zweiten Addierers, um eine Stelle nach links verschoben, und des ersten Addierers angelegt; an einen dritten Subtrahierer (ST2) sind die Ausgänge des ersten Addierers, um vier Stellen nach links verschoben, und des dritten Addierers, um eine Stelle nach links verschoben, angelegt; an einen vierten Addierer (SM3) sind die Ausgänge des ersten Addierers, um sechs Stellen nach links verschoben, und des dritten Addierers, um eine Stelle nach rechts verschoben, angelegt; an einen fünften Addierer (SM4) ist der Ausgang des dritten Addierers, um eine Stelle nach rechts verschoben, an einem seiner Eingänge angelegt; das weitere Register (RG17) empfängt den Ausgang des ersten Addierers, um sechs Stellen nach links verschoben; weiterhin dadurch gekennzeichnet, daß die zweite Recheneinheit (ORM) die folgende Verbindung zwischen den Addierern und Subtrahierern unter Zwischenschaltung der Register realisiert: an einen sechsten Addierer (SM5) und einen siebten Addierer (SM6) ist der Ausgang des ersten Subtrahierers (SOT1) angelegt, und zwar um sechs und um vier Stellen nach links verschoben bzw. um drei und um null Stellen nach links verschoben; an einen achten Addierer (SM7) sind die Ausgänge des ersten Subtrahierers, um drei Stellen nach links verschoben, und des siebten Addierers, um eine Stelle nach links verschoben, angelegt; an einen vierten Subtrahierer (ST3) sind die Ausgänge des ersten Subtrahierers (SOT1), um eine Stelle nach links verschoben, und des siebten Addierers, um drei Stellen nach links verschoben, angelegt; an einen fünften Subtrahierer (ST4) sind die Ausgänge des siebten Addierers und des achten Addierers, um eine Stelle nach links verschoben, angelegt; an einen neunten Addierer (SM8) sind die Ausgänge des ersten Subtrahierers, um sechs Stellen nach links verschoben, und des achten Addierers angelegt; an einen zehnten Addierer (SM9) sind die Ausgänge des sechsten Addierers, um vier Stellen nach rechts verschoben, und des achten Addierers, um eine Stelle nach links verschoben, angelegt; an einen elften Addierer (SM10) sind der Ausgang des ersten Subtrahierers und der Ausgang des fünften Subtrahierers, um eine Stelle nach links verschoben, angelegt; und daß die Ausgangsmultiplexer (MX5, MX6) ihre Eingänge mit ihren Ausgängen (5, 6) in der folgenden Reihenfolge verbinden: für das erste Teilergebnis, die Ausgänge des zweiten und des siebten Addierers (SM1, SM6); für das zweite Teilergebnis, die Ausgänge des zweiten Subtrahierers (ST1) und des achten Addierers (SM7); für das dritte Teilergebnis, die Ausgänge des dritten Addierers (SM2) und des fünften Subtrahierers (ST4); für das vierte Teilergebnis, die Ausgänge des weiteren Registers (RG17) und des vierten Subtrahierers (ST3); für das fünfte Teilergebnis, die Ausgänge des fünften und des sechsten Addierers (SM4, SM5); für das sechste Teilergebnis, die Ausgänge des dritten Subtrahierers (ST2) und des zehnten Addierers (SM9); für das siebte Teilergebnis, die Ausgänge des vierten und des elften Addierers (SM3, SM10); für das achte Teilergebnis, die Ausgänge des weiteren Registers (RG17) und des neunten Addierers (SM8).

6. Schaltung nach Anspruch 1, dadurch gekennzeichnet, daß für N=8 die erste Recheneinheit (ERM) folgende Einzelschaltungen umfaßt:

- einen fünften Multiplexer (MX7) und einen sechsten Multiplexer (MX8), die an einem ersten Eingang den Ausgang (4) des ersten Addierers (SOM1) und an einem zweiten Eingang den Ausgang (20) eines fünften Registers (RG27) empfangen, wobei der sechste Multiplexer an einem dritten Eingang den Ausgang (21) eines sechsten Registers (RG28), um eine Stelle nach links verschoben, empfängt und die an seinen ersten und zweiten Eingang angelegten Ausgänge um drei Stellen nach links verschoben sind;

- eine fünfte Schiebeeinheit (SH5), die den Ausgang des fünften Multiplexers (MX7) empfängt;

- einen sechsten Subtrahierer (SMST5), der den Ausgang der fünften Schiebeeinheit von dem des sechsten Multiplexers subtrahiert und dessen Ausgang (5) das fünfte und das sechste Register speist und der Ausgang der ersten Recheneinheit ist;

- einen siebten Multiplexer (MX9) und einen achten Multiplexer (MX10), die an einem ersten Eingang den Ausgang (4) des ersten Subtrahierers (SOT1) und an einem zweiten Eingang die Ausgänge (22, 23) eines siebten Registers (RG29) bzw. eines achten Register (RG30) empfangen;

- eine sechste Schiebeeinheit (SH6) und eine siebte Schiebeeinheit (SH7), die die Ausgänge des siebten Multiplexers (MX9) bzw. des achten Multiplexers (MX10) empfangen;

- einen sechsten Addierer/Subtrahierer (SMST6), der die Ausgänge der sechsten und der siebten Schiebeeinheiten zum Addieren oder Subtrahieren des Ausgangs der sechsten Schiebeeinheit mit oder von dem der siebten Schiebeeinheit empfängt, und dessen Ausgang (6) das siebte und das achte Register (RG29, RG30) speist und der Ausgang der zweiten Recheneinheit ist; wobei das fünfte, das sechste, das siebte und das achte Register der vorübergehenden Speicherung der vorherigen Teilergebnisse dienen.

7. Schaltung nach Anspruch 6, dadurch gekennzeichnet, daß die von den Adressiereinheiten (ADR2) erzeugten ersten Steuersignale (7) die folgende Aufeinanderfolge von von der ersten Recheneinheit (ERM) und der zweiten Recheneinheit (ORM) durchzuführenden Operationen bewirkt: für das erste Teilergebnis werden der fünfte, der sechste, der siebte und der achte Multiplexer (MX7, MX8, MX9, MX10) auf den ersten Eingang (3, 4) geschaltet, die fünfte, die sechste und die siebte Schiebeeinheit (SH5, SH6, SH7) schieben um null, null bzw. drei Stellen nach links, der sechste Addierer/Subtrahierer führt eine Subtraktion durch, das fünfte und das siebte Register (RG27, RG29), speichern ihre Eingangsdaten; für das zweite Teilergebnis werden der fünfte, der sechste und der siebte Multiplexer auf den zweiten Eingang und der achte Multiplexer auf den ersten Eingang gestellt, die fünfte, sechste und siebte Schiebeeinheit schieben um null, null bzw. fünf Stellen, der sechste Addierer/Subtrahierer führt eine Subtraktion durch und das sechste und das achte Register (RG28, RG30) speichern ihre Eingangsdaten; für das dritte Teilergebnis werden der fünfte, der sechste, der siebte und der achte Multiplexer auf den zweiten, den dritten, den zweiten bzw. den fünften Eingang gestellt, die fünfte, die sechste und die siebte Schiebeeinheit verschieben um null, null bzw. sechs Stellen nach links, der sechste Addierer/Subtrahierer bildet die Summe; für das vierte Teilergebnis werden der fünfte, der sechste, der siebte und der achte Multiplexer auf den zweiten, den dritten, den zweiten bzw. den zweiten Eingang gestellt, die fünfte, die sechste und die siebte Schiebeeinheit verschieben um null, drei bzw. eine Stelle nach links, der sechste Addierer/Subtrahierer bildet die Summe und das siebte Register speichert seine Eingangsdaten; für das fünfte Teilergebnis werden der fünfte, der sechste, der siebte und der achte Multiplexer auf den ersten, den dritten, den ersten bzw. den ersten Eingang gestellt, die fünfte, die sechste und die siebte Schiebeeinheit verschieben um sechs, eine bzw. sieben Stellen nach links und der sechste Addierer/Subtrahierer führt eine Subtraktion durch.

8. Schaltung nach Anspruch 1, dadurch gekennzeichnet, daß für N=8 die erste Recheneiheit (ERM) und die zweite Recheneineit (ORM) jeweils vier bzw. fünf Addierer oder Subtrahierer enthalten, die eine gleiche Zahl von Teilergebnissen durch geeignete Einstellungen ihrer beiden Eingänge erzeugen, weiterhin vier bzw. fünf Register, die deren Ergebnisse speichern, und einen Ausgangsmultiplexer, der die Ausgänge der Register empfängt, wobei die von der Adressiereinheit (ADR2) erzeugten ersten Steuersignale (7) nur die Verbindungsfolge zwischen den Eingängen und den Ausgängen der Multiplexer bestimmt.

9. Schaltung nach Anspruch 8, dadurch gekennzeichnet, daß die erste Recheneinheit (ERM) die folgenden Verbindungen zwischen den Addiereren oder Subtrahierern unter Zwischenschaltung der Register realisiert: an einen siebten Subtrahierer (ST6) ist der Ausgang des ersten Addierers (SOM1), um drei Stellen nach links verschoben, als einer der Eingänge angelegt; an einen achten Subtrahierer (ST7) ist der Ausgang des siebten Subtrahierers, an einem seiner Eingänge um drei Stellen verschoben, angelegt; an einen neunten Subtrahierer (ST8) ist der Ausgang des siebten Subtrahierers und der Ausgang des achten Subtrahierers, um eine Stelle nach links verschoben, angelegt; an einen zehnten Subtrahierer (ST9) sind die Ausgänge des ersten Addierers, um sechs Stellen nach links verschoben, und des neunten Subtrahierers, um eine Stelle nach links verschoben, angelegt; und weiterhin dadurch gekennzeichnet, daß die zweite Recheneinheit (ORM) die folgenden Verbindungen zwischen den Addierern oder Subtrahierern unter Zwischenschaltung der Register realisiert: an einen elften Subtrahierer (ST10) und einen zwölften Subtrahierer (ST11) ist der Ausgang des ersten Subtrahierers (SOT1), um drei, null, sieben bzw. eine Stelle nach links verschoben, angelegt; an einen dreizehnten Subtrahierer (ST12) sind der Ausgang des ersten Addierers, um fünf Stellen nach links verschoben, und der Ausgang des elften Subtrahierers angelegt; an einen zwölften Addierer (SM12) sind der Ausgang des ersten Subtrahierers, um sechs Stellen nach links verschoben, und der Ausgang des elften Subtrahierers angelegt; an einen dreizehnten Addierer (SM13) sind der Ausgang des elften Subtrahierers, um drei Stellen nach links verschoben, und der Ausgang des dreizehnten Subtrahierers, um eine Stelle nach links verschoben, angelegt; wobei Ausgangsmultiplexer (MX11, MX12) ihre Eingänge mit ihren Ausgängen (5, 6) in der folgenden Reihenfolge verbinden: für das erste Teilergebnis die Ausgänge des achten und des dreizehnten Subtrahierers (ST7, ST12); für das zweite Teilergebnis die Ausgänge des neunten Subtrahierers (ST8) und des zwölften Addierers (SM12); für das dritte Teilergebnis die Ausgänge des neunten Subtrahierers (ST8) und des dreizehnten Addierers (SM13); und für das vierte Teilergebnis die Ausgänge des zehnten und des zwölften Subtrahierers (ST9, ST11).

10. Schaltung nach einem der Ansprüche 1 bis 9, dadurch gekennzeichnet, daß die erste Adressiereinheit (ADR2) nach außen zu Beginn der sich auf auf die (N/2 - 1)-te Indexspalte beziehenden Operationen ein Daten-Bereit-Signal (DRT) abgibt, auf dessen Grundlage die Teilergebnisse R(k) an den Ausgängen des ersten und des zweiten Addierers/Subtrahierers (SMST1, SMST2) an Ausgängen (12, 13) als Komponenten eines transformierten F(k)-Abtastwertvektors zu erhalten sind.

11. Schaltung nach einem der Ansprüche 1 bis 10, dadurch gekennzeichnet, daß die erste Adressiereinheit (ADR2) am Ende der sich auf die (N/2 - 1)-te Indexspalte beziehenden Kalkulationen Adressen an den ersten und an den zweiten Speicher (MEM2, MEM3) für das aufeinanderfolgende Lesen und Abgeben an die Ausgänge von R(k)-Teilergebnissen, die dort gespeichert sind, als Komponenten eines transformierten F(k)-Abtastwertvektors liefert.

12. Schaltung nach einem der Ansprüche 1 bis 11, dadurch gekennzeichnet, daß die Daten an den Ausgängen des ersten Addierers (SOM1), des ersten Subtrahierers (SOT1), der ersten und der zweiten Recheneinheit (ERM, ORM) und des ersten und des zweiten Speichers (MEM2, MEM3) durch Register (RG1, ..., RG6) synchronisiert sind.

13. Schaltung nach einem der Ansprüche 2, 3, 6 oder 7, dadurch gekennzeichnet, daß die Schiebeeinheiten (SH1, ..., SH7) aus Faß-Schiebern (barrel shifters) bestehen.

14. Schaltung zum Berechnen der zweidimensionalen diskreten Cosinus-Transformation unter Verwendung von Schaltungen nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, daß sie eine erste dieser Schaltungen (DCT1), der ein matrixstrukturierter Zwischenspeicher (MEM4) und eine zweite solche Schaltung (DCT2) folgen, und zweite Adressiereinheiten (ADR3) für den Zwischenspeicher enthält, die das Schreiben von N Vektoren transformierter F(k)-Abtastwerte bestimmen, welcher von der ersten Schaltung berechnet worden sind, und das Lesen in einer zum Schreiben orthogonalen Richtung von N Vektoren von zu transformierenden f(j)-Abtastwerten, die jeweils aus der (k - n)-ten Komponente der F(k) Vektoren im Zwischenspeicher bestehen, zum Weitergeben an die zweite Schaltung (DCT2), bestimmen.