ドパベン！
← 記事一覧へ戻る

シリーズ「コンピュータの誤り訂正のしくみ」 第5回

回路が「あきらめる」とは？

無実の桁

ここまでの回を、短く振り返っておこう。

第1回は、4 桁の知らせに、1 の数を偶数にそろえる検査の桁を 1 つ足した（パリティ）。 どの 1 桁が化けても、受け取った側のランプが光った。

前回は、検査の桁を 3 つにした（ハミング符号）。 7 桁に 1〜7 番の番号を振ると、光ったランプを 2 進数として読んだ数が、化けた桁の番号そのものになった。 その番号の桁を反転すれば、直る。

ところが、前回の最後に 2 か所を化かすと、様子が変わった。 3 番と 5 番を化かすと、ランプは 110。6 番と読める。 受け取った側は、化けていない 6 番を反転し、違う桁を 3 か所に増やしてしまった。

第2回の多数決も、同じだった。 同じ桁が 2 回化けると、間違った値を選び、「直した」という顔をした。

困ることが、もう 1 つある。 6 番まで反転した 7 桁で、もう一度ランプを確かめると、3 つとも消えている。 間違って直したあとの 7 桁は、送る側が送りうる、正しいパターンになってしまっているのだ。 あとから誰が検査しても、もう、おかしいところは見つからない。

直す仕組みは、直せない誤りを、見えない誤りに変えてしまうことがある。

前回の終わりに、こう問いかけた。 直せないときに、直さないでいてもらうことはできないか。

1 か所と 2 か所を、見分けたい

直さないでいてもらうには、まず、受け取った側が「これは 1 か所の化けではない」と分からなければならない。

けれど、3 つのランプだけでは、それができない。

化けた桁3 つのランプ（4・2・1）回路の読み
6 番だけ1106 番
3 番と 5 番1106 番
1 番と 7 番1106 番
2 番と 4 番1106 番

どれも、同じ光り方になる。 回路から見れば、区別がつかない。

前回見たとおり、3 つのランプの光り方 8 通りは、無事と、7 か所のどれが化けたかに、1 通りも余さず使い切っている。 2 か所の化けに回せる光り方は、もう残っていない。

それなら、ランプを足すしかない。 では、何を見るランプを足せばいいだろう。

もう 1 つ、パリティ

答えは、このシリーズのいちばん最初にある。

第1回のパリティを思い出してほしい。 1 の数を偶数にそろえる桁を足して送ると、1 か所化けたときは 1 の数が奇数になり、ランプが光った。 2 か所化けると、偶奇が 2 回ひっくり返って元に戻り、ランプは光らなかった。

第1回では、これは弱点だった。 2 か所化けても、気づけないのだから。 そのとき、こう書いた。「この弱点は、覚えておいてほしい。このシリーズの後半で、思わぬ使い道が出てくる」。

その使い道が、ここだ。

前回の 7 桁に、もう 1 桁足す。 7 桁全体の 1 の数を、偶数にそろえる桁だ。これを 8 番と呼ぶ。 送るのは 8 桁で、8 桁全体の 1 の数は、いつも偶数になる。

知らせが 1011 なら、前回の 7 桁は 0110011。 1 は 4 個で偶数なので、8 番は 0。 送るのは 01100110 の 8 桁だ。

受け取った側には、ランプを 1 つ足す。 8 桁全体の 1 の数が奇数なら光る、全体のランプだ。 中身は、第1回のランプとまったく同じである。

すると、こうなる。

  • 1 か所化けたら … 1 の数が 1 つ増えるか減るかして、奇数になる。全体のランプは光る
  • 2 か所化けたら … 偶奇が 2 回ひっくり返り、偶数に戻る。全体のランプは光らない

第1回で弱点だった「2 か所化けると、偶奇が元に戻る」ことが、ここでは、1 か所と 2 か所を見分ける目印に変わる。

押して、確かめる

下のシミュレータは、前回の番号順の 7 桁の右に、8 番を足した。 受け取る側の点の表には「全」の行を足した。8 桁すべてに点があり、その右端が全体のランプだ。

1 か所と 2 か所を見分ける シミュレータ

⚡ で 1 か所、2 か所と化かして、受け取った側の答えを比べてみてください

8 桁目（全体の検査の桁）

送る側

1
2
3
4
5
6
7
8
0
1
0
0

紫＝検査の桁（自動で決まる）
1・2・4 番：同じ行に点のある桁の 1 の数を偶数に
8 番：1〜7 番の 1 の数を偶数に

↓ 8 桁を送る。通り道（⚡ を押した桁が反転する）

↓ 化けた桁：0 か所

受け取る側

1
2
3
4
5
6
7
8
0
1
1
0
0
1
1
0
4
2
1
全

3 つのランプ（上から）：000 → 0

全体のランプ：消えている（8 桁の 1 の数が偶数）

判定：無事

点＝そのランプの検査が見ている桁
ランプ＝点のある桁の 1 の数が奇数なら光る
全＝8 桁すべてを見る、全体のランプ

受け取った側の回路は、送った知らせを知らない

受け取った側が直した 8 桁

1
2
3
4
5
6
7
8
0
1
1
0
0
1
1
0

受け取った知らせ（3・5・6・7 番）：1011

緑の ✓ ＝ 回路が反転した桁（回路にも分かる）
赤い ✗ ＝ 送ったのと違う（あなたにだけ見える）

ランプは 1 つも光っていない。そのまま受け取る。

まず、⚡ で 5 番だけを化かしてほしい。

全体のランプが光る。 3 つのランプは 101、5 番。 1 か所とみなして、5 番を反転する。ここまでは、前回と同じだ。

次に、5 番の ⚡ はそのままにして、3 番も化かしてほしい。

3 つのランプは 110、6 番と読める。前回は、ここで 6 番を反転してしまった。 けれど今度は、全体のランプが消えている。 1 か所だけ化けたのなら、全体のランプは光るはずだ。光っていないのだから、1 か所ではない。

回路は、6 番に触らない。 どの桁も反転せずに、「直せない」と知らせる。 違う桁は 2 か所のまま、増えていない。

ほかの 2 か所も、試してみてほしい。 どの 2 か所でも、回路は直さずに「直せない」と言う。

上の切り替えで「8 桁目なし」を選ぶと、前回の 7 桁に戻る。 同じように 3 番と 5 番を化かすと、今度は 6 番を反転して、違う桁を 3 か所にしてしまう。

光り方は、4 通り

受け取った側が見るものは、2 つになった。 全体のランプと、3 つのランプだ。 組み合わせると、4 通りある。

全体のランプ3 つのランプ受け取った側は
消えている000無事。そのまま受け取る
光った000 以外1 か所。読んだ番号の桁を直す
光った0001 か所。8 番そのものが化けた。8 番を直す
消えている000 以外2 か所。直さずに「直せない」と知らせる

3 行目は、少し説明が要る。 8 番の桁は、全体のランプにしか見られていない（3 つのランプの点は、8 番には無い）。 だから 8 番だけが化けると、全体のランプだけが光り、3 つのランプは 000 のままだ。 前回、検査の桁が化けると「自分のランプだけ」が光って見分けがついたのと、同じ理屈である。 シミュレータで 8 番だけを化かすと、確かめられる。

4 行目が、この回で新しくできた答えだ。 2 か所化けると、全体のランプは消える。 そして、化けた 2 つの番号は違うのだから、前回見たとおり、3 つのランプのどれかは必ず光る（片方が 8 番なら、もう片方の番号がそのまま光る）。 だから、どの 2 か所が化けても、必ずこの行に落ちる。

知らせ 16 通りと、8 桁から 2 か所を選ぶ 28 通りの、448 通りを全部確かめても、1 つの例外もなく「直せない」と判定した。 1 か所の 128 通りは、すべて直った。

上のシミュレータの「判定の表」を開くと、いまの光り方が、どの行にあたるかが塗られる。

あきらめる、という仕事

ここで、回路がしたことを振り返ってみよう。

2 か所化けたとき、この回路は、どこが化けたのかを言い当てられない。 前回の回路も、言い当てられなかった。 違うのは、そのあとだ。

前回の回路は、分からないのに、分かったつもりで直した。 この回路は、分からないことが分かって、直さなかった。

どちらも、正しい知らせを取り戻せてはいない。 けれど、この 2 つは、まるで違う。

間違って直された知らせは、正しい知らせの顔をして、先へ進んでいく。 使う側には、疑う理由がない。 「直せない」と知らされた知らせなら、使う側は、それを使わずにすむ。 そこで止まることも、別の手を探すこともできる。

検査の桁をもう 1 つ足すと、回路は「直せる誤り」と「直せない誤り」を見分けられる。直せないときは、直さずに知らせればいい。

回路が「あきらめる」というのは、投げ出すことではない。 自分の手に余ると、正直に言うことだ。

1 か所なら直し、2 か所なら気づく。 この性質は、英語の頭文字をとって SECDED（Single Error Correction, Double Error Detection。1 か所訂正・2 か所検出）と呼ばれる。

実は、この 8 桁目は、前回紹介したハミングの 1950 年の論文に、もう出てくる。 論文には、1 か所の訂正と 2 か所の検出を両立させる節がある。 そこでは、前回と同じ 7 桁の例に「それまでの桁すべてを、偶数のパリティで検査する桁」を 1 つ足して、8 桁の例を作っている。

違う桁の、数

なぜ、1 桁足しただけで、こんなに変わるのだろう。 別の向きから見てみよう。

8 桁のパターンは、28 = 256 通りある。 そのうち、送る側が送りうる正しいパターンは、知らせの数と同じ 16 通りだけだ。 残りは、第1回の言い方でいえば、ありえないパターンである。

正しいパターンを 2 つ並べて、違っている桁を数えてみる。 知らせ 1011 の 8 桁は 01100110、知らせ 1010 の 8 桁は 10110100。 知らせは 1 桁しか違わないのに、8 桁では 1・2・4・7 番の 4 か所が違う。

16 通りのどの 2 つを比べても、違う桁は 4 か所以上ある。 これまでのやり方でも、正しいパターンどうしの違う桁の数を、いちばん少ないところで比べてみよう。

やり方送る桁数正しいパターンどうしで、違う桁の数（いちばん少ないところ）
パリティ52
3 回送る123
ハミング符号73
ハミング符号 ＋ 1 桁84

この「違う桁の数」を、ハミング距離という。 1 か所化けるごとに、パターンは 1 歩ずつ動く。2 つのパターンのあいだは、何歩離れているか、という距離だ。

距離が 3 のハミング符号では、2 か所化けると、元のパターンから 2 歩、別の正しいパターンから 1 歩のところに来る。 回路は、いちばん近い正しいパターンへ戻す。それが、別のパターンだった。 これが、前回の「無実の桁を直す」の正体である。

距離が 4 になると、1 か所化けたときは、元から 1 歩、ほかの正しいパターンからは 3 歩以上。迷わず戻せる。 2 か所化けたときは、元から 2 歩。そして、同じ 2 歩のところに、別の正しいパターンが 3 つ並んでいる。 どれに戻せばいいのか、決めようがない。 だから、「直せない」と言うしかない。そして、それが言える。

メモリの中で

この仕組みは、身近なところで働いている。 コンピュータのメモリの中だ。

メモリは、計算の途中の値やプログラムを、0 と 1 で覚えておく部品である。 パソコンやサーバーの主なメモリ（DRAM）は、小さなコンデンサにためた、ごくわずかな電気で 0 と 1 を覚えている。 『記憶のしくみ』を読んだ人は、最終回の DRAM を思い出してほしい。ためた電気が少しずつ漏れるので、ため直しつづけることで覚えていた、あの記憶だ。

そのわずかな電気は、外から飛び込んでくる粒にも乱される。

1979 年、Intel の研究者が、こう報告した。 メモリを包むパッケージの材料には、ウランやトリウムがごくわずかに含まれている。 それが出すアルファ線が記憶の粒に飛び込むと、その桁が化けることがある。

宇宙から降ってくる宇宙線も、原因になる。 IBM は、同じ種類のメモリを地下深くや、高さの違う場所に置いて、化ける回数を比べた。そうして、アルファ線と宇宙線の影響を分けて測った。

こうした化けは、部品が壊れたわけではない。 次に書き直せば、その桁は元どおりに覚える。 だから、ソフトエラー（やわらかい誤り）と呼ばれる。

では、メモリに、この回の仕組みを入れてみよう。 メモリは、64 桁をひとまとまりにして読み書きすることが多い。 64 桁の知らせで、1 か所を直し、2 か所に気づくには、検査の桁が何桁要るだろうか。 前回の数え方で、考えてみてほしい。

ランプが r 個なら、光り方は 2r 通り。無事の 1 通りを除いて、2r − 1 か所を見分けられる。 見分けなければならないのは、知らせの 64 桁と、検査の桁 r 桁だ。

ランプ見分けられる場所知らせ 64 桁 ＋ 検査の桁
626 − 1 = 6364 + 6 = 70（足りない）
727 − 1 = 12764 + 7 = 71（足りる）

ランプは 7 つ。 そこに全体のランプを 1 つ足して、検査の桁は 8 桁。 メモリに覚えるのは、64 + 8 = 72 桁だ。

実際、誤り訂正に使うメモリの部品は、64 桁ではなく、72 桁の幅で読み書きできるように作られている。 64 桁が知らせで、8 桁が検査の桁。直し方は、多くの場合、この回と同じ 1 か所訂正・2 か所検出だ。 こうしたメモリを、誤り訂正符号（Error Correcting Code）の頭文字をとって、ECC メモリという。

余分な桁は、72 桁のうちの 8 桁。1 割ほどだ。 3 回送るやり方なら、64 桁に 128 桁を足すことになる。

どれくらい化けるのだろう。 Google が自社のサーバーを 2 年半にわたって調べた 2009 年の研究では、ECC を載せたサーバーの約 3 台に 1 台が、1 年のあいだに少なくとも 1 回、メモリの誤りに出会っていた。 その多くは、一時的な化けではなく、部品そのものの不具合による誤りだった。 それでも、1 か所の誤りなら、ECC が直してくれる。 けれど、直せない誤りに出会ったサーバーも、1 年で 100 台に 1 台ほどあった。

あきらめたら

直せないと分かったら、コンピュータはどうするのか。

少なくとも、間違っていると分かった値を使って、先へ進みはしない。 使っていない場所の誤りなら、記録を残すだけで済むこともある。 けれど、いま使っている値なら、そこで止まるしかない。

さきほどの Google の研究でも、直せない誤りは、マシンを止めて、そのメモリを取り替えるほど重いものとして扱われていた。

止まるのは、困る。 けれど、間違った値で計算を続けて、間違った答えを「正しい」と言って返すより、ずっといい。

物差しの表に、1 行足そう。

やり方送る桁数1 か所化けたら2 か所化けたら
そのまま4気づかない気づかない
パリティ5気づく気づかない
3 回送る12直す別の桁なら直る。同じ桁の 2 回なら、間違った値に直す
縦横のパリティ8直す気づくことが多いが、間違って直すこともある
ハミング符号7直す化けていない桁を直して、3 か所にしてしまう
ハミング符号 ＋ 1 桁8直す気づく（直さない）

2 か所化けたとき、パリティは黙った。 多数決とハミング符号は、嘘をついた。 この回の回路は、「分からない」と言う。

止まったあと、どうするか。 探査機なら、もう一度送ってもらえばいいのか。 その話は、このシリーズの最後に取っておこう。

ここまでは、化けるのは 1 か所か 2 か所、それも、ばらばらの場所だと考えてきた。 けれど、化けるのは、ばらばらとは限らない。 CD の傷や、一瞬の雷は、隣り合う桁を、まとめて何桁も化かしてしまう。

化けるのが 1 か所・2 か所どころでなかったら、どうすればいいのか。

次回は、まとめて化ける傷を相手にしよう。

参考文献

シリーズ「コンピュータの誤り訂正のしくみ」