(57)【要約】【課題】  連結ジグザグ符号のためのパフォーマンスの高い符号器および復号器を提供する。【解決手段】  符号器１００は、入力情報語を複数のセグメントに分割するセグメンタ１１０と、今次のセグメントより順序が１つ先行するセグメントの冗長ビットを用いて今次のセグメントの冗長ビットを計算する符号器コア１２０を備える。インターリーバ１３０は、一連の中間的なサブステップを実行して得られる第１および第２のインターリービング規則を用いて前記セグメントから第１および第２のインターリーブバージョンを得る。符号語コンストラクタ１４０は入力情報語と符号器コア１２０が第１および第２のインターリーブバージョンから計算した第１および第２の冗長ビットの集合を使用して出力符号語を生成する。復号器３００は復号操作を行うための対応するコンポーネントを有し、入力符号語を復号して出力情報語を生成する。【選択図】  図１
2008136212.tif 000002
【特許請求の範囲】
【請求項１】
入力情報語に基づいてこの入力情報語よりもビット数が多い出力符号語を生成するための符号器（１００）であって、
前記入力情報語を各セグメントがいくつかのビットを有する複数の順序付けされたセグメントに分割するためのセグメンタ（１１０）と、
今次のセグメントより順序が先行するセグメントの冗長ビットを使用して、この今次のセグメントに対する冗長ビットを計算するための符号器コア（１２０）と、
第１のインターリービング規則を用いて前記複数のセグメントのビットをインターリーブして第１のインターリーブバージョンを得て、第２のインターリービング規則を用いて前記複数のセグメントのビットをインターリーブして第２のインターリーブバージョンを得るためのインターリーバであって、所定数の一連の中間的なサブステップを実行することによって得られる所定のインターリービング規則として前記第１のインターリービング規則を生成するように設計されたインターリーバ（１３０）と、
前記入力符号語またはそのインターリーブバージョンと、前記入力符号語または前記第１のインターリーブバージョンの供給を受けて前記符号器コア（１２０）によって生成された第１の冗長ビットの集合と、前記第２のインターリーブバージョンの供給を受けて符号器コア（１２０）によって生成された第２の冗長ビットの集合とを使用して前記出力符号語を構築するための出力符号語コンストラクタ（１４０）と
を具備し、前記インターリーバ（１３０）が、前記第２のインターリービング規則として、前記所定数の一連の中間的なサブステップのその所定数より省略されたサブステップの数だけ少ない数のサブステップを実行することによって得られる中間的なインターリービング規則か、前記省略された数のサブステップとは異なる方法で前記中間的なインターリービング規則を処理することによって得られるインターリービング規則かを使用するようされていることを特徴とする符号器（１００）。
【請求項２】
前記所定のインターリービング規則が、前記符号器コア（１２０）によって実行される符号化操作とは異なる符号化操作に対して最適化されていることを特徴とする請求項１に記載の符号器（１００）。
【請求項３】
前記所定のインターリービング規則が、連結畳み込み符号もしくはターボ符号に対して最適化されていることを特徴とする請求項１または２に記載の符号器（１００）。
【請求項４】
前記所定のインターリービング規則は、
各行がＣビットの入力情報語を有するセグメントに対応付けされるＲ本の行（横列）を有するＲ×Ｃの入力行列を生成するサブステップと、
前記入力行列の行同士を交換するサブステップと、
前記入力行列の交換された行内の要素同士を交換するサブステップと、
交換された行と交換された要素を有する入力行列を列方向に読み出すサブステップとを含むことを特徴とする請求項１〜３のいずれか１項に記載の符号器（１００）。
【請求項５】
前記所定のインターリービング規則が、３ＧＰＰ仕様書、ＴＳ２５．２１２，バージョン３．２．０，２０００−０３，リリース９９、に準拠することを特徴とする請求項１〜４のいずれか１項に記載の符号器（１００）。
【請求項６】
前記インターリーバ（１３０）が、前記所定のインターリービング規則からの中間的なインターリービング行列の転置または行もしくは列の交換に相当する中間的なインターリービング規則を処理するようにされていることを特徴とする請求項１〜５のいずれか１項に記載の符号器（１００）。
【請求項７】
合同式インターリーバの置換規則が行または列の交換を決定するために使用されることを特徴とする請求項４〜６のいずれか１項に記載の符号器（１００）。
【請求項８】
前記処理は、行または列が交換される、行または列が後方に読み出される、行または列がランダムな順序で読み出される、またはそれらの組み合わせになるような読み出し規則に基づく行列の読み出し操作を更に含むことを特徴とする請求項６または７に記載の符号器（１００）。
【請求項９】
入力情報語に基づいてこの入力情報語よりもビット数が多い出力符号語を生成することによって符号化するための符号化方法であって、
前記入力情報語を各セグメントがいくつかのビットを有する複数の順序付けされたセグメントに分割するステップと、
今次のセグメントより順序が先行するセグメントの冗長ビットを使用して、この今次のセグメントに対する冗長ビットを計算するステップと、
第１のインターリービング規則を用いて前記複数のセグメントのビットをインターリーブして第１のインターリーブバージョンを得て、第２のインターリービング規則を用いて前記複数のセグメントのビットをインターリーブして第２のインターリーブバージョンを得るステップであって、前記第１のインターリービング規則を所定数の一連の中間的なサブステップを実行することによって得られる所定のインターリービング規則として生成するように設計されたステップと、
前記入力符号語またはそのインターリーブバージョンと、前記入力符号語または前記第１のインターリーブバージョンに基づいて計算された第１の冗長ビットの集合と、前記第２のインターリーブバージョンに基づいて計算された第２の冗長ビットの集合とを使用して前記出力符号語を構築するステップとから成り、
前記複数のセグメントのビットをインターリーブするステップは、第２のインターリービング規則として、前記所定数の一連の中間的なサブステップのその所定数より省略されたサブステップの数だけ少ない数のサブステップを実行することによって得られる中間的なインターリービング規則か、前記省略された数のサブステップとは異なる方法で前記中間的なインターリービング規則を処理することによって得られるインターリービング規則かを使用するようされていることを特徴とする符号化方法。
【請求項１０】
コンピュータ上で走らせたときに、当該コンピュータが請求項９に記載された方法を実行することができるようにするためのプログラムコードを有するコンピュータプログラム。
【請求項１１】
入力符号語を復号し、この入力符号語よりもビット数が少ない出力情報語を生成するための復号器（３００）であって、
前記入力符号語を各セグメントがいくつかの情報ビットおよび冗長ビットを有する複数の順序付けされたセグメントに分割するためのセグメンタ（３１０）と、
第１のインターリービング規則を用いて前記複数のセグメントの情報ビットをインターリーブして第１のインターリーブバージョン情報ビットを得て、第２のインターリービング規則を用いて前記複数のセグメントの情報ビットをインターリーブして第２のインターリーブバージョン情報ビットを得るためのインターリーバであって、前記第１のインターリービング規則を所定数の一連の中間的なサブステップを実行することによって得られる所定のインターリービング規則として生成するように設計されたインターリーバ（３２０）と、
前記情報ビット、前記第１のインターリーブバージョン情報ビット、前記第２のインターリーブバージョン情報ビット、および前記冗長ビットに基づいて前記出力情報語を計算するための復号器（３３０）と
を具備し、前記インターリーバ（３２０）は、前記第２のインターリービング規則として、前記所定数の一連の中間的なサブステップのその所定数より省略されたサブステップの数だけ少ない数のサブステップを実行することによって得られる中間的なインターリービング規則か、前記省略された数のサブステップとは異なる方法で前記中間的なインターリービング規則を処理することによって得られるインターリービング規則かを使用するようされていることを特徴とする復号器（３００）。
【請求項１２】
入力符号語を復号し、この入力符号語よりもビット数が少ない出力情報語を生成するための復号方法であって、
前記入力符号語を各セグメントがいくつかの情報ビットおよび冗長ビットを有する複数の順序付けされたセグメントに分割するステップと、
第１のインターリービング規則を用いて前記複数のセグメントの情報ビットをインターリーブして第１のインターリーブバージョン情報ビットを得て、第２のインターリービング規則を用いて前記複数のセグメントの情報ビットをインターリーブして第２のインターリーブバージョン情報ビットを得るステップであって、前記第１のインターリービング規則を所定数の一連の中間的なサブステップを実行することによって得られる所定のインターリービング規則として生成するように設計されたステップと、
前記情報ビット、前記第１のインターリーブバージョン情報ビット、前記第２のインターリーブバージョン情報ビット、および、前記冗長ビットに基づいて前記出力情報語を計算するステップと
から成り、前記複数のセグメントの情報ビットをインターリーブするステップは、前記第２のインターリービング規則として、前記所定数の一連の中間的なサブステップのその所定数より省略されたサブステップの数だけ少ない数のサブステップを実行することによって得られる中間的なインターリービング規則か、前記省略された数のサブステップとは異なる方法で前記中間的なインターリービング規則を処理することによって得られるインターリービング規則かを使用するようされていることを特徴とする復号方法。
【請求項１３】
コンピュータ上で走らせたときに、当該コンピュータが請求項１２に記載された方法を実行することができるようにするためのプログラムコードを有するコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、国際標準化団体によって仕様が定められた例えばＷＣＤＭＡ（Wideband Code Division Multiple Access）およびＯＦＤＭＡ（Orthogonal Frequency Division Multiple Access）ベースのネットワークなどの通信ネットワークのための技術に関し、特に、ＵＭＴＳのような現行の通信システムの向上のため、そして誤り制御符号化のためのＬＴＥとして将来の通信システムに導入される候補として、ジグザグ符号および連結ジグザグ符号が検討されている通信ネットワーク技術に関する。
【背景技術】
【０００２】
連結ジグザグ符号（concatenated zigzag codes）は、符号化および復号化の複雑さが比較的低く、それでいて優れたパフォーマンスを発揮することから、魅力的な符号化スキームである。強力な符号（パワフルコード）はいくつもの要素ジグザグ符号の並列連結によって得られ、インターリーブ版データ系列（並べ替えられたデータ系列）を符号化する。しかしこれは、イタレーションを用いた復号化（iterative decoding）のために最適化されるインターリーバは唯一つだけでなくいくつものインターリーバが必要とされるという、インターリーバ設計における新たな問題を示唆する。そうしたインターリーバ（交錯器）はそれぞれ、可能な限り相互に独立でありながら、イタレーションによる復号化の良好なパフォーマンスを発揮しなければならない。
【０００３】
ジグザグ符号（Zigzag codes）は非特許文献１において提案され、非特許文献２、非特許文献３、非特許文献４、非特許文献５、非特許文献６、非特許文献７および非特許文献８において拡張された。
【０００４】
ジグザグ符号は符号化と復号化の複雑さが低く、それでいて特に高い符号化率で優れたパフォーマンスを発揮することから魅力的である。イタレーションによる復号化による連結ジグザグ符号は、並列連結畳み込み符号（ターボ符号）より複雑さはかなり低いもののパフォーマンスは約０．５ｄＢだけ低いだけである。単一のジグザグ符号は、その最小ハミング距離がｄmin＝２と小さいため、非常に弱い符号（weak code）である。強い符号（strong codes）はジグザグ符号の連結によって得られ、この場合、各要素符号はインターリーブ版データ系列を符号化する。ジグザグ符号は単独では通常は比較的高い符号化率を有するため、適切な符号化率と誤り訂正能力を持つ符号を得るためには複数のジグザグ符号が連結される必要がある。いくつもの構成要素符号の連結によって低い符号化率を構築することは、通常２つの構成要素符号しか連結されないターボ符号とは異なる点である。
【０００５】
これは、イタレーションによる復号化のために最適化されるインターリーバは唯一つだけでなくいくつものインターリーバが必要とされるという、インターリーバ設計における新たな問題を示唆する。そうしたインターリーバはそれぞれ、可能な限り相互に独立でありながら、イタレーションによる復号化の良好なパフォーマンスを発揮しなければならない。複数のインターリーバの相互独立性に対する良い基準が何かはまだ未解決の問題である。それと同時に、インターリーバは構成要素復号器の外部情報がほぼ無相関になるようにランダム性を導入する。
【０００６】
ジグザグ符号（concatenated zigzag codes）は、符号化および復号化の複雑さが比較的低く、それでいて特に高い符号化率で優れたパフォーマンスを発揮することから、魅力的である。連結ジグザグ符号は並列連結畳み込み符号（ターボ符号）より複雑さはかなり低いもののパフォーマンスは約０．５ｄＢだけ低下する。通常のジグザグ符号の原理を図１０に示す。図中、丸プラス記号（＋を○で囲んだ記号）はモジュロ２の加算を表す。データビットｄij∈｛０，１｝はＩ×Ｊ行列に配列される。行列の各行（横列）をジグザグ符号のセグメント（segment）という。パリティビットｐiは１つ前のパリティビットｐi-1と各セグメントｉのモジュロ２の加算として求められる。ジグザグ符号は２つのパラメータIとJで完全に記述される。
【０００７】
ジグザグ符号のための等価符号器は図１１に示すようにメモリ１を持つパンクチャード再帰的畳み込み符号器である。パリティビットに対するパンクチャリングパタンはトレリス符号器のあらゆるＪ番目のパリティビットのみが送信されるように選ばれる。単一のジグザグ符号は最小ハミング距離がｄmin＝２のため脆弱なパフォーマンスを有する。これはセグメントｉ内の２データビットがフリップされるときに容易に確認される。
【０００８】
この場合、パリティビットｐiは不変のままで、結果、符号語内の他のビットは影響を受けない。データ系列が図１２に示すように同一セグメント内に値ｄi,j＝１のビットを２ビットだけ含む場合、最小ハミングウェイトｗH＝ｄmin＝２の符号語が生じる。ハミングウェイトがｗH＝３の低ウェイト符号語は図１３に示すように２つの連続するセグメントの中に値１のビットが１ビットだけ現れる場合に生成される。強力な符号を構築するため、いくつもの構成要素ジグザグ符号が連結される必要がある。各それぞれの構成要素符号器は図１４に示すようにデータビットのインターリーブ系列（interleaved sequence）を符号化する。図中、Πkはインターリーバｋの置換規則を表す。ジグザグ符号の符号化率はＲc＝Ｊ／（Ｊ＋１）と通常比較的高く、このためいくつものジグザグ符号が連結される必要がある。
【０００９】
図１５に信号対ノイズ比（ＳＮＲ）に対するビット誤り率から見たパフォーマンスを示す。イタレーションによる復号化アプローチの一般的なインターリーバの設計基準は図１５のグラフから導き出すことが可能である。イタレーションによる復号化による良好なパフォーマンスはインターリービング規則によって図のグラフに示された良いランダム化が実行される場合に得ることができる。良いランダム化はビット誤り率のグラフの急峻な傾斜をサポートする。別の設計基準は、パターンが最悪となることを回避することである。というのは、これも図１５に示されるように、ビット誤り率のグラフの傾斜を幾分なだらかにし、およびエラーフロア（error floor）を引き起こすからである。
【００１０】
連結構成要素符号に対しては、パリティビットのみが送信される。Ｋ個の構成要素符号では、全符号化率はＲc＝Ｊ／（Ｊ＋Ｋ）になる。複数のインターリーバの使用は、通常は２つの構成要素符号のみが連結されるターボ符号との基本的な相違点である。これは、イタレーションによる復号化のために最適化されるインターリーバは唯一つだけでなくいくつものインターリーバが必要とされるという、インターリーバ設計における新たな問題を示唆する。そうしたインターリーバはそれぞれ、可能な限り相互に独立でありながら、イタレーションによる復号化の良好なパフォーマンスを発揮しなければならない。複数のインターリーバの相互独立性に対する良い基準が何かはまだ未解決の問題である。１つの直感的な条件として挙げるとすれば、符号全体の最小ハミング距離を増大させるため、インターリービング（並べ替え）は、ある特定の構成要素符号器の入力における１つのセグメント内にあるビットが任意の他の構成要素符号器の入力における同じセグメントもしくは隣接セグメントにマップされないようにする必要がある。この問題は例えば図１２の例に示されている。ジグザグ構成要素符号の出力における最小ハミングウェイトがｗH＝ｄmin＝２の符号語は、値ｄi,j＝１の２ビットが同一セグメントｉ内に存在するデータ系列によって生成される。符号全体の最小ハミング距離を増大させるため、インターリーバは、そうしたデータ系列がその他の構成要素符号器の出力においてより高いハミングウェイトの符号語を作り出すようにする必要がある。
【００１１】
図１１の表現は、ジグザグ符号は例えば非特許文献９にあるＢＣＪＲアルゴリズムといったトレリス（trellis）ベースのアルゴリズムによって復号することができることを提案している。復号器の入力において、パンクチャされるビットの位置にゼロが挿入される必要がある。後方再帰（backward recursion）の初期化では、ジグザグ符号器は所定の状態では終了されないことからトレリスの全ての終状態は等しいと仮定することができる。しかしながら、セグメントに分割することで、これも前方および後方再帰（forward and a backward recursion）を実行するＭＬＡアルゴリズムと呼ばれる複雑さがかなり低いアルゴリムを使ってジグザグ符号を復号することができる。非特許文献１に記されているシンプル版ＭＬＡアルゴリムは符号語にわたってＳＮＲが一定のＡＷＧＮチャネルに対してのみ機能する。ここでは時変チャネルでもより高次変調に対して機能する対数尤度比に基づくより一般的な説明が与えられる。まず、変調シンボルからデマップした後に得られるノイズを含む受信値を、データビットに対してはｄi,j、パリティビットに対してはｐiで表す。最初に、チャネル統計に基づく受信符号ビットと送信シンボルアルファベットのチャネル情報対数尤度比がデータビットとパリティビットに対してそれぞれ次のように計算される。
【数１】
2008136212.tif 000003
次に、データビットに関する、
【数２】
2008136212.tif 000004
で与えられるおそらく利用可能な事前情報（a-priori information）が、それを次式のようにチャネル情報に加えることによって考慮される。
【数３】
2008136212.tif 000005
【００１２】
次に、パリティビットに対するフォワードメトリック（forward metric）が次のように計算することができる。
【数４】
2008136212.tif 000006
式（５）および式（６）において、
【数５】
2008136212.tif 000007
はボックスプラス加算（boxplus sum）を意味する。ボックスプラス加算はそれぞれのビットのモジュロ２の加算に対応する対数尤度比の次のような操作である（非特許文献１０参照）。
【数６】
2008136212.tif 000008
【００１３】
ボックスプラス加算の正確な表現は非特許文献１０に次のように与えられている。
【数７】
2008136212.tif 000009
【００１４】
式（８）は次のように近似することができる。
【数８】
2008136212.tif 000010
【００１５】
式（６）の最初の項はパリティビットｐiに関するダイレクトチャネル情報プラス事前情報である。第二項は外部情報（extrinsic information）、すなわち符号制約条件に起因する符号語における全ての先行ビットから得られるｐiについての情報である。同様に、後方再帰（backward recursion）は次のように計算することができる。
【数９】
2008136212.tif 000011
【００１６】
このときＡＰＰ対数尤度比は次の式から得られる。
【数１０】
2008136212.tif 000012
【００１７】
式（１２）の最初の項はビットｄi,jに関するダイレクトチャネル情報プラス事前情報である。その他の項は外部情報、すなわち符号制約条件（code constraints）に起因する符号語における全ての他のビットから得られるｄi,jについての情報を構成する。連結ジグザグ符号は、構成要素符号がその他の構成要素復号器の外部情報を追加の事前情報と考えて復号されるイタレーションによるターボアルゴリズム（図１６参照）によって復号することができる。簡単のため図１６にはインターリーバは示されていない。各構成要素復号器ｌはデータビットとパリティビットに対する受信チャネル情報Ｌc（ｄi,j）およびＬc（ｐl,i）のほか、追加の事前情報Ｌa,l（ｄi,j）としてその他の構成要素復号器からの外部情報Ｌe,l（ｄi,j）も利用する。構成要素復号器ｌの外部情報は出力および入力対数尤度比の次のような差分によって定義される。
【数１１】
2008136212.tif 000013
イタレーションｎの際、事前情報は既に復号済みの構成要素復号器ｋ＝１，．．．，ｌ−１から現在のイタレーションｎにおいて得られた外部情報と、１つ前のイタレーションｎ−１で得られた復号器ｋ＝ｌ＋１，．．．，Ｋからの外部情報とを有する。
【００１８】
いくつものジグザグ構成要素符号を連結するには、Ｋ−１個の異なるインターリーバが必要とされる。一般に、複数のインターリーバはランダムに生成することができる。しかしながら、良好な相互特性を有するインターリーバが生成されることが保証できないという事実を除けば、Ｋ−１置換パタンがそれぞれ格納される必要があることから、必要メモリに関して重大な現実的問題が発生する。さらに、システムは様々なブロック長をサポートしなければならない場合がある。この場合、各可能なブロック長ごとにＫ個のインターリーバパタンを記憶する必要がある。それゆえ、シンプルな式からまたは共通のマザーインターリーバに対するシンプルな操作によって複数のインターリーバを生成することが望まれる。
【００１９】
複数のインターリーバのためのメモリを確保する問題は非特許文献７および非特許文献１１においてジグザグ符号のコンテクストにおいて取り組まれている。
【００２０】
ここには、立方体内にデータビットを配置し、立方体の様々な方向でジグザグ符号化を実行することによって、多次元ジグザグ符号を構築することが提案されている。しかしながら、そうすることによって、設計空間が制限され、特に構成要素ジグザグ符号のパラメータＪが固定され、異なることがある。
【００２１】
非特許文献１１（N. Nefedov著）には、同じ枠組みの中でＵＭＴＳ用に仕様が定められた並列連結畳み込み符号とジグザグ符号の利用を可能にする提案が示されている。インターリービングに関する限り、著者（N. Nefedov）はＵＭＴＳターボ符号用に仕様が定められたインターリーバと、第３の連結構成要素ジグザグ符号のためのインターリーバとしてその転置を利用することを提案している。このスキームは非常にシンプルではあるが、インターリーバ数は２に限定されている。また著者（N. Nefedov）は、ＵＭＴＳインターリーバからインターリーバのアドレスを交換（swap）することによって追加のインターリーバを生成することを更に提案している。しかしながら、これをどのように実行すべきかの情報は全く与えられていない。
【００２２】
多重インターリーバ（multiple interleavers）の設計に関する論文はごくわずかしか存在せず、適切な設計基準はまだ未解決の問題のままである。
【００２３】
多重インターリーバは、ＣＤＭＡ（code division multiple access）におけるマルチユーザ検出のコンテクストにおいて非特許文献１２および非特許文献１３に、ＩＤＭＡ（interleave division multiple access）のコンテクストにおいて非特許文献１４および非特許文献１５に考察されている。
【００２４】
多次元ターボ符号のための多重インターリーバが非特許文献１６、非特許文献１７および非特許文献１８に提案されている。また非特許文献１３において、著者等は特定の畳み込み符号の条件下でマルチユーザ干渉の影響を最小化するためにランダム合同式インターリーバ（random congruential interleavers）に対する設計基準を導出している。符号特性が例えばレート適応符号化スキームにおけるパンクチャリングによって変化すれば、インターリーバも変化する必要があることが不利な点である。さらに、設計基準を満足するために最小インターリーバサイズが要求される。
【００２５】
特に、低レート符号では、この最小インターリーバサイズは極めて大きくなる。そこで別の設計基準が非特許文献１２において議論されている。非特許文献１２の著者等はインターリービング後の結果の符号語同士の間の交わり、つまり共通の符号語の集合を最小化する経験的基準を採用している。
【００２６】
しかしながら、そうしたインターリーバはこの基準を破るが、その代わり、個別のインターリーバでは良好なターボ処理のための基準を満足し、より良いパフォーマンスを示すことが判明している。これはこの場合も同じく適切な設計基準を見つける困難を重視し、経験的アプローチとシミュレーションによる評価にもっと頼ることを正当化する。さらに、合同式シンボルインターリーバを畳み込み符号と組み合わせた場合を除いては、非特許文献１２には何の構成方法も与えられていない。非特許文献１４、非特許文献１５で採用された経験的アプローチについて以下より詳しく説明する。
【００２７】
多次元並列連結畳み込み符号のコンテクストにおけるインターリーバ設計が非特許文献１７および非特許文献１８において取り組まれている。ここでは、再帰的畳み込み構成要素符号のフィードバック多項式によって可分なデータ系列が低ウェイト符号語を作り出すという事実が考慮されている。インターリーバはそうした可分（dividible）パタンを非可分（non-dividible）パタンへ並べ替える必要がある。１つのインターリーバにあまり多くの制約を課さないようにするため、非特許文献１７および非特許文献１８において、各インターリーバが破られる必要のある臨界パタンの部分集合を処理するというアイデアが提案されている。これにより、少なくとも１つの構成要素符号が符号語にウェイトを寄与することが保証される。しかしながら、設計基準は並列連結畳み込み符号（ターボ符号）に限定され、構成要素符号の特定の選択に依存する。さらに、低コストの実装を可能にするシンプルな構成方法が与えられていない。非特許文献１６における提案は３つの畳み込み符号の並列連結に限定され、小さなブロック長に焦点を置いている。ここでの目標は全ての構成符号が同じ状態で終わることを保証することである。
【００２８】
合同式インターリーバは、シンプルな式からブロック長の異なる多重インターリーバを構築することを可能にする直接的なアプローチを提供する。しかしながら、合同式インターリーバは、次善最適なパフォーマンスをもたらす制限されたランダム性を導入する。
【００２９】
多重インターリーバを構築するシンプルな方法はスピードが異なる合同式インターリーバを使用することである。合同式インターリーバの置換規則は非特許文献１９に次のように与えられている。
【数１２】
2008136212.tif 000014
上式においてｓkは整数の開始値、Ｎはインターリーバサイズ、ｃkは一意写像を保証するためにＮと互いに素でなければならない整数である。多重インターリーバは異なるｃkとｓkを使用することによって生成することができる。ｃkの値は、データ系列内の隣接ビットがｓビットの所定の最小間隔だけ間隔を置いた位置にマップされるように選ぶことができる。この場合、インターリーバはｓランダム合同式インターリーバ（s-random congruential interleaver）と呼ばれる。
【００３０】
１つの共通のマザーインターリーバから巡回シフト（cyclic shifts）と自己インターリービング（self-interleaving）を使用して多重インターリーバを生成することは非特許文献１４および非特許文献１５の中でＩＤＭＡ（interleave division multiple access）のコンテクストにおいて提案された。この提案の中で低レートＦＥＣ符号化を用いるユーザ達は異なるインターリーバによって分離される。利点は単一のインターリービングパタンのみが記憶される必要があるということである。他のインターリーバは必要に応じて非常に少数のパラメータ、すなわち巡回シフトに基づいて構築することができる。多重インターリーバの生成に巡回シフトを利用することは、ユーザ間の同期−ユーザの信号が異なる遅延時間でマルチユーザ受信機に到達する−のおかげで全てのユーザに同じインターリーバが使用される場合でもユーザおよびユーザ別のランダムインターリーバを分離することができることを示したマルチユーザ検出の観測（非特許文献１４参照）によって動機付けられる。また図１７に示すようにユーザｋのインターリービングパタンΠkを共通のインターリーバΠからユーザ別の巡回シフトΔk,cと置換パタンのインターリービングを使って構築することが提案された。大体Ｄ＝３の場合に斯かる巡回シフトおよび自己インターリービング操作を用いて、ランダムに選ばれたインターリーバによるものと同じパフォーマンスがユーザが同期しているＩＤＭＡにおいて得ることができた。
【非特許文献１】L. Ping, X. Huang, and N. Phamdo, "Zigzag codes and concatenated zigzag codes," IEEE Transactions on Information Theory, vol. 47, pp. 800-807, February 2001
【非特許文献２】S.-N. Hong and D.-J. Shin, "Construction and analysis of rate compatible punctured concatenated zigzag codes," in International Symposium on Information Theory (ISIT), pp. 840-844, IEEE, September 2005
【非特許文献３】S.-N. Hong and D.-J. Shin, "Optimal rate-compatible punctured concatenated zigzag codes," in International Conference on Communications (ICC), pp. 627-631, IEEE, May 2005
【非特許文献４】S.-N. Hong and D.-J. Shin, "Design of irregular concatenated zigzag codes," in International Symposium on Information Theory (ISIT), pp. 1363-1366, IEEE, September 2005
【非特許文献５】L. Ping, S. Chan, and K. Yeung, "Iterative decoding of multidimensional concatenated single parity check codes," in International Conference on Communications (ICC), pp. 131-135, IEEE, June 1998
【非特許文献６】X. Wu, Y. Xue, and H. Xiang, "On concatenated zigzag codes and their decoding schemes," IEEE Communications Letters, vol. 8, pp. 54-56, January 2004
【非特許文献７】N. Nefedov, "Multi-dimensional zigzag codes for high data rate transmission," in 3rd International Symposium on Turbo Codes and Related Topics, pp. 215-218, September 2003
【非特許文献８】N. Nefedov, "data rate transmission," in 14th International Symposium on Personal, Indoor and Mobile Radio Communications, pp. 1868-1872, September 2003
【非特許文献９】L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, "Optimal decoding of linear codes for minimizing symbol error rate," IEEE Transactions on Information Theory, vol. IT-20, pp. 284-287, March 1974
【非特許文献１０】J. Hagenauer, E. Offer, and L. Papke, "Iterative decoding of binary block and convolutional codes," IEEE Transactions on Information Theory, vol. IT-42, pp. 425-429, March 1996
【非特許文献１１】N. Nefedov, "Evaluation of low complexity concatenated codes for high data rate transmission," in 14th International Symposium on Personal, Indoor and Mobile Radio Communications, pp. 1868-1872, September 2003
【非特許文献１２】A. Tarable, G. Montorsi, and S. Benedetto, "Analysis and design of interleavers for iterative multiuser receivers in coded CDMA systems," IEEE Transactions on Information Theory, vol. 51, pp. 1650-1666, May 2005
【非特許文献１３】S. Bruck, U. Sorger, S. Gligorevic, and N. Stolte, "Interleaving for outer convolutional codes in DS-CDMA systems," IEEE Transactions on Communications, vol. 48, pp. 1100-1107, July 2000
【非特許文献１４】K. Kusume and G. Bauch, "Cyclically shifted multiple interleavers," in Globecom, IEEE, November/December 2006
【非特許文献１５】K. Kusume and G. Bauch, "Some aspects of interleave division multiple access in ad hoc networks," in 4th International Symposium on Turbo Codes and Related Topics, April 2006
【非特許文献１６】A. Barbulescu and S. Pietrobon, "Interleaver design for three dimensional turbo codes," in IEEE International Symposium on Information Theory, p. 37, September 1995
【非特許文献１７】N. Ehtiati, M. Soleymani, and H. Sadjadpour, "Interleaver design for multiple turbo codes," in Canadian Conference on Electrical and Computer Engineering, pp. 1605-1607, May 2003
【非特許文献１８】N. Ehtiati, M. Soleymani, and H. Sadjadpour, "Joint interleaver design for multiple turbo codes, in IEEE Vehicular Technology Conference (VTC Fall), pp. 2302-2306, September 2004
【非特許文献１９】S. Crozier, J. Lodge, P. Guinand, and A. Hunt, "Performance of turbo-codes with relative prime and golden interleaving strategies", in International Mobile Satellite Conference, pp. 268-275, 1999
【発明の開示】
【発明が解決しようとする課題】
【００３１】
本発明の課題は、ジグザグ符号のための、パフォーマンスを向上させた符号器および復号器を提供することにある。
【課題を解決するための手段】
【００３２】
上記課題は、請求項１に記載された符号器、請求項９に記載された符号化方法、請求項１１に記載された復号器、および請求項１２に記載された復号方法によって解決される。
【発明の効果】
【００３３】
本発明は、既存の通信システムをジグザグ符号化および復号化で複雑さをあまり高めることなく容易に拡張することができ、適正なインターリービング規則も既存のインターリーバから導出することができるという所見に基づく。例えば、インターリング規則は共通のマザーインターリーバから例えば巡回シフト、自己インターリービング、または行列の転置といったシンプルな操作によって生成することができる。これはマザーインターリーバまたはその構築規則のみが記憶される必要があるという利点をもたらす。任意のインターリーバ、例えばＵＭＴＳ（Universal Mobile Telecommunication System）仕様書［3GPP, "Turbo code internal interleaver", in 3G TS 25.212 V3.2.0 (2000-03), Release 1999, 2000］においてターボ符号用に仕様が定められたインターリーバがマザーインターリーバとして利用することができる。
【００３４】
ジグザグ符号化のためのいくつものインターリーバを得るため、ＵＭＴＳにおけるターボ符号用に仕様が定められたインターリーバの構築からの中間的なステップを使用することによって利点が得られる。これは、例えば、ジグザグ符号がオプションの符号化スキームとして導入される場合に、基本的構成要素、すなわちＵＭＴＳといったシステムにおいて利用可能なデインターリーバが再利用できるという利点をもたらす。このおかげで、ターボ符号およびジグザグ符号を同一のフレームワーク内で利用することができる。ジグザグ符号がターボ符号より多くのインターリーバを必要としても、両方の符号化スキームはインターリーバの構築に基本的構成要素を共用することができる。
【００３５】
本発明は、既存のインターリーバから追加のインターリーバを導出することができるため、ジグザグ符号とは異なる符号化スキームを利用するシステムを複雑さを高めることなくジグザグ符号で拡張することが可能であるという利点をもたらす。
【００３６】
以下、本発明の実施の最良の形態を添付図面を参照して詳細に説明する。
【発明を実施するための最良の形態】
【００３７】
図１に、入力情報語に基づいてこの入力情報語よりビット数が多い出力符号語を生成するための符号器１００を示す。符号器１００は、セグメンタ１１０、ジグザグ符号器コア（zigzag encoder core）１２０、インターリーバ１３０、および出力符号語コンストラクタ（output codeword constructor）１４０を具備する。
【００３８】
符号器１００は入力情報語を各セグメントがいくつかのビットを有する複数の順序付けされたセグメントに分割するためのセグメンタ１１０を備える。ジグザグ符号器コア１２０は今次のセグメントの冗長ビットを計算するようされている。今次のセグメントの冗長ビットを計算する際は今次のセグメントより順序が１つ先行するセグメントの冗長ビットが使用される。符号器１００は、第１のインターリービング規則を用いて前記複数のセグメントのビットをインターリーブして第１のインターリーブバージョン（first interleaved version）を得て、第２のインターリービング規則を用いて前記複数のセグメントのビットをインターリーブして第２のインターリーブバージョン（second interleaved version）を得るためのインターリーバ１３０を備える。またインターリーバ１３０は、第１のインターリービング規則を、所定数の一連の中間的なサブステップを実行することによって得られる所定のインターリービング規則として生成するよう設計されている。出力符号語コンストラクタ１４０は、入力符号語またはそのインターリーブバージョンと、第１のインターリーブバージョンの供給を受けてジグザグ符号器コア１２０によって生成された第１の冗長ビットの集合と、第２のインターリーブバージョンの供給を受けてジグザグ符号器コア１２０によって生成された第２の冗長ビットの集合とを使用して、出力符号語を生成するようにされている。インターリーバ１３０は、第２のインターリービング規則として、第１のサブステップもしくは前記所定数の一連のサブステップより少ないステップ数のサブステップを実行することによって得られる中間的なインターリービング規則またはこの中間的なインターリービング規則を（前記所定数の一連のサブステップに含まれる）残りのサブステップとは（比較して）異なる方法で処理することによって得られるインターリービング規則を使用するようされている。
【００３９】
符号器１００の実施形態は限定はされないがジグザグ符号器コア１２０を利用する。他の実施形態では、例えば畳み込み符号、ターボ符号、リードソロモンなど、他の符号器コアも利用することが可能であり、一般に全ての構成要素符号を想定することができる。冗長ビットを生成する任意の符号化コアは第１のインターリーブバージョンと第２のインターリーブバージョンに対して使用することができる。
【００４０】
実施の一形態において、所定のインターリービング規則はジグザグ符号器コア１２０が実行する符号化操作とは異なる符号化操作に対して最適化することができる。所定のインターリービング規則は例えば連結畳み込み符号またはターボ符号に対して最適化することが可能である。実施の一形態によれば、所定のインターリービング規則は、３ＧＰＰ（Third Generation Partnership Project）仕様書ＴＳ２５．２１２に仕様が定められたＵＭＴＳインターリーバに対応する。別の実施形態では、インターリーバ１３０は中間的なインターリービング行列の行列の転置または行もしくは列の交換に相当する中間的なインターリービング規則を処理するよう構成することができる。
【００４１】
図２は所定のインターリービング規則のブロック図である。所定のインターリービング規則は、第１のステップ２００、第２のステップ２１０、あるステップ数の中間ステップ、および最後のステップ２２０とを有する。これらのステップの系列は第１のインターリービング規則２３０をもたらし、この規則は例えば、入力情報符号語のインデックスをそのインターリーブ版入力情報符号語のインデックスに割り当てる行列の形で与えることが可能である。図２は第２のインターリービング規則２４０の決定も更に示している。この第２のインターリービング規則は例えば、第１のインターリービング規則２３０を導出するプロセスから第１のステップ２００後の中間結果を採取し、続いてオプション処理２５０を実行することによって得られる。オプション処理２５０は、中間的なインターリービング行列の転置、行方向もしくは列方向の読み出しを含むことができる。ここでの読み出しはランダムであることが可能である。つまり、行または列をランダムな順序で読み出しすることが可能である。図２に示した例は一例として第１のステップ２００後の中間結果を採取する。一般には、本発明の実施形態は、所定のインターリービング規則から任意の中間ステップを採取することができる。
【００４２】
図３に本発明の実施の一形態による復号器３００を示す。復号器３００は、入力符号語を復号し、入力符号語よりもビット数が少ない出力情報語を生成するためのもので、セグメンタ３１０、インターリーバ３２０、およびジグザグ復号器３３０を具備する。セグメンタ３１０は入力符号語を各セグメントが情報ビットおよび冗長ビットを有する複数の順序付けされたセグメントに分割するようされている。インターリーバ３２０は、第１のインターリービング規則を用いて前記複数のセグメントの情報ビットをインターリーブして第１のインターリーブバージョン情報ビットを得て、第２のインターリービング規則を用いて前記複数のセグメントの情報ビットをインターリーブして第２のインターリーブバージョン情報ビットを得る働きをする。またインターリーバ３２０は第１のインターリービング規則を所定数の一連の中間的なサブステップを実行することによって得られる所定のインターリービング規則として生成するよう設計されている。
【００４３】
ジグザグ復号器３３０は、情報ビット、第１のインターリーブバージョン情報ビット、第２のインターリーブバージョン情報ビット、および冗長ビットに基づいて出力情報語を計算するようされている。インターリーバ３２０は更に、第２のインターリービング規則として、第１のサブステップもしくは前記所定数の一連の中間的なサブステップより少ない（ステップ）数のサブステップを実行して得られる中間的なインターリービング規則、またはその中間的なインターリービング規則を（前記所定数の一連の中間的なサブステップに含まれる）残りのサブステップとは（比較して）異なる方法で処理することによって得られるインターリービング規則を使用するようされている。
【００４４】
実施の一形態によれば、前記所定のインターリービング規則はＵＭＴＳインターリーバに基づいており、それは並列連結畳み込み符号（ターボ符号）用に定義され、異なるインターリーバサイズに対して比較的シンプルな構築を可能にすると同時にターボ符号のイタレーションによる復号化におけるパフォーマンスに関して最適化される。それはターボ符号の最悪ケースパタン−ハミングウェイトがＷH＝２のデータ系列で２つの１ビットが３ビットの距離を有する場合、例えばｄ＝（０，．．．，０，１，０，０，１，０，．．．，０）が最も重大である−を回避するように設計される（非特許文献［D. Divsalar and F. Pollara, "Multiple turbo codes for deep-space communications," TDA Progress Report 42-121, May 1995］および非特許文献［T. Sohdoh, N. Nishinaga, and Y. Iwadare, "The new interleaver design of turbo codes for error floor improvement," in 20th Symposium on Information Theory and its Applications, pp. 13-16, December 1997］を参照）。これらのパタンはＵＭＴＳインターリーバによって壊される。つまり、それらは２つの１ビットが同じく３ビットの距離を有する系列にマップされない。
【００４５】
しかしながら、多重インターリーバの問題はこのインターリーバに関して議論されなかった。１つの実施形態は、ＵＭＴＳインターリーバの置換行列（permutation matrix）の転置を利用することによって第２のインターリーバを得て、ＵＭＴＳインターリーバ構築の中間的なステップにおいて置換規則（permutation rules）を読み出すことによって更なるインターリーバを得ることである。ＵＭＴＳインターリーバは図４に示すように数ステップで構築される。図４はデータ要素ｄ1，．．．，ｄRCのＲ×Ｃ行列を示している。第１のステップでは、図４のステップ１（図中１）に示すように、データビットが１行ずつＲ×Ｃ行列に書き込まれる。ＲおよびＣの値はインターリーバサイズに依存する。つまりそれらはＵＭＴＳ仕様書に与えられた設定（コンフィギュレーション）が異なれば変わる。次のステップとして、図４のステップ２（図中２）に示すように、所定の規則に従って行が交換される。この規則の詳細もＵＭＴＳ仕様書［3GPP, "Turbo code internal interleaver", in 3G TS 25.212 V3.2.0 (2000-03), Release 1999, 2000］に与えられている。第３のステップでは、図４のステップ３（図中３）に示すように、行内置換が行内部において実行される。そして最後のステップにおいて、図４のステップ４（図中４）に示すように、置換されたビットが１列ずつ読み出される。
【００４６】
本発明の実施形態は各ステップごとに行方向または列方向にその時々の置換規則を読み出すことによって多重インターリーバを生成することができる。例えば、各ステップ後に、すなわちデータを行列に書き込んだ後に、１列ずつ読み出すことで、ブロックインターリーバがもたらされる。ステップ２における行の交換の後、１列ずつまたは１行ずつ読み出すことによってインターリーバを得ることができて、これにより２つの追加のインターリーバが提供される。まさにこれと同じことを各行内置換ステップ後に実行することが可能である。当然、そうしたインターリーバの全てが良いパフォーマンスを示すわけではない。図５ａ〜図５ｈにインターリーバのグラフ表現を示す。図５ａ〜図５ｈの各図において、横座標は“ｉｎ”でラベルされた当初のデータ系列のインデックスを示しており、縦座標は“ｏｕｔ”でラベルされたインターリーブ後のデータのインデックスを表している。
【００４７】
図５ａはステップ１後のインターリーバを示しており、これは列方向に読み出される。結果のインターリーバはブロックインターリーバである。
【００４８】
図５ｂはステップ２後の同じインターリーバを示しており、これも列方向に読み出される。図５ａとの違いはそれぞれの列の開始インデックスの順番にある。
【００４９】
図５ｃは行１の行内置換後のインターリーバを示しており、これはＵＭＴＳインターリーバのステップ３で実行される。図５ｃに示すグラフは入力行列の行方向の読み出しの結果である。
【００５０】
図５ｄは同じインターリーバを示しているが、図５ｄのグラフは行列の列方向の読み出しの結果である。
【００５１】
図５ｅおよび図５ｆはＵＭＴＳインターリーバのステップ３における行６の行内置換後のインターリーバを示している。図５ｅは行方向の読み出しの結果のインターリーバを示すもので、図５ｆは列方向の読み出しの結果のインターリーバを示すものである。
【００５２】
図５ｇおよび図５ｈは完全な形のＵＭＴＳインターリービング規則が入力行列に適用された後の結果のインターリーバを示している。図５ｇは列方向に読み出すときの結果を示しており、図５ｈは行方向に読み出すときの結果を示している。
【００５３】
図５ａ〜図５ｈから、ＵＭＴＳインターリーバのプロットはほとんど一様に拡散していることが見て取れる。それに対し、ステップ１後の列方向に読み出した結果のブロックインターリーバはかなり構造化されていることが見て取れる。行方向の読み出しは、例として図５ｈまたは図５ｅに示したように、ＵＭＴＳインターリーバとは対照的に局所的にのみランダム化されたインターリーバを提供する。所定のＵＭＴＳインターリーバ構築のステップ３で行内置換がもっと実行されるほど、結果のインターリーバはもっと構造化されなくなる。
【００５４】
本発明の実施形態は斯かる中間的なインターリーバの拡散特性をシンプルな操作で改善することができる。１つの可能性は置換行列Πk自体ではなくそれぞれの置換行列の転置行列ΠkTを使用することである。実際、ΠTkはΠkに対応するデインターリーバである。それゆえ、この操作はΠkを直接使用するときと比べて更なる複雑さを課すものではない。双方向通信では、デインターリービング規則（deinterleaving rule）をいずれにしても決定する必要があるからである。インターリーバおよびデインターリーバの役割は交換可能である。イタレーションによる復号器はいずれにしてもインターリーバとデインターリーバを両方必要とする。転置された中間的なインターリーバの一部のグラフ表現を図５ａ〜図５ｈと同様の示し方で図６ａおよび図６ｂに示す。
【００５５】
図６ａはＵＭＴＳインターリーバの転置を示しているのに対し、図６ｂはステップ１におけるインターリーバ行列の列方向の読み出しの結果であるブロックインターリーバの転置を示している。この場合も同様に、図６ａおよび図６ｂから、図６ｂに示されたブロックインターリーバはかなり構造化されており、それに対して図６ａに示されたＵＭＴＳインターリーバの転置はランダム化されていることが見て取れる。図７ａおよび図７ｂは、図５ａ〜図５ｈと同様の示し方で、当初の中間的なインターリーバと、それらの転置を示している。当初のバージョンは○印で示されており、それらのそれぞれの転置は×印で示されている。
【００５６】
図７ａはＵＭＴＳインターリーバとその転置を示しているのに対し、図７ｂはステップ１と列方向の読み出しの結果であるブロックインターリーバとその転置を示している。興味深いことに、最終的なＵＭＴＳインターリーバでは、オリジナルバージョンとその転置は共に共通のマッピングをほとんど持たない。これは良好な相互独立性のヒントとなり、連結ジグザグ符号における適用可能性を示すものである。更なるランダム化のための別の方法がインターリーバが読み出される順序を変更する実施形態によって得られる。図８は実施形態がインターリーバをいかにして更にランダム化するかを示している。図８は既に述べたＲ×Ｃ行列を示しており、それは列方向に読み出されることを示しているが、しかしながら列は順番に読み出されず、ランダムな順序で読み出されることを示している。開始値もランダム化される。図８に示した例は列（Ｃ−２）（注：列Ｘといえば左からＸ番目の列、行Ｙといえば上からＹ番目の行という約束を用いる）が最初に読み出されることを示している。この列の読み出しは行３から始まり、列の最後の要素まで下降し、その後に上から１番目および２番目の要素が読み出される。第２のステップでは、列３が読み出される。この列の読み出しは上から２番目の要素から始まり、１番目の要素、最後の要素・・・といった具合に読み出される。
【００５７】
別の実施形態では、合同式インターリーバの置換規則が列が読み出される順序を決定するために利用される。例えば、Ｃを列の数とすることができ、このとき列が読み出される順序は次式に従って決定することができる。
【数１３】
2008136212.tif 000015
上式において、ｃc,kは各列が一度だけ読み出されることを保証するためにＣとは互いに素の整数でなければならない。ｓc,kは整数の開始値である。ｃc,kおよびｓc,kは両方ともランダムに選ぶことができ、インターリーバΠkが異なれば異なる必要がある。列Πc,k（ｉc）はｉc番目に読み出される。特殊なケースとしてｃc,k＝１はちょうど列が読み出される順序のｓc,kによる巡回シフトを与える。
【００５８】
別の実施形態では、列ｉcの読み出しが始まる行インデックスはランダムにまたは所定のルールに従って選ぶことができる。さらに、実施形態によっては、ある特定の列ｉcは、上方向に、つまり行インデックスの減少方向に、あるいは下方向に、つまり行インデックスの増加方向に、巡回式に読み出される。より改良されたインターリーバを実現するため、実施形態は修正された読み出しプロセスによって生成される全てもしくは一部のインターリーバの置換行列の転置を採用することができる。
【００５９】
一般に、任意の事前に定められたインターリービング規則またはインターリーバがそれぞれのインターリーバを導出または決定するために上記実施形態で使用することが可能である。
【００６０】
実施の一形態において、インターリーバΠkはΠ1を決定するために完全なＵＭＴＳインターリーバを使用することができる。Π2＝ΠT1はΠ1の転置として構築することができる。Π3については、図４のステップ１後にデータを１列ずつ読み出した結果のブロックインターリーバが使用されることがある。次のインターリーバΠ4は図４のステップ２における行の交換後の１列ずつの読み出しによって得られることがある。そうすることにより、共通のビットマッピングをほとんど持たないインターリーバが得られる。
【００６１】
図９に、パラメータがＩ＝２５６、Ｊ＝４、Ｋ＝４に設定されたジグザグ符号とＵＭＴＳインターリーバの中間物から構築されたインターリーバに対するパフォーマンスの結果を示す。図９のグラフは、完全な形のＵＭＴＳインターリーバ（full UMTS interleaver）と、インターリーバ構築における図５のステップ１後のブロックインターリーバ（block interleaver）のほかにそれらの転置と中間的なインターリーバとしてランダムに読み出されたバージョンを使用して決定された。最悪のパフォーマンスとなるのは、行方向に読み出されたＵＭＴＳインターリーバと図４のステップ１後のブロックインターリーバと一緒にＵＭＴＳインターリーバが使用されるときである。これはＵＭＴＳを行方向に読み出す際の不利な局所的な置換に起因するものである。同じ中間的なインターリーバが使用されるが既に提案したようにランダムに読み出される場合にパフォーマンスは大きく改善可能である。図９に示すように、最良のパフォーマンスはUMTS intermediate transpose randomly read outΠkで得られる。ＵＭＴＳインターリーバ、その転置、および図４のステップ１後のブロックインターリーバが使用されるときに、非常に良いパフォーマンスが得られる。この組み合わせのパフォーマンスはランダムに読み出すことによって更に若干改善することができる。このインターリービングスキームはｓランダム合同式インターリーバ（このビット誤り率も図９に与えられている）よりもパフォーマンスが優れている。ＵＭＴＳインターリーバの転置の代わりにステップ１後のブロックインターリーバを使用するときのパフォーマンスは３つの異なる中間的なインターリーバをランダムに読み出すときのパフォーマンスと似ている。
【００６２】
本発明の実施形態のおかげで、ＵＭＴＳターボ符号と比べても負けないくらいのパフォーマンスを発揮する複雑さが大きく低減した符号化スキームを、低コストで実現することができる。チップ面積とバッテリ消費量を減らすことが可能であり、復号器の高いスループットをもたらすことが可能である。本発明の実施形態は、例えば、低い複雑さと低い必要メモリをもたらすＵＭＴＳインターリーバの構築方法を利用することができる。唯１つのインターリーバ構築ルールが必要とされるだけで、その他のインターリーバに関しては、完全なインターリーバ構築の中間的なステップが利用できる。本発明の実施形態は更に、例えば、ターボ符号とジグザグ符号を同一のフレームワーク内で使用することができるという利点を提供する。
【００６３】
本発明の実施形態は、例えばＵＭＴＳターボ符号などのインターリーバ構成部を利用することができることから、経済的に実施することが可能である。新しい符号化スキームとしてジグザグ符号を導入するために既存システムに加える変更は本発明の実施形態によれば最小限に留まる。さらに、本発明の実施形態は、他の用途のために、例えばＩＤＭＡシステムにおけるマルチユーザ検出を改良するために、多重インターリーバを構築するために利用することが可能である。
【００６４】
本発明の方法の一定の実施要件に応じて、本発明の方法はハードウェアまたはソフトウェアで実施が可能である。本発明の実施は、本発明の方法が実行されるようにプログラマブルなコンピュータシステムと協働することができるデジタル記憶媒体、特に電子的に可読な制御信号が保存された磁気ディスク、ＤＶＤまたはＣＤを使用して行うことができる。一般に、本発明は従ってコンピュータ上で走らせたときに本発明の方法を実行する働きをするプログラムコードが機械可読媒体に記憶されたコンピュータ・プログラム製品である。言い換えると、本発明の方法は、コンピュータ上で走らせたときに本発明の少なくとも１つの方法を実行するためのプログラムコードを有するコンピュータ・プログラムである。
【図面の簡単な説明】
【００６５】
【図１】本発明の実施の一形態による符号器を示す図である。
【図２】本発明の実施の一形態による追加のインターリービング規則の導出手続きを示す図である。
【図３】本発明の実施の一形態による復号器を示す図である。
【図４】ＵＭＴＳインターリービング規則を示す図である。
【図５ａ】インターリービング規則の異なるサブステップを示す図である。
【図５ｂ】インターリービング規則の異なるサブステップを示す図である。
【図５ｃ】インターリービング規則の異なるサブステップを示す図である。
【図５ｄ】インターリービング規則の異なるサブステップを示す図である。
【図５ｅ】インターリービング規則の異なるサブステップを示す図である。
【図５ｆ】インターリービング規則の異なるサブステップを示す図である。
【図５ｇ】インターリービング規則の異なるサブステップを示す図である。
【図５ｈ】インターリービング規則の異なるサブステップを示す図である。
【図６】図６ａおよび図６ｂは、転置したインターリーバ出力の２つの例を示す図である。
【図７】図７ａおよび図７ｂは、インターリーバ出力およびその転置の更なる２つの例を示す図である。
【図８】本発明の実施の一形態によるインターリービング規則の更なるランダム化を示す図である。
【図９】修正された中間的なＵＭＴＳインターリービング規則で得られたビット誤り率を示す図である。
【図１０】先行技術によるジグザグ符号を示す図である。
【図１１】先行技術によるジグザグ符号器のブロック図である。
【図１２】ハミング距離が短いジグザグ符号化された符号語を示す図である。
【図１３】ジグザグ符号化された符号語の別の例を示す図である。
【図１４】先行技術による連結ジグザグ符号器を示す図である。
【図１５】インターリービング規則のビット誤り率性能をグラフで示した図である。
【図１６】先行技術による連結ジグザグ符号のための復号器を示す図である。
【図１７】先行技術による巡回シフトに基づくインターリーバを示す図である。
【符号の説明】
【００６６】
１００  符号器
１１０  セグメンタ
１２０  ジグザグ符号器
１３０  インターリーバ
１４０  符号語コンストラクタ
２００  第１のステップ
２１０  第２のステップ
２２０  最後のステップ
２３０  第１のインターリービング規則
２４０  第２のインターリービング規則
２５０  オプション処理
３００  復号器
３１０  セグメンタ
３２０  インターリーバ
３３０  ジグザグ復号器
【図１】
2008136212.tif 000016
【図２】
2008136212.tif 000017
【図３】
2008136212.tif 000018
【図４】
2008136212.tif 000019
【図５ａ】
2008136212.tif 000020
【図５ｂ】
2008136212.tif 000021
【図５ｃ】
2008136212.tif 000022
【図５ｄ】
2008136212.tif 000023
【図５ｅ】
2008136212.tif 000024
【図５ｆ】
2008136212.tif 000025
【図５ｇ】
2008136212.tif 000026
【図５ｈ】
2008136212.tif 000027
【図６】
2008136212.tif 000028
【図７】
2008136212.tif 000029
【図８】
2008136212.tif 000030
【図９】
2008136212.tif 000031
【図１０】
2008136212.tif 000032
【図１１】
2008136212.tif 000033
【図１２】
2008136212.tif 000034
【図１３】
2008136212.tif 000035
【図１４】
2008136212.tif 000036
【図１５】
2008136212.tif 000037
【図１６】
2008136212.tif 000038
【図１７】
2008136212.tif 000039
【外国語明細書】
2008136212.tif 000040
2008136212.tif 000041
2008136212.tif 000042
2008136212.tif 000043
2008136212.tif 000044
2008136212.tif 000045
2008136212.tif 000046
2008136212.tif 000047
2008136212.tif 000048
2008136212.tif 000049
2008136212.tif 000050
2008136212.tif 000051
2008136212.tif 000052
2008136212.tif 000053
2008136212.tif 000054
2008136212.tif 000055
2008136212.tif 000056
2008136212.tif 000057
2008136212.tif 000058
2008136212.tif 000059
2008136212.tif 000060
2008136212.tif 000061
2008136212.tif 000062
2008136212.tif 000063
2008136212.tif 000064
2008136212.tif 000065
2008136212.tif 000066
2008136212.tif 000067
2008136212.tif 000068
2008136212.tif 000069
2008136212.tif 000070
2008136212.tif 000071
2008136212.tif 000072
2008136212.tif 000073
2008136212.tif 000074
2008136212.tif 000075
2008136212.tif 000076
2008136212.tif 000077
2008136212.tif 000078
2008136212.tif 000079
2008136212.tif 000080
2008136212.tif 000081
2008136212.tif 000082
2008136212.tif 000083
2008136212.tif 000084