1.4 Контроль за модулем
Контроль виконання арифметичних і логічних операцій можна здійснювати за допомогою контрольних кодів, що представляють собою залишки від ділення чисел на деякий модуль. Такий контроль називається контролем по модулю. Для двійкових чисел цей модуль звичайно дорівнює або більше 3. Розрізняють числовий і цифровий контроль за модулем.
При числовому методі код заданого числа визначається як найменший позитивний залишок від ділення числа на обраний модуль.
При цифровому методі контролю контрольний код числа утворюється діленням суми цифр числа на обраний модуль.
У даному варіанті можливі два шляхи отримання контрольного коду:
1) безпосереднє ділення суми цифр на модуль;
2) просто підсумовування цифр по вибраному модулю.
1.5 Мінімізація функцій перемикання
Одна із основних задач, що виникає при синтезі комбінаційних схем, є мінімізація функцій перемикання, які ці комбінаційні схеми реалізують. Чим простіший логічний вираз, тим простіша і дешевша комбінаційна схема, що реалізує його.
1.5.1. Метод мінімізації Квайна
Вихідною формою подання функції для мінімізації за методом Квайна є досконала диз'юнктивна нормальна форма (ДДНФ).
Метод забезпечує одержання скороченої ДНФ (СДНФ), тобто сукупності всіх простих імплікант. Метод базується на використанні співвідношення неповного склеювання
і співвідношення поглинання
де A і B - довільні кон'юнктивні терми, x - змінна.
Для мінімізації необхідно виконати такі етапи:
1) запис функції у вихідній формі - ДДНФ; 2) застосування співвідношення склеювання послідовно до конституент одиниці, потім до імплікант n-1 рангу, n-2 рангу і так далі, поки можливе формування нових імплікант; 3) виконання всіх можливих поглинань, в результаті чого визначаються всі прості імпліканти; 4) побудова таблиці покриттів (імплікантної матриці) і знаходження тупікових ДНФ (ТДНФ); 5) вибір мінімальної ДНФ (МДНФ) з числа ТДНФ.
1.5.2 Мінімізація булевих функцій методом Петрика
Петрик формалізував другий етап методу Квайна. Даний метод дозволяє звести роботу з імплікантною матрицею до роботи з аналітичним виразом. По імплікантній матриці будується кон'юктивне представлення даної матриці:
всі прості імпліканти позначаються буквами
для кожного i-го стовпця матриці будується диз'юнкція всіх букв, що позначають рядки матриці, перетини яких з i-тим стовпцем відмічено хрестиком.
кон'юнкція, побудована на диз'юнкції всіх стовпців матриці, і є кон'юктивним представленням імплікантної матриці.
До отриманого виразу можуть бути застосовані всі співвідношення булевої алгебри з метою його спрощення. Після розкриття дужок і всіх можливих поглинань отримаємо диз'юнкцію кон'юнкцій, кожна з яких містить імпліканти тупикових функцій.
1.5.3 Метод мінімізації Квайна - Мак-Класки
Метод Квайна - Мак-Класки є модифікацією методу Квайна. Він ґрунтується на співвідношеннях неповного склеювання і поглинання, як і метод Квайна. Особливістю методу є використання цифрової форми запису перемикальних функцій. В цьому випадку зменшується число символів для подання термів і число операцій в процесі мінімізації, що робить метод зручним при програмній реалізації.
Якщо використовувати геометричну інтерпретацію подання перемикальних функцій, то кожен набір аргументів є n-вимірним вектором (n - число аргументів) і визначає точку n-вимірного простору. Сукупність усіх наборів зображає n-вимірний куб. Конституентам відповідають вершини куба, а імплікантам - ребра і грані. Кожній конкретній функції відповідає певне просторове зображення.
Символом Х в r-кубах відзначаються аргументи, по яких склеюються (r-1)-куби. Множина кубів i-го рангу утворюють комплекс Кі.
Етапи мінімізації:
Для функції виписують комплекс 0-кубів (К0). Набори упорядковуються за кількістю одиниць. Одержують групи без одиниць, з однією одиницею, із двома і т.д. В цьому випадку склеювання можливе тільки між сусідніми групами кубів.
Шляхом склеювання формують 1-куби, 2-куби і т. ін., поки можливе
склеювання. Кожен куб упорядковується аналогічно 0-кубу. При цьому в одну групу повинні входити куби, що мають не тільки однакове число одиниць, але й залежать від тих самих змінних.
Шляхом поглинання формують покриття Z, що відповідає скороченій ДНФ.
Будують матрицю покриттів, з якої визначають усі ТДНФ.
Серед ТДНФ відшукують МДНФ.