Устройство для определения числа,ближАйшЕгО K зАдАННОМу Советский патент 1981 года по МПК G06F7/04 

{

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

Известно устройство для выбора из множества чисел числа, ближайшего к заданному, которое содержит регистры чисел, регистр для записи заданного числа, два регистра приема чисел, схему определения положения заданного числа относительно двух других, записанных на данном этапе сравнения в регистрах приема, две схемы совпадения и линии задержки 1. Операция выполняется путе.м выполнения (п - Г) цикла выбора из двух очередных чисел числа, ближайшего к заданному (п - количество чисел, сравниваемых с заданным).

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

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

0 получить большее (меньшее) число, то при каждом неравенстве цифр в сравниваемом разряде стираются те числа, у которых в рассматриваемом разряде оказалась меньшая (большая) цифра. Сравнение прекращается после рассмотрения всех разрядов сравниваемых чисел.

Недостатками данного устройства являются невысокие функциональные возможности, заключающиеся в том, что результатом сравнения является выбор только одного экстремального числа и при этом произвести выбор числа, ближайшего к заданно.му с помощью данного устройства невозможно. За исключением экстремальных чисел остальные числа массива уничтожаются, что В целом ряду практических случаев нежелательно или недопустимо. Цель изобретения - расширение функциональных возможностей устройства за счет обеспечения выбора чисел по критериям соотношений. Поставленная цель достигается тем, что в устройстве для определения числа, ближайшего к заданному, содержаш,ем кольцевой сдвигающий регистр заданного числа, п кольцевых сдвигающих регистров, п узлов разделения массива, 2п узлов коммутации, 2п узлов подк;1Ючения, узлы анализа, причем прямой и инверсный выходы кольцевого сдвигающего регистра заданного числа соединены с первым и вторым входом соответственно каждого из узлов разделения массива, а прямой и инверсный выходы каждого i-ro кольцевого сдвигающего регистра, где i 1, 2,...п, подключены к третьему и четвертому входам соответственно i-ro узла разделения массива, первый выход каждого i-ro узла разделения массива соединен с первым входом i-ro узла коммутации и 1--ым входом первого элемента ИЛИ с динамическими входами, выход которого подключен ко вторым входам 1, 2,...п-го узлов коммутации, второй выход каждого i-ro узла разделения массива соединен с первым входом (i + п)-го узла коммутации и с i-ым входом второго э.1емента ИЛИ с динамическими входа ми, выход которого подключен ко вторым входам (п -f- 1), (п -f 2),...2п-1о узлов коммутации, выход каждого i-ro уз.ла коммутации соединен с первь м входом j.-ro узла подключения, 1, 2,...2п, инверсный выход каждого i-ro кольцевого сдвигающего ре1истра соединен со вторыми входами i-iO и (i + п)-го узлов подключеппя, прямой выход каждого i-ro кольцевого сдвнгающе1() регистра соединен с третьими входами i-ro и (i -f п)-го узлов подключения, первый выход каждого j-ro узла подключения подключен к четвертому входу j-ro узла коммутации, второй и третий выходы i-ro уз.1а подключения соединены i-ым и (i + )-ым входами первого узла анализа, второй и третий выходы (i + п)-го узла подключения соединены к i-ому и (i + 1)-ому входам второго узла анализа, выход первого узла анализа соединен с четвертыми входами 1, 2,... п-го узлов коммутации, выход второго узла анализа подключен к четвертым входам (п-ь1), (п + 2) ,...2п-го узлов коммутации, вход устройства соединен с пятыми входами узлов разделения массива. Кроме того, в не.м каждый узел разделепия массива содержит э,1ементы И, триггеры, причем первый вход узла соединеп с первым входом первого элемента И, выход которого подключен ко входу установки в единичное состояние первого триггера, прямой выход которого соединен с первы.м выходом узла, а инверсный выход--с первым входом второго элемента И, выход которого подключен ко входу установки в единичное состояние второго триггера, прямой выход которого соединен со вторым выходом узла, а инверсный выход - со вторым входом первого элемента И, второй вход узла подключен ко второму входу второго элемента И, третий вход узла соединен с третьим входом первого элемента И, четвертый вход узла подключен к третьему входу второго элемента И, пятый вход узла соединен с четвертыми входами элементов И. А также каждый из узлов коммутации состоит из триггеров, элемента ИЛИ и элементов И, причем первый вход узла соединен с первыми входами элеме1 тов И, выход первого элемента И подключен к первому входу элемента ИЛИ, выход которого соединен со входом установки в нулевое состояние первого триггера, второй вход узла подключен ко вторым входам элементов И, выход второго элемента И соединен со входом установки в единичное состояние первого триггера, прямой выход которого подключен к выходу узла и ко входу установки в единичное состояние второго триггера, прямой и инверсный выходы которого соединены с третьими входами элементов И, третий вход узла подключен ко второму входу элемента ИЛИ. Кроме того, каждый из узлов подключения содержит элементы И, причем первый вход узла соединен с первы.ми входами первого и второго элементов И, второй вход узла подключеп ко второму входу первого элемента И и к первому входу третьего элемента И, выход которого соединен с первым выходом узла, третий вход узла подключен ко второму входу Bioporo элемента И, выход которого соединен со вторым выходом узла, четвертый вход узла подключен ко второму входу третьего элемента И, выход первого элемента И соединен с третьим выходом узла. При этом каждый из узлов анализа содержит эле. И и ИЛИ, причем i-ый вход узла, где i 1, 2,...п , соединен с i-ым входом первого эле.мента ИЛИ, выход которого подключен к первому входу элемента И, j-ый вход узла, где (п + 1), (п -f 2)...2п, соединен с (-п)-ым входом второго элемента ИЛИ, выход, которого подключен ко второму входу элемента И, выход которого соединен с выходом узла. На чертеже представлена блок-схема устройства. Устройство содержит кольцевой регистр 1 сдвига заданного числа, кольцевые сдвигающие регистры 2,, 2 2,...2л, узлы 3,, Зг,...3п разделения массива, каждый из которых состоит из элементов И 4 и 5 и триггеров 6 и 7, узлы,8,,...8я.и91, 9 Дкоммутации каждый из котЬрых состоит из триггеров 10 и 11, элементов И 12 и 13 и элемента ИЛИ 14, узлы 15ч, 152,...15« и 16, 16,,... 16„ подключения, каждый из которых состоит из элементов И 17-1.9, узлы 20 ь 20,... 20« анализа, каждый из которых состоит из элементов ИЛИ 21 и 22 и элемента И 23, элементы ИЛИ 24 и 25 с динамическими входами, вход 26 устройства. Устройство работает следующим образом. На вход 26 устройства подается сигнал, который сохраняется до окончания процесса выбора. Этот сигнал отпирает один из элементов И 4 и 5, каждого узла 3 разделения массива в зависимости от соотношения значений рассматриваемого разряда заданного числа и массива чисел. Пусть, например, в рассматриваемом разряде заданного числа записана единица, т.е. имеется сигнал на одном ,из входов элемента И 4. С инверсных выходов старших разрядов регистров 2 чисел, у которых в этом разряде нуль (следовательно, эти числа меньше заданного), подается сигнал на вход элемента И 4. Поскольку имеются единичные сигналы на всех входах элемента И 4, появляется единичный сигнал на его выходе, который переводит триггер 6 в единичное состояние. С исчезновением сигнала на инверсном выходе триггера 6 пропадает сигнал на четвертом входе элемента И 5 и теперь уже до окончания про цесса выбора сохраняется состояние 10 триггеров 6 и 7 для всех чисел, меньших заданного. В результате эти числа из процедуры дальнейшего разделения массива исключаются. Для чисел, у которых в рассматриваемом разряде, как и у заданного числа, записана единица, исходное состояние триггеров 6 и 7 не изменяется. Пусть после продвижения заданного числа и массива чисел на одну позицию в сторону старших разрядов в рассматриваемом разряде заданного числа записан нуль, т.е. имеется сигнал на одном из входов элемента И 5. С прямых выходов старших разрядов регистров чисел, у которых в -этом разряде единица (следовательно, эти числа за исключением выбывших из рассмотрения, больше заданного), подается сигнал на вход элемента И 5. Поскольку для оставшейся части массива чисел имеются сигналы на всех входах элемента И 5, появляется сигнал на его выходе, который переводит триггер 7 в состояние «1. С исчезновением сигнала на инверсном выходе триггера 7 пропадает сигнал на четвертом входе элемента И 4. Таким образом, до окончания процесса выбора состояние «01 триггеров 6 и 7 сохраняется для всех чисел, больших заданного, а сами эти числа из процесса дальнейшего рассмотрения исключаются. Для чисел, у которых в рассматриваемом разряде, как и у заданного числа, записан нуль, исходное состояние триггеров 6 и 7 не изменяется. Аналогичные процессы осуществляются после каждого продвижения чисел по кольцу, в результате чего к подмассивам чисел, меньших и больших заданного, добавляются новые числа. Если в массиве чисел имеется число, равное заданному, то это индицируется исходным состоянием «00 триггеров 6 и 7 данного числа. В соответствии с описанным выше принципом выбора ближайших чисел каждая очередная группа чисел, меньших или больших заданного, полученная на очередном такте, подключается к узла.м анализа для отыскания экстремальных значений следуюшим образом. С появлением сигнала на выходе триггера 6 появляется сигнал на выходе элемента ИЛИ 24 с динамическими входами. Элемент И 13, на всех входах которого теперь имеются единичные сигналы, открывается и переводит триггер 11 в единичное состояние. Появляющийся на прямом выходе триггера 11 сигнал открывает элементы И 17 и 18, в результате чего прямой и инверсный выходы старшего разряда соответствующего кольцевого сдвигающего регистра подключаются к узлу 20i анализа, а также переводит триггер 10 в единичное состояние, подготавлИвая элемент И 12. Аналогичным образом с появлением сигнала на выходе триггера 7 осуществляется подключение обоих выхо-дов старщего разряда соответствующего регистра чисел к узлу 20 анализа. До тех пор, пока тот или иной подмассив не пополнится новыми числами; среди чисел этого подмассива осуществляется поиск экстремального числа. Так,при поиске наибольщего числа среди подмассива чисел, меньщих заданного, работает узел 20 анализа. В том случае, если значения рассматриваемого разряда чисел этого подмассива неодинаковы, т.е. одни числа больше других, появляются сигналы на выходах элементов ИЛИ 21 и 22, а следовательно, на выходе узла 20 анализа. Этот сигнал проходит через открытый элемент И 19 первого узла 15,...,15и подключения, соответствуюшего числу с нулем в рассматриваемом разряде (элемент И 19 открыт сигналом с инверсного выхода регистра данного числа), через элемент ИЛИ 14 соответствующего узла 8,...8п коммутации и возвращает триггер 11 в исходное состояние. Тем самым отключается кольцевой сдвигающий регистр данного числа от дальнейшего анализа, как не удовлетворяющий критерию поиска. В результате для дальнейшего рассмотрения остаются только большие числа подмассива. Если до окончания процесса выбора этот подмассив не пополняется новыми числами, меньшими заданного, то находится наибольшее число, индицируемое состоянием «101 триггеров 6, 7 и 11, которое является ближайшим меньшим по отношению к заданному. Аналогичные действия происходят при поиске наименьшего числа среди подмассива чисел, больших заданного. При этом работают узел 202 анализа и вторые узлы 9,,... 9п коммутации и узлы 16,...,16г. подключения. Полученное наименьшее число, индицируемое состоянием «011 триггеров 6, 7 и 1 является ближайшим большим по отношению к заданному. Число, равное заданному, индицируется, как указывалось ранее, состоянием «000 триггеров 6, 7 и 11. В том случае, если на каком-либо такте нодмасснвы чисел, меньших или больших заданного, понолняются новыми числами, ГО в соответствии с нринципом выбора предыдущие числа подмассивов исключаются из рассмотрения, а экстремальные числа отыскиваются среди новых. Необходимые нереключення осуществляются следующим образом. Элементы И 12 некоторых из узлов 8,,...,8п, коммутации, соответствующих регистрам предыдущих чисел иодмассива, нодготавливаются но двум входам (на прямых выходах триггеров 6 и 10 имеются сигналы) для пропускания сигнала с выхода элемента ИЛИ 24 с динамическими входами. Пусть на некотором такте подмассив чисел, например .меньщих заданного, пополняется новыми числами. При этом срабатывают триггеры 6. и 7 некоторых из узлов 3|Зп разделения массива этих чисел, и сигнал, появляющийся на выходе элемента ИЛИ 24 с динамически.ми входами проходит через подготовленные элементы И 12 соответствующих узлов 8(,...,8п коммутации предыдущих чисел подмассива. Этот сигнал нро.чодит также через элемент ИЛИ 14 и возвращает триггер 11 в исходное состояние, отключая тем самым регистры данных чисел от узлов анализа. Одновременно с этим к узлам анализа подключаются регистры новых чисел подмассивов, как это описано выше. Кольцевые сдвигающие регистры заданного числа, узлы разделения массива, узлы коммутации, узлы подключения, элементы ИЛИ с соответствующими связями позволяют расширить функциональные возможности устройства, поскольку дают возможность при достаточно высоком быстродействии находить в массиве чисел число, ближайшее мепьп1ее, ближайшее большее по отношению к заданному, равное заданному,и при этом пе разрушать информацию в регистрах чисел. Формула изобретения 1. Устройство для определения числа, ближайшего к заданному, содержащее кольцевой сдвигающий регистр заданного числа, п кольцевых сдвигающих регистров, и уз.лов разделения массива, 2п узлов ком.мутации, 2п узлов подключения, узлы анализа, причем прямой и инверсный выходы кольцевого сдвигающего регистра заданного числа соедииены с первым и вторым входом соответственно каждого из узлов разделения массива, а прямой и инверсный выходы каждого i-ro кольцевого сдвигающего регистра. Где i 1, 2,...,п, подключены к третье.му и четвертому входам соответственно i-ro узла разделения массива, отличающееся тем, что, с целью расщирения функциональных возможностей устройства за счет обеспечения выбора чисел по критериям соотношений, в нем первый выход каждого i-ro узла разделения массива соединен с первым входом 1-го узла коммутации и i-ым входом первого элемента ИЛИ с динамическими входами, выход которого подключен ко вторым входам , 2,...п-го узлов ко.ммутации, второй выход каждого i-ro узла разделения массива соединен с первым входом (i -f п)-го узла коммутации и с i-ым входом второго элемен.та ИЛИ с динамическими входами, выход которого подключен ко вторы.м входам (п -f + 1), (п +2),...2п-го узлов ком.мутации, выход каждого j-ro узла коммутации соединен с первым входом j-ro узла подключения, где j 1, 2,...2п, инверсный выход каждого кольцевого сдвигающего регистра соединен со вторыми входами i-ro и (i -f п)-го узлов подключения, пря.мой выход каждого i-ro кольцевого сдвигающего регистра соединен с третьими входами i-ro и (i + + п)-го узлов подключения, первый выход каждого j-го узла подключения подключен к четвертому входу j-го узла коммутации, второй и третий выходы i-го узла подключения соединены с i-ым и (i + 1)-ым входами первого узла анализа, второй и третий выходы (1 + п)-го узла подключения соединены к i-ому и (i + + 1)-ому входам второго узла анализа, выход первого узла анализа соединен с четвертыми входами 1, 2,...п-го узлов коммутации, выход второго узла анализа подключен к четвертым входа.м (п + 1), (п + 2),...2п-го узлов коммутации, вход устройства соединен с пятыми входами узлов разделения массива. .2. Устройство по п. 1, отличающееся тем, что в нем каждый узел разделения массива содержит эле.менты И, триггеры, причем первый вход узла соеди 1ен с первым входо.м первого элемента И, выход которого подключен ко входу установки в единичное состояние первого триггера,прямой выход которого соединен с первым выходом узла, а инверсный выход - с первым входом второго элемента И, выход которого подключен ко входу установки в единичное состояние второго триггера, прямой выход которого соединен со вторым выходом узла, а инверсный выход - со вторым в.ходом первого элемента И, второй вход узла подключен ко второму входу второго элемента И, третий вход узла соединен с третьим входом первого эле.мента И, четвертый вход узла подключен к третьему входу второго эле.мента И, пятый вход узла соединен с четвертыми входа.ми элеMeirroB И. 3. Устройство по п. 1, отличающееся тем, что в пем каждый из узлов коммутации состоит из триггеров, элемента ИЛИ и элементов И, причем первый вход узла соединен с