DE2238687A1 - BINARY ADDING ARRANGEMENT - Google Patents

Description

Applicant's file number: UK 970 015

Binary adding arrangement

The invention relates to an adding arrangement for generating the Sum of two multi-digit binary operands (A ^ ,, A ^ _ /

V ' ^(B N' ^B Nl ^{f B} N-2 '* * memory.

B) using an associative

It is already known to use associative memories to run to use arithmetic operations (German Offenlegungsschrift 1 952 020). In these arrangements, one operand (or one operand group) is contained in the associative memory, and the other operand is used for a memory query operation. In the by the associative query operation determined word memory position, the content of the bit positions is read out one after the other and in accordance with the rules the arithmetic binary combination in inverted representation re-enrolled. Several removal and rewriting cycles are necessary to process a multi-digit word.

It is also known in the construction of adder circuits, the entire Subdivide job area into sub-areas (Proceedings of the IRE, Jan. 1961, pages 68 to 70). That way will the circuit complexity for realizing a predictive carry formation is reduced.

The object of the present invention is to specify an adding arrangement constructed using the associative memory,

309812/0739

which avoids the disadvantages of known arrangements of this type and a high operating speed or fewer memory accesses allowed per addition operation and / or subtraction operation. According to the invention this is achieved in that at least two pairs of serial coupled associative memories are provided, the output signals for each bit position on one Supply pair of lines and contain the function tables, their Entries are assigned to the individual operand combinations and can be called associatively as a function of these, that the first Memory of each pair of intermediate functions and the second memory of each pair of result functions, and that for associative calling of the entries in the first memory of one pair, a low-digit part of both operands and for calling The remaining part of the digits of both operands is used for the entries in the first memory of the other pair.

An exemplary embodiment of the invention is described below with reference to drawings. Show it:

1 shows a circuit of an associative storage element as it is in the illustrated adding arrangement Is used

Fig. 2 is a block diagram of a preferred embodiment of the adding arrangement according to the invention and

3 is a block diagram of a modified embodiment

part of the arrangement of FIG.

A storage element as it is in the circuit arrangement of the exemplary embodiment is usable includes a working line 10, a match line 11, two bit lines 12, 13 and an exclusive-OR circuit 14. The element can assume four stable states, denoted by "1", "0", "X" and "Y".

ÜK97OO15 309812/0739

This can be a storage element of the type described in German Offenlegungsschrift 1 801 215. The memory element of FIG. 1 has four transistors T, T ", T_ and T, which are connected to one another in the form of two bistable circuit pairs T, T ₂ and T ₃ , T. The four states are assigned to the conducting states of the transistors T and T. in the following way:.

^τ ι ^Τ 2 ■ 3 ^Τ 4 = O. FTl ^Τ 2 * 3 ^Τ 4 = 1 ITl ^Τ 2 ^Τ 3 V = X T ₁ * 2 T ₃ ^Τ 4 = γ

Each of the transistors T and T ₄ has two emitters, one of which is connected to the match line 11 and the other to the associated bit line 12 or 13. During a search operation, the bit lines 1.2, 13 carry a signal voltage according to the following table:

13 = 0 12th It = 1 T2 Ϊ3 = X 12th 13 = Y

Therefore, if the bit line connected to a conductive transistor carries an increased voltage signal, the transistor current can over the bit line in question cannot be derived and therefore arrives to match line 11. The memory elements of Fig. are arranged in the form of a matrix showing and column-wise, whereby the storage elements of each row are jointly assigned the operating line and the matching line 11, and the memory elements of each column the bit lines 12 and 13 and the exclusive OR circuit 14 are assigned in common. if hence no stream to the assigned one from any storage element of a row Compliance line 11 flows, this serves as an

UK 970 015 309812/0739 ".- ■ = - · ■ ■■ .-.,

show that a match was found and a latch circuit 15 connected to that line in FIG put the on-state. If either the storage element or the search argument is in state X, then for that storage element a match is displayed, and. if either the storage element or the search argument is in state Y, none can Match can be generated for the relevant row of memory elements, unless the state to be compared is X, da an X-state takes precedence over a Y-state.

When reading out information from the memory element of Fig.l those match lines 11 connected to latch circuits 15 in the on-state are on an increased signal level, so that a current flowing in the transistors T to T is conducted to the assigned bit line 12 or 13 will. If current only flows on one of the bit lines, which means that all memory elements of the column read out are im The The output of the exclusive OR circuit 14 of this column has the value 1, while in the other case it has the value "0". A mixed one Output of 1 and 0 values from the storage elements of a column or the presence of a Y output signal always leads to a collective output signal "0". The state Y therefore serves as a possible one Clear signal when searching and as a certain clear signal when reading. The latter feature is for the described embodiment of the invention of interest as it has the meaning that an expression "the result is 1 unless" can with a small number of words when the "unless" situations are relatively rare. In the example, (L + M) * 1 three words 101, 011, 111 (1 + 0 = 1, 0 + 1 = 1, 1 + 1 = 1) without a Y status and two words XXl, 0OY with the Y status are required. Of the the same effect could be achieved in this example by (XXl, 000) so that a three-state memory could be used (A three-state memory corresponds to a four-state memory in which the Y-state is not used). The latter

o ₁₅ 309812/0739

However, there is not always an effect. In a more complex function, in which the "unless" condition can occur without any of the remaining conditions being obtained, and where the There is a possibility that the result may be false, if the "unless" condition occurs alone, the Y state must be used during extraction, since a read "0" appears alone as a "1" after it has been the exclusive-OR circuit 14 happened.

For loading purposes, or for other purposes, the one match will be used indicating latch circuits 15 are normally connected together to form a shift register. It can therefore a 1 in such a register will be shifted to. select one word at a time in a given order, regardless of any search operation * JoiLese facility can also be used not to read out the word found to match during a search operation, but rather in each case the next word in the stored order, where the search field can be the width of the memory, as it is for the Result field applies.

The adder circuit shown in FIG. 2 contains an associative memory pair 20, 21 for a low digit part (low digit memory pair) and an associative memory pair 22 for a high digit part (high digit memory pair). Each memory of the mentioned memory pairs consists of a number of memory elements of the type described in connection with FIG. 1. The circuit receives an A operand from a register 24 and a B operand from a register 25 as input signals. The content of a low digit 34, 36 of both registers 25, 24 is transferred to memory 20, and the content of a high digit 37, 39 of both registers 25, 24 is transferred to memory 22. The memory 20 generates P and G functions of the low-order bits as well as further functions C and C _p according to the links P = AVB; G = A · B, where C,

X. J_ L · X · J- -Σ. J-

the carry from the highest bit position of the lower part

UK 970 015

309812/0739

and C is the carry propagation function. The memory 21 receives the low-digit P and G functions as well as a carry C at an input 26. This memory generates the low-digit part of the result, which is transmitted from the output of the memory 21 to an output register 27. The memory 23 receives the high-digit part of the P and G functions as well as the functions C _T and C _n as well as the transfer on line 26 and generates the high-digit part of the result, which is also sent to the output register 27. The memory 24 also generates a carry output which appears as the result bit of bit position (N + 1). For the sake of simplicity, it has been assumed that each operand has only eight bits, namely four low-order bits and four high-order bits. The carry output bit is result bit 9. All output lines of the four memories are routed via exclusive-OR circuits, not shown in FIG. 2, of the type of exclusive-OR circuit 14 of FIG. The four C_ read paths are connected to one another at 32, as a result of which an OR operation is practically obtained, the result of which is fed to the memory 23 as a single composite C input signal.

The complete tables for carrying out the addition are given in FIG. The basic method is based on the conventional one Two-cycle addition using the following relationships:

* N ^{= A} N ^VB N ^{V 0} NI

^C N-1 = ^A N-1 * ^B N-1 ^{+ {A} N-1 ^{V 1} W * ^C N-2

where R is the result bit of digit N and C is carries.

C is identical to C .. It becomes clear that if there is no transfer in C, the memories 22 and 23 only have bits A ₀ to A

8 need 5 B ₈ to B ₅ and C _4. However, C ₁ cannot be ignored,

and C _p is also required since C _{1 is} not in memory 20

970 015 309812/0739

2298687

is entered. C = 1 is therefore derived indirectly from the search fields, which define circumstances in which C- may not be transferred to the higher-digit fields. These are the following cases: (A ₁ · B ₁ + A · B ₃ + A _3. B ₃ + A ₄ · B ₄ ). The four suitable search expressions are already in memory (words 5 to 8 in memory 20). The "All X" search term is also present (word 9 in memory 2Q). C can therefore be derived using a single column (XXXXOOOOl). This column is part of the entries that would also be required if C ₁ could be ignored. Since the "1" entry is derived from the "All X" search field, it must always be read out, which is why a "0" deletion expression is sufficient.

The P functions are always "Γ" unless A · B = 1 or Ä · B = 1. Therefore, with the word 9, which has a "1" value for P-term generated in memory 20, "O" clearing terms for A · B = 1 and A B = 1 is sufficient.

The G functions, of which only G ₃ G_ and G _{1 are} required, are obtained directly from words 1 to 3 in memory 20 in the example shown.

The. composite function C _T is 1 if:

Yy

(A. B. = l) or
4 4

^(A 3 * ^B 3 = 1; it may be • because ^A 4 * i = D or ^A 3 -B ₃ = D. ) or (A, * ^B 2 = 1> it may be because (A ₄ t = 1 or • ^B 3 ⁼ 1 or * ^B l = 1 / it may be because (A ₄ 1 = 1 or ^A 2 * B ₂ = D.

C ₁ . ? 1 if Ä _o · B ₀ = 1 stands alone. There are therefore "Y '^ delete

L / Z

expressions in words 6 through 8 of memory 20 are required. The output signals of the columns C are read out through Exclusive-OR connected via the appropriate line pairs, such as all output signals of the memory. The result signals of the Exclusive-OR links become a common one

970 015 309812/0739

Transmission line out, with an additional OR link through the line junction 32 is obtained.

The memory 22 is designed similar to the memory 20, with the exception that the read fields C _T and C_ are missing and that G ₀

LP ο

hand is.

The memory 21 generates the result bits R., R_, R and R ₁ in the following way:

R ₁ = 1 when P ₁ = 1; unless C ₁ = 1; or

when C ₁ = 1; unless Ρ _χ = 1 (Α _χ ¥ Β _χ ¥ C _3. ) R ₂ = 1 when P_ = 1; unless G = I, or

P ₁ = 1 and C ₁ = 1, or

when Ρ _χ = 1 and C ₁ = 1; unless P ₃ = 1, or if G ₁ = 1; unless P "= 1; (A ¥ B ₃ V C.) R ₃ = 1 when P ₃ = 1; unless G_ = 1, or

P ₂ = 1 and G = 1, or P = I and P ₁ = 1 and C ₁ = 1, or when G_ = 1; unless P ₃ = 1, or if P ₃ = 1 and G = 1; unless P ₃ = 1, or if P "= 1 and P = 1 and C ₃ . = 1; unless

P ₃ = 1 (A ₃ VB ₃ VC ₂ ) R. = 1 if P. = 1, unless G ₃ = 1, or

P ₃ = 1 and G ₂ = I, or

P_ = 1 and P ₂ = 1 and G = I, or

P ₃ = 1 and P ₂ = 1 and Ρ _χ = 1 and

C ₁ = I, or when G ₃ = 1 ; unless P ₄ = 1, or

P ₃ = 1 and G ₂ = 1, unless P ₄ = 1; or P = I and P ₂ = 1 and G ₁ = 1, unless P ₄ = 1, or P- = 1 and P_ = 1 and P ₁ = 1 and C ₁ = 1, unless P ₄ = 1 (A ₄ ¥ B ₄ VC ₃ ).

With this information, all possible combinations are exhausted so that either "1" entries or "O" entries perform clear functions and "Y" entries are not required in the reading fields.

30981? / 0 7 3 9

UK 970 015

The memory 23 is similar to the memory 21. C and C as well as C and C ₁ are additional entries, so that the lowest result bit of this memory is obtained in the following way:

R, - = 1 if P- = 1, unless GL. = 1, or

Gp = 1 and C ₇ = .1; or when C _x = 1, unless P ₁ . = 1, or when C = I and C ₁ = 1, unless P ₁ . = .1; (A ₅ ¥ B ₅ V (C _x + Cp · C ₁ )).

If one takes into account that in a table formation in a conventional manner between 15 and 4 words are required for each addition _{to express C x} alone, it becomes clear that the

Yy

The circuit arrangement described allows a compact memory and circuit structure. Since the memory 20 has more read columns than are present in the conventional table, more bits are assigned to the high digit than the low digit when the operands are split into a high digit and a low digit in practice. It is possible _{to reduce the C x} field of the memory 20 to two lines. This takes place in the manner shown in FIG. 3. In this figure only words 1 to 8 are shown, and of each word is only. the search field and the C _x field are shown. The entries

Yy

express the following:

C _x = (A. «Β. Or A_ ° B_) unless (A ₄ -B ₄ ) or

(A ₀ -B ₀ or AB ₁ ) unless (A. «B. Or A - B- or A ₀ -B ₀ ). Zz 11 4 4 Jj δ δ

This expression means an alternate realization of the two statements:, ·

a) for each bit position, the AND operation of the two operand bits of this bit position generates a carry to the high-order end, provided that no carry-consuming The bit position is present in the part of the digit that is higher than the bit position under consideration,

b) creates the AND operation of the two for each bit position

309812/07 39

UK 970 Ο15 · / **.

Operand bits of this bit position carry a carry to the high-digit end, provided that no carry-consuming Bit position is present, unless this bit position is in the order of digits below the one under consideration Bit position.

Although these two statements are similar to one another, their alternating implementation in the adder circuit results in the length of the C _T field being halved.

In the exemplary embodiment shown, there is a total of 38 words contained in memories 21 and 23. The number of words in the memory 23 is much greater than the number of words in the Memory 21. If the memory pair 20, 21 is set up to handle bits 5 through 1 of each operand, and if the Memory pairs 22, 23 are set up to handle bits 8 through 6 of each operand, the sum total of the words in the memories 21 and 23 are reduced by 1, and there is an essentially equal number of for each of these two memories Words received. In the same sense, there are changes with regard to the division of the operands between the two memories of every memory pair possible if the operand size increases.

UK 970 015 309812/0739

Claims (1)

' P A-TE-W TA ¹ NS PR Ü C HE Adding arrangement for generating the sum of two multi-digit binary operands (JL ,, & *, _ ■, / ^ Vo ' A ₁ ), (B _n , B _n-1 , B _n _ ₂ , B ₁ ) using a associative memory, characterized in that at least two pairs of serial coupled associative Memories (20, 21 and 22, 23) are provided, the output signals for each bit position on a line pair (12, 13) and contain the function tables, the entries of which are assigned to the individual operand combinations and, depending on these, can be called associatively, that the first associative memory (20, 22) of each pair of intermediate functions and the second memory (21, 23) of each pair contains result functions, and that for the associative call of the entries in the first memory (20) of the one pair a low-digit part of both operands and for calling up the entries in the first memory (22) of the the remaining part of both operands is used for the other pair. 2. Arrangement according to claim 1, characterized in that at least some of the output lines of the first memory (20, 22) of each pair via logic combination circuits (14, 32) with the second memory (21, 23) of the each same pair and, as far as the output lines of the memory (20) which receives the low-order operand parts supplied, with the second memories (21 and 23) of both pairs are connected. 3. Arrangement according to claims 1 and 2, thereby marked. shows that the memories (20 to 23) are word-organized in a manner known per se and search and read-out areas have, and that the outputs of at least some of the memory elements have the same order of positions in the readout areas together to an exclusive OR circuit (14) are connected. 015 309812/0739 4. Arrangement according to claims 1 to 3, characterized in that that at the output of the first memory (20) at least one memory pair the output lines several exclusive OR circuits (1.4) with each other for Form an OR link (32) are allied. 5. Arrangement according to claims 1 to 4, characterized in that split operand registers (24, 25) are provided are, of which the low-digit parts (34, 36) with the first memory (20) of the one pair and the high-digit parts (37, 39) with the first memory (22) of the other couple are connected. 6. Arrangement according to one of claims 1 to 5, characterized in that the intermediate functions stored in the first memory (20, 22) of each pair are the exclusive OR operation (P) of operand bits of the same order, the AND operation (G) of operand bits of the same order and contain a carry condition (C _r ) of the highest bit position in the low-order operand part. 7. Arrangement according to claim 6, characterized in that the intermediate functions "carry condition (CL)" by OR operation (32) are formed from at least two intermediate result signals that are generated by exclusive-OpER linkage (14) the output signals of the associated memory cell columns, can be obtained. 8. Arrangement according to one of claims 1 to 7, characterized in that that the memories (20 to 23) contain three-state memory elements, which in groups (columns) with their output to a common exclusive OR circuit (14) are connected via the function values of the form U, unless V can be read out, where U and V are represented by the Binary values "1" and "0" are shown. 9. Arrangement according to one of claims 1 to 8, characterized in that UK 970 015 3098 12/0739 indicates that the memories (20 to 23) contain four-state memory elements which, in groups (in columns) with their output to a common Exk ^ GDER circuit ■. (.1.4) connected - "- are, - 'via the function values of the form S, unless T can be read out, where S is a binary value of the first two storage states and T is represented by one of the other two storage states .: - -: ■ '-,:;: -: -, "' Λ -": .-- "-. "'--- - ^: .- .- ■■'■" ^ ■■ - ^: - ΙΟ »Arrangement according to claim ^ 8 or 9, characterized in that that a; V storage state '- as ^^ neutral storage state (X) serves, which is independent of the associative addressing signal in each case a match signal aitt output of the Memory element generated, 11. Arrangement according to one of claims 8 to 10, characterized in that that a memory state serves as a lock or erasure state (Γ), which in the event of an associative call is a binary 1 value at the output of the exclusive OR circuit (1.4) blocked by supplying two identical input signals. UK97OO15 309812/0739