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

 

ОП ИСАНИЕ

ИЗО6РЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

Республик (п)938286 (61) Дополнительное к авт. сеид-ву— (22) Заявлемо 02.09.80 (21) 3211744/18-24 (51)NL. Кл.

G 06 F 15/31 с присоединением заявки 1Е (23) Приоритет

9куааратееннь4 кеннтет

СССР ае делам «зойретеннй

«етернтнй

Опубликовано 23.06.82. Бюллетень Мт 23

Дата опубликования описания 23.06.82 (56).УД К 681. 32 (088.8) Ф

Ъ

I (72) Автор изобретения

Г.И.Левин

"- 1

1 г ; - :

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

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

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

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

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

5 ки, элементы задержки.

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

Известно также устройство для матричных вычислений — определения числа инверсий, содержащее связанные между собой арифметический и запоминающий блоки и совдиненный с ним по входам;и выходам блок управления, коммутатор, связанные между собой реверсивтые счетчики, счетчик жпульсов и генератор импульсов, соединенные входами с блоком управления, 2о формирователь, вход которого подклю чен к выходу арифметического блока, а выход — к счетчику импульсов, входы реверсивных счетчиков подключены к генератору импульсов, устройство

938286 4

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

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

Цель изобретения — расширение функциональных ноэиакностей устрой. ства.

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

j0

И

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,например, устройство фотоввода FS 1501), клавиатуру 34 ручного ввода, шифратор 35 и переключатель 36 выхода. Вход 37 служит для ввода перфоленты в блок ввода, который запускается по второму входу с блока 1 управления. Переключатель выхода 36 служит для переключения при работе от ручного ввода с клавиатуры 34 на работу от фотоввода 33.

6 6 вырабатывает импульс и из счетчика

1! И

4 снова вычитается единица

Полученное в счетчике 4 число и-2 поступает на вход коммутатора 5, с помощью которого из блока 7 выбирается индекс элемента, находящегося в ячейке с номером и -2. Код этого индекса засылается в арифметический блок 8, где по аналогии с предыдущим проверяется условие (n)<)n -2),при выполнении которого заносится "единица" в счетчик 12 импульсов.

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

4 будет число, равное единице.

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

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

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

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

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

В процессе сравнений в счетчик

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

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

Процесс решения заканчивается выполнением и-1 цикла, после чего в

:счетчике 12 импульсов будет число, 5 93828

Схема блока 10 вывода содержит

I узел 38 индикации, печатающей узел

39 и триггер 40.

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

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

В режиме определения числа ин- 10 версий переключатель 9 находится в положении с1. Через блок 6 ввода в блок 7 памяти вводятся коды индексов (числа) К., К2,..., К и исходуюй перестановки а, а ...,а1,,которые 15 указывают место каждого элемента в исходной перестановке.

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

Кроме того, устройством решается еще одна сложная комбинаторная задача, а именно разложение перестановки в произведении циклов

Параллельно с вводом исходной пе- Зе рестановки через блок 6 ввода в блок

7, в реверсивные счетчики 3 и 4 зано- сится число и и вводится в коммутатор 5, с помощью которого из блока

7 считывается индекс элемента, вве- . З5 денного последним, т.е. занесенный в ячейку с номером и блока 7. Затем по команде блока управления 1 из содержимого реверсивного счетчика 4 имимпульсов с генератора 2 вычитается единица. Полученное в счетчике

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

Код этого индекса поступает в арифметический блок 8. По сигналу блока

1 управления коды индексов, хранящихся в арифметическом блоке 8, сравниваются и проверяется условие (n) ( (/n -1j, т.е. значение индекса перестановки в ячейке с номером е меньше значения индекса перестановки в ячейке с номером и-1 °

При выполнении этого условия в

55 счетчик 12 импульса через формирователь 11 и переключатель 9 наносится

"единица". Затем по сигналу блока

1 управления, генератор 2 импульсов

38286 8

7 9 равное количеству инверсий в данной перестановке.

Четкость или нечетность перестановки однозначно определяется по четности или нечеткости числа, получаемого в счетчике 12 импульсов.

Число инверсий из счетчика 12 импульсов переносится в блок 10 вывода.

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

В режиме определения транспозиций переключатель 9 устанавливается в положение б.

Исходная перестановка вводится в блок 6 ввода аналогично предыдущему режиму работы, причем коды индексов вводимой перестановки в ячейке запоминающего блока 7 располагаются последовательно, начиная с ячейки с номером 1, N I

По команде с блока 1 управления с помощью .коммутатора 5 из блока 7 выбирается код индекса а>, элемента

1 перестановки, хранящийся в ячейке с номером М=1. Код заносится в регистр

13, а номер ячейки М,>=1 в арифметический блок 8, где происходит сравнение кода а> „с номером ячейки N=l

Если выполняется равенство а =М

Ki 1

=1, то аналогично предыдущему выбирается код индекса ах >хранящегося в ячейке с номером М= блока 7, и снова производится сравнение а„=

7ф

=М 2. При выполнении этого равенства происходит выборка следующего кода индекса, т.е. а> и выполня" ется операция сравнения а =М =3 и т.д. до ячейки с номером п=п.

Если в результате и сравнений выполняются равенства кодов индексов перестановок и соответствующих им . номеров ячеек блока 7, то это свидетельствует об отсутствии транспозиций в исходной перестановке и в счетчике 12 импульсов будет нулевое значение.

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

По команде блока 1 управления код индекса элемента перестановки из регистра 13 подается на вход ком.5

1S

2S

55 мутатора 5, который осуществляет выборку из ячейки с номером, равным этому коду, новый код индекса, хранящийся в данной ячейке блока 7.

Аналогично предыдущему, в арифметическом блоке 8 происходит сравнение обоих кодов, и через формирователь 11 в счетчик 12 импульсов заносится "единица".

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

Если в:этом цикле сравниваемые коды окажутся равными, то содержимое регистра 13 и ячеек блока 7, as которых производилось считывание кодов индексов, гасятся в нулевое состояние. блока 7.

Если при сравнении окажется, что аК,4. а >то код >индекса(а1 иэ ре1 гистра 13 передается на вход коммутатора 5, с помощью которого из ячейки блока 7 с номером, равным этому коду, считывается значение кода индекса, хранящегося в этой ячейке, и засылается в арифметический блок

8, куда также передается код индекса, хранящегося в режиме регистра 13 °

Затем в блоке 8 производится сравнение этих двух кодов, и через формирователь 11 в счетчик 12 импульсов заносится единица.

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

При невыполнении равенства аналогично предыдущему выполняется следующий цикл °

Таким образом, количество циклов, в которых не выполняется равенство кодов индексов элементов исходной перестановки с номерами соответствующих ячеек блока 7, будет соответствовать количеству импульсов занесенных в счетчик 12 импульсов причем число, находящееся в счетчике 12 импульсов, после перебора всех ячеек равно числу транспозиций исходной перестановки.

В процессе считывания значений кодов индексов из блока 7, ячейки содержимое которых уже было погашено в нулевое состояние, пропускаются коммутатором 5.

В процессе считывания значений из ячеек блока 7 эти значения выво82 86 10

9 93 дятся иэ арифметическвпо блока 8 на блок вывода 10, причем после каждого выполнения условия сравнения ре гистрируется разделителыый символ.

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

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

1$

2S ,30

3$

Ю

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

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

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

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

Ф 336664, кл. G 06 F 15/32, 1970.

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

В 746533, кл. G 06 F 15/32, 1978 (прототип).

938286

Составитель А.Баранов

Редактор Н.Даугав Техред И. Гайду Корректор А.Гриценко

Заказ б

73 Тираж 731 Подписное

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

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

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