(57)【要約】【課題】【解決手段】入力データシークエンスを復号化する方法を提供する。この方法は、複数のテストシークエンスを生成する工程と、前記複数のテストシークエンスの順序を、各テストシークエンスが夫々の予め規定された数のビットだけその隣接テストシークエンスとは異なるように決定する工程と、最大尤度処理を、前記順序づけられたテストシークエンスおよび前記入力データシークエンスを用いて実行し、これにより最大尤度シークエンスを生成する工程とを備える。【選択図】      図４
2009515420.tif 000002
【特許請求の範囲】
【請求項１】
入力データシークエンスを復号化する方法であって、
複数のテストシークエンスを生成する工程と、
前記複数のテストシークエンスの順序を、各テストシークエンスが夫々の予め規定された数のビットだけその隣接テストシークエンスとは異なるように決定する工程と、
最大尤度処理を、前記順序づけられたテストシークエンスおよび前記入力データシークエンスを用いて実行し、これにより最大尤度シークエンスを生成する工程と
を備えることを特徴とする復号化方法。
【請求項２】
前記生成された最大尤度シークエンスに対する信頼性指標を決定する工程を更に備えることを特徴とする請求項１に記載の復号化方法。
【請求項３】
前記生成された最大尤度シークエンスに対する信頼性指標の係数は、前記生成された最大尤度シークエンスの重みと最大重みとの差を含むことを特徴とする請求項２に記載の復号化方法。
【請求項４】
前記得られた最大尤度シークエンスに対する信頼性指標の係数は、前記生成された最大尤度シークエンスにおける最も信頼できないビット位置の数を更に含むことを特徴とする請求項３に記載の復号化方法。
【請求項５】
エラーに遭遇する際に前記複数のテストシークエンスに摂動を与える工程を更に備えることを特徴とする請求項１に記載の復号化方法。
【請求項６】
前記複数のテストシークエンスに摂動を与える工程は、前記テストシークエンスの所定のビットを反転させる工程を備えることを特徴とする請求項５に記載の復号化方法。
【請求項７】
前記夫々の予め規定された数のビットは１ビットであることを特徴とする請求項１に記載の復号化方法。
【請求項８】
複数のテストシークエンスを生成する生成器と、
前記複数のテストシークエンスの順序を、各テストシークエンスが夫々の予め規定された数のビットだけその隣接テストシークエンスとは異なるように決定する第１手段と、
最大尤度処理を、前記順序づけられたテストシークエンスおよび前記入力データシークエンスを用いて実行し、これにより最大尤度シークエンスを生成する第２手段と
を備えることを特徴とする復号化装置。
【請求項９】
前記生成された最大尤度シークエンスに対する信頼性指標を決定する第３手段を更に備えることを特徴とする請求項８に記載の復号化装置。
【請求項１０】
入力データシークエンスを復号化する方法であって、
複数のテストシークエンスを生成する工程と、
前記複数のテストシークエンスの順序を、各テストシークエンスが夫々の予め規定された数のビットだけその隣接テストシークエンスとは異なるように決定する工程と、
最大尤度処理を、前記順序づけられたテストシークエンスおよび前記入力データシークエンスを用いて実行し、これにより最大尤度シークエンスを生成する工程と、
を備える前記復号化する方法を、コンピュータに実行させるコンピュータプログラム製品。
【請求項１１】
前記コンピュータに、前記生成された最大尤度シークエンスに対する信頼性指標を決定する工程を更に備える入力データシークエンスを復号化する方法を実行させることを特徴とする請求項１０に記載のコンピュータプログラム製品。
【請求項１２】
入力データシークエンスを符号化する方法であって、
少なくとも一の符号化行列を決定する工程と、
前記決定された少なくとも一の符号化行列を順番に並べる工程と、
前記入力データシークエンスを入力データ行列に配置する工程と、
前記配置された少なくとも一の符号化行列を用いて、前記入力データ行列に対して演算を実行し、これにより符号化されたデータブロックを生成する工程と
を備えることを特徴とする符号化方法。
【請求項１３】
前記決定された少なくとも一の符号化行列を順番に並べる工程は、前記少なくとも一の符号化行列の列を、各列のビット値により表わされる整数値が小さい順に並べる工程を備え、最上行のビットは、各列の最下位ビットに対応することを特徴とする請求項１２に記載の符号化方法。
【請求項１４】
前記決定された少なくとも一の符号化行列の最右列の後ろに所定値の列を付加する工程と、
前記決定された少なくとも一の符号化行列を順番に並べる前に、前記決定された少なくとも一の符号化行列の最上行の下に所定値の行を付加する工程と
を更に備えることを特徴とする請求項１２に記載の符号化方法。
【請求項１５】
前記所定値の列は、全てゼロの列であることを特徴とする請求項１２に記載の符号化方法。
【請求項１６】
前記所定値の行は、全て１の行であることを特徴とする請求項１２に記載の符号化方法。
【請求項１７】
前記符号化されたデータブロックの所定の行を削除する工程を更に備えることを特徴とする請求項１２に記載の符号化方法。
【請求項１８】
前記符号化されたデータブロックの所定の列を削除する工程を更に備えることを特徴とする請求項１７に記載の符号化方法。
【請求項１９】
前記符号化されたデータブロックにおける、所定組の連続ビットを、削除する工程を更に備えることを特徴とする請求項１８に記載の符号化方法。
【請求項２０】
前記符号化されたデータブロックにおける、所定組の連続ビットを、所定データで置換する工程を更に備えることを特徴とする請求項１８に記載の符号化方法。
【請求項２１】
前記所定データは、全てゼロ値の一組であることを特徴とする請求項２０に記載の符号化方法。
【請求項２２】
前記所定データは、巡回冗長検査（ＣＲＣ）データであることを特徴とする請求項２０に記載の符号化方法。
【請求項２３】
少なくとも一の符号化行列を決定する第１手段と、
前記決定された少なくとも一の符号化行列を順番に並べる第２手段と、
前記入力データシークエンスを入力データ行列に配置する第３手段と、
前記配置された少なくとも一の符号化行列を用いて、前記入力データ行列に対して演算を実行し、これにより符号化されたデータブロックを生成する第４手段と
を備えることを特徴とする符号化装置。
【請求項２４】
入力データシークエンスを符号化する方法であって、
少なくとも一の符号化行列を決定する工程と、
前記決定された少なくとも一の符号化行列を順番に並べる工程と、
前記入力データシークエンスを入力データ行列に配置する工程と、
前記配置された少なくとも一の符号化行列を用いて、前記入力データ行列に対して演算を実行し、これにより符号化されたデータブロックを生成する工程と、
を備える前記符号化する方法を、コンピュータに実行させるコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、米国仮出願６０／７３４，０５４（２００５年１１月７日出願）及び６０／７３４，０８０（２００５年１１月７日出願）の利益を要求する。これらの内容は全て参照することにより本願に組み込まれる。
【０００２】
本発明は、データを復号化及び符号化する方法、並びに対応する装置に関する。
【背景技術】
【０００３】
順方向誤り訂正（ＦＥＣ）コーディングは通信技術に用いられており、データ伝送中に生じた限定数のエラーを受信側で訂正することが可能である。近年、Ｂｅｒｒｏｕが、ターボコード（ＴＣ）［１］と称される新たなＦＥＣコーディング体系を提示した。これにより、性能レベルを、ソフト入力ソフト出力（ＳＩＳＯ）繰り返しデコーダを用いて、Ｓｈａｎｎｏｎの定理により予測される付加白色ガウス雑音（ＡＷＧＮ）チャネルの理論的限界まで近付けることができる。この新たなコーディング体系は、並行に連結した二つの再帰的組織畳み込み符号からなる。また、それ自体は畳み込みターボコード（ＣＴＣ）として一般に知られている。
【０００４】
その後、Ｐｙｎｄｉａｈが、ターボプロダクトコード（ＴＰＣ）［２］［３］、並びにターボプロダクトコードに効率的な復号アルゴリズムを提示した。ターボプロダクトコードは、畳み込みターボコードに匹敵する性能を示し、より高い符号化速度に対応することができる。これらの利点から、ターボプロダクトコードは、ＩＥＥＥ８０２．１６ネットワークの物理層や衛星通信及びデジタル記憶システムにおいて用いられてきた。
【０００５】
これら二つの最近の発展は、より高い性能レベルのコーディング体系を得るために、途方もない量の研究活動に持続的な努力がなされていることを立証するものである。これらの新たなコーディング体系における復号化の複雑さを緩和することに更なる研究努力が費やされている。例えば、ターボプロダクトコードの復号化における複雑さを更に緩和するために、Ｃｈａｓｅアルゴリズム［４］を用いて、繰り返し復号化の各ビット位置に関する外部情報を得ることができる。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本出願における対応する独立項に規定されるように、本発明の方法及び装置は、より高い性能レベルのコーディング体系を得るために更に貢献する。
【課題を解決するための手段】
【０００７】
本発明の第１の態様は、入力データシークエンスを復号化する方法であって、複数のテストシークエンスを生成する工程と、前記複数のテストシークエンスの順序を、各テストシークエンスが夫々の予め規定された数のビットだけその隣接テストシークエンスとは異なるように決定する工程と、最大尤度処理を、前記順序づけられたテストシークエンスおよび前記入力データシークエンスを用いて実行し、これにより最大尤度シークエンスを生成する工程とを備えることを特徴とする復号化方法を提供する。
【０００８】
本発明の第２の態様は、複数のテストシークエンスを生成する生成器と、
【０００９】
前記複数のテストシークエンスの順序を、各テストシークエンスが夫々の予め規定された数のビットだけその隣接テストシークエンスとは異なるように決定する第１手段と、最大尤度処理を、前記順序づけられたテストシークエンスおよび前記入力データシークエンスを用いて実行し、これにより最大尤度シークエンスを生成する第２手段とを備えることを特徴とする復号化装置を提供する。
【００１０】
本発明の第３の態様は、入力データシークエンスを復号化する方法であって、複数のテストシークエンスを生成する工程と、前記複数のテストシークエンスの順序を、各テストシークエンスが夫々の予め規定された数のビットだけその隣接テストシークエンスとは異なるように決定する工程と、最大尤度処理を、前記順序づけられたテストシークエンスおよび前記入力データシークエンスを用いて実行し、これにより最大尤度シークエンスを生成する工程とを備える前記復号化する方法を、コンピュータに実行させるコンピュータプログラムを提供する。
【００１１】
以下に述べる一の実施形態は、Ｃｈａｓｅアルゴリズムの変形例として考えられる。復号化処理における本来のＣｈａｓｅアルゴリズムに対して、複雑さの緩和を達成することができる。これらの変形例は、複数のテストシークエンスを、各テストシークエンスが所定数のビットだけその隣接テストシークエンスとは異なるように配置する工程と、最大尤度シークエンスの重みと最大重みとの差を含む係数を含んだ信頼性指標に対する信頼性指標を計算するための新たな式を取得する工程とを含んでよい。変形Ｃｈａｓｅアルゴリズムを用いると、復号化処理の複雑さはかなり緩和される。
【００１２】
本発明の実施形態は、従属項から発生する。
【００１３】
一の実施形態では、前記生成された最大尤度シークエンスに対する信頼性指標を決定してよい。他の実施形態では、前記得られた最大尤度シークエンスに対する信頼性指標の係数は、前記生成された最大尤度シークエンスの重みと最大重みとの差を含む。更なる他の実施形態では、前記得られた最大尤度シークエンスに対する信頼性指標の係数は、前記生成された最大尤度シークエンスにおける最も信頼できないビット位置の数を更に含む。
【００１４】
ここで用いられるように、前記生成された最大尤度シークエンスに対する信頼性指標は、前記取得された最大尤度シークエンスの相対信頼性を測定するために計算された値を参照する。前記生成された最大尤度シークエンスに対する信頼性指標は、例えば、最大尤度シークエンスの外部情報であってよいが、これに限定されない。
【００１５】
一の実施形態では、エラーに遭遇する際に前記複数のテストシークエンスに摂動を与えてよい。他の実施形態では、前記複数のテストシークエンスは、前記テストシークエンスの所定のビットを反転させることにより摂動を与えてよい。
【００１６】
一の実施形態では、前記夫々の予め規定された数のビットは１である。これは、二つの隣接するテストシークエンスは、１ビットのみ異なるという意味である。
【００１７】
本発明の第４の態様は、入力データシークエンスを符号化する方法であって、少なくとも一の符号化行列を決定する工程と、前記決定された少なくとも一の符号化行列を順番に並べる工程と、前記入力データシークエンスを入力データ行列に配置する工程と、前記配置された少なくとも一の符号化行列を用いて、前記入力データ行列に対して演算を実行し、これにより符号化されたデータブロックを生成する工程とを備えることを特徴とする符号化方法を提供する。
【００１８】
本発明の第５の態様は、少なくとも一の符号化行列を決定する第１手段と、前記決定された少なくとも一の符号化行列を順番に並べる第２手段と、前記入力データシークエンスを入力データ行列に配置する第３手段と、前記配置された少なくとも一の符号化行列を用いて、前記入力データ行列に対して演算を実行し、これにより符号化されたデータブロックを生成する第４手段とを備えることを特徴とする符号化装置を提供する。
【００１９】
本発明の第６の態様は、入力データシークエンスを符号化する方法であって、少なくとも一の符号化行列を決定する工程と、前記決定された少なくとも一の符号化行列を順番に並べる工程と、前記入力データシークエンスを入力データ行列に配置する工程と、前記配置された少なくとも一の符号化行列を用いて、前記入力データ行列に対して演算を実行し、これにより符号化されたデータブロックを生成する工程とを備える前記符号化する方法を、コンピュータに実行させるコンピュータプログラム製品を提供する。
【００２０】
具体的には、本来の符号化行列の各列の値を、小さい順に再配置することにより新たな符号化行列を取得する。この新たな符号化行列を有して生成された符号化データベクトルに対して、エラーが生じる際に、デコーダ側において、エラーシンドロームにより示された位置におけるビット値を単に反転させることにより、生成されたエラーシンドロームを用いてこのエラーを直接訂正してよい。しかしながら、本来の符号化行列を有して生成された符号化データベクトルに対しては、エラービットの位置を決定するために、生成されたエラーシンドロームに対してさらに処理を行うことが必要である。従って、この新たな符号化行列を有して生成された符号化データベクトルの復号化は簡略化される。
【００２１】
一の実施形態では、前記決定された少なくとも一の符号化行列は、前記少なくとも一の符号化行列の列を、各列のビット値により表わされる整数値が小さい順に配置することにより順番に並べられてよく、最上行のビットは、各列の最下位ビットに対応する。
【００２２】
一の実施形態では、前記決定された少なくとも一の符号化行列の最右列の後ろに所定値の列を付加されてよく、前記決定された少なくとも一の符号化行列を順番に並べる前に、前記決定された少なくとも一の符号化行列の最上行の下に所定値の行を付加されてよい。他の実施形態では、前記所定値の列は、全てゼロの列であってよく、前記所定値の行は、全て１の行であってよい。
【００２３】
一の実施形態では、前記符号化されたデータブロックの所定の行、又は前記符号化されたデータブロックの所定の列を削除してよい。他の実施形態では、前記符号化されたデータブロックにおける、所定組の連続ビットを、削除又は所定データで置換してよい。更なる他の実施形態では、前記所定データは、全てのゼロ値の一組であってよい。更なる他の実施形態では、前記所定データは、巡回冗長検査（ＣＲＣ）データであってよい。
【００２４】
本発明により提供された入力データシークエンスを復号化する方法から、次の利点が与えられることがわかる。即ち、本発明により提供された入力データシークエンスを復号化する方法を用いた復号化処理は、本来のＣｈａｓｅアルゴリズムを用いた復号化処理と比較して、あまり複雑ではない。
【００２５】
加えて、本発明により提供された入力データシークエンスを符号化する方法から、次の利点が与えられることがわかる。本発明により提供された入力データシークエンスを符号化する方法を用いて生成された符号化データベクトル又はブロックに対して、エラーが生じる際に、そのエラーのビット位置は計算されたシンドロームから直接取得されてよい。
【００２６】
従って、本発明により提供された入力データシークエンスを符号化する方法を用いて生成された符号化データベクトル又はブロックの復号化は、簡略化される。
【００２７】
提供された入力データシークエンスを復号化する方法、及び入力データシークエンスを符号化する方法において記載された実施形態は、装置及びコンピュータプログラム製品に対しても同じように有効である。
【発明を実施するための最良の形態】
【００２８】
図１は、本発明の実施例に係る通信システム１００を示す図である。
【００２９】
伝送経路において、通信システム１００は、情報源及び入力変換器１０１、ソースエンコーダ１０３、チャネルエンコーダ１０５、及びデジタル変調器１０７を備える。情報源及び入力変換器１０１により生成された信号は、送信される前に、ソースエンコーダ１０３、チャネルエンコーダ１０５、及びデジタル変調器１０７により処理される。送信された信号は、受信信号として、受信器側に到着する前にチャネル１０９を通過する。
【００３０】
受信経路において、通信システム１００は、デジタル復調器１１１、チャネルデコーダ１１３、ソースデコーダ１１５及び出力変換器１１７を備える。そして、受信信号は、理想的には、情報源及び入力変換器１０１により生成された信号と同一の信号を回収するために、受信経路における構成要素を介して処理される。
【００３１】
伝送経路上の各構成要素は、受信経路上の対応する構成要素を有する。例えば、伝送経路上にチャネルデコーダ１０５があり、その受信経路上の対応構成要素はチャネルデコーダ１１３である。
【００３２】
通信システム１００における典型的な信号伝送では、信号内にエラーが生じる可能性がある。エラーは、通常、チャネル１０９の信号伝送中に生じる。従って、チャネルエンコーダ１０５及びその対応するチャネルデコーダ１１３は、典型的な通信システム１００内に設けられており、チャネル１０９の信号伝送中に生じるエラーを減少させ、また可能であれば排除する。
【００３３】
この場合、チャネルエンコーダ１０５は、ターボプロダクトコード（ＴＰＣ）エンコーダであってよい。これは、本発明により提供されたデータの符号化方法により実施されてよい。これに対応して、チャネルデコーダ１１３は、ターボプロダクトコード（ＴＰＣ）デコーダであってよい。これは、本発明により提供されたデータの復号化方法を用いて実施されてよい。
【００３４】
ターボプロダクトコード（ＴＰＣ）エンコーダは、次のように説明されてよい。
【００３５】
後の説明では、次の規則が用いられる。Ｘは、行列又はベクトルセットを指し、ｘｉは、行列Ｘのｉｔｈ行を指す。この点に関して、
【数１】
2009515420.tif 000003
は、ｘｉのｊｔｈ要素を指す。しかしながら、Ｘが一行のみである場合は、ｘｊはＸのｊｔｈ要素を指す。
【００３６】
Ｃは、生成行列Ｇおよびパリティ検査行列Ｈを有するハミングコード符号化データベクトル（n,k,δ）を意味する。ここで、コード長ｎ＝２ｍ−１、情報ビット数ｋ＝ｎ−ｍ、最小ハミング距離δ＝３であり、ｍは整数値である。加えて、コード長ｎ及び情報ビット数ｋも整数値である。ｍは設定可能な値であり、
【数２】
2009515420.tif 000004
なる条件を伴う。
【００３７】
Ｇは、ｋ×（ｎ−ｋ）パリティサブ行列Ｐを有するＧ＝（Ｉｋ｜Ｐ）としての組織的形態で表わされてよい。従って、対応するパリティ検査行列Ｈは、Ｈ＝（ＰＴ｜Ｉｋ）により表わされてよい。ｍ＝３である行列Ｇ、Ｈ、及びＰの例が、式（１）、（２）、及び（３）に夫々示される。ｍ＝３、ｎ＝７、及びｋ＝４の場合、以下の通りである。
【数３】
2009515420.tif 000005
【００３８】
ハミングコードに対する符号化処理は、通常は、生成行列Ｇを用いて、ｃ（ｃ１，...，ｃｎ）＝（ｃ１，...，ｃｋ）Ｇで表わされる。情報ビットは、パリティ検査行列Ｈを用いて符号化されてよい。ｋ＞（ｎ−ｋ）の場合、パリティ検査行列Ｈを用いた符号化処理が必要とする計算数はより少ない。これらの場合、パリティ検査行列Ｈを用いた符号化処理はｃＨＴ＝０に基づいて実施され、ｎ−ｋパリティ検査ビットｃｋ＋１，...，ｃｎは次のように得られる。
【数４】
2009515420.tif 000006
【００３９】
ハミングコードは、それらのパリティ検査行列Ｈはその列の全てに対して異なる値を有するという特別な性質を有している。例えば、式（３）において、パリティ検査行列Ｈはその全ての列に対して（３，５，６，７，１，２，４）の値を有している。但し、最上行のビットは最下位ビット（ＬＳＢ）の値である。
【００４０】
仮に単一のエラーが、例えば位置ｊにおいて生じる場合、受信ベクトルｒのシンドロームｓは、エラーが生じた位置におけるＨの列を意味する。ｅがエラーベクトルを意味するとする。その成分の全てが、ｊｔｈ成分を除いてゼロに等しい、即ち、ｅｊ＝１と仮定すると、受信ベクトルｓのシンドロームは次式により与えられる。
【数５】
2009515420.tif 000007
但し、ｈｊ＝１はＨのｊ−ｔｈ番目の列を意味する。例えば、式（３）に与えられたパリティ検査行列Ｈを用いて生成されたハミングコード符号化データベクトルにおける単一のビットエラーに対して考えられるシンドロームの表を図２の左部分に示す。
【００４１】
式（５）から、Ｈの列がエラー位置の２進表現として表現される場合、シンドロームｓの値を直接用いて、エラーのビット位置を決定する。これを実現するために、パリティ検査行列Ｈの列を、その列の値が小さい順になるように再配置されてよい。
【００４２】
例えば、式（３）において、先に示したように、パリティ検査行列Ｈはその全ての列に対して（３，５，６，７，１，２，４）の値を有している。但し、最上行のビットは最下位ビット（ＬＳＢ）の値である。その全ての列の値を（１，２，３，４，５，６，７）に再配置することにより、次のような行列Ｈｒを取得する。
【数６】
2009515420.tif 000008
【００４３】
或いは、パリティ検査行列Ｈから行列Ｈｒを生成することを、次のように表現してよい。
【数７】
2009515420.tif 000009
【００４４】
行列Ｈｒを用いて生成されたハミングコード符号化データベクトルは、パリティ検査行列Ｈを用いて生成された本来のハミングコード符号化データベクトルの再配置版である。一般に、ｎ＝２ｍ−１及びｋ＝２ｍ−１−ｍである（ｎ，ｋ）ハミングコードに対して、パリティ検査ビットは、Ｈｒの１，２，４...２ｍ−１と番号づけられた列に位置する。残りの符号化ビットは、列番号３から、パリティ検査行列Ｈを用いる場合と同じ順序付けで再配置される。これに関し、図２を参照して以下に更に説明する。
【００４５】
デコーダ側において、パリティ検査行列Ｈを用いて生成されたハミングコード符号化データベクトルに対して、先ず、シンドロームｓが式（５）を用いて受信ベクトルから計算される。次に、計算されたシンドロームを用いて、対応するエラーパターンをルックアップテーブルから取得する。次に、訂正された受信ベクトルは、受信ベクトル及びエラーパターンに対する排他的ＯＲ（ＸＯＲ）動作により得られる。続いて、パリティ検査ビットを削除した後に、訂正された受信ベクトルから情報ビットを取り出せる或いは回収できる。
【００４６】
しかしながら、行列Ｈｒを用いて生成されたハミングコード符号化データベクトルに対して、硬判定復号を実施することは容易である。なぜなら、式（５）により計算されたシンドロームｓは、エラーのビット位置を直接与えるからである。次に、エラーのビットは受信ベクトルにおいて反転され、訂正された受信ベクトルが得られる。従って、計算されたシンドロームに対する対応エラーパターンを取得するためにルックアップテーブルを参照するステップの必要性がなくなる。従って、行列Ｈｒを用いて生成されたハミングコードのこの性質は、次に説明するターボプロダクトコード（ＴＰＣ）復号処理の複雑さを緩和するために用いられてよい。
【００４７】
更なる例として、行列Ｈ及び行列Ｈｒを用いて生成された符号化データベクトルの符号化及び復号化処理を図２のように例示する。この説明では、情報ビットは（ｃ１，...，ｃｋ）＝（１，０，１，０）２０１とする。
【００４８】
パリティ検査行列Ｈに対して、式（４）を用いてパリティ検査ビットを取得すると、生成されたハミングコード符号化データベクトルは、（ｃ１，...，ｃｎ）＝（１，０，１，０，１，０，１）２０３により与えられる。伝送中、エラーが例えばビット位置２で生じる。従って、受信ベクトルｒは、（ｒ１，...，ｒｎ）＝（１，１，１，０，１，０，１）２０５により与えられる。
【００４９】
受信ベクトルのシンドロームｓは、次のように計算される。
【数８】
2009515420.tif 000010
【００５０】
ルックアップテーブルから取得されたシンドロームｓ、即ち（１，０，１）２０７を用いて、シンドロームの値（１，０，１）２０７に対応する行２０９は、対応するエラーパターンが（０，１，０，０，０，０，０）２１１であることを示している。受信ベクトル及びエラーパターンに対する排他的ＯＲ（ＸＯＲ）動作により得られた訂正された受信ベクトルは、（１，０，１，０，１，０，１）であり、これは符号化データベクトル２０３と同じである。
【００５１】
式（６）からのパリティ検査行列Ｈｒに対して、パリティ検査ビット位置はＨｒの１，２，４と番号づけられた列に位置することが分かる。よって、パリティ検査サブ行列ＰＴの転置は、１，２，４と番号づけられた列を削除することにより得られてよい。
【００５２】
この行列と式（４）から、３のパリティ検査ビットが（１，０，１）として得られる。従って、パリティ検査ビットを１，２，４と番号づけられた列に挿入し、情報ビット（１，０，１，０）２０１を残りの列に、列３から挿入した後、得られたハミングコードまたは符号化ベクトルは、（１，０，１，１，０，１，０）２１５である。
【００５３】
エラーがビット位置２で生じたと仮定すると、受信ベクトルｒは（１，１，１，１，０，１，０）２１７である。この受信ベクトルに対して得られたシンドロームｓは、
【数９】
2009515420.tif 000011
【００５４】
このシンドローム（０，１，０）２１９はエラービットのビット位置を直接与えるので、得られた訂正受信ワードは、ビットをビット位置２で反転することにより、（１，０，１，１，０，１，０）２２１となる。訂正された受信ワードは、符号化データベクトルと同じであることがわかる。従って、この説明から、行列Ｈｒを用いて生成されたハミングコード符号化データベクトルの復号化処理が簡略化されたことがわかる。なぜなら直接計算されたシンドロームがエラービットのビット位置を直接与えるからである。
【００５５】
先に記載したように、行列Ｈｒは、パリティ検査行列Ｈの列を、列の値が小さい順になるように再配置することにより、パリティ検査行列Ｈから生成される。交代行列ＨｒＥも、行列Ｈｒと同様な方法で生成されてよい。行列ＨｒＥを用いて生成されたハミングコードも、行列Ｈｒを用いて生成されたハミングコードと同じ特異的性質を有している。行列Ｈｒを用いて生成されたハミングコードから区別するために、行列ＨｒＥを用いて生成されたハミングコードは、これ以降、拡張ハミングコードと称する。
【００５６】
行列ＨｒＥは、次のように生成されてよい。第１に、全てゼロの列をパリティ検査行列Ｈの最右列に付加する。第２に、全てゼロの列をパリティ検査行列Ｈの最右列に付加する。これに伴う中間の行列ＨＥは、次のように示される。
【数１０】
2009515420.tif 000012
【００５７】
これに続いて、パリティ検査行列ＨＥの列を、列の値が小さい順になるように再配置することにより、行列ＨｒＥをパリティ検査行列ＨＥから次に示すように生成する。
【数１１】
2009515420.tif 000013
【００５８】
次に、本発明の実施例に係るターボプロダクトコード（ＴＰＣ）を生成する手順について説明する。例えば、ターボプロダクトコード（ＴＰＣ）は、二つのハミングコードＣ１（n１,k１,δ１）及びＣ２（n２,k２,δ２）に基づいて生成されてよい。これらハミングコードは、先に説明した行列Ｈｒを用いて次のように生成される。
１）（ｋ２  ｋ１）情報ビットをｋ２行及びｋ１列の配列に配置する。
２）符号Ｃ１を用いてｋ２行を符号化する。
３）符号Ｃ２を用いてｋ１列を符号化する。
４）対応する行及び列に応じてパリティ検査ビットを計算し、その後挿入する。
【００５９】
先に記載した手順に従って生成されたターボプロダクトコード（ＴＰＣ）のコードワード長、情報ビットの数、及び最少ハミング距離は、夫々、ｎ１×ｎ２、ｋ１×ｋ２、及びδ１×δ２である。これは、最少ハミング距離の長い長ブロック符号が、最少ハミング距離の短い二つの短ブロック符号から取得されてよいことを意味する。
【００６０】
図３は、パリティ検査行列Ｈを用いて生成したターボプロダクトコード（ＴＰＣ）符号化データブロック３００を示す図である。一方、図４は、本発明の実施例に係るパリティ検査行列Ｈｒを用いて生成したターボプロダクトコード（ＴＰＣ）符号化データブロック４００を示す図である。
【００６１】
図３において、行ｉのビット（１，...，k1）、但し
【数１２】
2009515420.tif 000014
は、情報ビット３０１である。同じ行ｉにおいて、ビット（k1＋１，...，ｎ1―１）は、行ｉ３０３に対する複数のパリティ検査ビットであり、ビットｎ1は、全行ｉ３０５に対する単一のパリティ検査ビットであってよい。
【００６２】
同様に、列ｊのビット（１，...，k２）、但し
【数１３】
2009515420.tif 000015
は、情報ビット３０１である。同じ列ｊにおいて、ビット（k２＋１，...，ｎ２―１）は、列ｊ３０７の複数のパリティ検査ビットであり、ビットｎ2は、列ｊ３０５に対する単一のパリティ検査ビットであってよい。
【００６３】
最後に、行ｉのビット（k1+1，...， n1-1）、但し
【数１４】
2009515420.tif 000016
は、パリティ検査ビット３０９上のパリティ検査ビットである。これは、行iのビット（１，...，k1）、但し
【数１５】
2009515420.tif 000017
が、全て（列上の）パリティ検査ビット３０７であるからである。従って、符号化処理をパリティ検査ビットの行に対して実行する場合、符号化処理の結果として得られたパリティ検査ビットは、パリティ検査ビット上のパリティ検査ビットである。
【００６４】
他方、図４において、パリティ検査ビットは、１，２，４．．．２ｍ−１と番号づけられた列のみならず行にも位置していることがわかる。加えて、行及び列の両方が１，２，４．．．２ｍ−１のうちの一つとして番号づけられているビットは、パリティ検査ビット４０１上のパリティ検査ビットである。従って、先に記載した行列Ｈｒ及び行列Ｈｒを用いて生成された符号化ベクトルの特別なプロパティも、図４に示したターボプロダクトコード（ＴＰＣ）符号化データブロック内にある。
【００６５】
図２の説明図から、行列Ｈｒを用いて生成されたハミングコード符号化データベクトルの復号化は、受信ベクトルから計算されたシンドロームに対応するエラーパターンを取得するためにルックアップテーブルを必要としないことがわかる。これにより、復号化の複雑さが緩和される。従って、図４に示したＴＰＣ符号化データブロックに対する復号化の複雑さは、図３に示したＴＰＣ符号化データブロックと比較して、更に緩和されるであろう。これは、図３に示したＴＰＣ符号化データブロックに対する復号化は、復号化処理の各繰り返しの行番号及び列番号の積の倍数に関係しているからである。
【００６６】
次に、ターボプロダクトコード（ＴＰＣ）の符号化速度がどのように変更されるかについて説明する。通常、全てのエンコーダは符号化速度を有しており、これは通常（入力上の）情報ビットの数と（出力上の）符号化データビットの数との間の比として与えられる。エンコーダが所望の符号化速度を有していない場合、所望の符号化速度を取得するために、（符号化）速度マッチングと称される処理が符号化処理の後に実施されてよい。
【００６７】
先に記載したターボプロダクトコード（ＴＰＣ）に対して、速度マッチングは次のステップの組み合わせで実行してよい。即ち、
ａ）符号化データブロックから所定数の行を削除する。
ｂ）符号化データブロックから所定数の列を削除する。
ｃ）符号化データブロックの一の行から所定数のビットを削除する。
ｄ）符号化データブロックの一の行から所定数のビットを、所定組の値で置換する。
【００６８】
通常、ステップ（ｄ）に対して、符号化データブロックの一の行から所定数のビットを置換するために用いられる所定組の値は、全てゼロ値の一組である。符号化データブロックの一の行から所定数のビットを置換するために用いられる所定組の値は、情報ビットから生成される巡回冗長検査（ＣＲＣ）ビットであってもよい。
【００６９】
ここで巡回冗長検査（ＣＲＣ）ビットを用いると、受信器側において情報ビット中にエラーが存在するかを判断するために迅速な検査を行うことができる。情報ビット中にエラーが存在しないと判断された場合、情報ビットはターボプロダクトコード（ＴＰＣ）復号化処理を経由する必要なく、符号化データブロックから単に抽出されてよい。
【００７０】
次に、ターボプロダクトコード（ＴＰＣ）デコーダは、次のように説明できる。
【００７１】
前述のように、ターボプロダクトコードの復号化の複雑さを更に緩和させるために、Ｃｈａｓｅアルゴリズム［４］を用いて、繰り返し復号化に対する各ビット位置に関する外部情報が取得されてきた。しかしながら、Ｃｈａｓｅアルゴリズムは未だ相対的に複雑であることが観察された。
【００７２】
Ｃｈａｓｅアルゴリズムにおける多数のステップは通常ループ構造で実施されることが観察された。従って、複雑さの緩和はループ構造内のステップを最適化することにより達成されてよい。本発明の実施例によれば、復号化の複雑さの緩和は、符号化の見地のみならず復号化の見地からも考慮される。符号化の見地から考慮した復号化の複雑さの緩和は既に記載したので、ここで復号化の見地から考慮した復号化の複雑さの緩和を考慮する。
【００７３】
復号化の見地から考慮した復号化の複雑さの緩和は、次のように説明される。先に記載したターボプロダクトコード（ＴＰＣ）を生成する手順を用いて、本発明の実施例に係る変形Ｃｈａｓｅアルゴリズムが、次のステップに従って実施されてよい。即ち、
１）受信信号から、例えば、ｒ＝（ｒ１，ｒ２，．．．，ｒｎ＋１）で示される、位相補正を伴う二相位相変調（ＢＰＳＫ）変調信号｛１→１，０→−１｝は、
ａ）信頼性シークエンスｒａｂｓ＝（｜ｒ１｜，｜ｒ２｜，．．．，｜ｒｎ＋１｜）を生成する。
ｂ）バイナリシークエンスｙ＝（ｙ１，ｙ２，．．．，ｙｎ，ｙｎ＋１）を生成する。但し、ｒｌ＞０の場合、ｙｌは１に等しく、
【数１６】
2009515420.tif 000018
の場合、ｙｌは０に等しい。
ｃ）ｒａｂｓを用いてシークエンス（ｙ１，ｙ２，．．．，ｙｎ，ｙｎ＋１）のｐ個の最も信頼できないビット位置を決定する。
２）ａ）次のように規定されるテストパターン、アナログ重み（analog weight）、シンドローム、及び拡張ビットを初期化する。
【数１７】
2009515420.tif 000019
ｂ）テストパターンがその隣接テストパターンから１ビットのみ異なるようにテストパターンを再度順序付けする。
３）２ｐループ内で実行する。
ａ）次のように、拡張ビットを決定し、（エラーが生じた場合に）テストパターンに摂動を与え、アナログ重みを計算する。
【数１８】
2009515420.tif 000020
ｂ）次のように、次のテストシークエンスを生成し、シンドロームを計算し、拡張ビットを計算し、アナログ重みを計算する。
【数１９】
2009515420.tif 000021
４）最大尤度コードワードｄを有効コードワードセットから推定する。
【数２０】
2009515420.tif 000022
５）受信信号に対して外部情報を計算する。
ａ）ｐ個の最も信頼できないビット位置及びエラー訂正位置に対して、
【数２１】
2009515420.tif 000023
但し、ｗｄ及びｗｃは、夫々、最大尤度復号化シークエンスｄ及び競合復号化シークエンスｃｅｘのアナログ重みである。
ｂ）その他の全ての位置に対して、
【数２２】
2009515420.tif 000024
但し、ｗｍａｘは最大アナログ重みである。
【００７４】
ステップ５（ａ）に関して、本来のＣｈａｓｅアルゴリズムと同様に、最大尤度復号化シークエンスｄのビットが、一より多い競合復号化シークエンスを有する場合、ｗｃは、競合復号化シークエンス間でアナログ重みの最低値となる。ここで競合復号化シークエンスが、本来のＣｈａｓｅアルゴリズムにおいて行われるように設定された単なる候補復号化シークエンスの代わりに、全テストシークエンスから探索される。このようにすることで、復号化シークエンス探索処理の際の復号化の緩和が達成される。
【００７５】
最小のアナログ重みを有するテストシークエンスのエラー訂正位置及びｐ個の最も信頼できないビット位置に対して、復号化計算の複雑さは、本来のＣｈａｓｅあるとリズムと同じであり、各ビット位置に対して２ｐコンパレータ動作を必要とする。しかしながら、残りのエラー訂正位置に対して、計算の複雑さは多いに緩和される。なぜなら、競合復号化シークエンスの重みは、対応位置でエラー訂正動作が起こるテストシークエンスの重みと同じであるからである。従って、追加計算は必要とされない。
【００７６】
ステップ５（ｂ）に関して、本来のＣｈａｓｅアルゴリズムで用いられるパラメータβは、外部情報の正規化を要求する。これは次に大量の計算を要求する。式（１３）には本来のＣｈａｓｅアルゴリズムで用いられるようなパラメータβが存在しないので、外部情報の正規化を行う必要はない。従って、復号化の複雑さはかなり緩和される。
【００７７】
図５は、本来のＣｈａｓｅアルゴリズムと本発明の実施例に係る変形Ｃｈａｓｅアルゴリズムとの間における、ｎ＋１列及びｎ＋１行のスクエアターボプロダクトコード（ＴＰＣ）符号化データブロックの復号化の複雑さの比較例を示す図である。比較例は、スクエアターボプロダクトコード（ＴＰＣ）符号化データブロックの一成分コードワード（一列又は一行）における計算の複雑さのみを考慮している。
【００７８】
スクエアターボプロダクトコード（ＴＰＣ）符号化データブロックの符号化処理によれば、水平方向及び垂直方向のブロック成分コードは等しい。従って、両方向（行方向及び列方向に沿った）の一の繰り返しにおける復号化の複雑さは、単に、２（ｎ＋１）を乗じた一成分ベクトルの復号化の複雑さであってよい。
【００７９】
本来のＣｈａｓｅアルゴリズム、及び本発明の実施例に係る変形Ｃｈａｓｅアルゴリズムに対する動作数に関する比較を、図５の表にそれぞれ示す。次の表記法が図５に示す表に用いられる。即ち、
ａ）実数加算の回数は、Ｎａで示される。
ｂ）実数乗算の回数は、Ｎｍで示される。
ｃ）コンパレータ動作の回数は、Ｎｃｏｍｐで示される。
ｄ）ＧＦ（２）加算の回数は、Ｎｇで示される。
【００８０】
本来のＣｈａｓｅアルゴリズム、及び本発明の実施例に係る変形Ｃｈａｓｅアルゴリズムの複雑さの比較を用意にするために、ハミングコード（６４，５７，３）を用いて生成されたターボプロダクトコード（ＴＰＣ）に対する両アルゴリズムが要求する異なる動作数の数値を、図６に比の形態で与える。例えば、ｐ＝５でＧＦ（２）加算数Ｎｇに対して、本発明の実施例に係る変形Ｃｈａｓｅアルゴリズムは、本来のＣｈａｓｅアルゴリズムと比較して１９．７倍も小さいＧＦ（２）加算を用いる。
【００８１】
図６に示した比の数値が全て１よりも大きいので、これは本発明の実施例に係る変形Ｃｈａｓｅアルゴリズムは、本来のＣｈａｓｅアルゴリズムと比較して、実数加算、実数乗算、コンパレータ動作又はＧＦ（２）加算を含む全種類の演算について、より少ない演算しか使用しないことを意味する。従って、復号化の複雑さは、本発明の実施例に係る変形Ｃｈａｓｅアルゴリズムを用いてかなり緩和される。
【００８２】
図７は、本発明の実施例に係るデコーダの性能結果を示す図である。図７に示した結果は、公開された本来のＣｈａｓｅアルゴリズムの性能結果と比較すると、本来のＣｈａｓｅアルゴリズムと本発明の実施例に係る変形Ｃｈａｓｅアルゴリズムとの間には、無視できるほどの性能差しかないことを示している。これは、本発明の実施例に係る変形Ｃｈａｓｅアルゴリズムを用いて復号化の複雑さを緩和させても、性能差には損失がないという意味である。
【００８３】
本出願書類には、以下の文献が引用されている。
【非特許文献１】[1] Berrou, C., et al., “Near optimum error correcting coding and decoding: Turbo codes”, IEEE Trans. Commun., vol. 44, no. 10, pp. 1261-1271, Oct. 1996
【非特許文献２】[2] Pyndiah, R., “Near-optimum decoding of product codes; block turbo codes”, IEEE Trans. Commun., vol. 46, no. 8, pp. 1003-1010, Aug. 1998
【非特許文献３】[3] Pyndiah, R., et al., “Near-optimum decoding of product codes”, Proc. IEEE GLOBECOM'94, vol. 1/3, pp. 339-343, Nov. 1994
【非特許文献４】[4] Chase, D., “A class of algorithms for decoding block codes with channel measurement information”, IEEE Trans. Inform. Theory, vol.IT-18, pp. 170-182, Jan. 1972
【図面の簡単な説明】
【００８４】
【図１】図１は、本発明の実施例に係る通信システムを示す図である。
【図２】図２は、本発明の実施例に係る符号化及び復号化処理の中間ステップ及びシンドロームを示す図である。
【図３】図３は、ターボプロダクトコード（ＴＰＣ）の一例を示す図である。
【図４】図４は、本発明の実施例に係るターボプロダクトコード（ＴＰＣ）の一例を示す図である。
【図５】図５は、本来のＣｈａｓｅアルゴリズムと本発明の実施例に係る変形Ｃｈａｓｅアルゴリズムとの間における、ｎ＋１列及びｎ＋１行のスクエアターボプロダクトコード（ＴＰＣ）符号化データブロックの復号化の複雑さの比較例を示す図である。
【図６】図６は、本来のＣｈａｓｅアルゴリズムと本発明の実施例に係る変形Ｃｈａｓｅアルゴリズムとの間における、（６４，５７，３）ハミングコードブロックの復号化の複雑さの比較例を示す図である。
【図７】図７は、本発明の実施例に係るデコーダの性能結果を示す図である。
【符号の説明】
【００８５】
１００  通信システム
１０１  情報源及び入力変換器
１０３  ソースエンコーダ
１０５  チャネルエンコーダ
１０７  デジタル変調器
１１１  デジタル復調器
１１３  チャネルデコーダ
１１５  ソースデコーダ
１１７  出力変換器
４００  ターボプロダクトコード（ＴＰＣ）符号化データブロック
４０１  パリティ検査ビット
【図１】
2009515420.tif 000025
【図２】
2009515420.tif 000026
【図３】
2009515420.tif 000027
【図４】
2009515420.tif 000028
【図５】
2009515420.tif 000029
【図６】
2009515420.tif 000030
【図７】
2009515420.tif 000031
【国際調査報告】
2009515420.tif 000032
2009515420.tif 000033