基本情報技術者試験向けに、誤り検出と誤り訂正の仕組みをわかりやすく解説します。
パリティチェック、CRC、ハミング符号の特徴を初心者向けに整理しています。
誤り検出とは
コンピュータ同士が通信を行う際、データは0と1のビット列として送受信されます。しかし、通信経路にはさまざまな要因が存在するため、送信したデータが必ずしもそのまま受信されるとは限りません。
例えば、ネットワークケーブルのノイズや電波干渉、機器の故障などが原因で、データの一部が書き換わってしまうことがあります。
データの誤りをそのまま放置すると、ファイルの破損やシステム障害、通信内容の誤認識などの問題が発生する可能性があります。そのため、ネットワーク通信ではデータの誤りを発見したり修正したりする仕組みが必要になります。
パリティチェックとは
パリティチェックとは、送信するデータに「パリティビット」と呼ばれる検査用のビットを1つ追加し、受信側でデータの整合性を確認します。
偶数パリティと奇数パリティ
パリティチェックには偶数パリティと奇数パリテ次の2種類があります。
| 種類 | 内容 |
|---|---|
| 偶数パリティ | 1の個数を偶数にする |
| 奇数パリティ | 1の個数を奇数にする |
垂直水平パリティ
送信データを縦に並べて水平方向に付加する「水平パリティ」、垂直方向に付加する「垂直パリティ」があります。
水平垂直パリティチェックは、1ビットの誤りであれば、位置が特定できるため、誤りを訂正できます。
パリティチェックの欠点
パリティチェックは仕組みが単純で実装しやすいですが、次のデメリットがあります。
- 2ビット以上の誤り（反転）が発生した場合に、誤りを検出できない
- 水平垂直パリティチェック以外は、エラーの「訂正」ができない
強固なエラー対策が必要な場合は、高精度な検出が可能なCRC（巡回冗長検査）や、自動訂正もできるハミング符号などの手法が採用されます。
CRC（巡回冗長検査）とは
CRC（Cyclic Redundancy Check：巡回冗長検査）も、データが途中で壊れていないかを確認するための誤り検出方式です。
CRCの特徴
CRCは次の特徴があります。
- データの誤りを高い確率で検出できる
- 計算が高速でハードウェア実装しやすい
- Ethernet、USB、SSD、ZIPファイルなど幅広い分野で利用されている
- 誤りを「検出」する仕組みであり、基本的には誤りを「訂正」することはできない
- CRCは誤りの検出に優れているが、CRC単体では誤り訂正はできない
- パリティビットでは検出できなかったバースト誤りをより複雑な生成多項式による演算を行うことで検出できるという長所があります。
CRCの仕組み
送信するデータに対して、あらかじめ決められた生成多項式を用いて計算し、CRC値（検査用データ）を求めて、送信データ一緒に送信します。
受信したデータとCRC値に対して、送信側と同じ計算を行います
CRCでは、データを2進数として扱い、生成多項式による2進数の除算（排他的論理和：XORを用いた割り算）を行います。
試験ではCRCの詳細な計算問題よりも、CRCの特徴を問われることが多いです。
計算方法に関する問題が出たとしても説明ありきで出題されます。
ハミング符号とは
ハミング符号は、データの誤りを検出するだけでなく、誤りを自動的に訂正できる誤り訂正符号です。
ハミング符号の特徴
- ビット誤りを検出・訂正できる
- 2ビット誤りを検出できる（構成による）
- メモリや通信機器で広く利用されている
- ECCメモリの基礎技術として使われる
ハミング符号 誤り訂正の例
以下は、ハミング符号を使用した誤り訂正の例です。
検査ビットを付加して、検査ビットとデータビットで計算が成立するかどうかで誤りを検出し、訂正が可能です。
情報処理技術者試験では、ハミング符号を使用した誤り訂正の計算問題が出る場合、計算式は提示されるので、計算式を覚える必要はありません。
FAQ
- 偶数パリティと奇数パリティの違いは何ですか？
偶数パリティは、データ中の「1」の個数が偶数になるようにパリティビットを設定し、奇数パリティは、奇数になるように設定します。
どちらも誤り検出能力に大きな違いはありません。 - CRCとパリティチェックの違いは何ですか？
CRCはパリティチェックよりも高い精度で誤りを検出できます。 - 基本情報技術者試験ではどこがよく出題されますか？
- 偶数パリティと奇数パリティの違い
- 垂直水平パリティによる誤り訂正
- CRCは誤り検出であり訂正はできない
- ハミング符号は1ビット誤りを訂正できる
腕試し（理解テスト）
腕試し（理解テスト）に挑戦する場合はこちらをクリック。
コメント