Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Особливості та додаткові можливості застосування методу карт Карно.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних технологій, автоматики та метрології
Факультет:
Не вказано
Кафедра:
Захист інформації
Інформація про роботу
Рік:
2024
Тип роботи:
Державний іспит
Предмет:
Прикладна теорія цифрових автоматів
Варіант:
14
Частина тексту файла (без зображень, графіків і формул):
Особливості та додаткові можливості застосування методу карт Карно.
Карты Карно (их разновидностью являются карты Вейча, которые строятся как развертки куба на плоскости), являются графическим представлением таблиц истинности. Поэтому они строятся или по таблице истинности анализируемой функции, или же по ее СНДФ.
Напомним, что каждая строка таблицы истинности, для которой функция равна единице, соответствует конкретному минтерму функции, представленной в СНДФ. Строка, для которой функция равна нулю является определенным макстермом функции, представленной в СНКФ.
Карта Карно представляет собой прямоугольник, разбитый на квадраты, число которых равно общему числу наборов для данной функции n переменных, т.е. оно равно 2n. Так, для функции четырех переменных квадратов будет 16, для пяти переменных - 32 и т.д. Каждый квадрат соответствует определенному набору или терму, причем наборы располагаются так, чтобы соседние наборы или термы, как по горизонтали, так и по вертикали, отличались бы только значением одной переменной: в одном квадрате она с инверсией, а в другом, соседнем - без. Функцию в СНДФ наносят на карту, отмечая, например, знаком 1 квадраты, соответствующие тем наборам, на которых функция равна единице, т.е. в СНДФ функции есть соответствующий минтерм. Остальные квадраты отмечаются знаком 0. Иногда в углу квадрата ставят номер набора. Такой способ используется, если функция задана числовым образом, но он неудо-бен для процедуры минимизации.
Логическая функция двух переменных, где а) - таблица истинности; а б) - карта Карно.
а б
В итоге карту Карно можно оформлять любым подходящим образом, но только так, чтобы каждый квадрат соответствовал определенному набору или терму и они, как уже отмечалось, располагались бы таким образом, чтобы соседние наборы или термы, как по горизонтали, так и по вертикали, отличались бы только значением одной переменной: в одном квадрате она с инверсией, а в другом, соседнем - без. Причем, надо учесть, что квадраты, расположенные на противополжных концах каждой строки или столбца, также являются соседними.
Перечислим последовательность действий, выполняемых для минимизации функции по методу Карно.
1) Исходная функция, подлежащая минимизации, должна быть представлена в НДФ. Затем ее надо представить в СНДФ. Или же составляется таблица истинности минимизируемой функции.
Как уже отмечалось, между строками таблицы истинности и клетками (ячейками) на карте Карно существует взаимно однозначное соответствие. Когда карта Карно составляется по СНДФ минимизируемой функции, то очевидно, что каждая переменная без отрицания заменяется ее значением 1, а с отрицанием - 0.
2) Затем строится карта Карно по принципу, описанному ранее. Представим систему координат, в которой, например, для функции двух аргументов по горизонтальной оси откладываются значения одного аргумента, а по вертикали - другого. На пересечении соответствующих координат получаем ячейку, куда записывается значение функции (0 или 1), соответствующее данному набору. Если функция представлена в СНДФ, то в ячейке соответствующей существующему минтерму записывается 1, а в ячейке несуществующего минтерма - 0.
3) После этого объединяются в группы смежные ячейки, в которых записаны единицы, следующим образом: объединяется обязательно четное количество соседних ячеек с единицами как по вертикали, так и по горизонтали. Причем, каждая ячейка с 1 может попасть одновременно в две группы, полученные в результате объединения единиц как по вертикали, так и по горизонтали.
4) Каждой такой группе ставится в соответствие новый минтерм для изображения исходной функции в форме минимальной НДФ.
5) Изображение каждого нового минтерма формируется по следующему алгоритму:
а) переменная, которая в каждой ячейке образованной группы имеет значение только 0, изображается ее инверсией;
б) переменная, которая в каждой ячейке группы имеет значение только 1, изображается без инверсии;
в) переменная, которая в пределах образованной группы меняет свое значение, не изображается, т.е. отбрасывается.
Таким образом, карту Карно можно рассматривать как графическое представление совокупности всех (сушествующих и не существующих) минтермов функции в СНДФ данного числа логических переменных.
На основании закона дистрибутивности и теорем (F +A) = 1 и AA = 0= а также A + 0 = A и A0 = 0, два минтерма, находящиеся в соседних клетках, могут быть заменены одним новым минтермом, содержащим на одну переменную меньше. Если соседними являютя две пары минтермов, то такая группа из 4 минтермов может быть заменена новым минтермом, который содержит на две переменные меньше и т.д. В общем случае наличие единиц в 2n соседних клетках позволяет исключить n переменных.
При формировании на базе карты Карно новых минтермов для представления функции в минимальной НДФ, или же в минимальной НКФ, значения соответствующих переменных, равных 1, заменяются изображением переменных без отрицания, а при значениях равных 0 - с отрицанием.
Рассмотрим процесс минимизации на примере функции, заданной следующим логическим уравнением:
F(A,B,C,D) = BCD + ABD + BCD + ABC + ACD + BCD + ABC + ABC
Представим эту функцию в СДНФ:
F = BCD(A + A) + ABD(C + C) + BCD(A + A) + ABC(D + D) +ACD(B + B) +
+ BCD(A + A) + ABC(D + D) + ABC(D + D) = ABCD +ABCD + ABCD +
+ ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD.
Ниже изображена карта Карно, соответствующая рассматриваемой функции.
(ABC)
(ABC)
Минтермы функции образуют в карте четыре группы:
1) (ABC); 2) (ABC); 3) (D); 4) (ABC).
Следовательно
F = ABC + ABC + ABC + D = BC(A + A) + ABC + D = BC + ABC + D.
Но надо иметь в виду, что в общем случае функция может иметь несколько минимальных форм.
Пример. Найти минимальные дизъюнктивные и конъюнктивные нормальные формы функции:
f(A, B, C) = ABC ABC ABC ABC ABC.
Карты Карно для данной функции выглядят следующим образом:
а) б)
Объединить единицы можно двумя вариантами (а и б). Этим вариантам соответствуют две минимальные дизъюнктивные формы:
f(A, B, C) = AB AC AB,
f(A, B, C) = AB BC AB.
Для получения минимальной конъюнктивной нормальной формы следует объединить нули логической функции. Две конституенты нуля, соответст-вующие клеткам, обведенным пунктирной линией (а), склеиваются по пере-менной С и представляются импликантой A B, а оставшийся ноль - конституентойABC. Поэтому минимальная НКФ заданной функции будет
f(A, B, C) = (A B) (A B C).
Заметим, что минимальная НКФ функции содержит меньше букв, чем минимальные НДФ.
Как уже отмечалось, для того чтобы найти выражение заданной логической функции, наиболее удобное для синтеза логической схемы, следует, кроме минимальных дизъюнктивных нормальных форм, получить также минимальные конъюнктивные нормальные формы и выбрать из них ту, при технической реализации которой потребуется наименьшее количество элементов. Существует несколько методов получения минимальных конъюнктивных нормальных форм. Один из наиболее распространенных и удобных методов был продемонстрирован в предыдущем примере.
При наличии уже сформированной минимальной НДФ функции минимальную НКФ можно также, в частности, найти следующим образом:
берется от найденной минимальной НДФ отрицание и производится преобразование по формуле де Моргана. Тем самым получается минимальная НКФ функции. Например,
если МНДФ функции равна
f(A, B, C) =AB + AC,
то проведя отрицание и применив теорему де Моргана, получим МНКФ:
f(A, B, C) =AB + AC = (A +B)(A + C).
Каждая строка таблицы истинности, или ячейка на карте Карно, соответствует определенному значению логической функции для соответ ствующей комбинации значений аргументов, т.е. для соответствующего набора. В некоторых случаях известно, что какой-то набор появиться не может или же если он появится, то это значение функции, по тем или иным причинам, не существенно. Для таких случаев нет необходимости определять это значение функции по таблице истинности. В таких случаях говорят о неопределенных условиях. Карты Карно позволяют строить МНДФ и МНКФ и в этих ситуациях.
На карте Карно неопределенное условие обозначается прочерком в соответствующей ячейке. Такие ячейки могут произвольным образом включатья в группы при построении минимальных макстермов или минтермов. Любую из них можно включить как в группу единичных, так и в группу нулевых ячеек, или же вообще никуда не включать.В заключение обзора методов минимизации логических функций нужно отметить, что в настоящее время разработано много программ, позволяющих производить процедуру минимизации на компьютерах различными методами.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора