Ячейка однородной среды

Ячейка однородной среды

Иллюстрации

Показать все

Реферат

 

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.