Минимизация функций алгебры логики
1) сопоставление математического описания, адекватно отображающего процессы, происходящие в схеме (система логических уравнений).
2) анализ логических уравнений и получение минимальной формы для каждого из них в заданном базисе.
3) переход от логических уравнений к логической схеме, посредством применения логических операторов.
Электронные схемы с одним выходом.
Это наиболее простые схемы, основная сложность при синтезе этих схем – найти выражение для выходной функции в заданном базисе.
Пример:

Типы логических
элементов

Надо привести
в базис импликации

Т.к.
,
то

Тогда получим схему:
![]()
1

![]()


![]()
![]()


![]()
![]()

![]()
![]()

![]()
![]()
Задача синтеза, как правило, имеет различные решения в зависимости от выбора системы логических элементов. Однако, для любой заданной ФАЛ почти всегда можно синтезировать схему, соответствующую этой функции. Получение схемы с минимальным количеством логических связок требует нахождения минимальной формы для ФАЛ. Некоторые, более сложные схемы, имеющие несколько выходов, могут быть сведены в частном случае к набору схем с одним выходом, тогда синтез осуществляется путем декомпозиции для каждой выделенной схемы.
Пример:
синтезировать
схему одноразрядного
двоичного
сумматора
методом декомпозиции
в базисе

Составим таблицу истинности:
|
|
|
|
|
|
| 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 | |||
|
|
|
|
|
Тогда



![]()
![]()
![]()
&
1
1
1
&
1
1
1
&
![]()
![]()
&
&
1
![]()
![]()
![]()
![]()
![]()
![]()
&
![]()
![]()
&
1
![]()
![]()
![]()
![]()
П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 |
Причем, например
,
а
и.т.д.

![]()
![]()

1
&
&
1
![]()
1
![]()
![]()
![]()
&
&
![]()
![]()
![]()
Несложно убедиться, что такой подход не является оптимальным, поэтому рассмотрим следующие моменты синтеза схем:
1) Классический основан на выделении простых импликант заданной системы функций, подобно тому, как это делается в методе минимизации Квайна-Мак-Класки, а затем ищется покрытие заданной функции этими импликантами.
При этом требуется:
1) найти простые импликанты заданной системы функций
2) выразить каждую функцию через простые импликанты
3) синтезировать схему, включающую только эти импликанты и связи между ними
Пример:
синтезировать
схему в базисе
,
функции которой
на выходе имеют
следующий вид:


Решение:
разобьем
на группы,
соответствующие
по количеству
единиц:



![]()

![]()

![]()
1
&
1
![]()
![]()
![]()
![]()
![]()
![]()

1
1
&
&

![]()
![]()
![]()
Метод каскадов (1.8.5)
Этот метод основан на разложении ФАЛ на k переменных:

Где k
n
Эта формула попеременно применяется к заданной функции столько раз, чтобы получить простое логическое выражение, которое легко синтезировать.



.
.
.
и.т.д.
Построенная на основе этих выражений логическая схема на каждом этапе образует последний каскад искомой комбинационной схемы.













