畳み込み符号とは? わかりやすく解説

畳み込み符号

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/01/12 10:06 UTC 版)

ナビゲーションに移動 検索に移動

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

畳み込み符号が使われる場面

畳み込み符号は、デジタルラジオ携帯電話人工衛星リンク、Bluetooth などの実装について、性能を向上させるためによく使われる。

畳み込み符号化

図1. レート 1/3、拘束長 3 の非再帰的非系統的畳み込みエンコーダ

データを畳み込み符号化するには、それぞれが 1 入力ビットを保持する k 個のメモリレジスタを用意する。特に指定されない限り、各メモリレジスタの初期値は 0 である。エンコーダには、n 個の 2 を法とする加算器n 個の生成多項式があり、1つの生成多項式が1つの加算器に対応している。入力ビット m1 は左端のレジスタに格納される。そして、各メモリレジスタの値に対して生成多項式を適用して n ビットの出力をする。次に、全レジスタ値を右方向にビットシフトし(m1m0 に移し、m0m-1 に移す)、次の入力ビットを待つ。新たな入力ビットがない場合、エンコーダは全てのレジスタがゼロ状態になるまで出力を続ける。

右図はレート 1/3 (m/n) で拘束長 (k) が 3 のエンコーダを示している。生成多項式は、G1 = (1,1,1)、G2 = (0,1,1)、G3 = (1,0,1) である。従って、出力ビットは次のように計算される(2 を法とする)。

  • n1 = m1 + m0 + m-1
  • n2 = m0 + m-1
  • n3 = m1 + m-1.

再帰的符号と非再帰的符号

図2. レート 1/2、拘束長 4 の再帰的系統的畳み込みエンコーダ

図1のエンコーダは「非再帰的」エンコーダである。図2に示したのは、再帰的な例である。

この図を見て判るとおり、「出力2」として符号化対象の入力がそのまま出力されている。このような符号は組織的(systematic)であるといい、そうでない符号を非組織的(non-systematic)であるという。

再帰的符号は常に系統的であり、逆に非再帰的符号は非系統的であることが多い。これは絶対条件ではないが、一般にそのようになっていることが多い。

インパルス応答、伝達関数、拘束長

畳み込みエンコーダが「畳み込み」と呼ばれるのは、入力ストリームに対してエンコーダの「インパルス応答」による「畳み込み」を行うからである。エンコーダのインパルス応答は次の式で表される。

  • 図3. 図1のエンコーダについてのトレリス図

全ての可能な遷移は右図で示される。

実際に符号化された列は、この図での経路で示される。妥当な経路は右図では赤で示されている。

この図は「復号」に関する考え方を与えてくれる。受信したビット列がこの図に適合しない場合、誤りがあることがわかり、最も近い「正しい」ビット列を選ばなくてはならない。実際の復号アルゴリズムもこの考え方を定式化したものである。

自由距離と誤り分散

自由距離(free distance、d)は、異なる符号化列の間の最小ハミング距離である。畳み込み符号の訂正能力(correcting capability、t)とは、その符号によって訂正できる誤りの数である。訂正能力は次のように求められる。

畳み込み符号はブロックを使用せず、連続なビット列として処理するため、t の値は比較的互いに近い位置にある誤りに適用されるものである。すなわち、比較的遠い位置のビット列がそれぞれ t 個の誤りを含んでいても、問題なく訂正できる。

自由距離は、畳み込みデコーダの出力が連続的に誤りとなったときに許容できる最小の長さと解釈することもできる。畳み込み符号を使った連結符号を設計する際、誤りが連続して発生することを考慮する必要がある。この問題の一般的な解決策としては、インタリーバと呼ばれる機構で畳み込み符号化する前にデータをインターリーブしておき、外側のブロック符号リード・ソロモン符号など)がほとんどの誤りを正しく訂正できるようにする。

畳み込み符号の復号

畳み込み符号の復号にはいくつかのアルゴリズムがある。k が比較的小さい場合、最尤法に基づいた高度に並列化可能なビタビアルゴリズムがよく使われる。ビタビデコーダはVLSIにも実装が容易であり、CPU上でソフトウェアとして実行する場合もSIMD命令を使うのに適している。

拘束長が長い場合、逐次型の復号アルゴリズムがいくつか存在しており、ファーノ・アルゴリズムなどがよく知られている。ビタビ復号とは異なり、逐次復号は最尤法は用いないが、計算量は拘束長に対して若干増大するだけで、強力な長い拘束長の符号を利用可能とする。そのような符号は1970年代のパイオニア計画(木星および土星の探査)で使われたが、短いビタビ符号を大きなリード・ソロモン符号で連結した形であり、全体としてビットエラー率の曲線は急勾配となり、極めて低い誤り見逃し率を実現していた。

ビタビ復号アルゴリズムも逐次復号アルゴリズムも、根本は最もそれらしい符号語を探すものである。近似的な信頼度を各ビットに付与する方法として、軟出力ビタビアルゴリズムがある。各ビットについての最大事後確率(MAP)の軟判定は、BCJRアルゴリズムを使って実現される。

主な畳み込み符号

ビタビ復号による畳み込み符号の例としては、ボイジャー計画以来使われている、拘束長 k が 7、レート r が 1/2 の符号がある。

  • 拘束長が長ければ、それだけ符号としても強力になるが、ビタビアルゴリズムの計算量は拘束長に対して指数関数的に増大するため、宇宙探査ではデコーダの計算量と符号の性能のトレードオフで符号が設計されている。
  • マーズ・パスファインダーマーズ・エクスプロレーション・ローバーカッシーニでは、k が 15、レートが 1/16 の符号が使われている。これは従来の k が 7 の符号に比較して、符号の性能は 2 dB 向上しているが、デコーダの計算量は 256 倍となっている。

パンクチャド畳み込み符号

パンクチャリング(puncturing)とは、基本となる 1/2 レートの符号から m/n のレートの符号を作る技法である。これは、エンコーダの出力の一部ビットを削除することでなされる。削除されるビットは「パンクチャリング行列; puncturing matrix」によって決定される。次に示すパンクチャリング行列は最もよく使われているものである。なお、自由距離は、NASA で使われている k=7 の畳み込み符号の場合である。

符号レート パンクチャリング行列 自由距離
1/2
(No perf.)
1
1
10
2/3
10
11
6
3/4
101
110
5
5/6
10101
11010
4
7/8
1000101
1111010
3

例えば上の表にある行列を使って、レート 2/3 の符号を作る場合、第一出力の2つ目の出力ビットと第二出力の全ビットを出力とする。ビットの転送の順序は、それぞれの通信標準によって定義される。

パンクチャド畳み込み符号は通信衛星でよく使われており、例えば、インテルサットデジタルビデオブロードキャスティングで使われている。

パンクチャド畳み込み符号は「perforated; 穴あき」とも呼ばれる。

ターボ符号

単純なビタビ復号による畳み込み符号は、シャノン限界に迫る性能を発揮するターボ符号の要素として使われている。ターボ符号と同等の誤り訂正性能を畳み込み符号だけで実現しようとすると、デコーダの計算量が非常に大きくなる。ターボ符号は今のところリード・ソロモン符号を利用してはいない。

関連項目

外部リンク


畳み込み符号

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/05/07 06:08 UTC 版)

符号理論」の記事における「畳み込み符号」の解説

畳み込み符号は電話回線モデム(ITU-T V.32、V.17、V.34)や GSM 携帯電話さらには衛星通信軍事通信機器にも使われている。 ここでのアイデアは、入力となるメッセージ群のシンボル列の重み付き総和として各符号語シンボル作成するということである。これは線形時不変系において入力インパルス応答判っているときに出力求め畳み込み似ている。 従って、畳み込みエンコーダ出力一般に畳み込みエンコーダレジスタの状態に対す入力ビット畳み込みである。 基本的に畳み込み符号は同等なブロック符号上のノイズ耐性保証しないが、多く場合同程度ブロック符号よりも実装大幅に単純化される。エンコーダは大抵の場合、状態メモリフィードバック論理通常 XORゲート)を持つ単純な回路である。デコーダファームウェアソフトウェア実装される。 畳み込み符号のデコード最適なアルゴリズムとしてビタービ・アルゴリズムがある。その計算負荷を減らす単純化手法もあり、最も可能性の高い経路だけを探索する。これは最適ではないが、低ノイズ環境ではよい結果となることがわかっている。最近マイクロプロセッサでは、この縮小され探索アルゴリズム平均毎秒4,000符号語上のデコードが可能である。

※この「畳み込み符号」の解説は、「符号理論」の解説の一部です。
「畳み込み符号」を含む「符号理論」の記事については、「符号理論」の概要を参照ください。

ウィキペディア小見出し辞書の「畳み込み符号」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

カテゴリ一覧

すべての辞書の索引



Weblioのサービス

「畳み込み符号」の関連用語











畳み込み符号のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



畳み込み符号のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの畳み込み符号 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの符号理論 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS