DE2423265B2 - Optimierende Rechenmaschine - Google Patents

Description

Die Erfindung betrifft eine optimierende Rechenmaschine nach dem Oberbegriff des Patentanspruchs 1.

Sehr komplexe Aufgaben der sog. Ablaufplanung kommen auf zahlreichen Gebieten vor, z. B. im Luft- und Eisenbahnverkehr, bei der Erzeugung und Verteilung von Energie, die Herstellung von Kraftfahrzeugen mittels Rohstoffen und Teilen aus verschiedenen Werken usw. Derartige Ablaufplanungs-Aufgaben mit sehr zahlreichen Variablen könnten an sich durch einzelne Digitalrechner gelöst werden, falls diese eine ausreichend große Speicherkapazität und hinreichend kleine Rechenzeiten haben. Tatsächlich werden zur Lösung derartiger Ablaufplanungs-Aufgaben umfangreiche Sätze von Digitalrechnern verwendet, die dann in ca. zehn Minuten eine Lösung finden.

Falls es jedoch zu einer plötzlichen Betriebsstörung im Betriebsablauf kommt, ist es bisher unmöglich, in kurzer Zeit eine neue Lösung der betreffenden Ablaufplanungs-Aufgabe zu ermitteln, da die verwendeten Digitalrechner nicht so leistungsfähig sind, obwohl eine schnelle Umstellung der Ablaufplanung insbesondere im Verkehrswesen und bei der Verteilung elektrischer Energie äußerst erwünscht ist. y-,

Zur Beschreibung der Ablaufplanungs-Probleme bedient man sich des Begriffs »System«, d. h., die jeweilige Anwendungsrealität der Ablaufplanung kann durch ein System beschrieben werden.

Bekanntlich können die verschiedenen Zustände wi eines durch eine bestimmte Anzahl von Variablen definierten Systems durch die einzelnen Punkte eines geometrischen Raums, dessen Anzahl an Dimensionen gleich der Anzahl der System-Variablen entspricht, dargestellt werden. Ein Systemzusland entspricht also b-> danach einem Raumpunkt, so daß der Übergang des Systems von einem Zustand in einen anderen dem Weg von einem Rmimpiinkt /u einem anderen gleichwertig ist. Sofern die Anzahl dieser Raumpunkte endlich ist, bedeutet dies eine Quantifizierung bzw. Digitalisierung des Raums und damit auch der System-Variablen.

Ziel der Ablaufplanung ist es nun, einen optimalen Übergang von einem Anfangszustand zu einem Endzustand des Systems zu finden, also einen optimalen Weg zwischen Anfangs- und Endpunkt des entsprechenden geometrischen Raums zu ermitteln, wobei der optimale Weg normalerweise unter Umgehung von Hindernissen im betreffenden Raum, also unter Ausschluß gewisser System-Zustände, gefunden werden muß.

Verfahren zur Ermittlung des kürzesten Wegs zwischen zwei durch Hindernisse getrennten Punkten in einer Ebene sind bereits bekannt.

So ist es z. B. bekannt (E. F. M ο ο r e, »The shortest path through a maze«, Annals of the Computation Laboratory of Harvard University, Bd. 30,1959, S. 285), in jedes Koordinaten-Kästchen der von einem Koordinatennetz überzogen gedachten Ebene die Anzahl der Schritte einzuschreiben, um die das betreffende Kästchen von dem Anfangspunkt getrennt ist. Genauer gesagt, mit z. B. A als Anfangspunkt und B als Endpunkt wird in die an das Kästchen mit A angrenzenden Kästchen die Ziffer »1« eingeschrieben, worauf in sämtliche Kästchen, die an Kästchen mit »1« angrenzen, die Ziffer »2« eingeschrieben wird usw. Nach η Schritten ist dann der Endpunkt B erreicht. Der kürzeste Weg wird nun so ermittelt, daß man ausgehend vom Endpunkt B jeweils die benachbarten Kästchen verbindet, deren Inhalt bei jedem Schritt um »1« abnimmt.

Dieser bekannte Algorithmus gibt zwar außer dem optimalen Weg auch dessen Länge an (n Schritte im vorhergehenden Beispiel), jedoch müßte eine optimierende Rechenmaschine, die nach diesem Algorithmus arbeitet, notgedrungen N² Speicherplätze aufweisen, wenn die Anzahl der quantisierten bzw. digitalisierten Werte, die von jeder der beiden Variablen bzw. Koordinaten der Ebene angenommen werden kann, gespeichert wird. Da normalerweise N die Größenordnung von einigen Tausend hat, verbietet sich ein derartiges Vorgehen, weil die Anzahl der Speicherplätze gleich N₂ ist, also mehr als eine Million betrüge Außerdem müßten diese Speicherplätze so beschaffen sein, daß sie eine Zahl mindestens gleich der Länge des optimalen Wegs speichern, was in vielen Fällen sich derr Wert 2Λ/ nähern würde und damit wieder zu Speicherschwierigkeiten führte.

Zur Vermeidung des zuletzt genannten Nachteils is< es zwar bereits bekanntgeworden (vgl. S. B. A k e r s, A modification of Lee's path connection algorithm, IEEE Transactions on Electronic Computers, Bd. EC-K [1967], S. 97), die in den Kästchen eingeschriebener Zahlen eine derartige Folge bilden zu lassen, daß dii einem Symbol dieser Folge vorangehende Zahl von de nachfolgenden Zahl verschieden ist, um auf diese Weisi die Speicherelemente so vorzusehen, daß sie nur eim begrenzte Anzahl von Bits speichern, z. B. 2. Eine diesel Algorithmus anwendende optimierende Rechenmaschi ne müßte aber immer noch N² Speicherplätze aufwci sen.

Ähnliche Schwierigkeiten hinsichtlich der notwcndi gen Anzahl von N² Speicherplätzen würden bei de Anwendung eines anderen bekanntgewordenen Alge rithmus (C. Y. L c c, »An algorithm for path connection and its applications«, IEEE Transaction on Electroni Computers, Bd. F-C-IO, S. 346-365, September 1961

auftreten, bei dem folgendermaßen iterativ vorgegangen wird:

Zunächst wird in sämtliche Kästchen der Ebene »0« eingeschrieben, während eine »1« in das Kästchen mit dem Endpunkt A eingeschrieben wird. Darauf wird in ^r> sämtliche Kästchen, die noch eine »0« enthalten und an Kästchen mit bereits eingeschriebener »1« angrenzen, eine »1« eingeschrieben. Das Einschreiben der Einsen schreitet so lange schrittweise fort, bis nach η Schritten ein Kästchen L erreicht ist, von dem aus man mit einem einzigen Schritt das Kästchen mit dem Endpunkt B erreichen kann.

Der sog. erste optimale Elementarvorgang, dem das System unterworfen werden muß, ist dann der, der das System von B in L überführt. Ist dieser erste optimale Elementarvorgang ausgeführt, so werden sämtliche Kästcheninhalte der Ebene auf »0« gebracht (gelöscht), und der Prozeß wird durch erneutes Einschreiben einer »1« wiederholt, wobei jedoch der Punkt L als neuer Endpunkt genommen wird. Nach n— 1 Schritten wird ein Punkt M erreicht, von dem aus der Punkt L mit einem einzigen Schritt erreicht werden kann, so daß der zweite optimale Elementarvorgang derjenige ist, der das System vom Punkt L in den Punkt M überführt.

Das betreffende Verfahren wird entsprechend durch Iteration fortgesetzt, bis man am Anfangspunkt A angekommen ist. Die Gesamtzahl der dabei ausgeführten Schritte beträgt

30

mit η = Länge des kürzesten Wegs zwischen A und B.

Eine nach diesem bekannten Verfahren arbeitende Rechenmaschine würde nicht nur immer noch N² Speicherplätze benötigen, sondern bei ihr könnte auch die Rechenzeit sehr lang werden, wenn die Länge des optimalen Wegs sehr groß ist, wie deutlich die vorstehende Formel für die Gesamtzahl der auszuführenden Schritte zeigt, selbst wenn die Anzahl der Einschränkungen sehr gering wäre.

In diesem Zusammenhang ist es noch bekanntgeworden (vgl. C. Y. L e e, a.a.O.), worauf noch weiter unten genauer einzugehen sein wird, die Änderung des numerischen Inhalts der Kästchen in der für das System repräsentativen Ebene durch Ausbreitung einer gedachten Welle in dieser Ebene zu simulieren, wobei jedes v> Kästchen die Welle der vorangehenden angrenzenden Kästchen empfängt, ausgenommen nur diejenigen Kästchen, die verbotenen Zuständen — Einschränkungen — des Systems entsprechen, da diese Kästchen die Welle nicht fortpflanzen können.

Erreicht diese gedachte Welle einen der dem Zielpunkt vorausgehenden Punkte, so kann eine erste optimale Elementarentscheidung getroffen werden. Da dieser optimale Elementarvorgang der erste gefundene ist, ist der Zielpunkt der Welle im allgemeinen τ, repräsentativ für den Anfangszustand des Systems, während der Ausgangspunkt der Welle dem Endzustand des Systems entspricht. Die sich ausbreitende gedachte Welle ist also eine rücklaufende Welle in bezug auf Anfangs- und Endzustand des Systems, da sie sich von mi dessen Endzustand zu dessen Anfangszustand fortpflanzt und dabei die Kästchen- bzw. Zellen-Inhalte ändert.

Wohl gemerkt, es handelt sich bei dem Konzept der gedachten rücklaufendcn Welle nicht um eine physikali- h^r> sehe Realität, sondern nur um ein Denkmodcll zum leichteren Verständnis der zeitlichen Änderung des Inhalts der Koordinaten-Kästchen der das System darstellenden Ebene bzw. der entsprechenden Speicherund Rechenzellen in der Rechenmaschine selbst.

Es ist Aufgabe der Erfindung, eine optimierende Rechenmaschine der eingangs genannten Art zu schaffen, die die genannten Schwierigkeiten beim bekannten Stand der Technik überwindet, indem die Anzahl der bisher benötigten Speicherplätze von N³ beträchtlich verringert, aber auch die Rechenzeit beträchtlich verkürzt wird, indem die Wegesuche in der Koordinatenebene nicht mehr schrittweise erfolgt, sondern nur noch von Einschränkung zu Einschränkung, wobei schließlich auch keine zusätzlichen Speicherplätze erforderlich sein sollen, deren maximale Anzahl in die Größenordnung der Länge des optimalen Wegs kommt.

Die Lösung dieser Aufgabe erfolgt erfindungsgemäß durch die Lehre nach dem kennzeichnenden Teil des Patentanspruchs 1.

Die erfindungsgemäße Rechenmaschine kommt nicht nur mit 2N Speicherplätzen für Rechen- und Speicher-Zellen aus, was den baulichen Aufwand bei Zugrundelegung von N mindestens tausend erheblich verringert, sondern arbeitet praktisch in Echtzeit selbst bei sehr großer Anzahl der Einschränkungen. Die erfindungsgemäße Rechenmaschine löst also kombinatorische Aufgaben, für die die Rechenzeit eines Digitalrechners allein bisher zu lang war.

Zur Erläuterung des Unterschieds zwischen der erfindungsgemäßen Rechenmaschine und dem eingangs erörterten bekannten Stand der Technik sei auf das grundsätzlich für sich bekannte Konzept nach Lee zurückgegriffen, wonach die Änderung des Kästchenbzw. Zellen-Inhalts durch die Ausbreitung einer gedachten rücklaufenden Welle darstellbar ist:

Während bei Anwendung der bekannten Algorithmen die zugehörige optimierende Rechenmaschine notwendigerweise N² Speicherplätze zur Speicherung des Verlaufs der gesamten Welle im zu untersuchenden Teil der Ebene erfordert, interessiert bei der erfindungsgemäßen Rechenmaschine nicht mehr die ganze Welle, sondern nur die Wellenfront, weshalb man zur Beobachtung der Änderung der 2Λ/ Punkte der Wellenfront während ihrer Ausbreitung nur 2/V Speicherplätze benötigt.

Da außerdem die Wellenfront nur beim Auftreffen auf Einschränkungen (Hindernisse) gestört wird, also zwischen zwei Einschränkungen keine Änderung erfährt, braucht die Form der Wellenfront auch nur von Einschränkung zu Einschränkung untersucht zu werden, d. h., die früher betrachtete schrittweise Entwicklung der Welle fällt weg. Damit kann die erfindungsgemäße Rechenmaschine auch viel schneller als Rechenmaschinen, die die bekannten Algorithmen anwenden, arbeiten, so daß sie selbst bei praktisch unbegrenzter Anzahl von Einschränkungen Ablaufplanungs-Probleme im Echtzeitbetrieb löst.

Damit stellt der Inhalt der Speicher-Zellen bei der erfindungsgemäßen Rechenmaschine nicht mehr wie früher die Anzahl der von der Welle bis zum betreffenden Kästchen (Zelle) durchlaufenen Schritte dar, sondern nur die Abweichung zwischen der Anzahl der tatsächlich durchlaufenen Schritte und derjenigen Anzahl Schritte, die die gedachte Welle bei fehlenden Einschränkungen durchlaufen hätte. Mit anderen Worten, die Speicher-Zellen speichern nur noch die Verzerrung der Wcllcnfront beim Durchlaufen jeder Einschränkung gegenüber einer ohne diese Einschränkungen sich ausbreitenden, also ungestörten Bezugswcl-Ic.

Da unter Umständen diese Abweichung bzw. Verzerrung der Wellenfront verhältnismäßig groß werden könnte, so daß die entsprechenden Speicherelemente eine genügende Anzahl von Bits, ausgelegt für die maximal mögliche Abweichung, enthalten müßten, sieht die Erfindung weiter vor, nicht die Absolutwerte dieser Abweichung zu speichern, sondern nur jeweils ein lnkrement »0« oder »1«, je nachdem, ob sich die Wellenfront von Zelle zu Zelle ändert. Die Verarbeitung dieser Inkremente der Abweichung bzw. »Störung« der Wellenfront durch die Einschränkungen führt zu einer weiteren Vereinfachung der erfindungsgemäßen Rechenmaschine.

Vorteilhafte Ausgestaltungen der Erfindung sind in den Unteransprüchen angegeben.

Anhand der Zeichnung wird die Erfindung beispielsweise näher erläutert. Es zeigt

F i g. 1 eine Ebene, die ein System mit zwei digitalen Variablen beschreibt,

F i g. 2 eine ebene Darstellung, in der die Wellenfront rechteckig ist,

F i g. 3 ein Beispiel von Einschränkungen, um die dadurch für eine gedachte rücklaufende Welle entstehenden Störungen zu veranschaulichen,

Fig.4 die Abweichung zwischen einer ungestörten und einer durch eine Einschränkung gestörten Wellenfront,

F i g. 5 eine geometrische Konstruktion, mit der bei Kenntnis einer Einschränkung die durch sie gestörte Wellenfront konstruierbar :st,

F i g. 6 die Ermittlung der gestörten Wellenfront im Fall mehrerer Einschränkungen, von denen eine die Wellenfront nicht stört,

F i g. 7 die Ermittlung der Länge des Wegs, der von einem Ausgangspunkt der Welle zu einem Zielpunkt führt,

F i g. 8 die Definition der Diagonaladressen,

F i g. 9 das Blockschaltbild eines Ausführungsbeispiels der erfindungsgemäßen optimierenden Rechenmaschine, wobei sämtliche folgenden Figuren sich auf F i g. 9 beziehen,

F i g. 10 ein Organisationsbeispiel des Speichers in der Rechenmaschine,

F i g. 11 schematisch die Mittel zur Auswahl der im Diagonaladressen-Intervall JB, ///gelegenen Speicherstellen,

Fig. 12 ein Diagramm zur Erläuterung der Art und Weise der Auswahl des genannten Intervalls JB, HJ

Fig. 13 eine Logik K zur Freigabe geeigneter Ausgänge der Speicherplätze,

Fig. 14 das Schaltbild einer halben Speicher-Steckkarte mit Logiken zur Freigabe der Ausgänge,

Fig. 15 das Schaltbild eines Decodierers für niedere Diagonaladresse mit 3 Bits,

Fig. 16 das Schaltbild eines Decodierers für hohe Diagonaladresse mit 3 Bits,

F i g. 17 das Schaltbild eines Decodierers mit 4 Bits für niedere oder hohe Diagonaladresse,

F i g. 18 ein Blockschaltbild eines Addierers,

F i g. 19 eine Baugruppe des Addierers,

Fig.20 das Zusammenwirken der verschiedenen Baugruppen des Addierers,

F i g. 21 den Ausgang des Addierers,

F i g. 22 das Schaltbild einer Steuerschaltung Σ,

Fig.23 den Teil der Steuerschaltung, der den Vergleich von niederer und hoher Diagonaladresse ermöglicht,

F i g. 24 die gesamte Steuerschaltung,

F i g. 25 ein schematisches Schaltbild der Folgesteuereinrichtung und

F i g. 26 die verschiedenen Betriebsphasen der Folgesteuereinrichtung von F i g. 25.

ϊ Wie bereits weiter oben angegeben wurde, kann ein System mit η Variablen stets symbolisch durch die Punkte eines n-dimensionalen Raums dargestellt werden, wobei jeder Dimension eine Variable zugeordnet ist. In der Folge wird zur Vereinfachung vorausgesetzt,

ίο daß das System, für das ein optimales Fortschreiten gesucht wird, ein System mit zwei Variablen ist, so daß seine möglichen Zustände durch die Punkte einer Ebene dargestellt werden können. Die Verteilung der Punkte dieser Ebene kann mehrere Formen annehmen, wie aus F i g. 1 und 2 hervorgeht.

In der in F i g. 1 dargestellten Ebene nehmen die repräsentativen Punkte die Ecken von gleichseitigen Dreiecken ein. Die gedachte Welle, die die laufende Veränderung des Inhalts der Speicherelemente der

2(i optimierenden Rechenmaschine simuliert, breitet sich von Punkt zu Punkt, in Richtung der Pfeile, aus. Die Weglängen oder Schrittweiten zwischen den Punkten sind ab= ac= ad Die eingekreisten Punkte stellen die verbotenen Zustände des Systems dar, die die Welle nicht fortpflanzen, daher sind die Wege, die davon ausgehen, gesperrt. Die jedem Punkt zugeordneten Ziffern stellen die Anzahl ausgeführter Testschritte dar, ausgehend vom Anfangspunkt a. Die Wellenfront ist in diesem Fall ein Parallelepiped (Parallelogramm).

In F i g. 2 ist die Wellenfront rechtwinklig, und der Weg auf den Achsen X und Y zwischen zwei aufeinanderfolgenden Punkten ist dem Weg auf der Diagonale gleich. In der Folge wird zur Vereinfachung die repräsentative Ebene mit rechtwinkligen Achsen angenommen wie in F i g. 2.

In F i g. 3 ist eine Einschränkung (genau genommen ein Einschränkungs-Feld aus mehreren unmittelbar benachbarten Einschränkungen) dargestellt, die durch eine Menge \on »verbotenen« Punkten, die die Welle nicht fortpflanzen, definiert ist (zur leichteren Erklärung ist diese Einschränkung rechteckig). Die Zahlen in den Kästchen zeigen wiederum die Anzahl ausgeführter Schritte an, ausgehend vom Ausgangspunkt der Welle im Schnittpunkt der Achsen Xund Y, und gestatten die Darstellung der Wellenfront, insbesondere hinter der Einschränkung.

Enthält die Ebene nur eine Einschränkung, so zeigt Fig.4 die Abweichung zwischen der ungestörten Wellenfront Wund der gestörten Wellenfront Phinter der Einschränkung.

Die geometrische Konstruktion der gestörten Wellenfront kann auf einfache Weise, wie in Fig.5 angegeben ist, durch Projektion der Einschränkung auf die anfängliche, nicht gestörte Wellenfront Λ/Perfolgen, wobei zwei Schnittpunkte definiert werden, von denen aus die gestörte Wellenfront P aufgezeichnet werden kann.

Es ist möglich, daß gewisse Einschränkungen die Wellenfront nicht stören, z. B. die Einschränkung 2 in

bo Fig.6, da man im geraden Teil der Wellenfront keinen Ausschnitt vorsehen kann.

F i g. 7 erläutert die zu treffende elementare Entscheidung in bezug auf die Längen der drei Wege, die zu den drei, dem Endpunkt vorausgehenden Punkten führen.

Der Ausgangspunkt der Welle (die in Wirklichkeit den Endzustand des Systems darstellt, da die Welle rücklaufend ist) trägt die Bezeichnung D und der Zielpunkt (der den Anfangszustand des Systems

darstellt) trägt die Bezeichnung A. Die drei dem Punkt A vorausgehenden Punkte sind die Punkte A', A"und A'". Die Länge des bei /!"endenden Wegs ist beispielsweise gleich 14. Der vorausgehende Punkt (oder ggf. die vorausgehenden Punkte), für den die Länge minimal ist, bestimmt den ersten Elementarvorgang, dem das System unterzogen werden soll. Im Fall der Fig. 7 ist die kleinste der drei Längen gleich 14: diese Länge wird für die Punkte /!"und A'"gefunden. Der erste optimale Elementarvorgang bringt somit das System vom durch den Endpunkt A dargestellten Ausgangszustand zum durch den vorausgehenden Punkt A" dargestellten Zustand oder, im Sonderfall der F i g. 7, zum durch den Punkt /!'"dargestellten Zustand.

Der Punkt A" (oder A") wird dann als neuer Zielpunkt der Welle genommen, und eine neue Folge von Arbeitsschritten führt zum zweiten Elementarvorgang, ausgehend vom durch den Punkt A '"dargestellten Zustand, zum nächstfolgenden Zustand.

Nach und nach werden auf diese Weise sämtliche Elementarvorgänge gefunden, deren Gesamtheit den optimalen Übergang vom Anfangszustand in den Endzustand bildet.

Alle diese Betrachtungen über die Suche nach optimalen Elementarvorgängen in einer Ebene gelten zum großen Teil auch für die Verfahren nach dem bekannten Stand der Technik, wie dieser in den weiter oben angeführten Literaturstellen beschrieben ist.

In der Folge wird nun die erfindungsgemäße optimierende Rechenmaschine mit ihren wesentlichen Eigenschaften anhand von F i g. 8 und 9 und der Tabelle I beschrieben.

Die optimierende Rechenmaschine enthält P= 2Λ/ Zellen. Zum besseren Verständnis wird eine optimierende Rechenmaschine mit P= 18 Zellen betrachtet, was zur Verarbeitung des in Fig.8 gezeigten Problems ausreicht.

Jede der 18 Zellen ist durch eine Adresse, Diagonaladresse genannt, gekennzeichnet, wobei die Adressen von 0 bis 17 numeriert sind. Jede Zelle kann somit als einer jeden der 18 Diagonalen der repräsentativen Ebene zugeordnet betrachtet werden.

Jede Einschränkung wird in Speichermitteln durch zwei Zahlen gespeichert, wobei die eine »hohe Diagonaladresse« genannte Zahl, mit H bezeichnet, in der repräsentativen Ebene dem auf der höchsten Diagonale dieser Ebene gelegenen Punkt der Einschränkung entspricht und die andere »tiefe Diagonaladresse« genannte Zahl, mit B bezeichnet, dem auf der tiefsten Diagonale der Ebene gelegenen Punkt der Einschränkung entspricht.

Die Einschränkung Nr. 1 der F i g. 8 hat beispielsweise die Adressen H= 13 und B= 8. Der Inhalt einer Zelle mit der Adresse X wird symbolisch mit (X) bezeichnet.

Dieser Streifen von 18 Zellen dient dazu, die Störung bzw. Verzerrung der Wellenfront beim Vorbeilaufen an einer Einschränkung in 18 Punkten zu berechnen. Man könnte sich eine optimierende Rechenmaschine denken, für die die Rechen- und die Speicher-Zellen jeweils eine Zahl genau entsprechend der Abweichung, ausgedrückt in Anzahl von Schritten, der gestörten Wellenfront gegenüber einer ungestörten Wellenfront enthielten. Man würde dann also anfangs in den Zellen die Zahl »0« für die Zellen mit den Adressen von 0 bis Il einschließlich und die Zahlen »I«, »2«, »3«, »4«, »5« bzw. »6« in den Zellen mit den Adressen von 12 bzw. 17 einspeichern, wobei die Gesamtheit dieser Zahlen die Abweichung zwischen der anfänglichen rechteckigen

lü

15

20

25

30

35

40

50

55

(1O

b5 Wellenfront von F i g. 8 und einer linearen theoretischen Wellenfront darstellen würde, die mit der Achse OK zusammenfällt. Hier werden jedoch Berechnung und Speicherung der Zunahme der Abweichung vorgezogen, wenn man von einer Zelle zur folgenden geht, gegenüber der eigentlichen Abweichung. Diese Zunahme ist nämlich eine sehr einfache Zahl zwischen zwei aufeinanderfolgenden Zellen, da sie nur »1« (wenn die Abweichung um eine Einheit zunimmt) oder »0« (wenn die Abweichung sich nicht ändert) sein kann. Die 18 Zellen der optimierenden Rechenmaschine können daher ein »Inkrement« berechnen und speichern, dessen Wert entweder »0« oder »1« ist. Zu Beginn ist das Inkrement der Zellen gleich 0 für die Zellen mit den Adressen von »0« bis »11« einschließlich, und dieses Inkrement wird »1« für die Zellen mit den Adressen von 12bisl7.

Zur Verarbeitung einer Einschränkung, die durch ihre hohe Diagonaladresse H und ihre niedrige Diagonaladresse B definiert ist, führt die optimierende Rechenmaschine die folgenden Operationen aus:

Unterhalb der niederen Diagonaladresse bleiben die Inkremente unverändert;

ab der niedrigen Diagonaladresse, nämlich für B+\, 5+2 usw. bis B+S, wird S-mal »1« eingeschrieben, wobei S gleich (H)-(B) ist, d. h.

gleich der Anzahl der Inkremente, die vor der Verarbeitung der jeweiligen Einschränkung in den Zellen mit den Diagonaladrossen B+\ bis H gezählt wurden (welches Diagonaladressen-Intervall symbolisch JB, ///abgekürzt wird),

in den Zellen mit den Diagonaladressen B+S+\ bis H wird das Inkrement »0« gespeichert und

jenseits der Zelle mit der Diagonaladresse H bleiben die Inkremente unverändert.

Die Verarbeitung der Einschränkungen erfolgt also

unter Feststellung des Inhalts des Zielpunkts, was dadurch erhalten wird, daß die Summe aller »1«-Bits gebildet wird, die bis zu diesem Zielpunkt enthalten sind.

Tabelle I

I	H	III	IV	V
Adresse	Anfangs-	Anfangs-	Inkrement	Inkrement
	abwei	inkrement	nach Ein	nach Ein
	chung		schrän	schrän
			kung Nr. 1	kung Nr. 2
17	6	1	1	1
16	5	1	1	0
15	4	1	1	1
14	3	i	1	1
13	2	1	0	1
12	1	1	0	0
11	0	0	0	0
10	0	0	1	1
9	0	0	1	1
8	0	0	0	0
7	0	0	0	0
6	0	0	0	0
5	0	0	0	0
4	0	0	0	0
3	0	0	0	0
2	0	0	0	0
1	0	0	0	0
0	0	0	0	0

Tabelle I erläutert den Algorithmus. In Spalte 1 dieser Tabelle stehen die von 0 bis 17 numerierten Diagonaladressen und in Spalte II die Anfangsabweichung der Zellen. In Spalte III stehen die den Abweichungen der Spalte II entsprechenden Inkremente. Dieses Inkrement ist gleich »0« bis zur Adresse 11 und gleich »1« von Adresse 12 bis Adresse 17. Spalte III stellt folglich den Anfangszustand der Zellen dar, wenn diese zur Verarbeitung der Inkremente gedacht sind.

Nach der Verarbeitung der ersten, durch die Adressen B=8 und //=13 definierten Einschränkung findet man in den Zellen ein Inkrement gleich 0 oder 1, je nachdem, ob der Zellenabweichung identisch oder um Eins höher als die Abweichung der vorausgehenden Zelle ist. Nach der Verarbeitung dieser ersten Einschränkung sind dann die neuen Inkremente diejenigen der Spalte IV.

In Spalte V sind die aufeinanderfolgenden Inkremente nach der zweiten Einschränkung aufgezeichnet. Zwischen den Adressen B= 12 und //=16 wurden 3 Einsen gezählt, und in Spalte V findet man von der in Adresse 12+1 =13 an drei Einsen, jeweils in 13, 14 und

15, wobei das Intervall 12 — 16 nachher, bei der Adresse

16, durch eine »0« vervollständigt wird.

In Tabelle I wurde die Verarbeitung der Einschränkungen 3 und 4, die auf dieselbe Weise wie die Einschränkungen 1 und 2 verarbeitet würden, nicht dargestellt.

Zusammenfassend sieht man, daß für jede Verarbeitung die folgenden Arbeitsschritte ausgeführt werden:

30

— Summierung sämtlicher Einsen im Intervall JB, H] was die Summe Sergibt,

— Nullrückstellung (Löschung) der im Intervall JB, H] enthaltenen Zellen,

— Einschreiben einer Anzahl Einsen gleich der vorher berechneten Summe S, ausgehend von der unmittelbar nach der niederen Diagonaladresse gelegenen Adresse, anschließend Einschreiben von Nullen bis zur hohen Diagonaladresse,

— nach der letzten Verarbeitung führt man die Summierung sämtlicher eingeschriebenen Einsen bis zum Zielpunkt einschließlich durch, was die charakteristische Länge dieses Zielpunkts ergibt.

Das Blockschaltbild des Ausführungsbeispiels der erfindungsgemäßen optimierenden Rechenmaschine in Fig.9, die die eben genannten Operationen ausführt, besitzt die folgenden Baugruppen: ή>

einen Speicher Mmit P= 2/V Bit-Stellen, wobei jedes Bit ein Inkrement für eine Zelle darstellt,
eine Freigabeeinrichtung Vzur Freigabe aller Ausgänge der im Diagonaladressen-Intervall von B+1 bis H — JB, HJ- enthaltenen Speicherstellen, «

einen mit dem Ausgang des Speichers M über die Freigabeeinrichtung V verbundenen Addierer ADDi zum Addieren aller im Intervall JB, H] enthaltenen »1«-Bits,

eine Löscheinrichtung RZ zum Löschen der Speicher- «1 stellen des Speichers Aiim Intervall JB, HJ
eine Schreibeinrichtung Ezum Schreiben
einer Anzahl »1 «-Bits gleich der Summe 5, ausgehend von der Diagonaladresse B+ 1 bis zu X= B+ S, und
von »O«-Bits von der Diagonaladresse X+ 1 bis zu H, (,--, und

eine an einen Digitalrechner ORD angeschlossene Folgesteuereinrichtung SEQ, die:

ix) das Schreiben und Lesen im Speicher M, die Freigabeeinrichtung V und den Addierer ADD I bei jeder Verarbeitung einer Einschränkung steuert,

ß) einen Übergang von der Verarbeitung einer Einschränkung zur Verarbeitung der nachfolgenden Einschränkung gestattet und

y) nach der letzten Verarbeitung gestattet, die Summe der eingeschriebenen »1 «-Bits bis zur Diagonaladresse der Zellen, die den drei Folgezuständen des Anfangszustands entspricht, zu entnehmen.

Im folgenden werden Ausführungsbeispiele der Baugruppen von F i g. 9 genauer beschrieben, wobei noch einmal darauf hingewiesen werden soll, daß die Verarbeitung nur der Inkremente der Abweichung, nicht der Abweichungen selbst, zwischen ungestörter und durch die Einschränkungen gestörter Wellenfront den baulichen Aufwand weiter beträchtlich reduziert.

Aufbau des Speichers M

Der Speicher M hat so viel Bit-Stellen als Zellen vorhanden sind, d. h. P Bit-Stellen, wobei jedes Bit das lnkrerr.ent mit d:m Wert »0« oder »1« für die entsprechende Zelle darstellt. Um zu vermeiden, daß gleichzeitig die den P Zellenadressen zugeordneten P Speicherinhalte zu verarbeiten sind, ist es vorteilhaft, den Speicher zu 2i Zeilen mit je 2^r Bits zu organisieren, mit P=2i^+r. Die Zeile, der eine Adresse zugeordnet ist, ist dann durch die q Bits höchsten Gewichts der besagten Adresse definiert. Zur Vereinfachung der Schreibweise und nur zum besseren Verständnis wird im folgenden ein Speicher mit 2048 Stellen (2") betrachtet, der zu 2⁴=16 Zeilen mit 2⁷ = 128 Bits organisiert ist. Jede Zeile wird dann vorteilhafterweise in 16 Bytes zerlegt, die von /= 1 bis 16 numeriert sind, wobei die Bits eines Byte von J= 1 bis /=8 numeriert sind. Jedes der 128 Bits einer Zeile ist somit durch eine Schreibweise mit zwei Indizes Ai^bezeichnet.

Der Grundaufbau des Speichers M in diesem Sonderfall ist durch Fig. 10 illustriert. Der Speicher ist aus integrierten Schaltkreisen aufgebaut, von denen jeder 16 Worte zu 4 Bits enthält. Zwei integrierte Schaltkreise in Serienschaltung bilden 16 Bytes. 32 Schaltkreise in Serie gestatten folglich die Bildung von 16 Zeilen zu 128 Bits.

Die Ein- und Ausgänge des Speichers sind jeweils oben und unten in der genannten Figur durch 128 senkrechte Striche dargestellt. Eine Schreib-Lesesteuerleitung E/L gestattet es, jede der integrierten Schaltkreise mit einem Schreib- oder Lesebefehl zu adressieren. Die Ein- und Ausgangs-Schaltkreise der Speicherplätze sind in dieser Figur nicht abgebildet und werden später beschrieben.

Es können Speicherschaltkreise verwendet werden, die während der Lesephase auf jeden Ausgang das Komplement zum gespeicherten Bit geben. Zum Schreiben einer Information genügt es, die Schreib- und Lese-Steuerleitung E/L auf »1« zu bringen und die im adressierten Wort zu speichernde Information auf die Eingänge zu schalten.

Die den Speicher bildenden Schaltkreise können z. B. einbaufertige Schaltungen vom Typ SN 7489 N sein.

Mit einem solchen zu 16 Wortzeilen organisierten Speicher werden die 4 hochgewichteten Bits einer Adresse, die 11 umfaßt, zur Auswahl einer Zeile unter den 16 vorhandenen bestimmt. Die Gesamtheit dieser 4 hochgewichteten Bits wird nachstehend mit B, für die

niedere Diagonaladresse und mit H_x für die hohe Diagonaladresse bezeichnet oder allgemein mit A\.

Aufbau der Auswahlschaltung für das Intervall JB, H]

Wie bereits oben erklärt wurde, ist es notwendig, sämtliche Ausgänge der im Intervall ]B, H]enthaltenen Speicherplätze anzusteuern, damit der Addierer ADD i die Summation aller in diesem Intervall enthaltenen »1 «-Bits durchführen kann.

Es ist zweckmäßig, diese Freigabe in zwei Stufen durchzuführen, durch Ansteuerung einerseits der links von B gelegenen Ausgänge und andererseits derjenigen, die rechts von H gelegen sind, mit anschließender Kombination dieser beiden Ansteuerungen. Diese Art der Freigabe benutzt also »Dreieck«-Decodierer in dem Sinne, daß ihre Wahrheitstabelle eine dreieckförmige Konfiguration aufweist, wie eine solche in der untenstehenden Tabelle II für den Fall von 3 Bits dargestellt ist. Der komplementäre Decodierer, in dem »0« durch »1« ersetzt wurden und umgekehrt, wäre selbstverständlich ebenfalls ein »Dreieck«-Decodierer.

Tabelle II

abc 1234567

000
00 1
0 1 0

0 1 1

1 00
1 0 1
1 1 0
1 1 1

0000000
1000000
100000

1 1

1 1 1

1 1

1 1

1 1 1

0000
000
1100
1110
1 1 1

Die Komplexität eines »Dreieck«-Decodierers steigt mit der Anzahl Bits sehr rasch an. Daher ist es vorzuziehen, die Anzahl der zu verarbeitenden Bits zu unterteilen, was dazu führt, mehrere Decodierer zu kombinieren. Zu diesem Zweck ist vorgesehen, jede Zeile mit 128 Bits in 16 Bytes zu unterteilen, wodurch es gestattet wird, eines der Bits einer Zeile durch zwei Adressen zu adressieren, eine mit 4 Bits zur Ansteuerung eines Bytes unter den 16 vorhandenen und eine mit 4^r> 3 Bits zur Ansteuerung eines Bits unter den 8 vorhandenen.

Das heißt, eine beliebige Adresse A mit 11 Bits ist in ein aus 4 Bits mit hohem Gewicht gebildetes Wort A_x, ein aus 4 Bits mit mittlerem Gewicht gebildetes Wort Ai und ein aus 3 Bits mit niedrigem Gewicht gebildetes Wort Ai unterteilt (diese Wörter sind jeweils für die niedere Diagonaladresse mit B₁, B₂, Bj und für die hohe Diagonaladresse mit Hi, H₂, ^bezeichnet).

Die Freigabeeinrichtung V für die Ausgänge der im w Intervall ]B, H]enthaltenen Speicherplätze ist genauer in F i g. 11 abgebildet und enthält einen Decodierer DECOD B für die niedere Diagonaladresse und einen Decodierer DECOD H für die hohe Diagonaladresse. Der Decodierer DECOD B für die niedere Diagonal- «ι adresse enthält einen Decodierer DECOD B\ mit 4 Bits, einen Decodierer DECOD B₂ mit 4 Bits und einen Decodierer DECOD B₁ mit 3 Bits. Der Decodierer DECOD H für die hohe Diagonaladresse enthält in entsprechender Weise einen Decodierer DECOD H₁ ^ mit 4 Bits, einen Decodierer DECOD H₂ mit 4 Bits und einen Decodierer DECOD Hi mit 3 Bits.

Der Decodierer DECOD B₂ besitzt 4 Eingänge und 1 b Ausgänge, die in der Folge mit B'₂ bezeichnet werden, wobei / von 1 bis 16 variieren kann. Der Decodierer DECOD B₃ besitzt 3 Eingänge und 8 mit Bi bezeichnete Ausgänge, wobei; von 1 bis 8 variiert.

Der Decodierer DECOD H₂ besitzt 4 Eingänge und 16 mit Hi bezeichnete Ausgänge, wobei /von 1 bis 16 variieren kann, der Decodierer DECOD H3 3 Eingänge und 8 mit Hl bezeichnete Ausgänge, wobei ebenfalls j von 1 bis 8 variiert.

Die Decodierer DECODB_x und DECODH_x gestatten die Freigabe einer Zeile. In dieser Zeile werden die Stellen jeweils durch die Decodierer DECOD B₂ - DECOD B3 für die niedere Diagonaladresse und durch die Decodierer DECOD H₂ - DECOD H₃ für die hohe Diagonaladresse freigegeben. Letztere Freigabe einer Zeile erfolgt durch Freigabe-Logiken VAL Jeder Ausgang S'-J der Speicherstelle M'-J ist mit einer Freigabe-Logik VA L und dem Addierer ADDi verbunden.

Wie in F i g. 13 dargestellt, enthält die Freigabe-Logik VAL zur Freigabe der Speicherausgänge im Intervall ]B, H/ein jedem Ausgang zugeordnetes logisches Verknüpfungsglied P-J, genauer ein NOR-Glied, das an den Ausgang einer jeden Speicherstelle M'-i angeschlossen ist, wobei der Ausgang des NOR-Glieds an den Addierer ADDi angeschlossen ist. Einer der beiden Eingänge des NOR-Glieds ist mit dem Ausgang S'-i der Speicherstelle M'i verbunden und der andere Eingang mit dem Ausgang einer Logik K'-i, von der nachstehend das Funktionsprinzip und der Aufbau angegeben werden.

In Fig. 12 sind die 128 Stellen einer Speicherzeile schematisch dargestellt. Diese Speicherstellen sind, wie bereits weiter oben erklärt, durch eine Notation mit zwei Indizes bezeichnet: M'i. Die schraffierte Speicherstelle ist die übliche Stelle des /-ten Byte und des /-ten Bits in diesem Byte. Zunächst wird vorausgesetzt, daß die niedere Diagonaladresse B und die hohe Diagonaladresse H der zu verarbeitenden Einschränkung in derselben Zeile auftreten, d. h. B₁ = H_x. Der Fall B_x φ H_x wird später besprochen.

Zur Freigabe des Intervalls ]B, H] werden die links von B (B einschließlich) gelegenen Ausgänge und die rechts von H (H ausschließlich) gelegenen Ausgänge angesteuert.

Im Rahmen der Fig. 12 wird vorausgesetzt, daß die schraffierte Speicherstelle M'-J der niederen Diagonaladresse entspricht, links von der die Ausgänge angesteuert werden sollen.

Die Ansteuerungen (Freigaben oder Sperrungen) erfolgen mit Hilfe von dreieckförmigen Decodierern, denen die Konfiguration der in Tabelle 1 abgebildeten Wahrheitstabelle gegeben wurde.

Im folgenden wird der logische Zustand eines Decodiererausgangs mit einem kleinen Buchstaben bezeichnet, z. B. bi für den logischen Zustand des Ausgangs B\ des Decodierers DECOD B₂ oder hj, für den logischen Zustand des Ausgangs Hi des Decodierers DECOD Hi.

Schließt man nun die Speicherstellen Af ■', Af-²

Af-⁸ direkt an den Ausgang S] des Decodierers B₂ an

und die Speicherstellen Al²·¹, Af²² AP-⁸ an den

Ausgang B\ usw., so werden sämtliche Bytes von 1 bis / für jedes beliebige j angesteuert. Dies ist in Fig. 12 symbolisch dargestellt durch den Strich, der vom ersten Bit des ersten Byte bis zum letzten Bit des /-ten Byte durchläuft.

Werden nun die Ausgänge der Speicherstellen M' bei

beliebige j an die Ausgänge B'*¹ angeschlossen, so befindeü sich diese Ausgänge im logischen Zustand gleich dem der Speicherstellen M'⁺' im vorhergehenden Fall. Man erhält dann in diesem Fall eine Freigabe bis zum vorhergehenden Byte. Dies ist in F i g. 12 durch die zweite durchgehende Zeile dargestellt, die beim letzten Bit des Al -ten Byte endet.

Zur Auswahl der Speicherstellen von /'= 1, j= I bis M-i muß man dem durch die zweite Zeile in F i g. 12 dargestellten Zustand das Segment anfügen, das von j= 1 bis j im /-ten Byte geht. Nun ist das logische Produkt bi ■ b{ (worin der Punkt die UND-Verknüpfung symbolisiert) gleich »1«, wenn bj, und bj gleich »1« sind; dieser Ausdruck ist gleich »1« auf der ganzen Länge der auf der dritten Zeile der F i g. 12 dargestellten Segmente. Zur Freigabe sämtlicher Ausgänge links von M'j muß man folglich die Zeilen 2 und 3 kombinieren, was darauf hinausläuft, die logische Operation

fci⁺' + b>₂ ■ hl

auszuführen, worin das Zeichen » + « die ODER-Verknüpfung symbolisiert.

Wünscht man nur NAND-Glieder zu benutzen, würde die vorangehende Operation wie folgt geschrieben werden:

worin das Zeichen »|« die NAN D-Verknüpfung symbolisiert.

Jeder Ausgang einer Speicherstelle M'-J muß folglich mit einer an die Ausgänge B₂ undÄ2 ^{+ 1}des Decodieren DECOD B₂ und an den Ausgang Bi des Decodierers DECOD Bi angeschlossenen Logik verbunden sein, die mit den an diesen 3 Ausgängen erscheinenden logischen Zuständen folgende logische Operation ausführt

b₂ ^{+ l} + b[ ■ h{
oder, was aufs gleiche hinausläuft, die Operation

!>ί Ι H) wird die vorangehende Verknüpfung in folgender Form geschrieben:

worin das Zeichen »|« wiederum die NAND-Verknüpfung symbolisiert.

In Fig. 13 wird ein Beispiel einer Logik K'-' dargestellt, die nur aus NAND-Gliedern aufgebaut ist.

ίο Die Logik K>> besitzt 6 Eingänge, von denen 3 an die Decodierer für niedere Diagonaladressen DECOD B₂ und DECOD B₃ angeschlossen sind und die 3 anderen an die Decodierer für hohe Diagonaladressen DECOD H₂ UtIdDECODH₃.

Genauer gesagt, ein NAND-Glied PB ist mit den Ausgängen ßi und Bi und sein Ausgang mit dem Eingang eines NAND-Glieds PBH mit 4 Eingängen verbunden, das außerdem mit dem vorher komplementierten und symbolischÖ2 ⁺ 'bezeichneten AnschlußB₂ ^{+ 1} verbunden ist.

Auf die gleiche Weise enthält der obere Teil der Logik /Cw ein NAND-Glied PH, das die Ausgänge Hi, Hi der Decodierer für hohe Diagonaladressen aufnimmt, wobei der Ausgang des NAND-Glieds PH an den Eingang des NAND-Glieds PBH angeschlossen_|s_t, der außerdem den komplementierten AusgangH',~^l aufnimmt.

Die Logik K'i hat ihren Ausgang auf »1« für alle Stellen, die in der Vereinigung der beiden Intervalle/Ί, ß/und ]H, 1287enthalten ^smcl. ^wenn ! ^{das erste B}'^{1 der} Zeile und 128 das letzte Bit bezeichnet. Wird dieser Ausgang an ein NOR-Glied P-i angeschlossen, das mit dem Ausgang S'-i der Speicherstelle M'·' verbunden ist, so werden sämtliche Ausgänge, die sich nicht in der Vereinigung [\, B]+JH, 128Jbefinden, freigegeben, d. h. schließlich die Ausgänge des Intervalls ]B, HJ was auch das gesuchte Ergebnis ist.

Man könnte selbstverständlich dieselbe Funktion mit anderen Verknüpfungsgliedern darstellen, z. B. zunächst durch Ausführung der Operation

Was die Ansteuerung der rechts von der hohen Diagonaladresse gelegenen Ausgänge betrifft, ist die Aufgabenstellung ähnlich. Es wird ein »Dreieck«-Decodierer verwendet, dessen Wahrheitstabelle zu derjenigen des Decodierers der niederen Diagonaladresse symmetrisch ist.

Schließt man sämtliche Stellen eines Byte vom /-ten so Rang an den Ausgang Hi an, so werden alle Bytes rechts von //ausgesteuert, das die hohe Diagonaladresse H enthaltende einbegriffen. Es muß also noch eine Verschiebung um eine Stelle stattfinden, und folglich müssen die Bytes an den AusgangHj"¹ angeschlossen werden. Zur Ansteuerung der zwischen Mj^j und M'-^s gelegenen Stellen muß man für den Decodierer DECOD H₃ eine zum Decodierer DECOD B₃ symmetrische Wahrheitstabelle nehmen und die Kombination der logischen Zustände hi ■ hi ausführen. Die Logik zur Ansteuerung der rechts von der hohen Diagonaladresse gelegenen Elemente muß folglich mit den Ausgängen Hi und//i~'des Decodierers DECOD H₂ und mit dem Ausgang Hi des Decodierers DECOD H₃ verbunden sein und nachstehende logische Operation ausführen

hi'¹ + h'₂-hi.
Wünscht man nur NAND-Glieder zu verwenden, so [\,B]+]H, 128J

und dann durch Verwendung eines UND-Glieds am Ausgang der Speicherstellen.

In Fig. 14 ist die Hälfte einer Speicher-Steckkarte abgebildet. Diese umfaßt einen integrierten Schaltkreis 10 von 16 · 4 Bits, eine Schreibschaltung 12, ein Pufferregister 14, eine Schreib-Steuerleitung 16, eine mit dem Taktgeber verbundene Leitung H, Logiken K'-J, K'-², Κ'*, K'-⁴, wenn die Speicher-Steckkarte vom /-ten Rang ist sowie NOR-Glieder P-J... P·". Die Auswahl einer Zeile erfolgt durch die 4 Bits, die das Wort A\ bilden (B\ oder Hi, je nachdem, ob es sich um eine niedere oder hohe Diagonaladresse handelt). Die Eingänge der Logiken K sind mit den Decodierern verbunden (vgl. oben), und ihre Ausgänge sind einerseits an die NOR-Glieder P und andererseits an die Schreibschaltung 12 angeschlossen.

Die Schreibschaltung 12 gestattet nach Erhalten der Summe S, die sämtlichen im Intervall JB, ///auftretenden »1«-Bits spricht, die Nullrückstellung bzw. Löschung des ganzen Intervalls JB, H], damit nachher die gewünschte Anzahl »''--Bits darin eingeschrieben werden kann. Das Pulferregister 14 ermöglicht die weitere Speicherung der Speicherausgangszustände für die Dauer der Übergangszeit von einer Zeile zur anderen. Eine vollständige Steckkarte wird durch

Ergänzung mit einem zweiten integrierten Schaltkreis 10' erhalten, der an ähnliche Elemente wie der Schaltkreis 10 angeschlossen wird. Als integrierten Schaltkreis 10 kann man SN 7489 N und als Pufferregister SN 7475 N benutzen.

Nach der nun erfolgten Beschreibung der Speicher-Steckkarte und der Logiken zur Freigabe der Ausgänge wird jetzt der Aufbau der Decodierer mit 4 und 3 Bits, die die genannten Logiken steuern, genauer betrachtet.

Die Wahrheitstabelle des Decodierers DECOD B₃ ist in Tabelle Ml angegeben.

Tabelle	b c	III	bl	b]	bi	b\	0	bl	D	0
a	OO	b\	0	0	0	0	0	0	0
O	0 1	1	1	0	0	0	0	0	0
O	10	1	1	1	0	0	0	0	0
O	1 1	1	1	1	1	0	0	0	0
O	00	1	1	1	1	1	1	0	0
1	0 1	1	1	1	1	1	1	0	0
1	1 0	1	1	1	1	1	1	1	1
1	1 1	1	1	1	1	1		1
1	1

Ausgehend von Tabelle III ist es dem Fachmann ein leichtes, eine Logik aufzubauen, die diese Funktionen erfüllt. Zur besseren Erklärung wird in Fig. 15 eine solche Logik dargestellt, die somit ein Beispiel für ehien Decodierer des Typs DECOD B₃ angibt.

Die Wahrheitstabelle des Decodierers DECOD H₃ wird durch die Komplemente der logischen Zustände der Tabelle III gebildet. Es ist also unnötig, sie aufzuzeichnen. Ein Beispiel einer Logik, die diese Funktionen ausführt, ist in F i g. 16 gegeben.

Die WahrheitPtabelle des Decodierers DECOD B₂ mit 4 Bits ist in Tabelle IV wiedergegeben. Ihr entspricht das Schaltbild der Fig. 17, worin auch die Ausgänge angegeben sind, die es gestatten, den komplementären Zustand zu erhalten.

Tabelle IV

abcd

123456789 10 11...

0000 000 1 00 10 00 11 0 100 0 10 1 0 110 Olli 1000 100 1 10 10 10 11 1100 110 1 1110 1111

10000

110

110

1110

11110

1 1 1 1 1 0 ..

1111110.

11111110

11111 11111 11111 11111 11111

110. 111 0 111 . 111 . 111 .

1111111111 1111111111 1111111111

Tabelle V

abcd

12 3 4

. 16

0000 1111... 1

0001 0 1 1 .... 1

1110 0 11

1111 0 0 1

Ersichtlich gilt
= b\, h\ =

h₂ ^s = b\^b und h? = 1

Man kann folglich, ausgehend vom Schaltbild von F i g. 17, einen Decodierer DECOD H₂ erhalten durch Verschiebung der Ausgänge, wie dies im rechts gelegenen Teil dieser Figur dargestellt ist.

Aufbau des Addierers ADD I

Der Addierer ADD 1 erhält logische Signale nur von den freigegebenen Speicherausgängen, d. h. von denjenigen, die im Intervall JB, ///enthalten sind. Seine Rolle ist die Bildung der Summe S aller in diesem Intervall enthaltenen »1«-Bits. Es ist vorteilhaft, einen Addierer zu verwenden, der wie folgt arbeitet.

Die 128 Bits sind in 4 Gruppen mit 31 Bits aufgeteilt,

jo da die 4 restlichen Bits gesondert verarbeitet werden. Jede Gruppe wird in einem Addierwerk verarbeitet, dessen Ausgänge nachher an ein anderes Addierwerk angeschlossen werden. Ein Blockschaltbild ist in F i g. 18 dargestellt. Den Gruppen mit 31 Bits zugeordnete Addierer 20, 22, 24 und 26 liefern Signale von 5 Bits an einen Addierer 30, der außerdem das 125_ 126. und 127. Bit der betreffenden Zeile erhält. Der Ausgang des Addierers 30 gibt ein Wort von 7 Bits ab, das die Summe der im Intervall ]B, ///enthaltenen »1 «-Bits darstellt, das

128. Bit ausgenommen, das, wie weiter unten erklärt, gesondert verarbeitet wird.

Jede der die Gruppen mit 31 Bits verarbeitenden Schaltungen kann vorteilhafterweise aus Addiererbaugruppen aufgebaut werden, z. B. vom Typ SN 7483, von denen jede zur Bildung der Summe von zwei Worien mit 4 Bits U_u U₂, U₃, Ua bzw. Vi, V₂, V₃, V₄ vorgesehen ist. Es werden 6 Worte von 1 Bit jeweils auf die Eingänge Cj, U\, V,, (Λ, V₃, V₄ geschaltet und U₃ wird auf »1« gebracht, während U₂ und V₂ auf »0« gesetzt werden. Die Summe von G, U\ und U₂ wird bei Σ\ und Z₂ ausgegeben, und die in Tabelle VI dargestellte Wahrheitstabelle zeigt, daß die Summe von Ua, V₃, V₄ bei Σα und Cq ausgegeben wird für: C₄, U₃ = 0\ und V₄ = OO ist die Summe 01, (

Tabelle VI

K₄ V₃

C₀ X₄ Z₃

Die Wahrheitstabelle des Decodierers DECOD H₂ ist durch die vereinfachte Tabelle V gegeben.

0	0	0	0	0	1
0	0	1	0	1	0
0	1	0	0	1	1
0	1	1	1	0	0
1	I 0	0	0	1	1
1	0	1	1	0	0
1	1	0	1	0	1
1	1	1	1	I	0

Diese Schaltungsanordnung wird viermal wiederholt, und für jede Anordnung werden die ausgegebenen zwei Worte mit 2 Bits einer neuen Schaltung zugeführt, von der nur der erste Addierer sowie der Übertragungseingang benutzt werden. Man erhält so vier Worte mit 3 Bits, die je zu zweit addiert werden, mit Hilfe von zwei anderen integrierten Schaltungsmoduln, deren Übertragungseingänge zwei neue Worte mit 1 Bit erhalten, und schließlich werden die erhaltenen zwei Worte von 4 Bits mit dem 31. Wort von 1 Bit an einen 11. Addierer ausgegeben. Das Schaltbild einer solchen Schaltung ist in F i g. 20 dargestellt.

Zur Summation der den Addierern 20, 22, 24 und 26 entstammenden vier Worte mit 5 Bits wird die Schaltung 16 von Fig. 18 benutzt, die in vorteilhafter Weise aus Teilschaltungen entsprechend dem Schaltbild in Fig. 21 organisiert sind, bestehen kann. Für jedes Wortpaar wird für die 4 ersten Bits ein Schaltungsmodul benutzt und die Hälfte eines anderen für das 5. Bit, während der Übertragseingang des Addierers eines der 2η übriggebliebenen Worte von 1 Bit benutzt, d. h. das 125.

Die Ausgänge werden von einer aus einem Einbaumodul und einem halben Modul bestehenden dritten Schaltungsanordnung abgenommen, während der neue Übertragseingang das dritte (übriggebliebene) der vier Worte mit 1 Bit (das 127.) benutzt.

Nach Erhalt der Summe Sder»l «-Bits im Intervall JB. ///bleibt noch die Adresse X= 5+S zu berechnen, bis zu der von der niederen Diagonaladresse ausgehend die »1«-Bits einzuschreiben sind. Diese Addition erfolgt durch eine Schaltung Σ, deren Schaltbild in Fig.22 angegeben ist.

Diese Schaltung enthält:

— einen Pufferspeicher MT von 8 Bits, der die 7 Bits js des Wortes B2B1 über sieben Verknüpfungsglieder P erhält, die gleichzeitig durch den Anschluß 40 gesteuert werden; das an den Ausgängen des Pufferspeichers MT anstehende Wort mit 7 Bits bildet ein Wort X₂Xi, 4(i

— einen Addierer ADD 2 mit 8 Bits, der die aus dem Pufferspeicher MT stammenden 7 Bits und die vom Addierer ADDl kommenden 7 Bits sowie das am Anschluß 42 dargestellte 128. Bit erhält, das vom Addierer ADD I nicht berücksichtigt worden war,

— 8 Verknüpfungsglieder P\ die geöffnet sind, wenn die Verknüpfungsglieder P geschlossen sind und umgekehrt und die den 8 Ausgängen des Addierers ADDTl und den 8 Eingängen des Pufferspeichers WTvorgeschaltet sind, ■> <>

— ein Zählwerk G mit 4 Bits, das auf B\ voreingestellt ist und dessen Taktgebereingang 44 mit dem achten hochgewichteten Ausgang des Addierers ADDI verbunden ist; das am Ausgang des Zählwerks Q anstehende Wort Xi von 4 Bits stellt die hochge- -,<■> wichteten 4 Bits der Adresse Xdar, deren 7 Bits mit schwachem Gewicht außerdem dem Wort X₂Xi entsprechen.

Der Pufferspeicher kann aus 2 Moduln vom Typ SN _W) 7474 N und der Addierer ADD2 mit 8 Bits aus 2 in Kaskade geschaltete Moduln SN 7483 aufgebaut werden.

Die Ausgangssignale des Addierers ADD2 können dank der Verknüpfungsglieder P'in den Pufferspeichern t/, gespeichert werden.

Auf diese Weise kann so oft wie nötig das Ausgangssignal des Addierers ADDi wieder hinzuaddiert werden, um (vgl. weiter unten) den Fall zu berücksichtigen, daß die Adressen B und H sich nicht in der gleichen Zeile befinden: ßi Φ H\.

Aufbau der Steuerschaltung

Die Steuerschaltung ist in Fig.23 schematisch dargestellt. Sie umfaßt:
ein auf B\ voreingestelltes Zählwerk C₂, eine Weiche AXmit 2 Eingängen,
die X\ und Hi aufnehmen, und mit einem Steueranschluß 50, der bestimmt, welches der Worte X\ oder H₁ am Ausgang 52 erscheint,

einen Vergleicher COMP, dessen Eingänge mit dem Zählwerk C₂ und mit dem Ausgang der Weiche AK verbunden sind,

eine Weiche AH, die durch das über den Anschluß 50 abgegebene Steuersignal und durch das über einen Anschluß 52 abgegebene Komplementsignal gesteuert wird und deren Eingang mit dem Ausgang des Vergleichers COMPverbunden ist.

Die Weiche AH besitzt 2 komplementäre Ausgänge 53 und 55, von denen jeder eins der 2 Verknüpfungsglieder einer Weiche PH steuert, deren eines das Wort Λ2 Xi und deren anderes das Wort H2 Hi erhält. Die Ausgänge der Verknüpfungsglieder der Weiche PH sind mit den Decodierern DECODH₂ und DECODH₁ verbunden.

Die Arbeitsweise dieser Weiche ist folgende: B] und H\ werden auf den Vergleicher COMP gegeben. Bei H\ = Si entriegelt dieser Vergleicher die Weiche PH, die H2 und H3 auf den Decodierer für hohe Diagonaladressen überträgt. Der Decodierer für niedere Diagonaladressen erhält so eine Spannung, wie man später sehen wird, und die Addition der »1« erfolgt. Das Ergebnis 5 dieser Addition wird der niederen Diagonaladresse zugefügt zur Bildung der Adresse X, und »1«-Bits werden Sund X weiter eingeschrieben.

Nach dieser Operation wird durch das an dem Anschluß 52 erscheinende Signal »1« der Zustand der Weiche AH verändert, so daß H₂ H₃ durch X₂ X3 am Ausgang der Weiche PH ersetzt wird. Aus der Definition von X2 Xz folgt, daß das Schreiben der »1 «-Bits die Adresse Xnicht überschreitet. Das über den Anschluß 50 zugeführte Steuersignal wirkt ebenfalls auf die Weiche AX ein, die das Wort X\ an den Vergleicher abgibt; da jedoch vorausgesetzt war ßi = H\, so folgt daraus ΛΊ = Hi, was das vom Vergleicher COM? ausgegebene Signal nicht verändert.

In der ganzen vorausgehenden Beschreibung wurde zur Vereinfachung vorausgesetzt, daß die niederen unc hohen Diagonaladressen einer Einschränkung sich ir der gleichen Zeile befanden. Im folgenden wird nun die Arbeitsweise der optimierenden Rechenmaschine er klärt, wenn AVi von B\ verschieden ist.

Ist Hi von B\ verschieden, so fügen die im Addierei ADDl und im Addierer ADD2 ausgeführten Additio nen die Summe Si der Einsen der Zeile B\ zu B. Dh Folgesteuereinrichtung S£(?gibt dann einen Impuls afc der das Zählwerk C₂ inkremcnliert, und eine neui Addition

Si + Si + S₂

wird ausgeführt. Diese Additionen werden fortgesetz bis Gleichheit zwischen dem Inhalt von C₂ und H erreicht ist. Solange diese Gleichheit nicht erreicht is ist das Wiedereinschreiben der »!«-Bits gesperr Sobald der Inhalt des Zählwerks C₂ gleich Hi wird, lös

ein (nicht dargestelltes) Flipflop folgende Operationen aus:

— Wiedereingabe des Worts B\ in das Zählwerk C₂,

— Bildung des am Anschluß 52 erscheinenden Signals »1«, das über die Weiche AX die Verzweigung von X, zum Vergleicher COMPund über die Weiche PH die Verzweigung von X₂ X} zum Decodierer für hohe Diagonaladressen steuert,

— Freigabe des Wiedereinschreibens von »1 «-Bits im Intervall ]B,X].

Das Schaltbild der vollständigen Steckkarte mit der gesamten Steuerschaltung ist in Fig. 24 dargestellt. In dieser Figur finden sich die Baugruppen der Fig. 23 wieder, und zwar das Zählwerk C₂, der Vergleicher COMP, die Weichen AX, AH und PH, der Addierer ADD2, die Verknüpfungsglieder P und P' (die symbolisch nur durch ein einziges Glied dargestellt sind), der Pufferspeicher MT und das auf B\ voreingestellte Zählwerk C

Im unteren Teil gestattet die Logik PB das Eingreifen des Decodierers für niedere Diagonaladressen nur, wenn in der Zeile B\ gearbeitet wird.

Im Schaltbild der Fig. 24 stammen die (links) dargestellten Steueranschlüsse /» tu, AB, M 3, M₂ von der Folgesteuereinrichtung SEQ in Fig.9. Diese Folgesteuereinrichtung ist schematisch in Fig. 25 dargestellt. Sie enthält ein Flipflop 62, drei in Kaskade geschaltete Monoflops M], M₂, M] und eine Start-Stop-Kippscha!tung64.

Im vereinfachten Fall Si = H, arbeitet diese Folgesteuereinrichtung wie folgt:

Ein erster Übertragungsimpuls tn kommt vom Digitalrechner und sieht das Laden der Register Si, S₂, Bs und des Zählwerks C₂ vor. Ein zweiter Impuls tu lädt die Register Hi. H₂ und H₃, stellt das Flipflop 62 auf Null zurück und schaltet die Start-Stop-Kippschaltung 64 ein. Diese betätigt die Monoflops, die folgende Aufgaben haben:

— M] gestattet das Laden der sich auf der Steckkarte befindenden Pufferspeicher, deren Ausgänge den Addierer ADD 2 steuern,

— M₂ hat als Funktion das Einschreiben von Nullen und die lnkrementierung des Inhalts vom Zählwerk Ci,

— M) überträgt die Ausgangssignale des Addierers ADD 2 in die zugeordneten Pufferspeicher MT.

Ist der Inhalt des Zählwerks C₂ gleich W₁, so läßt der Impuls M₂ das Flipflop 62 kippen, was einen neuen Zyklus einschaltet, worin Xi den Vergleicher und X₂ Xj den Decodierer für hohe Diagonaladressen steuern. Das Einschreiben der »!«-Bits erfolgt zwischen Sund X.

1st der Inhalt des Zählwerks C₂ gleich Xi wegen des Kippens des Flipflops 62, so schallet der von M₂ kommende Impuls die Start-Stop-Kippschaltung 64 ab. Das entsprechende Phasendiagramm ist in Fig. 26 gegeben, stets für den Fall Si = Wi.

Weiter oben wurde angegeben, daß die Adresse X, bis zu der »!«-Bits ausgehend von der niederen piagonaladresse S einer Einschränkung eingeschrieben werden müssen, durch Addieren von B zur Summe S der im Intervall ]B, HJ stehenden »!«-Bits erhallen wurde. Diese Addition wird in der Schaltung Σ der Fig.22 ausgeführt.

Bei einer bevorzugten Ausgestaltung der optimierenden Rechenmaschine kann die für einen Elemcntarvorgang ausgehend von einem Zustand mit der Adresse A zu treffende Entscheidung direkt vom Wert von X abgeleitet werden. Ist die Adresse A kleiner als die Adresse X, die nach Verarbeitung der letzten Einschränkung erhalten wurde, so liegt A unterhalb der Diagonale X, und die zu treffende optimale Entscheidung besteht darin, einen Weg auszuwählen, der unterhalb der genannten Einschränkung verläuft. Ist die Adresse A größer als X, so befindet sich A oberhalb der Diagonalen X, und die zu treffende optimale Entschei-

in dung besteht darin, einen Weg auszuwählen, der oberhalb der Einschränkung verläuft.

Wenn außerdem aus irgendeinem Grund, der z. B. an Entscheidungen gebunden ist, die in anderen als in der gerade betrachteten Ebene getroffen werden müssen, veranlaßt wird, in besagter Ebene einen Weg auszuwählen, der nicht der optimale Weg ist, so ist sofort die durch diese nicht optimale Wahl hervorgerufene »Strafe« bekannt, die ganz einfach die Differenz I A - XI der Adressen ist.

2Π Die vorausgehende Beschreibung bezieht sich stets auf die Verarbeitung eines zweidimensionalen Raumes, der einem System von zwei Variablen entspricht.

Selbstverständlich gehört zum sachlichen Schutzbereich der Erfindung auch eine optimierende Rechenma-

2-3 schine, die entweder parallel oder seriell ρ (ρ—1)/2 Aufgaben entsprechend dem Auffinden eines optimalen bzw. kürzesten Wegs für ein System mit ρ Variablen löst, wobei die Anzahl ρ (p-1)/2 der Anzahl verschiedener, je zu zweit kombinierter Variablen

so entspricht und jedes der ebenen Probleme wie oben beschrieben verarbeitet wird. In diesem Fall zeigt die optimierende Rechenmaschine p(p—1)/2 optimale Elementarvorgänge an, die in beliebiger Weise kombiniert werden können, um den optimalen Elementarvorgang im p-dimensionalen Raum aufzufinden.

Nur der Vollständigkeit halber sei gesagt, daß man für diese Kombination das wohlbekannte »Entscheidungsbaum«-Verfahren anwenden kann, das darin besteht, alle in den verschiedenen Ebenen als Funktion der entsprechenden Weglänge erhaltenen Elementarwege zu ordnen und sukzessiv alle Eventualitäten, die den Wegen mit abnehmender Länge entsprechen, auszuschalten, so daß am Ende der kürzeste Weg übrigbleibt. Mit diesem Algorithmus kann man die optimale, im p-dimensionalen Raum zu treffende Entscheidung finden und durch Projektion auf jede Ebene den optimalen Vorgang in jeder der Ebenen. Man kann jedoch auch andere Kombinations-Algorithmen anwenden.

Im allgemeinsten Fall enthält eine optimierende Rechenmaschine zum Aufsuchen eines optimalen bzw. kürzesten Wegs zwischen einem Anfangs- und einem Endzustand eines Systems mit ρ Variablen 7/(1 Zi^p):

A) die bereits beschriebenen Mittel zum Auffinden " und Speichern eines jeden der p(p- l)/2 optimalen

Elementarvorgänge für die p(p- l)/2-Systeme mit zwei Variablen 7",=/»und T₁= n, mit ηίφη.

B) Mittel zur Ausführung der Kombination dieser p(p—\)l2 optimalen Elementarvorgängc, die den

^h" optimalen Elementarvorgang für das System mit ρ Variablen ergibt.

In einer leicht abgewandelten Variante enthält die optimierende Rechenmaschine

A) die bereits beschriebenen Mittel zum Auffinden und Speichern für jedes der p(p- l)/2, als Funktion von zwei Variablen T₁= m und Τ,-η, mit

betrachteten Systeme der Längen der drei Wege, die in den drei möglichen aufeinanderfolgenden Zuständen des Anfangszustandes enden,
B) Mittel zur Speicherung der auf diese Weise pip-

erhaltenen3 -

Längen,

C) Entscheidungsmittel, die besagte 3

Längen

vergleichen und einen der 2p— 1 möglichen, aufeinanderfolgenden Zustände für das System mit ρ Variablen auswählen, was den ersten optimalen Elementarvorgang definiert,

Die Daten können durch jedes klassische Computer-Peripheriegerät eingegeben werden (Lochkarten, Magnetbänder usw.) oder durch jedes andere Mittel (hydroelektromechanische Meßwertgeber usw.). Die Ergebnisse können durch Peripheriegeräte aller Art angezeigt werden: Bildschirmgeräte für farbige Anzeige, Schnelldrucker, Servogeräte.

Es versteht sich, daß über dieses Beispiel hinausgehend die optimierende Rechenmaschine sehr viel komplexere Aufgaben mit viel mehr als vier Variablen und einer bedeutenden Anzahl von Einschränkungen lösen kann.

D) Mittel, um in jeder der

Ebenen zu

überprüfen, ob besagter optimaler Elementarvor- r> Tabelle VII gang mit den in dieser Ebene angezeigten Einnschränkungen kompatibel ist.

Zur Veranschaulichung wird nachstehend ein absichtlich sehr einfaches Beispiel der Lösung einer Aufgabe -'< > mit Hilfe der erfindungsgemäßen Rechenmaschine gegeben, und zwar zur Illustration der Art und Weise, in der der optimierenden Rechenmaschine die Aufgabe gestellt wird, und der Form, in welcher diese sie löst.

Die Aufgabe betrifft 4 Züge, die sich ursprünglich auf 2"> 4 verschiedenen Gleisen befinden, welche Gleise sich zu einem einzigen Gleis mit 7 aufeinanderfolgenden Blockabschnitten vereinigen. Nach dem 7. Blockabschnitt teilt sich das einzige Gleis wieder in 4 Gleise, die aufs neue durch einen der 4 Züge belegt werden können, so Die Züge fahren mit Geschwindigkeiten, die nicht gleich sein müssen. Aus Sicherheitsgründen wird gefordert, daß wenigstens ein Blockabschnitt zwischen 2 Zügen frei bleibt. Die Aufgabe besteht nun darin, herauszufinden, auf welche Weise die Züge fahren müssen, um die )5 zeitlich optimale Lösung zu erhalten.

In dieser Aufgabe hängt die Gesamtsituation von vier Variablen 71, T₂, 7*3, T₄ ab, die die Besetztzeiten der Blockabschnitte darstellen. Es gibt sechs verschiedene Möglichkeiten, um diese Variablen zu zweit zu kombinieren, so daß die Aufgabe in sechs verschiedenen Ebenen behandelt werden muß.

Die Lage der Einschränkungen in jeder Ebene ist durch die Bedingung bestimmt, nach der mindestens ein freier Blockabschnitt zwischen 2 Zügen vorhanden sein muß, was bedeutet, daß, wenn der Zug Ti sich z. B. im Blockabschnitt 5 befindet, der Zug T₂ sich weder im Blockabschnitt 4 noch im Blockabschnitt 6 noch selbstverständlich im Blockabschnitt 5 befinden kann. Ist auf diese Weise der Ort der Einschränkungen in den so sechs Ebenen bestimmt, so lassen sich daraus die Koordinaten der hohen und niederen Punkte der Einschränkungen ableiten, die die Daten der Aufgabe bilden, die der Rechenmaschine einzugeben ist. Diese Koordinaten sind in der Tabelle VlI zusammengestellt. Der optimierenden Rechenmaschine werden ebenfalls die Zuggeschwindigkeiten mitgeteilt, z. B. 9, 13, 14 und 17.

Die optimierende Rechenmaschine kann das Ergebnis in Form einer Befehlsfolge ausgeben, wie sie in der bo Tabelle VIII zusammengestellt ist. In dieser Tabelle sind lediglich die Entscheidungsänderungen angegeben; so ist für die nicht ausdrücklich erwähnten Durchfahrten 2 und 3 die zu treffende Entscheidung die gleiche wie für die Durchfahrt 1, d. h. »Vorfahren des Zuges Nr. 2«. Die h5 optimierende Rechenmaschine gibt ebenfalls die Gesamtdauer der optimalen Lösung an, die im behandelten Beispiel 27 Testschritte beträgt.

Ebenen	Einschränkungen	Y	Koordinaten des	Y
	Koordinaten des	0	niederen Punktes	3
	hohen Punktes	I	X	5
	X	3	0	7
Ebene 2,1	2	5	1	10
	3	7	2	12
	4	10	3	13
	6	0	4	2
	8	1	6	3
	9	2	0	5
Ebene 3,1	2	3	1	9
	3	5	2	12
	4	9	3	14
	6	0	4	2
	8	1	6	3
	9	2	0	5
Ebene. 3,2	3	3	1	9
	5	5	3	12
	T /	9	5	14
	10	0	7	5
	12	1	10	8
	13	5	0	11
Ebene 4,1	2	8	1	13
	3	11	2	15
	4	13	3	17
	6	0	4	5
	8	1	6	8
	9	5	0	Il
Ebene 4,2	3	13	1	17
	5	0	3	5
	7	1	10	8
	13	5	0	Il
Ebene 4,3	2	8	1	13
	3	Il	2	15
	5	13	3	17
	9		5
	12		9
	14

27 28

24	Tabelle VIII	Hierzu 15	23 265
Durchfahrt
1	Folgende Züge; fahrer, vor
4	2
6	2-4
7	2
9	2-4
10	1-2-4
11	2-4
13	1-2-4
14	2-3-4
15	1-3-4
16	1-4
17	3-4
18	1-3-4
21	3-4
22	1-3-4
24	1-3
3
Blatt Zeichnungen

Claims (6)

u> Patentansprüche:

1. Optimierende Rechenmaschine zum Auffinden des kürzesten Weges zwischen einem vorgegebenen Anfangs- und einem vorgegebenen Endzustand eines Systems, dessen momentaner Zustand durch zwei digitale Variablen — Koordinaten — beschrieben ist, deren jede Λ/äquidistante Werte annehmen kann,

mit einem Eingabe-Speicher-Werk für die Anfangsund Endzustand-Koordinaten und für \erbotene Zustände — Einschränkungen — des Systems darstellende Koordinaten,

mit Rechen- und Speicher-Zellen zur Speicherung und Inkrementierung ihres Inhaltes mittels eines Inkrementbildners,

mit einer Einrichtung zur Änderung des Zelieninhalts in Abhängigkeit von den Einschränkungen derart, daß die zeitliche Änderung des Zelleninhalts durch die Ausbreitung einer gedachten rückiaufenden Welle darstellbar ist, die sich schrittweise in der Koordinaten-Ebene — Matrix — mit N² Punkten vom Endzustandspunkt bis zum Anfangszustandspunkt fortpflanzt, so daß jeder Punkt die Welle von den vorausgehenden angrenzenden Punkten mit Ausnahme der die Welle nicht fortpflanzenden Einschränkungspunkte empfängt, mit einem Vergleicher,

der an den Ausgang der Speicherzellen angeschlossen ist und die Inhalte der dem vorausgehend ermittelten Koordinatenpunkt benachbarten Zellen jeweils vergleicht mit dem Inhalt des vorausgehend ermittelten Koordinatenpunktes und jeweils als neuen Koordinatenpunkt denjenigen mit dem nächstniedrigeren Inhalt auswählt, und — zur Berechnung des vollständigen Weges zwischen Anfangs- und Endzustand — eine Iterationseinrichtung enthält, die ihrerseits aufweist: ein Speicherglied für den durch den Vergleicher ausgewählten Koordinatenpunkt als neuen Anfangszustand,

eine Einrichtung zum Wiedereinschreiben der ursprünglichen Zelleninhalte,
einen Befehlsgeber für die Steuerung der Einrichtung zur Änderung des Zelleninhalts, des Vergleichers, des Speicherglieds und der Einrichtung zum Wiedereinschreiben der ursprünglichen Zelleninhalte für eine neue Verarbeitung der Zelleninhalte und eine Speichereinheit für die aufeinanderfolgende Speicherung der Menge der bei jedem Iterationsablauf gefundenen optimalen Schritte, die nach und nach den gesuchten kürzesten Weg vom Anfangszum Endzustand ergeben,
gekennzeichnet durch folgende Merkmale:

25

jo

35

45

50

55

a) daß die Rechen- und Speicher-Zellen (F i g. 9 und 11) in der Anzahl P=2 ■ N (Fig.8) vorhanden sind,

b) daß jeder der P Zellen eine Adresse — Diagonaladresse (0 bis 17 in Fi g. 8) — zugeordnet ist, und zwar derart, daß die P Diagonaladressen 0 bis P— 1 durchlaufen und so die Zellen P Diagonalen der Koordinatenebene zugepzlnet gedacht werden können (F i g. 8),

c) daß (Teil von SEQ) Glieder enthält zur Speicherung:

des Inkrements »0« für die Zellen mit den Eingabe-Speicher-Werk

b5

Diagonaladressen 0 bis /V und

des Inkrements »1« für die Zellen mit den Diagonaladressen Λ/+ 1 bis P— 1,

d) daß das Eingabe-Speicher-Werk jede Einschränkung mittels zwei Zahlen speichert (Fig.8),

deren eine Zahl H (z.B. 13) — hohe Diagonaladresse — der in der Koordinatenebene gelegenen höchsten Diagonale entspricht, die gerade noch das Einschränkungsfeld (z. B. 1, 2,3 in F i g. 6) berührt, und
deren andere Zahl B (z. B. 8) — niedere Diagonaladresse — der in der Koordinatenebene gelegenen unteren Diagonale entspricht, die gerade noch das Einschränkungsfeld berührt,

e) daß der Inkrementbildner derart ausgebildet ist, daß er bei jedem Iterationsablauf den Zelleninhalt in Abhängigkeit von den Diagonaladressen B und H der verarbeiteten Einschränkung inkrementiert und

el) das inkrement der Zellen mit den Diagonaladressen 0 bis B auf »0« hält,

e2) die Anzahl S¹ von Inkrementen berechnet, die vor der Verarbeitung der jeweiligen Einschränkung in den Zellen mit den Diagonaladressen B+1 bis //gezählt wurden,

e3) den Inhalt der Zellen mit den Diagonaladressen ß+1 bis//löscht,

e4) das Inkrement »1« in den Zellen mit den Diagonaladressen ß+1, ß+2, ..., B+S speichert,

e5) das Inkrement »0« in den Zellen mit den Diagonaladressen ß+ 5+1 bis //speichert und

e6) die Inkremente der Zellen mit den Diagonaladressen H-r 1 bis P— 1 unverändert läßt.

2. Rechenmaschine nach Anspruch 1, gekennzeichnet durch

einen Speicher (M) mit P=2N Bit-Stellen, wobei jedes Bit ein Inkrement für eine Zelle darstellt, eine Freigabeeinrichtung (V) zur Freigabe aller Ausgänge der im Diagonaladressen-Intervall von ß+1 bis H- JB, H]- enthaltenen Speicherstellen, einen mit dem Ausgang des Speichers (M) über die Freigabeeinrichtung (V) verbundenen Addierer (ADDi) zum Addieren aller im Intervall ]B, H] enthaltenen »1«-Bits,

eine Löscheinrichtung (RZ) zum Löschen der Speicherstellen des Speichers (M)\m Intervall]B, H], eine Schreibeinrichtung (E)zum Schreiben einer Anzahl »1«-Bits gleich der Summe S, ausgehend von der Diagonaladresse ß-t-1 bis zu X= B+S, und

von »Ow-Bits von der Diagonaladresse X+1 bis zu H, und

eine an einen Digitalrechner (ORD) angeschlossene Folgesteuereinrichtung (SEQ), die:

Oi) das Schreiben und Lesen im Speicher (M), die Freigabeeinrichtung (V) und den Addierer (ADDi) bei jeder Verarbeitung einer Einschränkung steuert,

ß) einen Übergang von der Verarbeitung einer Einschränkung zur Verarbeitung der nachfolgenden Einschränkung gestattet und

γ) nach der letzten Verarbeitung gestattet, die Summe der eingeschriebenen »1 «-Bits bis zur Diagonaladresse der Zellen, die den drei

Folgezuständen des Anfangszustands entspricht, zu entnehmen (F i g. 9).

3. Rechenmaschine nach Anspruch 2, dadurch gekennzeichnet,

daß der Speicher (M) zu 2i Zeilen mit 2^r Bits bei P= 29+"Organisiert ist,

daß die Zeile, zu der eine Diagonaladresse gehört, durch die q Bits mit dem höchsten Gewicht dieser Diagonaladresse definiert ist, die ein Wort B\ für eine niedrige Diagonaladresse und ein Wort H\ für eine hohe uiagonaladresse bilden, und
daß die Freigabeeinrichtung (V) aufweist:
einen Decodierer (DECOD B) für niedere Diagonaladressen, dessen Eingänge mit den Mitteln zur Speicherung der niederen Diagonaladressen und dessen Ausgänge mit Freigabe-Logiken VAL zur Freigabe der dem Intervall ]B, H] entsprechenden Speicherausgänge verbunden sind und der einen Decodierer (DECOD B{) von q Bits enthält, der q Eingänge und 2? Ausgänge besitzt, und
einen Decodierer (DECOD H) für hohe Diagonaladressen. dessen Eingänge mit den Mitteln zur Speicherung der hohen Diagonaladressen und dessen Ausgänge mit den Freigabe-Logiken VAL verbunden sind und der einen Decodierer (DECOD H\) von q Bits enthält, der q Eingänge und 2f Ausgänge besitzt (F i g. 11).

4. Rechenmaschine nach Anspruch 3, dadurch gekennzeichnet,

daß jede Speicher-Zeile von 2^r Bits zu 2^S Worten von je 2' Bits mit 5+1 = rorganisiert ist und daß:

a) der Decodierer (DECOD B) für niedere Diagonaladressen außer dem Decodierer (DE- COD B\) von q Bits enthält:

al) einen Decodierer (DECOD B₂) von s Bits, die den s Bits mit mittlerem Gewicht der niederen Diagonaladresse entsprechen, die ein Wort B₂ bilden, und

a2) einen Decodierer (DECOD B₃) von t Bits, die den t Bits mit dem geringsten Gewicht der niederen Diagonaladresse entsprechen, die ein Wort B₃ bilden, und

b) der Decodierer (DECOD H) für hohe Diagonaladressen außer dem Decodierer (DECOD H\) von q Bits enthält:

bl) einen Decodierer (DECOD H₂) von s Bits, die den s Bits mit mittlerem Gewicht der hohen Diagonaladresse entsprechen, die ein Wort H₂ bilden, und

b2) einen Decodierer (DECOD H₃) von ( Bits, die den t Bits mit dem geringsten Gewicht der hohen Diagonaladresse entsprechen, die ein Wort H₃ bilden,

c) daß der Speicher (M) eine Kapazität von 2" =2048 Bits besitzt, die zu 2⁴= 16 Zeilen von 2⁷=128 Bits organisiert sind, unterteilt in 16 Bytes, numeriert von /=1 bis 16, wobei die Bits eines Byte von j= 1 bis /=8 numeriert sind und jedes der 128 Bits einer Zeile somit durch zwei Indizes i, j als Speicherstelle M'-J (Fig. 13) beschrieben ist,

d) daß jede Diagonaladresse durch ein Wort von 11 Bits definiert ist, das aus drei Worten B\, B₂ und B₃ für die niedere Diagonaladresse und drei Worten Wi, H₂ und H₃ für die hohe Diagonaladresse zusammengesetzt ist, welche Wörter jeweils durch die vier höchstgewichteten Bits

der Diagonaladresse, durch die 4 Bits mit dem mittleren Gewicht bzw. durch die 3 Bits mit dem geringsten Gewicht gebildet sind,

e) daß der Decodierer (DECOD B₂) von s Bits des Decodieren für niedere Diagonaladressen, der 4 Eingänge und 16 Ausgänge ΒΊ (7=1 bis 16) besitzt, alle Bytes links vom die niedere Diagonaladresse enthaltenden Byte einschließlich diesem auswählt,

f) daß der Decodierer (DECOD B₃) von f Bits des Decodierers für niedere Diagonaladressen, der 3 Eingänge und 8 Ausgänge Bi (j= I bis 8) besitzt, in jedem Byte alle Stellen links von der durch den Wert von B₃ im binären Dezimalcode dargestellten Stelle einschließlich dieser auswählt,

g) daß der Decodierer (DECOD H₂) von 5 Bits des Decodierers für hohe Diagonaladressen, der 4 Eingänge und 16 Ausgänge H'₂ (7=1 bis 16) besitzt, alle Bytes rechts vom die hohe Diagonaladresse enthaltenden Byte einschließlich diesem auswählt,

h) daß der Decodierer (DECOD H₃) von f Bits des Decodierers für hohe Diagonaladressen, der 3 Eingänge und 8 Ausgänge H{ (7=1 bis 8) besitzt, in jedem Byte die Stellen rechts von der durch den Wert von H₃ im binären Dezimalcode dargestellten Stelle einschließlich dieser auswählt,

i) daß die Freigabe-Logiken VAL jeweils aufweisen (F ig. 13):

ein NOR-Glied (P- J), das an den Ausgang jeder Speicherstelle (M'- J) angeschlossen ist und von dem

der Ausgang an den Addierer (ADDi), einer der beiden Eingänge an den Ausgang der Speicherstelle (M'')und der andere Eingang an den Ausgang einer Logik (K'-')mw. 6 Eingängen angeschlossen sind,

von denen 3 Eingänge mit den 2 Ausgängen ß; und Si ⁺'des Decodierers (DECOD B₂) von s Bits des Decodierers für niedere Diagonaladressen bzw. mit dem Ausgang B{ des Decodierers (DECOD B₃) von t Bits des Decodierers für niedere Diagonaladressen verbunden sind und für diese 3 Eingänge die Logik die Verknüpfung

b'₂ ^{+ l} + b₂ ■ b{

ausführt,

und die 3 anderen Eingänge mit dem 2 Ausgängen Hi und Wi"' des Decodierers (DECOD H₃) von f Bits des Decodierers für hohe Diagonaladressen bzw. mit dem Ausgang Hi'des Decodierers (DECOD H₃) von f Bits des Decodierers für niedere Diagonaladressen verbunden sind und für diese 3 Eingänge die Logik (K'J)d\e Verknüpfung

h'r¹ + Ix₂ ■ hi

ausführt,

wobei b und h den logischen Zustand der entsprechenden Ausgänge B bzw. H bezeichnen.

5. Rechenmaschine nach Anspruch 4, dadurch gekennzeichnet, daß jede Logik (K'-^enthält:

ein NAND-Glied (PH) mit 2 Eingängen, von denen einer mit dem Ausgang Hi und der andere mit dem Ausgang Hi verbunden ist,

ein NAND-Glied (PB) mit 2 Eingängen, von denen einer mit dem Ausgang Bi und der andere mit dem Ausgang B{ verbunden ist,

ein NAND-Glied (PBH)mil4 Eingängen, von denen der erste und der zweite mit dem Ausgang des einen NAND-Glieds (PH)bzu/. dem Ausgang des anderen NAND-Glieds (PB), der dritte mit dem komplementiertenAusgang Hi'¹, d.h.Hi'¹, und der vierte mit dem komplementierten Ausgang Bi'', d. h. ßj ^{+ l} sowie der Ausgang mit einem der 2 Eingänge des NOR-GliedsfP^verbunden sind(Fig. 13).

6. Rechenmaschine nach einem der Ansprüche 2 — 5, gekennzeichnet durch eine Schaltung Σ (F i g. 22) zur Berechnung der Summe S+ B,
die an den Ausgang des Addierers (ADDX) angeschlossen ist und deren Ausgang die Diagonaladresse X angibt, bis zu der »1«-Bits eingeschrieben werden müssen,

wobei die Diagonaladresse X auch mit ΛΊ, X₂, Xi bezeichnet ist, mit

X\ = das aus den 4 Bits mit hohem Gewicht der

Diagonaladresse gebildete Wort, ~³

X₂ = das aus den 4 Bits mit mittlerem Gewicht gebildete Wort und

Xi = das aus den 3 Bits mit dem geringsten Gewicht gebildete Wort.