Страница: 4/6
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, и оператора логического элемента ИЛИ
И-НЕ: Для реализации исходной булевой функции на элементах И-НЕ необходимо от МДНФ функции взять двойное отрицание и одно из них раскрыть по правилу де Моргана, избавляясь от дизъюнкции между элементарными конъюнкциями.
В этом случае функция представлена в виде суперпозиции только операторов И-НЕ
ИЛИ-НЕ: Для реализации исходной булевой функции на элементах ИЛИ-НЕ необходимо от МКНФ функции взять двойное отрицание и одно из них раскрыть по правилу де Моргана, избавляясь конъюнкции между элементарными дизъюнкциями.
Реферат опубликован: 24/03/2006