DE69227679T2

DE69227679T2 - Verfahren und Vorrichtung für die Transformation von Signalen aus einem Frequenzbereich im Zeitbereich

Info

Publication number: DE69227679T2
Application number: DE1992627679
Authority: DE
Inventors: Kevin Douglas Bishopston Bristol Bs7 8Hh Dewar; Anthony Mark Yate Bristol Bs17 5Tf Jones; Martin William Dursley Gloucestershire Gl11 6Bd Sotheran
Original assignee: Discovision Associates
Current assignee: Discovision Associates
Priority date: 1992-06-26
Filing date: 1992-06-26
Publication date: 1999-07-29
Anticipated expiration: 2012-06-27
Also published as: DE69227679D1; SG71043A1; EP0871133A1; SG71042A1

Description

Diese Erfindung bezieht sich auf ein Verfahren für die Transformation von Signalen von einer Frequenz- in eine Zeitdarstellung, sowie auf eine digitale Schaltungsanordnung zur Durchführung der Transformation.
Es ist ein allgemeines Ziel auf dem Gebiet der Telekommunikation, sowohl den Informationsinhalt als auch die Übertragungsgeschwindigkeit zu erhöhen. Jedes Kommunikationsmedium erzwingt jedoch eine Begrenzung der Übertragungsgeschwindigkeit, wie die Hardware auf der Übertragungs- und Empfangsseite, welche die übertragenden Signale verarbeiten muß. Ein Telegraphendraht ist zum Beispiel typisch für ein wesentlich schnelleres Medium zur Übertragung von Information als es die Post ist, auch wenn das Schreiben und Lesen eines gesendeten Dokuments schneller sein könnte, als es in einen Telegraphentaster zu tippen.
Das Verfahren zum Codieren von übertragenen Informationen begrenzt ebenfalls die Geschwindigkeit, mit welcher die Informationen befördert werden können. Eine lang gefaßte Telegraphennachricht wird zum Beispiel längere Zeit zur Übertragung in Anspruch nehmen, als eine knapp gefaßte Nachricht mit dem gleichen Informationsinhalt. Die größte Übertragungs- und Aufnahmegeschwindigkeit kann daher durch eine möglichst weitgehende Kompression der zu übertragenden Daten erzielt werden, und dann unter Verwendung eines Hochgeschwindigkeitsübertragungsmediums, um die Daten an beiden Enden so schnell wie möglich zu verarbeiten, was häufig die Reduzierung oder Beseitigung von "Flaschenhälsen" im System bedeutet.
Eine Anwendung, bei der es wesentlich ist, eine Hochgeschwindigkeitsübertragung von großen Datenmengen bereitzustellen, liegt im Gebiet des digitalen Fernsehens. Während herkömmliche Televisionssysteme analoge Radiosignale und elektrische Signale verwenden, um die Leuchtdichte bzw. Helligkeit und Farbe des Bildelements ("Pixels") in auf einem Fernsehbildschirm angezeigten Linien zu steuern, erzeugt ein Übertragungssystem für digitales Fernsehen eine digitale Darstellung eines Bildes durch Konvertierung analoger Signale in binäre "Zahlen", welche den Helligkeits- und Farbwerten für die Pixel entsprechen. Moderne Digitalcodierungs-Schemen und -Hardwarestrukturen ermöglichen üblicherweise wesentlich höhere Informationsübertragungsraten im Vergleich zu herkömmlichen analogen Übertragungssystemen. Digitale Televisionen sind somit in der Lage, eine wesentlich höhere Auflösung und wesentlich lebensechtere Abbildungen herzustellen, als ihre herkömmlichen analogen Gegenstücke. Es wird erwartet, daß digitale Fernsehsysteme, u. a. das sogenannte High-Definition TV-System (HDTV), die herkömmliche analoge Fernsehtechnologie in der industrialisierten Welt innerhalb der nächsten zehn Jahre weitgehend ersetzen wird. Die Umwandlung von einer analogen zur digitalen Bildsynthese wird daher sowohl für die Übertragung als auch die Speicherung ähnlich sein, wie die Umsetzung von analogen Audioaufzeichnungen auf die nun allgegenwärtigen Compactdiscs (CD's).
Um die allgemeine Nutzbarkeit der digitalen Bildsynthesetechnologie zu erhöhen, wurden standardisierte Verfahren für die Codierung und Decodierung digitaler Abbildungen aufgegriffen. Eines dieser standardisierten Verfahren ist als der "JPEG" Standard bekannt und wird für ruhende Bilder verwendet. Für bewegte Bilder gibt es gegenwärtig zwei Standards - MPEG und H.261 -, wobei beide JPEG-artige Prozeduren auf jeden der aufeinanderfolgenden Datenübertragungsblöcke des bewegten Bildes ausführen. Um den Vorteil gegenüber der wiederholten Verwendung von JPEG zu verstärken, arbeiten MPEG und H.261 anhand der Unterschiede zwischen aufeinanderfolgenden Datenübertragungsblöcken, wobei sie Vorteile aus der bekannten Tatsache ziehen, daß der Unterschied, d. h. die Bewegung, zwischen den Datenübertragungsblöcken gering ist; es erfordert daher üblicherweise weniger Zeit oder Raum, um die den Veränderungen entsprechende Information zu übertragen oder zu speichern, als die äquivalente Information des ruhenden Bildes zu übertragen oder zu speichern, so als ob jeder Datenübertragungsblock in der Abfolge völlig anders als der ihm am nächstliegendsten Datenübertragungsblock wäre.
Zur Vereinfachung arbeiten alle gegenwärtigen Standards mit einem Aufbrechen einer Abbildung eines Bildes in Felder oder Blöcke, wobei jeder Block aus einem Stück des Bildes besteht, das acht Pixel breit und acht Pixel hoch ist. Jedes Pixel wird dann durch drei (oder mehr) digitale Zahlen repräsentiert, die als "Komponenten" dieser Pixel bekannt sind. Es bestehen viele unterschiedliche Wege zum Aufbrechen eines Farbpixel in Komponenten, z. B. die Verwendung einer Standardnotation, YUV, YCrCb, RGB etc. Alle herkömmliche JPEG-artigen Verfahren arbeiten an jeder Komponente separat.
Es ist weiterhin bekannt, daß das Auge für Hochfrequenzkomponenten (oder -flanken) in einem Bild unempfindlich ist. Die Information betreffend der höchsten Frequenzen kann gewöhnlich gänzlich weggelassen werden, ohne daß der menschliche Betrachter eine wesentliche Verringerung der Abbildungsqualität erkennt. Um diese Fähigkeit zur Reduzierung des Informationsgehalts in einem Bild durch Beseitigung von hochfrequenter Information zu erzielen, ohne daß das Auge einen Verlust von Information erfaßt, muß der 8-zu-8 Pixelblock, der räumliche Informationen (z. B. die tatsächlichen Werte der Helligkeit) enthält, in einer Weise transformiert werden, um eine Frequenzinformation zu erzielen. Die JPEG-, MPEG- und H.216-Standards verwenden alle die bekannte diskrete Kosinus-Transformation, um die 8-zu-8-Raummatrix zu bearbeiten, um eine 8-zu-8-Frequenzmatrix zu erzielen.
Wie oben erläutert wurde, stellen die Eingabedaten einen Quadratbereich eines Bildes dar. Bei der Transformation der Eingabedaten in eine Frequenzdarstellung muß die angewendete Transformation zweidimensional sein, wobei aber derartige zweidimensionale Transformationen schwierig in effektiver Weise berechenbar sind. Die bekannte zweidimensionale diskrete Kosinus-Transformation (Discrete Cosine Transform, DCT) und die zugehörige inverse DCT (IDCT), weisen jedoch die Eigenschaft auf, daß sie "separierbar" sind. Das bedeutet, daß nicht alle 64 Pixel im 8-zu-8-Pixelblock gleichzeitig bearbeitet werden müssen, sondern der Block zuerst Reihe-für-Reihe zu Zwischenwerten transformiert werden kann, welche dann Spalte-für-Spalte in die abschließenden transformierten Frequenzwerte übertragen werden.
Eine eindimensionale DCT der Ordnung N ist mathematisch äquivalent zur Multiplikation zweier N-zu-N-Matrixen. Um die erforderliche Matrixenmultiplikation für einen 8-zu-8-Pixelblock durchzuführen, sind 512 Multiplikationen und 448 Additionen erforderlich, so daß 1024 Multiplikationen und 896 Additionen benötigt werden, um die vollständige zweidimensionale DCT am 8-zu-8-Pixelblock durchzuführen. Diese arithmetischen Operationen und insbesondere die Multiplikationen sind komplex und langsam und begrenzen daher die erreichbare Übertragungsrate; sie erfordern zudem auch einen beträchtlichen Raum auf einem Siliciumchip, der zur Durchführung der DCT verwendet wird.
Die DCT-Prozedur kann durch Verringerung der erforderlichen Berechnungen neu geordnet werden. Gegenwärtig gibt es zwei Hauptverfahren, die zur Verringerung der erforderlichen Berechnungen für die DCT verwendet werden, wobei beide davon die "binäre Dezimalisierung" verwenden. Die Bezeichnung "binäre Dezimalisierung" bedeutet, daß eine N-zu-N-Transformation durch Verwendung zweier N/2-zu-N/2-Transformationen plus einigen Berechnungszusätzen während ihrer Anordnung berechnet werden kann. Während die 8-zu-8-Transformation 512 Multiplikationen und 448 Additionen erfordert, verlangt eine 4-zu-4-Transformation nur 64 Multiplikationen und 48 Additionen. Die binäre Dezimalisierung spart somit 384 Multiplikationen und 352 Additionen und der entstandene Zusatzaufwand zur Durchführung der Dezimalisierung ist typischerweise unwesentlich im Vergleich zu seiner Reduktion hinsichtlich der Berechnung.
Die beiden heute wesentlichen Verfahren zur binären Dezimalisierung wurden entwickelt durch Byeong Gi Lee ("A New Algorithm to Compute the DCT", IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. Assp 32, No. 6, p. 1243, December 1984), und Wen-Hsiung Chen ("A Fast Computational Algorithm for the DCT", Wen-Hsiung Chen, C. Harrison Smith, S.C. Pralick, IEEE Transactions on Communications, Vol. Com 25, No. 9, p. 1004, September 1977). Das Verfahren nach Lee nutzt die Symmetrie, welche der Definition der inversen DCT innewohnt, und durch Verwendung einfacher Kosinus-Äquivalenzverknüpfungen (identities) ist ein Verfahren zur rekursiven binären Dezimalisierung definiert. Die Methode nach Lee ist nur geeignet für die IDCT. Das Verfahren nach Chen nutzt eine rekursive Matrix-Äquivalenzverknüpfung, welche die Matrixen nur zu Diagonalen reduziert. Dieses Verfahren schafft eine einfache binäre Dezimalisierung der DCT mit Verwendung bekannter Äquivalenzverknüpfungen für diagonale Matrixen.
Ein ernster Nachteil der Verfahren nach Lee und Chen liegt darin, daß sie unausgeglichen sind hinsichtlich dem Zeitpunkt, wann Multiplikationen und Additionen durchgeführt werden müssen. Grundsätzlich erfordern beide Methoden, daß viele Additionen von vielen Multiplikationen gefolgt werden, oder umgekehrt. Wenn die Verfahren nach Lee oder Chen in der Hardware angewendet werden, ist es daher nicht möglich, parallele Operationen von Addierern und Multiplizierern durchzuführen. Dies verringert ihre Geschwindigkeit und Effektivität, da die beste Ausnutzung der Hardware gegeben ist, wenn alle Addierer und Multiplizierer zur gleichen Zeit verwendet werden.
Ein weiter Nachteil von diesen bekannten Verfahren und Vorrichtungen zur Durchführung der DCT- und IDCT-Operationen liegt darin, daß es gewöhnlich schwierig ist, die sogenannten Standardisierungskoeffizienten zu verarbeiten, und bekannte Strukturen erfordern die Hinzufügung einer zusätzlichen Multiplikation zu einem Zeitpunkt, wenn alle Multiplizierer verwendet werden.
Bestimmte bekannte Verfahren zur Anwendung der vorwärts- und inversen DCT an Videodaten sind sehr einfach und hoch effizient für einen Softwaredesigner, der nicht mit der Ausgestaltung von Halbleitervorrichtungen betroffen ist, welche diese Berech nungen durchführen müssen. Solche Verfahren sind jedoch häufig viel zu langsam oder viel zu komplex hinsichtlich der Halbleiterstruktur und Hardwareverbindungen, um zufriedenstellend bei den für digitales Video gewünschten Übertragungsraten zu arbeiten.
Noch ein weiterer Nachteil bestehender Verfahren und Hardwarestrukturen zur Durchführung von DCT- und IDCT-Operationen an Videodaten liegt darin, daß sie eine Gleitkommadarstellung für numerische Werte erfordert. Zur Darstellung dieses Nachteils sei angenommen, daß jemand einen Rechner hat, der nur in der Lage ist, mit dreistelligen Zahlen zu arbeiten, inklusive der Stellen bzw. Codeelemente rechts vom Dezimalpunkt (sofern gegeben). Ferner sei angenommen, daß der Rechner die Zahlen 12,3 und 4,56 addieren soll (Zu bemerken ist, daß der Dezimalpunkt in der Lage hinsichtlich der Stellen in diesen beiden Nummern nicht festgelegt ist. Mit anderen Worten kann der Dezimalpunkt "gleiten".). Da der Rechner nicht in der Lage ist, die für die vollständige Darstellung der Antwort 16,86 erforderlichen vier Stellen zu speichern, muß der Rechner die Antwort auf drei Stellen reduzieren, entweder durch Abrunden der Antwort mittels Fallenlassen der äußerst rechten "6", was zu einer Antwort von 16,8 führt, oder er muß die erforderliche Hardware aufweisen, um die Antwort auf die nächst kommende dreistellige Näherung 16,9 zu runden.
Wie dieses sehr einfache Beispiel zeigt, muß man entweder einen Präzisionsverlust akzeptieren oder einen hochkomplizierten und raumverschwendenden Schaltkreis zur Minimierung des Rundungsfehlers einbringen, wenn eine Gleitkommadarstellung angenommen oder erforderlich ist. Auch bei einem effizienten Rundungsschaltkreis kann die Anhäufung und Fortpflanzung von Rundungs- oder Abrundungsfehler zu einer nicht akzeptablen Störung des Videosignals führen. Dieses Problem ist noch größer, wenn die Verfahren zur Bearbeitung des Videosignals mehrere Multiplikationen erfordern, da Fehler bei der Gleitkommarundung und -abrundung typischerweise bei der Multiplikation noch größer sind als bei der Addition.
Eine wesentlich effizientere DCT/IDCT-Verfahrens- und Hardwarestruktur würde sicherstellen, daß die im Verfahren verwendeten Zahlen mit einem festgelegten Dezimalpunkt dargestellt werden könnten, aber in einer derartigen Weise, daß der gesamte dynamische Bereich jeder Zahl genutzt werden könnte. In einem derartigen System würden Abrundungs- und Rundungsfehler entweder beseitigt oder zumindest weitestgehend reduziert.
Wenn die Hardware beim obigen Beispiel vier Stellen bewerkstelligen könnte und keine größere Zahl als 99, 99 jemals benötigt werden würde, sowie jede Zahl den Dezimalpunkt zwischen der zweiten und dritten Stelle hätte, dann würde die Gegenwart des Dezimalpunkts die Berechnung insgesamt nicht beeinflussen und die Arithmetik könnte gerade so ausgeführt werden, als wenn jede Zahl eine ganzzahlige wäre: Die Antwort von 1230 + 0456 = 1686 wäre genauso klar wie die von 12,30 + 4,56 = 16,86, da man immer weiß, daß die "1686" einen Dezimalpunkt zwischen der mittleren "6" und "8" haben sollte. Wenn Zahlen (konstante oder andere) alternativ derart selektiv skaliert oder eingestellt sind, daß sie alle innerhalb des gleichen Bereichs fallen, könnte jede Zahl in diesem Bereich ebenso genau und unzweideutig dargestellt werden, als ein Satz von ganzzahligen Zahlen.
Ein Weg zur Reduzierung der Anzahl der erforderlichen Multiplizierer liegt einfach darin, einen einzelnen Multiplizierer zu haben, der in der Lage ist, Eingabedaten von unterschiedlichen Quellen zu akzeptieren. Mit anderen Worten verwenden bestimmte Strukturen einen einzelnen Multiplizierer, um in unterschiedlichen Schritten der DCT- oder IDCT-Berechnungen erforderlichen Multiplikationen durchzuführen. Obwohl eine derartige "Kreuzschienenschaltung" die Anzahl der erforderlichen Multiplizierer verringern kann, bedeutet dies, daß große und komplizierte Multiplexer-Strukturen statt dessen eingesetzt werden müssen, um die Eingaben zum Mulitplizierer auszuwählen, um andere vom Multiplizierer zu isolieren, und um die geeigneten Signale von den ausgewählten Quellen zu den Eingabestellen des Multiplizierers zu schalten. Zusätzliche großformatige Multiplexer werden dann ferner erforderlich, um die große Anzahl von Ausgaben von den ausgewählten Multiplizierern zum geeigneten nachfolgenden Schaltkreis zu schalten. Die Kreuzschienenschaltung oder Multiplexierung ist daher komplex und gewöhnlich langsam (aufgrund des erforderlichen Zusatzspeichers), und ein kostenwesentlicher Bereich in einer abschließenden Halbleiterrealisierung.
Noch ein weiterer Nachteil von bestehenden Strukturen mit der "Kreuzschienenschaltung" liegt darin, daß sie Vielzweckmultiplizierer erfordern. Mit anderen Worten benötigen bestehende Systeme Multiplizierer, bei denen beide Eingabestellen variabel sind. Wie weithin bekannt ist, enthalten Realisierungen von digitalen Multiplizierern typischerweise Reihen von Addierern und Schiebegliedern in der Art, daß der Wert des Multiplikanten zum Teilergebnis addiert wird, wenn das gegenwärtige Bit eines Multiplikatorworts eine "Eins" ist, jedoch nicht addiert wird, wenn das gegenwärtige Bit eine "Null" ist. Da ein Vielzweckmultiplizierer in der Lage sein muß, um den Fall zu be werkstelligen, bei dem jedes Bit eine "1" ist, muß eine Reihe von Addierern für jedes Bit des Multiplikatorworts vorgesehen sein.
Beispielsweise wird angenommen, daß die Datenwörter 8-Bit breit sind, und daß jemand wünscht, daß einzelne Eingaben mit 5 multipliziert werden. Eine 8-Bit-Darstellung der Zahl 5 ist 00000101. Mit anderen Worten erfordert digitale Multiplikation mit 5 nur, daß der Eingabewert zwei Stellen (entsprechend einer Multiplikation mit 4) verschoben und dann zum nicht verschobenen Wert addiert wird. Die anderen sechs Positionen des Koeffizienten weisen Bit-Werte von "0" auf, so daß sie keine Verschiebe- oder Additionsschritte erfordern.
Ein Multiplizierer mit feststehenden Koeffizienten, d. h. in diesem Falle ein Multiplizierer, der zu einer Multiplikation nur mit fünf in der Lage ist, würde nur ein einzelnes Verschiebeglied und einen einzelnen Addierer erfordern, um die Multiplikation durchzuführen (ungeachtet des Schaltkreises, der zur Bearbeitung der Trägerbits erforderlich ist). Ein Vielzweckmultiplizierer würde jedoch im Gegensatz hierzu Schiebeglieder und Addierer für jede der acht Stellen erfordern, auch wenn die Anwendung von sechs davon niemals erforderlich sein würde. Wie dieses Beispiel zeigt, können feststehende Koeffizienten die Multiplizierer vereinfachen, da sie es dem Konstrukteur ermöglichen, Reihen von Addierern zu beseitigen, die mit Nullen in den Koeffizienten korrespondieren, wodurch Siliziumbereiche eingespart werden.
Die Erfindung wird entsprechend der beigefügten unabhängigen Ansprüche 1 und 4 ausgeführt.
Bei einem IDCT-Verfahren gemäß einem weiteren Aspekt der Erfindung wird eine eindimensionale IDCT für jede N-Reihe und N-Spalte eines N-zu-N Pixelblocks dezimalisiert (decimated) und eine 1-D IDCT wird separat an den N/2 geradzahligen Pixel-Eingabewörtern und den N/2 ungeradzahligen Pixel-Eingabewörtern ausgeführt.
In einer bevorzugten Ausführungsform ist N = 8 gemäß dem JPEG-Standard. Das zweidimensionale IDCT-Ergebnis wird dann durch Ausführen von zwei eindimensionalen IDCT-Operationen in Aufeinanderfolge erzielt (mit einer Zwischenaufzeichnung - Überführung - von Daten).
Bei einem gemeinsamen Verarbeitungsschritt für N = 8 wird ein erstes Paar von Eingabewerten ohne dem Erfordernis einer Multiplikation zu den Ausgabeaddierern und -subtrahierern weitergeleitet. Jedes eines zweiten Paares von Eingabewerten wird mit jedem der beiden Konstant-Koeffizientwerten entsprechend den beiden skalierten Kosinus-Werten multipliziert. Keine anderen Multiplikationen und nur eine Subtraktion und eine Addition sind beim gewöhnlichen Verarbeitungsschritt erforderlich. Das zweite Paar wird dann paarweise mit dem ersten Paar von Eingabewerten addiert oder differenziert, um gerade oder ungerade Ergebniswerte zu bilden.
In einem gemeinsamen bzw. allgemeinen Vorverarbeitungsschritt wird das ungerade Eingabewort der niedrigsten Ordnung vorab mit der 2 multipliziert, und die ungeraden Eingabewörter werden paarweise summiert, bevor sie in einem gemeinsamen bzw. allgemeinen Verarbeitungsblock verarbeitet werden. In einem gemeinsamen bzw. allgemeinen Nachbearbeitungsschritt werden Zwischenwerte entsprechend den verarbeiteten ungeraden Eingabewörtern mit vorbestimmten konstanten Koeffizienten multipliziert, um ungerade Ergebniswerte zu bilden.
Nach der Berechnung der geraden und ungeraden Ergebniswerte werden die N/2- Ausgaben der höheren Ordnung durch einfache Subtraktion der ungeraden Ergebniswerte von den geraden Ergebniswerten gebildet, und die N/2-Ausgaben der niedrigen Ordnung werden durch einfache Addition der ungeraden Ergebniswerte und der geraden Ergebniswerte gebildet.
Sowohl für die DCT (auf der Übertragungsseite eines Videoverarbeitungssystems) als auch für die IDCT (auf der Empfangsseite, welche einen oder mehrere der verschiedenen Aspekte der Erfindung aufweist) sind die Werte vorzugsweise bewußt um einen Faktor von 2 aufwärts skaliert. Nachdem die DCT/IDCT-Operationen ausgeführt sind, können die Ergebniswerte dann um einen Faktor von zwei durch eine einfache binäre Verschiebung nach rechts abwärts skaliert werden. Diese bewußte und ausgeglichene Aufwärtsskalierung beseitigt mehrere Multiplikationsschritte, welche gemäß den herkömmlichen Verfahren erforderlich sind.
Gemäß einem weiteren Aspekt des Verfahrens werden ausgewählte Bits von Konstant-Koeffizienten oder Zwischenergebnisdatenwörtern durch eine vorbestimmte Festlegung von ausgewählten Bits auf entweder "1" oder "0" gerundet oder eingestellt.
Eine zweidimensionale Transformation von Pixeldaten wird durch einen zweiten, identischen 1-D-Vorgang der ersten 1-D IDCT-Verarbeitungsschritte durchgeführt.
Ein IDCT-System gemäß noch einem anderen Aspekt der Erfindung enthält einen gemeinsamen Vorverarbeitungsschaltkreis, einen gemeinsamen Verarbeitungsschaltkreis und einen gemeinsamen Nachverarbeitungsschaltkreis, wobei die gemeinsamen Vorverarbeitungsberechnungen, die gemeinsamen Verarbeitungsberechnungen und die gemeinsamen Nachverarbeitungsberechnungen an Eingabedatenwörter ausgeführt werden. Eine Überwachungssteuererinheit erzeugt Steuersignale, um das Laden der verschiedenen Systemsignalspeicher zu steuern; vorzugsweise, um die Anwendung der geradzahligen und ungeradzahligen N/2-Eingabewörter zu Eingabesignalspeichern des gemeinsamen Vorblocks seriell auf die Zeit zu multiplexen; um die geraden und ungeraden Ergebniswerte direkt zu addieren, um Ausgabesignale niedriger Ordnung zu bilden und zu speichern, und um die ungeraden Ergebniswerte direkt von den geraden Ergebniswerten zu subtrahieren, um die Ausgabewerte hoher Ordnung zu bilden und zu speichern; und um Aufeinanderfolgen der internen Multiplexer zu steuern.
Gerade und ungerade Eingabewörter werden vorzugsweise in separaten Durchgängen durch die gleichen Verarbeitungsblöcke verarbeitet. Eingabedatenwörter werden vorzugsweise (jedoch nicht notwendigerweise) nicht in strikt aufsteigender oder fallender Weise gespeichert (latched), sondern in einer Ordnung, die eine effiziente "Schmetterlings"-Struktur für die Datenwege ermöglicht.
Zumindest der gemeinsame Verarbeitungsschaltkreis kann als eine reine Logik- Schaltung konfiguriert sein, wobei keine Takt- oder Steuersignale für seinen exakten Betrieb erforderlich sind, und wobei auch andere Verarbeitungsblocks in Abhängigkeit von der jeweiligen Anwendung so ausgebildet sein können.
Keine Vielzweck-Multiplizierer (mit zwei variablen Eingängen) sind erforderlich; statt dessen sind Konstant-Koeffizienten-Multiplizierer in der bevorzugten Ausführungsform durchgehend aufgenommen. Ferner sind in der bevorzugten Ausführungsform Ganzzahlen-Arithmetikvorrichtungen mit festgelegtem Komma für alle erforderlichen arithmetischen Operationen angeordnet.
Es ist erkennbar, daß bestimmte Ausführungsformen der Erfindung so gestaltet werden können, daß sie ein Verfahren und ein System zur Durchführung einer IDCT- Transformation von Videodaten mit einem oder mehreren der folgenden Merkmale schaffen:
(1) konstante Verwendung von allen kostenintensiven arithmetischen Operationen;
(2) um den zur Realisierung der IDCT benötigten Siliziumbereich zu reduzieren, sind eine geringe Anzahl von Speicherelementen (wie z. B. Signalspeicher) vorgesehen, vorzugsweise nicht mehr als erforderlich sind für eine effiziente Überlappung bzw. Verdrahtung der Struktur, gekoppelt mit einer geringen Anzahl von Konstant-Koeffizient-Multiplizierern anstelle von Vielzweckmultiplizierern, welche extra Speicherelemente erfordern;
(3) Operationen sind so angeordnet, daß jede arithmetische Operation nicht die Vewendung komplizierter Strukturen erfordert; wenn z. B. bekannte "Nullstellen-Addierer" (ripple adders) verwendet werden, würden diese hinreichende Zeit zum "Lösen" (siehe nachstehend) oder Produzieren ihrer Antworten erfordern; wenn Operationen in einer derartigen Weise angeordnet sind, daß andere vorgeordnete Vorrichtungen wie ein Welligkeitsaddierer im Datenweg im Leerlauf zu halten sind, während sie darauf warten, daß die anderen Addierer beendet haben, sollen dann Umordnungsoperationen zur Vermeidung dieser Verzögerung zu einen größeren Durchsatz und einer höheren Effektivität führen;
(4) jemand ist in der Lage, Ergebnisse in einer natürlichen Ordnung zu erzeugen;
(5) keine kostenintensive, komplexe Kreuzschienenschaltung ist erforderlich;
(6) die Architektur ist in der Lage, wesentlich schnellere Operationen zu unterstützen; und
(7) der Schaltkeis zur Steuerung des Datenstroms durch die Transformationshardware kann in seiner Fläche klein gehalten werden.
Für ein besseres Verständnis der Erfindung und um aufzuzeigen, wie diese wirksam ausgeführt werden kann, wird nun beispielhaft auf die beigefügten Figuren der Zeichnung verwiesen, in denen:
Fig. 1 eine vereinfachte Darstellung von Basisschritten eines erfindungsgemäßen Verfahrens zur Durchführung der IDCT an Eingabedaten zeigt;
Fig. 2 ein Blockdiagramm ist, welches die kombinierte, vereinfachte, zweistufige Architektur eines IDCT-Systems gemäß der Erfindung darstellt;
Fig. 3 ein vereinfachtes Blockdiagramm der integrierten Schaltkreise ist, welches die Hauptkomponenten des IDCT-Systems enthält;
Fig. 4a und 4b miteinander ein Blockdiagramm einer Vorverarbeitungsschaltung entsprechend einer der Hauptsystemkomponenten sind; zur Vereinfachung der Erläuterung werden diese Figuren zusammen als Fig. 4 bezeichnet;
Fig. 5a und 5b zusammen ein Blockdiagramm einer gemeinsamen Verarbeitungsschaltung im IDCT-System sind; zur Vereinfachung der Erläuterung werden diese Figuren zusammen als Fig. 5 bezeichnet;
Fig. 6a, 6b, 6c und 6d zusammen ein Blockdiagramm einer Nachverarbeitungsschaltung sind, welche einer anderen Hauptkomponente des Systems entspricht; außer wenn es erforderlich ist, bestimmte Merkmale hervorzuheben, werden diese Figuren zusammen als Fig. 6 bezeichnet; und
Fig. 7a, b und c Zeitdiagramme sind, welche die Zusammenhänge zwischen dem Zeitverlauf und den Steuersignalen im IDCT-System der bevorzugten Ausführungsform zeigen.

Theoretischer Hintergrund der Erfindung

Um den Zweck und die Funktion der verschiedenen Komponenten und die Vorteile des im erfindungsgemäßen IDCT-Systems verwendeten Signalverarbeitungsverfahrens verstehen zu können, ist es hilfreich, die theoretische Basis des Systems zu verstehen.

Trennbarkeit einer zweidimensionalen IDCT

Die mathematische Definition einer zweidimensionalen, diskreten Vorwärtskosinustransformation (DCT) für einen N · N Block von Pixel ist wie folgt, wobei Y (j, k) die Pixel-Frequenzwerte entsprechend den absoluten Pixelwerten X (m, n) sind:
(E1): Y(j, k) =
wobei j, k = 0, 1, ..., N-1
Der Term 2/N bestimmt den DC-Level der Transformation, und die Koeffizienten c (j), c (k) sind als Standardisierungsfaktoren vorbekannt.
Die Gleichung für die entsprechende inverse diskrete Kosinus-Transformation, d. h. für die IDCT, ist wie folgt:
(E2): X(m, n) =
wobei j, k = 0,1, ..., N-1
Die Vorwärts-DCT wird verwendet, um räumliche Werte (ob sie nun Eigenschaften, wie die Helligkeit direkt repräsentieren oder Differenzen darstellen, wie im MPEG- Standard) in ihre Frequenzdarstellung zu transformieren. Die inverse DCT arbeitet, wie ihr Name anzeigt, in die andere "Richtung", d. h. die IDCT transformiert die Frequenzwerte zurück in die räumlichen Werte.
In der Gleichung E2 ist zu bemerken, daß die Kosinusfunktionen von jeweils nur einem der Summenindizes abhängen. Die Gleichung E2 kann daher umgeschrieben werden auf:
(E3): X(m, n) =
Dies ist das Äquivalent einer ersten eindimensionalen IDCT, welche am Produkt von allen Termen ausgeführt wird, die von k und n abhängen, wobei dies gefolgt wird von einer zweiten eindimensionalen IDCT, welche als Eingaben die Ausgaben der ersten IDCT-Operation verwendet, nachdem eine geradlinige Standarddatenübertragung stattgefunden hat.

Definition der 1-D IDCT

Eine eindimensionale, N-Punkt IDCT (wobei N eine gerade Zahl ist) wird durch die folgende Gleichung definiert:
(E4):
und wobei y(n) die N-Eingaben zur inversen Transformationsfunktion und x(k) ihre N-Ausgaben sind. Wie im 2-D-Fall hat die Formel für die DCT die gleiche Struktur unter dem Summenzeichen, jedoch mit der Standardisierungskonstante außerhalb des Summenzeichens und wobei die x- und y-Vektoren ihre Plätze in der Gleichung tauschen.

Lösung einer 1-D IDCT

Wie oben gezeigt ist, kann die 2-D IDCT durch Verwendung einer Abfolge von 1- D IDCT-Operationen berechnet werden, die durch eine Transformierung separiert sind. Gemäß einer Ausführungsform wird jede dieser 1-D Operationen ihrerseits in Unterprozeduren aufgeteilt, welche dann genutzt werden, um die erforderliche Größe und Komplexität der Halbleiterrealisierung noch weiter zu verringern.

Standardisierung der Koeffizienten

Wie oben diskutiert wurde, liegt ein bedeutendes Gestaltungsziel für die IDCT- Hardware in der Verringerung der erforderlichen Anzahl von Multiplizierern, welche in den Schaltkreis eingefügt werden müssen. Die meisten Verfahren zur Berechnung der DCT oder IDCT versuchen daher die Anzahl der erforderlichen Multiplikationen zu verringern. Gemäß dieser Ausführungsform werden alle Eingabewerte jedoch bewußt aufwärts skaliert durch einen Faktor von 2. Mit anderen Worten ist die rechte Seite der IDCT-Gleichung (E4) bei Anwendung des Verfahrens gemäß dieser Ausführung bewußt mit 2 multipliziert.
Gemäß dieser Ausführungsform werden zwei 1-D IDCT-Operationen in Serie durchgeführt (mit einer dazwischen liegenden Transponierung), um das abschließende 2-D IDCT-Ergebnis zu erzielen. Jede dieser 1-D-Operationen enthält eine Multiplikation durch den gleichen 2 Faktor. Da die dazwischen liegende Transponierung keine Skalierung verursacht, ist das Ergebnis der beiden Multiplikationen um 2 in Reihe so, daß das abschließende 2-D-Ergebnis durch einen Faktor von 2 · 2 = 2 aufwärts skaliert ist. Um den unskalierten Wert zu erzielen, muß der Schaltkreis dann nur durch 2 dividieren, was auf einfache Weise durch ein simples nach rechts Verschieben der Daten durchgeführt werden kann, da die Werte alle digital dargestellt sind. Wie nachfolgend noch klarer wird, wird die Aufwärtsskalierung durch 2 in jeder 1-D IDCT-Stufe und das abschließende Herabskalieren um 2 durch Addierer, Multiplizierer und Schiebeglieder ausgeführt, welche alle derart innerhalb der Hardware des Systems vorliegen, daß das System keine Erfordernisse für eine skalierte Eingabe an anderen Vorrichtungen schafft, mit welchen das System verbunden sein kann. Aus diesem Grund ist das System kompatibel mit anderen herkömmlichen Vorrichtungen, welche gemäß den JPEG- oder MPEG-Standards arbeiten.
Die Standardisierung gemäß dieser Ausführungsform beseitigt daher die Notwendigkeit von Hardware-Multiplizierern innerhalb der IDCT-Halbleiterarchitektur für wenigstens zwei 2 -Multiplikationsoperationen. Wie nachfolgend noch detaillierter erläutert wird, führt der einzelne zusätzliche Multiplikationsschritt (Aufwärtsskalierung um 2) der Eingabedaten in jeder 1-D-Operation zur Beseitigung von noch weiteren Multiplikationsschritten, welche bei Anwendung von herkömmlichen Verfahren erforderlich sind.

Trennung der 1-D IDCT in hoch- und niederwertige Ausgaben

Die Gleichung E4 kann getrennt für die N/2 niederwertigen Ausgaben (k = 0, 1, ..., N/2-1) und die N/2 hochwertigen Ausgaben (k = N/2, N/2+1, ... N) ausgewertet werden. Für N = 8 bedeutet dies, daß man zuerst die Eingaben zur Berechnung von y(0), y(1), y(2), und y(3) transformieren kann, und dann die Eingaben zur Berechnung von y(4), y(5), y(6) und y(7) transformiert.
Die Variable k' = (N-1-k) für die hochwertigen Ausgaben (k = N/2+1, ..., N) werden derart eingebracht, daß sich k' von (N/2-1) zur 0 verändert, wenn sich k von (N/2+1) auf N verändert. Für N = 8 bedeutet dies, daß k' = {3, 2, 1, 0} für k = {4, 5, 6, 7}. Es kann dann gezeigt werden, daß die Gleichung E4 in die folgenden beiden Untergleichungen E5 (welche mit Ausnahme des Intervalls für die Summierung die gleiche wie E4 ist) und E6 unterteilt werden kann.
Niederwertige Ausgaben:
wobei k = {0, 1, ..., (N/2-1)}; und
Hochwertige Ausgänge:
wobei k = {N, ..., (N/2+1)} → k' = {0, 1, ..., (N/2-1)}
(Da c(n) = 1 für alle hochwertigen Terme gilt, ist c(n) nicht in diese Gleichung eingebracht.)
Zu bemerken ist, daß beide Gleichungen E5 und E6 die selbe Struktur unter dem Summenzeichen aufweisen, mit der Ausnahme, daß der Term (-1)n das Vorzeichen des Produkts unter dem Summenzeichen für die ungeradzahligen Eingaben (n ungeradzahlig) für die höheren N/2-Ausgabewerte verändert, und der Ausnahme, daß der y(0)-Term durch c(0) = 1/ 2 multipliziert wird.

Trennung der 1-D IDCT in gerade und ungerade Eingaben

Es sei angemerkt, daß die einzelne Summe in der 1-D IDCT-Gleichung E4 auch in zwei Summen getrennt werden kann: eine für die geradzahligen Eingaben (für N = 8, y(0), y(2), y(4), und y(6)) und eine für die ungeradzahligen Eingaben (für N = 8, y(1), y(3), y(5) und y(7)). Hierbei soll g(k) die Teilsumme für die geradzahligen Eingaben und h(k) die Teilsumme für die ungeradzahligen Eingaben darstellen. Es gilt daher:
(E7): g(k) =
wobei k = {0, 1, ..., (N/2-1)}; und
wobei k = {0, 1, ..., (N/2-1)}
Für N = 8 kann beobachtet werden, daß die Summen in E7 und E8 beide aus n = {0, 1, 2, 3} übernommen sind.
Nun rufe man sich die bekannte Kosinusgleichung in Erinnerung:
2 · cosA · cosB = cos(A + B)+ cos(A - B), und setze A = π (2k + 1)/2N und
B = π(2k + 1)· (2n + 1)/2N. Man kann dann beide Seiten der Gleichung E8 multiplizieren mit:
2 · cos A = 1/{2 · cos[π(2k + 1)/2N]} = Ck
Zu bemerken ist, daß Ck im Summenzeichen bewegt werden kann, da es nicht vom Summenindex n abhängt. Es sei nun per Definition angenommen, daß y(-1) = 0, und bemerkt, daß die Kosinusfunktion für die Eingabe y(7) gleich Null ist. Die Gleichung für h(k) kann dann zur folgenden Form umgestellt werden:
(E9):
wobei k = {0, 1, ..., (N/2-1)}.
Zu bemerken ist, daß die "Eingaben" [y(2n + 1) + y(2n - 1)] in der Gleichung h(k) darauf schließen lassen, daß die ungeraden Eingabewerte gepaart sind, um N/2 "gepaarte Eingaben" p(n) = [y(2n + 1) + y(2n - 1)] zu bilden.
Für N = 8 sind die Werte von p(n) wie folgt:

n p(n)

0 y(-1) + y(1) = y(1) (y(-1) = 0 per Definition)
1 y(1) + y(3)
2 y(3) + y(5)
3 y(5) + y(7)
Gleichung E9 für h(k) kann dann wie folgt wiedergegeben werden:
wobei k = {0,1, ..., (N/2-1)}.
Nun ist wahrzunehmen, daß der Konsinus-Term unter dem Summenzeichen sowohl für g(k) als auch für h(k) der gleiche ist, und daß beide die Struktur einer 1-D IDCT aufweisen (vgl. mit Gleichung E5). Das Ergebnis der IDCT für die ungeraden k- Werte, d. h. für h(k), wird jedoch mit dem Faktor Ck = 112 · cos[π{2k + 1)/2N]} multipliziert. Mit anderen Worten ist g(k) eine N/2-Punkt IDCT, welche gerade Eingaben y(2n) bearbeitet, und h(k) eine N/2-Punkt IDCT, welche [y(2n + 1) + y(2n - 1)] bearbeitet, wobei y(-1) = 0 per Definition.
Nun seien die folgenden Gleichungen eingeführt:
yn = y(n)
c1 = cos(π/8);
c2 = cos(2π/8) = cos(π/4) = 1/ 2;
c3 = cos(3π/8);
d1 = 1/[2 · cos(π/16)];
d3 = 1/[2 · cos(3π/16)];
d5 = 1/[2 · cos(5π/16)]; und
d7 = 1/[2 · cos(7π/16).
Ferner seien die skalierten Kosinus-Koeffizienten wie folgt eingeführt:
c1s = 2 · cos(π/8);
c3s = 2 · cos(3π/8);
Unter Verwendung der bekannten Gleichmäßigkeit (cos(-φ) = cos(φ)) und Periodizität (cos(-φ) = -cos(-φ)) der Konsinusfunktion können die Gleichungen E7 und E8 für N = 8 erweitert werden, um zu erzielen (man rufe sich auch in Erinnerung, daß c(0) gleich 1/ 2) ist:
g(0) = 1/ 2 · y0 + y2c1 + y4c2 + y6c3 = 1/ 2 · (y0 + y2 · c1s + y4 + y6 · c3s)
g(1) = 1/ 2 · y0 + y2c3 - y4c2 - y6c1 = 1/ 2 · (y0 + y2 · c3s - y4 - y6 · c1s)
g(2) = 1/ 2 · y0 - y2c3 - y4c2 + y6c1 = 1/ 2 · (y0 - y2 · c3s - y4 + y6 · c1s)
g(3) = 1/ 2 · y0 - y2c1 + y4c2 - y6c3 = 1/ 2 · (y0 - y2 · c1s + y4 - y6 · c3s)
und
h(0) = d1 · {y1 + (y1 + y3) c1 + (y3 + y5) c2 + (y5 + y7)c3} = d1/ 2 · { 2 · y1 + (y1 + y3) · c1s + (y3 + y5) + (y5 + y7) · c3s}
h(1) = d3 · {y1 + (y1 + y3) c3 - (y3 + y5) c2 - (y5 + y7) c1} = d3/ 2 · { 2 · y1 + (y1 + y3) · c3s - (y3 + y5) - (y5 + y7) · c1s}
h(2) = d5 · {y1 - (y1 + y3) c3 - (y3 + y5) c2 + (y5 + y7) c1} = d5/ 2 · { 2 · y1 - (y1 + y3) · c3s - (y3 + y5) + (y5 + y7)· c1s}
h(3) = d7 · {y1 - (y1 + y3) c1 + (y3 + y5) c2 - (y5 + y7) c3} = d7/ 2 · { 2 · y1 - (y1 + y3) · c1s + (y3 + y5) - (y5 + y7) · c3s}
Nun rufe man sich in Erinnerung, daß gemäß dieser Ausführungsform alle Werte um einen Faktor von 2 sowohl für die DCT- als auch für die IDCT-Operationen aufwärts skaliert sind. Mit anderen Worten sind gemäß dieser Ausführungsform sowohl h(k) als auch g(k) mit diesem Skalierungsfaktor multipliziert. Die Gleichungen g(k) und h(k) werden daher:
(E11):
g(0) = y0 + y2 · c1s + y4 + y6 · c3s
g(1) = y0 + y2 · c3s - y4 - y6 · c1s
g(2) = y0 - y2 · c3s - y4 + y6 · c1s
g(3) = y0 - y2 · c1s + y4 - y6 · c3s
und
(E12):
h (0) = d1{ 2 · y1 + (y1 + y3) · c1s + (y3 + y5) + (y5 + y7) · c3s}
h(1) = d3{ 2 · y1 + (y1 + y3) · c3s - (y3 + y5) - (y5 + y7) ·c1s}
h(2) = d5{ 2 · y1 - (y1 + y3) · c3s - (y3 + y5) + (y5 + y7) · c1s}
h(3) = d7{ 2 · y1 - (y1 + y3) · c1s + (y3 + y5) - (y5 + y7) · c3s}
Zu bemerken ist, daß die Multiplikation um 2 einen "skalierten" c2-Wert = 1 ergibt, da c2 = cos(π/4) = 1/ 2. Durch Skalierung der Gleichungen (entsprechend der Aufwärtsskalierung der Werte der Absolut- und Frequenz-Videowerte) ist es gemäß dieser Ausführungsform möglich, das Erfordernis der gemeinsamen Multiplikation um c2 zu beseitigen. Ferner müssen nur zwei Konsinus-Terme ausgewertet werden, c1s und c3s, wobei beide derart konstante Koeffizienten sind, daß Vielzweckmultiplizierer nicht erforderlich sind. Dies beseitigt zudem das Erfordernis für entsprechende Hardware- Multiplizierer in der Halbleiterrealisierung der IDCT-Operationen.
Die Ähnlichkeit von g(k) und h(k) in der Struktur kann durch Darstellen dieser Gleichungssätze in Matrixform illustriert werden. So sei die wie folgt definierte 4 · 4 Kosinus-Koeffizienten-Matrix:
dann:
und
wobei = diag[d1, d3, d5, d7] = die 4 · 4 Matrix mit d1, d3, d5 und d7 längs der Diagonalen und mit allen anderen Elementen gleich Null. Wie E14 und E15 zeigen, weisen die Prozeduren für die Bearbeitung von geradzahligen Eingaben zum Erhalt von g(k) und die Operationen für die ungeradzahligen Eingaben zum Erhalt von h(k) beide den gemeinsamen Schritt der Multiplikation mit der Konsinus-Koeffizienten-Matrix auf. Um h(k) zu erzielen, müssen die Eingaben jedoch zuerst paarweise summiert werden (es sei in Erinnerung gerufen, daß y(-1) = 0 per Definition), wobei y(1) mit 2 vormultipliziert sein muß, und wobei die Ergebnisse der Multiplikation mit multipliziert werden müssen mit .
Wie die oben dargestellten Gleichungen ferner anzeigen, kann die N-Punkt, 1-D IDCT (siehe E4) in zwei N/2-Punkt, 1-D IDCTs aufgeteilt werden, wobei jede gemeinsame Kernoperationen (unter dem Summenzeichen) an den N/2 ungeraden (gruppierten) und N/2 geraden Eingabewerte schafft. Die obigen Gleichungen erzielen die folgende einfache Struktur für die IDCT, wie sie in dieser Ausführungsform realisiert wird:
Niederwertige Ausgaben (für N = 8, Ausgaben k = {0, 1, 2, 3}):
(E16): y(k) = g(k) + h(k)
Hochwertige Ausgaben (für N = 8, Ausgaben k = {4, 5, 6, 7}):
(E17): y(k) = y(N-1-k') = g(k') - h(k')
Zu bemerken ist, daß g(k) unmittelbar an geraden Eingabewerten arbeitet, um auf direkte Weise Ausgabewerte zu erzielen, während h(k') ein Gruppieren von Eingabewerten bedingt, wie auch eine Multiplikation mit den Werten d1, d3, d5 und d7.
Wie immer ist der Designer einer IDCT-Schaltung mit einer Anzahl von Abwägungen konfrontiert, wie z. B. der Größe gegenüber der Geschwindigkeit und der größeren Zahl von realisierten Vorrichtungen gegenüber der verringerten Zwischenverbindungskomplexität. Z. B. ist es häufig möglich, die Geschwindigkeit der Berechnung durch Einbinden weiterer oder komplizierterer Vorrichtungen am Silizium-Chip zu verbessern, wobei dies die Realisierung jedoch offensichtlich größer oder komplexer macht. Ferner kann der verfügbare oder gewünschte Bereich auf dem IDCT-Chip die Verwendung von durchentwickelten, komplizierten Gestaltungen, wie z. B. "Vorgriff-" Addierer begrenzen oder ausschließen.

Genauigkeitsstandards

Nimmt man eine unbegrenzte Präzision und Genauigkeit bei allen Berechnungen an und somit einen unbegrenzten Speicherplatz und eine unbegrenzte Berechnungszeit, würde die wiederhergestellte Abbildung durch Ausführen der IDCT auf DCT-transformierten Abbildungsdaten das ursprüngliche Bild perfekt wieder herstellen. Eine derar tige Perfektion ist natürlich bei Verwendung der bestehenden Technologie nicht gegeben.
Um eine Standardisierung zu erzielen, werden IDCT-Systeme jedoch gegenwärtig an einem standardisierten Verfahren gemessen, welches vorgegeben ist vom Comite Consultatif International Telegraphique et Telephonique ("CCITT") im "Annex 1 of CCITT Recommendation H.261 - Inverse Transform Accuracy Specification". Dieser Test spezifiziert, daß Sätze von 10.000 8-zu-8 Blocks mit zufälligen. Ganzzahlen erzeugt werden. Diese Blöcke werden dann DCT- und IDCT transformiert (vorangehend oder gefolgt von vorbestimmten Rundungen, Abschneidungen und arithmetischen Operationen) unter Verwendung einer vorbestimmten Präzision, um 10.000 Sätze von 8-zu- 8 IDCT "Referenz"-Ausgabedaten zu erzeugen.
Beim Testen einer IDCT-Realisierung werden die CCITT-Testblocks als Eingaben verwendet. Die tatsächlichen transformierten IDCT-Ausgaben werden dann statistisch mit den bekannten IDCT "Referenz"-Ausgabedaten verglichen. Für die IDCT werden Maximalwerte hinsichtlich von Scheitel-, Mittelwert-, mittlerer quadratischer Fehler und Mittelwert des Mittelwertfehlers in Blöcken als ganzes oder individuelle Elemente spezifiziert. Ferner muß die IDCT alle Nullen heraus arbeiten, wenn der entsprechende Eingabeblock alle Nullen enthält, und die IDCT muß die gleichen Standards erfüllen, wenn das Zeichen von allen Eingabedaten verändert wird. Man betrachtet Realisierungen der IDCT nur mit einer akzeptablen Genauigkeit, wenn ihre Maximalfehler bei diesen Testläufen die spezifizierten Maximalwerte nicht übersteigen.
Weitere bekannte Standards sind jene des Institute of Electrical and Electronic Engineers ("IEEE"), in "IEEE Draft Standard Specification for the Implementation of 8 by 8 Discrete Cosine Transform", P1180/D2, July 18, 1990; und Anlage A von "8 by 8 Inverse Discrete Cosine Transform", ISO Committee Draft CD 11172-2. Diese Standards sind im wesentlichen mit dem oben beschriebenen CCITT-Standard identisch.

Hardware-Realisierung

Fig. 1 ist ein vereinfachtes Blockdiagramm, welches den Datenfluß beim IDCT- Verfahren gemäß einer Ausführungsform darstellt (obwohl die Hardwarestruktur, wie sie nachstehend dargestellt und erläutert ist, noch kompakter und effizienter gestaltet ist). In Fig. 1 sind die Eingaben zum System wie Y[0] und Y[4] und die Ausgaben aus dem System wie X[3] und X[6] gezeigt als seien sie auf einzelnen Linien übertragen. Es sollte verständlich sein, daß jede der einzeln gezeichneten Linien in Fig. 1 verschiedene Verbinder in der Gestalt von Datenbussen zum vorzugsweise parallelen Übertragen der Datenwörter mit unterschiedlicher Bitbreite darstellen, welchen jede Eingabe und Ausgabe entspricht.
In Fig. 1 stellen große offene Kreise Zwei-Eingang, Einzel-Ausgang-Addierer dar, wobei ein sehr kleiner Kreis am Verbindungspunkt eines Eingangs zum Addierer anzeigt, daß das Komplement des entsprechenden Eingabeworts verwendet wird. Addierer mit einem derartig komplementierten Eingang subtrahieren daher den komplementierten Eingang vom nicht komplementierten Eingang. So formt z. B. der Addierer mit der Ausgabe T1 den Wert Y0 + (-1) · Y4 = Y0 - Y4, obwohl der Ausgang T0 vom oberen linken Addierer gleich zu Y[0] + Y[4] sein wird (d. h. T0 = Y0 + Y4). Addierer mit einem einzelnen komplementierenden Eingang können daher als differenzierende Komponenten bezeichnet werden.
Ebenfalls in Fig. 1 sind Konstant-Koeffizient-Multiplizierer durch massive Dreiecke im Datenweg dargestellt. Z. B. durchläuft die Eingabe Y1 einen 2 Multiplizierer, bevor sie in den Addierer zur Ausbildung von BO eintritt. Folglich ist der Zwischenwert T3 = Y2 · T3 = Y2 · c1s + Y6 · c3s, und der Zwischenwert B2 = p1 · c3s - p3 · c1s = (Y1 + Y3) · c3s - (Y5 + Y7) · c1s. Durch Ausführen der angezeigten Additionen, Subtraktionen und Multiplikationen wird es erkennbar, daß die dargestellte Struktur die Gleichungen E11 und E12 für g(0) bis g(3) und h(0) bis h(3) realisiert.
Fig. 1 stellt einen wichtigen Vorteil dieser Ausführungsform dar. Wie Fig. 1 zeigt, ist die Struktur in vier Hauptregionen unterteilt: einen gemeinsamen Vorblock (precommon block) PREC, der die gepaarten Eingaben p(k) formt und die Eingabe Y(1) mit 2 multipliziert; einen ersten gemeinsamen Nachblock (post-common block) POSTC1, der vier Multiplizierer für die Konstanten d1, d3, d5 und d7 enthält (siehe Gleichung E12); einen zweiten gemeinsamen Nachblock (second post-common block) POSTC2, der die Terme g0 bis g3 und die Terme h0 bis h3 für die niederwertigen Ausgaben summiert, und die Differenz der Terme g0 bis g3 und der Terme h0 bis h3 für die hochwertigen Ausgaben bildet (siehe Gleichungen E16 und E17); und einen gemeinsamen Block (common block) CBLK, der nachfolgend beschrieben wird.
Wie die Gleichungen E14 und E15 andeuten, führt die Verarbeitung sowohl der geradzahligen als auch der ungeradzahligen Eingabesignale durch Manipulation der Eingabesignale gemäß dieser Ausführungsform zu einer gemeinsamen Operation, die durch die Matrix repräsentiert wird. Dies ist in Fig. 1 ersichtlich, in welcher der gemeinsame Block CBLK sowohl in den geraden, als auch in die ungeraden Datenwege aufgenommen ist. Beim Verarbeitungsschaltkreis gemäß dieser Ausführungsform werden die an den ungerad- und geradzahligen Eingaben durchgeführten gemeinsamen Operationen durch eine einzelne Struktur ausgeführt, anstelle der in Fig. 1 dargestellten duplizierten Struktur.
Um das Bearbeitungsverfahren und die Vorteile von bestimmten digitalen Strukturen, die in dieser Ausführungsform verwendet werden, zu verstehen, ist es hilfreich, zu verstehen, was ein "Übertragswort" ist, und wie es erzeugt wird.
Bei der Durchführung der beiden gewöhnlichsten arithmetischen Operationen, der Addition und der Multiplikation müssen digitale Vorrichtungen mit dem Problem von "Übertragsbits" arbeiten. Als einfaches Beispiel sei bemerkt, daß die Addition von zwei binären Zahlen derart ist, daß 1 + 1 = 0 ist, mit einem Übertrag von "1", welcher in das nächst höherwertige Bit addiert werden muß, um das korrekte Ergebnis "10" herzustellen (die binäre Darstellung der Dezimalzahl "2"). Mit anderen Worten is 01 + 01 = 00 (siehe "Summe" ohne Übertrag) + 10 (das Übertragswort); beim Addieren der "Summe" zum "Übertragswort" erhält man die korrekte Antwort 00 + 10 = 10.
Als ein dezimales Beispiel nimmt man an, daß die Zahlen "436" und "825" addiert werden müssen. Die gewöhnliche Prozedur für die Addition zweier Zahlen von Hand verläuft logischerweise wie folgt:
1) Einheiten: "6" plus "5" ist "1", mit einem Übertrag von "1" in die "Zehner"- Position -
Summe: 1, Eintrag: 0, Vortrag: 1;
2) Zehner: "3" plus "2" ist "5", plus die "1", welche vom vorhergehenden Schritt übertragen wurde, ergibt "6", mit keinem Übertrag -
Summe: S. Eintrag: 1, Vortrag: 0;
3) Hunderter: "4" plus "8" ist "2", mit einem Übertrag von 1 in die Tausender, aber mit keinem Übertrag, der aus dem vorangehendem Schritt zu addieren ist;
Summe: 2, Eintrag: 0, Vortrag: 1;
4) Tausender: "0" plus "0" ist "0", plus die "1", welche von den Hundertern übertragen wurde, ergibt "1".
Summe: 0, Eintrag: 1, Vortrag: 0
Die Antwort "1261" wird daher durch Addieren der Eintrags-Summe für jede Position zur Summe für die gleiche Position gebildet, wobei der Eintrag für jede Position der Austrag bzw. Vortrag der benachbarten niederwertigen Position ist. (Zu bemerken ist, daß dies impliziert, daß der Eintrag in die niedrigwertigste Position immer eine "0" ist.) Das Problem liegt natürlich daran, daß man mit dem Addieren der "4" und "8" in der Hunderterstelle warten muß, bis man weiß, ob hier ein Eintrag von der Zehnerstelle sein wird. Dies stellt einen "Nullstellen-Addierer" (ripple adder) dar, der im wesentlichen in dieser Weise arbeitet. Ein "Nullstellen-Addierer" erreicht daher eine "abschließende" Antwort ohne zusätzliche Speicherelemente zu benötigen, aber er ist langsamer als einige andere Bauweisen.
Eine derartig alternativ gestaltete Alternativbauweise ist bekannt als "Übertragssicherung" (carry-save), bei der die Summe von zwei Zahlen für jede Position durch Speichern einer Teilsumme oder eines Ergebnisworts (in diesem Beispiel 0251) und der Übertragswerte in einem anderen Wort (hier 1010) gebildet wird. Die volle Antwort wird dann durch "Auflösen" der Summe und der Übertragwörter in einem nachfolgenden Additionsschritt erzielt. Daher ist dann 0251 + 1010 = 1261. Zu bemerken ist, daß man die Addition für jede Position zur gleichen Zeit durchführen kann, ohne darauf warten zu müssen, um zu bestimmen, ob ein Übertrag dazu zu addieren sein wird, und daß Übertragwort kann zum Teilergebnis jederzeit addiert werden, so lange es gespeichert ist.
Da die Lösungsoperationen typischerweise den größten Anteil an der erforderlichen Zeit in jedem Berechnungsschritt erfordern, hat die Beschleunigung dieser Operationen einen signifikanten Effekt auf die gesamte Bearbeitungsgeschwindigkeit, während ein relativ geringer Anstieg im Umfang der Transformation erforderlich ist. Übertrag sparende Multiplikatoren sind daher gewöhnlich schneller als jene, die Nullstellen- Addierer in jeder Reihe verwenden, wobei dieser Zeitgewinn aber auf Kosten einer größeren Komplexität geht, da das Übertragwort für jede Addition im Multiplizierer entweder gespeichert oder zur nächsten Addition weitergeleitet werden muß. Um das abschließende Produkt einer Multiplikation zu erzielen, muß die abschließende Teilsumme und das abschließende Übertragswort ferner üblicherweise durch Addition in einen Nullstellen-Addierer gelöst werden. Zu bemerken ist, daß jedoch nur ein Nullstellen- Addierer erforderlich ist, so daß die Zeiteinsparungen gewöhnlich proportional zum Umfang der Multiplikation ist, die durchgeführt werden muß. Ferner ist zu bemerken, daß ein Übertragswort wie jede andere hinein zu addierende Zahl betrachtet werden kann, und so lange es einige Zeit vorher addiert wird, bevor die abschließende Multiplikationsantwort benötigt wird, kann die tatsächliche Addition verzögert werden.
In dieser Ausführungsform wird die Möglichkeit einer verzögerten Lösung genutzt, um die Bauweise zu vereinfachen und den Durchsatz durch den IDCT-Schaltkreis zu erhöhen. Ferner werden bestimmte Bits von vorbestimmten Übertragswörtern optional bewußt zu vorbestimmten Werten gebracht, bevor sie gelöst werden, um eine größere erwartete Genauigkeit des IDCT-Ergebnisses basierend auf einer statistischen Analyse aus Testläufen der Erfindung an Standardtest-Datensätzen herzustellen.
Fig. 2 ist ein Blockdiagramm, welches eine bevorzugte Struktur darstellt. In dieser bevorzugten Ausführungsform der Erfindung werden gerad- und ungeradzahlige Eingaben zeitlich multiplext und separat im gemeinsamen Block CBLK verarbeitet. Die Eingaben können in jeder Ordnung verarbeitet werden.
Gemäß Fig. 2 wird die Notation Y[1,0], Y[5,4], Y[3,2] und Y[7,6] verwendet, um anzuzeigen, daß die ungeradzahligen Eingaben Y1, Y3, Y5 und Y7 vorzugsweise zuerst durch den Berechnungsschaltkreis laufen, wobei sie von den geradzahligen Eingaben Y0, Y2, Y4 und Y6 gefolgt werden. Diese Ordnung ist nicht wesentlich für die Ausführungsform. Dennoch werden, wie nachfolgend beschrieben ist, bestimmte abwärts gerichtete arithmetische Operationen nur an den ungeradzahligen Eingaben durchgeführt, und bei einem vorausgehenden Eintritt der ungeradzahligen Eingabewerte, können diese abwärts gerichteten Operationen zur gleichen Zeit ablaufen, wie die gemeinsamen arithmetischen Operationen für alle Eingaben stromaufwärts an den geradzahligen Eingaben durchgeführt werden. Dies verringert die Zeit, in der verschiedene arithmetische Vorrichtungen sonst im Leerlauf bleiben würden.
In ähnlicher Weise wird die Notation X[0,7], X [1,6], X[3,4] und X[2,5] verwendet, um anzuzeigen, daß die niedrigerwertigen Ausgänge X0, X1, X2 und X3 zuerst ausgegeben werden, wobei sie von den höherwertigen Ausgaben X4, X5, X6 und X7 gefolgt werden. Wie die Fig. 1 und 2 darstellen, sind die Eingaben anfangs vorzugsweise nicht in aufsteigender Reihenfolge gruppiert, obwohl dies erfindungsgemäß nicht notwendig ist. Daher sind die geradzahligen Eingaben von oben nach unten gelesen Y0, Y4, Y2 und Y6 und die ungeradzahligen Eingaben sind Y1, Y5, Y3 und Y7. Die Anordnung der Eingabesignale in dieser Ordnung ermöglicht die einfache "Schmetterlings"-Datenwegstruktur gemäß der Darstellungen in Fig. 1 und 2 und erhöht in großem Umfange die Zwischenverbindungs-Effektivität der Realisierung der Erfindung in Siliziumhalbleitervorrichtungen.
In Fig. 2 sind Addierer und Subtrahierer durch Kreise angezeigt, die entweder ein "+" (Addierer), "-" (Subtrahierer, d. h. einen Addierer mit einem komplementierten Eingang), oder "±" (Lösungsaddierer/-subtrahierer, der zum Schalten zwischen Addition und Subtraktion in der Lage ist) enthalten. Die am weitesten links angeordneten Addierer und Subtrahierer im gemeinsamen Block CBLK sind vorzugsweise übertragsichernde Addierer und Subtrahierer, was bedeutet, daß ihre Ausgabe nach der Addition/Subtraktion der beiden m-Bit Eingabewörter das m-Bit Teilergebnis parallel zum m-Bit oder (m-1)-Bit Wort mit den Übertragbits der Addition/Subtraktion ist. Mit anderen Worten sind die ersten Additionen und Subtraktionen im gemeinsamen Block CBLK vorzugsweise ungelöst, was bedeutet, daß die Addition des Übertragsbits bis zu einem nachfolgenden Verarbeitungsschritt verzögert ist. Der Vorteil hiervon liegt darin, daß derartige übertragsichernde Addierer/Subtrahierer schneller sind als herkömmliche auflösende Addierer/Subtrahierer, da es nicht erforderlich ist, die abschließende Addition des Übertragsbit-Worts zum Ergebnis durchzuführen. Lösungsaddierer können jedoch auch verwendet werden, um die Breite der Sammelschiene an den Ausgängen der Addierer zu verringern.
Fig. 2 illustriert ferner die Verwendung von Ein- und Zweieingangs-Signalspeicher in der bevorzugten Ausführungsform der Erfindung. In Fig. 2 sind Signalspeicher als Rechtecke dargestellt und werden sowohl im gemeinsamen Vorblock PREC, als auch im gemeinsamen Nachblock POSTC verwendet. Einzeleingangs-Signalspeicher werden an den Eingängen der Multiplizierer D1, D3, DS und D7 verwendet, wie auch zum Speichern der Eingaben zu den Lösungsaddierern/-subtrahierern, welche die Ausgangssignale X0 bis X7 erzeugen. Wie Fig. 2 darstellt, sind die Eingaben zu diesen Lösungsaddierern/-subtrahierern die berechneten g(k) und h(k)-Werte entsprechend den jeweiligen Ausgaben von den Signalspeichern g[0,7], g[1,6], g[3,4] und g[2,5], und h[0,7], h[1,6], h[3,4] und h[2,5]. Als solche führen die Lösungsaddierer/-subtrahierer die Addition oder Subtraktion aus, die in den oben beschriebenen Gleichungen E16 und E17 angezeigt sind.
Wie oben erläutert wurde, müssen die geradzahligen Eingaben Y0, Y2, Y4 und Y6 nicht gepaart werden, bevor sie im gemeinsamen Block CBLK verarbeitet werden. Nicht nur die ungeradzahligen Eingänge erfordern jedoch eine solche Paarbildung, sondern auch die Eingabe Y1 muß mit 2 multipliziert werden, um sicherzustellen, daß die geeigneten Eingabewerte am gemeinsamen Block CBLK vorliegen. Der gemeinsame Vorblock PREC enthält daher einen 2-Eingabe-Mulitplex-Signalspeicher C10, C54, C32 und C76 ("mux") für jeden Eingabewert. Ein Eingang zum 2-Eingabe-mux- Signalspeicher wird folglich direkt mit den unverarbeiteten Eingabewerten verbunden, während der andere Eingang von den Lösungsaddierern empfängt und für die Eingabe Y1 vom 2-Lösungsmultiplizierer dient. Die korrekt gepaarten oder ungepaarten Eingänge können daher am gemeinsamen Block CBLK auf einfache Weise durch simples Schalten der Multiplex-Signalspeicher zwischen ihren beiden Eingängen präsentiert werden.
Wie Fig. 2 darstellt, lösen der 2-Multiplizierer und die Multiplizierer D1, D3, D5 und D7 vorzugsweise ihre Ausgaben, d. h. sie erzeugen Ergebnisse, in denen die Übertragungsbits hinein addiert wurden, um eine komplette Summe zu erzeugen. Dies stellt sicher, daß die Ausgänge der Multiplizierer die gleiche Sammelleitungsbreite aufweisen, wie die nicht multiplizierten Eingänge in den entsprechenden parallelen Datenwegen.
Die bevorzugte Ausführungsform des gemeinsamen Blocks enthält ferner jeweils einen "unechten" Addierer und einen "unechten" Subtrahierer in den weiteren Datenwegen für Y[1,0] und Y[5,4]. Diese Vorrichtungen wirken zum Kombinieren der beiden Eingaben (im Falle des unechten Subtrahierers nach der 2's-Komplimentierung des einen Eingangs) in einer derartigen Weise, daß sie als parallele Ausgaben durchlaufen. In diesen Fällen ist die eine Eingabe manipuliert, als wenn sie Übertragsbits enthalten würde, welche im nachfolgenden Verarbeitungsschritt aufaddiert werden. Die entsprechende Addition und Subtraktion wird daher durchgeführt, obwohl sie verzögert ist.
Diese Technik verringert die erforderlichen Ressourcen in den oberen beiden Datenwegen, da ein Endwertaddierer/-subtrahierer für diese Vorrichtungen nicht realisiert werden muß. Diese "Kombinierer" wirken daher als Addierer und Subtrahierer und können entweder als einfache Verbinder zur nächsten Vorrichtung (für die Addition) oder als eine Reihe von Inverter (für die Subtraktion) realisiert werden, welche geringe oder keine zusätzlichen Schaltkreise erfordern.
Die Verwendung von derartigen Kombinierern bedeutet auch, daß die Ausgänge der einleitenden Addierer und Subtrahierer im gemeinsamen Block CBLK alle die gleiche Breite aufweisen und kompatibel mit den Ausgängen der übertragssparenden Addierer/Subtrahierer sein werden, die in den unteren beiden Datenwegen vorgesehen sind, mit denen sie Eingaben zu den nachfolgenden Lösungsaddierern und -subtrahierern im gemeinsamen Block CBLK bilden.
Wie oben erläutert, werden die geradzahligen Eingaben in dieser bevorzugten Ausführungsform der Erfindung separat von den ungeradzahligen verarbeitet. Es wird angenommen, daß die ungeradzahligen Eingaben zuerst verarbeitet werden. Ein in Fig. 2 nicht dargestellter Überwachungssteuerungsschaltkreis beaufschlagt die ungeradzahligen Eingabewörter dann auf den gemeinsamen Vorblock PREC und wählt die unteren Eingaben (aus der Sicht in Fig. 2) der Mulitplex-Signalspeicher C10, C54, C32 und C76, die dann die gepaarten Werte p0 bis p3 (siehe Fig. 1 und die Definition von p(n) wie oben erläutert) speichern. Die Signalspeicher Lh0, Lh1, Lh3 und Lh2 werden dann aktiviert, um die jeweiligen Werte H0, H1, H3 und H2 zu speichern.
Der Überwachungssteuerungsschaltkreis speichert dann und wählt dann die oberen Eingaben der Zwei-Eingangs-Mulitiplex-Signalspeicher C10, C54, C32 und C76 im gemeinsamen Vorblock PREC und beaufschlagt die geradzahligen Eingabewörter auf diese Signalspeicher. Da die geradzahligen Eingaben verwendet werden, um die Werte von g0 bis g3 zu bilden, öffnet der Überwachungssteuerungsschaltkreis dann auch die Signalspeicher Lg0 bis Lg3 im gemeinsamen Nachblock POSTC, welcher die g(k)- Werte speichert.
Wenn die. g(k)- und h(k)-Werte einmal gespeichert sind, gibt der gemeinsame Nachblock POSTC die hochwertigen Ausgabesignale X7, X6, X5 und X4 durch Umschalten der Lösungsaddierer/-subtrahierer in den Subtraktionsmodus aus. Die niederwertigen Ausgabesignale X3, X2, X1 und X0 werden dann durch Umschalten der Lösungsaddierer/-subtrahierer in den Additionsmodus erzeugt. Es ist zu bemerken, daß die Ausgabedaten in einer willkürlichen Ordnung, darunter eine natürliche Ordnung, präsentiert werden können.
Die dargestellte bevorzugte Multiplex-Realisierung in der weitestgehend vereinfachten, schematischen Form gemäß Fig. 2 führt die gleichen Berechnungen aus, wie die nicht multiplexte Struktur, die in Fig. 1 dargestellt ist. Die Anzahl von Addierern, Subtrahierern und Multiplizierern im gemeinsamen Block CBLK ist jedoch auf die Hälfte beschnitten und die Anwendung von unechten Addierern/Subtrahierern verringert weiter die Komplexität des teuren arithmetischen Schaltkreises.
Fig. 3 stellt die Hauptkomponenten und Datenleitungen einer tatsächlichen Realisierung des IDCT-Schaltkreises gemäß der Ausführungsform dar. Die Hauptkomponenten enthalten den Vorblockschaltkreis PREC, den gemeinsamen Blockschaltkreis CBLK und den gemeinsamen Nachblock POSTC. Das System enthält ferner eine Steuereinheit CNTL, welche den gemeinsamen Vorblock PREC und gemeinsamen Nachblock POSTC entweder direkt oder indirekt mit Eingabe-, Zeitsteuerungs- und Steuersignalen beaufschlagt.
Bei der bevorzugten Ausführungsform der Erfindung sind die Eingabe- und Ausgabesignale (jeweils Y0 bis Y7 und X0 bis X7) 22 Bits breit. Tests haben angezeigt, daß dies die minimal mögliche Breite ist, bei der immer noch eine akzeptable Genauigkeit gemessen an bestehenden Industriestandards erzielt wird. Wie nachfolgend noch detaillierter erläutert ist, wird diese minimale Breite teilweise dadurch erreicht, daß bestimmte Übertragswörter in ausgewählten arithmetischen Vorrichtungen absichtlich entweder auf eine "1" oder eine "0" gesetzt werden. Diese Bit-Manipulation wird entsprechend einer Einstellung von bestimmten Datenwörtern als ein Ergebnis einer statistischen Analyse der Ergebnisse des IDCT-Systems gemäß der Ausführungsform ausgeführt, nachdem die Ausführungsform für eine IDCT-Transformation mit bekannten Eingabe- Testdaten verwendet wurde. Durch Beaufschlagen bestimmter Bits mit vorbestimmten Werten wurde entdeckt, daß die Effekte von Rundungs- und Streichfehlern derart reduziert werden können, daß die räumlichen Ausgabedaten des IDCT-Systems so hergestellt werden können, daß sie nur wenig von den bekannten, "korrekten" räumlichen Daten abweichen. Die Erfindung ist jedoch gleichermaßen auf andere Datenwortlängen anwendbar, da die verwendeten Komponenten im Schaltkreis gemäß dieser Ausführungsform alle für unterschiedliche Bus-Breiten, welche bekannte Verfahren verwenden, geeignet sind.
Obwohl alle vier Eingaben, die zusammen verarbeitet werden, gleichzeitig in den gemeinsamen Vorblock PREC auf 88 parallelen Leitungen (4 · 22) eingegeben werden könnten, werden die Pixel-Wörter typischerweise einmal zu einem Zeitpunkt der seriellen Datenübertragung konvertiert. Gemäß dieser Ausführungsform werden die Eingabedatenwörter daher vorzugsweise alle seriell über einen einzelnen, 22-Bit-Eingabebus übertragen, und jedes Eingabewort wird aufeinander folgend an einem geeigneten Eingabepunkt im Datenweg gespeichert. In Fig. 3 ist der 22-Bit-Eingabedatenbus mit T_IN[21 : 0] bezeichnet.
In den Figuren und in der nachfolgenden Beschreibung werden die Breiten der Mehrfach-Bit Signale mit dem höherwertigen Bit links eines Doppelpunkts ":" und das weniger signifikante Bit (least significant bit, LSB) rechts vom Doppelpunkt angezeigt. Das Eingabesignal T_IN[21 : 0] ist z. B. 22 Bits breit, wobei die Bits von 0 bis 21 numeriert sind. Ein einzelnes Bit wird als eine einzelne Zahl innerhalb eckiger Klammem identifiziert. Dabei bedeutet T_IN[1] das nächstliegende zum am wenigsten signifikanten Bit des Signals T_IN.
Die folgenden Steuersignale werden verwendet, um die Arbeitsweise des gemeinsamen Vorblocks PREC in der bevorzugten Ausführungsform der Erfindung zu steuern:
IN_CLK, OUT_CLK: Das System gemäß dieser Ausführungsform verwendet vorzugsweise ein nicht-überlappendes Zweiphasentaktsignal. Die Signale IN_CLK und OUT-CLK sind dementsprechend jeweils die Signale für die Eingabe- und Ausgabetaktsignale. Diese Taktsignale werden verwendet, um wechselnde Spalten von Signalspeichern bzw. Latches dazu zu befähigen, die Werte der Eingabe-, Zwischen- und Ausgabesignale zu halten.
LATCH10, LATCH54, LATCH32, LATCH76: Vorzugsweise wird ein 22-Bit- Wort zu einem Zeitpunkt bzw. einzeln in das System eingeben. Andererseits werden vier Eingabesignale gleichzeitig verarbeitet. Jedes Eingabesignal muß daher an ihrem geeigneten Ort in der Architektur gehalten bzw. gespeichert werden, bevor die anderen drei Eingabewörter verarbeitet werden. Diese gespeicherten Signale werden verwendet, um die jeweiligen Eingabespeicher frei zu geben. Das Signal LATCH54 wird z. B. zuerst verwendet, um das Eingabesignal Y5 und später das Eingabesignal Y4 zu speichern, welches in den gemeinsamen Vorblock PREC am gleichen Punkt wie das Eingabesignal Y5 eintritt (vgl. Fig. 2), jedoch während eines nachfolgenden Prozeßschritts.
LATCH: Sobald die vier gerad- oder ungeradzahligen Eingabesignale im gemeinsamen Vorblock PREC gespeichert sind, werden sie vorzugsweise zur gleichen Zeit zu einer nachfolgenden Reihe von Signalspeichern verschoben. Das Signal LATCH wird verwendet, um eine zweite Reihe von Eingabesignalspeichern freizugeben, welche die vier Eingabewerte halten, die durch die arithmetischen Vorrichtungen im gemeinsamen Vorblock PREC zu bearbeiten sind.
SEL_BYP, SEL_P: Wie Fig. 2 darstellt, sollten die geradzahligen Eingabesignale, welche in den Signalspeichern C10, C54, C32 und C76 gespeichert sind, diejenigen sein, welche die Addierer und den 2-Lösungsmultiplizierer umgehen. Die ungeradzahligen Eingabesignale müssen jedoch zuerst gepaart werden, um die gepaarten Eingaben p(n) zu bilden, und die Signale Y1 müssen mit 2 multipliziert werden. Das Steuersignal SEL_BYP wird verwendet, um die nicht gruppierten, umgeleiteten Eingabesignale (die geradzahligen Eingaben) auszuwählen, während das Signal SEL_P aktiviert wird, um die gepaarten Eingabesignale auszuwählen. Diese Signale werden daher verwendet, um Verknüpfungen zu steuern, welche als Multiplexer dienen, um die korrekten Signale zu den Ausgabesignalspeichern des gemeinsamen Vorblocks PREC durchzulassen.
Wie oben erläutert ist, führt nicht die Anordnung der Eingaben in strikt aufsteigender Ordnung zu einer vereinfachten "Schmetterlings"-Bus-Struktur mit hoher Durchgangseffizienz. Wie oben erläutert ist, werden die ungeraden Eingaben zuerst vorzugsweise als eine Gruppe auf den gemeinsamen Vorblock aufgebracht, wobei sie von den geradzahligen Eingaben gefolgt werden, und wobei jede Ordnung innerhalb jeder ungeraden oder geraden Gruppe verwendet werden kann. Jede Ordnung der Eingaben kann verwendet werden, wobei geeignete Signalspeicheranordnungen separat oder wenigstens in separaten Bereichen des Schaltkreises vorgesehen sind, um die ungeradzahligen und geradzahligen Eingaben zu verarbeiten.
Der Überwachungssteuerungsschaltkreis erzeugt auch Zeitsteuerungs- und Steuersignale für den gemeinsamen Nachblock POSTC. Diese Steuersignale sind die folgenden:
EN_BH, EN_GH: Betrachtet man im Moment Fig. 1, so sind die Ausgaben vom gemeinsamen Block CBLK nach der Verarbeitung der ungeradzahligen Eingaben als H0, H1, H3 und H2 gezeigt. Diese Signale werden dann zum jeweiligen Koeffizienten- Multiplizierer d1, d3, d7 und d5 im ersten gemeinsamen Nachblock POSTC 1 gesandt. Das Signal EN_BH wird verwendet, um die Signalspeicher zu befähigen, die Signale entsprechend H0 bis H3 zu halten. Das Signal EN_GH wird verwendet, um die Signalspeicher zu befähigen, die Werte g0 bis g3 zu halten, wie auch die Signalspeicher, welche die h0- bis h3-Werte halten, nachdem sie in den Koeffizienten-Multiplizierern multipliziert wurden.
ADD, SUB: Wie Fig. 2 darstellt, enthält die Ausführungsform eine Speichereinheit bzw. Bank von Lösungsaddierern/-subtrahierern, welche g(k)- und h(k)-Werte summieren und differenzieren, um jeweils die niederwertigen und hochwertigen Ausga ben zu bilden. Die Signale ADD und SUB werden verwendet, um die Lösungsaddierer/- subtrahierer jeweils in die Additions- und Subtraktionsmoden zu setzen.
EN_O: Dieses Signal wird verwendet, um die Ausgabesignalspeicher zu befähigen, die Ergebnisse von den Lösungsaddierern/-subtrahierern zu speichern.
MUX_OUT70, MUX_OUT61, MUX_OUT43, MUX_OUT52: Die Ausgabedaten des Systems werden vorzugsweise über einen einzelnen 22-Bit-Ausgabebus derart übertragen, daß nur ein Ausgabewert (X0 bis X7) zu einem Zeitpunkt übertragen wird. Diese Signale werden aufeinanderfolgend aktiviert, um auszuwählen, welcher der vier gespeicherten Ausgabewerte in einem abschließenden Ausgabesignalspeicher zu speichern ist. Diese Signale wirken daher als die Steuersignale für einen 4-zu-1-Multiplexer.
T_OUT[21 : 0]: Diese Kennzeichnung bezeichnet das 22-Bit-Ausgabesignal des gemeinsamen Nachblocks POSTC.
Die Ausgabesignale vom gemeinsamen Vorblock PREC werden gespeichert, um die Eingabesignale des gemeinsamen Blocks CBLK zu bilden. In Fig. 3 werden die Ausgabesignale des gemeinsamen Vorblocks PREC als die vier 22-Bit-Datenwörter CI10[21 : 0], CI54[21 : 0], CI32[21 : 0], CI76[21 : 0] dargestellt, welche jeweils die Eingabesignale IN[0], IN[1], IN[3] und IN[2] zum gemeinsamen Block CBLK werden.
Wie Fig. 3 zeigt, werden die vier 22-Bit-Ergebnisse vom gemeinsamen Block CBLK parallel als Ausgabesignale OUT0[21 : 0], OUT1[21 : 0], OUT3[21 : 0] und OUT2[21 : 0] übertragen, welche dann als die Eingabesignale des gemeinsamen Nachblocks POSTC als CO70[21 : 0], CO61[21 : 0], CO43[21 : 0] und CO52[21 : 0] gespeichert werden.
Man sollte insbesondere erkennen, daß keine Steuersignale für den gemeinsamen Block CBLK erforderlich sind. Aufgrund der ungewöhnlichen Struktur des IDCT-Systems in diesem Beispiel kann der gemeinsame Block der Operationen als reine Logikoperationen ohne eine Erfordernis für Takt-, Zeitsteuerungs- oder Steuersignale ausgeführt werden. Dies verringert die Komplexität der Vorrichtung weiter. Man sollte erkennen, daß bestimmte Anwendungen (insbesondere jene, in denen eine Menge Zeit zur Durchführung aller benötigten arithmetischen Operationen auftritt) des gemeinsamen Vorblocks PREC und gemeinsamen Nachblocks POSTC ebenfalls geordnet werden können, um ohne Takt-, Zeitsteuerungs- oder Steuersignal zu arbeiten.
Fig. 4 ist ein Blockdiagramm des gemeinsamen Vorblocks PREC. In dieser und den folgenden Figuren zeigt die Notation "S1[a], S2[b], ..., SM[Z]", wobei S eine willkürliche Signalkennzeichnung ist und a, b, ..., z Ganzzahlen im Bereich der Busbreite der Signale sind, an, daß die gewählten Bits a, b, ..., z der Signale S1, S2, ..., SM parallel über den gesamten Bus übertragen werden, wobei die am signifikantesten Bits (most significant bits, MSB's) die ausgewählten Bits "a" des Signals S1 sind, und die am wenigsten signifikanten Bits (least significant bits, LSB's) die ausgewählten Bits "z" des Signals SM sind. Die gewählten Bits müßten nicht individuelle Bits sein, sondern es können auch ganze oder teilweise Mehrfach-Bit-Wörter mit anderen einzelnen Bits oder kompletten oder teilweisen Mehrfach-Bit-Wörtern übertragen werden. In den Figuren wird das Symbol S durch die entsprechende Signalkennzeichnung ersetzt.
Zum Beispiel ist in Fig. 4 ein 2-Multiplizierer als R2MUL gezeigt. Die "Sicherungs-" oder "ungelöste Summen"-Ausgabe von diesem nicht lösenden Multiplizierer wird als das 21-Bit-Wort M5S[20 : 0] angezeigt. Die "Übertrags"-Ausgabe vom Multiplizierer R2MUL wird als das 22-Bit-Wort M5C[21 : 0] angezeigt, welches über den Bus zum "b"-Eingang eines übertrags-sichernden Lösungsaddierers M5A übertragen wird (Man rufe sich in Erinnerung, daß eine "0" als ein MSB zu den weniger signifikanten 21 Bits der Sicherungsausgabe eingefügt wird, bevor sie jedoch zu einem "a"-Eingang des Lösungsaddierers M5A aufgebracht werden. Dies ist in Fig. 4 durch die Notation GND; M5S[20 : 0] angezeigt). Mit anderen Worten wird die der MSB-Eingabe entsprechende Leitung zum Addierer M5A durch Verbinden mit der Masse GND dazu veranlaßt, eine "0" zu sein.
Um zu verstehen, warum eine "0" daher als das 22. Bit des "Summen"-Ausgangs eingefügt wird, ist zu beachten, daß das Übertragswort üblicherweise ebenfalls n-Stellen aufweist, wenn die Teilsumme einer Multiplikation n-Stellen breit ist. Beim Addieren des Übertragsworts zur Teilsumme wird das Übertragswort jedoch relativ zur Teilsumme eine Stelle nach links verschoben. Das Übertragswort erstreckt sich daher auf n + 1 Stellen, mit einem gültigen Datenbit in der n + 1ten Position und einer "0" in der weniger signifikanten Position (da nichts vor dieser Position ist, um ein Übertragsbit in der Einheitenstelle herzustellen). Wenn diese beiden Wörter als Eingaben zu einem binären Lösungsaddierer verwendet werden, muß Sorge getragen werden, um sicher zu stellen, daß die Bits (Anzeigestellen) des Übertragsworts genau zu den entsprechenden Bits der Teilsumme ausgerichtet sind. Dies stellt auch sicher, daß der Dezimalpunkt (auch wenn er nur als Ganzzahlenarithmetik eingebracht ist) in beiden Wörtern "ausge richtet" bleibt. Wenn man annimmt, daß die Eingaben zum Addierer n + 1 Bit breit sind, kann eine "0" in das höchstwertige Bit von allen n-Bit positiven Teilsummenwörtem eingefügt werden, um eine n + 1 Bit Eingabe zu schaffen, welche mit dem Übertragswort an der anderen Eingabe ausgerichtet ist.
Wie oben erläutert ist, werden die vier Eingaben, welche gleichzeitig im gemeinsamen Vorblock PREC verarbeitet wurden, über den Eingangsbus T_IN[21 : 0] übertragen. Dieser Eingangsbus ist mit den Eingängen der vier Eingangssignalspeicher IN10L, IN54L, IN32L und IN76L verbunden. Jeder der jeweiligen Signalspeicher ist nur dann freigegeben, wenn das Eingabetaktsignal IN_CLK und das entsprechende Signalspeicher-Auswahlsignal LATCH10, LATCH54, LACTH32 und LATCH76 hoch sind. Die vier Eingaben können daher in ihren jeweiligen Eingabesignalspeichern in vier Perioden des IN_CLK-Signals durch aufeinanderfolgende Aktivierung der Signalspeicher-Freigabesignale LATCH10, LATCH54, LATCH32 und LATCH76 gespeichert werden. Während dieser Zeit sollte das LATCH-Signal niedrig sein (oder auf einer unterschiedlichen Phase), um dadurch die Eingabesignalspeicher IN10L, IN54L, IN32L und IN76L freizugeben, um die vier Eingabewerte zu stabilisieren und zu speichern.
Ein Beispiel für die Zeitsteuerung der Signalspeicher ist in Fig. 7a dargestellt. Sind die vier Eingabesignale einmal in der bevorzugten Ordnung gespeichert, so werden sie zu einer zweiten Bank von Signalspeichern L10L, L54L, L32L und L76L weitergeleitet. Diese zweiten Signalspeicher sind freigegeben, wenn die Signale OUT_CLK und LATCH hoch sind. Diese Zeitsteuerung der Signale ist ebenfalls in Fig. 7a dargestellt.
Zu bemerken ist, daß das System den Empfang von allen acht Eingabewörtern nicht verzögern muß. Wenn alle der geraden oder ungeraden Eingabewörter in IN10L, IN54L, IN32L und IN76L empfangen und gespeichert sind, können sie in der nächsten Hochperiode des OUT_CLK zu den Signalspeichern L10L, L54L, L32L und L76L übertragen werden. Dies gibt die IN-Signalspeicher frei, welche beginnen können, um die anderen vier Eingabesignale ohne Verzögerung zur nächsten aufsteigenden Flanke des IN_CLK aufzunehmen.
Die zweistellige Kennungsnotation [10, 54, 32, 76], welche für die in den Figuren dargestellten verschiedenen Komponenten verwendet wird, zeigt an, daß ungeradzahlige Signale zuerst verarbeitet werden und dann von den geradzahligen Signalen in einem nachfolgenden Durchlauf durch die Struktur gefolgt werden. Wie oben erläutert ist, ist diese Ordnung nicht notwendig.
Sind die vier Eingabesignale einmal in geeigneter Ordnung in den zweiten Signalspeichern L10L, L54L, L32L und L76L gespeichert, so werden die entsprechenden Werte entweder als Eingaben zu den Ausgangs-Signalspeichern C10L, C54L, C32L und C76L bei Aktivierung des gewählten Umlenkungssignals SEL_BYP weitergeleitet, oder sie werden als gepaarte und multiplizierte Eingaben zu den gleichen Ausgangs-Signalspeichern weitergeleitet bei einer Aktivierung des "wähle p"-Signals SEL_P. Mit anderen Worten werden alle Signale über arithmetische Vorrichtungen sowohl direkt als auch indirekt zu den Ausgangs-Signalspeichern C10L, C54L, C32L und C76L des gemeinsamen Vorblocks PREC hindurch geführt. Die geeigneten Werte werden jedoch in diese Signalspeicher durch Aktivierung des "wähle Umleitung"-Signals SEL_BYP (für die geradzahligen Eingaben Y0, Y2, Y4 und Y6) oder das "wähle p"-Signal SEL_P geladen (für die ungeradzahligen Eingaben Y1, Y3, Y5 und Y7). Die gewünschte Zeitsteuerung und Ordnung von diesen und anderen Steuersignalen wird auf einfache Weise in einer herkömmlichen Art mittels einer geeigneten Konfiguration und/oder einer [mikro-]Programmierung der Steuereinheit bzw. des Kontrollers CNTL ausgeführt.
Der oberste Eingabewert am Ausgang des Signalspeichers L10L wird zuerst zum 2-Multiplizierer R2MUL und dann zum Lösungsaddierer M5A durchgeleitet, wie oben angezeigt wurde. Die Ausgabe vom Lösungsaddierer M5A wird als M5[21 : 0] gezeigt, was dem in Fig. 1 gezeigten 22-Bit-Wert p0 entspricht. Das 22-Bit-Signal M5[21 : 0] ist daher das Äquivalent der Lösungsmultiplikation der Ausgabe des Signalspeichers L10L mit 2. Die Ausgaben von den anderen drei Signalspeichern L54L, L32L und L76L werden jeweils ebenfalls zu entsprechenden Ausgabesignalspeichern C54L, C32L und C76L übertragen, sowohl direkt über 22-Bit-Signalspeichersammelleitungen LCH54[21 : 0] LCH32[21 : 0] und LCH76[21 : 0], als auch indirekt zu den Ausgabesignalspeichern über jeweilige Lösungsaddierer P2A, P1A und P3A.
Jeder Lösungsaddierer P2A, P1A und P3A weist zwei Eingänge "a" und "b" auf. Beim Addierer P2A wird eine Eingabe vom Signalspeicher L32L empfangen und die andere Eingabe wird vom Signalspeicher L54L empfangen. Für Eingabewerte Y5 (gespeichert in L54L) und Y3 (gespeichert in L32L) wird die Ausgabe vom Addierer P2A daher gleich Y5 + Y3, was gemäß dem oben gezeigten gleich zu p(2) ist. Die Addierer "paaren" daher die ungeradzahligen Eingaben, um die gepaarten Eingabewerte p(1), p(2) und p(3) zu bilden. Natürlich werden die geradzahligen Eingabesignale, welche in L54L, L32L und L76L gespeichert sind, jeweils ebenfalls durch die Lösungsaddierer P2A, P1A und P3A hindurch geführt, wobei die sich ergebenden p-"Werte" nicht zu den Ausgabesignalspeichern C54L, C32L und C76L durchgeführt werden, da das "wähle p"-Signal SEL_P nicht für geradzahlige Eingaben aktiviert wird.
Die in den Ausgabesignalspeichern C10L, C54L, C32L und C76L bis zur Aktivierung des Eingabetaktsignals IN_CLK gespeicherten Werte werden daher gleich zu jeder der geradzahligen Eingaben Y0, Y2, Y4 und Y6 oder den gepaarten Eingabewerten P0, P1, P2 und P3 für die ungeradzahligen Eingaben sein. Man sollte sich in Erinnerung rufen, daß die Eingabe Y(1) mit dem Wert Y(-1) "gepaart" ist, was als Null angenommen wird. In Fig. 4 ist diese Annahme dadurch realisiert, daß nichts zum Wert Y1 addiert wird; vielmehr wird Y1 nur mit 2 multipliziert, wie in den Fig. 1 und 2 gezeigt ist.
Fig. 5 stellt eine bevorzugte Architektur des gemeinsamen Blocks CBLK gemäß der Ausführungsform dar. Aufgrund der unterschiedlichen Multiplikationen und Additionen in den verschiedenen Systemblocks ist es notwendig oder vorteilhaft, die Eingabewerte für einen gemeinsamen Block vor der Durchführung der verschiedenen Berechnungen herunter zu skalieren; dies stellt eine gleichmäßige Position des Dezimalpunkts (welcher für die Ganzzahlenarithmetik impliziert ist) für die entsprechenden Eingaben zu den verschiedenen arithmetischen Vorrichtungen im System sicher.
Die Eingabewerte IN0[21 : 0] und IN1[21 : 0] sind entsprechend um einen Faktor von vier herab skaliert, was in der digitalen Arithmetik einer Rechtsverschiebung um zwei Bits entspricht. Um das Vorzeichen der Zahl in der binären Darstellung zu bewahren (positive Werte positiv und negative Werte negativ zu halten), müssen die signifikantesten Bits (MSB) dann in die beiden signifikantesten Bits des sich ergebenden, nach rechts verschobenen Werts kopiert werden; dieser Vorgang ist als "Vorzeichenerweiterung" bekannt. Dementsprechend wird der Eingabewert IN0 mit der Vorzeichenerweiterung um zwei Bits herunter verschoben, um den verschobenen Eingabewert zu bilden, der als IN0[21], IN0[21] und IN0[21 : 2] bezeichnet wird. Der Eingabewert IN1[21 : 0] wird gleichermaßen um zwei Stellen vorzeichenerweitert. Die Eingabewerte IN3 und IN2 (welche jeweils den Eingaben Y[3,2] und Y[7,6] entsprechen) werden mit der Vorzeichenerweiterung um eine Position nach rechts verschoben. Die dritte Eingabe ist daher als IN3[21], IN3[21 : 1] verschoben und erweitert. Die Eingabe IN2 ist gleichermaßen verschoben und erweitert, um IN2[21] und IN2[21 : 1] zu bilden. Diese einstelligen Verschiebungen entsprechen einer abgeschnitten Division um einen Faktor von zwei.
Wie Fig. 2 zeigt sind die Eingaben IN3 und IN2 jene, welche mit den skalierten Koeffizienten c1s und c3s multipliziert werden müssen. Jede Eingabe IN3 und IN2 muß mit jedem der skalierten Koeffizienten multipliziert werden. Wie Fig. 5 darstellt, wird dies durch die vier Konstant-Koeffizient-Übertragssicherungs-Multiplizierer MULC1S, MULNC1S, MULC3S3 und MULC3S2 realisiert. Man sollte bemerken, daß der Grundmultiplizierer für die IN2 ein invertierender Multiplizierer MULNCIS ist, d. h. seine Ausgabe dem negativen des Werts der Eingabe entspricht, welche mit der Konstante C1S multipliziert wird. Der in C76 gespeicherte Wert wird daher von dem in C32 gespeicherten Wert abgezogen (nach der Multiplikation um C3S). Durch Bereitstellen des invertierenden Multiplizierers MULNC1S wird diese Subtraktion durch Addieren des negativen entsprechenden Werts realisiert, was äquivalent zur Bildung der Differenz ist. Dies ermöglicht die Verwendung eines identischen Schaltkreises für die nachfolgenden Addierer, wobei jedoch ein nicht invertierender Multiplizierer mit einem nachfolgenden Subtrahierer verwendet werden kann.
In der dargestellten Ausführungsform sind vier Kosinus-Koeffizienten-Multiplizierer MULC1S, MULNC1S, MULC3S3 und MULC3S2 enthalten. Wenn jedoch Anordnungen für Signale bereitgestellt werden, damit diese separat durch die Multiplizierer hindurch laufen, können die erforderlichen Multiplikationen unter Verwendung von nur zwei Multiplizierern realisiert werden, einen für den c1s Koeffizienten und einen für den c3s Koeffizienten.
Die Multiplizierer MULC1S, MULNC1S, MULC3S3 und MULC3S2 sind vorzugsweise von der übertrags-sichernden Bauweise, was bedeutet, daß sie zwei Ausgabewörter erzeugen, eines entsprechend dem Ergebnis der verschiedenen Additionsreihen, welche im Hardware-Multiplizierer ausgeführt werden und einem anderen entsprechend den erzeugten Übertragsbits. Die Ausgaben der Multiplizierer werden dann als Eingaben zu einem der beiden vier-Eingangs-Lösungsaddierer BT2 und BT3 verbunden.
Nur zur Vereinfachung der Darstellung sind fünf der Ausgangssammelleitungen für den Multiplizierer so dargestellt, als seien sie nicht mit den entsprechenden Eingangssammelleitungen der Addierer verbunden. Diese Verbindungen sind mit der gleichen Kennzeichnung am jeweiligen Ausgang und Eingang zu verstehen und dargestellt. Daher ist die Sicherungsausgabe M1S[20 : 0] des Multiplizierers MULC1S mit den unteren 21 Bits des "sichere-a" Eingangs "sa" des Addierers BT3 verbunden.
In Fig. 5 sind fünf der Eingänge zu den Addierern BT2 und BT3 als "geteilt" dargestellt. Zum Beispiel ist der "ca" Eingang des Addierers BT2 gezeigt, als Weise er IN3[21] über M3C[20 : 0] auf. Dies ist so zu interpretieren, daß es bedeutet, daß vom 22- Bit-Eingabewort IN3[21] als das MSB eingegeben wird, wobei die 21 Bits des M3C[20 : 0] als die weniger signifikanten 21 Bits eingegeben werden. Gleichermaßen ist die "sa" (die "sichere-a" Eingabe) des gleichen Addierers gezeigt, als sei sie GND, GND über M3S[19 : 0]. Dies bedeutet, daß zwei Nullen als die beiden signifikantesten Bits dieses Eingabeworts beigefügt sind. Derart angehängte Bits stellen sicher, daß die genauen 22-Bit breiten Eingabewörter mit dem richtigen Zeichen gebildet werden.
Die übertrags-sichernden Addierer BT2 und BT3 addieren die Übertrags- und Sicherungswörter der beiden unterschiedlichen 22-Bit-Eingaben, um ein 22-Bit-Ausgabesicherungswort T3S[21 : 0] und ein 21-Bit-Ausgabeübertragswort T3C[21 : 1] zu bilden. Der Eingang zu jedem Addierer ist daher 88 Bit breit und der Ausgang von jedem Addierer ist 43 Bit breit. Wie Fig. 2 anzeigt, ist der Ausgang des Signalspeichers C10 mit dem Ausgang des Signalspeichers C54 im obersten Datenweg vor der Addition mit dem Ausgang des Übertrags-Sicherungsaddierers BT3 kombiniert. Diese "Kombination" ist jedoch nicht vor dem Erreichen des nachfolgenden Addierers im oberen Datenweg erforderlich. Folglich ist der verschobene und vorzeichenerweiternde Eingabewert IN0 mit der oberen Übertragseingabe verbunden, wie Fig. 5 zeigt.
Der obere Übertragseingang des Addieres CS0 ist mit dem verschobenen und vorzeichenerweiterten Eingabewert IN0 verbunden und die verschobene und vorzeichenerweiterte Eingabe IN1 ist als obere Sicherungseingabe des gleichen Addierers angeschlossen. Mit anderen Worten werden IN0 und IN1 später im Addierer CS0 addiert.
Die Bezeichnung "unechter" Addierer/Subtrahierer, welche in Fig. 2 verwendet ist, zeigt daher an, welche Operation ausgeführt werden muß, obwohl diese nicht notwendigerweise an dem in Fig. 2 angezeigten Punkt durchgeführt werden muß. Gleichermaßen erfordert der in Fig. 2 dargestellte untere unechte Subtrahierer, daß die Ausgabe des Signalspeichers C54 von der Ausgabe vom Signalspeicher C10 abgezogen wird. Dies ist das Gleiche wie ein Addieren der Ausgänge von C10 zum Komplement der Ausgabe von C54.
Nochmals auf Fig. 5 bezugnehmend, wird das Komplement der Eingabe IN1 (entsprechend der Ausgabe des Signalspeichers C54 in Fig. 2) durch einen 22-Bit Eingabeinverter IN1I[21 : 0] ausgeführt (der das logische inverse von jedem Bit seiner Ein gabe, Bit für Bit, erzeugt). Das Komplement des IN1-Werts - NIN1[21 : 0] - wird zur oberen "Sicherungs-"Eingabe des Addierers CS1 weitergeleitet, wobei die entsprechende obere "Übertrags-"Eingabe das verschobene und vorzeichenerweiterte IN0 ist. Der obere Abschnitt des Addierers CS1 führt daher die Subtraktion entsprechend IN0 minus IN1 aus.
In den unteren beiden in Fig. 2 dargestellten Datenwegen werden Lösungssubtrahierer anstelle der in den oberen beiden Datenwegen gezeigten Lösungsaddierer an den Ausgängen des gemeinsamen Blocks CBLK verwendet. Jeder Lösungsaddierer oder - subtrahierer ist äquivalent zu einem übertrags-sichernden Addierer oder Subtrahierer, der durch einen Lösungsaddierer gefolgt wird. Dies ist in Fig. 5 dargestellt. Die Subtrahierer CS2 und CS3 weisen als ihre Eingaben die verarbeiteten Werte von IN0 bis IN3 gemäß der in Fig. 2 gezeigten Verbindungsstruktur auf.
Die 22-Bit Übertrags- und Sicherungsausgaben von jedem der Addierer/Subtrahierer CS0 bis CS3 werden in den Lösungsaddierern RES0 bis RES3 aufgelöst. Das Lösen der Übertrags- und Sicherungsausgaben ist auf dem Gebiet des digitalen Designs weithin verstanden und wird daher hier nicht in näherem Detail beschrieben. Wie Fig. 5 darstellt, werden die Sicherungsausgaben von den Übertrags-Sicherungs- Addierern/-Subtrahierern CS0 bis CS3 direkt als 22-Bit-Eingaben zum "a"-Eingang des entsprechenden Lösungsaddierers RES0 bis RES3 weitergeleitet.
Wie weithin bekannt ist, wird das 2's-Komplement einer binären Zahl durch Invertieren von jedem seiner Bits (verändern aller "1er" zu "0ern" und umgekehrt) und anschließenden Addieren von "1" gebildet. Zu bemerken ist, daß die "1" unmittelbar nach der Bit-Umkehrung oder später addiert werden kann. Das LSB eines Übertragsworts wird immer ein "0" sein, welche in der dargestellten Ausführungsform durch Verbinden des LSB's der Übertragswörter O0C und O1C mit der Masse GND realisiert wird, wenn diese jeweils in die Lösungsaddierer RES0 und RES1 eingegeben werden. Die Addition von "1" zu den Übertragsausgaben der Subtrahierer CS2 und CS3 zur Bildung der 2's-komplementierten Werte wird jedoch durch Verbinden des LSB dieser Datenwörter O2C und O3C mit der Spannungsquelle VDD realisiert, wodurch das LSB mit "0" des Übertragsworts durch eine "1" somit "ersetzt" wird, was äquivalent zu einer Addition mit "1" ist.
Aus den oben genannten Gründen ist eine "0" als das LSB zu den 21-Bit-Übertragswörtern von den übertrags-sichernden Addierern CS0 und CS1 (durch Verbinden des LSB mit der Masse GND) angehängt und das LSB der Übertragswörter von den übertrags-sichernden Subtrahierern CS2 und CS3 wird mittels Verbinden der entsprechenden Datenleitungen mit der Spannungsquelle VDD gleich einer "1" gesetzt. Die Lösungsaddierer RES0 bis RES3 lösen daher die Ausgaben der Addierer/Subtrahierer CS0 bis CS3, um die 22-Bit-Ausgabesignale OUT0[21 : 0] bis OUT3[21 : 0] zu bilden.
Zwei Vorteile des IDCT-Schaltkreises gemäß dieser Ausführungsform sind aus Fig. 5 ersichtlich. Zum einen werden keine Steuerungs- oder Taktsignale für den gemeinsamen Block CBLK erfordert; ferner sind die Eingabesignale zum gemeinsamen Block bereits in einer derartigen Weise bearbeitet, daß sie unmittelbar auf rein logische arithmetische Vorrichtungen im gemeinsamen Block aufgebracht werden können. Zweitens kann die ganze Zeit über eine Ganzzahlenarithmetik durch die geeignete Skalierung der Datenwörter verwendet werden (oder wenigstens kann der Dezimalpunkt für alle Werte festgelegt werden). Dies vermeidet die Komplexität und Langsamkeit von Gleitkomma-Vorrichtungen mit keinen inakzeptablen Opfern hinsichtlich der Präzision.
Ein weiterer Vorteil der Ausführungsform liegt darin, daß durch die Anordnung der Eingaben in der gezeigten Weise und durch die Nutzung des symmetrischen dezimalisierten Verfahrens gemäß dieser Ausführungsform ähnliche Designstrukturen an verschiedenen Punkten in der Siliziumrealisierung verwendet werden können. Z. B. weisen die Konstant-Koeffizient-Multiplizierer MULC1S, MULC3S, MULC3S2 und MULNC1S gemäß Fig. 5 alle ähnliche Strukturen auf und empfangen Daten vom gleichen Punkt im Datenweg, so daß alle vier Multiplizierer zur gleichen Zeit arbeiten können. Dies beseitigt "Engpässe" und die Halbleiterrealisierung ist dann in der Lage, den vollen Vorteil der duplizierten, parallelen Struktur aufzugreifen. Die übertrags-sichernden Addierer BT2 und BT3 werden gleichermaßen in der Lage sein, simultan zu arbeiten, wie auch die nachfolgenden übertrags-sichernden Addierer und Subtrahierer. Diese Symmetrie hinsichtlich der Gestaltung und der effizienten gleichzeitigen Nutzung von verschiedenen Vorrichtungen ist über die gesamte Struktur gemäß der Ausführungsform üblich.
Fig. 6 zeigt die bevorzugte Anordnungsweise des gemeinsamen Nachblocks POSTC. Wie Fig. 2 zeigt, dienen die primären Funktionen des gemeinsamen Nachblocks POSTC zum Bilden der h0 bis h3-Werte durch Multiplizieren der Ausgaben des gemeinsamen Blocks mit den Koeffizienten d1, d3, d5 und d7; zum Addieren der Werte g(k) und h(k), um die niederwertigen Ausgaben zu bilden; und zum Subtrahieren der Werte h(k) von den entsprechenden Werten g(k), um die höherwertigen Ausgaben zu bilden. Nun wird sowohl auf Fig. 2 als auch auf Fig. 6 Bezug genommen, gemäß denen der gemeinsame Nachblock POSTC die entsprechenden Ausgaben des gemeinsamen Blocks CBLK in Signalspeichern BH0L, BH1L, BH3L und BH2L speichert, wenn die BH-Signalspeicher freigegeben sind, wobei der Steueningsschaltkreis die EN_ BH-Signale auf Hoch setzt, und das Ausgabetaktsignal OUTC_CLK-Signal auf Hoch geht. Die Werte g(k), g0 bis g3 werden in entsprechenden Signalspeichern G0L, G1L, G3L und G2L gespeichert, wenn der Steuerungsschaltkreis diese Signalspeicher über das Signal EN_GH freigibt und das Eingabetaktsignal IN_CLK auf Hoch geht.
Die verarbeiteten ungeradzahligen Eingaben, d. h. die Werte h0 bis h3 werden über die Konstant-Koeffizient-Multiplizierer D1MUL, D3MUL, D5MUL und D7MUL in die Signalspeicher H0L, H1L; H3L und H2L gespeichert, wenn die Signale EN_GH und IN_CLK hoch sind. Diese Multiplizierer multiplizieren jeweils mit d1, d3, d5 und d7. In der bevorzugten Ausführungsform sind diese Konstant-Koeffzient-Multiplizierer vorzugsweise übertrags-sichernde Multiplizierer, um die Bauweise zu vereinfachen und die Berechnungsgeschwindigkeit zu erhöhen. Wie Fig. 6 darstellt, sind die "Übertrags-" (carry "c") Ausgaben der Konstanz-Koeffizient-Multiplizierer mit bestimmten nachfolgend beschriebenen Änderungen zu den a-Eingängen der Lösungsaddierer H0A, H1A, H3A und H2A verbunden. Die "Sicherungs-" ("s") Ausgaben der Koeffizient-Multiplizierer sind in ähnlicher Weise mit bestimmten, nachfolgend beschriebenen veranlaßten Änderungen mit anderen Eingängen der entsprechenden Lösungsaddierer verbunden.
Wie Fig. 6 darstellt, wird das LSB des H0-Signals durch Verbinden der entsprechenden Leitung mit der Spannungsquelle VDD vorzugsweise dazu veranlaßt, eine "1" zu sein. Das MSB der entsprechenden "Sicherungs-" Ausgabe für H0 ist auf 0 festgelegt (mit der Masse GND verbunden), und das zweite Bit (entsprechend zu H0S[1]) ist auf "1" festgelegt. Die Datenwörter von den Übertrags- und Sicherungsausgaben des Konstant-Koeffizient-Multiplizierers D3MUL sind in ähnlicher Weise manipuliert und werden in den Lösungsaddierer H1A eingegeben. Der Vorteil dieser Manipulationen wird nachfolgend beschrieben.
Alle 22 Bits der Übertragsausgabe von den Koeffizient-Multiplizierern D7MUL und D5MUL sind direkt mit dem "a-" Eingang des entsprechenden Lösungsaddierers H3A und H2A verbunden. Das MSB von jedem "Sicherungs-" Ausgang der Multiplizierer wird durch Verbinden der entsprechenden Datenleitung mit der Masse GND dazu veranlaßt, eine "0" zu sein.
Das beschriebene IDCT-System wurde mit der oben beschriebenen CCITT-Spezifikation getestet. Aufgrund der Skalierung und anderer weithin bekannter Eigenschaften von digitalen Addierern und Multiplizierern ist etwas Präzision typischerweise während der verschiedenen Verarbeitungsstufen der Vorrichtung verloren gegangen. Die Erfinder entdeckten während einer statistischen Analyse eines Testlaufs mit einer 10.000er Probe, daß das Veranlassen der oben beschriebenen verschiedenen Bits dazu, entweder "0" oder "1" zu sein, den erwarteten Fehler der digitalen Transformation verringert. Als ein Ergebnis aus der Bit-Manipulation der Datenwörter erreichte die Ausführungsform eine akzeptable Genauigkeit unter dem CCITT-Standard bei der ausschließlichen Verwendung von 22-Bit breiten Datenwörtern, während 24 Bit gewöhnlich erforderlich sind, um eine vergleichbare Genauigkeit herzustellen.
Aufgrund der begrenzten Präzision und der Abrundungs- und Rundungsfehler besteht typischerweise eine gewisse Ungenauigkeit in jedem Datenwort in einem IDCT- System. Natürlich führt das Umändern ausgewählter. Bits eines Datenworts zu anderen, als sie als ein natürliches Ergebnis der entsprechenden Berechnungen sein würden, bewußt zur Einbringung eines "Fehlers". Die Erfinder entdeckten jedoch, daß ein hierdurch systematisch eingebrachter Fehler in ein bestimmtes Datenwort an einem bestimmten Punkt in der Hardware zu statistisch besseren Gesamtergebnissen geführt hat. Die Bit-Veränderung durch Einwirken von außen kann auch "innerhalb" einer Multiplikation angewendet werden, z. B. durch wahlweises Veranlassen von einem oder mehreren Übertrags-Bits vorbestimmte Werte anzunehmen.
Das Schema der Bit-Veränderung durch äußeres Einwirken muß nicht statisch sein, wobei bestimmte Bits immer zum Aufgreifen bestimmter Werte veranlaßt werden, sondern kann auch als ein dynamisches Schema verwendet werden. Z. B. können vorbestimmte Bits eines Datenworts dazu veranlaßt werden, auf "1" oder "0" zu gehen, in Abhängigkeit davon, ob das Wort (oder auch einige andere Daten) gerade oder ungerade, positiv oder negativ, über oder unter eines vorbestimmten Grenze etc. ist.
Normalerweise sind nur geringe schematische Veränderungen erforderlich, um die gesamte statistische Leistungsfähigkeit zu verbessern. Folglich werden die LSB's der gewählten Datenwörter (vorzugsweise ein Bit und ein Datenwort zu einem Zeitpunkt, obwohl dies nicht notwendig ist) gemäß dieser Ausführungsform dazu veranlaßt, eine "1" oder eine "0" zu sein. Der CCITT-Test läuft ab, und die CCITT-Statistiken für den Ablauf werden zusammengestellt. Das Bit wird dann veranlaßt, auf den anderen Wert als "1" oder "0" zu gehen, und der Test wird erneut gestartet. Dann wird das LSB (oder die LSB's) der anderen Datenwörter auf "1" und "0" veranlaßt und ähnliche Statistiken werden zusammengestellt. Durch Überprüfen der Statistiken für verschiedene Kombinationen von fremdbestimmten Bits in verschiedenen fremdbestimmten Wörtern kann die beste statistische Leistungsfähigkeit bestimmt werden.
Wenn diese auf Statistik basierende Verbesserung jedoch nicht erforderlich ist, können die Ausgaben von den Konstant-Koeffizient-Multiplizierern D1MUL, D3MUL, D5MUL und D7MUL in der herkömmlichen Weise in den Lösungsaddierern H0A bis H3A gelöst werden. Die unteren 21 Bits der Ausgaben von den Lösungsaddieren H0A bis H3A werden als die oberen 21 Bits an den Eingang der entsprechenden Signalspeicher H0L bis H3L aufgebracht, wobei das LSB dieser Eingaben mit dem Grund verbunden ist.
Die Ausgaben der H-Signalspeicher (H0L bis H3L) und der G-Signalspeicher (G0L bis G3L) bilden paarweise die jeweiligen a- und b-Eingaben zu den Lösungsaddierern/Subtrahierern S70A, S61A, S43A und S52A. Wie oben erläutert wurde, addieren diese Vorrichtungen ihre Eingaben, wenn das ADD-Signal hoch ist, und subtrahieren die "b-" Eingabe von der "a-" Eingabe, wenn das Subtraktionsfreigabesignal SUB hoch ist. Die zweiten Bits der oberen beiden Signalspeicherpaare H0L, G0L und H1L, G1L sind durch Multiplex-Anordnungen in einer nachfolgend beschriebenen Weise manipuliert.
Die Ausgaben von den Lösungsaddierern/-subtrahierern S70A, S61A, S43A und S52A werden in Ergebnissignalspeichern R70L, R61L, R43L und R52L gespeichert.
In Fig. 6b sind die Eingabewörter zu den Addieren/Subtrahierern S70A und S61A mit den zweiten Bits von jedem manipulierten Eingabewort versehen. Z. B. ist das zweite Bit des Eingabeworts zum "a"-Eingang des Addierers/Subtrahierers S70A gleich G0[21 : 2], G0[1M], G0[0]. Mit anderen Worten ist das zweite Bit dieses Signals auf den Wert G01M gesetzt. Die zweiten Bits der anderen Eingaben zu den Addierern/Subtrahierem S70A und S61A sind gleichermaßen manipuliert. Diese Bit-Manipulation wird durch vier 2 : 1-Bit Multiplexer H01MUX, G01MUX, H11MUX und G11MUX durchgeführt (gezeigt auf der rechten Seite in Fig. 6b). Diese Multiplexer werden durch die Signale ADD und SUB derart gesteuert, daß das zweite Bit. (H01M, G01M, H11M und G11M) auf Eins gesetzt ist, wenn der jeweilige Addierer/Subtrahierer S70A, S61A auf Addieren gesetzt ist (ADD ist hoch), und das zweite Bit ist auf seinen tatsächlichen Speicherausgabewert gesetzt, wenn das SUB-Signal auf Hoch gesetzt ist. Das Setzen der individuellen Bits in dieser Weise ist ein einfach realisierter, Hochgeschwindigskeitsvorgang. Die bevorzugte Ausführungsform enthält diese Anordnung zum Anpassen der Bits, da eine statistische Analyse einer größeren Zahl von Textpixelwörtern gemäß dem oben beschriebenen angezeigt hat, daß dadurch noch genauere Ergebnisse erzielt werden. Es ist jedoch nicht erforderlich, die zweiten Bits in dieser Weise zu manipulieren, obwohl daraus Vorteile einer geringeren Wortbreite entstehen.
Die vier hoch- und niederwertigen Ergebnisse werden in den Ausgabesignalspeichern R70L, R61L, R43L und R52L gespeichert. Die Ergebnisse werden aufeinanderfolgend in den finalen Ausgabesignalspeicher OUTF unter der Steuerung der Multiplex- Signale MUX_OUT70, MUX_OUT61, MUX_OUT43 und MUX_OUT52 gespeichert. Die Ordnung, in der die sich ergebenden Signale ausgegeben werden, kann daher einfach durch Verändern der Abfolge gesteuert werden, mittels der sie im Signalspeicher OUTF gespeichert sind. Die Ausgabe des Signalspeichers OUTF ist das finale 22- Bit-Resultatausgabesignal T_OUT[21 : 0].
Der Zusammenhang zwischen den Takt- und Steuersignalen im gemeinsamen Nachblock POSTC ist in den Fig. 7b und 7c gezeigt.
Wie oben diskutiert wurde, können zwei eindimensionale IDCT-Operationen in Serie durchgeführt werden, mit einem dazwischen liegenden Datentransfer, um eine 2- D-IDCT durchzuführen. Die Ausgabesignale des gemeinsamen Nachblocks POSTC werden daher entsprechend dieser Ausführungsform zuerst in bekannter Art spaltenweise (oder reihenweise) in einer herkömmlichen Speichereinheit wie z. B. einer RAM- Speicherschaltung (nicht gezeigt) gespeichert, und dann von der Speichereinheit reihenweise (spaltenweise) gelesen, um als Eingaben zu einem nachfolgenden gemeinsamen Vorblock weitergeleitet zu werden, und wie oben beschrieben in diesen Block, und in einem gemeinsamen Block CBLK und einem gemeinsamen Nachblock POSTC verarbeitet.
Das Speichern der Reihen (Spalten) und das Auslesen der Spalten (Reihen) führt die erforderliche Operation zum Übertragen der Daten vor der zweiten 1-D-IDCT aus. Die Ausgabe des zweiten POSTC werden die gewünschten 2-D-IDCT-Ergebnisse sein und kann in einer herkömmlichen Weise durch Verschieben skaliert werden, um die skalierten Verschiebungen, welche in den verschiedenen Verarbeitungsblöcken ausgeführt wurden, zu versetzen. Insbesondere führt eine Rechtsverschiebung um eine Posi tion eine Division um 2 aus, welche erforderlich ist, um die beiden 2-Multiplikationen zu versetzen, die in den 1-D-IDCT-Operationen ausgeführt wurden.
Abhängig von der Anwendung ist die zweite IDCT-Struktur (welche vorzugsweise identisch mit der in Fig. 3 gezeigten ist) vorzugsweise eine separate Halbleiterrealisierung. Dies vermeidet den Geschwindigkeitsabfall, der auftreten würde, wenn die gleichen Schaltkreise für beide Transformationen verwendet würden, obwohl separate 1-D-Transformationsrealisierungen nicht notwendig sind, wenn die. Pixel-Taktrate gering genug ist, daß eine einzelne Realisierung des Schaltkreises in der Lage ist, zwei Durchläufe in Echtzeit zu bewerkstelligen.
In den an einen Prototyp der oben beschriebenen Anordnung der IDCT-Anordnung durchgeführten Bereichstests wurde herausgefunden, daß alle Zwischen- und Abschlußwerte an jeder Stelle gut innerhalb eines bekannten Bereichs gehalten wurden, wobei sie immer noch die CCITT-Standards erfüllen. Daher war es wie oben beschrieben möglich, ausgewählte Werte um geringe Größenordnungen (z. B. durch Veranlassen bestimmter Bits von ausgewählten Datenwörtern bestimmte Werte anzunehmen) "einzustellen", ohne eine Bereichsüberschreitung oder -unterschreitung bei den arithmetischen Berechnungen fürchten zu müssen.
Das Verfahren und das System gemäß der Erfindung kann in vielfacher Weise variiert werden. Z. B. können die zum Lösen von Additionen oder Multiplikationen verwendeten Strukturen unter Verwendung bekannter Technologien verändert werden. So ist es möglich, Lösungsaddierer oder -subtrahierer zu verwenden, wo die bevorzugte Ausführungsform übertrags-sichernde Vorrichtungen mit separaten Lösungsaddierern nutzt. Ferner verwendet die bevorzugte Ausführungsform der Erfindung eine Herabskalierung an verschiedenen Punkten, um sicherzustellen, daß alle Werte in ihren akzeptablen Bereichen bleiben. Das Herabskalieren ist jedoch nicht notwendig, da andere Vorsichtsmaßnahmen ergriffen werden können, um eine Bereichsüberschreitung oder -unterschreitung zu vermeiden.
Bei einem Prototyp der Erfindung wurden bestimmte Bits von verschiedenen Datenwörtern auf der Basis einer statistischen Analyse von Testergebnissen des Systems manipuliert. Obwohl diese Manipulationen die erforderliche Wortbreite im System reduziert haben, können die verschiedenen Zwischenwerte natürlich ohne eine Bit-Manipulation hindurch geführt werden. Obwohl im dargestellten Beispiel der Erfindung nur Datenwörter mit Bit-Manipulation vorlagen, ist es ferner auch möglich, die Bits von Konstant-Koeffizienten als solche zu manipulieren und die Ergebnisse unter dem CCITT-Standard zu bewerten. Wenn ein Vergleich der Ergebnisse gezeigt hat, daß es in einigen Fällen vorteilhaft sein würde, ein bestimmtes Bit auf einen gegeben Wert zu stellen, ist man dann in der Lage, die Anzahl "Nullen" in der binären Darstellung dieser Koeffizienten zu erhöhen, um den zur Realisierung des entsprechenden Multiplizierers erforderlichen Siliziumbereich weiter zu verringern. Zur Wiederholung, eine Bit-Manipulation ist nicht notwendig.

Claims

1. Verfahren zur Durchführung einer inversen, diskreten Kosinustransformation von digitalen Signalen, welche einen Block von N Dateneingabewörtern darstellen, wobei N eine ganzzahlige Potenz von zwei ist, und wobei abwechselnde Wörter des Blocks jeweils als ungeradzahlige Wörter und geradzahlige Wörter definiert sind;

gekennzeichnet durch:

Durchführen einer paarweisen Addition von vorbestimmten ungeradzahligen der Eingabewörter in einer gemeinsamen Vorverarbeitungseinrichtung (PREC) und Übertragen von geradzahligen der Eingabewörter zu gemeinsamen Vorausgaben der gemeinsamen Vorverarbeitungseinrichtung (PREC), und Multiplizieren von einem der ungeradzahligen Wörter mit der Quadratwurzel von zwei, um einen geordneten Block von ungeradzahligen und geradzahligen, gemeinsamen Vorausgabedatenwörtern zu erzeugen;

Empfangen und Verarbeiten der ungeradzahligen, gemeinsamen Vorausgabedatenwörter in einer gemeinsamen Verarbeitungseinrichtung (CB-LK) in einem ersten Durchlauf, und ein getrenntes Empfangen und Verarbeiten der geradzahligen, gemeinsamen Vorausgabedatenwörter in der gemeinsamen Verarbeitungseinrichtung (CBLK) in einem zweiten Durchlauf, wobei die empfangenen Wörter Eingabedatenwörter definieren; und

Verarbeiten der Eingabedatenwörter in der gemeinsamen Verarbeitungseinrichtung (CBLK) mittels der Schritte:

Multiplizieren von ausgewählten, gepaarten Eingabedatenwörtern mit ersten und zweiten konstanten Koeffizienten;

Durchführen einer paarweisen Addition und einer paarweisen Subtraktion der Eingabedatenwörter, um gemeinsame Zwischendatenwörter zu bilden;

Multiplizieren von ausgewählten, gemeinsamen Zwischendatenwörtern mit einer Konstanten; und

Durchführen einer paarweisen Addition und einer paarweisen Subtraktion der gemeinsamen Zwischendatenwörter, um jeweils zuerst einen Block von geordneten ungeradzahligen und nachfolgend einen Block von geradzahligen Ausgabewerten von der gemeinsamen Verarbeitungseinrichtung (CBLK) zu erzeugen; und

Multiplizieren der ungeradzahligen Werte der gemeinsamen Verarbeitungseinrichtung mit dritten konstanten Koeffizienten (d1, d3, d5, d7) in einer gemeinsamen Nachverarbeitungseinrichtung (POSTC), um nachverarbeitete ungeradzahlige Ausgabewerte zu bilden, und Addieren von vorbestimmten nachverarbeiteten ungeradzahligen Ausgabewerten in der gemeinsamen Nachverarbeitungseinrichtung (POSTC) zu vorbestimmten geradzahligen Ausgabewerten der gemeinsamen Verarbeitungseinrichtung (CBLK), um hoch- und niederwertige Ausgabewörter zu erzeugen;

wobei die Ausgabewörter inverse, diskrete Kosinustransformationswerte entsprechend der Eingabedatenwörter enthalten.

2. Verfahren nach Anspruch 1, wobei die gemeinsame Vorverarbeitungseinrichtung (PREC) gemeinsame N/2 Voreingaben und gemeinsame N/2 Vorausgaben aufweist, wobei die gemeinsame Verarbeitungseinrichtung (CBLK) gemeinsame N/2 Eingaben, welche mit den gemeinsamen N/2 Vorausgaben verbunden sind, sowie gemeinsame N/2 Ausgaben aufweist, und wobei die gemeinsame Nachverarbeitungseinrichtung (POSTC) gemeinsame N/2 Nacheingaben, welche mit den gemeinsamen N/2 Ausgaben verbunden sind, und gemeinsame N/2 Nachausgaben aufweist, welche die Systemausgaben bilden.

3. Verfahren nach Anspruch 1 oder Anspruch 2, welches ferner für jedes von n gewählten Datenwörtern der Reihe nach (wobei n ein ganzzahliger Wert größer als 1 ist) einen Schritt zur Minimierung von Fehlern in den Ausgabewörtern enthält, mit

Erzeugen eines ersten Testdatensatzes, der indikativ für den Fehler im gewählten Datenwort ist, wobei ein vorbestimmtes Bit des Datenworts mit einem vorbestimmten binären Wert beaufschlagt ist,

Erzeugen eines zweiten Testdatensatzes, der indikativ für den Fehler im gewählten Datenwort ist, wobei das vorbestimmte Bit mit einem anderen binären Wert beaufschlagt ist, und

Vergleichen der 2n Testdatensätze, die somit durch die gewählten n Datenwörter erzeugt wurden, um den binären Wert zu bestimmen, den das vorbestimmte Bit aufweisen sollte, um den Fehler in den Ausgabewörtern zu minimieren.

4. Vorrichtung zur Durchführung einer inversen, diskreten Kosinustransformation von digitalen Signalen, welche einen Block von N Dateneingabewörtern darstellen, wobei N eine ganzzahlige Potenz von zwei ist, und wobei abwechselnde Wörter des Blocks jeweils als ungeradzahlige Wörter und geradzahlige Wörter definiert sind;

gekennzeichnet durch:

eine gemeinsame Vorverarbeitungseinrichtung (PREC) zur Durchführung einer paarweisen Addition von vorbestimmten ungeradzahligen der Eingabewörter und zum Übertragen der geradzahligen der Eingabewörter zu gemeinsamen Vorverarbeitungseinrichtungsausgaben, und zum Multiplizieren von einem der ungeradzahligen Wörter mit der Quadratwurzel von zwei, um einen geordneten Block von ungeradzahligen und geradzahligen, gemeinsamen Vorausgabedatenwörtern zu bilden,

eine gemeinsame Verarbeitungseinrichtung (CBLK), welche eine Eingabe von der gemeinsamen Vorverarbeitungseinrichtung empfängt, wobei sowohl die ungeradzahligen als auch die geradzahligen Datenwörter in getrennten Wegen hindurchgeführt werden, und welche enthält:

eine erste Mehrzahl von Multiplizierern (C1S, C3S) zum Multiplizieren von ausgewählten, gepaarten Eingabedatenwörtern mit ersten und zweiten konstanten Koeffizienten;

eine erste Mehrzahl von Addierern zum Durchführen einer paarweisen Addition und paarweisen Subtraktion von Eingabedatenwörtern, um gemeinsame Zwischendatenwörter zu bilden;

eine zweite Mehrzahl von Multiplizierern (MULC1S, MULNC1S, MULC3S3, MULC3S2) zum Multiplizieren von ausgewählten, gemeinsamen Zwischendatenwörtern mit einer Konstanten; und

einer zweiten Mehrzahl von Addierern zum Durchführen einer paarweisen Addition und paarweisen Subtraktion der gemeinsamen Zwischendatenwörter, um jeweils einen Block von geordneten ungeradzahligen und einen Block von geradzahligen gemeinsamen Ausgabewerten der Verarbeitungseinrichtung zu bilden; und

eine gemeinsame Nachverarbeitungseinrichtung (POSTC), mit:

einer dritten Mehrzahl von Multiplizierern zum Multiplizieren mittels dritter konstanter Koeffizienten (d1, d3, d5, d7) der ungeradzahligen Ausgabewerte der gemeinsamen Verarbeitungseinrichtung, um nachverarbeitete, ungeradzahlige Werte zu bilden,

einer dritten Mehrzahl von Addierern zum Addieren vorbestimmter, nachverarbeiteter ungeradzahliger Ausgabewerte zu vorbestimmten geradzahligen Ausgabewerten der gemeinsamen Verarbeitungseinrichtung, um hoch- und niederwertige Ausgabewörter zu erzeugen;

5. Vorrichtung nach Anspruch 4, wobei die gemeinsame Vorverarbeitungseinrichtung (PREC) gemeinsame N/2 Voreingaben und gemeinsame N/2 Vorausgaben aufweist, wobei die gemeinsame Verarbeitungseinrichtung (CBLK) gemeinsame N/2 Eingaben, welche mit den gemeinsamen N/2 Vorausgaben verbunden sind, sowie gemeinsame N/2 Ausgaben aufweist, und wobei die gemeinsame Nachverarbeitungseinrichtung (POSTC) gemeinsame N/2 Nacheingaben, welche mit den gemeinsamen N/2 Ausgaben verbunden sind, und gemeinsame N/2 Nachausgaben aufweist, welche die Systemausgaben bilden.

6. Vorrichtung nach Anspruch 4 oder Anspruch 5, ferner enthaltend:

eine erste Erzeugungseinrichtung zum Erzeugen eines ersten Testdatensatzes, der in Aufeinanderfolge indikativ für den Fehler in jedem der gewählten n Datenwörter ist, wobei n ein ganzzahliger Wert größer als 1 ist, wobei ein vorbestimmtes Bit von jedem ausgewählten Datenwort mit einem vorbestimmten binären Wert beaufschlagt ist;

eine zweite Erzeugungseinrichtung zum Erzeugen eines zweiten Testdatensatzes, der in Aufeinanderfolge indikativ für den Fehler in jedem der gewählten n Datenwörter ist, wobei das vorbestimmte Bit von jedem ausgewählten Wort mit einem anderen binaren Wert beaufschlagt ist: und

eine Vergleichseinrichtung zum Vergleichen der 2n-Testdatensätze, welche somit durch die gewählten n Datenwörter erzeugt wurden, um den binären Wert zu bestimmen, den das vorbestimmte Bit aufweisen sollte, um den Fehler in den Ausgabewörtern zu minimieren.