(57)【要約】  本発明は、N個の変数およびM個の制約を示す2部グラフによって表現することができる非バイナリ符号、特に非バイナリLDPC符号を復号するための方法に関し、変数は、非線形アルファベットAにおいてその値を取り、Aにおける係数行列(H)を使用して線形に制約され、それぞれの変数は、受け取られたまたは読み取られた情報に対応し、バイナリ値のpタプルの形で表される。それぞれの変数について、2013507807.tif 000113個の拡張バイナリ値が、前記変数のバイナリ値の2013507807.tif 000114個の線形結合によって生成される(620)。前記拡張バイナリ値は、拡張パリティチェックと呼ばれるパリティチェックに従う。変数の拡張バイナリ値から拡張パリティチェックへの転換を可能にするパリティ行列(630)は、メッセージパッシング反復復号(650)が実行される拡張2部グラフ(640)を定義する。
2013507807.tif 000002
【特許請求の範囲】
【請求項１】
N個の変数頂点およびM個の制約頂点を有する2部グラフによって表現することができる非バイナリ符号、特に非バイナリLDPC符号のための復号方法であって、変数がその値を非バイナリアルファベットAから引き出し、制約行列(H)によって線形に制約され、それぞれの変数が複数pのバイナリ値によって表され、
それぞれの変数について、拡張バイナリ値と呼ばれる複数
【数１】
2013507807.tif 000105
のバイナリ値が生成され(620)、ゼロ結合を除く、F2からの係数を用いる、前記p個のバイナリ値の
【数２】
2013507807.tif 000106
個の線形結合によって得られ、
拡張パリティチェックと呼ばれる、前記変数の前記拡張バイナリ値上でのパリティチェックを表す、拡張パリティ行列と呼ばれるパリティ行列が計算され(630)、前記拡張パリティチェックが前記変数に対する制約によって誘導され、
前記拡張パリティ行列を表し、前記拡張パリティチェックを前記変数の前記拡張バイナリ値に結び付ける、拡張グラフと呼ばれる第2の2部グラフ(700、800)を使用して、反復メッセージパッシング復号プロセス(650)が実行され、
それぞれの変数の前記バイナリ値が、前記反復復号プロセスの終わりに得られる、その拡張バイナリ値から決定される(660)、方法。
【請求項２】
アルファベットAがq=2p個の元および
【数３】
2013507807.tif 000107
で構成される、請求項1に記載の復号方法。
【請求項３】
前記パリティ行列
【数４】
2013507807.tif 000108
が、さらなる行を追加することによって完成され(630)、前記さらなる行が、前記ゼロ結合を除く、F2からの係数を用いる、既存の行の異なる線形結合によって得られ、こうして完成された前記行列のそれぞれの行が、拡張パリティチェックを定義し、次いで、前記拡張グラフが、前記変数の拡張バイナリ値の集合をこうして完成された行列
【数５】
2013507807.tif 000109
の拡張パリティチェックの集合に結び付ける、請求項1または2に記載の復号方法。
【請求項４】
追加されたさらなる行の数がq-p-1である、請求項2および3に記載の復号方法。
【請求項５】
それぞれの変数の前記拡張バイナリ値の少なくとも一部が、それ独自のバイナリ値を使用して初期化される、請求項1から4の一項に記載の復号方法。
【請求項６】
前記反復復号プロセスの少なくとも1回の反復に対して、それぞれの変数の前記拡張バイナリ値が最尤復号を受けて、前記
【数６】
2013507807.tif 000110
個の線形結合によって誘導された制約の集合を確認する推定された拡張バイナリ値を得て、前記拡張バイナリ値が、それぞれの変数について、前記反復復号プロセスを継続する目的で前記推定された拡張バイナリ値によって置き換えられる、請求項1から5の一項に記載の復号方法。
【請求項７】
前記反復復号プロセスの少なくとも1回の反復に対して、それぞれの変数の前記拡張バイナリ値によって通過したメッセージが最尤方向で訂正されて、前記
【数７】
2013507807.tif 000111
個の線形結合によって誘導された制約の集合を確認し、前記通過したメッセージが、それぞれの変数について、前記反復復号プロセスを継続する目的で前記訂正されたメッセージと置き換えられる、請求項1から5の一項に記載の復号方法。
【請求項８】
前記反復復号プロセスの少なくとも1回の反復プロセスに対して、それぞれの変数の前記拡張バイナリ値によって受信されたメッセージが最尤方向で訂正されて、前記
【数８】
2013507807.tif 000112
個の線形結合によって誘導された制約の集合を確認し、前記受信されたメッセージが、それぞれの変数について、前記反復復号プロセスを継続する目的で前記訂正されたメッセージによって置き換えられる、請求項1から5の一項に記載の復号方法。
【請求項９】
前記バイナリ値を前記変数の前記拡張バイナリ値に結び付ける補助グラフ(815)をさらに使用する方法であって、前記補助グラフが、前記線形結合を前記補助グラフから生成することを可能にする前記線形結合を表す、請求項1から8に記載の復号方法。
【請求項１０】
反復復号ステップが、前記補助グラフ(815)によって、前記バイナリ値と前記変数の前記拡張バイナリ値との間のメッセージパッシングの第1の段階、および前記拡張グラフ(800)によって、前記変数の前記バイナリ値と前記拡張パリティチェックとの間のメッセージパッシングの第2の段階を、少なくとも1つ含む、請求項9に記載の復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電気通信またはデータ記録の分野における誤り訂正符号の復号に関する。より具体的には、本発明は、非バイナリ符号、特に非バイナリLDPC(Low-Density  Parity  Check:低密度パリティチェック)符号のためのメッセージパッシング復号方法に関する。
【背景技術】
【０００２】
LDPC符号は、R.Gallagerによって、IEEE  Trans.Inform.Theory、Vol.IT-8、21〜28頁、1962年において発表された「Low  density  parity  check  codes」と題された論文において紹介され、その興味深い特性はつい最近、反復復号の力がターボ符号において強調されたときに再発見された。ターボ符号の反復復号についての説明は、IEEE  Trans.Inform.Theory、Vol.44、No.10、1261〜1271頁、1996年において発表された「Near  optimum  error  correcting  coding  and  decoding:  turbo-codes」と題されたC.Berrouらによる影響力の大きい論文に見出される。
【０００３】
ターボ符号と同様に、LDPC符号は2部グラフによって表現することができる。
【０００４】
2部グラフという用語は、同じ部分集合の2つの頂点がグラフの辺によって結ばれないような、頂点集合が2つの独立した部分集合からなる無向グラフを指す。
【０００５】
一般的に、特定の誤り訂正符号は2部グラフによって表現することができる。このグラフは、変数頂点と呼ばれる、符号語を構成するシンボルに関連付けられた頂点の第1の部分集合と、チェック頂点と呼ばれる、符号制約に関連付けられた頂点の第2の部分集合とに分割される。制約の群に関連付けられた2部グラフは、タナー(Tanner)グラフとも呼ばれる。符号語のシンボルがバイナリであるとき、符号制約はパリティチェックと呼ばれる。したがって、以下では、分かりやすくするために、バイナリ符号が関与するときは、パリティチェックという特定の用語を使用し、非バイナリ符号が関与するときは、制約という一般的な用語を使用する。
【０００６】
一般的に、符号語におけるシンボルはガロア体F2={0,1}の元、別名ビットであるが、より一般的には、これらのシンボルはサイズq≧2のアルファベットの元、例えば任意の標数2を有する体
【０００７】
【数１】
2013507807.tif 000003
【０００８】
すなわち、2p進アルファベット(したがってq=2p)とすることができる。
【０００９】
2部グラフによって表現することができる符号を、MP(Message  Passing(メッセージパッシング)の略)またはBP(Belief  Propagation(確率伝搬法)の略)とも呼ばれる反復メッセージパッシング復号を使用して復号することができる。この復号方法についての包括的な説明は、1996年の「Codes  and  decoding  on  general  graphs」と題されたN.  Wibergの論文に見出すことができる。実際、MP型の反復復号は、復号の分野でよく知られているアルゴリズム、すなわち、ターボ符号に使用される「フォワード-バックワード(forward-backward)」アルゴリズムおよびLDPC符号に使用されるギャラガー(Gallager)アルゴリズムの一般化である。
【００１０】
非バイナリ符号のメッセージパッシング復号は、バイナリ符号のメッセージパッシング復号とは異なる。
【００１１】
実際、バイナリLDPC符号などのバイナリ符号の場合、それぞれの変数頂点は符号化されたビットを表す。ビットの値に関する不確実性があるとき、この不確実性は値0または1の確率に換算して、または大抵の場合は、これらの確率の比の対数として定義される、LLR(Log  Likelihood  Ratio(対数尤度比))と呼ばれる対数尤度比として表される。次いで、場合によっては、2部グラフの頂点間で交換されるメッセージが確率またはLLRに換算してタグ付けされる。
【００１２】
非バイナリ符号の場合、それぞれの変数頂点は符号化されたシンボルを表し、符号化されたシンボルは符号アルファベットの元である。シンボルの値に関する不確実性があるとき、この不確実性をq-1個の確率のベクトルによって表すことができ、ここで、qはアルファベットのサイズ(q個の確率の合計は1に等しいので、q-1個の確率は十分である)、またはq-1個のLLR値である。場合によっては、2部グラフの頂点間で通過するメッセージもq-1個の確率値またはq-1個のLLR値のベクトルの形で表される。
【００１３】
図1は、非バイナリ符号、より詳細には、そのパリティ行列としてサイズM×N(ここで、N=6は変数の数であり、M=3は制約の数である)の行列を有するF8上で定義されるLDPC符号の2部グラフの例を示す。
【００１４】
【数２】
2013507807.tif 000004
【００１５】
行列の係数はF8の元であることに留意されたい。変数頂点X1,...,XNはグラフの左側の部分に示され、制約頂点Y1,...,YMは右側の部分に示されている。この場合、
Y1:  X1+3X2+4X3+6X4=0
Y2:  X2+7X4+X5+5X6=0  (2)
Y3:  5X1+X3+2X5+4X6=0
である。変数X1,...,X6のメッセージおよび制約Y1,...,Y3のメッセージをそれぞれ、サイズ7の確率のベクトルとして表すことができる。
【００１６】
このグラフの接続行列は符号のパリティ行列に対応し、言い換えれば、グラフの辺に割り当てられた重みは行列Hの係数を表す。慣例により、重みがゼロであるとき、これに対応する辺はグラフから割愛される。
【００１７】
非バイナリLDPC符号はバイナリLDPC符号よりも良い訂正確率を提供するが、一方で非バイナリLDPC符号は復号がより難しい。実際、復号アルゴリズムの複雑性は一般的にq2、すなわちアルファベットのサイズの2乗に比例する。非バイナリLDPC符号を復号するための1つの方法は、例えば、IEEE  Int.Symp.  on  Information  Theory  (ISIT)、トロント、カナダ、2008年に発表された「Min-Max  decoding  for  non  binary  LDPC  codes」と題されたV.Savinによる論文に記載された。
【００１８】
当業者であれば、非バイナリ符号を復号する自然な方法はパリティ行列の等価なバイナリ表現を使用することであると考えるであろう。しかし、理解されるように、この「自然な」バイナリ表現は、低い復号性能および高い誤り率をもたらす。
【００１９】
LDPC符号は、バイナリおよび非バイナリともに、パリティ行列において低密度の非ゼロ係数を示す特性を有することが知られている。この特性は、2部グラフにおいて少数の短いサイクルをもたらす。これらのサイクルは、反復復号プロセスにおける変数およびチェックの自己確認を引き起こす傾向がある。これは、近傍の頂点によって1つの頂点に送信されたメッセージはそれ自体で、この頂点が近傍の頂点に送信するメッセージに依存するという単純な事実により、頂点の誤った値を確認することができることを意味する。この自己確認現象に対処するためには、復号プロセスはいわゆる外部情報の原則(extrinsic  information  principle)に準拠しなければならない。すなわち、送信側頂点によって受信側頂点に送信されたメッセージは、受信側頂点から来るメッセージを除く、送信側頂点によって受信された全てのメッセージから計算される。しかし、外部情報の原則への準拠は、2部グラフに存在するサイクルのため、高次での自己確認を除外せず、これらの自己確認はサイクルが短いほど頻度が高くなる。
【００２０】
外部情報の原則が図2に概略的に示されている。ここで示されているのは、Y1,Y2,Y3がチェック頂点であり、X1,...,X4が変数頂点である2部グラフの一部である。変数頂点X1に向けられた制約頂点Y1のメッセージは、X1から受信されたメッセージを考慮せずに、Y1によって受信された変数頂点X2,X3,X4からのメッセージから計算される。逆に、チェック頂点Y1に向けられたチェック頂点X1からのメッセージは、Y1から受信されたメッセージを考慮せずに、X1によって受信されたチェック頂点Y2およびY3からのメッセージから計算される。
【００２１】
図3は、2部グラフにサイクルが存在することによる自己確認現象を示す。前述したように、グラフの一部が示されており、変数頂点は丸として、チェック頂点は四角として示されている。グラフ内のサイクルは太線で示されている。このサイクルに従うと、変数頂点X5によって受信されたメッセージm6は、連続するメッセージm2からm5を介して、以前のいくつかの復号反復と同じ頂点によって送信されたメッセージm1に間接的に依存することが分かる。
【００２２】
以下では、q個の元を有するアルファベットAを考える。Aの元を「シンボル」と呼ぶものとする。一般性を失うことなく簡略化するために、q=2pは2の累乗であると仮定する。次いで、
【００２３】
【数３】
2013507807.tif 000005
【００２４】
上にAの全単射
【００２５】
【数４】
2013507807.tif 000006
【００２６】
が存在し、ここで、F2={0,1}は2元体である。バイナリベクトル
【００２７】
【数５】
2013507807.tif 000007
【００２８】
はシンボルの「バイナリ像」と呼ばれ、ω(X)=xであれば、X∈Aである。
【００２９】
全単射ωはAにベクトルF2空間構造をもたらす。AのF2自己準同形（endomorphisms）、すなわち、そのベクトルF2空間構造を備えたAの自己準同形の代数を
【００３０】
【数６】
2013507807.tif 000008
【００３１】
と表す。Aのシンボル上でのLの元の評価は、Aの上でのLのアクションを定義し、これは乗法的に表される。
【００３２】
【数７】
2013507807.tif 000009
【００３３】
H∈MM,N(L)である、すなわち、Hを、その元がLに由来するサイズM×Nの行列とする。
【００３４】
非バイナリ符号C⊂ANは
【００３５】
【数８】
2013507807.tif 000010
【００３６】
によって定義され、Hは符号Cの制約行列と呼ばれる。全単射ωを使用して、それぞれのシンボルXnをそのバイナリ像に置き換えることによって、シンボル(X1,...,XN)∈ANのそれぞれのシーケンスをバイナリシーケンス
【００３７】
【数９】
2013507807.tif 000011
【００３８】
と一致させることができる。(長さNpの)このバイナリシーケンスをシーケンス(X1,...,XN)∈ANの「バイナリ像」と呼ぶものとする。全ての符号語(X1,...,XN)∈C⊂ANのバイナリ像は、「Cのバイナリ像」と呼ばれるバイナリ符号
【００３９】
【数１０】
2013507807.tif 000012
【００４０】
を形成する。
【００４１】
Aと
【００４２】
【数１１】
2013507807.tif 000013
【００４３】
との間の同形ωは、
【００４４】
【数１２】
2013507807.tif 000014
【００４５】
と
【００４６】
【数１３】
2013507807.tif 000015
【００４７】
との間の同形を誘導する。
【００４８】
【数１４】
2013507807.tif 000016
【００４９】
したがって、上記の恒等式(6)によって行列Hのそれぞれの元hm,nをその像で置き換えることによって、バイナリ行列Hbin∈MMp,Np(F2)が得られる。この行列は、バイナリ符号Cbinのパリティ行列である。
【００５０】
Fq上、すなわちq個の元を有する有限体上で定義される非バイナリ符号は、非バイナリ符号における特殊な場合を表すことに留意されたい。そのような符号のアルファベットはA=Fqであり、そのベクトルF2空間構造はFq上での内部加算によって誘導される。さらに、Fq上での乗算の演算は、
【００５１】
【数１５】
2013507807.tif 000017
【００５２】
(すなわち、Fq⊂L)のベクトル部分空間としてのFqの埋込みを定義する。符号Cが行列H∈MM,N(Fq)⊂MM,N(L)の核として定義される場合、「符号CはFq上で定義される」という。この場合、行列Hの全ての元はFqに属し、hm,n∈Fqであり、(5)内の乗算hm,nXnは単に体Fq内の内部乗算である。
【００５３】
例示するために、単純な非バイナリ符号のバイナリ表現の例を挙げる。
【００５４】
8個の元を有する、したがってF8と同形のアルファベットAを考える。慣習的に、F8という単純な表現を採用する。より詳細には、F8は、既約多項式P(D)=1+D+D3によって生成されるイデアルによるF2[D]の商環F2[D]/P(D)と同形である。F8内での加算および乗算は、P(D)を法として多項式の加算および乗算によって定義される。簡潔にするために、F8={0,1,...,7}であると仮定する。したがって、シンボルX∈F8={0,1,...,7}のバイナリ像は、多項式
【００５５】
【数１６】
2013507807.tif 000018
【００５６】
に対応するバイナリシーケンス(x0,x1,x2)である。一般的に、Xは多項式
【００５７】
【数１７】
2013507807.tif 000019
【００５８】
によって表され、その係数は、そのバイナリ像によって与えられる。2つのシンボルX,Y∈F8={0,1,...,7}の合計は、XおよびYのビット単位の合計に対応する。その積は、2つの多項式
【００５９】
【数１８】
2013507807.tif 000020
【００６０】
および
【００６１】
【数１９】
2013507807.tif 000021
【００６２】
の積のP(D)を法として、余りによって定義される。
【００６３】
F8に対する単一の線形制約によって定義される非バイナリ符号を考える。
3X+4Y+6Z=0  (7)
【００６４】
この場合、L=A=F8であることを想起されたい。
【００６５】
F8の元のバイナリ表現を使用することによって、より具体的には、3,4,6∈Lを表すために同形(6)を使用し、X,Y,Z∈Aを表すために同形(3)を使用することによって、上記の方程式は、
(1+D)(x0+x1D+x2D2)
+D2(y0+y1D+y2D2)   (8)
+(D2+D)(z0+z1D+z2D2)=0
となり、さらにD3=1+D[P(D)]、すなわち、
【００６６】
【数２０】
2013507807.tif 000022
【００６７】
であることを想起されたい。式(10)は行列形式
【００６８】
【数２１】
2013507807.tif 000023
【００６９】
で表すこともできる。制約行列H∈M1,3(F8)およびそのバイナリ像Hbin∈M3,9(F2)は、それぞれ方程式(7)および(10)から得られる。最終的には、
H=(3  4  6)  (11)
および
【００７０】
【数２２】
2013507807.tif 000024
【００７１】
を有する。
【００７２】
非バイナリ符号の制約行列Hおよびそのバイナリ像のパリティ行列Hbinにそれぞれ対応する2部グラフは、図4Aおよび図4Bにそれぞれ示されている。(長さ4の)多くの短いサイクルのバイナリグラフがあることが認められるが、非バイナリグラフは非循環である。
【００７３】
一般的に、非バイナリもしくは非循環である、または少数のサイクルを有する符号のバイナリ像は、選択されたバイナリ表現という理由だけで、多数のサイクルを含むことができる。当業者であれば、特定のバイナリ表現は代数の観点から等価とすることができるが、復号の点では変動する性能をもたらすことが理解されよう。
【先行技術文献】
【非特許文献】
【００７４】
【非特許文献１】R.Gallager、「Low  density  parity  check  codes」、IEEE  Trans.Inform.Theory、Vol.IT-8、21〜28頁、1962年
【非特許文献２】C.Berrouら、「Near  optimum  error  correcting  coding  and  decoding:  turbo-codes」、IEEE  Trans.  Inform.  Theory、Vol.  44、No.  10、1261〜1271頁、1996年
【非特許文献３】N.  Wiberg、「Codes  and  decoding  on  general  graphs」、1996年
【非特許文献４】V.  Savin、「Min-Max  decoding  for  non  binary  LDPC  codes」、IEEE  Int.  Symp.  on  Information  Theory  (ISIT)、トロント、カナダ、2008年
【非特許文献５】J.  Chenら、「Near  Optimum  universal  belief  propagation  based  decoding  of  low  density  parity  check  codes」、IEEE  Trans.  on  Comm.、50(3)、406〜414頁、2002年
【非特許文献６】V.  Savin、「Self-Corrected  Min-Sum  of  LDPC  codes」、IEEE  Int.  Symp.  on  Information  Theory  (ISIT)、トロント、カナダ、2008年
【発明の概要】
【発明が解決しようとする課題】
【００７５】
したがって、本発明が基づく課題は、2部グラフによって表現することができる非バイナリ符号、例えば非バイナリLDPC符号のための、上記の欠点がない復号方法、すなわち、低い復号複雑性および低い誤り率の両方を有する復号方法を提案することである。
【課題を解決するための手段】
【００７６】
本発明は、N個の変数頂点およびM個の制約頂点を有する2部グラフによって表現することができる非バイナリ符号、特に非バイナリLDPC符号のための復号方法によって定義され、変数はその値を非バイナリアルファベットAから引き出し、制約の行列によって線形に制約され、それぞれの変数は複数pのバイナリ値によって表される。この方法により、
-  それぞれの変数について、拡張バイナリ値と呼ばれる複数
【００７７】
【数２３】
2013507807.tif 000025
【００７８】
のバイナリ値が生成され、ゼロ結合を除く、F2における係数を使用する、前記p個のバイナリ値の
【００７９】
【数２４】
2013507807.tif 000026
【００８０】
個の異なる線形結合によって得られる
-  拡張パリティチェックと呼ばれる、変数の拡張バイナリ値上でのパリティチェックを表す、拡張パリティ行列と呼ばれるパリティ行列
【００８１】
【数２５】
2013507807.tif 000027
【００８２】
が計算され、前記拡張パリティチェックは前記変数に対する制約によって誘導される
-  拡張パリティ行列を表し、パリティチェックを変数の拡張バイナリ値に結び付ける、拡張グラフと呼ばれる第2の2部グラフを使用して、反復メッセージパッシング復号が実行される
-  それぞれの変数のバイナリ値が、反復復号の完了時に得られる、その拡張バイナリ値に基づいて決定される。
【００８３】
例えば、アルファベットAをq=2p個の元および
【００８４】
【数２６】
2013507807.tif 000028
【００８５】
で構成することができる。
【００８６】
前記拡張パリティ行列
【００８７】
【数２７】
2013507807.tif 000029
【００８８】
は有利には、さらなる行を追加することによって完成され、前記さらなる行は、ゼロ結合を除く、F2における係数を使用する、既存の行の異なる線形結合によって得られ、こうして完成された行列のそれぞれの行は、拡張パリティチェックを定義し、次いで、拡張グラフは、変数の拡張バイナリ値の集合をこうして完成された行列
【００８９】
【数２８】
2013507807.tif 000030
【００９０】
の拡張パリティチェックの集合に結び付ける。
【００９１】
例えば、追加された行の数はq-p-1である。
【００９２】
好ましくは、それぞれの変数の拡張バイナリ値の少なくとも一部は、それ独自のバイナリ値を使用して初期化される。
【００９３】
第1の変形形態によれば、反復復号の少なくとも1回の反復に対して、それぞれの変数の拡張バイナリ値は最尤復号を受けて、前記
【００９４】
【数２９】
2013507807.tif 000031
【００９５】
個の線形結合によって誘導された制約の集合を確認する推定された拡張バイナリ値を得る。それぞれの変数について、前記拡張バイナリ値は次いで、反復復号を継続する目的で前記推定された拡張バイナリ値によって置き換えられる。
【００９６】
第2の変形形態によれば、反復復号の少なくとも1回の反復に対して、それぞれの変数の拡張バイナリ値によって送信されたメッセージは最尤方向(maximum-likelihood  sense)で訂正されて、前記
【００９７】
【数３０】
2013507807.tif 000032
【００９８】
個の線形結合によって誘導された制約の集合を確認する。それぞれの変数について、前記送信されたメッセージは次いで、反復復号を継続する目的で前記訂正されたメッセージによって置き換えられる。
【００９９】
第3の変形形態によれば、反復復号の少なくとも1回の反復に対して、拡張バイナリ値によって受信されたメッセージは最尤方向で訂正されて、前記
【０１００】
【数３１】
2013507807.tif 000033
【０１０１】
個の線形結合によって誘導された制約の集合を確認する。それぞれの変数について、前記受信されたメッセージは次いで、反復復号を継続する目的で前記訂正されたメッセージによって置き換えられる。
【０１０２】
特定の実施形態によれば、バイナリ値を変数の拡張バイナリ値に結び付ける補助グラフも使用され、前記補助グラフは、線形結合を補助グラフから生成することを可能にする線形結合を表す。
【０１０３】
この場合、反復復号ステップは、前記補助グラフによって、バイナリ値と変数の拡張バイナリ値との間のメッセージパッシングの少なくとも1つの第1の段階を含み、前記拡張グラフによって、変数のバイナリ値と拡張パリティチェックとの間のメッセージパッシングの第2の段階を含むことができる。
【図面の簡単な説明】
【０１０４】
【図１】非バイナリLDPC符号の例の2部グラフを示す図である。
【図２】反復メッセージパッシング復号プロセスにおける外部情報の原則を概略的に示す図である。
【図３】2部グラフ内のサイクルの例を示す図である。
【図４Ａ】非バイナリ符号の2部グラフを示す図である。
【図４Ｂ】非バイナリ符号のバイナリ像に対応する2部グラフを示す図である。
【図５】バイナリ符号の例、そのバイナリ像、およびその拡張バイナリ像のそれぞれのパリティ行列を示す図である。
【図６】本発明の一実施形態による、拡張バイナリ表現を使用する非バイナリ符号のための復号方法を概略的に示す図である。
【図７】非バイナリ符号の拡張バイナリ表現に関連付けられ、図6の方法による復号を可能にする2部グラフの第1の例を表す図である。
【図８】非バイナリ符号の同じ拡張バイナリ表現に関連付けられ、図6の方法による復号も可能にする2部グラフの第2の例を表す図である。
【発明を実施するための形態】
【０１０５】
アルファベットA、サイズqの体の上で定義され、N個の変数およびM個の制約を有する2部グラフによって表現することができる非バイナリ誤り訂正符号を再び考える。以下では、一般性を失うことなく、この訂正符号は非バイナリLDPC符号であると仮定する。
【０１０６】
定義上、非バイナリ符号は、その値をAから引き出すN個の未知数(または変数)におけるM個の線形方程式(または制約)の集合によって定義される。やはり一般性を失うことなく、q=2pであると仮定される。次いで、ベクトル空間同形(3)により、それぞれの符号シンボルをp個のバイナリ値のベクトル、すなわち
【０１０７】
【数３２】
2013507807.tif 000034
【０１０８】
の元で識別することができる。バイナリ値のベクトルまたはpタプルは、非バイナリアルファベットのシンボルのバイナリ表現を与える。線形方程式内のLに属する係数を掛けたAからのシンボルの乗算を、規則(4)に従ってA上のF2自己準同形で識別することができる。Lのこの係数および、したがってA上のこのF2自己準同形を、F2からの係数を有する次元p×pの行列によって一般的に表すことができる。
【０１０９】
本発明が基づく主な考え方は、Aのシンボルの拡張バイナリ表現ならびにA上のF2自己準同形を使用することである。体Aの元の拡張バイナリ表現とは、pよりも確実に大きい(一般的に1og2(q)よりも大きい)
【０１１０】
【数３３】
2013507807.tif 000035
【０１１１】
個のビットを使用する、この元の冗長バイナリ表現を一般的に意味する。
【０１１２】
この拡張バイナリ表現の
【０１１３】
【数３４】
2013507807.tif 000036
【０１１４】
個のビットのそれぞれは、有利には、F2における係数を有するバイナリ表現のp個のバイナリ値の線形結合として表される。例えば、AからのシンボルXを
【０１１５】
【数３５】
2013507807.tif 000037
【０１１６】
を用いて、バイナリ表現においては(x0,x1,...,xp-1)によって、および拡張バイナリ表現においては(a1,a1,...,aq-1)によって表すことができ、ここで、
【０１１７】
【数３６】
2013507807.tif 000038
【０１１８】
はp個のビットのq-1個の考えられる結合(ゼロ結合を除くq個の結合)を表す。この場合、
【０１１９】
【数３７】
2013507807.tif 000039
【０１２０】
を有する。
【０１２１】
関係式(13)は、行列形式
(a1,a1,...,aq-1)=(x0,x1,...,xp-1)Sp  (14)
で表すこともでき、ここで、Spはサイズp×(q-1)の行列であり、その列はp個のビットのq-1個の考えられる結合である。言い換えれば、Spは符号(a1,a1,...,aq-1)の生成行列である。
【０１２２】
Aの任意の拡張バイナリ表現は、A上の自己準同形の拡張バイナリ表現を正準な方法で誘導する。実際に、次元
【０１２３】
【数３８】
2013507807.tif 000040
【０１２４】
のベクトルueを元X∈Aの拡張バイナリ表現とすると、
【０１２５】
【数３９】
2013507807.tif 000041
【０１２６】
は拡張バイナリ表現veも有するAの元である。したがって、自己準同形
【０１２７】
【数４０】
2013507807.tif 000042
【０１２８】
をサイズ
【０１２９】
【数４１】
2013507807.tif 000043
【０１３０】
のバイナリ行列によって表すことができる。
【０１３１】
次いで、M個の制約およびN個の変数を有する非バイナリ符号を次元
【０１３２】
【数４２】
2013507807.tif 000044
【０１３３】
の拡張バイナリ行列
【０１３４】
【数４３】
2013507807.tif 000045
【０１３５】
によって表すことができる。
【０１３６】
非バイナリ符号C⊂AN(ここで、Aはサイズq=2pの集合、したがって
【０１３７】
【数４４】
2013507807.tif 000046
【０１３８】
と同形である)の拡張バイナリ表現を考える。非バイナリ符号は、行列H∈MM,N(L)によって定義され、その元hm,n∈LはA上の自己準同形
【０１３９】
【数４５】
2013507807.tif 000047
【０１４０】
である。
【０１４１】
(15)にあるM個の方程式のそれぞれは、制約(すなわち、非バイナリ変数Xnにおける線形方程式)に対応する。行列Hは、非バイナリ符号Cの「パリティ行列」である。
【０１４２】
h∈Lとし、mh∈Mp(F2)を同形(6)の方向でのそのバイナリ像とする。
【０１４３】
具体的には、p=3であり、hがそれぞれの元Xについて元3Xとの対応を作成するA上の自己準同形である場合、式(11)および(12)に関連して上記で見たように、hのバイナリ像を
【０１４４】
【数４６】
2013507807.tif 000048
【０１４５】
と記述することができる。
【０１４６】
一般的な場合に戻って、qを法として整数の集合Zq={0,1,...,q-1}を考えると、行列mh∈Mp(F2)はZq上の自己準同形φh
【０１４７】
【数４７】
2013507807.tif 000049
【０１４８】
を誘導し、ここで、ηは整数z=b0+b121+b222+...+bp-12p-1をそれぞれのpタプル(b0,b1,..,bp-1)に関連付ける全単射である。逆に、η-1はZqにおけるそれぞれの整数にp個のビット上のそのバイナリ分解を関連付ける。
【０１４９】
【数４８】
2013507807.tif 000050
【０１５０】
上でのビット単位のXOR演算は、ZqにベクトルF2空間構造をもたらす。演算∧はZq上で
i∧j=η(η-1(i)XORη-1(j))  (18)
によって定義され、次いでφhは属性
φh(i∧j)=φh(i)∧φh(j),  ∀i,j∈Zq  (19)
を確認する。サイズ(q-1)×(q-1)の行列Mh∈Mq_1(F2)は
【０１５１】
【数４９】
2013507807.tif 000051
【０１５２】
によって定義され、ここで、
【０１５３】
【数５０】
2013507807.tif 000052
【０１５４】
である。自明にφh(0)=0を有するので、この表現はZqの零元を要求しない。
【０１５５】
行列Mhは、自己準同形h∈Lに関連付けられた「拡張バイナリ行列」と呼ばれる。上記の定義では、集合
【０１５６】
【数５１】
2013507807.tif 000053
【０１５７】
は、アルファベットAからのシンボルではなく、整数(i,j)∈Zq×Zqを有する行列Mh∈Mq-1(F2)の行および列にインデックス付けするためだけに使用されることに留意されたい。
【０１５８】
h∈Lが不可逆自己準同形である場合(すなわち、mh∈Mp(F2)が不可逆行列である場合)、φhはZq上の置換を誘導し、その結果として、Mhは列ごとおよび行ごとに1つの「1」のみを含む置換行列になることに留意されたい。
【０１５９】
上記の例A=F8、h=3∈Lの枠組み内の拡張バイナリ行列の構成を説明するが、そのバイナリ像は
【０１６０】
【数５２】
2013507807.tif 000054
【０１６１】
であると想起する。
【０１６２】
mhの行はそれぞれ、φ(1)、φ(2)およびφ(4)を定義する。したがって、φ(1)=5、バイナリ分解がmhの最初の行に対応する整数。同様に、φ(2)=7およびφ(4)=6を有する。
【０１６３】
(19)を使用して、Aをインデックス付けするZ8のその他の元の値を推論する。
φ(3)=φ(1)∧φ(2)=2
φ(5)=φ(1)∧φ(4)=3
φ(6)=φ(2)∧φ(4)=1
φ(7)=φ(1)∧φ(2)∧φ(4)=4  (21)
【０１６４】
最後に、hに関連付けられた拡張バイナリ行列Mhが
【０１６５】
【数５３】
2013507807.tif 000055
【０１６６】
によって与えられる。
【０１６７】
このようにして、M×N個の係数hm,n∈Lのそれぞれについて(すなわち、自己準同形のそれぞれについて)続行する。H∈MM,N(L)のそれぞれの元hm,nを、(20)によって定義される、関連付けられた拡張バイナリ行列Mh∈Mq-1(F2)で置き換えることによって得られる行列は、非バイナリ符号Cのパリティ行列Hに関連付けられた拡張バイナリ行列と呼ばれる、
【０１６８】
【数５４】
2013507807.tif 000056
【０１６９】
と表される行列である。
【０１７０】
バイナリ符号
【０１７１】
【数５５】
2013507807.tif 000057
【０１７２】
は、非バイナリ符号C=Ker(H)⊂ANに関連付けられた拡張バイナリ符号と呼ばれる。
【０１７３】
図5は、前述された通りに構成されたパリティ行列H、そのバイナリ像Hbin、およびその拡張バイナリ像
【０１７４】
【数５６】
2013507807.tif 000058
【０１７５】
の例を挙げている。簡略化するために、非ゼロ値のみが拡張バイナリ像に示されている。
【０１７６】
パリティ行列Hは、N=6の変数およびM=3のチェックを有する、F8上で定義される非バイナリLDPC符号のパリティ行列である。
【０１７７】
そのバイナリ像Hbinは、3×3の基本行列に基づいて構成されたサイズ9×18の行列であり、それぞれの基本行列は、Hの係数、すなわちF8上の自己準同形に対応し、((6)に従って)そのバイナリ表現を与える。それぞれの行列は、行数および列数がバイナリ重み20,21,22に対応する方向で「重み付け」される。
【０１７８】
拡張バイナリ像
【０１７９】
【数５７】
2013507807.tif 000059
【０１８０】
は、サイズ7×7の基本行列に基づいて構成されたサイズ21×42の行列であり、それぞれの基本行列はやはり、行列Hの係数、すなわちF8上の自己準同形に対応し、((20)に従って)その拡張バイナリ表現を与える。バイナリ像とは異なり、ここでは基本行列の行および列は「重み付け」されないが、それぞれはF8の元(零元を除く)に対応する。
【０１８１】
行列
【０１８２】
【数５８】
2013507807.tif 000060
【０１８３】
はあまり稠密でないことに留意されたい。この場合、行列は、42の間で分散された、行当たり4つの非ゼロ(「1」)値しか含まない。したがって、この行列に関連付けられたグラフは、バイナリ像Hbinよりも少ないサイクルを顕著に示す。
【０１８４】
非バイナリ符号Cの語を、Aの元の拡張バイナリ表現を使用して表すことができる。実際に、(X1,...,XN)∈C⊂ANを非バイナリ符号∀n∈{1,...,N}の語とすると、Xnのバイナリ像は
【０１８５】
【数５９】
2013507807.tif 000061
【０１８６】
と表され、その拡張バイナリ像は
【０１８７】
【数６０】
2013507807.tif 000062
【０１８８】
と表され、(14)によって得られる、すなわち、
(an,1,an,2,...,an,q-1)=(Xn,0,Xn,1,...,xn,p-1)Sp  (23)
次いで、
【０１８９】
【数６１】
2013507807.tif 000063
【０１９０】
である。以下では、その作成行列がSpであるバイナリ符号をSpで表す。逆に、バイナリシーケンスを、
∀n∈{1,...,N}、
【０１９１】
【数６２】
2013507807.tif 000064
【０１９２】
となるように、言い換えれば、
(an,1,an,2,...,an,q-1)=(Xn,0,Xn,1,...,xn,p-1)Spとなるような
【０１９３】
【数６３】
2013507807.tif 000065
【０１９４】
となるように、
【０１９５】
【数６４】
2013507807.tif 000066
【０１９６】
とする。Xn∈Aを、そのバイナリ像が
【０１９７】
【数６５】
2013507807.tif 000067
【０１９８】
であるシンボルとすると、全てのn∈{1,...,N}について、(X1,...,XN)∈C⊂ANが非バイナリ符号語であり、
【０１９９】
【数６６】
2013507807.tif 000068
【０２００】
がXNの拡張バイナリ像である。その結果、非バイナリ符号語(X1,...,XN)∈Cをその拡張バイナリ像
【０２０１】
【数６７】
2013507807.tif 000069
【０２０２】
に関連付ける適用は、
【０２０３】
【数６８】
2013507807.tif 000070
【０２０４】
上のCの同形であり、ここで、
【０２０５】
【数６９】
2013507807.tif 000071
【０２０６】
は、SpのN個のコピーから生成されたベクトル空間である。
【０２０７】
以下に、非バイナリ符号のバイナリ表現の簡単な例を挙げる。非バイナリ符号が単一のパリティ方程式(7)によってA=F8上で定義されるとする。p=3およびq=8を有する。行列S3は
【０２０８】
【数７０】
2013507807.tif 000072
【０２０９】
によって定義される。
【０２１０】
Aにおける元Xの拡張バイナリ表現(a1,a2,...,a7)を、(a1,a2,...,a7)=(x0,x1,x2)S3、またはさらには
a1=x0,  a2=x1,  a3=x0+x1,  a4=x2,  a5=x0+x2,  a6=x1+x2,  a7=x0+x1+x2  (26)
によって、そのバイナリ表現(x0,x1,x2)から得ることができる。
【０２１１】
変数a1,a2,...,a7は、バイナリ値x0,x1,x2の考えられる線形F2結合を表すことを理解されたい。
【０２１２】
Yの拡張バイナリ表現(b1,b2,...,b7)およびZの拡張バイナリ表現(c1,c2,...,c7)は同じように得られ、すなわち、(b1,b2,...,b7)=(y0,y1,y2)S3および(c1,c2,...,c7)=(z0,z1,z2)S3である。
【０２１３】
次いで、方程式(10)の系を以下の式
【０２１４】
【数７１】
2013507807.tif 000073
【０２１５】
で、すなわち、拡張バイナリ表現
【０２１６】
【数７２】
2013507807.tif 000074
【０２１７】
を要求することによって書き換えることができ、この拡張バイナリ表現は行列形式では
【０２１８】
【数７３】
2013507807.tif 000075
【０２１９】
となり、ここで、
【０２２０】
【数７４】
2013507807.tif 000076
【０２２１】
である。この行列は3つの基本行列を含み、それぞれの基本行列はF8上の自己準同形(非線形符号の係数)に対応し、3つの行は系(28)の3つの方程式に対応する。
【０２２２】
上記の行列は、X,Y,Zの拡張バイナリ表現の特定のビットに対して、いかなるパリティチェックも定義しないことに留意されたい。21個のビットa1,..,a7,b1,..,b7,c1,..,c7のそれぞれがパリティチェックに加わるためには、既に存在する行の線形結合から推論することができるさらなる行をこの行列に追加する。したがって、例えば、行列(29)の最初の2つの行を追加することによって、すなわち、系(28)の最初の2つの方程式を追加することによって、
(a5+a7)+(b2+b6)+(C5+C6)=0  (30)
が得られ、a5+a7=x0+x2+x0+x1+x2=x1=a2、b2+b6=b4およびc5+c6=c3であると考えると、これを行列の3番目の行
a2+b4+c3=0  (31)
として書き換えることができる。
【０２２３】
同様に、1番目および4番目の行を追加することによって、5番目の行
a3+b7+c1=0  (32)
が得られ、2番目および4番目の行を追加することによって、6番目の行
a1+b3+c2=0  (33)
が得られ、最後に、1番目、2番目および4番目の行を追加することによって、7番目の行
a4+b1+c4=0  (34)
が得られる。
【０２２４】
最終的に、こうして完成された行列は、拡張バイナリ行列
【０２２５】
【数７５】
2013507807.tif 000077
【０２２６】
すなわち
【０２２７】
【数７６】
2013507807.tif 000078
【０２２８】
にほかならない。
【０２２９】
このパリティ行列に関連付けられた2部グラフはいかなるサイクルも含まず、それぞれのビットai、biまたはciは単一のパリティチェックのみに現れる。一般的に、拡張バイナリ行列
【０２３０】
【数７７】
2013507807.tif 000079
【０２３１】
は、非バイナリ行列H自体がいくつかのサイクルを含む場合にのみサイクルを含み、実際に、
【０２３２】
【数７８】
2013507807.tif 000080
【０２３３】
に現れるサイクルはHに既に存在するサイクルによって誘導される。
【０２３４】
非バイナリ符号の拡張バイナリ表現を与えた後、この表現を実現する、本発明による復号方法を以下に開示する。
【０２３５】
図6は、本発明の一実施形態による、非バイナリ符号のための復号方法を流れ図として概略的に表す。
【０２３６】
前述したように、2部グラフGによって表現することができる非バイナリ誤り訂正符号Cを考えるが、この符号は、その値を非バイナリアルファベットAから引き出すN個の変数X1,...,XNの集合によって定義され、M個の制約の集合は、Lにおける係数からなる制約Hの行列によって、前記変数に線形に依存する。これをq=Card(A)と表し、p≧1og2(q)、言い換えれば、pがAのシンボルのバイナリ表現を可能にするビットの最小数であるような最小の整数をpと表す。
【０２３７】
変数X1,...,XNの値がステップ610で考慮される。これらの値を、通信チャネルを介して送信機から受信するか、記録媒体から読み取ることができる。より具体的には、それぞれの変数Xnはp個のバイナリ値xn,0,xn,1,...,xn,pによって表され、ここで、xn,0はLSBであり、xn,pはMSBである。これらのバイナリ値は、知られているやり方で、本質的に硬（hard）または軟（soft）であってもよい。同様に、それぞれの非バイナリ制約Ymは、バイナリ値xn,0,xn,1,...,xn,pによって確認されなければならないp個のパリティチェックym,0,ym,1,...,ym,pに対応する。
【０２３８】
さらに、制約行列Hは復号器に知られている。
【０２３９】
ステップ620で、それぞれの変数Xnに対して、Xnの拡張バイナリ表現
【０２４０】
【数７９】
2013507807.tif 000081
【０２４１】
が、
【０２４２】
【数８０】
2013507807.tif 000082
【０２４３】
となるような、そのバイナリ値xn,0,xn,1,...,xn,pのF2からの係数を有する複数
【０２４４】
【数８１】
2013507807.tif 000083
【０２４５】
の異なる線形結合によって生成される。値
【０２４６】
【数８２】
2013507807.tif 000084
【０２４７】
は、Xnの拡張バイナリ表現のバイナリ値、またはより簡潔には、Xnの拡張バイナリ値と呼ばれる。このようにして、最大q-1個の拡張バイナリ値を生成することが可能である。
【０２４８】
ステップ630で、拡張パリティ行列
【０２４９】
【数８３】
2013507807.tif 000085
【０２５０】
が計算され、異なる変数X1,...,XNの拡張バイナリ値に基づいて、それぞれの(非バイナリ)制約に関連付けられたパリティチェックを得ることが可能になる。こうして得られたチェックは、拡張パリティチェックと呼ばれる。
【０２５１】
ステップ640で、必ずというわけではないが有利には、さらなる行を追加することによって、パリティ行列
【０２５２】
【数８４】
2013507807.tif 000086
【０２５３】
が完成され、前記さらなる行は、ゼロ結合を除く、F2における係数を使用する、既存の行の異なる線形結合によって得られる。最大でq-p-1個のさらなる行を追加して、制約当たり合計q-1個の行を得ることも可能であり、このように完成された行列のそれぞれの行は拡張パリティチェックに関連付けられ、拡張パリティチェックは変数の拡張バイナリ値に適用される。
【０２５４】
より一般的には、制約当たり
【０２５５】
【数８５】
2013507807.tif 000087
【０２５６】
個の異なる線形結合からパリティ行列
【０２５７】
【数８６】
2013507807.tif 000088
【０２５８】
を得ることができ、これらの線形結合の1つ1つは、F2における係数を使用する、既存の行の結合(ゼロ結合を除く)である。これらの結合は、いくつかの既存の行を含む必要はなく、全ての既存の行を含む必要すらない。
【０２５９】
ステップ650で、変数の拡張バイナリ値をチェックの拡張バイナリ値に結び付ける2部グラフ
【０２６０】
【数８７】
2013507807.tif 000089
【０２６１】
によって、反復メッセージパッシング復号プロセスが実行される。変数頂点とチェック頂点との間で交換されるメッセージは、確率、対数尤度比(LLR)、または簡潔にはバイナリ値とすることができる。「和積(sum-product)」または「最小和(min-sum)」型、あるいはこれらの修正された変形である「正規化最小和(normalized  min-sum)」、「自己修正最小和(self-corrected  min-sum)」のアルゴリズムを使用して、本質的に知られているやり方で、メッセージを計算することができる。例えば、言及した最初の2つの型についての説明は、先に引用したN.Wibergによる論文に見出すことができる。「正規化最小和」の変形については、特に「Near  Optimum  universal  belief  propagation  based  decoding  of  low  density  parity  check  codes」と題されたJ.Chenらによる論文、IEEE  Trans.on  Comm.、50(3)、406〜414頁、2002年を参照することができる。「自己修正最小和」の変形については、「Self-Corrected  Min-Sum  of  LDPC  codes」と題されたV.Savinによる論文、IEEE  Int.  Symp.  On  Information  Theory(ISIT)、トロント、カナダ、2008年を参照することができる。
【０２６２】
反復復号は、停止基準が確認される(パリティチェックが確認される、反復の最大数に達する、LLRの絶対値が閾値を越える、など)まで継続する。
【０２６３】
ステップ660で、それぞれの変数のバイナリ値は最終的に、こうして得られたその拡張バイナリ値から決定される。
【０２６４】
図7は、非バイナリ符号Cの拡張バイナリ表現に関連付けられ、図6の方法による復号を可能にする2部グラフ
【０２６５】
【数８８】
2013507807.tif 000090
【０２６６】
の例を示す。
【０２６７】
示されている例は、(1)で与えられたパリティ行列HによってアルファベットA=F8上で定義される非バイナリ符号の例である。ここでは、q=8およびp=3、N=6およびM=3を有する。変数はX1,X2,...,X6と表され、制約はY1,Y2,Y3と表される。全ての変数はF8の元である。
【０２６８】
それぞれの変数Xnは、そのバイナリ像、すなわち3つのバイナリ値(Xn,0,Xn,1,xn,2)によって表される。それぞれの制約Ymは、そのバイナリ像、すなわち3つの拡張パリティチェック(ym,0,ym,1,ym,2)によって表される。
【０２６９】
示されている例では、変数の表現は、ビットの最大数、すなわちq-1=7個のビット(言い換えれば、
【０２７０】
【数８９】
2013507807.tif 000091
【０２７１】
)に拡張されている。同様に、制約の表現は、拡張チェックの最大数に拡張されている。したがって、変数Xnの拡張バイナリ表現は(an,1,an,2,...,an,7)と表され、Ymの拡張バイナリ表現は(bm,1,bm,2,...,bm,7)と表される。
【０２７２】
拡張表現は、次のようなやり方で得られる。
・変数Xnについて
an,1=xn,0
an,2=xn,1
an,3=xn,0+xn,1
an,4=xn,2  (36)
an,5=xn,0+xn,2
an,6=xn,1+xn,2
an,7=xn,0+xn,1+xn,2
したがって、変数の拡張バイナリ表現のそれぞれのビットは、そのバイナリ値の結合として表されることが分かる。
・制約Ymについて
bm,1=ym,0
bm,2=ym,1
bm,3=ym,0+ym,1
bm,4=ym,2  (37)
bm,5=ym,0+ym,2
bm,6=ym,1+ym,2
bm,7=ym,0+ym,1+ym,2
それぞれの拡張パリティチェックは、この制約のバイナリ像のパリティチェックの線形結合として表されることが分かる。
【０２７３】
その行が拡張パリティチェックbj,mに対応する行列
【０２７４】
【数９０】
2013507807.tif 000092
【０２７５】
は、サイズM(q-1)×N(q-1)、すなわち21×42である。この行列を図5に挙げる。
【０２７６】
図7のグラフ上では、変数は六角形、変数の拡張バイナリ値は丸、拡張パリティチェックは四角として示されている。
【０２７７】
図を詰め込み過ぎないようにするため、チェックY1に対応するグラフの部分のみが示されている。もちろん、制約Y2およびY3を表す拡張バイナリチェックも変数頂点の拡張バイナリ値に結び付けられるが、これに対応する辺は示されていない。
【０２７８】
復号を初期化するために使用される変数の初期値は灰色で示されている。より具体的には、バイナリ値Xn,0,Xn,1,Xn,2が使用されて、それぞれ拡張バイナリ値an,1,an,2,an,4を初期化する。その他の拡張バイナリ値は、削除箇所(erasures)、すなわち未知数(例えば、0.5に等しい確率値、または0に等しいLLR値)とみなすことができる。一変形形態によれば、その他の拡張バイナリ値はまた、上記の方程式(36)を使用して初期化される。
【０２７９】
反復メッセージパッシング復号の後、変数X1,X2,...,X6の復号されたバイナリ値は、
【０２８０】
【数９１】
2013507807.tif 000093
【０２８１】
から得られ、言い換えれば、初期化ステップを反映するやり方で、単に拡張バイナリ値からバイナリ値を回復しただけである。
【０２８２】
変数の拡張バイナリ表現は、必ずしもこれらの変数のバイナリ値の全ての線形F2結合を含む必要はないことを理解されたい。同様に、制約の拡張バイナリ表現は、必ずしもこれらの制約に関連付けられたパリティチェックの全ての線形F2結合を含む必要はない。
【０２８３】
いずれの場合も、変数の
【０２８４】
【数９２】
2013507807.tif 000094
【０２８５】
個のバイナリ値および/または
【０２８６】
【数９３】
2013507807.tif 000095
【０２８７】
個のパリティ方程式にわたって拡張された表現を使用することにより、低密度を有する行列および少数のサイクルを示す2部グラフを得ることが可能になる。一般的に、行列
【０２８８】
【数９４】
2013507807.tif 000096
【０２８９】
のパリティ方程式の数
【０２９０】
【数９５】
2013507807.tif 000097
【０２９１】
は
【０２９２】
【数９６】
2013507807.tif 000098
【０２９３】
とは異なるものとすることができることに留意されたい。
【０２９４】
先に説明された実施形態では、変数頂点710(非バイナリシンボル)および720(バイナリシンボル)は、初期化段階の間および復号値回復段階の間、反復復号プロセスの終了時にだけメッセージを通過させる。
【０２９５】
有利には、拡張バイナリ値の数が
【０２９６】
【数９７】
2013507807.tif 000099
【０２９７】
を確認するとき(この場合、an,1,an,2,...,an,q-1の
【０２９８】
【数９８】
2013507807.tif 000100
【０２９９】
個の値an,iだけが考慮される)、拡張バイナリ値an,1,an,2,...,an,q-1はSpまたは省略された符号語の符号語を形成するということを利用することができる。
【０３００】
第1の実施形態の第1の変形形態によれば、拡張バイナリ値が符号制約(例えばan,1+an,2=an,3)を実際に確認することを定期的に、または基準を満足するときにチェックする。そうでない場合には、特定のメトリック(例えば、ハミングメトリック)に従って、すなわち、最尤基準の方向で符号語を復号することになる確率方向において、an,1,an,2,...,an,q-1に最も近い、Spにおける符号語
【０３０１】
【数９９】
2013507807.tif 000101
【０３０２】
を検索することができる。次いで、語an,1,an,2,...,an,q-1は
【０３０３】
【数１００】
2013507807.tif 000102
【０３０４】
と置き換えられ、反復復号が継続される。この変形形態はまた、短縮された符号Spが考慮され、次いで、制約が拡張バイナリ値an,1,an,2,...,an,q-1を
【０３０５】
【数１０１】
2013507807.tif 000103
【０３０６】
の部分集合に適用するときに適用される。
【０３０７】
第2の変形形態によれば、拡張バイナリ変数に適用される制約(an,1,an,2,...,an,q-1は、符号Spにおける語である必要がある)が、メッセージ、すなわち、これらのバイナリ値がチェック頂点に送信する外部情報にも適用されるということを利用する。次いで、ML方向において訂正されたメッセージがこれらの制約を満足するように決定され、これらの訂正されたメッセージが反復復号の次のステップで上記のメッセージの代わりに使用される。ここでは、事後(posteriori)訂正が関与している。省略された符号が考慮されるとき、この結論は依然として有効である。
【０３０８】
第3の変形形態によれば、拡張バイナリ変数に適用される制約(an,1,an,2,...,an,q-1は、符号Spにおける語である必要がある)が、拡張バイナリ変数によって受信されたメッセージ、言い換えれば、チェック頂点によって拡張バイナリ変数に送信された外部情報にも適用されるということを利用する。前述したように、次いで受信されたメッセージがこれらの制約を満足するようにML方向において訂正されてから、チェック頂点に送信されるべきメッセージを決定するために使用される。省略された符号が考慮されるとき、この結論は依然として有効である。
【０３０９】
これら全ての変形形態において、次いで、変数頂点(六角形によって表される)をさらなる制約(省略された符号Spを確認するかしないか)として解釈することができることを理解されたい。
【０３１０】
図8は、同じ非バイナリ符号の2部グラフの別の例を示す。
【０３１１】
それぞれの変数のバイナリ値に関連付けられた頂点は810とラベル付けされている。ラベル820および840はそれぞれ、図7のラベル720および740と同一である。
【０３１２】
バイナリ値と変数の拡張バイナリ値を結び付けるグラフが815で示されている。このグラフは、第1から第2へのパッシングを可能にする
【０３１３】
【数１０２】
2013507807.tif 000104
【０３１４】
個の線形結合を表す。以下では、グラフ815を拡張グラフ800の補助グラフと呼ぶ。
【０３１５】
反復復号ステップは、補助グラフ815によって、バイナリ値と変数の拡張バイナリ値との間のメッセージパッシングの1つの第1の段階、およびグラフ800によって、変数の拡張バイナリ値と拡張チェックとの間のメッセージパッシングの第2の段階を、少なくとも１つ含む。
【０３１６】
したがって、3レベルのメッセージパッシングサイクル(810->820->840->820->810)を有する。
【０３１７】
他のメッセージパッシング戦略は、本発明の範囲から逸脱することなく、当業者によって想到されうる。
【符号の説明】
【０３１８】
710  変数頂点(非バイナリシンボル)
720  変数頂点(バイナリシンボル)
800  拡張グラフ
810  頂点
815  補助グラフ
【図１】
2013507807.tif 000115
【図２】
2013507807.tif 000116
【図３】
2013507807.tif 000117
【図４Ａ】
2013507807.tif 000118
【図４Ｂ】
2013507807.tif 000119
【図５】
2013507807.tif 000120
【図６】
2013507807.tif 000121
【図７】
2013507807.tif 000122
【図８】
2013507807.tif 000123
【国際調査報告】
2013507807.tif 000124
2013507807.tif 000125
2013507807.tif 000126
2013507807.tif 000127