Ассоциативное запоминающее устройство

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (51) 4 G 11 С 15/ОО

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (2l) 4379454/24-24 (22) 15,02,88 (46) 07.11.89, Бюл, ¹ 41 (72) В.Н. Быстров и Л.К. Александрова (53) 681.327(088.8) (56) Авторское свидетельство СССР № 1322292, кл. G 06 F 12/00, 1985.

Авторское свидетельство СССР № 1277210, кл. G 11 С 15/00, 1984. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ

УСТРОЙСТВО (57) Изобретение относится к вычис„„SU„„1520595 А1

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

2 памяти, сумматоры 3 и регистры 4.2 ил.

1520595

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

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

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

Каждый элемент 2 памяти содержит (фиг, 2) блок 14 сравнения, элементы

И !5 и 16, элементы НЕ 17 и 18, реверсивный счетчик 19, группу элементов

НЕ 20 и мультиплексор 21.

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

Математическая модель ассоциативной безадресной обработки заключается

40 в следующем, Входная информация массив А, выходная информация . — В, Массивы А,  — наборы чисел + 1. Пусть

A — - вектор-столбец,  — вектор-строка.

A=(a(x)J; В =(Ь(У)1 (1) где xl, 2, ..., m, у 1, 2, ..., n.

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

С(х,у) =а (х) . Ь (l(). (2)

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

В заполнен в массиве С по адресу А.

Считывание массива (восстановление) представляет собой не вызов по адресу, а цепь преобразований.

Пусть существует массив

p = ГР(у)7 (3) р =А С; (4) т где А — вектор-строка, транспортиро-, ванный вектор A.

Ill

p (у) - ?, С (х, у) ° а (х) . (5)

Подставив в (5) выражение (2), получают р (у) а (х). Ъ(у). (6)

Х 1

Так как элементы массива А единицы с разными знаками, то число а х есть единица.

Поэтому в (у)-м ь(у), (7) т,е. IS -М Ь . (8)

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

Поэтому — 1, если р(y)c0

О, если р (у) =О; (9)

1, если р(у))0.

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

А„, В„(К=I,...,К). Все массивы А„по размерам такие же, как А, а все массивы В такие же, как В, Тогда массив

С формируется таким образом

k к

С с . Ск - A„(10) к- к. °

Восстановим массив р, к

I3, =A„C=A,(:Е С„)=A,(C,+ 2 с„)= т

=A, С„+A„(Е - С„)=М.В +y ,к=г

rpe 11, — массив помехи.

Если выбрать массив А „ таким образом„ чтобы М было четно и количество элементов любой пары массивов

А „ и AI с разными знаками (кодовое расстояние по Хеммингу) равны 1/2, то все элементы массива Ъ станут равны

0(k=I,2ý...,K; i I,2,...,К; 1фК) .

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

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

Ассоциативное запоминающее устройство работает следующим образом, Предусмотрено два режима работы:

"Запись и Чтение „

В режиме "Запись" (" Обучение" ).

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

На шине 5 выставляется и-разрядное слово, соответствующее вектору ф, На шине 6 выставляется m-разрядное слово, соответствующее вектору А. Каждый

i — и разряд слова А посредством блока 20

14 сравнения сравнивается с 1-м разрядом слова p (j = l, n; i=i, m) . Положительный импульс по шине 7 разрешения записи поступает на соответствующие входы всех элементов 2 памяти. Если

25 сравниваемые сигналы противоположны, то ча выходе элемента И 16 устанавливается низкий уровень, а на выходе элемента НЕ 18 — высокий уровень, через элемент И 15 проходит положитель- 30 ный импульс, который, инвертируясь. на элементе HE 17, возбуждает первый счетный вход счетчика 19, при этом происходит обратный счет.

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

2 памяти. Содержание всех счетчиков 45

19 элементов 2 памяти матричного накопителя 1 соответствует матрице С.

Таким образом происходит обучение на одну пару слов. Если таких пар К, то подобную процедуру повторяют последовательно К раз.

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

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

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

НЕ 20, если открывается второй ка— нал, то выходная шина 10 подключается к выходам счетчика 19. Элементы

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

1. По завершении процесса суммирования на выходах знаковых разрядов регистров 4 формируется искомое выходное число В. Число В устанавливается на шине 5 °

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

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

1

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

Редактор О. Головач Техред JI.Ñåðäþêoâà Корректор Н ° Король

Заказ 6765/54 Тираж 558 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Иосква, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r.Óæãîðîä, ул. Гагарина, 101 единены и являются соответствующим входом разрешения чтения устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей устройства эа счет обеспечения поиска информации близкой па содержанию к входной информации, в него введены сумматоры и регистры, причем информационные входы каждого регистра подключены к выходам соответствующего сумматора, входы приема регистров, объединены н являются одноименным входом устройства, установочные входы регистров объединены и являются первым установочным входом устройства,.выходы знаковых разрядов регистров являются информационными выходами устройства, выходы информационных разрядов каждого регистра подключены к информационным входам первой группы соответствующего сумматора, одноименные выходы элементов памяти каждого столбца матричного накопителя объединены и подключены к соответствующим входам второй группы соответствующего сумматора, приэнаковые входы элементов памяти каждой строки матричного накопителя о бьединены и являются соответствующим признаковым входом устройства, входы сброса элементов памяти каждой строки матричного накопителя объединены и являются соответствующим входом сброса устройства, установочные входы элементов памяти объединены и являются вторым установочным входом устройства.