Обобщенный регистр сдвига

Рассмотрен вопрос расширения элементной базы проектирования дискретных устройств с памятью. Предложено устройство (обобщенный регистр сдвига), которое существенно увеличивает возможности однонаправленного регистра сдвига с последовательным вводом и параллельным выводом, являющегося последовательным соединением триггеров. Триггер из любого состояния может перейти при подаче тактового импульса (т.е. в следующий момент времени) в любое состояние (в зависимости от значения входа). Однако n-разрядный регистр сдвига в алфавите мощности M при любом n ≥ 2 в следующий момент времени может перейти только в M состояний. Отмечено, что такой регистр сдвига имеет Mⁿ состояний. Известно, что устройства, в схеме которых все элементы памяти находятся в одном регистре сдвига, реализуют узкий класс отображений. Показано, что любое последовательное устройство можно реализовать схемой из функциональных элементов и одного обобщенного регистра сдвига.

Литература

[1] Джон Ф. Уэйкерли. Проектирование цифровых устройств. Т. 1,2 / пер. с англ. Е.В. Воронова, А.Л. Ларина. М.: ПОСТМАРКЕТ, 2002. 1088 с.

[2] Трахтенброт Б.А. Асимптотическая оценка сложности логических сетей с памятью // Докл. АН СССР. 1959. Т. 127. № 2. С. 281-284.

[3] Трахтенброт Б.А. О сложности схем, реализующих многопараметрические семейства операторов: Сб. "Проблемы кибернетики". М.: Наука, 1964. Вып. 12. С. 99-112.

[4] Орлов В.А. Алгоритмическая неразрешимость задачи нахождения асимптотического поведения функции Шеннона при реализации ограниченно-детерминированных операторов схемами в произвольном базисе // Докл. АН СССР. 1971. Т 196. № 5. С. 1036-1039.

[5] Орлов В.А. Об особенностях поведения функции Шеннона в случае автоматных базисов // Математические заметки. 1972. Т. 11. Вып. 1. С. 73-82.

[6] Орлов В.А. О реализации функций схемами и формулами в функционально полных базисах // Докл. РАН. 1999. Т. 365. № 6. С. 734-735.