PatentDe  


Dokumentenidentifikation DE69326314T2 24.02.2000
EP-Veröffentlichungsnummer 0602888
Titel Durchführung aritmetische Operationen auf Daten
Anmelder Xerox Corp., Rochester, N.Y., US
Erfinder Davies, Daniel, Palo Alto, California 94306, US
Vertreter Grünecker, Kinkeldey, Stockmair & Schwanhäusser, Anwaltssozietät, 80538 München
DE-Aktenzeichen 69326314
Vertragsstaaten DE, FR, GB
Sprache des Dokument En
EP-Anmeldetag 08.12.1993
EP-Aktenzeichen 933098634
EP-Offenlegungsdatum 22.06.1994
EP date of grant 08.09.1999
Veröffentlichungstag im Patentblatt 24.02.2000
IPC-Hauptklasse G06F 7/48
IPC-Nebenklasse G06F 7/50   

Beschreibung[de]

Die vorliegende Erfindung betrifft Techniken zum Durchführen von arithmetischen Operationen auf Daten.

Wilson, US-A 5,129,092 ("Wilson '092"), beschreibt Techniken zum Verarbeiten von Datenmatrizen wie etwa Bildern und räumlich in Beziehung stehenden Daten unter Verwendung von Nachbarschaftverarbeitungseinheiten. Wie mit Bezug auf Fig. 1 und 2 gezeigt und beschrieben, bilden die Verarbeitungseinheiten eine Matrix mit mehreren Gruppen von acht Verarbeitungseinheiten. Die Verbindungen jeder Einheit zu den unmittelbar links und rechts davon benachbarten Verarbeitungseinheiten umfassen eine Übertrag-Ein-Leitung auf der linken Seite und eine Übertrag-Aus-Leitung auf der rechten Seite.

Wilson '092 beschreibt ab Spalte 12, Zeile 40 arithmetische Operationen. Bei einer bitseriellen Arithmetik wird ein Übertragsignal von einem Übertrag-Flip-Flop zu Multiplexern gegeben, von denen einer als eine Wahrheitstabelle für einen Übertrag-Fortpflanzungswert dient, der in Flip-Flops gespeichert ist, zu einem Ausgabeselektor gegeben wird und zurück in den Speicher gelesen werden kann. Bei der parallelen Arithmetik wird eine Übertrageingabe von einer unmittelbar links benachbarten Verarbeitungseinheit erhalten und pflanzt sich eine Übertragausgabe zu einer unmittelbar rechts benachbarten Verarbeitungseinheit fort. Wenn parallele arithmetische Operationen durchgeführt werden, muß bei Schreibalgorithmen darauf geachtet werden, einen Überlauf zu vermeiden, damit sich die Übertragsignale nicht versehentlich von einem Datenwort zum nächsten fortpflanzen, da sich viele Datenwörter in derselben Bitzeile befinden.

Mahoney, EP-A 460,970, beschreibt Techniken zum Operieren auf einem Datenkörper wie etwa auf Daten, die ein Bild definieren. Fig. 7 zeigt ein Verbindungsmaschinensystem, das eine Bildverarbeitung durch das Simulieren eines Binärbildjungles (BIJ = Binary Image Jungle) durchführt. Ein Vorschaltprozessor kann Aufrufe durchführen, um zu veranlassen, daß Verarbeitungseinheiten in der Verbindungsmaschine arithmetische und logische Operationen durchführen. Fig. 8 stellt einen Teil einer Matrix von Verarbeitungseinheiten in einer Verbindungsmaschine da, wobei eine Verarbeitungseinheit einen Pixelwert eines Bildes in der niedrigsten Ebene eines BIJs speichert und einen Pixelwert von einer anderen Verarbeitungseinheit in der nächsthöheren Ebene des BIJs empfängt. Wie auf Seite 20 in den Zeilen 15-28 mit Bezug auf Fig. 10 beschrieben ist, operiert jede Verarbeitungseinheit auf den Ergebnissen aus der nächstniedrigeren Ebene seiner ersten und zweiten Kinder. Fig. 13 und 14 zeigen jeweils eine Datensequenz von Datenelementmatrizen, in denen Summen von Pixelwerten erhalten werden. Wie mit Bezug auf Fig. 18 beschrieben, kann der lokale Speicher jeder Verarbeitungseinheit den Wert eines entsprechenden Pixels enthalten.

EP-A-0 464 601 gibt ein Arithmetikoperationssystem an, in welchem ein Übertragsteuerung- Angaberegister Übertragsteuerungsinformation für jede aus einer Vielzahl von kaskadierten Arithmetikeinheiten speichert. Jede Arithmetikeinheit umfaßt eine Übertragsteuereinrichtung, die ein Übertragsteuerbit vom Übertragsteuerung-Angaberegister empfängt und auf der Basis des Übertragsteuerbits einen Ausgabeübertrag von der Arithmetikeinheit modifiziert, bevor dieser an die benachbarte höherwertige Arithmetikeinheit ausgegeben wird. Das System kann an beliebigen Positionen in Felder partitioniert sein.

EP-A-0 486 143 gibt Techniken zum parallelen Verarbeiten von Daten an, bei denen vor der Verarbeitung Operanden in ein Wort mit wenigstens einem gelöschten Pufferbit zwischen jedem Operanden gepackt werden. Das Pufferbit wird vor allen arithmetischen oder logischen Operationen mit einer Vorzeichenarithmetik gelöscht und wird wiederum vor dem Bewerten der Ergebnisse gelöscht. Dadurch wird verhindert, daß sich ein mit einem Vorzeichen versehenes Bit fortpflanzt und in die Bits der Ergebnisses eines anderen Operanden fließt.

Es ist eine Aufgabe der vorliegenden Erfindung, ein Verfahren zum Betreiben eines Prozessors zum Durchführen von arithmetischen Operationen mit einer hohen Verarbeitungsgeschwindigkeit anzugeben.

Diese Aufgabe wird durch den Gegenstand von Anspruch 1 gelöst.

Bevorzugte Ausführungsformen der vorliegenden Erfindung sind Gegenstand der abhängigen Ansprüche.

Einige Operationen, die hier als "logische Operationen" beschrieben werden, erhalten unter Verwendung jedes Operandenbits jeweils ein Ergebnisbit. Deshalb erzeugt eine logische Operation gültige Ergebnisse, wenn sie parallel auf einem zusammengesetzten Operanden durchgeführt wird, der eine Vielzahl von zusammengesetzten Datenelementen umfaßt. Beispiele dafür sind NICHT, UND, ODER und EXKLUSIV-ODER.

Im Gegensatz dazu können gewöhnliche arithmetische Operationen ein Ergebnis erhalten, das mehr Bits umfaßt als die Werte, auf denen die Operationen durchgeführt werden. Das Addieren von zwei K-Bitwerten kann zum Beispiel wegen eines Übertragsignals ein (K + 1)- Ergebnis erzeugen. Das Subtrahieren eines K-Bitwertes von einem kleineren anderen kann in einem Leihsignal für das (K + 1)-te Bit resultieren. Das Multiplizieren von zwei K-Bitwerten kann ein 2K-Bit-Ergebnis erzeugen. Und eine Division kann manchmal eine unbegrenzte Anzahl von Bits erzeugen, wenn sie nicht auf einer bestimmten Präzisionsebene gekürzt wird.

Weil Ergebnisse mit einer größeren Breite erzeugt werden könnten, können herkömmliche Prozessoren keine gewöhnlichen arithmetischen Operationen parallel auf zusammengesetzten Operanden durchführen, die mehrere zusammengesetzte Datenelemente wie etwa Pixelwerte umfassen. Eine Operation auf einer Komponente kann ein Zwischenkomponentensignal wie etwa ein Übertragsignal, ein Leihsignal oder eine Verschiebung erzeugen, die sich fortpflanzt oder in die nächste Komponente überfließt, wodurch das von der nächsten Komponente erhaltene Ergebnis ungültig gemacht wird. Wenn die Komponenten Bits sind, dann können logische Operationen anstelle von arithmetischen Operationen verwendet werden, um dieses Problem zu lösen. Wenn die Komponenten jedoch mehr als ein Bit enthalten, dann können die logischen Operationen die arithmetischen Operationen nicht zufriedenstellend ersetzen.

Die vorliegende Erfindung erstrebt verbesserte Techniken, um arithmetische Operationen parallel zueinander auf zusammengesetzten Operanden durchzuführen, welche mehrere Multibit-Datenelemente als Komponenten umfassen. Zum Beispiel kann jede Komponente auf ein Pixel eines Bildes Bezug nehmen, wobei die Komponenten Graustufen- oder Farbpixelwerte sein können.

Während die arithmetischen Operationen gewöhnlich Signale zwischen Komponenten erzeugen, die hier als "Zwischenkomponentensignale" bezeichnet werden, wodurch ungültige Ergebnisse verursacht werden, erzeugen die Techniken der vorliegenden Erfindung gültige Ergebnisse. Einige Techniken verwenden einen Prozessor mit einem besonderen Schaltungsaufbau, der Zwischenkomponentensignale verhindern kann. Andere verwenden einen herkömmlichen Prozessor und erhalten trotz der Zwischenkomponentensignale gültige Ergebnisse bei arithmetischen Operationen.

Jede Technik, die einen herkömmlichen Prozessor verwenden kann, kann in einem Herstellungsartikel implementiert werden. Dieser Artikel umfaßt ein Datenspeichermedium und durch das Datenspeichermedium gespeicherte Befehlsdaten, wobei das Datenspeichermedium ein magnetisches Speichermedium, ein optisches Sepichermedium, ein Halbleiterspeicher oder ein anderes Speichermedium sein kann. Der Artikel kann in einem System verwendet werden, das einen Speicher, eine Speichermediumzugriffeinrichtung und einen Prozessor umfaßt. Der Speicher speichert Multibit-Datenelemente wie etwa Daten zu den Pixeln eines Bildes. Die Befehlsdaten geben Befehle an, die ein Prozessor ausführen kann, um eine arithmetische Operation parallel auf einem zusammengsetzten Operanden durchzuführen, der mehr als eines der Mehrbit-Datenelemente umfaßt. Die Befehle stellen sicher, daß die erhaltenen Ergebnisse trotz der Zwischenkomponentensignale gültig sind. Die Befehlsdaten können zum Beispiel ein Code sein, der durch einen Mikroprozessor wie etwa die CPU einer herkömmlichen Workstation oder eines anderen Computers ausgeführt wird.

Eine spezielle Schaltungstechnik verwendet einen Prozessor mit einer Gatterschaltung, die zum Steuern der Übertragung von Signalen zwischen Komponentendatenelementen verwendet werden kann. Diese Technik kann herkömmliche Mikroprozessoren verwenden, wenn die maximale Komponentenbreite ein ganzzahliges Vielfaches des Mikroprozessorbreite ist.

Eine andere spezielle Schaltungstechnik verwendet einen Prozessor mit einem Maskenregister, das mit der Verarbeitungsschaltung verbunden ist. Das Maskenregister kann mit einem Erlaubniswert wie etwa ON in den Bitpositionen geladen werden, welche Zwischenkomponentensignale von den nächstniedrigeren Bitpositionen empfangen dürfen. Das Maskenregister kann mit einem Verbotswert wie etwa OFF in den Bitpositionen geladen werden, welche keine Zwischenkomponentensignale von den nächstniedrigeren Bitpositionen empfangen dürfen. Das Maskenregister kann jedesmal geladen werden, wenn sich die Komponentenbreite ändert, wodurch viele Komponentenbreiten erlaubt werden. Bei Operationen auf anderen Daten als zusammengesetzten Operanden, kann das Maskenregister mit Werten geladen werden, welche erlauben, daß sich die Zwischenkomponentensignale frei fortpflanzen.

Eine Technik, die einen herkömmlichen Prozessor verwenden kann, verwendet einen oder mehrere Pufferbits zwischen jedem Paar von benachbarten Komponentendatenelementen. Zum Beispiel kann ein Pufferbit an jede Komponente über dem höchstwertigen Bit oder unter dem niedrigstwertigen Bit angehängt werden. Wenn die Präzision geopfert werden kann, kann auch das niedrigstwertige Bit jeder Komponente als ein Pufferbit verwendet werden.

Die Werte der Pufferbits können dann manipuliert werden, um Zwischenkomponentensignale zu verhindern oder zu kompensieren.

Eine Additionsoperation kann alle Pufferbits löschen, bevor zusammengesetzte Operanden addiert werden. Wenn die Operation zum Beispiel Komponentenpaare addiert, dann kann jeder zusammengesetzte Operand mit einer Maske mit einem OFF-Wert in jedem Pufferbit und einem ON-Wert an den anderen Stellen UND-verknüpft werden. Wenn die Operation eine Konstante zu jeder Komponente addiert, dann kann ein konstanter Operand durch das Replizieren der durch Pufferbits mit einem OFF-Wert separierten Konstante gebildet werden.

Eine Subtraktionsoperation kann ein Pufferbit über dem höchstwertigen Bit jeder Komponente verwenden. Um gültige Ergebnisse sicherzustellen, kann jedes Pufferbit in einem zusammengesetzten Minuenden einen ON-Wert aufweisen und jedes Pufferbit in einem zusammengesetzten Subtrahenden mit einem OFF-Wert beginnen. Tatsächlich stellen die Pufferbits sicher, daß jede Komponente des Minuenden einen Wert aufweist, der die ausgerichtete Komponente des Subtrahenden überschreitet. Daraus resultiert, daß sich kein Leihsignal zum Ergebnis der nächsten Komponente fortpflanzen kann.

Multiplikationen und Divisionen können mit Hilfe von Additionen und Subtraktionen zusammen mit Verschiebungs- und Logikoperationen unter Verwendung von Masken implementiert werden. Die Pufferbits können verwendet werden, um Masken zu erzeugen.

Die Pufferbittechnik kann auch unter Verwendung einer speziellen Schaltung implementiert werden, die Pufferbits zwischen Komponentendatenelementen einsetzt.

Eine andere Technik, die einen herkömmlichen Prozessor verwenden kann, kann zum Reduzieren oder Beseitigen von Pufferbits für bestimmte arithmetische Operationen verwendet werden. Diese Technik bereitet zusammengesetzte Operanden für eine Additionsoperation durch das Anpassen von Werten vor, die durch Komponentendatenelemente angegeben werden. Wenn zum Beispiel vorausgesagt werden kann, daß der Wert einer bestimmten Komponente ein Zwischenkomponenten-Übertragsignal verursacht, dann kann die Komponente neben dem höchstwertigen Bit angepaßt werden, indem vor der Operation eins subtrahiert wird, so daß das Zwischenkomponenten-Übertragsignal keinen Effekt hat.

Die Techniken der vorliegenden Erfindung sind vorteilhaft, weil sie einen Bereich von Alternativen vorsehen, von denen jede in bestimmten Situationen vorteilhaft ist. Jede Technik kann sicherstellen, daß keine Zwischenkomponentensignale die Ergebnisse einer parallel auf zusammengesetzten Operanden durchgeführten arithmetischen Operation mit Mehrbit- Komponentendatenelementen wie etwa Pixelwerten ungültig machen. Außerdem können einige der Techniken in bestimmten Situationen gemeinsam verwendet werden. Die vorliegende Erfindung ermöglicht also, daß arithmetische Operationen auf Mehrbit-Komponentendatenelementen schnell und effektiv in vielen Situationen durchgeführt werden können.

Die vorliegende Erfindung wird im folgenden beispielhaft mit Bezug auf die beigefügten Zeichnungen näher beschrieben. Es zeigen:

Fig. 1 ein schematisches Diagramm, das zeigt, wie ein gültiges Ergebnis einer arithmetischen Operation auf jeder Komponente eines zusammengesetzten Operanden erhalten werden kann, obwohl die Operation gewöhnlich ein Zwischenkomponentensignal erzeugen würde, welches ein ungültiges Ergebnis verursacht,

Fig. 2 ein schematisches Blockdiagramm, das Komponenten eines Systems zeigt, in welchem ein Prozessor Befehle von einem Softwareprodukt ausführen kann, um gültige Ergebnisse einer arithmetischen Operation trotz der Zwischenkomponentensignale zu erhalten,

Fig. 3 ein schematisches Blockdiagramm, das einen Prozessor mit einer Zwischenkomponenten-Verhinderungsschaltung zeigt, die Zwischenkomponentensignale verhindern kann,

Fig. 4 ein Flußdiagramm, das Schritte zeigt, mit welchen ein Prozessor trotz der Zwischenkomponentensignale gültige Ergebnisse erhalten kann,

Fig. 5 ein schematisches Schaltungsdiagramm, das eine Gatterschaltung für die Implementierung der Zwischenkomponenten-Verhinderungsschaltung von Fig. 3 zeigt,

Fig. 6 ein schematisches Schaltungsdiagramm, das eine Maskenregisterschaltung für die Implementierung der Zwischenkomponenten-Verhinderungsschaltung von Fig. 3 zeigt,

Fig. 7 ein schematisches Flußdiagramm, das eine Additionsoperation und eine Subtraktionsoperation zeigt, welche jeweils die Schritte von Fig. 4 implementieren, und

Fig. 8 ein Flußdiagramm, das einen Vorverarbeitungsansatz zeigt, welcher die Schritte von Fig. 4 implementiert.

Der im folgenden verwendete Begriff "zusammengesetzter Operand" bezeichnet einen Operanden, der zwei oder mehr Datenelemente umfaßt, welche als "Komponentendatenelemente" oder als "Komponenten" bezeichnet werden.

Ein Prozessor oder eine andere Schaltung, die eine arithmetische Operation auf einem zusammengesetzten Operanden durchführt, kann ein "Zwischenkomponentensignal" erzeu gen. Ein Zwischenkomponentensignal ist ein Signal wie etwa ein Übertragsignal, ein Leihsignal oder ein verschobenes Bit, das verursachen kann, daß eine Operation auf einer Komponente die für eine andere Komponente erhaltenen Ergebnisse beeinflußt.

Eine arithmetische Operation "erzeugt gewöhnlich ein Zwischenkomponentensignal aus einem Komponentendatenelement", wenn die in Übereinstimmung mit der gewöhnlichen Arithmetik durchgeführte Operation ein Zwischenkomponentensignal erzeugt, dessen Effekt sich über das Komponentendatenelement hinaus auswirkt. Zum Beispiel erzeugt das Addieren von eins zu einem Zweibit-Komponentendatenelement mit dem Wert 11 gewöhnlich ein Zwischenkomponenten-Übertragsignal, welches das nächste Bit auf der linken Seite beeinflußt.

A. Allgemeine Merkmale

Fig. 1 bis 4 stellen allgemeine Merkmale der vorliegenden Erfindung dar. Fig. 1 zeigt in schematischer Weise eine Technik, die ein gültiges Ergebnis einer arithmetischen Operation erhält, welche parallel auf Mehrbit-Komponentendatenelementen durchgeführt wird. Fig. 2 zeigt ein Softwareprodukt mit Befehlsdaten, welche Befehle angegeben, die durch einen Prozessor in Übereinstimmung mit einer wie in Fig. 1 gezeigten Technik ausgeführt werden können. Fig. 3 zeigt allgemeine Merkmale eines Prozessors mit einer Zwischenkomponenten-Verhinderungsschaltung, welche die Übertragung von Zwischenkomponentensignalen zwischen Verarbeitungspositionen verhindert. Fig. 4 zeigt allgemeine Schritte in einem Verfahren zum Betreiben eines Prozessors zum Erhalten von gültigen Ergebnissen trotz eines Zwischenkomponentensignals.

In Fig. 1 umfaßt ein zusammengesetzter Operand 10 Komponentendatenelemente 12 und 14, die jeweils zwei Bits umfassen. Die Komponente 12 weist den Wert 01 auf, während die Komponente 14 den Wert 10 aufweist. Entsprechend umfaßt der zusammengesetzte Operand 20 die Komponenten 22 und 24 mit jeweils den Werten 01 und 10.

Die Komponenten 12 und 22 können dieselben Bitpositionen einnehmen, und die Komponenten 14 und 24 können dieselben Bitpositionen einnehmen. Die höchstwertigen Bits der Komponenten 12 und 22 können jeweils zu den niedrigstwertigen Bits der Komponenten 12 und 22 benachbart sein. Wenn also ein Prozessor eine arithmetische Operation zum Addieren eines Operanden 10 zu einem Operanden 20 durchführt, dann werden jeweils die Komponenten 12 und 22 sowie die Komponenten 14 und 24 addiert.

Eine gewöhnliche arithmetische Additionsoperation, die auf den zusammengesetzten Operanden 10 und 20 mit Hilfe eines herkömmlichen Prozessors durchgeführt wird, kann ein Ergebnis 30 erzeugen. Wie gezeigt umfaßt das Ergebnis 30 die Datenelemente 32 und 34 mit jeweils den Werten 11 und 00. Die "1"-Werte im Datenelement 32 resultieren beide aus Übertragsignalen, nämlich aus dem Übertragsignal 36 vom höchstwertigen Bit der Komponenten 14 und 24 und aus dem Übertragsignal 38 vom niedrigstwertigen Bit der Komponenten 12 und 22. Es kann jedoch gesehen werden, daß das Übertragsignal 36 ein ungültiges Ergebnis im Datenelement 32 erzeugt, weil die Summe 01 und 01 gleich 10 und nicht gleich 11 ist.

Um das ungültige Ergebnis 30 zu vermeiden, kann der Prozessor statt dessen ein gültiges Ergebnis 40 erzeugen, in welchem die Datenelemente 42 und 44 jeweils die Werte 10 und 00 aufweisen. Verschiedene besondere Techniken zum Erzeugen eines gültigen Ergebnisses in Fällen, in welchen ein Zwischenkomponentensignal gewöhnlich ein ungültiges Ergebnis erzeugen würde, werden im folgenden erläutert.

Fig. 2 zeigt ein Softwareprodukt 60, d. h. einen Herstellungsartikel, der in einem System mit wie in Fig. 2 gezeigten Komponenten verwendet werden kann. Das Softwareprodukt 60 umfaßt ein Datenspeichermedium 62, auf das durch eine Speichermedium-Zugriffseinrichtung 64 zugegriffen werden kann. Das Datenspeichermedium 62 könnte zum Beispiel ein magnetisches Medium wie etwa ein Satz aus einer oder mehreren Disketten, ein optisches Medium wie etwa ein Satz aus einer oder mehreren CD-ROMs, ein Halbleiterspeicher oder ein anderes entsprechendes Medium zum Speichern von Daten sein.

Das Datenspeichermedium 62 speichert Daten, welche durch die Speichermedium-Zugriffseinrichtung 64 an den Prozessor 66 gegeben werden können, der zum Beispiel ein Mikroprozessor sein kann. Der Prozessor 66 ist zum Empfangen von Daten von einer Eingabeschaltung 70 verbunden. Die Daten können von einer geeigneten Quelle wie etwa von einem Faxgerät, von einem Scanner, der entweder der Scanner eines digitalen Kopiergerätes oder ein Eingabe-/Augabegerät eines Computers sein kann, von einem Editor, der ein Formulareditor oder ein interaktiver Bildeditor sein kann, welcher mit Hilfe von Benutzereingabeeinrichtungen wie einer Tastatur und einer Maus oder einer mit einem Stift arbeitenden Eingabeeinrichtung gesteuert wird, oder von einem Netzwerk erhalten werden, das ein lokales Netzwerk oder ein anderes Netzwerk sein kann, welches Daten übertragen kann. Die Daten können auf ein Bild Bezug nehmen.

Der Prozessor 66 ist weiterhin zum Ausgeben von Daten zu einer Ausgabeschaltung 80 verbunden. Die Daten können wiederum zum einem Faxgerät, einem Drucker, einer Anzeige oder einem Netzwerk ausgegeben werden. Der Drucker kann der Drucker eines digitalen Kopiergerätes oder ein Eingabe-/Ausgabegerät eines Computers sein.

Zusätzlich zu dem Datenspeichermedium 62 umfaßt das Softwareprodukt 60 durch das Datenspeichermedium 62 gespeicherte Daten. Die gespeicherten Daten umfassen Befehlsdaten, welche arithmetische Operationsbefehle 90 angeben. Der Prozessor 66 kann die Befehle 90 ausführen, um eine arithmetische Operation auf einem zusammengesetzten Operanden durchzuführen, der eine Vielzahl von Komponentendatenelementen umfaßt.

Der Prozessor 66 kann die Komponentendatenelemente, auf denen die arithmetische Operation durchgeführt wird, durch das Zugreifen auf den Speicher 92 erhalten. Jedes Datenelement kann zum Beispiel auf ein Pixel eines Bildes Bezug nehmen. Dies Datenelemente können zum Beispiel mehr als ein Bit umfassen. Die durch das Datenspeichermedium 62 gespeicherten Daten können auch Daten umfassen, welche Befehle angegeben, die der Prozessor 66 ausführen kann, um von der Eingabeschaltung 70 empfangene Datenelemente im Speicher 92 zu speichern, um Datenelemente für eine arithmetische Operation oder zum Ausgeben zur Ausgabeschaltung 80 aus dem Speicher 92 abzurufen oder um Datenelemente zu speichern, die aus einer arithmetischen Operation im Speicher 92 resultieren.

Der Prozessor 66 umfaßt eine Verarbeitungsschaltung 94 mit mehreren Verarbeitungspositionen 96. Der Prozessor 66 kann zum Beispiel ein herkömmlicher Mikroprozessor sein. Jede der Verarbeitungspositionen 96 kann eine Operation auf einem Bit durchführen. Die Verarbeitungsschaltung 94 umfaßt eine Positionenverbindungsschaltung 98 zum paarweisen Verbinden von Verarbeitungspositionen 96, um eine Matrix zu bilden. Ein Signal von einer Verarbeitungsposition in einem Paar kann durch die Positionenverbindungsschaltung 98 zu der anderen Verarbeitungseinheit übertragen werden.

Jedes Komponentendatenelement in einem zusammengesetzten Operanden, auf welchem eine arithmetische Operation durchgeführt wird, kann in einer entsprechenden Teilmatrix aus Verarbeitungspositionen 96 enthalten sein. Der Prozessor 66 kann arithmetische Operationsbefehle 90 ausführen, um ein resultierendes Datenelement in der Teilmatrix jeder Komponente zu erhalten. Während der Ausführung der arithmetischen Operationsbefehle 90 gibt die Teilmatrix einer ersten Komponente ein Zwischenkomponentensignal an die Positionen verbindungsschaltung 98 aus. Das Zwischenkomponentensignal kann veranlassen, daß die arithmetische Operation ein resultierendes Datenelement erhält, welches ein ungültiges Ergebnis in der Teilmatrix einer zweiten Komponente angibt. Der Prozessor 66 stellt beim Ausführen der arithmetischen Operationsbefehle 90 sicher, daß das resultierende Datenelement in der Teilmatrix der zweiten Komponente trotz des Zwischenkomponentensignals ein gültiges Ergebnis der arithmetischen Operation auf der zweiten Komponente angibt.

Fig. 3 zeigt allgemeine Komponenten eines Prozessors 100. Die Verarbeitungsschaltung 102 kann arithmetische Operationen parallel auf zusammengesetzten Operanden durchführen. Wie die Verarbeitungsschaltung 94 in Fig. 2 weist die Verarbeitungsschaltung 102 mehrere Verarbeitungspositionen 104 auf. Jeder der Verarbeitungspositionen 104 kann eine Operation auf einem Bit durchführen. Die Verarbeitungsschaltung 102 umfaßt eine Positionenverbindungsschaltung 105, welche Verarbeitungspositionen 104 paarweise verbindet, um eine Matrix zu bilden. Ein Signal von einer Verarbeitungsposition in einem Paar kann durch die Positionenverbindungsschaltung 106 zu der anderen Verarbeitungseinheit übertragen werden.

Der Prozessor 100 ist jedoch kein herkömmlicher Mikroprozessor. Die Zwischenkomponenten-Verhinderungsschaltung 100 ist derart verbunden, daß sie die Übertragung von Signalen zwischen Verarbeitungspositionen 104 durch die Positonsverbindungsschaltung 106 verhindern kann.

Eine Steuerschaltung 112 ist verbunden, um Steuersignale an die Verarbeitungsschaltung 102 und die Zwischenkomponenten-Verhinderungsschaltung 110 auszugeben.

Die Steuersignale veranlassen, daß die Verarbeitungsschaltung 102 eine arithmetische Operation parallel auf einem zusammengesetzten Operanden durchführt, der mehrere Mehrbit-Komponentendatenelemente umfaßt. Zum Beispiel kann jedes Komponentendatenelement auf ein Pixel eines Bildes Bezug nehmen. Jede Komponente ist in einer entsprechenden Teilmatrix aus Verarbeitungspositionen 104 enthalten. Die Verarbeitungsschaltung 102 führt die arithmetische Operation auf jeder Komponente durch, um ein resultierendes Datenelement in der Teilmatrix jeder Komponente zu erhalten. Während der Durchführung der arithmetischen Operation gibt die Teilmatrix einer ersten Komponente ein Zwischenkomponentensignal an die Positionenverbindungsschaltung 106 aus Das Zwischenkomponentensignal kann veranlassen, daß die arithmetische Operation ein resultierendes Datenelement erhält, das ein ungültiges Ergebnis in der Teilmatrix einer zweiten Komponente angibt.

Die Steuersignale veranlassen weiterhin, daß die Zwischenkomponenten-Verhinderungsschaltung 110 die Übertragung des Zwischenkomponentensignals durch die Positionenverbindungsschaltung 106 verhindert. Als ein Ergebnis gibt das resultierende Datenelement in der Teilmatrix der zweiten Komponente ein gültiges Ergebnis der arithmetischen Operation auf der zweiten Komponente an.

Fig. 4 zeigt allgemeine Schritte in einem Verfahren zum Betreiben eines Prozessors mit einer Verarbeitungsschaltung wie der in Fig. 2 gezeigten Verarbeitungsschaltung 94. Der Schritt in Block 130 gibt einen zusammengesetzten Operanden an die Verarbeitungsschaltung 94 aus, wobei jede Komponente zu einer entsprechenden Teilmatrix aus Verarbeitungspositionen 96 ausgegeben wird. Der Schritt in Block 132 betreibt die Verarbeitungsschaltung 94, um eine arithmetische Operation parallel auf dem zusammengesetzten Operanden durchzuführen, um ein resultierendes Datenelement in jeder Teilmatrix zu erhalten. Während der Durchführung der arithmetischen Operation, gibt die Teilmatrix einer ersten Komponente ein Zwischenkomponentensignal aus. Der Schritt in Block 132 wird durchgeführt, um sicherzustellen, daß jedes resultierende Datenelement trotz des Zwischenkomponentensignals ein gültiges Ergebnis angibt.

B. Implementierungen

Die oben mit Bezug auf Fig. 1 bis 4 beschriebenen allgemeinen Merkmale können auf verschiedene Weise implementiert werden, wobei viele verschiedene Komponenten und Operationen verwendet werden können. Zum Beispiel können einige der oben beschriebenen allgemeinen Merkmale mit herkömmlichen Prozessoren implementiert werden, während andere mit speziellen Prozessoren implementiert werden können.

Fig. 5 und 6 stellen zwei Implementierungen der in Fig. 3 gezeigten allgemeinen Komponenten dar. Fig. 7 und 8 stellen zwei Implementierungen der in Fig. 4 gezeigten allgemeinen Schritte dar, die für Verarbeitungseinheiten verwendet werden können, die parallel auf mehr als einem Datenelement operieren können; eine Anzahl von derartigen Verarbeitungseinheiten kann parallel ohne eine Positionenverbindungsschaltung dazwischen verwendet werden.

1. Gatterschaltung

Fig. 5 stellt eine Implementierung der mit Bezug auf Fig. 3 beschriebenen allgemeinen Komponenten dar, welche herkömmliche Mikroprozessoren in einer Verarbeitungsschaltung 102 verwenden können. Die Implementierung von Fig. 5 umfaßt eine Zwischenkomponenten- Verhinderungsschaltung 110, welche ein Zwischenkomponentensignal zwischen den Mikroprozessoren verhindern kann. Wenn also jeder Mikroprozessor M Bits breit ist, wobei M ≥ 1, dann kann die Matrix aus Verarbeitungspositionen in Teilmatrizen mit einem beliebigen ganzzahligen Vielfachen von M Bits unterteilt werden. Jede Teilmatrix kann dann arithmetische Operationen auf Komponentendatenelementen durchführen.

Fig. 5 zeigt den Mikroprozessor 150, den p-ten Mikroprozessor in einer Matrix aus Mikroprozessoren, die Verarbeitungspositionen 104 vorsieht. Innerhalb der Matrix verbindet die Positionenverbindungsschaltung 106 die Übertrageingänge und Übertragausgänge von benachbarten Mikroprozessoren. Wie gezeigt, empfängt der Übertrageingang des Mikroprozessors 150 ein Signal vom Übertragausgang des (p - 1)-ten Mikroprozessors nur dann, wenn ein Übertragauswahlsignal an das UND-Gatter 152 ausgegeben wird. Entsprechend wird ein Signal vom Übertragausgang des Mikroprozessors 150 an den (p + 1)-ten Mikroprozessor nur dann ausgegeben, wenn ein Übertragauswahlsignal an das UND-Gatter 154 ausgegeben wird.

Der Breitenauswahl-Decoder 156 kann ein Nur-Lese-Speicher (ROM), eine programmierbare Matrixlogik (PAL) oder eine andere herkömmliche Schaltung sein, die auf ein Signal von der Steuerschaltung 112 antwortet, indem sie Übertragfreigabesignale an die entsprechenden UND-Gatter ausgibt, so daß die Übertragsignale innerhalb einer Teilmatrix aber nicht zwischen Teilmatrizen von verschiedenen Komponentendatenelementen übertragen werden können. Das Signal von der Steuerschaltung 112 kann eine Teilmatrizenbreite wie etwa M, 2M, 3M usw. angeben, und die Ausgabe aus dem Breitenauswahl-Decoder 156 kann entsprechend ON für UND-Gatter innerhalb einer Teilmatrix und OFF für UND-Gatter zwischen Teilmatrizen sein. Um eine Operation auf einem matrixbreiten Wert durchzuführen, was für Aufgaben nützlich ist, welche wie etwa ein Pixelzählen große Zahlen erzeugen, dann kann das Signal von der Steuerschaltung 112 eine Breite angeben, so daß die Ausgabe vom Breitenauswahl-Decoder 156 eine ON-Ausgabe an alle UND-Gatter ausgibt.

2. Maskenregister

Fig. 6 stellt eine andere Implementierung der mit Bezug auf Fig. 3 beschriebenen allgemeinen Komponenten dar, die eine spezielle arithmetische Logikeinheit (ALU) 170 verwenden können. Die Implementierung in Fig. 6 umfaßt eine Zwischenkomponenten-Verhinderungsschaltung, die ein Zwischenkomponentensignal zwischen zwei benachbarten Verarbeitungspositionen in der ALU 170 verhindern kann. Wenn also die ALU 170 M Bits breit ist, dann kann die Matrix der Verarbeitungspositionen in gleiche Teilmatrizen mit einem beliebigen ganzzahligen Faktor von M Bits unterteilt werden. Jede Teilmatrix kann dann arithmetische Operationen auf Komponentendatenelementen durchführen.

Die Verarbeitungsposition 172 ist die p-te Position in den Verarbeitungspositionen 104 in der ALU 170. In der Matrix verbindet eine Positionenverbindungsschaltung wie in Fig. 3 die Übertrageingänge und Übertragausgänge von benachbarten Verarbeitungspositionen. Wie gezeigt empfängt jedoch der Übertrageingang der Position 172 ein Signal vom Übertragausgang der (p - 1)-ten Position über die Positonsverbindungslogik 174. Entsprechend gibt der Übertragausgang der Position 172 ein Signal an den Übertrageingang der (p + 1)-ten Position über die Positionenverbindungslogik 176 aus.

Die Positionenverbindungslogik 174 gibt ein Übertragsignal von der (p - 1)-ten Position nur dann aus, wenn ein ON-Wert an den anderen Eingang des UND-Gatters 180 ausgegeben wird, so daß das Signal über das ODER-Gatter 182 an den Übertrageingang der Position 172 ausgegeben wird. Wenn das Maskenregister ein OFF-Signal an die UND-Gatter 180 und 184 ausgibt, dann empfängt der Übertrageingang der Position 172 nur dann ein ON-Signal, wenn das Subtraktionssignal an das UND-Gatter 184 ON ist. Die Positionenverbindungslogik 176 umfaßt eine entsprechende Schaltung.

Das Maskenregister 190 kann mit einer herkömmlichen Registerschaltung implementiert werden, die durch Signale von der Steuerschaltung 112 mit Maskenwerten geladen werden kann. Die Maskenwerte umfassen Freigabewerte, die in der vorliegenden Darstellung ON sind, sowie Verbotssignale, die in der vorliegenden Darstellung OFF sind. Das Maskenregister 190 ist verbunden, so daß jeder Maskenwert an UND-Gatter ausgegeben wird, welche wie die UND-Gatter 180 und 184 den Übertrageingang einer entsprechenden Position steuern. Der Maskenwert 192 steuert den Übertrageingang der (p - 1)-ten Position, der Maskenwert 194 steuert den Übertrageingang der p-ten Position und der Maskenwert 196 steuert den Übertrageingang der (p + 1)-ten Position. Allgemein erlaubt ein Freigabewert, daß sich ein Übertragsignal aus der nächstniedrigeren Position nach oben fortpflanzt, während ein Verbotswert verhindert, daß sich Übertragsignale nach oben fortpflanzen. Während einer Subtraktionsoperation sieht ein Verbotswert jedoch auch dann ein Übertragsignal vor, wenn die nächstniedrigere Position kein Übertragsignal ausgibt, wie es für die Standardimplementierung einer Arithmetik mit zwei Komplementen erforderlich ist.

Die Steuerschaltung 112 kann das Maskenregister 190 jedesmal laden, wenn sich die Anzahl der Bits in jedem Komponentendatenelement ändert. Wenn die Komponentendatenelemente zum Beispiel Pixelwerte sind, dann können die Maskenwerte jedesmal geändert werden, wenn die sich die Anzahl der Bits in jedem Pixelwert ändert.

In dem dargestellten Beispiel steuert der Maskenwert 192 die oberste Verarbeitungsposition der Teilmatrix einer Komponente, während der Maskenwert 194 die unterste Verarbeitungsposition der Teilmatrix einer benachbarten Komponente steuert, d. h. der Position 172.

Jeder der oben genannten Implementierungen verwendet einen speziellen Schaltungsaufbau. Im Gegensatz dazu erfordern die folgenden Implementierungen keinen speziellen Schaltungsaufbau, können aber die Verarbeitungspositionen aber aufgrund von zusätzlichen Bits wie Pufferbits weniger effektiv verwenden.

3. Pufferbits

Fig. 7 ist ein Flußdiagramm, das zwei Implementierungen der mit Bezug auf Fig. 4 beschriebenen allgemeinen Schritte darstellt, wobei extra Bits zwischen Komponentendatenelementen verwendet werden, die als Pufferbits bezeichnet werden. Die durch die Operanden 200 bis 250 dargestellte erste Implementierung führt eine Additionsoperation durch, während die durch die Operanden 250 bis 300 dargestellte zweite Implementierung eine Subtraktionsoperation durchführt.

Der zusammengesetzte Operand 200 umfaßt eine Vielzahl von Komponentendatenelementen. Wie gezeigt, sind die Komponenten 202 und 204 innerhalb des Operanden 200 einander benachbart.

Es kann eine Ausbreitungsoperation auf dem Operanden 200 durchgeführt werden, um einen zusammengesetzten Operanden 210 zu erhalten. Der Operand 210 umfaßt eine Komponente 212 mit demselben Wert wie die Komponente 202 und eine Komponente 214 mit demselben Wert wie die Komponente 204. Außerdem umfaßt der Operand 210 ein Pufferbit 216 zwischen den Komponenten 212 und 214.

Allgemein kann eine beliebige Ausbreitungsoperation verwendet werden, welche einen zusammengesetzten Operanden verwendet, um einen anderen zusammengesetzten Operanden zu erhalten, der ein oder mehrere Pufferbits zwischen benachbarten Komponentendatenelementen enthält. Zum Beispiel kann eine Ausbreitungsoperation unter Verwendung einer Ausbreitungsschaltung implementiert werden. Die Anzahl der Pufferbits kann groß genug sein, um sicherzustellen, daß das in der Teilmatrix jeder Komponente erzeugte resultierende Datenelement nicht eine benachbarte Teilmatrix beeinflußt, wobei dies jedoch ineffizient sein kann.

Für eine maximale Effizienz sollte die Anzahl der Pufferbits vorzugsweise minimal gehalten werden.

Wenn ein M-Bit-Mikroprozessor verwendet wird und zum Beispiel jedes Komponentendatenelement ((M/n)-1) Bit oder weniger umfaßt, wobei n eine ganze Zahl ist, dann können n Komponenten in einem zusammengesetzten Operanden von M-Bit enthalten sein, wenn ein Pufferbit an/neben dem niedrigstwertigen Bit oder an/neben dem höchstwertigen Bit jedes Komponentendatenlements eingesetzt werden kann. In diesen Fällen kann die gesamte Arithmetik MOD 2n-1 durchgeführt werden.

Wenn Pufferbits durch das Ausbreiten von Komponenten eingefügt werden, dann werden der Bereich und die Auflösung der Komponentenwerte erhalten, wobei jedoch zusätzliche Verarbeitungspositionen für Pufferbits verwendet werden. Wenn die Pufferbits die niedrigstwertigen Bits von Komponenten ersetzen, dann wird die Präzision oder Auflösung der Komponentenwerte geopfert. Wenn die Pufferbits die höchstwertigen Bits ersetzen, dann wird der Bereich der Komponentenwerte um die Hälfte reduziert.

Außerdem kann ein Pufferbit an oder neben dem höchstwertigen Bit bequem verwendet werden, um ein binäres Ergebnis einer arithmetischen Operation für ein Pixel anzugeben, wie in der gleichzeitig anhängigen und gleichzeitig eingereichten europäischen Patentanmeldung EP-A-0 602 887 beschrieben.

Wenn jedes Komponentendatenelement mehr als ((M/n)-1), aber nicht mehr als (Mln) Bits enthält und wenn etwas von der Präzision geopfert werden kann, dann können n Kompo nentendatenelemente in einem zusammengesetzten M-Bit-Operanden enthalten sein, wenn die niedrigstwertigen Bits von einigen oder allen der Komponenten als Pufferbits verwendet werden. In diesem Fall werden die arithmetischen Operationen nur auf geraden Zahlen durchgeführt.

Vor einer Additionsoperation, die ausgerichtete Komponenten in zwei zusammengesetzten Operanden addiert, sollte jedes Pufferbit in beiden Operanden auf null gelöscht werden, um eine Fortpflanzung von Übertragsignalen der Teilmatrix einer Komponente auf die einer anderen zu vermeiden. Deshalb wird der Operand 210 mit dem Operanden 220 UND-verknüpft, welcher ein Maskenoperand ist, der in jeder Bitposition in der Teilmatrix einer Komponente ON ist und der in jeder Pufferbitposition OFF ist, wie durch das Bit 222 gezeigt.

Die UND-Operation erzeugt einen zusammengesetzten Operanden 230, wobei die Komponente 232 denselben Wert aufweist wie die Komponente 212 und wobei die Komponente 234 denselben Wert aufweist wie die Komponente 214. Das Pufferbit 236 weist den Wert null auf.

Die Additionsoperation addiert den zusammengesetzten Operanden 230 zu dem zusammengesetzten Operanden 240, dessen relevanter Teil in der Darstellung als mit dem Operanden 230 identisch gezeigt ist, wobei die Komponenten 242 und 244 mit den Komponenten 232 und 234 identisch sind und wobei das Pufferbit 246 mit dem Pufferbit 236 identisch ist. Der Operand 240 kann durch das Kopieren des Operanden 230 oder durch Schritte erhalten werden, die den oben beschriebenen ähnlich sind. Wenn eine Konstante zu jeder Komponente in einem zusammengesetzten Operanden addiert wird, dann kann der konstante Operand erhalten werden, indem mit einem Nur-Nullen-Operanden begonnen wird, mit welchem die Konstante an der Position der Teilmatrix jeder Komponente ODER-verknüpft wird.

Die Addition der Operanden 230 und 240 erzeugt einen zusammengesetzten Operanden 250 mit einem resultierenden Datenelement in der Teilmatrix jeder Komponente. Das resultierende Datenelement 252 gibt ein gültiges Ergebnis der Addition der Komponenten 232 und 242 an, während das resultierende Datenelement 254 ein gültiges Ergebnis der Addition der Komponenten 234 und 244 angibt. Das Pufferbit 256 weist wegen des Übertragsignals 258, das von der Teilmatrix, in welcher die Komponenten 234 und 244 addiert werden, empfangen wird, den Wert Eins auf, wobei jedoch das Pufferbit 256 sichergestellt hat, daß die resultierenden Datenelemente 252 und 254 gültige Ergebnisse angeben. Wenn eine weitere Addition durchgeführt wird, kann das Pufferbit 256 wiederum vor der Addition gelöscht werden.

Die Operanden 200 bis 250 stellen Implementierungen der Schritte von Fig. 4 dar. Die Operanden 200, 210, 230 und 240 stellen jeweils dar, wie jedes Komponentendatenelement zu einer Teilmatrix zugeordnet wird. Die Operanden 230, 340 und 250 stellen dar, wie eine arithmetische Operation parallel durchgeführt wird, um trotz eines Zwischenkomponentensignals wie des Übertragsignals 258 gültige Ergebnisse zu erhalten.

Eine Zwei-Komplement-Subtraktionsoperation kann implementiert werden, indem ein Subtrahend invertiert und zu einem Minuenden plus einem Übertrag addiert wird, um eine Differenz zwischen dem Minuenden und dem Subtrahenden zu erzeugen. Um also ein gültiges Ergebnis für jede Komponente zu erhalten, ist es erforderlich, einen Übertrag in jedes resultierende Datenelement zu addieren. Dies kann unter Verwendung von Pufferbits durchgeführt werden, vorausgesetzt, daß die Pufferbits in sowohl dem Minuendenoperanden wie in dem invertierten Subtrahendenoperanden den Wert Eins aufweisen, so daß sie sicher ein Übertragsignal zu der nächsten Teilmatrix erzeugen.

In Fig. 7 ist der zusammengesetzte Operand 250 der Minuendenoperand, der Nullen in einigen der Pufferbits aufweisen kann. Um diesen also für eine Subtraktionsoperation vorzubereiten, wird er mit dem Operanden 260 ODER-verknüpft, der ein Maskenoperand ist, welcher in jeder Bitposition in der Teilmatrix einer Komponente OFF ist und der in jeder Pufferbitposition ON ist, wie durch die Bits 262 und 264 gezeigt. Es ist deutlich, daß die Maske 260 das Komplement der Maske 220 ist. Eine Implementierung kann eine der zwei Masken speichern und bei Bedarf invertieren, um die andere zu erhalten.

Die ODER-Operation erzeugt einen zusammengesetzten Operanden 270, wobei die Komponente 272 denselben Wert wie die Komponente 252 aufweist und wobei die Komponente 274 denselben Wert wie die Komponente 254 aufweist. Die Pufferbits 276 und 278 weisen den Wert Eins auf.

Der zusammengesetzte Operand 280 ist der Subtrahend, der in Darstellung durch die ODER-Verknüpfung einer Konstante 11 mit jeder Teilmatrix in einem Nur-Nullen-Operanden erhalten wurde, so daß die konstanten Datenelemente 282 und 284 jeweils den Wert 11 aufweisen und die Pufferbits 286 und 288 jeweils den Wert Null aufweisen. Der Subtrahend muß derart erhalten werden, daß alle Pufferbits den Wert Null aufweisen. Dann wird der Operand 280 invertiert, um den Operanden 290 zu erhalten, wobei die konstanten Datenelemente 292 und 294 jeweils den Wert 00 und die Pufferbits 296 und 298 jeweils den Wert Eins aufweisen. Die Invertierungsoperation wird herkömmlicherweise durch eine arithmetisch-logische Einheit (ALU) als Teil einer Zwei-Komplement-Substraktionsoperation durchgeführt, so daß sie nicht als Code implementiert werden muß.

Eine Additionsoperation addiert dann den Operanden 270 zu dem Operanden 290, um den Operanden 300 zu erhalten, wobei ein Datenelement in jeder Teilmatrix resultiert. Das resultierende Datenelement 302 gibt ein gültiges Ergebnis der Subtraktion des konstanten Datenelements 282 von der Komponente 252 wegen des Übertragsignals 304 an, während das resultierende Datenelement 306 ein gültiges Ergebnis der Subtraktion des konstanten Datenelements 284 von der Komponente 254 wegen des Übertragsignals 308 angibt.

Die Operanden 250 bis 300 erzeugen also eine Implementierung der Schritte in Fig. 4. Die Operanden 250, 270, 280 und 290 stellen dar, wie jedes Komponentendatenelement zu einer Teilmatrix zugeordnet wird. Die Operanden 270, 290 und 300 stellen dar, wie eine arithmetische Operation parallel durchgeführt wird, um trotz Zwischenkomponentensignalen wie den Übertragsignalen 304 und 308 gültige Ergebnisse zu erhalten.

Wie in der gleichzeitig anhängigen und gleichzeitig eingereichten europäischen Patentanmeldung EP-A-0 602 886 beschrieben können auch Multiplikations- und Divisionsoperationen unter Verwendung von Pufferbits und Techniken zum Erzeugen von Masken durchgeführt werden.

4. Vorverarbeitung

Fig. 8 stellt andere Implementierungen der mit Bezug auf Fig. 4 beschriebenen allgemeinen Schritte dar, welche Werte von Komponentendatenelementen vorverarbeiten. Diese Implementierung hängt von Beschränkungen ab, die auf Werte von zusammengesetzten Operanden angewendet werden.

Der Schritt in Block 350 empfängt Eingabewerte. Diese Werte werden auf positive Zahlen mit nicht mehr als q Bits beschränkt, so daß sie von 0 bis 2q reichen. Die in Fig. 8 gezeigte Implementierung führt eine arithmetische Operation durch, die einen gespeicherten Wert wie etwa einen Wert aus einer Tabelle zu jedem Eingabewert addiert, wobei die gespeicherten Werte ähnlich auf positive oder negative Zahlen mit nicht mehr als r Bits beschränkt sind und also im Bereich von ±(2r-1 - 1) liegen. Wenn zum Beispiel q = r = 4, dann reichen die Eingabewerte von Null bis 15, während die gespeicherten Werte von -7 bis +7 reichen. In diesem Beispiel kann die arithmetische Operation Werte erhalten, die von -7 bis +22 reichen. Allgemein kann eine arithmetische Operation, die einen gespeicherten Wert zu einem Eingabewert addiert, Werte erhalten, die von -n bis +m reichen, wobei n und m positive ganze Zahlen sind.

Der Schritt in Block 352 bildet einen zusammengesetzten Operanden mit einer Teilmatrix für jeden Eingabewert. Alle Teilmatrizen können dieselbe Länge aufweisen, die log&sub2;(n + m) überschreiten muß.

Der Schritt in Block 354 verarbeitet die Komponenten durch das Addieren von n zu dem Wert in jeder Teilmatrix vor, um ein nicht-negatives Ergebnis sicherzustellen, wenn ein gespeicherter Wert zu der Teilmatrix addiert wird. Der Schritt in Block 356 addiert dann einen gespeicherten Wert zu jeder Teilmatrix, um Werte zu erhalten, die von Null bis (n + m) reichen können.

Die durch den Schritt in Block 356 addierten gespeicherten Werte müssen angepaßt werden, um sicherzustellen, daß die Übertragsignale nicht zu ungültigen Ergebnissen führen. In dem oben angeführten Beispiel kann die Anpassung durch das Abtasten der zu dem zusammengesetzten Operanden zu addierenden Werte vom niedrigstwertigen Ende nach links zum höchstwertigen Ende hin vorgenommen werden. Wenn ein gespeicherter Wert kleiner als Null ist, was durch eine Eins im höchstwertigen Bit angegeben wird, dann wird eins von dem nächsten links daneben gespeicherten Wert subtrahiert. Diese Prozedur ist effektiv, weil jeder negative gespeicherte Wert ein Übertragsignal erzeugt, was keiner der nicht-negativen gespeicherten Werte tun würde. Als Ergebnis dieser Anpassung führen die durch das Addieren der negativen gespeicherten Werte erzeugten Übertragsignale zu gültigen Ergebnissen.

Der Schritt in Block 358 paßt dann die Ergebnisse von Block 256 an. Der Schritt in Block 358 kann zum Beispiel n von jeder Teilmatrix subtrahieren, um den Schritt von Block 354 zu invertieren. Daraus resultiert, daß jede Teilmatrix ein gültiges Ergebnis nach dem Addieren eines in Block 350 empfangenen Eingabewertes zu einem gespeicherten Wert vor der in Block 356 angegebenen Anpassung enthält. Die Subtraktion in Block 358 kann auf verschiedene Weise durchgeführt werden. Eine Möglichkeit besteht darin, jede Teilmatrix separat zu behandeln; der Wert in jeder Teilmatrix kann verwendet werden, um auf eine Nachschlagetabelle zuzugreifen, um einen andren Wert zu erhalten, der um n von dem Wert in der Teilmatrix reduziert ist. Eine andere Möglichkeit besteht darin, eine Nachschlagetabelle für das Ergebnis von Block 356 zu erhalten. Andere Anpassungen können nach Wunsch vorgenommen werden, um gekürzte oder in anderer Weise geeignete Daten für folgende Operationen zu erhalten.

Die Implementierung von Fig. 8 ist nützlich, um Einträge von einer Tabelle zu addieren, wie etwa beim Halbtonverarbeiten von Pixelwerten. Die Implementierung kann für die Verwendung in anderen Situationen erweitert werden.

C. Anwendungen

Die vorstehend beschriebenen allgemeinen Implementierungsmerkmale können in verschiedenster Weise in Datenverarbeitungsanwendungen verwendet werden. Sie sind jedoch besonders nützlich bei der Durchführung von einigen Typen von Bildverarbeitung, weil sie eine schnellere Verarbeitung als bei der seriellen Verarbeitung der Komponentendatenelemente erlauben. Insbesondere können die oben beschriebenen Merkmale zum Implementieren von Techniken verwendet werden, welche denjenigen ähnlich sind, die in Serra, J., Image Analysis and Mathematical Morphology, Academic Press, 1982 und Serra, J., Image Analysis and Mathematichal Morphology, Volume 2: Theoretical Advances, Academic Press, 1988 beschrieben sind. Derartige Techniken können zum Beispiel verwendet werden, um Dokumentendienste wie das Entfernen von Rauschen oder anderen nicht-informativen Merkmalen, die Korrektur einer Schrägstellung, das Codieren von Daten, das Extrahieren von Segmenten für die automatische Erstellung von Formularen oder Kontrollblättern sowie die druckerspezifische Korrektur vorzusehen. Derartige Dokumentendienste können in digitalen Kopiergeräten, einschließlich von Faxgeräten und Fotokopiergeräten, in Geräten, welche Daten erzeugen, die ein Bild für einen Drucker oder eine andere Bildausgabeeinrichtung definieren, in Geräten, welche auf Daten operieren, die ein von einem Scanner oder von einer anderen Bildeingabeeinrichtung empfangenes Bild definieren, sowie in anderen Geräten verwendet werden.

Die oben beschriebenen Merkmale können verwendet werden, um arithmetische Operationen auf Graustufen- oder Farbpixeln in vielen verschiedenen Bildverarbeitungsoperationen durchzuführen.

Die oben beschriebenen allgemeinen Implementierungsmerkmale können auch in verschiedenen anderen Anwendungen nützlich sein, wie etwa beim Durchsuchen einer Bilddaten bank nach Bildern, die einen bestimmten Satz von Merkmalen enthalten, beim Scannen von Umschlägen nach Adressen, beim Interpretieren von Formularen von einem Hochgeschwindigkeits-Scanner, bei der maschinellen Bilderkennung sowie bei der verfahrensspezifischen Druckbildkorrektur und -verifizierung.

Die vorliegende Erfindung kann auch angewendet werden, um verschiedene andere Bildverarbeitungsoperationen wie etwa das Zählen von Pixeln, die Graustufenmorphologie, die Graustufenrotation, das Erzeugen von mit einer Fehlerdiffusion verarbeiteten Bildern und das Feststellen einer Schrägstellung durchzuführen.

Die vorliegende Erfindung kann auch mit Daten verwendet werden, die nicht auf ein Bild bezogen sind. Die vorliegende Erfindung kann zum Beispiel verwendet werden, um eine Finitdifferenzanalyse oder Simulationen von physikalischen Phänomenen durchzuführen.

D. Verschiedenes

Die vorliegende Erfindung wurde mit Bezug auf mehrere Implementierungen beschrieben. Die vorliegende Erfindung kann auch durch die gemeinsame Verwendung von zwei oder mehr Implementierungen implementiert werden.

Die vorliegende Erfindung wurde mit Bezug auf Implementierungen beschrieben, in denen Komponentendatenelemente in einem zusammengesetzten Operanden durch einzelne Pufferbits getrennt sind. Die vorliegende Erfindung kann aber auch mit mehreren Pufferbits zwischen Komponentendatenelementen implementiert werden.

Die vorliegende Erfindung wurde mit Bezug auf eine Zwischenkomponenten-Verhinderungsschaltung beschrieben, die eine Gatterschaltung oder ein Maskenregister umfaßt. Die vorliegende Erfindung kann auch mit anderen Typen von Zwischenkomponenten-Verhinderungsschaltungen implementiert werden. Wenn sie mit einem Prozessor verwendet wird, der Übertrag-Voraussicht-Signale oder andere derartige Signale verwendet, dann könnte die Zwischenkomponenten-Verhinderungsschaltung auch verhindern, daß derartige Signale ungültige Ergebnisse verursachen.

Die vorliegende Erfindung wurde mit Bezug auf die Addition und die Subtraktion beschrieben, wobei sie jedoch auch auf andere arithmetische Operationen angewendet werden kann, die eine Multiplikation, eine Division, und eine Schwellwertfaltung umfassen, wie in der gleichzeitig anhängigen und gleichzeitig eingereichten europäischen Patentanmeldung EP-A-0 602 886 beschrieben ist.

Die vorliegende Erfindung wurde mit Bezug auf Implementierungen beschrieben, die auf Daten operieren, welche auf Bilder bezogen sind, wobei die vorliegende Erfindung jedoch auch implementiert werden kann, um auf Daten zu operieren, die sich nicht auf ein Bild beziehen.

Die vorliegende Erfindung wurde mit Bezug auf Implementierungen beschrieben, welche leicht verfügbare diskrete Komponenten enthalten. Die vorliegende Erfindung kann jedoch auch mit besonderen VLSI-Komponenten und entsprechend mit besonderen Speicherkomponenten implementiert werden.

Die vorliegende Erfindung wurde mit Bezug auf Implementierungen beschrieben, welche herkömmliche Mikroprozessoren verwenden, wobei die vorliegende Erfindung jedoch auch mit (RISC)-Chips mit einem reduzierten Befehlssatz oder mit einem anderen Prozessor, einschließlich von einem Prozessor eines Großrechners, eines Minicomputers, eines Supercomputers oder einer anderen Recheneinrichtung implementiert werden kann.

Die vorliegende Erfindung wurde mit Bezug auf zusammengesetzte Operanden mit einfachen Strukturen beschrieben. In den vorstehend beschriebenen Beispielen weisen alle Komponentendatenelemente dieselbe Länge auf und müssen die Komponenten innerhalb eines zusammengesetzten Operanden nicht miteinander in Beziehung stehen. Die vorliegende Erfindung kann auch mit zusammengesetzten Operanden mit einer zusätzlichen Struktur innerhalb der Beschränkungen der Prozessorbreite implementiert werden. Zum Beispiel könnte ein zusammengesetzter Operand Komponentendatenelemente verschiedener Breite umfassen, vorausgesetzt, daß andere Operanden mit Komponenten derselben Breite in denselben Positionen ausgerichtet sind. Weiterhin können die Komponentendatenelemente in Gruppen von zwei oder mehr ausgerichtet sein, wobei die Komponenten in jeder Gruppe miteinander in Beziehung stehen: wenn die Komponenten in jeder Gruppe auf dasselbe Pixel Bezug nehmen, dann kann jede Komponente einen Wert für eine entsprechende Schwellwertreduktion speichern. Wenn allgemein die Komponenten in jeder Gruppe auf dieselbe Position in einem physikalischen Simulationsraum Bezug nehmen, dann kann eine Komponente einen Wert für die Position speichern und können die anderen Positionen Ableitungen an der Position speichern.


Anspruch[de]

1. Verfahren zum Betreiben eines Prozessors (66), der eine Verarbeitungsschaltung (94) zum parallelen Durchführen von arithmetischen Operationen auf Operanden umfaßt, wobei die Verarbeitungsschaltung (94) eine Vielzahl von Verarbeitungspositionen jeweils zum Durchführen von Operationen auf einem Bit aufweist, wobei die Verarbeitungsschaltung (94) eine Positionenverbindungsschaltung (98) zum Verbinden der Verarbeitungspositionen (96) umfaßt, um eine Matrix von Verarbeitungspositionen zu bilden, wobei die Positionenverbindungsschaltung (98) benachbarte Verarbeitungspositionen (96) verbindet, so daß ein Signal von einer der Verarbeitungspositionen zu einer benachbarten Verarbeitungsposition übertragen werden kann,

wobei das Verfahren folgende Schritte umfaßt:

a) Ausgeben von einer oder mehreren Sequenzen (200) aus zwei oder mehr Komponentendatenelementen (202, 204), die jeweils mehr als ein Bit umfassen, an die Verarbeitungspositionen (96) in der Verarbeitungsschaltung (94), wobei jede Sequenz wenigstens ein erstes Komponentendatenelement (204) mit einem höchstwertigen Bit neben einem niedrigstwertigen Bit eines zweiten Komponentendatenelements (202) in der Sequenz aufweist,

b) Vorsehen eines Pufferbits (216, 236, 246, 256, 286, 288, 276, 278, 296, 298) zwischen dem ersten und dem zweiten Komponentendatenelement in der Sequenz, wobei die Sequenz aus den Komponentendatenelementen einen zusammengesetzten Operanden bildet, er das Pufferbit enthält,

c) Betreiben des Prozessors (66) zum Durchführen einer parallelen arithmetischen Operation auf dem zusammengesetzten Operanden, wobei die arithmetische Operation eine Operation ist, die gewöhnlich ein Zwischenkomponentensignal vom ersten Komponentendatenelement zum zweiten Komponentendatenelement erzeugt, welches verursacht, daß die arithmetische Operation ein ungültiges Ergebnis für das zweite Komponentendatenelement erhält, wobei das Pufferbit einen Wert aufweist, welcher sicherstellt, daß die arithmetische Operation trotz des Zwischenkomponentensignals ein gültiges Ergebnis für das zweite Komponentendatenelement erhält, wobei die arithmetische Operation für jedes Komponentendatenelement ein entsprechendes resultierendes Datenelement erhält, das ein gültiges Ergebnis der arithmetischen Operation auf dem Komponentendatenelement angibt,

dadurch gekennzeichnet ist, daß

das Pufferbit entweder das höchstwertige Bit des ersten Komponentendatenelements oder das niedrigstwertige Bit des zweiten Komponentendatenelements ersetzt.

2. Verfahren nach Anspruch 1, wobei der Schritt zum Betreiben des Prozessors (66) das Erhalten eines Wertes in der Position des Pufferbits umfaßt, so daß die Position des Pufferbits nicht auf das Zwischenkomponentensignal antwortet, indem es ein Signal für die Positionenverbindungsschaltung (98) ausgibt.

3. Verfahren nach Anspruch 1 oder 2, wobei das niedrigstwertige Bit des zweiten Komponentendatenelements das Pufferbit ist.

4. Verfahren nach Anspruch 1 oder 2, wobei das höchstwertige Bit des ersten Komponentendatenelements das Pufferbit ist.

5. Verfahren nach wenigstens einem der vorstehenden Ansprüche, welches weiterhin folgenden Schritt umfaßt:

Ausgeben einer zweiten Sequenz aus zwei oder mehr Komponentendatenelementen, welche jeweils mehr als ein Bit umfassen, an die Verarbeitungspositionen (96) in der Verarbeitungsschaltung (94), wobei die zweite Sequenz ein Pufferbit umfaßt, das mit dem Pufferbit in der zuerst genannten Sequenz ausgerichtet ist,

wobei die arithmetische Operation auf der ersten und der zweiten Sequenz durchgeführt wird.

6. Verfahren nach wenigstens einem der vorstehenden Ansprüche, wobei die arithmetische Operation eine Addition ist und das Pufferbit den Wert Null aufweist.

7. Verfahren nach wenigstens einem der Ansprüche 1 bis 5, wobei die arithmetische Operation eine Subtraktion ist und das Pufferbit den Wert Eins aufweist.







IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

  Patente PDF

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com