(57)【要約】【課題】方法は、Ｎ個のサンプルの入力信号をｑ元アルファベットから引き出されるｋ個のシンボルのストリングに量子化する。【解決手段】補足的な方法は、何らかの歪み測度が与えられると、量子化ストリングから入力信号の歪みが最小であるバージョンを再生する。まず、スパーズ生成素ファクターグラフ表現を有する［Ｎ，ｋ］ｑ線形誤り訂正符号を選択する。ｑ元シンボルからサンプルへの固定マッピングを選択する。ＳＧＦＧ符号に対する軟入力復号器と符号器とを選択する。固定マッピングを使用して、入力信号と歪み測度とからコスト関数を求める。復号器は、入力信号に対して低コストのＳＧＦＧ符号の符号語に対応する情報ブロックを求める。入力信号を、固定マッピングと組み合わせて、ＳＧＦＧ符号に対する符号器を使用して再生することができる。【選択図】図４
2005110251.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ個のサンプルを含む入力信号を、ｑ元アルファベットから選択されたｋ個のシンボルのストリングに量子化する方法であって、
スパーズ生成素ファクターグラフ表現を有する［Ｎ，ｋ］ｑ線形ブロック誤り訂正符号を選択すること、
前記シンボルから前記サンプルへの選択されたマッピング関数と所定の歪み測度とを使用して前記入力信号に対するコスト関数を求めること、
および
前記コスト関数を、前記線形ブロック誤り訂正符号の符号語であって低歪みコストを有する符号語に対応する、前記ｋ個のシンボルのストリングを含む情報ブロックに復号すること
を含む、Ｎ個のサンプルを含む入力信号を、ｑ元アルファベットから選択されたｋ個のシンボルのストリングに量子化する方法。
【請求項２】
前記線形ブロック誤り訂正符号は、［Ｎ，ｋ］ｑスパーズ生成素ファクターグラフ符号である
請求項１記載のＮ個のサンプルを含む入力信号を、ｑ元アルファベットから選択されたｋ個のシンボルのストリングに量子化する方法。
【請求項３】
前記線形ブロック誤り訂正符号は、低密度生成素行列符号である
請求項１記載のＮ個のサンプルを含む入力信号を、ｑ元アルファベットから選択されたｋ個のシンボルのストリングに量子化する方法。
【請求項４】
前記復号は、軟入力復号方法である
請求項１記載のＮ個のサンプルを含む入力信号を、ｑ元アルファベットから選択されたｋ個のシンボルのストリングに量子化する方法。
【請求項５】
前記復号は、確率伝播復号方法である
請求項１記載のＮ個のサンプルを含む入力信号を、ｑ元アルファベットから選択されたｋ個のシンボルのストリングに量子化する方法。
【請求項６】
前記復号は、ビット反転復号方法である
請求項１記載のＮ個のサンプルを含む入力信号を、ｑ元アルファベットから選択されたｋ個のシンボルのストリングに量子化する方法。
【請求項７】
前記ｋ個のシンボルのストリングを前記線形ブロック誤り訂正符号の再生符号語に符号化すること、
および
前記再生符号語のシンボルを前記選択されたマッピング関数に従ってサンプルに置き換えること
から成る、前記ｋ個のシンボルのストリングから前記入力信号の歪みが最小のバージョンを再生する方法、をさらに含む
請求項１記載のＮ個のサンプルを含む入力信号を、ｑ元アルファベットから選択されたｋ個のシンボルのストリングに量子化する方法。
【請求項８】
前記符号化の方法は、前記線形ブロック誤り訂正符号を表すスパーズ生成素ファクターグラフに対するハードメッセージを用いる確率伝播方法である
請求項７記載のＮ個のサンプルを含む入力信号を、ｑ元アルファベットから選択されたｋ個のシンボルのストリングに量子化する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、信号を量子化し量子化信号を再生する分野に関する。
【背景技術】
【０００２】
データ記憶および通信の分野における基本的な問題は、入力信号を量子化する、およびその後最小の歪み量で量子化信号を再生する、実際的な方法の開発である。R. GrayおよびD. Neuhoff著、「Quantization」、IEEE Transactions on Information Theory、vol. 44、pp.2325-2383、October 1998を参照のこと。
【０００３】
信号を量子化し再生する方法は、大規模な物理的現象から取得される信号と同様に、一般に音声、画像またはビデオファイルとともに発生する非常に大量のデータを記憶または転送するシステムの重要な部分である。これらの方法は、特に、大量のデータを比較的低速な通信ネットワークで転送するかまたは量が限られたメモリに大きいデータセットを記憶する場合に重要である。量子化は、非可逆圧縮の一形態である。
【０００４】
量子化および再生問題
信号を量子化し再生する問題を、以下のように定式化することができる。入力信号は、Ｎ個のサンプルのデータを含む。信号は、画像、ビデオ、音声ストリーム、もしくは数のセットによって表すことができる他の任意の信号を表してもよい。サンプルは、実数であっても、精度が制限された数であってもよい。たとえば、サンプルは、１６ビット数であってもよく、それはサンプルが２１６のあり得る値のうちの１つをとることができることを意味する。
【０００５】
かかる信号を、ｑ元（q-ary）アルファベットから選択されるｋ個のシンボルのストリングに量子化することが望ましい。実際の適用では、ｑは、通常、サンプルがとることができるレベルの数よりはるかに小さい。すなわち、シンボルを表すために必要なビットの数は、通常、サンプルを表すために必要なビットの数より少ない。さらに、ｋ個のシンボルのストリングを後に、平均して入力信号と実質的に同様のＮ個のサンプルの出力信号に再生することができるように、量子化方法を使用することが望ましい。すなわち、量子化および再生により、最小量の歪みがもたらされる。
【０００６】
図１は、量子化および再生問題の一般的な形態１００を要約したものを示す。ソースは、量子化すべきＮ個のサンプル１０２の入力信号１０１を生成する。入力信号ｘ［ｎ］（指数ｎはＮ個のサンプルに及ぶ）を、量子化器１１０に渡す。量子化器は、サンプル１０２をｋ個のシンボルのストリングｓ［ａ］１１５に変換する。再生器１２０は、後に、シンボル１１５をＮ個のサンプル１０３の出力信号ｚ［ｎ］１０４に変換することができ、これは入力信号１０１と実質的に同様である。
【０００７】
例示的な量子化および再生方法
例示的な例として、入力信号がＮ＝４個のサンプルを含み、信号の各サンプルが、０．０と１．０との間の一様な確率分布とは無関係に選択される３つの有効数字の実数である、という場合を考える。典型的な信号は、｛．７２３，．２３８，．１２９，．６７８｝である。かかる信号を、ｑ＝４個のシンボルのアルファベット、たとえば４つの文字Ａ、Ｂ、ＣおよびＤから選択されるｋ＝２個のシンボルのストリングに量子化したいと仮定する。
【０００８】
この問題のための例示的な量子化方法は、以下ように作用する。まず、信号における最初の２つのサンプル、この場合は．７２３および．２３８を考える。これらがともに．５以上である場合、量子化ストリングの第１の文字をＡであるように割り当てる。第１のサンプルが．５以上であるが第２のサンプルが．５未満である場合、第１の文字をＢであるように割り当てる。第１のサンプルが．５未満であり第２のサンプルが．５以上である場合、第１の文字をＣであるように割り当てる。最後に、第１および第２のサンプルがともに．５未満である場合、第１の文字をＤであるように割り当てる。同一の規則を使用して、信号の第３および第４のサンプルの値に基づいて量子化ストリングの第２の文字を割り当てる。この方法を使用して、信号｛．７２３，．２３８，．１２９，．６７８｝をストリング｛Ｂ，Ｃ｝に量子化する。
【０００９】
量子化方法１１０とともに、入力信号を再構築するための適合する再生方法１２０が必要である。例示的な量子化方法と適合する妥当な再生方法は、以下のように作用する。量子化ストリングの最初の文字がＡである場合、再生信号の最初の２つのサンプルを｛．７５，．７５｝であるように割り当てる。ストリングの第１の文字がＢである場合、再生信号の最初の２つのサンプルを｛．７２，．２５｝であるように割り当てる。第１の文字がＣである場合、最初の２つのサンプルを｛．２５，．７５｝であるように割り当て、第１の文字がＤである場合、最初の２つのサンプルを｛．２５，．２５｝であるように割り当てる。同一の規則を利用して、第２の文字に基づいて第３および第４のサンプルを割り当てる。たとえば、これらの規則を使用してストリング｛Ｂ，Ｃ｝を再生信号｛．７５，．２５，．２５，．７５｝に変換する。
【００１０】
レートおよび歪み
任意の量子化／再生方法に対する２つの非常に重要な測度は、方法のレートおよびその方法によってもたらされる歪みである。
【００１１】
量子化器のレートＲは、入力信号のサンプル毎に使用されるビットの数である。単一ｑ元シンボルの情報内容はｌｏｇ２（ｑ）ビットであるため、量子化器の全体のレートは、Ｒ＝ｋｌｏｇ２（ｑ）／Ｎである。上の一例としての量子化器のレートは、２ｌｏｇ２（４）／４＝１ビット／サンプルである。明らかに、入力信号を表すために最小数のビットを使用するように、量子化器のレートは可能な限り低いことが望まれる。
【００１２】
歪みＤは、入力信号と再生出力信号との差の測度である。歪みを、入力信号のいずれの特徴が重要であるとみなされるかに応じて、多くの異なる方法で定義することができる。入力信号のサンプルが実数である場合、歪みを測定する１つの自然な方法は、入力信号と出力信号との差の二乗の合計を平均する、すなわち歪みを
【００１３】
【数１】
2005110251.tif 000003
【００１４】
であると定義することである。この歪み測度を、平均二乗誤差（ＭＳＥ）歪みと呼ぶ。
【００１５】
ほとんどの場合に妥当である、歪み測度に対するより一般的な形態は、
【００１６】
【数２】
2005110251.tif 000004
【００１７】
である。ここで、ｄ（ａ，ｂ）は、２つの個々のサンプルａとｂとの間の距離を測る。
【００１８】
通常、ｄ（ａ，ｂ）≧０であり、ａ＝ｂである場合はｄ（ａ，ｂ）＝０であるような距離測度を使用する。これにより、歪みが非負であり、出力信号ｚ［ｎ］が入力信号ｘ［ｎ］と同一である場合に０に等しいことが保証される。
【００１９】
優れた量子化および再生方法では、歪みとレートとをともに最小化する。しかしながら、レートと歪みとの間のトレードオフがあることが必然的である。一般に、レートが高いほど歪みを少なくすることが可能になる。
【００２０】
最適なレート・歪み関数
量子化問題を、入力信号の確率分布と歪み測度とによって定義することができる。量子化問題によっては、レートの関数として最適な歪みを与える式を明示的に求めることが可能である。この概念は、情報理論を紹介するシャノン（Shannon）の最初の論文にまでさかのぼる。C.E. Shannon著、「A Mathematical Theory of Communication」、Bell Syst. Tech. Journal、vol 27、pp.379-423、623-656、1948およびC.E. Shannon著、「Coding Theorems for a Discrete Source with a Fidelity Criterion」、IRE Nat. Conv. Rec.、Pt. 4、pp.142-163、1959を参照のこと。
【００２１】
シャノンは、最適なレート・歪み関数、すなわち特定のレートが与えられた場合の最適な歪みまたはその逆が、入力確率分布と歪み測度とのみに依存する式によって与えられることを証明した。この理論の詳細な論考について、T. CoverおよびJ. Thomas著、「Elements of Information Theory」、John Wiley & Sons、New York、1991を参照のこと。シャノンの式の詳細な理解は必要でない。重要な点は、単に、任意の量子化問題に対し最適なレート・歪み限界がある、ということである。
【００２２】
最適なレート・歪み関数をより明示的に計算することができる場合の１つの量子化問題は、信号のサンプルがガウス分布とは無関係に選択され、歪み測度がＭＳＥ歪みである場合である。
【００２３】
従来技術による量子化および再生方法における主な問題は、それらのいずれも、この問題に対し最適なレート・歪み限界での性能に達しない、ということである。たとえば、ＭＳＥ歪みに対してガウス源から生成される入力信号を量子化する場合、エントロピー符号化スカラー量子化（ＥＣＳＱ）方法は、レートに応じてシャノンレート・歪み限界から１．５〜３．４ｄＢ離れる。R. GrayおよびD. Neuhoff著、「Quantization」、IEEE Transactions on Information Theory、vol. 44、pp.2325-2383、October 1998を参照のこと。
【００２４】
この問題に対し、最適な量子化とともに２５６状態符号を使用するトレリス符号量子化（ＴＣＱ）は、最適なレート・歪み限界から０．５〜１．４ｄＢである。M. MarcellinおよびT. Fischer著、「Trellis Coded Quantization of Memoryless and Gauss-Markov Sources」、IEEE Transactions on Communications、vol. 38、pp.82-93、1990を参照のこと。
【００２５】
従来技術による量子化および再生方法は、同様に、いかなる他の非自明な量子化問題に対しても最適なレート・歪み限界を達成することができない。
【００２６】
二元消失量子化問題
最適なレート・歪み関数を明示的に計算することができる別の量子化問題は、二元消失量子化（binary erasure quantization）（ＢＥＱ）問題と呼ばれる。ＢＥＱ問題では、入力信号ｘ［ｎ］は、Ｎ個のサンプルのシーケンスであり、そこでは各サンプルは、「０」、「１」および「＊」で示される３つのあり得る値をとることができる。「＊」の値を、「消失」または「ドントケア」シンボルとみなすことができる。
【００２７】
ｘ［ｎ］の各サンプルを、無関係に、確率ｐｅで消失「＊」であると選択し、確率（１−ｐｅ）／２で「１」または「０」であると選択する。
【００２８】
信号ｘ［ｎ］を、ｋ個のビットｓ［ａ］のストリングに量子化する。この問題に対してｑ＝２であるため、したがって量子化器のレートはＲ＝ｋ／Ｎである。
【００２９】
ストリングｓ［ａ］を、最終的に、再生出力信号ｚ［ｎ］に変換する。出力信号ｚ［ｎ］は、「０」および「１」のサンプルのシーケンスである。ＢＥＱ問題における歪み測度は、
【００３０】
【数３】
2005110251.tif 000005
【００３１】
である。ここで、ａ＝＊またはａ＝ｂの場合はｄ（ａ，ｂ）であり、それ以外の場合はｄ（ａ，ｂ）＝１である。この問題に対し、最適なレート・歪み関数をシャノンのレート・歪み式を使用して求めることができる。特に、ゼロ歪み（Ｄ＝０）を要求する場合、最適レートはＲ＝１−ｐｅであることが分かる。
【００３２】
以下は、ＢＥＱ問題のより直観的な説明である。サンプルのうちのいくつか、たとえば「０」および「１」のサンプルを正確に再生する一方で、他のサンプル、たとえば「＊」サンプルを「０」または「１」に置き換えることができることを確実にしたい場合、Ｎ個のサンプルのランダムな入力信号が与えられる。
【００３３】
当然ながら、信号を受け取る前は、いずれのサンプルが重要であるか、およびいずれのサンプルが消失であるかを知らず、さらに、量子化器はいかなる入力信号に対しても作用しなければならない。
【００３４】
「０」または「１」のサンプルのうちのいくつが不正確に再生されるかに関して歪みの量を測定する。最適なレート・歪み関数に従って、通常は、いかなる歪みもなしに、入力信号をｋ個のシンボル（ｋは単に、元の信号の「０」および「１」のサンプルの平均数である）のストリングに量子化することができる。
【００３５】
二元対称量子化問題
例示の目的で有用な別の量子化問題は、二元対称量子化（binary symmetric quantization）（ＢＳＱ）問題である。ＢＳＱ問題では、入力信号ｘ［ｎ］はＮ個のサンプルのシーケンスであり、各サンプルは、「０」「１」によって示される２つのあり得る値のみをとることができる。ｘ［ｎ］の各サンプルを、無関係に、確率１／２で「１」であると選択し、確率１／２で「０」であると選択する。
【００３６】
信号ｘ［ｎ］を、ｋビットのストリングｓ［ａ］に量子化する。ストリングｓ［ａ］を、再生出力信号ｚ［ｎ］に変換する。出力信号ｚ［ｎ］は、「０」および「１」のサンプルのシーケンスである。ＢＥＱ問題における歪み測度は、
【００３７】
【数４】
2005110251.tif 000006
【００３８】
である。ここで、ａ＝ｂの場合はｄ（ａ，ｂ）＝０であり、それ以外の場合はｄ（ａ，ｂ）＝１である。
【００３９】
ＢＳＱ問題に対しても、最適なレート・歪み関数をシャノンのレート・歪み理論に従って求める。たとえば、レート１／２の量子化器の場合、あり得る最小歪みはおよそ０．１１であることが分かる。
【００４０】
ＢＥＱ問題とＢＳＱ問題とはともに、あり得るサンプル値の数が非常に少ないという意味で、実際的な適用では幾分か非現実的である。しかしながら、これらは、量子化および再生問題を例示するためにはまだ有用である。
【００４１】
線形ブロック誤り訂正符号
本発明は、線形ブロック誤り訂正符号を従来とは異なる方法で使用する。したがって、以下は、かかる線形ブロック誤り訂正符号に関する必要な背景情報を提供することを意図する。Blahut著、「Algebraic Codes for Data Transmission」、Cambridge University Press: Cambridge、2003およびMacWilliams他著、「The Theory of Error-Correcting Codes」、North-Holland: New York、NY、1997は、誤り訂正符号に関する優れた教科書である。
【００４２】
本明細書において「符号」という場合はいつも、特に線形ブロック誤り訂正符号を意味する。これらの符号の背景にある基本的な概念は、Ｎ個のシンボルのストリングを使用してｋ個のシンボルのストリングを符号化することであり、Ｎ＞ｋである。従来の誤り訂正符号の適用では、破損したメッセージを復号し訂正するために追加のＮ−ｋビットを使用する。
【００４３】
Ｎ個のシンボルの任意のストリングを、時に「ブロック」または「語」とも呼ぶ。符号のすべての制約を満足するＮ個のシンボルのブロックを、「符号語」と呼ぶ。シンボルを、ｑ元アルファベットから引き出す。非常に重要な特別な場合は、ｑ＝２の場合である。この場合、符号は「２進」符号である。
【００４４】
図２は、線形ブロック誤り訂正符号を使用する従来の通信路符号化方法２００を示す。ソース２０１は、ｋ個のシンボル２０２を含むストリングｓ［ａ］を生成し、シンボルはｑ元アルファベットから引き出される。このストリングを、誤り訂正符号の符号器２１０に渡し、Ｎ個のシンボル２０３を含む符号語ｘ［ｎ］に変換する。
【００４５】
そして、符号語２０３を、通信路２１５を通して送信し、そこでそれらは、破損して信号ｙ［ｎ］２０４になる。そして、破損した信号ｙ［ｎ］２０４を、復号器２２０に渡し、復号器２２０は、符号語ｘ［ｎ］の再構築２０５か、もしくは等化に、通信路における付加的雑音がそれほど大きくない場合は、入力信号と同様のｋ個のシンボルストリングｓ［ａ］の形態の出力信号２０６を出力する。
【００４６】
符号のパラメータ
符号Ｃを、ブロック長Ｎを有するｑｋ個のあり得る符号語のセットによって定義する。パラメータｋを、時に符号の「次元（dimension）」と呼ぶ。符号は、通常、Ｎおよびｋが大きい場合はるかに有効である。しかしながら、パラメータＮおよびｋのサイズが増大するに従い、破損したメッセージを復号することが困難になる。
【００４７】
符号の「レート」Ｒを、Ｒ＝ｋｌｏｇ２（ｑ）／Ｎによって定義する。
【００４８】
２つの符号語間のハミング距離を、２つの語における異なるシンボルの数として定義する。符号の距離ｄを、符号における符号語のすべての対の間の最小ハミング距離として定義する。ｄの値が大きい符号ほど、より大きい誤り訂正能力を有する。パラメータＮ、ｋおよびｑを有する符号を、［Ｎ，ｋ］ｑ符号と呼ぶ。距離ｄもまた既知である場合、それらを［Ｎ，ｋ，ｄ］ｑ符号と呼ぶ。
【００４９】
ガロア体
線形符号を、通常、生成素およびパリティ検査行列に関して表現する。これらの行列を定義するためには、まずｑ元シンボルを加算し乗算する方法が必要である。ガロア体とも呼ぶ有限体の理論は、ｑ元シンボルに対する加法および乗法を定義する方法を提供する。ガロア体の詳細な説明について、すでに引用したものまたはS. LinおよびD. Costello著、「Error Control Coding: Fundamentals and Applications」、Prentice Hall: Englewood Cliffs、NJ、1983を含む、誤り訂正符号に関する任意の教科書を参照のこと。
【００５０】
ガロア体では、ｑ元アルファベットからの任意の２つのシンボルを合せて加算または乗算する場合、回答は同じアルファベットからの要素である。乗法および加法単位元要素があり、各要素は、乗法および加法逆元を有するが、加法単位元要素は乗法逆元を有していない。
【００５１】
ガロア体を、ＧＦ（ｑ）と示す。ｑは、アルファベットの要素の数である。ガロア体を、その加法および乗法テーブルに関して定義することができる。もっとも単純なガロア体は、ＧＦ（２）であり、それは２つの要素０および１を有し、０は加法単位元であり１は乗法単位元である。ＧＦ（２）に対する加法規則は、０＋０＝１＋１＝０および０＋１＝１＋０＝１であり、ＧＦ（２）に対する乗法規則は、０＊０＝０＊１＝１＊０＝０および１＊１＝１である。
【００５２】
ＧＦ（３）は、３つの要素０、１および２を有し、０は加法単位元であり、１は乗法単位元であり、加法規則は、０＋０＝１＋２＝２＋１＝０、０＋１＝１＋０＝２＋２＝１、０＋２＝１＋１＝２＋０＝２であり、乗法規則は、０＊０＝０＊１＝０＊２＝１＊０＝２＊０＝０、１＊１＝２＊２＝１、１＊２＝２＊１＝２である。
【００５３】
ガロア体を、素数かまたは素数の整数乗である任意のｑに対して定義することができる。任意のガロア体に対する加法および乗法規則を、先に引用した誤り訂正符号に関する教科書に記載されている理論から導出することができる。
【００５４】
本明細書で述べるｑ元シンボルの加法および乗法はすべて、ＧＦ（ｑ）の規則を使用する加法および乗法であると想定しなければならない。
【００５５】
符号の生成素行列表現
任意の２つの符号語の加法もまた符号語である場合、ブロック符号は「線形」である。各々Ｎ個のシンボルの２つの符号語の合計を、１つずつ個々のシンボルを合計することによって得られるＮ個のシンボルの符号語であるとして定義する。たとえば、ＧＦ（２）を使用する２つの符号語１１１０１００および０１１１０１０の合計は、１００１１１０である。
【００５６】
線形符号を、生成素行列によってコンパクトに表すことができる。実際には、多くの異なる生成素行列が同じ線形符号を表すことができる。
【００５７】
［Ｎ，ｋ］ｑ符号を表す生成素行列は、Ｌ行およびＮ列の行列であり、行列の各要素はｑ元シンボルである。行列のＮ列は、符号語におけるＮ個のシンボルに対応する。生成素行列は、ｋ個の線形独立行を含む。Ｌ＞ｋである場合、生成素行列の行のうちのいくつかは冗長である。符号におけるすべての符号語を、生成素行列の行の線形組合せをとることによって取得することができる。
【００５８】
生成素行列の例示的な例は、「テトラ符号（tetra-code）」として既知の［Ｎ＝４，ｋ＝２，ｄ＝３］ｑ＝３符号に対する以下の行列である。
【００５９】
【数５】
2005110251.tif 000007
【００６０】
テトラ符号は、ブロック長Ｎ＝４を有し、符号語の数は、ｑｋ＝９である。
【００６１】
別の例として、以下は［Ｎ＝７，ｋ＝４，ｄ＝３］ｑ＝２バイナリハミング符号の生成素行列である。
【００６２】
【数６】
2005110251.tif 000008
【００６３】
誤り訂正符号のための符号器
線形［Ｎ，ｋ］ｑ符号に対する符号器２１０は、ｋ個のシンボルのストリング２０２をＮ個のシンボルの符号語２０３に変換する。このようにｑｋ個の異なる符号語に変換されるｋ個のシンボルのストリングを、「情報ブロック」と呼び、情報ブロックのシンボルを「情報シンボル」と呼ぶ。符号器は、符号に対し生成素行列を使用して構成することができる。
【００６４】
より詳細には、情報ブロックｓ［ａ］を有し、生成素行列Ｇによって生成される符号に対しＮ個のシンボル符号語ｙ［ｎ］を構成したいと想定する。符号化を式
【００６５】
【数７】
2005110251.tif 000009
【００６６】
を使用して行うことができる。ここで、Ｇ［ａ，ｎ］は、行列Ｇにおける第ａ行および第ｎ列のシンボルの値である。たとえば、式（３）で与えられた生成素行列によって表されるようなテトラ符号を考慮する。情報ブロックが｛１，２｝である場合、対応する符号語は、ＧＦ（３）の加法および乗法の規則を使用して、１０１１＋２＊０１１２＝１０１１＋０２２１＝１２０２である。全部で、テトラ符号の９個の符号語は、００００、１０１１、２０２２、０１１２、１１２０、２１０１、０２２１、１２０２および２２１０である。
【００６７】
なお、すべて０の語は、常に、情報ブロックのすべてのシンボルが０に等しい場合に得られる、線形符号の符号語である。
【００６８】
符号のパリティ検査行列表現
また、線形符号を、パリティ検査行列によって表すことも可能である。［Ｎ，ｋ］ｑ符号を表すパリティ検査行列を、Ｍ行およびＮ列を有するｑ元シンボルの行列によって定義する。パリティ検査行列のＮ列は、符号のＮシンボルに対応する。行列の線形独立行の数は、ｋでなければならない。
【００６９】
パリティ検査行列の各行は、制約を表す。特定の行によって表される制約に含まれるシンボルは、その行に非ゼロシンボルを有する列に対応する。パリティ検査制約により、それらのシンボルのＧＦ（ｑ）に亙る重み付き合計が、強制的にゼロに等しくなる。たとえば、バイナリ符号の場合、パリティ検査行列
【００７０】
【数８】
2005110251.tif 000010
【００７１】
は、３つの制約
【００７２】
【数９】
2005110251.tif 000011
【００７３】
を表す。ここで、ｙ［ｎ］は、第ｎビットの値である。このパリティ検査行列は、式（４）で与えられた生成素行列によって表される［Ｎ＝７，ｋ＝４，ｄ＝３］ｑ＝２ハミング符号を表す別の方法である。
【００７４】
符号を生成素行列Ｇおよびパリティ行列Ｈによって表す場合、その二重（dual）符号は、Ｈが生成素行列である符号である。
【００７５】
誤り訂正符号に対する復号器
線形［Ｎ，ｋ］ｑ符号に対する復号器２２０は、送信された符号語２０３の歪んだバージョンｘ［ｎ］を符号語ｙ［ｎ］２０５に変換する。符号語ｙ［ｎ］とｙ［ｎ］に符号化される情報ブロックｓ［ａ］との間に１対１マッピングがあるため、復号器を、ｘ［ｎ］を情報ブロックｓ［ａ］に変換することとみなすことも可能である。
【００７６】
送信された符号語の歪んだバージョンは、時に、サンプルが誤り訂正符号と同じｑ元アルファベットからの値をとる、語ｘ［ｎ］である。かかる入力信号を受け入れる復号器を、しばしば「硬入力（hard-input）」復号器と呼ぶ。かかる復号器は、通信路により幾分か低い確率で符号語のｑ元シンボルが破損して他のｑ元シンボルになる場合に有用である。かかる通信路に対する最適な硬入力復号器は、ｘ［ｎ］から最短距離を有する符号語ｙ［ｎ］を出力する。
【００７７】
代替的に、信号ｘ［ｎ］を、まず「コスト関数」に変換することができ、その後そのコスト関数を復号器に入力する。コスト関数は、各シンボルのあり得る状態各々に対するコストを指定するベクトルである。
【００７８】
かかる入力コスト関数を受け入れる復号器を、しばしば「軟入力（soft-input）」復号器と呼ぶ。ブロック長３のバイナリ符号の場合、軟入力復号器に対するコスト関数例は、［（．１，．３）、（．２，．４），（．２５，．１５）］である。このコスト関数は、第１のビットに値「０」を割り当てるコストが．１であり、第１のビットに値「１」を割り当てるコストが．３であり、第２のビットに値「０」を割り当てるコストが．２である等を意味する。
【００７９】
最適な軟入力復号器は、コスト関数が与えられると、あり得る最低の合計コストを有する符号語ｙ［ｎ］を返す。たとえば、先の段落の例の３ビット符号が２つの符号語０００および１１１を有する場合、符号語０００が返される。それは、符号語１１１が．３＋．４＋．１５＝．８５のコストを有する一方で、それが．１＋．２＋．２５＝．５５のコストを有するためである。
【００８０】
軟入力復号器のコストを、しばしば、受信信号と通信路モデルとが与えられた場合に、各ビットに対する対数尤度の負数に等しいように取る。このため、最適な復号器を、しばしば「最大尤度」復号器と呼ぶ。それは、コストを最小化することは尤度を最大化することに対応するためである。
【００８１】
誤り訂正符号に対し最適な硬入力または軟入力復号器を構成することは、一般に、誤り訂正符号に対して符号器を構成することより、はるかに複雑な問題である。この問題は、大きいＮおよびｋを有する符号に対して、特に複雑になる。この理由で、実際に使用される多くの復号器は最適ではない。非最適な硬入力復号器は、受け取った語に最も近い符号語を求めようと試みるが、そうすることは保証されておらず、一方、非最適な軟入力復号器は、最低コストの符号語を求めようと試みるが、そうすることは保証されていない。
【００８２】
符号の最適性能に対する限界
情報理論は、最適な復号器のあり得る性能に対して重要な限界を与える。これらの結果のいくつかは、最初に、C.E. Shannonにより、「A Mathematical Theory of Communication」、Bell Syst. Tech. Journal、vol 27、pp.379-423、623-656、1948において証明された。R. Gallager著、「Information Theory and Reliable Communication」、John Wiley & Sons、New York 1968は、この問題に関するさらなる参考教科書である。
【００８３】
直観的な用語で表現すると、シャノンは、いかなる雑音のある通信路も、その雑音性に関連する容量Ｃを有し、その容量が符号のレートより大きい場合にのみ、最適な符号の最適な復号器がすべての誤りを訂正することができることを示した。
【００８４】
雑音のある通信路の例は、二元消失通信路（ＢＥＣ）である。この通信路は、２入力および３出力通信路であり、入力は値「０」または「１」をとるビットであり、出力は値「０」、「１」または「？」をとり、「？」は消失を示す。各「０」または「１」入力ビットは、確率１−ｐｅで変化せずに通信路を通過し、確率でｐｅで「？」に変換され、すなわち消失される。シャノンの理論を使用してＢＥＣの容量は１−ｐｅであると示すことが可能である。
【００８５】
これは、平均してビットの半分が消失される二元消失通信路を使用している場合、０．５未満のレートを有する誤り訂正符号を使用することによりすべての消失を訂正することができる、ということを意味する。
【００８６】
実際の誤り訂正符号化方法は最適な性能から非常に遠かったため、何年もの間、シャノンの限界は、単に理論的に重要であるようにしかみられなかった。しかしながら、非常に最近、確率伝播（belief propagation）復号器と不規則な低密度パリティ検査符号とを使用した誤り訂正方法が、シャノン限界のまたはそれにきわめて近い結果を達成することができることが示された。確率伝播復号器と低密度パリティ検査符号とについては、後により詳細に説明する。
【００８７】
ＢＥＣに対し、Oswald等は、確率伝播復号器を使用して復号された不規則な低密度パリティ検査符号がシャノン限界に達することができることを示した。P. OswaldおよびA. Shokrollahi著、「Capacity-achieving Sequences for the Erasure Channel」、IEEE Transactions on Information Theory、vol. 48、pp.3017-3028、December 2002を参照のこと。加法性白色ガウス雑音（ＡＷＧＮ）に対し、Chung等は、シミュレーションにより、同様の符号と復号器とを使用してシャノン限界の．００４５ｄＢ内で１０−５のビット誤り率を取得することができることを示した。S.-Y. Chung、G. Forney、T. RichardsonおよびR. Urbanke著、「On the Design of Low-Density Parity-Check Codes Within .0045 dB of the Shannon Limit」、IEEE Communications Letters、vol. 5、pp. 58-60、February 2001を参照のこと。
【００８８】
反直感的に、非最適な復号器を使用することが、通信路符号化問題に対しシャノン限界に非常に近づくための重要な要素であることを理解することが重要である。この明白な逆説の説明は、シャノン限界に近づくためには、非常に大きいブロック長および次元の符号を使用しなければならない、ということである。かかる長い符号は、通常、最適な復号器を使用して事実上復号することができない。
【００８９】
最適に復号することができる例外的に長い符号があるが、かかる符号は、常に、それらの符号語間の非常に不十分な最短距離等、他の深刻な欠陥を有する。
【００９０】
確率伝播復号器のわずかな非最適性は、非常に長い低密度パリティ検査符号を使用することができることによって得られる利点に比較して、比較的重要でないことが分かる。
【００９１】
低密度パリティ検査符号
非常に重要な種類の符号、すなわち低密度パリティ検査（ＬＤＰＣ）符号は、R. Gallagerにより「Low Density Parity Check Codes」、MIT Press、Cambridge、1963において説明された。かかる符号の定義する特性は、それらのパリティ検査行列が低密度の非ゼロ要素を有する、ということである。
【００９２】
Gallagerによって述べられた元のＬＤＰＣ符号では、符号を定義するパリティ検査行列の各行は、同じ数の非ゼロ要素を有する。これらの符号を、時に、「レギュラー」ＬＤＰＣ符号と呼ぶ。イレギュラーＬＤＰＣ符号では、パリティ検査行列の行が異なると、異なる数の非ゼロ要素を有する可能性がある。
【００９３】
Gallagerはまた、大きいブロック長のＬＤＰＣ符号に対し２つの種類の復号方法を紹介した。彼が「確率的復号（probabilistic decoding）」と呼ぶ一方の方法は、しばしば「ｓｕｍ−ｐｒｏｄｕｃｔ復号」または「確率伝播復号」とも呼ばれる。他方の方法は、いわゆる「ビット反転（bit-flipping）」方法である。これらの復号方法はいずれも最適ではないが、上述したように、確率伝播復号方法は、シャノン限界に非常に近接して大きいイレギュラーＬＤＰＣ符号を復号するように用いることができるため十分に最適に近い。
【００９４】
最近では、適切なＬＤＰＣ符号を作成するために多くの方法が探求されてきた。文献の導入的概説として、T. RichardsonおよびR. Urbanke著、「The Renaissance of Gallager's Low-Density Parity Check Codes」、IEEE Communications Magazine、pp. 126-131、August 2003を参照のこと。
【００９５】
ファクターグラフ
図３に示すように、符号を、「ファクターグラフ（factor graph）」と呼ばれる２部グラフ３００によって表すことができる。F.R. Kschischang、B.J. FreyおよびH.-A. Loeliger著、「Factor Graphs and the Sum-Product Algorithm」、IEEE Transactions on Information Theory、vol. 47、pp. 498-519、February 2001と、G.D. Forney, Jr.著、「Codes on Graphs: Normal Realizations」、IEEE Transactions on Information Theory、vol. 47、pp. 520-549、February 2001と、R.M. Tanner著、「A Recursive Approach to Low-Complexity Codes」、IEEE Transactions on Information Theory、vol. 27、pp. 533-547、September 1981と、を参照のこと。
【００９６】
ファクターグラフは、「変数ノード（variable nodes）」と「ファクターノード（factor nodes）」と呼ばれる２つのタイプのノードを含む２部グラフである。変数ノード３０２は、ファクターノード３０１のみに接続され、その逆でもある。ファクターノードは、慣用的に正方形３０１を使用して描かれ、変数ノードは、慣用的に円３０２を使用して描かれ、変数ノードとファクターノードとの間の接続は、対応する円と正方形とを接続する線３０３によって示される。時に、ファクターノード内に、それが強制する制約の種類を表すために、シンボル、すなわち「＋」が描かれる。
【００９７】
変数ノードは、符号で使用されるシンボルを表し、ファクターノードは、符号に対する制約を表す。変数ノードは、対応する制約を受ける場合にのみファクターノードに接続される。
【００９８】
もっとも単純な符号のファクターグラフ表現は、パリティ検査行列表現に対応するものである。かかるファクターグラフでは、パリティ検査行列のＮ列に対応するＮ個の変数ノードがあり、パリティ検査行列のＭ行に対応するＭ個のファクターノードがある。たとえば、パリティ検査行列
【００９９】
【数１０】
2005110251.tif 000012
【０１００】
を有するバイナリ符号は、図３に示す対応するファクターグラフ表現を有する。このファクターグラフ表現において、変数ノードは、符号語のＮ個のシンボルに対応するもののみであり、ファクターノードはすべてパリティ検査制約に対応する。
【０１０１】
符号のより一般的なファクターグラフ表現が可能である。特に、変数ノードのセットは、時に、符号の定義に役立つが符号語のＮ個のシンボルのうちの１つではない「状態変数ノード（state variable node）」と呼ばれるノードも含む。
【０１０２】
時に、ファクターノードはまた、パリティ検査制約より一般的な制約を表す。たとえば、ファクターノードは、それに接続する変数ノードの許容可能な構成が何らかの小さい符号の符号語に対応するもののみであるように、制約を表すことができる。このように、大きい符号を小さい符号から再帰的に構築することができる。R.M. Tanner著、「A Recursive Approach to Low-Complexity Codes」、IEEE Transactions on Information Theory、vol. 27、pp. 533-547、September 1981を参照のこと。
【０１０３】
符号のスパーズ生成素ファクターグラフ表現
各ファクターノードが比較的少ない数の変数ノードにのみ接続されおよびその逆である場合、符号のファクターグラフ表現を「スパーズ（sparse）：まばら」と呼ぶ。
【０１０４】
ＬＤＰＣ符号のパリティ検査行列に対応するファクターグラフは、ＬＤＰＣ符号のパリティ検査行列の低密度特性のために本質的にスパーズである。
【０１０５】
また、時に、スパーズ生成素ファクターグラフ（sparse generator factor graph）表現により他の線形符号を表すことも可能である。たとえば、スパーズなファクターグラフにより、有限幾何学に基づくリード・マラー（Reed-Muller）符号および他の符号を表すことができる。G.D. Forney, Jr.著、「Codes on Graphs: Normal Realizations」、IEEE Transactions on Information Theory、vol. 47、pp.520-549、February 2001およびJ.S. Yedidia、J. ChenおよびM. Fossorier著、「Representing Codes for Belief Propagation Decoding」、Proceedings of the International Symposium on Information Theory、p. 176、2003を参照のこと。
【０１０６】
確率伝播復号
しばしば、スパーズファクターグラフによって表すことができる符号に対し、確率伝播復号方法を有効に適用することができる。確率伝播復号方法は、非最適な軟入力復号方法であるが、非最適性の程度は、符号のスパーズファクターグラフ表現に適用する場合は概して極めて小さい。
【０１０７】
確率伝播復号器には多くの異なるバージョンがある。F.R. Kschischang、B.J. FreyおよびH.-A. Loeliger著、「Factor Graphs and the Sum-Product Algorithm」、IEEE Transactions on Information Theory、vol. 47、pp.498-519、February 2001、およびSpecial Issue on Codes and Graphs and Iterative Algorithms、IEEE Transactions on Information Theory、vol. 47、February 2001における他の論文を参照のこと。「一般化された確率伝播（generalized belief propagation）」に基づく復号器もある。J.S. Yedidia、W.T. FreemanおよびY. Weiss著、「Constructing Free Energy Approximations and Generalized Belief Propagation Algorithms」、Mitsubishi Electric Research Laboratories、TR2002-35、August 2002を参照のこと。
【０１０８】
それら復号器はすべて、「メッセージ（message）」が変数ノードとファクターノードとの間を通るという概念に基づく。時に「証拠（evidence）」とも呼ばれる、符号のコスト関数に対応する特別な種類のメッセージもまた、各変数ノードに送出される。変数ノードは、指定されかつ事前に求められた更新規則に基づき、ノードがファクターノードに送出するメッセージを連続的に更新し、またその逆もまた同様である。更新規則は、ノードまたはノード群における出力メッセージを同じノードまたはノード群における入力メッセージに関連付ける。
【０１０９】
そして、変数ノードがそのあり得る状態のうちの１つにあるという「ビリーフ（belief）」を、その変数ノードに到達したメッセージと証拠とから求めることができる。「ビリーフ」は、通常、ｑ元ベクトルとして表される。ベクトルは、変数ノードのｑ個のあり得る値の各々が正しいものであるという推定された確率を含む。復号器は、最終的に、ビリーフが最高確率を有するシンボル値を選び取ることにより、各シンボルの状態を選択する。
【０１１０】
通信路符号化と量子化問題との二重関係
意外なことに、通信路符号化問題と量子化および再生問題とは、互いに非常に密接に関連する。たとえば、ＢＥＱ問題とＢＥＣモデルとが非常に類似していることは特筆すべきことであり、量子化問題に対する量子化器の最適レートは、通信路符号化問題に対する符号の最適レートと同一である。
【発明の開示】
【発明が解決しようとする課題】
【０１１１】
しかしながら、今まで、ＬＤＰＣ符号を使用して通信路符号化問題に対し最適な限界に近づくように、量子化および再生問題に対する最適限界に近づくことができる既知の方法はない。
【課題を解決するための手段】
【０１１２】
本発明は、Ｎ個のサンプルの入力信号をｑ元アルファベットから引き出されるｋ個のシンボルのストリングに量子化する方法を提供する。さらに、本発明は、量子化ストリングから入力信号を再生し、その再生の出力信号の入力信号に対する歪みが最小であるようにする、対応する方法を提供する。
【０１１３】
初期化中、以下の要素を選択する。
【０１１４】
量子化および再生方法に対する［Ｎ，ｋ］ｑ符号を選択する。符号は、スパーズ生成素ファクターグラフ（ＳＧＦＧ）表現を有する。したがって、選択された符号を、スパーズ生成素ファクターグラフ（ＳＧＦＧ）符号と呼ぶ。
【０１１５】
ｑ元シンボルをサンプル値にマッピングする固定関数を選択する。
【０１１６】
ＳＧＦＧ符号に対する軟入力復号方法を選択する。好ましい復号器は、確率伝播を使用する。しかしながら、他の復号器も可能である。
【０１１７】
ＳＧＦＧ符号に対する符号化方法を選択する。
【０１１８】
そして、量子化器は、入力信号を以下のように処理する。
【０１１９】
入力信号と、所定の歪み測度と、ｑ元シンボルをサンプル値にマッピングする関数と、から、コスト関数を求める。
【０１２０】
コスト関数を、低コストの符号語に復号する。そして、ｋ個のシンボルの対応する情報ブロックを生成するように、符号語の情報ブロックを選択する。
【０１２１】
再生方法は、ＳＧＦＧ符号に対する選択された符号器に基づく。量子化信号の再生が望まれる場合、まず量子化ストリングを、符号器を使用して対応する符号語に変換する。そして、ｑ元シンボルをサンプル値にマッピングする関数を使用して、符号語をＮ個のシンボルの出力信号に変換する。
【０１２２】
再生出力信号は、入力信号と実質的に同様である。
【発明を実施するための最良の形態】
【０１２３】
図４は、本発明による初期化手続き４００のステップを示す。図５は、本発明による量子化および再生方法のステップを示す。新規な特徴として、本方法は、スパーズ生成素ファクターグラフ符号を使用する。
【０１２４】
パラメータ
入力信号５０１は、Ｎ個のサンプルを含む。入力信号を、ｑ元アルファベットから選択されるｋ個のシンボルのストリングに量子化したいものとする。再生出力信号もまたＮ個のサンプルを有する。入力信号と再生出力信号との間の歪み測度は既知であり、式（１）の形態を有する。
【０１２５】
本発明の好ましい実施の形態では、Ｎは大きい数であり、およそ１０００以上である。この実施の形態を処理しやすくするために、より小さいＮでの実施の形態を用いる。Ｎに対する大きい値が望ましい理由は、ブロック長の大きい量子化器が、上述した最適なシャノンレート・歪み限界に近づくことができるからである。重要な点は、通信路符号化問題に対し最適な限界に近づくために、大きいブロック長の符号を使用し、同様に、量子化および再生問題の最適な限界に達するために、長い信号を量子化する量子化器を使用する、ということである。
【０１２６】
スパーズ生成素ファクターグラフ表現を用いる符号の選択
スパーズ生成素ファクターグラフ（ＳＧＦＧ）表現により［Ｎ，ｋ］ｑ符号４１１を選択する４１０ことにより、初期化を開始する。
【０１２７】
意味することを明らかにするために、まず、符号に対する「生成素ファクターグラフ（generator factor graph）」を定義する。［Ｎ，ｋ］ｑ符号に対する生成素ファクターグラフは、以下の条件を満足するファクターグラフである。第１に、生成素ファクターグラフは、少なくともＮ個の変数ノードを含み、それにより変数ノードのうちのＮ個が、符号語を定義するために使用されるシンボルに対応する。第２に、ｋ個の変数ノードは、符号に対する情報ブロックに対応する。第３に、情報ブロックに対応するｋ個の変数ノードの値が指定されると、符号語に対応するＮ個の変数ノードの値を一意に求めることができる。スパーズ生成素ファクターグラフは、同じくスパーズな生成素ファクターグラフである。スパーズ生成素ファクターグラフによって表される符号をスパーズ生成素ファクターグラフ（ＳＧＦＧ）符号４１１と呼ぶ。
【０１２８】
ＳＧＦＧ表現を有する符号の一実施例は、低密度パリティ検査（ＬＤＰＣ）符号に対して二重の符号である。かかる符号は低密度生成素行列を有するため、低密度生成素行列（ＬＤＧＭ）符号と呼ぶ。
【０１２９】
［Ｎ，ｋ］ｑＬＤＧＭ符号は、生成素行列表現を有し、生成素行列はＮ列およびＭ行を有し、そのうちのｋ行は線形独立である。ｑ元アルファベットから生成素行列のシンボルを選択し、それを、上述したようにガロア体ＧＦ（ｑ）の規則に従って操作する。
【０１３０】
ＬＤＧＭ符号の生成素行列の各行は、少数、典型的にはおよそ１０以下の非ゼロシンボルを有する。生成素行列を、ＬＤＰＣ符号に対しパリティ検査行列を形成するために文献において既知である多くの方法のうちのいずれかを使用して形成する。
【０１３１】
図６は、ＬＤＧＭ符号に対応する一例としてのスパーズ生成素ファクターグラフ６００を示す。以下の生成素行列を有する［Ｎ＝３，ｋ＝２］ｑ＝２符号を考慮する。
【０１３２】
【数１１】
2005110251.tif 000013
【０１３３】
式（５）に従って情報ブロックｓ［ａ］から符号語ｘ［ｎ］が求められる、ということを想起する。結果としての制約を明示的に書き出すことにより、
【０１３４】
【数１２】
2005110251.tif 000014
【０１３５】
となる。ＧＦ（２）を使用する場合、これらの制約を次のように書くことができる。
【０１３６】
【数１３】
2005110251.tif 000015
【０１３７】
これらの制約を、図６のファクターグラフに表す。なお、情報ブロックに対応する変数ノードｓ［１］およびｓ［２］が指定された後に、符号語に対応する変数ノードｘ［１］、ｘ［２］およびｘ［３］が一意に求められるため、これは生成素ファクターグラフである。
【０１３８】
概して、［Ｎ，ｋ］ＬＤＧＭ符号に対し、Ｎ＋ｋ変数、すなわちＮ個の符号語変数とｋ個の情報シンボル変数とに対するＮ個の制約式を求める。
【０１３９】
ＬＤＧＭ符号は、常に、生成素ファクターグラフ表現を有し、生成素ファクターグラフは、ＬＤＧＭ符号の生成素行列の低密度特性のために常にスパーズである。したがって、ＬＤＧＭ符号は、常にＳＧＦＧ符号である。
【０１４０】
ＬＤＧＭ符号のスパーズ生成素ファクターグラフ表現は、いかなる状態変数も含まないが、状態変数を含むスパーズ生成素ファクターグラフにより、リード・マラー符号等の他の符号を表すことができる。量子化問題によっては、状態変数を含むＳＧＦＧ表現を有するＳＧＦＧ符号がより使用に適当である場合がある。
【０１４１】
シンボルをサンプル値にマッピングする固定関数の選択
次に、シンボルをサンプルにマッピングする固定関数４２１を選択する４２０。この関数をｙ＝Ｙ（ａ）として書く。ここで、ａはシンボルであり、ｙは対応するサンプルであり、Ｙ（ａ）は選択された固定マッピング関数４２１である。
【０１４２】
たとえば、ｑ＝４であり入力信号５０１のサンプルが０．０と１．０との間に分散する実数である場合、１つのあり得る関数は、Ｙ（‘０’）＝．１２５、Ｙ（‘１’）＝．３７５、Ｙ（‘２’）＝．６２５、Ｙ（‘３’）＝．８７５である。
【０１４３】
最良の関数は、歪み測度４１９と入力信号の確率分布４１８とによって決まる。多くの場合、適切な選択は、いかなるサンプルもそのサンプルがマッピングされるシンボルの値から遠すぎない値を有するように、サンプルのあり得る値の範囲を比較的均一に分割することである。信号に対する入力確率分布または歪み測度が非対称である場合、他の関数がより適当である場合がある。
【０１４４】
マッピング関数の別の例として、ＢＥＱ問題に対し、サンプルが３つの値「０」、「１」および「＊」をとりシンボルが値「０」および「１」をとる場合、単純に、シンボル「０」をサンプル値「０」にマッピングし、シンボル「１」をサンプル値「１」にマッピングする。このマッピングを、ＢＥＱに対する「標準（standard）」マッピング関数と呼ぶ。
【０１４５】
ＳＧＦＧ符号に対する復号方法の選択
次に、選択されたＳＧＦＧ符号４１１に対し軟入力復号方法４３１を選択する４３０。
【０１４６】
最適な軟入力復号方法が実際的である場合、それを使用することができる。１つの最適な軟入力復号方法は、すべてのあり得る符号語をチェックし最低コストを有するものを選択する。
【０１４７】
多くの実際的な適用では、ＳＧＦＧ符号Ｎは非常に大きく、符号語の数は最適な復号器には大きすぎる。したがって、非最適な軟入力復号器を使用する。
【０１４８】
復号器の複雑性とそれが生成する符号語のコストとのトレードオフに応じて、いくつかの異なる非最適な軟入力復号器が可能である。たとえば、ビット反転復号器は通常それほど複雑ではない。しかしながら、確率伝播復号器が、通常、より低いコストを有する符号語を出力する。
【０１４９】
ＳＧＦＧ符号に対する符号化方法の選択
次に、入力信号を再生することが望まれる場合、ＳＧＦＧ符号４１１に対して符号器４４１を選択する４４０。これを行う１つの方法は、符号に対して生成素行列を求め、その後式（５）を使用して情報ブロックを符号語に変換する、というものである。
【０１５０】
生成素ファクターグラフの定義のために、常に、スパーズ生成素ファクターグラフ自体をあるバージョンの既知の確率伝播方法と結合して使用することにより、ＳＧＦＧ符号４１１に対して符号器４４１を生成することが可能である。これを、ノードが完全に確実である時にのみメッセージを送出する確率伝播方法のバージョンを使用して行うことができる。かかる確率伝播方法を、「ハード（hard）」メッセージを使用する確率伝播方法と呼ぶ。
【０１５１】
スパーズ生成素ファクターグラフとハードメッセージを使用する確率伝播方法とを使用して符号器を生成するために、情報ブロックシンボルのシンボルに対応する変数ノードをそれらの所望の状態に設定することにより開始する。そして、これらのノードは、メッセージをそれらの状態に関する接続されたファクターノードに送出し、それらのメッセージはファクターノードによって処理される。そして、ファクターノードは、状態がまだ求められていない他の変数ノードにメッセージを送出する。それらの状態を、状態がすでに既知であるノードから求めることができる。確率伝播を、所望の符号語に対応する変数を含むファクターグラフのすべての変数ノードが求められるまで繰り返す。
【０１５２】
量子化および再生方法の一般的な機能
上記選択を実行した後、図５に示すように信号を量子化し再生することができる。
【０１５３】
本発明の基本的な概念は、量子化に対しＳＧＦＧ符号４１１のための復号器４３１を使用し、再生に対しＳＧＦＧ符号４１１のための符号器４４１を使用する、ということである。
【０１５４】
入力信号のための歪みコスト関数を求める
入力信号ｘ［ｎ］５０１を量子化する第１のステップにおいて、入力信号５０１と、シンボルをサンプル値にマッピングする固定マッピング関数４２１と、既知の歪み測度４１９と、を使用して、軟入力コスト関数５１１を求める５１０。
【０１５５】
コスト関数５１１を、入力信号ｘ［ｎ］５０１のＮ個のサンプルすべてに対しサンプル毎に求める。入力信号ｘ［ｎ］の各サンプルに対し、あり得るシンボル値ａ各々に対して、ａから取得されるマッピングされたサンプル値ｙ＝Ｙ（ａ）のｘ［ｎ］に関する歪みコストを測定することにより、歪みコストを求める。
【０１５６】
例として、ここでは二元消失量子化適用を扱っており、信号｛１，＊，１，０｝を量子化したいとする。式（２）で与えられるＢＥＱ問題に対する歪み関数を、上述したＢＥＱに対するシンボルとサンプル値との間の標準固定マッピング４２１とともに使用する。入力信号から、シンボル「０」を第１のビットに割り当てるコストは１／４であり、シンボル「１」を第１のビットに割り当てるコストは０であると求められる。同様にいずれのシンボルを第２のビットに割り当てるコストも０である。この実施例での全歪みコスト関数は、この入力信号が与えられると、［（１／４，０），（０，０），（１／４，０），（０，１／４）］である。
【０１５７】
軟入力復号器の適用
［Ｎ，ｋ］ｑＳＧＦＧ符号４１１に対し歪みコスト関数５１１と軟入力復号器４３１とが与えられると、ここで、コスト関数５１１を、符号４１１の低コスト符号語に対応する情報ブロック５３１に復号する５２０。復号器４３１が最適である場合、最低コストの符号語に対応する情報ブロックを復号する。情報ブロックは、必要に応じてｑ元アルファベットから選択されるｋ個のシンボルを含む。この情報ブロックは、量子化器５００の出力である。
【０１５８】
実施例として、本量子化問題は、ＢＥＱ量子化問題であり、Ｎ＝４、ｋ＝２およびｑ＝２であるものとする。生成素行列
【０１５９】
【数１４】
2005110251.tif 000016
【０１６０】
を有する［Ｎ＝４，ｋ＝２］ｑ＝２ＳＧＦＧ符号４１１を使用し、使用される復号方法は最適な復号である。
【０１６１】
入力信号｛１，＊，１，０｝が［（１／４，０），（０，０），（１／４，０），（０，１／４）］の歪みコスト関数に変換される場合、選択される符号は、４つの符号語、すなわち００００、０１０１、１０１０および１１１１を有する。符号語は、それぞれ４つの情報ブロック００、０１、１０および１１に対応する。
【０１６２】
歪みコスト関数を使用することにより、４つの符号語のコストは、それぞれ２／４、３／４、０および１／４である。このため、最適な復号器は、０の歪みコストを有する、符号語１０１０に対応する情報ブロック１０に復号する。したがって、この誤り訂正符号と最適な復号器とを使用する量子化器は、入力信号｛１，＊，１，０｝を情報ブロック１０に量子化する。
【０１６３】
非最適軟入力復号器
Ｎが、最適な復号器を使用することができないほど大きい場合、代わりに非最適な復号器を使用する。任意の非最適復号器の１つの重要な要件は、復号器が、何らかの符号語に対応する情報ブロックを、その符号語が最低コスト符号語でない場合であっても常に出力する、ということである。障害状態は許容可能ではない。
【０１６４】
非最適な復号器は、低コスト符号語を、それが最低コスト符号語でない場合であっても確実に出力することが好ましい。ここで、この特性を有するビット反転復号器と確率伝播復号器とを論考する。
【０１６５】
ビット反転復号器
低コスト符号語を確実に出力する、比較的単純な種類の復号器は、ビット反転復号器である。使用することができる多くのあり得るビット反転復号器がある。一例として、「ゼロ温度ビット反転復号器（zero-temperature bit-flipping decoder）」と呼ぶ以下のビット反転復号器を考慮する。
【０１６６】
復号器を、「仮（provisional）」情報ブロックｔ［ａ］で初期化する。情報ブロックに対応する符号語ｙ［ｎ］を、ＳＧＦＧ符号に対する符号器を使用することによって取得することができる。各符号語は、歪みコスト関数を使用して求めることができるコストを有する。初期符号語のコストを、変数ｃに記憶する。
【０１６７】
各繰り返しにおいて、ゼロ温度ビット反転復号器は、仮情報ブロックにおける情報シンボルをランダムに選択し、そのシンボルを、同様にランダムに選択される別の情報シンボルに「反転させる（flip）」ように試みる。新たに取得された情報ブロックに対応する符号語のコストがｃより低い場合、反転を受け入れ、仮情報ブロックｔ［ａ］を更新し、コストｃを、ｔ［ａ］の新たな状態に対応する符号語のコストに更新する。一方、新たに取得された符号語のコストがｃより大きい場合、反転を拒否する。
【０１６８】
そして、復号器は繰り返し、別の情報シンボルを選択してランダムに反転させるように試みる。復号器は、いかなる情報シンボルも反転させることに成功せずに所定数繰り返した後に終了し、情報ブロックｔ［ａ］を出力する。
【０１６９】
確率伝播復号器
ＳＧＦＧ符号はスパーズファクターグラフ表現を有するため、軟入力復号器として確率伝播復号器を有効に使用することも可能である。
【０１７０】
符号の他のファクターグラフ表現とは対照的に生成素ファクターグラフの１つの重要な利点は、それらによって情報ブロックの状態として確率伝播復号器のいかなる所与の状態も迅速に解釈することができる、ということである。特に、情報ブロックの状態を求めるために情報ブロックに対応する変数ノードにおけるビリーフを見るだけでよい。
【０１７１】
再生方法
入力信号を再生するために、ｋ個のシンボル５３１のストリングｓ［ａ］をＮ個のサンプルの出力信号ｚ［ｎ］５０９に変換する必要があることを想起する。
【０１７２】
［Ｎ，ｋ］ｑＳＧＦＧ誤り訂正符号４１１に対する符号器４４１を使用することにより、ストリングｓ［ａ］５３１を符号語ｙ［ｎ］５４１に変換することができる。そして、上述したように、あり得るｑ元シンボルの各々を固定関数４２１に従って異なるサンプル値に割り当てることにより、符号語ｙ［ｎ］５４１を所望の出力信号ｚ［ｎ］５０９に変換することができ、それは、入力信号５０１と実質的に同様である。
【０１７３】
たとえば、入力信号は、０．０から１．０の範囲の実数の形態の４つのサンプルを有する。入力信号を、各々が２ビットであるシンボルのストリングに量子化する。例示の目的で、生成素行列
【０１７４】
【数１５】
2005110251.tif 000017
【０１７５】
を有する［Ｎ＝４，ｋ＝２］ｑ＝２ＳＧＦＧ符号を使用し、量子化ストリング｛１，０｝で開始するものとする。符号器は、入力ストリングを符号語｛１，０，１，０｝に変換する。そして、「０」シンボルを値．２５を有するサンプルに変換し「１」シンボルを値．７５を有するサンプルに変換するという規則を適用する場合、再生出力信号は｛．７５，．２５，．７５，．２５｝である。
【０１７６】
発明の効果
ＢＥＱ問題に対し、推奨される手法は、ＢＥＣ通信路符号化に対して有効なＬＤＰＣ符号に対し二重のＬＤＧＭ符号を使用することである。ＬＤＰＣ符号に対する確率伝播復号器がＢＥＣ通信路符号化問題に対し大きいＮ限界におけるシャノン限界に達する場合、量子化器として使用される二重符号に対する確率伝播復号器もまた、ＢＥＱ問題に対しシャノン限界に達する。
【０１７７】
経験的シミュレーションがこの結果を裏づけする。すなわち、レート１／２で長い符号を使用するほど、ゼロ歪みで５０％消失の限界により近づくように量子化することができる。
【０１７８】
ビット反転復号器もまた有効である。たとえば、ＢＳＱ問題に対し、ビット反転復号器とともに長さ１０００のレート１／２のレギュラーＬＤＧＭ符号を使用することにより、．１１という理論的限界に比較して．１４という歪みレベルで量子化することができる。
【０１７９】
本発明を好ましい実施形態の実施例として説明したが、発明の精神および範囲内でさまざまな他の適応および変更を行ってもよい、ということを理解しなければならない。したがって、本発明の真の精神および範囲内にあるかかる変形および変更のすべてを包含することが、添付の特許請求項の目的である。
【図面の簡単な説明】
【０１８０】
【図１】従来技術による量子化および再生方法のブロック図である。
【図２】従来技術による通信路符号化方法のブロック図である。
【図３】パリティ検査行列に対応する従来技術によるファクターグラフである。
【図４】本発明による初期化手続きのフローチャートである。
【図５】本発明による量子化手続きのフローチャートである。
【図６】本発明によって使用されるスパーズ生成素ファクターグラフである。
【図１】
2005110251.tif 000018
【図２】
2005110251.tif 000019
【図３】
2005110251.tif 000020
【図４】
2005110251.tif 000021
【図５】
2005110251.tif 000022
【図６】
2005110251.tif 000023
【外国語明細書】
2005110251.tif 000024
2005110251.tif 000025
2005110251.tif 000026
2005110251.tif 000027
2005110251.tif 000028
2005110251.tif 000029
2005110251.tif 000030
2005110251.tif 000031
2005110251.tif 000032
2005110251.tif 000033
2005110251.tif 000034
2005110251.tif 000035
2005110251.tif 000036
2005110251.tif 000037
2005110251.tif 000038
2005110251.tif 000039
2005110251.tif 000040
2005110251.tif 000041
2005110251.tif 000042
2005110251.tif 000043
2005110251.tif 000044
2005110251.tif 000045
2005110251.tif 000046
2005110251.tif 000047
2005110251.tif 000048
2005110251.tif 000049
2005110251.tif 000050
2005110251.tif 000051
2005110251.tif 000052
2005110251.tif 000053
2005110251.tif 000054
2005110251.tif 000055
2005110251.tif 000056
2005110251.tif 000057
2005110251.tif 000058
2005110251.tif 000059
2005110251.tif 000060
2005110251.tif 000061
2005110251.tif 000062
2005110251.tif 000063
2005110251.tif 000064
2005110251.tif 000065
2005110251.tif 000066
2005110251.tif 000067
2005110251.tif 000068
2005110251.tif 000069
2005110251.tif 000070