- •Основы компьютерной арифметики и логики
- •Предисловие
- •Глава 4, подготовленная доцентом о.П. Шафеевой, посвящена вопросам разработки алгоритмических моделей выполнения арифметических операций и моделирования на пэвм спроектированных алгоритмов.
- •Основы двоичной компьютерной арифметики
- •1.1. Позиционные системы счисления
- •Десятичная позиционная система счисления
- •Двоичная позиционная система счисления
- •1.1.3. Восьмеричная позиционная система счисления
- •1.1.4. Шестнадцатеричная позиционная система счисления
- •Сложение Вычитание
- •Перевод чисел из одной позиционной системы счисления в другую
- •1.2.1. Перевод целых чисел
- •1.2.2. Перевод правильных дробей
- •1.2.3. Перевод неправильных дробей из одной системы счисления в другую
- •1.2.4. Частный случай перевода чисел из одной системы счисления в другую
- •1.2.5. Перевод чисел из одной системы счисления в другую с использованием промежуточной двоично-десятичной системы
- •1.3. Представление чисел с фиксированной запятой (точкой)
- •1.4. Представление чисел с плавающей запятой (точкой)
- •1.5. Коды двоичных чисел
- •1.5.1. Прямой код
- •1.5.2. Обратный код
- •1.5.3. Модифицированный обратный код
- •1.5.4. Дополнительный код
- •2.1.1. Алгебраическое сложение чисел в дополнительном коде
- •2.1.2. Алгебраическое сложение чисел в обратном коде
- •2.1.3. Переполнение разрядной сетки при сложении чисел
- •2.2. Сложение (вычитание) двоичных чисел с плавающей запятой
- •2.2.1. Метод ускоренного сложения двоичных чисел с запоминанием переносов
- •2.3. Умножение двоичных чисел с фиксированной запятой
- •2.4. Машинные технологии выполнения операции умножения двоичных чисел с фиксированной запятой
- •2.5. Умножение двоичных чисел с плавающей запятой
- •2.6. Методы ускоренного выполнения операции умножения двоичных чисел
- •2.6.1. Метод пропуска такта суммирования
- •2.6.2. Метод анализа сомножителей
- •2.6.3. Метод расшифровки и одновременного умножения на два разряда множителя
- •2.6.4. Метод ускоренного умножения Мак-Сорли
- •2.6.5. Метод ускоренного умножения Лемана
- •2.6.6. Метод умножения с расшифровкой пар разрядов множителя и запоминанием переносов
- •2.7. Деление двоичных чисел с фиксированной запятой
- •2.8. Деление двоичных чисел с плавающей запятой
- •3. Основы десятичной компьютерной арифметики
- •3.1. Машинное кодирование десятичных чисел
- •3.2. Выполнение арифметических операций с десятичными числами
- •3.2.1. Сложение десятичных чисел в эвм
- •3.2.2. Умножение десятичных чисел в эвм
- •3.2.3. Ускорение умножения в -кодах
- •Деление десятичных чисел в эвм
- •4.2. Моделирование алгоритма сложения двоичных чисел
- •Различные случаи ненормализованных мантисс
- •4.3. Проектирование алгоритма умножения чисел
- •4.5. Проектирование алгоритма деления чисел
- •4.7. Разработка алгоритма вычисления квадратного корня
- •Определение 1. Пусть и произвольные множества. Соответствием называется тройка множеств
- •Свойства отношений
- •Эквивалентность
- •Толерантность
- •Отношения порядка
- •Самодвойственные функции
- •Монотонные функции
- •Линейные функции
- •Функции, сохраняющие константу
- •5.2.7. Минимизация булевых функций
- •Метод Блейка
- •Метод Квайна-Мак-Класки
- •Минимизация с использованием карт Карно
- •Дана функция четырех переменных (рис. 5.13):
- •Минимизация не полностью определенных булевых функций
- •Минимизация систем булевых функций
- •5.3. Методика синтеза комбинационных схем на логических элементах
- •5.3.1. Логические элементы
- •5.3.2. Общий алгоритм построения комбинационных схем
- •5.3.3. Синтез кс в классическом базисе
- •5.3.4. Синтез кс в базисах «и-не», «или-не»
- •5.3.5. Реализация кс в базисе Жегалкина
- •5.3.6. Синтез составных кс
- •Заключение
- •Библиографический список к главам 1, 2, 3, 4
- •Библиографический список к главе 5
5.3.4. Синтез кс в базисах «и-не», «или-не»
Реализация КС в базисе И-НЕ без ограничения на число входов ЛЭ достаточно проста. Пусть булева функция задана в ДНФ.
,
где означает либо либо . Выполним преобразование:
.
Применяя правила Де Моргана, получим
.
Таким образом, булева функция, заданная в ДНФ может быть реализована в базисе «И-НЕ» трехранговой КС. Первый ранг – двухвходовые элементы, играющие роль инверторов; второй ранг – элементы, реализующие элементарные дизъюнкты; третий ранг – объединительный элемент.
Для выражения из примера 5.28 имеем
,
.
Комбинационная схема в базисе «И-НЕ» приведена на рис. 5.24.
Рис. 5.24. Схема в базисе «И-НЕ» без ограничений на количество входов
Для синтеза КС в базисе «ИЛИ-НЕ» удобно использовать выражение для , полученное при минимизации по нулям.
Пример 5.31. Для задания из примера 5.24 имеем
,
,
.
Схема приводится на рис. 5.25.
Рис. 5.25. Схема в базисе «ИЛИ-НЕ»
Если наложено требование, ограничивающее число входов ЛЭ до двух, для реализации сложных термов можно использовать преобразования:
,
.
При реализации сложных термов одинаковые пары переменных реализуются на одном элементе, например
.
В данном примере части выражения в скобках будут реализованы один раз (на трех элементах «И-НЕ», два из них в роли инвертора), соответствие между выражением и КС обеспечивается посредством связей (с выхода последнего элемента, реализующего выражения в скобках (точка V схемы рис. 5.26б), будут исходить две связи в соответствии со структурой выражения). Схема данных фрагментов КС приводится на рис. 5.26, схема без ограничения на число входов приводится на рис. 5.26а (С=10), схема на двухвходовых элементах «И-НЕ» приводится на рис. 5.26б (С=12).
а) б)
Рис. 5.26. Схемы в базисе «И-НЕ»
Примеры, применяемые при реализации КС на базе двухвходовых элементов «ИЛИ-НЕ», аналогичны описанным.
5.3.5. Реализация кс в базисе Жегалкина
Как было рассмотрено ранее, базис Жегалкина соответствует сигнатуре .
Если булева функция задана в СДНФ, переход к базису Жегалкина достаточно прост. В выражении СДНФ знак «» (или) можно заменить на «» (исключающее или). Данная замена вполне правомочна, поскольку в СДНФ при определенном наборе аргументов только один терм может давать истинное выражение.
Пример 5.32. Представить в базисе Жегалкина и построить КС для булевой функции, заданный СДНФ:
, отсюда
.
Используя, что , выполним замены:
Учитывая, что , получим
.
Выражение упрощается посредством вычеркивания одинаковых термов, если они повторяются в выражении четное число раз. Реализация КС показана на рис 5.27.
Рис. 5.27. Схема в базисе Жегалкина
Имея выражения для булевой функции в произвольной ДНФ (конечно лучше иметь минимальную форму), для перехода к базису Жегалкина можно использовать соотношение
. (5.29)
Пример 5.33. Для предыдущего примера ,
.
Реализация в виде КС приведена на рис. 5.27.