2013. 10. 29. 22:22 Programme

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


'Programme' 카테고리의 다른 글

[C] Entering strings including <space>  (0) 2010.09.11
[C] Conway's Game of Life  (4) 2010.06.25
[C] Pseudorandom number generator  (0) 2010.06.14
C언어 달팽이(나선)배열  (7) 2010.04.26
Posted by 덱스터

블로그 이미지
A theorist takes on the world
덱스터
Yesterday
Today
Total

달력

 « |  » 2024.3
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

최근에 올라온 글

최근에 달린 댓글

글 보관함