Устройство для приведения матрицы к треугольной идемпотентной форме
Иллюстрации
Показать всеРеферат
Изобретение относится к области вычислительной техники и предназначено для решения систем линейных уравнений, определения коэффициентов линейного однородного разностного уравнения, определения кода М-последовательностей. Цель изобретения - повьшение быстродействия устройства.. 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