Читать онлайн «Арифметические и логические основы вычислительной техники: учеб. пособие для студ. спец. «Вычислительные машины, системы и сети» всех форм обуч.»

Министерство образования Республики Беларусь Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники» Кафедра электронных вычислительных машин Р УИ Ю. А. Луцик, И. В. Лукьянова БГ АРИФМЕТИЧЕСКИЕ И ЛОГИЧЕСКИЕ ОСНОВЫ а ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ ек т УЧЕБНОЕ ПОСОБИЕ для студентов специальности ио ”Вычислительные машины, системы и сети” всех форм обучения бл Би Минск 2004  УДК 681. 322 (075. 8) ББК 32. 97 я 73 Л 86 Р е ц е н з е н т: заведующий кафедрой математики и информатики ЕГУ, кандидат технических наук В. И. Романов Р Луцик Ю. А. Л 86 Арифметические и логические основы вычислительной техники: УИ Учеб. пособие для студ. спец. «Вычислительные машины, системы и сети» всех форм обуч. / Ю. А. Луцик, И. В. Лукьянова. − Мн. : БГУИР, 2004. − 121 с. : ил. ISBN 985-444-595-Х БГ Учебное пособие посвящено описанию способов представления числовой информации в ЭВМ, методов выполнения арифметических и логических операций в вычислительных машинах. Рассмотрены вопросы, связанные со способами кон- троля правильности функционирования вычислительного устройства и методами а оптимизации устройств, выполняющих арифметические операции. Пособие может быть использовано студентами всех форм обучения, магист- ек рантами и аспирантами специальности 40 02 01 ”Вычислительные машины, сис- темы и сети”. УДК 681. 322 (075. 8) т ББК 32. 97 я 73 ио бл Би © Луцик Ю. А. , Лукьянова И. В. , 2004 ISBN 985-444-595-Х © БГУИР, 2004  Содержание Введение 5 Арифметические основы вычислительной техники 5 Системы счисления ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 5 Двоичная система счисления ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 6 Восьмеричная система счисления ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 7 Шестнадцатеричная система счисления ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 8 Критерии выбора системы счисления... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 8 Перевод чисел из одной системы счисления в другую ... ... ... ... ... ... ... ... ... ... ... ... . . 11 Перевод целых чисел... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 11 Р Перевод правильных дробей ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 12 Перевод чисел из одной системы счисления в другую, основание которой УИ кратно степени 2 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 13 Кодирование чисел... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 14 Переполнение разрядной сетки ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 16 Модифицированные коды ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 17 БГ Машинные формы представления чисел ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 18 Погрешность выполнения арифметических операций... ... ... ... ... ... ... ... ... ... ... ... ... 19 Округление... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 20 Нормализация чисел... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 21 а Последовательное и параллельное сложение чисел ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 21 ек Сложение чисел с плавающей запятой ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 22 Машинные методы умножения чисел в прямых кодах... ... ... ... ... ... ... ... ... ... ... ... . . 24 Ускорение операции умножения ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 27 т Умножение с хранением переносов ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 27 Умножение на два разряда множителя одновременно... ... ... ... ... ... ... ... ... ... ... ... 28 ио Умножение на четыре разряда одновременно... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 30 Умножение в дополнительных кодах ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 31 Умножение на два разряда множителя в дополнительных кодах... ... ... ... ... ... ... 36 Матричные методы умножения ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 38 бл Машинные методы деления ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 39 Деление чисел в прямых кодах ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 40 Деление чисел в дополнительных кодах... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 42 Би Методы ускорения деления... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 43 Двоично-десятичные коды ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 43 Суммирование чисел с одинаковыми знаками в BCD-коде ... ... ... ... ... ... ... ... ... 45 Суммирование чисел с разными знаками в BCD-коде ... ... ... ... ... ... ... ... ... ... ... ... 46 BCD-коды с избытком 3 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 48 BCD-код с избытком 6 для одного из слагаемых... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 49 Система счисления в остаточных классах (СОК) ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 50 Представление отрицательных чисел в СОК... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 53 Контроль работы цифрового автомата... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 54  Некоторые понятия теории кодирования... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 55 Обнаружение и исправление одиночных ошибок путем использования дополнительных разрядов ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 56 Коды Хемминга ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 57 Логические основы вычислительной техники 58 Двоичные переменные и булевы функции ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 58 Способы задания булевых функций... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 59 Основные понятия алгебры логики ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 61 Основные законы алгебры логики... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 64 Формы представления функций алгебры логики ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 65 Системы функций алгебры логики... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 67 Р Минимизация ФАЛ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 71 Метод Квайна... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 73 УИ Метод Блейка - Порецкого ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 75 Метод минимизирующих карт Карно (Вейча) ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 76 Минимизация конъюнктивных нормальных форм... ... ... ... ... ... ... ... ... ... ... ... ... ... 78 Минимизация не полностью определенных ФАЛ ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 79 БГ Кубическое задание функций алгебры логики... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 80 Метод Квайна −Мак-Класки ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 83 Алгоритм извлечения (Рота) ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 85 Минимизация ФАЛ методом преобразования логических выражений ... ... . . 94 а Применение правил и законов алгебры логики к синтезу некоторых цифровых ек устройств ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 94 Синтез одноразрядного полного комбинационного сумматора... ... ... ... ... ... ... 94 Синтез одноразрядного комбинационного полусумматора ... ... ... ... ... ... ... ... ... 95 т Синтез одноразрядного полного комбинационного сумматора на двух полусумматорах ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 96 ио Синтез одноразрядного комбинационного вычитателя ... ... ... ... ... ... ... ... ... ... ... . 97 Объединенная схема одноразрядного комбинационного сумматора- вычитателя... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 97 Триггер со счетным входом как полный одноразрядный сумматор... ... ... ... . . 98 бл Введение в теорию конечных автоматов 99 Основные понятия теории автоматов... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 99 Способы задания автоматов ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 101 Би Структурный автомат ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 103 Память автомата ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 103 Канонический метод структурного синтеза автоматов... ... ... ... ... ... ... ... ... ... ... ... 106 Принцип микропрограммного управления ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 110 Граф-схема алгоритма... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 111 Пример синтеза МПА по ГСА ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 112 Синтез МПА Мили по ГСА... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 112 Синхронизация автоматов... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 117 Литература 120  Введение Основная цель настоящего учебного пособия - помочь студенту, присту- пившему к изучению арифметики вычислительных машин, приобрести теоре- тические знания и практические навыки выполнения основных арифметических операций.