Устройство для поиска данных

 

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

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

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

РЕСПУБЛИК (si)s 6 06 F 7/06

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4794493/24 (22) 22.02.90 (46) 15.02.93. Бюл. N- 6 (72) А.M. Белан и Д.И. Герасименко (56) Авторское свидетельство СССР

t4 1061133, кл, G 06 F 7/06, 1982.

Авторское свидетельство СССР

tk 1183955, кл. О 06 F 7/06, 1982.

„„.Я2 „„ l?9544? А1

2 (54) УСТРОЙСТВО ДЛЯ ПОИСКА ДАННЫХ (57) Изобретение относится к вычислительной технике и может быть использовано в качестве аппаратного расширителя ЭВМ для поиска заданного признака в массиве.

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

30 менной длины в неупорядоченном массиве данных,Устройство содержит группы из fl регистров 1 признака; группу из и схем 2 сравнения, группу из и триггеров 3, группу из и элементов И 4, группы из (n-1) элементов И 5, И 6, блок 7 анализа сигналов совпадения, шифратор 8, дешифратор 9, регистр

10 длины признака, счетчик 11 номера обрабатываемого символа, счетчик 12 адреса, регистр 13 адреса, сумматор 14, блок 15 вычитания, схемы 16, 17 сравнения, группы

Изобретение относится к вычислительной технике и может быть использовано в качестве аппаратного расширителя 3ВМ для поиска заданного признака в массиве.

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

Наиболее близким техническим решением к предлагаемому является устройство поиска заданного числа, содержащее регистры, счетчик адреса, схемы сравнения, триггер, группу элементов И, элемент 2ИИЛИ, элементы И, ИЛИ, элемент задержки, информационные входы, вход запуска, вход тактовых импульсов, выходы.

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

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

Поставленная цель достигается тем, что устройство для поиска данных, содержащее регистр длины признака, регистр признаю, две схемы сравнения, регистр адреса, первую схему сравнения группы, счетчик адреса, четыре элемента И, группу элементов И, два элемента ИЛИ, триггер, элемент эадержки, дополнительно содержит (и-1) регистров признака, где и — максимальная длина . признака, группу из (n-1) схем сравнения, группу иэ п триггеров, две группы из (и-1) элементов И, блок анализа сигналов cosnaдения, шифратор, двэ дешифратора, второй элемен-;ов ИЛИ 18, 19, элементы ИЛИ 20, 21, 22, 23, элемент И 24, группы элементов

И 25, 26, элементы И 27, 28, 29, элементы

30-35 задержки, дешифрато р Зб, триггер 37, Устройство реализует быстрый алгоритм позлементного поиска заданной последовательности чисел (символов. знаков) произвольной длины в неупорядоченном массиве данных, расположенном в памяти

ЭВМ. 2 ил. счетчик, сумматор, блок вычитания, две группы элементов ИЛИ, два элемента ИЛИ, две группы элементов И, пять элементов задержки, причем, информационные входы регистров признака являются кодовыми входами устройства, входы вторых групп всех схем сравнения являются информационными входами устройства, вход первого элемента задержки соединен с входом установки в нулевое состояние триггера и является первым управляющим входом устройства, второй вход первого элемента

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

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

На чертеже (фиг. 1) представлена блоксхема устройства..

Устройство содержит группу из и регистров 1 признака, группу из и схем 2 сравнения, группу из и триггеров 3, группу из и элементов И 4, группы из (и-1) элементов И

5, И 6, блок анализа сигналов совпадения 7, шифратор 8, дешифраторы 9, 36, регистр 10 длины признака; счетчик 11 номера обрабатываемого символа, счетчик 12 адреса, регистр 13 адреса, сумматор 14, блок 15 вычитания, схемы 16, 17 сравнения. группы элементов ИЛИ 18, 19, элементы ИЛИ 2023, группы элементов И 25, 26, элементы И

1795447

50

24, 27 — 29. элементы 30-35 задержки, триггер 37, вход 38 запуска, вход 39 записи длины признака, информационный 40 и управляющие 41. 43 входы, кодовые входы

42, адресные входы 44, 45, выход запроса

46, информационные выходы 47, 48, адресный выход 49, причем выходы разрядов счетчика 12 адреса и регистра 13 адреса соединены с входами соответственно первой и второй групп схемы 17 сравнения, выход которой подключен к первому входу элемента И 29, выход которого является выходом 46 запроса устройства, выходы разрядов j-го (j=1,n) регистра 1 признака подключены к входам первой группы j-ой схемы 2 сравнения группы, информационные входы регистра 10 длины признаков являются входами 39 длины признака устройства, информационные входы регистров

1 признака являются кодовыми входами 42 устройства, входы вторых групп всех схем 2 сравнения являются информационными входами 40 устройства, выходы j-ой схемы 2 сравнения группы подключены к первому входу j-го элемента И 4, группы, выход которого соединен с !-ым входом блока 7 анализа сигналов совпадения, первый выход которого соединен с первым входом шифратора 8, а 1-ый (1=2, и) выход соединен с 1-ым входом шйфратора 8 и с первым входом (I — 1)-го элемента И 5 группы, выход (i - 1)ro элемента И5 группы соединен с входом установки в нулевое состояние (i-1)-го триггера 3 группы. вход установки в единичное состояние которого соединен с выходом (i1)-го элемента И 6 группы, первый вход которого подключен к выходу триггера 37, выход (i —.1)-го триггера 3 группы подключен к вторым входам (I — 1)-ых элементов И 4, И 6 первой и третьей групп, выход и-го триггера

3 группы соединен с вторым входом и-го элемента И 4 группы, инверсный вход (1-1)го элемента И 6 группы подключен к (I — 1)ому выходу дешифратора 9, входы которого соединены с выходами разрядов регистра

10длины признака, информационными входами элементов И 25 группы, информационными входами счетчика 11 и входами первой группы блока 15 вычитания, входы второй группы которого подключены к выходам шифратора 8 и входам первой группы схемы 16 сравнения, входы второй группы которой соединены с выходами разрядов счетчика 11, и с входами дешифратора 36, выход схемы 16 сравнения подключен к первым входам элементов И 24, 27, 28, вторые входы которых соединены через элемент 33 задержки с управляющим входом 41 устройства и входом установки в нулевое состояние триггера 37. вход установки в

40 единичное состояние которого соединен с выходом элемента ИЛИ 20, первым входом элемента ИЛИ 21, входом установки в единичное состояние первого триггера 3 группы, управляющими входами счетчика 11 и сумматора 14 и через элемент 35 задержки с первым входом элемента ИЛИ 23. входы первой группы сумматора подключены к выходам элементов ИЛИ 18, а входы второй группы являются адресными выходами 49 устройства и подключены к выходам разрядов счетчика 12, выход схемы 17 сравнения является информационным выходом 48 устройства, второй вход элемента И 29 соединен через элемент 32 задержки с выходом элемента ИЛИ 21, второй вход которого подключен к первому входу элемента ИЛИ

22, вычитающему входу счетчика 11, вторым входам элементов И 5 группы и выходу элемента И 28, инверсный вход которого подключен к выходу дешифратора 36 и через элемент 30 задержки соединен с третьим входом элемента И 24, выход которого является информационным выходом 47 устройства, выход элемента И 27 соединен с управляющим входом блока 15 вычитания и через элемент 34 задержки подключен к второму входу элемента ИЛИ 20, к инверсным входам элементов И 25 группы и к первым входам элементов И 26 группы, вторые входы которых соединены с выходами блока

15 вычитания, а выходы — с первыми входами соответствующих элементов ИЛИ 18 группы, вторые входы которых подключены к выходам элементов И 25 группы, второй вход элемента ИЛИ 20 является входом 38 запуска устройства и через элемент 31 задержки соединен с вторым входом элемента

ИЛИ 22, выход которого соединен с вычитающим входом счетчика 12, информационные входы которого соединены с выходами соответствующих элементов ИЛИ 19 группы, первые входы которых являются адресными входами 44 устройства. а вторые входы соединены с выходами сумматора 14, управляющий вход счетчика 12 подключен к выходу элемента ИЛИ 23, второй вход которого является управляющим входом 43 устройства, вход регистра 13 адреса конца поиска является адресным входом 45 устройства. устройство работает следующим образом.

8 исходном состоянии в j-ые регистры 1 (j=1, и) по входам 42 заносятся коды j-ых символов (чисел) признака. Если число символов признака К<п, то (n — Iq последних регистров 1 окажутся не заполненными символами. Код длины признака по входам

39 заносится в регистр 10 и определяет чис1795447

10

25

35

50

55 ло заполненных регистров 1 группы, начиная с первого регистра 1, В счетчик 12 и регистр 13 по входам 44, 45 заносятся соответственно адреса начала и конца поиска (начального и конечного символов) в массиве памяти, который необходимо просмотреть на наличие в нем определенной комбинации символов — признака, Занесение адреса в счетчик 12 сопровождается управляющим сигналом по входу 43 устройства, который через элемент ИЛИ 23 поступает нэ управляющий вход счетчика 12.

Триггеры 3 группы, триггер 37 и счетчик 11 находятся в нулевом состоянии. Код длины признака с выхода регистра 10 поступает на вход дешифратора 9 устройства. В результате на К-ом выходе дешифратора 9 присутствует единичный сигнал (1 =К п, К вЂ” длина признака), который закрывает по инверсному входу К-ый элемент И 6 группы. Остальные элементы И 6 группы открыты по инверсным входам нулевыми сигналами с соответствующих выходов дешифрэтора 9, Работа устройства начинается с приходом сигнала запуска по входу 38. Сигнал запуска через элемент ИЛИ 20 устанавливает в единичное состояние триггер 37 и первый триггер 3 группы, Единичный сигнал с выхода триггера 37 поступает на первые входы элементов И 6 группы, подготавливая их открытие. Единичный сигнал с выхода ,первого триггера 3 группы поступает на второй вход первого элемента И 6 группы, Если первый элемент И 6 группы открыт по инаерсному входу нулевым сигналом с первого выхода дешифратора 9, то íà его выходе появляется единичный сигнал, устанавливающий в единичное состояние второй триггерЗ группы. Установка в единичное состояние

i-ых триггеров 3 группы (1=2, n) осуществляется последовательно единичными сигналами с выходов предыдущих (1-1)-ых триггеров 3 через соответствующие (i — 1) элементы И 6 группы, Так кэк К-ый элемент N 6 закрыт единичным сигналом с К-ro выхода дешифратора 9, то в единичное состояние по сигналу запуска будут последовательно устанавливаться триггеры 3 группы, начиная с первого и по К-ый, (n-К) последующих триггеров 3 группы останутся в нулевом состоянии, Элементы И 4 группы с первого по К-ый окажутся открытыми, а элементы И 4 с (К+1) до n — закрытыми по вторым входам единичными сигналами с выходов соответствующих триггеров 3 группы. Тем самым маскируются выходы схемы 2 сравнения, соответствующие регистрам 1, не содержащим символы признака.

Сигнал запуска через элемент ИЛИ 20 поступает также на управляющие входы счетчика 11 и сумматора 14, разрешая соответствз.<но занесение кода длины признака из регистра 10 в счетчик 11 и однократное выполнение операции суммирования в сумматоре 14 с записью результата в счетчик

12, На входы первой группы сумматора 14 через группу элементов И 25 и группу элементов ИЛИ 18 поступает содержимое регистра 10, а на входы второй группы— содержимое счетчика 12. К адресу начала поиска прибавляется длина признака и полученная сумма с выхода сумматора 14 через группу элементов ИЛИ 19 поступает на информационные входы счетчика 12, Сигнал запуска с выхода элемента ИЛИ 20 через элемент 35 задержки и элемент ИЛИ 23 поступает нэ управляющий вход счетчика 12, разрешая запись информации в счетчик.

Элемент 35 обеспечивает задержку появления сигнала на управляющем входе счетчика 12 на время, достаточное для формирования результата суммирования на выходе сумматора 14.

Сигнал запуска с входа 38 через элемент 31 задержки и элемент ИЛИ 22 поступает на вычитающий вход счетчика 12.

Элемент 31 обеспечивает задержку поступления сигнала вычитания "1" на время, достаточное для выполнения операции суммирования в сумматоре 14 и занесения полученной суммы в счетчик 12. В результате вычитания "1" из содержимого счетчика

12 на его выходах будет сформирован код адреса, смещенный относительно адреса начала поиска на (К-1}, т.е. адрес последнего К-го символа просматриваемого фрагмента массива (текста), который поступает на адресный выход 49 устройства.

Сигнал запуска через элементы ИЛИ 20, 21, элемент 32 задержки и элемент И 29 поступает на выход запроса 46 устройства, Элемент 32 обеспечивает задержку сигнала до установления соответствующих триггеров 3 в единичное состояние, появления адреса на выходе 49 устройства и его сравнения с адресом конца массива на схеме 17. Сигнал с выхода 46 инициирует запрос.в запоминающее устройство на выборку символа по адресу, сформированному нэ выходе 49.

Код символа, считанный из запоминающего устройства по информационному входу 40, поступает на входы второй группы схем 2 сравнения группы. При совпадении кода симвОла, считанного из памяти, с кодом символа признака, записанном в какомлибо регистре 1, на выходе соответствующей схемы 2 сравнения появится единичный сигнал. Сигнал совпадения может появиться на выходах нескольких схем 2, в зависимости от количествэ совпавших символов признака с символом, считан1795447

5

15

25

55 ным из памяти, Незамаскированные сигналы совпадения с выходов схем 2 через элементы И 4 группы поступают на соответствующие входы блока 7 анализа сигналов совпадения.

Блок 7 анализа сигналов совпадения построен таким образом, что при поступлении на его входы нескольких единичных сигналов совпадения с выходов соответствующих элементов И 4 группы, единичный сигнал появится на выходе одного наиболее старmего разряда (ближайшего к и-ому) на входе которого установлен единичный сигнал.

Блок 7 может быть построен на основе устройства для определения старшего значащего разряда (фиг. 2), устройства приоритета и других комбинационных схем.

При поступлении незамаскированных сигналов совпадения с выходов элементов, И 4 группы на входы блока 7 обеспечивается выделение одного незамаскированного сигнала совпадения в К-ом или наиболее близком к К-ому разряде, На одном из выходов блока 7 с 1-го по К-ый появляется единичный сигнал совпадения, поступающий на первый вход соответствующего элемента И 5 группы (кроме сигнала с первого выхода схемы 7) и на один из входов с 1-го по К-ый шифратора 8, На выходе шифратора 8 формируется ход номера К-го или наиболее близкого к К-ому символа признака, совпавmего с символом, считанным из памяти. Код с выхода шифратора 8 поступает на вторую группу входов схемы 16 сравнения, на первую группу входов которой поступает код с выходов счетчика 11.

Первоначально по сигналу запуска в счетчик 11 из регистра 10 заносится двоичный код числа символов в признаке — код числа К, который рассматривается как код номера последнего символа признака. На выходе схемы 16 появится единичный сигнал, если коды на выходах счетчика 11 и шифратора 8 совпадают, т.е, если символ, считанный из памяти, совпал с последним

К-ым символом признака. Единичный сигнал с выхода схемы 16 поступает на первые входы элементов И 24, 28, подготавливая их открытие, и закрывает по инверсному входу элемент И 27, Код с выхода счетчика 11 поступает также на входы дешифратора 36, настроенного на выявление одной входной кодовой комбинации 0...01, соответствующей наличию "1" в счетчике 11. Если в счетчике 11 первоначально записан код с числа

К>1, то на выходе дешифратора 36 присутствует нулевой сигнал, который открывает по инверсному входу элемент И 28 и закрывает по третьему входу элемент И 24. Поступление по информационному входу 40 символа из запоминающего устройства сопровождается сигналом считывания по управляющему входу 41 устройства, который устанавливается в нулевое состояние триггер 37 и через элемент ЗЗ задержки поступает на вторые входы элементов И 24, 27, 28.

Элемент 33 обеспечивает задержку сигнала на время, достаточное для сравнения выбранного из памяти символа с символами, занесенными в регистры 1, формирования кода номера совпавшего символа признака на выходе шифратора 8 и сравнения его на схеме 16 с кодом, записанным в счетчике 11.

Единичный сигнал с выхода элемента 33 задержки через элемент И 28, открытый по инверсному входу нулевым сигналом с выхода дешифратора 36 и по первому входу— единичным сигналом с выхода схемы 16 сравнения, поступает на вторые входы элементов И 5 группы, В результате сигнал с

К-го выхода блока 7 через открытый по второму входу элемента И 5 группы устанавливает в нулевое состояние соответствующий триггер 3, маскируя в дальнейшем результаты сравнения считываемых из памяти символов с К-ым символом признака, Единичный сигнал с выхода элемента И 28 поступает также на вычитающий вход счетчика 11 и через элемент ИЛИ 22 — на вычитающий вход счетчика 12, уменьшая их содержимое на "1". В счетчике 11 сформируется код номера следующего символа признака — код числа (К вЂ” 1), а в счетчике.12— код адреса, смещенного относительно адреса начала поиска на (К вЂ” 2), т.е, адрес (K — 1)-го символа анализируемого фрагмента массива. С задержкой, обеспечиваемой элементом 32 и достаточной для формирования адреса на выходе 49 устройства и его сравнения с адресом конца массива на схеме 17, сигнал с выхода элемента И 28 через элемент ИЛИ 21, элемент 32 задержки и элемент И 29 поступает на выход 46, инициируя запрос в запоминающее устройство на выборку очередного символа. Код в счетчике

11 анализируется в дешифраторе 36. на выходе которого появляется единичный сигнал, если после вычитания "1" в счетчике 11 будет сформирован код числа К-1=1, т.е. если число символов в признаке К=2. Единичный сигнал с выхода дешифратора 36 закрывает по инверсному входу элемент И

28 и через элемент 30 задержки поступает на третий вход элемента И 24, подготавливая его открытие. Элемент 30 обеспечивает задержку поступления единичного сигнала на третий вход элемента И 24 на время, достаточное для срабатывания схемы 16 и снятия единичного сигнала с первого и второго входов элемента И 24, что предотвра1795447

10

40

55 щает появление ложного сигнала на выходе

47 устройства.

Очередной символ, считанный из памяти по адресу, выставленному на выходе 49 устройства, сравнивается с содержимым регистров 1. Незамаскированные сигналы совпадения поступают с выходов схем 2 сравнения через элементы И 4 на соответствующие входы блока 7. Блок 7 выделяет . один из входных сигналов совпадения, наиболее близкий к К-ому входу, Сигнал с соответствующего выхода блока 7 поступает на вход шифратора 8, на выходе которого формируется код номера сигнала совпадения.

Если коды на выходах счетчика 11 и шифратора 8 одинаковы, т.е. считанный иэ памяти символ фрагмента массива совпадает с соответствующим символом признака, на выходе схемы 16 сравнения появится единичный сигнал, который поступает на первые входы элементов И 24, И 28, При этом, если код в счетчике 11 равен "1", т,е. выявлено совпадение первого символа анализируемого фрагмента массива с первого символа признака (остальные символы также совпали), то на выходе дешифратора 36 присутствует единичный сигнал, который открывает по третьему входу элемент И 24 и закрывает по инверсному входу элемент И

28, В результате управляющий сигнал считывания с выхода элемента 33 задержки через элемент И 24, открытый по второму и третьему входам, поступает на выход 47 ус-. тройства, Появление сигнала на выходе 47 свидетельствует о том, что в просматриваемом массиве по адресу, сформированному на выходе 49 устройства, найдена комбинация символов (фрагмент массива), совпадающая с заданным в регистрах 1 признаком, На этом работа устройства заканчивается.

Если содержимое счетчика 11 больше "1" и на выходе схемы 16 появится единичный сигнал, то необходимо продолжить сравнение символов данного фрагмента массива с символами признака, На выходе элемента И

28 будет сформирован единичный сигнал, по которому маскируется соответствующий выход схемы 2 сравнения, содержимое счетчика 11, 12 уменьшается на "1" и формируется запрос в память на чтение очередного символа.

Если блок 7 выделил совпадение считанного из памяти символа не с очередным символом признака, номер которого m записан в счетчике 11, а с символом, номер которого меньше, например, равен 1, где гп>1>1, то на выходе схемы 16 сравнения сохранится нулевой сигнал, закрывающий по первым входам элементы И 24, 28 и подготавливающий открытие по инверсному входу ь,емента И 27. Сигнал считывания с управляющего входа 41 с задержкой, достаточной для проверки на схеме 16 соответствия номера! сигнала совпадения номеру m очередного символа признака, поступает на второй вход элемента И 27, Единичный сигнал с выхода элемента И 27 поступает на управляющий вход блока 15 вычитания, разрешал выполнение операции вычитания (К1), Двоичные коды чисел К и поступают на входы первой и второй группы блока 15 с выходов соответственно регистра 10 длины признака и шифратора 8. Единичный сигнал с выхода элемента И 27 через элемент 34 задержки поступает на инверсные входы элементов И 25 группы, закрывая их и на первые входы элементов группы И 26, разрешая поступление кода с выходов бгока 15 через группу элементов ИЛИ 18 на входы первой группы сумматора 14. Элемент 34 обеспечивает задержку сигнала на время, достаточное для выполнения операции вычитания кодов в блоке 15. Единичный сигнал с выхода элемента 34 задержки через элемент ИЛИ 20 поступает также на управляющие входы счетчика 11 и сумматора 14, разрешая соответственно обновление содержимого счетчика 11 (запись кода длины признака иэ регистра 10) и однократное суммирование в сумматоре 14 двоичных кодов с выходов блока 15 вычитания и счетчика 12.

Полученная сумма через группу элементов

ИЛИ 19 заносится в счетчик 12. Длительность управляющего сигнала на входе блока

15 вычитания определяется длительностью сигнала на входе 41 устройства и является достаточной для вйполнения суммирования в сумматоре 14 с записью результата в счетчик 12. Запись в счетчике 12 осуществляется " по разрешающему единичному сигналу, поступающему на управляющий вход счетчика

12 с выхода элемента NJlM 20 через элементы 35 задержки и ИЛИ 23. Элемент 35 осуществляет задержку управляющего сигнала на время, достаточное для появления искомой суммы на выходе сумматора 14, Таким образом, в счетчике 12 формируется код адреса, смещенного относительно адреса последнего символа, считанного из памяти, на величину, равную (К вЂ” l), Полученный адрес позволяет начать выборку из памяти последнего символа нового фрагмента массива, который будет сравниваться с заданным признаком, Сигнал с выхода элемента ИЛИ 20 через элемент ИЛИ 21, элемент 32 задержки и элемент И 29 поступает на выход запроса 46 устройства, Элемент 32 обеспечивает задержку появления запроса в память на время, достаточное для формирования нового адреса на выходе 49

1795447 устройства и его сравнения с адресом, занесенным в регистр 13. Одновременно единичный сигнал с выхода элемента ИЛИ 20 поступает на входы установки в единичное состояние триггера 37.и первого триггера 3 группы. Последовательно устанавливаются в единицу триггеры 3 группы с первого по

К-ый. С приходом очередного символа, считанного из памяти, по информационному входу 40 и сигнала считывания по управляющему входу 41 устройство работает аналогично.

Если блок 7 не выявил ни одного незамаскированного сигнала совпадения, то на выходе шифратора 8 будет нулевой код, на выходе блока 15 вычитания — код разности

К вЂ” i = К вЂ” 0 = К, который будет суммировать- ся с содержимым счетчика 12. Полученный адрес является адресом последнего символа нового фрагмента массива и смещен относительно адреса последнего символа, 20 считанного из памяти, на величину, равную длине признака К, Заданный для поиска признак может

30 состоять из одного символа, B этом случае в счетчик 11 заносится из регистра 10 код числа п1", что приводит к появлению единичного сигнала на выходе дешифратора 36 и, следовательно, на третьем входе элемента И 24. Осуществляется последовательная выборка символов из массива и сравнение их с заданным символом. При выявлении совпадения единичный сигнал появляется на первом выходе блока 7, на соответствующем выходе шифратора 8, на выходах схемы

16 и элемента И 24, Во время работы устройства в регистре

13 хранится код адреса конца массива данных (адрес последнего символа в массиве).

Если текущий адрес в счетчике 12 превысит ч

I гг

40 адрес в регистре 13, то на выходе схемы 17

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

Устройство для поиска данных, содержащее регистр длины признака, регистр признака, две схемы сравнения, регистр адреса, первую схему сравнения группы, счетэлементов И, два элемента ИЛИ, триггер, элемент задержки, причем выходы разрядов счетчика адреса и регистра адреса соединены с входами соответственно первой и второй групп первой схемы сравнения, вычик адреса, четыре элемента И, группу ход которой подключен к первому входу сравнения появится единичный сигнал, который поступает на информационный выход 48 устройства и свидетельствует о том, что массив просмотрен и заданный признак 45 в MGM огсутствует. Единичный сигнал с выхода схемы 17 закрывает по инверсному входу элемент И 29, блокируя выдачу запроса в память на выборку очередного символа по адресу, превышающему заданную грани- 50 цу массива. Работа устройства заканчивается.

Новый цикл работы устройства начнется по сигналу запуска после занесения в регистры 1 нового признака и в регистр 10 кода его длины или (и) изменения адресов начала и конца поиска в счетчике 12 и регистре 13. Предварительноустанавливаются в нулевое состояние триггеры 3 группы, триггер 37 и счетчик 11. Изменение адреса начала поиска в счетчике. 12 сопровождается сигналом по управляющему входу 43 устройства. Массив, границы которого в памяти заданы адресами первого и последнего символов, анализируется последовательно фрагментами, длина которых равна длине признака. Фрагменты массива считываются из памяти посимвольно, начиная с последнего символа. Считанный символ сравнивается с символами заданного признака.

Первый просматриваемый фрагмент массива начинается с адреса начала поиска, Адрес последних символов последующих фрагментов массива вычисляется в зависимости от результатов сравнения символов предыдущего фрагмента массива с символами признака, Два смежных фрагмента массива могут перекрываться и иметь от 0 до {n-1) общих символов, Работа устройства заканчивается, если найден фрагмент массива, все символы которого совпадают с соответствующими символами признака, или просмотрен весь массив и заданный признак не обнаружен. При этом на соответствующих информационных выходах 47 и 48 устройства появляются единичные сигналы, а на адресном выходе 49 устройства формируется адрес первого символа фрагмента массива, совпавшего с признаком, Таким образом, предлагаемое устройство реализует рациональный алгоритм поиска заданного признака переменной длины в массиве. Признак представляет собой последовательность из К (К=1, n) символов (знаков, чисел). Массив состоит из неупорядоченной совокупности символов (знаков, чисел), расположенных в памяти по последовательным адресам, Устройство позволяет осуществить поиск . одного (К=1) или нескольких (К=2, n) чисел (символов, знаков), образующих признак; в неупорядоченном массиве, В качестве признака может быть задана любая последова- тельность чисел (символов, знаков), 1795447

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

И, блок анализа сигналов совпадения, шифратор, два дешифратора, второй счетчик, сумматор, блок вычитания, две группы элементов ИЛИ, два элемента ИЛИ, две группы элементов И, пять элементов задержки, причем информационные входы регистров признака являются кодовыми входами устройства, выходы разрядов i-го (l= ?, n) регистра признака подключены к входам первой группы 1-й схемы сравнения группы, входы вторых групп всех схем сравнения являются информационными входами устройства, выходы j-й (=1, и) схемы сравнения группы подключены к первому входу j-ro элемента

И первой группы, выход которого соединен с j-м входом блока анализа сигналов cosnaдения, первый выход которого соединен с первым входом шифратора, а i-й выход соединен c I-м входом шифратора и с первым входом (1-1)-ro элемента И второй группы, выход (1-1)-го элемента И второй группы соединен с входом установки в нулевое состояние (i — 1)-ro триггера группы, вход установки в единичное состояние которого соединен с выходом (i — 1)-го элемента И третьей группы, первый вход которого подключен к выходу триггера, выход (1 — 1)-го триггера группы подключен к вторым входам (i — 1)-х элементов первой и третьей групп, выход n-ro триггера группы соединен с вторым входом и-ro элемента И первой группы, инверсный вход (i — 1)-го элемента И третьей группы подключен к (i — 1)-му выходу дешифратора, входы которого соединены с выходами разрядов регистра длины признака, информационными входами элементов

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

35 подключен к второму входу первого элемента ИЛИ, к инверсным входам элементов И четвертой группы и к первым входам элементов И пятой группы, вторые входы которых соединены с выходами блока

40 вычитания, а выходы — с первыми входами соответствующих элементов ИЛИ первой группы, вторые входы которых подключены к выходам элементов И четвертой группы, второй вход первого элемента ИЛИ являет45 ся входом запуска устройства и через шестой элемент задержки соединен с вторым входом четвертого элемента ИЛИ, выход которого соединен с вычитающим входом первого счетчика, информационные входы

50 которого соединены c выходами соответствующих элементов ИЛИ второй группы, пер; вые входы которых являются первыми, адресными входами устройства, а вторые входы соединены с выходами сумматора, управляющий вход первого счетчика подключен к выходу третьего элемента ИЛИ, второй вход которого является вторым управляющим входом устройства, вход регистра адреса конца поиска является вторым адресным входом устройства.

его и четвертого элементов И, вторые входы которых соединены через первый элемент задержки с управляющим входом устройства и входом установки в нулевое состояние триггера, вход установки в единичное состояние которого соединен с выходом первого элемента ИЛИ, первым входом второго элемента ИЛИ, входом установки в единичное состояние первого триггера группы, управляЮщими входами второго счетчика и сумматора и через второй элемент задержки с первым входом третьего элемента ИЛИ, входы первой группы сумматора подключены к выходам элементов ИЛИ первой группы, а входы второй группы являются адресными выходами устройства и подключены к выходам разрядов первого счетчика, выход первой схемы сравнения является информационным выходом устройства, второй вход первого элемента И соединен через третий элемент задержки с выходом второго элемента ИЛИ, второй вход которого подключен к первому входу четвертого элемента ИЛИ, вычитающему входу второго счетчика, вторым входам элементов И вто— рой группы и выходу четвертого элемента И, инверсный вход которого подключен к выходу второго дешифратора и через четвертый

1795447 (e.-<) g

O pl) Фис 2

Редактор

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

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101

/pa) 5 (к-2) рп

5Ъ

Составитель А.Белан

Техред М.Моргентал Корректор 9.Кравцова