Устройство для выбора столбца двоичной матрицы размером ( @ ), переставляемого с первым столбцом Советский патент 1984 года по МПК G06F17/16 

f

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

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

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

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

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

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

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

150612

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

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

5 группы элементов И и элемент ИЛИ-НЕ, первый вход которого соединен с выходом первого элемента памяти первой строки матрицы, первым выходом устройства и входом первого элемента НЕ второй группы, остальные входы элемента ИЛИ-НЁ подключены к выходам элементов И третьей группы, первые входы которых соединены с выходами соответствующих элементов И первой группы, вход 1-го элемента НЕ второй группы (J 2, ..., т-1) соединен с выходом (j-l)-ro элемента И первой группы, и-и вход k-ro элемента И третьей группы (k 1, ..., m-1, 2, . , ., k+1) соединен с выходом (.-1)-го элемента НЕ второй группы, выходы элементов И третьей группы подключены к вторым входам соответствующих элементов ИЛИ группы, вход Р-го элемента НЕ третьей группы подключен к выходу (р + 1)-го элемента памяти первой строки матрицы (р 1, ..., ш-2), первый вход р-Го элемента И четвертой группы

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

3

р-го элемента И четвертой группы

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

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

Устройство содержит двоичную матрицу 1 размером (т т), содержащую матрицу элементов 2 памяти, первую группу 3 элементов НЕ 4, первую группу 5 элементов И 6, вторую группу 7 элементов НЕ 8, третью группу 9 элементов И 10, элемент ИЛИНЕ 1 1 , третью группу 12 элементов НЕ 13, четвертую группу 14 элементов И 15, вторую группу 16 элементов И 17, группу 18 элементов ИЛИ 19 выходы 20 устройства.

Выходы 2-2 m диагональных элементов памяти столбцов матрицы 1 через элементы НЕ 4 группы 3 подключены к первым входам элементов И 6 группы 5, вторые входы 2-(т-2) элементов И 6 объединены с входами 2-(п1-2) элементов НЕ 13 группы 12, с первыми входами 1-(т-3) элементов И 15 группы 14 и соединены с выходами элементов 2 памяти первых строк 3-(т-1) столбцов матрицы, второй вход (т-1) элемента И 6 объединен с первым входом, (т-2) элемента И 15 группы 14 и соединён с выходом элемента 2 памяти первой строки первого столбца матрицы, а выход элемента 2 памяти первой строки второго столбца матрицы 1 элементов памяти подключен к второму входу первого элемента И 6 группу 5, к входу первого элемента НЕ 13 группы 12 и к первому входу элемента И 17 группы 16.

Выход диагонального элемента 2 памяти первого столбца матрицы 1 соединен с входом первого элемента НЕ 8 группы 7, с первым входом элемента ИЛИ-НЕ 11 и с первым выхо- дом 20 устройства, выходы )-(т-2) элементов И 6 группы 5 соединены с входами 2-(т-1) элементов НЕ.8 группы 7 и с первыми входами 1-(т-2) элементов И 10 группы 9, выход (т-1) элемента И 6 группы 5 соединен с первым входом (т-1) элемента И 10 группы 9, вторые входы элементов И 10 объединены и подключены к выходу первого элемента НЕ 8 группы 7, третьи входы 2-(т-2) элементов И 10 группы 9 подключены к вы1506.1 . . -4

ходу второго элемента НЕ 8 группы 7., т-й вход т-1 элемента И 10 группы 9 соединен с вьгходсм (т-1) элемента НЕ 8 группы 7, а выходы элементов И 10 группы 9 подключены к первым входам элементов ИЛИ 19 группы 18 и к 2-т входам элемента ШШ 11. Вторые входы 1-(т-2) элементов И 15 группы 14 объединены и подключены к выходу первого элемента НЕ 13 группы 12, третьи входы 2-(т-2) элементов И 15 группы 14 объединены и подключены к выходу второго элемента НЕ 13 группы 12, (т-1) вход (т-2) элемента И 15 грзшпы 14 соединен с выходом (т-2) элемента НЕ 13 группы 12, выходы элементов И 15 группы .14 подключены к первым входам 2-(т-1) элементов И 17 группы 16, вторые входы 1-(т-1) элементов И 17 группы 1 6 объединены и соединены с выходом элемента ИЖ-НЕ 11, а выходы элементов И 17 группы 16 подключены к вторым входам элементов ИЛИ 19 группы 18, выходы которых являются 2-т выходами 20 устройства.

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

В элементы 2 памяти двоичной матрицы 1 размером () записаны коэффициенты ciL системы линейных уравнений

, + oC 24 c6ijZ3 + ...,z 0

..° .°

,-..т,

где ot-f g заданы для всех г (1-т), S (1-т) в виде комбинаций логических нулей и единиц.

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

отличен от нуля, а элемент 2

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

5

элементы 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 памяти диагонали равен нулю При этом, если таким столбцом оказался г столбец матрицы, то на выходах 1-(г-2) элементов И 6 группы 5 формируются логические нули, а на выходе г-1 элемента И 6 группы 5 формируется логическая единицу, следовательно, только на выходе г-1 элемента И 10 группы 9формируется логическая единица, так как входы 1-(г-2) элементов И 10 группы 9 заблокированы сигналами с выходов 1-(г-2) элементов И 6 группы 5 а входы 1-(г-1) элементов И 10 группы 9 заблокированы инверсным сигналом г-1 элемента И 6 группы 5.

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

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

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

5 выходе г-1 элемента ИЛИ 19 группы 18, т-.е. на г выходе 20 устройства, соответствующем номеру г столбца матрицы 1, который необходимо переставить с первым столб10 цом.

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

15 равен нулю, на выходах элементов И 6, 10 групп 5,9 имеет место нулевой потенциал, следовательно, на вторых вхрдах элементов И 17 группы 16 имеет место единичный потен20 циал, и на выходы 20 поступает

информация с выходов элементов И 15 группы 14, где осуществляется выбор крайнего левого столбца матрицы 1, в котором элементы верхней строки

5 ,и диагонали равны единице. Если таким столбцом оказался i-й столбец (i 1-m) матрицы 1, то потенциал логической единицы имеет место только на выходе i-2 элемента И 15

0 группы 14, так как входы 1-(i-3) элементов И 15 группы 14 заблокированы нулевыми сигналами верхних элементов памяти 3-(i-1) столбцов матрицы 1, а входы (i-1)-(m-2) элементов И 15 группы 14 заблокированы инверсным сигналом элемента 2 памяти верхней строки i-roстолбца матрицы. 1.

Следовательно, сигнал логической единицы имеет место только на

выходе i-1 элемента И 17 группы 18, первый вход которого соединен с выходом i-2 элемента И 15 группы 14, и сигнал логической единицы формируется только на i-м выходе 20 устройства, соответствующем номеру i-ro столбца матрицы 1, который необходимо переставить с первым столбцом.

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

Таким образом, введение в известное устройство для выбора столбца двоичной матрицы размером (mxm),

переставляемого с первым столбцом, I третьей группы 9 элементов И 10, четвертой группы 14 элементов И 15 и элемента ИЛИ-НЕ 11 позволяет осуществлять одновременный анализ крайнего левого столбца, в котором элемент верхней строки равен единице, а элемент диагонали равен нулю, и анализ крайнего левого столбца, в которомэлементы памяти верхней строки и диагонали отличны от нуля, и производить приоритетное подключение к выходам устройства выходов группы 9 элементов И 10 с помощью которого осуществляется анализ столбцов с единичным верхним

и нулевым диагональным элементом памяти.

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

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