ビタビアルゴリズムと誤り検出訂正

ショートカット: 違い、類似点、ジャカード類似性係数、参考文献。

ビタビアルゴリズムと誤り検出訂正の違い

ビタビアルゴリズム vs. 誤り検出訂正

ビタビアルゴリズム（Viterbi algorithm）は、観測された事象系列を結果として生じる隠された状態の最も尤もらしい並び（ビタビ経路と呼ぶ）を探す動的計画法アルゴリズムの一種であり、特に隠れマルコフモデルに基づいている。観測された事象系列の確率計算のアルゴリズムである 前向きアルゴリズム（forward algorithm）も密接に関連している。これらのアルゴリズムは情報理論の一部である。 このアルゴリズムには、いくつかの前提条件がある。まず、観測された事象と隠されている事象は1つの系列上に並んでいる。この系列は多くの場合時系列である。次に、これら2つの並びには一対一の対応があり、1つの観測された事象は正確に1つの隠されている事象に対応している。第三に、時点 t での最も尤もらしい隠されている事象の計算は、t での観測された事象と t − 1 での最も尤もらしい隠された事象の系列のみに依存している。これらの前提条件は、全て一次隠れマルコフモデルで満たされている。 「ビタビ経路; Viterbi path」および「ビタビアルゴリズム」という用語は、観測結果について1つの最も尤もらしい説明を与える動的計画法のアルゴリズムに関して使われる。例えば、動的計画法のアルゴリズムを使った統計的構文解析は、文字列について1つの最も尤もらしい解析結果を生じる。そのため、これを「ビタビ構文解析; Viterbi parse」と呼ぶこともある。 ビタビアルゴリズムは、アンドリュー・ビタビがノイズのあるデジタル通信経路における誤り検出訂正手法として生み出したものである。CDMAやGSMといったデジタル携帯電話、ダイヤルアップ接続用モデム、通信衛星、宇宙探査での通信、IEEE 802.11 無線LAN などの畳み込み符号の復号に広く利用されている。また、音声認識、自然言語処理、計算言語学、バイオインフォマティクスなどにも使われている。例えば、音声認識では、音声信号を観測された事象の系列として扱い、それを文字に変換したものがその音声信号に対応した「隠された原因」と見なされる。ビタビアルゴリズムは、与えられた音声信号から最も尤もらしい文字列を見つけ出す。. 誤り検出訂正（あやまりけんしゅつていせい）またはエラー検出訂正 (error detection and correction/error check and correct) とは、データに符号誤り（エラー）が発生した場合にそれを検出、あるいは検出し訂正（前方誤り訂正）することである。検出だけをする誤り検出またはエラー検出と、検出し訂正する誤り訂正またはエラー訂正を区別することもある。また改竄検出を含める場合も含めない場合もある。誤り検出訂正により、記憶装置やデジタル通信・信号処理の信頼性が確保されている。.

前方誤り訂正

前方誤り訂正（ぜんぽうあやまりていせい、Forward Error Correction, FEC）は、データ転送における誤り制御システムの一種。メッセージ送信者がメッセージに冗長性を付与することで、追加情報を送信者に要求することなく、受信者が誤りを（ある時間以内に）検出し訂正することを可能にする。一方向誤り訂正とも。前方誤り訂正の利点は、データの再送を防ぐことで高スループットを平均的に達成する点である。このため、再送がコスト高になる場合や不可能な場合に適用される。 FEC機器はアナログ信号の受信機に近い位置に設置され、受信側のデジタル信号処理の最初の段階で行われる。つまり、FEC回路はアナログ-デジタル変換回路の一部として組み込まれていることが多い。FEC符号器の多くはビットエラーレート信号も生成でき、アナログ受信電子回路のチューニングのためのフィードバックとして使われる。ビタビアルゴリズムなどのFECアルゴリズムの多くは、入力として（擬似）アナログデータをとり、出力としてデジタルデータを生成する。 訂正可能な誤りの程度は、符号の設計段階で決定される。そのため、個々の前方誤り訂正符号にはそれぞれに適した利用条件がある。.

ビタビアルゴリズムと前方誤り訂正 · 前方誤り訂正と誤り検出訂正 · 続きを見る »

畳み込み符号

畳み込み符号（たたみこみふごう、Convolutional code）は、電気通信における誤り訂正符号の一種である。m-ビットの情報シンボル（すなわち m-ビット文字列）が符号化によって n-ビットシンボルに変換され、このとき m/n を符号レートと呼ぶ（n ≥ m）。また、その変換は最近の k 個の情報シンボルに関する関数となっており、k をその符号の拘束長（constraint length）と呼ぶ。.

ビタビアルゴリズムと畳み込み符号 · 畳み込み符号と誤り検出訂正 · 続きを見る »