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

,С Об Г 15/347 ОПИСАНИЕ ИЗОБРЕТЕН Н АВТОРСНО ВИДЕТЕЛЬСТВ ГОдудАРственный нОмитет сссРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(56) 1, Авторское свидетельство СССР У 760107, кл. С Об Р 15/20, 19772. Авторское свидетельство СССР Р 748416, кл. С Об Р 15/20, 1978.3. Берлекэмп Э. Алгебраическая теория кодирования. М., "Мир", 1971, с. 65-67, рис. 2.23 (прототип), (54)(57) УСТРОЙСТВО ДЛЯ ВЫБОРА СТОЛБЦА ДВОИЧНОЙ МАТРИЦЫ РАЗМЕРОМ (ФФф), ПЕРЕСТАВЛЯЕМОГО С ПЕРВЫМ СТОЛБЦОМ, содержащее матрицу элементов памяти, первую группу элементов НЕ, первую группу элементов И, вторую группу элементов НЕ, тре-тью группу элементов НЕ, вторую группу элементов И, группу элементов ИЛИ, причем выходы элементов памяти главной диагонали матрицы, начиная со второго, соответственно соединены с входами элементов НЕ первой группы, выходы которых соединены с первыми входами соответствующих элементов И первой группы, вторые входы которых соответственно соединены с выходами элементов памяти первой строки матрицы, начиная со второго, выходы элементов И второй группы соединены с первыми входами соответствующих элементов ИЛИ группы, выходы которых являются выходами устройства, о т л ич а ю ш е е с я тем, что, с целью повышения быстродействия, устройст" во содержит третью и четвертую груп, ЯО 1115061 пы элементов И и элемент ИЛИ-НЕ,первый вход которого соединен с выходом первого элемента памяти первой строки матрицы, первым выходомустройства и входом первого элемента НЕ второй группы, остальныевходы элемента ИЛИ-НЕ подключенык выходам элементов И третьей группы, первые входы которых соединеныс выходами соответствующих элементов И первой группы, вход 1-го элементаНЕ второй группы (1 = 2,ш) соединен с выходом (1-1)-гоэлемента И первой группы, 1 -й входк-го элемента И третьей группыОс = 1, , тп; 1 = 2, , 1 с+1)соединен с выходом (1-1)-го элемента НЕ второй группы, выходы элементов И третьей группы подключены к вторым входам соответствующихэлементов ИЛИ группы, вход р-го элемента НЕ третьей группы подключенк выходу (р+1)-го элемента памятипервой строки матрицы (р = 1,ш-,2), первый вход Р -го элемента Ичетвертой группы соединен с выходом(р + 2)-го элемента памяти первойстроки матрицы, выход второго элемента памяти первой строки матрицыподключен к первому входу первогоэлемента И второй группы, с -й входр-го элемента И четвертой группы(С = 2, , р + 1) соединен с выходом (С - 1)-го элемента НЕ третьейгруппы, выход Р-го элемента И четвертой группы подключен к первомувходу (р + 1)-го элемента И второйгруппы, вторые входы элементов Ивторой группы подключены к выходуэлемента ИЛИ-НЕ.1115Изобретение относится к вычисли тельной технике и предназначено для выбора столбца двоичной матрицы размером (в щ), персставляемого с первым столбцом, при приведении двоичной матрицы к треугольной ицемпотентной форме.Известны устройства для перебора сочетаний и перестановок, предназначенные для обработки цифровой информации, содержащие логические элементы И, ИЛИ, ИХИ,", коммутирующие элементы П 3 и 12 .Однако с помощью данных устройств невозможно производить выбор столбца двоичной матрицы размером (щ щ), переставляемого с первым столбцом.Наиболее близким к изобретению по технической сущности является устройство для выбора столбца двоичной матрицы размером (в щ), переставляемого с первым столбцом, содержащее двоичную матрицу размером (щ щ), первую группу элементов НЕ, соединенных с выходами диагональных элементов памяти 2 - щ столбцов, первую группу элементов И, первые входы которых соединеиы с выходами первой группы элементов НЕ, вторые входы подключены к выходам элеменЗО тов памяти первых строк 2 - щ столбцов матрицы, вторую группу элементов НЕ, третью группу элементов НЕ, вторую группу элементов И, группу элементов ИЛИ, формирующее унитарный код, при этом номер выхода, на котором формируется логическая единица, соответствует номеру столбца двоичной матрицы размером (вх щ), переставляемого с первым столбцом (33.едостатком известного устройст ва является низкое быстродействие, обусловленное последовательным (от 1 до ю столбца) анализам для выбора первого столбца, в котором верхний элемент отличен от нуля, а 45 элемент главной диагонали равен нулю, а при отсутствии таких столбцов формированием управляющего сигнала, разрешающего последователь- . ный (от 1 до в столбца) анализ для выбора первого столбца, в котором верхний элемент памяти и элемент памяти главной диагонали отличны от нуля.Цель изобретения - повышение бы стродействия.Поставленная цель достигается тем, что в устройство для выбора 061 1столбца двоичной матрицы размером(в хщ), переставляемого с первымстолбцом, содержащее матрицу элементов памяти, первую группу элементов НЕ, первую группу элементов И, вторую группу элементов НЕ,третью группу элементов НЕ, вторуюгруппу элементов И, группу элементов ИЛИ, причем выходы элементовпамяти главной диагонали матрицы,начиная со второго, соответственно соединены с входами элементовНЕ первой группы, выходы которыхсоединены с первыми входами соответствующих элементов И первойгруппы, вторые входы которых соответственна соединены с выходамиэлементов памяти первой строки матрицы, начиная со второгО, выходыэлементов И второй группы соединены с первыми входами соответствующих элементов ИЛИ группы, выходыкоторых являются выходами устрой -ства, введены третья и четвертаягруппы элементов И и элемент ИЛИ-НЕ,первый вход которого соединен с выходом первого элемента памяти первой строки матрицы, первым выходомустройства и входом первого элемента НЕ второй группы, остальные входы элемента ИЛИ-НЕ подключены квыходам элементов И третьей группы,первые входы которых соединены с выходами соответствующих элементовИ первой группы, вход 1-го элемента НЕ второй группы ( = 2,щ) соединен с выходам ( - 1)-гаэлемента И первой группы, .-йвход -го элемента И третьей группы (с = 1, , в, Е.=2,1+1) соединен с выходом (6-1)-гаэлемента НЕ второй группы, выходыэлементов И третьей группы подключены к вторым входам соответствующих элементов ИЛИ группы, входР-го элемента НЕ третьей группыподключен к выходу (р + 1)-го элемента памяти первой строки матрицы(р = 1, , щ), первый входР-го элемента И четвертой группысоединен с выходом (р + 2)-га элемента памяти первой строки матрицы,выход второго элемента памяти первой строки матрицы подключен к первому. входу первого элемента И второй группы, о-й. вход р -го элемента И червертой группы ( = 2,р + 1) соединен с выходом (-1)-гоэлемента НЕ третьей группы, выход1115 Ю где Ыг заданы для всех г = (1-щ),45 в = (1-щ) в виде комбинаций логических нулей и единиц.При приведении матрицы 1 размером (шх щ) к треугольной идемпотент ной форме устройство определяет номер крайнего левого столбца матрицы, переставляемого с первым столбцом, путем выявления столбца, в котором элемент 2 памяти верхней строки 55 отличен от нуля, а элемент 2памяти главной диагонали равен нулю, а при отсутствии такого столбца определяет столбец, в котором Эр-го элемента И четвертой группы подключен к первому входу (р + 1)-го элемента И второй группы, вторые входы элементов И второй группы подключены к выходу элемента ИЛИ-НЕ.На чертеже изображена структур 5 ная схема предлагаемого устройства.Устройство содержит двоичную матрицу 1 размером (щ хщ), содержащую матрицу элементов 2 памяти, первую группу 3 элементов НЕ 4, первую группу 5 элементов И 6, вторую группу 7 элементов НЕ 8, третью группу 9 элементов И 10, элемент ИЛИНЕ 11, третью группу 12 элементов НЕ 3, четвертую группу 14 элемен 15 тов И 15, вторую группу 16 элементов И 17, группу 18 элементов ИЛИ 19, выходы 20 устройства.Выходы 2-2 щ диагональных эле 20 ментов памяти столбцов матрицы 1 через элементы НЕ 4 группы 3 подклю - чены к первым входам элементов И 6 группы 5, вторые входы 2-(щ) элементов И 6 объединены с входами 2-(щ) элементов НЕ 13 группы 12, с первыми входами 1-(щ) элементов И 15 группы 14 и соединены с выходами элементов 2 памяти первых строк 3-(щ) столбцов матрицы, второй вход (щ) элемента И 6 объединен30 с первым входом (щ) элемента И 15 группы 14 и соединен с выходом элемента 2 памяти первой строки первого столбца матрицы, а выход элемента 2 памяти первой строки второ- З 5 го столбца матрицы 1 элементов памяти подключен к второму входу первого элемента И Ь групп 5, к входу первого элемента НЕ 13 группы 12 и к первому входу элемента И 1740 группы 16Выход диагонального элемента 2 памяти первого столбца матрицы 1 соединен с входом первого элемента НЕ 8 группы 7, с первым входом элемента ИЛИ-НЕ 11 и с первым выходом 20 устройства, выходы 1-(щ - 2) элементов И 6 группы 5 соединены с входами 2-(щ) элементов НЕ.8 группы 7 и с первыми входами 1-(ш) элементов И 10 группы 9, выход(щ) элемента Й 6 группы 5 соединен с первым входом (щ) элемента И 10 группы 9, вторые входы элементов И 10 объединены и подключены к выходу первого элемента НЕ 8 группы 7, третьи входы 2-(щ) элементов И 10 группы 9 подключены к вы 061 4ходу второго элемента НЕ 8 группы 7., щ-й вход щэлемента И 10 группы 9 соединен с выходом (щ) элемента НЕ 8 группы 7, а выходы элементов И 10 группы 9 подключены к первым входам элементов ИЛИ 19 группы 18 и к 2-щ входам элемента ИЛИ 11. Вторые входы 1-(щ - 2) элементов И 15 группы 14 объединены и подключены к выходу первого элемента НЕ 13 группы 12, третьи входы 2-(щ) элементов И 15 группы 14 объединены и подключены к выходу второго элемента НЕ 13 группы 12, (т) вход (щ) элемента И 15 группы 14 соединен с выходом (щ) элемента НЕ 13 группы 12, выходы элементов И 15 группы 14 подключены к первым входам 2-(щ - 1) элементов И 17 группы 16, вторые входы 1-(щ) элементов И 17 группы 16 объединены и соединены с выходом элемента ИЛИ-НЕ 11, а выходы элементов И 17 группы 16 подключены к вторым входам элементов ИЛИ 19 группы 8, выходы которых являются 2-.щ выходами 20 устройства.Устройство для выбора столбца двоичной матрицы размером (щх щ), переставляемого с первым столбцом, работает следующим образом.В элементы 2 памяти двоичной матрицы 1 размером (щ хщ) записаны коэффициенты б. системы линейныхй 5уравнений г +о г с г о(. г =0 11 1 2 2 1 Ь 31 о д А г,+о г +о,г о г:о 21 1 22 2 23 5 " 2 в п5 1 элементы 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-(г) элементов И 6 группы 5 формируются логические нули, а на выходе гэлемента И 6 группы 5 формируется логическая единица, следовательно, только на выходе гэлемента И 10 группы 9 формируется логическая единица, так как входы 1-(г) элементов И 10 группы 9 заблокированы сигналами с выходов 1-(г) элементов И 6 группы 5, а входы 1-(г) элементов И 10 группы 9 заблокированы инверсным сигналом гэлемента И 6 группы 5.На гвходе элемента ИЛИ-НЕ 11 имеет место единичный потенциал, а на вторых входах элементов И 17 группы 16 имеет место нулевой по 115061 5 10 15 20 25 30 35 40 45 50 55 тенциал, блокирующий первые входы - элементов И 17 группы 16.Следовательно, сигнал логичес" кой единицы формируется только на выходе гэлемента ИЛИ 19 группы 18, т.е. на г выходе 20 устройства, соответствующем номеру г столбца матрицы 1, который необходимо переставить с первым столбцом.Если в матрице 1 отсутствует столбец, в котором элемент 2 памяти верхней строки равен единице, а диагональный элемент 2 памяти равен нулю, на выходах элементов И 6, 10 групп 5,9 имеет место нулевой потенциал, следовательно, на вторых входах элементов И 17 группы 16 имеет место единичный потенциал, и на выходы 20 поступает информация с выходов элементов И 15 группы 14, где осуществляется выбор крайнего левого столбца матрицы 1, в котором элементы верхней строки и диагонали равны единице. Если таким столбцом оказался ь-й столбец (х = 1-щ) матрицы 1, то потенциал логической единицы имеет место только на выходе -2 элемента И 15 группы 14, так как входы 1 в (1-3) элементов И 15 группы 14 заблокированы нулевыми сигналами верхних элементов памяти 3-(-1) столбцов матрицы 1, а входы (3.-1)-(тп) элементов И 15 группы 14 заблокированы инверсным сигналом элемента 2 памяти верхней строки -гостолбца матрицы. 1.Следовательно, сигнал логической единицы имеет место только на выходе -1 элемента И 17 группы 18, первый вход которого соединен с выходом -2 элемента И 15 группы 14, и сигнал логической единицы формируется только на х-м выходе 20 устройства, соответствующем номеру 1-го столбца матрицы 1, который необходимо переставить с первым столбцом.Если на всех элементах 2 памяти верхних строк имеет место логический нуль, на всех выходах 20 имеет место нулевой потенциал, т.е. в матрице 1 нет столбца, который необходимо переставить с первым столбцом.Таким образом, введение в известное устройство для выбора столбца двоичной матрицы размером (ваяв),.переставляемого с первым столбцом, -1 третьей группы 9 элементов И 1 О,четвертой группы 14 элементов И 15и элемента ИЛИ-НЕ 11 позволяет осуществлять одновременный анализ крайнего левого столбца, в которомэлемент верхней строки равен единице, а элемент диагонали равен нулю, и анализ крайнего левого столбца, в котором элементы памятиверхней строки и диагонали отличны от нуля, и производить приоритетное подключение к выходам устройства выходов группы 9 элементов И 10,с помощью которого осуществляетсяанализ столбцов с единичным верхним и нулевым диагональным элементомпамяти. Использование изобретения в устройстве для решения систем Р 1 линейных алгебраических уравнений с пнеизвестными (для приведения двоичной матрицы размером (шш) к треугольной идемпотентной форме), в 1 О котором операция выбора крайнеголевого столбца производится ю раз,позволяет повысить быстродействиеустройства для решения систем уравнений в 2раз и значительно улуч шить основной параметр устройства -время обработки информации.11150 Ь 1 Составитель А. ЧудовРедактор А. Шишкина ТехредЖ.Кастелевич Корректор В. Гирняк исн 4/5 Филиал ППП "Патент", г. Ужгород, улПроектная,каз 6772/3 ВНИИП по 113035, Тираж б 98 П осударственного комитета СС елам изобретений и открытий ква, Ж, Раушская наб., д