- •И. В. Потапов элементы прикладной теории цифровых автоматов
- •Оглавление
- •Введение
- •1. Представление чисел в эвм
- •1.1. Позиционные системы счисления
- •1.2. Обоснование применения в эвм двоичной системы счисления
- •1.3. Представление двоичных чисел с фиксированной и плавающей запятой
- •1.4. Прямой и инверсные коды чисел
- •1.5. Двоично-десятичные коды чисел
- •Вопросы для самоконтроля
- •2. Арифметические операции в двоичных кодах
- •2.1. Сложение двоичных кодов
- •2.2. Вычитание двоичных кодов
- •2.3. Выполнение операции округления чисел
- •2.3.1. Округление прямых кодов
- •2.3.2. Округление инверсных кодов
- •2.4. Умножение двоичных кодов
- •2.4.1. Умножение прямых кодов чисел
- •2.4.2. Ускоренное выполнение операции умножения
- •2.4.3. Умножение инверсных кодов чисел
- •2.5. Деление двоичных кодов
- •2.5.1. Деление прямых кодов чисел
- •2.5.2. Ускоренное выполнение операции деления
- •2.5.3. Деление дополнительных кодов чисел
- •2.6. Извлечение квадратного корня
- •2.7. Выполнение арифметических операций в d-кодах
- •2.7.1. Сложение в d-кодах
- •2.7.2. Умножение в d-кодах
- •2.7.3. Деление в d-кодах
- •Вопросы для самоконтроля
- •3. Переключательные функции
- •3.1. Основные определения и способы задания пф
- •3.2. Элементарные логические функции
- •3.3. Основные законы алгебры логики
- •3.4. Полные системы переключательных функций
- •3.5. Канонические формы аналитического представления пф
- •3.6. Кубическое представление пф
- •3.7. Синтез комбинационных схем
- •3.7.1. Синтез кс на логических элементах
- •3.7.2. Синтез кс на дешифраторах
- •3.7.3. Синтез кс на мультиплексорах
- •3.7.4. Синтез многовыходных схем
- •3.8. Риски сбоя в комбинационных схемах
- •Вопросы для самоконтроля
- •4. Минимизация переключательных функций
- •4.1. Минимизация пф с помощью карт Карно
- •4.2. Минимизация пф методом Квайна
- •4.3. Минимизация методом Квайна – Мак-Класки
- •4.4. Минимизация пф методом Блейка – Порецкого
- •4.5. Минимизация пф, заданных в конъюнктивной форме
- •4.6. Минимизация не полностью определенных пф
- •4.7. Минимизация систем пф
- •4.8. Минимизация пф в универсальных базисах и-не, или-не
- •Вопросы для самоконтроля
- •5. Моделирование работы и синтез автоматов с памятью
- •5.1. Основные модели, понятия и определения
- •5.1.1. Общее понятие цифрового автомата с памятью
- •5.1.2. Основные модели цифровых автоматов
- •5.1.3. Описание функционирования цифровых автоматов
- •5.1.4. Задание цифровых автоматов
- •5.1.5. Правила перехода между моделями Мили и Мура
- •5.2. Минимизация числа состояний цифровых автоматов
- •5.2.1. Минимизация числа состояний синхронного автомата методом Полла-Ангера
- •5.2.2. Минимизация числа состояний автомата Мура методом l-эквивалентных разбиений
- •5.2.3. Минимизация числа состояний автомата Мили методом l-эквивалентных разбиений
- •5.3. Структурный синтез цифровых автоматов
- •5.3.1. Типы элементарных автоматов, обладающие полной системой переходов-выходов
- •5.3.2. Основные этапы структурного синтеза
- •5.4. Рациональный выбор варианта кодирования состояний синхронных автоматов
- •Вопросы для самоконтроля
- •Библиографический список
- •Задания для выполнения самостоятельных работ
- •Илья Викторович потапов, канд. Техн. Наук, доцент элементы прикладной теории цифровых автоматов
4.6. Минимизация не полностью определенных пф
ПФ называется не полностью определенной или частично определенной, если число наборов n аргументов, на которых ее значение задано, меньше . С точки зрения практической реализации такой ПФ это может означать, что наборы аргументов, на которых значение функции не определено, никогда не появляются на входах КС либо формируемые на таких наборах выходные сигналы являются несущественными.
Из этого следует, что на таких наборах аргументов функция может быть произвольно доопределена значениями 0 или 1. Обычно доопределение производят, исходя из соображений минимизации. Рассмотрим ПФ, заданную картой Карно (табл. 4.17).
Таблица 4.17
|
x2
|
|
|
|
x1 |
1 |
- |
0 |
1 |
1 |
- |
0 |
0 |
|
|
|
x3 |
|
Значения этой функции определены на шести наборах. Если функцию не доопределять, то минимальная ДНФ запишется в следующем виде:
Доопределим заданную функцию единицами на оставшихся двух наборах (табл. 4.18).
Таблица 4.18
|
x2
|
|
|
|
x1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
|
|
|
x3 |
|
Тогда минимальную ДНФ можно записать в более простом виде:
В некоторых случаях для получения минимальной ДНФ выгодно на некоторых наборах доопределить функцию единицами, а на остальных наборах – нулями или оставить неопределенной. Пусть функция задана картой Карно (табл. 4.19). Доопределим ее единицами сначала на всех неопределенных наборах (табл. 4.20), а затем только на одном из них (табл. 4.21), и запишем для каждой карты Карно получающиеся минимальные ДНФ.
Таблица 4.19
|
x2
|
|
|
|
x1 |
1 |
1 |
0 |
- |
0 |
- |
1 |
0 |
|
|
|
x3 |
|
Таблица 4.20
|
x2
|
|
|
|
x1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
|
|
|
x3 |
|
Таблица 4.21
|
x2
|
|
|
|
x1 |
1 |
1 |
0 |
- |
0 |
1 |
1 |
0 |
|
|
|
x3 |
|
Частичное доопределение не полностью определенной ПФ требует перебора большого числа возможных вариантов и может дать ощутимую выгоду при минимизации на картах Карно для функций небольшого числа аргументов.
Для применения других методов минимизации (например, метод Квайна – Мак-Класки) удобно доопределить функцию на всех неопределенных наборах (единицами или нулями) и выполнить следующие шаги:
1) любым способом найти сокращенную ДНФ (КНФ);
2) по импликантной матрице Квайна определить минимальную совокупность простых импликант, накрывающую только те конституенты 1 (конституенты 0), которые соответствуют наборам, на которых функция была изначально определена.