ОСНОВЫ КОМПЬЮТЕРНОЙ АРИФМЕТИКИ И ЛОГИКИ
Учебное пособие
Омск– 2004
УДК 004.9(075)
ББК 32.973.202+22.12 я 73
П 64
Рецензенты:
С.А. Терентьев, канд. физ.-мат. наук, Омский государственный университет;
О.Н. Лучко канд. пед. наук, Омский государственный институт сервиса
Потапов В.И., Шафеева О.П., Червенчук И.В.
П 64 Основы компьютерной арифметики и логики:Учеб.пособие. – Омск: Изд- во
ОмГТУ, 2004. – 172 с.
Изложены основы двоичной и десятичной компьютерной арифметики, алгоритмы выполнения арифметических операций в ЭВМ для двоичных чисел с фиксированной и плавающей запятой и для двоично-десятичных чисел в D-кодах. Рассмотрены методы ускорения выполнения основных арифметических операций в ЭВМ в двоичной и в двоично-десятичной системе счисления. Описаны алгоритмические модели выполнения арифметических операций и изложены методы их проектирования. Даются основные понятия математической логики и методы синтеза комбинационных схем.
Предназначено для студентов направления «Информатика и вычислительная техника».
Печатается по решению редакционно-издательского совета Омского государственного технического университета.
УДК 004.9(075)
ББК 32.973.202+22.12 я 73
© Авторы, 2004
© Омский государственный
технический университет, 2004
| | |||
 |
| ОГЛАВЛЕНИЕ | ||
| Предисловие………………………………………………………………… | ||
| 1. | Основы двоичной компьютерной арифметики ……………………….. | |
| 1.1. | Позиционные системы счисления …………………………………………. | |
| 1.1.1. | Десятичная позиционная система счисления …………………….………. | |
| 1.1.2. | Двоичная позиционная система счисления ……………………..………… | |
| 1.1.3. | Восьмеричная позиционная система счисления ………………………….. | |
| 1.1.4. | Шестнадцатеричная позиционная система счисления …………………… | |
| 1.2. | Перевод чисел из одной позиционной системы счисления в другую…… | |
| 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. | Дополнительный код ……………………………………………………….. | |
| 1.5.5. | Модифицированный дополнительный код ……………………………….. | |
| 2. | Выполнение арифметических операций с двоичными числами …… | |
| 2.1. | Сложение (вычитание) двоичных чисел с фиксированной запятой …….. | |
| 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. | Ускорение умножения в D-кодах ………………………………………….. | |
| 3.2.4. | Деление десятичных чисел в ЭВМ ………………………………………... | |
| 4. | Алгоритмические модели выполнения арифметических операций... | |
| 4.1. | Проектирование универсального алгоритма перевода чисел в разные системы счисления ………………………………………………. | |
| 4.2. | Моделирование алгоритма сложения двоичных чисел ………………….. | |
| 4.3. | Проектирование алгоритма умножения чисел ……………………………. | |
| 4.4. | Разработка алгоритма ускоренного умножения с обработкой за один такт трех разрядов множителя ……………………………………. | |
| 4.5. | Проектирование алгоритма деления чисел ……………………………….. | |
| 4.6. | Разработка алгоритма ускоренного выполнения операции деления с анализом за один такт двух разрядов делителя ………………………… | |
| 4.7. | Разработка алгоритма вычисления квадратного корня …………………... | |
| 5. | Математическая логика и синтез комбинационных схем …………… | |
| 5.1. | Соответствия и предикаты …………………………………………………. | |
| 5.1.1. | Соответствия ………………………………………………………………... | |
| 5.1.2. | Логические функции ……………………………………………………….. | |
| 5.1.3. | Признаки …………………………………………………………………….. | |
| 5.1.4. | Бинарные отношения………………………………………………………... | |
| 5.2. | Булевы функции …………………………………………………………….. | |
| 5.2.1. | Логические операции соединения………………………………………….. | |
| 5.2.2. | Булевы формулы…………………………………………………………….. | |
| 5.2.3. | Совершенные дизъюнктивные нормальные формы ……………………… | |
| 5.2.4. | Булева алгебра ………………………………………………………………. | |
| 5.2.5. | Конъюнктивные нормальные формы …………………………………… | |
| 5.2.6. | Классы булевых функций. Понятие базиса………………………………... | |
| 5.2.7. | Минимизация булевых функций…………………………………………… | |
| 5.3. | Методика синтеза комбинационных схем на логических элементах…..... | |
| 5.3.1. | Логические элементы……………………………………………………….. | |
| 5.3.2. | Общий алгоритм построения комбинационных схем…………………….. | |
| 5.3.3. | Синтез КС в классическом базисе………………………………………….. | |
| 5.3.4. | Синтез КС в базисах «И-НЕ», «ИЛИ-НЕ»………………………………… | |
| 5.3.5. | Реализация КС в базисе Жегалкина………………………………………... | |
| 5.3.6. | Синтез составных КС……………………………………………………….. | |
| Заключение…………………………………………………………………. | ||
| Библиографический список……………………………………………… |
ПРЕДИСЛОВИЕ
В учебных планах подготовки дипломированных специалистов по специальности 220100 – «Вычислительные машины, комплексы, системы и сети» и направлению 552800 – «Информатика и вычислительная техника» дисциплины «Дискретная математика», «Введение в информатику и вычислительную технику», «Алгоритмические языки и программирование» входят в состав фундаментального цикла дисциплин, формирующих у студентов представление о базовых понятиях информатики и вычислительной техники как о предмете их дальнейшей профессиональной деятельности. Изучение указанных дисциплин и овладение навыками разработки и моделирования алгоритмов реализации арифметических и логических компьютерных операций, синтеза логических схем создает теоретическую базу для изложения таких дисциплин, как «Теория автоматов», «Организация ЭВМ и систем», «Микропроцессорные системы» и других специальных курсов.
В главах 1, 2, 3, подготовленных профессором В.И. Потаповым, изложены основы двоичной и десятичной компьютерной арифметики, алгоритмы выполнения арифметических операций в ЭВМ для двоичных чисел с фиксированной и плавающей запятой (точкой) и для двоично-десятичных чисел в D-кодах. Рассмотрены многочисленные методы ускоренного выполнения арифметических операций в ЭВМ в двоичной и в двоично-десятичной системе счисления.
Глава 4, подготовленная доцентом О.П. Шафеевой, посвящена вопросам разработки алгоритмических моделей выполнения арифметических операций и моделирования на ПЭВМ спроектированных алгоритмов.
В главе 5, подготовленной доцентом И.В. Червенчуком, рассматриваются фундаментальные вопросы математической логики и задачи синтеза комбинационных схем на логических элементах, а также свойства булевых функций и вопросы их минимизации известными в инженерной практике методами.
Учебное пособие иллюстрировано многочисленными примерами и содержит вопросы для самоконтроля.