Прямой, обратный и дополнительный код
Алгоритмы выполнения операций сложения и вычитания в позиционной системе счисления с основанием 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), свидетельствует о том, что
т. е. для представления результата операции требуется болъше, чем п разрядов (Xmax= 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+1 - k -m - Δ < Хmax. В этом случае перенос при сложении старших разрядов равен нулю, а сам результат будет представлен обратным кодом. Для образования кода знака результата дос- таточно сложить коды знаков чисел. Это осуществляется одновременно со сложе- нием кодов чисел.
При Δ > 0 получим Z = k s+1- k -m + Δ > Хmax.
В этом случае возникает единичный перенос при сложении старших раз- рядов, имеющий вес k s+1, а в п числовых разрядах будет записано число Δ – k -m. Знаковые разряды чисел суммируются с учетом переноса с весом k s+1. Образую- щейся при этом единице переноса можно приписать вес k -m и сложить ее с чис- лом Δ – k –m.В этом случае будет получена правильная сумма чисел X и Y. Пе- ренос, возникающий при сложении знаковых разрядов и прибавляемый к млад- шему разряду суммы чисел, называется циклическим переносом.
Если числа X и Y отрицательные, то (без учета знаковых разрядов)
Первое число k s+1в полученном выражении соответствует переносу из старшего разряда. Поэтому в числовых разрядах будет находиться число Z = k s+1 –– 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+1соответствует переносу при сложении старших раз- рядов, который учитывается при сложении знаковых разрядов. При Δ< 0 перенос из старших разрядов в знаковые отсутствует, а отрицательный результат будет представлен дополнительным кодом.
Сложение числовых разрядов отрицательных чисел X и Y вдополнительном коде дает следующий результат:
Следовательно, при сложении старших разрядов будет возникать перенос (о чем свидетельствует первое число k s+1), который прибавляется к сумме знаковых разрядов. Перенос из знаковых разрядов при сложении не учитывается (теряется). Отрицательный результат в этом случае будет представлен дополнительным ко-дом.
Таким образом, при выполнении операции сложения чисел с одинаковыми знаками может произойти переполнение разрядной сетки, когда для представления результата требуется большее количество разрядов, чем для представления чисел. Поскольку знаковые разряды складываются с учетом переноса из старшего разряда, то это может привести к неправильному результату. Независимо от кода для пред-ставления отрицательных чисел (обратный или дополнительный) переполнение разрядной сетки происходит всегда, если только при сложении положительных чи- сел возникает перенос в знаковый разряд, а при сложении отрицательных чисел такой перенос отсутствует.
Уменьшить вероятность переполнения разрядной сетки можно путем введе- ния масштабных коэффициентов, на которые умножаются все исходные данные пе- ред решением задачи. Однако для полного исключения переполнения необходимо оценивать возможные значения результата после каждой операции, что практически невыполнимо ввиду большого числа операций. Поэтому в ЭВМ принимаются спе-циальные меры для обнаружения переполнения разрядной сетки. Наиболее широко для этой цели используются два способа.
При обнаружении переполнения по первому способу учитывается то обсто-ятельство, что переполнение может появиться только при сложении чисел с одина-ковыми знаками. В этом случае о переполнении будет свидетельствовать несовпаде- ние знака слагаемых и знака суммы. Недостатком этого способа является необхо-димость реализации двукратного сравнения знаков чисел и их запоминания до кон- ца операции.
Сущность второго способа состоит в использовании так называемых моди-фицированных прямого, обратного и дополнительного кодов. Особенностью этих кодов является наличие двух знаковых разрядов, в которых знак числа представля- ется двумя одинаковыми цифрами. Появление в знаковых разрядах модифициро- ванного кода, обрабатываемых так же, как и числовые разряды, различных цифр (например, 01 при сложении положительных двоичных чисел и 10 при сложении отрицательных двоичных чисел) свидетельствует о переполнении разрядной сетки. Циклический перенос в случае модифицированного обратного кода возникает при сложении вторых (крайних слева) знаковых разрядов. Этот способ обнаружения переполнения получил наибольшее распространение в ЭВМ.
В СОК, как и в смещенных системах счисления, знаки чисел указываются в специальном знаковом разряде, а кодируются они так же, как и в двоичной системе счисления. Для выполнения операций алгебраического сложения чисел в СОК чаще всего используются дополнения отрицательных чисел, являющиеся ана-логами дополнительного кода в позиционных системах. При этом дополнением отрицательного числа X = (Х1, Х2, ... , Хт) в СОК называется величина
,
где , Pi – основания СОК (i =
).
Поскольку N в СОК можно представить как
N = (0, 0, … ,0) = (P1, P2, … , Pm) ,
а 0 ≤ X ≤ N , то компоненты Xg по каждому модулю Pi могут быть определены по формуле
Если один из модулей Pi равен 2 (например, Р1 = 2), то использование дополнений отрицательных чисел означает, что в качестве нуля в СОК принимается величина , диапазон
изменения чисел расположен симметрично относительно Q ,положительные числа X должны быть представлены в виде
,а отрицательные — в виде
. Такое представление чисел в СОК называется искусственной формой. Если ни один из модулей Рi не равен 2, то принимают
и называют такое представление обобщенной искусст-венной формой.