(57)【要約】【課題】従来よりも高速処理が可能でかつ誤り訂正後の誤り率特性の向上を実現可能な通信装置を得ること。【解決手段】本発明の通信装置は、情報ビット系列を符号化する符号化器１０１と、インタリーブ処理後の前記情報ビット系列を符号化する符号化器１０３と、を備えるターボ符号器を採用し、たとえば、前記ターボ符号器が、Ｍ×Ｎの入力バッファ内に前記情報ビット系列を格納し、Ｎ−１個のランダム系列を行数分だけ異なるものを用意し、Ｍ種類のランダム系列を生成し、さらに、すべてのランダム系列における各行のＮ個目に最小値をマッピングし、Ｍ×Ｎのマッピングパターンを生成し、前記Ｍ×Ｎのマッピングパターンにインタリーブ長の情報ビット系列をマッピングし、前記マッピング後の情報ビット系列を列単位に読み出し、符号化器１０３に対して出力するインタリーバ１０２、を備えることとした。【選択図】        図３−１
2008160169.tif 000002
【特許請求の範囲】
【請求項１】
情報ビット系列を畳込み符号化またはブロック符号化して第１の冗長データを出力する第１の符号化器と、インタリーブ処理後の前記情報ビット系列を畳込み符号化またはブロック符号化して第２の冗長データを出力する第２の符号化器と、を備えるターボ符号器を採用する通信装置であって、
前記ターボ符号器は、
Ｍ×Ｎの入力バッファ内に前記情報ビット系列を格納し、Ｎ−１個のランダム系列を行数分だけ異なるものを用意し、Ｍ種類のランダム系列を生成し、さらに、すべてのランダム系列における各行のＮ個目に最小値をマッピングし、Ｍ×Ｎのマッピングパターンを生成し、前記Ｍ×Ｎのマッピングパターンにインタリーブ長の情報ビット系列をマッピングし、前記マッピング後の情報ビット系列を列単位に読み出し、前記第２の符号化器に対して出力するインタリーバ、
を備えることを特徴とする通信装置。
【請求項２】
前記インタリーバは、前記Ｍ種類のランダム系列として、Ｍ×（Ｎ−１）のバッファ内でラテン方陣またはラテン長方形パターンを形成することを特徴とする請求項１に記載の通信装置。
【請求項３】
前記インタリーバは、特定のＮ−１個のランダム系列を行単位に１個または複数個ずつシフトすることで、前記Ｍ種類のランダム系列として、Ｍ×（Ｎ−１）のバッファ内でラテン方陣またはラテン長方形パターンを形成することを特徴とする請求項１または２に記載の通信装置。
【請求項４】
前記インタリーバは、特定のＮ−１個のランダム系列c(i)を、素数Ｐとその原始元G0を用いて、
c(i)=(G0×c(i-1))mod  P
i=1,2,…,P-2
c(0)=1
により生成すること（ただし、Ｎ＝Ｐ）を特徴とする請求項１、２または３に記載の通信装置。
【請求項５】
前記インタリーバは、原始元G0＝２の素数Ｐのみを用いてランダム系列を生成することを特徴とする請求項４に記載の通信装置。
【請求項６】
前記インタリーバは、特定のＮ−１個のランダム系列c'(i)を、Ｐ'を用いて、
c'(i)=(P'×i)mod  N
i=0,2,…,N-2
により生成すること（ただしＮとＰ'は互いに素）を特徴とする請求項１、２または３に記載の通信装置。
【請求項７】
前記インタリーバは、その他の確定的なランダム系列の求め方を用いてランダム系列を生成することを特徴とする請求項１、２または３に記載の通信装置。
【請求項８】
情報ビット系列を畳込み符号化またはブロック符号化して第１の冗長データを出力する第１の符号化器と、インタリーブ処理後の前記情報ビット系列を畳込み符号化またはブロック符号化して第２の冗長データを出力する第２の符号化器と、を備えるターボ符号器を採用する通信装置であって、
前記ターボ符号器は、
Ｍ×Ｎの入力バッファ内に前記情報ビット系列を格納し、Ｎ個のランダム系列を行数分だけ異なるものを用意し、Ｍ種類のランダム系列を生成し、Ｍ×Ｎのマッピングパターンを生成し、前記Ｍ×Ｎのマッピングパターンにインタリーブ長の情報ビット系列をマッピングし、前記マッピング後の情報ビット系列を列単位に読み出し、前記第２の符号化器に対して出力するインタリーバ、
を備えることを特徴とする通信装置。
【請求項９】
前記インタリーバは、前記Ｍ種類のランダム系列として、Ｍ×Ｎのバッファ内でラテン方陣またはラテン長方形パターンを形成することを特徴とする請求項８に記載の通信装置。
【請求項１０】
前記インタリーバは、特定のＮ個のランダム系列を行単位に１個または複数個ずつシフトすることで、前記Ｍ種類のランダム系列として、Ｍ×Ｎのバッファ内でラテン方陣またはラテン長方形パターンを形成することを特徴とする請求項８または９に記載の通信装置。
【請求項１１】
前記インタリーバは、特定のＮ個のランダム系列c(i)を、素数Ｐとその原始元G0を用いて、
c(i)=(G0×c(i-1))mod  P
i=1,2,…,P-1
c(0)=1
により生成すること（ただしＮ＋１＝Ｐ）を特徴とする請求項８、９または１０に記載の通信装置。
【請求項１２】
前記インタリーバは、原始元G0＝２の素数Ｐのみを用いてランダム系列を生成することを特徴とする請求項１１に記載の通信装置。
【請求項１３】
前記インタリーバは、特定のＮ個のランダム系列c'(i)を、Ｐ'を用いて、
c'(i)=(P'×i)mod  (N＋1)
i=0,2,…,N-1
により生成すること（ただしＮ＋１とＰ'は互いに素）を特徴とする請求項８、９または１０に記載の通信装置。
【請求項１４】
前記インタリーバは、その他の確定的なランダム系列の求め方を用いてランダム系列を生成することを特徴とする請求項８、９または１０に記載の通信装置。
【請求項１５】
情報ビット系列を畳込み符号化またはブロック符号化して第１の冗長データを出力する第１の符号化器と、インタリーブ処理後の前記情報ビット系列を畳込み符号化またはブロック符号化して第２の冗長データを出力する第２の符号化器と、を備えるターボ符号器を採用する通信装置であって、
前記ターボ符号器は、
Ｍ×Ｎの入力バッファ内に前記情報ビット系列を格納し、Ｍ個のランダム系列をＮ−１列数分だけ異なるものを用意し、Ｎ−１種類のランダム系列を生成し、さらに、各行のＮ個目に最小値をマッピングし、Ｍ×Ｎのマッピングパターンを生成し、前記Ｍ×Ｎのマッピングパターンにインタリーブ長の情報ビット系列をマッピングし、前記マッピング後の情報ビット系列を列単位に読み出し、前記第２の符号化器に対して出力するインタリーバ、
を備えることを特徴とする通信装置。
【請求項１６】
前記インタリーバは、前記Ｎ−１種類のランダム系列として、Ｍ×Ｎのバッファ内でラテン方陣またはラテン長方形パターンを形成することを特徴とする請求項１５に記載の通信装置。
【請求項１７】
前記インタリーバは、特定のＭ個のランダム系列を列単位に１個または複数個ずつシフトすることで、前記Ｎ−１種類のランダム系列として、Ｍ×（Ｎ−１）のバッファ内でラテン方陣またはラテン長方形パターンを形成することを特徴とする請求項１５または１６に記載の通信装置。
【請求項１８】
前記インタリーバは、特定のＭ個のランダム系列c(i)を、素数Ｐとその原始元G0を用いて、
c(i)=(G0×c(i-1))mod  P
i=1,2,…,P-1
c(0)=1
により生成すること（ただしＭ＋１＝Ｐ）を特徴とする請求項１５、１６または１７に記載の通信装置。
【請求項１９】
前記インタリーバは、原始元g＝２の素数Ｐのみを用いてランダム系列を生成することを特徴とする請求項１８に記載の通信装置。
【請求項２０】
前記インタリーバは、特定のＭ個のランダム系列c'(i)を、Ｐ'を用いて、
c'(i)=(P'×i)mod  (M＋1)
i=0,2,…,M-1
により生成すること（ただしＭ＋１とＰ'は互いに素）を特徴とする請求項１５、１６または１７に記載の通信装置。
【請求項２１】
前記インタリーバは、その他の確定的なランダム系列の求め方を用いてランダム系列を生成することを特徴とする請求項１５、１６または１７に記載の通信装置。
【請求項２２】
情報ビット系列を畳込み符号化またはブロック符号化して第１の冗長データを出力する第１の符号化器と、インタリーブ処理後の前記情報ビット系列を畳込み符号化またはブロック符号化して第２の冗長データを出力する第２の符号化器と、を備えるターボ符号器を採用する通信装置であって、
前記ターボ符号器は、
Ｍ×Ｎの入力バッファ内に前記情報ビット系列を格納し、Ｍ個のランダム系列を列数分だけ異なるものを用意し、Ｎ種類のランダム系列を生成し、Ｍ×Ｎのマッピングパターンを生成し、前記Ｍ×Ｎのマッピングパターンにインタリーブ長の情報ビット系列をマッピングし、前記マッピング後の情報ビット系列を列単位に読み出し、前記第２の符号化器に対して出力するインタリーバ、
を備えることを特徴とする通信装置。
【請求項２３】
前記インタリーバは、前記Ｎ種類のランダム系列として、Ｍ×Ｎのバッファ内でラテン方陣またはラテン長方形パターンを形成することを特徴とする請求項２２に記載の通信装置。
【請求項２４】
前記インタリーバは、特定のＭ個のランダム系列を列単位に１個または複数個ずつシフトすることで、前記Ｎ種類のランダム系列として、Ｍ×Ｎのバッファ内でラテン方陣またはラテン長方形パターンを形成することを特徴とする請求項２２または２３に記載の通信装置。
【請求項２５】
前記インタリーバは、特定のＭ個のランダム系列c(i)を、素数Ｐとその原始元gを用いて、
c(i)=(g×c(i-1))mod  P
i=1,2,…,P-1
c(0)=1
により生成すること（ただしＭ＋１＝Ｐ）を特徴とする請求項２２、２３または２４に記載の通信装置。
【請求項２６】
前記インタリーバは、原始元g＝２の素数Ｐのみを用いてランダム系列を生成することを特徴とする請求項２５に記載の通信装置。
【請求項２７】
前記インタリーバは、特定のＭ個のランダム系列c'(i)を、Ｐ'を用いて、
c'(i)=(P'×i)mod  (M＋1)
i=0,2,…,M-1
により生成すること（ただしＭ＋１とＰ'は互いに素）を特徴とする請求項２２、２３または２４に記載の通信装置。
【請求項２８】
前記インタリーバは、その他の確定的なランダム系列の求め方を用いてランダム系列を生成することを特徴とする請求項２２、２３または２４に記載の通信装置。
【請求項２９】
前記ターボ符号は、複数の畳み込み符号化器またはブロック符号器を持っていても良く、その際のインタリーバは諸元を変えることで複数のインタリーバを用意することを特徴とする請求項１〜２８のいずれか一つに記載の通信装置。
【請求項３０】
Ｎを素数とし、Ｍを素数Ｎと互いに素な整数とすることを特徴とする請求項１〜２９のいずれか一つに記載の通信装置。
【請求項３１】
前記インタリーバは、インタリーブパターンを、
u(k)=(P'×floor(k/M)+s×(M-1-(k  mod  M)  mod  N)+N×(k  mod  M)
N：インタリーブ行列の列数
M=ceil(K/N)：インタリーブ行列の行数、ceil(x)はxを超える最小整数
K：入力情報ビット数
s：基本疑似乱数系列読み出し時の開始位置シフト数
P'はNと互いに素な整数
floor(x)はxを超えない最大整数
により生成することを特徴とする請求項１、８、１５または２２に記載の通信装置。
【請求項３２】
さらに、
前記情報ビット系列を前記インタリーバの大きさに調整するビット調整手段、
を備えることを特徴とする請求項１〜３１のいずれか一つに記載の通信装置。
【請求項３３】
前記ターボ符号器が出力する符号語を通信システムの要求に応じた符号長にパンクチャするパンクチャ手段、
を備えることを特徴とする請求項３２に記載の通信装置。
【請求項３４】
前記請求項１〜３３のいずれか一つに記載の通信装置におけるインタリーバを含むことを特徴とするターボ符号器。
【請求項３５】
前記請求項１〜３３のいずれか一つに記載のインタリーブ処理を含むことを特徴とする通信方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ターボ符号等の誤り訂正符号を用いた通信装置に関するものである。
【背景技術】
【０００２】
以下、従来の通信装置について説明する。たとえば、SS（Spread  Spectrum）方式を用いた広帯域CDMA（W‐CDMA：Code  Division  Multiple  Access）においては、畳込み符号の性能を大きく上回る誤り訂正符号として、ターボ符号が提案されている。このターボ符号は、情報ビット系列にインタリーブを施した系列を既知の符号化系列と並列に符号化するもので、シャノン限界に近い特性が得られると言われており、一般的な誤り訂正符号の１つである。上記W‐CDMAにおいては、誤り訂正符号の性能が音声伝送やデータ伝送における伝送特性を大きく左右するため、ターボ符号の適用により伝送特性を大幅に向上させている。
【０００３】
ここで、上記ターボ符号を用いた従来の通信装置の送信系および受信系の動作を具体的に説明する。図３（図３−１および図３−２）は、送信系において使用されるターボ符号器の構成を示す図である。図３−１において、１０１は情報ビット系列を畳込み符号化して冗長ビットを出力する第１の再帰的組織畳込み符号化器であり、１０２はインタリーバであり、１０３はインタリーバ１０２により並べ替え後の情報ビット系列を畳込み符号化して冗長ビットを出力する第２の再帰的組織畳込み符号化器である。図３−２は、第１の再帰的組織畳込み符号化器１０１および第２の再帰的組織畳込み符号化器１０３の内部構成を示す図であり、２つの再帰的組織畳込み符号化器は、それぞれ冗長ビットのみを出力する符号化器である。また、上記ターボ符号器で用いられるインタリーバ１０２では、情報ビット系列をランダムに並べ替える処理を行う。
【０００４】
上記のように構成されるターボ符号器では、同時に、情報ビット系列：x1と、第１の再帰的組織畳込み符号化器１０１の処理により情報ビット系列：x1を符号化した冗長ビット系列：x2と、第２の再帰的組織畳込み符号化器１０３の処理によりインタリーブ処理後の情報ビット系列を符号化した冗長ビット系列：x3と、を出力する。
【０００５】
一方、図４は、受信系において使用されるターボ復号器の構成を示す図である。図４において、１１１は受信信号：y1と受信信号：y2とから対数尤度比を算出する第１の復号器であり、１１２および１１６は加算器であり、１１３および１１４はインタリーバであり、１１５は受信信号：y1と受信信号：y3とから対数尤度比を算出する第２の復号器であり、１１７はデインタリーバであり、１１８は第２の復号器１１５の出力を判定して元の情報ビット系列の推定値を出力する判定器である。なお、受信信号：y1，y2，y3は、それぞれ情報ビット系列：x1，冗長ビット系列：x2，x3に伝送路のノイズやフェージングの影響を与えた信号である。
【０００６】
上記のように構成されるターボ復号器では、まず、第１の復号器１１１が、受信信号：y1kと受信信号：y2kから推定される推定情報ビット：x1kの対数尤度比：L(x1k)を算出する（kは時刻を表す）。ここでは、情報ビット：x1kが０である確率に対する情報ビット：x1kが１である確率を求めることとなる。なお、後述するLe(x1k)は外部情報を表し、La(x1k)は１つ前の外部情報である事前情報を表す。
【０００７】
つぎに、加算器１１２では、前記算出結果である対数尤度比から、第２の復号器１１５に対する外部情報を算出する。なお、１回目の復号においては、事前情報が求められていないため、Le(x1k)＝０である。
【０００８】
つぎに、インタリーバ１１３および１１４では、受信信号：y1kと外部情報：Le(x1k)を、受信信号：y3の時刻にあわせるために、信号の並べ替えを行う。その後、第２の復号器１１５では、第１の復号器１１１と同様に、受信信号：y1と受信信号：y3、および先に算出しておいた外部情報：La(x1k)に基づいて、対数尤度比：L(x1k')を算出する。そして、加算器１１６では、外部情報：Le(x1k)を算出する。このとき、デインタリーバ１１７にて並べ替えられた外部情報は、事前情報：Ln(x1k)として前記第１の復号器１１１にフィードバックされる。
【０００９】
最後に、このターボ復号器では、上記処理を、所定の回数にわたって繰り返し実行することで、より精度の高い対数尤度比を算出し、そして、判定器１１８が、この対数尤度比に基づいて判定を行い、もとの情報ビット系列を推定する。具体的にいうと、たとえば、対数尤度比が“L(x1k')＞０”であれば、推定情報ビット：x1k'を１と判定し、“L(x1k')≦０”であれば、推定情報ビット：x1k'を０と判定する。
【００１０】
たとえば、W‐CDMAの規格においては、インタリーバとして、素数インタリーバ（Prime  Interleaver：以降、PILと呼ぶ）が用いられており、ターボ符号の内部インタリーバとして、非常に高性能な誤り訂正能力を持つ。
【００１１】
また、ターボ符号は繰り返し復号を行うことから復号遅延時間が大きく、100Mbps超の処理速度を要求されるシステムにおいては、復号処理の並列化が必要である。復号並列化には、インタリーブ前後にてメモリバンクに記憶したデータを読み出す場合、書き込み時に同じメモリバンクにアクセスしないことが必要となるが、前述のPILでは実装の際に回路が複雑になる等の問題があり、このような条件を満たすインタリーバにはブロックインタリーバ，ラテン方陣／ラテン長方形構造のインタリーバ（Latin  Lattice  /  Rectangle  Interleaver：以降、LRIと呼ぶ（下記特許文献１，２参照））がある。以下に、LRIインタリーバの生成方法を示す。
【００１２】
＜LRIインタリーバの構成方法＞
＜ステップ１＞
（１）パラメータを設定する。
K                    ：入力情報ビット数
P                    ：次を満たす最小素数  P2≧K
N=P                  ：インタリーブ行列の列数
M=ceil(K/N)          ：インタリーブ行列の行数
（ceil(x)はxを超える最小の整数）
（２）Pの原始元を選択する。
G0：  A  primitive  root
【００１３】
＜ステップ２＞
基本擬似乱数系列を生成する。
C(0)  =  1
For  i  =  1,…,P-3  ｛C(i+1)=G0×C(i)  mod  P｝
この生成に関しては、
For  i  =  1,…,P-2  ｛C(i)=(G0)i  mod  P｝
としても同じである。
【００１４】
＜ステップ３＞
系列C(・)を１つずつシフトして、行列CLj(ｉ)を構成する。ただし、最右列は０とする。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-2  ｛CLj(i)  =  C(j+i  mod  N-1)｝
CLj(N-1)  =  0
｝
【００１５】
＜ステップ４＞
M×Nの入力行列Uj(i)を用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛Uj(i)=i+N×j｝
｝
【００１６】
＜ステップ５＞
M×Nの出力行列U'j(i)を、CLj(i)を用いて用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛U'j(i)=U(M-1-j)(CL(M-1-j)(i))｝
｝
【００１７】
＜ステップ６＞
出力系列u(k)を列順に読み出すことで生成する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛u(j+M×i)=U'j(i)｝
｝
【００１８】
＜ステップ７＞
プルーニング
用意した行列の大きさと情報長に差がある場合には、情報長を超える大きさを持つ出力値（u(k)≧K）を削除する。
LRIで生成されたインタリーブパターンの例を以下に示す。これは、K=289，P=17，M=17，N=17，G0=3の場合である。インタリーブパターンは、下記（１）式：U'j(i)を列方向に読み出して生成される。
【００１９】
【数１】
2008160169.tif 000003
【００２０】
インタリーブパターン：u(i)=｛273,261,240,…,20,1,275,256,…,51,34,17,0｝となる。この例の復号過程において、受信信号y1kと外部情報Le(x1k)を行数と同じだけ用意した別のメモリバンクに記憶する（インタリーブ前のkは0,1,2,…,K、インタリーブ後のkはu(i)となる）。インタリーブ前には、｛0,1,2,…｝、｛17,18,19,…｝、｛34,35,36,…｝…と、｛｝ごとにすべて同じタイミングで処理を行い、インタリーブ後には、｛1,20,43,…｝、｛26,44,…,3｝、｛47,…,9,47｝…と、列単位で開始位置をずらして並列処理を行うと、同じタイミングで同じメモリバンクにアクセスすることはなく、矛盾なく並列処理ができる。
【００２１】
【特許文献１】特開２００１−３３２９８１号公報
【特許文献２】特開２００１−２８５０７７号公報
【発明の開示】
【発明が解決しようとする課題】
【００２２】
しかしながら、並列処理を可能にするインタリーバであるブロックインタリーバは、構成が非常に簡易であるものの、現行のPILに比べて性能劣化が大きい。LRIはインタリーバサイズが小さい場合にはPILと同等もしくはそれ以上の性能を有するが、大きくなる場合には劣化する。
【００２３】
本発明は、上記に鑑みてなされたものであって、ターボ符号を採用した通信システムすべてに適用可能とし、さらに、従来技術と比較して並列化による高速処理が可能で、かつ誤り訂正後の誤り率特性の向上を実現可能な通信装置を得ることを目的とする。
【課題を解決するための手段】
【００２４】
上述した課題を解決し、目的を達成するために、本発明にかかる通信装置は、情報ビット系列を畳込み符号化またはブロック符号化して第１の冗長データを出力する第１の符号化器と、インタリーブ処理後の前記情報ビット系列を畳込み符号化またはブロック符号化して第２の冗長データを出力する第２の符号化器と、を備えるターボ符号器を採用する通信装置であって、前記ターボ符号器は、Ｍ×Ｎの入力バッファ内に前記情報ビット系列を格納し、Ｎ−１個のランダム系列を行数分だけ異なるものを用意し、Ｍ種類のランダム系列を生成し、さらに、すべてのランダム系列における各行のＮ個目に最小値をマッピングし、Ｍ×Ｎのマッピングパターンを生成し、前記Ｍ×Ｎのマッピングパターンにインタリーブ長の情報ビット系列をマッピングし、前記マッピング後の情報ビット系列を列単位に読み出し、前記第２の符号化器に対して出力するインタリーバ、を備えることを特徴とする。
【発明の効果】
【００２５】
この発明によれば、従来のようにインタリーバ生成に関わるパラメータを入力情報長Kに対して一意に決めず、必要な処理速度を満たす並列数に対して、良いインタリーブパターンを検索することにより、高い誤り訂正能力を持つインタリーブパターンを得ることができる、という効果を奏する。
【発明を実施するための最良の形態】
【００２６】
以下に、本発明にかかる通信装置の実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。
【００２７】
実施の形態１．
図１は、ターボ符号化器１およびターボ復号器１１を含む実施の形態１の通信システムの構成例を示す構成図である。図１において、送信側の通信装置（送信装置と呼ぶ）は、ターボ符号化器１とインタリーバ生成器２と変調器３を含む構成とし、受信側の通信装置（受信装置と呼ぶ）は、復調器４とターボ復号器５とインタリーバ生成器２を含む構成とする。
【００２８】
ここで、ターボ符号を採用する通信システムにおける符号化処理，復号処理の流れを簡単に説明する。
【００２９】
送信装置内のターボ符号化器１では、情報長Kのメッセージ(u0,u1,…,uK-1)を受け取り、インタリーバ生成器２で生成したインタリーブパターンを用いて符号化した符号語ｖを生成する。そして、送信装置内の変調器２では、ターボ符号化器１で生成した符号語ｖに対して、BPSK，QPSK，多値QAM等の所定の変調方式によりディジタル変調を行い、その変調信号x=(x0,x1,…,xN-1)を、通信路６を介して受信装置に送信する。
【００３０】
一方、受信装置では、復調器４が、通信路６を介して受け取った変調信号y=(y0,y1,…,yN-1)に対して、上記BPSK，QPSK，多値QAM等の変調方式に応じたディジタル復調を行い、さらに、受信装置内のターボ復号器５が、復調結果に対してインタリーバ生成器２で生成したインタリーブパターンを用いて復号を実施し、その復号結果（元のメッセージu0,u1,…，uK-1に対応）を出力する。
【００３１】
なお、上記送信装置と上記受信装置の双方の構成を搭載した通信装置を複数構成し、当該複数の通信装置間で、互いに信号を送受信するようにしても良い。
【００３２】
また、ターボ符号化器１は、図３−１に示すように、第一の再帰的組織畳込み符号化器１０１とインタリーバ１０２と第２の再帰的組織畳込み符号化器１０３を用いて行う。図３−２は、上記再帰的組織畳込み符号化器の一例であって、たとえば、W-CDMA規格の再帰的組織畳込み符号化器など、ターボ符号を構成する再帰的組織畳込み符号化器であればいずれであっても良い。ターボ復号器５は、上記再帰的組織畳込み符号化器に対応して構成する。
【００３３】
つぎに、本実施の形態のインタリーバ生成器２でのインタリーブパターン生成アルゴリズムを示す。
【００３４】
＜ステップ１＞
（１）パラメータを設定する。
K                    ：入力情報ビット数
N                    ：インタリーブ行列の列数（素数）
M=ceil(K/N)          ：インタリーブ行列の行数
（ceil(x)はxを超える最小整数）
s                    ：基本疑似乱数系列読み出し時の開始位置シフト数
（２）Nの原始元を選択する。
G0                    ：Ｎの原始元
【００３５】
＜ステップ２＞
Ｎ個のランダム系列として、以下のように基本疑似乱数系列を生成する。
C(0)  =  1,  C(N-1)  =  0
For  i  =  0,…,N-3  ｛C(i+1)=G0×C(i)  mod  N｝
この生成に関しては、
For  i  =  0,…,N-2  ｛C(i)=(G0)i  mod  N｝
C(N-1)  =  0
としても同じである。
【００３６】
＜ステップ３＞
系列C(・)をｓ個ずつシフトして、行列CLj(i)を構成する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛CLj(i)=C(i+s×j  mod  N)｝
｝
【００３７】
＜ステップ４＞
M×Nの入力行列Uj(i)を用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛Uj(i)=i+N×j｝
｝
【００３８】
＜ステップ５＞
M×Nの出力行列U'j(i)を、CLj(i)を用いて用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛U'j(i)=U(M-1-j)(CL(M-1-j)(i))｝
｝
【００３９】
＜ステップ６＞
出力系列u(k)を列順に読み出すことで生成する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛u(j+M×i)=U'j(i)｝
｝
【００４０】
＜ステップ７＞
プルーニング
用意した行列の大きさと情報長に差がある場合には、情報長を超える大きさを持つ出力値（u(k)≧K）を削除する。
【００４１】
なお、ステップ２，３においては、従来のLRIとは違い最右列を０に固定していないが、下記のように最右列を0に固定しても良い。この場合には、Ｎ−１個のランダム系列として、以下のように基本疑似乱数系列を生成し、各行のＮ個目は0に固定する。
【００４２】
＜ステップ２＞
Ｎ−１個のランダム系列として、以下のように基本疑似乱数系列を生成する。
C(0)  =  1
For  i  =  0,…,N-3  ｛C(i+1)=G0×C(i)  mod  N｝
【００４３】
＜ステップ３＞
系列C(・)をｓ個ずつシフトして、行列CLj(i)を構成する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-2  ｛CLj(i)=C(i+s×j  mod  N-1)｝
CLj(N-1)  =  0
｝
【００４４】
また、ステップ１において、Ｎ＋１が素数となるようにＮを選択し、ステップ２において、
＜ステップ２＞
Ｎ個のランダム系列として、以下のように基本疑似乱数系列を生成する。
C(0)  =  0
For  i  =  0,…,N-3  ｛C(i+1)=(G0×(C(i)+1)  mod  N)-1｝
この生成に関しては、
For  i  =  0,…,N-2  ｛C(i)=((G0)i  mod  N)-1｝
としても同じである。
【００４５】
また、原始元G0が2の場合には、基本疑似乱数系列を得るために２乗算処理を行うことになるが、２の乗算は１ビットシフトで可能であるから、原始元が２の素数だけにNを限定することで処理量を軽減することも可能である。
【００４６】
また、図２（図２−１，図２−２，図２−３）には、本実施の形態のインタリーバと、従来のLRI，W-CDMA規格のPILとの性能比較を示す。シミュレーションは、AWGN通信路，BPSK変調を仮定しており、たとえば、ターボ符号の再帰的組織畳込み符号化器はW-CDMA規格と同じで、テールは１２ビットの終端ビットを付加した符号化率1/3で、また、復号方式はMax-Log-MAP復号法で繰り返し回数を８回、としている。横軸がブロック誤り率（Block  Error  Rate(BLER)：Eb/N0[dB]）である。また、図２−１が長さ３０００、図２−２が長さ４０００、図２−３が長さ５０００の場合であり、それぞれのインタリーバを構成するにあたり、(m,s)の組み合わせは“union  bound”および計算機シミュレーションの少なくともいずれか一方を用いて検索し、３０００の場合に(m,s)=(79,2)であり、４０００の場合に(101,1)であり、５０００の場合に(157,3)である。すべての場合において本実施の形態の方がBLERが向上しており、高い誤り訂正能力を持つ現3GPPで採用されているPILと同等の性能を示している。なお、(m,s)の設定値は、上記に限られるものではなく、誤り訂正能力の高い組み合わせをKに応じて検索する。
【００４７】
また、それぞれの場合の(m,s)から、行数はceil(3000/101)=30，ceil(4000/127)=32，ceil(5000/157)=32であり、それぞれ30，32，32の並列化が可能である。従来のLRIでは、P2≧K(N=P)として行数を決めるため、さらに大きな並列化が可能であるが、通信システムの要求処理速度を満たす並列数が確保できれば十分である。
【００４８】
以上のように、本実施の形態によれば、ラテン方陣またはラテン長方形構造を持つLRIインタリーバの、行または列数を基準にして性能改善を図ることとした。これにより、従来のLRIインタリーバと同様に高い並列数を可能にするだけでなく、高い性能を持つ3GPP規格のPILと同等の誤り訂正能力を有することができる。また、基本疑似乱数生成方法が3GPP規格のPILと同じであるため、従来の開発資産を効果的に用いることで、インタリーバ開発の効率化を図ることもできる。
【００４９】
実施の形態２．
つづいて、実施の形態２の通信システムについて説明する。なお、本実施の形態のシステムにおいて、送信装置および受信装置の構成については、前述した実施の形態１の図１と同様である。以下、実施の形態１と異なる処理について説明する。
【００５０】
ここで、実施の形態２のインタリーバ生成器２でのインタリーブパターン生成アルゴリズムを示す。
【００５１】
＜ステップ１＞
（１）パラメータを設定する。
K                ：入力情報ビット数
N                ：インタリーブ行列の列数
M=ceil(K/N)      ：インタリーブ行列の行数、ceil(x)はxを超える最小整数
s                ：基本疑似乱数系列読み出し時の開始位置シフト数
（２）Nと互いに素な整数を選択する。
P'              ：Nと互いに素な整数（co-prime、relative  prime）
【００５２】
＜ステップ２＞
Ｎ個のランダム系列として、以下のように基本疑似乱数系列を生成する。
For  i  =  0,…,N-1  ｛C(i)=(P'×i  mod  N)｝
この生成に関しては、
C(0)  =  0
For  i  =  1,…,N-1  ｛C(i+1)=C(i)+P'  mod  N｝
としても同じである。
【００５３】
＜ステップ３＞
系列C(・)を１つずつシフトして、行列CLj(i)を構成する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛CLj(i)=C(i+s×j  mod  N)｝
｝
【００５４】
＜ステップ４＞
M×Nの入力行列Uj(i)を用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛Uj(i)=i+N×j｝
｝
【００５５】
＜ステップ５＞
M×Nの出力行列U'j(i)を、CLj(i)を用いて用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛U'j(i)=U(M-1-j)(CL(M-1-j)(i))｝
｝
【００５６】
＜ステップ６＞
出力系列u(k)を列順に読み出すことで生成する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛u(j+M×i)=U'j(i)｝
｝
【００５７】
＜ステップ７＞
プルーニング
用意した行列の大きさと情報長に差がある場合には、情報長を超える大きさを持つ出力値（u(k)≧K）を削除する。
【００５８】
なお、ステップ２においては、以下のようにしても良い。
＜ステップ２＞
Ｎ個のランダム系列として、以下のように基本疑似乱数系列を生成する。
For  i  =  0,…,N-1  ｛C(i)=P'×i+Q  mod  N｝
ここで、Qは任意の整数である。
【００５９】
または、
＜ステップ２＞
Ｎ個のランダム系列として、以下のように基本疑似乱数系列を生成する。
For  i  =  0,…,N-1  ｛
C(i)  =  (floor(i/2)×P'  mod  N/2)×2+1  （iが偶数のとき）
C(i)  =  (floor(i/2+Q')×P'  mod  N/2)×2  （iが奇数のとき）
｝
ここで、floor(x)はxを超えない最大整数、Q'は任意の整数である。
【００６０】
さらに、Ｎ−１個のランダム系列として、Ｎ−１と互いに素な整数P''を用いて、以下のように基本疑似乱数系列を生成し、
＜ステップ２＞
For  i  =  0,…,N-2  ｛C(i)=P''×i  mod  N-1｝
または、
For  i  =  0,…,N-2  ｛C(i)=P''×i+Q  mod  N-1｝
＜ステップ３＞
系列C(・)をｓ個ずつシフトして、行列CLj(i)を構成する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-2  CLj(i)｛CLj(i)=C(i+s×j  mod  N)｝
CLj(N-1)  =  0
｝
と最右列を0と固定しても良い。
【００６１】
本実施の形態では、基本疑似乱数系列を列数の値と互いに素な整数に基づいて生成する。この疑似乱数生成は、P'の加算を繰り返し処理で実現可能であり、乱数生成が容易である。また、互いに素な整数は多数存在し、列数が素数に限定されることもなく、行数もしくは列数の設定に際して広い範囲から誤り訂正能力の高い組み合わせを検索することができる。
【００６２】
以上のように、本実施の形態によれば、ラテン方陣またはラテン長方形構造を持つLRIインタリーバの基本疑似乱数を、列数と互いに素な整数を用いて生成することとした。これにより、列数の選択枝が増え、良好な特性を持つ組み合わせを検索することが容易となる。
【００６３】
実施の形態３．
実施の形態３の通信システムについて説明する。なお、本実施の形態のシステムにおいて、送信装置および受信装置の構成については、前述した実施の形態１の図１と同様である。以下、実施の形態１と異なる処理について説明する。
【００６４】
ここで、実施の形態３のインタリーバ生成器２でのインタリーブパターン生成アルゴリズムを示す。
【００６５】
＜ステップ１＞
（１）パラメータを設定する。
K                ：入力情報ビット数
N                ：インタリーブ行列の列数
M=ceil(K/N)      ：インタリーブ行列の行数、ceil(x)はxを超える最小整数
s                ：基本疑似乱数系列読み出し時の開始位置シフト数
（２）Nと互いに素な整数を選択する。
P'              ：Nと互いに素な整数（co-prime、relative  prime）
【００６６】
＜ステップ２＞
以下の計算式に基づいて、インタリーブパターンを生成する。
u(k)=(P'×floor(k/M)+s×(M-1-(k  mod  M)  mod  N)+N×(k  mod  M)
【００６７】
＜ステップ３＞
プルーニング
生成したパターンの大きさと情報長に差がある場合には、情報長を超える大きさを持つ出力値（u(k)≧K）を削除する。
【００６８】
本実施の形態では、基本疑似乱数系列を列数の値と互いに素な整数に基づいて生成する。この疑似乱数生成は、P'の加算を繰り返し処理で実現可能であり、乱数生成が容易である。また、互いに素な整数は多数存在し、列数が素数に限定されることもなく、行数もしくは列数の設定に際して広い範囲から誤り訂正能力の高い組み合わせを検索することができる。
【００６９】
以上のように、本実施の形態によれば、ラテン方陣またはラテン長方形構造を持つLRIインタリーバの基本疑似乱数を、列数と互いに素な整数を用いて生成することとした。これにより、列数の選択枝が増え、良好な特性を持つ組み合わせを検索することが容易となる。
【００７０】
実施の形態４．
図５は、ターボ符号化器およびターボ復号器を含む実施の形態４の通信システムの構成例を示す構成図である。図５において、送信側の通信装置（送信装置と呼ぶ）は、ビット調整器１１とターボ符号化器１とインタリーバ生成器２ａとパンクチャ器１２と変調器３を含む構成とし、受信側の通信装置（受信装置と呼ぶ）は、復調器４とデパンクチャ器１３とターボ復号器５とインタリーバ生成器２ａとビット調整器１４を含む構成とする。
【００７１】
ここで、実施の形態４の通信システムにおける符号化処理，復号処理の流れを簡単に説明する。
【００７２】
送信装置内のビット調整器１１では、入力ビット長とインタリーバ生成器２ａで生成するインタリーバの大きさに基づいて、情報長Kのメッセージを調整する。入力ビット長をK、インタリーバ生成器２ａで生成するインタリーバの大きさをL(L≧K)とすると、両者に(L-K)ビットの違いがあるため、元のメッセージ(u0,u1,…,uK-1)に対して(L-K)ビット分を調整するため、0または1の既知の信号を挿入する。挿入位置は入力ビットの先頭や末尾などL-K個の任意の場所とする。ターボ符号化器１では、ビット調整されたLビットのメッセージを受け取り、インタリーバ生成器２ａで生成したインタリーブパターンを用いて符号化した符号語ｖを生成する。そして、送信装置内のパンクチャ器１２では、通信システムの要求に応じた符号長Wの符号化語を、ターボ符号化器１の出力からパンクチャして生成する。変調器３では、パンクチャ器１２で生成した符号語ｖに対して、BPSK，QPSK，多値QAM等の所定の変調方式によりディジタル変調を行い、その変調信号x=(x0,x1,…,xW-1)を、通信路を介して受信装置に送信する。
【００７３】
一方、受信装置では、復調器４が、通信路を介して受け取った変調信号y=(y0,y1,…,yW-1)に対して、上記BPSK，QPSK，多値QAM等の変調方式に応じたディジタル復調を行い、さらに、受信装置内のデパンクチャ器１３が、送信装置にてパンクチャされたビットのデパンクチャ処理を行い、ターボ復号器５が、復調結果に対して、インタリーバ生成器２ａで生成したインタリーブパターンを用いて復号を実施し、その復号結果を出力し、ビット調整器１４が、送信時に挿入した調整ビットを取り除き、その結果（元のメッセージu0,u1,…，uK-1に対応）を出力する。
【００７４】
なお、上記送信装置と上記受信装置の双方の構成を搭載した通信装置を複数構成し、当該複数の通信装置間で、互いに信号を送受信するようにしても良い。
【００７５】
また、ターボ符号化器１は、図３−１に示すように、第一の再帰的組織畳込み符号化器１０１とインタリーバ１０２と第２の再帰的組織畳込み符号化器１０３を用いて行う。図３−２は、上記再帰的組織畳込み符号化器の一例であって、たとえば、W-CDMA規格の再帰的組織畳込み符号化器など、ターボ符号を構成する再帰的組織畳込み符号化器であればいずれであっても良い。ターボ復号器５は、上記再帰的組織畳込み符号化器に対応して構成する。
【００７６】
つぎに、本実施の形態のインタリーバ生成器２ａでのインタリーブパターン生成アルゴリズムを示す。
【００７７】
＜ステップ１＞
（１）パラメータを設定する。
L                ：入力ビット数
N                ：インタリーブ行列の列数（素数）
M=ceil(L/N)      ：インタリーブ行列の行数
（ceil(x)はxを超える最小整数）
s                ：基本疑似乱数系列読み出し時の開始位置シフト数
（２）Nの原始元を選択する。
G0              ：Ｎの原始元
【００７８】
具体的に、Ｌ：入力ビット数に対して、Ｎ：インタリーブ行列の列数（素数Ｐ）、M=ceil(L/N)：インタリーブ行列の行数（ceil(x)はxを超える最小整数）、s：基本疑似乱数系列読み出し時の開始位置シフト数、G0：Ｎの原始元の例を記す。
【００７９】
入力ビット数Ｌに対応した、素数Ｐ、Ｐの原始元G0リストを定義する。ここでは、L=40〜82241に対応して、素数Ｐ(Ｐの原始元G0)は｛7(3),11(2),13(2),17(3),19(2),23(5),29(2),31(3),37(2),41(6),43(3),47(5),53(2),59(2),61(2),67(2),71(7),73(5),79(3),83(2),89(3),97(5),101(2),103(5),107(2),109(6),113(3),127(3),131(2),137(3),139(2),149(2),151(6),157(5),163(2),167(5),173(2),179(2),181(2),191(19),193(5),197(2),199(3),211(2),223(3),227(2),229(6),233(3),239(7),241(7),251(6),257(3)｝を用意する。
【００８０】
Ａ）L<=992のとき
１）列数Nを決める。
P*P≧Lとなる最小の素数Pを検索し、列数N(=P)とする。
２）Pの原始元G0を選択する。
３）行数Mを決める。M=ceil(L/N)、ceil(x)はxを超える最小整数。
４）シフト数sを決める。
M=7のとき、s=5
M=11のとき、s=10
上記以外、s=1
Ｂ）L>992のとき
１）列数Nを決める。
32*P≧Lとなる最小の素数Pを検索し、列数N(=P)とする。
２）Pの原始元G0を選択する。
３）行数Mを決める。M=ceil(L/N)、ceil(x)はxを超える最小整数。
４）シフト数sを決める。
M=131のとき、s=2
M=179のとき、s=3
M=227のとき、s=2
上記以外、s=1
【００８１】
＜ステップ２＞
基本疑似乱数系列を生成する。
C(0)  =  1
For  i  =  0,…,N-3  ｛C(i+1)=G0×C(i)  mod  N｝
【００８２】
＜ステップ３＞
系列C(・)をｓ個ずつシフトして、行列CLj(i)を構成する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-2  ｛CLj(i)=C(i+s×j  mod  N)｝
CLj(N-1)  =  0
｝
【００８３】
＜ステップ４＞
M×Nの入力行列Uj(i)を用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛Uj(i)=i+N×j｝
｝
【００８４】
＜ステップ５＞
M×Nの出力行列U'j(i)を、CLj(i)を用いて用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛U'j(i)=U(M-1-j)(CL(M-1-j)(i))｝
｝
【００８５】
＜ステップ６＞
出力系列u(k)を列順に読み出すことで生成する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛u(j+M×i)=U'j(i)｝
｝
【００８６】
また、原始元G0が2の場合には、基本疑似乱数系列を得るために２乗算処理を行うことになるが、２の乗算は１ビットシフトで可能であるから、原始元が２の素数だけにNを限定することで処理量を軽減することも可能である。
【００８７】
また、本実施の形態では、列数を素数で定義してその原始元から疑似乱数系列を生成しているが、列数を任意の整数としてその互いに素な整数を用いて疑似乱数系列を生成するなどの方法で重複のない疑似乱数系列を生成することも可能であり、実施の形態１、２に記載の＜ステップ１＞〜＜ステップ６＞、実施の形態３に記載の＜ステップ１＞、＜ステップ２＞のみを実施しても良い。
【００８８】
本実施の形態では、本来の情報ビットに対して0もしくは1など既知の情報を挿入して、ターボ符号の入力長をインタリーバの大きさに調整することで、インタリーバ生成におけるプルーニング処理をなくすこととした。これにより、インタリーバの生成処理を簡易にすることができる。
【００８９】
実施の形態５．
つづいて、実施の形態５の通信システムについて説明する。なお、本実施の形態のシステムにおいて、送信装置および受信装置の構成については、前述した実施の形態１の図１と同様である。以下、実施の形態１と異なる処理について説明する。
【００９０】
ここで、実施の形態５のインタリーバ生成器２でのインタリーブパターン生成アルゴリズムを示す。
【００９１】
なお、＜ステップ４＞、＜ステップ５＞を除く他のステップは、実施の形態１、実施の形態２と同様である。＜ステップ４＞、＜ステップ５＞のみ記す。
【００９２】
＜ステップ４＞
M×Nの入力行列Uj(i)を用意する。
For  i  =  0,1,…,N-1  ｛
For  j  =  0,1,…,M-1  [Uj(i)=j+M×i｝
｝
【００９３】
＜ステップ５＞
M×Nの出力行列U'j(i)を、CLj(i)を用いて用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛U'j(i)=U(M-1-j)(CL(M-1-j)(i))｝
｝
【００９４】
または、
＜ステップ５＞
M×Nの出力行列U'j(i)を、CLj(i)を用いて用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  [U'j(i)=Uj(CLj(i))｝
｝
【００９５】
入力行列を用意する際に、行方向に連続するように番号を書き込むが、本実施の形態では、列方向に連続するように番号を書き込む。従来から出力系列は列方向に連続するように読み出しており、入出系列を出力系列の書き込みと読み出しを同方向にすることで処理を簡易にすることができる。
【００９６】
実施の形態６．
つづいて、実施の形態６の通信システムについて説明する。なお、本実施の形態のシステムにおいて、送信装置および受信装置の構成については、前述した実施の形態１の図１と同様である。
【００９７】
ここで、実施の形態６のインタリーバ生成器２でのインタリーブパターン生成アルゴリズムを示す。なお、＜ステップ１＞以外の処理については前述した実施の形態１と同様である。
【００９８】
＜ステップ１＞
（１）パラメータを設定する。
L                ：入力ビット数
N                ：インタリーブ行列の列数（素数）
M                ：インタリーブ行列の行数
s                ：基本疑似乱数系列読み出し時の開始位置シフト数
（２）Nの原始元を選択する。
G0              ：Ｎの原始元
【００９９】
（３）入力ビット数Ｌに対応した、素数P，素数Pの原始元G0，シフト数sのリストを定義する。ここでは、L=40〜8224に対応して、素数P（Pの原始元G0,シフト数s）は｛7(3,5),11(2,10),13(2,1),17(3,1),19(2,15),23(5,2),29(2,5),31(3,1),37(2,1),41(6,1),43(3,1),47(5,1),53(2,1),59(2,7),61(2,1),67(2,1),71(7,1),73(5,1),79(3,1),83(2,1),89(3,1),97(5,1),101(2,2),103(5,2),107(2,2),109(6,1),113(3,1),127(3,1),131(2,13),137(3,4),139(2,2),149(2,2),151(6,1),157(5,1),163(2,4),167(5,2),173(2,2),179(2,3),181(2,2),191(19,1),193(5,1),197(2,3),199(3,2),211(2,2),223(3,1),227(2,3),229(6,2),233(3,1),239(7,1),241(7,1),251(6,1),257(3,1)｝を用意する。
【０１００】
Ａ）L≦930のとき
１）列数Nを決める。
P*(P-1)≧Lとなる最小の素数Pを検索し、列数N(=P)、行数M(=P-1)とする。
２）Pの原始元G0をリストから読む。
３）Pに対応したシフト数sをリストから読む。
Ｂ）L>930のとき
１）列数Nを決める。
行数M=32とする。
M*P≧Lとなる最小の素数Pを検索し、列数N(=P)とする。
２）Pの原始元G0をリストから読む。
３）Pに対応したシフト数sをリストから読む。
【０１０１】
＜ステップ２＞
基本疑似乱数系列を生成する。
C(0)  =  1
For  i  =  0,…,N-3  ｛C(i+1)=G0×C(i)  mod  N｝
C(N-1)  =  0
【０１０２】
＜ステップ３＞
系列C(・)をｓ個ずつシフトして、行列CLj(i)を構成する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛CLj(i)=C(i+s×j  mod  N)｝
｝
【０１０３】
＜ステップ４＞
M×Nの入力行列Uj(i)を用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛Uj(i)=i+N×j｝
｝
【０１０４】
＜ステップ５＞
M×Nの出力行列U'j(i)を、CLj(i)を用いて用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛U'j(i)=U(M-1-j)(CL(M-1-j)(i))｝
｝
【０１０５】
＜ステップ６＞
出力系列u(k)を列順に読み出すことで生成する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛u(j+M×i)=U'j(i)｝
｝
【０１０６】
＜ステップ７＞
プルーニング
用意した行列の大きさと情報長に差がある場合には、情報長を超える大きさを持つ出力値（u(k)≧K）を削除する。
【０１０７】
なお、ステップ２のランダム系列は以下のように生成しても良い。
＜ステップ２＞
For  i  =  0,…,N-2  ｛C(i)=(G0)i  mod  N｝
C(N-1)  =  0
【０１０８】
つづいて、上記インタリーブパターン生成アルゴリズムによりインタリーブパターンを生成した場合の、復号処理の一例について説明する。復号過程において、受信信号y1kと外部情報Le(x1k)を行数Mと同じだけ用意した別のメモリバンクに記憶する。たとえば、先頭からN個のデータ(0≦k≦N-1)をメモリバンク１に、次のN個のデータ(N≦k≦2×N-1)をメモリバンク２に、次のN個のデータ(2×N≦k≦3×N-1)をメモリバンク３に、…、と順に記憶しておく。インタリーブ前の復号を並列にするには、メモリバンクごとに復号が生じるので同じメモリバンクにアクセスすることはなく、行数M(メモリバンク数)の並列化が可能である。
【０１０９】
ここで、本実施の形態においては、インタリーブ後の復号においても同じメモリバンクにアクセスすることがなく、行数M(メモリバンク数)の並列化が可能であることを説明する。インタリーブ後の系列は、先頭から順に、C(s×(M-1)  mod  N)+N×(M-1)，C(s×(M-2)  mod  N)+N×(M-2)，…，C(s  mod  N)+N，C(0)，C(1+s×(M-1)  mod  N)+N×(M-1)，C(1+s×(M-2)  mod  N)+N×(M-2)，…，C(1+s  mod  N)+N，C(1)，C(2+s×(M-1)  mod  N)+N×(M-1)，C(2+s×(M-2)  mod  N)+N×(M-2)，…，C(2+s  mod  N)+N，C(2)，…となる。M個のメモリバンクに対するアクセスは、周期的に生じており、並列化するには各処理の最初にアクセスするメモリバンクが重ならなければ、処理中に同じメモリバンクにアクセスすることはない。M×N個の系列をM分割すると、先頭からN個ずつ区切られ、NとMは互いに素な関係にあるため、各並列処理で最初にアクセスするメモリバンクB(i)は、
B(i)  =  N×i  mod  M  (0≦i≦M-1)
で表すことができ、いずれのB(i)についても同じになることはない。B(i)の式は、互いに素な関係により疑似乱数を生成する手段と同じ原理となる。
【０１１０】
また、並列数がM未満のM'でもメモリバンクのアクセスが衝突することはなく、並列処理を行うことが可能である。先頭からWビットづつM'個に区切り、M'並列する場合に、各並列処理で最初にアクセスするメモリバンクB(i)は、
B(i)=W×i  mod  M  (0≦i≦M-1)
となる。WはMと互いに素であれば別のメモリバンクにアクセスし、Mが32の場合にWは奇数ならば互いに素となるため、メモリバンク数M以下の正の整数1≦W≦Mでの並列化が可能となる。
【０１１１】
また、本実施の形態では、素数Pとその原始元G0を用いて疑似乱数系列を生成したが、実施の形態２のように素数Pと互いに素な整数で疑似乱数系列を生成しても良い。また、実施の形態４のようにプルーニングを用いてインタリーバの大きさを調整せず、入力ビットに既知のビットを挿入してインタリーバの大きさと同じ入力ビット数として符号化しても良い。
【０１１２】
以上のように、本実施の形態によれば、列数と行数を互いに素な関係になるようにラテン方陣またはラテン長方形構造を持つLRIインタリーバを設計した。これにより、並列処理の選択肢が増え、高速処理が必要な復号回路の実装において、並列処理も選択肢を広くとることができる。
【０１１３】
実施の形態７．
つづいて、実施の形態７の通信システムについて説明する。なお、本実施の形態のシステムにおいて、送信装置および受信装置の構成については、前述した実施の形態６と同様である。以下、実施の形態６と異なる処理について説明する。
【０１１４】
具体的には、実施の形態７のインタリーブパターン生成アルゴリズムにおいては、＜ステップ４＞の処理が実施の形態６と異なっている。
【０１１５】
＜ステップ４＞
M×Nの入力行列Uj(i)を用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛Uj(i)=j+M×i｝
｝
【０１１６】
つづいて、上記実施の形態７のインタリーブパターン生成アルゴリズムによりインタリーブパターンを生成した場合の、復号処理の一例について説明する。復号過程において、受信信号y1kと外部情報Le(x1k)を行数Mと同じだけ用意した別のメモリバンクに記憶する。たとえば、データ番号kが(k  mod  M  =  0)となるデータ(N個)をメモリバンク１に、データ番号kが(k  mod  M  =  1)となるデータ(N個)をメモリバンク２に、データ番号kが(k  mod  M  =  2)となるデータ(N個)をメモリバンク３に、…、と順に記憶しておく。M個のメモリバンクのアクセスは周期的に生じており、並列化するには各処理の最初にアクセスするメモリバンクが重ならなければ、処理中に同じメモリバンクにアクセスすることはない。M×N個の系列をM分割すると、先頭からN個ずつ区切られ、NとMは互いに素な関係にあるため、各並列処理で最初にアクセスするメモリバンクB(i)は、
B(i)  =  N×i  mod  M  (0≦i≦M-1)
で表すことができ、いずれのB(i)についても同じになることはない。B(i)の式は、互いに素な関係により疑似乱数を生成する手段と同じ原理となる。
【０１１７】
また、並列数がM未満のM'でもメモリバンクのアクセスが衝突することはなく、並列処理を行うことが可能である。先頭からWビットづつM'個に区切り、M'並列する場合に、各並列処理で最初にアクセスするメモリバンクB(i)は、
B(i)=W×i  mod  M  (0≦i≦M-1)
となる。WはMと互いに素であれば別のメモリバンクにアクセスし、Mが32の場合にWは奇数ならば互いに素となるため、メモリバンク数M以下の正の整数1≦W≦Mでの並列化が可能となる。
【０１１８】
また、本実施の形態では素数Pとその原始元G0を用いて疑似乱数系列を生成したが、実施の形態２のように素数Pと互いに素な整数で疑似乱数系列を生成しても良い。また、実施の形態４のようにプルーニングを用いてインタリーバの大きさを調整せず、入力ビットに既知のビットを挿入してインタリーバの大きさと同じ入力ビット数として符号化しても良い。
【０１１９】
以上のように、本実施の形態によれば、列数と行数を互いに素な関係になるようにラテン方陣またはラテン長方形構造を持つLRIインタリーバを設計することとした。これにより、並列処理の選択肢が増え、高速処理が必要な復号回路の実装において、並列処理も選択肢を広くとることができる。
【０１２０】
実施の形態８．
つづいて、実施の形態８の通信システムについて説明する。なお、本実施の形態のシステムにおいて、送信装置および受信装置の構成については、前述した実施の形態２と同様である。以下、実施の形態２と異なる処理について説明する。
【０１２１】
具体的には、実施の形態８のインタリーブパターン生成アルゴリズムにおいては、＜ステップ４＞の処理が実施の形態２と異なっている。
【０１２２】
＜ステップ４＞
M×Nの入力行列Uj(i)を用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛Uj(i)=j+M×i｝
｝
【０１２３】
つづいて、上記実施の形態８のインタリーブパターン生成アルゴリズムによりインタリーブパターンを生成した場合の、復号処理の一例について説明する。復号過程において、受信信号y1kと外部情報Le(x1k)を行数Mと同じだけ用意した別のメモリバンクに記憶する。たとえば、データ番号kが(k  mod  M  =  0)となるデータ(N個)をメモリバンク１に、データ番号kが(k  mod  M  =  1)となるデータ(N個)をメモリバンク２に、データ番号kが(k  mod  M  =  2)となるデータ(N個)をメモリバンク３に、…と順に記憶しておく。M個のメモリバンクのアクセスは周期的に生じており、並列化するには各処理の最初にアクセスするメモリバンクが重ならなければ、処理中に同じメモリバンクにアクセスすることはない。M×N個の系列をW分割して並列処理する場合、先頭からW個ずつ区切られ、各並列処理で最初にアクセスするメモリバンクB(i)は、
B(i)  =  N×i  mod  W
で表すことができるので、Nと互いに素なWのときには並列処理が可能となる。
【０１２４】
また、上記とは違い、列数Nと同数のメモリバンクを用意し、先頭からM個のデータ(0≦k≦M-1)をメモリバンク１に、次のM個のデータ(M≦k≦2×M-1)をメモリバンク２に、次のM個のデータ(2×M≦k≦3×M-1)をメモリバンク３に、…と順に記憶しておくことで、列数Nと同数もしくはNの約数の並列化が可能となり、メモリバンクを列数の約数N'と同数用意すれば、その同数N'もしくはN'の約数だけ並列化が可能であることを説明する。列数Nのメモリバンクがある場合、インタリーブ前にはメモリバンクごとにアクセスして復号処理が行われるので、同じメモリバンクにアクセスすることはない。インタリーブ後の処理では、インタリーブ前のように順序だっておらず、生成した乱数系列に基づいてメモリバンクへのアクセスが発生するが、ラテン方陣・ラテン長方形構造に基づくため、同じメモリバンクにアクセスすることはない。同様に列数Nの約数で並列化する場合にも、「N  =  N'  mod  d」となる約数N'，分割数dを用いて、N並列での一処理をd回シリアルに行うことで、N'並列が可能となる。N'のメモリバンクを使って並列化する場合も同様である。
【０１２５】
また、実施の形態４のようにプルーニングを用いてインタリーバの大きさを調整せず、入力ビットに既知のビットを挿入してインタリーバの大きさと同じ入力ビット数として符号化しても良い。
【０１２６】
以上のように、本実施の形態によれば、ラテン方陣またはラテン長方形構造を持つLRIインタリーバの基本疑似乱数を、列数と互いに素な整数を用いて生成することとした。これにより、列数の選択枝が増え、良好な特性を持つ組み合わせを検索することが容易となる。
【０１２７】
実施の形態９．
つづいて、実施の形態９の通信システムについて説明する。なお、本実施の形態のシステムにおいて、送信装置および受信装置の構成については、前述した実施の形態６と同様である。以下、実施の形態６と異なる処理について説明する。
【０１２８】
具体的には、実施の形態９のインタリーブパターン生成アルゴリズムにおいては、＜ステップ１＞，＜ステップ５＞の処理が実施の形態６と異なっている。
【０１２９】
＜ステップ１＞
（１）パラメータを設定する。
L                ：入力ビット数
N                ：インタリーブ行列の列数（素数）
M                ：インタリーブ行列の行数
s                ：基本疑似乱数系列読み出し時の開始位置シフト数
（２）Nの原始元を選択する。
G0                ：Ｎの原始元
【０１３０】
（３）入力ビット数Ｌに対応した、素数P，素数Pの原始元G0のリストを定義する。ここでは、L=40〜8224に対応して、素数P（Pの原始元G0）は、｛7(3),11(2),13(2),17(3),19(2),23(5),29(2),31(3),37(2),41(6),43(3),47(5),53(2),59(2),61(2),67(2),71(7),73(5),79(3),83(2),89(3),97(5),101(2),103(5),107(2),109(6),113(3),127(3),131(2),137(3),139(2),149(2),151(6),157(5),163(2),167(5),173(2),179(2),181(2),191(19),193(5),197(2),199(3),211(2),223(3),227(2),229(6),233(3),239(7),241(7),251(6),257(3)｝を用意する。
【０１３１】
Ａ）L≦930のとき
１）列数Nを決める。
P*(P-1)≧Lとなる最小の素数Pを検索し、列数N(=P)、行数M(=P-1)とする。
２）Pの原始元G0をリストから読む。
Ｂ）L>930のとき
１）列数Nを決める。
行数M=32とする。
M*P≧Lとなる最小の素数Pを検索し、列数N(=P)とする。
２）Pの原始元G0をリストから読む。
【０１３２】
＜ステップ５＞
M個の疑似乱数系列を生成する。行数Mと互いに素な整数Qを用意し、
For  j  =  0,…,M-1  ｛D(j)=j×Q  mod  M｝
疑似乱数D(j)に基づいて、M×Nの出力行列U'j(i)を、CLj(i)を用いて用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛U'j(i)=U(D(j))(CL(D(j))(i))｝
｝
【０１３３】
以上のように、本実施の形態によれば、列数と行数を互いに素な関係になるようにラテン方陣またはラテン長方形構造を持つLRIインタリーバを設計することとした。これにより、並列処理の選択肢が増え、高速処理が必要な復号回路の実装において、並列処理も選択肢を広くとることができる。
【０１３４】
実施の形態１０．
つづいて、実施の形態１０の通信システムについて説明する。なお、本実施の形態のシステムにおいて、送信装置および受信装置の構成については、前述した実施の形態８と同様である。以下、実施の形態８と異なる処理について説明する。
【０１３５】
具体的には、実施の形態１０のインタリーブパターン生成アルゴリズムにおいては、＜ステップ５＞の処理が実施の形態８と異なっている。
【０１３６】
＜ステップ５＞
M個の疑似乱数系列を生成する。行数Mと互いに素な整数Qを用意し、
For  j  =  0,…,M-1  ｛D(j)=j×Q  mod  M｝
疑似乱数D(j)を用いて、M×Nの出力行列U'j(i)を、CLj(i)を用いて用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛U'j(i)=U(D(j))(CL(D(j))(i))｝
｝
【０１３７】
なお、本実施の形態では行数Nと互いに素な正整数を用いて行内置換用の疑似乱数系列を生成したが、実施の形態１のように素数Pの原始元を用いて疑似乱数系列を生成しても良い。
【０１３８】
以上のように、本実施の形態によれば、列数と行数を互いに素な関係になるようにラテン方陣またはラテン長方形構造を持つLRIインタリーバを設計することとした。これにより、並列処理の選択肢が増え、高速処理が必要な復号回路の実装において、並列処理も選択肢を広くとることができる。
【０１３９】
実施の形態１１．
つづいて、実施の形態１１の通信システムについて説明する。なお、本実施の形態のシステムにおいて、送信装置および受信装置の構成については、前述した実施の形態６と同様である。以下、実施の形態６と異なる処理について説明する。
【０１４０】
ここで、実施の形態１１のインタリーブパターン生成アルゴリズムを示す。
【０１４１】
＜ステップ１＞
（１）パラメータを設定する。
L                ：入力ビット数
N                ：インタリーブ行列の列数（素数）
M                ：インタリーブ行列の行数
（２）Nの原始元を選択する。
G0                ：Ｎの原始元
【０１４２】
（３）入力ビット数Ｌに対応した、素数P，Pの原始元G0のリストを定義する。素数Pの原始元は、
(G0)i  mod  P  (0≦i≦P-1)
と計算して、0≦i≦P-1のすべての数が現れる場合のG0である。たとえば、P=7では、G0=3とG0=5が原始元となる。ここでは、L=40〜8224に対応してリストを用意するが、説明の便宜上、一部を省略して記すこととする。（素数Ｐ:原始元）＝｛（7:3,5),(11:2,6,7,8),(13:2,6,7,11),(17:3,5,6,7,10,11,12,14),(19:2,3,10,13,14,15),(23:5,7,10,11,14,15,17,19,20,21),(29:2,3,8,10,11,14,15,18,19,21,26,27),(31:3,11,12,13,17,21,22,24),(37:2,5,13,15,17,18,19,20,22,24,32,35),(41:6,7,11,12,13,15,17,19,22,24,26,28,29,30,34,35),(43:3,5,…),(47:5,10,…),(53:2,3,…),(59:2,6,…),(61:2,6,…),(67:2,7,…),(71:7,11,…),(73:5,11,…),(79:3,6,…),(83:2,5,…),(89:3,6,…),(97:5,7,…),(101:2,3,…),(103:5,6,…),(107:2,5,…),(109:6,10,…),(113:3,5,…),(127:3,6,…),(131:2,6,…),(137:3,5,…),(139:2,3,…),(149:2,3,…),(151:6,7,…),(157:5,6,…),(163:2,3,…),(167:5,10,…),(173:2,3,…),(179:2,6,…),(181:2,10,…),(191:19,21…),(193:5,10,…),(197:2,3,…),(199:3,6,…),(211:2,3,…),(223:3,5,…),(227:2,5,…),(229:6,7,…),(233:3,5,…),(239:7,13,…),(241:7,13,…),(251:6,11,…),(257:3,5,…)｝となる。
【０１４３】
Ａ）L≦930のとき
１）列数Nを決める。
P*(P-1)≧Lとなる最小の素数Pを検索し、列数N(=P)，行数M(=P-1)とする。
２）リストから復号性能の高いPの原始元G0を選ぶ。
Ｂ）L>930のとき
１）列数Nを決める。
行数M=32とする。
M*P≧Lとなる最小の素数Pを検索し、列数N(=P)とする。
２）リストから復号性能の高いPの原始元G0を選ぶ。
【０１４４】
＜ステップ２＞
基本疑似乱数系列を生成する。
C(0)  =  1
For  i  =  0,…,N-3  ｛C(i+1)= G0×C(i)  mod  N｝
C(N-1)  =  0
【０１４５】
＜ステップ３＞
系列C(・)を１つずつシフトして、行列CLj(i)を構成する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛CLj(i)=C(i+j  mod  N)｝
｝
【０１４６】
＜ステップ４＞
M×Nの入力行列Uj(i)を用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛Uj(i)=i+N×j｝
｝
【０１４７】
＜ステップ５＞
M×Nの出力行列U'j(i)を、CLj(i)を用いて用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛U'j(i)=U(M-1-j)(CL(M-1-j)(i))｝
｝
【０１４８】
＜ステップ６＞
出力系列u(k)を列順に読み出すことで生成する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛u(j+M×i)=U'j(i)｝
｝
【０１４９】
＜ステップ７＞
プルーニング
用意した行列の大きさと情報長に差がある場合には、情報長を超える大きさを持つ出力値（u(k)≧K）を削除する。
【０１５０】
なお、ステップ２のランダム系列は以下のように生成しても良い。
＜ステップ２＞
For  i  =  0,…,N-2  ｛C(i)=(G0)i  mod  N｝
C(N-1)  =  0
【０１５１】
復号過程において、受信信号y1kと外部情報Le(x1k)を行数Mと同じだけ用意した別のメモリバンクに記憶する。データ番号kが(k  mod  M  =  0)となるデータ(N個)をメモリバンク１に、データ番号kが(k  mod  M  =  1)となるデータ(N個)をメモリバンク２に、データ番号kが(k  mod  M  =  2)となるデータ(N個)をメモリバンク３に、…と順に記憶しておく。M個のメモリバンクのアクセスは周期的に生じており、並列化するには各処理の最初にアクセスするメモリバンクが重ならなければ、処理中に同じメモリバンクにアクセスすることはない。M×N個の系列をM分割すると、先頭からN個ずつ区切られ、NとMは互いに素な関係にあるため、各並列処理で最初にアクセスするメモリバンクB(i)は、
B(i)  =  N×i  mod  M  (0≦i≦M-1)
で表すことができ、いずれのB(i)についても同じになることはない。B(i)の式は互いに素な関係を用いて、疑似乱数を生成する手段と同じ原理である。
【０１５２】
また、並列数がM以下でもメモリバンクのアクセスが衝突することはなく、並列処理を行うことが可能である。先頭からN'個づつW個に区切り、W並列する場合に各並列処理で最初にアクセスするメモリバンクB(i)は、
B(i)  =  W×i  mod  M  (0≦i≦M-1)
となる。WはMと互いに素であれば別のメモリバンクにアクセスし、Mが32の場合にWは奇数ならば互いに素となるため、メモリバンク数M以下の正の整数1≦W≦Mでの並列化が可能となる。
【０１５３】
また、ステップ４は、
＜ステップ４＞
M×Nの入力行列Uj(i)を用意する。
For  j  =  0,1,…,M-1  ｛
For  i  =  0,1,…,N-1  ｛Uj(i)=j+M×i｝
｝
としても良い。
【０１５４】
また、本実施の形態では、素数Pとその原始元G0を用いて疑似乱数系列を生成したが、実施の形態２のように素数Pと互いに素な整数で疑似乱数系列を生成しても良い。また、実施の形態４のようにプルーニングを用いてインタリーバの大きさを調整せず、入力ビットに既知のビットを挿入してインタリーバの大きさと同じ入力ビット数として符号化しても良い。
【０１５５】
以上のように、本実施の形態によれば、列数と行数を互いに素な関係になるようにラテン方陣またはラテン長方形構造を持つLRIインタリーバを設計することで、並列処理の選択肢が増え、高速処理が必要な復号回路の実装において、並列処理も選択肢を広くとることができる効果がある。また、各行で用いる乱数系列は、基本疑似乱数系列読み出し時の開始位置を１つずつシフトするだけで良いので実装が容易であり、素数Pに対して最小な原始元１つではなく複数の原始元、もしくは復号性能の良い最小でない原始元を用いることで、高い性能を得ることができる。
【産業上の利用可能性】
【０１５６】
以上のように、本発明にかかる通信装置は、ターボ符号等の誤り訂正符号を用いたすべての通信装置に適用可能である。
【図面の簡単な説明】
【０１５７】
【図１】本発明にかかる通信装置の構成例を示す図である。
【図２−１】本発明にかかるターボ符号インタリーバと従来例との性能比較を示す図である。
【図２−２】本発明にかかるターボ符号インタリーバと従来例との性能比較を示す図である。
【図２−３】本発明にかかるターボ符号インタリーバと従来例との性能比較を示す図である。
【図３−１】ターボ符号化器の構成例を示す図である。
【図３−２】ターボ符号化器の構成例を示す図である。
【図４】ターボ復号器の構成例を示す図である。
【図５】本発明にかかる通信装置の構成例を示す図である。
【符号の説明】
【０１５８】
１  ターボ符号化器
２，２ａ  インタリーバ生成器
３  変調器
４  復調器
５  ターボ復号器
６  通信路
１１  ビット調整器
１２  パンクチャ器
１３  デパンクチャ器
１４  ビット調整器
１０１  第１の再帰的組織畳込み符号化器
１０２  インタリーバ
１０３  第２の再帰的組織畳込み符号化器
１１１  第１の復号器
１１２，１１６  加算器
１１３，１１４  インタリーバ
１１５  第２の復号器
１１７  デインタリーバ
１１８  判定器
【図１】
2008160169.tif 000004
【図２−１】
2008160169.tif 000005
【図２−２】
2008160169.tif 000006
【図２−３】
2008160169.tif 000007
【図３−１】
2008160169.tif 000008
【図３−２】
2008160169.tif 000009
【図４】
2008160169.tif 000010
【図５】
2008160169.tif 000011