(57)【要約】  受信されたフレームの終わりの位置を特定する装置（１００）であって、経路メトリクスを格納する少なくとも１つのメモリ・ユニット（１３０）と、異なったあり得る終点で終わる仮定的トレリス経路を与え、各仮定的トレリス経路について順方向検出検査を実行し、順方向検出検査に合格した仮定的トレリス経路について虚偽検出変数を計算し、当該計算に応答して、受信されたフレームの終点を決定するよう適合された少なくとも１つのプロセッサとを備える装置である。そこにおいて、順方向検出検査の計算は、虚偽検出変数の計算より非常に早い。受信されたフレームの終わりの位置を特定する方法（３００）であって、異なったあり得る終点で終わる仮定的トレリス経路を与えるステップ（３１０）と、各仮定的トレリス経路についてＣＲＣ検査を実行するステップ（３２０）と、ＣＲＣ検査に合格した仮定的トレリス経路について虚偽検出変数を計算するステップ（３３０）と、当該計算に応答して、受信されたフレームの終点を決定するステップ（３４０）とを含む方法である。
2008523755.tif 000002
【特許請求の範囲】
【請求項１】
受信されたフレームの終わりの位置を特定する方法（３００）であって、異なったあり得る終点で終わる仮定的トレリス経路を与えるステップ（３１０）を備える方法において、
各仮定的トレリス経路について順方向検出検査を実行するステップ（３２０）と、
前記順方向検出検査に合格した仮定的トレリス経路について虚偽検出変数を計算するステップ（３３０）であって、前記順方向検出検査の計算が前記虚偽検出変数の計算より速い、前記計算するステップ（３３０）と、
前記計算に応答して前記受信されたフレームの終点を決定するステップ（３４０）と
を備えることを特徴とする方法。
【請求項２】
前記順方向検出検査がＣＲＣである請求項１記載の方法。
【請求項３】
仮定的トレリス経路を与える前記ステップ（３１０）が、第１のプロセッサにより実行され、
順方向検出検査を実行する前記ステップが、別のプロセッサにより実行される
請求項１又は２記載の方法。
【請求項４】
仮定的トレリス経路を与える前記ステップ（３１０）が、フィードフォワード・トレリス計算を実行するステップを備える請求項１又は２記載の方法。
【請求項５】
仮定的トレリス経路を与える前記ステップ（３１０）が、あり得る終点の経路メトリクスを格納するステップを備える請求項４記載の方法。
【請求項６】
仮定的トレリス経路を与える前記ステップ（３１０）が、残存経路を示す情報を格納するステップを備える請求項１から５のいずれか一項に記載の方法。
【請求項７】
仮定的トレリス経路を与える前記ステップ（３１０）が、トレース・バック・プロセスを実行するステップを備える請求項１から６のいずれか一項に記載の方法。
【請求項８】
トレース・バック・プロセスを実行する前記ステップが、残存経路を示す先に格納された情報を検索するステップを備える請求項７記載の方法。
【請求項９】
前記決定が、スレッショルドＤと前記の計算された変数との間の関係に応答し、
前記方法が、スレッショルドＤを変えるステップを備える
請求項１から８のいずれか一項に記載の方法。
【請求項１０】
仮定的トレリス経路を与える前記ステップ（３１０）が、仮定的トレリス経路を計算するステップを備える請求項１記載の方法。
【請求項１１】
先に計算された仮定的トレリス経路について順方向検出検査を実行しながら（３２０）、仮定的トレリス経路を計算する請求項９記載の方法。
【請求項１２】
ＣＲＣ検査に合格した先に与えられた仮定的トレリス経路について虚偽検出変数を計算しながら仮定的トレリス経路を計算するステップを備える請求項１から１１のいずれか一項に記載の方法。
【請求項１３】
受信されたフレームの終わりの位置を特定する装置（１００）であって、経路メトリクスを格納する少なくとも１つのメモリ・ユニット（１３０）を備える装置において、
異なったあり得る終点で終わる仮定的トレリス経路を与え、且つ各仮定的トレリス経路について順方向検出検査を実行し、
前記順方向検出検査に合格した仮定的トレリス経路について虚偽検出変数を計算し、そこにおいて、前記順方向検出検査の決定が前記虚偽検出変数の計算より早く、
前記計算に応答して前記受信されたフレームの終点を決定する
よう適合された少なくとも１つのプロセッサ（１１０，１２０）を備える装置。
【請求項１４】
第１のプロセッサ（１２０）が、異なったあり得る終点で終わる仮定的トレリス経路を与えるよう適合され、
第２のプロセッサ（１１０）が、各仮定的トレリス経路について順方向検出検査を実行するよう適合されている
請求項１３記載の装置。
【請求項１５】
前記第１及び第２のプロセッサ（１２０，１１０）が、少なくとも部分的に、互いに並列に動作する請求項１４記載の装置。
【請求項１６】
第１のプロセッサ（１２０）が、異なったあり得る終点で終わる仮定的トレリス経路与えるよう適合され、
第２のプロセッサ（１１０）が、前記順方向検出検査に合格した仮定的トレリス経路について虚偽検出変数を計算するよう適合されている
請求項１３から１５のいずれか一項に記載の装置。
【請求項１７】
前記第１及び第２のプロセッサ（１１０，１２０）が、少なくとも部分的に、互いに並列に動作する請求項１６記載の装置。
【請求項１８】
少なくとも１つのプロセッサ（１２０）が、フィードフォワード・トレリス計算を実行するよう適合されている請求項１３から１７のいずれか一項に記載の装置。
【請求項１９】
少なくとも１つのプロセッサ（１２０）が、あり得る終点の経路メトリクスを少なくとも１つのメモリ・ユニット（１３０）内に格納するよう適合されている請求項１８記載の装置。
【請求項２０】
少なくとも１つのプロセッサ（１２０）が、残存経路を示す情報を少なくとも１つのメモリ・ユニット（１４６）内に格納するよう適合されている請求項１３から１９のいずれか一項に記載の装置。
【請求項２１】
少なくとも１つのプロセッサ（１２０）が、トレース・バック・プロセスを実行するよう適合されている請求項１３から２０のいずれか一項に記載の装置。
【請求項２２】
少なくとも１つのプロセッサ（１２０）が、残存経路を示す先に格納された情報をトレース・バック・プロセス中に検索するよう適合されている請求項１３から２１のいずれか一項に記載の装置。
【請求項２３】
前記少なくとも１つのプロセッサ（１１０）が、スレッショルドＤと前記の計算された変数との間の関係に応答して、前記受信されたフレームの終点を決定するよう適合され、
前記装置が、スレッショルドＤを変えることが可能である
請求項１３から２２のいずれか一項に記載の装置。
【請求項２４】
請求項１３から２３のいずれか一項に記載された受信されたフレームの終わりの位置を特定する装置（１００）を備える受信器（９９）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報フレームの終点を検出する装置及び方法に関する。
【背景技術】
【０００２】
通信は、通常、無線媒体のようなしかしこれに限定されない媒体を介して一連の電磁符号を送信することを含む。送信中に、一連の電磁符号は破壊されることがある。最新の送信器及び受信器は、上記の破壊を克服して、強固な通信リンクを与えるため様々な対策を適用する。
【０００３】
送信器は、通常、入力情報シーケンスを受け取り、そしてそれを畳み込みエンコーダのような順方向誤り訂正装置により符号化される。畳み込みエンコーダは、入力情報信号並びに冗長信号を含む符号化された情報シーケンスを発生する。符号化された情報シーケンスは更に、様々な要領で処理され、そしてまた媒体を介して送信される前に変調されることができる。
【０００４】
発明の名称が「１パス・ブラインド移送フォーマット検出のためのシステム及び方法（Ｓｙｓｔｅｍ  ａｎｄ  ｍｅｔｈｏｄ  ｆｏｒ  ｏｎｅ−ｐａｓｓ  ｂｌｉｎｄ  ｔｒａｎｓｐｏｒｔ  ｆｏｒｍａｔ  ｄｅｔｅｃｔｉｏｎ）」であるＡｍｍｅｒ他の米国特許出願Ｎｏ．２００４／００９１０６７は、本明細書に援用されているが、この米国特許出願は、最新の広帯域符号分割多重アクセス（ＷＣＤＭＡ）送信器及び最新のＷＣＤＭＡ送信器により適用される様々な処理段階の簡単な説明をしている。
【０００５】
受信器は、通常、受信された信号を復調して、それらを処理して、入力情報信号シーケンスに再構成する。受信プロセスは、通常、ビタビ復号を含む。
【０００６】
ビタビ復号は、当該技術で周知である。以下の米国特許及び米国特許出願は、全て本明細書に援用されているが、これらは、従来技術のビタビ・デコーダ及びビタビ復号方法の一例を与える。これらの米国特許及び米国特許出願とは、発明の名称が「データ処理システムにおいて単一サイクル動作を実行する方法及び装置（Ｍｅｔｈｏｄ  ａｎｄ  ａｐｐａｒａｕｓ  ｆｏｒ  ｉｍｐｌｅｍｅｎｔｉｎｇ  ａ  ｓｉｎｇｌｅ  ｃｙｃｌｅ  ｏｐｅｒａｔｉｏｎ  ｉｎ  ａ  ｄａｔａ  ｐｒｏｃｅｓｓｉｎｇ  ｓｙｓｔｅｍ）」であるＣｏｏｍｂｓの米国特許出願Ｎｏ．２００３／００２８８４４、発明の名称が「高速ＡＣＳビタビ・デコーダ実現のため状態メトリクスを効率的に読み取ってメモリに格納する方法及び装置（Ｍｅｔｈｏｄ  ａｎｄ  ａｐｐａｒａｔｕｓ  ｆｏｒ  ｅｆｆｉｃｉｅｎｔｌｙ  ｒｅａｄｉｎｇ  ａｎｄ  ｓｔｏｒｉｎｇ  ｓｔａｔｅ  ｍｅｔｒｉｃｓ  ｉｎ  ｍｅｍｏｒｙ  ｆｏｒ  ｈｉｇｈ−ｓｐｅｅｄ  ＡＣＳ  Ｖｉｔｅｒｂｉ  ｄｅｃｏｄｅｒ  ｉｍｐｌｅｍｅｎｔａｔｉｏｎ）」であるＨａｎｓｑｕｉｎｅの米国特許Ｎｏ．６５７５８６４、発明の名称が「ビタビ・デコーダ、及びそのための方法及びユニット（Ｖｉｔｅｒｂｉ  ｄｅｃｏｒｄｅｒ，  ｍｅｔｈｏｄ  ａｎｄ  ｕｎｉｔ  ｔｈｅｒｅｆｏｒｅ）」であるＭｕｃｋ他の米国特許出願Ｎｏ．２００２／０１２６７７６、及び発明の名称が「ビタビ方程式の結果を単一サイクルで計算する装置及び方法（Ａｐｐａｒａｔｕｓ  ａｎｄ  ｍｅｔｈｏｄ  ｆｏｒ  ｃｏｍｐｕｔｉｎｇ  ｔｈｅ  ｒｅｓｕｌｔ  ｏｆ  ａ  Ｖｉｔｅｒｂｉ  ｅｑｕａｔｉｏｎ  ｉｎ  ａ  ｓｉｎｇｌｅ  ｃｙｃｌｅ）」であるＹｕ他の米国特許Ｎｏ．５９８７６３８である。
【０００７】
典型的には、受信器は、受信された情報シーケンス（これはまた情報フレーム、或いは情報ブロックとも呼ばれる。）の長さを予め知らなければならない。上記の受信された情報シーケンスの長さを知ることは、受信器の性能を改善し、そして或る場合には、不可欠ですらあり得る。
【０００８】
一部の通信プロトコル、標準及び方法は、可変長の情報フレームを用いる。例えば、第三世代パートナシップ・プロジェクト（３ＧＰＰ（登録商標））は、可変サイズのフレーム（これはまた通信チャネルとも呼ばれる。）を用いる通信プロトコルを定義した。
【０００９】
より詳細には、上記の標準は、複数の動作モード、及び各モードにつき通信チャネルの３つのあり得るサイズ（クラスＡ、クラスＢ及びクラスＣ）を定義した。このプロトコルは、本明細書に援用されている技術仕様書３ＧＰＰＴＳ ２５．２１２ Ｖ６．０．０を含む様々なペーパで定義された。
【００１０】
送信器は、送信される情報フレームのサイズを表すサイズ情報を受信器に送ることができる。他方、受信器は、受信された情報フレームのサイズを自身で決定することができる。情報パケットの長さを決定する周知の方法は、ブラインド移送順方向検出として知られている。このアルゴリズムは、３ＧＰＰＴＳ ２５．２１２ Ｖ６．０．０の付録Ａに記載されており、それは本明細書に援用されている。
【００１１】
手短には、ブラインド移送順方向検出（ＢＦＴＤ）アルゴリズム（又はシーケンス）は、順方向トレリス処理（これはまたビタビ復号又はフィードフォワード処理として知られている。）、Ｓ（ｎｅｎｄ）と表される変数の複素計算、及びこの変数の所定のスレッショルドＤとの比較を適用することを含む。Ｓ（ｎｅｎｄ）がＤに等しいか又はそれより小さい場合、アルゴリズムは、ビタビ・トレース・バック処理を実行することにより進み、そして巡回冗長検査（ＣＲＣ）をトレース・バック・プロセスの結果に適用する。
【００１２】
情報フレームのサイズ（又は情報フレームの終わりの位置）は、既知のグループのあり得る終点から１つの終点を選択することにより決定されることができる。２以上のあり得る終点がＣＲＣ試験を通過し、且つそのＳ（ｎｅｎｄ）がＤより小さい場合、アルゴリズムは、最も小さいＳ（ｎｅｎｄ）と関連した終点を選択する。受信器が、受信を失敗したと決定することができることに注目されたい。
【００１３】
数学の項S(nend)=-Log((a0(nend)-amin(nend))/(amax(nend)-amin(nend))において、a0(nend)は、ｎｅｎｄ′番目のあり得る終点に対応するトレリス段階のゼロ状態での経路メトリク値であり、そしてａｍｉｎ（ｎｅｎｄ）及びａｍａｘ（ｎｅｎｄ）は、それぞれ、そのトレリス段階の全ての残存経路の中の最小メトリク値及び最大メトリク値である。典型的なトレリス・グラフにおいて、各トレリス段階は、２Ｔ−１個の状態を含み、ここでＴは、畳み込みエンコーダの長さである。標準３ＧＰＰＴＳ ２５．２１２ Ｖ６．０．０において、Ｔは９である。従って、最小及び最大の残存経路の探索は、極めて長い。
【００１４】
Ａｍｍｅｒ他の米国特許出願Ｎｏ．２００４／００９１０６７は、Ｓ（ｎｅｎｄ）を計算してそれをＤと比較する代わりに、スレッショルドＴ（ｎｅｎｄ）を計算してそれをゼロと比較することを提案している。即ち、
T(nend)=10D/10×((amax(nend)-amin(nend))-((a0(nend)-amin(nend))
である。
【００１５】
図１は、情報フレーム１０、９個のあり得る終点１１−１０、及びその情報フレーム１０に対応するトレリス図２０の一部分を示す。情報フレーム１０は、ペイロード、ＣＲＣビット及び空ビット（ゼロ・ビットのシーケンス）を含む。トレリス図２０は、複数のトレリス段階を含み、そこにおいては、９個のトレリス段階は、９個のあり得る終点と関連付けられる。これらの９個のトレリス段階のそれぞれは、１から９の範囲にある或るｎｅｎｄ値と関連付けられる。
【００１６】
図２は、３ＧＰＰ ＴＳ ２５．２１２ Ｖ６．０．０の上記付録Ａのペーパに見られるように、ブラインド移送順方向アルゴリズムのための従来技術方法３０を示す。
【００１７】
方法３０は、ｎｅｎｄを１に設定し（第１のあり得る終点から始め）、別の変数ｎｅｎｄ′をゼロに設定し、そしてＳｍｉｎをＤに設定するステップ３２により開始する。
【００１８】
ステップ３２には、ビタビ復号を開始点からｎｅｎｄ′番目のあり得る終点に対応するトレリス段階まで実行する（これはまた順方向トレリス処理又はトレリス・フィードフォワード・プロセスと呼ばれる。）ステップ３４が続く。
【００１９】
ステップ３４には、Ｓ（ｎｅｎｄ）を計算するステップ３６が続く。
【００２０】
ステップ３６には、Ｓ（ｎｅｎｄ）がＤより大きいかどうかを決定する問い合わせステップ３８が続く。Ｄ≧Ｓ（ｎｅｎｄ）である場合、問い合わせステップ３８には、ｎｅｎｄ′番目の仮定的トレリス経路を与えるため、トレース・バック・プロセスをｎｅｎｄ′番目のあり得る終点から実行するステップ４０が続く。Ｄ＜Ｓ（ｎｅｎｄ）である場合、ステップ３８には、問い合わせステップ５０が続く。
【００２１】
ステップ４０には、ｎｅｎｄ′番目の仮定的トレリス経路についてＣＲＣパリティ・ビットを計算するステップ４２が続く。
【００２２】
ステップ４２には、ＣＲＣに合格パスしたか又は失敗したかを検査する問い合わせステップ４４が続き、そしてＣＲＣに失敗した場合、問い合わせステップ４４には、問い合わせステップ５０が続く。ＣＲＣに合格した場合、問い合わせスステップ４４には、Ｓ（ｎｅｎｄ）をＳｍｉｎと比較するステップ４６が続く。
【００２３】
Ｓ（ｎｅｎｄ）＜Ｓｍｉｎである場合、問い合わせステップ４６には、ＳｍｉｎをＳ（ｎｅｎｄ）に設定し、そしてｎｅｎｄ′をｎｅｎｄに設定するステップステップ４８が続く。さもなければ、問い合わせステップ４６には、問い合わせステップ５０が続く。ステップ４８には、問い合わせステップ５０が続く。
【００２４】
問い合わせステップ５０は、ステップ３４−４８が全てのあり得る終点に適用されたかどうか（「ｎｅｎｄが最大値か？」）を検査することを含む。
【００２５】
答えが否定である場合、問い合わせステップ５０には、ｎｅｎｄを増大し、そしてステップ３４へジャンプするステップ５２が続く。
【００２６】
全てのあり得る終点が検査された場合、問い合わせステップ５０には、ｎｅｎｄ′と関連した終点を選択されたフレーム終点として与えるステップ５４が続く。ｎｅｎｄ′の値がゼロである場合、受信されたフレームは、誤りであると宣言される。
【発明の開示】
【発明が解決しようとする課題】
【００２７】
情報フレームの終点の位置を特定するための効率的な方法及び装置に対する必要性が存在する。
【課題を解決するための手段】
【００２８】
添付の特許請求の範囲に記載されるような情報フレームの終わりの位置を特定する方法及び装置が提供される。
【００２９】
本発明は、添付図面と関係した以下の詳細な説明からより完全に理解され、そして認められるであろう。
【発明を実施するための最良の形態】
【００３０】
本発明者は、フィードフォワード復号、フィードフォワード・チャネル等化、トレース・バック、ＢＦＴＤ及び類似のもののような様々なアルゴリズムを適用するため、１個のビタビ・コプロセッサに選択的に接続されることができる４個のＳｔａｒＣｏｒｅ（登録商標）コアを含んだＭＳ８１２６チップ内の情報ブロックの終わりを検出する方法を用いた。提供された方法及びデバイスは、上記構成に限定されないことに注目されたい。
【００３１】
本発明者は、クラスＡ及びクラスＢの情報パケットをＶＣＯＰモジュールに与えることにより本特許出願の主題である方法の効率性を試験した。ＣＲＣ計算は、約９５０クロック・サイクルを必要としたが、一方、Ｓ（ｎｅｎｄ）の計算は、約１０，０００クロック・サイクルを必要とした。１７個の仮定的トレリス経路が、与えられ、そして僅か２つが、ＣＲＣ試験に合格した。この方法は、約３５，０００クロック・サイクルを必要とした。従来技術の方法の適用は、約１６５，０００クロック・サイクルを必要した。提案した方法のクロック・サイクルの数は、様々なプロセス（例えば、トレース・バック及びＣＲＣ検査、又は更にＳ（ｎｅｎｄ）計算のようなもの）を並列に実行することにより更に低減することができることに更に注目されたい。
【００３２】
本方法の様々なステップは１又はそれより多いプロセッサにより実行されることができることに更に注目されたい。そこにおいて、プロセッサは、情報を処理することが可能である装置である。プロセッサは、ソフトウエアを実行することができるが、しかしこれは、純粋なハードウエア構成要素が情報処理操作を実行することができるので、必ずしもそうであるわけではない。２以上のプロセッサが上記の方法の実行に係わる場合、それらのプロセッサは、両者が一体で、又は互いが個別の場所に配置され、或いは類似の状態にあることができることに更に注目されたい。
【００３３】
図３は、本発明の一実施形態に従った情報フレームの終わりを検出する装置１００を示す。
【００３４】
装置１００は、デジタル信号プロセッサ（ＤＳＰ）１１０、ビタビ・コプロセッサ（ＶＣＯＰ）１２０、及びメモリ・ユニット１３０を含む。
【００３５】
ＤＳＰ１１０は、ＶＣＯＰ１２０を構成することができ、そしてＶＣＯＰ１２０は、ＤＳＰ１１０に対する割り込み要求を発生することができる。両方のプロセッサ１１０及び１２０は、メモリ・ユニット１３０にアクセスすることができる。
【００３６】
装置１００は、受信器９９のような受信器に含まれることが都合良く、当該受信器は、アンテナ、ＲＦインターフェース、周波数ダウンコンバータ及び類似のものをようなしかしこれらに限定されるものでない他の構成要素を含む。受信器は、基地局内に配置されるが、しかしこれは、必ずしもそうであるわけではない。説明を簡単にするため、他の構成要素を示していない。
【００３７】
図４は、本発明の一実施形態に従ったＶＣＯＰ１２０を示す。
【００３８】
ＶＣＯＰ１２０は、出力インターフェース１４２、トレース・エンジン１４４、トレリス履歴メモリ１４６、制御器１４８、プログラミング・モジュール１７０、経路メトリクス計算器１５０、第１及び第２のトレリス段階メモリ１６０及び１６２、及びマルチプレクサ１５４、１５６及び１６４を含む。
【００３９】
プログラミング・モジュール１７０は、ＶＣＮＴレジスタ１７１、ＶＯＢＡＲレジスタ１７２、ＶＩＳＢＡＲレジスタ１７３、ＶＩＳＲＡレジスタ１７４、ＶＡＡＤＡＲレジスタ１７５、ＶＣＯＮＦＲレジスタ１７６及びＶＳＴＲレジスタ１７７のような複数のレジスタを含む。
【００４０】
ＶＣＮＴレジスタ１７１は、ビタビ・デコーダ・トレース・バック・モード指示及びトレース・バック開始トレリス段階指示を格納する。ＶＯＢＡＲレジスタ１７２は、アドレスをメモリ・ユニット１３０に格納し、当該メモリ・ユニット１３０は、トレース・バック・プロセス中に、又はトレリス履歴メモリ１４６をダンプするため、復号されたビットを格納する。ＶＩＳＢＡＲレジスタ１７３は、ビタビ復号プロセス及びＢＦＴＤプロセス中に処理されるべき入力シンボルのアドレスを格納する。
【００４１】
ＶＩＳＲＡ、ＶＩＳＲＢ及びＶＩＳＲＣレジスタ１７７−１７９は、あり得る終点を格納し、即ち、トレリス段階メモリ１６０（又は１６４）内に格納された経路メトリクスがメモリ・ユニット１３０へダンプされるトレリス段階である。ＶＡＡＤＡＲレジスタ１７５は、アドレスをメモリ・ユニット１３０の中に保持し、当該メモリ・ユニット１３０へあり得る終点の経路メトリクスがダンプされる。
【００４２】
ＶＣＯＮＦＲレジスタ１７６は、経路メトリク制御フィールド、フィードフォワード制御ビット、履歴ダンプ制御フィールド、トレース・バック制御フィールド、レート制御ビット、あり得る終点数ビット、履歴ダンプ割り込みイネーブル・ビット、フィードフォワード割り込みイネーブル・ビット、経路メトリクス・ダンプ割り込みイネーブル・ビット、及び類似のもののような制御ビットを格納する。ＶＳＴＲレジスタ１７４は、どのプロセス（例えば、トレリス履歴ダンプ、経路メトリクス充填、経路メトリクスのクリア、及びフィードフォワードのようなもの）が行われたかのようなＶＣＯＰの状態を示す状態ビットを含む。
【００４３】
制御器１４８は、プログラミング・モジュール１７０内に格納された制御情報に従ってＶＣＯＰ１２０の様々な構成要素の動作を制御する。
【００４４】
経路メトリクス計算器１５０は、残存経路を与えるためフィードフォワード・プロセスを実施する。フィードフォワード・プロセスは、現在のトレリス段階メモリ及び次のトレリス段階メモリとして交換可能に用いられる第１及び第２のトレリス段階メモリ１６０及び１６２を用いて、複数のバタフライ演算又は加算比較選択（ＡＣＳ）演算を実行することを含む。上記の交換可能性は、第１及び第２のトレリス段階メモリ１６０及び１６２の入力及び出力に接続されているマルチプレクサ１５４、１５６及び１６４を制御することにより達成される。
【００４５】
フィードフォワード・プロセス中に、残存経路は、トレリス履歴メモリ１４６に格納される。各状態が、このトレリス状態に至る２つの経路のうちのどちらが残存経路であるかを表すフラグと関連付けられることが都合良い。あり得る終点の経路メトリクスが、メモリ・ユニット１３０にダンプされることが都合良い。
【００４６】
トレース・エンジン１４４は、上記のフラグをトレリス履歴メモリ１４６から読み出すことにより仮定的トレリス経路を再構成することが可能である。トレース・エンジン１４４は、仮定的トレリス経路を、出力インターフェース１４２を介してメモリ・ユニット１３０のような他の構成要素へ出力することが可能である。
【００４７】
ＶＣＯＰ１２０は、ひとたびそれがフィードフォワード・プロセスを終えると、及びひとたびそれがトレース・バック・プロセスを終えると、割り込み要求をＤＳＰ１１０に対して発生することが可能である。それはまた、それが経路メトリクスをダンプする毎に割り込み要求を発生することが可能である。
【００４８】
本発明の一実施形態に従って、ＶＣＯＰ１２０及びＤＳＰ１１０は、ＢＦＴＤプロセスを実行するため協働する。ＶＣＯＰ１２０は、例えば、トレリス・フレームの始めで開始し、最後のあり得る終点１９で終わるフィードフォワード・プロセスを実行する。このフィードフォワード・プロセス中に、トレリス履歴メモリ１４６は、残存経路を格納し、そしてあり得る終点１１−１９の各あり得る終点の経路メトリクスが、メモリ・ユニット１３０にダンプされる。
【００４９】
ひとたびフィードフォワード・プロセスが終わると、ＶＣＯＰ１２０は、トレース・バック・プロセスをあり得る終点のうちの１つから開始する。ひとたびＶＣＯＰ１２０が（トレリス履歴メモリ１４６内に格納されているトレリス履歴に基づいて）仮定的トレリス経路を再構成することを終えると、それは、割り込みを発行し、そしてＤＳＰ１１０は、ＣＲＣパリティ・ビットを計算し、そしてＣＲＣに合格したかどうかを決定する。ＣＲＣに合格した場合、ＤＳＰ１１０は、Ｓ（ｎｅｎｄ）又はＴ（ｎｅｎｄ）のような虚偽検出変数を計算する。ＤＳＰ１１０がこれらの演算を実行して間に、ＶＣＯＰ１２０は、別のあり得る終点で開始するトレース・バック・プロセスを実行することができる。
【００５０】
ＢＦＴＤプロセスは、ＤＳＰ１１０及びＶＣＯＰ１２０の両方の並列動作により加速されることができる。
【００５１】
図１の情報フレームを参照すると、例示的ＢＦＴＤプロセスは、最後のあり得る終点１９までの全情報ブロックのＶＣＯＰ１２０によるフィードフォワード・プロセスを含むであろう。このフィードフォワード・プロセスには、ＣＲＣ検査に対して並列に実行されるトレース・バック・プロセスのシーケンス（これは異なったあり得る終点から開始する。）が続く。ＣＲＣ検査に合格した場合のみ、ＤＳＰ１１０は、Ｓ（ｎｅｎｄ）又はＴ（ｎｅｎｄ）のような虚偽検出変数を計算する。
【００５２】
図５は、本発明の一実施形態に従って、受信されたフレームの終わりの位置を特定する方法２００のフロー・チャートである。
【００５３】
方法２００は、ｎｅｎｄを１に設定し、別の変数ｎｅｎｄ″をゼロに設定し、そしてＳｍｉｎをＤに設定するステップ２０２により開始する（これは第１のあり得る終点から開始する。）。
【００５４】
ステップ２０２には、ビタビ復号を開始点から最後のあり得る終点まで実行するステップ２０４が続く。
【００５５】
ステップ２０４には、仮定的トレリス経路を与えるため、トレース・バック・プロセスをｎｅｎｄ′番目のあり得る終点から実行するステップ２０６が続く。
【００５６】
ステップ２０６には、仮定的トレリス経路についてＣＲＣパリティ・ビットを計算するようなフィードフォワード検出演算を実行するステップ２０８が続く。
【００５７】
ステップ２０８には、ＣＲＣのような順方向検出演算に合格したかどうかを検査する問い合わせステップ２１０が続く。順方向検出演算に失敗した場合、ステップ２１０には、問い合わせステップ２２０が続く。順方向検出演算に合格した場合、ステップ２１０には、虚偽検出変数を計算するステップ２１２が続く。この変数は、Ｓ（ｎｅｎｄ）である又は更にＴ（ｎｅｎｄ）でさえあることが都合良いが、しかしこれは、必ずしもそうであるわけではない。説明を簡単にするため、Ｓ（ｎｅｎｄ）が計算されると仮定する。順方向検出検査の計算が、一層速く、そして虚偽検出変数の計算より遙かに速いことが都合良いことに注目されたい。
【００５８】
ステップ２１２には、Ｓ（ｎｅｎｄ）がＤより大きいかどうかを決定する問い合わせステップ２１４が続く。Ｄ＜Ｓ（ｎｅｎｄ）である場合、問い合わせステップ２１４には、問い合わせステップ２２０が続く。Ｄ≧Ｓ（ｎｅｎｄ）である場合、問い合わせステップ２１４には、Ｓ（ｎｅｎｄ）をＳｍｉｎと比較するステップ２１６が続く。
【００５９】
Ｓ（ｎｅｎｄ）＜Ｓｍｉｎである場合、ステップ２１６には、ＳｍｉｎをＳ（ｎｅｎｄ）に設定し、そしてｎｅｎｄ″をｎｅｎｄに設定するステップ２１８が続く。さもなくてＳ（ｎｅｎｄ）≧Ｓｍｉｎである場合、問い合わせステップ２１６には、問い合わせステップ２２０が続く。ステップ２１８には、問い合わせステップ２２０が続く。
【００６０】
問い合わせステップ２２０は、ステップ２０４−２１８が全てのあり得る終点に適用されたかどうか（「ｎｅｎｄが最大値であるか？」）を検査することを含む。
【００６１】
答えが否定である場合、問い合わせステップ２２０には、ｎｅｎｄを増大し、そしてステップ２０６へジャンプするステップ２２２が続く。全てのあり得る終点が検査された場合、問い合わせステップ２２０には、ｎｅｎｄ″と関連した終点を選択されたフレームの終点として与えるステップ２２４が続く。ｎｅｎｄ″の値がゼロである場合、受信されたフレームは、誤りであると宣言される。
【００６２】
本発明の一実施形態に従って、方法２００は、ＤＳＰ１１０及びＶＣＯＰ１２０のようなしかしこれらに限定されるわけではない第１及び第２のプロセッサにより実行されるが、しかし必ずしもそうであるわけではない。
【００６３】
本発明の一実施形態に従って、第１及び第２のプロセッサは、少なくとも一部分並列に動作する。第１のプロセッサが或る一定のあり得る終点に関係して或る一定のステップを実行するとき、他方のプロセッサが、別のあり得る終点に関係して方法２００の他のステップを実行することが都合良い。
【００６４】
本発明の一実施形態に従って、ステップ２４０のビタビ復号は、フレームの複数の部分を一時に処理することを含むことができる。従って、ひとたび現在のフレーム部分が処理されると、或る一定の情報が（例えば、経路メトリクス、トレリス履歴）が、格納され又はダンプされ、そして別のフレーム部分が処理される。ビタビ復号が或る一定の点（例えば、あり得る終点のようなものであるがこれに限定されるものではない。）で終わるフレーム部分に適用されることができ、そして更なる復号がトレース・バック・セッション及び／又は仮定的トレリス経路の再構成のため要求される場合のみ、ビタビ復号を継続することができることに注目されたい。
【００６５】
図６は、本発明の一実施形態に従って、受信されたフレームの終わりの位置を特定する方法３００のフロー・チャートである。
【００６６】
方法３００は、異なったあり得る終点で終わる仮定的トレリス経路を与えるステップ３１０により開始する。ステップ３１０には、情報フレームを受信し、そして予め定義されたトレリス開始段階で開始し且つあり得る終点で終わることができる少なくとも１つのフィードフォワード・プロセスを実行することを含むことが都合良い。
【００６７】
フィードフォワード・プロセスは、それがあり得る終わりのグループのうちの最後のあり得る終点に対応するトレリス段階を処理するまで実行されることが都合良い。あり得る終点に対応するトレリス段階の経路メトリクスが格納される。本発明の一実施形態に従って、残存経路を表す情報がまた格納される。
【００６８】
図３及び図４に記載される例を参照すると、あり得る終点に対応するトレリス段階の経路メトリクスは、メモリ・ユニット１３０に送られ、そして残存経路を表す情報は、トレリス履歴メモリ１４６内に格納される。
【００６９】
本発明の一実施形態に従って、フィードフォワード・プロセスの終点は、最後のあり得る終点１９、又は上記最後のあり得る終点に続く点、或いは最後のあり得る終点１９より前にくる点であることができる。
【００７０】
フィードフォワード・プロセスには、トレース・バック・プロセスを或る一定のあり得る終点から実行して、仮定的トレリス経路を与えることが続くことが都合良い。ステップ２１４の第１の繰り返し中に、トレース・バック・プロセスは、第１のあり得る終点から開始するが、しかしこれは、選択されたあり得る終点が重大でないので、必ずしもそうであるわけではない。
【００７１】
ステップ３１０はステップ２０４の少なくとも１つの繰り返し、及びステップ２０６の複数の繰り返しを含むことが都合良い。
【００７２】
ステップ３１０には、各仮定的トレリス経路についてＣＲＣ検査のような順方向検出検査を実行するステップ３２０が続く。ステップ３２０はステップ２０８の複数の繰り返しを含むことが都合良い。図３に記載される例を参照すると、ＣＲＣ計算は、ＤＳＰ１１０により実行されることができる。
【００７３】
本発明の一実施形態に従って、ＶＣＯＰ１２０が或る一定の仮定的トレリス・フレームのトレース・バック・プロセスを実行している間に、ＤＳＰ１１０は、先に与えられた仮定的トレリス経路のＣＲＣ検査を実行する。
【００７４】
ステップ３２０には、順方向検出（ＣＲＣのようなもの）検査に合格した仮定的トレリス経路についてＳ（ｎｅｎｄ）又はＴ（ｎｅｎｄ）のような虚偽検出変数を計算するステップ３３０が続く。順方向検出検査の計算は、虚偽検出変数の計算より速く、そして更にそれより遙かに速いことが都合良い。
【００７５】
本発明の一実施形態に従って、ＶＣＯＰ１２０が或る一定の仮定的トレリス経路のトレース・バック・プロセスを実行している間に、ＤＳＰ１１０はまた、虚偽検出変数を計算することができる。
【００７６】
ステップ３３０はステップ２１０及び２１２を含むプロセス経路の複数の繰り返しを含むことが都合良い。ＣＲＣ検査に失敗した場合、前述した変数が計算されないことに注目されたい。
【００７７】
ステップ３３０には、上記計算に応答して、受信されたフレームの終点を決定するステップ３４０が続く。ステップ３４０はステップ２１６、２１８及び２２４の複数の繰り返しを含むことが都合良い。
【００７８】
本発明の一実施形態に従って、上記の決定は、最小のＳ（ｎｅｎｄ）と関連したあり得る終点を見つけることができ、そしてそこにおいては、そのＳ（ｎｅｎｄ）は、Ｄより小さい。
【００７９】
本発明の一実施形態に従って、仮定的トレリス経路を与えるステップ３１０は、ＶＣＯＰ１２０のようなしかしこれに限定されるわけではない第１のプロセッサにより実行され、そして更に虚偽検出変数を計算するステップでさえ、ＤＳＰ１１０のようなしかしこれに限定されるわけでは別のプロセッサにより実行される。
【００８０】
本発明の一実施形態に従って、決定するステップ３４０は、スレッショルドＤと計算された変数との間の関係に応答し、そこにおいて、スレッショルドＤは、方法３００中に、又は方法３００のセッション間に変えられることができる。
【００８１】
或る一定の仮定的トレリス経路の計算は、前に計算された仮定的トレリス経路についてＣＲＣ検査を実行することに対して並列に実行され、又はＣＲＣ検査に合格した先に与えられた仮定的トレリス経路について虚偽検出変数を計算することに対してさえ並列に実行されることが都合良い。
【００８２】
本明細書で説明されたものの変化、変更及び他の実施形態は、特許請求の範囲に記載された発明の趣旨及び範囲を逸脱することなしに当業者により行われるであろう。従って、本発明は、前述の例示的説明により定義されるべきではなく、代わりに添付の特許請求の範囲の趣旨及び範囲により定義されるべきである。
【図面の簡単な説明】
【００８３】
【図１】図１は、情報フレーム、９個のあり得る終点、及び情報フレームに対応する部分トレリス図を示す。
【図２】図２は、ブラインド移送順方向検出アルゴリズムの関する従来技術の方法を示す。
【図３】図３は、本発明の一実施形態に従った情報フレームの終わりを検出する装置を示す。
【図４】図４は、本発明の一実施形態に従ったビタビ・コプロセッサを示す。
【図５】図５は、本発明の一実施形態に従ってブラインド移送フォーマット検出を実行するフロー・チャートである。
【図６】図６は、本発明の一実施形態に従ってブラインド移送フォーマット検出を実行するフロー・チャートである。
【図１】
2008523755.tif 000003
【図２】
2008523755.tif 000004
【図３】
2008523755.tif 000005
【図４】
2008523755.tif 000006
【図５】
2008523755.tif 000007
【図６】
2008523755.tif 000008
【手続補正書】
【提出日】平成19年12月5日(2007.12.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
受信されたフレームの終わりの位置を特定する方法（３００）であって、異なったあり得る終点で終わる仮定的トレリス経路を与えるステップ（３１０）を備える方法において、
各仮定的トレリス経路について順方向検出検査を実行するステップ（３２０）と、
前記順方向検出検査に合格した仮定的トレリス経路について虚偽検出変数を計算するステップ（３３０）であって、前記順方向検出検査の計算が前記虚偽検出変数の計算より速い、前記計算するステップ（３３０）と、
前記計算に応答して前記受信されたフレームの終点を決定するステップ（３４０）と
を備えることを特徴とする方法。
【請求項２】
前記順方向検出検査がＣＲＣである請求項１記載の方法。
【請求項３】
仮定的トレリス経路を与える前記ステップ（３１０）が、第１のプロセッサにより実行され、
順方向検出検査を実行する前記ステップが、別のプロセッサにより実行される
請求項１又は２記載の方法。
【請求項４】
仮定的トレリス経路を与える前記ステップ（３１０）が、フィードフォワード・トレリス計算を実行するステップを備える請求項１又は２記載の方法。
【請求項５】
仮定的トレリス経路を与える前記ステップ（３１０）が、あり得る終点の経路メトリクスを格納するステップを備える請求項４記載の方法。
【請求項６】
仮定的トレリス経路を与える前記ステップ（３１０）が、残存経路を示す情報を格納するステップを備える請求項１から５のいずれか一項に記載の方法。
【請求項７】
仮定的トレリス経路を与える前記ステップ（３１０）が、トレース・バック・プロセスを実行するステップを備える請求項１から６のいずれか一項に記載の方法。
【請求項８】
トレース・バック・プロセスを実行する前記ステップが、残存経路を示す先に格納された情報を検索するステップを備える請求項７記載の方法。
【請求項９】
前記決定が、スレッショルドＤと前記の計算された変数との間の関係に応答し、
前記方法が、スレッショルドＤを変えるステップを備える
請求項１から８のいずれか一項に記載の方法。
【請求項１０】
仮定的トレリス経路を与える前記ステップ（３１０）が、仮定的トレリス経路を計算するステップを備える請求項１記載の方法。
【請求項１１】
先に計算された仮定的トレリス経路について順方向検出検査を実行しながら（３２０）、仮定的トレリス経路を計算するステップを備える請求項９記載の方法。
【請求項１２】
ＣＲＣ検査に合格した先に与えられた仮定的トレリス経路について虚偽検出変数を計算しながら仮定的トレリス経路を計算するステップを備える請求項１から１１のいずれか一項に記載の方法。
【請求項１３】
受信されたフレームの終わりの位置を特定する装置（１００）であって、経路メトリクスを格納する少なくとも１つのメモリ・ユニット（１３０）を備える装置（１００）において、
異なったあり得る終点で終わる仮定的トレリス経路を与え、且つ各仮定的トレリス経路について順方向検出検査を実行し、
前記順方向検出検査に合格した仮定的トレリス経路について虚偽検出変数を計算し、そこにおいて、前記順方向検出検査の決定が前記虚偽検出変数の計算より早く、
前記計算に応答して前記受信されたフレームの終点を決定する
よう適合された少なくとも１つのプロセッサ（１１０，１２０）を備えることを特徴とする装置（１００）。
【請求項１４】
第１のプロセッサ（１２０）が、異なったあり得る終点で終わる仮定的トレリス経路を与えるよう適合され、
第２のプロセッサ（１１０）が、各仮定的トレリス経路について順方向検出検査を実行するよう適合されている
請求項１３記載の装置。
【請求項１５】
前記第１及び第２のプロセッサ（１２０，１１０）が、少なくとも部分的に、互いに並列に動作する請求項１４記載の装置。
【請求項１６】
第１のプロセッサ（１２０）が、異なったあり得る終点で終わる仮定的トレリス経路を与えるよう適合され、
第２のプロセッサ（１１０）が、前記順方向検出検査に合格した仮定的トレリス経路について虚偽検出変数を計算するよう適合されている
請求項１３から１５のいずれか一項に記載の装置。
【請求項１７】
前記第１及び第２のプロセッサ（１１０，１２０）が、少なくとも部分的に、互いに並列に動作する請求項１６記載の装置。
【請求項１８】
少なくとも１つのプロセッサ（１２０）が、フィードフォワード・トレリス計算を実行するよう適合されている請求項１３から１７のいずれか一項に記載の装置。
【請求項１９】
少なくとも１つのプロセッサ（１２０）が、あり得る終点の経路メトリクスを少なくとも１つのメモリ・ユニット（１３０）内に格納するよう適合されている請求項１８記載の装置。
【請求項２０】
少なくとも１つのプロセッサ（１２０）が、残存経路を示す情報を少なくとも１つのメモリ・ユニット（１４６）内に格納するよう適合されている請求項１３から１９のいずれか一項に記載の装置。
【請求項２１】
少なくとも１つのプロセッサ（１２０）が、トレース・バック・プロセスを実行するよう適合されている請求項１３から２０のいずれか一項に記載の装置。
【請求項２２】
少なくとも１つのプロセッサ（１２０）が、残存経路を示す先に格納された情報をトレース・バック・プロセス中に検索するよう適合されている請求項１３から２１のいずれか一項に記載の装置。
【請求項２３】
前記少なくとも１つのプロセッサ（１１０）が、スレッショルドＤと前記の計算された変数との間の関係に応答して、前記受信されたフレームの終点を決定するよう適合され、
前記装置が、スレッショルドＤを変えることが可能である
請求項１３から２２のいずれか一項に記載の装置。
【請求項２４】
請求項１３から２３のいずれか一項に記載された受信されたフレームの終わりの位置を特定する装置（１００）を備える受信器（９９）。
【国際調査報告】
2008523755.tif 000009
2008523755.tif 000010
2008523755.tif 000011