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

ш

ел

УСТРОЙСТВО ДЛЯ ПОИСКА ДАННЫХ по авт. св. № 995087, отличающееся тем, что, с целью повышения быстродействия, в него введены элемент НЕ и элемент И, входы которого соединены соответственно с выходами блока импульсов сдвига и элемента НЕ, а выход подключен ко второму дополнительному входу исполнительного блока, вход элемента НЕ подключен к выходу преобразователя параллельного кода в последовательный.

СО

оо Изобретение относится к вычислительной технике. По основному авт. св. № 995087 известно устройство для поиска данных, содержащее блоки приема данных и признаков, блок поразрядного сравнения данных, исполнительный блок, блок сравнения числа совпавших разрядов с заданным, в состав которого входит блок импульсов установки нуля, блок импульсов сдвига, датчик одиночных импульсов, преобразователь параллельного кода в последовательный, блок записи, основной и дополнительный вычитающие счетчики, причем выходы блоков приема признаков и данных соединены с первым и вторым входами блока подразрядного сравнения, третий вход которого подключен к выходу датчика одиночных импульсов, а выход - к первому входу преобразователя параллельного кода в последовательный и через линию задержки ко входу блока импульсов сдвига, выход которого подключен ко второму входу преобразователя параллельного кода в последовательный и к первому входу дополнительного вычитающего счетчика, второй вход которого соединен с выходом блока импульсов установки нуля и первым входом основного вычитающего счетчика, а выход - с входом исполнительного блока, второй вход основного вычитающего счетчика соединен с выходом блока записи и третьим входом дополнительного вычитающего счетчика, выход основного вычитающего счетчика соединен с дополнительны.м входом исполнительного блока 1. Известное устройство позволяет производить сравнение данных с заданным числом совпадений разрядов, а следовательно поиск данных по переменному признаку. Недостатком известного устройства является его относительно низкое быстродействие, так как решение о результате сравнения вырабатывается после анализа всех разрядов признака сообщения путем последовательного вычитания импульсов из вычитающих счетчиков, по которым производится сравнение. Цель изобретения - увеличение быстродействия устройства. Поставленная цель достигается тем, что в устройство для поиска данных дополнительно введены элемент НЕ и элемент И, входы которого соединены соответственно с выходами блока импульсов сдвига и элемента НЕ, а выход подключен ко второму дополнительному входу исполнительного бло ка, вход элемента НЕ подключен к выходу преобразователя параллельного кода в последовательный. На чертеже представлена блок-схема уст ройства. Устройство содержит блок 1 приема признаков поискового предписания, блок 2 приема данных, блок 3 сравнения числа совпав ших разрядов с заданным, преобразователь4 параллельного кода в последовательный, вычитающий счетчик 5, блок записи 6, датчик 7 одиночных импульсов, блок 8 импульсов сдвига, блок 9 импульсов установки нуля, линию задержки 10, исполнительный блок 11, блок поразрядного сравнения 12, дополнительный вычитающий счетчик 13, элемент НЕ 14, элемент И 15. Преобразователь 4 параллельного кода в последовательный выполнеН по схеме сдвигового регистра, число разрядов которого равно максимальной разрядности чисел в массиве данных. Устройство работает следующим образом. На блоке записи 6 набирается число, представляющее общее количество подлежащих совпадению разрядов. Данные о поисковых признаках подаются на вход блока Iприема признаков поискового предписания. Импульс пуска осуществляет запись набранного на блоке записи числа в. вычитающие счетчики 5 и 13 и приема чисел в блок 12 поразрядного сравнения. Разряды регистра преобразователя 4 устанавливаются в состояние «1 в соответствии с информацией совпавших разрядов чисел. Одновременно этот же импульс через линию задержки 10 с задержкой, равной времени переключения триггера, поступает на вход блока 8 импульсов сдвига, импульсы которого поступают на преобразователь 4 и осуществляют преобразование записанной информации в соответствующее число последовательных импульсов. Кроме того, импульсы с блока 8 поступают на вход дополнительного вычитающего счетчика 13, осуществляя вычитание, и на первый вход элемента И 15. Импульсы с выхода преобразователя 4 поступают на вход вычитающего счетчика 5 и через элемент НЕ 14 - на второй вход элемента И 15. При поступлении в счетчик 13 количества импульсов, равного числу, предварительно записанному в блоке записи б, счетчик 13 обнуляется и подает на исполнительный блок I1сигнал о конце сравнения. Если при этом количество совпавщих разрядов равно числу, записанному в вычитающий счетчик 5 (следовательно, сравниваемое число совпадает с признаком), то счетчик 5 также устанавливается в нуль, и в результате срабатывает исполнительный блок И. В отличие от известного устройства, если в результате сравнения какой-либо из разрядов в преобразователе 4 не установил (отсутствует совпадение данных с признаком), то при поступлении с блока 8 импульса, соответствующего несовпавшему разряду, на выходе элемента И 15 образуется импульс, поступающий в исполнительный блок 11 и сигнализирующий о несовпадении. Импульс на входе элемента И 15 образуется за счет совпадения сигналов с блока 8 и инверсного сигнала с преобразователя 4 (отсутствие импульса). В результате устройство, не дожидаясь поступления сигналов со счетчиков 5 и 13, может обратиться к анализу следующей информации (данных).

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

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

то средний выигрыш во времени за один цикл сравнения составит

t

I - 2

гдеТ - период следования импульсов сдвига блока 8.

При длине признака п 10, это составит около 60% времени полного цикла сравнения в соответствии со схемой устройства. По сравнению с прототипом быстродействие устройства увеличится более, чем в 2 раза.

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

Таким образом, предложенное устройство обеспечивает более высокое быстродействие

при поиске данных по переменному признаку.