(57)【要約】  衛星受信器は、フロントエンド、復調器及びＬＤＰＣ復号器を備えている。フロントエンドは、ＤＶＢ−Ｓ２  ＬＤＰＣ符号化信号を受信し、ダウンコンバート信号を復調器に供給する。復調器は、ダウンコンバート信号を復調し、復調信号をＬＤＰＣ復号器に供給する。ＬＤＰＣ復号器は、部分的に並列なアーキテクチャを有しており、ビット・ノード・メッセージをＮ／３６０個の群に分割し、検査ノード・メッセージをｑ個の群に分割する。ここで、ｑ＝Ｍ／３６０である。各群は、３６０個のビット・ノード・プロセッサ又は３６０個の検査ノード・プロセッサそれぞれによって処理される。例証的には、ＬＤＰＣ復号器は、ビット・ノード群に関連したメッセージが連続してアドレス指定されるように分割されたメモリを有している。あるいは、ＬＤＰＣ復号器は、検査ノード群に関連したメッセージが連続してアドレス指定されるように分割されたメモリを有している。
2008515342.tif 000002
【特許請求の範囲】
【請求項１】
受信器において用いる方法であって、
低密度パリティ検査（ＬＤＰＣ）符号化データを受信する工程と、
検査ノード・メッセージ及びビット・ノード・メッセージを用いて前記受信ＬＤＰＣ符号化データを処理して復号化データを供給する工程とを備えており、
前記処理する工程は、前記ビット・ノード・メッセージをＹ個の群に分割し、前記検査ノード・メッセージをｑ個の群に分割し、ｑは、前記受信ＬＤＰＣ符号化データに関連した符号化率の関数として変動する方法。
【請求項２】
請求項１記載の方法であって、前記受信ＬＤＰＣ符号化データが、受信ディジタル・ビデオ放送システム−２信号から導き出される方法。
【請求項３】
請求項１記載の方法であって、前記受信ＬＤＰＣ符号化データは（Ｎ，Ｋ）ＬＤＰＣ符号を表し、Ｍ＝Ｎ−Ｋであり、ｑ＝Ｙ（Ｎ−Ｋ）／Ｎである方法。
【請求項４】
請求項３記載の方法であって、Ｙ＝Ｎ／３６０である方法。
【請求項５】
請求項１記載の方法であって、前記受信ＬＤＰＣ符号化データは、サイズＭ×Ｎのパリティ行列を有する（Ｎ，Ｋ）ＬＤＰＣ符号を表し、前記処理する工程は、
各検査ノード・メッセージ群をＪ個のプロセッサによって処理する工程と、
各ビット・ノード・メッセージ群をＪ個のプロセッサによって処理する工程とを含み、
Ｊは、数が整数の正方形部分行列が前記パリティ行列内に収まるような正方形部分行列のサイズを表す方法。
【請求項６】
請求項５記載の方法であって、前記検査ノード・メッセージを処理する工程は、
各検査ノード・メッセージ群を巡回的にシフトさせる工程と、
巡回的にシフトさせた検査ノード・メッセージ群それぞれをＪ個のプロセッサによって処理して新たなメッセージ群を供給する工程と、
新たなメッセージ群それぞれを巡回的にシフトさせてビット・ノード・メッセージ群を構成する工程とを含む方法。
【請求項７】
請求項５記載の方法であって、前記ビット・ノード・メッセージを処理する工程は、
各ビット・ノード・メッセージ群を巡回的にシフトさせる工程と、
巡回的にシフトさせたビット・ノード・メッセージ群それぞれをＪ個のプロセッサによって処理して新たなメッセージ群を供給する工程と、
新たなメッセージ群それぞれを巡回的にシフトさせて検査ノード・メッセージ群を構成する工程とを含む方法。
【請求項８】
請求項１記載の方法であって、前記受信ＬＤＰＣ符号化データは、サイズＭ×Ｎのパリティ行列を有する（Ｎ，Ｋ）ＬＤＰＣ符号を表し、前記処理する工程は、
各検査ノード・メッセージ群をＪ個のプロセッサによって処理する工程と、
各ビット・ノード・メッセージ群をＪ個のプロセッサによって処理する工程とを備えており、
Ｊ＝Ｎ／Ｙである方法。
【請求項９】
請求項８記載の方法であって、前記検査ノード・メッセージを処理する工程は、
各検査ノード・メッセージ群を巡回的にシフトさせる工程と、
巡回的にシフトさせた検査ノード・メッセージ群それぞれをＪ個のプロセッサによって処理して新たなメッセージ群を供給する工程と、
新たなメッセージ群それぞれを巡回的にシフトさせてビット・ノード・メッセージ群を構成する工程とを含む方法。
【請求項１０】
請求項８記載の方法であって、前記ビット・ノード・メッセージを処理する工程は、
各ビット・ノード・メッセージ群を巡回的にシフトさせる工程と、
巡回的にシフトさせたビット・ノード・メッセージ群それぞれをＪ個のプロセッサによって処理して新たなメッセージ群を供給する工程と、
新たなメッセージ群それぞれを巡回的にシフトさせて検査ノード・メッセージ群を構成する工程とを含む方法。
【請求項１１】
受信器において用いる装置であって、
低密度パリティ検査（ＬＤＰＣ）符号化データを供給する復調器と、
前記ＬＤＰＣ符号化データを復号化して復号化データを供給するＬＤＰＣ復号器とを備えており、  
前記ＬＤＰＣ復号器は、ビット・ノード・メッセージをＹ個の群に分割し、検査ノード・メッセージをｑ個の群に分割することによって前記ＬＤＰＣ符号化データを処理し、ｑは、前記ＬＤＰＣ符号化データに関連した符号化率の関数として変動する装置。
【請求項１２】
請求項１１記載の装置であって、前記ＬＤＰＣ符号化データが、受信ディジタル・ビデオ放送システム−２信号から導き出される装置。
【請求項１３】
請求項１１記載の装置であって、前記ＬＤＰＣ符号化データは（Ｎ，Ｋ）ＬＤＰＣ符号を表し、Ｍ＝Ｎ−Ｋであり、ｑ＝Ｙ（Ｎ−Ｋ）／Ｎである装置。
【請求項１４】
請求項１３記載の装置であって、Ｙ＝Ｎ／３６０である装置。
【請求項１５】
請求項１１記載の装置であって、前記ＬＤＰＣ符号化データは、サイズＭ×Ｎのパリティ行列を有する（Ｎ，Ｋ）ＬＤＰＣ符号を表し、前記ＬＤＰＣ符号器は、
各ビット・ノード・メッセージ群を処理するＪ個のプロセッサと、
各検査ノード・メッセージ群を処理するＪ個のプロセッサとを含み、
Ｊは、数が整数の正方形部分行列が前記パリティ行列内に収まるような正方形部分行列のサイズを表す装置。
【請求項１６】
請求項１１記載の装置であって、前記ＬＤＰＣ符号化データは、サイズＭ×Ｎのパリティ行列を有する（Ｎ，Ｋ）ＬＤＰＣ符号を表し、前記ＬＤＰＣ符号器は、
各ビット・ノード・メッセージ群を処理するＪ個のプロセッサと、
各検査ノード・メッセージ群を処理するＪ個のプロセッサとを備えており、
Ｊ＝Ｎ／Ｙである装置。
【請求項１７】
請求項１１記載の装置であって、前記ＬＤＰＣ復号器は、
前記検査ノード・メッセージ及び前記ビット・ノード・メッセージを記憶するメモリと、
前記検査ノード・メッセージをシフトさせる巡回シフタと、
前記巡回的にシフトさせた検査ノード・メッセージを処理して新たなメッセージを供給するビット・ノード・プロセッサ群と、
前記新たなメッセージをシフトさせて新たなビット・ノード・メッセージを構成する巡回シフタと、
前記ビット・ノード・メッセージを処理して、前記メモリに記憶するために新たな検査ノード・メッセージを供給する検査ノード・プロセッサ群とを備えており、
新たなビット・ノード・メッセージが連続して記憶されるように前記メモリが構成される装置。  
【請求項１８】
請求項１１記載の装置であって、前記ＬＤＰＣ復号器は、
前記検査ノード・メッセージ及び前記ビット・ノード・メッセージを記憶するメモリと、
前記検査ノード・メッセージを処理して、前記メモリ内に記憶するために新たなビット・ノード・メッセージを供給するビット・ノード・プロセッサ群と、
前記ビット・ノード・メッセージをシフトさせる巡回シフタと、
前記巡回的にシフトさせたビット・ノード・メッセージを処理して新たなメッセージを供給する検査ノード・プロセッサ群と、
前記新たなメッセージをシフトさせて新たな検査ノード・メッセージを構成する巡回シフタとを備えており、
新たな検査ノード・メッセージが連続して記憶されるように前記メモリが構成される装置。
【請求項１９】
請求項１１記載の装置であって、前記ＬＤＰＣ復号器は、ビット・ノード・メッセージ群が連続して記憶されるように編成されたメモリを備える装置。
【請求項２０】
請求項１１記載の装置であって、前記ＬＤＰＣ復号器は、検査ノード・メッセージ群が連続して記憶されるように編成されたメモリを備える装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に通信システムに関し、特に低密度パリティ検査（ＬＤＰＣ）符号化データを処理する受信器に関する。
【背景技術】
【０００２】
近年、ＬＤＰＣ符号は、ほぼシャノン限界の誤り訂正ケーパビリティを有しているため、人気が高まっている。例えば、第２世代のディジタル・ビデオ放送標準（ＤＶＢ−Ｓ２）によって、第１世代のＤＶＢ標準において用いられた畳み込み符号を置き換える主要な誤り訂正符号としてＬＤＰＣ符号が採用されている（例えば、Ｅｕｒｏｐｅａｎ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｔａｎｄａｒｄｓ  Ｉｎｓｔｉｔｕｔｅ  （ＥＴＳＩ）  Ｄｒａｆｔ  ＥＮ  ３０２３０７，  ｖ．１．１．１，  Ｊｕｎｅ  ２００４を参照されたい）。
【０００３】
一般に、（Ｎ，Ｋ）ＬＤＰＣ符号はパリティ検査符号である。ここで、Ｋは符号化する対象のビットの数、Ｎは結果として符号化されたブロックのサイズ（長さ）、（Ｎ−Ｋ）は、符号によって付加される付加誤り訂正ビットである。（Ｎ，Ｋ）ＬＤＰＣ符号は、行列式ＨｘＴ＝０Ｔの解の組（ｘ）として行列形式で表すことが可能である。ＨｘＴ＝０Ｔこの式は、「パリティ検査式」としても表される。ここで、上付き文字Ｔは、関連した行列の転置を表し、Ｈは、サイズＭ×Ｎの「パリティ検査行列」として表され、Ｎは前述の通り、結果として生じる符号化ブロックのサイズに対応しており、Ｍ＝Ｎ−Ｋである。「低密度」という修飾語は、パリティ検査行列内の非ゼロ要素の割合が小さいことを表し、特に、符号ブロック長Ｎにおいて線形である（対照的に、「ランダムな」線形ブロック符号は、１の期待数がＮ２のオーダで増えるものである）。
【０００４】
当該技術分野において知られているように、ＬＤＰＣ符号を２部グラフによって表すことも可能である。２部グラフは、ＬＤＰＣ復号化処理を理解するうえで有用である。サイズＭ×Ｎを有するパリティ検査行列Ｈの意味合いにおいて、対応する２部グラフは、パリティ検査行列のＮ個の列に対応するＮ個のビット・ノード（可変ノードまたはメッセージ・ノードとも呼ばれる）を含み、パリティ検査行列のＭ個の行に対応するＭ個の検査ノードも含む。各検査ノードは、１つ又は複数のビット・ノードに接続する。特に、辺（又は分岐）は、Ｈｍ，ｎ＝１である場合にのみ、検査ノードｍを可変ノードｎに接続する。ここで、０≦ｎ＜Ｎであり、０≦ｍ＜Ｍである。２部グラフの場合、「ビット・ノードの次数」という句（又はビット・ノード次数という語）は、ビット・ノードが接続される検査ノードの数を表す。同様に、「検査ノードの次数」という句（又は検査ノード次数という語）は、検査ノードが接続されるビット・ノードの数を表す。検査ノード次数及びビット・ノード次数が更に、パリティ検査行列Ｈのそれぞれの行及び列における「１」の数に対応することも分かる。手短に図１に移れば、例証的なパリティ検査行列５及び対応する２部グラフ６を示す。ここで、Ｎ＝７であり、Ｍ＝３である。例証的には、ビット・ノードｘ７のビット・ノード次数は１であり、検査ノードｃ３の検査ノード次数は４である。
【０００５】
前述の通り、２部グラフは、ＬＤＰＣ復号化処理を理解するうえで有用である。この意味合いで、ＬＤＰＣ復号器では、検査ノードが検査ノード・プロセッサと関連付けられ、ビット・ノードがビット・ノード・プロセッサと関連付けられる。残念ながら、ＬＤＰＣ復号器の復号化アルゴリズムは概念的に単純であるが、大容量の符号ブロック又はほぼランダムなパリティ検査行列のＬＤＰＣ復号器のアーキテクチャは、実現上の重大な問題をもたらす。ＬＤＰＣ復号器を実現する既知のアーキテクチャは３つ存在している。第１のものは、完全に並列のアーキテクチャである。このアーキテクチャでは、検査ノード、ビット・ノード及びそれらの接続がハードウェアにマッピングされる。このアーキテクチャによって、非常に高速の復号器がもたらされる。しかし、このアーキテクチャは、ブロック長が長いＬＤＰＣ符号の復号化には実用的でない。ハードウェアの複雑度が高いからである。第２のものは直列アーキテクチャである。このアーキテクチャでは、１つの検査ノード処理装置（ＣＰＵ）及び１つのビット・ノード処理装置（ＢＰＵ）のみを多数回実現し、再使用して復号化処理全てを達成する。残念ながら、処理は全て、直列に行われるので、直列アーキテクチャによって、速度が非常に低い復号器がもたらされる。最後に、第３のものは、部分的に並列のアーキテクチャである。これは、第１のアーキテクチャと第２のアーキテクチャとの間の中間である。ここでは、複数のビット・ノード処理装置（ＢＰＵ）及び複数の検査ノード処理装置（ＣＰＵ）を実現し、再使用して、事実上、所望のＬＤＰＣ復号器のハードウェア複雑度と復号化レーテンシとを天秤に掛ける。残念ながら、部分的に並列のＬＤＰＣ復号器を効率的に実現するための一貫した設計手法は存在しない。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ＬＤＰＣパリティ検査行列の特定の特性を活用することによってＬＤＰＣ復号器の複雑度を削減し、よって、部分的に並列のアーキテクチャを有するより効率的なＬＤＰＣ復号器を設計することが可能であることが明らかになった。
【課題を解決するための手段】
【０００７】
したがって、かつ、本発明の原理によれば、受信器が、ＬＰＤＳ復号化方法を行う。この方法は、ＬＤＰＣ符号化データを受信する工程と、受信ＬＤＰＣ符号化データを処理して復号化データを供給する工程とを備えており、処理する工程は、ビット・ノード・メッセージをＹ個の群に分割し、検査ノード・メッセージをｑ個の群に分割し、ｑは符号化率の関数として変動する。
【０００８】
本発明の実施例では、衛星受信器は、フロントエンドと、復調器と、ＬＤＰＣ復号器とを備える。フロントエンドは、ＤＶＢ−Ｓ２  ＬＤＰＣ符号化信号を受信し、ダウンコンバート信号を復調器に供給する。復調器は、ダウンコンバート信号を復調し、復調信号をＬＤＰＣ復号器に供給する。ＬＤＰＣ復号器は、部分的に並列のアーキテクチャを有しており、ビット・ノード・メッセージをＮ／３６０個の群に分割し、検査ノード・メッセージをｑ個の群に分割する。ここで、ｑ＝Ｍ／３６０である。各群は、３６０個のビット・ノード・プロセッサ又は３６０個の検査ノード・プロセッサそれぞれによって処理される。例証的には、ＬＤＰＣ復号器は、ビット・ノード群に関連したメッセージが連続してアドレス指定されるように分割されたメモリを有している。
【０００９】
本発明の実施例では、衛星受信器は、フロントエンドと、復調器と、ＬＤＰＣ復号器とを備える。フロントエンドは、ＤＶＢ−Ｓ２  ＬＤＰＣ符号化信号を受信し、ダウンコンバート信号を復調器に供給する。復調器は、ダウンコンバート信号を復調し、復調信号をＬＤＰＣ復号器に供給する。ＬＤＰＣ復号器は、部分的に並列のアーキテクチャを有しており、ビット・ノード・メッセージをＮ／３６０個の群に分割し、検査ノード・メッセージをｑ個の群に分割する。ここで、ｑ＝Ｍ／３６０である。各群は、３６０個のビット・ノード・プロセッサ又は３６０個の検査ノード・プロセッサそれぞれによって処理される。例証的には、ＬＤＰＣ復号器は、検査ノード群に関連したメッセージが連続してアドレス指定されるように分割されたメモリを有している。
【発明を実施するための最良の形態】
【００１０】
本発明の概念以外には、添付図面に示す構成要素は周知であり、詳細に説明しない。例えば、本発明の概念以外には、衛星トランスポンダ、ダウンリンク信号、シンボル・コンステレーション、キャリア再生、補間、位相ロック・ループ（ＰＬＬ）、無線周波数（ＲＦ）のフロントエンド部又は受信器部（低雑音ブロック・ダウンコンバータなど）、伝送ビット・ストリームを生成するためのフォーマッティング手法及び符号化手法（動画像専門家グループ（ＭＰＥＧ）−２システム標準（ＩＳＯ／ＩＥＣ１３８１８−１）、ＬＤＰＣ符号化等など）、復号化手法（対数尤度比、ソフト入力ソフト出力（ＳＩＳＯ）復号器、ビタビ復号器が、周知であり、本明細書及び特許請求の範囲では説明しない。更に、本発明の概念は、そういうものとして本明細書では説明しない通常のプログラミング手法を用いて実施することができる。更に、衛星ベースのシステム（例えば、ＤＢＶ−Ｓ２）及び前述のＥＴＳＩ，  Ｄｒａｆｔ  ＥＮ  ３０２３０７，  ｖ．１．１．１，  Ｊｕｎｅ  ２００４に精通していることを前提としており、本明細書では詳細に説明しない。最後に、添付図面上の同じ符号は同様な構成要素を表す。
【実施例】
【００１１】
本発明の概念の説明を続ける前に、ＬＤＰＣ復号器の従来技術の復号化アルゴリズムを手短に検討する。ＬＤＰＣ復号器の復号化アルゴリズムは場合によっては、当該技術分野において知られているように、メッセージ・パッシング・アルゴリズム又は確率伝搬アルゴリズムと呼ばれる。メッセージ・パッシング・アルゴリズム自体は、どちらかと言えば単純であるように思われる。具体的には、検査ノードの組（Ｍｎ＝｛ｍ：Ｈｍ．ｎ＝１｝）及びビット・ノードの組（Ｎｍ＝｛ｎ：Ｈｍ．ｎ＝１｝）を定義する。
【００１２】
【数１】
2008515342.tif 000003
を、ｌ回目の実行中の検査ノードｍからビット・ノードｎへのメッセージとし、
【数２】
2008515342.tif 000004
を、ｌ回目の実行中のビット・ノードｎから検査ノードｍへのメッセージとし、
【数３】
2008515342.tif 000005
が、ｌ回目の実行後のｎ番目のビットの事後確率対数尤度比（ＬＬＲ）の推定を表すものとする。ＬＤＰＣ符号ブロックのチャネル・データがベクトルｒとして表される場合、メッセージ・パッシング・アルゴリズムは以下の通りである。初期化時には、
【数４】
2008515342.tif 000006
（１）が計算される。全てのｎ∈｛０，．．．，Ｎ−１｝及びｍ∈Ｍｎについて、
【数５】
2008515342.tif 000007
とする。（２）
初期化後、すなわち、ｌ＝１，２，．．，ｌｍａｘの実行について、以下の計算を検査ノード更新毎及びビット・ノード更新毎に行う。検査ノード更新毎に、
ｍ∈｛０，１，…，Ｍ−１｝及びｎ∈Ｎｍについて、
【数６】
2008515342.tif 000008
（３）を計算する。ここで、
【数７】
2008515342.tif 000009
である。
【００１３】
更に、ビット・ノード更新毎に、
ｎ∈｛０，１，…，Ｎ−１｝及びｍ∈Ｍｎについて、
【数８】
2008515342.tif 000010
を計算する。
【００１４】
復号化アルゴリズムの硬判定基準及び終了基準は以下の通りである。
【００１５】
【数９】
2008515342.tif 000011
である場合、ｂｎ＝０であり、さもなければｂｎ＝１  （５）である。
【００１６】
ここで、パリティ検査行列Ｈによって定義されるパリティ検査式全てをビット系列ｂ０，ｂ１，…，ｂＮ−１が満たす場合、検査が行われる。肯定の場合、実行は終了する。さもなければ、ｌ←（ｌ＋１）とし、最大回数の実行に達するまで実行を続ける。
【００１７】
前述の通り、メッセージ・パッシング・アルゴリズム自体は、どちらかと言えば単純である。しかし、ＬＤＰＣ復号器の実際の実現形態は、ハードウェアの制約、ＬＤＰＣ符号の長さ、及びビット・ノードと検査ノードとの間のほぼランダムな接続が理由で、常に単純である訳でない。このことは、本発明の概念を例証するのに用いるＤＶＢ−Ｓ２衛星システムに用いるＬＤＰＣ符号によって特に示される。しかし、本発明の概念は、そのように限定されず、衛星システムの一部か否かにかかわらず、何れのタイプのＬＤＰＣ復号器にも適用可能である。
【００１８】
ＤＶＢ−Ｓ２においては、可能な変調手法は４つ（すなわち、ＱＰＳＫ（直交位相シフト・キーイング）、８‐ＰＳＫ、１６‐ＡＰＳＫ（振幅位相シフト・キーイング）及び３２‐ＡＰＳＫ）、存在する。変調前に、データは、直列連接符号手法を用いて符号化される。ＬＤＰＣ符号は内符号であり、ＢＣＨ（ボーズ・チャウドリー・オッケンヘェム）符号は外符号である。ＱＰＳＫ変調を除き、ＬＤＰＣ符号語ビットは更に、変調前にインタリーブされる。符号化処理に関し、ＢＣＨ符号は、強度が非常に低い符号である。これは、１０−７のパケット誤り率を達成するために、ＬＤＰＣ復号化処理後の残差を補正するのに用いられる。ＬＤＰＣ符号化に関し、２つのタイプのＬＤＰＣ符号が存在している。第１のタイプは、本明細書では、６４８００ビットの符号ブロック長を有する「通常ＬＤＰＣ符号」として表す。第２のタイプは、１６２００ビットの符号ブロック長を有する短ＬＤＰＣ符号である。２つのタイプの符号は同様な構造を有しているので、通常のＬＤＰＣ符号を本明細書において説明する。単に便宜上、かつ、別途明記しない限り、「ＬＤＰＣ符号」という語への後の言及は、通常ＬＤＰＣ符号を表す。しかし、特許請求の範囲記載の「ＬＤＰＣ符号」の語の使用は、そのように限定されるものでない。
【００１９】
ＤＶＢ−Ｓ２システム（例えば、前述のＥＴＳＩ，  Ｄｒａｆｔ  ＥＮ  ３０２３０７，  ｖ．１．１．１，  Ｊｕｎｅ  ２００４）の場合、図２のテーブル１に示すように、いくつかの別々の利用可能ＬＤＰＣ符号化率が存在している。「率」とラベリングした、テーブルの第１列は、前述の別々のＬＤＰＣ符号化率を列挙している。次の列「Ｋ」は、その特定のＬＤＰＣ符号化率でＬＤＰＣ符号化ブロックにおいて符号化されたデータの量を列挙している。ＤＶＢ−Ｓ２システムの意味合いでは、このデータは、前述のＢＣＨ符号化データを含む。例えば、１／４符号化率の場合、非符号化データ・ブロックは、１６００８ビットのサイズを有している（テーブル１に示していない）。この非符号化データ・ブロックは次いで、１６２００ビット（ＬＤＰＣ１／４符号化率の場合の、テーブル１におけるＫの当該値）のＢＣＨ符号化ブロックにＢＣＨ符号化される。このＢＣＨ符号化ブロックは次いで、特定の符号化率でＬＤＰＣ符号化される。この例では、ＬＤＰＣ符号化率が１／４であるので、結果として生じるＬＤＰＣ符号化ブロックのサイズは６８，４００ビットである（テーブル１に示していない）。対応する受信器は、受信ＤＶＢ−Ｓ２信号形式の所定の部分に含まれたデータから符号化率を判定する。
【００２０】
テーブル１から分かり得るように、１／４から９／１０に及ぶ１１個の考えられる符号化率が存在している。しかし、別々の率を有する符号は、ＤＶＢ−Ｓ２において規定されるような別々のパリティ検査行列を有する。そういうものとして、高い率の符号語は、低い率の符号語の破壊によって得ることが可能であるものでない。したがって、大きな符号ブロック長及び複数の符号化率によって、ＬＤＰＣ復号器のハードウェア実現形態が非常に複雑になる。
【００２１】
前述の通り、ＬＤＰＣ復号器実現形態には主要なアーキテクチャが３つ存在する。ＤＶＢ−Ｓ２の意味合いでは、ＬＤＰＣ符号ブロック長は６４，８００ビットであり、これはどちらかと言えば大容量である。更に、ＤＶＢ−Ｓ２復号器は、低レーテンシを必要とする。よって、完全に並列のアーキテクチャ又は完全に直列のアーキテクチャは復号器実現形態にふさわしくなく、部分的に並列のアーキテクチャを設計する必要がある。しかし、部分的に並列のＬＤＰＣ復号器を効率的に実現するための一貫した設計手法は存在しない。
【００２２】
この問題を解決するために、かつ、本発明の原理によれば、ＤＶＢ−Ｓ２パリティ検査行列の特定の特性を活用することによってＬＤＰＣ復号器の複雑度を削減することが可能である。非正則ＬＤＰＣ符号の場合、望ましい規則の１つに、検査ノード次数（Ｄｃ）の分布ができる限り一様であるという点がある。ＤＶＢ−Ｓ２  ＬＤＰＣ符号に関し、関連したパリティ検査行列毎に、各検査ノードは、（Ｄｃ−１）の次数を有する、パリティ検査行列の第１の検査ノード以外は、同じ検査ノード次数（Ｄｃ）を有する。よって、ＤＶＢ−Ｓ２内のＬＤＰＣ符号は、前述の規則に従う。
【００２３】
更に、ＤＶＢ−Ｓ２パリティ検査行列が、図３に示すように［Ａ｜Ｔ］の形式のものであることが知られている。行列Ａは、サイズＭ×Ｋの矩形行列である。ここで、Ｍ＝Ｎ−Ｋである。行列Ａは、図４に更に示す。行列Ａ自体は、２つの部分行列（Ａ１及びＡ２）から成るパリティ検査行列として扱うことが可能である。ここで、Ａ１はサイズＭ×Ｌの行列であり、Ａ２はサイズＭ×（Ｋ−Ｌ）の行列である。行列Ａ１内のビット・ノードは同じ次数（ＤＶ１として表す）を有しており、同様に、行列Ａ２内のビット・ノードの次数は同じであり、ＤＶ２＝３で固定される。次に行列Ｔに移れば、この行列は、図５に示すように特殊なＭ×Ｍの下三角行列である。このタイプの構造は場合によっては、階段構造と呼ばれる。これは、特定の次数分布の場合、次数２（すなわち、ＤＶ３＝２）のビット・ノードを実現する。更に、この下三角構造は、高速ＬＤＰＣ符号化を可能にする（例えば、ＥＴＳＩ，  Ｄｒａｆｔ  ＥＮ  ３０２３０７，  ｖ．１．１．１，  Ｊｕｎｅ  ２００４を参照されたい）。
【００２４】
次に図６に移れば、テーブル２は、種々のＤＶＢ−Ｓ２に対して前述のＬ、ＤＶ１、ｑ及びＤｃの値を示す。「率」及び「Ｋ」とラベリングされた、テーブル２の最初の２列は、図１のテーブル１に示す列と同一である。
【００２５】
本発明の原理によれば、行列Ａの構造の更なる解析によって、ＬＤＰＣ復号器の実現に更に解決の光があてられる。特に、３６０個のビット・ノード｛３６０×ｋ，…，３６０×ｋ＋３５９｝の群毎に、関係する検査ノードを、インデクス（３６０×ｋ）を備える第１のビット・ノードの検査ノードによって規定することが可能である。例えば、上記群内の第１のビット・ノードに検査ノード［Ｃ１，Ｃ２，  …，ＣＤＶ］の組が関係している場合（ここで、ＤＶは、ビット・ノードの次数である）、インデクス（３６０×ｋ＋ｍ）を備えるビット・ノードには、
｛ｃ｜ｃ＝（ｘ＋ｍ×ｑ）ｍｏｄＭ，ｘ∋｛Ｃ１，Ｃ２，…，ＣＤＶ｝｝  （６）
として表す、検査ノードの組が関係している。
ここで、ｑ＝Ｍ／３６０である。
【００２６】
前述の観察に鑑みて、かつ、本発明の原理によれば、ビット・ノード及び検査ノードをそれぞれ、複数の群に編成して、ビット・ノード更新動作又は検査ノード更新動作を同時に行う。この特定の例に関し、かつ、式（６）によって例証するように、３６０個のビット・ノード｛３６０×ｋ，…，３６０×ｋ＋３５９｝全てを一群として処理することが可能である。すなわち、ビット・ノードは、連続してグループ化される
（ｎ∈｛０，１，…，（Ｋ／３６０）−１｝の場合、ｎ番目のビット・ノード群は、ビット・ノード
｛３６０ｎ，  ３６０ｎ＋１，…，３６０ｎ＋３５８，３６０ｎ＋３５９｝を含むなど）。
【００２７】
前述のビット・ノードは、本明細書では、システマチック・ビット・ノードとしても表される。
【００２８】
検査ノードに関し、検査ノードは、ｑ個の群に以下のように再配置される（ここで、前述のように、ｑ＝Ｍ／３６０である、すなわち、ｑは符号化率の関数として変動する）。
【００２９】
群０：｛０，ｑ，２×ｑ，３×ｑ，・・・，３５９×ｑ｝、
群１：｛１，１＋ｑ，１＋２×ｑ，１＋３×ｑ，・・・，１＋３５９×ｑ｝、
・・・
群ｑ−２：｛ｑ−２，ｑ−２＋ｑ，・・・，ｑ−２＋３５９×ｑ｝及び
群ｑ−１：｛ｑ−１，ｑ−１＋ｑ，・・・，ｑ−１＋３５９×ｑ｝
ＬＤＰＣ符号化ブロックはＮ＝６４，８００ビットのサイズを有するので、より小さなサイズのＡ行列を以下に説明して本発明の概念を更に例証する。図７は、本発明の原理によって再編成される行列１０（形式Ａの行列）を示す。行列１０は、以下のパラメータを有するＬＤＰＣ符号に対するものである。
【００３０】
Ｎ＝１０×３６０＝３６００、
Ｍ＝５×３６０＝１８００、
ｑ＝５、
ＤＶ１＝４、及び
Ｌ＝３６０
各正方形１１は、サイズ３６０×３６０の部分行列を表す。本発明の概念以外に、図７に示す表記は、同様な符号構成に関して当該技術分野において知られている（例えば、Ｄａｖｉｄ  Ｊ．  Ｃ．  Ｍａｃｋａｙ、  Ｓｉｍｏｎ  Ｔ．  Ｗｉｌｓｏｎ及びＭａｔｔｈｅｗ  Ｃ．  Ｄａｖｅｙ、  「Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  Ｃｏｎｓｔｒｕｃｔｉｏｎｓ  ｏｆ  Ｉｒｒｅｇｕｌａｒ  Ｇａｌｌａｇｅｒ  Ｃｏｄｅｓ」，  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，  Ｖｏｌ．  ４７，  ｐｐ．  １４４９−１４５４，  Ｏｃｔ．  １９９９、並びに、Ｄ．  Ｓｒｉｄｈａｒａ、Ｔ．  Ｆｕｊａ及びＲ．Ｍ．Ｔａｎｎｅｒ、  「Ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ  ｃｈｅｃｋ  ｃｏｄｅｓ  ｆｒｏｍ  ｐｅｒｍｕｔａｔｉｏｎ  ｍａｔｒｉｃｅｓ」，  Ｃｏｎｆ．  Ｏｎ  Ｉｎｆｏ．  Ｓｃｉｅｎｃｅｓ  ａｎｄ  Ｓｙｓ．，  Ｔｈｅ  Ｊｏｈｎ  Ｈｏｐｋｉｎｓ  Ｕｎｉｖｅｒｓｉｔｙ，  Ｍａｒｃｈ  ２００１を参照されたい）。特に、空の正方形は、全て０の行列を表し、正方形内の円の中の整数は、周囲の正方形にスーパインポーズされたいくつかの巡回単位行列を表す。数字１は、特定のオフセットを有する単一の巡回単位行列を表す一方、数字２は、２つの巡回単位行列の組み合わせを表す。このことは、図８及び図９に更に示す。まず、図８に移れば、この図は、左シフトさせた巡回単位行列の意味合いにおける種々のオフセットを示す。行列２１は単位行列を示す。これは、本明細書では、シフトがない（すなわち、ゼロのオフセットを有する）巡回単位行列としても表す。図８の左から右に移れば、行列２１を一度左シフトさせ、その結果、行列２２が生じる。行列２２内の要素２４の位置を行列２１内のその先行位置と比較すれば、要素２４は同じ行に生起するが、左に一列シフトさせられている（事実上、列は、ラップしている）。そういうものとして、行列２２は、１のオフセットを有する巡回単位行列である。行列２２は再び、一回左シフトさせられ、その結果、次に行列２３が生じる。やはり、要素２４が行列２２内のその先行する位置から左に一列シフトさせられていることが図８から分かり得る。行列２３は、２つの左シフトの結果であるため、２のオフセットを有する巡回単位行列である。その他のオフセットを同様に導き出すことができる。図８に示していないが、右シフト動作を、他方の方向で同様に行うことも可能である。便宜上、左シフトさせられた巡回単位行列は本明細書では行列Ｉ（ｙ）として表す。ここで、上付き文字の値はオフセットの値を表す。
【００３１】
次に図９を参照すれば、結合巡回単位行列の概念を示す。結合巡回単位行列は、２つ以上の巡回単位行列の結合である。図９に関し、この図は、２つの巡回単位行列の結合を示す。特に、行列２６は図８の行列２１及び行列２２の結合であり、行列２７は図８の行列２２及び２３の結合であり、行列２８は図８の行列２１及び２３の結合である。その他の組み合わせは、同様に導き出すことが可能である。
【００３２】
前述に鑑みて、図１０はやはり、図７の行列１０（形式Ａの行列）を示しており、特定の左シフト巡回単位行列及び結合巡回単位行列のパターンを示している。部分行列内に線が存在している場合、このことは、線が交差する対応する部分行列要素が「１」の値を有しており、その他の部分行列要素が「０」の値を有していることを表す。中に線を有しない部分行列の場合、これは、全て０の部分行列を表す。
【００３３】
その結果、ＬＤＰＣ符号全てについて、パリティ検査行列のＡ行列が、３つのタイプの、サイズ３６０×３６０の部分集合（すなわち、
ゼロ行列、
巡回単位行列（Ｉ（ｙ）、０＜ｙ≦３５９）、及び
結合巡回単位行列（Ｉ（ｘ）＋Ｉ（ｙ）（ｘ≠ｙ及び０≦ｘ、ｙ≦３５９）
を備えることが図７及び図１０から分かり得る。
【００３４】
次に、ＬＤＰＣパリティ検査行列を表すための別のやり方が存在している。特に、Ｈ（ｍ，ｎ）は、検査ノード群ｍ及びビット・ノード群ｎに対応するパリティ検査行列のＡ行列の部分行列を表し、非ゼロ部分行列のみを示すものとする。パリティ・ビット・アキュムレータ・テーブルのアドレス内のｎ番目の行について（本発明の概念以外には、パリティ・ビット・アキュムレータのアドレスは、ＥＴＳＩ，  Ｄｒａｆｔ  ＥＮ  ３０２３０７，  ｖ．１．１．１，  Ｊｕｎｅ  ２００４に記載されている）、ｎ番目のビット・ノード群に対応する部分行列組が得られる。テーブルのｎ番目の行における特定の数ｘの場合、対応する検査ノード群はｍ＝ｘ  ｍｏｄ  ｑであり、左巡回シフト数の値は
【数１０】
2008515342.tif 000012
であり、対応する部分行列は、Ｈ（ｍ，ｎ）＝Ｉ（ｙ）である。例えば、図６から、率が１／２の符号の場合、ｑの値＝９０であり、ＥＴＳＩ，  Ｄｒａｆｔ  ＥＮ  ３０２３０７，ｖ．１．１．１，  Ｊｕｎｅ  ２００４のＡｎｎｅｘＢから、パリティ・ビット・アキュミュレータ・テーブルのアドレスのゼロ番目の行（ｎ＝０）は、
５４，９３１８，１４３９２，２７５６１，２６９０９，１０２１９，２５３４，８５９７である。
（ＥＴＳＩドラフトにおける呼び方では、率が１／２の符号のパリティ・ビット・アキュミュレータ・テーブルのゼロ番目の行は、列内に「１」が存在しているゼロ番目のビット・ノードのパリティ行列の行に対応する。）
よって、Ａ行列に対応する部分行列は、
５４：Ｈ（５４，０）＝Ｉ（０）；
９３１８：Ｈ（４８，０）＝Ｉ（１０３）；
１４３９２：Ｈ（８２，０）＝Ｉ（１５９）；
２７５６１：Ｈ（２１，０）＝Ｉ（３０６）；
２６９０９：Ｈ（８９，０）＝Ｉ（２９８）；
１０２１９：Ｈ（４９，０）＝Ｉ（１１３）；
２５３４：Ｈ（１４，０）＝Ｉ（２８）；及び
９５９７：Ｈ（４７，０）＝Ｉ（９５）
である。  同様に、同じパリティ・ビット・アキュミュレータ・テーブルからの第１の行（ｎ＝ｌ）
５５，７２６３，４６３５，２５３０，２８１３０，３０３３，２３８３０，３６５１
を考えてみる（やはり、ＥＴＳＩのＡｎｎｅｘ  Ｂ，  Ｄｒａｆｔ  ＥＮ  ３０２３０７，  ｖ．１．１．１，  Ｊｕｎｅ  ２００４から）。
【００３５】
よって、Ａ行列に対応する部分行列は、
５５：Ｈ（５５，１）＝Ｉ（０）；
３０３３，７２６３：Ｈ（６３，１）＝Ｉ（３３）＋Ｉ（８０）；
４６３５：Ｈ（４５，１）＝Ｉ（５１）；
２５３０：Ｈ（１０，１）＝Ｉ（２８）；
２８１３０：Ｈ（５０，１）＝Ｉ（３１２）；
２３８３０：Ｈ（７０，１）＝Ｉ（２６４）；及び
３６５１：Ｈ（５１，１）＝Ｉ（４０）
である。第１の行に関する３０３３及び７２６３の算出はともに、同じ部分行列Ｈ（６３，１）を、異なる巡回単位行列Ｉ（３３）及びＩ（８０）それぞれを伴ってではあるがもたらす。よって、部分行列Ｈ（６３，１）は、前述の２つの巡回単位行列の総和である。
【００３６】
前述の通り、ＤＶＢ−Ｓ２パリティ検査行列は全て、形式［Ａ｜Ｔ］のものである。本発明の原理によれば、行列Ｔでは、ビット・ノードは、行列Ａ内のビット・ノードとは異なるやり方でグループ化される。ｎ∈｛（Ｋ／３６０），…，（Ｎ／３６０）−１｝の場合、ｎ番目のビット・ノード群は、ビット・ノード
（Ｋ＋（ｎ−Ｋ／３６０）−｛０，ｑ，２×ｑ，３×ｑ，…，３５９×ｑ｝）
を含む。一ビット・ノード群におけるパリティ・ビット・ノードの不連続は、パリティ検査式の再配置による。結果として生じるＴ行列の例を図１１に示す。行列Ｔには、サイズ３６０×３６０の考えられる正方形が３つ
（ゼロ行列、
単位行列Ｉ（０）及び
サイズ３６０×３６０の特殊な部分行列を含む正方形Ｈ（０，（Ｎ／３６０）−１）（図１２に示す））
存在することが図１１から分かり得る。
【００３７】
パリティ検査行列の前述の再配置を次いで用いて、本発明の原理によるＬＤＰＣ復号器を実現する。本発明の原理による通信システムの例証的な部分を図１３に示す。図１３から分かり得るように、信号１０４が受信器１０５によって受信される。信号１０４は、制御シグナリング、コンテンツ（例えば、ビデオ）等を表す情報を伝達する。この例の意味合いで、信号１０４は、アンテナ（図示せず）による受信後のＤＶＢ−Ｓ２ダウンリンク衛星信号を表す。受信器１０５は、本発明の原理によって（以下に説明する）信号１０４を処理し、その上に表示するためにテレビジョン受像機（ＴＶ）９０によって表すマルチメディア端点に、特定のコンテンツを伝えるための信号１０６を供給する。
【００３８】
次に図１４に移れば、本発明の原理による受信器１０５の例証的な部分を示す。受信器１０５は、フロント・エンド・フィルタ１１０と、アナログ・ディジタル（Ａ／Ｄ）変換器１１５と、復調器１２０と、ＬＤＰＣ復号器１２５と、ＢＣＨ復号器１３５とを有している。フロント・エンド・フィルタ１１０は、（例えば、衛星伝送帯域から）ダウンコンバートし、受信信号１０４をフィルタリングして、ほぼベースバンドの信号をＡ／Ｄ変換器１１５に供給する。Ａ／Ｄ変換器は、ダウンコンバート信号をサンプリングしてこの信号をディジタル領域に変換し、サンプル系列である信号１１６を復調器１２０に供給する。復調器１２０は、（キャリア再生を含む）信号１１６の復調を行い、復調信号１２１をＬＤＰＣ復号器１２５に供給する。ＬＤＰＣ復号器１２５は、本発明の原理によって、復調信号点ストリーム１２１を復号化して信号１２６を供給する。信号１２６は、ＢＣＨ符号化された信号又はデータ・ストリームを表す。信号１２６は、信号１３６によって表すような送信データの再生のためにＢＣＨ復号器１３５に印加される。信号１３６からのデータの少なくとも一部が、信号１０６によってＴＶ９０に最終的に供給される（図１４に示していない）。（この点で、受信器１０５は更に、ＴＶ９０への印加の前にデータを処理し、かつ／又はデータをＴＶ９０に直接供給することができる。）
本発明の原理によれば、ＬＤＰＣ復号器１２５の例証的な実施例を図１５に示す。ＬＤＰＣ復号器１２５は、対数尤度比（ＬＬＲ）計算エレメント２０５と、ＬＬＲバッファ２１０と、マルチプレクサ（ＭＵＸ）２１５と、エッジ・メモリ２２０と、巡回シフタ２２５及び２３５と、複数の検査ノード処理装置（群ＣＰＵ処理）２３０と、複数のビット・ノード処理装置（群ＢＰＵ処理）２４０と、実行終了判定エレメント２４５と、コントローラ２９０とを備える。コントローラ２９０は、ストアードプログラム制御プロセッサ（例えば、マイクロプロセッサや、関連したメモリ）やステート・マシン等を表す。
【００３９】
ＬＬＲ計算エレメント２０５は、復調信号点ストリーム信号１２１を受信し、当該技術分野において知られているＬＬＲを計算して信号２０６を供給する。信号２０６は、受信ＬＤＰＣ符号化ブロックを表す算出ＬＬＲ値を表す。特に、ＬＬＲ計算エレメント２０５は、変調手法、及び受信信号の信号対雑音比に基づいて
【数１１】
2008515342.tif 000013
として符号語ビットのＬＬＲを計算する。単純化するように、ルックアップ・テーブル（図示せず）を用いてこの関数を実現する。これに加えて、ＬＬＲ計算エレメント２０５は更に、信号２０６を介して、ＬＬＲバッファ２１０に送出される前にＬＬＲ値をインタリーブ解除する（前述の通り、ＱＰＳＫ変調が用いられていない限り、ＬＤＰＣ符号化ビット・ストリームは、変調前にインタリーブされている）。ＬＬＲバッファ２１０は、記憶エレメントであり、例えば、受信ＬＤＰＣ符号化ブロックを表すデータを交互に記憶するための２重バッファ構造を備える。そういうものとして、一方のバッファが満たされると、他方のバッファからのデータが、先行して受信されたＬＤＰＣ符号化ブロックの復号化のために信号２１１を介して処理される。行列Ａのシステマチック・ビット・ノードのＬＬＲバッファにおいて用いる例証的なメモリ構造３１５を図１６に示す。一方、行列Ｔのビット・ノードのＬＬＲバッファにおいて用いる例証的なメモリ構造３２０を図１７に示す。図１６及び図１７から、必要なメモリ語の数は、Ｎ／３６０＝６４８００／３６０＝１８０である。ここで、一メモリ語のビット幅は、初期チャネル情報（λｎ（０））を記憶するために６ビットが必要であるものとした場合、３６０×６＝２１６０ビットである。そういうものとして、ＬＬＲバッファ２１０はＬＤＰＣ符号化ブロックを、信号２１１を介してＭＵＸ２１５に供給する。ＭＵＸ２１５は、単純にするために破線矢印によって表すＬＤＰＣ復号器１２５の種々の構成要素を制御するコントローラ２９０によって表すプロセッサによって制御される。ＭＵＸ２１５は、信号２１６によって、３つのタイプのデータ（復号化するための受信ＬＤＰＣ符号化ブロック（信号２１１による）、ビット・ノード処理データ（信号２４１による）、又は検査ノード処理データ（信号２３６による））をエッジ・メモリ２２０に供給する。
【００４０】
次に図１８を参照する。図１８は、ＬＤＰＣ復号化を行うためにＬＤＰＣ復号器１２５において用いられる全体処理の例証的なフロー図を示す。工程４０５では、ＬＤＰＣ符号化ブロックが、その中に記憶するためにエッジ・メモリ２２０にＬＬＲバッファ２１０から供給される。工程４１０及び４１５では、ＬＤＰＣ復号化が行われる。特に、検査ノード更新（工程４１０）及びビット・ノード更新（工程４１５）が、エッジ・メモリ２２０（以下に説明する）に記憶されたデータを処理する。工程４２０では、例えば、上記式（５）から、復号処理を終了すべきかを検査する。処理が終了させられた場合、実行は工程４０５に戻って、次のＬＤＰＣ符号化ブロックを復号化し始める。さもなければ、復号化は、工程４１０及び４１５を介して、もう一回の検査ノード更新及びビット・ノード更新に続く。単純にするために、エラー条件は図１８のフロー図に示していない。
【００４１】
前述の通り、エッジ・メモリ２２０は、ＬＤＰＣ符号化データを記憶し、図１８に示す検査ノード更新工程及びビット・ノード更新工程においてアクセスされる。エッジ・メモリ２２０は、記憶エレメントを表す。エッジ・メモリ２２０は、レジスタを用いて実現することが可能である。これは、高速アクセスを可能にする（設計の複雑度は高くなるが）。しかし、好ましくは、ＬＤＰＣ符号化ブロックの長さを前提とすれば、メモリ・バンクが、より適切な実現形態である。ＬＤＰＣ復号化処理では、ビット・ノードと検査ノードとの間の２部グラフの辺を通るメッセージ・パッシングが行われる。これは、図１９に概念的に示されている。図１９は、例証的な２部グラフの一部分を示す。例えば、ビット・ノードｎは、辺４０によって検査ノードｍに結合される。それによって、ビット・ノード・メッセージ４１及び検査ノード・メッセージ４２によって表すようにそれらの間のメッセージ・パッシングが可能になる。ＬＤＰＣ復号化処理において用いるメモリは検査ノードとビット・ノードとの間の辺（エッジ）と関連付けられるので、このメモリは本明細書ではエッジ・メモリと表す。そういうものとして、エッジ・メモリ２２０は、信号２３６を介した検査ノードからビット・ノードへのメッセージ｛ｕ（ｌ）ｍ，ｎ｝、又は、信号２４１を介したビット・ノードから検査ノードへのメッセージ｛ｖ（ｌ）ｎ，ｍ｝を記憶する。より具体的には、かつ、図１８のフロー図から分かり得るように、ＬＤＰＣ復号器１２５は、少なくとも２つの段階（検査ノード更新段階（例えば、図１８の工程４１０）及びビット・ノード更新段階（例えば、図１８の工程４１５））を有する。検査ノード更新段階の最初には、｛ｖ（ｌ−１）ｎ．ｍ｝がエッジ・メモリ２２０のメモリ位置に記憶される一方、検査ノード更新段階の最後には｛ｕ（ｌ）ｍ．ｎ｝が計算され、同じメモリ位置に記憶される。同様に、ビット・ノード更新段階では、｛ｕ（ｌ）ｍ．ｎ｝が読み出され、｛ｖ（ｌ）ｎ．ｍ｝が計算され、同じメモリ位置に記憶される。よって、部分的に並列のアーキテクチャでは、同じメモリ位置を用いて、ＬＤＰＣ復号器の段階に応じて｛ｖ（ｌ）ｎ．ｍ｝又は｛ｕ（ｌ）ｍ．ｎ｝が記憶される。
【００４２】
本発明の原理によれば、エッジ・メモリ２２０を、前述のパリティ行列再編成に従って、ビット・ノードによって、又は検査ノードによって編成することが可能である。必要な全体メモリ量は、いずれの場合にも同じである。辺の数は、特定のパリティ検査行列に対して固定である。
【００４３】
一実施例では、エッジ・メモリ２２０は、ビット・ノードによって例証的に編成される。この場合、一メモリ語を用いて、（前述の）巡回シフト単位行列に対応するメッセージ全てを記憶する。ビット・ノード群に関連付けられたメモリ語は、連続したアドレス位置に記憶される。これによって、ビット・ノード更新が単純になる。エッジ・メモリ２２０において用いる例証的なメモリ構造３２５を図２０に示す。エッジ・メモリ２２０のメモリは、ビット・ノードによって編成されるので、このメモリは、ビット・ノード・メモリ・バンクとしても表すことができる。
【００４４】
図１５に戻れば、エッジ・メモリ２２０に記憶されたデータが、ビット・ノード処理パス又は検査ノード処理パスに信号２２１を介して供給される。検査ノード処理パスに関しては、このパスは検査ノード更新段階（図１８の工程４１０）においてアクティブである。特に、データ（初期ＬＤＰＣ符号化データでも後続メッセージ・データでもよい）｛ｖ（ｌ−１）ｎ，ｍ｝が群ＣＰＵ処理２３０に、巡回シフタ２２５を介して処理される。エッジ・メモリ２２０がビット・ノードによって編成されるので、巡回シフタ２２５は、一検査ノード群のデータが合わせられるようにメモリ語内のデータを巡回的にシフトさせる。このことは図２１に示す。図２１は、検査ノード群０／ビット・ノード群０の巡回シフトの量を示す。群ＣＰＵ処理２３０は、｛ｕ（ｌ）ｍ，ｎ｝を計算し、｛ｕ（ｌ）ｍ，ｎ｝を巡回シフタ２３５に供給するための３６０個の検査ノード処理装置（以下に更に説明する）を備える。巡回シフタ２３５は、一ビット・ノード群のデータが合わせられるようにメモリ語内のデータをやはり再設定する。巡回シフタ２３５は、｛ｕ（ｌ）ｍ，ｎ｝を、信号２３６を介してエッジ・メモリ２２０にＭＵＸ２１５及び信号２１６を介して供給する。時間領域においてその動作を多重化することによって２つではなく１つの巡回シフタを用いることができる。次にビット・ノード処理パスに移れば、このパスはビット・ノード更新段階（図１８の工程４１５）においてアクティブである。特に、データ｛ｕ（ｌ）ｍ，ｎ｝が群ＢＰＵ処理２４０に供給される。群ＢＰＵ処理２４０は例証的には、｛ｖ（ｌ）ｎ，ｍ｝を計算し、｛ｖ（ｌ）ｎ，ｍ｝を信号２４１を介してエッジ・メモリ２２０にＭＵＸ２１５及び信号２１６を介して供給するための３６０個のビット・ノード処理装置（以下に更に説明する）を備える。
【００４５】
前述の通り、群ＣＰＵ２３０は、３６０個の検査ノード処理装置を備える。例証的な検査ノード処理装置（ＣＰＵ）２３０−Ｊ（０＜Ｊ≦３６０）を図２２に示す。ＣＰＵ２３０−Ｊは、入力メッセージ組｛ｅ０，ｅ１，…，ｅＤｃ−１｝を処理して、対応する出力メッセージ組｛ｅ’０，ｅ’１，…，ｅ’Ｄｃ−１｝を供給する。前述の通り、式（３）を、出力メッセージ組を生成するためにＬＤＰＣ復号化において用いる。しかし、式（３）におけるまさにその公式が実現された場合、各検査ノード処理装置の複雑度は増加する。実際に、考えられる最大の検査ノード次数が３０であるので、加算器配列及び関数ｆ（・）の実現形態は、関数ｆ（・）を単純なルックアップ・テーブルによって実現することが可能であっても非常に複雑になる。検査ノード処理装置の複雑度を削減するために、ＣＰＵ２３０−Ｊは以下の手法を実現する。特に、｛ｅ０，ｅ１，…，ｅＤｃ−１｝は、検査ノード処理装置（ＣＰＵ）への入力メーセージ組である。次いで、
ｓｋ＝ｓｉｇｎ（ｅｋ）  （７）
【数１２】
2008515342.tif 000014
（８）を計算する。
【００４６】
次に、組│ｅ０│，│ｅ１│，…，│ｅＤｃ−１│において３つの最小の値を選択し、それらに対応するインデクスをｍ０，ｍ１，ｍ２とする。その後、以下の４つの値を計算する。
【００４７】
λ０＝ｇ（│ｅｍ１│，│ｅｍ２│）  （９）
λ１＝ｇ（│ｅｍ０│，│ｅｍ２│）  （１０）
λ２＝ｇ（│ｅｍ０│，│ｅｍ１│）  （１１）
λ３＝ｇ（ｇ（│ｅｍ０│，│ｅｍ１│），│ｅｍ２│）  （１２）。
【００４８】
ここで、
ｇ（ｘ，ｙ）≒ｓｉｇｎ（ｘ）ｓｉｇｎ（ｙ）｛ｍｉｎ（│ｘ│，│ｙ│）−ｈ（││ｘ│−│ｙ││）｝  （１３）  及び
ｈ（ｘ）＝ｌｎ（１＋ｅ−ｘ）  （１４）である。  
次いで、出力メッセージ組｛ｅ’０，ｅ’１，…，ｅ’Ｄｃ−１｝が以下のように計算される。
【００４９】
ｅ’ｋ＝ｓｋ×Ｓ×（λ０（ｋ＝ｍ０の場合）、
λ１（ｋ＝ｍ１の場合）
λ２（ｋ＝ｍ２の場合）
λ３（ｋ≠ｍ０，ｍ１，ｍ２の場合））  （１５）
ここで、０＜ｋ≦ＤＣ−１である。前述の手法では、入力メッセージの３つの最小値のみを用いてＣＰＵの出力メッセージを計算する。この近似による性能低下は、ＤＶＢ−Ｓ２におけるＬＤＰＣ符号全てについて無視できる。
【００５０】
次にビット・ノード処理に移れば、群ＢＰＵ処理２４０は、３６０個のビット・ノード処理装置を備える。例証的なビット・ノード処理装置（ＢＰＵ）２４０−Ｉ（０＜Ｉ≦３６０）を図２３に示す。ＢＰＵ２４０−Ｉは、入力メッセージ組｛ｅ０，ｅ１，…，ｅＤＶ−１｝を処理して対応する出力メッセージ組｛ｅ’０，ｅ’１，…，ｅ’ＤＶ−１｝を供給する。ビット・ノード処理動作は、どちらかと言えば単純であり、図２４に更に示す。図２４では、語ＬＬＲは、ＬＬＲバッファ２１０から信号２１１を介して供給される関連ビット・ノードの対数尤度比を表す。
【００５１】
ＬＤＰＣ復号器１２５の最後の構成要素は、図１８の前述の工程４２０を実現する実行終了判定エレメント２４５である。図１５及び図２３から分かり得るように、信号２４２がビット・ノード処理パスから実行終了判定エレメント２４５に、その中で用いるために供給される。ＬＤＰＣ復号化が終了させられると、結果として生じるＬＤＰＣ復号化データが、前述のＢＣＨ復号器１３５に信号１２６を介して供給される。実行終了判定エレメント２４５は、ＬＤＰＣ復号化処理を続けるか、又は新たに始める（例えば、次のＬＤＰＣ符号化ブロックについて）ことに関するシグナリング（図示せず）を供給する。
【００５２】
前述の通り、ＤＶＢ−Ｓ２は、所定のパリティ行列によっていくつかの符号化率をサポートし、受信器は、受信ＤＶＢ−Ｓ２信号形式の所定部分に含まれたデータから符号化率を判定する。この意味合いで、コントローラ２９０は、判定された変調タイプを用いて、前述のＬＬＲ計算及び種々のインタリーブ手法（ＤＶＢ−Ｓ２に規定されているような）に対して種々のルックアップ・テーブル（図示せず）を選択する。コントローラ２９０は更に、前述の原理によって再編成されるパリティ行列によって種々の符号化率において受信ＬＤＰＣ符号化信号を処理するよう本発明の原理によってＬＤＰＣ復号器１２５を構成する。例えば、前述の部分行列算出（Ｈ（ｍ，ｎ））を、図６のテーブル２に示す種々のパラメータについて受信ＬＤＰＣ符号化データを処理するうえで後に用いるためにメモリ（例えば、図１５のコンフィグレーション・メモリ２９５）において事前に記憶することが可能である。
【００５３】
ＬＤＰＣ復号器１２５の別の例証的な実施例を図２５に示す。この配置は、図１５に示すもの、及び同様なやり方での機能（例えば、図１８、２２、２３及び２４）と（エッジ・メモリ２２０が、検査ノードによって編成され（、かつ、検査ノード・メモリ・バンクとして表すことが可能である）以外には）同様である。そういうものとして、２つの巡回シフタ２２５及び２３５はその場合、群ＢＰＵ処理２４０前後に配置される。やはり、単に、時間領域においてその動作を多重化することによって、２つではなく１つの巡回シフタを用いることができる。
【００５４】
検査ノードによるエッジ・メモリ２２０の編成に関しては、一検査ノード群に対応する検査ノード・メモリが集約され、一メモリ位置（例えば、語）を用いて、特定の巡回単位行列に対応するメッセージ全てを記憶する。すなわち、一メモリ語は、特定の巡回単位行列に関連した辺を介して送出されるメッセージ全てを記憶する。前述したように、かつ、図６のテーブル２に示すように、ＬＤＰＣ符号の場合、検査ノード全ての次数（Ｄｃ）は、検査ノード次数（Ｄｃ−１）を有する０番目の検査ノード以外は同じである。例証として、率が１／２のＬＤＰＣ符号を用いた以下の例を考えてみる（図６のテーブル２から、Ｄｃ＝７である）。６３番目の検査ノード群は、パリティ検査行列内の部分行列である（上記の例証の用に算出された）、以下の正方形行列に対応する。
【００５５】
Ｈ（６３，１）＝Ｉ（３３）＋Ｉ（８０）；
Ｈ（６３，９）＝Ｉ（０）；
Ｈ（６３，２９）＝Ｉ（３２４）；
Ｈ（６３，３４）＝Ｉ（１３２）；
Ｈ（６３，６２）＝Ｉ（０）；及び
Ｈ（６３，６３）＝Ｉ（０）
６３番目の検査ノード群に対応するエッジ・メモリ２２０内の例証的なメモリ・バンク３０５を図２６に示す。メモリ・バンク３０５の各行が単一のメモリ語として扱われる場合、検査ノード群について示すように、Ｄｃ＝７のメモリ語のみが必要である。実際に、検査ノード全てのメモリ・バンク全てをその場合、集約し、線形的にアドレス指定することが可能である。エッジ・メモリ２２０のこの例証的なメモリ構造３１０を図２７に示す。メモリ構造３１０のエッジ・メモリ２２０のアドレス空間は、｛０，１，２，…，ｑＤｃ−１｝である。すなわち、アドレス空間のサイズは（ｑ×Ｄｃ）である。種々のＬＤＰＣ符号に必要なメモリ空間を図２８のテーブル３に示す。テーブル３から分かり得るように、必要なメモリ語の最大数は７９２である。やはり、各ビット・ノード・メッセージ又は検査ノード・メッセージが６ビット幅であるものとする場合、メモリ語のビット幅は、３６０×６＝２１６０ビットである。
【００５６】
本発明の概念の別の例証的な実施例を図２９に示す。この例証的な実施例では、受信器（図示せず）において用いるための集積回路（ＩＣ）７０５は、ＬＤＰＣ復号器７２０と、バス７５１に結合された少なくとも１つのレジスタ７１０とを含む。例証的には、ＩＣ７０５は、一体化された復調器／復号器である。しかし、本発明の概念に適切なＩＣ７０５の部分のみを示す。例えば、アナログ・ディジタル変換器、フィルタ、復号器等は、単純にするために示していない。バス７５１は、プロセッサ７５０によって表される、受信器のその他の構成部分との間の通信を実現する。レジスタ７１０は、ＩＣ７０５の１つ又は複数のレジスタを表す。各レジスタは、ＩＣ７０５の動作を制御するためのビット７０９によって表される１つ又は複数のビットを備える。ＩＣ７０５のレジスタ、又はその一部分は、読み出し専用、書き込み専用、又は読み出し／書き込みであり得る。ＬＤＰＣ復号器７２０は、当該技術分野において知られているようにＬＤＰＣ復号器７２０をレジスタ７１０にインタフェースするためのその他の信号パス、及び／又はＩＣ７０５の構成部分を表す内部バス７１１を介してレジスタ７１０に結合される。本発明の原理によれば、ＬＤＰＣ復号器７２０は前述の群ＣＰＵ及び群ＢＰＵを含む。図１４の意味合いでは、ＩＣ７０５は、ＩＣ７０５の入力ピン又はリードを介して処理するためにＩＦ信号７０１（例えば、図１４の信号１１６）を受信する。この信号の派生物７０２が、前述（例えば、図１５及び図２４）の本発明の原理によるＬＤＰＣ復号化のためのＬＤＰＣ復号器７２０に印加される。ＬＤＰＣ復号器７２０は信号７２１（ＬＤＰＣ復号化ビット・ストリーム）を供給する。ＩＣ７０５は、信号７０６によって表す１つ又は複数の再生信号を供給する。例えば、信号７０６は、ＩＣ７０５のＢＣＨ復号器（図示せず）からの信号１３６を表す。ＩＣ７０５の別の変形では、信号７０６は、図１３の信号１０６を表す。
【００５７】
前述の通り、かつ本発明の原理によれば、各種の符号化率を扱うことができるＬＤＰＣ復号器を説明し、示す。更に、前述の巡回シフト単位行列は、置換行列に同様に一般化することが可能である。この場合、前述の巡回シフタは、置換ネットワークによって置換される。
【００５８】
上記に鑑みれば、衛星通信システムの意味合いで説明したが、本発明の概念はそのように限定されるものでない。例えば、図１３の構成要素は、他のタイプのシステム及び他の形態のマルチメディア端点を表すことができる。例えば、衛星ラジオ、地上放送、ケーブルＴＶ等である。更に、単一の復調器の意味合いで本明細書において説明しているが、本発明の概念は、複数の変調受信器（情報を別々の信号層上で伝えることができる）に適用可能である。例えば、レイヤード変調受信器、階層型受信器、又はそれらの組み合わせである。実際に、本発明は、ＬＤＰＣ復号化が行われる何れかのタイプの受信器に適用可能である。そういうものとして、本発明の概念は、ＤＶＢ−Ｓ２  ＬＤＰＣ符号の復号化に限定されるものでない。
【００５９】
そういうものとして、上記は、本発明の原理を例証しているに過ぎず、よって、当業者が、本明細書に明示していないが、本発明の原理を実施し、その趣旨及び範囲内に収まる数多くの別の配置を考え出すことができることが認識されよう。例えば、別個の機能的構成要素の意味合いで例証しているが、前述の機能的構成要素は、１つ又は複数の回路（ＩＣ）上に実施することができる。同様に、別個の構成要素として示しているが、構成要素の何れか又は全てを、ストアードプログラム制御プロセッサ（例えば、関連したソフトウェアを実行するディジタル信号プロセッサ（ＤＳＰ）やマイクロプロセッサ（例えば、図１４、図１５、及び／又は図２４等に示す構成要素の１つ又は複数に対応する））において実現することができる。更に、別個の構成要素として示したが、その中の構成要素は、それらの何れかの組み合わせにおける別々の装置に分散させることができる。例えば、受信器１０５は、ＴＶ９０の一部であり得るか、又は、受信器１０５は、配信システムにおける更にアップストリーム（例えば、ヘッドエンド）に配置し得る。それは次いで、ネットワークの他のノード及び／又は受信器にコンテンツを再送信する。よって、特許請求の範囲によって規定された本発明の趣旨及び範囲から逸脱することなく、数多くの修正を例証的な実施例に対して行うことができ、その他の配置を考え出すことができる。  
【図面の簡単な説明】
【００６０】
【図１】ＬＤＰＣ符号化に関するパリティ検査行列及び２部グラフを示す図である。
【図２】特定のＤＶＢ−Ｓ２  ＬＤＰＣ符号化パラメータを示すテーブル１である。
【図３】ＤＶＢ−Ｓ２  ＬＤＰＣパリティ検査行列についての特定の既知のデータを示す図である。
【図４】ＤＶＢ−Ｓ２  ＬＤＰＣパリティ検査行列についての特定の既知のデータを示す図である。
【図５】ＤＶＢ−Ｓ２  ＬＤＰＣパリティ検査行列についての特定の既知のデータを示す図である。
【図６】ＤＶＢ−Ｓ２  ＬＤＰＣ符号化についての特定のデータを更に示すテーブル２である。
【図７】本発明の原理によるパリティ検査行列の再編成を示す図である。
【図８】本発明の原理によるパリティ検査行列の再編成を示す図である。
【図９】本発明の原理によるパリティ検査行列の再編成を示す図である。
【図１０】本発明の原理によるパリティ検査行列の再編成を示す図である。
【図１１】本発明の原理によるパリティ検査行列の再編成を示す図である。
【図１２】本発明の原理によるパリティ検査行列の再編成を示す図である。
【図１３】本発明の原理を実施する例証的な通信システムの一部分を示す図である。
【図１４】本発明の原理による、受信器の例証的な実施例を示す図である。
【図１５】本発明の原理による、ＬＤＰＣ復号器の例証的な実施例を示す図である。
【図１６】本発明の原理による、ＬＤＰＣ復号器において用いるための例証的なメモリ構造を示す図である。
【図１７】本発明の原理による、ＬＤＰＣ復号器において用いるための例証的なメモリ構造を示す図である。
【図１８】図１５のＬＤＰＣ復号器において用いるための本発明の原理による例証的なフロー図である。
【図１９】図１５に示す実施例に関するメッセージ・パッシングを示す図である。
【図２０】本発明の原理による、ＬＤＰＣ復号器において用いるための例証的なメモリ構造を示す図である。
【図２１】図１５に巡回シフト器の動作を示す図である。
【図２２】図１５のＬＤＰＣ復号器において用いるための例証的な検査ノード処理装置を示す図である。
【図２３】図１５のＬＤＰＣ復号器において用いるための例証的なビット・ノード処理装置を示す図である。
【図２４】図１５のＬＤＰＣ復号器において用いるための例証的なビット・ノード処理装置を示す図である。
【図２５】本発明の原理による別の例証的な実施例を示す図である。
【図２６】本発明の原理による別の例証的な実施例を示す図である。
【図２７】本発明の原理による別の例証的な実施例を示す図である。
【図２８】本発明の原理による別の例証的な実施例を示す図である。
【図２９】本発明の原理による別の例証的な実施例を示す図である。
【図１】
2008515342.tif 000015
【図２】
2008515342.tif 000016
【図３】
2008515342.tif 000017
【図４】
2008515342.tif 000018
【図５】
2008515342.tif 000019
【図６】
2008515342.tif 000020
【図７】
2008515342.tif 000021
【図８】
2008515342.tif 000022
【図９】
2008515342.tif 000023
【図１０】
2008515342.tif 000024
【図１１】
2008515342.tif 000025
【図１２】
2008515342.tif 000026
【図１３】
2008515342.tif 000027
【図１４】
2008515342.tif 000028
【図１５】
2008515342.tif 000029
【図１６】
2008515342.tif 000030
【図１７】
2008515342.tif 000031
【図１８】
2008515342.tif 000032
【図１９】
2008515342.tif 000033
【図２０】
2008515342.tif 000034
【図２１】
2008515342.tif 000035
【図２２】
2008515342.tif 000036
【図２３】
2008515342.tif 000037
【図２４】
2008515342.tif 000038
【図２５】
2008515342.tif 000039
【図２６】
2008515342.tif 000040
【図２７】
2008515342.tif 000041
【図２８】
2008515342.tif 000042
【図２９】
2008515342.tif 000043
【国際調査報告】
2008515342.tif 000044
2008515342.tif 000045