Систолический автомат

 

Изобретение относится к вычислительной технике и предназначено для параллельной обработки информации при ее преобразовании в результате выполнения заданного алгоритма Целью изобретения является повышение универсальности и производительностиавтоматапри преобразованиях информации по заданному алгоритму для m (m 1) входных последовательностей сигналов, Имеются два режима Изобретение относится к вычислительной технике и предназначено для параллельной обработки информации при ее преобразовании в результате выполнения заданного алгоритм., Известен последовательностный автомат , содержащий итеративные матрицы для реализации функции обратной связи и выходной функцции. Недостатком этого автомата является зависимость структуры автомата от реализуемых функций, большая сложность и низкая производительность. работы систолического автомата. В режиме программирования в ячейки первой группы р систолических структур (СС) 2 и второй группы п систолических структур (СС) 3 записываются m-разрядные кубические покрытия функций выхода и функций перехода автомата, которые поступают по первой группе m информационных двухразрядных входов 4. В режиме вычислений происходит параллельное формирование на группе т-р информационных выходов 14 выходных последовательностей сигналов, определяемых внутренним состоянием автомата и m входными последовательностями сигналов, поступающих на вторую группу m информационных входов 5. Коммутация входных сигналов и сигналов обратной связи автомата на входы СС 2 и 3 осуществляется с помощью блока 1 коммутации. Вычисление функций выходов и функций переходов в автомате происходит путем выполнения ряда операций над кубическими покрытиями этих функций. 4 з.п,ф-лы, 7 ил., 2 табл. Наиболее близким по технической сущности к предлагаемому является управляющий автомат на q состояний, содержащий q универсальных логических модулей, блок из 1од2 q коммутаторов, дешифратор и регистр, выходы которого связаны с входами дешифратора , выходы которого являются выходами автомата, информационные входы блока коммутаторов соединены с выходами универсальных логических модулей, а управляющие входы соединены с выходами регистра, входы которого соединены с выходами блока коммутаторов, причем входы универсальС/1 с S со ю со Јь о

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)з G 06 F 7/00

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

В (21) 4844935/24 (22) 28.06.90 (46) 07.05.92. Бюл. М 17 (71) Винницкий политехнический институт (72) В.П.Семеренко (53) 681.327(088.8) (56) Фридман А„Менон П. Теория и проектирование переключательных схем. — M„

Мир, 1978, с.424.

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

ЬЬ 999040, кл. G 06 F 7/00, 1978. (54) СИСТОЛИЧЕСКИЙ АВТОМАТ (57) Изобретение относится к вычислительной технике и предназначено для параллельной обработк информации при ее преобразовании в результате выполнения заданного алгоритма. Целью изобретения является повышение универсальности и производительности автомата при преобразованиях информации по заданному алгоритму для m (m > 1) входных последовательностей сигналов, Имеются два режима

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

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

„„Я3 „„1732340 А1 работы систолического автомата. В режиме программирования в ячейки первой группы р систолических структур (СС) 2 и второй группы и систолических структур (СС) 3 записываютсяся m-разрядные кубические покрытия функций выхода и функций перехода автомата, которые поступают по первой группе m информационных двухразрядных входов 4. В режиме вычислений происходит параллельное формирование на группе m p информационных выходов 14 выходных последовательностей сигналов, определяемых внутренним состоянием автомата и m входными последовательностями сигналов, поступающих на вторую группу m информационных входов 5. Коммутация входных сигналов и сигналов обратной связи автомата на входы СС 2 и 3 осуществляется с помощью блока 1 коммутации, Вычисление функций выходов и функций переходов в автомате происходит путем выполнения ряда операций над кубическими покрытиями этих функций. 4 з.п,ф-лы, 7 ил„2 табл.

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

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

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

Целью изобретения является повышение универсальности и производительности автомата и ри преобразованиях информации по заданному алгоритму для m (m > 1) входных последовательностей сигналов.

В систолический автомат, содержащий блок коммутации, введены первая группа р систолических стуктур и вторая группа и систолических структур, причем группа

m w (где w p, если р>п, или w n, если р < п ) информационных выходов блока коммутации соединена с р вторыми группами m информационных входов первой группы р систолических структур и с п вторыми группами m информационных входов второй группы и систолических структур, первая группа m информационных двухразрядных входов первой систолической структуры из первой группы р систолических структур подключена соответственно к первой группе m информационных двухразрядных входов автомата, первая группа m информационных двухразрядных входов ()+1)-й (j =.1-(р-1)) систолической структуры из первой группы р систолических структур соединены соответственно с первой группой m информационных двухрэзрядных выходов j-й систолической структуры из первой группы р систолических структур, первая группа m информационных двухразрядных входов первой систолической структуры из второй группы и систолических структур соединена соответственно с первой группой m информационныхх двухразрядн ых выходов последней систолической структуры из первой группы р систолических структур. Первая группа m информационных двухразрядных входов (i+1)-й (i = 1 — (n-1)) систолической структуры из второй группы и систоличе ских структур соединена соответственно с первой группой m информационных двухразрядных выходов i-й систолической структуры из второй группы п систолических структур. Вторые группы m информационных выходов первой группы р систолических структур подключены соответственно к группе m р информационных выходов автомата, вторая группа m информационных входов которого подключена соответственно к первой группе m информационных входов блока коммутации, вторая группа m n информационных входов которого соединена соответственно с вторыми группами m

5 информационных выходов второй группы п

55 систолических структур. Первая — третья группы m управляющих входов автомата подключены соответственно к первой— третьей группе m управляющих входов первой группы р и второй группы и систолических структур. Четвертая группа m управляющих входов автомата подключена соответственно к группе m управляющих входов блока коммутации. Первый управляющий вход автомата подключен к первому управляющему входу блока коммутации и к первому управляющему входу первой группы р и второй группы п систолических структур, второй управляющий вход автомата подключен к второму управляющему входу первой группы р и второй группы и систолических структур, третий управляющий вход автомата подключен к третьему управляющему входу первой группы р и второй группы и систолических структур, четвертый управляющий вход автомата подключен к второму управляющему входу блока коммутации, который содержит группу m мультиплексоров, группу m счетчиков и группу m (w-1)-разрядных сдвиговых регистров, Первая группа m информационных входов блока соединена соответственно с первыми информационными входами всех мультиплексоров, второй, третий„„,(n+1)-й информационные входы h-го (h=1 — m) мультиплексора соединены соответственно с hм, (m+h)-м,.„,(m n-m+h)-м входами второй группы m и информэионных входов блока, управляющие входы h-го (h=1 — m) мультиплексора соединены соответственно с выходами h-го счетчика, Группа m управляющих входов блока соединена соответственно с входами суммирования всех счетчиков, входы сброса которых соединены вторым управляющим входом блока, первый управляющий вход которого соединен с синхронизирующими входами всех сдвиговых регистров, выход

h-го (h=1 — m) мультиплексора соединен с первым информационным входом h-ro сдвигового регистра и подключен к (h . w-w+1)му выходу группы m ° w информационных выходов блока, первый, второй,...,(w-1)-й выходы h-ro (h=1 — m) сдвигового регистра подключены соответственно к (h w-w+2)-му, (h w-w+3)- yÄ,,(h w)-му выходам группы

m w информационных выходов блока, причем s-я (s=1 — w) систолическая структура содержит матрицу m mячеек,,m элементов

1732340

15

25

55 свертки, 4m элементов И, 2m элементов

ИЛИ и инвертор, вход которого соединен с первыми входами первого и второго элементов И соответствующего столбца матрицы, выходы которых соединены с первыми входами первого и второго элементов ИЛИ соответствующего столбца матрицы, вторые входы которых соединены с выходами третьего и четвертого элементов И соответствующего столбца матрицы, первые входы которых соединены с вторым управляющим входом структуры и входом инвертора. Первый и второй разряды двухразрядного входа первой группы m информационных входов структуры соединены соответственно с вторыми входами третьего и четвертого элементов И соответствующего столбца матрицы, второй информационный вход первой, второй,.;.,m-й ячеек первого столбца матрицы соединен соответственно с s-м, . (w+s)-м„„,(m . w-w+s)-м входом второй группы m информационных входов структуры, Вторые информационные входы остальных ячеек каждой строки матрицы соединены соответственно с вторыми информационными выходами ячеек, являющихся соседними ячейками в строке слева, первые информационные двухразрядные входы ячеек всех строк матрицы, кроме первой строки, соединены соответственно с первыми информационными двухразрядными выходами ячеек, являющихся соседними ячейками в столбце сверху, Выходы первого и второго элементов

ИЛИ в каждом столбце соединены соответственно с первым и вторым разрядами первого информационного входа первой ячейки этого столбца, выходы результата ячеек h-й (h=1 — m) строки матрицы соединены с группой m информационных входов

h-ro элемента свертки, информационные выходы элементов свертки соединены соответственно с второй группой m информационных выходов структуры, первый и третий управляющие входы которой соединены соответственно с тактовыми входами ячеек и с первым управляющим входом элемента свертки, первый и второй разряды первого информационного друхразрядного выхода ячеек последней строки матрицы соединены с вторыми входами первого и второго элементов И соответствующего столбца, а также с первым и вторым разрядом соответствующего выхода первой группы m информационных двухразрядных выходов структуры.

Первая группа m управляющих входов структуры соединена соответственно с первой группой m управляющих входов элемента свертки, а вторая группа m управляющих входов структуры — соответственно с второй группой m управляющих входов элемента свертки, Вторые управляющие входы элементов свертки соединены соответственно с третьей группой m управляющих входов структуры, Ячейка содержит три D-триггера, элемент неравнозначности и элемент И, выход которого соединен с выходом результата ячейки, второй информационный вход которой соединен с 0-входом первого D-триггера, прямой выход которого соединен с первым входом элемента неравнозначности и с вторым информационным выходом ячейки, прямой выход второго 0-триггера соединен с вторым входом элемента неравнозначности и с первым разрядом первого информационного двухразрядного выхода ячейки, прямой выход третьего Dтриггера соединен с первым входом элемента И с вторым разрядом первого информационного двухразрядного выхода ячейки, выход элемента неравнозначности соединен с вторым входом элемента И, Dвходы второго и третьего D-триггеров соединены соответственно с первым и с вторым разрядом первого информационного двухразрядного входа ячейки, синхровходы всех D-триггеров соединены.с тактовым входом ячейки, Элемент свертки содержит группу m

RST-триггеров, группу в элементов И с открытым коллектором, RS-триггер и резистор, с помощью которого выходы группы m элементов И подключаются к источнику питания, группа m информационных входов элемента свертки соединена соответственно с S-входами группы m RST-триггеров, инверсные выходы которых соединены соответственно с первыми входами группы m элементов И, выходы которых соединены также c S-входом RS-триггера, прямой выход которого соединен с информационным выходом элемента свертки. Первый управляющий вход элемента свертки соединен с

T-входами всех RST-триггеров, второй управляющий вход элемента свертки соединен с R-входом Rs-триггера, первая группа

m управляющих входов элемента свертки соединена соответственно с R-входами группы m RST-триггеров, вторая группа m управляющих входов элемента свертки соединена соответственно с вторыми входами группы m элементов И.

В предлагаемом и в известном автоматах необходим этап предварительной подготовки перед началом работы автомата, В известном автомате предварительная подготовка автомата заключается в его настройке с помощью переключателей для ре1732340

55 ализации заданного алгоритма функционирования.

В предлагаемом автомате перед началом работы в ячейки систолических структур записываются кубические покрытия функций выходов и функций переходов автомата. Выполняемая комбинационной частью автомата функция интерпретируется как установление принадлежности входного набора аргументов множеству наборов, на которых булева функция принимает значение логической "1" (логического "0"). Установление принадлежности входного набора аргументов указанному множеству наборов выполняется с помощью операций пересечения над кубами покрытий булевой функции, Разбиение всего процесса вычислений булевой функции на элементарные независимые друг от друга операции позволило организовать в предлагаемом автомате систолическую обработку данных. Начиная с определенного момента времени, на соответстветствующих выходах автомата на каждом цикле работы реализуется значение функции выхода автомата от очередной входной последовательности сигналов из группы входных последовательностей сигналов.

В известном автомате следующая входная последовательность сигналов может быть подана на входы автомата только после окончание формирования выходной последовательности от предыдущей входной последовательности сигналов, B предлагаемом автомате программирование работы автомата заключается в записи новых кубических покрытий, тогда как изменения функционирования известного автомата выполняется аппаратурным способом путем перевода переключателей в другие положения, На фиг.1 представлена функциональная схема систолического автомата; на фиг.2— функциональная схема блока коммутации (БК); на фиг.3 — функциональная схема s-й (s=1 — w) систолической структуры (СС); на фиг.4 — схема ячейки; на фиг.5 — схема элемента свертки; на фиг,6 — временная диаграмма управляющих. сигналов; на фиг,7— схема автомата Мили.

Систолический автомат содержит (фиг.1) БК 1, первую группу р СС 2, вторую группу и СС 3, первую группу m информационных двухразрядных входов 4, вторую группу m информационных входов 5, первую — четвертую группы m управляющих входов 6 — 9, первый — четвертый управляющие входы 10 — 13, группу m . р информационных выходов 14, первую группу m информационных входов 15 БК 1, вторую

45 группу m n информационных входов 16 БК

1, группу m управляющих входов 17 БК 1, первый управляющий вход 18 БК 1, второй управляющий вход19 БК1, группу m чч(где

w=p, если р>п, или w=n, если р и) информационных выходов 20 БК 1, первую группу

m информационных двухразрядных входов

21 СС 2 и СС 3, вторую группу m информационных входов 22 СС 2 и 3, первую— третью группы m управляющих входов 23—

25 СС 2 и 3, первый — третий управляющие входы 26 — 28 СС 2 и 3, первую группу m информационных двухразрядных выходов

29 CC 2 и 3, вторую группу m информационных выходов 30 СС 2 и 3.

БК 1 предназначен для коммутации входных сигналов и сигналов обратной связи автомата на входы СС 2 и 3.

Первая группа р СС 2 предназначена для вычислений функций выхода автомата.

Вторая группа и СС 3 предназначена для вычислений функций обратной связи автомата.

БК 1 содержит (фиг,2) группу m мультиплексоров 31, группу m счетчиков 32, группу

m (w-1)-разрядных сдвиговых регистров 33, СС 2 и 3 имеют одинаковую структуру и содержат (фиг.3) m . m ячеек 34, m элементов свертки 35, 4m элементов И 36, 2:m элементов ИЛИ 37, инвертор 38, первый информационный двухразрядный вход 39 ячейки 34, второй информационный вход 40 ячейки 34, тактовый вход 41 ячейки 34, первый информационный двухразрядный выход 42 ячейки 34, второй информационный выход 43 ячейки 34, выход результата ячейки 34, группу m информационных входов 45 элемента 35 свертки, первую группу m управляющих входов 46 элемента 35 свертки, вторую группу m управляющих входов 47 элемента 35 свертки, первый управляющий вход 48 элемента 35 свертки, второй управляющий вход 49 элемента 35 свертки, информационный выход 50 элемента 35 свертки.

Ячейка 34 предназначена для выполнения элементарной операции пересечения компоненты входного набора аргументов булевой функции с компонентой одного куба кубического покрытия этой функции.

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

Ячейка 34 (фиг.4) содержит D-триггеры

51 — 53, элемент 54 неравнозначности, элемент И 55, Элемент 35 свертки (фиг,5) содержит группу m RST-триггеров 56, группу m эле1732340

10 ментов И 57 с открытым коллектором, RSтриггер 58 и резистор 59.

Автомат работает следующим образом.

Автомат работает в режиме программирования и в режиме вычислений.

В режиме программирования производится запись в автомат информации, определяющей его функционирование при вычислении заданных выходных последовательностей сигналов, Общей структурной моделью систолического автомата является автомат Мили (фиг.7), содержащий память (П), комбинационную схему выходов (КСВ) и комбинационную схему переходов (КСП), Функционирование автомата Мили однозначно определяется таблицами переключений элементов памяти, входящих в П, и значениями булевых функций, реализуемых

КСВ и КСП, С помощью КСВ формируется функция рвыходов, выражающая зависимость выхода Z автомата в момент времени т от выхода V и состояния А автомата в этот же момент времени:

Z(t) = p (V(t),A(t)).

С помощью КСП формируется функция д переходов, выражающая зависимость состояния А автомата в момент времени t+1 от входа V и состояния А автомата в момент времени t:

A(t+1) = д (V(t),A(t)), Для автомата с r вBхxоoд а м и, р выходами и и элементами памяти, в качестве которых используются D-триггеры, схема КСВ является р-выходной схемой, на входах которой реализуются функции p1,..., pp, а схема

КСП является и-выходной схемой, на выходах которой реализуются функциид1 ",дп °

В систолическом автомате функции rp1,..., ip p и д 1,..., д и задаются в виде кубических покрытий (D-покрытий или

R-покрытий) этих функций.

D-покрытие (R-покрытие) некоторой булевой функции f — это представленная в кубической форме минимальная дизьюнктивная нормальная форма (МДНФ) прямой функции f (инверсной функции f). МДНФ прямой функции f (инверсной функции f) содержит все наборы, на которых функция f принимает значение логической "1" (логического "0"), 0-покрытие (R-покрытие) состоит из кубов, число которых равно числу импликант МДНФ прямой функции f (инверсной функции f), Число компонент куба равно числу переменных МДНФ, а значениями компонент куба могут быть только три символа: 0,1,х, где х=(0,1), Каждый куб d>(r>) со5

55 ответствует одной импликанте МДНФ прямой функции т (инверсной функции f) таким образом, что единичное (нулевое) значение компонент куба соответствует прямому (инверсному) значению переменной в импликанте МДНФ (бф0, гфЯ), Каждое из покрытий (D и R) однозначно определяет функционирование комбинационной схемы, поэтому используется только одно из них, а именно то покрытие, которое содержит меньшее число кубов (в дальнейшем, для простоты, рассматриваются только D-покрытия).

Таким образом, схема КСВ описывается группой из р покрытий 01,,D p, а схема

КСП вЂ” группой из и покрытий 0>,...,0> .

Dj -покрытие состоит из mj -кубов, число которых равно числу импликант МДНФ прямой функции p j .

Di =(d>z,...,dip „„,d }, u=m, jD=1 — ц, Oi -покрытие состоит из m кубов, число которых равно числу импликант МДНФ прямой функции д i:

0 = (d „„,б,...,du ), u=mi, in=1 — а

Число Сп компонент куба всех покрытий равно

Co= г+ и.

Пусть, например, автомат имеет три внешних входа (а,Ь,р) и два входа обратной связи (q,qz), причем МДНФ функции имеет вид

p j = (а,b,c,q1,q2) = асц2 Ьсц11 ц1ц2, Тогда 0 -покрытие, соответствующее

МДНФ указанной функции, имеет вид а Ь с q> qz

1 х а х 1

D = x1 1 0x ххх11

Число m (пц ) кубов D -покрытия (Diпокрытия) и число Со компонент кубов покрытий Dj u Di (j=1-р, i=1 — n) связаны с параметром m схемы автомата следующим образом:

mi < m; ml < m; Со < m.

Если Ср < m, то (m-CD) разрядов соответствующего покрытия дополняются значениями х, Если mj < m (mj < m), то к соответствующему 0 -покрытию (0 -покрытию) добавляется m-пц (m-m< ) строк, являющихся копиями одной из строк этого покрытия (в дальнейшем, для простоты, рассматривают работу автомата только с m-разрядными Dj -покрытиями (D -покрытиями) содержащих по m кубов, при этом m = г+ n).

Перед началом работы автомата исходные покрытия D<, Dp и 01,...,0п преобразуются соответственно в покрытия

z z А А

O1,äð,...,0p,äð и 01,np,...,On,np которые

1732340

12 затем в режиме программирования, записываются в СС 2 и 3.

Процесс преобразования указанных покрытий на примере одного D-покрытия вида

d11 d12 ° Фт

d21 d22 „, С)г

D=,dh1 бЫ ... бМ, dm1 dm2 ... dmm происходит следующим образом.

D-покрытие вида (1) преобразуется в

Dnp покрытие за два этапа. На первом этапе происходит транспортирование D-покрытия аналогично известной операции транспортирования матриц. На втором этапе компоненты первого столбца транспортированного D-покрытия циклически сдвигаются снизу вверх на одну позицию; компоненты второго столбца транспортированного 0-покрытия циклически сдвигаются снизу вверх на две позиции, и т.д,. В итоге

Dnp-покрытие принимает вид

d1m d2(m-1) ... dm1

d 11m-1) d2(m-2) «. dmm

Dnp = d1P б2(п-1) ... dmj

d12 d21 " оп 3

d11 d2m " dm2

По аналогичному алгоритму происходит

z z

ПОЛУЧЕНИЕ ПОКрЫтИй D1,ïð „„,Dp,ïð И

A A

01,пр,".,Dn,nð

За ПИСЬ ПОКРЫТИЙ 01,пр,...,Dp,пр И

01.пр,.",Dn,np в СС 2 и 3 осуществляется

A A через первую группу m информационных двухразрядных входов 4 при наличии разрешающего сигнала (логической "1") на втором упраляющем входе 11. Запись указанных покрытий происходит в течение (и+р) m циклов, в каждом цикле записывается один куб, начиная с последнего куба

Dn,np -покрытия, Вначале на первую группу

А

m информационных двухразрядных входов

4 постУпают покРытиЯ D1,np,",Dn,np, а заА А тем ПОКРытиЯ 01,пр2,.„,0p,прг. В Режиме ПРОграмм и рован ия образуется путь прохождения информации между всеми соседними парами СС 2 и 3, В режиме вычислений происходит параллельное формирование на группе m p информационных выходов 14 выходных последовательностей сигналов, определяеMblx внутренним состоянием автомата и m входными последовательностями сигналов, поступаемых на вторую группу m информационных входов 5. Этот процесс осущестляется по циклам, каждый из которых состоит из трех тактов.

Вычисление функций

p1, ..., rjpp и д1,...,д и в автомате происходит путем выполнения ряда операций над кубическими покрытиями этих функций, записанных ранее в режиме программирования в соответствующие СС 2 и 3, Исходное состояние автомата принимается нулевым, т.е. значения функций

5 д1,..., д и вначале равны нулю.

В режиме вычислений на второй управляющий вход 11 поступает сигнал логического "0" и информационная связь между всеми соседними парами СС 2 и 3 прерыва10 ется.

Во время работы автомата на вторую группу m информационных входов 5 параллельно поступают m входных последовательностей сигналов:

15 „.L2m+1Lm+1L1 — ПОСЛЕдОВатЕЛЬНОСтЬ "1"; .) 2в+24п+2 2 — ПОСЛЕдОВатЕЛЬНОСтЬ "2"; ."LamL2mLm — последовательность "m", в следующем порядке.

На первый вход 51 поступают компонен20 ты набора L1;

L1 = (I 1 l2 ...Ir ), начиная с компоненты I 1 .

На h-й вход 5ь со сдвигом во времени на (h-1) циклов относительно компоненты на25 бора L1 поступают компоненты набора Lh:

Lh=(I1 2 "Ir) начиная с компоненты l1 (h=1 — m).

После поступления на вход 5ь последНЕй КОМПОНЕНТЫ lr НабОРа Lh ЧЕРЕЗ П ЦИКЛОВ

30 начинают поступать компоненты набора

Lm+h:

0 m+hl m+h. 1m+h) начиная с компоненты 11

Между поступлениями на вход 5р ком35 понент набора Lh и набора Lm+h поступают компоненты набора Qh сигналов обратной связи .

Qh = (q1 "Ср" ..qn"), начиная с компоненты q1, 40 Компоненты набора Qh поступают со сдвигом во времени на (h-1) циклов относительно компонент набора Q1.

На выходах БК 1 формируется w пакетов наборов следующим образом.

45 Первый пакет формируется на следующих выходах БК 1: ...Qm+1Lm+1Q1L1 — На ВЫХОДЕ 201; ...Qm+2Lm+2Q2L2 — На ВЫХОДЕ 20w+1 (2)

".Q2mL2mQmLm — на выходе 20(m-1)w+1.

50 Наборы пакета (2) на входе 20ь1+1 поступают со сдвигом во времени на один цикл относительно наборов на соседнем входе

20(h-1)w+1

В общем случае, I-й пакет наборов фор55 мируется на следующих выходах БК 1: ...СЬп+14п+101(1 — на выхсдЕ 20, (3) ...Qm+2Lm+2Q2L2 — На ВЫХОДЕ 20I+w, ...Q2m42mQmLm — на выходе 20(m-1)w+i.

14

Наборы пакета (3) в каждой строке поступают со сдвигом во времени íà (i-1) циклов относительно наборов в одноименной строке пакета (2). Наборы соседних сторон пакета (3) также поступают со сдвигом во времени на один цикл относительно друг друга внутри пакета.

Наборы пакета (2) поступают одновременно на входы первой СС 2 и на входы первой СС 3. Аналогично, наборы пакета (3) поступают одновременно на входы j-й СС 2 (j =1 — р) и на входы i-й CC3(i =1 — п).

С помощью группы р СС 2 происходит вычисление функций p < „„, pp для заданных m-входных последовательностей сигналов.

111

Значение функции р1 появляется на первом выходе первой СС 2 на (2m-1)-м цикле после поступления на первый вход первой СС 2 первой компоненты I< . входного набора L<. (1)

Значение функции р1 появляется на первом выходе j-й СС 2 через (j-1) циклов

a1) после вычисления функции р1. (ь1

Значение функции у) появляется на hм выходе j-й СС 2 через (h+j-2) циклов после (1) вычисления функции р1 (или íà (2m-1)-м цикле после поступления на h-й вход j-й СС

2 первой компоненты 11"+ входного набора

Lh+i) 0 =1 — р, h — 1 — m).

Очередные значения функции p j, определяемые h-й входной последовательностью сигналов

" L2m+hLm+hLh появляются через каждые m циклов íà h-м выходе j-й СС 2.

С помощью группы и СС 3 происходит вычисление функций 0 >,..., д „ для заданных m входных последовательностей сигналов. (11

Значение функции д 1 появляется на первом выходе первой СС 3 на (2m-1)-м цикле после поступления на первый вход первой СС 3 первой компоненты I> входного набора L>, т.е, одновременно с вычислением функции p ) .

Аналогично, значения функции д () появляются на h-м выходе i-й СС 3 одновременно с вычислением функции rpP, если

i=J (i = 1 — n, j - 1 — р, h = 1 — m).

БК 1 работает следующим образом.

Перед началом работы БК 1 устанавливается в исходное состояние по приходу сигнала сброса на второй управляющий вход 19. В исходном сотоянии все счетчики

32 находятся в нулевом состоянии.

Вначале управляющие сигналы в первом такте каждого цикла начинают поступать по первому входу 171 группы m управляющих входов 17.

Затем, со сдвигом на один цикл относительно соседних входов, начинают поступать управляющие сигналы на входы

172,.„,17п группы m управляющих входов

17, В итоге, счетчики 32 начинают считать, причем состояния соседних счетчиков в каждом цикле отличаются на единицу, Счетчики 32 имеют модуль пересчета m, Мультиплексоры 31 коммутируют сигналы так, что в течение первых r циклов на выходе h-ro мультиплексора 31 поступают сигналы с входа 15п первой группы m информационных входов 15, а в течение последующих и циклов — поочередно от тех и входов второй группы m n информационных входов 16, которые подключены к h-му мультиплексору, Далее на выход h-ro мультиплексора 31 снова поступают сигналы с входа 15ь и т.д.

Сигналы с выхода каждого мультиплексора 31 записываются в соответствующий (w-1)-разрядный сдвиговый регистр 33, начиная с младшего разряда регистра 33. С помощью h-го регистра 33 организуется задержка на 1,...,w циклов сигнала с выхода

h-r0 мультиплексора 31 на соответствующие выходы 20(h-ij +ã„.„20(ь- )у + группы m w информационных выходов 20.

В первой группе р СС 2 j-я СС 2 работает следующим образом () = 1 — р).

B режиме программирования при наличии разрешающего сигнала (логической н1н) на втором управляющем входе 27 происходит поступление кубов покрытий

О .npz,...,op,np через первую группу m информационных двухразрядных входов 21, Покрытия D(I+>),пр,.„,Dp,пр проходят через

j=e СС 2 на первую группу m информационных двухразрядных выходов 29, а покрытие

Dj,pp записывается в J-ю СС2, В режиме вычислений в j-м СС 2 осуществляется вычисление функций путем выполнения ряда операций над записанным ранее покрытием Di,ïp .

Традиционный метод вычисления булевой функции f на входном наборе L ее аргументов с помощью комбинационной схемы можно интерпретировать как установление принадлежности входного набора L множеству наборов, на которых функция f принимает значение логической н1".

При использовании кубического представления булевых функций установление принадлежности входного набора L указанному множеству наборов может быть выпол15

1732340

16 нено аналитически с помощью операции пересечения кубов. По определению операцИИ ПЕрЕСЕЧЕНИя Куба а=а1аг...an И Куба

Ь=Ь1Ьг...Ьд обозначается как с = à il ь и слу.жИт дЛя ВЫдЕЛЕНИя Куба С = С1Сг...Cn, яВЛяЮ- 5. щегося общей частью кубов а и b. Значение компоненты ci определяется по табл.1, как

ci = aiIIbi (l = 1 — n), где знак ф означает пустое пересечение), Например, если

a =x10x1, b =1 x01 1, 10 тогда куб с равен ,-!Х1ОХ1

1х011

1х011

Входной набор L принадлежит множе- 15 ству наборов, на которых функция f принимает значение логической "1" (логического

"О"), если имеет место непустое пересечение набора L хотя бы с одним кубом О-покрытия функции f (пустое пересечение 20 набора L со всеми кубами D-покрытия функции f):

1, если Lild Ф ф для любого е;

f(L)=

О, если Lhd. =ф для всех е, 25 где L=(I1I2...ln), dg =(dg1dg2". dgm), =1 — m, d 6 D.

Аналогичные соотношения справедливы и для комбинационной схемы КСП 30 (фиг.7), на входы которого поступают входные наборы сигналов и наборы сигналов обратной связи.

Значение функции р> íà h-м выходе (h)

j-й СС 2 может быть определено следующим образом:

i 1, О если U ОД4 Фф для любого s у ")(в а h)-. (4), О, если Ln Овлур* =ф для всех е

ГдЕ Lh=(li !г ... !г );

h h Л 40

Qh = (q1 цг ... qn ); !, = (dg) dip... !,„,); л рг

Если, например, Lh = (111) и СЬ = (00), тогда рассматривавшаяся функция р j(a,b,с,q1,с!г) принимает единичное значение, так как имеется непустое пересечение с одним кубом покрытия Dj этой функции: х110х

Отличительной особенностью выполнения операции над кубами является возможность одновременной и независимой обработки отдельных компонент кубов. Благодаря указанной особенности процесс выполнения операции пересечения входных наборов аргументов булевой функции с кубами кубического покрытия этой функции распараллеливается с помощью матрицы m-m ячеек 34.

На вторую группу m информационных входов 22 j-й СС 2 поступает параллельно !-й пакет наборов: .„Qm+1Lm+1Q1L1 — на вход 22з; ...Qm+2Lm+2Q2L2 на вход 22w+s (5) ...Q2mL2mQmLm HB вход 22(m-1)w+s.

Наборы соседних строк пакета (5) поступают со сдвигом во времени на один цикл относительно друг друга внутри пакета.

Процесс вычислений в матрице ячеек 34 начинается с активизации первой ячейки 34 первой строки, т,е. ячейки 1 с координатами (1,1).

На первом такте j-го цикла работы на вход 40 указанной ячейки 34 поступает компонента !1 входного набора L1, а также про1 исходит циклический сдвиг сверху вниз по столбцам содержимого матрицы ячеек 34.

Вследствие этого сдвига на вход 39 ячейки

34 с координатами (1,1) поступает компоНЕНта d11z ПОКрЫтИя Djnp И На ВЫХОДЕ 44 указанной ячейки 34 получается результат выполнения операции:

1д 7

На первом такте j-ro цикла работы первый элемент 35 свертки устанавливается в исходное состояние, а на втором такте по входу 451 группы m информаицонных входов полученный результат из ячейки 34 с координатами (1,1) записывается в первый элемент 35 свертки.

На первом такте (j+1)-го цикла работы компонента I1 набора L1 поступает на вход

40 ячейки 34 с координатами (1,2), а на входы 40 ячеек 34 с координатами (1,1) и (2„1) поступают компоненты соответственно !г и

I1 (!г с.- !1, I1 6 (г).

После циклического сдвига в матрице ячеек 34 на входы 39 ячеек 34 с координатами (1,1), (1,2) и (2,1) поступают соответствующие компоненты покрытия Dj,np . В итоге, на первом такте (j+1)-го цикла выполняют следующие операции: ! г lld12 — в ячейке 34 с координатами (1,1);

l1 f1 !г1 — в ячейке 34 с координатами (1,2); !

1 ис!11 — в ячейке 34 с координатами (2,1).

На втором такте (!+1)-ro цикла результаты выполнения указанных операций в ячейках 34 с координатами (1,1) и (1,2) записываются в первый элемент 35 свертки, а результат выполнения операции в ячейке

34 с координатами (2,1) записывается во второй элемент 35 свертки, После этого фронт выполняемых операций перемещается к ячейкам 34 с координа17

1732340

18 тами (3,1), (2,2), (1,3) и, таким образом, порождается волна вычислений, бегущая вниз по матрице ячеек 34.

В течение первых m циклов, начиная с

j-го цикла, в ячейке 34 с координатами (1,1) поочередно получают результаты выполнения следующих операций:

11Ьб11,"„1г(Ъб1г, q1hd1(r+1) gn fld1m

Тем самым на первом такте (j+m-1)-го цикла заканчивается выполнение операции пересечения наборов L101 с компонентами кУба б1 покРытиЯ Dj,np 06Щий РезУльтат выполнения операции пересечения наборов L1Q1 с кубом б1 формируется в первом элементе 35 свертки на втором такте (j+m-1)го цикла.

На первом такте (j+m)-ro цикла в ячейке

34 с координатами (1,2) заканчивается выполнение операции пересечения наборов

L1Q1 с кубом б2 покрытия Dj,npz

На первом такте (j+2m-2)-го цикла в ячейке 34 с координатами (1,m) заканчивается выполнение операции пересечения наборов L1Q1 с кубом dm покрытия 01,пр .

Общий результат выполнения операции пересечения наборов L1Q1 с кубом dm формируется в первом элементе 35 свертки на втором такте (j+2m-2)-го цикла, На третьем такте (j+2m-2)-ro цикла на первом выходе 301 второй группы m информационных выходов 30 получают окончательный результат выполнения операции пересечения наборов L1Q1 с покрытием

Dj,npz, сфоРмиРованным в соответствии с соотношением (4). на выходе 301 в указанный момент времени значение логической н1и (логического нОи) соответствует значению фУнкции Pj", покРытиЯ Dj,npz котоРый записано в j-1 СС 2, на входном наборе L1 и наборе 01 сигналов обратной связи автомата.

При дальнейшей работе автомата на третьем такте

J+2m-1,...,j+3m-3 циклов на выходах 30 „„,30m второй группы

m информационных выходов 30 поочередно получают результаты выполнения операции с покрытием Dj,np наборов L1Qz,...,LmQm.

Во второй группе и СС 3 i-я СС 3 работает следующим образом (i = 1 — и).

В режиме программирования в i-ю СС 3 записывается покрытие Dj,np аналогично

А записи покрытия Dj,np в j-ю СС 2, B режиме вычислений в i-й СС 3 осуществляется вычисление функций д I ),..., д п аналогично вычислению функций yP,..., pj"j в jй сс 2.

Ячейка. 34 работает следующим образом, На первом такте каждого цикла по входу

39 в D-триггеры 52 и 53 записывается очередная компонента б (d<< ) покрытия Dj,np

z (Di np ), а в D-триггер 51 — очередная компо5 нента 1 набора Lh или компонента qi набора Qh (К = 1 — r; i = 1 — n; h = 1 — m).

Поскольку значениями компонент куба могут быть символы из алфавита (0,1,х), поэтому для представления компоненты d < в

10 двоичном алфавите необходимо два разряг1 z2 да б - бь

0 - 01

1 -«11 х -ф10

15 Поэтому, на первом такте каждого цикла в D-триггер 52 и в О-триггер 53 записываются значения соответственно б„и б

z1 z2

После окончания записи соответствующей информации в D-триггеры 51-53 выпол20 няется. операция пеоесечения компоненты б ч с компонентой lk или q> .

z .1

Поскольку значениями компонент Ik u

q j могут быть только символы нОи и и1", поэтому в ячейке 34 укаэанная операция

25 пересечения выполняется согласно табл.2.

В ячейке 34 реализуется следующая функция О:

30 (Общееln, для компонент Ik и d<<

g(Q Пd ÏÇ, jU(g, Пе)„пд„)и

=(; 1ы) " "„

35 для компонент qi и б

Функция О, которая реализуется с помощью элемента 54 неравнозначности и элемент И 55, принимает значение логической и1н (логического иОи) при наличии пус40 того (непустого) пересечения компоненты

d с компонентой 1ь или qi

В конце первого такта каждого цикла значение функции реализуется на выходе 44

45 ячейки 34.

Аналогично реазлизуется функция О и для покрытия Di,np .

Первый элемент 35 свертки в первой СС

2 работает следующим образом.

50 На первом такте первого цикла по сигналу, поступающему по входу 461 первой группы m управляющих входов 46 первый

RST-триггер 56 устанавливается в нулевое состоя ние.

На первом такте каждого последующего цикла поочередно устанавливаются в нулевое состояние второй RST-триггер 56,...,m-й

RST-триггер 56.

1732340

Через каждые m циклов RST-триггеры

56 снова устанавливаются в нулевое состояние в указанной последовательности.

В ц — и RST-триггер 56 первого элемента 35 свертки в.конце первого такта каждого цикла по входу 45 у группы m информационных входов 45 поступает результат операZ ции пересечения компоненты d c компонентой Ik или q1 от ячейки 34 с коорь динатами (1, y) (y= 1 — m). Этот результат поступает на S-вход y — ro RST-триггера 56, и при наличии пустого пересечения компоненты с компонентой 1 или q1 g — и RSTь ь триггер 56 устанавливается в единичное состояние. S-вход RST-триггера 56 является синхронным и запись в RST-триггер 56 осуществляется во втором такте каждого цикла по приходу тактового сигнала на вход 48.

На втором такте m-го цикла в первом

RST-триггере 56 формируется результат операции пересечения наборов L1Q1 с кубом d1 покрытия D1,гр . При пустом (непустом) пересечении наборов L1Q1 с кубом d1 первый RST-триггер 56 находится в единичном (нулевом) состоянии.

На втором такте (2m-1)-ro цикла в m-м

RST-триггере 56 формируется результат операции пересечения наборов L1Q1 с кубом dm покРытиЯ D1,пр аналогичным обРазом, Окончательный вывод о результате операции пересечения наборов L1Q1 со всем покрытием D1,rip согласно соотношению (4) можно сделать после анализа результатов операции пересечения наборов L101 с отz дельными кубами покрытия D1,np .

Поэтому до получения результата операции пересечения наборов L1Q1 с кубом

d сохраняются результаты операции пересечения наборов L1Q1 с предыдущими кубами покрытия D1,» . С этой целью на третьем такте m-ro, (m+1)-го,...,(2m-1)-ro циклов по сигналам, поступающим по второй группе mуправляющих входов 47,,происходит передача инверсного содержимого соответственно первого RST-триггера 56, второго RST-триггера 56,...,m-го RST-триггера 56 через элементы И 57 в RS-триггер 58.

При наличии в указанные моменты времени хотя бы одного RST-триггера 56 в нулевом состоянии RS-триггер 58 по S-входу устанавливается в единичное состояние.

Следовательно, на третьем такте (2m-1)ro цикла e RS-триггере 58 формируется зна1 1 чение функции р ) (L101) согласно соотношению (4): единичное (нулевое) состояние RS-триггера 58 свидетельствует о () том, что на наборах 1 101 функция p ) (L1Q1) принимает единичное (нулевое) значение.

В RS-триггер 58 первого элемента 35 свертки с интервалом в m циклов формируются значения функций:

Р 1 (L1Q1), Р ) (1Qm+1), Р ) (Lzm+1Qzm+1),...

Во втором такте m-ro 2m-ro, 3m-го,... циклов RS-триггер 58 сбрасывается в нулеsoe состояние по сигналу, который поступает по входу 49.

Элементы И 57 являются элементами с открытым коллектором, что позволяет вместе с резистором 59 реализовать на их выходах схему "Монтажное ИЛИ".

Остальные элементы 35 свертки в автомате работают аналогично.

На фиг.6 показана последовательность появления управляющих сигналов на входах 46 — 49 элемента свертки.

Для определения технико-зкономической эффективности предлагаемого автомата по сравнению с известным оценивают производительность обеих автоматов на q состояний для N входных последовательностей сигналов, состоящих из r-компонентных входных наборов.

В известном автомате входные последовательности сигналов могут поступать лишь друг за другом, поэтому соответствующие им выходные последовательности сигналов формируются за время Т1:

30 где t1 — длительность цикла работы автомата, В предлагаемом автомате входные последовательности сигналов поступают в конвейерном режиме, причем значения выходных функций от очередной входной последовательности сигналов, начиная с (2m-1)-ro цикла (где m = r+ logz q), поя вля ются на соответствующих выходах автомата на каждом цикле, Поэтому общее время Тг вычислений составляет

Тг =(2m — 1+ N -1) tz = N tz+ 2(г+

+1092 Ц - 1) Ег, 45 та где tz — длительность цикла работы автомаРост по производительности и редлагаемого автомата по сравнению с известным составляет

Т1 N г

Тг N+2 r+logzq — 1

ПРИ t1=t2 .

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

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

22

21

1732340 первая группа р систолитических структур и вторая группа п систолических структур, причем группа m w (где w=p, если р > и, или w=n, если р и) информационных выходов блока коммутации соединена с р вторыми группами m информационных входов первой группы р систолических структур и с и вторыми группами m информационных входов второй группы п систолических структур, первая группа m информационных двухразрядных входов первой систолической структуры из первой группы р систолических структур подключена соответственно к первой группе m информационных двухразрядных входов автомата, первая группа m информационных двухразрядн ых входов (+1)-й (j=1-(n-1) ) систол ичес кой структуры из первой группы р систолических структур соединены соответственно с первой группой m информационных двухразрядных выходов)-й систолической структуры из первой группы р систолических структур, первая группа m информационных двухразрядных входов первой систолической структуры из второй группы и систолических структур соединена соответственно с первой группой m информационных двухразрядных выходов последней систолической структуры из первой группы р систолических структур, первая группа m информационных двухразрядных входов (i+1)-й (l=1 — (и-1)) систолической структуры из второй группы и систолических структур соединена соответственно с первой группой

m информационных двухрязрядных выходов 1-й систолической структуры из второй группы и систолических структур, вторые группы m информационных выходов первой группы р систолических структур подключены соответственно к группе m р информационных выходов автомата, вторая группа

m информационных входов которого подключена соответственно к первой группе m информационных входов блока коммутации, вторая группа m п информационных входов которого соединена соответственно с вторыми группами m информационных выходов второй группы и систолических структур, первая — третья группы m управляющих входов автомата подключены соответственно к первой — третьей группам m управляющих входов первой группы. р и второй группы и систолических структур, четвертая группа m управляющих входов автомата подключена соответственно к группе m управляющих входов блока коммутации, первый управляющий вход автомата подключен к первому управляющему входу блока коммутации и к первому управляющему входу первой группы р и второй группы и систоли5

30

55 ческих структур, второй управляющий вход автомата подключен к второму управляю-. щему входу первой группы р и второй группы п систолических структур, третий управляющий вход автомата подключен к третьему управляющему входу первой группы р и второй группы и систолических структур, четвертый управляющий вход автомата подключен к второму управляющему входу блока коммутации.

2. Автомат поп.1, отл и ч а ю щи и с я тем, что блок коммутации содержит группу

m мультиплексоров,,группу m счетчиков и группу m(w-1)-разрядных сдвиговых регистров, первая группа m информационных входов блока соединена соответственно с первыми информационными входами всех мультиплексоров, второй, третий...„(n+1)-й информационные входы h-го (h=1 — m) мультиплексора соединены соответственно с hм, (m+h)-м,...,(m . и-n+h)-м входами второй группы m п информационных входов блока, управляющие входы h-ro мультиплексора соединены соответственно с выходами h-го счетчика, группа m управляющих входов блока соединена соответственно с входами суммирования всех счетчиков, входы сброса которых соединены с вторым управляющим входом блока, первый управляющий вход которого, соединен с синхронизирующими. входами всех сдвиговых регистров, выход

h-го мультиплексора соединен с первым информационным входом h-ro сдвигового регистра и подключен к (h w-w+1)-му выходу группы m w информационных выходов блока, первый, второй,...,(w-1)-1 выходы h-го сдвигового регистра подключены соответственно к (h w-w+2)-му, (h w-w+3)-му,...,(h

w)-му выходам группы m w информационных выходов блока.

3, Автомат по и 1, отличающийся тем, что s-я (s = 1-w) систолическая структура содержит матрицу m m ячеек, m элементов свертки, 4m элементов И, 2m элементов

ИЛИ и инвертор, вход которого соединен с первыми входами первого и второго элементов И соответствующего столбца матрицы, выходы которых соединены с первыми входами первого и второго элементов ИЛИ соответствующего столбца матрицы, вторые входы которых соединены с выходами третьего и четвертого элементов И соответствующего столбца матрицы, первые входы которых соединены с вторым управляющим входом структуры и входом инвертора, первый и второй разряды двухразрядного входа первой группы m информационных входов структуры соединены соответственно с вторыми входами третьего и четвертого эле1732340

24

5

15

45

50 ментов И соответствующего столбца матрицы, второй информационный вход первой, второй,...,m-й ячеек первого столбца матрицы соединен соответственно с s-м, (s + w)м,...,(m w-w+s)-м входом второй группы m информационных входов структуры, вторые информационные входы остальных ячеек каждой строки матрицы соединены соответственно с вторыми информационными выходами ячеек, являющихся соседними ячейками в строке слева, первые информационные двухразрядные входы ячеек всех строк матрицы, кроме первой строки, соединены соответственно с первыми информационными двухразрядными выходами ячеек, являющихся соседними ячейками в столбце сверху, выходы первого и второго элементов ИЛИ в каждом столбце соединегы соответственно с первым и вторым разрядами первого информационного входа первой ячейки этого столбца, выходы результата ячеек h-й (h = 1 — m) строки матрицы соединены с группой m информационных входов h-го элемента свертки, информационные входы элементов свертки соединены соответственно с второй группой m информационных выходов структуры, первый и третий управляющие входы которой соединены соответственно с тактовыми входами ячеек и с первым управляющим входом элемента свертки, первый и второй разряды первого информационного двухразрядного выхода ячеек последней строки матрицы соединены с вторыми входами первого и второго элементов И соответствующего столбца, а также с первым и вторым разрядами соответствующего выхода первой группы m информационных двухразрядных выходов структуры, первая группа m управляющих входов структуры соединена соответственно с первой группой m управляющих входов элемента свертки, вторая группа m управляющих входов структуры соединена соответственно с второй группой m управляющих входов элемента свертки; вторые управляющие входы элементов свертки соединены соответственно с третьей группой m управляющих входов структуры.

4. Автомат по п.З, отличающийся тем, что ячейка содержит три D-триггера, элемент неравнозначности и элемент И, выход которого соединен с выходом результата ячейки, второй информационный вход которой соединен с D-входом первого 0триггера, прямой вход которого соединен с первым входом элемента неравнозначности и с вторым информационным выходом ячейки, прямой выход второго D-триггера соединен с вторым входом элемента неравнозначности и с первым разрядом первого информационного двухразрядного выхода ячейки, прямой выход третьего Dтриггера соединен с первым входом элемента И с вторым разрядом первого информационного двухразрядного выхода ячейки, выход элемента неравнозначности соединен с вторым входом элемента И, 0входы второго и третьего D-триггеров соединены соответственно с первым и вторым разрядами первого информационного двухразрядного входа ячейки, синхровходы всех

D-триггеров соединены с тактовым входом ячейки.

5. Автомат по п.З, отличающийся тем, что элемент свертки содержит группу m

RST-триггеров, группу m элементов И с открытым коллектором, RS-триггер и резистор, через который выходы группы m элементов И подключаются к источнику питания, причем группа m информационных входов элемента свертки соединена соответственно с S-входами группы m RST-триггеров, инверсные выходы которых соединены соответственно с первыми входами группы m элементов И, выходы которых соединены также с S-входом

RS-триггера, прямой выход которого соединен с информационным выходом элемента свертки, первый управляющий входэлемента свертки соединен с Т-входами всех RSTтриггеров, второй управляющий вход элемента свертки соединен с R-входом RSтриггера, первая группа управляющих входов элемента свертки соединена соответственно с R-входами группы m RSTтриггеров, вторая группа m управляющих входов элемента свертки соединена соответственно с вторыми входами группы m элементов И, 25

1732340

Таблица 1

Таблица 2

1732340

1732340

1732340

1732340

РХ. fall

3 l Зи+Ф Зги+7

Флг.г

25

Составитель В.Семеренко

Техред М.Моргентал Корректор О.Кравцова

Редактор И,Дербак

Заказ 1583 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101