Системы счисления

 

4.3.2  Двоичное вычитание

 

Вычитание в двоичной системе  выполняется аналогично вычитанию  в десятичной системе счисления. При необходимости, когда в некотором  разряде приходится вычитать единицу  из нуля, занимается единица из следующего старшего разряда. Если в следующем  разряде нуль, то заем делается в  ближайшем старшем разряде, в  котором стоит единица. При этом следует понимать, что занимаемая единица равна двум единицам данного  разряда, т. е. вычитание выполняется  по следующему правилу:

 

Пример 4.7  Вычитание двоичных чисел и

 

–	11010,	1011
	1101,	01111
	1101,	00111

 

Конечно, математически вычитание  выполнить несложно. Однако, если поступать таким образом, то к примеру в ЭВМ придется для выполнения сложения и вычитания иметь два блока: сумматор и вычитатель. Поэтому поступают следующим образом: вычитание можно представить как сложение положительного и отрицательного чисел, необходимо только подходящее представление для отрицательного числа.

Рассмотрим четырехразрядный десятичный счетчик, какие в автомобиле отсчитывают пройденный путь. Пусть  он показывает число 2, если вращать  его в обратном направлении, то сначала  появится 1, затем 0, после 0 появится число 9999. Сложим, к примеру, 6 с этим числом:

+	6
	9999
	10005

           

Если пренебречь единицей переноса и считать 9999 аналогом –1, то получим верный результат: .

Число 9999 называется десятичным дополнением числа 1. Таким образом,  в десятичной системе счисления отрицательные числа могут быть представлены в форме десятичного дополнения, а знак минус можно опустить.     

Двоичное   дополнение числа определяется как то число, которое будучи прибавлено к первоначальному числу, даст только единицу переноса в старшем разряде.

 

Пример 4.8  Двоичное дополнение числа

 

+	010101111	– число
	101010001	– двоичное дополнение
	1000000000	– сумма
­ – единица переноса

 

Для получения двоичного  дополнения необходимо:

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

010101111	– число
101010000	– обратный код

• прибавить к обратному коду единицу, образовав таким образом дополнительный           код:

+	101010000	– обратный код
	1
	101010001	– дополнительный код

 

Пример 4.9  Вычитание в дополнительном коде

 

 – обратный код,

 – дополнительный код.

100101₂=5₁₀ (верно).

 

4.3.3  Двоичное умножение

 

Умножение двух двоичных чисел  выполняется так же, как и умножение  десятичных. Сначала получаются частичные  произведения и затем их суммируют  с учетом веса соответствующего разряда  множителя.

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

Умножение производится, начиная  с младшего или старшего разряда  множителя, что и определяет направление  сдвига. Если сомножители имеют дробные  части, то положение запятой в  произведении определяется по тем же правилам, что и для десятичных чисел.

Пример 4.10  Умножение двоичных чисел и

 

 

4.3.4  Двоичное деление

 

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

 

Пример 4.11  Деление двоичных чисел

 

1) 18:2			2) 14:4
10010	10		1110	100
10	1001=(9)10		100	11,1=(3,5)10
00			110
00			100
001			100
000			100
10			0
10
00

 

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

2.5 Способы построения  двоичных кодов

Начиная с конца 60-х годов, компьютеры все больше использовать для обработки текстовой информации и в настоящее время большая часть компьютеров в мире занято именно обработкой текстовой информации.

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

Но способов построения таких  кодов очень много, рассмотрим некоторые  из них.

 

Алфавитное неравномерное  двоичное кодирование

При алфавитном способе двоичного  кодирования символы некоторого первичного алфавита (например, русского) кодируются комбинациями символов двоичного  алфавита (т.е. 0 и 1), причем, длина кодов  и, соответственно, длительность передачи отдельного кода, могут различаться. Оптимизировать кодирование можно  за счет суммарной длительности сообщения.

Суммарная длительность сообщения  будет меньше, если применить следующий  подход: чем буква первичного алфавита, встречается чаще, то присваиваем  ей более короткой по длине код. Следовательно, коды букв, вероятность появления  которых в сообщении выше, следует  строить из возможно меньшего числа  элементарных сигналов.

Возможны различные варианты двоичного кодирования, однако, не все  они будут пригодны для практического  использования - важно, чтобы закодированное сообщение могло быть однозначно декодировано, т.е. чтобы в последовательности 0 и 1, которая представляет собой многобуквенное кодированное сообщение, всегда можно было бы различить обозначения отдельных букв.

Рассмотрим пример построения двоичного кода для символов русского алфавита:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Неравномерный код  с разделителями

Для того что бы было проще  декодировать сообщения был придуман код с разделителями.

Проще всего достичь однозначного декодирования, если коды будут разграничены разделителем - некоторой постоянной комбинацией двоичных знаков. Условимся, что разделителем отдельных кодов букв будет последовательность 00 (признак конца знака), а разделителем слов - 000 (признак конца слова - пробел). Довольно очевидными оказываются следующие правила построения кодов:

— код признака конца  знака может быть включен в  код буквы, поскольку не существует отдельно (т.е. кода всех букв будут  заканчиваться 00);

— коды букв не должны содержать  двух и более нулей подряд в

середине (иначе они будут  восприниматься как конец знака);

— код буквы (кроме пробела) всегда должен начинаться с 1;

— разделителю слов (000) всегда предшествует признак конца знака;

при этом реализуется последовательность 00000 (т.е. если в конце кода встречается комбинация ...000 или ...0000, они не воспринимаются как разделитель слов); следовательно, коды букв могут оканчиваться на 0 или 00 (до признака конца знака).

Длительность передачи каждого  отдельного кода 4 очевидно, может быть найдена: t_i = k_i • τ, где k_i - количество элементарных сигналов (бит) в коде символа L.

 

Алфавитное неравномерное  двоичное кодирование. Префиксный код

Рассмотрев один из вариантов  двоичного неравномерного кодирования, попробуем найти ответы на следующие  вопросы: возможно ли такое кодирование  без использования разделителя  знаков? Существует ли наиболее оптимальный  способ неравномерного двоичного кодирования?

Суть первой проблемы состоит  в нахождении такого варианта кодирования  сообщения, при котором последующее  выделение из него каждого отдельного знака (т.е. декодирование) оказывается  однозначным без специальных  указателей разделения знаков. Наиболее простыми и употребимыми кодами такого типа являются так называемые префиксные коды, которые удовлетворяют следующему условию (условию Фано):

ииииииииииии

Неравномерный код может  быть однозначно декодирован, если никакой  из кодов не совпадает с началом  какого-либо иного более длинного кода.

Например, если имеется код  ПО, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр. Если условие  Фано выполняется, то при прочтении (расшифровке) закодированного сообщения путем сопоставления со списком кодов всегда можно точно указать, где заканчивается один код и начинается другой.

 

Пример: Пусть имеется  следующая таблица префиксных кодов:

 

а	л	м	р	у	ы
10	010	00	11	0110	0111

 

Требуется декодировать сообщение: 00100010000111010101110000110. Декодирование производится циклическим повторением следующих  действий:

1. отрезать от текущего  сообщения крайний левый символ, присоединить к рабочему кодовому  слову;

2. сравнить рабочее кодовое  слово с кодовой таблицей; если  совпадения нет, перейти к (1);

3. декодировать рабочее  кодовое слово, очистить его;

4. проверить, имеются ли  еще знаки в сообщении; если  «да», перейти к (1).

Применение данного алгоритма  дает:

 

Шаг	Рабочее слово	Текущее сообщение	Распознанный знак	Декодированное сообщение
0	пусто	00100010000111010101110000110	-	-
1	0	0100010000111010101110000110	нет	-
2	00	100010000111010101110000110	м	М
3	1	00010000111010101110000110	нет	М
4	10	0010000111010101110000110	а	МА
5	0	010000111010101110000110	нет	МА
6	00	10000111010101110000110	м	Мам
• • •