(SANITIZED)UNCLASSIFIED SOVIET BLOC PAPERS ON INFORMATION PROCESSING, 1959(SANITIZED)

• Document Type: CREST
• Collection: General CIA Records
• Document Number (FOIA) /ESDN (CREST): CIA-RDP81-01043R003600240020-0
• Release Decision: RIPPUB
• Original Classification: C
• Document Page Count: 123
• Document Creation Date: December 23, 2016
• Document Release Date: March 11, 2014
• Sequence Number: 20
• Publication Date: August 4, 1959
• Content Type: REPORT

Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
R
50X1 -HUM
Next 73 Page(s) In Document Denied
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
METHODS OF LOGICAL, RECURSIVE AND
0?ERATOR AN LYSIS AND SYNTHESIS OF AUTOMATA
BY
TU.!. BASILEYSIY Yu.A. SHREIDER .I.T.AKUSESKY,
Imstitute tor Scientific Research of
Electronic lathematical Nacbines
Moscow ? USSR.
STAT
Declassified in Part - Sanitized Copy Approved for Release 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
An automat may be regarded as an operating simulator of a
system interacting with the environment and, consequently, as
a simulator of a discrete control process. The study and solu-
tion of the problem of simulating a real system is a complex
process, which involves: the selection of essential character-
istics of the system and its interaction with the environment;
the approximate description of the system by means of the
totality of characteristic features, either algorithm, or
structure; the analysis of the obtained information and its
transformation into an optimum system of logical functions;
the synthesis of a real automat using a certain system of
physical components, executing logical functions.
Another alternate approach of the problem is the simula-
tion of a real system (or control process) in the form of a
process in an automat with a preset structure, endowed with
many degrees of freedom.
In this case, it is desirable that the analysis of the
system data be reduced to a certain optimum algorithm and
dismember it into independent blocks executed in the automat
by means of logical circuits or a program.
The development of digital computer logics and the employ-
ment of the machine for handling the information belong to
problems of this kind.
The solution of the problem of analysis and synthesis cf
automata may be performed on the basis of different formal
descriptions.
The present paper deals with three alternate approaches
to this problem: the calculation of logical functions of
time, the analytical medium for the presentation of recursive
functions and the operator representation of the process in
the automat.
Para.l. AUTOMATA AND ',MCA", FUNCTIONS OF TIME
As an analytical medium for the presentation and analysis
of logical features we use the calculus of logical time
functions (1), pressupposing that the processes of data con-
version occur discretly in time while their description is
related to the current moment, the origin.
From here takes its source the method of the process
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11 : CIA-RDP81-n1nannqRrin0 A nnnn n
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
-2-
prehistory description expressed in terms of time delays. To
The zero operations on'two-Talved variables is added the
operation of time shift ( D ) and relation of logical in-
equality (?rt5y, ).
In relation to any formula, built-up of two-valued vari-
ables by means of introduced operations, the time shift
responds to the distribution law.
Over words of equal length, composed of two-valued vElri.-
ables are i,ntroduced interdigit operations of negation ( x )
crossover ( )cn.9 ) conjunction XUY ) and time shift
( Lig X ). Besides, the operation is used for cycle shift of
the word oyer a preset number of digits to the left, or to
the right ( aKX ) and of the relation of logical inequality
( XIX0
which is impossible.
For the multiplication operation may be used the method
of "carry remembering", first proposed by U. Nadler (Czech-
oslovakia), which involves a special HMO! This method
takes advantage of a specific feature of the multiplication
operation consisting in the fact that, nt this operation all
intermediate actions, preparing the result, are executed by
the circuit without "conditional" transfers. Owing to this,
it is possible to considerably reduce the tine of the multi-
plication operation by introducing a special addition RED
with incompleted carry. The carries occurring at addition
during this ENO are memorized in a special register.
The memorized carries are taken in account at every
now addition and cleared at the end of the operation. i
considerable acceleration of the multiplication operation
may 'also be obtained, if the memorizing of the carries is
effected not in every digit, but in several equally distanced
points of the adder.
Let us now consider the algorithms of accelerated
division. Usually, the quotient digit is defined by the
feature of the direct or reverse (additional) code of the
remainder. However, the remainder code, besides the afore-
mentioned information, contains some additional data, which
frecluently allows to determine at once the group of ouotient
digits and, thus, reduce the number of elementary machine
operations. The idea of this method is that when a remainder
is formed with a sufficiently small or sufficiently big:
absolute value, the following digits of the quotient shall
be obligatorily a group of identical digits (zeros or units).
Let us assume that the divisor 3 is normalized, i.e.
contains "1" in the highest digit. Obviously, if the code of
the positive remainder contains in its highest digits a
number of zeros, then, besides "1", in the quotient digits
are to be recorded also X - 1 zeros. For obtaining the next
remainder, it is sufficient to simply shift the initial
remainder ,to the left over "K" digits and subtract the divisor
from the obtained number.
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2
1 . C
3R00360n24nn2n n
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
-7-
The case with the negative remainder #4? of a sufficient-
ly small absolute value is setrical to the just considered.
Assume, that in the higher digits of the remainder code there
are units. Demonstrate, hat K-1 following remainders
will be positive and, consequently, besides NW' in the next
quotient digits should be recorded K-1 units.
AtA
14idently, the L remainder of Ai, is equal to 411:=ZR041
provided all previous remainders were positive.
From the study of the A. code, and taking into account
the normalization of the divisor 7 , it may be concluded,
thatwhen1,6*.iallremainders.are positive, i.e., as
required. AIL
The last Al remainder may be obtained by shifting the
A code over I digits to the left and adding the number
thus obtained to the divisor Ir. e
Let now Xlo be a positive remainder approaching closely
enough to q. (such cases are more rarely encountered). This
fact may be found out in the machine by means of a simple
circuit analyzing the higher digits of divisor and re-
mainder.
In this case it is necessary to build up the quantity
/go = no ^ 4 and record in the quotient the K units
contained ih the higher digits of this quantity. The next
remainder is obtained by shifting the 40 code to the left
over I digits and adding the divisor$
The case when a negative remainder tio of a big
absolute value is obtained, is symmetrical to the case just
considered.
The average number of II luetient digits, obtained in
ODB addition or subtractio4 31 (taking into account only
small values of remainders) is determined for the case of
numbers with many digits in the following ways
Do
K-1 2
M + 1-
41 K=3 .2K 2. ?
It may be demonstrated, that the indicated division
algorithm (taking into account only small remainders) is the
most effective cycle algorithm, which realizes the method
digit by digit, on condition that besides the divider register
is used only one adding register and only classic EMO.
Declassified in Part - Sanitized Copy Approved for Release 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
-8-
.07
Let us assume that in the t. cycle in the adder is
obtained a certain quantity AM./140= ti defining the
following group of digits of the quotient BM ). (A and
B are designations of certain algorithms). It may be easily
ascertained that all the tL are nothing else but remainders
anAlt. consequently, B(21.) is the maximum determinable group
of the quotient digits. However, minding that of the divisor
is only known that it is normalized, the method for
obtaining the digit group described before, exhausts all the
possibilities; as was necessary to demonstrate.
The machine algorithm of the division operation with
simultaneous shift of the divisor is usually not employed
for the reason that it either results in a loss of division
signs and less accuracy in division, or requires a divisor
register and adder of double length.
However, by using a ring shift of the divisor it is
possible to eliminate the effect of shifts on the duration
of the division operation without increasing the equipment
and without any loss in accuracy.
This method presupposes the utilization of reverse
codes and the presence of a circuit of cycle carry in the
adder. Apparently, the shift of the remainder code on the
adder may be practically not made, considering that the place
of the point is "moved" over 1 digit to the right.
Correspondingly, on the adder is to be transferred the
divisor with a ring shift to the right. At every such trans-
fer, the position of the point and, correspondingly the
position of the sign digit are "shifted" in the adder over I
digit to the right. The further actions are obvious.
As an example of the execution of the division operation
with the utilization of special END, may be cited the method
of IL Nadler, realized by means of the addition ENO with
an incoapleted carry. However, in some cases, it is even
possible that the sign of the remainder, i.e., of the quot-
ient digit will be determined incorrectly. If it is assumed
that in each digit of the quotient there is also "-I", then,
using this method, any error in any one of the digits may be
dorrected at the expense of the following digits.
The operation is completed by reducing the obtained
quotient.to the ordinary form by subtracting two codes,
corresponding to the positive and negative units in the
quotient digits.
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
-9-
Speeding-up of operations may be achieved in many cases
by elizinating normalization and presenting the numbers in
net normalized condition. Thus, without considerable loss
in acciracy, it is possible at multiplication to have only
one of the multipliers normalized, and, moreover, its normal-
ization may be partially overlapped in time with niemory
access of the other multiplier. If the result of addition
is to participate in the subsequent addition, its normaliza-
tion to the left is also not obligatory.
A certain speeding-up may be achieved by the representa-
tion of negative numbers in the machine in the reverse code,
on condition that besides the sign is introduced the code
feature. In this case, at algebraic addition, no time is
vested in the adder for the conversion - it coincides with
the transfer of the code into the adder (at multiplication -
into the multiplicand or multiplier register). It is
expedient to introduce the code feature for digits as well.
It seems expedient to increase in the machine the number
of active computing devices, capable of conducting computing
operations in parallel and separately from each other, and
capable to ensure a wide direct exchange of information by
interaction. The presence of several active computing
devices permits to obtain a more effective execution of
comflexes of operations, as well as separate arithmetic opera-
tiona. Let us consider the possible procedures for the
realization of certain operations in conditions of an
increased number of components of the arithmetic device.
Assume that
- is the condition of the device (adder-S
t. ?
L register "-f?) at the rt. -cycle of the L. -stage
of the process.
1-10
LTI -shifts, to the left and to the right
respectively, over P
A. Calculation of LA. ag" with multiplicPtion in
a descending order of degrees 210
If
Eile+
4v)
(1)
norinccifia,r1 in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Mons ir+s 'Q. 84-'81-K4
ReL u
Take
oc.)
part St ) Se')
20
I)
)
I)
{Stith-K-1z {5/
2){S fas
t_t r-h-K-I e ""K"I
3) 1St }h.,c_iz [Se
-10-
1..Se h tSgLih-tc-1.
)1. )(--1
=
1.5
315 3. itipt-K-1 [54L1-K-/
B) Calculation of 1.1=a6)" with multiplication in an ascending
order of degrees 2x0
Let us designate: E. J21+
2 'ti` E1t1()"1?
Then:
30 = 0
I) { 54 IT-II
;
-Li
1;447- EK4-1e IC? E ocHev(ir")
LJ
P ) Es, =.1
I) [5.{sci 15GLI;=i5GLIJ_I+
2) isei; = LS{ Li-, f5e.V+ tizejj.
The schemes A and 13 require at each stage the knowledge of
only one figure " ". Therefore they may be adapted for any
process in which " " is determined digit by digit (for
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
-11-
95
example a c , then
The schemes considered above may be realized in decimal
code arithmetic devices, provided modifications, are
brcught in the schemer for the reason that doubling max be
effected in the decimal code adder. Thus, multiplication
of "oft " by " " in the descending order of degrees of 2x
is based on the presentation
a [a a.E,21- Qch_Mii- 4..1_ a ec,
and is realized in the machine arithmetic device from Spend
IL by the operationLSPJ ispjj..1? E./[Raj
ana LSP.1);21.5pJ'''.4 ispth-Lsp.i; and in the ascending
order in the machine arithmetic device from Sp and Sa.by the
operation
p - tspii-i+ Ei
The direct execution of this multiplication requires the
determination of binary digits. In this case it is advisable
to use the well known decomposition of a proper decimal
fraction into a binary fraction by the overflow of the adder
S at the operation S, obtainingbinexy digits in the
descending order of the degrees 2x. -Minding the greater
efficiency of multiplication in the ascending order, it is
expedient to use the number 6' dual in relation to "6 "
i.e.
EQ -1- En
At division, bimry digits of the quotient were obtained as
a result of a corresponding trial and error procedure and
proceeding to the multiplication with these nu i
mbers, t in
possible to form a quotient decimal code in the adder ..5(1,.
linstead of R1, ).
In the sane manner may be modified the afore described
schemes for execution in the decimal arithmetic devices.
Para.. METBODS FOR REDUCING TBE TIME OF ELEIESTARY
WHINE OPERATIONS
An iiportant condition for the accelerated execution of
the addition BUD is that each component of the add circuit
is of single-shot type.
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Usually in add circuits with single-shot operation
comloonents, for the addition procedure are used -memory
registers of both addends.
Is a result it is possible to eliminate on of the
memory operations, connected with the number transfer, as
practiced in computing impulse adders. When it is not
desirable to utilize in the add circuit the memory register
of the 2-d number, the single-shot operation may be achieved
by means of a scheme in which the code, of the number stored
in the adder, is defingd in each digit by the position of
two memory components (the combinations '00" and "11" corres-
pond to the code "0", while the combinations "10" and "01"
correspond to the code "1").
The functions from the digit and from the carry in
this circuit are divided between different memory components.
No simple mechanical solution has yet been found for
reducing the time of the carries.
Adding devices in which the average time of the add-
ition ENO is reduced by strictly noting the moment when
the carry is completed, or by introducing "by-pass circuits"
in the through carry circuit, are, for the time being, of
extremely complicated design.
The problem of group shift acceleration may be solved
by means of a special shifter.
The shifter (see Fig.1) is a ferrite matrix in which
the information is simultaneously recorded on all the ferrites
of the given column, (each matrix column corresponds to a
certain digit of the recorded information).
All the ferrites of each matrix line are transpierced by
a common reading wire. Besides the recording and reading
wires, all ferrites which enter into one matrix digmonal,are
transpierced by common shift wires.
In this manner, when a reading signal is applied to a
bus, the number shifted over a certain number of digits in
the direct or reverse code is read out.
The number of apparatus in this shifter is not greater
than in usual shifting registers, but its functional diagram
is more simple.
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
?
-13-
Para.ii. CIRCUIT EXECUTION nuauras FOR COMPUTING
ELEMZIEARY FUNCTIONS
The calculation of elementary functions should be includ-
ed in the list of main machine operations adaptable for cir-
cuirt execution may be considered the algorithms for the
calculation of function values, developed from the "digit by
digit" algorithms in the following directions.
Direct Scheme. a) Specially selected trial and error codes
are periocifcally generated by transmitters;
b) The result of the trial and error procedure defines
the rethod of formation of quantities by the arithmetic
device. These quantities are consecutive approximations to
the value It(x).
Reverse Scheme. The trial and error codes are consecutively
/alma by the -machine arithmetic device;
b) The value 14r) is formed on the basis of the trial
and error results from specially selected codes 'which are
periodically generated by the code transmitter.
IS elementary machine operations for circuit execution of
the calculation of the values ((xi may be adopted:
a) Addition at: -tei 6'
b) addition with shift
? 6i? it- 21'
The lapt elementary machine operation may be frequently used
at
II) at ? a1 22 = et. 229
Elementary machine operation
6" - multiplic,ation by the numbers (p-Get. 2;.) Gre. (if
depending on the results of the trial and. error procedure.
It should be noted that any number my be represented
with an accuracy up to 27, in the .interval (2)-2= //7/44 2-//
in the interval ( f)- 2.= 107 2-')
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
-14-
Let 1.113 consider the execution of certain elementary
functions on the basis of elementary me.chine operations 0,63,11
For the function e?92: we start from the present-
ation
(t)z-
y= e = (It 2(1-t6z2)... ccp 2-P) (1)
The trial and error codes have the following form:
= ea (i-t 2 4) P)
Using the recurrent relation
= 2f64;#1 2-(1").Y.1
(2)
Yo
we obtain the circuit of a device comprising an adder,
binary code registers and a shifter (see Fig.3).
Depending upon the results of the consecutive trial
and error, we calculate yi.., by the addition of Y./. to
1-.1 shifted over yj digit to the right. At Ye, C we
oibtain the values dif functi,Ce("x
By means of the reverse scheme, we can calculate the
function
Using the eriodically generated numbers (2) and the
recurrent relation
x./ 4 = x ? t 6,/ 2"(1.").T
we may determine dj?
6i4-1
where..t?-i#1
Depending upon the defined ej#1 it is determined
whether the addend aiff participates or not in the
formation of the quantity enz ?
For calculating the values of the functions =t
it is expedient to adopt the following presentatidn
c?fy#,)
e? x, # ? . .
ALL_
4jil
8
xi= au.
Declassified in Part - Sanitized Copy Approved for Release 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
-15-
In th, for the values Ai,/ and. B the following
recur. lat ions valuable take place:
411 2-"") Bi
j=t2,???,,a) (3)
= o;
(with hj7, 8i5 ye obtain .11p .17t.813zx
Bp LI-1144x
Tha values X are trial and error codes, on the basis
of which are determined this 6iff
ej#1 17: 59/7 (x- --rj.,)
Next, by adoling the shift (at 6j#, ) are calculated .fip-i
and Sift tor at ej.,=0, B.itt =ni = 8j)
and so on up to j.p . For dete,rnining x it is
rocessary to sake the division .
op
For calculating the values of hyperbolic functions say
be applied a procedure similar to that described for the
exponential function.
The calculation of the values of the function y=aze02-
is made by solving the equation
The trial and error procedure is effected for determining _
by the sign of the value 6../ where Sp., .-vgi,f-Bff,
The values 11%,11,.. and 8,./ are determined by (3)
ath hpf and. Bit/ from relations similar to (5).
it:if rig;
=
2"ii
.4=o -12
For carrying out calculations in decisal arithmetic devices,
the before nantioned algorithm, mist be so modified that any
shift to the ri:4,t is excluded.
For the function
is replaced by
re
?
,71?1
- p(
the recurrent relation (2)
(2)
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
?
eml6-
where = e
For calculating the values &7 it is necessary to
use the recurrent relation similar to (2') i.e.
Then
tf
10'2-FP'
17 -21"
J#1 ./
For detection of eji, it is necessary to calculate
$yn =Syn. (2 2 x-
nen calculating the values of the functian
relations (3) are replaced by
17141 " 21" j9.1.1-6)#, 131.
,81?
R 0= 0
OX the
(3T)
? ?IP)
Para.& SPEEDING-UP OPERATIONS AT MICROPROGRAM
CORTROL
The use of microprogram control in digital computers,
presents many positive features and also speeds-up machine
operation.
his is achieved by introducing in the external
alphabet of the machine several symbols of accelerated
algorithms, included in the executed program as a character-
istic elementary link.
For other terms, this is achieved by forming new
computing operations which are characteristic for the execu
ted program and allows to make the most efficient use of thy
equipment. Such methods of speeding-up calculations are
intermediate between the methods considered before and met l .8
related with the concrete pecularities of the program.
Thus, the gain in time, in this case, is the difference
between the tire needed for executing the calculations accord
ing to standard programs composed of external alphabet
Declassified in Part - Sanitized Copy Approved for Release 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
-17-
operations for a usual machines and the time for executing
the microprograms in the machine with microcontrol. This
difference is mainly caused by the following:
1. Micronrograms do not include such operations as
control transfer and memory of certain command addresses
for matching the main program with subprograms.
2. It is not necessary for many algorithms to bring
intermediate results to a standard form, for example,
rounding off and normalization may be omitted.
3. It is possible to match in time different operations,
as for examle simultaneously with the addition performed
in the arit I etic device adder it is sometimes possible to
read out from the memory the digits for the following
actions.
4. In some cases the specific features of the algorithm
may be used to advantage.
As known, the reverse value , may be computed by
the iterative formula
Yi X Yd
Let us replace )( by 2 :
YL-H2I (1.- rqz)
In this fora the formula becomes convenient in that all
the numbers participating in the calculation according to
this formula are not more than a unit, provided a limited
interval 9f )C modification is used and the initial
approximation yo has been appropriately chosen. (The
multiplication by 2 may be performed by a shift or addition
of the number with itself). This allows to make the
calculations with a fixed point. Moreover, no time has to
be spent on the subtraction, as represents an
additional code Zyt , which at all iterations may be
replaced by a reverse code without loss in precision.
It is known that at calculations according to the
indicated iteration formula the number of true signs 9.
is doubled.with each iteration. Thus, in Sl may be left
11.4'1`4.4 of higher digits and all others may be
discarded. This aay be used to advantage for reducing the
time spent on multiplication by employing sre as multi-
pliers. The average number of in multiplications
In this case will be equal to The initial approximation
yo nay be computed by the formulae of the type:
YL,
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
9.= cxx+e
90= 0L+ (43?x)2
where a and 8 are constants. In this case the time
of multiplication may also be reduced at the account of the
small number of digits. It may be considered that as far-
m speed is concerned, the method just ccosidered may compete
with different methods of division digit by digit, including
the accelerated methode, as well, At present, when single-
sided high-speed memories of large capacity on paper lists,
have appeared, it has become possible, by increasing the
number of constants, to pass from one approximation polyno-
mial for the elementary function to a series of such
polynomials at separate intervals.
It UB assume that the function value is to be determined
at the interval 0.6X4i ? We divide this interval in two
equal ones by their length, and, in each of them, make an 4?
approximation of the function by the polynomial in the X.'
degTee. For each X the groupjN4 of constants will be
determined according to the Ir. of the highest digits of the
number ? The lowest 11-.4 digits represent the difference
between )( and the nearest lowest table value of the
argument. The approximating polynomials are calculated by
the Horner diagram with 4t multiplications
(Gcr. AX i-CX49),ax +q
Obviously, in the polynomials, represented in this way, the
coefficients G4 ,erj, as may be expresse4.without an
exact number of 'digits. As the values X 4IX )' after
the point have not less than zeros, i.e., the number
of significant digits which they contain is not more than
consequently, the coefficients aj. may have not more
thann-qi significant digits. The advantage of this method
of polynomial representation appears at multiplication,
owing to the fact that these values may be taken with an
uncomplete number of significant digits.
It may be easily seen that the first multiplier contain
on the average401-$q) units the, second-gft-cOs-03
units and the last 4.01-q9 units. Thanks to this, the
calculation of the polynomial is considerably accelerated.
The analysisAf the methods for calculating the element-
ary functions 11-.0%ex, enX,S6IX,igX.AttsinX, etteipX
shows that provided slight nodifications and additions are
brought in the usual arithmetic device it may be used for
the execution of these methods. Thus, for computing a
it is necessary to provide an output in the control device of
Declassified in Part - Sanitized Copy Approved for Release 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
-19-
the last digit of the order, and the possibility of high-speed
recording and adding constants in the order adder.
Under these conditions, the speed of calculation of
elementary functions in the arithmetic device controlled by
a microprogram of an appropriate arrangement is increased by
several times.
Thus, the control by microprogram ensures the possibility
of making efficient use of all executive organs contained in
the machine.
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11.: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
?????
?20?
REFERENCES
I. R.K. Rychards. Arithmetic operations of digital computers.
Foreign literature publishing house, I9c".
2. V.S. Linsky. Computing elementary functions on digital
computers. Computing mathematics. Issue 2.
The Publishing of the Academy of Sciences,
1958.
3. G.D. Monakhov and E.I. Klyamko.
Method of Spoiling binary division in 3,
computers. Priborostroenje N 2, 1957.
4. I.Y. Akushsky. Many?registered schemes for executing
arithmetical operations. The theory o!
mathenatical machines. Collection I,
Moscow 1958.
Declassified in Part - Sanitized Copy Approved for Release @
014/03/11 ? CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release . 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release . 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
faae
and ettoz
biLna-tya(frieozde
CP7
.5hif t ez
tfc V)
ctez. ?
(cv)
Regtsi?ex 1 I Reg 51
/IV/ y0 .1
et .
60.r) -re .r
te2
7
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
STAT
MACHINE TRANSLATION METHODS AND THEIR APPLICATION
TO ANGLO-RUSSIAN SCHEME
Belskaya,
Academy of Sciences of the USSR
In this paper an account is given
of a scientific research which
haa resulted in devising an algo-
rithmic procedure for machine
translation of different langu
ages into Russian /I/.
Methods evolved for translational
purposes are explained, the Anglo-
Russian scheme being chosen as an
Illustration of their application.
I. INTRODUCTION
Rssemrch in MT methods, which are outlihed below,was started
late in 1954 on the initiative of Academician A.S. Nesmejanov, Pre-
sident of the USSR Academy of Sciences. The first experiments in MT
from English into Russian were carried out in December, 1955 /1,2/,
which terminated the first stage of the research.
Some of the principles on which our research is based were put
forward in earlier publications, among which a paper published in
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
RESEARCH, October 1957 /3/, can also be mentioned.
Since then considerable progress has been made towards adequa-
te formulation of the method. We are now in the position to says
that the second stage of the research has recently been completed ,
in the course of which the suggested methods were shown to be of
general applicability, for which purpose these methods were ex -
tended to cover UT from languages differing from English in struc-
ture as much as Japanese, Russian, Chinese and German /4/.
As to the Anglo-Russian scheme of UT the research here has
reached a stage where complete grammatical analysis at a bilingual
level aa well as rearrangement of most important types of English
idiomatic constructions can be accomplished, grammatical modifica-
tion of the Russian translation (which indeed is the simpler part
of the problem) being performed by an independent set of routines,
termed Russian Synthesis.
In addition to this, the progress in Anglo-Russian UT has ta-
ken the form of considerable growth of the volume of words now en-
tered into the MT dictionary. Lore than 2000 words are stored in
the English section of our multilingual LT dictionary, a still grea-
ter number of Russian equivalents being stored in its Russian see-
tion. The dictionary thus is made to cover different fields of ap -
plied mathematics1/.
To complete this stage of research a large-scale test of the
Anglo-Russian sheme has been carried out. 100 samples (which
1/
?
Participants in this work were G.A. Tarasolova, whose contribu-
tion to the compilation of the Anglo-Russian Dictionary is most
valuable, and L.U. Bykova.
2
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11: ClA-RDP81-0104pCwv
.
n9Annon
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
amounted Co 3000 sentences) of 'unknown text' were selected at ran-
dom from different English authors, and translated into Russian in
strict accordance with instructions provided by the UT dictionary
sad translational routines1/ The ten persons chosen to carry out
the experiment had no knowledge of English nor had they any pre-
vious experience with the tasks required2/.
It emerged from the text that the scheme is very effective at
dealing with all sorts of texts restricted, lexically, to applied
mathematics, whereas grammatically no limitation as to type of the
written text has been found necessary. 1 or 2 words per printed pa-
ge is the average for 'unknown' words with the present size dictio-
nary, which makes the translation quite adequate for understanding
/See Tables Nee 1,2,3,4/.
For this reason as well as for reasons of preserving the pro-
posed menes of UT dictionaries strictly specialized as to field,
we are not inclined to increase the volume of words in the present
dictionary, but rather proceed with compiling medlum size (say,
2600-3000 words each) dictionaries for various fields. This indeed
will be our occupation at the next stage of research.
Translational routines for Anglo-Russian MT being final achie-
vement of the recent research, it seems very reasonable, in the
present communication, to lay particular stress on discription of
translational routines for vocabulary and grammatical analysis of
the English sentence. As to the principles on which UT vocabulary
1/ A.I.Martynova was engaged as superviser in the testing procedure
2/
Several samples translated in this manner are given in Tables
Nos. 1,2,3 and 4.
3
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
is based, the reader is referr? to our earlier publications /3/.
2. GENERAL CONSIDERATIONS. APPLICABILITY OF IA METHODS.
Of two most general MT problems - those of possibility of ma-
chine translation and of its applicability - the former has alrea-
dy been resolved, both theoretically and practically, whereas the
latter problem still remains open for discussion. The objective of
the present research is to prove applicability of MT methods to
any sphere of language.
To date, it is only within the limited sphere of scientific
writing that the applicability of MT methods has won general re-
cognition. As to other uses of MT, most machine translators are
Inclined to feel very doubtful /4/.
Howeverlthe n:ajority of restrictions imposed on MT applica-
tion, when analyzei, turn out to be due to a very strong incline -
tion on the part of investigators to describe the translated lan-
guage /Bourse language/ in tams of correspondence to some other
system, say, another language, or a group of languages, or science
other than linguistics, especially logics or particular fields in
mathematics. The possibilities of MT are discussed then as depen -
dent on common elements in the compared systems. These elements
may be more or less numerous, yet absence of complete correspon -
donee between the systems, which is usually the case, inevitably
brings about limitations to the scope of MT. Thus, application of
machines to translating literary works of art has more than once
been declared as absolutely rulea out (See, for instance, Ref.4.
p.42).
In our opinion, it seems very reasonable to expect that these
4
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11 : CIA-RDP81-n1nannqRrin0 A nnnn n
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
limitations can easily be eliminated, should the problem be forwu
lated in a different way, namely, 'whether it is possible, within
any language existing, to give formal description to any of its
multiple spheres, individual as they may seem?'
This comes to the same thing as saying that the applicability
of MT depends on whether it is possible to identify the implicit
set of rules governing this or that particular sphere of language
applications, be it as narrow a sphere as, say, Wordsworth's poet-
ry, and, further, whether these rulef. can be formulated into a for-
mal set.
Apparently, every piece of writing (insofar as written langua-
ge it discussed) can be analyzed on these lines within the sphere
where it belongs, and a set of rules for such anraysis can be laid
out. It is essential that these rules should be formal all alonif,
the line. Yet this is no obstacle either, since language is but a
formal system of specific character developed by man to give commu-
nicative experession to his mental activities. As a consequence of
the foregoing, it is immediately obvious, that problems posed by
stylistic peculiarities of literary works of art can satisfactorily
by resolved, if treated on tne lines suggested above, i.e. within
the sphere where they belong.
In this light, the supposed 'principal informalizability' of
poetry (See Ref.4) should be rejected. Contrary to this supposition,
poetry, as indeed any piece of literary art where formal elements
are of no minor importance, is particularly susceptible to machine
translation, in this sense.
This assumption has partly been justified on empirical grounds,
5
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
that ia, by experimental translation of passages from Ch.Dickens14
J. Galaworthy, J. Aldridge and Edgar A. Poe. /See Tables Nos 2, 3
and 4/. It is our firm belief, that furter investigations
will completely eliminate the restrictionsimposed now on MT appli-
cation.
An adequate description of a language, as indevof any parti-
cular sphere of it, should finally aim at establishing wiflhin the
analyzed system a set of correlations of the following type-
means effect
, by which the correlation of linguistic means
and their meaning (effect) is inderstood.
Taken in its most general sense, the translational problem is,
in effect, the problem of equating the aforesaid correlations of
one language with those of another.
The procedure can symbolically be expressed by the following
chart (See Fig.I.)
means1 --.:----t-effect1
11
effect ?lb-means2
Fig.'.
where 'effecti, and 'effect2' are identical whereas means1' and
Imeans2' differ.
in the course of this substitution of one language for another,
transposition of semantic content from one language to another is
realized.
In conclusion, a final word must be added on the problem of
MT prerequisites. These do not rest upon the existence of common
basic elements in languages, as is often pointed out, but rather
include the following two factors:
10/ Illustration to be found in Reference /3/.
6
Declassified in Part - Sanitized Copy Approved for Release @ 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
I. language in itself is but a system of formal means by which
communication of meaning is effected;
2. all language systems existing are so developed as to express in
their particular ways any shade of meaning.as well as various
emotional effects.
When falling back on our symbolization, this comes to saying that
the number of 'effects' in any two languages is equal, which makes
the corresponding systems of 'means' fully comparable, through
their 'effects'.
Since language systeihs are formal , any application of them
can be provided with a description programumble on a machine.
3. A SHORT OUTLINE OF TRANSLATIONAL ROUTINES.
General procedure covered by translational routines can be
broken down into three independent steps, these being:
I. Vocabulary Analysis of the source language for which purpose
MT dictionary and a set of dictionary routines are used;
II. Grammatical Analysis of the source language for which purpo-
se Analysis routines are devised,
III. Grammatical Synthesis of the target language for which ends
the same set ofSntl_y_. routines is applied to the
text translated from different source languages.
To make the outline concrete, the translational routines will
further be described in their Arglo-Russian realization 1/
A. Dictionary Analysis.
Dictionary Analysis of the English sentence starts with
1/
Complete list of translation,d routines given in the order of
their application to be found in Table No 8.
7
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
searching every word of the text in MT dictionary. The first
dictionary routine to be used here is that of transforming words
of the text into the standard forms listed in 1.:T dictionary (See
Table No 5).
Thus 'wanted' will be transformed into 'want', 'stopped' in-
to 'stop', 'coming' into 'come', 'lying' into 'lle','copies'into
'copy', 'bigger' into 'big', etc.
When dictionary search is completed, another routine is ap-
plied which concerns itself with the words that for various rea-
sons have not been found in the dictionary. These are termed,
'unknown words', because their lexical equivalents remain unknown
throughout the translational procedure. Yet, for the forthcoming
grammtical Analysis, it is essential that grammatical qualifi -
cation of the 'unknown words' should be obtained.
It is impossible to foresee every word in every text of a
language or even of its particular sphere, since some of them may
be occurring for the first time in the language, not to mention
quite a number of more trivial reasons.
However, the 'unknown words' do not affect the translation,
so far as grammatically they have been classified. To meet the
latter problemla very important routine, that of classifying 'un-
known words' into 'parts of speech' has been devised,where exten-
sive use in made of morphology and syntax of these words.
Another category of sentence constituents which undergo pre-
liminary grammatical analysis in accordance with a dictionary
routine, are the so-called 'formulas', by which various symbols
used in different sciences are understood. Syntactical function
of every 'formula' in the sentence is defined in accordanoe with
8
Declassified in Part - Sanitized Copy Approved for Release
50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
Declassified in Part - Sanitized Copy Approved for Release ? 50-Yr 2014/03/11: CIA-RDP81-01043R003600240020-0
a special routine.
So much for the words and symbols not found in MT dictionary.
In addition to lexical equivalents, words found in the dic -
tionary are provided with information (termed 'invariant characte-
ristics') which is partly grammatical partly semantic in character.
For more detailed discription of this information the reader is
referred to our earlier publication /3/. The only thing that need
be montioned here, is that within the' invariant characteristics'
obtained from the dictionary final and preliminary information is
distinguished. Information is considered final for dictionary cyc-
le when lexical equivalent of the word is included. Ins Lead ,prel .1-
minary information of the word is restricted to the indication 'ho ?
monymous ' or 'polysemantic' .
apecial routines have been devised to deal with homonylimus
and polysemantic words, the analysis of former words preceding
that of the latter.
The four types of 'Homonyms' analyzed by the routine, are
those of ' abjective-noun' (Homonym I) , noun-verb' (Homonym 2)
'verb-adjective' (Homonyn.3) and of preposi ti on-adverb ' (Homonym 4)
Among Homonyms I, a more complicated sub-type is d is tinguished , -
that of 'adjective-noun-verb' (Homonym I Complicated). See fig. 2
Cp. : CHECK: I. adjective - KOHTP0AbHbici
?
2. noun - KOHTP0Ab
3. verb - polysemantie'
SQUARE: I. adjective KBAAPATHbvt:i
2. noun - ' polysemantic' ;
3. verb - 803BeCTI1 B 1