sum-product復号法
BCJRアルゴリズム
疎なグラフ(sparce graph)に基づく符号の復号にBCJRアルゴリズムは必要とされる
事後確率分布
外部値
線形符号のトレリス
BCJRアルゴリズムの詳細
- BCJRアルゴリズムは確率の積和計算を分配則を用いて効率化したアルゴリズムとみなせる
- 次の3ステップからなる
- 前向き計算
- 後ろ向き計算
- 事後確率・外部値計算
- 計算機にBCJFアルゴリズムを実装する場合は，確率の積を扱うためにその数値的安定性に気をつける必要がある
BCJRアルゴリズムの計算量
- 符号Cの符号語を全て列挙することにより事後確率，外部値は計算できるが，その計算量は符号語数に比例する
- BCJRアルゴリズムの場合，ノード数に比例する
タナーグラフ
確率領域sum-product復号法
確率領域sum-product復号法の詳細
確率領域sum-product復号法の復号過程の例
タナーグラフにループがある場合のsum-product復号法の振る舞い
確率領域sum-product復号法の導出
対数領域sum-product復号法
対数尤度比(log likelihood ratio)に基づく復号法を示す
対数領域sum-product復号法(log domain sum-product decoding algorithm)では，全て対数領域で処理が行われるため，確率積のような数値計算上取り扱いにくい注意を要する点が少なく，ソフトウェア・ハードウェア実装に向いている
対数領域sum-product復号法の詳細
- 初期化
- 行処理
- 列処理
- 一時推定語の計算
- パリティ検査
- 反復回数のカウント
- 対数領域sum-product復号法は，フィードバックのあるニューラルネットワークと類似した形を持つ
- 並列計算の可能性がある
- 対数領域sum-product復号法をソフトウェアで実装する際には，検査行列を表現するデータの善し悪しが実行性能を左右する
- ループフリーなタナーグラフを持つ符号をテスト用の符号として利用するのがよい
対数領域sum-product復号法の簡単化
- 対数領域sum-product復号法ではf(x)の計算コストが高い
- f(x)の計算コストに対する対処法が問題
- f関数の値を表として持つ
- 記憶したデータから線形補間を行う
- 近似する
- min-sum復号法（加算，最小，正負の判定，正負の符号の乗算の4種類の演算のみで実装可能）
sum-product復号法の計算量
- sum-product復号法は並列アルゴリズムである
- ハードウェア規模は大きくなるが符号長について線形時間よりもさらに高速に復号を実行可能である
最終更新：2006年10月20日 17:00
