DE3783056T2

DE3783056T2 - Geraet zur kosinustransformation eines abgetasteten digitalen signals.

Info

Publication number: DE3783056T2
Application number: DE8787400278T
Authority: DE
Inventors: Pierre Duhamel
Original assignee: France Telecom SA
Current assignee: Orange SA
Priority date: 1986-02-06
Filing date: 1987-02-06
Publication date: 1993-04-15
Anticipated expiration: 2007-02-07
Also published as: US4797847A; EP0237382A1; FR2593948A1; EP0237382B1; FR2593948B1; DE3783056D1; JPS62235622A

Description

Die Erfindung betrifft die Verarbeitung von abgetasteten digitalen Signalen ZurErzeugung einer diskreten Kosinustransformierten (TCD oder DCT).
Man benutzt seit langem die diskreten, schnellen Transformationen, um die zeitliche oder räumliche Kompression von zu übertragenden oder zu speichernden Daten zu bewerkstelligen. Man hat insbesondere die einfachen Transformationen benutzt, wie zum Beispiel die Walsh-Hadamard- Transformation, welche den Vorteil aufweisen, nur einfache Schaltungen zu benutzen, aber dafür nur einen geringen Kompressionsfaktor liefern.
Es macht sich zur Zeit der Bedarf bemerkbar, über schnelle Transformationen zu verfügen, welche es gestatten, erhöhte Kompressionsfaktoren zu erreichen, und dennoch nur Schaltungen von akzeptabler Komplexität erfordern, und welche in Echtzeit arbeiten können.
Insbesondere wurde die Benutzung der TCD vorgeschlagen, im speziellen für die Videotextsysteme, da diese eine beträchtliche Erhöhung des Kompressionsfaktors gestattet. Aber selbst für Transformationen geringer Länge ist es schwierig, integrierte Schaltungen zu verwirklichen, welche in Echtzeit mit den erforderlichen Abtastfrequenzen arbeiten können. Selbst wenn man die neuesten vorgeschlagenen Algorithem benutzt, welche die Komplexität der Rechnung reduzieren. In der Praxis kann man gerade eben Abtastfrequenzen von 10 MHz für Transformationen der Länge acht erreichen.
Eine Vorrichtung zur Erzeugung der diskreten Kosinustransformation eines Signals ist gleichfalls bekannt (Druckschrift US-A-4 385 363). Diese Vorrichtung benutzt Grundschaltungen, welche die Summe und die Differenz der zwei Eingänge liefern. Diese Vorrichtung weist aber eine pipelineartige Anordnung auf mehreren Ebenen auf, von denen jede Addierer und Multiplizierer umfaßt. Sie implementiert den Algorithmus von Chen und Fralick, und diese Konzeption führt zu einer komplexen Architektur.
Das Dokument in IEEE Transactions on Acoustics, Speech and Signal Processing, vol. ASSP-28, Nr. 1, Februar 1980, Seiten 27-34, IEEE New York, US, J. Makhoul: "A fast cosine transform in one and two dimensions" ließ schließlich ein Verarbeitungsverfahren für abgetastete digitale Signale zur Erzeugung einer diskreten, schnellen Kosinustransformierten (TCD) bekannt werden.
Die Erfindung zielt darauf ab, eine Vorrichtung zur Verarbeitung eines abgetasteten Signals zu liefern, welche geeignet ist, die diskrete Kosinustransformation des Signals zu liefern und einen einfacheren Aufbau aufweist, als die bekannten Vorrichtungen, und dür einen Algorithmus benutzt, der erhalten wird, wenn eine teilweise Äquivalenz zwischen TCD und zyklischer Faltung sichtbar gemacht wird, welche nicht mehr Multiplikationen als die Berechnung einer zyklischen Faltung der gleichen Länge erfordert.
Zu diesem Zweck schlägt die Erfindung insbesondere eine Vorrichtung zur Bestimmung der diskreten Kosinustransformierten Xk eines Signals gemäß dem Anspruch 1 vor. Sie schlägt gleichfalls eine Vorrichtung gemäß Anspruch 2 vor. In diesem zweiten Fall erscheinen die Transformationskoeffizienten X auf natürliche Art und Weise während der Faltungsberechnung, selbst vor dem Endresultat dieser letzteren. Es wird also nutzlos, die Transformierte TNE&supmin;¹ vollständig für die Mehrzahl der Koeffizienten X zu verwirklichen.
Die Erfindung wird durch die Lektüre der folgenden Beschreibung von bestimmten Ausführungsarten der Erfindung leichter verständlich werden, welche beispielhaft und nicht einschränkend ist. Die Beschreibung bezieht sich auf die beiliegenden Zeichnungen, in welchen:
Fig. 1 ist ein Prinzipschaltbild, welches die Elemente zeigt, die einer zyklischen Faltungseinheit, welche einen herkömmlichen Aufbau aufweisen kann, anzufügen sind, um eine die Kosinustransformation liefernde Vorrichtung zu verwirklichen;
Fig. 2 ist ein Prinzipschaltbild, welches die übliche Anwendung einer Faltungseinheit ausgehend von TNE von Signalabtastwerten zeigt und von der erzeugten ten oder gespeicherten Folge;
Fig. 3 zeigt schematisch die in die TNE&supmin;¹ eingehenden Vereinfachungen, welche es gestatten, die TCD der Abtastwerte eines Signals vor der vollständigen Berechnung der Faltung zu erhalten;
Fig. 4 zeigt ähnlich Fig. 2 eine Variante der Verwirklichung, welche die Blöcke "Kodierung" und "Basiswechsel" zeigt, welche eventuell zur Vereinfachung der in die TNE eingehende Modulo-Arithmetik notwendig ist.
Vor Beschreibung der erfindungsgemäßen Vorrichtungen ist es notwendig, die mathematische Entwicklung anzugeben, welche die Äquivalenz zwischen TCD und zyklischer Faltung, welche die Architektur der Vorrichtungen rechtfertigt, sichtbar macht.
Zwei aufeinanderfolgende Variablenumwandlungen gestatten es vom klassischen Ausdruck der TCD (Formel 1 oben) zu einer zyklischen Faltung der Form:
überzugehen.
Die erste Variablenumwandlung zielt darauf ab, im Kosinusterm den Wert 4i+1, der einfacher erzeugt wird, als die Größe 2i+1, sichtbar zu machen. Sie besteht darin, in der Formel (1) für x die Variable x' zu substituieren, so daß:
x' = x2i
x'N-i+1 = x2i+1 für x'O' ..., x'N/2-1
Diese Variablenumwandlung teilt die Werte x' in zwei Gruppen ein, wobei eine den geraden Werten x2i von x entspricht und die andere den ungeraden Werten x2i+1. Man erhält also:
Eine zweite Variablenumwandlung wird es daran anschließend gestatten, in die Definition der Transformation die Differenz der zwei Indices statt eines Produkts eingehen zu lassen. Man gelangt so zur klassischen Formulierung (2) der zyklischen Faltung mit ihrem Term hn-i.
Um dieses Resultat zu erhalten, wird auf die Entsprechung zwischen der Gesamtheit der ganzen Zahlen kongruent mit 1, Modulo 4 und kleiner als 2n+2 und der Gesamtheit der ganzen Zahlen kleiner als 2n hingewiesen. Man kann tatsächlich schreiben:
4i+1 = 5ui mod 2n+2 (4)
für i = O, 1, ..., 2n-1.
Man wird im folgenden, um die Schreibung der Gleichungen zu vereinfachen, die Notation:
4i+1 = < 5ui> 2n+2
benutzen.
Die Formel (3) wird dadurch:
In dieser Formel kann der Faktor x'i unter Berücksichtigung der durch die Formel (4) angezeigten Äguivalenz geschrieben werden:
und durch Setzen von:
findet man:
Um die Äquivalenz zwischen TCD und zyklischer Faltung offensichtlicher werden zu lassen, wird jetzt eine polynomiale Notierung benutzt werden, indem jeder der Koeffizienten Xk als ein Koeffizient eines Polynoms einer stummen Variablen z betrachtet wird. Es ist bekannt, daß eine Variable als "stumm" bezeichnet wird, wenn sie keiner wirklichen Variablen entspricht und nur zur Bequemlichkeit der Rechnung eingeführt ist. Man definiert zwei Polynome U und V, welche N Terme enthalten, wobei jeder Term einer Potenz von z zwischen 0 und N-1 entspricht:
Xk wird also der konstante Term des Polynomprodukts von U(z&supmin;¹) und von Vk(z) sein. Xk ist mit anderen Worten der konstante Term (entspricht z&sup0;) des Produkts:
U(z&supmin;¹) . Vk(z) mod (zN-1) (10)
Man kann zeigen, daß alle ungeraden Terme, d.h. von der Form V 2k'+1 (z) zu einer gleichen Polynomfamilie gehören, wobei die einen um eine Potenz von z modulo zN-1 gegen die anderen verschoben sind. Das leitet sich aus den vorhergehenden Rechnungen ab, da der Ausdruck (1) symmetrisch in i und k ist, wenn er für die ungeraden Werte k=2k'+1 geschrieben ist.
Wenn man V&sub1; kennt, kann man also alle anderen ungeraden Werte V2k'+1 ableiten.
Um die Rechnungen zu ermöglichen, wird man jetzt die Folge:
eingeführen, in der n die gleiche Potenz von 2 ist, wie diejenige, welche die notwendige Länge N festlegt, und j ein von i unterschiedlicher Inkrementierungsindex ist.
Diese Folge wi kann ein für allemal berechnet werden und in einer Vorrichtung zur Bestimmung der TCD gespeichert werden.
Man wird jetzt sehen, daß die TCD durch zyklische Faltung der Folge (xi) der Signalabtastwerte mit der gespeicherten Folge (wi) und einige zusätzliche Additionen erhalten werden kann.
Dafür genügt es zu bemerken, daß das Polynom W(z), in dem die w die Koeffizienten der aufeinanderfolgenden Potenzen der stummen Variablen z sind, gegeben ist durch:
und alle Vk von z durch Addition der verschobenen, aufeinanderfolgenden Versionen von W(z) erhalten werden können, da:
2V&sub1;(z) = W(N) (z) - zN/2 . W(N) (z) mod (zN-1) (13)
Das Polynom ist in dem in Fig. 1 dargestellten Fall einer Transformation der Länge N+8 insbesondere das folgende:
2X&sub1; + 2X&sub5; z + 2X&sub7; z² + 2X&sub3; z³ = yo - y&sub4; + (y&sub1; - y&sub5;)z+ (y&sub2; - y&sub6;) z² + (y&sub3; - y&sub7;) z³ .
Man hat nun aber weiter oben angedeutet, daß alle ungeraden Terme V2k'+1 zu einer gleichen Familie gehören und sich die einen von den anderen durch Verschiebung ergeben. Alle ungeraden Terme V2k'+1 leiten sich also von V&sub1; (z) durch Verschiebung ab. Genauso leiten sich alle geraden Terme V2(2k'+1) (z) von V&sub2; durch Verschiebung ab. Tatsächlich kann man die Ähnlichkeit zwischen dem Ausdruck 2V&sub1;(z), der durch die Formel gegeben ist, und demjenigen von 2W(N/2) (z):
2W(N/2) (z) = W (N) (z)+zN/2 .W(N) (z) mod (zN-1) (14)
bemerken, und man kann daraus die zu 2 mod 4 kongruenten Terme der Kosinustransformation herausziehen:
2V&sub2;(z) = W(N/2)-zN/4.W(N/2) (z) (15)
und alle V2(2k'+1) (z) durch aufeinanderfolgende Verschiebung von V&sub2;.
Durch Iteration wird man also aufeinanderfolgend:
V2k'+1(z)
V2(2k'+1) (z)
V2l(2k'+1) (z)
VN/2(z)
VN(z) = V&sub0;
erhalten, d.h. für N = 8 aufeinanderfolgend:
V&sub1;, V&sub3;, V&sub5;, V&sub7;
V&sub2;, V&sub6;
V&sub4;
V&sub0;
Ausgedrückt durch eine andere Form, kann man Vk(z) in der Form:
ausdrücken, in der αl eine stumme Variable ist.
Die Formel (16) macht sichtbar, daß alle Vk durch die Summe der verschobenen Versionen im polynomialen Sinne (d.h. daß die einen von den anderen durch Multiplikation mit z hergeleitet werden) gebildet sind.
Die bloße Kenntnis des Polynomprodukts Y(z), welche durch die in Fig. 2 für den Spezialfall einer Größe, welche gleich 8 ist, erscheinenden Term yo, ..., y&sub7; gebildet ist:
gestattet es also, Xk den konstanten Term (d.h. dem der Potenz 0 von z entsprechenden Faktor) des Produkts U(z&supmin;¹) .W(z) wiederzufinden, da unter Berücksichtigung der Formel (16):
und gemäß (17):
Nun ist aber das Polynomprodukt U(z&supmin;¹) .W(z) eine andere Schreibweise der zyklischen Faltung von {ui} durch
welche man mit der klassischen Formel (2) der zyklischen Faltung vergleichen kann.
Zusammenfassend sieht man, daß die TCD erhalten werden kann, indem man aufeinanderfolgend ausführt:
- eine klassische zyklische Faltungsoperation, welche die Eingangsabtastwerte x und die Werte w, die ein für allemal berechnet und abgespeichert werden können, eingehen läßt für jeden Wert von N;
- die durch die Gleichungen (15) und (16) dargestellten Operationen, welche sich auf Additionen beschränken und in der Form von in die Fourier-Transformationen eingehenden "Schmetterlingen" dargestellt werden können, wobei a und b die Eingangswerte sind:
Fig. 1 zeigt beispielhaft einen möglichen Aufbau einer Kosinustransformationsvorrichtung, welche eine zyklische Faltungseinheit benutzt, die irgendeinen bekannten klassischen Aufbau aufweist. Es kann sich insbesondere um eine zyklische Faltungseinheit des systolischen Typs handelt, wie er zum Beispiel im Artikel von H. Barral und anderen "Circuits for digital signal processing", Proceedings of ICASSP 84, Paper No. 44-9 beschrieben ist, vervollständigt durch Anschlüsse um sie zyklisch zu machen. Die dargestellte Faltungseinheit 10 ist vorgesehen, um eine Kosinustransformation der Länge N=8 zu verwirklichen. Sie umfaßt 8 Eingänge, welche dazu bestimmt sind, die Abtastwert x&sub0;, ..., x&sub7; aufzunehmen und acht Eingänge w&sub0;, ... w&sub7;, welche dazu bestimmt sind, die in einem Festspeicher 12 gespeicherten Werte w aufzunehmen. Die Ausgangswerte yo, ..., y&sub7;, die durch die Faltungseinheit geliefert werden, sind jene, die durch die obige Formel (19) gegeben sind. Diese Werte müssen durch Operatoren kombiniert werden, welche sich auf die Additions- oder Subtraktionsoperationen beschränken. Eine erste Gruppe von Operatoren 14 des Typs "Schmetterling", welche dem obigen Algorithmus (13) entspricht, liefert direkt das Doppelte der Werte X&sub1;, X&sub5;, X&sub7; und X&sub3; (ungerade Terme). Eine zweite Gruppe 16, die durch zwei den vier Operatoren 14 identische Operatoren gebildet wird, liefert ausgehend von den additiven Ausgängen der Operatoren 14 den Quadrupel des Wertes von X&sub2; und von X&sub6;. Schließlich liefert ein letzter Operator 18 den Oktupel des Wertes von X&sub0; und X&sub4;.
Das Vorhandensein einer Äquivalenz zwischen TCD und zyklischer Faltung gestattet es, die multiplikative Komplexität der TCD der Länge 2n, d.h. die minimale Zahl der für eine Berechnung einer TCD der Länge 2n notwendigen Multiplikationen zu berechnen. Da der Übergang von der Faltung zur TCD tatsächlich keine Multiplikation erfordert, weisen die TCD und die Faltung die gleiche multiplikative Komplexität auf:
u(Falt.2n) = 2n+1 - n - 1
Darüber hinaus ist zu beachten, daß eine der Multiplikationen trivial ist, d.h. in einer Multiplikation mit einem Faktor, der der Gesamtheit der Rationalzahligen angehört, besteht. Daraus folgt:
u(TCD 2n) = 2n+1 - n -2.
Im weiter oben gewählten Beispiel einer Länge N = 8 = 2³ wird es notwendig sein, 2&sup4; -3 -2 = 11 Multiplikationen durchzuführen.
Die gegenwärtigen aktuellen Technologien gestatten es, eine Multiplikation mit einem Arbeitstakt von 10 MHz durchzuführen. Wenn man diesen gleichen Arbeitstakt in Schaltungen verwirklichen will, um zum Beispiel auf Erfordernisse der Fotovideotextsysteme zu antworten, wird es notwendig sein, in die Schaltung wenigstens zwei Multiplikationen zu integrieren und häufig mehr, wegen des Mangels an Zuverlässigkeit der produkte.
Für zwölf Bit-Eingangsworte kann man mit einer einzigen, vollständigen Faltungseinheit der oben beschriebenen Gattung eine Geschwindigkeit in der Größenordnung von 300 kHz für Niveaus mit zwölf Binärelementen am Eingang erreichen.
In der in Fig. 2 gezeigten Ausführungsform benutzt die Vorrichtung einen Ganzzahltransformator 20. Die Werte (Xn) werden auf den Eingang eines Ganzzahltransformators oder TNE angelegt, welcher eine Folge (Ak):
liefert, wobei α eine positive N-te Wurzel der Einheit Modulo M ist.
Die Vorrichtung umfaßt auch einen Speicher 22, in welchem die Ganzzahltransformierten (Bk) der Folge (wn) des Werts w gespeichert sind. Die Werte Bk werden ein für allemal durch die Formel
berechnet.
Die Ganzzahltransformierten werden auf einen Multiplikator Modulo M 24 angewandt, welcher die Ganzzahltransformierte der Ergebnisfolge (yn) liefert, welche mit Hilfe eines Invers-Ganzzahltransformators oder TNE&supmin;¹ 26 erhalten wird.
Indem man N und M zweckmäßig wählt, kann man einen einfachen Wert von α haben. Man kann insbesondere einen Wert von α, der einer Potenz von 2 gleich ist, nehmen. In diesem Falle umfassen die Transformatoren TNE und TNE&supmin;¹ keine Multiplikation, sondern einzig Verschiebungen, was die materielle Verwirklichung der Schaltung vereinfacht.
Darüber hinaus gestattet die Benutzung von Ganzzahltransformatoren eine zusätzliche Vereinfachung, wenn man berücksichtigt, daß die Reduktionen von Y(z) =Σyn . zn Modulo (die zyklotomischen Polynome) als Zwischenvariablen innerhalb des TNE Algorithmus eingehen. Man kann die Berechnung von TNE&supmin;¹, welche in Fig. 2 eingeht, vor seinem Ende unterbrechen.
Fig. 3 ist ein Graph einer Kosinustransformations-Bestimmungsvorrichtung, welche den vereinfachten Algorithmus für eine Länge N = 8 benutzt. Auf dem Graphen erscheinen die Schmetterling-Operatorengruppen 28, 30, 32 und 34, welche den gleichen Aufbau wie die in Fig. 1 benutzten aufweisen. Die in Fig. 1 benutzten Operatoren jedoch sind gewöhnliche Operatoren, während die von Fig. 3 das Resultat Modulo M liefern, und von der in der Anmeldung FR 84 14 624 beschriebenen Gattung sein können. Die Multiplikatoren B&sub0; bis B&sub7; empfangen einerseits die durch die Transformatoren 28 bis 30 ausgehend von den Werten X&sub0;, . .., X&sub7; gelieferte Folge von Werten, und andererseits die Werte B&sub0;, ..., B&sub7;, TNE der entsprechenden Werte w. Diese Werte B&sub0;, ..., B7 können durch einen Festspeicher geliefert werden oder ausgehend von Werten w durch die Multiplikatoren selbst bestimmt werden.
Der Transformator von Fig. 3 bietet den Vorteil, nur eine allgemeine Multiplikation (Modulo M) pro Punkt zu erfordern. Daraus ergibt sich, daß die Schaltungen derart verwirklicht werden können, daß sie mit einer Abtastgeschwindigkeit, welche der Geschwindigkeit des Mutliplikatorarbeitstakts gleichkommt, arbeiten können, welche mit den zur Zeit verfügbaren Technologien 10 MHz sein kann. Durch Benutzung von Schaltplänen spezieller Multiplikatoren, wie sie zum Beispiel in Fig. II der Anmeldung FR 84 14 624 gezeigt sind, kann man die Geschwindigkeit noch vergrößern.
Man kann Vorrichtungen aufbauen, welche denen von Fig. 3 ähnlich sind, aber anderen Werten von N entsprechen. Es ist auf alle Fälle besonders interessant, besondere Werte von M zu nehmen, welche sich in einer Vereinfachung der Architektur auswirken. Das ist insbesondere der Fall, wenn man für M eine Fermat-Zahl 22 + 1, eine Pseudo- Fermat-Zahl 22q + 1 oder eine Zahl des Typs M = 22 - 2q + 1 annimmt. Zum Beispiel ist für eine Zahl des letzten Typs mit q=12, a=2 jede Multiplikation mit einer Potenz von α lediglich aus Rotationen, Komplementierungen und eventuell einer Addition zusammengesetzt.
In einer Variante der erfindungsgemäßen Ausführungsform wird die Ganzzahltransformation durch Benutzung eines Basiswechsels und einer Kodierung der in der Patentanmeldung FR 84 14 624 (Duhamel und Hollmann) beschriebenen Typs verwirklicht. In diesem Fall kann sich das allgemeine Schema der TCD auf das in Fig. 4 Gegebene beschränken.
Die Vorrichtung von Fig. 4 umfaßt vor dem Ganzzahltransformators 20 eine Kodierungs- und Basiswechselschaltung 36. Die auf den Multiplikator 24 angewandte Folge B wird ebenfalls durch Kodierung, Basiswechsel und TNE erhalten. Die Ausgangsfolge des Multiplikators 24 muß nicht einer vollständigen inversen TNE unterworfen werden, da die Reduzierungen von Y(z) als Zwischenvariable eingehen. Die Berechnung wird in diesem Stadium angehalten, was es gestattet, den Transformator TNE&supmin;¹ 38 zu vereinfachen. Die erhaltenen Resultate werden einer Dekodierung und einer Rückkehr zur Anfangsbasis in einer Schaltung 40, welche die Folge (Xk) liefert, unterworfen.
Die Bausteine 20, 24 und 38 von Fig. 4 können durch die Anordnung aus durchgezogenen Strichen von Fig. 3 gebildet sein, welche normalerweise durch die gestrichelten Bauteile vervollständig werden müßten. Die Eingangswerte Xi werden auf diese Anordnung nach Kodierung bei 36 angewandt, und man erhält auf dem Ausgang die kodierten Werte Nyi; dieser gestrichelte Abschnitt ist nicht notwendig, und es sind die Xi, welche auf den Dekoder 40 gelegt werden.
Die Gesamtheit der Schaltung von Fig. 3 (darin auch den gestrichelten Bereich eingeschlossen) kann eine Faltungseinheit 10 bilden, welche in der Vorrichtung von Fig. 1 benutzbar ist.
Die Anordnungen der oben erwähnten Faltungseinheit sind nicht die einzig möglichen. Man kann insbesondere eine Faltungseinheit benutzen, welche eine verteilte Arithmetik gebrauchende Schaltungen benutzt, wie jene, welche in "Digital Filter Structures Described by Distributed Arithmetic", C. Sydney Burrus, IEEE Transactions on circuits and systems, cas. 24, Nr. 12, Dezember 77, Seiten 674-680 und in "A Prime Factor FTT Algorithm Using Distributed Arithmetic" von Shune Chu et al, IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP-30, Nr. 2, April 82, Seiten 217-226 beschrieben ist.

Claims

1. Vorrichtung zur Bestimmung der diskreten Kosinustransformierten Xk eines durch N digitale Abtastwerte x&sub0;, ...., xi, ... xN-1 dargestellten Signals x, wobei N eine Potenz 2n von 2 ist:

dadurch gekennzeichnet, daß sie eine Faltungseinheit (10) zwischen den Abtastwerten xi und einer gespeicherten Folge von Abtastwerten wi(N) :

umfaßt, und daß sie darüber hinaus eine Gesamtheit in mehrere Gruppen aufgeteilter elementarer, identischer Schaltungen (14,16,18) umfaßt, von denen jede zwei Eingänge und zwei Ausgänge aufweist, deren einer die Summe und deren anderer die Differenz der zwei Eingänge liefert, wobei die elementaren Schaltungen der ersten Gruppe (14) auf ihren zwei Eingängen die Abtastwerte des Faltungsprodukts der durch N/2 untereinander getrennten Indices empfangen und direkt die ungeraden Werte (X1, X3, ...) liefern, während die Schaltungen der folgenden Gruppe durch Kombination der Summen die geraden Werte (X0, ..., X8) aufeinanderfolgend auf ihren Subtraktionsausgängen liefern.

2. Vorrichtung zur Bestimmung der diskreten Kosinustransformierten Xk eines durch N digitale Abtastwerte x&sub0;, ...., xi, ... xN-1 dargestellten Signals x, wobei N eine Potenz 2n von 2 ist:

dadurch gekennzeichnet, daß sie umfaßt:

- Mittel (20), um die Abtastwerte xi einer Ganzzahltransformation (TNE) zu unterziehen und eine Folge Ak zu liefern:

wobei α eine Konstante ist, die gleich einer positiven N-ten Wurzel der Einheit Modulo M ist,

- Mittel zum Abspeichern einer Folge Bk, welche die TNE einer gespeicherten Folge von Abtastwerten wi (N) darstellt, wobei diese Folge die Form:

aufweist, und

- Mittel, um ein Produkt Modulo M (M ist eine ganze Zahl, und α ist eine positive N-te Wurzel von M) der Folge Ak und der Folge Bk zu bilden,

- wobei die TNE-Mittel eine Gesamtheit von in verschiedene aufeinanderfolgende Gruppen (28,30) eingeteilten, elementaren, identischen Schaltungen umfassen, wobei jede elementare Schaltung zwei Eingänge und zwei Ausgänge aufweist, deren einer die Summe und deren anderer die Differenz der beiden Eingänge liefert, die N/2 Elementarschaltungen der ersten Gruppe auf ihren Eingängen die Abtastwerte mit Indices, die durch einen Abstand von N/2 getrennt sind, empfangen und auf ihren subtraktiven Ausgängen die TNE Ak ungerader Ordnung liefern und auf ihren additiven Ausgängen Daten liefern, welche auf die Eingänge der folgenden Gruppe angelegt werden.