(57)【要約】【課題】LDPC復号装置等の回路規模縮小を図る。【解決手段】ビットデインターリーバ内蔵LDPC復号器２５２は、ビットインターリーブ処理が施された符号語であって、パリティ部を含む符号語を単位として復号する処理の一例として、LDPC復号を行う。詳細には、受信部３０２には、符号語の長さ分のデータ容量を少なくとも有する受信値メモリが搭載されている。そこで、受信部３０２は、符号語の各要素を受信値Ｄ３０２として受信したとき、受信値Ｄ３０２に対してビットデインターリーブ処理とパリティ並び替え処理とを施して、受信値Ｄ３０２をメモリに格納する制御、即ち、書き込む制御を実行し、また、そのメモリに格納された符号語を読み出して出力Ｄ３０３としてLDPC復号計算部３０３に提供する。本発明は、LDPC復号装置に適用可能である。【選択図】図２０
2008278189.tif 000002
【特許請求の範囲】
【請求項１】
パリティ部を含む符号語を単位として復号する復号装置において、
前記符号語の長さ分のデータ容量を少なくとも有する格納手段と、
ビットインターリーブ処理が施された前記符号語の各要素を受信値として受信したとき、前記受信値に対してビットデインターリーブ処理とパリティ並び替え処理とを施して、前記受信値を前記格納手段に格納する制御を実行する受信手段と
を備える復号装置。
【請求項２】
前記符号語の前記各要素に対応する前記受信値のそれぞれは、前記受信手段に対してシリアルに入力される
請求項１に記載の復号装置。
【請求項３】
前記格納手段は、前記受信値を任意の位置に格納できる構成を有している
請求項１に記載の復号装置。
【請求項４】
前記受信値は軟値である
請求項１に記載の復号装置。
【請求項５】
前記復号装置は、低密度パリティ検査符号(Low Density Parity-Check code,LDPC符号)を復号する復号装置である
請求項１に記載の復号装置。
【請求項６】
前記格納手段は、RAM（Random Access Memory）で構成されている
請求項１に記載の復号装置。
【請求項７】
パリティ部を含む符号語を単位として復号する復号装置の復号方法において、
前記符号語の長さ分のデータ容量を少なくとも有するメモリを備える前記復号装置が、
ビットインターリーブ処理が施された前記符号語の各要素が受信値として受信されたとき、前記受信値に対してビットデインターリーブ処理とパリティ並び替え処理とを施して、前記受信値を前記メモリに格納する制御を実行する
ステップを含む復号方法。
【請求項８】
パリティ部を含む符号語を単位として復号する処理を制御するコンピュータに実行させるプログラムであって、
前記コンピュータまたはそれ以外の装置に、前記符号語の長さ分のデータ容量を少なくとも有するメモリが備えられており、
ビットインターリーブ処理が施された前記符号語の各要素が受信値として受信されたとき、前記受信値に対してビットデインターリーブ処理とパリティ並び替え処理とを施して、前記受信値を前記メモリに格納する制御を実行する
ステップを含むプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号装置および方法並びにプログラムに関し、特に、その回路規模が従来より縮小されるようになった復号装置および方法並びにプログラムに関する。
【背景技術】
【０００２】
通信システムにおいては、コーディングを使用して雑音のある通信チャネルに渡る信頼性ある通信が行われている。例えば、衛星ネットワークのようなワイヤレス（または無線）システムでは、地理的および環境的要因からの雑音源が多い。これらの通信チャネルは固定容量を表し、ある信号対雑音比（ＳＮＲ）におけるシンボル当たりのビットに関して表すことができ、シャノン限界として知られる理論的上限を規定している。結果として、コーディング設計はこのシャノン限界に近づくレートを達成することを目的としている。この目的は、帯域幅制約衛星システムに対して特に密接な関係がある。
【０００３】
近年では、シャノン限界に近い性能を示す符号化方法として、例えば、並列連接畳み込み符号(PCCC(Parallel Concatenated Convolutional Codes))や、縦列連接畳み込み符号(SCCC(Serially Concatenated Convolutional Codes))といった、いわゆるターボ符号化(Turbo coding)と称される手法が開発されている。また、これらのターボ符号が開発される一方で、古くから知られる符号化方法である低密度パリティ検査符号(Low Density Parity Check codes)（以下、LDPC符号と称する）が脚光を浴びつつある。
【０００４】
LDPC符号は、R. G. Gallagerによる非特許文献１において最初に提案されたものであり、その後、非特許文献２，３等において再注目されるに至ったものである。
【０００５】
LDPC符号は、近年の研究により、ターボ符号等と同様に、符号長を長くしていくに従って、シャノン限界に近い性能が得られることがわかりつつある。また、LDPC符号は、最小距離が符号長に比例するという性質があることから、その特徴として、ブロック誤り確率特性がよく、さらに、ターボ符号等の復号特性において観測される、いわゆるエラーフロア現象が殆ど生じないことが利点として挙げられる。
【０００６】
以上の利点により、LDPC符号は、DVB-S.2規格(ETSI(European Telecommunication Standard Institute: 欧州電気通信標準化機構)により規格された、世界的に最も一般的に使われている規格  DVB-Sの上位規格)に採用されている。
【０００７】
以下において、DVB-S.2規格に基づいて送信された信号を受信器で受信した場合を例にとり、LDPC符号のビットデインターリーブおよび復号法アルゴリズムについて具体的に説明する。なお、LDPC符号は、線形符号であり、必ずしも２元である必要はないが、DVB-S.2規格では２元符号が採用されているため、ここでは２元であるものとして説明する。
【０００８】
図１は、DVB-S.2規格における送信器の機能的構成を示している。
【０００９】
この送信器は、入力インターフェース１０１乃至変調部１１１を含むように構成されている。
【００１０】
なお、各機能ブロックの出力データに対しては、アルファベットのＤと所定の数値との組合せからなる符合が付されている。そこで、かかる符号によって、各機能ブロックの出力データの区別をすることとし、各ブロックの出力データの呼称については、同一のブロックの出力データの場合であっても必ずしも統一せず、逆に異なるブロックの出力データの場合であっても同一の呼称を用いる場合もある。即ち、符号が同一で呼称が異なるデータが存在する場合、そのことは、基本的には、同一機能ブロックの出力データを意味しているが、登場してきた各文章の内容に合致したそれぞれの呼称、例えば登場してきた各文章で注目されている各単位に応じたそれぞれの呼称を用いていることを意味している。逆に、呼称が同一でも符号が異なるデータが存在する場合、そのことは、所定の特徴等が合致しているため、その特徴等を表現する呼称を用いているため同一の呼称となっているが、符合が異なることから、それぞれ異なる機能ブロックから出力されたデータ、即ち厳密には一致しないデータ（例えばデータの配置換えが行われたデータ）を意味している。この段落の内容は、図１の説明のみならず、本明細書の全図の説明全体にわたって当てはまるとする。
【００１１】
以下、DVB-S.2規格における送信器について各機能に着目した説明を行う。
【００１２】
入力ストリームＤ１０１は、モード適応部１１によって次のような処理が施されて、ストリームＤ１０６として出力される。なお、入力ストリームＤ１０１は、単数入力ストリームの場合と、複数入力ストリームの場合とがある。
【００１３】
モード適応部１１は、入力インターフェース１０１乃至ベースバンドヘッダ出力部１０４を含むように構成されている。
【００１４】
入力ストリームＤ１０１は、モード適応部１１の入力インターフェース１０１に入力されて、ストリームＤ１０２としてCRC-8符号化部１０２に提供される。
【００１５】
CRC-8符号化部１０２は、入力インターフェース１０１からの入力ストリームＤ１０２のうち、同期バイトを除くユーザーパケット部を8bitCRC符号化し、その結果得られるユーザパケットストリームＤ１０３を結合分離部１０３に提供する。
【００１６】
8bitCRC符号化されたユーザパケットストリームＤ１０３は、結合分離部１０３で分割され、データフィールドＤ１０４に転記される。
【００１７】
データフィールドＤ１０４に転記されたユーザパケットストリームは、ベースバンドヘッダ出力部１０４からのベースバンドヘッダＤ１０５と結合し、ベースバンドフレームＤ１０６となり、モード適応部１１から出力されてストリーム適応部１２に提供される。
【００１８】
そして、ベースバンドフレームＤ１０６は、ストリーム適応部１２のベースバンドスクランブル部１０５において、擬似ランダムビット列生成多項式によりスクランブルされる。このスクランブルされたベースバンドフレームＤ１０７は、FEC符号化部１３に提供される。
【００１９】
FEC符号化部１３は、BCH符号化部１０６乃至ビットインタ−リーバ１０８を含むように構成されている。
【００２０】
スクランブルされたベースバンドフレームＤ１０７は、FEC符号化部１３のBCH符号化部１０６に提供されて、そこでBCH符号化され、その出力Ｄ１０８としてLDPC符号化部１０７に提供される。BCH符号化部１０６の出力Ｄ１０８は、LDPC符号化部１０７において、LDPC符号化され、その出力Ｄ１０９は、ビットインタ−リーバ１０８に提供される。そして、LDPC符号化部１０７の出力Ｄ１０９は、ビットインタ−リーバ１０８において、ビットインターリーブ処理が施され、FECフレームＤ１１０となる。このFECフレームＤ１１０は、FEC符号化部１３の出力としてマッピング部１４に提供される。なお、QPSKの場合はビットインターリーブ処理が行われない。
【００２１】
ここで、ビットインターリーブ処理について詳しく説明する。
【００２２】
DVB-S.2規格においては、符号長n=64800bit(標準FECフレーム長)または16200bit(短FECフレーム長)と値が定められている。またLDPC符号化される情報語の長さkは符号長nに符号化率rを掛け合わせたものとして定められている。
【００２３】
LDPC符号化部１０７に入力される情報語が0と1からなる長さk=P×k0のデータであって、図２に示されるように、LDPC符号化部１０７から出力された符号語が0と1からなる長さn=P×n0のデータであるとき、LDPC復号計算部（後述する図６等参照）で用いるparity check matrixは0と1からなるn-k行n列の行列となる。このparity check matrixにおいて、左から長さkの部分を情報部と称し、それより右の長さn-kの部分をパリティ部と称する。
【００２４】
この場合、ビットインタ−リーバ１０８におけるビットインターリーブ方式は、変調方式および符号化率rによって決定される。
【００２５】
例えば、図３は、標準FECフレーム長(64800bit)受信時の8PSK変調方式に関するビットインターリーブ方式を表している。図４は、標準FECフレーム長(64800bit)受信時の16APSK変調方式に関するビットインターリーブ方式を表している。図５は、標準FECフレーム長(64800bit)受信時の32APSK変調方式に関するビットインターリーブ方式を表している。
【００２６】
図３乃至図５において、列方向の実線矢印は受け取った受信値（図１の例ではLDPC符号化部１０７の出力Ｄ１０９）を書き込む方向を表しており、行方向の一点鎖線矢印は受信値をマッピング部１４（最終的にはFEC復号部）に出力する際の読み出す方向を表している。即ち、ビットインタ−リーバ１０８において、データは列方向に書き込まれていき、行方向で順に読み出されることになる。ただし、8PSK, 符号化率3/5のデータに対しては、図３中の点線矢印の方向で読み出されることになる。
【００２７】
図３乃至図５において、３つ乃至５つの四角の枠は受信された1符号語単位であって、各受信値をビットインターリーバ１０８が行列として並べたときの列を表している。図３乃至図５の何れに対しても、(行数)×(列数)= 64800の関係が成立している。
【００２８】
具体的には、列数は1信号点(1シンボル)毎のbit数で定まり、図３に示されるように8(=2^3)PSKなら3列となり、図４に示されるように16(=2^4)APSKなら4列となり、また、図５に示されるように32(=2^5)APSKなら5列となる。一方、行数は64800を列数で割った値であり、図３に示されるように8(=2^3)PSKなら21600行となり、図４に示されるように16(=2^4)APSKなら16200行となり、また、図５に示されるように32(=2^5)APSKなら12960行となる。
【００２９】
図１に戻り、このようにしてビットインタ−リーバ１０８によってビットインターリーバ処理が施された結果得られるFECフレームＤ１１０は、FEC符号化部１３の出力としてマッピング部１４のビットマッピング部１０９に入力され、そこで、決められた変調方式に従ってマッピングされ、さらに、Physical Layerスクランブルおよび同期パイロット信号挿入部１１０と変調部１１１を介して変調されて、最終的に、送信信号Ｄ１１３となって出力される。
【００３０】
以上のような図１の機能的構成を有する送信器からの送信信号（図１の例では送信信号Ｄ１１３）を受信する受信器のうちの、LDPC復号に関係する部分（以下、かかる部分をLDPC復号装置と称する）の機能的構成の概略例が図６に示されている。即ち、図６には、LDPC復号装置の概略として、デマッピング部１５１と、LDPC復号器および関連部分部１５２とが図示されている。
【００３１】
図１の送信器からの送信信号（図１の例では送信信号Ｄ１１３）は、受信器にとっての受信値Ｄ２０１として、デマッピング部１５１のビットデマッパ２０１に入力される。ビットデマッパ２０１は、受信値Ｄ２０１を、その信号の変調方式に基づいてデマップし、その結果得られる出力Ｄ２０２をLDPC復号器および関連部分部１５２に提供する。
【００３２】
具体的には、LDPC復号器および関連部分部１５２は、ビットデインターリーバ２０２とLDPC復号器１５３とを含むように構成されており、このうちのビットデインターリーバ２０２に対して、ビットデマッパ２０１の出力Ｄ２０２が入力される。
【００３３】
ビットデマッパ２０１の出力Ｄ２０２は、ビットデインターリーバ２０２において、ビットデインターリーブ処理が施された後、即ち、図１のビットインターリーバ１０８によって並び替えられた順番から並び替え前の順番に戻す処理が施された後、ビットデインターリーバ２０２の出力Ｄ２０３としてLDPC復号器１５３に提供される。
【００３４】
かかるLDPC復号器１５３は、受信部２０３、LDPC復号計算部２０４、および復号結果メモリ２０５を含むように構成されている。
【００３５】
ビットデインターリーバ２０２の出力Ｄ２０３は、LDPC復号器１５３の受信部２０３においてパリティ並び替え処理が施された上で書き込まれ、１符号語分たまる毎に、出力Ｄ２０４として読み出されて、LDPC復号計算部２０４に提供される。
【００３６】
LDPC復号計算部２０４は、その出力Ｄ２０４に対してLDPC復号計算処理を施す。その復号結果Ｄ２０５は、LDPC復号計算部２０４から出力され、復号結果メモリ２０５を経由して、復号語Ｄ２０６として外部に出力される。その際、LDPC復号器１５３は、より正確なLDPC復号計算処理を実行するため、一般的に軟値受信値を必要とする。
【００３７】
さらに以下、DVB-S.2規格における受信器のうちの、図６のLDPC復号器および関連部分部１５２について、各機能に着目した説明を詳細に行っていく。
【００３８】
ビットデインターリーバ２０２におけるビットデインターリーブ方式（ビットデインターリーブ処理）は、ちょうどビットインターリーバ１０８（図１）で実行した並べ替えを元に戻す処理に該当する。換言すると、ビットデインターリーバ２０２におけるビットデインターリーブ方式（ビットデインターリーブ処理）は、送信時に用いられた変調方式および符号化率rによって決定される。
【００３９】
例えば、図７は、図３のビットインターリーブ方式に対するビットデインターリーブ方式、即ち、標準FECフレーム長(64800bit)受信時の8PSK変調方式に関するビットデインターリーブ方式を表している。図８は、図４のビットインターリーブ方式に対するビットデインターリーブ方式、即ち、標準FECフレーム長(64800bit)受信時の16APSK変調方式に関するビットデインターリーブ方式を表している。図９は、図５のビットインターリーブ方式に対するビットデインターリーブ方式、即ち、標準FECフレーム長(64800bit)受信時の32APSK変調方式に関するビットデインターリーブ方式を表している。
【００４０】
図７乃至図９において、行方向の実線矢印は受け取った受信値（図６の例ではビットデマッパ２０１の出力Ｄ２０２）を書き込む方向を表しており、列方向の一点鎖線矢印は受信値をFEC復号部（図６の例ではLDPC復号器１５３）に出力する際の読み出す方向を表している。
【００４１】
図７乃至図９において、図３乃至図５と同様に、３つ乃至５つの四角の枠は受信された1符号語単位であって、各受信値をビットデインターリーバ２０２が行列として並べたときの列を表している。図７乃至図９の何れに対しても、(行数)×(列数)= 64800の関係が成立している。
【００４２】
具体的には、列数は1信号点(1シンボル)毎のbit数で定まり、図７に示されるように8(=2^3)PSKなら3列となり、図８に示されるように16(=2^4)APSKなら4列となり、また、図９に示されるように32(=2^5)APSKなら5列となる。一方、行数は64800を列数で割った値であり、図７に示されるように8(=2^3)PSKなら21600行となり、図８に示されるように16(=2^4)APSKなら16200行となり、また、図９に示されるように32(=2^5)APSKなら12960行となる。
【００４３】
これらの図７乃至図９に示されるように、ビットデインターリーブ処理として、データは行方向に書き込まれていき、列方向で順に読み出されることになる。ただし、8PSK, 符号化率3/5のデータに対しては、図９中の点線矢印方向で書き込まれることになる。
【００４４】
具体的には例えば、8PSK, 標準FECフレーム長(64800bit)の場合の図７の行列構造は21600行×3列(1要素が1bitに対応)で与えられ、受信値1シンボルにつき1行分ずつ(3bit長)書き込まれていき、読み出すときには列順に読み出されることになる。
【００４５】
このビットデインターリーバ２０２を実装する際、１つの記憶装置に対して読み出しと書き出しを同時に行うと、列方向に対する読み出しが終了する前に行方向に対する新たな受信値の書き込みを行ってしまうことになる。その結果、全ての受信値を正しく読み出してLDPC復号器１５３に送ることができなくなってしまう。そこで、実際には、ビットデインターリーバ２０２は、図１０や図１１に示されるように、パラレルに並べた２つの記憶装置２２１，２２２を搭載しており、これらの２つの記憶装置２２１，２２２に対して、書き込みと読み出しを交互に行うように制御することで、読み出し中のデータが上書きされることを防止している。
【００４６】
また、それぞれの記憶装置２２１，２２２としては、書き込みや読み出しのアドレスを任意に指定できるRAM（Random Access Memory）が一般的に採用されている。
【００４７】
このように、DVB-S.2規格に基づいた従来の受信器では、ビットデインターリーブ処理は、LDPC復号器１５３の外部に外付けされたビットデインターリーバ２０２によって実行されていた。
【００４８】
図６に戻り、LDPC復号器１５３は、このようにビットデインターリーバ２０２によってビットデインターリーブ処理が施された受信値Ｄ２０３（ビットデインターリーバ２０２の出力Ｄ２０３）に対して、LDPC復号処理を施す。
【００４９】
具体的には、LDPC復号器１５３は、parity check matrixとして、0と1からなるn-k行n行の行列を用いる。ここで、n-k=P×(n0-k0)であり、n=P×n0である。そして、LDPC復号器１５３は、parity check matrixのうちの、左から長さk=P×k0の部分が情報部であり、それより右の長さn-k=P×(n0-k0)の部分がパリティ部であるとみなす。
【００５０】
ここで、「0行列か、P×Pの単位行列をcyclic shiftさせた行列、およびそれらの和のいずれかの並びから構成される行列」としてのparity check matrix、または行／列置換による変形によってかかる構造に変換できるparity check matrixに対してLDPC復号計算処理が施される場合、LDPC復号計算部２０４がP個の並列な演算器を含むように構成すれば、それらのP個の並列な演算器を同時に用いることで、より一段と高速なLDPC復号処理が実現できることが知られている。
【００５１】
即ち、DVB-S.2方式で採用されているparity check matrixは行／列置換により、上述した構造を持つ行列へと変換することが可能であることが知られている。
【００５２】
このため、従来のDVB-S.2方式に基づいたLDPC復号器１５３では、P個の並列な演算器を同時に用いたより高速なLDPC復号を行うべく、元のparity check matrixを上述した構造となるように行／列置換処理を施している。
【００５３】
このような行／列置換後の行列の列の順序は、行／列置換前のparity check matrixと比較すると、情報部は同一であるが、パリティ部は異なっている。ただし、列置換前後の列番号には規則性があり、パリティ部の先頭列を0列目とすると、列置換前に(n0-k0)×i＋j（0≦i≦P-1 , 0≦j≦n0-k0-1)列目だった列は、列置換後にP×j+i列目となる。
【００５４】
従って、この方式に従う場合、受信値も列置換に応じた順番で扱わなければならない。即ち、受信値の成分は列置換前の列番号の順になっているが、それをLDPC復号計算処理（図６のLDPC復号計算部２０４の処理）に使うときには列置換後の列番号の順に並び替えなくてはならない。
【００５５】
そこで、ビットデインターリーバ２０２からの出力Ｄ２０３として提供される各受信値を、LDPC復号部１５３の受信部２０３に記録するときには、列置換後の列順に受信値を並べかえて記録する処理、即ち、パリティ並び替えによりparity check matrixを列置換した順に対応するように受信値の位置を変更するといった処理が受信部２０３において実行される。かかる処理が、パリティ並び替え処理である。
【００５６】
以下、例として、図１２のparity check matrix で表現される符号をLDPC復号する際の、パリティ並び替え処理の手順を紹介する。
【００５７】
なお、図１２のparity check matrix では“0”を“.”で表現している。また、図１２のparity check matrix で表現される符号は、符号化率r=2/3であって、符号長108とされているため、n=108 , k=72となる。
【００５８】
図１３は、図１２のparity check matrixを、P×P=6×6の行列を単位として間隔を空けて表示したものである。かかるP×P=6×6の行列の種類としては、6×6の単位行列、その単位行列における1のうち1個が0になった行列、それらのcyclic shiftにより生成される行列、それらの和により生成される行列、および、6×6の0行列といった種類が存在する。
【００５９】
即ち、図１３のparity check matrixは、これらの6×6の行列が縦方向にn0-k0=n/P-k/P=6個、横方向にn0=n/P=18個配置されて構成される行列である。
【００６０】
この図１３の行列は列置換後の行列であり、parity部の列の順序が置換前とは異なっている。
【００６１】
図１４の左方には、行列置換前のparity部が示されており、同図右方には、行列置換後のparity部が示されている。図１５には、行列置換前のparity部、即ち、図１４の左方の拡大図が示されている。図１６には、行置換後であって列置換前のparity部が示されている。図１７には、行列置換後のparity部、即ち、図１４の右方の拡大図が示されている。
【００６２】
図１６と図１７から明らかなように、列置換前に(n0-k0)×i+j=6×i+j(0≦i≦P-1=5 , 0≦j≦n0-k0-1=5)列目だった列は、列置換後にP×j+i=6×j+i列目の列に置換されていることがわかる。
【００６３】
このようなparity check matrixの列置換にあわせて、受信値のパリティ部でも（n0-k0)×i+j=6×i+j(0≦i≦P-1=5 , 0≦j≦n0-k0-1=5)番のデータを、P×j+i=6×j+i番の位置へ並び替える、といったパリティ並び替え処理を実行することが必要である。ただし、受信値のパリティ部の先頭データを0番目としている。
【００６４】
以下では、このようなパリティ並び替え処理を実現する具体的な手法について説明する。
【００６５】
従来、DVB-S.2規格に基づいた従来の受信器(図６)によるパリティ並び替え処理は、上述したように、LDPC復号器１５３の受信部２０３において実行されていた。
【００６６】
ここで、LDPC復号器１５３のLDPC復号計算部２０４によるP=6並列LDPC復号計算処理の実現を考える。このため、LDPC復号計算部２０４は、LDPC復号計算処理を実行可能な計算器を６個並列的に備える構成を有しているとする。以下、これらの６個の計算器をまとめて、6並列LDPC復号計算器と称する。
【００６７】
この場合、図１３の例のparity check matrixで表現される符号語は、図１８の上側の図に示されるようになる。そこで、図１８の下側の図に示されるように、word長108/6 = 18, １word毎にP=6個の受信値を格納できる30bit×18 wordsのRAMとして構成される記憶装置２３１（以下、受信値メモリ２３１と適宜称する）が、LDPC復号器１５３の受信部２０３に搭載されているとする。
【００６８】
また、この受信値メモリ２３１を用いるとき、受信値の量子化bitを5bitずつとし、シリアルに入力された軟値受信値を受信値メモリ２３１に１符号語分書き込み、1word(すなわち受信値6個分)単位でパラレルに受信値メモリ２３１から読み出した受信値（図１８の下側の図の各楕円枠Ru内の受信値）を同時にLDPC復号計算部２０４に入力させることで、そのLDPC復号計算部２０４における6並列LDPC復号計算器が、まとめてLDPC復号計算処理を実行できるようになる。
【００６９】
ここで、説明を簡便なものとすべく、bit方向番号と称する単位を定義する。
【００７０】
即ち、受信値メモリ２３１のbit幅をP等分し、それぞれに対して最上位bit桁(MSB)から順に0, 1,・・, P-1と番号を付していくとする。かかる番号が、bit方向番号である。この場合、P等分されたbit幅1区間（bit方向番号単位）ごとに軟値受信値１個が受信値メモリ２３１に記憶されていくこととなる。
【００７１】
具体的には例えば本例では、図１８の下側の図に示されるように、受信値メモリ２３１の持つ30bit幅が5bitずつP=6等分される。そして、5bit間隔で、最上位bit(MSB)から降順に、番号0, 1, ・・, (P-1=)5が割り振られる。かかる番号が、本例でのbit方向番号である。
【００７２】
また、図１８の上側の図に示されるように、受信部２０３から読み出される際の１符号語の各要素に対して、先頭の要素から順に番号が付されていくとする。例えばここでは、先頭の要素の番号として0が付され、それ以降１ずつインクリメントされていくとする。なお、以下、受信部２０３から読み出される際の符号語を、出力符号語と適宜称し、その出力符号語の要素、即ち、番号が付された要素を、要素データと適宜称する。また、以下でいう受信値とは、出力符号語の所定の要素データに対応している。
【００７３】
また、ここでは、受信値は受信部２０３に対してシリアル入力されるため、各受信値を任意の位置に書き込むことができるパーシャルライト可能なRAMが、受信値メモリ２３１として受信部２０３に搭載されているとする。
【００７４】
このとき、出力符号語の各要素データの受信値メモリ２３１上での格納位置は、図１８の下側の図の受信値メモリ２３１の構造を示す枠内の数字で表されている。即ち、出力符号語の各要素データは、受信値メモリ２３１内でbit方向番号の昇順に格納されていることとなる。詳細には、出力符号語のうちのP×x+y番の要素データは、受信値メモリ２３１上で(bit方向番号, word方向アドレス) = (x, y)の位置に格納されていることになる。
【００７５】
引き続き、このような受信値メモリ２３１が搭載された受信部２０３におけるパリティ並び替え処理の手順について説明する。
【００７６】
受信語の先頭の受信値から数えて、受信部２０３に到来する順番がk番目よりも前の受信値とは、情報部に対応する。このように情報部に対応している受信値については、受信値メモリ２３１上においては、符号語の先頭の要素データの配置位置から数えて、その到来順番の位置にそのまま配置させればよい。
【００７７】
例えば本例では、k=72であるので、受信語の先頭の受信値から数えて60番目に到来する受信値は、k=72番目以前の受信値であるため、情報部に対応している。このように情報部に対応している受信値については、受信値メモリ２３１上においては、符号語の先頭の要素データの配置位置から数えて、60番目の位置にそのまま配置させればよい。
【００７８】
一方、受信語の先頭の受信値から数えて、受信部２０３に到来する順番がk番目以降の受信値とは、即ち、k+(n0-k0)×i+j= 72+6×i+j番目の受信値とは、パリティ部に対応する。そこで、k+(n0-k0)×i+j= 72+6×i+j番目に受信したパリティ部の受信値は、受信値メモリ２３１上においては、k+P×j+i= 72+6×j+i番の位置に格納させるようにすればよい。
【００７９】
例えば、受信語の先頭の受信値から数えてk+(n0-k0)×2+1=72+6×2+1=85番目に受信された受信値は、パリティ部に対応するので、受信値メモリ２３１上においては、符号語の先頭の要素データの配置位置から数えて、k+P×1+1=72+6×1+2=80番目の位置に配置させればよい。
【００８０】
上述したように出力符号語の各要素データは、受信値メモリ２３１内でbit方向番号の昇順に格納されているので、出力符号語でP×x+y番目の要素データに対応する受信値メモリ２３１の位置は、word方向アドレスx番目、bit方向番号y番目の位置ということになる。
【００８１】
以上の内容を書き込み処理の観点から説明すると、受信部２０３に対して受信語がシリアルに入力されてくる。従って、受信語の先頭の受信値から数えて、受信部２０３に到来する順番がk番目よりも前の受信値は、情報部に対応する。そこで、図１９の上側の図に示されるように、情報部に対応する受信値が入力されている間は、それらの各受信値は、bit方向に順次書き込まれていく。
【００８２】
ここで、図１９の上側の図の受信値メモリ２３１の構造を示す枠内の数字は、受信部２０３に対して受信語がシリアルに入力（到来）されてくる場合の各受信値の到来順番を示している。一方、図１９の下側の図の受信値メモリ２３１の構造を示す枠内の数字は、図１８の下側の図と同様に、受信値メモリ２３１から読み出されてLDPC復号計算部２０４（図６）に提供される出力符号語の各要素データの番号（格納位置の番号）を示している。
【００８３】
そこで、図１９の下側の図の各番号と比較しつつ、図１９の上側の図を用いて再度書き込みの説明をしていく。受信語の先頭の受信値から数えてP×x+y , P×x+y+1,・・・番目に受信された受信値、即ち情報部に対応する受信値はそのまま、word方向アドレスx, x , ・・・番目、bit方向番号y , y+1 , ・・・番目の位置に順次書き込まれていく。このことは、例えば、受信語の先頭の受信値から数えて60 , 61番目に受信された受信値の書き込み位置（図１９の上側の図の番号60 , 61の位置）は、そのまま出力符号語の60 , 61番目の要素データを格納する位置（図１９の下方の番号60 , 61の位置）となっていることからも確認できる。
【００８４】
その後、受信部２０３には、パリティ部に対応する受信値が到来されてくることになるので、このような場合、次のような書き込みが行われる。即ち、パリティ部に対応するk+（n0-k0)×i+j, k+(n0-k0)×i+j+1,・・・番目に受信された受信値は、受信値メモリ２３１上のword方向アドレスk0+j , k0+j+1, ・・・番目、bit方向番号I , i, ・・・番目の位置に順次書き込まれていくことになる。即ち、パリティ部に対応する受信値については、受信値メモリ２３１上のword方向に書き込まれていくことになる。これにより、パリティ並び替え処理が実現されることになる。
【００８５】
このことは、図１９の上側の図の枠内の数字からも確認できる。例えば、受信語の先頭の受信値から数えてk+(n0-k0)×2+1=72+6×2+1=85 , k+(n0-k0)×2+2=72+6×2+2=86, ・・・番目に受信された受信値は、図１９の上側の図に示されるように、受信値メモリ２３１上のword方向に書き込まれていくことがわかる。この場合、図１９の下側の図と比較するに、かかる85 , 86, ・・・番目に受信された受信値の書き込み位置（図１９の上側の図の番号85 , 86, ・・・の位置）は、確かに出力符号語のk+P×1+2=72+6×1+2= 80 , k +P×2+2=72+ 6×2+2=86,・・・番目の要素データを格納する位置（図１９の下側の図の番号80 , 86, ・・・の位置）となっていることがわかる。
【００８６】
以上図１９を用いて説明した手法、即ち、受信部２０３にシリアル入力された受信値を１つずつ書き込むときの受信値メモリ２３１上の位置を工夫する手法を採用することで、parity check matrix の列置換に合わせたパリティ並び替え処理が実現可能となる。
【００８７】
そして、かかるパリティ並び替え処理によって１符号語分の書き込みが行われた後、図１８の下側の図の各楕円枠Ru単位、即ち、1word(受信値6個分)単位でパラレルに受信値メモリ２３１から受信値が同時に読み出されて、LDPC復号計算部２０４に提供されることで、そのLDPC復号計算部２０４における6並列LDPC復号計算器が、まとめてLDPC復号計算処理を実行できるようになる。
【００８８】
ただし、かかるパリティ並び替え処理を実現するためには、受信部２０３へ入力される受信値がシリアルに入力されること、および、シリアル入力されてくる各受信値を任意の位置に格納できる記憶装置２３１(例えばパーシャルライトが可能な受信値メモリ２３１)を受信部２０３に搭載することが必要になることは上述した通りである。
【００８９】
図６に戻り、このようにして、ビットデインターリーバ２０２によるビットデインターリーブ処理と、受信部２０３によるパリティ並び替え処理との各処理によって、順序変更がなされた受信値Ｄ２０４は、続いてLDPC復号計算部２０４に入力され、LDPC復号計算処理の復号結果Ｄ２０５が出力される。
【００９０】
この場合、LDPC復号計算部２０４は、上述したように、parity部が置換された行列を用いるので、受信値のparity部もその置換に応じた順番でLDPC復号計算処理に使われることになり、そのような順番の復号結果Ｄ２０５が出力される。即ち、LDPC復号計算処理で得られた復号結果Ｄ２０５は、列置換後の列番号の順になっている。
【００９１】
そこで、復号結果メモリ２０５から復号語Ｄ２０６として出力するためには、対応する復号結果Ｄ２０５を列置換前の列番号の順に戻すことが必要である。即ち、LDPC復号計算部２０４の復号結果Ｄ２０５は、復号結果メモリ２０５の内部では列置換後の列番号の順に並ぶように記録される。そこで、復号語Ｄ２０６として出力するときには列置換前の列番号の順で出力することが必要である。
【００９２】
この場合、情報部については、LDPC復号計算部２０４のLDPC復号計算処理が終わった時点の順番と一致するが、parity部については一致しない。従って、詳細については省略するが、上述したパリティ並び替え処理の逆処理、即ち、パリティ並び替え処理と反対の順に、parity部を並び替える処理を実行して、列置換前の列番号の順に復号結果を並べることで、列置換前の列番号の順となった復号語Ｄ２０６の出力が可能になる。
【００９３】
以上説明したように、従来のLDPC復号器１５３内には、符号長分の受信値メモリ（図１８等の受信部２０３の受信値メモリ２３１）や復号結果メモリ２０５が設けられており、受信値を受信値メモリに格納する際にパリティ並び替え処理が実行され、復号結果メモリ２０５に格納されている復号結果を読み出す際にもパリティの逆並び替え処理が実行されている。また、LDPC復号器１５３の前段には、ビットデインターリーバ２０２が存在し、かかるビットデインターリーバ２０２には、符号長分の2個の受信値メモリ（図１０や図１１の記憶装置２２１，２２２）が搭載されている。
【非特許文献１】R. G. Gallager, "Low Density Parity Check Codes", Cambridge, Massachusetts: M. I. T. Press, 1963
【非特許文献２】D. J. C. MacKay, "Good error correcting codes based on very parse matrices", Submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999
【非特許文献３】M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, "Analysis of low density codes and improved designs using irregular graphs", in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998
【発明の開示】
【発明が解決しようとする課題】
【００９４】
しかしながら、LDPC復号処理では受信値が軟値であり、そのLDPC復号処理を高精度に実行するためには、受信値の量子化ビット数を多くとる必要がある。その結果、その分だけ、受信部２０３内の受信値メモリや、ビットデインターリーバ２０２内の受信値メモリが増大してしまう、という問題が生ずることになる。
【００９５】
特に、DVB-S2方式の様な符号長が長い方式が採用される場合などには、これらの受信値メモリの増大の問題は、そのまま回路規模増加という深刻な問題に直結する。
【００９６】
本発明は、このような状況に鑑みてなされたものでありLDPC復号装置の回路規模縮小を図ることを目的とするものである。
【課題を解決するための手段】
【００９７】
本発明の一側面の復号装置は、ビットインターリーブ処理が施された符号語であって、パリティ部を含む符号語を単位として復号する復号装置であって、前記符号語の長さ分のデータ容量を少なくとも有する格納手段と、前記符号語の各要素を受信値として受信したとき、前記受信値に対してビットデインターリーブ処理とパリティ並び替え処理とを施して、前記受信値を前記格納手段に格納する制御を実行する受信手段とを備える。
【００９８】
前記符号語の前記各要素に対応する前記受信値のそれぞれは、前記受信手段に対してシリアルに入力される。
【００９９】
前記格納手段は、前記受信値を任意の位置に格納できる構成を有している。
【０１００】
前記受信値は軟値である。
【０１０１】
前記復号装置は、低密度パリティ検査符号(Low Density Parity-Check code,LDPC符号)を復号する復号装置である。
【０１０２】
前記格納手段は、RAM（Random Access Memory）で構成されている。
【０１０３】
本発明の一側面の復号方法およびプログラムは、上述した本発明の一側面の復号装置に対応する方法およびプログラムである。
【０１０４】
本発明の一側面の復号装置および方法並びにプログラムにおいては、ビットインターリーブ処理が施された符号語であって、パリティ部を含む符号語を単位として復号される場合に、次のような処理が実行される。即ち、前記符号語の長さ分のデータ容量を少なくとも有するメモリが存在し、前記符号語の各要素が受信値として受信されたとき、前記受信値に対してビットデインターリーブ処理とパリティ並び替え処理とが施されて、前記受信値が前記メモリに格納される。
【発明の効果】
【０１０５】
本発明によれば、ビットインターリーブ処理が施された符号語であって、パリティ部を含む符号語を単位として復号する復号装置を提供できる。特に、その回路規模を従来より縮小できるようになる。
【発明を実施するための最良の形態】
【０１０６】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、明細書または図面における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、明細書または図面に記載されていることを確認するためのものである。従って、明細書または図面中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【０１０７】
さらに、この記載は、明細書または図面に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、明細書または図面に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定するものではない。
【０１０８】
本発明の一側面の復号装置は、ビットインターリーブ処理が施された符号語であって、パリティ部を含む符号語（例えば図１８の上側の図の符号語）を単位として復号する復号装置（例えば図２０のLDPC復号装置）において、
前記符号語の長さ分のデータ容量を少なくとも有する格納手段（例えば図２１や図２２の受信値メモリ３３１や、図２３の受信値メモリ３５１）と、
前記符号語の各要素を受信値として受信したとき、前記受信値に対してビットデインターリーブ処理とパリティ並び替え処理（例えば図２２や図２３の手法に従った処理）とを施して、前記受信値を前記格納手段に格納する制御を実行する受信手段（例えば図２０の受信部３０２）と
を備える。
【０１０９】
次に、図面を参照して、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【０１１０】
図２０は、本発明が適用されるLDPC復号装置の機能的構成の概略例を示している。即ち、図２０には、図６の従来のLDPC復号装置との比較を容易なものとすべく、LDPC復号装置の構成要素として、デマッピング部２５１とビットデインターリーバ内蔵LDPC復号器２５２とのみが図示されている。
【０１１１】
詳細については後述するが、図６と図２０との比較から明らかなように、本発明が適用される図２０のLDPC復号装置では、従来のLDPC復号器１５３の前段に存在していたビットデインターリーバ２０２は排除されている。このため、本発明が適用される図２０のLDPC復号装置は、LDPC復号器２５３の受信部３０２の記憶装置（以下、適宜受信値メモリとも称する）に受信値Ｄ３０２を格納する際に、パリティ並び替え処理とともに、ビットデインターリーブ処理を実行することとしている。
【０１１２】
これにより、従来のビットデインターリーバ２０２に搭載されていた２個の受信値メモリ（例えば図１０や図１１の記憶装置２２１，２２２）の削減が可能になり、その結果、LDPC復号装置全体としても、従来より回路規模の縮小を図ることができるのである。
【０１１３】
なお、以下、このような本発明が適用される図２０のLDPC復号装置を、ビットデインターリーバ内蔵LDPC復号装置と適宜称する。
【０１１４】
ビットデインターリーバ内蔵LDPC復号装置のデマッピング部２５１は、図６のデマッピング部１５１と基本的に同様の機能と構成を有している。即ち、デマッピング部２５１の出力Ｄ３０２と、図６のデマッピング部１５１の出力Ｄ２０２とは、送信器側で同様のデータを送信した場合には同様のデータとなる。
【０１１５】
かかるデマッピング部２５１の出力Ｄ３０２は、受信値単位でシリアルに、ビットデインターリーバ内蔵LDPC復号器２５２に入力される。
【０１１６】
このビットデインターリーバ内蔵LDPC復号器２５２には、上述したように、ビットデインターリーバ２０２（図６）は存在せず、従来のLDPC復号器１５３の代わりに、LDPC復号器２５３が設けられている。LDPC復号器２５３は、受信部３０２、LDPC復号計算部３０３、および復号結果メモリ３０４を含むように構成されている。
【０１１７】
受信部３０２には、デマッピング部２５１の出力Ｄ３０２が入力される。そこで、受信部３０２は、デマッピング部２５１の出力Ｄ３０２に対してビットデインターリーブ処理とパリティ並び替え処理とを同時実行する。かかる受信部３０２の処理については、図２１乃至図２４を参照して後述する。
【０１１８】
このように、受信部３０２ではビットデインターリーブ処理とパリティ並び替え処理とが並列的に同時実行されるので、その受信部３０２の出力Ｄ３０３は、送信器側で同様のデータを送信した場合には、従来の受信部２０３の出力Ｄ２０４と同様のデータとなる。
【０１１９】
よって、LDPC復号計算部３０３と復号結果メモリ３０４とは、図６の従来のLDPC復号計算部２０４と復号結果メモリ２０５と基本的に同様の機能と構成を有するようにすることができる。即ち、LDPC復号計算部３０３と復号結果メモリ３０４として、図６の従来のLDPC復号計算部２０４と復号結果メモリ２０５とをそのまま採用することができる。
【０１２０】
ただし、注意すべき点は、本実施の形態で用いる受信語の例は、従来の説明で用いた受信語の例とは異なる点である。即ち、従来の説明では、その説明の簡略上、8PSK, 符号長108，符号化率r=2/3，P=6とされていた（図１８等参照）。これに対して、本実施の形態では、後述するように、8PSK, 符号長64800，符号化率r=2/3とされ、また、P=360とされている。
【０１２１】
即ち、DVB-S.2規格で与えられたparity check matrixを用いたLDPC復号処理においては360個(=P個)の受信値に対して並列にLDPC復号演算処理を実行できるようになっている。かかるLDPC復号演算処理が、本実施の形態のLDPC復号計算部３０３（図２０）に採用されている。即ち、本実施の形態では、計算時間削減のため、受信部３０２からLDPC復号計算部３０３に対しては、１時刻につき受信値が360個分パラレルに読み込まれ、その結果、LDPC復号計算部３０３における360並列LDPC復号計算器が、まとめてLDPC復号計算処理を実行するのである。
【０１２２】
換言すると、この点を除けば、本発明のビットデインターリーバ内蔵LDPC復号装置は、ビットデインターリーブ処理とパリティ並び替え処理を受信部３０２で同時に実行できる点が、従来のLDPC復号装置（図６参照）との差異点となっている。
【０１２３】
そこで、以下、かかる差異点、即ち、ビットデインターリーブ処理とパリティ並び替え処理を受信部３０２で同時に実行できる点について、図２１乃至図２４を用いて詳細に説明していく。
【０１２４】
図２１の上側の図は、本発明が適用される受信部３０２に搭載される受信値メモリ３３１の構成例であって、受信部３０２に受信される受信語がDVB-S.2規格に基づいた8PSK, 符号長64800, 符号化率r=2/3とされている場合に採用可能な構成例を示している。この場合、DVB-S.2規格に基づいた8PSK, 符号長64800, 符号化率r=2/3の受信語のLDPC復号処理においては、n=64800, k=43200,n0=180, k0=120と定まることになる。
【０１２５】
なお、本実施の形態では例えば、受信語は受信値単位で受信部３０２に対してシリアルに入力されてくるため、各受信値を任意の位置に書き込むことができるパーシャルライト可能なRAMが、受信値メモリ３３１として受信部３０２に搭載されているとする。
【０１２６】
また、LDPC復号計算部３０３における360並列LDPC復号計算器がまとめてLDPC復号計算処理を実行できるようにすべく、受信部３０２の受信値メモリ３３１は次のように構成されているとする。即ち、1word(1列)につき360個の軟値受信値を記憶して1時刻に1wordを同時に読み出せるように、そのword数とbit幅が定められた受信値メモリ３３１が採用されているとする。具体的には、軟値受信値1つの量子化ビット数を5bitとする場合の例として、bit幅が5×360=1800bitであって、word数が64800/360=180の受信値メモリ３３１が採用されているとする。
【０１２７】
また、以下、受信部３０２から読み出される際の１符号語（出力符号語）の各要素データに対して、先頭要素データから順に番号が付されていくとする。例えばここでは、先頭要素データの番号として0が付され、それ以降の要素データに対しては、１ずつインクリメントされた値が付されていくとする。
【０１２８】
このとき、出力符号語の各要素データの受信値メモリ３３１上での格納位置が、図２１の上側の図の受信値メモリ３３１の構造を示す枠内の数字で表されている。即ち、出力符号語の各要素データは、受信値メモリ３３１内でbit方向番号の昇順に格納されていることとなる。詳細には、出力符号語のうちのP×x+y番の要素データは、受信値メモリ３３１上で(bit方向番号, word方向アドレス) = (x, y)の位置に格納されることになる。
【０１２９】
この例の場合、8PSK変調された符号化率r=2/3の受信語が受信部３０２にシリアル入力されることになるため、受信部３０２におけるビットデインターリーブ方式（ビットデインターリーブ処理）は、上述した図７で示される方式となる。
【０１３０】
従って、受信値メモリ３３１上において、隣の時刻に受信された受信値との間隔が、受信値数にして64800/3=21600個分だけ空くように各受信値が配置（書き込み）されれば、ビットデインターリーブ処理が施されたことになる。
【０１３１】
即ち、受信値メモリ３３１では、1word(1列)につき、上述したように360個の受信値が格納される。よって、隣通しで受信された受信値同士の格納の関係では、図２１の下側の図の矢印で示されるように、word数としては、21600/360=60個分ずらしてそれぞれ格納されればよいことになる。
【０１３２】
即ち、図２１の下側の図の受信値メモリ３３１の構造を示す枠内の数値は、受信部３０２に対して受信語がシリアルに入力（到来）されてくる場合の各受信値の到来順番を示している。受信部３０２での受信値の書き込みの観点から換言すると、受信値は到来順に書き込まれていくので、各受信値の書き込み順番を示しているともいえる。
【０１３３】
ビットデインターリーブ処理を実行するためには、図２１の下側の図から明らかなように、受信部３０２での受信値の書き込み時においては、横(word方向)にn0/3=60wordおきに書き込まれればよい。即ち、図１９の上側の図を用いて上述したように、出力符号語のj×360+i番目の要素データの位置は、bit方向番号: i, word方向アドレス: jの位置となっている。従って、隣り合う時刻に到来した２つの受信値は、必ず互いの位置が要素64800/3=21600個分ずれた位置に書き込まれることとなり、その結果、ビットデインターリーブ処理が施されたことになる。
【０１３４】
さらに、本実施の形態の受信部３０２は、ビットデインターリーブ処理とパリティ並び替え処理とを同時に実行すべく、次のような処理を実行することができる。
【０１３５】
即ち、受信部３０２は、受信値の到来順番に基づいてパリティ部であるか否かを直接判断し、パリティ部であると判断した受信値、即ち、パリティ部に書き込まれる順番の受信値に対してはパリティ並び替えも行うことで、ビットデインターリーブ処理とパリティ並び替え処理との同時実行を実現する。
【０１３６】
換言すると、上述したように、情報部に対応する受信値に対してはビットデインターリーブ後の並び替えは行われない。そこで、受信部３０２は、情報部であると判断した受信値、即ち、情報部に書き込まれる順番の受信値に対しては、図２１を用いて説明した手法、即ち、ビットデインターリーブ処理のみを実行する手法に従って、その受信値を受信値メモリ３３１に書き込む。
【０１３７】
例えば本実施の形態の場合、8PSK, 符号化率r=2/3の変調方式に基づく受信値が受信部３０２に入力されるため、最初に受信された受信値の順番を0番目とするとき、3で割って2余る値の順番で受信部３０２に入力された受信値はすべてパリティ部に対応し、それ以外の受信値は情報部に対応することがわかる。
【０１３８】
従って、受信部３０２は、図２２に示される手法で、各受信値を受信値メモリ３３１に順次書き込んでいくことで、ビットデインターリーブ処理とパリティ並び替え処理との同時実行を実現する。
【０１３９】
即ち、図２２の受信値メモリ３３１の構造を示す枠内の数字は、受信部３０２に対して受信語がシリアルに入力（到来）されてくる場合の各受信値の到来順番を示している。受信部３０２での受信値の書き込みの観点から換言すると、受信値は到来順に書き込まれていくので、各受信値の書き込み順番を示しているともいえる。
【０１４０】
この場合、3で割って割り切れる値、または3で割って1余る値の順番で受信部３０２に入力された受信値は、図２２の情報部における実線矢印で示される順番、即ち、書き込み順番に従って、横(word方向)にn0/3=60wordおきに受信値メモリ３３１に書き込まれていくとする。これにより、出力符号語の要素データとして受信値メモリ３３１から読み出されるときには1wordずつ縦にパラレルで読み出されること（図２２の各楕円枠Ru内の１つの要素データとして読み出されること）を考慮すれば、隣の時刻に到来した受信値同士の間隔は、受信値数にして64800/3=21600個分開いて読み出されることとなり、受信語の情報部に対してビットデインターリーブ処理が施されたことになる。
【０１４１】
一方、3で割って2余る値の順番で受信部３０２に入力された受信値は、パリティ部に対応する。
【０１４２】
ここで、これらのパリティ部に対応する受信値も、情報部に対応するものと同じく、図２２の受信値メモリ３３１上のパリティ部配置領域（出力符号語のパリティ部を記憶する位置）におけるカッコ内の数値のbit方向位置に一旦配置されるとする。これにより、ビットデインターリーブ処理が施されたこととなる。例えば、5番目の受信値については、（５）の位置に配置された時点で、ビットデインターリーブ処理が施されたこととなる。
【０１４３】
さらに、パリティ部に対応する受信値については、受信値メモリ３３１上のパリティ部配置領域におけるカッコ無しの数値で指定された位置に配置換えすること、即ち、図２２の点線矢印で示される書込み順番の様にword方向に書き込むことで、図１９を用いて説明した場合と同様のパリティ並び替え処理が施されたことになる。例えば、5番目の受信値については、（５）の位置から、５の位置に書き込むことで、パリティ並び替え処理が施されたことになる。
【０１４４】
そこで、パリティ部に対応する受信値を、図２２の受信値メモリ３３１上のパリティ部配置領域に配置させる場合、カッコ内の数値のbit方向位置に配置させる処理を省略して、カッコ無しの数値で指定された位置に直接書き込めば、ビットデインターリーブ処理とパリティ並び替え処理とが同時に実行されたことになる。例えば、5番目の受信値については、（５）の位置への配置を省略して、５の位置に直接書き込むことで、ビットデインターリーブ処理とパリティ並び替え処理とが同時に実行されたことになる。
【０１４５】
以上、8PSK変調方式において、符号化率r=2/3の場合を例にして説明した。ただし、上述した手法は、かかる例のみに適用可能ではなく、より一般的に任意の符号化率rが与えられた場合にも適用可能である。即ち、8PSK変調方式において、任意の符号率rが与えられた場合であっても、上述した手法と基本的に同様の手法を採用することで、ビットデインターリーブ処理とパリティ並び替え処理との同時実行が実現できる。以下、このことについて、さらに説明する。
【０１４６】
LDPC符号化部（図１の例の送信器の場合にはLDPC符号化部１０７）に入力される情報語を0と1からなる長さk=P×k0のデータ、LDPC符号化部から出力された符号語を0と1からなる長さn=P×n0のデータとすると、符号化率r=k0/n0という関係が成立する。
【０１４７】
ここで、理解を容易なものとすべく、上述した例と同様に、n=64800 , k=64800×r , P=360 , n0=180 , k0=180×r , 2/3≦rであるとして以下の説明を行うものとする。勿論、n0 , k0 , Pが任意に与えられた場合であっても、以下の説明と同様の手法を採用することで、ビットデインターリーブ処理とパリティ並び替え処理との同時実行が容易に実現できることは言うまでもない。
【０１４８】
図２３は、8PSK, 符号長64800, 符号化率r の受信語を受信部３０２で受信し、ビットデインターリーブ処理とパリティ並び替え処理とを同時に実行する手法の一例であって、各受信値を矢印で表した順に書き込んでいく手法を説明する図である。
【０１４９】
即ち、ここでは、受信部３０２には、図２３の構成を有する受信値メモリ３５１が搭載されているとする。この受信値メモリ３５１の構造を示す枠内の数字は、受信部３０２に対して受信語がシリアルに入力（到来）されてくる場合の各受信値の到来順番を示している。受信部３０２での受信値の書き込みの観点から換言すると、受信値は到来順に書き込まれていくので、各受信値の書き込み順番を示しているともいえる。
【０１５０】
この場合、図２３に示されるように、出力符号語の各要素データが格納されている位置のword方向アドレスがk0未満ならば、その要素データは情報部に含まれるものであり、k0以上ならばその要素データはパリティ部に含まれるものであることがわかる。
【０１５１】
また、この例では変調方式として8PSKを用いており、受信部３０２におけるビットデインターリーブ方式（ビットデインターリーブ処理）は、上述した図７で示される方式となる。
【０１５２】
この場合、r=k0/n0より、n0×（2/3）=120≦k0の関係が成立することがわかる。従って最初に受信された受信値の順番を0番目とするとき、3で割って割り切れる値、または3で割って1余る値の順番で受信部３０２に入力された受信値は、情報部に対応するため、図２３の情報部における実線矢印で示される順番、即ち、書き込み順番に従って、横(word方向)にn0/3=60wordおきに受信値メモリ３５１に書き込まれていくとする。これにより、出力符号語の要素データとして受信値メモリ３５１から読み出されるときには1wordずつ縦にパラレルで読み出されること（図２３の各楕円枠Ru内の１つの要素データとして読み出されること）を考慮すれば、隣の時刻に到来した受信値同士の間隔は、受信値数にして64800/3=21600個分開いて読み出されることとなり、受信語の情報部に対してビットデインターリーブ処理が施されたことになる。
【０１５３】
一方、3で割って2余る値の順番で受信部３０２に入力された受信値についての取扱いは次の通りとなる。
【０１５４】
これらの受信値は、横方向(word方向)にn0/3=60wordおきに受信値を受信値メモリ３５１に書き込んでいくとき、図２３から明らかなように、(word方向アドレス, bit方向番号) = (60s + u, w)の位置に受信値が書き込まれてから、(word方向アドレス, bit方向番号) = (60s + u + 1, w)の位置に別の受信値が書き込まれるまで、3word分の受信値(個数: 360×3=1080個)が到来していることがわかる。ただし、0≦s≦2 , 0≦u≦59 , 0≦w≦359の関係が成立する場合のことである。
【０１５５】
また、パリティ部に最初に書き込まれる受信値の格納位置は、(word方向番号, bit方向番号)=（k0 , 0)であり、(word方向番号, bit方向番号)=(120, 0)に書き込まれる受信値が到来する順番は２番目となる。よって、パリティ部に最初に書き込まれる受信値が到来する順番は、1080×(k0-120)+2の値の順番となる。
【０１５６】
従って、受信の順番（到来順番）が、3で割って2余る値の順番のうちの、1080×(k0-120)+2の値の順番より前である受信値は、word方向アドレスがk0より小さな格納位置に書き込まれる受信値となるので、情報部に対応する。
【０１５７】
即ち、かかる順番で受信部３０２に入力された受信値についても、3で割って割り切れる値、または3で割って1余る値の順番で受信部３０２に入力された受信値と全く同様に、図２３の情報部における実線矢印で示される順番、即ち、書き込み順番に従って、横(word方向)にn0/3=60wordおきに受信値メモリ３５１に書き込まれていけばよい。これにより、出力符号語の要素データとして受信値メモリ３５１から読み出されるときには1wordずつ縦にパラレルで読み出されること（図２３の各楕円枠Ru内の１つの要素データとして読み出されること）を考慮すれば、隣の時刻に到来した受信値同士の間隔は、受信値数にして64800/3=21600個分開いて読み出されることとなり、受信語の情報部に対してビットデインターリーブ処理が施されたことと等価になる。
【０１５８】
一方、受信（到来）の順番が、3で割って2余る値の順番のうちの1080×(k0-120)+2の値の順番より後である受信値は、word方向アドレスがk0より大きな格納位置に書き込まれる受信値となるので、パリティ部に対応する。
【０１５９】
より具体的には、iを0≦i≦P-1= 359の間を動く整数とし、jを0≦j≦n0-1-k0の間を動く整数とする。すると、1080×(k0-120)+2+3×(n0-k0)×i+3×jの値の順番で到来する受信値は、3で割って2余る値の順番であり、かつ1080×(k0-120)+2の値の順番以降の順番で到来した受信値となるから、受信値メモリ３５１上のパリティ部配置領域（出力符号語のパリティ部を記憶する位置）に書き込まれることになる。
【０１６０】
以下、パリティ部に対応する受信値についての、受信値メモリ３５１上のパリティ部配置領域内の具体的な書き込み位置について説明する。
【０１６１】
そこで、以下、パリティ部配置領域に最初に書き込まれる受信値に対する番号として0番を付すとして、以後、到来した受信値の中から、パリティ部に書き込まれる受信値のみを順次取り出して、即ち、1080×(k0-120)+2+3×(n0-k0)×i+3×jの値の順番で到来する受信値のみを順次取り出して、取り出される毎に、各受信値に対して、１つずつカウントアップした番号を付していくとする。以下、かかる順番をパリティ書込順番と称する。
【０１６２】
すると、1080×(k0-120)+2+3×(n0-k0)×i+3×jの値の順番で到来してきた受信値は、パリティ書込順番に換算するとi×(n0-k0)+jの値の順番で、図２３の受信値メモリ３５１上のパリティ部配置領域に書き込まれる受信値となる。
【０１６３】
例えば、1080×(k0-120)+2+3×(n0-k0)×0+3×0=1080×(k0-120)+2 , 1080×(k0-120)+2+3×(n0-k0)×0+3×1=1080×(k0-120)+5 , ・・・ , 1080×(k0-120)+2+3×(n0-k0)×1+3×1番目にそれぞれ到来した各受信値は、パリティ書込順番に換算すると0 , 1, ・・・ , n0-k0+1の各値の順番で、図２３の受信値メモリ３５１上のパリティ部配置領域に書き込まれていくことになる。
【０１６４】
ここで、パリティ並び替え処理とは、上述したように、パリティ書込順番の観点でいえば、(n0-k0)×i+j(0≦i≦P-1=359, 0≦j≦n0-k0-1)番のデータを、P×j+i=359×j+i番の位置へ並び替えることと等価である。
【０１６５】
一方、上述したように、図２３の受信値メモリ３５１から出力される符号語の各要素データの番号の観点でいえば、図２４の上側の図に示されるように、各要素データは受信値メモリ３５１内でbit方向番号の昇順に格納されていることになるので、符号語のパリティ部内においてP×j+i番の要素データに対応する受信値メモリ３５１上の格納位置は、word方向アドレスk0+j番目、bit方向番号i番目の位置ということになる。ただし、0≦j≦n0-k0-1 , 0≦i≦359=P-1の場合のことである。
【０１６６】
従って、パリティ書込順番でいえば(n0-k0)×i+j , (n0-k0)×i+j+1 , ・・・番目の順番でパリティ部に書き込まれる各受信値を、図２３の受信値メモリ３５１上のword方向アドレスk0+j , k0+j+1 , ・・・番目、bit方向番号i , i, ・・・番目の位置に書き込んでいくこと、即ちパリティ部に対応する受信値をword方向に順次書き込んでいくことで、パリティ並び替え処理が実行されたことになる。
【０１６７】
例えば、図２４の下側の図において、カッコ無しの数値で指定された書き込み順の様に、パリティ書込順番でいえば0 , 1, ・・・ , n0-k0-1, ・・・番目に受信部３０２に受信された各受信値は、受信値メモリ３５１上のword方向アドレスk0+0 , k0+0+1 , ・・・ , n0-1 , ・・・番目、bit方向番号0 , 0, ・・・番目の各位置に順次書き込まれていく。その結果、パリティ書込順番でいえば(n0-k0)×i+j , (n0-k0)×i+j+1 , ・・・番目の順番でパリティ部に書き込まれる各受信値は、P×j+i , P×(j+1)+i, ・・・番に配置されたこととなり、たしかにパリティ並び替え処理が実行されたことになる。
【０１６８】
以上説明した手法を適用することで、8PSK変調方式において、より一般的に任意の符号化率rが与えられた場合であっても、ビットデインターリーブ処理とパリティ並び替え処理との同時実行が可能になる。
【０１６９】
このようにして、ビットデインターリーブ処理とパリティ並び替え処理との同時実行を実現するように受信値を書き込む際のアドレスを指定することで、ビットデインターリーバを用いずにそれと全く等価な処理が実現できたことになり、回路規模および消費電力の削減がほぼトレードオフなく得られるという効果を奏することが可能になる。
【０１７０】
例えば、上述した実施形態についていえば、ビットデインターリーブ処理とパリティ並び替え処理とは、受信部３０２の同一の受信値メモリ（上述した例では図２１の受信値メモリ３３１や図２３の受信値メモリ３５１）上で同時に実行されているため、従来手法においてビットデインターリーブ処理の実行に必須だったビットデインターリーバを削減でき、即ち、そのビットデインターリーバ上の２個のRAM（例えば図６のビットデインターリーバ２０３の図１０等の記憶装置２２１，２２２）を削減できる、という効果を奏することが可能になる。
【０１７１】
なお、説明は省略するが、本発明が適用される上述した手法は、他の変調方式や符号化率が変わっても全く同様に適用することができる。即ち、本発明は他のおよび異なる実施形態を取ることができ、そのいくつかの詳細は全て本発明の精神および範囲を逸脱することなくさまざまな明白な点で修正できる。従って図面および発明の詳細な説明は本質的に例証とみなされるべきであり、限定的とみなされてはならない。
【０１７２】
ところで、上述した一覧表示処理も含む一連の処理は、ハードウエアにより実行させることもできるし、ソフトウエアにより実行させることもできる。
【０１７３】
上述した一連の処理をソフトウエアにより実行させる場合、本発明が適用される復号装置は、例えば、図２５に示されるコンピュータで構成することもできる。
【０１７４】
図２５において、CPU（Central Processing Unit）５０１は、ROM（Read Only Memory）５０２に記録されているプログラム、または記憶部５０８からRAM（Random Access Memory）５０３にロードされたプログラムに従って各種の処理を実行する。RAM５０３にはまた、CPU５０１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０１７５】
CPU５０１、ROM５０２、およびRAM５０３は、バス５０４を介して相互に接続されている。このバス５０４にはまた、入出力インターフェース５０５も接続されている。
【０１７６】
入出力インターフェース５０５には、キーボード、マウスなどよりなる入力部５０６、ディスプレイなどよりなる出力部５０７、ハードディスクなどより構成される記憶部５０８、および、モデム、ターミナルアダプタなどより構成される通信部５０９が接続されている。通信部５０９は、インターネットを含むネットワークを介して他の装置（図示せず）との間で行う通信を制御する。
【０１７７】
入出力インターフェース５０５にはまた、必要に応じてドライブ５１０が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどよりなるリムーバブルメディア５１１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部５０８にインストールされる。
【０１７８】
一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、専用のハードウエアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、ネットワークや記録媒体からインストールされる。
【０１７９】
このようなプログラムを含む記録媒体は、図２５に示されるように、装置本体とは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク（フロッピディスクを含む）、光ディスク（CD-ROM(Compact Disk-Read Only Memory),DVD(Digital Versatile Disk)を含む）、光磁気ディスク（ＭＤ（Mini-Disk）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア（パッケージメディア）５１１により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに提供される、プログラムが記録されているROM５０２や、記憶部５０８に含まれるハードディスクなどで構成される。
【０１８０】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、その順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１８１】
また、本明細書において、システムとは、複数の装置や処理部により構成される装置全体を表すものである。
【図面の簡単な説明】
【０１８２】
【図１】DVB-S.2規格に基づいた送信信号の送信器の機能的構成例を示す機能ブロックである。
【図２】LDPC符号語の構成例を示す図である。
【図３】8PSK変調信号に対するビットインターリーブの方式を説明する図である。
【図４】16APSK変調信号に対するビットインターリーブの方式を説明する図である。
【図５】32APSK変調信号に対するビットインターリーブの方式を説明する図である。
【図６】DVB-S.2規格に基づいた送信信号の受信器のうちの、従来のLDPC復号装置の機能的構成の概略例を示す図である。
【図７】8PSK変調信号に対するビットデインターリーブの方式を説明する図である。
【図８】16APSK変調信号に対するビットデインターリーブの方式を説明する図である。
【図９】32APSK変調信号に対するビットデインターリーブの方式を説明する図である。
【図１０】従来のビットデインターリーブの実装例を示す図である。
【図１１】従来のビットデインターリーブの実装例を示す図である。
【図１２】LDPC符号の parity check matrixの例を示す図である。
【図１３】LDPC符号の parity check matrixの例を示す図である。
【図１４】行列置換前後のparity部の例を示す図である。
【図１５】行列置換前のparity部の例を示す図である。
【図１６】行置換後／列置換前のparity部の例を示す図である。
【図１７】行列置換後のparity部の例を示す図である。
【図１８】符号長108, 符号化率r=2/3のLDPC符号語の各要素データへの番号付けの例を示す図である。
【図１９】パリティ並び替え処理を説明する図である。
【図２０】本発明が適用される復号装置としての、ビットデインターリーブ内蔵LDPC復号器装置の機能的構成の概要例を示す機能ブロック図である。
【図２１】図２０のビットデインターリーブ内蔵LDPC復号器装置の受信部の受信値メモリの構成例と、受信値に対して施すビットデインターリーブ処理を説明する具体例を示す図である。
【図２２】受信値に対してビットデインターリーブ処理とパリティ並び替え処理とを同時に施すための受信値書き込み手法を説明する図である。
【図２３】受信値に対してビットデインターリーブ処理とパリティ並び替え処理とを同時に施すための受信値書き込み手法を説明する図である。
【図２４】受信値に対してビットデインターリーブ処理とパリティ並び替え処理とを同時に施すための受信値書き込み手法を説明する図である。
【図２５】本発明が適用される復号装置の他の実施形態としての、コンピュータの構成例を示すブロック図である。
【符号の説明】
【０１８３】
２５１  デマッピング部，  ２５２  ビットデインターリーバ内蔵LDPC復号器，  ２５３  LDPC復号器，  ３０１  ビットデマッパ，  ３０２  受信部，  ３０３  LDPC復号計算部，３０４  復号結果メモリ，  ３３１，３５１  受信値メモリ，  ５０１  CPU，  ５０２  ROM，  ５０３  RAM，  ５０８  記憶部，  ５１０  リムーバブルメディア
【図１】
2008278189.tif 000003
【図２】
2008278189.tif 000004
【図３】
2008278189.tif 000005
【図４】
2008278189.tif 000006
【図５】
2008278189.tif 000007
【図６】
2008278189.tif 000008
【図７】
2008278189.tif 000009
【図８】
2008278189.tif 000010
【図９】
2008278189.tif 000011
【図１０】
2008278189.tif 000012
【図１１】
2008278189.tif 000013
【図１２】
2008278189.tif 000014
【図１３】
2008278189.tif 000015
【図１４】
2008278189.tif 000016
【図１５】
2008278189.tif 000017
【図１６】
2008278189.tif 000018
【図１７】
2008278189.tif 000019
【図１８】
2008278189.tif 000020
【図１９】
2008278189.tif 000021
【図２０】
2008278189.tif 000022
【図２１】
2008278189.tif 000023
【図２２】
2008278189.tif 000024
【図２３】
2008278189.tif 000025
【図２４】
2008278189.tif 000026
【図２５】
2008278189.tif 000027