Коммутатор Советский патент 1984 года по МПК G06F7/00 

матрице соединен с третьим горизонтальным выходом ячейки с координата1 (k, t--1), второй горизонтальный выход последней ячейки i-й строки п&рвой треугольной матрицы соединен с вторым горизонтальным входом первой ячейки (Н-и-1)-й строки второй треугольной матрицы; третий горизонтальной выход последней ячейки .i-й строки первой треугольной матрицы соединен с третьим горизонтальным входом первой ячейки (Н-и)-й строки второй, ;треугольной матрицьц третий гори:зонтальный вькод последней ячейки I последней строки первой треугольной I матрицы соединен с третьим горизонтальным., вход ом первой .ячейки последней строки второй треугольной матрицЫд второй вертикальный выход j-й ячейки последней строки первой треугольной матрицы и второй вертикальный выход ()й ячейки последней строки второй треугольной матриць подключены соответственно к первому и второму входам элемента ШШ группы,, вьпсод которого является ВЫХОДОМ комг-г/таторад первьй горизон.тальный вход первой ячейки к-и строkH второй треугольной матрицы подключен к выходу к-го злемента НЕ группы элементов НЕд вход которого соединен с первым горизонтальным входом первой ячейки (N-k+1)-ft строки первой треугольной матрицы.

КОММУТАТОР, содержащий матрицу ячеек из двух треугольных матриц, причем в первой треугольной матрице первьш и второй вертикальные входы ячейки с координатами (i, j) соединены соответственно с первым и вторым вертикальными выходами ячейки с координатами (i-1, j), первый, второй горизонтальные входы ячейки с координатами (i, з)соединены соотвественно с первым, вторым горизон тальными выходами ячейки с координатами (i, j-1), во второйтреугольной матрице первый и второй вертикальные входы ячейки с координатами (k, 6) соединены соответственно с первым и вторым вертикальными выходами ячейки с координатами (k-1,) пet)6ый, второй горизонтальные входы ячейки с координатами (k, ) соединены соответственно с первым вторым горизонтальными выходами ячейки с координатами (k, 1-t) (k, , ), a каждая ячейка содержит три элемента И, два элемента НЕ и элемент ИЛИ, причей первый и второй горизонтальные и первый вертикальный входы ячейки соединены соответственно с входами с первого по третий первого элемента И, выход которого подключен к первому, входу элемента ИЛИ, второй вход которого соединен с вторым вертикальным входом ячейки, первый вертикальный вход которой соединен с первым входом второго элемента И, второй вход которого через первый элемент НЕ соединен с первым горизонтальным входом ячейки и первым входом третьего элемента И, второй вход которого через второй элемент НЕ подключен к (Л первому вертикальному входу ячейки, первый, второй вертикальные и первый, второй горизонтальные выходы ячейки соединены соответственно с .выходами второго элемента И, элемента ИЛИ, третьего элемента И и вторым горизонтальным входом ячейки, отличающийся тем, что с целью расширения функциональных возможностей за счет выполнения операций сжатия, расширения, сплетения и перегруппировки, он содержит группу элементов ИЛИ и группу элементов НЕ, причем третий горизонтальньй вход каждой ячейки соединен с третьим входом второго элемента И данной ячейки и ее третьим горазонтальным вывыходом, третий горизонтальный вход ячейки с координатами (i, j) в первой треугольной матрице соединен с третьим горизонтальным выходом ячейки с координатами (i, j-1),третий горизонтальный вход ячейки с координатами (fe, t) во второй треугольной

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

Известен коммутатор содерлсаший матрищг из ячеек, состоящих из эле1нентов И, ИЛИр НЕр и вьшолкяюрлий оп.ерации логической обработки массизо.Во с помощью которого можно реалийов&ть различные операции преобразования структур массовое 1 j.

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

Известен KOMNrsTaTops содержащий матрицу ячеек, каждая из которых содержит два элемента KEj три элемента И и три элемента ИЛИ, С помощью зтого ком1у утатора возможно изменение порядка соединения каналов С 2 1,

Недостатком данного коыр утатора является сложность ячеек.

Наиболее близким к изобретенрпо по технической сущности является коммутатор, содержащий матриц:;,г из о.динаковых ячеекэ каждая из которьи содержит элементы И, ЕПИ,, НЕ пркчвЕ горизонтальные и первьй вертикальный входы ячейки соединены с вхадаг-1И первого элемента И, вькод которог-о подключен к одному из входов первого элемента ШШ, другой вход которого соединен с вторым вертикальным вмсдом ячейкИ; а вьжод с вторым верти2

кальным выходом ячейки,, первый верти :;альньш вход ячейки подключен также У. одномз. из 13ХОДОЕ зторогс И; другой вход которого через первый элемент КЕ соединен с пкрвлк горизонтальным вхоцом ячейки, а выход - с первым вертикальным зккодом ячейгси. первый горизонтальный вход ячейки содинен с одним из входов третьего злемента И,, второй вход которого через второй злемект КЕ подключен к первому вертикальному входу , а выход - к tiKpsoify гооигонталъно1-г/ выходу ячейки, ЕТОРОЙ горизонтапькьш вход .Ячейки соединен с втсрьй/ горизонтальньш выходом ячейки,, причем вертикальные входы ячейки с коордкиата; -га (i, j)coaдингкы с sepvHKajribHbiMH выходами ягчейки с косрдинатаки . (i, J + 1JJ вертикальные выходы - с вертикальнь&ш ЕЗодамк ячейхя с коор.П1натэ.- ми (ij .K первые горкзонтальяые зход и вькод - с 73горыни горнзоатальными вьйсодом и входом ячейки с .координатами (i-lj j), а нторыа горизонтальные ixoA, н выход - с первыми горк охчтаньнь11 г-1 ;.:; : одами и входом ячейки с коор.цкна гами ( j) . Комиута™ тор имеет однородную структуру достагочкс простые ячейки и -высокую скоpocib .ХЗ D, Однако изв:;сткый коммутатор Быпсшняет только ограничек ый набда фун-ашй преобразования массивов,: J112 Цель изобретения - расширение функциональных возможностей коммутатора за счет выполнения операций сжатия, расширения, сплетения и перегруппировки. Поставленная цель достигается тем что коммутатор, содержащий матрицу ячеек из двух треугольных матриц, причем в первой треугольной матрице первый и второй вертикальные входы ячейки с координатами (i,j) соединены соответственно с первым и вторым вертикальными выходами ячейки с координатами (i-1, j), первый, второй горизонтальные входы ячейки с координатами (i,j) соединены соответственно с первым, вторым горизонтальными выходами ячейки с координатами (i, j-1), во второй треугольной матрице первый и второй вертикальные входы ячейки с координатами (к,2) соединены соответственно с первым и вторым вертикальными выходами ячейки с координатами (k-1,), первьм, второй горизонтальные входы ячейки с координатами (k,.2) соединены соответ ственно с первым, вторым горизонталь ными выходами ячейки с координатами (k,-© (k, - N, j 1-i, 1-k), a каждая ячейка содержит три элемента И, два элемента НЕ и элемент ИЛИ, причем первый и второй горизонтальны и первый вертикальньй входы ячейки соединены соответственно с входами с Первого по третий первого элемента И, выход которого соединен с первым входом элемента ИЛИ, второй вход доторого соединен с вторым вертикальным входом ячейки, первьй вертикальньй вход которой соединен с первым входом второго элемента И, второйвход которого через первый элемент НЕ соединен с первым горизонтальньм входом ячейки и первым входом третье го элемента И, второй вход которого через второй элемент НЕ соединен с первым вертикальным входом ячейки, первый, второй вертикальные и первый второй горизонтальные выходы ячейки соединены соответственно с выходами второго элемента И, элемента ИЛИ, третьего элемента И и вторым горизон тальным входом ячейки, содержит груп пу элементов ИЛИ и группу элементов НЕ, причем третий горизонтальньй вхо каждой ячейки соединен с третьим вхо дом второго элемента И данной ячейки и ее третьим горизонтальным выходом, третий горизонтальный вход йчейки 4 с координатами (i,j) в первой треугольной матрице соединен с третьим горизонтальным вькодом ячейки с координатами (i, j-1), третий горизонтальный вход ячейки с координатами (k,) во второй треугольной матрице соединен с третьим горизонтальным выходом ячейки с координатами (k,t-1), второй горизонтальньй выход последней (ячейки i-й строки первой треугольной, матрицы соединен с вторым горизонтальным входом первой ячейки (N-k-l)-й строки второй треугольной матрицы, третий горизонтальньй выход последней ячейки i-й строки первой треугольной матрицы соединен с третьим горизонтальным входом первой ячейки {N-k)-й строки второй треугольной матрицы, третий горизонтальньй выход последней ячейки последней строки первой треугольной матрицы соединен с третьим горизонтальным входом первой ячейки последней строки второй треугольной матрицы, второй вертикальньй выход j-й ячейки последней строки первой треугольной матрицы и второй вертикальньй выход (Ы-€+1)-й ячейки последней строки второй треугольной матрицы подключены соответственно к первому и второму входам j-ro элемента ИЛИ группы, выход которого является выходом коммутатора, первый горизонтальньй вход первой ячейки к-й строки второй треугольной матрицы подключен к выходу к-го элемента НЕ группы, вход которого соединен с первым горизонтальным входом первой ячейки (N-k+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. Коммутатор работает следукщим образом. Режим сжатия. I112 Сжатием произвольного вектора f .называется операция x«-z/f, где z управляющш логический (ДВОИЧНЬЕЙ) ве тор, размерность которого совпадает с размерностью вектора f. Результат операции - вектор х который содержи те компоненты исходного вектора, которые соответствуют Z. 1 Размерность вектора х совпадает с количеством единиц вектора z, В треугольной матрице 2 на входы 13 и 15 ячеек 6 с координатами (i,j) () подаются соответственно константы 1 и О,, а на входы 13 и 15 ячеек 6 с координатами (k,f)(k) Треугольной матрицы 3 подаются кон- станты На входы 1.1 ячеек 6 край него левого столбца треугольной матрицы 2 подаются константы 1 на горизонтальные входы 9 ячеек 6 крайнего левого столбца треугольной мат рицы 2 - логические уровни, соответ ствукядие коду управлякщего логического вектора z. Выходными каналами коммутатора 1 при выполнении операции сжатия являются горизонтальные входы 7 ячеек 6 крайнего левого столбца треугольной матрицы 2s а выходными каналами - вертикальные выходы 16 ячеек 6 последней строки треугольной матрицы 2, В крайнем левом столбце ячеек 6 треугольной матрицы 2 нулевой логический уровень образуется на вертикальном выходе 14 той ячейки 6, на ризоктальный вход 9 которой подан единичный логический уровень. Начиная с указанной ячейки, нулевой лог ческий уровень образуется на вертикальных выходах М всех распсложенных ниже ячеек 6 рассматриваемого столбца. Таким образом только в единственной ячейке 6 к райнего лево го столбца треугольной матрицы 2 имеет место одновременное наличие единичных логических уровней на вхо дах 13 и 9, в результате чего именн в этой ячейке осуществляется подклю чение, горизонтального входа 7 к вер тикальному выходу 16, т.е. реализуется соедининтельная функция Разветвление вниз. Следовательно, на вход 16 последней ячейки 6 крайнего левого столбца треугольной матрицы направляются сигналы того горизонта ного входного канала / которому соответствует первая сверху управляющего логического вектора z. На горизонтальном выходе 10 той ячей ки 6j 3 которой произошло разнетвленив; образуется нулевой логический уровень, В результате на горизонтальные входы 9 ячеек 6 смеж)-1ого правого столбца треугольной матрицы 2 подастся копия исходного управляющего логического вектора за исключением первой его единицы. Соединение последующих входньо: каналов 7 коммутатора I с выходными каналами 16 Е тре.угольной матрице 2 осуществляется аналогично. Таким образoMj на выходы 16 ниж- . ней границы треугольной матрицы 2 в первоМ; второй и так далее столбцах направляются сигналы тех входных каналов 7, которым соответствует первая, вторая к так далее единицы исходного кода управляющего логического аектора Zj что соответствует операцми сжатия . Очевидно, что треугольная матрица 3 коммутатора 1 не принимает участия в выполнении операции сжатия . Р ежим расшир ения. Расширением произвольного .ра f называется onepaLVHH x.z/f,.. разv-;e.pKocTb г не меньше размеркос7И вектора f. Результат onepauj.H вектор X; Е котором ког.шо:-гектз f. лсходного вектора занимают позиций,. соответствующие единицам вектора z, Размерность вектора х совпа.дает с размерностью вектора z., В матрице 2 на горизонтальные входы 11 ячеек Ь крайнего левого столб- дь подаются консгакты ;.; на граничкьге вертика.пькые входы 15 ячеек 5 с координата чи (ijj) () в матрице 2 и на граничные вертикальные входы 13 и 5 ячеек 6 с координгтамк (k,) (k-fC) в матрице 3 подаются константы , а на граничные вертикальные входы 13 ячеек 6 с координатами (.) () матрицы 2 -- логические з-РЗВНИ„ соответствующие -соду управляющего (расширяющего) логического взхтора z, Входными канаг(ам-и ггоммутатора 1 при вьйтолнении операции расширения также являкяся гсфизоктапьные й :-;ды 7 ячеек 6 крайкаго левого столбг;а матрицы 25 а выходньл- и кaнaлa iИ - ер-тик ал ь и ые вь-жсдь 16 ячеек 6 пскладней строки треугольной г- атритды 2, При STfjM .комионенте произвольного (расширяемого) .вектора f соствгтстэует гор;;шог-1тальнь;й вход 7 пэрвс й ячзйки .Гм-(ш-1)1-и стро:.;к матрицы 2,j где га -- размерность произволькога 7 вектора. На (N-mj верхних горизонта ных входов 7 ячеек 6 крайнего левого столбца матрицы 2 подаются константы О, на m нижних горизонтальн входах 9 ячеек 6 крайнего левого столбца матрицы 2 - константы 1, а на (N-m) горизонтальных входов 9 константы О, В тех столбцах треугольной матри цы 2, где управляющий вектор z имеет нули, не может быть ячеек 6, в к торых произошло бы разветвление вни и, следовательно, на выходных каналах 16 последних ячеек 6 этих столб цов сохраняются нулевые логические уровни. Столбцы треугольной матрицы 2, которым соответствуют единицы управляющего вектора z, ведут себя следующим образом, Пусть в соответствии с управляющ вектором Z единичные логические уро ни поданы на граничные вертикальные входы 13 ячеек 6 j и так далее столбцов треугольной матрицы 2. Тог да, поскольку на все га нижних гориз тальных входов 9 ячеек 6 крайнего л вого столбца поданы константы I, ситуация одновременного наличия еди ничных логических уровней на входах 13 и 9 возникает в N-(m-l)-и ячей ке 6 j-|-ro стобца. Следовательно, си налы N-(m-1)J-ro и так далее входных каналов 7 направлены на вертикал ные вьгходы 16 последних ячеек 6 и так далее столбцов матрицы 2, что соответствует операции распгарения. В выполнении данной операции треугольная матрица 3 также не принимае участия. Режим сплетения. Сплетением называется операция , Zjq i 5 которая по двум произвольным векторам f и q м логическому вектору z строит вектор х такой, что компонента принимает значение очередной компоненты f, если z.0, либо очередной компоненты q, если z.1. Размерность вектора х совпадает с размерностью г и равна сумме размерностей f и При выполнении операции сплетения треугольная матрица 2 работает в режиме расширения вектора q управлякщи вектором Zj а треугольная матрица 3 в режиме расширения вектора f управпяюш м вектором z, при этом в матриц 2 верхние п строк не принимают участия Е реализации операции расшире38кия, так как на горизонтальные, входы 9 этих строк поданы константы О, а в матрице 3 - нижние m строк, так как на горизонтальные входы 9 этих строк поданы константы О. Сигналы, образующиеся на вертикальных выходах 16 ячеек 6 последней строки матрицы 2 и матрицы 3, одновременно поступают на элементы ИЛИ группы 4. Входными каналами коммутатора 1 при выполнении операции сплетения являются горизонтальные входы 7 ячеек 6 крайнего левого столбца матрицы 2, а выходными каналами - выходы 17 элементов ИЛИ группы 4. Режим перегруппировки. Перегруппировкой произвольного вектора f назьшается операция x «-f/Jz, где z - логический вектор, размерность которого равна {Зазмерности вектора f. Результат операции - произвольный вектор х, который в качестве п первых компонент х. содержит те компоненты f. исходного вектора f, которые соответствуют (), а в качестве m следующих компонент X - те компоненты f исходного вектора f, которые соответствуют (), где пит- соответственно количество единиц и нулей в логическом векторе z. Размерность вектора х совпадает с размерностью z и равна сумме п+т При вьЕполнении операции перегр шпировки матрица 2 работает в режиме сжатия вектора f логическим векторой Zj а матрица 3 - в режиме сжатия этого же вектора f логическим вектором z. Результирующий вектор второй операции сжатия сцепляется справа с результирующим вектором первой операции сжатия и, таким образом, получается результирукяций вектор операции перегруппировки. На горизонтальные входы 9 ячеек 6 крайнего левого столбца матрицы 2 подаЕотся логические фовни, соответствующие коду управлянлцего логического вектора z. Входными каналами ком1чутатора I при выполнении операции перегруппировки являются горизонтальные входы 7 ячеек 6 крайнего левого столбца матрицы 2, а выходными каналами - выходы 17 элементов ИЛИ группы 4, На горизонтальные входы 9 ячеек 6 крайнего пра:вого столбца матритды 3 с элементов НЕ группы 5 поаются логические уровни, соответствующие коду вектора z. 9 Наличие горизонтального входа 11 в каждой ячейке 6 коммутатора 1 позволяет выделять в полных треугол ных матрицах 2 и 3 треугольйые подматрицы меньших, размеров иорганизовать одновременную и независигчую работу подматриц, что значительно расширяет функциональные возможности коммутатора. Рассмотрим, каким образом с помощью горизонтальных входов 11 произ водится выделение треугольных подматриц в треугольной матрице 2 комMjiTaTOpa 1 . Пусть на горизонтальный вход 11 ячейки 6 крайнего левого столбца треугольной матрицы 2 подан нуле вой логическийуровень, а на все дру гНе горизонтальные входы 11 ячеек 6 этого столбца - единичные логические уровни. В этом случае в треугольной матрице 2 выделяются две независимые треугольные подматриц. .Логический вектор, имекщий q нулей; выделяет в треугольной матрице (q+1) независимых подматриц. Вьщеление из полной треугольной матриць независимых и изменяемых по размеру треугольных подматриц по воляет организовать в каждой из них свой рйжим работы, причем эти подматрицы могут работать одновремекно выполняя различные операции сжатия и расширения. Каждой треугольной подматрице, выделенной из треугольной матрицы 2, соответствует идентич нал смежная с ней по диагонали тре.угольная подматрица из треугольной матриць 3, т.е. образуется пара (идентичных тре тольных подматриц, одна из которых расположена в треу гапьной матрице 2, а дрзгая s тре угапьной матрице 3. Все пары выделен П10 ных треуголькьж подматриц могут работать одновременно и работа любой пары не зависит от работы других пар,, что позволяет в каждой из пар треугольных подматриц организовать свой режим работы причем работать эти пары будут одновременноа выполняя различные операции сплетения и перегруппировки Размеры пар треугольных подматриц можно оперативно изменять;, меняя код логического вектора. Свойство ком(утатора выполнять операции перегруппировки одновременно во всех определенным образом выде ляемых парах треугольных подматриц позволяет аппаратно реализовать процед фу сортировки (упорядочения) элементов массива. Предлагаемый коммутатор выполняет -широкий набор функций преобразова1шя массивов; сжатие расширение,, сплетешле, перегруппировку, упорядочение и др., Возможность разделения матрицы коммутатора на независимые подматрицы позволяет организовать параллельщчо работу всех подматриц, причем в стдегт.ьнЕ.ьх пoд arpицax могут одноЕременко выполняться различные операцш, Это обеспечивает хорошую загрузку устройствы: при одновременном решении набора задач с массивами различных размеров, Простота ячеек к соединения внутри матриц только с сссед11И1да ячейками обеспечивают высокую техначогш-гность и надежность при.производстве на основе интегральной техно.погии. Настройка и перестройка ком1-1ут тора. осущестЕЯяется кодачей ыа состав етс т вуюпр-хз внешние входы отравляющих двоичных векторов Такая настройка осуществляется с очень высот-ой скс-ростью.