- •И. В. Потапов элементы прикладной теории цифровых автоматов
- •Оглавление
- •Введение
- •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. Рациональный выбор варианта кодирования состояний синхронных автоматов
- •Вопросы для самоконтроля
- •Библиографический список
- •Задания для выполнения самостоятельных работ
- •Илья Викторович потапов, канд. Техн. Наук, доцент элементы прикладной теории цифровых автоматов
3.5. Канонические формы аналитического представления пф
Конституентой единицы называется функция, принимающая значение 1 только на одном наборе переменных. Конституента единицы записывается как логическое произведение n различных переменных, некоторые из которых или все могут быть с отрицаниями.
Конституентой нуля называется функция, принимающая значение 0 на единственном наборе переменных. Конституента нуля записывается как логическая сумма n различных переменных, часть которых или все могут быть с отрицаниями.
Любую конституенту 1 можно записать в виде конъюнкции всех ее аргументов, при этом переменная записывается с инверсией, если в наборе, на котором функция принимает значение 1, переменная принимает значение 0. Например, логическое произведение соответствует конституенте 1, принимающей единичное значение на наборе , , . На всех остальных наборах, как следует из определения, конституента 1 принимает значение 0. Вышеприведенное утверждение может быть доказано, например, методом перебора.
Каждому i-му набору аргументов поставим в соответствие конституенту единицы , принимающую единичное значение только на этом наборе.
Любую переключательную функцию, зависящую от n аргументов, можно представить в виде разложения Шеннона:
.
Произведем разложение Шеннона по всем переменным:
В полученном выражении заменим наборы аргументов, представленных конъюнкциями переменных, на соответствующие конституенты 1. Тогда переключательная функция в общем виде может быть представлена следующим образом:
,
где – значение функции на i-м наборе.
Воспользовавшись тем, что и , в последнем выражении можно исключить слагаемые, для которых . Учитывая, что , можно не писать коэффициенты .
Таким образом, искомую функцию можно представить в виде дизъюнкции конституент 1, соответствующих наборам аргументов, на которых она принимает значение 1. Такая форма записи называется совершенной дизъюнктивной нормальной формой (СДНФ). Такое название объясняется тем, что каждый дизъюнктивный член включает в себя произведение всех n аргументов (совершенная форма) и каждое произведение является элементарным, т.е. под знаком инверсии могут быть только отдельные переменные (нормальная форма).
В качестве примера рассмотрим процедуру записи СДНФ логической функции , заданной таблицей истинности (табл. 3.7). Для представления этой функции в виде СДНФ необходимо выполнить следующие действия, основанные на вышеприведенных рассуждениях.
Таблица 3.7
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
На первом этапе запишем функцию в виде дизъюнкции конституент единицы, соответствующих тем наборам, на которых функция принимает значение 1:
Затем, выразив конституенты единицы через произведения аргументов, получим искомую СДНФ:
Из СДНФ функции и СДНФ ее отрицания, используя законы де Моргана, можно получить еще семь канонических форм.
Другой канонической формой записи является совершенная конъюнктивная нормальная форма (СКНФ). Ее отличие от СДНФ заключается в том, что СКНФ записывается как конъюнкция конституент нуля, соответствующих тем наборам, на которых функция принимает значение 0. При этом конституенты 0 записываются в виде элементарных дизъюнкций аргументов xi, инверсии которых соответствуют единичному значению аргумента.
Для примера запишем СКНФ функции, заданной табл. 3.7, при этом выполним последовательность действий, аналогичную той, которая была приведена в предыдущем примере.
На первом этапе запишем функцию в виде конъюнкции конституент нуля, соответствующих тем наборам, на которых функция принимает значение 0:
Далее, выразив конституенты нуля через дизъюнкции аргументов, получим искомую СКНФ:
С помощью законов де Моргана СКНФ функции можно получить из СДНФ ее отрицания, записываемой по нулям. В качестве примера рассмотрим преобразование отрицания СДНФ функции, заданной табл. 3.7:
откуда, избавляясь от операции отрицания в начальной и конечной частях выражения, получим
.
В СДНФ можно заменить операцию дизъюнкции операцией суммы по модулю 2. В том, что равенство при этом сохранится, можно убедиться путем сопоставления таблиц истинности получившихся выражений. Для рассмотренного выше примера:
Такая форма называется совершенной полиномиальной нормальной формой (СПНФ).
Воспользуемся соотношением и заменим в СПНФ все переменные с отрицаниями на суммы вида . После упрощения полученного выражения образуется канонический полином Жегалкина, который в общем виде можно записать следующим образом [4]:
Для рассматриваемого примера: