- •Основы компьютерной арифметики и логики
- •Предисловие
- •Глава 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
Самодвойственные функции
В математике существует понятие двойственности. Самодвойственными называются функции, двойственные самим себе. Применительно к булевым функциям.
Определение 24. Самодвойственной называется булева функция, которая на противоположных наборах аргументов принимает противоположные значения, т.е.
. (5.26)
Монотонные функции
Набор аргументов некоторой многоместной булевой функции представляет собой булев вектор. Введем отношение сравнения наборов. Будем считать, что один набор не больше другого, если одноименные значения аргументов одного набора не превосходят соответствующие значения второго набора.
Например, (1,0,0,1)(1,0,1,1), (1,0,1,0)(1,0,1,1). В то же время, неверно, что (1,0,0,1) (1,0,1,0).
Очевидно, что данное отношение образует частичный порядок на множестве наборов аргументов.
Монотонной называется булева функция, если при возрастании наборов аргументов ее значения не убывают.
Здесь, естественно, считается, что 1>0.
Линейные функции
Определение 25. Функция f(x1,…,xn) называется линейной, если существуют a0, a1,…,an{0,1} такие, что
f (x1,…,xn)=a0 a1x1 … an xn, (5.27)
т.е. если функция представима линейным полиномом Жегалкина. Здесь в качестве операции по умолчанию подразумевается логическое умножение, т.е. конъюнкция (например, a1x1 тождественно a1 x1).
Например, инверсия является линейной функцией ( ), функция конъюнкции не линейна.
Функции, сохраняющие константу
Определение 26. Функция f (x1,…,xn) называется функцией, сохраняющей ноль, если f (0,…,0)=0.
Определение 27. Функция f (x1,…,xn) называется функцией, сохраняющей единицу, если f (1,…,1)=1.
Рассмотренные классы функций, т.е. самодвойственные, монотонные, линейные, сохраняющие ноль и единицу, являются замкнутыми. Не трудно убедиться, что любые функции, полученные из исходных с помощью перенумерации аргументов и подстановок, будут принадлежать к соответствующему классу. И напротив, нельзя посредством подстановок и перенумерации аргументов из функций, не принадлежащих к данному классу, получить функции, принадлежащие к данному классу. Отсюда вытекает теорема Поста.
Теорема 9. В функционально-полной системе переключательных функций должна быть хотя бы одна функция, не являющаяся самодвойственной, линейной, монотонной, не сохраняющая ноль и единицу.
Пример 5.15. Рассмотрим классический базис {, , }. Здесь “” не монотонна, не сохраняет ноль и единицу, ““ и ““– не линейные и не самодвойственные.
Пример 5.16. Можно показать, что функции Шеффера и Пирса (каждая сама по себе) являются базисом, т.е. через любую из них могут быть выражены все возможные булевы функции.
Данный факт нашел широкое применение в технике, например, элемент И-НЕ, реализующий функцию Шеффера, является базовым для ряда серий интегральных микросхем, т.е. является тем основным “кирпичиком”, из которых воздвигаются здания и города аппаратных средств вычислительных систем и комплексов.
Вопросы для самоконтроля
1. К каким классам относится функция эквивалентности?
2. Докажите полноту базиса Жегалкина .