Реферат: Шпоры по теории автоматов
Мультиплексор – адресный коммутатор, который может выполнить коммутацию на выход сигнала с того информационного входа, адрес которого задан сигналами на адресных входах.
Аналитическое описание : Y = v Xi αiE, i = 0, 1, ..., 2n - 1, где αi – минтерм (конституента 1), соответствующий i – му адресному набору. Данная функция далее может быть реализована в заданном базисе элементов.
Синтез КЛС на основе мультиплексоров : Мультиплексор можно использовать для преобразования параллельной информации в последовательную, если последовательно задавать адреса разрядов кода числа. Мультиплексор на большое число входов, как правило, приходится строить из мультиплексоров меньшей размерности. «8-1» На адресные входы подаются входные переменные, а информационные входы, соответствующие входящим в функцию конституентам единицы, соединяются с шинами питания, остальные инф. входы соединяются с шинами земли. На выходе мультиплексора формируется значение функции. «4-1» В качестве управляющих сигналов используются переменные, которые подаются на адресные входы мультиплексора. На инф. входы поступают переменные.
Билет №21
Задача структурного синтеза автоматов с памятью. Канонический метод структурного синтеза. Теорема о структурной полноте. Структурная схема С-автомата.
Задача структурного синтеза : В общем случае задача структурного синтеза автоматов с памятью сводится к нахождению общих приемов построения структурной схемы полученного на этапе абстрактного синтеза автомата Мили, Мура или С-автомата на основе композиции некоторых элементарных автоматов специального вида.
Канонический метод синтеза позволяет свести задачу структурного синтеза произвольного автомата с памятью к задаче синтеза КС. Он оперирует с элементарными автоматами, разделяющимися на два больших класса. Первый класс составляют элементарные автоматы с памятью, называемые элементами памяти. Второй класс составляют элементарные комбинационные автоматы – логические элементы.
Теорема о структурной полноте : Всякая система элементарных автоматов, которая содержит автомат Мура, обладающий полной системой переходов и выходов, и какую-либо функционально-полную систему логических элементов, является структурно полной (Глушков В.М.).
Билет №22
Основные этапы канонического метода структурного синтеза автоматов с памятью. Особенности синтеза автоматов Мили и Мура. Пример.
Основные этапы канонического метода : 1. Переход на структурный уровень, т.е. кодирование входных, выходных сигналов и состояний автомата. При этом каждая буква алфавитов A,Z,w,u кодируется двоичными векторами (наборами), длина которых равна числу физически реализованных входных и выходных каналов ( для z,w,u) и числу элементов памяти. При этом две различные буквы одного и того же алфавита должны кодироваться различными двоичными векторами.
2. Выбор элементов памяти автомата. Для правильной работы схемы нельзя допустить, чтобы сигналы на входах элементов памяти участвовали в формировании сигналов, которые по цепям обратной связи подавались бы в тот же самый момент времени на эти входы. В связи с этим элементами памяти должны быть не автоматы Мили, а автоматы Мура, имеющие полную систему переходов и полную систему выходов.
3. Выбор функционально полной системы логических элементов. Система логических элементов должна быть функционально полной.
4. Построение булевых ф-ций возбуждения памяти и ф-ции выхода ( СКУ и СВФ). Получение булевых ф-ций выходов не зависит от типа используемых элементов памяти и может быть сделано непосредственно по структурной таблице выходов автомата. Для построения ф-ций возбуждения памяти, в начале строится таблица ф-ции возбуждения памяти по которой записываются канонические уравнения ф-ции возбуждения. Для построения этой таблицы используется структурная таблица переходов автомата и ф-ция входов, используемого триггера.
5. Построение функциональной схемы автомата. Полученная на этапе 4 СКУ и СВФ, преобразуется для рациональной реализации в выбранном базисе и строится функциональная схема структурного автомата.
Особенности синтеза автоматов Мили и Мура :
Билет №24
Гонки в ЦА. Аппаратные и логические методы устранения гонок.
Если при переходе автомата из одного состояния в другое должны изменить свои состояния сразу несколько запоминающих элементов, то между ними начинаются состязания, или гонки. Тот элемент, который выиграет эти состязания, т.е. изменит свое состояние ранее, чем другие элементы, может через цепь обратной связи изменить сигналы на входах некоторых запоминающих элементов до того, как другие, участвующие в состязаниях элементы изменят свои состояния. Это может привести к переходу автомата в состояние, не предусмотренное законом функционирования. Гонки в автомате связаны с разбросом во временных параметрах сигналов, проходящих через логические и запоминающие элементы, и имеют место в любой реальной логической схеме. Для обеспечения заданного закона функционирования автомата необходимо исключить возможность появления критических гонок.
Аппаратные методы:
Импульсная синхронизация : гонки устраняются путем ограничения длительности сигнала с, поступающего в цепь синхронизации.
Использование Двойной (двухступенчатой) памяти : Заключается в разделении во времени процессов выработки сигналов возбуждения и процесса переключения состояний.
Логические методы :
Соседнее кодирование : Способ кодирования состояний, при котором соседние состояния автомата кодируются наборами, различающимися состоянием только одного элемента памяти.