Reversible Computation

Feynman Lectures on Computation을 읽는 중. 가역계산(Reversible computation)에 대한 내용이 나오길레 연습문제 삼아 조금 풀어보았다. N(Not), CN(Control-Not), CCN(Control-Control-Not) 게이트에 대한 내용.

편의상 진리표의 숫자를 이진수로 읽으면 가역계산의 경우 permutation이 된다는 것을 알 수 있다.

CN gate

CN

0->0 (00->00)

1->1 (01->01)

2->3 (10->11)

3->2 (11->10)

NC

0->0

1->3

2->2

3->1

이렇게 쓸 경우의 장점(?)은 행렬(matrix)로 쓸 수 있다는 것. 따라서 교환회로(exchange circuit)의 경우

exchange = CNxNCxCN

0->0

1->2

2->1

3->3

로 읽을 수 있다. 다음은 CCN 게이트의 permutation에 해당하는 값.

CCN gate

CCN

0->0

1->1

2->2

3->3

4->4

5->5

6->7

7->6

CNC

0->0

1->1

2->2

3->3

4->4

5->7

6->6

7->5

NCC

0->0

1->1

2->2

3->7

4->4

5->5

6->6

7->3

전부 계산하느라 헤맸는데 생각해보니 행렬로 쓸 거면 좌표변환에 해당하는 orthogonal matrix를 양쪽에 곱하면 되는거였다... OTL 다음 문제는 1-bit full adder를 reversible하게 구성하라는 문제. 진리표는 계속 permutation으로 쓰도록 하자.

1-bit full adder (A+B=S, C carry)

Z redundant(0,4)

CAB->ZCS

0->Z0

1->Z1

2->Z1

3->Z2

4->Z1

5->Z2

6->Z2

7->Z3

THIS CANNOT WORK!

보면 Z가 취할 수 있는 값이 두 가지밖에 없는데 Z1과 Z2가 각각 세 번 나오므로 3in-3out 게이트로는 가역연산을 구할 수 없다는 것을 알 수 있다. 그러므로 4in-4out 게이트를 구성해야 한다. 이건 Feynman Lectures on Computation에 언급된 내용. 다양하게 구성할 수 있겠지만 한가지 예시는 다음과 같다.

1-bit full adder (A+B=S, C carry) - hex

X redundant(0,8)

Y, Z redundant(0,4,8,C)

XCAB->YZCS

0->YZ0=0

1->YZ1=1

2->YZ1=4+1=5

3->YZ2=2

4->YZ1=8+1=9

5->YZ2=4+2=6

6->YZ2=8+2=A

7->YZ3=3

8->8

9->4

A->7

B->B

C->C

D->D

E->E

F->F

16진법을 이용해서 permutation을 구성해봤다. 보면 알겠지만 중복될 경우 0, 4, 8 순서대로 더해줘 다른 값이 나오도록 조정해주었다. 같은 색은 순환하는 성분들을 표시해준 것.

permutation이기 때문에 얻는 특이한(?) 성질은 이 연산을 반복하면 언젠가는 원래 값으로 돌아온다는 사실이다. 어쨌든 permutation group은 부분군으로 cyclic group을 형성하기 때문.

XCAB=F(YZCS) -> F^6=I , i.e. x=F(F(F(F(F(F(x))))))

아직까지는 초반부라 재미있는데, 뒤쪽에 가서도 흥미를 잃지 않았으면 한다.

---

rev. 01 Nov 2013

바로 다음에 나오는 Fredkin 게이트를 이용해 모든 논리연산 구현하기.

Fredkin Gate(Controlled exchange gate)

CAB

0->0

1->1

2->2

3->3

4->4

5->6

6->5

7->7

As AND gate: input X0Y->X(X∧Y)(￢X∧Y)

As NOT/Fanout gate: input X10->X(￢X)X

=>Construct NAND => Everything can be built out of NAND gates