CYBERNETICS AND CONTROL THEORY

V. M. KHRAPCHENKO

ON ONE METHOD OF CONVERTING A MULTI-ROW CODE INTO A SINGLE-ROW CODE

(Presented by Academician A. I. Berg, 12 VII 1962)

In the case when, in order to specify a certain number \(C\), the numbers
\(A_1, A_2, \ldots, A_m\), satisfying the equality

\[ C=\sum_{j=1}^{m} A_j, \tag{1} \]

are used, the set of summands \(A_1, A_2, \ldots, A_m\) is called an \(m\)-row code of the number \(C\).

In digital computing technology, multi-row codes are used mainly to speed up arithmetic operations. In this connection, as a rule, it is necessary to convert the result of an arithmetic operation into a single-row code. Any of the known methods for carrying out such a conversion is based on successively adding each summand of the \(m\)-row code to the sum of all preceding ones. This note describes a method that makes it possible to convert a multi-row code into a single-row code considerably faster than when using the methods known up to now.

We consider the case in which the summands \(A_j\) \((1 \leqslant j \leqslant m)\) are represented in a positional numeral system with constant weight

\[ A_j=\sum_{i=1}^{n} a_{ji} r^{-i}. \tag{2} \]

Here \(n\) is the number of digits of \(A_j\); \(r\) is the base (an integer) of the numeral system used, with \(r \geqslant 2\); \(a_{ji}\) is one of the numbers \(0, 1, \ldots, r-1\).

Substituting (2) into (1) and changing the order of summation, we obtain

\[ C=\sum_{i=1}^{n} r^{-i} \sum_{j=1}^{m} a_{ji}. \tag{3} \]

Let the minimum number of digits necessary for representing the digit-wise sum \(\sum_{j=1}^{m} a_{ji}\) in the numeral system with base \(r\) be denoted by \(m'\). Owing to the integrality of this sum, from the expression

\[ \sum_{j=1}^{m} a_{ji} \leqslant m(r-1) \tag{4} \]

it follows that \(m'\) is the smallest integer satisfying the inequality

\[ m(r-1) \leqslant r^{m'} - 1. \tag{5} \]

Solving it, we obtain:

\[ m' = ] \log_r (m(r-1)+1)[ \tag{6} \]

(the quantity \(]d[\) is equal to the smallest integer not less than \(d\)). The digit sum \(\sum_{j=1}^{m} a_{ji}\) can be represented in the number system with base \(r\) in the form

\[ \sum_{j=1}^{m} a_{ji}=\sum_{j'=1}^{m'} b_{j'i} r^{j'-1}, \tag{7} \]

where \(b_{j'i}\) takes one of the values \(0, 1, \ldots, r-1\).

Substituting (7) into (3) and setting \(i=i'-(m'-j')\), we obtain

\[ C=\sum_{j'=1}^{m'} A'_{j'}, \tag{8} \]

where

\[ A'_{j'}=r^{m'-1}\sum_{i'=1}^{n+m'-1} a'_{j'i'} r^{-i'}, \]

\[ a'_{j'i'}= \begin{cases} b_{j'(i'-(m'-j'))}, & \text{for } 1\le i'-(m'-j')\le n,\\ 0, & \text{in all other cases.} \end{cases} \]

Expression (8) is a representation of the number \(C\) in an \(m'\)-row code. At the next step the \(m'\)-row code of the number \(C\) can be transformed into a code with the number of summands equal to \(m'' = ]\log_r(m'(r-1)+1)[\), and so on. After each transformation step the number of rows in the code will decrease until the next \(\widetilde m\) is no longer a solution of the inequality

\[ \widetilde m \le ]\log_r(\widetilde m(r-1)+1)[. \tag{9} \]

It can be shown that no integer \(\widetilde m\ge 3\) is a solution of inequality (9). At the same time \(\widetilde m_1=1\) and \(\widetilde m_2=2\) satisfy the equality

\[ \widetilde m = ]\log_r(\widetilde m(r-1)+1)[. \tag{10} \]

Thus the number of rows in the code will decrease until it becomes equal to two. The number of steps \(s\) required to transform an \(m\)-row code into a two-row code can be computed on the basis of expression (5). The data obtained are given in Table 1.

Table 1

The block diagram of the device implementing the described method is given in Fig. 1.

To each \(k\)-th step of transforming an \(m\)-row code into a two-row code there corresponds a group of blocks which performs this step and constitutes the \(k\)-th tier of the device. The transformation of the two-row code into a single-row code is carried out by a parallel \((n+m')\)-digit adder, which is the \((s+1)\)-st tier of the device. The first tier contains \(n\) blocks, each of which performs the transformation

\[ \sum_{j=1}^{m} a_{ji}\to \sum_{j'=1}^{m'} b_{j'i} r^{j'-1}. \]

Analogous transformations are performed by the blocks of the remaining tiers.

The functional dependences \(b_{i'i}\) \((1 \leq i' \leq m')\) on \(a_{ji}\) \((1 \leq j \leq m)\) are determined by the chosen radix of the number system. In the most common case, when \(r = 2\), these dependences have the form

\[ b_{i'i}=\bigvee_{c_{j'}=1} S_l(a_{1i}, \ldots, a_{ji}, \ldots, a_{mi}). \tag{11} \]

Here \(S_l(a_{1i}, \ldots, a_{ji}, \ldots, a_{mi})\) denotes the elementary symmetric function of Boolean algebra, equal to 1 if and only if exactly \(l\)

Fig. 1

of its arguments are equal to 1; \(0 \leq l \leq m\); \(c_{j'}\) is the \(j'\)-th digit in the binary notation of the number \(l\):

\[ l=\sum_{j'=1}^{m'} c_{j'}2^{j'-1}. \tag{12} \]

Considerably greater freedom in choosing an optimal circuit for the device is possible with a modification of the method described, which consists in the following. Let \(m_k\) be the number of rows in the code obtained after carrying out the \(k\)-th step of the transformation (here we take \(m_0=m\)). In accordance with the representation of the number \(m_k\) in the form

\[ m_k=p_k u_k+v_k, \tag{13} \]

where \(0 \leq v_k < u_k\), the summands of the \(m_k\)-row code are divided into groups of \(u_k\) summands in each group, except for one group, which may contain a smaller number of summands. Then the \(u^k\)-row code of each group is transformed into a code with the number of summands equal to \(u'_k=\rceil \log_r (u_k(r-1)+1)\lceil\), while the \(v_k\)-row code of the additional group (if such a group exists) is transformed into a code with the number of summands equal to \(v'_k=\rceil \log_r (v_k(r-1)+1)\lceil\). As a result of carrying out the \((k+1)\)-st transformation step, the number of rows in the code is reduced to the value

\[ m_{k+1}=p_k u'_k+v'_k. \tag{14} \]

This operation is repeated until a two-row code is obtained. The latter is transformed into a one-row code by a parallel \((n+m')\)-digit adder.

Let us consider the case where \(u_0=\ldots=u_k=\ldots=u\) (respectively, \(u'_0=\ldots=u'_k=\ldots=u'\)). Using expressions (13) and (14), we estimate from above the number of steps \(s\) necessary for transforming an \(m\)-row code

into a two-row one:

\[ s < \log_{u'} \left( \frac{m}{u+1} \right) + D, \tag{15} \]

where \(D\) is a certain constant depending on the chosen \(r\) and \(u\). Note that \(D\) does not exceed 6 if \(u \leqslant 2^{127} - 1\).

It also follows from expressions (13) and (14) that

\[ \sum_{k=0}^{s-1} p_k \leqslant \frac{m-2}{u-u'} . \tag{16} \]

Thus, in the given variant, for one digit of the device no more than \(\dfrac{m-2}{u-u'}\) blocks are required that implement a \(u'\)-digit sum of \(u\) single-digit addends, no more than \(s\) less complex blocks, and one single-digit adder.

The proposed method of converting a multi-row code can be used to speed up multiplication. In the case of using a parallel adder based on one of the methods of accelerated addition \({}^{1}\), the described variant with \(m=n=30\text{--}60\) (as is usual in computing machines) and \(r=2,\ u=3\) makes it possible to increase the speed of performing multiplication by a factor of 3–4 in comparison with the known second-order method of accelerating multiplication, and does not require additional equipment for its implementation.

Institute of Electronic Control Machines
Academy of Sciences of the USSR

Received
12 VII 1962

REFERENCES

\({}^{1}\) O. L. MacSorley, Proc. IRE, 49, No. 1, 67 (1961).