デジタルデータの誤り検出・誤り訂正（前編）

デジタルデータは、データ伝送中や書き込み中の異常、経年劣化など様々な要因でデータ誤りが発生する可能性があるので、実際に使用する情報データが元の情報データと同じであることを確認する手法として、「誤り検出符号」を付加する方式がよく用いられています。

誤り検出符号とは

誤り検出符号とは、デジタルデータの誤りを検出するために用意された追加のデータのことで、本来の情報データを元に算出された冗長ビットが付加されます。

この誤り検出符号を用いた代表的な方式として、今回はチェックサムとパリティチェックについて説明します。

その名の通り、情報データの合計値（SUM値）を誤り検出符号にして正否確認（チェック）する方式です。
チェックサムの計算には特別な決まり事はなく、送信側であらかじめ決められた方法で情報データの合計値を算出し、誤り検出符号として情報データに付加します。受信側は、受信した情報データを送信側と同じ方法で合計値を算出して、誤り検出符号から送信側の情報データと同じであることを確認します。

チェックサムの例

16bytesを1ワード列とし、各byteデータ加算合計の下位8bitの補数を誤り検出符号とします。

各byteデータの合計値 =
　0x00 + 0x11 + 0x22 + 0x33 + 0x44 + 0x55 + 0x66 + 0x77+ 0x88 + 0x99 + 0xAA + 0xBB + 0xCC + 0xDD + 0xEE + 0xFF = 0x7F8

上記の例では、各byteデータの合計値は 0x7F8 で、その下位8bit は 0xF8、この値の補数は 0x07 になるので、この 0x07（算出した誤り検出符号）を情報データに付加します。
受信側では誤り検出符号を含む1ワード列の総合計値を算出し、その下位8bitの値が 0x00 になるかどうかを判断します。

上述の例で正しくデータが受信された場合は、
　　0xF8（受信データのSUM値下位8bit） +  0x07（誤り検出符号） = 0x00
になりますが、受信した1ワード列中のどこかのビットが壊れていた場合の総合計値は 0x00 以外の値になるため、受信データにビットエラーがあったことを検出できます。
チェックサムはデータの合計値だけで誤り検出を行うため、例えばデータの順番が違った場合でも正しいと判断されることもあり、誤り符号検出としての精度は高くありません。しかしながら、付加される符号のビット数が少なく、算出が簡単で高速処理ができることから、簡易的な誤り検出方法として広く用いられています。

パリティとは偶奇性という意味で、ビット列に含まれる「1」の個数が偶数か奇数かを表すパリティビットを付加してビットエラーの有無を判断する誤り検出方法です。とてもシンプルな誤り検出方法のためシリアル通信などにも使用されており、UART通信では通信の信頼性を確保するためにこのパリティビットを設定することができます。

偶数パリティと奇数パリティ

パリティビットの値は、ビット列に含まれる「1」の個数とパリティビットを足した全体の和が、常に偶数もしくは奇数のどちらかに統一されるように設定します。

• 「1」の個数が偶数個であればパリティビットを ’0’ とする方式 ： 偶数パリティ（even parity）
• 「1」の個数が奇数個であればパリティビットを ‘0’ とする方式 ： 奇数パリティ（odd parity）

偶数パリティでの16bitデータの例

上記例の16bitデータ中の「1」の個数は8個（偶数個）なので、偶数パリティの場合のパリティビットは ’0’ になります（この例で、奇数パリティにした場合のパリティビットは ’1’ になります）。
演算としては全てのbitを排他的論理和（Exclusive OR）することで算出できます。

垂直水平パリティ

先のパリティチェックでの16bitデータの例のように、一定のビット列ごとにパリティを算出して末尾にパリティビットを付加する方式を「垂直パリティ（vertical parity）」と呼びます。一方、この一定のビット列を単位ごとに区切り、各データ列の同じ位置のビットをグループ化し、このグループに対してパリティビットを算出して付加する方式のことを「水平パリティ（horizontal parity）」と呼びます。
そして、この垂直パリティと水平パリティを併用する方式のことを「垂直水平パリティ」と呼び、この方式を用いることで同一ブロック中の誤りを検出したり、1ビットの誤り訂正を行うことができるようになります。

計算する方向を考えると「垂直」と「水平」が逆のように思われるかもしれませんが、一定のビット列を一つのグループとして、グループ内で独立して計算するのが「垂直パリティ」、他のビット列のグループに関連して計算するのが「水平パリティ」とお考えください。

垂直水平パリティを用いた誤り検出・訂正の例

• 例えば、bit[9]のデータが反転していた場合

• もし、2bit（下図の例では bit[6]とbit[9]）のデータが反転していた場合

上述の垂直水平パリティのように、1bitエラーの訂正もしくは2bitエラーを検出するために付加される符号、またはその検出機構のことを、ECC（Error Correction Code（誤り訂正符号）／Error Check and Correct（誤り検出・訂正））と言います。

垂直水平パリティを用いたECCのデメリット

垂直水平パリティを使っても ECC（誤り検出・訂正）を実現することはできますが、本来の情報データ量に対して、誤り検出・訂正符号（冗長ビット）の数は、他のECCと比べて若干大きくなります。冗長ビットが大きくなると、その分だけメモリの容量を増やすことになります。

メモリ容量の消費はコストに反映されしまうので、ECCの誤り検出・訂正符号のビット数はできる限り少なくすることが求められます。そのため、メモリに搭載されるECCに垂直水平パリティは不向きであり、主には別の検出・訂正符号が用いられています。

今回は、代表的な誤り検出・訂正符号である、チェックサムとパリティチェックについて説明しました。
どちらも、算出や検証が容易であることから広く普及している誤り検出符号になりますが、本記事で紹介した垂直水平パリティのように、基本のパリティチェックを応用することでECC（1bitエラー訂正、2bitエラー検出）として機能させることもできます。このECCには多種多様な検出機構がありますが、次回は「デジタルデータの誤り検出・誤り訂正（後編）」でハミング符号を用いたECCのアルゴリズムについて説明します。

丸文では、データ信頼性のためのECC機能を内蔵したメモリ製品やFlash/SRAM搭載マイコン製品を多数取り扱っておりますので、以下の製品紹介ページもご参照ください。