Этапы графического метода синтеза структурного автомата:
Определение структуры структурного автомата.
Находим количество элементов памяти  , ( M - число состояний абстрактного автомата) и закодируем состояния абстрактного автомата.
Кодируем входные и выходные сигналы.
Структурный автомат представляем обобщенной схемой.
Составление уравнений выходных функций.
Представляем закодированный граф абстрактного автомата, то есть вместо состояний автомата указываются соответствующие кодовые комбинации, а входные сигналы указываются на переходах своими логическими кодовыми комбинациями. Логические кодовые комбинации выходных сигналов 1 рода записываются на переходах, а сигналы 2 рода записываются как метки состояний (или внутри вершины графа). Причем для выходных функций следует указывать только те значения функций, которые принимают истинные значения, по которым составляются уравнения выходов.
Составление уравнений функций возбуждения.
На закодированном графе на дугах перехода указываем функции возбуждения, которые соответствуют переключению триггеров, причем следует указывать только те значения функций, которые принимают истинные значения, по которым составляются уравнения функций возбуждения.
Уравнения функций возбуждения и выходов минимизируются (по картам Карно, например) и по ним строится схема в заданном функционально - логическом базисе ({И, ИЛИ, НЕ}, {И-НЕ}, {ИЛИ-НЕ} ).
_____________________Вопрос 13____________________
_____________________Вопрос 14____________________
Синтез комбинационных схем на ПЗУ
ПЗУ представляет собой память, программируемую 1 раз(например, при изготовлении). Записанная информация сохраняется в течение всего времени эксплуатации. ПЗУ имеет k адресных входов и n выходов.->Можно записать 2^k n-разрядных двоичных слов. Большое распространение для синтеза комб. сх. получили программируемые логические матрицы. ПЛМ представляют собой множество связанных м/у собой определенным образом дизъюнктеров и конъюнктеров. Перед программированием имеет вид как:
x- электрические соединения, некот-е при програм-е ПЛМ уничтожаются. НА выходе в зависимости от уничтожения или сохранения x связи, можно получить как прямое, так и инверсное значение ф-ции. Лог. характ-й ПЛМ (n,p,k) n- число входов, p- число выходов, k- число конъюнктеров.n,p- столбцы, k-строки. Площадь N=(n+p)*k. Структурно ПЛМ - 2 матрицы M1(реализует k всевозможных конъюнкции от n переменных) и M2(p всевозможных дизъюнкций от k переменных)
2 задачи синтеза:
реализовать схему, минимизируя площадь ПЛМ
реализовать схему на минимальном числе ПЛМ с известными параметрами(n,p,k)
_____________________Вопрос 15____________________
Свойства функции “Штрих Шеффера” и “Стрелка Пирса”
_____________________Вопрос 16____________________
Дешифратор в цепи ОС структурного автомата
Дешифраторы и шифраторы (также, как и элементы И,ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ) являются комбинационными элементами: потенциалы на их выходах зависят от сиюминутного состояния входов, с их изменением меняется и ситуация на выходах; такие элементы не сохраняют предыдущее состояние после смены потенциалов на входах, т.е. не обладают памятью.
Дешифраторы могут быть полными и неполными. Полные дешифраторы реагируют на все входные коды, неполные – на коды, величина которых не превосходит некоторого заранее установленного значения. Выходы дешифраторов могут быть прямыми и инверсными. Дешифратор называется полным, если он имеет количество выходов m, связанных с количеством разрядов n входного двоичного числа следующим соотношением:
m=2n
Дешифратор, у которого при n входах число выходов меньше 2n (m<2n), называется неполным.
_____________________Вопрос 17____________________
Классы логических функций
Базис - полная система функций алгебры логики, с помощью которой любая функция может быть представлена суперпозицией исходных функций.
Базис 1. И, ИЛИ, НЕ (булевый).
Базис 2. И, НЕ.
Базис 3. ИЛИ, НЕ.
Базис 4. Штрих Шеффера.
Базис 5. Стрелка Пирса.
Из перечисления следует, что базисы могут быть избыточными(1) или минимальными(остальные). Так, из первого базиса может быть удалена функция “И” или “ИЛИ”, тогда будет осуществлен переход к базисам 3 или 2 соответственно. Для того чтобы ответить на вопрос, какие функции могут образовывать базис, необходимо установить некоторые свойства логических функций, определяемые их принадлежностью к классам функций.
Класс линейных функций (КЛ). Логическая функция называется линейной, если она представляется полиномом первой степени
Количество линейных функций равно 2n+1. Например, для n=2 количество линейных функций равно 8:
Класс функций, сохраняющих нуль(К0). Если функция на нулевом наборе переменных равна нулю, говорят, что функция сохраняет нуль: f(0, 0, …, 0) = 0.
Класс функций, сохраняющих единицу(К1). Если функция на единичном наборе переменных равна единице, говорят, что функция сохраняет единицу: f(1, 1, …, 1) = 0.
Класс монотонных функций(Км). Функция алгебры логики является монотонной, если при любом возрастании номера набора переменных значения этой функции не убывают.
Класс самодвойственных функций(Кс). Функция алгебры логики является самодвойственной, если выполняется равенство:  Названные классы функций обладают замечательным свойством: любая функция, полученная с помощью суперпозиции и подстановки из функций одного класса, будет принадлежать этому же классу.
Определим принадлежность функций, указанных в табл. 12.8,
описанным классам.
_____________________Вопрос 18____________________
Теорема Поста-Яблонского
Теорема Поста-Яблонского определяет необходимые и доста-
точные условия для получения базиса.
Чтобы система логических функций была полной (базисом), необходимо и достаточно, чтобы она содержала хотя бы одну функцию:
- не сохраняющую нуль;
- не сохраняющую единицу;
- не являющуюся линейной;
- не являющуюся монотонной;
- не являющуюся самодвойственной.
Как видно из таблицы, условиям теоремы Поста-Яблонского удовлетворяют только две функции: f8 - Стрелка Пирса и f14 Штрих Шеффера, которые обладают функциональной полнотой. Комбинации функций f11 и f12 или f4 и f9, а также некоторых других также образуют базисы. Наибольшее применение нашли описанные выше 5 базисов.
Для обозначения функций на логических принципиальных схемах используют специальные изображения:
_____________________Вопрос 19____________________
Состязания (гонки) в автоматах
Мат. аппарат исп-й при синтезе автоматов, строится на основе булевой алгебры, в к-й не учит. реальное время срабатывания лог. элементов.Однако реальные процессы переключения элементов, реализующих логические зависимости, происходит во времени с конечными задержками,если при синтезе автомата не учитывать фактор времени, то работа автомата может быть неправильной. Состязания или гонки - ситуация, при которых может появится риск сбоя. Критические состязания - состязания, приводящие автомат в устойчивые состояния, не предусмотренные законом функционирования.
Переключение автомата в следующее состояние производится сигналами возбуждения, вырабатываемыми в комбинационной части автомата и поступающими на входы триггеров запоминающей части. Если при переходе автомата из состояния аi в состояние аj несколько триггеров должны изменить свое состояние, то из-за различия моментах срабатывания могут начаться состязания. Тот триггер, который выиграет состязания, может через цепь обратной связи при определенных условиях изменить сигналы на входах остальных триггеров раньше, чем те изменят свое состояние. В результате гонок триггеры могут перейти в состояние, не соответствующее закону функционирования автомата, т.е. состояния будут критическими. Для искл-я опасных состяназний исп. спец. противогоночное кодирование либо аппаратные средства.К ним относят:1)выравнивание задержек по различным цепям распространения сигналов;2)импульсную синхронизацию; 3)двухступенчатую (двойную) память;4)апериодические схемы.
_____________________Вопрос 20____________________
Аппаратные противогоночные средства: импульсная синхронизация, двойная память, апериодические схемы.
Для искл-я опасных состяназний исп. спец. противогоночное кодирование либо аппаратные средства.К ним относят:1)выравнивание задержек по различным цепям распространения сигналов;2)импульсную синхронизацию; 3)двухступенчатую (двойную) память;4)апериодические схемы.
1)Метод выравнивания задержек состоит в том, что в более быстрые цепи включаются дополнительные логические элементы, не изменяющие логику работы цепи, но увеличивающие время прохождения сигнала по ней.2)В методе импульсной синхронизации в качестве ЭП используются синхронные элементарные автоматы. В них имеется вход синхронизации, и как бы ни менялись управляющие входы триггера, при наличии запрета на этом входе состояние триггера не изменится. 3)В автомате с 2ой памятью гонки устраняются путем разделения во времени процесса выработки сигналов возбуждения и процесса переключения состояний.В качестве элементов памяти исп. MS-триггеры. 4) При использовании апериодической схемотехники проблема гонок решается полностью. Внешняя синхронизация отсутствует, поэтому такие схемы иногда называют самосинхронизирующимися. Идея самосинхронизации состоит в том, что в схеме определяются точки, в которых сходятся сигналы, получившие разные задержки в процессе их формирования, и в этих точках устанавливаются так называемые семафоры. Семафоры запрещают встречу всех сигналов до тех пор, пока не придет самый задержанный из них. Таким образом, распространение сигналов по цепям схемы, в том числе и ко входам элементов памяти, происходит по специальным разрешающим сигналам, формируемым самой схемой по фактическому времени задержек. Естественно, что в этом случае, кроме полного исключения эффекта гонок, достигается максимально возможное для данной схемы быстродействие
_______________Вопрос 21(совпадает с 45)______________
Связь между моделями Мура и Мили.
Между автоматами Мура и Мили существует однозначная связь - каждому автомату Мура можно поставить в соответствие эквивалентный автомат Мили и наоборот(эквивалентность автоматов - одинаковость реакций автоматов на все возможные цепочки входных символов).
Выходной сигнал wg, записанный в вершине as, переносится на все дуги, входящие в эту вершину. При табличном способе задания автомата Мура таблица переходов автомата Мили совпадает с таблицей переходов автомата Мура, а таблица выходов автомата Мили получается из таблицы переходов заменой символа as, стоящего на пересечении строки zf и столбца am, символом выходного сигнала wg, отмечающего столбец as в отмеченной таблице переходов автомата Мура.
Функцию выходов λs и переходов δs определим так. Каждому состоянию автомата Мура, представляющему собой пару вида (as, wg), поставим в соответствие выходной сигнал wg. Если в автомате Мили был переход δR(am,zf) = as и при этом выдавался выходной сигнал λR(am, zf) = wk, то в автомате Мура будет переход из множества состояний Am, порождаемых am, в состояние (as,wk) под действием того же входного сигнала zf :
Пример. Дан автомат Мили R(рис. 15.6). построить эквивалентный автомат Мура S.
 
___________________Вопрос 22____________________
Базисы логических фунций.
Базис (функционально полный набор) – это множество логических функций, суперпозицией которых можно представить любую логическую формулу, т. е. полная система логических функций.
Базисы могут быть избыточными и минимальными. Например, система функций И, Или, НЕ (булев базис, базис Буля) – избыточный базис, так как при удалении из него некоторых функций (функции ИЛИ или функции И) система остаётся полной.
Минимальными базисами являются системы: 1) И, НЕ; 2) ИЛИ, НЕ; 3) И-НЕ (базис Шеффера); 4) ИЛИ-НЕ (базис Пирса). При удалении из таких базисов любой операции они перестают быть полными системами функций.
Одни и те же преобразования логических переменных можно задать в различных формах (базисах). Выбор базиса зависит от простоты реализации той или иной функции с помощью логических операций данной системы функций. Чаще всего используются базисы Шеффера и Пирса, т. к. они содержат только одну операцию, и для реализации сложной схемы нужен только один тип ЛЭ. В развитых сериях стандартных интегральных схем (ИС) наряду с базовыми ЛЭ обычно имеется и ряд других, выполняющих другие логические операции
___________________Вопрос 23____________________
Абсолютно минимальные формы представления ФАЛ.
Можно получить еще более простые выражения min ДНФ. Например,f(x1,x2,x3,x4) = x1x2 Vx1x3x4 можно представить в виде f(x1,x2.x3.x4) = x1(x2 V X3x4). Второе представление содержит две
коньюнкции и одну дизъюнкцию, а первое - три конъюнкции и одну дизъюнкцию, т.е. второе представление более экономично.
Дано 
1)Обозначаем конъюнктивные термы как abcd
2)Найдем пересечения термов и выбираем max ранг((a,d)(a,c)(c,d)), возьмем (C ,D)
3) Запишем функцию f, вынося общий элемент x1*не(x2) за скобки в C+D
4) вводим новые обозначения и повторяем шаги, пока окончательно не получим 
Данная форма имеет 6 конъюнкций и 3 дизъюнкции, а исходная 11 кон. и 3 диз.
|
Скачать 4.63 Mb.