Устройство для приведения матрицы к треугольной идемпотентной форме Советский патент 1987 года по МПК G06F17/16 

Устройство содержит блок 1 ввода информации, mxm двоичную матрицу 2, блок 3 памяти, ячейки 4 памяти, блок 5 выбора столбца, переставляемого с первым столбцом, коммутатор 6 входов ячеек 4 памяти первого столбца, второй блок 7 m элементов И, третий блок 8 га элементов И, блок 9 управления, блок 10 инверторов, первьм блок 11 элементов И, элемент ИЖ-НЕ

1

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

Цель изобретения - повышение

быстродействия.

На фиг.1 приведена структурная схема устройства для приведения матрицы к треугольной идемпотентной форме; на фиг.2 - структурная схема ячейки памяти; на фиг.З - временные диаграммы на выходах блока управления; на фиг.4 - структурная схема блока управления; на фиг.З - блок выбора столбца, переставляемого с первым столбцом; на фиг.6 - пример реализации предлагаемого устройства. Устройство для приведения матрицы к треугольной идемпотентной форме содержит блок 1 ввода входной информации, шхт двоичную матрицу 2, блок 3 памяти, ячейки 4 памяти, блок 5 выбора столбца, переставляемого с первым столбцом, коммутатор 6 входов ячеек 4 памяти первого столбца, второй блок 7 m элементов И, третий блок 8 ш элементов И, блок 9 управления, блок 10 инверторов, первьй блок 11 И элемент ШШ-НЕ 12, блок 13 вывода решения.

Ячейка 4 памяти (фиг.2) содержит коммутатор 14, элемент 15 памяти, элемент И 16, сумматор 17 по модулю два, три информационных входа 18-20, три управляющих входа 21-23, вход 24 записи, блокировйчньй вход 25, выход 26 ячейки памяти.

12, 13 вывода решения. Наличие в устройстве блоков 7 и 8 элементов И, коммутатора входов ячеек памяти первого столбца, а в составе каждой ячейки памяти - коммутатора входов элементов памяти поэволяет приводить матрицу к треугольной идемпотентной форме за 2т временных циклов (в про- тотипе - на 3т циклов), что позвеля ет достигнуть цели изобретения. 6 ил.

Коммутатор 14 выполнен в вчде элемента 2-2-2И-3 ИЛИ.

БЛОК 9 управления работает в соот ветствии с временными диаграммами, полученными на выходах 24, 21, 23, . 27 и 28 блока (фиг.З). Блок 9 управления (фиг.4) содержит генератор 29 тактовых импульсов. Триггеры 30-32, элементы И -33 и 34, счетчик на m 35, триггер 36, причем выход генератора 29 тактовых импульсов соединен с пер Bbw выходом 24 блока 9 управления, второй вьгход 21 которого соединен с выходом триггера 30. Прямой и инверсный выходы триггера 32 через элементы И 33 и. 34 соединены соответственно с третьим 27 и четвертым 23 выходами блока 9 управления, пятый выход 28 которого подключен к выходу триггера 36.

Блок 5 выбора столбца, переставляемого с первым столбцом, содержит т-1 инверторов 37, т-1 элементов И 38, инверторов 39, т-1 элементов И 40, т-2 инверторов 41, т-2 элементов И 42, элемент ИЛИ-НЕ 43, т-1 элементов И 44, т-1 элементов ИЖ 45,

элемент ИЛИ 46 (фиг.5). I

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

В начальный момент производится установка ячеек 4 памяти в нулевое состояние, триггеров 30 и 32 блока 9 в единичное состояние, триггеров 31 и 36, счетчика 35 блока 9 в нулевое состояние (цепи установки не показаны) . Триггер 30 перебрасывается в нулевое состояние первым импульсом . 24 и формирует импульс 21.

В момент действия импульса на первом управляющем входе 21 с выходов блока 1 ввода информации в ячейки 4 памяти матрицы по входу 18 первым импульсом 24 эаписьюается а , , заданные для всех ,,2,...,т, а в

ячейки 4 памяти блока 3 памяти -

т-мерный вектор-строка b.

Задним фронтом импульса 21 триггер 31 устанавливается в единичное состояние, при этом элементы И 33 и 34 открываются по первым входам, а триггер 32 начинает работать в счетном режиме.

20

Во время действия первого импульса на третьем выходе 27 блока 9 управления, на входах 23 и 25 имеет место нулевой потенциал, при этом сигнал на выходах 26 ячеек 4 памяти соответствует сигналу на выходах элементов 15 памяти данных ячеек 4 памяти, а на входы блока 5 выбора столбца, переставляемого с первым столбцом, подаются сигналы с выходов 25 26 ячеек 4 памяти первой строки матрицы 2 и с выходов 26 диагональных ячеек 4 матрицы. Блок 5, имеющий m выходов, определяет столбец, который необходимо переставить с первым столбцом по следующему принципу: если на. выходе 26 ячейки 4 памяти первой строки первого столбца матрицы 2 имеет место единичный потенциал

на первом.выходе блока 5, на 2-ш выходах блока 5 формируется нулевой сигнал. Если на выходе 26 ячейки 4 памяти первой строки первого столбца

0 |вым выходом в диагональной ячейке 4 единичные потенциалы формируются на выходах тех элементов И 38, входы кот орых соединены с выходами данных столбцов, при этом с помощью инвер- торов 39 и элементов И 40 формируется единичный потенциал только на выходе того элемента И 40, вход которого через элемент И 38 соединен с единичным выходом верхней ячейки 4 и нулевым выходом диагональной ячейки и крайнего левого столбца, т.е. с помощью инверторов 39 и элементов И 40 осуществляется выбор старшего значащего разряда (крайнего левого столбца) . На выходе элемента ИЛИ-НЕ 43 в данном случае имеет место нулевой потенциал, блокирующий элементы И 44, а на выходах элементов ИЛИ 45 единичный потенциал имеет место только на выходе того элемента ИЛИ, который соединен с единичным выходом элемента И 40 и соответствует номеру крайнего левого столбца, который необходимо

30

переставить с первым столбцом. При ., то единичньш сигнал формируется 35 отсутствии столбца с единичным потенциалом на выходе верхней ячейки 4 памяти и с нулевым потенциалом на выходе диагональной ячейки 4 осуществляется выбор столбца крайнего левого матрицы 2 имеет место нулевой потен- 40 столбца с единичными выходами верхней циал, то единичный сигнал формирует- „ диагональной ячеек 4 памяти, при

этом на выходе элемента ИЛИ-НЕ 43 имеет место единичный потенциал, а с помощью инверторов 41 и элементов 45 И 42 осуществляется формирование единичного потенциала только на выходе того элемента И 42, который непосредственно соединен с крайним левым -столбцом (единичный выход верхней 50 ячейки 4 памяти). Данный единичный потенциал передается через элементы И 44, ЛГШ 45 и 46 на первый выход блока 5 и на тот выход, номер которого соответствует крайнему левому При наличии единичного потенциала 55 столбцу. Таким образом, во время ;ей- на выходе ячейки 4 памяти первой ствия импульсов на выходе 27 блока строки первого столбца путем инвар- 9 управления единичный сигнал имеет тирования данного сигнала первым место только на выходах блока 7 (на инвертором 39 на выходах элементов входах 22), номер которых соответстся на первом выходе и на выходе блока 5, номер которого соответствует номеру самого левого столбца матрицы 2, в котором на выходах верхней и диагональной ячеек 4 памяти имеет место соответственно единичный и нулевой потенциалы, а при отсутствии такого столбца единичный сигнал формируется на выходе блока 5, номер которого соответствует номеру самого левого столбца матрицы 2, в котором на выходе верхней ячейки 4 памяти имеет место единичный потенциал.

0

5

И 40, а также на выходе элемента ИЛИ-НЕ 43, на выходах элементов ИЛИ 45, а, следовательно, на 2-т выходах блока 5 имеет место нулевой потенциал, а на первом выходе блока 5 единичный потенциал. При нулевом вы- . ходе верхней ячейки 4 первого столбца при наличии столбцов с единичным выходом на верхней ячейке 4 и нуле0 |вым выходом в диагональной ячейке 4 единичные потенциалы формируются на выходах тех элементов И 38, входы кот орых соединены с выходами данных столбцов, при этом с помощью инвер- торов 39 и элементов И 40 формируется единичный потенциал только на выходе того элемента И 40, вход которого через элемент И 38 соединен с единичным выходом верхней ячейки 4 и нулевым выходом диагональной ячейки и крайнего левого столбца, т.е. с помощью инверторов 39 и элементов И 40 осуществляется выбор старшего значащего разряда (крайнего левого столбца) . На выходе элемента ИЛИ-НЕ 43 в данном случае имеет место нулевой потенциал, блокирующий элементы И 44, а на выходах элементов ИЛИ 45 единичный потенциал имеет место только на выходе того элемента ИЛИ, который соединен с единичным выходом элемента И 40 и соответствует номеру крайнего левого столбца, который необходимо

0

вует первому и выбранному крайнему левому столбцам. С приходом импульса на вход 24 записи в ячейки 4 памяти первого столбца матрицы 2 и первой ячейки памяти в блоке 3 памяти по входу 19 осуществляется построчная запись информации из ячеек 4 памяти того столбца, который сЬответствует выбранному крайнему левому столбцу, а в данный крайний .левый столбец про изводится построчная перепись информации из первого столбца матрицы 2 и первой ячейки блока 3 памяти. В остальных ячейках 4 памяти матрицы 2 и блока 3 памяти информация остается без изменения. Если верхняя строка матрицы 2 является нулевой (при отсутствии крайнего левого столбца матрицы или первый столбец является крайним левым), в данном такте информация во всех ячейках 4 памяти остается без изменений. Во время действия первого единичного импульса на третьих управляющих входах 23 ячеек 4 памяти, на выходах 27 и на вторых управляющих входах 22 имеет место .нулевой потенциал, а блок 8 элементов И формирует единичный потенциал только на выходах, номера которых соответствуют номерам столбцов матрицы 2 (кроме первого), в которых в данный момент на выходах 26 верхних ячеек 4 памяти имеет место единичный потенциал. При этом в ячейках 4 памяти k-й строки 2-т столбцов производится суммирование по модулю два содержимого элемента 15 памяти данной ячейки 4 памяти с выходным сигналом ячейки 4 памяти данной k-й строки первого столбца, логически умноженным с сигналом на блокировочном входе 25 данной ячейки 4 памяти.

С приходом импульса на вход 24 записи в ячейки 4 памяти по третьим информационным входам 20 записывается информация с выходов 26 других ячеек 4 памяти в соответствии с про- изведенньми соединениями.

Таким образом, однократное выполнение (базисных операций алгоритма приведения матрицы к треугольной идемпотентной форме осуществляется за. два временных цикла, а приведение матрицы к треугольной идемпотентной форме осуществляется в результате ш-кратного выполнения базисных операций, т.е. за 2-т временных цикла.

В результате приведения матрицы 2 к треугольной идемпотентной форме блок 3 памяти содержит информацию некоторой строки, являющейся одним из решений & системы m линейных уравнений с m неизвестными вида 13. Ь. После m кратного выполнения базисных операций (при по дсчете счетчиком 35 блока 9 управления m импульсов 27) на выходе счетчика 35 формируется перепад, устанавливающий триеггер 31 блока 9 в нулевое состояние, а триггер 36 - в единичное состояние. При этом первым импульсом с выхода генератора 29 блока 9 триг-, гер 36 возвращается в исходное состояние, а на вьщоде 28 блока 9 управления формируется сигнал вывода решения, при этом вывод решения в блоке 13 осуществляется при условии отсутствия единичного сигнала хотя бы на одном из выходов блока 11 элементов И, т.е. при наличии единичного сигнала на выходе элемента ШШ-НЕ 12.

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

форме за 2т временных циклов, в то время как в известном устройстве данное преобразование осуществлялось за 3т временных циклов. Это приводит к сокращению времени обработки информации в 1,5 раза.

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

Устройство для приведения матрицы к треугольной идемпотентной форме, содержащее блок ввода входной информации, блок управления, mxm двоичную матрицу, состоящую из т ячеек памяти, блок памяти, состоящий из m ячеек памяти, блок инверторов, блок вы--. бора столбца, переставляемого с первым столбцом, первая группа входов которо- го подключена к выходам ячеек памяти первой строки матрицы, вторая группа входов объединена с входами блока ин- aei TopOB и соединена с выходами диагональных ячеек памяти двоичной матрицы, первьй блок элементов И, элемент ИЖ-НЕ, входы которого соединены с выходами

712

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

чены соответственно в блокировочным

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

5 т 20

25

30

35

40

45

50

55

148

равляющими входами ячеек памяти двоичной матрицы и блока памяти, третий выход блока управления подключен к вторым входам элементов И второго блока, четвертый выход блока управления соединен с третьими управляющими входами ячеек памяти двоичной матрицы и блока памяти и с вторыми входами элементов И третьего блока, пятый выход блока управления подключен к входу записи блока вывода решения, блокировочный вход которого подключен к выходу элемента ИЛИ-НЕ, вторые информационные входы ячеек памяти строки 2-т столбцов соединены с.выходом ячейки памяти первого столбца соответствующей строки, третий информационный вход ячейки памяти i-й строки (i 1-m-1) j-ro столбца (j 1-m-1) двоичной матрицы соединены с выходом ячейки памяти (1-«-1)-й строки (J+1)-го столбца двоичной матрицы, третий информационный вход ячейки памяти i-й строки т-го столбца двоичной матрицы .соединен с выходом ячейки памяти (i+1)-и строки первого столбца двоичной матрицы, третий информационный вход ячейки памяти ш-й строки j-ro столбца двоичной матрицы соединен с выходом ячейки памяти первой строки ()-ro столбца двоичной матрицы, третий

информационный вход яч1ейки памяти )

т-й строки ш-го столбца-двоичной матрицы соединен с выходом ячейки памяти первой строки первого столбца двоичной матрицы, третий информационный вход j-й ячейки памяти блока памяти соединен с выходом (j+1)-u ячейки памяти блока памяти, третий информационный вход т-й ячейки памяти блока памяти соединен с выходом первой ячейки памяти блока памяти, а в состав каждой ячейки памяти введен коммутатор, три информационных входа которого соединены с информа- ционньми входами ячейки памяти, три . управляющих входа коммутатора соединены с управляющими входами ячейки памяти, второй информационный вход коммутатора соединен с вторш4 входом элемента И данной ячейки памяти, а выход сумматора по модулю два подключен к выходу ячейки памяти.

Фиг.2

Фиг.З

) tacrrnllStr/n) )т1 ЩПя ЩГт 5) 1тп-3)Ш

18Vin}fy iy W & /e /F .(8 jjj20t-f ()()) ) (

/flT /X iB iW tw /йГ /F,,r „,

)()())(Гт() (2{П

Изобретение относится к области вычислительной техники и предназначено для решения систем линейных уравнений, определения коэффициентов линейного однородного разностного уравнения, определения кода М-после- довательностей. Цель изобретения - повьшение быстродействия устройства.. LliS 1C 00 00 sj

, Bxoff pg g ucmp сддига на 2-m разрядоб

, : 5 ;

OCF-CHff

w j /

Редактор Н.Бобкова

Составитель И.Пчелинцев

Техред Л.Олейник Корректор Л.Пилипенко

Заказ 7810/48 Тираж 673Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная, 4