(57)【要約】【課題】データ衝突を発生させない検査行列を作成可能な検査行列作成方法および符号化器並びに復号器を提供する。【解決手段】検査行列に含まれる各列ブロックに対して、各列ブロックにおける非零要素の位置決めのために、当該列ブロックに設定された列重みに相当する個数の初期値を割り当てる際に、各列ブロックに割り当てられる初期値の組み合わせそれぞれに含まれる当該列ブロックに対応する列重みに相当する個数の初期値が、パリティ長以下の自然数であって、検査行列において隣接する列間における非零要素の行位置の差を示すシフト数ｑを法とする剰余が互いに異なり、かつ、各列ブロックに割り当てられる組み合わせに含まれる初期値が互いに異なるように割り当て対象の初期値を選択し、各列ブロックに対して割り当てられた組み合わせに含まれる初期値に基づいて、当該列ブロックに含まれる各列の非零要素の位置を特定することによって検査行列を作成する。【選択図】      図６
2012244544.tif 000002
【特許請求の範囲】
【請求項１】
ＬＤＧＭ(Low Density Generation Matrix)構造を持つ検査行列に含まれる各列ブロックに対して、前記各列ブロックにおける非零要素の位置決めのために、当該列ブロックに含まれる列内に含まれるべき非零要素の数を示す列重みに相当する個数の初期値を割り当てる際に、
前記各列ブロックに割り当てられる初期値の組み合わせそれぞれに含まれる当該列ブロックに対応する前記列重みに相当する個数の初期値が、パリティ長以下の自然数であって、前記検査行列において隣接する列間における非零要素の行位置の差を示すシフト数ｑを法とする剰余が互いに異なり、
かつ、
前記各列ブロックに割り当てられる組み合わせに含まれる初期値が互いに異なるように割り当て対象の初期値を選択し、
前記各列ブロックに対して割り当てられた組み合わせに含まれる初期値に基づいて、当該列ブロックに含まれる各列の非零要素の位置を特定することによって前記検査行列を作成する
ことを特徴とする検査行列作成方法。
【請求項２】
請求項１に記載の検査行列作成方法において、
前記各列ブロックに初期値の組み合わせを割り当てる手順は、
前記シフト数ｑに等しい個数の互いに前記シフト数ｑを法とする剰余が異なる自然数Ｒ１〜Ｒｑと、これらの自然数Ｒ１〜Ｒｑに前記シフト数ｑとｎ通りの整数ｃ１〜ｃｎとの積を加算して得られるｑ×ｎ個の自然数Ｒ１＋ｑ×ｃ１〜Ｒｑ＋ｑ×ｃｎとを、前記各列ブロックに割り当てる初期値の候補として保持する初期値テーブルを作成し、
前記初期値テーブルから、前記各列ブロックについて、当該列ブロックに対応する列重みで示される個数の初期値の候補を選択する
ことを特徴とする検査行列作成方法。
【請求項３】
請求項２に記載の検査行列作成方法において、
前記初期値の候補を選択する手順は、
前記初期値テーブルに含まれる前記初期値の候補をランダムに並べ替え、
前記初期値テーブルから前記初期値テーブルにおける配列順に従って前記初期値の候補を読み出し、
前記初期値テーブルから新たに初期値の候補が読み出されるごとに、前記読み出された初期値の候補の前記シフト数ｑを法とする剰余とそれまでに同一の列ブロックに対応して読み出された初期値の候補の前記シフト数ｑを法とする剰余とが一致するか否かを判断し、
前記剰余が一致すると判断された初期値の候補に代えて、当該初期値の候補の次の順序に従って前記初期値テーブルに配列された別の初期値の候補を読み出す
ことを特徴とする検査行列作成方法。
【請求項４】
請求項２に記載の検査行列作成方法において、
前記初期値の候補を選択する手順は、
前記初期値テーブルに含まれる前記初期値の候補をランダムに並べ替え、
前記各列ブロックに対応して、前記初期値テーブルから前記初期値テーブルにおける配列順に従って、当該列ブロックの前記列重みで示される個数の前記初期値の候補を読み出し、
前記各列ブロックに対応して読み出された前記初期値の候補組み合わせに、前記シフト数ｑを法とする剰余が同一である初期値の候補の組が含まれているか否かを判断し、
前記剰余が同一である初期値の候補の組が含まれていると判断された場合に、
前記初期値テーブルにおける前記初期値の候補の配列順序を変更し、
前記各列ブロックに対応して、前記初期値テーブルから前記初期値テーブルにおける配列順に従って、当該列ブロックに対応する前記列重みで示される個数の前記初期値の候補を再び読み出す、
ことを特徴とする検査行列作成方法。
【請求項５】
ＬＤＧＭ構造を持つ検査行列に含まれる各列ブロックに対して、前記各列ブロックにおける非零要素の位置決めのために、当該列ブロックに含まれる列内に含まれるべき非零要素の数を示す列重みに相当する個数の初期値を割り当てる割り当て部と、
前記割り当て部によって前記各列ブロックに対して割り当てられた初期値の組み合わせに基づいて、前記検査行列の対応する列ブロックに含まれる各列の非ゼロ成分の位置を特定することによって前記検査行列を生成する作成部と、
前記検査行列を用いて送信信号を符号化する符号化部と
を備え、
前記割り当て部は、
前記各列ブロックに割り当てられる初期値の組み合わせそれぞれに含まれる当該列ブロックに対応する前記列重みに相当する個数の初期値が、パリティ長以下の自然数であって、前記検査行列において隣接する列間における非零要素の行位置の差を示すシフト数ｑを法とする剰余が互いに異なり、
かつ、
前記各列ブロックに割り当てられる組み合わせに含まれる初期値が互いに異なるように  割り当て対象の初期値を選択する
ことを特徴とする符号化器。
【請求項６】
請求項１に記載した検査行列作成方法で作成された検査行列の行および列を所定の規則に従って入れ替ることによって、前記検査行列を前記シフト数ｑに等しい数の階層に分割可能なように変形する変形部と、
前記検査行列作成方法で作成された検査行列を用いて符号化された符号語と前記変形部による変形後の検査行列とついて、前記階層ごとに事後確率を算出する処理を繰り返すことにより前記符号語の復号を行う繰り返し復号部と、
を備え、
前記変形部は、
前記検査行列の各行を、当該行を示す行番号を前記シフト数ｑで除した際の剰余に従って入れ替える行操作部と、
前記検査行列に含まれるパリティ部分行列の各列を、前記パリティ部分行列内で当該列を示す列番号を前記シフト数ｑで除した際の剰余に従って入れ替える列操作部とを備える
ことを特徴とする復号器。
【発明の詳細な説明】
【技術分野】
【０００１】
本件開示は、低密度パリティ検査(ＬＤＰＣ：Low Density Parity Check)符号化のための検査行列作成方法および符号化器並びに復号器に関する。
【背景技術】
【０００２】
ＬＤＰＣ符号を用いて送受信方式では、式(１)に示すように、Ｍ行Ｎ列(Ｎ＞Ｍ)の検査行列Ｈとの積が零行列となるように、Ｍビットのパリティを含むＮビットの送信信号Ｔｘを送信する。
【０００３】
Ｈ×Ｔｘ＝０        ・・・（１）
そして、受信側で、上述した検査行列Ｈとの積が零行列となるように受信信号Ｒｘの誤りを訂正することにより、送信データに一致する受信データを得る。なお、パリティ検査で用いる行列計算の積和演算は、行列の要素の積に代えて論理積を求め、得られた論理積演算結果について排他的論理和を求めることによって行われる。
【０００４】
ＬＤＰＣ復号化に用いられる検査行列Ｈが、ＬＤＧＭ(Low Density Generation Matrix)構造を持つ場合に、生成行列を用いることなくパリティビットを計算することができることが知られている。ＬＤＧＭ構造とは、例えば、行列の右側に位置するＭ行Ｍ列の正方部分行列が、対角線上の要素とその下隣の要素が「１」である二重対角構造を持つ構造である。
【０００５】
ＬＤＧＭ構造の検査行列Ｈは、任意の情報部分行列ＨＡと２重対角構造を持つパリティ部分行列ＨＢとを含む。この情報部分行列ＨＡは、例えば、初期値テーブルからランダムに選択した乱数に基づいて、非零の要素を配置する位置を特定することによって作成することができる(非特許文献１参照)。
【０００６】
上述した初期値テーブルは、例えば、所定数ｑ個の乱数Ｒ１〜Ｒｑとこれらの乱数に所定数ｑの整数倍を加算して得られる擬似乱数を含むように生成することができる。例えば、乱数Ｒ１〜Ｒｑについて、それぞれ行重みｄから１を差し引いた個数(ｄ−１)の擬似乱数を生成すれば、ｑ×ｄ個の乱数を含む初期値テーブルを生成することができる。なお、行重みとは、情報部分行列の各行に含まれる非零の要素の数である。
【０００７】
この初期値テーブルに基づいて、例えば、次のようにして、列ブロックごとに情報部分行列ＨＡを作成してもよい。ここで、列ブロックとは、情報部分行列ＨＡを所定数の列ごとに区切って得られるサブブロックである。各列ブロックには、当該列ブロック内の各列に含まれる非零の要素の数を示す列重みが設定される。
【０００８】
まず、個々の列ブロックについて、当該列ブロックに設定された列重みと同数の乱数が初期値テーブルから選ばれる。次いで、各列ブロックにおける第１列において、当該列ブロックについて選ばれた乱数それぞれで示される行番号の要素に値「１」にセットされ、他の要素に値「０」がセットされる。そして、各列ブロックの以降の各列における非零の要素の位置が、左隣の列において非零の要素が配置された行位置をそれぞれｑ行シフトさせた位置に特定される。
【０００９】
このようにして、非零の要素が行列内にまばらに配置された情報部分行列ＨＡを作成することができる。
【００１０】
ところで、ＬＤＰＣ符号を高速に復号する手法の一つに階層的復号アルゴリズムがある。階層的復号アルゴリズムは、検査行列Ｈを所定数の行ごとに分割して得られる複数の階層ごとに、事後確率の計算を実行する方法である(例えば、特許文献１参照)。
【００１１】
上述したようにして作成された情報部分行列ＨＡを含む検査行列Ｈは、所定の規則に従って行および列を入れ替えることにより、階層的復号アルゴリズムによる復号が可能な検査行列に変形することができる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特表２００８−５２６０８６号公報
【非特許文献】
【００１３】
【非特許文献１】鈴木陽一、榎本明記、小島政明、田中祥次、木村武史、正源和義、「高度衛星デジタル放送の誤り訂正技術」、ＮＨＫ技研  Ｒ＆Ｄ／Ｎｏ．119／2010．１
【発明の概要】
【発明が解決しようとする課題】
【００１４】
ところで、階層的復号アルゴリズムは、階層内に含まれる複数の行についての事後確率の計算処理を並行して行う。このため、階層内に同一の列に非零要素を含む行が複数存在すると、データ衝突(メモリ衝突)が発生し、算出された事後確率に誤差が発生することが報告されている(例えば、特許文献１参照)。
【００１５】
本件開示は、データ衝突を発生させない検査行列を作成可能な検査行列作成方法および符号化器並びに復号器を提供することを目的とする。
【課題を解決するための手段】
【００１６】
一つの観点による検査行列作成方法は、ＬＤＧＭ(Low Density Generation Matrix)構造を持つ検査行列に含まれる各列ブロックに対して、前記各列ブロックにおける非零要素の位置決めのために、当該列ブロックに含まれる列内に含まれるべき非零要素の数を示す列重みに相当する個数の初期値を割り当てる際に、前記各列ブロックに割り当てられる初期値の組み合わせそれぞれに含まれる当該列ブロックに対応する前記列重みに相当する個数の初期値が、パリティ長以下の自然数であって、前記検査行列において隣接する列間における非零要素の行位置の差を示すシフト数ｑを法とする剰余が互いに異なり、かつ、前記各列ブロックに割り当てられる組み合わせに含まれる初期値が互いに異なるように割り当て対象の初期値を選択し、前記各列ブロックに対して割り当てられた組み合わせに含まれる初期値に基づいて、当該列ブロックに含まれる各列の非零要素の位置を特定することによって前記検査行列を作成する。
【００１７】
また、別の観点による符号化器は、ＬＤＧＭ構造を持つ検査行列に含まれる各列ブロックに対して、前記各列ブロックにおける非零要素の位置決めのために、当該列ブロックに含まれる列内に含まれるべき非零要素の数を示す列重みに相当する個数の初期値を割り当てる割り当て部と、前記割り当て部によって前記各列ブロックに対して割り当てられた初期値の組み合わせに基づいて、前記検査行列の対応する列ブロックに含まれる各列の非ゼロ成分の位置を特定することによって前記検査行列を生成する作成部と、前記検査行列を用いて送信信号を符号化する符号化部とを備え、前記割り当て部は、前記各列ブロックに割り当てられる初期値の組み合わせそれぞれに含まれる当該列ブロックに対応する前記列重みに相当する個数の初期値が、パリティ長以下の自然数であって、前記検査行列において隣接する列間における非零要素の行位置の差を示すシフト数ｑを法とする剰余が互いに異なり、かつ、前記各列ブロックに割り当てられる組み合わせに含まれる初期値が互いに異なるように  割り当て対象の初期値を選択する。
【００１８】
更に、別の観点による復号器は、本件開示の検査行列作成方法で作成された検査行列の行および列を所定の規則に従って入れ替ることによって、前記検査行列を前記シフト数ｑに等しい数の階層に分割可能なように変形する変形部と、前記検査行列作成方法で作成された検査行列を用いて符号化された符号語と前記変形部による変形後の検査行列とついて、前記階層ごとに事後確率を算出する処理を繰り返すことにより前記符号語の復号を行う繰り返し復号部と、を備え、前記変形部は、前記検査行列の各行を、当該行を示す行番号を前記シフト数ｑで除した際の剰余に従って入れ替える行操作部と、前記検査行列に含まれるパリティ部分行列の各列を、前記パリティ部分行列内で当該列を示す列番号を前記シフト数ｑで除した際の剰余に従って入れ替える列操作部とを備える。
【発明の効果】
【００１９】
本件開示の検査行列作成方法および符号化器並びに復号器によれば、データ衝突を発生させない検査行列を作成し、ＬＤＰＣ符号化およびＬＤＰＣ復号化に利用することができる。
【図面の簡単な説明】
【００２０】
【図１】検査行列の例を示す図である。
【図２】検査行列Ｈに対する変形処理を説明する図である。
【図３】階層的復号アルゴリズムにおける事後確率の計算順序を説明する図である。
【図４】データ衝突を説明する図である。
【図５】データ衝突が発生する検査行列の例を示す図である。
【図６】本件開示の検査行列作成方法の一実施形態のフローチャートである。
【図７】検査行列作成方法の別実施形態のフローチャートである。
【図８】検査行列作成方法の別実施形態のフローチャートである。
【図９】初期値の組み合わせを選択する処理を説明する図である。
【図１０】検査行列作成方法の別実施形態のフローチャートである。
【図１１】本件開示の符号化器の一実施形態を示す図である。
【図１２】本件開示の符号化器を有する送信装置のハードウェア構成の一例を示す図である。
【図１３】本件開示の復号器の一実施形態を示す図である。
【図１４】本件開示の符号化器および復号器を有する送受信システムの性能を説明する図である。
【図１５】本件開示の復号器を有する受信装置のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００２１】
本件開示の検査行列作成方法および符号化器並びに復号器の実施形態の説明に先立って、階層的復号アルゴリズムを適用する際にデータ衝突を発生させる検査行列が作成される原因を分析する。
【００２２】
まず、階層的復号アルゴリズムを適用する際に、ＬＤＧＭ構造を持つ検査行列に対して施される変形処理について説明する。
【００２３】
図１に、ＬＤＧＭ構造を持つ検査行列の一例を示す。また、図２に、検査行列に対する変形処理を説明する図を示す。
【００２４】
図１は、非特許文献１に開示された方法に従って作成された検査行列の一例である。図１に示した符号ＨＡ、ＨＢは、それぞれ情報部分行列およびパリティ部分行列を示す。情報部分行列ＨＡは、それぞれ所定数Ｎｂの列を含む列ブロックごとに作成される。また、情報部分行列ＨＡは、列重みが大きい列ブロックと列重みが小さい列ブロックを組み合わせて含む。なお、列重みが大きい列ブロックとは、３より大きい列重みを持つ列ブロックを指す場合が多い。一方、列重みが小さい列ブロックとは、列重みが３である列ブロックを指す場合が多い。各列ブロックにおける非零の要素の位置は、初期値テーブルに含まれる乱数から列重みに応じて選ばれた初期値に基づいて特定される。
【００２５】
なお、図１の例では、図の煩雑化を避けるために、列重みが３の列ブロックと列重みが２の列ブロックとを組み合わせて情報部分行列ＨＡを作成する場合を説明する。番号１の列ブロックを含む情報部分行列ＨＡの左側に位置するいくつかの列ブロックに列重み３が割り当てられている。そして、例えば、図１に示した列ブロックＣＢ１には、初期値テーブルから選択された列重みと同数、すなわち、３つの乱数が初期値ｒ１１、ｒ１２、ｒ１３として割り当てられる。一方、番号４の列ブロックを含む情報部分行列ＨＡの右側に位置するいくつかの列ブロックに列重み２が割り当てられている。そして、同様に、列ブロックＣＢ４には、初期値テーブルから選択された列重みと同数、すなわち、２つの乱数が初期値ｒ４１、ｒ４２として割り当てられる。
【００２６】
図１に示した例では、列ブロックＣＢ１に割り当てられた３つの初期値のうち、初期値ｒ１１および初期値ｒ１３に基づいて、各列に含まれる非零の要素の位置が特定される様子を示した。図１からわかるように、列ブロックＣＢ１に含まれる列番号０の列においては、初期値ｒ１１、ｒ１２、ｒ１３で示される行の要素が非零の値を持つ要素となる。そして、列ブロックＣＢ１に含まれる列番号１の列においては、列番号０の列に配置された非零の要素を行方向にｑ行シフトさせた位置に非零の値を持つ要素が配置される。更に、列ブロックＣＢ１に含まれる列番号２の列においては、列番号１の列に配置された非零の要素を行方向にｑ行シフトさせた位置に非零の値を持つ要素が配置される。つまり、列ブロックＣＢ１のｋ(ｋ＝０〜Ｎｂ−１)番目の列において、非零の要素は、初期値ｒ１１、ｒ１２、ｒ１３と行方向へのシフト数ｑとを用いて、それぞれ行番号ｒ１１＋ｋ×ｑ、ｒ１２＋ｋ×ｑ、ｒ１３＋ｋ×ｑで示される位置に配置される。なお、初期値ｒ１１、ｒ１２、ｒ１３とシフト数ｑおよび列番号ｋを用いて求めた行番号がパリティ長Ｍを超える場合に、非零の要素は、それぞれの行番号からパリティ長Ｍを減算した値で示される行位置に配置される。例えば、第ｋ列において非零要素が初期値ｒ１１に基づいて配置される行番号を示す値ｒ１１＋ｋ×ｑがパリティ長Ｍを超えた場合は、行番号ｒ１１＋ｋ×ｑ−Ｍに非零要素が配置される。
【００２７】
同様に、列ブロックＣＢ４の最初の列においては、初期値ｒ４１、ｒ４２で示される行の要素が非零の値を持つ要素となる。そして、列ブロックＣＢ４に含まれる以降の各列における非零の要素の位置は、上述した列ブロックＣＢ１と同様に、左隣の列に配置された非零の要素を行方向にｑ行シフトさせた位置に配置される。つまり、列ブロックＣＢ４のｋ(ｋ＝０〜Ｎｂ−１)番目の列において、非零の要素は、初期値ｒ４１、ｒ４２と行方向へのシフト数ｑとを用いて、それぞれ行番号ｒ４１＋ｋ×ｑ、ｒ４２＋ｋ×ｑで示される位置に配置される。なお、初期値ｒ４１、ｒ４２とシフト数ｑおよび列番号ｋを用いて求めた行番号がパリティ長Ｍを超える場合に、非零の要素は、それぞれの行番号からパリティ長Ｍを減算した値で示される行位置に配置される。
【００２８】
このようにして作成された検査行列は、階層復号アルゴリズムを適用した復号処理に用いる際に、次のようにして、上述したシフト数ｑに等しい数の階層に分割可能な構造に変形される。
【００２９】
検査行列に含まれる各行は、図２に示すように、行番号を上述したシフト数ｑで除算した際の剰余に応じて並べ替えられる。この並べ替えにより、剰余がそれぞれ０〜ｑ−１である行番号を持つ行を含む各階層Ｌ１〜Ｌｑが形成される。また、パリティ部分行列に対しては、更に、列番号をシフト数ｑで除算した際の剰余に応じて並べ替える操作が行われる。
【００３０】
図２に示した例では、各階層Ｌ１〜Ｌｑを各階層の行数Ｐに対応するＰ列×Ｐ行のサブブロックに区切って示した。また、図２において、各サブブロックにおいて、対角線に平行に並んだ非零要素を太い実線で示した。一方、図２において、非零要素の配置を示す線が示されていないサブブロックは、いずれも零行列である。
【００３１】
図２から分かるように、上述した並べ替え操作により、検査行列に含まれる非零要素は、ごく一部のサブブロックの対角線に平行に並ぶ位置に集約される。例えば、図２に符号ＳＢ１で示したサブブロックＳＢ１は、シフト数ｑより小さい初期値に基づいて配置された非零要素が、対角成分として集約されたサブブロックの例である。一方、図２に符号ＳＢ２で示したサブブロックＳＢ２は、シフト数ｑ以上の初期値に基づいて配置された非零要素が、対角線に平行に並ぶサブブロックの例である。
【００３２】
図３に、階層的復号アルゴリズムにおける事後確率の計算順序を説明する図を示す。図３に示した符号Ｔ１，Ｔ２，Ｔ３，・・・は、それぞれ階層１、階層２、階層３，・・・に属する各行に基づく行列演算が行われるタイミングを示している。
【００３３】
階層的復号アルゴリズムでは、各階層に属するＰ行についての行列演算が並列に行われる。そして、前の階層についての行列演算で得られた結果を利用して、次の階層についての行列演算が行われる。つまり、ｊ番目の階層Ｌｊについての行列演算で得られる第ｎ列の事後確率Ｓｕｍ(ｎ)(ｊ)は、階層Ｌｊについての行列演算に関する所定の関数ｆ(ｊ)と階層Ｌｊ−１の第ｎ列の事後確率Ｓｕｍ(ｎ)(ｊ−１)を用いて式(２)のように表される。
【００３４】
Ｓｕｍ(ｎ)(ｊ)＝ｆ(ｊ)(Ｓｕｍ(ｎ)(ｊ−１))      ・・・（２）
このようにして、各階層についての行列演算を行っていき、最後の階層Ｌｑについての行列演算が終了したときに得られる事後確率Ｓｕｍを用いて、パリティ検査による誤り訂正処理が行われる。
【００３５】
ところで、各階層についての行列演算を進めていく過程で、一つの階層に属するＰ行の中に第ｎ列に非零の要素を持つ行が複数行存在する場合に、データ衝突が発生する。
【００３６】
図４に、データ衝突を説明する図を示す。図４において、各階層を示す矩形の右側に示した数式は、対応する階層について、式(２)に示した処理を行うことによって得られる第ｎ列の事後確率を示す。
【００３７】
図４に示した階層Ｌｊ−２および階層Ｌｊ−１のように、第ｎ列に含まれる非零の要素の数が１である場合は、それぞれの階層の右側に示した数式に従って、各階層までの部分についての第ｎ列の事後確率を求めることができる。一方、図４に示した階層Ｌｊには、第ｎ列に非零の要素が配置された複数の行が含まれている。この場合に、非零の要素を含む各行についての演算処理で、階層Ｌｊ−１について得られたＳｕｍ(ｎ)(ｊ−１)を共通して用いると、正しい結果を得ることができない。
【００３８】
なぜなら、図４において、符号Ｅ２で示した非零要素を含む行についての演算は、階層Ｌｊ−１について得られたＳｕｍ(ｎ)(ｊ−１)ではなく、符号Ｅ１で示した非零要素を含む行について得られるＳｕｍ(ｎ)(j)‐Ｅ1を用いて行うべきだからである。このように、階層に含まれるＰ行についての演算を並列処理するために、本来参照するべき演算結果とは異なる前の階層の処理結果を参照して行列演算処理を行ってしまうことが、データ衝突である。
【００３９】
そして、Ｓｕｍ(ｎ)(ｊ−１)を用いて得られる非零要素Ｅ２を含む行についての演算結果と、上述したＳｕｍ(ｎ)(j)‐Ｅ1を用いた場合に得られる非零要素Ｅ２を含む行についての演算結果との間の誤差は、以降の各階層についての演算結果に伝播する。このため、最終的に得られる事後確率Ｓｕｍにも誤差が発生するので、復号器の誤り訂正能力も影響を受けることになる。
【００４０】
図５に、データ衝突が発生する検査行列の一例を示す。図５に示した検査行列の例は、５つの階層に分割されている。また、図５において、各サブブロックにおいて、対角線に平行に並んだ非零要素を太い実線で示した。一方、図５において、非零成分を表す線が示されていないサブブロックは、いずれも零行列である。
【００４１】
図５に示した検査行列の例では、例えば、行番号を階層数５で除算した際の剰余が１である階層Ｌ１と同じく剰余が３である階層Ｌ４に、対角成分を複数個含むサブブロックが含まれている。このため、これらの階層においてデータ衝突が発生する。
【００４２】
ここで、図５に示した検査行列の第０列において非零要素が配置されている行番号は、この第０列を含む列ブロックに割り当てられた初期値を示している。図５に示した例では、上述した列ブロックに割り当てられた初期値は、１，１３，２６，５４，６３である。これらの初期値は、パリティ長１００で示される範囲内でランダムに分布している。しかしながら、並べ替え後の検査行列では、初期値１，２６および初期値１３，６３がそれぞれ階層Ｌ２と階層Ｌ４に集約されてしまっている。
【００４３】
同一の階層に集約される初期値に注目すると、これらの初期値の差は、階層数に一致するシフト数ｑの倍数になっていることが分かる。例えば、階層Ｌ２に集約されている初期値１と初期値２６の差２５は、シフト数ｑの５倍である。同様に、階層Ｌ４に集約されている初期値１３と初期値６３の差５０は、シフト数ｑの１０倍である。つまり、いずれかの列ブロックに割り当てられた初期値の組み合わせの中に、差がシフト数ｑの整数倍となる初期値の組があれば、変形後の検査行列のいずれかの階層において、複数の非零要素を含む列が現れる。なお、差がシフト数ｑの整数倍である数は、言い換えれば、シフト数ｑを法とする剰余が同一である数である。したがって、データ衝突を発生させる初期値の組み合わせの条件は、「シフト数ｑを法とする剰余が同一である初期値を含むこと」のように言い換えることができる。
【００４４】
逆に、各列ブロックに割り当てる初期値の組み合わせに含まれる各初期値のシフト数ｑを法とする剰余が互いに異なっていれば、変形後の検査行列において、同一の階層に複数の初期値に対応して配置された非零の要素が集約されることはない。つまり、検査行列を作成する際に、シフト数ｑを法とする剰余が互いに異なるように、各列ブロックに初期値を割り当てれば、データ衝突を防ぐことができる。
【００４５】
なお、列ブロックに設定された列重みがシフト数ｑより小さい場合は、シフト数ｑを法とする剰余が互いに異なる初期値の組み合わせを各列ブロックに割り当てることができる。この条件が満足される場合は、以下に述べるようにして、データ衝突を発生させない検査行列を作成することが望ましい。
【００４６】
以下、図面に基づいて、本件開示の検査行列作成方法および符号化器並びに復号器の実施形態について詳細に説明する。
【００４７】
図６に、本件開示の検査行列作成方法の一実施形態のフローチャートを示す。
【００４８】
送信装置に含まれる符号化器は、送信データの符号化処理に先立って、図６に示すステップ３０１およびステップ３０２の処理を行って、Ｍ行Ｎ列の検査行列を作成する。検査行列の行数Ｍは、送信データに付加されるパリティ長に等しい。また、検査行列の列数Ｎは、送信データのデータ長Ｎｄとパリティ長Ｍとの和(Ｎｄ＋Ｍ)で示される。
【００４９】
符号化器は、検査行列内のＭ行Ｎｄ列の情報部分行列に含まれる各列ブロックについて、それぞれに設定された列重みに等しい個数の初期値を、以下に挙げる条件を満たすように選択する(ステップ３０１)。
【００５０】
条件１：いずれかの列ブロックに割り当てられる初期値は、パリティ長Ｍ以下の値を持つ自然数であること。
【００５１】
条件２：いずれかの列ブロックに割り当てられる初期値は互いに重複しないこと。
【００５２】
条件３：個々の列ブロックに割り当てられる初期値の組み合わせに含まれる各初期値は、シフト数ｑを法とする剰余が互いに異なること。
【００５３】
ステップ３０１で割り当てられた初期値の組み合わせに基づいて、符号化器は、各列ブロックにおいて非零要素を配置する位置を特定する(ステップ３０２)。
【００５４】
図６に示した検査行列作成方法によれば、検査行列に含まれる情報部分行列の各列ブロックにおいて、シフト数ｑを法とする剰余が互いに異なる初期値に基づいて非零要素を配置することができる。このようにして作成された検査行列に配置された非零要素は、階層的復号アルゴリズムを適用するための変形処理により、シフト数ｑを法とする剰余が同一の行を集めて形成される階層に集約されることはない。つまり、図６に示した検査行列作成方法により、データ衝突を発生させない検査行列を作成することができる。
【００５５】
次に、上述したステップ３０１の処理を具体的に実現する方法について説明する。
【００５６】
図７に、検査行列作成方法の別実施形態のフローチャートを示す。図７に示したフローチャートに含まれるステップ３１１，３１２は、図６に示したステップ３０１に相当する。なお、図７に示したステップのうち、図６に示したステップと同等のものについては、同一の符号を付して示し、その説明は省略する。
【００５７】
符号化器は、まず、上述した条件１，２を満たす所定の個数の自然数を初期値候補として含む初期値テーブルを作成する(ステップ３１１)。例えば、符号化器は、パリティ長以下の値を持つ所定の個数の乱数を発生し、発生した個々の乱数を初期値候補として初期値テーブルに保持してもよい。また、符号化器は、非特許文献１に開示された手法を用いて、シフト数ｑに等しい個数の乱数とこれらの乱数に基づいて生成した擬似乱数とを初期値候補として含む初期値テーブルを作成してもよい。なお、擬似乱数の生成に用いる元の乱数は、シフト数ｑを法とする剰余が互いに異なっていることが望ましい。
【００５８】
次いで、符号化器は、上述したステップ３１１で作成された初期値テーブルから、各列ブロックに対応して、上述した条件３を満たす初期値候補の組み合わせを選択する(ステップ３１２)。
【００５９】
図７に示した検査行列作成方法によれば、望ましい初期値候補を含む初期値テーブルから条件３を満たすように、各列ブロックに割り当てる初期値の組み合わせを選択することができる。例えば、非特許文献１に開示された手法を用いて作成された初期値テーブルから初期値の組み合わせを選択することにより、検査行列において非零要素を、不規則でありながら偏りなく、しかもまばらに配置することができる。
【００６０】
次に、非特許文献１に開示された手法を用いて作成された初期値テーブルから各列ブロックに割り当てる初期値の組み合わせを選択する処理に好適な処理手順について説明する。
【００６１】
図８に、検査行列作成方法の別実施形態のフローチャートを示す。また、図９に、初期値の組み合わせを選択する処理を説明する図を示す。なお、図８に示したステップのうち、図７に示したステップと同等のものについては、同一の符号を付して示し、その説明は省略する。また、図８に示したフローチャートに含まれるステップ３２１〜ステップ３２８は、図７に示したステップ３１２に相当する。
【００６２】
図８に示したステップ３１１において、符号化器は、図９(Ａ)に示すような初期値候補を含む初期値テーブルを作成する。図９(Ａ)に示した初期値候補の例は、パリティ長Ｍ＝１００を上限として、シフト数ｑ＝５に等しい５個の乱数１，１７，１３，４，１０それぞれについて、行重みｄ＝４に等しい４個の擬似乱数を生成した場合を示している。なお、図９(Ａ)の組ＩＤ欄に示した符号Ｇ１、Ｇ２，Ｇ３，Ｇ４，Ｇ０は、それぞれ元の乱数とこの乱数に基づいて生成された擬似乱数とを含む初期値候補のグループを示す。
【００６３】
上述したように、符号化器は、各乱数に対応する擬似乱数を、元の乱数にシフト数ｑの整数倍を加算して生成する。したがって、図９(Ａ)に示した各組ＩＤで示されるグループに含まれる初期値候補のシフト数ｑを法とする剰余は、いずれも、元の乱数のシフト数ｑを法とする剰余に一致する。つまり、図９(Ａ)に組ＩＤに対応して示した初期値候補の組み合わせは、それぞれ同一の剰余系に属する。
【００６４】
このようにして生成された初期値候補を含む初期値テーブルについて、符号化器は、初期値テーブルに含まれるｑ×ｄ個の初期値候補をランダムに並べ替える処理を行う(図８のステップ３２１)。符号化器は、例えば、図９(Ｂ)に示すように、図９(Ａ)に示した２０個の初期値候補を、それぞれが属するグループを区別することなく並べ替えてもよい。なお、図９(Ｂ)において、並べ替えられた各初期値候補を示す欄の下に示した符号は、各初期値候補が属するグループを示す組ＩＤを示す。
【００６５】
次に、符号化器は、上述したようにして並べ替えられた配列順に従って、割り当て対象の列ブロックに対応して、初期値テーブルから一つの初期値候補を読み出す(図８のステップ３２２)。ステップ３２２で読み出された初期値候補について、符号化器は、割り当て対象の列ブロックに対応して既に決定された初期値のいずれかと同一のグループに属しているか否かを判定する(ステップ３２３)。符号化器は、例えば、上述した組ＩＤに基づいて、新たに読み出された初期値候補と既に当該列ブロックに割り当てられた初期値とが属するグループが同一であるか否かを判定してもよい。
【００６６】
図９(Ｃ)に、図９(Ｂ)に示した順に配列された初期値候補から、６つの列ブロックＣＢ１〜ＣＢ６に初期値を割り当てていく様子を示す。なお、図９(Ｃ)の例では、番号１の列ブロックＣＢ１に列重み５が、他の列ブロックＣＢ２〜ＣＢ６には列重み３が設定されている。
【００６７】
例えば、列ブロックＣＢ１について最初の初期値候補が読み出されたときには、未だ、既に割り当てられた初期値がない。このような場合に、符号化器は、新たに読み出した初期値候補と同一のグループに属する割り当て済みの初期値はないと判定する(ステップ３２３の否定判定)。この場合に、符号化器は、ステップ３２２で読み出した初期値候補(例えば。初期値候補「１３」)を割り当て対象の列ブロックに割り当てる初期値の組み合わせに含める(ステップ３２４)。次いで、符号化器は、初期値テーブルからの読出位置を次の初期値候補の配列順に進める(ステップ３２５)。その後、符号化器は、割り当て対象の列ブロックについて、列重みで示される個数の初期値の割り当てが完了したか否かを判定する(ステプ３２６)。初期値の組み合わせに含まれる初期値の数が列重み未満である場合に、符号化器は、ステップ３２６の否定判定として、ステップ３２２の処理に戻る。そして、符号化器は、初期値テーブルから新たな初期値候補を読み出す。
【００６８】
図９(Ｂ)のように初期値候補が並べられている場合に、符号化器は、上述した初期値候補「１３」に続いて、図８のステップ３２２において、初期値候補「６３」を読み出す。この場合に、列ブロックＣＢ１に割り当てる初期値の組み合わせには、既に、同一の組ＩＤで示される剰余が同一であるグループに属する初期値「１３」が含まれている。したがって、符号化器は、新たに読み出された初期値候補「６３」について、同一のグループに属する初期値があると判定する(ステップ３２３の肯定判定)。この場合に、符号化器は、ステップ３２４をスキップしてステップ３２５の処理に進む。このようにして、符号化器は、既に初期値の組み合わせに含まれている初期値と同一の剰余を持つグループに属する初期値候補を、割り当て対象の列ブロックに対応する初期値の組み合わせに含めないでスキップする。そして、符号化器は、ステップ３２６の肯定判定を経てステップ３２２の処理に進んだ際に、この初期値候補に続いて初期値テーブルに配列された別の初期値候補を読み出す。
【００６９】
図９(Ｂ)に示した配列順に基づいて説明すると、上述した初期値候補「６３」をスキップした後に、符号化器は、新たな初期値候補「５４」を初期値テーブルから読み出す。新たに読み出した初期値候補「５４」は、既に初期値の組み合わせに含まれている初期値「１３」とは異なるグループに属している(ステップ３２３の否定判定)。この判定結果に応じて、符号化器は、この初期値候補「５４」を列ブロックＣＢ１に割り当てる初期値の組み合わせに含める処理を行う(ステップ３２４)。
【００７０】
符号化器は、上述したステップ３２２〜ステップ３２６の処理を、ステップ３２６において、割り当て対象の列ブロックに設定された列重み分の初期値の割り当てが完了したと判定するまで繰り返す。例えば、列ブロックＣＢ１に割り当てる初期値の組み合わせを選択する過程で、符号化器は、図９(Ｃ)に示した初期値候補「１３」，「６３」，「５４」，「１」，「２６」，「１０」，「７６」，「６７」を読み出す。そして、符号化器は、これらの初期値候補のうち、初期値候補「６３」，「２６」，「７６」をスキップする。そして、これらのスキップされた初期値候補に代えて、符号化器は、初期値テーブルにおいてこれらの初期値候補の次に配列された初期値候補「５４」，「１０」，「６７」を読み出す。図９(Ｃ)に示した例では、スキップされた初期値候補の代わりに読み出された初期値候補「５４」，「１０」，「６７」は、いずれも、既に初期値の組み合わせに含まれている他の初期値とは異なるグループに属している。このため、これらの初期値候補「５４」，「１０」，「６７」は、いずれも列ブロックＣＢ１に割り当てられる初期値の組み合わせに含められる。このようにして、符号化器は、互いにシフト数ｑを法とする剰余が異なるグループに属する初期値の組み合わせを、列ブロックＣＢ１に割り当てることができる。なお、図９(Ｃ)において、スキップされた初期値候補を、二重取り消し線を付して示した。
【００７１】
このようにして、割り当て対象の列ブロックに設定された列重みで示される個数の初期値を含む初期値の組み合わせの選択が完了したときに(ステップ３２６の肯定判定)、符号化器は、ステップ３２７の処理に進む。
【００７２】
ステップ３２７で、符号化器は、全ての列ブロックについて初期値の組み合わせを選択する処理が完了したか否かを判定する。未だ初期値の組み合わせの選択が完了していない列ブロックがある場合に(ステップ３２７の否定判定)、符号化器は、前の列ブロックについての処理でスキップした初期値候補を初期値テーブルに戻す処理を行う(ステップ３２８)。符号化器は、例えば、初期値テーブルの最後に配列された初期値候補の後に、スキップした初期値候補を配列してもよい。
【００７３】
その後、符号化器は、ステップ３２８で戻された初期値候補を含む初期値テーブルから、新しく割り当て対象となった列ブロックに対して割り当てる初期値の組み合わせを選択する処理を開始する。
【００７４】
符号化器は、ステップ３２７において、全ての列ブロックについて初期値の組み合わせを選択する処理が完了したと判定されるまで、ステップ３２２〜ステップ３２８の処理を繰り返す。このようにして、符号化器は、各列ブロックに対してそれぞれ列重みに等しい個数の初期値の組み合わせを割り当てる。
【００７５】
例えば、図９(Ｃ)に列ブロックＣＢ２に対応して示した初期値「３８」，「８５」，「４」は、図９(Ｂ)に示した配列順に従って初期値テーブルから読み出された初期値候補である。このように、初期値テーブルから順に読み出した初期値候補「３８」，「８５」，「４」が、互いに異なるグループに属している場合に、符号化器は、読み出した初期値候補をそのまま初期値の組み合わせに含める。
【００７６】
同様に、列ブロックＣＢ３についての処理で、符号化器は、順に初期値テーブルから読み出した初期値候補「８８」、「２９」をそれぞれ初期値の組み合わせに含める。その後、初期値候補「２９」に続いて配列された初期値候補「７９」を読み出したときに、符号化器は、この初期値候補「７９」を、初期値「２９」と同一の剰余を持つグループに属することからスキップする。そして、符号化器は、この初期値候補「７９」に代えて、次に初期値テーブルから読み出した初期値候補「９２」を、列ブロックＣＢ３に割り当てる初期値の組み合わせに含める。
【００７７】
同様にして、符号化器は、列ブロックＣＢ４に対して、初期値「３５」，「１７」，「５１」を含む初期値の組み合わせを割り当てる。この過程で、符号化器は、初期値候補「６０」，「４２」を、それぞれ既に初期値の組み合わせに含まれている初期値「３５」，「１７」と同一のグループに属するとの判断に基づいてスキップする。
【００７８】
以降に割り当てが行われる列ブロックＣＢ５，ＣＢ６についての処理で、符号化器は、列ブロックＣＢ１〜ＣＢ４についての処理でスキップされた初期値候補の中から選択した初期値候補を初期値の組み合わせに含める。例えば、符号化器は、列ブロックＣＢ５についての割り当て処理の過程で、列ブロックＣＢ１についての処理でスキップされた初期値候補「６３」，「２６」，「７６」を初期値テーブルから読み出す。そして、符号化器は、これらの初期値候補のうち初期値候補「６３」，「２６」を列ブロックＣＢ５に割り当てる初期値の組み合わせに含める。一方、符号化器は、初期値「２６」と同一のグループに属することから、初期値候補「７６」を再びスキップする。そして、符号化器は、この初期値候補「７６」に代えて、初期値テーブルから読み出した初期値候補「７９」を、列ブロックＣＢ５に割り当てる初期値の組み合わせに含める。列ブロックＣＢ５についての処理過程で再びスキップされた初期値候補「７６」は、再び初期値テーブルに戻される。そして、この初期値候補「７６」は、列ブロックＣＢ６についての処理で、符号化器により、列ブロックＣＢ４についての処理過程でスキップした初期値候補「６０」，「４２」とともに初期値の組み合わせに含められる。
【００７９】
このようにして、符号化器は、各列ブロックに対して、それぞれシフト数ｑを法とする剰余が互いに異なるグループに属する列重み等しい個数の初期値を含む初期値の組み合わせを割り当てることができる。
【００８０】
そして、これらの初期値の組み合わせに基づいて、図８に示したステップ３０２において、符号化器は、検査行列に含まれる各列ブロックにおける非零要素の配置を決定する。
【００８１】
上述したようにして作成された検査行列に含まれる個々の列ブロックに含まれる各列において、非零要素は、シフト数ｑを法とする剰余が互いに異なる初期値から順次にシフト数ｑで示される行数ずつずらして配置される。したがって、階層的復号アルゴリズムを適用するために行われる変形処理によって、任意の列ブロックに割り当てられた互いに異なる初期値に基づいて配置された非零要素は、必ず、互いに異なる階層にそれぞれ集約される。故に、図８に示した検査行列作成方法の一実施形態によれば、階層的復号アルゴリズムを適用する際にデータ衝突を発生させない検査行列を作成することができる。
【００８２】
図１０に、検査行列作成方法の別実施形態のフローチャートを示す。なお、図１０に示したステップのうち、図７、８に示したステップと同等のものについては、同一の符号を付して示し、その説明は省略する。また、図１０に示したフローチャートに含まれるステップ３２１〜ステップ３２７およびステップ３３０〜ステップ３３１は、図７に示したステップ３１２に相当する。
【００８３】
図１０に示した検査行列作成方法を実行する際に、符号化器は、各列ブロックを割り当て対象として、ステップ３２２の処理とステップ３２４〜ステップ３２７の処理とを繰り返す。この過程で、符号化器は、初期値テーブルにおける配列順に従って、各列ブロックに、それぞれ列重みに等しい個数の初期値候補を割り当てる。そして、全ての列ブロックに初期値の組み合わせを割り当てる初期値の組み合わせを選択したときに(ステップ３２７の肯定判定)、符号化部は、ステップ３３０の処理に進む。
【００８４】
ステップ３３０において、符号化器は、各列ブロックに割り当てられた初期値の組み合わせに含まれる各初期値のシフト数ｑを法とする剰余が互いに異なるか否かを判定する。いずれかの列ブロックに対応する初期値の組み合わせに、シフト数ｑを法とする剰余が同一である初期値の組が含まれている場合に、符号化器は、ステップ３３０の否定判定として、ステップ３３１の処理に進む。
【００８５】
ステップ３３１の処理で、符号化器は、全ての列ブロックに対してそれぞれ割り当てた初期値の組み合わせを廃棄する。その後、符号化器は、ステップ３２１の処理に戻って、初期値テーブルに含まれる初期値候補を再びランダムに並べ替える処理を行う。そして、並べ替えられた初期値テーブルから、各列ブロックに割り当てる初期値の組み合わせを選択する処理を再び開始する。
【００８６】
つまり、ステップ３３０において、上述した条件３を満たさない初期値の組み合わせを検出するごとに、符号化器は、初期値テーブル内の初期値候補を並べ替えた上で、新たに各列ブロックに割り当てる初期値の組み合わせを選択する処理を行う。そして、各列ブロックに対して割り当てられた初期値の組み合わせの全てが上述した条件３を満たすときに(ステップ３３０の肯定判定)、符号化器は、これらの初期値の組み合わせに基づいて各列の非零要素を配置する(ステップ３０２)。
【００８７】
このようにして、図１０に示した検査行列作成方法の一実施形態により、階層的復号アルゴリズムを適用する際にデータ衝突を発生させない検査行列を作成することができる。
【００８８】
なお、図７に示したステップ３１２を実現する方法は、図８、図１０のフローチャートで示した手法に限られず、他のいかなる手法を用いてもよい。例えば、上述した初期値テーブルの並べ替えの代わりに、シフト数ｑを法とする剰余が同一である初期値候補を含む各グループ内で、これらの初期値候補をランダムに並べ替え、各グループから一つずつ順に初期値テーブルに配列してもよい。このようにして並べ替えられた初期値テーブルを用いれば、配列順に各列ブロックに列重み分の初期値候補を読み出すことにより、上述した条件３を満たすように、初期値の組み合わせを選択することができる。
【００８９】
次に、本件開示の符号化器の実施形態について説明する。
【００９０】
図１１に、本件開示の符号化器の一実施形態を示す。図１１において、符号化対象の送信データは、符号Ｄｉｎで示した入力端子を介して符号化器に入力される。また、符号化器によって得られた符号出力は、符号Ｃｏｕｔで示した出力端子を介して出力される。
【００９１】
図１１に示した符号化器は、割り当て部１１と、作成部１２と、符号化部１３とを含んでいる。また、割り当て部１１は、初期値テーブル作成部１４と、保持部１５と、選択部１６と、選択制御部１７とを含んでいる。
【００９２】
初期値テーブル作成部１４は、まず、シフト数ｑを法とする剰余が互いに異なるｑ個の乱数と、これらの乱数に基づいて作成した擬似乱数とを含むｑ×ｄ個の初期値候補を、パリティ長以下の値の範囲で生成する。初期値テーブル作成部１４は、例えば、図７に示したステップ３１１の処理で説明した手法を用いて、上述した条件１，２を満たす各初期値候補を生成してもよい。次いで、初期値テーブル作成部１４は、これらの初期値候補をランダムに配列することにより、初期値テーブルを作成する。保持部１５は、作成された初期値テーブルを保持する。
【００９３】
選択部１６は、保持部１５に保持された初期値テーブルに含まれる初期値候補から各列ブロックに割り当てる初期値の組み合わせを選択する処理を、選択制御部１７からの指示に従って実行する。選択部１６は、例えば、図１０を用いて説明したステップ３２２〜ステップ３２７の処理を実行することにより、各列ブロックに割り当てる初期値の組み合わせの候補を選択してもよい。そして、選択制御部１７は、例えば、図１０を用いて説明したステップ３３０、ステップ３３１およびステップ３２１の処理を行うことにより、選択部１６に上述した条件３を満たす初期値の組み合わせを選択させてもよい。
【００９４】
このようにして、割り当て部１１は、上述した３つの条件を満たす初期値の組み合わせを、各列ブロックに割り当てることができる。
【００９５】
割り当て部１１によって各列ブロックに割り当てられた初期値の組み合わせに基づいて、作成部１２は、検査行列に含まれる情報部分行列の各列ブロックにおいて非零要素を配置する処理を行う。更に、作成部１２は、上述したようにして非零要素が配置された情報部分行列と二重対角構造を持つパリティ部分行列とを組み合わせることにより、検査行列を作成する。
【００９６】
符号化部１３は、上述したようにして作成された検査行列Ｈと送信信号Ｔｘとの積がゼロ行列になるように、送信データＤにＭビットのパリティを付加することにより、送信データを符号化する。
【００９７】
図１１に例示した符号化器によれば、データ衝突を発生させないように非零要素が配置された検査行列を作成する検査行列作成処理を実現することができる。そして、この符号化器は、本件開示の検査行列作成法穂によって作成された検査行列を用いて、送信データの符号化を行うことができる。
【００９８】
図１２に、本件開示の符号化器を含む送信装置のハードウェア構成の一例を示す。図１２に示した送信装置は、符号化器２０と、送信回路２５とを含む。また、符号化器２０は、プロセッサ２１と、メモリ２２と、データ入力部２３と、行列演算部２４と、送信回路２５とを含む。
【００９９】
プロセッサ２１と、メモリ２２と、データ入力部２３と、行列演算部２４と、送信回路２５とは、バスを介して接続される。また、送信回路２５は、符号化器２０によって生成される送信信号Ｔｘを、このバスを介して受け取る。そして、送信回路２５は、受け取った送信信号Ｔｘを、例えば、アンテナを介して無線送信する。
【０１００】
メモリ２２には、送信装置を動作させるためのシステムプログラムおよび上述した検査行列作成処理を実行するためのアプリケーションプログラムが格納されている。アプリケーションプログラムは、本件開示の検査行列作成方法に含まれる各処理を実行するためのプログラムを含む。
【０１０１】
図１２に例示した送信装置は、上述したプロセッサ２１、メモリ２２などのハードウェアと、システムプログラムおよびアプリケーションプログラムなどのプログラムとが有機的に協働することにより、上述した各種機能を実現する。
【０１０２】
例えば、図１１に例示した初期値テーブル作成部１４の機能は、プロセッサ２１が、図７に示したステップ３１１の処理のためのプログラムを実行することによって実現してもよい。また、保持部１５は、メモリ２２の記憶容量の一部に初期値テーブルを表す情報を格納することによって実現してもよい。また、図１１に例示した選択部１６および選択制御部１７の機能は、プロセッサ２１が、メモリ２２に格納された初期値テーブルを表す情報を用いて、図７に示したステップ３１２の処理のためのプログラムを実行することによって実現してもよい。なお、プロセッサ２１は、ステップ３１２に相当する処理として、図８に示したステップ３２２〜ステップ３２８の処理を実行することによって、選択部１６および選択制御部１７の機能を実現してもよい。同様に、プロセッサ２１は、ステップ３１２に相当する処理として、図１０に示したステップ３２１〜ステップ３３１の処理を実行することによって、選択部１６および選択制御部１７の機能を実現してもよい。また、図１１に例示した作成部１２の機能は、プロセッサ２１が、図６に示したステップ３０２の処理のためのプログラムを実行することによって実現してもよい。そして、作成された検査行列を表す情報は、メモリ２２に保持される。また、図１１に例示した符号化部１３の機能は、プロセッサ２１とメモリ２２に保持された検査行列を表す情報と行列演算部２４とが協働することによって実現してもよい。なお、図１１に示した各部の処理過程で生成される情報は、メモリ２２に格納される。
【０１０３】
次に、本件開示の復号器の実施形態について説明する。
【０１０４】
図１３に、本件開示の復号器の一実施形態を示す。図１３において、復号対象の受信信号は、符号Ｃｉｎで示した入力端子を介して復号器に入力される。また、復号器によって得られた復号データは、符号Ｄｏｕｔで示した出力端子を介して出力される。
【０１０５】
図１３に例示した復号器は、検査行列保持部３０と、変形部３１と、繰り返し復号部３４とを含んでいる。また、変形部３１は、行操作部３２と、列操作部３３とを含んでいる。
【０１０６】
検査行列保持部３０は、上述した検査行列作成方法によって作成された検査行列Ｈを表す情報を保持している。
【０１０７】
そして、変形部３１は、検査行列保持部３０に保持されている検査行列に対して、図２を用いて説明したようにして、階層的復号アルゴリズムを適用するための変形処理を行う。変形部３１の行操作部３２は、検査行列に含まれる各行を、行番号をシフト数ｑで除算した際の剰余に基づいて入れ替える操作を行う。列操作部３３は、検査行列に含まれるパリティ部分行列に対して、このパリティ部分行列に含まれる各列を、列番号をシフト数ｑで除算した際の剰余に基づいて入れ替える操作を行う。
【０１０８】
繰り返し復号部３４は、上述したようにして変形された検査行列を用いた階層的復号アルゴリズムに従って、入力端子Ｃｉｎを介して入力される受信信号から誤り訂正された受信データを生成する。
【０１０９】
上述した検査行列作成方法によって作成された検査行列において、非零要素は、階層復号アルゴリズムを適用するための変形を行った後にデータ衝突を発生させないように配置されている。したがって、繰り返し復号部３４は、各階層に含まれるＰ行についての行列演算を並行して行うことにより、繰り返し復号処理のそれぞれの回において、データ衝突による誤差を含まない正確な事後確率を得ることができる。つまり、本件開示の検査行列作成方法によって作成された検査行列を用いることにより、復号器によって実現可能な復号性能を向上することができる。
【０１１０】
図１４に、本件開示の符号化器および復号器を有する送受信システムの性能を説明する図を示す。
【０１１１】
本出願人は、本件開示の検査行列作成方法を適用した符号化器および復号器を有する送受信システムの性能を評価するためのシミュレーションを行った。図１４は、このシミュレーション結果を示している。図１４において、本件開示の検査行列作成方法によって作成した３９８４列６６４行の検査行列を用いた場合のＢＥＲ（Bit Error Rate）特性を太い実線で示した。一方、図１４に太い破線で示したＢＥＲ（Bit Error Rate）特性は、非特許文献１に開示された手法で作成された同じく３９８４列６６４行の検査行列を用いて実現される特性である。このシミュレーションは、最大繰返し回数を２０回と設定した階層的復号アルゴリズムを用いて、計算処理は浮動小数点で行った。
【０１１２】
図１４から分かるように、本件開示の検査行列作成方法で作成した検査行列を用いることにより、ＢＥＲ特性を向上することができる。例えば、ＢＥＲ１０−４となるＳＮＲ(signal noise ratio)は、本件開示の検査行列作成方法で作成した検査行列を用いた場合が約３．３ｄＢであるのに対して、非特許文献１に開示された手法で作成された検査行列を用いた場合は約３．５ｄＢである。つまり、本件開示の検査行列作成方法で作成した検査行列を用いることにより、非特許文献１に開示された手法で作成された検査行列を用いた場合に比べて約０．２ｄＢの利得を得ることができる。このような効果は、本件開示の検査行列作成方法で作成した検査行列を用いた場合には、階層的復号アルゴリズムを適用した際に、データ衝突による誤差が発生しないことから得られる。
【０１１３】
図１５に、本件開示の復号器を含む受信装置のハードウェア構成の一例を示す。図１５に示した受信装置は、復号器４０と、データ出力部４５とを含む。また、復号器４０は、プロセッサ４１と、メモリ４２と、受信回路４３と、行列演算部４４とを含む。
【０１１４】
プロセッサ４１と、メモリ４２と、受信回路４３と、行列演算部４４と、データ出力部４５とは、バスを介して接続される。また、データ出力部４５は、復号器４０によって復号された受信データＤｘを、このバスを介して受け取る。そして、データ出力部４５は、受け取った受信データＤｘを、例えば、出力端子Ｄｏｕｔを介して出力する。
【０１１５】
メモリ４２には、受信装置を動作させるためのシステムプログラムおよび上述した復号処理を実行するためのアプリケーションプログラムが格納されている。アプリケーションプログラムは、階層的復号アルゴリズムに基づく復号処理に含まれる各処理を実行するための従来のプログラムと同等である。
【０１１６】
図１５に例示した受信装置は、上述したプロセッサ４１、メモリ４２などのハードウェアと、システムプログラムおよびアプリケーションプログラムなどのプログラムとが有機的に協働することにより、上述した各種機能を実現する。
【０１１７】
例えば、検査行列保持部３０は、メモリ４２の記憶容量の一部に検査行列を表す情報を格納することによって実現してもよい。また、図１３に例示した変形部３１の機能は、プロセッサ４１が、階層的復号アルゴリズムに基づく復号処理に含まれる検査行列変形処理のためのプログラムを、メモリ４２に保持された検査行列を表す情報に対して実行することによって実現してもよい。また、図１１に例示した繰り返し復号部３４の機能は、プロセッサ４１とメモリ４２に保持された検査行列Ｈを表す情報と行列演算部４４とが協働することによって実現してもよい。
【０１１８】
上述したように、本件開示の検査行列作成方法によって作成された検査行列を用いて符号化された送信信号は、階層的復号アルゴリズムに基づく従来の復号処理と同等の復号処理によって復号することができる。したがって、既存の受信装置を、そのまま、本件開示の検査行列作成方法によって作成された検査行列を用いて符号化された送信信号を受信する受信装置として利用することができる。
【符号の説明】
【０１１９】
１１…割り当て部；１２…作成部；１３…符号化部；１４…初期値テーブル作成部；１５…保持部；１６…選択部；１７…選択制御部；２０…符号化器；２１，４１…プロセッサ；２２，４２…メモリ；２３…データ入力部；２４，４４…行列演算部；２５…送信回路；３０…検査行列保持部；３１…変形部；３２…行操作部；３３…列操作部；３４…繰り返し復号部；４３…受信回路；４５…データ出力部
【図１】
2012244544.tif 000003
【図２】
2012244544.tif 000004
【図３】
2012244544.tif 000005
【図４】
2012244544.tif 000006
【図５】
2012244544.tif 000007
【図６】
2012244544.tif 000008
【図７】
2012244544.tif 000009
【図８】
2012244544.tif 000010
【図９】
2012244544.tif 000011
【図１０】
2012244544.tif 000012
【図１１】
2012244544.tif 000013
【図１２】
2012244544.tif 000014
【図１３】
2012244544.tif 000015
【図１４】
2012244544.tif 000016
【図１５】
2012244544.tif 000017