2.9. ДВОИЧНАЯ СИСТЕМА СЧИСЛЕНИЯ

Под двоичной системой счисления понимается такая система, в которой для изображения чисел используются два символа, а веса разрядов меняются по закону (где k — произвольное целое

Таблица 2.8

Таблица 2.9

число). Классической двоичной системой является система с символами . Ее двоичные цифры часто называют битами.

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

Табл. 2.8 умножения двоичных чисел полностью определяется двумя правилами: 1) умножение любого числа на 0 дает 0; 2) умножение любого числа на 1 оставляет его без изменения.

Для сложения имеется только правило, согласно которому прибавление 0 к любому числу не меняет этого числа. Тогда таблица сложения примет вид: (табл. 2.9).

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

Первая часть таблицы соответствует арифметике вычетов по

Вторая часть — представляет собой простейший пример операции булевой алгебры.

Третья — представляет собой обычную двоичную систему счисления с символами 0, 1.

Как уже отмечалось, в общем виде все двоичные числа представляются в виде полинома

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

Сложение в двоичной системе счисления производится по правилам сложения полиномов. Поэтому при сложении чисел А и В разряд суммы и перенос П из данного разряда в будет определяться в соответствии со следующим выражением:

где

Выражению (2.17) соответствует табл. 2.10 сложения одноразрядных чисел. В соответствии с табл. 2.10 можно суммировать многоразрядные двоичные числа.

Таблица 2.10

Пример. Задано . Найти сумму ,

В результате поразрядного сложения чисел А и В получаем;

Двоичная система с цифрами 1, 1

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

Символ —1 обычно изображают как 1, а систему, в которой используются символы , называют системой . Число вапишется, например, в этой системе как если положить в (2.16), что принимает значения 1 или 1.

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

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

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

где

Соотношение (2.18) выражает связь между обычной двоичной системой и системой (1,1).

Пример. Перевести число в систему (1,1).

Используя соотношение (2.18), сводим перевод к замене комбинаций комбинациями соответственно

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

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

Для перевода чисел в систему (I, Г) по методу [29] необходимо учитывать следующее: в случае нечетного числа перевод осуществляют по правилу (2.18), а затем в разряд записывают единицу; при переводе четного числа его сначала превращают в нечетное добавлением единицы в младший разряд и только после этого переводят в систему (1, I) по правилу (2.18) как нечетное число. Затем к полученному результату в разряд записывают 1.

Пример. Перевести в систему двоичное число

По [53, 65) это число вначале превращаем в нечетное число 11001. После этого заменяем в изображении числа комбинацию 001 на комбинацию 111, приписываем в разряд после запятой цифру Г и подучаем

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

Для перевода положительных чисел вначале к исходному числу приписывается справа еще один разряд, значение которого есть 1. Затем в исходном изображении выделяют конструкции, состоящие из последовательности нулей и единиц справа, т. е. конструкции вида Эти конструкции на основании (2.18) преобразуются к виду т. е. самый старший нулевой разряд заменяется на 1, а остальные разряды, включая 1 в младшем разряде конструкции, заменяются на 1.

Пример. Число

Приписываем справа разряд значением 1.

Выделяем конструкции вида

Преобразуем выделение конструкции и получаем

В этом случае добавлением 1 справа к исходной записи реализуется учет аддитивной поправки. Значение этой поправки должно быть одно и то же для всех чисел, поэтому, если в исходной записи дробная часть числа имеет меньше, чем значащих цифр, то ее надо заполнить нулями до зарядов и уже в разряд записать 1.

Пример. Число при

Вначале подготовим запись числа к преобразованию: .

Дополним А разрядом справа со значением 1 и выделим конструкции вида

Преобразуем выделенные конструкции и получим

Для представления отрицательных чисел в системе с цифрами 1,

1 вначале преобразуется запись абсолютной величины числа А путем дописывания слева и справа необходимого числа нулей. Затем в этом изображении все 1 заменяются на 1, а потом к полученному изображению дописывается 1 справа (аддитивная добавка). Далее выделяются конструкции вида которые преобразуются соответственно к виду

Пример.

Двоичную систему счисления с цифрами I, 1 рационально использовать как промежуточную при выполнении операций умножения и деления. Прямая реализация арифметических действий в этой снсте заметно сложнее, чем в системе с цифрами 0, 1.

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

Избыточная двоичная система

Избыточной системой счисления с основанием называется система, в которой для записи чисел используется количество символов большее, чем Избыточная двоичная система (симметричная) связана с обычной следующим соотношением:

На основании выражения (2.20) производится переход от двоичной системы с цифрами (0, 1) в систему (1, 0, 1) и наоборот, например,

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

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

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

Таблица 2.11

Таблица 2.12

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

Для доказательства рассмотрим следующий алгоритм суммирования знакоразрядных двоичных чисел А и В. На первом этапе производится поразрядное суммирование операндов А и В:

Значениями и могут но если (табл. 2.11). На втором этапе к полученному значению разрядной суммы прибавляется перенос из предыдущего разряда:

Здесь уже если (табл. 2.11). На третьем этапе складываются значения

Пусть это суммирование осуществляется точно так же, как на втором этапе, т. е. если Можно показать, что при этих условиях Действительно, если Пусть вначале но тогда а раз то обязательно должно быть . Это, в свою очередь, приводит к тому, что (см. табл. 2.11). Точно так же доказывается, что ; следовательно, и тогда Таким образом, при сложении знакоразрядных двоичных операндов перенос может распространяться не более чем на два разряда и, следовательно, максимальное время суммирования операндов произвольной длины составит не более считая, что в каждом одноразрядном сумматоре время формирования суммы больше, чем время формирования переноса.

Для переносов допустимыми значениями были 1, 0, I. Можно считать, что при сложении используются два типа переносов — положительный П со значениями 0, 1 и отрицательный П со значениями 0, 1. При наличии двух типов переносов можно перестроить алгоритм суммирования следующим образом. Вначале находят сумму и положительного переноса из предыдущего разряда

где для 5 допустимы значения О, I (табл. 2.12). Затем полученное значение разрядной суммы уточняется путем прибавления к ней отрицательного переноса из предыдущего разряда:

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

Для двоичной системы счисления можно добиться распространения переносов на один разряд, если один операнд представить в знакоразрядной форме, а второй — в обычной двоичной системе счисления. В этом случае на первом этапе поразрядно суммируются

Пусть Интересно, что можно выбрать значения так, что . На втором этапе складываются значения

Очевидно, что при этом никогда не будет переполнения и

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

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

Навыки в обращения с двоичными числами

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

Таблица 2.13

1. Число

Необходимо знать на память десятичные значения этих чисел от до Они приведены в табл. 2.13.

2. Число

3. Необходимо знать на память десятичные значения двоичных чисел от 0 до 31 включительно. Эти числа в дальнейшем будут называться «малыми числами».

4. Двоичное число

равно

Примеры.

Двоичное число

равно а

Примеры.

5. Если в -разрядном числе много единиц и мало нулей, то для определения его количественного эквивалента можно из -разрядного числа, записанного одними единицами, вычесть малое число, в котором разряды со значением I соответствуют разрядам исходного числа с нулевым значением и наоборот.

Пример. соответствует

Некоторые числа можно читать двумя способами.

Пример. или

6. Зная на память малые числа, легко проверять правильность выполнения операций сложения и вычитания двоичных чисел, если их можно разбить на группы, не связанные друг с другом переносами или заемами.

Пример. Левая группа: Правая группа:

7. Чтение двоичных дробей

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

Пример. — (читается «двадцать семь тридцать вторых»);

— (читается «пятьдесят четыре двести пятьдесят шестых»).

8. Двоичные дроби могут быть периодическими. Например, периодическими являются дроби вида

Примеры.