135719 (722557), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Алгоритм: При минимизации полностью определенных автоматов Мура вводится понятие 0-эквивалентности состояний и разбиение множества состояний на 0-эквивалентные классы. 0-эквивалентными являются одинаково отмеченные состояния. Если два состояния автомата Мура 0-эквивалентны и под действием одинаковых входных сигналов попадают в 0-эквивалентные состояния, то они называются 1-эквивалентными. Все дальнейшие классы эквивалентности для автомата Мура определяются аналогично, как для автомата Мили

1. Находим последовательные разбиения п1, п2, …, пк, пк+1 множества А на классы одно-, двух-, К-, К+1- эквивалентных состояний до тех пор, пока в каком-то (К+1) шаге не окажется, что пк = пк+1.

2. В каждом классе эквивалентности разбиения п выбирается по одному состоянию, в результате чего получаем множество А’ состояний минимального автомата S’ = {A’,z,w,?’,?’,a1’} эквивалентному автомату S.

3. Для определения функции переходов и выходов автомата S’ в таблице переходов и выходов вычеркиваются столбцы, соответствующие не вошедшим в А’ состояниям. В оставшихся столбцах не вошедшие в множество А состояния заменяются на эквивалентные.

4. В качестве начального состояния а1’ выбирается состояние из множества А’, эквивалентное состоянию а1. В частности, удобно за а1’ принимать само состояние а1.

Билет №14

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

Алгоритм:

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

Характеристики

Список файлов реферата