畳み込み符号

畳み込み符号の概要

畳み込み符号（Convolutional code）は、通信技術において誤り訂正を行う手法です。この技術は1955年にマサチューセッツ工科大学のピーター・イライアスによって提案されました。主に、入力されたビット列から新しいビット列を順次生成する方式で符号化が行われ、信号の誤りを検知・訂正することを可能にしています。これはブロック符号とは異なる特徴を持っています。

符号化の基本概念

畳み込み符号化の基本的な操作には、入力ビットを記憶するメモリレジスタと生成多項式が使われます。仮に、1ビットの入力を3ビットに変換する簡単な符号器を考えてみましょう。この符号器は、3ビットの直近の入力を一時的に保持し、それを基に新しい出力ビットを生成します。この際、以下の用語が使用されます。

• - 符号化率 (r)：入力ビットと出力ビットの比率を示します。例えば、入力が1ビットで出力が3ビットの場合、符号化率は1/3となります。
• - 拘束長 (k)：演算において使用する直近の入力ビットの長さを指します。
• - 自由距離 (d)：符号の訂正能力を表す指標です。

この例では、符号化率が1/3、拘束長が3となります。符号器は、この拘束長に応じて、複数のメモリレジスタを持ち、これらのレジスタの値を基に計算を行います。

符号器の動作と再帰的実装

この処理では、まず最初の入力ビットがメモリの左端に格納され、各メモリレジスタからの信号に生成多項式を適用して出力が得られます。出力が作成された後、全てのレジスタは右にシフトされ次の入力を待つという動作を繰り返します。このプロセスを続け、全てのレジスタがゼロになるまで出力を行います。

再帰的な実装は非再帰的なものとは異なる構造を持ち、特定の符号は「組織的」または「非組織的」として分類されます。再帰的符号の場合、組織的であり、出力が入力に直結します。

数学的な表現とトレリス図

畳み込み符号化は、入力ビットと符号器のインパルス応答との畳み込みに基づいて実行されます。出力は、入力列を加工した結果として得られ、トレリス図を用いて可視化されることが一般的です。トレリス図は、状態遷移を視覚的に表現する方法であり、符号器が取りうる全ての状態や経路を示します。

自由距離とエラー訂正能力

自由距離は、任意の異なる符号化列のビット差分の最小数量を示します。この値は、符号化されたデータが誤りを許容できる長さを示し、設計における重要な指標です。

畳み込み符号が持つ訂正能力は、自由距離を用いて計算され、許容される誤りの数は次のように求められます：

$$t = ⌊(d - 1)/2⌋$$

ここで、tは訂正可能な誤りの数を示します。

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

パンクチャリング（puncturing）技術を用いれば、符号化率を変更しながらも誤り訂正性能を保持することが可能です。特定のビットを削除することで生成された符号が、通信の効率を向上させるために使われることが多く、例えば、デジタルラジオや携帯電話、衛星通信などに広く用いられています。

実用例と現状

畳み込み符号は、現代の通信技術において非常に重要な役割を果たしています。NASAの宇宙探査ミッションや携帯電話通信において、この技術は多くの実用例があります。例えば、ビタビ法は、計算効率の良さから多くのデジタル通信システムで採用されています。今後も、さらなる進化が期待される技術です。

もう一度検索