Fredkin-poort

De Fredkin-poort (ook bekend als de CSWAP-poort) is een schakeling die geschikt is voor reversibele computatie, en werd uitgevonden door Edward Fredkin. De poort is universeel, wat betekent dat elke logische en wiskundige operatie opgebouwd kan worden uit Fredkin-poorten. De Fredkin-poort is een schakeling met drie ingangen en drie uitgangen. De poort laat het eerste bit ongeschonden en verwisselt de laatste twee bits, alleen als de eerste bit een 1 is.

Symbool voor de Fredkin-poort.

Definitie

De Fredkin-poort is een reversibele drie-bit poort die de laatste twee ingangen verwisselt als de eerste ingang een 1 is.

Waarheidstabel	Permutatiematrix
Ingangen Uitgangen C I1 I2 C O1 O2  0   0   0   0   0   0  0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1	${\begin{bmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\\\end{bmatrix}}$

De Fredkin-poort heeft als eigenschap dat het aantal nullen en enen behouden blijft.

Volledigheid

Om te zien dat de Fredkin-poort elke logische schakeling kan implementeren, toont men aan dat AND, NOT en OR realiseerbaar zijn:

Als I₂ = 0, dan O₂ = C AND I₁.

Als I₂ = 1, dan O₁ = C OR I₁.

Als I₁ = 0 dan I₂ = 1, dan O₂ = NOT C.

Voorbeeld

Full-adder opgebouwd uit vijf Fredkin-poorten.

Een full-adder kan gemaakt worden uit vijf Fredkin-poorten. De "garbage" uitgang "g" is (p NOR q) als r=0, en (p NAND q) als r=1. De adder heeft ook twee constante inputs 0 en 1.

Kwantum Fredkin-poort

De beschikbaarheid van kwantum Fredkin-poorten kan helpen met het maken van een kwantumcomputer. Kwantum poorten hebben namelijk de vereiste dat ze reversibel moeten zijn.

Zie ook

• Kwantumcomputer
• Logische poort
• Toffoli-poort

Logische poorten