Устройство для обращения матриц

.Р.Дудаов и А.8 8) ционный буфернк второ образуют первый вход коммутатор блока памяти по информационному и к информацион дачи, третий и онные входы ком к выходам второ.Н,Борисеналило ду коммутатора входу ключа выертый информацитора подключены третьей констанх) Авторское20810, кл. е Ав У 404Ав 9 59 1975. ы блока памяти нстантр В видетельство СССС 06 Р 15/32,видетельство СССС 06 Г 15/347 орское 90, кл. орское 726, к(54)(57) 1.УСТРОЙСТВО ДЛЯ ОБРАЩЕНИЯМАТРИЦ, содержащее блок управления,ключ выдачи, выходы которого являются выходами 1 элементов обращеннойматрицы устройства, где= 1 п - номер строки матрицы, 1 = 1,в - номерстолбца матрицы, п - порядок матрицы, И сумматоров константы, вычислитель, включающий первый и второйсумматоры, о т л и ч а ю щ е е с ятем, что, с целью расширения функциональных возможностей устройстваза счет обращения матриц произвольной размерности, в него введеныкоммутатор, буферный блок памяти,блок памяти констант, выход первойконстанты которого подключен к первым входам сумматоров константы,вторые входы которых являются информационными входами соответствующихц- элементов диагонали матрицы (==1 р ), выходы л сумматоров константы и информационные входы 1 элементов матрицы ромежуточных результатов уменьшмых, первых и вторых сомножителе вычислителя подключены к одн иным выходам коммутатора, вход кода управления и вход выбора которого подключены к одноименным выходам блока управления, выход выдачи ре:зультата которого подключен к вход стробирования информации ключа выдачи, выходы первой и второй константы блока памяти констант подкл чены к одноименным входам вычислителя соответственно, выход которогоподключен к информационному входубуферного блока памяти, первый ивторой входы записи которого подключены к прямому и инверсному выходамзаписи блока управления, вход константы которого подключен к выходучетвертой константы блока памятиконстант, коммутатор содержит мультиплексоры предварительной коммутации, выделения диагонального элемента, уменьшаемых, первых и вторыхсомножителей, первый, второй инфор-,мационные и адресный входы мультиплексора предварительной коммутацииявляются первым, вторым информационными входами входом выбора ком1211755 Составитель А. Ушакоенова Техред Л.Микеш орректор Т.Ко дакт аказ 642/54 4 Патент", г.Ужгород, ул.Проек Филиал Тираж 673 ВНИИПИ Государственного по делам изобретений и 13035, Москва, Ж, РаушПодписноомитета СССР открытии кая наб., д.4/5мутатора соответственно, выходы значений диагональных элементов мультиплексора предварительной коммутацииподключены к информационным входаммультиплексора выделения диагонального элемента, выход мультиплексорапредварительной коммутации подключен к первым информационным входам.мультиплексоров уменьшаемых и первого сомножителя и к информационномувходу мультиплексора второго сомножителя, вторые информационные входымультиплексоров уменьшаемых и первого сомножителя объединены и являютсятретьим информационным входом коммутатора, третий информационныйвход мультиплексора уменьшаемых является четвертым информационным входом коммутатора, адресные входымультиплексоров выделения диагонального элемента, уменьшаемых, первыхи вторых сомножителей объединены иявляются входом кода управления коммутатора, выходы мультиплексоровввьщеления диагонального элемента,уменьшаемых, первых и вторых сомножителей являются одноименными выходами коммутатора, а в вычислительвведены блок вычисления обратнойвеличины, с первого по третий умножители, выход первого сумматоравычислителя через блок вычисленияобратной величины подключен к перво-.му входу первого умножителя, второйвход которого является входом первой константы вычислителя, первый ивторой входы первого сумматора являются входом промежуточного результата и входом второй константы вычислителя соответственно, первый и второй входы второго умножителя являются входами первого и второго сомножителей вычислителя, выходы первогои второго умножителя подключены кпервому и второму входам третьегоумножителя, выход которого подключен к первому входу второго сумматора, второй вход и выход которогоявляются входом уменьшаемых и выходом вычислителя, блок управления содержит триггер запуска, триггер выдачи, триггер состояния, генератор тактовых импульсов, первый и второй одновибраторы, элЕмент И, элемент НЕ, счетчик, схему сравнения, формирователь сигнала выбора, вход установки триггера запуска и вход сброса триггера выдачи объединены и являются входом запуска блока управления устройства, выход триггера запуска подключен к информационному входу триггера состояния, выход которого подключен к первому входу элемента И, выход которого подключен к входу элемента НЕ и через первый одновибратор к счетному входу счетчика и является прямым выходом записи блока управления, выход элемента НЕ является инверсным выходом записи блока управления, выход генератора тактовых импульсов подключен к входу синхронизации триггера состояния и через второй одновибратор к второму входу элемента И, выход счетчика подключен к первому входу схемы сравнения, к входу формирователя сигнала выбора и является выходом кода управления блока управления, выход формирователя сигнала выбора и выход триггера выдачи являются выходами выбора и выдачи результата блока управления, второй вход схемы сравнения является входом константы блока управления, выход схемы сравнения подключен к входам сброса триггеров запуска и состояния и к входу установки триггера выдачи.2. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что блок буферной памяти содержит два последовательно включенных регистра, информационный вход первого регистра и выход второго регистра, являются информационным входом и выходом блока, входы синхронизации первого и второго регистров являются первым и вторым входами записи блока.1211755 45 50 55 Изобретение относится к вычислительной технике, предназначенодля выполнения операций, связанныхс обращением матриц, и может бытьиспользовано в специализированных 5устройствах обработки информации прирешении задач оценивания и управления, сводящихся к действиям надматрицами.Целью изобретения является рас-10ширение функциональных возможностейустройства за счет обращения матрицпроизвольной размерности.На фиг,1 представлена функциональная схема устройства для обращения матриц; на фиг.2 - функциональная схема сумматоров константы;на фиг.З - функциональная схемакоммутатора; на фиг.4 - функциональная схема вычислителя, на фиг.5 -функциональная схема буферногоблока памяти; на фиг.6 - функциональная схема блока управления; нафиг.7 - функциональная схема мультиплексора предварительной коммутации, на фиг.8 - функциональнаясхема мультиплексора вьщеления диагонального элемента; на фиг.9 -функциональная схема мультиплексорауменьшаемых; на фиг.10 - функциональ 30ная схема мультиплексора первых сомножителей, на фиг.11 - функциональная схема мультиплексора вторых сомножителей; на фиг.12 - функциональная схема формирователя знаменателя вычислителя; на фиг.13 -функциональная схема второго умножителя, на фиг.14 - функциональнаясхема третьего умножителя; нафиг.15 - функциональная схема второго сумматора; на фиг.16 - функциональная схема формирователя сигналавыбора; на фиг.17 - временная диаграмма работы блока управления нафиг.18 - таблица результатов вычислений на выходах блоков на каждомшаге вычислений,Устройство обращения матриц(фиг.1) содержит информационныевходы 1 элементов матрицы, О сумматоров константы 2, коммутатор 3,вычислитель 4, буферный блок 5 памяти, ключ 6 выдачи, блок 7 памятиконстант, выходы 9 элементов обращенной матрицы, шину 10 первойконстанты, первый информационныйвход 11 коммутатора, шину 12 третьей константы, второй информационныйвход 13 коммутатора 3, выходы 14-17 промежуточного результата уменьшаемых первых и вторых сомножителей соответственно, выход 18 вычислителя 4, шину 19 второй константы, вход 20 кода управления коммутатора 3, шину 21 четвертой константы, вход 22 выбора коммутатора 3, прямой и инверсный входы 23 и 24 записи буферного блока 5 памяти, вход 25 выдачи результата ключа 6Группа и сумматоров константы 2 содержит сумматоры 26 по числу диагональных элементов матрицы.Коммутатор 3 (фиг.З) содержит мультиплексор 27 предварительной коммутации, мультиплексор 28 вьщеления диагонального элемента, мультиплексор 20 уменьшаемых, мультиплексор 30 первых сомножителей и мультиплексор 31 вторых сомножителей.Вычислитель 4 (фиг.4) содержит формирователь знаменателя 33, второй и третий умножители 34 и 35, второй сумматор 36, первый, второй входы 37 и 38 и выход третьего умножителя 35Буферный блок 5 памяти (фиг.5) содержит первый и второй регистры 40.1Блок управления 8 (фиг.6) содержит генератор 41 тактовых импульсов, первый одновибратор 42, триггер 43.1 запуска, триггер 43.2 выдачи, триггер 44 состояния, элемент И 45, элемент НЕ 46, второй одновибратор 47, счетчик 48, схему 49 сравнения и формирователь 50 сигнала выбора, вход 51 запуска блока 8 .и устройства, выход 52 генератора 41, информационный вход 53 триггера 44, первый и второй входы 54 и 55 элемента И 45, выход 56 схемы 49, счетный вход 57 счетчика 48.Мультиплексоры 27-31 выполнены по схемам, приведенным на фиг7-1 с использованием мультиплексоров 58.Формирователь знаменателя 33 (фиг. 12) вычислителя 4 содержит первый сумматор 26, блок 59 вычисления обратной величины, первый умножитель 60.Формирователь 50 сигнала выбора (фиг.16) содержит элемент НЕ 61 и элемент И-НЕ 62.В устройстве реализован следующий алгоритм для обращения матрицы порядка я (алгоритм Ершова). Пустьтребуется обратить матрицу порядка п ал аг . а 4 паг агг " агл ап апг " апп Согласно алгоритму для вычисленияматрицы А необходимо провести(О) (3) 1) (и)вычисления матриц: А А ,А , Агде А 1 = А - Е , а Е - единичнаяматрица и а. а1, в =8 =, (м =1 р) 3 О,л Рассмотрим работу устройства на примере обращения произвольной матрицы третьего порядка, так как при дальнейшем увеличении порядка матрицы примеры становятся громоздкими. Запишем исходную матрицу 121 А= 213 111Нетрудно показать, что обратная ейбудет матрица-2 -1 5 1 0-1 1 1-3 Работа устройства начинается стого, что по входам 1 исходная матрица в виде последовательности ееэлементов, полученная разложениемпо строкам 121213111,поступает через и сумматоров константы 2 на первый информационныйвход 11 коммутатора 3, при этом насумматорах константы 2 из диагональных элементов матрицы вычитается"1", поступающая по шине 10 первойконстанты из блока 7 (двоичный эквивалент чисел не используется прирассмотрении работы устройства, таккак при этом теряется наглядность).Таким образом, на входе 11 коммутато 1211755 021203110,1 О 15 20 ном входе триггера 44 (фиг,17). Перевод триггера 44 в единичное состояние происходит в момент появления на его счетном входе тактового импульса от генератора 41 тактовых импульсов. В результате с выхода триггера 44 "1" поступает на первый вход элемента И 45, обеспечивая прохождение синхроимпульсов, поступающих на второй ее вход от первого одновибратора 42. С выхода элемента И 45 синхроимпульсы поступают на вход второго одновибратора 47, формирующего импульсы, по.заднему фронту синхроимпульсов, которые являются счетными импульсами счетчика 48. Период следования синхроимпульсов выбирается из условия полного завершения одного шага вычислений.1На первом шаге вычислений с выхода счетчика 48 поступает в двоичном коде "1" на выход 20 и на вход формирователя 50, в соответствии с законом работы которого (фиг.16) на его выходе на первом шаге формируется "0". На всех последующих шагах на выходе 22 присутствует "1". Так как вывод 22 является управляющим для мультиплексора 27 предварительной коммутации, то в соответствии с законом работы, на его выход передается последовательность чисел с шины 11 при сигнале на выводе 22, равном "0" (первый шаг вычислений) или последовательность чисел с шины 13 при сигнале на выводе 22, равном "1" (фиг.7), т,е. на первом шаге на выходе мультиплексора 27 предваритель 25 30 35 40 45 50 55 ра 3 формируется последовательностьчисел которая поступаетфна мультиплексор27 предварительной коммутации 27(фиг.3) коммутатора 3. Основная работа устройства осуществляется блоком 8 управления и начинается подачей сигнала на вход 51 внешнего запуска (фиг.17). При этом сбрасывается в нуль счетчик 48, переводится в нулевое состояние триггер 43,2, закрывая ключ 6, который запрещает вывод информации из буферного блока 5 во время вычислений, а также переводится в единичное состояние первый триггер 43,1, обеспечивая появление "1" на информацион11755 Фне 10 первой константы, в первый умножитель 60, В итоге на первом шагена шину 37 поступает число 5О 021042021,15 О. 20 25 100203110. 30 121 О 2 1 5ной коммутации будет сформированапоследовательность чисел 021203110,которая поступает на входы мультиплексоров выделения диагонального элемента 28, уменьшаемых 29, первых сомножителей 30 и вторых сомножителей 31 (фиг.3). В соответствии с законом работы мультиплексора 28 выделения диагональных элементов (фиг.8) к его выходу подключается шина, номер диагонального элемента которой совпадает с номером шага вычислений переданного по шине кода управления 20 из блока 8 управления, т.е. на первом шаге на выход 14 передается число Последовательность чисел по шине 32поступает на вход мультиплексора 29уменьшаемых, на выходе которого в соответствии с законом работы и номером шага вычислений (фиг.9) сформируется на первом шаге последовательность чисел Последовательность чисел с выходамультиплексора 27 предварительнойкоммутации поступает на вход мультиплексора 30 первых сомножителей(фиг. 10), на выходе которого на первом шаге в соответствии с закономработы и номером шага вычислений,поступающего по шине 20," сформируется следующая последовательность чисел Кроме того, последовательность чисел по шине 32 также поступает навход мультиплексора 31 вторых сомножителей, на выходе которого на первом шаге вычислений (фиг.1) появляется последовательность чисел По выходу 14 с мультиплексора 28выделения диагонального элементачисло "0" на первом шаге поступаетна вход формирователя знаменателя 33(фиг.12), где складывается с "1",поступающей по шине 19 второй константы блока 7 констант, преобразуется в обратную величину в блоке вычисления обратной величины 59 и умножается на "-1", поступающую по ши 35 40 45 50 55 С выходов мультиплексоров первых сомножителей 30 и вторых сомножителей31 последовательность чисел поступает на входы второго умножителя 34(фиг.13), где производится их взаимное перемножейие, в результате чегона выходе на первом шаге формируетсяпоследовательность чисел1 которая по шине 38 поступает навход третьего умножителя 35 (фиг.14),в котором все числа последовательности умножаются на число, переданноепо шине 37 из формирователя знаменателя 33, в результате чего напервом шаге на шину 39 передаетсяпоследовательность чисел 0-2-1 0-4-2 0-2-1,которая в свою очередь складываетсяв соответствии с номерами с последовательностью чисел, поступающей пошине 15, во второй сумматор 36(фиг.15), на выходе которого на первом шаге формируется последовательность чисел 1 -2 -1 2 -4 1 1 -1 -1. Данная последовательность чисел пошине 18 поступает на входы первогорегистра 40 буферного блока 5 .(фиг.5), который служит для развязки между собой шагов вычислений иустранения эффекта "гонок". Во время вычисления на каком-либо шаге напервый регистр 40 по выводу 23 поступает управляющий сигнал "0" с выходаэлемента И 45 блока управления 8(фиг.6), разрешающий запись информации в данный регистр, в то времякак по выводу 24 на второй регистр40 поступает "1" с выхода элемента И-НЕ 46 блока управления 8, разрешающая чтение информации из этогорегистра. Период следования синхроимпульсов с выхода первого одновибратора 42 выбираешься таким образом,чтобы за время существования низкого перепада напряжения на его выходе полностью завершались вычисленияна данном шаге и запись результатав первый регистр 40 (фиг,17). При1211755 8 5 записывается последовательность чисел ности. появлении высокого потенциала навыходе элемента И 45 на первый регистр 40 йоступает "1", а на второй0, т.е. происходиз перезапись ин -формации из первого регистра во второй. При появлении следующего синхроимпульса выдается разрешение начтение результата из второго регистра 40 и на запись результата следующего шага вычисления в первый регистр 40. Количество шагов вычислений равно порядку обращаемой матрицы. Результаты на выходах отдельныхблоков для каждого шага приведеныв таблице (фиг.18). На каждом шаге вычисления в схеме сравнения 49 происходит сравнение номера шага вычисления, поступающего с выхода счетчика 48 и числа "4" (в общем случае "и+1", где И порядок матрицы), поступающего по шине четвертой константы 21 из блока констант 7 (фиг.6). В результате окончания последнего третьего шага вычисления во второй регистр 40 буферного блока-2 - 1 5 1 0 -1 1 1 -3,представляющая элементы обращеннойматрицы Ь . В момент появления следующего четвертого синхроимпульса навыходе элемента И 45 блока управления 8 на управляющий вход второго О регистра 40 буферного блока 5 поступает сигнал "1" разрешения чтения.Номер четвертого синхроимпульсапоступает также на вход схемы сравнения 49, в результате чего на ее 15 выходе формируется управляющий импульс, который переводит триггер 43.2в единичное состояние, тем самымвыдав разрешение на открытие ключа6 и, соответственно, на вывод резуль тата, а также перебросит в нулевоесостояние триггеры 43.1 и 44, чтосоответствует запиранию блока управления 8 и окончанию вычисления.Устройство решает задачу обращения для матриц произвольной размер