通用、可逆Fredkin门的设计与测试
5.00/5 (6投票s)
2020年4月2日
10分钟阅读
16535
216
使用标准TTL集成电路实现Fredkin门，并通过Arduino Uno微控制器板进行测试
引言
Fredkin门由Edward Fredkin和Tommaso Toffoli在其题为“Conservative Logic”（International Journal of Theoretical Physics, 21 [3-4]: pp. 219-253）的论文中首次提出。下图展示了Fredkin门的符号（左）及其功能（中、右）。
输入信号u作为控制信号，而输入信号x1和x2是数据信号。输出信号是v、y1和y2。根据功能描述，v始终与u相同。当v = 1时，输出与输入相同（y1 = x1，y2 = x2）。当v = 0时，输出与输入交换（y1 = x2，y2 = x1）。因此，当控制信号v为1时，Fredkin门实现了一个SWAP操作。
Fredkin门是通用的，因为它们可以用来实现任何逻辑函数，如下图所示，其中AB表示逻辑AND，A + B表示逻辑OR，A’表示逻辑NOT。
Fredkin门也是可逆的，因为SWAP操作是其自身的逆操作。如果一个Fredkin门的输出信号（v, y1, y2）分别连接到第二个Fredkin门的输入信号（u, x1, x2），那么第二个门的输出信号将与第一个门的输入信号相同。SWAP操作的可逆性可以通过以下简单的Unmanaged C++ (Win32)控制台应用程序来演示，该程序实现了宏和函数两种形式的SWAP操作。
// Implementation and testing of the self-inverse 'swap' operation
// both in terms of a macro and a function.
//
// Programmer: Jorge L. Orejel
//
// Last update: 03/30/2020
//
// Based on: Intel 80X86 and Motorola 68000 assembly code and Borland
// C++ code written in 1991.
#include "stdafx.h"
#include <stdio.h>
// Macro implementation of 'swap' operation.
//
#define SWAP( x, y ) { x ^= y; y ^= x; x ^= y; }
// Functional implementation of the 'swap' operation
//
void Swap( int *x, int *y )
{
*x ^= *y;
*y ^= *x;
*x ^= *y;
}// Swap
void Display_int_x_y( int x, int y )
{
printf( "\nx == %d, y == %d\n\n", x, y );
}// Display_int_x_y
void DisplayIntSWAP( int x, int y )
{
printf( "SWAP( x, y ): x == %d, y == %d\n", x, y );
}// DisplayIntSWAP
void Display_char_x_y( char x, char y )
{
printf( "\nx == '%c', y == '%c'\n\n", x, y );
}// Display_char_x_y
void DisplayCharSWAP( char x, char y )
{
printf( "SWAP( x, y ): x == '%c', y == '%c'\n", x, y );
}// DisplayIntSWAP
void DisplaySwap( int x, int y )
{
printf( "Swap( x, y ): x == %d, y == %d\n", x, y );
}// DisplaySwap
int _tmain( int argc, _TCHAR* argv[] )
{
int x = 333, y = 666;
char chX = 'A', chY = 'z';
Display_int_x_y( x, y );
SWAP( x, y );
DisplayIntSWAP( x, y );
Swap( &x, &y );
DisplaySwap( x, y );
Display_char_x_y( chX, chY );
SWAP( chX, chY );
DisplayCharSWAP( chX, chY );
SWAP( chX, chY );
DisplayCharSWAP( chX, chY );
printf( "\n" );
return 0;
}// _tmain
请注意，与通常使用临时变量的教科书代码不同，前面的程序通过三次应用异或（XOR）运算符（C/C++/C#中的“^”）来实现SWAP操作。程序执行后，将产生以下输出。（此外，与Swap函数不同，SWAP宏可以应用于任何标量数据类型。）
x == 333, y == 666
SWAP( x, y ): x == 666, y == 333
Swap( x, y ): x == 333, y == 666
x == 'A', y == 'z'
SWAP( x, y ): x == 'z', y == 'A'
SWAP( x, y ): x == 'A', y == 'z'
按任意键继续 . . .
Fredkin门不仅仅是逻辑门设计的理论练习，它们在可逆计算和量子计算中都有重要的应用。
Fredkin门的设计实现
下图以普通逻辑运算的方式展示了Fredkin门的功能，其中信号名上方的横线表示取反（NOT），两个信号并列表示与（AND），圆圈加号表示异或（XOR）运算。
上图中Fredkin门的输出信号Q和R可以使用标准的TTL集成电路7404（六反相器）、7408（四与门）和7486（四异或门）来实现。这些TTL集成电路芯片的引脚分配如下。
以下两图展示了两个Fredkin门的设计。Fredkin门A是第一个，其输入为C（控制）、A和B（数据），输出为C、A’、B’（引号不表示取反）。Fredkin门B是第二个，其输入为C（控制）、A’和B’（数据），输出为C、A和B。Fredkin门B的数据输出被标记出来，以表明如果Fredkin门A的输出按照前面所述连接到Fredkin门B的输入，则门B的输出将与门A的输入相同。发光二极管（LED）没有零件号。它们是普通的微型LED（矩形黄色LED长度为7毫米，圆形绿色和琥珀色LED长度为5毫米）。在物理实现图中，省略了连接到Fredkin门A的A’和B’输出的LED。请注意，LED采用负逻辑连接：如果信号为逻辑0，则连接到它的LED将亮起，而如果信号为逻辑1，则LED将熄灭。NOT、AND和XOR门的输出信号标签以C/C++/C#布尔（bool）表达式的格式书写。
Fredkin门A
Fredkin门B
两个Fredkin门串联的物理接线
下图显示了两个Fredkin门在原型板上的接线。从左到右，四个TTL集成电路芯片分别是：一个74LS04（六反相器）、两个74LS08（四与门）和一个74LS86（四异或门）。“LS”表示“低功耗肖特基”，但此版本的TTL集成电路与非LS版本相比，在设计上没有区别。
原型板左侧的矩形黄色LED以及两个圆形绿色和琥珀色LED分别显示了Fredkin门A输入C、A和B的状态。右侧的黄色、绿色和琥珀色LED显示了Fredkin门A输出C、A’和B’的状态。这些信号分别连接到Fredkin门B的输入C、A’和B’。第二个74LS08和74LS86集成电路芯片之间的圆形绿色和琥珀色LED分别显示了Fredkin门B的A和B输出信号，这些信号的状态（亮或灭）应与连接到Fredkin门A的A和B输入的绿色和琥珀色LED相同，从而证明了Fredkin门的可逆性。（由于原型板上连接孔的限制，Fredkin门B输出对应的矩形黄色LED未连接。）原型板使用Belker Universal AC Adapter型号PA-30120W-ZMX供电。
Fredkin门的手动测试
以下八张图片显示了Fredkin门A输入信号（C, A and B）所有八种可能组合的LED状态。请记住，LED采用负逻辑工作：如果信号为逻辑0，则连接到它的LED亮起，而如果信号为逻辑1，则LED熄灭。信号的逻辑值以及门执行的操作显示在每张图片的顶部。
C = 0, A = 0, B = 0 (无SWAP)
C = 0, A = 0, B = 1 (无SWAP)
C = 0, A = 1, B = 1 (无SWAP)
C = 0, A = 1, B = 0 (无SWAP)
C = 1, A = 0, B = 0 (SWAP)
C = 1, A = 0, B = 1 (SWAP)
C = 1, A = 1, B = 1 (SWAP)
C = 1, A = 1, B = 0 (SWAP)
前面八张图片中的LED负逻辑状态证明了可逆Fredkin门的正确接线和预期操作：Fredkin门A的输出A’和B’是其输入A和B的交换值，而Fredkin门B的输出A和B是其输入A’和B’的交换值，并且与Fredkin门A的输入相同。
Fredkin门的自动化测试
为了自动化Fredkin门的测试，Fredkin门A的输入（C, A, and B）分别连接到Arduino Uno微控制器板的数字输入/输出引脚13、12和11。接地（GND）线连接到原型板的接地轨（“-”）。下图显示了连接方式。
Arduino Uno板通过USB线连接到Dell Inspiron mini笔记本电脑的串行端口COM4。之后，由于在三台其他笔记本电脑上使用Windows 10 Home和Windows 7 Ultimate and Professional访问COM端口时出现问题，该板被连接到运行Windows 10 Pro的Toshiba Satellite笔记本电脑的COM3端口。（原型板上的矩形黄色LED和圆形绿色、琥珀色LED的状态对应于Fredkin门A的输入C = 1, A = 0, B = 1。）Arduino IDE用于编写以下C++ Sketch来驱动Fredkin门A的输入。
// Computer: Toshiba Satellite C55D-B5308 laptop.
// Operating system: Windows 10 Pro.
// Compiler: Arduino 1.8.2.
//
// C:\Users\Jorge\Documents\Arduino\Fredkin Gates\Fredkin\Fredkin.ino
// C++ Sketch program to test the circuit implementing two Fredkin
// gates connected in cascade.
//
// Programmer: Jorge L. Orejel
//
// Last update: 04/01/2020 : Execution on a Toshiba Satellite C55D-B5308 laptop.
//
// 03/25/2020 : Original coding and execution on a Dell Inspiron laptop.
//
int C = 13; // Control pin
String Cname = "C";
int A = 12; // Data A pin
String Aname = "A";
int B = 11; // Data B pin
String Bname = "B";
void setup()
{
pinMode( C, OUTPUT );
pinMode( A, OUTPUT );
pinMode( B, OUTPUT );
digitalWrite ( C, LOW ); // Inactive state
digitalWrite( A, HIGH );
digitalWrite( B, HIGH );
Serial.begin( 9600 );
} // Setup
void TogglePin( int pin, String pinName )
{
int state = digitalRead( pin ), _state;
Serial.print( pinName );
Serial.print( ": " );
Serial.print( state );
Serial.print( " -> " );
Serial.print( !state );
digitalWrite( pin, !state );
Serial.println();
} // TogglePin
void SetPin( int pin, String pinName, int newState )
{
int currentState = digitalRead( pin );
if ( currentState != newState )
{
if ( newState == 0 )
{
digitalWrite( pin, LOW );
}
else
{
digitalWrite( pin, HIGH );
}
Serial.print( pinName );
Serial.print( ": " );
Serial.print( currentState );
Serial.print( " -> " );
Serial.print( newState );
Serial.println();
}
} // SetPin
void loop()
{
if ( Serial.available() > 0 )
{
Serial.println( "---------" );
delay( 4000 ); // Delay 4000 microseconds (4 seconds)
TogglePin( C, Cname );
for ( int i = 0; i < 2; ++i )
{
delay( 3000 );
SetPin( A, Aname, i );
delay( 3000 );
SetPin( A, Aname, !i );
for ( int j = 0; j < 2; ++j )
{
delay( 3000 );
SetPin( B, Bname, j );
delay( 3000 );
SetPin( B, Bname, !j );
}
}
}
} // loop
前面的C++ Sketch模拟了Fredkin门的手动测试，涵盖了Fredkin门A输入信号（C, A, and B）的所有组合。将Arduino板连接到计算机的USB端口后，选择Tools->Port可以在Arduino IDE中指定板所连接的COM端口。选择Sketch->Verify/Compile可以运行C++编译器以检查错误。选择Sketch->Upload可以将编译无误的代码传输到Arduino闪存中。选择Tools->Serial Monitor可以打开串行监视器窗口，该窗口包含一个显示区域（用于显示Serial.print和Serial.println命令的输出）和一个标有Send的按钮。单击该按钮将启动C++ Sketch，先执行一次Setup函数，然后无限期地执行loop函数，直到函数执行exit( 0 )或Arduino板断电。执行前面的C++ Sketch将产生与手动测试相同的LED状态。
通过C#程序与Arduino板上运行的C++ Sketch通信来自动化测试Fredkin门
这两个Fredkin门也可以通过.NET框架中的C#程序进行测试，该程序通过串行（COM）端口与适当的Arduino C++ Sketch通信，例如以下程序。（调用库函数delay用于模拟门的手动测试。）
// Computer: Toshiba Satellite C55D-B5308 laptop.
// Operating system: Windows 10 Pro.
// Compiler: Arduino 1.8.2.
//
// C:\Users\Jorge\Documents\Arduino\ReceiveFrom_NET\ReceiveFrom_NET.ino
//
// Sketch C++ program to receive commands from a .NET C# console application to set
// the states '0' or '1' of the 'C' (control), and 'A', 'B' inputs to Fredkin Gate A.
//
// Arduino Uno on COM3.
//
// Programmer: Jorge L. Orejel
//
// Last update: 04/01/2020
int C = 13; // Control pin
String Cname = "C";
int A = 12; // Data A pin
String Aname = "A";
int B = 11; // Data B pin
String Bname = "B";
void setup()
{
pinMode( C, OUTPUT );
pinMode( A, OUTPUT );
pinMode( B, OUTPUT );
digitalWrite( C, LOW ); // Inactive state
digitalWrite( A, HIGH );
digitalWrite( B, HIGH );
Serial.begin( 9600 );
} // setup
void SetPin( int pin, String pinName, int newState )
{
int currentState = digitalRead( pin );
if ( currentState != newState )
{
if ( newState == 0 )
{
digitalWrite( pin, LOW );
}
else
{
digitalWrite( pin, HIGH );
}
Serial.print( pinName );
Serial.print( ": " );
Serial.print( currentState );
Serial.print( " -> " );
Serial.print( newState );
Serial.println();
}
} // SetPin
void loop()
{
char inputChar;
if ( Serial.available() > 0 )
{
delay( 3000 );
inputChar = Serial.read();
delay( 3000 );
switch ( inputChar )
{
case '0': SetPin( C, Cname, 0 ); SetPin( A, Aname, 0 ); SetPin( B, Bname, 0 );
delay( 3000 );
break;
case '1': SetPin( C, Cname, 0 ); SetPin( A, Aname, 0 ); SetPin( B, Bname, 1 );
delay( 3000 );
break;
case '2': SetPin( C, Cname, 0 ); SetPin( A, Aname, 1 ); SetPin( B, Bname, 1 );
delay( 3000 );
break;
case '3': SetPin( C, Cname, 0 ); SetPin( A, Aname, 1 ); SetPin( B, Bname, 0 );
delay( 3000 );
break;
case '4': SetPin( C, Cname, 1 ); SetPin( A, Aname, 0 ); SetPin( B, Bname, 0 );
delay( 3000 );
break;
case '5': SetPin( C, Cname, 1 ); SetPin( A, Aname, 0 ); SetPin( B, Bname, 1 );
delay( 3000 );
break;
case '6': SetPin( C, Cname, 1 ); SetPin( A, Aname, 1 ); SetPin( B, Bname, 1 );
delay( 3000 );
break;
case '7': SetPin( C, Cname, 1 ); SetPin( A, Aname, 1 ); SetPin( B, Bname, 0 );
delay( 3000 );
break;
default: ;
}
}
} // loop
前面的程序与用于测试两个Fredkin门的独立C++ Sketch的编译和上传方式相同。在这种情况下，由于COM3端口正在使用，串行监视器无法运行。程序的loop函数 continuously reads commands sent by the following C# program running on the host computer.（程序的loop函数不断读取运行在主机上的以下C#程序发送的命令。）
// Computer: Toshiba Satellite C55D-B5308 laptop.
// Operating system: Windows 10 Pro.
// Compiler: C# on Visual Studio 2010.
//
// C:\Users\Jorge\Documents\Visual Studio 2010\Projects\C#
// \SendTo_Arduino\Program.cs
//
// Program to send commands to the Arduino Uno microcontroller
// board in order to set the states of the input signals 'C'
// (control) and 'A', 'B' (data) of Fredkin Gate A.
//
// Programmer: Jorge L. Orejel
//
// Last update: 04/01/2020
using System;
using System.IO.Ports;
namespace Fredkin
{
class Program
{
static void Main( string[] args )
{
try
{
bool running = true;
Console.CancelKeyPress
+= delegate( object sender, ConsoleCancelEventArgs e )
{
e.Cancel = true; running = false;
};
ListCOMports();
SerialPort serialPort = new SerialPort( "COM3", 9600 );
serialPort.Open();
if ( serialPort.IsOpen )
{
Console.WriteLine( "Serial port COM3 open\n" );
Console.WriteLine( "Press CTRL+C to exit\n" );
char[] command = new char[ 1 ];
command[ 0 ] = '0';
Console.WriteLine( "-----------------" );
while ( running )
{
Console.WriteLine( "command[ 0 ] == {0}", command[ 0 ] );
serialPort.Write( command, 0, 1 );
System.Threading.Thread.Sleep( 3000 );
if ( command[ 0 ] == '7' )
{
command[ 0 ] = '0';
Console.WriteLine( "-----------------" );
}
else
{
++command[ 0 ];
}
}
serialPort.Close();
}
}
catch ( Exception exc )
{
Console.WriteLine( "Exception: {0}", exc.Message );
}
Console.WriteLine( "\nProgram exit." );
Console.WriteLine();
}// Main
public static void ListCOMports()
{
Console.WriteLine( "\nCOM ports available:" );
foreach ( string str in SerialPort.GetPortNames() )
{
Console.WriteLine( "\t{0}", str );
}
Console.WriteLine();
}// ListCOMports
}// Program (class)
}// Fredkin (namespace)
按CTRL-C之前，前面控制台应用程序的输出如下：
COM ports available:
COM3
Serial port COM3 open
Press CTRL+C to exit
-----------------
command[ 0 ] == 0
command[ 0 ] == 1
command[ 0 ] == 2
command[ 0 ] == 3
command[ 0 ] == 4
command[ 0 ] == 5
command[ 0 ] == 6
command[ 0 ] == 7
-----------------
command[ 0 ] == 0
command[ 0 ] == 1
command[ 0 ] == 2
command[ 0 ] == 3
Program exit.
Press any key to continue . . .
以下四张图片显示了运行在主机上的C#程序与运行在Arduino板闪存中的C++ Sketch交互期间，原型板上LED的状态。前两张图片中，控制信号C为0，两个Fredkin门的输出与其输入相同，而后两张图片中，控制信号为1，Fredkin门的输出对应于交换后的输入。请记住，LED采用负逻辑连接（亮=0，灭=1）。
Fredkin门A：输入 C = 0, A = 0, B = 1, 输出 A’ = 0, B’ = 1;
Fredkin门B：输入 A’ = 0, B’ = 1, 输出 A = 0, B = 1
Fredkin门A：输入 C = 0, A = 1, B = 0, 输出 A’ = 1, B’ = 0;
Fredkin门B：输入 A’ = 1, B’ = 0, 输出 A = 1, B = 0
Fredkin门A：输入 C = 1, A = 0, B = 1, 输出 A’ = 1, B’ = 0;
Fredkin门B：输入 A’ = 1, B’ = 0, 输出 A = 0, B = 1
Fredkin门A：输入 C = 1, A = 1, B = 0, 输出 A’ = 0, B’ = 1;
Fredkin门B：输入 A’ = 0, B’ = 1, 输出 A = 1, B = 0
结论
本文介绍了使用标准晶体管-晶体管逻辑集成电路实现通用、可逆Fredkin门的设计。通过手动测试、使用Arduino Uno微控制器板进行自动化测试以及通过C#程序（在主机上运行）与Arduino板上运行的C++ Sketch进行交互的自动化测试，验证了设计的正确功能。Fredkin门可以作为构建更复杂逻辑电路的构建块，并在可逆计算和量子计算中具有重要的应用。
历史
- 2020年4月2日：初版
许可证
本文及其任何相关源代码和文件均根据MIT许可证（https://open-source.org.cn/licenses/MIT）和The Code Project Open License (CPOL: https://codeproject.org.cn/info/cpol10aspx)授权。