(57)【要約】      （修正有）【課題】ＬＤＰＣ−ＣＣを用いた符号化方法において、パリティ検査行列Ｈにフィードバックがある場合に、送信する情報に対応するパリティを求める際の演算規模を抑制する。【解決手段】フィードバックがあるパリティ検査行列Ｈに基づいて送信する情報に付加するパリティを求める。当該パリティ検査行列Ｈは、送信する情報ビット系列Ｘ１、Ｘ２、・・・、Ｘｎと、ＬＤＰＣ−ＣＣにより付加されるパリティビット系列Ｐ１、Ｐ２、・・・、Ｐｎとからなる符号化系列をｕ＝（Ｘ１、Ｘ２、・・・、Ｘｎ、Ｐ１、Ｐ２、・・・、Ｐｎ）とした場合に、ＨｕＴ＝０を満たし、且つ、ガウスの消去法を用いて、2011146899.tif 000033と変形行列ＨＧに変形することができる。変形行列ＨＧにおいて、情報ビット系列に対応するサブ行列Ｄはゼロ行列であることを満たし、パリティビット系列の一部に対応するサブ行列Ｂは単位行列であることを満たす。【選択図】図１１
2011146899.tif 000002
【特許請求の範囲】
【請求項１】
ＬＤＰＣ（Low Density Parity Check）畳み込み符号を用いた符号化方法であって、
送信する情報ビット系列をＸ１、Ｘ２、・・・、Ｘｎとし、当該情報ビットに対応して前記ＬＤＰＣ畳み込み符号により付加されるパリティビット系列をＰ１、Ｐ２、・・・、Ｐｎとし、前記情報ビット系列と前記パリティビット系列とからなる符号化系列をｕ＝（Ｘ１、Ｘ２、・・・、Ｘｎ、Ｐ１、Ｐ２、・・・、Ｐｎ）とし、ＨｕＴ＝０（ｕＴは符号化系列ｕの転置行列）を満たす前記ＬＤＰＣ畳み込み符号のパリティ検査行列をＨとすると、
前記ＬＤＰＣ畳み込み符号のパリティ検査行列Ｈの少なくとも一つの行において、前記符号化系列ｕにおいてパリティビット系列に対応する位置の前記行の要素のうち「１」を有する要素の数が２以上であり、
前記パリティ検査行列Ｈは、ガウスの消去法を用いることで、サブ行列Ａ、Ｂ、Ｃ、Ｄ、Ｅにより、
【数１】
2011146899.tif 000026
として表される変形行列ＨＧに変形することができ、
前記サブ行列Ａ及び前記サブ行列Ｄの列数は前記情報ビット系列の数に等しく、前記サブ行列Ｂの列数と前記サブ行列Ｃの列数との合計は、前記サブ行列Ｄの列数と等しくかつ前記パリティビット系列の数に等しく、前記サブ行列Ｂは単位行列であり、前記サブ行列Ｄはゼロ行列であり、
前記Ｈ又は前記ＨＧに基づいて、前記情報ビット系列から前記パリティビット系列を生成する
ことを特徴とする符号化方法。
【請求項２】
ＬＤＰＣ（Low Density Parity Check）畳み込み符号を用いた符号化により生成される符号化系列に基づく送信系列を送信する送信方法であって、
送信する情報ビット系列をＸ１、Ｘ２、・・・、Ｘｎとし、当該情報ビットに対応して前記ＬＤＰＣ畳み込み符号により付加されるパリティビット系列をＰ１、Ｐ２、・・・、Ｐｎとし、前記情報ビット系列と前記パリティビット系列とからなる符号化系列をｕ＝（Ｘ１、Ｘ２、・・・、Ｘｎ、Ｐ１、Ｐ２、・・・、Ｐｎ）とし、ＨｕＴ＝０（ｕＴは符号化系列ｕの転置行列）を満たす前記ＬＤＰＣ畳み込み符号のパリティ検査行列をＨとすると、
前記ＬＤＰＣ畳み込み符号のパリティ検査行列Ｈの少なくとも一つの行において、前記符号化系列ｕにおいてパリティビット系列に対応する位置の前記行の要素のうち「１」を有する要素の数が２以上であり、
前記パリティ検査行列Ｈは、ガウスの消去法を用いることで、サブ行列Ａ、Ｂ、Ｃ、Ｄ、Ｅにより、
【数２】
2011146899.tif 000027
として表される変形行列ＨＧに変形することができ、
前記サブ行列Ａ及び前記サブ行列Ｄの列数は前記情報ビット系列の数に等しく、前記サブ行列Ｂの列数と前記サブ行列Ｃの列数との合計は、前記サブ行列Ｄの列数と等しくかつ前記パリティビット系列の数に等しく、前記サブ行列Ｂは単位行列であり、前記サブ行列Ｄはゼロ行列であり、
前記符号化は、
前記Ｈ又は前記ＨＧに基づいて、前記情報ビット系列から前記パリティビット系列を生成するものであり、
前記送信方法は、
前記符号化系列ｕから、送信側と受信側で予め既知の値として扱うと定められている値を除いた送信系列ｕ´を送信することを特徴とする送信方法。
【請求項３】
ＬＤＰＣ（Low Density Parity Check）畳み込み符号を用いた符号化を実行する符号化器であって、
送信する情報ビット系列をＸ１、Ｘ２、・・・、Ｘｎとし、当該情報ビットに対応して前記ＬＤＰＣ畳み込み符号により付加されるパリティビット系列をＰ１、Ｐ２、・・・、Ｐｎとし、前記情報ビット系列と前記パリティビット系列とからなる符号化系列をｕ＝（Ｘ１、Ｘ２、・・・、Ｘｎ、Ｐ１、Ｐ２、・・・、Ｐｎ）とし、ＨｕＴ＝０（ｕＴは符号化系列ｕの転置行列）を満たす前記ＬＤＰＣ畳み込み符号のパリティ検査行列をＨとすると、
前記ＬＤＰＣ畳み込み符号のパリティ検査行列Ｈの少なくとも一つの行において、前記符号化系列ｕにおいてパリティビット系列に対応する位置の前記行の要素のうち「１」を有する要素の数が２以上であり、
前記パリティ検査行列Ｈは、ガウスの消去法を用いることで、サブ行列Ａ、Ｂ、Ｃ、Ｄ、Ｅにより、
【数３】
2011146899.tif 000028
として表される変形行列ＨＧに変形することができ、
前記サブ行列Ａ及び前記サブ行列Ｄの列数は前記情報ビット系列の数に等しく、前記サブ行列Ｂの列数と前記サブ行列Ｃの列数との合計は、前記サブ行列Ｄの列数と等しくかつ前記パリティビット系列の数に等しく、前記サブ行列Ｂは単位行列であり、前記サブ行列Ｄはゼロ行列であり、
前記Ｈ又は前記ＨＧに基づいて、前記情報ビット系列から前記パリティビット系列を生成する
ことを特徴とする符号化器。
【請求項４】
ＬＤＰＣ（Low Density Parity Check）畳み込み符号を用いた符号化により生成される符号化系列に基づく送信系列を送信する送信装置であって、
送信する情報ビット系列をＸ１、Ｘ２、・・・、Ｘｎとし、当該情報ビットに対応して前記ＬＤＰＣ畳み込み符号により付加されるパリティビット系列をＰ１、Ｐ２、・・・、Ｐｎとし、前記情報ビット系列と前記パリティビット系列とからなる符号化系列をｕ＝（Ｘ１、Ｘ２、・・・、Ｘｎ、Ｐ１、Ｐ２、・・・、Ｐｎ）とし、ＨｕＴ＝０（ｕＴは符号化系列ｕの転置行列）を満たす前記ＬＤＰＣ畳み込み符号のパリティ検査行列をＨとすると、
前記ＬＤＰＣ畳み込み符号のパリティ検査行列Ｈの少なくとも一つの行において、前記符号化系列ｕにおいてパリティビット系列に対応する位置の前記行の要素のうち「１」を有する要素の数が２以上であり、
前記パリティ検査行列Ｈは、ガウスの消去法を用いることで、サブ行列Ａ、Ｂ、Ｃ、Ｄ、Ｅにより、
【数４】
2011146899.tif 000029
として表される変形行列ＨＧに変形することができ、
前記サブ行列Ａ及び前記サブ行列Ｄの列数は前記情報ビット系列の数に等しく、前記サブ行列Ｂの列数と前記サブ行列Ｃの列数との合計は、前記サブ行列Ｄの列数と等しくかつ前記パリティビット系列の数に等しく、前記サブ行列Ｂは単位行列であり、前記サブ行列Ｄはゼロ行列であり、
前記符号化は、
前記Ｈ又は前記ＨＧに基づいて、情報ビット系列から前記パリティビット系列を生成するものであり、
前記送信装置は、
前記符号化系列ｕから、送信側と受信側で予め既知の値として扱うと定められている値を除いた送信系列ｕ´を送信することを特徴とする送信装置。
【請求項５】
ＬＤＰＣ（Low Density Parity Check）畳み込み符号を用いた符号化により生成される符号化系列に基づく送信系列を受信して復号する復号方法であって、
送信する情報ビット系列をＸ１、Ｘ２、・・・、Ｘｎとし、当該情報ビットに対応して前記ＬＤＰＣ畳み込み符号により付加されるパリティビット系列をＰ１、Ｐ２、・・・、Ｐｎとし、前記情報ビット系列と前記パリティビット系列とからなる符号化系列をｕ＝（Ｘ１、Ｘ２、・・・、Ｘｎ、Ｐ１、Ｐ２、・・・、Ｐｎ）とし、ＨｕＴ＝０（ｕＴは符号化系列ｕの転置行列）を満たす前記ＬＤＰＣ畳み込み符号のパリティ検査行列をＨとすると、
前記ＬＤＰＣ畳み込み符号のパリティ検査行列Ｈの少なくとも一つの行において、前記符号化系列ｕにおいてパリティビット系列に対応する位置の前記行の要素のうち「１」を有する要素の数が２以上であり、
前記パリティ検査行列Ｈは、ガウスの消去法を用いることで、サブ行列Ａ、Ｂ、Ｃ、Ｄ、Ｅにより、
【数５】
2011146899.tif 000030
として表される変形行列ＨＧに変形することができ、
前記サブ行列Ａ及び前記サブ行列Ｄの列数は前記情報ビット系列の数に等しく、前記サブ行列Ｂの列数と前記サブ行列Ｃの列数との合計は、前記サブ行列Ｄの列数と等しくかつ前記パリティビット系列の数に等しく、前記サブ行列Ｂは単位行列であり、前記サブ行列Ｄはゼロ行列であり、
前記符号化は、
前記Ｈ又は前記ＨＧに基づいて、前記情報ビット系列から前記パリティビット系列を生成するものであり、
前記送信系列は、前記符号化系列ｕから、送信側と受信側で予め既知の値として扱うと定められている値を除いたものであり、
前記復号方法は、
受信した信号から得られた送信系列それぞれにおける対数尤度比に、前記既知の値に相当する対数尤度比を挿入し、前記パリティ検査行列Ｈを用いて信頼度伝播復号を行う
ことを特徴とする復号方法。
【請求項６】
ＬＤＰＣ（Low Density Parity Check）畳み込み符号を用いた符号化により生成される符号化系列に基づく送信系列を受信して復号する復号化器であって、
送信する情報ビット系列をＸ１、Ｘ２、・・・、Ｘｎとし、当該情報ビットに対応して前記ＬＤＰＣ畳み込み符号により付加されるパリティビット系列をＰ１、Ｐ２、・・・、Ｐｎとし、前記情報ビット系列と前記パリティビット系列とからなる符号化系列をｕ＝（Ｘ１、Ｘ２、・・・、Ｘｎ、Ｐ１、Ｐ２、・・・、Ｐｎ）とし、ＨｕＴ＝０（ｕＴは符号化系列ｕの転置行列）を満たす前記ＬＤＰＣ畳み込み符号のパリティ検査行列をＨとすると、
前記ＬＤＰＣ畳み込み符号のパリティ検査行列Ｈの少なくとも一つの行において、前記符号化系列ｕにおいてパリティビット系列に対応する位置の前記行の要素のうち「１」を有する要素の数が２以上であり、
前記パリティ検査行列Ｈは、ガウスの消去法を用いることで、サブ行列Ａ、Ｂ、Ｃ、Ｄ、Ｅにより、
【数６】
2011146899.tif 000031
として表される変形行列ＨＧに変形することができ、
前記サブ行列Ａ及び前記サブ行列Ｄの列数は前記情報ビット系列の数に等しく、前記サブ行列Ｂの列数と前記サブ行列Ｃの列数との合計は、前記サブ行列Ｄの列数と等しくかつ前記パリティビット系列の数に等しく、前記サブ行列Ｂは単位行列であり、前記サブ行列Ｄはゼロ行列であり、
前記符号化は、
前記Ｈ又は前記ＨＧに基づいて、前記情報ビット系列から前記パリティビット系列を生成するものであり、
前記送信系列は、前記符号化系列ｕから、送信側と受信側で予め既知の値として扱うと定められている値を除いたものであり、
前記復号化器は、
受信した信号から得られた送信系列それぞれにおける対数尤度比に、前記既知の値に相当する対数尤度比を挿入し、前記パリティ検査行列Ｈを用いて信頼度伝播復号を行う
ことを特徴とする復号化器。
【請求項７】
ＬＤＰＣ（Low Density Parity Check）畳み込み符号を用いた符号化により生成される符号化系列に基づく送信系列を受信して復号する受信装置であって、
送信する情報ビット系列をＸ１、Ｘ２、・・・、Ｘｎとし、当該情報ビットに対応して前記ＬＤＰＣ畳み込み符号により付加されるパリティビット系列をＰ１、Ｐ２、・・・、Ｐｎとし、前記情報ビット系列と前記パリティビット系列とからなる符号化系列をｕ＝（Ｘ１、Ｘ２、・・・、Ｘｎ、Ｐ１、Ｐ２、・・・、Ｐｎ）とし、ＨｕＴ＝０（ｕＴは符号化系列ｕの転置行列）を満たす前記ＬＤＰＣ畳み込み符号のパリティ検査行列をＨとすると、
前記ＬＤＰＣ畳み込み符号のパリティ検査行列Ｈの少なくとも一つの行において、前記符号化系列ｕにおいてパリティビット系列に対応する位置の前記行の要素のうち「１」を有する要素の数が２以上であり、
前記パリティ検査行列Ｈは、ガウスの消去法を用いることで、サブ行列Ａ、Ｂ、Ｃ、Ｄ、Ｅにより、
【数７】
2011146899.tif 000032
として表される変形行列ＨＧに変形することができ、
前記サブ行列Ａ及び前記サブ行列Ｄの列数は前記情報ビット系列の数に等しく、前記サブ行列Ｂの列数と前記サブ行列Ｃの列数との合計は、前記サブ行列Ｄの列数と等しくかつ前記パリティビット系列の数に等しく、前記サブ行列Ｂは単位行列であり、前記サブ行列Ｄはゼロ行列であり、
前記符号化は、
前記Ｈ又は前記ＨＧに基づいて、前記情報ビット系列から前記パリティビット系列を生成するものであり、
前記送信系列は、前記符号化系列ｕから、送信側と受信側で予め既知の値として扱うと定められている値を除いたものであり、
前記受信装置は、
受信した信号から得られた送信系列それぞれにおける対数尤度比に、前記既知の値に相当する対数尤度比を挿入し、前記パリティ検査行列Ｈを用いて信頼度伝播復号を行う
ことを特徴とする受信装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、低密度パリティ検査畳み込み符号（ＬＤＰＣ−ＣＣ：Low Density Parity Check-Convolutional Codes）におけるテイルバイティング（Tail-Biting）を用いる符号化器、復号化器及び符号化方法、復号化方法に関する。
【背景技術】
【０００２】
近年、実現可能な回路規模で高い誤り訂正能力を発揮する誤り訂正符号として、低密度パリティ検査（ＬＤＰＣ：Low-Density Parity-Check）符号に注目が集まっている。ＬＤＰＣ符号は、誤り訂正能力が高く、かつ実装が容易なので、IEEE802.11nの高速無線LANシステムやディジタル放送システムなどの誤り訂正符号化方式に採用されている。
ＬＤＰＣ符号は、低密度なパリティ検査行列Ｈで定義される誤り訂正符号である。また、ＬＤＰＣ符号は、検査行列Ｈの列数Ｎと等しいブロック長を持つブロック符号である。（非特許文献１、非特許文献２、非特許文献３）例えば、ランダム的なＬＤＰＣ符号、ＡＱＣ−ＬＤＰＣ符号（ＱＣ:Quasi-Cyclic）が提案されている。
【０００３】
しかし、現在の通信システムの多くは、イーサネット（登録商標）のように、送信情報を、可変長のパケットやフレーム毎にまとめて伝送するという特徴がある。このようなシステムにブロック符号であるＬＤＰＣ符号を適用する場合、例えば、可変長なイーサネット（登録商標）のフレームに対して固定長のＬＤＰＣ符号のブロックをどのように対応させるかといった課題が生じる。IEEE802.11nでは、送信情報系列にパディング処理やパンクチャ処理を施すことで、送信情報系列の長さと、ＬＤＰＣ符号のブロック長の調節を行っているが、パディングやパンクチャによって、符号化率が変化したり、冗長な系列を送信したりすることを避けることは困難である。
【０００４】
このようなブロック符号のＬＤＰＣ符号（以降、これをＬＤＰＣ−ＢＣ：Low-Density Parity-Check Block Codeと標記する）に対して、任意の長さの情報系列に対しての符号化・復号化が可能なＬＤＰＣ−ＣＣ（Low-Density Parity-Check Convolutional Codes）の検討が行われている（例えば、非特許文献４、非特許文献５参照）。
ＬＤＰＣ−ＣＣは，低密度なパリティ検査行列により定義される畳み込み符号であり，例えば符号化率Ｒ＝１／２（＝ｂ／ｃ）のＬＤＰＣ−ＣＣのパリティ検査行列ＨＴ［０，ｎ］は、図１で示される。ここで、ＨＴ［０，ｎ］の要素ｈ１（ｍ）（ｔ）は、０または１をとる。また、ｈ１（ｍ）（ｔ）以外の要素は全て０である。ＭはＬＤＰＣ−ＣＣにおけるメモリ長、ｎはＬＤＰＣ−ＣＣの符号語の長さを表す。図１に示されるように、ＬＤＰＣ−ＣＣの検査行列は行列の対角項とその近辺の要素にのみに１が配置されており、行列の左下及び右上の要素はゼロであり、平行四辺形型の行列であるという特徴がある。
【０００５】
ここで，ｈ１（０）（ｔ）＝１，ｈ２（０）（ｔ）＝１であるとき、検査行列ＨＴ［０，ｎ］Ｔで定義されるＬＤＰＣ−ＣＣの符号化器は図２で表される。図２に示すように、ＬＤＰＣ−ＣＣの符号化器は、ビットレングスｃのＭ＋１個のシフトレジスタ２０１とｍｏｄ２加算（排他的論理和演算）器２０２で構成される。このため、ＬＤＰＣ−ＣＣの符号化器には、生成行列の乗算を行う回路や後退（前方）代入法に基づく演算を行うＬＤＰＣ−ＢＣの符号化器に比べ、非常に簡易な回路で実現することができるという特徴がある。また、図２は畳み込み符号の符号化器であるため、情報系列を固定長のブロックに区切って符号化する必要はなく、任意の長さの情報系列を符号化することができる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】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.
【非特許文献３】M. P. C. Fossorier, “Quasi-cyclic low-density parity-check codes from circulant permutation matrices,” IEEE Trans. Inform. Theory, vol.50, no.8, pp.1788-1793, Nov. 2001.
【非特許文献４】A. J. Feltstrom, and K. S. Zigangirov, “Time-varying periodic convolutional codes with low-density parity-check matrix,” IEEE Trans. Inform. Theory, vol.45, no.6, pp.2181-2191, Sep. 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.
【非特許文献６】H. H. Ma, and J. K. Wolf, “On tail biting convolutional codes,” IEEE Trans. Commun., vol.com-34, no.2, pp.104-111, Feb. 1986.
【非特許文献７】C. Weib, C. Bettstetter, and S. Riedel, “Code construction and decoding of parallel concatenated tail-biting codes,” IEEE Trans. Inform. Theory, vol.47, no.1, pp.366-386, Jan. 2001.
【非特許文献８】M. B. S. Tavares, K. S. Zigangirov, and G. P. Fettweis, “Tail-biting LDPC convolutional codes,” Proc. of IEEE ISIT 2007, pp.2341-2345, June 2007.
【非特許文献９】Y. Murakami, S.  Okamura, S. Okasaka, T. Kishigami, and M. Orihashi, “LDPC convolutional codes based on parity check polynomials with a time period of 3,” IEICE Trans. Fundamentals, vol.E-92, no.10, pp.-, Oct. 2009.
【非特許文献１０】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.
【非特許文献１２】J. Zhang, and M. P. C. Fossorier, “Shuffled iterative decoding,” IEEE Trans. Commun., vol.53, no.2, pp.209-213, Feb. 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、ＬＤＰＣ−ＣＣに関するテイルバイティングに関する発明である。非特許文献６、７、８には畳み込み符号、あるいは、ＬＤＰＣ−ＣＣのテイルバイティング方法が示されている。これらの非特許文献から、フィードバックのない畳み込み符号（フィードフォワードの畳み込み符号）では、２度の符号化を行うことで、テイルバイティングを行ったときの符号化系列を求められることが示されている。
【０００８】
また、非特許文献８には、ＬＤＰＣ−ＣＣにおいて、テイルバイティングを行ったときのパリティ検査行列の構成が示されている。ＬＤＰＣ−ＣＣにおいても、フィードバックのない符号構成の場合、テイルバイティングを行ったときの符号化系列を求めるのは、比較的容易である。しかし、フィードバックありのＬＤＰＣ−ＣＣ（畳み込み符号）の場合、特に、拘束長が増大するとテイルバイティングを行うのが回路規模という点から難しく、何らか回路規模を削減できる新しいテイルバイティング方法の開発は重要となる。ここで、フィードバックありのＬＤＰＣ−ＣＣとは、ＬＤＰＣ（Low Density Parity Check）畳み込み符号を用いた符号化方法であって、送信する情報ビット系列をＸ１、Ｘ２、・・・、Ｘｎとし、前記情報ビットに対応して前記ＬＤＰＣ畳み込み符号の符号化により付加されるパリティビット系列をＰ１、Ｐ２、・・・、Ｐｎとし、前記情報ビットと前記パリティビットからなる符号化系列をｕ＝（Ｘ１、Ｘ２、・・・、Ｘｎ、Ｐ１、Ｐ２、・・・、Ｐｎ）とし、ＨｕＴ＝０を満たす前記ＬＤＰＣ畳み込み符号のパリティ検査行列をＨとすると、前記ＬＤＰＣ畳み込み符号のパリティ検査行列Ｈの少なくとも１つの行において、符号化系列ｕにおいてパリティビット系列に対応する位置の前記行の要素のうち「１」の値を有する要素の数が２以上あるパリティ検査行列Ｈを用いる符号化方法のことである。
【０００９】
本発明の目的は、フィードバックありのＬＤＰＣ−ＣＣにおいて、従来よりも演算規模を低減する新しいテイルバイティング方法を提供することであり、その際の符号化方法、復号化方法及び符号化器、復号化器に関するものである。
【課題を解決するための手段】
【００１０】
本発明に係る符号化器は、ＬＤＰＣ（Low Density Parity Check）畳み込み符号を用いた符号化を実行する符号化器であって、送信する情報ビット系列をＸ１、Ｘ２、・・・、Ｘｎとし、当該情報ビットに対応して前記ＬＤＰＣ畳み込み符号により付加されるパリティビット系列をＰ１、Ｐ２、・・・、Ｐｎとし、前記情報ビット系列と前記パリティビット系列とからなる符号化系列をｕ＝（Ｘ１、Ｘ２、・・・、Ｘｎ、Ｐ１、Ｐ２、・・・、Ｐｎ）とし、ＨｕＴ＝０（ｕＴは符号化系列ｕの転置行列）を満たす前記ＬＤＰＣ畳み込み符号のパリティ検査行列をＨとすると、前記ＬＤＰＣ畳み込み符号のパリティ検査行列Ｈの少なくとも一つの行において、前記符号化系列ｕにおいてパリティビット系列に対応する位置の前記行の要素のうち「１」を有する要素の数が２以上であり、前記パリティ検査行列Ｈは、ガウスの消去法を用いることで、サブ行列Ａ、Ｂ、Ｃ、Ｄ、Ｅにより、
【００１１】
【数１】
2011146899.tif 000003
【００１２】
として表される変形行列ＨＧに変形することができ、前記サブ行列Ａ及び前記サブ行列Ｄの列数は前記情報ビット系列の数に等しく、前記サブ行列Ｂの列数と前記サブ行列Ｃの列数との合計は、前記サブ行列Ｄの列数と等しくかつ前記パリティビット系列の数に等しく、前記サブ行列Ｂは単位行列であり、前記サブ行列Ｄはゼロ行列であり、前記Ｈ又は前記ＨＧに基づいて、前記情報ビット系列から前記パリティビット系列を生成することを特徴とする。
【００１３】
本発明の復号化器は、ＬＤＰＣ（Low Density Parity Check）畳み込み符号を用いた符号化により生成される符号化系列に基づく送信系列を受信して復号する復号化器であって、送信する情報ビット系列をＸ１、Ｘ２、・・・、Ｘｎとし、当該情報ビットに対応して前記ＬＤＰＣ畳み込み符号により付加されるパリティビット系列をＰ１、Ｐ２、・・・、Ｐｎとし、前記情報ビット系列と前記パリティビット系列とからなる符号化系列をｕ＝（Ｘ１、Ｘ２、・・・、Ｘｎ、Ｐ１、Ｐ２、・・・、Ｐｎ）とし、ＨｕＴ＝０（ｕＴは符号化系列ｕの転置行列）を満たす前記ＬＤＰＣ畳み込み符号のパリティ検査行列をＨとすると、前記ＬＤＰＣ畳み込み符号のパリティ検査行列Ｈの少なくとも一つの行において、前記符号化系列ｕにおいてパリティビット系列に対応する位置の前記行の要素のうち「１」を有する要素の数が２以上であり、前記パリティ検査行列Ｈは、ガウスの消去法を用いることで、サブ行列Ａ、Ｂ、Ｃ、Ｄ、Ｅにより、
【００１４】
【数２】
2011146899.tif 000004
【００１５】
として表される変形行列ＨＧに変形することができ、前記サブ行列Ａ及び前記サブ行列Ｄの列数は前記情報ビット系列の数に等しく、前記サブ行列Ｂの列数と前記サブ行列Ｃの列数との合計は、前記サブ行列Ｄの列数と等しくかつ前記パリティビット系列の数に等しく、前記サブ行列Ｂは単位行列であり、前記サブ行列Ｄはゼロ行列であり、前記符号化は、前記Ｈ又は前記ＨＧに基づいて、前記情報ビット系列から前記パリティビット系列を生成するものであり、前記送信系列は、前記符号化系列ｕから、送信側と受信側で予め既知の値として扱うと定められている値を除いたものであり、前記復号化器は、受信した信号から得られた送信系列それぞれにおける対数尤度比に、前記既知の値に相当する対数尤度比を挿入し、前記パリティ検査行列Ｈを用いて信頼度伝播復号を行うことを特徴とする。
【００１６】
本発明のテイルバイティングを用いた符号化方法は、符号化が容易となるパリティ検査行列をもつテイルバイティング後のＬＤＰＣ−ＣＣを生成することで、容易に符号化系列を得るものとした。
【発明の効果】
【００１７】
本発明のテイルバイティングを用いた符号化方法、復号化方法及び符号化器、復号化器によれば、容易に符号化系列を得ることができるＬＤＰＣ−ＣＣを実現することができる。
【図面の簡単な説明】
【００１８】
【図１】ＬＤＰＣ−ＣＣの検査行列を示す図である。
【図２】ＬＤＰＣ−ＣＣ符号化器の構成を示す図である。
【図３】時変周期ｑのＬＤＰＣ−ＣＣの検査行列の構成の一例を示す図である。
【図４】テイルバイティングを行ったときのパリティ検査行列の例である。
【図５】テイルバイティングを行ったときのパリティ検査行列の例である。
【図６】送信装置及び受信装置の構成例である。
【図７】テイルバイティングを行ったときのパリティ検査行列の一例である。
【図８】ガウスの消去法を用いパリティ検査行列を変形した行列の一例である。
【図９】テイルバイティングを行ったときのパリティ検査行列の一例である。
【図１０】ガウスの消去法を用いパリティ検査行列を変形した行列の一例である。
【図１１】本実施の形態におけるガウスの消去法を用いパリティ検査行列を変形した行列の一例である。
【図１２】送信装置及び受信装置の構成例である。
【図１３】本実施の形態におけるガウスの消去法を用いパリティ検査行列を変形した行列の一例である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。
先ず、一例として、実施の形態の具体的な構成及び動作を説明する前に、非特許文献９に記載されているパリティ検査多項式に基づくＬＤＰＣ−ＣＣについて説明する。
パリティ検査多項式に基づく、符号化率R=(n-1)/nの時変ＬＤＰＣ−ＣＣについて説明する。X1, X2,・・・, Xn-1の情報ビット、及びパリティビットPの時点ｊにおけるビットをそれぞれX1,j, X2,j,・・・, Xn-1,j 及びPjと表す。そして、時点ｊにおけるベクトルujをuj=(X1,j,X2,j,・・・,Xn-1,j,Pj)と表す。また、符号化系列をu=(u0, u1,・・・, uj,・・・)Tと表す。Dを遅延演算子とすると、情報ビットX1, X2,・・・, Xn-1の多項式はX1(D), X2(D),・・・, Xn-1(D)と表され、パリティビットPの多項式はP(D)と表される。このとき、式（１）で表される０を満たすパリティ検査多項式を考える。
【００２０】
【数３】
2011146899.tif 000005
【００２１】
式（１）においてap,q (p=1,2,・・・,n-1 ; q=1,2,・・・,rp)及びbs (s=1,2,・・・,ε) は自然数とする。また、y, z=1,2,・・・,rp 、y≠zの∀(y,z)に対して、ap,y≠ap,zを満たす。また、y, z=1,2,・・・,ε 、 y≠zの∀(y,z) に対して、by≠bzを満たす。
符号化率R=(n-1)/n、時変周期mのＬＤＰＣ−ＣＣを作成するために、式（１）に基づく０を満たすパリティ検査多項式を用意する。このときi番目(i=0,1,・・・,m-1)の０を満たすパリティ検査多項式を式（２）のように表す。
【００２２】
【数４】
2011146899.tif 000006
【００２３】
式（２）において、AXδ,i(D) (δ=1,2,・・・,n-1)及びBi(D)のDの最大次数をそれぞれΓXd,i及びΓP,iと表す。そして、ΓXδ,i及びΓP,iの最大値をΓiとする。そして、Γi (i=0,1,・・・,m-1)の最大値をΓとする。符号化系列uを考慮すると、Γを用いると、i番目のパリティ検査多項式に相当するベクトルhiは式（３）のように表される。 
【００２４】
【数５】
2011146899.tif 000007
【００２５】
式（３）において、hi,v (v=0,1,・・・,Γ)は1×nのベクトルであり、[αi,v,X1, αi,v,X2,・・・, αi,v,Xn-1, βi,v]と表される。なぜなら、式（２）のパリティ検査多項式は、αi,v,XwDvXw(D)及びβi,vDvP(D) (w=1,2,・・・,n-1 and αi,v,Xw, βi,v ∈[0,1])をもつからである。この場合、式（２）の０を満たすパリティ検査多項式は、D0X1(D), D0X2(D),・・・, D0Xn-1(D)及びD0P(D)をもつので、
【００２６】
【数６】
2011146899.tif 000008
【００２７】
を満たす。 式（３）を用いることにより、符号化率R=(n-1)/n、時変周期mのパリティ検査多項式に基づくＬＤＰＣ−ＣＣの検査行列は、式（４）のように表される。 
【００２８】
【数７】
2011146899.tif 000009
【００２９】
式（４）において、∀ kに対して、Λ(k)=Λ(k+m)を満たす。ただし、Λ(k)はパリティ検査行列kの行目におけるhiに相当する。
上述では、ベースとなるパリティ検査多項式として、式（１）を取り扱っているが、必ずしも式（１）の形態に限らず、例えば、式（１）のかわりに、式（５）のような０を満たすパリティ検査多項式としてもよい。
【００３０】
【数８】
2011146899.tif 000010
【００３１】
式（５）においてap,q (p=1,2,・・・,n-1 ; q=1,2,・・・,rp)及びbs (s=1,2,・・・,ε) は自然数とする。また、y, z=1,2,・・・,rp 、y≠zの∀(y,z)に対して、ap,y≠ap,zを満たす。また、y, z=1,2,・・・,ε 、 y≠zの∀(y,z) に対して、by≠bzを満たす。
以下では、上述のパリティ検査多項式に基づく時変ＬＤＰＣ−ＣＣを例に、本提案の新しいテイルバイティング方法について説明する。
【００３２】
（実施の形態１）
上述で説明したパリティ検査多項式に基づくＬＤＰＣ−ＣＣにおいて、時変周期ｑの０を満たすｇ番目（ｇ＝０、１、・・・、ｑ−１）のパリティ検査多項式（式（２）参照）を式（６）のように表す。
【００３３】
【数９】
2011146899.tif 000011
【００３４】
ａ＃ｇ，ｐ，１、ａ＃ｇ，ｐ，２は自然数とし、ａ＃ｇ，ｐ，１≠ａ＃ｇ，ｐ，２、が成立するものとする。また、ｂ＃ｇ，１、ｂ＃ｇ，２は自然数とし、ｂ＃ｇ，１≠ｂ＃ｇ，２が成立するものとする（ｇ＝０、１、２、・・・、ｑ−１；ｐ＝１、２、・・・、ｎ―１）。簡単のため、Ｘ１（Ｄ）、Ｘ２（Ｄ）、・・・Ｘｎ−１（Ｄ）及びＰ（Ｄ）の数は３にする。式（６）のサブ行列（ベクトル）をＨｇとすると、第ｇサブ行列は、
【００３５】
【数１０】
2011146899.tif 000012
【００３６】
と表すことができる。（ｎ個連続した「１」は、式（６）の各式におけるＸ１（Ｄ）、Ｘ２（Ｄ）、・・・Ｘｎ−１（Ｄ）及びＰ（Ｄ）の項に相当する。）すると、パリティ検査行列Ｈは、図３のように表すことができる。図３に示すように、パリティ検査行列Ｈにおいて、第ｉ行と第ｉ＋１行とでは、サブ行列がｎ列右にシフトした構成となる（図３参照）。また、第ｉ＋１行と第ｉ行とでは、サブ行列がｎ列右にシフトした構成となる。そして、情報Ｘ１、Ｘ２、・・・Ｘｎ−１及びパリティＰの時点ｋにおけるデータをそれぞれＸ１，ｋ、Ｘ２，ｋ、・・・、Ｘｎ−１，ｋ、Ｐｋとする。すると、送信ベクトルｕは、ｕ＝（Ｘ１，０、Ｘ２，０、・・・、Ｘｎ−１，０、Ｐ０、Ｘ１，１、Ｘ２，１、・・・、Ｘｎ−１，１、Ｐ１、・・・、Ｘ１，ｋ、Ｘ２，ｋ、・・・、Ｘｎ−１，ｋ、Ｐｋ、・・・・）Ｔと表され、Ｈｕ＝０が成立する。
【００３７】
非特許文献８において、テイルバイティングを行ったときの検査行列が記載されている。パリティ検査行列は以下のとおりである。 
【００３８】
【数１１】
2011146899.tif 000013
【００３９】
式（７）において、Hは検査行列であり、HTはシンドロームフォーマーである。また、HTi(t) (i=0,1,・・・,Ms)はc×(c-b)のサブ行列、Msはメモリサイズである。
図３と式（７）から、パリティ検査多項式に基づく時変周期ｑ、符号化率（ｎ−１）／ｎのＬＤＰＣ−ＣＣにおいて、より高い誤り訂正能力を得るために、復号の際に必要とするパリティ検査行列Ｈでは、以下の条件が重要となる。
＜条件＃１＞
・パリティ検査行列の行数は、ｑの倍数である。
・したがって、パリティ検査行列の列数はｎ×ｑの倍数である。このとき、復号時に必要な（例えば）対数尤度比は、ｎ×ｑの倍数のビット分の対数尤度比である。
【００４０】
ただし、条件＃１が必要となる時変周期ｑ、符号化率（ｎ−１）／ｎのＬＤＰＣ−ＣＣの０を満たすパリティ検査多項式は、式（６）に限ったものではなく、式（１）、式（５）に基づく時変ＬＤＰＣ−ＣＣであってもよい。
ところで、パリティ検査多項式において、パリティＰ（Ｄ）の項が一つしか存在しない場合、式（６）は、 
【００４１】
【数１２】
2011146899.tif 000014
【００４２】
と表され、その時変周期ＬＤＰＣ−ＣＣはフィードフォワードの畳み込み符号の一種であるので、テイルバイティングを行ったときの符号化方法は、非特許文献６、非特許文献７に示されている符号化方法が適用できる。その手順は以下の通りである。
＜手順１＞
例えば、式（８）で定義される時変ＬＤＰＣ−ＣＣでは、Ｐ（Ｄ）は以下のように表され、
【００４３】
【数１３】
2011146899.tif 000015
【００４４】
そして、式（９）を以下のように表される。
【００４５】
【数１４】
2011146899.tif 000016
【００４６】
ただし、式（１０）において、○の中に＋を記載している記号は排他的論理和を示している。したがって、時点ｉにおいて、（ｉ―１）％ｑ＝ｋのとき（％はモジュラ演算（modulo）を示す。）、式（９）、式（１０）において、ｇ＝ｋとして時点ｉのパリティを求めることができる。そして、レジスタの初期値を「０」とする。つまり、式（１０）を用い、時点ｉにおいて（ｉ＝１、２、・・・）、（ｉ―１）％ｑ＝ｋのとき、式（１０）において、ｇ＝ｋとして時点ｉのパリティを求める。そして、式（１０）のＸ１［ｚ］、Ｘ２［ｚ］、・・・、Ｘｎ−１［ｚ］、Ｐ［ｚ］において、ｚが１より小さい場合は、「０」であるものとし、式（１０）を用いて符号化を行うことになる。そして、最後のパリティビットまで求める。そして、このときの符号化器におけるレジスタの状態を保持しておく。
＜手順２＞
手順１の保持しているレジスタの状態から（したがって、式（１０）のＸ１［ｚ］、Ｘ２［ｚ］、・・・、Ｘｎ−１［ｚ］、Ｐ［ｚ］において、ｚが１より小さい場合について、手順１で得られている値を用いることになる。）、再度、時点ｉ＝１から符号化を行い、パリティを求める。
【００４７】
このとき得られたパリティと情報ビットが、テイルバイティングを行ったときの符号化系列となる。
しかし、フィードフォワード型のＬＤＰＣ−ＣＣとフィードバックありのＬＤＰＣ−ＣＣを比較すると、同一符号化率、ほぼ同等の拘束長の条件の下で比較すると、フィードバックありのＬＤＰＣ−ＣＣの方が、高い誤り訂正能力を示す傾向が強いが、符号化系列を求める（パリティを求める）のが困難であるという課題がある。以下では、この課題に対し、容易に符号化系列（パリティ）を求めることを可能とする新しいテイルバイティング方法を提案する。
【００４８】
まず、パリティ検査多項式に基づくＬＤＰＣ−ＣＣにおけるテイルバイティングを行った際のパリティ検査行列について説明する。
例えば、式（６）で定義する、符号化率（ｎ−１）／ｎ、時変周期ｑのパリティ検査多項式に基づくＬＤＰＣ−ＣＣにおいて、時点ｉにおける情報Ｘ１、Ｘ２、・・・、Ｘｎ−１、及びパリティＰをＸ１，ｉ、Ｘ２，ｉ、・・・、Ｘｎ−１，ｉ、Ｐｉと表す。すると、＜条件＃１＞を満たすためには、ｉ＝１、２、３、・・・、ｑ、・・・、ｑ×Ｎ―ｑ＋１、ｑ×Ｎ―ｑ＋２、ｑ×Ｎ―ｑ＋３、・・・、ｑ×Ｎとしてテイルバイティングを行うことになる。（このときの、Ｎは自然数であり、送信系列ｕはｕ＝（Ｘ１，１、Ｘ２，１、・・・、Ｘｎ−１，１、Ｐ０、Ｘ１，２、Ｘ２，２、・・・、Ｘｎ−１，２、Ｐ２、・・・、Ｘ１，ｋ、Ｘ２，ｋ、・・・、Ｘｎ−１，ｋ、Ｐｋ、・・・、Ｘ１，ｑ×Ｎ、Ｘ２，ｑ×Ｎ、・・・、Ｘｎ−１，ｑ×Ｎ、Ｐｑ×Ｎ）Ｔとなり、Ｈｕ＝０が成立する。）このときのパリティ検査行列の構成について図４及び図５を用いて説明する。
【００４９】
式（６）のサブ行列（ベクトル）をＨｇとすると、第ｇサブ行列は、 
【００５０】
【数１５】
2011146899.tif 000017
【００５１】
と表すことができる。（ｎ個連続した「１」は、式（６）の各式におけるＸ１（Ｄ）、Ｘ２（Ｄ）、・・・Ｘｎ−１（Ｄ）及びＰ（Ｄ）の項に相当する。）  上記で定義した送信系列ｕに対応するパリティ検査行列のうち、時点ｑ×Ｎ近辺のパリティ検査行列を図４に示す。図４に示すように、パリティ検査行列Ｈにおいて、第ｉ行と第ｉ＋１行とでは、サブ行列がｎ列右にシフトした構成となる（図４参照）。
【００５２】
また、図４において、４０１はパリティ検査行列のｑ×Ｎ行（最後の行）を示しており、＜条件＃１＞を満たしているためｑ−１番目の０を満たすパリティ検査多項式に相当する。４０２はパリティ検査行列のｑ×Ｎ―１行を示しており、＜条件＃１＞を満たしているためｑ−２番目の０を満たすパリティ検査多項式に相当する。４０３は時点ｑ×Ｎに相当する列群を示しており、４０３の列群は、Ｘ１，ｑ×Ｎ、Ｘ２，ｑ×Ｎ、・・・、Ｘｎ−１，ｑ×Ｎ、Ｐｑ×Ｎの順に並んでいる。４０４は時点ｑ×Ｎ―１に相当する列群を示しており、４０４の列群は、Ｘ１，ｑ×Ｎ―１、Ｘ２，ｑ×Ｎ―１、・・・、Ｘｎ−１，ｑ×Ｎ―１、Ｐｑ×Ｎ―１の順に並んでいる。
【００５３】
次に、送信系列の順番を入れ替え、ｕ＝（・・・、Ｘ１，ｑ×Ｎ―１、Ｘ２，ｑ×Ｎ―１、・・・、Ｘｎ−１，ｑ×Ｎ―１、Ｐｑ×Ｎ―１、Ｘ１，ｑ×Ｎ、Ｘ２，ｑ×Ｎ、・・・、Ｘｎ−１，ｑ×Ｎ、Ｐｑ×Ｎ、Ｘ１，０、Ｘ２，１、・・・、Ｘｎ−１，１、Ｐ１、Ｘ１，２、Ｘ２，２、・・・、Ｘｎ−１，２、Ｐ２、・・・）Ｔに対応するパリティ検査行列のうち時点ｑ×Ｎ―１、ｑ×Ｎ、１、２近辺のパリティ検査行列を図５に示す。このとき、図５で示したパリティ検査行列の部分が、テイルバイティングを行ったときの特徴的な部分となり、この構成は式（７）と同様の構成となることがわかる。図５に示すように、パリティ検査行列Ｈにおいて、第ｉ行と第ｉ＋１行とでは、サブ行列がｎ列右にシフトした構成となる（図５参照）。また、図５において、５０５は図４のようにパリティ検査行列をあらわした場合、ｑ×Ｎ×ｎ列目に相当する列となり、５０６は図４のようにパリティ検査行列をあらわした場合、１列目に相当する列となる。
【００５４】
５０７は時点ｑ×Ｎ―１に相当する列群を示しており、５０７の列群は、Ｘ１，ｑ×Ｎ―１、Ｘ２，ｑ×Ｎ―１、・・・、Ｘｎ−１，ｑ×Ｎ―１、Ｐｑ×Ｎ―１の順に並んでいる。５０８は時点ｑ×Ｎに相当する列群を示しており、５０８の列群は、Ｘ１，ｑ×Ｎ、Ｘ２，ｑ×Ｎ、・・・、Ｘｎ−１，ｑ×Ｎ、Ｐｑ×Ｎの順に並んでいる。５０９は時点１に相当する列群を示しており、５０９の列群は、Ｘ１，１、Ｘ２，１、・・・、Ｘｎ−１，１、Ｐ１の順に並んでいる。５１０は時点２に相当する列群を示しており、５１０の列群は、Ｘ１，２、Ｘ２，２、・・・、Ｘｎ−１，２、Ｐ２の順に並んでいる。
【００５５】
４１１は図４のようにパリティ検査行列をあらわした場合、ｑ×Ｎ行目に相当する行となり、４１２は図４のようにパリティ検査行列をあらわした場合、１行目に相当する行となる。
そして、テイルバイティングを行ったときのパリティ検査行列の特徴的な部分は、図５において、５１３より左かつ５１４より下の部分となる（式（７）参照）。
【００５６】
図４のようにパリティ検査行列をあらわした場合、＜条件＃１＞を満たした場合、行は、０番目の０を満たすパリティ検査多項式に相当する行からはじまり、ｑ−１番目の０を満たすパリティ検査多項式に相当する行で終わる。この点が、より高い誤り訂正能力を得る上で重要となる。実際、時変ＬＤＰＣ−ＣＣは、タナーグラフで短い長さのサイクル（cycle of length）の数が少なくなるように符号を設計する。ここで、テイルバイティングを行ったとき、タナーグラフで短い長さのサイクルの数が少なくなるためには、図５のように記載すると明らかなように、図５のような状況が確保できること、つまり、＜条件＃１＞が重要な要件となる。
【００５７】
ただし、通信システムにおいて、テイルバイティングを行う際、システムで求められるブロック長（または情報長）に対し、＜条件＃１＞を満たすようにするために、工夫が必要となる場合がある。この点について、例をあげて説明する。
図６は、通信システムの略図である。通信システムは、送信装置６００と受信装置６１０とを含んで構成される。
【００５８】
送信装置６００は、符号化器６０１と変調部６０２とを含んで構成される。符号化器６０１は、情報を入力とし、符号化を行い、送信系列を生成し、出力する。そして、変調部６０２は、送信系列を入力とし、マッピング、直交変調、周波数変換、増幅等の所定の処理を行い、送信信号を出力する。送信信号は、通信媒体（無線、電力線、光など）を介して、受信装置に届く。
【００５９】
受信装置６１０は、受信部６１１と、対数尤度比生成部６１２と、復号化器６１３とを含んで構成される。受信部６１１は、受信信号を入力とし、増幅、周波数変換、直交復調、チャネル推定、デマッピング等の処理を施し、ベースバンド信号、及び、チャネル推定信号を出力する。対数尤度比生成部６１２は、ベースバンド信号、及び、チャネル推定信号を入力とし、ビット単位の対数尤度比を生成し、対数尤度比信号を出力する。復号化器６１３は、対数尤度比信号を入力とし、ここでは、特に、ＢＰ（Belief Propagation）復号（非特許文献１０〜１２参照）を用いた反復復号を行い、推定送信系列、または（及び）、推定情報系列を出力する。
【００６０】
例えば、符号化率１／２、時変周期１２のＬＤＰＣ−ＣＣを考える。このとき、テイルバイティングを行うことを前提し、設定した情報長（符号化長）を１６３８４とする。その情報をＸ１，１、Ｘ１，２、Ｘ１，３、・・・、Ｘ１，１６３８４とする。そして、何も工夫せずに、パリティを求めるとすると、Ｐ１、Ｐ２、Ｐ，３、・・・、Ｐ１６３８４が求まることになる。しかし、送信系列ｕ＝（Ｘ１，１、Ｐ１、Ｘ１，２、Ｐ２、・・・Ｘ１，１６３８４、Ｐ１６３８４）に対してパリティ検査行列を作成しても、＜条件＃１＞を満たさない。したがって、送信系列として、Ｘ１，１６３８５、Ｘ１，１６３８６、Ｘ１，１６３８７、Ｘ１，１６３８８を追加し、Ｐ１６３８５、Ｐ１６３８６、Ｐ１６３８７、Ｐ１６３８８を求めればよい。このとき、符号化器（送信装置）では、例えば、Ｘ１，１６３８５＝０、Ｘ１，１６３８６＝０、Ｘ１，１６３８７＝０、Ｘ１，１６３８８＝０と設定し、符号化を行い、Ｐ１６３８５、Ｐ１６３８６、Ｐ１６３８７、Ｐ１６３８８を求める。ただし、符号化器（送信装置）と復号化器（受信装置）において、Ｘ１，１６３８５＝０、Ｘ１，１６３８６＝０、Ｘ１，１６３８７＝０、Ｘ１，１６３８８＝０と設定したという約束事を共有している場合、Ｘ１，１６３８５、Ｘ１，１６３８６、Ｘ１，１６３８７、Ｘ１，１６３８８を送信する必要はない。
【００６１】
したがって、符号化器は、情報系列Ｘ＝（Ｘ１，１、Ｘ１，２、Ｘ１，３、・・・、Ｘ１，１６３８４、Ｘ１，１６３８５、Ｘ１，１６３８６、Ｘ１，１６３８７、Ｘ１，１６３８８）＝（Ｘ１，１、Ｘ１，２、Ｘ１，３、・・・、Ｘ１，１６３８４、０、０、０、０）を入力とし、系列（Ｘ１，１、Ｐ１、Ｘ１，２、Ｐ２、・・・Ｘ１，１６３８４、Ｐ１６３８４、Ｘ１，１６３８５、Ｐ１６３８５、Ｘ１，１６３８６、Ｐ１６３８６、Ｘ１，１６３８７、Ｐ１６３８７、Ｘ１，１６３８８、Ｐ１６３８８）＝（Ｘ１，１、Ｐ１、Ｘ１，２、Ｐ２、・・・Ｘ１，１６３８４、Ｐ１６３８４、０、Ｐ１６３８５、０、Ｐ１６３８６、０、Ｐ１６３８７、０、Ｐ１６３８８）を得る。そして、符号化器（送信装置）、復号化器（受信装置）で既知である「０」を削減し、送信装置は、送信系列を（Ｘ１，１、Ｐ１、Ｘ１，２、Ｐ２、・・・Ｘ１，１６３８４、Ｐ１６３８４、Ｐ１６３８５、Ｐ１６３８６、Ｐ１６３８７、Ｐ１６３８８）として送信する。
【００６２】
受信装置では、送信系列ごとの、例えば、対数尤度比をＬＬＲ（Ｘ１，１）、ＬＬＲ（Ｐ１）、ＬＬＲ（Ｘ１，２）、ＬＬＲ（Ｐ２）、・・・ＬＬＲ（Ｘ１，１６３８４）、ＬＬＲ（Ｐ１６３８４）、ＬＬＲ（Ｐ１６３８５）、ＬＬＲ（Ｐ１６３８６）、ＬＬＲ（Ｐ１６３８７）、ＬＬＲ（Ｐ１６３８８）を得ることになる。
そして、送信装置で送信しなかった「０」の値のＸ１，１６３８５、Ｘ１，１６３８６、Ｘ１，１６３８７、Ｘ１，１６３８８の対数尤度比ＬＬＲ（Ｘ１，１６３８５）＝ＬＬＲ（０）、ＬＬＲ（Ｘ１，１６３８６）＝ＬＬＲ（０）、ＬＬＲ（Ｘ１，１６３８７）＝ＬＬＲ（０）、ＬＬＲ（Ｘ１，１６３８８）＝ＬＬＲ（０）を生成し、ＬＬＲ（Ｘ１，１）、ＬＬＲ（Ｐ１）、ＬＬＲ（Ｘ１，２）、ＬＬＲ（Ｐ２）、・・・ＬＬＲ（Ｘ１，１６３８４）、ＬＬＲ（Ｐ１６３８４）、ＬＬＲ（Ｘ１，１６３８５）＝ＬＬＲ（０）、ＬＬＲ（Ｐ１６３８５）、ＬＬＲ（Ｘ１，１６３８６）＝ＬＬＲ（０）、ＬＬＲ（Ｐ１６３８６）、ＬＬＲ（Ｘ１，１６３８７）＝ＬＬＲ（０）、ＬＬＲ（Ｐ１６３８７）、ＬＬＲ（Ｘ１，１６３８８）＝ＬＬＲ（０）、ＬＬＲ（Ｐ１６３８８）を得ることになるので、これと符号化率１／２、時変周期１２のＬＤＰＣ−ＣＣの１６３８８×３２７７６のパリティ検査行列を用いて、非特許文献１０、非特許文献１１、非特許文献１２に示されているようなＢＰ（Belief Propagation）（信頼度伝播）復号、ＢＰ復号を近似したmin-sum復号、offset ＢＰ復号、Normalized ＢＰ復号、shuffled ＢＰ復号などの信頼度伝播を利用した復号を行うことで、推定送信系列、及び、推定情報系列を得る。
【００６３】
この例でわかるように、符号化率（ｎ−１）／ｎ、時変周期ｑのＬＤＰＣ−ＣＣにおいて、テイルバイティングを行う場合、受信装置で復号の際、＜条件＃１＞を満たすようなパリティ検査行列をもち、復号を行う。したがって、パリティ検査行列として（行）×（列）＝（ｑ×Ｍ）×（ｑ×ｎ×Ｍ）のパリティ検査行列を復号器は保有していることになる（Ｍは自然数）。
【００６４】
これに対応する符号化器において、符号化に必要となる情報ビット数はｑ×（ｎ−１）×Ｍとなる。これにより、ｑ×Ｍビットのパリティを求めることになる。これに対し、符号化器に入力される情報ビットの数が、ｑ×（ｎ−１）×Ｍビットより少ない場合は、符号化器において、情報ビット数がｑ×（ｎ−１）×Ｍビットとなるように送受信装置（符号化器及び復号化器）間で既知のビット（例えば「０」（「１」でもよい））を挿入する。そして、ｑ×Ｍビットのパリティを求めることになる。このとき、送信器は、挿入した既知のビットを除いた情報ビットと求めたパリティビットを送信する。（ただし、既知のビットを送信し、常に、ｑ×（ｎ−１）×Ｍビットの情報とｑ×Ｍビットのパリティを送信してもよいが、既知ビット送信分の伝送速度の低下を招くことになる。）
次に、提案する新しいテイルバイティング方法について説明する。一例として、符号化率１／２、時変周期３のパリティ検査多項式に基づくＬＤＰＣ−ＣＣを扱い、説明を進める。はじめに、提案するテイルバイティングを適用できない場合について説明する。ＬＤＰＣ−ＣＣのパリティ検査多項式を次式で表す。
【００６５】
０番目のパリティ検査多項式：
【００６６】
【数１６】
2011146899.tif 000018
【００６７】
１番目のパリティ検査多項式：
【００６８】
【数１７】
2011146899.tif 000019
【００６９】
２番目のパリティ検査多項式：
【００７０】
【数１８】
2011146899.tif 000020
【００７１】
そして、時点ｉにおける情報をＸ１，ｉ、パリティをＰｉとする。そして、情報１２ビット、パリティ１２ビットで構成されるブロックでテイルバイティングを行うものとする。したがって、送信系列ｕをｕ＝（Ｘ１，１、Ｘ１，２、Ｘ１，３、Ｘ１，４、Ｘ１，５、Ｘ１，６、Ｘ１，７、Ｘ１，８、Ｘ１，９、Ｘ１，１０、Ｘ１，１１、Ｘ１，１２、Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０、Ｐ１１、Ｐ１２）とする。このとき、パリティ検査行列Ｈとし、ＨｕＴ＝０を満たすＨは、図７のように表される。図７におけるサブ行列７０１は情報Ｘ１に関連するサブ行列であり、サブ行列７０２はパリティＰに関連するサブ行列である。そして、符号化を行う場合、ＨｕＴ＝０の関係を利用し、（未知の値である）パリティＰ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０、Ｐ１１、Ｐ１２を求めることになる。そこで、ＨｕＴ＝０に対し、ガウスの消去法を用いて、ＨｕＴ＝０と等価であるＨＧｕＴ＝０の関係となるＨＧを図８に示す。図８において、サブ行列８０１は情報Ｘ１に関連するサブ行列であり、サブ行列８０２はパリティＰに関連するサブ行列である。このとき、図８から明らかなように、フルランク（行列の行数とランクが等しい）とならない。一般的に、テイルバイティングを行った場合、図８のようなケースとなり、この場合、図８から、Ｐ１１、Ｐ１２を何らかの値に設定し、その後、ＨＧｕＴ＝０の関係から、Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０を求めることになる。
【００７２】
このとき、Ｐ１１、Ｐ１２にどの値に設定しても、必ずＰ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０が求まるというわけではなく、Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０が求まるためのＰ１１、Ｐ１２の値を探索しなければならない。したがって、計算が、非常に複雑となる。
具体的には、
＜１＞Ｐ１１＝０、Ｐ１２＝０として、ＨＧｕＴ＝０の関係から、Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０が求まるかどうか、を調べる。
【００７３】
＜２＞Ｐ１１＝０、Ｐ１２＝１として、ＨＧｕＴ＝０の関係から、Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０が求まるかどうか、を調べる。
＜３＞Ｐ１１＝１、Ｐ１２＝０として、ＨＧｕＴ＝０の関係から、Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０が求まるかどうか、を調べる。
＜４＞Ｐ１１＝１、Ｐ１２＝１として、ＨＧｕＴ＝０の関係から、Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０が求まるかどうか、を調べる。
これらの４つの計算を行い、Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０が求まる場合を探索し、求まった場合の計算結果が、Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０、Ｐ１１、Ｐ１２の値をして定まる。
【００７４】
次に、提案するテイルバイティングの方法について説明する。ＬＤＰＣ−ＣＣのパリティ検査多項式を次式で表す。 
０番目のパリティ検査多項式：
【００７５】
【数１９】
2011146899.tif 000021
【００７６】
１番目のパリティ検査多項式：
【００７７】
【数２０】
2011146899.tif 000022
【００７８】
２番目のパリティ検査多項式：
【００７９】
【数２１】
2011146899.tif 000023
【００８０】
そして、時点ｉにおける情報をＸ１，ｉ、パリティをＰｉとする。そして、情報１２ビット、パリティ１２ビットで構成されるブロックでテイルバイティングを行うものとする。したがって、送信系列ｕをｕ＝（Ｘ１，１、Ｘ１，２、Ｘ１，３、Ｘ１，４、Ｘ１，５、Ｘ１，６、Ｘ１，７、Ｘ１，８、Ｘ１，９、Ｘ１，１０、Ｘ１，１１、Ｘ１，１２、Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０、Ｐ１１、Ｐ１２）とする。このとき、パリティ検査行列Ｈとし、ＨｕＴ＝０を満たすＨは、図９のように表される。図９におけるサブ行列９０１は情報Ｘ１に関連するサブ行列であり、サブ行列９０２はパリティＰに関連するサブ行列である。そして、符号化を行う場合、ＨｕＴ＝０の関係を利用し、（未知の値である）パリティＰ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０、Ｐ１１、Ｐ１２を求めることになる。
【００８１】
そこで、ＨｕＴ＝０に対し、ガウスの消去法を用いて、ＨｕＴ＝０と等価であるＨＧｕＴ＝０の関係となるＨＧを図１０に示す。図１０において、サブ行列１００１は情報Ｘ１に関連するサブ行列であり、サブ行列１００２はパリティＰに関連するサブ行列である。このとき、図１０から明らかなように、フルランク（行列の行数とランクが等しい）とならない。ただし、図８の場合と異なり、サブ行列１００５が０の要素のみで構成されている。この場合、（Ｐ１１，Ｐ１２）を（０，０）、（０，１）、（１，０）、（１，１）いずれの値に設定しても、ＨＧｕＴ＝０を満たすＰ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０が求まる。したがって、（Ｐ１１，Ｐ１２）を例えば、（０，０）と固定的に設定し（（０，１）、（１，０）、（１，１）のいずれかに設定してもよいが、０を既知列として送信時に削除することを考慮すると、（０，０）に固定するのが効果的である。）、ＨＧｕＴ＝０の関係からＰ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０を求めるという従来のテイルバイティング方法より、格段に計算量の少ない符号化器を構成することができる。
【００８２】
次に、提案したテイルバイティング方法について、符号化率１／２、時変周期ｑのＬＤＰＣ−ＣＣを例に説明する。符号化率１／２、時変周期ｑの０を満たすｇ番目（ｇ＝０、１、・・・、ｑ−１）のパリティ検査多項式を式（１７）のように表す。 
【００８３】
【数２２】
2011146899.tif 000024
【００８４】
式（１７）においてa#g,p,q (p=1 ; q=1,2,・・・,r1)及びb#g,s(s=1,2,・・・,ε) は自然数とする。また、y, z=1,2,・・・,rp 、y≠zの∀(y,z)に対して、a#g,p,y≠a#g,p,zを満たす。また、y, z=1,2,・・・,ε 、 y≠zの∀(y,z) に対して、b#g,y≠b#g,zを満たす。
そして、＜条件＃１＞に基づき、テイルバイティングを行ったときのパリティ検査行列を生成する。ここで、符号化率１／２、時変周期ｑとしているので、パリティ検査行列の（行数）×（列数）＝（ｑ×Ｍ）×（２×ｑ×Ｍ）となる。
【００８５】
そして、時点ｉにおける情報をＸ１，ｉ、パリティをＰｉとする。そして、情報ｑ×Ｍビット、パリティｑ×Ｍビットで構成されるブロックでテイルバイティングを行うことになる。したがって、送信系列ｕをｕ＝（Ｘ１，１、Ｘ１，２、・・・、Ｘ１，ｑ×Ｍ―１、Ｘ１，ｑ×Ｍ、Ｐ１、Ｐ２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍ）とする。このとき、ＨｕＴ＝０を満たすパリティ検査行列Ｈを考える。ＨｕＴ＝０に対し、ガウスの消去法を用いて、ＨｕＴ＝０と等価であるＨＧｕＴ＝０の関係となるＨＧを考え、図１１のように表すものとする。このとき、図１１において、サブ行列Ａとサブ行列Ｄで構成されるサブ行列は、情報Ｘ１に関連するサブ行列となり、サブ行列Ｂ、サブ行列Ｃ、及び、サブ行列Ｅで構成されるサブ行列は、パリティＰに関連するサブ行列となる。また、サブ行列Ａは（行数）×（列数）＝（ｑ×Ｍ―ｙ）×（ｑ×Ｍ）、サブ行列Ｂは（行数）×（列数）＝（ｑ×Ｍ―ｙ）×（ｑ×Ｍ―ｙ）、サブ行列Ｃは（行数）×（列数）＝（ｑ×Ｍ―ｙ）×（ｙ）、サブ行列Ｄは（行数）×（列数）＝（ｙ）×（ｑ×Ｍ）、サブ行列Ｅは（行数）×（列数）＝（ｙ）×（ｑ×Ｍ）となる。
【００８６】
そして、提案したテイルバイティング方法では、サブ行列Ａは「０」及び「１」で構成される（行数）×（列数）＝（ｑ×Ｍ―ｙ）×（ｑ×Ｍ）のサブ行列であり、サブ行列Ｂは（行数）×（列数）＝（ｑ×Ｍ―ｙ）×（ｑ×Ｍ―ｙ）の単位行列となる。そして、サブ行列Ｃは「０」及び「１」で構成される（行数）×（列数）＝（ｑ×Ｍ―ｙ）×（ｙ）のサブ行列であり、サブ行列Ｄは「０」のみで構成される（行数）×（列数）＝（ｙ）×（ｑ×Ｍ）のゼロ行列であり、サブ行列Ｅは「０」のみで構成される（行数）×（列数）＝（ｙ）×（ｑ×Ｍ）のゼロ行列である。
【００８７】
そして、パリティＰ１、Ｐ２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×ＭのうちＰｑ×Ｍ―ｙ＋１、Ｐｑ×Ｍ―ｙ＋２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍを固定値、例えば、Ｐｑ×Ｍ―ｙ＋１、Ｐｑ×Ｍ―ｙ＋２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍのすべてを「０」（ただし、これに限ったものではない。）を与え、Ｐ１、Ｐ２、・・・、Ｐｑ×Ｍ―ｙ―１、Ｐｑ×Ｍ―ｙを求める。以上により、送信系列ｕ＝（Ｘ１，１、Ｘ１，２、・・・、Ｘ１，ｑ×Ｍ―１、Ｘ１，ｑ×Ｍ、Ｐ１、Ｐ２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍ）がすべて決定することになる。
【００８８】
図１２は、本実施の形態における通信システムの概略を示している。通信システムは、送信装置１２００と受信装置１２１０とを含んで構成される。
送信装置１２００は、符号化器１２０１と変調部１２０２と、既知系列発生部１２０３とを含んで構成される。符号化器１２０１は、情報（Ｘ１，１、Ｘ１，２、・・・、Ｘ１，ｑ×Ｍ―１、Ｘ１，ｑ×Ｍ）、及び、既知系列部が発生した既知系列（既知系列の挿入方法については、上記のとおりである。（Ｐｑ×Ｍ―ｙ＋１、Ｐｑ×Ｍ―ｙ＋２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍのすべてを「０」））を入力とし、符号化を行い、送信系列ｕ＝（Ｘ１，１、Ｘ１，２、・・・、Ｘ１，ｑ×Ｍ―１、Ｘ１，ｑ×Ｍ、Ｐ１、Ｐ２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍ）を生成し、このうち、既知系列を削除し、削除後の送信系列ｕ＝（Ｘ１，１、Ｘ１，２、・・・、Ｘ１，ｑ×Ｍ―１、Ｘ１，ｑ×Ｍ、Ｐ１、Ｐ２、・・・、Ｐｑ×Ｍ―ｙ−１、Ｐｑ×Ｍ―ｙ）を生成し、出力する。そして、変調部１２０２は、削除後の送信系列を入力とし、マッピング、直交変調、周波数変換、増幅等の所定の処理を行い、送信信号を出力する。送信信号は、通信媒体（無線、電力線、光など）を介して、受信装置に届く。
【００８９】
受信装置１２１０は、受信部１２１１と、対数尤度比生成部１２１２と、復号化器１２１３と、既知系列用対数尤度比生成部１２１４とを含んで構成される。受信部１２１１は、受信信号を入力とし、増幅、周波数変換、直交復調、チャネル推定、デマッピング等の処理を施し、ベースバンド信号、及び、チャネル推定信号を出力する。対数尤度比生成部１２１２は、ベースバンド信号、及び、チャネル推定信号を入力とし、ビット単位の対数尤度比を生成し、対数尤度比信号を出力する。
【００９０】
復号化器１２１３は、対数尤度比信号、及び、既知系列用対数尤度比発生部１２１４が出力した既知系列の対数尤度比信号（つまり、Ｐｑ×Ｍ―ｙ＋１、Ｐｑ×Ｍ―ｙ＋２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍのすべてを「０」に対応する対数尤度比）を入力とする。これらが入力されることにより、送信系列ｕ＝（Ｘ１，１、Ｘ１，２、・・・、Ｘ１，ｑ×Ｍ―１、Ｘ１，ｑ×Ｍ、Ｐ１、Ｐ２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍ）に対応するすべての対数尤度比、ＬＬＲ（Ｘ１，１）、ＬＬＲ（Ｘ１，２、・・・、ＬＬＲ（Ｘ１，ｑ×Ｍ―１）、ＬＬＲ（Ｘ１，ｑ×Ｍ）、ＬＬＲ（Ｐ１）、ＬＬＲ（Ｐ２）、・・・、ＬＬＲ（Ｐｑ×Ｍ―１）、ＬＬＲ（Ｐｑ×Ｍ）が揃うので、復号化器１９０５は、ＢＰ復号を用いた反復復号を行い、推定送信系列、または（及び）、推定情報系列を出力する。なお、一般的なＢＰ（Belief Propagation）（信頼度伝播）復号の代わりに、非特許文献１０、非特許文献１１、非特許文献１２に示されているようなＢＰ復号、ＢＰ復号を近似したmin-sum復号、offset ＢＰ復号、Normalized ＢＰ復号、shuffled ＢＰ復号などの信頼度伝播を利用した復号を行ってもよい。
【００９１】
ここで重要なことは、通信装置の中で用いる場合、符号化において用いた既知系列は、送信する必要がなく、この系列を送信しないことで、伝送効率が向上する。（送信してもよいが伝送効率の低下を招く。）そして、復号器では、送信しなかった既知系列に相当する対数尤度比を与える必要がある。
次に、提案したテイルバイティング方法について、符号化率（ｎ−１）／ｎ、時変周期ｑのＬＤＰＣ−ＣＣを例に説明する。符号化率（ｎ−１）／ｎ、時変周期ｑの０を満たすｇ番目（ｇ＝０、１、・・・、ｑ−１）のパリティ検査多項式を式（１８）のように表す。
【００９２】
【数２３】
2011146899.tif 000025
【００９３】
式（１８）においてa#g,p,q (p=1,2, ・・・,n-1 ; q=1,2,・・・,rn-1)及びb#g,s (s=1,2,・・・,ε) は自然数とする。また、y, z=1,2,・・・,rp 、y≠zの∀(y,z)に対して、a#g,p,y≠a#g,p,zを満たす。また、y, z=1,2,・・・,ε 、 y≠zの∀(y,z) に対して、b#g,y≠b#g,zを満たす。
そして、＜条件＃１＞に基づき、テイルバイティングを行ったときのパリティ検査行列を生成する。ここで、符号化率（ｎ−１）／ｎ、時変周期ｑとしているので、パリティ検査行列の（行数）×（列数）＝（ｑ×Ｍ）×（ｑ×ｎ×Ｍ）となる。そして、時点ｉにおける情報Ｘ１、Ｘ２、・・・、Ｘｎ−１、及びパリティＰをＸ１，ｉ、Ｘ２，ｉ、・・・、Ｘｎ−１，ｉ、Ｐｉと表す。このとき、情報ｑ×（ｎ―１）×Ｍビット、パリティｑ×Ｍビットで構成されるブロックでテイルバイティングを行うことになる。したがって、送信系列ｕをｕ＝（Ｘ１，１、Ｘ１，２、・・・、Ｘ１，ｑ×Ｍ―１、Ｘ１，ｑ×Ｍ、Ｘ２，１、Ｘ２，２、・・・、Ｘ２，ｑ×Ｍ―１、Ｘ２，ｑ×Ｍ、・・・・・・・・、Ｘｎ−１，１、Ｘｎ−１，２、・・・、Ｘｎ−１，ｑ×Ｍ―１、Ｘｎ−１，ｑ×Ｍ、Ｐ１、Ｐ２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍ）とする。
【００９４】
このとき、ＨｕＴ＝０を満たすパリティ検査行列Ｈを考える。ＨｕＴ＝０に対し、ガウスの消去法を用いて、ＨｕＴ＝０と等価であるＨＧｕＴ＝０の関係となるＨＧを考え、図１３のように表すものとする。このとき、図１３において、サブ行列ＡＸ１とサブ行列ＤＸ１で構成されるサブ行列は、情報Ｘ１に関連するサブ行列となる。同様に、サブ行列ＡＸ２とサブ行列ＤＸ２で構成されるサブ行列は、情報Ｘ２に関連するサブ行列となる。したがって、サブ行列ＡＸｋとサブ行列ＤＸｋで構成されるサブ行列は、情報Ｘｋに関連するサブ行列となる（ｋ＝１、２、・・・、ｎ−１）。
【００９５】
サブ行列Ｂ、サブ行列Ｃ、及び、サブ行列Ｅで構成されるサブ行列は、パリティＰに関連するサブ行列となる。
このとき、サブ行列ＡＸｋは（行数）×（列数）＝（ｑ×Ｍ―ｙ）×（ｑ×Ｍ）、サブ行列Ｂは（行数）×（列数）＝（ｑ×Ｍ―ｙ）×（ｑ×Ｍ―ｙ）、サブ行列Ｃは（行数）×（列数）＝（ｑ×Ｍ―ｙ）×（ｙ）、サブ行列ＤＸｋは（行数）×（列数）＝（ｙ）×（ｑ×Ｍ）、サブ行列Ｅは（行数）×（列数）＝（ｙ）×（ｑ×Ｍ）となる。そして、提案したテイルバイティング方法では、サブ行列ＡＸｋは「０」及び「１」で構成される（行数）×（列数）＝（ｑ×Ｍ―ｙ）×（ｑ×Ｍ）のサブ行列であり、サブ行列Ｂは（行数）×（列数）＝（ｑ×Ｍ―ｙ）×（ｑ×Ｍ―ｙ）の単位行列となる。そして、サブ行列Ｃは「０」及び「１」で構成される（行数）×（列数）＝（ｑ×Ｍ―ｙ）×（ｙ）のサブ行列であり、サブ行列ＤＸｋは「０」のみで構成される（行数）×（列数）＝（ｙ）×（ｑ×Ｍ）のゼロ行列であり、サブ行列Ｅは「０」のみで構成される（行数）×（列数）＝（ｙ）×（ｑ×Ｍ）のゼロ行列である。
【００９６】
そして、パリティＰ１、Ｐ２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×ＭのうちＰｑ×Ｍ―ｙ＋１、Ｐｑ×Ｍ―ｙ＋２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍを固定値、例えば、Ｐｑ×Ｍ―ｙ＋１、Ｐｑ×Ｍ―ｙ＋２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍのすべてを「０」（ただし、これに限ったものではない。）を与え、Ｐ１、Ｐ２、・・・、Ｐｑ×Ｍ―ｙ―１、Ｐｑ×Ｍ―ｙを求める。以上により、送信系列ｕ＝（Ｘ１，１、Ｘ１，２、・・・、Ｘ１，ｑ×Ｍ―１、Ｘ１，ｑ×Ｍ、Ｘ２，１、Ｘ２，２、・・・、Ｘ２，ｑ×Ｍ―１、Ｘ２，ｑ×Ｍ、・・・・・・・・、Ｘｎ−１，１、Ｘｎ−１，２、・・・、Ｘｎ−１，ｑ×Ｍ―１、Ｘｎ−１，ｑ×Ｍ、Ｐ１、Ｐ２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍ）がすべて決定することになる。
【００９７】
図１２は、本実施の形態における通信システムの概略を示している。符号化器９０１は、情報（Ｘ１，１、Ｘ１，２、・・・、Ｘ１，ｑ×Ｍ―１、Ｘ１，ｑ×Ｍ）、情報（Ｘ２，１、Ｘ２，２、・・・、Ｘ２，ｑ×Ｍ―１、Ｘ２，ｑ×Ｍ）、・・・、情報（Ｘｎ−１，１、Ｘｎ−１，２、・・・、Ｘｎ−１，ｑ×Ｍ―１、Ｘｎ−１，ｑ×Ｍ）、及び、既知系列部が発生した既知系列（既知系列の挿入方法については、上記のとおりである。（Ｐｑ×Ｍ―ｙ＋１、Ｐｑ×Ｍ―ｙ＋２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍのすべてを「０」））を入力とし、符号化を行い、送信系列ｕ＝（Ｘ１，１、Ｘ１，２、・・・、Ｘ１，ｑ×Ｍ―１、Ｘ１，ｑ×Ｍ、Ｘ２，１、Ｘ２，２、・・・、Ｘ２，ｑ×Ｍ―１、Ｘ２，ｑ×Ｍ、・・・・・・・・、Ｘｎ−１，１、Ｘｎ−１，２、・・・、Ｘｎ−１，ｑ×Ｍ―１、Ｘｎ−１，ｑ×Ｍ、Ｐ１、Ｐ２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍ）を生成し、このうち、既知系列を削除し、削除後の送信系列ｕ＝（Ｘ１，１、Ｘ１，２、・・・、Ｘ１，ｑ×Ｍ―１、Ｘ１，ｑ×Ｍ、Ｘ２，１、Ｘ２，２、・・・、Ｘ２，ｑ×Ｍ―１、Ｘ２，ｑ×Ｍ、・・・・・・・・、Ｘｎ−１，１、Ｘｎ−１，２、・・・、Ｘｎ−１，ｑ×Ｍ―１、Ｘｎ−１，ｑ×Ｍ、Ｐ１、Ｐ２、・・・、Ｐｑ×Ｍ―ｙ−１、Ｐｑ×Ｍ―ｙ）を生成し、出力する。そして、変調部９０２は、削除後の送信系列を入力とし、マッピング、直交変調、周波数変換、増幅等の所定の処理を行い、送信信号を出力する。送信信号は、通信媒体（無線、電力線、光など）を介して、受信装置に届く。
【００９８】
受信部１２１１は、受信信号を入力とし、増幅、周波数変換、直交復調、チャネル推定、デマッピング等の処理を施し、ベースバンド信号、及び、チャネル推定信号を出力する。対数尤度比生成部１２１２は、ベースバンド信号、及び、チャネル推定信号を入力とし、ビット単位の対数尤度比を生成し、対数尤度比信号を出力する。復号化器１２１３は、対数尤度比信号、及び、既知系列用対数尤度比発生部１２１４が出力した既知系列の対数尤度比信号（つまり、Ｐｑ×Ｍ―ｙ＋１、Ｐｑ×Ｍ―ｙ＋２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍのすべてを「０」に対応する対数尤度比）を入力とする。これにより、送信系列ｕ＝（Ｘ１，１、Ｘ１，２、・・・、Ｘ１，ｑ×Ｍ―１、Ｘ１，ｑ×Ｍ、Ｘ２，１、Ｘ２，２、・・・、Ｘ２，ｑ×Ｍ―１、Ｘ２，ｑ×Ｍ、・・・・・・・・、Ｘｎ−１，１、Ｘｎ−１，２、・・・、Ｘｎ−１，ｑ×Ｍ―１、Ｘｎ−１，ｑ×Ｍ、Ｐ１、Ｐ２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍ）に対応するすべての対数尤度比、ＬＬＲ（Ｘ１，１）、ＬＬＲ（Ｘ１，２）、・・・、ＬＬＲ（Ｘ１，ｑ×Ｍ―１）、ＬＬＲ（Ｘ１，ｑ×Ｍ）、ＬＬＲ（Ｘ２，１）、ＬＬＲ（Ｘ２，２）、・・・、ＬＬＲ（Ｘ２，ｑ×Ｍ―１）、ＬＬＲ（Ｘ２，ｑ×Ｍ）、・・・・・・・・、ＬＬＲ（Ｘｎ−１，１）、ＬＬＲ（Ｘｎ−１，２）、・・・、ＬＬＲ（Ｘｎ−１，ｑ×Ｍ―１）、ＬＬＲ（Ｘｎ−１，ｑ×Ｍ）、ＬＬＲ（Ｐ１）、ＬＬＲ（Ｐ２）、・・・、ＬＬＲ（Ｐｑ×Ｍ―１）、ＬＬＲ（Ｐｑ×Ｍ）が揃うので、復号化器１９０５は、ＢＰ復号を用いた反復復号を行い、推定送信系列、または（及び）、推定情報系列を出力する。なお、一般的なＢＰ（Belief Propagation）（信頼度伝播）復号の代わりに、非特許文献１０、非特許文献１１、非特許文献１２に示されているようなＢＰ復号、ＢＰ復号を近似したmin-sum復号、offset ＢＰ復号、Normalized ＢＰ復号、shuffled ＢＰ復号などの信頼度伝播を利用した復号を行ってもよい。
【００９９】
ここで重要なことは、通信装置の中で用いる場合、符号化において用いた既知系列は、送信する必要がなく、この系列を送信しないことで、伝送効率が向上する。（送信してもよいが伝送効率の低下を招く。）そして、復号器では、送信しなかった既知系列に相当する対数尤度比を与える必要がある。
上記とは別の視点として、Ｐｑ×Ｍ―ｙ＋１、Ｐｑ×Ｍ―ｙ＋２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍで、情報を伝送することもできる。Ｐｑ×Ｍ―ｙ＋１、Ｐｑ×Ｍ―ｙ＋２、・・・、Ｐｑ×Ｍ―１、Ｐｑ×Ｍにより、ｙビットの情報を伝送してもよい。この場合、通信システムでは、既知系列に関連する部分は必要としないので、図６の通信システムのような構成で、装置を実現することができる。
【０１００】
以上のように、本実施の形態のＬＤＰＣ−ＣＣにおけるテイルバイティング方法では、従来のテイルバイティングの方法とは異なり、演算規模（回路規模）が少ない（低複雑度）の符号化器を実現することができるとともに、テイルバイティングで必要とする既知系列を送信しない構成とすることで、データの伝送速度が向上するという効果を得ることができる。
【０１０１】
なお、本実施の形態では、パリティ検査多項式に基づくＬＤＰＣ−ＣＣを例に説明したが、本実施の形態は、このＬＤＰＣ−ＣＣに限って適用可能ということではなく、式（７）で与えられる、時変ＬＤＰＣ−ＣＣ（畳み込み符号）に対し、広く適用することができる。その場合、結局のところ、上述で説明した、図１１、図１３の行列において、行列Ｂが単位行列であり、かつ、行列Ｄ，Ｅ、ＤＸｋが「０」のみで構成される行列が得られることになる。
【０１０２】
本発明は上記全ての実施の形態に限定されず、種々変更して実施することが可能である。例えば、上記実施の形態では、主に、符号化器を実現する場合について説明しているが、これに限られるものではなく、通信装置で実現する場合においても適用可能である。（ＬＳＩ（：Large Scale Integration）により構成することも可能である。）
また、この符号化方法及び復号化方法をソフトウェアとして行うことも可能である。例えば、上記符号化方法及び通信方法を実行するプログラムを予めＲＯＭ（Read Only Memory）に格納しておき、そのプログラムをＣＰＵ（Central Processor Unit）によって動作させるようにしても良い。
【０１０３】
また、上記符号化方法を実行するプログラムをコンピュータで読み取り可能な記憶媒体に格納し、記憶媒体に格納されたプログラムをコンピュータのＲＡＭ（Random Access Memory）に記録して、コンピュータをそのプログラムにしたがって動作させるようにしても良い。
また、本発明は、無線通信に限らず、電灯線通信（ＰＬＣ：Power Line Communication）、可視光通信、光通信においても有用であることは言うまでもない。
【産業上の利用可能性】
【０１０４】
本発明に係る符号化器、及び符号化方法は、ＬＤＰＣ−ＣＣを用いた符号化器において、高い誤り訂正能力を得ることができ、かつ、データの伝送効率を向上させることができる。
【符号の説明】
【０１０５】
６００、１２００  送信装置
６０１、１２０１  符号化器
６０２、１２０２  変調部
１２０３  既知系列発生部
６１０、１２１０  受信装置
６１１、１２１１  受信部
６１２、１２１２  対数尤度比生成部
６１３、１２１３  復号化器
１２１４  既知系列用対数尤度比生成部
【図１】
2011146899.tif 000034
【図２】
2011146899.tif 000035
【図３】
2011146899.tif 000036
【図４】
2011146899.tif 000037
【図５】
2011146899.tif 000038
【図６】
2011146899.tif 000039
【図７】
2011146899.tif 000040
【図８】
2011146899.tif 000041
【図９】
2011146899.tif 000042
【図１０】
2011146899.tif 000043
【図１１】
2011146899.tif 000044
【図１２】
2011146899.tif 000045
【図１３】
2011146899.tif 000046