Находят одноэквивалентные разбиения состояний автомата

1. Находят одноэквивалентные разбиения состояний автомата

2. Строим таблицу пар. Строки таблицы пар помечены парами одноэквивалентных состояний, столбцы – входными сигналами. На пересечении строк и столбцов в таблице пар записываются пары состояний, которые являются первоприемниками по отношению к конкретному входному сигналу.

3. Последовательно по строкам отыскиваются отличающиеся пары состояний, которые отсутствуют в первом основном столбце таблицы пар. Если в какой-либо строке имеется хотя бы одна такая пара, то в этой строке зачеркивается пара в первом столбце. Такие строки, в которых зачеркнуты пары в первом столбце, называются выделенными строками.

4. Находятся невыделенные строки, в которых имеются пары, вычеркнутые в первом столбце на предыдущем этапе. Если такие строки имеются, то для них зачеркиваются пары в первом столбце. Такой процесс повторяется до тех пор, пока на очередном этапе не обнаруживаются невыделенные строки, в которых имеются пары, вычеркнутые в первом столбце на предыдущем этапе.

5. Оставшиеся незачеркнутые пары в первом столбце таблицы образуют все пары эквивалентных состояний.

Билет №15

Алгоритм минимизации ЦА Мура с помощью таблицы пар. Задача минимизации. Алгоритм. Пример.

Алгоритм:

1. Находят 0-эквивалентные разбиения состояний автомата

2. Строим таблицу пар. Строки таблицы пар помечены парами одноэквивалентных состояний, столбцы – входными сигналами. На пересечении строк и столбцов в таблице пар записываются пары состояний, которые являются первоприемниками по отношению к конкретному входному сигналу.

3. Последовательно по строкам отыскиваются отличающиеся пары состояний, которые отсутствуют в первом основном столбце таблицы пар. Если в какой-либо строке имеется хотя бы одна такая пара, то в этой строке зачеркивается пара в первом столбце. Такие строки, в которых зачеркнуты пары в первом столбце, называются выделенными строками.

4. Находятся невыделенные строки, в которых имеются пары, вычеркнутые в первом столбце на предыдущем этапе. Если такие строки имеются, то для них зачеркиваются пары в первом столбце. Такой процесс повторяется до тех пор, пока на очередном этапе не обнаруживаются невыделенные строки, в которых имеются пары, вычеркнутые в первом столбце на предыдущем этапе.

5. Оставшиеся незачеркнутые пары в первом столбце таблицы образуют все пары эквивалентных состояний.

Билет №16

Синтез автоматов без памяти. Основные понятия: КС, логический элемент, функциональная схема, базис. Задачи анализа и синтеза комбинационных логических схем (КЛС). Примеры.

Реализуемый в этих автоматах способ обработки информации называют комбинационным, а сами автоматы без памяти – комбинационными схемами. КС состоит из логических элементов и реализует булеву функцию или совокупность булевых функций.

Логический элемент: простейшая функциональная единица ЭВМ, реализующая одну элементарную булеву функцию. ЛЭ характеризуются определенными техническими параметрами: а) Коэффициент объединения по входу, показывающий какое число входов имеет логический элемент б) Коэффициент разветвления по выходу характеризующий количество входов логических элементов в) Среднее время задержки распространения сигнала в логическом элементе.

Базис: (совокупность) элементов, выбранных для синтеза КС, всегда должен быть функционально полным, т.е. допускать реализацию любой булевой функции на основе принципа суперпозиции.

Задача анализа: заданной КС сводится к отысканию булевой функции или системы булевых функций, описывающих работу этой схемы, с помощью аппарата алгебры логики.

Задача синтеза: КС состоит в построении оптимальной схемы проектируемого узла устройства, исходя из физического описания его работы.

Билет №17

Основные этапы проектирования автоматов без памяти – КЛС. Критерии качества технической реализации КЛС: сложность оборудования (цена схемы), быстродействие, надежность, минимум применяемых элементов. Пример синтеза КЛС.

Основные этапы синтеза: 1. Анализ технического задания и составление таблицы истинности.

2. Минимизация логических функций.

3. Преобразование минимальных логических функций для рациональной реализации логической схемы в заданном базисе.

4. Построение функциональной схемы.

5. Проверка работоспособности схемы и ее корректировка.

Критерии качества технической реализации: Сложность (цена) схемы по Квайну: Определяется суммарным числом входов логических элементов в составе схемы.

Быстродействие: Оценивается максимальной задержкой распространения сигнала при прохождении его от входа схемы к выходу.

Надежность: Оценивается интенсивностью отказов: λ = n/N*t, где n – количество элементов, вышедших из строя за период испытаний t, N- общее количество элементов.

Билет №18

Синтез КЛС в булевом базисе, базисах И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ. Правила преобразования для рациональной реализации. Пример.

Задача синтеза схемы состоит в преобразовании описывающих ее логических функций в суперпозицию логических элементов заданного типа.

И,ИЛИ,НЕ: В этом случае функция представляется в виде суперпозиции операторов логических элементов И (конъюнкторов), это a1, b1, c1, d1, и оператора логического элемента ИЛИ

И-НЕ: Для реализации исходной булевой функции на элементах И-НЕ необходимо от МДНФ функции взять двойное отрицание и одно из них раскрыть по правилу де Моргана, избавляясь от дизъюнкции между элементарными конъюнкциями.

В этом случае функция представлена в виде суперпозиции только операторов И-НЕ

ИЛИ-НЕ: Для реализации исходной булевой функции на элементах ИЛИ-НЕ необходимо от МКНФ функции взять двойное отрицание и одно из них раскрыть по правилу де Моргана, избавляясь конъюнкции между элементарными дизъюнкциями.

В этом случае функция представлена в виде суперпозиции только операторов ИЛИ-НЕ.

И-ИЛИ-НЕ: Для построения схемы необходимо получить МКНФ в виде МДНФ отрицания функции и в случае необходимости преобразовать.

Билет №19

Дешифраторы: определение, условное графическое обозначение, табличное и аналитическое описание. Синтез КЛС на основе дешифраторов. Примеры.

Дешифратором называется КС, имеющая n входов и 2 в степени n выходов, осуществляющая преобразование входного двоичного n-разрядного кода в сигнал на одном из выходов. Различают полные и неполные дешифраторы. Число выходов полного Д. N = 2ⁿ , неполного – N < 2ⁿ.

Аналитическое описание: Yi = αi * E, i = 0, 1, ..., n, где αi – i-й минтерм n входных переменных; Е – сигнал, разрешающий дешифрирование.

Синтез КЛС на основе дешифратора: Для получения схемы достаточно определить выходы дешифратора, соответствующие входящим в функцию конституентам единицы и соединить их с входами дизъюнктора. Если на входы дешифратора будут поданы входные переменные, то на выходе дизъюнктора сформируется значение функции.

Билет №20

Мультиплексоры: определение, условное графическое обозначение, табличное и аналитическое описание. Синтез КЛС на основе мультиплексоров. Примеры.

Мультиплексор – адресный коммутатор, который может выполнить коммутацию на выход сигнала с того информационного входа, адрес которого задан сигналами на адресных входах.

Аналитическое описание: Y = v Xi αiE, i = 0, 1, ..., 2ⁿ- 1, где αi – минтерм (конституента 1), соответствующий i – му адресному набору. Данная функция далее может быть реализована в заданном базисе элементов.

Синтез КЛС на основе мультиплексоров: Мультиплексор можно использовать для преобразования параллельной информации в последовательную, если последовательно задавать адреса разрядов кода числа. Мультиплексор на большое число входов, как правило, приходится строить из мультиплексоров меньшей размерности. «8-1» На адресные входы подаются входные переменные, а информационные входы, соответствующие входящим в функцию конституентам единицы, соединяются с шинами питания, остальные инф. входы соединяются с шинами земли. На выходе мультиплексора формируется значение функции. «4-1» В качестве управляющих сигналов используются переменные, которые подаются на адресные входы мультиплексора. На инф. входы поступают переменные.

 

Билет №21

Задача структурного синтеза автоматов с памятью. Канонический метод структурного синтеза. Теорема о структурной полноте. Структурная схема С-автомата.

Задача структурного синтеза: В общем случае задача структурного синтеза автоматов с памятью сводится к нахождению общих приемов построения структурной схемы полученного на этапе абстрактного синтеза автомата Мили, Мура или С-автомата на основе композиции некоторых элементарных автоматов специального вида.

Канонический метод синтеза позволяет свести задачу структурного синтеза произвольного автомата с памятью к задаче синтеза КС. Он оперирует с элементарными автоматами, разделяющимися на два больших класса. Первый класс составляют элементарные автоматы с памятью, называемые элементами памяти. Второй класс составляют элементарные комбинационные автоматы – логические элементы.

Теорема о структурной полноте: Всякая система элементарных автоматов, которая содержит автомат Мура, обладающий полной системой переходов и выходов, и какую-либо функционально-полную систему логических элементов, является структурно полной (Глушков В.М.).

Билет №22

Основные этапы канонического метода структурного синтеза автоматов с памятью. Особенности синтеза автоматов Мили и Мура. Пример.

Основные этапы канонического метода: 1. Переход на структурный уровень, т.е. кодирование входных, выходных сигналов и состояний автомата. При этом каждая буква алфавитов A,Z,w,u кодируется двоичными векторами (наборами), длина которых равна числу физически реализованных входных и выходных каналов ( для z,w,u) и числу элементов памяти. При этом две различные буквы одного и того же алфавита должны кодироваться различными двоичными векторами.

2. Выбор элементов памяти автомата. Для правильной работы схемы нельзя допустить, чтобы сигналы на входах элементов памяти участвовали в формировании сигналов, которые по цепям обратной связи подавались бы в тот же самый момент времени на эти входы. В связи с этим элементами памяти должны быть не автоматы Мили, а автоматы Мура, имеющие полную систему переходов и полную систему выходов.

3. Выбор функционально полной системы логических элементов. Система логических элементов должна быть функционально полной.

4. Построение булевых ф-ций возбуждения памяти и ф-ции выхода ( СКУ и СВФ). Получение булевых ф-ций выходов не зависит от типа используемых элементов памяти и может быть сделано непосредственно по структурной таблице выходов автомата. Для построения ф-ций возбуждения памяти, в начале строится таблица ф-ции возбуждения памяти по которой записываются канонические уравнения ф-ции возбуждения. Для построения этой таблицы используется структурная таблица переходов автомата и ф-ция входов, используемого триггера.

5. Построение функциональной схемы автомата. Полученная на этапе 4 СКУ и СВФ, преобразуется для рациональной реализации в выбранном базисе и строится функциональная схема структурного автомата.

Особенности синтеза автоматов Мили и Мура:

 

Билет №24

Гонки в ЦА. Аппаратные и логические методы устранения гонок.

Если при переходе автомата из одного состояния в другое должны изменить свои состояния сразу несколько запоминающих элементов, то между ними начинаются состязания, или гонки. Тот элемент, который выиграет эти состязания, т.е. изменит свое состояние ранее, чем другие элементы, может через цепь обратной связи изменить сигналы на входах некоторых запоминающих элементов до того, как другие, участвующие в состязаниях элементы изменят свои состояния. Это может привести к переходу автомата в состояние, не предусмотренное законом функционирования. Гонки в автомате связаны с разбросом во временных параметрах сигналов, проходящих через логические и запоминающие элементы, и имеют место в любой реальной логической схеме. Для обеспечения заданного закона функционирования автомата необходимо исключить возможность появления критических гонок.

Аппаратные методы:

Импульсная синхронизация: гонки устраняются путем ограничения длительности сигнала с, поступающего в цепь синхронизации.

Использование Двойной (двухступенчатой) памяти: Заключается в разделении во времени процессов выработки сигналов возбуждения и процесса переключения состояний.

Логические методы:

Соседнее кодирование: Способ кодирования состояний, при котором соседние состояния автомата кодируются наборами, различающимися состоянием только одного элемента памяти.