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

 

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

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

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

РЕСПУБЛИК (51)5 G 11 С 15 00

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

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

0р. ьациаи атехььэс:х

mp

Рхр и ьхоа пыл

Фиг.1

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

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

ПРИ ГКНТ СССР (21) 4431522/24-24 (22) 15.04.88 (46) 23.08.90. Бюл. №, 31 (72) Г. П. Токмаков и В. М. Кильдюшев (53) 681.327 (088.8) (56) Авторское свидетельство СССР № 1174988, кл. G 11 С 15/00, 1983.

Авторское свидетельство СССР № 1501164, кл. G 11 С 15/00, 1987. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике и может быть использовано при построении ассоциативных запоÄÄSUÄÄ 1587586 А1 минающих устройств. Цель изобретения— повышение информационной емкости устройства и расширение его функциональных возможностей за счет обеспечения адресного поиска информационных последовательностей. Устройство содержит первый 1 и второй 4 регистры, компаратор 2, блок 3 памяти, счетчик и блок 6 управления. Устройство обеспечивает ассоциативный поиск информационных последовательностей произвольной длины и выдачу соответствующего кода как результат поиска, а также восстановление информационной последовательности по ее коду. 7 ил.

1587586

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

Цель изобретения — повышение ин- 5 формационной емкости устройства и расширение его функциональных возможностей за счет обеспечения адресного поиска информационных последовательностей.

На фиг. 1 представлена структурная схема ассоциативного запоминающего устройства; на фиг. 2 — структурная схема блока памяти; на фиг. 3 — структура размещения информации в узлах памяти блока памяти; на фиг. 4 и 5 — алгоритмы функционирования устройства; на 15 фиг. 6 и 7 — временные диаграммы процессов работы устройства.

Устройство (фиг. 1) содержит первый регистр 1, компаратор 2, блок 3 памяти, второй регистр 4, счетчик 5 и блок 6 управления.

На фиг. 1 приняты следующие обозначения: Х вЂ” X> — входные сигналы. (потенциальные или импульсные), Yi — Yl i — выходные сигналы (потенциальные или импульсные) .блока 6 управления. 25

Блок 3 памяти (фиг. 2) составлен из иерархически организованных узлов 3 памя2 ти (1=1, 2, ..., N; m=1, 2, ..., К, K val где 1 —; m — номер узла на соответствующем уровне иерархии; N— количество уровней иерархии, равное количеству элементов максимальной по длине последовательности плюс 1; К вЂ” количество узлов памяти на соответствующем уровне иерархии) . На первом уровне иерархии содержится один узел Зь каждой ячейке этого узла, кроме последней, соответствует узел памяти на втором уровне, в свою очередь каждой ячейке узлов памяти второго уровня, кроме последних, соответствует узел памяти на третьем уровне и т. д. до N-ro уровня. 40

Каждый узел памяти блока 3 содержит символьную, адресную и признаковую части, выходы которых подключены соответственно к первому, третьему и второму выходам блока 3, а адресные входы узлов памяти подключены к адресному входу 45 блока 3.

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

W 1а,а,...,а;,...,а„); — А;

i=1,...,Ò; j=l,...,P, где W — j-я последовательность; а; — элементы последовательности (буквы некоторого алфавита); ч — переменная величина, равная количеству элементов в 1-й последовательности (букв в j-м слове);

Т вЂ” количество всевозможных элементов последовательностей (количество букв некоторого алфавита);

Р— количество последовательностей, записанных в адресном накопителе;

А; — адрес-код j-й последовательности.

Кроме того, устройство позволяет осуществить поиск последовательности по соответствующему ей адресу-коду, т. е. устанавливает обратное соответствие:

А; - IW;=a, a>,..., а;,..., а„};

Функционирование устройства основано на иерархической организации последовательностей и соответствующем их размещении в иерархически организованных узлах памяти блока 3 (фиг. 3).

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

1 первого уровня в узле 3i памяти первого уровня выделяется по одной ячейке, где в символьной части записываются первые элементы этих подмножеств. Таким образом, получим массив первых элементов последовательностей, которые записаны в символьной части узла 3 памяти первого уровня.

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

Проводя, таким образом, разбиение подмножеств f-го уровня на группы подмножеств (+1)-ro уровня и запись в символьные и адресные части ячеек узлов памяти 1-го и (1+1)-го уровней соответствующих элементов последовательностей и адреса, получают иерархически организованную структуру последовательностей, размещенную в узлах памяти блока 3.

1587586

25 устройства: первый режим — поиск по последовательности соответствующего ей адреса-кода; второй режим — поиск по адресукоду соответствующей ему последовательности.

При включении устройства в работу счетчик 5 сбрасывается. Тактовые импульсы СИ, поступающие на вход «Синхронизация» устройства, синхронизируют работу устройства и состоят из двух полутактов: первый имеет «единичный» уровень, второй — «нулевой».

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

55

Для осуществления считывания по соответствующему ей адресу-коду в конце каждого узла выделяется ячейка памяти. В адресной части этой ячейки записывается адрес ячейки памяти предыдущего уровня, в адресной части которой содержится начальный адрес данного узла. Исключение составляет последняя ячейка узла памяти первого уровня, в символьной части которой записывается код конца последовательности.

Каждый узел памяти имеет признаковую часть, в которой записываются признаки, идентифицирующие содержимое ячеек памяти. Ячейки узлов памяти, в символьной и адресной частях которых находятся соответственно элемент и адрес перехода на следующий уровень иерархии, идентифицируются признаком А; ячейки, в адресной части которых находится адрес перехода на предыдущий уровень иерархии, идентифицируются признаком В, последняя ячейка узла 3i памяти первого уровня иерархии идентифицируется признаком С.

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

Устройство работает в двух режимах, которые задаются подачей соответствующего потенциального сигнала Хг на вход «Режим» нии последовательности выдаче на выход

«Адрес информационной последовательности» устройства соответствующий этой последовательности адрес-код (фиг. 4).

Предположим, что необходимо найти адрес-код Aj некоторой последовательности

W;=(ai, аг,..., а .);.

На первом этапе проводится цикл записи первого элемента а последовательности W На информационный вход устройста в сопровождении потенциального сигнала Хз поступает элемент ai. Во втором полутакте такта цикла записи блок 6 управления подает импульс Уз на вход записи регистра 1, по которому элемент ai записывается в регистр 1 и цикл записи заканчивается. Сигнал снимается (фиг. 6а).

На втором этапе проводится поиск элемента а в массиве первых элементов. На вход блока 6 управления поступает потенциальный сигнал У4, по которому блок 6 подает потенциальные сигналы чтения У4 и Ys на вхрды регистра 1 и блока 3 соответственно. Так как счетчик 5 сброшен, то он адресует нулевую ячейку узла 3i памяти. По наличию признака А на Хб и Хт из блока 6 управления во втором полутакте на управляющий вход компаратора 2 поступает импульс Ys, по которому проводится сравнение содержимого регистра

1 и символьной части ячейки узла 3 памяти. Если сравнения не произошло, то процедура повторяется и т. д. до момента, когда в очередном такте с выхода компаратора 2 на вход «Совпадение» блока 6 управления не поступит импульс Х сравнения, свидетельствующий о том, что в массиве первых элементов найден элемент ai (фиг. 66).

На следующем этапе осуществляется переход на второй уровень иерархии. При этом в адресной части ячейки, в символьной части которой записан определенный на предыдущем этапе элемент аь считывается адрес начала узла памяти второго уровня, в котором записаны все возможные элементы а, следующие за данным элементом а . Во втором полутакте первого такта этого этапа блок 6 выдает импульс 7 записи на вход регистра 2, по которому производится запись начального адреса узла памяти второго уровня в регистр 2. В следующем такте блок 6 управления выдает сигнал (8 чтения на вход регистра 2 и во втором полутакте этого такта — импульс Yio на вход счетчика 5, по которому производится установка счетчика 5 и он адресует первую ячейку одного из узлов памяти второго уровня (фиг. 6в).

Чтобы продолжить поиск, устройство запрашивает очередной элемент последовательности и ожидает очередной цикл записи (фиг. 6г).

В результате второго цикла записи в регистре 1 записан второй элемент а последовательности W Осуществляя поиск в массиве вторых элементов, следующих за а, находят второй элемент а> последовательности W. в узле памяти второго уровня и по адресу переходят на начало одного из узлов памяти третьего уровня.

Аналогичным образом находят остальные элементы последовательности W; в узлах памяти соответствующих уровней иерархии.

По окончании последовательности W;, т. е. после нахождения последнего элемента последовательности а„, осуществляется переход на следующий (У+1-й уровень иерархии— счетчик 5 адресует в первую ячейку одного из узлов памяти (V+1) -го уровня иерархии, а в результате очередного зап1587586

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

Яарес

Л иднак

4ааг. 2 роса и цикла записи в регистре 1 записан код конца последовательности. При

«просмотре» вы бра нного узла памяти (V+ 1)го уровня сравнения не произойдет и счетчик 5 по окончанию «просмотра» будет адресовать последнюю ячейку этого узла памяти, идентифицируемую признаком В, адрес которой и является искомым адресомкодом А; последовательности W (фиг. 6е): блок 6 управления, получив сигналы Х6 и Х7 кода признака В, снимает сигналы чтения У4 и Y и выставляет на управляющем выходе «Вывод» устройства потенциальный сигнал У2, свидетельствующий, что на выходе «Адрес информационной последовательности» устройства находится искомый адрес- код.

Работа устройства во втором режиме заключается в поиске элементов искомой последовательности на соответствующих уровнях иерархии по известному адресукоду этой последовательности (фиг. 5).

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

«Признак поиска» блока управления, выход второго регистра подключен к информационному входу счетчика, выход которого соединен с адресным входом блока памяти, входы «Синхронизация», «Режим», «Запись» и «Поиск» блока управления являются одноименными входами устройства, первый и второй выходы блока управления являются соответственно выходами «Запрос» и «Вывод» устройства, третий и четвертый выходы блока управления соединены соответственно с входами записи и чтения первого регистра, пятый и шестой выходы блока памяти подключены .соответственно к управляющему входу компаратора и входу записи-чтения блока памяти, седьмой и восьмой выходы блока управления соединены соответственно с входами записи и чтения

)5 второго регистра, девятый, десятый и одиннадцатый выходы блока управления соединены соответственно с входом сброса, входом установки в «1» и счетным входом счетчика, выход компаратора подключен к входу «Совпадение» блока управления, отличаюи ееся тем, что, с целью повышения информационной емкости устройства и расширения его функциональных возможностей за счет обеспечения адресного поиска информационных последовательностей, в нем

25 третий выход блока памяти подключен к информационному входу второго регистра, выход счетчика является выходом «Адрес информационной последовательности» устройства, информационный вход счетчика является адресным входом устройства, первый выход блока памяти и информационный вход первого регистра являются соответственно информационным выходом и информационным входом устройства.!

587586

1урпбень г удЬ

Здродеиь

Фураже,чь

1587586

Фиг.) 1587586

1587586

Составитель B. Рудаков

Редактор Е. Папп Техред А. Кравчук Корректор Н. Ренская

Заказ 2424 Тираж 485 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытия lI при ГКНТ СССР ! l3О35, Москва, Ж вЂ” 35, Раушская наб., д, 415

Производственно-издательский комбинат «Патент», г. Ужгород, ул. Гагарина, !О!