Раннее завершение является свойством некоторых классов асинхронных схем . Это означает, что выход схемы может быть доступен, как только поступит достаточно входов, чтобы его можно было определить. Например, если все входы мультиплексора поступили , и все они одинаковы, но линия выбора еще не поступила, схема все равно может выдать выход. Поскольку все входы идентичны, линия выбора не имеет значения.
Сумматор с импульсным переносом — это простая схема сумматора, но медленная, поскольку сигнал переноса должен распространяться через каждый каскад сумматора:
На этой схеме показан 5-битный сумматор с непрерывным переносом в действии. Существует длинный путь переноса из пяти стадий, поэтому каждый раз, когда два числа складываются этим сумматором, ему нужно ждать, пока перенос распространится по всем пяти стадиям.
Переключившись на двухпроводную сигнализацию для бита переноса, он может заставить каждую стадию сигнализировать о своем переносе, как только узнает. Если оба входа на стадию равны 1, то перенос будет равен 1 независимо от того, какой перенос в. Если оба входа равны 0, то перенос будет равен нулю. Это раннее завершение сокращает максимальную длину цепи переноса в большинстве случаев:
Два бита переноса могут быть известны сразу же после поступления ввода, для ввода, показанного на рисунке. Это означает, что максимальная длина цепи переноса составляет три, а не пять. Если он использует двухпроводную сигнализацию для входов и выходов, он может указать на завершение, как только все цепи переноса будут завершены.
В среднем n -битный асинхронный сумматор с рябью завершит работу за время O(log n). Распространив этот подход на сумматоры с опережающим переносом , можно выполнить сложение за время O(log log n).