Билет №7
Задание ЦА на языке логических схем алгоритмов (ЛСА) и построение на его основе СКУ и СВФ.
Язык ЛСА является аналитической интерпретацией языка ГСА и может быть использован для более компактной формы записи алгоритма функционирования ЦА. Запись алгоритма на языке ЛСА представляет собой конечную строку, состоящую из символов операторов А = {A0, A1,...,Ak}, логических условий X={x1,...,xl} и верхних и нижних стрелок, которым приписаны натуральные числа. В некоторых случаях используются логические, которые всегда принимают нулевое значение, т.е. тождественно ложные логические условия ω (оператор ω). После оператора ω всегда производится переход по стрелке, которая стоит справа от него. Если в ЛСА имеются циклы из логических условий, то вводится пустой оператор Ae(Ye), отмеченный пустым выходным сигналом. Этот оператор помещают в ЛСА путем замены стрелки i, стоящей в начале петли из логических условий на следующую группу символов ЛСА: ω↑k↓iAe(Ye)↓k.
Билет №12
Минимизация полностью определенных автоматов Мили методом Ауфенкампа и Хона. Задача минимизации. Алгоритм. Пример.
Основная идея этого метода состоит в разбиении всех состояний исходного автомата на попарно непересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием. Получающийся в результате минимизации автомат имеет столько же состояний, на сколько классов эквивалентности разбиваются состояния исходного автомата.
Состояния am и as являются эквивалентными, если λ(am, ξ) = λ(as, ξ) для всевозможных входных слов ξ.
Алгоритм: 1. Находим последовательные разбиения п1, п2, …, пк, пк+1 множества А на классы одно-, двух-, К-, К+1- эквивалентных состояний до тех пор, пока в каком-то (К+1) шаге не окажется, что пк = пк+1.
2. В каждом классе эквивалентности разбиения п выбирается по одному состоянию, в результате чего получаем множество А’ состояний минимального автомата S’ = {A’,z,w,σ’,λ’,a1’} эквивалентному автомату S.
3. Для определения функции переходов и выходов автомата S’ в таблице переходов и выходов вычеркиваются столбцы, соответствующие не вошедшим в А’ состояниям. В оставшихся столбцах не вошедшие в множество А состояния заменяются на эквивалентные.
4. В качестве начального состояния а1’ выбирается состояние из множества А’, эквивалентное состоянию а1. В частности, удобно за а1’ принимать само состояние а1.
Билет №13
Минимизация полностью определенных автоматов Мура методом Ауфенкампа и Хона. Задача минимизации. Алгоритм. Пример.
Основная идея этого метода состоит в разбиении всех состояний исходного автомата на попарно непересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием. Получающийся в результате минимизации автомат имеет столько же состояний, на сколько классов эквивалентности разбиваются состояния исходного автомата.
Состояния am и as являются эквивалентными, если λ(am, ξ) = λ(as, ξ) для всевозможных входных слов ξ.
Алгоритм: При минимизации полностью определенных автоматов Мура вводится понятие 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
Синтез КЛС в булевом базисе, базисах И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ. Правила преобразования для рациональной реализации. Пример.
Задача синтеза схемы состоит в преобразовании описывающих ее логических функций в суперпозицию логических элементов заданного типа.