DE1945215C3 - Associative memory - Google Patents

Description

The invention relates to an associative memory with memory cells for one binary digit each, which are wired in rows and columns to form a matrix, with each row at least one Includes storage space with several binary digits and assigned the corresponding digit parts Storage cells of the storage locations are in the same columns of the matrix, and each Memory cell, a bistable memory element, a comparison circuit, a write gate circuit and a Reading gate circuit contains, with an information word register, to whose level outputs information lines are connected, each with the comparison circuits of all memory cells lying in a column are connected in such a way that each comparison circuit a the match or mismatch between the content of the associated Storage element and the binary digit transmitted via the information line indicating signal outputs, with an addressing register, to whose slave outputs addressing lines are connected, the each with the control inputs of the comparison circuits of all memory cells lying in a column are connected with line lines, which are each connected to the outputs of the comparison circuits of the memory cells belonging to a memory location are connected in this way are that they then and only then have a voltage value that indicates compliance, if there is a match in all the columns subject to the comparison, with reading references which each with the outputs of the reader circuits of all memory cells in the same column are connected, and to write control lines, each of which to the control inputs of the write circuit certain memory cells is connected.

An associative memory is known to be a digital information memory, in which the access to the Storage locations not based on the information about the location of the individual storage locations (»address«) takes place, but on the basis of the content of the memory cells; such memories are therefore also called "Content-addressed memory". Finding certain stored information takes place in that the contents or a certain part of the contents of all storage locations with a predetermined comparison criterion is compared; for those storage spaces for which a full If a match is found, a signal is emitted which identifies the memory location concerned and reading out the content of this memory location or writing in new information in this space allows.

The known associative memories have im

Principle all the structure specified at the beginning. A particularly vivid example of this state of the Technology is described in the magazine "Frequency" 1966, pp. 69 to 82, and in particular in Fig. 7 Shown on p. 75. In these known associative memories, the information register mentioned at the beginning contains the comparison criterion that is transmitted via the information lines is fed to the comparison circuits of the individual memory cells. The addressee register is a mask register that is only used for comparison in certain columns of the memory matrix, while it "masks" the remaining columns. To the Row lines are connected to detectors, which detect and store the signal, which is the complete one Correspondence between the comparison criterion and the content of the subject to comparison Indicates memory cells of a memory location. Through these parts of the memory, the Comparison criteria "addressed" memory locations found.

The subsequent 1 reading of the contents of the found Storage space or the writing of new information in this storage space takes place at the previously mentioned known associative memory in that due to the standing in the detector An internal address for the memory location found is generated by an encryptor based on the result of the comparison and with the help of this internal address a word driver is controlled via a decoder. In In this case, the searches of the reads and writes are linear and organizational separated.

The DT-AS 12 69182 is an associative memory known who works without creating an internal address with direct access to the line for which one Agreement was found. For this purpose, a line access switch is provided for each line, which is set depending on the search result and access for the intended read or Enables write operations. In this case too, reading or writing takes place in two phases: In the In the first phase, the correct memory location is searched for by the associative search process and with the help of of a memory element is marked, and in the second phase the reading or writing of the takes place Contents of the marked storage location.

In the first mentioned literal passage "Frequency" there is also the possibility of direct access to the The data part of an associative memory is mentioned, but the defined division of the memory into requires an associative part and a Dater.leil.

The object of the invention is to create an associative memory of the type specified at the beginning, which with reduced circuit complexity results in a significant shortening of the memory cycle and in which all memory cells can be used indiscriminately as data memory cells or as associative memory cells are.

According to the invention, this object is achieved in that the signal inputs of the Schrcibtorschaltungen of all memory cells lying in a column are connected to the information line assigned to this column are that each write control line with the control inputs of the write gate sounds of all memory cells lying in a column is connected, 6j, that a further control input of each write gate circuit is connected to the associated row line, that the control input of each reading gate circuit is connected to the associated row line \, and that the the voltage value on the row line indicating the agreement as an unlocking signal for the connected Reading gate switching and writing gate switching works.

The design according to the invention has the effect that the triggering of a search process subsequent writing or reading process is immediately possible without first a storing detector element queried or an access switch must be set, and without external addressing necessary is. At the moment when a memory location matches the The comparison criterion has been established, the content of the entire storage space is thus immediately available available on the read lines: if certain write control lines are also energized, in the memory cells of the relevant memory location connected to these write control lines das from the respective assigned fnfonii: iiionleiiung transferred bits are written in at the same time. Therewith Not only does the additional time required to control the relevant storage space and the triggering of the reading or writing process with Using an internal address or \ on storage elements or access switches, but above all also the entire cost of sounding required for this.

In the associative memory according to the invention, use is made of the fact that, as a rule, at associative storage of the contents of the memory cells subject to the comparison during a write process should not be changed, since this content represents the associative address. These memory cells are therefore generally excluded from the write process, which is determined by the corresponding selective Excitation of the writing curling is possible. the The writing process can therefore be carried out while the comparison hits are still pending. This organization gives further advantages: the information to be written can be stored in the same information word register be stored like the comparison criterion, so that a special input cgister is omitted, and it only a single information line is required per column of the memory matrix, which can be either the comparison bits or the information bits to be written. Practically done through the selective Excitation of the write control lines and the addressing lines a subdivision of the memory locations into one associative part and a data part, as is usual with associative memories, but this division can be changed at any time at will.

As with the known associative memories, it is also possible with the memory according to the invention, to provide a priority logic circuit that effects a priority control when several storage locations meet the same comparison criterion. According to an advantageous embodiment of the Object of the invention happen that the priority logic circuit a cascade of Vcrriegclungsschallungcn which are enabled in a sequence one after the other by the program signal and at each step of the sequence a line separation to accept the one indicating the match Release voltage value and all remaining row lines on one of the apparent mismatches Maintain the appropriate voltage value.

An embodiment of the invention is shown in the drawing. In it shows

F i g. 1 is a partially implemented block diagram Circuit diagram of a Spcichcrmoduls the associative memory according to the invention and

F i g. FIG. 2 shows a block diagram of an associative memory according to the invention, which is composed of the elements shown in FIG. 1 memory modules shown is constructed.

The in F i g. The associative memory shown in FIG. 2 consists of a number of memory modules 5, which are arranged in Hi horizontal rows and η vertical rows and correspondingly with 5, "5 ₂ , ... 51", ... 5, ", 5 ₂ " .. . 5m "are designated. Each memory module 5 has the one shown in FIG. 1 structure shown; it contains a plurality of memory cells 10 which belong to certain rows and columns of the memory; the reference numeral 10 are therefore in FIG. I added two indices which identify the column and the row in which the relevant memory cell 10 is located. The memory module 5 of FIG. 1 contains eight memory cells 10, which are in two columns /, / - | - 1 and in four rows k, k I-1, k ~ | · 2, A- + 3. The memory cell 10i, ι -,., Located at the intersection of column / and row k is shown in FIG. 1 shown in more detail, while the remaining seven memory cells ΙΟ, ·. * ,,; 10i.fr, “; 10 _Μ ·; ₃ : 10 ^,. »·: 10, ·, * - +,; 10 _f . _A ,.,; ΙΟ, -. /, ·!;, Are only indicated.

The eight memory cells 10 of the memory module 5 can also be referred to as intermixtures, from which larger memory matrices are composed. The smallest memory that can be built with such memory modules only consists of a single memory module. A memory made up of memory modules of this type is further organized in such a way that all memory cells lying in a row k form a single memory location. The index / defines a bit space within this memory location, and all memory cells assigned to the same bit parts in the different memory locations are in the same column /.

The memory matrix in general and the memory module shown in particular has three input lines II ', /, L and one output line D for each column, such as the input lines Wi, / ?, £ -? and the output line D, - for the column;. The line Wi is the writing control line which, when energized, causes a bit to be recorded in at least one memory cell 10 of the column /. The line /, · is the addressing line which, when energized, indicates that it is assumed for the current associative search process that the bit location / storage locations contains an address bit. The line Lt is the information line that carries the corresponding information bit. When the write control line W ₁ is excited at the same time as the line Z, <, the bit given on the information line Li is a data bit to be recorded. If the addressing line / j is excited at the same time, the bit on the information line Li defines an associative search bit and a memory cell is searched for in the column / which contains a bit which is equal to the bit supplied by the information line U. The output line Di is the read line, which removes a bit from an addressed bit position in the column; enables. Each row has a single row line K, like the line Y _k for row A. which serves both as an input and as an output line for all memory cells in this row. Therefore, each matrix point is served by five lines, as will be explained in more detail below. As a result of the signal processing inside the memory module and outside of the memory cells, as will be explained below, two additional connection lines are required for each memory cell, so that each memory cell with seven connections is wasted is.

It is now the structure of a single memory cell 10 within a memory module 5 on the basis of the

ίο memory cell 10i.fr from Fig.! to be discribed. Five input connections 11, 12, 13, 14 and 15 as well as two output connections 16 and 17 are provided for the relevant memory cell 10, · t. The input connections U, 13 and 14 are connected to the input lines / f, Wf, or / _, · of the column /. Terminal 12, together with the corresponding terminals of the remaining memory cells in the same column, is connected to a line which in turn is connected to information line L ₁ via a non-element 18 and is therefore referred to as "complementary information line t7" can. The connection 15 is connected to the row line K * of the row A 'via an amplifier 32. The output terminal 17 is connected to the row line Yt via a non-element 31, and the output terminal 16 is connected, together with the corresponding terminals of the other memory cells of the same column, to a line which is connected to the read line D, the column / via a non-element Link 35 is connected, and can accordingly be referred to as "complementary reading line 75 ~".

The central element of each memory cell is a bistable element 20, which can be a simple bistable flip-flop. The flip-flop 20 is of course always either in the set or in the reset state and it is assumed that these states correspond to the binary value 1 or the binary value 0. The outputs of flip-flop 20 are one of two AND gate 21. 22 existing comparison circuit and connected to a reading gate circuit 23 while its inputs are connected to a write gate circuit consisting of two NAND gates 24 and 25 are. The following circuit connections are established:

One input of the AND element 21 is connected to the direct output of the flip-flop 20. Two further inputs of the AND element 21 are connected to the input connections 11 and 12, respectively. An input of the AND element 22 and an input of the reading gate circuit 23 are connected to the complementary output of the Füpfiops 20. Two further inputs of the AND element 22 are connected to the input connections 14 and 14, and a further input of the AND element 23 is connected to the input connection 15. The outputs of the AND gates 21 and 22 are connected to one another in an OR operation to form a non-equivalence circuit; the output of the comparison circuit thus formed is connected to the output terminal 17. The comparison circuit 21, 22 is set to standby during an associative search process and compares the bit given to column i via the information line Lt with the state of the flip-flop 20. The output of the reading gate circuit 23 is connected to the output terminal 16. The reading gate circuit 23 therefore supplies a signal to the connection 16 which is complementary to the state of the flip-flop 20 when the relevant memory cell is activated via the connection 15 connected to the row line} '»-.

p The Asso AND gates 21, 22 of the comparison circuit have an output signal "1" off, so that a signal "0" is transmitted to output terminal 17.

The same signal "0" is sent to the output terminal 17 when the relevant memory cell 10 ", * does not take part in the associative search process because then the AND gates 21, 22 of the comparison circuit are blocked by the »0« signal on the addressing line / <.

If, on the other hand, the content of the flip-flop 20 does not match the search bit on the information line Lt , either the AND element 21 or the AND element 22 emits the output signal "1", which is transmitted to the output terminal 17, provided that at the same time the activation signal is present on the addressing line / (. It can be seen that the AND gates 21 and 22 can never emit an output signal "1" at the same time, since both outputs of the flip-flop 20 cannot carry the signal "1" at the same time; The comparison circuit 21, 22 shown actually corresponds to an exclusive circuit.

The output terminal 17 is connected to the row line Yk via a non-element 31. This row line Vj- is assigned to all of the memory cells 10 of the row k , which together form a memory location. As shown in FIG. 1 can be seen, the corresponding output terminal 17 of the second memory cell 10 belonging to the same row k has the memory module 5 shown connected to the input of the same non-element 31. The output of the non-element 31 thus only emits an output signal "1" when the output connections 17 of the two memory cells 10 ,, a- and 1O _{1 + 1} , * - simultaneously lead ial "0" while in all other cases right - Member 31 holds the line Yk - at the signal value "0".

The output connections 17 of all memory cells 10 located in row A are in the same way

the way from "The signal on the addressing line h which indicates the associative search process via corresponding non-elements with the row-pointing signal is coupled to line Y _k . The comparison circuit 21.22 is the input terminal 11 and thereby the one of the two ands not involved in the associative search process - Elements 21 22 of the comparison circuit memory cell 10 is out of readiness when the supplied. It is ^ of AND terms 21, 22 are finally set, will
a signal given the binary value of the search bit
the information line U given to which the
Input terminal 14 of the memory cell connected
is. The non-member 18, which is connected to the circuits 5 °
hears, which carry out signal processing within the memory module S but outside the memory cells 10, generates a signal on the complementary information line 17 which is complementary to the signal on the information line Li; this complete 55

mental signal is the input terminal 12 of the.

^ - The line Yk then and only then takes the

Signal value “1” when all output connections 17 of the assigned memory cells 10 carry the signal “0” 60; this is only the case if all of the memory cells of this row that have been subjected to the associative search process match the contents of the memory cells transmitted via the corresponding information line L.

mentärT ed ^ ngssTgnal of Flipflops20 and carrion Suchbit match, if only in a direct Informationssienal the information line U "5 of these memory cells be-ΪΤ no Ubera.nstimmung Lu S * J7mtanddes Flipflopl is 20, the comparison circuit 21, 22 of the S ^ K ^^ sSÄnieMÄ ^ memory cell 10 a signal .1, from which the non-conduction L ₁ agrees, none of the two members 31 is fed, so that the output signal

609635/119

As a result of the non-member 35 then appears on the reading line £> <a signal reproduced the state of the flip-flop 20.

The NAND gate 25 of the write dead circuit controls the set input of the flip-flop 20. The three inputs of this NAND gate are connected to input terminals 12, 13 and 15, respectively. The NAND gate 24 controls the reset input of the flip-flop 20; its three inputs are connected to input terminals 13, 14 and 15, respectively. The write control circuit 24, 25 therefore causes the flip-flop 20 to be set or reset when the write control line Wi is energized and when the memory location A- (ie all memory cells 10 connected to the row line Y _{k) is activated.}

In the described associative memory, each memory cell 10 can play a double role: the bit stored therein can either be a search bit for the associative search process or a data bit; the respective meaning is not determined by the relevant memory cell, but depends on the control by means of the addressing line /. The energization of the addressing line / <indicates that the column / is participating in the associative search process. ^nip 'ziativsuche is that FeSi''' in the memory cells on Assozi; save receiving column bits .... time via the information line L supplied to the column bit u '-----'- ^*: - ~ result is for those _
positive, in which the content of all memory cells participating in the process corresponds to the search bits transmitted via the assigned information lines L. If this match does not exist even in one of the memory cells participating in the search process, the search result for the relevant line is negative.

Under these assumptions, the Asso meaning runs that the comparison circuits 21. 22 of the Memory cells 10 each emit the same output signals (namely the output signal "0") when they

- either not at all in the associative search process participate (the output signal of the comparison circuit then being independent of the content of the memory cell);

- Or take part in the associative search process and their content matches the search bit transmitted via the information line L.

SSiSA !; And-GLd 21 except for the A ^^ WJJs coming via the addressing line U , the direct output signal of the ^{F 1} P ¹¹⁰ P ^ """ _ions .

complementary information ^{signals d} "lnl ° X * the line Lt, while the AND element 22 auuer

Activation signal of the addressing line «£ as ™ mp mental output signal of the _t ^F1 'P ^flo P _t ^s . *""™,

of the relevant non-element 31 has the signal value "0" Transfer the contents of your flip-flop to the read, whereby the line line Yt is opened on the signal value line A + i. In more general terms: "0" is held, regardless of whether the read gate circuit of each memory cell 10 carries the content of the relevant memory cell to the row via the other comparison circuits of the memory cells 10 signals "1" or 5 read line D as soon as the assigned row line Y emit signals »0«. The output assumes the signal value "1", that is, when the signal of the non-element 31 assumes the signal value "0", so the search result for the memory location in question was soon positive at least one of the two with its input Regardless of whether the connected connections 17 have the signal word "1", the relevant memory cell 10 participated in the associative search independently of the signal value on the other 10 process or not.
Connection 17. Regardless of whether an association

In other words: By activating the ziative search process there is also the possibility of an addressing line / it is determined which memory row line Y will bring signal value "1" to the associative search process through external influence on the cells 10 of a row. This allows a reading to participate. If the contents of these memory cells 15 of all memory cells which are assigned to the relevant row with the search bits transmitted via the assigned information lines L line Y match, assuming, of course, that the remaining row lines Y of the corresponding line Y have the signal value "1" at the same time, memory matrix by external influence on which, regardless of the content, are not kept at the signal value "0". This case is explained in more detail below in the memory cells of FIG. 20 involved in the associative search process.
relevant line. If, on the other hand, in at least one of them, it will now be described how a request for storage information bit involved in the associative search process cannot become a match between the contents and the _{storage cell 10i 1 A.} To carry out a write over the corresponding information line /, over process, it is necessary that the search bit transmitted by write control exists, the line W _{t of} the corresponding column / assumes the signal value "0", again regardless of the . a signal »1« leads. This signal is transmitted via the on contents of the two NAND gates 24 and 25 of the memory cells that are not involved in the associative search process. Writer gate circuit supplied. The writing process

If the row line> '* ■ has the signal value "1" it furthermore requires that the assigned row

leads (positive search result), this signal will have the signal value »1« in line Y _k. This signal value

an amplifier 32, which can also be amplified in one of the two previously indicated ways

components lying outside the memory cells are obtained, namely either as a result of a positive

of the memory module 5 belongs. The input connections tive search result or by an external input

15 of the two effects in the relevant line. In both cases the amplifier provides 32

Memory cells 10 _t , _A and 10, -. *., Are at the output ₃₅ a signal "1" to an input of each of the two

this amplifier 32 is connected. The output NAND elements 24, 25 of the writing gate, where-

signal of the Veratärkcrs 32 is thus in each case to a by the write gate circuit for a write

Input of the reading gate circuit 23 and the two processes are prepared.

NAND gates 24, 25 of the write gate circuit each the bit to be written into the memory cell

of the two memory cells 10 transferred. How then, again on the information line U

Already mentioned, the reading torchief receives the column; given. So it is up to all memory

processing23 also sends the output signal from the grain cells of this column, but is only sent to the memory

complementary output of the flip-flop 20. If the cell of the row is written into its row line Y

the flip-flop 20 is in the idle state, supplies the reading is excited. Depending on the binary value of the information

Torschaitung 23 a signal "1" leads to the output connection ₄₅ mation line L, transmitted information bits

16; if, on the other hand, the flip-flop 20 is set to either the connection 12 or the connection 14 the

If stc'H stood, the reading gate circuit 23 delivers a signal "1", so that the relevant NAND element 25

"0" to the output terminal 16. The output signal or 24 emits an output signal "0". The flip-flop 20

the reading gate circuit 23 thus reaches the complete- is set or reset accordingly,

mental read line D ₁ , which via the non-member 35 50 whereby the information line U to-

is connected to reading line A. Thus, the guided information bit results is stored

Read line A is a signal that corresponds to the state of the I _{n of} the above description of the memory cell

Flip-flops corresponds to 20 as soon as the relevant memory ΙΟ,. * And their mode of operation are already different.

cherzellelO an output signal from the amplifier 32 dene components of the memory module 5 mentioned

is fed. ........ "·. 55, which are common to a plurality of memory cells.

This process naturally takes place for all of the memory cells 32 connected to the non-element 31 and the comparison row line Y , which are connected to the row line Yt at the same time, since all amplifiers 32 of this row give an output signal to the memory cells of this memory module at the same time. as soon as they are sam. Corresponding non-members 311 312,313 row line Y assumes the signal value "1". Thus 60 and amplifier 321 322 323 are provided for the rows in the relevant memory cells 10 lines Y _{k + U} Y _{k +} , γ ' Storage lines A, A ₊ , .. .delivery If, for example, this storage module is used together; This failure to indicate that the cell 10, _Mil did not participate in the link, in particular for the purpose of a special associative search process, because the corresponding column line whose signal was always _{not energized to the addressing line /, 4} , received the signal on the information line U, this memory cell is nevertheless the output signal of the complementary. A corresponding non-element 19 is provided for the amplifier 32, so that its reader circuit for the memory cells is provided in column i + 1. The

Non-member 35 is also common to all memory cells of the memory module located in the column /, and a corresponding non-member 36 is for those in the column; + 1 lying memory cells provided.

Finally, for the column / a non-element 33 is provided which connects the information line h to the write control line W _{of this column; a corresponding non-member 34 connects the information line Zi _{+ 1} to the write control line Wi ι , in the column f "+ 1. The non-member 33 holds this write control line Wt at the signal value" 0 ". When the addressing line Λ the signal value"! This prevents a column that has been selected for an associative attempt process by activating the addressing line / from taking part in a write process through which the bits in this column (which in a sense form the "address bits" of the associative search process) are changed The automatic blocking of the write process for all columns involved in the associative search process in turn enables the circuit structure to be simplified because it is then possible, for example, to connect all write control lines W to a common control source (for example a single write control flip-flop) which excites all write control lines W, as far as this is not caused by excitation of the corresponding corresponding addressing line / are blocked. It is also possible in this way to carry out a write process by external excitation of all write control lines without performing an associative search process, but to exclude certain memory cells from the write process by exciting the relevant addressing lines /.

Finally, conversely, the data bits in certain memory cells can be used before a write process are protected when the address bits for a new associative in other memory cells Address should be registered.

The following special situations are of interest: If all addressing lines / a memory matrix carry the signal “0” at the same time, all row lines Y are brought to the signal value “1” at the same time. If, in this case, the signal "1" is also given on all write control lines W and the signal "0" is given on all information lines L , all flip-flops are reset, ie the entire memory is erased. In other words, by simultaneously energizing all write control lines W while all addressing lines / are held at the signal value "0" at the same time , the bit which is currently being transmitted over the information line L of the relevant column is input into all cells of each column.

It can be seen from the foregoing description that the associative search process does not necessarily always lead to a unique situation. The search condition can be selected so that several row lines Y simultaneously assume the signal value "1". The data output via the read lines D would then not be unambiguous, and when a write operation was carried out, the same information would be written into several memory locations. In order to avoid such uncertainties, the row lines Y are connected to a priority logic circuit 60, as is now shown with reference to FIG. 2 is to be described.

F i g. 2 shows how an associative memory made up of memory modules of the type shown in FIG. 1 type shown can be assembled. Each memory module has, as shown in FIG. 1 eight bit storage locations, each two bits of four different words stored in four consecutive lines. It is assumed that the memory has a total of ρ memory locations and q bit positions per memory location. Here, ρ and q are generally positive integers. For the smallest possible memory, which consists of only one memory module, /> 4 and q - ■ - 2 (m - η - 1) apply. Hence ρ must be an integral multiple of 4 and q an integral multiple of 2. However, this is not a fundamental restriction, but only results from the use of a memory module with 2 × 4 memory cells. It should be noted that in FIG. 2 the memory modules 5 compared to the representation of FIG. rotated by 90 ° so that the "rows" run vertically and the "columns" run horizontally. The memory modules 5 are shown in FIG. 2 arranged in m horizontal rows (which correspond to the columns) and in η vertical rows (which correspond to the rows) and provided with indices, the first digit of which denotes the horizontal row and the second digit of the vertical row. So / 1 = p / 4 and /? I - q / 2 applies, and there are a total of qjl ■ p / 4 memory modules of the in FIG. 1 shown type available. However, reasons of space, only the horizontal in the first two rows of No. 1 and No. 2 and in the last horizontal row number in opposite modules of the first vertical row No. 1 and the last vertical row Nr /.....; lying memory modules 5 ,,, S ₂₁ , 5 »» 1 ^ 5 _in . 5 ₂ ". 5, "" shown.

For these six memory modules are shown in FIG. 1 the associated write control lines W, addressing lines /, information lines L and read lines O are indicated, which are common to all memory modules lying in the same horizontal row, as well as the row lines} ', which are each of the memory modules lying in the same vertical row.

4 modules 5 are common. For the memory modules 5 ,, and 5, π of the first (lowest) horizontal row, these are the write control lines W _x , W ₂ , the addressing lines Z ₁ , Z ₂ , the information lines L ₁ , L ₂ and the reading lines D ₁ , D ₂ ; for the storage

4: 5 modules 5 ₂₁ and 5 _sf! of the second horizontal row the write control lines H ₃ . W ₁ , the addressing lines Z ₃ , Z ₁ , the information lines L ₃ , L ₄ and the read lines D. “Dj; and finally for the memory modules 5 _m and 5 "" of the last horizontal row the write control lines W _q , W _q ~ _x , the addressing lines Z ₇ , Z ₁₇₁ , the information lines L ₉ , L _q - ■ and the read lines D _q , D _q,. For the memory modules S _n , 5 ₂₁ , 5 _{ffll of} the first vertical row, the row lines K ₁ , Y ₂ , Y ₃ , Y _t are shown, and for the memory modules 5, _n , 5 ₂ ″, 5 _{mn of} the last vertical row the row lines Y _v , Yp ~ \, Yp z, Yp 3 All row lines Y are connected to a priority logic circuit 60, which also receives an enable signal coming from outside via a line 66. The priority logic circuit 60 has the task of preventing the simultaneous activation of two or more memory locations if several row lines Y have the signal value "1" at the same time, because the associative search process for the be

«5 relevant memory locations were positive.

In the priority logic circuit 60, each row line Y is connected to one input of a NOR gate, as through the NOR gates 70, 71, 72 fü

13 14

the row lines K ₁ , K ", Y _{3 is} shown. The buffer amplifier 93 and the other, not shown

the second input of each of these NOR gates receives set buffer amplifiers on the row line Y ₁

the release signal coming via line 66. and all following row lines are applied so that

The output of each NOR element 70, 71, 72 ... is to be kept at the signal value "0", regardless of

one input of an OR element 80, 81, 82 ... 5 depending on the result of the associative search process,

connected, the second input of which is connected to the output If no release signal via line 66

The priority logic circuit 60 is connected to the transmission of the preceding OR element

and the first OR element 80 is permanently put out of operation. This is for example for the

Signal value »1« corresponds to the positive potential of the previously described process of deleting the

The output of each OR element 8, 10 of the entire memory is important, in which all row lines

81, 82 ... are held at the signal value »lt via a buffer amplifier 91, 92, 93 ... Y ₁ to Yp

with the following row line K ₂ , Y ₃ , K ₄ ... The priority logic circuit 60 must also then

bound. The OR elements 80, 81, 82 ... form to be put out of operation if the same information

written together with the buffer amplifiers 91, 92, 93 ... veration in more than one memory location

Riegetüngsschaltungen, soft which is to be connected in each case. Finally, the row lines K ₁

sene row line K inevitably on the signal to Y _p also with an outer one, not shown

hold value »0« if any of the preceding addressing arrangements are coupled so that the memory

Row lines carry the signal value "!"

a priority order is established, whereby the processes can be controlled. This

first row line K ₁ the highest and the last row 20 possibility makes the arrangement even more adaptable

line Y _{p has} the lowest priority. more capable, but also presupposes that the

This priority logic circuit 60 operates in the following logic circuit 60 is disabled.
Gender: It is assumed that the read lines D ₁ to D _q , each of which with device 66 an enable signal is applied to all of the NOR elements in the memory cells 70, 71, 72 in the same column. Assuming further that 25 is connected, a data acquisition register 65 is connected to the first row line K as a result of the positive, which has q stages. The read line D ₁ results of an associative search process the signal is with the first stage the data acquisition register 65 carries a value of "1". In this case, the NOR element 70, connected _{to the second stage, emits the read line D 2} a signal "0", which is connected via all of the OR elements connected in cascade and finally the read line D ₉ to the q-th stage 80, 81, 82. The amplified signal “0” is present in the manner described above from the driven row, so that it is read out _{on all row lines K 2 , K 3} ... Y _{v of the memory matrix.} The write b with the exception of the first row line K, an and control lines W ₁ to W ₉ , each of which also holds these row lines on the corresponding 35 with all memory cells of the column in question, even when the comparison is connected connected to a write control circuit 61 circuits of the memory cells lying in a row. This write control circuit 61 can also be a register with q stages, each of which drives one of the write control lines W , to bring the surfing results to the signal value "!" Therefore, only the memory location is selected, 40 This is the case when the non-elements between the first row line K _{1 is} assigned. see the addressing lines / and the write control

It is now assumed that the result of the association W (like the non-members 33 and 34 of

ciative search process negative for the first two lines F i g. 1) not available in memory modules 5

was, so that the row lines Kj and K _{2 are} on the or if no external addressing is possible

Signal value "0" remain while the result for 45 is. If on the other hand the mentioned non-members after

third row was positive, so that the row line K ₃ type of non-elements 33 and 34 are present,

assumes the signal value »l ·«. As a result of the signal, all write control lines W _x to W _q can directly

values "0" on the row lines K ₁ and K ₂ remain connected to one another, and the write control

the output signal of the NOR gates 70 and 71 to the circuit 61 can then be from a single stage

Signal value »1«, which is also available at the outputs of the OR-5 °, to which all write control lines are shared

Gates 80, 81 and the buffer amplifier 91 and 92 are connected, and all of them in the working state

appears. That brings write control lines W to the potential at the output of the buffer amplifier 91,

but the signal "1" that appears brings the line K _2, which indicates that a write process is taking place

not to the signal value »1«, as this should be missing because of the.

The addressing lines Z ₁ to I ₉ , of which each device 21, 22 is connected to at least one memory cell in the column that is in turn held at the signal value "0" with all memory cells of the relevant row, are on the outputs one becomes. In contrast, the row line K _{3 leads} the signal addressing register 63 connected. The addressing value “1”, since it can contain q stages from the comparison switch register 63, with which the lines of the associated memory cells and from the 60 addressing lines / buffer amplifier 92 can be applied separately. The memory location assigned to the lines, if it is not certain from the start that certain line K _{3 is} assigned, is therefore selected as the bit locations of all memory locations of the memory arrangement as a result of the associative search process. Never used for an associative search process, on the other hand, the signal value "1" calls on the row line. To carry out an associative _{search K 3} a signal "0" at the output of the NOR element 72 65 process, the addressing register 63 receives a control, and this signal "0" is the OR word in which, for example, the bits "1" specify element 82 and all of the bit positions of the associative memory connected to it in cascade which are to be transmitted to the further OR elements and to participate in the associative search process, ie, bits

that are to be compared with the search bits.

All bits "0" in this sleuerwort then designate the memory cells which are not involved in the associative search process participate roll. An essential feature of the described associative memory is that basically no bit position of any memory location by a hard wiring is set to contain only associative search bits. Such a restriction can apply to a ίο correct application can be carried out, but the structure allows the memory modules used basically a free choice in the way. that each memory cell in each memory location after May contain either an associative search bit or a data bit, each indicated by the Addressing lines / it is determined whether the stored bit is interpreted as a search bit or as a data bit will.

Finally, the memory of FIG. 2 also has an information register 64, to the outputs of which the information lines L ₁ to L _{q are} connected. This information register 64 forms the information input register for the memory and accordingly has q stages. The inputs of the information register 64 are coupled to the data processing system (not shown) to which the associative memory belongs. The information register 64 receives both the search bits for the associative searches and the data bits to be recorded. Bits contained in certain levels of the information register 64 are interpreted as associative search bits if the corresponding levels of the addressing register 63 contain the binary digit "1". The contents of the remaining levels of the information register 64, which correspond to levels of the addressing register 63 in which bits "0" are located. are interpreted as data bits if a write process is carried out.

The addressing register 63 can be used in various ways for controlling the memory will. The possible controls depend on the organization of the memory. For example, can each memory location have a special memory cell in which a bit is stored that is identified by its Binary value indicates the occupied status of the storage space. This flag defines whether the Storage space can be written with deletion of the previous content, or whether the storage space contains protected data that must not be deleted. One way of doing it of the associative search process then consists of searching for a memory location which, as a result of its Identification bits can be regarded as empty.

In this case, the addressing register 63 contains a single bit "1" in the level, that of the column of the memory is assigned, in which all the memory cells containing the identification bit are located; all other levels of the addressing register 63, however, contain bits "0". This defines that only one column of memory is subject to the associative search. If one also assumes that an identifier bit "0" indicates the occupied state and an identifier bit "1" indicates the free state of the memory location, a search bit "1" is entered in the corresponding level of the information register 64; the content of the remaining levels of the information register 64 is for the Associative search insignificant. Since, however, the search for an empty memory space is common is carried out for the purpose of a write operation, these remaining levels of the information register 64 contain the bits which are empty in the searched Storage space are to be written. These bits can be both data bits and address bits for associative searches.

The search process just described only searches for an empty memory location. After an empty memory location has been found, the write control circuit 61 is activated, whereby the in the remaining levels of the information register 64 Data are written into the memory location found.

If more than one free memory location is found, then priority logic circuit 60 determines if so it is activated so that the writing takes place only in the first empty memory location, while the others empty memory locations are blocked.

Since every associative search process is coupled with a read process, the reading line D appears which is assigned to the memory cells containing the identification bits, a "1" signal whenever at least one empty memory location has been found. The absence of this signal "1" indicates that no empty space was found by the associative search. Since in this case the write cannot be carried out, the data processing system must decide what is in this Case is to be done.

After finding the empty space and writing information into the space found, it is necessary to mark this space as "occupied". This can be done in the following way: After the writing process has been carried out, the information register 64 still contains the new address bits that have just been written into the memory location in certain stages. The corresponding levels of the address register / now receive the content "1", whereas the level of the addressing register 63 assigned to the identifier bit is reset to the state "0". The bit “0” is also placed in the level of the information register 64 corresponding to the identification bit. If a new associative search process with a subsequent write process is triggered, with only the write control line W corresponding to the identification bit being energized, it can be seen immediately that the identification bit "0 <· is written into the memory location found, whereby this memory location is marked as" occupied " .

The associative memory per se is not individually addressable at all, if not an external addressing is provided, which is not necessary in principle. The memory can be useful for commissioning be operated in the following manner: The priority logic circuit 60 is initially out of service set, all write control lines IV are energized, the address register 63 contains nothing but bits - »Ο«, and the information register 64 is inputted with a word corresponding to the flag bits Position contains a bit “1” and a bit “0” in all other positions. All line separations V are brought to the signal value »1«. As a result, the symbols in all memory locations > ·! * be enrolled, which means that the Storage locations are marked as "unoccupied",

while all remaining memory cells are erased. You can then write operations in the previously described manner are carried out in such a way that a free memory space is searched for. the

d dfü dß di

Priority logic circuit then ensures that the 5 bits are carried out.

free memory spaces are allocated one after the other. As soon as memory spaces are occupied, you can also Associative searches using the search functions that have now been written into the memory locations d

For this purpose 2 sheets of drawings

Claims (3)

Patent claims: 1. Associative memory with memory cells for one binary digit each, which are wired in rows and columns to form a matrix, each row comprising at least one memory location with several binary digits and the memory cells of the memory locations assigned to each other corresponding to digit positions in the same columns of the matrix, and Each memory cell contains a bistable memory element, a comparison circuit, a write gate circuit and a read gate circuit, with an information word register, to whose stage outputs liifor- mation lines are connected, which are each connected to the comparison circuits of all memory cells in a column in such a way that each comparison circuit has the Correspondence or non-agreement between the content of the associated memory element and the signal indicating the binary digit transmitted via the information line emits, with an addressing register, at the level outputs of which Adr Essierlinien are connected, which are connected to the control inputs of the comparison circuits of all memory cells lying in a column, with Zeüenlinien each connected to the outputs of the comparison circuits of the memory cells belonging to a memory location in such a way that they then and only one the match If there is a match in all the columns subject to the comparison, with read lines, which are each connected to the outputs of the encoder circuits of all memory cells in the same column, and with write control lines, each of which is connected to the control inputs of the write gate circuits of certain memory cells is. characterized in that the signal inputs of the write gate circuits (24, 25) of all memory cells (10) lying in a column are connected to the information line (L) assigned to this column, that each write control line (W) with the control inputs of the write gate circuits (24, 25) of all memory cells (10) lying in a column is connected, that a further control input of each writing gate circuit (24, 25) is connected to the associated row line () '), that the control input of each reading gate circuit (23) is connected to the associated line line ()') and that the voltage value on the row line (Y) indicating the correspondence acts as an unlocking signal for the connected reading gate circuits (23) and writing gate circuits (24, 25). 2. Associative memory according to Claim 1, characterized in that each addressing line (/) is connected to the write control line (W) belonging to the same column via a circuit (33.34) which excites the write control line (U) when the Addressing line (/) prevented. 3. Associative memory according to claim 1 or 2, in which a multiple response to the same associative search is regulated by a priority logic circuit which can be excited by a special program signal, characterized in that the priority logic circuit (60) is a cascade of locking circuits (70, 71 , 72, ...; 80, 81, 82, ...; 90, 91, 92, ...) which are enabled in a sequence one after the other by the program signal and a row line at each step of the sequence Enable ( Y) to accept the voltage value indicating the match and keep all other row lines (K) at a voltage value corresponding to the apparent mismatch.