A Block Diagram Compiler By JOHN L. KELLY, Jr, CAROL LOCHBAUM, and V. A. VYSSOTSKY (Manuscript received December 7, 1960) A computer program known as BLODI, which accepts for an input a source program written in the BLODI language, is described. The BLODI sourze language corresponds closely to an engineer's block diagram of a circuit and is easily learned, even by persons not familiar with computing machines. The input code consists essentially of designating the connec- tivity of a number of boxes drawn from an alphabet of about $0 types. ‘These types include amplifiers, delay lines, counters, ete., which are familiar to designers of electronic circuits. The principles of the compiler are ex- plained and applications are discussed. 1. INTRODUCTION ‘This paper describes a computer program known as BLODI (BLOck ‘Dlagram compiler). BLODI accepts for an input a source program writ- ten in the BLODI language, which corresponds closely to an engineer's block diagram of a circuit, and produces a machine program to simulate the circuit BLODI has been written for both the IBM 704 and 7090 machines, and has been in use at Bell Telephone Laboratories for several ‘months. Generally speaking, there are two situations in which it can be used profitably. One arises when a person with no knowledge of machine coding wishes to program his own problem. In this ease, the BLODI language is much easier to learn than Fortran or SAP. There are, in addition, certain problems involving a rather smooth flow of data which can be most easily coded in BLODI, even by an experienced program- met. I: is rather easy to estimate the efficiency of an object program pro- duced by BLODI. Thus a person with no knowledge of computing ma- chines can often tell if he should code his problem in BLODI or seek the aid of an experienced programmer. This will be discussed in Sec- tion V. BLODI was written to lighten the programming burden in problems ‘concerning the simulation of signal-processing devices. It has the added 660 670 ‘THE BELL SYSTEM TECHNICAL JOURNAL, MAY 1961 advantage of keeping the engineer who invents stich a device in close communication with the computing machine by eliminating the middle- ‘man (expert programmer), II, BLOCK DIAGRAM OF SAMPLED (OR PULSE) SYSTEMS ‘The cireuits* which we wish to consider here are limited to combina- tions of devices which accept pulses as inputs and yield pulses as out- puts. While the pulses may have arbitrary sizes within certain limits, they must all occur at multiples of a fixed clock time. In general, the output of one of the devices (or boxes) can depend on the present and all past input pulses. A box whose output is independent of the current input. pulse or pulses is called a delaying-iype box. In the current form of the compiler the only delaying-type box is a simple delay line. In addition to these boxes, the circuit may have one or more ultimate out- puts and original inputs. A circuit then means a number of boxes, ulti- mate outputs, and original inputs connected in such a way that the output of any box is connected to one or more inputs to boxes and ulti- mate outputs, and each input to a box is connected to an output from a box or an original input. (We limit ourselves to boxes with a single output.) ‘A closed loop is a path that starts from any point, goes only through connected boxes in the direction of the pulses (ie., input to output), and returns to its starting point. A circuit which does not contain a closed loop with no delaying-type boxes will be called an admissible circuit. The compiler will reject any block diagram which does not de- scribe an admissible circuit. It is easy to see that if the pulse heights were limited to a finite number of values (as they are, of course, in the machine simulation) then an admissible creuit would be a finite-state machine. On the other hand, there is no way to interpret a block diagram corresponding to a nonadmissible circuit. To be sure, one could connect physical boxes in such a manner and something would happen. ‘The analysis, however, would involve the precise transient behavior of the devices within the pulse width — information which is not available to the compiler. In addition to simulating pulse circuits, the compiler may be used to simulate continuous cireuits whose inputs and outputs are bandlimited time functions. One must first design a pulse circuit whose output pulses would correspond to the sample values of the desired output. Extreme * For clarity the machine being simulated will be ealled the eireuit, Its de- scription in a certain canonjeal form will be called the block diagram. ‘The word ‘machine will always mean the IBM 704 EDPS (or 7000 EDPS), BLOCK DIAGRAM COMPILER oz ‘care must be exercised here; for example, an accumulator (a device whose output is the sum of all previous input pulses) is not equivalent to an integrator. Certain continuous circuits (especially nonlinear ones) are extremely difficult to translate into pulse form. A simple cireuit which is difficult to simulate on a machine (with or without the use of this rompiler) is the following: Let a bandlimited input signal be con- nected to a full-wave rectifier, and this to a low-pass filter to return the signsl to the original bandwidth, ‘We will see later that (with a trivial exception) the compiler can be used to simulate any admissible circuit composed of boxes drawn from 1 fixed list or stockpile. The boxes may have only one output (which may go to several places, however) and at most four inputs. The first cons:raint is no real restriction, but the second one is.* We know of no example in signal processing where a general function of more than four variables that cannot be expressed as combinations of functions of four or less variables is needed. In fact, two inputs to each box would proba- bly be adequate but slightly awkward. HI, THE BLODI LANGUAGE A BLODI source program is punched on standard SHARE symbolic cards in either the FAP (7090) or SAP (704) format. In general, each ‘card corresponds to one box in the circuit; there is, however, a provision made for continuing a description of a box to the next card. The loca- tion field (columns 1 through 6) is either blank or contains the name assigned the box by the programmer. (If a box is to have any inputs, it must have a name.) The operation code field (columns 8 through 10) contains the type of box. Parameters (such as gain of an amplifier) and ‘output connections are separated by commas and listed consecutively starting in column 12 (or column 16 for the 7090 format). The various inputs to the sume box are designated by a fraction bar and numeral following the name of the box. Example: UV AMP 5.28, XY, 2/2 Box UV is an amplifier with a gain of 5.28 which feeds box XY (first input) and the second input of box Z. list of all the available bos types appears in Table I. Note that INP may be thought of as a box which generates signals spontaneously; ac- ut from a tape designated as a parameter. Simi ‘Taste I — Aut tae Tyres or Boxes Wutc ane RECOGNIZED BY THe COMPILER — Fonion mts Femtes DEL Numer of wits AMP: Gain” atk Sone 308 Nowe Max None MN None ron Gipring level CN Gioig evel otis ing level EWR | Pullewave rect None BAR | Bauary or bas Nee | Mutter BW | Divider yr | square rooter AGG | Aictinlater . BL | tanoversal alter Number of tape Delay per sur | symmetric ster Signal Number of tape vm ens Belay ‘per tap APL | Antisymmetric ster | signal Number of taps Delay'per tay ant | Quantizer Ruber of lvels tot | ui i Sipe near quantizer op ce SMP | Sampler Pertod Quiescent level Bier pase HED. | Sample and hold Tireabsl ENE | Goudie Countdown factor Threshold Active level Passive lovel Tatil phase Dts | Double-throw switch Threat vue fp Low threshold High thresold Ese tate outpat High state output PIS | Pulser Control ‘Threshold Pulse Henge Pulse level gusscent level 098 | Cosine generator | None ‘ cen | Function generator | None Sample valuos WNG | Noise generator None Standard deviation Tar | Bante Contra; Tieshola| Tagnals | Record Limit ‘BLOCK DIAGRAM COMPILER 673 ‘Tanue I — (Continued) Tre Panction | pats Parameters TP | Input None “Tape number ] File maximum Start printing Stop printing pur | Output Signal Tape number Samples per record Record maximum Stare printing Btop printing END | Last card of source program larly, OUT causes the signal appearing on its input lead to be written on the designated tape. A circuit may have several inputs and outputs. END is not a box at all but signifies the end of the source program, In addition to the types listed, it is possible for a programmer to create types of his own invention by supplying subroutines written in basic ‘machine language. Tt is also quite easy to change the basic input-output programs used by BLODI to handle arbitrary tape formats. IV. PRINCIPLE OF OPERATION ‘An object program produced by the compiler consists of three parts: (a) the prefix, which sets up the logic for the main loop; (t) the main loop, which is exeeuted once for each sumple processed; (©) the sufir, which causes the main loop to be repeated the proper number of times, empties output buffers, fills input buffers, ete. ‘We will concern ourselves here only with the main loop. Except for some strictly local inner loops in certain boxes, this part of the object program is compiled in the same order in which it is to be executed. Sim- ply stated, the procedure is as follows: One storage cell in the object program is assigned for each box. Each time the main loop is entered, ‘these cells will contain values corresponding to the last outputs of the respective boxes. It is then the function of the main loop to compute these output values for the next (current) time slot and to fill the cells with these values. In order to simplify the description of the algorithm used by the com- piler we will at first limit ourselves to the case where all delays are unit delays. By “compiling a box” we mean writing the necessary coding to 674 THE BLL SYSTEM TECHNICAT, JOURNAL, MAY 1901 cause the object program to fill the output cell of the box with the cur- rent pulse value. A nondelaying-type box eannot be compiled until all the boxes feeding it. have been compiled. ‘The reason is that the output of this type of box is a function of its ewrrent inputs, and this part of the object program must not be executed until the cells corresponding to input to this box have been filled with current pulse values. On the other hand, a unit delay must be compiled before the box which feeds it. Its ‘output is a function of (equal to, in fact) its last or old input. At object time this value must be “moved along” before it is overwritten. To re- word this second rule, no box which feeds a delay line can be compiled until that. delay line has been. This second rule could be dropped if we provided an additional storage cell for each unit delay and had the ob- ject program first go through and fill each of these cells with the old in- put to the corresponding delay line. We will see below, however, that the only price we pay for the more efficient. procedure is that. the com- piler will reject any block diagram containing a closed loop with nothing but delays. Such a diagram would represent an admissible circuit but would be of little value, since we could never get anything but zeros out, of this loop at any point. (All delay lines are initialized at zero.) ‘The above two rules are effected in a fairly simple manner. A binary storage cell is assigned in the compiler program for each of the output cells in the object program. The two states of each of these cells are called “full” and “empty.” Initially all cells which represent. inputs to delay lines are marked “full” and all others marked “empty.” A box ean be compiled whenever its inputs are all marked “full” and its output “empty.” When a box is compiled, its output is marked “full” and its inputs “empty.” Compilation proceeds until all boxes have been com- piled (successful compilation) or until no uncompiled box meets the two requirements. In the latter event the compiler prints the remark CLOSED LOOP WITH NO DELAYS OR ALL DELAYS and halts. To see that one of these conditions must prevail, note that a delay line can always be compiled unless it feeds another uncompiled delay line. ‘Therefore, if any of the uncompiled boxes are delay lines there exists a closed loop with all delays. If, on the other hand, all uncompiled boxes are nondelaying, then each must have an empty input which must be the output of an uncompiled nondelaying box. Thus, working back- ‘wards, we find a closed loop with no delay. ‘The order of searching for uncompiled boxes which meet the tests is immaterial from a logieal point of view, but this freedom can be used to optimize the use of the accumulator. By first trying to compile a box «d box, the compiler is sometimes able to order, or both. Delays are not, of course, which is fed by the last eomy save a “storage” or “fetch” BLOCK DIAGRAM COMPILER 675 limited to unit delays as in the above discussion. A delay of length n sets n — 1 storage cells in addition to its normal output cell. For short delays the data are “stepped along” a notch each time the main loop is execited, For longer delays the same effect is produced by address ‘modification. "The above description is merely a sketch of the general procedure used by BLODI. Actually, it has a lot more structure of purely technical character. For example, some boxes are broken down into simpler boxes by the compiler so that parts of the object program concerning a given box may not appear in consecutive locations. Y. CONCLUSIONS BLODI has been in use at Bell Telephone Laboratories for about a year, mostly in the Department of Visual and Acoustics Research. It has been used chiefly for signal processing types of problems, and one of the authors has used the compiler to simulate a speech synthesizer of the resonant-vocoder type. Tt has also been used to study television coding schemes, artificial reverberation in acoustic research, and for part of the coding in a handwriting recognition problem. Tn appraising its value one must consider two separate questions: 1, What type of problem is easily coded in the BLODI language? 2, What type of problem causes BLODI to write efficient object programs? ‘The first question will be answered relative to a programmer well versed in basic and Fortran language. Whenever the problem involves rather smooth flow of data in and out of the machine, with the output being a nearly stationary function of the input, then it ean be more easily oded in BLODI than in any other existing language. When, however, the program must process input samples in a complicated order, de- pendent on previous results, the BLODI language becomes unbearably awkward. (This is precisely the type of circuit which is hard to design with delay lines, switches, ete.) ‘The second question is easily answered. Any diagram which contains maty idle boxes will be inefficient, because the object program goes through the motion of calculating the state of all boxes at each clock time. For example, a program with five memory-free (delay-free) paths, only one of which is connected to the output at any one time, would re- sult in an inefficient object program. For diagrams containing few idle boxes, however, BLODI produces object. programs which are usually as efficient as those written by a competent programmer. ‘The version of BLODI in use at Bell Telephone Laboratories is coupled to the monitor and I-O system, BE SYS 3. Thus an installation not us- 676 ‘THE BELL SYSTEM TECHNICAL JOURNAL, MAY 1961 1 Noise ricrer enenatoR| cuPer Fig. 1 — Typical BLODI progran: block diagram. £-e:a0t sauce proaeme - Sun AOR eu ogLev et ———t rset, sue-e—————— —— nsuEi-2 a —— sue Sind Sub /L PRINT Za vO0e 4 suet sup THESE CARDS AND THE CARDS WARKEO a puR. Pernt PRY 150 PRINTING WERE NOT DESIRED Fig. 2 — Typical BLODI program: source program ing BE SYS 3 would have to modify the BLODI program. The changes, however, would only involve 1-0 and interaction with the FAP (or SAP) assembly program. Figs. 1, 2, and 3 represent a sample BLODI program. Fig. 1 is a block diagram suitable for simulation using BLODI; Fig. 2 is the correspond ing source program; and Fig. 3 shows the printed output that results from compiling the source program and running the simulation. REFERENCE 1, Frighkopt, LS. and Harmon, LD, Machine Recognition of Cursive Seript, ‘Fourth Annual Symposium on Tnformation Theory, 1900. ig 3 —Typlal BLODI program: pinta oats,