(57)【要約】パイプライン最大事後確率（ＭＡＰ）復号器アーキテクチャのためのスライディングウインドウ法を、処理時間を減少させるために修正する。一旦、フォワードメトリックが復号器の第１スライディングウインドウに対して計算されると、次のウインドウに対するフォワードメトリックが計算されている間に、それぞれのウインドウに対するリバースメトリックが計算される。それぞれの新しいフォワードメトリックが計算され、メモリ（１４）に格納されたときに、計算されたリバースメトリックとともに、外部値を計算することにおいて使用するために、以前のウインドウからのフォワードメトリックがメモリ（１４）から読み出される。外部値を計算することにおいて使用するための各フォワードメトリックは、新しいフォワードメトリックが書き込まれたのと同一のクロックエッジで同一のメモリ位置から読み出される。この構成は、ターボ復号器のために開発されたが、すべてのコンボリューション符号で本発明のＭＡＰアルゴリズムを使うことができる。
2005503058.tif 000002
【特許請求の範囲】
【請求項１】
受信された信号の２値状態を判定する出力計算を実行するために必要とされるフォワードおよびリバースメトリックを計算する方法であって、
（ａ）前記フォワードメトリック計算を２つのステージで実行するステップであって、前記フォワードメトリック計算の第１グループを第１ステージにおいて計算し、引き続いて前記フォワードメトリック計算の第２グループを第２ステージにおいて計算するステップと、
（ｂ）リバースメトリック値と共に使用するために、前記第１ステージの間に計算された前記フォワードメトリックをメモリから読み出し、前記出力計算を実行するステップと、
（ｃ）前記第１ステージに引き続いて、前記第２ステージにおいて前記リバースメトリック計算を実行するステップと、
（ｄ）前記リバース計算が実行されているときに、フォワードメトリック計算の後半を実行するステップと、
（ｅ）前記第１ステージにおいて実行された前記フォワードメトリック計算のそれぞれを格納するステップと、
（ｆ）前記第１ステージの間に計算されたフォワードメトリックが出力計算において使用するために読み出されたメモリ位置に、前記第２ステージの間に計算された各フォワードメトリックを書き込むステップと
を備えることを特徴とする方法。
【請求項２】
前記第１ステージにおいて計算された前記フォワードメトリックおよび前記第２ステージにおいて計算された前記リバースメトリックを利用して出力計算を実行するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項３】
ステップ（ｅ）およびステップ（ｆ）は、クロック信号の共通のクロックエッジを適用することにより実行されることを特徴とする請求項１に記載の方法。
【請求項４】
前記第２ステージにおいて計算された前記フォワードメトリックとともに使用するために、前記第２ステージに引き続く第３ステージにおいてリバースメトリックを実行し、前記第２ステージの間に計算された前記フォワードメトリックおよび前記第３ステージの間に計算された前記リバースメトリックを利用して出力計算を実行するステップをさらに備えることを特徴とする請求項２に記載の方法。
【請求項５】
データビットおよび関連付けられたパリティビットを含み、かつ伝送チャネルにおける雑音により乱されている可能性がある、遠隔地から受信された前記伝送信号を復号する方法であって、
（ａ）第１の時間間隔の間に、送信地から受信されたそれぞれのデータビットおよびその付随するパリティビットに対するフォワードメトリック値を計算するステップと、
（ｂ）それぞれのフォワードメトリック値を第１のメモリに格納するステップと、
（ｃ）受信されたデータビットおよび付随するパリティビットのそれぞれをそれらが受信されたときにローカルメモリに格納するステップと、
（ｄ）外部値を計算するために、第２の時間間隔の間に前記第１のメモリからフォワードメトリック値を読み出すステップと、
（ｅ）前記第２の時間間隔の間にリバースメトリック値を計算するために、以前にメモリに格納されていた前記データビットおよび付随するパリティビットを利用するステップと、
（ｆ）前記第２の時間間隔の間に、前記第２の時間間隔の間に受信されたデータビットおよび付随するパリティビットに対するフォワードメトリック値を計算し、およびステップ（ｄ）の間に、そこからフォワードメトリック値が読み出されたメモリ位置に、前記第２の時間間隔の間に計算された各フォワードメトリック値を格納するステップと
を備えることを特徴とする方法。
【請求項６】
ステップ（ｃ）の間に前記ローカルメモリに読み込まれた前記データビットおよび付随するパリティビットは、前記リバースメトリックの計算において使用するため、前記ローカルメモリから逆の順序で読み出されることを特徴とする請求項５に記載の方法。
【請求項７】
前記計算されたフォワードメトリック値は、前記外部値の計算において使用するため、前記フォワードメトリック値が読み込まれた順序と逆の順序でメモリから読み出されることを特徴とする請求項５に記載の方法。
【請求項８】
ステップ（ａ）は、前記第１の時間間隔の間にフォワードメトリック値を計算する前に、前記データビットおよび付随するパリティビットに関するガンマ計算を実行することをさらに備えることを特徴とする請求項５に記載の方法。
【請求項９】
所定のフォワードメトリック値、所定のリバースメトリック値、および所定のデータビットならびに付随するパリティビットに基づいて、初期外部値を計算するステップをさらに備えることを特徴とする請求項５に記載の方法。
【請求項１０】
前記外部値は、外部メモリに格納されることを特徴とする請求項９に記載の方法。
【請求項１１】
前記外部値を格納するステップは、格納された前記外部値を計算するために利用された前記データビットに結合されたメモリ位置に、前記内部値を格納することを含むことを特徴とする請求項９に記載の方法。
【請求項１２】
前記データビットおよび付随するパリティビットを前記ローカルメモリから抽出するステップと、
前記外部値の計算において使用するために、前記第２の時間間隔の間に、前記データビットおよび付随するパリティビットに関するガンマ計算を実行するステップと
をさらに備えることを特徴とする請求項１０に記載の方法。
【請求項１３】
前記第２の時間間隔の間に前記ローカルメモリから読み出されたデータビットおよび付随するパリティビットを、前記初期外部値から差し引いて、最終の外部値を得るステップをさらに備えることを特徴とする請求項１２に記載の方法。
【請求項１４】
前記外部値計算器の前記出力データの２値状態を判定し、前記２値状態に関する硬判定を行うステップと、
前記硬判定出力をメモリに格納するステップと
をさらに備えたことを特徴とする請求項１２に記載の方法。
【請求項１５】
それぞれ付随するパリティビットを伴い、かつ雑音により乱されている可能性があるデータビットを受信するターボ復号器を動作させる方法であって、
（ａ）２つの連続した時間間隔においてフォワードメトリック計算を実行するステップであって、フォワードメトリック計算の１つのグループが、第２の時間間隔を伴う第１の時間間隔において計算されるステップと、
（ｂ）前記第１の時間間隔の間に実行された前記フォワードメトリック計算のそれぞれを格納するステップと、
（ｃ）外部値計算においてリバースメトリック値とともに使用するために、前記第１の時間間隔の間に計算されたそれぞれのフォワードメトリック値をメモリから読み出すステップと、
（ｄ）前記第２の時間間隔の間で、かつ前記第１の時間間隔の間に実行された前記フォワードメトリック計算の完了の後に、リバースメトリック計算を実行するステップと、
（ｅ）前記第１の時間間隔の間に計算されたフォワードメトリック値がメモリから読み出されたメモリ位置に、前記第２の時間間隔の間に計算された各フォワードメトリック値を書き込むステップと
を備えることを特徴とする方法。
【請求項１６】
受信された信号の２値状態を判定するための計算を実行するために必要とされるフォワードおよびリバースメトリックを計算する方法であって、
（ａ）外部メモリにおけるメモリ位置を生成するステップと、
（ｂ）雑音またはこれと同様なものにより乱されている可能性があるデータビットおよび付随するパリティビットを備える信号を受信するステップと、
（ｃ）前記データビット、付随するパリティビット、メモリ位置、および初期外部値を格納するステップと、
（ｄ）前記データビット、付随するパリティビット、および初期外部値に基づいて第１組のフォワードメトリック値を計算するステップと、
（ｅ）計算された前記フォワードメトリック値をフォワードメトリックメモリに格納するステップと、
（ｆ）外部値計算においてリバースメトリック値とともに使用するために、計算された前記フォワードメトリック値をメモリから読み出すステップと、
（ｇ）前記リバースメトリック値が計算されている間に、第２組のフォワードメトリック値を計算するためにステップ（ａ）からステップ（ｃ）を実行するステップと、
（ｈ）リバースメトリック値計算において使用するために、前記第１組のフォワードメトリック値の１つが読み出された位置と同一のメモリ位置に、前記第２組のフォワードメトリック値のそれぞれを格納するステップと
を備えることを特徴とする方法。
【請求項１７】
リバースメトリック値の計算のために、前記フォワードメトリック値がメモリに読み込まれた順序とは逆の順序でメモリから前記フォワードメトリック値を読み出すステップをさらに備えることを特徴とする請求項１６に記載の方法。
【請求項１８】
受信された信号の２値状態を判定するための計算を実行するために要求されたフォワードメトリック（α）およびリバースメトリック（β）を計算するための方法であって、
（ａ）信号が雑音またはこれと同様なものにより乱されている可能性があり、それぞれ付随するパリティビットを有するデータビットを備える信号を受信するステップと、
（ｂ）外部値を格納するために外部メモリにおけるメモリ位置を生成するステップと、
（ｃ）第１のデータビット、付随するパリティビット、メモリ位置、および初期外部値を第１のメモリに格納するステップと、
（ｄ）前記データビット、付随するパリティビット、および初期外部値に基づいて第１のフォワードメトリック値を計算するステップと、
（ｅ）計算された前記フォワードメトリック値をフォワードメトリックメモリに格納するステップと、
（ｆ）外部値計算においてリバースメトリックとともに使用するために、計算された前記フォワードメトリック値を前記フォワードメトリックメモリから読み出すステップと、
（ｇ）前記リバースメトリック値が計算されている間に、第２組のフォワードメトリック値の前記第１のフォワードメトリック値を計算するためにステップ（ａ）からステップ（ｃ）を実行するステップと、
（ｈ）リバースメトリック値計算において使用するために、前記第１組のフォワードメトリック値の１つが読み出された位置と同一のメモリ位置に、前記第２組のフォワードメトリック値の前記第１のフォワードメトリック値を格納するステップと
を備えることを特徴とする方法。
【請求項１９】
受信された信号の２値状態を判定するための計算を実行するために要求されたフォワードおよびリバースメトリックを計算するためのターボ復号器であって、
外部メモリと、
前記外部メモリにおけるメモリ位置を生成する第１手段と、
雑音またはこれと同様なものにより乱されている可能性がある、それぞれ付随するパリティビットパリティビットを有するデータビットを備える信号を受信する第２手段と、
前記データビット、付随するパリティビット、およびメモリ位置を格納する第３手段と、
前記データビット、付随するパリティビット、および初期外部値に基づいて第１組のフォワードメトリック値を計算する第４手段と、
計算された前記フォワードメトリック値をフォワードメトリックメモリに格納する第５手段と、
外部値計算においてリバースメトリックとともに使用するために、計算された前記フォワードメトリック値を前記フォワードメトリックメモリから読み出す第６手段とを備え、
前記リバースメトリック値が計算されている間に、前記第１、第２および第３の手段が、第２組のフォワードメトリック値を計算し、
前記第５の手段が、外部値計算において使用するために、前記第１組のフォワードメトリック値の１つが読み出された位置と同一な前記フォワードメトリックメモリのメモリ位置に、前記第２組のフォワードメトリック値の１つを格納するための手段を含むことを特徴とするターボ復号器。
【請求項２０】
受信された信号の２値状態を判定するための計算を実行するために要求されたフォワードおよびリバースメトリックを計算するためのターボ復号器において使用するための格納方法であって、
（ａ）フォワードメトリック値の第１グループをメモリにおいて所定の順序で格納するステップと、
（ｂ）最後に計算されたものから最初に計算されたものへの順序で格納されたメトリック値を読み出すステップと、
（ｃ）所定の順序でフォワードメトリック値の第２のグループを格納することにより、前記第２グループの最初に計算されたフォワードメトリック値が、前記第２のグループの最後に計算されたメトリック値が読み出されたメモリ位置に格納されるステップと
を備えることを特徴とする格納方法。
【請求項２１】
メモリから読み出された前記フォワードメトリック値に基づいてリバースメトリック値を計算するステップをさらに備えることを特徴とする請求項２０に記載の格納方法。
【請求項２２】
受信された信号の２値状態を判定するための計算を実行するために要求されたフォワードおよびリバースメトリックを計算するためのターボ復号器において使用するための装置であって、
データビットおよび付随するパリティビットを格納する第１のメモリと、
フォワードメトリックメモリと、
前記データビットおよび付随するパリティビットに基づいてフォワードメトリック値の第１グループを計算する手段と、
フォワードメトリック値の前記第１グループを前記メモリにおいて所定の順序で格納する手段と、
格納されたメトリック値の前記第１グループを、最後に計算されたものから最初に計算されたものへの順序で前記メモリから読み出す手段と、
前記計算する手段を制御して、メトリック値の前記第１のグループの計算に引き続く、フォワードメトリック値の第２グループを計算する手段と、
所定の順序で、フォワードメトリック値の前記第２グループを前記フォワードメトリックメモリに格納することにより、前記第２グループの最初に計算されたフォワードメトリック値を、前記第１グループの最後に計算されたメトリック値が読み出されたメモリ位置に格納する手段と
を備えることを特徴とする装置。
【請求項２３】
フォワードメトリック値の前記第１のグループの計算の間に、前記第１のメモリから読み出された前記データビットおよび付随するパリティビットに基づくリバースメトリック値を計算する第２手段をさらに備えることを特徴とする請求項２２に記載の装置。
【請求項２４】
受信された信号の２値状態を判定するための出力計算を実行するために要求されたフォワードおよびリバースメトリックを計算するための方法であって、
（ａ）前記リバースメトリック計算を２つのステージで実行するステップであって、前記リバースメトリック計算の１つのグループが第１ステージにおいて計算され、引き続きリバースメトリック計算の第２グループが第２ステージにおいて計算されるステップと、
（ｂ）前記第１ステージにおいて実行された前記リバースメトリック計算のそれぞれを格納するステップと、
（ｃ）前記出力計算において使用するため、前記第１ステージの間に計算された前記リバースメトリック値をメモリから読み出すステップと、
（ｄ）リバースメトリック計算の前記第１ステージの完了の後で、かつリバースメトリック計算の前記第２ステージの前に、前記フォワードメトリック計算を実行するステップと、
（ｅ）前記第１ステージの間に計算されたリバースメトリックが出力計算において使用するため読み出されたメモリ位置に、前記第２ステージの間に計算された各リバースメトリックを書き込むステップと
を備えることを特徴とする方法。
【請求項２５】
前記第１ステージにおいて計算された前記リバースメトリックおよび前記第２ステージにおいて計算された前記フォワードメトリックを利用して出力計算を実行するステップをさらに備えることを特徴とする請求項２４に記載の方法。
【請求項２６】
ステップ（ｃ）およびステップ（ｅ）は、クロック信号の共通のクロックエッジを適用して実行されることを特徴とする請求項２４に記載の方法。
【請求項２７】
前記第２ステージに引き続く第３ステージにおいて、前記第２ステージにおいて計算された前記リバースメトリックに対応するフォワードメトリックを実行するステップと、
前記第２ステージの間に計算された前記リバースメトリック値および前記第３ステージの間に計算された前記フォワードメトリック値を利用して出力計算を実行するステップと
をさらに備えることを特徴とする請求項２５に記載の方法。
【請求項２８】
データビットおよび関連付けられたパリティビットを含み、かつ伝送チャネルにおける雑音により乱されている可能性がある、遠隔地から受信された前記伝送信号を復号するための方法であって、
（ａ）第１の時間間隔の間に、送信地から受信されたそれぞれのデータビットおよびその付随するパリティビットに対するリバースメトリック値を計算するステップと、
（ｂ）各リバースメトリック値を第１のメモリに格納するステップと、
（ｃ）それぞれの受信されたデータビットおよび付随するパリティビットをそれらが受信されたときにローカルメモリに格納するステップと、
（ｄ）外部値を計算する際に使用するために、前記第１のメモリからリバースメトリック値を読み出すステップと、
（ｅ）フォワードメトリック値を計算するために、以前に前記ローカルメモリに格納されている前記データビットおよび付随するパリティビットを利用するステップと、
（ｆ）第２の時間間隔の間に、前記第２の時間間隔の間に受信されたデータビットおよび付随するパリティビットに対するリバースメトリック値を計算し、かつステップ（ｄ）の間に、そこからリバースメトリック値が読み出された前記第１のメモリのメモリ位置に、前記第２の時間間隔の間に計算された各リバースメトリック値を格納するステップと
を備えることを特徴とする方法。
【請求項２９】
前記外部値を計算する際に使用するために、ステップ（ｃ）の間に前記ローカルメモリに読み込まれた前記データビットおよび付随するパリティビットが、前記ローカルメモリから逆の順序で読み出されることを特徴とする請求項２８に記載の方法。
【請求項３０】
前記第２の時間間隔において計算された前記リバースメトリック値がメモリに読み込まれた順序とは逆の順序で、前記第１の時間間隔において計算された前記リバースメトリック値がメモリから読み出されることを特徴とする請求項２９に記載の方法。
【請求項３１】
所定のフォワードメトリック値、所定のリバースメトリック値、および所定のデータビットおよび付随するパリティビットに基づいて外部値を計算するステップをさらに備えることを特徴とする請求項２９に記載の方法。
【請求項３２】
受信された信号の２値状態を判定する計算を実行するために必要とされたフォワードおよびリバースメトリックを計算するための方法であって、
（ａ）第１ステージの間にフォワードメトリック計算の第１グループを実行すること、
（ｂ）フォワードメトリック値の前記第１グループをメモリに格納すること、
（ｃ）前記第１ステージに引き続く第２ステージの間にリバースメトリック計算を実行すること、
（ｄ）前記第２ステージの間にリバースメトリック値が計算されるときに、フォワードメトリック計算の第２グループを実行すること、
（ｅ）前記受信された信号の２値状態を判定する計算を実行するために、前記第２ステージの間に計算された前記リバースメトリック値とともに使用するために、メモリにおける位置から前記第１グループのフォワードメトリック値を読み出すこと、および
（ｆ）前記第２ステージにおいて前記リバースメトリック値が計算されている時間の間にフォワードメトリック値の前記第２グループの計算を格納することにより、前記第２ステージの間に計算された各フォワードメトリック値が、前記第１ステージの間に計算されたフォワードメトリック値が、前記受信された信号の２値状態を判定する計算を実行することにおいて使用するために読み出された位置と同一の位置に格納されること
を備えることを特徴とする方法。
【請求項３３】
受け取られた信号の２値状態を判定するための出力計算を実行するために要求されたフォワードおよびリバースメトリックを計算するための装置であって、
前記リバースメトリック計算を２つのステージで実行する手段であって、リバースメトリック計算の１つのグループを第１ステージにおいて計算し、引き続いてリバースメトリック計算の第２グループを第２ステージにおいて計算する手段と、
前記第１ステージにおいて実行された前記リバースメトリック計算のそれぞれを格納する手段と、
前記第１ステージの間に計算された前記リバースメトリック値を、前記出力計算において使用するためにメモリから読み出す手段と、
リバースメトリック計算の前記第１ステージの完了の後で、かつリバースメトリック計算の前記第２ステージの前に、前記フォワードメトリック計算を実行する手段と、
前記第１ステージの間に計算されたリバースメトリックが出力計算において使用するために読み出されたメモリ位置に、前記第２ステージの間に計算された各リバースメトリックを書き込む手段と
を備えることを特徴とする装置。
【請求項３４】
前記第１ステージにおいて計算された前記リバースメトリックおよび前記第２ステージにおいて計算された前記フォワードメトリックを利用して出力計算を実行する手段をさらに備えることを特徴とする請求項３３に記載の装置。
【請求項３５】
前記第２ステージに引き続く第３ステージにおいて、前記第２ステージにおいて計算された前記リバースメトリックに対応するフォワードメトリックを実行する手段と、
前記第２ステージの間に計算された前記リバースメトリック値および前記第３ステージの間に計算された前記フォワードメトリック値を利用して出力計算を実行する手段と
をさらに備えることを特徴とする請求項３３に記載の装置。
【請求項３６】
データビットおよび関連付けられたパリティビットを含み、かつ伝送チャネルにおける雑音により乱されている可能性がある、遠隔地から受信された前記伝送信号を復号する装置であって、
送信地から受信されたそれぞれのデータビットおよびその付随するパリティビットに対するリバースメトリック値を、第１の時間間隔の間に計算する手段と、
それぞれのリバースメトリック値を格納する第１メモリと、
それぞれの受信されたデータビットおよび付随するパリティビットを格納するローカルメモリと、
外部値を計算することにおいて使用するために、リバースメトリック値を前記第１メモリから読み出す手段と、
以前に前記ローカルメモリに格納された前記データビットおよび付随するパリティビットを、フォワードメトリックを計算するために利用する手段と、
第２の時間間隔の間に、前記第２の時間間隔の間に受信されたデータビットおよび付随するパリティビットに対するリバースメトリック値を計算し、前記第２の時間間隔の間に計算された各リバースメトリック値を、リバースメトリック値が読み出された前記第１メモリのメモリ位置に格納する手段と
を備えることを特徴とする装置。
【請求項３７】
前記ローカルメモリに読み込まれた前記データビットおよび付随するパリティビットを、読み出し専用の手段により前記外部値を計算することにおいて使用するために、前記ローカルメモリから逆の順序で読み出す手段を含むことを特徴とする請求項３６に記載の装置。
【請求項３８】
所定のフォワードメトリック値、所定のリバースメトリック値、および所定のデータビットおよび付随するパリティビットに基づいて、外部値を計算する手段をさらに備えることを特徴とする請求項３７に記載の装置。
【請求項３９】
受信された信号の２値状態を判定する出力計算を実行するために必要とされたフォワードおよびリバースメトリックを計算するための装置であって、
第１ステージの間にフォワードメトリック計算の第１グループを実行する手段と、
フォワードメトリック値の前記第１グループを格納するメモリ手段と、
前記第１ステージに引き続く第２ステージの間にリバースメトリック計算を実行する手段と、
前記第２ステージの間にリバースメトリック値が計算されるときに、フォワードメトリック計算の第２グループを実行する手段と、
前記受信された信号の２値状態を判定するための計算を実行するため前記第２ステージの間に計算された前記リバースメトリック値とともに使用するために、前記第１グループのフォワードメトリック値を前記メモリから読み出す手段と、
前記第２ステージにおいて前記リバースメトリック値が計算されている時間の間に、フォワードメトリック値の前記第２グループの計算を格納することにより、前記第２ステージの間に計算された各フォワードメトリック値が、前記第１ステージの間に計算されたフォワードメトリック値が、前記受信された信号の２値状態を判定する計算を実行することにおいて使用するために読み出された位置と同一の位置に格納される手段と
を備えることを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エラーの検出および訂正アルゴリズムを処理する技術分野に関する。より詳細には、本発明は、最大事後確率（ＭＡＰ：Maximum A Posteriori）アルゴリズムを処理するための効率的なパイプライン構造に関する。
【背景技術】
【０００２】
ターボ復号器アルゴリズムなどの一部のエラー訂正アルゴリズムは、ＭＡＰアルゴリズムを変形したものを用いて、雑音により乱された符号化されたビット列から情報ビット列を回復する。ＭＡＰアルゴリズムにより要求される計算の再帰的な性質により、その実行にはコストがかかる。
【０００３】
例えば、図１は、一連のAforward@metricsおよび一連のAbackward@metricsの関数として、ＭＡＰアルゴリズムによる連続出力を例示する。しかしながら、それぞれのフォワードメトリック（ｋ）は、前のフォワードメトリック（ｋ−１）の関数であり、それぞれのリバースメトリック（ｋ−１）は、次のリバースメトリック（ｋ）の関数である。図１の時間軸方向で示されるように、このアルゴリズムを実行するアーキテクチャは、出力が計算されている間に、他の一連のメトリックの計算が可能なように、フォワードメトリックのすべて、またはリバースメトリックのすべてのどちらかを保持するのに十分な大きさのバッファを必要とし、これを設計すると、復号される必要のあるブロックの大きさの約２倍に比例する待ち時間の復号器を必要とする。
【０００４】
ＭＡＰアルゴリズムにより必要とされるバッファを削減する努力において、スライディングウインドウアルゴリズムと呼ばれるＭＡＰアルゴリズムの修正版が開発されている。リバースメトリック計算において細かな近似を行うことにより、スライディングウインドウ法により、必要とされるメトリックバッファの大きさが削減される。これは、受信した系列をウインドウに分割し、次に各ウインドウを処理することにより達成される。
【０００５】
図２は、データが２つのウインドウに分割された場合に、スライディングウインドウ計算がどのように実行されるかを時間軸方向で示す。テールおよび学習サイズの長さは、典型的には、処理されるデータの量と比較すると非常に小さい。ウインドウサイズが学習ウインドウのサイズと比較して比較的大である限り、復号器による待ち時間が極端に増加することはなく、フォワードメトリックを保持するために必要とされるバッファのサイズが際立って減少することは明白である。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従って、本発明の目的は、このようなアルゴリズムを実行することに関連付けられた待ち時間およびコストの両方を削減することである。
【課題を解決するための手段】
【０００７】
本発明のパイプライン化されたＭＡＰ復号器アーキテクチャにおいて、スライディングウインドウ法を修正して、処理時間を削減する。一旦、第1のウインドウに対してフォワードメトリックを計算すると、次のウインドウに対するフォワードメトリックが計算されている間に、各ウインドウに対するリバースメトリックを計算する。新しいフォワードメトリックが計算され、メモリに格納されると、前のウインドウからのフォワードメトリックがメモリから読み出され、新しいリバースメトリックを計算することができる。前のウインドウからの各フォワードメトリックは、次のウインドウに対する新しいフォワードメトリックが同じメモリ位置に書き込まれるのと同一のクロックエッジにおいて、メモリから読み出される。フォワードメトリックをメモリとの間でこのように読み書きすることにより、フォワードメトリックのバッファサイズの増大は必要無くなる。データが２つのウインドウに分割された場合でも、パイプライン化された計算を実行することができる。このアーキテクチャはターボ復号器のために開発されたが、ＭＡＰアルゴリズムの翻案を用いる任意の復号器を使用することができる。パイプライン化されたスライディングウインドウ構造は、処理時間を削減する。標準的なスライディングウインドウ構造は、同じスループットを達成するために、非常に高速のクロックレートで動作させる必要がある。
【発明を実施するための最良の形態】
【０００８】
本発明の図３Ａは、本発明のパイプライン復号器の構成が属するがあるターボ復号器のブロック図である。本発明のパイプライン化されたＭＡＰ復号器の構成において、スライディングウインドウ法を修正して、処理時間を削減する。図４は本発明によって達成された時間軸方向を例示する。一旦、第1のウインドウに対してフォワードメトリックが計算されると、次のウインドウに対するフォワードメトリックが計算されている間に、各ウインドウに対するリバースメトリックが計算される。それぞれの新しいフォワードメトリックが計算され、メモリに格納されると、前のウインドウからのフォワードメトリックは、メモリから読み出され、新しいリバースメトリックを計算することができる。各フォワードメトリックは、新しいフォワードメトリックが同じメモリ位置に書き込まれるのと同一のクロックエッジにおいて、メモリから読み出される。フォワードメトリックをメモリとの間でこのように読み書きすることにより、フォワードメトリックのバッファサイズの増大は必要無くなる。
【０００９】
図３Ａは、本発明の原理および／または手法を具体化するターボ復号器の一実施形態のブロック図を示す。
【００１０】
ターボ復号器１０は、例えば、各データビット（Ａ１＠またはＡ０＠）を３ビット、すなわちデータまたはシステマティックビット（ｓ）、第１パリティビット（ｐ１）および第２パリティビット（ｐ２）に変換する基地局などの送信施設からデータを受信する。ｓｐ１ｐ２データはレジスタ１２に加えられ、レジスタ（spe_mem）１２は、以下により詳細に記述されるように、外部メモリ１４から読み出された外部データ、およびインターリーブアドレスレジスタ１６から得られたアドレスを受信する。このようにメモリレジスタ１２は、最初にｓｐ１ｐ２データ、ライン１４ａに現われている外部データ、およびライン１６ａにおいて外部データが位置するアドレスを受信し、格納する。以下により詳細に記述するために、計算を通じて、アドレスはｓｐ１ｐ２データに付随する。
【００１１】
ｓｐ１ｐ２データは、レジスタ１２からガンマ（Γ）計算器１８へ転送され、さらにローカルメモリ２０に格納される。
【００１２】
従来のターボ復号器と同様に、３つの量、アルファ（α）、ベータ（β）およびガンマ（Γ）が定義される。これらの量は、特定の状態と特定の時間ステップに対して、符号器がその特定の状態と特定の時間ステップにある確率を定義する値を有する。アルファは、時間ｋ＝１から始まり、時間方向に移動し、再帰的に算出される。その値は、類似しているが、時間に逆方向に作用する。ガンマ（Γ）は、符号器が所定の時間における状態から、次に続く時間増分においてある許可された状態に移動する遷移確率として定義される。アルファ（α）は、ガンマ（Γ）により提示される状態遷移確率に基づいて、格子状にすべての状態に対して計算され得る。ガンマ（Γ）計算器１８において行われたガンマ（Γ）の計算は、レジスタ（gamma_a）２２に格納される。計算ステージ２４と２６とは、それぞれアルファの計算、およびアルファ計算の正規化を個別に行う。各アルファ値は、レジスタ２２からの入力、および計算ステージ２６から出力されマルチプレクサ２８とレジスタ３０（current_beta：８つの計算値を保持）を通して入力２４ｂに供給される、以前に計算されたアルファの値に基づいて計算される。レジスタ３０の出力は、最初に計算されたアルファ値を最初のメモリ位置３２ａに格納するアルファ（α）メモリ３２の入力に接続され、計算されたアルファ値を入力２４ｂへ供給する。
【００１３】
計算を初期化するため、および初期状態において起動するために、最初の８つのアルファメトリックは、ある一定の初期値に設定され、初期値は、計算ステージ２４と２６でアルファのために８つの値を計算できるようにするために、マルチプレクサ２８の初期化入力２８ａに適用される。上述したように、ｓｐ１ｐ２データは、ローカルメモリ２０に格納される。
【００１４】
最初に、すべてのアルファ値が計算され、ｓｐ１ｐ２データを使用することによりベータ値が計算される。ｓｐ１ｐ２データは、ベータについて逆方向の再帰的な計算式のために必要とされる計算を実行するために、ローカルメモリ２０から逆の順序（すなわち、後入れ先出しの順）で読み出される。ローカルメモリ２０において最後に読み込まれたｓｐ１ｐ２データは、レジスタ（read_spe）３４の中に読み込まれる。レジスタ３４には、ｓｐ１ｐ２データだけではなく外部値（初期段階動作においては０）、および初期の外部値が外部メモリ１４において位置しているメモリ位置を表すデータを含む。ｓｐ１ｐ２および外部的データは、ガンマ（Γ）計算ステージ３６において計算される。ガンマ計算ステージ３６の出力を、ガンマレジスタ（gamma_b）３８および４０に加える。ベータ計算は、ベータ計算ステージ４４およびベータ正規化ステージ４６により個別に実行される。最初に、スタート条件の２進の１（Ａ１＠）を、マルチプレクサ４２の入力４２ａに加える。正規化されたベータ計算は、最初に、出力レジスタ（current_beta）４８を通して外部値計算ステージ５０に適用される。出力レジスタ４８は、さらにマルチプレクサ４２の残りの計算値入力４２ｂに適用される。外部値計算ステージ５０は、入力５０ａにおいて受信されたレジスタ５２に対するアルファ値、入力５０ｂにおいて受信されたレジスタ３８からのガンマ値、および入力５０ｃにおいて受信されたレジスタ４８からのベータ出力を監視することにより、それぞれの時間状態ｋに対する外部値を計算する。レジスタ４８、レジスタ（beta_read）５２およびレジスタ３８は、外部値計算ステージ５０における信号の時間登録を保証するために用意されている。
【００１５】
第１の外部値計算ステージ５０により計算された中間的な値は、レジスタ（inter_extrin_calc）５４に加えられ、その内容が外部値計算の第２ステージ５６に転送される。
【００１６】
上述したように、レジスタ３４がその内容をレジスタ５８（read_E1）に転送し、レジスタ５８は、順にその内容をレジスタ（read_E2）６０に転送し、レジスタ６０の内容が第２の外部値計算ステージ５６の出力に現われている外部値から差し引かれる。この減算ステージは、引き算回路６２において実行される。
【００１７】
ステージ５６において得られた外部値は、さらに、第２の外部値計算ステージ５６の出力を受信する２値状態判定回路６６を備えるソフト−イン−ハード−アウト回路６４に加えられる。ＳＩＨＯ回路６４における回路６６の動作は、以下により詳細に明らかにされるであろう。
【００１８】
差分回路６２における差分出力は、レジスタ（calc）６８に加えられ、レジスタ６８は、外部値計算のために外部メモリ１４の端子１４ｂに加える。上述したように、ローカルメモリ２０は、データ、パリティおよび外部値を格納することに加えて、さらに外部メモリ１４の第１の外部値アドレスを格納する。このアドレスは、メモリレジスタ３４、および同期化レジスタ（extrin_write_addr1）７０、レジスタ（extrin_write_addr2）７２およびレジスタ（extrin_write_addr3）７４を通して連続的に接続され、外部値計算が格納される外部メモリ１４の位置情報を提供する。このメモリ位置データは、外部メモリ１４の端子１４ｃに加えられる。
【００１９】
図２に示した例を参照して上述したように、アルファを決定するための計算の半分は、最初の時間ウインドウのｋ／２の間に実行される。
【００２０】
リバースメトリックの計算は、最初のウインドウの後の半分（ｋ／２）の間に実行される。アルファ値は、アルファメモリ３２からそれらが格納された順と逆の順序で読み出される。ウインドウ２（図４参照）に対するフォワードメトリックの間に計算されたアルファ値は、外部値を計算する目的のためにウインドウ１の間に計算されたアルファ値が読み出されるメモリ位置に同時に格納される。これにより、図３Ａの実施形態においては、メモリ容量が２分の１に削減される。新たに計算されたアルファ値が最初のウインドウの間に計算された値の順と逆の順序で格納されることに注意する必要がある。
【００２１】
それぞれの引き続くウインドウ計算の組において、実行される計算の数は外部値を計算するための望ましい繰り返しの数の関数であり、アルファメモリ３２におけるアルファ値の読み出しおよび書き込みの順序は、逆転される。すなわち、最後のメモリ位置から最初の順序で格納された、前に計算されたアルファ値が読み出されると、アルファ値は、最初のメモリ位置から最後のメモリ位置へ逆の順序で読み出され、さらにフォワードメトリックに対する第２の繰り返しのウインドウ２において決定されたアルファ値まで読み出され、２４／２６において計算された新しい値は、アルファ値が読み出されたそれらの位置で読み込まれる。
【００２２】
上述したように、外部値が計算されると、すなわち最初の繰り返しが完了すると、この外部値は、外部メモリ１４から読み出され、次の繰り返しの計算の間に使用される。簡略化の目的のために示されないが、従来型の制御回路により、実行される繰り返しの数が決定される。
【００２３】
上述したように、それぞれの外部値が決定されると、回路６６に加えられ、その振幅が調べることにより、データビットがＡｌ＠かＡ０＠かが判定される。ある一定の閾値より上であると判定された場合にはＡｌ＠とし、ある一定の閾値より下であると判定された場合にはＡ０＠とする。この確定された値は、レジスタ（HARD DECISION）７６に加えられ、レジスタ７４から引き出され、マージ回路７８に加えられる外部値メモリ位置とマージされる。出力ビットは、メモリ８４に書き込まれる。ＳＩＨＯ回路６４は、各ビットを、各行が１６ビット幅であるメモリ位置に書き込む。マージ回路マルチプレクサ７８、マルチプレクサ回路８０および出力メモリ読み取りレジスタ（output_mem_read_1）８２が、２値状態判定回路６６により評価された１６のデータビットを格納することにより、各メモリ位置の２値の１６ビットすべてが活用されるように動作する。
【００２４】
図３Ａで示される実施形態では、アルファが最初のウインドウの間に計算され、ベータが最初のウインドウの後半部分の間に計算されることが示されているが、図１で示した実施形態のすべての利益を得つつ、アルファとベータ計算を逆転することが可能であることを理解それたい。この利益は、すなわち、現在の技法および装置との比較において、図３Ａのターボ復号器のメモリ必要量の５０％削減、および計算時間の著しい削減である。本発明の構成は、メモリサイズのさらなる削減を可能にする。例えば、データを３つのウインドウ、４つのウインドウ等を用いて処理することにより、メモリサイズのさらなる削減を提供する。例えば、４つのウインドウを用いることにより、メモリサイズにおいて、ウインドウ分割が適用されない場合の処理に比較して３分の１のメモリサイズとなる。
【００２５】
図４は、データが２つのウインドウに分割された場合に、パイプライン計算がどのように実行されるかを例示する。学習ウインドウおよびテールビットの数を無視すれば、この例のパイプラインスライディングウインドウ復号器を通しての待ち時間は、単純なスライディングウインドウアーキテクチャにおける２Ｋに対して１２Ｋに比例する。ウインドウサイズ、ウインドウの数、および処理される必要があるデータ量による学習サイズを変えることにより、待ち時間を削減することが可能である。
【００２６】
上述されたアーキテクチャは、ターボ復号器のために開発されたが、すべてのコンボリューション符号が、ＭＡＰ復号器を用いることが可能である。フォワードメトリック計算を、リバースメトリックの前か後のどちらで計算してもよい。リバースメトリックが最初に計算され、次に出力計算が実行されている間にフォワードメトリックが計算される場合もあり得る。例えば、これは図３Ｂの実施形態に示されるように実施される。ここでは、計算ブロック２４’がベータ計算器、計算ブロック２６’がベータ正規化計算ブロック、メモリ３２’がベータメモリ、計算ブロック４４’がアルファ計算ブロック、計算ブロック４６’はアルファ正規化計算ブロックである。
【００２７】
図３Ｂの実施形態の動作はその他については、実質的には図３Ａの実施形態と同一である。
【図面の簡単な説明】
【００２８】
【図１】従来技術にかかるエラー訂正アルゴリズム構成の時間軸方向の一例である。
【図２】フォワードおよびリバースメトリックがスライディングウインドウを用いて計算される、従来技術にかかるエラー訂正アルゴリズム構成の時間軸方向の第２の例である。
【図３Ａ】本発明のエラー訂正の構成が属することのできるターボ復号器のブロック図である。
【図３Ｂ】フォワードおよびリバースメトリックの計算が入れ替えられた代替のターボ復号器のブロック図である。
【図４】本発明のエラー訂正の構成の時間軸方向である。
【図１】
2005503058.tif 000003
【図２】
2005503058.tif 000004
【図３Ａ】
2005503058.tif 000005
【図３Ｂ】
2005503058.tif 000006
【図４】
2005503058.tif 000007
【国際公開パンフレット】
2005503058.tif 000008
2005503058.tif 000009
2005503058.tif 000010
2005503058.tif 000011
2005503058.tif 000012
2005503058.tif 000013
2005503058.tif 000014
2005503058.tif 000015
2005503058.tif 000016
2005503058.tif 000017
2005503058.tif 000018
2005503058.tif 000019
2005503058.tif 000020
2005503058.tif 000021
2005503058.tif 000022
2005503058.tif 000023
2005503058.tif 000024
2005503058.tif 000025
2005503058.tif 000026
2005503058.tif 000027
2005503058.tif 000028
2005503058.tif 000029
2005503058.tif 000030
2005503058.tif 000031
2005503058.tif 000032
2005503058.tif 000033
【国際調査報告】
2005503058.tif 000034