Ассоциативное запоминающее устройство Советский патент 1989 года по МПК G11C15/00 

Изобретение относится к вычислительной технике и может быть использовано в качестве ассоциативных запоминающих устройств (ЗУ) в системах, где необходимо вести ассоциативный поиск по произвольному числу признаков .

Цель изобретения - расширение

05954

Однако массивы А и В хранятся в этой памяти безадресным способом, так как элемент этих массивов принял участие в образовании нескольких элементов массива С, т.е. распределен по всему объему некоторой части С, или массив В заполнен в массиве С по адресу А, Считьшание массива (восстановление)

Изобретение относится к вычислительной технике и может быть использовано в качестве ассоциативных запоминающих устройств в системах, где необходимо вести ассоциативный поиск по произвольному числу признаков. Цель изобретения - расширение функциональных возможностей за счет обеспечения поиска информации, близкой по содержанию к входной информации. Устройство содержит матричный накопитель 1, состоящий из элементов 2 памяти, сумматоры 3 и регистры 4. 2 ил.

функциональных возможностей устройст- . представляет собой не вызов по адре15

20

ва за счет обеспечения поиска информации, близкой по содержанию входной информации.

На фиг. 1 изображена структурная схема ассрциативного запоминающего устройства; на фиг. 2 - структурная схема элемента памяти.

Устройство содержит (фиг. 1) матричный накопитель 1 тЧп (где m - число строк; п - число столбцов матрицы), состоящий из элементов 2 памяти, сумматоры 3 - по числу столбцов регистры 4 - по числу столбцов, первую информационную шину 5, объединяющую информационные входы и выходы устрой- 25 ства, вторую информационную шину 6, объединяющую признаковые входы устройства, шины разрешения записи 7, разрешения чтения 8, шину 9 сброса, выходные шины 10, установочный вход II, , вход 12 приема и установочный вход 13.

Каждый элемент 2 памяти содержит (фиг. 2) блок 14 сравнения, элементы И 15 и 16, элементы НЕ 17 и 18, реверсивный счетчик 19, группу элементов НЕ 20 и мультиплексор 2J.

В устройстве осуществляется ассоциативная безадресная обработка.

Математическая модель ассоциативной безадресной обработки заключается в следующем. Входная информация - массив А, выходная информация - В. Массивы А, Б - наборы чисел tl. Пусть А - вектор-столбец, В - вектор-строка:

(х); (у).1, ()

где , 2m;

, 2п.

В память необходимо записать соответствие входному массиву А выходного массива В. Результатом такого соответствия является массив-матрица С, причем элементы С - произведения соответствующих элементов входного и выходного массивов.

С(х,у)а(х)-Ь(у). (2)

Массив С хранится в памяти адресным способом, т.е. каждому его элементу отводится отдельная ячейка.

40

50

55

су, а цепь преобразований. Пусть существует массив

)7; (3)

С;(4)

где А - вектор-строка, транспортированный вектор А.

Л(У) Г, С(х,у).а(х). (5) Подставив в (5) выражение (2), получают„,

Л(У)- Zs/(x)-b(y).

(6)

Так как элементы массива А единицы

2,

С разными знаками, то число а единица. Поэтому

/З(У)М.Ь(У), й М-Ь

-X есть

т.е,

(7) (8)

Формула (7) показьшает, что элемен ты массива р- целые числа М с разным знаками, причем для массивов 9 и В эле менты, имеющие одинаковые номера, име ют и одинаковые знаки, Поэтому

Ь(у) (y)

-1,

если (б(у)О;

0,если /i(y)0j

1,если /}(у)0.

Пусть имеется К пар

Ац, В (,.. . ,К) . Все массивы А по размерам такие же, как А, а все массивы В такие же, как Б. Тогда массив С формируется таким образом

С- I Ск- Z АК-В;. (10)

К«

Восстановим массив /ь,

45 ,З, С,)А:(С,,) С;+А :;(|: - c,)M B,-fW,,

где W - массив помехи.

Если выбрать массив А таким образом, чтобы М было четно и количество элементов любой пары массивов А и AI с разными знаками (кодовое расстояние .по Хеммингу) равны 1/2, то все элементы массива W станут равны 0(k ,2,.. .,К; ,2,...,К; ) .

Массив С устанавливает соответствие между множествами кодов А и В.

су, а цепь преобразований. Пусть существует массив

)7; (3)

С;(4)

где А - вектор-строка, транспортиро, ванный вектор А.

Л(У) Г, С(х,у).а(х). (5) Подставив в (5) выражение (2), получают„,

Л(У)- Zs/(x)-b(y).

(6)

Так как элементы массива А единицы

2,

С разными знаками, то число а единица. Поэтому

/З(У)М.Ь(У), й М-Ь

-X есть

т.е,

(7) (8)

Формула (7) показьшает, что элементы массива р- целые числа М с разными знаками, причем для массивов 9 и В элементы, имеющие одинаковые номера, имеют и одинаковые знаки, Поэтому

(y)

-1,

если (б(у)О;

0,если /i(y)0j

1,если /}(у)0.

(9)

Пусть имеется К пар

Ац, В (,.. . ,К) . Все массивы А по размерам такие же, как А, а все массивы В такие же, как Б. Тогда массив С формируется таким образом

С- I Ск- Z АК-В;. (10)

К«

Восстановим массив /ь,

,З, С,)А:(С,,) С;+А :;(|: - c,)M B,-fW,,

где W - массив помехи.

Если выбрать массив А таким образом, чтобы М было четно и количество элементов любой пары массивов А и AI с разными знаками (кодовое расстояние .по Хеммингу) равны 1/2, то все элементы массива W станут равны 0(k ,2,.. .,К; ,2,...,К; ) .

Массив С устанавливает соответствие между множествами кодов А и В.

Такое cooTBercTBvie существует при обучении массива С на любое количество пар. При изменении количества пар изменяется и соответствие, его содержание.

Ассоциативное г апоминающее устройство работает следующим образом.

Предусмотрено два режима работы: Запись и Чтение.

В режиме Запись (Обучение). Перед началом-работы необходимо обнулить каждый счетчик 19, для этого на шину 9 поступает отрицательный импульс.

На шине 5 выставляется п-разрядное слово, соответствующее вектору 9 На шине 6 выставляется т-разрядное слово соответствующее вектору А. Каждый i-й разряд слова А посредством блока 14 сравнения сравнивается с j-м разрядом слова ft(,n; ,m). Положительный импульс по шине 7 разрешения записи поступает на соответствующие входы всех элементов 2 памяти. Если сравниваемые сигналы противоположны, то на выходе элемента И 16 устанавливается низкий уровень, а на выходе элемента НЕ 18 - высокий уровень, че

рез элемент И 15 проходит положитель- 30 ствии с тем, инфор мация какого из

ный импульс, который, инвертируясь- на элементе НЕ 17, возбуждает первый счетный вход счетчика 19, при этом происходит обратный счет.

1

Если сравниваемые сигналы одинаковы, то аналогично посредством элементов И 15 и НЕ 17 на первом счетном входе счетчика 19 устанавливается высокий уровень, а на второй счетный вход приходит отрицательный импульс, при этом происходит прямой счет; Запись и накопление информации производятся в каждом счетчике 19 элемента 2 памяти. Содержание всех счетчиков 19 элементов 2 памяти матричного накопителя 1 соответствует матрице С.

Таким образом происходит обучение

на одну пару слов. Если таких пар К,

элементов 2 памяти участвует в процес се суммирования. На Р-вход каждого сумматора 3 поступает через шину 10 тот разряд числа А, который соответ35 ствует строке матричного накопителя 1. По завершении процесса суммирования на выходах знаковых разрядов регистров 4 формируется искомое выходное число В. Число В устанавлива40 ется на шине 5.

Формула изобретения

5 Ассоциативное запоминающее устройство, содержащее матричный накопитель, состоящий из. элементов памяти, причем информационные входы элементов памяти каждого столбца матричто подобную процедуру повторяют после- но го накопителя объединены и являются довательно К раз.соответствующим информационным входом устройства, входы разрешения записи элементов памяти каждой строки

матричного накопителя объединены и

При этом емкость счетчика соответствует количеству обучаемых пар, причем старший разряд должен быть знаковым. При необходимости можно увели- являются соответствующим входом раз- чить разрядность счетчика, используя решения записи устройства, входы раз- при этом выходы прямого и обратного решения чтения элементов йамяти иаж- переносов.дои строки матричного накопителя объ10

15

, 0595

В режиме Чтение (Восстановление) перед начшюм работы регистры 4 устанавливаются в исходное состояние .

На шине 6 выставляется т-разряднс е. слово А. В каждый элемент 2 памяти поступает сигнал, соответствующий одному из разрядов слова А. Этот же сигнал поступает на адресный вход мультиплексора 21. Если открьшает- ся первый канал, то выходная шина 10 подключается к выходам элементов НЕ 20, если открывается второй канал, то выходная шина 10 подключается к выходам счетчика 19. Элементы 2 памяти, входящие в столбец матричного накопителя 1, имеют единую выходную шину 10. Суммирование числа,

20 поступающего по выходной шине 10, и числа, находящегося в регистре 4, производится при поступлении сигнала записи на вход 12 приема. Суммирование производится m раз, оно происхо25 дит параллельно по столбцам и последовательно по строкам матричного накопителя 1. При этом линии, составляющие шину 8 разрешения чтения, возбуждаются последовательно в соответэлементов 2 памяти участвует в процесе суммирования. На Р-вход каждого сумматора 3 поступает через шину 10 тот разряд числа А, который соответ35 ствует строке матричного накопителя 1. По завершении процесса суммирования на выходах знаковых разрядов регистров 4 формируется искомое выходное число В. Число В устанавлива40 ется на шине 5.

Формула изобретения

5 Ассоциативное запоминающее устройство, содержащее матричный накопитель, состоящий из. элементов памяти, причем информационные входы элементов памяти каждого столбца матричматричного накопителя объединены и

являются соответствующим входом раз решения записи устройства, входы ра решения чтения элементов йамяти иаж дои строки матричного накопителя об

единены и являются соответствующим входом разрешения чтения устройства, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет обеспечения поиска информации близкой по содержанию к входной информации, в него введены сумматоры и регистры, причем информационные входы каждого регистра подключены к выходам соответствующего сумматора, входы приема регистров.объединены и являются одноименным входом устройства, установочные входы регистров объединены и являются первым установочным входом устройства,.выходы знаковых разрядов регистров являются информационными выходами устройства, выходы инфорРедактор О. Головач

Составитель В, Рудаков

Техред Л.Сердюкова Корректор. Н, Король

Заказ 6765/54

Тираж 558

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. А/5

мациопных разрядов каждого регистра подключены к информационным входам первой группы соответствующего сумматора, одноименные выходы элементов памяти каждого столбца матричного накопителя объединены и подключены к соответствующим входам второй группы соответствующего сумматора, признаковые входы элементов памяти каждой строки матричного накопителя о&единены и .являются соответствующим признаковым входом устройства, входы сброса элементов памяти каждой строки матричного накопителя объединены и являются соответствующим входом сброса устройства, установочные входы элементов памяти объединены и являются вторым установочным входом устройства.

Подписное