Hinweise zum Entwurf von Digitalen Schaltwerken bei der Lösung von Optimierungsaufgaben mit dem Analogrechner
‘seine
B. Schrimpe, GS/N-B
HINWEISE ZUM ENTWURF VON DIGITALEN SCHALTWERKEN _
BEI DER LÖSUNG VON OPTIMIERUNGSAUFGABEN MIT DEM
_ ANALOGRECHNER
Zusammenfassung:
Ausgehend von dem in /1/ entwickelten Flußdiagramm zur auto-
matischen Suche eines Parabelminimums, ‚wird zur Lösung des
Problems mit Tischrechnern eine Möglichkeit des Entwurfs des.
digitalen Schaltwerks am Digitalzusatz DEX 102 (baw, DEX 100)
angegeben.
. Zur Minimisierung des Logikaufwands wird die grafische Verein-
fachung im Karnaugh- -Veitch Diagramm ‚benutzt.
/ı/ P. WIESENTHAL |
„Die Lösung von Optimierungsaufgaben n mit dem hybriden
Gleichspannungsanalogrechner ” :
AEG- Telefunken
‚ Sonderdruck AH 570. © |
"elektronische datenverarbeitung" |
Heft 1, Jahrgang 8 (1966) &
Seite 16 - 23
. - . ReSoUzV=0 2
.. . 7 . ; ausentaste
- . Co Pate Sy X32 Xo eee
Q: = Q(x,)
\ 5 =x “dx Der erste normale
eX Jterationstakt
nein
Us}
xix + dx
3. Ein Beispiel . 2 ja N nein j
Ein einfaches Beispiel möge das Zusammenspiel von Analog- —
und Digitalteil bei der automatischen Optimierung eines ein- Vel Rel)
are , Xi= X44 X
parametrigen Objektes erläutern.
: . ja nein -
3.1 Beschreibung des Optimierungsverfahrens nn (6: 12} : u u
Mis xe AX
Die Objektfunktion ist eine Parabel
i, 2 a, ReU=V=0 5=1
09 = „ax * bx 0) ac>0 un Axı=S, ais xx
Bild 8
H@sixt-180 , ' Flußdiagramm des Optimierungsverfahrens
Es gilt, das Maximum der Parabel zu finden, Die Aufgabe
wird durch iteratives Rechnen gelöst, Während des normalen
Taktes wird x um den Betrag A x verändert. Im komplemen-
üren Takt wird das neu errechnete Q(x +4 x) bzw. Q(x-Ax)-
mit dem einen Iterationszyklus früher berechneten Wert Q(x) ex _ Ax
durch einen Komparator -Verstärker verglichen (siehe Bild 11),
Die Boolesche Variable am Ausgang des Komparator -Verstär-
kers sei mit B bezeichnet, B ist gleich 1, wenn Q(x + Ax)
größer ist als Q(x) und gleich 0 sonst, Im Falle B= 1 hat sich
also das Objekt verbessert, .
Es kann aber auch sein, daß xq auf der anderen Seite des
Maximums der Parabel liegt, Dann muß xo nicht erniedrigt,
sondern erhöht werden und: es wird nach der ersten Operation
2B gleich Null sein, weil Q(xg - 4x) kleiner ist als Q(X) C):
; In diesem Falle wird die erste Operation wieder rückgängig
gemacht und anschließend x laufend um Ax erhöht, bis
schließlich Q(x + A x) kleiner ist als Q(x), und das Maxi- j
; ; Bu a * mum der Parabel überschritten ist, Nachdem die!letzte Ande-
Anhand des Flußdiagrammes (Bild 8) läßt sich verfolgen, nach ‘rung wieder aufgehoben ist, hat man offenbar einen Zustand
welchen Regeln x verändert wird, Fur die Variation stehen erreicht, in dem das Objekt nicht mehr durch Variation von x
zwei feste Schrittweiten S. und $ = > zur Verfügung, Zu mit der großen Schrittweite $1 verbessert werden kann, Im
. ı . Flußdiagramm ist nun der Konnektor @) erreicht und es gilt
Beginn des Optimierungsprozesses steht der Rechner in Stellung :
Pause und x hat den Wert x=x,. Nach dem Start derRech- | 1x - ul x 5, %) = x-Wert des Maximums),
nung wird x zunächst um den Betrag Ax= 5 erniedrigt, Dies.
wird durch den Ausdruck ... Bild 9 zeigt noch einmal den bisherigen Verlauf der Optimie-
xix -dx ; _— . "rung für die’beiden Fälle X, %y und x,>x
0 a ... Anschließend wird nun das Verfahren mit der Kleineren Schritt+ -
; os _weite So wiederholt, Wenn der Konnektor @ im Flußdia -
im Flußdiagramm angedeutet, Das Zejchen := ist zu lesen als: .
"ersetze durch”, Falls diese erste Änderung bereits erfol reich gramm auf dlese Weise zum zweiten Mal erreicht wird, ist ;
: ang 8 das Maximum der Parabel bis auf den Fehler.
war (B= 1) wird x auch weiterhin um ‘A x erniedrigt, bis Fu
schließlich B gleich 0 wird, d.h, bis das Maximum der Para. € =ix- x Ar) 5, ng
bel überschritten ist, Dann muß der letzte Schritt ruckgängig we eS
gemacht werden, d A x ist.um den Betrag 4 x zu erhöhen, _ gefunden und der Optinierungsprozes beendet, . .
N
Zunachst werden, ausgehend vom Flußdiagramm, alle vorkommenden
. Zustände des Digitalschaltwerks numeriert (Bild 1). Die Übergänge
zwischen den einzelnen Zuständen werden in Abhängigkeit von der
Steuergröße Bin einem Übergangsdiagramm dargestellt, dem man
dann auch die Ausgangssignale des Schaltwerks, nämlich Steuerung
des Vorzeichens und der Schrittweise der Parameteränderung, söwie
die Haltsteuerung entnehmen kann (Bild 2).
Aus dem Übergangsdiagramm gewinnt man die Übergangsgleichungen
für die Flip-Flops am besten durch Gegenüberstellung der Zustände vor
und nach dem Eintreffen des Takts in Form einer Tabelle (Bild 3). Darin
bedeuten "x" beliebige Zustände 1 oder 0 einer Variablen. Von den
2” = 32 möglichen Zustanden,. die die Variablen B, R,S,U,V beschreiben
können, werden hier nur 20 ausgenutzt; die restlichen 12 (am unteren
Ende der Tabelle) sind redundant und können zur Vereinfachung des Auf-
baus der Logik herangezogen werden.
Um das Schaltwerk mit den Flip-Flops des DEX 102 (DEX 100) zu reali-
„zieren, wird deren Übergangsverhalten untersucht:
R S
0 0 x . X = Zustand nach dem Takt
1: 0 0. i R = Stat. Steuereingang für
o | 4 ı = | Rücksetzen
1. 1 x S = Stat. Steuereingang für
Setzen |
Dies kann durch die Gleichung
X =S*+ X+R-X (1)
ebenfalls beschrieben werden. Bei der Vereinfachung der Uber- .
gangsgleichungen wird man also den Ausdruck für X als disjunktive
Verknüpfung von 2 Konjunktionen in Form der Gleichung (2)
xX =k et, (x) a x, 1) +X ef, (X: Ko XL) 9
f, 9 = Boole! sche Funktionen
darzustellen versuchen. ‘Durch Koeffizientenvergleich mit Gleichung (1)
erhält man dann sofort die an die Steuergänge R und S zu schaltenden
logischen Verknüpfungen der Variablen
| % RR x y .®&
Ry =f) &p Xp TX) (4)
Die Vereinfachung der Boole! schen Funktionen f und f, soll auf grafi-
schem Wege im Karnaugh-Veitch (KV)-Diagramm erfolgen. Dazu wird
_ Tür jede Variable ein KV-Diagramm. gezeichnet. Es wird dann überall
dort eine logische 1 eingetragen, wo die Variable lt. Tabelle nach dem
Takt den Wert 1 annehmen soll. Die grafische Vereinfachung wird so
durchgeführt, daß eine Gleichung von der Form der Gleichung (2) ent-
steht. u 7 re =
Zur Vereinfachung des Bintragens in. das Diagramm wird das 32er-Feld
für die 5 Variablen B, R, Ss, U, Vv in zwei 16er-Felder aufgeteilt, dessen
oberes durch B bestimmt wird, das untere durch B.
Den übrigen 4 Variablen R, S, U, V werden (in der Tabelle) in
dieser Reihenfolge Gewichte 8, 4, 2, 1 zugeordnet, so daß jeder
Zustand durch eine Dezimalzahl 0.... 15 bezeichnet undin die
Felder des KV-Diagramms eingetragen werden kann.
Für alle KV-Diagramme gilt, daß in die Felder mit den. Nummern
(7), (9), (13), (11), (14) und (15) das Zeichen X (beliebiger Wert
i oder 0) eingetragen werden kann, entsprechend den 12 redundanten
Zuständen.
Für die Variable R erhält man somit folgende. Gleichung:
R= Be (0) + Be (8) + Bes) + Be A)+Be (12)+B + (12)
In runden Klamrnern stehende Zahlen sind die Kurzbezeichnungen der
Zustände, das B bzw. B wählt das obere bzw, untere l6er-Feld aus.
& 2
timate a
gt
en er, .
Den tibrigen 4 Variablen R, S, U, V werden (in der Tabelle) in
dieser Reihenfolge Gewichte 8, 4, 2, 1 zugeordnet, so daß jeder
Zustand durch eine Dezimalzahl 0 ... 15 bezeichnet und in die
Felder des KV-Diagramms eingetragen werden kann.
Für alle KV-Diagramme gilt, daßin die Felder mit den Nummern
(7), (9), (13), (11), (14) und (15) das Zeichen X (beliebiger Wert
i oder 0) eingetragen werden kann, entsprechend den 12 redundanten
- Zuständen. _
Für die Variable R erhält man somit folgende Gleichung:
R = B« ()+B®e (8) + Be(s) + Be (4) +B (12) + B«* (12).
In runden Klammern stehende Zahlen sind die Kurzbezeichnungen der
Zustände, das B bzw. B wählt das obere bzw. untere 16er-Feld aus.
%
SO
YY
+ |
2 7 o
a rn :
u
RÄT ¥) ee)
Daraus folgt für die Steuereingänge R und S des Flip-Flop R nach
Gleichung (3) und (4): EEE ans |
gh = (3) +(10)+ + (4) + (12) + (6) + (5)
ek
|: .
Amn
un
W
Hos I
a.
n
oO
4 = B-(0) + B-(1) + Bo(8) + Bo(12) + Be(4) + B-(5)
x
x
XX
RU DXDXDX
Vi = (2) + (1) + (6) + (5)
ER).
SED
SL
mer
nx oe
SI
'
vie vile u) + v (a)
SR: U
Ry = U
Die Ansteuerung des Vorzeichens der Parameteränderung
(AX = 1 bedeute: positives Vorzeichen) muß, wie in der
Beschreibung der ‚Aufgabe bereits erwähnt, durch die Funktion ©
ere ae
realisiert werden.
Die kleinere. Schrittweite S wird direkt vom Flip-Flop S gesteuert.
2
Aus dem Übergangsdiagramm ist zu ‚entnehmen, daß ein Signal
STOP (für Halt) zu erzeugen ist, wenn der letzte Optimierungs-
schritt mit kleiner Schrittweite. eine Verschlechterung des Kriteriums
B gebracht hatte und deshalb dieser letzte Schritt zurück gesetzt wur-
de. Mit STOP wird deshalb ein Flip-Flop H gesetzt, das mit seinem
Ausgang H direkt die Haltsteuerbuchse ''Ha" des Rechners aktivieren
kann.
STOP = RSs-U.V oRsmv
Ho = (12) + (5)
RR.
Rays
JOC
KX
H = RS Ve
Es genügt, den Setzeingang des H- FF zu 1 beschalten, da die Rück-
setzung automati sch erfolgt.
“4.
ere
Um einen Überblick über die Steuersignale für die einzeln gesteuerten
Speicher des Analogprogrammteils zur Berechnung des Kriteriums B
zu gewinnen, sind in (Bild 4 ) die zeitlichen Vorgänge bei den einzelnen
Speichern kurz aufgeführt. Es ergibt sich daraus, daß am Ende der
Rechenzeit an den Speichern die gewünschten Vergleichswerte anstehen |
und damit das Kriterium B als Steuergröße für das Schaltwerk gewonnen
wird. Demzufolge muß zu diesem Zeitpunkt das Schaltwerk getaktet
werden.
Soll der Optimierungsvorgang selbsttätig ständig von neuem beginnen,
muß folgende. Steuerung des Rechners vorbereitet werden:
1. Das Signal H wird mit einem Zeitglied Z 1 verzögert. Das
verzögerte und invertierte H-Signal wird zur Aktivierung des
Zustandes "Pause" über die Buchse "Pa'' am Rechner ver-
wendet.
2. Nach nochmaliger Verzögerung mit einem Zeitglied Z 2 bewirkt
das H-Signal, an die Buchse "Lé6" des. DEX 102 gelegt, das
Löschen sämtlicher Flip-Flops. Damit werden Halt-und Pausen-
zustand aufgehoben, so daß der Optimierungsprozeß von neuem.
beginnt. Z 1 bestimmt die Haltephase, Z2 die Pausenzeit, während
der alle Speicher den ersten Anfangswert + Xo bzw Qt Xo) auf-
nehmen können, Dazu werden die R-Buchsen der normalen Speicher
mit dem Ausgang Z1 verbunden (s. Analogprogramm).
Disjunktive Verknüpfungen von Z 2 und Zimit dem Signal "PT"
(Pausentaste gedrückt) erlauben die Normierung der Flip-Flops
und die Anfangswertaufnahme bei gedrückter Pausentaste.
Die Schaltungen für Analog- und Digitalprogrammteil zeigen (Bild 5) und
Bild 6). RR : Ber ” =
DEFINITION DER ZUSTANDE
1:
Bild
Nr.
ri N
10
11
12
UBERGANGSGLEICHUNGEN FUR DIE FLIP-FLOPS
Bild 3:
an Ry
~~ „ 35
3 lal = So N 5
= un nn Se a
a CGe tes
S gL NPM ornntyroaaomanan 5% Se
Ne rm riod 3 So
% EN .2>
EI
Ey + u
S > OCmrnmmooeoooo oor AS KM MK -
[a] . j
e > HOOHSCOCOHOCOOHHOO ae MMM
Tan] . .
~
i
Q un ooooHooo HH HH rim re Ps Pd bt bd
Bi
fy f+ 7
; a oeoooo HH HOH HHOOGO SO me OM.
+ . Be
men 2 a
> SoOHrHHmooooooooon. HHrHmon
gr OHMoo"HoOo0o"H0o000H0o00©0 HOH Ons)
Si:
ord
a .
Ss n Sooooooo0o0O HH Hr nH eG AOOn nA Ss
O° ,
“ ant S°7OCDC OHHH OHH OOOO SH Hrn
2
S
im SKK HoXmmoKHmmHooNno
od
eal
bd bd it bd Ot be
‘ Bild 2: ÜBERGANGSDIAGRAMM FÜR FLIP-FLOP-ZUSTÄNDE
| , | AWEGRMESICHALE
(Schr iitresre & .
VET ECI CM EL der Para tate hog
BUA Lp EEE LX |
Helis Cisloet TER)
: ’
u X 4
n
N
AX
Seo
Bed.
Bo
AX
x
u AMA LOG
TEL
Rechenzustand
Speicher Pausentaste Rechnen Pause Rechnen Pause
gedrückt _
SP 4 Anfangswert x wird! folgt den anstehen- | halt den anst ehen- folgt halt
aufgenommen den Größen x, und x: den Wert
® X =X ay = —(x 24x) = — (x, +Ax) X= 4x4 24x) , ZAX
SP 2 folgt SP 1 halt seinen Wert folgt den anlie- | halt folgt
Anfangswert x_ wird ‘| genden Größen
aufgenommen;
od > ©) OU |.) Te
x x (x 3 Ax) (x, +Ax) (x, Saar)
SP 3 ninat als Anfangs- |folgt der Eingangs- hält den anliegen-|. folgt hält
wert Q (x) auf: größe den Wert 7
wo ye py 3
40 (x) Fates |” amsanı PY amazn | a(x earn)
sp 4 [folgt sp 3 hält alten Wert - | folgt der anliegen! hält folgt
Q (x) wird aufge- den Größe
nommen:
a a ee eet eo
~ Q(x) Zax) Pa (x, 44x) g(x 44x) Aal 228%)
4) Am Ende des Zustandes "Rechnen" stehen
an den Speichern 3 und 4 die einge-
rahmten Werte an, so daß das digitale
- Steuerwerk mit dem daraus abgeleiteten
Signal B gesteuert werden kann.
‘Die mit (#) bezeichneten Größen
geban die analogen Werte aller
Speicher am Ende des jeweiligen —
Rechenzustandes an.
Bild 4: ZEITLICHER ABLAUF DER SPEICHERZUSTÄNDE
as
Ryd YADA DD My
>
‘ a 8 wie
SAE
wy 4. 19
fy Lo, ZEN
al.
; ln wessauzt 7 we Sanat race — san ae -
£
HATFGEETULGIE FRITZ
ei ET mers ey