(57)【特許請求の範囲】
【請求項１】
ｍ次の原始多項式を使用してｎ個のデータストリームを符号化する第１帰還畳み込み符号器と、前記ｎ個のデータストリームをｋ個のデータグループに分けた後、ｋ個のデータグループからｎ個のデータストリームを読み出してインタリービングする２次元インタリーバと、ｍ次の前記原始多項式を使用して前記２次元インタリーバから前記インタリービングされたデータストリームを符号化する第２帰還畳み込み符号器とを含む符号化装置において、
前記ｋが２ｍ−１の正の倍数であり、前記データグループ中の少なくとも１つが特定のデータパターンを有するとき、前記２次元インタリーバの出力が前記特定のパターンとは相違であるように、データグループの選択を制御する制御器を含むことを特徴とする符号化装置。
【請求項２】
前記制御器は、それぞれの選択サイクルごと、データグループ選択順序を特定の値でシフトさせる請求項１に記載の符号化装置。
【請求項３】
前記特定のパターンは、一番目の‘１’とその次の‘１’との距離が２ｍ−１ビットの倍数であるシーケンスである請求項１に記載の符号化装置。
【請求項４】
ｍ個のメモリを有する帰還符号器と、ｇ（２ｍ−１の倍数）個のデータグループを有する２次元インタリーバと、所定のサイズのアドレスを有する各データグループとを含む通信システムのインタリービング方法において、
前記各データグループ内の前記アドレス中の一つを選択するデータグループ選択サイクルが２ｍ−１の倍数と同じではないようにアドレスを選択することを特徴とするインタリービング方法。
【請求項５】
データグループ選択順序は、それぞれの選択サイクルごと特定の値でシフトされる請求項４に記載のインタリービング方法。
【請求項６】
ｍ次の原始多項式を使用してｎ個のデータストリームを符号化する第１帰還畳み込み符号器と、前記ｎ個のデータストリームをｋ個のデータグループに分けた後、ｋ個のデータグループからｎ個のデータストリームを読み出してインタリービングする２次元インタリーバと、ｍ次の前記原始多項式を使用して前記２次元インタリーバから前記インタリービングされたデータストリームを符号化する第２帰還畳み込み符号器とを含む符号化装置において、
前記ｋが２ｍ−１の正の倍数であり、前記ｋ個のデータグループ中の特定の１つを選択した後、前記特定のデータグループを選択するサイクルが前記第１および第２帰還畳み込み符号器の周期と相異であるように、前記データグループの選択を制御する制御器を含むことを特徴とする符号化装置。
【請求項７】
前記制御器は、それぞれの選択サイクルごと特定の値でデータグループ選択順序をシフトする請求項６に記載の符号化装置。
【請求項８】
前記ｍは‘３’であり、前記第１および第２帰還畳み込み符号器の周期は、‘７’である請求項６に記載の符号化装置。
【請求項９】
ｍ次の原始多項式を使用してｎ個のデータストリームを符号化する第１帰還畳み込み符号器と、前記ｎ個のデータストリームをｋ個のデータグループに分けた後、ｋ個のデータグループからｎ個のデータストリームを読み出してインタリービングする２次元インタリーバと、ｍ次の前記原始多項式を使用して前記２次元インタリーバから前記インタリービングされたデータストリームを符号化する第２帰還畳み込み符号器とを含む符号化装置において、
前記ｋが２ｍ−１の正の倍数であり、前記ｋ個のデータグループ中の特定の１つを選択した後、前記特定のデータグループを選択するサイクルが前記２ｍ−１の倍数と同一ではないように、前記データグループの選択を制御する制御器を含むことを特徴とする符号化装置。
【請求項１０】
前記制御器は、選択サイクルごと特定の値でデータグループ選択順序をシフトさせて前記グループの選択を制御する請求項９に記載の符号化装置。
【請求項１１】
前記データグループ選択順序は、特定のパターンによりランダム化されたシーケンスである請求項１０に記載の符号化装置。
【請求項１２】
前記インタリーバは、
前記ｎ個のデータストリームを順次に貯蔵するメモリと、
前記ｋ個のデータグループのそれぞれに対して所定のインタリービングルールに従って読出しアドレスを生成するアドレス生成器と、
前記制御器の制御の下に所定の順序に従って前記データグループを選択し、前記選択されたデータグループから読出しアドレスを選択する選択器とを備え、
前記メモリは、前記選択器からの読出しアドレスを利用して前記ｎ個のデータストリームを出力する請求項９に記載の符号化装置。
【請求項１３】
ｍ次の原始多項式を使用してｎ個のデータストリームを符号化する第１帰還畳み込み符号器と、前記ｎ個のデータストリームをｋ個のデータグループに分けた後、ｋ個のデータグループからｎ個のデータストリームを読み出してインタリービングする２次元インタリーバと、ｍ次の前記原始多項式を使用して前記２次元インタリーバから前記インタリービングされたデータストリームを符号化する第２帰還畳み込み符号器とを含む符号化装置でのインタリーバのインタリービング方法において、
前記ｋが２ｍ−１の正の倍数であり、前記ｋ個のデータグループ中の特定の１つが選択された後、前記特定のグループを選択するサイクルが２ｍ−１の倍数と同じではないように前記データグループの選択を制御することを特徴とするインタリービング方法。
【請求項１４】
選択周期ごと特定の値でデータグループ選択順序をシフトさせて前記データグループの選択を制御する請求項１３に記載の符号化方法。
【請求項１５】
前記データグループ選択順序は、特定のパターンによってランダム化されたシーケンスである請求項１４に記載の符号化方法。
【請求項１６】
ｍ次の原始多項式を使用してｎ個のデータストリームを符号化する第１帰還畳み込み符号器と、前記ｎ個のデータストリームをｋ個のデータグループに分けた後、ｋ個のデータグループからｎ個のデータストリームを読み出してインタリービングする２次元インタリーバと、ｍ次の前記原始多項式を使用して前記２次元インタリーバから前記インタリービングされたデータストリームを符号化する第２帰還畳み込み符号器とを含む符号化装置における前記インタリーバのインタリービング方法において、
入力された前記ｎ個のデータストリームをメモリに順次に貯蔵するステップと、
所定のインタリービングルールに従って読出しアドレスを生成するステップとからなり、前記インタリービングルールは、
前記ｋが２ｍ−１の正の倍数であり、前記ｋ個のデータグループ中の特定の１つを選択した後、前記特定のデータグループを選択する周期が２ｍ−１の倍数と同じではないように前記データグループの選択を制御し、前記読出しアドレスを利用して前記入力データを前記メモリから読み出すことを含むことを特徴とするインタリービング方法。
【請求項１７】
毎周期ごと特定の値でデータグループ選択順序をシフトさせて前記グループの選択を制御する請求項１６に記載のインタリービング方法。
【請求項１８】
前記データグループ選択順序は、特定のパターンによってランダム化されたシーケンスである請求項１７に記載の符号化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、インタリービング／デインタリービング装置及び方法に関し、特に、衛星システム、ＩＳＤＮ（Ｉｎｔｅｇｒａｔｅｄ Ｓｅｒｖｉｃｅｓ Ｄｉｇｉｔａｌ Ｎｅｔｗｏｒｋ）、ディジタルセルラー（Ｄｉｇｉｔａｌ ｃｅｌｌｕｌａｒ）、Ｗ−ＣＤＭＡ（Ｗｉｄｅｂａｎｄ Ｃｏｄｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ）、ＩＭＴ−２０００、Ｗ−ＡＴＭ（Ｗｉｄｅｂａｎｄ Ａｓｙｎｃｈｒｏｎｏｕｓ Ｔｒａｎｓｆｅｒ Ｍｏｄｅ）通信システムのような無線通信システムで使用されるターボ符号器のための２次元インタリービング／デインタリービング装置及び方法に関する。
【０００２】
【従来の技術】
一般に、ターボ符号は、ディジタル通信システムの信頼度に影響する誤り訂正符号の１つの種類である。通常、ターボ符号は、並列ターボ符号と直列ターボ符号とに区分される。並列ターボ符号器（ｐａｒａｌｌｅｌ ｔｕｒｂｏ ｅｎｃｏｄｅｒ）は、Ｌ個の情報ビットストリームの入力フレームを２個の簡単な並列鎖状符号（ｐａｒａｌｌｅｌ ｃｏｎｃａｔｅｎａｔｅｄ ｃｏｄｅ）を利用してパリティーシンボル（ｐａｒｉｔｙ Ｓｙｍｂｏｌ）に符号化し、ここで、ＲＳＣ（Ｒｅｃｕｒｓｉｖｅ Ｓｙｓｔｅｍａｔｉｃ Ｃｏｎｖｏｌｕｔｉｏｎａｌ）符号器は、一般的に、構成符号器（ｃｏｍｐｏｎｅｎｔ ｅｎｃｏｄｅｒ）として利用される。また、前記並列ターボ符号器は、前記構成符号器の間に連結されたインタリーバを含んでいる。
【０００３】
前記ターボ符号器において、フレーム単位に基づいてデータストリームをランダム化（ｒａｎｄｏｍｉｚａｔｉｏｎ）し、コードワード（ｃｏｄｅｗｏｒｄ）の距離特性（ｄｉｓｔａｎｃｅ ｐｒｏｐｅｒｔｙ）を改善するためにインタリービングが遂行される。特に、前記ターボ符号器は、ＥＴＳＩ（Ｅｕｒｏｐｅａｎ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｔａｎｄａｒｄｓ Ｉｎｓｔｉｔｕｔｅ）が提案したように、ＩＭＴ−２０００（またはＣＤＭＡ−２０００）通信システムの付加チャンネル（Ｓｕｐｐｌｅｍｅｎｔａｌ Ｃｈａｎｎｅｌ）（またはトラヒックチャンネル（ｔｒａｆｆｉｃ ｃｈａｎｎｅｌ））及びＵＭＴＳ（Ｕｎｉｖｅｒｓａｌ Ｍｏｂｉｌｅ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓｔｅｍ）のデータチャンネルで使用される。従って、このようなターボ符号器のためのターボインタリーバを実現するための確実な方法が要求されている。
【０００４】
図１は、一般的な並列ターボ符号器の構造を示し、１９９５年８月２９日付登録された米国特許第５，４４６，７４７号にはターボ符号について詳細に開示されている。
【０００５】
図１を参照すると、前記ターボ符号器は、入力フレームデータを符号化する第１構成符号器１１１と、前記入力フレームデータをインタリービングするインタリーバ１１２と、前記インタリーバ１１２の出力を符号化する第２構成符号器１１３とからなる。前記第１構成符号器１１１及び第２構成符号器１１３は、一般的に、既知のＲＳＣ符号器またはＮＳＣ（Ｎｏｎ−Ｒｅｃｕｒｓｉｖｅ Ｓｙｓｔｅｍａｔｉｃ Ｃｏｎｖｏｌｕｔｉｏｎａｌ）符号器を使用する。このような構成符号器は、符号化率、拘束長さＫ、及び生成多項式に従って異なる構成を有する。そして、前記インタリーバ１１２は、入力情報ビットフレームと同一なサイズを有し、前記第２構成符号器１１３に入力される情報ビットのシーケンスを再整列することにより情報ビット間の相関（ｃｏｒｒｅｌａｔｉｏｎ）を減少させる。
【０００６】
前記ターボ符号器の内部インタリーバ（ｉｎｔｅｒｎａｌ ｉｎｔｅｒｌｅａｖｅｒ）（またはターボインタリーバ）１１２の場合、ＰＮ（Ｐｓｅｕｄｏ Ｎｏｉｓｅ）ランダムインタリーバ（ｒａｎｄｏｍ ｉｎｔｅｒｌｅａｖｅｒ）、ランダムインタリーバ、ブロックインタリーバ（ｂｌｏｃｋ ｉｎｔｅｒｌｅａｖｅｒ）、非線形インタリーバ（ｎｏｎ−ｌｉｎｅａｒ ｉｎｔｅｒｌｅａｖｅｒ）、及びＳランダムインタリーバなどの多様なインタリーバが提案される。しかし、このようなインタリーバは、これまでは実現より学問的な研究分野という観点で、性能改善のために設計された単純なアルゴリズムである。従って、実際のシステムの実現にあっては、ハードウェアの実現複雑度という側面を考慮に入れておかなければならない。以下、従来なターボ符号器のインタリーバに関する特性及び問題点を説明する。
【０００７】
ターボ符号器の性能は、内部インタリーバによって左右される。一般的に、入力フレームサイズ（すなわち、１つのフレームに含まれた情報ビットの個数）が増加すると、前記ターボ符号器の性能が増加する。しかし、インタリーバサイズの増加に従って計算量が増加するので、一般的に、フレームサイズが大きすぎる場合、インタリーバの実現が実質的に不能である。
【０００８】
実験結果によると、性能面において、ランダムインタリーバがブロックインタリーバより優れる。しかし、ランダムインタリーバの短所は、フレームの多様性及びサイズが増加するに従ってインタリーバのインデックス（すなわち、マッピングルール（ｍａｐｐｉｎｇ ｒｕｌｅ）またはアドレス）を貯蔵するための必要なメモリ容量が増加することである。すなわち、アドレッシングのために必要なメモリ容量が非常に増加するようになる。従って、必要なハードウェアのサイズを考慮して、インタリーバのインデックスを貯蔵するルックアップテーブル（Ｌｏｏｋ−Ｕｐ Ｔａｂｌｅ）方式よりは、インデックスを発生させるルールを利用して毎シンボルクロックごとアドレスを発生させて該当アドレスに貯蔵されたデータを読み出すアドレス計算（ｅｎｕｍｅｒａｔｉｏｎ）方式が望ましい。
【０００９】
結論的に、ＩＭＴ−２０００またはＵＭＴＳシステムのように多様なインタリーバサイズが要求され、ハードウェアの複雑度が制限される場合、前記ターボインタリーバは、このような制限的な条件を考慮して最適なインタリーバ性能が保証されるように設計されなければならない。すなわち、特定のインタリービングルールに従ってインタリービング／デインタリービングを遂行するインタリーバを必要とする。また、前記ターボインタリーバは、優秀なインタリーバの特性が要求される（例えば、距離特性、ウェイト特性、及びランダム特性）。
【００１０】
ＩＭＴ−２０００またはＵＭＴＳスペックにおいて、ターボインタリーバに対しては明確に定義されていない。ＩＭＴ−２０００スペックの定義した順方向リンク（ｆｏｒｗａｒｄ ｌｉｎｋ）及び逆方向リンク（ｒｅｖｅｒｓｅ ｌｉｎｋ）は、多様なタイプの論理チャンネル（ｌｏｇｉｃａｌ ｃｈａｎｎｅｌ）及び多様なインタリーバサイズを有する。従って、このような多様な要件を充足させるためには、メモリ容量の増加が要求される。例えば、ＣＤＭＡ−２０００の順方向リンク伝送モードにおいて、１４４ビット／フレームから３６８６４ビット／フレームにわたる多様なサイズのインタリーバが使用されることができる。また、前記インタリーバは、入力フレームの全体を１つの領域と見なしてインタリービングを遂行する１次元インタリーバと入力フレームを幾つかの部分領域に分けた後、前記分けられた領域に従ってインタリービングを遂行する２次元インタリーバに区分できる。
【００１１】
このように従来技術の問題点は次のように要約される。
【００１２】
一番目、前記ターボ符号器の内部インタリーバの場合、ＰＮランダムインタリーバ、ランダムインタリーバ、ブロックインタリーバ、非線形インタリーバ、及びＳランダムインタリーバなどが使用されることができる。しかし、このようなインタリーバは、実現より学問的な研究分野という観点で、性能改善のために設計された単純なアルゴリズムである。従って、実際のシステムの実現にあっては、そのようなインタリーバのハードウェアの実現複雑度という側面を考慮に入れておかなければならないが、これに関しては具体的に定義されていない。
【００１３】
二番目、送受信器の制御部（ＣＰＵまたはホスト）は、ルックアップテーブルを利用した既存のインタリービング方式において、それぞれのインタリーバサイズに従うインタリービングルールを貯蔵しておかなければならないので、ホストメモリは、インタリーババッファの以外に別途の容量を必要とする。すなわち、フレームサイズが多様であり増加するほど、インタリーバのインデックス（すなわち、マッピングルールまたはアドレス）を貯蔵するためのメモリ容量が増加する。すなわち、メモリ容量がかなり増加する問題点があった。
【００１４】
三番目、距離特性及びランダム特性を同時に満足するインタリーバの実現が容易ではなかった。
【００１５】
四番目、２次元インタリーバを使用するとき、構成符号器の周期性を考慮せず領域を選択するので、構成符号器の状態をリセットさせる問題があった。
【００１６】
【発明が解決しようとする課題】
従って、本発明の目的は、通信システムにおいてターボ符号器の距離特性（ｄｉｓｔａｎｃｅ ｐｒｏｐｅｒｔｙ）が最大化できるインタリービング／デインタリービング装置及び方法を提供することにある。
【００１７】
本発明の他の目的は、ターボ符号器のインタリーバが入力フレームデータを特定のサイズに分割してインタリービングするターボ符号器に対するインタリービング装置及び方法を提供することにある。
【００１８】
本発明のまた他の目的は、特定のグループを選択する周期がターボ符号器内の構成符号器の周期と相異であるように、グループ選択を制御する２次元インタリービング装置及び方法を提供することにある。
【００１９】
【課題を解決するための手段】
前記のような目的を達成するために、符号化装置は、ｍ次の原始多項式を使用してｎ個のデータストリームを符号化する第１帰還畳み込み符号器と、前記ｎ個のデータストリームをｋ個のデータグループに分けた後、ｎ個のデータストリームデータグループをインタリービンし、ｋ個のデータグループからｎ個のデータストリームを読み出してインタリービングする２次元インタリーバと、ｍ次の前記原始多項式を使用して前記２次元インタリーバから前記インタリービングされたデータを符号化する第２帰還畳み込み符号器とを含む。前記符号化装置は、前記ｋが２ｍ−１の正の倍数であり、前記データグループ中の少なくとも１つが特定のデータパターンを有するとき、前記２次元インタリーバの出力が前記特定のパターンとは一致しないように、データグループの選択を制御する制御器を構成することを特徴とする。
【００２０】
【発明の実施の形態】
以下、本発明に従う好適な実施形態を添付図面を参照しつつ詳細に説明する。下記説明において、本発明の要旨のみを明瞭にするために公知の機能及び構成に対する詳細な説明は省略する。
【００２１】
多様なフレームサイズに対して最適の性能を有するターボ符号器を設計するためには、ターボ符号器の構成符号器に対するメモリ個数（すなわち、拘束長さＫ）、生成多項式、及び最適の符号化率などのような多数のパラメータが考慮されなければならない。このようなすべてのパラメータがその性能にどのように影響にするかが検証されない状態では、実験を通じて最適の性能を有するターボ符号器を設計することは非常に難しい。
【００２２】
従って、一般的に、インタリーバは、幾つかの所定の基準を満足させる条件を決定することにより実現される。その基準は次のようである。
【００２３】
距離特性（Ｄｉｓｔａｎｃｅ Ｐｒｏｐｅｒｔｙ）：隣接したコードワードドシンボル間の距離をある程度まで保持すべきである。これは、畳み込み符号のコードワードの距離特性と同一の機能を有するので、できるだけ距離が大きくなるようにインタリーバを設計することが望ましい。
ウェイト特性（Ｗｅｉｇｈｔ Ｐｒｏｐｅｒｔｙ）：ゼロではない情報語（Ｎｏｎ−ｚｅｒｏ ｉｎｆｏｒｍａｔｉｏｎ ｗｏｒｄ）に対応するコードワードのウェイトがしきい値より高くなければならない。これは、畳み込み符号の最小距離（ｍｉｎｉｍｕｍ ｄｉｓｔａｎｃｅ）の特性と同一の機能を有するので、できるだけウェイトが大きくなるようにインタリーバを設計することが望ましい。
ランダム特性（Ｒａｎｄｏｍ Ｐｒｏｐｅｒｔｙ）：インタリービング以後の出力ワードシンボル間の相関係数がインタリービング以前の元来入力語シンボル（ｏｒｉｇｉｎａｌ ｉｎｐｕｔ ｗｏｒｄ ｓｙｍｂｏｌ）間の相関係数（ｃｏｒｒｅｌａｔｉｏｎ ｆａｃｔｏｒ）よりかなり低くなければならない。すなわち、出力ワードシンボル間のランダム化が充実に行わなければならない。これは、連続デコーディングで発生した外部情報（Ｅｘｔｒｉｎｓｉｃ ｉｎｆｏｒｍａｔｉｏｎ）の品質に直接的な影響を与える。
【００２４】
以下、本発明の好適な実施形態を添付図面を参照しつつ詳細に説明する。
【００２５】
本発明は、前記ターボインタリーバの特性（距離特性、ウェイト特性、及びランダム特性など）が満足できる最適のインタリービング／デインタリービング装置を提案する。
【００２６】
一般的に、ターボ符号器の内部インタリーバとして、ランダムインタリーバは優秀な性能を有する。特に、フレームサイズが大きくなるほど優秀な性能に優れる。従って、本発明は、ランダムインタリーバの性能を満足させつつ複雑度が改善できるように２次元（２−ｄｉｍｅｎｓｉｏｎａｌ）インタリーバを提案する。前記２次元インタリーバは、入力フレームのサイズを複数のグループに分割し、グループに従って特定のインタリービングルールを適用する。特定のグループが選択されたときと同一の特定のグループが連続的に選択されたときとの周期として定義されたグループ選択周期は、内部構成符号器の周期と一致してはいけない。また、本発明の実施形態では、各グループにＰＮシーケンスを生成する線形帰還シフトレジスタ（ＬＦＳＲ：Ｌｉｎｅａｒ Ｆｅｅｄｂａｃｋ Ｓｈｉｆｔ Ｒｅｇｉｓｔｅｒ）を適用させ、前記ＬＦＳＲから生成されたランダム数（Ｒａｎｄｏｍ Ｎｕｍｂｅｒ）を読出しアドレスとして使用する。しかし、本発明は、グループ単位でインタリービングを遂行する方法に限定されることではなく、構成符号器の周期性を考慮して各グループ別に生成されたアドレスを選択することを旨とする。また、本発明に従うターボ符号器の第１及び第２構成符号器は、従来技術の構成符号器だけではなく、ＣＤＭＡ２０００及びＵＭＴＳスペックが明示した構成符号器も使用できる。さらに、本発明に従うインタリーバは、直列ターボ符号器の内部インタリーバのみならずチャンネルインタリーバなどにも適用できる。
【００２７】
図２及び図３は、本発明に従うインタリーバ及びデインタリーバの構造をそれぞれ示す。
【００２８】
図２を参照して、フレームデータ入力をインタリービングするインタリーバを説明する。アドレス生成器２１１は、入力フレームデータサイズＬ及び入力クロックに従ってデータビットのシーケンスを再整列するための読出しアドレスを生成してインタリーバメモリ２１２へ出力する。前記インタリーバメモリ２１２は、書込み動作モードのとき入力データを順次的に貯蔵し、読出し動作モードのとき前記アドレス生成器２１１から提供されるアドレスに従ってデータを読み出す。入力クロックを受信するカウンタ２１３は、前記インタリーバメモリ２１２に書込みアドレスを提供する。前述したように、前記インタリーバは、書込み動作モードのとき前記インタリーバメモリ２１２に入力データを順次的に貯蔵し、読出し動作モードのとき前記アドレス生成器２１１が生成した読出しアドレスに従って前記インタリーバメモリ２１２に貯蔵されたデータを読み出す。代わりに、前記インタリーバは、書込み動作モードのときデータビットのシーケンスを再整列した後、前記インタリーバメモリ２１２に入力データが貯蔵でき、読出し動作モードのときデータを順次的に読み出す。
【００２９】
図３を参照して、本発明の実施形態によるデインタリーバを説明する。アドレス生成器３１１は、入力フレームデータサイズＬ及び入力クロックによって入力データのシーケンスを元来の状態に復元するための書込みアドレスを生成してデインタリーバメモリ３１２へ提供する。前記デインタリーバメモリ３１２は、書込み動作モードのとき前記アドレス生成器３１１から提供された書込みアドレスに従って入力データを貯蔵し、読出し動作モードのとき前記貯蔵されたデータを順次的に読み出す。シンボルクロックを受信するカウンタ３１３は、前記デインタリーバメモリ３１２からデータを読み出すための読出しアドレスを前記デインタリーバメモリ３１２に提供する。前述したように、前記デインタリーバは、前記インタリーバの逆動作を有するが、前記インタリーバと同一の構造を有する。ただ、読出しモード及び書込みモードのとき入力されるデータビットのシーケンスが異なる。従って、以下インタリーバのみを参照して説明する。
【００３０】
一般的に、所定の入力フレームサイズに対して、ターボ符号器の性能は、拘束長さＫ及びターボインタリーバの特性によって決定される。復号器の設計のとき、前記拘束長さＫは、複雑度及び所望の性能向上を考慮して３または４に設定される。例えば、ＣＤＭＡ−２０００及びＵＭＴＳシステムの場合、拘束長さＫは、通常４（Ｋ＝４）に設定される。これに反して、ターボインタリーバ（すなわち、ターボ符号器のインタリーバ）の場合、あんまり多い設計パラメータが存在するから、最適なターボインタリーバを得られる特性を選択することが非常に難しくなる。従って、最適のターボインタリーバよりむしろ、サブオプチマル（ｓｕｂ−ｏｐｔｉｍａｌ）のターボインタリーバを利用した研究が活発に進行している。
【００３１】
まず、畳み込み符号の特性を分析する必要がある。一般的な畳み込み符号の場合、入力シーケンスＩのハミングウェイト（Ｈａｍｍｉｎｇ Ｗｅｉｇｈｔ）Ｗ（Ｉ）が低い場合コードのウェイトも低い。反面、ハミングウェイトＷ（Ｉ）が高い場合コードのウェイトも高い。これは、正方向（ｆｅｅｄ ｆｏｒｗａｒｄ）畳み込み符号の特性による。畳み込み符号とは異なり、再帰的畳み込み符号を利用するターボ符号は、無限インパルス応答シーケンス（ｉｎｆｉｎｉｔｅ ｉｍｐｕｌｓｅ ｒｅｓｐｏｎｓｅ ｓｅｑｕｅｎｃｅ）を有する。すなわち、Ｋ＝４の場合、１０００００…０の入力シーケンスを使用すると、周期が７である構成符号シーケンス（ｃｏｍｐｏｎｅｎｔ ｃｏｄｅ ｓｅｑｕｅｎｃｅ）を生成する。
【００３２】
図１は、ターボ符号器の構成を示す。示したように、前記ターボ符号器内に備えられるターボインタリーバは、再帰的畳み込み符号器ＲＣＥ（ｒｅｃｕｒｓｉｖｅ ｃｏｎｖｏｌｕｔｉｏｎａｌ ｅｎｃｏｄｅｒ）を使用する２つの構成符号器の間に連結される。前記ターボインタリーバは、第１符号器が低いウェイトを有する符号を生成する場合、第２符号器が高いウェイトを有する符号を生成できるように入力データのインタリービングを遂行する。従って、前記第１符号器から出力される符号が低いウェイトを有するとしても、第２符号器から出力される符号は、高いウェイトを有する。これにより、全体符号のウェイトが増加させられる。例えば、入力シーケンス１０００００…０がＫ＝４であるターボ符号器に入力される場合、ターボ符号器内の各構成符号器は、周期が２（ｋ−１）−１＝７である周期性を有する２進シーケンス（ｐｅｒｉｏｄｉｃ ｂｉｎａｒｙ ｓｅｑｕｅｎｃｅ）を生成する。このようなシーケンスのパターンは、ターボ符号器の生成多項式（ｇｅｎｅｒａｔｏｒ ｐｏｌｙｎｏｍｉａｌ）と関連がある。また、ゼロシーケンス符号器ではない特定の入力シーケンスに対して、構成符号器の状態をゼロ状態にリセットすることにより有限符号シーケンス（ｆｉｎｉｔｅ ｃｏｄｅ ｓｅｑｕｅｎｃｅ）が生成できる。
【００３３】
例えば、Ｋ＝４の場合、１００００００１０００００００００…である入力シーケンスに対して、２番目‘１’ビットを符号化した後、第１構成符号器の状態をゼロ状態にリセットする。また、周期性のため、２つの‘１’間の距離が７の倍数であるすべての場合、第１符号器の状態を同様の方式にてリセットする。従って、その後続する符号のすべてはゼロになり、ターボ符号の最小距離（ｍｉｎｉｍｕｍ ｄｉｓｔａｎｃｅ）を減少させる。このような場合、前記ターボインタリーバは、入力シーケンスのパターンをブレーク（ｂｒｅａｋ）することにより、第２構成符号器はより高い符号ウェイトを有し、これにより、前記ターボ符号器の最小ウェイトを増加させる。
【００３４】
このようなターボインタリーバは、設計方法に従って、１次元ターボインタリーバ及び２次元ターボインタリーバに分けられる。前記１次元インタリーバは、全体のフレームを１つの対象としてインタリービングされるようにする点でインタリービングを遂行する。前記２次元インタリーバは、全体のフレームを同一のサイズを有するサブフレーム（ｓｕｂ−ｆｒａｍｅ）または複数のグループに分割した後、それぞれのグループが該当するインタリービングルールを使用してインタリービングを独立的に遂行する。一般的に、２次元ターボインタリーバは、１次元ターボインタリーバの性能に比べて優れ、また、それぞれのグループに従ってインタリービングルールを有し、これにより、１次元ターボインタリーバの場合に比べて単純な最適化過程を提供する。
【００３５】
図４は、２次元ターボインタリーバの動作原理を説明する図である。図４を参照すると、入力フレームは、ｇｒｏｕｐ０、ｇｒｏｕｐ１、ｇｒｏｕｐ２、ｇｒｏｕｐ３の４つのグループに分割される。Ｐ０（ｋ）は、前記ｇｒｏｕｐ０のデータをインタリービングするためのインタリービングルールを示し、Ｐ１（ｋ）は、前記ｇｒｏｕｐ１のデータをインタリービングするためのインタリービングルールを示し、Ｐ２（ｋ）は、前記ｇｒｏｕｐ２のデータをインタリービングするためのインタリービングルールを示し、Ｐ３（ｋ）は、前記ｇｒｏｕｐ３のデータをインタリービングするためのインタリービングルールを示す。また、Ｐ０（０）、Ｐ１（０）、Ｐ２（０）、及びＰ３（０）は、前記ｋが‘０’であるとき各グループでインタリービングされたデータのアドレスを示し、Ｐ０（１）、Ｐ１（１）、Ｐ２（１）、及びＰ３（１）は、前記ｋが‘１’であるとき、各グループでインタリービングされたデータのアドレスを示す。Ｐ０（２）、Ｐ１（２）、Ｐ２（２）、及びＰ３（２）は、前記ｋが‘２’であるとき各グループでインタリービングされたデータのアドレスを示す。Ｐ０（３）、Ｐ１（３）、Ｐ２（３）、及びＰ３（３）は、前記ｋが‘３’であるとき各グループでインタリービングされたデータのアドレスを示す。すなわち、毎時点ｋで、それぞれのグループに該当するインタリービングルールＰｇ（ｋ）によってそれぞれのグループから１つのデータビットを読み出す。これは、１次元インタリービングに対する自然な拡張であると見なすことができる。もちろん、このようなグループは、順次的にまたは特定のルールに従って選択されることができる。例えば、図４に示すように、前記グループは、０，１，２，及び３の順序ではなく、全体のインタリービングルールを変更することによって、０，２，１，及び３の順序で選択されることができる。すなわち、図４は、前記入力フレームのデータビット数が１６個であり、前記入力フレームをそれぞれ４ビットを有する４つのグループに分割して、それぞれのグループが関連するインタリービングルールによってインタリービングされる場合を示す。
【００３６】
このような２次元ターボインタリービングを遂行する場合問題点が発生できる。すなわち、グループ数が構成符号器の周期または周期の倍数と同一である場合、ターボ符号の最小距離を大きく減少させる。例えば、ｋ＝４の場合周期が７であるので、グループ数が７または７の倍数であれば、それぞれの構成符号器をゼロ状態にリセットする可能性がある。
【００３７】
図５は、ターボ符号器の入力シーケンス１００００００１００００…が、インタリービングの後にもそのまま保持される最悪の場合を示す。示したように、前記入力シーケンスのパターンがインタリービングされた後もそのまま保持される。従って、第２構成符号器もゼロ状態でリセットされ、その結果、ターボ符号の最小ウェイトが減少する。これは、グループ数が７の倍数であるすべての場合に該当する。多くの場合、最小距離は、グループ数が７または１４の場合発生する。結局、ターボインタリーバは、最小距離が非常に短くなって、ターボ符号の全体のＢＥＲ（Ｂｉｔ Ｅｒｒｏｒ Ｒａｔｅ）またはＦＥＲ（Ｆｒａｍｅ Ｅｒｒｏｒ Ｒａｔｅ）の性能を低下させる。
【００３８】
従って、２次元ターボインタリーバを設計するとき前述した問題点を解決するために、本発明は、グループ選択周期、同一のグループの連続的な選択周期がターボ符号器内の構成符号器の周期と相違であるようにグループ選択パターンを変更する。すなわち、本発明は、２次元ターボインタリーバがグループ選択を遂行する場合、ターボ符号器の特性を分析してターボ符号の最小距離を最大化することを旨とする。
【００３９】
以下、本発明の実施形態に従う前記ターボ符号の最小距離を最大化するターボインタリービング装置について詳細に説明する。
【００４０】
グループ選択の周期性をブレーキングする一番効率的な方式は、前記グループを毎周期ごとに最初に選択されるように変更させることである。下記［表１］は、ｋ＝４であり、グループ数が７の場合、このような方式の例を示す。下記［表１］は、循環シフトに基づいてグループ選択が順次的に行われることを示すものであっても、グループ選択が所定のパターンに従って循環シフトに基づいてランダムに行われることも可能である。
【表１】
0003574405.tif 000002
【００４１】
例えば、［表１］において、シフトステップ（ｓｈｉｆｔ ｓｔｅｐ）が２の場合、第１周期では、“０１２３４５６”の順序を利用してグループを選択し、第２周期では、前記第１周期でのグループ選択順序を２だけシフトさせた“２３４５６０１”の順序を利用してグループを選択する。すなわち、左から右へ“２”だけ移動させる［表１］に示すように、すべてのグループ選択周期ごと、以前のグループ選択順序を２だけシフトさせて決定されたグループ選択順序でグループを選択する。［表１］に示すように、循環シフト方式にてグループを選択する場合、特定のグループ選択順序は、７回の異なるグループ選択順序が行われた後に反復するので、最小距離を増加させる。すなわち、シフトステップが０の場合、前記グループ選択パターンは、毎周期ごと以前のパターンと同一のパターンを有する。しかし、シフトステップが１，２，３，４，５，及び６の場合、特定のグループ選択パターンは、７回の異なるグループ選択パターンが循環された後発生する。すなわち、前記グループ選択順序は、循環シフトによって変更され、その結果、前記ターボ符号器の周期が循環シフト順序とは異なるようになる。
【００４２】
このような循環シフト方式のグループ選択は、簡単に実現されることができる。それぞれのグループ選択は、下記［数式１］のように求められる。
［数式１］
ｇ ＝ （ｃｌｋ％Ｎｇ ＋ ｓｈｉｆｔ＿ｓｔｅｐ＊ｋ）％ＮＧ  ｆｏｒ ｃｌｋ＝０， … ，ｆｒａｍｅ＿ｌｅｎｇｔｈ−１
【００４３】
例えば、Ｎｇ＝７、ｓｈｉｆｔ＿ｓｔｅｐ＝１である場合、ｋ＝０，０，０，０，０，０，０｜１，１，１，１，１，１，１｜．．．になり、ｃｌｋが０，１，２，３，４，５，６，｜７，８，９，１０，１１，１２，１３｜．．．になる場合、それに従って、ｇ＝０，１，２，３，４，５，６｜１，２，３，４，５，６，０｜．．．．になる。
ここで、Ｎｇはグループ数、ｃｌｋはビット単位のデータクロックを意味する一種のカウンタ、ｋは０（ｋ＝０）に初期化されるカウンタであり、初めに選択されるグループの順序を毎Ｎｇグループが選択されるときごと１ずつ増加させる。また、ｓｈｉｆｔ＿ｓｔｅｐは、ＧＣＤ（２Ｋ−１、ｓｈｉｆｔ＿ｓｔｅｐ）＝１を満足する所定の数であり、拘束長さＫに依存する常数である。すなわち、２つのカウンタ及び１つのアドレス加算器を利用して循環シフト方式が実現できる。
【００４４】
グループ選択順序が順次的に増加する場合の循環グループシフト方式を参照して説明したが、ターボインタリーバの距離特性を増加させるためには、それぞれのグループからインタリービングアドレス（ｉｎｔｅｒｌｅａｖｉｎｇ ａｄｄｒｅｓｓ）をランダムに出力することができる。
【００４５】
例えば、ｋ＝４、グループ数Ｎｇが７の場合を仮定すると、このような場合、どのようなグループマルチプレキシング（ｇｒｏｕｐ ｍｕｌｔｉｐｌｅｘｉｎｇ）方式を使用するとしても、前記循環グループシフトなく、グループ選択の周期性をブレークできない。従って、循環シフトによってグループ選択の周期を増加させた後、前記グループマルチプレキシングは、所定のパターンによってグループ選択をランダム化させる。ここで、“グループマルチプレキシング”とは、特定のパターンによってグループをランダムに選択することである。前記グループ選択順序が循環シフトによってシフトされるとしても、前記グループをランダムに選択するための特定のパターンは、変更されない。すなわち、グループ選択は、特定のパターンがシフトされつつ行われる。
【００４６】
図６は、グループ選択の周期性をブレークするために、ランダムグループ選択のグループマルチプレキシング動作及び毎周期ごとグループ選択順序をシフトする循環シフト動作を遂行する２次元インタリービング装置内のグループ選択器を示す。
【００４７】
図６を参照すると、グループ選択器は、グループ数Ｎｇが２（ｋ−１）−１の倍数であるか否かを判断し、そのような場合、循環グループシフト動作によってグループ選択の周期を増加させる。その後、前記増加されたグループ選択周期に基づいて、前記グループマルチプレクサは、特定のパターンによって前記グループをランダムに選択する。
【００４８】
図７は、本発明の実施形態による２次元インタリービングを遂行するためのアドレス生成器を示す。
【００４９】
図７を参照すると、ランダムアドレス生成器７１１〜７１Ｎは、それぞれ関連のグループのアドレス生成器を利用して所定のインタリービングルールによって読出しアドレスを生成する。制御器７２１は、選択器７３１のマルチプレキシングを制御する。前記選択器７３１は、前記制御器７２１の制御下に前記アドレス生成器７１１〜７１Ｎの生成したアドレスを選択する。このように出力されたアドレスは、インタリーバメモリ２１２に順次に貯蔵されている入力フレームデータを読み出すのに使用される。前述したように、２次元インタリービング方法は、インタリーバサイズを多数のグループに区分し、前記区分されたグループに従ってインタリービングを遂行してアドレスを生成する。その後、前記生成されたアドレスを順次的またはランダムに選択して読出しアドレスとして使用する。このような場合、優秀なインタリービング特性を得るためには、前記選択器のグループ選択順序が重要である。本発明では、循環シフト方式によって毎周期ごとグループ選択順序をシフトする基本的な方式、及びインタリーバの距離特性を増加させるために、グループ選択順序をランダム化する方式を提案する。
【００５０】
図７のアドレス生成器の動作を説明すると、まず、アドレス生成器７１１〜７１Ｎは、該当グループ内のそれぞれ関連したインタリービングルールを利用してアドレスを生成する。例えば、前記アドレス生成器は、線形帰還シフトレジスタが使用できる。そして、制御器７２１は、前記アドレス生成器７１１〜７１Ｎの生成したアドレスを選択するための選択信号を前記選択器７３１に提供する。前記制御器７２１は、前記［表１］のように、循環シフト方式によるグループ選択信号を出力する。例えば、シフトステップが２の場合、前記制御器７２１は、第１周期では、０１２３４５６、第２周期では２３４５６０１、…、及び第７周期では、５６０１２３４の順序で周期ごとグループ選択順序を‘２’だけシフトさせる選択信号を出力する。インタリーバの距離特性を増加させるために、前記制御器７２１は、特定のパターンによってグループをランダムに選択することができる。前記特定のパターンは、Ｎｇグループを選択する度シフトされるが、そのシーケンスは変わらない。そして、前記選択器７３１は、前記制御器７２１からの前記選択信号によって前記アドレス生成器の生成したアドレスを選択する。前記選択されたアドレスは、インタリーバメモリ２１２に順次に貯蔵されている入力フレームデータをランダムに読み出すのに利用される。
【００５１】
図８Ａは、本発明の実施形態によるグループ選択を制御する制御器７２１の詳細なブロック図を示し、図８Ｂは、図８Ａの制御器７２１のタイミング図を示す。
【００５２】
図８Ａを参照すると、演算器８０３は、第２クロック信号ｃｌｋ２（図８Ｂに示すように）に応答してｍｏｄ７演算した値をスタートカウント値としてカウンタ８０１へ提供する。そうすると、前記カウンタ８０１は、第１クロック信号ｃｌｋ１に応答して前記演算器８０３から提供されたスタートカウント値でカウンティングを遂行し始め、グループ選択順序で行置換ルックアップテーブル８０５の前記カウント値をルックテーブルのアドレスとして使用する。ここで、前記カウンタ８０１は、［０．．６］を循環シフト方式にてカウンティングする。
【００５３】
図９Ａは、本発明の他の実施形態によるグループ選択を制御する制御器７２１の詳細なブロック図を示す。
【００５４】
図９Ａを参照すると、カウンタ９０３は、図９Ｂのクロック信号ｃｌｋに応答して、図９Ｂのカウンタ信号を出力する。比較器９０９は、前記カウンタ９０３からのカウンタ信号と所定の数‘６’とを比較した後、前記カウンタ信号が所定の数‘６’と同一である場合、ロードカウンタ（ｌｏａｄａｂｌｅ ｃｏｕｎｔｅｒ）９０１及びシフトカウンタ９０５に動作パルスＡＣＴ（ａｃｔｉｖａｔｉｏｎ ｐｕｌｓｅ）を提供する。そうすると、前記動作パルスＡＣＴの受信のとき、前記シフトカウンタ９０５は、シフトカウンタ信号（図９Ｂに示すように）を前記ロードカウンタ９０１へ出力する。その後、前記ロードカウンタ９０１は、前記クロック信号ｃｌｋに応答して毎周期ごと‘１’だけシフトされたロードカウンタ値（図９Ｂに示すように）を行置換ルックアップテーブル９０７にグループ選択順序で書き込む。
以上、本発明を特定の実施形態を参照して説明したが、本発明はこれらに限られるべきではなく、各種の変形が本発明の思想及び範囲を逸脱しない限り、当該技術分野における通常の知識を持つ者により可能なのは明らかである。
【００５５】
【発明の効果】
前述したように、本発明は、２次元インタリービングを遂行するとき、インタリーバの距離特性が満足させられる方式を提供する。すなわち、新たな２次元インタリーバは、特定のグループを選択する周期がターボ符号器の周期と相違であるように設計され、これにより、ターボ符号器の内部に備えられる構成符号器がゼロ状態でリセットされることを防止する。その結果、ターボ符号器の最小距離が最大化できる。
【図面の簡単な説明】
【図１】一般なターボ符号器を示すブロック図である。
【図２】本発明の実施形態に従う通信システムでのインタリービング装置を示すブロック図である。
【図３】本発明の実施形態に従う通信システムでのインタリービング装置を示すブロック図である。
【図４】２次元ターボインタリーバの動作原理を説明する図である。
【図５】Ｋ＝４、Ｎｇ＝７であり、グループ選択を順次に行う場合、特定の入力シーケンスに対する出力を示す図である。
【図６】本発明の実施形態に従う２次元インタリービング装置のグループ選択の概念を示す図である。
【図７】本発明の実施形態に従う２次元インタリービング装置を示す図である。
【図８Ａ】本発明の実施形態に従う図７のコントローラを示す詳細なブロック図である。
【図８Ｂ】図８Ａのコントローラを示すタイミング図である。
【図９Ａ】本発明の他の実施形態に従う図７のコントローラを示す詳細なブロック図である。
【図９Ｂ】図９Ａのコントローラのタイミング図である。
【符号の説明】
２１１，３１１  アドレス生成器
２１２  インタリーバメモリ
２１３，３１３，８０１，９０３  カウンタ
３１２  デインタリーバメモリ
７１１  第１ランダムアドレス生成器
７１２  第２ランダムアドレス生成器
７１３  第３ランダムアドレス生成器
７１Ｎ  第Ｎランダムアドレス生成器
７２１  制御器
７３１  選択器
８０５，９０７  行置換ルックアップテーブル
９０１  ロードカウンタ
９０５  シフトカウンタ
９０９  比較器
【図１】
0003574405.tif 000003
【図２】
0003574405.tif 000004
【図３】
0003574405.tif 000005
【図４】
0003574405.tif 000006
【図５】
0003574405.tif 000007
【図６】
0003574405.tif 000008
【図７】
0003574405.tif 000009
【図８Ａ】
0003574405.tif 000010
【図８Ｂ】
0003574405.tif 000011
【図９Ａ】
0003574405.tif 000012
【図９Ｂ】
0003574405.tif 000013