Устройство для поиска данных Советский патент 1993 года по МПК G06F7/10 

Изобретение относится к вычислительной технике.

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

На фиг. 1 представлена блок-схема устройства; на фиг.2А - заданные признаки поискового предписания,; на фиг.2Б - данные, среди которых производится поиск; на фиг.2В - циклограмма, иллюстрирующая поиск данных по заданным признакам.

Устройство содержит блок.1 приема признаков поискового предписания, блок 2 приема данных, блок 3 сравнения числа совпавших разрядов с заданными, преобразователь 4 параллельного кода в последовательный, основной вычитающий счетчик 5, блок записи 6, датчик 7 одиночных импульсов, блок 8 импульсов сдвига, блок 9 импульсов установки нуля, линию задержки 10, исполнительный блок 11, блок поразрядного сравнения 12, дополнительный вычитающий счетчик 13, элемент НЕ 14, первый элемент И 15, второй элемент И 16, третий элемент И 17, триггер 18, элемент ИЛИ 19. Преобразователь параллельного кода в последовательный выполнен по схеме сдвигового регистра, число разрядов которого равно максимальной разрядности чисел в массиве данных.

Блок 1 приема признаков поискового предписания выходом подключен к первому входу блока 12 поразрядного сравнения. Блок 2 приема данных выходом подключен ко второму входу блока 12 поразрядного сравнения. Преобразователь 4 параллельного код в последовательный первым входом соединен с выходом блока 12 поразрядного сравнения и с входом линии задержки 10, вторым входом подключен к выходу блока 8 импульсов сдвига, к первому входу первого элемента И 15 и к первому входу третьего элемента И 17, а выходом соединен с первым входом второго элемента И 16 и с входом элемента НЕ 14. Основной вычитающий счетчик 5 первым входом подключен к выходу блока 9 импульсов установки нуля, ко второму входу триггера 18 и ко второму входу дополнительного вычитающего счетчика 13, вторым входом соединен с выходом блока записи 6, третьим входом - с выходом второго элемента И 16, а выходом подключен ко второму входу элемента ИЛИ 19 и к основному входу исполни0

тельного блока 11. Блок записи 6 вторым выходом соединен с третьим входом дополнительного вычитающего счетчика 13. Датчик 7 одиночных импульсов выходом

соединен с третьим входом блока 12 поразрядного сравнения. Блок 8 импульсов сдвига входом подключен к выходу линии задержки 10. Исполнительный блок 11 дополнительным входом соединен с выходом первого элемента И 15 и с третьим входом элемента ИЛИ 19. Дополнительный вычитающий счетчик 13 первым.входом подключен к выходу третьего элемента И 17, а выходом

5 к третьему входу элемента ИЛИ 19. Элемент НЕ 14 выходом соединен со вторым входом первого элемента И 15, третий вход которого подключен к первому выходу триггера 18 и ко второму входу второго элемента

0 И 16. Третий элемент И 17 вторым входом соединен со вторым выходом триггера 18, первый вход которого подключен к выходу элемента ИЛИ 19.

Устройство работает следующим обра5 зом.

На блоке записи 6 набирается число N, представляющее общее количество подлежащих совпадению разрядов, и число М, определяющее количество несущественных

0 старших разрядов кода признака) поискового предписания. Поисковые признаки подаются на вход блока 1 приема признаков поискового предписания, а данные, среди / которых производится поиск. - на вход блс«-

5 ка 2 приема данных. Импульс установки нуля блока 9 приводит устройство в исходное состояние, при этом происходит первоначальное обнуление основного 5 и дополнительного 13 вычитающих счетчиков, а также установка триггера 18 в состояние О по первому выходу и 1 - по второму. Первоначальное обнуление вычитающих счетчиков производится импульсами установки

5 нуля блока 9 по отдельным входам. В этом случае на выходах вычитающих счетчиков отсутствуют импульсы, и триггер 18 сохраняет свое исходное состояние. Импульс пуска осуществляет запись набранных на

0 блоке 6 чисел N и М в основной 5 и дополнительный 13 вычитающие счетчики соответственно. При этом рассмотрим два случая: первый lyl 0 и второй - М 0.

При записи в вычитающий счетчик 13

5 числа М 0 на выходе счетчика вырабатывается единичный импульс, поступающий через элемент ИЛИ 19 на первый вход триггера 18 и изменяющий его состояние на противоположное: 1 - по первому выходу и О - по второму. Одновременно с импуль0

сом пуска осуществляется прием чисел в блок 12 поразрядного сравнения. Разряды регистра преобразователя 4 устанавливаются в состояние 1 или О в соответствии с информацией совпавших разрядов чисел. Кроме того, импульс пуска через линию задержки 10 с задержкой, равной времени переключения триггера поступает на вход блока 8 импульсов сдвига, импульсы которого поступают на входы первого элемента И 15, третьего элемента И 17, и на вход преобразователя 4, осуществляя преобразование записанной информации в соответствующее число последовательных импульсов. При состоянии 1 по первому выходу триггера 18 импульсы с выхода преобразователя 4 через второй элемент И 16 поступают на вход основного вычитающего счетчика 5, изменяя его содержимое. Если при этом количество совпавших разрядов равно числу N, предварительно записанному в блоке записи 6 (то есть, сравниваемое число соответствует заданному поисковому признаку), то счетчик 5 устанавливается в нуль и на его выходе .вырабатывается сигнал 1, поступающий на исполнительный блок 11 и сигнализирующий об отыскании числа с заданным переменным признаком. Одновременно этот сигнал через элемент ИЛИ 19 поступает на основной вход триггера 18, изменяя его состояние на исходное.

Если в процессе сравнения какой-либо из разрядов регистра в преобразователе 4 не устанавливается в состояние 1 (отсутствует совпадение переменного признака с соответствующими разрядами сравниваемого числа), то-соответствующий этому результату сигнал О преобразуется элементом НЕ 14 в сигнал 1 и поступает на второй вход первого элемента И 15. В силу единичного состояния сигнала по первому выходу триггера 18 на выходе первого элемента И 15 образуется сигнал 1, который поступает на дополнительный вход исполнительного блока 11, сигнализируя об отрицательном результате сравнения, а также через элемент ИЛИ 19 на вход триггера 18. В результате этого к приходу следующего импульса пуска триггер 18 переходит в исходное состояние. Импульсы сдвига блока 8 поступают также на первый вход третьего элемента И 17, на второй вход которого поступает сигнал О со второго выхода триггера 18. В результате этого третий элемент И 17 работает как элемент запрета для прохождения импульсов на вход дополнительного вычитающего счетчика 13, предназначенного для выработки сигнала о

5

моменте начала поразрядового сравнения при поиске по переменному признаку.

При М 0, в отличие от известного устройства, если поисковый признак задан, начиная с (М+1)-го разряда числа, результат сравнения М старших разрядов не анализируется. Это позволяет предотвратить выдачу сигнала на дополнительный вход исполнительного блока 11 и тем самым избежать отбраковки необходимых данных. Так же, как и в случае М 0, с приходом импульса пуска в основной 5 и дополнительный 13 вычитающие счетчики заносятся числа N и М, при этом триггер 18 сохраняет свое исходное состояние. В результате сравнения переменного признака с очередным числом данных, среди которых производится поиск, разряды регистра преобразоватеQ ля 4 устанавливаются в состояние О и 1 в соответствии с информацией совпавших разрядов. При этом значения М первых разрядов регистра являются неопределенными в силу неопределенности М первых разря5 до° сравниваемых чисел. С приходом импульсов сдвига блока 8 на вход преобразователя 4 сигналы с его выхода, предназначенные для прохождения в ос- новной вычитающий счетчик 5, будут блоки0 роваться вторым элементом И 16, на второй вход которого подается сигнал О с первого выхода триггера 18. Аналогично, как элемент запрета работает и первый элемент И 15. не пропускающий инвертированные эле5 ментом НЕ 14 сигналы преобразователя 4 на дополнительный вход исполнительного блока 1.1 и, следовательно, исключающий реакцию устройства в случае несравнения каких-либо из числа М старших разрядов

сравниваемых чисел. В то же время третий элемент И 17 на второй вход которого поступает сигнал 1 с выхода триггера 18, пропускает импульсы блока 8 в дополнительный вычитающий счетчик 13. При поступлении М импульсов счетчик 13 обнуляется и вырабатывается на выходе сигнал, информирующий о начале, начиная с (М+1)-го разряда, анализа результата сравнения признака поQ искового предписания и очередного числа данных. Сигнал с выхода счетчика 13 через элемент ИЛ И 19 поступает на вход триггера 18 и изменяет его состояние. Далее устройство работает так же, как о случае М 0.

5 Для примера рассмотрим работу устройства при поиске чисел среди восьмиразрядных данных. На фиг.2А представлены признаки поискового предписания. В первом признаке существенными являются значения 8-го и 7-го разрядов, а во втором

5

признаке - значения 6-го и разрядов. Остальные разряды, значения которых отменены символом X, не существенны для поиска данных. На фиг.2Б приведены восьмиразрядные данные, причем первому признаку поискового предписания соответствует третий байт, а второму признаку - второй байт данных. При поиске по первому признаку на блоке записи 6 набираются числа N 2 (совпадению подлежат два старших разряда) и М О (признак задан, начиная с 8-го разряда). На фиг. 2В отражены основные параметры состояния устройства и их динамика при поиске данных. Рассмотрены два цикла поиска: первый - поиск по первому признаку и второй - поиск по второму признаку. Исходное состояние устройства отражено в соответствующей графе циклограммы.

Импульс пуска осуществляет запись чисел N 2 и М О в вычитающие 5 и 13, при этом на выходе счетчика 13 вырабатывается сигнал 1 (фиг.2В, первая графа первого цикла), поступающий через элемент ИЛИ 19 на первый вход триггера 18. При сравнении первого признака с первым числом 8-ой и 7-ой разряды регистра преобразователя 4 устанавливаются в состояние О (нет сравнения), а остальные разряды не определены в силу неопределенности их в первом признаке. В результате с приходом импульса сдвига с задержкой, равной времени переключения триггера, сигнал О с выхода преобразователя 4 инвертируется элементом НЕ 14 в сигнал 1 и, благодаря единичному состоянию триггера 18 по первому выходу, проходит через первый элемент И15 на дополнительный вход исполнительного блока 1.1. Одновременно этот же сигнал через элемент ИЛИ 19 поступает на вход триггера 18 для перевода его в исходное состояние. Соответствующие этому состоянию сигналы приведены во второй графе первого цикла поиска на фиг.2В. Точно также работает устройство при сравнении первого признака со вторым числом данных, что отражено в третьей и четвертой, графах первого цикла поиска. При сравнении первого признака с третьим числом данных 8-ой и 7-ой разряды регистра преобразователя 4 устанавливаются в состояние 1. Поэтому с приходом первого импульса сдвига на выходе преобразователя 4 вырабатывается сигнал 1 (фиг.2В, шестая графа первого цикла поиска), который в силу единичного состояния триггера 18 по первому выходу проходит через второй элемент И 16 на вход основного вычитающего счетчика 5 и его содержи5

мое уменьшается на единицу (фиг.2В, пятая и шестая графы первого цикла поиска). С приходом второго импульса сдвига на выходе преобразователя 4 вновь образуется сигнал 1, при этом содержимое счетчика 5 обнуляется и на его выходе образуется сигнал 1. (фиг. 2В, седьмая графа первого цикла поиска). Этот сигнал поступает на основной вход исполнительного блока 11,

сигнализируя об обнаружении числа с заданным признаком. Одновременно сигнал с выхода счетчика 5 поступает через элемент ИЛИ 19 на вход триггера 18 для перевода его в исходное состояние.

При поиске данных по второму признаку с приходом импульса пуска в вычитающий счетчик 5 заносится число N 2 (совпадению подлежат два разряда: 6-ой и

Q 5-ый), а в счетчик 13 - число М 2 (два старших разряда кода признака не определены). В результате сравнения второго признака с первым числом данных 6-ой и 5-ый разряды регистра преобразователя 4 уста5 навливаются в состояния О и 1 соответственно, а остальные разряды не определены. Триггер 18 находится в исходном состоянии, поэтому с приходом первого и второго импульсов сдвига воздействия

0 сигналов на исполнительный блок 11 блокируются. В то же время третий элемент И 17, на второй вход которого поступает сигнал 1 с триггера 18, пропускает импульсы в дополнительный вычитающий счетчик 13,

5 который после второго импульса сдвига обнуляется, и вырабатывается сигнал 1 (фиг.2В, третья графа второго цикла поиска). Этот сигнал через элемент ИЛИ 19 поступает на вход триггера 18 для изменения его состояния. С приходом третьего импульса сдвига (фиг. 2В, четвертая графа второго цикла поискч) в силу отрицательного результата сравнения второго признака и первого числа данных (не совпадают значения шестых разрядов) на выходе преобразователя 4 вырабатывается сигнал О, который инвертируется элементом НЕ 14 и проходит через первый элемент И 15 на исполнительный

Q блок 11, сигнализируя о несравнении второго признака с первым числом данных (фиг.2В, четвертая графа второго цикла поиска). Этот же сигнал через элемент ИЛИ 19 поступает на вход триггера 18 для измене5 ния его состояния. Следующий импульс пуска вновь заносит числа М 2иМ 2в вычитающие счетчики 5 и 13; Содержимое регистра преобразователя 4 устанавливается в состояние, при котором 6-й и 5-й разряды имеют значение 1, а остальные

разряды не определены. С приходом первых двух импульсов сдвига содержимое счетчика 13 обнуляется и на его выходе вырабатывается сигнал 1 (фиг.2В, седьмая графа второго цикла поиска); В результате изменяется состояние триггера 18, и с приходом третьего импульса сдвига сигнал 1 с выхода преобразователя А проходит через второй элемент И 16, уменьшая содержимое счетчика 5 на единицу (фиг.2В, восьмая графа второго цикла поиска). С приходом четвертого импульса сдвига содержимое счетчика 5 обнуляется, в результате чего на основной вход исполнительного блока 11 выдается сигнал о нахождении искомого числа данных по второму признаку поискового предписания.

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

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

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

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

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

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

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

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

выходу основного вычитающего счетчика,

pabPflAHctx сетка, признаков nep&btd признак

- 6m

OPOU признак

Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах подготовки исходных данных для переработки многопараметрических потоков измерительной информации. Целью изобретения является расширение функциональных возможностей устройства за счет обеспечения поиска данных по более широкому спектру признаков, коды которых могут задаваться произвольно в пределах разрядной сетки данных. Устройство содержит блоки приема данных и признаков 1 и 2, блок 12 поразрядного сравнения, исполнительный блок регистрации результата 11 и блок 3 сравнения числа совпавших разрядов с заданными. В состав последнего входят блоки 9 импульсов установки нуля, блок 8 импульсов сдвига и дат-- чикодиночных импульсов, линия задержки 10, блок 6 записи и преобразователь кода А, основной 5 и дополнительный 13 вычитающие счетчики, элемент НЕ 14, элемент ИЛИ 19 и три элемента И 15, 16, 17. 2 ил. w &

Разрядная сетка ланных пер&ое число ламных бторое. число М.а.нных третье, чцсло лонных: