книги из ГПНТБ / Архаров В.И. Арифметические и логические основы цифровых вычислительных машин учеб. пособие
.pdf
Министерство высшего и среднего специального образования РСФСР
СЕВЕРО-ЗАПАДНЫЙ ЗАОЧНЫЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ
В. И. АРХАРОВ
Одобрено Редсоветом СЗПИ
9 апреля 1973 .г.
АРИФМЕТИЧЕСКИЕ И ЛОГИЧЕСКИЕ ОСНОВЫ ЦИФРОВЫХ ВЫЧИСЛИТЕЛЬНЫХ МАШИН
УЧЕБНОЕ ПОСОБИЕ
ЛЕНИНГРАД
.1 97 4
j |
: 0-1 |
■■ f- '<■ |
|
и-.' . •: |
:•• |
|
r>-C |
, • |
Ы Т <0 • о |
ЧИТАЛЬНОГО ЗлЛА |
|
~ч ч - н т
ВИКТОР ИВАНОВИЧ АРХАРОВ
АРИФМЕТИЧЕСКИЕ И ЛОГИЧЕСКИЕ ОСНОВЫ
ЦИФРОВЫХ ВЫЧИСЛИТЕЛЬНЫХ МАШИН
УЧЕБНОЕ ПОСОБИЕ
Научный редактор канд. ф.-м. наук А. Н. ЖЕ Р НА К
© — Издание Северо-Западного заочного политехнического института, 1974 г.
2 ^
В В Е Д Е Н И Е
Настоящая книга предназначается в качестве учебного пособия для студентов специальности 0608 — «электронные вычислитель ные машины».
Содержание этой книги представляет собой расширенный курс лекций, которые читались автором для студентов, специализирую щихся по вычислительной технике, в Северо-Западном заочном политехническом институте. Причиной, побудившей автора напи сать настоящее пособие, явилось отсутствие какой-либо моногра фии или пособия, содержание которых соответствовало бы мате риалу, сообщаемому на лекциях по курсу «Арифметические и ло гические основы ЦВМ».
Известные книги Д. А. Поспелова, М. А. Карцева, А. А. Папернова, несмотря на целый ряд достоинств, не содержат в едином це лом необходимого материала и не могут быть эффективно исполь зованы при подготовке студентов.
При работе над учебным пособием автор широко использовал отечественную и зарубежную литературу. При этом в отдельных случаях заимствовались доказательства или примеры. Ссылок на эти заимствования в тексте не делалось. Необходимо отметить, что все работы, которые были использованы автором, приведены и ука заны в конце пособия.
Курс «Арифметические и логические основы цифровых вычис лительных машин», как показывает само название его, состоит из двух независимых частей.
Первая часть курса — арифметические основы цифровых вы числительных машин. В ней рассматриваются принципы построе ния позиционных систем счисления, способы записи чисел в маши нах, арифметические операции в двоичной системе и методы выпол нения их на цифровых вычислительных машинах. Изучение этих вопросов необходимо по целому ряду соображений. В большинстве цифровых вычислительных машин применена не десятичная, а двоичная система счисления. Без знания этой системы счисления, а главное, способов выполнения арифметических операций над дво ичными числами, отличающихся от десятичной арифметики про стотой и в то же время необычностью,— невозможно, понимание принципа действия таких важнейших частей машины, как арифме тическое и управляющее устройство. И тем более невозможно ква лифицированное и оперативное обслуживание действующей машины
1* |
3 |
или рациональное проектирование вновь строящейся вычислитель ной машины.
Эта часть курса содержит большое количество примеров и кон трольных вопросов.
Вторая часть курса — логические основы ЦВМ. Цель этой ча сти курса — обеспечение специалиста знанием аппарата булевой алгебры в теоретико-множественном плане и в плане логических схем, методов представления булевых функций, включая методы геометрического представления, методов минимизации булевых функций, используемых при синтезе логических схем.
Глава седьмая второй части посвящена исчислению предикатов, где рассматриваются основные понятия логики предикатов и их тождественные преобразования. Особое внимание уделено преди катам с ограниченными кванторами.
Материал, изложенный в книге, является теоретической основой для изучения вычислительной техники различного назначения.
Часть I
АРИФМЕТИЧЕСКИЕ ОСНОВЫ ЦВМ
Глава первая
С И С ТЕ М Ы СЧИСЛЕНИЯ
Системой счисления называется совокупность ограниченного числа названий и знаков, с помощью которых можно письменно или устно изобразить данное число.
Различные системы счислений отличаются друг от друга мно жеством признаков, важнейшим из которых является основание системы счисления.
Основанием системы счисления называется количество допусти мых символов или цифр, которые могут стоять на месте каждого разряда числа. Например, если для изображения числа исполь зуются десять различных цифр, обозначающих последовательные целые числа от 0 до 9, то система называется десятичной, если ис пользуются всего две цифры: 0 и 1, то — двоичной и т. д.
В общем случае в системах счисления с основанием q исполь зуется q различных цифр, обозначающих последовательные целые числа от 0 до (q— 1) включительно.
Все системы счисления делятся на два основных класса: пози ционные и непозиционные.
§ 1. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ
В позиционных системах счисления значение каждой цифры (символа), входящей в запись числа, зависит от ее положения в последовательности цифр (символов), служащих для изображения данного числа.
В общем виде число в позиционной системе записывается в виде суммы степеней основания q с соответствующими коэффициентами
Nq — o.nqn+ ап—%qn + |
■• |
• + ai<? +Оо?° + а—\Ц *+ |
• • • |
. . |
. |
-)-d —nq ", |
(1-1) |
где q — основание системы, |
а — коэффициенты (цифры) |
системы |
|
от 0 до (q—1), причем каждая цифра а может быть представлена каким-то одним знаком (например, цифры десятичной системы пред
5
ставляются знаками О, 1, 2, 3, . . . 9), либо может быть выражена
несколькими |
цифрами другой системы счисления, т. е. записана |
в виде числа, |
закодированного в другой системе счисления. |
Часто в системах с основанием q коэффициент а заменяют дво ичным изображением при помощи п двоичных разрядов. Такие си стемы называются двоично-кодированными.
Однако запись числа в виде (1.1) неудобна и громоздка, по этому при изображении числа степени основания q опускают, и число
записывается в виде последовательности |
коэффициентов |
системы, |
в которых целая часть отделяется от дробной запятой |
|
|
N q — апап- \ . . . аха0, a _ t |
. . . a_„. |
(1.2) |
Запятая опускается, если нет отрицательных степеней. Позиции цифр, отсчитываемые от запятой, называют разрядами.
В позиционной системе счисления значение каждого разряда больше значения соседнего справа разряда в число раз, равное ос нованию q. Если коэффициенты ап и an_, изображаются одной и
той же цифрой системы, то
В современных ЦВМ из всего разнообразия позиционных систем практическое применение нашли системы с основаниями
<7= 2, 3, 8, 10, 16.
Такие системы называются соответственно двоичными, троич ными, восьмеричными, десятичными, шестнадцатиричными.
Десятичная система счисления
Десятичная система счисления является общепринятой для ма тематических вычислений при ручном и автоматическом счете. В десятичной системе для изображения числа используются десять различных цифр
0, |
1, |
2, |
3, |
4, |
5, |
6, |
7, |
8, |
9. |
(1.3) |
Основание системы |
q = |
10 запишется |
как |
10, поскольку оно |
||||||
является единицей следующего (второго) разряда. Запись чисел, отличных от последовательности (1.3), производится комбинацией этих десяти цифр.
В общем виде число в десятичной системе записывается в виде
M10 = a„10" + a„-i 10n-1 + . . . + a 1101 + |
a010° + a _ 110~1+ . . . |
. . . + а _ „ 1 0 - " , |
(1.4) |
где 10 — основание десятичной системы,
а— коэффициент, равный любой цифре из последовательно сти цифр (1.3).
6
В сокращенном виде число запишется как
Например:
Af10= 5-106+ 0-105+ |
Ы 0 4+ 0-103+ ( Ы 02+ 3-10,+ |
|
|
+ 4-10°+9-10 |
1+ 8 -10“ 2 |
N 10= 50 100 34, 98, |
|
|
J N 10 |
= 7-10‘ + 6-10° + |
2- 10”.!-|- 0-10 2-f- 5• 10~3 |
| N 10 |
= 76, 205. |
|
Восьмеричная система счисления
В восьмеричной системе для записи всевозможных чисел приме
няют восемь различных |
цифр |
|
|
|
|
|
|
|
0, |
1, |
2, |
3, |
4, |
5, |
6, |
7. |
(1.6) |
Основание системы q — 8 записывается как 10, поскольку оно является единицей второго разряда. В дальнейшем, где это необ ходимо для большей наглядности, будем записывать основание лю бой системы счисления 10 в привычной для нас десятичной системе.
Запись чисел, отличных от последовательности цифр (1.6), про изводится комбинацией указанных восьми цифр.
В общем виде число в восьмеричной системе счисления записы вается в виде
N 8 — ап8 -\-ап_ ,8П + |
• • • |
+ Я[8 -j-o08 4 -n _ t8 |
-f- |
• • • |
+ а_п8~я , |
(1.7) |
|
где 8 — основание восьмеричной |
системы, записанное |
в десятич |
|
ной системе; |
|
|
|
а— коэффициент, равный любой цифре из последовательности цифр (1.6).
Всокращенном виде число запишется как
N 8 = a na n - 1 ■ • • а 1й 0’ « - ! • • • а _ п . |
( 1 . 8 ) |
Пользуясь соотношениями (1.7) и (1.8), составим таблицу неко торых целых, правильных и неправильных дробных десятичных чисел, выраженных в восьмеричной системе (табл. 1-1).
7
|
|
|
|
|
|
|
Т а б л и ц а 1-1 |
|
Десятичное |
изображение |
Восьмеричное |
полное |
Восьмеричное сокращенное |
||||
изображение |
изображение |
|||||||
|
|
|
||||||
|
0 |
|
|
0 - 8 ° |
|
0 |
||
|
3 |
|
|
3 - 8 ° |
|
3 |
||
|
7 |
|
|
7 - 8 ° |
|
7 |
||
|
8 |
|
1 - 8 1 + |
0 - 8° |
10 |
|||
|
15 |
|
1 - 8 1 + 7 - 8 ° |
17 |
||||
|
16 |
|
2 ■8 1 + |
0 • 8° |
20 |
|||
|
24 |
|
3 - 8 М - 0 - 8 ° |
30 |
||||
|
35 |
|
4 - 8 1 + 3 - 8 ° |
43 |
||||
|
64 |
|
1 • 8 2 + |
0 • 81 -(- 0 • 8° |
100 |
|||
125 |
|
1 - 8 2 + |
7 - 8 ! |
+ 5 - 8 ° |
175 |
|||
0 ,6 2 5 |
= |
1/16 |
0 • 8° + |
0 ■81 |
4 ■8—2 |
0 ,0 4 |
||
0 ,5 4 6 8 7 5 |
= |
3 5/64 |
0 - 8 ° + |
4 - 8 - 1 |
+ 3 - 8 - 2 |
0 , 4 3 |
||
3 ,1 8 7 5 |
= |
33/1 6 |
3 - 8 ° + |
1 -8—1 -j- 4• 8—2 |
3 ,1 4 |
|||
Троичная система счисления
В троичной системе счисления для записи всевозможных чисел
применяют три различные цифры: 0, 1,2. |
|
|
|||
Основание системы q |
3 записывается как |
10. Запись |
чисел, |
||
отличных от 0, 1, 2, |
производится комбинацией этих трех |
цифр. |
|||
В общем виде число в троичной системе записывается в виде |
|||||
jV3 — ап3 |
-f- ап__j3 |
+ . . . -j- а^З1+ |
aQ3° + |
|
|
+ |
а _ 13 " ‘+ |
■• • + а _ п3“ п, |
|
(1.9) |
|
где 3 — основание троичной системы, записанное в десятичной системе счисления;
а— коэффициент, равный любой из цифр 0, 1,2.
Всокращенном виде число в троичной системе записывается
как
|
N 3 = anan~l |
■■■ « Л - а-1 |
■■■ а-п |
(1Л0) |
|
|
|
|
|
Т а б л и ц а 1-2 |
|
Десятичное |
|
|
|
Троичное |
|
Троичное полное изображение |
сокращенное |
||||
изображение |
|||||
|
|
|
|
изображен ие |
|
2 |
|
2 - 3 ° |
|
2 |
|
3 |
|
1 - 3 1 - f 0 , 3 ° |
|
10 |
|
18 |
2 - 3 2 4 - 0 - 3 1 4 - 0 - 3 ° |
|
200 |
||
27 |
1 - 3 3 4 - 0 - 3 2 4 - 0 - 3 1 + 0 - 3 ° |
1000 |
|||
19/81 |
о - ^ 4 - о , з ~ 3 |
4 - 2 - з - 2 4 - о - з - 3 |
4 - ь з - 4 |
0,0 2 0 1 |
|
117/27 |
1-3° 4 - 1 -3 —1 -(- 2• 3—2 4 - 2 . 3 - 3 |
1 ,1 2 2 |
|||
8
Пользуясь соотношениями (1.9) и (1.10), составим таблицу не скольких десятичных чисел, выраженных в троичной системе
(табл. 1-2).
Двоичная система счисления
Вдвоичной системе счисления для изображения числа требуются всего лишь две цифры 0 и 1. Основание системы q — 2 записывается как 10, так как оно является единицей второго разряда.
Вобщем виде число в двоичной системе записывается в виде
N2 = a F + an_ xT - ' + . . . + ^ 2 * + |
|
|
'Ь ^ 02° + a_j2 |
1+ . . . -\-а_п2 ", |
(1.11) |
где 2 — основание системы, |
записанное в десятичной |
системе; |
а— коэффициент, принимающий только два значения: 0 или 1.
Всокращенном виде число в двоичной системе записывается
как
N 2 = a na n - i • ■ • a ia v f l _ , • • • а _ п . |
( 1 . 1 2 ) |
Пользуясь соотношениями (1.11) и (1.12), составим таблицу десятичных чисел, выраженных в двоичной системе (табл. 1-3).
|
|
|
Т а б л и ц а |
1-3 |
|
Десятичное |
Двоичное |
Десятичное |
Двоичное |
|
|
изображение |
изображение |
изображение |
изображение |
|
|
0 |
0 |
и |
1011 |
|
|
12 |
|
||||
1 |
1 |
1100 |
|
||
13 |
|
||||
2 |
10 |
1101 |
|
||
14 |
|
||||
3 |
11 |
1110 |
|
||
15 |
|
||||
4 |
100 |
1111 |
|
||
16 |
|
||||
5 |
101 |
10000 |
|
||
1/Z |
|
||||
6 |
п о |
0 ,1 |
|
||
1/4 |
|
||||
7 |
111 |
0 ,0 1 |
|
||
1/8 |
|
||||
8 |
1000 |
0 ,0 0 1 |
" |
||
1/16 |
|||||
9 |
1001 |
0 ,0 0 0 1 |
|
||
|
|
||||
10 |
1010 |
3 — |
11,1001 |
|
|
|
|
16 |
|
|
Двоично-десятичная система записи десятичных чисел
Если коэффициент а в десятичной системе счисления (1.4) и (1.5) записать в двоичной системе, то получим двоично-десятичную систему записи десятичных чисел.
Для кодирования десяти цифр от 0 до 9 требуется не менее че тырех двоичных разрядов. Самой распространенной является си стема, при которой каждая десятичная цифра изображается че тырьмя разрядами. Группа из четырех разрядов, предназначенных
9