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

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветсникСоцнапистнчесиикРеспублик(23) Приоритет Экуааретюа 4 кемктет СССР ае делам зоеретенкй и атермтвй(72) Автор изобретения Г.И.ЛевинИтнский филиал Всесоюзного научно-исследовавелааоогон проектно-конструкторского института по автоматизацййпредприятий промышленности строительных материалов(54) УСТРОЙСТВО ДЛЯ МАТРИЧНЫХ ВЫЧИСЛЕНЫ 1Изобретение относится к вычислительной технике и может быть использовано при создании средств вычислительной и управляющей техники, структура которых ориентирована на решении задач с,использованием методов матричной алгебры, теории множеств и комбинаторики.Необходимость определения числа инверсий и транспоэиций, кроме задач вычислительного характера, появляется, например, в АСУТП, где необходимо сократить время (или определить его), необходимое для упорядочения поступающйх значений технологических параметров относительно выдаваемых управляющих воздействий, особенно если последовательность выдачи управляющих воздействий зависит от порядка поступления отклонений значений контропируеиах параметров.Известно устройство для матричных вычислений - определения знака 2членов определителя матриц, т.е.четности или нечетности перестановки, содержащее коммутатор, матри цу переключающих ячеек, ретмстр,запоминающие триггеры, блок эадерж-.5ки, элементы задержки.Однако данное устройство имеетограниченные функциональные возможности.Известно также устройство для матричных вычислений - определения числаинверсий, содержащее связанные между собой арифметический и запоминающий блоки и совдиненный с ним повходам;и выходам блок управления,коммутатор, связанные между собой. реверсивные счетчики, счетчик жпульсов и генератор импульсов, соединенные входами с блоком управления, 20 формирователь, вход которого подключен к выходу арифметического блока,а выход - к счетчику импульсов, входыреверсивных счетчиков подключЕнык генератору импульсов, устройствоввода, выход которого подключен к запоминающему блоку и входам. реверсивных счетчиков, один из выходов ,второго реверсивного счетчика соединен с входом коммутатора, выход которого подключен к запоминающему блоку, а выход счетчика импульсов соединен с устройством вывода.Недостатком известного устройства является недостаточно широкие функциональные возможности, так как оно не обеспечивает автоматическое определение числа транспоэиций и не осуществляет разложение исходной перестановки в произведение циклов.Цель изобретения - расширение функциональных воэмакностей устрой ства.Это достигается тем, что в устройство, содержащее формирователь импульсов, выход которого подключен к первому входу блока вывода, блок ввода, информационный выход которого соединен с информационным входом блока памяти, адресный вход которого подключен к выходу коммутатора, первый вход которого подключен к выходу первого реверсивного счетчика 1 вход которого соединен с выходом второго реверсивного счетчика, причем установочные входы первого и второго реверсивных счетчиков соединены с выходом числа элементов блока ввода, генератор импульсов, выход которого соединен с числовыми входами первого и второго реверсивных счетчиков, блок управления, содержащий генератор такто вых импульсов, сдвиговый регистр и шифратор, причем выход генератора тактовых импульсов соединен с выходом сдвигового регистра, выход которого подключен к входу ,шифратора, первый - восьмой выходы которого соединены с управляющими входами соответственно блока памяти, блока ввода, второго реверсивного счетчика, генератора импульсов, первого реверсивного счетчика, коммутатора, блока вывода и счетчика импульсов, арифметический блок, содержащий два регистра и узел сравнения, причем выходы первого и второго регистров подключены соответственно.к первому и второму входам узла сравнения, выход которого соединен с входом формирователя импульсов, девятый выход шифратора соединен с управляющими входами узла сравнения, первого и 5 16 13 29 И ЗО 35 40 второго регистров, введены третий регистр и переключатель, первый выход которого соединен с.входом первого регистра, выход которого подключен к второму входу блока вывода, выход третьего регистра соединен с входом второго регистра арифметического блока и вторым входом коммутатора, вход третьего регистра соединен с вторым выходом переключателя, вход которого подключен к выходу блока памяти, причем десятый выход шифратора блока управления соединен с управляющим входом третьего регистра.На, фиг, 1 приведена блок-схема предлагаемого устройствами на фиг. 2 " схема блока управления; на фиг. 3 - схема коммутатора; на фиг. 4 - схема арифметического блока, на фиг. 5 - схема блока вводами на фиг. 6 - схема блока вывода.Устройство содержит блок 1 управления, генератор 2 импульсов, реверсивные счетчики 3 и 4, коммутатор 5, блок 6 ввода, блок 7 памяти, арифметический блок 8, переключатель 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 1,например, устройство фотоввода Г 5 150), клавиатуру 34 ручного ввода, шифратор 35 и переключатель 36 выхода. Вход 37 служит для ввода перфоленты в блок ввода, который запускается по второму входу с блока 1 управления. Переключатель выхода 36 служит для переключения при работе от ручного ввода с клавиатуры 34 на работу от Фотоввода 33.38286 8 3 10 13 20 23 30 33 40 4 30 Я 7 9равное количеству инверсий в даннойперестановке.Четкость или нечетность перестановки однозначно определяется по чет.ности или нечеткости числа, получаемого в счетчике 12 импульсов.Число инверсий из счетчика 12 импульсов переносится в блок 1 О вывода.При вычислении определителя матрицы, т.е. когда индексами элементовперестановки являются вторые индексы элементов матрицы, четкость перестановки дает соответствующему членуматрицы знак "плюс", а нечетностьзнак "минус".В режиме определения транспозиций переключатель 9 устанавливается в положение б.Исходная перестановка вводитсяв блок 6 ввода аналогично предыдущему режиму работы, причем коды индексов вводимой перестановки в ячейке запоминающего блока 7 располагаются последовательно, начиная сячейки с номером 1, М 1,По команде с блока 1 управленияс помощью .коммутатора 5 из блока 7выбирается код индекса а элемента1перестановки, хранящийся в ячейке сномером М=1. Код заносится в регистр13, а номер ячейки М,1=1 в арифметический блок 8, где происходит сравнение кода а 1 с номером ячейки М=1,Если выполняется равенство а =МК 1=1, то аналогично предыдущему выбирается код индекса а 1 ,хранящегосяв ячейке с номером М= блока 7, иснова производится сравнение а=Ц=М=2. При выполнении этого равенства происходит выборка следующегокода индекса, т,е. а и выполня"ется операция сравнения а=М=3 ит.д. до ячейки с номером п=п.Если в результате п сравнений выполняются равенства кодов индексовперестановок и соответствующих им .номеров ячеек блока 7, то это свидетельствует об отсутствии транспозиций в исходной перестановке и всчетчике 12 импульсов будет нулевоезначение.При несовпадении на некотором шаге кода индекса элемента перестановки с номером ячейки блока 7, вкоторой хранится этот код, выполняются следующие операции,По команде блока 1 управлениякод индекса элемента перестановкииз регистра 13 подается на вход ком. мутатора 5, который осуществляетвыборку из ячейки с номером, равным этому коду, новый код индекса, хранящийся в данной ячейке блока 7.Аналогично предыдущему, в арифметическом блоке 8 происходит сравнение обоих кодов, и через формирователь 11 в счетчик 12 импульсовзаносится "единица".На этом заканчивается один циклработы устройства.Если в,этом цикле сравниваемыекоды окажутся равными, то содержимое регистра 13 и ячеек блока 7,из которых производилось считывание кодов индексов, гасятся в нулевое состояние. блока 7.Если при сравнении окажется, чтоа,Ф ае то код индекса а иэ регистра 13 передается на вход коммутатора 5, с помощью которого из ячейки блока 7 с номером, равным этомукоду, считывается значение кодаиндекса, хранящегося в этой ячейке,и засылается в арифметический блок8, куда также передается код индекса, хранящегося в режиме регистра 13Затем в блоке 8 производится срав-нение этих двух кодов, и через формирователь 11 в счетчик 12 импульсовзаносится единица,В случае равенства сравниваемыхзначений, значений регистра 13, содержимое ячеек, из которых произошло считывание кодов индексов перестановки гасится в нулевое состояние.При невыполнении равенства аналогично предыдущему выполняется следукщий циклеТаким образом, количество циклов, в которых не выполняется равенство кодов индексов элементов исходной перестановки с номерами соответствующих ячеек блока 7, будетсоответствовать количеству импульсов занесенных в счетчик 12 импульсов причем число, находящееся всчетчике 12 импульсов, после перебора всех ячеек равно числу транспозиций исходной перестановки.В процессе считывания значенийкодов индексов из блока 7, ячейкисодержимое которых уже было погашено в нулевое состояние, пропускаются коммутатором 5,В процессе считывания значенийиз ячеек блока 7 эти значения выво8286 10 9 93 дятся иэ арифметическопо блока 8 на блок вывода 10, причем после каждого выполнения условия сравнения ре гистрируется разделительвай символ.В результате чего устройством вывода будет зафиксирована последовательность кодов индексов, соответствующая разложению исходной перестановки в произведение циклов, которые будут отделены друг от друга разделительными символами.Таким образом преимущественно предлагаемого устройства по сравнению с известным заключается в том, что при .минимальном добавлении элементов (регистр и переключатель) его функциональные возможности значи.тельно увеличиваются, поскольку дополнительно возможно определение транспозиций и разложение перестановки и произведение циклов. 5 10 15 25 ,30 35 Ю 45 формула изобретения Устройство для матричных вычислений, содержащее. формирователь импульсов, выход которого соединен с входом счетчика импульсов, выход которого подключен к первому входу блока вывода, блок ввода, информационный выход которого соединен с информационным входом блока памяти, адресный вход которого подключен к выходу коммутатора, первый вход которого подключен к выходу первого реверсивного счетчика, вход которого соединен с выходом второго реверсивного счетчика, причем установочные входы первого и второго реверсивных счетчиков соединен с выходом числа элементов блока ввода, генератор импульсов выход которого соединен с. числовыми входами первого и второго реверсивных счетчиков, блок управления, содержащий генератор тактовых импульсов, сдвиговый регистр и шифратор, причем выход генератора тактовых импульсов соединен с выходом сдвинового регист" ра, выход которого подключен к входу шифратора, первый - восьмой выходы которого соединено с управляющими входами соответственно блока памяти, блока ввода, второго реверсивного счетчика, генератора импульсов, первого реверсивного счетчика, коммутатора, блока ввода и счетчика импульсов, арифметический блок, содержащий два регисТра и узел сравнения, причем выходы первого и второго регистров подключены соответ. ственно к первому и второму входам узла сравнения, выход которого сое-динен с входом формирователя импульсов, девятый выход шифратора соединен с управляющими входами узла сравнения, первого и второго регистров, о т л и ч а ю щ е е с я тем, что, с целью расширений функцио" нальных возможностей за счет вычисления числа транспозиций и разложения перестановки в произведении цик. лов, в него введены третий регистр и переключатель, первый выход которого подключен к второму входу блока вывода, выход третьего регистра соединен с входом второго регистра арифметического блока и вторым входом коммутатора, вход третьего регистра соединен с вторым выходом переключателя, вход которого подключен к выходу блока,памяти, причем десятый выход пнфратора блока управления соединен с управляющим входом третьего регистра.Источники информации, принятые во внимание при экспертизе1. Авторское свидетельство СССР В 336664, кл. О 06 Г 15/32, 1970.2. Авторское свидетельство СССР В 746533, кл. О 06 Г 15/32, 1978 (прототип).938286 Составител Техред И,А.Барано Джуга Корректор А.Гриценко У НИИПИ юиал ППП тент , г. Ужгород, ул. Проект Тираж 731Государственногоо делам изобретений35, Москва, Ж, Р комите и откр ушская Подписное СССР ий аб д, 4/