символов входного алфавита (входные последовательности) в последователь-
ности выходного алфавита той же длины. Символы поступают (и считыва-
ются) в дискретные моменты времени, определяемые генератором тактовых
импульсов. Устройство может находиться в одном из своих (внутренних)
состояний. Число состояний конечно. В каждый момент времени выходной
символ и состояние в следующий момент времени однозначно определяются
входным символом и текущим состоянием. Математической моделью после-
довательностных устройств являются конечные автоматы.
Наиболее часто последовательностные схемы строят из функциональ-
ных элементов (реализующих преобразования, не зависящие от времени) и
триггеров. Значение выхода триггера при подаче тактового импульса (т.е. в
следующий момент времени) равно значению его входа в текущий момент
времени.
Целью работы является расширение функциональных возможностей од-
нонаправленного регистра сдвига с последовательным вводом и параллель-
ным выводом, являющегося последовательным соединением триггеров [1].
Регистры сдвига часто используют для обработки информации. Напри-
мер, при выполнении арифметических операций операнды загружаются в
регистры сдвига; значения результата операции вычисляют как функции зна-
чений выходов регистров сдвига.
В качестве особенности обычного регистра сдвига отметим следующее.
Состоянием триггера считают значение его выхода, а состоянием регистра
сдвига — упорядоченный набор состояний его элементов (триггеров). При
анализе цифровых устройств с памятью часто время полагают дискретным,
равным числу поданных тактовых импульсов от начала работы устройства.
Триггер из любого состояния может перейти при подаче тактового импульса
(т.е. в следующий момент времени) в любое состояние (в зависимости от
значения входа). Однако
n
-разрядный регистр сдвига в алфавите мощности
M
при любом
n
≥
2
в следующий момент времени может перейти только
в
M
состояний, такой регистр сдвига имеет
M
n
состояний. Известно, что
устройства, в схеме которых все элементы памяти находятся в одном регистре
сдвига, реализуют узкий класс последовательностных отображений.
Предлагаемое устройство назовем обобщенным регистром сдвига (ОРС).
Оно может переходить в следующий (дискретный) момент времени из любо-
го состояния в любое свое состояние. При этом при любой последовательно-
сти значений входов обобщенного регистра сдвига на его основном выходе в
любой момент времени
t
реализуется перестановка значений его основного
входа в момент времени
t
−
n
, где
n
— разрядность регистра сдвига. Отме-
тим, что авторы хотели назвать ОРС управляемым регистром сдвига, но это
понятие уже имеет другой смысл.
Поставленная задача решается следующим образом. Обобщенный ре-
гистр сдвига состоит из
n
триггеров и
n
−
1
функциональных элементов
с двумя входами и одним выходом, реализующих функцию, которая при
любом фиксированном аргументе является перестановкой другого аргумен-
та, кроме того, среди перестановок первого аргумента имеется тождествен-
ная перестановка (такой функцией является, например, сложение по модулю
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 2 97
