Файл: Кодирования.pdf

2.2. Перевод чисел между системами счисления
2.2.1. Перевод двоичного числа в десятичное
Перевод двоичного числа в десятичное производится по классической схеме сложения степеней двойки с коэффициентами, которыми являются со- ответствующие цифры этого двоичного числа.
Процесс перевода двоичного числа в десятичное рассмотрим на приме- ре двоичного числа
100111001011 2
Для простоты распишем показатели степени
11 1
10 0
9 0
8 1
7 1
6 1
5 0
4 0
3 1
2 0
1 1
0 1
2
Таким образом, для получения десятичного числа можно написать
1·2 11
+0·2 10
+0·2 9
+1·2 8
+1·2 7
+1·2 6
+0·2 5
+0·2 4
+1·2 3
+0·2 2
+1·2 1
+1·2 0
Убрав степени с коэффициентом 0, получим
1 · 2 11
+ 1 · 2 8
+ 1 · 2 7
+ 1 · 2 6
+ 1 · 2 3
+ 1 · 2 1
+ 1 · 2 0
Уберем коэффициенты и раскроем степени
2 11
+ 2 8
+ 2 7
+ 2 6
+ 2 3
+ 2 1
+ 2 0
= 2048 + 256 + 128 + 64 + 8 + 2 + 1 = 2507.
Таким образом
100111001011 2
= 2507 10 2.2.2. Перевод десятичного числа в двоичное
Для перевода десятичного числа в двоичное используется процедура последовательного деления десятичного числа на два с накоплением остатка.
Для примера рассмотрим обратный перевод числа 2507 10
, полученного в примере, приведенном в предыдущем подпункте.
13

2507 2 1 1253 2 1 626 2 0 313 2 1 156 2 0 78 2 0 39 2 1 19 2
1 9 2
1 4 2
0 2 2 0 1
Результат записывается, начиная с конца. Таким образом
2507 10
= 100111001011 2
При переводе небольших десятичных чисел иногда удобнее использо- вать разложение в ряд степеней двойки (табл.
2.1
), обратно рассмотренной в пп.
2.2.1
процедуре.
Например, число 292 10
можно представить как
292 10
= 256 + 32 + 4 = 2 8
+ 2 5
+ 2 2
= 100100100 2
Вначале берем ближайшую к заданному десятичному числу степень двойки —
в примере это число 256 = 2 8
. Теперь считаем разность 292 − 256 = 36. Далее снова берем ближайшую степень двойки 32 = 2 5
. Остается 4 = 2 2
. В итоге получаем искомое число в двоичном виде.
2.2.3. Перевод между двоичной и восьмеричной системами счисления
Перевод целых чисел из двоичной системы в восьмеричную и обратно основан на том, что каждому восьмеричному числу ставится в соответствие его значение в двоичной системе счисления, выраженное в виде блока из трех двоичных цифр — двоичная триада [
5
]. Соответствия между восьмеричны- ми цифрами и двоичными числами показаны в табл.
2.3
Таблица 2.3
Соответствия между цифрами восьмеричной системы счисления и двоичными числами (в виде триад)
Восьмеричные
Двоичные
Восьмеричные
Двоичные цифры триады цифры триады
0 000 4
100 14

Окончание табл. 2.3
Соответствия между цифрами восьмеричной системы счисления и двоичными числами (в виде триад)
Восьмеричные
Двоичные
Восьмеричные
Двоичные цифры триады цифры триады
1 001 5
101 2
010 6
110 3
011 7
111
При переводе двоичного целого числа в восьмеричную систему счисле- ния его необходимо разбить на триады, начиная с младшего разряда, а затем вместо каждой триады записать соответствующую ей восьмеричную цифру
[
5
]. Для примера рассмотрим перевод двоичного числа 1001001000011 2
:
1001001000011 2
⇒ 001.001.001.000.011 ⇒ 1.1.1.0.3 ⇒ 11103 8
Заметим, что при разбиении двоичного числа на триады пришлось дополнить его нулями слева.
При переводе целого восьмеричного числа в двоичную систему счисле- ния достаточно вместо каждой восьмеричной цифры записать соответству- ющую ей двоичную триаду [
5
]. Для примера рассмотрим обратный перевод восьмеричного числа 11103 8
:
11103 8
⇒ 001.001.001.000.011 ⇒ 1001001000011 2
Незначащие нули в левой части полученного двоичного числа были удалены.
2.2.4. Перевод между двоичной и шестнадцатеричной системами счисления
Перевод целых чисел из двоичной системы в шестнадцатеричную и об- ратно аналогичен переводу между двоичной и восьмеричной системами. Каж- дой шестнадцатеричной цифре ставится в соответствие ее значение в дво- ичной системе счисления, выраженное в виде блока из четырех двоичных цифр — двоичная тетрада [
5
]. Соответствия между восьмеричными циф- рами и двоичными числами показаны в табл.
2.4
Таблица 2.4
Соответствия между цифрами шестнадцатеричной системы счисления и двоичными числами (в виде тетрад)
Шестнадцатеричные
Двоичные
Шестнадцатеричные
Двоичные цифры тетрады цифры тетрады
0 0000 8
1000 1
0001 9
1001 2
0010
A
1010 15

Окончание табл. 2.4
Соответствия между цифрами шестнадцатеричной системы счисления и двоичными числами (в виде тетрад)
Шестнадцатеричные
Двоичные
Шестнадцатеричные
Двоичные цифры тетрады цифры тетрады
3 0011
B
1011 4
0100
C
1100 5
0101
D
1101 6
0110
E
1110 7
0111
F
1111
При переводе двоичного целого числа в шестнадцатеричную систему счисления его необходимо разбить на тетрады, начиная с младшего разря- да, а затем вместо каждой тетрады записать соответствующую ей шестна- дцатеричную цифру [
5
]. Для примера рассмотрим перевод двоичного числа
1001001001011 2
:
1001001001011 2
⇒ 0001.0010.0100.1011 ⇒ 1.2.4.B ⇒ 124B
16
Заметим, что при разбиении двоичного числа на тетрады пришлось дополнить его нулями слева.
При переводе целого шестнадцатеричного числа в двоичную систему счисления достаточно вместо каждой шестнадцатеричной цифры записать со- ответствующую ей двоичную тетраду [
5
]. Для примера рассмотрим обратный перевод шестнадцатеричного числа 124B
16
:
124B
16
⇒ 0001.0010.0100.1011 ⇒ 1001001001011 2
Незначащие нули в левой части полученного двоичного числа были удалены.
2.2.5. Перевод между десятичной и двоично-десятичной системами счисления
Перевод целых чисел между десятичной и двоично-десятичной систе- мами счисления аналогичен переводу между двоичной и шестнадцатеричной системами. Каждой десятичной цифре ставится в соответствие ее значение в двоичной системе счисления, выраженное в виде двоичной тетрады [
5
]. Со- ответствия между десятичными цифрами и двоичными тетрадами показаны в табл.
2.5 16

Таблица 2.5
Соответствия между цифрами десятичной системы счисления и двоичными тетрадами
Десятичные
Двоичные
Десятичные
Двоичные цифры тетрады цифры тетрады
0 0000 5
0101 1
0001 6
0110 2
0010 7
0111 3
0011 8
1000 4
0100 9
1001
При переводе целого десятичного числа в двоично-десятичную систему счисления достаточно вместо каждой десятичной цифры записать соответ- ствующую ей двоичную тетраду [
5
]. Для примера рассмотрим перевод деся- тичного числа 124 10
:
124 10
⇒ 0001.0010.0100 ⇒ 000100100100 2−10
Обратный перевод из двоично-десятичной системы в десятичную пол- ностью аналогичен переводу из двоичной в шестнадцатеричную систему.
2.3. Операции над двоичными числами
К основным операциям над двоичными числами относятся логические операции инверсия, конъюнкция и дизъюнкция и арифметические операции сложение и умножение, а также сложение по модулю 2, соответствующее логической операции «Исключающее ИЛИ».
Инверсия является унарной операцией, т. е. осуществляется над одним операндом. Прочие операции являются бинарными, т. е. осуществляются над двумя операндами.
Инверсия, конъюнкция и дизъюнкция являются основными логически- ми операциями. Этим операциям соответствуют простейшие логические эле- менты «НЕ» (инвертор), «И» и «ИЛИ», на основе которых строятся любые цифровые микросхемы. Для описания логических элементов используются таблицы истинности, содержащие совокупность всех возможных комбина- ций логических сигналов на входе цифрового устройства и значений выход- ных сигналов для каждой комбинации. К основным логическим элементам также относят элемент «Исключающее ИЛИ», буфер памяти, а также обрат- ные элементы «И–НЕ», «ИЛИ–НЕ», «Исключающее ИЛИ–НЕ».
Основные логические элементы имеют стандартные условно- графические обозначения. Существует несколько стандартов обозначения.
17

1. Стандарт Международной электротехнической комиссии (МЭК,
International Electrotechnical Commission, IEC), аналогичный британскому стандарту BS3939.
2. Американский стандарт MIL/ANSI.
3. Обозначения, согласно книге A. Croft, R. Davidson and M. Hargreaves
Engineering Mathematics, 1992. Эти обозначения часто называют CDH. Эти обозначения аналогичны стандарту MIL/ANSI за исключением обозначений для элементов «И»/«И–НЕ».
4. ГОСТ 2.743-91 «Единая система конструкторской документации.
Обозначения условные графические в схемах. Элементы цифровой техники»
(ЕСКД). Этот стандарт во многом аналогичен стандарту IEC.
Для основных логических элементов в пособии будут приведены все варианты обозначений. Основным вариантом, который будет использовать- ся для более сложных схем, как наиболее употребимый на практике, выбран стандарт MIL/ANSI.
2.3.1. Инверсия
Инверсия (отрицание, дополнение, операция «НЕ», NOT) осуществля- ет смену значения операнда на противоположное. В том случае, если речь идет об инверсии двоичного числа из нескольких разрядов, эта операция осу- ществляется поразрядно (побитово), т. е. инвертируется каждый разряд (бит)
числа.
В тексте операция инверсии может обозначаться различными способа- ми, как показано в формуле:
a
;
!a;
¬a.
(2.1)
В настоящем пособии будем использовать первое обозначение. Например
01110010 = 10001101.
Таблица истинности инвертора показана в табл.
2.6
Таблица 2.6
Таблица истинности инвертора a
a
0 1
1 0
На рис.
2.1
представлены основные условно-графические обозначения инвертора.
18

1
(а)
(б)
Рис. 2.1. Условно-графические обозначения инвертора:
(а)
по стандартам IEC и ЕСКД;
(б)
по стандартам MIL/ANSI и CDH
2.3.2. Конъюнкция
Конъюнкция (логическое умножение, операция «И», AND) является бинарной операцией, возвращающей 1, только когда оба операнда равны 1.
При работе с двоичными числами из нескольких разрядов, эта операция осу- ществляется поразрядно. Поразрядные операции как правило осуществляют- ся с операндами равной длины. В случае разной длины операндов, тот, кото- рый имеет меньшую длину, дополняется нулями в старших степенях. Напри- мер, при необходимости осуществить поразрядное логическое умножение чи- сел c = 110010 2
и d = 1010 2
, число d следует представить как d = 001010 2
В записи операция логического умножения может обозначаться различ- ными способами, как показано в формуле:
a
∧ b;
a
∩ b;
a
&b.
(2.2)
В настоящем пособии будем использовать первое обозначение.
Далее приведем таблицу логического умножения (табл.
2.7
) и таблицу истинности соответствующего ему логического элемента «И» (табл.
2.8
).
Таблица 2.7
Таблица логического умножения
∧
0 1
0 0
0 1
0 1
Таблица 2.8
Таблица истинности элемента «И»
a b
a
∧ b
0 0
0 0
1 0
1 0
0 1
1 1
На рис.
2.2
представлены основные условно-графические обозначения логического элемента «И».
&
(а)
(б)
(в)
Рис. 2.2. Условно-графические обозначения логического элемента «И»:
(а)
по стандартам IEC и ЕСКД;
(б)
по стандарту MIL/ANSI;
(в)
по стандарту CDH
19

Рассмотрим операцию поразрядного логического умножения на приме- ре двух двоичных чисел a и b:
a
= 101101 2
;
b
= 100110 2
∧
1 0 1 1 0 1 1 0 0 1 1 0 1 0 0 1 0 0
Таким образом, a ∧ b = 101101 2
∧ 100110 2
= 100100 2
2.3.3. Дизъюнкция
Дизъюнкция (логическое сложение, операция «ИЛИ», OR) является бинарной операцией, возвращающей 1, когда хотя бы один операнд равен 1.
При работе с двоичными числами из нескольких разрядов, эта операция осу- ществляется поразрядно.
В записи операция логического сложения может обозначаться различ- ными способами:
a
∨ b;
a
∪ b;
a
|b.
(2.3)
В настоящем пособии будем использовать первое обозначение.
Далее приведем таблицу логического сложения (табл.
2.9
) и таблицу ис- тинности соответствующего ему логического элемента «ИЛИ» (табл.
2.10
).
Таблица 2.9
Таблица логического сложения
∨
0 1
0 0
1 1
1 1
Таблица 2.10
Таблица истинности элемента «ИЛИ»
a b
a
∨ b
0 0
0 0
1 1
1 0
1 1
1 1
На рис.
2.3
представлены основные условно-графические обозначения логического элемента «ИЛИ».
≥1
(а)
(б)
Рис. 2.3. Условно-графические обозначения логического элемента «ИЛИ»:
(а)
по стандартам IEC и ЕСКД;
(б)
по стандартам MIL/ANSI и CDH
Рассмотрим операцию поразрядного логического сложения на примере двух двоичных чисел a и b:
a
∨ b = 101101 2
∨ 100110 2
= 101111 2
20

∨
1 0 1 1 0 1 1 0 0 1 1 0 1 0 1 1 1 1 2.3.4. Сложение по модулю 2
Сложение по модулю 2 (операция «Исключающее ИЛИ», XOR) яв- ляется бинарной операцией, возвращающей 1, когда один операнд равен 0, а второй 1, и возвращающей 0 при равенстве операндов. Фактически, этот сум- матор выполняет суммирование без учета переноса. При работе с двоичными числами из нескольких разрядов, эта операция осуществляется поразрядно.
В записи операция сложения по модулю 2 обычно обозначается спосо- бом, показанным в формуле:
a
⊕ b.
(2.4)
Далее приведем таблицу сложения по модулю 2 (табл.
2.11
) и таблицу истинности сумматора по модулю 2 (табл.
2.12
).
Таблица 2.11
Таблица сложения по модулю 2
⊕
0 1
0 0
1 1
1 0
Таблица 2.12
Таблица истинности сумматора по модулю 2
a b
a
⊕ b
0 0
0 0
1 1
1 0
1 1
1 0
Принципиальная схема сумматора по модулю 2 показана на рис.
2.4 1
1
&
&
≥1
a
⊕ b a
b
(а)
a
⊕ b a
b
(б)
Рис. 2.4. Принципиальная схема сумматора по модулю 2:
(а)
по стандартам IEC и ЕСКД;
(б)
по стандарту MIL/ANSI
На рис.
2.5
представлены основные условно-графические обозначения сумматора по модулю 2.
21

=1
(а)
(б)
Рис. 2.5. Условно-графические обозначения сумматора по модулю 2:
(а)
по стандартам IEC и ЕСКД;
(б)
по стандартам MIL/ANSI и CDH
Рассмотрим операцию поразрядного сложения по модулю 2 на примере двух двоичных чисел a и b:
a
⊕ b = 101101 2
⊕ 100110 2
= 001011 2
⊕
1 0 1 1 0 1 1 0 0 1 1 0 0 0 1 0 1 1 2.3.5. Сложение
В отличие от сложения по модулю 2 операция двоичного арифметиче- ского сложения производится с переносом в следующий двоичный разряд. То есть, 1 2
+ 1 2
= 10 2
. В записи для обозначения двоичного арифметического сложения используется обычный символ сложения «+».
Поскольку необходимо учитывать перенос, схема построения двоично- го сумматора усложняется по сравнению с сумматором по модулю 2. Выде- ляют два типа схем:
1) полусумматор, который формирует перенос в следующий разряд,
но не может учитывать перенос из предыдущего разряда;
2) полный сумматор, который формирует перенос в следующий раз- ряд, и учитывает перенос из предыдущего разряда.
Далее приведем таблицу двоичного сложения (табл.
2.13
) и таблицу ис- тинности одноразрядного полусумматора (табл.
2.14
), в которой S обозначает сумму, а PO — перенос.
Таблица 2.13
Таблица двоичного сложения
+
0 1
0 0
1 1
1 10
Таблица 2.14
Таблица истинности одноразрядного полусумматора
A
B
S
PO
0 0
0 0
0 1
1 0
1 0
1 0
1 1
0 1
Принципиальная схема, реализующая таблицу истинности одноразряд- ного полусумматора, показана на рис.
2.6 22

1 1
&
&
≥1
&
S
A
B
PO
(а)
S
A
B
PO
(б)
Рис. 2.6. Принципиальная схема одноразрядного полусумматора:
(а)
по стандартам IEC и ЕСКД;
(б)
по стандарту MIL/ANSI
Анализируя схему полусумматора на рис.
2.6
, можно увидеть, что часть схемы, отвечающая за получение суммы, соответствует схеме сумматора по модулю 2, следовательно, схему полусумматора можно преобразовать так,
как показано на рис.
2.7
=1
&
A
B
S
PO
(а)
A
B
S
PO
(б)
Рис. 2.7. Принципиальная схема полусумматора на основе сумматора по модулю 2:
(а)
по стандартам IEC и ЕСКД;
(б)
по стандарту MIL/ANSI
На рис.
2.8
приведено условно-графическое обозначение одноразрядно- го полусумматора.
HS
A
B
S
PO
Рис. 2.8. Условно-графическое обозначение одноразрядного полусумматора
Таблица истинности полного двоичного одноразрядного сумматора по- казана в табл.
2.15
, где S обозначает сумму, PI — перенос на входе, а PO —
перенос на выходе.
23

Таблица 2.15
Таблица истинности полного двоичного одноразрядного сумматора
PI
A
B
S
PO
0 0
0 0
0 0
0 1
1 0
0 1
0 1
0 0
1 1
0 1
1 0
0 1
0 1
0 1
0 1
1 1
0 0
1 1
1 1
1 1
Принципиальная схема полного двоичного одноразрядного сумматора на основе сумматоров по модулю 2 показана на рис.
2.9
. Можно видеть, что эта схема состоит из двух полусумматоров и схемы ИЛИ, объединяющей сиг- налы переносов от полусумматоров.
=1
&
A
B
PI
=1
&
≥1
PO
S
(а)
A
B
PI
PO
S
(б)
Рис. 2.9. Принципиальная схема полного двоичного одноразрядного сумматора на основе сумматоров по модулю 2:
(а)
по стандартам IEC и ЕСКД;
(б)
по стандарту MIL/ANSI
На рис.
2.10
приведено условно-графическое обозначение полного дво- ичного одноразрядного сумматора.
SM
PI
A
B
S
PO
Рис. 2.10. Условно-графическое обозначение полного двоичного одноразрядного сумматора
Для того чтобы получить многоразрядный сумматор, достаточно со- единить входы и выходы переносов соответствующих двоичных разрядов. На практике одноразрядные сумматоры практически никогда не использовались,
так как почти сразу же были выпущены микросхемы многоразрядных сумма- торов. На рис.
2.11
приведены принципиальная схема и условно-графическое обозначение полного двоичного четырехразрядного сумматора.
24

SM
PI
A
B
S
PO
SM
PI
A
B
S
PO
SM
PI
A
B
S
PO
SM
PI
A
B
S
PO
PI
A
1
B
1
S
1
A
2
B
2
S
2
A
3
B
3
S
3
A
4
B
4
S
4
PO
(а)
SM
PI
A0
A1
A2
A3
B0
B1
B2
B3
S0
S1
S2
S3
PO
(б)
Рис. 2.11. Полный двоичный четырехразрядный сумматор:
(а)
принципиальная схема;
(б)
условно-графическое обозначение
При ручных расчетах арифметическое двоичное сложение a и b легко осуществляется методом сложения «в столбик»:
+
1 1
0 1
1 1 0 1 = 45 10
= a
1 0 0 1 1 0 = 38 10
= b
1 0 1 0 0 1 1 = 83 10 2.3.6. Умножение
Операция арифметического умножения обычно рассматривается как многоразрядная, поскольку одноразрядное умножение полностью соответ- ствует логическому умножению (конъюнкции), а одноразрядный умножитель,
соответственно, схеме «И».
При ручных расчетах умножение, как и сложение, удобно вычисляется
«в столбик». Рассмотрим на примере b · a:
×
1 0 0 1 1 0 = 38 10
= b
1 0 1 1 0 1 = 45 10
= a
0 0 0 0 0 0 1
0 1 1 0 1 1
0 1 1 0 1 1 0 1 1 0
1 1 1 0 1 0
1 0 1 1 1 0 = 1710 10
Из этого расчета видно, что умножение двух двоичных чисел представ- ляет собой последовательное суммирование первого множителя с ним же, но сдвинутым согласно позициям единиц во втором множителе.
25