Основы компьютерной арифметики и логики

Учебное пособие

Омск– 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, подготовленной доцентом И.В. Червенчуком, рассматриваются фундаментальные вопросы математической логики и задачи синтеза комбинационных схем на логических элементах, а также свойства булевых функций и вопросы их минимизации известными в инженерной практике методами.

Учебное пособие иллюстрировано многочисленными примерами и содержит вопросы для самоконтроля.