Мінімізація функцій перемикання



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

    1.5.1.МетодмінімізаціїКвайна

Вихідною формою поданняфункції для мінімізації за методом Квайна є досконаладиз'юнктивна нормальна форма (ДДНФ).

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

і співвідношенняпоглинання

де A і B - довільнікон'юнктивнітерми, x - змінна.

Для мінімізаціїнеобхідновиконатитакіетапи:

1) записфункції у вихіднійформі - ДДНФ;
2) застосуванняспіввідношеннясклеюванняпослідовно до конституентодиниці, потім до імплікантn-1 рангу, n-2 рангу і так далі, покиможливеформуванняновихімплікант;

         

5.04030101. О-319.ПТЦА.КР.00

 

Арк.
         

16

Змн.. Арк. № докум. Підпис Дата

 

3) виконаннявсіхможливихпоглинань, в результатічоговизначаютьсявсіпростіімпліканти;
4) побудоватаблиціпокриттів (імплікантноїматриці) і знаходженнятупікових ДНФ (ТДНФ);
5) вибірмінімальної ДНФ (МДНФ) з числа ТДНФ.

 

Мінімізація булевих функцій методом Петрика

Петрик формалізував другий етап методу Квайна. Даний метод дозволяє звести роботу з імплікантною матрицею до роботи з аналітичним

         

5.04030101. О-319.ПТЦА.КР.00

 

Арк.
         

17

Змн.. Арк. № докум. Підпис Дата

 

виразом. По імплікантній матриці будується кон'юктивне представлення даної матриці:

1) всі прості імпліканти позначаються буквами

2) для кожного i-го стовпця матриці будується диз'юнкціявсіх букв, що позначають рядки матриці, перетини яких з i-тим стовпцем відмічено хрестиком.

3) кон'юнкція, побудована на диз'юнкції всіх стовпців матриці, і є кон'юктивним представленням імплікантної матриці.

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

 

 

1.5.3Метод мінімізації Квайна - Мак-Класки

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

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

Символом Х в r-кубах відзначаютьсяаргументи, по якихсклеюються (r-1)-куби. Множинакубів i-го рангу утворюють комплексКі.

Етапимінімізації:

1. Для функціївиписують комплекс 0-кубів (К0). Набориупорядковуються за кількістюодиниць. Одержуютьгрупи без одиниць, з однієюодиницею, іздвома і т.д. В цьомувипадкусклеюванняможливетількиміжсусіднімигрупамикубів.

2. Шляхом склеюванняформують 1-куби, 2-куби і т. ін., покиможливе

         

5.04030101. О-319.ПТЦА.КР.00

 

Арк.
         

18

Змн.. Арк. № докум. Підпис Дата

 

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

3.  Шляхом поглинанняформуютьпокриття Z, щовідповідаєскороченій ДНФ.

4. Будують матрицю покриттів, з якої визначають усі ТДНФ.

5. Серед ТДНФ відшукують МДНФ.


1.5.4

         

5.04030101. О-319.ПТЦА.КР.00

 

Арк.
         

19

Змн.. Арк. № докум. Підпис Дата

 

Карти Карно.

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

Алгоритм мінімізації функції перемикання записується таким чином:

1. Переведення функції перемикання в ДДНФ.

2. Нанесення одиниць на карту Карно.

3. Об’єднання сусідніх одиниць контурами, що охоплюють два, чотири або вісім квадратів.

4. Проведення спрощення, виключаючи члени, які доповнюють один одного всередині контуру.

5. Об’єднання членів, що залишилися (по одному у кожному контурі), функцією АБО.

6. Запис мінімізованої функції перемикання в ДДНФ.

 

>

         

5.04030101. О-319.ПТЦА.КР.00

 

Арк.
         

20

Змн.. Арк. № докум. Підпис Дата

 

Розділ ІІРозрахункові дані

Частина І

A=12110B=34510


Дата добавления: 2018-02-18; просмотров: 1069; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!