Криптографические методы защиты информации. Лекция Криптографические методы защиты информации Кодирование информации
 Скачать 0.84 Mb.
|
|
1. Формат с фиксированной запятой, в основном, применяется для целых чисел, но может применяться и для вещественных чисел, у которых фиксировано количество десятичных знаков после запятой. Для целых чисел подразумевается, что «запятая» находится справа после младшего бита (разряда), т.е. вне разрядной сетки. В данном формате существуют два представления: беззнаковое (для неотрицательных чисел) и со знаком. Для беззнакового представления все разряды отводятся под представление самого числа. Например, с помощью байта можно представить беззнаковые целые числа от 010 до 25510 (000000002 - 111111112) или вещественные числа с одним десятичным знаком от 0.010 до 25.510 (000000002 - 111111112). Для знакового представления, т.е. положительных и отрицательных чисел, старший разряд отводится под знак (0 – положительное число, 1 – отрицательное). Различают прямой, обратный и дополнительный коды записи знаковых чисел. В прямом коде запись положительного и отрицательного числа выполняется так же, как и в беззнаковом представление (за исключение того, что старший разряд отводится под знак). Таким образом, числа 510 и -510 записываются, как 000001012 и 100001012. В прямом коде имеются два кода числа 0: «положительный нуль» 000000002 и «отрицательный нуль» 100000002. При использовании обратного кода отрицательное число записывается в виде инвертированного положительного числа (0 меняются на 1 и наоборот). Например, числа 510 и -510 записываются, как 000001012 и 111110102. Следует отметить, что в обратном коде, как и в прямом, имеются «положительный нуль» 000000002 и «отрицательный нуль» 111111112. Применение обратного кода позволяет вычесть одно число из другого, используя операцию сложения, т.е. вычитание двух чисел X – Y заменяется их суммой X + (-Y). При этом используются два дополнительных правила: - вычитаемое число инвертируется (представляется в виде обратного кода); - если количество разрядов результата получается больше, чем отведено на представление чисел, то крайний левый разряд (старший) отбрасывается, а к результату добавляется 12. В следующей таблице приведены примеры вычитания. Таблица 22.2. Примеры вычитания двух чисел с использованием обратного кода
Несмотря на то, что обратный код значительно упрощает вычислительные процедуры, а соответственно и быстродействие компьютеров, наличие двух «нулей» и другие условности привели к появлению дополнительного кода. При представлении отрицательного числа его модуль вначале инвертируется, как в обратном коде, а затем к инверсии сразу добавляется 12. В следующей таблице приведены некоторые числа в различном кодовом представлении. Таблица 22.3. Представление чисел в различных кодах
При представлении отрицательных чисел в дополнительных кодах второе правило несколько упрощается - если количество разрядов результата получается больше, чем отведено на представление чисел, то только отбрасывается крайний левый разряд (старший). Таблица 22.4. Примеры вычитания двух чисел с использованием дополнительного кода
Можно возразить, что представление чисел в дополнительных кодах требует на одну операцию больше (после инверсии всегда требуется сложение с 12), что может и не потребоваться в дальнейшем, как в примерах с обратными кодами. В данном случае срабатывает известный «принцип чайника». Лучше сделать процедуру линейной, чем применять в ней правила «Если A то B» (даже если оно одно). То, что с человеческой точки зрения кажется увеличением трудозатрат (вычислительной и временной сложности), с точки зрения программно-технической реализации может оказаться эффективней. Еще одно из преимуществ дополнительного кода перед обратным заключается в возможности представления в единице информации на одно число (состояние) больше, за счет исключения «отрицательного нуля». Поэтому, как правило, диапазон представления (хранения) для знаковых целых чисел длиной один байт составляет от +127 до -128. 2. Формат с плавающей запятой, в основном, используется для вещественных чисел. Число в данном формате представляется в экспоненциальном виде X = en * m, (22.1) где e - основание показательной функции; n - порядок основания; en - характеристика числа; m - мантисса (лат. mantissa - прибавка) – множитель, на который надо умножить характеристику числа, чтобы получить само число. Например, число десятичное число 350 может быть записано, как 3.5 * 102, 35 * 101, 350 * 100 и т.д. В нормализованной научной записи, порядок n выбирается такой, чтобы абсолютная величина m оставалась не меньше единицы, но строго меньше десяти (1 ? |m| < 10). Таким образом, в нормализованной научной записи число 350 выглядит, как 3.5 * 102. При отображении чисел в программах, учитывая, что основание равно 10, их записывают в виде m E ± n, где Е означает «*10^» («…умножить на десять в степени…»). Например, число 350 – 3.5Е+2, а число 0.035 – 3.5Е-2. Так как числа хранится и обрабатывается в компьютерах в двоичном виде, то для этих целей принимается e = 2. Одной из возможных форм двоичного представления чисел с плавающей запятой является следующая.
Рис. 22.9. Двоичный формат представления чисел с плавающей запятой Биты bn± и bm±, означающие знак порядка и мантиссы, кодируются аналогично числам с фиксированной запятой: для положительных чисел «0», для отрицательных – «1». Значение порядка выбирается таким образом, чтобы величина целой части мантиссы в десятичном (и соответственно в двоичном) представлении равнялась «1», что будет соответствовать нормализованной записи для двоичных чисел. Например, для числа 35010 порядок n = 810 = 0010002(350 = 1.3671875 * 28), а для 57610 – n = 910 = 0010012 (576 = 1.125 * 29). Битовое представление величины порядка может быть выполнено в прямом, обратном или дополнительном коде (например, для n = 810 бинарный вид 0010002). Величина мантиссы отображает дробную часть. Для ее преобразования в двоичный вид, она последовательно умножается на 2, пока не станет равной 0. Например,  Рис. 22.10. Пример получения дробной части в бинарном виде Целые части, получаемые в результате последовательного перемножения, и представляют собой двоичный вид дробной части (0.367187510 = 01011112). Оставшаяся часть разрядов величины мантиссы заполняется 0. Таким образом, итоговый вид числа 350 в формате с плавающей запятой с учетом представления мантиссы в нормализованной записи
Рис. 22.11. Двоичный вид числа 350 В программно-аппаратных реализациях арифметических действий широко распространен стандарт представления чисел с плавающей точкой IEEE2 754 (последняя редакция «754-2008 - IEEE Standard for Floating-Point Arithmetic»). Данный стандарт определяет форматы с плавающими запятыми для представления чисел одинарной (англ. single, float) и двойной (англ. double) точности. Общая структура форматов
Рис. 22.12. Общий формат представления двоичных чисел в стандарте IEEE 754 Форматы представления отличаются количеством бит (байт), отводимым для представления чисел, и, соответственно, точностью представления самих чисел. Таблица 22.5. Характеристики форматов представления двоичных чисел в стандарте IEEE 754
Особенностью представления чисел по стандарту IEEE является отсутствие бита под знак порядка. Несмотря на это, величина порядка может принимать как положительные значения, так и отрицательные. Этот момент учитывается т.н. «смещением порядка». После преобразования двоичного вида порядка (записанного в прямом коде) в десятичный от полученной величины отнимается «смещение порядка». В результате получается «истинное» значения порядка числа. Например, если для числа одинарной точности указан порядок 111111112 (= 25510), то величина порядка на самом деле 12810 (= 25510 - 12710), а если 000000002 (= 010), то -12710 (= 010 - 12710). Величина мантиссы указывается, как и в предыдущем случае, в нормализованном виде. C учетом вышеизложенного, число 35010 в формате одинарной точности стандарта IEEE 754 записывается следующим образом.
Рис. 22.13. Двоичный вид числа 350 по стандарту IEEE К другим особенностям стандарта IEEE относится возможность представления специальных чисел. К ним относятся значения NaN (англ. Not a Number - не число) и +/-INF (англ. Infinity - бесконечность), получающихся в результате операций типа деления на ноль. Также сюда попадают денормализованные числа, у которых мантисса меньше единицы. В заключение по числам с плавающей запятой несколько слов о пресловутой «ошибке округления». Т.к. в двоичной форме представления числа хранится только несколько значащих цифр, она не может «покрыть» все многообразие вещественных чисел в заданном диапазоне. В результате, если число невозможно точно представить в двоичной форме, оно представляется ближайшим возможным. Например, если к числу типа double «0.0» последовательно добавлять «1.7», то можно обнаружить следующую «картину» изменения значений. 0.0 1.7 3.4 5.1 6.8 8.5 10.2 11.899999999999999 13.599999999999998 15.299999999999997 16.999999999999996 18.699999999999996 20.399999999999995 22.099999999999994 23.799999999999994 25.499999999999993 27.199999999999992 28.89999999999999 30.59999999999999 32.29999999999999 33.99999999999999 35.699999999999996 37.4 39.1 40.800000000000004 42.50000000000001 44.20000000000001 45.90000000000001 47.600000000000016 … Рис. 22.14. Результат последовательного добавления числа 1.7 (Java 7) Другой нюанс обнаруживается при сложении двух чисел, у которых значительно отличается порядок. Например, результатом сложения 1010 + 10-10 будет 1010. Даже если последовательно триллион (1012) раз добавлять 10-10 к 1010, то результат останется прежним 1010. Если же к 1010 добавить произведение 10-10 * 1012, что с математической точки зрения одно и то же, результат станет 10000000100 (1.0000000100 * 1010). | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||