Двумерная однородная структура для анализа логических векторов

 

ОП ИСАНИ Е

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕХЪСТВУ (11) 590747

Союз Советских

Социалистических, Ресиублик ()

1 (. ° (61) Дополнительное к авт. свид-ву— (22) Заявлено 18.07.75 (21) 2158318/18-24 с присоединением заявки №вЂ” (23) Приоритет— (43) Опубликовано 30.01.78. Бюллетень № 4 (45) Дата опубликования описания 30.01.78 ( ч (51) М. Кл г 6 06 F 15/20

Государстаеииый комитет

Совета Мииистров СССР ло делам иаобретеиий и открытий (53) УДК 681.3(088.8) (72) Авторы изобретения

В. Н. Алеева и Я. И. Фет

Институт математики Сибирского отделения АН СССР (71) Заявитель (54) ДВУХМЕРНАЯ ОДНОРОДНАЯ СТРУКТУРА

ДЛЯ АНАЛИЗА ЛОГИЧЕСКИХ ВЕКТОРОВ

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

Известны устройства для анализа логических векторов (1), выполненные в виде после- 5 довательных или .последовательно-параллельных схем из элементов ИЛИ. Однако такие устройства позволяют находить только, положение первой единицы анализируемого вектора, что ограничивает их функциональные воз- 1О ложности.

Наиболее близким к изобретению является устройство (2), выполненное в виде матрицы ячеек, каждая из .которых содержит логиче- 15 ские элементы И, ИЛИ и НЕ. Это устройство позволяет .подсчитывать количество единиц в анализируемых векторах, но оно характеризуется узкой специализацией, неоднородностью и нерегулярностью связей и обеспечивает 2О только суммирование количества единиц в векторе.

Целью настоящего изобретения является расширение функциональных возможностей двумерной однородной структуры для анализа 25 логических векторов, то есть подсчет количества единиц и определение. положения k-й единицы. Указанна я цель достигаетоя тем, что первый вход ячейки соединен с первым входом первого элемента И и с первым выходом ячейки; второй вход ячейки соединен с первым входом первого элемента ИЛИ, со вторым входом, первого элемента И, через первый элемент НЕ с первым входом третьего элемента И и с первым входом второго элемента

И, выход которого является вторым выходом ячейки; третий вход ячейки соединен со вторым входом первого элемента ИЛИ, выход ,которого соединен с третьим выходом ячейки; четвертый вход, ячейки соединен через второй элемент HE со вторым входом второго элемента И, с третьим входом первого элемента

И и со вторым входом третьего элемента И, выход, которого является четвертым выходом ячейки; пятый вход ячейки соединен с первым входом второго элемента ИЛИ, второй вход которого соединен с выходом первого элемента И, а выход второго элемента ИЛИ является пятым выходом ячейки.

На фиг. 1 изображена структурная схема предлагаемой стру1ктуры; на фиг. 2 — функциональная схема ячейки.

Структура состоит |из ячеек 1 с входами

2 — б и выходами 7 — П. Каждая ячейка содержит элементы НЕ 12 и 18, элементы И 14, 15 и 1б и элементы ИЛИ 17 и 18.

Каждая (ячейка реализует следующие функции:

590747 х =х i/z, / = f t yzt, z = — zt

У =У (1) (2) () (4) (5) Анализируемый логический вектор подают поразрядно на входы всех строк левой границы матр ицы. Для подсчета количества единиц необходимо, чтобы в,каждом столбце на входах х и t верхней строки были «О» и «1» соответственно (состояние входов у и f для данной операции несущественно). Очевидно, что при этом потенциал точек 19 ячеек первого слева столбца соответствует значениям одноименных разрядов анализируемого вектора.

Точечки 20 этих же ячеек имеют, потенциал «1» до тех;пор, пока не встретится ячейка, соответствующая первой единице анализируемого вектора. Из функции (2) следует, что во всех ячейках, расположенных ниже этой ячейки, потенциал точки 20 будет иметь значение «О» независимо от содержимого анализируемого вектора. Вследствие этого, согласно функции (4), на выходах z первого столбца будет продублирован анализируемый вектор за исключением его первой единицы, которая заменяется нулем, Аналогичные преобразования происходят в каждом столбце матрицы, в результате чего на выходах z k-го столбца дублируется

«остаток» исходного вектора за исключением первых k единиц. Если всего в исходном векторе содержится l единиц, то в i.ì столбце (i (l) будет l — i+1 точек 19 с потенциалом, соответствующим «1». Начиная с (1+ 1) -ro столбца, все точки 19 имеют «О». Таким образом, задача подсчета количества единиц в анализируемом векторе сводится к нахождению l-го столбца. Это выполняется с помощью цепочки, реализующей функцию (1): так как на верхние входы х,подаются, константы «О». то значения выходов х в нижней строке рав ны «1» только в первых l столбцах, что позволяет легко обнаружить 1-й столбец.

Для определения положения k-й единицы з анализируемом логическом, векторе необхо-! и мо одновременно подать константу «1» на входы 1 верхней строки и верхний вход у k-го столбца и,константу «О» на все входы f левого столбца (состояние входов х для данной операции несущественно). При этом в соотзетствии с функцией (3), на выходах f правого столбца дублируется «остаток» исходного вектора за исключением первых k — 1 единиц.

Двухмерная однородная структура для анализа логических векторов, выполненная в

25 виде матрицы ячеек, ка>идая из;которых содержит логические элементы И, ИЛИ и НЕ, о т л и ч а ю:щ а я с я тем, что, с целью расширения функциональных возможностей, в ней первый вход ячейки соединен с первым вхоЗО дом первого элемента И и с первым выходом ячейки; второй вход ячейки соединен с первым входом первого элемента ИЛИ, со вторым входом первого элемента И, через первый элемент НЕ с,первым входом третьего

85 элемента И и с первым входо м второго элемента И, выход которого является вторым выходом ячейки; третий вход ячейки соединен со вторым входом первого элемента ИЛИ, выход которого соединен с третьим выходом

4О ячейки, четвертый вход ячейки Соединен через второй элемент НЕ со вторым входом второго элемента И, с третьим входом первого элемента И и со вторым входом третьего элемента И, выход которого является четвертым вы45 ходом ячейки; пятый вход ячейки соединен с первым входом второго элемента ИЛИ, второй вход которого соединен с выходом первого элемента И, а выход, второго элемента

ИЛИ является пятым выходом ячейки.

55

О!

Следовательно, положение k-й единицы совпадает с положением первой единицы «остатка».

Для выделения этой единицы можно использовать, например, схему, аналогичную цепочке t описанной однородной структуры.

Устройство, позволяет также решить задачу выделения первых k единиц исходного вектора. Дл я этого достаточно подать анализируемый вектор на входы z левой границы в «отраженном» виде, то есть старшими разрядами сверху.

Устройство для анализа логических векторов,может найти широкое применение в различных цифровых вычислительных и управляющих устройствах, например, для аппаратной реализации логических языков высокого уровня. Стоимость устройства может быть достаточно, малой, если однородная структура выполнена на больших интегральных схемах.

Ф о plM у л а и з о б р ет е н и я

Источники информации, принятые во внимание при экспертизе:

1. Крайз мер Л. П. и,др. «Ассоциативные запоминающие устройствам, Л., «Энергия».

1967.

2. Авторское свидетельство СССР

Ко 304567, кл. G 06 F 1/00, 1969.

590747

Pz г.;

Составитель И. Грибков

Техред А. Камышникова

Корректор В. Гутман

Редактор Н. Громов

Подписное

Тип. Харьк. фил. пред. «Патент»

Заказ 1013/2067 Изд. № 210 Тираж 881

НПО Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, )К-35, Раушская наб., д. 4/5