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

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

回路が「繰り返す」とは？

聞き返せないなら

前回は、4 桁の知らせに、1 桁だけ足して送った。 1 の数を偶数にそろえる、検査の桁である。 これで、通り道でどの 1 桁が化けても、受け取った側のランプが必ず光るようになった。

けれど、ランプは「どこかが化けた」としか言わない。 どこが化けたかは分からない。 聞き返そうにも、相手は遠い。ボイジャー 1 号までは、電波でも片道 1 日近くかかる。

受け取った側だけで、直すことはできないか。 これが、前回の終わりに残った問いだった。

人間なら、こういうとき、どうするだろう。

大事なことを伝えるとき、人は繰り返す。 「電話番号は、0123……。もう一度言います。0123……」。 一度目を聞き違えても、二度目で気づける。

このやり方のいいところは、送る側が勝手に繰り返すことだ。 受け取った側から「もう一度」と頼まなくていい。 だから、聞き返せない相手にも使える。

では、何回繰り返せばいいのだろう。

時計は、1 つか 3 つ

まず、2 回にしてみる。 4 桁の知らせを、2 回続けて送る。

届いた 2 つが同じなら、たぶん正しい。 食い違っていたら、どこかが化けている。 それは分かる。

けれど、どちらが正しいのかは分からない。 1011 と 1001 が届いたとして、化けたのが 1 回目なのか 2 回目なのか、決め手がない。

これでは、前回のパリティと同じ立場だ。 気づけるけれど、直せない。 しかも、パリティは 1 桁足すだけで済んだのに、こちらは 4 桁も足している。

ソフトウェアづくりの古典、ブルックスの『人月の神話』に、古い格言として、こんな言葉が引かれている。

「海に出るなら、時計を 2 つ持っていくな。1 つか 3 つにせよ」

昔の船は、クロノメーターという正確な時計を積み、海の上で自分の位置（経度）を割り出すのに使っていた。

木の箱に収まった、航海用の時計

航海用の時計、クロノメーター。これが食い違ったら、どちらを信じる？

1 つなら、それを信じるしかない。 2 つが食い違ったら、どちらを信じればいいか分からない。 3 つあれば、2 つがそろっているほうを信じればいい。

3 つのうち、多いほうに合わせる。 これを多数決という。

押して、確かめる

まずは 1 桁で試そう。 送る側は、同じ桁を 3 回送る。 受け取る側は、届いた 3 つを「多数決の回路」に入れる。回路の中身は、あとで開ける。

多数決 シミュレータ

送る桁を決めてから、⚡ でどれか 1 つを化かしてみてください

送る側

↓ 同じ桁を 3 回送る

1
1
1

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

↓ 化けた桁：0 か所

受け取る側

1
1
1

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

↓ 受け取った 3 つを、多数決の回路に入れる

多数決の回路中身は、あとで開ける1 回目12 回目13 回目1答え
1受け取った知らせ

緑の ✓ ＝ 3 つがそろっていなかった（回路にも分かる）

3 つともそろっている。答えは 1。

⚡ で、3 つのうちどれか 1 つを化かしてほしい。

答えは、送った桁のまま変わらない。 どれを化かしても、そうなる。

答えのマスに、緑の ✓ が付いたはずだ。 これは「3 つがそろっていなかった」という印である。

ここでも、前回と同じことを強調しておきたい。 受け取った側の回路は、送った桁を知らない。 赤い枠は、画面の前のあなたにだけ見えている。

それでも、3 つがそろっていないことは分かる。 そして、2 つそろっているほうを選べる。 前回の回路は、化けたことに気づくだけだった。 この回路は、直している。

多数決を、ゲートで

多数決の回路の中身を見よう。 使うのは、AND と OR という 2 つのゲートである。

AND は、入力が両方とも 1 のときだけ 1 になる。

入力1入力2出力
000
010
100
111

OR は、入力のどれか 1 つでも 1 なら 1 になる。 入力が 3 本あっても同じで、全部 0 のときだけ 0 だ。

入力1入力2出力
000
011
101
111

多数決の答えは、「3 つのうち、2 つ以上が 1 なら 1」。 これを、少し言い換える。

「どれか 2 つが、両方とも 1」。

3 つの中から 2 つを選ぶ組は、3 通りしかない。 1 回目と 2 回目、2 回目と 3 回目、3 回目と 1 回目。

だから、こう組めばいい。

  1. 1 回目と 2 回目を、AND に入れる
  2. 2 回目と 3 回目を、AND に入れる
  3. 3 回目と 1 回目を、AND に入れる
  4. 3 つの AND の答えを、OR に入れる。これが答えになる

どれかの組が両方とも 1 なら、その AND が 1 になり、OR も 1 になる。 どの組も両方 1 でなければ、つまり 1 が 1 つ以下なら、AND はどれも 0 で、答えも 0 だ。

8 通り全部を、表で確かめておこう。 左の 3 列が、1 回目・2 回目・3 回目に受け取った桁。 AND の列は、左から「1 回目と 2 回目」「2 回目と 3 回目」「3 回目と 1 回目」の組だ。

123AND 1・2AND 2・3AND 3・1答え
0000000
0010000
0100000
0110101
1000000
1010011
1101001
1111111

1 が 2 個以上の行（4・6・7・8 行目）だけ、答えが 1 になっている。 『計算のしくみ』を読んだ人は、第2回の全加算器の「繰り上がり出力」を思い出してほしい。入力の 1 が 2 個以上なら 1。あれも、多数決だった。

箱を開けたシミュレータで、確かめてほしい。 1 回目から 3 番目の AND へ下りる線は、2 回目・3 回目の線をまたいでいる（小さな半円のところ）。つながってはいない。

多数決 シミュレータ（多数決の回路を開けた）

⚡ を押して、どの AND が 1 になるか見てください

送る側

↓ 同じ桁を 3 回送る

1
1
1

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

↓ 化けた桁：0 か所

受け取る側

1
1
1

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

↓ 受け取った 3 つを、多数決の回路に入れる

ANDANDANDOR1 回目12 回目13 回目1答え
1受け取った知らせ

緑の ✓ ＝ 3 つがそろっていなかった（回路にも分かる）

3 つともそろっている。答えは 1。

送る桁を 1 にして、どれか 1 つを化かしてみる。 化けた写しが入っている AND は、0 になる。 けれど、化けていない 2 つの組の AND が、1 のまま残る。 だから OR も 1 のままで、答えは変わらない。

送る桁が 0 のときは、逆に考えればいい。 1 つ化けて 1 になっても、それと組になる相手はどちらも 0 だ。 どの AND も 1 にならず、答えは 0 のままである。

4 桁を、3 回

1 桁でできたなら、4 桁でも同じだ。 4 桁の知らせを、3 回送る。送る桁は、全部で 12 桁になる。

受け取った側は、12 桁を 3 行 4 列に並べる。 そして、縦に並んだ 3 つ（列）ごとに、多数決の回路に通す。 1 桁目の答えは、1 回目・2 回目・3 回目の 1 桁目どうしの多数決、というわけだ。

3 回送る シミュレータ

知らせを決めてから、⚡ で好きな桁を化かしてみてください

送る側

知らせ

↓ 同じ 4 桁を 3 回送る（12 桁）

1 回目
1
0
1
1
2 回目
1
0
1
1
3 回目
1
0
1
1

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

1 回目
2 回目
3 回目

↓ 化けた桁：0 か所

受け取る側

1 回目
1
0
1
1
2 回目
1
0
1
1
3 回目
1
0
1
1

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

↓ 縦の 3 つずつ（列ごと）に、多数決の回路に入れる

答え
1
0
1
1

緑の ✓ ＝ その列の 3 つがそろっていなかった（回路にも分かる）

3 回ともそろっている。受け取った知らせは 1011。

どこか 1 か所を化かしてほしい。 その列に ✓ が付き、受け取った知らせは元どおりになる。

では、1 桁目の列で 1 つ、3 桁目の列で 1 つ、と列を変えて化かしたら？ どちらの列も、化けたのは 1 つだけだ。だから両方とも直る。 4 つの列で 1 つずつなら、4 か所化けても、全部直る。

自信満々で、間違える

今度は、同じ列の中で 2 つを化かしてほしい。 たとえば、3 桁目の列の、1 回目と 2 回目。

受け取った知らせの 3 桁目が、送ったのとは逆になる。 しかも、答えのマスには緑の ✓ が付いている。 回路は「1 つだけ食い違っていたので、直しておいた」という顔をしている。

化けた 2 つのほうが、多数になってしまったのだ。 受け取った側から見れば、2 対 1 で割れた列にすぎない。 2 つのほうを信じるのが多数決なのだから、そうするしかない。

前回のパリティは、2 か所化けると、黙ってしまった（ランプが光らない）。 多数決は、2 か所化けると、嘘をつく。

12 桁のうち 2 か所を選ぶやり方は、66 通りある。 そのうち、同じ列の 2 つを選ぶのは 12 通り（4 つの列それぞれに 3 通り）。この 12 通りで、多数決は間違った値に直す。 残りの 54 通りは、別々の列の 2 つなので、両方とも直る。

同じ列の 3 つを、全部化かしたらどうなるだろう。 3 つはそろって見えるので、✓ も付かない。回路は、気づきもしない。

それでも多数決が役に立つのは、前回と同じ理由だ。 化けることがめったに起きないなら、同じ列に 2 つが重なるのは、もっとめったに起きない。

この「自信満々で間違える」という弱点には、このシリーズで、もう一度出会うことになる。

3 倍は、高い

ここまでを、前回の表に書き足そう。

やり方送る桁数1 か所化けたら2 か所化けたら
そのまま4気づかない気づかない
パリティ5気づく気づかない
3 回送る12直す別の桁なら直る。同じ桁の 2 回なら、間違った値に直す

「気づく」から「直す」へ、1 段上がった。 けれど、送る桁数を見てほしい。

パリティは、知らせ 4 桁に 1 桁を足して、気づいた。 3 回送るやり方は、4 桁に 8 桁を足して、直した。 足した桁は、1 桁から 8 桁へ、8 倍になっている。

同じ桁を 3 回送れば、多数決で直せる。けれど直すには、気づくよりずっと多くの余分な桁が要る。

それでも、この素朴なやり方は、実際に宇宙で使われてきた。

1960 年代、アメリカの 2 人乗りの宇宙船ジェミニは、計算機のプログラムを磁気テープに記録して積んでいた。 当時のテープは、10 万桁に 1 桁ほど読み違えた。 計算機をつくった IBM は、これを 10 億桁に 1 桁にまで減らしたかった。

2 人の飛行士が並んで乗った、ジェミニ宇宙船の断面図

ジェミニの断面図（NASA の絵）。2 人が肩を並べて乗る

とったやり方は、この回のシミュレータとほとんど同じだ。 プログラムを3 回ずつ記録し、対応する 3 つの桁を 1 桁ずつ多数決の回路に通してから、計算機の記憶へ送った。 この装置は、1966 年のジェミニ 8 号から積まれた。

10 万桁に 1 桁化けるテープで、3 つのうち 2 つ以上が同時に化けるのは、計算すると、およそ 33 億桁に 1 桁になる（3 つの化け方が、それぞれ無関係に起きる、とした場合）。 目標の 10 億桁に 1 桁を、上回っている。 そのかわり、テープの 3 分の 2 は、繰り返しのために使うことになる。

多数決は、知らせを繰り返すだけでなく、回路そのものを 3 つ並べる形でも使われた。 月へ向かったサターン V ロケットの誘導コンピュータは、同じ回路を 3 組持ち、あちこちの信号を多数決にかけていた。

繰り返す回数を増やせば、もっと強くなる。 5 回送れば、同じ列で 2 つ化けても直せる。そのかわり、5 倍の桁を送ることになる。

直すたびに、こんなに払わなければならないのだろうか。

思い出してほしい。 前回の「気づく」は、たった 1 桁でできた。

気づくを組み合わせて、どこが化けたかまで分からないか。 場所さえ分かれば、直せるかもしれない。

次回は、パリティを 1 つではなく、いくつか置いてみよう。

参考文献

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