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

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

1

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

Необходимость определения числа инверсий и транспозиций, кроме задач вычислительного характера, появляется, например, в АСУТП, где необходнмо сократить время (или определить его), необходимое для упорядочения поступающих значений технологических параметров относительно выдаваемых управляющих воздействий, особенно если последовательность выдачи управляющих воздействий зависит от порядка поступления отклонений значений контролируелых параметров.

Известно устройство для матричных вычислений - определения знака

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

Однако данное устройство имеет ограничен1ые функциональные возмозкности.

Известно также устройство для матричных вычислений - определения числа ииверсий, содержащее связанные между собой арифметический и запоминающий блоки и совдиненш 1й с ним по входам и выходам блок управления, коммутатор, связанные между собой реверсившле счетчики, счетчик игпульсов и генератор импульсов, соединенные входами с блоком управления, формирователь, вход которого подклкт чей к выходу арифметического блока, а выход - к счетчику импульсов, входы реверсивных счетчиков подключены к генератору импульсов, устройство ввода, выход которого подключен к запоминающему блоку и входак реверсивных Счетчиков, один из выходов .второго реверсивного счетчика соединен с входом коммутатора, выход которого подключен к запоминающему блоку, а выход счетчика импульсов соединен с устройством вывода. Недостатком известного устройств является недостаточно пшрокие функциональные возможности, так как оно не обеспечивает автоматическое определение числа транспозиций и не осуществляет разложение исходной перестановки в произведение циклов. Цель изобретения - расширение функциональных возможностей устройства. Это достигается тем, что в устройство, содержащее формирователь импульсов, выход которого подключен к первому входу блока вывода, блок ввода, информационный выход которого соединен с информационным входом блока памяти, адресный вход которого подключен к клходу коммутатора, первый вход которого подключен к выходу первого реверсивного счетчика, вход которого соединен с выходом второго реверсивного счетчика, причем установочныевходы первого и второго реверсивных счетчиков соединены с выходом числа элементов блока ввода, генератор импульсов, выход которого соединен с числовыми входг1ми первого и второ го реверсивных счетчиков, блок управления, содержащий генератор такт вых импульсов, сдвиговый реги,стр и шифратор, причем выход генератора тактовых импульсов соединен с выходом сдвигового регистра, выход которого подключен к входу .шифратора первый - восьмой выходы которого соединены с управлянщими входами соответственно блока памяти, блока ввода, второго реверсивного счетчика, генератора импульсов, первого реверсивного счетчика, коммутатора блока вывода и счетчика импульсов, арифметический блок, содержащий два регистра и узел сравнения, причем выходы первого и второго регистров подключены соответственно к первому и второму входам узла сравнения, вы ход которого соединен с входом формирователя импульсов, девятый выход шифратора соединен с управляющими входами узла сравнения, первого и второго регистров, введены третий регистр и переключатель, первый выход которого соединен с входом первого регистра, выход которого подключен к второму входу блока вывода, выход третьего регистра соединен с входом второго регистра арифметического блока и вторым входом коммутатора, вход третьего регистра соединен с вторым выходом переключателя, вход которого подключен к выходу блока памяти, причем десятый выход шифратора блока управления соединен с управляющим входом третьего регистра. На. фиг. 1 приведена блок-схема |Предлагаемого устройства) на фиг. 2 схема блока управления; на фиг, 3 схема коммутатора; на фиг. 4 - схема арифметического блока; на фяг. 5 - схема блока ввода; на фиг. 6 - схема блока вывода. Устройство содержит блок I управления, генератор 2 импульсов, реверсивные счетчики 3 и 4, коммутатор 5, блок 6 ввода, блок 7 памяти, арифметический блок В, переключатель 9, блок 10 вывода, формирователь 11 импульсов, счетчик 12 импульсов и регистр 13. Схема блока 1 управления состоит из генератора 14 тактовых импульсов, регистра 15 сдвига, шифратора ( например, диодного типа) 16 и пусковой кнопки 17. Схема коммутатора 5 содержит группу элементов И 18 - 25 и группу элементов ИЛИ 26-29. Коммутатор 5 осуществляет передачу кодов на вход блока 7 От реверсивного счетчика 4 или от регистра 13 в зависимости от сигнала блока 1 управления. Схема арифметического блока 8 содержит приемные регистры 30 и 31 и узлы сравнения кодов 32. Коды чисел поступают в регистр 30 из блока 7, а в регистр 31 из регистра 13. Схема блоков ввода 6 содержит узел ввода с перфоленты 33 (например, устройство фотоввода FS 1501), клавиатуру 34 ручного ввода, шифратор 35 и переключатель 36 выхода. Вход 37 служит для ввода перфоленты в блок ввода, который запускается по второму входу с блока 1 управления. Переключатель выхода 36 служит для переключения при работе от ручного ввода с клавиатуры 34 на работу от фотоввода 33. Схема блока 10 вывода содержит узел 38 индикации, печатающей узел 39 и триггер 40. Включение одного из узлов, . в зависимости от режима работы, осущестдляется с блока 1 управления с помощью триггера 40. Устройство работает следуювдм образом. В режиме определения числа инверсий переключатель 9 находится в положении 0. Через блок 6 ввода в блок 7 памяти вводятся коды ивдексов (числа) К, Кл,... ,Kf, исходной перестановки а|, а|(...,а| ,которые указывают место каждого элемента в исходной перестановке. Если в перестановке имеются ин°версии, порядок следова1шя кодов индексов нарушается. В общем случае индексы перестановки располагаются в произвольном порядке и задач заключается в определении числа инверсий в заданной перестановке, а также числа транспозиций. Кроме того, устройством решается еще одна сложная комбинаторная задача, а именно разложение перестановки в произведении циклов Параллельно с вводом исходной перестановки через блок 6 ввода в блок 7, в реверсивные счетчики 3 и 4 зано сится число п и вводится в коммутатор 5, с помощью которого из блока 7 считьшается индекс элемента, введенного последним, т.е. занесенный в ячейку с номером п блока 7. Затем по команде блока управления 1 из содержимого реверсивного счетчика 4 им импульсов с генератора 2 вычитается единица. Полученное в счетчике 4 число п-1 поступает иа вход коммутатора 5, с помощью которого из блока 7 выбирается индекс элемента, находящегося в ячейке с номером п-1, Код этого индекса поступает в арифметический блок 8. По сигналу блока 1 управлещ«1 коды индексов, хранящихся в арифметическом блоке В, срав ниваются и проверяется услою1е п t 1 т.е. значение индекса перестановки в ячейке с номером п меньше значения индекса перестановки в ячей ке с номером п-1. При выполнении этого условия в счетчик 12 импульса через формирователь 11 и переключатель 9 наносится единица. Затем по сигналу блока 1 управления, генератор 2 импульсов вырабатывает импульс и из счетчика 4 снова вычитается единица. Полученное в счетчике 4 число «-2 поступает на вход коммутатора 5, с помощью которого из блока 7 выбирается индекс элемента, находящегося в ячейке с номером п -2. Код этого индекса засылается в арифметический блок В, где по аналогии с предьщущим проверяется условие ,при вьшолнении которого заносится единица в счетчик 12 импульсов. Процесс выборки и сравнения индексов перестановки происходит до перебора всех п элементов введенной перестановки, т.е. включая шаг, при котором в реверсивном счетчике 4 будет число, равное единице. После сравнения последнего элемента перестанбвки с первым элементом этой перестановки в счетчике 4 будет число, равное нулю. На этом заканчивается первый цикл решения задачи. Второй цикл начинается вычитанием по команде с блока 1 управления (подачей импульса с генератора 2 импульсов) единицы из содержимого счетчика 3 и занесения.полученного числа п-1 в счетчик 4, откуда это число поступает на вход коммутатора 5, с помощью которого из блока 7 выбирается индекс хранящегося кода элемента в ячейке с номером 1т-1 и заносится в арифметический блок 8. Далее по аналогии с первым циклом работы устройства последовательно выбираются индексы элементов перестановки из ячеек с номерами п-2, ,...1 и сравниваются с индексом, соответствующим ячейке п-1. В процессе сравнений в счетчик 12 импульсов поступит столько импульсов, сколько раз индекс элемента, хранящегося в ячейке с номером П-1, окажется меньше индекса элементов, хранящихся в.ячейках с меньшими номерами. Третий цикл начинается по команде с блока 1 управления вычитанием единицы из счетчика 3 и занесением полученного числа ti-2 в счетчик 4. Далее цикл выполняется аналогично двум предьщущим. Процесс решения заканчивается вы полнением п-1 цикла, после чего в счетчике 12 импульсов будет число. равное количеству инверсий в данной перестановке. Четность или нечетность перестановки однозначно определяется по че ности или нечетности числа, получа емого в счетчике 12 импульсов. Число инверсий из счетчика 12 им пульсов переносится в блок 10 вывод При вычислении определителя матрицы, т.е. когда индексами элементо перестановки являются вторые индексы элементов матрицы, четность пере становки дает соответствующему член матрицы знак плюс, а нечетность знак минус. В режиме определения транспозиций переключатель 9 устанавливается в положение б. Исходная перестановка вводится в блок 6 ввода аналогично предьщущему режиму работы, причем коды индексов вводимой перестановки в ячей ке запоминающего блока 7 располагаются последовательно, начиная с ячейки с номером 1, , По команде с блока 1 управлении с помощью коммутатора 5 из блока 7 выбирается код индекса а элемента перестановки, хранящийся в ячейке с номером . Код заносится в регист 13, а номер ячейки в арифметический блок 8, где происходит сравнение кода номером ячейки . Если вьтолняется равенство 1, то аналогично предыдущему выбирается код индекса а.,хранящегося в ячейке с номером блока 7, и снова производится сравнение а . При выполнении этого равенства происходит выборка следующего кода индекса, т.е. а и выполняется операция сравнешя aj( и т.д. до ячейки с номером Nr,n. Если в результате п сравнений вы полняются равенства кодов индексов перестановок и соответствующих им номеров ячеек блока 7, то это свидетельствует об отсутствии транспозиций в исходной перестановке и в счетчике 12 импульсов будет нулевое значение. При несовпадении на некотором ша ге кода индекса элемента перестановки с номером ячейки блока 7, в которой хранится этот код, выполняются следующие операции. По команде блока I управления код индекса элемента перестановки из регистра 13 подается на вход ком мутатора 5, который осуществляет выборку из ячейки с номером, равным этому коду, новый код индекса, хранящийся в данной ячейке блока 7. Аналогично предыдущему, в арифметическом блоке 8 происходит сравнение обоих кодов, и через формирователь 11 в счетчик 12 импульсов заносится единица. На этом заканчивается один цикл работы устройства. Если в:этом цикле сравниваемые коды окажутся равными, то содержимое регистра 13 и ячеек блока 7, из которых производилось считывание кодов индексов, гасятся в нулевое состояние, блока 7. Если при сравнении окажется, что а. ,то код шндекса/ регистра 13 передается на вход коммутатора 5, с помощью которого из ячейки блока 7 с номером, равным этому коду, считывается значение кода индекса, хранящегося в этой ячейке, и засылается в арифметический блок 8, куда также передается код индекса, хранящегося в режиме регистра 13, Затем в блоке 8 производится сравнение этих двух кодов, и через формирователь 1I в счетчик 12 импуЛьсов заносится единица. В Случае равенства сравниваемых значений, значений регистра 13, содержимое ячеек, из которых произошло считывание кодов индексов перестановки гасится в нулевое состояние. При невыполнении равенства аналогично предьщущему выполняется следуюций цикл. Таким образом, количество циклов, в которых не выполняется равенство кодов индексов элементов исходной перестановки с номерами соответствукищх ячеек блока 7, будет соответствовать количеству импульсов занесенных в счетчик 12 импульсов,, причем число, находящееся в счетчике 12 импульсов, после перебора всех ячеек равно числу транспозиций исходной перестановки. В процессе считывания значений кодов индексов из блока 7, ячейки содержимое которых уже бьто погашено в нулевое состояние, пропускаются коммутатором 5. В процессе считывания значений из ячеек блока 7 эти эначс1шя выводятся из арифметического блока 8 на блок вывода 10, причем после каладого выполнения условия сравнения регистрируется разделительный символ. В результате чего устройством вывода будет зафиксирована последовательность кодов индексов, соответ -ствующая разложению исходной перестановки в произведение циклов, которые будут отделены друг от друга разделительными символами. Таким образом преимущественно предлагаемого устройства по сравнению с известным заключается в том, что при минимальном добавлении элементов (регистр и переключатель) его функциональные возможности знач .тельно увеличиваются, поскольку дополнительно возможно определение транспозиций и разложение перестановки и произведение циклов. Формула изобретения Устройство для матричных вычислений, содержащее формирователь импульсов, выход которого соединен с входом счетчика импульсов, выход ко торого подключен к первому входу блока вывода, блок ввода, информаци онный выход которого соединен с информационным входом блока памяти, адресный вход которого подключен к выходу коммутатора, первый вход которого подключен к выходу первого реверсивного счетчика, вход которого соединен с выходом второго реверсивного счетчика, причем установочные входы первого и второго ре версивных счетчиков соединен с и 1ходом числа элементов блока ввода, генератор импульсов выход которого соединен с. числовыми входами первого и второго реверсивных счетчиков, блок управления, содержащий генератор тактовых импульсов, сдви- говый регистр и шифратор, причем выход генератора тактовых импульсов соединен с выходом сдвинового ре пестра, вькод которого подключен к входу шифратора, первый - восьмой выходы которого соединены с управляющими входами соответственно блока памяти, блока ввода, второго реверсивного счетчика, генератора импульсов, первого реверсивного счетчика, коммутатора, блока ввода и счетчика импульсов, арифметический блок, содержащий два регистра и узел сравнения, причем выходы первого и второго регистров подключены соответственно к первому и второму входам узла сравнения, выход которого соединен с входом формирователя импульсов, девятый выход шифратора соединен с управляющими входами узла сравнения, первого и второго регистров, отличающееся тем, что, с целью расширения функциональных возможностей за счет вычисления числа транспозиций и разложения перестановки в произведении циклов, в него введены третий регистр и переключатель, первый выход которого подключен к второму входу блока вывода, выход третьего регистра соединен с входом второго регистра арифметического блока и вторым входом коммутатора, вход третьего регистра соединен с вторым выходом переключателя, вход которого подключен к выходу блока,памяти, причем десятый выход щифрато- ра блока управления соединен с управляющим входом третьего регистра. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 336664, кл. G 06 F 15/32, 1970. 2,Авторсйое свидетельство СССР № 746533, кл. G 06 F 15/32, 1978 (прототип).

Фиг.1

Фиг.2

Л

W 4 W J 4 L

15 г55 i i

5 t 11 1

Л ф л лч

д

г/г

н

33

12

У

д

де

f

J

Фи9.5

Фиа.б