Устройство для приведения матрицы к треугольной идемпотентной форме

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (И) ш4 С 06 F 15 324

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Н АВТОРСНОМУ СВИДЕТЕЛЬСТВУ ь)(И1 37) .н,": (21) 3350304/24-24 (22) 04.11.81 (46) 07.02.87. Бюл. Р 5 (72) В.А.Алеев и А.А.Чудов (53) 681.32(088.8) (54) УСТРОЙСТВО ДЛЯ.ПРИВЕДЕНИЯ МАТРИЦЫ К ТРЕУГОЛЬНОЙ ИДЕМПОТЕНТНОЙ

ФОРМЕ (57) Изобретение относится к области вычислительной техники и предназначено для решения систем линейных уравнений, определения коэффициентов линейного однородного раэностного уравнения, определения кода М-последовательностей. Цель иэобретения— повышение быстродействия устройства. (56)Авторское свидетельство СССР и 624234, кл. G 06 F 15/324, 1976.

Берлекэмп Э. Алгебраическая теория кодирования. — M.: Мир, 1971, с.61-72, рис. 2.20-2.24.

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ц

1288714

Устройство содержит блок 1 ввода информации, шх m двоичную матрицу 2, блок 3 памяти, ячейки 4 памяти, блок

5 выбора столбца, переставляемого с первым столбцом, коммутатор 6 входов ячеек 4 памяти первого столбца, второй блок 7 ш элементов И, третий блок 8 m элементов И, блок 9 управления, блок 10 инверторов, первый блок 11.элементов И, элемент ИЛИ-НЕ

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

Цель изобретения — повышение быстродействия. t0

На фиг.1 приведена структурная схема устройства для приведения матрицы к треугольной идемпотентной форме; на фиг.2 — структурная схема. ячейки памяти; на фиг.3. " -временные диаграммы на выходах блока управления; на фиг.4 — структурная схема блока управления; на фиг.5 — блок

I выбора столбца, переставляемого с первым столбцом; на фнг.6 — пример 20 реализации предлагаемого устройства.

Устройство для приведения матрицы к треугольной идемпотентной форме содержит блок 1 ввода входной информации, шх ш двоичную матрицу 2, блок 25

3 памяти, ячейки 4 памяти, блок S выбора столбца, переставляемого с первым столбцом, коммутатор 6 входов ячеек 4 памяти первого столбца, второй блок 7 ш элементов И, третий блок 30

8 m элементов И, блок 9 управления, блок 10 инверторов, первый блок 11 И, элемент ИЛИ-HE 12, блок 13 вывода решения.

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

26 ячейки памяти.

12 блок 13 вывода решения. Наличие в устройстве блоков 7 и 8 элементов

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

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

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

29 тактовых импульсов соединен с первым выходом 24 блока 9 управления, второй выход 21 которого соединен с выходом триггера 30. Прямой и инверсный выходы триггера 32 через элементы И 33 и. 34 соединены соответственно с третьим 27 и четвертым

23 выходами блока 9. управления, пятый выход 28 которого подключен к выходу триггера 36.

Блок 5 выбора столбца, переставляемого с первым столбцом, содержит ш-1 инверторов 37, m-1 элементов И

38, m-1 инверторов 39, m-1 элементов

И 40, m-2 инверторов 41, m-2 элементов И 42, элемент ИЛИ-HE 43, m-1 элементов И 44, m-1 элементов ИЛИ 45, элемент ИЛИ 46 (фиг.5).

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

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

24 и формирует импульс 21.

1288714

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

m-мерный вектор-строка Ь;

Задним фронтом импульса 21 триггер, 31 устанавливается в единичное состояние, при этом элементы И 33 и

34 открываются по первым входам, а триггер 32 начинает работать в счетном режиме.

f5

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

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

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

При наличии единичного потенциала 55 на выходе ячейки 4 памяти первой строки первого столбца путем инвертирования данного сигнала первым инвертором 39 на выходах элементов

И 40, а также на выходе элемента

ИЛИ-НЕ 43, на выходах элементов ИЛИ

45, а, следовательно, на 2-m выходах блока 5 имеет место нулевой потенциал, а на первом выходе блока 5 единичный потенциал. При нулевом выходе верхней ячейки 4 первого столбца при наличии столбцов с единичным выходом на верхней ячейке 4 и нуле вым выходом в диагональной ячейке 4

I единичные потенциалы формируются на выходах тех элементов И 38, входы которых соединены с выходами данных столбцов, при этом с помощью инверторов 39 и элементов И 40 формируется единичный потенциал только на выходе того элемента И 40, вход которого через элемент И 38. соединен с единичным выходом верхней ячейки 4 и нулевым выходом диагональной ячейки и крайнего левого столбца, т.е. с помощью инверторов 39 и элементов И

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

И 40 и соответствует номеру крайнего левого столбца, который необходимо переставить с первым столбцом. При отсутствии столбца с единичным потенциалом на выходе верхней ячейки 4 памяти и с нулевым потенциалом на выходе диагональной ячейки 4 осуществляется выбор столбца крайнего левого столбца с единичными выходами верхней и диагональной ячеек 4 памяти, при этом на выходе элемента ИЛИ-НЕ 43 имеет место единичный потенциал, а с помощью инверторов 41 и элементов

И 42 осуществляется формирование единичного потенциала только на выходе того элемента И 42, который непосредственно соединен с крайним левым

-столбцом (единичный выход верхней ячейки 4 памяти). Данный единичный потенциал передается через элементы

И 44, ИЛИ 45 и 46 на первый выход блока 5 и на тот выход, номер которого соответствует крайнему левому столбцу. Таким образом, во времялействия импульсов на выходе 27 блока

9 управления единичный сигнал имеет место только на выходах блока 7 (на входах 22), номер которых соответст14 6

В результате приведения матрицы

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

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

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

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

m-кратного выполнения базисных операций, т.е. за 2-m временных цикла.

5 12887 вует первому и выбранному крайнему левому столбцам. C приходом импульса на вход 24 записи в ячейки 4 памяти: первого столбца матрицы 2 и первой ячейки памяти в блоке 3 памяти по входу 19 осуществляется построчная запись информации из ячеек 4 памяти того столбца, который сбответствует выбранному крайнему левому столбцу, а в данный крайний .левый столбец про-10 изводится построчная перепись информации из первого столбца матрицы 2 и первой ячейки блока 3 памяти. В остальных ячейках 4 памяти матрицы 2 и блока 3 памяти информация остается без изменения. Если верхняя строка матрицы 2 является нулевой (при от-. сутствии крайнего левого столбца матрицы или первый столбец является крайним левым), в данном такте информация во всех ячейках 4 памяти остается без изменений. Во время действия первого единичного импульса на третьих управляющих входах 23 ячеек 4 памяти, на выходах 27 и на вторых управляющих входах 22 имеет место .нулевой потенциал, а блок 8 элементов И формирует единичный потенциал только на выходах, номера которых соответствуют номерам столбцов матрицы 2 (кроме первого), в которых в данный момент на выходах

26 верхних ячеек 4 памяти имеет место единичный потенциал. При этом в ячейках 4 памяти k-й строки 2-m 35 столбцов производится суммирование по модулю два содержимого элемента

15 памяти данной ячейки 4 памяти с выходным сигналом ячейки 4 памяти данной k-й строки первого столбца, 40 логически умноженным с сигналом на блокировочном входе 25 данной ячейки

4 памяти.

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

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

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

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

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

1 управляющих входа коммутатора соединены с управляющими входами ячейки памяти, второй информационный вход коммутатора соединен с вторым входом элемента И данной ячейки памяти, а выход сумматора по модулю два подключен к выходу ячейки памяти.

1288714

° ° °

2?

1288714

1288714 ! 2 3

4 4

/ //) /В 2)/

2 4 4

3)6

3 4 4 ! U)/ 4)/

4 4 4

/8 4) /В/ТУ/

/e И)/8 Б// б(4) 4

887а) /8 /77) /

/В 7/3 8)/

/e (тв)/а(тй/ /r)/ /z)

° ° ° ° ° ° ° ° ° Ф ° ° ° ° °

m-/Ц Ц Ц Д4 Д4

/8/Ь-/) /ЯИ)/@и+/) /ЙТа ЯВЬ+3)

/8 Ч/В) / /e re r ()///+Юа+2)(Та+Я)а+4)( (Tin /)(Tm+2)(Tm+3) (T///+4)(Tm+5)

5 т), т

Фиг.б

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

Редактор Н.Бобкова Техред Л.Олейник Корректор Л.Пилипенко

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

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

113035, Москва, Ж-35, Раушская наб., д. 4/5 . Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная, 4