Устройство для определения числа, ближайшего k заданному

ОП ИСАНИЕИЗОБРЕТЕН ИЯи АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСощиалистическихРеслублик 7777 809166Опубликовано 28.02.81. Бюллетень8Дата опубликования описания 05.03.81 па делам изобретений и открытий(72) Автор изобретения Ю. Д. Полисский Научно-исследовательский и опытно-конструкторский инй 71 тут автоматизации черной металлургии ,11; и(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА,БЛИЖАЙШЕГО К ЗАДАННОМУИзобретение относится к автоматике и вычислительной технике и может быть использовано в системах дискретного управления и цифровых вычислительных машинах.Известно устройство для выбора из множества чисел числа, ближайшего к заданному, которое содержит регистры чисел, регистр для записи заданного числа, два регистра приема чисел, схему определения положения заданного числа относительно двух других, записанных на данном этапе сравнения в регистрах приема, две схемы совпадения и линии задержки (1. Операция выполняется путем выполнения (п - 1) цикла выбора из двух очередных чисел числа, ближайшего к заданному (и - количество чисел, сравниваемых с заданным).Недостатками известного устройства являются невысокое быстродействие и значительные затраты оборудования. Кроме того, поскольку выборка из большого массива данных гю определенным критериям представляет собой важнейшую операцию во всех информационных системах, для построения динамических массивов в информационных системах необходимо знание ближайшего числа к заданному, ближайшего мень 2шего, равного заданному. Это устройство не обеспечивает выбора чисел из массива.Наиболее близким к предлагаемому является устройство, содержащее регистры, узлыанализа, элементы И, ИЛИ, НЕ,элементы задержки, кольцевые сдвигающие регистры (2. В этом устройстве производится одновременное поразрядное сравнение записанных предварительно в кольцевые сдвигающие регистры сравниваемых чисел, начиная со старшего разряда. Если необходимо 1 о получить большее (меньшее) число, то прикаждом неравенстве цифр в сравниваемом разряде стираются те числа, у которых в рассматриваемом разряде оказалась меньшая (большая) цифра. Сравнение прекращается после рассмотрения всех разря дов сравниваемых чисел.Недостатками данного устройства являются невысокие функциональные возможности, заключающиеся в том, что результатом сравнения является выбор только одного экстремального числа и при этом произвести выбор числа, ближайшего к заданному; с помощью данного устройства невозможно. За исключением экстремальных чисел остальные числа массива уничтожаются, что10 15 20 З 0 З 5 40 45 50 55 ь целом ряду практических случаев нежелательно или недопустимо.Цель изобретения - расширение функциональных возможностей устройства за счет обеспечения выбора чисел по критериям соотношений,Г 1 остывлеццыя цель достигается тем, что в устройстве для определения числа, ближайшего к заданному, содержащем кольцевой слвигаюший регистр заланного числа, и кольцевых слвигаюших регистров, и узлов разделения массива, 2 п узлов коммутации, 2 п узлов подключения, узлы анализа, причем прямой и инверсный выходы кольцевого слвигающего регистра заданного числя соединены с первым и вторым входом соответственно каждого из узлов разделения массивы, ы прямой и инверсный выходы каждого 1-го кольцевого слвигаюгцего регистра, гле =- 1, 2,.п, подключены к третьему и четвертому входам соответствен"о 1-го узла разделения массива, первый выход каждого 1-го узла разделения массива сослицец с первь.м входом 1-го узла коммутации и 1-ым входом первого злемецта ИЛИ с динамическими входами, выход которого подключен ко вторым входам 1, 2 п-го узлов коммутации, второй выход каждого 1-го узла разделения массивы соединен с первым входом (1 - и)- -го узлы коммутации и с 1-ым входом второго элементы ИЛИ с динамическими входы ми, выход которого подключен ко вторым входам (и + 1), (и + 2),2 п-го узлов коммутации, Выход каждого -го узла коммутациии соединен с первым входом -гс узла подключения, где= 1, 2,2 п, ицьерсный выход каждого 1-го кольцевого слвигыюшего рсгистря соединен со вторыми входами 1-го и+ и)-го узлов подключения, прямой вы. хол каждого 1-го кольцевого слвцгяюсцего регистра соединен с третьими входами 1-го и (1+ и)-го узлов полклюцсция, первый выход каждого )-го узла подключения подключен к четвертому входу )-го узла коммутации, второй и третий выходы 1-го узлы подключения соединены 1-ым и (1 - , - 1) -ым входами первого узла анализа, второй и третий выходы (1+ п)-го узла подключения соединены к 1-ому и (1+ 1)-ому входам второго узла анализа, выход первого узла анализа соединен с четвертыми входами 1, 2, и-го узлов коммутации, выход второго узла анализа подключен к четвертым входам (п +1), (и + 2)2 п-го узлов комму 1 ыции, вход устройства соединен с пятыми входами узлов разделения массива.Кроме того, в нем каждый узел разделения массива содержит элементы И, триггеры, причем первый вход узла соелицец с первым входом первого элемента И, выход которого подключен ко входу установки в сдиничное состояние первого триггера, прямой выход которого соединен с первым выходом узла, а инверсный выход - с цсрвым входом второго элемента И, выход которого подключен ко входу установки в елиниццое состояние второго триггера, прямой выход которого соединен со вторым выходом узла, а инверсный выход - со вторым входом первого элемента И, второй вход узла подключен ко второму входу второго элемента И, третий вход узла соединен с третьим входом первого элемента И, четвертый вхол узла подключен к третьему входу второго элемента И, пятый вход узла соединен с четвертыми входами элементов И. А также каждый из узлов коммутации состоит из триггеров, элемента ИЛИ и элементов И, причем первый вход узла соединен с первыми входами элементов И, выход первого элемента И подключен к первому входу элемента ИЛИ, выход которого соединен со вхолом установки в нулевое состояние первого триггера, второй вход узла подключен ко вторым входам элементов И, выход второго элемента И соединен со входом установки в единичное состояние первого триггера, ппямой выход которого подключен к выходу узла и ко входу установки в единичное состояние второго триггера, прямой и инверсный выходы которого соединены с третьими входами элементов И, третий вход узла подключен ко второму входу элеИ 11 И Кроме того, каждый из узлов подключения содержит элементы И, причем первый вход узла соединен с первыми входами первого и вгорого элементов И, второй вход узла потключен ко второму входу первого элемента И и к первому входу третьего элементы И, выход которого соелинен с первым выходом узла, третий вход узла подключен ко второму входу в орого элемента И, выход которого соединен со вторым выходом узла, четвертый вход узла подключен ко второму входу третьего элемента И, выход первого элемента И соединен с третьим выходом узла.При этом каждый из узлов анализа содержит элементы И и ИЛИ, причем 1-ый вход узла, где 1 =- 1, 2,п; соединен с 1-ым входом первого элемента ИЛИ, выход которого подключен к первому входу элемента И, 1-ый вход узла, где) = (п + 1), (и + 2) 2 п, соединен с- п) -ым входом второго элемента ИЛИ, выход которого подклюцен ко второму входу элемента И, выход которого соединен с выходом узла.г 1 я чертеже представлена блок-схема устройства.Устройство содержит кольцевой регистр 1 сдвига заданного числа, кольцевые сдвигаюшие регистры 2 2 ъ" 2, узлы 3 3," 3 разделения массива, каждый из которых состоит из элементов И 4 и 5 и триггеров 6и 7, узлы Д 8 д,8 и 94, 94.4 коммутации каждый из которых состоит из триггеров 10 и 11, элементов И 2 и 13 и элемента ИЛИ 14, узлы 15 15,15, и 16 168091 5о в рассматриваемом разряде заданного числа записана единица, т.е. имеется сигнал на одном из входов элемента И 4. С инверсных выходов старших разрядов регистров 2 чисел, у которых в этом разряде нуль (следовательно, эти числа меньше заданного), подается сигнал на вход элемента И 4. Поскольку имеются единичные сигналы на всех входах элемента И 4, появляется единичный 20 сигнал на его выходе, который переводит триггер 6 в единичное состояние. С исчезновением сигнала на инверсном выходе триггера 6 пропадает сигнал на четвер-ом входе элемента И 5 и теперь уже до окончания процесса выбора сохраняется состояние 1025 триггеров 6 и 7 для всех чисел, меньших заданного. В результате эти числа из процедуры дальнейшего разделения массива исключаются. Для чисел, у которых в рассматриваемом разряде, как и у заданного числа, записана единица, исходное состояние триггеров 6 и 7 не изменяется. Аналогичные процессы осуществляются пос-ле каждого продвижения чисел по кольцу, в результате чего к подмассивам чисел, меньших и больших заданного, добавляются но 16, подключения, каждый из которых состоит из элементов И 17 - 19, узлы 20 ь 20,20. анализа, каждый из которых состоит из элементов ИЛИ 21 и 22 и элемента И 23,элементы ИЛИ 24 и 25 с динамическими входами, вход 26 устройства.Устройство работает следующим образом. На вход 26 устройства подается сигнал, который сохраняется до окончания процесса выбора. Этот сигнал отпирает один из элементов И 4 и 5, каждого узла 3 разделения массива в зависимости от соотношения значений рассматриваемого разряда заданного числа и массива чисел. Пусть, например,Пусть после продвижения заданного числа и массива чисел на одну позицию в сторону старших разрядов в рассматриваемом разряде заданного числа записан нуль, т.е. имеется сигнал на одном из входов элемента И 5. С прямых выходов старших разрядов регистров чисел, у которых в этом разряде единица (следовательно, эти числа за исключением выбывших из рассмотрения, больше заданного), подается сигнал на вход элемента И 5, Поскольку для оставшейся части массива чисел имеются сигналы на всех входах элемента И 5, появляется сигнал на его выходе, который переводит триггер 7 в состояние 1. С исчезновением сигнала на инверсном выходе триггера 7 пропадает сигнал на четвертом входе элемента И 4. Таким образом, до окончания процесса выбора состояние 01 триггеров 6 и 7 сохраняется для всех чисел, больших заданного, а сами эти числа из процесса дальнейшегс рассмотрения исключаются. Для чисел, у которых в рассматриваемом разряде, как и у заданного числа, записан нуль, исходное состояние триггеров 6 и 7 не изменяется. 35 40 45 50 66вые числа. Если в массиве чисел имеется число, равное заданному, то это индицируется исходным состоянием 00 триггеров 6 и 7 данного числа.В соответствии с описанным выше принципом выбора ближайших чисел каждая очередная группа чисел, меньших или больших заданного, полученная на очередном такте, подключается к узлам анализа для отыскания экстремальных значений следующим образом.С появлением сигналаа выходе триггера 6 появляется сигнал на выходе элемента ИЛИ 24 с динамическими входами. Элемент И 13, на всех входах которого теперь имеются единичные сигналы, открывается и переводит триггер 11 в единичное состояние. Появляющийся на прямом выходе триггера 11 сигнал открывает элементы И 17 и 18, в результате чего прямой и инверсный выходы старшего разряда соответствующего кольцевого сдвигающего регистра подключаются к узлу 20 анализа, а также переводит триггер 10 в единичное состояние, подготавливая элемент И 12. Аналогичным образом с появлением сигнала на выходе триггера 7 осуществляется подключение обоих выходов старшего разряда соответствующего регистра чисел к узлу 20 анализа. До тех пор, пока тот или иной подмассив не пополнится новыми числами, среди чисел этого подмассива осуществляется поиск экстремального числа. Так,при поиске наибольшего числа среди подмассива чисел, меньших .заданного, работает узел 20, анализа. В том случае, если значения рассматриваемого разряда чисел этого подмассива неодинаковы, т.е. одни числа больше друпх, появляются сигналы на выходах элементов ИЛИ 21 и 22, а следовательно, на выходе узла 20 анализа. Этот сигнал проходит через открытый элемент И 9 первого узла 1515 подключения, соответствующего числу с нулем в рассматриваемом разряде (элемент И 19 открыт сигналом с инверсного выхода регистра данного числа), через элемент ИЛИ 14 соответствующего узла 8,8 коммутации и возвращает триггер 11 в исходное состояние. Тем самым отключается кольцевой сдвигающий регистр данного числа от дальнейшего анализа, как не удовлетворяющий критерию поиска. В результате для дальнейшего рассмотрения остаются только большие числа подмассива. Если до окончания процесса выбора этот подмассив не пополняется новыми числами, меньшими заданного, то находится наибольшее число, индицируемое состоянием 101 триггеров 6, 7 и 11, которое является ближайшим меньшим по отношению к заданному.Аналогичные действия происходят при поиске наименьшего числа среди подмассива чисел, больших заданного. При этом работают узел 20 анализа и вторые узлы 9,9 коммутации и узлы 1616 подключе 809166ния. Полученное имеее ело, индицируемое состоянием 011 триггеров 6, 7 и 1 является ближайшим большим по отношению к заданному. Число, равное заданному, индицируется, как указывалось ранее, состоянием 000 триггеров 6, 7 и 11.В том случае, если на каком-либо такте подмасспвы чисел, меньших или больших заданного, пополняются новыми числами, то в соответствии с принципом выбора предыд) шие числа подмассивов исключаются нз рассмотрения, а экстремальные числа 10 отыскиваются среди новых. Необходимые переключения осуществляются следующим образом. Элементы И 12 некоторых из узлов 8,8, коммутации, соответствуюших регистрам предыдущих чисел подмассива, под 5 готавливаются по двум входам (на прямых выходах триггеров 6 и 10 имеются сигналы) для пропускания сигнала с выхода элемента ИЛИ 24 с динамическими входами. Пусть на некотором такте подмассив чисел, например меньших заданного, пополняется новыми числами. При этом срабатывакт триггеры 6. и 7 некоторых из узлов 3 ь,3, разделения массива этих чисел, и сигнал, появляюшийся на выходе элемента ИЛИ 24 с динамическими входами, проходит через подготовленные элементы И 12 25 соответствуюших узлов 8, ,8, коммутации предыдуших чисел подмассива. Этот сигнал проходит также через элемент ИЛИ 14 и возвращает триггер1 в исходное состояние, отключая тем самым регистры данных чисел от узлов анализа. Одновременно с этим к30 узлам анализа подключаются регистры новых чисел подмассивов, как это описано выше.Кольцевые сдвигаюшие регистры заданного числа, узлы разделения массива, узлы З 5 коммутации, узлы подключения, элементы ИЛИ с соответствующими связями позволяют расширить функциональные возможности устройства, поскольку дают возможность при достаточно высоком быстродействии40 находить в массиве чисел число, ближайгцее меньшее, ближайшее большее по отношению к заданному, равное заданному,и при этом не разрушать информацию в регистрах чисел.Формула изобретения1. Устройство для определения числа, ближайшего к заданному, содержашее кольцевой сдвигакШий регистр заданного числа, 50 и кольцевых сдвигаюших регистроь, и узлов разделения массива, 2 п узлов коммутации, 2 п узлов подключения, узлы анализа, причем прямой и инверсный выходы кольцевого сдвигаюшего регистра заданного числа соединены с первым и вторым входом соответственно каждого из узлов разделения массива, а прямой и инверсный выходы каждого 1-го кольцевого сдвигаюшего регистра, где= 1, 2п, подключены к третьему и четвертому Входам соответственно 1-го узла разделения массива, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет обеспечения выбора чисел по критериям соотношений, в нем первый выход каждого 1-го узла разделения массива соединен с первым входом 1-го узла коммутации и 1-ым входом первого элемента ИЛИ с динамическими входами, выход которого подключен ко вторым входам 1, 2,п-го узлов коммутации, второй выход каждого 1-го узла разделения массива соединен с первым входом (1+ и)-го узла коммутации и с 1-ым входом второго элемента ИЛИ с динамическими входами, выход которого подключен ко вторым входам (и + + 1), (и + 2),2 п-го узлов коммутации, выход каждого )-го узла коммутации соединен с первым входом 1-го узла подключения, где ) = 1, 2,2 п, инверсный выход каждого 1-го кольцевого сдвигаюшего регистра соединен со вторыми входами 1-го и (1 -+ и) -го узлов подключения, прямой выход каждого 1-го кольцевого сдвигаюшего регистра соединен с третьими входами 1-го и (1 + + п) - го узлов подключения, первый выход каждого ) - го узла подключения подключен к четвертому входу ) - го узла коммутации, второй и третий выходы 1 - го узла подключения соединены с 1-ым и (1+ 1)-ым входами первого узла анализа, второй и третий выходы ( + п)-го узла подключения соединены к 1-ому и (1+ + 1)-ому входам второго узла анализа, выход первого узла анализа соединен с четвертыми входами 1, 2,п-го узлов коммутации, выход второго узла анализа подключен к четвертым входам (и + 1), (п + 2),2 п-го узлов коммутации, вход устройства соединен с пятыми входами узлов разделения массива.2. Устройство по п, 1, отличающееся тем, что в нем каждый узел разделения массива содержит элементы И, триггеры, причем первый вход узла соединен с первым входом первого элемента И, выход которого подключен ко входу установки в единичное состояние первого триггера, прямой выход которого соединен с первым выходом узла, а инверсный выход - с первым входом второго элемента И, выход которого подключен ко входу установки в единичное состояние второго триггера, прямой выход которого соединен со вторым выходом узла, а инверсный выход - со вторым входом первого элемента И, второй вход узла подключен ко второму входу в 1 орого элемента И, третий вход узла соединен с третьим входом первого элемента И, четвертый вход узла подключен к третьему входу в;орого элемента И, пятый вход узла соединен с четвертыми входами элементов И.3. Устройство по п. 1, отличающееся тем, что в нем каждый из узлов коммутации состоит из триггеров, элемента ИЛИ и элементов И, причем первый вход узла соединен с8091 66 10 9первыми входами элементов И, выход первого элемента И подключен к первому входу элемента ИЛИ, выход которого соединен со входом установки в нулевое состояние первого триггера, второй вход узла подключен ко вторым входам элементов И, выход второго элемента И соединен со входом установки в единичное состояние первого триггера, прямой выход которого подключен к выходу узла и ко входу установки в единичное состояние второго триггера, прямой и инверсный выходы которого соединены с третьими вхо дами элементов И, третий вход узла подключен ко второму входу элемента ИЛИ.4. Устройство по п. 1, отличающееся тем, что в нем каждый из узлов подключения содержит элементы И, причем первый вход5 узла соединен с первыми входами первого и второго элементов И, второй вход узла подключен ко второму входу первого элемента И и к первому входу третьего элемента И, выход которого соединен с первым выходом узла, третий вход узла подключен ко второ му воду второго элемента И, выход которого соединен со вторым выходом узла, четвертый вход узла подключен ко второму входу третьего элемента И, выход первого элемента И соединен с третьим выходом узла.5. Устройство по п. 1, отличающееся тем, что в нем каждый из узлов анализа содержит элементы И и ИЛИ, причем 1-ый вход узла, где 1 = 1, 2,п, соединен с 1-ым входом первого элемента ИЛИ, выход которого подключен к первому входу элемента И, .-ый вход узла, где ) = (и + 1), (п + 2),2 п, соединен с- п)-ым входом второго элемента ИЛИ, выход которого подключен ко второму входу элемента И, выход которого соединен с выходом узла.Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССРМ 356643, кл. б 06 Г 7/02, 23.10,72, 2. Авторское свидетельство СССРМо 193160, кл, б 06 Г 14/01, 02.03.67(прототип).БелкинКорректор МПодписноетета СССРткрытийнаб., д. 4/5ул Проектная 4 дактор АЛежнинказ 17/58 Составитель В. а Техред А. Бойкас Тираж 756 ВНИИПИ Государственного коми по делам изобретений и о 113035, Москва, Ж - 35, Раушская илиал ППП Патент, г. Ужгород, мчи