КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
Теорема о преобразовании периодической последовательности автоматной функцией Понятие ограниченно детерминированной функции Пусть даны алфавиты: входной и выходной. Обозначим и как множества всех возможных последовательностей в алфавитах и соответственно. Определение 1. Отображение → называется детерминированной функцией, если любой член выходная последовательности для любого однозначно определяется предшествующими значениями входной последовательности. Функция, осуществляющая отображения двух входных последовательностей
будет детерминированной функцией, при условиях: 1) если, то и 2) если,то. Определение 2. Пусть задана детерминированная функция →. Пусть далее имеется произвольное входное слово. Функция при произвольной входной последовательности даёт следующий результат: , При этом вводится функция →, осуществляющая отображение . Она называется остаточной функцией по слову. Определение 3. Детерминированная функция → называется ограниченно-детерминированной функцией, если у нее имеется лишь конечное число различных остаточных функций. Рассмотрим автомат (A,S,B,φ,,) где A,S,B — конечные алфавиты (входной, выходной и состояния), - переходная функция, - выходная и - начальное состояние. Входом автомата служит последовательность (конечная или бесконечная), выходом автомата служит последовательность. При этом автомат задается системой канонических уравнений:
В результате работы конечного автомата бесконечная последовательность преобразуется в бесконечную последовательность. Таким образом, автомат определяет некоторую функцию, которая называется отображением, осуществляемым конечным автоматом.
Определение 4. Отображение,называется автоматной функцией, если существует автомат, который реализует это отображение. Справедливо утверждение: функция является автоматной тогда и только тогда, когда она ограниченно детерминированная. Пример: Пусть задан автомат с алфавитами, а его система канонических уравнений выглядит следующим образом:
Такой автомат осуществляет отображение
и называется единичной задержкой. При этом последовательности входа, состояния и выхода меняются следующим образом Таблица 12 Пусть - автоматная функция веса r. Тогда для каждой входной периодической последовательности с периодом T она выдаёт выходную периодическую последовательность, период которой / Определение. Схемой из функциональных элементов и элементов задержки (СФЭЗ) называется схема, содержащая элементы некоторой функционально полной системы булевых функций, к которой добавлены элементы, реализующие функцию единичной задержки. В СФЭЗ допускаются ориентированные циклы, но любой ориентированный цикл должен проходить хотя бы через одну задержку. Заметим что, схема из функциональных элементов и задержки осуществляет автоматное отображение. Определение. Пусть автоматная функция отображает последовательность конечного базиса в последовательность конечного базиса. При \этом СФЭЗ Σ осуществляет преобразование последовательностей булевых векторов длины в последовательности булевых векторов длины. Говорят, что Σ моделирует, если существуют отображения (кодировки) и, которые сопоставляют разным элементам алфавита разные векторы. Отображения и таковы, что если, то при любой последовательности из алфавита Здесь использовано обозначение. Следует иметь ввиду, что для любого конечного автомата существует моделирующая его СФЭЗ в функционально полной системе, содержащей элементы дизъюнкции, конъюнкции, отрицания, а также элемента задержки.
Для осуществления такого моделирования необходимо задать конечный автомат системой булевых функций. Алгоритм задания конечного автомата системой булевых функций. 1) Находим число разрядов, необходимых для двоичного представления чисел, и. Соответствующие числа находятся из условий -;;. 2) Кодирование состояний, входных и выходных символов исходного автомата. Каждому состоянию ставится в соответствие двоичная последовательность длины - двоичный код. Аналогично каждому и каждому ставятся в соответствие двоичные последовательности. Отметим, что кодирование может быть осуществлено различными способами. При этом может оказаться, что некоторые коды не используются. 3) Составляется следующая таблица: Таблица 13
Дата добавления: 2014-01-11; Просмотров: 1819; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |