XORと活用例(パリティや暗号)

過去のブログのアーカイブ

この記事は前身のブログのアーカイブを引き継いだものです．画像が正しく表示できないなど，コンテンツの表示に問題がある恐れがあります．

ANDやORなど、コンピュータをある程度知っている人ならよく聞く単語だと思います。Minecraftが流行ったときに、レッドストーン回路を扱うに当たって勉強し始めた人も少なくないと思います。
しかし、ANDやORが紹介されているページに高確率であるXOR(排他的論理和)、いまいち使い道がピンとこない人も多いのではないでしょうか。

XORの計算方法

まずはおさらいとしてXORの計算方法です。データ1(以下「#1」)、データ2(以下「#2」)が00同士または11同士のときは0、違う場合は1を返す計算方法です。別名「排他的論理和」と言われています。

つまりはOR(論理和)と似ているが11同士のときは0を返すようになっただけです。

使用例

データの保護

それでは早速使用例の紹介ですが、一番よく使われているのがデータの保護用です。バックアップみたいなものですがもっと万能な方法です。ここではストレージの保護技術「RAID5」を紹介します。
例えば10個あるデータの保護するとすればどうすればよいでしょうか。最も単純な方法ならそのままバックアップすることで保護することができます。しかしこれには問題点がある、10TBのデータがある場合、普通にバックアップするとバックアップしたデータを置くための容量10TBが必要になり、合計20TB必要となります。
これでは確かに安全ですがとても非効率です。ここで使われるのがXORです。
XORは、#1と#2のXORした結果(以下「#P」)の3つがあれば、#2のデータがわからなくなっても#1と#Pの結果があれば#2の結果がわかると言う特性があります。データは2つだけじゃなく、3つでも4つ…複数あっても大丈夫です。
例えばデータが3つあり、#2がわからなくなったとします。
この場合のXORした結果(パリティ)は01011100となります。このデータをバックアップ用のストレージなりに保存しておきます。
あとは#1・#3・#Pのデータから#2を取り出すことができます。この場合、計算は#1 XOR #3→その結果 XOR #Pとします。順番はバラバラでもいいですが1つずつXORしていきます。

これで#2のデータが復活しました！データが10個、計10TBあっても復元のためのパリティ1TBがあればいいので、バックアップ含め11TBあれば保護ができます。
しかしこれには欠点もあります。ちょっぴり複雑になること。そして2つ以上のデータが吹っ飛んだら結局復元できなくなってしまうことです。ケースバイケースですね。

暗号技術

データを暗号する際にもXORがよく使われています。先程のように、#pがあれば、#2と#pから#1を作り出すことができるといいましたが、この方法が暗号技術にも使われています。この際の#Pとは暗号化した後のデータです。
つまり、ぐるぐる回る方式の暗号技術があれば、暗号も複合も同じプログラムで行うことができ、とても効率が良いのです。