Устройство для определения числа инверсий

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ и 746533

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт, свид-ву (22) Заявлено 05. 1,2.77 (21) 2550g20/18-24 с присоединением заявки N (23) Приоритет

Опубликовано 07.07.80. Бюллетень J% 25

Дата опубликования описания10,07.80 (53)M. Кл.

G 06 F 15/32

3ааударатввнный камитет

СССР аа делам неабретений н аткрыткй (53) УДК 681.Зг5 (088.8) .(72) Автор изобретения

Г. И. Левин

Минский филиал Всесоюзного научно-исследовательского и проектно-конструкторского института по автоматизации предприятий промышленности строительных материалов (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА

ИНВЕРСИЙ

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

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

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

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

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

Отклонившиеся параметры следует упорядочить таким образом, чтобы при ,выдаче управляющих воздействий по ре- еулироваиию этих параметров не нару10

20

30

50 е

3 74 шался (т.е. был строго выполнен) порядок подачи этих воздействий на регулирующие органы.

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

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

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

Это преобразование заключается в определении числа инверсий среди параметров, поступающих на вход данного устройства.

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

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

Наиболее близким техническим решением к изобретению является устройство 2) -"; содержащее матрицу ячеек, блок управления, соединенный с арифметическим блоком, блоком вывода и программирующим блоком, соединенным с генератором, коммутатором и чсрез блоки определения знаков с арифметическим блоком. При этом выходы матрицы через элементы ИДИ соединены с арифметическим блоком и блоком вывода.

Недостатком известного устройства является низкое быстродействие.

Оелью изобретении является повьппени быстродействия устройства.

Поставленная цель достигается тем, что в устройство для определения числа инверсий, содержащее блок управления, первый и второй вьавды которого соединен«ы с первыми входами соответствен6533 ф но арифматического блока и блока вывода, третий выход и вход блока управления соединены с первым входом и выхо-! дом памяти соответственно, генератор, первый выход которого соединен с первым входом первого реверсивного счетчика, триггер знака и первый коммутатор, введены второй коммутатор, второй реверсивный счетчик, формирователь и счетчик. Четвертый выход блока управления соединен со вторым входом арифметического блока, выход которого через формирователь соединен с первыми входами счетчика и триггера знака, вторые входы которых и третий вход арифметического блока соединены с вторым выходом блока управления, пятый выход ко» торого соединен с первым входом пер.— вого коммутатора. Второй вход и выход первого коммутатора, соединены соответственно с выходом первого реверсивного счетчика и вторым входом памяти, третий вход которой соединен с первым выходом второ о коммутатора, вход которого соединен с шестым выходом блока управления, седьмой выход которого соединен с первым входом второго реверсивного счетчика, вторые входы которого и входы первого реверсивного счетчика соединены со вторым выходом второго коммутатора. Восьмой;выход блока управления через последовательно соединенные генератор и второй реверсивный счетчик соединен с третьим входом первого реверсивного счетчика, четвертый вход которого соединен с девятым вы1 ходом блока управления. Выход счетчика через блок вывода соединен с выходом устройства.

Структурная схема устройства приведена на чертеже.

Устройство содержит. блок 1 управлен«ия, генератор 2, реверсивные счетчики 3, 4, коммутаторы 5, 6, память 7, арифметический блок 8, триггер 9 знака, блок 10 вывода, формирователь 11 и счетчик 12.

Устройство работает следующим обраом

Через коммутатор 6 в память 7 вводятся коды индексов {числа) К

K, ..., К,, исходной перестановки а, а,, ..., ар,, которые ука-

<и и зывают место каждого элемента в ис-.

1 ходной перестановке. Если в перестановке имеется инверсия, то естестенный порядок следования кодов индексов 1чисел) будет нарушен.

746533

В общем случае индексы переста/ новки расположены в произвольном порядке, и задача заключается в определении числа инверсий в заданной перестановке порядка n .. 5

Параллельно с вводом исходной перестановки в память 7 в счетчики 3 и

4 заносится число, равное и (т.е. число, равное числу элементов исходной перестановки). Из счетчика 3 число и 10, вводится в коммутатор 5, с помощью которого из памяти 7 выбирается индекс элемента введенного последним, т.е. индекс (число), хранящийся в памяти 7 в ячейке (разряде) с номером n . 15

Это число заносится в арифметический блок 8. Затем по команде из блока 1 из содержимого счетчика 3 с помощью ге» нератора 2 вычитается единица.

Полученное в счетчике 4 число г) -1 20 поступает на коммутатор 5; с помощью которого из памяти 7 выбирается индекс элемента, находящегося в ячейке с номером п -1. Код этого индекса также поступает в арифметический блок8. 25

По сигналу блока 1. в арифметическом блоке 8 проверяется условие knl(Yn-1, т.е. значение индекса перестановки в ячейке с номером A должно быть меньше значения индекса перестановки 30 в яЧейке с номером п -1.

При выполнении этого условия в счетчик 12 через формирователь 11 заносится единица, и срабатывает триггер

9. В противном случае это не происхо- ç5 дит. Затем по сигналу блока 1 генера1 тор 2 вырабатывает импульс, и иэ счетчика 3 снова вычитается единица.

Полученное в счетчике З число и -2 поступает на коммутатор 5, с помощью 40 которого из памяти 7 выбирается индекс элемента, находящегося в ячейке с номером tl -2. Код этого индекса засылается в арифметический блок 8, где по аналогии с предыдущим <Я -g$ . 45

При выполнении условия заносится единица в счетчик импульсов 11 и перебрасывается триггер 9.

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

После сравнения последнего элемента перестановки с первым элементом этой перестановки в счетчике 3 будет число, равное нулю.

На этом заканчивается первый цикл решения задачи.

Второй цикл начинается вычитанием по команде с блока 1 (подачей импульса с генератора 2) единицы из содержимого счетчика 4 и занесения полученного чиисла и -1 в счетчик 3, откуда это число поступает на коммутатор 5, с помощью которого из памяти 7 выбирается индекс хранящегося кода элемента в

его ячейке с номером и -1 и заносится в арифметический блок 8.

Далее по аналогии с первым циклом работы устройства последовательно выбираются индексы элементов перестановки из ячеек с номерами и -2, и -3, „, L и сравниваются с индексом, соответствующим ячейке n — 1.

B процессе сравнений в счетчик 12 поступает столько импульсов, сколько раз индекс элемента, хранящегося в ячейке с номером n — 1, окажется меньше индекса элементов, хранящихся в ячейках с меньшими номерами.

Третий цикл начинается по команде с блока 1 вычитанием единицы из счетчика 4 и занесением полученного числа

-2 в счетчик 3. Далее цикл работы выполняется аналогично двум предыдущим.

Процесс решения заканчивается выполнением.A --1 цикла, после чего в счетчике 12 будет число, равное числу инверсий в данной перестановке.

В связи с тем, что триггер 9 изменил свое состояние при выполнении условия сравнения индексов и выработке сигнала арифметическим блоком 8, соответствующим наличию инверсии иа каждом шаге сравнения, при наличии в исходной перестановке четного числа инверсий I триггер 9 оказывается в ис-ходном состоянии, а при нечетном числе инверсий он окажется в противоположном состоянии. Таким образом, основанием триггера 9 однозначно определяется четность или несуетность перестановки.

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

Число инверсий из счетчика 12 по,дается в блок 10. Процесс ввода пе-! рестановок в коммутатор 6 и вывода

7 74653 результата вычислений на блок 10 позволяет использовать предложенное устройство как автономное или в качестве функционального блоха ЭВМ.

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

Устройство реализовано в составе комплекса технических средств АСУТП производства минераловатных изделий, 15 внедряемой в производственном объединении Гомельстройматериалы, и предназначено для обработки массива входных,. параметров, записываемых в матричной форме. 20

Согласно расчету экономической эффективности по теме 151-М "Создание

АТ4 для пройзводства минераловатных изделий, государственный регистрационный ¹ 75044258, экономический эффехт 25 от внедрения комплекса технических средств АСУТП в п/о Гомельстройматериалы" составит свыше 111 тыс. руб., в том числе от использования предлагаемого устройства будет получен эффект 30 около 4,0 тыс. руб. Общая потребность в таких устройствах только для минера,ловатной промышленности составляет

150 шт. Таким образом, суммарный, экономический эффект от внедрения Q5 комплекса технических средств АСУТЦ в котором используется предлагаемое устройство, только в минераловатной промышленности составит 16650 тыс.руб. в том числе от использования самого 40 устройства суммарный экономический эффект составит около 600 тыс. руб.

Устройство может найти сЫое широкое применение в других отраслях народного хозяйства, в научных исследо- 45 ваниях, формула. изобретения

Устройство для определения числа инверсий, содержашее блок управления, 5р

3 8 первый и второй выходы которого соединены с первыми входами соответственно арифметического блока и блока вывода, третий выход и вход блока управления соединены с первыми входом и выходом памяти соответственно, генератор, первый выход которого соединен с первым входом первого реверсивного счетчика, триггер знака и первый ком-.

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

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

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

% 474809, кл. (д 06 15/32, 1971.

2. Авторское свидетельство СССР № 404090, кл. 6 06 Р 15/32, 1977 (прототип) .

746533

Составитель Г. Левин

Редактор Л. Утехина Текред Ж.Кастелевич Корректор В. Бутяга

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

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

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

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