Устройство для выбора столбца двоичной матрицы размером ( @ ), переставляемого с первым столбцом

 

УСТРОЙСТВО ДЛЯ ВЫБОРА СТОЛБЦА ДВОИЧНОЙ МАТРИЦЫ РАЗМЕРОМ (тут), ПЕРЕСТАВЛЯЕМОГО С ПЕРВЫМ СТОЛБЦОМ, содержащее матрицу элементов памяти, первую группу элементов НЕ, первую группу элементов И, вторую группу элементов НЕ, третью группу элементов НЕ, вторую группу элементов И, группу элементов ИЛИ, причем выходы элементов памяти главной диагонали матрицы, начиная со второго, соответственно соединены с входами элементов НЕ первой группы, выходы которых соединены с первыми входами соответствующих элементов И первой группы, вторые входы которых соответственно соединены с выходами элементов памяти первой строки матрицы, начиная со второго, выходы элементов И второй группы соединены с первыми входами соответствующих элементов ИЛИ группы, выходы которых являются выходами устройства, отличающееся тем, что, с целью повышения быстродействия, устройство содержит третью и четвертую груп; пы элементов И и элемент ИЛИ-НЕ, первый вход которого сьединен с выходом первого элемента памяти первой строки матрицы, первым выходом устройства и входом первого элемента НЕ второй группы, остальные входы элемента ИЛИ-НЕ подключены к выходам элементов И третьей группы , первые входы которых соединены с выходами соответствующих элементов И первой группы, вход т-го элемента НЕ второй группы (i 2, ..., m-1) соединен с выходом (j-l)-ro элемента И первой группы, В-и вход k-ro элемента И третьей группы (k 1, ..., m-r, I 2, .., k+1) соединен с выходом

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

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

РЕСПУБЛИН

„„SU„„1115061

З(5 ) С 06 Г 15/347

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3510534/24-24 (22) 10. 11.82 (46) 23.09.84. Бюл. и 35 .(72) В.А. Алеев, Ю.M. Кондратьев, Ю.Г. Савкин и А.А. Чудов (53) 681.3(088.8) (56) 1. Авторское свидетельство СССР

У 760107, кл. С Об F 15/20, 1977 °

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

Р 748416, кл. G Об F 15/20, 1978.

3. Берлекэмп Э. Алгебраическая теория кодирования. M. "Мир", 1971, с. 65-67, рис. 2.23 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ВЫБОРА

СТОЛБЦА ДВОИЧНОЙ МАТРИЦЫ PA3MEPOI ("), ПЕРЕСТАВЛЯЕМОГО С ПЕРВЫМ

СТОЛБЦОМ, содержащее матрицу элементов памяти, первую группу элементов НЕ, первую группу элементов

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

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

k-го элемента И третьей группы (k = 1, ..., m-1; I = 2, ..., k+1) соединен с выходом (I — 1)-го элемента НЕ второй группы, выходы элементов И третьей группы подключены к вторым входам соответствующих элементов ИЛИ группы, вход р-го элемента НЕ третьей группы подключен к выходу (р+1)-го элемента памяти первой строки матрицы (р = 1, m-.2), первый вход P --го элемента И четвертой группы соединен с выходом (р + 2)-го элемента памяти первой строки матрицы, выход второго элемента памяти первой строки матрицы подключен к первому входу первого элемента И второй группы, с -й вход р-го элемента И четвертой группы (Q = 2, ..., р + 1) соединен с выхо дом (С вЂ” 1)-го элемента НЕ третьей группы, выход Р-го элемента И четвертой группы подключен к первому входу (р + 1)-ro элемента И второй группы, вторые входы элементов И второй группы подключены к выходу элемента ИЛИ-HE.

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

Известны устройства для перебора сочетаний и перестановок, предназначенные для обработки цифровой информации, содержащие логические элементы И, ИЛИ, ИЛИ-НЕ, коммутирующие элементы L13 и L2).

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

Наиболее близким к изобретению по технической сущности является устройство для выбора столбца двоичной матрицы размером (m x m), переставляемого с первым столбцом, содержащее двоичную матрицу. размером (m x m), первую группу элементов НЕ, соединенных с выходами диагональных элементов памяти 2 — m столбцов, первую группу элементов И, первые входы которых соединеиы с выходами первой группы элементов НЕ, вторые входы подключены к выходам элемен30 тов памяти первых строк 2 — m столбцов матрицы, вторую группу элементов

НЕ, третью группу элементов НЕ, вторую группу элементов И, группу элементов ИЛИ, формирующее унитарный код, при этом номер выхода, на котором формируется логическая единица, соответствует номеру столбца двоичной матрицы размером (mx m), переставляемого с первым столбцом (3)

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

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

Поставленная цель достигается тем, что в устройство для выбора

061 2 столбца двоичной матрицы размером (m х m), переставляемого с первым столбцом, содержащее матрицу элементов памяти, первую группу элементов НЕ, первую группу элементов И, вторую группу элементов НЕ, третью группу элементов НЕ, вторую группу элементов И, группу элементов ИЛИ, причем выходы элементов памяти главной диагонали матрицы, начиная со второго, соответственно соединены с входами элементов

НЕ первой группы, выходы которых соединены с первыми входами соответствующих элементов И первой группы, вторые входы которых соответственна соединены с выходами элементов памяти первой строки матрицы, начиная со второгО, выходы элементов И второй группы соединены с первыми входами соответствующих элементов ИЛИ группы, выходы которых являются выходами устрой— ства, введены третья и четвертая группы элементов И и элемент ИЛИ-НЕ, первый вход которого соединен с выходом первого элемента памяти первой строки матрицы, первым выходом устройства и входом первого элемента НЕ второй группы, остальные входы элемента ИЛИ-НЕ подключены к выходам элементов И третьей группы, первые входы которых соединены с выходами соответствующих элементов

И первой группы, вход I — га элемента НЕ второй группы (j = 2, m- 1) соединен с выходам (j — 1)-га элемента И первой группы, -й вход k-ro элемента И третьей группы (k = 1, ..., m-1, Е.=2, k+1) соединен с выходом (С-1)-га элемента НЕ второй группы, выходы элементов И третьей группы подключены к вторым входам соответствующих элементов ИЛИ группы, вход

P-го элемента НЕ третьей группы подключен к выходу (р + 1)-го элемента памяти первой строки матрицы (р = 1, ..., m-2), первый вход

Р-го элемента И четвертой группы соединен с выходом (р + 2)-га элемента памяти первой строки матрицы, выход второго элемента памяти первой строки матрицы подключен к первому. входу первого элемента И второй группы, q-й вход р -ro элемента И червертой группы (g = 2, р + 1) соединен с BbIxopoM (q-1)-ro элемента НЕ третьей группы, выход

1115

Ю где Ыгз заданы для всех r = (1-m), I

45 s = (1-т) в виде комбинаций логических нулей и единиц.

При приведении матрицы 1 размером (mx m) к треугольной идемпотент50 ной форме устройство определяет номер крайнего левого столбца матрицы, переставляемого с первым столбцом, путем выявления столбца, в котором элемент 2 памяти верхней строки

55 отличен от нуля, а элемент 2 памяти главной диагонали равен нулю, а при отсутствии такого столбца определяет столбец, в котором

3 р-го элемента И четвертой группы подключен к первому входу (р + 1)-го элемента И второй группы, вторые входы элементов И второй группы подключены к выходу элемента ИЛИ-НЕ.

На чертеже изображена структур5 ная схема предлагаемого устройства.

Устройство содержит двоичную матрицу 1 размером (m y. m), содержащую матрицу элементов 2 памяти, первую группу 3 элементов HE 4, первую группу 5 элементов И 6, вторую группу 7 элементов НЕ 8, третью группу 9 элементов И 10, элемент ИЛИНЕ 11, третью группу 12 элементов

НЕ !3, четвертую группу 14 элемен15 тов И 15, вторую группу 16 элементов И 17, группу 18 элементов ИЛИ 19, выходы 20 устройства.

Выходы 2-2 m диагональных эле20 ментов памяти столбцов матрицы 1 че рез элементы НЕ 4 группы 3 подклю— чены к первым входам элементов И 6 группы 5, вторые входы 2 †(m — 2) элементов И 6 объединены с входами

2-(m-2) элементов НЕ 13 группы 12, с первыми входами 1 †(m-3) элементов

И 15 группы 14 и соединены с выходами элементов 2 памяти первых строк

3-(m-1) столбцов матрицы, второй вход (m-1) элемента И 6 объединен

30 с первым входом (m-2) элемента И 15 группы 14 и соединен с выходом элемента 2 памяти первой строки первого столбца матрицы, а выход элемента 2 памяти первой строки второ- З5

ro столбца матрицы 1 элементов памяти подключен к второму входу первого элемента И Ь групп 5, к входу первого элемента НЕ 13 группы 12 и к первому входу элемента И 17

40 группы 16 °

Выход диагонального элемента 2 памяти первого столбца матрицы 1 соединен с входом первого элемента

НЕ 8 группы 7, с первым входом элемента ИЛИ-НЕ 11 и с первым выхо- . дом 20 устройства, выходы 1-(m — 2) элементов И 6 группы 5 соединены с входами 2-(m-1) элементов НЕ.8 группы 7 и с первыми входами 1-(m-2) элементов И 10 группы 9, выход (тп-1) элемента Й 6 группы 5 соединен с первым входом (m-1) элемента

И 10 группы 9, вторые входы элементов И 10 объединены и подключены к выходу первого элемента НЕ 8 группы 7, третьи входы 2-(m-2) элементов И 10 группы 9 подключены к вы061 4 ходу второго элемента HE 8 группы

7, m-й вход m-1 элемента И 10 группы 9 соединен с выходом (m-1) элемента НЕ 8 группы 7, а выходы элементов И 10 группы 9 подключены к первым входам элементов ИЛИ 19 группы 18 и к 2-m входам элемента

ИЛИ 11. Вторые входы 1-(m — 2) элементов И 15 группы 14 объединены и подключены к выходу первого элемента HE 13 группы 12, третьи входы 2-(m-2) элементов И 15 группы

14 объединены и подключены к выходу второго элемента НЕ 13 группы ! 12, (m-1) вход (ю-2) элемента И 15 группы 14 соединен с выходом (m — 2) элемента НЕ 13 группы 12, выходы элементов И 15 группы 14 подключены к первым входам 2-(m — 1) элементов И 17 группы 16, вторые входы 1 †(m- 1) элементов И 17 группы 16 объединены и соединены с выходом элемента ИЛИ-НЕ 11, а выходы элементов И 17 группы 16 подключены к вторым входам элементов ИЛИ !9 группы 18, выходы которых являются

2-.к выходами 20 устройства.

Устройство для выбора столбца двоичной матрицы размером (тпх щ), переставляемого с первым столбцом, работает следующим образом.

В элементы 2 памяти двоичной матрицы 1 размером (m х m) записаны коэффициенты д. системы линейных и 5 уравнений с/. +ц, 2 Фс Z +..-+k 2 =0 и 1 gg 2 1Ь 3 " 1п

А Ч.+aL 2 +о „Z +...+о Z =0

2 i 22 2 25 ь " 2в л

311 32 2 Ззз Зл rn а „я„ +, п, Z2 2з, +, „,, =0

5 11 элементы 2 памяти верхней строки и диагонали отличны от нуля.

Если элемент 2 памяти главной диагонали первого столбца матриць1 отличен от нуля, то сигнал логической единицы формируется на первом выходе 20, при этом на всех остальных выходах 20 имеют место логические нули, так как на вторых входах элементов И 10 группы 9 и на вторых входах элементов И 17 группы 16 имеет место нулевой потенциал. Если элемент 2 памяти главной диагонали первого столбца матрицы

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

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

С помощью элементов И 10 группы

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

При этом, если таким столбцом оказался r столбец матрицы,,то на выходах 1 †(r-2) элементов И 6 группы

5 формируются логические нули, а на выходе r-1 элемента И 6 группы

5 формируется логическая единица, следовательно, только на выходе

r-1 элемента И 10 группы 9 формируется логическая единица, так как входы 1-(r-2) элементов И 10 группы

9 заблокированы сигналами с выходов 1-(r -2) элементов И 6 группы 5, а входы 1 †(r-1) элементов И 10 группы 9 заблокированы инверсным сигналом r-1 элемента И 6 группы 5.

На r-1 входе элемента ИЛИ-НЕ 11 имеет место единичный потенциал, а на вторых входах элементов И 17 группы 16 имеет место нулевой по15061

t0

55 тенциал, блокирующий первые входыэлементов И 17 группы 16.

Следовательно, сигнал логичес" кой единицы формируется только на выходе г- t элемента ИЛИ 19 группы 18, т.е. íà r выходе 20 устройства, соответствующем номеру r столбца матрицы 1, который необходимо переставить с первым столбцом.

Если в матрице 1 отсутствует столбец, в котором элемент 2 памяти верхней строки равен единице, а диагональный элемент 2 памяти равен нулю, на выходах элементов

И 6, 10 групп 5,9 имеет место нулевой потенциал, следовательно, на вторых входах элементов И l7 группы 16 имеет место единичный потенциал, и на выходы 20 поступает информация с выходов элементов И 15 группы 14, где осуществляется выбор крайнего левого столбца матрицы 1, в котором элементы верхней строки и диагонали равны единице. Если таким столбцом оказался i-й столбец (i = 1-m) матрицы 1, то. потенциал логической единицы имеет место только на выходе i-2 элемента И 15 группы 14, так как входы 1 †(i-3) элементов И t5 группы 14 заблокированы нулевыми сигналами верхних элементов памяти 3-(i-1) столбцов матрицы 1, а входы (i-1)-(m-2) элементов И 15 группы 14 заблокированы инверсным сигналом элемента 2 памяти верхней строки i-го столбца матрицы. 1.

Следовательно, сигнал логической единицы имеет место только на выходе i-1 элемента И 17 группы 18, первый вход которого соединен с выходом i-2 элемента И 15 группы

14, и сигнал логической единицы формируется только на i-м выходе

20 устройства, соответствующем номеру i-ro столбца матрицы i, который необходимо переставить с первым столбцом.

Если на всех элементах 2 памяти верхних строк имеет место логический нуль, на всех выходах 20 имеет место нулевой потенциал. т.е. в матрице 1 нет столбца, который необходимо переставить с первым столбцом.

Таким образом, введение в известное устройство для выбора столбца двоичной матрицы размером (mxm), 1115061 переставляемого с первым столбцом,— третьей группы 9 элементов И 1О, четвертой группы 14 элементов И 15 и элемента ИЛИ-НЕ 11 позволяет осуществлять одновременный анализ крайнего левого столбца, в котором элемент верхней строки равен единице, а элемент диагонали равен нулю, и анализ крайнего левого столбца, в котором элементы памяти верхней строки и диагонали отличны от нуля, и производить приоритетное подключение к выходам устройства выходов группы 9 элементов И 10, с помощью которого осуществляется анализ столбцов с единичным верхним и нулевым диагональным элементом памяти.

Использование изобретения в устройстве для решения систем илинейных алгебраических уравнений с п неизвестными (для приведения двоичной матрицы размером (m w m) к треугольной идемпотентной форме), в

10 котором операция выбора крайнего левого столбца производится vn paw, позволяет повысить быстродействие устройства для решения систем уравнений в 2 раз и значительно улуч15 шить основной параметр устройства— время обработки информации.

1115061

Составитель А. Чудов

Редактор А. Шишкина Техред Ж. Кастелевич Корректор В. Гирняк

Заказ 6772/36 Тираж 698 Подписное

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

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