Устройство для определения числа инверсий Советский патент 1980 года по МПК G06F17/10 

(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА

1

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

Технологическим процессом производства минераловатнь1х изделий предусматривается непрерывный автоматический контроль 64 основных технологических параметров (перепады давлений в камерах волокноосаждения, полимеризации, давлений, разряжений, температур, скоростей конвейеров и т.д.), которые сравюшаются с заданными уставками. ИНВЕРСИЙ

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

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

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

15 если упала температура в камере поли меризацни. Необходимо сначала поднять температуру в камере полимеризации, а затем увеличить скорость конвейера, . и т.д.

20

Отклонившиеся параметры следует упорядочить таким образом, чтобы при /выдаче утфавляющих воздействий по регулированию этих параметров не нару746533шалея (т.е. бып строго выполнен) порядок подачи этих воздействий на регулирующие органы. При этом решается задача определения числа инверсий среди зарегйст|3ированиых параметров iio отношению к выходньпу управляющим воздействиям по этим параметрам. Условием для выдачи разрешения на подачу утфавляющих воздействий является равенство нулю числа инверсий в последовательности выходных параметров, очередность выдачи которых прону Мёрована натуральным рядом чйсёя. Устройство должно непрерывно контролировать число инверсий среди входны параметров и при их наличии производит соответствующую перестановку параметров. Число перестановок транспозиций равно числу инверсий среди параметров, записанных в данном цикле опроса.-Таким образом, основной задачей устройства в данном техническом процессе является преобразование потока входной информации в соответствий с ограничениями, налагаемыми на выходные управляющие сигналы технологией производства минераловатных изделий. Это преобразование заключается в определении числа инверсийсреди параметров, поступающих на вход данного Устройства. Известно устройство 1} , содержащее блок управления, матрицу ячеек, память генератор и индикатор знака. Недостатками устройства являются низкое быстродействие и ограниченные функциональньте возможности. Наиболее близким техническим реше нием к изобретению является устройств 2 7 содё ржащёё матрицу ячеек Г блок управления, соединенный с арифметичес ким блоком, блоком вывода и прьграммйрующим бШкомТсоШшёшьшГс генератором, коммутатором и блоки определения знаков с ари шёгвгаёсзким блоком. При этом выходы матрицы через элементы ИДИ соединены с арифме тическим блоком и блоком вывода. Недостатком известного устройства является низкое быстродействие. Целью изобрётениа юляетея повыше быстродействия устройства. Поставленная цель достигается тем, что в устройство дяя определения числа инверсий, содержащее блок упрййлеяйй, первый и второй выяоды которого соедвншы с первыми входвмн соответстве КО арифматического блока и блока вывода, третий выход и вход блока управления соединены с первым входом и выходом памяти соответственно, генератор, первый выход которого соединен с первым входом первого реверсивнохч) счетчика, триггер знака и первый коммутатор, введены второй коммутатор, второй реверсивный счетчик, формирователь и счетчик. Четвертый выход блока управЛ ения соединен со вторым входом арифметического блока, выход которого через . формирователь соединен с первыми входами счетчика и триггера знака, вторые входы которых и третий вход арифметического блока соед1шены с вторым выходом блока управления, пятый выход ко-, торого соединен с первым входом первого коммутатора. Второй вход и выход первого коммутатора. соединены соответственно с выходом первого реверсивного счетчика и вторым входом памяти, третий вход которой соединен с первым выходом второго коммутатора, вход которого соединен с шестым выходом блока управления, седьмой выход которого соединён с первым входом второго реверсивного счетчика, вторые входы которого и входы первого реверсивного счетчика соединены со вторым выходом второго коммутатора. Восьмой выход блока управления череэ последовательно соединенные генератор и второй реверсивный счетчик соединен с третьим входом первого реверсивного счетчика, четвертый вход которого соединен с девятым выходом блока управления. Выход счетчика через блок вывода соед$шен с выходом устройства.. Структурная устройства привейёйа на чертеже. Устройство содержит блок 1 управлеШя, генератор 2, реверсивные счетчики 3, 4, коммутаторы 5, 6, память 7, арифметический блок 8, триггер 9 знака, блок 10 вывода, формирователь 11 и счетчик 12. Устройство работает следующим образом. Через коммутатор 6 в память 7 вводятся коды индексов (числа) К , Кр исходной перестановки KI 01. Ко У зывают место каждого элемента в ис-ходной перестановке. Если в перестановке иМёе-тся инверсия, то естестенный порядок следования кодов индексов fчисел) будет нарушен. В общем случае индексы перестановки расположены в произвольном поря ке, и задача заключается в определении числа инверсий в заданной перестановке пррядка п . Параллельно с вводом исходной перестановки в память 7 в счетчики 3 и 4 заносится число, равное п (т.е. число, равное числу элементов исходной перестановки). Из счетчика 3 число п .вводится в коммутатор 5, с помощью которого из памяти 7 выбирается индекс элемента введенного последним, т.е. индекс (число), хранящийся в памя ти 7 в ячейке (разряде) с номером о . Это число заносится в арифметический блок 8. Затем по команде из блока 1 и содержимого счетчика 3 с помощью генератора 2 вычитается единица. Полученное в счетчике 4 число П -1 поступает на коммутатор 5, с помощью которого из пам5гги 7 выбирается индекс элемента, находящегося в ячейке с номером П -1. Код этого индекса также поступает в арифметический блок По сигналу блока 1 в арифметическом блоке 8 проверяется условие , т.е. значение индекса перестановки в ячейке с номером п должно быть меньше значения индекса перестановки в ячейке с номером п При выполнении этого условия в счетчик 12 через формирователь 11 за носится единица, и срабатывает триггер 9. В противном случае это не происходит. Затем по сигналу блока 1 генератор 2 вырабатывает импульс, и из счет чика 3 снова вычитается единица. Полученное в счеТчике 3 число п -2 поступает на коммутатор 5, с помощью которого из памяти 7 выбирается ин.декс элемента, находящегося в ячейке с номером П -2. Код этого индекса засылается,в арифметический блок 8, где по аналогии с предыдущим пЗ |Ь-23 При вьшолнении условия заносится единица в счетчик импульсов 11 и перебрасывается триггер 9. Процесс выборки и сравнения индексов перестановки происходит до перебора всех п элементов введенной перестановки, т.е. включая щаг, при котором в счетчике 3 будет число,равное еди,нице. После сравнения последнего элемента перестановки с первым элементом этой перестановки в,счетчике 3 будет число, равное нулю. На этом заканчивается первый цикл решения задачи. Второй цикл начинается вычитанием по команде с блока 1 (подачей импульса с генератора 2) единицы из содержимого счетчика 4 и занесения полученного чиисла п -1 в счетчик 3, откуда это число поступает на коммутатор 5, с помощью которого из памяти 7 выбирается индекс хранящегося кода элемента в его ячейке с номером п -1 и заносится В арифметический блок 8. Далее по аналогии с первым циклом работы устройства последовательно выбираются индексы элементов перестановки из ячеек с номерами п -2, п -3,.,, 1 и сравниваются с индексом, соответствующим ячейке п - 1. В процессе сравнений в счетчик 12 поступает столько имиульсов, сколько раз индекс элемента, храняпцегося вячейке с номером п -1, окажется меньше индекса элементов, хранящихся в ячейках с меньшим1И номерами. Третий цикл начинается по команде с блока 1 вычитанием, единицы из счетчика 4 и занесением полученного числа П -2 в счетчик 3. Далее цикл работы вьшолняется аналогично двум предыдущим. Процесс решения заканчивается выполнетшем-п -1. цикла, после чего в счетчике 12 будет число, равное числу инверсий в данной перестановке. В связи с тем, что триггер 9 изменил свое состояние при выполнении условия сравнения индексов и выработке сигнала арифметическим блоком 8, . соответствующим наличию инверсии на каждом щаге сравнения, при наличии в исходной перестановке четного числа инверсийI триггер 9 оказывается в ис-ходнрм состоянии, а при нечетном числе инверсий он окажется в противополож-. ном состоянии.. Таким образом, основа- ниё1Л триггера 9 однозначно опрёделяется четность или нечетность перестановки. При вычислении определителя матриы, т.е. когда индексами элементов пеестановки явЛ5в6тся вторые индексы лементов матрицы, четность перестаовки дает, соответствующему члену« атрицы знак плюс а нечетность нак минус. Число инверсий из счетчика 12 поается в блок 1О. Процесс ввода пеестановок в коммутатор 6 и вывода

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

Повышение быстродействия устройстёй дос-гигйется за счет автЬмат)йч эског аппаратного решения одной из сложнейших комбинаторных задач - вычисления числа инверсий в перестановке порядка.

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

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

Согласно расчету экономической эффекти ности по теме 151-М Создание AT 4 для производства минераловатных изделий, государственный регистрационный № 75044258, экономический эффек от внедренияксйутлекса технических средств АСУТП в п/о Томельстройматериалы составит свыше 111 тыс. руб в toM числе от использования предлагаемого устройства будет получен эффек около 4,0 тыс. руб. Обшая потребность в таких устройствах только для минера.ловатной промышленности составляет 15О шт. Таким образом , суммарньтй , экономический эффект от внедрения

комплекса технических средств АСУТЦ в котором используется предлагаемое устройство, только в минераловатной промышленности составит 166БО тыс.ру в том числе от использования самого устройства суммарный эконснлический эффект составит около 6ОО тыс. руб.

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

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

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

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

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

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

№ 4748О9, кл. G 06 F 15/32, 1971

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