(57)【特許請求の範囲】
【請求項１】
検査行列によって定義される空間結合ＬＤＰＣ符号を生成する符号化装置であって、
前記検査行列は、情報部とパリティ部とで構成され、
前記情報部は、Ｎ種類のｍ行ｋ列の疎行列を列方向に結合させたＮ・ｍ行ｋ列の疎行列Ｌ個をｍ行ｋ列ずつずらして結合させた、（Ｌ＋Ｎ−１）ｍ行、Ｌ・ｋ列の行列であり、
前記パリティ部は、対角の要素と該対角の真下の対角の要素を１とし、残り全ての要素を０とする、（Ｌ＋Ｎ−１）ｍ行、（Ｌ＋Ｎ−１）ｍ列の行列であり、
前記検査行列を用いて、情報ビットに（Ｌ＋Ｎ−１）ｍビットのパリティビットが付加された空間結合ＬＤＰＣ符号を生成するＬＤＰＣ符号化部と、
前記パリティビットをｍビットずつ（Ｌ＋Ｎ−１）分割して分割パリティビットを生成するパリティ分割部と、
前記分割パリティビットのビットを並べ替えるパリティインターリーブ部と、
前記パリティインターリーブ部により並べ替えられた分割パリティビットを結合し、前記情報ビットに付加して空間結合ＬＤＰＣ符号として外部に出力するＬＤＰＣ符号出力部と、
を備えることを特徴とする符号化装置。
【請求項２】
前記パリティインターリーブ部は、前記ｍがｑ×Ｍで表せられるとすると、前記分割パリティビットを、記憶部にｑビットずつ行及び列の一方の方向に書き込んだ後に、該記憶部からＭビットずつ行及び列の他方の方向に読み出すことを特徴とする、請求項１に記載の符号化装置。
【請求項３】
検査行列によって定義される空間結合ＬＤＰＣ符号を生成する符号化装置であって、
前記検査行列は、情報部とパリティ部とで構成され、
前記情報部は、Ｎ種類のｍ行ｋ列の疎行列を行方向に結合させたＮ・ｍ行ｋ列の疎行列Ｌ個をｍ行ｋ列ずつずらして結合させた、（Ｌ＋Ｎ−１）ｍ行、Ｌ・ｋ列の行列であり、
前記パリティ部は、対角の要素と該対角の真下の対角の要素を１とし、残り全ての要素を０とする、（Ｌ＋Ｎ−１）ｍ行、（Ｌ＋Ｎ−１）ｍ列の行列であり、
前記Ｎ種類のｍ行ｋ列の疎行列は、基本疎行列の１をいずれかの同一要素位置に配置した行列であり、前記基本疎行列は、１列目に１が疎に配置され２列目以降は１列目の１をｑ行分サイクリックにシフトさせた位置に１が配置されたｍ行ｋ列の行列であり、
前記検査行列を用いて、情報ビットに（Ｌ＋Ｎ−１）ｍビットのパリティビットが付加された空間結合ＬＤＰＣ符号を生成するＬＤＰＣ符号化部を備え、
前記ＬＤＰＣ符号化部は、並列処理数がｍ／ｑの並列処理を行って、ｍビットずつのパリティビットを生成することを特徴とする符号化装置。
【請求項４】
検査行列によって定義される空間結合ＬＤＰＣ符号を復号する復号装置であって、
前記検査行列は、情報部とパリティ部とで構成され、
前記情報部は、Ｎ種類のｍ行ｋ列の疎行列を行方向に結合させたＮ・ｍ行ｋ列の疎行列Ｌ個をｍ行ｋ列ずつずらして結合させた、（Ｌ＋Ｎ−１）ｍ行、Ｌ・ｋ列の行列であり、
前記パリティ部は、対角の要素と該対角の真下の対角の要素を１とし、残り全ての要素を０とする、（Ｌ＋Ｎ−１）ｍ行、（Ｌ＋Ｎ−１）ｍ列の行列であり、
空間結合ＬＤＰＣ符号のパリティビットに相当する（Ｌ＋Ｎ−１）ｍ個の尤度比をｍ個ずつ（Ｌ＋Ｎ−１）分割して分割パリティ尤度比を生成するパリティ分割部と、
前記分割パリティ尤度比を並べ替えるパリティデインターリーブ部と、
前記パリティデインターリーブ部により並び替えられた分割パリティ尤度比を結合し、情報ビットに相当する尤度比に付加した尤度比を生成するパリティ結合部と、
パリティ結合部により生成された尤度比を用いて空間結合ＬＤＰＣ符号を復号するＬＤＰＣ符号復号部と、
を備えることを特徴とする復号装置。
【請求項５】
前記パリティデインターリーブ部は、前記ｍがｑ×Ｍで表せられるとすると、前記分割パリティ尤度比を、記憶部にＭ個ずつ行及び列の一方の方向に書き込んだ後に、該記憶部からｑ個ずつ行及び列の他方の方向に読み出すことを特徴とする、請求項４に記載の復号装置。
【請求項６】
前記Ｎ種類のｍ行ｋ列の疎行列は、基本疎行列の１をいずれかの同一要素位置に配置した行列であり、前記基本疎行列は、１列目に１が疎に配置され２列目以降は１列目の１をｑ行分サイクリックにシフトさせた位置に１が配置されたｍ行ｋ列の行列であることを特徴とする、請求項４又は５に記載の復号装置。
【請求項７】
検査行列によって定義される空間結合ＬＤＰＣ符号を生成する半導体チップであって、
前記検査行列は、情報部とパリティ部とで構成され、
前記情報部は、Ｎ種類のｍ行ｋ列の疎行列を行方向に結合させたＮ・ｍ行ｋ列の疎行列Ｌ個をｍ行ｋ列ずつずらして結合させた、（Ｌ＋Ｎ−１）ｍ行、Ｌ・ｋ列の行列であり、
前記パリティ部は、対角の要素と該対角の真下の対角の要素を１とし、残り全ての要素を０とする、（Ｌ＋Ｎ−１）ｍ行、（Ｌ＋Ｎ−１）ｍ列の行列であり、
前記検査行列を用いて、情報ビットに（Ｌ＋Ｎ−１）ｍビットのパリティビットが付加された空間結合ＬＤＰＣ符号を生成するＬＤＰＣ符号化部と、
前記パリティビットをｍビットずつ（Ｌ＋Ｎ−１）分割して分割パリティビットを生成するパリティ分割部と、
前記分割パリティビットの順番を並べ替えるパリティインターリーブ部と、
前記パリティインターリーブ部により並べ替えられた分割パリティビットを結合し、前記情報ビットに付加して空間結合ＬＤＰＣ符号として外部に出力するＬＤＰＣ符号出力部と、
を備えることを特徴とすることを特徴とする半導体チップ。
【請求項８】
検査行列によって定義される空間結合ＬＤＰＣ符号を生成する半導体チップであって、
前記検査行列は、情報部とパリティ部とで構成され、
前記情報部は、Ｎ種類のｍ行ｋ列の疎行列を行方向に結合させたＮ・ｍ行ｋ列の疎行列Ｌ個をｍ行ｋ列ずつずらして結合させた、（Ｌ＋Ｎ−１）ｍ行、Ｌ・ｋ列の行列であり、
前記パリティ部は、対角の要素と該対角の真下の対角の要素を１とし、残り全ての要素を０とする、（Ｌ＋Ｎ−１）ｍ行、（Ｌ＋Ｎ−１）ｍ列の行列であり、
前記Ｎ種類のｍ行ｋ列の疎行列は、基本疎行列の１をいずれかの同一要素位置に配置した行列であり、前記基本疎行列は、１列目に１が疎に配置され２列目以降は１列目の１をｑ行分サイクリックにシフトさせた位置に１が配置されたｍ行ｋ列の行列であり、
前記検査行列を用いて、情報ビットに（Ｌ＋Ｎ−１）ｍビットのパリティビットが付加された空間結合ＬＤＰＣ符号を生成するＬＤＰＣ符号化部を備え、
前記ＬＤＰＣ符号化部は、並列処理数がｍ／ｑの並列処理を行って、ｍビットずつのパリティビットを生成することを特徴とする半導体チップ。
【請求項９】
検査行列によって定義される空間結合ＬＤＰＣ符号を復号する半導体チップであって、
前記検査行列は、情報部とパリティ部とで構成され、
前記情報部は、Ｎ種類のｍ行ｋ列の疎行列を行方向に結合させたＮ・ｍ行ｋ列の疎行列Ｌ個をｍ行ｋ列ずつずらして結合させた、（Ｌ＋Ｎ−１）ｍ行、Ｌ・ｋ列の行列であり、
前記パリティ部は、対角の要素と該対角の真下の対角の要素を１とし、残り全ての要素を０とする、（Ｌ＋Ｎ−１）ｍ行、（Ｌ＋Ｎ−１）ｍ列の行列であり、
空間結合ＬＤＰＣ符号のパリティビットに相当する（Ｌ＋Ｎ−１）ｍ個の尤度比をｍ個ずつ（Ｌ＋Ｎ−１）分割して分割パリティ尤度比を生成するパリティ分割部と、
前記分割パリティ尤度比の順番を並べ替えるパリティデインターリーブ部と、
前記パリティデインターリーブ部により並び替えられた分割パリティ尤度比を結合し、情報ビットに相当する尤度比に付加した尤度比を生成するパリティ結合部と、
パリティ結合部により生成された尤度比を用いて空間結合ＬＤＰＣ符号を復号するＬＤＰＣ符号復号部と、
を備えることを特徴とする半導体チップ。
【請求項１０】
コンピュータを、請求項１から３のいずれか一項に記載の符号化装置として機能させるためのプログラム。
【請求項１１】
コンピュータを、請求項４から６のいずれか一項に記載の復号装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、空間結合ＬＤＰＣ符号を生成する符号化装置、半導体チップ、及びプログラム、並びに空間結合ＬＤＰＣ符号を復号する復号装置、半導体チップ、及びプログラムに関する。
【背景技術】
【０００２】
日本の地上デジタル放送方式であるＩＳＤＢ−Ｔ（Integrated Services Digital Broadcasting - Terrestrial）は、固定受信向けにハイビジョン放送（もしくは複数標準画質放送）を実現している。次世代の地上デジタル放送方式では、従来のハイビジョンに変わり３Ｄハイビジョン放送やハイビジョンの１６倍の解像度を持つスーパーハイビジョン等、さらに情報量の多いサービスを提供することが求められている。
【０００３】
そこで、データ容量の拡大、及び誤り訂正技術による所要Ｃ／Ｎの低減を実現するために、誤り訂正符号としてＬＤＰＣ（Low Density Parity Check；低密度パリティチェック）符号の採用が検討されている。ＬＤＰＣ符号は、設計次第では、誤り訂正の理論的限界であるシャノン限界に迫る特性が得られる。ＬＤＰＣ符号は情報ビットにパリティビットを付加したものであるが、欧州地上波デジタル放送の規格では、パリティビットをビットインターリーブ処理することが知られている（例えば、非特許文献１参照）。
【０００４】
また、近年では、ＬＤＰＣ符号の性能を凌駕する符号として、空間結合ＬＤＰＣ符号が注目されている（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】“Frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)”、[online]、2012年4月、ETSI、[2015年7月21日検索]，インターネット<URL: http://www.etsi.org/deliver/etsi_en/302700_302799/302755/01.03.01_60/en_302755v010301p.pdf>
【非特許文献２】朝倉  慎悟、外４名、“次世代地上放送に向けた伝送技術−空間結合ＬＤＰＣ符号の一検討−”、映像情報メディア学会技術報告、２０１３年９月、Ｖｏｌ．３７、Ｎｏ．３９
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ＬＤＰＣ符号のパリティビットをビットインターリーブ処理する場合、すべてのパリティビットを求めた後にインターリーブ処理を行うと、処理時間を要するという問題があった。
【０００７】
かかる事情に鑑みてなされた本発明の目的は、空間結合ＬＤＰＣ符号の構成に着目し、パリティビットのインターリーブ処理時間を短縮することが可能な符号化装置、復号装置、半導体チップ、及びプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
上記課題を解決するため、本発明に係る符号化装置は、検査行列によって定義される空間結合ＬＤＰＣ符号を生成する符号化装置であって、前記検査行列は、情報部とパリティ部とで構成され、前記情報部は、Ｎ種類のｍ行ｋ列の疎行列を行方向に結合させたＮ・ｍ行ｋ列の疎行列Ｌ個をｍ行ｋ列ずつずらして結合させた、（Ｌ＋Ｎ−１）ｍ行、Ｌ・ｋ列の行列であり、前記パリティ部は、対角の要素と該対角の真下の対角の要素を１とし、残り全ての要素を０とする、（Ｌ＋Ｎ−１）ｍ行、（Ｌ＋Ｎ−１）ｍ列の行列であり、前記検査行列を用いて、情報ビットに（Ｌ＋Ｎ−１）ｍビットのパリティビットが付加された空間結合ＬＤＰＣ符号を生成するＬＤＰＣ符号化部と、前記パリティビットをｍビットずつ（Ｌ＋Ｎ−１）分割して分割パリティビットを生成するパリティ分割部と、前記分割パリティビットのビットを並べ替えるパリティインターリーブ部と、前記パリティインターリーブ部により並べ替えられた分割パリティビットを結合し、前記情報ビットに付加して空間結合ＬＤＰＣ符号として外部に出力するＬＤＰＣ符号出力部と、を備えることを特徴とする。
【０００９】
さらに、本発明に係る符号化装置において、前記パリティインターリーブ部は、前記ｍがｑ×Ｍで表せられるとすると、前記分割パリティビットを、記憶部にｑビットずつ行及び列の一方の方向に書き込んだ後に、該記憶部からＭビットずつ行及び列の他方の方向に読み出すことを特徴とする。
【００１０】
また、上記課題を解決するため、本発明に係る符号化装置は、検査行列によって定義される空間結合ＬＤＰＣ符号を生成する符号化装置であって、前記検査行列は、情報部とパリティ部とで構成され、前記情報部は、Ｎ種類のｍ行ｋ列の疎行列を行方向に結合させたＮ・ｍ行ｋ列の疎行列Ｌ個をｍ行ｋ列ずつずらして結合させた、（Ｌ＋Ｎ−１）ｍ行、Ｌ・ｋ列の行列であり、前記パリティ部は、対角の要素と該対角の真下の対角の要素を１とし、残り全ての要素を０とする、（Ｌ＋Ｎ−１）ｍ行、（Ｌ＋Ｎ−１）ｍ列の行列であり、前記Ｎ種類のｍ行ｋ列の疎行列は、基本疎行列の１をいずれかの同一要素位置に配置した行列であり、前記基本疎行列は、１列目に１が疎に配置され２列目以降は１列目の１をｑ行分サイクリックにシフトさせた位置に１が配置されたｍ行ｋ列の行列であり、前記検査行列を用いて、情報ビットに（Ｌ＋Ｎ−１）ｍビットのパリティビットが付加された空間結合ＬＤＰＣ符号を生成するＬＤＰＣ符号化部を備え、前記ＬＤＰＣ符号化部は、並列処理数がｍ／ｑの並列処理を行って、ｍビットずつのパリティビットを生成することを特徴とする。
【００１１】
また、上記課題を解決するため、本発明に係る復号装置は、検査行列によって定義される空間結合ＬＤＰＣ符号を復号する復号装置であって、前記検査行列は、情報部とパリティ部とで構成され、前記情報部は、Ｎ種類のｍ行ｋ列の疎行列を行方向に結合させたＮ・ｍ行ｋ列の疎行列Ｌ個をｍ行ｋ列ずつずらして結合させた、（Ｌ＋Ｎ−１）ｍ行、Ｌ・ｋ列の行列であり、前記パリティ部は、対角の要素と該対角の真下の対角の要素を１とし、残り全ての要素を０とする、（Ｌ＋Ｎ−１）ｍ行、（Ｌ＋Ｎ−１）ｍ列の行列であり、空間結合ＬＤＰＣ符号のパリティビットに相当する（Ｌ＋Ｎ−１）ｍ個の尤度比をｍ個ずつ（Ｌ＋Ｎ−１）分割して分割パリティ尤度比を生成するパリティ分割部と、前記分割パリティ尤度比を並べ替えるパリティデインターリーブ部と、前記パリティデインターリーブ部により並び替えられた分割パリティ尤度比を結合し、情報ビットに相当する尤度比に付加した尤度比を生成するパリティ結合部と、パリティ結合部により生成された尤度比を用いて空間結合ＬＤＰＣ符号を復号するＬＤＰＣ符号復号部と、を備えることを特徴とする。
【００１２】
さらに、本発明に係る復号装置において、前記パリティデインターリーブ部は、前記ｍがｑ×Ｍで表せられるとすると、前記分割パリティ尤度比を、記憶部にＭ個ずつ行及び列の一方の方向に書き込んだ後に、該記憶部からｑ個ずつ行及び列の他方の方向に読み出すことを特徴とする。
【００１３】
さらに、本発明に係る復号装置において、前記Ｎ種類のｍ行ｋ列の疎行列は、基本疎行列の１をいずれかの同一要素位置に配置した行列であり、前記基本疎行列は、１列目に１が疎に配置され２列目以降は１列目の１をｑ行分サイクリックにシフトさせた位置に１が配置されたｍ行ｋ列の行列であることを特徴とする。
【００１４】
また、上記課題を解決するため、本発明に係る半導体チップは、検査行列によって定義される空間結合ＬＤＰＣ符号を生成する半導体チップであって、前記検査行列は、情報部とパリティ部とで構成され、前記情報部は、Ｎ種類のｍ行ｋ列の疎行列を行方向に結合させたＮ・ｍ行ｋ列の疎行列Ｌ個をｍ行ｋ列ずつずらして結合させた、（Ｌ＋Ｎ−１）ｍ行、Ｌ・ｋ列の行列であり、前記パリティ部は、対角の要素と該対角の真下の対角の要素を１とし、残り全ての要素を０とする、（Ｌ＋Ｎ−１）ｍ行、（Ｌ＋Ｎ−１）ｍ列の行列であり、前記検査行列を用いて、情報ビットに（Ｌ＋Ｎ−１）ｍビットのパリティビットが付加された空間結合ＬＤＰＣ符号を生成するＬＤＰＣ符号化部と、前記パリティビットをｍビットずつ（Ｌ＋Ｎ−１）分割して分割パリティビットを生成するパリティ分割部と、前記分割パリティビットの順番を並べ替えるパリティインターリーブ部と、前記パリティインターリーブ部により並べ替えられた分割パリティビットを結合し、前記情報ビットに付加して空間結合ＬＤＰＣ符号として外部に出力するＬＤＰＣ符号出力部と、を備えることを特徴とすることを特徴とする。
【００１５】
また、上記課題を解決するため、本発明に係る半導体チップは、検査行列によって定義される空間結合ＬＤＰＣ符号を生成する半導体チップであって、前記検査行列は、情報部とパリティ部とで構成され、前記情報部は、Ｎ種類のｍ行ｋ列の疎行列を行方向に結合させたＮ・ｍ行ｋ列の疎行列Ｌ個をｍ行ｋ列ずつずらして結合させた、（Ｌ＋Ｎ−１）ｍ行、Ｌ・ｋ列の行列であり、前記パリティ部は、対角の要素と該対角の真下の対角の要素を１とし、残り全ての要素を０とする、（Ｌ＋Ｎ−１）ｍ行、（Ｌ＋Ｎ−１）ｍ列の行列であり、前記Ｎ種類のｍ行ｋ列の疎行列は、基本疎行列の１をいずれかの同一要素位置に配置した行列であり、前記基本疎行列は、１列目に１が疎に配置され２列目以降は１列目の１をｑ行分サイクリックにシフトさせた位置に１が配置されたｍ行ｋ列の行列であり、前記検査行列を用いて、情報ビットに（Ｌ＋Ｎ−１）ｍビットのパリティビットが付加された空間結合ＬＤＰＣ符号を生成するＬＤＰＣ符号化部を備え、前記ＬＤＰＣ符号化部は、並列処理数がｍ／ｑの並列処理を行って、ｍビットずつのパリティビットを生成することを特徴とする。
【００１６】
また、上記課題を解決するため、本発明に係る半導体チップは、検査行列によって定義される空間結合ＬＤＰＣ符号を復号する半導体チップであって、前記検査行列は、情報部とパリティ部とで構成され、前記情報部は、Ｎ種類のｍ行ｋ列の疎行列を行方向に結合させたＮ・ｍ行ｋ列の疎行列Ｌ個をｍ行ｋ列ずつずらして結合させた、（Ｌ＋Ｎ−１）ｍ行、Ｌ・ｋ列の行列であり、前記パリティ部は、対角の要素と該対角の真下の対角の要素を１とし、残り全ての要素を０とする、（Ｌ＋Ｎ−１）ｍ行、（Ｌ＋Ｎ−１）ｍ列の行列であり、空間結合ＬＤＰＣ符号のパリティビットに相当する（Ｌ＋Ｎ−１）ｍ個の尤度比をｍ個ずつ（Ｌ＋Ｎ−１）分割して分割パリティ尤度比を生成するパリティ分割部と、前記分割パリティ尤度比の順番を並べ替えるパリティデインターリーブ部と、前記パリティデインターリーブ部により並び替えられた分割パリティ尤度比を結合し、情報ビットに相当する尤度比に付加した尤度比を生成するパリティ結合部と、パリティ結合部により生成された尤度比を用いて空間結合ＬＤＰＣ符号を復号するＬＤＰＣ符号復号部と、を備えることを特徴とする。
【００１７】
また、上記課題を解決するため、本発明に係るプログラムは、コンピュータを、上記符号化装置として機能させることを特徴とする。
【００１８】
また、上記課題を解決するため、本発明に係るプログラムは、コンピュータを、上記復号装置として機能させることを特徴とする。
【発明の効果】
【００１９】
本発明によれば、空間結合ＬＤＰＣ符号のパリティビットのインターリーブ処理時間を短縮することができるようになる。
【図面の簡単な説明】
【００２０】
【図１】本発明の第１の実施形態に係る符号化装置を備える送信装置の構成例を示すブロック図である。
【図２】空間結合ＬＤＰＣ符号の検査行列を示す模式図である。
【図３】空間結合ＬＤＰＣ符号の基本疎行列を示す模式図である。
【図４】空間結合ＬＤＰＣ符号の基本疎行列を分割して生成される疎行列を示す模式図である。
【図５】空間結合ＬＤＰＣ符号の検査行列のパリティ部を示す行列である。
【図６】本発明の第１の実施形態に係る符号化装置におけるパリティ分割部の処理を説明する図である。
【図７】本発明の一実施形態に係る符号化装置におけるパリティインターリーブ部の処理を説明する図である。
【図８】本発明の一実施形態に係る符号化装置のＬＤＰＣ符号化部によるパリティビットの生成について説明する図である。
【図９】本発明の第２の実施形態に係る復号装置の構成例を示すブロック図である。
【発明を実施するための形態】
【００２１】
以下、本発明の実施形態について、図面を参照して詳細に説明する。
【００２２】
（第１の実施形態）
本発明の第１の実施形態に係る符号化装置について、以下に説明する。図１は、本発明の第１の実施形態に係る符号化装置を備える送信装置の構成例を示すブロック図である。図１に示す例では、送信装置１は、符号化装置１０と、ＯＦＤＭ変調部２０とを備える。この図では主要な処理ブロックのみ示しており、時間インターリーブ処理部など、本発明に直接関連しない処理部については省略している。
【００２３】
符号化装置１０は、情報ビットにパリティビット（冗長ビット）が付加された空間結合ＬＤＰＣ符号を生成し、ＯＦＤＭ変調部２０に出力する。本明細書においては、空間結合ＬＤＰＣ符号とは、１の要素が帯状に斜めに配置された検査行列により定義されるＬＤＰＣ符号とする。また、ＢＣＨ符号を外符号とし空間結合ＬＤＰＣ符号を内符号とする連接符号も含むものとする。符号化装置１０は、ＬＤＰＣ符号化部１１と、パリティ分割部１２と、複数のパリティインターリーブ部１３と、ＬＤＰＣ符号出力部１４とを備える。
【００２４】
ＯＦＤＭ変調部２０は、符号化装置１０から入力される空間結合ＬＤＰＣ符号をＯＦＤＭ変調してＯＦＤＭ信号を生成し、アンテナを介して外部に送信する。
【００２５】
ＬＤＰＣ符号化部１１は、後述する空間結合検査行列ＨＣを用いて、情報ビットにパリティビットが付加された空間結合ＬＤＰＣ符号を生成し、パリティビットをパリティ分割部１２に出力する。
【００２６】
ここで、まずＬＤＰＣ符号の一般的な生成手法について説明する。ＬＤＰＣ符号は検査行列Ｈを用いて生成される。検査行列ＨのサイズはＬＤＰＣ符号の符号長ｎに比例するため、符号長ｎが大きくなると検査行列Ｈも大きなサイズの行列となる。したがって、符号化に必要な生成行列Ｇを計算する際の演算量は非常に大きくなる。あるいは生成行列Ｇを予め計算して記憶させておき符号化を行う場合においても非常に大きなメモリが必要となる。このように符号化における演算量又は所要メモリ量がＬＤＰＣ符号の課題の一つとなっている。
【００２７】
これを解決する一つの手段として、ＬＤＧＭ（Low-Density Generator Matrix）構造を導入した検査行列を用いてＬＤＰＣ符号を生成する手法が提案されている。ＬＤＧＭ構造とは、検査行列Ｈを式（１）に示すように情報部ＨＩとパリティ部ＨＰに分割することで、検査行列Ｈから生成行列Ｇを求めずに直接符号化を可能にすることを特徴としている。本発明もＬＤＧＭ構造を有する検査行列を用いるものとする。
【００２８】
【数１】
0006553975.tif 000002
【００２９】
図２は、本発明で用いられる空間結合ＬＤＰＣ符号の検査行列ＨＣを示す模式図である。空間結合ＬＤＰＣ符号は、いくつかのＬＤＰＣ符号を結合することで構成されるＬＤＰＣ畳み込み符号の一種であり、斜めの帯状に１が疎に存在する検査行列によって定義される。上記のように、空間結合ＬＤＰＣ符号の検査行列（以下、空間結合検査行列という。）ＨＣは、ＬＤＧＭ構造を有し、情報部ＨＩとパリティ部ＨＰとで構成される行列である。
【００３０】
情報部ＨＩは、符号長ｎ、パリティ長ｍの疎行列（以下、基本疎行列という。）ＨＢに基づいて生成される。ここで、ｋ＝ｎ−ｍとする。情報部ＨＩは、Ｎ種類（Ｎ：２以上の自然数）のｍ行ｋ列の疎行列を列方向（縦方向）に結合させたＮ・ｍ行ｋ列の疎行列Ｌ個をｍ行ｋ列ずつずらして結合させた、（Ｌ＋Ｎ−１）ｍ行、Ｌ・ｋ列の行列である。Ｎ種類の疎行列は、ｍ行ｋ列の基本疎行列ＨＢの各要素をＮ個のいずれかの行列に振り分けることにより生成される。図２ではＮ＝２の場合を示しており、２種類の疎行列をＨＵ，ＨＬと表記している。
【００３１】
図３は、基本疎行列ＨＢを示す模式図である。基本疎行列ＨＢはｍ行Ｍ列の行列ごとに周期的構造を有し、各ｍ行Ｍ列の行列では１列目に１が疎に配置され、２列目以降は１列目の１をｑ行分サイクリックにシフトさせた位置に１が配置される。Ｍはｍ／ｑとする。
【００３２】
図４は、基本疎行列ＨＢを２つに分割した疎行列ＨＵ，ＨＬを示す模式図である。ここでは説明のため、基本疎行列ＨＢ、及び疎行列ＨＵ，ＨＬについてそれぞれｍ行Ｍ列の行列のみを示している。疎行列ＨＵ，ＨＬは、基本疎行列ＨＢの１をいずれかの同一要素位置に配置した行列である。
【００３３】
図５は、空間結合検査行列ＨＣのパリティ部ＨＰを示す行列である。図５に示すように、パリティ部ＨＰは２重対角行列である。２重対角行列とは、対角の要素と該対角の真下の要素を１とし、残り全ての要素を０とする行列である。パリティ部ＨＰのサイズは（Ｌ＋Ｎ−１）ｍ行、（Ｌ＋Ｎ−１）ｍ列であり、図２ではＮ＝２の場合を示している。
【００３４】
ＬＤＰＣ符号化部１１は、上述した（Ｌ＋Ｎ−１）ｍ行、｛Ｌ・ｋ＋（Ｌ＋Ｎ−１）ｍ｝列の空間結合検査行列ＨＣを用いて、Ｌ・ｋビットの情報ビットに（Ｌ＋Ｎ−１）ｍビットのパリティビットが付加された空間結合ＬＤＰＣ符号を生成する。
【００３５】
パリティ分割部１２は、ＬＤＰＣ符号化部１１により生成された（Ｌ＋Ｎ−１）ｍビットのパリティビットをｍビットずつ（Ｌ＋Ｎ−１）分割し、それぞれパリティインターリーブ部１３に出力する。そのため、パリティインターリーブ部１３の数は（Ｌ＋Ｎ−１）個である。なお、図１ではＮ＝２の場合を示しており、この場合のパリティインターリーブ部１３の数は（Ｌ＋１）個である。
【００３６】
図６は、パリティ分割部１２の処理を説明する図である。図６ではＮ＝２の場合を示しており、この場合パリティ分割部１２は、（Ｌ＋１）ｍビットのパリティビットｐ０，ｐ１，・・・，ｐｍ−１，ｐｍ，ｐｍ＋１，・・・，ｐ２ｍ−１，・・・，ｐ（Ｌ＋１）ｍ−１を入力し、ｍビットずつ分割して（Ｌ＋１）個の分割されたパリティビット（以下、「分割パリティビット」という。）を生成する。そして、分割パリティビットｐ０，ｐ１，・・・，ｐｍ−１をパリティインターリーブ部１３−１に出力し、分割パリティビットｐｍ，ｐｍ+１，・・・，ｐ２ｍ−１をパリティインターリーブ部１３−２に出力し、以下同様にして、分割パリティビットｐＬｍ，ｐＬｍ＋１，・・・，ｐ（Ｌ＋１）ｍ−1をパリティインターリーブ部１３−（Ｌ＋１）に出力する。
【００３７】
各パリティインターリーブ部１３は、パリティ分割部１２により生成されたｍビットの分割パリティビットの順番を並べ替え、ＬＤＰＣ符号出力部１４に出力する。
【００３８】
図７は、パリティインターリーブ部１３の処理を説明する図である。この図では代表してパリティインターリーブ部１３−１の処理を示している。ｍ＝ｑ×Ｍとすると、パリティインターリーブ部１３−１は、分割パリティビットｐ０，ｐ１，・・・，ｐｑ−１，ｐｑ，ｐｑ＋１，・・・，ｐ２ｑ−１，ｐ２ｑ，ｐ２ｑ＋１，・・・，ｐ３ｑ−１，・・・，ｐ（Ｍ−１）ｑ，ｐ（Ｍ−１）ｑ＋１，・・・，ｐｍ−１を、図示しない記憶部にｑビットずつ列方向に書き込んだ後に、該記憶部からＭビットずつ行方向に読み出す。すなわち、出力される分割パリティビットの順は、ｐ０，ｐｑ，ｐ２ｑ，・・・，ｐ（Ｍ−１）ｑ，ｐ１，ｐｑ＋１，ｐ２ｑ＋１，・・・ｐ（Ｍ−１）ｑ＋１，・・・，ｐｑ−１，ｐ２ｑ―１，ｐ３ｑ―１，・・・，ｐｍ−１となる。なお、パリティインターリーブ部１３は分割パリティビットを記憶部にｑビットずつ行方向に書き込んだ後に、該記憶部からＭビットずつ列方向に読み出してもよいのは勿論である。また、並べ替え方法はこれに限定されるものではない。
【００３９】
なお、パリティインターリーブ部１３の処理をＣ言語で表現すると、入力パリティデータｐｉ［ ］、出力パリティデータｐｏ［ ］として、以下のように表すことができる。
for(int i=0; i<(L+N-1); i++){
for(int j=0; j<m; j++){
int r = m/q;
int c = m%q;
po[im + cM + r] = pi[im + j];
}
}
【００４０】
ＬＤＰＣ符号出力部１４は、（Ｌ＋Ｎ−１）個のパリティインターリーブ部１３により並べ替えられた分割パリティビットを結合し、情報ビットに付加して空間結合ＬＤＰＣ符号として外部に出力する。
【００４１】
空間結合ＬＤＰＣ符号の符号語ｃは、式（２）の条件を満たす。ここで、Ｔは行列の転置を表す。式（２）により（Ｌ＋Ｎ−１）ｍ個の関係式が得られ、これを解くことで（Ｌ＋Ｎ−１）ｍビットのパリティビットを算出できる。
【００４２】
【数２】
0006553975.tif 000003
【００４３】
２重対角行列のパリティ部ＨＰを用いた場合、空間結合検査行列ＨＣの１行目を用いた関係式から１ビット目のパリティビットｐ０が求まる。空間結合検査行列ＨＣの２行目を用いた関係式と１ビット目のパリティビットｐ０とから、２ビット目のパリティビットｐ１が求まる。空間結合検査行列ＨＣの３行目を用いた関係式と２ビット目のパリティビットｐ１とから、３ビット目のパリティビットｐ２が求まる。このようにして順番にパリティビットを求めることができる。
【００４４】
図８は、ＬＤＰＣ符号化部１１によるパリティビットの生成について説明する図でり、Ｎ＝２の場合を示している。空間結合ＬＤＰＣ符号を生成する場合においては、式（２）の条件式を満たすパリティビットをｍ行単位で算出することができる。ＬＤＰＣ符号出力部１４は、空間結合検査行列ＨＣのうち最初のｍ行を用いて、最初のｍビットのパリティビットｐ０，ｐ１，・・・，ｐｍ−１を算出することができる。図８ではこのｍビットのパリティビットをＰ０と示す。また、ＬＤＰＣ符号出力部１４は、空間結合検査行列ＨＣのうち次のｍ行（ｍ＋１行目から２ｍ行目）を用いて、次のｍビットのパリティビットｐｍ，ｐｍ＋１，・・・，ｐ２ｍ−１を算出することができる。図８ではこのｍビットのパリティビットをＰ１と示す。以下、同様にして、パリティビットＰ０，Ｐ１，・・・，ＰＬを算出することができる。
【００４５】
このように、符号化装置１０は、ＬＤＰＣ符号化部１１により、空間結合検査行列ＨＣを用いて、情報ビットに（Ｌ＋Ｎ−１）ｍビットのパリティビットが付加された空間結合ＬＤＰＣ符号を生成し、パリティ分割部１２により、パリティビットをｍビットずつ（Ｌ＋Ｎ−１）分割して分割パリティビットを生成し、パリティインターリーブ部１３により、分割パリティビットの順番を並べ替え、ＬＤＰＣ符号出力部１４により、パリティインターリーブ部１３により並べ替えられた分割パリティビットを結合し、情報ビットに付加して空間結合ＬＤＰＣ符号として外部に出力する。かかる構成により、空間結合ＬＤＰＣ符号の生成が完了するのを待たないで、ｍビットのパリティビットを生成するごとにインターリーブ処理を行うことができるため、空間結合ＬＤＰＣ符号の生成及びパリティビットのインターリーブ処理に要する時間を短縮することができる。
【００４６】
つぎに、パリティビットを並列演算処理により生成するＬＤＰＣ符号化部１１’について検討する。空間結合ＬＤＰＣ符号を生成する場合においては、基本疎行列ＨＢがＭ列ごとに周期性を有する行列である場合には、ｍビットずつのパリティビットを生成するにあたり、並列処理数Ｍ＝ｍ／ｑの並列処理を行うことができる。詳細については、例えばMarco Gomes、他４名、“High Throughput Encoder Architecture for DVB-S2 LDPC-IRP Codes”、ＩＥＥＥ ＩＣＭ、２００７年を参照されたい。
【００４７】
具体的には、図２に示す空間結合検査行列ＨＣを使用した場合、疎行列ＨＵ＿０,ＨＬ＿０を用いて最初のｍビットのパリティビットｐ０，ｐ１，・・・，ｐｍ−１を並列処理により算出し、次にこの結果（パリティビットｐ０，ｐ１，・・・，ｐｍ−１）と、疎行列ＨＵ＿１,ＨＬ＿１を用いて次のｍビットのパリティビットｐｍ，ｐｍ＋１，・・・，ｐ２ｍ−１を並列処理により算出することができる。以下、同様にして、算出済みのパリティビットｐ（ｋ−１）ｍ，ｐ（ｋ−１）ｍ＋１，・・・，ｐｋｍ−１と、疎行列ＨＵ＿ｋ,ＨＬ＿ｋとを用いて、ｍビットのパリティビットｐｋｍ，ｐｋｍ＋１，・・・，ｐ（ｋ＋1）ｍ−１を並列処理により算出することができる。
【００４８】
また、並列処理数Ｍでｍビットのパリティビットを生成する場合、１ビット目からｍビット目まで順番に生成されるのではなく、１ビット目からｑビットおきにＭビット生成され、２ビット目からｑビットおきにＭビットされ、同様にして最後はｑビット目からｑビットおきにＭビット生成される。つまり、図７で示したパリティインターリーブ部１３の処理順と同じく、ｐ０，ｐｑ，ｐ２ｑ，・・・，ｐ（Ｍ−１）ｑ，ｐ１，ｐｑ＋１，ｐ２ｑ＋１，・・・ｐ（Ｍ−１）ｑ＋１，・・・，ｐｑ−１，ｐ２ｑ―１，ｐ３ｑ―１，・・・，ｐｍ−１の順序で生成される。
【００４９】
したがって、符号化装置１０が、パリティビットを並列演算処理により算出するＬＤＰＣ符号化部１１’を備える場合には、パリティビットのインターリーブ処理も同時に行われるため、パリティ分割部１２、パリティインターリーブ部１３、及びＬＤＰＣ符号出力部１４は不要となる。
【００５０】
このように、符号化装置１０は、ＬＤＰＣ符号化部１１’により、並列処理数がｍ／ｑの並列処理を行って、ｍビットずつのパリティビットを生成することもできる。パリティビットの演算処理を並列で行うことにより、パリティビットの算出に要する時間を短縮することができる。
【００５１】
なお、上述した送信装置１又は符号化装置１０として機能させるためにコンピュータを好適に用いることができ、そのようなコンピュータは、送信装置１又は符号化装置１０の各機能を実現する処理内容を記述したプログラムを該コンピュータの記憶部に格納しておき、該コンピュータのＣＰＵによってこのプログラムを読み出して実行させることで実現することができる。なお、このプログラムは、コンピュータ読取り可能な記録媒体に記録可能である。
【００５２】
また、上述した送信装置１又は符号化装置１０は、１つ又は複数の半導体チップにより構成されてもよい。この半導体チップは、送信装置１又は符号化装置１０の各機能を実現する処理内容を記述したプログラムを実行するＣＰＵを搭載してもよい。
【００５３】
（第２の実施形態）
つぎに、本発明の第２の実施形態に係る復号装置について説明する。図９は、第２の実施形態に係る復号装置の構成例を示すブロック図である。図９に示す例では、受信装置２は、ＯＦＤＭ復調部３０と、尤度比算出部４０と、復号装置５０とを備える。この図では主要な処理ブロックのみ示しており、時間デインターリーブ処理部など、本発明に直接関連しない処理部については省略している。
【００５４】
受信装置２は、第１の実施形態に係る送信装置１が送信するＯＦＤＭ信号を受信する装置であり、空間結合検査行列ＨＣによって定義される空間結合ＬＤＰＣ符号を復号する。上述したように、空間結合検査行列ＨＣは、情報部ＨＩとパリティ部ＨＰとで構成され、情報部ＨＩは、Ｎ種類のｍ行ｋ列の疎行列を列方向に結合させたＮ・ｍ行ｋ列の疎行列Ｌ個をｍ行ｋ列ずつずらして結合させた、（Ｌ＋Ｎ−１）ｍ行、Ｌ・ｋ列の行列であり、パリティ部ＨＰは、対角の要素と該対角の真下の対角の要素を１とし、残り全ての要素を０とする、（Ｌ＋Ｎ−１）ｍ行、（Ｌ＋Ｎ−１）ｍ列の行列である。
【００５５】
さらに、上述したように、基本疎行列ＨＢを、１列目に１が疎に配置され２列目以降は１列目の１をｑ行分サイクリックにシフトさせた位置に１が配置されたｍ行ｋ列の行列とし、Ｎ種類のｍ行ｋ列の疎行列を、基本疎行列ＨＢの１をいずれかの同一要素位置に配置した行列としてもよい。
【００５６】
ＯＦＤＭ復調部３０は、送信装置１からＯＦＤＭ信号を受信し、復調して空間結合ＬＤＰＣ符号を生成し、尤度比算出部４０に出力する。空間結合ＬＤＰＣ符号は送信装置１で生成された、Ｌ・ｋビットの情報ビットに（Ｌ＋Ｎ−１）ｍビットのパリティビットが付加された符号である。
【００５７】
尤度比算出部４０は、ＯＦＤＭ復調部３０により生成された空間結合ＬＤＰＣ符号の各ビットの尤度比を算出し、復号装置５０に出力する。尤度比としては、一般的に対数尤度比（ＬＬＲ：Log-Likelihood Ratio）が用いられる。ｎ番目のビットの対数尤度比λｎは、ｎ番目のビットのビット値が０となる尤度関数と１となる尤度関数との比の対数で表される。
【００５８】
復号装置５０は、尤度比算出部４０から尤度比を入力し、空間結合ＬＤＰＣ符号を復号して情報ビットを出力する。復号装置５０は、尤度比分離部５１と、パリティ分割部５２と、複数のパリティデインターリーブ部５３と、パリティ結合部５４と、ＬＤＰＣ符号復号部５５とを備える。
【００５９】
尤度比分離部５１は、空間結合ＬＤＰＣ符号の各ビットの尤度比を入力する。そして、尤度比分離部５１は、空間結合ＬＤＰＣ符号のパリティビットに相当する（Ｌ＋Ｎ−１）ｍ個の尤度比をパリティ分割部５２に出力し、空間結合ＬＤＰＣ符号の情報ビットに相当するＬ・ｋ個の尤度比をパリティ結合部５４に出力する。
【００６０】
パリティ分割部５２は、尤度比分離部５１から入力される尤度比をｍ個ずつ（Ｌ＋Ｎ−１）分割して分割された尤度比（以下、分割パリティ尤度比という。）を生成し、それぞれパリティデインターリーブ部５３に出力する。そのため、パリティデインターリーブ部５３の数は（Ｌ＋Ｎ−１）個である。なお、図９ではＮ＝２の場合を示しており、この場合のパリティデインターリーブ部５３の数は（Ｌ＋１）個である。
【００６１】
各パリティデインターリーブ部５３は、パリティ分割部５２から入力されるｍ個の分割パリティ尤度比の順番を、送信装置１のパリティインターリーブ部１３による並べ替えと逆方向に並べ替え、パリティ結合部５４に出力する。例えば図７に示したように、各パリティインターリーブ部１３がパリティビットを記憶部にｑビットずつ列方向に書き込んだ後に、該記憶部からＭビットずつ行方向に読み出して並べ替えた場合には、各パリティデインターリーブ部５３は、尤度比を記憶部にＭ個ずつ行方向に書き込んだ後に、該記憶部からｑ個ずつ列方向に読み出す。なお、各パリティインターリーブ部１３がパリティビットを記憶部にｑビットずつ行方向に書き込んだ後に、該記憶部からＭビットずつ列方向に読み出して並べ替えた場合には、各パリティデインターリーブ部５３は、尤度比を記憶部にＭ個ずつ列方向に書き込んだ後に、該記憶部からｑ個ずつ行方向に読み出す。
【００６２】
パリティ結合部５４は、各パリティデインターリーブ部５３から入力されるパリティビットに相当する尤度比を結合し、尤度比分離部５１から入力される情報ビットに相当する尤度比に付加した尤度比を生成し、ＬＤＰＣ符号復号部５５に出力する。
【００６３】
ＬＤＰＣ符号復号部５５は、パリティ結合部５４により生成された尤度比を用いて、既知の手法（例えば、sum-product復号法）により、空間結合ＬＤＰＣ符号の復号を行い、情報ビットを外部に出力する。
【００６４】
このように、復号装置５０は、パリティ分割部５２により空間結合ＬＤＰＣ符号のパリティビットに相当する（Ｌ＋Ｎ−１）ｍ個の尤度比をｍ個ずつ（Ｌ＋Ｎ−１）分割して分割パリティ尤度比を生成し、パリティデインターリーブ部５３により分割パリティ尤度比を並べ替え、パリティ結合部５４によりパリティデインターリーブ部５３により並び替えられた分割パリティ尤度比を結合し、情報ビットに相当する尤度比に付加した尤度比を生成し、ＬＤＰＣ符号復号部５５によりパリティ結合部５４により生成された尤度比を用いて空間結合ＬＤＰＣ符号を復号する。かかる構成により、符号化装置１０により生成された空間結合ＬＤＰＣ符号を復号することができる。
【００６５】
また、復号装置５０は、入力されたデータをデインターリーブするのではなく、空間結合検査行列ＨＣの行を入力データに合わせて並べ替えておくことにより、パリティデインターリーブ処理を行わずに、すなわちパリティ分割部５２、パリティデインターリーブ部５３、及びパリティ結合部５４を備えることなく、ＬＤＰＣ符号を復号することも可能である。
【００６６】
なお、上述した受信装置２又は復号装置５０として機能させるためにコンピュータを好適に用いることができ、そのようなコンピュータは、受信装置２又は復号装置５０の各機能を実現する処理内容を記述したプログラムを該コンピュータの記憶部に格納しておき、該コンピュータのＣＰＵによってこのプログラムを読み出して実行させることで実現することができる。なお、このプログラムは、コンピュータ読取り可能な記録媒体に記録可能である。
【００６７】
また、上述した受信装置２又は復号装置５０は、１つ又は複数の半導体チップにより構成されてもよい。この半導体チップは、受信装置２又は復号装置５０の各機能を実現する処理内容を記述したプログラムを実行するＣＰＵを搭載してもよい。
【００６８】
上述の実施形態は代表的な例として説明したが、本発明の趣旨及び範囲内で、多くの変更及び置換ができることは当業者に明らかである。したがって、本発明は、上述の実施形態によって制限するものと解するべきではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。例えば、実施形態に記載の複数の構成ブロックを１つに組み合わせたり、あるいは１つの構成ブロックを分割したりすることが可能である。
【符号の説明】
【００６９】
１    送信装置
２    受信装置
１０  符号化装置
１１  ＬＤＰＣ符号化部
１２  パリティ分割部
１３  パリティインターリーブ部
１４  ＬＤＰＣ符号出力部
２０  ＯＦＤＭ変調部
３０  ＯＦＤＭ復調部
４０  尤度比算出部
５０  復号装置
５１  尤度比分離部
５２  パリティ分割部
５３  パリティデインターリーブ部
５４  パリティ結合部
５５  ＬＤＰＣ符号復号部
【図１】
0006553975.tif 000004
【図２】
0006553975.tif 000005
【図３】
0006553975.tif 000006
【図４】
0006553975.tif 000007
【図５】
0006553975.tif 000008
【図６】
0006553975.tif 000009
【図７】
0006553975.tif 000010
【図８】
0006553975.tif 000011
【図９】
0006553975.tif 000012