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

Алек с андро ство СССР/00, 1984,ИНАЮЩЕЕ етел Р 1 етельс 11 С 1 Е ЗАПОИ к вычи носи ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(57) Изобретение лительной технике и может быть использовано в качестве ассоциативныхзапоминающих устройств в системах,где необходимо вести ассоциативныйпоиск по произвольному числу признаков, Цель изобретения - расширениефункциональных возможностей за счетобеспечения поиска информации, близкой по содержанию к входной информа-.:ции. Устройство содержит матричныйнакопитель 1, состоящий из элементов2 памяти, сумматоры 3 и регистры 4,2 илИзобретение относится к вычислительной технике и может быть использовано в качестве ассоциативных запоминающих устройств (ЗУ) в системах,где необходимо вести ассоциативныйпоиск по произвольному числу признаков,Цель изобретения - расширениефункциональных возможностей устройст- Ова за счет обеспечения поиска информации, близкой по содержанию входнойинформации.На фиг. 1 изображена структурнаясхема ассоциативного запоминающегоустройства; на фиг, 2 - структурнаясхема элемента памяти,Устройство содержит (фиг, 1) матричный накопитель 1 шип (где ш -число строк; и - число столбцов матрицы), состоящий иэ элементов 2 памя-ти, сумматоры 3 - по числу столбцоврегистры 4 - по числу столбцов, первуюинформационную шину 5, объединяющуюинформационные входы и выходы устройства, вторую информационную шину бобъединяющую признаковые входы устройства, шины разрешения записи 7, разрешения чтения 8, шину 9 сброса, выходные шины 10, установочный вход 11,вход 12 приема и установочный вход 13,Каждый элемент 2 памяти содержит(фиг, 2) блок 14 сравнения, элементыИ 5 и 16, элементы НЕ 17 и 18, реверсивный счетчик 19, группу элементовНЕ 20 и мультиплексор 21,35В устройс тв е осуществляется ассоциативная безадресная обработка.Математическая модель ассоциативной безадресной обработки заключается40в следующем, Входная информациямассив А, выходная информация . - В,Массивы А, В - наборы чисел + 1. ПустьА - вектор-столбец, В - вектор-строка.т 45А=Га(х); В=Ь(У)1,где х, 2 ш;у 1, 2, , и.В память необходимо записать соответствие входному массиву А выход -ного массива В. Результатом такогосоответствия является массив-матрица С, причем элементы С - произведения соответствующих элементов входного и выходного массивовС(х,у) =а(х) Ь. (2)Массив С хранится в памяти адресным способом, т.е, каждому его элементу отводится отдельная ячейка,Однако массивы А и В хранятся в этой памяти безадресным способом, так как элемент этих массивов принял участие в образовании нескольких элементов массива С, т,е, распределен по всему объему некоторой части С, или массив В заполнен в массиве С по адресу А. Считывание массива (восстановление) представляет собой не вызов по адресу, а цепь преобразований. Пусть существует массив а = ГР(у)7; (3) /3 =А С; (4) т где А - вектор-строка, транспортиро-,ванный вектор А.р (у) , С(х,у)а(х). (5)Подставив в (5) выражение (2), получают р(у)а (х) Ъ(у). (б)Х 1Так как элементы массива А единицы с разными знаками, то число ах есть единица, Поэтомур(у)-М Ь(у), (7) т.е. рт -М Ь. (8)Формула (7) показывает, что элементы массива- целые числа М с разными знаками, причем для массивов аи В элементы, имеющие одинаковые номера, имеют и одинаковые знаки. Поэтому- 1, если р(у)(0; Ь (У) 818 п Р(УИ О, если /ъ (У) 0 (9)1, если /3(У 0Пусть имеется К пар А, В(К=1,К). Все массивы Апо размерам такие же, как А, а все массивы Вк такие же, как В, Тогда массив С формируется таким образомк С ", Ск",. А 1,В (10)Кс 1 КсВосстановим массив р 1к 31=АС=А, ( с. С)=А,(С,+ 2 С)=т . т =А, С+А(, С)=М В 1+1,,Ксг где 11, - массив помехи,Если выбрать массив Атаким образом чтобы М было четно и количество элементов любой пары массивов Аи А с разными знаками (кодовое расстояние по Хеммингу) равны 1/2, то все элементы массивастанут равны О(1 с=1 ю 2 ф,К;1 ф 2К; 1.фК).Массив С устанавливает соответствие между множествами кодов А и В,1520595 25 Такое соответствие существует при обучении массива С на любое количество пар. При изменении количества пар изменяется и соответствие, его содержание.Ассоциативное запоминающее устройство работает следующим образом,Предусмотрено два режима работы: "Запись и ЧтениеВ режиме "Запись" (" Обучение" ). Перед началом работы необходимо обнулить каждый счетчик 19, для этого на шину 9 поступает отрицательный импульс. 15На шине 5 выставляется и-разрядное слово, соответствующее вектору ф, На шине 6 выставляется ш-разрядное слово, соответствующее вектору А, Каждый 1. - й разряд слова А посредством блока 20 14 сравнения сравнивается с 1-м разрядом слова р(=1,п; д=д,ш). Положительный импульс по шине 7 разрешения записи поступает на соответствующие входы всех элементов 2 памяти, Если сравниваемые сигналы противоположны,то ча выходе элемента И 16 устанавливается низкий уровень, а на выходеэлемента НЕ 18 - высокий уровень, через элемент И 15 проходит положительный импульс, который, инвертируясь,на элементе НЕ 17, возбуждает первыйсчетный вход счетчика 19, при этомпроисходит обратный счет,35Если сравниваемые сигналы одинаковы, то аналогично посредством элементов И 15 и НЕ 17 на первом счетном входе счетчика 19 устанавливается высокий уровень, а на второй счетный 40 вход приходит отрицательный импульс, при этом происходит прямой счет. Запись и накопление информации производятся в каждом счетчике 19 элемента 2 памяти. Содержание всех счетчиков 45 19 элементов 2 памяти матричного накопителя 1 соответствует матрице С.Таким образом происходит обучение на одну пару слов, Если таких пар К, то подобную процедуру повторяют последовательно К раз.При этом емкость счетчика соответствует количеству обучаемых пар, причем старший разряд должен быть знаковым, При необходимости можно увели чить разрядность счетчика, используя при этом выходы прямого и обратного переносов. В режиме Чтение (Восстановление") перед началом работы регистрыустанавливаются в исходное состояние.На шине 6 выставляется щ-разрядное слово А. В каждый элемент 2 памяти поступает сигнал, соответствующий одному из разрядов слова А. Этот же сигнал поступает на адресный вход мультиплексора 21. Если открывается первый канал, то выходная шина 10 подключается к выходам элементов НЕ 20, если открывается второй ка - нал, то выходная шина 10 подключается к выходам счетчика 19. Элементы 2 памяти, входящие в столбец матричного накопителя 1, имеют единую выходную шину 1 О. Суммирование числа, поступающего по выходной шине 10, и числа, находящегося в регистре 4, производится при поступлении сигнала записи на вход 12 приема. Суммирование производится ш раз, оно происхо - дит параллельно по столбцам и последовательно по строкам матричного накопителя 1, При этом линии, составляющие шину 8 разрешения чтения, возбуждаются последовательно в соответствии с тем, информация какого из элементов 2 памяти участвует в процессе суммирования. На Р-вход каждого сумматора 3 поступает через шину 10 тот разряд числа А, который соответствует строке матричного накопителя 1, По завершении процесса суммирования на выходах знаковых разрядов регистров 4 формируется искомое выходное число В. Число В устанавливается на шине 5Формула изобретения Ассоциативное запоминающее устройство, содержащее матричный накопитель, состоящий из. элментов памяти, причем информационные входы элементов памяти каждого столбца матричного накопителя объединены и являются соответствующим информационным входом устройства, входы разрешения записи элементов памяти каждой строки матричного накопителя объединены и являются соответствующим входом разрешения записи устройства, входы раэрешения чтения элементов памяти;.;аждой строки матричного накопителя объ1520595 20 Составитель В, РудакРедактор О, Головач Техред Л.Сердюкова Коррек оль Заказ 6765/5 Тираж 558 дписное НИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 113035, Иосква, Ж, Раущская наб., д. 4/5роиэводственно-издательский комбинат Патент", г.уж ул. Гагарина, 1 О единены и являются соответствующимвходом разрешения чтения устройства,о т л и ч а ю щ е е с я тем, что,с целью расширения функциональныхвоэможностей устройства эа счет обеспечения поиска информацииблизкойпа содержанию к входной информации,в него введены сумматоры и регистры,причем информационные входы каждогорегистра подключены к выходам соответствующего сумматора, входы приемарегистров, объединены н являются одноименным входом устройства, установочные входы регистров объединены иявляются первым установочным входомустройства,.выходы знаковых разрядоврегистров являются информационнымивыходами устройства, выходы информационных разрядов каждого регистраподключены к информационным входампервой группы соответствующего сумматора, одноименные выходы элементовпамяти каждого столбца матричногонакопителя объединены и подключенык соответствующим входам второйгруппы соответствующего сумматора,приэнаковые входы элементов памятикаждой строки матричного накопителяо бьединены и являются соответствующимпризнаковым входом устройства, входысброса элементов памяти каждой строкиматричного накопителя объединены иявляются соответствующим входом сброса устройства, установочные входы элементов памяти объединены и являютсявторым установочным входом устройства.