Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Карта Карно



План:


Введення

Рис. 1 Приклад Карти Карно

Карта Карно - графічний спосіб мінімізації перемикальних (булевих) функцій, що забезпечує відносну простоту роботи з великими виразами і усунення потенційних гонок. Являє собою операції попарного неповного склеювання і елементарного поглинання. Карти Карно розглядаються як перебудована відповідним чином таблиця істинності функції. Карти Карно можна розглядати як певну плоску розгортку n-мірного куба булева.

Карти Карно були винайдені в 1952 Едвардом В. Вейча та удосконалено в 1953 Морісом Карно, фізиком з " Bell Labs ", і були покликані допомогти спростити цифрові електронні схеми.

У карту Карно булеві змінні передаються з таблиці істинності та впорядковуються за допомогою коду Грея, в якому кожне наступне число відрізняється від попереднього тільки одним розрядом.


1. Принципи мінімізації

Основним методом мінімізації логічних функцій, представлених у вигляді СДНФ або СКНФ, є операція попарного неповного склеювання і елементарного поглинання. Операція попарного склеювання здійснюється між двома термами (членами), що містять однакові змінні, входження яких (прямі і інверсні) збігаються для всіх змінних, крім однієї. У цьому випадку всі змінні, крім однієї, можна винести за дужки, а залишилися в дужках пряме і інверсне входження однієї змінної піддати склейці. Наприклад:

\ Overline {X} _1X_2X_3X_4 \ vee \ overline {X} _1X_2 \ overline {X} _3X_4 = \ overline {X} _1X_2X_4 (X_3 \ vee \ overline {X} _3) = \ overline {X} _1X_2X_4 \ cdot 1 = \ overline {X} _1X_2X_4.

Аналогічно для КНФ:

(\ Overline {X} _1 \ vee X_2 \ vee X_3 \ vee X_4) (\ overline {X} _1 \ vee X_2 \ vee \ overline {X} _3 \ vee X_4) = \ overline {X} _1 \ vee X_2 \ vee X_4 \ vee X_3 \ overline {X} _3 = \ overline {X} _1 \ vee X_2 \ vee X_4 \ vee 0 = \ overline {X} _1 \ vee X_2 \ vee X_4.

Можливість поглинання слід з очевидних рівностей

A \ vee \ overline {A} = 1; A \ overline {A} = 0.

Таким чином, головним завданням при мінімізації СДНФ і СКНФ є пошук термів, придатних до склейці з подальшим поглинанням, що для великих форм може виявитися досить складним завданням. Карти Карно надають наочний спосіб відшукання таких термів.

Як відомо, булеві функції N змінних, представлені у вигляді СДНФ або СКНФ, можуть мати у своєму складі 2 N різних термів. Всі ці члени складають деяку структуру, топологічно еквівалентну N-мірному кубу, причому будь-які два терми, з'єднані ребром, придатні для склеювання і поглинання.

На малюнку зображена проста таблиця істинності для функції з двох змінних, що відповідає цій таблиці 2-мірний куб (квадрат), а також 2-мірний куб з позначенням членів СДНФ і еквівалентна таблиця для угруповання термів:

Karnaugh map 01.gif

У випадку функції трьох змінних доводиться мати справу з тривимірним кубом. Це складніше і менш наочно, але технічно можливо. На малюнку як приклад показана таблиця істинності для булевої функції трьох змінних і відповідний їй куб.

Karnaugh map 02.gif

Як видно з малюнка, для тривимірного випадку можливі більш складні конфігурації термів. Наприклад, чотири терма, що належать одній грані куба, об'єднуються в один терм з поглинанням двох змінних:

\ Overline {X} _1 \ overline {X} _2 \ overline {X} _3 \ vee X_1 \ overline {X} _2 \ overline {X} _3 \ vee \ overline {X} _1 \ overline {X} _2X_3 \ vee X_1 \ overline {X} _2X_3 =

= \ Overline {X} _2 (\ overline {X} _1 \ overline {X} _3 \ vee \ overline {X} _1X_3 \ vee X_1 \ overline {X} _3 \ vee X_1X_3) = \ overline {X} _2 (\ overline {X} _1 \ vee X_1) (\ overline {X} _3 \ vee X_3) = \ overline {X} _2

У загальному випадку можна сказати, що 2 K термів, що належать одній K-мірної межі гіперкуба, склеюються в один терм, при цьому поглинаються K змінних.

Для спрощення роботи з булевими функціями великого числа змінних був запропонований наступний зручний прийом. Куб, що представляє собою структуру термів, розгортається на площину як показано на малюнку. Таким чином з'являється можливість представляти булеві функції з числом змінних більше двох у вигляді плоскої таблиці. При цьому слід пам'ятати, що порядок кодів термів в таблиці (00 01 11 10) не відповідає порядку проходження двійкових чисел, а клітини, які знаходяться в крайніх стовпцях таблиці, сусідять між собою.

Karnaugh map 03.gif

Аналогічним чином можна працювати з функціями п'яти, семи (обов'язково просте число) і т.д., використовуючи невізуалізіруемие багатовимірні булеві куби.


2. Порядок роботи з картою Карно

Вихідною інформацією для роботи з картою Карно є таблиця істинності минимизируемой функції. Таблиця істинності містить повну інформацію про логічної функції, задаючи її значення на всіх можливих 2 N наборах вхідних змінних X 1... X N. Карта Карно також містить 2 N клітин, кожна з яких ассоціірцется з унікальним набором вхідних змінних X 1... X N. Таким чином, між таблицею істинності і картою Карно є взаємно однозначна відповідність, і карту Карно можна вважати відповідним чином відформатованої таблицею істинності.

У даному розділі в якості прикладу використовується функція чотирьох змінних, задана таблицею істинності, зображеної на рис. 2а. Карта Карно для тієї ж функції зображено на рис. 2б.

Рис. 2. Приклад роботи з картою Карно

2.1. Принципи склейки

  • Склейку клітин карти Карно можна здійснювати по одиницях (якщо необхідно отримати ДНФ) або по нулях (якщо потрібно КНФ).
  • Склеювати можна тільки прямокутні області з числом одиниць (нулів) 2 n, де n - ціле число. Для карт Карно з числом змінних більше чотирьох можуть виходити більш складні області, про що буде сказано в наступних розділів.
  • Область, яка піддається склеюванню повинна містити лише одиниці (нулі).
  • Крайні клітини кожної горизонталі і вертикалі кожної також межують між собою (топологічно карта Карно для чотирьох змінних являє собою тор) і можуть об'єднуватися в прямокутники. Наслідком цього правила є суміжність всіх чотирьох кутових клітинок карти Карно для N = 4. Якщо у всіх чотирьох кутових клітинках стоять одиниці (нулі) вони можуть бути об'єднані в квадрат, як показано на рис. 2в.
  • Усі одиниці (нулі) повинні потрапити в яку-небудь область.
  • З точки зору мінімальності ДНФ ( КНФ) число областей повинно бути якомога менше (кожна область є терм), а число клітин в області має бути як можна більше (чим більше клітин в області, тим менше змінних містить терм. Терм розміром 2 n осередків містить N - n змінних ).
  • Одна осередок карти Карно може входити відразу в кілька областей. Це випливає з очевидного властивості булевих функцій: повторення вже існуючого доданка (сомножителя) не впливає на функцію:

A \ vee A = A; A \ cdot A = A.

  • На відміну від СДНФ (СКНФ), ДНФ (КНФ) не єдині. Можливо кілька еквівалентних один одному ДНФ (КНФ), які відповідають різним способам покриття карти Карно прямокутними областями.

3. Опис

Карта Карно може бути складена для будь-якої кількості змінних, однак зручно працювати при кількості змінних не більше п'яти. По суті Карта Карно - це таблиця істинності складена в 2-х мірному вигляді. Завдяки використанню коду Грея в ній верхній рядок є сусідній з нижньої, а правий стовпець сусідній з лівим, т.ч. вся Карта Карно згортається в фігуру тор (бублик). На перетині рядка і стовпця проставляється відповідне значення з таблиці істинності. Після того як Карта заповнена, можна приступати до мінімізації.

Якщо необхідно отримати мінімальну ДНФ, то у Карті розглядаємо тільки ті клітини які містять одиниці, якщо потрібна КНФ, то розглядаємо ті клітини, які містять нулі. Сама мінімізація проводиться за такими правилами (на прикладі ДНФ):

  1. Об'єднуємо суміжні клітини, що містять одиниці, в область так, щоб одна область містила 2 n ( n ціле число = 0 ... \ Infty ) Клітин (пам'ятаємо про те, що крайні рядки та стовпці є сусідніми між собою), в області не повинно знаходитися клітин, що містять нулі;
  2. Область повинна розташовуватися симетрично осі (ів) (осі розташовуються через кожні чотири клітини);
  3. Несуміжні області, розташовані симетрично осі (їй), можуть об'єднуватися в одну;
  4. Область має бути якомога більше, а кількість областей якомога менше;
  5. Області можуть перетинатися;
  6. Можливо кілька варіантів покриття.

Далі беремо першу область і дивимося, які змінні не змінюються в межах цієї області, виписуємо кон'юнкцію цих змінних; якщо незмінний мінлива нульова, проставляємо над нею інверсію. Беремо наступну область, виконуємо те ж саме, що і для першої, і т. д. для всіх областей. Кон'юнкції областей об'єднуємо диз'юнкцією.
Наприклад (для Карт на 2 змінні):

Karnough map 1 лютого 1.PNG Karnough map 1 лютого 2.PNG Karnough map 1 лютого 3.PNG Karnough map 1 лютого 4.PNG Karnough map 1 лютого 5.PNG Karnough map 1 лютого 6.PNG Karnough map 1 лютого 7.PNG Karnough map 1 лютого 8.PNG
\ Overline {X_1} \ \ overline {X_2}\ Overline {X_1} \ X_2X_1 \ X_2 \X_1 \ \ overline {X_2}\ Overline {X_2}\ Overline {X_1}{X_2} \{X_1} \


Karnough map 1 лютого 9.PNG Karnough map 1 лютого 10.PNG Karnough map 1 лютого 11.PNG Karnough map 1 лютого 12.PNG Karnough map 1 лютого 13.PNG Karnough map 1 лютого 14.PNG
S_1 \ vee S_2 =S_1 \ vee S_2 =S_1 \ vee S_2 =S_1 \ vee S_2 =S_1 \ vee S_2 =S_1 \ vee S_2 =
= X_1X_2 \ vee= X_1 \ overline {X_2} \ vee= X_2 \ vee X_1= X_1 \ vee \ overline {X_2}= \ Overline {X_1} \ vee \ overline {X_2}= X_2 \ vee \ overline {X_1}
\ Vee \ overline {X_1} \ \ overline {X_2}\ Vee \ overline {X_1} X_2

Для КНФ все те ж саме, тільки розглядаємо клітини з нулями, незмінний змінні в межах однієї області об'єднуємо в диз'юнкції (інверсії проставляємо над одиничними змінними), а диз'юнкції областей об'єднуємо в кон'юнкцію. На цьому мінімізація вважається закінченою. Так для Карти Карно на рис.1 вираження у форматі ДНФ матиме вигляд:

f (X_1, X_2, X_3, X_4) = S_1 \ vee S_2 \ vee S_3 = \ overline {X_1} \ \ overline {X_4} \ vee X_1X_2X_4 \ vee \ overline {X_2} \ \ overline {X_4}

У форматі КНФ:

f (X_1, X_2, X_3, X_4) = S_1 S_2 S_3 = (X_1 \ vee \ overline {X_4}) (X_2 \ vee \ overline {X_4}) (\ overline {X_1} \ vee \ overline {X_2} \ vee X_4)

Так само з ДНФ у КНФ і назад можна перейти використавши Закони де Моргана.


4. Приклади

4.1. Приклад 1

У хлопчика Колі є мама, тато, дідусь і бабуся. Коля піде гуляти на вулицю, якщо йому дозволять хоча б двоє родичів.
Для стислості позначимо родичів Коли через літери:
мама - х1
тато - х2
дідусь - х3
бабуся - х4
Домовимося позначати згода родичів одиницею, незгода - нулем. Можливість піти погуляти позначимо літерою f, Коля йде гуляти - f = 1, Коля гуляти не йде - f = 0.
Складемо таблицю істинності:

Nikolay true table.png



Перерісуем таблицю істинності в 2-х мірний вид:
2d true table.png


Переставимо в ній рядки та стовпці відповідно до коду Грея. Отримали Карту Карно:

Karnough map 4 empty.png



Заповнимо її значеннями з таблиці істинності:
Nikolay map.png


Мінімізуємо відповідно до правил:

Nikolay map DNF.png



  1. 1. Всі області містять 2 ^ n клітин;
  2. 2. Так як Карта Карно на чотири змінні, осі розташовуються на кордонах Карти і їх не видно (докладніше дивись приклад Карти на 5 змінних);
  3. 3. Так як Карта Карно на чотири змінні, всі області симетрично осей - суміжні між собою (детальніше дивись приклад Карти на 5 змінних);
  4. 4. Області S3, S4, S5, S6 максимально великі;
  5. 5. Всі області перетинаються (необов'язкова умова);
  6. 6. В даному випадку раціональний варіант тільки один.

f (X1, X2, X3, X4) = S1 \ vee S2 \ vee S3 \ vee S4 \ vee S5 \ vee S6 == X3X4 \ \ vee \ X1X2 \ \ vee \ X2X4 \ \ vee \ X1X4 \ \ vee \ X1X3 \ \ vee \ X2X3
Тепер за отриманою мінімальної ДНФ можна побудувати логічну схему:

Logic Nikolay.PNG

Через відсутність в наявності шести-входові елемента АБО, що реалізує функцію диз'юнкції, довелося каскадировать п'яти-і двох-входові елементи (D7, D8).

Складемо хв. КНФ:

Nikolay map KNF.png


f (X1, X2, X3, X4) = (S1) \ (S2) \ (S3) \ (S4) == (X1 \ vee X2 \ vee X3) (X1 \ vee X3 \ vee X4) (X2 \ vee X3 \ vee X4) (X1 \ vee X2 \ vee X4)

~ Logic Nikolay.PNG


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Карно
Цикл Карно
Карно, Моріс
Карно, Саді
Бунге Карно (стадіон)
Карно, Іполіт Лазар
Карно, Марі Франсуа Саді
Карта
Звукова карта
© Усі права захищені
написати до нас
Рейтинг@Mail.ru