シリーズ「コンピュータの誤り訂正のしくみ」 第6回
回路が「散らす」とは？
傷は、まとめて化かす
ここまでの回を、短く振り返っておこう。
第1回は、4 桁の知らせに、1 の数を偶数にそろえる検査の桁を 1 つ足した（パリティ）。1 か所化けると、気づけた。 第4回は、検査の桁を 3 つにした（ハミング符号）。光ったランプを 2 進数として読むと、化けた桁の番号になり、1 か所なら直せた。 前回は、もう 1 桁、全体のパリティを足して 8 桁にした。 1 か所なら直し、2 か所なら、直さずに「直せない」と知らせる。
ただし、ここまでの話には、ひとつ前提があった。 化けるのは 1 か所か 2 か所、それも、ばらばらの場所だ、という前提だ。
前回の終わりに、こう書いた。 CD の傷や、一瞬の雷は、隣り合う桁を、まとめて何桁も化かしてしまう。 化けるのが 1 か所・2 か所どころでなかったら、どうすればいいのか。
CD の表面には、0 と 1 を表す小さなくぼみが、細い線に沿って、びっしり並んでいる。 くぼみは、とても小さい。 ほこりや傷のほうが、ずっと大きい。 だから、1 つの傷が、並んだくぼみを、いくつもまとめてまたいでしまう。 CD を開発した Philips の研究者たちも、1982 年の論文で、CD の誤りは、ばらばらに来るより、まとめて来ることのほうが多いと書いている。
電線に雷のノイズが乗るときも、電波が一瞬とぎれるときも、同じだ。 そのあいだに送っていた桁が、続けて化ける。
押して、確かめる
前回の 8 桁で、まとめて化ける傷を受けてみよう。
知らせを 4 通用意して、上から A・B・C・D と呼ぶ。 どの通も、前回と同じ 8 桁にする（知らせ 4 桁 ＋ 検査の桁 4 つ）。 送るのは、全部で 32 桁だ。
まずは素直に、1 通ずつ送る。 A の 1〜8 番、B の 1〜8 番、C の 1〜8 番、D の 1〜8 番の順だ。 送る側の各マスの下の小さな数が、送る順番である。
傷は、送る順で、続けて何桁かを化かす。 長さと位置は、シミュレータの下のボタンで変えられる。
1 通ずつ送る シミュレータ
傷の長さを変えたり、傷をずらしたりして、4 通の判定を見てください
送る側（8 桁の知らせを 4 通）
マスの下の小さな数＝送る順番
A の 8 桁、B の 8 桁、……と 1 通ずつ送る
↓ 32 桁を、この順に送る（文字＝どの通の桁か）
傷：送る順で 11〜12 番目の 2 桁
受け取る側（4 通に積み直す）
- A：化けていない
- B：2 か所 → 直さずに「直せない」と知らせる
- C：化けていない
- D：化けていない
○ 無事 ✓ 直した ？ 直せない（直さずに知らせる）
✗ 送ったのと違う（あなたにだけ見える）
1 通ずつ、第5回の回路に通す
赤い枠は、あなたにだけ見えている。受け取った側の回路には見えない
B には 2 か所が集まった。その通は直さずに「直せない」と知らせる。
最初は、長さ 2 の傷が、送る順で 11 番目と 12 番目に当たっている。 B の 3 番と 4 番だ。
B には、2 か所が集まった。 前回の回路は、正直に「直せない」と知らせる。 A・C・D は無事だが、B の知らせは失われた。
化けたのは、32 桁のうち、たった 2 桁だ。 それでも、同じ通に 2 か所集まると、もう直せない。
傷の長さを 3 にしてみてほしい。 B に 3 か所が集まり、今度は、回路は何かを「直して」しまう。右端の印は ✗ だ。 前回の回路が約束したのは、1 か所なら直し、2 か所なら気づく、まで。 3 か所以上は、約束の外である。
もう 1 つ、試してほしいことがある。 長さを 2 に戻して、「後ろへ ▶」で、傷を送る順の 16 番目と 17 番目までずらしてみてほしい。 B の 8 番と、C の 1 番だ。 傷は同じ長さなのに、今度は、B と C に 1 か所ずつ。両方とも直る。
傷の長さは変わっていない。 変わったのは、傷がどの通に、何か所ずつ当たったかだけだ。
縦に、送る
傷がたまたま通の境目をまたぐと、1 か所ずつに分かれて、直った。 それなら、たまたまに任せず、いつでも分かれるように送ればいい。
4 通を、上から A・B・C・D と積んで、4 行 8 列の表にする。 そして、表を縦に読んで送る。
- 1 番の列を、A・B・C・D の順に
- 次に 2 番の列を、A・B・C・D の順に
- ……8 番の列まで
送る 32 桁は、A・B・C・D・A・B・C・D……と、4 通の桁が 1 桁ずつ交互に並ぶ。 受け取った側は、32 桁がそろったら、同じ決まりで 4 行 8 列の表に積み直す。 そして、1 通ずつ、前回の回路に通す。
こうすると、送る順で隣り合う桁は、いつも違う通の桁になる。 続けて 4 桁化けても、その 4 桁は、A・B・C・D に 1 桁ずつ入る。
こうして、いくつかの知らせの桁を、交互に差し込むように並べ替えて送ることを、インターリーブという。 英語で「交互に差し込む」という意味だ。
並べ替えといっても、特別な回路は要らない。 表に書き込む順番と、表から読み出す順番を、変えるだけだ。 『記憶のしくみ』を読んだ人は、第8回のメモリを思い出してほしい。番地を指せば、どの番地でも同じ手間で読み書きできた。書くときは行の順に、読むときは列の順に番地を指せば、それで並べ替えになる。
散らして、送る
下のシミュレータは、同じ 4 通を、列ごとに送る。 送る順の帯の文字が、A・B・C・D・A・B・C・D……と並んでいるのを確かめてほしい。
並べ替えて送る シミュレータ
傷の長さを 1 から 8 まで変えて、4 通の判定を見てください
送る側（8 桁の知らせを 4 通）
マスの下の小さな数＝送る順番
1 番の列を A・B・C・D、2 番の列を……と、列ごとに送る
↓ 32 桁を、この順に送る（文字＝どの通の桁か）
傷：送る順で 11〜14 番目の 4 桁
受け取る側（4 通に積み直す）
- A：1 か所 → 4 番を直した
- B：1 か所 → 4 番を直した
- C：1 か所 → 3 番を直した
- D：1 か所 → 3 番を直した
○ 無事 ✓ 直した ？ 直せない（直さずに知らせる）
✗ 送ったのと違う（あなたにだけ見える）
32 桁がそろってから、4 通に積み直して、1 通ずつ第5回の回路に通す
赤い枠は、あなたにだけ見えている。受け取った側の回路には見えない
傷は 4 桁。化けた桁は、4 通に 1 か所ずつ散らばった。全部直った。
長さ 4 の傷が、送る順で 11〜14 番目に当たっている。 積み直すと、C の 3 番、D の 3 番、A の 4 番、B の 4 番。 4 通に 1 か所ずつだ。 4 通とも、直った。
傷の長さを 1 から 4 まで変え、「◀」「▶」で位置も動かしてみてほしい。 長さ 4 までなら、どこに傷が来ても、全部直る。
今度は、長さを 5 にしてみる。 5 桁目は、どこかの通の 2 か所目になる。 その通は、「直せない」と知らせる。
6、7、8 と伸ばしても、同じだ。 2 か所が集まる通が増えるだけで、どの通も、間違って直すことは一度もない。 長さ 8 までなら、1 通に来るのは、多くても 2 か所だからだ。
まとめると、こうなる。
- 4 桁までの傷なら、直す
- 8 桁までの傷なら、直せないと気づく
ここで、前回足した 8 桁目が効いている。 第4回の 7 桁のままだったら、1 通に 2 か所集まったとき、化けていない桁を「直して」しまっていた。
最後に、上の切り替えで「1 通ずつ」を選んでみてほしい。 傷は、送る順の 11〜14 番目のまま。同じ瞬間に来た、同じ傷だ。 それなのに、今度は 4 桁すべてが B に集まり、B は直せない。
数は、同じ
2 つの送り方を、比べてみよう。
化けた桁の数は、同じだ。 どちらも、32 桁のうち 4 桁。 違うのは、その 4 桁が、4 通にどう散らばったか、だけである。
そして、検査の桁は、1 桁も増えていない。 1 通は、どちらも前回の 8 桁のまま。回路も、前回のまま。 変えたのは、送る順番だけだ。
並べ替えて送るだけで、まとめて来た誤りを、ばらばらの 1 か所ずつに変えられる。検査の桁は、1 桁も増やさなくていい。
これまでの回で、直す力を上げるには、いつも桁を足してきた。 パリティで 1 桁、縦横で 4 桁、ハミング符号で 3 桁、前回でもう 1 桁。 この回は、足さない。 回路が「散らす」というのは、傷が 1 か所に集まらないように、先回りして並べておくことだ。
かわりに、払うものがある。待つことだ。 送る側は、4 通がそろうまで、1 番の列を送り始められない。 受け取った側は、ほとんど全部の桁が届くまで、どの通も積み直せない。 1 通ずつ送るなら、A は最初の 8 桁で届き終わるのに。
実は、このシリーズには、もう 1 つ、似た表があった。 第2回では、4 桁の知らせを 3 回送り、受け取った側は 12 桁を 3 行 4 列に並べて、列ごとに多数決をとった。 そのとき、「4 つの列で 1 つずつなら、4 か所化けても、全部直る」と書いた。 そして、12 桁をどんな順番で送るのかは、決めずにおいた。
1 回目の 4 桁、2 回目の 4 桁、3 回目の 4 桁、と送るなら、それは列ごとに散らして送っているのと同じだ。 送る順で隣り合う桁は、いつも違う列の桁になる。続けて 4 桁化けても、4 つの列に 1 つずつで、全部直る。 反対に、1 桁目を 3 回、2 桁目を 3 回、……と送ると、長さ 2 の傷でも、同じ列に 2 つ集まることがある。 その列は、自信満々で間違える。
深く、散らす
積む数を増やせば、もっと長い傷にも耐えられる。
8 通を積んで、列ごとに送ってみよう。 送る順で隣り合う 8 桁は、8 通に 1 桁ずつ入る。 だから、8 桁までの傷なら全部直り、16 桁までなら、直せないと気づく。
2 通なら 2 桁まで、4 通なら 4 桁まで、8 通なら 8 桁まで。 積んだ数が、そのまま、直せる傷の長さになる（1 通が 1 か所まで直せる回路なら）。
もちろん、そのぶん長く待つ。 どれだけ深く散らすかは、どれくらい長い傷が来るのか、どれくらいなら待てるのか、で決めることになる。
CD と QR コード
この考え方は、身近なところで働いている。
1 つは、CD だ。 CD の誤り訂正は、CIRC（Cross-Interleaved Reed–Solomon Code）と呼ばれる。 名前のとおり、「交差させるように並べ替える（Cross-Interleaved）」ことと、リード・ソロモン符号という符号を組み合わせている。
リード・ソロモン符号は、8 桁をひとまとまりの 1 文字として扱い、文字単位で直す符号だ。 まとめて化けても、それが 1 つの文字の 8 桁の中に収まっていれば、1 文字の誤りで済む。 まとめて化ける傷に、もともと強い。 そのうえで、文字の並べ替えも使って、傷を散らしている。
先ほどの Philips の論文によれば、CIRC は、続けて約 4000 桁まで化けても、完全に直せる。 ディスクの上の長さでいえば、約 2.5 mm の傷だ。
もう 1 つは、QR コードだ。 QR コードは、汚れたり、一部が欠けたりしていても、読み取れるように作られている。 中身は、やはりリード・ソロモン符号である。
QR コードを作るときには、誤り訂正の強さを、L・M・Q・H の 4 段階から選べる。 QR コードを考えたデンソーウェーブの説明では、それぞれ約 7%・15%・25%・30% まで復元できる。
この割合は、QR コードの面積に対するものではない。 QR コードの中身を、8 桁ずつの文字（コードワードと呼ばれる）に区切ったときの、文字の数に対する割合だ。 それに、隅にある 3 つの大きな四角は、読み取り機に位置を教えるための模様で、データを運んでいない。 「30% までなら、どこを隠しても読める」という意味ではない。
そして、QR コードの規格では、符号がいくつかのまとまり（ブロック）に分かれているとき、それぞれのブロックの文字を、交互に並べて置く。 この回の、A・B・C・D を 1 桁ずつ交互に送ったのと、同じ考え方である。
さきほどの、右下が破れた QR コードで確かめてみよう。
この QR コードの中身は、70 文字。 それが 35 文字ずつ、2 つのブロックに分かれている。 強さは Q で、1 つのブロックで直せるのは、9 文字までだ。
破れたところに少しでもかかった文字は、15 文字あった。 1 つのブロックで直せる 9 文字を、超えている。 けれど、2 つのブロックの文字は交互に並んでいるので、15 文字は、片方に 7 文字、もう片方に 8 文字と分かれた。 どちらも 9 文字以内。 だから、両方とも直せて、読み取れる。
もし、片方のブロックの 35 文字を置き終えてから、もう片方を置いていたら、どうだっただろう。 QR コードは、文字を右下の角から置いていく。 破れた右下には、片方のブロックの文字ばかりが並ぶことになる。 15 文字が、すべて同じブロックに集まる。 9 文字を超えるので、そのブロックは直せず、QR コードは読み取れない。
破れ方は、同じだ。 違うのは、文字の並べ方だけである。
直しきれない傷
この回で分かったことを、表にしておこう。 1 通は、どれも前回の 8 桁だ。
| 送り方 | 送る桁数 | 直せる傷 | 気づける傷 |
|---|---|---|---|
| 1 通ずつ | 8 | 1 桁 | 2 桁まで |
| 4 通を、列ごとに | 32 | 4 桁まで | 8 桁まで |
| 8 通を、列ごとに | 64 | 8 桁まで | 16 桁まで |
「気づける」は、その長さまでの傷なら、間違って直さずに「直せない」と知らせる、という意味だ。 どの送り方でも、傷をどこに置いても、こうなることを全部確かめた。
それでも、限りはある。 どれだけ深く散らしても、それより長い傷は来うる。
CD も、約 4000 桁より長い傷は直せない。 先ほどの論文によれば、そこから約 12300 桁（約 7.7 mm）までは、直せなかった音を、前後の音から推し量った値で埋める。 それでもだめなら、そのあいだは音を消す。 どちらも、それらしく聞こえるようにしているだけで、元の音を取り戻したわけではない。
しかも、CD の傷は、ディスクに刻まれている。 何度読み直しても、同じところで、同じように化ける。 CD の中身を送り直してくれる相手は、どこにもいない。
けれど、このシリーズの第1回に出てきた、遠くの探査機はどうだろう。 探査機には、知らせを送ってきた相手がいる。
探査機なら、もう一度送ってもらえばいいのではないか。
次回は、このシリーズの最終回。 第1回の、遠くの探査機に戻ろう。
参考文献
- 松下俊介 著. 基礎からわかる論理回路. 第2版, 森北出版, 2021.7. 978-4-627-82842-1. https://ndlsearch.ndl.go.jp/books/R100000002-I031573740
- 今井秀樹 著. 符号理論, 電子情報通信学会, 1990.3. 4-88552-090-8. https://ndlsearch.ndl.go.jp/books/R100000002-I000002038659
- H. Hoeve, J. Timmermans, L. B. Vries. "Error correction and concealment in the Compact Disc system". Philips Technical Review, Vol. 40, No. 6, pp. 166–172, 1982. https://www.bramjacobse.nl/wordpress/wp-content/uploads/2021/03/PTechReview-40-1982-166.pdf, (参照 2026-10-1).
- デンソーウェーブ. "誤り訂正機能について". QRコードドットコム. https://www.qrcode.com/about/error_correction.html, (参照 2026-10-1).
- 日本規格協会. "JIS X 0510 情報技術－自動認識及びデータ取得技術－QRコード バーコードシンボル体系仕様（原案）". 日本規格協会 Webdesk. https://webdesk.jsa.or.jp/pdf/jisnintei/jisgenan_voice/JIS_X0510_情報技術－自動認識及びデータ取得技術－QRコード%20バーコードシンボル体系仕様_加工後_.pdf, (参照 2026-10-1).
- Bobmath. "File:QR Code Damaged.jpg". Wikimedia Commons. https://commons.wikimedia.org/wiki/File:QR_Code_Damaged.jpg, (参照 2026-10-3).
