ホーム
テクノロジ系
A. 基礎理論
Ⅰ. 基礎理論
4. 通信に関する理論

4.4. 誤り検出・訂正

2024.08.25

1. 概要

　「誤り検出・訂正」は、データ通信において非常に重要な役割を果たす技術です。データがネットワークを通じて送信される際、様々な理由でビットの反転やエラーが発生する可能性があります。これにより、送信された情報が受信側で正確に復元できない場合があります。誤り検出・訂正技術は、このようなエラーを検出し、必要に応じて訂正するために設計されています。信頼性の高いデータ通信を実現するため、これらの技術は不可欠です。

　主な誤り検出・訂正技術として、偶数パリティや奇数パリティ、CRC、ハミング符号、ECC（誤り訂正コード）、チェックサムなどがあります。それぞれの技術には特徴があり、状況に応じて適切な方式が選択されます。

誤り検出・訂正方式の特徴比較

方式検出能力訂正能力オーバーヘッド主な用途
パリティチェック1ビットのエラー検出なし低（1ビット）簡易的な通信、メモリ
CRC複数ビットのエラー検出なし中（通常8〜32ビット）ネットワーク通信、ストレージ
ハミング符号複数ビットのエラー検出1ビットのエラー訂正中（log₂n+1ビット）メモリ、通信システム
ECC (拡張ハミング符号)複数ビットのエラー検出複数ビットのエラー訂正高高信頼性メモリ、宇宙通信
チェックサム複数ビットのエラー検出（限定的）なし低〜中インターネット通信、ファイル検証

2. 詳細説明

2.1. パリティチェック

　パリティチェックは、最も基本的な誤り検出の手法の一つです。パリティとは、データビットに付加される1ビットの付加情報で、偶数パリティと奇数パリティの2種類があります。

  • 偶数パリティ：1のビットの総数が偶数になるようにパリティビットを設定します。
  • 奇数パリティ：1のビットの総数が奇数になるようにパリティビットを設定します。

　これにより、1ビットのエラーが発生した場合、そのエラーを検出することができます。

パリティチェックの仕組み

偶数パリティの例

データ: 1 0 1 1 0 0 1 0
1の数: 4つ (偶数)
パリティビット: 0
送信データ: 1 0 1 1 0 0 1 0 0

奇数パリティの例

データ: 1 0 1 1 0 0 1 0
1の数: 4つ (偶数)
パリティビット: 1
送信データ: 1 0 1 1 0 0 1 0 1

パリティチェックの限界

　パリティチェックは単純ですが、2ビット以上のエラーが発生した場合は検出できないという重大な欠点があります。例えば、2ビットが反転すると1の総数の偶奇が変わらないため、エラーを検出できません。また、パリティチェックではエラーの位置を特定できないため、訂正することができません。

2ビットエラーの例:

元データ: 1 0 1 1 0 0 1 0 0 (偶数パリティ)
2ビットエラー: 1 1 1 0 0 0 1 0 0
  ↑ ↑ 
この場合、1の数は4つで偶数のまま、エラーを検出できない

2.2. CRC（Cyclic Redundancy Check）

　CRCは、ブロックデータの誤り検出に広く使用される技術です。送信側では、データブロックに対して特定の生成多項式を用いてCRCコードを計算し、データに付加します。受信側では、受信したデータに同じ多項式を適用し、計算結果がゼロでない場合、誤りが検出されたと判断します。

　CRCの計算は、データをビット列と見なし、それを生成多項式で割った余りをCRCコードとする手法です。このプロセスは多項式除算として知られています。CRCは複数ビットエラーの検出に効果的であり、特にバースト的なエラー（連続したビットのエラー）に対して高い検出能力を持ちます。一般的に使用される生成多項式としては、CRC-16（x^16 + x^15 + x^2 + 1）やCRC-32（x^32 + x^26 + … + x + 1）などがあります。

　CRCは単純なパリティチェックよりも強力な誤り検出能力を持ちますが、訂正機能は持ちません。

CRCの計算例

　例えば、データ「1101」に対して生成多項式「x^3 + x + 1 = 1011」を使用してCRCを計算する過程は次のようになります：

データ: 1101
生成多項式: x³ + x + 1 = 1011

計算手順:
1. データに生成多項式の次数（3）分のゼロを追加: 1101000
2. 多項式除算を実行:

   1101000 ÷ 1011 = 
   1011
   ----
   0110
    1011
    ----
    1010
    1011
    ----
     001 ← 余り (CRC)

3. CRCコード: 001
4. 送信データ: 1101001

2.3. ハミング符号

　ハミング符号は、リチャード・ハミングによって開発された誤り訂正符号で、単一ビットエラーを訂正する能力を持ちます。ハミング符号では、データビットに複数のパリティビットを追加します。それぞれのパリティビットは、特定のビット位置のデータに対応しており、エラーが発生した場合、パリティチェックの結果からエラーの位置を特定できます。

　一般的な(n,k)ハミング符号では、k個のデータビットに対して、n-k個のパリティビットを追加します。パリティビットの数rは、2^r ≥ n+1の関係を満たす必要があります。例えば、(7,4)ハミング符号では、4ビットのデータに3ビットのパリティを追加し、7ビットの符号語を生成します。

　ハミング符号のパリティビットは、2のべき乗の位置（1, 2, 4, 8…）に配置されます。各パリティビットは、そのビット位置を表す2進数で1が立つ位置のビットをチェックします。つまり：

  • 位置1のパリティビット（P₁）は、ビット位置1, 3, 5, 7…をチェック
  • 位置2のパリティビット（P₂）は、ビット位置2, 3, 6, 7…をチェック
  • 位置4のパリティビット（P₃）は、ビット位置4, 5, 6, 7…をチェック

ハミング符号の構造 (7,4)

ビット位置:  1  2  3  4  5  6  7
ビットの種類: P₁ P₂ D₁ P₃ D₂ D₃ D₄
(P=パリティビット、D=データビット)

パリティビットの計算:
- P₁: ビット位置 1,3,5,7 をチェック (D₁,D₂,D₄)
- P₂: ビット位置 2,3,6,7 をチェック (D₁,D₃,D₄)
- P₃: ビット位置 4,5,6,7 をチェック (D₂,D₃,D₄)

　ハミング符号は、単一ビットエラーを訂正できる能力を持ち、データ通信やメモリ保護など、多くのシステムで使用されています。しかし、2ビット以上のエラーに対しては訂正能力を持たず、場合によっては誤った訂正を行う可能性があります。

2.4. ECC（誤り訂正コード）

　ECCは、複数ビットのエラーを検出し、訂正できる高度な誤り訂正技術です。ハミング符号の拡張として考えられることが多く、特にメモリシステムで使用されます。最も一般的なECCの一つは、SECDED（Single Error Correction, Double Error Detection）で、単一ビットエラーを訂正し、2ビットエラーを検出する能力を持ちます。

　一般的なSECDEDの実装では、ハミング符号に全体パリティビットを追加します。この追加のパリティビットにより、2ビットエラーの検出が可能になります。例えば、(72,64)コードでは、64ビットのデータに8ビットのECCを追加し、単一ビットエラーの訂正と2ビットエラーの検出を実現します。

　より高度なECCとしては、Reed-Solomon符号、LDPC（Low-Density Parity-Check）符号、ターボ符号などがあり、これらは複数ビットエラーの訂正能力を持ちます。これらの技術は、光ディスク、デジタル放送、宇宙通信など、エラーが発生しやすい環境で広く使用されています。

　ECCを使用することで、データの信頼性が大幅に向上し、データ破損のリスクを最小限に抑えることができます。

2.5. チェックサム

　チェックサムは、データの誤りを検出するための簡単な手法です。データブロックの全てのビットを加算し、その結果の一部（通常は下位ビット）をチェックサムとして保持します。受信側で同じ計算を行い、送信側と一致しない場合、誤りが発生したと判断されます。

　チェックサムの計算方法にはいくつかのバリエーションがあります。最も基本的な方法は、データをバイトやワード単位で単純に加算するものですが、より高度な方法としては、加算の際にキャリー（桁上がり）を考慮したり、結果を反転（1の補数）したりする方法があります。

　IPヘッダのチェックサムは、16ビット単位での加算と桁上がりの処理、そして最終結果の1の補数を取るという方法で計算されます。

　チェックサムは、特にファイル転送やパケット通信などで使用されますが、複数ビットのエラーに対しては検出能力が限定的です。特に、特定のパターンのエラーでは検出できない場合があります。

3. 応用例

　誤り検出・訂正技術は、さまざまな分野で広く応用されています。

インターネット通信

　TCP/IPプロトコルでは、データパケットの一部にチェックサムを使用してデータの整合性を確認します。エラーが検出されると、パケットが再送信されます。IPヘッダは16ビットのチェックサム、TCPとUDPは疑似ヘッダを含めたチェックサムを使用します。

ディジタルメモリ

　ECCメモリは、コンピュータのメモリ（特にサーバー向け）で使用され、メモリビットの反転によるデータ破損を自動的に検出・訂正します。一般的には、SECDED方式が採用され、64ビットのデータに8ビットのECCを追加しています。

ストレージシステム

　ハードディスクやSSDなどのストレージデバイスでは、データセクターごとにCRCコードが付加され、読み取り時のデータの整合性を確認します。また、RAID（Redundant Array of Independent Disks）システムでは、パリティ情報やミラーリングを使用して、ディスク障害時のデータ復旧を可能にしています。

宇宙通信

　宇宙探査機が地球にデータを送信する際、エラーが発生しやすい環境下で信頼性を確保するため、ハミング符号や他の高度なECC技術（Reed-Solomon符号など）が使用されます。これらの技術は、放射線による影響が大きい宇宙環境で特に重要です。

QRコードや光ディスク

　QRコードはReed-Solomon符号を使用して、コードの一部が損傷しても情報を復元できるようにしています。同様に、CD、DVD、Blu-rayなどの光ディスクも、Reed-Solomon符号を使用して、ディスク表面の傷やほこりによるエラーを訂正します。

4. 例題

例題1

　偶数パリティを使用して、以下の8ビットデータにパリティビットを追加してください。

  • データ: 10110010

偶数パリティでは、1の数が偶数になるようにパリティビットを追加します。この場合、1の数は4つ（偶数）なので、パリティビットは0になります。よって、パリティビットを含めたデータは 101100100 です。

例題2

　 次のデータに対してCRCを計算する生成多項式が x^3 + x + 1 の場合、CRCコードを求めてください。

  • データ: 1101

回答例: 生成多項式を使用して、データビットにCRCコードを付加します。

データ: 1101
生成多項式: x³ + x + 1 = 1011

計算手順:
1. データに生成多項式の次数（3）分のゼロを追加: 1101000
2. 多項式除算を実行:

   1101000 ÷ 1011 = 
   1011
   ----
   0110
    1011
    ----
    1010
    1011
    ----
     001 ← 余り (CRC)

3. CRCコード: 001
4. 送信データ: 1101001

例題3

　ハミング符号を使って以下の4ビットデータを符号化してください。また、符号化後のデータの2ビット目がエラーになったと仮定して、エラーを訂正してください。

  • データ: 1011

回答例: ハミング符号を使った4ビットデータ「1011」の符号化は以下のようになります。

(7,4)ハミング符号では、ビット位置は次のように割り当てられます：

ビット位置:  1  2  3  4  5  6  7
ビット種類: P₁ P₂ D₁ P₃ D₂ D₃ D₄
実際の値:   ?  ?  1  ?  0  1  1

パリティビットの計算（偶数パリティを使用）：

  • P₁（位置1）: ビット位置1,3,5,7の値 → ?,1,0,1 → 合計1の数が2つ（偶数）→ P₁=0
  • P₂（位置2）: ビット位置2,3,6,7の値 → ?,1,1,1 → 合計1の数が3つ（奇数）→ P₂=1
  • P₃（位置4）: ビット位置4,5,6,7の値 → ?,0,1,1 → 合計1の数が2つ（偶数）→ P₃=0

符号化後のデータ: 0110111

2ビット目にエラーが発生した場合（1→0）: 0010111

エラー検出・訂正のプロセス: パリティチェック（受信側）：

  • P₁（位置1）: 0,1,0,1 → 合計1の数が2つ（偶数）→ 正常
  • P₂（位置2）: 0,1,1,1 → 合計1の数が3つ（奇数）→ 正常でないはず→エラー
  • P₃（位置4）: 0,0,1,1 → 合計1の数が2つ（偶数）→ 正常

エラーの位置: P₂に関連するビットのみでエラーが検出された → 位置2（P₂自身）にエラーがある

訂正後: 0110111 (元の符号語に戻る)

5. まとめ

　誤り検出・訂正技術は、信頼性の高いデータ通信を実現するための基本的かつ重要な技術です。パリティチェック、CRC、ハミング符号、ECC、チェックサムなど、さまざまな手法が存在し、それぞれ異なる用途や環境で使用されています。これらの技術を理解し、適切に応用することで、システム全体の信頼性とデータの保全性を大幅に向上させることが可能です。

　これらの誤り検出・訂正技術は、単独で使用されることもあれば、複数の手法を組み合わせて使用されることもあります。近年、より高度な誤り訂正符号としてReed-Solomon符号、ターボ符号、LDPC（Low-Density Parity-Check）符号などが開発され、デジタル放送、光ディスク、QRコード、宇宙通信などで広く使用されています。情報社会の信頼性を支える基盤技術として、誤り検出・訂正の重要性は今後も増していくでしょう。

参考文献・リソース

  1. 情報処理技術者試験 シラバス IPA
  2. デジタル通信理論入門 宮内一洋,若林勇, コロナ社
  3. “Information Theory, Inference and Learning Algorithms” David J.C. MacKay, Cambridge University Press
  4. “誤り訂正技術の基礎” 和田山正, 森北出版

※この記事にはAmazonアソシエイトのリンクが含まれています。購入された場合、収益の一部を得ることがあります。