(57)【要約】【課題】特性劣化を抑制しつつ復号処理の処理量を低減する。【解決手段】受信尤度データ及び事前尤度に基づいて第１時刻と第１時刻の次の時刻の第２時刻との間のブランチのブランチメトリックを算出し、第１時刻の第１状態及び第２状態と第２時刻の第３状態及び第４状態とで表されるバタフライにおける状態遷移において、第１状態の第１前方累積メトリックと、第２状態の第２前方累積メトリックと、第１時刻の第１状態と第２時刻の第３状態との間のブランチメトリック及び第１状態の第１前方累積メトリックと第２状態の第２前方累積メトリックとの間の差分である第１差分に基づく第２差分とに基づいて、第３状態の第３前方累積メトリックと、第４状態の第４前方累積メトリックとを、バタフライ毎及び時刻毎に算出する演算部と、第２差分をバタフライ毎及び時刻毎に格納する記憶部とを備える復号化装置とする。【選択図】図１
2015039156.tif 000002
【特許請求の範囲】
【請求項１】
開始時刻と終了時刻との間の各時刻の事後尤度を算出する復号化装置であって、
受信尤度データ及び事前尤度に基づいて第１時刻と前記第１時刻の次の時刻である第２時刻との間のブランチのブランチメトリックを算出し、前記第１時刻の第１状態及び第２状態と前記第２時刻の第３状態及び第４状態とで表されるバタフライにおける状態遷移において、前記第１状態の第１前方累積メトリックと、前記第２状態の第２前方累積メトリックと、前記第１時刻の第１状態と前記第２時刻の第３状態との間の前記ブランチメトリック及び前記第１状態の第１前方累積メトリックと前記第２状態の第２前方累積メトリックとの間の差分である第１差分に基づく第２差分とに基づいて、前記第３状態の第３前方累積メトリックと、前記第４状態の第４前方累積メトリックとを、バタフライ毎及び時刻毎に算出する演算部と、
前記第２差分を、バタフライ毎及び時刻毎に格納する記憶部と、
を備える復号化装置。
【請求項２】
前記演算部は、前記終了時刻における前方累積メトリックを最尤パスのパスメトリックとし、前記最尤パスのパスメトリックと各時刻の各バタフライにおける前記第２差分とに基づいて、各状態の最尤のパスメトリックを時刻毎に算出し、各時刻において、前記最尤パスの推定ビットを前記第２差分の符号に基づいて算出し、各時刻において、前記最尤パスの推定ビットの反対ビットを含むパスのパスメトリックのうち最尤のもの及び前記最尤パスのパスメトリックに基づいて事後尤度を算出する、
請求項１に記載の復号化装置。
【請求項３】
前記演算部は、前記終了時刻における前方累積メトリックを最尤パスのパスメトリックとし、前記最尤パスのパスメトリックと各時刻の各バタフライにおける前記第２差分とに基づいて、各状態の最尤のパスメトリックを時刻毎に算出し、各時刻において、前記最尤パスの推定ビットを前記第２差分の符号に基づいて算出し、各時刻において、前記最尤パスの推定ビットの反対ビットを含むパスのパスメトリックであって前記最尤パスに負けたパスのパスメトリックのうち最尤のもの及び前記最尤パスのパスメトリックに基づいて事後尤度を算出する、
請求項１に記載の復号化装置。
【請求項４】
前記演算部は、前記最尤パスの推定ビットの反対ビットを含むパスであって前記最尤パスに負けたパスの数が前記所定数未満である場合、前記最尤パスの推定ビットの反対ビットを含むパスであって前記最尤パスに負けたパスに負けたパスを前記所定数に達するまで抽出し、当該抽出したパスのパスメトリックと前記最尤パスに負けたパスのパスメトリックのうち最尤のもの及び前記最尤パスのパスメトリックに基づいて事後尤度を算出する
請求項３に記載の復号化装置。
【請求項５】
前記所定数は、時刻ごとに可変である
請求項４に記載の復号化装置。
【請求項６】
前記所定数は、周期的に変化する、
請求項４に記載の復号化装置。
【請求項７】
記憶部を有し、開始時刻と終了時刻との間の各時刻の事後尤度を算出する復号化装置において、
受信尤度データ及び事前尤度に基づいて第１時刻と前記第１時刻の次の時刻である第２時刻との間のブランチのブランチメトリックを算出し、前記第１時刻の第１状態及び第２状態と前記第２時刻の第３状態及び第４状態とで表されるバタフライにおける状態遷移に
おいて、前記第１状態の第１前方累積メトリックと、前記第２状態の第２前方累積メトリックと、前記第１時刻の第１状態と前記第２時刻の第３状態との間の前記ブランチメトリック及び前記第１状態の第１前方累積メトリックと前記第２状態の第２前方累積メトリックとの間の差分である第１差分に基づく第２差分とに基づいて、前記第３状態の第３前方累積メトリックと、前記第４状態の第４前方累積メトリックとを、バタフライ毎及び時刻毎に算出し、
前記第２差分を、バタフライ毎及び時刻毎に前記記憶部に格納する、
復号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号化装置、及び、復号化方法に関する。
【背景技術】
【０００２】
デジタル通信システムでは、送信装置はデジタルデータに誤り検出符号化処理や誤り訂正符号化処理を施し、デジタル変調して伝搬路に出力する。伝搬路では、雑音などの影響を受けて信号に歪が生じる。受信装置は、送信装置からの伝搬路を介した信号を受信し、受信信号を復調して信号レベルに応じた尤度データを生成し、これを復号して元のデジタルデータを得る。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１０−２３９４９１号公報
【特許文献２】特開２００６−１９７４２２号公報
【特許文献３】特開２００７−１６４９２３号公報
【非特許文献】
【０００４】
【非特許文献１】J. Hagenauer and P. Hoeher, "A Viterbi algorithm with soft-decision outputs and its applications," in Proc. GLOBECOM'89, vol. 3, Dallas, TX, Nov. 1989, pp. 1680-1686.
【非特許文献２】L. Ang, W. Lim, and M. Kamuf, "Modification of SOVA-based algorithms for efficient hardware implementation," in Proceedings of IEEE 71st Vehicular Technology Conference, Taipei, May 16-19, 2010: 1-5.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
受信装置では、尤度データを用いて、要素復号器における演算を繰り返すことで、出力データ（元のデジタルデータ）を得る。特性のよいデータを得ることが求められるが、一般に、特性の良いデータを得るには、要素復号器における処理量が増大する。また、要素復号器における演算量を減らすと、データの特性が劣化する。
【０００６】
本件開示の技術は、特性劣化を抑制しつつ、復号処理の処理量を低減することを課題とする。
【課題を解決するための手段】
【０００７】
開示の技術は、上記課題を解決するために、以下の手段を採用する。
【０００８】
即ち、第１の態様は、
開始時刻と終了時刻との間の各時刻の事後尤度を算出する復号化装置であって、
受信尤度データ及び事前尤度に基づいて第１時刻と該第１時刻の次の時刻である第２時刻との間のブランチのブランチメトリックを算出し、該第１時刻の第１状態及び第２状態と該第２時刻の第３状態及び第４状態とで表されるバタフライにおける状態遷移において、該第１状態の第１前方累積メトリックと、該第２状態の第２前方累積メトリックと、該第１時刻の第１状態と該第２時刻の第３状態との間の該ブランチメトリック及び該第１状態の第１前方累積メトリックと該第２状態の第２前方累積メトリックとの間の差分である第１差分に基づく第２差分とに基づいて、該第３状態の第３前方累積メトリックと、該第４状態の第４前方累積メトリックとを、バタフライ毎及び時刻毎に算出する演算部と、
該第２差分を、バタフライ毎及び時刻毎に格納する記憶部と、
を備える復号化装置とする。
【０００９】
開示の態様は、プログラムが情報処理装置によって実行されることによって実現されてもよい。即ち、開示の構成は、上記した態様における各手段が実行する処理を、情報処理装置に対して実行させるためのプログラム、或いは当該プログラムを記録したコンピュータ読み取り可能な記録媒体として特定することができる。また、開示の構成は、上記した各手段が実行する処理を情報処理装置が実行する方法をもって特定されてもよい。開示の構成は、上記した各手段が実行する処理を行う情報処理装置を含むシステムとして特定されてもよい。
【発明の効果】
【００１０】
開示の技術によれば、特性劣化を抑制しつつ、復号処理の処理量を低減することができる。
【図面の簡単な説明】
【００１１】
【図１】図１は、３ＧＰＰのターボ符号の定義の例を示す図である。
【図２】図２は、トレリスセクションの例を示す図である。
【図３】図３は、トレリスダイアグラムの例を示す図である。
【図４】図４は、前方累積メトリックαとブランチメトリックγとの関係を示す図である。
【図５】図５は、後方累積メトリックβとブランチメトリックγとの関係を示す図である。
【図６】図６は、実施形態１の通信システムの構成の例を示す図である。
【図７】図７は、送信装置及び受信装置の構成例を示す図である。
【図８】図８は、符号化処理部の例を示す図である。
【図９】図９は、復号処理部の例を示す図である。
【図１０】図１０は、送信装置のハードウェア構成例を示す図である。
【図１１】図１１は、受信装置のハードウェア構成例を示す図である。
【図１２】図１２は、動作例１における第１要素復号器２３１の尤度演算の動作フローの例（１）を示す図である。
【図１３】図１３は、動作例１における第１要素復号器２３１の尤度演算の動作フローの例（２）を示す図である。
【図１４】図１４は、前方累積メトリックαとブランチメトリックγとの例を示す図である。
【図１５】図１５は、シミュレーション結果の例を示す図である。
【図１６】図１６は、動作例２における第１要素復号器２３１の尤度演算の動作フローの例（１）を示す図である。
【図１７】図１７は、動作例２における第１要素復号器２３１の尤度演算の動作フローの例（２）を示す図である。
【図１８】図１８は、実施形態２における復号処理部の構成例を示す図である。
【図１９】図１９は、第１要素復号器２４１の構成例を示す図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して実施形態について説明する。実施形態の構成は例示であり、開示の構成は、開示の実施形態の具体的構成に限定されない。開示の構成の実施にあたって、実施形態に応じた具体的構成が適宜採用されてもよい。
【００１３】
ここでは、通信システムとして３ＧＰＰ（3rd Generation Partnership Project）のＬＴＥ（Long Term Evolution）のような通信システムを想定する。ここで説明する実施形
態は、３ＧＰＰのＬＴＥのような通信システムに限定されず、他の通信システムにも適用可能である。
【００１４】
〔符号化／復号処理〕
ターボ符号およびターボ復号について、３ＧＰＰ移動通信システムで採用されている符号を具体的な例として取り上げて説明する。実施形態の適用範囲は、この符号に限定されるものではない。本実施形態は、一般的に、要素符号として、トレリス符号が適用されていて、対応する要素復号処理として、ＳＩＳＯ（Soft In Soft Out）型の復号器を用いるような符号の復号処理に適用可能である。ここで、ＳＩＳＯ型の復号器は、入力尤度に基づいて、ＭＡＰ演算原理に基づいて、送信ビット系列の各ビットに対しての事後尤度を出力するタイプの復号器である。
【００１５】
（符号化）
図１は、３ＧＰＰのターボ符号の定義の例を示す図である。３ＧＰＰでデータチャネルの符号化方式として定義されているターボ符号は、スタンダードな符号化率１／３のターボ符号であり、２つの要素符号器とその間を関係づけるインターリーバー（ＩＬ）を含む。要素符号は、符号化率１／２のリカーシブな畳み込み符号である。
【００１６】
要素符号の生成多項式は、次のように定義される。
【００１７】
【数１】
2015039156.tif 000003
ここで、
【００１８】
【数２】
2015039156.tif 000004
である。多項式の次数は、遅延メモリのサイズ（ｍ＝３）に対応する。
【００１９】
符号化の終端方法として、例えば、トレリス終端（Trellis Termination）が採用され
る。トレリス終端では、最後の情報ビットを入力した後、遅延メモリと同じ数のテールビットが入力されることで、遅延メモリ内の最後の値が０となる。
【００２０】
実施形態で使用されるターボ符号は、図１の例に限定されるものではない。
【００２１】
（復号）
ターボ符号に対する復号処理は、要素復号処理を繰り返し行う「繰り返し復号処理」である。要素復号器は、２つの要素符号器のそれぞれに対応する復号処理を行う。畳み込み符号に関して、情報ビット毎の推定方法として、ＭＡＰ（Maximum A posteriori Probability）方式が採用される。ただし、ＭＡＰ方式をそのままの形で実装するのはハードウェアの設計上、コストが大きすぎるため、実装に適した形で修正された方式を適用することが考えられている。そのような方式としてよく知られた方式には、「Ｍａｘ−Ｌｏｇ−ＭＡＰ方式」及び「ＳＯＶＡ（Soft Output Viterbi Algorithm）方式」がある。
【００２２】
状態（遅延メモリの状態）は、畳み込み符号の遅延レジスタメモリの値に対応する。遅延メモリのサイズが３であるとき（ｍ＝３）、状態数は２の３乗で８個となる。
【００２３】
ある時刻での情報ビットを入力する前のメモリの状態は、開始状態である。また、情報ビットの入力により開始状態から別の状態へと遷移した状態は、終了状態である。開始状態ｓiと終了状態ｓeとを結ぶ関係は、「ブランチ」と呼ばれる。開始状態ｓiと終了状態
ｓeとの間のブランチは、（ｓi，ｓe）と表される。
【００２４】
トレリスセクションは、畳み込み符号における、ある時刻での情報ビットの入力に対しての、遅延メモリの値（状態）の変化、ローカル符号の出力の様子を図式的に示したものである。
【００２５】
図２は、トレリスセクションの例を示す図である。図２のように、トレリスセクションは、各時刻の異なる状態を縦に並べて、隣接する時刻での可能な遷移先の状態を「ブランチ」でつないだものである。図２の横方向は、時間を表す。図２の例では、時刻ｔ＝ｔ０の各状態が縦に並べられ、時刻ｔ＝ｔ０の各状態から、隣接する時刻である時刻ｔ＝ｔ０＋１での可能な遷移先の状態に、ブランチがつながれている。
【００２６】
トレリスダイアグラムは、トレリスセクションを情報ビット系列分（情報ビット数分）、時間順に並べたグラフである。
【００２７】
図３は、トレリスダイアグラムの例を示す図である。図３の横軸は時間であり、縦軸は遅延メモリの状態を表す。遅延メモリの状態は、開始時に０、終了時に０となるように規定されている。任意の情報ビットの系列は、開始時刻で０の状態から出発して、各時刻での、０及び１のブランチのうちいずれか１つのブランチを辿り、最終的に、終了状態が０になる。トレリスパス（単に、パスともいう）は、このブランチをつないだものである。任意のトレリスパスは、それぞれ互いに異なる取り得る符号語（Codeword）に対応している。図３において、太線で示される折線がトレリスパスの一例である。
【００２８】
一般に、任意の時刻の任意の状態から、別の時刻の任意の状態に、遷移する経路のことも「パス」と呼ぶ。ブランチは「パス」の１つである。
【００２９】
ある状態から発生しているパスに対して、その同じ状態から発生している、もう一方のパスは、「対抗パス」と呼ばれる。また、同様に、ある状態に入力するパスについて、その同じ状態に入力する、もう一方のパスのことも「対抗パス」と呼ばれる。
【００３０】
図２のように対抗パス上の符号ビットの値は、互いに「反転ビット」の値になっている。
【００３１】
α演算は、開始時刻から（開始時刻より後の）ある時刻のある状態に到達するまでの累積メトリックの最大値または最小値を求める演算である。β演算は、終了時刻から（終了時刻より前の）ある時刻のある状態に到達するまでの累積メトリックの最大値または最小値を求める演算である。
【００３２】
α演算において、累積メトリックの最大あるいは最小の選択（最適なメトリックの選択）において、選択されたパスは「勝ちパス」、もう一方のパスは「負けパス」と呼ばれる。２つの候補のパスは、前の時刻のそれぞれの状態に到達するまで、勝ち続けてきたパスである。即ち、２つの候補のパスは、前の時刻のそれぞれの状態の「勝ちパス」である。従って、「負けパス」は前の時刻まで勝ち続け最後の時刻に負けたパスである。β演算に対しても、時間の方向を反転させて同様の呼び方が適用される。
【００３３】
メトリックの最適性が最大あるいは最小のいずれとするかは、入力尤度から、ブランチメトリックを生成する場合の係数の正負に依存する。最大のものが最適の場合には「ｍａｘ規約」、最小のものが最適の場合には「ｍｉｎ規約」と呼ぶ。
【００３４】
ｕ∈｛０，１｝に対して、ビットの値を反転させたものを、ｕc＝１−ｕと表す。また
、ビット値｛０，１｝のそれぞれを、｛＋１，−１｝の値に対応させる規則を次のようにする。
【００３５】
【数３】
2015039156.tif 000005
数式による表記はビットｕに対しての振幅シンボルをｕのバーとして次のように与えられる。
【００３６】
【数４】
2015039156.tif 000006
ビットｐに対する振幅シンボル（ｐのバー）も同様である。
【００３７】
情報ビットのサイズＫの符号語のビットサイズをＮとすると、受信信号の尤度データ系列は、Ｎ次元の実ユークリッド空間上の点と解釈される。雑音がない場合には、各符号語は、ユークリッド空間上の異なる２K個の点として表される。一般には雑音データが付加
されて、受信データは、符号語とは異なる任意の点として表されることになる。最尤復号は、この受信データに対して、最も近い符号語の点を、送信された符号ビット系列であると推定することである。基本的な定義として、各符号語とのユークリッド距離を「メトリック」とする。ただし、上記の符号原理から、結果は、各符号語のメトリックの大小関係に依存していることが分かる。従って、すべての符号語のメトリックに共通する量を一律加減算したものを、「メトリック」と再定義することが可能である。また、さらに、Ｍａｘ−Ｌｏｇ−ＭＡＰ方式では、メトリックの全体に共通の係数でスケールしても結果は変わらないことが示される。よって、任意にスケールを掛けたものを「メトリック」として再定義する場合がある。
【００３８】
パスメトリックは、トレリスパスに対応する符号語のメトリックである。メトリックは、ユークリッド距離であるから、各ビットについての距離の２乗和で表わされる。
【００３９】
ブランチメトリックは、トレリスのブランチに対応するローカル符号に限定したメトリック値である。
【００４０】
（Ｍａｘ−Ｌｏｇ−ＭＡＰ方式）
ここで、Ｍａｘ−Ｌｏｇ−ＭＡＰ方式について説明する。Ｍａｘ−Ｌｏｇ−ＭＡＰ方式では、トレリスダイアグラム上でビタビ演算が行われ、パスメトリックが算出される。
【００４１】
最初に、すべてのトレリスパスに対しての、パスメトリックが求められる。ある時刻の
ブランチを通過するパスのメトリック（パスメトリック）は、ブランチの始点の状態の前方累積メトリックαと終点の状態の後方累積メトリックβおよびブランチメトリックの和によって与えられる。ブランチの始点の状態の前方累積メトリックαは、開始時刻の状態から当該ブランチの始点の状態までのブランチメトリックの和である。ブランチの終点の状態の後方累積メトリックβは、終了時刻の状態から当該ブランチの終点の状態までのブランチメトリックの和である。ここでは、ｍａｘ規約が採用される。
【００４２】
時刻ｔ＝ｉにおいて状態ｓから状態ｓ’に遷移する際のブランチメトリックγは次のように表される。
【００４３】
【数５】
2015039156.tif 000007
ただし、（ｕ，ｐ）は、ブランチＢ（ｓ，ｓ’）に対応するローカル符号である。ｙs
、ｙpは、受信尤度（尤度データ）である。Ｌeは、前の演算における事後尤度である。
【００４４】
時刻ｔ＝ｉ＋１における状態ｓの前方累積メトリックαは、次のように求められる。ここでは、トレリスダイアグラム上で、時刻ｔ＝iの状態ｓ０または状態ｓ１は、時刻ｔ＝
ｉ＋１の状態ｓに遷移するものとする。
【００４５】
【数６】
2015039156.tif 000008
ここで、時刻ｔ＝ｉにおける状態ｓ０の前方累積メトリックに時刻ｔ＝ｉにおいて状態ｓ０から状態ｓに遷移する際のブランチメトリックを足したものをＡとする。時刻ｔ＝ｉにおける状態ｓ１の前方累積メトリックに時刻ｔ＝ｉにおいて状態ｓ１から状態ｓに遷移する際のブランチメトリックを足したものをＢとする。時刻ｔ＝ｉ＋１における状態ｓの前方累積メトリックαは、Ａ及びＢのうち大きい値のものである。ここで、ｉ＝０からｉ＝Ｋｔ−１まで昇順に前方累積メトリックαが求められる。
【００４６】
図４は、前方累積メトリックαとブランチメトリックγとの関係を示す図である。図４において、各白丸は、１つの状態を表す。図４では、時刻ｔ＝ｉの状態ｓ0及び状態ｓ1、時刻ｔ＝ｉ＋１の状態ｓ’0及び状態ｓ’1が示される。現時刻の前方累積メトリックαは、１時刻前の前方累積メトリックと１時刻前のブランチメトリックとから求められる。すべての前方累積メトリックαは、保存され、事後尤度Ｌの算出の際に使用される。
【００４７】
時刻ｔ＝ｉにおける状態ｓの後方累積メトリックβは、次のように求められる。
【００４８】
【数７】
2015039156.tif 000009
ここで、ｉ＝Ｋｔ−１からｉ＝０まで降順にβが求められる。
【００４９】
図５は、後方累積メトリックβとブランチメトリックγとの関係を示す図である。図５において、各白丸は、１つの状態を表す。図５では、時刻ｔ＝ｉの状態ｓ0及び状態ｓ1、
時刻ｔ＝ｉ＋１の状態ｓ’0及び状態ｓ’1が示される。現時刻の前方累積メトリックβは、１時刻後の前方累積メトリックと現時刻のブランチメトリックとから求められる。
【００５０】
次に、各時刻において、ビットの値が０である場合、及び、ビットの値が１であるの場合の事後尤度（Ｌ0、Ｌ1）が求められる。各時刻で、それぞれのビットの値を取るすべてのトレリスパスのうち、最適なメトリックのパスが選択される。最適パスのメトリックが、事後尤度とされる。さらに、ビットの値が０である場合の事後尤度とビットの値が１である場合の事後尤度との差が求められる。
【００５１】
時刻ｔ＝ｉにおける事後尤度の差Ｌは、次のように求められる。ここでは、ｍａｘ規約が採用されている。
【００５２】
【数８】
2015039156.tif 000010
ここで、ｉ＝Ｋｔ−１からｉ＝０まで降順に、Ｌ（ｉ）が求められる。事後尤度の差Ｌ（ｉ）は、後方累積メトリックβの算出とともに算出される。事後尤度の差Ｌ（ｉ）の算出の際に、保存されている前方累積メトリックαが使用される。また、ｂは、ビット値であり、０または１をとる。Ｌb（ｉ）は、時刻ｔ＝ｉにおいてビット値がｂであるパスの
最尤パスの事後尤度である。Ｂbは、入力ビット値がｂであるブランチの集合である。Ｌ
（ｉ）は、次の演算におけるＬe（ｉ）で使用される。Ｌ（ｉ）が大きいほど、時刻ｔ＝
ｉにおけるブランチの情報ビットが０である確率が高い。また、Ｌ（ｉ）は、他の要素復号器で使用され得る。次の演算におけるＬe（ｉ）（＝Ｌe(next)（ｉ））は、Ｌ（ｉ）を用いて、次のように表される。
【００５３】
【数９】
2015039156.tif 000011
（修正Ｍａｘ−Ｌｏｇ−ＭＡＰ方式）
ここで、修正Ｍａｘ−Ｌｏｇ−ＭＡＰ方式について説明する。Ｍａｘ−Ｌｏｇ−ＭＡＰ方式では、各時刻での２つのビット値に対応する事後尤度（Ｌ0（ｉ），Ｌ1（ｉ））において一方は最尤パスに一致することが利用される。即ち、α演算の結果から、最尤パスのパスメトリックが特定される。最尤パスを構成するブランチに対応する情報ビットは、推定ビットとなる。Ｌ演算（事後尤度の演算）では、各時刻で、推定ビットの反対ビットに対しての事後尤度が求められる。
【００５４】
時刻ｔ＝ｉにおいて状態ｓから状態ｓ'に遷移する際のブランチメトリックγは次のよ
うに表される。
【００５５】
【数１０】
2015039156.tif 000012
ただし、（ｕ，ｐ）は、ブランチＢ＝（ｓ，ｓ’）に対応するローカル符号である。
【００５６】
時刻ｔ＝ｉ＋１における状態ｓの前方累積メトリックαは、次のように求められる。
【００５７】
【数１１】
2015039156.tif 000013
ここで、ｉ＝０からｉ＝Ｋｔ−１まで昇順にαが求められる。また、前方累積メトリックαの計算において、どちらのブランチが選択されたかの情報が、フラグ（フラグ情報）として保存される。各ブランチは、対応する入力情報ビットによって区別される。時刻ｔ＝ｉにおけるフラグ情報ｑiは、ブランチの入力情報ビットｕによって、次のように表さ
れる。
【００５８】
【数１２】
2015039156.tif 000014
ここで、ｓxは、選択されたブランチの時刻ｔ＝ｉにおける状態である。
【００５９】
また、選択されなかったブランチの前方累積メトリックαi,loseが、保存される。αi,loseは、次のように表される。
【００６０】
【数１３】
2015039156.tif 000015
ここで、ｓyは、選択されなかったブランチの時刻ｔ＝ｉにおける状態である。
【００６１】
トレースバックの開始位置ｉBでの最大のλの値が、最尤パスのパスメトリックとされ
る。
【００６２】
【数１４】
2015039156.tif 000016
ただし、トレリス終端を行っている場合には、境界での状態はｓ＝０であり、βの境界条件をβiB（ｓ）＝０とすると、
【００６３】
【数１５】
2015039156.tif 000017
となる。
【００６４】
ｉ＝Ｋｔ−１での終状態０からフラグ情報により勝ちパスをたどることで、最尤パスが特定される。最尤パスに対応するフラグ情報は、推定ビット（ｕiのハット）に一致して
いる。
【００６５】
【数１６】
2015039156.tif 000018
事後尤度Ｌを算出する際に、前方累積メトリックαが再計算される。負けパスの前方累積メトリックαは保存されているが、勝ちパスの前方累積メトリックαは保存されていない。そこで、勝ちパスの前方累積メトリックαは、１時刻後の前方累積メトリックと現時刻のブランチメトリックを使用して算出される。即ち、時刻ｔ＝ｉの勝ちパスの前方累積メトリックαは、時刻ｔ＝ｉ＋１の前方累積メトリックと時刻ｔ＝ｉのブランチメトリックを使用して算出される。また、任意の状態の前方累積メトリックが勝ちパスであるか負けパスであるかは、フラグ情報によって認識される。
【００６６】
【数１７】
2015039156.tif 000019
時刻ｔ＝ｉにおける状態ｓの後方累積メトリックβは、次のように求められる。
【００６７】
【数１８】
2015039156.tif 000020
ここで、ｉ＝Ｋｔ−１からｉ＝０まで降順にβが求められる。
【００６８】
次に、各時刻において、ビットの値が０である場合及びビットの値が１である場合の事後尤度（Ｌ0、Ｌ1）が求められる。各時刻で、最適パスのブランチのビットの値の事後尤度は、Ｌmaxとする。最適パスのブランチのビットの値の反対ビットの値の事後尤度とし
て、当該反対ビットの値を取るすべてのトレリスパスのうち最適なメトリックのパスが選択される。さらに、最適パスのブランチのビット値の事後尤度と最適パスのブランチのビットの値の反対ビットの値の事後尤度との差が求められる。
【００６９】
時刻ｔ＝ｉにおける事後尤度の差Ｌ（ｉ）は、次のように求められる。
【００７０】
【数１９】
2015039156.tif 000021
ここで、ｉ＝Ｋｔ−１からｉ＝０まで降順に、Ｌ（ｉ）が求められる。事後尤度の差Ｌ（ｉ）は、後方累積メトリックβの算出とともに算出される。事後尤度の差Ｌ（ｉ）の算出の際に、保存されている前方累積メトリックα及び再計算される前方累積メトリックαが使用される。
【００７１】
また、ｂは、ビット値であり、０または１をとる。Ｂbは、入力ビット値がｂであるブ
ランチの集合である。Ｌ（ｉ）は、次の演算におけるＬe（ｉ）で使用される。Ｌ（ｉ）
が大きいほど、時刻ｔ＝ｉにおけるブランチの情報ビットが０である確率が高い。また、Ｌ（ｉ）は、他の要素復号器で使用され得る。
【００７２】
（ＳＯＶＡ方式）
ここで、ＳＯＶＡ（Soft Output Viterbi Algorithm）方式について説明する。ＳＯＶ
Ａ方式は、最尤パスに対してのトレースバックにおいて、各時刻で、最尤パスに負ける「負けパス」を、「β演算」及び「Ｌ演算」のための候補として選択する方式である。Ｍａｘ−Ｌｏｇ−ＭＡＰ方式と比較して、処理量は減少するが、特性が劣化する。ＳＯＶＡ方式の演算上の特徴としては、後方累積メトリックβは導入されず、パスメトリックＬの差分を扱うことが挙げられる。「勝ちパス」である最尤パスに負けた負けパスの事後尤度Ｌloseは、最尤パスの事後尤度Ｌwinとα演算におけるメトリックの差Δとにより次のよう
に求まる。ここでは、ｍｉｎ規約が採用される。
【００７３】
【数２０】
2015039156.tif 000022
α演算は、上記のＭａｘ−Ｌｏｇ−ＭＡＰ方式と同様に行われる。また、α演算において選択されたブランチの前方累積メトリックと選択されなかったブランチの前方累積メトリックとの差Δが、保存される。
【００７４】
さらに、前方累積メトリックαの計算において、どちらのブランチが選択されたかの情報が、フラグ（選択フラグ）として保存される。各ブランチは、対応する入力情報ビットによって区別される。
【００７５】
Ｌ演算（事後尤度の差Ｌの算出）において、トレースバックの開始位置での最尤パスのメトリックは、α演算の結果として得られる。この最尤パスを基準として、α演算の結果として得られるメトリックの差Δの値と、選択フラグによって、「負けパス」の特定と、当該「負けパス」に対するメトリック値の演算が、上記の関係式により実行される。
【００７６】
時刻ｔ＝ｉにおける事後尤度の差Ｌ（ｉ）は、最尤パスのメトリック値と、最尤パスに負けた「負けパス」のうち時刻ｔ＝ｉにおいて最尤パスの推定ビットの反対のビットを有
するものの中から最尤のパスのメトリック値との差として得られる。
【００７７】
また、最尤パスに負けたパス同士がトレースバックによって同じ状態に入力する場合には、両者のうちの最尤のパスが選択される。これは、β演算に相当する処理となる。Ｌ（ｉ）は、次の演算におけるＬe（ｉ）で使用される。
【００７８】
ＳＯＶＡ方式では、Ｌ演算で使用される候補として、最尤パスに負ける「負けパス」が採用される。
【００７９】
（修正ＳＯＶＡ方式）
ここでは、修正ＳＯＶＡ方式について説明する。ＳＯＶＡ方式の特性を改善する方式として、修正ＳＯＶＡ方式が知られている。
【００８０】
上記のＳＯＶＡ方式では、負けパスの時刻ｔ＝ｉにおけるビットが最尤パスの時刻ｔ＝ｉにおける推定ビットと同じである負けパスは、事後尤度Ｌ（ｉ）の算出から除外される。従って、上記のＳＯＶＡ方式では、事後尤度の差Ｌの算出の際に、選択される負けパスの候補の数が小さくなるおそれがある。これを改善するために、負けパスの時刻ｔ＝ｉにおけるブランチが、最尤パスの時刻ｔ＝ｉにおける推定ビットと同じとなる場合、当該負けパスの時刻ｔ＝ｉにおける負けパス（負けパスの負けパス）が候補として選択されるようにする。
【００８１】
修正ＳＯＶＡ方式は、ＳＯＶＡ方式に対して大きく特性が改善される。しかし、修正ＳＯＶＡ方式の特性は、Ｍａｘ−Ｌｏｇ−ＭＡＰ方式の特性と比較して、劣化している。
【００８２】
〔実施形態１〕
（構成例）
図６は、本実施形態の通信システムの構成の例を示す図である。通信システム１０は、送信装置１００と受信装置２００とが、伝搬路（チャネル）を通して、情報ビットを送受信するシステムである。図６のように、本実施形態の通信システム１０は、送信装置１００、受信装置２００を含む。送信装置１００は、伝搬路を介して、受信装置２００に、データ送信を行う。受信装置２００は、送信装置１００から受信した信号を復号する。受信装置２００は、復号化装置の一例である。
【００８３】
図７は、送信装置及び受信装置の構成例を示す図である。図７の送信装置１００は、符号化処理部１１０、変調マッピング処理部１２０、送信処理部１３０を有する。
【００８４】
符号化処理部１１０は、情報ビット系列を誤り訂正符号化し、符号ビット系列に変換する。
【００８５】
変調マッピング処理部１２０は、符号ビットを規定の数のビットの単位で変調処理を行い、信号シンボルにマッピングする。信号シンボル（単に、シンボルとも言う）は、元のビットの値に応じて、複素平面上（信号空間）の点として表される。
【００８６】
送信処理部１３０は、信号シンボルを搬送波の形に変換して、チャネル（伝搬路）に送信する。
【００８７】
図８は、符号化処理部の例を示す図である。図８の符号化処理部１１０は、例えば、３ＧＰＰのＬＴＥの無線規格に準拠した符号器であり、第１要素符号化部１１１と、第２要素符号化部１１２と、情報源の入力ビットに対して入力ビットの並び替えを行うインタリーバ（ＩＬ）１１３とを含む。また、符号化処理部１１０は、パラレルシリアル（Ｐ／Ｓ
）変換部１１４を含む。
【００８８】
第１要素符号化部１１１は、シフトレジスタＤ及び排他的論理和回路を含む畳み込み符号化部であり、入力データが順次シフトされ、それにより出力が生成され、第１パリティビットを生成して出力する。第２要素符号化部１１２は、同様に、第２パリティビットを生成して出力する。
【００８９】
第１要素符号化部１１１において、第１スイッチは、入力が情報ビット（０または１）の場合に、入力側に接続して情報ビットを第１要素符号化部１１１に取り込む。第２要素符号化部１１２において、第２スイッチも同様に、入力が情報ビット（０または１）の場合に、インタリーバ（ＩＬ）１１３によってインタリーブされた入力側に接続して情報ビットを第２要素符号化部１１２に取り込む。
【００９０】
パラレルシリアル変換部１１４は、組織ビット、第１パリティビット、第２パリティビット、テールビットを直列データに変換して、符号ビットとして出力する。
【００９１】
図７の受信装置２００は、受信処理部２１０、復調デマッピング処理部２２０、復号処理部２３０を有する。
【００９２】
受信処理部２１０は、受信データに対して（同期検波等の）適切な処理を行い、受信シンボルを信号空間上の点の形で求める。
【００９３】
復調デマッピング処理部２２０は、受信シンボルから各ビットに対応する尤度データ（受信尤度データ）を求める。尤度データは、復号処理の観点で軟判定データとも呼ばれる。ビットの尤度は、例えば、当該ビットが０であること（または１であること）の尤もらしさを表す尺度である。
【００９４】
復号処理部２３０は、軟判定データを用いて誤り訂正復号処理を行い、送信ビットを推定する。復号処理部２３０には、尤度データが復調デマッピング処理部２２０から入力される。復号処理部２３０は、尤度データを用いて、復号ビットを算出する。復号処理部２３０は、例えば、ターボ復号器である。
【００９５】
図９は、復号処理部の例を示す図である。図９の復号処理部２３０は、第１要素復号器２３１、第２要素復号器２３２、インタリーバ（ＩＬ）２３３、デインタリーバ（ＤｅＩＬ）２３４を含む。
【００９６】
第１要素復号器２３１は、尤度データｙｓ、尤度データｙｐ１、第２要素復号器２３２の出力データ等を用いて、復号ビットを算出する。第２要素復号器２３２は、尤度データｙｓ、尤度データｙｐ２、第１要素復号器２３１の出力データ等を用いて、復号ビットを算出する。インタリーバ２３３は、尤度データｙｓ、第１要素復号器２３１の出力データの順序を入れ替え、入れ替えたデータを第２要素復号器２３２に出力する。デインタリーバ２３４は、第２要素復号器２３２の出力データの順序を入れ替え、入れ替えたデータを第１要素復号器２３１に出力する。また、デインタリーバ２３４は、第２要素復号器２３２の出力データの順序を入れ替え、入れ替えたデータを復号ビットとして出力する。
【００９７】
第１要素符号器２３１から出力される事後尤度は、インタリーブされて、第２要素符号器２３２の入力となる。第１要素符号器２３１から出力される事後尤度は、第１要素復号器では、次の演算における事前尤度として解釈される。第１要素符号器２３１及び第２要素復号器２３２が、演算を繰り返すことによって、出力データのＳ／Ｎ比が改善されていく。
【００９８】
送信装置１００、受信装置２００は、専用または汎用のコンピュータ、あるいは、コンピュータを搭載した電子機器を使用して実現可能である。
【００９９】
コンピュータ、すなわち、情報処理装置は、プロセッサ、主記憶装置、及び、二次記憶装置や、通信インタフェース装置のような周辺装置とのインタフェース装置を含む。記憶装置（主記憶装置及び二次記憶装置）は、コンピュータ読み取り可能な記録媒体である。
【０１００】
コンピュータは、プロセッサが記録媒体に記憶されたプログラムを主記憶装置の作業領域にロードして実行し、プログラムの実行を通じて周辺機器が制御されることによって、所定の目的に合致した機能を実現することができる。
【０１０１】
プロセッサは、例えば、ＣＰＵ（Central Processing Unit）やＤＳＰ（Data Signal Processor）である。主記憶装置は、例えば、ＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）を含む。
【０１０２】
二次記憶装置は、例えば、ＥＰＲＯＭ（Erasable Programmable ROM）、ハードディス
クドライブ（ＨＤＤ、Hard Disk Drive）である。また、二次記憶装置は、リムーバブル
メディア、即ち可搬記録媒体を含むことができる。リムーバブルメディアは、例えば、ＵＳＢ（Universal Serial Bus）メモリ、あるいは、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）のようなディスク記録媒体である。
【０１０３】
通信インタフェース装置は、例えば、ＬＡＮ（Local Area Network）インタフェースボードや、無線通信のための無線通信回路である。
【０１０４】
周辺装置は、上記の二次記憶装置や通信インタフェース装置の他、キーボードやポインティングデバイスのような入力装置や、ディスプレイ装置やプリンタのような出力装置を含む。また、入力装置は、カメラのような映像や画像の入力装置や、マイクロフォンのような音声の入力装置を含むことができる。また、出力装置は、スピーカのような音声の出力装置を含むことができる。
【０１０５】
主記憶装置または二次記憶装置には、オペレーティングシステム、各種プログラム、各種テーブル等が格納される。オペレーティングシステムは、ソフトウェアとハードウェアとの仲介、メモリ空間の管理、ファイル管理、プロセスやタスクの管理等を行うソフトウェアである。
【０１０６】
一連の処理は、ハードウェアにより実行させることもできるが、ソフトウェアにより実行させることもできる。送信装置１００、受信装置２００の各ユニットは、ハードウェアの構成要素、ソフトウェアの構成要素、又は、これらの組み合わせとして、それぞれ実現され得る。
【０１０７】
ハードウェアの構成要素は、ハードウェア回路であり、例えば、ＦＰＧＡ（Field Programmable Gate Array）、特定用途向け集積回路（ＡＳＩＣ）、ゲートアレイ、論理ゲー
トの組み合わせ、アナログ回路等がある。
【０１０８】
ソフトウェアの構成要素は、ソフトウェアとして所定の処理を実現する部品である。ソフトウェアの構成要素は、ソフトウェアを実現する言語、開発環境等を限定する概念ではない。
【０１０９】
プログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理は
もちろん、必ずしも時系列的に処理されなくても、並列的または個別に実行される処理を含む。
【０１１０】
図１０は、送信装置のハードウェア構成例を示す図である。送信装置１００は、プロセッサ１８２、記憶装置１８４、ベースバンド処理回路１８６、無線処理回路１８８、アンテナ１９０を含む。プロセッサ１８２、記憶装置１８４、ベースバンド処理回路１８６、無線処理回路１８８、アンテナ１９０は、例えば、バスを介して互いに接続される。
【０１１１】
プロセッサ１８２は、符号化処理部１１０、変調マッピング処理部１２０、送信処理部１３０としての機能を実現しうる。プロセッサ１８２は、演算部の一例である。記憶装置１８４は、プロセッサで実行されるプログラム、プログラムの実行の際に使用されるデータ等が格納される。記憶装置１８４は、メモリ（記憶部）の一例である。ベースバンド処理回路１８６は、ベースバンド信号を処理する。無線処理回路１８８は、アンテナ１９０で送受信される無線信号を処理する。アンテナ１９０は、無線処理回路１８８等で処理された送信信号を送信する。
【０１１２】
図１１は、受信装置のハードウェア構成例を示す図である。受信装置２００は、プロセッサ２８２、記憶装置２８４、ベースバンド処理回路２８６、無線処理回路２８８、アンテナ２９０を含む。プロセッサ２８２、記憶装置２８４、ベースバンド処理回路２８６、無線処理回路２８８、アンテナ２９０は、例えば、バスを介して互いに接続される。
【０１１３】
プロセッサ２８２は、受信処理部２１０、復調デマッピング処理部２２０、復号処理部２３０としての機能を実現しうる。プロセッサ２８２は、演算部の一例である。記憶装置２８４は、プロセッサで実行されるプログラム、プログラムの実行の際に使用されるデータ等が格納される。記憶装置２８４は、メモリ（記憶部）の一例である。記憶装置２８４として、複数の記憶装置が使用されてもよい。ベースバンド処理回路２８６は、ベースバンド信号を処理する。無線処理回路２８８は、アンテナ２９０で送受信される無線信号を処理する。アンテナ２９０は、他の装置から送信された信号を受信する。
【０１１４】
復号処理部２３０等における処理は、例えば、プロセッサで実行されるプログラムによって実現される。復号処理部２３０等における処理は、ＡＳＩＣ（Application Specific
Integrated Circuit）や、ＦＰＧＡ（Field-Programmable Gate Array）などの回路で実装されてもよい。
【０１１５】
（動作例１）
ここでは、復号処理部２３０の第１要素復号器２３１の動作例１について説明する。要素復号器２３１には、尤度データｙsと尤度データｙp1（ｙpともいう）とが復調デマッピング処理部から入力される。第１要素復号器２３１は、復号ビットを出力する。第２要素復号器２３２の動作は、第１要素復号器２３１の動作と同様である。
【０１１６】
動作例１では、第１要素復号器２３１は、Ｍａｘ−Ｌｏｇ−ＭＡＰ方式と同様の尤度演算を、ＳＯＶＡ方式を利用して行う。ここでは、ｍｉｎ規約が採用される。
【０１１７】
図１２及び図１３は、動作例１における第１要素復号器２３１の尤度演算の動作フローの例を示す図である。図１２の「Ａ」は、図１３の「Ａ」と接続する。
【０１１８】
ステップＳ１０１からステップＳ１０５までの処理は、前方累積メトリック演算（α演算）における処理である。
【０１１９】
ステップＳ１０１では、第１要素復号器２３１は、変数ｉを用意し、変数ｉに初期値０
を代入する。変数ｉは、時刻に対応する変数である。時刻ｔ＝０は、開始時刻である。
【０１２０】
ステップＳ１０２では、第１要素復号器２３１は、変数ｉが（Ｋｔ−１）以下であるか否かを判定する。所定値Ｋｔは、第１要素復号器２３１に入力される１つの情報ビット系列の長さに対応する。変数ｉが（Ｋｔ−１）以下である場合（Ｓ１０２；ＹＥＳ）、処理がステップＳ１０３に進む。変数ｉが（Ｋｔ−１）以下でない場合（Ｓ１０２；ＮＯ）、処理がステップＳ１０６に進む。時刻ｔ＝Ｋｔは、終了時刻である。
【０１２１】
ステップＳ１０３では、第１要素復号器２３１は、時刻ｔ＝ｉ＋１における前方累積メトリックを演算し、保存する。
【０１２２】
第１要素復号器２３１は、時刻ｔ＝ｉの尤度データｙs（ｉ）、尤度データｙp（ｉ）、事後尤度データＬe（ｉ）を取得する。第１要素復号器２３１は、例えば、メモリに格納
される時刻ｔ＝ｉの尤度データｙs、尤度データｙp及び事後尤度データＬeを取得する。
第１要素復号器２３１は、時刻ｔ＝ｉから時刻ｔ＝ｉ＋１へのブランチ毎にブランチメトリックγを算出する。時刻ｔ＝ｉの状態ｓから時刻ｔ＝ｔ＋１の状態ｓ’に遷移する際のブランチメトリックγは次のように表される。
【０１２３】
【数２１】
2015039156.tif 000023
ただし、（ｕ，ｐ）は、ブランチＢ（ｓ，ｓ’）に対応するローカル符号である。Ｌe
は、前の演算における事後尤度である。Ｌeは、他の要素復号器（第２要素復号器２３２
）の演算による事後尤度であってもよい。最初の演算では、Ｌeは、例えば、０である。
【０１２４】
さらに、第１要素復号器２３１は、前方累積メトリックの演算（α演算）を行う。時刻ｔ＝ｉ＋１における状態ｓの前方累積メトリックαは、次のように求められる。ここでは、トレリスダイアグラム上で、状態ｓ０及び状態ｓ１は、状態ｓに遷移し得るものとする。また、α0（ｓ）＝０であるとする。
【０１２５】
【数２２】
2015039156.tif 000024
第１要素復号器２３１は、時刻ｔ＝ｉ＋１のすべての状態ｓについて、αi+1（ｓ）を
、算出し、メモリに保存する。
【０１２６】
ステップＳ１０４では、第１要素復号器２３１は、勝ちパスの尤度と負けパスの尤度との差分Δを算出する。
【０１２７】
図１４は、前方累積メトリックαとブランチメトリックγとの例を示す図である。図１４の例では、２つの開始状態（状態ｓ0及び状態ｓ1）から２つの終了状態（状態ｓ’0及
び状態ｓ’1）までが示されている。図１４のような２つの開始状態と２つの終了状態と
をブランチで結んだ図をバタフライともいう。トレリスダイアグラムにおいて、時刻ｔ＝ｉと時刻ｔ＝ｉ＋１との間には、４つのバタフライが存在する。図２において、破線の曲線で囲まれた部分は、バタフライの一例である。また、図３において、破線の曲線で囲ま
れた部分は、それぞれ、バタフライの一例である。
【０１２８】
第１要素復号器２３１は、時刻ｔ＝ｉと時刻ｔ＝ｉ＋１との間の４つのバタフライに対して次の式で表される演算を行う。ここでは、１つのバタフライにおいて、時刻ｔ＝ｉにおける状態ｓ0及び状態ｓ1が、時刻ｔ＝ｉ＋１における状態ｓ’0及び状態ｓ’1に遷移するとする。
【０１２９】
【数２３】
2015039156.tif 000025
ここで、ローカル符号の対称性から、各バタフライにおいて、次の関係式が導かれる。
【０１３０】
【数２４】
2015039156.tif 000026
γi,0は、メモリに格納されてもよい。ここでは、ブランチＢ＝（ｓ0，ｓ’0）及びブ
ランチＢ＝（ｓ1，ｓ’1）が情報ビットｕ＝０に対応し、ブランチＢ＝（ｓ0，ｓ’1）及びブランチＢ＝（ｓ1，ｓ’0）が情報ビットｕ＝１に対応するとする。ここで、時刻ｔ＝ｉ＋１の状態ｓの前方累積メトリックαi+1（ｓ）の算出の際に用いた２つのパスの尤度
の差分Δを次のように定義する。
【０１３１】
【数２５】
2015039156.tif 000027
第１要素復号器２３１は、時刻ｔ＝ｉ＋１のすべての状態ｓについて、上記の尤度の差分Δi（ｓ）を算出する。
【０１３２】
ここでは、尤度の差分Δiは、時刻ｔ＝ｉにおける情報ビットｕが０であるパスがより
尤もらしいパスである場合に負になり、時刻ｔ＝ｉにおける情報ビットｕが１であるパスがより尤もらしいパスである場合に正になる。ここで、差分Δの正負と、上記のγi,0と
を用いて、前方累積メトリックαは、次のように、表される。
【０１３３】
【数２６】
2015039156.tif 000028
第１要素復号器２３１は、時刻ｔ＝ｉと時刻ｔ＝ｉ＋１との間の１つのバタフライにつき、２つの差分Δi（ｓ’0）及び差分Δi（ｓ’1）のうち１つの差分Δi（ｓ’0）を、メモリに格納する。即ち、時刻ｔ＝ｉと時刻ｔ＝ｉ＋１との間の４つのバタフライに対して、４つの差分Δiが、メモリに格納される。なお、差分Δi（ｓ’1）は、差分Δi（ｓ’0
）とγi,0とによって、容易に算出される。よって、差分Δi（ｓ’1）は、メモリに格納
されなくてもよい。
【０１３４】
また、第１要素復号器２３１は、αi+1（ｓ’0）及びαi+1（ｓ’1）をメモリに格納する。メモリに格納されたαi+1（ｓ’0）及びαi+1（ｓ’1）は、次の時刻（ｔ＝ｉ＋２）において、αが算出される際に使用される。ここで、第１要素復号器２３１は、αi（ｓ
’0）及びαi（ｓ’1）を、メモリから削除してもよい。αi（ｓ’0）及びαi（ｓ’1）
がメモリから削除されることで、メモリの使用量が削減される。
【０１３５】
ステップＳ１０５では、第１要素復号器２３１は、変数ｉに（ｉ＋１）を代入し、処理がステップＳ１０２に戻る。変数ｉが（Ｋｔ−１）を超えたとき、ステップＳ１０２を経て、処理が、ステップＳ１０６に進む。
【０１３６】
ステップＳ１０６以降は、事後尤度演算（Ｌ演算）における処理である。ｉ＝Ｋｔ−１での状態ｓ＝０（終状態）からフラグ情報（パス選択フラグ）により勝ちパスをたどることで最尤パスが、特定される。最尤パスに対応するフラグ情報は、推定ビット（ｕiのハ
ット）に一致する。
【０１３７】
【数２７】
2015039156.tif 000029
ステップＳ１０６では、第１要素復号器２３１は、変数ｉを用意し、変数ｉに（Ｋｔ−１）を代入する。時刻ｔ＝Ｋｔは、トレースバック開始位置である。
【０１３８】
ステップＳ１０７では、第１要素復号器２３１は、変数ｉが０以上であるか否かを判定する。変数ｉが０以上である場合（Ｓ１０７；ＹＥＳ）、処理がステップＳ１０８に進む。変数ｉが０以上でない場合（Ｓ１０７；ＮＯ）、処理が終了する。
【０１３９】
ステップＳ１０８では、第１要素復号器２３１は、時刻ｔ＝ｉにおける尤度の差分Δi
を算出する。
【０１４０】
第１要素復号器２３１は、時刻ｔ＝ｉの尤度データｙs（ｉ）、尤度データｙp（ｉ）、事後尤度データＬe（ｉ）を取得する。第１要素復号器２３１は、例えば、メモリに格納
される時刻ｔ＝ｉの尤度データｙs、尤度データｙp及び事後尤度データＬeを取得する。
第１要素復号器２３１は、時刻ｔ＝ｉの尤度データｙs、尤度データｙp及び事後尤度データＬeに基づいて、γi,0を算出する。γi,0がメモリに格納されている場合には、第１要
素復号器２３１はγi,0をメモリから取得してもよい。
【０１４１】
第１要素復号器２３１は、メモリに格納されている差分Δi（ｓ’0）を、メモリから取得する。また、第１要素復号器２３１は、メモリに格納されない差分Δi（ｓ’1）を算出する。メモリに格納されない差分Δi（ｓ’1）は、差分Δi（ｓ’0）及びγi,0を用いて
、次のように算出される。
【０１４２】
【数２８】
2015039156.tif 000030
また、時刻ｔ＝ｉ＋１の状態ｓ’kへのパスのパス選択フラグｑiは、次のように表される。
【０１４３】
【数２９】
2015039156.tif 000031
即ち、差分Δiの正負が、パス選択フラグｑiの値に対応する。よって、差分Δiの正負
が、推定ビットの値に対応する。
【０１４４】
ステップＳ１０９では、第１要素復号器２３１は、時刻ｔ＝ｉと時刻ｔ＝ｉ＋１との間のブランチを通るパスのうち最尤パスのパスメトリックＬiをブランチ毎に求める。
【０１４５】
時刻ｔ＝ｉで状態ｓを通るパスのうちの最尤パスのメトリックをλi（ｓ）＝αi（ｓ）＋βi（ｓ）とする。第１要素復号器２３１は、トレースバックの開始位置ｉBでの最小のλiBを求め、Ｌminとする。
【０１４６】
【数３０】
2015039156.tif 000032
ここでは、トレリス終端を行っているので、境界での状態ｓは０であり、βの境界条件をβiB（ｓ）＝０とすると、
【０１４７】
【数３１】
2015039156.tif 000033
となる。ここでは、トレースバックの開始位置は、時刻ｔ＝Ｋｔである。Ｌminは、最尤
パスのパスメトリックである。
【０１４８】
第１要素復号器２３１は、λi+1（ｓ’）から、パス選択情報を利用して時刻ｔ＝ｉに
おける状態ｓから時刻ｔ＝ｉ＋１における状態ｓ’へのブランチを含むパスのうちの最尤パスのメトリックを求める。時刻ｔ＝ｉにおける状態ｓ’へのパス選択情報は、Δi（ｓ
’）の符号により得られる。ここで、時刻ｔ＝ｉにおける状態ｓから時刻ｔ＝ｉ＋１における状態ｓ’へのブランチを含むパスのうちの最尤パスのメトリックをＬi（ｓ，ｓ’）
とする。
【０１４９】
ここで、ｑi（ｓ’0）＝０であるとき、
【０１５０】
【数３２】
2015039156.tif 000034
であるから、時刻ｔ＝ｉでブランチ（ｓ1，ｓ’0）を通るパスがブランチ（ｓ0，ｓ’0）を通るパスよりも良いパスとなる。従って、
【０１５１】
【数３３】
2015039156.tif 000035
となる。
【０１５２】
また、同様に、ｑi（ｓ’1）＝０であるとき、
【０１５３】
【数３４】
2015039156.tif 000036
であるから、時刻ｔ＝ｉでブランチ（ｓ0，ｓ’1）を通るパスがブランチ（ｓ1，ｓ’1）を通るパスよりも良いパスとなる。従って、
【０１５４】
【数３５】
2015039156.tif 000037
となる。パスメトリックＬiは、λi+1及びΔiに基づいて算出される。
【０１５５】
一般化すると、ｑi（ｓ’k）＝０であるとき、
【０１５６】
【数３６】
2015039156.tif 000038
となる。
【０１５７】
さらに、同様にして、ｑi（ｓ’k）＝１であるとき、
【０１５８】
【数３７】
2015039156.tif 000039
となる。
【０１５９】
第１要素復号器２３１は、このようにして、時刻ｔ＝ｉと時刻ｔ＝ｉ＋１との間のブランチを通るパスのうち最尤パスのパスメトリックＬiをブランチ毎に算出する。算出され
たパスメトリックＬiは、メモリに格納される。ここで、λi+1（ｓ’k）が存在しない場
合、パスメトリックＬi（ｓ，ｓ’k）は、算出されない。即ち、パスメトリックがＬmin
である最尤パスのパスメトリック及び時刻ｔ＝ｉ以降で当該最尤パスに負けたパスのパスメトリックＬiが、算出される。
【０１６０】
例えば、ｉ＝Ｋｔ−１である場合、状態ｓ’kが０以外であるλi+1（ｓ’k）は、存在
しない。従って、ｉ＝Ｋｔ−１であり、状態ｓ’kが０以外である場合、パスメトリック
Ｌiは、算出されない。
【０１６１】
ステップＳ１１０では、第１要素復号器２３１は、パスメトリックＬiを用いて、λi（ｓ）を算出する。
【０１６２】
第１要素復号器２３１は、Ｌiを利用して、各状態について、次のように、λi（ｓ）を算出する。算出されたλi（ｓ）は、メモリに格納される。これにより、生き残りパス同
士が、トレースバックによって同じ状態に入力する際に、両者のうち最尤パスが選択される。これは、β演算に相当する処理である。
【０１６３】
【数３８】
2015039156.tif 000040
但し、Ｌi（ｓk，ｓ’0）及びＬi（ｓk，ｓ’1）が共に存在しない場合、λi（ｓk）は、算出されない。このとき、λi（ｓk）がメモリに存在しないことになる。
【０１６４】
ステップＳ１１１では、第１要素復号器２３１は、パスメトリックＬiを用いて、事後
尤度Ｌ（ｉ）を算出する。
【０１６５】
第１要素復号器２３１は、Ｌiを利用して、時刻ｔ＝ｉについて、次のように、事後尤
度Ｌ（ｉ）を算出する。算出された事後尤度Ｌ（ｉ）は、メモリに格納される。
【０１６６】
【数３９】
2015039156.tif 000041
ここで、ｂは、ビット値であり、０または１をとる。ｂは、最尤パスの時刻ｔ＝ｉの入力ビット値の対抗ビット値である。Ｂbは、入力ビット値がｂであるブランチの集合であ
る。Ｌ（ｉ）が小さいほど、時刻ｔ＝ｉにおけるブランチの情報ビットが１である確率が高い。第２番目の式におけるＬi（ｓ1，ｓ2）として、少なくとも、時刻ｔ＝ｉ＋１で最
尤パスに負けたパスが含まれる。
【０１６７】
ステップＳ１１２では、第１要素復号器２３１は、変数ｉに（ｉ−１）を代入し、処理がステップＳ１０７に戻る。変数ｉが０未満である場合（Ｓ１０７；ＮＯ）、処理が終了する。
【０１６８】
第１要素復号器２３１は、ｉ＝Ｋｔ−１での終状態０からフラグ情報（パス選択情報）により勝ちパスをたどることで最尤パスを特定することができる。第１要素復号器２３１は、ｉ＝Ｋｔ−１からｉ＝０まで降順に、事後尤度Ｌ（ｉ）が求められる。Ｌ（ｉ）は、次の演算におけるＬe（ｉ）で使用される。Ｌ（ｉ）は、他の要素復号器で使用され得る
。
【０１６９】
動作例１では、第１要素復号器２３１は、Ｍａｘ−Ｌｏｇ−ＭＡＰ方式と同じ尤度演算をＳＯＶＡの演算方式を利用して演算する。ただし、α演算は、バタフライ単位の演算である。ＳＯＶＡにおいては、ビット毎の尤度を更新するための演算として、尤度の差分Δが利用される。バタフライに含まれるブランチ上のローカル符号の対称性を利用することにより、演算が簡単化される。よって、動作例１の方法では、Ｍａｘ−Ｌｏｇ−ＭＡＰ方式と同等の特性が得られる。
【０１７０】
ＳＯＶＡ方式におけるΔの定義は、「勝ちパス」から「負けパス」への増加分である。ここでは、Δの定義は、情報ビットｕ＝０の累積メトリックαと情報ビットｕ＝１の累積メトリックαとの差とする。このΔは、大きさが尤度差に相当しており、正負の符号ビットがｕ＝０，１の勝ち負けに対応するフラグであると解釈できる。このΔによれば、簡潔な式で他方のΔの値を求めることができる。そのため、計算量が削減される。
【０１７１】
（動作例２）
次に動作例２について説明する。動作例２は、動作例１との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。
【０１７２】
ここでは、復号処理部２３０の第１要素復号器２３１の動作例２について説明する。要素復号器２３１には、尤度データｙsと尤度データｙp1（ｙpともいう）とが復調デマッピング処理部から入力される。第１要素復号器２３１は、復号ビットを出力する。第２要素復号器２３２の動作は、第１要素復号器２３１の動作と同様である。
【０１７３】
動作例２では、第１要素復号器２３１は、Ｍａｘ−Ｌｏｇ−ＭＡＰ方式と同様の尤度演
算を、修正ＳＯＶＡ方式を利用して行う。ここでは、ｍｉｎ規約が採用される。
【０１７４】
図１６及び図１７は、動作例２における第１要素復号器２３１の尤度演算の動作フローの例を示す図である。図１６の「Ｂ」は、図１７の「Ｂ」と接続する。
【０１７５】
ステップＳ２０１からステップＳ２０５までの処理は、前方累積メトリック演算（α演算）における処理である。ステップＳ２０１からステップＳ２０５までの処理は、それぞれ、動作例１のステップＳ１０１からステップＳ１０５までの処理と同様である。
【０１７６】
ステップＳ２０６以降は、事後尤度演算（Ｌ演算）における処理である。ｉ＝Ｋｔ−１での状態ｓ＝０（終状態）からフラグ情報（パス選択フラグ）により勝ちパスをたどることで最尤パスが、特定される。最尤パスに対応するフラグ情報は、推定ビット（ｕiのハ
ット）に一致する。
【０１７７】
ステップＳ２０６では、第１要素復号器２３１は、パスフラグを初期化する。
【０１７８】
第１要素復号器２３１は、ｉ＝Ｋｔからｉ＝Ｋｔ−ｍにおいて、時刻ｔ＝ｉと時刻ｔ＝ｉ＋１との間のブランチのブランチメトリックを、終端位置からブランチ毎に求める。ｍは、遅延メモリのサイズである。ここでは、ｍ＝３である。ここでは、時刻ｔ＝Ｋｔで、終端するとする（トレリス終端）。終端位置からｍ（＝３）個のステップで、時刻ｔ＝Ｋｔの状態０からすべての状態（状態０から状態７までの８個の状態）にまで、一意に達するパスを網羅的にたどることができる。時刻ｔ＝Ｋｔの状態０の終端位置から時刻ｔ＝Ｋｔ−ｍの各状態（２m個の状態）までのｍ（＝３）個のブランチのブランチメトリックの
和を、それぞれ、時刻ｔ＝Ｋｔ−ｍの各状態のβの値とする。時刻ｔ＝Ｋｔの状態０から時刻ｔ＝Ｋｔ−ｍ＝Ｋの各状態までのパスは、それぞれ、一意に決まる。
【０１７９】
第１要素復号器２３１は、トレースバックの開始位置ｔ＝ｉB＝Ｋにおける生き残りパ
スをこの時点での候補パスとして、トレースバックする。時刻ｔ＝ｉ、状態ｓでの生き残りパスの有無を示すパスフラグを、Ｆi（ｓ）とする。Ｆi（ｓ）が、１であるとき、時刻ｔ＝ｉ、状態ｓでの生き残りパスが有ることを示す。トレースバック開始位置ｔ＝ｉBに
おけるパスフラグは、次のように表される。第１要素復号器２３１は、パスフラグを、メモリに格納する。
【０１８０】
【数４０】
2015039156.tif 000042
即ち、時刻ｔ＝ｉB＝Ｋでは、すべての状態（状態０から状態７までの８個の状態）に
おいて、生き残りパスが有るとする。ここでは、ｉB＝Ｋ＝Ｋｔ−ｍである。
【０１８１】
また、時刻ｔ＝ｉで状態ｓを通るパスのうちの最尤パスのメトリックをλi（ｓ）＝αi（ｓ）＋βi（ｓ）とする。第１要素復号器２３１は、時刻ｔ＝ｉB＝Ｋの各状態のλiBを求める。第１要素復号器２３１は、トレースバックの開始位置ｉBでの最小のλiBを求め
、Ｌminとする。
【０１８２】
【数４１】
2015039156.tif 000043
ここでは、トレースバックの開始位置は、時刻ｔ＝ｉBである。Ｌminは、最尤パスのパスメトリックである。
【０１８３】
ステップＳ２０７では、第１要素復号器２３１は、変数ｉを用意し、変数ｉに（ｉB−
１）を代入する。
【０１８４】
ステップＳ２０８では、第１要素復号器２３１は、変数ｉが０以上であるか否かを判定する。変数ｉが０以上である場合（Ｓ２０８；ＹＥＳ）、処理がステップＳ２０９に進む。変数ｉが０以上でない場合（Ｓ２０８；ＮＯ）、処理が終了する。
【０１８５】
ステップＳ２０９では、第１要素復号器２３１は、時刻ｔ＝ｉにおける尤度の差分Δi
を算出する。ステップＳ２０９の動作は、動作例１のステップＳ１０８の動作と同様である。
【０１８６】
ステップＳ２１０では、第１要素復号器２３１は、パスフラグを用いて、時刻ｔ＝ｉと時刻ｔ＝ｉ＋１との間のブランチを通るパスのうちの最尤パスのパスメトリックＬiをブ
ランチ毎に求める。即ち、第１要素復号器２３１は、パスフラグＦi+1（ｓ’）が１であ
る時刻ｔ＝ｉ＋１の状態ｓ’を通るパスのうちの最尤パスのメトリックＬiを求める。
【０１８７】
第１要素復号器２３１は、λi+1（ｓ’）から、パス選択情報を利用して時刻ｔ＝ｉに
おける状態ｓから時刻ｔ＝ｉ＋１における状態ｓ’へのブランチを含むパスのうちの最尤パスのメトリックを求める。ここで、パスフラグＦi+1（ｓ’）が０である時刻ｔ＝ｉ＋
１の状態ｓ’を通るパスについては、求められない。時刻ｔ＝ｉにおける時刻ｔ＝ｉ＋１の状態ｓ’へのパス選択情報は、Δi（ｓ’）の符号により得られる。ここで、時刻ｔ＝
ｉの状態ｓから時刻ｔ＝ｉ＋１の状態ｓ’へのブランチを含むパスのうちの最尤パスのメトリックをＬi（ｓ，ｓ’）とする。
【０１８８】
ここで、ｑi（ｓ’k）＝０であるとき、
【０１８９】
【数４２】
2015039156.tif 000044
となる。
【０１９０】
さらに、同様にして、ｑi（ｓ’k）＝１であるとき、
【０１９１】
【数４３】
2015039156.tif 000045
となる。
【０１９２】
第１要素復号器２３１は、このようにして、時刻ｔ＝ｉと時刻ｔ＝ｉ＋１との間のブランチを通るパスのうち最尤パスのパスメトリックＬiを算出する。算出されたパスメトリ
ックＬiは、メモリに格納される。ここで、λi+1（ｓ’k）が存在しない場合、パスメト
リックＬi（ｓ，ｓ’k）は、算出されない。また、Ｆi+1（ｓ’k）＝０である場合、パスメトリックＬi（ｓ，ｓ’k）は、算出されない。即ち、パスメトリックがＬminである最
尤パスのパスメトリック及び時刻ｔ＝ｉ以降で当該最尤パスに負けたパスのパスメトリックＬiが、算出される。
【０１９３】
ステップＳ２１１では、第１要素復号器２３１は、パスメトリックＬiを用いて、λi（ｓ）を算出する。
【０１９４】
第１要素復号器２３１は、Ｌiを利用して、各状態について、次のように、λi（ｓ）を算出する。算出されたλi（ｓ）は、メモリに格納される。これにより、生き残りパス同
士が、トレースバックによって同じ状態に入力する際に、両者のうち最尤パスが選択される。これは、β演算に相当する処理である。
【０１９５】
【数４４】
2015039156.tif 000046
但し、Ｌi（ｓk，ｓ’0）及びＬi（ｓk，ｓ’1）が共に存在しない場合、λi（ｓk）は、算出されない。このとき、λi（ｓk）がメモリに存在しないことになる。
【０１９６】
ステップＳ２１２では、第１要素復号器２３１は、パスメトリックＬiを用いて、事後
尤度Ｌ（ｉ）を算出する。
【０１９７】
第１要素復号器２３１は、Ｌiを利用して、時刻ｔ＝ｉについて、次のように、事後尤
度Ｌ（ｉ）を算出する。算出された事後尤度Ｌ（ｉ）は、メモリに格納される。
【０１９８】
【数４５】
2015039156.tif 000047
ここで、ｂは、ビット値であり、０または１をとる。ｂは、最尤パスの時刻ｔ＝ｉにおけるビット値の反対のビット値（対抗ビット値）である。ここで、パスフラグＦi+1（ｓ
）が１である時刻ｔ＝ｉ＋１の状態ｓを通るパスの最尤パスを、ＳＯＶＡ基本パスという。Ｂbは、ＳＯＶＡ基本パスのうち時刻ｔ＝ｉにおける入力ビット値がｂであるパスの、
時刻ｔ＝ｉと時刻ｔ＝ｉ＋１との間のブランチの集合（最尤パスの対抗パスのブランチの集合）である。ただし、Ｂbに含まれるブランチの数が、所定値Ｃst未満である場合、時
刻ｔ＝ｉにおける入力ビット値が１−ｂであるＳＯＶＡ基本パスに時刻ｔ＝ｉ＋１で負けたパス（負けパスの負けパス）のブランチが、Ｂbに含まれるブランチの数が所定値Ｃst
に達するまで、Ｂbに追加される。時刻ｔ＝ｉにおける入力ビット値が１−ｂであるＳＯ
ＶＡ基本パスに時刻ｔ＝ｉ＋１で負けたパス（負けパスの負けパス）のブランチのうち、Ｂｂに追加されるブランチは、どのように選択されてもよい。以上により、Ｂbに含まれ
るブランチの数は、所定値Ｃst以上になる。即ち、Ｌb（ｉ）は、所定値Ｃst以上のパス
から最尤のものが選択されて求められる。所定値Ｃstは、例えば、演算処理量とシミュレーションによる特性により、決定される。所定値Ｃstは、０以上８（＝２m）以下である
。
【０１９９】
ここで、所定値Ｃstが０である場合、ＳＯＶＡ基本パスに負けたパスが選択されないため、最尤パスの時刻ｔ＝ｉで入力ビット値の対抗ビット値を取るパスうちの最尤パスの選択が、ＳＯＶＡ基本パスに基づいて、実行される。また、所定値Ｃstが８（＝２m）であ
る場合、ＳＯＶＡ基本パスのすべての負けパスも選択対象に含まれるため、最尤パスの時刻ｔ＝ｉで入力ビット値の対抗ビット値を取るパスうちの最尤パスの選択が、修正ＳＯＶＡ基本パスにより、実行される。
【０２００】
Ｌ（ｉ）が小さいほど、時刻ｔ＝ｉにおけるブランチの情報ビットが０である確率が高い。第２番目の式におけるＬi（ｓ1，ｓ2）として、少なくとも、時刻ｔ＝ｉ＋１で最尤
パスに負けたパスが含まれる。
【０２０１】
ステップＳ２１３では、第１要素復号器２３１は、パスフラグを更新する。第１要素復号器２３１は、Ｆi+1（ｓ’）＝１であり時刻ｔ＝ｉと時刻ｔ＝ｉ＋１との間のブランチ
（ｓk，ｓ’）を通るパスがブランチ（ｓ1-k，ｓ’）を通るパスに対する勝ちパスである場合、Ｆi（ｓk）＝１とする。また、他の状態では、Ｆi＝０とする。
【０２０２】
ステップＳ２１４では、第１要素復号器２３１は、変数ｉに（ｉ−１）を代入し、処理がステップＳ２０８に戻る。変数ｉが０未満である場合（Ｓ２０８；ＮＯ）、処理が終了する。
【０２０３】
動作例２では、Ｍａｘ−Ｌｏｇ−ＭＡＰ方式においてＳＯＶＡ方式を取り込むことにより、β演算及びＬ演算が一緒に行われる。また、動作例２では、β演算相当部分において、Ｍａｘ−Ｌｏｇ−ＭＡＰ方式と同様の結果が得られる。さらに、動作例２では、Ｌ演算において、ＳＯＶＡ基本パスをベースとしてパス候補を絞ることにより、演算量が削減される。
【０２０４】
動作例２では、最尤パスの時刻ｔ＝ｉで入力ビット値の対抗ビット値を取るパスうちの最尤パスの選択が、修正ＳＯＶＡ方式の生き残りのパスの候補に基づいて、実行される。所定値Ｃstが８より小さくなることで、Ｌ演算における計算量が減少する。また、所定値Ｃstが０より大きくなることで、Ｌ演算における対抗パスの選択肢を増やすことができ、特性劣化がより抑制される。
【０２０５】
（動作例３）
次に動作例３について説明する。動作例３は、動作例１、動作例２との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。
【０２０６】
動作例２では所定値Ｃstは定数（固定値）であったが、動作例３では所定値Ｃstの代わりに、時刻ｔ＝ｉに依存する値Ｃst（ｉ）が導入される。
【０２０７】
時刻ｔ＝ｉにおけるＣst（ｉ）は、例えば、次のように定義される。
【０２０８】
【数４６】
2015039156.tif 000048
即ち、上記のＣstは、原則Ｃst＝Ｃ1とし、時間ｔ1毎にＣst＝Ｃ2とする。
【０２０９】
このようにすることにより、動作例３では、動作例２で所定値Ｃstを１ずつ変更させるよりも、対抗パスの選択における候補数をより細かく調整することができる。例えば、動作例２において、Ｃstが４のときに特性劣化が大きい場合、対抗パスの選択における候補の数が各時刻において４になる確率が高い。この場合、Ｃstを一律に５にしても特性改善が十分でない可能性がある。一方、原則Ｃst＝４とし、時間４毎にＣst＝８とすることで、尤もらしいパスを選択できるビットの数は増加する。
【０２１０】
ターボ復号処理は、事後尤度をフィードバックして繰り返す復号処理であるため、よりよい尤度の数が多いほど最終的な特性がよくなる。
【０２１１】
また、上記のように周期的にＣstを変更することで、不規則に変更する場合に比べて、切り替える処理が簡単になる。
【０２１２】
（実施形態１の作用、効果）
本実施形態の第１要素復号器２３１は、前方累積メトリックの算出の際に、再計算用のデータとして、前方累積メトリックの差分Δをメモリに保存する。１つのバタフライに対して、１つの差分Δが保存される。メモリに保存されない差分Δは、メモリに保存された差分Δから容易に求められる。差分Δの正負が、推定ビットの値に対応する。第１要素復号器２３１によれば、バタフライに含まれるブランチ上のローカル符号の対称性を利用することにより、演算量（処理量）を削減することができる。
【０２１３】
ここで、要素復号器の演算における処理量を求める。ここでは、１情報ビットあたりの加減算、及び、比較演算をそれぞれウェイト１の処理量としてカウントする。従来のＭａｘ−Ｌｏｇ−ＭＡＰ方式では、α演算における、加減算で１９、比較演算で８、β演算及びＬ演算における、加減算で３１、比較演算で１５の、合計７２の処理量である。これに対し、本実施形態の方法では、α演算における、加減算で１５、比較演算で８、Ｌ演算（β演算相当を含む）における、加減算で１５、比較演算で１３の、合計５０の処理量である。従って、本実施形態の方法では、Ｍａｘ−Ｌｏｇ−ＭＡＰ方式と比べて、１−５０／７２＝３１％の処理量が削減される。
【０２１４】
図１５は、特性のシミュレーション結果の例を示す図である。図１５の横軸は、信号対雑音電力比である。縦軸は、ＢＬＥＲの対数表示である。図１５では、従来のＭａｘ−Ｌｏｇ−ＭＡＰ方式、動作例１の方法、動作例２の方法、従来の修正ＳＯＶＡ方式の特性のシミュレーション結果の例が示される。図１５のグラフでは、ＢＬＥＲが小さいほど、精度がよいことを示す。本実施形態の動作例１および動作例２の方法の特性は、従来のＭａｘ−Ｌｏｇ−ＭＡＰ方式と同様である。
【０２１５】
従って、本実施形態の方法はＭａｘ−Ｌｏｇ−ＭＡＰ方式と同様の特性を有し、Ｍａｘ−Ｌｏｇ−ＭＡＰ方式と比べて演算処理量が少ない。
【０２１６】
〔実施形態２〕
（構成例）
次に実施形態２について説明する。実施形態２は、実施形態１との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。
【０２１７】
本実施形態では、実施形態１と並列ＭＡＰ方式とを組み合わせる。ここでは、並列数をＭとして、入力される情報ビット系列がＭ個に分割される。情報ビット系列の分割では、それぞれが極力同じサイズになるように分割される。ここでは、情報ビット系列が分割数Ｍで割り切れるとする。分割された小ブロックを、サブブロックと呼ぶ。サブブロック毎のＭＡＰ処理を並列に処理することで、処理遅延を１／Ｍにして処理を高速化する。この
とき、各サブブロックに対してのＭＡＰ処理において、α演算、β演算を、途中のビット位置から開始することになる。
【０２１８】
本実施形態の通信システムの構成は、実施形態１と同様である。本実施形態は、実施形態１と復号演算部における第１要素復号器及び第２要素復号器の内部が異なる。
【０２１９】
図１８は、本実施形態における復号処理部の構成例を示す図である。本実施形態における復号演算部を、復号演算部２４０とする。図１８の復号処理部２４０は、第１要素復号器２４１、第２要素復号器２４２、インタリーバ（ＩＬ）２４３、デインタリーバ（ＤｅＩＬ）２４４を含む。
【０２２０】
第１要素復号器２４１は、尤度データｙｓ、尤度データｙｐ１、第２要素復号器２４２の出力データ等を用いて、サブブロック毎に並列に復号ビットを算出する。第２要素復号器２４２は、尤度データｙｓ、尤度データｙｐ２、第１要素復号器２４１の出力データ等を用いて、サブブロック毎に並列に復号ビットを算出する。インタリーバ２４３は、尤度データｙｓ、第１要素復号器２４１の出力データの順序を入れ替え、入れ替えたデータを第２要素復号器２４２に出力する。デインタリーバ２４４は、第２要素復号器２４２の出力データの順序を入れ替え、入れ替えたデータを第１要素復号器２４１に出力する。また、デインタリーバ２４４は、第２要素復号器２４２の出力データの順序を入れ替え、入れ替えたデータを復号ビットとして出力する。第１要素復号器２４１及び第２要素復号器２４２は、互いに同様の構成を有する。
【０２２１】
図１９は、第１要素復号器２４１の構成例を示す図である。第１要素復号器２４１は、第１並列ＭＡＰ演算部２５１−１、第２並列ＭＡＰ演算部２５１−２、・・・、第Ｍ並列ＭＡＰ演算部２５１−Ｍ、Ｌｅ演算部２５２を含む。
【０２２２】
各並列ＭＡＰ演算部は、同様の構成を有する。ここでは、代表して、並列ＭＡＰ演算部２５１と表記する。
【０２２３】
並列ＭＡＰ演算部２５１は、それぞれ、実施形態１の第１要素復号器２３１と同様の構成を有する。並列ＭＡＰ演算部２５１には、それぞれに、情報ビット系列（尤度データ）がＭ個に分割されたサブブロックの１つが入力される。並列ＭＡＰ演算部２５１には、それぞれに、すべての情報ビット系列が入力されて、各並列ＭＡＰ演算部２５１が、演算で使用するデータを抽出してもよい。並列ＭＡＰ演算部２５１は、それぞれ、実施形態１の第１要素復号器２３１と同様に動作する。
【０２２４】
Ｌｅ演算部２５２は、各並列ＭＡＰ演算部２５１で算出されたパスメトリックを用いて、最尤パスと対抗パスとのパスメトリックの差であるＬ（ｉ）を算出し、フィードバック尤度データ又は出力尤度データとして出力する。フィードバック尤度データは、並列ＭＡＰ演算部２５１に、事前尤度として入力される。出力尤度データは、第２要素復号器２４２等に向けて出力される。
【０２２５】
（動作例４）
動作例４は、実施形態１の動作例１、動作例２、動作例３との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。
【０２２６】
並列ＭＡＰ演算部２５１の処理において、α演算、β演算を、情報ビット系列の途中のビット位置から開始することになる。このとき、隣接するサブブロックとの境界位置の前方累積メトリックα、及び、後方累積メトリックβが、使用される。情報ビット系列の先頭及び最後では、実施形態１と同様に、前方累積メトリックα、及び、後方累積メトリッ
クβが得られる。並列ＭＡＰ演算部２５１は、演算において、初期値としての、隣接するサブブロックとの境界位置での、前方累積メトリックα、及び、後方累積メトリックβを、次のいずれかのようにして得る。
【０２２７】
（１）トレーニング法
並列ＭＡＰ演算部２５１は、α演算（β演算）において、境界位置に対して所定のサイズ前（後）から境界位置までの累積尤度を求め、この値を境界位置での前方累積メトリックα（後方累積メトリックβ）とする。
【０２２８】
（２）確率伝搬法（ＢＰ（Belief Propagation）法）
並列ＭＡＰ演算部２５１は、繰り返し処理による前回の繰り返しにおいて、境界位置での前方累積メトリックα及び後方累積メトリックβを保存しておく。並列ＭＡＰ演算部２５１は、保存しておいた境界位置での前方累積メトリックα及び後方累積メトリックβを境界位置での初期値として使用する。
【０２２９】
境界位置での各状態における最尤パス（生き残りパス）のパスメトリックは、（１）、（２）又はこれらの組み合わせにより使用される初期値が求められて、これらのαとβとの和によって求められる。また、境界位置でのαまたはβを使用して、各並列ＭＡＰ演算部２５１における演算が、実施形態１と同様に行われる。
【０２３０】
（動作例５）
動作例５は、動作例４、実施形態１の動作例１、動作例２、動作例３との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。
【０２３１】
ここでは、境界位置での初期化（パスグラフ初期化）が、次のように行われる。
【０２３２】
境界位置での生き残りパスの数をＮB＝２nbとする。境界位置（時刻ｔ＝ｉB）において、各状態からトレースバックされるパスのメトリックλi（ｓ）＝αi（ｓ）＋βi（ｓ）
（ｓ＝０，・・・，７）について、状態値のペア（ｓ0，ｓ1）＝（２ｋ，２ｋ＋１）に関して、大小比較を行う。小さい方のパスを生き残りパスとみなして、パスフラグを立てる。
【０２３３】
【数４７】
2015039156.tif 000049
ｎｂ＝２の場合、この時点での生き残りパスを初期の状態としてパスフラグを立てる。
【０２３４】
【数４８】
2015039156.tif 000050
ｎｂ＝１の場合、さらに、ｋ＝０，１及びｋ＝２，３の組み合わせで、大小比較を行い、メトリックが小さい方を生き残りパスとしてフラグを立てる。
【０２３５】
ｎｂ＝０の場合、ｎｂ＝１の場合に残った２つに対して大小比較を行い、小さい方を生き残りパスとする。これは、最尤パスに対してのトレースバックを開始する境界位置での状態を特定したことに一致する。
【０２３６】
境界位置での生き残りのパスの数を制限することで、演算処理量が削減される。
【０２３７】
（実施形態２の作用、効果）
本実施形態の要素復号器２４１は、複数の並列ＭＡＰ演算部２５１により、並列して復号処理を行う。要素復号器２４１によれば、並列して復号処理を行うことにより、処理時間が削減される。
【０２３８】
以上の各実施形態は、可能な限りこれらを組み合わせて実施され得る。
【０２３９】
〔付記〕
上記の各実施形態に関し、以下の付記を開示する。
（付記１）
開始時刻と終了時刻との間の各時刻の事後尤度を算出する復号化装置であって、
受信尤度データ及び事前尤度に基づいて第１時刻と前記第１時刻の次の時刻である第２時刻との間のブランチのブランチメトリックを算出し、前記第１時刻の第１状態及び第２状態と前記第２時刻の第３状態及び第４状態とで表されるバタフライにおける状態遷移において、前記第１状態の第１前方累積メトリックと、前記第２状態の第２前方累積メトリックと、前記第１時刻の第１状態と前記第２時刻の第３状態との間の前記ブランチメトリック及び前記第１状態の第１前方累積メトリックと前記第２状態の第２前方累積メトリックとの間の差分である第１差分に基づく第２差分とに基づいて、前記第３状態の第３前方累積メトリックと、前記第４状態の第４前方累積メトリックとを、バタフライ毎及び時刻毎に算出する演算部と、
前記第２差分を、バタフライ毎及び時刻毎に格納する記憶部と、
を備える復号化装置。
（付記２）
前記演算部は、前記終了時刻における前方累積メトリックを最尤パスのパスメトリックとし、前記最尤パスのパスメトリックと各時刻の各バタフライにおける前記第２差分とに基づいて、各状態の最尤のパスメトリックを時刻毎に算出し、各時刻において、前記最尤パスの推定ビットを前記第２差分の符号に基づいて算出し、各時刻において、前記最尤パスの推定ビットの反対ビットを含むパスのパスメトリックのうち最尤のもの及び前記最尤パスのパスメトリックに基づいて事後尤度を算出する、
付記１に記載の復号化装置。
（付記３）
前記演算部は、前記終了時刻における前方累積メトリックを最尤パスのパスメトリックとし、前記最尤パスのパスメトリックと各時刻の各バタフライにおける前記第２差分とに基づいて、各状態の最尤のパスメトリックを時刻毎に算出し、各時刻において、前記最尤パスの推定ビットを前記第２差分の符号に基づいて算出し、各時刻において、前記最尤パスの推定ビットの反対ビットを含むパスのパスメトリックであって前記最尤パスに負けたパスのパスメトリックのうち最尤のもの及び前記最尤パスのパスメトリックに基づいて事後尤度を算出する、
付記１に記載の復号化装置。
（付記４）
前記演算部は、前記最尤パスの推定ビットの反対ビットを含むパスであって前記最尤パスに負けたパスの数が前記所定数未満である場合、前記最尤パスの推定ビットの反対ビットを含むパスであって前記最尤パスに負けたパスに負けたパスを前記所定数に達するまで抽出し、当該抽出したパスのパスメトリックと前記最尤パスに負けたパスのパスメトリックのうち最尤のもの及び前記最尤パスのパスメトリックに基づいて事後尤度を算出する
付記３に記載の復号化装置。
（付記５）
前記所定数は、時刻ごとに可変である
付記４に記載の復号化装置。
（付記６）
前記所定数は、周期的に変化する、
付記４に記載の復号化装置。
（付記７）
記憶部を有し、開始時刻と終了時刻との間の各時刻の事後尤度を算出する復号化装置において、
受信尤度データ及び事前尤度に基づいて第１時刻と前記第１時刻の次の時刻である第２時刻との間のブランチのブランチメトリックを算出し、前記第１時刻の第１状態及び第２状態と前記第２時刻の第３状態及び第４状態とで表されるバタフライにおける状態遷移において、前記第１状態の第１前方累積メトリックと、前記第２状態の第２前方累積メトリックと、前記第１時刻の第１状態と前記第２時刻の第３状態との間の前記ブランチメトリック及び前記第１状態の第１前方累積メトリックと前記第２状態の第２前方累積メトリックとの間の差分である第１差分に基づく第２差分とに基づいて、前記第３状態の第３前方累積メトリックと、前記第４状態の第４前方累積メトリックとを、バタフライ毎及び時刻毎に算出し、
前記第２差分を、バタフライ毎及び時刻毎に前記記憶部に格納する、
復号化方法。
（付記８）
前記終了時刻における前方累積メトリックを最尤パスのパスメトリックとし、前記最尤パスのパスメトリックと各時刻の各バタフライにおける前記第２差分とに基づいて、各状態の最尤のパスメトリックを時刻毎に算出し、各時刻において、前記最尤パスの推定ビットを前記第２差分の符号に基づいて算出し、各時刻において、前記最尤パスの推定ビットの反対ビットを含むパスのパスメトリックのうち最尤のもの及び前記最尤パスのパスメトリックに基づいて事後尤度を算出する、
付記７に記載の復号化方法。
（付記９）
前記終了時刻における前方累積メトリックを最尤パスのパスメトリックとし、前記最尤パスのパスメトリックと各時刻の各バタフライにおける前記第２差分とに基づいて、各状態の最尤のパスメトリックを時刻毎に算出し、各時刻において、前記最尤パスの推定ビットを前記第２差分の符号に基づいて算出し、各時刻において、前記最尤パスの推定ビットの反対ビットを含むパスのパスメトリックであって前記最尤パスに負けたパスのパスメトリックのうち最尤のもの及び前記最尤パスのパスメトリックに基づいて事後尤度を算出する、
付記７に記載の復号化方法。
（付記１０）
前記最尤パスの推定ビットの反対ビットを含むパスであって前記最尤パスに負けたパスの数が前記所定数未満である場合、前記最尤パスの推定ビットの反対ビットを含むパスであって前記最尤パスに負けたパスに負けたパスを前記所定数に達するまで抽出し、当該抽出したパスのパスメトリックと前記最尤パスに負けたパスのパスメトリックのうち最尤のもの及び前記最尤パスのパスメトリックに基づいて事後尤度を算出する
付記９に記載の復号化方法。
（付記１１）
前記所定数は、時刻ごとに可変である
付記１０に記載の復号化方法。
（付記１２）
前記所定数は、周期的に変化する、
付記１０に記載の復号化方法。
【符号の説明】
【０２４０】
１０              通信システム
１００                送信装置
１１０                  符号化処理部
１１１                    第１要素符号化部
１１２                    第２要素符号化部
１１３                    インタリーバ（ＩＬ）
１１４                    パラレルシリアル変換部（Ｐ／Ｓ）
１２０                  変調マッピング処理部
１３０                  送信処理部
１８２                  プロセッサ
１８４                  記憶装置
１８６                  ベースバンド処理回路
１８８                  無線処理回路
１９０                  アンテナ
２００                受信装置
２１０                  受信処理部
２２０                  復調デマッピング処理部
２３０                  復号処理部
２３１                    第１要素復号器
２３２                    第２要素復号器
２３３                    インタリーバ（ＩＬ）
２３４                    デインタリーバ（ＤｅＩＬ）
２８２                  プロセッサ
２８４                  記憶装置
２８６                  ベースバンド処理回路
２８８                  無線処理回路
２９０                  アンテナ
【図１】
2015039156.tif 000051
【図２】
2015039156.tif 000052
【図３】
2015039156.tif 000053
【図４】
2015039156.tif 000054
【図５】
2015039156.tif 000055
【図６】
2015039156.tif 000056
【図７】
2015039156.tif 000057
【図８】
2015039156.tif 000058
【図９】
2015039156.tif 000059
【図１０】
2015039156.tif 000060
【図１１】
2015039156.tif 000061
【図１２】
2015039156.tif 000062
【図１３】
2015039156.tif 000063
【図１４】
2015039156.tif 000064
【図１５】
2015039156.tif 000065
【図１６】
2015039156.tif 000066
【図１７】
2015039156.tif 000067
【図１８】
2015039156.tif 000068
【図１９】
2015039156.tif 000069