Ячейка однородной среды
i
Союз Соаетскив Социалистическик Веспублик ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. саид-ву (22) Заявлено 090377 (21) 2461268/18-24 с присоединением заявки Но (23) Приоритет— (51)М. Кл.2 G 06 F. 7/00 Государственный комите СССР ио делам изобретений и открытий Опубликовано 2505,79, Бюллетень М 19 (53) УДК 681. 327 (088.8) Дата опубликования описания 28.05.79 (72) Автор: изобретения Я. И. Фет (71) ЗаяВИтЕЛЬ Институт математики CO AH СССР (54) ЯЧЕИКА ОДНОРОДНОИ СРЕДЫ Изобретение относится к области дискретной вычислительной техники и предназначено для логической обработки информации. Известны ячейки однородной среды для логической обработки двоичных векторов, например для подсчета количества единиц в заданном двоичном векторе (1). Недостатком их является невозможность коммутации каналов в соответствии с заданным управляющим двоичным вектором. Наиболее близким техническим:решением к данному является ячейка однородной среды, содержащая элементы15 И, ИЛИ, НЕ, причем первый вход ячейки соединен с первым входом первого элемента И и с первым выходом ячейки, второй вход ячейки соединен со вторым входом первого элемента И, с первым входом второго элемента И, выход которого является вторым выходом ячейки, и, через первый элемент НЕ— с первым входом третьего элемента И, третий вход ячейки соединен с третьим входом первого элемента И, со вторым входом третьего элемента И, выход которого является третьим выходом ячейки, и через второй элемент НŠ— со вторым входом второго элемен-ЗО та И, четвертый вход ячейки соединен с первым входом первого элемента ИЛИ, второй вход которого соединен с выходом первого элемента И, а выход является четнертым ныходом ячейки, пятый вход ячейки соединен с первым входом второго элемента ИЛИ, выход которого является пятым выходом ячейки (2). Недостатком известного устройства является узкая специализация: каждое устройство выполняет лишь некоторые отдельные операции обработки логических векторов. Цель настоящего изобретения — расширение класса решаемых задач эа счет реализации коммутации в соответстнии с управляющим вектором. Эта цель достигается тем, что в ячейку однородной среды введен четвертый элемент И, входы которого соединены со вторым, третьим и четвертым входами ячейки, а выход — со вторым входом второго элемента ИЛИ. На фиг. 1 изображена структурная схема однородной среды; на фиг. 2 функциональная схема ячейки. Двумерная однородная структура выполнена в виде матрицы одинаковых бб 4169 (1) (2) (3) (4) жение k-Й единицы. и одинаково между собой соединенных ячеек. Применяются обозначения: входы 2, 3, 4, 5, б переменных у, 3, t, f,õ соответственно и выходы 7, 8 9, 10, 11 переменных y, z, t, f, x соответственно. Выходы 8 и 10 каждой ячейки соединены со входами 3 и 5 соседней по горизонтали, а выходы 7,9 и ll co входами 2,4 и б соседней по вертикали ячейки соответственно. Ячейка 1 содержит. элементы И 12,13,0 l4 и 15, элементы ИЛИ 16 и 17 и элементы HE 18 и 19. Из, функциональной схемы ясно, что ячейка 1 реализует следующие логические функции: I5 и =zE t =tz f =f+zty х =x+ztf Благодаря такой конструкции двумерная однородная структура обеспечивает выполнение следующих операций 1. Подсчет количества единиц в заданном логическом векторе. 2. Определение положения к-й единицы в заданном логическом векторе. 3. Соединение любой упорядоченной m-ки входных каналов (иэ n) с m выходными каналами s соответствии с заданным управляющим логическим век- ЗО тором (сжатие, сжимающая коммутация) 4 ° Соединение m входных каналов с любой упорядоченной m-кой (иэ n) выходных каналов (расширение, расширяющая коммутация) . 35 Предлагаемая двумерная однородная структура работает следующим образом. Заданный логический вектор подает« ся поразрядно на входы 3 ячеек левой границы матрицы. На входы 4 всех яче- 4О ек верхней границы матрицы подаются константы t = 1. Очевидно, что при этом потенциалы в точках 20 ячеек 1-ro (левого) столбца матрицы соответствуют значениям одноименных разрядов заданного логического вектора. Потенциалы в точках 21 ячеек этого столбца имеют значение 1 до тех пор, пока не встретится некоторая 1, -я ячейка, соответствующая первой единице заданного вектора. Иэ (2) следует, что во всех ячейках, расположенных ниже l -й, поI тенциалы в точках 21 будут иметь значение О, независимо от содержимого заданного вектора. Вследствие этого, согласно (1), на выходах 8 . ячеек первого столбца будет продублирован заданный вектор,: за исключением его первой единицы, которая заменяется нулем. Этот остаток исходного g) вектора поступает на входы 3 ячеек 2-го столбца матрицы. При этом 1 -я ячейка является ! единственной ячейкой 1-го столбца, в которой выполняется условие zt=l. Аналогичные преобразования происходят во 2-м, 3-м и т.д. столбцах матрицы: в некоторой 1 -Й, 1 -й и т.д. ячейках 2-го, 3-го и т.д. столб" цов выделяются вторая, третья и т,д, единицы заданного логического вектора, Рассмотренный процесс выделения очередных единиц обеспечивает выполнение всех описанных ниже операций „ l. Подсчет количества единиц. Для выполнения этОЙ операции На входы 5 всех ячеек левой границы матрицы подаются константы f-=l, а на входы б всех ячеек верхней границы— константы х=о. П и этом, согласно (3), во всех ячейках матрицы f=-l, и выражение (4) принимает вид х = x+zt Как было показано выше, условие zt.=-1 выполняется в каждом столбце матрицы, начйная с 1-Го (lleBQI o) только в одной ячейке — соответствующей первОЙ сверху единице исходного вектора или его остатка, Значит, если в исходном векторе содержится единиц, то условие zt-1 будет выполнено в точности в 1 левых столбцах. Во всех остальных (расположенных правее) столбцах матрицы ситуация zt=l возникнуть не может. Поскольку на входы б верхней границы поданы константы х=0 сигналы на выходах 11 нижней границы примут значение х =1 только в R левых столбцах. Итак, выходы х нижней Границы предлагаемой двумерной однородной структуры образуют шкалу, по которой непосредственно отсчитывается количество единиц, содержащихся в заданном логическом векторе. 2. Определение положения k-й едйницы ,Для выполнения этой операции на входы 5 всех ячеек левой границы матрицы подаются константы f=.О, на входы 2 верхней границы во всех столбцах, кроме k-го, подаются сигналы у=О, а в k-и столбце у †. При этом, согласно (3), во всех ячейках k-го Столбца f f+zt. Ho ycловие zt=l выполняется в единственной ячейке k-го столбца, а именно, в ячейке, находящейся в строке, соответствующей k-й единице исходного вектора. В этой единственной ячейке возникает сигнал f =1, который B co ответствии с (3) сохраняется далее до правой границы матрицы. Значит сигнал f =1 появляется на выходе 10 правой границы матрицы в .единственной строке, соответствующей k-й единице заданного логического вектора. Следовательно, выходы f правОЙ границы матрицы образуют шкалу, по которой после подачи в k-й столбец запроса у=l отсчитывается поло6641б9 нала, в 1 -й сигналы 2-ro входного канала и т,д. Таким образом, выходы f правой границы матрицы являются в данном случае выходными каналами и устройство осуществляет расширяющую коммута5 цию. Предлагаемая двумерная однородная структура может найти применение в различных универсальных и специализированных устройствах цифровой тех@ ники. Одно из возможных применений — выполнение логических операций при аппаратурной реализации языков высокоr0 уровня и различных Функций математического обеспечения ЦВМ. Широкие Функциональные возможности предлагаемой структуры и большая скорость выполнения операций могут способствовать увеличению эффективности всей системы. Другое применение предлагаемой структуры — коммутация сообщений в цифровых устройствах и в системах связи. В этом случае дополнительным преимуществом является большая скорость перестройки: для изменения коммутации достаточно подать на вхо ды матрицы новый управляющий вектор. Предлагаемую структуру можно использовать также для эффектйвной реа30 лизации произвольной коммутации и каналов (IIpH условиир что B каждый момент времени необходимо обслужи+ вать не более, чем m из и каналов) . Для этого достаточно построить схему 55 из трех последовательно включенйых блоков: сжимающий коммутатор размера и х m, полный коммутатор размера m x m расширяющий коммутатор размера m х п. При этом размеры полно40 го коммутатора (который может быть выполнен по любой известной схеме) уменьшаются от и х п до m x m что упрощает коммутирующее устройство в целом. Формула изобр етени я 3. Сжатие (сжимающая коммутация) Задача, которую решает устройство в этом случае, состоит в соединении любой упорядоченной m-ки входных ка налов (из общего числа n) с m выходными каналами. Номера подлежащих переключению входных каналов 1,,1,...,1 (1, с 1 e .... .1 ) указываются и-раз рядным логическим вектором, который содержит единицы в соответствующих этим номерам разрядах (управляющий вектор) . и входных каналов подключаются поразрядно ко входам 5 левой границы матрицы. На входы 2 всех ячеек верхней границы подаются константы у=о. При этом согласно (3) во всех ячейках матрицы f =-f и сигналы, поступающие на входные каналы, распространяются по цепям f вдоль соответствующих строк матрицы. Кроме того, на входы б всех ячеек верхней границы матрицы подаются кон станты х-0. Поэтому в любой ячейке, где выполняется условие zt=l соглас но (4) х =f, то есть происходит пово рот сигнала из горизонтальной цепи в вертикальную цепь х. В соответствии со структурой управляющего вектора в 1-м (левом) столбце матрицы ситуация zt=l возни» кает в i, -й строке, во 2-м в i -й и т.д. Следовательно на выходы 11 нижней границы матрицы будут направлены в l-м столбце сигналы i -го входного 4 канала, во 2-м сигналы i -го входного канала и т.д. Таким образом, выходы х нижней границы матрицы являются в данном случае выходными каналами и устройст во осуществляет сжимающую коммутацию 4 ° Расширение (расширяющая коммутация) . Задача, которую решает устройство в этом случае, состоит в соединении m упорядоченных входных каналов с mo» бой упорядоченной m-кой выходных каналов (из общего числа n) . .Номера выходных каналов 1 1 (1 < 1 4 ° ° ° < 1 )q к RQTDpHM Долж нй бйть йодключенЬт входные каналы 1,2,,m задаются и-разрядным управляющим вектором, который содержит вдиницы в соответствующих разрядах. m входных каналов подключаются поразрядно к входам у верхней границы матрицы. На входы 5 всех ячеек 55 левой границы матрицы подаются константы f=0. При этом в любой ячейке, где выполняется условие zt--l, согласно (3)i f ó, то есть происходит поворот сйг- 50 нала из вертикальной цепи у в горизонтальную цепь f, Очевидно на выходы 10 правой границы матрицы будут направлены: в -й строке сигналы l-ro входного кас 65 Ячейка однородной среды, содержащая элементы И, ИЛИ, НЕ, причем первый вход ячейки соединен с первым входом первого элемента И и с первым выходом ячейки, второй вход ячейки соединен со вторым входом первого элемента И, с первым входом второго элемента И, выход которого является Вторым выходом ячейки, и, через первый элемент НŠ— с первым входом третьего элемента И, третий вход ячейки соединен с третьим входом первого элемента И, со вторым входом третьего элемента И, выход которого является третьим выходом ячейки, и через второй элемент НŠ— со вторым входом второго элемента И, четвертый вход ячейки соединен с первым 664169 ° ° в ° ° е ° ° ° Rue I Составитель в. Пузырев Техред Н. Андрейчук Корректор С. Патрушева Редактор Б. Герцен Заказ 3001/46 Тираж 779 Подписное ЦНИИПИ Государстненного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д . 4/5 Филиал ППП Патент, г. Ужгород, ул ° Проектная, 4 7 с4 входом. и ерно го элемента ИЛИ, н т орой вход .к старого соединен с выход ом п ер-ного элемента И, а выход явля ет с я четвертым выходом я чейки, и ятый вход я чей ки соедин ен с первым нходом нт орого эл емент а ИЛИ, выход которого я нл я ет с я пятым выходом яч ей ки, о т л и ч а ю щ а я с я т ем, что, с целью расширения класса решаемых задач за счет реализации коммутации в соотнетствии с управляющим вектором, в ячейку введен четвертый элемент И, входы которого соединены со вторым, третьим и четвертым входами ячейки, а выход — со вторым входом второго элемента ИЛИ. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР Р 304567, кл. G 06 F 7/04, 15.09.69. 2, Авторское свидетельство СССР Р 590747, кл. G 06 F 7/00.
