Die Erfindung betrifft Schaltungsanordnungen zur Bestimmung einer besten Anpassung zwischen Eingangssignalen und einer Auswahl von Grundfunktionen.

Digitale Computer sind allgegenwärtig und ziemlich leistungsstark, das heißt aber nicht, daß digitale Computer nicht bestimmten Begrenzungen bei der Lösung von Problemen unterliegen. Tatsächlich erfordern viele praktische Probleme einen so enormen Rechenaufwand, daß eine Lösung in Echtzeit nicht möglich ist. Auf solche Schwierigkeiten stößt man beispielsweise bei Programmen, die dazu dienen, aus einem Speicher die Information auszuwählen, die bekannte Eigenschaften oder Deskriptoren (die man auch als "Hinweise" ("Clues") bezeichnen kann) am besten erfüllt, wenn die Hinweise nicht ausreichen, die Information vollständig festzulegen. Die Mustererkennung ist ein anderes Beispiel dafür, daß das Rechenproblem für digitale Computer zu groß ist.

Die meisten Fachleute dulden entweder die Beschränkungen digitaler Allzweckrechner oder entwickeln digitale Sonderzweckrechner, um ihre besonderen Probleme effizienter zu lösen.

In einer gleichzeitig anhängenden Anmeldung mit der Bezeichnung "Electronic Network For Collective Decision Based On Large Number Of Connections Between Signals", von J. J. Hopfield, wurde eine verallgemeinerte Schaltungsanordnung offenbart, die N Verstärker mit hoher Verstärkung und eine N · N Verbindungsmatrix mit N Eingangsleitungen und N Ausgangsleitungen aufweist. Die Verstärker weisen eine s-förmige Eingang- Ausgang- Beziehung auf mit einem minimal und maximal möglichen Ausgangssignal, das als eine "0" oder "1" aufgefaßt werden kann. Jede Eingangsleitung der Matrix ist mit dem Eingang eines anderen Verstärkers verbunden, wobei die Ausgangsanschlüsse (positiv und negativ) jedes Verstärkers mit einer anderen Matrix-Ausgangsleitung verbunden sind. Jeder Verstärker weist außerdem eine Eingangskapazität Ci und einen Eingangswiderstand Pi auf. Innerhalb der Verbindungsmatrix ist jede Eingangsleitung i mit einer Ausgangsleitung j über einen Widerstand Ri,j verbunden. Bei der offenbarten Schaltungsanordnung genügt jeder Verstärker der Bewegungsgleichung der Schaltung

wobei

Tij = [(1/Rij) * sgn des Ausgangs des Verstärkers j], ui die Eingangsspannung am Verstärker i, Vj die Ausgangsspannung des einen Verstärkers j, und Ii der in den Eingangsanschluß des Verstärkers i (z. B. von einer Quelle hoher Impedanz) eingeführte Strom ist.

Durch die Dynamik der offenbarten Schaltungsanordnung (wie sie durch die obige Gleichung spezifiziert ist) wird das Netzwerk in einen von mehreren vorbestimmten stabilen Zuständen getrieben, der ein Ausgangsmuster von binären 1'en und 0'en darstellt (da die Verstärker eine hohe Verstärkung haben).

Wenn die Verstärker i zum Zugriff auf die Informationen in einem assoziativen Speicher verwendet werden, werden die Eingangsspannungen der Verstärker im Einklang mit den einzelnen Bits des Eingangswortes für jeden Hinweis (Deskriptor), der für die erwünschte Information bekannt ist, gesetzt. Alternativ kann ein konstanter Strom jedem Eingang proportional zum Vertrauen darauf, daß die Spannung Vi in der Endantwort "1" sein soll, zugeführt werden. Wenn die Verstärker einmal aktiviert sind, gehen sie in einen stabilen Zustand, und produzieren am Ausgang ein einheitliches Wort, das die Information selbst darstellt, die die Adresse eines Speicherplatzes in einem anderen Speicher enthalten kann, der dann einen Block von Wörtern hervorbringen kann, die die Information enthalten, die durch den Deskriptor festgelegt ist, der zum Speichern und Auslesen des einheitlichen Wortes aus dem assoziativen Speicher verwendet wird.

Bei einer Verwendung für Problemlösungen können alle Eingänge näherungsweise auf den gleichen Wert gesetzt werden, beispielsweise auf Null, oder in einem Muster gehalten werden, das die Eingangsinformation darstellt, und das Ausgangsmuster aus den Bits "1" und "0" legt die Lösung fest. Bei beiden Anwendungen, d. h. bei der Problemlösung oder Informationswiedergewinnung, liefert das Ausgangssignal in binärer Form eine sehr gute Lösung des gegebenen Problems.

Obwohl die offenbarte Schaltung einen stabilen Lösungszustand schnell und effizient erreicht, ist nicht sichergestellt, daß die optimale Lösung zu einem gegebenen Problem gefunden wird. Das liegt daran, daß die Topology des Lösungsraums sehr grob ist und viele lokale Minima aufweist, und deshalb viele gute Lösungen der optimalen Lösung ähnlich sind. Sehr gute und schnell berechnete Lösungen von schwierigen Problemen bei der Erkennung und Wahrnehmung in Bereichen der Robotertechnik und der Biologie können ausreichende Informationen für den praktischen Gebrauch liefern, aber in einigen Anwendungsfällen ist die exakte oder beste Lösungen erwünscht.

Ein Bericht der National Acadamy of Science USA, Vol. 81, Mai 1984, Seiten 3088-3092; J. J. Hopfield: "Neurons with graded response have collective computational properties like those of two-state neurons handelt von einer mathematischen Analyse des Verhaltens zweier Schaltungen. Eine davon ist eine klassische Schaltung (sie ist der später unter Bezugnahme auf Fig. 1 hierin beschriebenen Schaltung ähnlich), bei der die Verstärker eine sehr hohe Verstärkung aufweisen und grundsätzlich Elemente mit zwei Zuständen (0 und 1) sind, und die andere die klassische Schaltung ist, bei der die Verstärker analoge Ausgänge haben. Die Veröffentlichung zeigt, daß das Verhalten der beiden Schaltungen im wesentlichen gleich ist.

Der Erfindung liegt daher die Aufgabe zugrunde, ein Netzwerk analoger Prozessoren in Verbindung mit Zerlegungsprozessen zu verwirklichen.

Gemäß der Erfindung wird eine in Anspruch 1 beanspruchte Schaltungsanordnung geschaffen.

Bei einer Ausführungsform der Erfindung ist ein analoges Netzwerk mit hohem Verbindungsgrad aufgebaut, um einen spezifischen Zerlegungsprozeß auszuführen. Das Netzwerk weist analoge Verstärker auf, die mit einer ohmschen Verbindungsmatrix verbunden sind, die wie bei dem bekannten Netzwerk jeden Verstärkerausgang mit dem Eingang aller anderen Verstärker verbindet. Die konkreten Verbindungen in der Matrix werden mit Leitwertelementen erzielt, deren Werte gemäß dem Satz von Zerlegungsfunktionen, für die die Lösung gesucht wird, berechnet werden. Zusätzlich zu der spezifizierten Verbindung, die durch die Verbindungsmatrix ausgeführt ist, enthält das analoge Netzwerk eine zweite Matrix, die außen angelegte Spannungen über Widerstände an die Verstärkereingänge anlegt, deren Werte ebenfalls gemäß dem Satz von Zerlegungsfunktionen berechnet werden, für die die Lösung gesucht wird. Die Schaltung kann ihre Lösung durch einen Prozeß simulierten Hochfahrens finden, wobei die Verstärkungen der Verstärker anfänglich auf niedrige Werte gesetzt sind und dann langsam auf ihren maximalen Wert erhöht werden. Dieser Prozeß verhindert, daß die Schaltung in ein lokales Minimum getrieben wird.

Die Erfindung wird unter Bezugnahme auf die beigefügten Zeichnungen beschrieben. Es zeigen:

Fig. 1 ein Analog-Netzwerk mit hohem Verbindungsgrad nach dem Stand der Technik,

Fig. 2 ein die Erfindung verwirklichendes Netzwerk zur Ausführung eines 4-Bit-Analog-Digital-Umsetzprozesses,

Fig. 3 ein abgetastetes Signal, daß durch ein die Erfindung verwirklichendes Netzwerk zerlegt werden kann,

Fig. 4 eine Vielzahl von Gaußfunktionen, die, wenn sie zusammengesetzt werden, das abgetastete Signal der Fig. 3 bilden,

Fig. 5 ein Netzwerk zur Ausführung einer Zerlegung eines Signals, das eine Vielzahl von Abtastwerten enthält, und

Fig. 6 eine Darstellung zur Beschreibung des Schaltungsverhaltens unter Ansprechen auf das Ändern der Größe der Verstärkungen der Verstärker.

Fig. 1 zeigt ein schematisches Schaltbild eines Mehrprozessor- Rechennetzwerkes, das in der oben erwähnten, gleichzeitig anhängigen Anmeldung offenbart ist. Es weist Verstärker 10 auf, die eine positive und fakultativ eine negative Verstärkung liefern, wobei deren Ein-und Ausgänge über ein Verbindungsnetzwerk 20 miteinander verbunden sind. Eine physikalische Ausführungsform eines Verstärkers weist notwendigerweise eine Impedanz am Eingang auf, die hauptsächlich ohmscher und kapazitiver Natur ist. Sie ist in Fig. 1 durch Widerstände 11 (Pi) und Kondensatoren 12 (Ci) dargestellt. Jeder Knoten in der Verbindungsmatrix 20 ist durch einen fetten schwarzen Punkt 21 dargestellt, wobei jeder Knoten einen Widerstand Rij aufweist, der einen mit einem Ausgang eines Verstärkers i verbundenen Pfad der Matrix 20' beispielsweise den Pfad 22, mit einem mit dem Eingang eines Verstärkers j verbundenen Pfad der Matrix 20, beispielsweise dem Pfad 23, verbindet. Außerdem ermöglicht die in Fig. 1 dargestellte Schaltungsanordnung außen angelegte Ströme in die Pfade 23, die mit den Eingängen der Verstärker 10 verbunden sind, einzuspeisen. Der Strom Ii stellt den Eingangsstrom zu dem Pfad 23 dar, der mit dem Verstärker i verbunden ist. Die Spannung Vi stellt die Ausgangsspannung des Verstärkers i dar.

Die das Zeitverhalten beschreibende Bewegungsgleichung der in Fig. 1 gezeigten Schaltungsanordnung ist durch

gegeben, wobei ui die Eingangsspannung des Verstärkers i ist, gi die Übertragungsfunktion des Verstärkers i, d. h. Vj = gj (uj) und

Es wurde bereits in der zuvor erwähnten, gleichzeitig anhängenden Anmeldung gezeigt, daß, wenn die Gleichung

berücksichtigt wird, und die Terme Tij und Tji gleich sind sowie die Verstärkung der Verstärker sehr groß ist, die nach der Zeit abgeleitete Gleichung (2) sich auf

reduziert. Der Klammerausdruck in Gleichung (3) entspricht der rechten Seite der Gleichung (1). Das bedeutet, daß eine Änderung (mit der Zeit) der Eingangsspannung am Verstärker i multipliziert mit der Änderung (mit Zeit) der Ausgangsspannung am Verstärker i, die über alle Verstärker aufaddiert wird, gleich dE/dt der Gleichung (3) und gleich dem Ausdruck ist:

Da keiner der Terme in Gleichung (4) negativ ist, ist dE/dt negativ und nähert sich dem Wert 0 (Stabilität), wenn dVi/dt sich für alle i dem Wert 0 nähert.

Nach der obigen Analyse bedeutet das, daß ein vorgelegtes Problem, das die für die obigen Gleichungen angegebenen Bedingungen erfüllt, durch die Schaltungsanordnung der Fig. 1 gelöst werden kann, wenn die Werte Tij und die Eingangsströme Ii geeignet ausgewählt werden, ein Anfangssatz von Verstärkereingangsspannungen bereitgestellt wird, und das Analog-System irgendwann in einen stabilen Zustand konvergiert.

Eine Klasse von Problemen, die auf diese Weise vorteilhaft gelöst werden kann, ist die Klasse von Zerlegungsproblemen, bei denen man versucht, ein Eingangssignal durch einen Satz "Bester Anpassung" anderer, nicht-orthogonaler Signale darzustellen. Ein solches Problem ist beispielsweise die Analog-Digital-Umsetzung. Ein anderes Beispiel ist die Zerlegung eines komplexen Signals (das durch eine Folge von Spannungsabtastwerten dargestellt wird), in einen Satz vorgewählter Funktionen.

Um unsere Erfindung verständlicher zu beschreiben, wird im folgenden die eingeschlagene Vorgehensweise erläutert, um das Problem bei der Analog-Digital-Umsetzung zu lösen. Danach werden die beschriebenen Konzepte soweit ausgedehnt, daß alle Klassen der Zerlegungsprobleme erfaßt werden.

In Verbindung mit dem Analog-Digital-Umsetzungsverfahren ist es bekannt, daß die Umsetzung eines Signals aus einer analogen Darstellung in eine digitale Darstellung bedeutet, daß ein analoges Signal x näherungsweise gleich der gewichteten Summe erzeugter digitaler Signale (V&sub1;, V&sub2;, . . . VN) ist, von denen angenommen wird, daß sie x darstellen. Das heißt ein Signal x', das eine Näherung des Signals x darstellt, kann folgendermaßen ausgedrückt werden:

Ein bekanntes Maß für die "Güte" von x' ist die quadratische Differenz zwischen dem Signal x und dem Signal x'. Dieser Gedanke ist in der folgenden Gleichung verkörpert:

Die Gleichung (6) gibt an, daß der optimale Wert von x' zu einem minimierten Wert von E führt. Ein Erweitern und Umformen der Gleichung (6) führt zu einer Form, die der Gleichung (1) plus einer Konstanten ähnlich ist, wodurch angedeutet wird, daß ein Analog-Digital-Wandler in der Tat mit einer Schaltungsanordnung realisiert werden kann, die der aus Fig. 1 ähnlich ist.

Leider liegen die durch die Gleichung (6) festgelegten Minima der Funktion nicht notwendigerweise nahe genug bei 0 und 1, um als digitale Logikpegel, die ein Analog-Digital-Wandler erzeugen muß, identifiziert zu werden.

Wir umgehen dieses Problem, indem ein zusätzlicher Term zu der Energiefunktion der Gleichung (6) hinzugefügt wird. Wir wählen den Term

denn er begünstigt digitale Darstellungen, da der Ausdruck Null wird, wenn alle Vi Terme auf 0 oder 1 beschränkt werden. Wenn die Gleichung (7) mit der Gleichung (6) kombiniert und umgeformt wird, ergibt sich die Gleichung

die auch der Form der Gleichung (1) entspricht, wenn wir die Verbindungsmatrixelemente und die Eingangsströme wie folgt kennzeichnen:

Tij = - 2(i+j)

und

Ii = (- 2(2i-1) + 2ix).

Fig. 2 stellt eine 4 Bit-Analog-Digital-Wandlerschaltung dar, die mit einer Verbindungsmatrix aufgebaut ist, die der Gleichung (8) genügt. Die Analog-Digital-Wandlerschaltung weist auf: invertierende Verstärker 10 mit Eingangsleitungen 22 und Ausgangsleitungen 23, eine Verbindungsmatrix 20, die die Leitungen 23 mit den Leitungen 22 über Knoten 21 verbindet, und eine Verbindungsmatrix 30, die eine Referenzspannung -V (z. B. -1 Volt) an eine Leitung 31 und ein Eingangssignal x an eine Leitung 32 anlegt. Beide Signale -V und x kommunizieren über Knoten 33 mit den Leitungen 22.

Gemäß der Spezifikation der Gleichung (8) nimmt jedes Element Tij den Wert 2i+j (mit Ausnahme bei i = j, wo Tij nicht existiert) an. Das sind die in Fig. 2 verstärkt dargestellten Verbindungen. Gemäß der Spezifikation der Gleichung (8) besitzt jeder Eingangsstrom Ii den Wert - 22i-1 + 2ix. Die Matrix 30 realisiert diese Ströme über die verstärkt dargestellten Verbindungen, die Leitwertelemente mit einem spezifizierten Wert darstellen.

Wie früher bereits erwähnt, dient das hier vorgestellte Analog- Digital-Umsetzungsverfahren lediglich erläuternden Zwecken, wobei viele Zerlegungsprozesse mit einer Schaltung, wie sie in Fig. 2 gezeigt ist, ausgeführt werden können.

Wenn beispielsweise einen Satz Grundfunktionen (beispielsweise Gaußfunktionen) darstellt, die den Signalraum x (Signalabtastwerte) umfassen, dann beschreibt die Funktion

ein Netzwerk, das ein Energieminimum hat, wenn die digitale Kombination "Bester Anpassung" der Grundfunktionen ausgewählt wird (mit Vi = 1), um das Signal zu beschreiben. Der Term stellt übrigens das Skalarprodukte des Signals mit sich selbst dar. Die Gleichung (9) kann erweitert und umgeformt werden, um die Form

anzunehmen, wobei die Gleichung (10) der Form der Gleichung (1) plus einer Konstanten entspricht. Daß heißt, wie bei Gleichung (8), können die Terme Tij und Terme Ii festgelegt werden, damit die Gleichung (10) mit Gleichung (1) übereinzustimmen scheint, und dabei eine Entsprechung zwischen den Elementen in der Gleichung und den physikalischen Parametern des in der Fig. 2 gezeigten Netzwerkes zu erzielen. Für die Gleichung (10) gilt speziell

®.

Ein Beispiel könnte angebracht sein.

Es wird das Problem der Zerlegung einer Zeitfolge analoger Signale betrachtet, die sich aus der linearen Addition zeitlich getrennter Gaußimpulse unterschiedlicher Breite ergeben. Ein typisches summiertes Signal ist in Fig 3 dargestellt, wobei die verschiedenen Gaußimpulse, aus denen das Signal zusammengesetzt ist, in Fig. 4 dargestellt sind. Der Zerlegungsprozeß muß diesen besonderen Untersatz aller möglichen Grundfunktionen bestimmen, die, wenn sie aufaddiert sind, das Signal in Fig. 3 wiederherstellen. Wie durch die Punkte 100 auf der Kurve in Fig. 3 angedeutet, ist eine Vielzahl von Abtastwerten von dem Signal der Fig. 3 verfügbar, wobei diese Abtastwerte die analogen Daten xi mit i = 1, 2, . . . , N enthalten. Der Basissatz, der alle möglichen "Pulse" festlegt, entspricht den Gaußfunktionen der Form

wobei der Breitenparameter σ eine endliche Anzahl von Werten annimmt, während die Spitzenposition des Impulses t irgendeinen der N Augenblicke darstellen kann, zu denen die Abtastwerte des in Fig. 3 dargestellten Signals abgetastet werden. Da der Basissatz durch zwei Parameter spezifiziert ist, nämlich die Breite und die Spitzenposition, können die in dem Zerlegungsnetzwerk verwendeten Verstärker günstigerweise mit den beiden Indizes σ, t indiziert werden. Bei der Beschreibung der Zerlegung enthält jede dieser Grundfunktionen einen digitalen Koeffizienten (Vσt), der dem Ausgangssignal eines Verstärkers in dem Netzwerk entspricht und der das Vorhandensein oder das Fehlen dieser Funktion in dem zu zerlegenden Signal darstellt. Für V20,10 = 1 bedeutet das beispielsweise, daß eine Gaußfunktion mit einer Spitze im Zeitpunkt des Abtastwertes 20 und mit einer Breite von 10 in dem Lösungssatz enthalten ist.

Unter Berücksichtigung des oben Gesagten, gilt für die Energiefunktion, die ein analoges, dieses besondere Zerlegungsproblem lösendes Rechennetzwerk beschreibt:

mit der Grundfunktion, wie sie in Gleichung (12) definiert ist. Dieser Ausdruck definiert einen Satz von verstärkten dargestellten Verbindungen Tσt,σ't' und Eingangsströme Iσt, mit:

Ein Rechennetzwerk zur Ausführung der obigen Verarbeitung stimmt im wesentlichen mit dem in Fig. 2 gezeigten Netzwerk überein. Der einzige Unterschied ist der, daß anstelle eines einzelnen Eingangssignals x eine Vielzahl von Eingangssignalabtastwerten xi verwendet wird, die je mit einer Leitung 32 verbunden sind, die über die Verbindungsmatrix 30 Ströme an die Verstärker 10 gemäß der Gleichung (16) führen. Diese Schaltungsanordnung ist in ihrer allgemeinen Form in Fig. 5 gezeigt, und zwar mit Leitungen 32-1 bis 32-4, die eine Vielzahl von Eingangsleitungen aufweisen, an die jeweils ein Signalabtastwert angelegt wird und über die jeder Signalabtastwert mit allen Verstärkern verbunden wird.

Wie erläutert, sucht unsere Schaltungsanordnung einen minimalen stabilen Zustand, die aber eine Anzahl anderer stabiler Zustände aufweist, die lokale Minima bilden. Dieser Zustand ist in Fig. 6 durch die Kurve 100 dargestellt, in der der niedrigste stabile Zustand im Schaltungszustand S4 im Punkt 104 auftritt und lokale Minima in den Zuständen S1, S2, S3, S5, S6, S7, S8 und S9, auftreten, die den jeweiligen Punkten 101-109 (ausgenommen Punkt 104) auf der Kurve 100 entsprechen.

Wir haben entdeckt, daß die Verstärkung der Verstärker 10 in unserer Schaltungsanordnung eine Steuerung über die Kurvenform 100 auf eine Art und Weise darstellt, die dem Ausglühverfahren ähnlich ist. Da bei einigen Spinglas- Problemen von der Beschreibung eines effektiven Feldes, das kontinuierlich den hohen Temperaturen zu niedrigeren Temperaturen gefolgt ist, erwartet wird, daß sie zu einem Zustand nahe des thermodynamischen Grundzustandes führt, beginnen wir bei unseren Schaltungsanordnungen mit niedrigen Verstärkungen der Verstärker und erhöhen sie langsam auf ihre höchsten Werte. Dies führt zu besseren Rechenergebnissen.

Dieses Verhalten kann heuristisch dadurch verstanden werden, daß man die Kurve 110 in Fig. 6 betrachtet, die der Schaltungsenergiefunktion entspricht, wenn die Verstärkung niedrig ist, und die Unstetigkeiten in dem Kurvenverlauf in Punkten aufweist, die den Punkten S1 bis S9 (Ecken) entsprechen. Dennoch steigt oder fällt die Kurve auf beiden Seiten des Punktes 114, der dem Tiefpunkt der Kurve 110 entspricht, monoton. Die anderen Ecken in der Kurve sind keine lokalen Minima und darum wird unsere Schaltung, wenn wir die Verstärkungen auf einen unteren Wert setzen, nicht in diesen Punkten bleiben, sondern sich zu dem Punkt 114 bewegen. Wenn die Verstärkung erhöht wird, stabilisiert sich unsere Schaltung einfach und schnell in dem Tiefpunkt, d. h. dem Punkt 104.

Ein Beginnen einer Berechnung in einem niedrigen Verstärkungszustand initialisiert die Schaltungsanordnung. Bei sich ändernden Eingangssignalen, beispielsweise wenn der Analog-Digital-Wandler eine schwankende Spannung mißt, kann die Schaltung dann am besten arbeiten, wenn die Verstärkung für jede neue Entscheidung wieder initialisiert wird.

Das Leistungsmerkmal der Verstärkungssteuerung, die auf herkömmliche Weise ausgeführt werden kann, ist in Fig. 5 durch eine Linie 40 erläutert, die mit einem Verstärkungssteuerpunkt mit allen Verstärkern 10 verbunden ist. Eine Änderung der Spannung auf der Leitung 10 führt zu einer Änderung der Verstärkung der Verstärker 10, die die erwünschte Hochfahr-Aktion oder Wiederinitialisierung hervorruft.