JP3854155B2 - 待ち時間を短くしたソフトイン／ソフトアウトモジュール - Google Patents

Description

【０００１】
関連する出願
本願は、２０００年３月３日付けで出願された米国仮特許願第６０／２０１，５８３号の特典を主張するものである。なおこの仮特許願は本願に援用するものである。
【０００２】
発明の起源
本願に記載されている研究と開発は、援助番号：ＮＣＲ−ＣＣＲ−９７２６３９１に基づいて全米科学財団によって援助を受けたものである。米国政府は本願発明に特定の権利を有している。
【０００３】
発明の技術分野
本願には、連結符号（concatenated code）を、反復検出するか又は復号する技法が記載されている。さらに具体的に述べると、本願は、例えばターボ復号器で用いられるような、有限状態機械（すなわちソフトイン／ソフトアウトモジュールすなわち「ＳＩＳＯ」モジュール）のソフトインバースを計算することに関する。
【０００４】
背景
通信チャネルにはノイズが存在するので、受信信号は発信信号と必ずしも同一ではない。チャネル符号化又は等しく誤り訂正符号化は、通信システムの受信機が送られたデータ流の組成（composition）を正しく検出できる確率を高める方法に関連している。一般に、このことは、信号を発信する前に符号化して冗長性を加えることによって達成される。この冗長性によって、受信機が符号化された信号を正しく復号して元のデータを回復できる可能性が高まる。
【０００５】
ターボ符号化法は、比較的新しいが広く利用されているチャネル符号化法であり、可能な理論的限界に近い電力効率で発信している。ターボ符号の特徴としては、並列符号連結、不均一インタリービング及び反復復号がある。ターボ符号は、エネルギー効率を大きく改善することができるので、電力及び／又は干渉（interference）が限定されているチャネルに使用するのに魅力がある。
【０００６】
ターボ復号器を使用してターボ符号を復号することができる。そのターボ復号器は、反復方式で協働する二つのソフトインプット／ソフトアウトプット（ＳＩＳＯ）復号モジュールを備えていてもよい。そのＳＩＳＯ復号モジュールは、有限状態機械のネットワークを有するシステム又はより一般的にいえばサブシステムに対して樹立された反復検出法に用いる基本的な構築ブロックである。
【０００７】
図７Ａと７Ｂはそれぞれ、典型的なターボ符号器１０とターボ復号器１１の構成のブロック図を示す。この実施例では、ターボ符号器１０は、二つの別個の符号器ＲＳＣ１とＲＳＣ２を利用し、これらは各々、再帰的組織畳みこみ符号器（Recursive Systematic Convolutional encoder）である。これら符号器ＲＳＣ１とＲＳＣ２は、各々、特定数の状態（ターボ符号器に対して一般に四つ又は八つ）及びそれら状態間の遷移（transition）を有する有限状態機械（ＦＳＭ）としてモデル化することができる。ビットストリームを符号化してチャネルで伝送するために、未符号化データビットｂ_ｋを第一符号器ＲＳＣ１とインタリーバＩの両者に入力する。そのインタリーバＩは、該入力されたシーケンスｂ_ｋをシャッフルしてランダムネスを増大して、該シャッフルされたシーケンスａ_ｋを第二復号器ＲＳＣ２に導く。符号器ＲＳＣ１とＲＳＣ２それぞれの出力ｃ_ｋとｄ_ｋは、ブロックによってパンクチャ（puncture）され変調されて符号化された出力ｘ_ｋ（０）とｘ_ｋ（１）が生成し、これら出力はチャネルによって復号器１１に送られる。
【０００８】
復号器１１に、該符号化された出力は、ノイズのある入力ｚ_ｋ（０）及びｚ_ｋ（１）として受け入れられ次にパンクチャ及び変調のブロック１２のソフトインバース（soft-inverse）であるブロック１３によって復調され次いでデ・パンクチャ（de-puncture）される。ブロック１３の出力：Ｍ［ｃ_ｋ（０）］、Ｍ［ｃ_ｋ（１）］及びＭ［ｄ_ｋ（１）］は、「ソフト」情報であり、すなわち、これら情報はそれぞれ、該符号化されたシーケンスｃ_ｋ（０）、ｃ_ｋ（１）及びｄ_ｋ（１）で送られた情報ビットの最も適当なシーケンスについての推定又は信念（guess or belief）である。その復号プロセスは、受け取られたソフト情報Ｍ［ｃ_ｋ（０）］、Ｍ［ｃ_ｋ（１）］を第一復号器ＳＩＳＯに送ることによって続き、その復号器は送られた情報を推定してソフト出力Ｍ［ｂ_ｋ］を生成し、そのソフト出力をインタリーバＩ（符号器１０のインタリーバＩと同じインタリービングマップを利用する）に送ってＭ［ａ_ｋ］を生成させる。第二復号器ＳＩＳＯ２は、Ｍ［ａ_ｋ］と受け取ったソフト情報Ｍ［ｄ_ｋ（１）］を使用してその情報を再推定する。この第二推定は、インタリーバのソフトインバースＩ^−１によってＳＩＳＯ１にループバックされそのＳＩＳＯ１で推定プロセスが再び始まる。その反復プロセスは特定の条件が満たされるまで、例えば、特定回数反復されて、その時点で最終のソフト推定が伝送された情報を示す「ハード」出力になるまで続く。
【０００９】
復号器１１内のＳＩＳＯ復号器モジュールは各々、符号器１０内のそのカウンタパートＲＳＣ符号器のソフトインバースである。ソフトインバースを計算する従来のアルゴリズムは「順方向−逆方向」アルゴリズムとして知られており、例えばG. David Forney、Jr.「The Forward-Backward Algorithm」、Proceedings of the 34^th Allerton Conference on Communications、Control and Computing、４３２〜４４６頁１９９６年１０月に記載されている。その順方向−逆方向アルゴリズムでは、データビットの値の推定は、ＳＩＳＯの「トレリス（trellis）」、特に、ＦＳＭの状態間の可能なすべての遷移を示す展開状態図（unfolded state diagram）によって順方向と逆方向の最小コスト経路を再帰的に計算する（加算−比較−選択操作すなわちＡＣＳ操作を利用して）ことによって行われる。ＳＩＳＯのトレリスによる各経路は、受け取るノイズのある入力に基づいた対応するコストがかかり、ＲＳＣが、データを符号化するときそのトレリスを通る特定の経路をとる可能性を示す。一般に、経路の全コストが低ければ低いほど、ＲＳＣが、データを符号化する際、対応する遷移をする確率が高くなる。一般に、ＳＩＳＯによって実行される順方向と逆方向のＡＣＳの再帰は、直列又は並列で計算することができる。並列で再帰を行うと、これら二つの方法のうち速いほうの方法が、待ち時間（latency）がＯ（Ｎ）（但しＮは符号化されたデータのブロックサイズである）のアーキテクチャが生成する。用語「待ち時間」は本願で使用する場合、Ｎビットのブロックを復号するための終点間（end-to-end）遅延を意味する。
【００１０】
本発明の発明者らは、復号器又は他の検出システムの他の要素の待ち時間によって、ＳＩＳＯの待ち時間を減らすとそのシステムの処理量（システムのアーキテクチャが処理できる一秒当りビット数の大きさ）が有意に改善できることを見出した。その結果、本発明の発明者らは、待ち時間を減らすことができる木構造化ＳＩＳＯ（tree-structured SISO）を開発した。
【００１１】
要約
上記木構造化ＳＩＳＯの実施態様としては、下記機構の各種組合せがある。
【００１２】
一面において、符号化された信号（例えばターボ符号化信号、ブロック符号化信号など）の復号は、例えば無線通信システムで、受信した符号化信号を復調してソフト情報（soft information）を生成させ次にそのソフト情報を、１又は２以上のソフト−イン／ソフト−アウトプット（SISO）モジュールで繰返し処理することによって行うことができる。それらＳＩＳＯモジュールのうちの少なくとも一つが、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うように構成された木構造を利用して、順方向と逆方向の状態メトリクス（forward and backward state metrics）を、例えば再帰的マージナライゼーション結合演算（recursive marginalization-combining operation）を実施することによって計算する。なおその演算は、各種の実施態様で、ｍｉｎ−ｓｕｍ演算、ｍｉｎ^＊−ｓｕｍ演算［但しｍｉｎ^＊＝ｍｉｎ（ｘ、ｙ）−ｌｎ（１＋ｅ^{−｜ｘ−ｙ｜}）］、ｓｕｍ−ｐｒｏｄｕｃｔ演算及び／又はｍａｘ−ｐｒｏｄｕｃｔ演算を含んでいる。
【００１３】
上記符号化信号は、ターボ符号化信号、ブロックターボ符号化信号、低密度パリティチェック符号化信号、積符号化信号（product coded signal）、畳みこみ符号化信号（convolutional coded signal）、並列連結畳みこみ符号化信号、及び／又は直列連結畳みこみ符号化信号のうちの少なくとも一つを含んでいてもよい。
【００１４】
上記反復処理は、予め定められた状態が起こったとき、例えば予め定められた数の反復を完了したときに停止させることができる。その反復処理には、該ソフト情報に対する並列プレフィックス演算又は並列サフィックス演算又はその両者が含まれていてもよい、さらに、その反復処理には、第一ＳＩＳＯのソフト出力を、もう一つのＳＩＳＯへのソフト入力として使用すること及び／又は該ソフト情報上にセミリング（semi-ring）を形成するマージナライゼーション結合演算を行うことが含まれていてもよい。
【００１５】
少なくとも一つのＳＩＳＯが使用する木構造は、待ち時間がＯ（ｌｏｇ_２Ｎ）（但しＮはブロックサイズである）のＳＩＳＯをもたらす木構造、Ｂｒｅｎｔ−Ｋｕｎｇの木、又は例えば二方向性の木構造再帰（tree structure recursion）を有する順方向−逆方向の木でもよい。
【００１６】
少なくとも一つのＳＩＳＯが実行する処理は、観測インターバル（observation interval）を、サブインターバル（subinterval）中にタイルし（tile）、次いで、各サブインターバルに対し、最小ハーフウィンドウＳＩＳＯ演算を適用することを含んでいてもよい。
【００１７】
別の側面で、ＳＩＳＯモジュールは、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うための木構造中に配置されて、順方向と逆方向の状態メトリクスを計算するように構成された複数の融合モジュール（fusion module）を含んでいてもよい。各融合モジュールは下記式で定義することができる。
【００１８】
【数２】

式中、Ｃ（ｋ、ｍ）は、Ｓ_ｋとＳ_ｍの間のソフト入力に基づいた状態ペア（state pair）Ｓ_ｋとＳ_ｍの最小シーケンスメトリクス（ＭＳＭ）のマトリックスである。それら融合モジュールのうち少なくとも一つが、再帰的マージナライゼーション結合演算を実施することによって、順方向と逆方向の状態メトリクスを計算することができる。
【００１９】
別の側面で、ＳＩＳＯモジュールは、順方向と逆方向の両方のマージナライゼーション結合演算を行う１又は２以上の完全融合モジュール（ＣＦＭ）、順方向のみのマージナライゼーション結合演算を行う１又は２以上の順方向融合モジュール（ｆＦＭ）、及び逆方向のみのマージナライゼーション結合演算を行う１又は２以上の逆方向融合モジュール（ｂＦＭ）を含んでいてもよい。上記１又は２以上のＣＦＭ、ｆＦＭ及びｂＦＭは、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うための木構造（例えばＢｒｅｎｔ−Ｋｕｎｇの木、順方向−逆方向の木）中に配置される。ＣＦＭの数は、ソフト−インバース（soft-inverse）を計算するのに必要な最少数に設定される。一般に、ｆＦＭとｂＦＭは、可能なときはいつでも、ＣＦＭの代わりに木構造中で使用できる。
【００２０】
別の側面で、反復検出は、有限状態機械（ＦＳＭ）の１つ又は２以上の出力に対応する入力信号（例えばターボ符号化信号又は畳みこみ符号化信号）を受信し、次に、その受信した入力信号の順方向と逆方向の状態メトリクスを、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うように構成された木構造を利用して計算することによってＦＳＭのソフトインバースを求めることを含んでいてもよい。その順方向と逆方向の状態メトリクスは、１又は２以上のＳＩＳＯモジュールによって、例えばマージナライゼーション結合演算の木構造化セットを使用して、計算することができる。
【００２１】
ＦＳＭのソフトインバースを求めることには、例えばソフト情報に対して、並列プレフィックス演算又は並列サフィックス演算又はその両者を実施して、ソフト情報を反復処理することが含まれていてもよい。さらに、その反復処理は、第一ＳＩＳＯのソフト出力をもう一つのＳＩＳＯへのソフト入力として使用することを含んでいてもよい。少なくとも一つのＳＩＳＯは、さらに、観測インターバルをサブインターバル中にタイルし、次に、各サブインターバルに最小ハーフウィンドウＳＩＳＯ演算を適用することができる。
【００２２】
別の側面で、ターボ復号器は、ＦＳＭが符号化した信号を入力として受信してその受信した信号に関連するソフト情報を生成するよう構成された復調器、及びその復調器と交信し、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うように構成された木構造を使用してＦＳＭのソフトインバースを計算するよう構成された少なくとも一つのＳＩＳＯモジュールを備えている。その木構造は、並列プレフィックス演算と並列サフィックス演算を組み合わせて実行できる。
【００２３】
該ターボ復号器は、互いに交信する少なくとも二つのＳＩＳＯモジュールを備えていてもよい。その場合、そのＳＩＳＯモジュールは、該復号された信号のソフト情報の推定を繰返し交換することができる。いずれの場合も、少なくとも一つのＳＩＳＯは、該受信信号の順方向と逆方向の状態メトリクスを計算することによってＦＳＭのソフトインバースを計算することができる。
【００２４】
別の側面において、反復検出は、１又は２以上のブロック符号化モジュールからの出力に対応する入力信号を受信し、次に、その受信した入力信号の順方向と逆方向の状態メトリクスを、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うように構成された木構造を使用して計算することによって１又は２以上のブロック符号化モジュールのソフトインバースを求めることによって実施できる。該入力信号は、ブロックターボ符号化信号、低密度パリティチェック符号化信号及び／又は積符号化信号を含んでいてもよい。
【００２５】
ブロック符号化モジュールのソフトインバースを求めることには、ソフト情報を反復処理すること例えばソフト情報に対して並列プレフィックス演算又は並列サフィックス演算又はこれら両者を実施することを含んでいてもよい。
【００２６】
別の側面で、ブロック復号器は、ブロック符号化モジュールによって符号化された信号を入力として受信してその受信信号に関連するソフト情報を生成するように構成された復調器、及びその復調器と交信しかつ該ブロック符号化モジュールのソフトインバースを、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うように構成された木構造を使って計算するように構成された少なくとも一つのＳＩＳＯモジュールを備えていてもよい。使用される木構造は、並列プレフィックス演算と並列サフィックス演算を組み合わせて実行することができる。該ブロック復号器はさらに、互いに交信しそして復号された信号のソフト情報推定を反復交換する少なくとも二つのＳＩＳＯモジュールを含んでいてもよい。いずれの場合も、少なくとも一つのＳＩＳＯは、受信した信号の順方向と逆方向の状態メトリクスを計算することによって、ブロック符号化モジュールのソフトインバースを計算することができる。
【００２７】
別の側面で、反復検出は、モジュールの１又は２以上の出力に対応する入力信号（例えばブロック誤り訂正符号化信号、ブロックターボ符号化信号、低密度パリティチェック符号化信号、及び／又は積符号化信号）を受信し［そのモジュールのソフトインバースは、そのモジュール（例えばＦＳＭ又はブロック符号化モジュール）のトレリス表現に対し順方向−逆方向のアルゴリズムを実行することによって計算することができる］、次いで該入力信号の順方向と逆方向の状態メトリクスを、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うように構成された木構造を使用して計算することによって該モジュールのソフトインバースを求めることを含んでいてもよい。
【００２８】
以下の利点の１又は２以上を提供することができる。ここで述べる技術と方法は、並列で順方向と逆方向の再帰を実行し、待ち時間がＯ（Ｎ）の従来のＳＩＳＯとは対照的に、待ち時間をＯ（ｌｇＮ）（但しＮはブロックサイズでありそして「ｌｇ」はｌｏｇ_２を意味する）と短くできる木構造のＳＩＳＯモジュールをもたらす。待ち時間は、主としてチップ面積（chip area）を犠牲にすることによって短くなり、場合によっては計算量がごくわずか増大することがある。この木構造ＳＩＳＯを使用して処理量が非常に大きいターボ復号器すなわちより一般的に述べれば反復検出器を設計することができる。また、各種のサブウインドウイング（sub-windowing）方式及びタイリング方式を使用して、待ち時間をさらに改善することもできる。
【００２９】
これら待ち時間を短くしたＳＩＳＯは、順方向−逆方向アルゴリズムをトレリスに対し実行することが望ましいか又は必要な事実上どんな環境でも使用できる。例えば、この木−ＳＩＳＯは、無線通信及び多くのタイプの復号［ターボ復号、ブロックターボ復号、並列連結畳みこみ符号と直列連結畳みこみ符号の両者を含む畳みこみ符号化、低密度パリティチェック（ＬＤＰＣ）符号、積符号及びより一般的に述べると反復検出時の符号を含むパリティチェック符号化］に用途がある。この待ち時間を短くしたＳＩＳＯは、比較的少数の状態を有するＦＳＭ例えば、一般に４個又は８個の状態を有するターボ符号ＦＳＭを復号するのに利用するとき、特に有利である。
【００３０】
１又は２以上の実施態様の詳細を、添付図面と以下の説明で述べる。本発明の他の特徴、目的及び利点は、本願の説明と図面及び特許請求の範囲から明らかになるであろう。
【００３１】
詳細な説明
本発明の発明者らは、プレフィックス演算とサフィックス演算の組合せを利用して、標準ＳＩＳＯ計算の再公式化法（re-formulation）を開発した。このアーキテクチャ（木−ＳＩＳＯと呼称される）は、高速加算器などの超大規模集積回路（ＶＬＳＩ）の用途に使用される高速並列プレフィックス計算用の木構造に基づいている。この木−ＳＩＳＯと各種の別の実施態様の詳細を以下に述べる。
【００３２】
有限状態機械（ＦＳＭ）の「ソフトインバース」を計算することが、多くのデータ検出／復号のアルゴリズムの重要な演算である。より一般的な用途の一つは、例えばBerrouら、「Near Shannon limit error-correcting coding and decoding: turbo-codes」、International Conference on Communications、（スイス、ジュネーブ）、１０６４〜１０７０頁１９９３年５月、及びBerrouら、「Near optimum error correcting coding and decoding: turbo-codes」、IEEE Trans. Commun.４４巻１２６１〜１２７１頁１９９６年１０月に記載されているターボ符号のような連結復号の反復復号である。しかし、ＳＩＳＯ（ソフトイン／ソフトアウト）モジュールは、反復的及び非反復的の受信器並びに信号処理装置に広く適用することができる。また、ＳＩＳＯが生成するソフト出力は、しきい値処理されて最適のハード決定を得ることもできる［例えばビタビアルゴリズム（G. O. Forney、「The Viterbi algorithm」、Proc. IEEE、６１巻２６８〜２７８頁１９７３年３月）又はバールアルゴリズム（L. R. Bahl、J. Cocke、F. Jelinek,及びJ. Raviv、「Optimal decoding of linear codes for minimizing symbol error rate」、IEEE Trans. Inform. Theory 、ＩＴ−２０巻２８４〜２８７頁１９７４年３月）と同じ決定を生成する］。多くの用途の一般的な傾向は、より高いデータ速度へ向かっているので、高速のアルゴリズムとアーキテクチャが要望されている。
【００３３】
データ検出回路アーキテクチャの二つの基本的な性能（速度）の側面がある。第一の側面は、そのアーキテクチャが復号できる１秒当りビット数の大きさである処理量である。第二の側面は、Ｎビットのブロックを復号するための終端間遅延（end-to-end delay）である待ち時間である。非パイプラインのアーキテクチャは、一度に一ブロックだけを復号し、かつその処理量が単に待ち時間で割り算されたＮで表されるアーキテクチャである。一方、パイプラインアーキテクチャは、複数のブロックを同時に復号し、その後シフトされて、非パイプラインの対応するアーキテクチャよりはるかに大きい処理量を達成することができる。
【００３４】
その用途によっては、データ検出ハードウェアの処理量及び／又は待ち時間が重要である。例えば、ターボ符号化システムにて、比較的低いデータ速度（１００Ｋｂ／ｓ未満）でインタリーブすることに関連する待ち時間は、反復復号ハードウェアの待ち時間を超えるようである。しかし、将来の高速システムの場合、インタリーバによる待ち時間は、比較的短くなり、復号器の待ち時間が重要になる。パイプライン復号器は、処理量の要求を達成できることが多いが、このような方法は一般的に、待ち時間を、実質的に短くすることはない。その上、待ち時間はシステムの全性能に対して劇的なインパクトを与える時がある。例えば、データ記憶システム（例えば磁気ハードドライブ）において、検索プロセスの待ち時間は、マイクロプロセッサやコンピュータ全体の性能に対して劇的なインパクトを与える。このような磁気記憶チャネルは、ターボ符号化法による高速のビタビ処理法を利用できる。
【００３５】
標準のＳＩＳＯアルゴリズムは順方向−逆方向アルゴリズムである。関連する順方向と逆方向の再帰的ステップは、与えられた時点のすべてのＦＳＭ状態に対して並列に計算して、Ｏ（Ｎ）という計算量（computational complexity）と待ち時間（Ｎはブロックサイズである）を有するアーキテクチャを得ることができる。本願の重要な結果は、プレフィックス演算とサフィックス演算の組合せを使用して標準ＳＩＳＯ計算を再公式化することであり、その再公式化によって、Ｏ（ｌｇＮ）という待ち時間を有するアーキテクチャがもたらされる。このアーキテクチャは「木−ＳＩＳＯ」と呼ばれるが、超大規模集積回路（ＶＬＳＩ）文献中の高速並列プレフィックス計算のための木構造（例えば高速加算器に基づいている。
【００３６】
前記木−ＳＩＳＯの待ち時間のこの指数関数的な減少は、計算量と計算領域の増大を犠牲にしてなされる。これらコストの正確な値は、該ＦＳＭの構造（例えば状態の数）とその実行の詳細によって決まる。しかし、四状態の畳みこみ符号、例えばターボ符号の構成符号として使用されることが多い符号の場合、その木−ＳＩＳＯアーキテクチャは、Ｏ（ＮｌｇＮ）という計算量で、Ｏ（ｌｇＮ）という待ち時間を達成する。この四状態実施例の場合、木−ＳＩＳＯアーキテクチャの計算量は、関連するスピードアップに対してほぼ直線的に増大することに留意すべきである。これは、ビタビアルゴリズムに対する線形スケールの解（linear-scale solution）（例えばFettweisら、「Parallel Viterbi algorithm implementation: Breaking the ACS-bottleneck」、IEEE Trans・Commun. 、３７巻７８５〜７９０頁１９８９年８月などに記載されている）より優れており、そしてその解の汎化（generalization）は、上記ＳＩＳＯの問題に対して必ずしも明確でない。この四状態符号の実施例の場合、待ち時間がＯ（ｌｇＮ）の木−ＳＩＳＯに関連する領域はＯ（Ｎ）である。
【００３７】
ソフトイン・ソフトアウトモジュール
並列状態遷移（Parallel state transition）なしで一般Ｓ状態のトレリス（generic S-state trellis）を有する特別クラスの有限状態機械を考案する。このようなトレリスは、Ｓ遷移に達するまで、各状態に出入りする。ＦＳＭは、対応するＦＳＭ入力とＦＳＭ出力による状態遷移のラベル付けによって定義される。ｔ_ｋ＝（ｓ_ｋ、ａ_ｋ、ｓ_ｋ＋１）＝（ｓ_ｋ、ａ_ｋ）＝（ｓ_ｋ、ｓ_ｋ＋１）とすると、時点ｋにおける状態ｓ_ｋから、入力ａ_ｋに応じて状態ｓ_ｋ＋１へのトレリス遷移になる。並列の状態遷移はないので、ｔ_ｋはこれらの表現によって独自に定義される。遷移ｔ_ｋが起こると仮定すると、ＦＳＭ出力はｘ_ｋ（ｔ_ｋ）である。一般に、遷移から出力へのマッピングはｋによって決めることができることに留意すべきである。
【００３８】
ＦＳＭは、ディジタル入力シーケンスａ_ｋをディジタル出力シーケンスにマップするシステムとみなす。このＦＳＭの限界ソフトインバース（marginal soft-inverse）又はＳＩＳＯは、入力ＳＩ（ａ_ｋ）と出力ＳＩ（ｘ_ｋ）のソフトイン（ＳＩ）情報の、ａ_ｋ及び／又はｘ_ｋに対するソフト出力（ＳＯ）情報へのマッピングと定義することができる。そのマッピングは、使用される結合オペレータとマージナライゼーションオペレータによって定義される。マージナライゼーションと結合のオペレータについて、一つの特定の妥当な選択を考えることだけが必要でありそしてその結果は他の重要なオペレータに容易に変換することは現在よく知られている。したがって、焦点は、標準の方式で、ｍａｘ−積（max-product）、ｓｕｍ−積、ｍｉｎ^＊−ｓｕｍ及びｍａｘ^＊−ｓｕｍへ変換された結果によるｍｉｎ−ｓｕｍマージナライゼーション−結合演算である。いずれの場合も、特定量ｕ_ｋに対するソフト出力の計算［例えばｕ_ｋ＝ｓ_ｋ、ｕ_ｋ＝ａ_ｋ、ｕ_ｋ＝ｔ_ｋ、ｕ_ｋ＝ｘ_ｋ＝（ｓ_ｋ、ｓ_ｋ＋ｄ）など］に使用される結合ウィンドウ又はスパンの時間境界は、指標Ｋ_１とＫ_２に定義させる。一般にＫ_１とＫ_２はｋの関数である。表記はコンパクトであるため、この従属性は明確には示されていない。ｍｉｎ−ｓｕｍマージナライゼーション結合の場合、量ｕ_ｋの最小シーケンスメトリック（ＭＳＭ）は、ｕ_ｋの条件値（conditional value）と両立する結合ウィンドウ又はスパンの最短の経路又はシーケンスのメトリック（又は長さ）である。具体的に述べると、ＭＳＭは次のように定義される。標準慣行と同様に、ＦＳＭ構造下では起こり得ない遷移のメトリックは無限大であると解釈される。
【００３９】
【数３】

上記式中、ｕ_ｋと両立する、時点Ｋ_１で始まり時点Ｋ_２で終わる一組の遷移は
【数４】

で表され、そして
【数５】

は遷移ｔ_ｋ１、ｔ_ｋ１＋１、…、ｔ_ｋ２のシーケンスを暗黙のうちに定義する。
【００４０】
特定の用途に応じて、下記の「外因性（extrinsic）」量が計算される。
【００４１】
【数６】

【００４２】
ＳＩＳＯが定義されるシステムはＦＳＭであるから、式（２）〜（３）における結合とマージナライゼーションの演算は効率的に計算することができる。伝統的な方法は、状態のＭＳＭを、適時再帰的に順方向と逆方向に計算する順方向−逆方向のアルゴリズムである。具体的に述べると、遷移ｔ_ｋ、ｋ＝０，１，…，Ｎ−１に対するソフトインに基づいた標準の固定インターバルアルゴリズムの場合、加算−比較−選択（ＡＣＳ）演算に基づいて下記再帰式（recursion）が得られる。
【００４３】
【数７】

上記式中、ｆ_−１（ｓ_０）とｂ_Ｎ（ｓ_Ｎ）は、利用可能なエッジ情報に応じて初期化される。状態に対するＳ可能値（S possible value）があるので、これらの状態メトリクスは（Ｓ×１）ベクトルｆ_ｋとｂ_ｋとみなすことができる。式（４）〜（５）における最終ソフト出力は、遷移ｔ_ｋのＭＳＭについてマージナライズすることによって得られる。
【００４４】
【数８】

上記式中ｕ_ｋはｘ_ｋ又はａ_ｋである。式（８）での演算は完了演算と呼ばれる。
【００４５】
上記順方向−逆方向のアルゴリズムは計算が効率的であるがその直接順方向の実行（straightforward implementation）は、カジュアル（casual）及びアンチカジュアルの状態ＭＳＭを計算する際のＡＣＳのボトルネックのため、待ち時間が大きい（すなわちＯ（Ｎ））。
【００４６】
プレフィックス演算とサフィックス演算
プレフィックス演算は、下記式にしたがって、ｎ個の入力ｙ_０、ｙ_１、…、ｙ_ｎ−１、を行ってｎ個の出力ｚ_０、ｚ_１、…、ｚ_ｎ−１を生成する計算の一つの一般形式と定義される。
【００４７】
【数９】

上記式（１０）中、各文字の肩部に付された記号はアソシエティブ２項オペレータ（associative binary operator）である。
【００４８】
同様に、サフィックス演算は、下記式にしたがって、ｎ個の入力ｙ_０、ｙ_１、…、ｙ_ｎ−１、を行ってｎ個の出力ｚ_０、ｚ_１、…、ｚ_ｎ−１を生成する計算の一つの一般形式と定義できる。
【００４９】
【数１０】

上記式（１２）中、各文字の肩部に付された記号はアソシエティブ２項オペレータである。サフィックス演算は、単に、他のエッジに固定された（逆方向）プレフィックス演算であることに注目すべきである。
【００５０】
プレフィックス演算とサフィックス演算は、木構造化アーキテクチャを利用して短い待ち時間で実行できる一クラスのアルゴリズムを可能にするので重要である。この概念を実現する最も注目すべきものは、待ち時間がＯ（ｌｇＮ）のＶＬＳＩＮ−ビットの木加算器（VLSI N-bit tree adder）である。
【００５１】
ＳＩＳＯ演算の再公式化
上記提案された短い待ち時間のアーキテクチャは、プレフィックス演算とサフィックス演算を組み合わせることによりＳＩＳＯ計算を公式化することによって誘導される。この公式化を行うために、ｍ＞ｋの場合のＣ（ｓ_ｋ、ｓ_ｍ）を状態のペア（state pair）ｓ_ｋとｓ_ｍのＭＳＭとして、それらペア間のソフト入力に基づいて定義する。すなわちＣ（ｓ_ｋ、ｓ_ｍ）＝ＭＳＭ_ｋ ^ｍ−１（ｓ_ｋ、ｓ_ｍ）と定義する。ＭＳＭのセットＣ（ｓ_ｋ、ｓ_ｍ）は（ｓ×ｓ）マトリックスＣ（ｋ、ｍ）とみなすことができる。カジュアル状態ＭＳＭｆ_ｋ−１は、ｓ_０に対しその条件をマージナライズする（例えば最小限にする）ことによってＣ（０、ｋ）から得ることができる。逆方向状態メトリクスは類似の方式で得ることができる。具体的に述べると、ｓ_ｋの各条件値に対して下記のとおりである。
【００５２】
【数１１】

【００５３】
この観測の場合、該アルゴリズムの一つの重要スナップは、ｋ＝１、２、…、Ｎ−１の場合のＣ（０、ｋ）及びＣ（ｋ、Ｎ）を計算することである。該アルゴリズムの入力は、ｋ＝０、１、…、Ｎ−１の場合のＣ（ｋ、ｋ＋１）と書き表すことができる１ステップ遷移メトリクスであることに注目すべきである。このアルゴリズムがプレフィックスとサフィックスの計算によってどのように実行できるかを示すために、二つのかようなマトリックスすなわち一方が他方の右エッジと一致する左エッジを有しているマトリックスを入力し、次いでその中央点をマージナライズアウトしてより大きいスパンを有するペアワイズ(pairwise)状態ＭＳＭを得るＣマトリックスのｍｉｎ−ｓｕｍ融合オペレータを定義する。具体的に述べると、Ｃ（ｋ_０、ｍ）とＣ（ｍ、ｋ_１）が与えられると、我々はＣ融合オペレータを定義するか、又は、下記式において（Ｃ（ｋ_０、ｍ）とＣ（ｍ、ｋ_１）の間に）記載された記号にて表されるアソシエティブ２項オペレータが定義される。
【００５４】
【数１２】

【００５５】
このアソシエティブ２項オペレータは、二つのマトリックスを受け入れて一つのマトリックスを戻すアソシエティブ２項オペレータである。これは図１に示す。この定義によって、ｋ＝０、１、…、Ｎ−１の場合のＣ（０、ｋ）とＣ（ｋ、Ｎ）は下記のようにプレフィックス演算とサフィックス演算を利用して計算することができる。
【００５６】
【数１３】

【００５７】
一般に、ＳＩＳＯアルゴリズムは、状態を調整する分離特性（decoupling property）に基づいている。具体的に述べると、時点ｋにおけるすべての可能なＦＳＭ状態値に対する調整、すなわちこの状態条件の両側の最短経路の問題（例えばＭＳＭ計算）は、独立して解決しともに融合させることができる（例えば、Ｃ融合オペレータ（C-fusion operator）によって実行されるように）。より一般的には、該ＳＩＳＯ演算は、観測インターバルを、独立して処理された各サブインターバルで区分することによって分離し次に融合することができる。例えば、順方向−逆方向アルゴリズムは、順方向と逆方向に順次起こる融合によって、単一遷移レベルに区切ることに基づいている。対照的に、他のＳＩＳＯアルゴリズムは、前記区分、及び前記部分問題（sub-problem）に対する解を融合するスケジュールを指定することによって定義できる。これは、アソシエーション方式を上記プレフィックス−サフィックス演算に記入して（すなわち括弧でまとめて）表すことができる。
【００５８】
Ｃ融合演算は、場合によっては、アソシエーション方式に応じて単純化することができる。例えば、該順方向―逆方向アルゴリズムは、すべてのＣ融合演算を、はるかに単純な順方向と逆方向のＡＣＳで代替する。しかし、待ち時間もアソシエーション方式の関数である。ペアワイズ木構造化グルーピングに基づいたアーキテクチャを以下に示す。この構造は、Ｃ融合演算の小サブセットのみを単純化できるが、部分問題に対する解を、順次方式の代わりに並列方式で融合することによって、順方向−逆方向アルゴリズムに比較して、待ち時間を容易に、大きく短くすることができる。
【００５９】
待ち時間の短い木−ＳＩＳＯアーキテクチャ
プレフィックス演算の２項木−構造化グルーピングに基づいた多くの待ち時間の短い並列アーキテクチャは、Brentら、「A regular layout for parallel adders」、IEEE Transactions on computers 、Ｃ−３１巻２６０〜２６４頁１９８２年３月；T．H．Cormenら著、Introduction to Algorithms、米国マサチューセッツ州ケンブリッジ、The MIT Press、１９９０年；及びA. E. Despain著、New Computer Architectures、Academic press、１９８４年の「第二章：Notes on computer architecture for high performance」に記載されているようなＳＩＳＯに採用させることができる。これらはすべて、その二項アソシエティブオペレータが単純な１ビット加算であるｎ−ビット加算設計を目標としている。本発明の発明者らは、並列のプレフィックス−サフィックスアーキテクチャが１ビット加算より大きく複雑である二項アソシエティブオペレータに基づいたアルゴリズムに適用できることを最初に見出したのである。従来の並列プレフィックス−アーキテクチャは、領域が小さくならず、待ち時間が長いので、各計算モジュールの限定論理出力の二次的制限の原因になっている。この後者の制限は、計算モジュールが小さくかつ、ワイヤやバッファの遅延に類似の遅延を有しているとき（例えば加算器の設計において）に重要である。しかし、該融合オペレータは比較的大きい。その結果、現行ＶＬＳＩの傾向が提供されると、その傾向は、近い将来、全遅延を左右すると考えられる。したがって、本願に記載のアーキテクチャは、論理出力に関係なく、最小数の計算モジュールによって、待ち時間を最小限にする。
【００６０】
具体的に述べると、ｋ＝１、２、…、Ｎの場合の順方向と逆方向のメトリクスｆ_ｋ−１とｂ_Ｎ−ｋは、図２に示す融合モジュール（ＦＭ）アレイに基づいた階層木構造を使用することによって得ることができる。インターバル［ｋ_０、ｋ_０＋Ｋ］上のＣマトリックスの完全セットは、Ｃ（ｋ_０、ｋ_０＋Ｋ）に加えて、ｍ＝１、２、…、Ｋ−１の場合の２Ｋ−１マトリックスＣ（ｋ_０、ｋ_０＋ｍ）とＣ（ｋ_０＋ｍ、ｋ_０＋Ｋ）である。これは、一状態が該インターバルの左又は右のエッジにある場合のトレリスのＫステップのスパン上のすべての状態ペアに対するＭＳＭ情報である。図２に示すモジュールは、二つの隣接するスパン−Ｋインターバルに対するＣマトリックスの完全セットを融合して、サイズ２Ｋの結合スパン上にＣマトリックスの完全セットを生成する。４Ｋ−１出力Ｃマトリックスのうち２Ｋは、全くプロセッシングなしで２（２Ｋ−１）入力から得られる。他の２Ｋ−１出力Ｃマトリックスは、前記アソシエティブ２項オペレータを実行する２Ｋ−１Ｃ融合モジュールすなわちＣＦＭによって得られる。
【００６１】
図２に示すスパン−２ＫＦＭアレイに対する基本スパン−Ｋを利用して、ｌｇＮステージにおける全インターバルのＣマトリックスを計算することができる。これは、Ｎ＝１６の特別な場合について図３に示してある。ｉ＝１、２、…、ｎ＝ｌｇＮのとき左から右へ（すなわちスパンを増大しながら）ステージに指標付けすると、ステージｉに２^ｎ−ｉＦＭアレイがあることは明らかであることに注目すべきである。
【００６２】
しかし、最終目的は、カジュアルとアンチカジュアルの状態マトリックスを計算することであるから、すべてのＦＭが、すべてのＦＭアレイに対してＣＦＭである必要はない。具体的に述べると、順方向状態のメトリクスｆ_ｋ−１は下記式によってｆ_ｍ−１とＣ（ｍ、ｋ）から得ることができる。
【００６３】
【数１４】

同様に、逆方向状態のメトリクスは下記式によって更新することができる。
【００６４】
【数１５】

【００６５】
式（１６）に記載されているように、別のｆベクトルとＣマトリックスからｆベクトルを生成するプロセッシングモジュールはｆ融合モジュール（ｆＦＭ）と呼称する。ｂ融合モジュール（ｂＦＭ）は式（１７）による演算によって、同様に定義される。図３は、どのＦＭを、ｆＦＭ又はｂＦＭとして実行できるかを示す。
【００６６】
この開発の重要性は、その状態メトリクスを計算するのにＯ（ｌｇＮ）の待ち時間があることである。これは、データ従属性だけが一ステージから次のステージまでであるので、一ステージ内のすべてのＦＭアレイとＦＭアレイ内のすべてのＦＭを、各々Ｏ（ｌ）の待ち時間をとりながら並列に実行できるからである。この短い待ち時間のコストは、比較的大きな領域に対して必要である。一つの軽減ファクターは、木のステージが順に作動するから、ハードウェアがステージ間で共用できるということである。したがって、最大のハードウェアを必要とするステージは、必要な全ハードウェアを決定する。これの概略推定はＮＣＦＭであり、それらＣＦＭは各々、関連レジスタ（associated register）を有するＳ^２ＳウェイＡＣＳユニットを含んでいる。可能な場合はいつでもｂＦＭとｆＦＭを使用する理由を説明するより詳細な解析結果は、後記項目「ハードウェア資源の必要量（requirements）」で詳述する。図３に示す実施例及び４状態ＦＳＭ（すなわち、Ｓ＝４）の場合、ステージ２は最も多数のＣＦＭ（８）を有しているが、ステージ３は最大の処理計算を有している。特に、四つの４ウェイＡＣＳユニットによって測定される、ステージｉ＝１、２、３、４の計算量はそれぞれ２６、３６、３２及び１６である。したがって、ハードウェアがステージ間で共用される場合には、すべてのＦＭを与えられたステージにて並列で実行するために、四つの４ウェイＡＣＳユニットからなるセットが合計３６セット必要である。この数のＡＣＳユニットが実際に利用できないときの用途の場合、ハードウェアの必要量を、待ち時間の対応する線形増加によって、１／Ｓまで減らすことができる。
【００６７】
式（８）で定義された完了演算の実行も考慮しなければならない。必要な基本的演算はＱウェイＡＣＳユニット（Ｑはｕ_ｋと一致する遷移の数である）である。その遷移のせいぜい１／２がｕ_ｋと一致していると仮定すると、ＱはＳ^２／２が上限である。その結果、Ｓが大きいと、完了ステップの待ち時間が短く領域効率のよい実行が重要な問題になる。幸いにも、低待ち時間の実行が多数、広く知られている（例えばP. J. Blackの博士論文：Algorithms and Architectures for High Speed Viterbi Decoding、米国カリフォルニア州スタンフォード大学、１９９３年３月に記載されている）。一つの直線的順方向の実行は、コンパレータの二本木を使用しかつ待ち時間がＯ（ｌｇＳ^２）の実行である。小さいＳの場合、この追加の待ち時間は一般に有意でない。
【００６８】
状態メトリック計算（state metric calculation）の計算量は、図２と３に基づいた単純な表現を使用して計算できる。後記「計算量の解析」の項で説明するように、Ｓ回のＳウェイＡＣＳ計算の単位で測定される計算の全回数は次のとおりである。
【００６９】
【数１６】

【００７０】
図３に示す４状態ＦＳＭの実施例の場合、四つの４ウェイＡＣＳ演算の１１０セットと等しい演算を実行する。これは、２Ｎ＝３２のかような演算を実行し、待ち時間が４倍のベースラインアーキテクチャを有する対応する順方向−逆方向アルゴリズムと比較すべきである。一般に、待ち時間をＮからｌｇＮまで減らすには、計算が、約（１／２）（ｌｇＮ−３）Ｓ＋１倍増大することに留意すべきである。したがって、その関連計算量は大きいが、その計算量のスケーリングはＮにサブリニアである（sub-linear in N）。
【００７１】
疎トレリスに対する最適化
一般に、上記アーキテクチャは、十分に接続されトレリスに対して最も有効である。しかし、より疎なトレリス構造の場合、初期処理モジュールは、間に遷移のシーケンスが全くない状態のペアのＭＳＭを占め、そのため処理電力と待ち時間を浪費する、∞に設定された要素を含むＣマトリックスを処理しなければならない。別の実施態様は、この非能率に取り組む最適化法を組み入れることができる。
【００７２】
Ｓ＝Ｍ^Ｌ状態でありそして各状態（時点ｓ_ｋにおいて与えられた状態から与えられた状態ｓ_ｋ＋Ｌへと進む遷移のシーケンスが正確に存在している）に出入りする正確にＭ個の遷移を有する標準の１ステップトレリスを、ベースラインとみなす。一最適化法は、該一スナップトレリスをプレコラプス（pre-collapse）して、Ｒステップのトレリス（１≦Ｒ≦Ｌ）にして木−ＳＩＳＯアーキテクチャを該コラプスされたトレリスに適用する方法である。第二の最適化法は、可能な場合はいつでもＣ融合モジュールを単純化する方法である。特に、Ｒステップのトレリス上のＳＩＳＯの場合、第一ｌｇ（Ｌ／Ｒ）ステージは、単純化して、多重ステップの遷移メトリクスの入力ペアを単純に加算する加算のバンクにすることができる。
【００７３】
さらに詳しく述べると、プレコラプシングは、ｋ＝０、１、…、（Ｎ−１）／Ｒの場合の各スーパー遷移（super-transition）
【数１７】

の遷移メトリクスを構成する１ステップ遷移のＲメトリクスの加算を含む。そのＳＩＳＯは、これらの入力を受け入れて、順方向と逆方向のＭＳＭすなわちｋ＝０、１、…、Ｎ／Ｒの場合のｆ_ｋＲ−１（ｓ_ｋ）とｂ_{（ｋ＋１）Ｒ}（Ｓ_{（ｋ＋１）Ｒ}）を生成する。プレコラスピングの一つの重要な利点は、ＳＩＳＯ入力の数が１／Ｒに減少して、ｌｇＲによる状態のメトリック計算に必要なステージの数が減少することである。プレコラスピングの起こりうる一つの欠点は、所望のソフト入力が、より複雑で一般化された下記完了演算（completion operation）を利用して計算しなければならないことである。
【００７４】
【数１８】

一つの重要な問題点は、各Ｕ_ｋＲ＋ｍについて、この完了ステップが、１ステップトレリスに必要な（Ｍ^Ｌ＋１／２）ウエイＡＣＳではなくて（（Ｍ^Ｌ＋Ｒ／２）ウエイＡＣＳを含むということである。
【００７５】
これら両者の最適化法が実施されると仮定して最適Ｒ（すなわち最短の待ち時間を得るための）を確認するため、構成演算（constituent operation）の相対待ち時間が必要である。正確な待ち時間は実行の詳細によって決まるが、粗い推定によって、やはり洞察に満ちた結果が得られる。特に、状態メトリックに対するプレコラプシング加算とＡＣＲ演算及び完了演算の両者を、加算器／コンパレータの２分木（binary tree）を利用して実行すると想定すると、それらの推定遅延は、それら入力の数の対数になる。一つの重要な観測は、プレコラプシングが、ｌｇＲで単純化されたステージとともに、Ｌ１ステップの遷移メトリクスを加算して（充分に接続されたＬステップトレリスに対する遷移メトリクスを生成する）。推定されたｌｇＬ時間単位で共同して実行できることである。その上に、状態メトリック（Ｍ^Ｌ）ウエイＡＣＳユニットはｌｇＭ^Ｌ時間単位を採用し、完了ユニット（Ｍ^Ｌ＋Ｒ／２）ウエイＡＣＳはｌｇ（Ｍ^Ｌ＋Ｒ／２）時間単位を採用する。並列性が最高であると仮定すると、全待ち時間は下記式で表される。
【００７６】
【数１９】

【００７７】
待ち時間は、Ｒ＝Ｌのときに起こるＲ−ＬｌｇＲが最小の場合（１≦Ｒ≦Ｌを条件とする）に最も短くなる。このことは、待ち時間の最も短いアーキテクチャが、トレリスが充分に接続されたトレリスにプレコラプスされ、そしてより複雑な完了ユニットを使用して、ソフト出力を、計算された定期状態メトリクス（periodic state metrics calculated）から抽出するアーキテクチャであることを示唆している。
【００７８】
この短くした待ち時間のコストは、Ｌステップの遷移メトリクスを生成する加算器の木及びより複雑な完了演算を実行するのに必要なコンパレータのより大きな木を、実行するのに必要な追加の領域である。しかし、この領域のオーバヘッドは、各木のステージ間で、場合によっては待ち時間に対して重要でない影響しか与えない木の間で加算器とコンパレータを共用することによって軽減することができる。
【００７９】
タイルドサブウインドウ方式（tiled sub-window scheme）
本発明の発明者らは、より小さい結合ウィンドウを使用すると待ち時間が短くなり、ソフトインバース計算の処理量が改善されることを知った。最小ハーフウィンドウ（Minimum half-window）（ＭＨＷ）アルゴリズムは一クラスのＳＩＳＯであり、そのＳＩＳＯでは、結合ウィンドウのエッジＫ_１とＫ_２が、ｋ＝０、…、Ｎ−１の場合、Ｋ_１≦ｍａｘ（０、ｋ−ｄ）及びＫ_２≧ｍｉｎ（Ｎ、ｋ＋ｄ）を満たし、すなわち、該観測ウィンドウのエッジからＫだけ離れているあらゆる点に対するソフト出力は、左と右のエッジのｋだけ離れた少なくともｄ個の点を有するサブウィンドウに基づいている。
【００８０】
伝統的な順方向−逆方向アルゴリズムは、サブウィンドウに使用してＭＨＷ−ＳＩＳＯを得ることができる。一つの特別な方式は、長さが２ｄ＋ｈの結合ウィンドウを使用してすべての状態メトリクスを引き出すタイルサブウィンドウ方式である。この方式では、図４に示すように、ウィンドウは長さ２ｄがオーバーラップしてタイルされて、このようなウィンドウが（Ｎ−２ｄ）／ｈ個ある。各内部サブウィンドウでの順方向−逆方向の再帰によってｈのソフト出力が生成し、その結果、ｈが小さくなるにつれて増大するオーバラップペナルティ（overlap penalty）がある。
【００８１】
ｉ番目のこのようなウィンドウについて、順方向と逆方向のメトリクスは、式（６）と（７）に示す再帰式を変形した下記再帰式を使用して計算される。
【００８２】
【数２０】

すべてのウィンドウが並列で処理されると、このアーキテクチャは待ち時間がＯ（ｄ＋ｈ）になる。
【００８３】
前記の木−ＳＩＳＯアルゴリズムは、オーバラップペナルティなしでかつ待ち時間Ｏ（ｌｇｄ）のＭＨＷ方式に使用できる。サイズがｄのＮ／ｄ結合ウィンドウを考慮して、該木−ＳＩＳＯに、ｊ＝０、…、ｄ−１及びｉ＝０、…、Ｎ／ｄ−１の場合のＣ（ｉｄ、ｉｄ＋ｊ）及びＣ（（ｉ＋１）ｄ、（ｉ＋１）ｄ−ｊ）を計算させる。次いで、下記のようにして、一つの追加の論理ステージを使って、ｉ番目のウィンドウ（ｉ＝０、…、Ｎ／ｄ−１）内に入るすべてのｋ ｔｉｍｅの指標について順方向と逆方向の状態メトリクスを計算する（これは、Ｃ（ｓ_−ｄ、ｓ_０）が初期の左エッジ情報で置換されかつＣ（ｓ_Ｎ−１、ｓ_{Ｎ＋ｄ−１}）の場合も同様に置換されると解釈すべきである）。
【００８４】
【数２１】

【００８５】
上記内部最小化は、式（１３）と（１４）に示すような、Ｃ情報からｆ（ｂ）情報への変換に相当する。上記外部最小化はｆＦＭ又はｂＦＭに相当する。この最小化の順序は計算量が最小限になるように選択した。これは、図５に示すこの方法の実施例に反映されており、その実施例では、四つの木−ＳＩＳＯ各々の最後のステージが、提案された順序で上記最小化を実行するように改変されている。これを実施するモジュールは、２Ｃｆｂモジュールと呼称される。このモジュールは、図３に示すステージの二つの中央ＣＦＭを特化したものとみなすことができる。サブウィンドウの木−ＳＩＳＯ出力の上記紹介は一つの追加処理ステージを加算し、その結果、ＦＭのステージの必要数はｌｇ（ｄ）＋１になる。
【００８６】
計算量の比較
順方向−逆方向のタイルド方式を利用して状態メトリクスを計算する際の計算量は、（各ウィンドウで順方向−逆方向のアルゴリズムを計算する際の計算量）×（ウィンドウの数）の計算量である。これは、ＳのＳウェイＡＣＳによって、Ｎが大きい場合下記式で近似することができる。
【００８７】
【数２２】

木−ＳＩＳＯのタイルド方式を利用して、ＳのＳウェイＡＣＳによって状態メトリクスを計算する際の計算量は同様に、展開することができ下記の式で表される。
【００８８】
【数２３】

【００８９】
どの方式がより高い計算量であるかの判断は、ｈとｄの相対的大きさによって決まる。ｈが小さくなると、標準の順方向−逆方向方式は待ち時間が短くなるが、オーバーラップしたウィンドウの数が増大するので計算量が増大する。タイルド木−ＳＩＳＯのアーキテクチャはオーバラップペナルティがないので、ｈが、タイルド順方向−逆方向方式において小さくなるにつれて、相対的計算量トレードオフは、木−ＳＩＳＯ法にとってより有利になる。実際に、ｈ＜（２ｄ／Ｓｌｇｄ）の場合、木−ＳＩＳＯの計算量は、タイルド順方向−逆方向方式の場合より小さい。
【００９０】
設計実施例：４状態ＰＣＣＣ
考えられる高並列性のアーキテクチャは、大きい実行領域が必要である。この実施例では、その領域必要量が、近い将来に実行するのに最も適している実施態様について述べる。具体的に述べると、４状態の疎（一ステップ）トレリスに基づいた反復復号器が考えられる。より大きなＳを考慮すると、木−ＳＩＳＯの待ち時間がより印象的に短くなる。これは、並列タイルド順方向―逆方向アーキテクチャに対して木−ＳＩＳＯアーキテクチャによって得られる待ち時間の短縮は、最小ハーフウィンドウの大きさによって決まる。優れた性能は、状態の数とともに大きくなるｄの値を必要とする（すなわち疎トレリスに対するビタビアルゴリズムのトレースバック深さ（traceback depth）に関する経験則に似ている）と予測される。対照的に、プレコラプシングを考慮すると、得られる待ち時間の短縮は余り印象的でない。例えばｄ＝１６であることが、単一ステップトレリスに対して必要である場合、ｄ＝８という有効値が２ステップトレリスにとって充分なものである。前者の場合の木−ＳＩＳＯに関する待ち時間は、約１／４まで短縮されるが、後者の場合３／８まで短縮されるにすぎない。しかし、Ｓ及び／又はプレコラプシングが大きくなればなるほど実行領域が大きくなって、これらアルゴリズムを近い将来実現できる可能性を現実的に評価する我々の要望と一致しない。
【００９１】
特に、二つの４状態構成符号（4-state constituent code）［１］［２］を有する標準の並列連結畳みこみ符号（ＰＣＣＣ）が考えられる。これらの再帰組織構成符号（recursive systematic constituent code）は各々、句読点をつけたバリティビットを有するジェネレータ多項式（generator polynomial）：Ｇ（Ｄ）＝（１＋Ｄ^２）／（１＋Ｄ＋Ｄ^２）を使用してパリティを生成して、レート（rate）１／２の全組織符号を達成する。
【００９２】
ＭＨＷ−ＳＩＳＯに使用するｄの近似値を求めるために、各ＳＩＳＯが結合ウィンドウ（ｋ−ｄ、…ｋ＋ｄ）を使用して時点ｋにおけるソフト出力を計算するシミュレーション行った。これは、ｈ＝１のタイルド順方向−逆方向法によって得られるＳＩＳＯ演算に、正確に等しい。ｄは前記シミュレーションに用いるすべての（内部）ハーフウィンドウの大きさであるから、ｄを有するＭＨＷ−ＳＩＳＯに基づいたどのアーキテクチャも、少なくとも同様に作動する（例えばｈ＝２のタイルド順方向−逆方向、ｄタイルド木−ＳＩＳＯなど）。インタリーバの大きさがＮ＝１０２４で、ｍｉｎ−ｓｕｍマージナライゼーションと結合及び１０回の繰返しによるシミュレーションの結果を図６に示す。各種のｄの場合の性能を、固定インターバル（Ｎ＝１０２４）ＳＩＳＯの性能とともに示す。どんな機器構成の場合でも、１０回を超える繰返しを行っても繰返しによる有意な利得は全く達成されない。これらの結果は、ｄ＝１６によって、固定インターバルの場合に近い性能が得られることを示している。これは、ビタビ復号器のトレースバック深さに対するメモリの５〜７倍という経験則と一致している（すなわち、おおむねｄ＝７×２＝１４で充分であると考えられる）。
【００９３】
必要なウィンドウの大きさはｄ＝１６であるから、タイルド順方向−逆方向方式に対する木−ＳＩＳＯの待ち時間の改善は４＝１６／ｌｇ（１６）に近い。これら二つの方法の計算量は、類似しており、そしてその実行の詳細、及びタイルド順方向−逆方向の方法に対するｈの選択によって決まる。完全で公平な比較を行うには、これら二つの方法の詳細な実行が必要であろう。木−ＳＩＳＯベースのサブウィンドウアーキテクチャの設計について以下に説明する。
【００９４】
そのアーキテクチャの領域に影響する要因は、データ単位のビット幅である。シミュレーションの結果は、８ビットのデータ経路で充分であることを示唆している。概略を述べると、この実施例の木をベースにしたアーキテクチャは、中間状態メトリックの結果を記憶するため、関連する出力レジスタ（output register）とともに１６の４ウエイＡＣＳユニットの１０２４セットが必要であろう。各４ウエイＡＣＳユニットは、一つの８ビットの４−ｔｏ−１マルチプレクサ、四つの８ビット加算器、六つの８ビットコンパレータ及び一つの８ビットレジスタで実行できる。初期のＶＬＳＩの設計は、これらユニットが約２２５０個のトランジスタを必要とすることを示している。したがって、これから、１６×２２５０×１０２４≒４０万個のトランジスタが推定される。論理トランジスタのこの数は、現在のＶＬＳＩの技術の限度を超えているがまもなく実現可能になるはずである。１クロックサイクルが、前記木の１ステージ当り、２００ＭＨｚクロック周波数で用いられるアーキテクチャが考えられる。ｄ＝１６の場合、各ＳＩＳＯ演算は、六つのこのようなクロックサイクルで（その完了ステップに対して１クロックを使用する）実施することができる。さらに、相互接続ネットワークを有する１０２４個のレジスタからなる２行を含む配線インタリーバを想定する。このようなインタリーバは既存のメモリに基づく解より大きいであろうが、待ち時間は１クロックサイクルであろう。その結果、ＳＩＳＯを２回、インタリービングを一回及びデインタリービングを一回適用することからなるターボ復号器の一回の繰返しは１４のクロックサイクルを必要とする。１０回繰返すと仮定すると、１０２４ビットを復号するには、１４０のクロックサイクル又は丁度７００ｎｓの待ち時間が必要であろう。
【００９５】
また、この待ち時間は、標準のパイプライン方式によってさらに改善できる非常に高い処理量を暗示している。特に、非パイプライン方式は推定処理量が１０２４ビット／７００ｎｓ＝１．５Ｇｂ／秒である。Maseraら、「VLSI architectures for turbo codes」、IEEE、Transactions on VLSI、７巻１９９９年９月に記載されているように、木−ＳＩＳＯアーキテクチャを使用して、インタリーバブロックを横切ってパイプラインを設けることもできる。特に、このようなタイルド木−ＳＩＳＯ及び関連するインタリーバを２０個利用して処理量を２０倍まで増大して、３０Ｇｂ／秒という処理量を達成することができる。
【００９６】
さらに、順方向−逆方向アルゴリズムに基づいたアーキテクチャと異なり、木−ＳＩＳＯは、内部に容易にパイプラインを設けて、線形ハードウェアスケーリングでさらに高い処理量を達成することができる。特に、専用ハードウェアを木−ＳＩＳＯの各ステージで利用すると、木−ＳＩＳＯの内部にパイプラインを設けることによって、待ち時間が増大することなく、処理量がさらにｌｇ（ｄ）倍になる。ウィンドウサイズがｄ＝１６の場合、木ベースのアーキテクチャは、１２０Ｇｂ／秒を超える処理量を維持できる。すなわち、現在の方式では、このようなハードウェアのコストは実用限度を超えることがあると理解することが重要である。しかし、ＶＬＳＩ法の密度が連続的に増大すると仮定すると、このようなアグレッシブアーキテクチャ(aggressive architecture)でさえも、将来、費用効率が高くなりうる。
【００９７】
計算量の解析
必要なステージの数は、ステージｉ中２^ｎ−ｉＦＭアレイの場合、ｎ＝ｌｇＮである。ステージｉのこれらＦＭアレイは各々、トレリスの２^ｉステップにわたっておりかつ２^ｉ−１ＦＭを含んでいる。したがって、ステージｉのＦＭの総数はｎ_ＦＭ（ｉ）＝（２^ｉ−１）２^ｎ−ｉである。それ故、融合演算の総数は下記のとおりである。
【００９８】
【数２４】

図３に示す実施例の場合、この総数はＮ_ＦＭ＝４９まで減少する。
【００９９】
図３を一実施例として利用して、ステージｉでｆＦＭとして実行できるＦＭの数がｎ_ｆ（ｉ）＝２^ｉ−１であることを知ることができる。ｉ＝ｎである特別の場合、これは、２Ｋ−１ＣＦＭを、ＫｆＦＭ及びＫｂＦＭで置換すると解釈される。例えば、図３の第四のステージで、図２に含まれている１５のＣＦＭは、図に示されているように８ｆＦＭ及び８ｂＦＭで置換することができる。ｂＦＭとして実行できるＦＭの数は同じであり、すなわちｎ_ｂ（ｉ）＝ｎ_ｆ（ｉ）＝２^ｉ−１である。ステージｉで必要なＣＦＭの数は下記式で表されることになる。
【０１００】
【数２５】

【０１０１】
【数２６】

上記式中、δ（ｊ）はクロネッカーのδである。それ故、融合モジュールの総数は下記のとおりである。
【０１０２】
【数２７】

式（２５）と（２９）を比較すると、Ｎが比較的大きい場合、ＣＦＭでなければならないＦＭの比率は（ｌｇＮ−３）／（ｌｇＮ−１）であることが分かる。Ｎが小さい場合、その比率はわずかに大きくなる。例えば、図３において、Ｎ_ｆ＝Ｎ_ｂ＝１５でありそして２０のＣＦＭがある。
【０１０３】
そのＣＦＭは、複雑さがｆＦＭとｂＦＭの演算の約Ｓ（すなわち状態の数）倍である。このことは、式（１５）を、式（１６）及び（１７）と比べることによって知ることができる。具体的に述べると、式（１５）、（１６）及び（１７）の演算はＳウェイＡＣＳを含んでいる。ＣＦＭの場合、ＳウェイＡＣＳは、式（１５）のあらゆる可能な状態ペア(state pair)（Ｓ_ｋ０、Ｓ_ｋ１）すなわちＳ^２の状態のペアについて実施されねばならない。式（１６）と（１７）におけるＳウェイ演算は、Ｓ状態Ｓ_ｋの各々について計算することだけが必要である。したがって、計算の基本単位を、Ｓ状態トレリスに対して、ＳＳウェイＡＣＳにすると、ステージｉに対して必要なこれら計算の総数は下記式で表される。
【０１０４】
【数２８】

諸ステージにわたって合計すると、計算の総数が得られ、下記式のようにＳＳウェイＡＣＳ計算の単位で測定される。
【０１０５】
【数２９】

図３に示す実施例と４状態ＦＳＭの場合、１１０セットのＳＳウェイＡＣＳ演算の等価物が実行される。これは、２Ｎ＝３２のかような演算を実施し、４倍の待ち時間を有するベースラインアーキテクチャを有する対応する順方向−逆方向アルゴリズムと比較するためである。一般に、待ち時間がＮからｌｇＮまで減少する場合、計算が約（１／２）（ｌｇＮ−３）Ｓ＋１倍まで増大することに留意すべきである。したがって、関連する計算量は大きいが、計算量のスケーリングはＮでほぼ線形である。Ｓが小さい場合、これは、短い待ち時間のビタビアルゴリズムの実行（例えばP. J. Black博士の論文、Algorithms and Architectures for High Speed Viterbi Decoding、米国カリフォルニア州スタンフォード大学１９９３年３月；及びFettweisら、「Parallel Viterbi algorithm implementation: Breaking the ACS-bottleneck」、IEEE Trans. Commum.、３７巻７８５〜７９０頁１９８９年８月に記載されている）に対する線形スケールの解より優れている。
【０１０６】
ハードウェア資源の必要量
ｎ_Ｓ、_Ｓ（ｉ）のｉに関する最大値は、所望の最小の待ち時間を達成するための最小限のハードウェア資源の必要量を決定するので重要である。これは、融合モジュールが、待ち時間に対して無視できる影響しか与えずステージ間で共用できるからである。
【０１０７】
ｎ_Ｓ、_Ｓ（ｉ）の最大値は、ｎ_Ｓ、_Ｓ（ｉ）≧ｎ_Ｓ、_Ｓ（ｉ−１）であるｉに対する条件を検討することによって求めることができる。具体的に述べると、ｉ＜ｎの場合、下記のとおりであり、
【数３０】

ｎ_Ｓ、_Ｓ（ｉ）は局所最大値を持っていないことになり、下記式
【数３１】

を利用してｎ_Ｓ、_Ｓ（ｉ）のマキシマイザー（maximizer）を求めることができる。具体的に述べると、式（３５）においてｉ^＊＜ｎ−１になった場合、最大値はｉ^＊において生じ、その外の場合（ｉ^＊＝ｎ−１）、ｉ＝ｎ−１とｉ＝ｎの場合を比較して、最大計算量のステージを決定しなければならない。Ｓ≧４の場合、０．５≦｛１−ｌｇ（１−Ｓ^−１）｝／２≦０．７１であるから、式（３５）は下記式まで縮小することができる。
【０１０８】
【数３２】

【０１０９】
木構造化ＳＩＳＯ（tree-structured SISO）の他の実施態様
一般に、木構造化ＳＩＳＯを実動化する場合、システムデザイサーの選好に応じて、待ち時間、計算量及びＩＣ領域の間のトレードオフを示す各種木構造のどれでも使用することができる。図８Ａと図８Ｂは、順方向−逆方向の木−ＳＩＳＯ（ＦＢＴ−ＳＩＳＯ）と呼称される実施態様を示す。ＦＢＴ−ＳＩＳＯにおける木構造の再帰は、内向きと外向きの二方向性である。一つの結果として、ＦＢＴ−ＳＩＳＯは、待ち時間が木−ＳＩＳＯの２倍であるが、計算量が有意に減少するので、集積回路（ＩＣ）チップの使用面積は小さくなる。
【０１１０】
ｍｉｎ−ｓｕｍ処理中に、汎用の順方向−逆方向スケジュールを使用して送るメッセージの詳細を、図８Ａと８Ｂに示してある。内向きメッセージは図８Ａに示してある。具体的に述べると、初めに、ＭＩ〔ｔｋ〕が均一に設定され次に前記アルゴリズムが、サブシステムの第一レベルを起動することによって始まり、Ｍｋ〔ｔｋ〕をＭＩ〔ｘ（ｔｋ）〕及びＭＩ〔ａ（ｔｋ）〕から計算する。前記木の次のレベルまで内向きに送られたメッセージは、並列の遷移がない場合、単にＭｋ〔ｔｋ〕であるＭＳＭｋ〔ｓｋ、ｓｋ＋１〕である。この内向きメッセージの伝送によって、続いてメッセージが示される。ｓ４のメッセージ二つがＶ４−ｓに到達すると、図８Ｂに示すように、外向き伝搬が始まって下方向に進行する。再び、前記木の与えられたレベルすべてのノードが起動された後に、次のレベルのノードが起動される。ボトムレベルにおいて、（ｓｋ、ｓｋ＋１）に入力メトリックは、ＭＳＭ｛ｋ｝ｃ〔ｓｋ、ｓｋ＋１〕：すなわち標準順方向−逆方向アルゴリズムの順方向と逆方向の状態メトリクスの合計である。こうして、ボトムレベルでのこれらノードの最終起動によって、所望の外来出力メトリクス(extrinsic output metrics)が生成する。
【０１１１】
これらのメッセージは内向きと外向きの両方に伝搬しなければならないので、このＦＢＴ−ＳＩＳＯは待ち時間が、木−ＳＩＳＯの２倍である。待ち時間がこのように適度に増加し、これに伴い計算量が有意に減少している。具体的に述べると、ＦＢＴ−木ＳＩＳＯは計算量がＯ（Ｋ）で待ち時間がＯ（ｌｏｇ２Ｋ）である。これは、木−ＳＩＳＯの場合の計算量Ｏ（Ｋ ｌｏｇ２Ｋ）と待ち時間Ｏ（ｌｏｇ２Ｋ）及び標準のトレリスで送るメッセージの場合の計算量Ｏ（Ｋ）と待ち時間Ｏ（Ｋ）に匹敵している。
【０１１２】
木構造ＳＩＳＯの他の実施態様は、設計者の目的と制限条件によっては有利である。一般に、事実上どんなタイプの木構造でも使用する木構造ＳＩＳＯをつくることができる。例えば、R. P. Brent及びH. T. Kung「A regular layout for parallel adders」、IEEE Transactions on Computers、Ｃ−３１巻２６０〜２６４頁１９８２年３月（「Brent-Kung tree」）；A. E. Despain著「New Computer Architectures」第二章：Notes on computer architecture for high performance、Academic Press １９８４年；T. H. Cormen、C. Leiserson、及びR. L. Rivest、「Introduction to Algorithms」、The MIT Press １９９０年；及び／又はS. M. Aji及びR. J. McEliece、「The generalized distributive law」、IEEE Trans. Inform. Theory、４６(２)巻３２５〜３４３頁２０００年３月に記載されている木構造の１又は２以上を使用する木構造化ＳＩＳＯによって、有利な結果を得ることができる。
【０１１３】
図９は、ｄ＝１６のサブウィンドウにおけるブランチメトリクスの計算にＢｒｅｎｔ−Ｋｕｎｇモデルの改変バージョンが使用されるＢｒｅｎｔ−Ｋｕｎｇ木−ＳＩＳＯの表現を示す。そのＢｒｅｎｔ−Ｋｕｎｇ木−ＳＩＳＯには、点線で示す六つのパイプラインステージがある。陰をつけたノードは２ウェイＡＣＳを示し、一方黒色ノードは４ウェイＡＣＳを示す。
【０１１４】
そのＢｒｅｎｔ−Ｋｕｎｇ木−ＳＩＳＯは、Ｂｒｅｎｔ−Ｋｕｎｇ並列加算器に基づいている。それは、プレフィックス加算器のファンアウト(fan-out)問題を解決するためにつくられた。その上に、それは全メトリクスを計算するのに必要なハードウェアの大きさを減らす。ここで、融合演算も利用されるが、必要な融合演算の量は有意に減少する。Ｂｒｅｎｔ−Ｋｕｎｇ加算器では、加算の代わりに、融合演算が各ノードで実行される。この形態では、順方向の情報だけを計算することができる。そのモデルは、順方向と逆方向両方のメトリクスの計算が同時に実行できるように改変された。
【０１１５】
このモデルは、第一に、ＡＣＳの出力によって駆動しなければならないユニットの数を減らす。ここで最悪の場合、四つのユニットが単一のステージの出力を供給されている（すなわちノードＣ０、８）。これは、従来の方法が必要としているもののほとんど１／２である。また、２ウェイＡＣＳユニットのみ必要とする演算の数がかなり多いことも観察されている。２ウェイＡＣＳユニットが、４ウェイＡＣＳユニットに必要なハードウェアの１／２未満しか使用しないことを考えると、その回路系の全体の大きさはかなり小さくなると考えられる。前に実施した解析と類似の解析によって、この直感的な推測を実証する。その結果を要約して図１０に示す。
【０１１６】
この方法には、システム性能の低下を埋め合わせることができるという利点がある。図９に示すブロック図を詳しく見ると、計算の最も長い経路はこの図では６サイクル長の経路であることを示している。順方向及び逆方向のメトリック計算を行うのに必要な三つの追加のサイクルを加算すると、完了ステップとインターリービングプロセスは、ＳＩＳＯモジュールの全遅延が９サイクルになる。このことは、全復号プロセスが１８０サイクルテイクすることを意味する。同じセルが実動化に使用されると仮定すると、これによって、１０２４ビットのデータの一ブロックを処理するための全時間が５４０ｎｓｅｃになる。この場合の該システムの処理量は１．８９６Ｇｂｐｓになる。各ＡＣＳの後にパイプラインされた展開設計（unfolded design）が用いられると、各ステップの後に一つのブロックを処理することができ、そして１６．８２Ｇｂｐｓの処理量を実現できる。２０のＳＩＳＯを利用してループを展開したならば、処理量は３４１．３２Ｇｂｐｓになるであろう。第一の場合、その設計の大きさのために重要であるが、性能の劣化は約２４．１％に過ぎない。同時に、この設計を実動化するのに必要なトランジスタの数は、ほとんど４３．８％まで減少する。
【０１１７】
ブロック符号及び連結符号の、木−構造ＳＩＳＯによる復号
他の関連する復号に問題点として、通常の解がトレリスに対して標準の順方向−逆方向アルゴリズムを実行することであるという問題点がある。また、ここで述べる方法や技術は、これらの用途で処理の待ち時間を短くするため、該順方向−逆方向アルゴリズムの代わりに適用することもできる。このような用途の一実施例は、ブロックエラー訂正符号のソフトインバージョンを、その符号のトレリス表現を使用して計算することである。トレリスの表現を使用してブロック符号を復号する方法は、Robert J. McEliece、「On the BCJR Trellis for Linear Block Codes」、IEEE Transactions on Information Theory、４２巻４号１９９６年７月に記載されていた。その論文には、その符号のパリティチェック構造に基づいたトレリスの表現の構築方法が記載されている。復号、又はより一般的に述べるとブロック符号のソフトインバージョンは、このトレリスに対して順方向−逆方向のアルゴリズムを実行することによって達成できる。ここに記載の方法と技術は、ＦＳＭのソフトインバージョンの木構造化法と類似の方法でブロック符号のソフトインバージョンを決定するのに適用することができる。具体的に述べると、順方向と逆方向の状態メトリクスを計算し、木構造を有する並列プレフィックス計算アーキテクチャを使用することによってブロックコードのソフトインバージョンを求めることができる。
【０１１８】
パリティチェック構造によって、ブロック符号のソフトインバージョンを実行するために木−ＳＩＳＯアーキテクチャを適用することは実際問題として重要である。というのは、いくつもの魅力のあるターボ式符号は、簡単なパリティチェック符号の連結に基づいているからである。これらの符号は、類似の機能を有し、そしてソフトインパースノードが符号化されたビットのソフト情報を受け入れ、更新し次いで交換する反復アルゴリズムを使用して復号されるので、それら符号は「ターボ式符号」と呼称されることが多い。ターボ式符号の具体例としては、Ｇａｌｌａｇｅｒ符号及び積符号としても知られている（またターボブロック符号としても知られている）低密度パリティチェック符号（ＬＤＰＣ）があり、この符号は、J. Hagenauer、E. Offer及びL. Papke、「Iterative decoding of binary block and convolutional codes」、IEEE Transactions on Information Theory、４２(２)巻、４２９〜４４５頁１９９６年３月；及びR. G. Gallager著「Low-Density Parity-Check Codes」、MIT Press、米国マサチューセッツ州ケンブリッジ１９６３年に記載されている。
【０１１９】
具体例として、標準Ｈａｍｍｉｎｇ（７、４）符号に対するパリティチェックトレリスを図１１に示す。該順方向−逆方向アルゴリズムは、このトレリスに対して、７程度の待ち時間で実施できる。あるいは木−ＳＩＳＯアーキテクチャを使用して図１２に示す計算構造を得ることができる。ＦＳＭソフトインバージョンの場合と同様に、木構造化計算は、通常の解析法（すなわちトレリスに対して標準の順方向−逆方向アルゴリズムを実行する方法）と同じ順方向と逆方向の状態メトリクスを生じるが、対数の待ち時間（この単純な実施例では約１／２の待ち時間）を有している。一般に、長さがＮのブロック符号の場合、該順方向−逆方向アルゴリズムに基づいた従来の方法は待ち時間はＯ（Ｎ）であるが、同じ計算は、待ち時間がＯ（ｌｇＮ）の木ＳＩＳＯを利用して計算することができる。
【０１２０】
図１２に示すような木構造化パリティチェックノードＳＩＳＯに用いる具体例として、図１３に示すようなＬＤＰＣ用の反復復号器が考えられる。この復号器は、二つの基本的タイプのソフトインバース処理ノードすなわちソフトブロードキャスタノードとパリティチェックＳＩＳＯノードを有している。一実施態様で、この復号器は、並列のソフトブロードキャスタノードを起動し、続いて、該チェックＳＩＳＯノードへの入力になる生成したソフト情報を置換する(permutation)ことによって実動化する。これらのノードが、起動されて、置換によって送り戻されそしてソフトブロードキャスタへの入力になる符号化ビット値に対する更新信念（updated belief)を生成する。これは単一の反復とみなすことができる。該復号手続きが完了する前に、いくつもの反復が必要である。ターボ復号の場合と同様に、その停止基準はその設計の一部分であり、共通して選択されることは反復の数が固定されていることである。図１１に示す計算は、好ましい実施態様の各パリティチェックＳＩＳＯノードで実行される。あるいは、木構造化アーキテクチャを使用して、各パリティチェックＳＩＳＯノードで計算することができる。最も普通の形態の、ＬＤＰＣのパリティチェックノードは、単一パリティチェックであるから、二状態のトレリス表現を有している。
【０１２１】
結論
並列のプレフィックス／サフィックス演算によるＳＩＳＯ演算の解釈に基づいて、木構造化アーキテクチャのファミリーについて説明してきた。ベースライン順方向−逆方向アルゴリズムのアーキテクチャに比べて、木−ＳＩＳＯアーキテクチャは、待ち時間をＯ（Ｎ）からＯ（ｌｇＮ）まで短くなる。別の木構造化ＳＩＳＯ、例えばＦＢＴ−ＳＩＳＯは、待ち時間が線形増加せず、計算量と領域が実質的に小さくなる。
【０１２２】
有効なＳＩＳＯの設計は一般に、単一の木−ＳＩＳＯを使用して構築されることはなく、複数の木−ＳＩＳＯを重要な要素として使用して構築される。例えば、上記のように、多数の木−ＳＩＳＯを使用して、タイルドサブウィンドウを使用するＳＩＳＯを構成させた。その実施例の待ち時間は、順方向−逆方向のアルゴリズムに基づいた完全に並列のタイルドアーキテクチャに対する最小１／２ウィンドウサイズ（ｄ）の線形から、タイルド木−ＳＩＳＯに対するｄの対数形まで低下した。
【０１２３】
一般に、木−ＳＩＳＯの待ち時間の可能性のある利点は、大きな結合ウィンドウを必要とする用途にとって、明らかに最も重要である。最も実質的な設計の場合、これは状態の数が増大するときに予想される。考えられる詳細な４状態タイルドウィンドウの一実施例では、待ち時間が約１／４まで短くなった。バイナリー入力とＳの状態を有するシステムの場合、ｄ≒８ｌｇ（Ｓ）が満たされると期待できるであろう。したがって、Ｓが増大するにつれて全く重要になる。ほぼ８ｌｇ（Ｓ）／ｌｇ（８ｌｇＳ）の待ち時間が短くなる可能性がある。しかし待ち時間の可能性がある改善を達成する際の重要な課題は、それを実行するのに必要な領域である。特に、大きなＳに対して高速のＳウェイＡＣＳユニットをつくることは重要課題である。機能の劣化を招くことなく（例えばビット直列アーキテクチャ）この領域の要求を減らす技法は、前途有望な研究分野である。事実、より大きいＳを促進するとより小さいインタリーバを使用ことができ、その結果、前記領域の要求が軽減されかつ待ち時間が短くなる。
【０１２４】
本願で説明したシステムと技法の各種実動化は、ディジタル電子回路系、集積回路系、特別に設計されたＡＳＩＣ（特定用途向け集積回路）又はコンピュータのハードウェア、ファームウェア、ソフトウェアもしくはその組合せで実現することができる。
【０１２５】
本発明のいくつもの実施態様を説明してきた。しかし、本発明の精神と範囲を逸脱することなく各種の変形を行うことができると解される。したがって、他の実施態様は本願の特許請求の範囲の範囲内にある。
【図面の簡単な説明】
【図１】 Ｃ融合プロセスを示す。
【図２】 〔ｋ_０、ｋ_０＋Ｋ〕及び〔ｋ_０＋Ｋ、ｋ_０＋２Ｋ〕のＣマトリックスの完全セットを結合して〔ｋ_０、ｋ_０＋２Ｋ〕の完全セットを得る融合モジュールアレイを示す。
【図３】 Ｎ＝１６の場合の木−ＳＩＳＯアーキテクチャを示す。
【図４】 順方向−逆方向アルゴリズムに基づいたタイルドサブウィンドウ方式を示す。
【図５】 ｄ＝４ＭＨＷＳＩＳＯを実行する、Ｎ＝１６の場合ウィンドウサイズ４の四つの木−ＳＩＳＯを用いるタイルドサブウィンドウ法を示す。
【図６】 各種ハーフウィンドウサイズのＳＩＳＯ、Ｎ＝１０２４及び１０回の繰り返しの場合の標準ターボ符号のシミュレーションを示すグラフである。
【図７Ａ】 それぞれターボ符号器とターボ復号器の実施例を示す。
【図７Ｂ】 それぞれターボ符号器とターボ復号器の実施例を示す。
【図８Ａ】 順方向−逆方向木−ＳＩＳＯ（ＦＢＴ−ＳＩＳＯ）の実動化を示す。
【図８Ｂ】 順方向−逆方向木−ＳＩＳＯ（ＦＢＴ−ＳＩＳＯ）の実動化を示す。
【図９】 Ｂｒｅｎｔ−Ｋｕｎｇ木−ＳＩＳＯの一実施態様を示す。
【図１０】 図９に示すＢｒｅｎｔ−Ｋｕｎｇ木−ＳＩＳＯ法に用いるトランジスタの計数推定値を示すグラフである。
【図１１】 標準Ｈａｍｍｉｎｇ（７、４）符号に対するパリティチェックに用いるトレリス構造を示す。
【図１２】 Ｈａｍｍｉｎｇ符号パリティチェックの木構造化表現を示し、そのパリティチェックにおいて順方向−逆方向の木−ＳＩＳＯアルゴリズムを、この木で、Ｖ６と標識されたノードへのメッセージパス（message pass)の内向け（アップ）セットで次にメッセージパスの外向け（ダウン）セットで実行して、符号化ビット上に所望のソフト−アウトメトリクスを生成することができる。
【図１３】 ＬＤＰＣ復号器〔全符号情報点率(overall code rate)が０．５〕の一実施例を示し、その復号器において、信念が、固定置換によってブロードキャスタノードからパリティチェックノードへ送られ、そしてそのパリティチェックノードが木構造化ＳＩＳＯとして実動化することができる。

Claims (102)

1. 符号化信号を受信し、
   その受信した符号化信号を復調してソフト情報を生成させ、次いで
   そのソフト情報を１又は２以上のソフトイン／ソフトアウトプット（ＳＩＳＯ）モジュールで反復処理し、少なくとも一つのＳＩＳＯモジュールが、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うように構成された木構造を利用して順方向と逆方向の状態メトリクスを計算する、
   ことを含む復号方法。
2. 該少なくとも一つのＳＩＳＯが、再帰的マージナライゼーション結合演算を実行することによって、順方向と逆方向の状態メトリクスを計算する請求項１に記載の方法。
3. 該再帰的マージナライゼーション結合演算がｍｉｎ−ｓｕｍ演算を含む請求項２に記載の方法。
4. 該再帰的マージナライゼーション結合演算がｍｉｎ^＊−ｓｕｍ演算を含む請求項２に記載の方法。
5. ｍｉｎ^＊＝ｍｉｎ（ｘ、ｙ）−ｌｎ（１＋ｅ^{−｜ｘ−ｙ｜}）である請求項４に記載の方法。
6. 該再帰的マージナライゼーション結合演算がｓｕｍ−ｐｒｏｄｕｃｔ演算を含む請求項２に記載の方法。
7. 該再帰的マージナライゼーション結合演算がｍａｘ−ｐｒｏｄｕｃｔ演算を含む請求項２に記載の方法。
8. 該符号化信号が、ターボ符号化信号、ブロックターボ符号化信号、低密度パリティチェック符号化信号、積符号化信号及び畳みこみ符号化信号のうち少なくとも一つを含む請求項１に記載の方法。
9. 該符号化信号が、並列連結畳みこみ符号及び直列連結畳みこみ符号のうちの少なくとも一つを含む請求項１に記載の方法。
10. 反復復号法を無線通信システムで使用することをさらに含む請求項１に記載の方法。
11. 予め定められた状態が起こったときに、該反復処理を停止することをさらに含む請求項１に記載の方法。
12. 該反復処理が、並列プレフィックス演算又は並列サフィックス演算又は両演算を、ソフト情報に対して実行することを含む請求項１に記載の方法。
13. 該反復処理が、第一ＳＩＳＯのソフト出力を、もう一つのＳＩＳＯに対するソフト入力として使用することを含む請求項１に記載の方法。
14. 少なくとも一つのＳＩＳＯによって使用される木構造が、待ち時間がＯ（ｌｏｇ_２Ｎ）（但しＮはブロックサイズである）のＳＩＳＯをもたらす木構造を含む請求項１に記載の方法。
15. 少なくとも一つのＳＩＳＯによって使用される木構造がＢｒｅｎｔ−Ｋｕｎｇの木を含む請求項１に記載の方法。
16. 少なくとも一つのＳＩＳＯによって使用される木構造が順方向−逆方向の木を含む請求項１に記載の方法。
17. 該順方向−逆方向の木が、二方向性の木構造再帰を含む請求項１６に記載の方法。
18. 少なくとも一つのＳＩＳＯによって実行される反復処理が、観測インターバルをサブインターバル中にタイルし、次いで最小ハーフウィンドウＳＩＳＯ演算を、各サブインターバルに適用する、
    ことを含む請求項１に記載の方法。
19. 該反復処理が、ソフト情報の上にセミ−リングを形成するマージナライゼーション結合演算を実行することを含む請求項１に記載の方法。
20. 番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うための木構造中に配列されかつ順方向と逆方向の状態メトリクスを計算するように構成された複数の融合モジュールを含むソフトイン／ソフトアウト（ＳＩＳＯ）モジュールであって、
    各融合モジュールが下記式：
    

    

    （式中、Ｃ（ｋ、ｍ）はｓ_ｋとｓ_ｍの間のソフト入力に基づいた状態ペアｓ_ｋとｓ_ｍの最小シーケンスメトリクス（ＭＳＭ）のマトリックスである）で定義されるソフトイン／ソフトアウト（ＳＩＳＯ）モジュール。
21. 該複数の融合モジュールのうちの少なくとも一つが、再帰的マージナライゼーション結合演算を実行することによって、順方向と逆方向の状態メトリクスを計算する請求項２０に記載のＳＩＳＯモジュール。
22. 該再帰的マージナライゼーション結合演算がｍｉｎ−ｓｕｍ演算を含む請求項２１に記載のＳＩＳＯモジュール。
23. 該再帰的マージナライゼーション結合演算がｍｉｎ^＊−ｓｕｍ演算を含む請求項２１に記載のＳＩＳＯモジュール。
24. ｍｉｎ^＊＝ｍｉｎ（ｘ、ｙ）−ｌｎ（１＋ｅ^{−｜ｘ−ｙ｜}）である請求項２１に記載のＳＩＳＯモジュール。
25. 該再帰的マージナライゼーション結合演算がｓｕｍ−ｐｒｏｄｕｃｔ演算を含む請求項２１に記載のＳＩＳＯモジュール。
26. 該再帰的マージナライゼーション結合演算がｍａｘ−ｐｒｏｄｕｃｔ演算を含む請求項２１に記載のＳＩＳＯモジュール。
27. 順方向と逆方向の両方のマージナライゼーション結合演算を実行するための１又は２以上の完全融合モジュール（ＣＦＭ）、
    順方向だけのマージナライゼーション結合演算を実行するための１又は２以上の順方向融合モジュール（ｆＦＭ）、及び
    逆方向だけのマージナライゼーション結合演算を実行するための１又は２以上の逆方向融合モジュール（ｂＦＭ）、
    を含み、
    その１又は２以上のＣＦＭ、ｆＦＭ及びｂＦＭが、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うための木構造に配列されている、ソフトイン／ソフトアウト（ＳＩＳＯ）モジュール。
28. ＣＦＭの数が、ソフトインバースを計算するのに必要な最小限の数である請求項２７に記載のＳＩＳＯモジュール。
29. ｆＦＭとｂＦＭが、可能な場合はいつでも、ＣＦＭの代わりに木構造中に使用される請求項２８に記載のＳＩＳＯモジュール。
30. 該融合モジュールの１又は２以上によって実行されるマージナライゼーション結合演算がｍｉｎ−ｓｕｍ演算を含む請求項２７に記載のＳＩＳＯモジュール。
31. 該再帰的マージナライゼーション結合演算がｍｉｎ^＊−ｓｕｍ演算を含む請求項２７に記載のＳＩＳＯモジュール。
32. ｍｉｎ^＊＝ｍｉｎ（ｘ、ｙ）−ｌｎ（１＋ｅ^{−｜ｘ−ｙ｜}）である請求項３１に記載のＳＩＳＯモジュール。
33. 該再帰的マージナライゼーション結合演算がｓｕｍ−ｐｒｏｄｕｃｔ演算を含む請求項２７に記載のＳＩＳＯモジュール。
34. 該再帰的マージナライゼーション結合演算がｍａｘ−ｐｒｏｄｕｃｔ演算を含む請求項２７に記載のＳＩＳＯモジュール。
35. 該木構造が、Ｂｒｅｎｔ−Ｋｕｎｇの木及び順方向−逆方向の木（ＦＢＴ）のうち少なくとも一つを含む請求項２７に記載のＳＩＳＯモジュール。
36. 有限状態機械（ＦＳＭ）の１又は２以上の出力に対応する入力信号を受信し、次いで
    番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うように構成された木構造を使用して上記受信した入力信号の順方向と逆方向の状態メトリクスを計算することによって、上記ＦＳＭのソフトインバースを求める、
    ことを含む反復検出方法。
37. 該順方向と逆方向の状態メトリクスが、少なくとも一つのソフトイン／ソフトアウト（ＳＩＳＯ）モジュールによって計算される請求項３６に記載の方法。
38. 該順方向と逆方向の状態メトリクスが、マージナライゼーション結合演算の木構造化セットを使用して計算される請求項３６に記載の方法。
39. 該マージナライゼーション結合演算がｍｉｎ−ｓｕｍ演算を含む請求項３８に記載の方法。
40. 該マージナライゼーション結合演算がｍｉｎ^＊−ｓｕｍ演算を含む請求項３８に記載の方法。
41. ｍｉｎ^＊＝ｍｉｎ（ｘ、ｙ）−ｌｎ（１＋ｅ^{−｜ｘ−ｙ｜}）である請求項４０に記載の方法。
42. 該マージナライゼーション結合演算がｓｕｍ−ｐｒｏｄｕｃｔ演算を含む請求項３８に記載の方法。
43. 該マージナライゼーション結合演算がｍａｘ−ｐｒｏｄｕｃｔ演算を含む請求項３８に記載の方法。
44. 該入力信号が、ターボ符号化信号と畳みこみ符号化信号のうちの少なくとも一つを含む請求項３６に記載の方法。
45. 該入力信号が、並列連結畳みこみ符号化信号及び直列連結畳みこみ符号化信号のうちの少なくとも一つを含む請求項３６に記載の方法。
46. ＦＳＭの該ソフトインバースを求めることが、ソフト情報を反復して処理することを含む請求項３６に記載の方法。
47. 該反復処理が、並列プレフィックス演算又は並列サフィックス演算又は両方の演算を、該ソフト情報に対して実行することを含む請求項４６に記載の方法。
48. 該反復処理が、第一ＳＩＳＯのソフト出力を、もう一つのＳＩＳＯに対するソフト入力として使用することを含む請求項４６に記載の方法。
49. 使用される木構造が、待ち時間がＯ（ｌｏｇ_２Ｎ）（但しＮはブロックサイズである）のＳＩＳＯモジュールをもたらす木構造を含む請求項３７に記載の方法。
50. 該木構造がＢｒｅｎｔ−Ｋｕｎｇの木を含む請求項３６に記載の方法。
51. 該木構造が順方向−逆方向の木を含む請求項３６に記載の方法。
52. 該順方向−逆方向の木が、二方向性の木構造再帰を含む請求項５１に記載の方法。
53. 該少なくとも一つのＳＩＳＯが、さらに、
    観測インターバルをサブインターバル中にタイルし、次いで
    最小ハーフウィンドウＳＩＳＯ演算を各サブインターバルに適用する、
    請求項３７に記載の方法。
54. 有限状態機械（ＦＳＭ）によって符号化された信号を入力として受信しその受信した信号に関するソフト情報を生成するよう構成された復調器、及び
    上記復調器と交信かつ上記ＦＳＭのソフトインバースを、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うように構成された木構造を利用して計算するよう構成された少なくとも一つのソフトイン／ソフトアウト（ＳＩＳＯ）モジュール、
    を含むターボ復号器。
55. 該木構造が、並列プレフィックス演算と並列サフィックス演算を組み合わせて実行する請求項５４に記載の復号器。
56. 互いに交信する少なくとも二つのＳＩＳＯモジュールをさらに含み、それらＳＩＳＯモジュールが、復号された信号のソフト情報推定を反復して交換する請求項５４に記載の復号器。
57. 上記少なくとも一つのＳＩＳＯが、該受信された信号の順方向と逆方向の状態メトリクスを計算することによって、該ＦＳＭのソフトインバースを計算する請求項５４に記載の復号器。
58. 上記少なくとも一つのＳＩＳＯの使用する木構造が、待ち時間がＯ（ｌｏｇ_２Ｎ）（但しＮはブロックサイズである）のＳＩＳＯをもたらす木構造を含む請求項５４に記載の復号器。
59. 上記少なくとも一つのＳＩＳＯの使用する木構造がＢｒｅｎｔ−Ｋｕｎｇの木を含む請求項５４に記載の復号器。
60. 上記少なくとも一つのＳＩＳＯの使用する木構造が、順方向−逆方向の木（ＦＢＴ）を含む請求項５４に記載の復号器。
61. １又は２以上のブロック符号化モジュールからの出力に対応する入力信号を受信し、次いで
    上記受信された入力信号の順方向と逆方向の状態メトリクスを、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うように構成された木構造を使用して計算することによって、上記１又は２以上のブロック符号化モジュールのソフトインバースを求める、ことを含む反復検出方法。
62. 該順方向と逆方向の状態メトリクスが、少なくとも一つのソフトイン／ソフトアウト（ＳＩＳＯ）モジュールによって計算される請求項６１に記載の方法。
63. 該順方向と逆方向の状態メトリクスが、マージナライゼーション結合演算の木構造化セットを使用して計算される請求項６１に記載の方法。
64. 該マージナライゼーション結合演算がｍｉｎ−ｓｕｍ演算を含む請求項６３に記載の方法。
65. 該マージナライゼーション結合演算がｍｉｎ^＊−ｓｕｍ演算を含む請求項６３に記載の方法。
66. ｍｉｎ^＊＝ｍｉｎ（ｘ、ｙ）−ｌｎ（１＋ｅ^{−｜ｘ−ｙ｜}）である請求項６５に記載の方法。
67. 該マージナライゼーション結合演算がｓｕｍ−ｐｒｏｄｕｃｔ演算を含む請求項６３に記載の方法。
68. 該マージナライゼーション結合演算がｍａｘ−ｐｒｏｄｕｃｔ演算を含む請求項６３に記載の方法。
69. 該入力信号が、ブロックターボ符号化信号、低密度パリティチェック符号化信号及び積符号化信号のうちの少なくとも一つを含む請求項６１に記載の方法。
70. １又は２以上の該ブロック符号化モジュールのソフトインバースを求めることが、ソフト情報を反復処理することを含む請求項６１に記載の方法。
71. 該反復処理が、並列プレフィックス演算又は並列サフィックス演算又は両方の演算を、該ソフト情報に対して実行することを含む請求項７０に記載の方法。
72. 該反復処理が、第一ＳＩＳＯのソフト出力を、もう一つのＳＩＳＯに対するソフト入力として使用することを含む請求項７０に記載の方法。
73. 使用される木構造が、待ち時間がＯ（ｌｏｇ_２Ｎ）（但しＮはブロックサイズである）のＳＩＳＯモジュールをもたらす木構造を含む請求項６１に記載の方法。
74. 該木構造がＢｒｅｎｔ−Ｋｕｎｇの木を含む請求項６１に記載の方法。
75. 該木構造が順方向−逆方向の木を含む請求項６１に記載の方法。
76. 該順方向−逆方向の木が二方向性の木構造再帰を含む請求項７５に記載の方法。
77. 該少なくとも一つのＳＩＳＯが、さらに、
    観測インターバルをサブインターバル中にタイルし、次いで
    最小ハーフウィンドウＳＩＳＯ演算を各サブインターバルに適用する、
    請求項６２に記載の方法。
78. ブロック符号化モジュールによって符号化された信号を入力として受信し次いでその受信した信号に関するソフト情報を生成するよう構成された復調器、及び
    上記復調器と交信しかつ上記ブロック符号化モジュールのソフトインバースを、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うように構成された木構造を利用して計算するよう構成された少なくとも一つのソフトイン／ソフトアウト（ＳＩＳＯ）モジュール、
    を含むブロック復号器。
79. 該木構造が、並列プレフィックス演算と並列サフィックス演算を組み合わせて実行する請求項７８に記載の復合器。
80. 互いに交信する少なくとも二つのＳＩＳＯモジュールをさらに含み、そのＳＩＳＯモジュールが、復号された信号のソフト情報推定を反復して交換する請求項７８に記載の復号器。
81. 少なくとも一つのＳＩＳＯが、受信した信号の順方向と逆方向の状態メトリクスを計算することによって、ブロック符号化モジュールのソフトインバースを計算する請求項７８に記載の復号器。
82. 少なくとも一つのＳＩＳＯによって使用される木構造が、待ち時間がＯ（ｌｏｇ_２Ｎ）（但しＮはブロックサイズである）のＳＩＳＯをもたらす木構造を含む請求項７８に記載の復合器。
83. 少なくとも一つのＳＩＳＯによって使用される木構造がＢｒｅｎｔ−Ｋｕｎｇの木を含む請求項７８に記載の復号器。
84. 少なくとも一つのＳＩＳＯによって使用される木構造が順方向−逆方向の木（ＦＢＴ）を含む請求項７８に記載の復号器。
85. モジュールの１又は２以上の出力に対応する入力信号を受信し、そのモジュールのソフトインバースは順方向−逆方向のアルゴリズムを該モジュールのトレリス表現に対して実行することによって計算することができ、次いで
    上記受信した入力信号の順方向と逆方向の状態メトリクスを、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算と、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算とを行うように構成された木構造を利用して計算することによって、上記モジュールのソフトインバースを求める、
    ことを含む反復検出方法。
86. 該入力信号が、ブロック誤り訂正符号化信号、ブロックターボ符号化信号、低密度パリティチェック符号化信号、及び積符号化信号のうち少なくとも一つを含む請求項８５に記載の方法。
87. 該入力信号が、ターボ符号化信号及び畳みこみ符号化のうち少なくとも一つを含む請求項８５に記載の方法。
88. 該符号化信号が、並列の連結畳みこみ符号及び直列の連結畳みこみ符号のうち少なくとも一つを含む請求項８５に記載の方法。
89. 該モジュールが有限状態機械を含んでいる請求項８５に記載の方法。
90. 該モジュールがブロック符号化モジュールを含んでいる請求項８５に記載の方法。
91. 符号化信号を受信し、
    その受信した符号化信号を復調してソフト情報を生成させ、次いで
    そのソフト情報を１又は２以上のソフトイン／ソフトアウトプット（ＳＩＳＯ）モジュールで反復処理し、少なくとも一つのＳＩＳＯモジュールが、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算を行うための木構造を利用して順方向の状態メトリクスを計算する、
    ことを含む復号方法。
92. 該木構造が、逆方向の状態メトリクスを計算するために、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算を更に行うように構成された請求項９１に記載の方法。
93. 有限状態機械（ＦＳＭ）の１又は２以上の出力に対応する入力信号を受信し、次いで
    番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算を行うように構成された木構造を使用して上記受信した入力信号の順方向の状態メトリクスを計算することによって、上記ＦＳＭのソフトインバースを求める、
    ことを含む反復検出方法。
94. 該木構造が、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算を更に行うように構成され、
    上記ＦＳＭのソフトインバースを求めることは、該木構造を使用して上記受信した入力信号の逆方向の状態メトリクスを計算することによって上記ＦＳＭのソフトインバースを求めることを更に含む請求項９３に記載の方法。
95. 有限状態機械（ＦＳＭ）によって符号化された信号を入力として受信しその受信した信号に関するソフト情報を生成するよう構成された復調器、及び
    上記復調器と交信かつ上記ＦＳＭのソフトインバースを、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算を行うように構成された木構造を利用して計算するよう構成された少なくとも一つのソフトイン／ソフトアウト（ＳＩＳＯ）モジュール、
    を含むターボ復号器。
96. 該木構造が、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算を更に行うように構成された請求項９５に記載の複合器。
97. １又は２以上のブロック符号化モジュールからの出力に対応する入力信号を受信し、次いで
    上記受信された入力信号の順方向の状態メトリクスを、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算を行うように構成された木構造を使用して計算することによって、上記１又は２以上のブロック符号化モジュールのソフトインバースを求める、ことを含む反復検出方法。
98. 該木構造が、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算を更に行うように構成され、
    上記１又は２以上のブロック符号化モジュールのソフトインバースを求めることは、該木構造を使用して上記受信した入力信号の逆方向の状態メトリクスを計算することによって上記１又は２以上のブロック符号化モジュールのソフトインバースを求めることを更に含む請求項９７に記載の方法。
99. ブロック符号化モジュールによって符号化された信号を入力として受信し次いでその受信した信号に関するソフト情報を生成するよう構成された復調器、及び
    上記復調器と交信しかつ上記ブロック符号化モジュールのソフトインバースを、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算を行うための木構造を利用して計算するよう構成された少なくとも一つのソフトイン／ソフトアウト（ＳＩＳＯ）モジュール、
    を含むブロック復号器。
100. 該木構造が、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算を更に行うように構成された請求項９９に記載の複合器。
101. モジュールの１又は２以上の出力に対応する入力信号を受信し、そのモジュールのソフトインバースは順方向−逆方向のアルゴリズムを該モジュールのトレリス表現に対して実行することによって計算することができ、次いで
     上記受信した入力信号の順方向の状態メトリクスを、番号付けされた複数の入力を行って番号付けされた複数の出力を最下位番号の出力から最上位番号の出力まで順に生成する並列のプレフィックス演算を行うように構成された木構造を利用して計算することによって、上記モジュールのソフトインバースを求める、
     ことを含む反復検出方法。
102. 該木構造が、番号付けされた複数の入力を行って番号付けされた複数の出力を最上位番号の出力から最下位番号の出力まで順に生成する並列のサフィックス演算を更に行うように構成され、
     上記モジュールのソフトインバースを求めることは、該木構造を使用して上記受信した入力信号の逆方向の状態メトリクスを計算することによって上記モジュールのソフトインバースを求めることを更に含む請求項１０１に記載の方法。

Images