(57)【要約】  Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャを使用した入力復号化シーケンス、および復号器（４０）を採用した復号化方法で動作するように構成された復号器（４０）が提供されている。復号器（４０）／方法は、復号シーケンスとして選択したパスを出力し、最初の反復以外のＷｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャであるその時点の反復の場合には、その時点の反復までの最良のパスの保存を回避するように構成されている。
2011501612.tif 000002
【特許請求の範囲】
【請求項１】
Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャを使用して入力符号化シーケンスで動作するよう構成された復号器（４０）であって、
前記復号器（４０）は、復号シーケンスとして選択したパスを出力するよう構成されており、
前記復号器（４０）が、最初の反復以外のＷｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャのその時点の反復に対して、前記その時点の反復までの最良のパスの保存を回避するように構成されていることを特徴とする復号器。
【請求項２】
前記復号器（４０）が、前記その時点の反復に対して（１）前記その時点の反復の最良のパスを判定し、（２）前記その時点の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定及び記録するように構成される、請求項１に記載の復号器（４０）。
【請求項３】
前記復号器（４０）が、前記その時点の反復に対して、（１）前記その時点の反復が最大の反復で、最大の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合にのみ、前記その時点の反復の最良のパスを判定し、（２）前記その時点の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定し記録するように構成される、請求項１に記載の復号器（４０）。
【請求項４】
前記復号器（４０）が、前記その時点の反復に対して、（１）前記その時点の反復が最大の反復で、最大の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合にのみ、前記その時点の反復の最良のパスを判定し、（２）前記その時点の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定するように構成される、請求項１に記載の復号器（４０）。
【請求項５】
前記復号器（４０）が、前記その時点の反復に対して、（１）前記その時点の反復の最良のパスを判定し、（２）前記その時点の反復が最大の反復で、最大の反復の最良のパスがＴａｉｌ−Ｂｉｔｉｎｇパスではない場合にのみ、前記その時点の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定するように構成される、請求項１に記載の復号器（４０）。
【請求項６】
復号化工程を実行する方法であって、
ビタビプロシージャの反復を実行することによって、入力復号化シーケンスで動作するＷｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャを使用する工程を含み、
最初の反復以外のＷｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャの反復に対して、最良のパスおよび／または最良のＴａｉｌ−Ｂｉｔｉｎｇパスを見つけて保存するが、前記反復まで最良のパスを保存しないことを特徴とする方法。
【請求項７】
（１）ビタビプロシージャの最初の反復に対して、
（１．１）Ｍ個の開始状態を初期化する工程と、
（１．２）ビタビプロシージャを実行し、Ｍ個のサバイバーパスを見つける工程と、
（１．３）最初の反復の最良のパスを見つける工程と、
（１．４）最初の反復がＴａｉｌ−Ｂｉｔｉｎｇパスであることを判定し、そうであるならば、復号化シーケンスとして最初の反復の最良のパスを復号化および出力する工程と、
（２）反復カウンタを増分し、前記反復カウンタに対応するその時点の反復ｉに対して、
（２．１）反復ｉ−１からＭ個の最後の状態のメトリクスによってＭ個の開始状態メトリクスを初期化する工程と、
（２．２）ビタビプロシージャを実行し、Ｍ個のサバイバーパスを見つける工程と、
（２．３）反復ｉに対して前記その時点の反復ｉまでの最良のパスを保存することなく、反復ｉに対して検索および保存の工程を行う工程と、
（２．４）停止ルールを満たしているかを判定し、そうであるならば、復号化シーケンスとして保存したパスを出力する工程と、
（２．５）最大数の反復が実行されたことを判定し、そうでない場合には、工程（２）に戻る工程と、
（３）パスの存在確認を実行する工程と、
（４）復号化シーケンスとして保存したパスを出力する工程とをさらに含む、請求項６に記載の方法。
【請求項８】
工程（２．３）が、その時点の反復に対して、（１）その時点の反復の最良のパスを判定する工程と、（２）その時点の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定および記録する工程とを含み、
工程（２．４）では、前記保存されたパスが反復ｉまでの前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスであり、
工程（３）が前記最大の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在するかを判定する工程を含み、
工程（４）が、工程（３）の前記判定が肯定の場合に、前記最大の反復までの前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスを出力する工程を含み、
工程（４）が、工程（３）の前記判定が否定の場合に、前記最大の反復の前記最良のパスを出力する工程を含む、請求項７に記載の方法。
【請求項９】
工程（２．３）が、その時点の反復に対して、（１）その時点の反復が最大の反復で、前記最大の反復までの前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合にのみ、その時点の反復の最良のパスを判定する工程、または（２）その時点の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定および記録する工程を含み、
工程（２．４）では、前記保存されたパスが反復ｉまでの前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスであり、
工程（３）が前記最大の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在するかを判定する工程を含み、
工程（４）が、工程（３）の前記判定が肯定の場合に、前記最大の反復までの前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスを出力する工程を含み、
工程（４）が、工程（３）の前記判定が否定の場合に、前記最大の反復の前記最良のパスを出力する工程を含む、請求項７に記載の方法。
【請求項１０】
工程（２．３）が、その時点の反復に対して、（１）その時点の反復が最大の反復で、その時点の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合にのみ、その時点の反復の最良のパスを判定するか、または（２）その時点の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定する工程を含み、
工程（２．４）では、前記保存されたパスが反復ｉの前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスであり、
工程（３）が前記最大の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在するかを判定する工程を含み、
工程（４）が、工程（３）の前記判定が肯定の場合に、前記最大の反復の前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスを出力する工程を含み、
工程（４）が、工程（３）の前記判定が否定の場合に、前記最大の反復の前記最良のパスを出力する工程を含む、請求項７に記載の方法。
【請求項１１】
工程（２．３）が、その時点の反復に対して、（１）その時点の反復の最良のパスを判定し、（２）その時点の反復が最大の反復で、前記最大の反復の前記最良のパスがＴａｉｌ−Ｂｉｔｉｎｇパスではない場合に、その時点の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定する工程を含み、
工程（２．４）では、前記保存されたパスが反復ｉの間の前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスであり、
工程（３）が前記最大の反復に最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在するかを判定する工程を含み、
工程（４）が、工程（３）の前記判定が肯定の場合に、前記最大の反復の前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスを出力する工程を含み、
工程（４）が、工程（３）の前記判定が否定の場合に、前記最大の反復の前記最良のパスを出力する工程を含む、請求項７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００７年１０月２３日に出願された「ＲＥＤＵＣＥＤ−ＣＯＭＰＬＥＸＩＴＹ  ＤＥＣＯＤＩＮＧ  ＡＬＧＯＲＩＴＨＭＳ  ＦＯＲ  ＴＡＩＬ−ＢＩＴＩＮＧ  ＣＯＮＶＯＬＵＴＩＯＮＡＬ  ＣＯＤＥＳ」と題する、米国仮特許出願第６０／９８２，１１２号の利益と優先権を主張するものであり、この特許の全体は参照により本明細書に組み込まれる。
【０００２】
本発明は、畳み込み符号化に関し、特に、Ｔａｉｌ−Ｂｉｔｉｎｇ畳み込み符号を復号化するための復号器および復号化手順に関する。
【背景技術】
【０００３】
多くの環境で、各種形式のデータ（例えば、各種プロトコル、変調など）は送信機から受信機のチャネルにより送信することができる。工程のタイプおよび状況により、一部のチャネルでは、チャネルによって送信されるデータの損失または劣化の影響を受けやすい程度が大きい場合や小さい場合があり、さらにチャネルが異なると、損失または破損の可能性の程度も異なってくる。例えば通常、有線回線の場合、無線またはインターフェースを介して存在するチャネルよりも完全性および信頼性の程度が比較的高くなる。
【０００４】
特定の追加情報をエラー検出符号の形でデータストリームに追加することで、チャネルを介したデータの損失または不正確な送信の検出が可能である。例えば、受信機で、データのフレームまたはブロックをデータストリームに付加することができ、それは、ブロックから計算あるいは取得される（例えば）検査文字またはチェックサムの形のエラー検出符号である。受信機でブロックが受け取られると、受信機では、エラー検出符号（例えば、検査文字またはチェックサムの受信機のバージョン）を独自に再計算または再取得することができる。再計算または再取得されたエラー検出コード（例えば、チェックサム）が受信したブロックまたはフレームに含まれるエラー検出符号と同じ場合、受信機ではブロックまたはフレームが正常に復号化されたことを確認できる。
【０００５】
エラー検出技術に加えて、エラー訂正技術も知られている。例えば、エラー訂正符号（ユーザーデータのフレームまたはブロックで機能する多項式から生成される）もデータストリームに追加することができる。完全なフレームまたはブロックを受け取ると、受信機では知られているエラー訂正コード／技術を使用してデータストリームの特定のエラーを見つけ出し、訂正することができる。
【０００６】
畳み込み符号とは、順方向エラー訂正スキームで、符号化シーケンスが入力ストリームからの現在のデータビットに前のデータビットの一部を加えたものを使用して、アルゴリズムにより達成される。遠隔通信の場合、畳み込み符号は復号化される各ｍビットの情報記号（各ｍビットの文字列）がｎビット記号に変換されるタイプのエラー訂正符号で、ここで、ｍ／ｎは符号レート（ｎ＞ｍ）で、変換は最後のｋ情報記号の関数で、ｋは符号の制約長である。畳み込み符号器のトレリス記述は、符号器への各可能な入力が符号器の出力と状態遷移にどのように影響を与えるかを示す。
【０００７】
符号化後の符号化トレリスの開始状態が常時、符号化トレリスの最後の状態に等しい場合、畳み込み符号（ＣＣ）はＴａｉｌ−Ｂｉｔｉｎｇ（または円形）と呼ばれる。Ｔａｉｌ−Ｂｉｔｉｎｇ畳み込み符号（ＴＢＣＣ）はシンプルで強力な順方向エラー訂正（ＦＥＣ）符号で、例えば、Ｈ．Ｈ．ＭａおよびＪ．Ｋ．Ｗｏｌｆ著「Ｏｎ  ｔａｉｌ  ｂｉｔｉｎｇ  ｃｏｎｖｏｌｕｔｉｏｎａｌ  ｃｏｄｅｓ」，ＩＥＥＥ  Ｔｒａｎｓ，Ｃｏｍｍｕｎ．，第３４巻、１０４〜１１１ページ、１９８６年２月で説明されている。
【０００８】
Ｔａｉｌ−Ｂｉｔｉｎｇ畳み込み符号（ＴＢＣＣ）は、電波、無線、または「ワイヤレス」インターフェースを有する遠隔通信ネットワークを含む、多くの環境で採用されている。Ｔａｉｌ−Ｂｉｔｉｎｇ畳み込み符号（ＴＢＣＣ）は、８０２．１６  ＷｉＭＡＸ（Ｗｏｒｌｄｗｉｄｅ  Ｉｎｔｅｒｏｐｅｒａｂｉｌｉｔｙ  ｆｏｒ  Ｍｉｃｒｏｗａｖｅ  Ａｃｃｅｓｓ）システムのデータチャネルおよびオーバーヘッドチャネル（フレームコントロールヘッダのような）の必須チャネル符号として採用されている。８０２．１６  ＷｉＭＡＸは、例えば、ＩＥＥＥ  Ｓｔｄ  ８０２．１６−２００４、「ＩＥＥＥ  Ｓｔａｎｄａｒｄ  ｆｏｒ  Ｌｏｃａｌ  ａｎｄ  Ｍｅｔｒｏｐｏｌｉｔａｎ  Ａｒｅａ  Ｎｅｔｗｏｒｋｓ−Ｐａｒｔ  １６：Ａｉｒ  Ｉｎｔｅｒｆａｃｅ  ｆｏｒ  Ｆｉｘｅｄ  Ｂｒｏａｄｂａｎｄ  Ｗｉｒｅｌｅｓｓ  Ａｃｃｅｓｓ  Ｓｙｓｔｅｍｓ」、２００４年１０月およびＩＥＥＥ  Ｓｔｄ  Ｐ８０２．１６ｅ−２００５、「ＩＥＥＥ  Ｓｔａｎｄａｒｄ  ｆｏｒ  Ｌｏｃａｌ  ａｎｄ  Ｍｅｔｒｏｐｏｌｉｔａｎ  Ａｒｅａ  Ｎｅｔｗｏｒｋｓ−Ｐａｒｔ  １６：Ａｉｒ  Ｉｎｔｅｒｆａｃｅ  ｆｏｒ  Ｆｉｘｅｄ  ａｎｄ  Ｍｏｂｉｌｅ  Ｂｒｏａｄｂａｎｄ  Ｗｉｒｅｌｅｓｓ  Ａｃｃｅｓｓ  Ｓｙｓｔｅｍｓ」、２００６年２月で説明されており、この両方の内容を参照により本明細書に組み込まれる。さらに、ＥＤＧＥシステムのヘッダチャネルおよびＩＳ−５４システムの制御チャネルのチャネル符号としても採用されている。ＥＤＧＥシステムの説明については、例えば、Ｍ．ＭｚｙｅｃｅおよびＪ．Ｄｕｎｌｏｐ著「Ｐｅｒｆｏｒｍａｎｃｅ  ｅｖａｌｕａｔｉｏｎ  ｏｆ  ｓｕｂｏｐｔｉｍａｌ  ｄｅｃｏｄｉｎｇ  ｓｃｈｅｍｅｓ  ｆｏｒ  ｔａｉｌ  ｂｉｔｉｎｇ  ｃｏｎｖｏｌｕｔｉｏｎａｌ  ｃｏｄｅｓ  ｉｎ  ＥＤＧＥ  ｈｅａｄｅｒｓ」，ＩＥＥ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｌｅｔｔｅｒｓ、第３９巻、第１７号、１２８０〜１２８１ページ、２００３年８月を参照でき、この内容は参照により本明細書に組み込まれる。ＩＳ−５４システムの説明については、例えば、Ｒ．Ｖ．ＣｏｘおよびＣ−Ｅ．Ｗ．Ｓｕｎｄｂｅｒｇ著、「Ａｎ  ｅｆｆｉｃｉｅｎｔ  ａｄａｐｔｉｖｅ  ｃｉｒｃｕｌａｒ  ｖｉｔｅｒｂｉ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｄｅｃｏｄｉｎｇ  ｇｅｎｅｒａｌｉｚｅｄ  ｔａｉｌｂｉｔｉｎｇ  ｃｏｎｖｏｌｕｔｉｏｎａｌ  ｃｏｄｅｓ」，ＩＥＥＥ  Ｔｒａｎｓ．Ｖｅｈ．Ｔｅｃｈｎｏｌ．、第４３巻、５７〜６８ページ、１９９４年２月を参照でき、この内容は参照により本明細書に組み込まれる。
【０００９】
前述のとおり、符号化後の符号化トレリスの最初の状態が常時、符号化トレリスの最後の状態に等しい場合、畳み込み符号（ＣＣ）はＴａｉｌ−Ｂｉｔｉｎｇ（または円形）と呼ばれる。フィードフォワードＣＣの場合、開始状態は単に最後のｖ入力ビットで決定され、ここでｖは全制約長である。例えば、Ｈ．Ｈ．ＭａおよびＪ．Ｋ．Ｗｏｌｆ著、「Ｏｎ  ｔａｉｌ  ｂｉｔｉｎｇ  ｃｏｎｖｏｌｕｔｉｏｎａｌ  ｃｏｄｅｓ」，ＩＥＥＥ  Ｔｒａｎｓ．Ｃｏｍｍｕｎ．、第３４巻、１０４〜１１１ページ、１９８６年２月、ＪｏｈａｎｎｅｓｓｏｎおよびＫ．Ｓ．Ｚｉｇａｎｇｉｒｏｖ著、Ｆｕｎｄａｍｅｎｔａｌｓ  ｏｆ  ｃｏｎｖｏｌｕｔｉｏｎａｌ  ｃｏｄｉｎｇ（畳み込み符号化の基礎）。Ｐｉｓｃａｔａｗａｙ、Ｎｅｗ  Ｊｅｒｓｅｙ：ＩＥＥＥ  Ｐｒｅｓｓ、１９９９年、Ｓ．ＬｉｎおよびＤ．Ｊ．Ｃｏｓｔｅｌｌｏ，Ｊｒ著、Ｅｒｒｏｒ  ｃｏｎｔｒｏｌ  ｃｏｄｉｎｇ（エラー制御の符号化）。Ｕｐｐｅｒ  Ｓａｄｄｌｅ  Ｒｉｖｅｒ、Ｎｅｗ  Ｊｅｒｓｅｙ：Ｐｅａｒｓｏｎ、２００４年を参照でき、この全内容は参照により本明細書に組み込まれる。フィードバックＣＣの場合、符号器構造体は、円形符号化ができるような特定な状況に適合する必要がある。例えば、Ｃ．Ｂｅｒｒｏｕ、Ｃ．Ｄｏｕｉｌｌａｒｄ、およびＭ．Ｊｅｚｅｑｕｅｌ著、「Ｍｕｌｔｉｐｌｅ  ｐａｒａｌｌｅｌ  ｃｏｎｃａｔｅｎａｔｉｏｎ  ｏｆ  ｃｉｒｃｕｌａｒ  ｒｅｃｕｒｓｉｖｅ  ｃｏｎｖｏｌｕｔｉｏｎａｌ（ＣＲＳＣ）ｃｏｄｅｓ」，Ａｎｎａｌｓ  ｏｆ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ、第５４巻、第３〜４号、１６６〜１７２ページ、１９９９年３月〜４月、ならびにＹ．−Ｐ．Ｗａｎｇ、Ｒ．Ｒａｍｅｓｈ、Ａ．Ｈａｓｓａｎ、およびＨ．Ｋｏｏｒａｐａｔｙ著、「Ｏｎ  ＭＡＰ  ｄｅｃｏｄｉｎｇ  ｆｏｒ  ｔａｉｌ−ｂｉｔｉｎｇ  ｃｏｎｖｏｌｕｔｉｏｎａｌ  ｃｏｄｅｓ」，ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ（ＩＳＩＴ）１９９７、２２５ページ、１９９７年６月を参照でき、この両方の内容は参照により本明細書に組み込まれる。
【００１０】
両方の場合（フィードフォワードおよびフィードバックＣＣ）、符号化トレリスの開始状態（円形状態とも呼ばれる）は入力情報ビットベクトルで決定される。つまり、開始状態は必ずしもすべてがゼロ状態に等しいとは限らず、入力ビットの値に左右される。しかし、円形状態の情報は受信機で入手することはできない。したがって、ＴＢＣＣを復号するための復号器の１つの重要なタスクは受信したソフトビットメトリクスに基づいて円形状態を推定することである。
【００１１】
従来のＺｅｒｏ−Ｔａｉｌ畳み込み符号（ＺＴＣＣ）および一部のブロック符号によるＴａｉｌ−Ｂｉｔｉｎｇ畳み込み符号（ＴＢＣＣ）の使用には多くの利点がある。その利点は次のとおりである。
【００１２】
１．Ｚｅｒｏ−Ｔａｉｌ畳み込み符号（ＺＴＣＣ）では、符号化トレリスをすべてゼロ状態で終了するには、ｖ個の冗長Ｚｅｒｏ−Ｔａｉｌビットを使用する必要がある。Ｔａｉｌ−Ｂｉｔｉｎｇ畳み込み符号（ＴＢＣＣ）では、Ｚｅｒｏ−Ｔａｉｌビットは必要ではなく、ペイロードビットで置き換えて、チャネル符号のスペクトル効率を増大させることができる。
【００１３】
２．多くの優れたブロック符号が等価ＴＢＣＣ（例えば、Ｐ．Ｓｔａｈｌ、Ｊ．Ｂ．Ａｎｄｅｒｓｏｎ、およびＲ．Ｊｏｈａｎｎｅｓｓｏｎ著、「Ｏｐｔｉｍａｌ  ａｎｄ  ｎｅａｒ−ｏｐｔｉｍａｌ  ｅｎｃｏｄｅｒｓ  ｆｏｒ  ｓｈｏｒｔ  ａｎｄ  ｍｏｄｅｒａｔｅ−ｌｅｎｇｔｈ  ｔａｉｌ−ｂｉｔｉｎｇ  ｔｒｅｌｌｉｓｅｓ」，ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ、第４５巻、２５６２〜２５７１ページ、１９９９年１１月を参照でき、その内容は参照により本明細書に組み込まれる）で生成できるので、トレリス符号のより効率的なソフト入力ソフト出力復号化アルゴリズムで復号化することができる。例えば、Ｒ．Ｙ．Ｓｈａｏ、Ｓ．Ｌｉｎ、およびＭ．Ｐ．Ｃ．Ｆｏｓｓｏｒｉｅｒ著、「Ｔｗｏ  ｄｅｃｏｄｉｎｇ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｔａｉｌ−ｂｉｔｉｎｇ  ｃｏｄｅｓ」，ＩＥＥＥ  Ｔｒａｎｓ．Ｃｏｍｍｕｎ．、第５１巻、第１０号、１６５８〜１６６５ページ、２００３年１０月、Ｒ．ＪｏｈａｎｎｅｓｓｏｎおよびＫ．Ｓ．Ｚｉｇａｎｇｉｒｏｖ著、Ｆｕｎｄａｍｅｎｔａｌｓ  ｏｆ  ｃｏｎｖｏｌｕｔｉｏｎａｌ  ｃｏｄｉｎｇ（畳み込み符号化の基礎）。Ｐｉｓｃａｔａｗａｙ、Ｎｅｗ  Ｊｅｒｓｅｙ：ＩＥＥＥ  Ｐｒｅｓｓ、１９９９年、Ｓ．ＬｉｎおよびＤ．Ｊ．Ｃｏｓｔｅｌｌｏ，Ｊｒ著、Ｅｒｒｏｒ  ｃｏｎｔｒｏｌ  ｃｏｄｉｎｇ（エラー制御の符号化）。Ｕｐｐｅｒ  Ｓａｄｄｌｅ  Ｒｉｖｅｒ、Ｎｅｗ  Ｊｅｒｓｅｙ：Ｐｅａｒｓｏｎ、２００４年を参照でき、この全内容は参照により本明細書に組み込まれる。
【００１４】
Ｔａｉｌ−Ｂｉｔｉｎｇ畳み込み符号（ＴＢＣＣ）の優れた性能を実現するには、円形状態（または状態メトリクスの点での開始状態の確率分布）がより効率的で、復号化プロセスの前、またはそのプロセスと同時に正確に推定される必要がある。円形状態（または状態メトリクスの点での開始状態の確率分布）の推定およびＴａｉｌ−Ｂｉｔｉｎｇ畳み込み符号（ＴＢＣＣ）の符号化のために、効率的な多くのアルゴリズムが提案されている。これらのアルゴリズムは、おおよそ２つのカテゴリに分類することができる。第１のカテゴリは、最尤（ＭＬ）ビタビタイプアルゴリズムである（例えば、Ｒ．Ｙ．Ｓｈａｏ、Ｓ．Ｌｉｎ、およびＭ．Ｐ．Ｃ．Ｆｏｓｓｏｒｉｅｒ著、「Ｔｗｏ  ｄｅｃｏｄｉｎｇ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｔａｉｌ−ｂｉｔｉｎｇ  ｃｏｄｅｓ」，ＩＥＥＥ  Ｔｒａｎｓ．Ｃｏｍｍｕｎ．、第５１巻、第１０号、１６５８〜１６６５ページ、２００３年１０月、を参照でき、この内容は参照により本明細書に組み込まれる）。第２のカテゴリは最大事後確率（ＭＡＰ）ＢＣＪＲタイプアルゴリズムである。例えば、Ｌ．Ｒ．Ｂａｈｌ、Ｊ．Ｃｏｃｋｅ、Ｆ．Ｊｅｌｉｎｋ、およびＪ．Ｒａｖｉｖ著、「Ｏｐｔｉｍａｌ  ｄｅｃｏｄｉｎｇ  ｏｆ  ｌｉｎｅａｒ  ｃｏｄｅｓ  ｆｏｒ  ｍｉｎｉｍｉｚｉｎｇ  ｓｙｍｂｏｌ  ｅｒｒｏｒ  ｒａｔｅ」，ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ、第２０巻、２８４〜２８７ページ、１９７４年３月、ならびにＪ．Ｂ．ＡｎｄｅｒｓｏｎおよびＳ．Ｍ．Ｈｌａｄｉｋ著、「Ｔａｉｌｂｉｔｉｎｇ  ＭＡＰ  ｄｅｃｏｄｅｒｓ」，ＩＥＥＥ  Ｊ．Ｓｅｌｅｃｔ．Ａｒｅａｓ  Ｃｏｍｍｕｎ．、第１６巻、２９７〜３０２ページ、１９９８年２月を参照でき、この内容は参照により本明細書に組み込まれる。
【００１５】
本明細書で説明している技術は、主に、複雑さを低減化したビタビタイプアルゴリズムに焦点を当てている。その中で、Ｗｒａｐ−Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ（ＷＡＶＡ）では、性能と複雑さの間で優れた折り合いをつけることができる。複雑さを低減化したビタビタイプアルゴリズムが説明されているのは、例えば、Ｒ．Ｙ．Ｓｈａｏ、Ｓ．Ｌｉｎ、およびＭ．Ｐ．Ｃ．Ｆｏｓｓｏｒｉｅｒ著、「Ｔｗｏ  ｄｅｃｏｄｉｎｇ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｔａｉｌ−ｂｉｔｉｎｇ  ｃｏｄｅｓ」，ＩＥＥＥ  Ｔｒａｎｓ．Ｃｏｍｍｕｎ．、第５１巻、第１０号、１６５８〜１６６５ページ、２００３年１０月で、この内容は参照により本明細書に組み込まれる。ＷＡＶＡについては以下で簡潔に要約している。
【００１６】
Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ（ＷＡＶＡ）はＴａｉｌ−Ｂｉｔｉｎｇ符号のトレリスの開始および終了状態が同じであるプロパティに基づいているので、トレリスはトレリスの開始および終了部分を共に接続することでシリンダーと見なすことができる。次に、従来のビタビアルゴリズムがいくつかのサイクル（または反復）の復号トレリスで行われ、開始状態（状態メトリクスの点で）の確率分布の推定が向上する。Ｍ＝２ｖはトレリスの状態の数、Ｌはトレリスの長さ（またはトレリス段階の数）、およびＩは、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ（ＷＡＶＡ）に許可されたサイクル（または反復）の最大数とする。（ρ(i)best、ｍ(i)best）は反復ｉまでの最良のパスおよびパスメトリック、ならびに（ρ(i)TB,best、ｍ(i)TB,best）は反復ｉまでの最良のＴａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ）およびパスメトリックとする。本明細書で使用しているように、「反復ｉまでの」最良のパスとは（Ｔａｉｌ−Ｂｉｔｉｎｇかどうかに関係なく）、今までのところ、その時点の反復ｉを含むすべての反復で発生する最良のパスを意味する。他方、（σ(i)best、τ(i)best）は反復ｉの間の最良のパスおよびパスメトリック、ならびに（σ(i)TB,best、τ(i)TB,best）は反復ｉの間の最良のＴａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ）およびパスメトリックとする。ここのＴａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ）は、同じ開始状態および終了状態の復号化パスとして定義される。したがって、反復ｉの間に復号器がσ(i)TB,bestを見つけることはできない。状態メトリクスは本当に最初の反復から蓄積され、ビタビアルゴリズムのサバイバーパスの選択で使用されることに留意されたい。しかし、各反復中の最良のパスの選択および最良のＴａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ）はパスメトリクスに基づいており、それは、１つの反復中の開始状態のメトリクスにより差し引かれた終了状態のメトリクスに等しくなる。反復ｉの間、τ(i)bestがｍ(i-1)bestより大きい場合、（ρ(i)best、ｍ(i)best）は（σ(i)best、τ(i)best）に更新されるか、そうではない場合には（ρ(i)best、ｍ(i)best）は前の値（ρ(i-1)best、ｍ(i-1)best）に設定される。同じ規則が最良のＴＢＰの更新にも適用される。
【００１７】
従来のＷｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ（ＷＡＶＡ）については、次の順序の工程またはステップにより説明することができる。
【００１８】
（工程１）Ｍ個すべての開始状態のメトリクスをゼロに初期化して、開始状態がすべて同じようになるようにする。
【００１９】
（工程２）最初の反復で、従来のビタビアルゴリズムが実行され、Ｍ個の終了状態でＭ個のサバイバーパスを見つける。Ｍ個のサバイバーパス中の最良のパス（最大のパスメトリックを有する）がＴａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ）の場合には、復号化プロセスが終了し、復号器は復号化シーケンスとして最良のパスを出力する。あるいは、（ρ(l)best、ｍ(l)best）と（ρ(l)TB,best、ｍ(l)TB,best）が存在する場合には、そのペアを記録する。
【００２０】
（工程３）反復ｉで、ｉ＞１の場合、Ｍ個の開始状態の状態メトリクスは、反復（ｉ−１）のＭ個の最終状態の状態メトリクスによって初期化され、そして従来のビタビアルゴリズムが実行され、Ｍ個の終了状態でＭ個のサバイバーパスを見つける。反復ｉの終わりで、（ρ(i)best、ｍ(i)best）と（ρ(i)TB,best、ｍ(i)TB,best）の両方が更新される。ρ(i)TB,bestが存在し、何らかの終了条件を満たしている場合、復号化プロセスは終了し、復号器は復号化シーケンスとしてρ(i)TB,bestを出力する。そうではない場合には、工程４が行われる。
【００２１】
（工程４）復号化プロセスが終了するか（何らかの終了条件を満たすので）、反復Ｉの最大数に達したためのいずれかまで、工程３が繰り返される。
【００２２】
（工程５）復号器は、ρ(l)TB,bestが存在する場合には復号化シーケンスとしてρ(l)TB,bestを出力する。そうではない場合、復号器は復号化シーケンスとしてρ(l)bestを出力する。
【００２３】
上記工程３では、可能な２つの条件（または停止ルール）を使用できる（例えば、Ｒ．Ｙ．Ｓｈａｏ、Ｓ．Ｌｉｎ、およびＭ．Ｐ．Ｃ．Ｆｏｓｓｏｒｉｅｒ著、「Ｔｗｏ  ｄｅｃｏｄｉｎｇ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｔａｉｌ−ｂｉｔｉｎｇ  ｃｏｄｅｓ」，ＩＥＥＥ  Ｔｒａｎｓ．Ｃｏｍｍｕｎ．、第５１巻、第１０号、１６５８〜１６６５ページ、２００３年１０月、を参照でき、この内容は参照により本明細書に組み込まれる）。可能な第１の終了条件はシンプル終了条件と呼ばれ、この場合ρ(i)TB,best＝ρ(i)bestなので、反復ｉまでの最良のパスは反復ｉまでの最良のＴａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ）である。可能な第２の終了条件は充足終了条件と呼ばれ、この場合、反復ｉ（ｍ(i)TB,best）までの最良のＴａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ）のメトリックは何らかの適応閾値と比較される。充足条件により、出力Ｔａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ）が最尤（ＭＬ）の解決策であることが保証される。充足終了条件の詳細については、Ｒ．Ｙ．Ｓｈａｏ、Ｓ．Ｌｉｎ、およびＭ．Ｐ．Ｃ．Ｆｏｓｓｏｒｉｅｒ著、「Ｔｗｏ  ｄｅｃｏｄｉｎｇ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｔａｉｌ−ｂｉｔｉｎｇ  ｃｏｄｅｓ」，ＩＥＥＥ  Ｔｒａｎｓ．Ｃｏｍｍｕｎ．、第５１巻、第１０号、１６５８〜１６６５ページ、２００３年１０月を参照でき、この内容は参照により本明細書に組み込まれる。
【００２４】
一般に、上記２つの終了条件での性能はほとんど同一で、最適化最尤（ＭＬ）復号化の性能とほとんど同じである。例えば、Ｔ．−Ｔ．Ｊａｓｏｎ  Ｃｈｅｎ、Ｓ．Ｓｈａｗｎ  Ｔｓａｉ著、「Ｆｉｎａｌ  ｒｅｐｏｒｔ  ｏｎ  ２００５  ＷｉＭＡＸ  ｌｉｎｋ  ｓｉｍｕｌａｔｉｏｎ」，０５／０３６３−６／ＦＣＰ  １０１  ３６３０  Ｕｅｎ、Ｅｒｉｃｓｓｏｎ  Ｉｎｔｅｒｎａｌ  Ｔｅｃｈｎｉｃａｌ  Ｄｏｃｕｍｅｎｔ、２００６年３月を参照でき、この内容は参照により本明細書に組み込まれる。しかし、充足終了条件の場合の復号器では、シンプル終了条件の場合の復号器より高度な複雑さ（閾値の計算および記憶）が必要であるが、平均の反復（サイクル）数はより少なくて済む。
【発明の概要】
【発明が解決しようとする課題】
【００２５】
しかし、既存の解決策には問題がある。例えば、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ（ＷＡＶＡ）の反復中には（ρ(i)best、ｍ(i)best）と（ρ(i)TB,best、ｍ(i)TB,best）の両方を保存し、各反復後には更新する必要がある。（ρ(i)best、ｍ(i)best）と（ρ(i)TB,best、ｍ(i)TB,best）の値の保存および更新には、より複雑な計算が必要でメモリの使用もより必要となる。パケット長が長かったり、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ（ＷＡＶＡ）で必要な反復（サイクル）の平均数が大きい場合（低ＳＮＲ領域を超えるような場合）には特にそうである。計算がより複雑でメモリの使用量もより大きいことは望ましいものではない。特に、無線アクセスネットワークアプリケーションや特に、ワイヤレスターミナル（例えば、移動局端末側）ではそうである。
【課題を解決するための手段】
【００２６】
本発明の一態様において、本明細書で説明している技術は、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャを使用した入力符号化シーケンスで動作するように構成された復号器、およびその復号器が採用する復号化方法に関するものである。復号器／方法は、復号シーケンスとして選択したパスを出力し、最初の反復以外のＷｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャであるその時点の反復の場合には、その時点の反復までの最良のパスの保存を回避するように構成されている。
【００２７】
本明細書で説明している技術は、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ（ＷＡＶＡ）を使用した復号化プロセス間に、開始状態の確率分布の正確さ（メトリクスの点で）が一般に、１つの反復からその次の反復へと移るにつれ向上するという事実を活用している。その結果、反復ｉの間に見つかった最良のパス（または最良のＴａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ））は、反復（ｉ−１）までに見つかっている最良のパス（または最良のＴａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ））より優れている可能性が非常に高い。したがって、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ（ＷＡＶＡ）の反復ｉの間、本明細書で説明している復号器および復号化方法により、反復（ｉ−１）までに見つかっている最良のパスを追跡する必要はなく、その時点の反復ｉの間に見つかる最良のパスおよび最良のＴａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ）を使用することで一般的には十分である。
【００２８】
本明細書で説明している技術は、アルゴリズムの実行の複雑さを低減化することによりＷｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ（ＷＡＶＡ）の利用を向上させる、新しいスキーム（例えば、復号器の新しい実施形態および復号化工程の新しいモード）から構成される。第１のスキームはＷＡＶＡ１（第１の複雑さを低減化したＷｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ）と呼ばれ、第２のスキームはＷＡＶＡ２（第２の複雑さを低減化したＷｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ）と呼ばれる。上述のように、終了条件には、シンプル終了条件と充足終了条件の２種類がある。ＷＡＶＡ１シンプル、ＷＡＶＡ１充足、ＷＡＶＡ２シンプル、およびＷＡＶＡ２充足は、この技術の好適なアルゴリズムの例である。
【００２９】
一特定の例示的な実施形態およびモード（「ＷＡＶＡ１シンプル」）において、復号器／方法は、その時点の反復に対して、（１）その時点の反復の最良のパスを判定し、（２）その時点の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定し記録するように構成されている。
【００３０】
別の特定の例示的な実施形態およびモード（「ＷＡＶＡ１充足」）では、復号器／方法は、その時点の反復に対して、（１）その時点の反復が最大の反復であり、最大の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合にのみ、その時点の反復の最良のパスを判定するか、または（２）その時点の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定し記録するように構成されている。
【００３１】
別の特定の例示的な実施形態およびモード（「ＷＡＶＡ２充足」）では、復号器／方法は、その時点の反復に対して、（１）その時点の反復が最大の反復であり、最大の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合にのみ、その時点の反復の最良のパスを判定するように、または（２）その時点の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定するように構成されている。
【００３２】
さらに別の特定の例示的な実施形態およびモード（「ＷＡＶＡ２シンプル」）では、復号器／方法は、（１）その時点の反復の最良のパスを判定し、（２）その時点の反復が最大の反復で最大の反復の最良のパスがＴａｉｌ−Ｂｉｔｉｎｇパスではない場合にのみその時点の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定し保存するように構成されている。
【００３３】
本発明の前述および他の目的、特徴、および利点は、各種の図全体を通して参照符号が同じ部品を表す、添付図面で例示する好適な実施形態のより詳細な説明から明らかになろう。図面は、必ずしもスケール調整する必要はなく、むしろ本発明の原理の例示に基づき配置されていることが強調されている。
【図面の簡単な説明】
【００３４】
【図１】例示的な実施形態による符号器を備える通信ノードまたはデバイスのブロック図である。
【００３５】
【図２】一般モードの図１の例示的符号器で実行される例示的な一般工程またはステップを示す流れ図である。
【００３６】
【図２Ａ】第１の特定モードの図１の例示的符号器で実行される例示的な工程またはステップを示す流れ図である。
【００３７】
【図２Ｂ】第２の特定モードの図１の例示的符号器で実行される例示的な工程またはステップを示す流れ図である。
【００３８】
【図２Ｃ】第３の特定モードの図１の例示的符号器で実行される例示的な工程またはステップを示す流れ図である。
【００３９】
【図２Ｄ】第４の特定モードの図１の例示的符号器で実行される例示的な工程またはステップを示す流れ図である。
【００４０】
【図３】長さ２４レート１／２のＴａｉｌ−Ｂｉｔｉｎｇ畳み込み符号（ＴＢＣＣ）のＦＥＲの比較を示すグラフである。
【００４１】
【図４】長さ２４レート１／２のＴａｉｌ−Ｂｉｔｉｎｇ畳み込み符号（ＴＢＣＣ）のＢＥＲの比較を示すグラフである。
【００４２】
【図５】長さ２４レート１／２のＴａｉｌ−Ｂｉｔｉｎｇ畳み込み符号（ＴＢＣＣ）に必要な平均反復数の比較を示すグラフである。
【００４３】
【図６】長さ２４０レート１／２のＴａｉｌ−Ｂｉｔｉｎｇ畳み込み符号（ＴＢＣＣ）のＦＥＲの比較を示すグラフである。
【００４４】
【図７】長さ２４０レート１／２のＴａｉｌ−Ｂｉｔｉｎｇ畳み込み符号（ＴＢＣＣ）のＢＥＲの比較を示すグラフである。
【００４５】
【図８】長さ２４０レート１／２のＴａｉｌ−Ｂｉｔｉｎｇ畳み込み符号（ＴＢＣＣ）に必要な平均反復数の比較を示すグラフである。
【発明を実施するための形態】
【００４６】
次の記述では、制限するのではなく説明目的で、特定のアーキテクチャ、インターフェース、技術などの特定の詳細を、本発明が十分に理解できるように説明している。しかし、本発明が、これらの特定の詳細以外の他の実施形態でも実施可能であることは当業者には明らかであろう。つまり、当業者の場合、本明細書で明示的に記述または提示されていなくても、本発明の原理を具体化し、本発明の精神および範囲内に含まれる装置を考案することができる。一部の例では、不必要な詳細で本発明の説明が不明瞭にならないために、よく知られたデバイス、回路、および方法の詳細な説明が省かれている。本発明の原理、態様、および実施形態を列挙する本明細書の全記述のほか、それについての特定の例も、それに関する構造的および機能的同等物の両方を包含することを意図している。さらに、そのような同等物には現在知られている同等物と、将来、開発される同等物の両方、すなわち、構造に関係なく同じ機能を実行するよう開発されたすべての構成部品も含まれることを意図している。
【００４７】
したがって、例えば、本明細書のブロック図は技術の原理を具体化する例示的回路の概念的表示であることは当業者には明らかであろう。同様に、すべての流れ図、状態遷移図、擬似コードなどは、実質上、コンピュータの読み出し可能な媒体で表され、そのため、そのようなコンピュータやプロセッサが明示的に表示されているかどうかに関係なく、コンピュータまたはプロセッサで実行することができる各種プロセスを意味していることを認識されたい。
【００４８】
「プロセッサ」または「コントローラ」としてラベル付けまたは記述されている機能ブロックを含む各種構成部品の機能は、専用ハードウェアの使用のほか、適切なソフトウェアに関連付けられたソフトウェアを実行できるハードウェアによっても提供することができる。プロセッサによって提供される場合、その機能は、単一の専用プロセッサ、単一の共有プロセッサ、複数の個々のプロセッサで、その一部で共有または分散しているものによって提供することができる。さらに、「プロセッサ」または「コントローラ」という用語の明示的な使用は、ソフトウェアを実行可能なハードウェアのみを指していると解釈されるべきではなく、これらに限定されるわけではないが、デジタルシグナルプロセッサ（ＤＳＰ）ハードウェア、ソフトウェア保存用の読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、および不揮発性ストレージを含めることができる。
【００４９】
図１では、本技術の使用に適したノードまたはデバイス２０の例示的な実施形態を示している。ノードまたはデバイス２０はインターフェース２２を介して、別のノードまたはデバイス２４と通信している。例示している限定されない例ではそのようになるが、ノードまたはデバイス２０およびノードまたはデバイス２４は、無線アクセスネットワークを構成またはその中に存在しており、インターフェース２２は無線または電波インターフェースである。無線アクセスネットワークの例示例の環境では、ノードまたはデバイス２０およびノードまたはデバイス２４のいずれかは、基地局ノード（他の名称では、無線基地局、ＮｏｄｅＢ、またはｅＮｏｄｅＢとしても知られている）で、もう一方は、ワイヤレスターミナルなど（他の名称では、モバイルターミナル、移動局、またはユーザー装置ユニット（ＵＥ）としても知られている）である。ノードまたはデバイス２０の一般的な例示的構成要素または構成部品は、（無線アクセスネットワークの例示的環境で）ノードまたはデバイス２０が基地局ノードまたはワイヤレスターミナルのいずれかであるような方法で図１に示している。
【００５０】
図１では、代表的なノードまたはデバイス２０を、トランシーバー３０を備えるものとして示しており、それによってノードまたはデバイス２０は、インターフェース２２を介して他のノードまたはデバイス２４と通信する。ノードまたはデバイス２０からノードまたはデバイス２４までのリンクで、トランシーバー３０はアプリケーション／インターフェース３２から送信のデータを取得する。アプリケーション／インターフェース３２という用語は、送信用のデータソースが、ノードまたはデバイス２０で実行されるアプリケーション（例えば、ソフトウェアまたはプログラム）、またはノードまたはデバイス２０が別のアップストリームノードまたは別のデバイス（図１では非例示）からデータを受け取るインターフェースのいずれかであることを示すために利用される。さらに図１では、ノードまたはデバイス２０をフレーマ／フォーマッタ３４を備えるものとして示しており、これは、ソース（例えば、アプリケーション／インターフェース３２）から取得されたデータをフレーム、ブロックなどの送信ユニットにアセンブルする。さらに、ノードまたはデバイス２０は、アプリケーション／インターフェース３２を介してトランシーバー３０で送信される送信ユニットを符号化する符号器を備えている。
【００５１】
受信側のノードまたはデバイス２０ではデフレーマ／デフォーマッタ３８を備え、これは、データの入力ストリーム（例えば、インターフェース２２を介しての他のノードまたはデバイス２４から入力）を、アプリケーション／インターフェース３２で使用可能な送信ユニット（フレーム、ブロックなど）にセグメント化する。さらにノードまたはデバイス２０では復号器４０を備えており、これはデータシンク、すなわちアプリケーション／インターフェース３２で使用するために、トランシーバー３０で取得された送信ユニットを復号化する。ノードまたはデバイス２０の受信側に関して、アプリケーション／インターフェース３２という用語はノードまたはデバイス２０で受信されるデータのデータシンクが、ノードまたはデバイス２０で実行されるアプリケーション（例えば、ソフトウェアまたはプログラム）、またはノードまたはデバイス２０が別のアップストリームノードまたは別のデバイス（図１では非例示）からデータを転送するインターフェースのいずれかであることを示すために利用される。
【００５２】
本技術の特徴は、復号器４０およびそれによって実行される復号化工程である。復号器４０のいくつかの例示的実施形態および復号化手順の実装形態の様々なモードが本明細書で説明されている。復号器４０およびその工程方法の説明を続ける前に、図１の例示的で代表的なノードまたはデバイス２０には、通常、受信側と送信側の両方で他の構成部品や構成要素があり、普通、図１で例示し本明細書で説明しているものより、全体構造と工程の点で、かなり複雑であることを強調しておきたい。しかし、ノードまたはデバイス２０を備える選択した構成部品および構成要素のみが図１に描写されているのは、本技術のより明確で、あいまいさのない説明を提供するためである。さらに、ノードまたはデバイス２０の工程環境は無線アクセスネットワークに限定されているわけではなく、ノードまたはデバイス２０は無線または電波インターフェース以外の（限定を受けない例として）有線インターフェースや光インターフェースなどのインターフェースを介して、他のノードまたはデバイス２４と通信することができることも認識されたい。さらに、工程環境が無線アクセスネットワークである特定の状況では、無線アクセスネットワークのタイプは重要なことではなく、例えば、ＧＳＭ、ＵＴＲＡＮ、ＥＤＧＥ、ＷｉＭＡＸ、ＬＴＥ、または他のタイプの無線アクセスネットワークで構成することができる。
【００５３】
例示的な各種実施形態およびモードで、復号器４０は、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャを使用した入力符号化シーケンスで動作するよう構成されている。復号器４０は、復号シーケンスとして選択したパスを出力し、最初の反復以外のＷｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャであるその時点の反復の場合には、その時点の反復までの最良のパスの保存を回避するように構成されている。
【００５４】
復号器４０の構造および工程は、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ（ＷＡＶＡ）を使用した復号化プロセス間に、開始状態の確率分布の正確さ（メトリクスの点で）が一般に、１つの反復からその次の反復へと移るにつれ向上するという事実を活用している。その結果、反復ｉの間に見つかった最良のパス（または最良のＴａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ））は、反復（ｉ−１）までに見つかっている最良のパス（または最良のＴａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ））より優れている可能性が非常に高い。したがって、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ（ＷＡＶＡ）の反復ｉの間、本明細書で説明している復号器および復号化方法により、反復（ｉ−１）までに見つかっている最良のパスおよび最良のＴａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ）を追跡する必要はなく、その時点の反復ｉの間に見つかる最良のパスおよび最良のＴａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ）を使用することで十分なはずである。
【００５５】
本明細書で説明している技術では、限定を受けない例という形で、復号器４０の４つの例示的実施形態と対応する復号化の４つのモードを使用している。これらの４つの実施形態／モードは以下で、ＷＡＶＡ１シンプル、ＷＡＶＡ２シンプル、ＷＡＶＡ１充足、およびＷＡＶＡ２充足として説明および／または名付けられている。前述から理解されるように、「ＷＡＶＡ」とは、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍの略語で、「Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ」という成句は「Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャ」や「Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉ技術」と同義的に使用されている。
【００５６】
本明細書および図面全体で、「ＷＡＶＡ１」または「ＷＡＶＡ２」のみが表示されている場合には、シンプルと充足の両方の終了条件が適用されるものと理解されたい。
【００５７】
ある特定の実施形態およびモードを説明する前に、一般的な実施形態およびモードを、図２を参照して説明する。図２の例示的で一般的であり代表的な工程またはステップは動作の一般的な方法を反映しており、同様に一般的な復号器４０が本技術を実行するように構築または構成することができることを認識されたい。
【００５８】
図２の工程２−１には、Ｍ個すべての開始状態メトリクスをゼロに初期化して、開始状態がすべて同じようになることが含まれる。次に、工程２−２として、最初の反復に対し、従来のビタビアルゴリズムが実行され、Ｍ個の最後の状態でＭ個のサバイバーパスが見つかる。工程２−３には、最初の反復に対して、最良のパスρ(l)bestを見つけることが含まれる。工程２−４として、Ｍ個のサバイバーパスの中で最良のパスρ(l)best（最大のパスメトリクスを有する）はＴａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ）であることが判定される場合には、（工程２−５として）復号化プロセスが終了し、復号器は復号化シーケンスとして最良のパスρ(l)bestを出力する。そうではない場合には、オプションの工程２−６、その次に工程２−７と手順が続く。
【００５９】
（ρ(l)TB,best、ｍ(l)TB,best）などのペアが存在する場合には、オプション工程２−６に、復号器４０が（ρ(l)TB,best、ｍ(l)TB,best）などの最初の反復の情報の保存または記録を行うことを含めることができる。より特定なモードを参照して理解されるとおり、このオプション工程２−６は、ＷＡＶＡ１シンプルおよびＷＡＶＡ１充足のモードで実行される。ＷＡＶＡ２シンプルおよびＷＡＶＡ２充足の各モードの場合には、（ρ(l)TB,best、ｍ(l)TB,best）を見つける必要はない。
【００６０】
工程２−７には、反復カウンタｉを増分するが含まれる。したがって、最初の反復後の最初の実行の場合、反復カウンタｉ＝１＋１＝２である。
【００６１】
工程２−８には、各反復ｉ（ｉ＞１）に対して、反復（ｉ−１）のＭ個の最終状態の状態メトリクスによって、Ｍ個の開始状態の状態メトリクスを初期化することが含まれる。工程２−９には、従来のビタビアルゴリズムを実行して、Ｍ個の最後の状態でＭ個のサバイバーパスを見つけることが含まれる。
【００６２】
工程２−１０には、最良のパスおよび最良のＴａｉｌ−Ｂｉｔｉｎｇパスの少なくとも１つを見つけることが含まれる。ＷＡＶＡ１モードなどの一部のモードでは、工程２−１０で見つかる最良のパスが反復ｉ［σ(i)best］の最良のパスで、最良のＴａｉｌ−Ｂｉｔｉｎｇパスは反復ｉまでの最良のＴａｉｌ−Ｂｉｔｉｎｇパス［ρ(i)TB,best］で、（ρ(i)TB,best、ｍ(i)TB,best）は更新される。ＷＡＶＡ１モードの一部のバージョンでは、その時点の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合にのみ、最大反復の最良のパスが判定され保存される。
【００６３】
ＷＡＶＡ２モードなどの他のモードでは、工程２−１０で見つかる最良のパス［σ(i)best］が反復ｉの最良のパスで、最良のＴａｉｌ−Ｂｉｔｉｎｇパスは反復ｉの最良のＴａｉｌ−Ｂｉｔｉｎｇパス［σ(i)TB,best］である。ＷＡＶＡ２モードの一部のバージョンでは、その時点の反復が最大反復で、最大反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合にのみ、その時点の反復の最良のパスが判定され保存される。工程２−１０は、最初の反復以外のＷｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャのその時点の反復に対して、その時点の反復までの最良のパス（例えば、その時点の反復の前に見つかる任意の最良のパス）の保存を回避するように実行される。
【００６４】
工程２−１１には、有効な特定の停止ルールが満たされるかどうかを判定することが含まれる。すでに示しているように、停止ルールは、両方ともすでに説明している、シンプル終了条件または充足終了条件のいずれかに従うことができる。停止ルールが満たされる場合、工程２−１２のとおり、復号化は終了し、復号器４０は適切な復号化シーケンスを出力する。工程２−１２のとおり、ＷＡＶＡ１モードに対して、復号器４０は復号化シーケンスとしてρ(i)TB,bestを出力し、ＷＡＶＡ２シンプルに対して、復号器４０は復号化シーケンスとしてσ(i)bestを出力し、ＷＡＶＡ２充足に対して、復号器４０は復号器シーケンスとしてσ(i)TB,bestを出力する。
【００６５】
停止ルールを満たしていない場合（工程２−１１での判定のとおり）、工程２−１１Ａのとおり、反復ｉまでの最良のＴａｉｌ−Ｂｉｔｉｎｇパス［ρ(i)TB,best］およびそのメトリック（例えば、ｍ(i)TB,best）がＷＡＶＡ１モードに対して記録される。工程２−１１ＡはＷＡＶＡ１モードに対してのみ実行されるので、図２では破線で表示している。
【００６６】
工程２−１３には、反復の最大数（「Ｊ」）に達したかどうかを確認することが含まれる。そうではない場合、後続の反復に対して、少なくとも工程２−７から工程２−１１までが実行される。反復の最大数に達している場合、工程２−１４が実行される。
【００６７】
工程２−１４は最良のＴａｉｌ−Ｂｉｔｉｎｇパスの存在確認である。ＷＡＶＡ１シンプルとＷＡＶＡ１充足のモードの場合、工程２−１４には、ρ(J)TB,bestが存在しているかを判定することが含まれる。ＷＡＶＡ２シンプルとＷＡＶＡ２充足の場合、工程２−１４には、σ(J)TB,bestが存在しているかを判定することが含まれる。
【００６８】
最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合、工程２−１５のとおり、復号化は終了し、最良のＴａｉｌ−Ｂｉｔｉｎｇパスが復号化シーケンスとして出力される。ＷＡＶＡ１モードの場合、工程２−１５のとおり、復号器４０は復号化シーケンスとしてρ(J)TB,bestを出力する。ＷＡＶＡ２モードの場合、工程２−１５のとおり、復号器４０は復号化シーケンスとしてσ(J)TB,bestを出力する。
【００６９】
最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合、工程２−１６のとおり、復号化は終了し、最良のパスが復号化シーケンスとして出力される。ＷＡＶＡ１モードとＷＡＶＡ２モードの場合、工程２−１６のとおり、復号器４０は復号化シーケンスとしてσ(J)bestを出力する。
【００７０】
図２Ａでは、特定の一例示的実施形態およびモードで実行される例示的工程またはステップを示している。図２Ａの特定の例示的な実施形態およびモードでは、復号器／方法は、その時点の反復に対して、（１）その時点の反復の最良のパス、および（２）その時点の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定し保存するように構成されている。図２Ａの特定の例示的な実施形態およびモードは、ＷＡＶＡ１シンプルの実施形態／モードである。
【００７１】
基本的に一般的な図２の実施形態／モードの工程と同一の図２Ａの実施形態／モードの工程には、対応する参照符号が付いている。図２Ａで詳述する図２Ａの実施形態／モードの工程には、工程番号に２Ａという接頭語が付いており、工程２Ａ−１０、工程２Ａ−１２、および工程２Ａ−１４から２Ａ−１６までが含まれる。
【００７２】
工程２Ａ−１０には、その時点の反復に対して、（１）その時点の反復の最良のパス［σ(i)best］、および（２）その時点の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパス［ρ(i)TB,best］を判定し保存することが含まれる。
【００７３】
工程２Ａ−１２では、出力されたパスは反復ｉまでの最良のＴａｉｌ−Ｂｉｔｉｎｇパス［ρ(i)TB,best］である。
【００７４】
工程２Ａ−１４には、最大反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパス［ρ(J)TB,best］が存在しているかを判定することが含まれる。
【００７５】
工程２Ａ−１５には工程２Ａ−１４の判定が肯定の場合に、最大反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパス［ρ(J)TB,best］を出力することが含まれ、工程２Ａ−１６には工程２Ａ−１４の判定が否定の場合に、最大反復の最良のパス［σ(J)best］を出力することが含まれる。
【００７６】
図２Ｂでは、特定の一例示的実施形態およびモードで実行される例示的工程またはステップを示している。図２Ｂの特定の例示的な実施形態およびモードでは、復号器／方法は、その時点の反復に対して、（１）その時点の反復が最大の反復で、最大の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合にのみ、その時点の反復の最良のパスを判定し、（２）その時点の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定し記録するように構成されている。図２Ｂの特定の例示的な実施形態およびモードは、ＷＡＶＡ１充足の実施形態／モードである。
【００７７】
基本的に一般的な図２の実施形態／モードの工程と同一の図２Ｂの実施形態／モードの工程には、対応する参照符号が付いている。図２Ｂで詳述する図２Ｂの実施形態／モードの工程には、工程番号に２Ｂという接頭語が付いており、工程２Ｂ−１０、工程２Ｂ−１２、および工程２Ｂ−１４から２Ｂ−１６までが含まれる。
【００７８】
工程２Ｂ−１０には、その時点の反復に対して、（１）その時点の反復が最大の反復で、最大の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパス［ρ(i)TB,best］が存在しない場合にのみ、その時点の反復の最良のパス［σ(i)best］を判定するか、または（２）その時点の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパス［ρ(i)TB,best］を判定し記録することが含まれる。
【００７９】
工程２Ｂ−１２では、出力されたパスは反復ｉまでの最良のＴａｉｌ−Ｂｉｔｉｎｇパス［ρ(i)TB,best］である。
【００８０】
工程２Ｂ−１４には、最大反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパス［ρ(J)TB,best］が存在しているかを判定することが含まれる。
【００８１】
工程２Ｂ−１５には工程２Ｂ−１４の判定が肯定の場合に、最大反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパス［ρ(J)TB,best］を出力することが含まれ、工程２Ｂ−１６には工程２Ａ−１４の判定が否定の場合に、最大反復の最良のパス［σ(J)best］を出力することが含まれる。
【００８２】
図２Ｃでは、特定の別の例示的実施形態およびモードで実行される例示的工程またはステップを示している。図２Ｃの特定の例示的な実施形態およびモードでは、復号器／方法が、その時点の反復に対して、その時点の反復の最良のパス［σ(i)best］、およびその時点の反復が最大の反復で、σ(J)bestがＴａｉｌ−Ｂｉｔｉｎｇパス［σ(J)TB,best］ではない場合にのみ、最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定するように構成されている。図２Ｃの特定の例示的な実施形態およびモードは、ＷＡＶＡ２シンプルの実施形態／モードである。基本的に一般的な図２の実施形態／モードの工程と同一の図２Ｃの実施形態／モードの工程には、対応する参照符号が付いている。図２Ｃで詳述する図２Ｃの実施形態／モードの工程には、工程番号に２Ｃという接頭語が付いており、工程２Ｃ−１０、工程２Ｃ−１２、および工程２Ｃ−１４から２Ｃ−１６までが含まれる。
【００８３】
工程２Ｃ−１０には、その時点の反復に対して、（１）その時点の反復の最良のパス［σ(i)best］、および（２）その時点の反復が最大の反復で、σ(J)bestが最大反復の完了時に（例えば、最後の反復）、Ｔａｉｌ−Ｂｉｔｉｎｇパス（ＴＢＰ）ではない場合にのみ、その時点の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパス［σ(i)TB,best］を判定することが含まれる。
【００８４】
工程２Ｃ−１２では、出力されたパスは反復ｉの間の最良のパス［σ(i)best］である。
【００８５】
工程２Ｃ−１４には、最大反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパス［σ(J)TB,best］が存在しているかを判定することが含まれる。
【００８６】
工程２Ｃ−１５には工程２Ｃ−１４の判定が肯定の場合に、最大反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパス［σ(J)TB,best］を出力することが含まれ、工程２Ｃ−１６には工程２Ｃ−１４の判定が否定の場合に、最大反復の最良のパス［σ(J)best］を出力することが含まれる。
【００８７】
図２Ｄでは、特定のさらに別の例示的実施形態およびモードで実行される例示的工程またはステップを示している。図２Ｄの特定の例示的な実施形態およびモードでは、復号器／方法は、その時点の反復に対して、（１）その時点の反復が最大の反復で、最大の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパス［σ(i)TB,best］が存在しない場合にのみ、その時点の反復の最良のパス［σ(i)best］を判定し保存するか、または（２）その時点の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパス［σ(i)TB,best］を判定し保存するように構成されている。 
図２Ｄの特定の例示的な実施形態およびモードは、ＷＡＶＡ２充足の実施形態／モードである。基本的に一般的な図２の実施形態／モードの工程と同一の図２Ｄの実施形態／モードの工程には、対応する参照符号が付いている。図２Ｄで詳述する図２Ｄの実施形態／モードの工程には、工程番号に２Ｄという接頭語が付いており、工程２Ｄ−１０、工程２Ｄ−１２、および工程２Ｄ−１４から２Ｄ−１６までが含まれる。
【００８８】
工程２Ｄ−１０には、その時点の反復に対して、（１）その時点の反復が最大反復で、最大反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパス［σ(i)TB,best］が存在しない場合にのみその時点の反復の最良のパス［σ(i)best］を判定し保存するか、または（２）その時点の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパス［σ(i)TB,best］を判定し保存することが含まれる。
【００８９】
工程２Ｄ−１２では、出力されたパスは反復ｉの最良のＴａｉｌ−Ｂｉｔｉｎｇパス、すなわちσ(i)TB,bestである。
【００９０】
工程２Ｄ−１４には、最大反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパス［σ(J)TB,best］が存在しているかを判定することが含まれる。
【００９１】
工程２Ｄ−１５には工程２Ｄ−１４の判定が肯定の場合に、最大反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパス［σ(J)TB,best］を出力することが含まれ、工程２Ｄ−１６には工程２Ｄ−１４の判定が否定の場合に、最大反復の最良のパス［σ(J)best］を出力することが含まれる。
【００９２】
復号器４０は、それらの用語が本明細書で広範囲化して定義されているように、プロセッサやコントローラの形を取ることができ、プロセッサやコントローラは復号器４０専用でも、ノードまたはデバイス２０の他の機能と復号器４０が共有するものでも可能であることを認識されたい。さらに一部の例示的な実施形態では、４０の復号化機能は、複数のプロセッサやコントローラ、例えば、複数のプロセッサやコントローラに分散したもので実現できる。
【００９３】
既存（従来）のＷＡＶＡアルゴリズムと、前項に一覧した４つなどの本明細書で提案したアルゴリズムは、表１にまとめられている。表１で、アルゴリズム（「Ａｌｇ．」）１はシンプル終了条件を伴うベースラインまたは従来のアルゴリズムで、アルゴリズムＡｌｇ．２およびアルゴリズムＡｌｇ．３と比較する必要がある。これはアルゴリズムＡｌｇ．２およびアルゴリズムＡｌｇ．３が本明細書で説明している技術の例示的な実施形態／モードを表しているからである。同様に、アルゴリズムＡｌｇ．４は充足終了条件を伴うベースラインまたは従来のアルゴリズムなので、アルゴリズムＡｌｇ．４はアルゴリズムＡｌｇ．５およびアルゴリズムＡｌｇ．６と比較する必要がある。それはアルゴリズムＡｌｇ．５およびアルゴリズムＡｌｇ．６が本明細書で説明している技術の例示的な実施形態／モードを表しているからである。
【００９４】
本技術には複数の利点がある。リンクレベルのシミュレーションが行われ、提案したアルゴリズムの利点が示されている。そこでは、ペイロードサイズ２４ビット（長さの短い符号と呼ばれる）または２４０ビット（長さの長い符号と呼ばれる）を伴う８０２．１６レート１／２ＴＢＣＣが使用されている。ＴＢＣＣの８進法の生成多項式は（５５４、７４４）で与えられ、メモリ長はｖ＝６である。復号化で許容されるサイクル（反復）の最大数は、ペイロードサイズが２４ビットの場合には、Ｉ＝３０で、ペイロードサイズが２４０ビットの場合にはＩ＝２０である。シミュレーションの試行数は、ＳＮＲポイントごとに２００００００である。技術の利点は表１にまとめられており、次で説明されている。
【００９５】
１．ＷＡＶＡ１とＷＡＶＡ２の両方で、シンプルまたは充足終了条件において、各復号化反復間のＷＡＶＡよりも複雑な計算およびメモリの使用量の必要性が少なくなっている。ＷＡＶＡの場合、その時点の反復までの最良のパスおよび最良のＴＢＰが見つけられ、記録される必要がある。ＷＡＶＡ１シンプルの場合、その時点の反復の最良のパスは必要とされるが、その時点の反復までの最良のパスを見つける必要はない。それでもなお、ＷＡＶＡ１シンプルの場合、その時点の反復までの最良のＴＢＰを見つけて記録する必要がある。ＷＡＶＡ１充足の場合、その時点の反復までの最良のＴＢＰを見つけて記録する必要がある。その時点の反復の最良のパスは、最大の反復Ｊまでの最良のＴＢＰが存在しない場合に、最大反復Ｊでのみ必要とされる。ＷＡＶＡ２充足の場合、その時点の反復の最良のＴＢＰと最良のパス（最良のＴＢＰが最大反復Ｊに存在しないに場合にのみ必要）が必要とされる。しかし、その時点の反復までの最良のパスと最良のＴＢＰを見つける必要はない。ＷＡＶＡ２シンプルの場合、その時点の反復の最良のＴＢＰおよび最良のパス（最良のＴＢＰが最大反復Ｊに存在しないに場合にのみ必要）が必要とされる。しかし、その時点の反復までの最良のパスおよび最良のＴＢＰを見つける必要はない。したがって、提案したアルゴリズムの中で、ＷＡＶＡ２はＷＡＶＡ１よりも複雑な計算およびメモリの使用量の必要性が少なくなる。
【００９６】
２．ＷＡＶＡ１とＷＡＶＡ２の両方の性能は、シンプルまたは充足終了条件のいずれの場合も、ほとんどＷＡＶＡと同じである。ＷＡＶＡ１シンプルとＷＡＶＡ１充足の場合、図３と図４からＦＥＲとＢＥＲで、長さの短い符号（ペイロード２４ビット）のＷＡＶＡからの損失がほとんどない。ＷＡＶＡ２シンプルとＷＡＶＡ２充足の場合、図３と図４からＦＥＲとＢＥＲで、長さの短い符号のＷＡＶＡに比べて損失は０．１ｄＢ以下のように思われる。長さの長い符号（ペイロード２４０ビット）の場合、図６と図７から、シンプルまたは充足終了条件のいずれであっても、ＷＡＶＡ１とＷＡＶＡ２の両方の性能はＷＡＶＡと同じように思われる。
【００９７】
ＷＡＶＡ１シンプルとＷＡＶＡ２シンプルの両方で、必要な復号化反復数はＷＡＶＡシンプルよりも少ない。ＷＡＶＡ２充足で必要な復号化反復数はＷＡＶＡ充足よりも少ないが、ＷＡＶＡ１充足で必要な復号化反復数はＷＡＶＡ充足と同じである。この結論は、長さの短い符号と長さの長い符号の両方で言えることであり、図５と図８で示されている。
【００９８】
上記説明には多くの特異性が含まれているが、これらは、本発明の範囲を限定するものとして解釈するべきではなく、むしろ、本発明の現在の好適な実施形態の一部の例示例を提供しているにすぎない。したがって、本発明の範囲には、当業者にとって明らかになる場合のある他の実施形態も完全に含まれることを認識されたい。当業者に知られている上述の好適な実施形態の構成部品と構造的、化学的、および機能的に同等なすべてのものは、参照によって本明細書に明示的に組み込まれる。さらに、デバイスまたは方法が、本明細書に含まれ、本発明で解決しようとするありとあらゆる問題に対処するのに必ずしも必要であるとは限らない。
【００９９】
2011501612.tif 000003
【０１００】
2011501612.tif 000004
【図１】
2011501612.tif 000005
【図２】
2011501612.tif 000006
【図２Ａ】
2011501612.tif 000007
【図２Ｂ】
2011501612.tif 000008
【図２Ｃ】
2011501612.tif 000009
【図２Ｄ】
2011501612.tif 000010
【図３】
2011501612.tif 000011
【図４】
2011501612.tif 000012
【図５】
2011501612.tif 000013
【図６】
2011501612.tif 000014
【図７】
2011501612.tif 000015
【図８】
2011501612.tif 000016
【手続補正書】
【提出日】平成21年8月13日(2009.8.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャを使用して、チャネル上で受信される入力符号化シーケンスで動作するよう構成された復号器（４０）であって、
前記復号器（４０）は、復号シーケンスとして選択したパスを出力するよう構成されており、
前記復号器（４０）が、異なるチャネル状態について、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャのその時点の反復に対して、その時点の反復までの最良のパスの保存を回避するように構成されていることを特徴とする復号器。
【請求項２】
前記復号器（４０）が、前記その時点の反復に対して（１）前記その時点の反復の最良のパスを判定し、（２）前記その時点の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定及び記録するように構成される、請求項１に記載の復号器（４０）。
【請求項３】
前記復号器（４０）が、前記その時点の反復に対して、（１）前記その時点の反復が最大の反復で、最大の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合にのみ、前記その時点の反復の最良のパスを判定し、（２）前記その時点の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定し記録するように構成される、請求項１に記載の復号器（４０）。
【請求項４】
前記復号器（４０）が、前記その時点の反復に対して、（１）前記その時点の反復が最大の反復で、最大の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合にのみ、前記その時点の反復の最良のパスを判定し、（２）前記その時点の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定するように構成される、請求項１に記載の復号器（４０）。
【請求項５】
前記復号器（４０）が、前記その時点の反復に対して、（１）前記その時点の反復の最良のパスを判定し、（２）前記その時点の反復が最大の反復で、最大の反復の最良のパスがＴａｉｌ−Ｂｉｔｉｎｇパスではない場合にのみ、前記その時点の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定するように構成される、請求項１に記載の復号器（４０）。
【請求項６】
復号化工程を実行する方法であって、
ビタビプロシージャの反復を実行することによって、チャネル上で受信される入力復号化シーケンスで動作するＷｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャを使用する工程を含み、
Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャの反復に対して、最良のパスおよび／または最良のＴａｉｌ−Ｂｉｔｉｎｇパスを見つけて保存するが、前記反復まで最良のパスを保存しないことを特徴とする方法。
【請求項７】
（１）ビタビプロシージャの最初の反復に対して、
（１．１）Ｍ個の開始状態を初期化する工程と、
（１．２）ビタビプロシージャを実行し、Ｍ個のサバイバーパスを見つける工程と、
（１．３）最初の反復の最良のパスを見つける工程と、
（１．４）最初の反復がＴａｉｌ−Ｂｉｔｉｎｇパスであることを判定し、そうであるならば、復号化シーケンスとして最初の反復の最良のパスを復号化および出力する工程と、
（２）反復カウンタを増分し、前記反復カウンタに対応するその時点の反復ｉに対して、
（２．１）反復ｉ−１からＭ個の最後の状態のメトリクスによってＭ個の開始状態メトリクスを初期化する工程と、
（２．２）ビタビプロシージャを実行し、Ｍ個のサバイバーパスを見つける工程と、
（２．３）反復ｉに対して前記その時点の反復ｉまでの最良のパスを保存することなく、反復ｉに対して検索および保存の工程を行う工程と、
（２．４）停止ルールを満たしているかを判定し、そうであるならば、復号化シーケンスとして保存したパスを出力する工程と、
（２．５）最大数の反復が実行されたことを判定し、そうでない場合には、工程（２）に戻る工程と、
（３）パスの存在確認を実行する工程と、
（４）復号化シーケンスとして保存したパスを出力する工程とをさらに含む、請求項６に記載の方法。
【請求項８】
工程（２．３）が、その時点の反復に対して、（１）その時点の反復の最良のパスを判定する工程と、（２）その時点の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定および記録する工程とを含み、
工程（２．４）では、前記保存されたパスが反復ｉまでの前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスであり、
工程（３）が前記最大の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在するかを判定する工程を含み、
工程（４）が、工程（３）の前記判定が肯定の場合に、前記最大の反復までの前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスを出力する工程を含み、
工程（４）が、工程（３）の前記判定が否定の場合に、前記最大の反復の前記最良のパスを出力する工程を含む、請求項７に記載の方法。
【請求項９】
工程（２．３）が、その時点の反復に対して、（１）その時点の反復が最大の反復で、前記最大の反復までの前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合にのみ、その時点の反復の最良のパスを判定する工程、または（２）その時点の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定および記録する工程を含み、
工程（２．４）では、前記保存されたパスが反復ｉまでの前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスであり、
工程（３）が前記最大の反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在するかを判定する工程を含み、
工程（４）が、工程（３）の前記判定が肯定の場合に、前記最大の反復までの前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスを出力する工程を含み、
工程（４）が、工程（３）の前記判定が否定の場合に、前記最大の反復の前記最良のパスを出力する工程を含む、請求項７に記載の方法。
【請求項１０】
工程（２．３）が、その時点の反復に対して、（１）その時点の反復が最大の反復で、その時点の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合にのみ、その時点の反復の最良のパスを判定するか、または（２）その時点の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定する工程を含み、
工程（２．４）では、前記保存されたパスが反復ｉの前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスであり、
工程（３）が前記最大の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在するかを判定する工程を含み、
工程（４）が、工程（３）の前記判定が肯定の場合に、前記最大の反復の前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスを出力する工程を含み、
工程（４）が、工程（３）の前記判定が否定の場合に、前記最大の反復の前記最良のパスを出力する工程を含む、請求項７に記載の方法。
【請求項１１】
工程（２．３）が、その時点の反復に対して、（１）その時点の反復の最良のパスを判定し、（２）その時点の反復が最大の反復で、前記最大の反復の前記最良のパスがＴａｉｌ−Ｂｉｔｉｎｇパスではない場合に、その時点の反復の最良のＴａｉｌ−Ｂｉｔｉｎｇパスを判定する工程を含み、
工程（２．４）では、前記保存されたパスが反復ｉの間の前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスであり、
工程（３）が前記最大の反復に最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在するかを判定する工程を含み、
工程（４）が、工程（３）の前記判定が肯定の場合に、前記最大の反復の前記最良のＴａｉｌ−Ｂｉｔｉｎｇパスを出力する工程を含み、
工程（４）が、工程（３）の前記判定が否定の場合に、前記最大の反復の前記最良のパスを出力する工程を含む、請求項７に記載の方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
本発明の一態様において、本明細書で説明している技術は、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャを使用した入力符号化シーケンスで動作するように構成された復号器、およびその復号器が採用する復号化方法に関するものである。復号器／方法は、復号シーケンスとして選択したパスを出力し、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャであるその時点の反復の場合には、その時点の反復までの最良のパスの保存を回避するように構成されている。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００５３
【補正方法】変更
【補正の内容】
【００５３】
例示的な各種実施形態およびモードで、復号器４０は、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャを使用した入力符号化シーケンスで動作するよう構成されている。復号器４０は、復号シーケンスとして選択したパスを出力し、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャであるその時点の反復の場合には、その時点の反復までの最良のパスの保存を回避するように構成されている。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００６３
【補正方法】変更
【補正の内容】
【００６３】
ＷＡＶＡ２モードなどの他のモードでは、工程２−１０で見つかる最良のパス［σ(i)best］が反復ｉの最良のパスで、最良のＴａｉｌ−Ｂｉｔｉｎｇパスは反復ｉの最良のＴａｉｌ−Ｂｉｔｉｎｇパス［σ(i)TB,best］である。ＷＡＶＡ２モードの一部のバージョンでは、その時点の反復が最大反復で、最大反復までの最良のＴａｉｌ−Ｂｉｔｉｎｇパスが存在しない場合にのみ、その時点の反復の最良のパスが判定され保存される。工程２−１０は、Ｗｒａｐ  Ａｒｏｕｎｄ  Ｖｉｔｅｒｂｉプロシージャのその時点の反復に対して、その時点の反復までの最良のパス（例えば、その時点の反復の前に見つかる任意の最良のパス）の保存を回避するように実行される。
【手続補正５】
【補正対象書類名】図面
【補正対象項目名】図１
【補正方法】変更
【補正の内容】
【図１】
2011501612.tif 000017
【手続補正６】
【補正対象書類名】図面
【補正対象項目名】図２
【補正方法】変更
【補正の内容】
【図２】
2011501612.tif 000018
【手続補正７】
【補正対象書類名】図面
【補正対象項目名】図２Ａ
【補正方法】変更
【補正の内容】
【図２Ａ】
2011501612.tif 000019
【手続補正８】
【補正対象書類名】図面
【補正対象項目名】図２Ｂ
【補正方法】変更
【補正の内容】
【図２Ｂ】
2011501612.tif 000020
【手続補正９】
【補正対象書類名】図面
【補正対象項目名】図２Ｃ
【補正方法】変更
【補正の内容】
【図２Ｃ】
2011501612.tif 000021
【手続補正１０】
【補正対象書類名】図面
【補正対象項目名】図２Ｄ
【補正方法】変更
【補正の内容】
【図２Ｄ】
2011501612.tif 000022
【国際調査報告】
2011501612.tif 000023