DE69815389T2

DE69815389T2 - Hammingwertvergleichung für ungewogene bitfelder

Info

Publication number: DE69815389T2
Application number: DE69815389T
Authority: DE
Inventors: Beverley King
Original assignee: BAE Systems PLC
Current assignee: BAE Systems PLC
Priority date: 1997-12-19
Filing date: 1998-12-18
Publication date: 2003-12-11
Anticipated expiration: 2018-12-19
Also published as: EP1038215B1; EP1038215A1; JP2000517089A; EP1038215B9; ES2195432T3; AU1769799A; DE69815389D1; US6330702B1; WO1999032961A1; JP3587533B2

Description

Die Erfindung bezieht sich auf Verfahren und eine Vorrichtung zur Bestimmung der Hammingwerte von Binär-Vektoren oder -Feldern allgemein und insbesondere, aber nicht ausschließlich auf Verfahren und eine Vorrichtung zur Benutzung bei der Bestimmung der Hammingwert-Beziehung einer Gruppe von ungewogenen Bits, die hier sonst als ungewogene Tupels oder ungewogene Vektoren bezeichnet werden. Die Erfindung bezieht sich auch auf eine Vorrichtung und Verfahren zur Bestimmung der Hammingwert-Beziehung von zwei Thermometercodes ungewogener Vektoren. Die Erfindung bezieht sich weiter auf einen Hammingwert-Komparator zum Vergleich der Hammingwert-Beziehung zweidimensionaler Datenfelder. Die Erfindung bezieht sich außerdem auf Summierungs- und Schwellwert-Vorrichtungen, die Hammingwert-Komparatoren gemäß der Erfindung benutzen.
Die Vorrichtung und die Verfahren, die hier beschrieben werden, können in zweckmäßiger Weise in Verbindung mit irgendeiner Vorrichtung oder einem Verfahren benutzt werden oder diese benutzen, wie sie in unseren laufenden Patentanmeldungen WO99/33184, WO99/33019, WO99/33175 und WO99/32962 beschrieben sind, deren Inhalt hiermit zur Bezugnahme eingeführt wird.

Terminologie

Der Ausdruck "Hammingwert" wird benutzt, um die Zahl einer logischen 1'er-Gruppe in einem ein-dimensionalen Feld einer Binärzahl eines Tupel, eines Vektors oder von zwei- oder höheren dimensionalen Feldern zu definieren. Die Hammingwert- Beziehung von zwei binären Zahlen oder Feldern zeigt an, welche den größeren Hammingwert besitzt oder ob die Hammingwerte die gleichen sind.
Der Ausdruck "gewichtete Bits" wird im konventionellen Sinne benutzt, um anzuzeigen, dass aufeinanderfolgende Bit-Positionen gewichtet sind, insbesondere ... 16, 8, 4, 2, 1, obgleich andere gewichtete Repräsentationen möglich sind. "Ungewogene Bits" ist eine Gruppe von binären Zeichen 1 und 0, die jeweils gerade "1" bzw. "0" repräsentieren. Es gibt kein niedrigstwertiges Bit (LSB) oder höchstwertiges Bit (MSB). Die Gruppe von Bits kann geordnet oder ungeordnet stehen. Wenn sämtliche 1'er zusammen gruppiert sind, z. B. ([111000]), dann wird der Code als Thermometercode, als Thermocode oder als Balkengraphikcode bezeichnet, und sämtliche Ausdrücke werden hierbei kollektiv zusammengefasst unter dem Ausdruck "Thermometercode".
Der Ausdruck "Thermometercode" wird hierbei auch benutzt, um Felder zu beschreiben, wo Bit-Gruppen um ein vorbestimmtes Bit innerhalb des Tupel angehäufelt sind statt nach den Enden des Tupels angehäufelt zu sein. In gleicher Weise wird der Ausdruck auch benutzt, um das zweidimensionale Feld, das dreidimensionale Feld oder höhere Felder zu beschreiben, in denen die Bit-Gruppen um eine vorbestimmte fokale Bit-Stellung angehäufelt sind, die irgendwo innerhalb des Feldes liegen kann, z. B. an einer Ecke oder im Zentrum eines zwei- oder dreidimensionalen Feldes.
Eine Gruppe von ungewogenen Bits wird hierbei als "ungewogenes Tupel" oder "ungewogener Vektor" bezeichnet, und diese Ausdrücke sollen nicht auf geordnete Gruppen beschränkt sein.
In traditionellen Neuronennetzen wird ein synaptischer Echtwert mit einem synaptischen Verbindungswert oder einem gewichteten Wert multipliziert und mit anderen in gleicher Weise verarbeiteten Synapse-Werten summiert, bevor sie sämtlich summiert und auf einen Schwellwert gebracht sind, um einen Neuronenausgang zu schaffen. Der gewichtete Wert ist eine synaptische Echtwert- Verbindungs-Intensität und demgemäß die übliche Benutzung des Ausdrucks "gewichtetes Neuronennetz". Jedoch ist es ebenso möglich, Neuronennetze auf binärer RAM-Basis zu haben, die keine Echtwert-Verbindungs-Gewichte benutzen, sondern stattdessen auf Werten der binären Bits entweder auf 0 oder auf 1 beruhen. Demgemäß gibt es zwei Kontexte der Unausgewogenheit: ohne synaptische Verbindungs-Intensität und ohne binäre Code-Gewichtung. Die hier beschriebenen Anordnungen benutzen ungewogene binäre Manipulationsmechanismen und können benutzt werden, um ungewogene künstliche Neuronennetze zu entwerfen, die sonst als ungewogene künstlich ungewogene Neuronennetze bezeichnet werden.
Gemäß einem Merkmal bezieht sich die Erfindung auf den Vergleich von zwei ungewichteten Vektoren in Ausdrücken ihrer Hammingwerte. Dieses Verfahren ist größtenteils äquivalent zur Funktion eines binären Neurons. Wenn das Neuron einen Vektor A eines ungewogenen synaptischen Wertes (z. B. [10110010]) und einen Vektor T eines ungewogenen neutralen Schwellwertes (z. B. [00101000]) empfängt, dann kann das Neuron eine Aktivierung erfordern, wenn der Hammingwert von A größer ist als der Hammingwert von T. Bei diesem Beispiel kann der Schwellwert T als eine Gruppe von synaptischen Sperrwerten angesehen werden, die überschritten werden müssen, wenn das Neuron aktiviert werden muss. Dies ist ein besonderes Beispiel eines Umstandes, wenn es erforderlich ist, die Hammingwert-Beziehung zwischen zwei binären Vektoren zu bestimmen, aber sehr viel andere Systemtypen vorhanden sind, die diese oder eine ähnliche Verarbeitung erfordern. Beispielsweise kann dieser Vergleich und es können die anderen Techniken, die hier beschrieben sind, benutzt werden in Flugsteuersystemen, in Auswahlsystemen mit Redundanz, in kritischen Sicherheitssystemen, in Fernmeldesystemen, in Entscheidungssystemen und künstlichen Intelligenzsystemen, beispielsweise Neuronennetzen.
Bei einer bekannten Anordnung wird ein auf einer Zustandsmaschine basierendes System benutzt, um die Zahl der 1'er-Gruppen zu zählen, und digitale arithmetische Einheiten werden für den binären Vergleich benutzt. Für jeden ungewogenen Vektor wird jedes Bit aufeinanderfolgend abgetastet, und ein Zähler oder ein arithmetisches Register werden demgemäß inkrementiert, um den Hammingwert zu berechnen. Danach wird der Inhalt der jeweiligen Zähler oder arithmetischen Register verglichen, um die Hammingwert-Beziehung zu bestimmen. Diese bekannte Technik ist geeignet zur Durchführung mit einer Software unter Benutzung eines Mikroprozessors oder einer ähnlichen Zustandsmaschine.
Diese Technik ist jedoch langsam und anfällig gegenüber Leitfähigkeits-Störungen (RFI), da diese Technik grundsätzlich auf Taktgebern, Zählern und Mikroprozessoren beruht. Sowohl die Arbeitsgeschwindigkeit als auch die Unterbrechung oder Störung durch andere Störungen machen ein solches System nur schlecht geeignet für kritische Sicherheitssysteme, wie beispielsweise Flugsteuersysteme. Beispielsweise kann ein Flugsteuersystem schnelle Entscheidungen benötigen, basierend auf dem augenblicklichen "L"- oder "0"- Zustand verschiedener Wandler, die verschiedene Aspekte des Flugbetriebes vermitteln; eine Verstümmelung einer der Eingänge des die Entscheidung herbeiführenden Prozesses (verursacht beispielsweise durch Störung oder RFI- Unterbrechung) kann zu einer Fehlinterpretation eines der Eingänge führen mit der Folge, dass der die Entscheidung treffende Prozessor oder das Neuronennetz die falsche Entscheidung trifft, was potentiell katastrophale Konsequenzen nach sich ziehen kann.
Die GB-A-1,588,535 beschreibt eine Anordnung, bei der jeweils Datenwörter gesucht werden und die Hamming-Distanz zwischen einem Datenwort und einem Suchwort gemessen wird. Dabei ist zu bemerken, dass die Hamming-Distanz (d. h. die Zahl von Bits, in denen sich zwei Worte unterscheide) völlig unterschiedlich ist gegenüber dem Hammingwert-Vergleich, bei dem in typischer Weise bestimmt wird, welcher der beiden Binär-Vektoren oder Tupels die größte Zahl von logisch 1'er- Gruppen hat.
Demgemäß werden hier verschiedene Mechanismen beschrieben, um die Hammingwert-Beziehungen von zwei Binär-Vektoren zu bestimmen, und zwar unter Benutzung von asynchronen Boolean'schen logischen Bit-Zellen- Manipulationsschemen, die sehr schnell für kleine ungewogene Systeme sind. Außerdem neigen diese dazu, gegenüber einer Funkstörung (RFl-Störung) widerstandsfähiger als die gewichteten binären Alternativen zu sein und eine größere Fehlertoleranz als diese aufzuweisen.
Gemäß dem ersten beschriebenen Ausführungsbeispiel werden zwei ungewichtete binäre Vektoren zunächst getrennt in ein Thermometercode umgewandelt, und dann werden die Thermometercode durch einen Thermocode-Komparator verglichen, um die Hammingwert-Beziehung zu bestimmen.
Bei den beiden folgenden Schemen werden zwei ungewogene Vektoren parallel zueinander verglichen, ohne dass eine getrennte Umwandlung in einen Thermometercode erforderlich wäre, und sie werden danach verglichen. Jedoch können Thermometercode-Wandler und Thermocode-Komparator jeweils in verschiedenen Anwendungsfällen benutzt werden, und die Erfindung erstreckt auch auf diese an sich.
Gemäß einem Merkmal der Erfindung betrifft diese einen Hammingwert-Komparator, der einen Ausgang liefert, der die Hammingwert-Beziehung eines ersten ein- oder mehrdimensionalen ungewogenen Feldes ungewogener Bits und ein zweites ein- oder mehrdimensionales ungewogenes Feld ungewogener Bits anzeigt, wobei der Hammingwert eines gegebenen ungewogenen Feldes die Zahl der darin befindlichen logischen 1'er ist und die Hammingwert-Beziehung von zwei ungewogenen Feldern anzeigt, welches den größeren Hammingwert besitzt oder ob die Hammingwerte davon die gleichen sind,
wobei der Hammingwert-Komparator die folgenden Teile umfasst:
Mittel, die diese Bits aus den Feldern den Verarbeitungsmitteln liefern, die mehrere Schichten von (n + n)-Bit-Manipulationszellen aufweisen und jede Manipulationszelle einen ersten n-Eingang zum Empfang jeweiliger Bits entsprechend den jeweiligen Bits im ersten Feld und einen zweiten n-Eingang zum Empfang von Bits entsprechend den jeweiligen Bits in dem zweiten Feld hat, wobei ein erster n-Ausgang und ein zweiter n-Ausgang jeweils den ersten und zweiten n- Eingängen entsprechen,
wobei jede Manipulationszelle Logikmittel enthält, um wenigstens eine Bit- Verschiebeoperation und eine Bit-Eliminierungsoperation durchzuführen,
wobei die (n + n)-Bit-Manipulationszellen miteinander verbunden sind, indem die Ausgänge jeder Schicht abseits der Endschicht mit den jeweiligen Eingängen der nächsten oder der übernächsten Schicht durchgehend verbunden sind,
wobei in aufeinanderfolgenden Schichten die Bit-Gruppen am Ausgang der Bit-Manipulationszellen in aufeinanderfolgenden Schichten nach einer gemeinsamen Bit-Position relativ zu den Schichten wandern und die Endschicht einen Ausgang liefert, der die Hamming-Beziehung anzeigt.
Der Hammingwert-Komparator weist vorzugsweise Behandlungsmittel auf, die mehrere Schichten von Bit-Manipulationszellen umfassen, von denen jede mehrere Eingänge und mehrere Ausgänge aufweist und die Eingänge entsprechender Bits von jedem der beiden Binärfelder mit jeweiligen Eingängen der Bit- Manipulationszellen in der ersten Schicht der Verarbeitungsmittel verbunden sind und die Bit-Manipulationszellen miteinander verbunden sind, indem die Ausgänge jeder Schicht abseits von dem letzten nach den jeweiligen Eingängen der nächsten oder übernächsten Schicht durchgehen, wodurch ein Ausgang geliefert wird, der die Hammingwert-Beziehung angibt.
Der Komparator soll vorzugsweise in Verbindung mit ungewogenen Feldern oder Worten benutzt werden, aber seine Benutzung mit gewichteten Feldern oder Worten ist nicht auszuschließen.
Jede Bit-Manipulationszelle kann vier Eingänge und vier Ausgänge umfassen, wobei die Bit-Manipulationszellen in der ersten Schicht so angeordnet sind, dass für jede Bit-Manipulationszelle zwei Eingänge jeweils ein entsprechendes Bit von einem der Binärfelder empfangen und der andere der beiden Eingänge jeweils ein entsprechendes Bit von dem anderen Binärfeld empfängt.
Jeder der zwei Eingänge in den Bit-Manipulationszellen in der ersten Schicht empfängt vorzugsweise benachbarte Bits des entsprechenden Binärfeldes, genommen an einer geraden Begrenzung. Vorzugsweise bewirkt jede Manipulationszeile eine Einwirkung auf die Bits von erstem und zweitem Binärfeld, empfangen an den jeweiligen Eingängen, wodurch eine Bit-Gruppe in einer gemeinsamen Richtung verschoben wird und entsprechend positionierte Bit- Gruppen voll oder teilweise eliminiert werden. Demgemäß kann jede der Bit- Manipulationszellen eine Verschiebung und volle Eliminierung bewirken, wie dies in der folgenden Wahrheitstabelle (oder einer inversen Tabelle) beschrieben ist:
wobei AinL, AinR, BinL, BinR die vier Eingänge der Zeilen sind und AoutL, AoutR, BoutL, BoutR die vier Ausgänge dieser Zellen.
Stattdessen kann jede der Bit-Manipulationszellen eine Verschiebung und teilweise Eliminierung bewirken, wie dies in der folgenden Wahrheitstabelle oder einer hierzu inversen Tabelle angegeben ist:
Vorzugsweise hat jede Manipulationszelle folgende Teile: eine erste Mehrzahl von Eingängen zum Empfang der jeweiligen Bits von einem der Binärworte; eine zweite Mehrzahl von Eingängen zum Empfang der jeweiligen Bits von dem anderen der Binärworte; eine entsprechende Mehrzahl von Ausgängen; und eine Logikeinrichtung zur Ausgabe einer Bit-Gruppe an einem jeweiligen vorgewählten Ausgang, wenn der Hammingwert der Bits an der ersten Mehrzahl der Eingänge größer ist als der Hammingwert der Bits an der zweiten Mehrzahl von Eingängen.
Vorzugsweise hat die Bit-Manipulationszelle eine erste Mehrzahl von Eingängen zum Empfang der jeweiligen Bits von einem der Binärfelder und eine zweite Mehrzahl von Eingängen zum Empfang der jeweiligen Bits von dem anderen Binärfeld, wobei die Bit-Transformationsmittel eine entsprechende Vielzahl von Ausgängen aufweisen und eine Logikeinrichtung vorgesehen ist, um an einem vorgewählten Ausgang eine Bit-Gruppe auszugeben, wenn der Hammingwert der Bit-Gruppe an der ersten Mehrzahl von Eingängen größer ist als der Hammingwert der Bit-Gruppe an der zweiten Mehrzahl von Eingängen.
Gemäß einem bevorzugten Ausführungsbeispiel haben die Bit-Transformationsmittel eine erste Mehrzahl von Eingängen (AINL, AINR) zum Empfang der jeweiligen Bits von einem der Binärfelder und eine zweite Mehrzahl von Eingängen (BINL, BINR) zum Empfang der jeweiligen Bits von dem anderen Binärfeld, und die Bit- Transformationsmittel besitzen eine entsprechende Mehrzahl von Ausgängen (AOUTL, AOUTR, BOUTL, BOUTR), und die Logikmittel führen eine Boolean'sche Logikoperation durch, um an einem vorgewählten der Ausgänge eine Bit-Gruppe auszugeben, wenn die Zahl der logischen 1'er-Gruppe an der ersten Mehrzahl von Eingängen größer ist als der Hammingwert der Bit-Gruppe an der zweiten Mehrzahl von Eingängen.
Gemäß einem bevorzugten Ausführungsbeispiel betrifft die vorliegende Erfindung einen Hammingwert-Komparator zum Vergleich der Hammingwerte von 2 zweidimensionalen Feldern binärer Daten, und der Komparator umfasst mehrere Schichten von Bit-Manipulationszellen, und jede Zelle umfasst wenigstens zwei Eingänge und zwei Ausgänge und bewirkt eine Verschiebung der Bit-Gruppen nach einer vorbestimmten Bit-Position, und es ist eine Verbindung zwischen den Schichten vorgesehen, um wenigstens eine Bit-Verschiebung oder Bit-Eliminierung durchzuführen, wodurch ein Ausgang erhalten wird, der die Hammingwert- Beziehung der Felder anzeigt.
Die Erfindung betrifft auch ein Verfahren zur Bestimmung, ob, falls vorhanden, ein erstes ein- oder mehrdimensionales ungewogenes Feld ungewogener Bits oder ein zweites ein- oder mehrdimensionales ungewogenes Feld ungewogener Bits die größere Zahl von logischen 1'er darin aufweist, und das Verfahren umfasst die folgenden Schritte:
(i) es werden die Bits von den Feldern der Verarbeitungseinrichtung zugeführt, die mehrere Schichten von (n + n)-Bit-Manipulationszellen enthält, wobei jede Manipulationszelle einen ersten n-Eingang zum Empfang der jeweiligen Bits entsprechend den jeweiligen Bits in dem ersten Feld und einen zweiten n-Eingang zum Epfang von Bits entsprechend den jeweiligen Bits in dem zweiten Feld aufweist, wobei ein erster n-Ausgang und ein zweiter n-Ausgang entsprechend den ersten und zweiten n-Eingängen vorgesehen sind,
wobei jede Manipulationszelle Logikmittel aufweist, um wenigstens eine Bit- Verschiebungsoperation oder eine Bit-Eliminierungsoperation durchzuführen,
wobei (n + n)-Bit-Manipulationszellen verbunden sind, indem die Ausgänge jeder Schicht abseits der Endschicht auf jeweilige Eingänge der nächsten oder übernächsten Schicht durchgehen,
und wobei in aufeinanderfolgenden Schichten die Bit-Gruppen am Ausgang der Bit-Manipulationszellen nacheinander nach einer gemeinsamen Bit-Position relativ zu den Schichten wandern, wobei die Endschicht einen Ausgang liefert, der die Hamming-Beziehung anzeigt.
Die Erfindung wurde vorstehend beschrieben, und sie erstreckt sich auf jede erfinderische Kombination von Merkmalen, die sich aus der vorstehenden oder nachstehenden Beschreibung ergeben.
Die Erfindung kann auf verschiedene Weise durchgeführt werden, und nachstehend werden verschiedene Ausführungsbeispiele im Einzelnen beschrieben, wobei auf die beiliegenden Zeichnungen Bezug genommen wird, die die herkömmlichen Symbole für Logikschaltungen benutzen. In der Zeichnung zeigen:
Fig. 1 ist ein Schaltungsdiagramm eines ersten Ausführungsbeispiels eines ungewogenen binären Komparators gemäß der Erfindung zur Bestimmung der Hammingwert-Beziehung von zwei ungewogenen binären Vektoren;
Fig. 2(a) und 2(b) zeigen Schaltungsdiagramme von zwei der Bit- Manipulationszellen zur Benutzung in dem ungewogenen binären Komparator gemäß Fig. 1, und zwar eine Zelle zur Durchführung einer vollen Verschiebung und vollen Hamming-Eliminierung und die andere zur Durchführung einer teilweisen Verschiebung bzw. einer Hamming-Eliminierung;
Fig. 3 ist ein ausgearbeitetes Beispiel des ungewogenen binären Komparators nach Fig. 1, welches die Bit-Gruppen an den Eingängen und Ausgängen der Bit-Manipulationszellen gemäß dem Eingang von zwei typischen ungewogenen Binär-Vektoren zeigt;
Fig. 4 ist ein Schaltbild eines zweiten Ausführungsbeispiels eines ungewogenen Binär-Komparators gemäß der Erfindung zur Bestimmung der Hammingwert-Beziehung von zwei Binär-Vektoren;
Fig. 5 ist ein Schaltbild von einer der Bit-Manipulationszellen des ungewogenen Binär-Komparators gemäß Fig. 4 zur Durchführung einer vollen Verschiebung und einer teilweisen Hamming-Eliminierung;
Fig. 6 ist ein ausgearbeitetes Beispiel des ungewogenen Binär-Komparators nach Fig. 4, welches die Bit-Gruppen an den Eingängen und Ausgängen der Bit- Manipulationszellen gemäß dem Eingang von zwei typischen ungewogenen Binär- Vektoren zeigt;
Fig. 7 ist ein Schaltbild einer 2 · 2-Manipulationszelle zur Durchführung einer Verschiebung und Hamming-Eliminierung;
Fig. 8 ist ein Schaltbild einer 2 · 4-Manipulationszelle zur Durchführung einer Verschiebung und einer Hamming-Elimination;
Fig. 9 ist ein Schaltbild eines Feldes von Manipulationszellen gemäß Fig. 8, welche einen Hammingwert-Komparator bilden, der zwei ungewogene 12-Bit- Eingänge vergleicht;
Fig. 10 ist ein ausgearbeitetes Beispiel eines Feldes von Fig. 11;
Fig. 11 ist ein weiteres Beispiel eines Hammingwert-Komparators zum Vergleichen von zwei ungewogenen 8-Bit-Eingängen;
Fig. 12 ist in größerem Maßstab eine Ansicht eines Teils von Fig. 11 zur Erläuterung von dessen Struktur;
Fig. 13 ist in größerem Maßstab eine Ansicht des Rückend-Dekoders, der bei dem Ausführungsbeispiel nach Fig. 11 benutzt wird;
Fig. 14 ist eine schematische Darstellung der ungeraden und der geraden Schichten und der Zellennummer-Identifizierung, die bei einer planaren Hammingwert-Komparator-Struktur benutzt wird;
Fig. 15 ist ein Diagramm einer 2 · 2-Bit-Manipulationszelle, die bei dem Ausführungsbeispiel der planaren Hammingwert-Komparator-Struktur gemäß Fig. 14 benutzt wird;
Fig. 16 ist ein Diagramm einer 2 · 4-Bit-Manipulationszelle zur Benutzung bei dem Ausführungsbeispiel des planaren Hammingwert-Komparators nach Fig. 14;
Fig. 17 und 18 sind ausgearbeitete Beispiele des planaren Hammingwert- Komparators gemäß Fig. 14; und
Fig. 19 ist ein Diagramm der Summierungs- und Schwellwert- Bildungseinrichtung (SAT), die durch einen Hammingwert-Komparator wie oben beschrieben konstruiert werden kann.

BESCHREIBUNG VON BEVORZUGTEN AUSFÜHRUNGSBEISPIELEN

Hammingwert-Komparator für Thermometercodes

Hammingwert-Komparator für ungewogene Tupels

Im Folgenden wird zunächst auf die Fig. 1 bis 6 Bezug genommen. Hier wird die Hammingwert-Beziehung von zwei ungewogenen N-Tupel-Vektoren unter Benutzung eines einzigen Komparators bestimmt. Bei beiden Ausführungsbeispielen wird eine modulare Bit-Manipulationszelle mit vier Eingängen und vier Ausgängen definiert, um auf zwei Elemente von jedem der N-Tupels A und B einzuwirken, und diese Manipulationszellen sind in einer Architektur aufgebaut, die den erforderlichen Vergleich parallel zueinander durchführt.
Zunächst wird auf das Ausführungsbeispiel nach Fig. 1 und 2 Bezug genommen. Jede der Bit-Manipulationszellen 22 besitzt vier Eingänge und vier Ausgänge. In der Eingangsschicht und über das Netzwerk sind zwei Eingänge einer jeden Zelle 22 mit Ziffern des A-Vektors und zwei Eingänge mit Ziffern des B-Vektors verknüpft. In Fig. 1 sind, wie dargestellt, die unteren zwei Eingänge einer jeden Zelle 22 dem A-Vektor zugeordnet, und die oberen zwei Eingänge sind dem B-Vektor zugeordnet.
Aus Fig. 1 ist ersichtlich, dass die Zahl der Bit-Manipulationszellen 22 in jeder Lage sich zwischen gerade und ungerade ändert, obgleich die siebente und die folgenden Stufen gestützt sind, weil die relevanten Ausgänge von einer einzigen Manipulationszelle 22 in der Endstufe abgenommen werden, und so werden die Bit- Manipulationszellen, die durch Stützung entfernt werden, redundant, da diese Zellen nichts zu dieser einzigen Manipulationszelle beitragen würden. Die Verbindungen zwischen den Bit-Manipulationszellen 22 in benachbarten Lagen sind derart gestaffelt, dass, abgesehen von der Eingangslage, jede Bit-Manipulationszelle 22 jeweils Eingänge von zwei Bit-Manipulationszellen in entweder einer oder zwei vorherigen Lagen empfängt, je nachdem, ob die Bit-Manipulationszelle an einem Ende der Lage liegt und ob die Lage eine ungerade oder gerade Zahl von Zellen 22 besitzt.
Nunmehr wird auf die Fig. 2(a) und 2(b) Bezug genommen. Diese zeigen zwei alternative Logikschaltungen, die die erforderliche Manipulation liefern. Zur Vereinfachung des Vergleichs soll festgestellt werden, dass die Zelleneingänge, die mit a, b, c, d in Fig. 1 bezeichnet sind, den Eingängen entsprechen, die AinL, AinR, BinL, BinR in den Fig. 2(a) und 2(b) entsprechen. Die mit Ya, Yb, Yc, Yd bezeichneten Ausgänge in Fig. 1 entsprechen den Ausgängen, die in Fig. 2(a) mit AoutL, AoutR, BoutL, BoutR bezeichnet sind. In Fig. 2(a) umfasst die Anordnung Inverter 24, UND-Gatter 26 und ODER-Gatter 28.
Die reduzierten Boolean'schen Gleichungen für AoutL, AoutR, BoutL und BoutR sind unten angegeben, wobei q, r, s und t AinL, AinR, BinL bzw. BinR repräsentieren. Die Boolean'schen Operatoren "NAND", "UND" oder "ODER" werden von 1, & bzw. # repräsentiert.
Jede dar Bit-Manipulationszellen 22 bildet eine kombinatorische volle Verschiebung und eine volle Hamming-Eliminierungs-Operation, wie in der folgenden Wahrheitstabelle dargestellt, in der die vier Eingänge der Zelle mit AinL, AinR, BinL und BinR bezeichnet sind, wobei die entsprechenden Ausgänge mit AoutL, AoutR, BoutL und BoutR bezeichnet sind, wobei beide Eingänge und Ausgänge in der gleichen Richtung von links nach rechts gelesen werden.
Eine Überprüfung der Wahrheitstabelle zeigt, dass die Bit-Manipulationszellen eine Bit-Gruppe von einer rechten Lage (AinR oder BinR) nach links verschieben, wenn das Bit jener Stellung nicht bereits gesetzt ist, aber es werden keine Bits über die Grenze zwischen AinR und BinL übertragen; beispielsweise wird (0001) als (0010) abgebildet, während (0010) nicht abgebildet wird. In gleicher Weise wird (0100) als (1000) abgebildet. Außerdem wird eine Löschoperation durchgeführt, wodurch eine Bit-Gruppe auf einer Seite der A : B-Begrenzung eine Bit-Gruppe (in irgendeiner Lage) auf der anderen Seite der Grenze löscht, und so werden beide Bits auf Null gesetzt. Dies wird beispielsweise durch die folgenden Abbildungen veranschaulicht: (0101) nach (0000); (0110) auf (0000); (1101) auf (1000) und (1111) auf (0000). Aus der Wahrheitstabelle ergibt sich außerdem, dass die 16 möglichen Eingangszustände auf fünf mögliche Ausgangszustände reduziert wurden.
Eine abgewandelte Ausführungsform einer Bit-Manipulationszelle, die allgemein die gleiche Arbeitsweise durchführt, aber gewisse Unterschiede aufweist, ist in Fig. 2(b) dargestellt. Diese Zelle besteht aus UND-Gattern 30, ODER-Gattern 32 und Invertern 34 und führt eine kombinatorische partielle Verschiebung und volle Hamming-Eliminierung durch. So liefert ein Eingang (1110) an die Zelle gemäß Fig. 2(b), die bei der Zelle gemäß Fig. 2(a) einen Ausgang von (1000) liefern würde, stattdessen einen Ausgang (0100). Jedoch kann die Zelle gemäß Fig. 2(b) in einem Feld eingebaut und benutzt werden, um einen Hammingwert-Vergleich durchzuführen.
Die AoutL- und BoutL-Bits des letzten Bit-Zellen-Manipulators werden benutzt, um die Komparator-Ausgänge zu bestimmen, wie diese durch die folgende Wahrheitstabelle definiert sind. AoutL und BoutL können nicht gleichzeitig logisch 1 sein.
Obgleich der Komparator unter Bezugnahme auf die Benutzung von ungewogenen Binär-Tupels beschrieben wurde, so ist jedoch klar, dass er auch in Verbindung mit dem Thermometercode arbeitet.
Fig. 3 ist ein ausgearbeitetes Beispiel, das einen Vergleich des Tupel A (10100110) mit dem Hammingwert von 4 zeigt, wobei B (00100000) einen Hammingwert von 1 hat. An der End-Ausgangsstufe 45, die Werte (1100) zeigt, ist ersichtlich, dass AoutL auf logisch 1 steht und BoutL auf logisch 0, was anzeigt, dass der Hammingwert von A größer ist als jener von B, wie dies in der obigen Wahrheitstabelle definiert ist.
Es wird nunmehr auf die Ausführungsbeispiele nach Fig. 5 und 6 Bezug genommen. Das Feld der Bit-Manipulationszellen 36 und ihre Verbindungen sind gleich wie bei dem Ausführungsbeispiel nach Fig. 4. Jedoch ist die jeder Zelle zugeordnete Logik unterschiedlich, und die Logik-Operationen, die durchgeführt werden und der Ausgang der Bit-Manipulationszelle und die Endauslegung sind unterschiedlich. Die Logikschaltung für die Bit-Manipulationszelle 36 ist in Fig. 5 dargestellt, und sie besteht aus sechs UND-Gattern 38 und zwei ODER-Gattern 40 und vier Invertern 42, wodurch sich einfachere Logik-Operationen für AoutL, AoutR, BoutL und BoutR ergeben, wie dies unten angegeben ist, wobei q, r, s und t AinL, AinR, BinL und BinR repräsentieren. Die Boolean'schen Operatoren "NAND", "UND" und "ODER" werden von 1, & bzw. # repräsentiert.
Die Wahrheitstabelle ist im Folgenden aufgeführt, und es ist ersichtlich, dass für zwei Bits der Tupels A und B, abgenommen an einer geraden Grenze von zwei, die Wahrheitstabelle eine kombinatorische volle Verschiebung und eine teilweise Hamming-Eliminierungs-Operation durchführt.
Diese Wahrheitstabelle ist die gleiche wie jene für das vorherige Ausführungsbeispiel mit Ausnahme der Abbildungen von (0110) auf (1010) und der Abbildung von (1001) auf (1010). Demgemäß beziehen wir uns auf diese Anordnung als "partielle" Hamming-Eliminierungs-Operation, d. h. dass Bits auf beiden Seiten der A : B-Grenze nur gelöscht werden, wenn sie in den entsprechenden Stellungen stehen, bevor die Verschiebe-Operation auftritt. So bilden beispielsweise (0101) und (1010) jeweils in (0000) ab, aber (0110) und (1001) (die beim vorigen Ausführungsbeispiel auf (0000) abbildeten) bilden bei diesem Ausführungsbeispiel auf (1010) ab. Fig. 6 ist ein ausgearbeitetes Ausführungsbeispiel für den Vergleich eines ungewogenen Tupels A (11001011), das einen Hammingwert von 5 hat und einem Tupel B (00111100), das einen Hammingwert von 4 hat. An der Endstufe 65 der Manipulationszellen 57 zeigt die Bit-Gruppe bei AoutL an, dass der Hammingwert von A größer ist als jener von B. Die Logiktabelle zur Ableitung der Hammingwert-Beziehung von AoutL und BoutL ist in der folgenden Tabelle dargestellt:
Dabei ist festzustellen, dass dieser Vergleich auch in Verbindung mit Thermometercodes arbeitet.
Die Zahl von Zellen und die Zahl von Lagen, die erforderlich sind, hängt von der Breite der zu vergleichenden Worte ab und kann empirisch bestimmt werden, um einen stabilen Ausgang für alle Eingangszustände zu erhalten.
Falls erforderlich, kann die Anordnung größer oder kleiner gemacht werden, um Tupeln unterschiedlicher Länge zu verarbeiten oder, falls erforderlich, kann ein Tupel mit 0'en ausgefüllt werden.
Die Erfindung erstreckt sich auch auf Felder, die die gleiche Funktion unter Benutzung unterschiedlicher Bit-Manipulationszellen erreichen oder De Morgan- Äquivalente der dargestellten Form benutzen. Es ist außerdem klar, dass die Anordnung eine inverse Logik und De Morgan-Äquivalente benutzen könnte. Außerdem kann die Erfindung erstreckt werden, um einen Vergleich von mehr als zwei Binär-Tupels zu ermöglichen, indem geeignete Vergleichs- und Kombinations- Stufen benutzt werden. Für drei Tupels A, B und C kann beispielsweise ein Vergleich durchgeführt werden, indem verglichen werden A : B, A : C und B : C, und dann werden die Tupels A, B, C geordert, da die Ergebnisse der Vergleiche bekannt sind.
Die Hammingwert-Komparatoren gemäß Fig. 1 bis 6 umfassen die Benutzung eines Feldes von gewöhnlichen 2 · 2-Bit-Manipulationszellen, die auf zwei Bits von jedem Tupel arbeiten, um die Hammingwert-Beziehung von zwei Binär-Tupels zu bestimmen, ohne dass vorher eine Umwandlung auf den Thermometercode erforderlich wäre. Diese Prinzipien können auch modifiziert und auf Anordnungen angewandt werden, die Bit-Manipulationszellen benutzen, welche auf mehr als zwei Bits arbeiten und die im Folgenden als n-Bit-Zellen bezeichnet werden. Die allgemeine Technik für Systeme, die n-Bit-Zellen benutzen, wird weiter unten beschrieben, und ein Beispiel wird für eine 2 · 4-Bit-Zelle angegeben.
Das allgemeine Prinzip besteht darin, dass die beiden ungewogenen Strings (A, B) zum Hammingwert-Vergleich in n-Tupels segmentiert werden, wobei n = 2, 3, 4 geeignet ist. Größere Werte von n sind theoretisch möglich, aber schwierig zu verwirklichen. Wenn die Länge der Binär-Strings durch n unteilbar ist, dann werden die Strings mit zusätzlichen 0'en ausgefüllt. In der Eingabelage und ungeraden Lagen werden die Tupels auf gerade Grenzen aufgespalten, wobei in den geraden Lagen die Tupels auf ungerade Grenzen aufgespalten werden. Dieser Staffelungseffekt schafft die Möglichkeit, dass Bit-Gruppen progressiv über gerade und ungerade Grenzen in aufeinanderfolgen Lagen wandern. Die Bit-Position innerhalb eines jeden Tupel und tatsächlich die Ordnung der Tupel in jedem Binär- String ist irrelevant, weil dis Bits ungewogen sind. Die n-Tupels mit A und B werden in einen Gitterzellenaufbau eingegeben, der eine erste Stufe hat, die eine Thermometercode-Umwandlung bewirkt, gefolgt von einer zweiten Stufe, die eine Hamming-Eliminierung bewirkt. Jedes Tupel wird in den Thermometercode unter Benutzung einer Boolean'schen Abbildung umgewandelt, wie dies in der WO99/33184 beschrieben ist.
Demgemäß benutzen die Anordnungen nach Fig. 1 bis 3 für eine Zwei-Bit-Zelle eine Zwei-Bit-Zelle in einer Gitterstruktur, aber es ist auch möglich, eine ähnliche Struktur zu benutzen, die 3, 4 usw. Bits benutzt. Wie oben erwähnt, sind für eine Zwei-Bit- Zelle die Manipulator-Gleichungen die folgenden:
wobei # die ODER-Funktion und & die UND-Funktion ist und A und B sind die Eingänge und Ya und Yb sind die entsprechenden Ausgänge.
Für eine Drei-Bit-Zelle mit den Eingängen a, b, c und den Ausgängen Ya, Yb, Yc sind die Manipulator-Gleichungen die folgenden:
in gleicher Weise sind für eine Vier-Bit-Zelle mit den Eingängen a, b, c, d und den Ausgängen Ya, Yb, Yc, Yd die Manipulator-Gleichungen die folgenden:
In der zweiten Stufe werden Bit-Gruppen in den jeweiligen Bit-Positionen der Tupel A und B durch ein Verfahren eliminiert, das hierbei als Hamming-Eliminierung bezeichnet wird. Die Thermometer-codierten Tupels A und B (1100) (1000) werden so (0100) bzw. (0000). Die Boolean'sche Gleichung, dis diese Hamming- Eliminierung an jeder Bit-Stelle durchführt, ist demgemäß ya = a & !b für die A- Tupels und yb = b & !a für die B-Tupels. Beispiele der vollständigen Zelle für n = 2 und n = 4 finden sich in Fig. 1, die eine duale 2-Eingangs-Struktur (identisch der Struktur gemäß Fig. 2(b)) zeigt bzw. in Fig. 8, die eine duale 4-Eingangs- Struktur zeigt.
Eine Prüfung der Fig. 7 und 8 zeigt, dass jede Struktur 44 bzw. 46 eine erste Stufe 48, 50 von UND- und ODER-Gattern aufweist, die die Umwandlung in den Thermometercode vornehmen und eine zweite Stufe 52, 54, die die Hamming- Eliminierung bewirkt. Die zweiten Stufen sind jeweils gleich. Die Gleichheit der ersten Stufe der beiden Eingangs-Strukturen und die vier Eingangs-Strukturen der Thermometercode-Wandlerstruktur ergeben sich aus der WO99/33184.
Dann wird eine Gitter-Struktur der Bit-Zellen-Manipulatoren erzeugt, um die Boolean'schen Prozesse parallel zueinander durchzuführen. Fig. 9 zeigt ein Beispiel für einen Hammingwert-Komparator, der aus einem Feld von 2 · 4-Bit- Manipulationszellen 56 der Type besteht, wie sie in Fig. 8 dargestellt sind, um die Hammingwerte von zwei 12-Bit-Worten A (mit den Bits a&sub0; ... a&sub1;&sub1;) und B (mit den Bits b&sub0; ... b&sub1;&sub1;) zu vergleichen. In diesem Feld werden Eingänge und Ausgänge so wieder angeordnet, dass sie in einer Linie liegen, statt um 90º versetzt zu sein wie in Fig. 8, aber die logischen Operationen verbleiben ungeändert. Wie oben, hat die Struktur abwechselnd ungerade und gerade Lagen von Bit-Manipulationszellen 56, und die Zellen in benachbarten Lagen sind gestaffelt, um eine Versetzung oder Überlappung zu erreichen, damit die Bit-Gruppen durch das Feld hindurchwandern, wie dies erforderlich ist. Das Feld wird wie oben gestutzt, und jeweils zwei der Ausgänge von der letzten Zelle werden über ODER-Gatter zusammen an einem Endstufen- Dekoder 58 verknüpft. Wenn ein Bit auf den mit "B" bezeichneten Ausgang gesetzt wird, aber nicht auf jenen, der mit "A" markiert ist, dann ist der Hammingwert von B größer als jener für A. Wenn ein Bit auf den mit A markierten Ausgang gesetzt wird, nicht aber auf jenen, der mit B markiert ist, dann wird der Hammingwert von B kleiner als jener von A. Wenn die Bits an den mit "A" und "B" markierten Ausgängen die gleichen sind, dann sind auch die Hammingwerte von A und B die gleichen.
Demgemäß setzen am Dekoder 58 das ODER-Gatter, das EXKLUSIV-NOR-Gatter und das UND-Gatter 60, 62, 64 und die Inverter 66 das jeweilige Bit auf einen der Dekoder-Ausgänge A kleiner als B (A B), A größer als B (A B) oder A gleich B (A = B). Fig. 10 ist ein ausgearbeitetes Beispiel für die Schaltung nach Fig. 9, welche zwei 12-Bit-Binär-Tupels (111011000000) bzw. (000000111111) vergleicht und das richtige Ergebnis bestimmt.
Es ist auch möglich, Komparatoren auszubilden, die verschieben und vergleichen nach dem Zentrum der Strings. Diese Konstruktion ist schneller und benutzt eine kleinere Logik. Im Folgenden wird nunmehr auf die Fig. 11 bis 13 Bezug genommen, wo ein Ausführungsbeispiel eines Hammingwert-Komparators dargestellt ist, der ein Feld von 2 · 2-Bit-Manipulationszellen benutzt, die zwei Bits von jedem Binär-Tupel nehmen - hier jedes von acht Bits - und eine Verschiebung und Eliminierung durchführen. Bei diesem Ausführungsbeispiel werden die Bits nach der Mitte des Tupel und nicht nach einem Ende verschoben. Die Ähnlichkeiten mit der ursprünglichen 2-Bit-Manipulationszelle ist offensichtlich.
Aus der Darstellung gemäß Fig. 12 ist ersichtlich, dass das Feld aus einer Zahl von Zellen besteht, die jeweils als ungerade Verschiebezellen 68, gerade Verschiebezellen 70 und Hamming-Eliminierungs-Blocks 72 ausgebildet sind. Die ungeraden und die geraden Verschiebezellen 68, 70 sind symmetrisch um die Mittellinie des Feldes plaziert, wobei die Verschiebezellen unter der Mittellinie nach oben verschieben und die Verschiebezellen über der Mittellinie nach unten verschieben. Die Hamming-Eliminierungs-Blöcke 72 sind auf der Feld-Mittellinie angeordnet und spezielle Manipulationszellen wirken auf vier Bits, die als ein Block von 2 · 2-Bits organisiert sind und aus einem UND-Gatter und gewählten Eingängen bestehen, die wie dargestellt invertiert sind. Die Eliminierung umfasst eine vertikale Stufe 74 und eine Querstufe 76, und die Stufen können in irgendeiner Ordnung angeordnet sein. Unter Bezugnahme auf die schematische Darstellung in den Fig. 11 oder 13 sind die folgenden Operationen zutreffend, wobei die Eingänge und Ausgänge des Feldes mit (A1, B1, A2, B2) bezeichnet sind, wenn man von unten nach oben in der Betrachtung fortschreitet.
Wenn A1 und B1 gleich 1 sind, dann werden sie beide 0 (vertikal)
Wenn A2 und B2 gleich 1 sind, dann werden sie beide 0 (vertikal)
Wenn A1 und B2 gleich 1 sind, dann werden sie beide 0 (quer)
Wenn A2 und B1 gleich 1 sind, dann werden sie beide 0 (quer)
wobei alle anderen Werte gerade hindurchlaufen.
Es ist ein Haupt-Dekoder 78 erforderlich, um die A B-, A B- und A = B-Ausgänge aus den Werten zu liefern, die von dem letzten Hamming-Eliminierungs-Block empfangen werden, und die logischen Schaltungen hierfür sind in den Fig. 11 und 13 dargestellt.

Ebener Hammingwert-Komparator

Nunmehr wird auf das Ausführungsbeispiel nach den Fig. 14 bis 18 Bezug genommen. Hierin ist eine Boolean'sche Gitter-Struktur für einen Hammingwert- Vergleich vorgesehen. Die oben in Verbindung mit den Fig. 1 bis 13 beschriebenen Anordnungen bewirken den Hammingwert-Vergleich von ein-dimensionalen Strings von ungewogenen binären Bits verschiedener Wortlänge, die ein Feld von Manipulationszellen benutzen, das eine vollständige oder teilweise Verschiebung und eine vollständige oder teilweise Bit-Eliminierung auf gewählten Bits von den zwei ein-dimensionalen Strings zur Folge hat. Diese Technik wurde entwickelt, um eine Anordnung zu schaffen, mit der die Hammingwert-Beziehungen von zwei gleich bemessenen quadratischen ungewogenen Feldern verglichen werden können.
Gemäß Fig. 14 besteht die Hammingwert-Einrichtung aus abwechselnden ungeraden und geraden Lagen 80, 82. Jede Lage bei diesem Beispiel verarbeitet ein erstes Feld von 6 · 6-Bits (identifiziert durch neun Posten von Großbuchstaben (A, B, C, D) und Koordinaten R&sub1; bis R&sub6; und C&sub1; bis C&sub6;) und ein zweites Feld von Bits (identifiziert durch neun Posten von Kleinbuchstaben (a, b, c, d) und Koordinaten r&sub1; bis r&sub6;, c&sub1; bis c&sub6;). Jede Lage bewirkt eine Verschiebung von Bit-Gruppen nach der oberen linken Ecke, wie betrachtet. Jede Lage bewirkt außerdem eine Hamming- Eliminierung zwischen den Feldern, ähnlich jener, die in den ein-dimensionalen Feldern durchgeführt wurde und wie es unten veranschaulicht wird, so dass in aufeinanderfolgenden Lagen die Bits nach der linken oberen Ecke des Feldes verschoben werden und die Hamming-Eliminierung durchgeführt wird. Schließlich zeigt in der letzten Lage ein einziges Bit am Ausgang die Hammingwert-Beziehung der beiden Felder an.
Hierbei ist zu berücksichtigen, dass jede Lage symmetrisch um die Diagonale ist, die von oben links nach unten rechts verläuft, wobei die Zellen auf und über der Diagonalen die folgenden sind:
und die unter der Diagonalen laufen sind:
In der ersten Lage 80 ist jedes 6 · 6 - Feld von Eingängen in neun 2 · 2-Tupels abgesondert. Für ein Eingangsfeld gibt es neun Tupels, je identifiziert durch {a, b, c, d} (obgleich a, b, c, d nicht jeweils gleich zwischen den Tupels ist) und für das andere Feld gibt es neun Tupels {A, B, C, D}.
In der ersten Lage sind zwei Posten von 2 · 2-Tupels von dem gleichen Teil von Eingangsfeldern kombiniert, wie dies durch die konzentrische Anordnung angedeutet ist. Demgemäß werden an jeder Tupel-Stellung die Tupels {a, b, c, d} in der Mitte und die Tupels {A, B, C, D} um die Mitte herum zusammen so verarbeitet, dass im Effekt die erste Lage 80 aus einem Feld von neun 8-Bit-Manipulationszellen 84 besteht. Die 8-Bit-Manipulationszelle 84 ist in Fig. 16 dargestellt, und sie ist die gleiche wie jene, die in Fig. 8 dargestellt ist mit der Ausnahme, dass zur Verbesserung des Verständnisses die Bezeichnung geändert wurde, um die Identifikation der Tupels durch Groß- und Kleinbuchstaben zu erleichtern. Die 8-Bit- Manipulationszelle empfängt die beiden Tupels {a, b, c, d} und {A, B, C, D} und führt eine Verschiebe- und Eliminierungs-Operation durch und gibt das Ergebnis in Form von Tupeln {Ya, Yb, Yc, Yd} und {YA, YB, YC, YD} aus. Die gleichen Operationen werden in allen anderen ungeraden Lagen durchgeführt.
In der zweiten und den geraden Lagen 82 gibt es eine Versetzung und Überlappung und eine Durchführung 86 an den vier Ecken. Um die erforderliche Versetzung und Überlappung zu erhalten, bestehen bei diesem Beispiel die geraden Lagen aus vier 8-Bit-Manipulationszellen 84 der Type, wie sie bei den ungeraden Lagen benutzt wurden, und diese sind zentral und symmetrisch um die Diagonale angeordnet, die üblicherweise von links oben nach rechts unten verläuft. Acht Peripherie-4-Bit- Manipulationszellen 88 sind im Abstand über die Peripherie verteilt, und acht Durchführungen 86 an den Ecken. Die 4-Bit-Manipulationszellen in den geraden Lagen wirken auf zwei Tupel {A, B} und {a, b} und führen eine Verschiebung und eine Hamming-Eliminierung durch, wie dies in der Gleichungs-Gruppe (1) beschrieben wurde. Fig. 15 zeigt die Logikschaltung der Fig. 1 und 2, gekennzeichnet mit {A, B}- und {a, b}-Eingangs-Tupeln und {YA, YB}- {Ya Yb}- Ausgangs-Tupeln.
Demgemäß wird ein Bit mit Koordinaten (Cm, Rn) in einer ungeraden Lage auf (Cm, Rn) in einer geraden Lage abgebildet, und (cm, rn) in einer ungeraden Lage wird auf (cm, rn) in einer geraden Lage abgebildet. So werden beispielsweise die Ausgänge in der oberen rechten Lage der ersten Lage mit den Koordinaten (C&sub6;, R&sub1;) und (c&sub6;, r&sub1;) YC und Yc wie in Fig. 16 dargestellt. Die Elemente an diesen Koordinaten in der zweiten Lage sind Durchführungen 86, und so durchlaufen YC und Yc unverändert die zweite Schicht, um die "C"- und "c"- Eingänge nach der oberen rechten Manipulationszelle 34 in der dritten Lage zu bilden. Die Abbildung der Ausgänge der anderen ersten Lage auf die Eingänge der zweiten oder folgenden Lage kann leicht in ähnlicher Weise bestimmt werden.
Die Fig. 17 und 18 zeigen ausgearbeitete Beispiele für die ebene 6 · 6- Hammingwert-Struktur, die gerade beschrieben wurde, für zwei Gruppen von 6 · 6- Eingängen. Dabei ist zu bemerken, dass in Fig. 17 der Ausgang nach fünf Lagen stabil ist, während gemäß Fig. 18 ein stabiler Ausgang nach sechs Lagen erreicht wird.
In Fig. 17 hat das innere Feld von Eingängen (d. h. das untere Feld gemäß Fig. 14) einen Hammingwert von 18, während das äußere Feld von Eingängen (d. h. das Feld mit Großbuchstaben gemäß Fig. 14) einen Hammingwert von 14 hat. Die Ausgänge einer jeden Lage sind zusammen mit den jeweiligen Hammingwerten dargestellt, was zu einer Eliminierung für jedes Feld führt. Der Ausgang des Feldes wird durch. Überwachung der Bits an den Stellen (C&sub1;, R&sub1;) und (c&sub1;, r&sub1;) abgelesen. Wenn der Hammingwert des Großbuchstaben-Feldes größer ist, dann wird am Ausgang der letzten Lage das Bit bei (C&sub1;, R&sub1;) (wie in Fig. 18(b) dargestellt) gesetzt. Wenn der Hammingwert des Feldes der Kleinbuchstaben größer ist, dann wird das Bit an der Stelle (c&sub1;, r&sub1;) (wie in Fig. 17) gesetzt. Wenn die Bits an beiden Stellen die gleichen sind, so bedeutet dies, dass die Hammingwerte der beiden Felder die gleichen sind.
Die Fig. 14 bis 16 zeigen ein Beispiel einer Zellen-Lage-Struktur zur Verarbeitung an zwei 6 · 6-Bit-Feldern. Es ist jedoch möglich, Strukturen für kleinere oder größere Felder zu schaffen, wobei die gleichen Grundprinzipien benutzt werden. Falls erforderlich, können größere Verarbeitungsblöcke benutzt werden, anstelle der 8-Bit-Blöcke, wie sie bei diesem Beispiel benutzt wurden.
Es ist zu bemerken, dass die oben beschriebene Technik in Bezug auf die Aggregat-Code-Formation und planare Hammingwert-Struktur über die zweidimensionalen Felder ausgedehnt werden kann, um dreidimensionale Felder oder höher-dimensionale Felder zu schaffen (kubische und hyper-planare Systeme). Die oben beschriebenen Hammingwert-Komparatoren können benutzt werden, um eine Summierungs- und Schwellwert-Funktion (SAT) bei bestehenden und neuen ungewogenen Neuronen-Netzen durchzuführen. Wie in Fig. 19 dargestellt, können ein Tupel von Neuronen-Daten und ein Tupel, das einen Neuronen-Schwellwert definiert, einem Hammingwert-Komparator 90 zugeführt werden, der gemäß einer der oben beschriebenen Typen ausgebildet ist, und zwar unabhängig von einer, von zwei oder von größeren Dimensionen. Der relevante Ausgang des Komparators wird dann überprüft, um zu sehen, ob ein Bit am Ausgang gesetzt ist, was anzeigt, dass die Neuronen-Daten den Neuronen-Schwellwert überschritten haben. Der relevante Ausgang wird dann als der einzige Ausgang des Neuronen-Netzes angesehen, von dem man annimmt, dass ein "Feuern" stattgefunden hat, wenn das Bit gesetzt war. Natürlich könnte einer der anderen Ausgänge überwacht werden, wenn beabsichtigt ist, dass das Neuronen-Netz auf eine andere Bedingung anspricht.

Claims

1. Hammingwert-Komparator zur Lieferung eines Ausgangs, der die Hammingwert-Beziehung eines ersten ein- oder mehrdimensionalen ungewogenen Feldes ungewogener Bits (a&sub1; ... a&sub8;) und eines zweiten ein- oder mehrdimensionalen ungewogenen Feldes ungewogener Bits (b&sub1; ... b&sub8;) anzeigt,

wobei der Hammingwert eines gegebenen ungewogenen Feldes die Zahl der darin befindlichen logischen 1's ist und die Hammingwert-Beziehung von zwei ungewogenen Feldern anzeigt, welches den größeren Hammingwert hat oder ob die Hammingwerte hiervon die gleichen sind;

wobei der Hammingwert-Komparator die folgenden Merkmale aufweist:

Mittel, um die Bits von den Feldern einem Prozessor zuzuführen, der mehrere Lagen von (n + n)-Bit-Manipulationszellen (22, 36, 46, 56 usw.) aufweist, wobei jede Manipulationszelle (22, 36, 46, 56 usw.) erste n-Eingänge zum Empfang der jeweiligen Bits aufweist, die den jeweiligen Bits (a&sub1;, a&sub2; usw.) in dem ersten Feld (a&sub1; ... a&sub8;) entsprechen und zweite n-Eingänge vorgesehen sind, um Bits zu empfangen, die den jeweiligen Bits (b&sub1;, b&sub2; usw.) in dem zweiten Feld (b&sub1; ... b&sub8;) entsprechen und erste n-Ausgänge und zweite n-Ausgänge jeweils den ersten bzw. zweiten n-Eingängen entsprechen,

wobei jede Manipulationszelle (22, 36, 46, 56 usw.) Logikmittel (24, 26, 28 usw.) aufweist, um wenigstens eine Bit-Verschiebeoperation oder eine Bit- Eliminierungsoperation durchzuführen,

wobei die (n + n)-Bit-Manipulationszellen (22, 36, 46, 56 usw.) miteinander verbunden sind, indem die Ausgänge jeder Schicht außer der letzten Schicht nach den jeweiligen Eingängen der nächsten oder übernächsten Lage verlaufen,

und wobei in aufeinanderfolgenden Lagen die Bit-Gruppen am Ausgang der Manipulationszellen in aufeinanderfolgende Lagen nach einer gemeinsamen Bit- Position relativ zu den Lagen wandern und die Endlage einen Ausgang liefert, der die Hamming-Beziehung anzeigt.

2. Hammingwert-Komparator nach Anspruch 1, bei welchem der Prozessor mehrere im Wesentlichen gemeinsame (n + n)-Bit-Manipulationszellen (22, 36, 46, 56 usw.) aufweist und jede Manipulationszelle Logikmittel umfasst, um die folgenden Schritte durchzuführen:

(i) eine Bit-Verschiebeoperation, wobei Bit-Gruppen in jedem der ersten und zweiten n-Eingänge in einer vorbestimmten Richtung verschoben werden und das Vorhandensein genullter Bits ein Erscheinen in einer Bit-verschobenen Position in dem entsprechenden n-Ausgang ermöglicht, und

(ii) eine Hamming-Eliminierungsoperation, wobei dann, wenn eine logisch 1 an einer gegebenen Bit-Position in den ersten Eingängen steht, die einer logisch 1 an einer entsprechenden Bit-Position in den zweiten Eingängen entspricht, beide Bit-Gruppen auf logisch 0 gesetzt werden.

3. Hammingwert-Komparator nach Anspruch 2, bei welchem die Hamming- Eliminierungsoperation eine volle Eliminierungsoperation ist, wobei eine logisch 1 in einem der ersten Eingänge in der Lage ist, eine logisch 1 an irgendeiner Bit- Position in den zweiten n-Eingängen zu eliminieren.

4. Hammingwert-Komparator nach Anspruch 2, bei welchem die Hamming- Eliminierungsoperation eine partielle Eliminierungsoperation ist, wobei eine logisch 1 an einer gegebenen Bit-Position in den ersten n-Eingängen nur eine logisch 1 an der gleichen Bit-Position in den zweiten n-Eingängen eliminieren kann.

5. Hammingwert-Komparator nach einem der vorhergehenden Ansprüche, bei welchem die Bit-Manipulationszellen eine vollständige Bit-Verschiebung durchführen, wobei sowohl für die ersten als auch die zweiten n-Eingänge eine logisch 1 immer in der vorbestimmten Richtung verschoben wird, wenn eine oder mehrere logische 0 benachbart zur logisch 1 in Richtung der Bit-Verschiebung vorhanden sind.

6. Hammingwert-Komparator nach einem der vorhergehenden Ansprüche, bei welchem jede Bit-Manipulationszelle (22, 36, 46, 56 usw.) vier Eingänge (AINL, AINR, BINL, BINR) und vier Ausgänge (AOUTL, AOUTR, BOUTL, BOUTR) aufweist und die Bit-Manipulationszellen in der ersten Lage so angeordnet sind, dass für jede Bit-Manipulationszelle (22, 36) zwei Eingänge (AINL, AINR) jeweils ein entsprechendes Bit empfangen, das von einer der Binärfelder (a&sub1; ... a&sub8;) abgeleitet wird und die anderen beiden Eingänge (BINL, BINR) jeweils ein entsprechendes Bit empfangen, das von dem anderen Binärfeld (b&sub1; ... b&sub8;) abgeleitet wurde.

7. Hammingwert-Komparator nach Anspruch 6, bei welchem jede der entsprechenden Gruppen von zwei Eingängen (AINL, AINR; BINL, BINR) nach den Bit-Manipulationszellen (22, 36) in der ersten Lage benachbarte Bits empfangen, die von den entsprechenden Binärfeldern (a&sub1; ... a&sub8;; b&sub1; ... b&sub8; usw.) abgeleitet sind, abgenommen von einer geraden Begrenzung.

8. Hammingwert-Komparator nach Anspruch 7, bei welchem jede Manipulationszelle (22, 36) eine Operation auf die Bits (AINL, AINR; BINL, BlNR) durchführt, die von den ersten und zweiten Binärfeldern (a&sub1; ... a&sub8;; b&sub1; ... b&sub8;) abgeleitet wurden und an den entsprechenden Eingängen empfangen wurden, wodurch eine Bit-Gruppe nach einer vorbestimmten Bit-Richtung verschoben und entsprechende positionierte Bit-Gruppen vollständig oder teilweise eliminiert werden.

9. Hammingwert-Komparator nach Anspruch 5 bei Abhängigkeit von Anspruch 3, bei welchem jede der Bit-Manipulationszellen eine Wahrheitstabelle aufweist, die im Wesentlichen wie folgt oder invers hierzu aufgebaut ist.

wobei AINL, AINR, BINL, BINR die vier Eingänge nach der Zelle sind und AOUTL, AOUTR, BOUTL, BOUTR die vier Ausgänge sind.

10. Hammingwert-Komparator nach Anspruch 5 bei Abhängigkeit von Anspruch 4, bei welchem jede Bit-Manipulationszelle eine Wahrheitstabelle enthält, die im Wesentlichen wie im Folgenden beschrieben oder invers hierzu aufgebaut ist.

11. Hammingwert-Komparator nach einem der vorhergehenden Ansprüche, bei welchem jede Bit-Manipulationszelle (22, 36) eine erste Mehrzahl von Eingängen (AINL, AINR) zum Empfang der jeweiligen Bits (a&sub1;, a&sub2; usw.) aufweist, die von einem der Felder (a&sub1; ... a&sub8;) abgeleitet wurden und eine zweite Mehrzahl von Eingängen (BINL, BINR) zum Empfang der jeweiligen Bits (b&sub1;, b&sub2;), die von den anderen Binärfeldern (b&sub1; ... b&sub8;) abgeleitet wurden und die Bit-Manipulationszelle (22, 36) eine entsprechende Mehrzahl von Ausgängen aufweist und Logikmittel vorgesehen sind, um auf einem vorgewählten Ausgang eine Bit-Gruppe auszugeben, wenn der Hammingwert der Bits (a&sub1; ... a&sub8;) auf der ersten Mehrzahl von Eingängen größer ist als der Hammingwert der Bits (b&sub1; ... b&sub8;) auf der zweiten Mehrzahl von Eingängen.

12. Hammingwert-Komparator nach Anspruch 1 zum Vergleich von zwei ein- oder mehrdimensionalen Binärfeldern (a&sub1; ... a&sub8;; b&sub1; ... b&sub8;), der mehrere abwechselnde Lagen von Bit-Manipulationszellen (68, 70, 72) aufweist und eine der Lagen eine Mehrzahl von ersten Bit-Manipulationszellen (68) zur Verschiebung der Bit-Gruppen in den Eingangsfeldern nach einer vorbestimmten Bit-Position aufweist und andere der Lagen mehrere Bit-Manipulationszellen (68) in Verbindung mit einer Hamming- Eliminierungszelle (72) aufweisen, um entsprechende Bit-Gruppen in jedem der Felder zu eliminieren.

13. Hammingwert-Komparator nach Anspruch 1 zum Vergleich von zwei zweidimensionalen Feldern binärer Daten (ABCD; abcd) und zur Bestimmung, welche, wenn überhaupt, die größere Zahl von logischen 1's enthält, wobei der Komparator eine Mehrzahl von Lagen (80, 82) von Bit-Manipulationszellen (84) aufweist und jede Zelle (84) wenigstens zwei Eingänge und zwei Ausgänge aufweist und so ausgebildet ist, dass die Bit-Gruppen nach einer vorgewählten Bit-Position verschoben werden und eine Verbindung zwischen den Lagen vorhanden ist, um wenigstens eine Bit-Verschiebung oder eine Bit-Eliminierung durchzuführen, wodurch ein Ausgang erhalten wird, der anzeigt, welches Feld die größere Zahl von logischen 1's enthält, wenn überhaupt welche vorhanden sind.

14. Hammingwert-Komparator nach Anspruch 13, bei welchem der Komparator abwechselnde Lagen (80, 82) aufweist und eine der Lagen (80) ein Feld von 4 + 4- Bit-Manipulationszellen (84) umfasst und die andere Lage (82) ein Feld von 4 + 4-Bit- Manipulationszellen (84) aufweist und mehrere 2 + 2-Bit-Manipulationszellen (88) in Umfangsrichtung angeordnet sind und mehrere Durchgänge (I) vorgesehen sind.

15. Hammingwert-Komparator nach Anspruch 14, bei welchem die Bit- Manipulationszellen in jeder Lage so ausgebildet sind, dass die Bits nach einer gemeinsamen Achse oder einem Brennpunkt relativ zu den Lagen verschoben werden.

16. Hammingwert-Komparator nach einem der Ansprüche 14 oder 15, bei welchem die 2 + 2-Bit-Manipulationszellen (88) die Logikoperationen wie nachstehend beschrieben unter Benutzung der Eingänge a, b, c, d und der Ausgänge Ya, Yb, Yc, Yd durchführen:

wobei "&" den UND-Operator und "#" den ODER-Operator repräsentiert.

17. Hammingwert-Komparator nach einem der Ansprüche 14 bis 16, bei welchem die 4 + 4-Bit-Manipulationszelle (84) über die Eingänge ({ABCD} und {abcd}) Ausgänge YA, YB, YC, YD und Ya, Yb, Yc, Yd gemäß den Logikoperationen liefert, wie sie in Fig. 17 dargestellt sind.

18. Binär-Summierungs- und Schwellwertvorrichtung mit einem Hammingwert- Komparator nach einem der vorhergehenden Ansprüche.

19. Verfahren zur Bestimmung, ob, wenn überhaupt, ein erstes ein- oder mehrdimensioneles ungewogenes Feld ungewogener Bits (a&sub1; ... a&sub8;) oder ein zweites ein- oder mehrdimensionales ungewogenes Feld ungewogener Bits (b&sub1; ... b&sub8;) die größere Zahl logischer 1's aufweist, wobei das Verfahren die folgenden Schritte umfasst:

(i) es werden die Bits aus den Feldern einem Prozessor zugeführt, der eine Mehrzahl von Lagen von (n + n)-Bit-Manipulationszellen (22, 36, 46, 56 usw.) aufweist und jede Manipulationszelle (22, 36, 46, 56 usw.) erste n-Eingänge zum Empfang der jeweiligen Bits aufweist, die den Bits (a&sub1;, a&sub2; usw.) in dem ersten Feld (a&sub1; ... a&sub8;) entsprechen und zweite n-Eingänge zum Empfang von Bits entsprechend den jeweiligen Bits (b&sub1;, b&sub2; usw.) in dem zweiten Feld (b&sub1; ... b&sub8;) und erste n-Ausgänge und zweite n-Ausgänge entsprechend den ersten bzw. den zweiten Eingängen vorgesehen sind,

wobei die n + n-Bit-Manipulationszellen (22, 36, 46, 56 usw.) miteinander verbunden sind, indem die Ausgänge jeder Lage außer der Endlage nach den jeweiligen Eingängen der nächsten oder übernächsten Lage hindurchlaufen,

wobei in aufeinanderfolgenden Lagen die Bit-Gruppen am Ausgang der Bit- Manipulationszellen in aufeinanderfolgende Lagen nach einer gemeinsamen Bit- Position relativ zu den Lagen wandern und die Endlage einen Ausgang liefert, der die Hamming-Beziehung anzeigt.