(57)【要約】【課題】良好な受信品質を得ること。【解決手段】差集合巡回符号の検査行列Ｈｏｒｇがプロトグラフとして用いられ、かつ、当該プロトグラフが対角線上に配置された検査行列Ｈに基づいて符号化を施す場合において、差集合巡回符号化部５１０は、検査行列Ｈｏｒｇに基づいて入力データに対し差集合巡回符号化を施し、記憶部５２０は、当該プロトグラフと異なる位置に「１」を追加することにより、複数のプロトグラフを結合した結果、検査行列Ｈの検査式に含まれる過去の符号語を保持し、パリティ修正部５３０は、記憶部５２０に保持された過去の符号語を用いて、差集合巡回符号化部５１０から出力されるパリティビットを修正する。【選択図】図６
2009100234.tif 000002
【特許請求の範囲】
【請求項１】
差集合巡回符号の検査行列がプロトグラフとして用いられ、かつ、当該プロトグラフが対角線上に配置された検査行列に基づいて符号化を施す符号化器であって、
入力データに対し差集合巡回符号化を施し、組織化ビット及びパリティビットから成る符号語を生成する差集合巡回符号化手段と、
過去の前記符号語のうち、前記プロトグラフを結合した場合に、前記検査行列の検査式に含まれる過去の前記符号語を保持する記憶手段と、
前記記憶手段に保持された過去の前記符号語を用いて、前記差集合巡回符号化手段から出力される前記パリティビットを修正するパリティ修正部と、
を具備する符号化器。
【請求項２】
前記記憶手段は、過去の前記組織化ビットを記憶し、
前記パリティ修正手段は、過去の前記組織化ビットを用いて、前記差集合巡回符号化手段から出力される前記パリティビットを修正する
請求項１に記載の符号化器。
【請求項３】
前記記憶手段は、過去の前記パリティビットを記憶し、
前記パリティ修正手段は、過去の前記パリティビットを用いて、前記差集合巡回符号化手段から出力される前記パリティビットを修正する
請求項１に記載の符号化器。
【請求項４】
差集合巡回符号の検査行列がプロトグラフとして用いられ、かつ、当該プロトグラフが対角線上に配置された検査行列を用いて符号化を施す符号化方法であって、
入力データに対し差集合巡回符号化を施し、組織化ビット及びパリティビットから成る符号語を生成するステップと、
過去の前記符号語のうち、前記プロトグラフを結合した場合に、前記検査行列の検査式に含まれる過去の前記符号語を保持するステップ、
保持された過去の前記符号語を用いて、生成される前記パリティビットを修正するステップと、
を有する符号化方法。
【請求項５】
差集合巡回符号の検査行列Ｈｏｒｇがプロトグラフとして用いられ、かつ、当該プロトグラフが対角線上に配置され、かつ、複数の当該プロトグラフを結合するために、当該プロトグラフと異なる位置に「１」が追加された、検査行列Ｈに基づいて符号化された符号語を復号する復号方法であって、
当該プロトグラフと異なる位置に追加された「１」により前記検査行列Ｈの検査式に含まれる過去の符号語が、他の過去の符号語に置き換わるように、前記検査行列Ｈに対し、前記追加される「１」の位置が変更された検査行列Ｈ１を用いて、復号を施す復号方法。
【請求項６】
ＬＤＰＣ−ＢＣの検査行列がプロトグラフとして用いられ、かつ、当該プロトグラフが対角線上に配置された検査行列に基づいて符号化を施す符号化器であって、
入力データに対しＬＤＰＣ−ＢＣ符号化を施し、組織化ビット及びパリティビットから成る符号語を生成するＬＤＰＣ−ＢＣ符号化手段と、
過去の前記符号語のうち、前記プロトグラフを結合した場合に、前記検査行列の検査式に含まれる過去の前記符号語を保持する記憶手段と、
前記記憶手段に保持された過去の前記符号語を用いて、前記ＬＤＰＣ−ＢＣ符号化手段から出力される前記パリティビットを修正するパリティ修正部と、
を具備する符号化器。
【請求項７】
前記記憶手段は、過去の前記組織化ビットを記憶し、
前記パリティ修正手段は、過去の前記組織化ビットを用いて、前記ＬＤＰＣ−ＢＣ符号化手段から出力される前記パリティビットを修正する
請求項１に記載の符号化器。
【請求項８】
前記記憶手段は、過去の前記パリティビットを記憶し、
前記パリティ修正手段は、過去の前記パリティビットを用いて、前記ＬＤＰＣ−ＢＣ符号化手段から出力される前記パリティビットを修正する
請求項１に記載の符号化器。
【請求項９】
ＬＤＰＣ−ＢＣの検査行列がプロトグラフとして用いられ、かつ、当該プロトグラフが対角線上に配置された検査行列を用いて符号化を施す符号化方法であって、
入力データに対しＬＤＰＣ−ＢＣ符号化を施し、組織化ビット及びパリティビットから成る符号語を生成するステップと、
過去の前記符号語のうち、前記プロトグラフを結合した場合に、前記検査行列の検査式に含まれる過去の前記符号語を保持するステップ、
保持された過去の前記符号語を用いて、生成される前記パリティビットを修正するステップと、
を有する符号化方法。
【請求項１０】
ＬＤＰＣ−ＢＣの検査行列Ｈｏｒｇがプロトグラフとして用いられ、かつ、当該プロトグラフが対角線上に配置され、かつ、複数の当該プロトグラフを結合するために、当該プロトグラフと異なる位置に「１」が追加された、検査行列Ｈに基づいて符号化された符号語を復号する復号方法であって、
当該プロトグラフと異なる位置に追加された「１」により前記検査行列Ｈの検査式に含まれる過去の符号語が、他の過去の符号語に置き換わるように、前記検査行列Ｈに対し、前記追加される「１」の位置が変更された検査行列Ｈ１を用いて、復号を施す復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、差集合巡回符号又はＬＤＰＣ−ＢＣ符号を用いた符号化器、符号化方法、及び復号方法に関する。
【背景技術】
【０００２】
近年、実現可能な回路規模で高い誤り訂正能力を発揮する誤り訂正符号として、低密度パリティ検査（ＬＤＰＣ：Low-Density Parity-Check）符号に注目が集まっている。ＬＤＰＣ符号は、誤り訂正能力が高く、かつ実装が容易なので、IEEE802.11nの高速無線ＬＡＮ（Local Area Network）システムやデジタル放送システムなどの誤り訂正符号化方式に採用されている。
【０００３】
ＬＤＰＣ符号は、低密度なパリティ検査行列Ｈで定義される誤り訂正符号である。また、ＬＤＰＣ符号は、検査行列Ｈの列数Ｎと等しいブロック長を持つブロック符号である。例えば、非特許文献１、非特許文献２、非特許文献３では、ランダム的なＬＤＰＣ符号、Ａｒｒａｙ  ＬＤＰＣ符号、ＱＣ−ＬＤＰＣ符号（ＱＣ:Quasi-Cyclic）が提案されている。
【０００４】
しかし、現在の通信システムの多くは、イーサネット（登録商標）のように、送信情報を、可変長のパケットやフレーム毎にまとめて伝送するという特徴がある。このようなシステムにブロック符号であるＬＤＰＣ符号を適用する場合、例えば、可変長なイーサネット（登録商標）のフレームに対して固定長のＬＤＰＣ符号のブロックをどのように対応させるかといった課題が生じる。IEEE802.11nでは、送信情報系列にパディング処理やパンクチャ処理を施すことで、送信情報系列の長さと、ＬＤＰＣ符号のブロック長の調節を行っているが、パディングやパンクチャによって、符号化率が変化したり、冗長な系列を送信することを避けることは困難である。
【０００５】
このようなブロック符号のＬＤＰＣ符号（以降、これをＬＤＰＣ−ＢＣ：Low-Density Parity-Check Block Codeと標記する）に対して、任意の長さの情報系列に対しての符号化・復号化が可能なＬＤＰＣ−ＣＣ（Low-Density Parity-Check ConvolutionalCode）の検討が行われている（例えば、非特許文献１、非特許文献２参照）。
【０００６】
ＬＤＰＣ−ＣＣは，低密度なパリティ検査行列により定義される畳み込み符号であり、例えば符号化率Ｒ＝１／２（＝ｂ／ｃ）のＬＤＰＣ−ＣＣのパリティ検査行列ＨＴ［０，ｎ］は、図２１で示される。ここで、ＨＴ［０，ｎ］の要素ｈ１（ｍ）（ｔ）は、０または１をとる。また、ｈ１（ｍ）（ｔ）以外の要素は全て０である。ＭはＬＤＰＣ−ＣＣにおけるメモリ長、ｎはＬＤＰＣ−ＣＣの符号語の長さを表す。図２１に示されるように、ＬＤＰＣ−ＣＣの検査行列は行列の対角項とその近辺の要素にのみに１が立っており、行列の左下および右上の要素はゼロであり、平行四辺形型の行列であるという特徴がある。
【０００７】
ここで，ｈ１（０）（ｔ）＝１，ｈ２（０）（ｔ）＝１であるとき、検査行列ＨＴ［０，ｎ］Ｔで定義されるＬＤＰＣ−ＣＣの符号化器は図２１で表される。図２２に示すように、ＬＤＰＣ−ＣＣの符号化器は、ビットレングスｃのシフトレジスタＭ＋１個とｍｏｄ２加算器で構成される。このため、ＬＤＰＣ−ＣＣの符号化器には、生成行列の乗算を行う回路や後退（前方）代入法に基づく演算を行うＬＤＰＣ−ＢＣの符号化器に比べ、非常に簡易な回路で実現することができるという特徴がある。また、図２２の符号化器は、畳み込み符号の符号化器であるため、情報系列を固定長のブロックに区切って符号化する必要はなく、任意の長さの情報系列を符号化することができる。
【０００８】
ところで、ＬＤＰＣ−ＣＣと同様な特徴をもつ符号として、検査行列のサイズが小さいＬＤＰＣ―ＢＣ又は差集合巡回符号をプロトグラフとし、当該プロトグラフを複数結合（接続）するために、検査行列に「１」を追加することで新しい検査行列を作成し、この新しい検査行列に基づき符号化及び復号を行う方法が考えられる。
【０００９】
この新しい検査行列において、プロトグラフをブロック長が小さいＬＤＰＣ―ＢＣ又は差集合巡回符号の検査行列で構成することにより、パケットサイズが小さいデータを送信する場合においても、余分なビットを送信する量を少なくすることができるため、データの伝送効率の面で有利であるという特長をもつ。
【非特許文献１】R. G. Gallager, “Low-density parity check codes,” IRE Trans. Inform. Theory, IT-8, pp-21-28, 1962.
【非特許文献２】D. J. C. Mackay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, vol.45, no.2, pp399-431, March 1999.
【非特許文献３】J. L. Fan, “Array codes as low-density parity-check codes,” proc. of 2nd Int. Symp. on Turbo Codes, pp.543-546, Sep. 2000.
【非特許文献４】Y. Kou, S. Lin, and M. P. C. Fossorier, “Low-density parity-check codes based on finite geometries: A rediscovery and new results,” IEEE Trans. Inform. Theory, vol.47, no.7, pp2711-2736, Nov. 2001.
【非特許文献５】A. J. Felstorom, and K. Sh. Zigangirov,“Time-Varying Periodic Convolutional Codes With Low-Density Parity-Check Matrix,”IEEE Transactions on Information Theory, Vol.45, No.6,pp2181-2191, September 1999.
【非特許文献６】R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja, and D. J. Costello Jr., “LDPC block and convolutional codes based on circulant matrices,” IEEE Trans. Inform. Theory, vol.50, no.12, pp.2966-2984, Dec. 2004.
【非特許文献７】G. Richter, M. Kaupper, and K. Sh. Zigangirov,“Irregular low-density parity-Check convolutional codes based on protographs,”Proceedingof IEEE ISIT 2006,pp1633-1637.
【非特許文献８】R. D. Gallager, “Low-Density Parity-Check Codes,” Cambridge, MA: MIT Press, 1963.
【非特許文献９】M. P. C. Fossorier, M. Mihaljevic, and H. Imai, “Reduced complexity iterative decoding of low density parity check codes based on belief propagation,” IEEE Trans. Commun., vol.47., no.5, pp.673-680, May 1999.
【非特許文献１０】J. Chen, A. Dholakia, E. Eleftheriou, M. P. C. Fossorier, and X.-Yu Hu, “Reduced-complexity decoding of LDPC codes,” IEEE Trans. Commun., vol.53., no.8, pp.1288-1299, Aug. 2005.
【非特許文献１１】和田山  正、“低密度パリティ検査符号とその復号方法”  トリケップス．
【非特許文献１２】江藤良純、金子敏信  監修、“誤り訂正符号とその応用”  オーム社．
【非特許文献１３】S. Lin, D. J. Jr., Costello, “Error control coding : Fundamentals and applications,” Prentice-Hall.
【非特許文献１４】今井秀樹、“符号理論”  社団法人  電子情報通信学会．
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、プロトグラフと異なる位置に「１」を追加することにより複数のプロトグラフを結合した検査行列を生成し、当該検査行列に基づいて符号化を行う符号化方法、及び復号方法については、十分な検討がなされておらず、特に、受信品質の改善に関する考察について、十分に議論がされているわけではない。
【００１１】
本発明は、かかる点を考慮してなされたものであり、差集合巡回符号又はＬＤＰＣ−ＢＣの検査行列をプロトグラフとして用い、プロトグラフと異なる位置に「１」を追加することにより複数のプロトグラフを結合した検査行列に基づいて符号化、及び復号を施す場合において、良好な受信品質を得ることができる符号化器、符号化方法、及び復号方法を提供する。
【課題を解決するための手段】
【００１２】
本発明の符号化器の一つの態様は、差集合巡回符号の検査行列がプロトグラフとして用いられ、かつ、当該プロトグラフが対角線上に配置された検査行列に基づいて符号化を施す符号化器であって、入力データに対し差集合巡回符号化を施し、組織化ビット及びパリティビットから成る符号語を生成する差集合巡回符号化手段と、過去の前記符号語のうち、前記プロトグラフを結合した場合に、前記検査行列の検査式に含まれる過去の前記符号語を保持する記憶手段と、前記記憶手段に保持された過去の前記符号語を用いて、前記差集合巡回符号化手段から出力される前記パリティビットを修正するパリティ修正部と、を具備する構成を採る。
【００１３】
本発明の符号化器の一つの態様は、前記記憶手段は、過去の前記組織化ビットを記憶し、前記パリティ修正手段は、過去の前記組織化ビットを用いて、前記差集合巡回符号化手段から出力される前記パリティビットを修正する構成を採る。
【００１４】
本発明の符号化器の一つの態様は、前記記憶手段は、過去の前記パリティビットを記憶し、前記パリティ修正手段は、過去の前記パリティビットを用いて、前記差集合巡回符号化手段から出力される前記パリティビットを修正する構成を採る。
【００１５】
本発明の符号化方法の一つの態様は、差集合巡回符号の検査行列がプロトグラフとして用いられ、かつ、当該プロトグラフが対角線上に配置された検査行列を用いて符号化を施す符号化方法であって、入力データに対し差集合巡回符号化を施し、組織化ビット及びパリティビットから成る符号語を生成するステップと、過去の前記符号語のうち、前記プロトグラフを結合した場合に、前記検査行列の検査式に含まれる過去の前記符号語を保持するステップ、保持された過去の前記符号語を用いて、生成される前記パリティビットを修正するステップと、を有するようにした。
【００１６】
本発明の復号方法の一つの態様は、差集合巡回符号の検査行列Ｈｏｒｇがプロトグラフとして用いられ、かつ、当該プロトグラフが対角線上に配置され、かつ、複数の当該プロトグラフを結合するために、当該プロトグラフと異なる位置に「１」が追加された、検査行列Ｈに基づいて符号化された符号語を復号する復号方法であって、当該プロトグラフと異なる位置に追加された「１」により前記検査行列Ｈの検査式に含まれる過去の符号語が、他の過去の符号語に置き換わるように、前記検査行列Ｈに対し、前記追加される「１」の位置が変更された検査行列Ｈ１を用いて、復号を施すようにした。
【発明の効果】
【００１７】
本発明によれば、ブロック長をパケットサイズに合わせた差集合巡回符号又はＬＤＰＣ−ＢＣの検査行列をプロトグラフとして、余分なビットを送信する量を少なくし、データ伝送効率の劣化を回避しつつ、良好な受信品質を得ることができる。
【発明を実施するための最良の形態】
【００１８】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００１９】
先ず、実施の形態の具体的な構成及び動作を説明する前に、ＬＤＰＣ−ＢＣ符号及び差集合巡回符号の一般的な符号化方法及び復号方法について説明する。
【００２０】
（符号化方法）
ＬＤＰＣ−ＢＣ及び差集合巡回符号では、生成行列Ｇを情報ベクトルｎに乗ずることにより、符号化データ（符号語）を得る。つまり、符号化データ（符号語）ｃは、ｃ＝ｎ×Ｇと表すことができる。ここで、生成行列Ｇは、あらかじめ設計された検査行列Ｈに対応して求められたものである。具体的には、生成行列Ｇは、Ｇ×ＨＴ＝０を満たす行列である。
【００２１】
（復号方法）
ＬＤＰＣ―ＢＣでは、非特許文献８〜非特許文献１０に示されているようなＢＰ（Belief Propagation）復号、ＢＰ復号を近似したmin-sum復号、offset BP復号、Normalized BP復号、shuffled BP復号など行った場合、優れた受信品質を得ることができる。
【００２２】
ＬＤＰＣ−ＢＣでは、符号長より少ない数の検査式が存在するのに対し、差集合巡回符号の検査行列は、符号長に対し符号長と同数の検査式が存在する。このため、ＬＤＰＣ符号と同様に、差集合巡回符号においても、非特許文献８〜非特許文献１０に示されているようなＢＰ（Belief Propagation）復号、ＢＰ復号を近似したmin-sum復号、offset BP復号、Normalized BP復号、shuffled BP復号など行った場合、優れた受信品質を得ることができることになる。
【００２３】
以下では、復号側での復号アルゴリズムの一例として、sum-product復号アルゴリズムについて説明する。sum-product復号は、ＢＰ復号の一種である。
【００２４】
以下の説明では、２元（Ｍ×Ｎ）行列Ｈ＝｛Ｈｍｎ｝を、復号対象であるＬＤＰＣ符号の検査行列とする。集合［１，Ｎ］＝｛１，２，・・・，Ｎ｝の部分集合Ａ（ｍ），Ｂ（ｎ）を次式のように定義する。
【数１】
2009100234.tif 000003
【数２】
2009100234.tif 000004
なお、Ａ（ｍ）は検査行列Ｈのｍ行目において“１”である列インデックスの集合を意味し、Ｂ（ｎ）は検査行列Ｈのｎ行目において“１”である行インデックスの集合を意味する。
【００２５】
・Ｓｔｅｐ  Ａ・１（初期化）：
Ｈｍｎ＝１を満たす全ての組（ｍ，ｎ）に対して、事前値対数比βｍｎ＝０と設定する。また、ループ変数（反復回数）ｌｓｕｍ＝１と設定し、ループ最大回数をｌｓｕｍ，ｍａｘと設定する。
【００２６】
・Ｓｔｅｐ  Ａ・２（行処理）：
ｍ＝１，２，・・・，Ｍの順にＨｍｎ＝１を満たす全ての組（ｍ，ｎ）に対して、次の更新式を用いて外部値対数比αｍｎを更新する。
【数３】
2009100234.tif 000005
【数４】
2009100234.tif 000006
【数５】
2009100234.tif 000007
なお、ｆはＧａｌｌａｇｅｒの関数であり、λｎはビット毎の対数尤度である。
【００２７】
・Ｓｔｅｐ  Ａ・３（列処理）：
ｎ＝１，２，・・・，Ｎの順にＨｍｎ＝１を満たす全ての組（ｍ，ｎ）に対して、次の更新式を用いて外部値対数比βｍｎを更新する。
【数６】
2009100234.tif 000008
【００２８】
・Ｓｔｅｐ  Ａ・４（対数尤度比の計算）：
ｎ∈［１，Ｎ］について対数尤度比Ｌｎを、次式のように求める。
【数７】
2009100234.tif 000009
【００２９】
・Ｓｔｅｐ  Ａ・５（反復回数のカウント）：
もしｌｓｕｍ＜ｌｓｕｍ，ｍａｘならばｌｓｕｍをインクリメントして、ｓｔｅｐ  Ａ・２に戻る。一方、ｌｓｕｍ＝ｌｓｕｍ，ｍａｘの場合、式（８）に示すように符号語ｗを推定し、sum-product復号を終了する。
【数８】
2009100234.tif 000010
【００３０】
ところで、送信系列（符号化後のデータ）をｕ＝（ｎ１，ｎ２，ｎ３，ｎ４，…）とし、情報系列のベクトルｉ＝（ｉ１,ｉ２,ｉ３,ｉ４,…)とすると、式（９）が成立する。
【数９】
2009100234.tif 000011
なお、式（９）において、Ｇは生成行列であり、検査行列Ｈと生成行列Ｇとの間には、式（１０）の関係式が成立する。
【数１０】
2009100234.tif 000012
このように、式（９）,（１０）を利用することで、ＬＤＰＣ−ＢＣに対し、sum-product復号を用いて、送信系列を求めることができる。
【００３１】
図１は、復号器として、sum-product復号を用いたときの構成の一例を示す図である。図１の復号器１００において、対数尤度比記憶部１０３は、対数尤度比信号１０１、タイミング信号１０２を入力とし、タイミング信号１０２に基づいてデータ区間の対数尤度比を記憶する。そして、数尤度比記憶部１０３は、記憶した対数尤度比を信号１０４として行処理演算部１０５に出力する。
【００３２】
行処理演算部１０５は、対数尤度比信号１０４、列処理後の信号１１２を入力とし、検査行列Ｈに「１」が存在する位置において、上述のＳｔｅｐ  Ａ・２（行処理）の演算を行う。復号器は反復復号を行っているので、行処理演算部１０５は、１回目の復号時には、対数尤度比信号１０４を用いて行処理を行い（上述のＳｔｅｐ  Ａ・１の処理に相当する）、２回目の復号時には、列処理後の信号１１２を用いて行処理を行う。そして、行処理演算部１０５は、行処理後の信号１０６を行処理後データ記憶部１０７に出力する。
【００３３】
行処理後データ記憶部１０７は、行処理後の信号１０６を入力とし、すべての行処理後の値（信号）を記憶する。そして、行処理後データ記憶部１０７は、行処理後の信号１０８を列処理演算部１０９及び対数尤度比演算部１１５に出力する。
【００３４】
列処理演算部１０９は、行処理後の信号１０８及び制御信号１１４を入力とし、制御信号１１４から最後の反復演算でないことを確認し、検査行列Ｈに「１」が存在する位置において、上述のＳｔｅｐ  Ａ・３（列処理）の演算を行う。そして、列処理演算部１０９は、列処理後の信号１１０を列処理後データ記憶部１１１に出力する。
【００３５】
列処理後データ記憶部１１１は、列処理後の信号１１０を入力とし、すべての列処理後の値（信号）を記憶する。そして、列処理後データ記憶部１１１は、列処理後の信号１１２を行処理演算部１０５に出力する。
【００３６】
制御部１１３は、タイミング信号１０２を入力とし、反復回数をカウントし、反復回数を制御信号１１４として列処理演算部１０９及び対数尤度比演算部１１５に出力する。
【００３７】
対数尤度比演算部１１５は、行処理後の信号１０８、制御信号１１４を入力とし、制御信号１１４に基づいて最後の反復演算であると判断した場合、検査行列Ｈに「１」が存在する位置に対して、Ｓｔｅｐ  Ａ・４（対数尤度比の計算）の演算を施し、対数尤度比信号１１６を得る。そして、対数尤度比演算部１１５は、対数尤度比信号１１６を判定部１１７に出力する。
【００３８】
判定部１１７は、対数尤度比信号１１６を入力とし、符号語を推定し、推定ビット１１８を出力する。
【００３９】
ここでは、ＢＰ復号として、sum-product復号について述べたが、ＢＰ復号を近似したmin-sum復号、offset ＢＰ復号、Normalized ＢＰ復号、shuffled ＢＰ復号などを用いることでも、ＬＤＰＣ−ＢＣに対し復号を行うことができる。
【００４０】
一般的なＬＤＰＣ符号では、検査式の数は符号長の数より少ないのに対し、差集合巡回符号の検査行列は、後述するように、符号長と同数の検査式が存在する。このため、差集合巡回符号を用いた場合においても、ＬＤＰＣ符号と同様に、復号側では、差集合巡回符号の検査行列Ｈｏｒｇを用い、非特許文献８〜非特許文献１０に示されているようなＢＰ（Belief Propagation）復号、ＢＰ復号を近似したmin-sum復号、offset BP復号、Normalized BP復号、shuffled BP復号など行った場合、優れた受信品質を得ることができる。
【００４１】
本発明は、差集合巡回符号の検査行列又はＬＤＰＣ−ＢＣの検査行列をプロトグラフとし、プロトグラフと異なる位置に「１」を追加することにより、複数のプロトグラフを結合した検査行列に基づいて符号化を施し、上記ＢＰ復号アルゴリズム等により復号を行う場合において、検査行列を工夫することで、符号化側では、比較的単純な方法で符号化を行うことができるとともに、復号側での受信品質を改善するものである。
【００４２】
（実施の形態１）
本実施の形態は、差集合巡回符号の検査行列をプロトグラフとする符号化方法、復号方法、及び符号化器について詳しく説明する。なお、以下では、差集合巡回符号として、（２１，１１）差集合巡回符号を用いる場合を例に説明する。
【００４３】
（検査行列の構成）
図２に、（２１，１１）差集合巡回符号の検査行列Ｈｏｒｇの一例を示す。図２に示す(２１，１１)差集合巡回符号の検査行列Ｈｏｒｇは、１行目の（１，０，０，０，０，０，０，０，０，０，１，０，０，１，１，０，０，０，０，１，０）を右に巡回置換して得られる。
【００４４】
（２１，１１）差集合巡回符号の検査行列Ｈｏｒｇにより定義される符号語（送信ベクトル）をｗＴ＝（ｘ，ｐ）とする。ここで、ｘは、１１ビットのデータ（ｘ０，ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）を示し、ｐは、１０ビットのパリティビット（ｐ０，ｐ１，ｐ２，ｐ３，ｐ４，ｐ５，ｐ６，ｐ７，ｐ８，ｐ９）を示す。このとき、式（１１）であらわされる送信ベクトルｗＴに対し、式（１２）が成立することから、式（１２）を展開して、式（１３−１）〜（１３−２１）を得る。
【数１１】
2009100234.tif 000013
【数１２】
2009100234.tif 000014
【数１３】
2009100234.tif 000015
式（１３−１）〜（１３−２１）において、「＾」は排他的論理和を示す。
【００４５】
このように、(２１，１１）差集合巡回符号の検査行列Ｈｏｒｇでは、符号長２１に対し２１個の検査式（式（１３−１）〜（１３−２１））が存在する。式（１３−１）〜（１３−２１）から、１０ビットのパリティビットは、式（１４−１）〜（１４−１０）にようにあらわされる。
【数１４】
2009100234.tif 000016
【００４６】
このように、図２に示す（２１，１１）差集合巡回符号の検査行列Ｈｏｒｇを用いる場合、１１ビットのデータ（ｘ０，ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）から、１０ビットのパリティビット（ｐ０，ｐ１，ｐ２，ｐ３，ｐ４，ｐ５，ｐ６，ｐ７，ｐ８，ｐ９）が作成されることになる。本実施の形態では、上述のように定義される（２１，１１）差集合巡回符号の検査行列Ｈｏｒｇをプロトグラフとする検査行列Ｈについて検討する。
【００４７】
図３は、本実施の形態の検査行列Ｈの構成の概念図の一例を示している。本提案の検査行列Ｈは、図２の検査行列Ｈｏｒｇを対角線２０１上に配置し、対角線２０１の上三角の要素は「０」とするものとする。送信ベクトルｗＴを式（１５）のようにあらわすとき、検査行列Ｈと送信ベクトルｗＴの間には式（１６）が成立する。
【数１５】
2009100234.tif 000017
【数１６】
2009100234.tif 000018
なお、式（１５）において、ｘｉ，ｊはデータであり、ｑｉ，ｊはパリティである。
【００４８】
図４は、図２に示した（２１，１１）差集合巡回符号の検査行列Ｈｏｒｇをプロトグラフとした場合の検査行列Ｈの一例を示している。検査行列Ｈを、複数のプロトグラフが結合（接続）した符号とするために、プロトグラフ３００を対角線上に配置し、さらに、プロトグラフ３００とは異なる位置に検査行列「１」を追加する。プロトグラフとは異なる位置に「１」が配置されることにより、検査行列の検査式に過去の符号語が含まれるようになるので、復号側（受信側）で過去の尤度を結合することができるようになる。
【００４９】
図４には、（２１，１１）差集合巡回符号の検査行列Ｈｏｒｇのプロトグラフ３００を結合（接続）するために、位置３０１及び位置３０３に「１」が追加された例が示されている。
【００５０】
位置３０１及び位置３０３に「１」が追加されたことにより、検査式は以下の式（１７−１）〜（１７−２１）のようになる。
【数１７】
2009100234.tif 000019
【００５１】
上記検査式（１７−１）〜（１７−２１）と、図２に示した（２１，１１）差集合巡回符号の検査行列に対応する検査式（１３−１）〜（１３−２１）との比較から、位置３０１に「１」を追加したことにより、ｑ１，７は、式（１８）のように表される。
【数１８】
2009100234.tif 000020
ここで、ｐ１，７は、（２１，１１）差集合巡回符号において、式（１４−８）により求められるパリティである。
【００５２】
このように、位置３０１に「１」を追加したことにより、過去（時点０（ｉ＝０））の符号語ｘ０，０が、時点１（ｉ＝１）のパリティｑ１，７を求める際に関連することになる。
【００５３】
同様に、位置３０３に追加した「１」により、ｑ２，７は、式（１９）のように表される。
【数１９】
2009100234.tif 000021
ここで、ｐ２，７は、（２１，１１）差集合巡回符号において、式（１４−８）により求められるパリティである。このように、位置３０３に「１」を追加したことにより、過去（時点１（ｉ＝１））の符号語ｘ１，０が、時点２（ｉ＝２）のパリティｑ２，７を求める際に関連することになる。
【００５４】
式（１８），（１９）に示すように、位置３０１，３０３に追加した「１」により、（２１，１１）差集合巡回符号のパリティｐ１，７，ｐ２，７は、パリティｑ１，７，ｑ２，７に書き換えられる。
【００５５】
一方、検査式（１７−９）以外では、ｑ１，ｊ＝ｐ１，ｊ（ｊ≠７）、ｑ２，ｊ＝ｐ２，ｊ（ｊ≠７）のままであるため、図４の検査行３０５，３０６に示す、ｑ１，ｊ，ｑ２，ｊ含む他の検査式（１７−５），（１７−６），（１７−１９），（１７−２１）が満たされなくなり、検査行列Ｈが、式（１６）を満たさなくなってしまう。
【００５６】
ここで、検査行列Ｈが、式（１６）を満たさなくなってしまうのは、位置３０１に追加された「１」によって、式（１８）に示すように、パリティｐ１，７が書き換えられるのに対し、パリティｐ１，７を含む他の検査行３０５（式（７−５），（７−６），（７−１９），（７−２１））はそのままで書き換えられていないからである。
【００５７】
そこで、本実施の形態の検査行列Ｈでは、プロトグラフを結合するために追加された「１」により書き換えられるパリティｑｉ，７を含む他の検査行３０５，３０６において、「１」を追加した列と同じ列に「１」を追加するようにした。
【００５８】
つまり、プロトグラフを結合するために「１」を追加するにあたり、まず、ｉ番目の符号語を求める際に関連させたい（ｉ−１）番目の符号語をｘｉ，０とし、さらに、当該符号語ｘｉ，０により修正したいパリティビットをパリティｐｉ，７とした場合、当該パリティｐｉ，７を含む検査行３０５，３０６において、符号語ｘｉ，０に対応する列に「１」を追加する。
【００５９】
このようにすることで、プロトグラフを結合するために当該プロトグラフと異なる位置に「１」を追加することにより、ｉ番目のパリティを求める際に関連することになった過去の符号語ｘｉ，０が、パリティｑｉ，７を含む全ての検査式に含まれるようになるので、式（１６）を満たすようになる。
【００６０】
図５に、図４の検査行列に基づき作成した本実施の形態の検査行列の一例を示す。図５に示す例では、パリティｑｉ，７を含む検査式において、プロトグラフを結合するために追加された「１」の列と同じ列、つまり、図５において位置４０１に「１」を追加する。このようにすることで、検査式（７−５），（７−６），（７−１９），（７−２１）が、それぞれ、検査式（２０−１），（２０−２），（２０−３），（２０−４）のように書き換えられ、検査行３０５が「０」を満たすようになる。
【数２０】
2009100234.tif 000022
【００６１】
同様に、図５において位置４０３に“１”を追加すると、検査行３０６が「０」を満たすようになり、検査行列Ｈが、式（１６）を満たすようになる。これにより、図５の検査行列Ｈを用いて、非特許文献８〜非特許文献１１に示されているようなＢＰ（Belief Propagation）復号、ＢＰ復号を近似したmin-sum復号、offset BP復号、Normalized BP復号、shuffled BP復号など行うことができるようになる。
【００６２】
（符号化器の構成）
図５において、プロトグラフ４０５をＨｍ、プロトグラフ３００をＨｏｒｇとあらわすと、図５の検査行列Ｈは、式（２１）のようにあらわすことができる。
【数２１】
2009100234.tif 000023
【００６３】
以下では、式（２１）のようにあらわされる検査行列Ｈに基づく符号化器の構成例について説明する。
【００６４】
図６は、図４の検査行列Ｈに基づき符号化を施す符号化器の構成の一例を示している。図５において、符号化器５００は、差集合巡回符号化部５１０、記憶部５２０、及びパリティ修正部５３０を備えて構成される。
【００６５】
差集合巡回符号化部５１０は、データ５０１（ｘｉ，０，ｘｉ，１，ｘｉ，２，ｘｉ，３，ｘｉ，４，ｘｉ，５，ｘｉ，６，ｘｉ，７，ｘｉ，８，ｘｉ，９，ｘｉ，１０）を入力とし、式（１４−１）〜（１４−２１）を用いて、パリティ５０３を生成する。差集合巡回符号化部５１０は、生成したパリティ５０３（ｐｉ，０，ｐｉ，１，ｐｉ，２，ｐｉ，３，ｐｉ，４，ｐｉ，５，ｐｉ，６，ｐｉ，７，ｐｉ，８，ｐｉ，９）をパリティ修正部５３０に出力する。
【００６６】
記憶部５２０は、データ５０１を入力とし、プロトグラフとは異なる位置に「１」を追加した結果、検査式に含まれるｘｉ−１，０を少なくとも記憶する。そして、記憶部５２０は、パリティ修正部５３０がｉ番目の符号化を行う際に、記憶している（ｉ−１）番目のデータｘｉ−１，０（５０５）をパリティ修正部５３０に出力する。
【００６７】
パリティ修正部５３０は、パリティ５０３（ｐｉ，０，ｐｉ，１，ｐｉ，２，ｐｉ，３，ｐｉ，４，ｐｉ，５，ｐｉ，６，ｐｉ，７，ｐｉ，８，ｐｉ，９）、及び、（ｉ−１）番目のデータ５０５（ｘｉ−１，０）を入力する。そして、パリティ修正部５３０は、式（２２）を用いてパリティ５０３を修正し、修正後のパリティ５０６（ｑｉ，０，ｑｉ，１，ｑｉ，２，ｑｉ，３，ｑｉ，４，ｑｉ，５，ｑｉ，６，ｑｉ，７，ｑｉ，８，ｑｉ，９）を符号化器５００の出力結果として出力する。
【数２２】
2009100234.tif 000024
【００６８】
このように、符号化側では、式（２２）を用いて、差集合巡回符号化部５１０から出力されるパリティｐｉ，７を修正するだけで、式（１６）を満たす符号化を施すことができるので、簡易な構成で符号化器５００を構成することができる。
【００６９】
このとき、差集合巡回符号化部５１０が、パケットサイズに合わせたブロック長で符号化を行うようにすれば、余分なビットを送信する量を少なくすることができ、データ伝送効率の劣化を回避することができる。
【００７０】
以上のように、本実施の形態によれば、差集合巡回符号の検査行列Ｈｏｒｇがプロトグラフとして用いられ、かつ、当該プロトグラフが対角線上に配置された検査行列Ｈに基づいて符号化を施す場合において、差集合巡回符号化部５１０は、検査行列Ｈｏｒｇに基づいて入力データに対し差集合巡回符号化を施し、記憶部５２０は、当該プロトグラフと異なる位置に「１」を追加することにより、複数のプロトグラフを結合した結果、検査行列Ｈの検査式に含まれる過去の符号語を保持し、パリティ修正部５３０は、記憶部５２０に保持された過去の符号語を用いて、差集合巡回符号化部５１０から出力されるパリティビットを修正するようにした。
【００７１】
符号化側では、差集合巡回符号の検査行列Ｈｏｒｇがプロトグラフとして用いられ、かつ、プロトグラフが対角線上に配置され、かつ、複数のプロトグラフを結合するために、プロトグラフと異なる位置に「１」が追加された検査行列Ｈを用いて符号化を施す場合に、予め、ｉ番目の符号語を生成するにあたり関連する（ｉ−１）番目の過去の符号語と、過去の符号語を用いて修正するｉ番目のパリティビットを選択しておき、入力データに対し差集合巡回符号化を施し、組織化ビット及びパリティビットから成る符号語を生成し、選択したｉ番目のパリティビットを選択した（ｉ−１）番目の過去の符号語で修正するようにした。
【００７２】
このようにすることで、過去の符号語が検査式に含められ、プロトグラフが結合される。過去の符号語を検査式に含めることにより、プロトグラフ同士の確率伝播の関係から、フェージングの影響による受信電界強度の低下の影響を軽減することができるので、受信品質を改善することができる。また、検査式（１６）を満たす検査行列Ｈに基づいた符号化を施すので、復号側では、ＢＰ復号アルゴリズムを用いて、過去の尤度を結合しながら復号することができ、優れた復号特性を得ることができる。
【００７３】
以上の説明では、プロトグラフを結合（接続）するために関連する符号語が１ビット（ｘｉ−１，０）の場合について説明したが、これに限ったものではなく、２ビット以上の場合についても同様に実施することができる。以下、プロトグラフを結合するために関連する符号語が２ビットの場合の符号化、及び復号方法の一例について説明する。
【００７４】
図７は、プロトグラフを結合（接続）するために関連する符号語が２ビットの場合の検査行列Ｈの構成の一例を示している。図７において、図４及び図５と同一の部分には同一符号を付して説明を省略する。図７は、図５に対し、さらに、位置６０１に「１」を追加することで、過去の符号語ｘｉ−１，０に加え、過去の符号語ｘｉ−１，２を検査式にさらに含めるようにした場合の例である。
【００７５】
図５の位置４０１に「１」を追加したように、ｑｉ，９を含む検査式に対応する位置６０１に「１」を追加することで、検査行列Ｈが式（１６）を満たすようになる。
【００７６】
符号化器の構成は図６と同様の構成を採る。ただし、記憶部５２０は、検査式に関連するｘｉ−１，０及びｘｉ−２，２を少なくとも記憶し、ｘｉ−１，０及びｘｉ−２，２をパリティ修正部５３０に出力する。パリティ修正部５３０は、式（２３−１）〜（２３−３）によりパリティビットを求める。
【数２３】
2009100234.tif 000025
【００７７】
このように、検査行列の位置４０１及び位置６０１に「１」を追加することにより、図７の検査行列Ｈは、式（１６）を満たすようになる。したがって、復号側では、図７のように「１」が追加された検査行列Ｈを用いることにより、非特許文献８〜非特許文献１０に示されているようなＢＰ復号、ＢＰ復号を近似したmin-sum復号、offset BP復号、Normalized BP復号、shuffled BP復号など行うことができる。
【００７８】
図７において、プロトグラフ６０２をＨｎとすると、図７の検査行列は、式（２４）のようにあらわすことができる。
【数２４】
2009100234.tif 000026
【００７９】
関連する過去の符号語を３ビット以上とする場合についても、上述と同様の方法で、検査行列を生成すれば、同様に実施することができる。すなわち、符号化側では、プロトグラフを結合するために関連させたい過去の符号語と、当該過去の符号語により修正したいパリティビットを決定し、パリティビットを過去の符号語によって修正するようにすればよく、過去の符号語と当該過去の符号語を用いて修正するパリティビットとの組み合わせが複数あってもよい。その際には、式（２４）に示される検査行列Ｈの下三角行列の０行列が、０行列でない行列（ＨｎやＨｍに相当）にさらに書き換えられ、例えば、検査行列Ｈは、式（２５−１），（２５−２）のように表される。式（２５−１），（２５−２）において、Ｈｐ，Ｈｑは、式（２４）に示される検査行列Ｈの下三角行列の０行列が、０行列でない行列に書き換えられた行列に相当する。
【数２５】
2009100234.tif 000027
【００８０】
なお、本実施の形態では、（２１，１１）差集合巡回符号の検査行列をプロトグラフとする場合を例に説明したが、他の差集合巡回符号を用いても同様に実施することができる。他の差集合巡回符号については、非特許文献１２及び非特許文献１３に記載されている。また、差集合巡回符号以外の符号、例えば、ＬＤＰＣ―ＢＣ、ＢＣＨ符号等の場合においても同様に実施することができる。ＬＤＰＣ−ＢＣの場合については、実施の形態３及び実施の形態４において説明する。
【００８１】
また、本実施の形態では、「１」を追加する位置をデータ（ｘｉ−１，０）に関連する位置（例えば、位置４０１）とする場合について説明したが、これに限ったものではなく、パリティに関連する位置に「１」を追加してもよい。その例については、実施の形態５で説明する。
【００８２】
（実施の形態２）
本実施の形態では、実施の形態１における図５の検査行列Ｈの変形方法と変形による利点について詳しく説明する。
【００８３】
図５の検査行列Ｈは、式（２１）に示すように（２１，１１）差集合巡回符号の検査行列Ｈｏｒｇをプロトグラフ３００として対角線上に配置した行列である。ところで、差集合巡回符号は、直交符号であるため、非特許文献１４に記載されているパンクチャを行った場合においても受信品質の劣化を抑えることができ、かつ、パンクチャ方法に制限を設けずとも、受信品質の劣化を抑えることができるので、非常に簡単にパンクチャするビットを選択できるという利点を持っている。
【００８４】
しかし、図５に示した検査行列Ｈでは、プロトグラフ３００を結合（接続）するために、検査行列Ｈの位置４０１及び位置４０３に「１」を追加したことにより、検査行列Ｈは、ｘｉ−１，０の存在により直交性を失う。そのため、非特許文献１４に記載されているパンクチャ方法に制限を与える必要がある。この場合、パンクチャによる受信品質の劣化を抑えるためには、検査行列Ｈに「１」を追加したことにより、検査式に関連することになった符号語ｘｉ−０がパンクチャされないようにし、符号語ｘｉ−０以外のビット（ｘｉ，１，ｘｉ，２，ｘｉ，３，ｘｉ，４，ｘｉ，５，ｘｉ，６，ｘｉ，７，ｘｉ，８，ｘｉ，９，ｘｉ，１０，ｑｉ，０，ｑｉ，１，ｑｉ，２，ｑｉ，３，ｑｉ，４，ｑｉ，５，ｑｉ，６，ｑｉ，７，ｑｉ，８，ｑｉ，９）を送信しないビット（間引くビット）として選択するようにするとよい。しかし、「１」を挿入する数が増え、関連する符号語数が増えるにしたがい、パンクチャする方法が限られる。また、関連する符号語がパンクチャされる場合には、受信品質の劣化を招くことになる。
【００８５】
また、一般に、タナーグラフを描いた際、長さ４のループ（ループ：あるノードから始まりそのノードで終わる周回路（周回するパス））が存在する場合、ＢＰ復号を行うと受信品質が劣化するという問題がある（非特許文献１１参照）。
【００８６】
図５の検査行列では、位置４０１に追加した「１」により、位置４０１と位置４０２との間に長さ４のループが形成される。また、位置４０３に追加した「１」により、位置４０３と位置４０４との間に長さ４のループが形成される。このため、図５の検査行列Ｈを用いた場合にＢＰ復号を行うと受信品質が劣化してしまう。
【００８７】
そこで、本実施の形態では、図５に示した検査行列Ｈと等価の検査行列であり、かつ、パンクチャ方法に関わらず受信品質の劣化を受けにくい検査行列の生成方法について詳しく説明する。以下では、図５の検査行列Ｈを図８のような検査行列Ｈ１に変更する方法を提案する。
【００８８】
図８において、プロトグラフ３００は、（２１，１１）差集合巡回符号の検査行列であり、プロトグラフ３００において、ｘ０，０に関連する検査行７００の間には、式（２６−１）〜（２６−５）に示す関係式が成立する。
【数２６】
2009100234.tif 000028
【００８９】
したがって、式（２６−１）〜（２６−５）から、ｘ０，０は、式（２７−１）〜（２７−５）のようにあらわすことができる。
【数２７】
2009100234.tif 000029
【００９０】
同様に、検査行列Ｈの対角線上のプロトグラフ３００においても、一般的に、以下の関係式（２８−１）〜（２８−５）が成立する。
【数２８】
2009100234.tif 000030
【００９１】
本実施の形態では、上記式（２８−１）〜（２８−５）の関係式を利用して、図５のプロトグラフ４０５を、図８のプロトグラフ７０３のように書き換えるようにした。具体的には、図５の位置４０１に追加された「１」により、ｘｉ，０が含まれるようになった検査式において、ｘｉ，０を、式（２８−１）〜（２８−５）を用いて、ｘｉ，０以外の符号語で置き換えるようにした。
【００９２】
例えば、図８において、検査行７０５は、式（２８−１）を用いて置き換えられている。同様に、検査行７０６，７０７，７０８，７０９は、それぞれ、式（２８−２）,（２８−３）,（２８−４）,（２８−５）を用いて置き換えられている。
【００９３】
同様に、図５の位置４０３に追加された「１」により、ｘｉ，０が含まれるようになった検査式において、ｘｉ，０を、式（２８−１）〜（２８−５）を用いて、ｘｉ，０以外の符号語で置き換えるようにした。図８において、検査行７０２は、式（２８−１）〜（２８−５）を用いて置き換えられた後の検査式である。
【００９４】
図８の検査行７０２から分かるように、式（２８−１）〜（２８−５）を用いて、ｘｉ，０を含む検査式を置き換えることにより、検査行列Ｈ１の直交性が確保されるようになる。この結果、パンクチャの方法に特別な制限を設けることなく、パンクチャを施すことができるようになる。
【００９５】
また、図８の検査行列Ｈ１には、長さ４のループが含まれなくなるようになるので、図５の検査行列Ｈを用いる場合に比し、受信品質を改善することができる。
【００９６】
図８において、プロトグラフ７０３をＨｎ、プロトグラフ３００をＨｏｒｇとすると、図７の検査行列Ｈ１は、式（２９）のようにあらわすことができる。
【数２９】
2009100234.tif 000031
【００９７】
式（２９）から分かるように、差集合巡回符号の検査行列Ｈｏｒｇが、検査行列Ｈｎにより結合されることになる。式（２９）の検査行列Ｈ１は、式（２１）の検査行列Ｈと等価であるため、本実施の検査行列Ｈ１に基づく符号化器の構成は、実施の形態１と同様の構成を採ることができる。
【００９８】
復号側では、図５の検査行列Ｈに代えて、図８の検査行列Ｈ１を用いて復号を施す。検査行列Ｈと等価であり、かつ、直交性が確保された検査行列Ｈ１を用いて復号することができるので、符号化側では、パンクチャの方法に制限を設けることなく、パンクチャを施すことができ、パンクチャ方法による受信品質の劣化を抑えることができる。
【００９９】
また、図８の検査行列Ｈ１には、長さ４のループが含まれないので、図５の検査行列Ｈを用いて復号を施す場合に比べ、受信品質を改善することができる。
【０１００】
以上のように、本実施の形態によれば、差集合巡回符号の検査行列Ｈｏｒｇがプロトグラフとして用いられ、かつ、当該プロトグラフが対角線上に配置され、かつ、複数の当該プロトグラフを結合するために、当該プロトグラフと異なる位置に「１」が追加された、検査行列Ｈに基づいて符号化された符号語を復号する場合に、当該プロトグラフと異なる位置に追加された「１」により検査行列Ｈの検査式に含まれる過去の符号語ｘｉ，０が、他の過去の符号語に置き換わるように、検査行列Ｈに対し、追加される「１」の位置が変更された検査行列Ｈ１を用いて復号を施すようにした。
【０１０１】
検査行列Ｈ１は、検査行列Ｈと等価であるため、実施の形態１と同様にＢＰ復号できるともに、検査行列Ｈ１は、直交性を確保しているので、符号化側におけるパンクチャ方法に特別な制限を設ける必要がなくなる。加えて、検査行列Ｈ１には、長さ４のループが含まれなくなるので、受信品質を改善することができるようになる。
【０１０２】
なお、本実施の形態では、プロトグラフを結合（接続）するために関連する符号語が１ビットの場合の検査行列Ｈと等価な検査行列Ｈ１を作成する方法について述べたが、これに限ったものではなく、プロトグラフを結合するために関連する符号語が２ビット以上の場合についても同様に等価な検査行列を作成することができる。また、本実施の形態では、（２１，１１）差集合巡回符号を例に説明したが、他の差集合巡回符号を用いても同様に、実施することができる。他の差集合巡回符号については、非特許文献１２及び非特許文献１３に記載されている。
【０１０３】
（実施の形態３）
本実施の形態では、差集合巡回符号の検査行列に代え、ＬＤＰＣ−ＢＣの検査行列をプロトグラフとする符号化方法、復号方法、及び符号化器について説明する。
【０１０４】
（検査行列の構成）
図９に、ＬＤＰＣ―ＢＣの検査行列Ｈｏｒｇの一例を示す。図９の検査行列により定義される符号語（送信ベクトル）をｗＴ＝（ｘ，ｐ）とする。ここで、ｘは、１６ビットのデータ（ｘ０，ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０，ｘ１１，ｘ１２，ｘ１３，ｘ１４，ｘ１５）であり、ｐは、１２ビットのパリティビット（ｐ０，ｐ１，ｐ２，ｐ３，ｐ４，ｐ５，ｐ６，ｐ７，ｐ８，ｐ９，ｐ１０，ｐ１１）を示す。このとき、式（３０）であらわされる送信ベクトルｗＴに対し、式（３１）が成立することから、式（３１）を展開して、式（３２−１）〜（３２−１２）を得る。
【数３０】
2009100234.tif 000032
【数３１】
2009100234.tif 000033
【数３２】
2009100234.tif 000034
式（３２−１）〜（３２−１２）において、「＾」は排他的論理和を示す。
【０１０５】
上記式（３２−１）〜（３２−１２）から、１２ビットのパリティを求めることができる。また、検査行列Ｈｏｒｇが、式（３１）を満たすことから、復号側では、検査行列Ｈｏｒｇを用いて、非特許文献８〜非特許文献１０に示されているようなＢＰ（Belief Propagation）復号、ＢＰ復号を近似したmin-sum復号、offset BP復号、Normalized BP復号、shuffled BP復号など行いデータを得ることができる。
【０１０６】
本実施の形態では、上述のように定義されるＬＤＰＣ−ＢＣの検査行列Ｈｏｒｇをプロトグラフとする検査行列Ｈについて検討する。
【０１０７】
図１０は、本実施の形態の検査行列の構成の概念図の一例を示している。本提案の検査行列Ｈは、図９の検査行列Ｈｏｒｇを対角線２０１上に配置し、対角線２０１の上三角の要素は「０」とするものとする。送信ベクトルｗＴを式（３３）のようにあらわすとき、検査行列Ｈと送信ベクトルｗＴの間には式（３４）が成立する。
【数３３】
2009100234.tif 000035
【数３４】
2009100234.tif 000036
【０１０８】
図１１は、図９に示したＬＤＰＣ−ＢＣの検査行列Ｈｏｒｇをプロトグラフとした場合の検査行列Ｈの一例を示している。検査行列Ｈを、複数のプロトグラフが結合（接続）した符号とするために、プロトグラフ８００を対角線上に配置し、さらに、プロトグラフ８００とは異なる位置に「１」を追加する。プロトグラフとは異なる位置に配置された「１」は、復号側（受信側）で尤度を結合するために用いられる。
【０１０９】
図１１には、ＬＤＰＣ−ＢＣの検査行列Ｈｏｒｇのプロトグラフ８００を結合（接続）するために、位置８０２及び位置８０４に「１」が追加された例が示されている。
【０１１０】
位置８０２及び位置８０４に「１」が追加されたことにより、検査式は以下の式（３５−１）〜（３５−１２）のようになる。
【数３５】
2009100234.tif 000037
【０１１１】
位置８０２及び位置８０４に「１」が追加されたことにより、過去の符号語ｘｉ−１，２が検査式（３５−１２）に含まれるようになる。
【０１１２】
この検査式（３５−１２）には、２つのパリティｑｉ，１０，ｑｉ，１１が含まれている。そこで、以下では、パリティｑｉ，１０，ｑｉ，１１のうち、ＬＤＰＣ−ＢＣ符号化により生成されるｐｉ，１１と過去の符号語ｘｉ−１，２とを用いて、式（３６）から、パリティｑｉ，１１を書き換える場合について説明する。なお、パリティｑｉ，１０を書き換える場合については、後述する。
【数３６】
2009100234.tif 000038
【０１１３】
位置８０２及び位置８０４に追加した「１」により、パリティｑ１，１１，ｑ２，１１は、ＬＤＰＣ−ＢＣのパリティｐ１，１１，ｐ２，１１を用いて、式（３６）より書き換えられる。このとき、検査式（３５−１）〜（３５−１２）には、ｑｉ，１１を含む検査式が式（３５−１２）のみであるので、位置８０２及び位置８０４に「１」を追加した場合において、図１１の検査行列Ｈは、式（３４）を満たす。
【０１１４】
したがって、図１１の検査行列Ｈを用いて、非特許文献８〜非特許文献１１に示されているようなＢＰ復号、ＢＰ復号を近似したmin-sum復号、offset BP復号、Normalized BP復号、shuffled BP復号など行うことができる。
【０１１５】
なお、ＬＤＰＣ−ＢＣ符号化により生成されるｐｉ，１０を用いて、式（３７）から、パリティｑｉ，１０を書き換える場合には、位置８０２及び位置８０４に「１」を追加したことにより、検査式（３５−１１）が満たされなくなってしまう。
【数３７】
2009100234.tif 000039
【０１１６】
そこで、ｐｉ，１０を用いて、式（３７）から、パリティｑｉ，１０を書き換える場合には、実施の形態１に示した場合と同様に、検査式（３５−１１）において、ｘｉ−１，２が含まれるように、検査行列Ｈに「１」をさらに追加する必要がある。なお、この場合には、検査行列Ｈに長さ４のループが含まれるようになるため、実施の形態２と同様に、検査行列Ｈを等価な検査行列に置き換えるようにすることが望ましい。なお、この点については、実施の形態４において説明する。
【０１１７】
（符号化器の構成）
図１１において、プロトグラフ８００をＨｏｒｇ、プロトグラフ８０６をＨｍとあらわすと、図１１の検査行列Ｈは、式（３８）のようにあらわすことができる。
【数３８】
2009100234.tif 000040
【０１１８】
以下では、式（３８）であらわされる検査行列Ｈに基づく符号化器の構成例について説明する。
【０１１９】
図１２は、図１１の検査行列Ｈに基づき符号化を施す符号化器の構成の一例を示している。図１２において、符号化器９００は、ＬＤＰＣ−ＢＣ符号化部９１０、記憶部９２０、及びパリティ修正部９３０を備えて構成される。
【０１２０】
ＬＤＰＣ−ＢＣ符号化部９１０は、データ９０１（ｘｉ，０，ｘｉ，１，ｘｉ，２，ｘｉ，３，ｘｉ，４，ｘｉ，５，ｘｉ，６，ｘｉ，７，ｘｉ，８，ｘｉ，９，ｘｉ，１０，ｘｉ，１１，ｘｉ，１２，ｘｉ，１３，ｘｉ，１４，ｘｉ，１５）を入力とし、式（３４）の関係式を用いて、パリティ９０３を生成する。ＬＤＰＣ−ＢＣ符号化部９１０は、生成したパリティ９０３（ｐｉ，０，ｐｉ，１，ｐｉ，２，ｐｉ，３，ｐｉ，４，ｐｉ，５，ｐｉ，６，ｐｉ，７，ｐｉ，８，ｐｉ，９，ｐｉ，１０，ｐｉ，１１）をパリティ修正部９３０に出力する。
【０１２１】
記憶部９２０は、データ９０１を入力とし、検査式に関連するｘｉ−１，２を少なくとも記憶する。そして、記憶部９２０は、パリティ修正部９３０がｉ番目の符号化を行う際に、記憶している（ｉ−１）番目のデータ９０５（ｘｉ−１，２）をパリティ修正部９３０に出力する。
【０１２２】
パリティ修正部９３０は、パリティ９０３（ｐｉ，０，ｐｉ，１，ｐｉ，２，ｐｉ，３，ｐｉ，４，ｐｉ，５，ｐｉ，６，ｐｉ，７，ｐｉ，８，ｐｉ，９，ｐｉ，１０，ｐｉ，１１）、及び、（ｉ−１）番目のデータ９０５（ｘｉ−１，２）を入力する。そして、パリティ修正部９３０は、式（３９−１），（３９−２）を用いてパリティ９０３を修正し、修正後のパリティ９０６（ｑｉ，０，ｑｉ，１，ｑｉ，２，ｑｉ，３，ｑｉ，４，ｑｉ，５，ｑｉ，６，ｑｉ，７，ｑｉ，８，ｑｉ，９，ｑｉ，１０，ｑｉ，１１）を出力する。
【数３９】
2009100234.tif 000041
【０１２３】
このように、符号化側では、式（３９−２）を用いて、ＬＤＰＣ−ＢＣ符号化部９１０から出力されるパリティｐｉ，１１を修正するだけで、式（３４）を満たす符号化を施すことができるので、簡易な構成で符号化器９００を構成することができる。
【０１２４】
このとき、ＬＤＰＣ−ＢＣ符号化部９１０が、パケットサイズに合わせたブロック長で符号化を行うようにすれば、余分なビットを送信する量を少なくすることができ、データ伝送効率の劣化を回避することができる。
【０１２５】
以上のように、本実施の形態によれば、ＬＤＰＣ−ＢＣの検査行列Ｈｏｒｇがプロトグラフとして用いられ、かつ、当該プロトグラフが対角線上に配置された検査行列Ｈに基づいて符号化を施す場合において、ＬＤＰＣ−ＢＣ符号化部９１０は、検査行列Ｈｏｒｇに基づいて入力データに対しＬＤＰＣ−ＢＣ符号化を施し、記憶部９２０は、当該プロトグラフと異なる位置に「１」を追加することにより、複数のプロトグラフを結合した結果、検査行列Ｈの検査式に含まれる過去の符号語を保持し、パリティ修正部９３０は、記憶部９２０に保持された過去の符号語を用いて、ＬＤＰＣ−ＢＣ符号化部９１０から出力されるパリティビットを修正するようにした。
【０１２６】
符号化側では、ＬＤＰＣ−ＢＣの検査行列Ｈｏｒｇがプロトグラフとして用いられ、かつ、プロトグラフが対角線上に配置され、かつ、複数のプロトグラフを結合するために、プロトグラフと異なる位置に「１」が追加された検査行列Ｈを用いて符号化を施す場合に、予め、ｉ番目の符号語を生成するにあたり関連する（ｉ−１）番目の過去の符号語と、過去の符号語を用いて修正するｉ番目のパリティビットを選択しておき、入力データに対しＬＤＰＣ−ＢＣ符号化を施し、組織化ビット及びパリティビットから成る符号語を生成し、選択したｉ番目のパリティビットを選択した（ｉ−１）番目の過去の符号語で修正するようにした。
【０１２７】
このようにすることで、過去の符号語が検査式に含められ、プロトグラフが結合される。過去の符号語を検査式に含めることにより、プロトグラフ同士の確率伝播の関係から、フェージングの影響による受信電界強度の低下の影響を軽減することができるので、受信品質を改善することができる。また、検査式（３４）を満たす検査行列Ｈに基づいた符号化を施すので、復号側では、ＢＰ復号アルゴリズムを用いて、過去の尤度を結合しながら復号することができ、優れた復号特性を得ることができる。
【０１２８】
以上の説明では、プロトグラフを結合（接続）するために関連する符号語が１ビット（ｘｉ−１，０）の場合について説明したが、これに限ったものではなく、２ビット以上の場合についても同様に実施することができる。
【０１２９】
また、本実施の形態では、図９に示すようなＬＤＰＣ−ＢＣの検査行列をプロトグラフとする場合を例に説明したが、他のＬＤＰＣ−ＢＣを用いても同様に実施することができる。
【０１３０】
また、本実施の形態では、「１」を追加する位置をデータ（ｘｉ−１，２）に関連する位置（例えば、位置８０２）とする場合について説明したが、これに限ったものではなく、パリティに関連する位置に「１」を追加してもよい。その例については、実施の形態５で説明する。
【０１３１】
（実施の形態４）
本実施の形態では、実施の形態３における図１１の検査行列Ｈの変形方法について説明する。
【０１３２】
図１３は、ＬＤＰＣ−ＢＣの検査行列をプロトグラフとした場合の検査行列を示す図である。なお、図１３において図１１と同一の部分には同一符号を付して説明を省略する。
【０１３３】
図１３に示す検査行列Ｈは、ＬＤＰＣ−ＢＣの検査行列のプロトグラフを結合（接続）するために位置１００２及び位置１００４に「１」を追加した場合の例である。
【０１３４】
位置１００２及び位置１００４に「１」を追加することにより、検査式（４０−１）,（４０−２）を得る。
【数４０】
2009100234.tif 000042
【０１３５】
このように、位置１００２及び位置１００４に「１」が追加されたことにより、検査式（４０−１）,（４０−２）に、過去の符号語ｘｉ−１，０が含まれるようになる。このとき、検査式（４０−１）,（４０−２）のいずれにもパリティｑｉ，０が含まれていることから、以下では、ＬＤＰＣ−ＢＣ符号化により生成されるパリティｐｉ，０を用いて、式（４１）から、パリティｑｉ，０を書き換える場合について説明する。
【数４１】
2009100234.tif 000043
【０１３６】
式（４１）を用いることにより、位置１００２及び位置１００４に追加した「１」により、ＬＤＰＣ−ＢＣのパリティｐ１，０，ｐ２，０は、パリティｑ１，０，ｑ２，０に書き換えられる。
【０１３７】
このように、図１３の検査行列Ｈは、検査式に関連する過去の符号語としてｘｉ−１，０を選択し、過去の符号語ｘｉ−１，０により修正されるパリティビットとしてパリティｑｉ，０を選択した場合に、式（３４）を満たすように、「１」が追加された場合の例である。
【０１３８】
図１３に示す検査行列Ｈは、式（３４）を満たすので、非特許文献８〜非特許文献１１に示されているようなＢＰ復号、ＢＰ復号を近似したmin-sum復号、offset BP復号、Normalized BP復号、shuffled BP復号など行うことができる。
【０１３９】
図１３において、プロトグラフ８００をＨｏｒｇ、プロトグラフ１０００をＨｍとすると、図１３の検査行列Ｈは、式（４２）のようにあらわすことができる。
【数４２】
2009100234.tif 000044
【０１４０】
非特許文献１１に示されているように、一般に、タナーグラフを描いた際、長さ４のループが存在する場合、ＢＰ復号を行うと受信品質が劣化するという問題がある。図１３の検査行列では、位置１００２及び位置１００４に「１」を追加したことにより、位置１００２と位置１００１との間、及び、位置１００４と位置１００３との間に、長さ４のループが発生し、これにより、受信品質が劣化する。
【０１４１】
この問題を解決するために、本実施の形態では、図１３に示した検査行列Ｈと等価の検査行列であり、かつ、長さ４のループの数を少なくした検査行列の作成方法について説明する。
【０１４２】
図１４に、本実施の形態の検査行列の構成の一例を示す。図１４において、図１１及び図１３と同一の部分には同一符号を付して説明を省略する。
【０１４３】
図１４において、プロトグラフ８００は、ＬＤＰＣ−ＢＣの検査行列であり、プロトグラフ８００において、ｘｉ−０に関する検査行１１００の間には、式（４３−１）〜（４３−３）に示す関係式が成立する。
【数４３】
2009100234.tif 000045
【０１４４】
したがって、式（４３−１）〜（４３−３）から、ｘ０，０は、式（４４−１）〜（４４−３）のようにあらわすことができる。
【数４４】
2009100234.tif 000046
【０１４５】
同様に、検査行列Ｈの対角線上のプロトグラフ８００において、一般的に、以下の関係式（４５−１）〜（４５−３）が成立する。
【数４５】
2009100234.tif 000047
【０１４６】
本実施の形態では、上記式（４５−１）〜（４５−３）の関係式を利用して、図１３のプロトグラフ１０００を、図１４のプロトグラフ１１０３のように書き換えるようにした。具体的には、図１３の位置１００２に追加された「１」により、ｘｉ，０が含まれるようになった検査式において、ｘｉ，０を、式（４５−１）〜（４５−３）を用いて、ｘｉ，０以外の符号語で置き換えるようにした。
【０１４７】
例えば、図１４において、検査行１１０５は、式（４５−１）を用いて置き換えられている。同様に、検査行１１０６は、それぞれ、式（４５−２）を用いて置き換えられている。
【０１４８】
このようにすることで、図１４の検査行列Ｈ１には、長さ４のループが含まれなくなるようになるので、図１３の検査行列Ｈを用いる場合に比し、受信品質を改善することができる。
【０１４９】
図１４において、プロトグラフ１１０３をＨｎ、プロトグラフ８００をＨｏｒｇとすると、図１４の検査行列Ｈ１は、式（４６）のようにあらわすことができる。
【数４６】
2009100234.tif 000048
【０１５０】
式（４６）から分かるように、ＬＤＰＣ−ＢＣの検査行列Ｈｏｒｇが、検査行列Ｈｎにより結合されることになる。式（４６）の検査行列Ｈ１は、式（３８）の検査行列Ｈと等価であるため、本実施の形態の検査行列Ｈ１に基づく符号化器の構成は、実施の形態１と同様の構成を採ることができる。
【０１５１】
復号側では、図１３の検査行列Ｈに代えて、図１４の検査行列Ｈ１を用いて復号を施す。図１３の検査行列Ｈと等価である図１４の検査行列Ｈ１には、長さ４のループが含まれないので、図１３の検査行列Ｈを用いて復号を施す場合に比べ、受信品質を改善することができる。
【０１５２】
以上のように、本実施の形態によれば、ＬＤＰＣ−ＢＣの検査行列Ｈｏｒｇがプロトグラフとして用いられ、かつ、当該プロトグラフが対角線上に配置され、かつ、複数の当該プロトグラフを結合するために、当該プロトグラフと異なる位置に「１」が追加された、検査行列Ｈに基づいて符号化された符号語を復号する場合に、当該プロトグラフと異なる位置に追加された「１」により検査行列Ｈの検査式に含まれる過去の符号語ｘｉ，０が、他の過去の符号語に置き換わるように、検査行列Ｈに対し、追加される「１」の位置が変更された検査行列Ｈ１を用いて復号を施すようにした。
【０１５３】
検査行列Ｈ１は、検査行列Ｈと等価であるため、実施の形態１から実施の形態３と同様にＢＰ復号できるともに、検査行列Ｈ１には、長さ４のループが含まれなくなるので、受信品質を改善することができるようになる。
【０１５４】
以上の説明では、プロトグラフを結合（接続）するために関連する符号語が１ビット（ｘｉ−１，０）の場合について説明したが、これに限ったものではなく、２ビット以上の場合についても同様に実施することができる。
【０１５５】
また、本実施の形態では、図９に示すようなＬＤＰＣ−ＢＣの検査行列をプロトグラフとする場合を例に説明したが、他のＬＤＰＣ−ＢＣを用いても同様に実施することができる。
【０１５６】
また、本実施の形態では、「１」を追加する位置をデータ（ｘｉ−１，０）に関連する位置（位置１００２）とする場合について説明したが、これに限ったものではなく、パリティに関連する位置に「１」を追加してもよい。その例については、実施の形態５で説明する。
【０１５７】
（実施の形態５）
実施の形態１から実施の形態４では、検査行列に追加する「１」をデータに関連する位置とする場合について説明したが、本実施の形態では、パリティに関連する位置に「１」を追加した場合の例を説明する。なお、以下では、ＬＤＰＣ−ＢＣの検査行列をプロトグラフとする場合を例に説明する。
【０１５８】
図１５に、本実施の形態における検査行列の一例を示す。図１５の検査行列Ｈは、パリティに関連する位置に「１」が追加された場合の構成を示している。なお、図１５において、図１３と同一の部分には同一符号を付して説明を省略する。図１５の検査行列Ｈにおいて、プロトグラフ８００は、実施の形態３及び実施の形態４で用いたＬＤＰＣ−ＢＣの検査行列である。
【０１５９】
図１５に示す検査行列Ｈでは、ＬＤＰＣ−ＢＣの検査行列のプロトグラフを結合（接続）するために位置１２０１及び位置１２０２に「１」を追加した場合の例である。
【０１６０】
位置１２０１及び位置１２０２に「１」を追加することにより、式（４７−１）,（４７−２）に示すように、検査式にパリティｐｉ−１，１０が含まれるようになる。
【数４７】
2009100234.tif 000049
【０１６１】
図１５は、プロトグラフを結合するために関連する符号語としてパリティｐｉ−１，１０を選択し、このパリティｐｉ−１，１０により、式（４８）を用いて、パリティｑｉ，０を修正することとした場合の例である。
【数４８】
2009100234.tif 000050
【０１６２】
なお、図１６は、図１５の検査行列Ｈと等価の検査行列である。図１６において、図１３及び図１５と同一の部分には同一符号を付して説明を省略する。
【０１６３】
図１５の検査行列Ｈには、長さ４のループが存在していたのに対し、図１６の検査行列Ｈ１では、パリティｐｉ−１，１０を他の符号語で置き換えることにより、長さ４のループが含まれないようになっている。
【０１６４】
具体的には、式（３２−１１）から、一般式、式（４９）を得ることができるので、式（４９）を用いて、図１５の検査行１２０３,１２０４において、パリティｐｉ−１，１０に関連する位置に配置された「１」を、（ｘｉ，１，ｘｉ，１０，ｘｉ，１２，ｘｉ，１４，ｐｉ，９）に関連する位置に置き換えるようにした。これにより、図１５の検査行１２０３,１２０４が、図１６の検査行１３０２，１３０３に置き換わる。
【数４９】
2009100234.tif 000051
【０１６５】
復号側では、図１５の検査行列Ｈに代えて、図１５の検査行列Ｈと等価な図１６の検査行列Ｈ１を用いて復号を施す。図１６の検査行列Ｈ１には、長さ４のループが含まれないので、図１５の検査行列Ｈを用いて復号を施す場合に比べ、受信品質の劣化を防ぐことができる。
【０１６６】
（符号化器の構成）
図１５において、プロトグラフ８００をＨｏｒｇ、プロトグラフ１２００をＨｍとあらわすと、図１５の検査行列は、以下のようにあらわすことができる。
【数５０】
2009100234.tif 000052
【０１６７】
図１７は、図１５の検査行列Ｈ又は図１６の検査行列Ｈ１に基づき符号を施す符号化器の構成を示している。図１７において、図５及び図１２と同一の部分には同一符号を付して説明を省略する。図１７の符号化器１４００は、図１２の符号化器９００の記憶部９２０及びパリティ修正部９３０に代えて、記憶部１４１０及びパリティ修正部１４２０を備えて構成される。
【０１６８】
記憶部１４１０は、パリティ９０３を入力とし、プロトグラフとは異なる位置に「１」を追加することにより、検査式に含まれるｐｉ−１，０を少なくとも記憶する。そして、記憶部１４１０は、パリティ修正部１４２０がｉ番目の符号化を行う際に、記憶している（ｉ−１）番目のパリティｐｉ−１，０（１４０５）をパリティ修正部１４２０に出力する。
【０１６９】
パリティ修正部１４２０は、式（４８）及び式（５１）に基づいて、パリティｑｉ，ｊを生成し、得られたパリティｑｉ，ｊ（１４０６）を符号化器１４００の出力結果として出力する。
【数５１】
2009100234.tif 000053
【０１７０】
以上の説明では、ＬＤＰＣ−ＢＣの検査行列をプロトグラフとする場合を例に説明したが、これに限ったものではなく、実施の形態１で説明した差集合巡回符号の検査行列をプロトグラフとする場合においても、同様に実施することができる。
【０１７１】
また、例えば、ＢＣＨ符号等のブロック符号をプロトグラフとする場合においても同様に実施することができる。
【０１７２】
（実施の形態６）
これまでの実施の形態１から実施の形態５では、１種類のプロトグラフを複数結合して検査行列を生成する場合について説明したが、実際には、複数種類のプロトグラフを結合することも可能である。そこで、本実施の形態では、実施の形態１で用いた（２１，１１）差集合巡回符号の検査行列と実施の形態３で用いたＬＤＰＣ−ＢＣの検査行列とをプロトグラフとし、これら２種類のプロトグラフを結合するために、プロトグラフと異なる位置に「１」が追加された検査行列に基づく符号化方法、復号方法、及び符号化器について説明する。
【０１７３】
図１８に、本実施の形態における検査行列Ｈの一例を示す。図１８の検査行列Ｈでは、複数のプロトグラフを結合し、かつ、式（５２）を満たすように、位置１５０３及び位置１５０５に「１」が追加されている。
【数５２】
2009100234.tif 000054
【０１７４】
なお、式（５２）において、ｗは、符号語（送信ベクトル）であり、符号語（送信ベクトル）ｗは、式（５３）のようにあわらわれる。
【数５３】
2009100234.tif 000055
なお、式（５３）において、ｘｉ，ｊはデータであり、ｑｉ，ｊはパリティである。
【０１７５】
図１８の検査行列Ｈにおいて、プロトグラフ８００は、ＬＤＰＣ−ＢＣの検査行列である。以下、ＬＤＰＣ−ＢＣの検査行列をＨｏｒｇ１とあらわす。また、プロトグラフ３００は、（２１，１１）差集合巡回符号の検査行列である。以下、（２１，１１）差集合巡回符号の検査行列をＨｏｒｇ２とあらわす。
【０１７６】
図１８の検査行列Ｈは、プロトグラフを結合するために関連する符号語をｘ２ｉ＋１，０及びｘ２ｉ，０とし、符号語ｘ２ｉ＋１，０によりパリティビットｑ２ｉ＋２，１０を修正するとして選択し、かつ、符号語ｘ２ｉ，０によりパリティビットｑ２ｉ＋１，９を修正するとして選択した場合の例である。
【０１７７】
位置１５０３に「１」が追加された行に対応する検査式は、以下の式（５４−１）〜（５４−５）のようになる。
【数５４】
2009100234.tif 000056
【０１７８】
位置１５０３に「１」を追加したことにより、ｑ２ｉ＋１，９は、式（５５）のように表される。
【数５５】
2009100234.tif 000057
【０１７９】
同様に、位置１５０５に「１」が追加された行に対応する検査式は、以下の式（５６−１）〜（５６−２）のようになる。
【数５６】
2009100234.tif 000058
【０１８０】
位置１５０５に「１」を追加したことにより、ｑ２ｉ，１０は、式（５７）のように表される。
【数５７】
2009100234.tif 000059
【０１８１】
このように、図１８、ｑ２ｉ＋１，９を過去の符号語ｘ２ｉ，０を用いて修正するようにし、ｑ２ｉ＋２，１０を過去の符号語ｘ２ｉ＋１，０を用いて修正するとして、位置１５０３及び位置１５０５に「１」を追加するようにした。
【０１８２】
（符号化器の構成）
図１８において、ＬＤＰＣ−ＢＣの検査行列であるプロトグラフ１５０６をＨｍ１、（２１，１１）差集合巡回符号の検査行列であるプロトグラフ１５０７をＨｍ２とあらわすと、図１８の検査行列は、式（５８）のようにあらわすことができる。
【数５８】
2009100234.tif 000060
【０１８３】
以下では、式（５８）であらわされる検査行列Ｈに基づく符号化器の構成例について説明する。
【０１８４】
図１９は、図１８の検査行列Ｈに基づき符号化を施す符号化器の構成の一例を示している。なお、図１９において、図６及び図１２と同一部分には同一の符号を付してその説明を省略する。
【０１８５】
図１９において、符号化器１６００は、振り分け部１６１０、ＬＤＰＣ−ＢＣ符号化部９１０、差集合巡回符号化部５１０、記憶部５２０，９２０、及びパリティ修正部１６２０，１６３０を備えて構成される。
【０１８６】
振り分け部１６１０は、データｘを入力とし、データｘを、データ１６０３（ｘ２ｉ，０，ｘ２ｉ，１，ｘ２ｉ，２，ｘ２ｉ，３，ｘ２ｉ，４，ｘ２ｉ，５，ｘ２ｉ，６，ｘ２ｉ，７，ｘ２ｉ，８，ｘ２ｉ，９，ｘ２ｉ，１０，ｘ２ｉ，１１，ｘ２ｉ，１２，ｘ２ｉ，１３，ｘ２ｉ，１４，ｘ２ｉ，１５）とデータ１６０８（ｘ２ｉ＋１，０，ｘ２ｉ＋１，１，ｘ２ｉ＋１，２，ｘ２ｉ＋１，３，ｘ２ｉ＋１，４，ｘ２ｉ＋１，５，ｘ２ｉ＋１，６，ｘ２ｉ＋１，７，ｘ２ｉ＋１，８，ｘ２ｉ＋１，９，ｘ２ｉ＋１，１０）とに振り分ける。振り分け部１６１０は、データ１６０３をＬＤＰＣ−ＢＣ符号化部９１０及び記憶部９２０に出力するとともに、データ１６０８を差集合巡回符号化部５１０及び記憶部５２０に出力する。
【０１８７】
ＬＤＰＣ−ＢＣ符号化部９１０は、データ１６０３を入力とし、パリティ１６０５（ｐ２ｉ，０，ｐ２ｉ，１，ｐ２ｉ，２，ｐ２ｉ，３，ｐ２ｉ，４，ｐ２ｉ，５，ｐ２ｉ，６，ｐ２ｉ，７，ｐ２ｉ，８，ｐ２ｉ，９，ｐ２ｉ，１０，ｐ２ｉ，１１）を生成し、生成したパリティ１６０５をパリティ修正部１６２０に出力する。
【０１８８】
記憶部９２０は、データ１６０３を入力とし、検査式に関連するｘ２ｉ，０を少なくとも記憶する。そして、記憶部９２０は、パリティ修正部１６３０が（２ｉ＋１）番目の符号化を行う際に、記憶している２ｉ番目のデータｘ２ｉ，０（１６０７）をパリティ修正部１６３０に出力する。
【０１８９】
差集合巡回符号化部５１０は、データ１６０８を入力とし、パリティ１６１２（ｐ２ｉ＋１，０，ｐ２ｉ＋１，１，ｐ２ｉ＋１，２，ｐ２ｉ＋１，３，ｐ２ｉ＋１，４，ｐ２ｉ＋１，５，ｐ２ｉ＋１，６，ｐ２ｉ＋１，７，ｐ２ｉ＋１，８，ｐ２ｉ＋１，９）を生成し、生成したパリティ１６１２をパリティ修正部１６３０に出力する。
【０１９０】
記憶部５２０は、データ１６０８を入力とし、プロトグラフとは異なる位置に「１」を追加することにより、検査式に含まれるｘ２ｉ-１，０を少なくとも記憶する。そして、記憶部５２０は、パリティ修正部１６２０が２ｉ番目の符号化を行う際に、記憶している（２ｉ−１）番目のデータｘ２ｉ-１，０（１６１４）をパリティ修正部１６２０に出力する。
【０１９１】
パリティ修正部１６２０は、ＬＤＰＣ−ＢＣ符号化部９１０から出力されるパリティｐ２ｉ，ｊ（１６０５）と記憶部５２０に保持されるデータｘ２ｉ-１，０（１６１４）を入力とし、式（５７），（５９）に基づいて、パリティｑ２ｉ，ｊを取得し、得られたパリティｑ２ｉ，ｊ（１６０９）を符号化器１６００の出力結果として出力する。
【数５９】
2009100234.tif 000061
【０１９２】
同様に、パリティ修正部１６３０は、差集合巡回符号化部５１０から出力されるパリティｐ２ｉ＋１，ｊ（１６１２）と記憶部５２０に保持されるデータｘ２ｉ，０（１６０７）を入力とし、式（５５），（６０）に基づいて、パリティｑ２ｉ＋１，ｊを取得し、得られたパリティｑ２ｉ＋１，ｊ（１６１６）を符号化器１６００の出力結果として出力する。
【数６０】
2009100234.tif 000062
【０１９３】
以上のように、本実施の形態によれば、パリティ修正部１６２０は、記憶部５２０に保持された（２ｉ＋１）番目の符号語ｘ２ｉ＋１，０を用いて、ＬＤＰＣ−ＢＣ符号化部９１０から出力される（２ｉ＋２）番目パリティｐ２ｉ＋２，ｊを修正して、パリティｑ２ｉ＋２，ｊを取得し、パリティ修正部１６３０は、記憶部９２０に保持された２ｉ番目の符号語ｘ２ｉ，０を用いて、差集合巡回符号化部５１０から出力される（２ｉ＋１）番目パリティｐ２ｉ＋１，ｊを修正して、パリティｑ２ｉ＋１，ｊを取得するようにするようにした。このようにすることで、検査行列の対角線上に異なる種類のプロトグラフを配置し、これらプロトグラフを過去の符号語を用いて結合した検査行列に基づいて、比較的簡易な処理で符号化を施すことができる。
【０１９４】
なお、本実施の形態では、ＬＤＰＣ−ＢＣの検査行列及び（２１，１１）差集合巡回符号の検査行列をプロトグラフとし、これらプロトグラフを結合する場合を例に説明したが、これに限ったものではない。
【０１９５】
（実施の形態７）
上述の実施の形態では、差集合巡回符号の検査行列又はＬＤＰＣの検査行列をプロトグラフとし、これらプロトグラフを複数結合する場合を例に説明した。ところで、イーサネット（登録商標）や無線ＬＡＮのフレームなどのように送信情報系列が可変長な場合には、送信情報系列長がプロトタイプを構成する検査行列のブロック長よりも短いような場合が考えられる。本実施の形態は、送信情報系列長が可変するような場合においても、確実にデータ伝送効率の劣化を防止することができ、かつ、伝送品質を向上させることができる符号化器及び符号化方法について説明する。
【０１９６】
図２０は、本実施の形態に係る符号化器の構成の一例を示す図である。なお、図２０において、図６と同一の部分には同一符号を付して説明を省略する。図２０の符号化器１７００は、図６の符号化器５００に対し、パリティ修正部５３０に代えて、パリティ修正部１７３０を備え、データ長カウント部１７１０及びパリティ演算切替部１７２０をさらに追加した構成を採る。
【０１９７】
データ長カウント部１７１０は、データ５０１（ｘｉ，０，ｘｉ，１，ｘｉ，２，ｘｉ，３，ｘｉ，４，ｘｉ，５，ｘｉ，６，ｘｉ，７，ｘｉ，８，ｘｉ，９，ｘｉ，１０）を入力とし、データ５０１のデータ長をカウントし、カウント値をパリティ演算切替部１７２０に出力する。
【０１９８】
パリティ演算切替部１７２０は、カウント値に基づいて、パリティ修正部１７３０においてパリティ修正を行うか否かの指示信号をパリティ修正部１７３０に出力する。具体的には、パリティ演算切替部１７２０は、カウント値が、差集合巡回符号化部５１０のブロック長より長い場合、パリティ修正部１７３０において、パリティ修正部５３０と同様に、式（２２）を用いてパリティｐｉ，７を修正するような指示信号をパリティ修正部１７３０に出力する。一方、カウント値が、差集合巡回符号化部５１０のブロック長以下の場合、パリティ修正部１７３０において、パリティ修正を行わないような指示信号をパリティ修正部１７３０に出力する。
【０１９９】
パリティ修正部１７３０は、パリティ演算切替部１７２０からの指示信号に応じて、パリティ修正を行うか否か切替る。したがって、データ５０１のデータ長が、差集合巡回符号化部５１０のブロック長より長い場合、パリティ修正部１７３０は、式（２２）を用いて、パリティｐｉ，７を修正し、修正後のパリティｑｉ，７を符号化器１７００の出力結果として出力する。一方、データ５０１のデータ長が、差集合巡回符号化部５１０のブロック長以下の場合、パリティ修正部１７３０は、パリティ修正を行わず、差集合巡回符号化部５１０から出力されるパリティを符号化器１７００の出力結果として出力する。
【０２００】
このようにすることで、データ長が差集合巡回符号のブロック長以下の場合には、差集合巡回符号の検査行列Ｈｏｒｇがプロトグラフとして結合された検査行列Ｈ（図３参照）を用いずに、検査行列Ｈｏｒｇのみを用いて符号化が施されるようになるので、余分に送信されるビット量を最小限に抑えることができ、データ伝送効率の劣化を防止することができる。
【０２０１】
一方、データ長が差集合巡回符号のブロック長より長い場合、パリティの書き換えを行い、差集合巡回符号の検査行列Ｈｏｒｇを連結するため、受信品質が向上するという効果を得ることができる。
【０２０２】
なお、通信相手が復号に用いる検査行列を切り替えることができるように、通信相手に対し、パリティ修正を行ったか否かを通知するための制御情報を送信する必要がある。
【０２０３】
以上のように、本実施の形態によれば、データ長カウント部１７１０は、データ５０１のデータ長をカウントし、パリティ演算切替部１７２０は、データ長に応じて、パリティ修正を行うか否かの指示信号をパリティ修正部１７３０に出力し、パリティ修正部１７３０は、パリティ演算切替部１７２０からの指示信号に応じて、パリティ修正を行うか否か切替るようにした。これにより、送信情報系列が可変な場合においても、余分に送信されるビット量を最小限に抑え、データ伝送効率の劣化を防止することができ、かつ、パリティの書き換えを行った場合、受信品質が向上するという効果を得ることができる。
【０２０４】
なお、以上の説明では、パリティ演算切替部１７２０は、データ５０１のデータ長に応じて、パリティ修正を行うか否か切り替えるようにしたが、データ長に代えて、例えば、通信相手からの制御信号に応じて切り替えるようにしてもよい。
【０２０５】
以上の説明では、差集合巡回符号を例に説明したが、この符号に限ったものではなく、ＬＤＰＣ符号等のブロック符号であれば同様に実施することができる。また、本実施の形態では、実施の形態１〜６の連結方法を用いる場合を例に説明したが、これに限ったものではなく、他の連結方法を用いる場合でも同様に実施することができる。つまり、オリジナルのブロック符号をベースとし、データ長がオリジナルのブロック符号長より長い場合、簡単な演算で、パリティビットを書き換えることにより、オリジナルのブロック符号を連結する場合であれば、同様に実施することができる。
【０２０６】
なお、本発明は上記すべての実施の形態に限定されず、種々変更して実施することが可能である。例えば、上記実施の形態では、主に、符号化器及び復号器で実現する場合について説明しているが、これに限られるものではなく、この符号化方法及び復号方法をソフトウェアとして行うことも可能である。
【０２０７】
例えば、上記符号化方法及び復号方法を実行するプログラムを予めＲＯＭ（Read Only Memory）に格納しておき、そのプログラムをＣＰＵ（Central Processor Unit）によって動作させるようにしても良い。
【０２０８】
また、上記符号化方法及び復号方法を実行するプログラムをコンピュータで読み取り可能な記憶媒体に格納し、記憶媒体に格納されたプログラムをコンピュータのＲＡＭ（Random Access Memory）に記録して、コンピュータをそのプログラムにしたがって動作させるようにしても良い。
【産業上の利用可能性】
【０２０９】
本発明は、差集合巡回符号又はＬＤＰＣ−ＢＣ符号を接続して形成された検査行列に基づく符号を適用する通信システムに広く適用できる。
【図面の簡単な説明】
【０２１０】
【図１】sum-product復号を施す復号器の構成の一例を示すブロック図
【図２】本実施の形態１における（２１，１１）差集合巡回符号の検査行列Ｈｏｒｇの一例を示す図
【図３】実施の形態１における検査行列Ｈの構成の概念図の一例を示す図
【図４】（２１，１１）差集合巡回符号の検査行列Ｈｏｒｇをプロトグラフとした場合の検査行列Ｈの一例を示す図
【図５】実施の形態１の検査行列Ｈの一例を示す図
【図６】実施の形態１に係る符号化器の要部構成を示すブロック図
【図７】実施の形態１の検査行列Ｈの別の一例を示す図
【図８】本実施の形態２の検査行列Ｈの一例を示す図
【図９】ＬＤＰＣ―ＢＣの検査行列Ｈｏｒｇの一例を示す図
【図１０】本実施の形態３における検査行列の構成の概念図の一例を示す図
【図１１】実施の形態３における検査行列Ｈの一例を示す図
【図１２】実施の形態３に係る符号化器の要部構成を示すブロック図
【図１３】ＬＤＰＣ−ＢＣの検査行列をプロトグラフとした場合の検査行列を示す図
【図１４】本実施の形態４の検査行列の構成の一例を示す図
【図１５】本実施の形態５における検査行列の一例を示す図
【図１６】図１５の検査行列Ｈと等価な検査行列の一例を示す図
【図１７】実施の形態５に係る符号化器の要部構成を示すブロック図
【図１８】本実施の形態６における検査行列Ｈの一例を示す図
【図１９】実施の形態６に係る符号化器の要部構成を示すブロック図
【図２０】実施の形態７に係る符号化器の要部構成を示すブロック図
【図２１】ＬＤＰＣ−ＣＣの検査行列を示す図
【図２２】ＬＤＰＣ−ＣＣ符号化器の構成例を示す図
【符号の説明】
【０２１１】
１０５  行処理演算部
１０７  行処理後データ記憶部
１０９  列処理演算部
１１１  列処理後データ記憶部
１１５  対数尤度比演算部
１１７  判定部
１１３  制御部
１０３  対数尤度比記憶部
５００，９００，１６００  符号化器
５１０  差集合巡回符号化部
５２０，９２０，１４１０  記憶部
５３０，９３０，１４２０，１６２０，１６３０，１７３０  パリティ修正部
９１０  ＬＤＰＣ−ＢＣ符号化部
１６１０  振り分け部
１７１０  データ長カウント部
１７２０  パリティ演算切替部
【図１】
2009100234.tif 000063
【図２】
2009100234.tif 000064
【図３】
2009100234.tif 000065
【図４】
2009100234.tif 000066
【図５】
2009100234.tif 000067
【図６】
2009100234.tif 000068
【図７】
2009100234.tif 000069
【図８】
2009100234.tif 000070
【図９】
2009100234.tif 000071
【図１０】
2009100234.tif 000072
【図１１】
2009100234.tif 000073
【図１２】
2009100234.tif 000074
【図１３】
2009100234.tif 000075
【図１４】
2009100234.tif 000076
【図１５】
2009100234.tif 000077
【図１６】
2009100234.tif 000078
【図１７】
2009100234.tif 000079
【図１８】
2009100234.tif 000080
【図１９】
2009100234.tif 000081
【図２０】
2009100234.tif 000082
【図２１】
2009100234.tif 000083
【図２２】
2009100234.tif 000084