##### 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.

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.