Introduction

Recently I remembered how about a year ago a comrade told me about an associative memory . I remember then I was not particularly interested, and now for some reason I decided to play around, since the thing is quite interesting.

Theory

Associative memory, ABC (eng. Associative memory, content-addressable memory, CAM) is a type of memory in which addressing is based on the content of the data, rather than their location, thus speeding up the search for the necessary records (Wikipedia entry - Free Encyclopedia).

AZS are useful and needed for hardware accelerated searches. After all, any search task in the final result is reduced to finding the address of a memory cell (to speed up this process, data is sorted, indexes are created, etc.).

Logically, the CAM can be implemented using a neural network with feedback (for example). Such a neural network will give us the necessary data if we input part of the data to it, or noisy data (used for text recognition).

Below I want to give an example of a slightly different approach.

Practice

So, let's say we need to match two sequences of bits (let's take 4-bit numbers for simplicity):

1101> 1000

1001> 1100

')

We build a matrix for each correspondence:

The method of construction is extremely simple. The left column is the first value, the bottom line is the match. At intersections, we perform a logical AND operation on the current bits.





Now combine the matrices with the operation OR (Rezult [i, j] = A1 [i, j] OR A2 [i, j]).





This associative matrix (AM) stores our two matches, 1101> 1000 and 1001> 1100.



Now retrieve the data. For example, we need to find what corresponds to 1001.

Write 1001 to the left of AM, and logically multiply the resulting column by each AM column.

In the resulting matrix, sum up the columns and write the results in the bottom row.



In the received line (2200) we find the largest number (in our example it will be 2) and in the corresponding bits we write 1, and in the rest - 0. Thus, we got the number 1100. It is this value that we recorded in the matrix.

You can also get the inverse match, if 1100 is written down below and multiplied by each row, then by analogy we find the original match in the column.

Opportunities

In the examples above, we worked with four-bit numbers. But the most interesting thing is that this approach can be implemented as an N-dimensional matrix and store (N-1) dimensional data. For example, you can make a 3-dimensional matrix, which will remember the correspondence of 2-dimensional black and white pictures. And most importantly, such matrices are easy to implement in hardware.

disadvantages

The main disadvantage is the low memory capacity of the matrix. If 5–6 matches are written into our matrix, the system will start to get confused and give incorrect values.

It is also impossible to write matches in which all zeros or ones (in our case, 1111 and 0000).

Conclusion

In general, the thing is almost useless, but quite interesting :)