29. Префиксный сумматор.

Префиксный сумматор развивает логику генерации и распространения сумматора с ускоренным переносом для еще более быстрого выполнения операции сложения. Сначала он вычисляет G и P для пар разрядов, далее для блоков из 4-х разрядов, затем для блоков из 8-ми, 16-ти и т. д. разрядов, пока сигнал генерации не будет известен для каждого разряда. Сумма определяется всеми сигналами генерации.

Иначе говоря, стратегия префиксного сумматора заключается в вычислении входного сигнала переноса C_i-1 для каждого разряда так быстро, насколько это возможно. Затем по формуле вычисляется сумма: S_i = (A_i ⊕ B_i) ⊕ C_i–1

Определим разряд i = –1 для вычисления C_in: G–1 = C_in и P–1 = 0. Следовательно, C_i–1 = G_i–1:–1, так как выходной сигнал переноса (i–1)-го разряда будет активным, если блок, охватывающий разряды от i–1 до –1, генерирует перенос. Полученный перенос генерируется или в разряде (i–1), или в предыдущем разряде и затем распространяется дальше.

Тогда сумма: S_i = (A_i ⊕ B_i) ⊕ G_i–1:–1

Таким образом, основной проблемой является быстрое вычисление всех блоковых сигналов генерации G_-1:-1, G_0:-1, G_1:-1, G_2:-1, . . . , G_N-2:-1.

Эти сигналы вместе с P_-1:-1, P_0:-1, P_1:-1, P_2:-1, . . . , P_N-2:-1 называют префиксными.

Пример 16 разрядного префиксного сумматора:

Работа начинается с предварительного формирования сигналов P_i и G_i для всех разрядов A_i и B_i с использованием элементов И и ИЛИ. Затем используется log₂N = 4 уровня черных ячеек для формирования префиксов G_i:j и P_i:j. Черная ячейка принимает входы из верхней части блока, соответствующего битам i:k, и из нижней части блока, соответствующего битам k–1:j. Затем эти части объединяются для формирования сигналов генерации и распространения всего блока, соответствующего битам i:j.

Блок, соответствующего битам i:j, будет генерировать сигнал переноса, если верхняя часть генерирует перенос или если она распространяет перенос, сгенерированный в нижней части. Блок будет распространять перенос, если и верхняя, и нижняя части распространяют его.

В итоге, префиксный сумматор вычисляет сумму на основе уравнения S_i = (A_i ⊕ B_i) ⊕ G_i–1:–1

Таким образом, задержка префиксного сумматора достигает значения, которое растет с числом разрядов сумматора логарифмически, а не линейно. Ускорение значительно, особенно для сумматоров, имеющих 32 и более разрядов. Такой сумматор использует существенно больше аппаратных средств, чем простой сумматор с ускоренным переносом. Сеть черных ячеек называется префиксным деревом.

Критический путь N-разрядного префиксного сумматора включает в себя предварительное вычисление P_i и G_i, за которым следует log₂N каскадов черных ячеек для получения всех префиксов. Затем сигналы G_i-1:-1 обрабатываются финальными элементами «исключающее ИЛИ» в нижней части схемы для получения сигнала S_i. Задержка N-разрядного префиксного сумматора равна

где t_{pg_prefix} – задержка черной префиксной ячейки