D
соединен с входом элемента задержки. Входами блока
Z
являются входы
элемента
D
. Выходом блока
Z
является выход элемента задержки.
Являющуюся (
s, s
)-блоком схему, состоящую из элемента задержки и
s
−
1
блоков
Z
, назовем (
Z, s
)-цепочкой. Первым входом (выходом) (
Z, s
)-цепочки
является вход (выход) элемента задержки, выход которого соединен с вхо-
дом первого блока
Z
. Выход блока
Z
соединен с входом следующего блока
Z
. Остальными входами (выходами) (
Z, s
)-цепочки являются входы (выхо-
ды) блоков
Z
. Нетрудно проверить, что (
Z, s
)-цепочка является моделью
s
–
разрядного ОРС.
Состоянием конечного автомата является набор значений выходов его
элементов задержки. Через
z
1
, z
2
, . . . , z
s
обозначим значения входов (
Z, s
)-
цепочки, а через
u
1
, u
2
, . . . , u
s
— значения ее выходов.
Нетрудно проверить, что из состояния
(
u
1
, u
2
, . . . , u
s
)
(
Z, s
)-цепочка пе-
рейдет в состояние
z
1
, u
1
z
2
, . . . , u
s
−
1
z
s
,
где символом обозначена операция сложения по модулю 2.
Покажем теперь, что любой конечный автомат можно реализовать схемой
T
, в которой все элементы задержки находятся в одном ОРС.
Эта схема
T
, реализующая автомат M, имеет
n
входов
x
1
, x
2
, . . . , x
n
,
m
выходов
y
1
, y
2
, . . . , y
m
и состоит из (
n
+
s, m
)-блока
A
, (
n
+
s, s
)-блока
C
и
(
s, s
)-блока
R
, являющегося (
Z, s
)-цепочкой.
Блок
A
(как и в схеме
S
) реализует функцию выхода. Входы схемы
T
соединены с первыми входами блоков
A
и
C
. Остальные входы этих блоков
соединены с выходами блока
R
. Входы блока
R
соединены с последними
s
выходами блока
C
. Выходами схемы
T
являются выходы блока
A
.
Опишем функционирование блока
C
. Значения выходов блока
R
обозна-
чим через
q
1
, q
2
, . . . , q
s
.
Пусть
p
i
(
x
1
, . . . , x
n
, q
1
, . . . , q
s
)
,
1
≤
i
≤
s,
— булева функция, реализу-
емая на
i
-м выходе блока
B
(из схемы
S
).
Пусть
z
i
(
x
1
, . . . , x
n
, q
1
, . . . , q
s
)
,
1
≤
i
≤
s,
— булева функция, реализуе-
мая на
i
-м выходе блока
C
. Положим
z
1
(
x
1
, . . . , x
n
, q
1
, . . . , q
s
) =
p
1
(
x
1
, . . . , x
n
, q
1
, . . . , q
s
)
и
z
i
(
x
1
, . . . , x
n
, q
1
, . . . , q
s
) =
p
i
(
x
1
, . . . , x
n
, q
1
, . . . , q
s
)
q
i
−
1
,
2
≤
i
≤
s.
Нетрудно проверить, что схема
T
реализует автомат M. Поскольку блоки
B
и
C
реализуют различные системы булевых функций, схема
T
может иметь
более простую реализацию.
Отметим, что в ОРС элементы задержки почти образуют цепочку, что
может иметь значение в ряде приложений.
В заключение отметим, что предлагаемый авторами ОРС может быть ис-
пользован при построении универсальных и специализированных устройств
обработки дискретной информации.
100 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 2
