前方誤り訂正

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

前方誤り訂正(ぜんぽうあやまりていせい、: Forward Error Correction, FEC)は、データ転送における誤り制御システムの一種。メッセージ送信者がメッセージに冗長性を付与することで、追加情報を送信者に要求することなく、受信者が誤りを(ある時間以内に)検出し訂正することを可能にする。一方向誤り訂正とも。前方誤り訂正の利点は、データの再送を防ぐことで高スループットを平均的に達成する点である。このため、再送がコスト高になる場合や不可能な場合に適用される。

FEC機器はアナログ信号の受信機に近い位置に設置され、受信側のデジタル信号処理の最初の段階で行われる。つまり、FEC回路はアナログ-デジタル変換回路の一部として組み込まれていることが多い。FEC符号器の多くはビットエラーレート信号も生成でき、アナログ受信電子回路のチューニングのためのフィードバックとして使われる。ビタビアルゴリズムなどのFECアルゴリズムの多くは、入力として(擬似)アナログデータをとり、出力としてデジタルデータを生成する。

訂正可能な誤りの程度は、符号の設計段階で決定される。そのため、個々の前方誤り訂正符号にはそれぞれに適した利用条件がある。

動作原理[編集]

FEC は、転送すべき情報に予め設定されたアルゴリズムに従って冗長性を付与することでなされる。それぞれの冗長ビットは常に、多数の本来の情報ビット群を引数とする複雑な関数となっている。本来の情報が符号化された出力にそのまま含まれるかどうかは方式による。変更されていない入力が出力符号に含まれる場合を系統的(systematic)、そうでない場合を 非系統的(nonsystematic) と称する。

非常に単純な例として、3ビットぶんの信号で1ビットのデータを転送する方式がある。3ビットがほぼゼロであれば、転送ビットはゼロの可能性が高く、3ビットが全て 1 なら、転送ビットは 1 の可能性が高い。最も単純な誤り訂正の例としては、受信機においてそれぞれの3ビット毎の信号について多数決で出力を決定する方式である。

受信された3ビット その解釈
000 0
001 0
010 0
100 0
111 1
110 1
101 1
011 1

これは、FECとしてはあまりにも貧弱だが、基本原理はこの通りである。実際典型的な FEC 符号では、現在受信中のビット列グループ(一般に 2ビットから8ビット)を復号するのに、その直前の数百ビットの内容を利用する。

ノイズ平均化による誤り削減[編集]

FEC は「ノイズ平均化; averaging noize」を利用した方式と言える。個々のデータビットが転送すべき複数のシンボルに関わっているため、一部がノイズによって破壊されても本来のユーザーデータをそこから引き出すことができる。これは保険会社がリスクを分散する方法に似ている。

  • このようなリスク分散効果により、FEC を利用したデジタル通信システムは、ある程度のSN比までは完璧に機能する。ただしSN比が限界を越えると全く機能しない。
  • その(全てか無かという)傾向は、シャノン限界で定められる理論的限界に近い強い符号ほど顕著である。

種類[編集]

FEC はブロック符号畳み込み符号に分類される。

  • ブロック符号はビット列やシンボル列を固定サイズのブロック(パケット)に分割した上で符号化する。
  • 畳み込み符号は任意長のビット列やシンボル列を対象とする。
  • 畳み込み符号は必要ならブロック符号に変換可能である。
  • 畳み込み符号はビタビアルゴリズムを使って復号されることが多いが、他のアルゴリズムが使われることもある。

ブロック符号には様々な種類があるが、最も有名な符号はコンパクトディスクDVDやコンピュータのディスクドライブで広く使われているリード・ソロモン符号であろう。他にもゴレイ符号BCH符号ハミング符号などがある。

ハミング ECC はNAND型フラッシュメモリでの誤り訂正によく使われている[要出典]。これは、2ビット誤り検出-1ビット誤り訂正方式である。ハミング符号はより信頼性の高い SLC(single level cell)NAND でのみ使われている。より高密度な MLC(multi level cell)NAND では、もっと強力な多ビット訂正が可能な ECC として、BCH符号やリード・ソロモン符号が使われている[要出典]

ほとんどのブロック符号は、有限体の代数的特性を利用している。

FEC 符号の連結による誤り削減[編集]

ブロック符号と畳み込み符号を「連結」することで、誤り訂正能力を高めることができる。一般に畳み込み符号を基本とし、畳み込み符号の復号器で起きた誤りをブロック符号で訂正する。1986年にボイジャー2号天王星に接近した際に初めて使われて以来、この手法は人工衛星や宇宙探査での通信に標準的に使用されている。

ターボ符号[編集]

誤り訂正における最近(1990年代初期)の進展としてターボ符号がある。この方式は、2つ以上の比較的単純な畳み込み符号を用い、インタリーバと呼ばれる機構によってブロック符号を生成し、シャノン限界に迫る性能を発揮する。

  • ターボ符号の最初の商用利用の1つとして CDMA2000 1x (TIA IS-2000) がある。これはクアルコムが携帯電話向けに開発し、ベライゾン・ワイヤレススプリント・ネクステルなどの事業者によって販売されている。
  • CDMA2000 1x をインターネット向けに改良した 1xEV-DO (TIA IS-856) でもターボ符号が使われている。1x と同様、 EV-DO もクアルコムが開発し、ベライゾン・ワイヤレスなどの事業者が販売している。

関連項目[編集]

参考文献[編集]

外部リンク[編集]