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

Союз СоаетскивСоциалистическикВеспублик ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(22) Заявлено 090377 (21) 2461268/18-24с присоединением заявки Мо(23) Приоритет -1) М. С 06 Г. 7/00 Госуда рственный комСССРелам изобретеи открытий оо 3) УДК 681. 32Опубликовано 25 Л 5,79, Бюллетен Дата опубликования описания 2 М 19 5. 2) Автор: изобретени(71) Заявител нститут математики СО АН ССС 54) ЯЧЕИКА ОДНОРОДНОИ СР Изобретение относится к областидискретной вычислительной техники и предназначено для логической обработки информации.Известны ячейки однородной среды для логической обработки двоичных векторов, например для подсчета количества единиц в заданном двоичном векторе 111. Недостатком их является невозможность коммутации каналов в соответствии с заданным управляющим двоичным вектором.Наиболее близким техническим решением к данному является ячейка однородной среды, содержащая элементы 15 И, ИЛИ, НЕ, причем первый вход ячейки соединен с первым входом первого элемента И и с первым выходом ячейки, второй вход ячейки соединен со вторый входом первого элемента И, с 20 первым входом второго элемента И, выход которого является вторым выходом ячейки, и, через первый элемент НЕ - с первым входом третьего элемента И, третий вход ячейки соединен с третьим входом первого элемента И, со вторым входом третьего элемента И, выход которого является третьим выходом ячейки, и через второй элемент НЕ - со вторым входом второго элемен-З 0 та И, четвертый вход ячейки соединенс первым входом первого элемента ИЛИ,второй вход которого соединен с выходом первого элемента И, а выход является четнертым ныходом ячейки,пятый вход ячейки соединен с первымвходом второго элемента ИЛИ, выходкоторого является пятым выходомячейки 121,Недостатком известного устройстваявляется узкая специализация: каждоеустройство выполняет лишь некоторыеотдельные операции обработки логических векторов. Цель настоящего изобретения - расширение класса решаемых задач эа счет реализации коммутации в соответстнии с управляющим вектором,Эта цель достигается тем, что в ячейку однородной среды введен четвертый элемент И, входы которого соединены со вторым, третьим и четвертым входами ячейки, а выход - со вторым входом второго элемента ИЛИ.На фиг. 1 изображена структурная схема однородной среды; на фиг. 2 функциональная схема ячейки.Двумерная однородная структура выполнена в виде матрицы одинаковых(1) (2) (3) (4) жение -Й единицы,и одинаково между собой соединеяиых ячеек,Применяются Обозначения: входы 2,3,4,5,6 переменных у,3,1,Г,х соответственно и выходы 7,8,9,10,11 переменных у, к, С, Е, хсоответственно. Выходы 8 и 10 каждой ячейки 5 соединены со входами 3 и 5 соседней по горизонтали, а выходы 7,9 и 11 со входами 2,4 и б соседней по вертикали ячейки соответственно.Ячейка 1 содержит элементы И 12,13,0 14 и 15, элементы ИЛИ 16 и 17 и элементы НЕ 18 и 19.Из, функциональной схемы ясно, что ячейка 1 реализует следующие логические функции: 15е=кЕС =1 гй =Е+з 1 ун =х+з 1 Г 20Благодаря такой конструкции двумерная однородная структура обеспечивает выполнение следующих операций1. Подсчет количества единиц взаданном логическом векторе,2. Определение положения к-й единицы в заданном логическом векторе.3. Соединение любой упорядоченной в-ки входных каналов (иэ п) с ввыходными каналами в соответствии сзаданным управляющим логическим век- ЗОтором (сжатие, сжимающая коммутация)4. Соединение а входных каналовс любой упорядоченной в-кой (иэ и)выходных каналов (расширение, расширяющая коммутация), 35Предлагаемая двумерная ОднОРоднаяструктура работает следующим образом.Заданный логический вектор подается поразрядно на входы 3 ячеек левойграницы матрицы, На входы 4 всех ячеек верхней границы матрицы подаютсяконстанты 1 = 1,Очевидно, что при этом потенциалыв точках 20 ячеек 1-го (левого) столбца матрицы соответствуют значениямОдноименных разрядов заданного логического вектора. Потенциалы в точках21 ячеек этого столбца имеют значение 11 до тех пор, пока не встретится некоторая 1, -я ячейка, соответствующая первой единице заданноговектора. Иэ (2) следует, что во всехячейках, расположенных ниже 1 -й, потенциалы в точках 21 будут иметь значение О, независимо от содержимого заданного вектора. Вследствие 55Этого, согласно (1), на выходах 8 .ячеек первого столбца будет продублирован заданный вектор, за исключениемего первой единицы, которая заменяется нулем. Этот ффостатак исходного 60вектора поступает на входы 3 ячеек2-го столбца матрицы.При этом 1 -я ячейка являетсяединственной ячейкой 1-го столбца,в которой выполняется условие к=1,4Аналогичные преобразОвания проис.ходят во 2-м, 3-м и т,д. столбцахматрицы: в некоторой 1 -Й, 1 -й ит.д. ячейках 2-го, 3-го и Т.1, столб"цов выделяются вторая, третья и т,д,единицы заданного логического вектора,Рассмотренный процесс выделенияОчоредных сдиниц Обеспечивает выполнение всех описанных ниже операций .1. Подсчет количества единиц.Дпя выпОлнения этОЙ Операции навходы 5 всех ячеек левой границыматрицы подаются константы К=1, а навходы б всех ячеек верхней границы -константы х=О.Пои этом, согласно (3), во всехячейках матрицы Г.=1, и выражение (4)принимает видКак было показано выше, условиек=1 выполняется в каждом столбцематриц, начйная с 1-го (левОго),только в одной ячейке - соответствующей первОй сверху единице исходноговектора или его остатка, Значит,если висходном векторе содержитсяединиц, то условие вам=1 будет выполнено в точности в 1 левых столбцах. Во всех остальных (расположенных правее) столбцах матрицы ситуация к=1 возникнуть не может,Поскольку на входы б верхней границы поданы кОнстанты х=Ор сигналына выхОдах 11 нижней границы примутзначение х =1 только в 1 левых столбцах.Итак, выходы х нижней границыпредлагаемой двумерной однороднойструктуры образуют фшкалу, по которой непосредственно отсчитываетсяколичество единиц, содержащихся взаданном логическом векторе.2. Определение положения К-й едйницы,,Для выполнения этой операции навходы 5 всех ячеек левой границыматрицы подаются константы Г=О, навходы 2 верхней границы во всехстолбцах, кроме К-го, подаются сигналы у=О, а в к-и столбце у=1,При этом, согласно (3), во всехячейках к-го Столбца Г й+з 1, Бо условие гав=1 выполняется в единственной ячейке к-го столбца, а именно,в ячейке, находящейся в строке, соответствующей к-й единице исходного вектора. В этой единственной ячейке возникает сигнал Г" =1, который в соответствии с (3) сохраняется далее до праной границы матрицы. Значит сигнал 1 =1 появляется на выходе 10 праной границы матрицы в .единственной строке, соответствующей к-й единице заданного логического вектора,Следовательно, выходы й правОй границы матрицы образуют шкалу, по которой после подачи в к-й столбец запроса у=1 отсчитывается полобб 41 б 9цала, в 1 -й сигналы 2-го входногокакала и т,д.Таким образом, выходы Г правойграницы матрицы являются в данномслучае выходными каналами и устройство осуществляет расширяющую коммута 5 циюПредлагаемая двумерная однороднаяструктура может найти применение вразличных универсальных и специализированных устройствах цифровой тех)О ники.Одно из возможных применений - ныполнение логических операций при аппаратурной реализации языков высокого уровня и различных Функций мате)5 матического обеспечения ЦВМ. ШирокиеФункциональные возможноси предлагаемой структуры и большая скоростьвыполнения операций могут способстновать увеличению эффективности всейсистемы.Другое применение предлагаемойструктуры - коммутация сообщений нцифровых устройствах и в системахсвязи. В этом случае дополнительнымпреимуществом является большая скорость перестройки: для изменениякоммутации достаточно подать на вхо"ды матрицы новый управляющий вектор.Предлагаемую структуру можно использовать также для эффектйвной реа 30 лизации произвольной коммутации иканалов (при условии, что в каждыймомент времени необходимо обслужи-.вать не более, чем в из и каналов) .Для этого достаточно построить схему35 из трех последовательно включенйыхблоков: сжимающий коммутатор размера и х в, полный коммутатор размерав х в, расширяющий коммутатор размера в х и. При этом размеры полно 4 О го коммутатора (который может бытьвыполнен по любой известной схеме)уменьшаются от и х и до в х в, чтоупрощает коммутирующее устройство ицелом. Формула изобретени я 3. Сжатие (сжимающая коммутация)Задача, которую решает устройствов этом случае, состоит н соединениилюбой упорядоченной в-ки входных каналон (иэ общего числа и) с в выходными каналами .Номера подлежащих переключениювходных каналов 11 ,..,1,(1, с 1 с1,) указываются и-Разрядным логическим вектором, которыйсодержит единицы н соответствующихэтим номерам разрядах (управляющийвектор) .и входных каналов подключаютсяпоразрядно ко входам 5 левой границы матрицы, На входы 2 всех ячеекверхней границы подаются константыу=о.При этом согласно (3) во всехячейках матрицы Е=Е и сигналы, поступающие на нходцые каналы, распространяются по цепям Г вдоль соответствующих строк матрицы.Кроме того, на входы б всех ячеекверхней границы матрицы подаются константы х=О. Поэтому н любой ячейке,где выполняется условие з 1=1, согласно (4) х=Г, то есть происходит поворот сигнала из горизонтальной цепи Гв вертикальную цепь х.В соответствии со структурой управляющего вектора н 1-м (левом)столбце матрицы ситуация з 1=1 возникает в 1, -й строке, во 2-м в 1 -й ит.д. Следовательно на выходы 11 нижней границы матрицы будут направленыв 1-м столбце сигналы 1 -го входногоканала, во 2-м сигналы 1 -го входного канала и т.д,Таким образом, выходы х нижнейграницы матрицы янляются в данномслучае выходными каналами и устройство осуществляет сжимающую коммутацию4Расширение (расширяющая коммутация) .Задача, которую решает устройствов этом случае, состоит в соединениив упорядоченных входных каналов с любой упорядоченной в-кой выходных каналов (из общего числа и) .Номера выходных каналов 1, .121 (1, с 1 сс 1 ), к которйм долж"нй бйть йодключеньт входные каналы1,2, ,в задаются и-разрядным управзияющим вектором, которцй содержитВдиницы в соответствующих разрядах.в входных каналов подключаютсяпоразрядно к входам у верхней гра-ницы матрицы. На входы 5 всех ячеек 55левой границы матрицы подаются константы Я=О.При этом в любой ячейке, где выполняется условие яС.=1, согласно (3)й=у, то есть происходит поворот сйг- бОрала из вертикальной цепи у в горизонтальную цепь К,Очевидно на выходы 10 правой границы матрицы будут направлены: н-й строке сигналы 1-го входного кас 65 Ячейка однородной среды, содержащая элементы И, ИЛИ, НЕ, причем первый вход ячейки соединен с первым входом первого элемента И и с первым выходом ячейки, второй вход ячейки соединен со вторым входом первого элемента И, с первым входом второго элемента И, выход которого является Вторым выходом ячейки, и, через первый элемент НЕ - с первым входом третьего элемента И, третий вход ячейки соединен с третьим входом первого элемента И, со вторым входом третьего элемента И, выход которого.является третьим выходом ячейки, и через второй элемент НЕ - со вторым входом второго элемента И, четвертый вход ячейки соединен с первым664169 Составитель в. Техред Н. Андр едакто ерц аказ 3001/46 Тираж 779 ЦНИИПИ Государстненног по делам изобретений 13035, Москва, Ж, РаушПодписноекомитета СССРи открытийская наб., д . 4/ П Патент, г. Ужгород, улПроектная фили 7с 4входом. первого элемента ИЛИ, н т орой вход которого соединен с выходом и ер ного элемента И, а выход явля ет с я четвертым выходом я чейки, и ятый вход ячей ки соединен с первым нходом нт орого эл емента ИЛИ, выход которого янляется пятым выходом ячейки, о т - 5 л и ч а ю щ а я с я тем, что, с целью расширения класса ркааемых задач за счет реализации коммутации в соотнетствии с управляющим вектором,в ячейку введен четвертый элемент И,входы которого соединены со вторым,третьим и четвертым входами ячейки,а выход - со вторым входом второгоэлемента ИЛИ.Источники информации, принятые вовнимание при экспертизе1. Авторское свидетельство СССРР 304567, кл. 6 06 Г 7/04, 15.09.69,2, Авторское свидетельство СССРР 590747, кл, С 06 Г 7/00. Пу ырев чук Корректор С, Патрушева