Прямой, обратный и дополнительный код

Алгоритмы выполнения операций сложения и вычитания в позиционной системе счисления с основанием k устанавливаются аналогично соответствующим алгоритмам в обычной десятичной системе. Результаты выполнения операций сло-жения и вычитания цифр х и у в одном разряде представляются двумя цифрами: цифрой s результата соответствующей операции в данном разряде и цифрой r переноса (заема) в старшем разряде. Правила формирования цифр s и r при любом k для всех указанных операций можно записать так:

а)для сложения

б) для вычитания

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

Представление числа X в прямом коде определяется выражением

(6)

т. е. прямые коды чисел + X и —X отличаются только знаковыми разрядами. Из (6) видно, что нуль в прямом коде может быть представлен двояко: положительный нуль +0 = 0_пр = 0.00... 0,00... 0 и отрицательный нуль – 0 = 0_пр = . 00... 0,00... 0.

Используется прямой код в ЭВМ для ввода и вывода информации, а также для представления чисел в запоминающих устройствах. Сложение чисел с одина- ковыми знаками в прямом коде выполняется в соответствии с приведенными вы- ше правилами и не вызывает затруднений. Наличие цифры переноса r _слож = 1 при сложении старших разрядов n -разрядных чисел X и Y, представленных в форме (1), свидетельствует о том, что

т. е. для представления результата операции требуется болъше, чем п разрядов (X _max= k ^s — k ^- ^m – максимальное число, которое может быть представлено п раз- рядами в форме (1)). В этом случае говорят, что происходит переполнение разряд- ной сетки. Однако складывать числа с разными знаками (т. е. выполнять алгебраическое сложение) в прямых кодах неудобно, так как в составе ЭВМ в этом случае должно быть специальное оборудование для вычитания чисел (вычитатель) и оп-ределения знака разности.

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

(7)

Сравнивая (6) и (7), легко заметить, что обратный код положительного числа совпадает с его прямым кодом.

Так как при k =2

то для получения обратного кода отрицательного числа в двоичной системе счис- ления необходимо в знаковом разряде записать 1, а в остальных разрядах едини- цы заменить нулями и нули единицами. Аналогичным образом переходят от об- ратного кода отрицательного числа к прямому коду. Для получения обратного ко- да отрицательных чисел в k -йсистеме (k > 2) необходимо в знаковый разряд за- писать цифру k – 1, а остальные цифры заменить их дополнениями до k – 1. На- пример, в десятичной системе заменяют 9 на 0, 8 на 1 и т. д. В отличие от пря- мого кода в обратном коде нельзя отбрасывать нули после знакового разряда в целой части, смещая знаковый разряд вправо, и нули в конце дробной части от-рицательных чисел, но можно отбрасывать записанные на этих местах цифры k – 1. Нуль в обратном коде так же, как и в прямом коде, имеет два изображения. Если числа X и Y положительные, то их сложение не отличается от сложения в прямом коде. Когда же одно из чисел (например, Y) отрицательное и представлено обрат- ным кодом, то без учета знаковых разрядов можно записать, что

(8)

Дальнейшее выполнение операции зависит от знака разности Δ = | X | - | Y |. При Δ < 0 выражение (8) можно записать так: Z = k ^s⁺¹- k ^- ^m - Δ < Х _max. В этом случае перенос при сложении старших разрядов равен нулю, а сам результат будет представлен обратным кодом. Для образования кода знака результата дос- таточно сложить коды знаков чисел. Это осуществляется одновременно со сложе- нием кодов чисел.

При Δ > 0 получим Z = k ^s⁺¹- k^-^m + Δ > Х _max.

В этом случае возникает единичный перенос при сложении старших раз- рядов, имеющий вес k ^s⁺¹, а в п числовых разрядах будет записано число Δ – k ^-^m. Знаковые разряды чисел суммируются с учетом переноса с весом k ^s⁺¹. Образую- щейся при этом единице переноса можно приписать вес k ^-^m и сложить ее с чис- лом Δ – k ^–^m. В этом случае будет получена правильная сумма чисел X и Y. Пе- ренос, возникающий при сложении знаковых разрядов и прибавляемый к млад- шему разряду суммы чисел, называется циклическим переносом.

Если числа X и Y отрицательные, то (без учета знаковых разрядов)

Первое число k ^s⁺¹в полученном выражении соответствует переносу из старшего разряда. Поэтому в числовых разрядах будет находиться число Z = k ^s⁺¹–– k ^-^m – (| X | + | Y |) – k ^-^m, которое после прибавления единицы циклического пе- реноса, образующейся при сложении знаковых разрядов, будет представлять собой сумму чисел X и Y, записанную в обратном коде.

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

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

(9)

Представление положительного числа в дополнительном коде совпадает с его прямым кодом. Из сравнения вторых строк выражений (7) и (9) следует, что дополнительный код отрицательного числа отличается от обратного кода того же числа на величину k ^-^m. На этом основано правило формирования дополнительного кода отрицательного числа – достаточно получить обратный код числа и приба- вить 1 в его младший разряд. При k = 2 тот же результат может быть получен, если в прямом коде отрицательного числа оставить без изменения крайние справа нули и первую единицу за ними, а все цифры левее этой единицы (кроме знаково- го разряда) поменять на обратные. Преобразование дополнительного кода отрица-тельного числа в прямой код может быть осуществлено либо обратным путем (т.е. вычитанием 1 в младшем разряде и последующим преобразованием обратного кода), либо путем формирования дополнительного кода от дополнительного. Оба пути при-водят к одинаковому результату. Нуль, в отличие от прямого и обратного кодов, в дополнительном коде имеет единственное представление 0_доп = 0.000... 0,00... 0.

Сложение положительных чисел X и Y в дополнительном коде выполняет- ся так же, как и в прямом и обратном кодах. Если число Y отрицательное, то без учета знаковых разрядов получим

При Δ > 0 число k ^s⁺¹соответствует переносу при сложении старших раз- рядов, который учитывается при сложении знаковых разрядов. При Δ< 0 перенос из старших разрядов в знаковые отсутствует, а отрицательный результат будет представлен дополнительным кодом.

Сложение числовых разрядов отрицательных чисел X и Y вдополнительном коде дает следующий результат:

Следовательно, при сложении старших разрядов будет возникать перенос (о чем свидетельствует первое число k ^s⁺¹), который прибавляется к сумме знаковых разрядов. Перенос из знаковых разрядов при сложении не учитывается (теряется). Отрицательный результат в этом случае будет представлен дополнительным ко-дом.

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

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

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

Сущность второго способа состоит в использовании так называемых моди-фицированных прямого, обратного и дополнительного кодов. Особенностью этих кодов является наличие двух знаковых разрядов, в которых знак числа представля- ется двумя одинаковыми цифрами. Появление в знаковых разрядах модифициро- ванного кода, обрабатываемых так же, как и числовые разряды, различных цифр (например, 01 при сложении положительных двоичных чисел и 10 при сложении отрицательных двоичных чисел) свидетельствует о переполнении разрядной сетки. Циклический перенос в случае модифицированного обратного кода возникает при сложении вторых (крайних слева) знаковых разрядов. Этот способ обнаружения переполнения получил наибольшее распространение в ЭВМ.

В СОК, как и в смещенных системах счисления, знаки чисел указываются в специальном знаковом разряде, а кодируются они так же, как и в двоичной системе счисления. Для выполнения операций алгебраического сложения чисел в СОК чаще всего используются дополнения отрицательных чисел, являющиеся ана-логами дополнительного кода в позиционных системах. При этом дополнением отрицательного числа X = (Х ₁, Х ₂, ..., Х_т) в СОК называется величина

где , P_i – основания СОК (i = ).

Поскольку N в СОК можно представить как

N = (0, 0, …,0) = (P ₁, P ₂, …, P_m),

а 0 ≤ X ≤ N, то компоненты X_g по каждому модулю P_i могут быть определены по формуле

Если один из модулей P_i равен 2 (например, Р ₁ = 2 ), то использование дополнений отрицательных чисел означает, что в качестве нуля в СОК принимается величина , диапазон изменения чисел расположен симметрично относительно Q,положительные числа X должны быть представлены в виде ,а отрицательные — в виде . Такое представление чисел в СОК называется искусственной формой. Если ни один из модулей Р_i не равен 2, то принимают и называют такое представление обобщенной искусст-венной формой.