第3章 STAGE 7

有限の体と QR コード

有限体で誤りを直す

🎯 ミッション

mod 2 の多項式 x²＋x＋1 から要素4個の体を作り、掛け算表で 0 以外のどの数にも逆数があることを確かめよう。データを1次式の係数にして mod 7 で7つの値を送り、2か所まで壊れても元に戻せる理由（違う直線は1点でしか一致しない）を説明できれば合格。

未達成

ねこ博士

この章の最後に、体のもう1つの顔を見よう。QR コードは、一部が汚れたり欠けたりしても読み取れる。いちばん強い設定では、全体のおよそ30%が読めなくても元のデータを復元できるんだ。その仕組みの土台にあるのが、有限個の数でできた体だ。STAGE1 で、p が素数なら mod p の世界は体になると分かったね。では、要素が4個の体は作れるかな？ mod 4 の世界で考えてごらん。

うさ美

mod 4 では 2×1＝2、2×2＝4≡0、2×3＝6≡2 なので、2 に何を掛けても 1 になりません。2 には逆数がないので、mod 4 の世界は体ではありません。2×2≡0 のように、0 でない数どうしを掛けて 0 になってしまうのが原因です。

ねこ博士

そう。でも、別の作り方がある。STAGE3 で、ℚ(∛2) の計算は「多項式を既約多項式 x³−2 で割った余りで計算する」ことだった。同じことを、係数が mod 2 の数（0 と 1）の多項式でやってみよう。mod 2 では 1＋1＝0 になる。まず、x²＋x＋1 が mod 2 で既約かどうか調べてごらん。

うさ美

2次式なので、根があるかどうかで判定できます。x＝0 なら 0＋0＋1＝1、x＝1 なら 1＋1＋1＝3≡1。どちらも 0 にならないので根がなく、x²＋x＋1 は mod 2 で既約です。

ねこ博士

その通り。では、x²＋x＋1 の根を α とする。α は mod 2 の世界にはない、新しい数だ。ℚ に √2 を加えたように、mod 2 の世界に α を加える。x²＋x＋1 で割った余りは1次以下だから、できる数は a＋bα（a, b は 0 か 1）の4つ、0, 1, α, α＋1 だ。α²＋α＋1＝0 から、α² は何になるかな？

うさ美

α²＝−α−1 で、mod 2 では −1≡1 なので α²＝α＋1 です。これを使って掛け算を計算すると、α×(α＋1)＝α²＋α＝(α＋1)＋α＝2α＋1≡1。(α＋1)²＝α²＋2α＋1≡α²＋1＝(α＋1)＋1＝α。足し算は α＋α＝2α≡0 です。α と α＋1 は掛けると 1 になるので、0 以外の 1, α, α＋1 にはどれも逆数があります。要素が4個の体ができました！

足し算

掛け算

要素4個の体の足し算と掛け算。0, 1, α, α＋1 の4つの数で、α²＝α＋1、1＋1＝0 として計算した表。掛け算表で 1 になるところ（緑）が、0 以外のどの行にもちょうど1つあるので、どの数にも逆数がある。「mod 4」に切りかえると、2×2＝0（赤）となり、2 の行に 1 が現れない

ねこ博士

そうだね。要素の個数が有限の体を有限体（ゆうげんたい）という。実は、有限体の要素の個数は、必ず素数 p の累乗 pᵏ になり、pᵏ 個の有限体はどれも同じ形をしていることが分かっている。4＝2² 個の体はいま作ったもので、6 個や 10 個の体はない。有限体を初めて本格的に調べたのは、第4章の主人公ガロアで、有限体はガロア体とも呼ばれる。QR コードで使われるのは、mod 2 の世界に既約な8次式 x⁸＋x⁴＋x³＋x²＋1 の根を加えた、2⁸＝256 個の要素をもつ体だ。

うさ美

256 個なら、8 けたの 0 と 1 の並び、つまり 1 バイトで1つの要素を表せます。コンピュータのデータをそのまま体の数と思って、足し算・引き算・掛け算・割り算ができるんですね。

ねこ博士

その通り。では、体の数で、どうやって誤りを直すのか。いちばん単純なのは、同じデータを3回ずつ送って多数決をとる方法だけど、データ量が3倍になるわりに、直せる誤りは少ない。そこで多項式を使う。mod 7 の世界で考えよう。送りたいデータを2つの数 a, b（0〜6）とし、1次式 f(x)＝a＋bx を作る。そして、f(0), f(1), …, f(6) の7つの値を送るんだ。a＝2, b＝3 のとき、送る7つの値を計算してごらん。

うさ美

f(x)＝2＋3x を mod 7 で計算します。f(0)＝2、f(1)＝5、f(2)＝8≡1、f(3)＝11≡4、f(4)＝14≡0、f(5)＝17≡3、f(6)＝20≡6。送るのは 2, 5, 1, 4, 0, 3, 6 です。

ねこ博士

受け取った人は、7つの値のうち正しい値が2つあれば、元のデータに戻せる。たとえば f(1)＝5 と f(3)＝4 だけが分かったとして、a と b を求めてごらん。

うさ美

a＋b≡5、a＋3b≡4 です。引き算すると 2b≡4−5＝−1≡6。2 の逆数は、2×4＝8≡1 なので 4 です。両辺に 4 を掛けて b≡24≡3。a≡5−3＝2。a＝2, b＝3 が戻りました。ここで 2 で割るのに、mod 7 が体であることを使いました。

データ (a, b)＝(2, 3) → 1次式 f(x)＝2＋3x（mod 7）送る値：f(0), …, f(6)＝2, 5, 1, 4, 0, 3, 6（2個のデータを7個の値にして送る）正しい値が2つあれば戻せる：a＋b≡5、a＋3b≡4 → 2b≡6 2 の逆数は 4（2×4＝8≡1）→ b≡6×4＝24≡3、a≡5−3＝2

ねこ博士

よし。でも本当の問題は、どの値が壊れているのか、受け取った人には分からないことだ。たとえば x＝2 と x＝5 の値が壊れて、2, 5, 6, 4, 0, 1, 6 が届いたとしよう。鍵になるのは、「違う2本の直線は、mod 7 の世界でも1点でしか一致しない」という性質だ。ここで直線とは、a＋bx の形の式のこと。なぜ成り立つかな？

うさ美

f と g が2つの点 x₁, x₂ で同じ値になったとします。h＝f−g も a＋bx の形で、h(x₁)≡h(x₂)≡0 です。b≢0 なら h(x)≡0 は x≡−a×(b の逆数) のただ1つしか解がないので、2つの点で 0 になれません。b≡0 なら h＝a で、0 になるには a≡0。どちらにしても h は 0、つまり f と g は同じ直線です。ここでも、b の逆数があること、つまり体であることを使っています。

ねこ博士

その通り。だから受け取った人は、ありうる 7×7＝49 本の直線を全部調べて、届いた値といちばん多く一致する直線を選べばいい。2か所までの誤りなら、必ず正しい直線が選ばれる。理由を説明してごらん。

うさ美

正しい直線は、壊れていない 5 か所で一致します。ほかの直線は、正しい直線と1点でしか一致しないので、正しい値の場所では多くて1か所しか一致しません。壊れた2か所で偶然一致したとしても、合わせて 1＋2＝3 か所以下です。5 は 3 より大きいので、正しい直線がただ1つの「いちばん多く一致する直線」になります。でも3か所壊れると、正しい直線は 4 か所、ほかの直線も 1＋3＝4 か所まで一致できて、区別できなくなるかもしれません。

a b

mod 7 のリード・ソロモン符号。データ a, b から f(x)＝a＋bx の7つの値を送る。「受け取った値」の数をタップすると、その値が1つずれて壊れる（赤）。受け取った人は 49 本の直線を全部調べて、いちばん多く一致する直線を選ぶ。下の格子は、横が x、縦が値（0〜6）。受け取った値が黒い点、復元した直線の値が緑の輪。2か所までなら必ず正しく直り、どこが壊れたかも分かる。3か所以上壊すと、間違った直線を選んだり、決められなくなったりすることがある

ねこ博士

そう。7個の値のうち2個までの誤りを、場所が分からなくても直せる。データの個数を k、送る値の個数を n にすると、(n−k)/2 個までの誤りを直せることが分かっている。ここで、もし mod 7 のかわりに mod 8 を使ったらどうなるかな？ f(x)＝0 と g(x)＝2x を比べてごらん。

うさ美

g(0)＝0、g(4)＝8≡0 なので、f と g は x＝0 と x＝4 の2点で一致します。違う直線なのに2点で一致してしまうので、さっきの「多くて1点」の議論が崩れます。mod 8 では 2 に逆数がないからです。体でなければ、誤り訂正の保証ができないんですね。

ねこ博士

その通り。この方法は、1960年にリードとソロモンが考えたのでリード・ソロモン符号と呼ばれる。QR コードは1994年に日本のデンソー（いまのデンソーウェーブ）で開発され、256 個の要素の有限体の上で、もっと次数の高い多項式を使って、同じことをしている。CD や DVD の傷に強い読み取りや、宇宙探査機ボイジャーが遠い惑星から送ってきた画像にも、この符号が使われてきた。

リード・ソロモン符号の流れ。データを多項式の係数にし、必要より多くの点での値を送る。いくつか壊れても、受け取った値といちばん多く一致する多項式を選べば元に戻る。違う多項式どうしが一致する点が少ないことは、0 以外の数で割れる、つまり体であることから保証される

うさ美

作図のときは、体の次数を測って「できない」ことを証明しました。今日は、体の中で割り算ができることが、「必ず直せる」ことの保証になりました。体は、できることとできないことを、はっきり言い切るための道具なんですね。

ねこ博士

いいまとめだね。この章で学んだことを整理しておこう。

第3章のまとめ・体：四則（0 以外での割り算も）で閉じた数の世界。ℚ、実数、複素数、mod p、有限体
・作図できる数＝ℚ から四則と √ で作れる数。作図の1手は2次方程式なので、体は1段で次数 2 までしかひろがらない
・次数 [L：K]：基底の個数。[ℚ(α)：ℚ]＝α の最小多項式の次数、[L：K]＝[L：M][M：K]
・作図できる数の次数は 2 の累乗 → 立方体倍積（∛2、次数 3）と 60° の三等分（cos 20°、次数 3）は不可能。円積問題は π が超越数なので不可能
・正 n 角形が作図できる ⇔ φ(n) が 2 の累乗（正5角形・正17角形は可、正7角形・正9角形は不可）
・有限体（要素は pᵏ 個）の上の多項式で、QR コードの誤り訂正ができる

うさ美

第3章では、体に √ を加えると何が作れるかを調べました。次の第4章では、第1章の終わりに聞いた「5次方程式にはなぜ解の公式がないのか」を調べるんですよね。解の公式は「四則と √ や ∛ で解を書く」ことなので、今日までの体の話が使えそうです。

ねこ博士

その通り。√ や ∛ を加えて体をひろげていくとき、方程式の解どうしの入れ替えがつくる群、つまり第1章の群が、どう小さくなっていくか。群と体を結びつけたのが、20歳で亡くなったガロアだ。第4章で、群・環・体のすべてを使って、5次方程式の謎に挑もう。

【このステージの成果】 mod 4 は体でない（2×2≡0）。mod 2 の既約多項式 x²＋x＋1 の根 α を加えると、要素4個の体 {0, 1, α, α＋1}（α²＝α＋1）ができる有限体の要素の個数は素数の累乗 pᵏ。QR コードは 2⁸＝256 個の体（1 バイト＝1 要素）を使うデータ a, b を f(x)＝a＋bx にして、mod 7 で f(0)〜f(6) の7つを送る。正しい値が2つあれば、2 の逆数などを使って a, b に戻せる違う直線は1点でしか一致しない（体だから）→ 7個中2個までの誤りなら、いちばん多く一致する直線が正しいものになる mod 8 では 2x と 0 が2点で一致し、保証が崩れる。リード・ソロモン符号（1960年）は QR コード・CD・探査機で使われている

確認クイズ

Q1. 要素4個の体 {0, 1, α, α＋1}（α²＝α＋1、1＋1＝0）で、α の逆数は？

Q2. mod 7 で f(x)＝a＋bx の7つの値を送るとき、2か所までの誤りを直せる理由は？

Q3. mod 8 で同じ方法を使うと保証が崩れる理由は？

← 章のトップへ