パリティチェックの解説とXORを用いた高速な計算方法｜XOR活用例

Aru

昔のパソコンは処理速度も遅く、計算を高速化するために色々なテクニックを使っていました。今回は、そのようなテクニックの中からパリティ計算を高速に行う方法について解説します。

Contents

パリティ計算とは
パリティ計算の方法（通常の実装）
高速な実装（XORを使った方法）
まとめ

パリティ計算とは

パリティ計算は、データ通信やメモリのエラー検出などに用いられる手法で、ビット列の偶奇を判定するために使われます。具体的には、ビット列に含まれる1の数が偶数か奇数かを調べます。パリティには2種類あります。偶数パリティ（Even Parity）と奇数パリティ（Odd Parity）です。

偶数パリティ
偶数パリティでは、ビット列の1の数が偶数になるようにパリティビットが設定されます。例えば、ビット列「1011」の場合、1の数は3つで奇数です。偶数パリティを持つために、パリティビットを1に設定して「10111」にします
奇数パリティ
奇数パリティでは、ビット列の1の数が奇数になるようにパリティビットが設定されます。例えば、ビット列「1011」の場合、1の数は3つで奇数です。奇数パリティを持つために、パリティビットを0に設定して「10110」にします

このようなパリティビットを付加するためには、ビット列の１の数を数える必要があります（パリティ計算）。この記事では、この偶奇の計算を行う方法について解説します。

パリティ計算の方法（通常の実装）

普通にパリティを計算する場合、以下のようなコードを書きます（Pythonのコードです）。このプログラムでは、1ビットずつシフトしながらビットが1か0かを調べ、1であればcntを1加算しています。最後にcntを2で割った余りをパリティとして出力しています（奇数か偶数かを出力）。

def parity8(x) :
    cnt = 0
    for i in range(8) :
        if (x >> i)%2 == 1 : cnt += 1

    return cnt%2


for i in range(256):
    print(bin(i), parity8(i))

このように、ビット数分ループさせて１を数えるのがパリティ計算の簡単な方法になります。

高速な実装（XORを使った方法）

パリティ計算を高速に行う方法が奥津かありますが、ここではXORを用いた実装方法について解説します。

考え方

XORの基本

まず、XOR演算（排他的論理和）について説明します。XORは2つのビットが異なるときに1を返し、同じときに0を返す演算です。数学的には、A xor Bは(A + B)(mod 2)と同じです。つまり、ビット列の偶奇は(mod 2が0か1か)で判定できます。

パリティ計算の基本概念

ビット列A = A0, A1, A2, A3, A4, A5, A6, A7のパリティを計算は、以下のように記述できます。

A0 + A1 + A2 + A3 + A4 + A5 + A6 + A7 (mod 2)

mod計算の場合、途中にmodを挟んで書いても結果は同じなので、以下のように書き直すことができます。

((A0 + A1) mod 2 + (A2 + A3) mod 2 + (A4 + A5) mod 2 + (A6 + A7) mod 2) mod 2

先ほど書いたようにA+B mod 2は、A xor Bで書き直せるので、パリティ計算は以下のように書き直すことが可能です。

A0 xor A1 xor A2 xor A3 xor A4 xor A5 xor A6 xor A7

xorの順番は入れ替え可能なので、さらに変形して、以下のように記述することができます。

((A0 xor A4) xor (A1 xor A5)) xor ((A2 xor A6) xor (A3 xor A7))

ビット演算によるパリティ計算

上記の式の計算を、ビット演算で考えてみます。

上位4ビットと下位4ビットをXORすることで(A0 xor A4) と (A1 xor A5)、(A2 xor A6)、 (A3 xor A7)の計算ができます。
次にその結果を2ビットごとにまとめてXORすることで以下の計算が行えます。
(A0 xor A4) xor (A1 xor A5) と (A2 xor A6) xor (A3 xor A7)
最後に、2つの結果をXORしたものがパリティになります。

このようにして、XORを使ったビット演算で効率的にパリティを計算することができます。

この方法は、特にハードウェア実装や低レベルのプログラムでパリティビットを計算する際に有効です。ビット操作が軽量で高速であるため、計算コストを抑えることができます。

パリティ計算高速版（８ビット）

上記の解説をプログラムにしたものが以下になります。

最初の１つめは4ビットシフトして、4ビットをまとめてxorし、次は2ビットシフトし、最後に1ビットシフトしてxorを行います。この計算を行うと、最下位ビットに偶奇が格納されるので、これを返します。

def parity8(x) :
    x ^= x>>4
    x ^= x>>2
    x ^= x>>1
    x &= 0x1
    return x

パリティ計算高速版（64bit）

8ビットだとそれほど高速になった感じはしませんが、64bitのパリティを計算する場合は、速度が実感できます。64ビットの場合、8ビットと比べると8倍の数のビットをチェックする必要がありますが、追加されるたコードはたったの３行です。

def parity64(x) :
    x ^= x>>32
    x ^= x>>16
    x ^= x>>8
    x ^= x>>4
    x ^= x>>2
    x ^= x>>1
    x &= 0x1
    return x

計算量の差

単純にループで計算する場合、8ビットの場合は8回、64ビットの場合は64回ループする必要があります。これと比べると、8bitでは3回、64bitでは6回のシフトとXOR演算で計算ができます。このように、ビット数が増えれば増えるほどxorを使った場合と単純に行った場合の差が大きくなります。