9.2.3 Методы ускорения операции сложения

Из всего многообразия методов ускорения операций суммирования, наибольший интерес представляет параллельное суммирование при избыточном кодировании. Если имеется возможность построить -разрядный параллельный сумматор, то удобнее всего организовать суммирование как это делается в алгоритме B. Тогда кодирование в случае CSAs заключается в представлении 0 как , 1 как или и 2 как . Таким образом, операнд, участвующий в сложении, представляется парой составляющих, имеющих обычный неизбыточный алфавит ( и в алгоритме B). Причем операнд в избыточной форме может складываться с обыкновенным двоичным числом ( и в алгоритме B), а получающийся при этом результат носит тот же избыточный характер. Представление отрицательных чисел (образование поразрядных дополнений) производится как простая инверсия двоичных разрядов. Использование такой избыточной системы позволяет значительно ускорить выполнение операции суммирования за счет сокращения распространения переносов, причем быстродействие не зависит от длины операндов, однако увеличивается объем памяти для хранения данных и количество вентилей, реализующих суммирование.

Если бы удалось сконструировать такой параллельный сумматор (для алгоритма B), то, как показано в [Se], время выполнения операции модулярного умножения можно было бы уменьшить с (если использовать процессор с фиксированной длиной слова) до . В самом деле, пусть время выполнения цикла FOR алгоритма B равно , тогда время выполнения всего алгоритма действительно не превысит , где  -- задержка на нормализацию, приведение из избыточной к нормальной форме и избавление от отрицательного остатка.

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

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