(57)【特許請求の範囲】
【請求項１】
可変的な入力情報ビットを受信する受信ポートと、情報ビットを出力する出力ポートと、
予め決定された数の遅延メモリを有し、入力ポートから受信された入力情報ビットを符号化し、かつ、第１パリティビットを生成する第１構成符号器と、
入力ポートから受信された入力情報ビットをインタリービングするインタリーバと、
予め決定された数の遅延メモリを有し、インタリービングされた情報ビットを符号化し、かつ、第２パリティビットを生成する第２構成符号器と、
データ伝送率を調整するために、第１パリティビットおよび第２パリティビットのうちの一部を穿孔する穿孔機と
から構成され、
第１構成符号器および第２構成符号器の各々は、構成符号器をターミネーションするために、メモリの数に等しい数のテールビットを生成し、かつ、該テールビットは、情報ビットの出力ポート上で伝送される
ことを特徴とするチャネル符号化装置。
【請求項２】
インタリーバが循環インタリーバであることを特徴とする請求項１記載のチャネル符号化装置。
【請求項３】
インタリーバが、入力情報の大きさに対応するホップ変数に基づいて、循環インタリービングを行うことを特徴とする請求項１記載のチャネル符号化装置。
【請求項４】
インタリーバが、入力情報の大きさと入力情報の大きさに対応するホップ変数とを貯蔵する手段を有することを特徴とする請求項３記載のチャネル符号化装置。
【請求項５】
インタリーバが、入力情報の大きさに対応するホップ変数と入力情報の順序とに基づいて、循環インタリービングを行うことを特徴とする請求項３記載のチャネル符号化装置。
【請求項６】
ホップ変数と入力情報ビットの順序に関する情報との積を循環大きさで除算することによって得られた余りを用いて、循環インタリービングが行われることを特徴とする請求項５記載のチャネル符号化装置。
【請求項７】
循環インタリービングが下記の数式によって行われることを特徴とする請求項６記載のチャネル符号化装置。
for(i=0;i<SIZE;i++)
new addr[i]=(p*i+STEP) mod SIZE
ここで、ｉは入力情報ビットの順序、ｐは循環インタリービングのためのホップ変数、ＳＴＥＰは‘０’を含むスタート位置、new addr[]は対角インタリービングされた情報ビットの新規のアドレス、ＳＩＺＥは循環大きさを示す。
【請求項８】
循環大きさが入力情報の大きさと同一であることを特徴とする請求項７記載のチャネル符号化装置。
【請求項９】
循環インタリービングが下記の数式によって行われることを特徴とする請求項６記載のチャネル符号化装置。
d=GCD(P,SIZE);
for(k-j=0;j<d;j++)
for(i=0;i<SIZE/d;i++,k++)
new addr[k]=((P*i+STEP)+j)mod SIZE
ここで、ＳＩＺＥは循環大きさ、ｐは循環インタリービングのためのホップ変数、ＳＴＥＰは‘０’を含むスタート位置、ＧＣＤは最大公約数、new addr[]は対角インタリービングされた情報ビットの新規のアドレス、ｉ，ｊ，ｋはインデックスを示す。
【請求項１０】
入力情報とパリティとが各々別に穿孔されることを特徴とする請求項１記載のチャネル符号化装置。
【請求項１１】
入力情報、第１パリティ及び第２パリティが全て穿孔されるのではないことを特徴とする請求項１記載のチャネル符号化装置。
【請求項１２】
第１パリティ及び第２パリティが全て穿孔されるのではないことを特徴とする請求項１１記載のチャネル符号化装置。
【請求項１３】
第１構成符号器と第２構成符号器とを有するチャネル符号器での使用のためのチャネル符号化方法であって、
第１構成符号器によって入力情報ビットの第１パリティを生成する過程と、
入力情報ビットをインタリービングする過程と、
インタリービングされた入力情報ビットの第２パリティを第２構成符号器によって生成する過程と、
第１構成符号器内のメモリを初期化するための第１テールビットを生成する過程と、
第２構成符号機内のメモリを初期化するための第２テールビットを生成する過程と、
フレームの終わりに、第１構成符号器の入力を入力情報ビットから第１テールビットへ切り換え、かつ、第２構成符号器の入力をインタリービングされた入力情報ビットから第２テールビットへ切り換える過程と
を備えることを特徴とするチャネル符号化方法。
【請求項１４】
第１テールビットと第２テールビットとを多重化する過程
を更に備えることを特徴とする請求項１３記載のチャネル符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信システムの適用形チャネル符号化方法及び装置に関し、特に、音声及びデータ伝送のための適応形チャネル符号化方法及び装置に関する。
【背景技術】
【０００２】
ターボ符号器(turbo encoder)は、Ｎ情報ビットのフレームからなる入力を二つの簡単な構成符号器(constituent encoder)を用いてパリティシンボル(parity symbol)を発生するシステムであって、並列及び直列構造で構成できる。そして、前記ターボ符号器の構成符号は、循環体系的たたみ込み符号(Recursive Systematic Convolutional code)を用いる。
【０００３】
図１は、従来の並列構造を有するターボ符号器の構成を示す図であって、Berrouによって発明された米国特許番号第５,４４６,７４７号に開示してある。前記図１のような構成を有するターボ符号器は、第１構成符号器１１と第２構成符号器１３との間にインタリーバ１２が連結されてなる。そして、前記インタリーバ１２は、入力される情報ビットのフレーム長さＮと同一な大きさを有し、前記第２構成符号器１３に入力される情報ビットの順序を変えることによって、情報ビット間の相関(correlation)を減らす。図２は、従来の直列構造を有するターボ符号器の構造を示す図であって、第１構成符号器１１と第２構成符号器１３との間にインタリーバ１２が連結されてなる。
【０００４】
これらターボ符号器は、宇宙通信(space communication)に使用されてきたターボ符号を生成し、前記構成符号器１１，１３は、拘束長が９(Ｋ＝９)である従来のたたみ込み符号に比べて拘束長は短いが、インタリーバ１２に使用されるメモリが非常に大きいために、復号時非常に長い時間遅延を有する。
【０００５】
前記図１のような並列構造のターボ符号器の出力を復号するターボ復号器は、図３のような構成を有し、図１のターボ符号器と同様に、前記Berrouによって発明された米国特許番号第５,４４６,７４７号に開示してある。そして、前記図２のような直列構造のターボ符号器の出力を復号するターボ復号器は、図４のような構成を有し、Benedettoが発表した論文に開示してある(IEEE Electronics Letters.June 1996,Vol.32 No.13)。
【０００６】
前記図３の並列構造のターボ復号器は、反復復号アルゴリズム(iterative decoding algorithm)を用いて受信されたフレーム単位に入力データを反復復号することによって、ビットエラー率(Bit Error Rate：ＢＥＲ)の性能を有効に向上させるという長所がある。そして、前記インタリーバ３２３は、第１復号器３１９で訂正されなかったバースト誤りパターン(burst error pattern)を分散させた後、第２復号器３２７で前記バースト誤りパターン訂正が行われるようにして誤り訂正能力を向上させる。
【０００７】
前記反復復号とは、特定な過程を通じて復号されたシンボルを再び復号することであって、派生される付加情報を用いて反復復号を行うと、優秀な復号性能が得られる。前記反復復号を行うためのアルゴリズムには、ＳＯＶＡ(Soft-Output Viterbi Algorithm：Proceedings of IEEE Vehnicular Technology Conference,pp 941-944.May 1993.)とＭＡＰ(Maximum A Posteriori Probability：IEEE Transactions on Information Theory,pp 429-445,Vol.42 No.２ March 1996.)がある。前記ＳＯＶＡアルゴリズムは軟判定(soft decision)値を出力するビタビアルゴリズムの変形であって、符号語(code word)の誤りを最小化し得る。一方、前記ＭＡＰアルゴリズムは、シンボル誤りを最小化し得るアルゴリズムである。
【０００８】
前記図３の復号器では、受信されるパリティシンボルｙｋが図１の第１構成符号器１１から受信された場合にはデパンクチャ(depuncturer)３１３の出力ｙ１ｋ＝ｙｋ、ｙ２ｋ＝０になり、パリティシンボルｙｋが図１の第２構成符号器１３から受信される場合には、ｙ１ｋ＝０、ｙ２ｋ＝ｙｋになる。そして、ｚｋ＋１は反復復号アルゴリズムで付加情報として使用される軟判定シンボルであって、次の反復復号時の入力として用いられる。最終復号段階で前記ｚｋ＋１を硬判定(hard decision)した値が最終的に望むd^ｋになる。前記ターボ符号の性能は、インタリーバの大きさ、インタリーバの構造及び反復復号回数によって決定される。
【０００９】
前記図１に示すように、ターボ符号器の内部にはインタリーバ１２を備える。前記インタリーバ１２によってターボ符号化／復号化がフレーム単位に行われる。従って、図３に示すように、ターボ符号の複雑度(complexity)は、第１反復復号器３１９及び第２反復復号器３２７に必要なメモリのフレーム大きさと構成符号器１１，１３の構成符号の状態数(state number)との積に比例する。前記ターボ符号は、通常非常に大きいフレームを使用しているために、音声及びデータの伝送には適用し難かった。より良好の性能を得るために前記ターボ符号器の構成符号の状態数を増加させると、前記図３の第１及び第２復号器の複雑度はその分だけ増加することになる。
【００１０】
前記図３のような構造を有する復号器でバースト誤りが生じた場合、前記第１反復復号器３１９の出力は相関を有し、従って、次の段階の復号過程で第２反復復号器３２７は相関された入力のために正確な復号が行えないことになる。従って、全体ブロックには誤りが存在し、これは次の復号過程でも訂正不可能になる。従って、反復復号を行う符号では１フレーム内のバースト誤りを相関が無いようによく分散させられるインタリーバ及びデインタリーバを使用するのが必須のこどである。
【００１１】
従って、相関を遥かに低減できるランダムインタリーバを使用すると、ターボ符号は非常に優秀な性能を示す。しかし、フレームの大きさが小さい場合は、ランダムインタリーバを使用しても、バースト誤りを相関がないよう十分に分離させ難く、ランダムインタリーバに必要なルックアップテーブルも必要になる。従って、音声伝送や伝送率の低いデータ伝送では、構成符号の状態数が小さい上に、時間遅延を最小化できるフレーム大きさ及び構造化したインタリーバを使用しなければならない。要するに、従来のターボ符号で使用する構成符号の拘束長と大きいインタリーバでは前記音声及びデータ伝送を行うのが非常に難しい。にも拘わらず、前記ターボ符号器の長所を生かして通信システムの符号器及び復号器を具現しようとする努力が続いている。
【００１２】
従来の通信システムで使用するたたみ込み符号に比べてその性能が同一又は優秀である上に、複雑度の低いターボ符号器を具現するためには、構成符号の状態数が小さく、時間遅延を最小化でき、且つ優秀な性能を有するインタリーバを使用すべきである。一般に、ターボ符号器に使用されるインタリーバ(図１の１２又は図２の１２)の性能はその大きさに比例する。しかし、ターボ符号ではフレーム大きさを増加させるには限界がある。この場合は、ブロック符号の観点からターボ符号の最小ハミング距離(minimum Hamming distance)を最大化させるインタリーバを使用するのが望ましい。フレーム大きさが小さい場合には、構造的インタリーバを用いることによって前記問題点を解決できる。
【発明の開示】
【課題を解決するための手段】
【００１３】
従って、本発明の目的は、通信システムで、音声及び低い伝送率を有するデータを符号化できるターボ符号化方法及び装置を提供することにある。
本発明の他の目的は、通信システムで、入力されるデータフレームの大きさに拘わらずにインタリービングし得る対角インタリーバを用いる並列又は直列構造のターボ符号化方法及び装置を提供することにある。
本発明のさらに他の目的は、入力されるデータフレームの大きさに拘わらずにインタリービングし得る循環インタリーバを用いる並列又は直列構造のターボ符号化方法及び装置を提供することにある。
本発明のさらに他の目的は、音声及びデータ信号をターボ符号に符号化する装置で、テールビットとテールビットによって生成されるパリティビットをチャネルに伝送できる方法及び装置を提供することにある。
本発明のさらに他の目的は、音声及びデータ信号をターボ符号に符号化する装置で、データ及びパリティ情報を穿孔してデータ伝送率を調整できる方法及び装置を提供することにある。
【００１４】
前記の目的を達成するために、本発明の一様態によるターボ符号化装置が、入力される情報ビットを符号化する複数の構成符号器と、前記符号器のうち少なくとも一つの構成符号器の入力端に連結され、可変的なフレーム大きさに対応する行列情報を貯蔵するテーブルを備え、前記入力情報ビットのフレーム大きさに対応する行列情報に基づいて情報ビットを対角インタリービングする対角インタリーバと、から構成される。
【００１５】
さらに、本発明の他の様態によるターボ符号化装置が、入力される情報ビットを符号化する複数の構成符号器と、前記符号器のうち少なくとも一つの構成符号器の入力端に連結され、可変的フレーム大きさに対応するホップ及びステップ情報を貯蔵するテーブルを備え、入力情報ビットのフレーム大きさに対応する前記ホップ及びステップ情報に基づいて情報ビットを循環インタリービングする循環インタリーバと、から構成される。
【００１６】
また、本発明のさらに他の様態によるターボ符号化装置が、入力される情報ビットを符号化する複数の構成符号器と、入力情報をフレーム大きさに基づいてインタリービングし、前記符号器のうち少なくとも一つの構成符号器の入力端に連結するインタリーバと、前記構成符号器の数に対応するよう備えられ、フレーム終了時構成符号器に入力される情報ビットを遮断し、構成符号器のメモリ装置の値を分析して入力データのフレームを終端させるテールビットを生成するテールビット生成器と、から構成される。
【００１７】
さらに、本発明のさらに他の様態によるターボ符号化装置において、複数の構成符号器は入力情報ビットを符号化し、インタリーバは伝送される入力情報ビットをインタリービングして前記少なくとも一つの構成符号器の入力端に連結する。また、テールビット生成器は、前記構成符号器の数に対応するよう備えられ、フレーム終了時構成符号器に入力される情報ビットを遮断し、構成符号器のメモリ装置の値を分析して入力データのフレームを終端させるテールビットを生成する。第１穿孔器は前記入力情報ビットを穿孔し、第２穿孔器は前記構成符号器の出力を穿孔して前記符号化したデータの伝送率を調整する。
【発明を実施するための最良の形態】
【００１８】
本発明の実施形態では、説明の便宜上、並列鎖状循環構造を有するターボ符号器(parallel concatenated recursive turbo encoder)の構成について説明する。図５及び図６は、本発明の実施形態によるターボ符号器の構成を示す図である。ここで、符号器４１０，４２０は、構成符号器であって、前記図１及び図２の構成符号器と同様に、受信される情報ビットｄｋを符号化してパリティシンボルＹｋを生成する。また、対角インタリーバ(diagonal interleaver)４３２と循環インタリーバ(circular shifting interleaver)４３４は、本発明の第１及び第２実施形態によるインタリーバであって、以下の説明では特定インタリーバを称する場合を除いてインタリーバ４３０と通称するものとする。
【００１９】
前記図５及び図６を参照すれば、前記情報ビットｄｋは、第１構成符号器４１０に入力される同時に、インタリーバ４３０に入力される。前記インタリーバ４３０は前記情報ビットの順序を変えて第２構成符号器４２０に入力させる。前記インタリーバ４３０は、入力情報ビットｄｋが符号化した後出力されるシーケンス(Ｘｋ、Ｙｋ)の最小ハミング距離が最大になるインタリーバを使用する。また、チャネル符号器に入力されるデータのフレーム大きさは、ＣＲＣ(Cyclic Redundancy Check)ビット及びその他の制御ビットが前記データに追加されるために可変的である。もし、強制に入力データフレームの大きさを固定させようとする場合は、フレーム大きさとインタリーバ大きさとの差だけのダミービット(dummy bit)をさらに加えなけばならない。しかし、前記ダミービットはシステムの性能改善とはなんの係わりも無いので可能な限り少ない方が望ましい。従って、インタリーバ４３０は、優秀な性能を有すると共に、入力データフレーム大きさと関係のあるパラメータの変化に拘わらずにうまく動作されるものでなければならない。
【００２０】
図７は、図５及び図６に示した対角インタリーバ４３２及び循環インタリーバ４３４の構成を示している。前記対角インタリーバ４３２及び循環インタリーバ４３４は、可変的なフレーム大きさを有する情報ビットが入力される時、該当フレーム大きさを分析し、フレーム大きさ分析結果に従ってシステム制御部から受信したインタリーバ関連パラメータに基づいて最適のインタリービング動作を行う。本発明の実施形態では前記対角インタリーバ４３２及び循環インタリーバ４３４を一つのインタリーバに結合した場合を説明しているが、ターボ符号器では対角インタリービング又は循環インタリービング中いずれか一つを使用することもできる。ここでは、前記対角インタリーバ４３２及び循環インタリーバ４３４をインタリーバ４３０と通称する。
【００２１】
前記図７を参照すれば、レジスタ５１１はシステム制御部(図示せず)から出力されるフレーム大きさ信号(frame size signal)とインタリーバ形態信号(interleaver type signal)を貯蔵する。対角インタリービングテーブル５１３は対角インタリービングを行う時、情報ビットのフレーム大きさに従って最適の対角インタリービング特性を有する行及び列の値Ｍ及びＮを貯蔵するテーブルである。即ち、可変的なフレーム大きさに受信される情報ビットを対角インタリービングする時、最適の対角インタリービング効果を有するＭ及びＮを実験的に測定して対角インタリービングテーブル５１３に貯蔵する。前記対角インタリービングテーブル５１３は、前記レジスタ５１１から出力されるフレーム大きさ信号に対応するＭ及びＮ値を出力する。対角インタリービング制御器５１７は、前記対角インタリービングテーブル５１３から出力されるＭ及びＮ値を受信し、設定された対角インタリービング方式で情報ビットをインタリービング出力するための読取りアドレス(read address)を発生する。
【００２２】
循環インタリービングテーブル５１５は、循環インタリービングを行う時、情報ビットのフレーム大きさに従って最適の循環インタリービング特性を有するホップ変数(hop parameter)及びステップ変数(step parameter)値Ｐ及びＳＴＥＰを貯蔵するテーブルである。即ち、可変的なフレーム大きさに受信される情報ビットを循環インタリービングする時、最適の循環インタリービング効果を有するＰ及びＳＴＥＰ変数を実験的に測定して循環インタリービングテーブル５１５に貯蔵する。前記循環インタリービングテーブル５１３は前記レジスタ５１１から出力されるフレーム大きさ信号に対応するＰ及びＳＴＥＰ値を出力する。循環インタリービング制御器５１９は、前記循環インタリービングテーブル５１５から出力されるＰ及びＳＴＥＰ値を受信し、設定された循環インタリービング方式で情報ビットをインタリービング出力するための読取りアドレスを発生する。マルチプレクサ５２１は、前記対角インタリービング制御器５１７及び循環インタリービング制御器５１９から出力される読取りアドレスを受信し、前記レジスタ５１１から出力されるインタリーバ形態信号に基づいて対応するインタリービング方式のアドレスを選択して読取りアドレスとして出力する。メモリ５２３は、前記情報ビットを順次に受信し、前記マルチプレクサ５２１から出力される読取りアドレスに基づいて貯蔵された情報ビットをインタリービング出力する。前記メモリ５２３は、前記情報ビットが最大の可変フレーム大きさを有するに十分な大きさに設計される。
【００２３】
前記図７の構成で、対角インタリーバ４３２を単独に具現する場合、レジスタ５１１、対角インタリービングテーブル５１３、対角インタリービング制御器５１７及びメモリ５２３で構成でき、この時、マルチプレクサ及び前記インタリーバ形態信号は使用しない。また、前記図７の構成で、循環インタリーバ４３４を単独に具現する場合、レジスタ５１１、循環インタリービングテーブル５１５、循環インタリービング制御器５１９及びメモリ５２３で構成でき、この時、マルチプレクサ及び前記インタリーバ形態信号は使用しない。
【００２４】
前記図７で、対角インタリービングテーブル５１３及び循環インタリービングテーブル５１５は、ＲＯＭ及びＲＡＭのようなメモリで具現でき、論理素子を結合して具現しても良い。また、前記対角インタリービング制御器５１７及び循環インタリービング制御器５１９は、論理素子を結合して具現することができ、デジタル信号プロセッサで具現しても良い。
【００２５】
図８及び図９は対角インタリービングの流れ図を例示しており、図１０及び図１１は循環インタリービングの流れ図を例示している。また、以下に説明されるインタリーバは入力バッファを備えていると仮定する。
【００２６】
前記図７のインタリーバ４３０の構成を参照して第１対角インタリービング〜第３対角インタリービング動作について調べてみる。
【００２７】
まず、図８は、第１対角インタリービングの動作を示す流れ図である。前記図８を参照すれば、第１対角インタリービングはＭ*Ｎの入力ビットシーケンスの順序を変える過程を含む。第１対角インタリービングでは、まず、情報ビットｄｋが入力されると、６１１段階で入力される情報ビットをメモリ５２３(図７)に順次的に貯蔵するためのアドレスold＿addr[k]に情報を貯蔵し、フレームデータの大きさｋを設定する。その後、６１３段階で、対角インタリービングを行うためのデータフレームの行及び列変数Ｍ*Ｎを決定する。即ち、対角インタリービングを行うために、前記入力フレームのデータ大きさ変数ｋに基づいて前記対角インタリービングテーブルから前記Ｍ及びＮ値を設定する。複数のＭ*Ｎ値は、ルックアップテーブルに貯蔵されて入力フレームの大きさｋに基づいて決定されることができ、入力フレームの大きさｋに基づいて最適のＭ*Ｎを計算しても良い。そして、６１５段階で、前記Ｍ及びＮ値の最大公約数が１[GCD(M,N)=1]であるかチェックする。この時、前記Ｍ及びＮの最大公約数(ＧＣＤ：Greatest Common Denominator)が１である場合は、６１７段階で下記の数式２９によって第１対角インタリービングのアドレスを演算する。
for(k=0;k<M*N-1;k++)
new addr[k]=(M-1-(k mod N))*N+(k mod N)  ……（２９）
【００２８】
前記数式２９のように出力バッファのアドレスを指定し、前記入力バッファに貯蔵された入力情報ビットをインタリービングして出力バッファに貯蔵する。
【００２９】
しかし、前記６１５段階で、前記Ｍ及びＮの最大公約数が１でないと[GCD(M,N)≠1]、６１９段階で第１対角インタリービング動作を中断し、終了する。
【００３０】
前記第１対角インタリービングで、まず、最初の前記入力バッファのold＿addr[k]に貯蔵されているＭ＝６、Ｎ＝５のシーケンスを{0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29}と仮定すれば、第１対角インタリービング後に出力バッファnew＿addr[k]に貯蔵されたシーケンスは{25 21 17 13 9 0 26 22 18 14 5 1 27 23 19 10 6 2 28 24 15 11 7 3 29 20 16 12 8 4}になる。
【００３１】
前記貯蔵された値をＭ*Ｎ行列で表現すると、入力されたデータと第１対角インタリービングした後出力されるデータは表１のようになる。
【００３２】
【表１】
0003730238.tif 000002
【００３３】
しかし、前記第１対角インタリービングはＭとＮの最大公約数が１である場合に限って可能である。しかし最大公約数(Ｍ，Ｎ)≠１である場合、例えばＭ＝６，Ｎ＝６の場合は、下記の表２のようにインタリービングが全くなされなく、同一のデータが重ね書き(overwrite)されてしまう。
【００３４】
【表２】
0003730238.tif 000003
【００３５】
第２対角インタリービング方式及び第３対角インタリービング方式は、Ｍ*Ｎ行列で表現される入力情報ビットシーケンスの順序を変える過程を含むが、最大公約数(Ｍ，Ｎ)＝１の場合の以外に、最大公約数(Ｍ，Ｎ)≠１である場合にもインタリービングできる構造である。
【００３６】
図９は、第２対角インタリービングの動作を示す流れ図である。前記図９を参照すれば、第２対角インタリービングは、Ｍ*Ｎ行列の入力ビットの順序を変えるものであって、ＭとＮの最大公約数が‘１’である場合と‘１’でない場合のいずれにも適用できる対角インタリービング方式である。第２対角インタリービング時、まず、情報ビットｄｋが入力されると、６３１段階で入力バッファのアドレスold＿addr[k]に情報を貯蔵し、フレームデータの大きさｋを設定する。ここで、前記ｋは入力されるフレームデータの大きさを示す変数である。その後、６３３段階で、対角インタリービングを行うためのデータフレームの行及び列変数Ｍ＊Ｎを決定する。前記Ｍ及びＮを設定した後、６３５段階で、下記の数式３０によって第２対角インタリービングのアドレスを演算する。
for(j=0;j<M;j++)
for(i=0;i<M;i++)
new addr[i+j+N]=i+(M-1-(i+j) mod M)*N  ……（３０）
ここで、ｉ及びｊは増加フレーム位置を示す。
【００３７】
前記数式３０のように出力フレームバッファのアドレスを指定し、前記入力バッファに貯蔵された入力情報ビットをインタリービングして出力バッファに貯蔵する。
【００３８】
最大公約数(Ｍ，Ｎ)＝１、例えばＭ＝６，Ｎ＝５の入力シーケンスに対応する前記第２対角インタリービングされた出力は下記の表３で示される。
【００３９】
【表３】
0003730238.tif 000004
【００４０】
また、最大公約数(Ｍ，Ｎ)≠１、例えばＭ＝６，Ｎ＝６である場合も下記の表４のようにインタリービングが正常に行われることが判る。
【００４１】
【表４】
0003730238.tif 000005
【００４２】
第３対角インタリービング方式で、対角インタリービング制御器５１７は下記の数式３１で具現される。
for(j=0;j<M;j++)
for(i=0;i<N;i++)
new addr[i+j+N]=i+((i+j) mod M)*N  ……（３１）
【００４３】
前記対角インタリーバ４３２を用いて入力シーケンスをマッピング(mapping)されるメモリアドレスに貯蔵した後、次の行又は列単位に順次にデータを読み取ったり、入力シーケンスを行又は列単位にメモリに順次に貯蔵した後、対角インタリーバ４３２によってアドレスから１ビットずつデータを読み取ってインタリービングを行うことができる。
【００４４】
デインタリービングはインタリーバで使用した方法の逆順で具現できる。
【００４５】
図１０は、循環インタリーバ４３４を用いて入力情報ビットを第１循環インタリービングする動作を示す流れ図である。本発明の実施形態による第１循環インタリービング動作は、入力シーケンスを一つの円(circle)に見なし、一定間隔にデータの順序を変えるものであって、入力シーケンスの長さに拘わらずにインタリービングが行える。
【００４６】
前記図１０を参照すれば、まず、情報ビットｄｋが入力されると、７１１段階で入力バッファのアドレスold＿addr[k]に情報を貯蔵し、フレームデータの大きさＳＩＺＥを設定する。その後、７１３段階で、Ｐ変数及びＳＴＥＰ変数を設定する。ここで、前記Ｐ変数はホップ(hop)間隔変数であって、循環インタリーバの性能を決定する。したがって、前記Ｐ変数は最適の効果を有するよう実験的に求める。また、前記ＳＴＥＰ変数は前記Ｐ変数によってホッピングされる位置から左側又は右側にデータをシフトさせる変数である。ここで、前記ＳＴＥＰ変数は整数になる。このようにＰ変数及びＳＴＥＰ変数を求めた後、７１５段階で前記ＰとＳＩＺＥの最大公約数が１[GCD(P,SIZE=1)]かチェックする。この時、Ｐ変数とＳＩＺＥ変数の最大公約数が１である場合には、７１７段階で、第１循環インタリービングアドレスを下記の数式３２によって演算する。
for(i=0;i<SIZE;i++)
new addr[i]=(p*i+STEP) mod SIZE  ……（３２）
【００４７】
前記数式３２で、ｉは入力データのフレーム大きさを示す変数であって、０からＳＩＺＥ(アドレスの数)まで変わる変数である。また、前記ＳＩＺＥはインタリーバの大きさであり、ｐは最大公約数(ＳＩＺＥ，ｐ)＝１を満足する任意の自然数であり、ＳＴＥＰは整数である。
【００４８】
例えば、最初の入力バッファold＿addr[k]に貯蔵されている、ＳＩＺＥ＝３０の入力シーケンスが{0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29}であれば、Ｐ＝１１、ＳＴＥＰ＝０の時、第１循環インタリービング後に出力バッファnew＿addr[k]に貯蔵されたシーケンスは{0 11 22 3 14 25 6 17 28 9 20 1 12 23 4 15 26 7 18 29 10 21 2 13 24 5 16 27 8 19}になる。前記貯蔵された値をＭ*Ｎ行列で表現すれば、下記の表５のようになる。
【００４９】
【表５】
0003730238.tif 000006
【００５０】
しかし、最大公約数(ＳＩＺＥ，ｐ)≠１である、ｐ＝６を用いる場合、前記図１０のような第１循環インタリービングを行うと、同一のデータが重ね書きされるためにインタリービングがなされない。
【００５１】
ここで、最初メモリの順次的なアドレスold＿addr[k]に貯蔵されているＳＩＺＥ＝３０であるシーケンスが入力され、Ｐ＝１１、ＳＴＥＰ＝０と仮定すれば、前記図１０のような第１循環インタリービング方式で前記入力シーケンスをインタリービングした結果が次の表６のようなＭ*Ｎ行列で表現される。
【００５２】
【表６】
0003730238.tif 000007
【００５３】
最大公約数(ＳＩＺＥ，ｐ)≠１の場合にもインタリービング可能な第２循環インタリービング方式が図１１に示されている。前記図１１に示した第２循環インタリービング方式は入力シーケンスをｄ*(ＳＩＺＥ/ｄ)の行列に見なし、列は第１循環インタリービングされ、行はブロックインタリービングされる方式である。
【００５４】
図１１は、第２循環インタリービングの動作を示す流れ図であって、ＰとＳＴＥＰ変数の最大公約数が１である場合と１でない場合のいずれの場合にも適用可能な循環インタリービング方式である。第２循環インタリービングの動作について調べてみれば、まず、情報ビットｄｋが入力されると、７２１段階でメモリの順次アドレスold＿addr[k]に情報を貯蔵し、フレームデータの大きさＳＩＺＥを設定する。その後、７２３段階で、循環インタリービングを行うためのホップ変数Ｐ及びステップ変数ＳＴＥＰを設定する。前記Ｐ及びＳＴＥＰ変数を設定した後、７２５段階で下記の数式３３によって第２循環インタリービングのアドレスを演算する。
【００５５】
次の数式３３において、ｉ及びｋは０からＳＩＺＥまでの数を示す変数である。ｊはアドレス変数であって、０からｄまでの数を示す。Ｐは循環インタリービングを行うためのホップ変数を示す。ＳＴＥＰは前記ホップ変数によって決定された位置からＳＴＥＰ変数だけ左側又は右側にデータをシフトしてスタート時点(start point)を決定するための変数である。
d=GCD(P,SIZE);
for(k-j=0;j<d;j++)
new addr[k]=((P*i+STEP)+j)mod SIZE  ……（３３）
【００５６】
前記数式３３において、(P*i+STEP)は循環インタリービング動作を示し、ｊはブロックインタリービング動作を示す。ＳＩＺＥは入力データのフレーム大きさ、ｐは任意の自然数、ＳＴＥＰは整数である。
【００５７】
ここで、ＳＩＺＥ＝３０、ｐ＝１１の第２循環インタリービング結果をＭ*Ｎ行列で示すと、下記の表７になる。
【００５８】
【表７】
0003730238.tif 000008
【００５９】
前記表７の結果は、表５の第１循環インタリービングの結果と同一である。しかし、最大公約数(ＳＩＺＥ，ｐ)≠１の場合は次のようになる。
【００６０】
【表８】
0003730238.tif 000009
【００６１】
前記循環インタリーバを用いて入力シーケンスをマッピングされるメモリアドレスに貯蔵した後、行又は列単位に順次にデータを読み取ったり、入力シーケンスを行又は列単位に順次にメモリに貯蔵した後、アドレスから１ビットずつデータを読み取る方法を用いてインタリービングし得る。
【００６２】
デインタリービングはインタリーバで使用した方法の逆順で具現される。
【００６３】
図１２は、本発明の第２実施形態による並列鎖状構造のターボ符号器で循環インタリーバの性能を示すグラフであって、構成符号の拘束長が３(Ｋ＝３)であり、入力フレーム大きさは１０４ビット、反復復号回数は８回、ＢＰＳＫ(Bi-Phase Shift Key)変調方式、ＡＷＧＮ(Additive White Gaussian Noise)環境におけるＢＥＲに関連して、広く用いられているブロックインタリーバ及びランダムインタリーバと循環インタリーバとを比較している。前記図１２に示すように、１０−５ＢＥＲで循環インタリーバのＥｂ／Ｎｏが３dB程度であり、ブロックインタリーバが３.４dBになる。従って、前記１０−５ＢＥＲで循環インタリーバがフロックインタリーバに比べて約０.４dB性能が改善されたことが判る。
【００６４】
図１３は、本発明の実施形態によるターボ符号器の構成を示す図である。
前記図１３を参照すれば、第１構成符号器４１０は、例えば拘束長が３(Ｋ＝３)である情報ビットを符号化して出力し、インタリーバ４３０は、前記情報ビットを設定された規則に基づいてインタリービングして情報ビットの順序を変える。このインタリーバ４３０は、前記図７と同様に構成することができ、この場合、前記第１〜第３対角インタリービング方式又は第１〜第２循環インタリービング方式で具現できる。第２構成符号器４２０は、拘束長が３(Ｋ＝３)である前記インタリーバ４３０の出力を符号化して出力する。
【００６５】
第１テールビット生成器４５０は、前記第１構成符号器４１０の入力端に連結される第１スイッチ４５５と、前記第１構成符号器４１０のメモリ素子４１２，４１３の出力を排他的論理和する排他的論理和器(exclusive OR gate)４５１と、前記排他的論理和器４５１の出力に基づいてフレーム終端信号(termination signal)を発生して前記第１スイッチ４５５に印加するビット発生器４５３とで構成される。前記第１テールビット生成器４５０は、フレーム終了時、前記第１スイッチ４５５が第１構成符号器４１０と連結されて前記第１構成符号器４１０のメモリ素子を初期化させると同時に、フレーム終端信号を発生する。第２テールビット生成器４６０は、前記第２構成符号器４２０の入力端に連結される第２スイッチ４６５と、前記第２構成符号器４２０のメモリ素子４２２，４２３の出力を排他的論理和する排他的論理和器４６１と、前記排他的論理和器４６１の出力に基づいてフレーム終端信号を発生して前記第２スイッチ４６５に印加するビット発生器４６３とで構成される。前記第２テールビット生成器４６０は、フレーム終了時、前記第２スイッチ４６５が第２構成符号器４２０と連結されて前記第２構成符号器４２０のメモリ素子を初期化させると同時に、フレーム終端信号を発生する。
【００６６】
第１穿孔器４７０は、前記情報ビットを穿孔する。第２穿孔器４８０は、前記第１構成符号器４１０及び第２構成符号器４２０から出力される符号化したデータを穿孔する。前記第１穿孔器４７０及び第２穿孔器４８０はデータの伝送率を調整する役割を果たす。マルチプレクサ４９１は、ビット発生器４５３，４６３の出力をマルチプレクシングして出力する。第３スイッチ４９３は、フレーム終了時前記マルチプレクサ４９１から出力されるテールビットを伝送チャネルにスイッチング連結する。
【００６７】
従って、前記第１テールビット生成器４５０は、前記第１構成符号器４１０を終端させるためのテールビットを生成し、前記第２テールビット生成器４６０は、前記第２構成符号器４２０を終端させるためのテールビットを生成する。また、第１穿孔器４７０及び第２穿孔器４８０は、伝送率を適切なレベルに調整して出力する。
【００６８】
前記図１３を参照すれば、ターボ符号は構成符号器４１０，４２０を終端させるためにテールビットを使用する。この時、前記ターボ符号の構成符号は体系的符号(systematic code)なので、非体系的たたみ込み符号のように‘０’を続いて入力しても、構成符号器４１０，４２０のメモリ４１２，４１３，４２２，４２３は初期化されない。しかし、入力から最も近いメモリの値を‘０’に設定するために、構成符号器４１０，４２０は、前記メモリにフィードバックされる値の和をテールビット発生器を用いて入力すればいい。従って、ターボ符号器では各構成符号のメモリ数に対応するテールビットが必要である。図１３で前記第１構成符号器４１０の入力端に連結されるスイッチ４５５及び第２構成符号器４２０の入力端に連結されるスイッチ４６５は、テールビット生成時点でスイッチングされる。その後、前記第１構成符号器４１０及び第２構成符号器４２０に出力されるテールビットによるパリティビットは前記第２穿孔器４８０に出力され、テールビット生成器から生成したテールビットは前記第３スイッチ４９３によってスイッチングされて情報ビットＸｋとして出力される。
【００６９】
ハードウェアの複雑度を低減するために、伝送率を２の累乗(power of 2)にするのが望ましい。しかし、例えば、３８４kbpsのデータ伝送率を有する場合には、符号率が１／２であるターボ符号を使用すると、伝送率の２の累乗にすることができない。従って、このような場合には符号率が１／２であるターボ符号を穿孔して生成した、符号率３／８のターボ符号を使用すればいい。特に、１４４kbps伝送率では符号率が１／２であるターボ符号を穿孔して符号率を９／１６に変える。ここで、下記の表９及び表１０は９／６穿孔マトリックスの例を示したものである。
【００７０】
【表９】
0003730238.tif 000010
【００７１】
【表１０】
0003730238.tif 000011
【００７２】
前記表９及び表１０で、情報ビットは入力される情報ビットｄｋであって、第１穿孔器４７０に印加され、ＲＳＣ１は第１構成符号器４１０から出力されるパリティビットであって、第２穿孔器４８０に印加される。この時、前記表９は構成符号器４１０及び４２０から出力するパリティビットを穿孔した例を示すものであって、この場合、パリティビットに該当する部分で連続的に‘０’で示される部分が多数存在する。即ち、伝送率を調整するためにパリティビットを穿孔すると、前記表９の下線を引いた部分のようにパリティビットに該当する部分で連続的に‘０’が現れる箇所が存在する。しかし、本発明の実施形態では前記各構成符号器４１０，４２０のメモリが２個しかないために、パリティビットを連続して二つ以上伝送しないと致命的な誤りが生ずる恐れがある。従って、本発明の実施形態では前記表１０のように情報ビットを穿孔する。前記表１０は前記表９と同一な９／６穿孔マトリックスであるが、常に連続して二つ以上のパリティビットが伝送される。しかし、ターボ符号の性能は反復復号回数に比例して向上される。
【００７３】
上述の如く、本発明は、ターボ符号器の内部に存在するインタリーバの大きさを縮め、ターボ符号に優秀な性能を示すインタリーバを導入することによって、時間遅延の制約のために通信システムの音声及びデータ伝送に適用できなかったターボ符号を音声及びデータ伝送に利用することができる。また、性能の優秀なインタリーバを使用して前記ターボ符号器の構成符号器の状態数を減少させることによって復号器の複雑さを減少できる。また、本発明の実施形態では、入力情報を穿孔するために、多様な符号率を提供することができる。
【００７４】
一方、前記本発明の詳細な説明では具体的な実施形態に上げて説明してきたが、本発明の範囲内で様々な変形が可能であるということは勿論である。従って、本発明の範囲は前記実施形態によって限られてはいけなく、特許請求の範囲とそれに均等なものによって定められるべきである。
【図面の簡単な説明】
【００７５】
【図１】従来の並列鎖状循環構造的符号器の構成図。
【図２】従来の直列鎖状循環構造的符号器の構成図。
【図３】従来の並列鎖状循環構造的復号器の構成図。
【図４】従来の直列鎖状循環構造的復号器の構成図。
【図５】本発明の第１実施形態による鎖状循環構造的符号器の構成を示す図。
【図６】本発明の第２実施形態による鎖状循環構造的符号器の構成を示す図。
【図７】本発明の第１実施形態によるターボ符号器で対角インタリーバの構造を示す図。
【図８】図７のような構成を有する対角インタリーバの構造で第１対角インタリービング動作過程を示す流れ図。
【図９】本発明の第２実施形態によるターボ符号器で循環インタリーバの構造を示す図。
【図１０】図９のような構成を有するインタリーバの構造で第１循環インタリービング動作過程を示す流れ図。
【図１１】図７のような構成を有するインタリーバの構造で第２循環インタリービング動作過程を示す流れ図。
【図１２】ランダムインタリービング方式及びブロックインタリービング方式を使用したターボ符号器と本発明の第２実施形態による循環インタリービング方式を使用したターボ符号器の特性を比較したグラフ。
【図１３】テールビット生成及び穿孔動作を説明するための本発明の実施形態によるターボ符号器の構成図。
【符号の説明】
【００７６】
４１０    第１符号器
４２０    第２符号器
４３２    対角インタリーバ
４３４    循環インタリーバ
５１１    レジスタ
５１３    対角インタリービングテーブル
５１５    循環インタリービングテーブル
５１７    対角インタリービング制御器
５１９    循環インタリービング制御器
５２１    マルチプレクサ
５２３    メモリ
【図１】
0003730238.tif 000012
【図２】
0003730238.tif 000013
【図３】
0003730238.tif 000014
【図４】
0003730238.tif 000015
【図５】
0003730238.tif 000016
【図６】
0003730238.tif 000017
【図７】
0003730238.tif 000018
【図８】
0003730238.tif 000019
【図９】
0003730238.tif 000020
【図１０】
0003730238.tif 000021
【図１１】
0003730238.tif 000022
【図１２】
0003730238.tif 000023
【図１３】
0003730238.tif 000024