JPH05290077A - Accumulator - Google Patents

Abstract

(57) [Summary] [Object] To construct an accumulator for n-fold time-division multiplexing processing, which requires a small circuit scale and has a delay time of about p full adders. [Configuration] A full adder (FA) 10 adds the j-th bit input data I _j and the j-th bit cumulative addition result above the register R in the first stage. Then, between the register R of the first stage and the register R of the second stage, the input data I _{j + 1} of the j + 1th bit, the cumulative addition result of the j + 1th bit, and the full adder 1
The carry output from 0 is added by the full adder (FA) 11. In addition, j between the registers R in the second and third stages
The full adder 12 (FA) adds the +2 bit input data I _{j + 2} , the j + 2 bit cumulative addition result, and the carry output from the full adder 11. This gives 6
The register R output of the (= n) th stage has a carry only at the j-th bit and no carry at the j + 1-th bit and the j + 2-th bit.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an accumulator for cumulatively adding a plurality of data groups by time division multiplexing processing.

[0002]

2. Description of the Related Art The circuit configuration of an accumulator (cumulative adder) is disclosed in JP-A-64-86271, JP-A-3-1096.
No. 70 is disclosed. JP-A-64-86271
The publication discloses that by adding a carry (carry) for each bit and performing addition, calculation can be performed with a delay time of about one full adder (FA), and high speed operation is possible. ing. Further, in Japanese Unexamined Patent Publication No. 3-109670, a carry can be added for each r (r is an integer of 2 or more) bits and added, whereby calculation can be performed with a delay time of about r full adders and high speed operation is possible. It has been shown that The device disclosed in JP-A-64-86271 is faster than the device disclosed in JP-A-3-109670, but the circuit scale is larger.

FIG. 3 shows the configuration of the device disclosed in Japanese Patent Laid-Open No. 64-86271. In this figure, 1 bit (jth bit)
Although only shown in the figure, in actuality, the calculation is performed by using the configuration of FIG. 3 in parallel for the word length. In addition, this output is 2 bits of carry (carry output) and sum (sum output) per bit.
Since it is output by the wiring of the book (that is, output by a redundant expression), a carry adder is required as a post-processing circuit separately from the figure in order to return to a normal non-redundant binary expression. In this figure, a timing chart of inputs when calculating A + B + C + ... Is shown in FIG.

Since the apparatus disclosed in Japanese Patent Laid-Open No. 64-86271 operates at high speed, it is possible to perform time division multiplex processing on low bit rate data. For example, three cumulative additions of A + B + C + ... And A '+ B' + C '+ ... And A "+ B" + C "+ ... Are combined in one circuit by triple time division multiplexing processing. For the calculation, the device disclosed in Japanese Patent Laid-Open No. 64-86271 may be applied to obtain the configuration shown in Fig. 5. A timing chart of inputs at this time is shown in Fig. 6.

Since the registers R are serially connected in three stages in FIG. 5, data for every three cycles in FIG. 6, that is, (A, B, C, ...) And (A ', B', C). ′, ...) And (A ″, B ″, C ″, ...) Three additions can be calculated by one circuit (FIG. 5).

Although only one bit is shown in FIG. 5, in actuality, the word length is used for the operation by using the configuration of FIG. 5 in parallel. Also, since this output is output (that is, output in a redundant expression) with two wires of carry (carry output) and sum (sum output) per bit, it is restored to a normal non-redundant binary expression. For that purpose, a carry adder is required as a post-processing circuit in addition to that shown in FIG.

As can be seen by analogy from FIG. 5 in the case of triple time division multiplex processing, generally, when the n-fold time division multiplex processing is applied to the apparatus of Japanese Patent Laid-Open No. 64-8671, the word length is One full adder and 2n registers are required for each bit, which leads to an increase in circuit scale.

Further, Japanese Patent Laid-Open No. 3-109670 (r
When n-time-division multiplexing processing is applied to a device of an accumulator that leaves a carry for each bit, a total adder of r registers (r + 1) n is required per word length of r bits, that is, a word length of 1 One full adder and one register (r + 1) n / r are required per bit, which leads to an increase in circuit scale. (R is 2
An integer greater than or equal to)

Summarizing these two matters, the accumulator of the n-fold time-division multiplexing process, which has a delay time of about p full adders in the prior art, has a full adder 1 per word length. Individual registers (p + 1) n / p were required, which led to an increase in circuit scale. (P is 1
An integer greater than or equal to)

[0010]

A problem to be solved is that in the case of performing time division multiplexing processing, conventionally, the circuit scale has been increased.

[0011]

According to the present invention, in an accumulator for cumulatively adding a plurality of data groups by time division multiplexing processing, a predetermined register among the registers R holding the cumulative addition results of the plurality of data groups is provided. Addition with the input data relating to a predetermined digit between (full adders 10, 11, 1
It is an accumulator characterized by performing 2).

[0012]

According to this, the circuit size is smaller than one full adder register (p + 1) n / p per word length of 1 bit, and the operation speed is a delay time of about p full adders. It is possible to configure an accumulator (p is an integer of 1 or more) for n-fold time division multiplexing processing.

[0013]

FIG. 1 shows an embodiment in which n = 6 and p = 1. In this figure, 3 bits (jth bit, j + 1th bit, j +
Only the second bit is shown, but in reality (word length /
3) Calculation is performed by using the configuration of FIG.

Conventionally (for example, in FIG. 3), the calculation of each bit is performed by the full adder in the portion above the register R in the first stage.
The full adder outputs in a form in which the carry remains (that is, in the form of carry and sum), and this is received by the register R of the first stage. Then, the registers R to n (FIG.
Then, the registers R up to the (n = 3) th stage are simply connected in series, and no calculation is performed between the registers R.

However, in the present invention, the j-th bit input data I _j and the j-th bit cumulative addition result (the 6th (= n) -th stage j-th bit register R are located above the first-stage register R. The full adder (FA) 10 performs addition of output and carry from the lower part of FIG. Then, between the register R of the first stage and the register R of the second stage, the input data I _{j + 1} of the j + 1th bit and the cumulative addition result of the j + 1th bit (6
(= N) th stage (j + 1-th bit register R output) and carry output from full adder 10 are added to each other by a full adder (FA)
I'm going at 11. Further, between the register R of the second stage and the register R of the third stage, the input data I _{j + 2 of the j + 2th} bit
And the cumulative addition result of the j + 2nd bit (j of the 6 (= n) th stage
The addition of the carry output from the full adder 11 is performed by the full adder 12 (FA).

As a result, the register R of the sixth (= n) th stage
The output has a carry (carry from the lower part of FIG. 1) only at the j-th bit and no carry at the j + 1-th bit and the j + 2-th bit. That is, the output terminal O _j , which is a redundant expression that a carry exists only at the j-th bit,
It is output to O _{j + 1} and O _{j + 2} .

The output of the register R of the nth stage is output to the feedback output terminals O _j , O _{j + 1} and O _{j + 2,} and is output from the input terminals I _j , I _{j + 1} and I _{j + 2} . The data is added by full adders 10, 11, 12.

A feature of FIG. 1 is that each full adder is always sandwiched by one register R. Therefore, the operation speed is a delay time of about one full adder.

In FIG. 1, a total of three full adders (10, 11, 12) are inserted up to the register R of the third stage, but this is generalized to a full adder by the register R of the mth stage. It is also possible to form a circuit by sandwiching m in total. However, m
Is n or less.

In this case (generalization when p = 1), the circuit scale is 1 full-adder per word length 1 bit {(registers from the first stage to the m-th stage per word length m bits) R total) + (m per word length m bits)
The total number of registers R from the + 1st stage to the nth stage)} / m = {((3m + 1) m / 2) + ((m + 1) (n-m))} / m = m / 2-1 / 2 + n + n / When the number is m, and k = √ (2n), the scale is the minimum scale, and the scale is 1 full adder per word length 1 bit register n−1 / 2 + √ (2n). Therefore, when n is sufficiently large, the number of registers R is about n, which is a saving of about n per word length 1 bit as compared with the conventional case (p = 1).

Further, the finally obtained output (cumulative addition result) has a redundant wiring (output) of 1 bit per m-bit word length, and conversion (carry addition) for returning to a normal non-redundant binary representation. The container can also be constructed in a smaller scale than in the conventional case (p = 1).

Thus, according to the above-mentioned device, the circuit scale is smaller than one full adder register (p + 1) n / p per word length of 1 bit, and the operation speed is a delay of about p full adders. It is possible to configure an accumulator (p is an integer of 1 or more) for n-time time division multiplex processing, which is time.

The application of the present invention to the case of p = 1 has been described above. Next, n = 20, p = 3, m
= 2 will be described. Of course, it can be generalized (arbitrary n, p, m (m is n or less)), but it will be omitted because it becomes complicated.

The m here means the above-mentioned m, that is, it means that a total of m p-bit adders are sandwiched by the register R of the m-th stage. n = 20, p = 3,
A circuit for m = 2 is shown in FIG. In this figure, 6 (= m
p) bits (jth bit, j + 1th bit, ... j
Although only +5 (= j + mp−1) th bit) is shown, in actuality, the operation of (word length / 6 = word length / mp) pieces is performed using the configuration of FIG. 2 in parallel.

Conventionally (not shown), the register R of the first stage is used.
In the upper part, the calculation of each bit is performed by the p-bit adder, and the p-bit adder outputs in the form in which the carry remains (that is, in the form of carry and sum), and this is output in the first stage. Register R was receiving. And the register R of the first stage
To the register R of the nth stage are simply connected in series, and no operation is performed between the registers R.

However, in the present invention (FIG. 2), in the portion above the register R in the first stage, the j-th bit, the j + 1-th bit,
the input data I _j , I _{j + 1} , I _{j + 2} of the j + 2nd bit,
Cumulative addition result of the j-th bit, the j + 1-th bit, and the j + 2-th bit (j-th register R output of the 20 (= n) th stage,
Addition of the j + 1th bit register R output, the j + 2nd bit register R output, and carry to the jth bit from the lower order of FIG. 2) is performed by a 3-bit (= p) adder.

Then, between the register R of the first stage and the register R of the second stage, the j + 3th bit, the j + 4th bit, and the j + 5th bit.
Input data I _{j + 3} , I _{j + 4} , I _{j + 5} , and j + of the bit
Cumulative addition result of 3rd bit, j + 4th bit, j + 5th bit (j + 3rd bit register R output of 20 (= n) th stage, j + 4th bit register R output, j + 5th bit register R output The carry output from the adder to the j + 3th bit is added by the 3 (= p) bit adder.

Further, in FIG. 2, since the 3-bit (= p) adder composed of 3 (= p) full adders is always sandwiched by the register R, the operating speed is equivalent to that of the full adders 3. It will be a delay time.

The circuit scale of FIG. 2 is one full adder, one register 143/6 per word length 1 bit. Thus, the word length per bit is (p + 1) n / p- (143/6) = 17 / from the conventional case (n = 20, p = 3).
This saves 6 registers R.

As can be seen from FIGS. 1 and 2, the m-th to n-th stage registers R are simply connected in series. Therefore, instead of the m-th to n-th stage registers R, (N-
A m + 1) word FIFO or memory may be used.

[0031]

According to the present invention, the circuit scale is smaller than one full adder register (p + 1) n / p per word length 1 bit, and the operation speed is a delay of about p full adders. It has become possible to construct an accumulator (p is an integer of 1 or more) for time-division multiplex processing of n times, which is time.

[Brief description of drawings]

FIG. 1 is a configuration diagram of an example of an accumulator according to the present invention.

FIG. 2 is a configuration diagram of another example of the accumulator according to the present invention.

FIG. 3 is a configuration diagram of a conventional accumulator.

FIG. 4 is a diagram for explaining the explanation.

FIG. 5 is a configuration diagram of a conventional multiplexed accumulator.

FIG. 6 is a diagram for explaining the explanation.

[Explanation of symbols]

10, 11, 12 Full adder R register I _j , I _{j + 1} , I _{j + 2} input terminal O _j , O _{j + 1} , O _{j + 2} output terminal

Claims (1)

[Claims] 1. An accumulator for cumulatively adding a plurality of data groups by time division multiplexing processing, wherein, among registers for holding the cumulative addition results of the plurality of data groups, input data relating to a predetermined digit is input between predetermined registers. An accumulator characterized by performing addition of.