5 / 63 · 개념

XOR·XNOR: 같음, 다름과 패리티

두 입력 XOR와 다중 입력 패리티를 구분하고 오류 검출의 한계를 설명합니다.

두 비트가 다른지 묻는 게이트

XOR는 두 입력이 다르면 1이고, XNOR는 같으면 1입니다.

a\oplus b=\overline a b+a\overline b,\qquad \overline{a\oplus b}=ab+\overline a\,\overline b

OR와 XOR는 00·01·10에서 같지만 11에서는 다릅니다. OR 기호 앞에 곡선 하나가 더 있는 것이 XOR 기호입니다. XNOR에는 출력 반전^{부정 0을 1로, 1을 0으로 바꾸는 NOT 연산입니다. 수식 위의 선은 선 아래 식 전체에 NOT을 적용한다는 뜻입니다. 자세히 보기} 원도 있습니다.

11에서 OR와 XOR를 비교하기

XOR · 진리표
a	b	y
0	0	0
0	1	1
1	0	1
1	1	0

입력이 세 개 이상이면 “정확히 하나”가 아닙니다

XOR는 결합법칙이 성립하므로 $a\oplus b\oplus c$ 를 차례로 계산할 수 있습니다. 결과는 입력 중 1의 개수가 홀수일 때 1입니다. 111의 결과도 1이므로 “정확히 하나의 입력이 1”이라는 설명을 그대로 확장하면 틀립니다.

전가산기의 sum 출력은 이 3입력 패리티^{패리티 1인 비트 개수가 홀수인지 짝수인지 나타내는 값입니다. 패리티 검사는 홀수 개 비트 오류를 검출하지만 짝수 개 오류는 놓칠 수 있습니다.}이고, cout은 1의 개수가 둘 이상인지를 나타냅니다. 아래에서 111을 만들면 sum=1, cout=1이며 정수 합은 $1+2\times1=3$ 입니다.

세 입력: 홀수 개수와 다수결은 다릅니다

a + b + cin = sum + 2 × cout

패리티는 검사할 수 있는 오류의 종류가 정해져 있습니다

데이터 $d_3d_2d_1d_0=1011$ 에서 짝수 패리티 비트는 $p=d_3\oplus d_2\oplus d_1\oplus d_0=1$ 입니다. 데이터와 p를 함께 XOR하면 0입니다. 전송 중 홀수 개의 비트가 뒤집히면 전체 XOR가 1로 바뀌어 검출됩니다. 짝수 개가 뒤집히면 검출되지 않을 수 있으며, 단일 패리티 비트로 오류 위치도 알아낼 수 없습니다.

같은 비트열인지 비교하기

두 벡터 A와 B가 같은지는 각 비트의 XOR를 OR로 묶어 검사할 수 있습니다.

equal=\overline{\bigvee_i(A_i\oplus B_i)}

불일치 비트가 하나라도 있으면 OR가 1입니다. 그 전체를 반전하면 모든 비트가 같을 때만 1입니다. “XOR를 전부 XOR하면 같다”라고 구현하면 두 불일치가 서로 상쇄되는 오류가 생깁니다.

직접 생각해 보기

A=1010, B=1001에서 XOR 비트열과 equality 결과를 구하세요. XOR 비트열을 다시 XOR 축약해서 “같음”을 판정하면 어떤 문제가 생기나요?

해설 보기

XOR 비트열은 0011이고 같음은 0입니다. 두 불일치 비트를 XOR하면 0으로 상쇄되므로, 이를 반전한 결과는 잘못된 같음=1이 됩니다. 불일치 비트는 OR 축약해야 합니다.