мощности алфавита регистра). Входом ОРС является вход первого триггера.
Выход каждого триггера, кроме последнего, присоединяется к первому входу
функционального элемента. Вторые входы функциональных элементов суть
управляющие входы обобщенного регистра сдвига. Выход функционального
элемента присоединяется к входу следующего триггера. Выходы триггеров,
кроме последнего, являются выходами обобщенного регистра сдвига. Основ-
ным выходом обобщенного триггера является выход последнего триггера.
Нетрудно проверить, что предлагаемое устройство (
n
-разрядный ОРС)
обладает объявленным свойством. А именно, из любого состояния он может
перейти в следующий момент времени в любое другое свое состояние. По-
скольку суперпозиция перестановок является перестановкой, ОРС обладает
следующим свойством. При любой последовательности значений управля-
ющих входов обобщенного регистра сдвига на основном выходе в любой
момент времени
t
реализуется перестановка значений его основного входа
в момент времени
t
−
n
, где
n
— разрядность регистра. Отметим, что если
функциональные элементы ОРС реализует сумму значений их входов по мо-
дулю мощности алфавита, то при значениях управляющих входов, равных
нулю, функционирование
n
-разрядного ОРС совпадает с функционировани-
ем обычного
n
-разрядного регистра сдвига.
На рисунке показана схема ОРС.
Входом
3
ОРС является вход первого триггера. Выход
7
каждого триг-
гера, кроме последнего, присоединяется к первому входу функционального
элемента. Вторые входы
6
функциональных элементов суть управляющие
входы ОРС. Выход функционального элемента
2
присоединяется к входу
следующего триггера. Выходы
7
триггеров, кроме последнего, являются вы-
ходами ОРС. Основным выходом
4
обобщенного триггера является выход
последнего триггера.
Докажем теперь еще одно свойство ОРС: любое последовательностное
устройство в алфавите
A
мощности
M
, имеющее не более
M
n
состояний,
можно реализовать с использованием функциональных элементов и одного
n
-разрядного ОРС в алфавите
A
.
Доказательство проведем с использованием теории конечных автоматов.
Для простоты изложения ограничимся рассмотрением автоматных бази-
сов в алфавите {0, 1}, состоящих из функционально полной системы элемен-
тов с одним состоянием и элемента единичной задержки.
Блок-схема ОРС:
1
— триггер;
2
— функциональный элемент;
3
— вход;
4
— основной выход;
5
—
тактовый вход;
6
— управляющие входы;
7
— выходы
98 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 2
