5 / 63 · 概念

XOR・XNOR：一致・不一致とパリティ

2 入力 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

3 入力以上では「ちょうど一つ」ではありません

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$ です。

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 ビット列と等値比較の結果を求めてください。XOR ビット列をさらに XOR リダクションして「一致」を判定すると、何が問題になりますか。

解説を見る

XOR ビット列は 0011、一致の結果は 0 です。二つの不一致ビットを XOR すると 0 に打ち消し合うため、それを否定すると誤って一致=1 になります。不一致ビットは OR リダクションします。