Минимизация ФАЛ - (реферат)
p>Значит Браун – чиновник, Джон – старик, Смит – мошенник, он же преступник. 2) Среди технических средств автоматизации (релейно-контактные системы). Значительное место занимают РКС, используемые в вычислительной технике. РКС –переключательные схемы. В 1910 г. физик Эрнфест указал на возможность применения алгебры логики при исследовании РКС. Его идея заключается в том, что каждой схеме можно сопоставить ФАЛ и наоборот. Это позволяет выявить возможности схемы, изучая соответствующую формулу, а упрощение схемы свести к упрощению ФАЛ– анализ переключательной схемы.Синтез переключательной схемы (до построения схемы можно описать ее работу с помощью логической функции).
Рассмотрим связь между переключательными схемами и ФАЛ. (1. 8. 1) Определение: переключательная схема – схемотехническое изображение устройства, состоящее из следующих элементов: 1) переключатель (может быть разомкнут или замкнут)
2) проводники
3) вход в схему и выход из нее
Примеры:
а) А В
б) Дизъюнкция: А В
в) Импликация: А В
г) Тождественно ложно: А В
д) Тождественно истинно: А В
Из схем а, б, в можно получить функцию алгебры логики.
А Б
После упрощения получим:
А B
Синтез логической схемы. (1. 8. 2)
В зависимости от выходного сигнала, все электрические схемы можно разбить на две группы:
1) 1-го рода – содержит комбинаторные схемы (выход зависит от входа) 2) 2-го рода –накапливающие схемы (элементы памяти, выход зависит от входа в данный момент времени и в предыдущий момент времени).
По количеству входов и выходов делятся на:
1) 1+1 – 1 вход и 1 выход
2) n+1 – n входов и 1 выход
3) 1+n – 1 вход и n выходов
4) n+m – n входов и m выходов
Любая ЭВМ состоит из комбинации схем 1-го и 2-го порядков.
Определение: логический оператор схемы –это элементарная логическая функция, с помощью которой описывается работа схемы в целом.
Анализ схемы производят в два этапа:
1) Из вспомогательной схемы удаляются все вспомогательные элементы, не влияющие на логику работы системы.
2) Через логические операторы выражают все элементы схемы, получая логическое уравнение, являющееся моделью функции, выполняемой схемой, затем ее упрощают и переходят к схематическому изображению.
Примеры:
Простейшие логические схемы:
После упрощения получим:
Синтез электронных схем (1. 8. 3)
Задачу синтеза электронных схем можно сформулировать следующим образом: при заданных входных переменных и известной выходной функции, спроектировать логическое устройство, которое реализует эту функцию. При этом могут быть наложены дополнительные ограничения либо в виде системы логических элементов, либо по количеству логических операторов и. т. д. Обычно, решая задачи анализа и синтеза, используют полные базисы функций. При этом, любую логическую функцию, входящую в базис, сопоставляют с некоторым физическим элементом, в результате логическую схему можно заменить принципиальной схемой, состоящей из физических элементов. Таким образом удается соединить математическую задачу синтеза логической схемы с инженерной задачей проектирования электронной схемы. При разработке электронной схемы за основные критерии принимают минимум аппаратуры, минимум типов применяемых элементов и максимум надежности. С точки зрения математической логики, задачи синтеза решаются при обеспечении минимального числа логических операторов, минимального количества типов логических операторов. В общем случае при синтезе электронной схемы соблюдается следующая последовательность:
1) сопоставление математического описания, адекватно отображающего процессы, происходящие в схеме (система логических уравнений).
2) анализ логических уравнений и получение минимальной формы для каждого из них в заданном базисе.
3) переход от логических уравнений к логической схеме, посредством применения логических операторов.
Электронные схемы с одним выходом.
Это наиболее простые схемы, основная сложность при синтезе этих схем – найти выражение для выходной функции в заданном базисе. Пример:
Типы логических элементов
Надо привести в базис импликации
Т. к. , то
Тогда получим схему:
Задача синтеза, как правило, имеет различные решения в зависимости от выбора системы логических элементов. Однако, для любой заданной ФАЛ почти всегда можно синтезировать схему, соответствующую этой функции. Получение схемы с минимальным количеством логических связок требует нахождения минимальной формы для ФАЛ. Некоторые, более сложные схемы, имеющие несколько выходов, могут быть сведены в частном случае к набору схем с одним выходом, тогда синтез осуществляется путем декомпозиции для каждой выделенной схемы. Пример: синтезировать схему одноразрядного двоичного сумматора методом декомпозиции в базисе
Составим таблицу истинности:
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
Где - переменные, - сумма в -ом разряде, - перенос из младшего разряда в старший, - перенос из старшего разряда. Составим ДСНФ:
1
1
1
1
1
1
1
1
Тогда
Ci
Пi
Такой способ не очень хорош, так как не всегда оптимален.
Электронные схемы с несколькими выходами (1. 8. 4)
Пусть n входов и k выходов.
Классический пример таких схем – дешифратор
Входы Выходы
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
1
0
1
1
1
0
0
0
0
0
0
0
1
Причем, например , а и. т. д.
y0
y7
Несложно убедиться, что такой подход не является оптимальным, поэтому рассмотрим следующие моменты синтеза схем:
1) Классический основан на выделении простых импликант заданной системы функций, подобно тому, как это делается в методе минимизации Квайна-Мак-Класки, а затем ищется покрытие заданной функции этими импликантами. При этом требуется:
1) найти простые импликанты заданной системы функций
2) выразить каждую функцию через простые импликанты
3) синтезировать схему, включающую только эти импликанты и связи между ними Пример: синтезировать схему в базисе , функции которой на выходе имеют следующий вид:
Решение: разобьем на группы, соответствующие по количеству единиц:
y2
y1
Метод каскадов (1. 8. 5)
Этот метод основан на разложении ФАЛ на k переменных:
Где kn
Эта формула попеременно применяется к заданной функции столько раз, чтобы получить простое логическое выражение, которое легко синтезировать.
.
и. т. д.
Построенная на основе этих выражений логическая схема на каждом этапе образует последний каскад искомой комбинационной схемы.
