前回
前回に引き続き誤り制御に関しての学習内容をまとめていく。
CRC
CRC: Cyclic Redundancy Check(巡回冗長検査)
送信するデータに生成多項式を適用して、誤り検出用の冗長データを添付する方式。
方法としては参照リンク参照。ムズかったので、簡単に流れだけ記載する。
符号の求め方
- nビットの「符号」を求めるために、左端及び右端のビットが 1 である ( n + 1) ビットのビットパターン (以下，マスクという) を定める。
- ビット列の左端から調べ，最初に値が 1 であるビットの位置に対して、排他的論理和を求めていく
- すべてが0になったときの、右端のnビットを「符号」とする。
データのチェック
- 送信データの右端に「符号」を追加する
- 「符号の求め方」の2と同じ手順で、計算をしていく
- 右端のビット列が0になれば誤りなし、0にならなければ誤りあり と判断する。
参照: 基本情報でわかる CRC 「具体例を見て体験すれば仕組みがわかる
ハミング符号
情報ビットに対して検査ビットを付加することで、2ビットまでの誤り検出と1ビットまでの自動訂正機能を持つ、誤り制御方式。
自動訂正の仕組みを説明する際に必要なXOR演算の特徴について触れておく。
XORの特性について
XOR演算は、復元が可能である。
例
value1, 2の値演算の結果がある。
| value1 | 1 | 0 | 1 | 1 |
| value2 | 0 | 1 | 1 | 0 |
| XOR | 1 | 1 | 0 | 1 |
| AND | 0 | 0 | 1 | 0 |
value2が失われた場合
| value1 | 1 | 0 | 1 | 1 |
| value2 | ||||
| XOR | 1 | 1 | 0 | 1 |
| AND | 0 | 0 | 1 | 0 |
ANDの結果から、value2を復元することが不可能であるが、
XORの結果からは復元が可能である。
符号化
下記のデータを送信する場合について考えていく
| 1 | 0 | 0 | 1 |
- 各ビットに3桁のアドレス情報を付与する。
| 1 | 0 | 1 | 1 |
| 100 | 011 | 010 | 001 |
- 「1」となっているビットのアドレスについて、XOR演算を行う
| 1 | 0 | 0 | |
| 0 | 0 | 1 | |
| 0 | 1 | 0 | |
| XOR | 1 | 1 | 1 |
この、111が「符号」となるので、データ送信時には符号を付与した
| 1 | 0 | 1 | 1 | 1 | 1 | 1 |
を送信する。
エラー検知方法
データが送信された場合のエラー検知方法を考えていく
| 1 | 0 | 1 | 1 | 1 | 1 | 1 |
アドレス情報を付与すると次のようになる
| 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 100 | 011 | 010 | 001 |
1となっている部分について、XOR演算を行う
| 0 | 0 | 1 | |
| 0 | 1 | 0 | |
| 1 | 0 | 0 | |
| XOR | 1 | 1 | 1 |
この結果を、符号で更にXOR演算を行う
| 1 | 1 | 1 | |
| 1 | 1 | 1 | |
| XOR | 0 | 0 | 0 |
誤りが存在する場合には、演算結果が000にならない。
誤り訂正方法
次に、誤りがあった場合の訂正方法について説明を行う
※ 青色部分が1から0になっている。
| 1 | 0 | 1 | 0 | 1 | 1 | 1 |
エラー検知時と同様にXOR演算を行う
| 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 100 | 011 | 010 | 001 |
1のアドレスと、符号でXOR演算を行う
| 1 | 0 | 0 | |
| 0 | 1 | 0 | |
| 1 | 1 | 1 | |
| XOR | 0 | 0 | 1 |
ここで、XOR演算の結果が「000」ではなく「001」となっている。
この結果を見れば、「送信データに誤りがあること」と「誤りのあるデータのアドレスが001」であることがわかる。
わかるけどわからない。
参考:ハミング符号の大枠を掴もう 誤り検出・訂正基礎講座 第2回
以上で「符号化と伝送」については終了。
次回から3章の勉強をしていく。 うーん。なんとなくは理解した気がする。
コメント