eng
Содержание
СОДЕРЖАНИЕ
ПРЕДИСЛОВИЕ ...................................................................................11
ГЛАВА 1.
ВВЕДЕНИЕ ...........................................................................................14
ГЛАВА 2.
КОДИРОВАНИЕ И СИСТЕМЫ СЧИСЛЕНИЯ ....................................17
2.1.
Коды ................................................................................................. 17
2.2.
Двоичный код .................................................................................. 18
2.3.
Арифметические операции с фиксированной
запятой в двоичной системе ............................................................ 20
2.3.1.
Целочисленное сложение в двоичной системе ......................................... 20
2.3.2.
Сложение чисел с фиксированной запятой .............................................. 21
2.3.3.
Представление с помощью обратного кода ............................................... 21
2.3.4.
Представление с помощью двойного дополнения
(точное дополнение, two’s complement) ..................................................... 22
2.3.5.
Вычитание при представлении с помощью
точного дополнения ................................................................................... 23
2.3.6.
Переполнение числового диапазона ......................................................... 24
2.3.7.
Умножение .................................................................................................. 25
2.3.8.
Деление ....................................................................................................... 26
2.4.
Представление вещественных чисел с плавающей запятой .......... 26
2.4.1.
Введение: представление с плавающей запятой
в десятичной системе счисления ............................................................... 26
2.4.2.
Представление с плавающей запятой в двоичной
системе счисления ...................................................................................... 27
2.4.3.
Особые представления чисел ..................................................................... 29
2.5.
Шестнадцатеричный код ................................................................. 29
2.6.
Восьмеричный код ........................................................................... 30
2.7.
Код Грея ............................................................................................ 31
2.8.
Двоично-десятичный код ................................................................ 31
2.9.
Алфавитно-цифровые коды ............................................................ 32
2.10.
Упражнения ..................................................................................... 33
ГЛАВА 3.
ПЕРЕКЛЮЧАТЕЛЬНАЯ АЛГЕБРА .......................................................35
3.1.
Переключательная переменная и переключательная функция ..... 35
3.2.
Двухразрядные переключательные функции ............................37
3.3.
Вычислительные правила ................................................................ 40
3.4.
Упрощенное обозначение ............................................................... 41
3.5.
Каноническая дизъюнктивная нормальная форма (KDNF) ......... 41
3.6.
Каноническая конъюнктивная нормальная форма (KKNF) ......... 43
3.7.
Представление функций с помощью KKNF и KDNF ................... 44
3.8.
Минимизация с помощью переключательной алгебры ................. 46
3.9.
Символическое обозначение логических элементов ..................... 47
3.9.1.
Основы структуры символов ...................................................................... 47
3.9.2.
Индексация зависимости ........................................................................... 48
3.9.3.
Зависимость вида И (G) ............................................................................. 49
3.9.4.
Зависимость по типу ИЛИ (V) ................................................................... 50
3.9.5.
Зависимость по типу EXOR (N) ................................................................. 50
3.9.6.
Образующая соединение зависимость (Z)................................................. 51
3.9.7.
Зависимость с передачей (X) ...................................................................... 51
3.10.
Упражнения ..................................................................................... 52
ГЛАВА 4.
ПРИНЦИПЫ РАБОТЫ ЛОГИЧЕСКИХ ВЕНТИЛЕЙ ...........................54
4.1.
Положительная и отрицательная логика ........................................ 55
4.2.
Определение времени переключения ............................................. 56
4.3.
Передаточная характеристика, запас по помехоустойчивости ...... 57
4.4.
Вентили ............................................................................................ 60
4.4.1.
Вентили с открытым коллектором (open collector) ................................... 61
4.4.2.
Вентиль с тремя состояниями .................................................................... 62
4.5.
Упражнения ..................................................................................... 63
ГЛАВА 5.
СХЕМОТЕХНИКА .................................................................................65
5.1.
КМОП .............................................................................................. 65
5.1.1.
Нагрузочная способность ........................................................................... 67
5.1.2.
Основные схемы NAND и NOR ................................................................ 68
5.1.3.
Передаточный вентиль ............................................................................... 69
5.1.4.
Элемент с тремя состояниями ................................................................... 70
5.1.5.
Специфические свойства КМОП .............................................................. 71
5.2.
ТТЛ ................................................................................................... 72
5.2.1.
Нагрузка выходов ....................................................................................... 74
5.3.
Эмиттерно-связанная логика .......................................................... 76
5.4.
Интегральная инжекционная логика (I2L) .................................... 77
5.5.
Рассеиваемая мощность и характеристики переключения
транзисторных переключателей ...................................................... 78
5.6.
Упражнения ..................................................................................... 80
ГЛАВА 6.
ЛОГИЧЕСКИЕ СХЕМЫ ........................................................................82
6.1.
Минимизация с помощью диаграмм Карно – Вейча .................... 82
6.1.1.
Минимизация KDNF ................................................................................. 82
6.1.2.
Минимизация нормальной KKNF ............................................................ 86
6.1.3.
Диаграммы Карно – Вейча для 2, 3, 4, 5, 6 входных переменных ............ 87
6.1.4.
Неполностью заданные функции .............................................................. 88
6.2.
Способ Квина – Мак-Класки ......................................................... 89
6.3.
Другие направления оптимизации .................................................. 93
6.3.1.
Преобразование логической схемы И/ИЛИ в схему НЕ-И ..................... 94
6.3.2.
Преобразование логической схемы ИЛИ/И в логическую
схему НЕ-ИЛИ ........................................................................................... 95
6.4.
Воздействие времени задержки на логические схемы ................... 95
6.4.1.
Отрицательное воздействие на структуру .................................................. 95
6.4.2.
Отрицательное воздействие на функционирование ................................. 97
6.4.3.
Классификация отрицательных воздействий ........................................... 98
6.5.
Упражнения ..................................................................................... 98
ГЛАВА 7.
АСИНХРОННЫЕ СХЕМЫ ПЕРЕКЛЮЧЕНИЯ .................................. 101
7.1.
Принципиальные особенности структуры триггеров .................. 102
7.2.
Анализ асинхронных триггеров .................................................... 102
7.3.
Систематический анализ ............................................................... 104
7.4.
Анализ с учетом задержки вентилей ............................................. 106
7.5.
Элементы ЗУ .................................................................................. 108
7.5.1.
RS-триггер ..................................................................................................109
7.5.2.
RS-триггер с тактовым входом ..................................................................110
7.5.3.
D-триггер ...................................................................................................112
7.5.4.
D-триггер с управлением по переднему фронту импульса ......................115
7.5.5.
Управление по двум фронтам ....................................................................117
7.5.6.
JK-триггер ..................................................................................................118
7.5.7.
Т-триггер ....................................................................................................120
7.5.8.
Пример .......................................................................................................120
7.5.9.
Обобщенные сведения о триггерах ...........................................................121
7.6.
Упражнения ................................................................................... 123
ГЛАВА 8.
СИНХРОННЫЕ ДРАЙВЕРЫ .............................................................. 126
8.1.
Пример 1: «Двоичный счетчик» .................................................... 127
8.2.
Переключатель Мура ..................................................................... 129
8.3.
Схема Мили ................................................................................... 131
8.3.1.
Пример 2: Схема Мили «Управление машиной» .....................................132
8.3.2.
Реализация управления машиной в виде
распределительного устройства Мура ......................................................135
8.4.
Кодирование состояний ................................................................ 136
8.4.1.
Двоичное кодирование ..............................................................................137
8.4.2.
Кодирование по коду Грея .........................................................................137
8.4.3.
Кодирование, ориентированное на вывод ...............................................137
8.4.4.
«Горячее» кодирование ..............................................................................141
8.5.
Выбор триггеров ............................................................................ 142
8.6.
Временные характеристики схем переключения ......................... 144
8.7.
Упражнения ................................................................................... 147
ГЛАВА 9.
МУЛЬТИПЛЕКСОРЫ И ПРЕОБРАЗОВАТЕЛИ КОДА .......................150
9.1.
Мультиплексор .............................................................................. 150
9.1.1.
Реализация функций мультиплексора ......................................................151
9.2.
Преобразователь кода .................................................................... 154
9.2.1.
Преобразователь двоично-десятичного кода
в десятичный код 7442 ...............................................................................155
9.2.2.
Демультиплексор .......................................................................................156
9.2.3.
Генерирование наборов функций .............................................................158
9.3.
Аналоговые мультиплексоры и демультиплексоры ..................... 159
9.4.
Упражнения ................................................................................... 160
ГЛАВА 10.
ЦИФРОВЫЕ СЧЕТЧИКИ .................................................................. 163
10.1.
Асинхронный счетчик ................................................................... 163
10.1.1.
Двоичный счетчик по модулю 8 ................................................................163
10.1.2.
Счетчик по модулю 6 .................................................................................164
10.1.3.
Асинхронный обратный счетчик ..............................................................165
10.1.4.
Временные характеристики асинхронных счетчиков ..............................166
10.2.
Синхронные счетчики ................................................................... 167
10.2.1.
4-битовый двоичный счетчик ...................................................................168
10.2.2.
Счетчик по модулю 6 с использованием кода Грея ..................................170
10.2.3.
Синхронный 4-битовый реверсивный двоичный счетчик 74191 ............172
10.3.
Упражнения ................................................................................... 173
ГЛАВА 11.
РЕГИСТРЫ СДВИГА ...........................................................................175
11.1.
Временные характеристики регистров сдвига .............................. 176
11.1.1.
Регистр сдвига на микросхеме 74194 ........................................................178
11.2.
Регистр сдвига с обратной связью ................................................. 179
11.2.1.
Счетчик Мебиуса, счетчик Джонсона ......................................................181
11.2.2.
Псевдослучайные последовательности ....................................................183
11.3.
Упражнения ................................................................................... 185
ГЛАВА 12.
АРИФМЕТИЧЕСКИЕ УСТРОЙСТВА .................................................187
12.1.
Полный сумматор .......................................................................... 187
12.2.
Последовательный сумматор ........................................................ 187
12.3.
Сумматор с последовательным переносом (ripple-carry-adder) ... 188
12.4.
Сумматор с параллельным переносом .......................................... 189
12.4.1.
Каскадирование сумматоров с параллельным переносом .......................192
12.4.2.
Сравнение сумматоров ..............................................................................196
12.5.
Арифметико-логические вычислительные
устройства (ALU, АЛУ) .................................................................. 196
12.5.1.
Примеры операций ....................................................................................199
12.6.
Компараторы ................................................................................. 201
12.6.1.
2-битовый компаратор ..............................................................................201
12.6.2.
Каскадируемые компараторы ...................................................................202
12.7.
Упражнения ................................................................................... 203
ГЛАВА 13.
ЦИФРОВЫЕ ЗУ .................................................................................. 204
13.1.
Принципиальная структурная схема ЗУ ....................................... 205
13.2.
ROM ............................................................................................... 206
13.3.
PROM ............................................................................................. 209
13.4.
EPROM ........................................................................................... 209
13.5.
EEPROM ........................................................................................ 211
13.6.
EAROM ........................................................................................... 211
13.7.
NOVRAM ....................................................................................... 212
13.8.
RAM ................................................................................................ 212
13.8.1.
Статическое RAM ......................................................................................213
13.8.2.
Пример работы RAM .................................................................................213
13.9.
Динамическое RAM (DRAM) ....................................................... 217
13.9.1.
Структура DRAM .......................................................................................217
13.9.2.
Пример DRAM ..........................................................................................218
13.10.
SDRAM (синхронная DRAM) ....................................................... 222
13.11.
DDR-RAM (DRAM с двойной скоростью передачи данных) ..... 223
13.12.
Память ковшовой цепи ................................................................. 223
13.12.1.
Примеры FIFO ...........................................................................................224
13.13.
Каскадирование ЗУ ....................................................................... 226
13.14.
Увеличение длины слов ................................................................. 226
13.15.
Увеличение емкости ЗУ ................................................................. 227
13.15.1.
Полное декодирование .............................................................................227
13.15.2.
Частичное декодирование ........................................................................229
13.15.3.
Линейное декодирование .........................................................................231
13.16.
Упражнения ................................................................................... 233
ГЛАВА 14.
ПРОГРАММИРУЕМЫЕ ЛОГИЧЕСКИЕ МАТРИЦЫ – ПЛМ ............235
14.1.
Семейства ASIC ............................................................................. 236
14.2.
ПЛИС (PLD) .................................................................................. 240
14.2.1.
Типы PLD – ПЛИС ...................................................................................240
14.3.
ROM, EPROM, EEPROM .............................................................. 242
14.4.
PLA ................................................................................................. 243
14.5.
PAL ................................................................................................. 249
14.6.
GAL ................................................................................................ 251
14.7.
Программирование ПЛИС (PLD) ................................................ 254
14.7.1.
Тестирование ..............................................................................................256
14.8.
Программируемые логические матрицы – ПЛМ (FPGA) ........... 256
14.8.1.
Структура FPGA ........................................................................................258
14.8.2.
Конфигурируемые логические блоки (CLB) ............................................259
14.8.3.
IO-блоки ....................................................................................................260
14.8.4.
Соединительные линии .............................................................................262
14.8.5.
Программирование FPGA .........................................................................263
14.9.
СPLD .............................................................................................. 264
14.9.1.
Структура CPLD ......................................................................................264
14.9.2.
Блоки логических массивов (LAB) ...........................................................266
14.9.3.
IO-контроль ...............................................................................................267
14.9.4.
Размер CPLD .............................................................................................268
14.10.
Вентильные матрицы .................................................................... 268
14.10.1.
Структура канализированных вентильных матриц ..................................269
14.11.
ASIC со стандартными ячейками .................................................. 273
14.12.
ASIC на основе полностью заказного проектирования ............... 274
14.13.
Упражнения ................................................................................... 274
ГЛАВА 15.
ЯЗЫК ПРОЕКТИРОВАНИЯ VHDL ....................................................276
15.1.
Методы проектирования цифровых схем ..................................... 276
15.2.
Структура VHDL ............................................................................ 277
15.3.
Типы ............................................................................................... 278
15.4.
Операторы ...................................................................................... 280
15.5.
Объект ............................................................................................ 282
15.6.
Архитектура .................................................................................... 283
15.7.
Процессы ....................................................................................... 285
15.8.
Структурное проектирование ....................................................... 290
15.9.
Шины ............................................................................................. 292
15.10.
Упражнения ................................................................................... 294
ГЛАВА 16.
МИКРОПРОЦЕССОРЫ ..................................................................... 295
16.1.
Принцип работы интегрированных схем переключения ............ 295
16.2.
Компьютер фон Неймана .............................................................. 296
16.2.1.
Операционный блок ..................................................................................297
16.2.2.
Управляющее устройство ..........................................................................299
16.2.3.
Запоминающее устройство (память) .........................................................300
16.2.4.
Устройства ввода-вывода...........................................................................300
16.2.5.
Режим работы ............................................................................................300
16.3.
Архитектура ATmega16 ................................................................... 301
16.3.1.
Выводы микросхемы ATmega16 ................................................................304
16.3.2.
Регистры центрального процессора ..........................................................305
16.3.3.
Программная память .................................................................................307
16.3.4.
ЗУ для хранения данных ............................................................................308
16.3.5.
Процедуры выполнения команд ...............................................................309
16.4.
Программирование на ассемблере ................................................ 310
16.5.
Типы адресации ............................................................................. 312
16.6.
Набор команд ................................................................................. 317
16.6.1.
Соглашения ...............................................................................................317
16.6.2.
Команда перемещения ..............................................................................317
16.6.3.
Загрузка байтов .........................................................................................317
16.6.4.
Запись байтов .............................................................................................319
16.6.5.
Арифметические операции: Отрицание .................................................320
16.6.6.
Арифметические операции: сложение и вычитание ...............................321
16.6.7.
Арифметические инструкции: установка и очистка битов
в регистре ...................................................................................................324
16.6.8.
Арифметические команды: проверка и сравнение ..................................324
16.6.9.
Арифметические команды: логические операции .................................324
16.6.10.
Команды сдвига и ротации .....................................................................325
16.6.11.
Команды удаления и вставки флагов в SREG .........................................327
16.6.12.
Безусловный адресный переход ................................................................328
16.6.13.
Относительный переход по адресу ............................................................329
16.6.14.
Условно адресуемые команды перехода ...................................................330
16.6.15.
Команды перехода ....................................................................................332
16.6.16.
Команды подпрограмм .............................................................................333
16.7.
Инструкции на языке ассемблера .............................................. 337
16.8.
Обработка прерываний .................................................................. 339
16.9.
Задания .......................................................................................... 343
ПРИЛОЖЕНИЯ
A.1. Обозначения функций ....................................................................... 344
A.2. Набор команд микроконтроллера ATmega16 .................................... 348
A.3. Решения задач .................................................................................... 353
А.4. Литература .......................................................................................... 383
А.5. Предметный указатель ....................................................................... 387
ПРЕДИСЛОВИЕ
Сегодня знание цифровой техники требуется в очень многих областях.
Невозможно понять принципы работы мобильной связи, микрокомпью-
терных технологий, систем цифрового управления и различного телеком-
муникационного оборудования без знания методов цифровой обработки
информации, а широкое применение интегрированных механико-элек-
тронных систем лишь усиливает эту тенденцию. Особое значение цифро-
вые технологии приобрели во встраиваемых системах. Речь идет о цифро-
вых схемах, которые «встраиваются» в те или иные технические решения.
Встраиваемые системы вы можете встретить в самых разных устрой-
ствах — стиральных машинах, автомобилях, холодильниках, развлекатель-
ной электронике, мобильных телефонах и т. д.
В данной книге отлично изложены основы цифровой техники, вклю-
чая устройство и программирование простых микропроцессоров. Поми-
мо прочной теоретической базы, читатель получит знания, позволяющие
понять принципы работы большинства цифровых схем. В это 8-е издание
внесены многочисленные дополнения. В частности, в главе о микропро-
цессорах в качестве примера рассматривается микропроцессор, широко
используемый в современной промышленности. Также добавлен материал
о представлении чисел с плавающей запятой.
Эта книга предназначена, в первую очередь, для студентов колледжей
и университетов, изучающих инженерию и информационные технологии.
Поскольку для понимания книги не требуется никаких специальных зна-
ний, она также подходит для широкого круга заинтересованных читате-
лей. Для работы с главой «Схемотехника» читателю понадобятся базовые
знания в области электроники, однако эта глава не обязательна для пони-
мания других глав книги, и ее можно пропустить. Представление булевой
алгебры и используемые символы в основном соответствуют действую-
щим стандартам DIN1.
Для облегчения самостоятельной работы с книгой каждая глава сопро-
вождается упражнениями, с помощью которых можно проверить понима-
ние материала. Предлагаемые решения можно найти в приложении. Одна
из основных задач данной книги — это подробное изложение основ циф-
ровой техники. В частности, много внимания уделено синтезу коммута-
ционных схем. Рассмотрены примеры широко применяемых стандартных
коммутационных схем, таких как мультиплексоры и преобразователи кода.
Поскольку для понимания работы процессоров важно знание арифмети-
ческих операций, подробно рассматриваются арифметика с фиксирован-
ной запятой и аппаратная реализация арифметико-логических устройств.
Сегодня в распоряжении разработчиков схем находятся совершенные ин-
струменты проектирования, позволяющие разрабатывать сложные циф-
ровые схемы, реализовывать их на основе полупроводников, тестировать и
настраивать работу схемы. Это обусловило бурное развитие интегральных
схем специального назначения (ASIC), которые заказчик может настроить
самостоятельно. Поэтому одна из глав посвящена таким интегральным
схемам. Следующая глава знакомит с VHDL – языком программирования
для описания, синтеза и моделирования интегральных цифровых схем,
который фактически стал стандартом и часто используется при проекти-
ровании схем ASIC. Такой язык описания оборудования (HDL) становит-
ся все более популярным при проектировании схем, поскольку он дает
значительные преимущества по сравнению с традиционными методами
графически ориентированного проектирования, особенно при работе над
сложными проектами. Опираясь на знание коммутационных схем, можно
переходить к изучению синхронных и асинхронных методов коммутации.
В книге представлена методика разработки синхронных и асинхронных
контроллеров. При этом в новой редакции больше внимания уделено син-
хронным контроллерам. Методы асинхронной коммутации сейчас приме-
няются, главным образом, в триггерах, наиболее распространенные типы
которых представлены в книге. Кроме того, рассмотрено проектирование
счетчиков и регистров сдвига и представлены некоторые примеры их про-
мышленной реализации. Отдельная глава посвящена сравнению различ-
ных технологий и свойств модулей памяти, которые существенно влияют
на характеристики современных вычислительных систем. Приведены ти-
повые временные диаграммы, иллюстрирующие принципы работы раз-
личных модулей памяти. Последняя глава представляет простое введение
в микропроцессорную технику. Для знакомства с устройством вычисли-
тельной машины поясняется принцип работы компьютера фон Неймана,
на примере которого описываются процессы выполнения команд. В каче-
стве практического примера в одном из разделов представлен современный микроконтроллер ATmega16 производства компании AVR, описаны
его структура и режимы работы. Подробно рассматривается программи-
рование на ассемблере, знание которого будет полезно при работе с раз-
личными типами процессоров.
Фульда,
март 2018 года,
Клаус Фрике
ГЛАВА 1
ВВЕДЕНИЕ
В последние годы значение цифровой техники все более и более возрас-
тает. Причина этого заключается в значительных преимуществах цифро-
вой техники при создании очень сложных систем. Это достигается путем
представления сигнала двумя значениями, которые могут обрабатываться
логическими вентилями с сильно нелинейными передаточными характе-
ристиками без сбоев, накопления и дальнейшего распространения иска-
жений сигнала. Благодаря такому представлению сигналов удалось соз-
дать полупроводниковую технологию, позволяющую реализовать до 107
элементов на одном кристалле.
Поскольку целью систем цифровой техники является обработка сиг-
налов, то следует несколько подробнее рассмотреть понятие «сигнал».
Сигналы служат для переноса информации. Они описываются такими
физическими величинами, как напряжение, ток, давление, сила и т. д.
Амплитуды таких величин зависят от времени. Передаваемая информа-
ция заключается в изменяющихся амплитудных значениях. Пусть, напри-
мер, измеряется зависящий от времени уровень жидкости F в резервуаре.
На рис. 1.1a показана зависимость уровня жидкости от времени. Если дат-
чик выдает электрический сигнал, напряжение которого пропорциональ-
но величине заполнения, получаем временную зависимость напряжения
Us, показанную на рис. 1.1 b. Этот сигнал имеет непрерывную величину,
то есть в измеряемом диапазоне могут появиться все значения амплитуды.
Системы, которые могут обрабатывать непрерывные по величине сиг-
налы, называются аналоговыми системами.
Дискретные по величине сигналы, которые также называют цифро-
выми сигналами, могут, в отличие от этого, принимать только определен-
ные дискретные значения в фиксированные моменты времени. Примером
цифрового сигнала является сигнал, который с помощью двух различных
уровней напряжения показывает, закрыта или открыта дверь. Подобные
сигналы могут непосредственно обрабатываться цифровыми системами.
В том случае, если сигналы с непрерывной величиной должны переда-
ваться цифровыми системами, эти сигналы должны быть предварительно
квантизированы. В соответствии с данным процессом, с определенными
временными точками (точками считывания) соотнесена амплитуда сигнала дискретной амплитудной ступени. Вышеупомянутый пример про-
демонстрирован на рис. 1.1с, показывающем датчик уровня заполнения.
При этом получаем напряжение с дискретными величинами Uq. При кван-
тизировании необходимо принимать во внимание ошибку округления.
При цифровой передаче сигнал вначале должен быть переведен в циф-
ровую форму. В этом случае амплитуда будет предъявляться с помощью
последовательности цифр. Каждая цифра представляет собой сигнал
с дискретным значением. На рис. 1.1d приведен пример кодирования с
помощью нескольких следующих друг за другом цифр. Амплитудная сту-
пень 0 представлена двумя цифрами 00. Амплитуды 1, 2 и 3 становятся
сочетаниями 01, 10, 11. Следует различать также дискретные во времени
сигналы и непрерывные во времени сигналы. Дискретные во времени сиг-
налы могут изменять свою амплитуду только в определенные моменты
времени, в то время как непрерывные во времени сигналы могут изменять
свою амплитуду в произвольные моменты времени. Цифровые системы
могут быть дискретными во времени, в этом случае их называют синхрон-
ными. Синхронизация осуществляется с помощью тактового сигнала.
Благодаря ограничению в использовании конечного числа амплитуд-
ных ступеней, цифровая система обладает высокой помехозащищенно-
стью. Подвергнувшиеся воздействию помех цифровые сигналы могут быть
однозначно приведены к первоначальным дискретным амплитудным зна-
чениям. Но чтобы не возникла ошибка, помеха не должна превышать по-
ловину расстояния между двумя амплитудными ступенями.
Цифровые системы имеют ряд преимуществ перед аналоговыми систе-
мами:
– При использовании цифровых сигналов не происходит накопле-
ния их искажений — появляется возможность реализации систем
любой степени сложности, например микропроцессоров. Это свой-
ство цифровых систем определяет их превосходство и при передаче
на большие расстояния.
– Цифровые системы сравнительно легко проектировать, посколь-
ку способ их описания, представляющий собой булеву алгебру, —
аппарат очень удобный для автоматизации. Сегодня разработка
сложных цифровых систем автоматизирована посредством приме-
нения высокопроизводительных алгоритмов.
– Цифровые системы можно относительно просто тестировать.
Недостаток цифровых систем:
– Цифровые системы являются более медленными системами, чем
аналоговые. Поэтому в области высоких частот доминирует анало-
говая техника.
ГЛАВА 2
КОДИРОВАНИЕ
И СИСТЕМЫ
СЧИСЛЕНИЯ
2.1. Коды
В цифровой технике коды используются для оптимального представления
сигнала в случае его применения. Код отображает символы одного мно-
жества через символы второго множества. При этом должна существовать
возможность декодирования, при которой вероятно получить исходные
символы из кодированных.
Известным примером кода является код Морзе. Определение кода
производится с помощью таблицы соответствия. Для кода Морзе подоб-
ное соответствие отображено в табл. 2.1. Этот код является обратимым, так
как из буквы можно получить символ Морзе, а из него можно вновь обра-
зовать букву. Но это справедливо только для текста, написанного строчны-
ми буквами, поскольку код Морзе не делает различия между прописными
и строчными буквами. Строго говоря, из кода Морзе нельзя восстановить
путем декодирования текст, записанный с помощью строчных и пропис-
ных букв.
Для каждого применения имеется более или менее подходящий код.
Так, для проведения операций над числами в компьютере рационально
применять иной код, чем для передачи чисел по линии связи. В данной
главе исследуются различия между отдельными кодами и даны указания
по их специфическому применению.
Комбинацию нескольких символов кода называют словом (word). В по-
следующем мы ограничимся технически важным случаем, в котором все
слова одного кода имеют одинаковую длину n. В коде Морзе это не про-
исходит. Если в код входит множество символов N, то Nn различных слов
могут иметь длину n. Когда используются все Nn возможных слов одного
кода, то в этом случае говорят о минимальном коде. При использовании
менее чем Nn слов его называют избыточным кодом. Ниже можно найти
описание наиболее употребительных кодов, их полное описание можно
получить из [7–9].
2.2. Двоичный код
Будучи универсальным, двоичный код является важнейшим в цифровых
системах. В соответствии с определением, при котором применяются толь-
ко символы 1 и 0, становится возможной обработка сигналов с помощью
схемных элементов, работающих как переключатели. Также двоичный код
позволяет использование арифметики, аналогичной арифметике десятич-
ных систем. При этом двоичную систему счисления можно рассматривать
как кодирование десятичной системы, где двоичное число состоит из сло-
ва, образованного символом ci {0, 1}. Символы ci одного слова называют
в цифровой технике битами. Слово z2 в двоичном представлении форми-
руется путем последовательного присоединения отдельных битов, как это
показано ниже:
z2 = cn–1cn–2 · · · c1 c0 · · · c–m + 1 c–m. (2.1)
Двоичное число имеет n разрядов перед запятой и m разрядов после за-
пятой. Отдельным битам присвоены, в соответствии с их позицией i в сло-
ве, весовые коэффициенты 2i. На основе этого можно рассчитать эквива-
лентное десятичное число z10:
см. уравнение в книге (2.2)
Рассмотрим в качестве примера двоичное число 10110,0012, которое
в качестве такового отмечено символом 2. Оно интерпретируется как:
g(z2) = 1 · 24 + 0 · 23 + 1 · 22 + 1 · 21 + 0 · 20 + 0 · 2–1 + 1 · 2–2 + 1 · 2–3 =
= z10 = 22,37510
Двоичный (или дуальный) код обозначается как взвешенный, по-
скольку стоящие дальше влево биты обладают более высокими весовыми
коэффициентами. Уравнение (2.2) можно рассматривать как правило, в
соответствии с которым производится преобразование двоичных чисел в
десятичные числа.
Преобразование же десятичных чисел в двоичные числа является более
сложным. Его можно описать различными алгоритмами для целочислен-
ной и дробной частей. В приведенном выше примере с числом 22,37510
алгоритм должен быть представлен следующим образом:
Вначале формируется целочисленная часть двоичного числа.
Для чего целочисленная часть десятичного числа последовательно
делится на 2 и записывается остаток, пока не будет получен 0.
22 : 2 = 1
11 : 2 = 5
5 : 2 = 2
2 : 2 = 1
1 : 2 = 0
остаток 0
остаток 1
остаток 1
остаток 0
остаток 1
цело-
числ. часть
двоичного
числа
Соответствующее числу 2210 двоичное число представляет собой 101102.
Второй шаг заключается в преобразовании дробной части деся-
тичного числа в дробную часть двоичного числа. Вначале дробная
часть десятичного числа умножается на 2. Целочисленная часть от-
деляется, она образует разряды двоичного числа с наименьшими
значениями.
Процесс повторяется, как это показано ниже.
0,375 · 2 = 0,75
0,75 · 2 = 0,5
0,5 · 2 = 0
+0
+1
+1
дробная часть
двоичного
числа
В данном примере мы видим, что остаток равен 0. Но не обязатель-
но так всегда бывает. В нормальном случае дробная часть эквивалентного
двоичного числа имеет бесконечно большое количество разрядов. В дан-
ном случае необходимо удовольствоваться определенным числом разря-
дов после запятой и этим ограничить точность.
В нашем случае 0, 37510 точно соответствует 0, 0112. На основе целочис-
ленной и дробной частей получаем искомое двоичное число 10110,0112.
2.3. Арифметические операции с фиксированной
запятой в двоичной системе
В данной главе описываются арифметические операции с числами с фик-
сированной запятой. Арифметические операции с фиксированной запя-
той означают, что в них запятая всегда стоит на фиксированном месте.
При этом место, на котором стоит запятая, ориентируется на позицию
в запоминающем устройстве (ЗУ), на которой находится число. В этом
случае нет необходимости реализовать запятую в аппаратуре компьютера.
Она существует только в голове программиста. Мы ограничиваемся посто-
янной длиной слова n, как это имеет место в компьютерах. На основе этого
можно обсудить проблему переполнения допустимой области.
2.3.1. Целочисленное сложение в двоичной системе
Целочисленное сложение двух чисел A и B производится в двоичной си-
стеме точно так же, как и в десятичной системе — по разрядам. Как и там,
в каждом разряде должны быть просуммированы обе двоичных цифры an и
bn и перенос из предыдущего разряда Cn–1.
При сложении возникают (табл. 2.2) новая сумма Sn и новый перенос Cn.
В этой таблице дискретной линией разделены входные и выходные ве-
личины. Например:
0 1 1 1 1 1 1 0
+ 0 0 1 1 0 1 0 1
перенос 1 1 1 1 1 0 0
= 1 0 1 1 0 0 1 1
В приведённом выше примере, чтобы не было переполнения, необ-
ходимо суммировать два числа длиной 8 бит, итог которых также должен
иметь длину 8 бит.
2.3.2. Сложение чисел с фиксированной запятой
В случае когда суммируются два числа с фиксированной запятой, важно,
как и в обычной процедуре, чтобы обе запятые стояли друг над другом.
Так, при сложении двух чисел длиной в 8 бит запятая у обоих чисел должна
стоять, например, на третьем месте.
Например:
+ 0 1 1 0 0, 0 1 0
0 0 1 1 0, 1 1 1
перенос 1 1 0 0 1 1 0
= 1 0 0 1 1, 0 0 1
2.3.3. Представление с помощью обратного кода
Для того, чтобы иметь малые затраты на аппаратурную часть (hardware)
компьютера, были предприняты усилия по сведению к одному
алгоритму вычитания и сложения. Этого можно добиться, если при-
менять двоичные цифры в их дополняющей форме. Различают единичное
дополнение (обратный код, поразрядное дополнение) и двойное дополне-
ние (точное дополнение).
Поразрядное дополнение формируется путем замены всех нулей на
единицы и обратно. Следовательно, поразрядным дополнением (one’s
complement) 0001 является 1110. Ниже поразрядное дополне ние двоично-
го числа A обозначено ¬A. Очевидно, что при представлении n-битового
слова имеем:
¬A + A = 2n – 1. (2.3)
Например, при представлении 8-битового слова имеем:
10110011 + 01001100 = 11111111 = 28 – 1.
Можно так преобразовать уравнение (2.3), чтобы получить формулу
для расчета поразрядного дополнения:
¬A = 2n – 1 – A. (2.4)
2.3.4. Представление с помощью двойного дополнения
(точное дополнение, two’s complement)
Точное дополнение AK2 образуется из поразрядного дополнения ¬A путем
прибавления 1:
AK2 = ¬A + 1. (2.5)
Следовательно, с учетом (2.4) будет справедливо:
AK2 = 2n – A. (2.6)
Мы видим, что в данном представлении содержится «–A», благодаря
чему оно удобно для проведения вычитания. Учтем также, что 2n в двоич-
ном представлении имеет n + 1 разрядов. Ниже пример точного дополне-
ния для 10101100:
AK2 = ¬A + 1 = 01010011 + 1 = 01010100
Представление 4-битовых двоичных слов в круговой форме, приведен-
ное на рис. 2.1, позволяет показать числовой диапазон. Соответствующее
данным значениям наибольшее представляемое положительное число рав-
но 710, соответствующее данным значениям наибольшее отрицательное чис-
ло равно –810. Следовательно, числовой диапазон построен несимметрично,
поскольку отрицательное число занимает больше места, чем положитель-
ное. Наибольшее и наименьшее представляемые числа можно выразить как:
zmax = 2n–1 – 1, (2.7)
zmin = –2n–1. (2.8)
На рис. 2.1 можно видеть, что малые числа, сформированные на осно-
ве точного дополнения, содержат много ведущих единиц, когда они от-
рицательны, и содержат много ведущих нулей, когда они положительны.
В числах, представленных в формате дополнения до двух, на крайней по-
зиции слева стоит нуль, когда они отрицательны, и единица, когда они
положительны. Их собственным точным дополнением является число 10002 (–810). Важно установить, что при представлении на основе точного
дополнения имеем только один 0. Это облегчает запрос, равен ли резуль-
тат 0. Напротив, при представлении на основе поразрядного дополнения
имеют место двоичное число 00002, соответствующее +010, и двоичное чис-
ло 11112, соответствующее –010.
2.3.5. Вычитание при представлении с помощью
точного дополнения
Пусть будут вычтены одно из другого два положительных двоичных чис-
ла A и B. При условии применения точного дополнения в соответствии
с уравнением (2.6) вычитание можно провести следующим образом:
A – B = A – B + BK2 – BK2 = A – B + BK2 – (2n – B). (2.9)
Раскрытие скобок в правой части уравнения дает:
A – B = A + BK2 – 2n. (2.10)
Что означает вычитание 2n? Поясним это на примере операции вычи-
тания 7 – 3 = 4 в 4-битовой двоичной системе. Сумма двоичного эквива-
лента числа 7 и дополнение двоичного эквивалента числа 3 равняется:
0 1 1 1 7 + 10 1 1 0 1 –310
= 1 0 1 0 0
– 1 0 0 0 0
= 0 1 0 0 410
Вычитание числа 100002, проведенное в соответствии с уравнени-
ем (2.10), дает правильный результат 01002. Это может произойти в 4-бито-
вом компьютере просто потому, что высший результат игнорируется. Итак,
при проведении вычитания с помощью точного дополнения нет необходи-
мости учитывать высший перенос c4. Но необходимо соблюдать осторож-
ность в связи с переполнением числового диапазона. Исследуем это ниже.
2.3.6. Переполнение числового диапазона
Исходя из вышесказанного, возникает необходимость рассмотрения про-
блемы переполнения числового диапазона (overflow) в связи с представле-
нием на основе точного дополнения. Переполнение числового диапазона
может происходить только в двух случаях. А именно, когда суммируются
два положительных числа либо суммируются два отрицательных числа.
В связи с этим рассмотрим несколько примеров, относящихся к 4-бито-
вому представлению.
Пример переполнения числового диапазона при сложении двух по-
ложительных чисел:
0 1 0 1 5 + 10 0 1 0 1 510
= (0) 1 0 1 0 –610
Очевидно, что результат является неправильным. Ошибка возника-
ет за счет переноса 3-го разряда на место 4-го разряда, что приводит
к симуляции отрицательного числа. Этот перенос c3 в представле-
нии, использующем n бит, обычно обозначается как cn–1. Перенос
c4 (в общем случае cn) из разряда 4 в разряд 5 называется Carry (Cy).
В этом примере данный перенос не имеет места.
Пример переполнения численного диапазона при сложении отри-
цательных чисел:
1 0 1 1 –5+ 10 1 0 1 1 –510
= (1) 0 1 1 0 610
В этом примере также появляется неправильный результат. Имеет
место не перенос cn–1 из разряда 3 в разряд 4, а перенос cn из разряда
4 в разряд 5.
Для сравнения проведем сложение двух отрицательных чисел без
переполнения числового диапазона:
1 1 1 1 –1 + 10 1 1 0 1 –310
= (1) 1 1 0 0 –410
Имеются переносы cn и cn–1.
Сведем эти результаты вместе с другими, здесь не показанными случа-
ями в таблицу. На основе результатов, представленных в табл. 2.3, для двух
двоичных чисел A и B, которые лежат в числовом диапазоне, определяе-
мом n-битовым представлением на базе точного дополнения, можно уста-
новить перенос переполнения при сложении.
= cn–1, неправильный результат — когда cn cn–1.
2.3.7. Умножение
Умножение выполняется так же, как и для десятичной системы. Рас-
смотрим пример умножения на основе двоичной системы для чисел
1010 1110 = 11010:
1 0 1 0
1 0 1 1
1 0 1 0
1 0 1 0
1 0 1 0
1 1 0 1 1 1 0
Наибольший из ожидаемых результатов E умножения двух n-битовых
слов представляет собой:
E = (2n – 1) · (2n – 1) = 22n – 2n+1 + 1 22n – 1
Следовательно, результат умножения двух n-битовых чисел имеет дли-
ну 2n бит. Но он меньше, чем максимальное представляемое с помощью 2n
бит двоичное число 22n – 1.
Сказанное выше справедливо для умножения положительных чисел.
При вычислениях с использованием представления на основе точного
дополнения могут быть применены специальные алгоритмы [41], или же
числа на основе точного дополнения перед умножением следует преобра-
зовать обратно в исходные значения, а результат перевести в соответствии
со знаком в желаемое представление.
При умножении чисел с фиксированной запятой вначале числа умно-
жаются без учета запятой. Затем запятая вводится в соответствии с прави-
лом: умножение двух чисел с n и k разрядами после запятой даст произве-
дение с n + k разрядами после запятой.
2.3.8. Деление
Для деления можно использовать тот же самый алгоритм, что и в де-
сятичной системе. Продемонстрируем это на примере уравнения
1010 : 210 = 5D:
1 0 1 0 | 0 0 1 0
– 1 0 1 0 1
– 0 1 0
1 0
0
Соответственно, при делении числа с n разрядами после запятой
на число с k разрядами после запятой частное имеет n – k разря-
дов после запятой. Так, в соответствии с верхним примером имеем
(1,2510 : 0,510 = 2,510): 1,010 : 00,10 = 10,1. Деление чисел с точным дополне-
нием также можно свести к умножению и сложению [41].
2.4. Представление вещественных чисел с плавающей
запятой
2.4.1. Введение: представление с плавающей запятой
в десятичной системе счисления
Большие числа обычно представляются в экспоненциальном виде с пла-
вающей запятой. Примером может служить представление скорости света:
2,99792458 · 108 м/с. В общем виде:
Число m называется мантиссой, а e — показателем степени. Здесь e — це-
лое число, а m — число с фиксированной запятой со знаком. В этом при-
мере мантисса равна 2,99792458, а показатель степени равен 8. Для пред-
ставления чисел в формате с плавающей запятой характерно наличие
основания b. В данном примере основание b = 10. И показатель степени,
и мантисса имеют знак. В компьютерах используется представление в дво-
ичной системе с основанием b = 2.
2.4.2. Представление с плавающей запятой в двоичной
системе счисления
В этой главе описывается представление с плавающей запятой в двоич-
ной системе счисления. В информатике эту форму представления числа
называют «реальной», поскольку ее можно использовать для представле-
ния действительных чисел. Согласно стандарту IEEE-754 в общем случае
представление чисел с плавающей запятой имеет следующий вид:
z = (–1)s · 1, m · 2e = (–1)s · 1, m · 2(c–q). (2.12)
s — знак мантиссы, он представлен одним битом.
1, m — абсолютное значение мантиссы. Оно хранится как двоич-
ное число с фиксированной запятой и перед местом, обозначенным
запятой. Оно всегда равно единице. Число m после запятой назы-
вается дробной частью. m выбирается согласно выбору показателя
степени так, чтобы удовлетворять условию:
2 > | 1, m | 1. (2.13)
Условие верно только для чисел z 0. Следовательно, нельзя пред-
ставить нуль. Форма записи с плавающей запятой, удовлетворяю-
щая условию (2.13), называется нормализованной. Мантисса рас-
полагает в компьютере фиксированным количеством цифровых
позиций nm.
Вместо показателя степени e сохраняется характеристика c = e + q.
Она имеет фиксированное количество цифр nc. При добавлении
остатка показатель степени e сдвигается так, чтобы сохранять толь-
ко положительные числа. Остаток равен
q = 2nc–1 – 1. (2.14)
Таким образом, например, для 8 цифр (nc = 8) получим остаток 127. Это
означает, что могут быть представлены показатели от –127 до 128. Наименьшая характеристика 0 получается, когда наименьший показатель сте-
пени равен –127, и становится равной нулю при добавлении остатка 127.
Наибольшая характеристика, а именно наибольшее число 255, которое
может быть представлено 8 битами, получается из суммы наибольшего по-
казателя 128 и остатка 127.
Согласно стандарту IEEE-745 часто используются две степени точно-
сти — одинарная точность и двойная точность.
Два часто используемых числовых формата согласно IEEE-745 — это
одинарная точность и двойная точность. Согласно табл. 2.4 используются
двоичные цифры 1 + nc + nm. Для чисел в числовом формате одинарной
точности требуется 32 бита, в формате двойной точности — 64 бита.
Пример:
Действительное число –0,17187510 должно быть преобразовано в фор-
мат одинарной точности согласно IEEE-745. Первая цифра — это знак s.
s = 1 означает отрицательную мантиссу, s = 0 — положительную. В данном
случае s = 1.
Сначала вы конвертируете десятичное число в двоичное:
–0,17187510 = –0,0010112
Затем число нормализуется, и тогда оно будет иметь вид 1, m · 2 n:
–0,0010112 = –1,011 · 2–3
2–3 означает, аналогично десятичной системе счисления, сдвиг на 3 пози-
ции. Мантисса сохраняется без 1 перед десятичной запятой и расширяется
до 23 бит с нулями или округляется до 23 разрядов, если необходимо:
m = +1,011 0000 0000 0000 0000 0000
Избыток q добавляется к показателю степени e = –3 (для одинарной
точности q = 127), чтобы получить характеристику c. Он сохраняется как
8-значное двоичное число:
c = e + q = –3 + 127 = 12410 = 011111002
Теперь число, которое нужно сохранить, формируется путем совмеще-
ния s, c и m
s c m
1 01111100011 0000 0000 0000 0000 0000
Итак, двоичное число, которое мы ищем:
1011 1110 0011 0000 0000 0000 0000 00002.
2.4.3. Особые представления чисел
По определению нуль не может быть представлен, так как мантисса
равна 1, m, и следовательно всегда не равна 0. В качестве альтерна-
тивы было определено число с мантиссой 1,00 ... и характеристикой
0. Это наименьшее число, которое можно представить, и оно опре-
делено в качестве нуля. Поскольку разрешены оба знака, получает-
ся два представления нуля.
Числа с мантиссой 1,00. . . и максимально возможной характери-
стикой определены для представления ± бесконечности. При пред-
ставлении бесконечности с одинарной точностью это число 255.
Кроме того, существует представление под названием NaN (Not a
Number — не число). Это число не считается числом с плавающей
запятой и обычно приводит к отмене вычисления.
2.5. Шестнадцатеричный код
На практике наряду с двоичным кодом внедрился шестнадцатеричный код,
поскольку он обеспечивает лучшее обозрение длинных двоичных чисел.
Шестнадцать шестнадцатеричных цифр определены в табл. 2.4. Шестнад-
цатеричные цифры больше девяти представлены буквами A–F. Для преобразования двоичных в шестнадцатеричные числа объединяют по четыре
цифры двоичного числа, которые интерпретируются как шестнадцатерич-
ный разряд. Благодаря этому шестнадцатеричное число занимает только
четверть разрядов, занимаемых двоичным числом одинаковой величины.
Например:
1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0
B E 3 0
Итак, справедливо выражение 10111110001100002 = BE3016.
В качестве обозначения шестнадцатеричного числа используется ин-
декс H и $. Преобразование шестнадцатеричного числа в десятичное чис-
ло и обратно проще всего производить через соответствующее двоичное
число. Также возможно производить преобразование с помощью алгорит-
ма, как при преобразовании двоичного числа в десятичное число. Обрат-
ное преобразование производится аналогично представленному уравне-
нием (2.2).
2.6. Восьмеричный код
Восьмеричный код применяется аналогично шестнадцатеричному, толь-
ко объединяются лишь по 3 разряда двоичного числа. Для восьмеричного
кода применяются цифры десятичного кода от 0 до 7, он обозначается ин-
дексом 0.
Например:
1 1 0 1 0 1 1 0 0 0 1 1
6 5 4 3
Следовательно, справедливо 110101000112 = 65438.
2.7. Код Грея
Часто в цифровой технике требуется для числового кода схема кодирова-
ния, в соответствии с которой при переходе от одного числа к следующему
изменялась бы только одна цифра. Выполнение этого условия необходи-
мо, когда вследствие технических неточностей момент переключения не
может быть точно выдержан. Из-за этого при переключении двух цифр
могут возникнуть неправильные коммутационные операции. В качестве
примера подобной ошибки рассмотрим переключение от 110 к 210 в дво-
ичном коде:
0000 0011
0001
0010
При этом переключении изменяются биты 0 и 1, при одновременном
переключении непосредственно достигается новое число. Если вначале
изменяется бит 0, то появляется число 0000, и только когда изменяется бит
1, получаем правильное число 0010. Если же сначала изменяется бит 1 и
потом изменяется бит 0, то в промежутке возникает число 0011. Коды Грея
позволяют избежать этой очень серьезной ошибки за счет того, что при
переходе от одного кодового слова к следующему изменяется только один
разряд. В табл. 2.7 представлен 4-разрядный код Грея. В дополнение к вы-
шесказанному показанный код имеет свойство, которое заключается в его
цикличности, также как и при переходе от высшего числа (15D) к низшему
числу изменяется только один разряд. Циклические коды Грея могут быть
сконструированы для всех прямых длин периодов.
Таблица 2.7. Пример 4-разрядного кода Грея
Десятичные (числа) Код Грея Десятичные (числа) Код Грея
0 000 4 110
1 001 5 111
2 011 6 101
3 010 7 100
2.8. Двоично-десятичный код
Если мы хотим подвести к десятичным цифрам некоторые отметки, то
для этого подойдет код, в котором отдельным десятичным цифрам приданы двоично-кодированные кодовые слова. Этот код обозначается как
двоично-десятичный код (BCD-код). Подходящая возможность реализа-
ции заключается в том, чтобы каждой десятичной цифре сопоставить ее
запись в двоичной системе счисления, то есть четырехразрядное двоичное
число (см. табл. 2.6). Поскольку отдельные разряды имеют веса 8, 4, 2 и 1,
данный код называют кодом типа 8-4-2-1. Существует также возможность
построить двоично-десятичный код 2, 4, 2, 1 (Aiken-Code). К другим дво-
ичнодесятичным кодам относятся код с избытком три (3-Excess-Code) и
двоично-десятичный код Грея (BCD-Gray-Code) [5].
2.9. Алфавитно-цифровые коды
Существует большое количество кодов, осуществляющих представление
алфавитно-цифровых символов с помощью двоичных цифр.
Известным примером подобных символов является код ASCII
(American Standard Code for Information Interchange), который содержит
также ряд управляющих символов.
2.10. Упражнения
Задача 2.1. Преобразуйте следующие двоичные числа в десятичные числа:
а. 1110,101
б. 10011,1101
Задача 2.2. Преобразуйте следующие десятичные числа в двоичные числа:
а. 33,125
б. 45,33
Задача 2.3. Рассчитайте приведенные ниже примеры с использованием
точных дополнений при длине слова в 6 бит. Укажите, имеет ли место пе-
реполнение числового диапазона.
а. 010101 –001010
б. –010111 –011011
Задача 2.4. Рассчитайте в двоичной системе:
а. 110101 · 010101
б. 1101110 : 110
Задача 2.5. Разработайте циклический код Грея с длиной периода 6.
Задача 2.6. Какое действительное число представлено числом одинарной
точности C23A800016 согласно IEEE-754?
ГЛАВА 3
ПЕРЕКЛЮЧАТЕЛЬНАЯ
АЛГЕБРА
Цифровая техника имеет преимущество перед аналоговой техникой: она
основывается на относительно простой, но при этом мощной теории, на
булевой алгебре, называемой также переключательной алгеброй. В данной
главе представлены теоретические основы цифровой техники. Булева ал-
гебра может быть применена для решения почти всех проблем, возникаю-
щих при разработке цифровых схем с условием выполнения технологиче-
ских предпосылок, которые рассматриваются в главе 4.
3.1. Переключательная переменная
и переключательная функция
В цифровой технике применяют специальные переменные и функции.
Под булевой переменной понимают переменную, которая может прини-
мать только значения 0 и 1. С булевыми переменными могут быть образо-
ваны функции. Функцию
y = fx1, x2, x3, . . . xn при xi, y {0, 1} (3.1)
называют n-разрядной переключательной или двоичной функцией. Об-
ласть значений подобной функции также определяется двоичной систе-
мой счисления с элементами 0 и 1. Функции могут быть определены та-
блицами, в которых величины функций связываются с возможными 2n
комбинациями n входных переменных. Эти таблицы называются табли-
цами истинности.
Очень простая функция, которая связывает входную переменную x
с выходной переменной y, представлена в табл. 3.1. Можно видеть, что
все переключательные функции могут быть определены таблицей, со-
держащей все входные переменные, поскольку учитывать необходимо
только два элемента 0 и 1.
Определенную табл. 3.1 переключательную функцию y = f (x) именуют
«отрицание», «дополнение» или НЕТ (NOT). В последующем она обозна-
чается оператором « ¬ » и читается «y равен не x»:
y = ¬x. (3.2)
«Отрицание» является одноразрядной переключательной функцией,
поскольку она обладает только одним входным символом. Схемный эле-
мент «инвертор» обозначается с помощью схемного обозначения, пред-
ставленного на рис. 3.1.
Имеются ли еще одноразрядные переключательные функции? Пу-
тем систематических проб находим их общим числом 4, все они сведены
в табл. 3.2. Других видов одноразрядной переключательной функции y не
существует. Переключательные функции y = 0 и y = 1 вырабатывают посто-
янные, не зависящие от входа. Поэтому существенной для переключатель-
ной алгебры является только одноразрядная двоичная функция y = ¬x.
3.2. Двухразрядные переключательные функции
В принципе можно образовывать произвольные двоичные функции мно-
гих входных переменных. Но оказалось практичным вначале рассматри-
вать только функции с одной или двумя входными переменными, а функ-
ции с большим количеством входных переменных сводить к ним.
Двоичную функцию с входными переменными x0 и x1 также мож-
но определить с помощью таблицы. Комбинацию входных переменных
x0 и x1 можно представить в виде вектора X = [x0, x1]. Двум входным пере-
менным соответствуют 4 возможных входных вектора X, которые часто
индицируются через их десятичные эквиваленты. Так, x2 означает, что
x1 = 1 и x0 = 0, или, выражаясь по-другому, что X2 = [x1, x0] = [1, 0].
Наряду с «отрицанием» технически возможными являются основные
логические элементы И или ИЛИ, определяемые табл. 3.3. Также обозна-
чают И как AND или «конъюнкция»; ИЛИ как OR или «дизъюнкция».
Возникает вопрос о других возможных двухразрядных двоичных функ-
циях. Чтобы системно ответить на этот вопрос, надо осуществить пере-
становку значений входных переменных y, которые можно получить из
четырех возможных входных векторов. В общем случае функция y(x1, x0)
может быть определена таблицей истинности (табл. 3.4).
На основе этой таблицы можно сделать заключение о возможности об-
разования 22n = 16 различных двоичных функций с двумя входными пере-
менными. Все вероятные двухразрядные двоичные функции приведены в
табл. 3.5. Представление двоичных функций выполнено в соответствии со
стандартом DIN [10].
Технически важным функциям NAND, NOR, «эквивалентность» и
EXOR (также «исключающее ИЛИ», дизъюнкция) соответствуют соб-
ственные логические символы. На практике они часто реализуются на ос-
нове специальных схем.
В этой таблице показано, что отдельные функции могут быть представ-
лены только с помощью логических элементов AND, OR и NOT. Поэто-
му каждая логическая функция может быть представлена с помощью этих
трех логических элементов. Все двоичные функции могут быть представ-
лены как с помощью функции NOR, так и с помощью NAND. Поэтому
эти функции называют совершенными.
Доказательство эквивалентности можно привести путем размещения
таблиц истинности. Таким образом, например (см. табл. 3.5), может быть
доказана эквивалентность для логического элемента EXOR на основе
AND, OR или NOT:
x0 x1 = ¬x0 x1 x0 ¬x1. (3.3)
В табл. 3.6 вначале оцениваются оба выражения в скобках. Затем фор-
мируется логическое OR, соответствующее обоим выражениям в скоб-
ках, и вписывается в пустую колонку. Так как последняя и предпослед-
няя колонки совпадают, уравнение доказано, поскольку в последней
колонке стоит определение функции «исключающее ИЛИ» (то есть
EXOR).
Сегодня знание цифровой техники требуется в очень многих областях.
Невозможно понять принципы работы мобильной связи, микрокомпью-
терных технологий, систем цифрового управления и различного телеком-
муникационного оборудования без знания методов цифровой обработки
информации, а широкое применение интегрированных механико-элек-
тронных систем лишь усиливает эту тенденцию. Особое значение цифро-
вые технологии приобрели во встраиваемых системах. Речь идет о цифро-
вых схемах, которые «встраиваются» в те или иные технические решения.
Встраиваемые системы вы можете встретить в самых разных устрой-
ствах — стиральных машинах, автомобилях, холодильниках, развлекатель-
ной электронике, мобильных телефонах и т. д.
В данной книге отлично изложены основы цифровой техники, вклю-
чая устройство и программирование простых микропроцессоров. Поми-
мо прочной теоретической базы, читатель получит знания, позволяющие
понять принципы работы большинства цифровых схем. В это 8-е издание
внесены многочисленные дополнения. В частности, в главе о микропро-
цессорах в качестве примера рассматривается микропроцессор, широко
используемый в современной промышленности. Также добавлен материал
о представлении чисел с плавающей запятой.
Эта книга предназначена, в первую очередь, для студентов колледжей
и университетов, изучающих инженерию и информационные технологии.
Поскольку для понимания книги не требуется никаких специальных зна-
ний, она также подходит для широкого круга заинтересованных читате-
лей. Для работы с главой «Схемотехника» читателю понадобятся базовые
знания в области электроники, однако эта глава не обязательна для пони-
мания других глав книги, и ее можно пропустить. Представление булевой
алгебры и используемые символы в основном соответствуют действую-
щим стандартам DIN1.
Для облегчения самостоятельной работы с книгой каждая глава сопро-
вождается упражнениями, с помощью которых можно проверить понима-
ние материала. Предлагаемые решения можно найти в приложении. Одна
из основных задач данной книги — это подробное изложение основ циф-
ровой техники. В частности, много внимания уделено синтезу коммута-
ционных схем. Рассмотрены примеры широко применяемых стандартных
коммутационных схем, таких как мультиплексоры и преобразователи кода.
Поскольку для понимания работы процессоров важно знание арифмети-
ческих операций, подробно рассматриваются арифметика с фиксирован-
ной запятой и аппаратная реализация арифметико-логических устройств.
Сегодня в распоряжении разработчиков схем находятся совершенные ин-
струменты проектирования, позволяющие разрабатывать сложные циф-
ровые схемы, реализовывать их на основе полупроводников, тестировать и
настраивать работу схемы. Это обусловило бурное развитие интегральных
схем специального назначения (ASIC), которые заказчик может настроить
самостоятельно. Поэтому одна из глав посвящена таким интегральным
схемам. Следующая глава знакомит с VHDL – языком программирования
для описания, синтеза и моделирования интегральных цифровых схем,
который фактически стал стандартом и часто используется при проекти-
ровании схем ASIC. Такой язык описания оборудования (HDL) становит-
ся все более популярным при проектировании схем, поскольку он дает
значительные преимущества по сравнению с традиционными методами
графически ориентированного проектирования, особенно при работе над
сложными проектами. Опираясь на знание коммутационных схем, можно
переходить к изучению синхронных и асинхронных методов коммутации.
В книге представлена методика разработки синхронных и асинхронных
контроллеров. При этом в новой редакции больше внимания уделено син-
хронным контроллерам. Методы асинхронной коммутации сейчас приме-
няются, главным образом, в триггерах, наиболее распространенные типы
которых представлены в книге. Кроме того, рассмотрено проектирование
счетчиков и регистров сдвига и представлены некоторые примеры их про-
мышленной реализации. Отдельная глава посвящена сравнению различ-
ных технологий и свойств модулей памяти, которые существенно влияют
на характеристики современных вычислительных систем. Приведены ти-
повые временные диаграммы, иллюстрирующие принципы работы раз-
личных модулей памяти. Последняя глава представляет простое введение
в микропроцессорную технику. Для знакомства с устройством вычисли-
тельной машины поясняется принцип работы компьютера фон Неймана,
на примере которого описываются процессы выполнения команд. В каче-
стве практического примера в одном из разделов представлен современный микроконтроллер ATmega16 производства компании AVR, описаны
его структура и режимы работы. Подробно рассматривается программи-
рование на ассемблере, знание которого будет полезно при работе с раз-
личными типами процессоров.
Фульда,
март 2018 года,
Клаус Фрике
ГЛАВА 1
ВВЕДЕНИЕ
В последние годы значение цифровой техники все более и более возрас-
тает. Причина этого заключается в значительных преимуществах цифро-
вой техники при создании очень сложных систем. Это достигается путем
представления сигнала двумя значениями, которые могут обрабатываться
логическими вентилями с сильно нелинейными передаточными характе-
ристиками без сбоев, накопления и дальнейшего распространения иска-
жений сигнала. Благодаря такому представлению сигналов удалось соз-
дать полупроводниковую технологию, позволяющую реализовать до 107
элементов на одном кристалле.
Поскольку целью систем цифровой техники является обработка сиг-
налов, то следует несколько подробнее рассмотреть понятие «сигнал».
Сигналы служат для переноса информации. Они описываются такими
физическими величинами, как напряжение, ток, давление, сила и т. д.
Амплитуды таких величин зависят от времени. Передаваемая информа-
ция заключается в изменяющихся амплитудных значениях. Пусть, напри-
мер, измеряется зависящий от времени уровень жидкости F в резервуаре.
На рис. 1.1a показана зависимость уровня жидкости от времени. Если дат-
чик выдает электрический сигнал, напряжение которого пропорциональ-
но величине заполнения, получаем временную зависимость напряжения
Us, показанную на рис. 1.1 b. Этот сигнал имеет непрерывную величину,
то есть в измеряемом диапазоне могут появиться все значения амплитуды.
Системы, которые могут обрабатывать непрерывные по величине сиг-
налы, называются аналоговыми системами.
Дискретные по величине сигналы, которые также называют цифро-
выми сигналами, могут, в отличие от этого, принимать только определен-
ные дискретные значения в фиксированные моменты времени. Примером
цифрового сигнала является сигнал, который с помощью двух различных
уровней напряжения показывает, закрыта или открыта дверь. Подобные
сигналы могут непосредственно обрабатываться цифровыми системами.
В том случае, если сигналы с непрерывной величиной должны переда-
ваться цифровыми системами, эти сигналы должны быть предварительно
квантизированы. В соответствии с данным процессом, с определенными
временными точками (точками считывания) соотнесена амплитуда сигнала дискретной амплитудной ступени. Вышеупомянутый пример про-
демонстрирован на рис. 1.1с, показывающем датчик уровня заполнения.
При этом получаем напряжение с дискретными величинами Uq. При кван-
тизировании необходимо принимать во внимание ошибку округления.
При цифровой передаче сигнал вначале должен быть переведен в циф-
ровую форму. В этом случае амплитуда будет предъявляться с помощью
последовательности цифр. Каждая цифра представляет собой сигнал
с дискретным значением. На рис. 1.1d приведен пример кодирования с
помощью нескольких следующих друг за другом цифр. Амплитудная сту-
пень 0 представлена двумя цифрами 00. Амплитуды 1, 2 и 3 становятся
сочетаниями 01, 10, 11. Следует различать также дискретные во времени
сигналы и непрерывные во времени сигналы. Дискретные во времени сиг-
налы могут изменять свою амплитуду только в определенные моменты
времени, в то время как непрерывные во времени сигналы могут изменять
свою амплитуду в произвольные моменты времени. Цифровые системы
могут быть дискретными во времени, в этом случае их называют синхрон-
ными. Синхронизация осуществляется с помощью тактового сигнала.
Благодаря ограничению в использовании конечного числа амплитуд-
ных ступеней, цифровая система обладает высокой помехозащищенно-
стью. Подвергнувшиеся воздействию помех цифровые сигналы могут быть
однозначно приведены к первоначальным дискретным амплитудным зна-
чениям. Но чтобы не возникла ошибка, помеха не должна превышать по-
ловину расстояния между двумя амплитудными ступенями.
Цифровые системы имеют ряд преимуществ перед аналоговыми систе-
мами:
– При использовании цифровых сигналов не происходит накопле-
ния их искажений — появляется возможность реализации систем
любой степени сложности, например микропроцессоров. Это свой-
ство цифровых систем определяет их превосходство и при передаче
на большие расстояния.
– Цифровые системы сравнительно легко проектировать, посколь-
ку способ их описания, представляющий собой булеву алгебру, —
аппарат очень удобный для автоматизации. Сегодня разработка
сложных цифровых систем автоматизирована посредством приме-
нения высокопроизводительных алгоритмов.
– Цифровые системы можно относительно просто тестировать.
Недостаток цифровых систем:
– Цифровые системы являются более медленными системами, чем
аналоговые. Поэтому в области высоких частот доминирует анало-
говая техника.
ГЛАВА 2
КОДИРОВАНИЕ
И СИСТЕМЫ
СЧИСЛЕНИЯ
2.1. Коды
В цифровой технике коды используются для оптимального представления
сигнала в случае его применения. Код отображает символы одного мно-
жества через символы второго множества. При этом должна существовать
возможность декодирования, при которой вероятно получить исходные
символы из кодированных.
Известным примером кода является код Морзе. Определение кода
производится с помощью таблицы соответствия. Для кода Морзе подоб-
ное соответствие отображено в табл. 2.1. Этот код является обратимым, так
как из буквы можно получить символ Морзе, а из него можно вновь обра-
зовать букву. Но это справедливо только для текста, написанного строчны-
ми буквами, поскольку код Морзе не делает различия между прописными
и строчными буквами. Строго говоря, из кода Морзе нельзя восстановить
путем декодирования текст, записанный с помощью строчных и пропис-
ных букв.
Для каждого применения имеется более или менее подходящий код.
Так, для проведения операций над числами в компьютере рационально
применять иной код, чем для передачи чисел по линии связи. В данной
главе исследуются различия между отдельными кодами и даны указания
по их специфическому применению.
Комбинацию нескольких символов кода называют словом (word). В по-
следующем мы ограничимся технически важным случаем, в котором все
слова одного кода имеют одинаковую длину n. В коде Морзе это не про-
исходит. Если в код входит множество символов N, то Nn различных слов
могут иметь длину n. Когда используются все Nn возможных слов одного
кода, то в этом случае говорят о минимальном коде. При использовании
менее чем Nn слов его называют избыточным кодом. Ниже можно найти
описание наиболее употребительных кодов, их полное описание можно
получить из [7–9].
2.2. Двоичный код
Будучи универсальным, двоичный код является важнейшим в цифровых
системах. В соответствии с определением, при котором применяются толь-
ко символы 1 и 0, становится возможной обработка сигналов с помощью
схемных элементов, работающих как переключатели. Также двоичный код
позволяет использование арифметики, аналогичной арифметике десятич-
ных систем. При этом двоичную систему счисления можно рассматривать
как кодирование десятичной системы, где двоичное число состоит из сло-
ва, образованного символом ci {0, 1}. Символы ci одного слова называют
в цифровой технике битами. Слово z2 в двоичном представлении форми-
руется путем последовательного присоединения отдельных битов, как это
показано ниже:
z2 = cn–1cn–2 · · · c1 c0 · · · c–m + 1 c–m. (2.1)
Двоичное число имеет n разрядов перед запятой и m разрядов после за-
пятой. Отдельным битам присвоены, в соответствии с их позицией i в сло-
ве, весовые коэффициенты 2i. На основе этого можно рассчитать эквива-
лентное десятичное число z10:
см. уравнение в книге (2.2)
Рассмотрим в качестве примера двоичное число 10110,0012, которое
в качестве такового отмечено символом 2. Оно интерпретируется как:
g(z2) = 1 · 24 + 0 · 23 + 1 · 22 + 1 · 21 + 0 · 20 + 0 · 2–1 + 1 · 2–2 + 1 · 2–3 =
= z10 = 22,37510
Двоичный (или дуальный) код обозначается как взвешенный, по-
скольку стоящие дальше влево биты обладают более высокими весовыми
коэффициентами. Уравнение (2.2) можно рассматривать как правило, в
соответствии с которым производится преобразование двоичных чисел в
десятичные числа.
Преобразование же десятичных чисел в двоичные числа является более
сложным. Его можно описать различными алгоритмами для целочислен-
ной и дробной частей. В приведенном выше примере с числом 22,37510
алгоритм должен быть представлен следующим образом:
Вначале формируется целочисленная часть двоичного числа.
Для чего целочисленная часть десятичного числа последовательно
делится на 2 и записывается остаток, пока не будет получен 0.
22 : 2 = 1
11 : 2 = 5
5 : 2 = 2
2 : 2 = 1
1 : 2 = 0
остаток 0
остаток 1
остаток 1
остаток 0
остаток 1
цело-
числ. часть
двоичного
числа
Соответствующее числу 2210 двоичное число представляет собой 101102.
Второй шаг заключается в преобразовании дробной части деся-
тичного числа в дробную часть двоичного числа. Вначале дробная
часть десятичного числа умножается на 2. Целочисленная часть от-
деляется, она образует разряды двоичного числа с наименьшими
значениями.
Процесс повторяется, как это показано ниже.
0,375 · 2 = 0,75
0,75 · 2 = 0,5
0,5 · 2 = 0
+0
+1
+1
дробная часть
двоичного
числа
В данном примере мы видим, что остаток равен 0. Но не обязатель-
но так всегда бывает. В нормальном случае дробная часть эквивалентного
двоичного числа имеет бесконечно большое количество разрядов. В дан-
ном случае необходимо удовольствоваться определенным числом разря-
дов после запятой и этим ограничить точность.
В нашем случае 0, 37510 точно соответствует 0, 0112. На основе целочис-
ленной и дробной частей получаем искомое двоичное число 10110,0112.
2.3. Арифметические операции с фиксированной
запятой в двоичной системе
В данной главе описываются арифметические операции с числами с фик-
сированной запятой. Арифметические операции с фиксированной запя-
той означают, что в них запятая всегда стоит на фиксированном месте.
При этом место, на котором стоит запятая, ориентируется на позицию
в запоминающем устройстве (ЗУ), на которой находится число. В этом
случае нет необходимости реализовать запятую в аппаратуре компьютера.
Она существует только в голове программиста. Мы ограничиваемся посто-
янной длиной слова n, как это имеет место в компьютерах. На основе этого
можно обсудить проблему переполнения допустимой области.
2.3.1. Целочисленное сложение в двоичной системе
Целочисленное сложение двух чисел A и B производится в двоичной си-
стеме точно так же, как и в десятичной системе — по разрядам. Как и там,
в каждом разряде должны быть просуммированы обе двоичных цифры an и
bn и перенос из предыдущего разряда Cn–1.
При сложении возникают (табл. 2.2) новая сумма Sn и новый перенос Cn.
В этой таблице дискретной линией разделены входные и выходные ве-
личины. Например:
0 1 1 1 1 1 1 0
+ 0 0 1 1 0 1 0 1
перенос 1 1 1 1 1 0 0
= 1 0 1 1 0 0 1 1
В приведённом выше примере, чтобы не было переполнения, необ-
ходимо суммировать два числа длиной 8 бит, итог которых также должен
иметь длину 8 бит.
2.3.2. Сложение чисел с фиксированной запятой
В случае когда суммируются два числа с фиксированной запятой, важно,
как и в обычной процедуре, чтобы обе запятые стояли друг над другом.
Так, при сложении двух чисел длиной в 8 бит запятая у обоих чисел должна
стоять, например, на третьем месте.
Например:
+ 0 1 1 0 0, 0 1 0
0 0 1 1 0, 1 1 1
перенос 1 1 0 0 1 1 0
= 1 0 0 1 1, 0 0 1
2.3.3. Представление с помощью обратного кода
Для того, чтобы иметь малые затраты на аппаратурную часть (hardware)
компьютера, были предприняты усилия по сведению к одному
алгоритму вычитания и сложения. Этого можно добиться, если при-
менять двоичные цифры в их дополняющей форме. Различают единичное
дополнение (обратный код, поразрядное дополнение) и двойное дополне-
ние (точное дополнение).
Поразрядное дополнение формируется путем замены всех нулей на
единицы и обратно. Следовательно, поразрядным дополнением (one’s
complement) 0001 является 1110. Ниже поразрядное дополне ние двоично-
го числа A обозначено ¬A. Очевидно, что при представлении n-битового
слова имеем:
¬A + A = 2n – 1. (2.3)
Например, при представлении 8-битового слова имеем:
10110011 + 01001100 = 11111111 = 28 – 1.
Можно так преобразовать уравнение (2.3), чтобы получить формулу
для расчета поразрядного дополнения:
¬A = 2n – 1 – A. (2.4)
2.3.4. Представление с помощью двойного дополнения
(точное дополнение, two’s complement)
Точное дополнение AK2 образуется из поразрядного дополнения ¬A путем
прибавления 1:
AK2 = ¬A + 1. (2.5)
Следовательно, с учетом (2.4) будет справедливо:
AK2 = 2n – A. (2.6)
Мы видим, что в данном представлении содержится «–A», благодаря
чему оно удобно для проведения вычитания. Учтем также, что 2n в двоич-
ном представлении имеет n + 1 разрядов. Ниже пример точного дополне-
ния для 10101100:
AK2 = ¬A + 1 = 01010011 + 1 = 01010100
Представление 4-битовых двоичных слов в круговой форме, приведен-
ное на рис. 2.1, позволяет показать числовой диапазон. Соответствующее
данным значениям наибольшее представляемое положительное число рав-
но 710, соответствующее данным значениям наибольшее отрицательное чис-
ло равно –810. Следовательно, числовой диапазон построен несимметрично,
поскольку отрицательное число занимает больше места, чем положитель-
ное. Наибольшее и наименьшее представляемые числа можно выразить как:
zmax = 2n–1 – 1, (2.7)
zmin = –2n–1. (2.8)
На рис. 2.1 можно видеть, что малые числа, сформированные на осно-
ве точного дополнения, содержат много ведущих единиц, когда они от-
рицательны, и содержат много ведущих нулей, когда они положительны.
В числах, представленных в формате дополнения до двух, на крайней по-
зиции слева стоит нуль, когда они отрицательны, и единица, когда они
положительны. Их собственным точным дополнением является число 10002 (–810). Важно установить, что при представлении на основе точного
дополнения имеем только один 0. Это облегчает запрос, равен ли резуль-
тат 0. Напротив, при представлении на основе поразрядного дополнения
имеют место двоичное число 00002, соответствующее +010, и двоичное чис-
ло 11112, соответствующее –010.
2.3.5. Вычитание при представлении с помощью
точного дополнения
Пусть будут вычтены одно из другого два положительных двоичных чис-
ла A и B. При условии применения точного дополнения в соответствии
с уравнением (2.6) вычитание можно провести следующим образом:
A – B = A – B + BK2 – BK2 = A – B + BK2 – (2n – B). (2.9)
Раскрытие скобок в правой части уравнения дает:
A – B = A + BK2 – 2n. (2.10)
Что означает вычитание 2n? Поясним это на примере операции вычи-
тания 7 – 3 = 4 в 4-битовой двоичной системе. Сумма двоичного эквива-
лента числа 7 и дополнение двоичного эквивалента числа 3 равняется:
0 1 1 1 7 + 10 1 1 0 1 –310
= 1 0 1 0 0
– 1 0 0 0 0
= 0 1 0 0 410
Вычитание числа 100002, проведенное в соответствии с уравнени-
ем (2.10), дает правильный результат 01002. Это может произойти в 4-бито-
вом компьютере просто потому, что высший результат игнорируется. Итак,
при проведении вычитания с помощью точного дополнения нет необходи-
мости учитывать высший перенос c4. Но необходимо соблюдать осторож-
ность в связи с переполнением числового диапазона. Исследуем это ниже.
2.3.6. Переполнение числового диапазона
Исходя из вышесказанного, возникает необходимость рассмотрения про-
блемы переполнения числового диапазона (overflow) в связи с представле-
нием на основе точного дополнения. Переполнение числового диапазона
может происходить только в двух случаях. А именно, когда суммируются
два положительных числа либо суммируются два отрицательных числа.
В связи с этим рассмотрим несколько примеров, относящихся к 4-бито-
вому представлению.
Пример переполнения числового диапазона при сложении двух по-
ложительных чисел:
0 1 0 1 5 + 10 0 1 0 1 510
= (0) 1 0 1 0 –610
Очевидно, что результат является неправильным. Ошибка возника-
ет за счет переноса 3-го разряда на место 4-го разряда, что приводит
к симуляции отрицательного числа. Этот перенос c3 в представле-
нии, использующем n бит, обычно обозначается как cn–1. Перенос
c4 (в общем случае cn) из разряда 4 в разряд 5 называется Carry (Cy).
В этом примере данный перенос не имеет места.
Пример переполнения численного диапазона при сложении отри-
цательных чисел:
1 0 1 1 –5+ 10 1 0 1 1 –510
= (1) 0 1 1 0 610
В этом примере также появляется неправильный результат. Имеет
место не перенос cn–1 из разряда 3 в разряд 4, а перенос cn из разряда
4 в разряд 5.
Для сравнения проведем сложение двух отрицательных чисел без
переполнения числового диапазона:
1 1 1 1 –1 + 10 1 1 0 1 –310
= (1) 1 1 0 0 –410
Имеются переносы cn и cn–1.
Сведем эти результаты вместе с другими, здесь не показанными случа-
ями в таблицу. На основе результатов, представленных в табл. 2.3, для двух
двоичных чисел A и B, которые лежат в числовом диапазоне, определяе-
мом n-битовым представлением на базе точного дополнения, можно уста-
новить перенос переполнения при сложении.
= cn–1, неправильный результат — когда cn cn–1.
2.3.7. Умножение
Умножение выполняется так же, как и для десятичной системы. Рас-
смотрим пример умножения на основе двоичной системы для чисел
1010 1110 = 11010:
1 0 1 0
1 0 1 1
1 0 1 0
1 0 1 0
1 0 1 0
1 1 0 1 1 1 0
Наибольший из ожидаемых результатов E умножения двух n-битовых
слов представляет собой:
E = (2n – 1) · (2n – 1) = 22n – 2n+1 + 1 22n – 1
Следовательно, результат умножения двух n-битовых чисел имеет дли-
ну 2n бит. Но он меньше, чем максимальное представляемое с помощью 2n
бит двоичное число 22n – 1.
Сказанное выше справедливо для умножения положительных чисел.
При вычислениях с использованием представления на основе точного
дополнения могут быть применены специальные алгоритмы [41], или же
числа на основе точного дополнения перед умножением следует преобра-
зовать обратно в исходные значения, а результат перевести в соответствии
со знаком в желаемое представление.
При умножении чисел с фиксированной запятой вначале числа умно-
жаются без учета запятой. Затем запятая вводится в соответствии с прави-
лом: умножение двух чисел с n и k разрядами после запятой даст произве-
дение с n + k разрядами после запятой.
2.3.8. Деление
Для деления можно использовать тот же самый алгоритм, что и в де-
сятичной системе. Продемонстрируем это на примере уравнения
1010 : 210 = 5D:
1 0 1 0 | 0 0 1 0
– 1 0 1 0 1
– 0 1 0
1 0
0
Соответственно, при делении числа с n разрядами после запятой
на число с k разрядами после запятой частное имеет n – k разря-
дов после запятой. Так, в соответствии с верхним примером имеем
(1,2510 : 0,510 = 2,510): 1,010 : 00,10 = 10,1. Деление чисел с точным дополне-
нием также можно свести к умножению и сложению [41].
2.4. Представление вещественных чисел с плавающей
запятой
2.4.1. Введение: представление с плавающей запятой
в десятичной системе счисления
Большие числа обычно представляются в экспоненциальном виде с пла-
вающей запятой. Примером может служить представление скорости света:
2,99792458 · 108 м/с. В общем виде:
Число m называется мантиссой, а e — показателем степени. Здесь e — це-
лое число, а m — число с фиксированной запятой со знаком. В этом при-
мере мантисса равна 2,99792458, а показатель степени равен 8. Для пред-
ставления чисел в формате с плавающей запятой характерно наличие
основания b. В данном примере основание b = 10. И показатель степени,
и мантисса имеют знак. В компьютерах используется представление в дво-
ичной системе с основанием b = 2.
2.4.2. Представление с плавающей запятой в двоичной
системе счисления
В этой главе описывается представление с плавающей запятой в двоич-
ной системе счисления. В информатике эту форму представления числа
называют «реальной», поскольку ее можно использовать для представле-
ния действительных чисел. Согласно стандарту IEEE-754 в общем случае
представление чисел с плавающей запятой имеет следующий вид:
z = (–1)s · 1, m · 2e = (–1)s · 1, m · 2(c–q). (2.12)
s — знак мантиссы, он представлен одним битом.
1, m — абсолютное значение мантиссы. Оно хранится как двоич-
ное число с фиксированной запятой и перед местом, обозначенным
запятой. Оно всегда равно единице. Число m после запятой назы-
вается дробной частью. m выбирается согласно выбору показателя
степени так, чтобы удовлетворять условию:
2 > | 1, m | 1. (2.13)
Условие верно только для чисел z 0. Следовательно, нельзя пред-
ставить нуль. Форма записи с плавающей запятой, удовлетворяю-
щая условию (2.13), называется нормализованной. Мантисса рас-
полагает в компьютере фиксированным количеством цифровых
позиций nm.
Вместо показателя степени e сохраняется характеристика c = e + q.
Она имеет фиксированное количество цифр nc. При добавлении
остатка показатель степени e сдвигается так, чтобы сохранять толь-
ко положительные числа. Остаток равен
q = 2nc–1 – 1. (2.14)
Таким образом, например, для 8 цифр (nc = 8) получим остаток 127. Это
означает, что могут быть представлены показатели от –127 до 128. Наименьшая характеристика 0 получается, когда наименьший показатель сте-
пени равен –127, и становится равной нулю при добавлении остатка 127.
Наибольшая характеристика, а именно наибольшее число 255, которое
может быть представлено 8 битами, получается из суммы наибольшего по-
казателя 128 и остатка 127.
Согласно стандарту IEEE-745 часто используются две степени точно-
сти — одинарная точность и двойная точность.
Два часто используемых числовых формата согласно IEEE-745 — это
одинарная точность и двойная точность. Согласно табл. 2.4 используются
двоичные цифры 1 + nc + nm. Для чисел в числовом формате одинарной
точности требуется 32 бита, в формате двойной точности — 64 бита.
Пример:
Действительное число –0,17187510 должно быть преобразовано в фор-
мат одинарной точности согласно IEEE-745. Первая цифра — это знак s.
s = 1 означает отрицательную мантиссу, s = 0 — положительную. В данном
случае s = 1.
Сначала вы конвертируете десятичное число в двоичное:
–0,17187510 = –0,0010112
Затем число нормализуется, и тогда оно будет иметь вид 1, m · 2 n:
–0,0010112 = –1,011 · 2–3
2–3 означает, аналогично десятичной системе счисления, сдвиг на 3 пози-
ции. Мантисса сохраняется без 1 перед десятичной запятой и расширяется
до 23 бит с нулями или округляется до 23 разрядов, если необходимо:
m = +1,011 0000 0000 0000 0000 0000
Избыток q добавляется к показателю степени e = –3 (для одинарной
точности q = 127), чтобы получить характеристику c. Он сохраняется как
8-значное двоичное число:
c = e + q = –3 + 127 = 12410 = 011111002
Теперь число, которое нужно сохранить, формируется путем совмеще-
ния s, c и m
s c m
1 01111100011 0000 0000 0000 0000 0000
Итак, двоичное число, которое мы ищем:
1011 1110 0011 0000 0000 0000 0000 00002.
2.4.3. Особые представления чисел
По определению нуль не может быть представлен, так как мантисса
равна 1, m, и следовательно всегда не равна 0. В качестве альтерна-
тивы было определено число с мантиссой 1,00 ... и характеристикой
0. Это наименьшее число, которое можно представить, и оно опре-
делено в качестве нуля. Поскольку разрешены оба знака, получает-
ся два представления нуля.
Числа с мантиссой 1,00. . . и максимально возможной характери-
стикой определены для представления ± бесконечности. При пред-
ставлении бесконечности с одинарной точностью это число 255.
Кроме того, существует представление под названием NaN (Not a
Number — не число). Это число не считается числом с плавающей
запятой и обычно приводит к отмене вычисления.
2.5. Шестнадцатеричный код
На практике наряду с двоичным кодом внедрился шестнадцатеричный код,
поскольку он обеспечивает лучшее обозрение длинных двоичных чисел.
Шестнадцать шестнадцатеричных цифр определены в табл. 2.4. Шестнад-
цатеричные цифры больше девяти представлены буквами A–F. Для преобразования двоичных в шестнадцатеричные числа объединяют по четыре
цифры двоичного числа, которые интерпретируются как шестнадцатерич-
ный разряд. Благодаря этому шестнадцатеричное число занимает только
четверть разрядов, занимаемых двоичным числом одинаковой величины.
Например:
1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0
B E 3 0
Итак, справедливо выражение 10111110001100002 = BE3016.
В качестве обозначения шестнадцатеричного числа используется ин-
декс H и $. Преобразование шестнадцатеричного числа в десятичное чис-
ло и обратно проще всего производить через соответствующее двоичное
число. Также возможно производить преобразование с помощью алгорит-
ма, как при преобразовании двоичного числа в десятичное число. Обрат-
ное преобразование производится аналогично представленному уравне-
нием (2.2).
2.6. Восьмеричный код
Восьмеричный код применяется аналогично шестнадцатеричному, толь-
ко объединяются лишь по 3 разряда двоичного числа. Для восьмеричного
кода применяются цифры десятичного кода от 0 до 7, он обозначается ин-
дексом 0.
Например:
1 1 0 1 0 1 1 0 0 0 1 1
6 5 4 3
Следовательно, справедливо 110101000112 = 65438.
2.7. Код Грея
Часто в цифровой технике требуется для числового кода схема кодирова-
ния, в соответствии с которой при переходе от одного числа к следующему
изменялась бы только одна цифра. Выполнение этого условия необходи-
мо, когда вследствие технических неточностей момент переключения не
может быть точно выдержан. Из-за этого при переключении двух цифр
могут возникнуть неправильные коммутационные операции. В качестве
примера подобной ошибки рассмотрим переключение от 110 к 210 в дво-
ичном коде:
0000 0011
0001
0010
При этом переключении изменяются биты 0 и 1, при одновременном
переключении непосредственно достигается новое число. Если вначале
изменяется бит 0, то появляется число 0000, и только когда изменяется бит
1, получаем правильное число 0010. Если же сначала изменяется бит 1 и
потом изменяется бит 0, то в промежутке возникает число 0011. Коды Грея
позволяют избежать этой очень серьезной ошибки за счет того, что при
переходе от одного кодового слова к следующему изменяется только один
разряд. В табл. 2.7 представлен 4-разрядный код Грея. В дополнение к вы-
шесказанному показанный код имеет свойство, которое заключается в его
цикличности, также как и при переходе от высшего числа (15D) к низшему
числу изменяется только один разряд. Циклические коды Грея могут быть
сконструированы для всех прямых длин периодов.
Таблица 2.7. Пример 4-разрядного кода Грея
Десятичные (числа) Код Грея Десятичные (числа) Код Грея
0 000 4 110
1 001 5 111
2 011 6 101
3 010 7 100
2.8. Двоично-десятичный код
Если мы хотим подвести к десятичным цифрам некоторые отметки, то
для этого подойдет код, в котором отдельным десятичным цифрам приданы двоично-кодированные кодовые слова. Этот код обозначается как
двоично-десятичный код (BCD-код). Подходящая возможность реализа-
ции заключается в том, чтобы каждой десятичной цифре сопоставить ее
запись в двоичной системе счисления, то есть четырехразрядное двоичное
число (см. табл. 2.6). Поскольку отдельные разряды имеют веса 8, 4, 2 и 1,
данный код называют кодом типа 8-4-2-1. Существует также возможность
построить двоично-десятичный код 2, 4, 2, 1 (Aiken-Code). К другим дво-
ичнодесятичным кодам относятся код с избытком три (3-Excess-Code) и
двоично-десятичный код Грея (BCD-Gray-Code) [5].
2.9. Алфавитно-цифровые коды
Существует большое количество кодов, осуществляющих представление
алфавитно-цифровых символов с помощью двоичных цифр.
Известным примером подобных символов является код ASCII
(American Standard Code for Information Interchange), который содержит
также ряд управляющих символов.
2.10. Упражнения
Задача 2.1. Преобразуйте следующие двоичные числа в десятичные числа:
а. 1110,101
б. 10011,1101
Задача 2.2. Преобразуйте следующие десятичные числа в двоичные числа:
а. 33,125
б. 45,33
Задача 2.3. Рассчитайте приведенные ниже примеры с использованием
точных дополнений при длине слова в 6 бит. Укажите, имеет ли место пе-
реполнение числового диапазона.
а. 010101 –001010
б. –010111 –011011
Задача 2.4. Рассчитайте в двоичной системе:
а. 110101 · 010101
б. 1101110 : 110
Задача 2.5. Разработайте циклический код Грея с длиной периода 6.
Задача 2.6. Какое действительное число представлено числом одинарной
точности C23A800016 согласно IEEE-754?
ГЛАВА 3
ПЕРЕКЛЮЧАТЕЛЬНАЯ
АЛГЕБРА
Цифровая техника имеет преимущество перед аналоговой техникой: она
основывается на относительно простой, но при этом мощной теории, на
булевой алгебре, называемой также переключательной алгеброй. В данной
главе представлены теоретические основы цифровой техники. Булева ал-
гебра может быть применена для решения почти всех проблем, возникаю-
щих при разработке цифровых схем с условием выполнения технологиче-
ских предпосылок, которые рассматриваются в главе 4.
3.1. Переключательная переменная
и переключательная функция
В цифровой технике применяют специальные переменные и функции.
Под булевой переменной понимают переменную, которая может прини-
мать только значения 0 и 1. С булевыми переменными могут быть образо-
ваны функции. Функцию
y = fx1, x2, x3, . . . xn при xi, y {0, 1} (3.1)
называют n-разрядной переключательной или двоичной функцией. Об-
ласть значений подобной функции также определяется двоичной систе-
мой счисления с элементами 0 и 1. Функции могут быть определены та-
блицами, в которых величины функций связываются с возможными 2n
комбинациями n входных переменных. Эти таблицы называются табли-
цами истинности.
Очень простая функция, которая связывает входную переменную x
с выходной переменной y, представлена в табл. 3.1. Можно видеть, что
все переключательные функции могут быть определены таблицей, со-
держащей все входные переменные, поскольку учитывать необходимо
только два элемента 0 и 1.
Определенную табл. 3.1 переключательную функцию y = f (x) именуют
«отрицание», «дополнение» или НЕТ (NOT). В последующем она обозна-
чается оператором « ¬ » и читается «y равен не x»:
y = ¬x. (3.2)
«Отрицание» является одноразрядной переключательной функцией,
поскольку она обладает только одним входным символом. Схемный эле-
мент «инвертор» обозначается с помощью схемного обозначения, пред-
ставленного на рис. 3.1.
Имеются ли еще одноразрядные переключательные функции? Пу-
тем систематических проб находим их общим числом 4, все они сведены
в табл. 3.2. Других видов одноразрядной переключательной функции y не
существует. Переключательные функции y = 0 и y = 1 вырабатывают посто-
янные, не зависящие от входа. Поэтому существенной для переключатель-
ной алгебры является только одноразрядная двоичная функция y = ¬x.
3.2. Двухразрядные переключательные функции
В принципе можно образовывать произвольные двоичные функции мно-
гих входных переменных. Но оказалось практичным вначале рассматри-
вать только функции с одной или двумя входными переменными, а функ-
ции с большим количеством входных переменных сводить к ним.
Двоичную функцию с входными переменными x0 и x1 также мож-
но определить с помощью таблицы. Комбинацию входных переменных
x0 и x1 можно представить в виде вектора X = [x0, x1]. Двум входным пере-
менным соответствуют 4 возможных входных вектора X, которые часто
индицируются через их десятичные эквиваленты. Так, x2 означает, что
x1 = 1 и x0 = 0, или, выражаясь по-другому, что X2 = [x1, x0] = [1, 0].
Наряду с «отрицанием» технически возможными являются основные
логические элементы И или ИЛИ, определяемые табл. 3.3. Также обозна-
чают И как AND или «конъюнкция»; ИЛИ как OR или «дизъюнкция».
Возникает вопрос о других возможных двухразрядных двоичных функ-
циях. Чтобы системно ответить на этот вопрос, надо осуществить пере-
становку значений входных переменных y, которые можно получить из
четырех возможных входных векторов. В общем случае функция y(x1, x0)
может быть определена таблицей истинности (табл. 3.4).
На основе этой таблицы можно сделать заключение о возможности об-
разования 22n = 16 различных двоичных функций с двумя входными пере-
менными. Все вероятные двухразрядные двоичные функции приведены в
табл. 3.5. Представление двоичных функций выполнено в соответствии со
стандартом DIN [10].
Технически важным функциям NAND, NOR, «эквивалентность» и
EXOR (также «исключающее ИЛИ», дизъюнкция) соответствуют соб-
ственные логические символы. На практике они часто реализуются на ос-
нове специальных схем.
В этой таблице показано, что отдельные функции могут быть представ-
лены только с помощью логических элементов AND, OR и NOT. Поэто-
му каждая логическая функция может быть представлена с помощью этих
трех логических элементов. Все двоичные функции могут быть представ-
лены как с помощью функции NOR, так и с помощью NAND. Поэтому
эти функции называют совершенными.
Доказательство эквивалентности можно привести путем размещения
таблиц истинности. Таким образом, например (см. табл. 3.5), может быть
доказана эквивалентность для логического элемента EXOR на основе
AND, OR или NOT:
x0 x1 = ¬x0 x1 x0 ¬x1. (3.3)
В табл. 3.6 вначале оцениваются оба выражения в скобках. Затем фор-
мируется логическое OR, соответствующее обоим выражениям в скоб-
ках, и вписывается в пустую колонку. Так как последняя и предпослед-
няя колонки совпадают, уравнение доказано, поскольку в последней
колонке стоит определение функции «исключающее ИЛИ» (то есть
EXOR).