«Минимизация с помощью минимизирующих карт»

МИНИСТЕРСТВО ПО РАЗВИТИЮ ИНФОРМАТИЗАЦИИ И
КОММУНИКАЦИЙ РЕСПУБЛИКИ УЗБЕКИСТАН
УРГЕНЧСКИЙ ФИЛИАЛ ТАШКЕНТСКОГО УНИВЕРСИТЕТА
ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ИМЕНИ
МУХАММАДА АЛЬ-ХОРАЗМИЙ


Самостоятельная работа
По предмету: «Введение в проектирование цифровых устройств»
На тему: « Минимизация с помощью минимизирующих карт »

студент группы № 962-19

Мамутов Жасурбек

Ургенч 2022

Содержание

Введение 3
Минимизация булевых функций с помощью карт Карно 3
Графический метод минимизации – Карты Карно 5
Нахождение тупиковых форм 9
Минимизация булевых функций методом Карно 10

Введение

Минимизация булевых функций с помощью карт Карно

Для минимизации функций относительно небольшого числа переменной (не более шести) наиболее простым и наглядным является графический метод, использующий карты Карно.

Карта Карно – это прямоугольник, разбитый на квадраты, число которых равно числу наборов рассматриваемой функции, т. е. 2ⁿ. Клетки размечаются так, чтобы наборы, для которых возможны смежные конституанты, оказались бы в соседних клетках.
При заполнении карты Карно в ее клетки проставляют значения функции для соответствующих наборов, которые являются координатами клеток. Например, для функции двух переменных А и В (рис. 5) карта Карно имеет вид

Единицы, представленные в клетках, обозначают конституанты единицы рассматриваемой функции. Отыскание минимальной ее формы сводится к определению варианта, при котором все конституанты единицы накрываются (охватываются контурами покрытия) наименьшим числом наиболее коротких импликант. Объединение клеток на карте эквивалентно выполнению операции склеивания.

Всегда нужно стремиться к минимальному количеству контуров и максимальной площади каждого из них, руководствуясь следующими правилами:

• 
  площадь контура покрытия должна быть S
  

_k = 2^m-i клеток,

где – целое число, m – число переменных. Если, например, m = 3, то S_k = 1, 2, 4, или 8 клеток;

• 
  число сокращаемых переменных
  

N_перем. = log₂ S_k,

т.е. при S_k = 1 не сокращается ни одна переменная, при S_k = 2 сокращается одна переменная и т.д.

В примере на рис. 5 пара единиц верхней строки охватывается импликантой Ā (т.е. обе клетки) имеют общий аргумент Ā). Пара единиц правого столбца накрывается импликантой B, как общей для обеих клеток. Следовательно, минимальная ДНФ функции F(A,B) = Ā Ъ B.
Если имеется несколько вариантов объединения конституант контурами, то можно получить несколько различных эквивалентных минимальных ДНФ функции, одна из которых выбирается для реализации в цифровом устройстве.
Карту Карно удобно использовать и для минимизации функций, заданных в алгебраической форме, например,


.

Карта Карно, состоящая из 2³ = 8 клеток, может быть размечена, как показано на рис. 6.

При охвате единиц контурами склеивания карту Карно можно сворачивать в цилиндр, как вдоль горизонтальной, так и вертикальной оси. В результате все четыре единицы, расположенные в углах Карты, охватываются контуром с общей импликантой . Такой минимизации соответствует выражение

.