Введение
Недавно вспомнил, как около года назад товарищ мне рассказывал про ассоциативную память. Помню тогда меня это не особо заинтересовало и сейчас почему то решил поиграться, так как штука довольно интересная.
Теория
Ассоциативное ЗУ, АЗУ (англ. associative memory, content-addressable memory, CAM) — вид памяти, в котором адресация осуществляется на основе содержания данных, а не их местоположения, чем обеспечивается ускорение поиска необходимых записей (Материал из Википедии — свободной энциклопедии).
АЗУ полезны и нужны для аппаратного ускорения поиска. Ведь любая задача поиска в конечном результате сводится к нахождению адреса ячейки памяти (для ускорения этого процесса данные сортируют, создают индексы и т.д.).
Логически АЗУ можно реализовать с помощью нейронной сети с обратной связью (например ). Такая нейронная сеть будет выдавать нам нужные данные если на вход ей подать часть данных, либо зашумленные данные (используют для распознавания текстов).
Ниже хочу привести пример немного другого подхода.
Практика
Итак, допустим нам нужно поставить в соответствие две последовательности бит (возьмем 4-х разрядные числа для простоты):
1101 > 1000
1001 > 1100
Строим для каждого соответствия матрицу:
Метод построения предельно прост. Левый столбец — это первое значение, нижняя строка — это соответствие. На пересечениях мы выполняем логическую операцию AND текущих битов.
Теперь объединим матрицы операцией OR (Rezult[i, j] = A1[i, j] OR A2[i, j]).
Эта ассоциативная матрица(АМ) хранит наши два соответствия 1101 > 1000 и 1001 > 1100.
Теперь извлечем данные. Например, нам нужно найти чему соответствует 1001.
Запишем 1001 слева от АМ, и логически умножим получившийся столбец на каждый столбец АМ.
В полученной матрице, просуммируем столбцы и запишем результаты в нижней строке.
В полученной строке (2200) найдем наибольшее число (в нашем примере это будет 2) и в соответствующих битах запишем 1, а в остальных — 0. Таким образом получили число 1100. Именно это значение мы и записывали в матрицу.
Также можно получить обратное соответствие, если 1100 записать снизу и умножить на каждую строку, то по аналогии найдем в столбце исходное соответствие.
Возможности
В примерах выше, мы работали с четырехбитными числами. Но самое интересное то, что данный подход можно реализовать в виде N-мерной матрицы и хранить (N-1) мерные данные. Например можно сделать 3-х мерную матрицу, которая будет помнить соответствия 2-х мерных черно-белых картинок. И самое главное — такие матрицы легко реализовать в железе.
Недостатки
Самый главный недостаток — это низкий объем памяти матрицы. Если в нашу матрицу записать штук 5–6 соответствий, то система начнет путаться и выдавать неверные значения.
Также нельзя записать соответствия в которых все нули или единицы (в нашем случае 1111 и 0000).
Вывод
В общем, штука практически бесполезная, но довольно интересная:)
