Прелести вентилей Фредкина

Вентиль Фредкина, также известный как Controlled Swap и симметрический переключатель — замена транзистора в цифровой технике будущего. Переключатели обратимые и консервативные (выходит столько же единиц и нулей, сколько входило), а значит спинтронные переключатели такого типа скорее всего удастся сделать очень маленькими, очень быстрыми и очень эффективными. А переключатели это очень практичные. Клонирование сигнала, not, and, or, and not и implicates можно реализовать одним переключателем. nand, nor, xor и xnor всего двумя.


Однобитный сумматор требует четырёх вентилей и срабатывает за 2·τ, где τ — время прохождения сигналом от входа одного вентиля до входа другого, см. изображение справа. Сумматоры большей разрядности можно делать из одного однобитного сумматора и (n - 1) трёхбитных суммирующих блоков. Минимальные по размеру трёхбитные суммирующие блоки состоят из четырёх вентилей:


Однако, такие блоки работают довольно медленно: сложение n-битных чисел занимает (2n + 1)·τ, при том что используются (4n - 2) блоков. Существуют оптимизированные по скорости (неминимальные по размеру) трёхбитные сумматоры. Лучший известный автору вариант выглядит следующим обазом:


Эти блоки можно соединять как последовательно, реализуя сложение в столбик, так и деревом, реализуя сложение Когге-Стоуна.
Сложение в столбик занимает (n + 2)·τ и требует (7·n - 3) вентилей.
Сложение Когге-Стоуна занимает ⌈3 + log₂(n)⌉·τ и использует дополнительных вентилей ⌈n·log₂(n)⌉.

В случае 64-битных чисел, сложение в столбик потребует 66τ и 445 вентилей, а сложение Когге-Стоуна потребует 9τ и 957 вентилей. Компромиссные варианты, работающие за 10-12τ могут обходиться ≈500 вентилями. В предположении, что удастся реализовать баллистические (т.е. не привносящие задержки в передачу сигнала) переключатели Фредкина размеров порядка применяемых в сегодняшних процессорах транзисторов, сложение двух 64-битных можно будет производить (в совершенно реалистичных предположениях) с частотой порядка по меньшей мере миллионов ГГц.

* В тексте использованы материалы и изображения из cтатьи Bruce, Thornton et al., “Efficient Adder Circuits Based on a Conservative Reversible Logic”, Mississippi State University, IEEE 0-7695-1486-3/02, 2002.