정답
① \(110011_2 \rightarrow\) 그레이 코드 : \(101010\)
② \(g_5g_4g_3g_2g_1g_0 = 100101 \rightarrow\) 2진수 : \(111001_2\)
③ 덧셈 연산을 대체하는 공통 논리 게이트 : 배타적 논리합 게이트(XOR 게이트)
출제 의도
그레이 코드와 2진수 사이의 변환 규칙을 이해하고, 실제 비트열에 적용하여 서로 변환할 수 있는지를 묻는다. 또한 캐리를 무시한 2진 덧셈이 어떤 논리 게이트의 동작과 같은지 파악하여, 그레이 코드 변환 과정을 논리 회로 관점에서 해석할 수 있는지 평가한다.
풀이 과정
문제에서 주어진 변환 규칙은 다음과 같다.
2진수 \(b_{n-1}\cdots b_1b_0\) → 그레이 코드 \(g_{n-1}\cdots g_1g_0\) 일 때
$$ g_{n-1} = b_{n-1}, \qquad g_i = b_{i+1} + b_i \quad (i = n-2,\dots,1,0) $$
그레이 코드 \(g_{n-1}\cdots g_1g_0\) → 2진수 \(b_{n-1}\cdots b_1b_0\) 일 때
$$ b_{n-1} = g_{n-1}, \qquad b_i = g_i + b_{i+1} \quad (i = n-2,\dots,1,0) $$
여기서 \(+\)는 캐리를 무시한 2진 덧셈, 즉 각 비트끼리만 더한 것으로 생각한다.
① 먼저 6비트 2진수 \(b_5b_4b_3b_2b_1b_0 = 110011\) 을 그레이 코드로 바꾼다.
$$ b_5 = 1,\; b_4 = 1,\; b_3 = 0,\; b_2 = 0,\; b_1 = 1,\; b_0 = 1 $$
최상위 비트는 그대로이므로
$$ g_5 = b_5 = 1 $$
이제 왼쪽에서 오른쪽으로 진행하며
$$ \begin{aligned} g_4 &= b_5 + b_4 = 1 + 1 = 0,\\ g_3 &= b_4 + b_3 = 1 + 0 = 1,\\ g_2 &= b_3 + b_2 = 0 + 0 = 0,\\ g_1 &= b_2 + b_1 = 0 + 1 = 1,\\ g_0 &= b_1 + b_0 = 1 + 1 = 0. \end{aligned} $$
따라서 그레이 코드는
$$ g_5g_4g_3g_2g_1g_0 = 101010 $$
이다.
② 다음으로 6비트 그레이 코드 \(g_5g_4g_3g_2g_1g_0 = 100101\) 를 2진수로 변환한다.
$$ g_5 = 1,\; g_4 = 0,\; g_3 = 0,\; g_2 = 1,\; g_1 = 0,\; g_0 = 1 $$
최상위 비트는 같으므로
$$ b_5 = g_5 = 1 $$
이제 왼쪽에서 오른쪽으로 진행하며
$$ \begin{aligned} b_4 &= g_4 + b_5 = 0 + 1 = 1,\\ b_3 &= g_3 + b_4 = 0 + 1 = 1,\\ b_2 &= g_2 + b_3 = 1 + 1 = 0,\\ b_1 &= g_1 + b_2 = 0 + 0 = 0,\\ b_0 &= g_0 + b_1 = 1 + 0 = 1. \end{aligned} $$
따라서 2진수는
$$ b_5b_4b_3b_2b_1b_0 = 111001_2 $$
이 된다.
③ 이제 (나)의 2진수→그레이 코드, 그레이 코드→2진수 변환 과정에서 사용하는 덧셈 연산을 논리 게이트로 바꾸어 생각한다.
여기서 사용하는 덧셈은 캐리를 무시한 2진 덧셈으로, 두 비트 \(x, y\) 에 대해 다음과 같은 진리표를 갖는다.
$$ \begin{array}{c|c|c} x & y & x + y \ (\text{캐리 무시}) \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{array} $$
이 진리표는 배타적 논리합(XOR) 게이트의 진리표와 완전히 같다. 즉,
$$ x + y\ (\text{캐리 무시}) = x \oplus y $$
가 된다.
따라서 2진수→그레이 코드 변환에서의 식 \(g_i = b_{i+1} + b_i\) 와, 그레이 코드→2진수 변환에서의 식 \(b_i = g_i + b_{i+1}\) 에 들어가는 덧셈은 모두 XOR 연산으로 구현할 수 있고, 각 비트당 하나의 XOR 게이트를 사용하면 된다.
결론적으로, 두 변환 과정에서 공통으로 사용할 수 있는 논리 게이트는 배타적 논리합(XOR) 게이트이며, 그 이유는 캐리를 무시한 2진 덧셈이 XOR 연산과 동일한 진리표를 갖기 때문이다.
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>