誤り検出および訂正：データ完全性を守る方式とアルゴリズム

基本原理と一般的な技術

基本的な考え方は、追加のビット、処理量、または時間を用いて信頼性を高めることである。単純な検出方式では、メッセージに短い要約情報を付加し、その要約が一致しなければ誤りとして通知する。より高度な方式では、再送を求めることなく、受信側が正しい内容を推定できる。

• パリティ検査：1の個数が偶数または奇数になるように1ビットを追加する。単一ビット誤りの検出に有用である。
• チェックサムと巡回冗長検査（CRC）：コンパクトな要約値を計算する。ネットワークパケットやファイルにおける連続した誤りの検出に広く用いられる。
• 誤り訂正符号（ECC）：ハミング符号、リード・ソロモン符号、畳み込み符号、ターボ符号などを含む。限られた数の誤りを訂正でき、メモリ、ストレージ、無線システムで使用される。
• 自動再送要求（ARQ）：検出と再送を組み合わせる方式である。遅延を許容できる場合、信頼性の高いトランスポートプロトコルで一般的に使われる。

歴史と発展

誤り制御の理論的基盤は、20世紀のデジタル通信と情報理論の発展とともに形成された。初期の実用的な方式は電信や電話におけるノイズへの対処を目的としていた。その後、形式化された符号理論により、冗長性、誤り耐性、計算コストの均衡を図る体系的な構成法が生み出された。時間の経過とともに、アルゴリズムとハードウェアの進歩によって、現代の高速ネットワークや記憶媒体に向けた、さらに効率的な符号が利用可能になった。

用途と例

誤り制御は、コンピューティングと通信の幅広い分野で用いられている。例として、ハードディスクやソリッドステートメモリ（ECCメモリ）、光学・磁気媒体（コンパクトディスクやDVDは特定の誤り訂正層を使用する）、衛星・携帯電話通信（無線リンクにおける専用の前方誤り訂正）、バーコードとQRコード（リード・ソロモン符号）、インターネットプロトコル（パケットチェックサムと再送戦略）がある。どの方法を選ぶかは、通信路の特性、必要な信頼性、許容可能な遅延、利用できる帯域幅によって決まる。

トレードオフと主な区別

検出のみを行う方式は小規模で低コストだが、別の送信なしには破損したデータを修復できない。訂正方式はより多くの冗長性と処理を必要とする一方、データを即座に復元できる。また、ブロック構造か畳み込み構造か、記号単位かビット単位か、受信側で硬判定を使うか軟判定の指標を使うかによっても設計は異なる。システム設計者は、方式を選択する際に複雑さ、遅延、オーバーヘッドを比較検討する。

実践的な入門や仕様については、データ完全性と符号理論に関する資料を参照できる。データ完全性の概要、プロトコルおよびチェックサムの資料、符号理論に関する技術資料がある。