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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Северо-Западный заочный политехнический институт(56) Авторское свидетельство СССР У 851398, кл.С 06 Р 7/00, 1978.Авторское свидетельс тво СССР У 1013943, кл.С 06 Р 7/00, 1982, (54) ЯЧЕЙКА ОДНОРОДНОЙ СТРУКТУРЫ (57) Изобретение относится к цифровой вычислительной технике и предназначено для массовой параллельной обработки информации. Целью изобретения является расширение функциональных возможностей за счет выполненияопераций перемещения данных. Ячейкаоднородной среды содержит триггер 12,элементы НЕ 24,25,31,32 элементыИ 13-20,26,27,29, элементы ИЛИ 2 в23, 28,30, входы 1-6, выходы 7-11.Устройство работает в различных режимах в зависимости от значений управляющих сигналов К и И. Устройствовыполняет: 1) информационный поиск,включающий поиск максимального элемента, поиск минимального элемента,разбиение массива на три подмножества; 2)преобразование структур, включающее расширение, сжатие, взвешивание;3) перемещение данных, включающеезапись информации в столбец, сдвигданных. 1 ил.ры.Ячейка имеет входы 1 -6 ,г,х, у,ч,ц соответственно), выходы 7- 11 (г ,х,у ,ч ,ц соответственно), триггер 12, элементы И 13-20, элеФ менты ИЛИ 21 -23, элементы НЕ 24 и 25, элементы И 26 и 27, элементы ИЛ 28, И 29, ИЛИ 30, НЕ 31 и 32.В однородной структуре выходы 8 и 9 ячейки соединены с входами 3 и 4 соседней по вертикали ячейки соответственно, а выходы 7,10 и 11 с входами 2,5 и 6 соседней ячейки по горизонтали соответственно.Ячейка однородной структуры реализует функции х = х ч г а 1 сг 1 с; г = г ас чгу 1 с у гхЬл ч 1 сца; (2)(5) цу 1 ч ц 1 г,состояние триггера 12;сигналы установки триггера 12 в "1" "О" где а Ч 1 1 Чо 1 с,г,хуу управляющие сигналы навходах 1-6 ячейки; 1 (г ,х ,уч,ц - сигналы на выходах 7-11ячейки.Ячейка однородной структуры работает следующим образом,Функции (4) и (5) позволяют осуществить парафазную запись информации в триггеры 12 строки однороднойструктуры. Для этого прямой кодзаписываемого двоичного слова подается поразрядно на входы 3 ячейки,а обратный код - на входы 4 ячейкисоответствующих столбцов однороднойструктуры, Одновременно на входы 6 Изобретение относится к цифровой вычислительной технике и предназначено для массовой параллельной обработки информации.Целью изобретения является расширение функциональных воэможностей за счет выполнения операций перемещения данных.На чертеже приведена функциональная схема ячейки однородной структу всех ячеек выбранной строки подается импульс разрешения записи, а навходы 1 - нулевой сигнал,5Устройство может работать в различных режимах, в зависимости отзначения управляющего сигнала 1 иуправляющего сигнала ц,В режиме информационного поиска10 на входы 1 всей ячеек однороднойструктуры подается управляющий сигнал 1 = О, а на входы 6 - управляющий сигнал ц = О. Функции (1) - (3)принимают вид:15(2) (3) х =хч га; г = г(ач у)1 ч = чч гау. но, то по окончанию переходных процессов сигнал г = 1 на выходах 7 ячеек правого столбца установится 40 в тех строках, которые содержатмаксимальные элементы информации,Поиск минимального элемента. Выполняется аналогично предыдущему,если все элементы массива записаны 45 в триггерах 12 обратным кодом,Разбиение массива на три подмножества. Для выполнения этой операции массив записывается так же, какпри поиске максимального элемента.Признак сравнения подается поразрядно на входы 4 верхних ячеек соответственно в столбцы в обратном коде.Если теперь подать на входы 2 и 5всех ячеек левого столбца граничныесигналы г=1, ч=О соответственно, топо окончании переходных, где содержатся элементы, большие заданногопризнака, установятся сигналы ч= 1,если меньшие заданного признака 20При этом ячейки однородной структуры обеспечивают выполнение в однородной структуре следующих информационно-логических операций.25 Поиск максимального элемента. Длявыполнения этой операции элементы обрабатываемого массива должны бытьпредварительно записаны по строкам,старшими разрядами слева, в тригге рах 12 однородной структуры. Еслитеперь в каждом столбце соединитьчерез элемент НЕ выходы 8 и 9 нижней ячейки и подать на входы 2 всехячеек левого столбца и на входы 3всех ячеек верхней строки граничныесигналы г = 1 и х = О соответствен 372322сигналы ч= О и г = О, совпадающие с признаком - сигналы ч = О и г= 1,В режиме преобразования структур данных на входы 1 всех ячеек однородной структуры подаются управляющие сигналы 1 = 1 и и = О.Функции- (5) принимают вид:х =хуг;(4 )о- фа =а (5 )Если при этом подать на входы 2 всех ячеек левого столбца произвольный двоичный вектор, а на входы 3 всех ячеек верхней строки - граничные сигналы х = О, то в первом (левом) столбце однороднои структуры выделится (условием гх = 1) первая сверху единица исходного двоичного вектора, во втором столбце - вторая его единица, и т.д. Действительно, в первом (левом) столбце согласнопеременная х сохраняет значение "О до тех пор, пока г=О. В некоторой 1-й ячейке, где впервые встречается г = 1, х меняет значение на "1" и сохраняет до нижней границы. Значит, это единственная ячейка первого столбца, в которой выполняется условие гх=1. Горизонтальный канал г выделенной 1-й ячейки в соответствии с (2 ) заперт сигналом х=О, поэтому первая "1" исходного двоичного вектора далее по горизонтали не распространяется. Во всех ячейках первого столбца, расположенных ниже 1, -й ячейки, х=1 и, следовательно, г= г. Значит, на входы 2 второго столбца поступает копия исходного двоичного вектора за исключением его первой (верхней) единицы. Аналогичные преобразования происходят во втором, третьем и т.д. столбцах однородной структуры: в некоторой 1-й ячейке второго столбца вьщеляется (условием гх=1) вторая "1" исходного вектора, в 1 -й ячейке третьего столбца - третья "1" и т.д, При ЭТОМ ОЧЕВИДНО 1, с 1 с 1 сРассмотренное свойство последовательного выделения очередных единиц и наличие функции 3) обеспечивает выполнение следующих операцийпреобразования структур данных.Расширение. Задача, которую решает устройство в этом случае, состоит в соединении щ упорядоченныхвходных каналов с любой упорядоченной группой щ выходных каналов изобщего числа п). Номер входных кана О лов 11171 1 (1 1 . 1 с)к которым должны быть подключенывходные каналы 1,2 ., задаютсяи-разрядным двоичным вектором, содержащим "1" в соответствующих раз рядах (управляющий вектор). Этотвектор подается поразрядно на входы2 яеек левой границы однороднойструктуры, щ входных каналов подключаются поразрядно к входам 2 О ячеек верхней границы. На входы 5ячеек левой границы подаются граничные сигналы ч, = О. При этом в каждойячейке однородной структуры, гдевыполняется условие гх=1, в соответ 625 ствии с (3 ) имеет место ч = у,т.е.происходит поворот сигнала иэ вертикального канала у в горизонтальныйканал ч. Очевидно, при этом на выходы 10 ячеек правой границы будутнаправлены в 1,-й строке сигналы1-го входного канала, в 1-й строке - сигналы 2-го канала и т.д.,что соответствует решаемой задаче.Сжатие. Задача, которую решаетустройство в этом случае, состоит всоединении любой упорядоченной группы входных каналов (из общего числаи) с щ последовательными выходнымиканалами. Номера входных каналов 40 112(1 с 1 г 1 З)торые должны быть подключены к выходным каналам 1,2щ, задаются и-разрядным двоичным вектором,содержащим "1 в соответствующих раз разрядах. В данйом случае этот управляющий вектор подается в обратномкоде на входы 3 ячеек верхней границы однородной структуры, и входных каналов подключаются поразряднок входам 4 ячеек верхней границы. Навходы 2 и 5 всех ячеек левой границыподаются соответственно граничныесигналы г=1 и ч = О. При этом втех столбцах, где управляющий вектор 55содержит "О", х=1. Значит, в столбцах не может быть выделенных ячеек.Остальнь:е столбцы ведут себя следующим образом. Пусть в управляющемвекторе, единицы расположены на 1, -й, 1372322(1 ) (2 ) (3 ) 45 (4 ) (5" ) ХЧ 21 а; ч ч гху; ч гаС=г2 Таким образом, настройка ячеек однородной структуры на выполнение функций (1 ) - (5 ) обеспечивает возможность записи в триггеры этих ячеекинформации, поступающей н них повходу 2, и одновременно с этим формирование на выходе 7 значения состояния триггера соответствующей ячейки н предыдущий такт работы однородной структуры. Это свойство обеспе 12 -й и т.д. позициях. Так как 2=1,условие гх=1 согласно ( ) и (2 ) возникает в 1, -й слева ячейке 1-й строки, 1 -й слева ячейке 2-й строки и т.д., следовательно, сигналы 1 12-го и т.д. входных каналов будут направлены на выходы 10 ячеек правой границы в 1,2-й и т.д, строках, что соответствует 1 О решаемой в данном случае задаче.Взвешивание (подсчет количества единиц в двоичном векторе). Вектор- аргумент подается в обратном коде на входы 3 ячеек верхней границы. На 5 все входы 2 ячеек левой границы и входы 4 ячеек нерхней границы подаются соответственно граничные сигналы 21 и у =1. Если в векторе-аргументе содержится 1 единиц, то условие 20 гх=1 будет выполняться в точности в 1 первых строках однородной структуры. Во всех остальных, расположенных ниже, строках условие гх= возникнуть не может. Значит, сигналы у=1 будут направлены в каналы ч только н первых 1 строках. Следовательно, выходы 10 яеек правой границы образуют в данном случае шкалу, по которой считывается вес (количество единиц) 30 заданного двоичного вектора.В режиме перемещения данных на входы 6 всех яеек однородной структуры подается сигнал и=1, а на входы 1 ячеек, настраиваемых на работу в 35 указанном режиме - кратковременный сигнал к=1. При этом ячейки, на которые подаются сигналы настройки ц= =с=1, реализуют функции (1) в (5) в виде: 40(4 ) (5 ) ц(= х оТаким образом, в соответствии с (1 ) - (5" ) двоичный вектор, подаваемый на входы 2 ячеек крайнего левого столбца однородной структуры, без изменения поступает на входы 2 ячеек 1-го столбца и в соответствии с (1 )-(5 ) заносится в триггеры 12 этих ячеек при поступлении импульса записи 1=1 по входу, что и требуется для решения поставленной задачи.Следует отметить, что при подаче сигнала 1=1 на входы 1 всех ячеек однородной структуры будет выполнена запись нходного двоичного вектора, параллельно во все столбцы однородной структуры.Сдвиг данных, Задача, которую решает устройство в данном случае, заключается в записи н каждую (1, 3)-ю ячейку однородной структуры (111) значения состояния (1-1,3)-й ячейки, чем достигается сдвиг данных, хранящихся н ячейках однородной чивает выполнение следующих операций в однородной структуре.Запись информации в столбец. Задача, которую решает устройство в данном случае, состоит н записи в некоторый 1-й столбец однородной структуры п-разрядности дноичного вектора, поступающего на вторые входы . ячеек крайнего левого столбца однородной структуры. Для решения этой задачи на входы 2 ячеек крайнего левого столбца однородной структуры подается п-разрядный двоичный вектор, на входы 6 которых подается также сигнал и=1, на входы 4 всех ячеек однородной структуры - сигнал у=1, на входы 1 ячеек 1-го столбца однородной структуры, в которых выполняется запись исходно двоичного вектора, подается импульснь 11 й сигнал 1=1. В результате такой настройки в ячейках 1-го столбца реализуются функции (1" ) - (5 ),а в остальных ячейках однородной структуры - функции (1-5) в ниде:1372322 1 О 15 20 25 30 35 40 структуры и один ра зряд лира во.Для реализации этои задачи на входы 1 всех ячеек однородной структуры подается сигнал Е=,ца входы 6 ячеек крайнего левого столбца подается импульс ц=,при этом на выходах 7 каждой ячейки однородной структуры формируется значение состояния триггера этой ячейки, которое по входу 2 поступает в соседнюю ячейку и заносится в ее триггер. Длительность импульса и=1 при работе однородной структуры в данном режиме соответственно должна быть равна 2 Я, +2 с + ь гдес:,соответственно времена задержки сигналов в схемах ИЛИ,И,НЕ, на которых реализованы ячейки однородной структуры, Таким образом, в результате настройки ячеек однородной структуры сигналами 1=1 и ц= однородная структура в данном случае преобразуется в матричный сдвиговый регистр, в котором реализуется операция сдвига вправо на одну позицию хранимых данных, что и требуется для решения поставленной задачи. Следует отметить, что при соединении выходов 7 ячеек крайнего правого столбца однородной структуры с входами крайнего левого столбца однородная структура преобразуется в матричный сдвиговый кольцевой регистр. Кроме того, в случае формирования на входах 6 ячеек крайнего левого столбца однородной структуры серии импульсов ц= в однородной структуре будет реализован сдвиг на и позиций, где и - число импульсов ц=1 в задаваемой серии. Формула и зобретения 45 Ячейка однородной структуры, содержащая триггер, первый и второй элементы НЕ, восемь элементов И и три элемента ИЛИ, причем первый вход50 ячейки соединен с входом первого элемента НЕ и первыми входами первого, второго и третьего элементов И, вторые входы которых соединены с вторым входом ячейки и первыми входами чет 55 вертого и пятого элементов И, вто рые входы которых соединены с выходом первого элемента НЕ, выход первого элемента И соединен с первым входом первого элемента ИЛИ, второй входкоторого соединен с третьим входомвторого элсмсцта И, первым входомшестого элемента И, третьжч входомячейки и входом второго элемента НЕ,выход которого соединен с третьимвходом третьего элемента И, четвертый вход которого соединен с третьи входом пятого элемента И, первымивходами седьмого и восьмого элементов И, четвертым входом и первымвыходом ячейки, пятый вход которогосоединен с первым входом второгоэлемента ИЛИ, второй и третий входыкоторого соединены с выходами третьего элемента И и седьмого элементаИ, второй вход которого соединен стретьим входом первого элемента ИЛИ,выходом четвертого элемента И и первым входом третьего элемента ИЛИ,второй и третий входы которого соединены с выходами второго и пятого элементов И, вы:.оды первого, второго итретьего элементов ИЛИ соединены с вторым, третьим и четвертым выходами ячейки, шестой вход которой соединен с вторыми входами шестого и восьмого элементов И и пятым выходомячейки, третий вход четвертого элемента И соединен с выходом триггера,о т л и ч а ю щ а я с я тем, что,с целью расширения функциональныхвозможностей за счет выполнения операции перемещения данных, она дополнительно содержит третий и четвертый элементы НЕ, девятый, десятыйи одиннадцатый элементы И, четвертый и пятый элементы ИЛИ, причем первый вход ячейки соединен с первымивходами девятого, десятого и одиннадцатого элементов И, вторые входыкоторых соединены с выходом триггера,выходом третьего элемента НЕ и вторым входом ячейки соответственно, атретьи входы девятого, десятого иодиннадцатого элементов И соединены с шестым входом ячейки и входомчетвертого элемента НЕ, выход которого соединен с четвертым входом второго элемента И, выход первого элемента НЕ соединен с третьими входамишестого и восьмого элементов И, выходы которых соединены с первымивходами четвертого и пятого элементов ИЛИ, вторые входы которых соединены с выходами одиннадцатого идесятого элементов И, а выходы четвертого и пятого элементор ИЛИ соедиЗаказ 484/41 Тираж 104 Подписное В 11 ИИПИ Государственного комитета СССР по делам изобретений и открытий 1130 Э 5, Москва, Ж, Раушская наб., д.4/5Производственно-полиграФическое предприятие, г,ужгород, ул. Проектная, 4 цены с единичным и нулевым входамитриггера, вход третьего элемента ИЕсоединен с вторым входом ячейки,четвертый вход третьего элемента И сое -динен с выходом девятого элемецта И.