DE3887135T2

DE3887135T2 - Permutationsbitabbildungsarchitektur für zellulare rastergrafikadressierung.

Info

Publication number: DE3887135T2
Application number: DE3887135T
Authority: DE
Inventors: Charle Rupp; William Stronge
Original assignee: Fairchild Semiconductor Corp
Current assignee: Fairchild Semiconductor Corp
Priority date: 1987-03-16
Filing date: 1988-03-14
Publication date: 1994-07-28
Anticipated expiration: 2008-03-15
Also published as: US4882683B1; EP0349582B1; EP0349582A4; JPH03500459A; US4882683A; WO1988007235A1; EP0349582A1; DE3887135D1

Description

Technisches Feld

Die Erfindung bezieht sich auf ein neues Computergraphikbilderzeugungssystem, eine Rahmenpufferspeichersteuerung und eine flexible Rahmenpufferadreßarchitektur für Rastergraphikmaschinen. Die Erfindung stellt einen neuen Rahmenpufferadreßgenerator und Adreßschaltungen für den Zugriff auf Rahmenpufferspeicherstellen mit unterschiedlichen Zellkonfigurationsadreßmoden bereit, um die Leistung und die Effizienz zu erhöhen. Die Erfindung stellt einen neuen Graphikbilddatengenerator für die Erzeugung, Modifizierung und Auffrischung von Graphikbilddaten in den Rahmenpufferspeicherstellen bereit, auf welche durch die vielfachen Adreßmoduswörter und Zellkonfigurationen des Adreßgenerators zugegriffen wird. Der Graphikbilddatengenerator stellt beispielsweise Vektorzeichnung, Polygonauffüllung, "Bit Blt's" oder Bitblockübergänge bereit und frischt die Wiedergabe einer Rastersichtoberfläche auf. Die Erfindung bezieht sich zudem auf eine neue und ungewöhnliche permutierte Bitmappenorganisation von Graphikbilddaten in den Rahmenpufferspeicherstellen. Die Rahmenpufferspeicherschaltung beeinhaltet lineare Permutationsnetzwerke, die die Benutzer -X-, -Y- oder -X-, -Y-, -Z-Koordinatenadressen permutieren, um Standardbitmappen mit permutierten Bitmappen auszutauschen, welche mehrfache Wort- und Zelladreßierungsmoden anpassen. Parallele Verarbeitung von Daten, auf die zugegriffen wurde, wird dadurch erreicht, daß ein Rahmenspeicher benutzt wird, welcher mehrfache Speicherbänke umfaßt. Die Erfindung schließt auch neue dreidimensionale permutierte Bitmappenorganisation mit variabler Anzahl von mehrfachen Ebenen in der dritten oder Z-Dimension ein, um die Anzahl der Bits, welche jedes Pixel definieren, zu variieren.

Hintergrundwissen

In Computerrastergraphikmaschinen wird ein Bild typischerweise durch Rasterabtastung auf einem Bildschirm oder einer Rasterwiedergabesichtoberfläche dargestellt. Jedes kleinste Bildelement auf einem Bildschirm oder einer Sichtoberflächenstelle wird als Pixel bezeichnet, und jedes Pixel ist durch ein oder mehr Bits an einer oder mehreren Speicherstellen des Bilddatenspeichers definiert. In der einfachsten Rastergraphikdarstellung ist ein Pixel an jeder Wiedergabestelle durch ein Bit an einer entsprechenden Speicherstelle des Bilddatenspeichers definiert. Der Graphikbilddatenspeicher wird als Bildrahmenpuffer, Bildauffrischpuffer oder Bildbitmappe bezeichnet. Der Rahmenpuffer ist typischerweise als Festkörper-Schreib-Lese-Speicher (RAM) integrierter-Schaltkreis- (IC)-Chip ausgebildet, der möglicherweise aus Mehrfachspeicherbänken besteht. Der Rahmenpuffer wird als Auffrischpuffer bezeichnet, weil der Bildrahmen auf einem Röhrenbildschirm mit dem Inhalt des Rahmenpuffers aufgefrischt wird, typischerweise in 30 oder 60 Rasterzyklen pro Sekunde. Der Rahmenpuffer wird auch als Bitmappe bezeichnet, weil der Inhalt oder die Bits an den Speicherstellen des Rahmenpuffers auf den Bildschirm oder die Sichtoberfläche durch einen Raster-Scan-Generator abgebildet werden. Die Inhalte der Rahmenpuffer werden durch einen Video-Abtastliniengenerator als linearer Strom organisiert, um die Intensität der Bildröhre zu kontrollieren.
Typischerweise gibt es eine feste Eins-zu-Eins-Beziehung zwischen den Speicheradreßstellen in dem Rahmenpuffer und den Pixelpositionen auf dem Bildschirm oder der Sichtoberfläche, identifiziert als Benutzer/Beobachter-X, -Y-Koordinatensystem. Dort, wo jedes Pixel der Rasterwiedergabesichtoberfläche durch mehr als ein Bit, z. B. 1, 2, 4, 8 oder 16 Bits etc. definiert ist, werden die Rahmenpufferspeicherstellen organisiert in Ebenen, beispielsweise 1, 2, 4, 8 und 16 Ebenen etc., angesehen, entsprechend den mehrfachen Bits pro Pixel. Die Ebenen können als Addition einer dritten Dimension zu der Bitmappe angesehen werden. Die mehrfachen Bits pro Pixel tragen eine Mehrfach-zu-Eins-Beziehung mit Pixelpositionen der Benutzer-X, -Y-Koordinatensystemsichtoberfläche und werden benutzt, um Farbton, Grauskala, Auflösung etc. zu definieren und ein Bild mit größerer Schärfe bereitzustellen.
Die Inhalte der Rahmenspeicher werden zu der Video-Wiedergabesektion in einer linearen Sequenz mittels aufeinanderfolgender Speicherzyklen übergeben. Aufeinanderfolgende Speicherzyklen greifen auf den Rahmenspeicher in Standardbitmappenwortmodusadressierung oder Wortkonfigurationsadressierung der mehrfachen RAMS oder Speicherbänke zu, aus denen der Rahmenpuffer sich aufbaut. Jeder Speicherzyklus oder Speicherzugriffszyklus greift auf jede der Speicherbänke fortfolgend zu und bezieht eine Sequenz von Bits von den aufeinanderfolgenden RAMs oder Speicherbänken, die vermutlich als ein horizontales Wort oder Teil der Reihe der Standardbitmappe oder ein horizontales Wort oder Teil einer Reihe von Pixel auf der Benutzer-X, -Y-Koordinatensystemsichtoberfläche angesehen werden kann. Jede Scanzeile des Rastermusters besteht aus einer Sequenz solcher Worte, welche von der Bitmappe wiederbekommen wurden und komplette Reihen oder Scanzeile über die Sichtoberfläche formen. Die halbe Speicherbandbreite oder Speicherzykluszeit des Rahmenpuffers wird typischerweise für den Auffrischspeicherzugriff benutzt.
Der andere Teil der Speicherbandbreite oder der Speicherzykluszeit steht für die Aktualisierung des Rahmenpuffers oder des Auffrischungspufferbildspeichers zur Verfügung. Dies wird auch als Schreiben, Zeichnen oder Malen neuer Bilder, Bildteile oder Bildelemente in dem Rahmenpuffer bezeichnet. Im Falle einer Bildröhrenwiedergabe wird die Aktualisierung typischerweise durch Verzahnung während des Auffrischens ausgeführt. Die neuen Inhalte werden durch Auffrischung des Bildes auf dem Bildschirm oder der Sichtoberfläche wiedergegeben. Ein Nachteil der konventionellen Rastergraphikwortmodusarchitektur und der Standardbitmappe besteht darin, daß die Aktualisierung des Rahmenpuffers durch "Zeichnen" oder "Malen" dadurch ausgeführt wird, daß dieselbe Wortmodenadressierung und Horizontalwortkonfiguration für den Zugriff der mehrfachen RAMs oder Speicherbänke benutzt wird. Dies ist ein Nachteil, weil der eindimensionale horizontale Wortmodus oder die Wortkonfigurationsadressierung, welche für effizienten Zugriff auf den Inhalt des Rahmenpuffers zur Auffrischung des gesamten Bildschirms adaptiert wurde, nicht auf die einfache Geometrie kleinerer zweidimensionaler Flächen zu zeichnender Vektoren vergrößert werden kann.
Beim Vektorzeichnen und -malen wird nur auf einen bestimmten Teil des Rahmenpufferbedarfs zugegriffen, um einen kleinen Teil des Sichtoberflächenbereiches zu zeichnen, zu malen oder zu modifizieren. Die Wortmodusadressierung zwingt die Rastergraphikmaschine, auf eine Anzahl von Speicherstellen zuzugreifen, die diejenige für eine bestimmte Rahmenspeicheraktualisierung,z. B. das Zeichnen eines Vektors, weit überschreitet. Dies liegt daran, daß die konventionelle Wortmodenarchitektur und -adressierung nur nach langen horizontalen Wortsequenzen oder Reihenteilen der Bitmappe in sukzessiven Speicherzyklen sucht. Der Vektor oder das Zeichen, welches gemalt werden soll, paßt realistischer zu einem kleinen vertikal orientierten zweidimensionalen Rechteck. Überschüssige Zeit mehrfacher Speicherzyklen ist deshalb zur Aktualisierung des Rahmenpuffers beim Zeichnen und Malen erforderlich, und die zur Verfügung stehende Rahmenpufferspeicherbandbreite oder die zur Verfügung stehende Speicherzykluszeit wird ineffizient genutzt.
Die Effizienz oder Leistung der Rastergraphikmaschine kann als Funktion der Anzahl von pixeldefinierenden Bits auf dem Bildschirm, welche tatsächlich geändert oder in jedem Zyklus aktualisiert werden, gemessen werden. Wenn z. B. jeder Speicherzyklus auf 64 Bits an 64 Speicherstellen der Speicherbank in Form eines 64-Bit horizontalen Adreßworts zugreift, wird ein 16-Bit oder 16-Pixel vertikaler oder diagonaler Vektor ineffizient im Rahmenpuffer gezeichnet oder aktualisiert. In einem Rahmenpuffer mit einer Ebene wird vielleicht nur ein Bit korrespondierend einem einzelnen Pixel auf dem Schirm in jedem Speicherwortzugriffszyklus aktualisiert. Daher sind bis zu 16 der Wortspeicherzugriffszyklen erforderlich, das Zeichnen der Vertikalen oder die Aktualisierung des diagonalen Vektors zu vervollständigen, wobei nur ein Bit bei jedem 64-Bit Wortspeicherzugriffszyklus aufgefrischt wird.
Eine zellulare Architektur für rastergescante Rahmenspeicherwiedergabe wird beschrieben durch Satish Gupta und Robert F. Sproull, Carnegie-Mellon Universität, und Ivan E. Sutherland in "A VLSI Architecture for Updating Raster-Scan Displays", Computer Graphics, Band 15, Nr. 3, Seiten 333-340, August 1981, auch veröffentlicht in Proceedings of SIGGRAPH 81, Seiten 71-78, Association of Computing Machinery, 1981. Das System wird auch in der Dissertation zur Erlangung des Doktorgrades von Satish Gupta mit dem Titel "Architectures and Algorithms for Parallel Uptdates of Raster-Scan Displays" beschrieben, eingereicht am Computer Science Department der Carnegie-Mellon Universität im Dezember 1981 mit Urheberrecht von 1982. Gupta, Sproull und Sutherland offenbaren eine 8· 8 Bitzellenorganisation des Rahmenpufferspeichers anstatt der konventionellen horizontalen wortorientierten Speicherorganisation für den Zugriff auf den Rahmenspeicher durch einen einzelnen zweidimensionalen 8· 8 Bit-Zellkonfigurationsadressierungsmodus.
Bezüglich dieses Zelladressierungskonzepts sind die Rahmenpufferadressierung und die Kontrollschaltkreise und die Bitmappen so gestaltet, daß der Zugriff auf aufeinanderfolgende Speicheradreßstellen der Speicherbänke in einer Zellkonfiguration entsprechend einer rechteckigen Zelle von Pixeln auf der Sichtoberfläche oder dem Bildschirm erlaubt ist. Das Zellkonfigurationsrechteck ist aus einer ähnlichen Anzahl von Bits oder Pixeln als ein Horizontalwortmodusadressierungswort zusammengesetzt, z. B. 64 Bits. Gleichwohl ist die Zelladressierungskonfiguration, die auf dem Bildschirm oder der Sichtoberfläche betrachtet wird, zweidimensional. Resultierend kann der Rahmenspeicher aktualisiert werden, und eine Vertikale oder ein diagonaler Vektor oder ein zweidimensionales Zeichen kann bei eingeschränkter Anzahl von Speicherzugriffszyklen zur Aktualisierung oder Zeichnung der erforderlichen Bits und Pixel gezeichnet werden. Die Leistungsfähigkeit, Vektoren zu zeichnen, welche konventionellerweise auf ein Bit oder ein Pixel, welches geändert oder pro Speicherzyklus aktualisiert wird, beschränkt ist, wird gesteigert auf mehrfache Bits oder Pixel, welche gewechselt oder je Speicherzugriffszyklus aktualisiert werden.
Der 8·8 Zelladressierungsmodus erlaubt größere Leistung bezüglich der Anzahl von je Speicherzugriffszyklus aktualisierten Pixeln während der Aktualisierung des Rahmenpuffers zur Zeichnung zweidimensionaler Vektoren, Zeichen und Bitblockübergaben. Ein Nachteil des Gupta- Sproull- und Sutherland-Systems ist jedoch, daß die Auffrischung der Wiedergabe weniger effizient ist als im Fall der horizontalen Wortmodusadressierung, weil die rechteckige Adressierungsmoduszelle für die Auffrischung oder die Wiedergabe der Inhalte des Rahmenpuffers über die Sichtoberfläche genutzt werden muß. Nur eine Zeile der 8·8 Bit Zelle von jedem Speicherzugriffszyklus wird genutzt, um eine bestimmte aufgefrischte Scanlinie zusammenzusetzen. Die Systemarchitektur von Gupta et al. kann nur einen Adressierungsmodus erreichen und ist durch die gewählte Zellkonfiguration und eine Bitmappenorganisation, die nur einen Adressierungsmodus erlaubt, eingeschränkt.
Eine andere zellartig organisierte Rasterwiedergabearchitektur mit einer 8·8 Pixelzelle wird durch Jordan and Barrett in "A Cell Organized Raster Display for Line Drawings", CACM, Band 17(2):70, Februar 1974 und "A Scan Conversion Algorithm with Reduced Storage Requirements", CACM, 16(11):676, November 1973, beschrieben. Weiteres Hintergrundwissen bezüglich Computergraphik-Rasterwiedergabe-Rahmenpufferarchitektur wird gegeben durch Foley & Van Dam, Fundamentals of Interactive Computer Graphics, Addison-Wesley Company, Reading, Massachusetts, 1982, Kapitel 3, 10 12 ff. und Newman und Sproull, Principles of Interactive Computer Graphics, 2. Auflage, McGraw-Hill Book Company, New York, New York, 1979, Kapitel 15-19. Nach Foley und Van Dam nutzen die Bildschirme der Tektronix- 4025- und 4027-(Warenzeichen)- Zellkodierung, bei der Speicher durch Speicherung von 8·14 Pixel großen Zellen belegt wird. In der vorhergehenden Referenz ist die Architektur limitiert durch einen Adressierungsmodus mit einer generell einfachen oder geradlinig standardisierten oder konventionellen Bitmappenorganisation, die nur eine Adressierungsmoduszellkonfiguration während des Rahmenpufferspeicherzugriffszyklusses anpassen kann.
Beim Texas Instrument TI 34010 Graphiksystemprozessor oder GSP können eine unterschiedliche Anzahl von Ebenen, beispielsweise 1, 2, 4, 8 oder 16 Ebenen, ausgewählt werden. Dieses Rastergraphiksystem ist daher in der Lage, Pixel durch die unterschiedlich ausgewählte Anzahl mehrfacher Bits zu definieren. Ein unterschiedliches horizontales Adressierungswort ist verbunden mit jeder Auswahl einer Anzahl von Ebenen. Daher gibt es unterschiedliche Adressiserungsworte. Eine unterschiedliche Bitmappe, aber eine solche vom Standardtyp, ist verbunden mit jeder Auswahl einer unterschiedlichen Anzahl von Ebenen. Ist jedoch die Anzahl der Ebenen und entsprechenden Standardbitmappen gewählt, so ist nur ein Adressierungswort oder Modus verfügbar.
Ein sogenannter "Pixel-Cache" wird auf dem Niveau eines generellen Blockdiagrammes in einem Artikel von Andy Goris, Bob Frederikson und Harold L. Baeverstad von Hewlett-Packard Co., "A Configurable Pixel Cache for Fast lmage Generation", IEEE CG&A, März 1987, Seiten 24-32, beschrieben. Es wird behauptet, daß der Pixel Cache seriell Pixeldatenbits zusammenzieht und ein rechteckiges Feld oder eine "Kachel" von Rahmenpufferspeicherpixeldatenbits hält. Die Abwesenheit jeglicher vollziehbarer Offenbarung in der Goris et al. Publikation schränkt die Bedeutung dieser Veröffentlichung stark ein. Es gibt keine Offenbarung oder Lehre, wie der Pixel-Cache zu benutzen wäre oder wie er in einer Schaltung auszuführen wäre. Es gibt keinen Hinweis, daß der "Pixel-Cache" irgendetwas anderes ist als ein konventioneller Adressierungsschaltkreis oder Generator, der mit einer Standardbitmappe (SBM) durch sequentiellen Speicherzugriff operiert. Die Bitmappentabelle von Fig. 6 der Goris et al. Veröffentlichung scheint tatsächlich nicht mehr zu sein als eine Anleitung, wie auf eine Standardbitmappe durch sequentiellen Speicherzugriff zuzugreifen ist, um unterschiedliche "Kachel"-Organisationen der Pixel oder Pixeldatenbits zu erreichen. Es besteht kein Hinweis, daß mit der Tabelle von Fig. 6 beabsichtigt wird, eine physikalische Rahmenpufferbitmappe zu repräsentieren, noch jegliche Würdigung, daß es eine physikalische Bitmappe sein könnte, oder wie solch eine Rahmenpufferbitmappe ausgeführt werden könnte.
US-A-3996559 beschreibt einen zweidimensionalen Bildspeicher mit einem linearen Permutationsnetzwerk für den Zugriff auf horizontale und vertikale Sequenzen und Blöcke in einem Speicher.
Weitere Diskussionen der bisherigen Kenntnisse und dem Stand der Technik in Rastergraphikarchitekturen, Bitmappen und Adressierungsmoden sind in der Anmelder-Informations- und Offenbarungsangabe zusammen mit einer Diskussion von unterscheidenden und kontrastierenden Merkmalen der vorliegenden Erfindung zu finden. Die Anmelder-Informations- und Offenbarungsangabe und die zitierten Druckschriften sind hier beigefügt.

Gegenstand der Erfindung

Es ist daher ein Ziel der vorliegenden Erfindung, eine neue und flexible Rastergraphikarchitektur und Rahmenpufferbitmappen bereitzustellen, die mehr als drei unterschiedliche Zell- und Wortadressierungsmoden oder mehr als drei Zell- und Wortkonfigurationen für den Zugriff auf die Rasterwiedergabe-Rahmenpufferspeicherstellen unterbringen.
Ein anderer Gegenstand der Erfindung ist es, Rahmenpufferadressierungs- und Kontrollschaltungen bereitzustellen, die die Auswahl aus einem Bereich von Zell- oder Wortkonfigurationsadreßmoden erlauben, um ein bestimmtes Bildzeichnungserfordernis zur Optimierung der Leistung anzupassen. Die Erfindung nutzt die einfache Geometrie zu zeichnender oder aktualisierender Vektoren und Zeichen bei der Adressierung des Rahmenpuffers. Das heißt, die neue Architektur der vorliegenden Erfindung beabsichtigt, die Wahl geeigneter Moden aus einer Vielzahl alternativer zellularer Adreßmoden zu erlauben, um die Anzahl von dienlichen Bits der Rahmenpufferbitmappe und der korrespondierenden Pixel zu optimieren und zu maximieren, welche in jedem Speicherzyklus herangezogen oder aufgefrischt werden. In dieser Anordnung wird die Anzahl der Speicherzugriffszyklen minimiert, wobei die Zeit, welche erforderlich ist, eine Graphikzeichenoperation durchzuführen, reduziert wird. Von der verfügbaren Speicherbandbreite und Speicherzykluszeit, welche nicht für die Auffrischung des Wiedergabeschirms erforderlich ist, wird optimaler Gebrauch gemacht.
Ein weiterer Gegenstand der Erfindung ist es, multizellulare Adressierungsmoden einschließlich beider Alternativen zweidimensionaler Zellen und horizontaler Wörter bereitzustellen. Ein Merkmal und Vorteil dieser flexiblen Architektur ist, daß die Vektorzeichnungsleistung dramatisch mit der zweidimensionalen zellularen Adressierung verbessert wird unter Erhaltung der hohen Effizienz horizontalen Wortzugriffs auf den Rahmenpuffer, um die Rasterwiedergabe wieder aufzufrischen.
Daher ist ein weiterer Gegenstand der Erfindung, eine flexible Organisation der Rahmenpufferspeicheradreßstellen in einzelne und mehrfache Ebenen durch Addition einer flexiblen dritten Dimension zur Bitmappe bereitzustellen unter Erhaltung multizellularer und Wortadressierungsmoden für jede ausgewählte Anzahl von Ebenen. Gemäß diesem Merkmal bringt die Rahmenpufferarchitektur effektiv mehr als drei dreidimensionale Adressierungsmodenzellen und Wortkonfigurationen für selektive variable Bildpixelwiedergabe-Definition der Farbskala, Grauskala, Auflösung etc. unter.
Ein hiermit verbundener Gegenstand der Erfindung ist es, ein Bilderzeugungssystem und einen Bilddatengenerator für Rastergraphikmaschinen bereitzustellen, der in der Lage ist, die Rastergraphik-Rahmenpufferarchtiktur und die Bitmappen in der neuen flexiblen Adressierung zu betreiben. Der Datengenerator ist in der Lage, Rasteroperationen auf Graphikbilddaten auszuführen, auf welche unter irgendeiner der verschiedenen Adressierungsmoden zugegriffen wurde.

Offenbarung der Erfindung

Mit dem Ziel, diese Resultate zu erhalten und mehrfache Zell- und Wortadressierungsmoden unterzubringen, ist eine höchst ungewöhnliche Bitmappenorganisation in der vorliegenden Erfindung vorgesehen. Zu diesem Zweck sind die Speicherstellen und die entsprechenden Speicheradressen der Rahmenpufferspeicherbank nicht konventionellerweise als Reihen- und Spaltenanordnung einer Standardbitmappe oder SBM entsprechend einer simplen arithmetischen oder identischen Bitmappenrelation mit dem Benutzer/Beobachter-X-, Y-Koordinatensystem organisiert. Vielmehr sind die Adressen oder Speicherstellen des Rahmenpuffers in einer ungewöhnlichen Ordnung permutiert. Die Bilddatenrahmenpufferbitmappe bildet eine lineare Permutation oder Transformation von der einfachen Reihen-oder Spalten-Benutzer-X,-Y-Koordinatenadreßanordnung auf dem Wiedergabeschirm oder der Sichtoberfläche. Um die Konsequenz dieser permutierten Ordnung zu veranschaulichen, kontrolliert jede Speicherbank anstatt einer ordentlichen Sequenz von Spalten von Pixeln auf der Sichtoberfläche eine komplexe Verteilung von Pixeln über den Schirm, umfassend eine komplex lineare Permutation der originalen konventionellen Spalten und Reihen der Pixel in dem Benutzer/Beobachter-X-,-Y-Koordinatensystem.
Nach der Erfindung beinhalten die Adreß- und Kontrollschaltkreise für den Rahmenpuffer logische Linearpermutationsnetzwerke oder Operatoren zur Erreichung und Ausführung dieser ungewöhnlichen Organisation. Die Bitmappe selbst ist organisiert als eine komplexe logische Linearpermutation der Benutzer-X, -Y-Koordinatensystemorganisation von Bildpixeladreßpositionen auf der Wiedergabeoberfläche. Die linearen Permutationsoperatoren, welche mit der Rahmenpufferadressierung und Kontrollschaltkreisen verbunden sind, speichern die Bilddatenbits in dem Rahmenpuffer in einer permutierten oder gewebten Ordnung und bilden dadurch eine neue Permutationsbitmappe oder PBM, welche den Adressierungszugriff in unterschiedlichen mehrzelligen Zellkonfigurationen und Wortmoden unterbringt. Ein Bilddatengeneratorschaltkreis ist ebenfalls vorgesehen, welcher logische Linearpermutationsnetzwerke und Linearpermutationsoperatoren verbindet, um Bilddaten zu normalisieren, welche auf dem Rahmenpuffer in mehrzelligen Zugriffsmoden entnommen wurden, um Boole'sche Operationen auf Bilddaten anzuwenden, welche vom Rahmenpuffer entnommen wurden. Die ungewöhnliche permutierte oder gewebte Ordnung wird in den bearbeiteten Bilddaten wieder hergestellt bei der Rückgabe der Permutationsbitmappe auf den Rahmenpuffer.
Ein Adreßgeneratorsschaltkreis oder AGEN mit dazugehöriger Adreßschaltung empfängt Kommandosignale von einem Wirtscomputer, einer CPU, einem Mikroprozessor oder einem programmierbaren Graphikprozessor etc. Der AGEN empfängt ebenfalls Bilddatenadreßkoordinateninformation im originären Benutzer-X, -Y-Koordinatensystem oder -raum entsprechend einem Standardkoordinatenraum. Das AGEN und zugehörige Adreßschaltkreise transformieren die Bilddatenadressen in den permutierten oder "gewebten" Adreßraum und begründen damit einen permutierten Bitmappen- oder neuen PBM-Koordinatenraum des Rahmenpuffers. Das AGEN liefert umgekehrt Kommandoworte oder Operationscodes an den Rahmenpuffer, Bilddatengeneratorschaltkreis oder DGEN, welcher die Graphikbilddaten verarbeitet, welche vor der permutierten Bitmappe stammen, um den Rahmenpufferspeicher zu aktualisieren und die Rasterwiedergabe aufzufrischen.
Bei der Ausführung der neuen Rastergraphikarchitektur permutieren logische Linearpermutationsnetzwerke (LPNs), welche selbst-symmetrische reversible logische Funktionen oder Tore beinhalten, die Adreßsequenz des BEnutzer-X, -Y-Koordinatenraumes in einen permutierten Rahmenpuffer oder PBM Speicherbank- oder Bankadreßraum, B,A. Die LPNs sind mit beiden verbunden, den Adreßschaltkreisen und den Datengenerations-oder Bilderzeugungsschaltkreisen. Diese LPN-Schaltkreise verwirklichen logische oder Boole'sche Linearpermutationsoperatoren oder primitive, wie Auswechsel- und zyklische oder Rotations-LPN-Operatoren. Sogenannte Drahtlinearpermutationsnetzwerkoperatoren oder primitive oder Draht-LPNs, wie Umkehrung, Schmetterling und Schiebe-LPN-Operatoren werden kombiniert mit den logischen LPNs.
Die Erfindung schließt in die flexible Adressierungsarchitektur eine dritte Dimension in der Form einer flexiblen Anzahl von Bitebenen der Organisation der Rahmenpuffer entlang der dritten Z-Koordinate ein. Die Anzahl der ausgesuchten Ebenen entlang der Z-Koordinate stimmt mit der Anzahl von Bits, die jedes Pixel definieren, überein und addiert effektiv eine flexible dritte Dimension oder Bittiefe Z zur Bitmappe und dem Benutzer-Koordinatensystem. Das dreidimensionale Benutzer-X, -Y, -Z-Koordinatensystem oder der SBM-Raum ist deshalb gemäß der Erfindung permutiert oder gewebt, um vielzahlige dreidimensionale Adreßmodenzellen und Wörter in einer neuen dreidimensionalen PBM-Raum- oder Permutationsbitmappe unterzubringen.
Die Adressen, welche vom Adreßgenerator und der verbundenen Schaltung im X-, Y-, Z-Benutzerkoordinatenraum empfangen werden, werden in einem bevorzugten Beispiel in den physikalischen Speicherbank- und Bankadreß-PBM-Koordinatenraum in zwei Permutationsschritten transformiert. Zuerst werden die Adressen im Benutzer-X-, -Y-, -Z-Koordinatenraum in einen abstrakten permutierten C-, U-, S-Adreßraum transformiert oder als Bitmappen aus dreidimensionalen Blocksektionsadressen S zusammengesetzt, welche Untereinheiten der dreidimensionalen Adreßbitmappe in mehreren Ebenen und korrespondierenden Untereinheiten eine Rastersichtoberfläche repräsentieren, die Bittiefendimension umgebend. Die Blocksektionen sind dann in dreidimensionale Zellen unterteilt. Die Zellen sind dann unterteilt in Einheiten U von Bilddaten, welche in der bevorzugten Ausführung Einheiten von vier Bits bilden, welche als quadratische Pixel bezeichnet werden sollen, wobei eine Einheit von jeder Speicherbank des Rahmenpufferspeichers in einem Speicherzugriffszyklus abgeleitet wird.
Die Transformation vom Benutzer-X-, -Y-, -Z-Koordinatenraum zum abstrakten C-, U-, S-Organisationskoordinatenraum wird bewerkstelligt durch die Verwendung einer neuen Multiplexier- oder Schalter-LPN Op, welches tatsächlich ein logisches LPN ist, konstruiert, um auf mehr als einem Index zu arbeiten und in der Lage zu sein, zwei oder mehrere Dimensionen des SBM, PBM und zwischengelagerter Adreßräume zu mischen.
Der zwischengelagerte C-, U-, S-Bitmappenadreßraum wird dann durch weitere Adreßschaltungen unter Verwendung der logischen LPNs in konkrete Speicherbanknamen B und Speicherbankadreßkoordinaten Ay und Az übersetzt. Der Ay-Koordinatenadreßanteil kontrolliert den vertikalen Zugriff für eine einzelne Ebenemode, und der Az-Koordinatenadreßanteil kontrolliert die Wahl der Ebene für Adreßmoden mit einer vertikalen Höhe von einer Einheit, wie im folgenden weiter entwickelt wird. Der physikalische Speicherbankadreßkoordinatenraum mit der Bezeichnung B,Ay,Az, welcher die ungewöhnliche permutierte Ordnung hat und aus einem dreidimensionalen permutierten Rahmenpufferspeicher oder permutierter Bitmappe besteht, erlaubt den Speicherzugriff in jeder der gewünschten Adreßkonfigurationsmoden.
In einem Beispiel ist die Einzelebenen-Bitmappe zu Zell- oder Wortgrößen von 64 Bit ausgewählt und angeordnet, die Adreßmodenzelle und die Wortkonfiguration erstrecken sich vom horizontalen 64·1 Auffrischungswort, welches benutzt wird, auf den Rahmenpuffer während eines Bildschirm-Auffrischungszyklus zuzugreifen, bis zu horizontal und vertikal orientierten Rechtecken, z. B. 32·2 Bit, 16·4 Bit und 4·16 Bit Zellen zur Aktualisierung des Rahmenpuffers, während vertikal und horizontal orientierte zweidimensionale Vektoren und Zeichen gezeichnet werden. Es wird auch ein Rechteckzellen 8·8 Bit Adreßmodus bereitgestellt. Darüberhinaus kann die Zellkonfiguration innerhalb der Blöcke umgeordnet und in drei Dimensionen über 2, 4, 8 und 16 Ebenen der Organisationstiefen ausgeführt werden, entsprechend der Anzahl von Bits, die erforderlich sind, jedes Pixel zu definieren, eine Ebene für jedes Bit des Multibitpixels.
Bei der Ausführung der Datengenerationsschaltkreise oder DGEN sind logische Linearpermutationsnetzwerke, welche logische oder Boole'sche Linearpermutationsgrundoperatoren, wie Auswechsel- oder zyklische Permutationsnetzwerke verwirklichen, erneut erforderlich. Draht- LPNs, wie Umkehrung-, Schmetterling- und Schiebelinearpermutationsnetzwerke werden auch mit logischen LPNs kombiniert. Für Rasteroperationen einschließlich Raster-ops oder Bit Blts werden aus dem Rahmenpufferspeicher stammende Quelldaten für die Bit Blts oder Bitblocktransfers mit den Zieldaten aus dem Rahmenpuffer vermischt, um wieder in den Rahmenpufferspeicher nach geeigneter Maskierung zu schreiben. Entsprechend einem exemplarischen Ausführungsbeispiel werden aus dem Rahmenpuffer stammende Daten normalisiert, d. h. permutiert oder zurücktransformiert in das Benutzer-X, -Y-, -Z-Koordinatensystem oder den Standardkoordinatenraum zur Durchführung solcher Rasteroperationen. Eine Vorpermutationsoperation ist deshalb ausgeführt durch ein Vorpermutationsnetzwerk einschließlich logischen LPNs, so daß die Quelldaten und die Zieldaten im selben Koordinatenraum dargestellt werden. Alternativ können die Daten für logische Operationen angepaßt werden, entweder im normalisierten X-, Z-Koordinatenraum oder im permutierten C-, U-, S-oder B-, Ay-, Az-Koordinatenraum. Justierung und Maskierungsschritte werden mit eingeschlossen, falls erforderlich.
Abschließend wird nach der Vermischung von angepaßten und justierten Quell- und Zieldaten einer logischen Funktion oder einem Boole'schen Logikschaltkreis eine Nachpermutation oder "Postnet"-Operation durchgeführt, um alle normalisierten Daten in die ungewöhnlich permutierte oder PBM-Adreßraumorganisation der Rahmenpufferspeicherstellenadressen zurückzuführen, um in den Speicher zurückzuschreiben. Zusammenfassend werden DGEN-Transformationen vom physikalischen Speicherbankadreßkoordinatenraum B,Ay,Az auf den Benutzer-X-, -Y-, -Z-Koordinatenraum repräsentiert durch logische LPN funktionale Vorpermutationen oder Prenet-Transformationen X,Y,Z = f(B,Ay,Az), während die Nachpermutation oder Postnet- logischen LPN-Operationen die Umkehrung B,Ay,Az = f(X,Y,Z) sind.
In der bevorzugten dreidimensionalen Systemarchitektur repräsentiert die zwischengelagerte Transformation durch ein zwischengelagertes Koordinatensystem zwischen dem ursprünglichen X-, -Y-, -Z-Koordinatensystem und dem permutierten physikalischen Speicherbankkoordinatensystem B,Ay,Az die Organisation von Bilddatenbits oder Pixeln oder Speicherstellenadressen in Blöcken, Zellen und Einheiten. Dieser Organisationsmodus beeinhaltet ein wichtiges neues und unterscheidendes Merkmal der Erfindung eines Rastergraphiksystems. Da immer wenigstens zwei unterschiedliche Zellen oder Wortadressierungsmoden vorhanden sind, entsteht aus den alternativen Zellen oder Worten eine neue Ebene der Organisation oder Unterteilung der Bitmappe oder der Sichtoberfläche, welche als "Block" bezeichnet wird. Die Blockbreite ist ebenso groß wie die größte horizontale Dimension der verfügbaren Zelle oder des Wortadressierungsmodus. Die Blockhöhe ist ebenso groß wie die größte vertikale Dimension der verfügbaren Zelle oder des Wortadreßmodus. Die Zellgröße ist in Bits definiert durch das Produkt der horizontalen Dimension Hi in Bits, multipliziert mit der vertikalen Dimension Vi in Bits jeder Zelle und jedes Wortes in der zweidimensionalen Ausführung und ist für alle verfügbaren Adreßmoden, Zellen oder Zellkonfigurationen und Worte gleich groß. Die Zellgröße in Bits in zwei Dimensionen ist deshalb gleich Hi· Vi und für jedes Wort und jede Zellkonfiguration gleich groß, und sie wird bezüglich der gewünschten Gesamtleistung ausgewählt. Eine größere Zellgröße bezüglich der Anzahl von Bits ergibt eine bessere Leistung. Des weiteren füllt die gleiche Anzahl von Zellen in jeder Adressierungsmode jeden Block ohne überlapp aus, und die Blockgröße in zwei Dimensionen ist Hmax·Vmax, wobei Hmax die größte horizontale Dimension ist, z. B. 64 Bits für das 64·1 Bit Darstellungswort, und Vmax ist die größte vertikale Dimension, z. B. 16 Bits für die 4·16 Bits vertikal orientierte Zelle. In der Mehrebenen- Dreidimensional-Architektur wird die Anzahl der Ebenen P als Faktor in der Zellgröße Hi·Vi·Pi und Blockgröße Hmax·Vmax·P addiert. In jedem dieser Fälle definieren die Blöcke Grenzen, in denen alle Adressierungsmoden unterkommen als ein Satz von gleicher Anzahl von Zellen und innerhalb eines Satzes der gleichen Anzahl von Zellen jeder Adressierungsmode einen abgegrenzten Untersatz bilden. In der vorliegenden Erfindung umfaßt der Rahmenpufferspeicher eine Vielzahl von separat adressierbaren Speicherbänken für parallele Verarbeitung. Der Adreßschaltkreis adressiert jede Speicherbank B desselben Rahmenpufferspeichers in einem Speicherzugriffszyklus. Jeder Speicherzugriffszyklus greift zu auf oder generiert eine einzelne Zelle, und jede Speicherbank trägt mit einer Einheit von Bilddaten dazu bei, z. B. ein quadratisches Bit oder ein quadratisches Pixel zu jeder Zelle. Die Zellgröße steht deshalb in Beziehung zur Anzahl von verfügbaren Speicherbänken. Die Blockgröße steht in Bezug zur Anzahl von unterschiedlichen Adressierungsmoden, Zellen oder Wortkonfigurationen und zur Zellgröße. Die Einheit von Bilddaten, welche von jeder Speicherbank stammen, z. B. Quadrate von Bits, steht in ihrer Größe in Beziehung zur Bitbreite der Speicherbankkomponenten, z. B. vier Bit breiten Speicherbänken.
Die lineare Permutationsbitmappe, permutierte Bitmappe oder PBM der vorliegenden Erfindung ist durch die Rahmenpufferadreßschaltkreise in wenigstens zwei unterschiedlichen Adressierungsmoden, Zell- oder Wortkonfigurationen adressierbar. Wenigstens eine der Adressierungsmoden, Zell- oder Wortkonfigurationen entspricht einer zweidimensionalen Zelle im Benutzer-X, -Y-Koordinatensystem, einer zweidimensionalen Zelle im Benutzer-X-, -Z-Koordinatensystem oder einer dreidimensionalen Zelle im Benutzer-X, -Y-, -Z-Koordinatensystem. Ein Merkmal der Erfindung ist, daß die permutierte Bitmappe oder PBM in vielfachen Wortadressierungsmoden in vielfachen Ebenen im X-, Z-Koordinatensystem operieren kann, falls Y, die vertikale Dimension, auf Null gesetzt wird. Die vorliegende Erfindung stellt durch die Änderung der Anzahl von Ebenen in derselben Bitmappe und der Änderung der horizontalen Dimension der horizontalen Adressierung und dem wiedergegebenen Wort eine Vielzahl von Worten adressierende Bitmappe im X-, Z-Koordinatensystem dar. Dieses Merkmal der Erfindung stellt permutierte Bitmappen für Mehrfach-Wort-und Mehrfach-Zell-Adressierungsmoden dar, und zwar entweder bezüglich des X-, Y-Koordinatensystems, X-, Z-Koordinatensystems oder des X-, Y-, Z-Koordinatensystems des Benutzers.
Im bevorzugten Beispiel umfassen die linearen Permutationsnetzwerke wenigstens ein Boole'sches oder logisches Linearpermutationsnetzwerk (LPN), welches selbstsymmetrische reversible Boole'sche logische Funktionen oder Tore einschließt. Ein Merkmal und ein Vorteil dieser Anordnung besteht darin, daß eine reversible Eins-zu-Eins-Beziehung zwischen der Eingabe und der Ausgabe besteht, so daß die Graphikbilddaten nicht verloren werden können. Die benannte Speicherbank B im B-, Ay-, Az-Koordinatensystem ist eine Funktion von X,Y und Z im X-, Y-, Z-Koordinatensystem und besitzt eine funktionale Beziehung der Form:
B = f&sub1;(X,f&sub2;(Y,Z)),
wobei fi und f&sub2; Funktionen sind, welche logische Linearpermutationsnetzwerke umfassen, z. B. ein Auswechsel-Linearpermutationsnetzwerk Ep. Zur optimalen Flexibilität umfaßt f&sub2; ein Auswechsel-LPN, Ep und ein Umkehr- LPN, Rp. Speziell ist B in der bevorzugten Ausführung die folgende Funktion von X, Y und Z:
B = Ep (X,Ep(Ys,Zr)),
wobei
Zr = Rp(Z)
und
Ys = Sp(sm,Rp(Y)),
wobei Sp das Schieberdraht-LPN, Rp das Umkehrdraht-LPN ist und wobei sm zur ausgewählten Permutationsbitmappe oder PBM in Beziehung ist, welche als die gesetzte statische Adressierungsmode oder statische Mode bezeichnet wird und anschließend beschrieben und definiert wird.
Die Speicherbankzellenadreßstelle Yy im B-, Ay-, Az-Koordinatensystem kann generell eine Funktion von Y im X-, Y-, Z-Koordinatensystem sein, welche eine funktionale Abhängigkeit der Form besitzt:
Ay = f&sub3;(Y)
wobei f&sub3; ein Drahtlinearpermutationsnetzwerk umfaßt, z. B. ein Umkehr- LPN, Rp. Speziell in der bevorzugten Ausführungsform ist Ay eine Funktion von Y der Form:
Ay = Ys.
Die Rahmenpufferbitebenenadressen Az können eine Funktion von Z im X-, Y-, Z-Koordinatensystem sein, die eine funktionale Beziehung der Form haben:
Az = Zr
Diese funktionalen Beziehungen logischer Linearpermutationen von X,Y,Z nach B,Ay,Az oder von dem Bildpixelraum zu dem PBM sind in den Rahmenpufferadreßschaltkreisen AGEN und in den "Postnet"- oder Nachpermutationsschaltkreisen der DGEN ausgeführt. Umgekehrt werden die umgekehrten funktionalen Beziehungen, welche von dem PBM B-, Ay-, Az-Koordinatenraum in den X-, Y,- Z-Koordinatenraum permutieren und normalisieren, in dem "Prenet"- oder Vorpermutationsschaltkreis der DGEN wie folgt ausgeführt:
X = Ep(B,Ep(Ay,Az))
Ys = Ay
Zr = Az
Die linearen Permutationstransformationen von der Benutzer-X-, Y-, -Z-Koordinatensystem-Bitmappe in die Rahmenpufferspeicheradressen-B-, Ay-, Az-Koordinatensystem-permutierte Bitmappe können wie oben beschrieben in zwei Schritten linearer Transformationen erreicht werden. Eine erste lineare Permutationsnetzwerkfunktion transformiert und permutiert die Graphikbilddatenadressen des Benutzer-X-, -Y-, -Z-Koordinatensystems in Adressen eines abstraken C-, U-, S-Koordinatensystems von dreidimensionalen Mehrfachebenen-Blocksektionen S, Zelluntereinheiten C der Blocksektionen, welche den Adressierungsmodenzellen entsprechen, und Graphikbilddateneinheiten U, wobei jede Zelle eine gleiche Anzahl von Dateneinheiten umfaßt. Das C-, U-, S-Koordinatensystem bildet eine erste lineare Permutationsbitmappe oder erste permutierte Bitmappe. Die funktionale Beziehung des ersten Linearpermutationsnetzwerks hat die Form:
C,U,S = f(X,Y,Z),
wobei f das Schalter-Linearpermutationsnetzwerk Qp einschließt. Speziell werden die Zelladressen C, Einheitadressen U oder die Adressen S der dritten Dimension der Blocksektion durch die folgende Funktion der Schalter- oder multiplexten LPN Qp angegeben:
C = Qp(X,h,Ys)
U = Qp(Qp(Zr,L-p,Ys),h,X)
S = Qp(Ys,L-p,Zr),
wobei h und p die Adreßmodenauswahlparameter sind, wobei h der Logarithmus zur Basis 2 der horizontalen Dimension H des ausgewählten Wortes oder Zelladressierungsmodus in Einheiten von 4 Bits, quadratischen Bits oder Quadraten ist, p der Logarithmus ist zur Basis 2 der ausgewählten Anzahl von Ebenen, v der Logarithmus ist zur Basis 2 der vertikalen Dimension V der ausgewählten Wörter oder Zelladressierungsmoden in Einheiten von Bits und L = h + v + p für die ausgewählten Adressierungsmoden. L ist der Logarithmus zur Basis 2 oder Log&sub2; der Anzahl logischer Speicherbänke und auch die Anzahl von Einheiten U in der Zelle C.
Ein zweites Linearpermutationsnetzwerk transformiert und permutiert die Graphikdatenadressen des abstrakten C-, U-, S-Koordinatensystems in Speicherbankadressen des B-, Ay-, Az-Koordinatensystems der genannten Speicherbänke B, Speicherbankadreßstellen Ay und die Speicherbankbitebenenadressen der dritten Dimension Az der Rahmenpufferspeicher. Die funktionale Beziehung zwischen der zweiten Transformation und der linearen Permutation hat die Form:
B,Ay,Az = g(C,U,S),
wobei g auch die logischen LPNs für die abschließende Transformation in B und die Schalter-Linearpermutationsnetzwerke Qp für die abschließende Transformation in Ay und Az einschließt. Jede der ersten und zweiten Linearpermutationsnetzwerktransformationen des zweischrittigen Prozesses schließen weiterhin LPNs ein. Speziell wird die Speicherbanknennung B und die Bankzelladreßstellen Ay und Az durch die folgenden Linearpermutationsoperationen gegeben, wobei B im wesentlichen die gleiche funktionale Permutation von C,U,S und von X,Y,Z ist:
B = Ep(U,Ep(C,S))
und Ay und Az Funktionen der Schalter oder Multiplex LPN, Qp sind:
Ay = Qp(Qp(S,L-p,U)h,C)
Az = Qp(U,L-p,S)
Der Datengenerationsschaltkreis ist beim Betrieb an den Rahmenpufferadreßschaltkreis und den Rahmenpufferspeicher zur Aktualisierung des Rahmenpuffers mit Vektorzeichnung, Polygonauffüllung und Rasteroperationen und zur Auffrischung und der Wiedergabe der Rasterwiedergabe oder der Sichtoberfläche mit Graphikbilddateninhalten des Rahmenpufferspeichers gekoppelt. Aufgrund der permutierten Bitmappe, welche durch den Adreßgenerator und die Adreßschaltkreise der Erfindung in den Rahmenpufferspeicherbankadreßstellen festgelegt werden, ist der Datengenerationsschaltkreis mit einem ersten Prenet- oder Vorpermutationslinearpermutationsnetzwerk ausgerüstet. Das Vorpermutations-LPN stellt ausgewählte Transformationen und lineare Permutationen von Graphikbilddaten, auf die vom Rahmenpufferspeicher im permutierten B-, Ay-, Az-Koordinatensystem oder dem PBM-Raum zugegriffen wurde, in das Benutzer-X-, -Y-, -Z-Koordinatensystem oder den Standardraum dar, wodurch Graphikbilddaten, auf die vom Rahmenpuffer zur Durchführung von Rasteroperationen zugegriffen wurde, normalisiert werden. Ein zweites Postnet- oder Nachpermutatierungslinear-Permutationsnetzwerk wird ebenfalls mit dem Datengeneratorschaltkreis bereitgestellt. Die Nachpermutations-LPN vollführt Transformation und Linearpermutation von bearbeiteten Graphikbilddaten, welche im normalisierten Benutzer-X-, -Y-Koordinatensystem oder dem Standardraum verbleiben, in das permutierte B-, Ay-, Az-Koordinatensystem oder den PBM-Raum der Rahmenpufferspeicherbankadreßstellen, um sie in die Rahmenpufferspeicherpermutationsbitmappe zurückzuführen.
Die Vorpermutations- oder Prenet- und Postpermuations- oder Postnet-LPNs sind im wesentlichen die gleichen wie die logischen Permutationsnetzwerke, welche im Adreßgenerator und der verbundenen Adreßschaltung verwendet werden. Die logischen LPNs sind selbstsymmetrisch und umkehrbar und beinhalten reversible Boole'sche logische Tore, wie XOR- oder XNOR-Tore. Diese Tore sind montiert, um z. B. die Auswechsel-Linearpermutationsnetzwerke Ep und Umkehrauswechselnetzwerke Ep,Rp zu bilden, wie anschließend beschrieben, um sie in den Adreßgeneratoren und den verbundenen Adreßschaltungen und Datengeneratorschaltungen zu verwenden. Die selbstsymmetrischen Eigenschaften und die umkehrbaren Betriebscharakteristiken der logischen LPNs erlauben umkehrbare Transformation und Permutation in beiden Richtungen zwischen dem normalisierten Benutzer-X, -Y-, -Z-Koordinatenraum und Standardbitmappe und dem ungewöhnlichen permutierten B-, Ay-, Az-Koordinatenraum und permutierter Bitmappe. Im wesentlichen werden dieselben logischen Linearpermutationsnetzwerke sowohl in die AGEN und verbundene Adreßschaltungen als auch die DGEN eingeschlossen. Während die Adreßschaltkreis-LPNs nur mit den Indizes oder Adressen operieren, operieren die DGEN LPNs selektiv direkt auf die Daten zur Durchführung der Rasteroperatonen, Bit Blts und Polygonauffüllung von aus dem PBM-Raum stammenden Graphikbilddaten der permutierten Bitmappe.
Die Erfindung betrachtet eine neue Methode zur Graphikbilddatengeneration zum Auffrischen von Rahmenpufferspeicherbankadreßstellen A in der Speicherbank B eines Rahmenpufferspeichers in einer Rastergraphikmaschine und insbesondere für Rasteroperationen. Bezüglich einer generellen zweidimensionalen Implementation sind die Schritte der Methode die folgenden: Organisation der Rahmenpufferspeicherbankadreßstellen in eine permutierte oder gewebte Bitmappe durch Empfang von Graphikbilddatenadressen in das Benutzer-X-, -Y-Koordinatensystem und Transformation und Permutation der Adressen des Benutzer-X-, -Y-Koordinatensystems durch lineare Permutationsnetzwerke in ein permutiertes B,A-Koordinatensystem oder den PBM-Raum von ausgewählten Speicherbänken B und Speicherbankadreßstellen A; Wiederherstellung von Graphikbilddaten aus den Rahmenpufferspeicherbankadreßstellen in das permutierte B-, A-Koordinatensystem oder den PBM-Raum zur Durchführung von Rasteroperationen; Vorpermutation und Normalisierung der Anordnung von aus dem permutierten B-, A-Koordinatensystem stammenden Graphikbilddaten in das normalisierte Benutzer-X-, -Y-Koordinatensystem oder den Standardraum durch Vorpermutations-Linearpermutationsnetzwerkmittel zur Anpassung von Quelldaten auf Zieldaten während der Rasteroperation; nachpermutierte Graphikbilddaten verbleiben in dem normalisierten Benutzer-X-, Y-Koordinatensystem nach Durchführung von Rasteroperationen in das permutierte B-, A-Koordinatensystem oder den PBM-Raum durch Nachpermutation-Linearpermutationsnetzwerkmittel; und Umkehrung der Graphikbilddaten in das permutierte B-, A-Koordinatensystem in den Rahmenpufferspeicherbankadreßstellen, dadurch die Rasteroperationen in der permutierten Bitmappe oder dem PBM-Raum abschließend.
Die Erfindung betrachtet auch eine neue Methode zur Vektorzeichnung im PBM-Raum der Permutationsbitmappe und zur Auffrischung einer Rasterwiedergabe unter Verwendung aus der Rahmenpufferpermutationsbitmappe stammender Wiedergabewörter Operationen der AGEN und verbundener Adreßschaltkreise mit dem DGEN einschließlich seiner Pfadsektionen, Vektor- und Maskensektionen und Videosektionen sind voll integriert für Operationen zwischen den SBM- und PBM-Koordinatenräumen oder -systemen.
Die Erfindung faßt ebenfalls ins Auge, die neuen Methoden auf ein Benutzer-X-, -Y-, -Z-Koordinatensystem einer Mehrebenen-Bitmappe auszuweiten und die X-, Y-, Z-Standardbitmappe in drei Dimensionen in eine dreidimensionale Permutationsbitmappe oder PBM logisch zu permutieren, welche durch ein Vielfaches von dreidimensionalen Wort- und Zellkonfigurationsadressierungsmoden adressierbar und erreichbar ist. Datenpfadmanipulationen werden bezüglich der Graphikbilddaten durchgeführt, welche von den Mehrebenen-PBMs stammen, wobei auf diese in einem Adressierungsmodus zugegriffen wird, der nicht nur in der horizontalen und vertikalen Bitdimension variabel ist, sondern auch in seinen Bitebenentiefendimensionen, d. h. variabel in der Anzahl der Ebenen.
Eine Vielzahl alternativer Verfahren und Hardware-Ausführungen wird durch die Erfindung betrachtet, um neue flexible Adressierungsrahmenpufferarchitektur, Bilddatenerzeugung und Generationssysteme und Rahmenpufferadressierung und Kontrollschaltkreise zu verwirklichen. Die Merkmale und Vorteile dieser Ausführungen der Erfindung werden in den folgenden Spezifikationen und begleitenden Zeichnungen und Tabellen fortgeführt.

Kurze Beschreibung der Zeichnungen

Fig. 1 ist ein generelles Blockdiagramm einer Rastergraphikmaschine, die das Bilderzeugungssystem und die Rahmenpuffersteuerung der vorliegenden Erfindung beeinhaltet einschließlich dem Datengenerator oder DGEN, dem Adreßgenerator oder AGEN und weitere Rahmenpufferspeicheradressierungsschaltungen.
Fig. 2 ist eine andere generelle Blockdiagrammkonfiguration der Rastergraphikmaschine, wobei der Rahmenpufferspeicher in mehreren Ebenen organisiert ist.
Fig. 3 ist ein Diagramm von Block- und Zellorganisationen der Rahmenpufferspeicherbankadreßstellen entsprechend einem Beispiel der vorliegenden Erfindung, welches sich auf eine Blockuntereinteilung der Sichtoberfläche mit mehrfachen Adressierungsmoden, Zellen oder Zellkonfigurationen für den Zugriff auf die Rahmenpufferspeicherbankadreßstellen bezieht.
Fig. 4A, 4B und 4C sind Diagramme des Blocks der Rahmenpufferspeicherbankadreßstellen, die den Zugriff auf den Block entsprechend der drei unterschiedlichen Adressierungsmodenzellen oder Zellkonfiguration darstellen.
Fig. 5 zeigt ein Schaltkreisdiagramm zur Ausführung des zyklisch logischen LPN-Operators Cp zur Operation bezüglich Adreß- oder Indexbits im Adreßraum.
Fig. 6 zeigt ein Schaltkreisdiagramm zur Ausführung des gemultiplexten Schalterhybrid-LPN-Operators Qp, während Fig. 6A Einzelheiten des 2-zu-1-Auswahlschalters darstellt.
Fig. 7 zeigt ein Schaltkreisdiagramm zur Ausführung des Auswechsel-logischen-LPN-Operators Ep für die Operation auf Adreß- oder Indexbits im Adreßraum.
Fig. 8 zeigt ein Schaltkreisdiagramm zur Ausführung des umgekehrten Draht-LPN-Operators Rp zur Operation von Adressen oder Indexbits im Adreßraum.
Fig. 9A, 9B und 9C repräsentieren Schaltungsdiagramme zur Ausführung des schiebenden Draht-LPN-Operators Sp, während Fig. 9D ein Schaltkreisdiagramm für die kombinierte Ausführung von Rp und Sp darstellt.
In den Fig. 10 und 10A sind Diagramme dargestellt, die das fundamentale Theorem der linearen Permutationsnetzwerktheorie und der wechselseitigen Herleitung und Transformation in drei Dimensionen zwischen den X-, Y-, Z- C-, U-, S- und B-, Ay-, Az-Koordinatenräumen und den zwei Dimensionen zwischen den X-, Y- C-, U- und B-, A-Koordinatenräumen illustrieren.
Fig. 11 und 12 präsentieren ein generelles Blockdiagramm und ein Flußdiagramm der Adreß- und Datenpfadkomponenten, wobei der Abbildungsfluß der Adreßdaten und Graphikbilddaten zwischen dem Adreßgenerator oder AGEN, den logischen Adreßschaltkreisen, den Rahmenpufferspeicherbänken und dem Datengenerator oder DGEN dargestellt wird.
Fig. 13 zeigt ein Blockdiagramm der Zelladreßgenerationsektion des Adreßgenerators oder AGEN.
Fig. 14 zeigt ein Blockdiagramm und ein Flußdiagramm der Adreßgenerationssektion der aufgefrischten Wortzellen des AGEN.
Fig. 15 zeigt ein Blockdiagramm und ein Flußdiagramm des Datengenerators oder DGEN.
Fig. 16 zeigt ein generalisiertes Blockdiagramm eines logischen Linearpermutationsnetzwerks, welches einen logischen Austausch-Linearpermutationsoperator Ep zur Bearbeitung von Daten im DGEN im Datenraum und zur Bereitstellung der fundamentalen Gleichung für den besten Modus des PBM einschließt.
Fig. 17 zeigt einen detaillierten logischen Schaltkreis eines linearen Permutationsauswechselelementes von Fig. 16 zur Bearbeitung von Datenbits im Datenraum.
Fig. 18 zeigt ein alternatives generelles Blockdiagramm und ein Flußdiagramm der Adreß- und Datenpfadkomponenten unter Darstellung des Abbildungsflusses von Adreßdaten und Graphikbilddaten zwischen dem AGEN und den logischen Adreßschaltkreisen, den Rahmenpufferspeicherbänken und DGEN und den Datenpfadkomponenten.

Kurze Beschreibung und Bezeichnung der Tabellen

Tabelle 1 ist eine Tabelle eines Blocks einer zyklischen Permuationsbitmappe unter Darstellung der Permutation und Zuweisung von Speicherbanken in das permutierte B-, A-Koordinatensystem relativ zu den Sichtoberflächenpixelpositionen im Benutzer X-, Y-Koordinatensytem unter Verwendung eines zyklischen Linearpermutationsnetzwerks oder Rotators, um eine beispielhafte Architektur zu erhalten, welche an mehrfache Adressierungsmoden, Wort-oder Zellkonfigurationen angepaßt ist.
Tabellen 2, 3 und 4 sind Tabellen, die das zyklisch-logische Linearpermutationsnetzwerk Cp, das multiplexende Schalterhybridlinearpermutationsnetzwerk Qp und das logische Austausch-Linearpermutationsnetzwerk Ep definieren, welche respektive benutzt werden, lineare Permutationsoperationen durchführen, um beispielsweise die zyklischen Permutationsbitmappen und die zyklischen PBM- Ausführungen der vorliegenden Erfindung darzulegen.
Tabellen 5 bis 8 sind Tabellen von Blöcken von Umkehr-, Auswechsel- oder Auswechsel- und Umkehrpermutationsbitmappen im Rahmen der Erfindung, welche die entsprechenden Zellkonfigurationsadressierungsmoden und entsprechende Aufteilungen von Austausch- und Umkehrpermutationsbitmappenblöcken darstellen.
Tabelle 9 ist eine Tabelle, welche den Umkehrdraht-LPN, Rp definiert, welcher beispielsweise in Kombination mit dem logischen Auswechsel-LPN Ep verwendet wird, die die Umkehr-, Auswechsel- oder Auswechsel- und Umkehrpermutationsbitmappe der vorliegenden Erfindung festlegt.
Tabelle 10 ist eine Zusammenfassung der multizellularen Adressierungsmoden der entsprechenden statischen Moden für eine optimale Doppelauswechselungs- und Verschiebe- und Umkehrpermutationsbitmappe, ausgeführt mittels kombinatorischen Linearpermutationsoperationen von Adreßbits oder Indexbits bei wenigstens zwei logischen Auswechsel-LPNs Ep und zwei Draht-LPNs, dem Schiebe-LPN Sp und dem Umkehr LPN Rp Tabellen 11 bis 25 sind Tabellen von Blöcken von dreidimensionalen Doppelauswechselschiebe- und Umkehrpermutationsbitmappen im Rahmen der Erfindung, partitioniert, um ausgewählte der mehrfachen dreidimensionalen Zellkonfigurationsadressierungsmoden für ausgewählte statische Moden zu zeigen. Die Tabellen 11 bis 15 sind jeweils einzeln partitionierte Blöcke, welche unterschiedlich ausgewählte Zellkonfigurationsadressierungsmoden AM in einer Ebene für die statische Mode sm = 0 darstellen. Die Tabellen 16 bis 19 sind jeweils partitionierte Blöcke, welche ausgewählte unterschiedliche dreidimensionale Zellkonfigurationsadressierungsmoden AM in zwei Ebenen für die statische Mode sm = 1 zeigen. Die Tabellen 20 bis 24 sind jeweils mehrfach partitionierte Blöcke, welche ausgewählte unterschiedliche dreidimensionale Zellkonfigurationsadressierungsmoden AM in vier Ebenen für die statische Mode sm = 2 darstellen. Die Tabelle 25 präsentiert mehrfach partitionierte Blöcke, welche eine ausgewählte dreidimensionale Zellkonfigurationsadressierungsmode AM in acht Ebenen für die statische Mode sm = 3 darstellt.
Tabelle 26 ist eine Tabelle der fundamentalen Gleichungen, welche die Rahmenpufferarchitektur, Adresierungsschaltkreise, Datengenerationsschaltkreise und Linearpermutationsnetzwerke für die Transformation zwischen dem Benutzer-X-, -Y-, -X-Koordinatensystem, der abstrakten Zelle, Einheit und Blocksektion C,U,S, dem Koordinatensystem und den Speicherbankadressen B-, Ay-, Az-Koordinatensystem definiert; und Tabelle 26A ist eine Tabelle der fundamentalen Gleichung, welche alternative Symbole benutzt.
Tabelle 27 ist eine Tabelle, welche den Schiebedraht-LNP, Sp definiert, der in Kombination mit dem logischen Austausch-LPN Ep benutzt wird, und das Umkehrdraht-LPN Rp zur Bereitstellung der dreidimensionalen Doppelauswechslungsschiebe- und Umkehrpermutationsbitmappe der vorliegenden Erfindung.
Tabelle 28 ist eine Tabelle der Rahmenpufferspeicherbank der Adreßgleichungen und Adreßverbindungen in der dreidimensionalen universellen Ausführung der Erfindung.
Tabelle 29 ist eine Tabelle der gültigen dynamischen Zellularadressierungsmoden AM für jede der unterschiedlichen mehrfachen Ebenen der statischen Adressierungsmode sm.
Tabelle 30 ist eine Tabelle der funktionalen Permutation und der Korrelation zwischen den C-, U-, S-Adressen oder Indexbits und den X-, Y-, Z-Indexbits für die unterschiedlichen dynamischen Adressierungsmoden AM in der statischen Mode sm = 0.
Tabelle 31 ist eine Tabelle der entsprechenden externen Adreßliniengleichungen der Rahmenpufferspeicherbankadreßstellen für unterschiedliche Adressierungsmodenzellkonfigurationen in der statischen Mode sm = 0.
Tabelle 32 ist eine Tabelle der funktionalen Permutation und Korrelation zwischen C-, U-, S-Adressen oder Indexbits und X-, Y-, und Z-Indexbits für die unterschiedlichen Adressierungsmoden AM in der statischen Mode sm = 1.
Tabelle 33 ist eine Tabelle der entsprechenden externen Adreßliniengleichungen der Speicherbankadreßstellen für unterschiedliche Adressierungsmoden-Zellkonfigurationen in der statischen Mode sm = 1.
Tabelle 34 ist eine Tabelle der funktionalen Permutation und Korrelation zwischen den C-, U-, S-Adressen oder Indexbits und X-, Y-, Z-Indexbits für unterschiedliche Adressierungsmoden Am in der statischen Mode sm = 2.
Tabelle 35 ist eine Tabelle der entsprechenden externen Adreßliniengleichungen für die Speicherbankadreßstellen für unterschiedliche Adressierungsmode-Zellkonfigurationen in der statischen Mode sm = 2.
Tabelle 36 ist eine Tabelle der funktionalen Permutation und Korrelation zwischen den C-, U-, S-Adreßbits oder Indexbits und X-, Y-, Z-Indexbits für die unterschiedlichen dynamischen Adressierungsmoden AM in der statischen Mode sm = 3.
Tabelle 37 ist eine Tabelle der entsprechenden externen Adreßliniengleichungen für die Speicherbankadreßstellen für die unterschiedlichen Adressierungsmode-Zellkonfigurationen in der statischen Mode sm = 3.
Tabelle 38 ist eine Tabelle der funktionalen Permutation und Korrelation zwischen C-, U-, S-Adressen oder Indexbits und X-, Y-, Z-Indexbits für die unterschiedlichen dynamischen Adressierungsmoden AM in der statischen Mode sm = 4.
Tabelle 39 ist eine Tabelle der entsprechenden externen Adreßliniengleichungen für die Speicherbankadreßstellen für die unterschiedlichen Adressierungsmode-Zellkonfigurationen für die statische Mode sm = 4.
Tabelle 40 ist eine Tabelle von Zelladreßgleichungen in Boole'schem Format zur Formulierung der Zelladreßlinienschaltkreise und -verbindungen entsprechend der Zelladreßlinien CA von Fig. 24.

Beschreibung der bevorzugten Beispielausführung und der besten Mode der Erfindung

Ein generelles Systemblockdiagramm eines Rastergraphiksystems 10, welches die Graphikarchitektur der vorliegenden Erfindung ausführt, ist in Fig. 1 dargestellt. Der Rahmenpufferspeicher 12 wird durch ein Feld von physikalischen Speicherbanken oder Komponenten bereitgestellt, beispielsweise wenigstens acht physikalische Speicherbanken mit einer Bitbreite von beispielsweise 4 Bits, um die neue Permutationsbitmappe zu unterstützen.
Im nachfolgenden beschriebenen detaillierten Beispiel wird der Rahmenpufferspeicher durch acht physikalische Speicherbanken "zeitgeschnitten" zweimal in jedem Speicherzugriffszyklus bereitgestellt. Die beiden "Züge" von jeder physikalischen Speicherbank in jedem Speicherzyklus stellen so 16 effektive oder logische Speicherbanken dar. Die 16 logischen Speicherbänke beinhalten 16 Permutations-"Objekte" für die neuen logischen Permutationsoperatoren oder Netzwerke, welche in die Adressierung und Datenpfadschaltkreise inkorporiert sind.
Im Rahmen des Beispiels ist jede Speicherbank zusammengesetzt aus vier integrierten Schaltkreisen AM-Chips, welche Speicherbanken von vier Bit Breite mit vier Eingabe/Ausgabe-Leitungen mit derselben Adressen bereitstellt. Während eines Speicherzugriffszyklus werden Graphikbilddateneinheiten U von vier Bits, die als Quadrate oder Quadratbits oder Quadratpixel bezeichnet werden, von der Speicherbank gezogen. In Zeitschnitten werden zwei Quadrate von jedem der acht physikalischen Speicherbanken oder ein Quadrat von jedem der 16 effektiven oder logischen Speicherbanken in jedem Speicherzugriffszyklus abgezogen. Das Speicheradressierungswort oder die Zelle ist deshalb zusammengesetzt aus 16 Quadraten oder 64 Bits. Die Datenpfadsystemkomponenten sind so gestaltet, um die 64 Bitworte beispielsweise durch gemultiplexte 32 Bit Datenpfade anzupassen. Daher besteht jedes 64 Bit Wort aus zwei verzahnten 32 Bit Wörtern oder "Zügen".
Falls der Rahmenpuffer aus dynamischen RAMs oder DRAMs zusammengesetzt ist, ist eine dynamische RAM-Steuerung oder DRAMC 14 erforderlich, um die DRAM-Zellen aufzufrischen. Alternativ kann die Adreßgeneratorablaufverfolgung diese Funktion durchführen.
Der Adreßgenerator oder AGEN 15 führt Graphikinstruktionen aus, die er über die ICODE-Leitung vom programmierbaren Graphikprozessor oder PGP 16 erhalten hat, der alternativ auch eine Wirt- oder System-CPU sein kann, und bestätigt die Instruktionsanfragen über die BUSCODE-Leitung. Der AGEN 15 generiert geeignete Adressen für den Rahmenpuffer als Antwort auf Instruktionsanfragen auf den Adreßleitungen oder AD-Leitungen und dem Adreßbus- oder ADBUS 18, der beispielsweise ein 32 Bit langer bidirektionaler Bus ist für die Adressierung des Rahmenpuffers 12 durch zusätzliche Adressierung von Logikschaltkreisen 20. Die adressierten Logikschaltkreise 20 beinhalten einen Adreßpuffer- Latch und logische Tore, um die vier bestimmten Bankadreßleitungen zu den 16 logischen Speicherbänken (acht physikalische Speicherbänke, Zeit zweifach geschnitten) anzusteuern. Der AGEN 15 und verbundene Adreßlogik 20 bilden zusammen und führen die Permutationsbitmappe aus, wie nachfolgend beschrieben wird. Der AGEN 15 übergibt auch Instruktionsequenzen in Form von Datenoperationscodes oder DOP-Codes auf die DOP-Leitung zum Datengenerator oder DGEN 22.
Der Datengenerator 22 ist eine Datenpfadkomponente, vergleichbar mit einem Bitblocktransferchip zum Empfang von Instruktionssequenzen vom AGEN 15 und führt Graphikoperationen bezüglich Graphikbilddaten aus, auf die im Rahmenpuffer zugegriffen wurde entsprechend der Adreßsequenzen, welche durch den Adreßgenerator generiert wurden. Die Graphikoperationen, die vom DGEN 22 in Kombination mit dem AGEN durchgeführt werden, schließen Vektorzeichnung oder Vektoradressierung von relativen oder absoluten Positionen, Raster-ops oder Bitblocktransfers, bekannt als Bit Blts, Polygonauffüllung, Zeichenzeichnung, Streifensequenzierung, etc. ein und frischen die Rasterwiedergabe auf. Die 64 Bit Graphikdatenworte oder Zellen werden von und zu dem Rahmenpuffer 12 in gemultiplexten 32 Bitworten auf den Datenleitungen oder D-Leitungen und Datenbus 24 transferiert, beispielsweise wird ein 32 Bit bidirektionaler Bus auch als DBUS oder MBUS 24 bezeichnet, der unter der Adressierungskontrolle des AGEN 15 steht.
Die durch den Adreßgeperator eingesetzten graphischen Bilddaten stehen in den Speicherbanken des Rahmenpuffers in permutierter Ordnung. Diese Permutationsbitmappe beinhaltet Mehrfach-Wort- und Zelladressierungsmoden. Der DGEN 22 ist konstruiert und angeordnet, um Graphikdatenoperationen auszuführen und Datenpfadmanipulationen der Graphikbilddaten durchzuführen, die in der ungewöhnlich permutierten Ordnung von der Permutationsbitmappe empfangen werden, die durch den AGEN erzeugt wurde. Der DGEN ist ausgestattet mit logischen Linearpermutationsoperatoren zur Normalisierung von Daten und zur Zurücksendung von Daten zur ungewöhnlich permutierten Ordnung nach Komplettierung von Datenpfadmanipulationen zur Rückgabe an die Rahmenpufferpermutationsbitmappe. Während die logischen Linearpermutationsoperatorschaltkreise oder -netzwerke des AGEN die Indizes oder Adressen der Graphikbilddaten bearbeiten, bearbeiten die entsprechenden logischen LPN-Schaltkreise des DGEN direkt die Datenobjekte. Die DGEN-Netzwerke und -schaltkeise sind in der Lage, die Graphikbilddatenorganisation zwischen dem Benutzer X-, Y- oder X-, Y-, Z-Koordinatensystem zu transformieren entsprechend einer Standardbitmappe oder einem SBM-Raum, und die Speicherbank und die Bankadresse koordinieren entsprechenden Raum für die Permutationsbitmappe, koordinieren System- oder PBM-Raum bezüglich der Anforderungen der bestimmten Datengraphikoperation oder Datenpfadmanipulation. Die Datenpfadmanipulationen schließen Maskierung, Justage und logische Operationen ein, welche beispielsweise für die Vektorzeichnung erforderlich sind, Bit Blts und Polygonauffüllungen werden geeignet arrangiert entsprechend dem SBM- oder PBM-Koordinatenraum der Datenworte.
Der DGEN 22 bereitet Wiedergabeworte vor zur Auffrischung der Bildschirmwiedergabe 25 über Video-Ausgangsleitungen oder VID-Leitungen. Der DGEN 22 schließt eine FIFO-Schnittstelle für die Zusammensetzung von Display-Worten ein und führt den ersten Schritt der Video-Signalverschiebung aus. Video-Verschieberegister 26 werden eingeschlossen, falls eine höhere Bandbreite erforderlich ist, beispielsweise Bandbreiten größer als 40 MHz. Der erste Schritt der Video-Signalverschiebung, welcher im Datengenerator 22 durchgeführt wird, dient zur Anpassung und Justage der permutierten Ordnung von Wiedergabeadressierungsmoduswörtern, welche von der Rahmenpufferpermutationsbitmappe empfangen wurden, für den Aufbau normalisierter Sequenzen, um die Video-Abtastlinien zu kontrollieren. Die verschobenen Video-Daten können direkt in Verbindung mit einer Farbsuchtabelle (LUT) und Digitalnach-Analogkonvertern (DAC) verwendet werden, um die Bildschirmwiedergabe 25 aufzufrischen. Der Video-Synchronisationsgenerator 28 kontrolliert die zeitliche Abfolge der Wiedergabe und die Anfrage nach Auffrischzyklen vom AGEN 15.
Der AGEN 15 und DGEN 22 und entsprechende ADBUS 18 und MBUS 24 sind durch einen Bussendeempfänger 30 aufgeteilt. Der Bussendeempfänger 30 erlaubt fortlaufende Adressierung der Rahmenpufferspeicherbanken bei simultanem Datentransfer zwischen DGEN und den Rahmenpufferspeicherbanken. Der Bussendeempfänger 30 erlaubt ebenfalls fortlaufendes Laden der nächsten Instruktionsdaten während der Ausführung der monentanen Instruktion. Diese aufgeteilte Anordnung zur fortlaufenden Adressierung und dem Datentransfer wird als "Harvard"-Architektur bezeichnet. Ein zweiter Bussendeempfänger 32 stellt fortlaufende Isolation des AGEN 15 und des PGP-Bus 34 bereit. Die Bussendeempfänger 30 und 32 resultieren in einem dreistufigen hierarchischen Datenfließband, welches konstante Informationsbandbreite, aber wachsende Bitbandbreite besitzt mit einem programmierbaren graphischen Prozessor, der die erste Stufe bildet. Der PGB 16 bricht geometrische Objekte der Datenbasis einer System-CPU in hochrangige geometrische Grundelemente auf und führt die notwendigen Transformationen zur Konvertierung und Generation von Positionsinformationen im Benutzer-X-, -Y- oder X-, -Y-, -Z-Koordinatensystem durch. Der AGEN 15 oder DGEN 22 bildet die zweite Stufe, welche die Positionsdaten in einen Bitstrom von Pixeln für zur Rahmenpufferspeicherung konvertiert, während die Auffrischungswiedergabe die dritte Stufe bildet. Es ist die zweite Stufe der Konvertierung der Positionsdaten in einem Bitstrom von Pixeldaten, in der der AGEN und DGEN die Ordnung so permutieren, daß nur zwei- und dreidimensionale PBMs im Rahmenpuffer gebildet werden.
Andere Komponenten des generellen Systems beinhalten eine Systemuhr, die beispielsweise Zeitsignale mit 40 MHz auf den ICLK-Leitungen liefert, um die AGEN 15 und DGEN 22 Instruktionsausführungssequenz anzutreiben und andere System-Zeitplanungserfordernisse bereitzustellen. Ein Pixelprozessor 36 kann hinzugefügt werden, um einen Okklusionsalgorithmus und Farbschattierung auszuführen.
Ein weiteres Blockdiagramm des Rastergraphiksystems, welches eine Ausführung mit mehreren Ebenen der vorliegenden Erfindung zeigt, ist in Fig. 2 illustriert. Komponenten ähnlich denen des Blockdiagramms in Fig. 1 sind mit der gleichen Bezugsziffer bezeichnet. Dieses vollständigere Blockdiagramm stellt klarer die hierarchische Fließbandorganisation dar, die durch die vorliegende Erfindung betrachtet wird. In diesem Beispiel ist die Wirts- oder System-CPU über einen CPU-Bus 38 mit einer Datenbasis verbunden, die eine Hierarchie abstrakter Symbole beinhaltet, die in hochrangige aufgelöste geometrische Objekte während des Datenbasisdurchgangs besteht. Die hochrangigen geometrischen Objekte werden durch den programmierbaren Graphikprozessor PGB 16 aufgelöst in hochrangige geometrische Grundbestandteile, wie im Vorgehenden beschrieben, durch lokalen Speicher 40 und optimale Benutzer-Schnittstellenperipherie 42 vergrößert. Der PGP 16 ist von CPU-Bus 38 durch einen Bussendeempfänger 44 isoliert. Die weiteren Stufen des hierarchischen Datenfließbandes sehen aus wie oben beschrieben.
Im Systembeispiel der Fig. 2 sind die Rahmenpufferspeicherbanken 12 eingeteilt und organisiert in N Ebenen 50, 51 . . . 50N. Im Blockdiagramm der Fig. 2 wird beispielsweise betrachtet, daß der Satz von Speicherbanken 12 und der Datengenerator oder DGEN 22 für jede Ebene des Rahmenpufferspeichers dupliziert wird. Die Ebenen des Rahmenpufferspeichers repräsentieren die Anzahl von Bits, welche jedes Pixel definieren, und bilden eine dritte Tiefendimension oder Z-Koordinate des Benutzer/Betrachter-Koordinatensystems. Derselbe Satz von Speicherbanken umfaßt alternativ den Rahmenpufferspeicher, der in N multiple Ebenen eingeteilt und organisiert sein kann, wobei jede Ebene alle acht physikalischen Speicherbanken oder 16 logischen Speicherbanken überschneidet. In dieser Instanz und im detaillierten Beispiel, welches anschließend beschrieben wird, kann ein einzelner Datengenerator oder eine DGEN-Komponente die Datenpfadmanipulation für alle Ebenen ausführen. Die Speichersteuerung 46 führt die notwendige dynamische Speicherauffrischung durch und kann zusätzliche adressierende Logiktore oder Schaltkreise 20 beinhalten, welche in Verbindung mit Operationen des Adreßgenerators oder AGEN 15 stehen. Der Adreßgenerator kann durch einen Pixelprozessor 36 ergänzt werden. Die AGEN 15 und DGEN 22 sind in der Lage, einen 320 MHz Monitor 25 zu steuern bei einer Auflösung von beispielsweise bis zu 2048·2048 Pixeln.
Im Rahmen des Systemblockdiagramms von Fig. 1 und 2 des Rastergraphiksystems der vorliegenden Erfindung ähnelt dieses zur Zeit verfügbaren Rastergraphikmaschinen und Work-Station-Graphikarchitekturen. Der subtile Unterschied der vorliegenden Erfindung liegt innerhalb des Adreßgenerators oder AGEN 15 und steht im Zusammenhang mit Adreßlogikschaltungen und dem Datengenerator oder Datenpfadkomponenten-DGEN 22. Während der AGEN 15 innerhalb des Systemblockdiagrammniveaus wie ein konventioneller Adreßgenerator erscheint, beinhaltet er entweder intern im AGEN oder sowohl intern im AGEN und extern in verbundenen Adreßlogikschaltungen 20 logische Permutationsnetzwerke, Operatoren oder Schaltkreise, welche anschließend beschrieben werden, und die Graphikbilddatenadressen permutieren, um in den Mehrfachbank-Rahmenpufferspeichern neue Permutationsbitmappen festzulegen, auf die zugegriffen werden kann und in denen eine Vielzahl unterschiedlicher Wort- und Zellkonfigurationsadreßmoden untergebracht sind. Dies gilt in ähnlicher Weise für den DGEN, der in seiner Kapazität einem konventionellen Datenpfad-Chip oder Bit Blt ähnelt, da er ebenfalls logische Linearpermutationsnetze, Operatoren oder Schaltkreise beinhaltet, um Graphikbilddaten zu bearbeiten und zu manipulieren, die aus der Rahmenpufferpermutationsbitmappe in ungewöhnlicher permutierter Ordnung aufgefunden worden sind. Nach der vorliegenden Erfindung stellt der DGEN eine Vielzahl von Strategien zur Behandlung von Daten, welche in ungewöhnlicher permutierter Ordnung empfangen wurden, bereit und führt die notwendigen Graphikoperationen, wie z. B. Vektorzeichnung, Polygonauffüllung, 64 Bit horizonataler Wortblocktransfer und Bildauffrischung und -wiedergabe durch.
Die multizellulare Adressierungsfähigkeit, die den Permutationsbitmappen oder PBMs der vorliegenden Erfindung anhaftet, kontrastiert mit den konventionellen Standardbitmappen oder SBMs, welche eng verbunden sind mit dem Benutzer/Betrachter-X- -Y- oder -X-, -Y-, -Z-Koordinatensystem. Konventionelle SBMs haben die Fähigkeit, daß sie nur in einem Adressierungsmodus adressiert oder auf sie zugegriffen werden kann, entweder durch ein eindimensionales Wort oder zweidimensionale Zellen. Die multizellulare Adressierungsfähigkeit der vorliegenden Erfindung ist in den Diagrammen der Fig. 3 und 4 illustriert, welche einen Block oder Unterteilungen der Rasterwiedergabesichtoberfläche darstellen, welche zusätzlich der neuen Blockorganisation der Permutationsbitmappe des Rahmenpuffers entspricht. Das Blockorganisationskonzept ist fundamental im Hinblick auf die vorliegende Erfindung, die Konsequenz der Koexistenz und den Fortlauf mehrerer Zellenadressierungsmoden. Der Block oder die Blocksektion ist die kleinste rechteckige Unterteilung der Rasterwiedergabesichtoberfläche, in der alle unterschiedlichen Adressierungsmodenzellen und -wörter Unterabschnitte mit gleichen Grenzen bilden. Eine gleiche Anzahl von Zellen oder Wörtern von jedem unterschiedlichen Adressierungsmodus füllen den Block ohne überlapp aus.
Nach Fig. 3 wird ein neuer Block 16 gemäß der vorliegenden Erfindung gezeigt, der verstanden werden kann als die Repräsentation einer rechteckigen Unterteilung oder eines Teils einer Rasterwiedergabesichtoberfläche, beispielsweise einem Bildröhrenschirm in Benutzer/Betrachter-zweidimensionalen-X-, Y-Koordinatensystemraum.
Wie anschließend vollständiger beschrieben werden wird im Hinblick auf die Beispiele in Tabelle 1 und den nachfolgenden Tabellen, repräsentiert der Block 16 auch eine abstrakte Unterteilung der Organisation der Speicherbanken und Speicherbankadreßstellen der Rahmenpufferpermutationsbitmappe im PBM-Raum. Ein wichtiges Merkmal der vorliegenden Erfindung und Erfindungsausführung ist, daß das Block-60-Konzept transferierbar ist und überleitet zwischen dem Benutzer-X, -Y-Koordinatensystem und dem permutierten B-, A-Koordinatensystem, welches zwischen dem Standardkoordinatenraum und dem permutierten PBM-Koordinatenraum liegt. Diese übertragbare Blockorganisation entsteht prinzipiell nur, weil Übereinstimmung multipler Adressierungsmoden, Zellen und Wörter besteht und ist absolut neu mit dem Ursprung in der vorliegenden Erfindung.
Im Systembeispiel, welches oben beschrieben wurde, beträgt die Adressierungswort- und -zellgröße 64 Bit, besteht aus 16 Quadraten, Quadratbits oder Quadratpixeln, wobei je eines durch jede der 16 effektiven oder logischen Speicherbanken in jedem Speicherzugriffszyklus beigetragen wird. Im Beispiel der Fig. 3 kann der Block 60 abgefragt oder auf ihn zu gegriffen werden durch jede der drei Adressierungsmodenzellen. Die 64·1 Bit Zelle 61 ist grundsätzlich die horizontale Wortadressierungsmode, welche dazu benutzt wird, auf den Rahmenpufferspeicher zur Auffrischung des Röhrenbildschirms zuzugreifen. Die 64·1 Bit horizontalen Wörter 62 werden gemäß der vorliegenden Erfindung auch für Bit Blts und Polygonauffüllungen verwendet. Die 16·4 Bit Zellen 64 repräsentieren eine zweidimensionale Zelle, die größer ist in ihrer horizontalen Dimension und deshalb gemäß der Erfindung nützlich, auf den Rahmenpufferspeicher zuzugreifen, um den Rahmenpuffer zu aktualisieren, beispielsweise bei der Zeichnung horizontal orientierter Vektoren. Die 4 x 16 Bit Zelle 66 ist ein anderer zweidimensionaler Zelladressierungsmodus, der größer ist in der vertikalen Dimension und deshalb gemäß der vorliegenden Erfindung nützlich ist, auf den Rahmenpuffer zuzugreifen und den Rahmenpuffer durch Zeichnung vertikal orientierter Vektoren zu aktualisieren. Es ist offensichtlich, daß die Dimensionen des Blocks 60 durch die maximalen Dimensionen der restriktiven Adressierungsmodenzellen 62, 64 und 66 festgelegt werden. Die horizontale Dimension des Blocks 60 ist gleich dem Maximum der horizontalen Dimensionen der adressierenden Zelle, nämlich die 64 Bit horizontale Breite des eindimensionalen 64·1 Bit Wiedergabewortes 62. Die vertikale Dimension des Blocks 60 ist das Maximum der vertikalen Dimension der adressierenden Zellen, nämlich 16 Bit vertikaler Höhe einer 4·16 Bit vertikal orientierten Zelle 66. Insgesamt beträgt die Dimension des Blocks 60 daher 64·16 Bit. Eine Wiedergabeoberfläche oder Sichtoberfläche, die auf eine Auflösung von beispielsweise 1024·1024 Pixeln hat, wäre zusammengesetzt aus ca. 1000 oder 1024 Blöcken, 16 Blöcke entlang der horizontalen X-Richtung und 64 Blöcke abwärts in der vertikalen Y-Richtung. Eine Wiedergabeoberfläche oder Sichtoberfläche, die eine Auflösung von 2048·2048 Pixeln hat, wäre zusammengesetzt aus 32 Blöcken entlang der X-Koordinatenrichtung und 128 Blöcken abwärts in der vertikalen Y-Richtung um ca. 4000 oder exakt 4096 Blöcke.
Weiter auf Fig. 3 bezugnehmend, ist jede der horizontalen Wortmoduszellen 62 zusammengesetzt aus 16 horizontal orientierten Quadratpixeln 61, die in einer einzelnen Reihe angeordnet sind. Jedes Quadratpixel oder Quadrat 61 ist dann zusammengesetzt aus vier Bits 63, angeordnet in einer horizontalen Reihe. Im Falle eines Rahmenpuffers aus einer einzelnen Ebene wird jedes Pixel durch ein einzelnes der Bit 63 definiert. Die horizontal orientierte zweidimensionale Adressierungsmodenzelle 64 ist auch zusammengesetzt aus 16 Quadraten 65, in diesem Fall angeordnet in vier Spalten und vier Reihen von Quadraten 65. Jedes Quadrat ist als horizontale Reihe von vier Bits angeordnet. Die vertikal orientierten zweidimensionalen Adressiermodenzellen 66 sind zusammengesetzt aus 16 Quadratpixeln 67, angeordnet in einer einzelnen vertikalen Spalte. Jedes Quadrat ist ebenfalls zusammengesetzt aus vier Bits in einer horizontalen Reihe. Die grundlegende Einheit U der Blockgeometrie im bevorzugten Beispiel ist das horizontal orientierte Quadrat, obwohl die grundlegende Einheit von Daten auch ein Bit oder andere mehrfache Bitkonfigurationen sein kann. Jede der drei dargestellten Adressiermodenzellen ist zusammengesetzt aus 16 Einheiten U oder Quadraten und deshalb aus 64 Bits, und die Geometrie der Zellen ist zum Teil festgelegt durch die 64 Bit Zellengröße und die Dateneinheit U der Quadrate, die als horizontale Einheiten von vier Bits angeordnet sind. Die Dimensionen oder Grenzen der Blöcke 60 sind so festgelegt.
Wie in den Fig. 4A, 4B und 4C gezeigt, ist der Block die kleinste Unterteilung der X-, Y-Koordinatensystemsichtoberfläche, in welcher alle der unterschiedlichen Adressiermodenzellen an den Grenzen mit der gleichen Anzahl von Zellen übereinstimmen. In Fig. 4A füllen 16 der eindimensionalen horizontalen Wortmodenzellen 62 aus und greifen zu auf alle Bits oder Pixel des Blocks 60 ohne überlapp. Die 16 horizontalen Wörter oder Zellen 62 formen tatsächlich eine einzelne Reihe, die den Block auffüllt. In Fig. 4B greifen 16 der horizontal orientierten zweidimensionalen Adressierungsmodenzellen 64 auf alle Bits oder Pixel zu, die den Block 60 auffüllen, wobei vier Reihen und vier Spalten der Zelle ohne überlapp sind. In Fig. 4C greifen 16 der vertikal orientierten zweidimensionalen Adressierungsmodenzellen 66 auf alle Bits oder Pixel des Blocks 60 ohne überlapp zu. Die 16 Zellen 66 formen effektiv eine einzige Reihe, die den Block ausfüllt. In jedem Fall ist die Blockgröße von 64·16 Bit oder 1024 Bit dieselbe, und es existiert keine Redundanz oder Überlapp in der Zellabdeckung des Blocks. Mit anderen Worten, jede Gruppe von Adressierungsmodenzellen bildet eine begrenzende Untergruppe des Blocks.
Die Übertragung des Blockniveaus der Organisation vom Benutzer/Betrachter-X-, -Y-Koordinatensystem oder dem Standardraum in die permutierte Bitmappe, den permutierten PBM-Raum oder das B-, A-Koordinatensystem des Rahmenspeichers der vorliegenden Erfindung wird dargestellt im Beispiel von Tabelle 1, welches einen Block repräsentiert, der den Blöcken von Fig. 3 und 4 entspricht. Die 16 effektiven oder logischen Speicherbänke, bestimmbar durch 16 hexadezimale Ziffern 0 bis F sind die permutierten Objekte, dargestellt in permutierter Ordnung mit Hinblick auf die Pixel X- und Y-Koordinaten des korrespondierenden Blockteils oder der Unterteilung der Benutzerrasterwiedergabesichtoberfläche. Gemäß der Konvention von Tabelle 1 und den folgenden Tabellen der Spezifikation der X-Koordinate steigt die horizontale Koordinate von links nach rechts. Die Y-Koordinate ist die vertikale Koordinate und steigt von oben nach unten. In Tabelle 1 werden die X-Koordinaten in den fundamentalen Dateneinheiten U von Quadraten von 0 bis 16 Quadraten dargestellt, ausgedrückt in hexadezimalen Ziffern 0 bis F, 50 daß die Bitdimension der X-Koordinatenachse tatsächlich 64 Bit, aber 16 Quadrate oder Dateneinheiten beträgt. Dies liegt daran, daß die Quadrate immer horizontal orientiert sind und Einheiten von vier Bits in einer horizontalen Reihe umfassen. Die Y-Koordinate wird ausgedrückt in Einheiten von Bits, wobei die Y-Koordinatendimension sich von 0 bis 16 erstreckt, ausgedrückt in hexadezimalen Ziffern 0 bis F, weil die grundlegenden Dateneinheiten U oder Quadrate eine vertikale Dimension von nur einem Bit besitzen. Daher bleibt die Blockgröße, repräsentiert durch Tabelle 1, 64·16 entsprechend dem Block der Fig. 3 und 4 mit einer Verzerrung oder Kompression der tatsächlichen horizontalen Breite, da die X-Koordinatenposition in Quadrateinheiten angegeben ist.
Innerhalb des Hauptteils der Tabelle 1 werden die Zuweisungen der 16 logischen Speicherbänke zu den Pixelpositionen auf der Sichtoberfläche durch die erste hexadezimale Ziffer in jedem Paar von Ziffern in der permutierten Ordnung einer zyklischen Permutationsbitmappe definiert, wobei eine Beispielausführung der Erfindung repräsentiert ist. Jede der 16 Speicherbanken trägt ein Quadrat oder eine Einheit zu jedem Adressierungsmodenwort oder jeder -zelle bei und eine Gesamtheit von 16 Quadraten oder Einheiten zu dem Block. Jede Speicherbank ist daher ausgestattet mit 16 Bankadressen A, die die Zelladressen C für jeden Block korrelieren. Während die Bankadressenzuweisung A für ein bestimmtes Pixel oder eine Pixelposition invariabel bleibt, wechselt die korrelierte Zelladresse C des Pixels gemäß der ausgewählten Adressierungsmodenzellenkonfiguration, wie anschließend weiter beschrieben wird. Wurden einmal die Blockadressen oder Adressierungszellenmoden festgelegt, brauchen nur die Speicherbank B und Speicherbankadressen A und alle Adressen C für jedes Pixel oder Quadrat oder jede Quadratpixelposition auf der Sichtoberfläche festgelegt zu werden. Die Bankadresse A oder Zelladdresse C ist die zweite hexadezimale Ziffer in jedem Paar von Ziffern, und ein mögliches Beispiel einer zufälligen Zuweisung von Bankzelladressen ist im Hauptteil der Tabelle 1 dargestellt. Bei jedem Speicherzugriffszyklus wird jede Speicherbank B abgefragt oder auf sie zugegriffen an einer Adresse A, und die 16 Speicherbanken und Bankzelladessen B, A erzeugen eine Adressierungsmodenzelle.
In einer Standard-Bitmappe wäre die Abfolge oder Ordnung von Speicherbankzuweisungen über die Reihe dieselbe Sequenz von Spalten von 0 bis F mit der Standard-Bitmappe als einfacher funktionaler arithmetischer Beziehung zum X-, Y-Koordinatensystem und resultierend in substantieller Identität. Wie in Tabelle 1 offensichtlich, erscheinen die Speicherbankzuweisungen der vorliegenden Erfindung in einer permutierten Ordnung. Die Speicherbanken permutieren oder bestimmen die Graphikbilddatenwerte an Pixelpositionen über den Blockeinteilungen der Sichtoberfläche in einer Anordnung, die auf eine komplexe lineare Permutation eines X-, Y-Koordinatensystems hinausläuft. Beispielsweise liefert Speicherbank 9 16 Quadratpixel an den Block, um die Graphikbildpixel zu kontrollieren in einem komplexen Feld über dem Block, der nicht einfach durch eine einführende Studie charakterisiert werden kann. Wie nachfolgend präsentiert, ist diese funktionale Beziehung eine komplexe logische Linearpermutation, die es ermöglicht, die drei unterschiedlichen Adressierungsmodenzellen auf den gesamten Block zugreifen zu lassen ohne Redundanz oder überlapp.
Wie in Tabelle 1 gezeigt, werden drei Beispieladreßmodenzellen ausgeführt, die ungefähr den drei Zellen entsprechen, die im Block von Fig. 3 erscheinen. Die Dimension von Tabelle 1 ist jedoch verzerrt bezüglich der tatsächlichen Dimension eines Blocks der Sichtoberfläche, wie sie in Fig. 3 erscheint, weil die Quadrate, die in Tabelle 1 auftreten, durch hexadezimale Ziffern bezeichnet werden, die tatsächlich eine horizontale Breite oder Dimension von vier Bits haben. Falls Tabelle 1 in der tatsächlichen Skala gemäß der Sichtoberfläche präsentiert würde, wäre sie 4·breiter in ihrer horizontalen Dimension und daher in Übereinstimmung mit dem Block der Fig. 3. Untersucht man beispielsweise die Entfaltung der horizontalen Auffrischungszelle 62 auf der Speicherbank in Tabelle 1 in jeder der 16 horizontalen Wortzellen, die die Tabelle 1 füllen würden, so ist jede der 16 Speicherbanken repräsentiert und trägt mit einem Quadratpixel bei, und es existiert keine Redundanz oder überlapp. In ähnlicher Weise würde die Entfaltung der vertikal orientierten 4·16 Bit Zelle an 16 Stellen entlang der Tabelle 1 in 16 vertikal orientierten zweidimensionalen Zellen resultieren, wobei in jeder die 16 Speicherbanken repräsentiert sind und Quadratpixel oben überlapp und Redundanz beitragen. Abschließend würde die Entfaltung der horizontal orientierten zweidimensionalen Adressierungsmodenzellen 64 entlang den Speicherbankzuweisungen von Tabelle 1 16 Zellen produzieren, wobei in jeder alle der 16 Speicherbanken repräsentiert sind und ein Quadratpixel ohne Redundanz und überlapp beiträgt.
Es ist offensichtlich, daß die Permutationsbitmappe von Tabelle 1, in dieser Weise angeordnet, die Zuweisung von Speicherbanken und Bankzelladreßstellen auf Pixelpositionen auf den Bildschirm besitzt, so daß drei unterschiedliche Adressierungsmodenzellkonfigurationen erreicht werden. Es ist in diesem Sinn, daß die vorliegende Erfindung die Leistung gegenüber Standard-Bitmappenmaschinen stark steigert. In dem System der vorliegenden Erfindung können bis zu 16 Pixel von z. B. einem vertikal orientierten Vektor den in jedem verzahnten Speicherzyklus gezeichnet werden, zugreifend auf eine 16 Quadrat oder 64 Bit Zelle. Die Zelle kann ausgewählt werden, um die Anzahl der aktualisierten Pixel zu optimieren, je nach dem, ob der Vektor horizontal oder vertikal orientiert ist. Für Vektoren mit zufälligem Winkel liefert die Multizellularadreßmodenarchitektur der Fig. 3 und 4 und Tabelle 1 immer noch eine mittlere Leistung von wenigstens sechs aktualisierten Pixeln pro Speicherzugriffszyklus im Gegensatz zur Aktualisierung von einem Pixel pro Speicherzugriffszyklus, der charakteristisch für Standard- Bitmappen-maschinen ist. Die vorliegende Erfindung erhöht daher die Vektorzugriffsgeschwindigkeit um einen Faktor 5 bis 10 gegenüber konventionellen Standard-Bitmappenmaschinen.
Obwohl es eine gewaltige Verbesserung gegenüber Standard-Bitmappen darstellt, ist das zyklische Linearpermutationsnetzwerk PBM, welches in Tabelle 1 dargestellt ist, immer noch eine suboptimale Ausführung der vorliegenden Erfindung. Es wurde vorgestellt, um die minimalen Anforderungen der vorliegenden Erfindung zur Erreichung multizellularer Adressierungsmoden zu illustrieren. Im einzelnen müssen die Rahmenpuffer aus mehreren Speicherbanken mit separaten einzigartigen Adressen zusammengesetzt sein, die Speicherbanken bilden "Permutationsobjekte" von linearen Permutationsnetzwerken, welche wenigstens einen logischen LPN beinhalten. Die Anzahl M von logischen Speicherbanken ist eine Potenz von 2, und in den folgenden Beispielen ist M = 16. Das logische Linearpermutationsnetzwerk oder der Operator, der die zyklische PBM von Tabelle 1 ausführt, ist die Rotation oder das zyklische Linearpermutationsnetzwerk oder der Operator Cp. Die funktionale Definition des LPN-Operators Cp ist in Tabelle 2 wiedergegeben.
Der zyklische Linearpermutationsoperator Cp wird als logischer LPN- oder linearer Permutationsoperator bezeichnet, weil er wenigstens zwei Operanden, Adreßvariablen oder Indexvariablen in zwei Dimensionen bearbeitet und weil er auf selbstsymmetrischen oder reversiblen logischen oder Boole'schen Toren, wie XOR- und XNOR-Toren beruht oder sie einschließt. Mit Hinblick auf diese Anforderungen sind die Eingaben und Ausgaben der logischen Linearpermutationsnetzwerke reversibel, und die Daten können nicht verloren werden. Die Adressierungs- und Datenpfadschaltkreise, die in den AGEN eingeschlossen sind und mit der Adreßlogik und den DGEN verbunden sind, können das Rastergraphiksystem in der Weise ausführen, daß sogleich ein Vor- und Zurückschalten zwischen dem Standard-X-, -Y-Koordinatenraum und dem permutierten B-, A-Koordinatensystem- oder PBM-Raum ohne Verlust von Daten stattfindet. Der zyklische Operator Cp bearbeitet zwei Indexvariablen und modifiziert die Indexbits durch modulare Addition oder Subtraktion. Das Inverse des Cp -Operators ist durch einen anderen Cp LPO gegeben, bei dem einer der Operanden das Negative einer der Indexvariablen ist.
Der zyklische LPN ist als eine Adreßlogikschaltung im Index- oder Adreßraum ausgeführt durch Anordnung von reversiblen oder selbstsymmetrischen logischen XOR- und XNOR-Toren, die in einem Addierer wie in Fig. 5 gezeigt angeordnet sind. Die zyklische Linearpermutation der Operanden ist daher die Summe der Operanden im Hinblick auf einen konstanten Koeffizienten, der gleich der permutierten Anzahl von Adreßindizes oder Objekten ist. Im Rahmen der Logikschaltungen übersetzt der zyklische LPN Cp auf einen Addierer oder "Rotator", der als solcher in den Adreßschaltkreisen des AGEN oder seiner verbundenen Adreßlogik ausgeführt ist. Im Datenraum und den Datenpfaden des DGEN ist, wie nachfolgend beschrieben, der zyklische LPN Cp als Barrell-Schieber oder Datenrotator ausgeführt.
Der bestimmte funktionale Zusammenhang und die lineare Permutation zwischen dem X-, Y-Koordinatensystem und der PBM-Organisation der 16 Speicherbanken B, welche in Tabelle 1 gezeigt sind, ist durch die folgende Normalformgleichung definiert:
B = Cp(X',Y')
Die Normalformkoordinaten X', Y' sind mit den X-, Y-Koordinaten durch folgende Gleichung verbunden:
X' = Qp (X,1,0)
Y' = Qp(Y,1,Ep(X,Y)), wobei Qp das in Tabelle 3 definierte Multiplex- oder Schalthybrid-LPN ist und Ep der in Tabelle 4 definierte Auswechsel-logische-Linearpermutationsoperator. Das Auswechsel-Linearpermutationsnetzwerk oder der Operator Ep ist ein logischer Linearpermutationsoperator, der auf wenigstens zwei Operanden oder Dimensionen wirkt und selbstsymmetrische logische reversible Tore, wie XOR- und XNOR-Logiktore beinhaltet oder verwirklicht.
Das Multiplex- oder Schalt-LPN Qp wird als Hybrid-LPN bezeichnet, weil es derartige Logiktore nicht beinhaltet oder verwirklicht und daher als "Draht" ausgeführt ist, der nur auf den Index oder einen Operanden wirkt. Dennoch ist der Qp LPN ein paarweise logischer LPN. Das Qp LPN ist eine einzigartige LPN-Konstruktion, weil es auf die Indizes zweier oder mehrerer Dimensionen wirkt, wobei mehrere Dimensionen gemultiplext werden und, falls als Paar ausgeführt, effektiv als ein logisches LNP funktioniert. Daher ist der paarweise logische Schaltoperator Qp ein LNP, das zwei oder mehr Indizes bearbeitet und das, falls in Paaren operierend, logische Operationen durchführen kann, wie nachfolgend vollständiger ausgeführt wird. Das Schalt-LPN Qp ist tatsächlich ein zweidimensionaler permutierender Logikoperator, der Bits aus zwei verschiedenen Dimensionen nimmt und Index- und Adreßbits multiplext. Ein Schaltkreis zur Ausführung des Schalt-LPN Qp im Adreß- oder Indexraum ist in Fig. 6 für das Beispiel von Tabelle 3 gezeigt, während Fig. 6A die Details des 2-zu-1-Wahlschalters von Fig. 6 zeigt. Ein Schaltkreis zur Ausführung des Auswechsel-LPN Ep ist in Fig. 7 gezeigt.
Zur Ausdehnung der Permutationsbitmappe von Tabelle 1 von zwei auf drei Dimensionen, beispielsweise unter Einschluß einer Multiebenen- Permutationsbitmappe, sind die logischen LPN-Transformationsgleichungen, welche die Zuweisung der 16 Speicherbanken B zu den Pixel- oder Bitstellen des Benutzer-X-, -Y-, -Z-Koordinatensystems definieren, zwei Anwendungen des zyklischen LPN oder des zyklischen Operators Cp erforderlich. Das heißt, um die Permutationsbitmappen der vorliegenden Erfindung auszuführen, ist eine Transformations-LPN-Funktion erforderlich, welche mindestens eine logische LPN-Funktion, wie den zyklischen Linearpermutationsoperator Cp für die zweidimensionale Permutationsbitmappe, und wenigstens ein logisches LPN für jede Dimension, nach der ersten Bitmappe für Bitmappen höherer Dimension, beeinhaltet. Zur Permutation des dreidimensionalen X-, Y-, Z-Koordinatensystem in ein dreidimensionales PBM sind wenigstens zwei logische LPNs erforderlich.
Um multizellulare Adressierung mit zweidimensionalen Zellkonfigurationen zu erreichen, müssen die Permutationsobjekte, nämlich die 16 logischen Speicherbanken B eine logische Linearpermutationsfunktion von wenigstens zwei Dimensionen, beispielsweise beide Dimensionen im X-, Y-Koordinatensystem, nämlich X und Y, sein. Im Falle eines dreidimensionalen Koordinatensystems mit mehreren Ebenen kann die Speicherbankbenennung auch eine Funktion von wenigstens beiden X- und Z-Koordinaten sein.
Das logische LPN wirkt daher auf die geeigneten Indizes oder Adressen von beiden Koordinatendimensionen. Im vorliegenden Beispiel sind vier dieser Adreßbits, welche auch als Indizes oder Indexbits bezeichnet werden, entlang jeder Koordinate angeordnet. In der Y-Koordinatenrichtung eines Blocks werden die Adreßbitsindizes oder die durch eine logisch LPN-Funktion permutierten Indizes als Y&sub3;, Y&sub2;, Y&sub1; und Y&sub0; oder generell Yi bezeichnet, wobei i = 3, . . . 0 ist. In der X-Koordinatenrichtung des Blocks sind die durch die logische LPN-Funktion permutierten Adreßbits X&sub5;, X&sub4;, X&sub3; und X&sub2; oder generell Xi, wobei i = 5, . . . 2 ist. Die Eignung von vier Index- oder Adreßbits von X und Y basiert auf dem folgenden Adressierungsschema.
Im Hinblick auf die Adressierungsbitanordnung und -richtung werden die folgenden Konventionen beobachtet. Der generellen Handhabung folgend, ist das Bit ganz rechts ein Adressierungswort oder Datenwort, welches horizontal als das am wenigsten signifikante Bit (LSB) ausgedrückt wird, und welches mit der Indexnummer oder Kennzeichnung i = 0 bezeichnet ist. Das Bit ganz links ist ein Wort, welches im am meisten signifikanten Bit (MSB) ausgedrückt wird und mit N-1 für ein N Bit langes Wort bezeichnet ist. Der LSB- und MSB-Konvention folgend, ist es Konvention, daß die X-Werte im X-, Y-Koordinatensystem von links nach rechts zu nehmen, während die Y-Werte des X-, Y-Koordinatensystems des aufgefrischten Bildes von oben nach unten zunehmen. Im Rahmen einer Beispielausführung werden die 64 Bit Zellen oder Wörter im DGEN als verzahnte Sequenz von 32 Bit Wörtern in und aus dem Rahmenpufferspeicher gebildet. Im Rahmen der Konvention zur Identifizierung der Ordnung der Datenstrukturen mit mehreren Teilen und ansteigender Speicheradreßordnung muß das erste übertragene oder empfangene 32 Bit Wort die niedrigere Speicheradreßnummer besitzen. Die 32 Bit Wörter des AGEN sind gleichartig aus 16 Bit Operanden zusammengesetzt und so angeordnet, daß das 16 Bit Wort im kleineren Register in den am wenigsten signifikanten Bits des 32 Bit Worts geschrieben wird. Im Falle der dreidimensionalen Bitmappe mit einer Z-Koordinate für mehrere Ebene wird einer Konvention gefolgt, daß die erste Ebene oder die höchste Ebene durch ein Indexbit 0 identifiziert wird, wobei höhernumerierte Ebenen in der Pixeltiefe abwärts fortschreiten. Zur Auffrischung der Wiedergabe beginnt jede gescante Zeile, auszusammengesetzt aus aufeinanderfolgenden horizontalen Wiedergabewörtern von aufeinanderfolgenden Blöcken, an einer Blockadreßgrenze.
Es kein binäre Adressierung von X, Y zur Basis 2 benutzt werden, um die X-, Y-Position eines Pixels auf der Rasterwiedergabesichtoberfläche zu Adreßwerten oder Positionen der Speicherbanken und Speicherbankzelladressen, die das geeignete Pixel enthalten, in Bezug zu stellen. Während lineare Adressierung vorzugsweise für Windowing-Systeme benutzt werden kann, wird das folgende binäre Adressierungsschema beschrieben. Die X-, Y-Adresse ist eine Verkettung von Indexbits für X und Y. Die X-Adresse einer Pixelstelle der Sichtoberfläche im X-, Y-Koordinatensystem wird durch die Adresse oder Indexbits XN-1, . . . , X&sub6;, X&sub5;, X&sub2;, X&sub1;, X&sub0; gegeben, wobei XN-1, . . . , X&sub6; die Blockadressen in X repräsentieren, wobei X&sub5;, . . . , X&sub2; die Adressen in X einer Quadrateinheit innerhalb einer Zelle repräsentieren, und wobei X&sub1;, X&sub0; die vier Bits innerhalb der Quadrateinheit identifizieren. Für eine Sichtoberfläche und eine Bitmappe mit einer Auflösung von z. B. 1024·1024 Pixeln wird die Sichtoberfläche unterteilt und ausgefüllt durch 1024 Blöcke der Dimension 64·16 Bits, wie oben beschrieben. Für eine Auflösung von 2048· 2048 Pixeln wird die Rastersichtoberfläche und die Bitmappe in 4096 Blöcke unterteilt. Ein Minimum von 10 bis 12 Adreßbits ist daher erforderlich, einen bestimmten Block, teilweise spezifiziert durch die Adreßbits X&submin;&sub1;, . . . , X&sub6;, zu identifizieren. Dieser X-Koordinatenteil der Blockadresse überträgt direkt zwischen dem X-, Y-Koordinatensystem und dem B-, A-Koordinatensystem oder PBM ohne Permutation gemäß Standard oder konventioneller Adressierungstransformation in den Speicher.
Die Kette von vier Adreß- oder Indexbits X&sub5;, . . . , X&sub2; identifiziert ein Quadrat in der horizontalen X-Richtung des Blocks, welche als Zelladresse bezüglich einer Koordinatenposition im X-, Y-Koordinatenraum identifiziert werden kann. Dies gelingt deshalb, weil in der horizontalen X-Koordinatenrichtung jede Koordinatenposition ein Quadrat von 4 Bits oder Pixeln repräsentiert. Jede Reihe von Blöcken entlang der horizontalen X-Richtung ist zusammengesetzt aus 16 Quadraten (64 Bits), deren Quadrate durch vier Indexbits X&sub5;, . . . X&sub2; identifiziert werden können. Jedes Quadrat der horizontalen X-Koordinatenposition wird kontrolliert oder hinzugefügt bei einer anderen der 16 Speicherbanken B, wie in Tabelle 1 gezeigt. Die Speicherbanken B sind ebenfalls in Blöcken organisiert, die die gleiche Blockadresse für bestimmte Blöcke aufweisen. Ist einmal die Blockadresse spezifiziert, ist sie dieselbe für alle Speicherbanken, und alle 16 Speicherbanken tragen zu dem Block bei. Der spezifizierte Block einer bestimmten Speicherbank ist in 16 Zelladressen für die 16 Zellen des Blocks eingeteilt, zu dem die Speicherbank beiträgt und aus dem ein Quadrat aufgebaut ist. Wie vorstehend erläutert, trägt jede Speicherbank eine Dateneinheit oder ein Quadrat zu jeder der 16 Zellen eines Blocks bei. Das Quadrat für eine spezielle Zelle ist daher identifiziert durch die Zelladresse innerhalb der Speicherbank B. Diese Zelladresse A und die Speicherbezeichnung B des PBM-Koordinatensystems steht mit den X-, Y-Koordinatenpositionen durch die logischen Linearpermutationstransformationen in Verbindung.
Im Falle der X-Koordinatenrichtung sind es nur die Zelladressen oder Quadrate für die Zelladressen oder Indexbits X&sub5;, . . . , X&sub2;, die permutiert werden und vier Indexbits repräsentieren. Bei der Definition der unterschiedlichen logischen und Draht-LPNs von Tabellen 2, 3, 4 etc. ist die Anzahl der Indexbits L daher vier und der konstante Koeffizient, der beispielsweise die zyklischen LPN Cp definiert, ist ebenfalls 4. Die Blockadreßbits XN-1, . . . , X&sub6; sind nicht permutiert, werden aber durch konventionelle Adressierung in die Speicherbanken übertragen. Mit anderen Worten ist der Block der Satz von Bits im Speicher, für den jede Speicherbank dieselbe Adresse hat. Jede Speicherbank hat dieselbe Blockadresse in einem bestimmten Block. Die Blockorganisation der vorliegenden Erfindung entsteht, weil Teile von Adressen sich nicht ändern. In gleicher Weise werden die Adreßbits X&sub1;, X&sub0;, welche ein Bit oder eine Pixelposition innerhalb des Quadrats identifizieren,nicht durch die LPNs permutiert. Es sind daher nur die vier Indexbits des Zelladreßteils, welche geändert werden, dies im Rahmen der ausgewählten Adressierungsmode, und daher sind es nur die Zelladressenbits, die permutiert werden. Es ist der Zellteil der Adresse, der sich ändert.
Die Y-Adresse einer Pixelstelle einer Sichtoberfläche im X-, Y-Koordinatensystem wird durch die folgenden Adreßindexbits gegeben:
YM-1, . . . , Y&sub4;, Y&sub3;, . . . Y&sub0;,
wobei YM-1, . . . , Y&sub4; den Y-Koordinatenteil der Blockadresse repräsentiert und Y&sub3;, . . . , Y&sub0; nicht nur das Quadrat innerhalb einer Zelle repräsentiert, sondern auch ein spezielles Bit oder eine Pixelposition, weil in der vertikalen oder Y-Richtung die Dimension einer Quadrateinheit nur ein Bit beträgt. Die vertikale Dimension eines Blocks ist 16 Bits oder 16 Pixelpositionen, welche durch die vier Indexbits Y&sub3;, . . . , Y&sub0; speziziert werden können. Wiederum überträgt der Y-Teil der Blockadresse YM-1, . . . Y&sub4; direkt zwischen dem X-, Y-Koordinaten- oder dem SBM-Raum und dem B-, A-Koordinatensystem- oder PBM-Raum ohne Permutation wie beim Standard oder konventionellem Adressieren über Transformation. Die vollständige Blockadresse wird durch Verkettung der X- und Y-Koordinatenblockadreßteile gegeben:
YM-1, . . . , Y&sub5;, Y&sub4;, XN-1, . . . , X&sub7;, X&sub6;.
Wie oben gesagt, wird die Blockadresse nicht permutiert und überträgt sich in den Speicherbankadreßraum in einer konventionellen arithmetischen Beziehung.
Die Handhabung der Blockadressen während der Auffrischung der Wiedergabe ist beispielsweise wie folgt. Bei Beginn jedes Rahmens werden, festgelegt durch die Uhr ID, auf dem Wiedergabedatenbus die Blockadreßzähler oder Register mit den Wiedergabestartblockadressen geladen, welche in dem Blockadreßregister des AGEN 15 gespeichert sind. Das Register wird mit der ersten darzustellenden Blockadresse geladen. Der Blockteil der Adresse wird über jede horizontal gescante Zeile erhöht, jedesmal, wenn die Uhr ID vom Wiedergabebus den Beginn eines Wiedergabespeicherzugriffszyklus anzeigt. Eine gescante Zeile auf dem Bildschirm ist zusammengesetzt aus justierten Reihen von 16 aufeinanderfolgenden Blöcken. Wenn eine neu gescante Zeile beginnt, verursacht die Uhr ID, den Y-Teil der Adresse um eine Reihe zu erhöhen. Wenn der Y-Teil seinen Maximalwert erreicht hat, nämlich die 16. Reihe von 0 - F des Blocks, wird die Blockadresse ebenfalls in der vertikalen Y-Richtung erhöht. Falls der Y-Anteil noch nicht sein Maximum ereicht hat und im selben Block verbleibt, wird die Blockadresse für die nächste gescante Zeile wiedergeladen. Auf diese Weise wiederholen die Wiedergabeadressen die gleiche Serie von Blockadressen 16 mal innerhalb 16 aufeinanderfolgenden Zeilen, wobei jede der 16 Zeilen unterschiedliche Y benutzt.
Wiedergabezugriffe benutzen nur den 64·1 Wiedergabewortzugriff, so daß nur der Y-Teil der Wiedergabeadresse benötigt wird, um die 16 Quadratadressen zu generieren, die alle gleich sind. Aktualisierungsadressen der Adreßregister des AGEN 15 benutzen irgendeine der ausgewählten zweidimensionalen Zelladressierungsmoden. Die Aktualisierungsadressen können beide X- und Y-Teile der Adressen benutzen als Zugabe zur Spezifikation der ausgewählten Zellkonfigurationsadressierungsmode.
Die Kette von vier Adressen oder Indexbits Y&sub3;, . . . , Y&sub0; identifiziert ein Bit oder eine Pixelposition in der vertikalen Y-Richtung des Blocks, welcher als eine Zelladresse im X-, Y-Koordinatenraum identifiziert werden kann. Jede Spalte des Blocks in der vertikalen Richtung ist zusammengesetzt aus 16 Bits oder Pixelpositionen von 16 Quadraten, welche durch die Indexbits X&sub3; . . . , Y&sub0; spezifiziert werden können. Jede vertikale Y-Koordinatenposition wird kontrolliert oder hinzugefügt durch einen anderen der 16 Speicherbanken B, gekennzeichnet durch die hexadezimalen Ziffern 0-11, wie in Tabelle 1 gezeigt.
Wie oben festgehalten, sind die Speicherbanken B ebenfalls in Blocks organisiert, jeder mit der gleichen Blockadresse für einen bestimmten spezifizierten Block. Ist die Blockadresse einmal festgelegt, trägt jede Speicherbank 16 Dateneinheiten oder Quadrate zu jedem Block von 16 Speicherbankadressen A bei. Jede der Speicherbankadressen A trägt eine Einheit von Graphikbilddaten oder ein Quadrat zu jeder Zelle des Blocks bei, und zwar für jeden unterschiedlichen Zelladressierungsmodus, der spezifiziert ist. Die Speicherbankadressen A sind mit sich unterscheidenden Zelladressen C für die unterschiedlichen Adressierungsmodenzellkonfigurationen korreliert. Jede der 16 Speicherbanken B hat daher 16 Bankadressen A innerhalb jedes Blockes, welche ebenfalls durch 16 sich ändernde Zelladressen C identifiziert werden können. Die Bankadressen innerhalb eines Blocks sind daher mit den Zelladressen C für irgendeine bestimmte spezifizierte Adressierungsmodenzellkonfiguration korreliert. Diese 16 Zelladressen C repräsentieren die 16 Dateneinheiten oder Quadrate, die zu jedem Block beigetragen werden, eine Einheit pro Zelle. Diese Zelladresse ist festgelegt, wenn der Block oder die Adressierungsmode einmal spezifiziert ist. Dies liegt daran, daß der Blockteil der Permutationsbitmappe im Rahmen der Erfindung so organisiert ist, nur genau eine Dateneinheit oder ein Quadrat zu jeder Zelle beizutragen. Sind die Adressierungsmoden bis hierhin einmal spezifiziert, können die Bankadressen A innerhalb eines Blockes mit den Zelladressen identifiziert werden, weil jede der 16 Quadrate oder Graphikdateneinheiten mit einer der 16 Zellen des Blocks für jede unterschiedliche Adressierungsmode verbunden ist. In den anschließend gezeigten Tabellen für jede der unterschiedlichen Adressierungsmoden sind es die Speicherbanken B und Zelladressen C für jede spezifizierte Adressierungsmode, die als Funktion der Benutzer-X-, -Y- oder X-, -Y-, -Z-Koordinatenpixelpositionen dargestellt werden. Die Bankadressen A oder Speicherbankbezeichnungen B des PBM-Raums oder Koordinatensystems sind daher mit dem X-, Y-Koordinatenraum durch eine lineare Permutation von Indexbits in X und Y, nämlich Xi, wobei i = 5, . . . , 2 und Yi, wobei i = 3, . . . , 0 ist, verbunden. Bei der Definition der unterschiedlichen logischen und Draht-LPNs der Tabellen 2, 3, 4 etc. bleibt die Anzahl der permutierten Indexbits L im Rahmen der ausgewählten Beispielsausführungen immer 4. Der konstante Koeffizient, der angewendet wird, bleibt auch 4. Wie schon gesagt, werden die Blockadreßbits nicht permutiert.
Wie in folgenden Adreßgleichungen ähnlich entwickelt, sind die Adreßbits oder Indexbits zur Spezifikation der 16 Speicherbanken B eines Blocks die vier Indexbits B&sub3;, . . . , B&sub0;. Die Adreßbits oder Indexbits zur Spezifikation der 16 Zelladressen A eines Blocks sind die vier Indexbits A&sub3;, . . . , A&sub0;. Die Adreßgleichungen sind daher Vektorgleichungen, die die mehrfachen Gleichungen zusammenfassen. In der bevorzugten Beispielausführung bleibt die Anzahl der permutierten Indexbits pro Dimension oder Koordinate, die Gegenstand einer linearen Permutationstransformation ist, immer vier, nämlich Xi, Yi, Bi, Ai, wobei die Anzahl der Indexbits L vier ist und i als einer der vier Werte angesehen werden kann. Die Anzahl von Index- oder Adreßbits L für jede Indexvariable, beispielsweise Xi, Yi, Bi, Ai, etc. ist wie der Logarithmus zur Basis 2 zu der Anzahl der logischen Speicherbanken M verbunden. Das heißt, L = log&sub2;(M). In Erweiterung der vorliegenden Erfindung auf die dritte Dimension Z mit 16 möglichen Ebenen der Organisation des Rahmenpuffers bleibt dieses ebenfalls richtig für die Indexbits Xi, Yi, Zi des SBM-Koordinatensystems als auch für die Indexbits Bi, Ayi, Azi des PBM-Koordinatensystems.
Eine vorrangige Ausführung der vorliegenden Erfindung ist die neuartige Konstruktion einer ganzen Klasse von Permutationsbitmappen mit den folgenden einzigartigen Charakteristika. Innerhalb jedes Blocks der Speicherbanken und der Bankzellen sind die Adressen in Korrelation mit den Pixelpositionen der Sichtoberfläche und des X-, Y-Koordinatensystems so angeordnet, daß mehrfach unterschiedliche Zelladressierungsmoden ausgewählt werden können und dennoch jede Speicherbank nur eine Dateneinheit (in diesem Ausführungsbeispiel das Quadrat) zu jeder Zelle von irgendeiner ausgewählten Konfiguration beiträgt. Die unterschiedlichen Zell- und Wortadressierungsmoden oder Konfigurationen füllen jeden Block aus oder greifen auf jeden Block zu, der alle Bits oder Pixelpositionen ohne Redundanz und ohne überlapp abdeckt, und bilden so Grenzuntermengen des Blocks. Jeder Speicherzugriffszyklus für irgendeine ausgewählte Adressierungsmode greift auf jede Speicherbank zu und greift auf eine Zelle oder ein Wort zu, zu der jede Speicherbank nur eine Dateneinheit beiträgt, welche im vorliegenden Beispiel durch ein Quadrat repräsentiert wird.
Dieser Ausführung der vorliegenden Erfindung erfordert eine lineare Permutationstransformation zwischen dem Standard-X-, Y-Koordinatensystem und dem PBM- oder B-, A-Koordinatensystem, welche wenigstens ein logisches LPN im Falle einer zweidimensionalen Bitmappe und wenigstens ein logisches LPN für jede Dimension nach der ersten höherdimensionaler Bitmappen verbindet. Deshalb sind für eine dreidimensionale PBM wenigstens zwei logische LPNs bei der funktionalen Transformation erforderlich. Des weiteren besteht keine Begrenzung in der vorliegenden Erfindung bezüglich der Anzahl der Dimensionen der Bitmappe. Beispielsweise kann eine vierdimensionale PBM konstruiert werden, die auf einer linearen Permutation von beispielsweise einem Benutzer-X-, -Y-, -Z-, -T-Koordinatensystem beruht, welches wenigstens drei logische LPNs verbindet und wobei die vierte Dimension die Zeit ist. Solch ein vierdimensionales LPN ist beispielsweise in Doppel- oder Mehrfachpuffergraphiken geeignet. Es sollte festgehalten werden, daß bei Linearpermutationsberechnungen die Werte der Daten sich nicht ändern, nur ihre Anordnung. Derart können die Variablen als Koordinaten angesehen werden, die die Daten enthalten, und die Mappenfunktion F kann angesehen werden als eine Berechnung, welche die Anzahl der Datenpunkte in eine unterschiedliche Anzahl ändert und daher eine Transformation von einem Koordinatensystem in ein anderes ist. Die Anwendung der Permutationstheorie auf Rahmenpufferadressierung ist ein einzigartiger Gebrauch dieser Mathematik, bei der die Datenordnung in mehr als einer Dimension durchgeführt wird. Die mathematische Literatur behandelt nur eindimensionale Probleme, während die vorliegende Erfindung sich mit neuartiger multidimensionaler Rahmenpufferadressierung durch lineare Permutationsoperatoren beschäftigt. Nach der Erfindung gibt es immer eine 1-zu-1-Abbildung der Daten aus einem Satz in einen anderen in der Art, daß die Daten durch eine inverse Transformation in ihre ursprüngliche Ordnung zurücktransformiert werden können. Abbildungsfunktionen, die diese 1-zu-1-Umkehrungseigenschaft besitzen, werden lineare Permutationsoperatoren oder kurz LPOs genannt. LPOs sind mathematische Funktionen, die die Regeln einer Algebra erfüllen und durch Formeln manipuliert werden können, um gewünschte Eigenschaften zu prüfen oder Endresultate zu erreichen.
Die physikalische Ausführung von LPOs in jeglicher Kombination wird als "Linearpermutationsnetzwerk" oder kurz LPN bezeichnet. Generell benötigt ein im Indexraum ausgeführtes LPN bemerkenswert weniger Schaltung als ein äquivalentes LPN, welches im Datenraum ausgeführt ist. Aus diesem Grund sind alle LPNs in den Adreßschaltungen oder dem Adreßgenerator im Indexraum ausgeführt. Hier werden die Bezeichnungen LPO und LPN zeitweise austauschbar benutzt, sind es jedoch die LPNs, die die physikalische Schaltungsausführung der LPOs sind.
Eine vielseitigere Permutationsbitmappenausführung der vorliegenden Erfindung ist in den Tabellen 5, 6, 7, 8 und 8A zusammengefaßt, wobei jede einen Block von 64·16 Bit Größe (16·16 Größe des Quadratblocks) der Permutationsbitmappe darstellt. Die Tabellen geben die Speicherbank und Bankzelladressen B,A oder B,C, als eine Funktion von X, Y oder X,W an, wobei W = Rp(Y) ist. Eine nähere Betrachtung der Zuweisung von Speicherbanken, bezeichnet durch die erste hexadezimale Ziffer O - F jedes Paars von hexadezimalen Ziffern im Hauptteil der Tabelle zu Pixel- oder Quadratpixelpositionen des X-, Y-Koordinatensystems offenbart einen Unterschied in der Permutationsordnung, der aus Auswechsel- oder Umkehrlinearpermutationsnetzwerken resultiert, im Gegensatz zu den zyklischen LPNs, die in Tabelle 1 generiert wurden. Tabellen 5 bis 8A zeigen ebenfalls die horizontale X-Koordinate, die von links nach rechts zunimmt, und die vertikale Y-Koordinate, die von oben nach unten zunimmt.
Ein Merkmal und Vorteil des Auswechsel- und Umkehr-PBM der Tabellen 5 bis 8 besteht darin, daß zusätzliche Adressierungsmoden AM angepaßt werden. Jede Adressierungsmode AM wird durch zwei Nummern hv bezeichnet, wobei h der Exponent zur Basis 2 der Anzahl von Quadraten in horizontaler Richtung und v der Exponent zur Basis 2 der Anzahl von Bits in der vertikalen Richtung ist, die jede Zelle des Adressierungsmodus aufbauen. Wie in Tabelle 5 gezeigt, wird der Block adressiert oder auf ihn zugegriffen durch einen 64·1 Bit Horizontalwortadressierungsmodus AM 40 zur Auffrischung der Wiedergabe und für Bitblocktransfers oder Polygonauffüllung. Tabelle 6 zeigt die Einteilung des Blocks in vertikal orientierte 4·16 Bit Zellen von Adressierungsmode AM 04, welche nützlich ist zur Aktualisierung des Rahmenpuffers zur Zeichnung vertikal orientierter Vektoren mit hoher Leistung. Eine große Anzahl von Pixeln kann aktualisiert werden, bis zu 16 Pixel in jedem Speicherzugriffszyklus. Tabelle 7 zeigt die Einteilung des Blocks in 16 horizontal orientierte 16·4 Bit Zellen im AM 22, nützlich zur Aktualisierung des Rahmenpuffers und zur Heranziehung horizontal orientierter Vektoren mit hoher Leistung. Mit Hinblick auf Tabellen 5, 6 und 7 gleicht die Auswechsel- und Umkehr-PBM der Fähigkeit des zyklischen PBM von Tabelle 1. Zusätzlich jedoch, wie in Tabellen 8 und 8A illustriert, kann der Block eingeteilt werden, adressiert werden und auf ihn zugegriffen werden durch quadratisch konfigurierte 8·8 Bit Zellen und horizontale 32·2 Bit Zellen für geeignete Anwendungen. In jedem Schritt tragen die 16 Speicherbanken genau eine Dateneinheit und Quadrat in jeder Zelle und den 8·8 Bit Zellen von Tabelle 8 und den 32·2 Bit Zellen von Tabelle 8A bei, füllen und überdecken von Block ohne Redundanz oder überlapp und bilden weitere Grenzuntermengen für Adressiermoden AM1 3 und AM3 1.
Betrachtet man die Tabellen 5 bis 8A, so ist offensichtlich, daß die Zuweisung von Speicherbankadressen B zu Pixelpositionen auf der Sichtoberfläche, die durch die X-, Y-Koordinatensystemblöcke der Tabelle repräsentiert werden, fest und invariant sind. In diesen Beispielen werden die Speicherbankbezeichnungen B als erste hexadezimale Ziffer gezeigt, während die Bankadressen A oder tatsächlich die korrespondierenden Adressen C für die spezifizierten Adressierungsmoden AM in der zweiten hexadezimalen Ziffer gezeigt werden. Daher ändern sich die Bankbezeichnungen B in derselben statischen Mode nicht. Die Zellzuweisung oder Zelladressen C jedoch ändern sich bei unterschiedlichen Zelladressierungsmoden. Tabellen 5 bis 8A zeigen die unvariierten Bandzuweisungen B und die logische Linearpermutation der Banken als permutierte Objekte in der Transformation durch logische Linearpermutation vom X-, Y-Koordinatensystem in das logische Speicherbankkoordinatensystem. Die Speicherbankzelladressen, welche hier den Zelladressen C entsprechen, werden ebenfalls zu "Permutationsobjekten", aber die Permutation ist nicht unvariiert und wechselt bezüglich der ausgewählten Adressierungsmodenzellkonfiguration. Alle 16 Speicherbanken sind in jeder Zelle repräsentiert, unabhängig vom Konfigurationsadressierungsmodus, aber die Speicherbankzelladressen der Bankadreßstellen A innerhalb der Speicherbanken variieren, wie im Hinblick auf die Beispielausführung der Permutationsbitmappenerfindung im folgenden in weiteren Details beschrieben wird.
Um die Permutationsbitmappen der Tabellen 5 bis 8A zu erreichen, sind die 16 Speicherbanken koordiniert oder zu den X-, Y-Koordinatenpixeln zugewiesen gemäß der logischen Linearpermutation, deren funktionale Transformation in den folgenden Gleichungen ausgedrückt ist:
B = Ep(X,Rp(Y))
oder B = Ep(X,W),
wobei W = Rp(Y) und umgekehrt
X = Ep(B,A,),
wobei Ep das Auswechsel- logische Permutationsnetzwerk, welches in Tabelle 4 definiert wird, ist, und Rp die Umkehrung oder das umgekehrte Draht-Linearpermutationsnetzwerk, welches in Tabelle 9 definiert ist, ist. Ein Schaltkreis zur Implementierung der Draht-LPN Rp ist in Fig. 8 gezeigt.
Mit Rücksicht auf die LPO- und LPN-Schreibweisen und Tabellendefinitionen werden die Stellen spezifischer Daten in einem Satz von Daten durch eine Indexvariable (auch als Datenkoordinate bezeichnet) definiert und durch Großbuchstaben, Variablennamen, wie X, Y und Z, ausgedrückt; B, Ay und Az; C, U und S etc. Alle Datensätze beinhalten eine Anzahl N von Datenobjekten als Potenz von 2, so daß jede Indexvariable L
- log&sub2;(M) Bits erfordert. Die individuellen Bits in einer Indexvariablen sind Boole'sche Werte, die entweder durch eine tiefgestellte Schreibweise, wie Xi, oder durch Anhängen der tatsächlichen Bitnummer an die Variable, wie X0, X1 und so weiter, repräsentiert werden. Die Bits in einer Indexvariablen sind ordnungssensitiv, und Bit 0 wird immer benutzt, um das am wenigsten signifikante Bit zu bezeichnen. Beispielsweise hat in einem System mit 16 Speicherbanken die "Banknummer" Indexvariable B vier Bits, die wie folgt definiert sind:
B = B[3 : 0] = [B3,B2,B1,B0]
Alle LPOs auf einer Indexvariablen schließen einfache Operationen auf die Bits des Index in der Weise ein, daß die Invertierungseigenschaft erhalten bleibt. Alle Ausdrücke in einem LPN müssen Variablen mit derselben Anzahl von Indexbits einschließen. Daher können allgemeine Formeln hergeleitet werden, die ein System jeglicher Größe zur Implementierung in ein spezielles System, welches die gewünschten Werte von L spezifiziert, beschreiben. Die LPO-Defintionen sind gemäß dem i-ten Bit einer Indexvariablen gegeben.
Formeln, die die Indexbitnummern einschließen, werden ausgeführt durch modulare Arithmetik, welche auf dem Modul L basiert. Das heißt, wenn j und k die Indexvariablen Bitnummern sind, dann ist:
i = j + k = (j + k) mod L
und
i = j - k = (L + j - k) mod L.
Zum Beispiel, wenn L = 4, j = 3 und k = 2 ist, dann:
j + k = 5 mod 4 = 1
und
k - j = (4 + 2 - 3) mod 4 = 3.
Der Umkehroperator Rp resultiert in der Umkehrung der indexvariablen Bits einer einzelnen Indexvariablen. Rp ist einfach die umgekehrte Ordnung der Bits in einer Indexvariablen. Eine zweite Umkehrung Rp wird die ursprüngliche Ordnung wieder herstellen, so daß Rp sein eigenes Inverses darstellt. Der Auswechsel-(Ep)-LPO ist ein logischer LPO, der zwei Indexvariable und den XOR Boole'schen Grundoperator benutzt. Man merke, daß XOR und XNOR die einzigen Boole'schen Funktionen von zwei Variablen sind, die umkehrbar sind. Die Auswechsel-LPN oder -LPO ist die ausschließliche oder Boole'sche Funktion der zwei Variablen. Die Inversion von Ep ist die Auswechselung oder Ersetzung zweier beliebiger Variablen aus Tabelle 4. Generell vertauscht Ep bezüglich irgendeines Draht-LpOs, wohingegen der logische Cp LPO nicht über irgendein Draht- LPO vertauscht. Weiterhin vertauscht Cp nicht bezüglich Ep Allgemeiner ist die Umkehr-Auswechselpermutationsbitmappe durch die folgenden fundamentalen Gleichungen in allgemeiner Form definiert:
B = fL(X,fW(Y)),
wobei fL eine Funktion eines logischen LPN ist, während fW eine Funktion eines Draht-LPN oder linearen Permutationsoperators ist. In der Mehrfachebenenausführung der Umkehr-Auswechselpermutationsbitmappe können die fundamentalen Gleichungen auch auf die zwei Dimensionen X und Z zur Adressierung an unterschiedlichen Anzahlen von Ebenen wie folgt angewendet werden:
B = fL(X,fW(Z)).
Die wechselnden Speicherbankzellen und Einheitenadressen C und U, die bezüglich des ausgewählten Adressierungsmodus AM wechseln, werden durch folgende LPN-Permutationen gegeben:
C = Qp(X,h,W) U = Qp(W,h,X)
und umgekehrt,
X = Qp(C,h,U) W = Qp(U,h,c),
wobei W = Rp(Y)
und h der Exponent oder Logarithmus zur Basis 2 der Anzahl von Quadraten in der horizontalen Dimension der ausgewählten adressierenden Modenzelle ist. Der Multiplex- oder Schalter-LPN Qp drückt die wechselnden Bankzellenadressen aus, die notwendig sind, die vielzahligen Zelladressierungsmoden zu erreichen. Die Adressenabbildung der Speicherbankadreßstellen A wird gegeben durch:
A = Qp(Ep(B,C),h,C)
Im Rahmen der besten Ausführung der Erfindung wird eine dreidimensionale Permutationsbitmappe konstruiert mit linearen Permutationen des Benutzer-X-, -Y-, -Z-Koordinatensystems, welches in drei Dimensionen adressiert und dabei eine neue Kombination von sowohl logischen als auch Drahtpermutationsnetzwerken benutzt, die wenigstens zwei Anwendungen von logischen Linearpermutationsoperatoren verwenden. In der bevorzugten dreidimensionalen PBM-Ausführung sind nahezu 50 unterschiedliche Zellkonfigurationsadressierungsmoden für den Zugriff auf die Blöcke verfügbar. Diese Zellkonfigurationen der besten Moden PBM sind in Tabelle 10 zusammengefaßt. Wie vorstehend beschrieben, ist die bevorzugte Ausführung mit Hinblick auf einen Rahmenpuffer, der aus acht physikalischen Speicherbanken, jede mit einem einzigartigen Satz von Adressierungsleitungen, beschrieben. Die physikalischen Speicherbanken werden bei jedem Speicherzugriffszyklus zweimal zeitlich geschnitten, wobei 16 effektive logische Speicherbanken zur Permutation in der dreidimensionalen Permutationsbitmappe bereitgestellt werden.
Wegen der dritten Dimension beinhaltet die Dimension des Blocks oder der Blocksektion nicht nur die horizontale Dimension von 16 Quadraten oder 64 Bits und die vertikale Dimension von 16 Bits im Falle einer Einzelebene P = 1, sondern auch die Tiefendimension einer Anzahl von Ebenen P von bis zu 16 Ebenen. Die Blockdimension ist daher Hmax· Vmax·P Bits, wobei P die Anzahl von Ebenen ist, die einen Wert von 1, 2, 4, 8 oder 16 Bits haben können. Die Blockgröße überschreitet 1024 Bits nicht. Jeder Block besteht aus und ist aufgeteilt in dreidimensionale Zellen. Die horizontale Zellbreite ist als H bezeichnet mit einer maximalen Zellbreite Hmax, die vertikale Zellhöhe ist als V bezeichnet mit einer maximalen Zellhöhe Vmax, und die Pixeltiefe ist entsprechend als P bezeichnet.
Die Anzahl von Adressiermoden der bevorzugten Permutationsbitmappe, welche anschließend beschrieben wird, sind in Tabelle 10 zusammengefaßt. Die meisten Adressierungsmoden bezüglich der Tabelle 10 gehören zur optimalen Permutationsbitmappe oder PBM oder vorliegenden Erfindung, obwohl das System auch eine Anzahl von Standardbitmappen oder SBM- Adressierungsmoden anpaßt. Die zweite Spalte bezeichnet oder nennt die respektiven Adressierungsmoden durch eine vierziffrige Zahl hvps. Der Ursprung dieser Bezeichnung ist wie folgt. Von den Spalten auf der rechten Seite spezifizieren drei der Spalten, bezeichnet als H, V und P, die respektiven horizontalen, vertikalen und ebenen Tiefendimension jeder der adressierenden Zellkonfigurationen in Bit. Die Bezeichnung durch Großbuchstaben ist daher umgekehrt, um die Dimension in Bit zu kennzeichnen. Von den linken Spalten repräsentieren die kleingeschriebenen Spalten h, v, p den Logarithmus zur Basis 2 der horizontalen, vertikalen und ebenen Tiefedimension, welche durch die respektiven Großbuchstaben H, V und P mit den entsprechenden Qualifizierungen spezifiziert wurde. Die v- und p-Bezeichnungen sind in der Tat die Exponenten zur Basis 2 der entsprechenden V- und P-Dimensionen in den einzelnen Bits. Die Bezeichnung h, welche sich auf die horizontale Dimension bezieht, ist hingegen der Exponent zur Basis 2 der Anzahl von Quadraten, welche die Zelle in der horizontalen Dimension definiert. Daher ist beispielsweise in der ersten Zeile, welche eine 64·1 Bit horizontale Wort-Zellkonfiguration festlegt, die horizontale Dimension 64 Bit oder 16 Quadrate, und h ist der Exponent 4 zur Basis 2, welcher 16 Quadrate ergibt, was ebenfalls 64 Bit entspricht.
Die vierte Bezeichnung der Adressierungsmode, welche die hvps- Notation benutzt, ist das s, welches sich auf die statische Adressierungsmode oder statische Mode bezieht. Nicht alle der PBM-Adressierungsmoden sind zur gleichen Zeit unter den mathematischen Bedingungen der dreidimensionalen Permutationsbitmappenarchitektur verfügbar. Nur solche Adressierungsmoden sind in gleicher Weise verfügbar, die einer Angrenzungsanforderung genügen, welche im folgenden beschrieben wird.
Die optimale multizellulare Adressierung-PBM-Architektur im Rahmen der vorliegenden Erfindung erlaubt dem Benutzer, eine von fünf statischen Moden s oder sm auszusuchen, gekennzeichnet durch die Nummern s = 0, . . . , 4, wobei jede statische Mode einen reichen Satz und eine Auswahl alternativer Zellkonfigurationsadressiermoden mit stark verbesserter Leistungscharakteristik, geeignet für eine bestimmte Anwendung, erlaubt. Wie in Tabelle 10 gezeigt, sind diese Adressiermoden, die dem Benutzer in gleicher Weise zur Verfügung stehen, bezeichnet durch dieselbe Ziffer s gleich 0, 1, 2, 3 oder 4. Die Parameter h,v,p zum Logarithmus der Basis 2 entsprechend den H-, V-, P-Parametern, werden mit dem Zeichen s der statischen Mode kombiniert, um die vier Zeichen der Adreßmode oder AM-Bezeichnung, z. B. AM3100, zu bilden, die zweite Adressierungsmode von Tabelle 10. Die AM3100 ist eine horizontal orientierte 32·2 Bit Zelle. Für jede der identifierten Zelladressierungsmoden sind die geeignetsten Verwendungen für die Zellkonfiguration in der rechten Spalte von Tabelle 10 aufgelistet. In dieser Spalte unter der Überschrift "GEBRAUCH" bezieht sich B auf den Gebrauch von Bitblocktransfers, während V sich auf den Gebrauch des Vektorschreibens bezieht. In einigen Fällen sind beides geeignete Verwendungen.
Unter Bezug auf Tabelle 10 wird festgehalten, daß das Produkt der Bitdimension H·V·P der dreidimensionalen Zelle immer gleich 64 Bit sein muß. Die unterschiedlichen Adressierungsmoden werden dadurch erreicht, daß jeweils zwei der drei Parameter variiert werden, aber das Produkt der Parameter immer exakt die 64 Bit Zellgröße der bevorzugten Beispielsausführung ist. Es wird auch festgehalten, daß die Summe der korrespondierenden Exponenten oder Logarithmen h,v,p immer gleich 4 ist, und diese Summe wird als L bezeichnet:
L = h + v + p,
wobei L = log&sub2;(M),
ein Parameter der nützlich ist, die Gleichungen des logischen und Draht- Linearpermutationsnetzwerks zu definieren. In den vorliegenden Beispielen ist M = 16 und L = 4. Die Zahl 4 stimmt mit der Anzahl der Adreßbits oder Indexbits, die in einer linearen Permutationsoperation für irgendeine Koordinatendimension permutiert wurden, und mit der Anzahl der niederwertigsten Adreßbits oder Indexbits, welche von Interesse für jede Dimension oder jeden Freiheitsgrad sind, überein. Es ist das vierte niederwertigste Bit in jeder der Dimensionen, welches permutiert wird, um die dreidimensionale Permutationsbitmappe zu erhalten. Im Falle der X-Koordinatendimension stimmt dieses jedoch mit den Adreßbits X&sub5;, . . . , X&sub2; überein, weil die Dateneinheiten Quadrate sind und die niedrigsten Bits X&sub1;, X&sub0; ein Bit oder eine Pixelposition innerhalb des Quadrats festlegen.
Die optimale Permutationsbitmappe oder die der besten Mode in drei Dimensionen, die mit den repräsentativ ausgewählten Adressierungsmoden der statischen Mode von Tabelle 10 korrespondieren, sind in den Tabellen 11 bis 25 dargestellt. Diese Permutationsbitmappen werden als Doppelauswechselungs-, Verschiebe- und Umkehrbitmappen bezeichnet, ausgeführt durch kombinatorische Lineartransformationsfunktionen, welche zwei Auswechsel- logische Linearpermutationsnetzwerke oder Operatoren und Schieber- und Umkehrdraht-Linearpermutationsnetzwerke oder Operatoren umfassen, welche nachfolgend vollständiger definiert werden. Ein einzelner Block des dreidimensionalen Doppelauswechselungsschieberumkehr -PBM wird in jeder der Tabellen 11 bis 15 gezeigt. Jede Tabelle präsentiert die Koordinaten des Benutzer-X-, -Y-, -Z-Koordinatensystems, repräsentiert in zwei Dimensionen mit der X-Koordinate in der horizontalen Richtung zunehmend von links nach rechts, der X-, Y- und Z-Koordinate in der vertikalen Richtung zunehmend von oben nach unten. Der Zuweisung von Speicherbanken im Hauptteil der Tabelle werden entsprechend Pixel oder Quadratpixelstellen der Sichtoberfläche der Blockunterteilung durch drei hexadezimale Ziffern repräsentiert. Die erste Ziffer ist die Bezeichnung der logischen Speicherbank B, welche mit der ersten Ziffer in den Tabellen 1 und 5 bis 8A verglichen werden kann. Die zweite hexadezimale Ziffer repräsentiert die Bankzellenadresse C für die spezifische Adressierungsmode AM innerhalb der Speicherbank, während die dritte hexadezimale Ziffer die dreidimensionale Blocksektion oder Zelladresse Az oder S repräsentiert. Für die Tabellen 11 bis 15 ist diese dritte Adressenkennzeichnung Null, weil diese Tabellen Adressierungsmoden der Permutationsbitmappe in einer einzigen Ebene repräsentieren. Die Einteilung zeigt ausgewählte der unterschiedlichen Adressungsmodenzellkonfigurationen AM, welche in der statischen Mode sm = 0 verfügbar sind. Alle Adressierungswortmoden, beispielsweise die, bei denen v = 0 und V = 1 ist, sind nicht dargestellt, obwohl sie in Tabelle 10 aufgeführt sind. Bei näherer Betrachtung sind die subtilen Unterschiede der Doppelaustauschschiebeumkehr-Permutationsbitmappe von der Auswechselumkehr-Permutationsbitmappe und der zyklischen Permutationsbitmappe offensichtlich. Es ist die Charakteristik und die subtil permutierte Organisation der Doppelaustauschschiebeumkehr- Permutationsbitmappe, die die reiche Auswahl von verfügbaren Zellkonfigurationsadressierungsmoden in mehrfachen Ebenen erlaubt, wie in Tabelle 10 zusammengefaßt. Die Tabellen 16 bis 25 repräsentieren vielfache partitionierte Blöcke, welche repräsentativ ausgewählte der unterschiedlichen dreidimensionalen Zellkonfigurationsadressiermoden AM in mehreren Ebenen für höhere statische Moden sm = 0 zeigen. Alle verfügbaren dreidimensionalen AMs sind in Tabelle 10 aufgelistet.
Die Gleichungen zur Definition der linearen Permutationstransformationen, um die PBMs der Tabellen 10 bis 25 zu begründen, sind in Tabelle 26 zusammengefaßt einschließlich der Ausgangsgleichungen. Die Gleichungen für Wortmodenadressierung AMhWp sind Spezialfälle, bei denen W = v = 0 ist. Eine alternative Bezeichnung oder Schreibweise zur Darstellung der gleichen fundamentalen Gleichungen von Tabelle 26 wird in den äquivalenten Gleichungen aus Tabelle 26A verwendet. Alle anwendbaren linearen Permutationsoperatoren oder LPNs sind bereits definiert worden mit Ausnahme des Verschiebedraht-LPN Sp, welcher in Tabelle 27 definiert und zusammengefaßt ist. Die Schaltkreise zur Ausführung des Schiebe-LPN Sp sind in den Fig. 9A bis 9D dargestellt.
Der Verschiebe-LPO Sp ist ein Draht-LPN oder LPO, der die Bits einer Indexvariablen rotiert. Die Phase der Rotation wird gegeben durch einen Phasenschiebeparameter oder Schiebephasenparameter. Das Inverse einer Verschiebung ist eine Verschiebung mit einem negativen Schiebephasenverschiebungsparameter oder einem Negativen des ursprünglichen Schieberphasenschiebungsparameters. Eine postive Schiebephasenverschiebung ergibt eine Links-nach-Rechts-Rotation, während eine negative Schiebephasenverschiebung eine Rechts-nach-Links-Rotation ergibt. Es sei bemerkt, daß Rp und Sp nichtdistributiv sind. Sp wird benutzt, um die ausgewählte statische Addressierungsmode oder die ausgewählte statische Mode-(sm) Permutationsbitmappe auszuführen.
Die generelle fundamentale Gleichung für die Linearpermutationstransformation zwischen dem Standard und den PBM-Räumen für die beste Mode der dreidimensionalen Linearpermutationsbitmappe hat die Normalform:
B = fL1 (X'fL2(Y'Z'))
Ay = Y'
Az = Z',
wobei fL1 und fL2 logische LPN-Funktionen sind und X', Y' und Z' weitere Draht- oder logische LPN-Funktionen der ursprünglichen Benutzer-Pixelkoordinaten X, Y und Z mit einbringen können. In dem bevorzugten Beispiel sind fL1 und fL2 der Auswechsel-LPN-Operator Ep oder sind mit diesem verbunden, und Y' und Z' sind mit Schiebe-Sp und Umkehr-Rp-Operator-LPN-Funktionen von Y und Z verbunden. Im einzelnen sind die bevorzugten fundamentalen Gleichungen von der folgenden Form:
B = Ep(X,Ep(Ys,Zr))
Ay =Ys Ys = Sp(sm, Rp(Y))
Az = Zr Zr = Rp(Z)
B = Ep(U,Ep(C,S)
Ay = C
Az = S
Die umgekehrte Transformation vom Permutationsbitmappenkoordinatenraum B,Ay,Az in das Benutzer-X-, -Y-, -Z-Standardkoordinatensystem ist ebenfalls in der funktionalen Form der fundamentalen Gleichungen wie folgt:
X = Ep(B,Ep(Ay,Az))
Yy = Ay Ys = Sp(sm,Rp(Y))
Zr = Az Zr = Rp(Z)
Die zwischengeschalteten Transformationen, beispielsweise zwischen dem X-, Y-, Z- und dem C-, U-, S-Koordinatensystem erfordern den gemultiplexten Schalthybrid LPN Qp, wie in den Gleichungen von Tabelle 26 und 26A dargestellt. Die fundamentale zirkulare Beziehung zwischen den drei Koordinatensystemräumen X, Y, Z; C, U, S und B, Ay, Az ist in Fig. 10 gezeigt. Dieses Diagramm illustriert das fundamentale Theorem der linearen Permutationsnetzwerktheorie, welches besagt, daß, wenn zwei der drei wechselseitig ableitbaren funktionalen Transformationen gegeben sind, die dritte ebenfalls gegeben ist. Um die lineare Transformation der besten Mode in zwei Dimensionen zu etablieren, sollten die fundamentalen Gleichungen der linearen Permutationstransformationen zwischen dem SBM- und dem PBM-Raum folgende generelle Form annehmen:
B = FL(X,fW)(Y),
wobei FL ein logisches Linearpermutationsnetzwerk oder eine Operatorfunktion ist, während fW eine Drahtlinearpermutationsnetzwerk- oder eine Operatorfunktion ist. Die Speicherbankzelle und die einheitlichen Adreßgleichungen können folgende Form annehmen:
C = Qp(X,h,W), U = Qp(W,h,Y), W = Rp(Y)
mit der Adreßabbildung
A = Qp(Ep(B,C),h,C))
Es sollte festgehalten werden, daß der nächstliegende Stand der Technik bezüglich Rastergraphikarchitekturen und Rahmenpufferbitmappen, wie z. B. Texas Instruments TI 34010 Graphiksystemprozessor oder die Carnegie Mellon University (CMU) zellulare Architektur, wie oben diskutiert, falls sie im Rahmen der linearen Permutationsnetzwerktheorie charakterisiert werden, nicht weitergehen und nicht charakterisiert werden können, als ob sie über eine Transformation der folgenden generellen Form hinausgingen:
B = fW(X,fW)(Y),
wobei fWs nicht mehr sind als Drahtlinearpermutationsnetzwerke oder Operatoren. In der Tat hat bisher kein Fachmann auf diesem Gebiet und keine Bauelemente gemäß dem Stand der Technik, von denen der Anmelder etwas wüßte, einen Hinweis auf die sehr produktive, aber nicht offensichtliche Anwendbarkeit einer linearen Permutationsnetzwerktheorie auf Rastergraphikarchitektur gegeben noch LPN-Konzepte in Rastergraphik- Software- oder Hardware verbunden oder ausgeführt. Noch wichtiger ist es, daß ein weiterer neuer und nicht offensichtlicher Beitrag und eine Entdeckung der vorliegenden Erfindung darin besteht, daß wenigstens ein logisches lineares Permutationsnetzwerk oder ein Operator, der aus einem umkehrbaren, d. h. selbstsymmetrischen Boole'schen Logiktor, wie XOR-und XNOR-Toren, konstruiert wurde, eingebaut wird.
Für eine zweidimensionale Bitmappe ist ein einzelner logischer LPN ausreichend, eine neue PBM zu begründen entsprechend der Erfindung mit einer reichen Auswahl mehrerer verschiedener Zellen- und Wortkonfigurationsadressierungsmoden. Darüberhinaus kann die zweidimensionale Permutation entweder in der X-, Y-Koordinatenebene oder der X-, Z-Koordinatenebene vorliegen, um eine neue zweidimensionale Permutationsbitmappe in eine der Ebenen bereitzustellen. Beispielsweise kann die fundamentale Permutation Transformationsgleichung in zwei Dimensionen auch auf die X-, Y-Ebene wie folgt angewendet werden:
B = fL(X,fW)(Z)).
Wie oben beschrieben, ist beim Übergang in eine dreidimensionale Bitmappe oder selbst in höherdimensionale Bitmappen eine Vielzahl von logischen Linearpermutationsnetzwerken, Operatoren oder Funktionen gemäß der fundamentalen Transformationsgleichung gefordert, eine für jede nach der ersten folgenden Dimension. Auf diese Weise kann eine mehrdimensionale Permutationsbitmappe begründet werden mit einer reichen und variablen Auswahl von dreidimensionalen oder höherdimensionalen Zellen- und Wortkonfigurationsadressierungsmoden. In jedem Schritt für gleich wie viele Dimensionen der multidimensionalen Permutationsbitmappe gemäß der Erfindung ist die fundamentale Abbildungsgleichung für die Speicherbanken B und unabhängig von den Adressierungsmoden. Das heißt, die Transformation oder Zuweisung der Speicherbanken B und Speicherbankadreßstellen A auf die Pixelpositionen der Sichtoberfläche bleibt invariant für jede bestimmt ausgewählte Permutationsbitmappe, während es die Zelladressen C sind, die variieren gemäß dem ausgewählten Adressierungsmodus. Wegen diesem charakteristischen Merkmal der Erfindung erscheint der Multiplex- oder Schalt-LPN Qp nicht in den fundamentalen Abbildungsgleichungen für B. Der Multiplexoperator Qp drückt die mehrfache Adressierungszelle und die Wortmoden für jede bestimmte Permutationsbitmappe der Erfindung aus und erscheint deshalb insbesondere in der Zelladresse, den Dateneinheitsadressen und den zellrelevanten Parametern und Koordinatengleichungen von Tabelle 26 und 26A. Die Bedeutung des Permutors oder Operators Qp liegt im Ausdruck der unterschiedlichen dynamischen Zellen-und Wortkonfigurationsadressierungsmoden, die anwendbar sind und im Zusammenhang mit einer ausgewählten Permutationsbitmappe erlaubt sind. Im beschriebenen Ausführungsbeispiel ist die bestimmte Permutationsbitmappe durch Wahl der statischen Mode sm oder s, die in Tabelle 10 gezeigt ist, ausgewählt.
Die gültigen dynamischen Mehrfachzelladressierungsmoden AM für jede der unterschiedlich ausgewählten statischen Moden sm oder Permutationsbitmappen des bevorzugten Ausführungsbeispiels sind auch in Tabelle 29 zusammengefaßt. Jede statische Mode sm kann angesehen werden als eine unterschiedliche Permutationsbitmappe oder PBM mit unterschiedlichen festen Zuweisungen oder Permutationen von Speicherbanken, die relativ zu den Koordinatenpositionen für Pixelpositionen der Benutzersichtoberfläche sind. Für jede unterschiedliche PBM oder sm sind die gültigen verfügbaren Adressierungsmoden AM durch den bestätigenden Buchstaben Y in Tabelle 29 angezeigt. Der Zwang, der hier festlegt, ob ein bestimmter Adressierungsmodus für eine bestimmte PBM oder sm verfügbar ist oder nicht, wird hier als Angrenzungserfordernis bezeichnet. Gemäß dem Angrenzungserfordernis sind nur kontinuierliche Moden verfügbar. Die Angrenzung oder die angrenzenden Moden beziehen sich auf Adressierungsgleichungen, in denen die Adreßbits oder Indexbits, nämlich die niederwertigsten Bits von X und Y und Z, benachbarte oder angrenzende Bits sein müssen. Beispielsweise ist Tabelle 30 eine Tabelle der Adressierungspermutation und Korrelation zwischen den C-, U-, S-Adressen- oder Indexbits und den X-, Y-, Z-Indexbits für die unterschiedlichen dynamischen Adressierungsmoden AM, die in der statischen Mode sm = 0 verfügbar sind. Bei Betrachtung der Tabelle ist es offensichtlich, daß das Angrenzungserfordernis durch die angezeigten Adressierungsmoden AM erfüllt wird, weil die niederwertigsten Bits oder X, Y oder Z immer benachbarte oder angrenzende Bits im Hinblick auf die numerische Ordnung des Index i sind.
Die Befriedigung des Angrenzungserfordernisses durch die meisten Adressierungsmoden, die für die PBM- oder statische Mode sm oder SM = 1 verfügbar sind, die PBM- oder statische Mode sm oder SM = 2, die PBM- oder statische Mode sm oder SM = 3 und die PBM- oder statische Mode sm oder SM = 4 ist respektive in den Tabellen 33, 36, 39 und 42 gezeigt. Jede dieser Tabellen zeigt auch die Transformation von Adreßbits zwischen dem Benutzer-X-, -Y-, -Z-Koordinatensystem oder der zwischengelagerten Blockzelle und dem Einheitenkoordinatensystem C,U,S. Es sollte festgehalten werden, daß in jeder dieser Tabellen die Indexbitnummer (niedergeschrieben durch Spezifikation eines Subskripts) den Koordinatendimensionsbuchstaben X, Y oder Z folgt und diese Tabellen sich auf dieses Subskript beziehen. In den Tabellen 33, 36, 39 und 42 sind die Indexbitziffern für Y und Z, in denen i = 3, . . . , 0 ist, und für X, in dem i = 5, . . . , 2 ist, der Einfachheit halber benachbart zu den Dimensionen der Koordinatenbuchstaben geschrieben. In den LPN-Definitionstabellen 2, 3, 4, 9 und 27 werden diese Indexbits als tatsächliche Subskripte geschrieben.
Die abschließenden physikalischen Speicherbankadreßverbindungen A in zwei Dimensionen und Ay, Az in drei Dimensionen sind von den fundamentalen Permutationsbitmappengleichungen der vorliegenden Erfindung in vier grundlegenden Schritten abgeleitet und formuliert. Im ersten Schritt werden die statischen Moden für das System und die möglichen statischen Modentransformierten oder statischen Transformierten begründet. Jede statische Mode ist eine bestimmte Abbildung von Pixeln vom Standard-X-, -Y-Koordinatensystem in physikalische Speicherbankstellen. In der bevorzugten Ausführung ist ein Bereich von statischen Moden verfügbar, von denen jede tatsächlich eine unterschiedliche physikalische Permutationsbitmappe mit einem unterschiedlichen Bereich von dynamischen Adressierungsmoden oder Adressierungsmodenzellkonfigurationen aufbaut. Ein definierter Satz von dynamischen Adressierungsmodenzellkonfigurationen wird auf die Permutationsbitmappe wirken, die durch eine bestimmte statische Mode definiert ist. Die statische Transformierte kann jede Kombination von Draht- oder Schalter-LPOs oder LPNs umfassen, aber schließt andere logische LPNs nicht ein. Das Resultat dieses ersten Schritts oder der statischen Transformierten ist ein Satz von modifizierten Funktionen von X, Y und Z, bespielsweise X, Ys, Zr, wobei Ys eine Schiebelinearpermutation von X ist und Zr eine umgekehrte Linearpermutationsfunktion von Z ist. In der alternativen Schreibweise von Tabelle 26A sind die anfänglich modifizierten Variablen beispielsweise X, Wy und Wz.
Im zweiten Schritt zur Definition und Formulierung der Adreßleitungsverbindungen und -gleichungen werden die Speicherbankbezeichnungen und -zuweisungen B und die Speicherbankadreßzuweisungen A in zwei Dimensionen und Ay und Az in drei Dimensionen als eine Funktion der modifizierten statischen transformierten Variablen X, Ys und Yz oder Wy, Wz begründet. Dies sind die fundamentalen Gleichungen für B, Ay und Az zu Beginn der Tabelle 26 und 26A. Diese Bankzuweisungstransformation oder logischen Bankzuweisungen begründen den Bereich der möglichen Adressierungsmodenzellkonfigurationen. Die Bankzuweisung-LPNs sind jede Kombination von logischen LPOs oder LPNs. Insbesondere die bankzuweisungstransformierte Funktion umfaßt zyklische Cp- und Auswechsel-Ep-Linearpermutationen in jeder Kombination, die alle Indexraumvariablen umfassen. Die Schalter-LPO Qp mit wenigsten einem konstanten Index kann eingefügt werden, um spezielle Permutationsbitmappen zu konstruieren, wie die zyklische Permutationsbitmappe von Tabelle 1. Wenn die Anzahl der Dimensionen des Indexraumes N + 1 ist, dann muß in der transformierten Funktion der Bankzuweisungen exakt N mal ein logisches LPO vorkommen entsprechend der Erfindung. Diese Bankzuweisungstransformationen müssen invertierbar sein, wie in den fundamentalen Gleichungen der Tabellen 26 und 26A gezeigt.
Der dritte Schritt bei der Formulierung der Adreßleitungsverbindungen ist die dynamische Zelladreßtransformation, welche die Adreßzelle und Einheitenkoordinaten in zweidimensionale Indexräume oder C,U,S in dreidimensionale Indexräume der modifizierten statischen transformierten Variablen X, Ys,Zr oder X,Wy,Wz ableitet. Diese Zelladressentransformierte definiert die möglichen dynamischen Zelladreßmoden für gegebene Sätze von statischen Transformationsgleichungen der Schritte 1 und 2. Jede Adreßmode wird ausgewählt durch eine Wahl von Parametern, die zur Dimension der ausgewählten Adressierungsmodenzelle in Beziehung steht, wie bisher mit Hinblick auf Tabelle 10 beschrieben wurde. Nur solche Adressierungsmoden sollten nützlich sein, die das oben diskutierte Angrenzungserfordernis erfüllen. Die Zelladressierungstransformation des dritten Schrittes umfaßt nur die logischen Schalteroperatoren Qp unter Benutzung der Adreßmoden, Wahlvariablen für die Schalterindexschwellenparameter, die als h bezeichnet in Tabelle 3 stehen und Variable h,L
- p und p' in den Tabellen 26 und 26A beinhalten. Die Zellmodentransformierte muß invertierbar sein und die invertierte Transformierte muß nur im Rahmen der U-, C-, oder U-, C-, C-Indexvariablen ausdrückbar sein. In gleicher Weise sollten in der inversen Transformierten nur Qp LPOs oder LPNs benutzt werden, wie in in den Tabellen 26 und 26 dargestellt. Die Zelladreßvariablen U,C und S in Tabelle 26 sind in der alternativen Schreibweise U,Cy,Cz in Tabelle 26A ausgedrückt.
Der letzte Schritt der Definition der Speicherbankadreßleitungsverbindungen, welche physikalisch die Architektur des Systems definieren, besteht darin, die physikalische Adreßabbildung der Bankadressenzuweisungen Ay und Az (auch bezeichnet als AY und AZ in den Adreßgleichungen) im Rahmen der Speicherbankzuweisungen oder Bezeichnungen B und die Zelladressen C in zwei Dimensionen oder C,S in drei Dimensionen abzuleiten. In der alternativen Schreibweise von Tabelle 26A sind die Speicherbankadreßleitungszuweisungen Ay und Az (AY und AZ) im Rahmen der Variablen B,Cy und Cz formuliert. Das in Fig. 10 diagrammatisch illustrierte fundamentale Theorem erlaubt die abschließende Index- oder Adreßleitungstransformation. Dies ist auch in der bevorzugten Ausführung der vorliegenden Erfindung möglich, weil die Operatoren Ep und Qp vertauschen. Sind die Speicherbankadreßzuweisungen Ay und Az einmal im Rahmen der Speicherbankzuweisungen B und Zelladressen C,S oder Cy, Cz formuliert, können äquivalente Boole'sche Gleichungen für die Ausführung der Speicherbankzelladreßleitungen und Leitungsverbindungen hergeleitet werden. Dies wird durch Ersetzung der LPO-Operatoren in den abschließenden Gleichungen für Ai, nämlich Ay und Az, mit ihren Boole'schen logischen Äquivalenten erreicht. Diese Adreßleitungen für Ay und Az sind in Fig. 11 gezeigt. Die fundamentalen Gleichungen für Ay uns Az sind in kombinatorischer Mathematik in Tabelle 26 und 26A zusammengefaßt. Die korrespondierenden äquivalenten Boole'schen Gleichungen Ay und Az zur Festlegung der tatsächlichen Adreßleitungsschaltkreise und Verbindungen sind in den Tabellen 28, 31, 33, 35, 37 und 39 gegeben. Die Indexbits &ijlig;, die den AY und AZ folgen, sind die variable Bitnummer i [3 : 0] und die "Zieh"-Nummer j, die entweder 0 oder 1 ist.
Während die Beispielausführungen mit Hinblick auf Rahmenpufferspeicheradressen und Datenräume von zwei und drei Dimensionen beschrieben wurden, ist die vorliegende Erfindung anwendbar auf n dimensionale Räume, welche durch n Koordinaten, Indexvariable oder Adreßvariable definiert sind. In jedem Fall können die fundamentalen Gleichungen für lineare Permutationstransformationen zwischen einem n dimensionalen oder n Standardkoordinaten umfassenden Benutzer/Betrachterraum einer n dimensionalen abstrakten Dateneinheit und einem Zelladreßraum und abschließend einer n dimensionalen Speicherbank und Bankadreßkoordinatenraum generalisiert werden.
Die Speicherbankadreßverbindungen für die korrespondierenden Adreßschaltkreise zur Erreichung des Beispiels der besten Mode sind in Tabelle 28 zusammen mit den Adressierungsgleichungen dargestellt in zusammengefaßtem Boole'schen Gleichungsformat fortgeführt. Diese Adreßleitungsgleichungen werden in den Tabellen 31, 33, 35, 37 und 39 in detaillierterer Form für die unterschiedlichen statischen Moden ausgeführt. Die externen Adreßgleichungen berechnen und generieren die Adreßleitungen. Sie konvertieren die fundamentalen Gleichungen und Ausgangsgleichungen von Tabelle 26 und 26A, welche in kombinatorischer Mathematik als lineare Permutationsoperatoren ausgedrückt sind, in Logikschaltungen ausgedrückt durch Boole'sche logische Gleichungen. Diese Symbolkonvention für die Adressierungsgleichungen und die externen Adreßgleichungen sind wie folgt.
Die H und P in dieser Spezifikation sind tatsächlich die Werte des Logarithmus, welche als h und p ausgedrückt werden. Dennoch werden sie in den Tabellen 31, 33, 35, 37 und 39 in Großbuchstaben geschrieben, weil es Konvention ist, Boole'sche Adreßgleichungen in Großbuchstaben zu schreiben. Die Ausdrücke HTL und PLT bezeichnen "h kleiner als" und "p kleiner als". Es soll bemerkt werden, daß die Subskripte gemäß ihrer Spezifikation als Subskripte in den Tabellen in derselben Zeile auftreten wie ihr Referent. Daher bezieht sich AY auf Ay. In den externen Adreßgleichungen bezieht sich das Pluszeichen "+" auf die logische "OR"-Operation, ein Leerzeichen bezieht sich auf die logische "AND"-Operation, das Komplementsystem "'" bezieht sich auf das logische Komplement oder die "NOT"-Operation und das Dachsystem beziehen sich auf die Ausschließlich- oder "XOR"-Operation. Diese externen Adreßgleichungen konvertieren die fundamentalen Gleichungen von Tabelle 26 und 26A in logische Schaltkreise.
Ein generalisiertes Blockdiagramm und ein Flußdiagramm eines Rastergraphiksystems gemäß der Erfindung, welches den AGEN 15, die verbundenen Adreßschaltkreise 20, die Rahmenpufferspeicherbanken 12 und die DGEN 22 illustriert, ist in den Fig. 11 und 12 dargestellt. Dieses Blockdiagramm zeigt die grundlegende Konfiguration einer Rahmenpufferadreß- und Datensteuerung für Rastergraphikmaschinen mit den neuen Elementen, welche durch die vorliegende Erfindung umfaßt werden. Wie in Fig. 11 gezeigt, schließt der AGEN 15 das grundlegende Linearpermutationsnetzwerk in einer Blockdiagrammform ein, um Graphikdatenadreßinformation im Benutzer-X-, -Y-, -Z-Koordinaten in die zwischengelagerte Zelle, die Dateneinheit und das Blocksektionskoordinatensystem C,U,S, zu transformieren. Bis hierher beinhalten die Netzwerkblöcke respektive Drahtlinearpermutationsnetzwerke Sp und Rp und die wichtigen Zelladreßpermutationshybrid-LPN Qp in der funktionalen Beziehung, die in der Tabelle 26 zusammengefaßt sind.
Im Beispiel von Fig. 11 ist die vollständige lineare Permutationstransformation vom Benutzer-X-, -Y-, -Koordinatensystem in die Speicherbank und das Bankadreßkoordinatensystem B,Ay,Az nicht innerhalb des AGEN 15 komplettiert. Diese Ausführung der Erfindung wird als äußere Adressierungsmode für AGEN 15 bezeichnet. Die Adressierungspermutationstransformationen werden vollständig in der verbundenen Adreßschaltung 20 ausgeführt, welche beispielsweise die externe Adreßschaltung der Tabelle 31, 33, 35, 37 und 39 beinhaltet. Der verbundene Adreßschaltkreis 20 schließt das lineare Permutationsnetzwerk zur Vervollständigung der Transformation vom intermediären C-, U-, S-Koordinatensystem in die physikalische Datenbank und den Speicherbankadreßkoordinatenraum B,Ay,Az ein. Die Vervollständigung der linearen Permutationstransformation wird durch logische Draht- und Hybrid-LPNs Ep Sp und Op bewerkstelligt, wie in den Gleichungen der Tabelle 26 fortgeschrieben und ausgeführt in den funktionalen Blöcken der verbundenen Adreßschaltung 20, wie in Fig. 11 gezeigt. Die resultierenden Speicherbankadressen sind durch die Adressierungsgleichungen zusammengefaßt und die Speicherbankadreßleitungsadreßverbindungen sind in den Tabellen 28, 31, 33, 35, 37 und 39 zusammengefaßt.
Die von den Speicherbankadreßstellen stammenden Daten werden für die spezifischen Graphikoperationen im DGEN 22 prozessiert, wie in Fig. 12 dargestellt. Eine detaillierte Beschreibung der Komponenten und Elemente des DGEN 22, der in Fig. 12, Teil 2 und Fig. 15 gezeigt ist, wird hiernach mit Rücksicht auf die Beschreibung des DGEN in den Fig. 15 und 12 bereitgestellt. Wegen der ungewöhnlich permutierten Ordnung der aus den Speicherbanken 12 stammenden Daten zeigt für den vorliegenden Zweck das Blockdiagramm von Fig. 12 die neuen Elemente, die zur Ausführung in der Graphikdatengenerationskomponente erforderlich sind. Wegen der Graphikoperation, die durchgeführt werden muß, beispielsweise Bitblocktransfers, Polygonauffüllung, Vektorbeschaffung etc., müssen die Daten in bestimmten Fällen vom PBM-Raum des B-, Ay-, Az-Koordinatensystems in das SBM-Standardkoordinatensystem umgeordnet werden. Um dies zu erreichen, werden prä- und postlineare Permutationsnetzwerke bereitgestellt, beispielsweise in Verbindung mit den EXNET- Elementen 110 und 120 der Fig. 12, im folgenden als PRENET und POSTNET der Fig. 15 bezeichnet, um die linearen Permutationen durchzuführen. Alternativ müssen Vektorgraphikdaten, die in den Speicher geschrieben werden sollen, vom Benutzer-X-, -Y-, -Z-Koordinatensystem in den zwischengelagerten PBM-Koordinatenraum C,U,S zur Anpassung und Maskierung mit Zieldaten etc. transformiert werden. Die Masken müssen Quell- oder Zieldaten auch während Bit Blt und Polygonfülloperationen angepaßt werden. Wie anschließend detaillierter beschrieben, werden lineare Permutationsnetzwerke zur Anpassung und Maskierung von Daten, welche alle gemischt und maskiert werden müssen, in den funktionalen Blockelementen des LPN des DGEN 22 in Fig. 12 ausgeführt. Alle diese Parameter zur Ausführung der Operationen bezüglich Graphikdaten im DGEN 22 sind in Tabelle 26 zusammengefaßt und definiert. Zusätzliche lineare Permutationsoperatoren können beispielsweise in die Translate-Komponente oder Elemente des DGEN 22 in Fig. 12 eingebettet sein nach Maßgabe der ausgewählten Permutationsbitmappe im Rahmenpuffer und daher gemäß der PBM-Organisation von aus dem Rahmenpuffer stammenden Daten.
Der AGEN 15 umfaßt einen Zeichen- oder Aktualisierungszelladreßgenerator, einen Erneuerungszelladreßgenerator, einen Blockadressengenerator, Adreßregister und einen Adreßmultiplexer. Jedesmal, wenn die Zellgrenze überschritten wird, werden die Werte für die Zelladresse und die Blockadresse aktualisiert. Die Zelladreßgeneration hängt ausschließlich von den aktuellen X-, Y-, Z-Werten ab, während die Blockadreßgeneration von einer Information abhängt, die anzeigt, welche Seite eines Speicherblocks überschritten wurde, und die die augenblicklichen Adreßwerte und Bitmappendefinitionswerte, welche sich in den Adreßregistern befinden, anzeigt. An jedem Punkt des Rasterprozesses, bei dem eine neue Zelle definiert wurde, wird die Speicheradresse, welche benötigt wird, um Speicher für diese Zelle zu lesen und zu schreiben, von der aktuellen Zelladresse und Blockadresse durch den Adreßmultiplexer zusammengesetzt und an die Speichersteuerung über den ADBUS 18 übertragen.
Weitere Details des AGEN 15 Aktualisierungszellgenerators sind in Fig. 13 beschrieben. Zur Zelladressengeneration werden die Eingabedaten im X-, Y-Koordinatensystem der momentanen absoluten horizontalen Zeichenposition für Vektoren und Zeichen in den augenblicklichen X- und Y-Zeichenpositionsregistern CURX und CURY empfangen. Die augenblicklichen X- und Y-Positionsregister stellen Dateneingaben für die XEDGE- und YEDGE-Register 180 und 182 bereit. Gemäß den neuen Elementen der vorliegenden Erfindung werden die abschließenden Zelladreßdaten in das C-,S- und Ay-, Az-Speicherbankkoordinatensystem durch lineare Permutationsnetzwerke permutiert unter Ausführung der LPN-Operatoren, wie in den funktionalen Blöcken der Fig. 14 beschrieben. Die LPN-Operationen, die von den grundlegenden definierenden Gleichungen der Tabelle 26 ausgewählt wurden, begründen die aktualisierten Zelladressen im Rahmen des ausgewählten Adressierungsmodus.
Weitere Details des AGEN-Erneuerungszellgenerators sind im Blockdiagramm der Fig. 14 gezeigt. Zur Erneuerungszelladreßgeneration unter Benutzung des Erneuerungswortmodus werden die erneuerten X- und Y-Koordinatenadreßdaten RY und RX gemäß den ausgewählten LPNs der Fig. 14 permutiert, also abgeleitet von den grundlegenden Linearpermutationsgleichungen von Tabelle 26. Die Ausgaben des Erneuerungszellgenerators sind die Erneuerungszelladressen in den C-, S- und Ay-, Az-Koordinatensystemen. Aufgefrischte Adressierung begründet das Auslesen der Wiedergabebitmappenspeicherdaten für den DGEN zur Konversion in einen seriellen Fluß, welcher dann benutzt wird, um die Strahlintensität für das Wiedergabelement zu kontrollieren.
Der DGEN oder die Datengeneratorkomponente 22, welche in den Fig. 15 und 12 gezeigt wird, ist die Datenpfadmanipulationskomponente der Systemarchitektur. Der DGEN verwirklicht die räumlichen Datenpermutationen, welche nötig sind, verschiedene Zelladreßmoden für Bitmappen mit variablen Ebenen und Hochgeschwindigkeitsvektorgeneration zu erlauben.
Der Zweck des DGEN ist erstens, die extrem hohe Bandbreite von Daten zu handhaben, die High-End-Graphiksystemen eigen sind, zweitens Flächenbilder zu generieren (Polygonfüllung, Fenster und Zeichen), drittens vektor-(zeilen-)artige Bilder mit "Strichgraphik"-Leistung zu generieren und viertens, die erste Ebene von Videobandbreitengeneration zur Bildauffrischung durchzuführen. In vergleichender Weise kann ein DGEN als "Bit-Blt-Chip" angesehen, der dem Fachmann bekannte Merkmale beinhaltet und seine Vorteile aus einer neuen Permutationsbitmappenarchitektur der vorliegenden Erfindung zieht, um die Aspekte der Datenmanipulation von Bilderzeugung mit einer Geschwindigkeit durchzuführen, die fünf bis zehn mal höher ist als die Rate vorherig entwickelter Komponenten.
Das grundlegende funktionale Blockdiagramm von Fig. 15 und das Blockdiagramm von Fig. 12 zeigt die hauptsächlichen funktionellen Komponenten des DGEN 22. Der DGEN stellt einen effektiven 64 Bit Pfad, der auf einem gemultiplexten 32 Bit Datenpfad beruht, bereit. Dies erzeugt eine ökonomischere Ausführung ohne Leistungsdegradation. Der DGEN 22 kann als aus drei Hauptsektionen bestehend angesehen werden: (1) Der prinzipielle Datenpfad im Zentrum der Fig. 15, (2) die Video-Sektion auf der rechten Fig. 15, und (3) die Vektorgenerationssektion auf der linken Seite von Fig. 15.
Die grundlegende Sequenz zur Modifizierung von Speicherinhalten besteht darin, Daten von dem DBUS 24 durch den voroperativen Permutationsnormalisierungsschaltkreis PRENET 110 zu nehmen, die Standardbitmappen SBM-Benutzerorganisation wieder abzuspeichern, falls angemessen, und dann diese Daten in den Quell- und Zieldaten-Latches SRCO 112, SRC1 114 und DST 115 abzuspeichern. Diese Daten werden dann durch den Justierrotator oder ALROT 116 umgeordnet und logisch im PLOG- und LOGCOM- Schaltkreis 118 gemischt, um das neu resultierende Wort zu bilden, welches postoperativ im POSTNET permutiert wird, um normalisierte Daten zur ungewöhnlichen PBM-Organisation zurückzugeben, die dann in den Speicher zurückgeschrieben werden. Die entsprechenden Komponenten von Fig. 16 und Fig. 11, Teil 2, werden mit denselben Bezugsziffern bezeichnet.
Die PRENET 110 und POSTNET 120 Schaltkreise, die auch als die EXNET Schaltkreise 110 und 120, Teil 2, bezeichnet werden, sind die hauptsächlich unterscheidenden Punkte des DGEN im Vergleich zu bestehenden Bit-Blt-Chips und bilden indirekt die Basis der Architektur der vorliegenden Erfindung. Die Notwendigkeit für diese Prä- und Postoperationsrotationen oder -permutationen ist eine Konsequenz der Art und Weise, in der die Daten im Speicher gespeichert werden, um den Zugriff durch die vielfältigen zellularen Adressierungsmoden auf die zweidimensionalen Pixelzellen zu erlauben, die die Basis für Hochleistungsvektorzeichnen darstellen. Die Justagerotation oder ALROT 116 wird genutzt, um die Position der Bits in den Bit-Btl-Quellworten bezüglich der Zielwortgrenzen zu justieren, bevor die Quellworte mit den Zielworten gemischt werden, wie es dem Fachmann in Rastergraphik bekannt ist. Der LOGCOM- Schaltkreis 18 und der verbundene PLOG-Schaltkreis stellen die programmierbaren Mittel zur Definition bereit, in welcher Art und Weise die Quellworte von Quellmultiplex- oder SRCMUX 122 (einschließlich der Vektorbits) in bestehenden Speicherzielworten vom DST-Register 115 kombiniert werden. Die 16 logischen Operationen, die bereitgestellt werden, schließen die Fähigkeit ein, exklusive ODER-Funktionen der Quellworte mit dem Ziel von Gummibandoperationen durchzuführen und die Quelle mit dem Ziel zu "odern", transparente Bilder zu simulieren. Der BITMUX 124 ist der prinzipielle Datenpfad, der die Auswahl von Bits, die in den Zielspeicherworten zurückgelassen werden, ohne Modifikation erlaubt gemäß der Definition durch die Ausgabe von EDGEMAST 155 und Maskenmultiplexer MASKMUX 125. Beispielsweise müssen die Bits in einer Bit-Blt-Operation, die links und rechts vom Zielbildfenster stehen, ohne Modifikation gelassen werden.
Gemäß dem Beispiel ist die Auswechsel-Linearpermutation Ep im DGEN 22 von Fig. 15 unter Benutzung der PRENET- und POSTNET-Schaltkreise ausgeführt, welche beispielsweise die Auswechsel-LPNs aus den Fig. 16 und 17 umschließen. Bezüglich der DGEN-Dateneingabe 24 an PRENET 110 ist das Eingabewort die Banknummerkennzeichnung oder -zuweisung B, und die Ausgabe des PRENET-Schaltkreises ist das Quadrat oder der Quadratpixel der Koordinaten der normalisierten Graphikdateneinheit U. Die Zelladreßparameter Ep von C,S sind dann die PRENETC-Kontrolle für das PRENET- Permutationsnetzwerk. Die Ausgabe des PRENET-Schaltkreises 110 geht über eine mögliche weitere Drahtpermutationsnetzwerktransformation in TRANS- LATE 152 an die DGEN-Register gemäß dem betreibenden statischen MOS oder der Permutationsbitmappe. Daher kann günstigerweise die Kontrolle für das PRENET-Permutationsnetzwerk 110 einfach die Zelladreßfunktion Ep(C,S) zur Operation des DGEN 22 mit Permutationsbitmappen sein. Für eine Operation von DGEN 22 mit einer Standardbitmappe ist die PRENETC- Kontrolle gleich null. Die Quadratpixeleinheitskoordinaten U werden daher als Funktionen der Speicherbankkennzeichnungen B und Zelladressen C von den fundamentalen Gleichungen abgeleitet:
U = Ep(B,Ep(C,S) PRENETC = Ep(C,S)
Der POSTNET-Output-Permutationsschaltkreis 120 ist die Inversion des PRENET-Schaltkreises 110. Die POSTNET-LPN-Schaltkreise führen die Auswechselinversion des fundamentalen Theorems durch, nämlich:
B = Ep(U,Ep(C,S)) POSTNETC = Ep(C,S)
Daher ist die Eingabe an den POSTNET-Permutationsschaltkreis 120 vom Ausgang des Multiplexers 124 in den quadratpixelnormalisierten Einheitsdimensionskoordinaten U, und die Ausgabe ist in permutierten Speicherbankzuweisungskoordinaten B zur Rückgabe an die Rahmenpufferspeicherpermutationsbitmappe. Die POSTNETC-Kontrolle kann in gleicher Weise die Zelladreßfunktion Ep(C,S) zur Permutationsbitmappe sein, von der die Speicherbankkoordinaten B als Funktion von C und U abgeleitet werden. Während das POSTNETC-Kontrollsignal für die Operation des DGEN mit den Rahmenpufferpermutationsbitmappen Ep(C,S) sein kann, ist das Kontrollsignal für die Standarbitmappen gleich null. Die Netzwerksanordnungen zur Ableitung dieser Signale entsprechen den linearen Permutationsfunktionen, wie in Fig. 12 gezeigt.
Das Schiebelinearpermutationsnetzwerk Sp kann beispielsweise in die TRANSLATE-Komponente eingeschlossen sein, um Wechsel in der statischen Mode oder der Permutationsbitmappe anzupassen. Der Schiebe-LNP- Operator Sp leitet eine statische adreß- oder indexbitpositionenwechselndeTransformation sein. Eine Charakteristik des Schiebeoperators Sp ist, daß er die Zuweisung von Pixelpositionen in dem Benutzer/Betrachter-X-, -Y-, oder -X-, -Y- oder -Z-Koordinatensystem auf Speicherbankadreßstellen im B-, A- oder B-, Ay-, Az-Koordinatensystem wechselt. Dieser Wechsel in der Permutationsbitmappe wird hier als statische Transformation bezeichnet und wechselt die statische Mode sm.
Der Schiebe-LNP Sp ist nur für den Wechsel der statischen Mode oder der Permutationsbitmappen nützlich und kann nicht in der fundamentalen Gleichung für eine bestimmte Permutationsbitmappe gebraucht werden, wenn die PBM einmal begründet ist. Andererseits sind die logischen Permutationsnetzwerkoperatoren Ep und Cp alleine oder in Kombination miteinander oder mit dem Draht-LPN Rp nützlich, um eine bestimmte Zuweisung von Pixelpositionen zu definieren und damit die Permutation ohne Änderung der Adreß- oder Indexbits durchzuführen. Die Zuweisung von Pixelpositionen an physikalische Speicherbankadreßstellen bleibt ohne Rücksicht auf ihre Operationen durch die Operatoren Ep, Cp und Rp gleich.
Ein anderer Draht-LPN, der nützlich ist, die Index- oder Adreßbits zu wechseln und daher die Verbindung von Pixelpositionen im Benutzer/Betrachter-X-, -Y-Koordinatensystem mit den Speicherbankadreßstellen, ist der Schmetterling-LPN Bp.
Daher kann gemäß der Erfindung der Schmetterlingoperator Bp anstelle des Schiebeoperators Sp benutzt werden, um die Permutationsbitmappe in unterschiedliche statische Moden sm zu ändern. Kurz gesagt, umfaßt die Schmetterling-Linearpermutationsoperation (LPO) Bp die Auswechselung eines speziellen zufälligen Indexbit Nummer K mit dem niedrigstsignifikanten Bit (LSB) dieser Adresse oder dieses Index. Zum Beispiel:
Wenn Bp(k;ai) = Bp(2;A&sub3;A&sub2;A&sub1;A&sub0;)
wobei k = 2 und i = 3, . . . , 0
L = 4 (der konstante Koeffizient oder Anzahl von Indexbits)
i = Indexbitnummer = L - 1, . . . , 0;
dann ist Bp(1;A&sub3;A&sub2;A&sub1;A&sub0;) = A&sub3;,A&sub0;,A&sub1;,A&sub2;.
In diesem Beispiel, bei dem das spezifizierte oder ausgewählte ausgewechselte Indexbit k = 2 ist, wird das Adreß- oder Indexbit A&sub2; mit dem niedrigstsignifikanten Bit der Adresse, nämlich A&sub0;, ausgewechselt. Der Schmetterling-LPO ist selbstinvertierend wie folgt:
Bp(k,)Bp(k,A) = A.
Der Verschiebe-LPO Sp und der Schmetterling-LPO Bp stellen daher Beispiele von linearen Permutationsnetzwerken bereit, die tatsächlich die Indexbitpositionen, welche für den Wechsel der Definition oder Organisation der Permutationsbitmappe und daher der statischen Moden sm nützlich sind, wechseln oder auswechseln. Solche LPOs können in die Adreßschaltung zum Wechsel der PBM und die TRANSLATE 152 Komponente des DGEN zur Normalisierung der Daten, die aus alternierten oder neu definierten PBMs stammen, eingefügt werden. Die TRANSLATE-Komponente kann auch andere LPNs einschließen, die notwendig sind, aus dem Rahmenpufferspeicher stammende Daten zu normalisieren, wie z. B. die Umkehr-LPN Rp Die Video-Generationssektion der Bit-Blt-Chips ist aus zwei Gründen bereitgestellt. (1) Pufferdaten vom Bildspeicher benutzen die DGEN-Hochgeschwindigkeitsbusschnittstelle und (2) verdecken sie die Fremdartigkeit der Bitanordnung der PBM-aufgefrischten Daten im Bildspeicher. FIFO-Pufferung 128 der Video-Daten ist ein Standard, um Systemzeitschaltung zu vereinfachen und erlaubt eine effektivere Nutzung von Speicherbandbreite. Die Einbeziehung der Video-FIFO oder VFIFO 128 in den DGEN läßt Standard-DRAMs aussehen wie Video-RAMs oder wie VRAMs. Die Einbeziehung der 40 MHz-Video-Schieberegister 130 in den DGEN erlaubt, billige Standard-ECL-Schieber zu benutzen, um die abschließende Systembandbreite zu generieren. Alternativ kann der DGEN auch direkt mit kommerziell verfügbaren LUT/DAC (Farbsuchttafel/Digital-Analog-Wandler)- Komponenten verbunden werden, die mit Video-Schieberegistern ausgerüstet sind.
Die Vektorgenerationssektion auf der linken Seite des DGEN 22 in Fig. 15 besteht aus Hochgeschwindigkeitsschaltkreisen, die den Vektorquellwert-Latch oder das Regier VVL 140 und ein Vektormaskier-Latch oder Register VML 142 laden, basierend auf der Datenoperation (DOP), Pixelwerten (PFLD) und Unterbrechungssequenz -(BFLD)-Kontrollsignaleingaben auf dem DOBBUS. Diese Sektion schließt 6-Bit X-Wert- und 4-Bit Y-Wert-Zähler ein, welche die Position im Register kontrollieren, in die die aufeinanderfolgenden Wertebits geschrieben werden. Die X- und Y-Zähler werden als Funktion der momentanen Zeichenrichtung und der Werte des Unterbrechungssignals für jedes Bit erhöht und erniedrigt. Dieser Schaltkreis ist konstruiert, um den Datenmanipulationsteil der inneren Schleife irgendeiner Variation eines Bresenham'schen Vektorzeichenalgorithmus auszuführen, wie er auf dem Gebiet der Rastergraphik wohlbekannt ist. Der DGEN kann auch mit nicht Bresenham-Zeilengeneratoren verwendet werden.
VMR 144 ist ein 64-Bit Vektormaskenaufbauregister. Vektormaskenbits werden zuerst in dieses Register gespeichert, bevor sie in das VMR-Register 142 geladen werden. VVR 145 ist ein 64-Bit Vektorwertaufbauregister. Vektorpixel werden zuerst im VVR aufgebaut, bevor sie in den VVL zur Speichermodifikation transferiert werden. DSMR 146 ist ein 32-Bit DGEN Statikmodenregister. Es speichert die statische Modenkontrollinformation für die Video-Kontrolle 147. DIR 156 kontrolliert die Richtung der Bitblocktransferoperation. DBSV ist ein 32-Bit Blocktransfer-, Vertikaltransfer-Kontrollregister. Es beinhaltet die Information, welche vom DGEN benötigt wird, um den Datentransfer und die Übersetzung für eine vollständige Blocktransferoperation mittels der Instruktionskontrolle 150 zu kontrollieren. ROTC ist ein 6 Bit Rotationsindex. Er definiert den Betrag, um den der Quellregisterwert rotiert wird, bevor er mit den Zielbitmappendaten gemischt wird. XLTC kontrolliert die Übersetzung von Quelldaten vom Speicher durch die TRANSLATE-Komponente 152.
DVSH 154 ist ein 32-Bit Vektor und Blocktransferhorizontalkontrollregister. Es beinhaltet die Information, welche vom DGEN benötigt wird, Kantenmaskierung für Blocktransferoperationen durch EDGEMASK 155, beide linke Kante oder LEDGE- oder rechte Kante oder REDGE-Permutationskontrolle der Zielbitmappe und Positionsinformation für die Vektorzeichnung zu kontrollieren. Das WEM-Signal erlaubt die schreibfähige Maskenausgabe. Es erlaubt nur, einen Teil von Zielworten im Speicher zu modifizieren. Das GLOG- oder globale logische Operationsregister kontrolliert die Mischung von SRC- und VVL-Registern bezüglich ausgewählter Operationen.
Lineare Permutationsnetzwerke oder LPN-Schaltkreise zur Ausführung des PRENET 110 und POSTNET 120 des DGEN 22 für Auswechselpermutationsbitmappen sind in den Fig. 16 und 17 illustriert. Fig. 16 illustriert eine Kombination von Auswechsel-LPNs für Graphikbilddatenoperationen mit einer Auswechsel-Permutationsbitmappe oder PBM des beschriebenen Typs. Mit Bezug auf Fig. 16 umfaßt jedes rechteckige Element 190 ein logisches Auswechsel-Linearpermutationsnetzwerk Ep mit zwei Dateneingängen und -ausgängen, wie in Fig. 17 illustriert. Die respektiven Auswechsel-LPNs 190 sind dann gekoppelte Auswechsel-LPNs, die die acht Dateneingaben D [0, . . . 7] insgesamt in die permutierten Datenausgänge DLPN [0, . . . , 7] permutieren.
Für zyklische Permutationsbitmappen können PRENET 110 und POSTNET 120 durch den zyklischen LPN, Cp ausgeführt werden. Der zyklische Operator C p ist im Indexraum durch ein Addierbit im DGEN ausgeführt im Datenraum durch einen Datenrotator oder Barrelschieber. Cp kann auch genutzt werden, um Systeme zu definieren, in denen der Datenjustierrotator oder ALROT 116 im DGEN 22 auch genutzt wird, die Permutationsnormalisierung durchzuführen. Obwohl dies die Torkomplexität des DGEN reduziert, ist die Anzahl von einzigartigen Adreßleitungen, die erforderlich sind, proportional zur Anzahl von Adreßbanken, was bedeutet, daß die Bankadreßleitungen extern für den AGEN berechnet werden müssen. Im Gegensatz dazu sind für die Komponenten, die auf dem Auswechsel-LPO Ep basieren, die Anzahl von einzigartigen Adreßleitungen, die erforderlich sind, proportional zum Logarithmus zur Basis 2 der Anzahl von Speicherbänken N, so daß die Adreßleitungen intern zum AGEN berechnet und als Teil des gesamten Speicheradreßwortes übertragen werden. Dies reduziert substantiell die Komplexität der externen Schaltung.
Die DGEN-Komponente 22 von Fig. 15 schließt auch das Schaltkreiselement TRANSLATE 152 ein, welches zusätzliches LPNs umfaßt, wie sie für eine bestimmte Permutationsbitmappe oder PBM erforderlich sein könnten, beispielsweise zusätzliche Draht-LPNs, wie der Umkehr-LPN Rp und/der Schiebe-LPN Sp Alternativ kann das PRENET 110 und POSTNET 120 direkt zusätzlich logische oder Draht-LPNs umfassen, beispielsweise zur Ausführung der Doppel-Auswechselschieber- und Umkehr-PBM, welche in den Tabellen 11 bis 25 beispielhaft zusammengefaßt sind. Ein fundamentales Konzept der linearen Permutationstheorie ist, daß LPO-Transformationen bezüglich der Ordnung der Daten in zwei fundamental unterschiedlichen, aber exakt gleichen Arten angesehen (und ausgeführt) werden können, nämlich in (1) dem Datenraum und (2) dem Index- oder Adreßraum. Im Datenraum werden die Daten physikalisch von einem Ort an den anderen bewegt. Im Indexraum (oder Koordinatenraum) bleiben die Daten physikalisch im selben Raum, aber werden in einer unterschiedlichen Anordnung zugänglich (gelesen oder geschrieben). Eine Gleichung, welche LPOs benutzt, kann unter Benutzung beider ausgeführt werden. Im Falle der Architektur der vorliegenden Erfindung permutieren alle AGEN und Adreßschaltkreisoperationen die Pixeldaten in den Speicherblöcken unter Benutzung von Indexraumoperationen, wobei der AGEN niemals die Daten physikalisch erfaßt. Im Gegensatz dazu führen die meisten DGEN-Operationen dieselben Gleichungen im Datenraum aus durch physikalische Bewegung von Bits von einem Ort zum anderen. Die Invariante für all diese Operationen ist die Stelle der Pixel im Speicher, welche dieselbe sein muß für alle Adreßmoden, die auf dieselben Permutationsbitmappen zugreifen. Die AGEN-Zelladressierungen an den Speicher werden benutzt, um die Datenordnungstransformation zu definieren, indem sie jeder Speicherbank erlauben, Pixeldaten von unterschiedlichen Stellen beizutragen. Dies erlaubt die Ausführung der Adreßmoden. In den Transformationsgleichungen ist der Datensatz aus dem Speicher generell in der Weise permutiert, daß er nicht direkt für eine Wiedergabeauffrischung oder eine Blocktransferoperation verwendbar ist. Der DGEN-PRENET-Schaltkreis führt dieselben Gleichungen im Datenraum aus, um die Normalisierung von Daten in der Schirmordnung zur Auffrischung und zur Blocktransferoperation zu erlauben. Der DGEN-POSTNET- Schaltkreis repermutiert in die PBM-Ordnung, die für ordnungsgemäße physikalische Plazierung der Daten in die Speicherbanken benötigt wird.
Graphikoperationen im Datenraum-Koordinatensystem repräsentieren ein exponentielles Anwachsen der Anzahl von Permutationsobjekten, welche durch die LPN-Schaltkreise permutiert wurden, gegenüber den Operationen im Indexraum. Deshalb ist es gemäß der Erfindung vorteilhaft, die meisten Operationen oder so viele Operationen wie möglich im Adreß- oder Indexraum unter Verwendung der Adreßschaltung auszuführen. Jene LPN-Operationen, die nicht in die Adreßschaltung umplaziert werden können, werden dann in der Datengeneratorschaltung bezüglich Daten im Datenraum ausgeführt.
Beispielsweise sind die Fig. 6A und 17 äquivalent in ihren ausführten Funktionen, aber der einfachere Schaltkreis in Fig. 6A operiert im Index- oder Adreßraum, und der kompliziertere Schaltkreis von Fig. 17 operiert im Datenraum. Bezüglich der Anzahl von Permutationsobjekten besitzen der Indexraum und der Datenraum bezüglich einander diese logarithmische oder exponentielle Beziehung. Im Rahmen eines anderen Beispiels ist der zyklische Operator Cp im Indexraum durch einen Addierer ausführt und im Datenraum durch einen Datenrotator oder Barrel-Verschieber.
Daher unterscheidet sich die vorliegende Erfindung von konventionellen Rastergraphikmaschinen in den folgenden Punkten. Erstens führt die vorliegende ein und erfordert wenigstens drei Abbildungsräume, X,Y,Z; B,Ay,Az: und C,U,S im Gegensatz zum Stand der Technik und konventionellen Rastergraphikmaschinen, die nur zwischen zwei Abbildungsräumen operieren. Zweitens führt die vorliegende Erfindung ein und erfordert wenigstens zwei Abbildungsbeziehungen zwischen wenigstens drei neuen Abbildungsräumen. Eine dieser Abbildungsbeziehungen repräsentiert die Invarianzeigenschaft des Systems der vorliegenden Erfindung, während die andere Abbildungsrelation die Varianz oder Auswahleigenschaft des Systems der vorliegenden Erfindung repräsentiert. Dies ist im Gegensatz zu konventionellen Rastergraphiksystemen, die mit nur einer invarianten Abbildungsrelation operieren. Drittens führen diese neuen Abbildungsrelationen gemäß der vorliegenden Erfindung lineare Permutationstransformationen aus, die permutierte oder Permutationsbitmappen bilden. Gemäß einer der Abbildungsrelationen wird die invariante Pixelposition/Bankadressenabbildung durch logische Permutationsnetzwerke erreicht, welche logische Permutationsoperationen durch reversible selbstsymmetrische Boole'sche Logiktore ausführen. Andererseits wird die zweite Varianz oder Auswahlpixelposition/Zelladreßabbildung durchgeführt unter Verwendung von logischen Multiplex- oder Schaltlinearpermutationsnetzwerken Qp, welche im Wechsel von Zelladressen für die Einheiten von Graphikbilddaten gemäß der ausgewählten Adressierungsmodenzellkonfiguration resultieren.
Ein weiteres Beispiel der multizellular adressierenden Permutationsbitmappen-Rahmenpufferarchitektur der vorliegenden Erfindung wird mit Hinblick auf die Fig. 18 und die Tabelle 40 beschrieben. Dieses Beispiel gehört zu einer Rahmenpuffer-Rastergraphikmaschine gemäß der Erfindung mit drei Pixeldimensionen X,Y,Z und zwei Blockdimensionen im Speicherbankadreßraum B,A und Zell- und Einheitenadreßraum C,U. Dieses System basiert in gleicher Weise auf 16 Speicherbanken B, so daß L, der Logarithmus zur Basis 2 der Anzahl der Speicherbanken, der die Anzahl von Indexbits für jede der Variablen X,Y,Z,B,A,C,U repräsentiert, gleich vier ist. Die fundamentalen Gleichungen, die dieses System definieren, sind wie folgt:
B = Ep(X,W)
A = W
W = Qp(Rp(Z),sm'Sp(sm,Rp(Y))
U = Qp(W,h,X) = Ep(B,C)
C = Qp(X,h,W) = Ep(B,U)
X = Qp(C,h,U) = Ep(B,A)
W = Qp(U,h,C) = Ep(B,X)
B = Ep(U,C)
A = Qp(Ep(B,C),h,C)
Der statische Modenparameter oder die Anzahl wird durch sm angezeigt, während sm' gleich L - sm ist. Die letzte Adreßabbildungsgleichung für die Bankadressenzuweisung A im Rahmen der Speicherbankbenennug oder -zuweisung B und Zelladressen C wird durch die letzte Gleichung gegeben.
Diese Adreßabbildungsgleichung in der kombinatorischen mathematischen Schreibweiseise ist in die Schreibweise Boole'scher Logikgleichungen in Tabelle 40 konvertiert. Diese Tabelle gibt die Adreßschaltleitungen und Verbindungen für die Adreßleitungen CA zwischen dem AGEN 15 und dem Rahmenpuffer-Permutationsbitmappenspeicher 12 in Fig. 18 an. In der Figur 18 und dem begleitenden Text sind die Bankadreßzuweisungen A durch die Buchstaben CA bezeichnet, bezugnehmend auf die Bezeichnung als Zelladreßleitungen. Die Adreßleitungsbezeichnung CA ist abgeleitet von der fundamentalen Gleichung für A von Tabelle 40. In diesem Beispiel ist die grundlegende Graphikbilddateneinheit U das Quadratpixel oder Quadrat von vier horizontalen Bits, die Blockgröße beträgt 64·16 Bit, und die Indexgröße ist L = 4. Daher ist jede Variable ausgedrückt durch vier Indexbits i = [3 : 0]. Die Herleitung der Adreßgleichungen für A gemäß der Notation in linearer Permutationsmathematik und CA in der Schreibweise Boole'scher Gleichungen ist diagrammatisch in den Adreßdatenabbildungsflußelementen des AGEN 15 in Fig. 18 dargestellt. Von den verschiedenen Registern ist XCUR der Ursprung des momentalen X-Variablenwertes, DDH ist die Quelle des h-Parameters (repräsentiert durch H in Fig. 18 und Tabelle 40), SM ist die Quelle der statischen Modenparameternummer sm (gezeigt durch SM in Tabelle 40 und Fig. 18), ZCUR ist die Quelle des Bitwerts der momentanen Variablen Z und YCUR ist die Quelle des Indexbits der momentanen Variablen Y.
Die Arbeitsweise der Datengeneratorschaltkreiskomponente DGEN 22 entspricht der bisher beschriebenen mit der Ausnahme, daß der DGEN 22 von Fig. 18 im Datenfluß einer Blockorganisation in zwei Dimensionen B,A oder C,U bearbeitet.
Die Auswechsel-Linearpermutation Ep ist beispielhaft ausgeführt im DGEN 22 von Fig. 18 unter Verwendung der PRENET 110 und POST- NET 120 Schaltkreise, die beispielsweise die Auswechsel-LPNs der Fig. 16 und 17 umfassen. Bezüglich der DGEN-Dateneingabe 24 in das PRENET 110 ist das Eingabewort die permutierte Banknummerbezeichnung oder -zuweisung B und die Ausgabe des PRENET-Schaltkreise sind die Quadrate oder Quadratpixel in Koordinaten der normalisierten Graphikdateneinheitendimensionen. Der Zelladreßparameter oder -index C kann dann die Permutationskontrolle CON für das PRENET-Permutationsnetzwerk sein. Die Ausgabe der PRENET-Schaltkreise 110 geht in die DGEN-Register 112, 114 durch eine mögliche weitere Draht-Permutationsnetzwerktransformation gemäß der operierenden statischen Mode und den Permutationsbitmappen-Definitionsfunktionen. Daher kann angenehmerweise die PCON-Kontrolle für das PRENET-Permutationsnetzwerk 110 einfach die Zelladresse C bezüglich der Operation des DGEN 22 mit den Rahmenpuffer-speicherpermutationsbitmappen sein. Für Operationen von DGEN 22 mit einer Rahmenpufferspeicher-Standardbitmappe ist die PCON-Kontrolle gleich null. Die Quadratpixeleinheitenkoordinaten U werden daher als Funktionen der Speicherbankbezeichnungen B und Zelladressen von den fundamentalen Gleichungen hergeleitet.
U = Ep(B,C) PCON = C.
Der POSTNET-Ausgabepermutationsschaltkreis 120 ist die Inversion des PRENET-Schaltkreises 110. Die POSTNET-LPN-Schaltkreise bilden die Auswechselinversion des fundamentalen Theorems, nämlich:
B = Ep(U,C) PCON = C.
Daher ist die Eingabe in die POSTNET-Permutationsschaltkreise 120 aus der Ausgabe des Multiplexers 124 in den normalisierten Einheiten der Dimensionskoordinaten U des Quadratpixels. Die Ausgabe erfolgt in den permutierten Speicherbankzuweisungskoordinaten B zur Rückgabe an die Rahmenpufferspeicherpermutationsbitmappe. Der POSTNET-Kontrollindex PCON kann in ähnlicher Weise die Zelladresse C für die Permutation sein, von der die Speicherbankkoordinaten B als eine Funktion von C und U abgeleitet werden. Während das PCON-Permutationskontrollsignal die Zelladresse C für die Operation des DGEN mit Rahmenpufferpermutationsbitmappen sein kann, ist das Kontrollsignal für Standardbitmappen gleich null.
Für Vektorenoperationen wird der Permutationskontrollindex PCON [3 : 0] abgeleitet unter Verwendung der Zustandsinformation in den DGEN-Registern. Für alle Operationen (einschließlich der Auffrischung) ist der PCON-Parameter abgeleitet von der Zustandsinformation im AGEN und wird an den DGEN übertragen als ein Teil der DOPBUS-Anweisung. Das Schema zur Ableitung von PCON aus der fundamentalen Theorem-Gleichung ist dasselbe in beiden Fällen:
U = Ep(B,C) und B = Ep(U,C)
Die Gleichungen zur Ableitung von PCON für eine PBM sind wie folgt:
PCON = C
= CAO
= Qp(X,h,XZ)
Für eine SBM, PCON = 0.
Die DGEN-Register, die benutzt werden, die Permutationskontrollindexsignale PCON im Fall von Vektoroperationen zu bilden, sind wie folgt:
XDST [5 : 2] ergänzt den X-Index
YDST [3 : 0] ergänzt den Y-Index
ZDST ergänzt das Z-Bit für DSM = 1 oder sm = 1 Operationen
DDH [2 : 0] ergänzt den h-Parameter.
DGEN bearbeitet aufeinanderfolgende 32-Bit Worte oder "Züge" zur Bildung der vollständigen 64-Bit Zelle. PRENET und POSTNET operieren daher mit aufeinanderfolgenden 32-Bit Zügen, wobei Abfolgeregeln die Anordnung der Züge so behandeln, daß sie konsistent mit der Permutationsübersetzung sind. Diese Regeln sind wie folgt:
1. Die Speicherkontrolle liest und schreibt die Züge immer in numerisch ansteigender Ordnung unabhängig vom Permutationskontrollwert PCON.
2. DGEN lädt die unteren oder oberen 32 Bit eines Registers in der Ordnung, welche durch PCON wie folgt definiert ist:
a. Wenn PCON gleich 0 ist, wird der erste Zug gespeichert (oder gelesen von) den unteren 32 Bit, und der zweite Zug bearbeitet die oberen 32 Bit eines Registers.
b. Wenn PCON gleich 1 ist, wird der erste Zug gespeichert (oder gelesen von) den oberen 32 Bit, und der zweite Zug bearbeitet die unteren 32 Bit eines Registers. Diese Regeln basieren auf der XOR-Eigenschft der PCON-Bits.
Im Beispiel der Fig. 18 und Tabelle 40 sind die Bezeichnungen für die Adreßleitungen für A, bezeichnet CA, zu den acht physikalischen Speicherbanken (16 logischen Speicherbanken) durch zwei Indexbits ji, gefolgt, z. B. CAji. Die erste Indexbitnummer j ist die "Zug"-Nummer 0 oder 1, während die zweite Bitnummer i die variable Bitnummer i [3 : 0] ist und ein bestimmtes der vierkomponentigen Bits der Variable spezifiziert. Dies ist nicht zu verwechseln mit den Adreßleitungsbezeichnungen Ay und Az oder AY und AZ von Fig. 11 und Tabellen 28, 31, 33, 35, 37 und 33, in denen die Variablen AY und AZ durch zwei Indexbits &ijlig; gefolgt werden, z. B. AY&ijlig; und AZ&ijlig;, wobei die erste Indexbitnummer i die variable Bitnummer i [3 : 0] und die zweite Bitnummer j die "Zug"-Nummer 0 oder 1 ist.

TABELLE 1

BLOCK EINER ZYKLISCHEN PERMUTATIONSBITMAPPE MIT AUFTEILUNGEN, DIE DREI UNTERSCHIEDLICHE ZELL- KONFIGURATIONSADRESSIERUNGSMODEN DARSTELLEN

TABELLE 2

Definition des Rotations- oder zyklischen LPN, Cp Ein logischer Linear-Permutationsoperator

Definition:

Cp(X,Y) = (X + Y) mod L
X,Y, sind Operanden oder Indexvariablen
i = Indexbitnummer = L - 1, . . . , 1, 0
L ist die Anzahl von Indexbits der Indexvariablen
+ ist der Additionsoperator

Beispiel:

Wenn: Xi = X&sub3;,X&sub2;,X&sub1;,X&sub0;
Yi = Y&sub3;,Y&sub2;,Y&sub1;,Y&sub0;
L = Anzahl der Indexbits der Variablen = 4
i = 3, . . . , 0
Dann: Cp(X&sub1;,Y&sub1;) = {(X&sub1; + Y&sub1;) mod 4}i

Inversion:

Cp (-X,Cp(X,Y)) = Y
Da: -X + (X + Y) = Y

TABELLE 3

Blatt 1 von 2

Definition von Multiplexschalter LPN, Qp, Ein Hybridlinearpermutationsoperator

Definition:

Qp (X,h,Y)&sub1; : Yi für i < h
= Xi für i ≥ h
i = Indexbitnummer
X,Y, sind Operanden oder Indexvariablen
h = Schalterschwellparameter

Beispiele:

1) Xi = X&sub3;,X&sub2;,X&sub1;,X&sub0;
Yi = Y&sub3;,Y&sub2;,Y&sub1;,Y&sub0;
i = Indexbitnummer
L = Nummer von Indexbits der Indexvariablen = 4
h = 2
Qp (X,2,Y) - (X&sub3;,X&sub2;,Y&sub1;,Y&sub0;)
2) For A = Qp(B,h,C):

TABELLE 3

Blatt 2 von 2

Paaroperationsdefinitionen und Paaroperations- Umkehrbeweis:

If
Wenn X =Qp(A,h,B)
Y = Qp(B,h,A)
Then
dann A = Qp(X,h,Y)
B = Qp(Y,h,X)

Andere brauchbare Eigenschaften:

Qp(X,h,Qp(Y,h,Z) = Qp(X,h,Z)
Qp(Qp(X,h,Y),h,Z) =Qp(X,h,Z)
Qp(C,h,C) = C
Ep(Qp(X,h,Y),Z) = Qp(Ep(X,Z),h,Ep(Y,Z))

TABELLE 4

Definition der Auswechsel-LPN, Ep, Ein logischer Linearpermutationsoperator

Definition

Ep(X,Y)i = Xi Yi
= XOR a a = 0
a A = 1
X,Y sind Operanden oder Indexvariablen
i = Indexbitnummer = L - 1, . . . , 0
L = Anzahl von Indexbits oder Indexvariablen

Umkehrbeweis:

Ep(X,Ep(X,Y)) = Y

Inversion:

Wenn X = Ep(Y,Z)
Dann Y = Ep(X,Z)
Und Z = Ep(Y,X)

Andere nützliche Eigenschaften

Ep((R,X) = X
Ep(X,X) = R
Rp(Ep(X,Y)) = Ep(Rp(X),Rp(Y))
R = Indexvariable mit allen Indexbitwerten null

TABELLE 5

AUFTEILUNGSTABELLE BC = f(XW) FÜR AM40

TABELLE 6

AUfTEILUNGSTABELLE BC = f(XW) FÜR AM04

TABELLE 7

AUFTEILUNGSTABELLE BC = f(XW) FÜR AM22

TABELLE 8

AUFTEILUNGSTABELLE BC = f(XW) FÜR AM13

TABELLE 8A

AUFTEILUNGSTABELLE BC = f(XW) FÜR AM31

TABELLE 9

Definition des Umkehrr-LPN, Rp, Ein Draht- Linearpermutationsoperator

Definition

Rp(Xi) = X(L-i-1) = Xi,
wobei i' = L-i-1
i = Indexbitnummer
L = Anzahl der Indexbits i
L = Konstanter Koeffizient
X = Operand oder Indexvariable

Beispiel

Wenn L = 4 und i = 0
Dann i' = 3 und Rp(X&sub0;) = X&sub3;
Wenn L = 4 und i = 1
Dann i' = 2 und Rp(X&sub1;) = X&sub2;
Allgemein für L = 4:

Umkehrbeweis:

Rp(Rp(Xi)) = Xi

TABELLE 10

Zelladressierungsmoden

(hups Schreibweise)

Typ hups Gebrauch

TABELLE 11

AUfTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 0 AM4000

TABELLE 12

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 0 AM3100

TABELLE 13

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 0 AM2200

TABELLE 14

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 0 AM1300

TABELLE 15

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 0 AM0400

TABELLE 16

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 1 AM3011

TABELLE 17

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 1 AM2111

TABELLE 18

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 1 AM1211

TABELLE 19

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 1 AM0311

TABELLE 20

Blatt 1

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 2 AM4002

TABELLE 20

Blatt 2

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 2 AM4002

TABELLE 21

Blatt 1

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 2 AM3012

TABELLE 21

Blatt 2

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 2 AM3012

TABELLE 22

Blatt 1

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 2 AM2022

TABELLE 22

Blatt 2

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 2 AM4002

TABELLE 23

Blatt 1

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 2 AM1122

TABELLE 23

Blatt 2

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 2 AM1122

TABELLE 24

Blatt 1

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 2 AM0222

TABELLE 24

Blatt 2

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 2 AM0222

TABELLE 25

Blatt 1 von 2

AUFTEILUNGSTABELLE BCS = f(XYZ) FÜR sm = 3 AM1033

TABELLE 25

Blatt 2 von 2

TABELLE 26

FUNDAMENTALE GLEICHUNGEN UND AUSGANGSGLEICHUNGEN

GRUNDLEGENDE DEFINITIONSGLEICHUNG

(L = h + v + p)

AMhvp Moden

Ys = Sp(sm,Rp(Y))
Zr = Rp(Z)
B = Ep(X,Ep(Ys,Zr))
Ay = Ys
Az = Zr
X = Ep(B,Sp(Ay,Az))
Ys = Ay
Zr = Az
C = Qp(X,h,Ys)
U = Qp(Qp(Zr,L-p,Ys),h,X)
S = Qp(Ys,L-p,Zr)
X = Qp(C,h,U)
Ys = Qp(Qp,Qp,S,L-p,U),h,C))
Zr = Qp(Qp,U,L-p,s)
Ucs = Ep(B,Zp(C,S))
Ay = Qp(Qp,S,L-p,Ucs),h,C)
Az = Qp(Ucs,L-p,S)

TABELLE 26A

PERMUTATIONSGLEICHUNG FÜR EIN SYSTEM MIT DREI BLOCKDIMENSIONEN, STATISCHE TRANSFORMATION VON DREI PIXELDIMENSIONEN UND EINER MIXTUR VON PERMUTATIONSBITMAPPEN (PBMs) UND STANDARD- BITMAPPEN (SBMs).

PBM TRANSFORMATION:

Wy = Sp(sm,Rp,Y)) = Qp(Qp(Cz,p',U),h,Cy)
Wz = Rp(Z= = Qp(U,p',Cz)
B = Ep(x,Sp,Wy,Wz) = Ep(U,Ep(Cy,Cz))
Ay = Wy = Qp(Qp(Cz,p',Ep(B,Ep(Cy,Cz))),h,Cy)
Az = Wz = Qp(Ep(B,Ep(Cy,Cz)),p',Cz)
U = Qp(Qp(Wz,p',Wy),h,X)
Cy = Qp(X,h,Wy)
Cz = Qp(Wy,p',Wz) p' = L - p
X = Qp(Cy,h,U)

SBM TRANSFORMATION:

B = U = Qp(Wz,p',X)
Ay = Cy = Qp(X,p',Wz)
Az = Cz = Qp(Wy,p',Wz)

TABELLE 27

Definition von Schieber-Linearpermutations- Netzwerk Sp, Ein Draht-LPN

Definition:

Sp(S,Xi) = X(i + s)mod L = Xi,
wobei i = Indexbitnummerwert
i' = (i + s) mod L
s = Schieberphasenverschiebung
L = Anzahl von Indexbits i

Beispiele:

s = i und L = 4
s = 2 und L = 4
s = 3 und L = 4

Umkehrbeweis:

Sp(-s,Sp(S,Xi)) = Xi
Sp(0, Xi) = Xi
Sp(L, Xi) = Xi

TABELLE 28

ADRESSIERUNGSGLEICHUNGEN

SPEICHERBANKADRESSVERBINDUNGEN:

H = h HLT = "h kleiner als"
P = p PLT = "p kleinen als"
+ = "OR"
= "XOR"
LEERZEICHEN = "AND"
' = "NOT"

TABELLE 29

GÜLTIGE ADRESSMODEN BEI GEGEBENER STATISCHER MODE SM:

Mode sm
Y = gültige Adreßmode unter Angrenzungserfordernis TABELLE 30
SM Mode
? = Erfüllt nicht das Angrenzungserfordernis

TABELLE 31

Statische Mode sm = 0
Externe Adreßgleichungen für p < = sm:
H = h HLT = "h kleiner als"
= XOR TABELLE 32
SM Mode
? = Erfüllt nicht das Angrenzungserfordernis

TABELLE 33

Statische Mode sm =1
EXTERNE ADRESSGLEICHUNGEN FÜR p < = sm:
H = h HLT = "h kleiner als"
p = p PLT = "p kleiner als
+ = "OR"
= "XOR"
' = "NOT"
LEERZEICHEN = "AND" TABELLE 34
SM Mode
? = Erfüllt nicht das Angrenzungserfordernis

TABELLE 35

Statische Mode sm = 2
EXTERME ADRESSGLEICHUNGEN p < = sm:
H = h HLT = "h kleiner als"
p = p PLT = "p kleiner als"
+ = "OR"
= "XOR"
' = "NOT"
LEERZEICHEN = "AND" TABELLE 36
SM Mode
? = Erfüllt nicht das Angrenzungserfordernis

TABELLE 37

Statische Mode = sm = 3
EXTERNE ADRESSGLEICHUNGEN FÜR p < = sm:
H = h HLT = "h kleiner als"
P = p PLT = "p kleiner als"
+ = "OR"
= "XOR"
' = "NOT"
LEERZEICHEN = "AND" TABELLE 38
SM Mode
? = Erfüllt nicht das Angrenzungserfordernis

TABELLE 39

Statische Mode sm = 4
EXTERNE ADRESSGLEICHUNGEN FÜR
H = h HLT = "h kleiner als"
P = p PLT = "p kleiner als"
+ = "OR"
= "XOR"
' = "NOT"
LEERZEICHEN = "AND"

TABELLE 40

Die CA0 [3 : 0] und CA1 [3 : 0] Felder der AGEN Ausgabeadresse:
H = h HLE = h kleiner oder gleich
SM = sm SM' = L - sm
∂ = "AND" CA = A
! = "OR"
= "XOR"
' = "NOT"

Claims

1. Eine Rastergraphikmaschine mit einem Rahmenpufferspeicher (12), umfassend eine Bitmappe für das Speichern von graphischen Bilddaten unter Rahmenpufferspeicheradressen in Korrelation mit Pixelpositionen einer Rasterwiedergabesichtoberfläche (25) und einen Rahmenpufferadreßschaltkreis für das Adressieren des Rahmenpufferspeichers und wobei der Rahmenpufferspeicher (12) eine Mehrzahl von separat adressierbaren Speicherbänken B umfaßt mit Speicherbankadreßstellen A, wobei ein Adreßschaltkreis (15, 20) jede Speicherbank des Rahmenpufferspeichers in einem Speicherzugangszyklus adressiert, welche Rahmenpufferspeicher- Bitmappe Speicherbankadreßstellen umfaßt in Korrelation mit Pixelpositionen der Rasterwiedergabesichtoberfläche und wobei der Rahmenpufferadreßschaltkreis aufgebaut ist zum Empfang von graphischen Bilddatenadressen, organisiert in einem zweidimensionalen Betrachter-X,Y- Koordinatensystem entsprechend den Pixelpositionen auf der Rasterwiedergabesichtoberfläche, welcher Rahmenpufferadreßschaltkreis ferner umfaßt:

logische lineare Permutationsnetzwerkmittel (LPN), umfassend ein lineares Austauschpermutationsnetzwerk Ep, das wie folgt definiert ist:

Ep (X,Y)i= Xi Yi

wobei EXKLUSIV-ODER bedeutet, d. h. a a = 0 a = 1

X,Y Operanden oder Indexvariable sind

i = Indexbitnummer = L - 1, . . . , 0

L = Zahl von Indexbits der Indexvariablen

für logische lineare Permutation der graphischen Bilddatenadressen in dem Betrachter-X,Y-Koordinatensystem zu Adressen in einem B,A-Koordinatensystem von designierten Speicherbänken B und Speicherbankadreßstellen A des Rahmenpufferspeichers (12), wobei das B,A-Koordinatensystem eine logische lineare Permutation des Betracher-X,Y-Koordinatensystems umfaßt, welches B,A-Koordinatensystem eine logische lineare Permutationsbitmappe (PBM) umfaßt, die adressierbar ist durch den Rahmenpufferadreßschaltkreis (15, 20) in mehr als drei unterschiedlichen Adressiermoduszellkonfigurationen, wobei eine Mehrzahl der Adressiermoduszellkonfigurationen zweidimensionalen Zellen in dem Betrachter-X,Y-Koordinatensystem entspricht.

2. Die Rastergraphikmaschine nach Anspruch 1, bei der die rahmenpufferadreßschaltkreisdesignierte Speicherbank B in dem B,A-Koordinantensystem eine Funktion sowohl von X als auch von Y in dem X,Y-Koordinatensystem ist mit einer funktionalen Beziehung der Form

B = f&sub1; (X, f&sub2; (Y))

worin die Funktionen f&sub1; tund f&sub1; LPNs sind und zumindest eine der Funktionen f&sub1; und f&sub2; logische Austausch-LPN umfaßt, wobei Ep definiert ist wie folgt:

Ep (X,Y)i = Xi Yi

wobei EXKLUSIV-ODER bedeutet, d. h. a a = 0 a = 1

X,Y Operanden oder Indexvariable sind

i = Indexbitnummer = L - 1, . . . , 0

L = Zahl von Indexbits der Indexvariablen.

3. Die Rastergraphikmaschine nach Anspruch 2, bei der B eine Funktion von X und Y ist wie folgt:

B = Ep(X, Rp(Y))

worin Ep die Austausch-LPN ist, definiert wie folgt:

Rp(Xi) = X(L-i-1) = Xi

worin i' = L-i-1

i = Indexbitnummer

L = Nummer von Indexbits i

L = Modul

X = Operand oder Indexvariable.

4. Die Rastergraphikmaschine (10) nach Anspruch 1, bei der der Rahmenpufferadreßschaltkreis (15, 20) aufgebaut ist zum Organisieren der logischen linearen Permutationsbitmappe (PBM) des Rahmenpufferspeichers (12) in eine Mehrzahl von Blöcken (60) gleicher Zahl von Speicherbankadreßstellen entsprechend Blöcken gleicher Zahlen von Pixeln der Rasterwiedergabesichtoberfläche, welcher Adreßschaltkreis ferner die Blöcke (60) in eine Mehrzahl unterschiedlicher Sätze einer gleichen Zahl von Zellen (62, 64, 66) organisiert mit gleichen Zahlen von Speicherbankadreßstellen in jeder Zelle, wobei ein Satz von Zellen jeder Adressiermoduszellenkonfiguration entspricht, jeder Satz von Zellen nichtüberlappenden Zellen gleicher Zahlen von Pixeln auf der Rasterwiedergabesichtoberfläche entspricht, jede Zelle eine gleiche Zahl von Einheiten (61, 65, 67, 63) von graphischen Bilddaten von den Rahmenpufferspeicherbankadreßstellen umfaßt, eine Einheit von graphischen Bilddaten von jeder Speicherbank.

5. Eine Rastergraphikmaschine (10) mit einem Rahmenpufferspeicher (12), umfassend eine Bitmappe für das Speichern graphischer Bilddaten unter Rahmenpufferspeicheradressen in Korrelation mit Pixelpositionen einer Rasterwiedergabesichtoberfläche (25) und einen Rahmenpufferadreßschaltkreis für das Adressieren des Rahmenpufferspeichers und wobei der Rahmenpufferspeicher (12) eine Mehrzahl von separat adressierbaren Speicherbänken B mit Speicherbankadreßstellen AY, AZ umfaßt, organisiert in eine Mehrzahl von Bitebenen (50, 51, . . . 50N), wobei der Adreßschaltkreis jede Speicherbank des Rahmenpufferspeichers in einem Speicherzugriffszyklus in Zugriff nimmt, wobei die Rahmenpufferbitmappe Speicherbankadreßstellen umfaßt in Korrelation mit Pixelpositionen einer Rasterwiedergabesichtoberfläche, wobei jede Ebene des Rahmenpufferspeichers Speicherbankadreßstellen umfaßt für das Speichern eines Bits pro Pixel der Rasterwiedergabesichtoberfläche in jeder Ebene und wobei der Rahmenpufferadreßschaltkreis aufgebaut ist zum Empfang von graphischen Bilddatenadressen, organisiert in einem dreidimensionalen Betrachter-X,Y,Z-Koordinatensystem von horizontalen Zeilen in der X-Koordinatenrichtung und vertikalen Spalten in der Y-Koordinatenrichtung entsprechend den Pixelpositionen auf der Rasterwiedergabesichtoberfläche, welches Benutzer-X,Y,Z-Koordinatensystem ferner eine Bittiefendimension Z umfaßt entsprechend den Ebenen des Rahmenpufferspeichers, welcher Rahmenpufferadreßschaltkreis ferner umfaßt:

logische lineare Permutationsnetzwerkmittel PLN, umfassend mindestens zwei Austausch-LPNs Ep, definiert wie folgt

Ep (X,Y)i = Xi Yi

wobei EXKLUSIV-ODER bedeutet, d. h. a a = 0 a = 1

X,Y Operanden oder Indexvariable sind

i = Indexbitnummer = L - 1, . . . , 0

L = Zahl von Indexbits der Indexvariablen

für lineare Permutation der graphischen Bilddatenadressen in dem Betrachter-X,Y,Z-Koordinatensystem zum Adressieren in einem B,AY,AZ-Koordinatensystem von designierten Speicherbänken und Speicherbankadreßstellen AY, AZ des Rahmenpuffers, welches B,AY,AZ-Koordinatensystem eine logische lineare Permutation des Benutzer-X,Y-Koordinatensystems umfaßt, wobei das B,AY,AZ-Koordinatensystem eine logisch lineare Permutationsbitmappe (PBM) umfaßt, adressierbar durch den Rahmenpufferadreßschaltkreis mit mehr als drei unterschiedlichen Adressiermoduszellkonfigurationen, wobei eine Mehrzahl der Adressiermoduszellkonfigurationen den dreidimensionalen Zellen in dem Betrachter-X,Y,Z-Koordinatensystem entspricht.

6. Die Rastergraphikmaschine nach Anspruch 5, bei der die dem Rahmenpufferadreßschaltkreis designierte Speicherbank B in dem B,AY, AZ-Koordinatensystem eine Funktion von X,Y und Z in dem Betrachter-X,Y,Z-Koordinatensystem ist mit einer funktionellen Beziehung der Form:

B = f&sub1; (X,f&sub2;(Y,Z)

worin f&sub1; und f&sub2; Funktionen sind, umfassend Logikaustausch-LPNs Ep, definiert wie folgt:

Ep (X,Y)i = Xi Yi

wobei EXKLUSIV-ODER bedeutet, d. h. a a = 0 a = 1

X,Y Operanden oder Indexvariable sind

i = Indexbitnummer = L - 1, . . . , 0

L = Zahl von Indexbits der Indexvariablen.

7. Die Rastergraphikmaschine nach Anspruch 6, bei der B eine Funktion von X, Y und Z wie folgt ist:

B = Ep(X,EpRp (Y,Z))

worin Ep die Austausch LPN ist, definiert wie folgt:

Ep (X,Y)i = Xi Yi wobei EXKLUSIV-ODER bedeutet, d. h. a a = 0 a = 1

X,Y Operanden oder Indexvariable sind

i = Indexbitnummer = L - 1, . . . , 0

L = Zahl von Indexbits der Indexvariablen

und Rp die reverse LPN ist, definiert wie folgt

Rp(Xi) = X(L-i-1) = Xi,

worin i' = L-i-1

i = Indexbitnummer

L = Nummer von Indexbits i

L = Modul

X = Operand oder Indexvariable.

8. Der Rahmenpufferadreßschaltkreis nach Anspruch 7, bei dem B eine Funktion von X, Y und Z wie folgt ist:

B = Ep(X,Ep(Ys,Zr))

worin

Zr = Rp(Z) und

Ys = Sp(sm, Rp(Y))

worin

Sp die Schiebelinie LPN ist, definiert wie folgt:

Sp(s,Xi) = X(i + s)mod L = Xi,

worin

i = Indexbitzahlwert

i' = (i + s) mod L

s = Schiebephasenverschiebung

L = Zahl von Indexbits i,

Rp die reverse Linien-LPN ist, definiert wie folgt:

Rp(Xi) = X(L-i-1) = Xi,

worin i' = L-i-1

i = Indexbitnummer

L = Nummer von Indexbits i

L = Modul

X = Operand oder Indexvariable

und worin sm der statische Adressiermodus ist.

9. Die Rastergraphikmaschine nach Anspruch 5, bei der der Rahmenpufferadreßschaltkreis aufgebaut ist zum Organisieren der logischen linearen Permutationsbitmappe (PBM) des Rahmenpufferspeichers in eine Mehrzahl von Blöcken gleicher Zahl von Speicherbankadreßstellen entsprechend Blöcken gleicher Zahl von Pixeln der Rasterwiedergabesichtoberfläche, wobei der Adreßschaltkreis ferner die Blöcke in eine Mehrzahl von unterschiedlichen Sätzen einer gleichen Zahl von Zellen organisiert mit gleichen Zahlen von Zellen mit gleichen Zahlen von Speicherbankadreßstellen in jeder Zelle, wobei ein Satz von Zellen jeder Adressiermoduskonfiguration entspricht, jeder Satz von Zellen nichtüberlappenden Zellen gleicher Zahlen von Pixeln auf der Rasterwiedergabesichtoberfläche entspricht, jede Zelle eine gleiche Zahl von Einheiten von graphischen Bilddaten von den Rahmenpufferspeicherbankadreßstellen umfaßt, eine Einheit von graphischen Bilddaten von jeder Speicherbank.

10. Die Rastergraphikmaschine nach Anspruch 9, bei der die logischen LPN-Mittel des Rahmenpufferadreßschaltkreises ein erstes lineares Permutationsfunktionsnetzwerk umfassen für die Transformation und lineare Permutation der graphischen Bilddatenadressen in dem X,Y,Z-Koordinatensystem in Adressen in einem abstrakten C,U,S-Koordinatensystem von dreidimensionalen Blockabschnitten S von gleicher Bitgröße und Konfiguration entsprechend den dreidimensionalen Blockabschnitten des X,Y,Z-Koordinatensystems, wobei Zellunterteilungen C der Blockabschnitte den Zelladressiermoduszellen entsprechen und nichtüberlappenden Zellen gleicher Zahlen von Pixeln auf der Rasterwiedergabesichtoberfläche entsprechen und graphische Bilddateneinheiten U, wobei jede Zelle eine gleiche Zahl dieser Einheiten umfaßt, welches C,U,S-Koordinatensystem eine erste logische Permutationsbitmappe (PBM) umfaßt, welches erste lineare Permutationsnetzwerk eine funktionelle Beziehung der Form umfaßt:

C,U,S, = f(X,Y,Z)

wobei f das paarweise logisch lineare Permutationsnetzwerk Qp umfaßt, definiert wie folgt:

Qp(X,h,Y)i = Yi für i < h

= Xi für i ≥ h

i = Indexbitzahl

X,Y, Operanden oder Indexvariablen

h = Schaltschwellenparameter

und worin die logischen LPN-Mittel ferner ein zweites lineares Permutationsfunktionsnetzwerk umfassen für lineare Permutation der graphischen Bilddatenadressen in dem abstrakten C,U,S-Koordinatensystem in Speicherbankadressen in dem B,AY,AZ-Koordinatensystem der designierten Speicherbänke B und Speicherbankadreßstellen AY des Rahmenpufferspeichers, wobei das B,AY,AZ-Koordinatensystem eine logische lineare Permutation des abstrakten C,U,S-Koordinatensystems umfaßt und wobei die funktionelle Beziehung der zweiten Transformation und linearen Permutation von der Form ist:

B,AY,AZ = g(C,U,S)

worin g das paarweise logische lineare Permutationsnetzwerk Qp und den logischen Austausch-LPN-Ep umfaßt, definiert wie folgt:

Ep (X,Y)i = Xi Yi

wobei EXKLUSIV-ODER bedeutet, d. h. a a = 0 a = 1

X,Y Operanden oder Indexvariable sind

i = Indexbitnummer = L - 1, . . . , 0

L = Zahl von Indexbits der Indexvariablen.

11. Die Rastergraphikmaschine (10) nach Anspruch 5, umfassend einen Datengeneratorschaltkreis (22), angekoppelt an den Rahmenpufferadreßschaltkreis (15, 20) und den Rahmenpufferspeicher (12) der rastergraphischen Maschine für Zugriff auf graphische Bilddaten in den Rahmenpufferspeicherbankadreßstellen für das Auffrischen der Rahmenpufferspeicherbankadreßstellen mit Vektorziehen und Rasteroperationen und für das Auffrischen der Rasterwiedergabesichtoberfläche mit dem Inhalt des Rahmenpufferspeichers, welcher Datengeneratorschaltkreis umfaßt: logische Präpermutations-LPN-Mittel (110) für logische lineare Permutation von graphischen Quellenbilddaten, entnommen den Rahmenpufferspeicherbankadreßstellen in dem permutierten B,AY,AZ-Koordinatensystem des Rahmenpufferspeichers für Normalisierung der Ordnung der graphischen Quellenbilddaten von einem PMB-Format entsprechend der logischen linearen Permutation von graphischen Quellenbilddaten in ein Betrachter-X,Y,Z-Koordinatensystem in ein Standardbitmappenformat (SBM) entsprechend den graphischen Quellenbilddaten in einem Betrachter-X,Y,Z-Koordinatensystem für das Etablieren eines gemeinsamen Koordinatensystems für graphische Quellenbilddaten und graphische Bestimmungsbilddaten in dem Betrachter- X,Y,Z-Koordinatensystem während Rasteroperationen; und

logische Postpermutations-LPN-Mittel (120) für logische lineare Permutation von graphischen Bestimmungsbilddaten, verarbeitet durch Rasteroperationen in das permutierte B,AY,AZ-Koordinatensystem für die Rückführung von verarbeiteten graphischen Bestimmungsbilddaten zu dem Rahmenpufferspeicher in dem permutierten Koordinatensystem, welche logischen Präpermutationsmittel (110) und Postpermutationsmittel (120) des Datengeneratorschaltkreises (22) lineare Austauschpermutationsnetzwerke Ep umfassen, definiert wie folgt:

Ep (X,Y)i = Xi Yi

wobei EXKLUSIV-ODER bedeutet, d. h. a a = 0 a = 1

X,Y Operanden oder Indexvariable sind

i = Indexbitnummer = L - 1, . . . , 0

L = Zahl von Indexbits der Indexvariablen

sowie reverse lineare Linienpermutationsnetzwerke Rp, definiert wie folgt:

Rp(X&sub1;) = X (L-i-1) = Xi,

worin i' = L-i-1

i = Indexbitnummer

L = Nummer von Indexbits i

L = Modul

X = Operand oder Indexvariable.

12. Die Rastergraphikmaschine (10) nach einem der Ansprüche 1 oder 5, bei der die Austausch-LPN Ep definiert ist wie folgt:

Ep (X,Y)i = Xi Yi

wobei EXKLUSIV-ODER bedeutet, d. h. a a = 0 a = 1

X,Y Operanden oder Indexvariable sind

i = Indexbitnummer = L - 1, . . . , 0

L = Zahl von Indexbits der Indexvariablen

implementiert wird durch reversible Boole'sche logische EXKLUSIV-ODER- oder EXKLUSIV-NICHT-ODER-Gatter.

13. Die Rastergraphikmaschine nach einem der Ansprüche 1 oder 5, bei der die Adressiermoduszellkonfigurationen des Rahmenpufferadreßschaltkreises eine horizontal orientierte zweidimensionale Zelle, eine vertikal orientierte zweidimensionale Zelle, eine im wesentlichen quadratische zweidimensionale Zelle und eine horizontale Wortmoduszelle umfassen.

14. Die Rastergraphikmaschine nach einem der Ansprüche 1 oder 5, ferner umfassend einen Datengeneratorschaltkreis (22) für das Auffrischen des Rahmenpufferspeichers (12) mit Vektorziehungs- und Rasteroperationen und für das Auffrischen einer Rasterwiedergabesichtoberfläche (25) mit dem graphischen Bilddateninhalt des Rahmenpufferspeichers (12), welcher Datengeneratorschaltkreis umfaßt:

erste logische LPN-Mittel, umfassend ein lineares Austauschpermutationsnetzwerk Ep, wie folgt definiert:

Ep (X,Y)i = Xi Yi wobei EXKLUSIV-ODER bedeutet, d. h. a a = 0 a = 1

X,Y Operanden oder Indexvariable sind

i = Indexbitnummer = L - 1, . . . , 0

L = Zahl von Indexbits der Indexvariablen

für logische lineare Permutation von graphischen Bilddaten, entnommen dem Rahmenpufferspeicher für die Normalisierung graphischer Bilddaten von einem PBM-Format entsprechend einer logischen linearen Permutation von graphischen Bilddaten in einem Betrachter-X,Y-Koordinatensystem in ein Standardbitmappenformat (SBM) entsprechend den graphischen Bilddaten in dem Betrachter-X,Y-Koordinatensystem für Rasteroperationen und für das Auffrischen einer Rasterwiedergabesichtoberfläche; und

zweite logische LPN-Mittel, umfassend ein lineares Austauschpermutationsnetzwerk Ep, definiert wie folgt

Ep (X,Y)i = Xi Yi

wobei A EXKLUSIV-ODER bedeutet, d. h. a a = 0 a = 1

X,Y Operanden oder Indexvariable sind

i = Indexbitnummer = L - 1, . . . , 0

L = Zahl von Indexbits der Indexvariablen

für logische lineare Permutation der normalisierten graphischen SBM-Formatbilddaten, verarbeitet gemäß den Rasteroperationen in dem Datengeneratorschaltkreis für die Rückführung zu dem Rahmenpufferspeicher (12) in einem PBM-Format.

15. Die Rastergraphikmaschine nach Anspruch 14, bei der die ersten und zweiten logischen LPN-Mittel des Datengeneratorschaltkreises (22) jedes ein lineares Austauschpermutationsnetzwerk Ep umfassen, definiert wie folgt:

Ep (X,Y)i = Xi Yi

wobei EXKLUSIV-ODER bedeutet, d. h. a a = 0 a = 1

X,Y Operanden oder Indexvariable sind

i = Indexbitnummer = L - 1, . . . , 0

L = Zahl von Indexbits der Indexvariablen

und eine reverse LPN, RP, definiert wie folgt:

Rp(Xi) = X(L-i-1) = Xi,

worin i' = L-i-1

i = Indexbitnummer

L = Nummer von Indexbits i

L = Modul

X = Operand oder Indexvariable.