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