4.Кодирование и обработка знаковых чисел
Основное неудобство построения устройств, реализующих арифметические операции, состоит в сложном характере алгоритма вычитания. Для его преодоления в ЭВМ всегда операция выполняется по иным правилам, чем это делается обычно. В его основе лежит операция сложения. Алгоритмы выполнения такого рода операций требуют специальных кодов представления отрицательных чисел.
Прямой код.
Это естественное и наиболее привычное представление числа в следующем виде:
знак:
"+" соответствует 0
"-" соответствует 1
В цифровых разрядах пишется модуль положительного или отрицательного числа.
[X]пк - обозначим таким образом изображение числа "X" в прямом коде.
Рассмотрим диапазоны представляемых чисел:
X+min = 0,000....0 - изображение положительного нуля
X+max = 0,111....1 = 1 - 2-n
X-min = 1,111....1 = -(1-2-n)
X-max = 1,000....0 - изображение отрицательного нуля.
Таким образом, нуль имеет двоякое изображение.
Замечания:
перед выполнением операции вычитания чисел с одинаковыми знаками и сложения с разными, необходимо сравнить по модулю два кода и, если нужно, сделать перестановку кодов местами, затем можно выполнять собственно операцию вычитания кодов.
при выполнении операции умножения отдельно и независимо находятся модули произведений кодов, а знак находится как результат операции сложения по модулю два:
[X]пк * [Y]пк = sign Z. |Z|
|Z| = |X|*|Y|
sign Z = sign X sign Y или Sz = Sx Sy
Собственно умножение выполняется с применением микроопераций сложения и сдвига.
аналогично умножению выполняется операция деления с использованием микроопераций вычитания и сдвига.
Вследствие ряда неудобств в ЭВМ операции вычитания, сложения чисел с разными знаками и деления в прямом коде практически не выполняются.
Дополнительный код
Дополнительным называется код, в котором для положительного числа в знаковом разряде пишется "0", в цифровых - модуль числа, а для отрицательного в знаковом разряде пишется "1", в цифровых - дополнение числа до единицы.
Если некоторое X- = -0,x1x2...xn нужно представить в дополнительном коде, то
где: 1 - 0,x1x2...xn = 0, Z1Z2...Zn
Диапазоны представленных чисел:
Х+ min = 0,0...0 - положительный нуль
Х+ max = 0,11...1 = 1-2-n - максимальное положительное число.
X- min = 1,11...1 = 2-2-n - минимальное отрицательное число
X- max = 1,0...0 - наибольшее(по модулю) отрицательное число
Таким образом, нуль имеет единственное представление.
В самом деле, так как
X-X = [X+]дк + [X-]дк = 0, то в дополнительном коде: |X+| + 10 - |X-| = 10, если в разрядной сетке ЭВМ нет второго знакового разряда, то это переполнение теряется, и в знаковом разряде будет только нуль.
Важная особенность в получении дополнительного кода отрицательного числа состоит в следующем:
Таким образом, для записи дополнительного кода отрицательного числа необходимо в знаковом разряде поставить единицу, проинвертировать все цифровые разряды числа и прибавить единицу в младший разряд. Это также правило перевода из дополнительного кода в прямой код.
Рассмотрим на примерах выполнение операции сложения двух чисел с разными знаками.
Возможны следующие случаи:
X+ + Y+ = S+
X+ + Y- = S+
X+ + Y- = S-
X- + Y- = S-
Необходимо помнить, что нельзя, выполняя операции, выходить за диапазон представляемых в данной разрядной сетке чисел, записанных с фиксированной запятой.
Положим n = 3, 1 - знаковый разряд и 2 - цифровых.
X+ = 0,10
Y+ = 0,01
В дополнительном коде
То есть, нет никаких особенностей.
X+ = 0,10
Y- = -0,01
В дополнительном коде
Переполнение теряется и получается верный результат.
X+ = 0,01
Y- = -0,11
В дополнительном коде
X- = -0,10
Y- = -0,01
В дополнительном коде
Возникающее переполнение теряется и общий результат отрицательный.
Таким образом, важной особенностью дополнительного кода является то, что знаковый разряд в процессе выполнения операции рассматривается совместно с цифровыми. Возникающие переносы теряются и не влияют на результат операции.
Обратным называется код, для которого в знаковом разряде положительного числа пишется "0", в цифровых - модуль числа, а для отрицательного - в знаковом разряде пишется единица, в цифровых - инвертированные разряды исходного числа.
Определим диапазоны чисел:
X+ min = 0,00...0 - положительный нуль.
X+ max = 0,111...1 = 1 - 2-n
X- min = 1,11...1 0 = 2 - 2-n+1
X- max = 1,00...00 = 1
В обратном коде есть два изображения нуля:
"Положительный" нуль:
[X]ок = 0,0...0
и "отрицательный" нуль:
[X]ок = 1,11...11
При этом
X - X = [X+]ок + [X-]ок = |X+| + 10 - (10)-n - |X-| = +10 - (10)-n = 0
То есть, единица переноса в знаковом разряде эквивалентна единице младшего разряда. Поэтому при выполнении операции сложения-вычитания необходимо возникающий перенос циклически прибавлять в младший разряд частичного результата.
Рассмотрим прежние четыре случая, помня о том, что сумма двух слагаемых по модулю должна быть меньше единицы.
X+ = 0,10
Y- = -0,01
X+ + Y- = S+
В обратном коде:
Возникающее переполнение должно быть добавлено к младшему разряду частичной суммы.
X+ = 0,10
Y+ = +0,01
X+ + Y+ = S+
В обратном коде:
Нет никаких особенностей по сравнению с прямым кодом.
X+ = 0,01
Y- = -0,10
X+ + Y- = S-
В обратном коде:
То есть, не возникает циклического переноса.
X- = -0,01
Y- = -0,10
X- + Y- = S-
В обратном коде:
Возникает переполнение знакового разряда, которое добавляется в младший разряд частичной суммы.
Заметим, что получение обратного кода проще, чем дополнительного. Это поразрядно выполняемая микрооперция инверсии кода. Как станет ясно из схемного решения, эта микрооперация выполняется так же быстро, как и передача кода.
Поскольку результатом операции является совокупность результатов по всем разрядам, то данную операцию можно выполнять одновременно над всеми цифровыми разрядами числа.
Модифицированные коды
Важная особенность рассмотренных кодов состоит в том, что в процессе выполнения операции сложения-вычитания не происходит переполнения цифровой части числа и переноса в знаковый разряд. Переполнение возникает лишь в знаковом разряде. Так бывает потому, что сумма двух слагаемых по модулю меньше единицы.
При решении реальных задач часто трудно определить заранее, будет ли сумма двух слагаемых меньше единицы. Во всяком случае, для предотвращения переполнения можно вводить дополнительные ограничения на величину слагаемых, сужающих диапазон чисел, с которыми оперирует машина. И то, и другое является неприемлемым.
Рассмотрим такой пример:
X = -0,101 Дополнительный код 1.011 = [X]дк
Y= -0,111 1.001 = [Y]дк
S- = X- + Y- 0.100 = [S]дк
То есть получаем неправильный результат как по знаку, так и в цифровой части.
Рассмотрим ещё один пример:
X = +0,101 В любом из ранее рассмотренных 0.101 = [X]дк,ок
Y = +0,111 кодов имеем 0.111 = [Y]дк,ок
S+ = X+ + Y+ 1.100 = [S]дк,ок
То есть и в этом случае происходящее переполнение в цифровой части искажает результат операции.
Можно заметить, что переполнение числовой сетки происходит в случае одинаковых знаков слагаемых, так как именно в этом случае модуль результата превосходит модули каждого из слагаемых, сам факт переполнения может быть зафиксирован изменением знака результата.
Таким образом, одним из способов фиксации переполнения является автоматическое определение перехода от одинаковых знаков слагаемых к противоположному знаку результата.
Однако такой способ фиксации переполнения неудобен, так как предварительно знаки слагаемых должны быть запомнены, сравнены между собой и после получения результата.
Существует другой принцип фиксации переполнения. Этот принцип основан на применении так называемых модифицированных кодов. Очевидно,что при переполнении разрядной сетки вычисления необходимо прекратить или, по крайней мере, выработать специальный признак переполнения, а решение о прекращении вычислений возложить на программиста.
Существо модифицированных кодов состоит в том, что к знаковому разряду добавляется ещё один разряд:
"+" ставится в соответствие 00
"–" ставится в соответствие 11
Тогда, по определению модифицированным дополнительным кодом числа называется
Возникающий в знаковых разрядах перенос теряется. В целом же модифицированный код не отличается от простого дополнительного. Аналогично, по определению, обратным кодом является:
Как и в случае простого обратного кода, возникающая единица переноса в знаковых разрядах по цепи циклического переноса добавляется в младший разряд цифровой части числа.
Так как в сложении по-прежнему участвуют только числа меньше единицы, то
S = X + Y < 2
Поэтому старший знаковый разряд не может быть искажён переносом из цифровой части числа, с другой стороны, перенос, возникающий при сложении чисел в случае, когда
S = X + Y > 1
искажает младший знаковый разряд.
Несовпадение знаковых разрядов после выполнения операции указывает на факт наличия переполнения.
При этом различают два типа переполнения:
"01" - положительное
"10" - отрицательное.
Первому ставится в соответствие комбинация 01 в знаковых разрядах, а второму – 10.
Примеры
Модифицированный дополнительный код:
а) [X]мдк = 00.101 +00.101
[Y]мдк = 00.111 00.111
[S]мдк = 01.100 – положительное переполнение
б) [X]мдк = 11.101 +11.101
[Y]мдк = 11.001 11.001
[S]мдк = 1х10.110 – отрицательное переполнение
Модифицированный обратный код
а) [X]мок = 00.101 +00.101
[Y]мок = 00.111 00.111
[S]мок = 01.100 – положительное переполнение
б) [X]мок = 11.010 +11.010
[Y]мок = 11.000 11.000
1|10.010
-----
1
[S]мок = 10.011 – отрицательное переполнение
Умножение чисел со старших разрядов в прямом коде
Пусть два числа X и Y представлены с фиксированной запятой в виде:
[X]пк = sign X.x1x2...xn – множимое
[Y]пк = sign Y.y1y2...yn – множитель
Представим множитель в виде:
[Y]пк = sign Y. (y1*2-1 + y2*2-2 + ... + yn*2-n)
Тогда:
[Z]пк = [X]пк*[Y]пк = sign Z. |X| (y1*2-1 + y2*2-2 + ... + yn*2-n) =
= sign Z. (|X|*y1*2-1 + |X|*y2*2-2 + ... + |X|*yn*2-n) =
= sign Z. (|X|*2-1*y1 + |X|*2-2*y2 + ... + |X|*2-n*yn)
Это есть аналитическая запись алгоритма умножения двух чисел, начиная со старших разрядов множителя.
Алгоритм:
Множимое сдвигается вправо на 1 разряд
Анализируется цифра множителя. Если она – нуль, то частичное произведение не суммируется, а если она – единица, то частичное произведение добавляется к общему результату.
Последовательность операций по пунктам 1 и 2 продолжается "n" раз.
Знак произведения находится независимо от получения цифровой части по формуле:
sign Z = sign X sign Y
Пример:
Видно, что в общем случае нужно иметь для точного результата сетку с числом разрядов, равным сумме разрядностей сеток сомножителей.
Если нужно получать произведение с точностью не хуже, чем 2-n, то достаточно иметь не удвоенную величину разрядной сетки, а лишь увеличенную на
d = log2n разрядов
Умножение с младших разрядов в прямом коде
Напишем выражение для произведения двух чисел в несколько изменённом виде, а именно:
[Z]пк = [X]пк*[Y]пк =
= sign Z.(|X|*y1*2-1 + |X|*y2*2-2 +... + |X|*yn*2-n ) =
= sign Z.( |X|*2-1*y1 + 2-1 (|X|*2-1*y2 + 2-1 (|X|*2-1*y3 + (...)))) =
= sign Z. ((...(( |X|*yn*2-1 + |X|*yn-1 )2-1 + |X|*yn-2 )2-1 + ... +
+ |X|*y2 )2-1 + |X|*y1 )*2-1
Это выражение называется преобразованием по схеме Горнера и задаёт алгоритм умножения с младших разрядов множителя.
Таким образом, для умножения должна выполняться следующая последовательность действий:
Анализируется младшая цифра множителя. Если она равна "1", то множимое участвует в формировании части произведения. В противном случае – не участвует.
Полученное частичное произведение сдвигается вправо на 1 разряд.
Операции по пунктам 1 и 2 выполняются до старшего разряда.
Пример:
signZ= 1 1 = 0
[Z]пк = 0.10000100
Замечание.
Для получения произведения с точностью не ниже, чем 2-n нужно иметь только "n"– разрядную сетку.
Итак, видим, что для получения произведения как при умножении со старших,так и младших разрядов необходимо выполнять две микрооперации: суммирование чисел в позиционной системе счисления и сдвига.
Однако, известно, что числа могут быть представлены в различных кодах(это, прежде всего, отрицательные числа).
Мы уже знаем, как выполняется операция суммирования чисел (в том числе и с разными знаками).
Однако микрооперация сдвига имеет некоторые особенности:
Сдвиг вправо:
Сдвиг влево возможен только в случае, если сдвинутое число меньше единицы по модулю:
Исходные числа:
Если чисто формально сделать преобразование выражения некоторого числа, записанного в прямом коде до выполнения сдвига и после выполнения микрооперации сдвига, в обратный модифицированный код, то:
То есть при сдвиге вправо отрицательного числа старшие разряды заполняются единицами. При сдвиге влево в старшие и младшие разряды пишутся единицы.
Пользуясь аналогичными правилами, нетрудно установить, что при сдвиге влево отрицательного числа в модифицированном дополнительном коде младшие разряды сдвинутого числа нужно заполнить нулями.
Умножение с младших разрядов в дополнительном коде
Алгоритм:
[Z]дк = (...(0+[X]дк*[yn+1 – yn])*2-1 + [X]дк*[yn – yn-1])*2-1 + ...
... + [X]дк*[y2 – y1])*2-1 + [X]дк*[y1 – y0]
Если yn = yn+ 1 , то производится сдвиг частичного произведения.
Если yn = 0 и yn+1 = 1, то к частичному произведению прибавляется [X]дк
Если yn = 1 и yn+1 = 0, то из частичного произведения вычитается [X]дк.
Пример:
Умножение со старших разрядов в дополнительном коде
[Z]дк = [X]дк*[Y]дк = [X]дк*(y1 – y0 ) + [X]дк*(y2 – y1 )*2-1 + ... +
+ [X]дк*(yn+1 – yn )*2-n
[-X]дк = 1.01011
[Z]дк = [-X]дк + [X]*2-1 + [X]дк*2-2*0 + [-X]дк*2-3 +
+ [X]дк*2-4 + [-X]дк*2-5
+1.01011 [-X]дк
0.010101 [X]дк*2-1
________
+1.101011
1.11101011 [-X]дк*2-3
__________
+1.10010111
0.000010101 [X]дк*2-4
___________
+1.101000011
1.1111101011 [-X]дк*2-5
____________
1.1001110001
Ответ: [Z]дк = 1.1001110001