Устройство для упорядочения переменных

 

о и и Ыд йское

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

Социвлистическик

Республик

< 734675

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 20.02.78 (21) 2581765/18-24 с присоединением заявки №вЂ” (23) Приоритет— (51) М. Кл.

G 06F 7/06

Гасударстаеивй камитет.

СССР

Опубликовано 15.05.80. Бюллетень № 18

Дата опубликования описания 17.05.80 (53) УДК 681.333 (088.8) ао делам изебретеиий и открытий

А. Г. Додонов, В. В. Федотов, Н. В. Федотов, В. В. Хаджинов и А. М. Щетинин (72) Авторы изобретения

Институт электродинамики АН Украинской ССР (71) Заявитель (54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ ПЕРЕМЕННЫХ

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

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

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

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

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

Недостаток этого устройства — недостаточная точность.

Цель изобретения — повышение точности устройства.

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

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

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

46

4s

so

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

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

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

Устройство включает формирователи

I q — 1„значений переменных< коммутирующие блоки 21 — 2„, блок 3 управления, регенерационный счетчик 4, триггер 5, элементы 6 — 8 ИЛИ, элементы 9 — 12 И.

Каждый из формирователей < значений переменных, число которых равно числу упорядочиваемых переменных и числу ячеек коммутирующих блоков содержит счетчики 13 и 14 импульсов, триггер 15 и элемент 16 И. Входы 17 всех формирователей

5 о

20 и

jo

35 значений переменных объединены со входом регенерационного счетчика 4 и с выходом элемента 10 И. Вход 18 каждого формирователя значений переменных подключен к разрядному выходу соответствующего коммутирующего блока, а выход 19 к установочному входу того же блока к соответствующему входу элемента 8 ИЛИ. Полюса 20 формирователей 1 — 1 объединены с выходом 21 блока управления и входом элемента 6 ИЛИ а входы 22 подключены к выходу элемента И 11.

Коммутирующие блоки представляющие собой идентичные ячейки, число которых равно числу упорядочиваемых переменных, предназначены для организации последовательного формирования значений переменных, у которых сформирован номер последовательности. В состав каждого блока 2д входят триггеры 23 и 24, элементы И 25, 26, 27 и 28.

Предлагаемое устройство позволяет осуществить упорядочение переменных как по возрастанию, так и по убыванию. При упорядочении переменных по возрастанию в счетчик 13 каждого формирователя 1!. значений переменных заносится число импульсов (N — f„), где N — емкость счетчика 13; (. — число импульсов, пропорциональное величине i-ой переменной.

При упорядочении переменных по убыванию в счетчик 13 модели (; заносится число импульсов пропорциональное величине

i-ой переменной.

Работа устройства при упорядочении переменных по возрастанию и убыванию аналогична. При упорядочении переменных только по убыванию после занесения каждой упорядочиваемой переменной в соответствующий формирователь 1«, триггер 5, регенерационный счетчик 4, триггеры 23, 24 блоков 2 и счетчики 14 всех формирователей устанавливаются в нулевое состояние. с

Процесс упорядочения переменных состоит из последовательно говторяющихся циклов и начинается с момента подачи импульса «пуск» блоком 3 управления, в функции которого входит также выработка импульсов ГИь ГИ и ГИ», сдвинутых относительно друг друга. Импульс «пуск» с полюса 21 блока 3 управления поступает ка полюса 20 всех формирователей 1 — 1 а также устанавливает триггер 5 через элемент 6 ИЛИ в единичное состояние. В каждом формирователе 1 импульс «пуск» с полюса 20 поступает на вход триггера 15 и устанавливает его в единичное состояние.

Импульсы ГИ с полюса 20 блока управления поступают через элемент 10 И на вход регенерационного счетчика 4 и через полюс

17 на входы счетчиков 13 всех формирователей 1 — 1„. Импульсы ГИ поступают на вход регенерационного счетчика и на полюс

17 формирователей до тех пор, пока на по734675

1о

5 люсе 19 с выхода счетчика 13 какого-либо формирователя не появится импульс переполнения. С появлением импульса переполнения на полюсе 19 происходит блокировка входа элемента 10 И. Это осуществляется следующим образом.

Импульс с полюса 19 поступает на один из входов элемента 8 ИЛИ, а с выхода элемента 8 ИЛИ этот сигнал проходит через элемент 7 ИЛИ и устанавливает в нулевое состояние триггер 5. Нулевое состояние триггера 5 запрещает поступление импульсов

ГИ1 через элемент 10 И. Импульс переполнения, поступивший на установочный вход соответствующего коммутирующего блока с полюса 19, устанавливает триггер 23 через элемент 25 И в единичное состояние.

Нулевое состояние триггера 5 выдает разрешение на вход элементов 9, 11 и 12 И. В результате чего импульсы ГИ начинают поступать через элемент 11 И на полюсе 22 всех формирователей 1> — 1„, а импульсы ГИ с полюса 30 блока 3 управления через элемент 9 И поступают на управляющий вход

31 первого блока 21. Блок 3 управления вырабатывает также на полюсе 32 импульсы

ГИ, сдвинутые относительно серии импульсов ГИ . Импульсы ГИ поступают через элемент 12 И на синхронизирующие входы

331 — 33m. всех блоков 2.

Первый импульс ГИ 1, поступающий на полюс 22, заносится в счетчик 14 через элемент И всех формирователей 1q — 1п, Следующий за импульсом ГИ;, импульс ГИг поступает на полюс 31 первого блока 21 и распространяется по распределителю, пока не дойдет до выбранного блока, который соответствует формирователю с переполнивши мся счетч и ком 13.

Происходит это следующим образом.

Предварительно триггеры 23 и 24 устанавливаются в нулевое состояние. При появлении сигнала переполнения на полюсе 19i через элемент 25 И устанавливается в единичное состояние триггер 23 блока 2 . Вследствие этого на нулевом его выходе, соединенным со входом элемента 26 И, появляется запрещенный потенциал, а на единичном выходе — разрешающий потенциал. С появлением на полюсе 31 первого импульса серии ГИ который через элемент 27 И устанавливает триггер 24 блока 2;в единичное состояние (если триггер 23 этого блока находится в единичном состоянии). Тем самым снимается разрешающий потенциал со входа элемента 25 И и подается разрешающий потенциал на элемент 28 И. Импульс серии ГИ г, следующий за импульсом ГИ 2, поступает на полюс 33 коммутируемого блока и через элемент 28 И устанавливает триггер 23 в нулевое состояние, а также этот импульс проходит на разрядный выход блока полюса 18 . Нулевое состояние триггера

23 выдает разрешение на прохождение им1S ло

ы зо

5О

Ь пульсов ГИ со входа 31i коммутирующего блока на его выход 34 через элемент 26 И.

С разрядного выхода этот импульс поступает на полюс 18 того формирователя, у которого первым появляется импульс переполнения на полюсе 19, и устанавливает триггер 1 5 в нулевое состояние. Нулевое состояние триггера15 блокирует вход элемента 16

И и поэтому в этом формирователе в счетчик 14 не будет заносится больше ни одного импульса ГИ1. Сигнал же с полюса 311 первого блока 21 передается от блока к блоку, пропуская те блоки, на входах элементов

25 И которых нет разрешения на формирователей !. Так, импульс движения распространяется по коммутирующим блокам, пока не появится на выходе 34» последнего блока.

Появившийся импульс на выходе 34» блока 2, пройдя элемент 6 ИЛИ, устанавливает триггер 5 в единичное состояние. Далее весь цикл работы устройства повторяется аналогично описанному.

На полюсах 19 формирователей 1 < — 1» последовательно появляются импульсы переполнения счетчиков 13, что соответствует последовательному выбору нужных переменных. Аналогично от цикла к циклу в счетчики 14 будет заносится по одному импульсу ГИ 1, что соответствует возрастанию номера, который присваивается каждой переменной.

Если в процессе упорядочнения переменных окажется, что две или более переменных имеют одинаковую величину, то в этом случае устройство произведет их упорядочение по мере возрастания номера блока соответствующего формирователя 1, . Это объясняется тем, что импульс ГИ первым появится на разрядном выходе того блока, который ближе к началу последовательности блоков 2.

Наличие регенерационного счетчика 4 позволяет восстанавливать информацию о величине упорядочиваемых переменных в счетчиках 13 формирователей 1 — 1». Это происходит потому, что импульс «пуск», выработанный коммутирующими блоками и соответствующий выбору последней их упорядочиваемых переменных, установит триггер 5 в единичное состояние. Единичное состояние триггера 5 выдает разрешение на вход элемента 10 И, что дает возможность поступать импульсам ГИ на вход регенерационного счетчика 4 и полюса !7 всех формирователей 1т — 1». Импульсы ГИ1 оудут поступать до тех пор, пока на выходе регенерационного счетчика 4 не появится импульс переполнения. Этот импульс переполнения установит через элемент 7 ИЛИ триггер 5 в нулевое состояние, свидетельствуя о том, что процесс упорядочения и восстановления переменнь.х окончен.

Устройство отличается более высокой точностью по сравнению с устройствами аналогичного назначения.

"м"т "вг 34675 ф

ttg .ea. ° ", .Ф * °

7 .. а ф;А

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

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

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

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

1у соединены с выходами соответствующих формирователей значений переменных.

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

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

1. Специализированные электронные моделирующие машины и устройства, ЦК АН

УССР, К., вып. 1969, с. 78.

2. Авторское свидетельство СССР № 570060, кл. G 06 G 7/122, 1975 (прототип).

Составитель И. 3 агорбинина

Редактор Ю. Петрушко Техред К. Шуфрнч Корректор Н. Стен

Заказ 2221/11 Тираж 751 Подписное

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

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

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