여기서는 가장 간단한 불 대수(Boolean algebra)인 두 원소 대수를 다룬다. 변수는 참과 거짓에 대응하는 1과 0의 두 값을 갖는다. 이 대수는 디지털 논리와 논리 게이트를 수학적으로 기술하는 바탕이 된다.

불 대수의 합 연산 $\lor$는 논리합, 곱 연산 $\land$는 논리곱에 해당한다. $\neg x$는 $x$의 부정을 나타내는 여원이며, 논리합의 역원은 아니다. 다음 항등식들을 살펴보자. $x \land \neg x = 0$ , $x \lor \neg x = 1$ , $\neg(\neg x) = x$

진리표(truth table)는 가능한 입력 조합마다 출력값을 정리한 표다. 진리표로 불 함수를 정의할 수 있고, 반대로 주어진 진리표를 불 변수의 논리식으로 표현할 수도 있다. 앞의 항등식들은 각 입력에 대한 진리표를 비교하여 증명할 수 있다.

아래는 네 가지 이항 연산에 대한 진리표이다.

$\neg (x \oplus y) = x \odot y$ 이다. XNOR는 $x \leftrightarrow y$ 로도 쓴다. $x$와 $y$를 명제로 보면, 두 명제의 진릿값이 같을 때 참이 되는 동치 연산이다.

• $x \lor 1 = 1$ , $x \land 0 = 0$

• $x \lor x = x$ , $x \land x = x$

• $x \land (x \lor y) = x$ , $x \lor (x \land y) = x$

• $x \land (y \lor z) = (x \land y ) \lor (x \land z)$

• $x \lor (y \land z) = (x \lor y ) \land (x \lor z)$

드모르간의 법칙 $$\begin{aligned} \neg x \land \neg y &= \neg (x \lor y)\\ \neg x \lor \neg y &= \neg (x \land y) \end{aligned}$$

주어진 진리표와 같은 출력을 내는 논리식을 어떻게 만들까? NOT, AND, OR만 조합해도 모든 불 함수를 표현할 수 있다.

먼저 두 비트열이 같을 때만 $1$을 출력하는 함수를 만들자. 비트열 $X$의 $i$번째 비트를 $x_i$, 비트열 $Y$의 $i$번째 비트를 $y_i$라 하자. 두 비트열 $X$와 $Y$가 같을 때만 $1$이 되는 함수는 다음과 같다. $$X \odot Y := (x_{1} \odot y_{1}) \land (x_{2} \odot y_{2}) \land\cdots\land (x_{n} \odot y_{n})$$ 이 함수는 $X$와 $Y$의 각 자리 비트를 비교한다.

$X$가 정해져 있으면 다음 항등식을 이용할 수 있다. $$x \odot y = \begin{cases} \neg y, & x = 0\\ y, & x = 1 \end{cases}$$

이제 $n$개의 비트를 입력받는 불 함수 $f$를 생각하자. 출력이 $1$인 입력들의 집합을 $\{X_i\}_{i=1}^{m}$이라 하자. 그러면 $f(X_i) = 1$ 이고, 이 집합에 속하지 않는 입력에서 $f$의 값은 $0$이다.

이 함수는 다음과 같이 표현된다. $$f(Y) := (X_1 \odot Y) \lor (X_2 \odot Y) \lor \cdots \lor (X_m \odot Y)$$ 이러한 형태를 논리합 표준형(disjunctive normal form, DNF)이라 한다. 출력이 $1$인 입력이 없으면 $f=0$ 이다.

XOR의 논리합 표준형을 구해 보자. 위 식에서 $x = y_1$ , $y = y_2$ 로 놓으면 $$\begin{aligned} x \oplus y &= ( (0 \odot x) \land (1 \odot y) ) \lor ( (1 \odot x) \land (0 \odot y) )\\ &= (\neg x \land y) \lor (x \land \neg y) \end{aligned}$$이다. XNOR의 논리합 표준형은 다음과 같다. $$x \odot y = (x \land y) \lor (\neg x \land \neg y)$$ [질문] $x \odot y = \neg (x \oplus y)$ 와 앞서 구한 XOR의 논리합 표준형을 이용하여 이 식을 유도하자.

같은 함수를 나타내는 논리식은 여러 가지다. 카르노 맵(Karnaugh map)이나 콰인–매클러스키(Quine–McCluskey) 방법으로 논리합 표준형을 단순화할 수 있다. 실제 회로를 구현할 때는 하드웨어에 적합한 형태로 최적화하기도 한다.

논리 게이트는 불 연산을 수행하는 기본 단위다. 게이트를 연결하여 연산의 흐름을 나타낸 것이 논리 회로다. 회로도를 보면 동시에 수행할 수 있는 연산, 순서대로 수행해야 하는 연산, 배선의 복잡도를 파악할 수 있다.

NAND는 AND의 결과에 NOT을 적용하는 게이트다. NAND 게이트만 조합해도 모든 불 함수를 구현할 수 있으므로, NAND를 보편 게이트(universal gate)라 한다.

• $\neg (x \land x) = \neg x$ 이므로 NOT 게이트를 대체할 수 있다.

• NAND와 NOT을 조합하여 AND를 만들 수 있다.

• $\neg ((\neg x) \land (\neg y)) = x \lor y$ 임을 이용하여 OR을 만들 수 있다.

따라서 새로운 소재나 설계로 디지털 회로를 만들 때, NAND 게이트를 구현하고 연결할 수 있으면 논리적으로는 모든 불 함수를 구현할 수 있다.

전자식 논리 게이트는 보통 트랜지스터로 만든다. 아래 회로는 무슨 게이트인가?

$V_{\mathrm{CC}}$는 전원이다. 베이스(base) 전류가 충분하면 NPN 트랜지스터가 켜져 컬렉터(collector)에서 이미터(emitter)로 전류가 흐른다. 두 입력 전압이 모두 높을 때만 출력 전압이 낮아진다. 실제 회로에서는 전압과 저항을 적절한 범위로 정해야 한다.

가장 간단한 덧셈 회로인 반가산기(half adder)를 살펴보자. 두 1비트 이진수를 더하면 합 비트와 올림 비트가 각각 어떻게 정해지는가?

합 비트는 XOR로, 올림 비트는 AND로 구한다. 여러 자릿수의 덧셈에서는 아랫자리에서 넘어온 올림도 더해야 한다. 반가산기 두 개와 OR 게이트로 전가산기를 만들고, 전가산기들을 연결하면 된다.

반가산기의 합 비트 $s$와 올림 비트 $c$. 배선이 교차하는 곳의 점은 두 배선이 연결되어 있음을 뜻한다.

두 입력 비트 $x,y$뿐 아니라 아랫자리에서 넘어온 올림 $c_{\mathrm{in}}$도 더해야 한다. 첫 반가산기의 출력을 $s_1,c_1$, 둘째의 출력을 $s,c_2$라 하자.

$x+y=s_1+2c_1$ 이고 $s_1+c_{\mathrm{in}}=s+2c_2$ 이므로 $$x+y+c_{\mathrm{in}}=s+2(c_1+c_2)=s+2c_{\mathrm{out}}.$$이다. $c_1=1$ 이면 $s_1=0$ 이므로 $c_2=0$ 이다. 따라서 $c_1,c_2$가 동시에 1일 수 없으며, 두 올림 비트의 합은 OR 연산의 결과와 같다.

튜링 기계(Turing machine)는 계산 과정을 수학적으로 기술한 모형이다. 튜링은 이 모형을 통해 기계적인 절차로는 해결할 수 없는 계산 문제가 있음을 보였다.

튜링 기계는 무한히 긴 테이프, 기호를 읽고 쓰는 헤드, 유한한 내부 상태로 기술된다. 현재 상태와 읽은 기호에 따라 쓸 기호, 헤드의 이동 방향, 다음 상태를 정한다. 이 규칙을 전이 함수(transition function)라 한다.

유한한 기계적 절차로 계산할 수 있는 함수는 튜링 기계로도 계산할 수 있다는 주장을 처치–튜링 논제(Church–Turing thesis)라 한다.

이 논제는 비형식적인 “기계적 절차에 의한 계산”과 수학적 계산 모형을 연결한다. 여기서 계산 가능성은 계산 속도와 다른 개념이다. 한편 튜링 계산 가능성과 부분 재귀 함수로의 표현 가능성이 동치라는 명제는 수학적 정리다.

적절한 입력을 받아 임의의 튜링 기계를 모사할 수 있는 튜링 기계를 보편 튜링 기계(universal Turing machine)라 한다. 그 구성 방법은 여러 가지이며, 테이프의 기호를 $0$과 $1$ 두 종류로 제한해도 구성할 수 있다.

튜링 기계보다 더 많은 종류의 함수를 계산할 수 있는 계산 기계는 없을까?

어떤 계산 모형이나 프로그래밍 언어가 튜링 기계를 모사할 수 있으면, 그 모형은 튜링 기계가 할 수 있는 계산을 모두 수행할 수 있다. 이 성질을 튜링 완전성(Turing completeness)이라 한다.

통신의 한 과제는 송신자가 고른 메시지 $M$을 수신자가 알아내게 하는 것이다. 신호가 도착하더라도 잡음 때문에 메시지를 잘못 읽을 수 있다. 수신자의 추정값을 $\widehat M$이라 하자. $$P_{\mathrm{err}}=\Pr(\widehat M\ne M).$$ 정보원 부호화 (source coding)는 메시지를 효율적으로 표현하여 평균 길이를 줄이는 과정이다. 채널 부호화 (channel coding)는 중복 정보를 추가하여 잡음이 있어도 메시지를 구별할 수 있게 하는 과정이다. 압축과 오류 정정은 목적이 다르므로 함께 사용할 수 있다.

한 번의 채널 사용과 1초는 같은 단위가 아니다. 이하에서는 주로 채널 사용 한 번당 전달하는 비트 수를 센다.

아래 세 가지를 구별하며 읽자.

• 어떤 메시지를 보내는가?

• 어떤 채널과 사전 자원을 사용하는가?

• 오류를 얼마나 허용하며, 비용은 무엇으로 세는가?

참고: [SH48]. 통신 모형과 두 종류의 부호화.

확률변수 $X$가 값 $x$을 가질 확률을 $p(x)$라 하자. 이 결과의 정보량은 $-\log_2p(x)$이며, 그 평균을 섀넌 엔트로피(Shannon entropy)라 한다. $$H(X)=-\sum_x p(x)\log_2p(x).$$ 로그의 밑이 2이므로 단위는 비트다. 연속성을 이용하여 $0\log_2 0=0$ 으로 정한다. 항상 같은 결과가 나오면 $H=0$ 이고, 0과 1이 같은 확률로 나오는 이진 정보원이면 $H=1$ 이다.

$\Pr(X=1)=q$ 인 이진 정보원에 대해서는 $$h_2(q)=-q\log_2q-(1-q)\log_2(1-q).$$ 엔트로피는 물리적 큐비트 수나 진폭 개수와 같은 양이 아니다.

예를 들어 $q=0.1$ 이면 엔트로피는 $H(X)\simeq0.469$ 비트다. 독립적으로 반복되는 긴 메시지에서는 이 값이 무손실 압축의 점근적 한계를 정한다. 각 결과를 반드시 $0.469$개의 이진 기호로 적어야 한다는 뜻은 아니다. 기호 사이에 상관관계가 있으면 개별 기호의 엔트로피가 아니라 긴 기호열의 엔트로피율을 고려해야 한다.

참고: [SH48]. 여기서는 독립·동일분포 정보원의 기초만 다룬다.

보낸 비트가 독립적으로 확률 $p$로 뒤집히는 이진 대칭 채널 (binary symmetric channel, BSC)을 생각하자. $$Y=X\oplus N,\qquad \Pr(N=1)=p,\quad 0\le p\le\tfrac12.$$ $N$은 $X$와 독립이다. $p=1/2$ 이면 출력은 입력에 대한 정보를 주지 않는다. 수신값을 통해 입력에 대해 얻는 평균 정보는 상호정보량 (mutual information)이다. $$I(X;Y)=H(Y)-H(Y\mid X).$$ 조건부 엔트로피 $H(Y\mid X)$는 $X$를 알고도 남는 $Y$의 평균 불확실성이다. 입력 분포까지 최적화한 최댓값이 이 채널의 용량이다. $$C=\max_{p(x)}I(X;Y)=1-h_2(p).$$

$k$비트 메시지를 보내는 데 채널을 $n$번 사용하면 전송률은 $R=k/n$ 이다. 이 무기억 채널 (memoryless channel)에서는 $R<C$ 일 때 충분히 긴 부호를 적절히 선택하여 블록 오류 확률을 작게 할 수 있다. 어떤 부호나 이러한 성능을 낸다는 뜻도, 유한한 부호 길이에서 오류가 전혀 없다는 뜻도 아니다.

참고: [SH48]. 용량은 채널 사용 한 번당 비트 수다.

메시지를 전송·저장할 비트열에 대응시키는 것을 부호화(encoding)라 한다. 부호화는 데이터 압축에도 사용하지만, 여기서는 오류를 줄이기 위한 부호화를 다룬다.

앞서 본 통신 채널뿐 아니라 고전적인 저장과 연산에도 오류가 생길 수 있다. 여기서는 독립적인 비트 반전만 가정한다. 가장 단순한 방법은 $0\mapsto000$ , $1\mapsto111$ 로 세 번 반복하고 다수결로 읽는 것이다. 각 비트가 독립적으로 확률 $\epsilon$로 뒤집힌다고 하자.

$0$을 부호화하여 보냈는데 다수결 결과가 $1$이 될 확률은 $\epsilon^3 + 3(1-\epsilon)\epsilon^2 = 3\epsilon^2 - 2 \epsilon^3$ 이다. 이는 $0<\epsilon<1/2$ 일 때 반복 없이 보낸 오류 확률 $\epsilon$보다 작으며, $\epsilon\ll1$ 이면 $3\epsilon^2$에 가깝다.

두 비트열의 해밍 거리(Hamming distance)는 서로 다른 자리의 수다. 아래의 a와 b는 첫째와 셋째 자리에서 다르므로 거리가 2다. 부호 거리(code distance)는 서로 다른 부호어 쌍의 해밍 거리 중 최솟값이다.

위 부호의 거리는 $2$다. 거리가 $d$인 부호는 최대 $\lfloor d-1 \rfloor$ 개의 비트 반전 오류를 검출하거나, 최대 $\lfloor (d-1)/2 \rfloor$개의 비트 반전 오류를 정정할 수 있다. [질문] 검출과 정정에 필요한 거리 조건이 왜 다른가?

$\Pr(X=1)=q$ 라 하면 $$r:=\Pr(Y=1)=(1-q)p+q(1-p)=p+q(1-2p).$$ 어떤 $X$를 고정해도 $Y$의 조건부 엔트로피는 $h_2(p)$다. 따라서 $$I(X;Y)=h_2(r)-h_2(p).$$ 이진 엔트로피는 $1$ 이하이고 $q=1/2$ 이면 $r=1/2$ 이므로 $$\max_q I(X;Y)=1-h_2(p).$$ $p=1/2$ 일 때는 모든 $q$에 대해 $I=0$ 이다. $p=0$ 일 때는 $I=h_2(q)$ 이며 균등한 입력에서 용량 $1$을 얻는다.

$p=0.1$ 인 예를 살펴보자. $$C=1-h_2(0.1)\simeq0.531.$$ 각 비트를 세 번 반복하여 보내고 다수결로 복호하면, 오류가 두 번 또는 세 번 발생한 경우에 잘못 판정한다. $$p_{\mathrm{rep}}=3p^2(1-p)+p^3=3p^2-2p^3.$$ $$p_{\mathrm{rep}}=0.028,\qquad R_{\mathrm{rep}}=\frac13.$$ 오류 확률은 줄지만, 한 비트를 보내는 데 채널을 세 번 사용한다. 이 유한 길이의 부호가 채널 용량을 달성하는 것은 아니다.

$p=0$ , $p=1/2$ 에서는 무엇이 달라지는가? 독립성 가정을 버리면 $3p^2-2p^3$ 을 그대로 쓸 수 있는가?

참고: [SH48]. 앞서 본 반복 부호의 원리는 뒤의 양자 오류 정정 부분과 연결된다.

고전 비트는 0 또는 1을 나타낸다. 큐비트(qubit)는 두 기저 상태 $\left|0\right\rangle,\left|1\right\rangle$을 갖는 양자계다. 먼저 순수 상태를 다루자. $$\left|\psi\right\rangle=\alpha\left|0\right\rangle+\beta\left|1\right\rangle,\qquad |\alpha|^2+|\beta|^2=1.$$ 두 기저 상태 $\left|0\right\rangle,\left|1\right\rangle$를 구별하는 측정에서는 0 또는 1을 얻으며, 각 결과의 확률은 $$\Pr(0)=|\alpha|^2,\qquad \Pr(1)=|\beta|^2$$이다. 한 번의 측정으로 $\alpha,\beta$를 모두 읽어 내는 것은 아니다.

예를 들어 $\left|\psi\right\rangle=\sqrt3\left|0\right\rangle/2+\left|1\right\rangle/2$ 이면 두 측정 결과의 확률은 $3/4,1/4$다. 이 확률을 실험으로 확인하려면 매번 같은 상태를 새로 준비한 뒤 측정하는 과정을 반복한다.