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

 

О П И С А Н И Е < 809166

ИЗО6РЕТЕН ИЯ

АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Сощиалистических

Реслублик (61) Дополнительное к авт. свид-ву— (22) Заявлено 28.04.79 (21) 2759529/18-24 с присоединением заявки №вЂ” (23) Приоритет— (51) М. Кл.

С7 06 F 7/04

Государственный комитет (53) УДК 681.325..5 (088.8) Опубликовано 28.02.81. Бюллетень № 8

Дата опубликования описания 05.03.81 па делом изобретений и открытий (72) Автор изобретения

Ю. Д. Полисский

Научно-исследовательский и опытно-конструкторский институт автоматизации черной металлургии,11 7 (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА, БЛИЖАЙШЕГО К ЗАДАННОМУ

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

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

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

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

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

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

809166

20 5

З5

55 ь целом ряду практических случаев нежелытельно или недопустимо.

Цель изобретения — расширение функциональных возможностей устройства за счет обеспечения выбора чисел по критериям соотношений, Г1осты 0;I(. ll))dя II(ëь достигается T(.м, что е3 устройстве для определения числа, ближайшего к заданному, содержащем кольцевой сдвигающий регистр заданного числа, и кольцевых сдвигающих регистров, и узлов разделения массива, 2п узлов коммутации, 2п узлов подключения, узлы анализа, причем прямой и инверсный выходы кольцевого сдвигающего регистра заданного числя соединены с первым и вторым входом соответственно каждого из узлов разделения массивы, ы прямой и инверсный выходы каждого i-Io кольцевого сдвигающего регистра, где

=- 1, 2,...n, подключены к третьему и четвертому входам соответствен"о )-го узла разделения массива, первый выход каждого I-го узла разделения массива соединен с первь)ч входом I-го узла коммутации и I -ым входом первого элеме)ета ИЛИ с динамическими входами, выход которого подключен ко втoрым входам 1, 2,...n-го узлов коммутации, второй выход каждого I-го узла разделения массивы соединен с первым входом () )- и)-го узла коммутации и с I-ым входом 01орого элемента ИЛИ с динамическими вход() ми, выход которого подключен ко вторым входам (и + 1), (и + 2),...2п-го узлов ко;Iмутации, выход каждого J-гo узла Koì3)ó I ыцпи соединен с первым входом j.-го узла «п1ключения, где = 1, 2,...2п, иньерсный выход каждого I-гo кольцевого сдвигыющегo регистра соединен со вторыми входами )-го и (I + и)-го узлов подключения, прямой выход каждого )-го кольцевого с,)вигякнце) о регистра соединен с третьими вхоцами l-го и (i + и)-го узлов подключения, первый выход каждого j-го узла подключения lloaключен к четвертому входу j-гo узла коммутации, второй и третий выходы I-гo узлы подключения соединены I -ым и (I —,— 1) -ым входами е;ервого узла анализа, второй и третий выходы () + п)-го узла подключения соединены к )-ому и (I + 1)-оМУ входам второго узла анализа, выход первого узла анализа соединен с четвертыми входами 1, 2,... и-го узлов коммутации, выход второго узла анализа подключен к четвертым входам (и +1), (и + 2),...2п-го узлов коммутации, вход устройства соединен с пятыми входdми узлов разделения массива.

Кроме того, в нем каждый узел разделения массива содержит элементы И, триггеры, причем первый вход узла сое ),II>I(II c первым входом первого элемента II, выход которого подключен ко входу установки в сдиничное состояние первого триггера, прямой выход которого соединен с первым выходом узла, а инверсный выход — с п(рвым входом второго элемента И, выход которого подключен ко входу установки в единичное состояние второго триггера, прямой выход которого соединен со вторым выходом узла, а инверсный выход — со вторым входом первого элемента И, второй вход узла подключен ко второму входу второго элемента И, третий вход узла соединен с третьим входом первого элемента И, четвертый вход узла подключен к третьему входу второго элемента И, пятый вход узла соединен с четвертыми входами элементов И.

А также каждый из узлов коммутации состоит из триггеров, элемента ИЛИ и элементов И, причем первый вход узла соединен с первыми входами элементов И, выход первого элемента И подключен к первому вхо)у элемента ИЛИ, выход которого соединен со входом установки в нулевое состояние первого триггера, второй вход узла подключен ко вторым входам элементов И, вых()д второго элемента И соединен со входом установки в единичное состояние первого триггера, прямой выход которого подключен к выходу узла и ко входу установки в единичное состояние второго триггера. прямой и инверсный выходы которого соединены с третьими входами элементов И, третий вход узла подключен ко второму входу элеlvl(IIT2 ИЛИ.

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

При этом каждый из узлов анализа содер>кит элементы И и ИЛИ, причем i-ый вход узла, где i =- 1, 2,...п; соединен с i-ым входом первого элемента ИЛИ, выход которого подключен к первому входу элемента И, j-ый вход узла, где j = (п + 1), (и + 2) ...2п, соединен с (j - n) -ым входом второго элемента ИЛИ, выход которого подключен ко второму входу элемента И, выход которого соединен с выходом узла.

Ня чертеже представлена блок-схема устройства.

Устройство содержит кольцевой регистр 1 сдвига заданного числа, кольцевые сдвигающие регистры 2 ь 2ъ...2», узлы 3», 3,,...3 разделения массива, каждый из которых состоит из элементов И 4 и 5 и триггеров 6 и 7, узлы Я, 8д,...8((и 94, 94 .9„коммутации каждый из которых состоит из триггеров

l0 и 11, элементов И 12 и 13 и элемента

ИЛИ 14, узлы 15, 15,...15 и 16,, 16,,...

8091

5 ! о в рассматриваемом разряде заданного числа записана единица, т.е. имеется сигнал на одном из входов элемента И 4. С инверсных выходов старших разрядов регистров 2 чисел, у которых в этом разряде нуль (следовательно, эти числа меньше заданного), подается сигнал на вход элемента И 4. Поскольку имеются единичные сигналы на всех входах элемента И 4, появляется единичный 20 сигнал на его выходе, который переводит триггер 6 в единичное состояние. С исчезновением сигнала на инверсном выходе триггера 6 пропадает сигнал на четвер-ом входе элемента И 5 и теперь уже до окончания процесса выбора сохраняется состояние »10»

25 триггеров 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 не изменяется.

66 вые числа. Если в массиве чисел имеется число, равное заданному, то это индицируется исходным состоянием «00» триггеров 6 и 7 данного числа.

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

С появлением сигнала <а выходе триггера 6 появляется сигнал на выходе элемента ИЛИ

24 с динамическими входами. Элемент И 3, на всех входах которого теперь имеются единичные сигналы, открывается и переводит триггер 11 в единичное состояние. Появляющийся на прямом выходе триггера 11 сигнал открывает элементы И 17 и 18, в результате чего прямой и инверсный выходы старшего разряда соответствующего кольцевого сдвигающего регистра подключаются к узлу 20< анализа, а также переводит триггер IO в единичное состояние, подготавливая элемент И 12. Аналогичным образом с появлением сигнала на выходе триггера 7 осуществляется подключение обоих выхо-. дов старшего разряда соответствующего регистра чисел к узлу 20 анализа. До тех пор, пока тот или иной подмассив не пополнится новыми числами, среди чисел этого подмассива осуществляется поиск экстремального числа. Так,при поиске наибольшего числа среди подмассива чисел, меньших . заданного, работает узел 20< анализа. В том случае, если значения рассматриваемого разряда чисел этого подмассива неодинаковы, т.е. одни числа больше друп<х, появляются сигналы на выходах элементов ИЛИ 21 и

22, а следовательно, на выходе узла 20< анализа. Этот сигнал проходит через открытый элемент И 19 первого узла 15q,...,15, подключения, соответствующего числу с нулем в рассматриваемом разряде (элемент

И 19 открыт сигналом с инверсного выхода регистра данного числа), через элемент

ИЛИ 14 соответствующего узла 8<,...8 коммутации и возвращает триггер 11 в исходное состояние. Тем самым отключается коль- цевой сдвигающий регистр данного числа от дальнейшего анализа, как не удовлетворяющий критерию поиска. В результате для дальнейшего рассмотрения остаются только большие числа подмассива. Если до окончания процесса выбора этот подмассив не пополняется новыми числами, меньшими заданного, то находится наибольшее число, индицируемое состоянием «101» триггеров 6, 7 и 11, которое является ближайшим меньшим по отношению к заданному.

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

9„коммутации и узлы 16<,...,16 подключе809166 ния. Полученное наименьшее число, индицируемое состоянием «011» триггеров 6, 7 и 1 является ближайшим большим по отношению к заданному. Число, равное заданному, индицируется, как указывалось ранее, состоянием «000» триггеров 6, 7 и 11.

В том случае, если на каком-либо такте подмасспвы чисел, меньших или больших заданного, пополняются новыми числами, то в соответствии с принципом выбора предыд) щие числа подмассивов исключаются из рассмотрения, а экстремальные числа I0 отыскиваются среди новых. Необходимые переключения осуществляются следующим 00разом. Элементы И 12 некоторых из узлов

8,,...,8», коммутации, соответствующих регистрам предыдущих чисел подмассива, подiS готавливаются по двум входам (на прямых выходах триггеров 6 и 10 имеются сигналы) для пропускания сигнала с выхода элемента ИЛИ 24 с динамическими входами. Пусть на некотором такте подмассив чисел, например меньших заданного, пополняется новыми числами. При этом срабатывак>т триггеры 6. и 7 некоторых из узлов

3 ь...,З„разделения массива этих чисел, и сигнал, появляющHAcH на выходе элемента

ИЛИ 24 с динамическими входами, проходит через подготовленные элементы И 12 25 соотвеTcTBYIQLLIHx узлов 8 I,...,8, коммутации предыдущих чисел подмассива. Этот сигнал проходит также через элемент ИЛИ 14 и возвращает триггер 1 в исходное состояние, отключая тем самым регистры данных чисел оТ узлов анализа. Одновременно с этим к

ЗО узлам анализа подключаются регистры новых чисел подмассивов, как это описано вышс.

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

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

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

@op»Igла изобретения

1. Устройство для определения числа, ближайшего к заданному, содержащее кольцевой сдвигак>щий регистр заданного числа, 50 и кольцевых сдвнгающих регистроь, и узлов разделения массива, 2п узлов коммутации, 2п узлов подключения, узлы анализа, причем прямой и инверсный выходы кольцевого сдвигаюшего регистра заданного числа соедиí Hbl с первым и вторым входом соответственно каждого из узлов разделения массива, а прямой и инверсный выходы каждого i-го кольцевого сдвигающего регистра, где

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

i-го узла коммутации и i-ым входом первого элемента ИЛИ с динамическими входами, выход которого подключен ко вторым вхо дам 1, 2,...n-го узлов коммутации, второй выход каждого i-го узла разделения массива соединен с первым входом (i + n)-го узла коммутации и с I-ым входом второго элемента ИЛИ с динамическими входами, выход которого подключен ко вторым входам (и +

+ 1), (и + 2),...2п-го узлов коммутации, выход каждого j-го узла коммутации соединен с первым входом j ãî узла подключения, где j = 1, 2,...2п, инверсный выход каждого

i-го кольцевого сдвигающего регистра соединен со вторыми входами 1-го и (I --!- и) -го узлов подключения, прямой выход каждого

i-lo кольцевого сдвигающего регистра соединен с третьими входами i-го и (i +

+ n) — го узлов подключения, первый выход каждого j — го узла подключения подключен к четвертому входу j — го узла коммутации, второй и третий выходы i — го узла подключения соединены с

1-ым и (I + 1)-ым входами первого узла анализа, второй и третий выходы (i + и)-го узла подключения соединены к 1-ому и (1 +

+ 1)-ому входам второго узла анализа, выход первого узла анализа соединен с четвертыми входами 1, 2,...n-го узлов коммутации, выход второго узла анализа подключен к четвертым входам (и + 1), (п + 2),...2п-го узлов коммутации, вход устройства соединен с пятыми входами узлов разделения массива.

2. Устройство по п. 1, отличающееся тем, что в нем каждый узел разделения массива содержит элементы И, триггеры, причем первый вход узла соеди.ген с первым входом первого элемента И, выход которого подключен ко входу установки в единичное состояние первого триггера, прямой выход которого соединен с первым выходом узла, а инверсный выход — с первым входом второго элемента И, выход которого подключен ко входу установки в единичное состояние второго триггера, прямой выход которого соединен со вторым выходом узла, а инверсный выход — co вторым входом первого элемента И, второй вход узла подключен ко второму входу в1орого элемента И, третий вход узла соединен с третьим входом первого элемента И, четвертый вход узла подключен к третьему входу в;орого элемента И, пятый вход узла соединен с четвертыми входами элементов И.

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

8091

10

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

Техред А. Бойкас Корректор М. немчик

Тираж 756 Подписное

Редактор А..Лежнина

Заказ 17/58

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

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

Филиал ППП «Патент», г. Ужгород, ул. Проектная, 4

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

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

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

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

5. Устройство по п. 1, отличающееся тем, что в нем каждый из узлов анализа содержит элементы И и ИЛИ, причем i-ый вход узла, где 1 = 1, 2,...п, соединен с 1-ым входом первого элемента ИЛИ, выход которого подключен к первому входу элемента И, -ый вход узла, где j = (и + 1), (п + 2),...

2п, соединен с (j - п) -ым входом второго элемента ИЛИ, выход которого подключен ко второму входу элемента И, выход которого соединен с выходом узла.

Источники информации, принятые во внимание при экспертизе

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

М 356643, кл. G 06 F 7/02, 23.10.72, 2. Авторское свидетельство СССР

Ме 193160, кл. G 06 F 14/01, 02.03.67(прототип).