エラー訂正コード

コンピューティング、電気通信、情報理論、および符号化理論において、前方誤り訂正（FEC）またはチャネル符号化^{[ 1 ]}は、信頼性の低いまたはノイズの多い通信チャネルを介したデータ伝送のエラーを制御するために使用される技術です。

中心となる考え方は、送信者がメッセージを冗長な方法でエンコードすることであり、多くの場合、誤り訂正符号（ECC）を使用します。^{[ 2 ]}^{[ 3 ]}この冗長性により、受信側はメッセージのどこかで発生する可能性のあるエラーを検出できるだけでなく、多くの場合、限られた数のエラーを訂正できます。したがって、再送信を要求するための逆方向チャネルは必要ない場合があります。コストは、固定された、より高い順方向チャネル帯域幅です。

アメリカの数学者リチャード・ハミングは1940年代にこの分野を開拓し、1950年に最初の誤り訂正符号であるハミング(7,4)符号を発明した。^{[ 3 ]}

FECは、一方通行の通信リンクやマルチキャストで複数の受信者に送信する場合など、再送信がコストがかかる、または不可能な状況に適用できます。

遅延時間の長い接続にもメリットがあります。遠方の惑星を周回する衛星の場合、エラーによる再送信によって数時間の遅延が生じる可能性があります。FECはモデムや携帯電話ネットワークでも広く使用されています。

受信機におけるFEC処理は、デジタルビットストリームに適用することも、デジタル変調された搬送波の復調に適用することもできます。後者の場合、FECは受信機における初期のアナログ-デジタル変換の不可欠な部分です。ビタビ復号器は、ノイズによって劣化されたアナログ信号からデジタルデータを復調するために、ソフトデシジョンアルゴリズムを実装しています。多くのFEC復号器は、アナログ受信回路を微調整するためのフィードバックとして使用できるビット誤り率（BER）信号も生成できます。

FEC情報は、破損したデータの復旧を可能にするために、大容量記憶装置（磁気式、光式、ソリッドステート／フラッシュベース）に追加され、信頼性に関する特別な対策が必要なシステムではECC コンピュータメモリとして使用されます。

訂正可能なエラーまたは欠落ビットの最大割合は ECC の設計によって決まるため、異なる前方誤り訂正符号は異なる条件に適しています。一般に、より強力な符号は、利用可能な帯域幅を使用して送信する必要のある冗長性を増加させ、受信の実効信号対雑音比を向上させながら実効ビットレートを低下させます。クロード・シャノンの雑音チャネル符号化定理は、与えられた最大許容エラー確率に対して達成可能な最大通信帯域幅を計算するために使用できます。これにより、与えられた基本雑音レベルを持つチャネルの理論上の最大情報転送速度の境界が確立されます。ただし、証明は構成的ではないため、容量達成コードを構築する方法についての洞察は得られません。長年の研究の後、極性符号^[⁴^]のような高度な FEC システムは、無限長のフレームを仮定した場合のシャノンチャネル容量によって与えられる理論上の最大値 (シャノン限界) に非常に近いものとなっています。

方法

ECCは、アルゴリズムを用いて送信情報に冗長性を加えることで実現されます。冗長ビットは、元の情報ビットの複雑な関数となる場合があります。元の情報は、符号化された出力にそのまま現れる場合もあれば、現れない場合もあります。出力に未変更の入力が含まれるコードは体系的であり、含まれないコードは非体系的です。

ECCの簡単な例として、各データビットを3回送信する方法があり、これは（3,1）繰り返し符号として知られています。ノイズの多い通信チャネルでは、受信側で8種類の出力が見られる可能性があります。下の表を参照してください。

これにより、3つのサンプルのいずれかに誤りがあった場合、「多数決」または「民主的な投票」によって訂正することが可能になります。このECCの訂正能力は以下のとおりです。

最大で1ビットのトリプレットの誤り、または
トリプレットのうち最大2ビットが省略される（表には示されていないケース）。

実装が容易で広く使用されているものの、この三重冗長方式は比較的効率の悪いECCである。より優れたECC符号は、通常、過去に受信した数十ビット、あるいは数百ビットを調べて、現在受信している少数のビット（通常は2～8ビットのグループ）をどのように復号するかを決定する。

簡略化された形式主義

形式的には、誤り訂正符号は（単射）符号化関数によって与えられる。 $f:\Sigma ^{*}\hookrightarrow \Delta ^{*}$ 各単語に割り当てられる $\displaystyle u\in \Sigma ^{*}\;{\stackrel {\mathrm {def} }{=}}\;\textstyle \bigcup _{n\in \mathbb {N} }\Sigma ^{n}}$ 有限アルファベットの $\Sigma$ ユニークな言葉 $w\in \Delta ^{*}\;{\stackrel {\mathrm {def} }{=}}\;\textstyle \bigcup _{n\in \mathbb {N} }\Delta ^{n}$ （アルファベットからの文字の連結） $\Delta$ 。

最も一般的には、 $f$ は、次の意味で準同型である。 $x_{1}*x_{2}$ 連結 $x_{1}$ そして $x_{2}$ すると、次のようになります。 $f(u_{1}*u_{2})=f(u_{1})*f(u_{2})$ これは、定義するだけで十分であることを意味する $f(\sigma )$ 一文字の単語の場合 $\sigma$ 範囲 $\mathrm {Im} (f)$ 関数の $f$ これはコードワードの集合です。コードのエラー検出および訂正能力は、距離から理解することができます。 $d=\min _{w_{1},w_{2}\in \mathrm {Im} (f);\ w_{1}\neq w_{2}}d_{H}(w_{1},w_{2})$ コードの最小ハミング距離は、異なる2つのコードワードを隔てる最小ハミング距離です。 $d$ エラーを検出できます $k$ ビットの長さは $k<d$ 検出されたエラーのうち、コードは修正することができます $l$ -ビットエラーが発生するたびに $2l<d$ 。

ノイズを平均化して誤差を低減する

ECCは「ノイズを平均化する」ことで機能すると言えるでしょう。各データビットは多くの送信シンボルに影響を与えるため、ノイズによって一部のシンボルが破損しても、通常は同じユーザーデータに依存する他の破損していない受信シンボルから元のユーザーデータを抽出することができます。

この「リスク共有」効果により、ECCを使用するデジタル通信システムは、一定の最小信号対雑音比を上回るレベルでは良好に機能する傾向があり、それ以下のレベルでは全く機能しない。
この全か無かの傾向、つまり崖効果は、理論上のシャノン限界に近づくようなより強力な符号が使用されるにつれて、より顕著になる。
ECC符号化データをインターリーブすることで、チャネルエラーがバースト的に発生する場合に、送信されるECCコードのオール・オア・ナッシング特性を軽減できます。ただし、この方法には限界があり、狭帯域データでの使用が最適です。

ほとんどの通信システムは、想定される最悪のビット誤り率を許容するように設計された固定チャネルコードを使用しており、ビット誤り率がそれよりも悪くなると全く機能しなくなります。しかし、一部のシステムは、与えられたチャネルのエラー条件に適応します。ハイブリッド自動再送要求の一部のインスタンスでは、ECCがエラー率を処理できる限り固定ECC方式を使用し、エラー率が高すぎると ARQに切り替えます。適応変調符号化では、さまざまなECCレートを使用し、チャネルのエラー率が高い場合はパケットあたりのエラー訂正ビットを増やし、必要ない場合は削除します。

種類

ECC符号の主な種類は、ブロック符号と畳み込み符号の2つである。

ブロック符号は、あらかじめ決められたサイズのビットまたはシンボルからなる固定サイズのブロック（パケット）で動作します。実用的なブロック符号は、一般的に、そのブロック長に対して多項式時間でハードデコードできます。
畳み込み符号は、任意の長さのビット列またはシンボル列に対して機能します。多くの場合、ビタビアルゴリズムを使用してソフト復号されますが、他のアルゴリズムが使用されることもあります。ビタビ復号では、畳み込み符号の制約長が増加するにつれて漸近的に最適な復号効率が得られますが、その代償として複雑さが指数関数的に増加します。終端された畳み込み符号は、入力データのブロックを符号化するという点で「ブロック符号」でもありますが、畳み込み符号のブロックサイズは一般的に任意であるのに対し、ブロック符号は代数的特性によってサイズが固定されています。畳み込み符号の終端方式には、「テールバイティング」と「ビットフラッシング」があります。

古典的なブロックコードは通常、ハード決定アルゴリズムを使用して復号されます^{[ 5 ]。}これは、すべての入力信号と出力信号に対して、それが1ビットか0ビットかのハード決定が行われることを意味します。対照的に、畳み込みコードは通常、ビタビ、MAP、BCJRアルゴリズムなどのソフト決定アルゴリズムを使用して復号されます。これらのアルゴリズムは（離散化された）アナログ信号を処理し、ハード決定復号よりもはるかに高い誤り訂正性能を可能にします。

古典ブロック符号のほぼ全ては、有限体の代数的性質を利用している。そのため、古典ブロック符号はしばしば代数符号と呼ばれる。

ブロックコード

ブロック符号には多くの種類がありますが、リード・ソロモン符号はコンパクトディスク、DVD、ハードディスクドライブなどで広く用いられていることで知られています。その他の古典的なブロック符号の例としては、ゴレイ符号、BCH符号、多次元パリティ符号、ハミング符号などがあります。

ハミング ECC は、 ECC メモリや初期の SLC NAND フラッシュメモリのエラーを訂正するためによく使用されます。 ^{[ 6 ]} これは、1 ビットのエラー訂正と 2 ビットのエラー検出を提供します。ハミング符号は、より信頼性の高いシングルレベルセル(SLC) NAND にのみ適しています。高密度のマルチレベルセル(MLC) NAND では、 BCH、リード-ソロモン、またはLDPCなどのマルチビット訂正 ECC が使用される場合があります。^{[ 7 ]}^{[ 8 ]} NOR フラッシュは通常、エラー訂正を使用しません。^{[ 7 ]}

ソフトコード

低密度パリティ検査（LDPC）

Low-density parity-check (LDPC) codes are a class of highly efficient linear block codes made from many single parity check (SPC) codes. They can provide performance very close to the channel capacity (the theoretical maximum) using an iterated soft-decision decoding approach, at linear time complexity in terms of their block length. Practical implementations rely heavily on decoding the constituent SPC codes in parallel.

LDPC codes were first introduced by Robert G. Gallager in his PhD thesis in 1960, but due to the computational effort in implementing encoder and decoder and the introduction of Reed–Solomon codes, they were mostly ignored until the 1990s.

LDPC codes are now used in many recent high-speed communication standards, such as DVB-S2 (Digital Video Broadcasting – Satellite – Second Generation), WiMAX (IEEE 802.16e standard for microwave communications), High-Speed Wireless LAN (IEEE 802.11n),^[9]10GBase-T Ethernet (802.3an) and G.hn/G.9960 (ITU-T Standard for networking over power lines, phone lines and coaxial cable). Other LDPC codes are standardized for wireless communication standards within 3GPP MBMS (see fountain codes).

Turbo code

Turbo coding is an iterated soft-decoding scheme that combines two or more relatively simple convolutional codes and an interleaver to produce a block code that can perform to within a fraction of a decibel of the Shannon limit. Predating LDPC codes in terms of practical application, they now provide similar performance.

One of the earliest commercial applications of turbo coding was the CDMA2000 1x (TIA IS-2000) digital cellular technology developed by Qualcomm and sold by Verizon Wireless, Sprint, and other carriers. It is also used for the evolution of CDMA2000 1x specifically for Internet access, 1xEV-DO (TIA IS-856). Like 1x, EV-DO was developed by Qualcomm, and is sold by Verizon Wireless, Sprint, and other carriers (Verizon's marketing name for 1xEV-DO is Broadband Access, Sprint's consumer and business marketing names for 1xEV-DO are Power Vision and Mobile Broadband, respectively).

Describing the performance of an ECC

誤り検出機能や誤り訂正機能を規定することが多い従来のブロック符号とは対照的に、LDPC符号などの多くの現代的なブロック符号は、そのような保証を欠いている。その代わりに、現代の符号はビット誤り率によって評価される。

ほとんどの前方誤り訂正符号はビット反転のみを訂正し、ビット挿入やビット削除は訂正しません。この場合、ハミング距離がビット誤り率を測定する適切な方法です。マーカー符号やウォーターマーク符号など、ビット挿入とビット削除の両方を訂正するように設計された前方誤り訂正符号もいくつかあります。このような符号を使用する場合、レーベンシュタイン距離がビット誤り率を測定するより適切な方法です。 ^{[ 10 ]}

コードレートと信頼性とデータレートのトレードオフ

ECCの基本原理は、冗長ビットを追加することで、デコーダが送信機によって符号化された真のメッセージを見つけやすくすることです。特定のECCシステムの符号化率は、通信パケット内の情報ビット数と総ビット数（情報ビットと冗長ビットの合計）の比として定義されます。したがって、符号化率は実数です。ゼロに近い低い符号化率は、多くの冗長ビットを使用して優れた性能を実現する強力な符号を意味し、1に近い高い符号化率は、弱い符号を意味します。

情報を保護する冗長ビットは、保護しようとしている通信リソースと同じものを使用して転送する必要があります。これにより、信頼性とデータレートの間に根本的なトレードオフが生じます。^{[ 11 ]}一方で、強力なコード（低コードレート）は、実効データレートの低下を犠牲にして、受信機のSNR（信号対雑音比）を大幅に向上させ、ビット誤り率を低下させることができます。もう一方では、ECCを使用しない（つまり、コードレートが1に等しい）と、ビットに追加の保護が一切施されないという代償を伴い、チャネル全体を情報転送に使用します。

興味深い疑問の 1 つは、復号エラー率が無視できる ECC は情報転送の観点からどの程度効率的になり得るか、という点です。この疑問は、クロード・シャノンが第 2 定理で答えました。この定理は、チャネル容量はエラー率がゼロに近づく ECC で達成可能な最大ビットレートであると述べています。^{[ 12 ]}彼の証明はガウスランダムコーディングに依存していますが、これは実際のアプリケーションには適していません。シャノンの研究によって与えられた上限は、究極のパフォーマンス限界に近づくことができる ECC を設計する長い道のりを促しました。今日ではさまざまなコードがほぼシャノン限界を達成できます。しかし、容量を達成する ECC は通常、実装が非常に複雑です。

最も一般的な ECC は、パフォーマンスと計算複雑性の間にトレードオフがあります。通常、そのパラメータは可能なコードレートの範囲を示し、シナリオに応じて最適化できます。通常、この最適化は、データレートへの影響を最小限に抑えながら、低い復号エラー確率を達成するために行われます。コードレートを最適化するもう 1 つの基準は、通信のエネルギーコストに合わせて、低いエラー率と再送信数のバランスを取ることです。^{[ 13 ]}

コードのローカル復号とテスト

メッセージのビット単位だけを復号したり、与えられた信号が符号語であるかどうかをチェックしたりするだけで済む場合があり、その際に信号全体を調べる必要はありません。これは、符号語が大きすぎて従来の方法では十分な速度で復号できず、現時点ではメッセージのごく一部のビットだけが関心事となるストリーミング環境では特に有効です。また、このような符号は、例えば確率的に検証可能な証明の設計など、計算複雑性理論における重要なツールとなっています。

局所復号可能符号とは、符号語の一定割合の位置が破損した後でも、符号語のごく少数（例えば定数）の位置を調べるだけで、メッセージの単一ビットを確率的に復元できる誤り訂正符号のことである。局所テスト可能符号とは、信号のごく少数の位置を調べるだけで、信号が符号語に近いかどうかを確率的に判定できる誤り訂正符号のことである。

すべての局所復号可能コード（LDC）が局所テスト可能コード（LTC）であるとは限りません^{[ 14 ]。}また、局所訂正可能コード（LCC）でもありません^{[ 15 ]} 。qクエリLCCは指数関数的に制限されます^{[ 16 ]}が、LDCは準指数関数的な長さを持つことができます^{[ 17 ] 。}

パフォーマンスの向上

連結（組み合わせ）

古典的な（代数的な）ブロック符号と畳み込み符号は、連結符号化方式で頻繁に組み合わされます。この方式では、制約長が短いビタビ復号された畳み込み符号がほとんどの処理を行い、シンボルサイズとブロック長が大きいブロック符号（通常はリード・ソロモン符号）が畳み込み復号器で発生した誤りを「回収」します。この誤り訂正符号群を用いたシングルパス復号では非常に低い誤り率が得られますが、長距離伝送条件（深宇宙など）では反復復号が推奨されます。

連結符号は、ボイジャー2号が1986年の天王星接近時に初めてこの技術を使用して以来、衛星通信や深宇宙通信における標準的な手法となっている。ガリレオ探査機は、アンテナの故障によって生じる非常に高いエラー率を補償するために、反復連結符号を使用した。

インターリーブ

インターリーブは、前方誤り訂正符号の性能を向上させるために、デジタル通信およびストレージシステムで頻繁に使用されます。多くの通信チャネルはメモリレスではなく、エラーは通常、独立してではなくバースト的に発生します。コードワード内のエラー数が誤り訂正符号の能力を超えると、元のコードワードを復元できなくなります。インターリーブは、ソースシンボルを複数のコードワードにシャッフルすることでこの問題を軽減し、エラーの分布をより均一にします。 ^{[ 18 ]}したがって、インターリーブはバースト誤り訂正に広く使用されています。

ターボ符号やLDPC符号などの最新の反復符号の解析では、通常、エラーの分布が独立であると仮定されます。^{[ 19 ]}そのため、LDPC符号を使用するシステムでは、通常、符号語内のシンボル間で追加のインターリーブが採用されます。^{[ 20 ]}

ターボ符号の場合、インターリーバは不可欠なコンポーネントであり、その適切な設計は良好なパフォーマンスにとって重要です。^{[ 18 ]}^{[ 21 ]}反復復号アルゴリズムは、復号器を表す因子グラフに短いサイクルがない場合に最もよく機能します。インターリーバは短いサイクルを回避するように選択されます。

インターリーバの設計には以下が含まれます。

矩形（または均一）インターリーバ（上記で説明したスキップ係数を使用する方法と同様）
畳み込みインターリーバ
ランダムインターリーバー（インターリーバーは既知のランダム順列）
Sランダムインターリーバ（インターリーバは既知のランダム順列であり、入力シンボルが距離S以内にある場合、出力シンボルも距離S以内に現れないという制約がある）。^{[ 22 ]}
競合のない二次順列多項式（QPP）。^{[ 23 ]}使用例としては、3GPP Long Term Evolution移動体通信規格がある。^{[ 24 ]}

マルチキャリア通信システムでは、周波数ダイバーシティを実現するためにキャリア間のインターリーブが用いられることがあり、例えば周波数選択性フェージングや狭帯域干渉を軽減するために使用される。^{[ 25 ]}

インターリーブの例

インターリーブなしの伝送：

エラーのないメッセージ: aaaabbbbccccddddeeeeffffgggg バーストエラーのある送信: aaaabbbbccc____deeeeffffgggg

ここでは、同じ文字の各グループが、4ビットの1ビット誤り訂正符号語を表します。符号語ccccは1ビットだけ変更されているため訂正可能ですが、符号語ddddは3ビットだけ変更されているため、全く復号できないか、誤って復号される可能性があります。

インターリーブ方式の場合：

エラーのないコードワード: aaaabbbbccccddddeeeeffffgggg インターリーブ: abcdefgabcdefgabcdefgabcdefg バーストエラーのある送信: abcdefgabcd____bcdefgabcdefg デインターリーブ後の受信コードワード: aa_abbbbccccdddde_eef_ffg_gg

「 aaaa」、「eeee」、「ffff」、「gggg 」の各符号語では、1ビットだけが変更されるため、1ビットの誤り訂正符号ですべて正しく復号できます。

インターリーブなしの伝送：

元の送信文: ThisIsAnExampleOfInterleaving バーストエラーで受信した文: ThisIs______pleOfInterleaving

「 AnExample 」という用語は、ほとんどの場合意味不明で、修正も困難です。

インターリーブ方式の場合：

送信された文: ThisIsAnExampleOfInterleaving... エラーのない送信: TIEpfeaghsxlIrv.iAaenli.snmOten. バーストエラーのある受信文: TIEpfe______Irv.iAaenli.snmOten. デインターリーブ後の受信文: T_isI_AnE_amp_eOfInterle_vin_...

完全に失われる単語はなく、欠落した文字も最小限の推測で復元できる。

インターリーブのデメリット

インターリーブ技術を使用すると、全体の遅延が増加します。これは、パケットを復号する前に、インターリーブされたブロック全体を受信する必要があるためです。^{[ 26 ]}また、インターリーバはエラーの構造を隠蔽します。インターリーバがない場合、より高度な復号アルゴリズムはエラー構造を利用して、インターリーバと組み合わせた単純なデコーダよりも信頼性の高い通信を実現できます。このようなアルゴリズムの例は、ニューラルネットワーク^[²⁷^]構造に基づいています。