Коммутатор

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 1) 4 0 06 Р 7/О ПИСАНИЕ ИЗОБРЕТЕНИА ВТОРСКОМУ СВИДЕТЕЛЬСТВУ(46) 30,05.87. Бюл, 91) Ленинградский элкий институт им. ВИ(54) КОММУТАТОР льство СССР 7/00, 19837) Изобретение отн числительной техни сится к цифров е, предназначе аботки массиво я логическ ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ информации и является усовершенствованием изобретения по а.с. У 1120313Цель изобретения - расширение функциональных возможностей коммутатораза счет выполнения операции формирования единичного вектора. Коммутаторсодержит две треугольные матрицы 2,3, группу элементов ИЛИ 4, группуэлементов НЕ 5, ячейки 6 со входами 7, 9, 11, 13, 15 и выходами 8,10, 12, 14, 16. Ячейка коммутаторасодержит элементы НЕ, элементы И,элементы ИЛИ, Коммутатор работаетв режимах сжатия, расширения, сплетения, перегруппировки и формирования единичного вектора, 2 ил,1 134332 2Изобретение относится к цифровойвычислительной технике и предназначено для логической обработки массивов информации,Целью изобретения является расширение функциональных возможностейза счет выполнения операции формирования единичного вектора,Длина сформированного единичноговектора может служить оценкой связ- Оности,Операция вычисления связности между элементами является одной из основных при решении задач проектирования (компоновка элементов, размешение элементов, трассировка связей),программирования (выделение областейпамяти ЭВМ в зависимости от связности данных), а также при решении задач на графах (поиск максимальносвязанных подмножеств, разбиение наподграфы, вычисление характеристиксвязности граФа) и др.На фиг, 1 приведена схема предлагаемого коммутатора; на фиг. 2 - схема ячейки,55 Коммутатор 1 (фиг. 1) содержит треугольные матрицы 2 и 3, группу элементов ИЛИ 4, группу элементов НЕ 5, ячейки 6 с вторым горизонтальным входом 7 и выходом 8, первым горизонтальным входом 9 и выходом 10, третьим горизонтальным входом 11 и выходом 12, первым вертикальным входом 13 и выходом 14, вторым вертикальным входом 15 и выходом 16, выхо 17 коммутатора, причем в первой треугольной матрице 2, первый 13 и второй 15 вертикальные входы ячейки 6 с координатами И, ) соединены соответственно с первым 14 и вторым 16 вертикальными выходами ячейки с коор динатами (-1, ), второй 7, первый 9 горизонтальные входы ячейки с координатами (, 3) соединены соответственно с вторым 8, первым 1 О гори - зонтальными входами ячейки с координатами (.,- 1), Во второй треугольной матрице 3, первый 16 и второй 17 вертикальные входы ячейки 6 с координатами (1 с, 1) соединены соответственна с первым 15 и вторым 13 вертикальными выходами ячейки 6 с координатами (1 с, 1), второй 7, первый 9 горизонтальные входы ячейки с координатами (1 с, .) соединены соответственно с вторым 8, первым 10 горизонтальными вхо; ими ячейки с коор 5 20 25 30 35 40 45 50 динатами (К, 1-1), (К, 1 =Н 3- 1-1.; 1 = 1-К), причем третий горизонтальный вход 11 каждой ячейки 6соединен с вторым входом второго элемента И 2 данной ячейки 6 и ее третьим 12 горизонтальным выходом. Третий 11 горизонтальный выход ячейки 6с координатами (., ) в первой треугольной матрице 2 соединен с третьимгоризонтальным выходом 2 ячейки 6с координатами (д, 3-1), третий горизонтальный вход 11 ячейки 6 с координатами (К, 1) во второй треугольнойматрице 3 соединен с третьим горизонтальным выходом 12 ячейки 6 с координатами (К, 1-1), второй 8 горизонтальный выход последней ячейки д-йстроки первой треугольной матрицы 2соединен с вторым горизонтальнымвходом 7 первой ячейки (И-К)-йстроки второй треугольной матрицы 3,третий горизонтальный выход 12 последней ячейки -й строки первой треугольной матрицы 2 соединен с тре"тьим горизонтальным входом 9 первойячейки (И-К)-й строки второй треугольной матрицы 3, третий горизонтальный выход последней ячейки последней строки первой треугольной матрицы 2 соединен с третьим горизонтальным входом 11 первой ячейки последней строки второй треугольнойматрицы 3, второй вертикальный выход 16 3-й ячейки последней строкипервой треугольной матрицы 2 и второй вертикальный выход 16 (М+1)-йячейки последней строки второй треугольной матрицы 3 подключены соответственно к первому и второму входам1-го элемента группы ИЛИ 4, выходкоторого является выходом 17 коммутатора, первый горизонтальный вход 9первой ячейки 1-й строки второй треугольной матрицы 3 подключен к выходу 1-го элемента группы НЕ 5, входкоторого соединен с первым горизонтальным входом 9 первой ячейки (М-К+1)-й строки первой треугольной матрицы 2,Ячейка коммутатора (фиг. 2) содержит элементы НЕ 18 и 19, элементыИ 20-22, элементы ИЛИ 23 и 24, элемент И 25,Коммутатор работает следующим образом.Режим сжатия, Сжатием произвольного вектора Г называется операция х -к/1, где я - управляющий логичес 1314332кий (двоичный) вектор, размерностькоторого совпадает с размерностьювектора й, Результат операции - вектор х, который содержит те компоненты Г; исходного вектора, которые соответствуют г, = 1, Размерность вектора х совпадает с количеством единиц вектора к,В треугольной матрице 2 на входы13 и 15 ячеек 6 с координатами (1, 10(К = 1) треугольной матрицы 3 подаются константы "О", На входы 11 яче - 15ек 6 крайнего левого столбца треугольной матрицы 2 подаются константы "1", на горизонтальные входы 9ячеек 6 крайнего левого столбца треугольной матрицы 2 - логические уровни, соответствующие коду управляющего логического вектора г, Входнымиканалами коммутатора 1 при выполнении операции сжатия являются горизонтальные входы 7 ячеек 6 крайнего 25левого столбца треугольной матрицы 2 а выходными каналами - вертикальные выходы 16 ячеек 6 последнейстроки треугольной матрицы 2,30В крайнем левом столбце ячеек 6 треугольной матрицы 2 нулевой логический уровень образует на вертикальном выходе 14 ячейки 6, на горизонтальный вход 9 которой подан логический уровень, Начиная с указанной ячейки, нулевой логический уровень образуется на вертикальных выходах 14 всех расположенных ниже ячеек 6 рассматриваемого столбца, Таким образом, только в единственной ячейке 6 крайнео левого столбца треугольной матрицы 2 имеет место одновременное наличие единичных логических уровней на входах 13 и 9, в ре зультате чего именно в этой ячейке осуществляется подключение горизонтального входа 7 к вертикальному выходу 16, т,е, реализуется соединительная функция "Разветвление вниз , Следовательно, на выход 16 последней ячейки 6 крайнего левого столбца треугольной матрицы 2 направляются сигналы того горизонтального входного канала 7, которому соответствует первая сверху единица управляющего логического вектора г. На горизонтальном выходе 10 ячейки 6, в которой произошло разветвление, образуется нулевой логический уровень, В результате на горизонтальные входы 9 ячеек 6 смежного правого столбца треугольной матрицы 2 подается копия исходного управляющего логического вектора за исключением его первой единицы. Соединение последующих входных каналов 7 коммутатора 1 с выходными каналами 16 в треугольной матрице 2 осуществляется аналогичноТаким образом, на выходы 16 нижней границы треугольной матрицы 2 в первом, втором и так далее столбцах направляются сигналы тех входных каналов 7, которым соответствует первая, вторая и так далее единицы исходного кода управляющего логического вектора г, что соответствует операции сжатияОчевидно, что треугольная матрица 3 коммутатора 1 не принимает участия в выполнении операции сжатия,Режим формирования единичного вектора, Формированием единичного вектора называется операция х -к/Е,где к - управляющий логический вектор, размерность которого совпадает с размерностью вектора Г, Результат операция - вектор х, который содержит только единичные компоненты й; исходного вектора, которые соответствуют поразрядно г, = 1, Размерность вектора х равна количеству единиц в результирующем векторе приоперации пересечения векторов Й и япоразрядно,В треугольной матрице 2 на входы13 и 15 ячеек 6 с координатами (.,) (1=3) подаются соответственноконстанты "1" и "О", а на входы 13и 15 ячеек 6 с координатами (К, 1) (К=1) треугольной матрицы 3 подаются константы "О" На входы 11 ячеек 6 крайнего левого столбца треугольной матрицы 2 подаются константы 11 иО , на горизонтальные входы 9 ячеек 6 крайнего левого столбца треугольной матрицы 2 - логические уровни, соответствуюшие коду управляющего логического вектора к, Входными каналами коммутатора 1 при выполнении операции формирования единичного вектора являются горизонтальные входы 7 ячеек 6 крайнего левого столбца треугольной матрицы 2, а выходными каналами - вертикальные выходы 6 ячеек 6 последней строкитреугольной матрицы 2,314332 гично,40 45 50 55 В крайнем левом столбце ячеек 6" треугольной матрицы 2 нулевой логический уровень образуется на вертикальном выходе 4 той ячейки 6, на горизонтальные входы 9 и 7 которой подан единичный логический уровень. Начиная с указанной ячейки, нулевой логический уровень образуется на вертикальных выходах 14 всех расположенных ниже ячеек 6 рассматриваемого столбца, Таким образом, только в единственной ячейке 6 крайнего левого столбца треугольной матрицы 2 имеет место одновременное наличие единичных логических уровней на входах 13, 9 и 7, Следовательно, на выход 16 последней ячейки 6 крайнего левого столбца треугольной матрицы 2 направляются сигналы того горизонтального входного канала 7, которому соответствует первая сверху единица управляющего логического вектора г, разрядно совпадающая с единицей входного вектора Г, На горизонтальном выходе 10 ячейки 6, в которой произошло разветвление, образуется нулевой логический уровень, В результате на горизонтальные входы 9 ячеек 6 смежного правого столбца треугольной матрицы 2 подается копия исходного управляющего логического вектора, за исключением первой единицы, поразрядно совпавшей с единицей вектора Г, Соединение последующих входных каналов 7 коммутатора 1 с выходными каналами 16 в треугольной матрице 2 осуществляется аналоОчевидно, что треугольная матрица 3 коммутатора 1 не принимаетучастия в выполнении операции формирования единичного вектора,Режим расширения. Расширениемпроизвольного вектора называетсяоперация х - г/Г, размерность г неменьше размерности вектора т. Результат операции - вектор х, в котором компоненты исходного вектора занимают позиции, соответствующие единицам вектора г, Размерность вектора совпадает с размерностью вектора г,В матрице 2 на горизонтальные входы 11 ячеек 6 крайнего левого столбца подаются константы "1", причем награничные вертикальные входы 15 ячеек 6 с координатами (1, 1) (1 = 11 вматрице 2 и на граничные вертикаль 5 10 15 20 25 30 35 ные входы 13 и 5 ячеек 6 с координатами (1, 1) (К = 1) в матрице 3 подаются константы "О", а на граничныевертикальные входы 13 ячеек 6 с координатами (1, ) (1 = 1) матрицы 2 -логические уровни, соответствующиекоду управляющего (расширяющего) логического вектора,Входными каналами коммутатора 1при выполнении операции расширениятакже являются горизонтальные входы7 ячеек 6 крайнего левого столбцаматрицы 2, а выходными каналами -вертикальные выходы 16 ячеек 6 последней строки треугольной матрицы 2,При этом 1-й компоненте произвольного вектора соответствует горизонтальный вход 7 первой ячейки И-(ш 1) строки матрицы 2, где ш - размерность произвольного вектора, На(11-ш) верхние горизонтальные входы7 ячеек 6 крайнего левого столбцаматрицы 2 подаются константы "О",на нижние горизонтальные ш-входы 9ячеек 6 крайнего левого столбцаматрицы 2 - константы "1", а на (Ит) горизонтальные входы 9 - константы лО",В тех столбцах треугольной матрицы 2, где управляющий вектор имеетнули, не может быть ячеек 6, в которых произошло бы разветвление внизи, следовательно, на выходных каналах 6 последних ячеек 6 этих столбцов сохраняются нулевые логическиеуровни,Столбцы треугольной матрицы 2,которым соответствуют единицы управляющего вектора г, ведут себя следующим образом,В соответствии с управляющим вектором единичные логические уровни поданы на граничные вертикальные входы 13 ячеек 6 3, и так далее столбцов треугольной матрицы 2, тогда поскольку на все нижние горизонтальные входы 9 ячеек 6 крайнего левого столбца поданы константы "1", ситуация одновременного наличия единичных логических уровней на входах 13 и 9 возникает в И-(гп) -й ячейке 6 1, -го столбца, Следовательно, сигналы И-(в)-го и так далее входных каналов 7 направлены на вертикальные выходы 16 последних ячеек 6-го итак далее столбцов матрицы 2, что соответствует операции расширения.1314332 5 1 О 15 20 25 30 35 40 45 50 55 В выполнении данной операции треугольная матрица 3 не принимает участия,Режим сплетения, Сплетением называется операция х -(Е, г, ф, котораяпо двум производным векторам Й илогическому вектору г строит вектортакой, что компонента х, принимаетзначение очередной компоненты 2, если г; = О, либо очередной компоненты г, если г = 1, Размерность вектора х совпадает с размерностью ги равна сумме размерностей Й и .При выполнении операции сплетениятреугольная матрица 2 работает в режиме расширения вектора д управляющим вектором г, а треугольная матрица 3 - в режиме расширения вектора Гуправляющим вектором г, при этом вматрице 2 верхние щ строки не принимают участия в операции расширения,так как на горизонтальные входы 9этих строк поданы константы "О", ав матрице 3 - нижние щ строки, таккак на горизонтальные входы 9 этихстрок поданы константы 0". Сигналы,образующие на вертикальных выходах16 ячеек 6 последней строки матрицы2 и матрицы 3, одновременно поступают на элементы группы ИЛИ 4,Входными каналами коммутаторапри выполнении операции сплетенияявляются горизонтальные входы 7 ячеек 6 крайнего левого столбца матрицы 2, а выходными каналами - выходы17 элементов группы ИЛИ 4,Режим перегруппировки, Перегруппировкой произвольного вектора Г называется операция х.а в Е Ь г, где глогический вектор, размерность которого равна размерности вектора Г,Результат операции - произвольныйвектор х, который в качестве п первых компонент х содержит те компокенты Е исходного вектора Г, котогрые соответствуют г =1(11п),а в качестве щ следующих компонентх п+- те компоненты Г; исходноговектора Г, которые соответствуютг, =О (1щ), где и и щ - соответственно количество единиц и нулей в логическом векторе г, Размерность вектора х совпадает с размерностью г и равна сумме и+щ,При выполнении операции перегруппировки матрица 2 работает в режиме сжатия вектора 1 логическим вектором г, а матрица 3 - в режиме сжатия этого же вектора логическим вектором г,Результирующий вектор второй операции сжатия сцепляется справа с результирующим вектором первой операции сжатия итаким образом, получается результирующий вектор операцииперегруппировки,На горизонтальные входы 9 ячеек 6крайнего левого столбца матрицы 2подаются логические уровни, соответствующие коду управляющего логического вектора г, Входными каналамикоммутатора 1 при выполнении операции перегруппировки являются горизонтальные входы 7 ячеек 6 крайнего левого столбца матрицы 2, а выходнымиканалами - выходы 17 элементов группы ИЛИ 4, На горизонтальные входы 9ячеек 6 крайнего правого столбца матрицы 3 с элементов группы НЕ подаются логические уровни, соответствующие коду вектора г,Наличие горизонтального входа 11в каждой ячейке 6 коммутатора 1 позволяет выделять в полных треугольныхматрицах 2 и 3 треугольные подматрицы меньших размеров и организоватьодновременную и независимую работуподматриц, что значительно расширяет функциональные возможности коммутатора.Рассмотрим, каким образом с помощью горизонтальных входов 11 производится выделение треугольных подматриц в треугольной матрице 2 коммутатора 1,Пусть на горизонтальный вход 11 1.-й ячейки 6 крайнего левого столбца треугольной матрицы 2 подан нулевой логический уровень, а на все другие горизонтальные входы 11 ячеек 6 этого столбца - единичные логические уровни, В этом случае в треугольной матрице 2 выделяются две независимые треугольные подматрицы. Логический вектор, имеющийнулей, выделяет в треугольной матрице (д+1) независимых подматриц. Выделение из полной треугольной матрицы независимых и изменяемых по размеру треугольных подматриц позволяет организовать в каждой из них свой режим работы, причем эти подматрицы могут работать одновременно, выполняя различные операции сжатия и расширения. Каждой треугольной подматрице, выделенной из треуголь13143 деляемых парах треугольных подматрицпозволяет аппаратно реализовать процедуру сортировки (упорядочения)элементов массива,Формула изобретения иг език Составитель О, Б Редактор Ю. Середа Техред М.ХоданичШулл орректо 73комитета СССй и открытийшская наб., ц 14/49 ЩИИПИ Госуд по делам 3035, Москвасно Тиражтвенно аказ зобрете Ж.5, Р 1 роизводственно-полиграфическое предприятие, г, Ужгород, ул, Проектная, 4 9ной матрицы 2, соответствует идентичная смежная с ней по диагонали треугольная подматрица из треугольной матрицы 3, т,еобразуется пара идентичных треугольных подматриц, одна из которых расположена в треугольной матрице 2, а другая - в треугольной матрице 3, Все пары выделенных треугольных подматриц могут работать одновременно и работа лю бой пары не зависит от работы других пар, что позволяет в каждой из пар треугольных подматриц организовать свой режим работы, причем работать эти пары будут одновременно, выпол няя различные операции сплетения и перегруппировки, Размеры пар треугольных подматриц можно оперативно изменять, меняя код логического вектора20Свойства коммутатора выполнять операции перегруппировки одновременно во всех определенным образом выКоммутатор по авт, св. В 1120313, о т л и ч а ю щ и й с я тем, что, с целью расширения функциональных возможностей за счет выполнения операции формирования единичного вектора, в каждую ячейку введены четвертый элемент И и второй элемент ИЛИ, причем второй и третий горизонтальные входы каждой ячейки соединен с первым и вторым входами второго элемента ИЛИ, выход которого соединен с первым входом четвертого элемента И, второй вход которого соединен с выходом третьего элемента И, а выход четвертого элемента И является первым горизонтальным выходом ячейки.