三人寄れば文殊の知恵符号
こんにちは。Kumaです。
先日、とても素晴らしい記事が鯵坂もっちょ氏により公開されました。
www.ajimatics.com
私はこの記事を見た時に、別の側面で捉えました。
それは、
「三人寄れば文殊の知恵は誤り訂正符号である」
ということです。
- 三人寄れば文殊の知恵、n人寄れば・・・・
- 三人寄れば文殊の知恵 の符号的捉え方
- 三人寄れば文殊の知恵符号 を図で見る
- 三人寄れば文殊の知恵符号 の性質
- n人寄れば文殊の知恵符号 の極限とShannonの定理
三人寄れば文殊の知恵、n人寄れば・・・・
鯵坂もっちょ氏のブログ通り、
確率で正解出来る人が3人居たとし、多数決で全体の回答を決める時に「三人寄れば文殊の知恵」が成立します。*1
n人寄れば・・・・を考えると、全体の回答が正解となる確率はどんどん1に近づきます。
三人寄れば文殊の知恵 の符号的捉え方
簡単のため、正解を数字の１、誤りを数字の０で表現します。
そして、以下のような問題を考えます。
(図をみるとわかりやすいかと思います)
- 正解を知っている人 が１人いるとします。[1]
- この人をコピーして3人にします。[111]
- 確率1-pで1を0に反転する操作 を3人にそれぞれ行います。例として[101]
- 多数決で全体の回答を決めます。[101]の場合は[111]となります。
これは誤り訂正符号とその復号になっています。つまり、
1. 正解を知っている人 が１人いるとします。[1]
→ 守りたい情報を決めます。この場合は1を守りたい。 (ここで０を選んでもよいわけです）
2. この人をコピーして3人にします。[111]
→ 守りたい情報を3倍の長さの情報に埋め込みます。(”符号化”)
3. 確率で1を0に反転する操作 を3人にそれぞれ行います。例として[101]
→ 0/1反転誤りが発生してしまいました。
4. 多数決で全体の回答を決めます。[101]の場合は[111]となります。
→ 誤りを多数決で元に戻します。("復号")
守りたい情報を、より長い系列に埋め込むことで冗長性を取っているわけです。
冗長性があるので、一部が破壊されても元の系列が推定できる。この仕組を 誤り訂正符号 といいます。*2
この符号を
「３人寄れば文殊の知恵符号」 とでも名付けましょう！！
三人寄れば文殊の知恵符号 の性質
三人寄れば文殊の知恵符号 は、実は符号理論では有名な 反復復号 と呼ばれるものに相当します。
3人寄れば文殊の知恵符号 は 反復符号であり、n人寄れば文殊の知恵符号は
反復符号です。
復号方法としては 多数決論理復号法 を採用したことになります。*4
一般の符号において、符号というのは元の情報量が
bit で、冗長化した後の情報量が
bitであるものを指します。
桁の２進数から
桁の２進数への写像で規定される ともいえます。
反復符号は 完全符号 と呼ばれる性質を満たします。
ハミング限界 - Wikipedia
ハミング限界（ハミングげんかい、英: Hamming bound）は、符号（線型符号とは限らない）のパラメータの限界値を指す。球充填の限界を情報理論の観点で言い直したものと言える。ハミング限界に従った符号を「完全符号; perfect code」と呼ぶ。
完全符号というのはとてもカッコイイ名前ですが、完全符号だからといってそれだけで誤り訂正符号としての性能が良いとかってことはないです。
他にもいくつか条件があり、それを複数満たすものが 「良い符号」 と言われます。*5
n人寄れば文殊の知恵符号 の極限とShannonの定理
人寄れば文殊の知恵符号 を考えましょう。
を無限大に飛ばすと、明らかに正答率は1に近づきます。
しかし たかだか bitの情報を守るために、
bit の情報を使うというのはどうも効率が悪い気がします。
正答率を1に近づけるには 人寄れば文殊の知恵符号 にするしかないのでしょうか？
符号ではなく
符号を考えた場合にも、やはりその効率
は0にする他にないのでしょうか？
段々、難しくなってきたと思います。このあたりがまさに 符号理論の真髄 の一端です。
情報理論の始祖である C.E.Shannon は驚くべき結果を示しています。*6
与えられた誤り率の通信路に対して、ある数
が存在する。
符号の効率 が
未満でありさえすれば、いくらでも誤り率を小さくする うまい符号 が存在する。
つまり、効率を0にまで落とさなくても、未満にしておけば、誤りを完全に無くすような符号/復号が必ず構成出来る ということです。*7
は誤りなく転送可能な情報量の上限といえますから、 通信路容量 と呼ばれます。*8
逆に、いかなる符号をもってしても通信路容量を超える誤りなし転送は不可能です。
話は尽きませんが、今回はこのあたりでおしまいです。
興味を持たれた方はぜひ、甘利先生の情報理論などを手にとって見て下さい。（この本は、私の知る限りでは最も分かりやすく気軽に読める符号の本です)
www.amazon.co.jp
*1:正解率がの時は「船頭多くして船山に登る」となりますが。
*2:身近なところではQRコードなどに使われています。符号のないデジタルシステムは無いと言っていいでしょう
*3:なぜ符号化した系列を立方体の頂点に配置したのかには、意味があります。気になる方は ハミング距離 や 符号空間 で調べてみて下さい。
*4:わざわざ 「多数決論理復号法 を採用した」 と書いたということは、他の復号方法もあるというわけです。 符号理論において、一般的な復号方法は 「最小距離復号(Minimum Distance Decoding)」です。反復符号の場合、両者は同じ結果を与えますが。
*5:QRコードに使われている リードソロモン符号 は良い符号の代表です
*6:かなり雑な書き方をしているのはご容赦下さい
*7:Shannon の証明ではランダム符号というものが使われています。これは復号に指数時間かかるために実用上は役に立ちません。具体的な符号の構成方法についてShannonの定理は何も教えてくれません。それでも、実際にランダム符号に非常によく漸近するような符号はいくつも見つかっています
*8:ちなみにKumaは光の通信路に対して通信路容量を調べたりもしています
