Download Synthesis of Digital Automata / Problemy Sinteza Tsifrovykh Avtomatov / Проƃлемы Синтеза Цифровых Автоматов PDF

TitleSynthesis of Digital Automata / Problemy Sinteza Tsifrovykh Avtomatov / Проƃлемы Синтеза Цифровых Автоматов
Author
LanguageEnglish
File Size5.8 MB
Total Pages180
Document Text Contents
Page 1

SYNTHESIS OF DIGITAL AUTOMA TA

PROBLEMY SINTEZA TSIFROVYKH AVTOMATOV

np06JIEMbI Cl1HTE3A WH>POBbIX ABTOMATOB

Page 2

Synthesis of Digital Automata

Edited by
v. G. Lazarev and A. V. Zakrevskii

Laboratory of Automatic Control Devices
Institute for Problems of Information Transmission

Academy of Sciences of the USSR
Moscow, USSR

Translated from Russian by

Edwin S. Spiegelthal

® CONSULTANTS BUREAU· NEW YORK - LONDON· 1969

Page 90

82

23

29

IbI6



A. D. ZAKREVSKII AND V. 1. OSTROVSKII

1515 9

Fig. 3

2

Fig. 4

~~UI6I6UU~U ~~g ~m~~



We now give the program for the al-
gorithm described, in which the previously
described internal and external operands
retain the same meaning. To these, we add
only the single variable h, representing that
one-element, or two-element, increment Q

h : : II {Q}:l A II,
which, when added to the variable set at
depth 1-3, gives a covering. Such increments
are produced by the operators 0 d n 0 p 0 k
(one-element) and d v y p 0 k (two-element);
in the absence of the covering being sought,
variable h is assigned the value zero. We
give here the corresponding subprograms:

odmopok etK+, ~rr+, rrr+, fJn/a, a
650 40 2 (~a)
06 ~=}a

§ 1 a 3: 2a eta -[/\ r i~ 1 Ca =} 6
§ 2

dvapok etK+, ~rr+, rrr+, 6rr, err+/c,b
651 73 3 (~ab) (rc)
06E=}b

§ 1 b I 3 b etb 1/\ r =} c ~ EB Cb =} a
§ 2 a I la eta 1/\ C l-+ 2Cb V Ca =} 6
§ 3

In each of these subprograms, as in the previous ones, the matrix being operated on is
specified by array O! and variables f3 and 'Y. Program 0 d n 0 po k seeks a single-row covering
in it, and represents its value by variable 6; if there is no such covering, 6 is assigned value
zero. Program d v up 0 k performs the analogous task, seeking a two-row covering with one of

Page 91

OPTIMIZING THE SEARCH FOR SHORTEST COVERING 83

the elements being noted by the value of variable £., which can be considered as one of the columns
of the given matrix in transposed form.

The operation of determining the value of this variable by transposing the leftmost of the
columns of the matrix being analyzed is performed by subprogram trale s to, outputting this
value via variable 6:

tralesto aK+, ~n+, yn+, ~n/b,b
4 57 2 (~a) (yb)
o ~ yf- ~ b Cb =? b~ =? a

§ 1 a ~ 2a aa 1\ b o~ 1 Ca V ~ =? ~ ~ 1
§ 2

The last of the new subprograms to be introduced is m a k s t r 0, which finds the maximal
row of a matrix, outputting its result, i.e., the row's ordinal number, via index 0 :

makstro aK+, ~n +, yn + , ~u/a, b
3 47 2 (~a)
Ob ~=?a

§ 1 a ~ 2a aa /\ y v - bo~ 1 + b =? b a =? ~ -'> 1
§ 2

The program as a whole then has the following form:

okrapok aK+, ~n+, yn+, ~K, en/h, f
652 306 11 (~dejh)(yag)

1 =H Of Oe oba ~ =? j Y =? g
§ 1 sokramin a jg / I minstro a jgd I / d 0-+ 4 makstro a dgc II c =? a

Ca EB d =? d
§ 2 aall\g=?ao~3 caffij=?j(jgde)=?~ caVe=?e a=?g 6eEBfl-

0~5~1

§ 3 Ca V e =? E II~ 10 ~ 6
§ 4 \I~10d~4a~2.
§ 5 tralesta ajgd II odnopok adgh / / h o~ 7 h Ve =? E \I~ 10
§ 6 11-'> 10 e =? f
§ 7 dvypok ajghd / / h o~ 4 h V e =? E ~ 6
§ 10 6e o~ 11 ~ =? (fgde)!
§ 11 .

As has already been mentioned, programs so k ram i nand min s to are quite laborious.
This is related to the facts that, in executing program so k ram in, all (more precisely, almost
all) pairs of matrix rows are scanned and, in executing program min s to, all the matrix ele-
ments are processed. It is obvious that program min s to can be replaced by program min-
s t r 0, the program for finding the minimal row of a matrix, if we first transpose this matrix:

minstro aK +, ~n +, yn +, ~n/a, b
655 52 2 (~a)

Ob~=?a
§ 1 a ~ 2a aa /\ y \7 - b 1- 1 + b =? b aa /\ y =? ~ ~ 1
§ 2

Execution of this program turns out to be simpler than that of min s to, particularly in
the case when the computer's operation complement includes the operation '9, that of counting the
number of one-bits in a word. If a matrix contains several minimal rows, the uppermost of them
is selected.

Page 179

DESCRIPTION OF THE LYaPAS LANGUAGE 171

Obtaining the Upper Bound of a Cartesian Product

Operator k a r v e g r a is defined analogously to operator k a r n i g r a, with the difference
being that here we find the upper, rather than the lower, bound of the Cartesian product of two
arrays.

karvegra 0:0, ~1\ + , 11\ + . b1\? / a, d / (~yb)
55 133 5 (~a)

oboe
§ 1 6, b EB b.( 0+ 5(5a
§ 2 6,aEBb~o+l~aO:Yb=9aod
§ 3 6, dEBe 0+ 4bd 1/\ a 0+ 2a 1/\ bd I~ 3

6. cbc =9 bd 6 d --'; 3
§ 4 a =9 be? 6,c --> 2
§ 5 c =9 bs.

Cartesian Multiplication of an Array by a Variable

Operator k ark 0 p e differs from operator k art e z only in that the second of the two
arrays being multiplied together contains only one element, represented by variable 'Y.

karkope 0:0, ~K + . yn, bK / - • a / ~/l / (~y/l)
56 37 2
oab~ =9 bs

§ 1 6, a EB b~ 0> 2~aO:Y =9/la ~ 1
§ 2 .

Cartesian Multiplication of a Variable by an Array

Operator k a r p e k 0 differs from operator k art e z only in that the first of the two ar-
rays being multiplied together contains only one element, represented by variable {3.

Exchange of Information

karpeko 0:0, ~n. y1\ + . /lK / - , a / r~ / (~rb)
57 37 2

oaby =9b&
§ 1 6, a EB by 0+ 2~o:y a =9 ba ~ 1
§ 2.

The following very simple operators can turn out to be useful in the programming of ex-
change of information between arrays.

Operator per e s y I k a transmits (Le., assigns) to array {3 the value of array a.

peresylka 0:1\ + . ~K/ - • a/ (o:~)
60 35 2

oa
§ 16,aEBb,,0+2cxa=9~a-'>1
§ 2 bot =9bp..

If there is no necessity of retaining the previous value of array a, it is possible to limit
oneself to transmitting to array {3 the characteristic of array a (a ex and bex ) by using the expres-
sion

Page 180

172 A. D. ZAKREVSKII

which is so simple that its replacement by a special L-operator is hardly justifiable.

In some situations, one can require the interchange of information between two arrays,
programmed equally simply:

Operator ochistka sets all the elements of array a equal to zero.

ochistka <J,R / - , a
61 26 2

Oa
§ 1 6 a E8 b" ~ 20<J,a -4 1
§ 2 .

LITERATURE CITED

1. H. Bottenbruch, Structure and Use of ALGOL 60 [Russian translation from the English],
Moscow, ILl (1963).

2. Languages for aiding compiler writing. Symbol. Languages Data Process., New York,
London (1962), pp. 184-204.

3. K. E. Iverson, A Programming Language, New York, London (1963).
4. A. D. Zakrevskii, "LYaPAS, a logical language for the representation of synthesis

algorithms," in: Materials of the Scientific Seminar on Theoretical and Applied
Questions of Cybernetics, Kiev (1964).

5. A. D. Zakrevskii, "The LYaPAS compiler," in: Logical Language for the Represen-
tation of Algorithms for the Synthesis of Relay Devices, Nauka, Moscow (1966), pp. 70-74.

Similer Documents