(57)【要約】  Ｋ個の初期シンボルの列がパリティ検査型の符号を用いて符号化される。Ｋ個の初期シンボルは、２より厳密に大きい位数ｑのガロア体に属する。符号は、それぞれが位数ｑのガロア体上で定義されたパリティ検査式を満たす（Ｎ−Ｋ）個の第１のノード（ＮＣｉ）、中間ノードのＮ個のパケット（ＮＩＴｉ）およびＮＩ個の第２のノード（ＮＳＳｉ）を含み、各中間ノードが接続方式によって１つの第１のノードと、複数の第２のノードとにリンクされているグラフ（ＧＲＨ）で表すことのできる符号特性によって定義される。Ｋ個の初期シンボルの列は上記符号特性を使用して符号化され、接続方式（Π）を表す細分化方式に従って、位数がｑ未満の数学的集合にそれぞれ属するＮＩ個のサブシンボルにそれぞれ細分化された、Ｎ個の符号化シンボルの列が獲得される。
2010539744.tif 000002
【特許請求の範囲】
【請求項１】
パリティ検査型の符号を用いてＫ個の初期シンボルの列を符号化する方法であって、
前記Ｋ個の初期シンボルは２より大きい位数ｑのガロア体に属し、
前記符号は、それぞれ前記位数ｑのガロア体上で定義されたパリティ検査式を満たす（Ｎ−Ｋ）個の第１のノード、中間ノードのＮ個のパケットおよびＮＩ個の第２のノードを含み、
各中間ノードが、接続方式によって、１つの第１のノードと複数の第２のノードとにリンクされているグラフで表すことのできる符号特性によって定義されており、
Ｋ個の初期シンボルの前記列は前記符号特性を使用して符号化され、前記接続方式を表す細分化方式に従って、位数がｑ未満の数学的集合にそれぞれ属するＮＩ個のサブシンボルにそれぞれ細分化されたＮ個の符号化シンボルの列が獲得される、方法。
【請求項２】
前記中間ノードのＮ個のパケットはそれぞれ前記Ｎ個の符号化シンボルと関連付けられており、
前記細分化方式は、符号化シンボルごとに、前記列内の前記対応するサブシンボルの数および各場所を含み、
前記数および前記各場所は、最終的に前記符号化シンボルと関連付けられた前記中間ノードのパケットになる前記接続方式の部分を表す、請求項１に記載の方法。
【請求項３】
ｑはｐが１より大きい２ｐに等しく、ｑ未満の各位数も２の整数乗であり、
前記符号特性の定義は、それぞれ前記（Ｎ−Ｋ）個のパリティ検査式と関連付けられたｐ行の（Ｎ−Ｋ）個の群とそれぞれ前記Ｎ個のシンボルと関連付けられたｐ列のＮ個の群とを有し、
ｐ行の各群は、考察される前記ｐ行の各群と関連付けられた前記パリティ検査式の非ゼロ係数の２値行列像をそれぞれ形成するｐ行およびｐ列のビットブロックを含み、
前記ビットブロックはそれぞれ、１つのシンボルと関連付けられ、前記ｐ行の各群上の異なる場所にそれぞれ位置するｐ行およびｐｉ列のｊビットのサブブロックに細分化され、前記数ｊおよびｉが１からｊまで変化する数ｐｉの値、ならびに符号化シンボルと関連付けられたビットブロックを形成する前記サブブロックの場所の位置が、前記符号化シンボルと関連付けられた前記細分化方式の部分を表す第１の行列を形成することを含み、
前記符号化シンボルの列は、前記第１の行列と前記初期シンボルの列とに基づいて獲得される、請求項１または２に記載の方法。
【請求項４】
前記第１の行列を形成することは、前記パリティ検査式を表す第１の部分と、前記細分化方式をそれぞれ表す群分け指示を含む第２の部分とを含む初期行列を形成すること、および前記初期行列に基づいて前記第１の行列を決定することを含む、請求項１〜３のいずれかに記載の方法。
【請求項５】
前記初期行列の前記第１の部分は、前記位数ｑのガロア体に属する行の要素が前記パリティ検査式の前記係数を表す（Ｎ−Ｋ）行を含み、
前記初期行列の第２の部分は、前記ＮＩ個の第２のノードとそれぞれ関連付けられた、行の要素が前記群分け指示を形成するＮＩ行を含み、
前記初期行列の前記第１の部分と前記第２の部分は、中間ノードの数と等しい同数の列を有する、請求項４に記載の方法。
【請求項６】
前記初期行列の前記第２の部分は、前記初期行列のために所定の閾値以上のグラフ半径を獲得するように形成される、請求項５に記載の方法。
【請求項７】
前記所定の閾値は６である、請求項６に記載の方法。
【請求項８】
位数がｑ未満の前記数学的集合はすべて同じ位数を示す、請求項１〜７のいずれかに記載の方法。
【請求項９】
前記数学的集合はガロア体である、請求項１〜８のいずれかに記載の方法。
【請求項１０】
２ｐ未満の各位数が２ｐ／ｎｓに等しく、ＮＩがｎｓとＮの積に等しい、請求項３に記載の方法。
【請求項１１】
前記シンボル細分化方式を表す指示が提供される、請求項１〜１０のいずれかに記載の方法。
【請求項１２】
２より厳密に大きい位数ｑのガロア体に属するＫ個の初期シンボルの列を受け取る入力と、
それぞれ前記位数ｑのガロア体上で定義されたパリティ検査式を満たす（Ｎ−Ｋ）個の第１のノード、中間ノードのＮ個のパケットおよびＮＩ個の第２のノードを含み、各中間ノードが、接続方式によって、１つの第１のノードと複数の第２のノードとにリンクされているグラフで表すことのできる符号特性を備える記憶手段と、
前記入力と前記記憶手段とに結合された、前記接続方式を表す細分化方式に従って、位数がｑ未満の数学的集合にそれぞれ属するＮＩ個のサブシンボルにそれぞれ細分化されたＮ個の符号化シンボルの列を形成することのできる符号化手段と、
を備える符号化装置。
【請求項１３】
前記中間ノードのＮ個のパケットはそれぞれ前記Ｎ個の符号化シンボルと関連付けられており、
前記細分化方式は、符号化シンボルごとに、前記列内の前記対応するサブシンボルの数および各場所を含み、
前記数および前記各場所は、最終的に前記符号化シンボルと関連付けられた前記中間ノードパケットになる前記接続方式の部分を表す、請求項１２に記載の符号化装置。
【請求項１４】
ｑはｐが１より大きい２ｐに等しく、ｑ未満の各位数も２の整数乗であり、前記符号特性も表す第１の行列を形成することのできる処理手段をさらに備え、
前記第１の行列は、それぞれ前記（Ｎ−Ｋ）個のパリティ検査式と関連付けられたｐ行の（Ｎ−Ｋ）個の群とそれぞれ前記Ｎ個のシンボルと関連付けられたｐ列のＮ個の群とを有し、
ｐ行の各群は、考察される前記ｐ行の各群と関連付けられた前記パリティ検査式の非ゼロ係数の２値行列像をそれぞれ形成するｐ行およびｐ列のビットブロックを含み、
前記ビットブロックはそれぞれ、１つの符号化シンボルと関連付けられ、前記ｐ行の各群上の異なる場所にそれぞれ位置するｐ行およびｐｊ列のｊビットのサブブロックに細分化され、
前記数ｊおよびｉが１からｊまで変化する数ｐｉの値、ならびに符号化シンボルと関連付けられたブロックを形成する前記サブブロックの場所の位置は、前記符号化シンボルと関連付けられた前記細分化方式の部分を表し、
前記符号化手段は、前記第１の行列に基づいて前記符号化シンボルの列を形成することができる、請求項１２または１３に記載の符号化装置。
【請求項１５】
前記処理手段は、さらに、前記パリティ検査式を表す第１の部分と、前記細分化方式をそれぞれ表す群分け指示を含む第２の部分とを含む初期行列を形成し、前記初期行列に基づいて前記第１の行列を決定することができる、請求項１２〜１４のいずれかに記載の符号化装置。
【請求項１６】
前記初期行列の前記第１の部分は、前記位数ｑのガロア体に属する行の要素が前記パリティ検査式の前記係数を表す（Ｎ−Ｋ）行を含み、
前記初期行列の第２の部分は、前記ＮＩ個の第２のノードとそれぞれ関連付けられた、行の要素が前記群分け指示を形成するＮＩ行を含み、
前記初期行列の前記第１の部分と前記第２の部分は、中間ノードの数と等しい同数の列を有する、請求項１５に記載の符号化装置。
【請求項１７】
前記初期行列は所定の閾値以上のグラフ半径を示す、請求項１６に記載の符号化装置。
【請求項１８】
前記所定の閾値は６である、請求項１７に記載の符号化装置。
【請求項１９】
位数がｑ未満の前記数学的集合はすべて同じ位数を示す、請求項１２〜１８のいずれかに記載の符号化装置。
【請求項２０】
位数がｑ未満の前記数学的集合はガロア体である、請求項１２から１９のいずれかに記載の符号化装置。
【請求項２１】
２ｐ未満の各位数が２ｐ／ｎｓに等しく、ＮＩがｎｓとＮの積に等しい、請求項１４に記載の符号化装置。
【請求項２２】
前記符号化手段は、前記シンボル細分化方式を表す指示を渡すことができる、請求項１２〜２１のいずれかに記載の符号化装置。
【請求項２３】
符号化シンボルの列を復号する方法であって、
各シンボルは、それぞれパリティ式を満たす第１のノード、第２のノードおよび中間ノードを含み、各中間ノードが、接続方式によって、１つの第１のノードと複数の第２のノードとにリンクされているグラフで表すことのできる符号特性によって定義されたパリティ検査型の符号を用いて符号化されており、
前記列の各符号化シンボルは、２より大きい位数ｑのガロア体に属し、前記接続方式を表す細分化方式に従って、位数がｑ未満の数学的集合にそれぞれ属するサブシンボルに細分化されており、前記細分化方式を考慮に入れて、前記位数ｑのガロア体における前記第１のノードの反復的更新が行われる一方で、前記位数がｑ未満の数学的集合における前記第２のノードの反復的更新が行われる、方法。
【請求項２４】
前記第１のノードの更新の前と後とに分散された前記中間ノードの処理も行われる、請求項２３に記載の方法。
【請求項２５】
前記第１および第２のノードの前記反復的更新は、前記第１のノードと、更新された第１のノードそれぞれの近隣に位置するノードの順次更新を含む、請求項２３または２４に記載の方法。
【請求項２６】
前記更新は確率伝搬型のアルゴリズムを使用して行われる、請求項２３〜２５のいずれかに記載の方法。
【請求項２７】
ｑはｐが１より大きい２ｐに等しく、ｑ未満の各位数も２の整数乗である、請求項２３〜２６のいずれかに記載の方法。
【請求項２８】
位数がｑ未満の前記数学的集合はすべて同じ位数を示す、請求項２３〜２７のいずれかに記載の方法。
【請求項２９】
位数がｑ未満の前記数学的集合はガロア体である、請求項２３〜２８のいずれかに記載の方法。
【請求項３０】
２ｐ未満の各位数が２ｐ／ｎｓに等しい、請求項２７に記載の方法。
【請求項３１】
前記グラフに対応する前記符号特性は行列形式で記憶される、請求項２３〜３０のいずれかに記載の方法。
【請求項３２】
前記パリティ検査型の符号パリティ式の係数および前記列内で前記シンボルをサブシンボルに細分化する前記方式を表す情報が行列形式で記憶される、請求項３１に記載の方法。
【請求項３３】
前記行列は、前記パリティ検査式を表す第１の部分と、前記符号化シンボルの細分をそれぞれ表す群分け指示を含む第２の部分とを含む、請求項３２に記載の方法。
【請求項３４】
Ｎ個の符号化シンボルの列が受け取られ、Ｋ個の復号シンボルの列が渡され、
前記行列の前記第１の部分は、前記位数ｑのガロア体に属する行の要素が前記パリティ検査式の前記係数を表す（Ｎ−Ｋ）行を含み、
前記行列の前記第２の部分は、前記ＮＩ個の第２のノードとそれぞれ関連付けられた、行の要素が前記群分け指示を形成するＮＩ行を含み、
前記行列の前記第１の部分と前記第２の部分は、中間ノードの数と等しい同数の列を有する、請求項３３に記載の方法。
【請求項３５】
パリティ検査型の符号を用いて符号化されたシンボルの列であり、各符号化シンボルが２より大きい位数ｑのガロア体に属し、細分化方式に従って、位数がｑ未満の数学的集合にそれぞれ属するサブシンボルに細分化されている前記列を受け取る入力と、
それぞれパリティ式を満たす第１のノード、第２のノードおよび中間ノードを含み、各中間ノードが、前記細分化方式を表す接続方式によって、１つの第１のノードと複数の第２のノードとにリンクされているグラフで表すことのできる前記符号の特性を記憶することのできる記憶手段と、
前記入力と前記記憶手段とに結合された、前記細分化方式を考慮に入れて、前記位数ｑのガロア体における前記第１のノードの反復的更新を行い、前記位数がｑ未満の数学的集合における前記第２のノードの反復的更新を行うことのできる復号手段とを備える、復号装置。
【請求項３６】
前記復号手段は、前記第１のノードの更新の前と後とに分散された前記中間ノードの処理を行うことができる、請求項３５に記載の復号装置。
【請求項３７】
前記復号手段は、前記第１のノード、および更新されるべき第１のノードそれぞれの近隣に位置するノードを順次に更新することができる、請求項３５または３６に記載の復号装置。
【請求項３８】
前記復号手段は、確率伝搬型のアルゴリズムを実施することができる、請求項３５〜３７のいずれかに記載の復号装置。
【請求項３９】
ｑはｐが１より大きい２ｐに等しく、ｑ未満の各位数も２の整数乗である、請求項３５〜３８のいずれかに記載の復号装置。
【請求項４０】
位数がｑ未満の前記数学的集合はすべて同じ位数を示す、請求項３５〜３９のいずれかに記載の復号装置。
【請求項４１】
位数がｑ未満の前記数学的集合はガロア体である、請求項３５〜４０のいずれかに記載の復号装置。
【請求項４２】
２ｐ未満の各位数が２ｐ／ｎｓに等しい、請求項３９に記載の復号装置。
【請求項４３】
前記記憶手段は、前記グラフに対応する前記符号特性を行列形式で記憶することができる、請求項３５〜４２のいずれかに記載の装置。
【請求項４４】
前記行列は、前記パリティ式の係数および前記列内で前記シンボルをサブシンボルに細分化する方式を表す情報を含む、請求項４３に記載の装置。
【請求項４５】
前記行列は、前記パリティ検査式を表す第１の部分と、前記様々な符号化シンボルの細分をそれぞれ表す群分け指示を含む第２の部分とを含む、請求項４４に記載の装置。
【請求項４６】
前記行列の前記第１の部分は、前記位数ｑのガロア体に属する行の要素が前記パリティ検査式の前記係数を表す行を含み、
前記行列の第２の部分は、前記ＮＩ個の第２のノードとそれぞれ関連付けられた、行の要素が前記群分け指示を形成するＮＩ行を含み、
前記行列の前記第１の部分と前記第２の部分は、中間ノードの数と等しい同数の列を有し、
前記入力はＮ個の符号化シンボルの列を受け取ることができ、
前記復号手段は、前記行列と前記Ｎ個のシンボルの列とに基づいて復号されたＫ個のシンボルの列を渡すことができる、請求項４５に記載の装置。
【請求項４７】
伝送路に結合された、請求項１２〜２２のいずれかに記載の符号化装置を備える通信施設。
【請求項４８】
伝送路に結合された、請求項３５〜４６のいずれかに記載の復号装置を備える通信施設。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パリティ検査型の符号に関し、特に符号特性を低密度を示す、すなわち少数の非ゼロ値を含む行列によって表すことができるパリティ検査型の符号に関する。
【背景技術】
【０００２】
このような符号は、低密度の、パリティ検査を有する符号であると考えることができ、当業者には、「ＬＤＰＣ」（低密度パリティ検査）符号という名で知られている。ＬＤＰＣ符号は、１９６２年にＧａｌｌａｇｅｒによって発表され、１９９６年にＭａｃ  ＫａｙおよびＮｉｅｌによって再発見された。ＬＤＰＣ符号は、特にその非常に優れた誤り訂正性能のために、現代の通信において基本的な役割を果たしている。
【０００３】
現在、一般に使用されているＬＤＰＣ符号はいわゆる２進（バイナリ）ＬＤＰＣ符号であり、すなわちこれらのＬＤＰＣ符号は２次のガロア体上で定義される。この場合「体（フィールド）」という語は、数学的な意味において理解されなければならず、ガロア体とは、有限個の要素を含む体であることを想起する。２進ＬＤＰＣ符号、すなわち２次のガロア体上で定義されたＬＤＰＣ符号は、ただ２つの値だけ、例えば０または１の値などを取り得るシンボルを含む。
【０００４】
理論的には、さらにいわゆる「非２進」ＬＤＰＣ符号、すなわち、例えば、１より厳密に大きい２の整数乗に等しいなど、２より厳密に大きい位数のガロア体上で定義されたＬＤＰＣ符号も知られている。非２進ＬＤＰＣ符号は、２進ＬＤＰＣ符号と比べてその誤り訂正における性能を著しく向上させることができるため有益である。言い換えると、２進ＬＤＰＣ符号は、特に、符号化すべきシンボル列のサイズが小さい場合には、より強固（ロバスト）である。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】C. Poulliat, M. Fossorier and D. Declercq, 「Design of non binary LDPC codes using their binary image: algebraic properties」, in the proc. of ISIT  '06, Seattle, USA, July 2006
【非特許文献２】David Declercq and Marc Fossorier, 「Decoding Algorithms for Nonbinary LDPC Codes over GF (q)」, IEEE Trans. On Commun., vol 55(4), pp. 633-643, April 2007
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非２進ＬＤＰＣ符号を用いて獲得される性能利得には、復号の複雑さおよび復号器に必要なメモリサイズの著しい増大を伴う。具体的には、例えば、位数２ｐのガロア体において定義されるＬＤＰＣ符号には、サイズ２ｐのメッセージを記憶する必要があり、今までこのメモリサイズ増大の問題は解決されていない。
【課題を解決するための手段】
【０００７】
本発明の一形態によれば、２より厳密に大きい位数ｑのガロア体上で定義されたシンボルの符号化、および、メモリサイズが低減された復号器の実施を可能にする、対応する復号化が提案される。
【０００８】
本発明の一形態によれば、ｑが２より厳密に大きい位数ｑのガロア体において定義されたシンボルを、位数がｑ未満の数学的集合に属する、等価のシンボルまたはサブシンボルの列に「投影」することが提案される。これらの数学的集合は、一個別例においては体であるが、より一般的には、加法演算子を備える、群（ｇｒｏｕｐ）や環（ｒｉｎｇ）といった任意の数学的構造である。
【０００９】
本発明の一形態によれば、それぞれパリティ検査式を満たす検査ノードを含むグラフ（ＧＲＨ）によって表すことのできる符号特性によって定義されたパリティ検査型の符号が形成される。非２進ＬＤＰＣ符号のグラフは検査ノードおよびシンボルノードを含み、これらのノードはすべて２より厳密に大きい位数ｑのガロア体上で定義され、シンボルノードは検査ノードとの関連で第１のリンク接続性を示し、検査ノードはシンボルノードとの関連で第２のリンク接続性を示す。
【００１０】
このようなグラフに関して、各シンボルノードは、それぞれ位数がｑ未満の数学的集合上で定義されたサブシンボルノード（等価のシンボル）に細分化され、各シンボルノードは中間ノードのパケットで置き換えられ、各中間ノードは１つの検査ノードにリンクされて、中間ノードとの関連で検査ノードの接続性が保持される。他方、各中間ノードは接続方式によって複数のサブシンボルノードにリンクされて、第１の接続性がサブシンボルノードのレベルまで伝達される。
【００１１】
その場合、非２進ＬＤＰＣ符号であるとみなすことのできない全く新しい符号構造が獲得されるが、以下でより詳細に示すように、復号器は、それにもかかわらず、サブシンボルの局所的再結合を使用して位数ｑのガロア体において局所的に復号を行う一方で、位数がｑ未満の集合においてサブシンボルノードを更新する。
【００１２】
本発明の別の一形態によれば、パリティ検査型の符号を用いてＫ個の初期シンボルの列を符号化する方法が提案される。Ｋ個の初期シンボルは２より厳密に大きい位数ｑのガロア体に属し、符号は、それぞれが位数ｑのガロア体上で定義されたパリティ検査式を満たす、検査ノードなどの名で呼ばれる（Ｎ−Ｋ）個の第１のノード（ＮＣｉ）を含むグラフで表すことのできる符号特性によって定義される。
【００１３】
グラフ（ＧＲＨ）は、さらに、中間ノードのＮ個のパケット（ＮＩＴｉ）と、「サブシンボルノード」などとも呼ばれる、ＮＩ個の第２のノード（ＮＳＳｉ）も含む。各中間ノードは、接続方式によって１つの第１のノードと複数の第２のノードとにリンクされる。
【００１４】
Ｋ個の初期シンボルの列（２１）は符号特性を使用して符号化され２０）、接続方式（Π）を表す細分化方式に従って、位数がｑ未満の数学的集合にそれぞれ属するＮＩ個のサブシンボルにそれぞれ細分化されたＮ個の符号化シンボルの列（Ｊ２）が獲得される。
【００１５】
各シンボルが同一数のサブシンボルに細分化される方が、特に簡単にするためには有利であるが、この細分化が不規則になる、すなわち、サブシンボルの数がシンボルごとに異なる可能性も十分にある。
【００１６】
同様に、やはり簡単にするためには、位数がｑ未満の数学的集合がすべて同じ位数を示す方が有利であるが、これらの数学的集合が異なる位数を示し得る場合も除外されない。
【００１７】
例えば、ｑがｐを１より厳密に大とする２ｐに等しいときには、ｑ未満の各位数も、２の整数乗、例えば２ｐ／ｎｓに等しいものとすることができる。この場合、ＮＩはｎｓ×Ｎの積に等しい。
【００１８】
本発明の一形態によれば、中間ノードのＮ個のパケットは、Ｎ個の符号化シンボルとそれぞれ関連付けられており、細分化方式は、各符号化シンボルごとに、列内の対応するサブシンボルの数および場所を含む。その数および場所は、最終的に上号化シンボルと関連付けられた中間ノードのパケットになる接続方式の部分を表す。
【００１９】
本発明の一形態によれば、ｑはｐが厳密に１より大きい２ｐに等しく、ｑ未満の各位数も２の整数乗であり、上号特性の定義は、それぞれ（Ｎ−Ｋ）個のパリティ検査式と関連付けられたｐ行の（Ｎ−Ｋ）個の群と、それぞれＮ個のシンボルと関連付けられたｐ列のＮ個の群とを有する第１の行列（Ｈ）を形成することを含む。ｐ行の各群は、考察される上記ｐ行の各群と関連付けられたパリティ検査式の非ゼロ係数の２値行列像をそれぞれ形成するｐ行およびｐ列のビットブロックを含む。そのビットブロックはそれぞれ、１つのシンボルと関連付けられ、ｐ行の各群上の異なる場所にそれぞれ位置するｐ行およびｐｉ列のｊビットのサブブロックに細分化される。数ｊおよびｉが１からｊまで変化する数ｐｉの値、ならびに符号化シンボルと関連付けられたブロックを形成するサブブロックの様々な場所の位置は、上号化シンボルと関連付けられた細分化方式の一部を表し、符号化シンボルの列は、第１の行列と初期シンボルの列とに基づいて獲得される。例えば、符号化シンボルの列を獲得することは、第１の行列を、第２の行列（「生成行列」ともいう）を獲得するように対角化すること、および第２の行列を初期シンボルの列と乗算することを含み得る。
【００２０】
一変形として、符号化シンボルの列を獲得することは、第１の行列を、第２の行列を獲得するように三角化すること、および第２の行列と初期シンボルの列を使用して冗長サブシンボルを再帰的に計算することを含み得る。
【００２１】
本発明の一形態によれば、第１の行列を形成することは、パリティ検査式を表す第１の部分（Ｅ１）と、細分化方式をそれぞれ表す様々な群分け指示を含む第２の部分（Ｅ２）とを含む初期行列（ＭＩＮ）を形成すること、および初期行列に基づいて第１の行列を決定することを含む。
【００２２】
この初期行列は、従来の意味でのパリティ行列に含まれるものではなく、符号構造を完全に記述し、シンボル細分化方式を、特に著しく簡単なやり方で表す指示を提供することを可能にするものである。
【００２３】
より正確には、例えば、初期行列の第１の部分は、位数ｑのガロア体に属するその各要素が様々なパリティ検査式の係数を表す（Ｎ−Ｋ）行を含み、初期行列の第２の部分は、ＮＩ個の第２のノードとそれぞれ関連付けられた、その各要素が様々な群分け指示を形成するＮＩ行を含み、初期行列の第１の部分と第２の部分とが中間ノードの数と等しい同数の列を有する。
【００２４】
初期行列の第２の部分を、上記初期行列が全体として取られる場合に、所定の閾値以上のグラフ半径を獲得するように形成するのが特に有利である。ここで、グラフ半径とは、当業者に周知の用語法によれば、符号を表すグラフの最小周期に対応するものであることを想起する。周期とは、任意のノードから開始し同じノードに戻るグラフのリンクに沿った経路を表す。可能な限り大きいグラフ半径を有することは、誤り訂正に関して復号の性能をさらに改善することを可能にする。よって、例えば、所定の閾値に６を選択することが可能になる。
【００２５】
復号のためには、簡単に実現できるように、シンボル細分化方式を表す指示（ＭＩＮ）も提供することが好ましい。とはいえ、そのような指示は不可欠ではない。というのは、適切なアルゴリズムを使用すれば、復号器のレベルにおいて、各シンボルの２値像が識別されるまで、符号化ブロックにおいて使用されたすべての可能な細分を決定することが常に可能だからである。シンボル細分化方式を表すこの指示は、任意の適切な形をとり得るが、これの特に簡単な表現が上記の初期行列である。
【００２６】
別の一態様によれば、２より厳密に大きい位数ｑのガロア体に属するＫ個の初期シンボルの列（Ｊ１）を受け取る入力（ＥＮ１）と、それぞれ位数ｑのガロア体上で定義されたパリティ検査式を満たす（Ｎ−Ｋ）個の第１のノード（ＮＣｉ）、中間ノードのＮ個のパケット（ＮＩＴｉ）、およびＮＩ個の第２のノード（ＮＳＳｉ）を含み、各中間ノードが接続方式（Π）によって１つの第１の検査ノードと複数の第２のノードとにリンクされているグラフで表すことのできる符号特性を備える記憶手段（ＭＭ１）と、入力と記憶手段とに結合された、接続方式を表す細分化方式に従って、位数がｑ未満の数学的集合にそれぞれ属するＮＩ個のサブシンボルにそれぞれ細分化されたＮ個の符号化シンボルの列（Ｊ２）を形成することのできる符号化手段（ＭＥＮＣ）と、を備える符号化装置も提供される。
【００２７】
ｑはｐが１より大きい２ｐに等しく、ｑ未満の各位数も２の整数乗である一実施形態によれば、この装置はさらに、符号特性も表す第１の行列を形成することのできる処理手段（ＭＴＣ）を備え、この第１の行列は、それぞれ（Ｎ−Ｋ）個のパリティ検査式と関連付けられたｐ行の（Ｎ−Ｋ）個の群と、それぞれＮ個のシンボルと関連付けられたｐ列のＮ個の群とを有し、ｐ行の各群は、考察される上記ｐ行の各群と関連付けられたパリティ検査式の非ゼロ係数の２値行列像をそれぞれ形成するｐ行およびｐ列のビットブロックを含み、これらのブロックはそれぞれ、１つの符号化シンボルと関連付けられ、上記ｐ行の各群上の異なる場所にそれぞれ位置するｐ行およびｐｉ列のｊビットのサブブロックに細分化され、数ｊおよびｉが１からｊまで変化する数ｐｉの値、ならびに符号化シンボルと関連付けられたブロックを形成するサブブロックの様々な場所の位置は、符号化シンボルと関連付けられた細分化方式の一部を表し、符号化手段（ＭＥＮＣ）は、上記第１の行列に基づいて符号化シンボルの列を形成することができる。
【００２８】
本発明の一実施形態によれば、処理手段はさらに、パリティ検査式を表す第１の部分と、細分化方式をそれぞれ表す様々な群分け指示を含む第２の部分とを含む初期行列を形成し、初期行列に基づいて上記第１の行列を決定することができる。
【００２９】
別の一態様によれば、符号化シンボルの列を復号する方法であって、各シンボルが、それぞれパリティ式を満たす第１のノード、第２のノードおよび中間ノードを含み、各中間ノードが接続方式によって１つの第１のノードと複数の第２のノードとにリンクされているグラフで表すことのできる符号特性によって定義されるパリティ検査型の符号を用いて符号化されており、列の各符号化シンボルが、２より厳密に大きい位数ｑのガロア体に属し、接続方式を表す細分化方式に従って、位数がｑ未満の数学的集合にそれぞれ属するサブシンボルに細分化されており、細分化方式を考慮に入れて、位数ｑのガロア体における第１のノードの反復的更新（１３１２）が行われる一方で、位数がｑ未満の上記数学的集合における第２のノードの反復的更新（１３１０）も行われる方法も提案される。
【００３０】
様々なノードの反復的更新は並列的に行われ得る。すなわち、すべての第２のノードの反復的更新が行われ、次いですべての第１のノードの更新が行われる。とはいえ、第１のノードと、更新された第１のノードの近隣に位置するノードとを順次更新する方がより有利である。
【００３１】
また、この方法は、第１のノードの更新の前と後とに分散された中間ノードの処理（１３１１、１３１３）も含む。より正確には、例えば、中間ノードの処理は、第１のノードの更新の前に行われる第１の再結合副処理と、次いで、第１のノードの更新の後に行われる第２の副処理または周辺化処理とを含む。例えば、確率伝搬型のアルゴリズム（当業者に周知の用語によればＢＰアルゴリズム）を使用してノードの更新を行うことも可能である。
【００３２】
復号では、例えば、グラフに対応する符号特性を行列形式（ＭＩＮ）で記憶することも可能である。よって、この行列形式での記憶は、例えば、パリティ式の様々な係数、および列内でシンボルをサブシンボルに細分化する方式を表す情報などを含む。
【００３３】
別の一態様によれば、列の各符号化シンボルが２より厳密に大きい位数ｑのガロア体に属し、細分化方式に従って、位数がｑ未満の数学的集合にそれぞれ属するサブシンボルに細分化されている、パリティ検査型の符号を用いて符号化されたシンボルの列を受け取る入力（ＥＮ２）と、それぞれパリティ式を満たす第１のノード、第２のノードおよび中間ノードを含み、各中間ノードが、細分化方式を表す接続方式によって、１つの第１のノードと複数の第２のノードとにリンクされているグラフで表される上記符号の特性を記憶することのできる記憶手段（ＭＭ２）と、入力と記憶手段とに結合された、細分化方式を考慮に入れて、位数ｑのガロア体における第１のノードの反復的更新を行い、位数がｑ未満の数学的集合における第２のノードの反復的更新を行うことのできる復号手段（ＭＤＥＣ）とを備える復号装置が提案される。
【００３４】
一形態によれば、復号手段は、第１のノードの更新の前と後とに分散される中間ノードの処理も行うことができる。復号手段は、様々な第１のノード、および更新された第１のノードそれぞれの近隣に位置するノードを、順次に更新することができる。復号手段は、確率伝搬型のアルゴリズムを実施することができる。
【００３５】
一形態によれば、記憶手段は、グラフに対応する符号特性を、行列形式で記憶することができる。行列は、パリティ式の様々な係数、および列内でシンボルをサブシンボルに細分化する方式を表す情報を含む。行列は、パリティ検査式を表す第１の部分と、様々な符号化シンボルの細分をそれぞれ表す様々な群分け指示を含む第２の部分とを備える。
【００３６】
一形態によれば、行列の第１の部分は、位数ｑのガロア体に属するその各要素が様々なパリティ検査式の係数を表す（Ｎ−Ｋ）行を含み、行列の第２の部分は、ＮＩ個の第２のノードとそれぞれ関連付けられた、その各要素が様々な群分け指示を形成するＮＩ行を備え、行列の第１の部分と第２の部分は中間ノードの数と等しい同数の列を有し、上記入力は、Ｎ個の符号化シンボルの列を受け取ることができ、復号手段は、上記行列と、Ｎ個のシンボルの列とに基づいて復号されたＫ個のシンボルの列を渡すことができる。
【００３７】
別の態様によれば、伝送路に結合された、前述のような符号化装置を備える通信施設が提案される。さらに、伝送路に結合された、前述のような復号装置を備える通信施設が提案される。
【００３８】
本発明の他の利点および特徴は、全く限定されない実施形態および実現形態の詳細な説明、ならびに添付の図面を考察すれば明らかになる。
【図面の簡単な説明】
【００３９】
【図１】符号化装置の一実施形態を備える通信施設と、復号装置の一実施形態を備える通信施設とを概略的に示す図である。
【図２】例示的細分化符号構造を使用した符号化の一実現形態を概略的に示す図である。
【図３】細分化符号構造に関連するグラフの例を示す図である。
【図４】細分化符号構造に関連するグラフの例を示す図である。
【図５】細分化符号構造に関連する、特に行列形式の符号特性構築の例を概略的に示す図である。
【図６】細分化符号構造に関連する、特に行列形式の符号特性構築の例を概略的に示す図である。
【図７】細分化符号構造に関連する、特に行列形式の符号特性構築の例を概略的に示す図である。
【図８】細分化符号構造に関連する、特に行列形式の符号特性構築の例を概略的に示す図である。
【図９】細分化符号構造に関連する、特に行列形式の符号特性構築の例を概略的に示す図である。
【図１０】細分化符号構造に関連する、特に行列形式の符号特性構築の例を概略的に示す図である。
【図１１】細分化符号構造に関連する、特に行列形式の符号特性構築の例を概略的に示す図である。
【図１２】細分化符号構造に関連する、特に行列形式の符号特性構築の例を概略的に示す図である。
【図１３】細分化構造符号の復号の実現形態を示す図である。
【図１４】細分化構造符号の復号の実現形態を示す図である。
【図１５】細分化構造符号の復号の実現形態を示す図である。
【図１６】細分化符号構造の例を使用した復号性能の例を示す図である。
【図１７】細分化符号構造の例を使用した復号性能の例を示す図である。
【発明を実施するための形態】
【００４０】
図１において、参照符号ＡＰＰ１は、伝送設備、例えば、無線通信システムに属する無線設備を表すが、本発明はこの種の用途だけに限定されるものではなく、例えば、光ファイバやモデムを介して情報を交換することのできる伝送設備などといった多くの用途を包含するものである。
【００４１】
より一般的には、本発明は、超高スループットでの伝送、ならびに、特に、現在使用されているリードソロモン型の符号に取って代わるための、ハードディスクなどといった磁気記録の用途などにおいて特に活用され得る。
【００４２】
設備ＡＰＰ１は、出力ＳＯＲ１において、実際には以下でより詳細に示すように細分化されたシンボルである、Ｎ個の符号化シンボルの連続した列を渡すように、Ｋ個の初期シンボルの連続した列を受け取ることのできる入力ＥＮ１を有する符号化装置ＤＥＮＣを備える。この符号化を行うために、装置ＤＥＮＣは、入力ＥＮ１と出力ＳＯＲ１の間に結合された、メモリ手段などの記憶手段ＭＭ１に記憶された符号特性を使用する符号化手段ＭＥＮＣを備える。
【００４３】
この例において、設備ＡＰＰ１の送信チェーンは、例えば、Ｍ−ＰＳＫ型の変調や、Ｍ−ＱＡＭ型の変調といった当業者に周知の任意の種類の変調を実施することのできる変調手段も備える。その後、情報は、アンテナＡＮＴにより通信路ＣＨＮ、この場合は無線で送信される。参照符号ＡＰＰ２は、アンテナＡＮＴを有する受信チェーンを備える受信設備を表す。
【００４４】
それ自体は公知の従来の構造のものである復調手段ＤＮＤＭが復調処理を行い、特に、実際には確率情報であるＮ個の情報項目を渡す。加えて、以下でより詳細に示すように、各情報項目は、実際には、ベクトルである。
【００４５】
これらＮ個の情報項目は、実際には送信されたＮ個の符号化シンボルに対応しており、復号装置ＤＤＣの入力ＥＮ２に渡される。この復号装置ＤＤＣは、符号化に使用されるのと同じ符号特性を使用する復号手段ＭＤＥＣを備える。また、これらの符号特性は、例えば、メモリ型などの記憶手段ＭＭ２にも記憶される。
【００４６】
復号手段の出力ＳＯＲ２は、Ｋ個の復号シンボルの推定を提供する。Ｋ個の初期シンボルの各列の各シンボルは、ｑが厳密に２より大きい、（当業者が通例使用する用語によれば）ＧＦ（ｑ）と呼ばれる位数ｑのガロア体上で定義されたシンボルである。したがって、各初期シンボルは、ｑ個の値を取ることができる。本発明はそれだけに限定されるものではないが、これ以後本明細書において、ｑはｐが厳密に１より大きい２ｐに等しいものとみなす。この場合、各シンボルは、ｐビットの集合で表すことができ、これらのビットはそれぞれ０または１の値を取り得る。
【００４７】
図２に示すように、Ｋ個の初期シンボルの列Ｊ１が、メモリＭＭ１に含まれる符号特性を使用して符号化され（ステップ２０）、Ｎ個の符号化シンボルの列Ｊ２が渡される。また、これらＮ個の符号化シンボルもそれぞれガロア体ＧＦ（ｑ）上で定義されたものであるが、サブシンボルに細分化されており、したがってこの列Ｊ２は、ＮＩ個の符号化サブシンボルからなる。
【００４８】
各サブシンボルは、位数がｑ未満の、本明細書で説明する例ではやはり体である数学的集合上で定義されている。加えて、符号化シンボルを形成するサブシンボルの数は各シンボルごとに異なっていても同一であってもよい。同様に、各サブシンボルのサイズも、シンボルごとに異なり得る。とはいえ、簡単にするために、ここでは、符号化サブシンボルがすべて、ｑ未満の同一の位数を有する、体などの同じ数学的集合上で定義されているものと仮定する。
【００４９】
より詳細には、以下において、各符号化シンボルはｎｓ個のサブシンボルに細分化されているものと仮定する。したがって、各サブシンボルは結果的にガロア体ＧＦ（２ｐ／ｎｓ）上で定義されたものとなる。言い換えると、Ｎ個の符号化シンボルの列Ｊ２は、実際には、ＮＩ個の符号化サブシンボルを含み、ＮＩはｎｓ×Ｎの積に等しい。このような符号構造を、以後、「細分化されたシンボルを有する符号構造」またはより簡単に「細分化符号構造」と呼ぶ。
【００５０】
次にｎｓ＝４である図３を参照すると、このような細分化符号構造が、当業者が一般に使用する用語法によれば「検査ノード」とも呼ばれる、Ｍ＝（Ｎ−Ｋ）個の第１のノードＮＣｉを含むグラフＧＲＨで表すことのできる符号特性を示すことがわかる。これら第１のノードはそれぞれ、あとでより詳細に説明する、位数ｑのガロア体上で定義されているパリティ検査式を満たす。また、グラフＧＲＨは、「サブシンボルノード」ＮＳＳｊとも呼ばれるＮＩ個の第２のノードも含む。加えて、グラフは、中間ノードのＮ個のパケットＮＩＴｉも含み、中間ノードのＮ個のパケットは、Ｎ個の符号化シンボルとそれぞれ関連付けられている。各中間ノードは、本明細書ではΠと呼ぶ接続方式によって１つの検査ノードと、複数のサブシンボルノードとにリンクされている。実際には、Ｎ個の符号化シンボルの列Ｊ２は、接続方式Πを表す細分化方式に従ってＮＩ個のシンボルに細分化されている。
【００５１】
また、この細分化方式は、各符号化シンボルごとに、Ｊ２内の対応するサブシンボルの数および各場所を含み、この数および各場所は、最終的に符号化シンボルと関連付けられた中間ノードのパケットになる接続方式の部分を表す。
【００５２】
図４の左部分は、ＧＦ（ｑ）上で定義された検査ノード（この場合は３個）ＮＣ１〜ＮＣ３と２つのシンボルノードＡ１およびＡ２を含む、ＧＦ（ｑ）上の従来の非２進ＬＤＰＣ符号のグラフの一部を表す。このグラフの部分には、各シンボルノードＡ１およびＡ２が、検査ノードとの関連で接続度２を示すことが示されている。本発明の一特徴は、シンボルノードを位数がｑ未満のガロア体上で定義されたサブシンボルノードに「投影」または変換することにあり、結果的には、例えば図４の右部分に示すようなグラフの変更をもたらす。
【００５３】
この右部分には、シンボルノードが削除され、各シンボルが２つのサブシンボルに細分化されると仮定すると、４個のサブシンボルノードＮＳ１〜ＮＳ４が実際には獲得される。シンボルノードＡ１はサブシンボルノードＮＳＳ１およびＮＳＳ２に細分化され、シンボルノードＡ２はサブシンボルノードＮＳＳ３およびＮＳＳ４に細分化される。中間ノードに関しては、それぞれ、１つの検査ノードにリンクされている。他方、シンボルＡ１は検査ノードＮＣ１およびＮＣ２にリンクされており、検査ノードＮＣ１およびＮＣ２にそれぞれ接続される２つの中間ノードＮＩＴ１およびＮＩＴ２をシンボルＡ１と関連付ける必要がある。
【００５４】
同様に、シンボルＡ２は２つの検査ノードＮＣ１およびＮＣ３に接続されており、各中間ノードはただ１つの検査ノードだけに接続され得るため、検査ノードＮＣ１およびＮＣ３にそれぞれ接続される２つの中間ノードＮＩＴ３およびＮＩＴ４をシンボルノードＡ２と関連付ける必要がある。他方、各シンボルノードの接続性は、図４の右部分に示すように、サブシンボルノードのレベルにおいて図示されている。
【００５５】
グラフで表すことのできる符号特性は、行列形式でも表すことができる。これに関しては、図５に示すように、符号化装置ＤＥＮＣは、例えば、行列Ｈを形成することのできる処理手段ＮＴＣを備え、この行列Ｈに基づいて符号化シンボルの各列Ｊ２を決定することが可能になるものと想定する。
【００５６】
ｑ＝２ｐのＧＦ（ｑ）上で定義された非２進ＬＤＰＣ符号について、パリティ検査式の各非ゼロ係数は、ｐ行およびｐ列のビットブロックとして表現することができ、よって、この係数の２値行列像を形成することが知られている。これについては、C. Poulliat, M. Fossorier and D. Declercq, 「Design of non binary LDPC codes using their binary image: algebraic properties」, in the proc. of ISIT  '06, Seattle, USA, July 2006（非特許文献１）という論文に記載されている。また、Ｈｋ（図６）と呼ばれるｐ×ｐビットの各行列ブロックは１つのシンボルと関連付けられる。
【００５７】
各シンボルをサブシンボルに細分化することは、図６に示すように、結果的に、ブロックＨｋをｊ個のサブブロックに細分化することになる（この場合、各シンボルは２つのサブシンボルに細分化されると仮定されるため、ｊは２に等しい）。各サブビットブロックはｐ行と、サブシンボルのサイズに等しい数ｐｉ（ｉ＝１，…ｊ）の列とを含む。この場合、すべてのシンボルが２つのサブシンボルに細分化されると仮定されているため、各サブブロック列数ｐｉは同一である。
【００５８】
他方、符号化シンボルと関連付けられたブロックを形成するサブブロックの様々な場所の位置は、符号化シンボルと関連付けられた細分化方式の部分を表す。図６の例では、ブロックＨｋは２つのサブブロックＨｋ１およびＨｋ２に細分化されている。
【００５９】
よって、図７に示すように、「第１の行列」とも呼ばれるこの行列Ｈは、Ｍ個のパリティ検査式（Ｍは（Ｎ−Ｋ）に等しい）とそれぞれ関連付けられたｐ行のＭ個の群と、Ｎ個の符号化シンボルとそれぞれ関連付けられたｐ列のＮ個の群とを含む。ｐ行の各群は、考察されるｐ行の群と関連付けられたパリティ検査式の非ゼロ係数の２値行列像を形成するｐ行およびｐ列のビットブロックを含む。
【００６０】
また、これらのブロックはそれぞれ、前述のようにｊ個のサブブロックに細分化され、数ｊの値、ならびにサブブロックの列の数の値Ｐｉ（ｉ＝１からｊ）、および符号化シンボルと関連付けられたブロックを形成するサブブロックの様々な場所の位置は、この符号化シンボルと関連付けられた細分化方式の部分を表す。よって、ＧＦ（ｑ）の従来の非２進ＬＤＰＣ符号における位数ｄｃ−１のパリティ検査式は次式によって定義される。
【数１】
2010539744.tif 000003
式中、ＡｋはＧＦ（ｑ）におけるシンボルを表し、ｈｋは（やはりＧＦ（ｑ）における）パリティ検査式の非ゼロ係数を表し、このパリティ検査式は、行列形式の細分化符号構造の場合には、次式で書き換えることができ、
【数２】
2010539744.tif 000004
式中、ＳＳｋｉはサブシンボルを表し、ｎｓは、シンボルを形成する（この場合は一定で同一であるものと仮定される）サブシンボルの数を表す。
【００６１】
実際には、各シンボルがどんなやり方でサブシンボルに細分化されるとしても、すなわち、ｐ行の様々な群内の様々なサブブロックの場所がどのようなものであれ、記憶される必要のあるサブシンボルのサイズが低減されることになるため、位数がｑ未満のガロア体上で符号化されたシンボルを獲得することを可能にし、復号時に復号に必要なメモリサイズを低減することを可能にする細分化型の符号構造が常に獲得される。
【００６２】
とはいえ、以下でより詳細に示すように、行列Ｈ内のサブブロックの適切な場所をもたらす適切な細分化方式は、特に誤り訂正の点で、符号化および復号の性能を改善することを可能にする。行列Ｈに基づき、処理手段ＭＴＣは、符号化シンボルの形成を可能にする、生成行列と呼ばれる行列Ｇを獲得するように、例えば、当業者に周知の対角化処理８０（図８）などを行うことができる。
【００６３】
具体的には、図８に示すように、符号化手段ＭＥＮＣは、Ｋ個の初期シンボルの列を生成行列Ｇと乗算する（ステップ８１）ことにより、Ｎ個の符号化シンボルを形成する。
【００６４】
別の解決法は、図９に示すように、行列Ｈの三角化処理（ステップ９０）を行って行列Ｇ１を獲得し、次いで、それ自体は公知の従来方式で、行列Ｇ１およびＫ個の初期シンボルの列を使用して冗長サブシンボルの再帰的計算（ステップ９１）を行って、Ｎ個の符号化シンボルを獲得するものである。
【００６５】
符号特性を表す別のやり方は、図１１に示す個別例のような、いわゆる初期行列ＭＩＮを形成するものである。このような初期行列ＭＩＮは、後述するように、パリティ検査式を表す第１の部分と、細分化方式をそれぞれ表す様々な群分け指示を含む第２の部分とを含む。図１１に示す行列ＭＩＮの構造をより正確に説明するために、図１０に示す型の細分化構造符号グラフがあるものと仮定する。
【００６６】
図１０には、ｄｃに等しい検査ノードの接続度、およびｄｖに等しいサブシンボルノードＮＳＳｊの接続度があることが示されている。各符号化シンボルはｎｓ個の等しいシンボルまたはサブシンボルに細分化されているものと仮定する。加えて、この例では、ｄｖはｎｓに等しく（これら２つの値は２であり）、ｄｃは４に等しいとみなす。
【００６７】
初期行列ＭＩＮの第１の部分Ｅ１は、２ｐ次のガロア体に属するその各要素が様々なパリティ検査式の係数を表す、Ｍ＝（Ｎ−Ｋ）行を含む。言い換えると、行列ＭＩＮの第１の部分Ｅ１は、検査ノードのプロファイルに対応する。行列ＭＩＮの第２の部分Ｅ２は、サブシンボルの数、この場合はＮ×ｎｓに等しい数の行を含む。各行は１つのサブシンボルと関連付けられており、行列ＭＩＮの第２の部分Ｅ２の各要素は様々な群分け指示を形成する。加えて、行列ＭＩＮは、中間ノードの数、この場合はＮｄｖに等しい数の列も有する。
【００６８】
前述のように、行列ＭＩＮの第２の部分Ｅ２の要素は、サブシンボルからシンボルを形成することを可能にする様々な群分け指示を形成する。これに関して、例えば、行列ＭＩＮの第２の部分Ｅ２のある行とある列との交点のところなどの１の論理値は、対応するサブシンボルが対応する中間ノードにリンクされていることを意味する。
【００６９】
中間ノードの検査ノードへの接続は、その行列ＭＩＮの第１の部分Ｅ１によって定義される部分についてのものである。加えて、図１１において、ＤＥ１はサイズＭ×Ｍの対角行列を表す。ＩＥ２はサイズＮ×Ｎの単位行列を表す。ｐｉは円順列を表す。したがって、行列Ｅ１および行列Ｅ２は、円順列に基づく構造を使用して構築されることが示されている。言い換えると、ｉ＝１から４の場合のＰ（ＩＥ２）は、行列ＩＥ２の円順列から生じる行列である。
【００７０】
この場合、この行列ＭＩＮは、従来の意味でのパリティ行列ではなく、細分化符号構造を完全に記述することを可能にするものであることに留意すべきである。このような初期行列の構造の利点は、１つはその構造の簡潔性に存し、また、良好な特性のグラフ半径を獲得することにも存する。この場合、グラフ半径は、任意のシンボルから開始してこの同じシンボルまで戻るグラフ内の最小経路であることを想起する。また、初期行列ＭＩＮの第２の部分Ｅ２の非ゼロ要素を適切なやり方（図１２）で配置しようとすることにより、その最小値が所定の閾値より大きい周期を獲得することが可能になる。
【００７１】
例えば、図１２に示すように、行列Ｅ１の第２列第２行に位置する中間ノードから開始して、この同じノードで終了する周期ＣＹＣは、８区間ＴＲ１〜ＴＲ８として行われる。当業者は、グラフ半径の望ましい閾値を、想定される用途と、復号のために望ましい性能との関数としてどのように決定すべきかを理解する。とはいえ、６以上の閾値が許容される値である。
【００７２】
この場合、前述の細分化符号構造は、非２進ＬＤＰＣ符号になぞらえることのできない全く新しい系統の符号であることに留意すべきである。具体的には、この符号構造は、ＧＦ（ｑ）上で線形符号化関数を定義するものではない。言い換えると、その要素をＧＦ（ｑ）に取り込み、符号を定義するいかなるパリティ行列Ｈも生成行列Ｇも存在しない。しかし、細分化されたシンボルを有する符号は、前述のような２値パリティ行列像を有する、ＧＦ（２）上の通常の意味でのパリティ符号のままである。
【００７３】
次に図１に戻り、さらに図１３〜図１５を参照して、細分化型の符号構造を用いて符号化されたブロックの復号の実現形態を示す。この場合も、簡潔にするために、ｑは２ｐに等しく、したがって、各符号化シンボルはｐビットのベクトルの形で表すことができ、各シンボルはｎｓ個のサブシンボルに細分化されるものと仮定する。
【００７４】
図１を参照すると、復調手段ＤＭＤＭの出力のところで、したがって、伝送路上を送られたＮ個の符号化シンボルに対応するＮ個の情報項目の列が獲得される。現実の伝送条件が与えられたとすると、各情報項目は、実際には、当業者が一般にＬＬＲ：「対数尤度比（Ｌｏｇ  Ｌｉｋｅｌｉｈｏｏｄ  Ｒａｔｉｏ）」と呼ぶ確率値であるｐデータのベクトルである。実際には、データの符号（ｓｉｇｎ）は関連付けられたビットの論理値を指示し、データの絶対値は上記論理値の信頼度を指示する。
【００７５】
よって、復調手段ＤＭＤＭの出力は、Ｎ個の符号化シンボルを表すＬＬＲのＮ個のベクトルを渡す。とはいえ、簡潔にするために、以下本明細書では大ざっぱに、ＬＬＲのＮ個のベクトルを「Ｎ個の符号化シンボル」という表現で示す。当然ながら、これらＮ個の符号化シンボルは、実際には、復号手段によって復号されることになるＮＩ個のサブシンボルに細分化されている。
【００７６】
一般には、図１３に示すように、Ｎ個の細分化された符号化シンボルの列の受け取り（ステップ１３０）の後に復号１３１が行われる。この復号は、最初に、通信路から受け取られた情報（ＬＬＲ）の値（図１４、この図ではｎｓ＝４）を用いたサブシンボルノードの初期設定を含む。これに関して、復号器は、通信路から受け取ったｐ／ｎｓビットを、ガロア体ＧＦ（２ｐ／ｎｓ）上で定義された１つのシンボル（実際にはサブシンボル）と解釈する。
【００７７】
復号は、これら様々なノード間でのメッセージの反復的交換を含み、これらのメッセージはＬＬＲのベクトルである。サブシンボルノードＮＳＳは更新される（ステップ１３１０、図１３）。これに関しては、この更新が位数２ｐ／ｎｓのガロア体において行われるため、記憶される必要のあるメッセージのサイズが低減される。また、復号は、位数ｑのガロア体において行われる検査ノードの更新（ステップ１３１２）、ならびに検査ノードの更新の前と後に分散された中間ノードの処理（ステップ１３１１およびステップ１３１３）も含む。
【００７８】
実際には、以下でより詳細に示すように、中間ノードの第１の副処理は、確率の再結合からなり、第２の副処理は周辺化処理からなる。この複合は、図１３に矢印１３１４で示すように反復される。ある回数の反復および／または復号停止基準の満足の後、ＬＬＲのＫ個のベクトルが獲得され、その符号は、Ｋ個の復号シンボルに対応するｐビットのＫ個の集合の論理値を提供する。この復号を行うために、当業者にＢＰという名で周知の確率伝搬型のアルゴリズムを使用することが可能である。
【００７９】
この反復復号を行う解決法は、まず、すべてのサブシンボルノードを更新し、次いで、すべての中間ノードの第１の副処理を行い、次いで、すべての検査ノードの更新を行い、最後に、すべての中間ノードの周辺化処理を行うものとすることができる。
【００８０】
より有効な解決法は、ノードの順次更新を行うものであり、その実現方法の例を図１５に示す。図１５において、ｉｔは反復回数を表し、ｉは検査ノードＮＣのインデックスを表す。現在ノードＮＣｉ（ステップ１３１５）について、ノードＮＣｉの近隣ノード、すなわち、この検査ノードにリンクされているサブシンボルノードＮＳＳｊおよびＮＩＴｋが決定される。この場合、この近隣ノードの決定は、シンボル細分化方式を表す指示に基づいて獲得されるが、すでに述べたように、そのような指示自体は、絶対に不可欠なものではなく、復号を容易にするものにすぎない。この場合、この指示は、例えば、メモリＭＭ２に含まれる初期行列ＭＩＮなどから生じるものである。
【００８１】
この検査ノードＮＣｉに接続されたサブシンボルノードＮＳＳｊを決定した後で、これらのサブシンボルノードの更新（ステップ１３１６）が行われる。この更新は、前述のように、位数２ｐ／ｎｓのガロア体において行われる。
【００８２】
ガロア体においてそのようなノードを更新する式は当業者に公知であり、例えば、David Declercq and Marc Fossorier entitled 「Decoding Algorithms for Nonbinary LDPC Codes over GF (q)」, IEEE Trans. On Commun., vol 55(4), pp. 633-643, April 2007（非特許文献２）という論文などに記載されている。この場合、更新は、特に加法演算によって、このサブシンボルが間接的にリンクされている検査ノードから発するものを除いて、最終的に考察されるサブシンボルノードになるメッセージを考慮に入れるというものであることを想起する。
【００８３】
その後、これらの更新されたサブシンボルノードに接続された中間ノードＮＩＴｋの第１の副処理１３１７が行われる。この第１の副処理は、確率を組み合わせる処理である。よって、中間ノードＮＩＴの値がαｉに等しい確率は、サブシンボルノードの値βに基づき、次式により、ベイズの条件付き確率規則を使用して獲得される。
Ｐ（ＮＩＴ＝αｉ）＝Ｐ（ＳＳ０＝β０，…，ＳＳｘ−１＝βｘ−１）
Ｐ（ＳＳ０＝β０｜ＳＳ１＝β１，…，ＳＳＸ−１＝βｘ−１）Ｐ（ＳＳ１＝β１｜ＳＳ２＝β２，…，ＳＳｘ−１＝βｘ−１）…Ｐ（ＳＳｘ−１＝βｘ−１）
この式を簡潔にするために、サブシンボル間の独立の仮定を使用して、次式で定義されるより簡単な式を獲得することが可能である。
Ｐ(ＮＩＴ＝αｉ)＝Ｐ(ＳＳ０＝β０)Ｐ(ＳＳ１＝β１)…Ｐ(ＳＳｘ−１＝βｘ−１)
【００８４】
その後、検査ノードＮＣｉの更新が行われる（ステップ１３１８）。この更新は、位数ｑのガロア体において行われ、それ自体は通常の、当業者に周知の更新である。また、これについては前述の非特許文献２にも記載されている。最後に、中間ノードＮＩＴｋの第２の副処理１３１９が行われ、これは、例えば以下の式による周辺化処理である。
【数３】
2010539744.tif 000005
式中ではサブシンボルの相互独立が仮定されている。
【００８５】
次いで、次の検査ノードに進み、前述の操作が繰り返される。ｉがＭになると、すなわち、すべての検査ノードの処理が完了すると、反復カウンタが増分され（ステップ１３２３）、前述の各ステップが繰り返される。反復回数が事前に定義された最大反復回数ＩＴｍａｘになると（ステップ１３２２）、復号アルゴリズムは打ち切られる。当然ながら、この停止基準は一例にすぎず、他の任意の従来の停止基準も当てはまる。
【００８６】
図１６および図１７には、本発明のいくつかの利点を示す曲線が図示されている。準巡回構造に基づき、細分化型の符号の構造が、以下のパラメータを用いて定式化されている。
符号化率Ｒ＝０．５
ｄｖ＝２
ｄｃ＝４
【００８７】
検査ノードは、位数ｑ＝６４（２６）のガロア体上で定義され、すべてのシンボルはビットサイズ３の２つのサブシンボル（ｎｓ＝２）に細分化される。図１６において、初期シンボル列の総ビット数はＮｂ＝８６４である。最大１０００反復が決定されており、復号器は、当業者に周知の、従来の「シンドローム（ｓｙｎｄｒｏｍｅ）」型の基準を使用して停止されている。（ｄＢ）
【００８８】
図１７では、同じパラメータが使用されているが、Ｎｂ＝３０００ビットである。図１６および図１７において、縦軸はフレーム誤り率を表し、横軸はＥｂ／Ｎ０（ｄＢ）を表し、Ｅｂは通信路上での１ビット伝送の平均エネルギーを表し、Ｎ０は通信路の雑音エネルギーである。曲線ＣＶ１はＧＦ（６４）上の従来のＬＤＰＣ符号の性能を表し、曲線ＣＶ２は細分化構造を有する符号での性能を示す。したがって、細分化構造を有する符号がずっと低いエラーフロア（フレーム誤り率）を示すことがわかる。
【図１】
2010539744.tif 000006
【図２】
2010539744.tif 000007
【図３】
2010539744.tif 000008
【図４】
2010539744.tif 000009
【図５】
2010539744.tif 000010
【図６】
2010539744.tif 000011
【図７】
2010539744.tif 000012
【図８】
2010539744.tif 000013
【図９】
2010539744.tif 000014
【図１０】
2010539744.tif 000015
【図１１】
2010539744.tif 000016
【図１２】
2010539744.tif 000017
【図１３】
2010539744.tif 000018
【図１４】
2010539744.tif 000019
【図１５】
2010539744.tif 000020
【図１６】
2010539744.tif 000021
【図１７】
2010539744.tif 000022
【国際調査報告】
2010539744.tif 000023
2010539744.tif 000024