Карта КарноРис. 1 Пример Карты КарноКарта Карно
 Скачать 0.91 Mb.
|
Карта Карно 1 Карта Карно Рис. 1 Пример Карты Карно Карта Карно́ — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба. Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы. В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом. Принципы минимизации Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ, является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами (членами), содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке. Например: Аналогично для КНФ: Возможность поглощения следует из очевидных равенств Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов. Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ, могут иметь в своём составе 2 N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N–мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения. На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов: Карта Карно 2 В случае функции трёх переменных приходится иметь дело с трёхмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке в качестве примера показана таблица истинности для булевой функции трёх переменных и соответствующий ей куб. Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных: В общем случае можно сказать, что 2 K термов, принадлежащие одной K–мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются K переменных. Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел, а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой. Карта Карно 3 Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для N=4 и N=5 приведены на рисунке. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х4 виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4 являются сосоедними, и соответствующие им термы можно склеивать. Описание Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности составленная в 2-х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т.о. вся Карта Карно сворачивается в фигуру тор (бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации. Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки, которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ): 1. Объединяем смежные клетки, содержащие единицы, в область так, чтобы одна область содержала ( целое число = 0… ) клеток (помним про то, что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток, содержащих нули; Карта Карно 4 2. Область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки); 3. Несмежные области, расположенные симметрично оси(ей), могут объединяться в одну; 4. Область должна быть как можно больше, а количество областей как можно меньше; 5. Области могут пересекаться; 6. Возможно несколько вариантов покрытия. Далее берём первую область и смотрим, какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных; если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое, что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией. Например (для Карт на 2 переменные): Для КНФ всё то же самое, только рассматриваем клетки с нулями, неменяющиеся переменные в пределах одной области объединяем в дизъюнкции (инверсии проставляем над единичными переменными), а дизъюнкции областей объединяем в конъюнкцию. На этом минимизация считается законченной. Так для Карты Карно на рис.1 выражение в формате ДНФ будет иметь вид: В формате КНФ: Так же из ДНФ в КНФ и обратно можно перейти использовав Законы де Моргана. Примеры Пример 1 У мальчика Коли есть мама, папа, дедушка и бабушка. Коля пойдёт гулять на улицу, если ему разрешат хотя бы двое родственников. Для краткости обозначим родственников Коли через буквы: мама — х1 папа — х2 дедушка — х3 бабушка — х4 Условимся обозначать согласие родственников единицей, несогласие - нулём. Возможность пойти погулять обозначим буквой f, Коля идёт гулять — f = 1, Коля гулять не идёт — f = 0. Составим таблицу истинности: Карта Карно 5 Перерисуем таблицу истинности в 2-х мерный вид: Переставим в ней строки и столбцы в соответствии с кодом Грея. Получили Карту Карно: Заполним её значениями из таблицы истинности: Минимизируем в соответствии с правилами: Карта Карно 6 1. 1. Все области содержат 2^n клеток; 2. 2. Так как Карта Карно на четыре переменные, оси располагаются на границах Карты и их не видно (подробнее смотри пример Карты на 5 переменных); 3. 3. Так как Карта Карно на четыре переменные, все области симметрично осей — смежные между собой (подробнее смотри пример Карты на 5 переменных); 4. 4. Области S3, S4, S5, S6 максимально большие; 5. 5. Все области пересекаются (необязательное условие); 6. 6. В данном случае рациональный вариант только один. Теперь по полученной минимальной ДНФ можно построить логическую схему: Из-за отсутствия в наличии шести-входового элемента ИЛИ, реализующего функцию дизъюнкции, пришлось каскадировать пяти- и двух-входовые элементы(D7, D8). Составим мин. КНФ: Карта Карно 7 Карта Карно 8 Пример Карты Карно на пять переменных Имеем такую таблицу истинности: Карта Карно будет выглядеть следующим образом (для лучшего визуального восприятия в Карту нули не записываем): Неправильно (на примере ДНФ): • — Область S1 — накрыта правильно; • — Область S2 — нарушает п.1; • — Область S3 — нарушает п.2; • -Области S4 и S6 — не выполняют п.3, это не является ошибкой — выражение получится больше чем если бы S4 и S6 представляли собой одну область; • — Область S5 — нарушает п.1 по кол-ву клеток и по недопустимости нахождения нулей в области. Карта Карно 9 Правильно, но не оптимально: Эта карта Карно минимизирована неоптимально, так как можно объединить единицы, входящие в члены S3 и S5. Минимизировав эту Карту получаем следующую ДНФ: Оптимально: Карта Карно 10 Составим минимальную КНФ: Другой вариант той же самой Карты Карно: Ничего не меняется только в строках записано три переменных, а в столбцах две. Карта Карно 11 Пример большой Карты Карно на восемь переменных Предположим, по имеющейся таблице истинности составлена такая Карта Карно: Найдём минимальную ДНФ: Минимальная КНФ: Карта Карно 12 Источники и основные авторы 13 Источники и основные авторы Карта Карно Источник: http://ru.wikipedia.org/w/index.php?oldid=36798414 Редакторы: AdmiralHood, Altum, Antonix Wayfarer, CaesarIII, Changall, DerLetzteRegenbogen, Dims, Fedorchenko.bogdan, Gvozdet, Jack-ov, Jazz, Loveless, Obersachse, Qldor, Rinatus, VP, Ботильда, Голем, Дмитрий Джус, Синдар, 30 анонимных правок Источники, лицензии и редакторы изображений Файл:Karnaugh map Intro.png Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnaugh_map_Intro.png Лицензия: Public Domain Редакторы: Jack-ov Файл:Karnaugh map 01.gif Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnaugh_map_01.gif Лицензия: Creative Commons Attribution-Sharealike 3.0,2.5,2.0,1.0 Редакторы: AdmiralHood Файл:Karnaugh map 02.gif Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnaugh_map_02.gif Лицензия: Creative Commons Attribution-Sharealike 3.0,2.5,2.0,1.0 Редакторы: AdmiralHood Файл:Karnaugh map 03.gif Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnaugh_map_03.gif Лицензия: Creative Commons Attribution-Sharealike 3.0,2.5,2.0,1.0 Редакторы: AdmiralHood Файл:Karnaugh map 04.gif Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnaugh_map_04.gif Лицензия: Creative Commons Attribution-Sharealike 3.0,2.5,2.0,1.0 Редакторы: AdmiralHood Изображение:Karnough map 2 1 1.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_1.PNG Лицензия: Public Domain Редакторы: Jack-ov Изображение:Karnough map 2 1 2.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_2.PNG Лицензия: Public Domain Редакторы: Jack-ov Изображение:Karnough map 2 1 3.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_3.PNG Лицензия: Public Domain Редакторы: Jack-ov Изображение:Karnough map 2 1 4.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_4.PNG Лицензия: Public Domain Редакторы: Jack-ov Изображение:Karnough map 2 1 5.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_5.PNG Лицензия: Public Domain Редакторы: Jack-ov Изображение:Karnough map 2 1 6.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_6.PNG Лицензия: Public Domain Редакторы: Jack-ov Изображение:Karnough map 2 1 7.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_7.PNG Лицензия: Public Domain Редакторы: Jack-ov Изображение:Karnough map 2 1 8.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_8.PNG Лицензия: Public Domain Редакторы: Jack-ov Изображение:Karnough map 2 1 9.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_9.PNG Лицензия: Public Domain Редакторы: Jack-ov Изображение:Karnough map 2 1 10.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_10.PNG Лицензия: Public Domain Редакторы: Jack-ov Изображение:Karnough map 2 1 11.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_11.PNG Лицензия: Public Domain Редакторы: Jack-ov Изображение:Karnough map 2 1 12.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_12.PNG Лицензия: Public Domain Редакторы: Jack-ov Изображение:Karnough map 2 1 13.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_13.PNG Лицензия: Public Domain Редакторы: Jack-ov Изображение:Karnough map 2 1 14.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_14.PNG Лицензия: Public Domain Редакторы: Jack-ov Файл:Nikolay true table.png Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Nikolay_true_table.png Лицензия: Public Domain Редакторы: Jack-ov Файл:2d true table.png Источник: http://ru.wikipedia.org/w/index.php?title=Файл:2d_true_table.png Лицензия: Public Domain Редакторы: Jack-ov Файл:Karnough map 4 empty.png Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_4_empty.png Лицензия: Public Domain Редакторы: Jack-ov Файл:Nikolay map.png Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Nikolay_map.png Лицензия: Public Domain Редакторы: Jack-ov Файл:Nikolay map DNF.png Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Nikolay_map_DNF.png Лицензия: Public Domain Редакторы: Jack-ov Файл:Logic Nikolay.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Logic_Nikolay.PNG Лицензия: Public Domain Редакторы: Jack-ov Файл:Nikolay map KNF.png Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Nikolay_map_KNF.png Лицензия: Public Domain Редакторы: Jack-ov Файл:logic Nikolay.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:logic_Nikolay.PNG Лицензия: Public Domain Редакторы: Jack-ov Файл:X5 true table.png Источник: http://ru.wikipedia.org/w/index.php?title=Файл:X5_true_table.png Лицензия: Public Domain Редакторы: Jack-ov Файл:Karnough map 5.png Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_5.png Лицензия: Public Domain Редакторы: Jack-ov Файл:Karnough map 5 error.png Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_5_error.png Лицензия: Public Domain Редакторы: Jack-ov Файл:Karnough map 5 right.png Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_5_right.png Лицензия: Public Domain Редакторы: Jack-ov Файл:Karnaugh map minimize.gif Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnaugh_map_minimize.gif Лицензия: Creative Commons Attribution-Sharealike 3.0,2.5,2.0,1.0 Редакторы: Admiralhood Файл:Karnough map 5 KNF.png Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_5_KNF.png Лицензия: Public Domain Редакторы: Jack-ov Файл:Karnough map 5 turn.png Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_5_turn.png Лицензия: Public Domain Редакторы: Jack-ov Файл:Karnough 8 clear.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_8_clear.PNG Лицензия: Public Domain Редакторы: Jack-ov Файл:Karnough 8 DNF.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_8_DNF.PNG Лицензия: Public Domain Редакторы: Jack-ov Файл:Karnough 8 KNF.PNG Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_8_KNF.PNG Лицензия: Public Domain Редакторы: Jack-ov Лицензия Creative Commons Attribution-Share Alike 3.0 Unported http:/ / creativecommons. org/ licenses/ by-sa/ 3. 0/ |