Viterbi Decoder
ビタビ アルゴリズムを使用した畳み込み符号化されたデータの復号化
ライブラリ
Error Detection and Correction の Convolutional サブライブラリ
説明
Viterbi Decoder ブロックは、入力信号を復号化して、バイナリの出力シンボルを生成します。このブロックは、高速パフォーマンスを実現するために複数のシンボルを一度に処理できます。
このブロックは、シミュレーション中に長さが変わるシーケンスを出力することができます。長さがさまざまであるシーケンスや可変サイズ信号の詳細は、可変サイズの信号の基礎 (Simulink)を参照してください。
入力および出力サイズ
畳み込み符号が 2n シンボル候補のアルファベットを使用した場合、このブロックの入力ベクトル長はある正の整数 L に対して L*n になります。同様に、復号化されたデータが 2k 出力シンボル候補のアルファベットを使用する場合、このブロックの出力ベクトル長は L*k になります。
このブロックは、L の正の整数値のある列ベクトル入力信号を受け入れます。可変サイズの入力の場合、L はシミュレーション中に変化する可能性があります。ブロックの処理は、処理モード パラメーターによって管理されます。
各ブロックの端子でサポートされるデータ型については、このページのサポートされているデータ型の表を参照してください。
入力値と判別タイプ
入力ベクトルのエントリは、[Decision type] パラメーターによって、バイポーラ、バイナリ、整数データのいずれかになります。
判別タイプ パラメーター | 復号化器入力の可能なエントリ | 値の解釈 | 分岐メトリクス計算 |
---|---|---|---|
| 実数 | 正の実数: 論理 0 負の実数: 論理 1 | Euclidean 距離 |
| 0, 1 | 0: 論理 0 1: 論理 1 | ハミング距離 |
| 0 から 2b-1 までの整数。ここで、b は [Number of soft decision bits] パラメーターです。 | 0: 論理 0 に対する最も信頼性の高い判定 2b-1: 論理 1 に対する最も信頼性の高い判定 その他の値は、比較的信頼性の低い判定を表します。 | ハミング距離 |
軟判定状況をより明確にするために、次の表は 3 ビット軟判定に対する値の解釈を示しています。
入力値 | 解釈 |
---|---|
0 | 最も信頼性の高い 0 |
1 | 2 番目に信頼性の高い 0 |
2 | 3 番目に信頼性の高い 0 |
3 | 最も信頼性の低い 0 |
4 | 最も信頼性の低い 1 |
5 | 3 番目に信頼性の高い 1 |
6 | 2 番目に信頼性の高い 1 |
7 | 最も信頼性の高い 1 |
入力用の操作モード
Viterbi decoder ブロックには、連続入力フレーム間の遷移のために 3 種類の可能な方法があります。[Operation mode] パラメーターは、ブロックがどの方法を使用するかを制御します。
[Continuous]
モードでは、ブロックは次のフレームで使用するために、各入力の最後で内部状態メトリクスを保存します。各トレースバック パスは、独立して扱われます。[Truncated]
モードでは、ブロックは各入力を個別に扱います。トレースバック パスは最良のメトリクスで始まり、常にすべて 0 の状態で終了します。このモードは、対応する Convolutional Encoder ブロックがその [Operation mode] を[Truncated (reset every frame)]
に設定するときに適切です。[Terminated]
モードでは、ブロックは各入力を個別に扱い、トレースバック パスはすべて 0 の状態で開始し、終了します。このモードは、コード化されていないメッセージ信号 (つまり、対応する Convolutional Encoder ブロックへの入力) が各入力の末尾に、フィードフォワード符号化器のすべてのメモリ レジスタを埋めるのに充分な 0 がある場合に適しています。符号化器にk
入力ストリームと拘束長ベクトルconstr
(多項式表現を使用) がある場合、"充分" な 0 とはk*max(constr-1)
を意味します。フィードバック符号化器の場合、このモードは、対応する Convolutional Encoder ブロックで [Operation mode] がTerminate trellis by appending bits
に設定されている場合には適しています。
メモ
このブロックがシミュレーション中に長さが異なるシーケンスを出力し、[Operation mode] を [Truncated]
または [Terminated]
に設定すると、ブロックの状態がすべての入力タイム ステップでリセットします。
入力信号に 1 つのシンボルだけが含まれているときは [Continuous]
モードを使用します。
リセット端子
リセット端子は、[Operation mode] パラメーターが [Continuous]
に設定されているときにだけ使用できます。[Enable reset input port] を選択すると、Rst
とラベル付けされた追加の入力端子がブロックに提供されます。Rst
入力が非ゼロであると、復号化器は、内部メモリを次のように設定することで初期状態に戻ります。
すべて 0 状態メトリクスを 0 に設定する
他のすべての状態メトリクスを最大値に設定する
トレースバック メモリを 0 に設定する
このブロックにリセット端子を使用することは、Convolutional Encoder ブロックで [Operation mode] を [Reset on nonzero input via port]
に設定することと同じです。
リセット端子は double
または boolean
型の信号をサポートしています。
固定小数点信号の流れ図
ビタビ復号化アルゴリズムには 3 つの主なコンポーネントがあります。それらは、分岐メトリクス計算 (BMC)、追加比較と選択 (ACS)、およびトレースバック復号化 (TBD) です。次の図は、符号化率 k/n の符号の信号の流れを示しています。
BMC 図の例として、1/2 レートで、nsdec = 3 の信号の流れは次のようになります。
ACS コンポーネントは、通常は次の図のように示されます。
ここで、WL2
はユーザーによってマスクに指定されます。
前述の流れ図では、inNT、bMetNT、stMetNT、および outNT は numerictype
(Fixed-Point Designer) オブジェクトであり、bMetFIMATH と stMetFIMATH は fimath (Fixed-Point Designer)
オブジェクトです。
パンクチャ パターンの例
特定のレートや多項式で一般的に使用するパンクチャ パターンについては、最後の 3 つのリファレンスを参照してください。
固定小数点ビタビ復号化の例
固定小数点の硬判定ビタビ復号化の実行と固定小数点の軟判定ビタビ復号化の実行の例は、硬判定と軟判定の畳み込み復号化の固定小数点処理を使用するように Viterbi Decoder ブロックを設定します。
この例では、ビタビ復号化器の固定長小数点モデリング属性を類似のレイアウトを使用して強調表示します。
シミュレーションの概要
2 つのシミュレーションには、類似の構造があり、ほとんどのパラメーターは共通しています。データ ソースは、畳み込みで符号化され、BPSK で変調され、AWGN チャネルを通過した 2 進の乱数シーケンスを生成します。
畳み込み符号化器は、符号化率 1/2 の符号化器として構成されます。この符号化器は、2 ビットごとに別の 2 つの冗長ビットを追加します。これに適合させ、正確な量のノイズを追加するため、AWGN ブロックのパラメーター [Eb/No (dB)] は 10*log10(2) を差し引くことにより実質半分にされます。
硬判定の場合、BPSK 復調器は、復号化器に渡される硬判定を受信側で生成します。
軟判定の場合、BPSK 復調器は、対数尤度比を使用して軟判定を受信側で生成します。これらの軟出力は、3 ビットで量子化され、復号化器に渡されます。
復号化後に、シミュレーションは受信して復号化したシンボルと元の送信シンボルを比較して、ビット誤り率を計算します。シミュレーションは、100 個のビット誤りまたは 1e6 ビットを処理した後、どちらか先に発生したものの後で終了します。
固定小数点モデリング
固定小数点モデリングは、ハードウェア実装の検討とデータ/パラメーターの動的な範囲を考慮に入れた bit-true シミュレーションを有効にします。たとえば、対象のハードウェアが DSP マイクロプロセッサである場合、可能性のある語長は 8、16、または 32 ビットであり、ターゲット ハードウェアが ASIC または FPGA の場合は語長の選択に柔軟性があります。
固定長小数点ビタビ復号化を有効にするには、ブロック入力が硬判定のためにタイプ ufix1 (語長 1 の符号なし整数) でなければなりません。この入力 ( a 0 または a 1 のいずれか) に基づき、内部分岐メトリクスは、トレリス構造体に指定された (硬判定例の場合は 2 に等しい) ように、語長の符号なし整数 = (出力ビットの数) を使用して計算されます。
軟判定の場合、ブロック入力はタイプ ufixN (語長 N の符号なし整数) でなければなりません。ここで、N は固定長小数点の復号化を有効にするための軟判定ビットの数です。ブロック入力は、範囲を 0 から 2N-1 までにしなければなりません。内部分岐メトリクスは、トレリス構造体に指定された (軟判定例の場合は 4 に等しい) ように、語長の符号なし整数 = (N + 出力ビットの数 - 1) を使用して計算されます。
[State metric word length] は、ユーザーによって指定され、通常は既に計算されている分岐メトリクス語長よりも長くなければなりません。これは、システム用に記録されたデータを確認することによって、最も適した値に (ハードウェアやデータの検討に基づいて) 調整することができます。
ログを有効にするため、[アプリ]、[固定小数点ツール] を選択します。[固定小数点設定] GUI で、[固定小数点の計測モード] を [Minimums, maximums and overflows
] に設定し、シミュレーションを再実行します。オーバーフローが確認できた場合は、データが選択したコンテナーに収まらなかったことを示しています。(ハードウェアで許可されているのであれば) 語長のサイズを増やすか、データを処理する前にデータのスケーリングを行ってください。データの最小値と最大値に基づいて、選択したコンテナーが適切なサイズであるかどうかを判断することもできます。
[State metric word length] のさまざまな値でシミュレーションを実行して、その値のアルゴリズムへの影響を理解します。BER の結果に悪影響を及ぼさない適切な値になるようにパラメーターを絞り込むこともできます。
倍精度データとの比較
倍精度データで同じモデルを実行するには、[アプリ]、[固定小数点ツール] を選択します。[固定小数点ツール] GUI で、[データ型オーバーライド] に [Double
] を選択します。この選択によって、すべてのブロックのすべてのデータ型設定がオーバーライドされて倍精度を使用します。Viterbi Decoder ブロックには、[Output type] が [Boolean
] に設定されていたため、このパラメーターも double に設定しなければなりません。
モデルのシミュレーション時に、倍精度と固定小数点の BER の結果が同じであることに注意してください。同じである理由は、モデルの固定小数点パラメーターが、精度の低下を避けるために選択されており、これが引き続き最も効率的であるためです。
硬判定と軟判定の復号化の比較
2 つのモデルは BERTool の中から実行するように設定されて、硬判定と軟判定の復号化の BER パフォーマンスを比較するシミュレーション曲線を生成します。
固定小数点の硬判定ビタビ復号化の実行用のシミュレーション結果を生成するには、次の手順に従います。
固定小数点の硬判定ビタビ復号化の実行の例を開いてパス上の Simulink モデルを取得します。
MATLAB コマンド プロンプトで
bertool
と入力します。[Monte Carlo] ペインに移動します。
[Eb/No range] を
2:5
に設定します。[Simulation model] を
cm_viterbi_harddec_fixpt
に設定します。モデルがパス上にあることを確認します。[BER variable name] を
BER
に設定します。[Number of errors] を
100
に、[Number of bits] を1e6
に設定します。[実行] を押すと、プロットが生成されます。
固定小数点の軟判定ビタビ復号化の実行のシミュレーション結果を生成するには、例を開いてパス上の simulink モデルを取得し、[Simulation model] を cm_viterbi_softdec_fixpt
に変更して、[実行] を押します。
予想できるように、3 ビットの軟判定復号化は、硬判定復号化よりも良好であり、ほぼ 1.7 dB の調整ができ、一般に指摘されるように 2 dB ではありません。予想結果との違いは、復調器からの軟出力の不完全な量子化のためである可能性があります。
パラメーター
- Trellis structure
畳み込み符号化器のトレリス表現を含む MATLAB® 構造体。ここと対応する Convolutional Encoder ブロックで同じ値を使用します。
- Punctured code
このチェック ボックスをオンにして、パンクチャした入力コードを指定します。フィールド [Punctured code] が表示されます。
- Puncture vector
送信側 (符号化器) で使用される定数パンクチャ パターン ベクトル。パンクチャ ベクトルは
1
および0
のパターンです。0
はパンクチャド ビットを示します。[Punctured code] を選択すると、[Punctured vector] フィールドが表示されます。- Enable erasures input port
このボックスをオンにすると、復号化器が
Era
というラベルの入力端子を開きます。この端子から1
と0
の消去ベクトル パターンを指定できます。ここで、1
は消去されたビットを示します。受信するデータ ストリームでこれらを消去する場合、復号化器は分岐メトリクスを更新しません。消去および入力のデータ端子の幅とサンプル時間は、同じでなければなりません。消去入力端子は、データ型を
double
またはBoolean
にできます。- Decision type
分岐メトリクス計算の
[Unquantized]
、[Hard-decision]
、または[Soft Decision]
の使用を指定します。[Unquantized]
判定は、ユークリッド距離を使用して分岐メトリクスを計算します。[Soft Decision]
と[Hard-decision]
は、ハミング距離を使用して分岐メトリクスを計算します。このとき、[Number of soft decision bits] は1
です。
- Number of soft decision bits
各入力を表す軟判定ビットの数。このフィールドは、[Decision type] が
[Soft Decision]
に設定されている場合のみ表示されます。- Error if quantized input values are out of range
このチェック ボックスをオンにすると、量子化入力値が範囲外のときにエラーが報告されます。このチェック ボックスは、[Decision type] が
[Soft Decision]
または[Hard-decision]
に設定されている場合のみ表示されます。- Traceback depth
各トレースバック パスを構築するトレリス分岐の数。
- Operation mode
連続する入力フレーム間を遷移するための方法で、
[Continuous]
、[Terminated]
、および[Truncated]
があります。メモ
このブロックがシミュレーション中に長さが異なるシーケンスを出力し、[Operation mode] を
[Truncated]
または[Terminated]
に設定すると、ブロックの状態がすべての入力タイム ステップでリセットします。- Enable reset input port
このボックスをオンにすると、復号化器が
Rst
というラベルの入力端子を開きます。この端子にゼロ以外の入力値を提供することによって、ブロックはその内部メモリを、入力データを処理する前の初期状態に設定します。- Delay reset action to next time step
このオプションを選択すると、Viterbi Decoder ブロックは、符号化されたデータを復号化した後でリセットします。このオプションは、[Operation mode] を
[Continuous]
に設定し、[Enable reset input port] を選択したときにだけ利用可能です。このオプションは HDL サポートのために有効にしなければなりません。
- Output data type
出力信号のデータ型は、
double
、single
、boolean
、int8
、uint8
、int16
、uint16
、int32
、uint32
にでき、また、'Inherit via internal rule'
または'Smallest unsigned integer'
に設定できます。'Smallest unsigned integer'
に設定されると、出力データ型は、モデルの [コンフィギュレーション パラメーター] ダイアログ ボックスの [ハードウェア実行] ペインで使用されている設定に基づいて選択されます。ASIC/FPGA
が [ハードウェア実行] ペインで選択されると、出力データ型はufix(1)
になります。他のすべての選択の場合は、char 値に対応する指定された最も小さな語長 (uint8
) の符号なし整数です。'Inherit via internal rule'
(既定の設定) に設定されると、ブロックは double 入力に対しては double 型の出力を選択し、single 入力に対しては single 型の出力を選択肢、他のすべての型の入力に対しては'Smallest unsigned integer'
オプションと同様に動作します。
サポートされているデータ型
端子 | サポートされているデータ型 |
---|---|
入力 |
|
出力 |
|
参考文献
[1] Clark, George C., and J. Bibb Cain. Error-Correction Coding for Digital Communications. Applications of Communications Theory. New York: Plenum Press, 1981.
[2] Gitlin, Richard D., Jeremiah F. Hayes, and Stephen B. Weinstein. Data Communications Principles. Applications of Communications Theory. New York: Plenum Press, 1992.
[3] Heller, J., and I. Jacobs. “Viterbi Decoding for Satellite and Space Communication.” IEEE Transactions on Communication Technology 19, no. 5 (October 1971): 835–48. https://doi.org/10.1109/TCOM.1971.1090711.
[4] Yasuda, Y., K. Kashiki, and Y. Hirata. “High-Rate Punctured Convolutional Codes for Soft Decision Viterbi Decoding.” IEEE Transactions on Communications 32, no. 3 (March 1984): 315–19. https://doi.org/10.1109/TCOM.1984.1096047.
[5] Haccoun, D., and G. Begin. “High-Rate Punctured Convolutional Codes for Viterbi and Sequential Decoding.” IEEE Transactions on Communications 37, no. 11 (November 1989): 1113–25. https://doi.org/10.1109/26.46505.
[6] Begin, G., D. Haccoun, and C. Paquin. “Further Results on High-Rate Punctured Convolutional Codes for Viterbi and Sequential Decoding.” IEEE Transactions on Communications 38, no. 11 (November 1990): 1922–28. https://doi.org/10.1109/26.61470.
[7] Moision, B. "A Truncation Depth Rule of Thumb for Convolutional Codes." In Information Theory and Applications Workshop (January 27 2008-February 1 2008, San Diego, California), 555-557. New York: IEEE, 2008.