Вводый курс цифровой электроники (К.Фрике, 2003)

Глава 2. Кодирование и системы счисления

Для каждого применения имеется более или менее подходящий код. Так для проведения операций над числами в компьютере ра­ ционально применять другой код, чем для передачи чисел по линии связи. В данной главе исследуются различия между отдельными ко­ дами и даны указания по их специфическому применению.

Комбинацию нескольких символов кода называют словом (word). В последующем мы ограничимся технически важным случаем, в ко­ тором все слова одного кода имеют одинаковую длину п. В коде Морзе этот случай не имеет места. Если в код входит множество символов ЛГ, то N'^ различных слов могут иметь длину п. Если ис­ пользуются все N"^ возможных слов одного кода, то в этом случае говорят о минимальном коде. Если используют менее чем N^ слов, то его называют избыточным кодом. Ниже можно найти описание наиболее употребительных кодов, полное описание можно получить из [8].

2.2. Двоичный код

Двоичный код является важнейшим кодом в цифровых системах, по­ скольку он является универсальным. Благодаря ограничению, в со­ ответствии с которым применяются только символы 1 и О, стано­ вится возможной обработка сигналов с помощью схемных элемен­ тов, работающих как переключатели. Двоичный код позволяет так­ же пользоваться арифметикой, аналогичной арифметике десятич­ ных систем. Двоичную систему счисления можно рассматривать как кодирование десятичной системы. Двоичное число состоит из сло­ ва, которое образовано символом С{ Е {0,1}. Символы Сг одного слова называют в цифровой технике битами. Слово z в двоичном представлении формируется путем последовательного присоедине­ ния отдельных битов, как это показано ниже:

ZB = Cn-lCn-2'"CiCo,C-iC-2-"C-m-\-2C-m+lC-m

(2.1)

Двоичное число имеет п разрядов перед запятой и т разрядов после запятой. Отдельным битам присвоены, в соответствии с их позицией г в слове, весовые коэффициенты 2\ На основе этого можно рассчитать эквивалентное десятичное число ZIQ:

^Сп-хТ-^ + Сп-22^-2 + ... + ci2i 4- со20 + c_i2-^ + ... + с _ ^ 2 - ^ (2.2)

2.2, Двоичный код

Рассмотрим в качестве примера двоичное число 10110,001^, ко­ торое как двоичное число отмечено символом В (binary). Оно ин­ терпретируется как:

g{z2) = 1 • 2 4 О • 2 4 1 • 2^+ 1 • 2 4 О • 2^+ О • 2"^ + 1 • 2 - 4 1 • 2"^ = -2rio = 22,375io

Двоичный (или дуальный) код обозначается как взвешенный код, поскольку стояш;ие дальше влево биты обладают более высокими ве­ совыми коэффициентами. Уравнение (2.2) можно рассматривать как правило, в соответствии с которым производится преобразование двоичных чисел в десятичные числа.

Преобразование десятичных чисел в двоичные числа является более сложным. Оно может быть описано различными алгоритмами для целочисленной и дробной частей. В приведенном выше примере с числом 22,375io алгоритм должен быть представлен следуюш;им образом:

• Вначале формируется целочисленная часть двоичного числа. Для этого целочисленная часть десятичного числа последова­ тельно делится на 2 и записывается остаток, пока не будет получен 0.

2 2 : 2 : 1	остаток 0	К	1
11 :2 = 5	остаток 1	«	ОS	«3
5 2 = 2	остаток 1	i		5
		S		^
2 2 == 1	остаток 0	t^	л	о
		о
1 2 = 0	остаток 1	5	ь	f4
			tr	W
		tr		о

Соответствующее числу 22ю двоичное число представляет со­ бой 101102.

•Второй шаг заключается в преобразовании дробной части де­ сятичного числа в дробную часть двоичного числа. Вначале дробная часть десятичного числа умножается на 2. Целочи­ сленная часть отделяется, она образует разряды двоичного чи­ сла с наименьшими значениями.

Процесс повторяется, как это показано ниже.

	0,375 2--= 0,75	+0	дробная часть
	0,75 2-.= 0,5	+1	двоичного числа
	0,5- 2- = 0	+1

Глава 2. Кодирование и системы счисления

В этом примере мы видим, что остаток равен 0. Но не обяза­ тельно так всегда бывает. В нормальном случае дробная часть экви­ валентного двоичного числа имеет бесконечно большое количество разрядов. В этом случае необходимо удовольствоваться определен­ ным числом разрядов после запятой и ограничить этим точность. В нашем случае 0,375io точно соответствует 0,0112.

На основе целочисленной и дробной частей получаем искомое двоичное число 10110,0112-

2.3.Арифметические операции с фиксированной запятой в двоичной системе

вданной главе описываются арифметические операции с числами с фиксированной запятой. Арифметические операции с фиксирован­ ной запятой означают, что в них запятая всегда стоит на фиксиро­ ванном месте. Нри этом место, на котором стоит запятая, ориенти­ руется на позицию в ЗУ, на которой находится число. В этом случае нет необходимости реализовать запятую в аппаратуре компьютера. Она существует только в голове программиста. Мы ограничиваемся постоянной длиной слова п, как это имеет место в компьютерах. На основе этого можно обсудить проблему переполнения допустимой области.

2.3.1.Целочисленное сложение в двоичной системе

Целочисленное сложение двух чисел А и В производится в двоичной системе точно так же, как и в десятичной системе — по разрядам. Как и там, в каждом разряде должны быть просуммированы обе двоичных цифры an и Ьп и перенос из предыдущего разряда Cn-i- При сложении возникают (табл. 2.2) новая сумма Sn и новый пе­

ренос Сп- В этой таблице дискретной линией разделены входные и выход­

ные величины. Например:

01111110

^00110101

- 1 0 1 1 0 0 1 1

перенос

1 1 1 1 1 0 0

Необходимо следить, чтобы в приведенном вьппе примере сумми­ ровались два числа длиной по 8 бит и чтобы итог тоже имел длину 8 бит, чтобы не было переполнения допустимой зоны.

2.3. Арифметические операции с фиксированной запятой

Таблица 2.2. Сложение в двоичной системе со слагаемыми атг,ЬпИ перено­ сом из предыдущего разряда Сп-\- Сумма равна Ьп 5 новый перенос Си-

^п	Ьп	С п - 1	Сп	Sn
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

2.3.2.Сложение чисел с фиксированной запятой

Вэтом случае, когда суммируются два числа с фиксированной за­ пятой, важным моментом является то, чтобы аналогично обычной процедуре в десятичной системе обе запятые стояли друг над дру­ гом. Так, при сложении двух чисел длиной в 8 бит запятая у обоих чисел должна стоять, например, на третьем месте.

Например:

0 1 1 0 0 , 0 1 0

0 0 1 1 0 , 1 1 1

= 1100,110 перенос 100 11,001

2.3.3. Представление с помощью обратного кода

Ц^ля того, чтобы иметь малые затраты на аппаратурную часть (hard­ ware) компьютера, были предприняты усилия по сведению к одно­ му алгоритму вычитания и сложения. Этого можно добиться, если применять двоичные цифры в их дополняющей форме. Различают единичное дополнение (обратный код, поразрядное дополнение) и двойное дополнение (точное дополнение).

Поразрядное дополнение формируется путем замены всех нулей на единицы и обратно. Следовательно, поразрядным дополнением (one's complement) 0001 является 1110. Ниже поразрядное дополне­ ние двоичного числа А обозначено -^А. Очевидно, что при предста­ влении п-битового слова имеем:

.А + Л - 2^ - 1

(2.3)

24 Глава 2. Кодирование и системы счисления

Например, при представлении 8-битового слова имеем:

10110011 + 01001100 = 11111111 - 2 ^ - 1

Можно так преобразовать уравнение (2.3), чтобы получить фор­ мулу р^ля расчета поразрядного дополнения:

-.А = 2^ - 1 - А

(2.4)

2.3.4.Представление с помощью двойного дополнения (точное дополнение, two's complement)

Точное дополнение Ак2 образуется из поразрядного дополнения -^А путем прибавления 1:

Ак2 = --АЛ-1

(2.5)

Следовательно, с учетом (2.4) будет справедливо:

Ак2 ^Т -А

(2.6)

Мы видим, что в данном представлении содержится «—А», благо­ даря чему оно удобно для проведения вычитания. Учтем также, что Т^ в двоичном представлении имеет п Л-\ разрядов. Ниже пример точного дополнения J\A^ 10101100:

Ак2 - - Л + 1 = 01010011 + 1 - 01010100

Представление 4-битовых двоичных слов в круговой форме, при­ веденное на рис. 2.1, позволяет показать числовой диапазон. Соот­ ветствующее данным значениям набольшее представляемое положи­ тельное число равно 7/), соответствующее данным значениям наи­ большее отрицательное число равно —8^). Следовательно, числовой диапазон построен несимметрично, поскольку отрицательное число занимает больше места, чем положительное. Наибольшее и наимень­ шее представляемые числа можно выразить как:

^тах ^^ ^

\^' * )

На рис. 2.1 можно видеть, что малые числа, сформированные на основе точного дополнения, содержат много ведущих единиц, ко­ гда они отрицательны, и содержат много ведущих нулей, когда они

2.3. Арифметические операции с фиксированной запятой

положительны. Соответствующие данным значениям большие чи­ сла, сформированные на основе точного дополнения, содержат да­ леко влево отстоящий нуль, когда они отрицательны, и далеко вле­ во отстоящий нуль, когда они положительны. Их собственным точ­ ным дополнением является число 1000^ (—8/)). Важно установить, что при представлении на основе точного дополнения имеем толь­ ко один 0. Это облегчает запрос, равен ли результат 0. Напротив, при представлении на основе поразрядного дополнения имеют ме­ сто двоичное число 0000^, соответствующее -i-Oo и двоичное число 1111^, соответствующее —0/^.

0000

1111 _ - # - - _ 0001

0010

2

1100 1 ^

л^от

1001	•	0111
	1000

Рис . 2.1. Представление 4-битовых слов с помощью 4-битового дополнения.

2.3.5.Вычитание при представлении с помощью точного дополнения

Пусть должны были вычтены одно из другого два положительных двоичных числа А и В, При условии применения точного дополне­ ния в соответствии с уравнением (2.6) вычитание можно провести следующим образом:

А-В = А-В + Вк2-Вк2 = А-В-{-Вк2-{2''-В)

(2.9)

Раскрытие скобок в правой части уравнения дает:

А-В = А + Вк2-2''

(2.10)

Что означает вычитание 2'^? Поясним это на примере операции вычитания 7—3 = 4 в 4-битовой двоичной системе. Сумма двоичного

Глава 2. Кодирование и системы счисления

эквивалента числа 7 и дополнение двоичного эквивалента числа 3 равняется:

, 0 1 1 1	7io
1101	- Зю

-1 0 1 0 0

-1 0 0 0 0

=0100 tio

Вычитание числа 10000^, проведенное в соответствии с уравне­ нием (2.10), дает правильный результат 0100^. Это может произой­ ти в 4-битовом компьютере просто потому, что высший результат игнорируется. Итак, при проведении вычитания с помош;ью точно­ го дополнения нет необходимости учитывать высший перенос С4. Но необходимо соблюдать осторожность в связи с переполнением числового диапазона. Исследуем это ниже.

2.3.6. Переполнение числового диапазона

Исходя из вышесказанного возникает необходимость рассмотрения проблемы переполнения числового диапазона (overflow) в связи с представлением на основе точного дополнения. Переполнение число­ вого диапазона может происходить только в двух случаях. А имен­ но, когда суммируются два положительных числа либо суммируют­ ся два отрицательных числа. В связи с этим рассмотрим несколько примеров, относяш;ихся к 4-битовому представлению.

•Пример переполнения числового диапазона при сложении двух положительных чисел:

0 1 0 1	5io
0 1 0 1	5io
= 1010	-610

Очевидно, что результат является неправильным. Ошибка воз­ никает за счет переноса 3-го разряда на место 4-го разряда, что приводит к симуляции отрицательного числа. Этот пере­ нос сз в представлении, используюш;ем п бит, обычно обозна­ чается как Сп-1- Перенос с^ (в обш;ем случае с^) из разряда 4 в разряд 5 называется Carry {Су). В этом примере данный перенос не имеет места.

2,3. Арифметические операции с фиксированной запятой

•Пример переполнения численного диапазона при сложении от­ рицательных чисел:

+	1011	-5io
	1011	-5io
- ( 1 ) 0 1 1 0		6io

В этом примере также появляется неправильный результат. Имел место не перенос Cn-i из разряда 3 в разряд 4, а перенос Сп ИЗ разряда 4 в разряд 5.

•Для сравнения проведем сложение двух отрицательных чисел без переполнения числового диапазона:

[phone] —3io

=(1)1100 -4io- l i o

Имели место переносы Сп и c^-i.

Сведем эти результаты вместе с другими, здесь не показанны­ ми случаями, в таблицу. На основе результатов, представленных в табл. 2.3, для двух двоичных чисел Л и Б, которые лежат в чи­ словом диапазоне, определяемом п-битовом представлением на базе точного дополнения, можно установить перенос переполнения при сложении.

Таблица 2.3. Перенос переполнения при сложении в случае п-битового представления на основе точного дополнения.

	Правильный результат		Перенос переполнения
А-\-В	Сп = 0, C n - l = 0		Сп ~ 0, Сп - 1 = 1
А-В	Сп =	Сп—\	невозможен
-А-В	Сп = 1,	Сп - 1 = 1	Сп ^^ -L) Сп — 1 ^^^ vJ

Следовательно, правильный результат имеет место тогда, когда Сп = c^i-i, неправильный результат — когда Сп ф Cn-i-

2.3.7. Умножение

Умножение выполняется так же, как и для десятичной системы. Рас­ смотрим пример умножения на основе двоичной системы для чисел

Глава 2. Кодирование и системы счисления

IOD X UD = IIOD:

1010

""ion

1010

1 0 1 0

10 1 О

11 1 ОНО

Наибольший из ожидаемых результатов Е умножения двух п- битовых слов представляет собой:

£; = (2^ - 1) . {2'' -I) = 2^"" - 2''"'^ + 1 < г^"" - 1

Следовательно, результат умножения двух п-битовых чисел име­ ет длину 2п бит. Но он меньше, чем максимальное представляемое с помош;ью 2п бит двоичное число 2^^ — 1.

Сказанное выше справедливо для умножения положительных чи­ сел. При вычислениях с использованием представления на основе точного дополнения могут быть применены специальные алгорит­ мы [20], или следует числа на основе точного дополнения перед умно­ жением преобразовать обратно в исходные значения, а результат перевести в соответствии со знаком в желаемое представление.

При умножении чисел с фиксированной запятой вначале числа умножаются без учета запятой. Затем запятая вводится в соответ­ ствии с правилом: умножение двух чисел с п и А; разрядами после запятой даст произведение с п -f /с разрядами после запятой.

2.3.8. Деление

Для деления можно использовать тот же самый алгоритм, что и в десятичной системе. Продемонстрируем это на примере уравнения lOi^ : 2г> = 5D:

1 0	1 0	1	0	0	1 0
~ 1 0			1	0	1

0 1 0

10

о

Соответственно при делении числа с п разрядами после запятой на число с к разрядами после запятой частное имеет п — к разрядов

2.4' Шестнадцатеричный код 29

после запятой. Так в соответствии с верхним примером имеем:

10,10-101,1 = 1101,110

Деление чисел с точным дополнением также можно свести к умножению и сложению [20].

2.4. Шестнадцатеричный код

На практике наряду с двоичным кодом внедрился шестнадцатерич­ ный код, поскольку он обеспечивает лучшее обозрение длинных дво­ ичных чисел. Шестнадцать шестнадцатеричных цифр определены в табл. 2.4. Шестнадцатеричные цифры больше девяти представлены буквами A-F. Для преобразования двоичных в шестнадцатеричные числа объединяют по четыре цифры двоичного числа, которые ин­ терпретируются как шестнадцатеричный разряд. Благодаря этому шестнадцатеричное число занимает только четверть разрядов, за­ нимаемых двоичным числом одинаковой величины.

Например:

ОНО 1100 1111

G С

Итак, справедливо выражение 0110011001III2 = GCFi^.

	Таблица 2.4. Шестнадцатеричные числа.
	десятичные	двоичные	шестнадца­	десятичные	двоичные	шестнадца­
			теричные			теричные
	0	0000	0	8	1000	8
	1	0001	1	9	1001	9
	2	0010	2	10	1010	А
	3	ООП	3	11	1011	В
	4	0100	4	12	1100	С
	5	0101	5	13	1101	D
	6	ОНО	6	14	1110	Е
	7	0111	7	15	1111	F

В качестве обозначения шестнадцатеричного числа использует­ ся индекс Н, Преобразование шестнадцатеричного числа в десятич­ ное число и обратно проще всего производить через соответствую­ щее двоичное число. Также возможно производить преобразование с помощью алгоритма, как при преобразовании двоичного числа в