- •Министерство образования и науки украины
- •Содержание
- •Глава 1 Арифметико-логические основы эвм
- •1.1 Информационные процессы
- •1.2. Обмен информацией между различными информационными устройствами
- •1.3. Аппаратные средства хранения и обработки информации
- •Глава 2 представление числовой информации в цифровом автомате
- •2.1. Системы счисления и понятие кода
- •2.2. Выбор системы счисления
- •2.3. Формальные правила двоичной арифметики
- •2.4. Перевод числа из одной позиционной системы счисления в другую
- •Глава 3 формы представления чисел в цифровых автоматах
- •3.1. Форма представления двоичных чисел с фиксированной запятой
- •3.2. Представление отрицательных чисел в формате с фиксированной запятой
- •3.3. Форма представление чисел с плавающей запятой
- •3.4. Перевод чисел из формата с фиксированной запятой в формат с плавающей запятой и обратно
- •3.5. Погрешности представления чисел
- •20 [A]ф2n- 1 для целых чисел
- •Глава 4. Арифметические действия с двоичными числами
- •4.1. Сложение двоичных чисел
- •4.1.1. Алгебраическое сложение чисел, представленных в форме с фиксированной запятой
- •4.1.2. Переполнение разрядной сетки
- •4.1.3. Модифицированный прямой, обратный и дополнительный код
- •4.1.4. Алгебраическое сложение чисел, представленных в форме с плавающей запятой
- •4.2. Умножение двоичных чисел
- •4.2.1. Методы умножения двоичных чисел
- •4.2.2. Умножение чисел, представленных в форме с фиксированной запятой
- •4.2.3. Умножение чисел, представленных в форме с плавающей запятой
- •4.2.4. Ускорение операции умножения
- •4.3. Деление двоичных чисел
- •4.3.1. Деление двоичных чисел, представленных в форме с фиксированной запятой.
- •4.3.2. Деление двоичных чисел, представленных в форме с плавающей запятой.
- •4.4. Оценка точности выполнения арифметических операций
- •4.4.1. Погрешность округления
- •Глава 5. Выполнение операций над двоично-десятичными числами
- •5.1. Представление десятичных чисел в д-кодах
- •5.2. Формальные правила поразрядного сложения в д-кодах
- •5.3. Представление отрицательных чисел в д-кодах
- •5.4. Выполнение операций сложения и вычитания в д-кодах
- •5.5. Умножение чисел в д-кодах
- •5.6. Деление чисел в д-кодах
- •5.7. Перевод чисел из д-кода в двоичный и из двоичного в д-код
- •Глава 6 Информационные основы цифровых автоматов
- •6.1. Понятие об информации и её преобразованиях
- •6.2. Преобразования алфавитной информации
- •6.3 Понятие об алгоритме
- •6.4 Понятие о дискретном (цифровом) автомате
- •Глава 7 Основы логического проектирования ца. Основные понятия алгебры логики.
- •7.1. Свойства элементарных функций алгебры логики
- •7.2. Аналитическое представление функций алгебры логики
- •7.3. Совершенные нормальные формы
- •7.4. Системы функций алгебры логики
- •7.5. Числовое и геометрическое представление фал
- •Глава 8 Минимизация функций алгебры логики
- •8.1 Метод Квайна
- •Ядро: мднф:
- •8.2 Метод Квайна-Мак-Класки
- •Простые импликанты: *111, 111*, 0**1
- •8.3 Метод Нельсона
- •8.4 Метод диаграмм Вейча
- •8.5 Метод самопонижающихся циклов
- •8.6 Минимизация монотонных функций
- •8.7 Минимизация конъюнктивных нормальных форм
- •8.8 Минимизация частично определенных булевых функций
- •8.9 Минимизация функций в базисах и-не и или-не
- •8.10 Минимизация систем булевых функций
- •Глава 9 Абстрактная теория автоматов
- •9.2 Декомпозиция абстрактных автоматов
- •Глава 10 Структурная теория автоматов
- •10.1 Композиция автоматов
- •Глава 11 Проектирование асинхронных цифровых автоматов
- •11.1 Проектирование комбинационных схем (кс) с учетом кобъед по входу и по выходу
- •11.2 Проектирование кс на дешифраторах и мультиплексорах
- •11.3 Проектирование кс на пзу
- •11.4 Проектирование кс на плм
- •Глава 12 Канонический метод структурного синтеза ца с памятью
- •12.1 Кодирование
- •12.2 Выбор элементов памяти автомата
- •12.3 Выбор структурно-полной системы элементов
- •12.4 Построение уравнений булевых функций возбуждения и выходов автомата
- •12.5 Построение функциональной схемы автомата
- •Глава 13 Обеспечение устойчивости функционирования ца
- •13.2 Проблема синтеза надёжных схем из ненадёжных элементов
- •13.3 Коды Хэмминга
- •Глава 14 Микропрограммные автоматы
- •14.2 Граф-схемы алгоритмов
8.3 Метод Нельсона
Метод позволяет получить СкДНФ булевой функции из ее произвольной КНФ. Если в произвольной КНФ булевой функциираскрыть все скобки и произвести все поглощения, то в результате будет получена СкДНФ булевой функции.
Пример:
Найдем СкДНФ:
Произведем поглощения: - СкДНФ.
8.4 Метод диаграмм Вейча
Метод получает МДНФ булевой функции небольшого числа переменных. Булевы функции задаются в виде специальных диаграмм. Для функции 2-х переменных и 3-х переменных:
Добавление к диаграмме 3-х переменных еще такой же даст диаграмму 4-х переменных, если приписать еще одну диаграмму 4-х переменных, то получим диаграмму для функции 5-ти переменных.
Правила склеивания конституэнт "1" на диаграммах Вейча: склеиванию подлежат прямоугольные конфигурации, заполненные конституэнтами "1" и содержащие число клеток, являющееся степенью 2. Получающееся новое элементарное произведение определяется как произведение переменных, не меняющих своего значения на всех склеиваемых наборах. Минимизация булевой функции заключается в нахождении минимального накрытия всех единиц диаграммы Вейча блоками из единиц, расположенных в соседних клетках диаграммы.
Примеры: Булевы функции заданы диаграммами Вейча. Найти их МДНФ.
8.5 Метод самопонижающихся циклов
М
x1 x2 … xm-3 xn-2 xn-1 xn f … … … … … … … … … n 0 0 0 1 … n 0 0 1 1 .
. 0 1 0 1 .
. 0 1 1 1 .
. 1 0 0 1 .
. 1 0 1 1 .
. 1 1 0 1 … n 1 1 1 1 … … … … … … … …
Если в таблице истинности произвольной булевой функции существует фрагмент вида (см. таблицу), то ее СкДНФ на этом фрагменте описывается выражением, так как по переменнымможет быть произведено полное склеивание. Никаких ограничений на число склеенных переменных и размещение их во фрагменте таблицы истинности булевой функции не накладывается. Если имеется фрагмент, содержащийдвоичных наборов длины n, где m – число склеенных переменных, то такой фрагмент описывается конъюнкцией ранга (n-m) в представлении булевой функции СкДНФ по этому фрагменту. Фрагмент вида (см. таблицу) называется самопонижающимся циклом, а число склеенных переменных во фрагменте – рангом самопонижающегося цикла.
Пример:
Найти СкДНФ булевой функции методом самопонижающихся циклов. Функция задана таблицей истинности.
Ищем циклы максимального ранга. Имеется только один такой цикл №1. Найденный цикл покрывает не все "1" таблицы истинности функции .
Ищем циклы ранга . Имеется два таких цикла №2 и №3. Цикл №3 полностью содержится в цикле №1, поэтому цикл №3 не рассматривается. Поиск цикла меньшего ранга не нужен, так как циклы 1 и 2 полностью покрывают конституэнты "1" функции .
СкДНФ: