Matrix and pipeline mirror-symmetrical adders
Matrix mirror-symmetrical adder. It is well known that the digital signal processors put forward high demands on the speed of the arithmetical devices. The different special structures (matrix, pipeline, etc) are elaborated for this purpose. Let's show that the ternary mirror-symmetrical arithmetic contains in itself the interesting possibilities for realization of the fast arithmetical processors.
Let's consider the matrix multi-digit ternary mirror-symmetrical adder (Fig. 1).
Each cell of the matrix adder in Fig. 1 is the ternary mirror-symmetrical single-digit full adder having 4 inputs and 2 outputs. The matrix adder in Fig. 1 consists of the 21 single-digit full adders arranged in the form of the 7 ´ 3-matrix. Each ternary single-digit adder has a designation of where the number 4 means that the adder has 4 ternary inputs, the lower index i means the digit number in the ternary mirror-symmetrical representation and the higher index k means the row number of the matrix adder in Fig. 1.
The inputs of the single-digit adders
of the first row form the multi-digit input of the matrix ternary mirror-symmetrical adder. The output of the intermediate sum of each single-digit adder is connected to the corresponding input of the next single-digit adder of the same column.
The outputs of the intermediate sum of the single-digit adders
of the last row form the multi-digit output of the matrix ternary mirror-symmetrical adder.
The basic peculiarity of the matrix mirror-symmetrical adder in Fig. 1 consists of the special organization of the connections between the carry outputs of the single-digit adders and the inputs of the neighboring single-digit adders. The carry outputs of all the single-digit adders with the even low indices (2, 0, -2) are connected to the corresponding inputs of the neighboring single-digit adders aligned in the same row but the carry outputs of all the single-digit adders with the odd low indices (3, 1, -1, -3) are connected to the corresponding inputs of the neighboring single-digit adders aligned in the low row. Note that such organization of carry connections allows eliminating the above-considered "swing" phenomenon.
Let's consider operating the matrix mirror-symmetrical adder for the concrete example. Let's sum up two equal mirror-symmetrical numbers:
A = 0 1 1 1, 1 1 0 and B = 0 1 1 1, 1 1 0.
The addition consists of 2 stages. Each of the stages is realized by one row of the single-digit adders and consists of two steps.
The first stage. The single-digit adders of the first row with the even low indices () form intermediate sums, which enter the inputs of the low (second) row adders, and the carries, which enter the corresponding inputs of the neighboring single-digit adders with the odd low indices of the same (first) row (). The above-considered transformation of the code information may be represented in the following form:
Hence the first step is the formation of the intermediate sums and the carries on the outputs of the single-digit adders of the first row with the even low indices (2, 0, -2).
At the second step the single-digit adders with the odd low indices (3, 1, -1, -3) enter into action. Taking into consideration the carries entered from the neighboring single-digit adders of the same row they form the intermediate sums and the carries entering the single-digit adders of the low row, i.e.
The first stage is over. We can see that some intermediate sums and some carries entering the adders of the lower row are the results of the first stage. These intermediate sums and carries contain in themselves full information about the summable numbers.
The second stage. The single-digit adders of the second row with the even low indices () form the intermediate sums entering the corresponding inputs of the low row adders and the carries entering the corresponding inputs of the same row adders with the odd low indices (), i.e.
AS all the carries formed at this stage became equal to 0 this means that the addition is over at the second stage (this is true only for the case considered). The obtained sum enters the inputs of the lower row adders and then appears on the output of the adder.
Pipeline mirror-symmetrical adder. There exist two ways for the widening of the functional possibilities of the matrix mirror-symmetrical adder in Fig.1. If we set the ternary memory registers between the neighboring rows of the single-digit adders then the above-considered matrix adder turns into the pipeline mirror-symmetrical adder. In fact, the code information from the preceding rows of the single-digit adders is memorized in the corresponding memory registers and the preceding row of the adders becomes ready for the further processing. Then the adders of the low row begin to process the code information entered from the preceding row and simultaneously the top row of the single-digit adders starts to process the new code information. This means that starting since the given moment we will get the sums of the numbers A1 + B1, A2 + B2, ..., An + Bn entering the adder input sequentially through the time period 2Dt, where Dt is the delay time of the single-digit adder.
Pipeline mirror-symmetrical multiplier. Other possibility to widen the functional possibilities of the pipeline adder consists of the following. We can see from Fig. 1 that each single-digit adder of the low rows has the "free" input. We can use these inputs as the new multi-digit inputs of the pipeline adder. Using these multi-digit inputs we can turn over the pipeline adder into the pipeline multiplier. In this case multiplication of the two mirror-symmetrical numbers A(1) ´ B(1) is performed in the following way. The first row of the single-digit adders sums up the first two partial products . The intermediate result of the addition enters the second row of the single-digit adders. If we send now the 3rd partial product to the "free" multi-digit input of the second row we will get the sum on the outputs of the second row. Starting since this moment the first row starts summing up the first two partial products of the next pair of multiplied numbers A(2) ´ B(2). The "free" input of the 3rd row is used for receiving the next partial product of the first pair of the multiplied numbers A(1) ´ B(1) etc. We can see that the pipeline adder in Fig. 1 allows multiplying many mirror-symmetrical numbers in the pipeline regime. In so doing the pipeline multiplication speed is determined by the time 2Dt, where Dt is the delay time of the single-digit adder.
Thus we have considered the highly unusual mirror-symmetrical arithmetical device allowing to perform in the pipeline regime three important arithmetical operations: addition, subtraction and multiplication of the mirror-symmetrical numbers. But if integers are the input information of the mirror-symmetrical adder in this case the output information will be represented in the mirror-symmetrical form. This means that the mirror-symmetrical numbers allows controlling the arithmetical processes in it.
We can realize the pipeline mirror-symmetrical adder only for the case if we use the ternary registers in it. But what means the "ternary register". We will give an answer this question at the next page of our Museum. Follow us!