スマホで友達に「おはよう」とメッセージを送った時、一瞬で相手に「おはよう」というメッセージが届きますよね。
とても当たり前のことですが、実はとても凄いことが行われています。
とても凄いことの一つに「データの誤り制御」があります。データが物理的に相手に届くまでに間の様々なノイズによるデータ間違いを検知し、直してくれるものです。
今回はデータの誤り制御における、「誤り検知」と「誤り訂正」に関して解説します！
誤り訂正とは？
まず、下の図を見てください。
これは、スマホから「1111」というデータを送った際、WiFiルータやインターネット網などを経て、相手のスマホにデータが届くまでに、様々なノイズを受けてデータが間違えていくことをイメージしたものです。
コンピュータにおけるデータは最終的に「０」か「１」のどちらかになりますが、物理的には電気的な波形のデータとして信号として取り扱われます。
電気的なデータなので、有線のケーブルや無線の電波の中に電気が通ることになります。なので、伝送距離が長くなれば、波形が崩れてきますし、妨害電波などが入れば、これまた波形が崩れます。
波形が崩れれば、本来「１」になる波形が「０」と間違えられてしまいます。これが「データの誤り」です。
物理的なノイズを完全に防ぐことはできないので、このデータ誤りを検出したり、訂正したりする仕組みがあります。
これからいくつかの「誤り検出」や「誤り訂正」を手法を解説します。
パリティチェック
先ずはデータの誤りを検出するシンプルな方法としてパリティチェックがあります。
これは送信するビット列に対して、パリティビットと呼ばれる検査用のビットを付加することで、データの誤りを検出します。
パリティビットを付加する方法は「偶数パリティ」と「奇数パリティ」の2種類ありますが、そんなに難しくありません。
偶数、奇数パリティ
- 偶数パリティ：ビット列の中の「１」の数が偶数になるようにパリティビットの値をセットする
- 奇数パリティ：ビット列の中の「１」の数が奇数になるようにパリティビットの値をセットする
下にイメージを載せてますが、生成されるビット列の「１」が偶数になるか奇数になるか決めるだけですね。
では、このパリティビットを使ってデータを送る場合の例を考えます。
元のデータが「1010011」で偶数パリティを使うとデータの先頭にパリティビットとして「０」を付けて「01010011」として伝送します。
伝送後のデータが「01010001」だった場合、偶数パリティなのに「１」が「3個」で奇数になっていますので、データに誤りがあることが分かります。
このようにしてパリティチェックでデータの誤りを検出できるので、この後にデータ訂正を行うことができます。
ただし、二つのビットエラーが発生すると、「１」の数が偶数なので、エラーには気付けないという欠点もあります。
水平垂直パリティチェック
パリティチェックは誤り検出だけでしたが、誤り訂正も行うための手法が「水平垂直パリティチェック」になります。
この手法は伝送するデータを文字などの単位に区切って並べて、区切ったデータ単位とビットの位置単位でそれぞれパリティビットを付加します。
水平垂直パリティ
- 垂直パリティ：データ単位でパリティビットを付加する
- 水平パリティ：データを並べた時の各ビット位置単位でパリティビットを付加する
この二つのパリティを組み合わせると縦横両面から誤りを検出できるようになるので、1ビットの誤りであれば、誤りの位置を特定することができ、そこの誤り訂正ができます。
言葉だけだとちょっとわかりにくいので、以下の図を見て頂ければと思います。
水平パリティと垂直パリティがおかしかった場合に、そのデータ列の交差部分に誤りがある、ということですね。
ただし、2ビット以上の誤りになってしまうと位置の特定ができなくなるので、その場合は誤り訂正ができない、ということも覚えておいた方が良いですね。
CRC（巡回冗長検査）
では、複数のビットに誤りが発生していた時はどのように検出したら良いのでしょうか？
その解決方法として、「CRC（Cyclic Redundancy Check）：巡回冗長検査」があります。
これは伝送するデータのビット列を「生成多項式」と呼ばれる特定の式で割り、計算結果の余りをチェック用のデータとして付加する方法です。
データの送信側は計算で求められた余りを、元々のビット列に付加して送信します。
これにより、伝送後のデータは誤りが無ければ、同じ生成多項式で割った時に余りが無い、つまり割り切れる数になります。
もしも余りが出た場合は「誤りがある」ということで、誤りを検出できることになります。
CRCはパリティチェックと同じくデータの誤り訂正は行えないのですが、連続したビットの誤りを検出することができることがメリットです。
バースト誤りの検出なんて呼びますね。
BER（ビット誤り率）
BER（Bit Error Rate）は受信したデータのビット列の中に、どのくらいの割合でビットの誤りが発生しているのかを表す指標です。
計算式としては以下のようになります。
BERの計算式
$$\begin{align*} ビット誤り率（BER）= 誤りが生じたビット数 ÷ 送信ビット数 \end{align*}$$
例えば8ビットのデータを100回送って、2ビットの誤りが発生した場合のBERは以下のようになります。
$$\begin{align*} ビット誤り率（BER）&= 2 ÷ (8 \times 100) \\
&= 2.5 \times 10^{-3} \end{align*}$$
BERを使って回線の品質とかの評価に使えますね。
まとめ
今回はデータの誤り検出と誤り訂正に関して解説してきました。
データの誤り検出と誤り訂正のまとめ
- データの伝送において、ビットの誤りは発生するため、誤り検知や誤り訂正が必要
- パリティチェックによって、1ビットの誤り検出が可能
- 水平垂直パリティチェックにより、1ビットの誤り訂正が可能
- CRCにより連続した誤り（バースト誤り）の検出が可能
- BERを使って誤りの品質を算出することができる
データの誤り検出や訂正によって、インターネットなどから取得するデータを正しく表示できていることが分かりますね。とても重要な技術ですね。
データの誤り検出や誤り訂正に関しては、この記事で解説したもの以外に「ハミング符号」や「リード・ソロモン符号」、「ターボ符号」などがありますので、機会があったら調べてみてください。
尚、デジタルにおける「０」と「１」の考え方に関しては、以下に記事で解説してますので、あわせて読んで頂ければと思います。
以上です！
