31294

Мінімізація логічних функцій

Практическая работа

Информатика, кибернетика и программирование

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

Украинкский

2013-08-28

449.5 KB

21 чел.

ПРАКТИЧНЕ ЗАНЯТТЯ № 3

 

Тема:    Мінімізація логічних функцій

Мета заняття:  Закріпити отримані теоретичні знання з алгебри логіки та практичні навички з мінімізації логічних схем з використанням карт Карно, навчитися будувати контактні та безконтактні схеми на основі отриманих мінімальних логічних форм

1 ТЕОРЕТИЧНІ  ВІДОМОСТІ

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

Аксіоми алгебри логіки.

1.  - можливість виключення з логічного виразу всіх  членів, що мають подвійне заперечення, замінивши їх вихідною величиною;

2. ;  – правила подібних перетворень, що дозволяють скоротити довжину логічних виразів;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Властивості диз'юнкції і кон’юнкції:

а) асоціативності (сполучний закон)

; ;

б)  комутативності (переміщувальний закон)

;  ;

в) дистрибутивності (розподільний закон)

; ;

Теореми:

а) склеювання

;

б) поглинання

; ;

в) де Моргана

; ;

Для функції Що виключає АБО:

Закони:

а) комутативності

;

б) асоціативності

;

в) дистрибутивності

.

Аксіоми:

;

;

;

.

Правила вираження базисів І, АБО, НЕ через базис Що виключає АБО:

;

;

.

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

Мінімальна форма логічної функції – форма, що містить мінімальну кількість термів чи змінних у термах.

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

Порядок ручної мінімізації логічних функцій за допомогою карт Карно наступний:

1. Терми заносяться в карту (для СКНФ – нулі, для СДНФ - одиниці). Розташування термів у карті Карно для чотирьох логічних змінних проілюстровано на рис. 3.1.

00

01

11

10

00

0

1

3

2

01

4

5

7

6

11

12

13

15

14

10

8

9

11

10

Рис. 3.1

2. Терми поєднують у контури, причому число контурів повинне бути мінімальним, але як можна більшого розміру.

3.  Контури можуть бути прямокутної чи квадратної форми; терми, що розміщуються по діагоналі, у контури не поєднуються.

4. Проводиться операція склеювання. Число розрядів, на яке зменшується вихідний терм, визначається в залежності від величини контуру (2-1, 4-2, 8-3, 16-4) і т.п. Склеюванню підлягають ті аргументи, що змінюються в межах контуру.

5. Записується мінімальна форма.

Карти Карно і діаграми Вейча доцільно застосовувати при числі змінних не більше 5. Якщо їх більше – користуються методами Квайна і Квайна – Мак-Класки.

При необхідності реалізації схеми на контактних елементах за синтезованою функцією слід пам'ятати, що сигнал без інверсії – це розімкнутий контакт, сигнал з інверсією – замкнений (див. рис. 3.2), логічна кон’юнкція – послідовне поєднання контактів, а логічна диз’юнкція – паралельне (див. рис. 3.3).

Рис. 3.2 Рис. 3.3

При реалізації схеми на безконтактних елементах слід застосовувати теорему де Моргана.

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

Щоб показати ефективність логічних перетворень і множинність одержуваних мінімальних форм, розглянемо наступний приклад. Нехай необхідно побудувати на логічних мікросхемах серії К155 декілька варіантів схем, що реалізують задану мінімальну ДНФ (3.1) і порівняти отримані результати.

(3.1)

Схемну реалізацію цієї формули представлено на рис. 3.4.

Рис. 3.4

Оскільки, на підставі довідкової даних, затримки поширення сигналу для елементів ЛР3 і ЛН1 серії К155 однакові, затримка всієї схеми дорівнює . Апаратні витрати складаються з п'яти інверторів ЛН1, кожний з який займає 1/6 корпуса, і елемента І-АБО-НІ - ЛР3, що займає цілий корпус. Разом для схеми за рис. 3.4:

Невикористані елементи частково зайнятого корпуса (у даному випадку шостий інвертор) не враховуються, оскільки вони можуть бути використані в інших вузлах. Підрахунки зручно робити в дванадцятих частках корпуса: 12 – це число логічних виводів корпуса найменшого розміру. Оцінка устаткування в дванадцятих частках корпуса чисельно близька до оцінки устаткування по сумі входів і виходів всіх елементів.

Оскільки в ЛР3 частина входів залишилися невикористаними, можна спробувати реалізувати за допомогою елементів І-НЕ, набір яких має дрібну градацію по числу входів. Застосувавши до (3.1) правило де Моргана, отримаємо:

(3.2)

Реалізацію (3.2) представлено на рис. 3.5.

Рис. 3.5

Параметри схеми: ; . Схема виявилась помітно більш економічною.

Можна спробувати використати формулу де-Моргана для зменшення числа інверторів на вході. Тоді:

(3.3)

Схему, що реалізує (3.3), показано на рис. 3.6.

Рис. 3.6

Для неї ;  корпуса. Вдалося виграти і в часі, і в устаткуванні. Ще одне застосування формули де-Моргана дає:

(3.4)

Схему за формулою (3.4) представлено на рис. 3.7. Її параметри: ; . Схема виявилася дуже економічною, хоча і досить повільною.

Рис. 3.7

Якщо в (3.4) розкрити дужки, то можна отримати ще один варіант схеми (рис. 3.8):

; ; . (3.5)

Рис. 3.8

Затримка цієї схеми виявилася найменшої з усіх розглянутих.

На рис. 3.4-3.8 показано всі отримані схеми, хоча для спрощення функції  просто кілька разів використовувалося правило де-Моргана. Продовжуючи перетворення логічного виразу, можна побудувати ще ряд схем і порівняти зі вже отриманими.

 

2 КОНТРОЛЬНИЙ ПРИКЛАД

Здійснити мінімізацію функції  згідно з завданням: . За допомогою карти Карно отримати мінімальну форму функції, побудувати контактну та безконтактну (на базі елементів І-НІ) схеми.

Рішення

В даному випадку маємо (див. рис. 3.9)

Рис. 3.9

. (3.6)

Контактну схему з урахуванням вихідних теоретичних відомостей  зображено на рис. 3.10.

Рис. 3.10

Для переходу до базису І-НЕ використаємо теорему де-Моргана і отримаємо

. (3.7)

Безконтактну схему для (3.7) зображено на рис. 3.11.

Рис. 3.11

3 ЗАВДАННЯ НА САМОСТІЙНУ РОБОТУ

1. Провести мінімізацію функцій за допомогою карт Карно, та побудувати контактні та безконтактні схеми в логічному базисі І-НІ.

а)

б) .

Для переходу до базису І-НІ використати теорему де-Моргана.

2. Провести можливу мінімізацію форми, отриманої за картою Карно, користуючись теоремою де-Моргана.

4 КОНТРОЛЬНІ ЗАПИТАННЯ

  1.  Назвіть основні аксіоми алгебри логіки.
  2.  Сформулюйте та докажіть основні теореми алгебри логіки.
  3.  Сформулюйте основні властивості логічних операцій.
  4.  Покажіть правила переходу між різними логічними базисами.
  5.  Назвіть етапи мінімізації логічних функцій за допомогою карти Карно.
  6.  В чому заключаються основні принципи побудови контактних схем на основі заданих логічних функцій?
  7.  Як реалізувати безконтактну схему, задану логічною функцією, в конкретному логічному базисі?

 

30


 

А также другие работы, которые могут Вас заинтересовать

46637. Традиційні формули звертання в діловому та науковому стилях 23.5 KB
  Традиційні формули звертання в діловому та науковому стилях. Звертання найяскравіший і часто вживаний вид мовленнєвого етикету. Вибір звертання значною мірою залежить від тональності спілкування. В офіційному здебільшого усному спілкуванні послуговуються цим звертанням у поєднанні з прізвищем або назвою особи за фахом чи родом діяльності напр.
46639. Quite and rather 23.5 KB
  Мы часто употребляем quite в позитивных ситуациях, а rather в негативных: She is quite intelligent but rather lazy. Когда мы употребляем rather с позитивными словами
46640. ОСНОВНЫЕ ИТОГИ СОЦИАЛЬНО–ЭКОНОМИЧЕСКОГО РАЗВИТИЯ СССР К ИСХОДУ 30–Х ГОДОВ 23.6 KB
  На наш взгляд в оценке итогов развития страны к началу 40–х годов следует учитывать два объективных обстоятельства: во–первых конечный результат во–вторых средства и методы с помощью которых он был достигнут. Бесспорно то что в конце 30–хгодов были созданы основные конструкции социалистического общества. К исходу 30–х годов наша страна вышла с пятого места в1913году на второе место в мире после США по объемам валовой промышленной продукции.
46641. Прогнозирование возможной радиационной обстановки и ее оценка 23.62 KB
  Полученные размеры ОЯП и зон РЗ ВП наносят на карту или схему местности с учетом принятого или фактического направления ветра. Методика прогнозирования и оценки зон РЗ местности при ЯВ. На 1 этапе определяют размеры зон Р3 изображают их на карте схеме местности в соответствующих цветах и находят в какую зону по РЗ попал рассматриваемый объект. На 3 этапе разрабатывают текст оповещения населения об опасности РЗ местности и принимают решения по работе персонала объекта.
46642. Образование единых централизованных государств 23.65 KB
  Экспансия государства была в основе своей экспансией сельского хозяйства которое при всей своей первобытности обнаруживало превосходство над кочевниками Юга и Востока. Жадная требовательность государства и скудость крестьянской базы под господствующими классами порождали самые ожесточенные формы эксплуатации. Национальный гнет в России был несравненно грубее чем в соседних государствах не только по западную но и по восточную границу. Если в национально однородных государствах буржуазная революция развивала могучие центробежные тенденции...