- •Основы компьютерной арифметики и логики
- •Предисловие
- •Глава 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
Министерство образования и науки Российской Федерации
Омский государственный технический университет
В. И. Потапов, О.П. Шафеева, И.В. Червенчук
Основы компьютерной арифметики и логики
Учебное пособие
Омск– 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
|
ОГЛАВЛЕНИЕ |
|
|
Предисловие………………………………………………………………… |
5 |
1. |
Основы двоичной компьютерной арифметики ……………………….. |
6 |
1.1. |
Позиционные системы счисления …………………………………………. |
6 |
1.1.1. |
Десятичная позиционная система счисления …………………….………. |
7 |
1.1.2. |
Двоичная позиционная система счисления ……………………..………… |
7 |
1.1.3. |
Восьмеричная позиционная система счисления ………………………….. |
9 |
1.1.4. |
Шестнадцатеричная позиционная система счисления …………………… |
11 |
1.2. |
Перевод чисел из одной позиционной системы счисления в другую…… |
14 |
1.2.1. |
Перевод целых чисел ……………………………………………………….. |
14 |
1.2.2. |
Перевод правильных дробей……………………………………………….. |
17 |
1.2.3. |
Перевод неправильных дробей из одной системы счисления в другую… |
19 |
1.2.4. |
Частный случай перевода чисел из одной системы счисления в другую.. |
19 |
1.2.5. |
Перевод чисел из одной системы счисления в другую с использованием промежуточной двоично-десятичной системы ……… |
21 |
1.3. |
Представление чисел с фиксированной запятой (точкой) ……………….. |
25 |
1.4. |
Представление чисел с плавающей запятой (точкой) ……………………. |
26 |
1.5. |
Коды двоичных чисел ……………………………………………………… |
27 |
1.5.1. |
Прямой код ………………………………………………………………….. |
27 |
1.5.2. |
Обратный код ……………………………………………………………….. |
28 |
1.5.3. |
Модифицированный обратный код ……………………………………….. |
29 |
1.5.4. |
Дополнительный код ……………………………………………………….. |
30 |
1.5.5. |
Модифицированный дополнительный код ……………………………….. |
31 |
2. |
Выполнение арифметических операций с двоичными числами …… |
31 |
2.1. |
Сложение (вычитание) двоичных чисел с фиксированной запятой …….. |
31 |
2.1.1. |
Алгебраическое сложение чисел в дополнительном коде ………………. |
31 |
2.1.2. |
Алгебраическое сложение чисел в обратном коде ……………………….. |
32 |
2.1.3. |
Переполнение разрядной сетки при сложении чисел …………………… |
33 |
2.2. |
Сложение (вычитание) двоичных чисел с плавающей запятой …………. |
34 |
2.2.1. |
Метод ускоренного сложения двоичных чисел с запоминанием переносов…………………………………………………. |
38 |
2.3. |
Умножение двоичных чисел с фиксированной запятой …………………. |
40 |
2.4. |
Машинные технологии выполнения операции умножения двоичных чисел с фиксированной запятой……………………………………………. |
41 |
2.5. |
Умножение двоичных чисел с плавающей запятой ……………………… |
45 |
2.6. |
Методы ускоренного выполнения операции умножения двоичных чисел ……………………………………………………………... |
47 |
2.6.1. |
Метод пропуска такта суммирования …………………………………….. |
48 |
2.6.2. |
Метод анализа сомножителей ……………………………………………... |
49 |
2.6.3. |
Метод расшифровки и одновременного умножения на два разряда множителя …………………………………………………………………... |
50 |
2.6.4. |
Метод ускоренного умножения Мак-Сорли …………………………….... |
53 |
2.6.5. |
Метод ускоренного умножения Лемана …………………………………... |
55 |
2.6.6. |
Метод умножения с расшифровкой пар разрядов множителя и запоминанием переносов ………………………………………………… |
57 |
2.7. |
Деление двоичных чисел с фиксированной запятой ……………………... |
60 |
2.8. |
Деление двоичных чисел с плавающей запятой ………………………….. |
62 |
3. |
Основы десятичной компьютерной арифметики …………………….. |
66 |
3.1. |
Машинное кодирование десятичных чисел ………………………………. |
66 |
3.2. |
Выполнение арифметических операций с десятичными числами ……….…………………………………………… |
69 |
3.2.1. |
Сложение десятичных чисел в ЭВМ ………………………………………. |
69 |
3.2.2. |
Умножение десятичных чисел в ЭВМ …………………………………….. |
71 |
3.2.3. |
Ускорение умножения в D-кодах ………………………………………….. |
73 |
3.2.4. |
Деление десятичных чисел в ЭВМ ………………………………………... |
75 |
4. |
Алгоритмические модели выполнения арифметических операций... |
79 |
4.1. |
Проектирование универсального алгоритма перевода чисел в разные системы счисления ………………………………………………. |
79 |
4.2. |
Моделирование алгоритма сложения двоичных чисел ………………….. |
81 |
4.3. |
Проектирование алгоритма умножения чисел ……………………………. |
84 |
4.4. |
Разработка алгоритма ускоренного умножения с обработкой за один такт трех разрядов множителя ……………………………………. |
87 |
4.5. |
Проектирование алгоритма деления чисел ……………………………….. |
91 |
4.6. |
Разработка алгоритма ускоренного выполнения операции деления с анализом за один такт двух разрядов делителя ………………………… |
94 |
4.7. |
Разработка алгоритма вычисления квадратного корня …………………... |
95 |
5. |
Математическая логика и синтез комбинационных схем …………… |
100 |
5.1. |
Соответствия и предикаты …………………………………………………. |
100 |
5.1.1. |
Соответствия ………………………………………………………………... |
100 |
5.1.2. |
Логические функции ……………………………………………………….. |
104 |
5.1.3. |
Признаки …………………………………………………………………….. |
105 |
5.1.4. |
Бинарные отношения………………………………………………………... |
107 |
5.2. |
Булевы функции …………………………………………………………….. |
127 |
5.2.1. |
Логические операции соединения………………………………………….. |
128 |
5.2.2. |
Булевы формулы…………………………………………………………….. |
130 |
5.2.3. |
Совершенные дизъюнктивные нормальные формы ……………………… |
131 |
5.2.4. |
Булева алгебра ………………………………………………………………. |
134 |
5.2.5. |
Конъюнктивные нормальные формы …………………………………… |
137 |
5.2.6. |
Классы булевых функций. Понятие базиса………………………………... |
138 |
5.2.7. |
Минимизация булевых функций…………………………………………… |
140 |
5.3. |
Методика синтеза комбинационных схем на логических элементах…..... |
155 |
5.3.1. |
Логические элементы……………………………………………………….. |
155 |
5.3.2. |
Общий алгоритм построения комбинационных схем…………………….. |
157 |
5.3.3. |
Синтез КС в классическом базисе………………………………………….. |
158 |
5.3.4. |
Синтез КС в базисах «И-НЕ», «ИЛИ-НЕ»………………………………… |
160 |
5.3.5. |
Реализация КС в базисе Жегалкина………………………………………... |
162 |
5.3.6. |
Синтез составных КС……………………………………………………….. |
163 |
|
Заключение…………………………………………………………………. |
168 |
|
Библиографический список……………………………………………… |
169 |