English translation
Hinweise zum Entwurf von Digitalen Schaltwerken bei der Lösung von Optimierungsaufgaben mit dem Analogrechner
Complete English translation of the original German-language document (17 pages).
Notes on the Design of Digital Logic Circuits for Solving Optimization Problems with the Analog Computer
H. Schrimpe, G3/N-B
Abstract
Starting from a flow diagram developed in [1] for the automated search for parameter minima, the solution of the problem of finding local minima using the digital logic circuits of the DEX 102 (or DEX 100) analog computers is described. For minimizing the logic expenditure, the Karnaugh–Veitch diagram is used for simplification.
Reference:
[1] P. Wiesenthal, “Die Lösung von Optimierungsaufgaben mit dem hybriden Gleichspannungsanalysator” [The Solution of Optimization Problems with the Hybrid DC Analyzer], AEG-Telefunken, Sonderdruck AB 370, “elektronische datenverarbeitung,” Heft 1, Jahrgang 8 (1966), pages 16–23.
0. Introduction
The task described consists of automatically finding the extremum of a criterion function by means of an analog–digital (hybrid) computer. Starting from a flow diagram for the automated optimization of a cost criterion:
$$Q(t) = \frac{1}{2}a \cdot X^2 + b \cdot X + c$$
this expression can also be written as:
$$Q(t) = \frac{1}{2}a \cdot X^2 - b \cdot X$$
In the flow diagram, Z denotes a “counting” variable and X an “analog” variable. The flow diagram begins at the start. From the start, the sign of Z is checked. If Z = 0 (i.e., there is no Takt yet), the system goes to the block that computes Q(t). The flow then proceeds to the next comparison: if Q(t) < Q_0 (where Q_0 is the previously stored value of Q), then the system branches accordingly. If Q(t) < Q_0, the new Q value is stored as Q_0, and the process of parameter variation continues.
1.1 Introduction
The flow diagram shows the flowchart of the optimization process.
The flow diagram describes the functional sequence of the optimization as follows:
- Start
- The sign of Z is tested. If Z = 0, the criterion Q(t) is computed.
- A comparison is made: is Q(t) < Q_0?
- If yes: Q_0 is updated (Q_0 := Q(t)); the sign of the parameter change ΔX is set to positive; and the process continues.
- If no: the sign of ΔX is checked; if ΔX > 0, the parameter is decreased (ΔX becomes negative); if ΔX < 0, a STOP is generated.
The flow diagram (Fig. 1) illustrates the optimization sequence.
In the flow diagram, the following decision paths are shown:
- Q(t) is computed at each Takt.
- If Q(t) < Q_0: Q_0 is updated, ΔX is kept positive, the next Takt begins.
- If Q(t) ≥ Q_0: the sign of ΔX is tested.
- If ΔX > 0: ΔX is reversed (ΔX → negative), Q_0 := Q(t), the next Takt begins.
- If ΔX < 0: STOP.
The largest Takt value X_y corresponds to the optimal Takt. With STOP, a Flip-Flop H in the computer is activated through its output “Hi”, which can lock the hold state.
2. The Transition Table and State Encoding
From the flow diagram, a transition table for all states is derived. The transitions between states are expressed as a function of the boundary conditions (sign of Z, comparison result Q(t) vs. Q_0, sign of ΔX), as well as the parameter-steering variables.
The logic circuit is to be realized using the Flip-Flops of the DEX 102 (or DEX 100). The transitions are given in Table 3 (Transition equations for the Flip-Flops).
The states of the digital logic circuit are encoded with the variables:
- X* = State after the Takt
- R = Stat. Steering for Forward
- S = Stat. Steering for Backward
2.1 State Definition
A table of states (see Table 1: Definition of States) lists the numbers 1 through 12 (and beyond), with columns B, S, U, Y:
| No. | B | S | U | Y |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 1 |
| 3 | 0 | 0 | 1 | 0 |
| 4 | 0 | 0 | 1 | 1 |
| 5 | 0 | 1 | 0 | 0 |
| 6 | 0 | 1 | 0 | 1 |
| 7 | 0 | 1 | 1 | 0 |
| 8 | 0 | 1 | 1 | 1 |
| 9 | 1 | 0 | 0 | 0 |
| 10 | 1 | 0 | 0 | 1 |
| 11 | 1 | 0 | 1 | 0 |
| 12 | 1 | 0 | 1 | 1 |
3. Derivation of the Transition Equations
3.1 General Approach
The state encoding uses the Boolean variables B, R, S, U, V (as listed in the table). Since each state is encoded as a decimal number 0 through 15, each state can be entered into the fields of the KV diagram (Karnaugh–Veitch diagram). Of the 2^4 = 16 possible states, only 12 are actually used; the remaining 4 (at the end of the table) are redundant and can be used to simplify the logic construction.
In the logic circuit, the Flip-Flops of the DEX 102 (DEX 100) are to be realized. For the 5 variables B, R, S, U, V in the table, each state is encoded in decimal notation 0 through 15, so that each state can be entered into the KV-diagram fields with decimal 0 through 15 can be entered.
For variable B, the following equation must hold:
$$B^+ = B \cdot (U \cdot \overline{V}) + B \cdot (\overline{U})$$
(numbers in brackets are the state-number cross-references of the states where B = 1 or where the upper/lower 1-field applies)
The simplification of the Boolean functions is accomplished using the KV diagrams. For each variable an individual KV diagram is drawn. For that purpose, the logical 3-table is set up. In the Takt column, the decimal value 1 is entered. For all pairs of variables forming the KV diagram, those entries where the criterion yields value 1 are marked.
The graphic simplification is carried out using the KV diagram as follows:
The simplification of the Boolean function of B uses the following combination method: the Boolean product expressions obtained from the KV diagrams are combined (ANDed and ORed) to yield minimal expressions.
The KV diagram for the 5 variables B, R, S, U, V is arranged in a 16-field layout. The entries in the numbers 0 through 15 designate the states from which B becomes 1, and B̄ means the upper row or lower row of the field.
4. Derivation of Control Equations for Individual Flip-Flops
4.1 Variable B
From the transition table, the next-state value of B is:
$$B^+ = \overline{B} \cdot (U \cdot \overline{V}) + B \cdot (\overline{U} \cdot V)$$
(where the terms in parentheses are the Karnaugh groupings from states (7), (8), (11), (12), (4), (5), (6))
From this, the set and reset inputs of Flip-Flop B follow from equations (3) and (4):
$$S_B = \overline{B} \cdot (U + \overline{V})$$ $$R_B = U$$
4.2 Variable S (Steering for Backward)
$$S^+ = \overline{B} \cdot \overline{(U \cdot \overline{V})} + B \cdot (\overline{U})$$
From the KV diagram for variable S (the 5-variable, 16-field layout):
$$S^+ = \overline{U} \cdot (\overline{B} + U) + V \cdot (\overline{U})$$
$$S_S = \overline{B} \cdot U$$ $$R_S = 0$$
4.3 Variable U
$$U^+ = \overline{B} \cdot \overline{(1)} + \overline{B} \cdot (11) + \overline{B} \cdot (12) + \overline{B} \cdot (13) + \overline{B} \cdot (14) + \overline{B} \cdot (15)$$
From the KV diagram for variable U (with 5 variables):
$$U^+ = V \cdot (\overline{B} \cdot U) + V \cdot (\overline{U})$$
$$S_U = \overline{B} \cdot U \cdot V$$ $$R_U = 1$$
5. Sign Sensing of Parameter Changes
5.1 Sense of the Sign (dX)
The sensing of the sign of the parameter change (dX = 1 means positive sign must hold, as stated in the task description) is realized by the function:
$$\delta X = U + \overline{U} \cdot V + U \cdot \overline{U} + \overline{V} \cdot U$$
5.2 The Smaller Step Size S_w
The smaller step size S_w is measured directly via Flip-Flop S. From the flow diagram it is apparent that the optimization step STOP (for Null) can cause a deterioration of the criterion Q. The STOP signal brings a Flip-Flop H through its output “Hi” in the computer, which can lock the hold state.
$$\text{STOP} = \overline{B} \cdot \overline{S} \cdot \overline{V} + \overline{B} \cdot \overline{S} \cdot V$$
$$H^+ = (12) + (1)$$
It is sufficient to drive the set input of the H-FF, since the reset occurs automatically.
6. Overview of the Control Logic
To provide an overview of the most recently activated memory of the analog computer for computing criterion B, the following sequence for storing was carried out. It results from the following:
-
The digital logic is to start by itself with a new Takt (time step). The computer does this by sending a “Pause” signal via the digital computer “Pa” to the analog computer.
-
For the next Takt, a digital signal Z (= 2) triggers the storage of identical states in the DEX 102, and an H-signal (HH signal) is generated at the same time. The digital program is switched to normal operation via the Pause flip-flop connected to input Z = 1 of the analog computer. The disjunctive program switches between Z = 2 and Z = 1, and the drive signal “P1” (generated as the junction of Z and 1) ensures the normal Pause flip-flop at the pressed Pause state and its value-hold hold at the pass state.
The switching diagrams for the digital and analog programs are shown in Fig. 51 and Fig. 61.
Table 1: Definition of States
| No. | B | S | U | Y |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 1 |
| 3 | 0 | 0 | 1 | 0 |
| 4 | 0 | 0 | 1 | 1 |
| 5 | 0 | 1 | 0 | 0 |
| 6 | 0 | 1 | 0 | 1 |
| 7 | 0 | 1 | 1 | 0 |
| 8 | 0 | 1 | 1 | 1 |
| 9 | 1 | 0 | 0 | 0 |
| 10 | 1 | 0 | 0 | 1 |
| 11 | 1 | 0 | 1 | 0 |
| 12 | 1 | 0 | 1 | 1 |
Table 2: Transition Equations for the Flip-Flops
The table lists input combinations (B, S, U, Y) together with the next-state FF-state X* after Takt. For states 16 and 17 the entry is marked STOP. States marked X are redundant states that can be exploited for simplification.
| B | S | U | Y | B* | S* | U* | Y* | State No. | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | |
| 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 3 | |
| 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 4 | |
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 5 | |
| 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 6 | |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 7 | |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 8 | |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 9 | |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 10 | |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 11 | |
| 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 12 | |
| 1 | 1 | 0 | 0 | — | — | — | — | 16 STOP | |
| 1 | 1 | 0 | 1 | — | — | — | — | 17 STOP | |
| X | X | X | X | X | X | X | X | Redundant states, usable for simplification |
Fig. 3: Transition Diagram for Flip-Flop States
[page 14: figure only — state-transition diagram showing states 1 through 12 (and STOP states) with labeled transitions for conditions ΔS=0, ΔS=1, ΔU=0, ΔU=1, Step-1, Step-7, etc.]
Fig. 4: Temporal Sequence of Memory States
The figure shows the timing of the memory (register) states of the control logic, with the following columns:
- Takt (clock step)
- Possible activity (column: Eintreffen = Arrival)
- Columns: Eintreffen (Arrival) | Pause | Rechnen (Compute) | Pause | Pause
The table of operating-state sequences:
| Takt No. | Possible Activity | Arrival | Pause | Compute | Pause | Pause |
|---|---|---|---|---|---|---|
| SP 1 | Output aligned to the computer at input Z=1; aligned to the next single-step value X_0 (largest); analog computer operates normally | Q(t) ≥ Q_0 | Null | next value X_0 (largest) | Q(t) | — |
| SP 2 | If SP 2: output Q(t) ≥ Q_0; go to next criterion value | Q(t) ≥ Q_0 | holds next value | Q(t) ≥ Q_0, holds next | — | — |
| SP 3 | If SP 3: output criterion value at end; go to largest value | goto largest value | null | go to largest value | — | — |
| SP 4 | If SP 4: signal at end of smallest value | STOP | at smallest value | null | — | — |
*) In the last column (“Pause state”), the value X is received from the computer at input Z = 1; then the new digital signal S is passed digitally on and is held at the Pause state of the held value.
Fig. 4: Temporal Sequence of Memory States
[page 16: figure only — schematic diagram labeled “Analog program for the optimization algorithm DEX 102/DEX 100”, showing the digital logic block (labeled “DIGITAL-TEIL” / Digital Part) connected to analog computing elements including operational amplifiers, comparators, and interconnections for the criterion function Q(t), parameter X, and control signals B, R, S, U, V, STOP, Pause/Hold inputs and outputs.]
[page 17: figure only — detailed logic circuit schematic labeled “Digital Part for the Optimization — DEX 102/DEX 100”, showing the complete Flip-Flop network (FF B, FF S, FF U, FF V, FF H) with their set (S) and reset (R) inputs, the AND/OR gate network implementing the Boolean transition equations derived in the preceding pages, and the output lines for R (forward steering), S (backward steering), STOP, and the Pause control signal to the analog computer.]