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

Запись

Реми

(Л

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

Х-1 К X Xl/ V;

Yj Y« XjYsYj/sXj Yj Yg Y, У,о Y,,

Инсрормационныи Зход

Инсрормацион 7

IZ

ны: / выход

ASpec инфор. ной последо8атель.

Адресный 8хо)

сд

00

01

00

05

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

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

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

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

На фиг. 1 приняты следующие обозначения: Х|-Х/ - входные сигналы, (потенциальные или импульсные), YI -YI : - выходные сигналы (потенциальные или импульс ные).блока 6 управления.

Блок 3 памяти (фиг. 2) составлен из иерархически организованных узлов 3 памяти (1 1, 2, ..., N; , 2, ..., Кг; где I - уровень иерархии; ш - номер узла на соответствующем уровне иерархии; N - количество уровней иерархии, равное количеству элементов максимальной по длине последовательности плюс 1; К - количество узлов памяти на соответствующем уровне иерархии). На первом уровне иерархии содержится один узел 31, каждой ячейке этого узла, кроме последней, соответствует узел памяти на втором уровне, в свою очередь каждой ячейке узлов памяти второго уровня, кроме последних, соответствует узел памяти на третьем уровне и т. Д: до N-ro уровня.

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

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

U7,{ai, а2 а,-,, ..., а,)/ - А/

,...,T; ,...,P,

20

5

.Q 15

25

45

30

35

40

50

5

где W- j-я последовательность;

а/ - элементы последовательности (буквы некоторого алфавита); V - переменная величина, равная, количеству элементов в j-й последовательности (букв в J-M слове); Т - количество всевозможных элементов последовательностей (количество букв некоторого алфавита); Р - количество последовательностей, записанных в адресном накопителе; А;-адрес-код j-й последовательности. Кроме того, устройство позволяет осуществить поиск последовательности по соответствующему ей адресу-коду, т. е. устанавливает обратное соответствие:

, ад,..., а/,..., а )/.

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

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

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

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

записывается код конца последовательности.

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

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

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

коду соответствующей ему последовательное- ти.

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

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

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

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

0

5

5

n

5

0 5

0 g

На втором этапе проводится поиск элемента О в массиве первых элементов. На вход блока б управления поступает потенциальный сигнал Y4, по которому блок б подает потенциальные сигналы чтения 4 и Ye на вхрды регистра 1 и блока 3 соответственно. Так как счетчик 5 сброшен, то он адресует нулевую ячейку узла 31 памяти. По наличию признака Л на Хе и Х из блока б управления во втором полутакте на управляющий вход компаратора 2 поступает импульс Ys, по которому проводится сравнение содержимого регистра 1 и символьной части ячейки узла 3 памяти. Если сравнения не произошло, то процедура повторяется и т. д. до момента, когда в очередном такте с выхода компаратора 2 на вход «Совпадение блока б управления не поступит импульс Xs сравнения, свидетельствующий о том, что в массиве первых элементов найден элемент а: (фиг. бб).

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

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

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

Аналогичным образом находят остальные элементы последовательности Wj в узлах памяти соответствующих уровней иерархии. По окончании последовательности Wj, т. е. после нахождения последнего элемента последовательности а,/, осуществляется переход на следующий (У.+ Ьй уровень иерархии - счетчик 5 адресует в первую ячейку одного из узлов памяти (V+l)-ro уровня иерархии, а в результате очередного зап

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

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

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

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

1 ypoSem уровень Зуродемб A/i/jooffe/

Ъаннь/е

Адрес

Признан

0

5 5

5 0

0

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

FXT

lijpobeHb

2дродень

2уродень

NgpobaHb

8 йОр Г J

ФСЕ

ав1

-Ф.

AL

I аа

Ш.

I g. J

Ш.

1 одр I 1

4

Ц 1 |а 1

LO I Tgtf I

.

4

о I 1 Д 1I I J

Фагз

Нет

(Сч)(Сч)4-7

L

Нет

Залась а

Запись дРе

Чтение Ре 1

Выбод

С Коней J ФигЛ

(C4)(cv}+ I

С НонецJ

Устанодш Сч

Залс/сь 8рг 2

ycmffffodfia Cv

Фиг. 5

I I

,

h П h K

I I