последовательным). Таким образом, оценояная функция для такого сумматора имеет вид

Ф"(5) = :11 = Ф(5)-/=-(5). (1.13)

. , 21og S -

Значения всех, вновь построенных функций для неко-торых значений S даны в нижеследующей таблице.

Таблица 1.4

Все функции, кроме Ф"(5), монотонно возрастают. Минимум для Ф"(5), как это следует из таблицы, равен 6. Таким образом, при использовании комбинационного последовательного сумматора система счисления с основанием шесть представляет определенный интерес.

Отметим также, что с ростом S функция Ф(5) растет наиболее быстро.

Введенные нами оценочные функции типа Ф(5) оценивали время выполнения операции умножения "толькЪ с точки зрения числа необходимых сложений. Но при выполнении умножения, кроме сложений, необходимо еще учитывать число операций сдвига, так как время сдвига для некоторых типов сумматора соизмеримо с временем реализации операции сложения.

Количество сдвигов пропорционально числу разрядов множителя и, следовательно, тем меньше, чем больше S (при фиксированном N). Время одного сдвига практически не зависит от основания системы счисления, поэтому полное время умножения с учетом сдвигов можно определить как

. logMf-flog/V.,,

где -с -время одного сложения в системе счисления с основанием S, а \ -время однократного сдвига. Если в качестве эталона сравнения снова использовать двоичную систему счисления, то полная оценочная функция для умножения принимает вид .

log2 7VT + 21og2 7VT

Для сумматоров параллельного типа можно дать более прозрачную запись для этой оценочной функ-. ции. Если в машине используется параллельный сумматор с комбинационными одноразрядными суммирующими схемами, то я-= т,. Если обозначить через д = \-у, то R{S) принимает вид

: /(5) Izi L2£ . -(1,15)

Если же в машине используется накапливающий параллельный сумматор, то "су! и если через t обозначить : т, то оценочная функция R (5) примет вид

R"(S)== S\S~-l) + 4t 2(l+2f)log2S

На практике при использовании комбинационного сумматора параллельного типа принято считать, что

•c=-jc2. В-этом случае функция /?(5) принимает вид

S-1+1 S

/?(5) =

(l + l)l0g2S 2l0g2S

т. е. совпадает с функцией F{S).

. ill

Если рассматривать операцию умножения не как операцию, сводящуюся к последовательности сложений и сдвигов, а как операцию, для производства которой используется схема, показанная на рис. 1.7, то сложность умножения должна будет- зависеть от сложности блока УО. Сложность блока УО определяется в основном размером таблицы умножения, используемой в данной системе счисления. Объем

этой таблицы есть - (в таблицу умножения

Не включена цифра О и учтена имеющаяся симметрия таблицы). Поведение функции

Q(5) = i£ziiH5n2I (1.17)

описывается следующей таблицей:

Рассмотрим теперь оценку различных систем счисления с точки зрения возможности убыстрения- производства основных арифметических операций в машине. В настоящее время подобные результаты в достаточно общей фррме имеются лишь для операции умножения. Эти результаты были получены М. А. Карцевым.

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