(57)【要約】      （修正有）【課題】改善された性能を提供する、ジグザグ符号のための符号器と復号器を提供する。【解決手段】符号器１００は、今次のセグメントの冗長ビットを計算するジグザグ符号器１２０をさらに備え、今次のセグメントの冗長ビットを計算するときには、前記順序における前のセグメントの冗長ビットを使用する。符号器１００は、インターリービング規則を用いて複数のセグメントのビットをインターリーブし、インターリーブバージョンを得るインターリーバ１３０と、入力符号語またはそのインターリーブバージョン、およびインターリーブバージョンによって供給され、ジグザグ符号器１２０によって生成される１組の冗長ビットを用いて出力符号語を構築する、出力符号語コンストラクタ１４０とを備える。【選択図】図１
2008154229.tif 000002
【特許請求の範囲】
【請求項１】
出力符号語より少ないビット数を有する入力情報語に基づいて前記出力符号語を生成する符号器（１００）であって、
前記入力情報語を、いくつかのビットを有する複数の順序付けされたセグメントにセグメント化するセグメンタ（１１０）と、
今次のセグメントの冗長ビットを計算するジグザグ符号器（１２０）であって、前記今次のセグメントの前記冗長ビットを計算するときに、前記順序における前のセグメントの冗長ビットを使用する前記ジグザグ符号器（１２０）と、
インターリービング規則を用いて前記複数のセグメントの前記ビットをインターリーブし、インターリーブバージョンを得るインターリーバ（１３０）と、
前記入力符号語または前記入力符号語の前記インターリーブバージョンと、前記インターリーブバージョンによって供給され、前記ジグザグ符号器（１２０）によって生成される１組の冗長ビットとを用いて、前記出力符号語を構築する出力符号語コンストラクタ（１４０）と
を備え、前記インターリーバ（１３０）は、同じセグメント内の前記入力情報語の前記入力情報語ビットの全セグメントの少なくとも５０％が、前記インターリーブバージョンの少なくとも１つの異なるセグメントに再配置されるような前記インターリービング規則を使用するようにされており、前記インターリービング規則は、さらに、前記インターリーブバージョンからの既定の領域内のランダムな位置を、前記入力情報語の位置に割り当てることに基づいており、前記既定の領域をさらにインターリーブするためのものである、符号器（１００）。
【請求項２】
前記出力符号語コンストラクタ（１４０）が、前記入力符号語によって供給され、前記ジグザグ符号器（１２０）によって生成される冗長ビットを用いて、前記出力符号語を構築するようにさらにされており、または、前記インターリーバ（１３０）が、別のインターリービング規則を用いて前記複数のセグメントの前記情報ビットの別のインターリーブバージョンを得るようにさらにされており、前記出力符号語コンストラクタ（１４０）が、前記別のインターリーブバージョンによって供給され、前記ジグザグ符号器（１２０）によって生成される冗長ビットを用いて、前記出力符号語を構築するようにさらにされている、請求項１に記載の符号器（１００）。
【請求項３】
前記インターリーバ（１３０）は、前記入力情報語の前記同じセグメント内に位置する２つのビットが、前記インターリーブバージョン内の別々のセグメントに再配置されるような前記インターリービング規則を使用するようにされている、請求項１または２の一項に記載の符号器（１００）。
【請求項４】
前記インターリーバ（１３０）は、前記入力符号語の隣接するセグメント内に位置する２つのビットが、前記インターリーブバージョン内で少なくとも２セグメント離されるような前記インターリービング規則を使用するようにされている、請求項１から３の一項に記載の符号器（１００）。
【請求項５】
前記インターリーバ（１３０）が、２つの入力情報語の２つのインターリーブバージョンと、前記２つのインターリーブバージョンによって供給され、前記ジグザグ符号器（１２０）によって生成される２組の冗長ビットとを用いて、２つの出力符号語が構築されるような前記インターリービング規則を使用し、前記入力情報語より大きいハミング重みを有するようにされている、請求項１から４の一項に記載の符号器（１００）。
【請求項６】
出力符号語が、２より大きいハミング重みを有する、請求項５に記載の符号器（１００）。
【請求項７】
前記インターリーバ（１３０）が、前記入力情報語内のビットの前記位置に、前記インターリーブバージョン内の、以前に割り当てられているビットの位置まである一定の距離を有する前記既定の領域からの前記ランダムな位置を割り当てるサブステップを備える、前記インターリービング規則を使用するようにされている、請求項１から６の一項に記載の符号器（１００）。
【請求項８】
前記既定の領域が、前記インターリーブバージョン内にある位置のうち、以前に割り当てられて配置されているブロック済み領域か、または、あるセグメントから以前に割り当てられた位置までにある一定の距離となるような設けるブロック済領域を除く全ての位置から決定される、請求項７に記載の符号器（１００）。
【請求項９】
前記インターリーバ（１３０）が、前記インターリービング規則と前記別のインターリービング規則とに基づいて少なくとも２つのインターリーブバージョンを提供するようにされており、前記第１のインターリービング規則が、前記入力情報語からの前記ビットの少なくとも１０％の位置が、前記別のインターリーブバージョンにおいて、前記インターリーブバージョン内で割り当てられている前記位置とは異なる位置に割り当てられるような規則である、請求項２から８の一項に記載の符号器（１００）。
【請求項１０】
前記インターリーバ（１３０）が、前記インターリーブバージョンをインターリーブすることによって前記別のインターリーブバージョンを得るようにされている、請求項２から９の一項に記載の符号器（１００）。
【請求項１１】
出力符号語より少ないビット数を有する入力情報語に基づいて前記出力符号語を生成する方法であって、
前記入力情報語を、いくつかのビットを有する複数の順序付けされたセグメントにセグメント化するステップと、
今次のセグメントの冗長ビットを計算するステップであり、前記今次のセグメントの前記冗長ビットを計算するときに、前記順序における前のセグメントの冗長ビットを使用する前記ステップと、
インターリービング規則を用いて前記複数のセグメントの前記ビットをインターリーブし、インターリーブバージョンを得るステップと、
前記入力符号語または前記入力符号語の前記インターリーブバージョンと、前記インターリーブバージョンから計算される１組の冗長ビットとを用いて、前記出力符号語を構築するステップと、
を備え、前記インターリーブするステップが、同じセグメント内の前記入力情報語の前記入力情報語ビットの全セグメントの少なくとも５０％が、前記インターリーブバージョンの少なくとも１つの異なるセグメントに再配置されるような前記インターリービング規則を使用し、前記インターリービング規則が、さらに、前記インターリーブバージョンからの既定の領域内のランダムな位置を、前記入力情報語の位置に割り当てることに基づいており、前記既定の領域をさらにインターリーブするためのものである、方法。
【請求項１２】
コンピュータ上で実行されると請求項１４に記載の方法を実行するプログラムコードを備える、コンピュータプログラム。
【請求項１３】
入力符号語を復号化し、前記入力符号語より少ないビット数を有する出力情報語を生成する復号器（３００）であって、
前記入力符号語を、いくつかの情報ビットと冗長ビットを有する複数の順序付けされたセグメントにセグメント化するセグメンタ（３１０）と、
インターリービング規則を用いて前記複数のセグメントの前記情報ビットをインターリーブし、前記情報ビットの第１のインターリーブバージョンを得るインターリーバ（３２０）であり、同じセグメント内の前記情報語の前記入力情報語ビットの全セグメントの少なくとも５０％が、前記インターリーブバージョンの少なくとも１つの異なるセグメントに再配置されるような前記インターリービング規則を使用するようにされている、前記インターリーバ（３２０）と、
前記情報ビットと、前記情報ビットの前記インターリーブバージョンと前記冗長ビットとに基づいて、前記出力情報語を計算するジグザグ復号器（３３０）と、
を備え、前記インターリービング規則が、さらに、前記インターリーブバージョンからの既定の領域内のランダムな位置を、前記入力情報語の位置に割り当てることに基づいており、前記既定の領域をさらにインターリーブするためのものである、復号器（３００）。
【請求項１４】
入力符号語を復号化し、前記入力符号語より少ないビット数を有する出力情報語を生成する方法であって、
前記入力符号語を、いくつかの情報ビットと冗長ビットを有する複数の順序付けされたセグメントにセグメント化するステップと、
インターリービング規則を用いて前記複数のセグメントの前記情報ビットをインターリーブし、前記情報ビットのインターリーブバージョンを得るステップであり、同じセグメント内の前記入力情報語の前記入力情報語ビットの全セグメントの少なくとも５０％が、前記インターリーブバージョンの少なくとも１つの異なるセグメントに再配置されるような前記インターリービング規則を使用するようにされている、前記インターリーブするステップと、
前記情報ビットと、前記情報ビットの前記インターリーブバージョンと前記冗長ビットとに基づいて、前記出力情報語を計算するステップと、
を備え、前記インターリービング規則が、さらに、前記インターリーブバージョンからの既定の領域内のランダムな位置を、前記入力情報語の位置に割り当てることに基づいており、前記既定の領域をさらにインターリーブするためのものである、方法。
【請求項１５】
コンピュータ上で実行されると請求項１４に記載の方法を実行するプログラムコードを備える、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、国際標準化団体によって規定されるＷＣＤＭＡ（広帯域符号分割多元接続）やＯＦＤＭＡ（直交周波数分割多元接続）に基づくネットワークなどの通信ネットワークの分野に関し、ＵＭＴＳのような現在の通信システムとＬＴＥのような将来の通信システムにおける導入候補の誤り制御符号化を機能強化するための、ジグザグ符号（zigzag code）および連結（concatenated）ジグザグ符号を考察する。
【背景技術】
【０００２】
連結ジグザグ符号は、比較的少ない符号化および復号化の計算量を有しながらも優れた性能を提供するため、魅力的な符号化方式である。データシーケンスのインターリーブバージョンを符号化している複数の構成要素ジグザグ符号(constituent zigzag code)を並列連結すること（parallel concatenation）によって、強力な符号が得られる。これは、インターリーバ設計に新たな問題が生ずることを示唆する。すなわち、イタレーションによる復号化（iterative coding）のために最適化されているインターリーバが、１つのみならず複数必要となるのである。これらのインターリーバは、それぞれ、できる限り相互に独立でありながらも、イタレーションによる復号化に良好な性能を提供する必要がある。
【０００３】
ジグザグ符号は、Ｌ．Ｐｉｎｇ，Ｘ．Ｈｕａｎｇ，ａｎｄ  Ｎ．Ｐｈａｍｄｏ，「Ｚｉｇｚａｇ  ｃｏｄｅｓ  ａｎｄ  ｃｏｎｃａｔｅｎａｔｅｄ  ｚｉｇｚａｇ  ｃｏｄｅｓ」，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．４７，ｐｐ．８００−８０７，Ｆｅｂｒｕａｒｙ  ２００１において提案されており、Ｓ．−Ｎ．Ｈｏｎｇ  ａｎｄ  Ｄ．−Ｊ．Ｓｈｉｎ，「Ｃｏｎｓｔｒｕｃｔｉｏｎ  ａｎｄ  ａｎａｌｙｓｉｓ  ｏｆ  ｒａｔｅ  ｃｏｍｐａｔｉｂｌｅ  ｐｕｎｃｔｕｒｅｄ  ｃｏｎｃａｔｅｎａｔｅｄ  ｚｉｇｚａｇ  ｃｏｄｅｓ」，ｉｎ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ（ＩＳＩＴ），ｐｐ．８４０−８４４，ＩＥＥＥ，Ｓｅｐｔｅｍｂｅｒ  ２００５、Ｓ．−Ｎ．Ｈｏｎｇ  ａｎｄ  Ｄ．−Ｊ．Ｓｈｉｎ，「Ｏｐｔｉｍａｌ  ｒａｔｅ−ｃｏｍｐａｔｉｂｌｅ  ｐｕｎｃｔｕｒｅｄ  ｃｏｎｃａｔｅｎａｔｅｄ  ｚｉｇｚａｇ  ｃｏｄｅｓ」，ｉｎ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ（ＩＣＣ），ｐｐ．６２７−６３１，ＩＥＥＥ，Ｍａｙ  ２００５、Ｓ．−Ｎ．Ｈｏｎｇ  ａｎｄ  Ｄ．−Ｊ．Ｓｈｉｎ，「Ｄｅｓｉｇｎ  ｏｆ  ｉｒｒｅｇｕｌａｒ  ｃｏｎｃａｔｅｎａｔｅｄ  ｚｉｇｚａｇ  ｃｏｄｅｓ」，ｉｎ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ（ＩＳＩＴ），ｐｐ．１３６３−１３６６，ＩＥＥＥ，Ｓｅｐｔｅｍｂｅｒ  ２００５、Ｌ．Ｐｉｎｇ，Ｓ．Ｃｈａｎ，ａｎｄ  Ｋ．Ｙｅｕｎｇ，「Ｉｔｅｒａｔｉｖｅ  ｄｅｃｏｄｉｎｇ  ｏｆ  ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ  ｃｏｎｃａｔｅｎａｔｅｄ  ｓｉｎｇｌｅ  ｐａｒｉｔｙ  ｃｈｅｃｋ  ｃｏｄｅｓ」，ｉｎ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ（ＩＣＣ），ｐｐ．１３１−１３５，ＩＥＥＥ，Ｊｕｎｅ  １９９８、Ｘ．Ｗｕ，Ｙ．Ｘｕｅ，ａｎｄ  Ｈ．Ｘｉａｎｇ，「Ｏｎ  ｃｏｎｃａｔｅｎａｔｅｄ  ｚｉｇｚａｇ  ｃｏｄｅｓ  ａｎｄ  ｔｈｅｉｒ  ｄｅｃｏｄｉｎｇ  ｓｃｈｅｍｅｓ」，ＩＥＥＥ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｌｅｔｔｅｒｓ，ｖｏｌ．８，ｐｐ．５４−５６，Ｊａｎｕａｒｙ  ２００４、Ｎ．Ｎｅｆｅｄｏｖ，「Ｍｕｌｔｉ−ｄｉｍｅｎｓｉｏｎａｌ  ｚｉｇｚａｇ  ｃｏｄｅｓ  ｆｏｒ  ｈｉｇｈ  ｄａｔａ  ｒａｔｅ  ｔｒａｎｓｍｉｓｓｉｏｎ」，ｉｎ  ３ｒｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｕｒｂｏ  Ｃｏｄｅｓ  ａｎｄ  Ｒｅｌａｔｅｄ  Ｔｏｐｉｃｓ，ｐｐ．２１５−２１８，Ｓｅｐｔｅｍｂｅｒ  ２００３、Ｎ．Ｎｅｆｅｄｏｖ，ｄａｔａ  ｒａｔｅ  ｔｒａｎｓｍｉｓｓｉｏｎ」，ｉｎ  １４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｐｅｒｓｏｎａｌ，Ｉｎｄｏｏｒ  ａｎｄ  Ｍｏｂｉｌｅ  Ｒａｄｉｏ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，ｐｐ．１８６８−１８７２，Ｓｅｐｔｅｍｂｅｒ  ２００３において拡張されている。
【０００４】
ジグザグ符号が魅力的なのは、これらの符号化および復号化の計算量が少なく、特に大きい符号化率における性能が優れているからである。イタレーションによる復号化を伴う連結ジグザグ符号は、著しく少ない計算量でありながら、並列連結畳み込み符号（ターボ符号）より約０．５ｄＢ機能が劣るだけである。単一のジグザグ符号は、その最小ハミング距離ｄmin＝２が小さいため、非常に弱い符号である。強い符号は、各構成要素符号がデータシーケンスのインターリーブバージョンを符号化しているジグザグ符号の連結によって得られる。ジグザグ符号は、普通、比較的大きい符号化率を有するため、適切な符号化率と誤り訂正機能を有する符号を得るには、複数のジグザグ符号が連結される必要がある。複数の構成要素符号の連結により小さい符号化率の符号を構成することが、普通はただ２つの構成要素符号が連結されているターボ符号との違いである。
【０００５】
これは、インターリーバ設計に新たな問題が生じることを示唆する。すなわち、イタレーションを用いる復号化（iterative decoding）のために最適化されているインターリーバが、１つのみならず複数必要となるのである。これらのインターリーバは、それぞれ、できる限り相互に独立でありながらも、望ましいイタレーションによる復号化性能を提供する必要がある。複数のインターリーバの相互独立性についての適切な基準は、依然として未解決の問題である。同時に、インターリーバは、構成要素復号器の外部情報がほとんど無相関になるようなランダム性を導入するものである。
【０００６】
ジグザグ符号が魅力的なのは、これらの符号化および復号化の計算量が少なく、特に大きい符号化率の際の性能が優れているからである。連結ジグザグ符号は、著しく少ない計算量でありながら、並列連結畳み込み符号（ターボ符号）より約０．５ｄＢ機能が劣るだけである。通常のジグザグ符号の原理が図２８に示されている。図中、
【数１】
2008154229.tif 000003
は、モジュロ２加算を表す。データビットｄi,j∈｛０，１｝はＩ×Ｊの行列に配列されている。行列の各行を、ジグザグ符号のセグメントという。パリティビットｐiは、前のパリティビットｐi-1を含む各セグメントｉにわたるモジュロ２加算として求められる。ジグザグ符号は、２つのパラメータＩとＪによって完全に記述される。
【０００７】
ジグザグ符号の等価の符号器は、図２９に示すようなメモリ１を備えるパンクチャド再帰的畳み込み符号器（punctured recursive convolutional encoder）である。パリティビットのパンクチャリングパターンは、トレリス符号器のＪ番目ごとのパリティビットだけが送信されるように選択される。単一のジグザグ符号は、最小ハミング距離がｄmin＝２であるため弱い性能(weak performance)を有する。これは、セグメントｉ内の２つのデータビットが反転されるときに容易に検証される。
【０００８】
この場合、パリティビットｐiは変化せず、したがって、符号語内の他のどのビットも影響を受けない。最小ハミング重みｗH＝ｄmin＝２を有する符号語が生成するのは、データシーケンスが、図３０に示すように同じセグメント内に位置する値ｄi,j＝１を有する２つのビットだけを含む場合である。ハミング重みｗH＝３である重みの小さい符号語は、図３１に示すように、値１を有する単一ビットが２つの連続するセグメントに出現する場合に生成される。強力な符号を作るためには、いくつかの構成要素ジグザグ符号が連結される必要がある。個々の構成要素符号器が、それぞれ、図３２に示すようにデータビットのインターリーブシーケンスを符号化する。ここで、図３２でΠkは、インターリーバｋの置換規則を表す。ジグザグ符号の符号化率Ｒc＝Ｊ／（Ｊ＋１）は、普通、比較的大きい値をとるため、いくつかのジグザグ符号が連結される必要がある。
【０００９】
図３３に、その性能を信号対雑音比に対するビット誤り率によって図示する。イタレーションによる復号化手法の典型的なインターリーバの設計基準は、図３３に示すグラフから導出することができる。イタレーションによる復号化での望ましい性能は、グラフに示されるインターリービング規則によって適切なランダム化が実行された場合に得ることができる。適切なランダム化は、ビット誤り率グラフの急な傾斜に対応している。別の設計基準は、ケースパターンが最悪となることを回避することである。というのは、最悪のケースパターンは、やはり図３３に示されている、ビット誤り率グラフのやや緩やかな傾斜とエラーフロアを生じるからである。
【００１０】
連結構成要素符号では、パリティビットだけが送信される。Ｋ個の構成要素符号を用いる場合、全体の符号化率は、Ｒc＝Ｊ／（Ｊ＋Ｋ）になる。複数のインターリーバを使用することが、普通はただ２つの構成要素符号だけが連結されるターボ符号との本質的な違いである。これは、インターリーバ設計における新たな問題を示唆する。すなわち、イタレーションによる復号化のために最適化されているインターリーバが、１つのみならず複数必要となるのである。これらのインターリーバは、それぞれ、できる限り相互に独立でありながらも、望ましいイタレーションによる復号化性能を提供する必要がある。複数のインターリーバの相互独立性の適切な基準は、依然として未解決の問題である。１つの直観的条件は、符号全体の最小ハミング距離を増大させるために、インターリービングが、ある構成要素符号器の入力のところの１セグメント内のビットが、他の任意の構成要素符号器の入力のところの同じまたは隣接するセグメントにマップされないようにすることである。この問題は、例えば、図３０に示されている。ジグザグ構成要素符号の出力のところの最小ハミング重みｗH＝ｄmin＝２を有する符号語が、データシーケンスによって生成され、値ｄi,j＝１の２つのビットが同じセグメントｉ内に位置している。符号全体の最小ハミング距離を増大させるために、インターリーバは、これらのデータシーケンスが、その他の構成要素符号器の出力のところでより大きなハミング重みを有する符号語を生成するようにする必要がある。したがって、これら２つの値１のビットは、図３０の右側に示すように、できる限り遠くに分散されている必要がある。
【００１１】
図２９の図には、ジグザグ符号が、Ｌ．Ｂａｈｌ，Ｊ．Ｃｏｃｋｅ，Ｆ．Ｊｅｌｉｎｅｋ，ａｎｄ  Ｊ．Ｒａｖｉｖ，「Ｏｐｔｉｍａｌ  ｄｅｃｏｄｉｎｇ  ｏｆ  ｌｉｎｅａｒ  ｃｏｄｅｓ  ｆｏｒ  ｍｉｎｉｍｉｚｉｎｇ  ｓｙｍｂｏｌ  ｅｒｒｏｒ  ｒａｔｅ」，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．ＩＴ−２０，ｐｐ．２８４−２８７，Ｍａｒｃｈ  １９７４に記載されているＢＣＪＲアルゴリズムのような、トレリスベースのアルゴリズムによって復号化され得ることが示唆されている。復号器の入力において、後方再帰（backward recursion）の初期設定のために、パンクチャドビットの位置にゼロが挿入される必要があり、ジグザグ符号器は、所定の状態では終了されるわけではないため、トレリスのすべての終了状態が等しく起こり得るものと仮定される。しかしながら、各セグメントの分割が、前方再帰（forward recursion）と後方再帰も実行する、ＭＬＡアルゴリズムと呼ばれる複雑さの著しく小さいアルゴリズムを使ったジグザグ符号の復号化を可能にする。Ｌ．Ｐｉｎｇ，Ｘ．Ｈｕａｎｇ，ａｎｄ  Ｎ．Ｐｈａｍｄｏ，「Ｚｉｇｚａｇ  ｃｏｄｅｓ  ａｎｄ  ｃｏｎｃａｔｅｎａｔｅｄ  ｚｉｇｚａｇ  ｃｏｄｅｓ」，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．４７，ｐｐ．８００−８０７，Ｆｅｂｒｕａｒｙ  ２００１に記載されているＭＬＡアルゴリズムの簡易バージョンは、符号語に対して一定のＳＮＲを有するＡＷＧＮチャネルについてのみ機能する。文献には、時間で変化するチャネルにおいて、より高次の変調でも機能する、対数尤度比に基づくより一般的な記述が示されている。データとパリティビットの変調シンボルからの逆マップ後の、雑音のある受け取り値が、それぞれ、ｄi,jとｐiで表わされる。まず、チャネル統計と送信シンボルアルファベットに基づき、受け取り符号ビットのチャネル情報対数尤度（channel information log-likelihood ratios）比を、以下のように算出する。
【数２】
2008154229.tif 000004
次に、おそらく利用可能な、データビットに関する事前情報（a-priori information）
【数３】
2008154229.tif 000005
を考慮に入れ、これをチャネル情報に加算する。
【数４】
2008154229.tif 000006
【００１２】
次に、パリティビットの前方メトリック（forward metric）を、次式に従って算出することができる。
【数５】
2008154229.tif 000007
式中、
【数６】
2008154229.tif 000008
は、ボックスプラス加算を表す。ボックスプラス加算は、Ｊ．Ｈａｇｅｎａｕｅｒ，Ｅ．Ｏｆｆｅｒ，ａｎｄ  Ｌ．Ｐａｐｋｅ，「Ｉｔｅｒａｔｉｖｅ  ｄｅｃｏｄｉｎｇ  ｏｆ  ｂｉｎａｒｙ  ｂｌｏｃｋ  ａｎｄ  ｃｏｎｖｏｌｕｔｉｏｎａｌ  ｃｏｄｅｓ」，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．ＩＴ−４２，ｐｐ．４２５−４２９，Ｍａｒｃｈ  １９９６によって示されている、個々のビットのモジュロ２加算に対応する、対数尤度比を用いた演算である。すなわち次式で示される。
【数７】
2008154229.tif 000009
【００１３】
ボックスプラス加算の正確な式は、Ｊ．Ｈａｇｅｎａｕｅｒ，Ｅ．Ｏｆｆｅｒ，ａｎｄ  Ｌ．Ｐａｐｋｅ，「Ｉｔｅｒａｔｉｖｅ  ｄｅｃｏｄｉｎｇ  ｏｆ  ｂｉｎａｒｙ  ｂｌｏｃｋ  ａｎｄ  ｃｏｎｖｏｌｕｔｉｏｎａｌ  ｃｏｄｅｓ」，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．ＩＴ−４２，ｐｐ．４２５−４２９，Ｍａｒｃｈ  １９９６に、以下のように記載されている。
【数８】
2008154229.tif 000010
【００１４】
これは、以下のように近似することができる。
【数９】
2008154229.tif 000011
【００１５】
式（６）の第１項は、パリティビットｐiの直接チャネル情報に事前情報を加えたものであり、第２項は、外部情報（extrinsic information）、すなわち、符号制約条件（code constraints）により符号語内のすべての前のビットから得られ得るｐiに関する情報である。同様に、後方再帰は以下のように算出され得る。
【数１０】
2008154229.tif 000012
【００１６】
次いで、ＡＰＰ対数尤度比が、以下のようにして得られる。
【数１１】
2008154229.tif 000013
【数１２】
2008154229.tif 000014
【００１７】
式（１２）の第１項は、ビットｄi,jに関する直接チャネル情報に事前情報を加えたものであり、その他の項は、外部情報、すなわち、符号制約条件により符号語内の他のすべてのビットから得られ得るｄi,jに関する情報である。連結ジグザグ符号は、構成要素符号が、その他の構成要素復号器の外部情報を追加事前情報として考慮に入れて順番に復号化される、図３４に示すようなイタレーションによるターボアルゴリズムによって復号化することができる。簡潔にするために図３４にはインターリーバが示されていない。各構成要素復号器ｌは、それぞれ、データビットとパリティビットの受け取りチャネル情報Ｌc（ｄi,j）とＬc（ｐl,i）、ならびに追加事前情報Ｌa,l（ｄi,j）としてのその他の構成要素復号器からの外部情報Ｌe,k（ｄi,j）を使用する。構成要素復号器ｌの外部情報は、以下の出力と入力の対数尤度比の差によって定義される。
【数１３】
2008154229.tif 000015
イタレーションｎにおいて、事前情報は、現在のイタレーションｎですでに復号化された構成要素復号器ｋ＝１，・・・，ｌ−１から得られる外部情報と、前のイタレーションｎ−１で得られた復号器ｋ＝ｌ＋１，・・・，Ｋからの外部情報からなる。
【００１８】
複数のジグザグ構成要素符号を連結するには、Ｋ−１の異なるインターリーバが必要である。一般に、複数のインターリーバは、ランダムに生成され得る。しかしながら、適切な相互の特性を有するインターリーバが生成されることが保証され得ないことのほかにも、Ｋ−１の置換パターンのそれぞれを格納する必要があるため、所要メモリ量の観点で大きな実際上の問題が生じる。しかも、システムは、様々なブロック長のサポートも必要とし得る。この場合、可能な各ブロック長ごとにＫインターリーバパターンを格納する必要がある。したがって、単純な式から、または共通のマザーインターリーバに関する単純な演算によって、複数のインターリーバを生成することが望ましい。
【００１９】
複数のインターリーバのためのメモリを節約する問題は、ジグザグ符号の状況において、Ｎ．Ｎｅｆｅｄｏｖ，「Ｍｕｌｔｉ−ｄｉｍｅｎｓｉｏｎａｌ  ｚｉｇｚａｇ  ｃｏｄｅｓ  ｆｏｒ  ｈｉｇｈ  ｄａｔａ  ｒａｔｅ  ｔｒａｎｓｍｉｓｓｉｏｎ」，ｉｎ  ３ｒｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｕｒｂｏ  Ｃｏｄｅｓ  ａｎｄ  Ｒｅｌａｔｅｄ  Ｔｏｐｉｃｓ，ｐｐ．２１５−２１８，Ｓｅｐｔｅｍｂｅｒ  ２００３と、Ｎ．Ｎｅｆｅｄｏｖ，「Ｅｖａｌｕａｔｉｏｎ  ｏｆ  ｌｏｗ  ｃｏｍｐｌｅｘｉｔｙ  ｃｏｎｃａｔｅｎａｔｅｄ  ｃｏｄｅｓ  ｆｏｒ  ｈｉｇｈ  ｄａｔａ  ｒａｔｅ  ｔｒａｎｓｍｉｓｓｉｏｎ」，ｉｎ  １４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｐｅｒｓｏｎａｌ，Ｉｎｄｏｏｒ  ａｎｄ  Ｍｏｂｉｌｅ  Ｒａｄｉｏ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，ｐｐ．１８６８−１８７２，Ｓｅｐｔｅｍｂｅｒ  ２００３で対処されている。
【００２０】
これらの文献では、データビットを立方体に配列し、この立方体を通る様々な方向にジグザグ符号化を行うことによって多次元ジグザグ符号を作ることが提案されている。しかしながら、これによって、設計空間が制限され、特に、構成要素ジグザグ符号のパラメータＪが固定され、異なることがある。
【００２１】
Ｎ．Ｎｅｆｅｄｏｖ，「Ｅｖａｌｕａｔｉｏｎ  ｏｆ  ｌｏｗ  ｃｏｍｐｌｅｘｉｔｙ  ｃｏｎｃａｔｅｎａｔｅｄ  ｃｏｄｅｓ  ｆｏｒ  ｈｉｇｈ  ｄａｔａ  ｒａｔｅ  ｔｒａｎｓｍｉｓｓｉｏｎ」，ｉｎ  １４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｐｅｒｓｏｎａｌ，Ｉｎｄｏｏｒ  ａｎｄ  Ｍｏｂｉｌｅ  Ｒａｄｉｏ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，ｐｐ．１８６８−１８７２，Ｓｅｐｔｅｍｂｅｒ  ２００３には、ジグザグ符号と、同じフレームワーク内のＵＭＴＳに指定された並列連結畳み込み符号の使用を可能にする提案が示されている。インターリービングに関する限り、著者は、ＵＭＴＳターボ符号に指定されたインターリーバと、第３の連結構成要素ジグザグ符号のインターリーバとしてのこれの転置を使用するよう提案している。この方式は非常に単純ではあるが、２つのインターリーバだけに限定されている。Ｎ．Ｎｅｆｅｄｏｖは、さらに、インターリーバのアドレスを交換することによって、ＵＭＴＳインターリーバから追加のインターリーバを生み出すことも提案している。しかしながら、これがどのようになされるべきかの情報は示していない。
【００２２】
多重のインターリーバ（multiple interleaver）の設計に関する論文は、ごくわずかしか存在せず、適切な設計基準は、依然として未解決の問題である。
【００２３】
複数のインターリーバは、符号分割多元接続（ＣＤＭＡ）におけるマルチユーザ検出の状況で、Ａ．Ｔａｒａｂｌｅ，Ｇ．Ｍｏｎｔｏｒｓｉ，ａｎｄ  Ｓ．Ｂｅｎｅｄｅｔｔｏ，「Ａｎａｌｙｓｉｓ  ａｎｄ  ｄｅｓｉｇｎ  ｏｆ  ｉｎｔｅｒｌｅａｖｅｒｓ  ｆｏｒ  ｉｔｅｒａｔｉｖｅ  ｍｕｌｔｉ−ｕｓｅｒ  ｒｅｃｅｉｖｅｒｓ  ｉｎ  ｃｏｄｅｄ  ＣＤＭＡ  ｓｙｓｔｅｍｓ」，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．５１，ｐｐ．１６５０−１６６６，Ｍａｙ  ２００５と、Ｓ．Ｂｒｕｃｋ，Ｕ．Ｓｏｒｇｅｒ，Ｓ．Ｇｌｉｇｏｒｅｖｉｃ，ａｎｄ  Ｎ．Ｓｔｏｌｔｅ，「Ｉｎｔｅｒｌｅａｖｉｎｇ  ｆｏｒ  ｏｕｔｅｒ  ｃｏｎｖｏｌｕｔｉｏｎａｌ  ｃｏｄｅｓ  ｉｎ  ＤＳ−ＣＤＭＡ  ｓｙｓｔｅｍｓ」，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，ｖｏｌ．４８，ｐｐ．１１００−１１０７，Ｊｕｌｙ  ２０００において、また、Ｋ．Ｋｕｓｕｍｅ  ａｎｄ  Ｇ．Ｂａｕｃｈ，「Ｃｙｃｌｉｃａｌｌｙ  ｓｈｉｆｔｅｄ  ｍｕｌｔｉｐｌｅ  ｉｎｔｅｒｌｅａｖｅｒｓ」，ｉｎ  Ｇｌｏｂｅｃｏｍ，ＩＥＥＥ，Ｎｏｖｅｍｂｅｒ／Ｄｅｃｅｍｂｅｒ  ２００６と、Ｋｕｓｕｍｅ  ａｎｄ  Ｇ．Ｂａｕｃｈ，「Ｓｏｍｅ  ａｓｐｅｃｔｓ  ｏｆ  ｉｎｔｅｒｌｅａｖｅ  ｄｉｖｉｓｉｏｎ  ｍｕｌｔｉｐｌｅ  ａｃｃｅｓｓ  ｉｎ  ａｄ  ｈｏｃ  ｎｅｔｗｏｒｋｓ」，ｉｎ  ４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｕｒｂｏ  Ｃｏｄｅｓ  ａｎｄ  Ｒｅｌａｔｅｄ  Ｔｏｐｉｃｓ，Ａｐｒｉｌ  ２００６またはインターリーブ分割多元アクセス（ＩＤＭＡ）において考察されている。
【００２４】
多次元ターボ符号のための複数のインターリーバは、Ａ．Ｂａｒｂｕｌｅｓｃｕ  ａｎｄ  Ｓ．Ｐｉｅｔｒｏｂｏｎ，「Ｉｎｔｅｒｌｅａｖｅｒ  ｄｅｓｉｇｎ  ｆｏｒ  ｔｈｒｅｅ  ｄｉｍｅｎｓｉｏｎａｌ  ｔｕｒｂｏ  ｃｏｄｅｓ」，ｉｎ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｐ．３７，Ｓｅｐｔｅｍｂｅｒ  １９９５と、Ｎ．Ｅｈｔｉａｔｉ，Ｍ．Ｓｏｌｅｙｍａｎｉ，ａｎｄ  Ｈ．Ｓａｄｊａｄｐｏｕｒ，「Ｉｎｔｅｒｌｅａｖｅｒ  ｄｅｓｉｇｎ  ｆｏｒ  ｍｕｌｔｉｐｌｅ  ｔｕｒｂｏ  ｃｏｄｅｓ」，ｉｎ  Ｃａｎａｄｉａｎ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｃｏｍｐｕｔｅｒ  Ｅｎｇｉｎｅｅｒｉｎｇ，ｐｐ．１６０５−１６０７，Ｍａｙ  ２００３と、Ｎ．Ｅｈｔｉａｔｉ，Ｍ．Ｓｏｌｅｙｍａｎｉ，ａｎｄ  Ｈ．Ｓａｄｊａｄｐｏｕｒ，「Ｊｏｉｎｔ  ｉｎｔｅｒｌｅａｖｅｒ  ｄｅｓｉｇｎ  ｆｏｒ  ｍｕｌｔｉｐｌｅ  ｔｕｒｂｏ  ｃｏｄｅｓ」，ｉｎ  ＩＥＥＥ  Ｖｅｈｉｃｕｌａｒ  Ｔｅｃｈｎｏｌｏｇｙ  Ｃｏｎｆｅｒｅｎｃｅ（ＶＴＣ  Ｆａｌｌ），ｐｐ．２３０２−２３０６，Ｓｅｐｔｅｍｂｅｒ  ２００４において提案されている。Ｓ．Ｂｒｕｃｋ，Ｕ．Ｓｏｒｇｅｒ，Ｓ．Ｇｌｉｇｏｒｅｖｉｃ，ａｎｄ  Ｎ．Ｓｔｏｌｔｅ，「Ｉｎｔｅｒｌｅａｖｉｎｇ  ｆｏｒ  ｏｕｔｅｒ  ｃｏｎｖｏｌｕｔｉｏｎａｌ  ｃｏｄｅｓ  ｉｎ  ＤＳ−ＣＤＭＡ  ｓｙｓｔｅｍｓ」，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，ｖｏｌ．４８，ｐｐ．１１００−１１０７，Ｊｕｌｙ  ２０００において、著者らは、いくつかの畳み込み符号の条件下におけるマルチユーザ干渉の影響を最小限に抑えるための、ランダム合同式インターリーバ（random congruent interleaver）での設計基準を導出している。欠点は、符号特性が、例えば、レート適応符号化方式におけるパンクチャリングなどによって変更された場合、インターリーバが変更されねばならないことである。さらに、設計基準を満たすために、最小インターリーバサイズも必要とされる。
【００２５】
特に、符号化率の小さい符号では、この最小インターリーバサイズが、法外に大きくなる。別の設計基準が、Ａ．Ｔａｒａｂｌｅ，Ｇ．Ｍｏｎｔｏｒｓｉ，ａｎｄ  Ｓ．Ｂｅｎｅｄｅｔｔｏ，「Ａｎａｌｙｓｉｓ  ａｎｄ  ｄｅｓｉｇｎ  ｏｆ  ｉｎｔｅｒｌｅａｖｅｒｓ  ｆｏｒ  ｉｔｅｒａｔｉｖｅ  ｍｕｌｔｉｕｓｅｒ  ｒｅｃｅｉｖｅｒｓ  ｉｎ  ｃｏｄｅｄ  ＣＤＭＡ  ｓｙｓｔｅｍｓ」，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．５１，ｐｐ．１６５０−１６６６，Ｍａｙ  ２００５で論じられており、この論文において著者らは、インターリービング後に結果として生じる符号語間の交わり、すなわち共通符号語の集合を最小にするという発見的基準（heuristic criterion）を使用している。
【００２６】
しかしながら、この基準には違反するが、代わりに、適切なターボ処理のための個々のインターリーバの基準を満たすインターリーバは、より望ましい性能を示すことが判明している。これもまた、適切な設計基準を見出すことの難しさを強調し、より一層発見的手法とシミュレーションによる評価に依存することを正当化するものである。さらに、畳み込み符号と組み合わせた合同式シンボルインターリーバの事例を除いて、Ａ．Ｔａｒａｂｌｅ，Ｇ．Ｍｏｎｔｏｒｓｉ，ａｎｄ  Ｓ．Ｂｅｎｅｄｅｔｔｏ，「Ａｎａｌｙｓｉｓ  ａｎｄ  ｄｅｓｉｇｎ  ｏｆ  ｉｎｔｅｒｌｅａｖｅｒｓ  ｆｏｒ  ｉｔｅｒａｔｉｖｅ  ｍｕｌｔｉ−ｕｓｅｒ  ｒｅｃｅｉｖｅｒｓ  ｉｎ  ｃｏｄｅｄ  ＣＤＭＡ  ｓｙｓｔｅｍｓ」，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．５１，ｐｐ．１６５０−１６６６，Ｍａｙ  ２００５には、他の構築方法が示されていない。Ｋ．Ｋｕｓｕｍｅ  ａｎｄ  Ｇ．Ｂａｕｃｈ，「Ｃｙｃｌｉｃａｌｌｙ  ｓｈｉｆｔｅｄ  ｍｕｌｔｉｐｌｅ  ｉｎｔｅｒｌｅａｖｅｒｓ」，ｉｎ  Ｇｌｏｂｅｃｏｍ，ＩＥＥＥ，Ｎｏｖｅｍｂｅｒ／Ｄｅｃｅｍｂｅｒ  ２００６と、Ｋ．Ｋｕｓｕｍｅ  ａｎｄ  Ｇ．Ｂａｕｃｈ，「Ｓｏｍｅ  ａｓｐｅｃｔｓ  ｏｆ  ｉｎｔｅｒｌｅａｖｅ  ｄｉｖｉｓｉｏｎ  ｍｕｌｔｉｐｌｅ  ａｃｃｅｓｓ  ｉｎ  ａｄ  ｈｏｃ  ｎｅｔｗｏｒｋｓ」，ｉｎ  ４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｕｒｂｏ  Ｃｏｄｅｓ  ａｎｄ  Ｒｅｌａｔｅｄ  Ｔｏｐｉｃｓ，Ａｐｒｉｌ  ２００６において採用されている発見的手法については、以下でより詳細に説明する。
【００２７】
多次元並列連結畳み込み符号の状況でのインターリーバ設計は、Ｎ．Ｅｈｔｉａｔｉ，Ｍ．Ｓｏｌｅｙｍａｎｉ，ａｎｄ  Ｈ．Ｓａｄｊａｄｐｏｕｒ，「Ｉｎｔｅｒｌｅａｖｅｒ  ｄｅｓｉｇｎ  ｆｏｒ  ｍｕｌｔｉｐｌｅ  ｔｕｒｂｏ  ｃｏｄｅｓ」，ｉｎ  Ｃａｎａｄｉａｎ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｃｏｍｐｕｔｅｒ  Ｅｎｇｉｎｅｅｒｉｎｇ，ｐｐ．１６０５−１６０７，Ｍａｙ  ２００３と、Ｎ．Ｅｈｔｉａｔｉ，Ｍ．Ｓｏｌｅｙｍａｎｉ，ａｎｄ  Ｈ．Ｓａｄｊａｄｐｏｕｒ，「Ｊｏｉｎｔ  ｉｎｔｅｒｌｅａｖｅｒ  ｄｅｓｉｇｎ  ｆｏｒ  ｍｕｌｔｉｐｌｅ  ｔｕｒｂｏ  ｃｏｄｅｓ」，ｉｎ  ＩＥＥＥ  Ｖｅｈｉｃｕｌａｒ  Ｔｅｃｈｎｏｌｏｇｙ  Ｃｏｎｆｅｒｅｎｃｅ（ＶＴＣ  Ｆａｌｌ），ｐｐ．２３０２−２３０６，Ｓｅｐｔｅｍｂｅｒ  ２００４において対処されている。ここでは、再帰的畳み込み構成要素符号のフィードバック多項式によって可分（divisible）データシーケンスは、重みの小さい符号語を生じるという事実が考慮に入れられている。インターリーバは、これらの可分パターンを不可分のパターンに置換する必要がある。１つのインターリーバに多くの制限を加えないように、Ｎ．Ｅｈｔｉａｔｉ，Ｍ．Ｓｏｌｅｙｍａｎｉ，ａｎｄ  Ｈ．Ｓａｄｊａｄｐｏｕｒ，「Ｉｎｔｅｒｌｅａｖｅｒ  ｄｅｓｉｇｎ  ｆｏｒ  ｍｕｌｔｉｐｌｅ  ｔｕｒｂｏ  ｃｏｄｅｓ」，ｉｎ  Ｃａｎａｄｉａｎ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｃｏｍｐｕｔｅｒ  Ｅｎｇｉｎｅｅｒｉｎｇ，ｐｐ．１６０５−１６０７，Ｍａｙ  ２００３と、Ｎ．Ｅｈｔｉａｔｉ，Ｍ．Ｓｏｌｅｙｍａｎｉ，ａｎｄ  Ｈ．Ｓａｄｊａｄｐｏｕｒ，「Ｊｏｉｎｔ  ｉｎｔｅｒｌｅａｖｅｒ  ｄｅｓｉｇｎ  ｆｏｒ  ｍｕｌｔｉｐｌｅ  ｔｕｒｂｏ  ｃｏｄｅｓ」，ｉｎ  ＩＥＥＥ  Ｖｅｈｉｃｕｌａｒ  Ｔｅｃｈｎｏｌｏｇｙ  Ｃｏｎｆｅｒｅｎｃｅ（ＶＴＣ  Ｆａｌｌ），ｐｐ．２３０２−２３０６，Ｓｅｐｔｅｍｂｅｒ  ２００４の考え方は、各インターリーバが、切断される必要のある重要パターンの一部を処理するというものである。これは、少なくとも１つの構成要素符号が符号語に重みを付与することを保証する。しかしながら、これらの設計基準は、並列連結畳み込み符号だけに限定され、構成要素符号の特定の選択に依存するものである。さらに、低コストでの実施を可能にするはずの単純な構築方法が示されていない。Ａ．Ｂａｒｂｕｌｅｓｃｕ  ａｎｄ  Ｓ．Ｐｉｅｔｒｏｂｏｎ，「Ｉｎｔｅｒｌｅａｖｅｒ  ｄｅｓｉｇｎ  ｆｏｒ  ｔｈｒｅｅ  ｄｉｍｅｎｓｉｏｎａｌ  ｔｕｒｂｏ  ｃｏｄｅｓ」，ｉｎ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｐ．３７，Ｓｅｐｔｅｍｂｅｒ  １９９５の提案は、３つの畳み込み符号の並列連結だけに限定され、小さいブロック長に焦点を当てるものである。ここでの目標は、すべての構成要素符号が同じ状態で終了するようにすることである。
【００２８】
合同式インターリーバは、単純な式から、異なるブロック長での複数のインターリーバを構築することを可能にする、直接的な手法を提供する。しかしながら、合同式インターリーバは、限られたランダム性しか導入せず、最適には及ばない性能をもたらす。
【００２９】
複数のインターリーバを構築する単純な方法が、合同式インターリーバを異なるシードと共に使用するものである。合同式インターリーバの置換規則は、Ｓ．Ｃｒｏｚｉｅｒ，Ｊ．Ｌｏｄｇｅ，Ｐ．Ｇｕｉｎａｎｄ，ａｎｄ  Ａ．Ｈｕｎｔ，「Ｐｅｒｆｏｒｍａｎｃｅ  ｏｆ  ｔｕｒｂｏ−ｃｏｄｅｓ  ｗｉｔｈ  ｒｅｌａｔｉｖｅ  ｐｒｉｍｅ  ａｎｄ  ｇｏｌｄｅｎ  ｉｎｔｅｒｌｅａｖｉｎｇ  ｓｔｒａｔｅｇｉｅｓ」，ｉｎ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｍｏｂｉｌｅ  Ｓａｔｅｌｌｉｔｅ  Ｃｏｎｆｅｒｅｎｃｅ，ｐｐ．２６８−２７５，１９９９に示されている。
【数１４】
2008154229.tif 000016
式中、ｓkは整数開始値であり、Ｎはインターリーバサイズであり、ｃkは、整数であり、一意のマッピングを保証するためにＮに対して素でなければならない。複数のインターリーバは、異なるｃkとｓkを用いて生成することができる。ｃkの値は、データシーケンス内の隣接するビットが、ｓビットの所定の最小間隔を有する位置にマップされるように選択され得る。この場合、インターリーバを、ｓランダム合同式インターリーバという。
【００３０】
Ｋ．Ｋｕｓｕｍｅ  ａｎｄ  Ｇ．Ｂａｕｃｈ，「Ｃｙｃｌｉｃａｌｌｙ  ｓｈｉｆｔｅｄ  ｍｕｌｔｉｐｌｅ  ｉｎｔｅｒｌｅａｖｅｒｓ」，ｉｎ  Ｇｌｏｂｅｃｏｍ，ＩＥＥＥ，Ｎｏｖｅｍｂｅｒ／Ｄｅｃｅｍｂｅｒ  ２００６と、Ｋ．Ｋｕｓｕｍｅ  ａｎｄ  Ｇ．Ｂａｕｃｈ，「Ｓｏｍｅ  ａｓｐｅｃｔｓ  ｏｆ  ｉｎｔｅｒｌｅａｖｅ  ｄｉｖｉｓｉｏｎ  ｍｕｌｔｉｐｌｅ  ａｃｃｅｓｓ  ｉｎ  ａｄ  ｈｏｃ  ｎｅｔｗｏｒｋｓ」，ｉｎ  ４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｕｒｂｏ  Ｃｏｄｅｓ  ａｎｄ  Ｒｅｌａｔｅｄ  Ｔｏｐｉｃｓ，Ａｐｒｉｌ  ２００６では、符号化率の小さいＦＥＣ符号化を有するユーザが、異なるインターリーバによって分離されるインターリーブ分割多元アクセス（ＩＤＭＡ）の状況における、循環シフトと自己インターリービングを使った、１つの共通のマザーインターリーバからの複数のインターリーバの生成が提案された。その利点は、単一のインターリービングパターンさえ格納されればよいことである。他のインターリーバは、ごく少数のパラメータ、すなわち循環シフトに基づき、必要に応じて構築することができる。複数のインターリーバの生成のために循環シフトを使用することは、Ｋ．Ｋｕｓｕｍｅ  ａｎｄ  Ｇ．Ｂａｕｃｈ，「Ｃｙｃｌｉｃａｌｌｙ  ｓｈｉｆｔｅｄ  ｍｕｌｔｉｐｌｅ  ｉｎｔｅｒｌｅａｖｅｒｓ」，ｉｎ  Ｇｌｏｂｅｃｏｍ，ＩＥＥＥ，Ｎｏｖｅｍｂｅｒ／Ｄｅｃｅｍｂｅｒ  ２００６における、ユーザ間の同期、すなわち、ユーザの信号が、マルチユーザ受信機において異なる遅延で到着することが、同じインターリーバがすべてのユーザに使用される場合でさえもこれらのユーザ、ならびに、ユーザ特有のランダムインターリーバを分離することを可能にすることを示した、マルチユーザ検出での所見によって動機付けられたものである。ユーザｋのインターリービングパターンΠkを、図３５に示すように、共通のインターリーバΠから、ユーザ特有の循環シフトΔk,cと、置換パターンのそれ自体によるインターリービングによって構築することが提案された。約Ｄ＝３のこのような循環シフトと自己インターリービング操作で、ランダムに選択されたインターリーバの場合と同じ性能を、同期ユーザを有するＩＤＭＡにおいて得ることができた。
【発明の開示】
【発明が解決しようとする課題】
【００３１】
本発明の目的は、改善された性能を提供する、ジグザグ符号のための符号器と復号器を提供することである。
【課題を解決するための手段】
【００３２】
この目的は、請求項１に記載の符号器と、請求項１４に記載の符号化する方法と、請求項１６に記載の復号器と、請求項１７に記載の復号化する方法によって達成される。
【００３３】
本発明は、インターリービング規則がジグザグ符号の特性にされるとき、連結ジグザグ符号を利用した通信システム性能の改善が得られるという知見に基づくものである。一実施形態では、インターリービング規則によって、符号全体の最小ハミング距離が増大される。一実施形態では、入力符号語がセグメント化され、インターリーバは、ある構成要素符号器の入力のところの１セグメント内のビットが、他の任意の構成要素符号器の入力のところの同じセグメントまたは隣接するセグメントにマップされないようにする。
【００３４】
したがって、各実施形態は、ジグザグ符号のパターンにおける最悪のものが回避されるため、最適化された性能を提供する。異なるインターリーバの共通のマッピングも回避される。さらに、インターリーバ生成がより構造化されているため、実施形態の実装の複雑さが、従来技術の概念のものより小さい。サブインターリーバは小規模であるので、より少ないメモリ所要量で済み、並列実装を可能にする。さらに、小さいサブインターリーバは、すべてのサブインターリーバに共通のマザーインターリーバが使用される場合には、さらに少ない所要メモリ量を可能にする。
【００３５】
各実施形態の詳細を、添付の図を用いて説明する。
【発明を実施するための最良の形態】
【００３６】
図１に、出力符号語より少ないビット数を有する入力情報語に基づいて出力符号語を生成する符号器１００を示す。符号器１００は、セグメンタ１１０と、ジグザグ符号器コア１２０と、インターリーバ１３０と、出力符号語コンストラクタ１４０とを備える。
【００３７】
セグメンタ１１０は、入力情報語を、いくつかのビットを有する複数の順序付けされたセグメントにセグメント化するようにされている。ジグザグ符号器１２０は、今次のセグメントの冗長ビットを計算するように設計されており、今次のセグメントの冗長ビットを計算するときには、前記順序における前のセグメントの冗長ビットを使用する。符号器１００は、インターリービング規則を用いて複数のセグメントのビットをインターリーブし、インターリーブバージョンを得るインターリーバ１３０を備える。出力符号語コンストラクタ１４０は、入力符号語またはそのインターリーブバージョンと、インターリーブバージョンによって供給され、ジグザグ符号器コア１２０によって生成される１組の冗長ビットを用いて、出力符号語を構築するようにされており、インターリーバ１３０は、同じセグメント内の入力情報語の入力情報語ビットの全セグメントの少なくとも５０％が、インターリーブバージョンの少なくとも１つの異なるセグメントに再配置されるようなインターリービング規則を使用するようにされている。
【００３８】
別の実施形態では、出力符号語コンストラクタ１４０は、さらに、入力符号語によって供給され、ジグザグ符号器コア１２０によって生成される冗長ビットを用いて、出力符号語を構築するようにされている。別の実施形態では、インターリーバ１３０は、別のインターリービング規則を用いて、複数のセグメントのビットの別のインターリーブバージョンを得るようにされており、出力符号語コンストラクタ１４０は、別のインターリーブバージョンによって供給され、ジグザグ符号器コア１２０によって生成される冗長ビットを用いて、出力符号語を構築するようにされている。
【００３９】
別の実施形態では、インターリーバ１３０は、入力情報語の同じセグメント内に位置する２つのビットが、インターリーブバージョン内の別々のセグメントに再配置されるようなインターリービング規則を使用するようにされている。別の実施形態では、インターリーバ１３０は、入力符号語の隣接するセグメント内に位置する２つのビットが、インターリーブバージョン内で少なくとも２セグメント離されるようなインターリービング規則を使用するようにされていてもよい。
【００４０】
別の実施形態では、インターリーバ１３０は、入力情報語の２つのインターリーブバージョンと、２つのインターリーブバージョンによって供給され、ジグザグ符号器によって生成される２組の冗長ビットとを用いて構築される２つの出力符号語が、入力情報語よりも大きい最小ハミング重みを有するようなインターリービング規則を使用するようにされ得る。一実装形態では、任意の２つの出力符号語間の最小ハミング重みは、２より大きいものとすることができる。
【００４１】
各実施形態は、入力情報語内のビットの位置にインターリーブバージョン内の位置をランダムに割り当てるサブステップを備えるインターリービング規則を使用するようにされたインターリーバ１３０を有していてもよい。別の実施形態では、インターリービング規則は、入力情報語内のビットの位置に、インターリーブバージョン内の許容領域からの位置をランダムに割り当てるサブステップを備えていてもよい。この許容領域は、前に割り当てられているビットの位置まで一定の距離を有している。ここでの許容領域は、インターリーブバージョン内のすべての位置から決定され得るが、以前に割り当てられており、またはあるセグメントから以前に割り当てられた位置までにある一定の距離を設けるブロック済み領域が位置決めされ得る。
【００４２】
別の実施形態では、インターリーバ１３０は、あるインターリービング規則と別のインターリービング規則に基づく少なくとも２つのインターリーブバージョンを提供するようにされていてもよく、別のインターリービング規則は、少なくとも、入力情報語からのビットの少なくとも１０％の位置が、別のインターリーブバージョンにおいて、それらがあるインターリーブバージョン内で割り当てられている位置とは異なる位置に割り当てられるような規則である。インターリーバ１３０は、インターリーブバージョンをインターリーブすることによって別のインターリーブバージョンを得るようにされていてもよい。また、インターリーバ１３０は、インターリーブバージョンからの既定の領域内のランダムな位置を、入力情報語の位置に割り当てることに基づく、インターリービング規則を使用するようにさせることもできる。インターリーバ１３０は、既定の領域をさらにインターリーブするように動作することもできる。
【００４３】
図２に、セグメンタ１１０と、ジグザグ符号器コア１２０とインターリーバ１３０と符号語コンストラクタ１４０とを備える、符号器１００の別の実施形態を示す。図２に示す実施形態では、インターリーバは、ジグザグ符号器コア１２０と符号語コンストラクタ１４０に別のインターリーブバージョンを提供するようにされている。ジグザグ符号器１２０は、セグメンタ１１０から受け取られるセグメントと、インターリーバ１３０から受け取られる別のインターリーブバージョンに基づいて、追加の冗長ビットを提供するようにされ得る。したがって、符号語コンストラクタ１４０は、セグメンタ１１０から受け取られるセグメントと、インターリーバ１３０から受け取られるインターリーブバージョンまたは別のインターリーブバージョンと、セグメンタ１１０からのセグメントおよびインターリーバ１３０から受け取られるインターリーブバージョンまたは別のインターリーブバージョンを参照する、ジグザグ符号器から受け取られる冗長ビットとに基づく、出力符号語を提供するようにされ得る。
【００４４】
図３に、入力符号語を復号化し、入力符号語より少ないビット数を有する出力情報語を生成する復号器３００を示す。復号器３００は、セグメンタ３１０と、インターリーバ３２０と、ジグザグ復号器３３０とを備える。セグメンタ３１０は、入力符号語を、いくつかの情報ビットと冗長ビットを有する複数の順序付けされたセグメントにセグメント化するようにされている。復号器３００は、インターリービング規則を用いて複数のセグメントの情報ビットをインターリーブし、情報ビットのインターリーブバージョンを得るインターリーバ３２０を備え、インターリーバ３２０は、同じセグメント内の入力情報語の入力情報語ビットの全セグメントの少なくとも５０％が、インターリーブバージョンの少なくとも１つの異なるセグメントに再配置されるような、インターリービング規則を使用するようにされている。復号器３００は、情報ビット、情報ビットのインターリーブバージョンおよび冗長ビットに基づいて出力情報語を計算する、ジグザグ復号器３３０を備える。
【００４５】
各実施形態は、インターリーバの構築において、連結ジグザグ符号の要件を明示的に考慮に入れる。Ｌ．Ｐｉｎｇ，Ｘ．Ｈｕａｎｇ，ａｎｄ  Ｎ．Ｐｈａｍｄｏ，「Ｚｉｇｚａｇ  ｃｏｄｅｓ  ａｎｄ  ｃｏｎｃａｔｅｎａｔｅｄ  ｚｉｇｚａｇ  ｃｏｄｅｓ」，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．４７，ｐｐ．８００−８０７，Ｆｅｂｒｕａｒｙ  ２００１によれば、連結ジグザグ符号の漸近的性能は、符号全体の重みの小さい符号語によって決定される。各実施形態は、連結符号において最小ハミング距離が増大されると同時に、インターリーバによって十分なランダム性が提供されるため、このような重みの小さい符号語が生成されないという利点を提供する。各実施形態は、重みｗH＝２を有する符号語を回避する。ハミング重みｗH＝２を有する符号語が生成されるのは、図４に示すように、元のデータシーケンスが、同じセグメント内に位置し、インターリーバによって同じセグメントにマップされる、値ｄi,j＝１を有するただ２つのビットだけを有する場合である。
【００４６】
ｗH＝ｄmin＝２の最小ハミング距離を有する符号語が左側に示され、「構成要素符号１」と表示されている。図４の右側には、「構成要素符号２」で表示される、インターリービング規則Πから生じる別の符号語が示されている。ハミング距離が増大されたことが分かる。各実施形態は、図４の規則Πに従ってインターリービング規則を提供する。したがって、各実施形態は、元のシーケンスの同じセグメント内のデータビットを、インターリーブバージョン内の異なるセグメントにマップする。図４を用いて説明したのと同様に、結果として生じる符号語の重みは、値１を有する２つのビットがマップされる先のセグメントがより遠く離されるほど大きくなるはずである。別の実施形態では、これを考慮に入れて、例えば、元のシーケンスの１セグメント内のビットが、最小で少なくともＢセグメント分離されている異なるセグメントにマップされるなど、より一層厳しいインターリーバ制限を実行することもできる。
【００４７】
別の実施形態では、２番目に小さい可能なハミング重みｗH＝３を有する符号語も考慮される。これらの符号語が生成されるのは、データシーケンスが、「構成要素符号１」で表す、図５の左側に示すような隣接するセグメント内に位置する値１の２つのビットを含む場合である。図５の左側には、やはりハミング重み３を有するジグザグ符号化された符号語が示されている。各実施形態は、図５の左側の符号語を、「構成要素符号２」で表す、右側にマップするインターリービング規則Πを提供する。ハミング重みが増大されることが分かる。２つの１ビット、インターリーバによってより遠くに拡散される。特に、図６に示すような状況が回避される。図６の左側には、図５の左側と同じ符号語が示されているが、図６で使用されるインターリービング規則は、ハミング重みｗH＝３を有する符号語を、最小ハミング距離を有する符号語にマップする。各実施形態は、これらの不利なマッピングを回避する。
【００４８】
各実施形態では、主に、ハミング重みが小さい符号語に焦点を当てる。したがって、別の実施形態では、図７に示すような、相当大きなｗH＝５のハミング重みを有する符号語（「構成要素符号１」）が、不都合なことに、ｗH＝４のハミング重みを有する符号語（「構成要素符号２」）にマップされる状況も生じる可能性もあるが、これらの符号語は、連結ジグザグ符号の漸近的性能を決定付けるわけではない。さらに、連結ジグザグ符号では、構成要素符号のパリティビットだけが送信され、それ以上の重みが符号語全体の連結構成要素符号によって生じることはない。図７の例では、非インターリーブデータ語により、すでにｗH＝５の重みの符号語を生じているため、あまり重大な事例ではない。さらに、データシーケンス内に値１を有するより多くのビットが含まれるほど、これらの１ビットが、１つまたはすべてのインターリーバによってさえも同じセグメントにマップされるコンステレーションの可能性が低くなる。各実施形態は、２つの主要な設計基準を有することができ、これらは以下のように要約することができる。
１．インターリーバ入力シーケンスの同じセグメント内に位置するビットは、少なくともＢセグメント離れた異なるセグメントにマップされるべきであり、Ｂ≧１は設計パラメータである。
２．インターリーバ入力シーケンスの隣接するセグメント内に位置するビットは、少なくともｎセグメント離れた異なるセグメントにマップされるべきであり、ｎ≧２は設計パラメータである。
【００４９】
一実施形態では、制限付きのランダムインターリーバの構築が実行され得る。この手法を図８に示す。図８には、入力シーケンスのインデックスの、出力シーケンスのインデックスへのマッピングが示されている。入力シーケンスは、それぞれがＪ個の要素を含むＩセグメントにセグメント化されるものと仮定する。図８では、これらのインデックスが、「ｉｎ」と表示された横軸上に示されている。図８の縦軸上には、「ｏｕｔ」と表示された、それぞれがＪ個の要素を含む、やはりＩセグメントに対応する出力インデックスが与えられている。したがって、横軸はインターリーバ入力シーケンスのインデックスを表し、縦軸は、出力シーケンスのインデックスを表す。
【００５０】
入力インデックスは、出力インデックスに、インデックス（ｉ，ｊ）＝（１，１）から（ｉ，ｊ）＝（Ｉ，Ｊ）まで連続してマップされる。第１のインデックス（ｉ，ｊ）＝（１，１）は、インデックス（ｉ’，ｊ’）にランダムにマップされる。第（ｉ’，ｊ’）の行は、それ以上の入力インデックスが同じ出力インデックスにマップされないように、ブロック済領域とマークされている。前述の基準１を満たすために、図８で示すように割り当てセグメントＩ’に属する、第Ｊ行の上の所定数ａＪの行と下のｂＪ行からなる第１のセグメントｉ＝１内の領域がブロックされている。各実施形態では、ａ＝ｂ＝ｋを選択し得る。次に、次のインデックス（ｉ，ｊ）＝（１，２）が（ｉ’，ｊ’）にマップされ、（ｉ’，ｊ’）はブロック済領域に位置決めすることができない。これは、インターリーバ入力のところの同じセグメント内に位置するすべてのビットが、少なくともＢ＝ｍｉｎ｛ａ，ｂ｝セグメント離れた異なるセグメントにマップされることを保証する。その後のすべてのインデックスがしかるべく割り当てられる。
【００５１】
また、前述の基準２を満たすために、入力シーケンスの２つのセグメントｉおよびｉ＋１のセグメントｉ’の上と下のそれぞれの行が、図９に示すように、ブロックされ得る。図９には、ブロック済領域がｉ＋１にも達することを示す、図８について示したのと同じ入力／出力インデックスマッピンググラフが示されている。これは、入力シーケンスの２つの隣接するセグメント内に位置するデータビットが、少なくともＢ＝ｍｉｎ｛ａ，ｂ｝セグメント離れたセグメントにマップされることを保証する。（２Ｊ−１）（ａ＋ｂ＋１）＞Ｉの場合、インターリーバの構築が不可能であることに留意されたい。実施形態の方法の収束を可能にするためには、以下が必要である。
【数１５】
2008154229.tif 000017
【００５２】
手短にいうと、１インターリーバ構築の実施形態は、以下のように要約することができる。
ｆｏｒ  ｉ＝１：Ｉ
ｆｏｒ  ｊ＝１：Ｊ
・列（ｉ，ｊ）内のブロックされていない（ｉ’，ｊ’）の集合からインデックス対（ｉ’，ｊ’）をランダムに選択する。
・行（ｉ’，ｊ’）をブロック済みとマークする。
・ｉ＝ｉ，ｉ＋１，ｊ＝１，・・・，Ｊ，ｉ’＝ｉ’−ａ，・・・，ｉ’＋ｂ，ｊ’＝１，・・・，Ｊについて、エントリ（ｉ’，ｊ’）、（ｉ，ｊ）をブロック済みとマークする。
ｅｎｄ  ｆｏｒ  ｊ
ｅｎｄ  ｆｏｒ  ｉ．
【００５３】
これまでは、１インターリーバの構築を可能にする実施形態を説明してきた。実施形態には、相互に独立のインターリーバの構築も可能にするものもある。一実施形態では、「相互に独立」の基準は、構築されるインターリーバが共通のマッピングを有さないこととすることもできる。各実施形態は、この基準を、以前に構築されたインターリーバΠ1からΠk-1までのブロック済領域の一部からなるブロック済領域を有する第ｋのインターリーバΠkの構築から開始することによって達成する。一実施形態では、図１０に示すように、各列において、それぞれの列の入力インデックス対（ｉ，ｊ）が、以前に構築されたインターリーバΠ1からΠk-1によってそこにマップされているインデックス対（ｉ’，ｊ’）、ならびにこれらのインデックス対（ｉ’，ｊ’）の上と下の所定数ｍ（ｍ≧０）の要素がブロックされている。図１０には、図８および９と同じ割り当て方式が示されているが、以前のインターリーバΠ1からΠk-1との共通のマッピングを回避するために、余分の領域がブロックされている。このブロッキングの結果として、インターリーバΠkの構築時に、特定の入力インデックス対について出力インデックス対を割り当てることのできない状況が生じた場合、以前に割り当てられたインターリーバΠ1からΠk-1に起因するブロッキングがこの列のために削除される。それでもなおマッピングが見つからない場合には、現在のインターリーバΠkの構築時に設定されたブロッキングも削除される。代替として、一実施形態では、現在のインターリーバΠkを、乱数生成器の新しいシードを用いて最初から復元して構築することができる。
【００５４】
前述の実施形態は、元のデータシーケンスを基準として使用する。しかしながら、第１のインターリーバΠ1によって、例えば図７に示す例のような、符号語全体の重みを増大させないシーケンスにマップされているより大きい重みのデータシーケンスが、その後のインターリーバΠ2からΠk-1によって、追加の重みを生成するシーケンスにマップされるよう保証するものではない。各実施形態はこれを、図１１の右側に示す符号器構造によって達成することができる。左側の構造とは対照的に、インターリーバΠkは、インターリーバΠkの出力において、元のシーケンスに対してではなく、置換されたシーケンスに対して作用する。
【００５５】
より高次の入力インデックス対（ｉ，ｊ）では、すでに加えられた制限のために、自由度が低減される。各実施形態は、各構築済インターリーバΠkごとの開始インデックスが変更される場合には、これを考慮に入れることができる。一実施形態では、アルゴリズムは、奇数のｋでは（ｉ，ｊ）＝（１，１）であり、偶数のｋでは、逆の順序が取られ、すなわち、最高次のインデックス対（ｉ，ｊ）＝（Ｉ，Ｊ）から開始される。一実施形態では、各ステップごとに次のインデックス対（ｉ，ｊ）をランダムに選択することによって、より一層のランダム化が達成され得る。この実施形態では、前述の基準２を満たすために、個々の行が、入力セグメントｉとｉ＋１についてのみならず、セグメントｉ−１についてもブロックされる。
【００５６】
前述の実施形態によるランダムインターリーバのグラフ表示を図１２から１５に示す。これらの図には、それぞれ、２つのインターリーバΠ1とΠ2の２つのグラフが示されている。Π1を濃色の○印で示し、Π2を淡色の○印で示す。図１２と１３には、それぞれがＪ＝４個の要素を備え、ブロック済領域のサイズが、図１２ではａ＝ｂ＝２、図１３ではａ＝ｂ＝４である、Ｉ＝１２８セグメントのグラフが示されている。図１４と図１５には、それぞれがＪ＝４個の要素を備え、ａ＝ｂ＝８であるＩ＝２５６セグメントのグラフが示されている。Π2の構成は図１５では（ｉ，ｊ）＝（Ｉ，Ｊ）で、図１４では（ｉ，ｊ）＝（１，１）で開始する。望ましいランダム化が達成され、２つのインターリーバΠ1とΠ2には共通のマッピングがないことが分かる。拡散は、より大きいａとｂが選択されるほどよい。
【００５７】
別の実施形態は、ジグザグ符号の要件を満たすインターリーバを生成する、より構造化されたアルゴリズムとして実行される。前述のものと同様に、部１６に示すグラフを用いて、実施形態を詳述する。図１６には、四角いインターリーバの図が示されており、横軸でインターリーバ入力シーケンスのインデックスを表し、縦軸で出力シーケンスのインデックスを表している。パターンにおける最悪のものを回避するために、許容されるマッピングの領域がブロックされている。元のシーケンスで同じセグメント内に位置するビットを、出力シーケンス内の異なるセグメントにマップするために、図１６には、各入力ビットのマッピングでのＡセグメントの許容領域が示されている。入力セグメント内の２つのビットの許容領域は、少なくともＢセグメント離されることになる。したがって、各入力セグメントＩ内の第ｊビットでのＡセグメントの許容領域は、奇数番号のセグメントｉでは、出力セグメントＩ’＝（ｊ−１）・（Ａ＋Ｂ）＋１，ｊ＝１，・・・Ｊから開始する。偶数番号のセグメントｉでは、許容領域は、すべての出力インデックス対への一意のマッピングを得るために、Ｂセグメントだけ上方にシフトされている。一意のマッピングの保証を簡素化するために、例示の実施形態は、ここでは、Ａ＝Ｂ＝Ｉ／２の場合だけに限定されている。一般に、別の実施形態内では、他のすべてのマッピングが考えられる。ここでは、Ｉ／２はＪの倍数であることを示唆しているが、一般的な事例では、任意のマッピングが考えられる。
【００５８】
この実施形態では、同じ許容領域を共用するすべての入力ビットが１つのブロックに積み重ねられ、図１７に示すようなＩ／２のインターリーバによってインターリーブされる。これらのインターリーバΠ’1からΠ’2Jには、同一のインターリービング規則または他の任意のインターリービング規則、例えば、ランダムインターリーバや、合同式インターリーバや、ＵＭＴＳターボ符号に指定されたインターリーバなどが使用され得る。インターリーバΠ’1からΠ’2Jは、同一のものとすることも異なるものとすることもできる。複数のより小さいインターリーバを使用すれば、置換パターンの所要メモリ量がより小さくなり、またはインターリーバ構成の労力がより少なくて済み、メモリアクセス衝突問題が緩和されるという利点がもたらされる。欠点は、インターリーバサイズが低減され、よって、ランダム化の効果が小さくなることである。その場合、インターリーバΠ’1からΠ’2Jの置換パターンは、図１７に示すように、十分なインターリーバパターンに再マップされる。
【００５９】
一実施形態では、セグメント内置換、すなわち、１セグメントｉ内の列の置換とセグメント置換、すなわち、同じ入力セグメントｉに属するサイズＪの列グループのグループごとの置換を行うことによって、さらなるランダム化を得ることができる。これらの置換は、擬似ランダムに、または任意の決定論的規則に従って行われ得る。しかしながら、各実施形態は、必ず奇数セグメントｉが奇数セグメントとだけ交換され、偶数セグメントが偶数セグメントとだけ交換されるセグメント置換を行う。
【００６０】
各実施形態は、異なる列置換を行うことによって、複数のインターリーバを容易に生成する。別の実施形態において、複数のインターリーバを得る別の少し複雑な方法では、異なるサイズのＩ／２インターリーバΠ’1からΠ’2Jを使用する。
【００６１】
各実施形態は、このようにして、パターンにおける最悪のものを回避することを保証するインターリーバを生成する。前述の基準１が満たされ、図６に示すような状況を回避するために、隣接するセグメントのビットが同じセグメントにマップされないことが保証される。実施形態の中には、前述の副次的基準２を完全に満たさない、すなわち、実施形態によっては、隣接するセグメントのビットが、図５に示すようにより遠くに拡散されないものもある。
【００６２】
図１８に、ランダム・サブ・インターリーバと、ランダムセグメント間およびセグメント内インターリービングを用いたＡＢインターリーバの図を示す。やはり、Ｉ＝１２８セグメント、１セグメント当たりＪ＝４個の要素を有するインターリーバの、出力インデックス対入力インデックスが示されている。望ましいランダム化が得られることが分かる。図１９ａと１９ｂに、ＡＢインターリーバの２つのグラフが示されており、図１９ａには、Ｉ＝１２８セグメント、１セグメント当たりＪ＝４個の要素の２つのインターリーバΠ1（×印）とΠ2（○印）が示されている。やはり、ランダム・サブ・インターリーバと、ランダムセグメント間およびセグメント内インターリービングが使用された場合には、図１９ａにおいて望ましいランダム化が得られる。図１９ｂには、ランダム・サブ・インターリーバを用い、セグメント間およびセグメント内インターリービングを用いない場合の、ＡＢインターリーバのグラフが示されている。やはり、Ｉ＝１２８セグメント、１セグメント当たりＪ＝４個の要素を有するインターリーバの、出力インデックス対入力インデックスが示されている。図２０ａには、類似の寸法の２つのインターリーバ、Π’1とΠ’2についての、ランダム・サブ・インターリーバを用い、セグメント間およびセグメント内インターリービングを用いない場合の、ＡＢインターリーバのグラフが示されている。図２０ｂには、同じ寸法での、ＵＭＴＳサブインターリーバとランダムセグメント間およびセグメント内インターリービングを用いた、ＡＢインターリーバのグラフが示されている。図２１ａには、２つのインターリーバ、Π’1（×印）とΠ’2（○印）が、同じ寸法で、ＵＭＴＳサブインターリーバとランダムセグメント間およびセグメント内インターリービングを用いた、ＡＢインターリーバについて示されている。図２１ｂには、セグメント間およびセグメント内インターリービングなしの単一インターリーバの結果が示されている。図２１ａでも２１ｂでも、図１８、１９ａ、１９ｂ、２０ａ、２０ｂと同じ寸法が使用されている。これらの図から、ＡＢインターリーバを用いて望ましいランダム化が得られることが分かる。
【００６３】
ビット誤り率性能（ＢＥＲ）について、前述の様々なインターリーバの比較を、Ｉ＝２５６セグメント、１セグメント当たりＪ＝４個の要素のジグザグ符号を用いて考察する。図２２に、Ｋ＝３、すなわち２つのインターリーバでのビット誤り率を示す。図２２には、複数のインターリーバのグラフが示されており、これらは、１循環シフトを行う循環ランダム２２ａ、１循環シフトを行う循環ＵＭＴＳ２２ｂ、ランダムインターリーバ２２ｃ、合同式インターリーバ２２ｄ、ｓランダム合同式インターリーバ２２ｅ、ジグザグランダムインターリーバ２２ｆ、ＡＢランダムインターリーバ２２ｇ、Ｄ＝３シフトを行う循環ＵＭＴＳインターリーバ２２ｈ、およびＤ＝３循環シフトを行う循環ランダムインターリーバ２２ｉである。図２２から、循環シフトインターリーバは、望ましい性能を得るために、Ｄ＝３循環シフトと、自己インターリービング操作を必要とすることが分かる。ランダムマザーインターリーバまたはマザーインターリーバとしてのＵＭＴＳインターリーバを有する循環シフトインターリーバは、エラーフロア領域において、ＵＭＴＳベースのインターリーバと同様にわずかに有利に機能する。合同式インターリーバは、比較的低い性能を示す。しかしながら、ｓ＝２・Ｊ＋１の選択を有するｓランダムインターリーバは非常に良好に機能する。これは、一実施形態としての制限付きランダムインターリーバとほぼ同じ性能を示す。別の実施形態としてのＡＢインターリーバは、ウォーターフォール領域における性能がわずかに劣る。これは、小さいサブインターリーバのランダム化の効果がより小さいことに起因するものである。ＡＢインターリーバは、エラーフロア領域において最善の性能を示す。
【００６４】
図２３に、図２２を求めるのに使用したのと同じ構成での、Ｋ＝４の異なるインターリーバ、すなわち３つのインターリーバを用いた場合の別のグラフの組を示す。図２３には、ランダムインターリーバ２３ａ、Ｄ＝３の循環シフトを行う循環ランダムインターリーバ２３ｂ、Ｄ＝３の循環シフトを行う循環シフトＵＭＴＳインターリーバ２３ｃ、合同式インターリーバ２３ｄ、ｓランダム合同式インターリーバ２３ｅ、共通のマッピングを有するジグザグランダムインターリーバ２３ｆ、およびＡＢランダムインターリーバ２３ｇが示されている。図２３から、ＡＢランダムインターリーバのジグザグランダムインターリーバが、その他のインターリーバより性能が優れていることが分かり、実施形態の利点が指し示されている。
【００６５】
図２４に、ビット誤り率の別のグラフを示す。このグラフでは、各実施形態による制限を有するランダムインターリーバでのインターリーバパターンΠ1からΠ2への共通マッピングの影響を調べている。Π1からΠ2への共通マッピングが許容されないときのＢＥＲ性能が、この制限なしでの性能と比較されている。違いは、エラーフロア領域でのみ見られ、ここでは、共通マッピングなしのインターリーバがより優れた性能を示している。
【００６６】
図２５に、各実施形態による、ＡＢインターリーバの変形の別のＢＥＲ性能比較を示す。すべてのグラフにおいてランダムセグメント内およびセグメント間置換が使用された。やはり、１セグメント当たりＪ＝４個の要素、Ｋ＝３個のパリティビットを有するＩ＝２５６セグメントの構成が選択された。異なるランダム・サブ・インターリーバを用いて最善の性能が得られる。比較のために、ＵＭＴＳインターリーバの結果と、すべてのインターリーバΠkの構成において、共通のランダムインターリーバがすべてのサブインターリーバに使用された場合の結果も示す。ランダム化の効果が減少すると、結果として性能が低下する。しかしながら、所要メモリ量の構成の複雑さが大幅に低減する。
【００６７】
図２６に、より大きい数のインターリーバ、すなわちＫ＝４の場合の別のＢＥＲ性能グラフを示す。Ｋ＝３の場合と比べて、ｓランダム合同式インターリーバの性能が、実施形態のものより著しく悪い。合同式の構築の規則は、異なるインターリーバ間の相互ランダム性を提供することができない。実施形態によるＡＢインターリーバの変形を比較すると、図２７に示すように、独立のランダム・サブ・インターリーバではなく共通のランダム・サブ・インターリーバを使用すると、エラーフロア領域における性能が著しく低下する結果になることが分かる。
【００６８】
本発明の実施形態は、ジグザグ符号の改善された性能を提供する。本発明の実施形態によれば、異なるインターリーバの共通のマッピングのみならず、ジグザグ符号のパターンにおける最悪のものも回避され、前述の利益がもたらされる。さらに、本発明の実施形態は、畳み込み符号やターボ符号のような従来技術の概念と比べて、複雑さを低減させて実施され得る。
【００６９】
本発明の方法のいくつかの実装要件に応じて、本発明の方法は、ハードウェアとしてもソフトウェアとしても実施され得る。実施は、デジタル記憶媒体、特に、プログラム可能なコンピュータシステムと協働して本発明の方法を実行する電子的に読み取り可能な制御信号が格納されている、ディスク、ＤＶＤまたはＣＤを用いて行われ得る。したがって、本発明は、一般に、コンピュータ上で実行されると本発明の方法を実行するように動作するプログラムコードが機械可読媒体上に格納されている、コンピュータプログラム製品である。したがって、言い換えると、本発明の方法は、コンピュータ上で実行されると本発明の方法の少なくとも１つを実行するプログラムコードを有する、コンピュータプログラムである。
【図面の簡単な説明】
【００７０】
【図１】符号器の一実施形態を示す図である。
【図２】符号器の別の実施形態を示す図である。
【図３】復号器の一実施形態を示す図である。
【図４】最小ハミング距離ｄmin＝２の符号語と最適化バージョンを示す図である。
【図５】ｗH＝３のハミング重みを有する符号語と最適化バージョンを示す図である。
【図６】ｗH＝３のハミング重みを有する符号語と最適状態に及ばないインターリーバを用いて得られるバージョンを示す図である。
【図７】ｗH＝５のハミング重みを有する符号語とインターリーブバージョンを示す図である。
【図８】インターリーバの構造の一実施形態を示す図である。
【図９】インターリーバの構造の別の実施形態を示す図である。
【図１０】インターリーバの構造の別の実施形態を示す図である。
【図１１】符号器の２つの代替実施形態を示す図である。
【図１２】インターリービング規則の一実施形態を示す図である。
【図１３】インターリービング規則の別の実施形態を示す図である。
【図１４】インターリービング規則の別の実施形態を示す図である。
【図１５】インターリービング規則の別の実施形態を示す図である。
【図１６】インターリーバの構造の別の実施形態を示す図である。
【図１７】インターリーバの構造の別の実施形態を示す図である。
【図１８】インターリービング規則の一実施形態を示すグラフである。
【図１９】図１９ａおよび図１９ｂはインターリービング規則の一実施形態を示すグラフである。
【図２０】図２０ａおよび図２０ｂはインターリービング規則の一実施形態を示すグラフである。
【図２１】図２１ａおよび図２１ｂはインターリービング規則の一実施形態を示すグラフである。
【図２２】一実施形態を用いて得られるビット誤り率を示すグラフである。
【図２３】一実施形態を用いて得られるビット誤り率を示す別のグラフである。
【図２４】共通のマッピングありとなしで一実施形態を用いて得られるビット誤り率を示すグラフである。
【図２５】異なる実施形態を用いて得られるビット誤り率を示すグラフである。
【図２６】異なるインターリーバを用いて得られるビット誤り率を示すグラフである。
【図２７】ＡＢインターリーバの一実施形態を用いたジグザグ符号のビット誤り率を示すグラフである。
【図２８】従来技術のジグザグ符号を示す図である。
【図２９】従来技術のジグザグ符号器を示す図である。
【図３０】最小ハミング距離ｄmin＝２を有するジグザグ符号語を示す図である。
【図３１】ハミング距離３を有するジグザグ符号語を示す図である。
【図３２】従来技術の連結ジグザグ符号の符号器を示す図である。
【図３３】連結ジグザグ符号の設計基準を示す図である。
【図３４】従来技術の連結ジグザグ符号の復号器を示す図である。
【図３５】従来技術の循環シフトを用いたインターリービング規則を示す図である。
【符号の説明】
【００７１】
１００  符号器
１１０  セグメンタ
１２０  ジグザグ符号器コア
１３０  インターリーバ
１４０  出力符号語コンストラクタ
３００  復号器
３１０  セグメンタ
３２０  インターリーバ
３３０  ジグザグ復号器
２２ａ  １循環シフトを行う循環ランダムインターリーバ
２２ｂ  １循環シフトを行う循環ＵＭＴＳインターリーバ
２２ｃ  ランダムインターリーバ
２２ｄ  合同式インターリーバ
２２ｅ  ｓランダム合同式インターリーバ
２２ｆ  ジグザグランダムインターリーバ
２２ｇ  ＡＢランダムインターリーバ
２２ｈ  ３循環シフトを行う循環ＵＭＴＳインターリーバ
２２ｉ  ３循環シフトを行う循環ランダムインターリーバ
２３ａ  ランダムインターリーバ
２３ｂ  ３循環シフトを行う循環ランダムインターリーバ
２３ｃ  ３循環シフトを行う循環ＵＭＴＳインターリーバ
２３ｄ  合同式インターリーバ
２３ｅ  ｓランダム合同式インターリーバ
２３ｆ  共通のマッピングを有するジグザグランダムインターリーバ
２３ｇ  ＡＢランダムインターリーバ
【図１】
2008154229.tif 000018
【図２】
2008154229.tif 000019
【図３】
2008154229.tif 000020
【図４】
2008154229.tif 000021
【図５】
2008154229.tif 000022
【図６】
2008154229.tif 000023
【図７】
2008154229.tif 000024
【図８】
2008154229.tif 000025
【図９】
2008154229.tif 000026
【図１０】
2008154229.tif 000027
【図１１】
2008154229.tif 000028
【図１２】
2008154229.tif 000029
【図１３】
2008154229.tif 000030
【図１４】
2008154229.tif 000031
【図１５】
2008154229.tif 000032
【図１６】
2008154229.tif 000033
【図１７】
2008154229.tif 000034
【図１８】
2008154229.tif 000035
【図１９】
2008154229.tif 000036
【図２０】
2008154229.tif 000037
【図２１】
2008154229.tif 000038
【図２２】
2008154229.tif 000039
【図２３】
2008154229.tif 000040
【図２４】
2008154229.tif 000041
【図２５】
2008154229.tif 000042
【図２６】
2008154229.tif 000043
【図２７】
2008154229.tif 000044
【図２８】
2008154229.tif 000045
【図２９】
2008154229.tif 000046
【図３０】
2008154229.tif 000047
【図３１】
2008154229.tif 000048
【図３２】
2008154229.tif 000049
【図３３】
2008154229.tif 000050
【図３４】
2008154229.tif 000051
【図３５】
2008154229.tif 000052
【外国語明細書】
2008154229.tif 000053
2008154229.tif 000054
2008154229.tif 000055
2008154229.tif 000056
2008154229.tif 000057
2008154229.tif 000058
2008154229.tif 000059
2008154229.tif 000060
2008154229.tif 000061
2008154229.tif 000062
2008154229.tif 000063
2008154229.tif 000064
2008154229.tif 000065
2008154229.tif 000066
2008154229.tif 000067
2008154229.tif 000068
2008154229.tif 000069
2008154229.tif 000070
2008154229.tif 000071
2008154229.tif 000072
2008154229.tif 000073
2008154229.tif 000074
2008154229.tif 000075
2008154229.tif 000076
2008154229.tif 000077
2008154229.tif 000078
2008154229.tif 000079
2008154229.tif 000080
2008154229.tif 000081
2008154229.tif 000082
2008154229.tif 000083
2008154229.tif 000084
2008154229.tif 000085
2008154229.tif 000086
2008154229.tif 000087
2008154229.tif 000088
2008154229.tif 000089
2008154229.tif 000090
2008154229.tif 000091
2008154229.tif 000092
2008154229.tif 000093
2008154229.tif 000094
2008154229.tif 000095
2008154229.tif 000096
2008154229.tif 000097
2008154229.tif 000098
2008154229.tif 000099
2008154229.tif 000100
2008154229.tif 000101
2008154229.tif 000102
2008154229.tif 000103
2008154229.tif 000104
2008154229.tif 000105
2008154229.tif 000106
2008154229.tif 000107
2008154229.tif 000108
2008154229.tif 000109