前方誤り訂正

前方誤り訂正（ぜんぽうあやまりていせい、英: Forward Error Correction, FEC）は、データ転送における誤り検出訂正方式の一種。データ送信時に誤り訂正用の符号をあらかじめ付与することにより、受信者は再送を要求することなく、ただちに誤りを検出し訂正することができる。一方向誤り訂正とも言う。

概要

FEC は「ノイズ平均化; averaging noize」を利用した方式であり、データの一部がノイズによって破壊されても、データを復元することができる。FEC を利用したデジタル通信システムは、ある程度のSN比までは完璧に機能する。ただしSN比が限界を越えると全く機能しない。その（全てか無かという）傾向は、シャノン限界で定められる理論的限界に近い強い符号ほど顕著である。

前方誤り訂正の利点は、誤り検出時にデータの再送を行わないことである。このため、動画配信や音声通話など、完全かつ低遅延が求められるデータ転送において利用される。一方で、誤り訂正用の符号を付与するため、データ量は増加する。訂正可能な誤りの程度は、訂正符号の設計によって異なり、一般に訂正符号のデータ量が多いほど高頻度な誤りを訂正することができる。

種類

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

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

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

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

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

ターボ符号

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

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

関連項目

• 低密度パリティ検査符号

参考文献

• Clark, George C., Jr., and J. Bibb Cain. Error-Correction Coding for Digital Communications. New York: Plenum Press, 1981. ISBN 0-306-40615-2.
• Lin, Shu, and Daniel J. Costello, Jr. "Error Control Coding: Fundamentals and Applications". Englewood Cliffs, N.J.: Prentice-Hall, 1983. ISBN 0-13-283796-X.
• Mackenzie, Dana. "Communication speed nears terminal velocity". New Scientist 187.2507 (9 July 2005): 38–41. ISSN 0262-4079.
• Wicker, Stephen B. Error Control Systems for Digital Communication and Storage. Englewood Cliffs, N.J.: Prentice-Hall, 1995. ISBN 0-13-200809-2.
• Wilson, Stephen G. Digital Modulation and Coding, Englewood Cliffs, N.J.: Prentice-Hall, 1996. ISBN 0-13-210071-1.
• "Error Correction Code in Single Level Cell NAND Flash memories" 16/02/2007
• United States Patent 6041001 "Method of increasing data reliability of a flash memory device without compromising compatibility"
• United States Patent 7187583 "Method for reducing data error when flash memory storage device using copy back command"

外部リンク

• “Forward Error-Correction Coding”. Crosslink - The Aerospace Corporation magazine of advances in aerospace technology. The Aerospace Corporation (Volume 3, Number 1 (Winter 2001/2002)). 2006年3月5日閲覧。
• “How Forward Error-Correcting Codes Work”. Crosslink - The Aerospace Corporation magazine of advances in aerospace technology. The Aerospace Corporation. 2006年3月5日閲覧。
• Morelos-Zaragoza, Robert (2004年). “The Error Correcting Codes (ECC) Page”. 2006年3月5日閲覧。