- •Основы компьютерной арифметики и логики
- •Предисловие
- •Глава 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.6. Синтез составных кс
В общем случае для минимизации систем ПФ может быть использован модифицированный алгоритм Квайна-Мак-Класки, рассмотренный в п. 5.2.7. Реализация КС для примера 5.27. приведена на рис. 5.28.
;
;
Рис. 5.28. Комбинационная схема для системы ПФ
В ряде специальных случаев при реализации систем ПФ можно ограничиться более простыми методами. Для системы из двух булевых функций рассмотрим следующие частные случаи:
остальные,
где - множество 0-кубов функции f, т.е. наборов, соответствующих истинным значениям; - множество наборов, соответствующих ложным значениям функции f.
Рассмотрим приемы синтеза КС на примерах.
Пример 5.34. Две ПФ заданы на картах Карно (рис. 5.29).
х2 х2 f1 f2
х1 |
|
|
|
х1 |
|
|
|
|
|
1 |
1 |
|
х3 |
|
|
|
х3 |
|
1 |
|
1 |
|
|
1 |
|
1 |
1 |
x4 |
1 |
1 |
|
1 |
x4 |
|
1 |
Рис. 5.29. Представление на картах Карно системы
из двух ПФ при
Найдем минимальные ДНФ для и :
,
,
отсюда очевидно, что здесь .
.
Здесь терм поглощает , однако последний необходимо оставить, чтобы обеспечить реализацию функции . На рис. 5.30 приводится реализация КС, реализация первого уровня, обеспечивающего инверсии входных переменных, не показана.
f1 f2
Рис. 5.30. Пример КС системы для случая
В случае можно провести минимизацию по нулям и поступить аналогично.
Пример 5.35. ПФ заданы на картах Карно рис. 5.31. Реализовать комбинационную схему.
х2 х2 f1 f2
х1 |
1 |
1 |
|
х1 |
1 |
0 |
0 |
1 |
|
|
|
|
х3 |
1 |
1 |
1 |
х3 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
0 |
1 |
х4 |
1 |
1 |
|
1 |
х4 |
0 |
0 |
Рис. 5.31. Карты Карно для случая
В данном случае . По картам Карно получим
,
.
Минимизируя по нулям, получим
,
.
При минимизации по единицам оценим сложность КС по критерию Квайна , при минимизации по нулям получим (показатели сложности получены без учета инверсий для входных аргументов, поскольку таковые уже используются для реализации ). Таким образом, для реализации используем минимальную форму, полученную по единицам. Схема приводится на рис 5.32.
Рис. 5.32. Пример КС системы для случая
В самом общем случае мы имеем частичное перекрытие комплекса или одной функции с комплексом ( или ) другой функции. В данной ситуации необходимо рассмотреть несколько вариантов реализации и выбрать наиболее эффективный, например, в смысле критерия Квайна. Здесь часто оказывается важным выделить максимально большую общую часть.
Пример. 5.36. Пусть две ПФ заданы на картах Карно рис. 5.33.
х2 х2
х1 х1
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
|
0 |
0 |
1 |
0 |
х3 х3
Рис. 5.33. Пример частичного перекрытия комплексов функций
Запишем выражения для минимальных форм, используя минимизацию по единицам и по нулям:
,
,
,
.
Используя выражения для и , реализуя общую часть выражения (взятую в скобки) отдельной схемой, построим КС (рис. 5.34а).
а) б)
Рис. 5.34. Примеры составных КС
Данная схема имеет сложность .
По карте Карно для и можно выделить общую часть (на рис. 5.33 отмечена пунктиром).
, отсюда
,
.
КС, реализующий данный способ, приводится на рис. 5.34б, сложность данной схемы составляет . Очевидно, что первый способ реализации более эффективный.
В данном учебном пособии мы рассмотрели некоторые методы и практические рекомендации к реализации комбинационных схем на ЛЭ. Более подробно с данным вопросом можно ознакомиться, например, в [9].
Вопросы для самоконтроля
1. Постройте комбинационные схемы в различных базисах для заданий к п. 5.2.