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

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ йГ 746533 Союз СоветскихСоциалистическихРеспублик АВТОРСКОМУ СВИДЕТЕЛЬСТ(51) М. Кд. 606 Р 1 3 ааударатввнный камнтет СССР аа делам неабретеннй н аткрытнйрнтет УДК 681,325088,8) Бюллетень,лъ 25 убликовано 07 ата опублнкова сан ня 10,07,8 72) Автор изобретен И. Левин инский филиал Всесоюзного научно-исследовательскогопроектно-конструкторского института по автоматизациипредприятий промышленности строительных материалов аявител(54) УСТРОЙС ДЛЯ ОПРЕПЕЛЕНИЯ ЧИСЛЕРСИЙ производ- едусмат- ический мериэа темперзатем и т.д. ическихв камезации,ур, скорые сравИзобретение относится к области вы;числительной техники и может быть использовано при создании вычислительных машин, а также специализированных устройств, решающих задачи на основе теории определителей и матриц, задачи теории множеств и задачи комбинаторного типа при решении которых автоматически определяется число инверсий в заданной последовательности элементов (перестановке), в частности четностьили нечет- ность перестановки, что используется для определения знака членов определителя матрицы. Технологическим процессом ства минераловатных изделий пр ривается непрерывный автомат контроль 64 основных техноло параметров (перепады давлений рах волокноосаждения, полимери давлений, разряжений, температ ростей конвейеров и т.д.) кото ниваются с заданными уставкам При возникновении отклонений некото-рых параметров необходимо осуществлятьих регулирование йли корректировку уставок в предусмотренных пределах.Поскольку возникновение отклонений.5, контролируемых параметров носит случайный характер., то запись (регистрация) отклонений осуществляется в неопределенном порядке.10В то же время порядок выдачи управляющих воздействий для регулирования параметров, вышедших эа заданныепределы, строго определен. Это объясняется тем, что нельзя, например, увеличить скорость одного иэ конвейеров,если упала теМпература в камере полиции, Необходимо сначала поднятьатуру в камере полимеризации, аувеличить скорость конвейера,Отклонившиеся параметры следует упорядочить таким образом, чтобы при ыдаче управляющих воздействий по ре- улироваиию этих параметров не нару46533 фно арифматического блока и блока вывода, третий выход и вход блока управления соединены с первым входом и выходом памяти соответственно, генератор,первый выход которого соединен с первым входом первого реверсивного счетчика, триггер знака и первый коммутатор,введены второй коммутатор, второй реверсивный счетчик, формирователь ищ счетчик. Четвертый выход блока управления соединен со вторым входом арифметического блока, выход которого черезформирователь соединен с первыми входами счетчика и триггера знака, вторыед входы которых и третий вход арифметического блока соединены с вторым выходом блока управления, пятый выход которого соединен с первым входом пер. -вого коммутатора. Второй вход и выход20 первого коммутатора, соединены соответственно с выходом первого реверсивногосчетчика и вторым входом памяти, третий вход которой соединен с первым выходом второго коммутатора, вход кото 25 рого соединен с шестым выходом блокауправления, седьмой выход которого соединен с первым входом второго реверсивного счетчика, вторые входы которогои входы первого реверсивного счетчикаЗо соединены со вторым выходом второгокоммутатора. Восьмой;выход блока управления через последовательно соединенные генератор и второй реверсивныйсчетчик соединен с третьим входом перЗ 5 вого реверсивного счетчика, четвертыйвход которого соединен с девятым выходом блока управления, Выход счетчикачерез блок вывода соединен с выходомустройства.40 Структурная схема устройства приведена на чертеже,Устройство содержит блок 1 управления, генератор 2, реверсивные счетчики 3, 4, коммутаторы 8, 6, память 7,45 арифметический блок 8, триггер 9 знака, блок 10 вывода, формирователь 11и счетчик 12.Устройство работает следующим образомЧерез коммутатор 6 в память 7вводятся коды индексов (числа) Ке К , , К исходной перестановкиД, которые ука-л изывают место каждого элемента в ис 551ходной перестановке. Если в перестановке имеется инверсия, то естестенный 3 7шался (т.е. был строго выполнен) порядок подачи этих воздействий на регулирующие органы,При этом решается задача определения числа инверсий среди зарегистрированных параметров по отношению к выходным управлякпцим воздействиям поэтим параметрам.Условием для выдачи разрешения наподачу управляющих воздействий является равенство нулю числа инверсий впоследовательности выходных параметров, очередность выдачи которых прону мерована натуральным рядом чисел."Устройство должно непрерывно конт ролировать число инверсий среди входныхпараметров и при их наличии производитьсоответствующую перестановку параметров. Число перестановок транспозиций"равно числу инверсий среди параметров,записанных в данном цикле опроса.- Таким образом, основной задачейустройства в данном техническом процессе является преобразование потокавходной информации в соответствий сограничениями, налагаемыми на выходные управляющие сигналы технологиейпроизводства минераловатных изделий.Это преобразование заключается вопределении числа инверсий среди параметров, поступающих на вход данногоустройства.Известно устройство 13, содержащееблок управления, матрицу ячеек, память,генератор и ицдикатор знака.Недостатками устройства являютсянизкое быстродействие и ограниченныефункциональные возможности.Наиболее близким техническим решением к изобретению является устройство2 -";"содержащее матрицу .ячеек, блокуправления, соединенный с арифметическим блоком, блоком вывода и щвграммирующим блоком, соединенным с гейератором, коммутатором и через блокиопределения знаков с арифметическимблоком. При этом выходы матрицы через элементы ИДИ соединены с арифметическим блоком и блоком вывода.Недостатком известного устройстваявляется низкое быстродействие.Оелью изобретении является повьппенибыстродействия устройства.Поставленная цель достигается тем,что в устройство для определения числаинверсий, содержащее блок управления,первый и второй вьавды которого соединены с первыми входами соответственпорядок следования кодов индексов1 чисел) будет нарушен.20 25 30 40 В общем случае индексы переста/новки расположены в произвольном порядке, и задача заключается в определениичисла инверсий в заданной перестановкепорядка о ,Параллельно с вводом исходной перестановки в память 7 в счетчики 3 и4 заносится число, равное о (т.е. число, равное числу элементов исходнойперестановки). Из счетчика 3 число о. вводится в коммутатор 5, с помощьюкоторого из памяти 7 выбирается индекс элемента введенного последним,т.е. индекс (число), хранящийся в памяти 7 в ячейке (разряде) с номером 11 .Это число заносится в арифметическийблок 8. Затем по команде из блока 1 изсодержимого счетчика 3 с помощью генераторв 2 вычитается единица.Полученное в счетчике 4 число 0 -1поступает на коммутатор 5; с помощьюкоторого из памяти 7 выбирается индекс элемента, находящегося в ячейкес номером о -1. Код этого индексатакже поступает в арифметический блок 8.По сигналу блока 1. в арифметическомблоке 8 проверяется условие 1 й(р-и,т.е. значение индекса перестановки вячейке с номером о должно бытьменьше значения индекса перестановкив яЧейке с номером г -1.При выполнении этого условия всчетчик 12 через формирователь 11 заносится единица, и срабатывает триггер9. В противном случае это не происходит. Затем по сигналу блока 1 генератор 2 вырабатывает импульс, и иэ счетчика 3 снова вычитается единица.Полученное в счетчике З число и -2поступает на коммутатор 5, с помощьюкоторого из памяти 7 выбирается индекс элемента, находящегося в ячейкес номером О -2. Код этого индексазасылается в арифметический блок 8,где по аналогии с предыдущим 61 ь- .При выполнении условия заносится единица в счетчик импульсов 11 и перебрасывается триггер 9,Процесс выборки и сравнения индек-сов перестановки происходит до перебора всех о элементов введенной перестановки, т.е. включая шаг, при которомв счетчике 3 будет число, рввное еди,нице. После сравнения последнего элемента перестановки с первым элементом этой перестановки в счетчике 3 будет число, равное нулю. 6На этом заканчивается первый цикл решения задачи.Второй цикл начинается вычитанием по команде с блока 1 (подачей импульса с генератора 2) единицы из содержимого счетчика 4 и занесения полученного чиисла о -1 в счетчик 3, откуда это число поступает на коммутатор 5, с помощью которого из памяти 7 выбирается индекс хранящегося кода элемента в его ячейке с номером о -1 и заносится в арифметический блок 8.Далее по аналогии с первым циклом работы устройства последовательно выбираются индексы элементов перестановки из ячеек с номерами и -2, о -3, , 1 и сравниваются с индексом, соответствующим ячейке р - 1.В процессе сравнений в счетчик 12 поступает столько импульсов, сколько раз индекс элемента, хранящегося в ячейке с номером о - 1, окажется меньше индекса элементов, хранящихся в ячейках с меньшими номерами.Третий цикл начинается по команде с блока 1 вычитанием. единицы из счетчика 4 и занесением полученного числа-2 в счетчик 3. Далее цикл работы выполняется аналогично двум предыдущим.Процесс решения заканчивается выполнением й -1 цикла, после чего в счетчике 12 будет число, равное числу инверсий в данной перестановке.В связи с тем, что триггер 9 изменил свое состояние при выполнении условия сравнения индексов и выработке сигнала арифметическим блоком 8,соответствующим наличию инверсии нв каждом шаге сравнения, при наличии в исходной перестановке четного числа инверсий 1 триггер 9 оказывается в ис- . ходном состоянии, а при нечетном числе инверсий он окажется в противоположном состоянии. Таким образом, основвЧисло инверсий из счетчика 12 по,дается в блок 10. Процесс ввода перестановок в коммутатор 6 и вывода нием триггера 9 однозначно определяется четность или несуетность перестановки,При вычислении определителя матрицы, т.е. когда индексами элементов перестановки являются вторые индексыэлементов матрицы, четность перестановки дает соответствующему членуматрицы знак плюс" а нечетность,знак "минус.7 74653результата вычислений на блок 10 позволяет использовать предложенное устройство как автономное или в качествефункционального блоха ЭВМ.Повышение быстродействия устрой ства достигается за счет автоматическогоапйаратного решения одной из сложнейших комбинаторных задач - вычислениячисла инверсий в перестановке порядка,Это позволяет использовать устрой Оство для решения комбинаторных задачбольшой размерности.Устройство реализовано в составекомплекса технических средств АСУТПпроизводства минераловатных изделий, 15внедряемой в производственном объединении "Гомельстройматериалы", и предназначено для обработки массива входных,. параметров, записываемых в матричной форме. 20Согласно расчету экономической эффективности по теме 151-М "СозданиеАТ 4 для пройзводства минераловатныхизделий, государственный регистрационный75044258, экономический эффехт 23от внедрения "комплекса техническихсредств АСУТП в п/о Гомельстройматериалы" составит свыше 111 тыс. руб.,в том числе от использования предлагаемого устройства будет получен эффект 30около 4,0 тыс. руб. Общая потребностьв таких устройствах только для минера,ловатной промышленности составляет150 шт. Таким образом, суммарныйэкономический эффект от внедрения ЗЗкомплекса технических средств АСУТЦв котором используется предлагаемоеустройство, только в минераловатнойпромышленности составит 16650 тыс.руб.в том числе от использования самого 40устройства суммарный экономическийэффект составит около 600 тыс. руб.Устройство может найти сЫое широкое применение в других отраслях народного хозяйства, в научных исследо-45ваниях,формула. изобретения Устройство для определениячислаинверсий, содержащее блок управления, у 3 8первый и второй выходы которого соединены с первыми входами соответственно арифметического блока и блока вывода, третий выход и вход блока управления соединены с первыми входом ивыходом памяти соответственно, генератор, первый выход которого соединенс первым входом первого реверсивногосчетчика, триггер знака и первый коммутатор о т л и ч а ю ш е е с я тем,что, с целью повышения быстродействия,в йего введены второй коммутатор, второй реверсавный счетчик, формировательи счетчик, четвертый выход блока управления соединен со вторым входом арифметического блока, выход которого черезформирователь соединен с первыми входами счетчика и триггера знака, вторыевходы которых и третий вход арифметического блока соединены с вторым выходом блоха управления, пятый выходкоторого соединен с первым входом первого коммутора, второй вход и выходпервого коммутатора соединены соответственно с выходом первого реверсивного счетчика и вторым входом памяти,третий вход которой соединен с первымвыходом" второго коммутатора, вход которого соединен с шестым выходом блока управления, седьмой выход которогосоединен с первым входом второго реверсивного счетчика, вторые входы которого и первого реверсивного счетчикасоединены со вторым выходом второгокоммутатора восьмой выход блокауправления через последовательно соединенные генератор и второй реверсивныйй счетчик соединен с третьимвходом первого реверсивного счетчике,четвертый вход которого соединен с девятым выходом блока управления, выходсчетчика через блок вывода соединен свыходом устройства.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССР, Редак 3949/39 ЦНИИПИ Госу по делам и113035,Москв Тираж 751 Подписное дарственного комитета СССР эобретений и открытий а, Ж, Раушская наб., д. 4/ к пиал ППП Патент", г. Ужгород, ул. Проектная,Составитель Г. ЛевинЛ. Утехина Текред Ж.Кастелевич Корректор В. Бутяг