Коммутатор

СОЮЗ СОВЕТСКИХОСЦааепневикРЕСПУБЛИН З(59 С 06 Г 7/00 ОПИСАНИ К АВТОРСКОМУ ОБРЕТЕНИЯ ЕТЕЛЬСТ видетельство ССГ 7/00, 1971,идетельство СССРК 17/00, 1981.идетельство СССРР 7/00, 1976 ая ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРГО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Институт математики Сибирского отделения АН СССР и Новосибирский государственный университет им. Ленинского комсомола. (54)(57) КОМИУТАТОР, содержащий матрицу ячеек из двух треугольных матриц, причем в первой треугольной матрице первый и второй вертикальные входы ячейки с координатами (ь, 1) соединены соответственно с первым и вторым вертикальными выходами ячейки с координатами (х, 3), первьй, второй горизонтальные входы ячейки с координатами (д, 3)соединены соотвественно с первым, вторым горизон тальными выходами ячейки с координатами (, 1-1), во второй треугольной матрице первый и второй вертикальные входы ячейки с координатами (1, 8) соединены соответственно с первым и вторым вертикальными вьасодами ячейки с координатами Ос,Ф) пейый, второй горизонтальные входы ячейки с координатами , ) соединены соответственно с первым, вторым горизонтальными выходами ячейки с координатами , 1-б (1 с, 1 щ 1-0,1-3., 61-1 с), а кажд ячейка со.,801120 13 А держит три элемента И, два элемента НЕ и элемент ИЛИ, причем первый и второй горизонтальные и первый вертикальный входы ячейки соединены соответственно с входами с первого по третий первого элемента И, выход которого подключен к первому входу элемента ИПИ, второй вход которого соединен с вторым вертикальным входом ячейки, первый вертикальный вход которой соединен с первым входом второго элемента И, второй вход которого через первый элемент НЕ соединен с первым горизонтальным вхо- дом ячейки и первым входом третьего элемента И, второй вход которого че-рез второй элемент НЕ подключен к первому вертикальному входу ячейки, первый, второй вертикальные и первый, второй горизонтальные выходы С ячейки соединены соответственно с ,выходами второго элемента И, элемента ИЛИ, третьего элемента И и вторым горизонтальным входом ячейки, о т л и ч а ю щ и й с я тем, что с целью расширения функциональных возможностей за счет выполнения операций сжатия, расширения, сплетения (ф и перегруппировки, он содержит груп- фы пу элементов ИЛИ и группу элементов р НЕ, причем третий горизонтальный вход каждой ячейки соединен с третьим входом второго элемента И данной ячейки и.ее третьим горазонтальным вывыходом, третий горизонтальный вход . 3 Ьячейки с координатами (, 1) в первой треугольной матрице соединен с, третьим горизонтальным выходом ячейки с координатами (д, 3-1),третий горизонтальный вход ячейки с координатами (1, С) во второй треугольной112 СЗ 13матрице соединен с третьим горизонтальным выходом ячейки с координатами (1 с, -1), второй горизонтальнья Выход последней ячейки -й строки пер- вой треугольной матрицы соединен с вторым горизонтальным входом первой ячейки (И-Е) -й строки второй треугольной матрицы, третий горизонталь- ной выход последней ячейки,-й строки первой треугольной матрицы соединен с третьим горизонтальньи входом первой ячейки (Б-к)-й строки Второй треугольной матрицй, третий горн.эонтальный выход последней ячейки :последней строки первой треугольной .матрицы соединен с третьим горизонтальным входом первой ячейки послед-:ф ней строки второй треугольной матрицы Второй вертикальный выход 1-й ячейки последней строки первой треугольной матрицы и второй вертикальный выход (Н-ь+1) -й ячейки последней строки ьторой треугольной матрицы подключены соответственно к перному и второму входам -го элемента йИ группы, вььход которого является гьг.одом коммутатора первьй горизонтальный вход первой ячейки к - й строи второй треугопьной матриць 1 подключен к выходу к-го элемента НЕ группы элементов НЕ, вход которого соединен с первьв 1 горизонтальным Входом первой ячейки (И+1)-й строки перВой треугольной матрицы.Изобретение Относится к цифровойВычислительной технике и предназна,чено для логической обработки мясовов информации,Известен коммутатор, содержащийматрицу из ячеек, состоящих из эле -ментов И, ИЛИ, НЕ, и выполняющий опе".рации логической обработки мас=епов,с помощью которого можно реализова".ьразличные операции преобразования ,Сструктур массовов 1 ,Недостатки дянного коммутаторасложность ячеек и длительное времянастройки на заданнс е преобразование.РЗВЕСТЕН КОМЬУТЯТОР СОДЕРжаЩИйматрицу ячеек, каждая из которьгхсодержит два элемеля ьь урн злемента Я и трн элемента ЦИ; С помощьюэтОГО коммутятова возможно изменениепорядка соединения каналов Г 2 3 2 бНедостатком данного коьаутатараявляется сложность ячеек.Наиболее близким к изобретению .Отехнической сущности являетсяОммутатор, содержащий мятвиц-,т из одинаковых ячеек, каждая из которьп; содержит элементы Ч, ИЛИ НЕ,. Причемгоризонтальные и первьй Вертикальньгйвходы ячейки соединены с входамипервого элемента И, вьп;Од которогоподключен к одному из Входов первогоэлемента ИГИ, другой Вход которогоссединен с Вторьж Вертикальным Входом ячейки, а вьпод - с вторым вер гикя,: ьны Вььходом ячейкепеон; д" Вевти -А;хд ячейк. Водкпче-Я 1;-е дп 1 тои Вход которого -врез чеввыи "регент НЕ Оединес пе л,в , говизон -ал.:-нььм В Опсм ;чеик;:. з Выхо- с1 лОВЫ 1, Р,ЗРТЛУ - ЬО 1 -ЕЛ"Л ВС з.й- ,О-,тх О1-,ЬНЫй Воп,.-ЕйКсою-П"НЕВСПЪ НЗ В;:; ОПОР : ЕТЬ О ЗЛЕЕН 1 Р", ВТОРй ВХОД,"Р.-ОООГО ЧЕ.ЕЭ Второн элемент ;:,Е подключен к первоВЫХОД - К ПЕРВОГУ ЛОВИ: О:. РЯЛ-;НО;,;,т3нВ; ; у ЧрИКЧ В .1 О ПОИ О л т -- -,. 1 й . Код .ч - йки соединен с ВОВ-.: гоон-зонтапьным Выходом ячейки - .Н.Вм Верт капьные Вхсдь: ячеке с косОделат= - ЛЬХОДЯМИ ЯЧЕ 1,"Ц, - о - и"- - -" . НЫ 7.; . -,ДУУТЯ,,", В 1 ПОП:;Е. ОЛ КО ОГРЯ - ЯС С ИВ ОВ с112031 зЦель изобретения - расширениефункциональных возможностей коммутатора эа счет выполнения операцийсжатия, расширения, сплетения и перегруппировки,Поставленная цель достигается тем,что коммутатор, содержащий матрицуячеек иэ двух треугольных матриц,причем в первой треугольной матрицепервый и второй вертикальные входы10ячейки с координатами (,3) соединены соответственно с первым и вторым вертикальными выходами ячейкис координатами (1-1, 3), первый,второй горизонтальные входы ячейкис координатами (х,3) соединены соот 15ветственно с первым, вторым горизонтальными выходами ячейки с координатами (, 3-1), во второй треугольнойматрице первый и второй вертикальныевходы ячейки с координатами (к, 3)соединены соответственно с первым ивторым вертикальными выходами ячейкис координатами Ь, 1), первый, второй горизонтальные входы ячейки скоординатами Й,.2) соединены соответ 25ственно с первым, вторым горизонтальньпи выходами ячейки с координатами(1 с,1-6 Ъ,=1 - Б, 3=1-, =1-И,а каждая ячейка содержит три элемента И, два элемента НЕ и элемент ИЛИ,причем первый и второй горизонтальныеи первый вертикальный входы ячейкисоединены соответственно с входами спервого по третий первого элементаИ, выход которого соединен с первым 35входом элемента ИЛИ, второй вход,которого соединен с вторым вертикальным входом ячейки, первый вертикальный вход которой соединен с первым входом второго элемента И,второй 40вход которого через первый элементНЕ соединен с первым горизонтальнымвходом ячейки и первым входом третьего элемента И, второй вход которогочерез второй элемент НЕ соединен с 45первым вертикальным входом ячейки,первый, второй вертикальные и первый,второй горизонтальные выходы ячейкисоединены соответственно с выходамивторого элемента И, элемента ИЛИ, 50третьего элемента И и вторым горизонтальным входом ячейки, содержит группу элементов ИЛИ и группу элементовНЕ причем третий горизонтальный входкаждой ячейки соединен с третьим вхо дом второго элемента И данной ячейкии ее третьим горизонтальным выходом,третий горизонтальный вход ячейки с координатами (,1) в первой треугольной матрице соединен с третьим горизонтальным выходом ячейки с координатами (1, 1-1), третий горизонтальный вход ячейки с координатами Ь,) во второй треугольной матрице соединен с третьим горизонтальным выходом ячейки с координатами Ь,8-1), второй горизонтальный выход последней чейки д-й строки первой треугольной, атрицы соединен с вторым горизонта 3 тЬ- ным входом первой ячейки (И-Е)-й строки второй треугольной матрицы, третий горизонтальный выход последней ячейки 1-й строки первой треугольной матрицы соединен с третьим горизонтальным входом первой ячейки (М-Е) -й строки второй треугольной матрицы, третий горизонтальный выход последней ячейки последней строки первой треугольной матрицы соединен с третьим горизонтальным входом первой ячейки последней строки второй треугольной матрицы, второй вертикальный выход 1-й ячейки последней строки первой треугольной матрицы и второй вертикальныи выход (И -1+1) -й ячейки последней строки второй треугольной матрицы подключены соответственно к первому и второму входам 3-го элемента ИЛИ группы, выход которого является выходом коммутатора, первый горизонтальный вход первой ячейки к-й строки второй треугольной матрицы подключен к выходу к-го элемента НЕ группы, вход которого соединен с первым горизонтальным входом первой ячейки (И+1) -й строки первой треугольной матрицы. На фиг. 1 представлена схема предлагаемого коммутатора;на фиг, 2 - схема ячейки.Коммутатор 1 содержит треугольные матрицы 2 и 3, группу 4 элементов ИЛИ, группу 5 элементов НЕ, ячейки 6 с вторыми горизонтальными входом 7 и выходом 8, первыми горизонтальными входом 9 и выходом 10, третьими горизонтальными входом 11 и выходом 12, первыми вентикальными входом 13 и выходом 14, вторыми вертикальными входом 15 и выходом 16, выход 17 коммутатора. Ячейка коммутатора содержит элементы НЕ 18 и 19, элементы И 20-22, элемент ИЛИ 23.Коммутатор работает следукщим образом.Режим сжатия.,называется операция х-г/Г, где яуправляющий логический (двоичный) вектор, размерность которого совпадаетс размерностью вектора Г, Результатоперации - вектор х, который содержитте компоненты Г. исходного вектора,которые соответствуют г,=1, Раэмерность вектора х совпадает с количеством единиц вектора я, 1 ОВ треугольной матрице 2 на входы13 и 15 ячеек 6 с координатами(1,3) (1=3) подаются соответственноконстанты "1" и "0", а на входы 13 к15 ячеек б с координатами (1 с, б (1 с=й 151 реугольной матрицы 3 подаются константы 0 н. На входы 11 ячеек 6 крайнего левого столбца треугольной матрицы 2 подаются константы "1", нагоризонтальные входы 9 ячеек 6 крайнего левого столбца треугольной матрицы 2 - логические уровни соответствующие коду управляющего логичес-.кого вектора г. Выходными каналамикоммутатора 1 при выполнении опера Бции сжатия являются горизонтальныевходы 7 ячеек б крайнего левогостолбца треугольной матркцы 2 авьиодными каналами - вертикальныевыходы 16 ячеек 6 последней строкитреугольной матрицы 2,В ырайнем левом столбце яческ 6треугольной матрицы 2 нулевой логический уровень образуется на вертикальном выходе 14 той ячейки 6 на горизоитальный вход 9 которой поданединичный логический уровень. Начиная с указанной ячейки, нулевой логический уровень образуется на Вертикальных выходах 14 Всех расположенбных ниже ячеек 6 рассматриваемогостолбца. Таким образом, только вединственной ячейке б крайнего левого столбца треугольной матрицы 2имеет место одновременное наличиеединичных логических уровней ня Входах 13 и 9, в результате чего именнов этой ячейке осущестьляется подключение, горизонтального входа 7 к вертикальному выходу 16, т,е. реализуется соедкнинтельная Функция Рязветвление вниз . Следовательно, навход 1 б последней ячейки 6 крайнеголевого столбца треугольной матрицынаправляются сигналы того горизонтального входного канала 7 которомусоответствует первая сверху единицауправляющего логического вектора к.На горизонтальном выходе 10 той ячейкк 6 в 1.оторой произошло разнетвленке, образуется нулевой логический уровень, В результате ня горизонтальные Входы 9 ячеек 6 смежного правого столбца треугольной матрицы 2 подастся копия исходного упрявляюще - го логического вектора зя исключением первой его единицы. Соединение последу 1 ощих Бходньо. каналов 7 коммутатора 1 с выходными кянялямк 16 Б треугольной матрице 2 Осуществляетсяаналогично.Таким образом, ня выхопы 16 нижней границы треугольной матрицы 2 Бпервом, Второй к так далее столбцахнаправляются сигналы тех входных ка -нялов 7, которым соответствует перыяя,Вторая к тяк далее единицы исходногокода управляющего логического Бекторя е что соответствует Оперяц:"1 и сжя -тия.Очевидно что треугольная матрица3 коммутатора 1 не прии:ь 1 яет у 1 ясткяБ Быпол 11 ении операции сжатия.Р ежим рясшир ения,Расширением произвольного в:;.ктораназывается Операция х ьк/ ряз --сходного Вектора занкмяют позкц 1=.-:соответствующие единицам Векторя еРазмерность Вектора х совпяцяе 1 сразмерностью вектора к.,В матрице 2 НЯ горизонтальные зхо -ды 11 ячеек 6 крайнего легого столбца подаются константы 1", НЯ гранич -кь 1 е Бертика 11 ьнь 1 е ВходыЗ ячеек 6 сКООРпицата И (Х,3) (т=1) Б МЯТРКЦЕ2 ч ня граничные Вертикальные входы13 и 5 ячеек 6: коордкнятямк Ь, О(к.) В матрице 3 подаются кокс ган -и 11ть: О, а нг .граничные вертикальныеВходы 13 ячеек б с ксординятамк (1,.3),расширяющего,1 логического Вектора яВходньии каналами Оммутяторяпрк Бьнол 1 зеник Операции расширениятякже являются г Ориз Онтд чьнь 1 е Б 1.".ды 7 ячеек 6 кГЯйного пеБОГО столбца мЯт - Окцы 2 я выхо-. гк (нплямк - -.ертккальные Вьо;сдь 1 16 ячеек 6 1 тс ледней Г 1;ОКК ТОЕтгОЛЬНОй Матриць 1 2. Гр ЯТОМ Х-й КОМГ ОНЕН ГЕ 1 г ОКЗВОЛЗОТ О , ОЯСШКРЯЕМОГО) БЕКТОРЯ С ООТБЯ Ст Б нЕ Т Г О р и З О и Т ЯЛ Ь и Ь 1 й Б л О и 7 ГУБ Б О й ячейки .11-ш-,.-и ство:;11 матвкцы 2, 7 11203 вектора. На (И-щ) верхних горизонтальных входов 7 ячеек 6 крайнего левого столбца матрицы 2 подаются константы 0, на щ нижних горизонтальных входах 9 ячеек б крайнего левого столбца матрицы 2 - константы "1", а на (И-щ) горизонтальных входов 9 константы "0".В тех столбцах треугольной матрицы 2, где управляющий вектор г имеет нули, не может быть ячеек б, в которых произошло бы раэветвление вниз и, следовательно, на выходных каналах 16 последних ячеек 6 этих столбцов сохраняются нулевые логические уровни.Столбцы треугольной матрицы 2, которым соответствуют единицы управляющего вектора г, ведут себя следующим образом.20Пусть в соответствии с управляющим вектором г единичные логические уровни поданы на граничные вертикальные входы 13 ячеек 6 3и так далее столбцов треугольной матрицы.2. Тогда, поскольку на все щ нижних горизонтальных входов 9 ячеек 6 крайнего левого столбца поданы константы "1", ситуация одновременного наличия единичных логических уровней на входах 13 и 9 возникает в И-(щ)Д -й ячей 30 ке 6 1-го стобца. Следовательно, сигналы И-(щ - 1)-го и так далее входных каналов 7 направлены на вертикаль. ные выходы 16 последних ячеек б З-го и так далее столбцов матрицы 2, что соответствует операции расширения .В выполнении данной операции треугольная матрица 3 также не принимает участия.Режим сплетения. 40Сплетением называется операция хХ,г,ц 1, которая по двум произвольным векторам Г и о м логическому вектору г строит вектор х такой, что компонента х, принимает значение ф 5 очередной компоненты Г, если г.=О,1 либо очередной компоненты о, если г; =1, Размерность вектора х совпадает с размерностью г и равна сумме размерностей Г и о. 50При выполнении операции сплетения треугольная матрица 2 работает в режиме расширения вектора о управляющим вектором г, а треугольная матрица 3 в режиме расширения вектора Г управ ляющим вектором г, при этом в матрице 2 верхние и строк не принимают участия в реализации операции расшире 13 8ниятак как на горизонтальные. входы9 этих строк поданы константы "0", ав матрице 3 - нижние щ строк, так какна горизонтальные входы 9 этих строкподаны константы "0"Сигналы, образующиеся на вертикальных выходах 16ячеек 6 последней строки матрицы 2 иматрицы 3, одновременно поступаютна элементы ИЛИ группы 4.Входными каналами коммутатора 1при выполнении операции сплетения яв-ляются горизонтальные входы 7 ячеек6 крайнего левого столбца матрицы 2,а выходными каналами - выходы 17 элементов ИЛИ группы 4.Режим перегруппировки .Перегруппировкой произвольного век.тора Й называется операция х + Гйг,где г - логический вектор, размерность которого равна размерности вектора Х. Результат операции - произвольный вектор х, который в качествеи первых компонент х содержит текомпоненты Г. исходного вектора Г,которые соответствуют г в -1 ( 163 и),1а в качестве щ следующих компонентх и+- те компоненты 1: исходноговектора й, которые соответствуют г; О(16 щ), где г. и щ - соответственноколичество единиц и нулей в логическом векторе г. Размерность вектора хсовпадает с размерностью г и равнасумме и+щ.Прч выполнении операции перегруппировки матрица 2 работает в режимесжатия вектора Е логИческим векторойг, а матрица 3 - в режиме сжатия этого же вектора Г логическим вектором г.Результирующий вектор второй операции сжатия сцепляется справа с результирующим вектором первой операции сжатия и, таким образом, получается результирующий вектор операции перегруппировки,На горизонтальные входы 9 ячеек6 крайнего левого столбца матрицы 2подаются логические уровни, соответствукицие коду управляющего логического вектора г. Входными каналами коммутаторапри выполнении операцииперегруппировки являются горизонтальные входы 7 ячеек 6 крайнего левогостолбца матрицы 2, а выходными каналами - выходы 17 элементов ИЛИ группы 4. На горизонтальные входы 9ячеек б крайнего правого столбцаматрицы 3 с элементов НЕ группы 5 подаются логические уровни, соответствующие коду вектора г.9 11203Наличие горизонтального входа 11в каждой ячейке 6 коммутаторапозволяет выделять в полных треуголь;ных матрицах 2 и 3 треугольйые подматрицы меньших размеров иорганизо 5вать одновременную и независимую работу подматриц, что значительно расширяет функциональные возможностикоммутатора.Рассмотрим, каким образом с по-мощью горизонтальных входов 11 произвОдится выделение треугольных подматриц в треугольной матрице 2 коммУтатора 1,Пусть на горизонтальный вход 1-й ячейки 6 крайнего левого столбца треугольной матрицы 2 подач нулевой логический уровень, а на все другие горизонтальные входы 11 ячеек 6этого столбца - единичные логические2 1уровни. В этом случае в треугольнойматрице 2 выделяются две независимые треугольные подматрицыЛогический вектор, имеющий О нулей, выделяет в треугольной матрице (1+1)независимых подматриц,Выделение из полной треугольнойматрицы независимых и изменяемыхпо размеру треугольных подматриц позволяет организовать в каждой из нихЗОсвой режим работы, причем эти подматрицы могут работать одновременно,выполняя различные операции сжатия ирасширения. Каждой треугольной подматрице, выделенной из треугольной матрицы 2, соответствует идентич -3ная смежная с ней по диагонали тре.угольная подматрица из треугольнойматрицы 3, т,е. образуется пара1 идентичных треугольных подматриц,одна из которых расположена в треу- фгопьной матрице 2, а другая - в треугольной матрице 3. Все пары выделен 13 1 Оных тре угол ьных подматриц могут раб отать одновременно и оабота любой пары независит от работы других пар, чтопозьоляет в каждой из пар треугольныхподматриц организовать свой режимработы, причем работать эти парыбудут одновременно выполняя различные операции сплетения и перегруппировки, Размеры пар треугольных подматриц можно оперативно изменять, меняя код логического ьектара.Свойство коммутатора вьполнятьоперации перегруппировки одновременно во всех определенным образом выделяемых парах треугольных подматрицпозволяет аппаратно реализоватьпроцедуру сортировки (упорядочения)элементов массива.Предлагаемьщ коммутатор выполняетширокий набор Функций преобразованиямассивов, сжатие, расширение сплетение, перегруппировку, упорядочениеи др: Возможность разделения матрицыкоммутатора на не-ависимые подматрицы позволяет организовать параллельгую работу всех подматриц причемз с Гдельньх в;Одматрицах могут Одно -временно выполняться различные Операции: Это обеспечивает хороьтую згрузку устройства при одновременномрешении набора задач с массивамиразличных размеров,Простота ячеек и соеД.нения внуттимятрыц только с соседними ячейкамиобеспечивают высокую технологичностьы надежность при произвоцстве на основе интегральной технологии,Настройка и перестройка комгута -тора. осуществляется подачей на состъетствующиз внешние входы управляющих1120313 Составитель А.Клюеведактор И, Николайчук Техред Л, Кощобняк рректор З,Бутя дпис ное ПП "Па г. Ужгоро Проект ная,аказ 7742/35 Тираж б 98 ИоВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113 О 35, Москва, Ж, Раушская наб ., д,