(57)【特許請求の範囲】
【請求項１】
送信対象である情報を符号化した符号語を生成して雑音を有する通信路に入力し、前記通信路から出力された前記符号語である出力符号語を復号化した復号語を生成して前記情報を受信する情報送受信方法であって、
第一の疎行列と第二の疎行列とをそれぞれ生成する疎行列生成工程と、
前記通信路に入力される前記符号語の出現確率の分布である入力確率分布を第一の記憶部に記憶する入力確率分布記憶工程と、
前記通信路を模した確率分布として、前記符号語が入力された際に前記出力符号語が出力される条件付確率分布を第二の記憶部に記憶する条件付確率分布記憶工程と、
前記情報に対して、前記疎行列生成工程によって生成された前記第一の疎行列との積が零行列となり、かつ前記疎行列生成工程によって生成された前記第二の疎行列との積が前記情報となる前記符号語の候補の中で、前記第一の記憶部が記憶する前記入力確率分布が最大となるものを最適化アルゴリズムによって選択し、当該選択された候補を当該情報の前記符号語として生成する符号語生成工程と、
前記出力符号語に対して、前記疎行列生成工程によって生成された前記第一の疎行列との積が零行列となる前記符号語の候補の中で、自身が前記通信路に入力された場合、前記第一の記憶部が記憶する前記入力確率分布と前記第二の記憶部が記憶する前記条件付確率分布とを用いて算出される当該出力符号語が出力される確率が最大となるものを最適化アルゴリズムによって選択し、当該選択された候補と前記疎行列生成工程によって生成された前記第二の疎行列との積を、当該出力符号語の前記復号語として生成する復号語生成工程と、
を含んだことを特徴とする情報送受信方法。
【請求項２】
送信対象である情報を符号化した符号語を生成して雑音を有する通信路に入力する符号化装置であって、
第一の疎行列と第二の疎行列とをそれぞれ生成する疎行列生成手段と、
前記通信路に入力される前記符号語として出現する確率の分布である入力確率分布を記憶する入力確率分布記憶手段と、
前記情報に対して、前記疎行列生成手段によって生成された前記第一の疎行列との積が零行列となり、かつ前記疎行列生成手段によって生成された前記第二の疎行列との積が前記情報となる前記符号語の候補の中で、前記入力確率分布記憶手段が記憶する前記入力確率分布が最大となるものを最適化アルゴリズムによって選択し、当該選択された候補を当該情報の前記符号語として生成する符号語生成手段と、
を備えたことを特徴とする符号化装置。
【請求項３】
送信対象である情報を符号化した符号語が雑音を有する通信路に入力された後に、当該通信路から出力された前記符号語である出力符号語を復号化した復号語を生成して前記情報を受信する復号化装置であって、
第一の疎行列と第二の疎行列とをそれぞれ生成する疎行列生成手段と、
前記通信路に入力される前記符号語として出現する確率の分布である入力確率分布を記憶する入力確率分布記憶手段と、
前記通信路を模した確率分布として、前記符号語が入力された際に前記出力符号語が出力される条件付確率分布を記憶する条件付確率分布記憶手段と、
前記出力符号語に対して、前記疎行列生成手段によって生成された前記第一の疎行列との積が零行列となる前記符号語の候補の中で、自身が前記通信路に入力された場合、前記入力確率分布記憶手段が記憶する前記入力確率分布と前記条件付確率分布記憶手段が記憶する前記条件付確率分布とを用いて算出される当該出力符号語が出力される確率が最大となるものを最適化アルゴリズムによって選択し、当該選択された候補と前記疎行列生成手段によって生成された前記第二の疎行列との積を、当該出力符号語の前記復号語として生成する復号語生成手段と、
を備えたことを特徴とする復号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報送受信方法、符号化装置および復号化装置に関する。
【背景技術】
【０００２】
従来より、雑音を有する通信路を介した情報伝達においては、通信路で発生する誤りを訂正する仕組みを情報に付加した符号語を生成して通信路に入力し、通信路から出力された符号語を、付加された仕組みを用いて復号することで、雑音により発生する情報の誤りを訂正して信頼性の高い情報伝達を実現する通信路符号化が行なわれている。すなわち、雑音を有する通信路における通信路符号化においては、符号器によって「情報ビット」に「誤り訂正のためのビット」を付加した符号語を生成し、通信路から出力された符号語を、復号器が「誤り訂正のためのビット」を用いて復号することで誤り訂正処理を行なっている。
【０００３】
ここで、雑音を有する通信路における通信路符号化においては、以下の３つの課題がある。
【０００４】
第１の課題は、「必ずしも加法的雑音とは限らない一般の雑音を有する通信路に対しても適用でき、復号誤りを任意に小さくすること」である。ここで、加法的雑音を有する通信路とは、例えば、「０」および「１」から構成される情報が通信路から出力された場合、「０」が「１」として誤って出力される確率、および「１」が「０」として誤って出力される確率が固定値である２元対称通信路（Ｂｉｎａｒｙ  Ｓｙｍｍｅｔｒｉｃ  Ｃｈａｎｎｅｌ）のようにモデル化された通信路のことであり、一般の雑音を有する通信路とは、「０」が「１」として誤って出力される確率、および「１」が「０」として誤って出力される確率が情報伝達ごとに変動する通信路のことである。すなわち、第１の課題は、このような一般の雑音を有する通信路においても、復号誤りを任意に小さくすることができる情報の符号化および復号を可能にする通信路符号化を達成することである。
【０００５】
第２の課題は、「通信路容量に近い伝送レート（符号化レート）で符号化できること」である。ここで、通信路容量とは、通信路が誤りなく伝送できる情報の最大量のことである。また、伝送レート（符号化レート）とは、「情報ビット数」に対する「誤り訂正符号化後のビット数」の比であり、例えば、伝送レート（符号化レート）が「８／９」とは、８ビットの「情報ビット」に対して、１ビットの「誤り訂正のためのビット」を付加して、９ビットの符号語を生成することを意味する。すなわち、第２の課題は、通信路が誤りなく伝送できる情報の最大量の限界近くまで、「誤り訂正のためのビット」を付加する情報の符号化を可能にする通信路符号化を達成することである。
【０００６】
第３の課題は、「符号化および復号化が効率的に実時間で実行可能とすること」である。具体的には、線形符号によって情報を符号化する際に用いられる多項式のオーダーが、１乗から３乗のオーダーに収まるようにすることで、情報伝達における符号器および復号器の計算処理を少なくして、情報伝達にかかる時間を短くすることを可能にする通信路符号化を達成することである。
【０００７】
これら３つの課題を部分的に解決する通信路符号は、数多く存在するが、代表的なものとしては、以下のものが挙げられる。
【０００８】
第１の課題および第２の課題を解決する通信路符号としては、ランダム符号化によって構成されるタイプ一定符号（ユニバーサル符号）が知られており（非特許文献１参照）、また、第１の課題および第３の課題を解決する通信路符号としては、ブロック符号であるリードソロモン符号（Ｒｅａｄ−Ｓｏｌｏｍｏｎ  Ｃｏｄｉｎｇ）が知られている（非特許文献２参照）。
【０００９】
また、第２の課題および第３の課題を解決する通信路符号としては、リードソロモン符号と同じくブロック符号であり、ｓｕｍ−ｐｒｏｄｕｃｔ法などの効率的な最適化アルゴリズムによる復号ができる低密度パリティ検査符号（ＬＤＰＣ符号、ＬＤＰＣ：Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）が知られている（非特許文献３および非特許文献４参照）。ここで、ＬＤＰＣ符号は、非常に疎な疎行列であるパリティ検査行列（低密度パリティ検査行列：ＬＤＰＣ行列）により定義される線形ブロック符号であり、通信路符号のみならず、情報源を符号化によって圧縮する情報源符号化においても、有用な手法として知られている（非特許文献５参照）。
【００１０】
また、ＬＤＰＣ符号に量子化手法を組み合わせることにより、第１の課題も解決する可能性のあることが、理論的な観点から考察されている（非特許文献６参照）。
【００１１】
また、ＬＤＰＣ符号と同様な特性を有する通信路符号としては、畳み込み符号であるターボ符号が知られている（非特許文献７参照）。
【００１２】
【非特許文献１】植松友彦著、「現代シャノン理論―タイプによる情報理論」、培風館、１９９８年７月、ｐ６４−７７
【非特許文献２】平澤茂一、西島利尚著、「符号理論入門」、培風館、１９９９年１１月、ｐ１０１−１０７
【非特許文献３】和田山正著、「低密度パリティ検査符号とその復号法」、トリケップス社、２００２年６月、ｐ２３−４２、ｐ６５−９９
【非特許文献４】D. J. C. MacKay, “Good error-correcting codes based on very separate matrices.”, IEEE Transactions on Information Theory, Vol. IT-45, No. 2, pp.399-431, 1999
【非特許文献５】S. Miyake and J. Muramatsu, “Construction of a lossy source code using LDPC matrices.”, 信学技報, Vol. IT2006-51, pp.7-12, 2007
【非特許文献６】A. Bennatan and D. Burshtein, “On the application of LDPC codes to arbitrary discrete-memoryless-channels.”, IEEE Transactions on Information Theory, Vol. IT-50, No. 3, pp.417-438, 2004
【非特許文献７】C. Berrou and A. Glavieux, “Near optimum error correcting coding and decoding: Turbo-Codes.”, IEEE Transactions on Communications, Vol. COM-44, No. 10, pp.1261-1271, 1996
【発明の開示】
【発明が解決しようとする課題】
【００１３】
ところで、上記した従来の通信路符号は、第１の課題、第２の課題および第３の課題のすべてを実用運用面において解決するものではない。
【００１４】
すなわち、上記した従来のタイプ一定符号は、ランダム符号化によって構成されるものであるとともに、復号法に最尤推定や相互情報量最大推定を用いるため、効率的な復号が行なえないため、第３の課題を解決することができない。
【００１５】
また、上記した従来のリードソロモン符号は、ｓｉｎｇｌｔｏｎ  ｂｏｕｎｄ（限界）を満足する最大距離分離符号であり、復号時の誤り確率を限りなく「０」に近い値にするためにはブロック長を大きくすることとなり、必然的に伝送レートは漸近的に「０」に近づいていくため、第２の課題を解決することができない。また、リードソロモン符号と畳み込み符号とを組み合わせるなど、既存の符号同士を組み合わせることで、伝送レートの効率化と符号器および復号器による計算の効率化とを同時に実現する構成を実現する試みが数多くなされてきたが、応用的な面からは、あまり不自由なく利用できるようになっているものの、通信路容量に近い伝送レートで情報を送信できるとともに、復号時の誤り確率を限りなく「０」に近い値にすることができるシャノン限界に達することができるものは、依然として構成されていない。
【００１６】
また、上記した従来のＬＤＰＣ符号は、シャノン限界を達成する可能性を持つとされているが、線形符号をベースとしているので、その有効性は、加法的雑音下の通信路に限られているため、第１の課題を解決することができない。
【００１７】
また、上記した従来のＬＤＰＣ符号に量子化手法を組み合わせた方法は、漸近的に大きくする量が、ブロック長のみならず、符号器の量子化パラメータも含むため、現実的な符号器として実装には困難である。
【００１８】
また、上記した従来のターボ符号は、第２の課題および第３の課題を解決する場合があることが経験的にわかっているのみであり、ＬＤＰＣ符号のように理論的な解析が進んでいない。
【００１９】
このように、上記した従来の通信路符号は、第１の課題、第２の課題および第３の課題のすべてを実用運用面において解決する技術ではないので、一般の雑音を有する通信路の通信路容量に近い伝送レートで情報を送信できるとともに、復号時の誤り確率を限りなく「０」に近い値にすることができる効率的な通信路符号ではないという問題点があった。      
【００２０】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、ｓｕｍ−ｐｒｏｄｕｃｔ法などの効率的な最適化アルゴリズムが利用可能であるというＬＤＰＣ符号の利点を残しつつ、漸近的なパラメータがブロック長のみである符号を構成することにより、一般の雑音を有する通信路の通信路容量に近い伝送レートで情報を送信できるとともに、復号時の誤り確率を限りなく「０」に近い値にすることができ、かつ、符号化および復号化が実時間で行なえる情報送受信方法、符号化装置および復号化装置を提供することを目的とする。
【課題を解決するための手段】
【００２１】
上述した課題を解決し、目的を達成するため、請求項１に係る発明は、送信対象である情報を符号化した符号語を生成して雑音を有する通信路に入力し、前記通信路から出力された前記符号語である出力符号語を復号化した復号語を生成して前記情報を受信する情報送受信方法であって、第一の疎行列と第二の疎行列とをそれぞれ生成する疎行列生成工程と、前記通信路に入力される前記符号語の出現確率の分布である入力確率分布を第一の記憶部に記憶する入力確率分布記憶工程と、前記通信路を模した確率分布として、前記符号語が入力された際に前記出力符号語が出力される条件付確率分布を第二の記憶部に記憶する条件付確率分布記憶工程と、前記情報に対して、前記疎行列生成工程によって生成された前記第一の疎行列との積が零行列となり、かつ前記疎行列生成工程によって生成された前記第二の疎行列との積が前記情報となる前記符号語の候補の中で、前記第一の記憶部が記憶する前記入力確率分布が最大となるものを最適化アルゴリズムによって選択し、当該選択された候補を当該情報の前記符号語として生成する符号語生成工程と、前記出力符号語に対して、前記疎行列生成工程によって生成された前記第一の疎行列との積が零行列となる前記符号語の候補の中で、自身が前記通信路に入力された場合、前記第一の記憶部が記憶する前記入力確率分布と前記第二の記憶部が記憶する前記条件付確率分布とを用いて算出される当該出力符号語が出力される確率が最大となるものを最適化アルゴリズムによって選択し、当該選択された候補と前記疎行列生成工程によって生成された前記第二の疎行列との積を、当該出力符号語の前記復号語として生成する復号語生成工程と、を含んだことを特徴とする。
【００２２】
また、請求項２に係る発明は、送信対象である情報を符号化した符号語を生成して雑音を有する通信路に入力する符号化装置であって、第一の疎行列と第二の疎行列とをそれぞれ生成する疎行列生成手段と、前記通信路に入力される前記符号語として出現する確率の分布である入力確率分布を記憶する入力確率分布記憶手段と、前記情報に対して、前記疎行列生成手段によって生成された前記第一の疎行列との積が零行列となり、かつ前記疎行列生成手段によって生成された前記第二の疎行列との積が前記情報となる前記符号語の候補の中で、前記入力確率分布記憶手段が記憶する前記入力確率分布が最大となるものを最適化アルゴリズムによって選択し、当該選択された候補を当該情報の前記符号語として生成する符号語生成手段と、を備えたことを特徴とする。
【００２３】
また、請求項３に係る発明は、送信対象である情報を符号化した符号語が雑音を有する通信路に入力された後に、当該通信路から出力された前記符号語である出力符号語を復号化した復号語を生成して前記情報を受信する復号化装置であって、第一の疎行列と第二の疎行列とをそれぞれ生成する疎行列生成手段と、前記通信路に入力される前記符号語として出現する確率の分布である入力確率分布を記憶する入力確率分布記憶手段と、前記通信路を模した確率分布として、前記符号語が入力された際に前記出力符号語が出力される条件付確率分布を記憶する条件付確率分布記憶手段と、前記出力符号語に対して、前記疎行列生成手段によって生成された前記第一の疎行列との積が零行列となる前記符号語の候補の中で、自身が前記通信路に入力された場合、前記入力確率分布記憶手段が記憶する前記入力確率分布と前記条件付確率分布記憶手段が記憶する前記条件付確率分布とを用いて算出される当該出力符号語が出力される確率が最大となるものを最適化アルゴリズムによって選択し、当該選択された候補と前記疎行列生成手段によって生成された前記第二の疎行列との積を、当該出力符号語の前記復号語として生成する復号語生成手段と、を備えたことを特徴とする。
【発明の効果】
【００２４】
本発明によれば、第一の疎行列と第二の疎行列とをそれぞれ生成し、通信路に入力される符号語の出現確率の分布である入力確率分布と、通信路を模した確率分布として、符号語が入力された際に出力符号語が出力される条件付確率分布とを記憶する。そして、送信対象の情報に対して、第一の疎行列との積が零行列となり、かつ第二の疎行列との積が情報となる符号語の候補の中で、入力確率分布が最大となるものを最適化アルゴリズムによって選択し、当該選択された候補を当該情報の符号語として生成する。さらに、出力符号語に対して、第一の疎行列との積が零行列となる符号語の候補の中で、自身が通信路に入力された場合、入力確率分布と条件付確率分布とを用いて算出される当該出力符号語が出力される確率が最大となるものを最適化アルゴリズムによって選択し、当該選択された候補と第二の疎行列との積を、当該出力符号語の復号語として生成する。従って、第一の疎行列は、従来のＬＤＰＣ符号に用いられていたパリティチェック用のＬＤＰＣ行列として用い、また、第二の疎行列は、送信対象である情報（送信メッセージ）と符号語との対応関係を与える行列として用い、さらに、符号化時において、パリティチェックおよび送信メッセージと符号語との対応付けを実現するために、通常、従来のＬＤＰＣ符号における復号化時においてのみ用いられるｓｕｍ−ｐｒｏｄｕｃｔ法などの最適化アルゴリズムを符号化時においても用いることで、復号化時において、送信メッセージと符号語との対応付けを行なう計算処理が効率的になるので、一般の雑音を有する通信路の通信路容量に近い伝送レートで情報を送信できるとともに、復号時の誤り確率を限りなく「０」に近い値にすることができ、かつ、符号化および復号化が実時間で行なえる。
【発明を実施するための最良の形態】
【００２５】
以下に添付図面を参照して、この発明に係る情報送受信方法、符号化装置および復号化装置の実施例を詳細に説明する。なお、以下では、この発明に係る情報送受信方法を実行する通信システムを実施例として説明する。
【実施例】
【００２６】
［用語の説明］
まず最初に、以下の実施例で用いる主要な用語を説明する。以下の実施例で用いる「通信路」とは、情報の送受信のために使用される情報伝達用媒体であり、「雑音を有する通信路」とは、２元対称通信路（Ｂｉｎａｒｙ  Ｓｙｍｍｅｔｒｉｃ  Ｃｈａｎｎｅｌ）のように「０」および「１」から構成される情報が「通信路」から出力された場合、「０」が「１」として誤って出力される確率、および「１」が「０」として誤って出力される確率が固定値であるような「加法的雑音を有する通信路」の他に、「０」が「１」として誤って出力される確率、および「１」が「０」として誤って出力される確率が情報伝達ごとに変動するものも含まれる「一般の雑音を有する通信路」のことである。
【００２７】
また、「符号器」とは、送信対象である送信メッセージとしての「情報ビット」に「誤り訂正のためのビット」を付加した符号語（符号化されたメッセージ）を生成し、符号語を「通信路」に入力する装置であり、特許請求の範囲に記載の「符号化装置」に対応する。なお、以下では、「符号化されたメッセージ」のことを、「通信路入力メッセージ」と記述する場合がある。また、「復号器」とは、「通信路」から出力された符号語（通信路出力メッセージ）を、「誤り訂正のためのビット」を用いて誤り訂正を行なった復号語を生成して、送信メッセージを復号化した復号メッセージを、情報受信対象に出力する装置であり、特許請求の範囲に記載の「復号化装置」に対応する。また、「通信路出力メッセージ」は、特許請求の範囲に記載の「出力符号語」に対応する。
【００２８】
また、伝送レート（符号化レート）とは、「情報ビット数」に対する「誤り訂正符号化後のビット数」の比であり、伝送レート（符号化レート）が「ｋ／ｎ」とは、「ｋビット」の「情報ビット」に対して、「（ｎ−ｋ）ビット」の「誤り訂正のためのビット」を付加して、「ｎビット」の符号語を生成することを意味する。また、「通信路容量」とは、「通信路」が誤りなく伝送できる情報の最大量のことであり、「シャノン限界」とは、『「通信路容量」に近い「伝送レート」で情報を送信できるとともに、復号時の誤り確率を限りなく「０」に近い値にすることができる』ことを意味する。
【００２９】
また、以下の説明で用いるアルファベットは、加減乗除で閉じている集合である「体：Zq（ただし、ｑは素数）」に属するものとする。なお、本実施例では、「ｑ＝２」であり、「体」は、「０」および「１」からなる数字の集合である場合について説明する。また、「Ｘ」は、通信路に入力される「符号語」の確率変数であり、「Ｙ」は、通信路から出力される「符号語」の確率変数であるとする。また、「xn」および「yn」は、ぞれぞれ、確率変数「Ｘ」および「Ｙ」の実現値（ｎビット）を示し、これらは、「体：Zq」に属する。
【００３０】
また、「ｋビット」の送信メッセージを、「uk」として表し、「uk」は、集合「{ Zq}k」に属するものとする。また、「符号器」を、ギリシャ文字の「ファイ」で表し、本実施例では、「符号器：ファイ」は、「ｋビット」の送信メッセージ「{ Zq}k」を、「ｎビット」の符号語「{ Zq}n」に符号化するものとする。また、「復号器」を、ギリシャ文字の「プサイ」で表し、本実施例では、「復号器：プサイ」は、「ｎビット」の符号語「{ Zq}n」を、「ｋビット」の復号メッセージ「{ Zq}k」に復号化するものとする。なお、復号メッセージを、以下では、「uk」の「u」の上に「^：ハット」記号をつけて表すものとする。
【００３１】
［本実施例における通信システムの概要および特徴］
続いて、図１および図２を用いて、本実施例における通信システムの概要および主たる特徴を具体的に説明する。図１は、本実施例における通信システムの概要を説明するための図であり、図２は、本実施例における通信システムの特徴を説明するための図である。
【００３２】
本実施例における通信システムは、図１に示すように、「送信メッセージ」を符号化した符号語である「通信路入力メッセージ」を、「符号器」によって『伝送レート（符号化レート）：「ｋ／ｎ」』で生成して「雑音を有する通信路」に入力し、「雑音を有する通信路」から出力された符号語である「通信路出力メッセージ」を、「復号器」によって復号化して復号語である復号メッセージを生成することを概要とする。なお、図１に示すアルファベットの記号は、上述した［用語の説明］に順ずるものである。
【００３３】
ここで、本発明は、一般の雑音を有する通信路の通信路容量に近い伝送レートで情報を送信できるとともに、復号時の誤り確率を限りなく「０」に近い値にすることができ、かつ、符号化および復号化が実時間で行なえることに主たる特徴がある。この主たる特徴について簡単に説明すると、本実施例における通信システムは、図２の（Ａ）に示すように、「符号器」および「復号器」とともに、「疎行列生成装置」をさらに備え、「疎行列生成装置」は、第一の疎行列（Ａ）と第二の疎行列（Ｂ）とをそれぞれ生成し、生成した第一の疎行列（Ａ）と第二の疎行列（Ｂ）とを、「符号器」および「復号器」に出力する。ここで、第一の疎行列（Ａ）は、「ｎ行ｌ列」のＬＤＰＣ行列であり、第二の疎行列（Ｂ）は、「ｎ行ｋ列」のＬＤＰＣ行列であるとする。また、これらが疎行列であることは、ｓｕｍ−ｐｒｏｄｕｃｔ法などの効率的な最適化アルゴリズムを効率的に実行させるために必要な条件となる。なお、第一の疎行列（Ａ）と第二の疎行列（Ｂ）との具体的な生成法については、後に詳述する。
【００３４】
また、本実施例における通信システムを構成する「符号器」および「復号器」は、通信路に入力される符号語の出現確率の分布である入力確率分布を記憶する。例えば、図２の（Ａ）に示すように、「符号器」および「復号器」は、「xn」が出現する確率の分布である入力確率分布を、「Pxn」として記憶する。なお、本実施例で用いられる入力確率分布は、通信システムの管理者により予め設定されるものであり、「シャノン限界」を達成するために最適な確率分布が用いられる。例えば、本実施例で用いられる入力確率分布は、タイプ一定符号に対応して、相互情報量（通信路が伝送できる情報の量）が「通信路容量」より小さくなるような確率分布であればよく、例えば、Ａｒｉｍｏｔｏ−Ｂｌａｈｕｔアルゴリズム（R. W. Yeung, “A First Course in Information Theory.”, Springer, 2002参照）を用いることで得ることができる。
【００３５】
また、本実施例における通信システムを構成する「復号器」は、「通信路」を模した確率分布として、「通信路入力メッセージ」が入力された際に「通信路出力メッセージ」が出力される条件付確率分布を記憶する。例えば、図２の（Ａ）に示すように、「復号器」は、通信路に入力される「符号語」の確率変数「Ｘ」が入力された際に、通信路から確率変数「Ｙ」が出力される条件付確率分布を「WY|X」として記憶する（なお、以下では、「WY|X」のように、図２の（Ａ）に示す条件付確率分布における「Ｘ」および「Ｙ」にある上付きの「ｎ」は、省略して記述する）。ここで、本実施例で用いられる条件付確率分布は、「通信路」ごとに固有のものとして与えられるものであるが、「通信路」ごとに実際に情報の送受信を行なうことで得られる経験値に基づいて、通信システムの管理者が算出して設定するものであってもよい。
【００３６】
なお、H(X)を、「Pxn」により定義される量であるエントロピーとし、H(X|Y)を、「PXY=PxWY|X」により定義される量である条件付エントロピーとした場合、上記した自然数「ｎ」、「ｋ」および「ｌ」は、「l/n> H(X|Y)」を満たし、かつ、「(l+k)/n< H(X)」を満たすものとする。これは、シャノン限界に近づくための条件として必要なものである。
【００３７】
そして、本実施例における通信システムを構成する「符号器」は、図２の（Ｂ）に示すように、送信メッセージ「uk」に対して、第一の疎行列（Ａ）との積が零行列となり、かつ第二の疎行列（Ｂ）との積が「uk」となる符号語の候補の中で、入力確率分布が最大となるものを最適化アルゴリズムによって選択し、当該選択された候補を当該情報の符号語である「通信路入力メッセージ：xn」として生成して、「通信路」に出力する。なお、図２の（Ｂ）に示すように、符号語の候補は、「xn」の「x」の上に「~：チルダ」記号をつけて表しており、符号語の候補は、「{ Zq}n」に属する。
【００３８】
そして、本実施例における通信システムを構成する「復号器」は、図２の（Ｃ）に示すように、「通信路出力メッセージ：yn」に対して、第一の疎行列（Ａ）との積が零行列となる符号語の候補の中で、自身が通信路に入力された場合、入力確率分布「Pxn」と条件付確率分布「WY|X」とを用いて算出される当該出力符号語が出力される確率「PXY=PxWY|X」が最大となるものを最適化アルゴリズムによって選択し、当該選択された候補（すなわち、推定された「通信路入力メッセージ」）と第二の疎行列（Ｂ）との積を、「送信メッセージ」を復元した復号メッセージ（「^：ハット」記号が「uk」の「u」の上に付加されたもの）として生成して、情報受信対象に出力する。なお、図２の（Ｃ）では、図２の（Ｂ）と同様に、「通信路出力メッセージ：yn」から誤り訂正される符号語の候補を、「xn」の「x」の上に「~：チルダ」記号をつけて表しており、さらに、誤り訂正される符号語の候補の中で、最適化アルゴリズムによって選択されたものを、「xn」の「x」の上に「^：ハット」記号をつけて表している。
【００３９】
このようなことから、本実施例における通信システムは、第一の疎行列（Ａ）は、従来のＬＤＰＣ符号に用いられていたパリティチェック用のＬＤＰＣ行列として用い、また、第二の疎行列（Ｂ）は、送信メッセージと符号語との対応関係を与える行列として用い、さらに、符号化時において、パリティチェックおよび送信メッセージと符号語との対応付けを実現するために、通常、従来のＬＤＰＣ符号における復号化時においてのみ用いられるｓｕｍ−ｐｒｏｄｕｃｔ法などの最適化アルゴリズムを符号化時においても用いることで、復号化時において、送信メッセージと符号語との対応付けを行なう計算処理が効率的になるので、上記した主たる特徴の通り、一般の雑音を有する通信路の通信路容量に近い伝送レートで情報を送信できるとともに、復号時の誤り確率を限りなく「０」に近い値にすることができ、かつ、符号化および復号化が実時間で行なえる。
【００４０】
［本実施例における疎行列生成装置の構成］
次に、図３および図４を用いて、本実施例における疎行列生成装置の構成を説明する。図３は、本実施例における疎行列生成装置の構成を示すブロック図であり、図４は、疎行列生成部を説明するための図である。
【００４１】
図３に示すように、本実施例における疎行列生成装置１０は、通信制御Ｉ／Ｆ部１１と、処理部１２とから構成され、さらに、符号器２０および復号器４０とネットワークを介して接続される。
【００４２】
通信制御Ｉ／Ｆ部１１は、ネットワークを通じて送信されるデータの転送を制御するインターフェースである。具体的には、通信システムの管理者からの疎行列生成要求を、ネットワークを介して、受け付けたり、後述する疎行列生成部１２ａによって生成される疎行列を、ネットワークを介して、符号器２０および復号器４０に送信する。
【００４３】
処理部１２は、各種処理を実行し、特に本発明に密接に関連するものとしては、図３に示すように、疎行列生成部１２ａを備える。
【００４４】
疎行列生成部１２ａは、第一の疎行列（Ａ）と第二の疎行列（Ｂ）とをそれぞれ生成し、生成した第一の疎行列（Ａ）と第二の疎行列（Ｂ）とを、符号器２０および復号器４０に通信制御Ｉ／Ｆ部１１を介して送信する。ここで、疎行列生成部１２ａは、「ｎ行ｌ列」のＬＤＰＣ行列である第一の疎行列（Ａ）を、例えば、図４の（Ａ）に示す方法により生成する。まず、「ｎ行ｌ列」のＡの要素をすべて「０」とし、「１〜ｌ」の数字をランダムに「ｔ」回取り出す。ここで、「ｔ」は、「ｎ」の自然対数によって求められるオーダー（Ｏｒｄｅｒ）である。そして、疎行列生成部１２ａは、取り出された数字に対応する「列」に、「１」を「体：Zq」上で加える。これにより、「ｎ行ｌ列」の要素において「０」が多い第一の疎行列（Ａ）を生成する。
【００４５】
また、疎行列生成部１２ａは、第一の疎行列（Ａ）と同様に、「ｎ行ｋ列」のＬＤＰＣ行列である第二の疎行列（Ｂ）を、図４の（Ｂ）に示す方法により生成する。まず、「ｎ行ｋ列」のＢの要素をすべて「０」とし、「１〜ｋ」の数字をランダムに「ｔ」回取り出す。そして、疎行列生成部１２ａは、取り出された数字に対応する「列」に、「１」を「体：Zq」上で加える。これにより、「ｎ行ｋ列」の要素において「０」が多い第二の疎行列（Ｂ）を生成する。なお、オーダー「Ｏ」で定義される数値は、図４の（Ｃ）に示す関係式で定義されるものである。
【００４６】
［本実施例における符号器の構成］
続いて、図５および図６を用いて、本実施例における符号器の構成を説明する。図５は、本実施例における符号器の構成を示すブロック図であり、図６は、符号語生成部を説明するための図を説明するための図である。
【００４７】
図５に示すように、本実施例における符号器２０は、入力部２１と、出力部２２と、通信制御部２３と、入出力制御Ｉ／Ｆ部２４と、記憶部２５と、処理部２６とから構成され、さらに、疎行列生成装置１０とネットワークを介して接続され、通信路３０に接続される。
【００４８】
入力部２１は、各種情報を入力する。例えば、キーボードや、タッチパネルなどがこれに該当し、特に本発明に密接に関連するものとしては、通信システムの管理者が設定し、後述する入力確率分布記憶部２５ｂに格納される入力確率分布を、通信システムの管理者が操作するキーボードなどから入力する。
【００４９】
出力部２２は、各種情報を出力する。例えば、ディスプレイやスピーカなどがこれに該当し、例えば、疎行列生成装置１０が送信した疎行列を、ディスプレイの画面に表示したりする。
【００５０】
通信制御部２３は、他の装置との通信を制御する。例えば、ネットワークを通じて送受信されるデータの転送を制御し、特に本発明に密接に関連するものとしては、送信対象である送信メッセージのデータ受信を制御したり、疎行列生成装置１０が生成して送信した疎行列のデータ受信を制御したり、後述する符号語生成部２６ａが生成した通信路入力メッセージを通信路３０に出力する際のデータ送信を制御したりする。
【００５１】
入出力制御Ｉ／Ｆ部２４は、入力部２１、出力部２２および通信制御部２３と、記憶部２５および処理部２６との間におけるデータ転送を制御する。
【００５２】
記憶部２５は、処理部２６による各種処理に用いるデータを記憶し、特に本発明に密接に関連するものとしては、図５に示すように、疎行列記憶部２５ａと、入力確率分布記憶部２５ｂとを備える。
【００５３】
疎行列記憶部２５ａは、疎行列生成装置１０が生成し、通信制御部２３が受信した第一の疎行列（Ａ）と第二の疎行列（Ｂ）とを記憶する。
【００５４】
入力確率分布記憶部２５ｂは、通信路３０に入力される符号語の出現確率の分布である入力確率分布を記憶する。ここで、入力確率分布は、通信システムの管理者により予め設定されるものであり、入力部２１を介して入力され、入出力制御Ｉ／Ｆ部２４を介して、入力確率分布記憶部２５ｂに格納され、例えば、図２の（Ａ）に示すように、「xn」が出現する確率の分布である入力確率分布を、「Pxn」として記憶する。なお、入力確率分布は、例えば、Ａｒｉｍｏｔｏ−Ｂｌａｈｕｔアルゴリズムを用いることで得ることができる。
【００５５】
処理部２６は、入出力制御Ｉ／Ｆ部２４から転送された送信メッセージ「uk」に基づき各種処理を実行し、特に本発明に密接に関連するものとしては、図５に示すように、符号語生成部２６ａを備える。
【００５６】
符号語生成部２６ａは、図６に示す定義に従って、送信メッセージ「uk」に対して、疎行列記憶部２５ａが記憶する第一の疎行列（Ａ）との積が零行列となり、かつ疎行列記憶部２５ａが記憶する第二の疎行列（Ｂ）との積が「uk」となる符号語の候補の中で、入力確率分布記憶部２５ｂが記憶する入力確率分布が最大となるものを最適化アルゴリズムによって選択し、当該選択された候補を当該情報の符号語である「通信路入力メッセージ：xn」として生成して、通信路３０に、通信制御部２３を介して、出力する。なお、図６に示すように、符号語の候補は、「xn」の「x」の上に「~：チルダ」記号をつけ表しており、符号語の候補は、「{ Zq}n」に属する。
【００５７】
［本実施例における復号器の構成］
続いて、図７および図８を用いて、本実施例における復号器の構成を説明する。図７は、本実施例における復号器の構成を示すブロック図であり、図８は、復号メッセージ生成部を説明するための図である。
【００５８】
図７に示すように、本実施例における復号器４０は、入力部４１と、出力部４２と、通信制御部４３と、入出力制御Ｉ／Ｆ部４４と、記憶部４５と、処理部４６とから構成され、さらに、疎行列生成装置１０とネットワークを介して接続され、通信路３０に接続される。
【００５９】
入力部４１は、各種情報を入力する。例えば、キーボードや、タッチパネルなどがこれに該当し、特に本発明に密接に関連するものとしては、通信システムの管理者が設定し、後述する入力確率分布記憶部４５ｂに格納される入力確率分布、および後述する条件付確率分布記憶部４５ｃに格納される条件付確率分布を、通信システムの管理者が操作するキーボードなどから入力する。
【００６０】
出力部４２は、各種情報を出力する。例えば、ディスプレイやスピーカなどがこれに該当し、例えば、疎行列生成装置１０が送信した疎行列を、ディスプレイの画面に表示したりする。
【００６１】
通信制御部４３は、他の装置との通信を制御する。例えば、ネットワークを通じて送受信されるデータの転送を制御し、特に本発明に密接に関連するものとしては、通信路３０から出力された通信路出力メッセージのデータ受信を制御したり、疎行列生成装置１０が生成して送信した疎行列のデータ受信を制御したり、後述する復号メッセージ生成部４６ａが生成した復号メッセージを送信対象に出力する際のデータ送信を制御したりする。
【００６２】
入出力制御Ｉ／Ｆ部４４は、入力部４１、出力部４２および通信制御部４３と、記憶部４５および処理部４６との間におけるデータ転送を制御する。
【００６３】
記憶部４５は、処理部４６による各種処理に用いるデータを記憶し、特に本発明に密接に関連するものとしては、図７に示すように、疎行列記憶部４５ａと、入力確率分布記憶部４５ｂと、条件付確率分布記憶部４５ｃとを備える。
【００６４】
疎行列記憶部４５ａは、符号器２０における疎行列記憶部２５ａと同様に、疎行列生成装置１０が生成し、通信制御部４３が受信した第一の疎行列（Ａ）と第二の疎行列（Ｂ）とを記憶し、入力確率分布記憶部４５ｂは、符号器２０における入力確率分布記憶部２５ｂと同様に、通信路３０に入力される符号語の出現確率の分布である入力確率分布を記憶する。
【００６５】
条件付確率分布記憶部４５ｃは、「通信路」を模した確率分布として、「通信路入力メッセージ：xn」が入力された際に「通信路出力メッセージ：yn」が出力される条件付確率分布を記憶する。ここで、条件付確率分布は、通信システムの管理者により、入力部４１を介して入力され、入出力制御Ｉ／Ｆ部４４を介して、条件付確率分布記憶部４５ｃに格納され、例えば、図２の（Ａ）に示すように、「復号器」は、通信路に入力される「符号語」の確率変数「Ｘ」が入力された際に、通信路から確率変数「Ｙ」出力される条件付確率分布を「WY|X」として記憶する。なお、本実施例で用いられる条件付確率分布は、「通信路」ごとに与えられる固有のものとして設定するものであるが、「通信路」ごとに実際に情報の送受信を行なうことで得られる経験値に基づいて、通信システムの管理者が算出して設定するものであってもよい。
【００６６】
処理部４６は、入出力制御Ｉ／Ｆ部４４から転送された「通信路入力メッセージ」に基づき各種処理を実行し、特に本発明に密接に関連するものとしては、図７に示すように、復号メッセージ生成部４６ａを備える。
【００６７】
復号メッセージ生成部４６ａは、図８の（Ａ）に示す定義に従って、「通信路出力メッセージ：yn」に対して、疎行列記憶部４５ａが記憶する第一の疎行列（Ａ）との積が零行列となる符号語の候補の中で、自身が通信路に入力された場合、入力確率分布記憶部４５ｂが記憶する入力確率分布「Pxn」と条件付確率分布記憶部４５ｃが記憶する条件付確率分布「WY|X」とを用いて算出される当該出力符号語が出力される確率（図８の（Ｃ）参照）が最大となるものを最適化アルゴリズムによって選択する。
【００６８】
そして、復号メッセージ生成部４６ａは、図８の（Ｂ）に示すように、選択された候補と疎行列記憶部４５ａが記憶する第二の疎行列（Ｂ）との積を、復号メッセージ（「^：ハット」記号が「uk」の「u」の上に付加されたもの）として生成して、情報受信対象に出力する。
【００６９】
［本実施例における疎行列生成装置による処理の手順］
次に、図９を用いて、本実施例における疎行列生成装置１０による処理を説明する。図９は、本実施例における疎行列生成装置の処理の手順を説明するための図である。
【００７０】
図９に示すように、まず、本実施例における疎行列生成装置１０は、通信システムの管理者から疎行列生成要求を、通信制御Ｉ／Ｆ部１１を介して、受け付けると（ステップＳ９０１肯定）、疎行列生成部１２ａは、第一の疎行列（Ａ）と第二の疎行列（Ｂ）とをそれぞれ生成する（ステップＳ９０２）。
【００７１】
例えば、疎行列生成部１２ａは、「ｎ行ｌ列」のＬＤＰＣ行列である第一の疎行列（Ａ）を、図４の（Ａ）に示す方法により生成し、「ｎ行ｋ列」のＬＤＰＣ行列である第二の疎行列（Ｂ）を、図４の（Ｂ）に示す方法により生成する。
【００７２】
そして、疎行列生成部１２ａは、生成した第一の疎行列（Ａ）および第二の疎行列（Ｂ）を、通信制御Ｉ／Ｆ部１１から、符号器２０および復号器４０にネットワークを介して送信し（ステップＳ９０３）、処理を終了する。
【００７３】
［本実施例における符号器による処理の手順］
次に、図１０を用いて、本実施例における符号器２０による処理を説明する。図１０は、本実施例における符号器の処理の手順を説明するための図である。
【００７４】
図１０に示すように、まず、本実施例における符号器２０は、送信メッセージ「uk」を、通信制御部２３を介して、受信すると（ステップＳ１００１肯定）、符号語生成部２６ａは、受信した送信メッセージ「uk」から、最適アルゴリズムを用いて符号語である「通信路入力メッセージ：xn」を生成する（ステップＳ１００２）。
【００７５】
すなわち、符号語生成部２６ａは、図６に示す定義に従って、送信メッセージ「uk」に対して、疎行列記憶部２５ａが記憶する第一の疎行列（Ａ）との積が零行列となり、かつ疎行列記憶部２５ａが記憶する第二の疎行列（Ｂ）との積が「uk」となる符号語の候補の中で、入力確率分布記憶部２５ｂが記憶する入力確率分布が最大となるものを最適化アルゴリズムによって選択し、当該選択された候補を当該情報の符号語である「通信路入力メッセージ：xn」として生成する。
【００７６】
そして、符号語生成部２６ａは、生成した符号語である「通信路入力メッセージ：xn」を、通信路３０に、通信制御部２３を介して、入力し（ステップＳ１００３）、処理を終了する。
【００７７】
［本実施例における復号器による処理の手順］
次に、図１１を用いて、本実施例における復号器４０による処理を説明する。図１１は、本実施例における復号器の処理の手順を説明するための図である。
【００７８】
図１１に示すように、まず、本実施例における復号器４０は、通信路３０から、出力符号語である「通信路出力メッセージ：yn」が出力されると（ステップＳ１１０１肯定）、復号メッセージ生成部４６ａは、受信した出力符号語から最適アルゴリズムを用いて最適な符号語を選択する（ステップＳ１１０２）。
【００７９】
すなわち、復号メッセージ生成部４６ａは、図８の（Ａ）に示す定義に従って、「通信路出力メッセージ：yn」に対して、疎行列記憶部４５ａが記憶する第一の疎行列（Ａ）との積が零行列となる符号語の候補の中で、自身が通信路に入力された場合、入力確率分布記憶部４５ｂが記憶する入力確率分布「Pxn」と条件付確率分布記憶部４５ｃが記憶する条件付確率分布「WY|X」とを用いて算出される当該出力符号語が出力される確率（図８の（Ｃ）参照）が最大となるものを最適化アルゴリズムによって選択する。
【００８０】
そして、復号メッセージ生成部４６ａは、復号メッセージを生成する（ステップＳ１１０３）。すなわち、復号メッセージ生成部４６ａは、図８の（Ｂ）に示すように、選択された候補と疎行列記憶部４５ａが記憶する第二の疎行列（Ｂ）との積を、復号メッセージとして生成する。
【００８１】
そののち、復号メッセージ生成部４６ａは、生成した復号メッセージを情報受信対象に出力して（ステップＳ１１０４）、処理を終了する。
【００８２】
［本実施例の効果］
上記したように、本実施例によれば、第一の疎行列（Ａ）は、従来のＬＤＰＣ符号に用いられていたパリティチェック用のＬＤＰＣ行列として用い、また、第二の疎行列（Ｂ）は、送信メッセージと符号語との対応関係を与える行列として用い、さらに、符号化時において、パリティチェックおよび送信メッセージと符号語との対応付けを実現するために、通常、従来のＬＤＰＣ符号における復号化時においてのみ用いられるｓｕｍ−ｐｒｏｄｕｃｔ法などの最適化アルゴリズムを符号化時においても用いることで、復号化時において、送信メッセージと符号語との対応付けを行なう計算処理が効率的になるので、一般の雑音を有する通信路の通信路容量に近い伝送レートで情報を送信できるとともに、復号時の誤り確率を限りなく「０」に近い値にすることができ、かつ、符号化および復号化が実時間で行なえる。
【００８３】
なお、本実施例では、疎行列生成装置１０が生成した第一の疎行列（Ａ）と第二の疎行列（Ｂ）とを、ネットワークを介して、符号器２０と復号器４０とに送信して入力する場合について説明したが、本発明はこれに限定されるものではなく、例えば、疎行列生成装置１０が生成した第一の疎行列（Ａ）と第二の疎行列（Ｂ）とを、通信システムの管理者が、符号器２０と復号器４０とに対して、直接、入力する場合であってもよい。
【００８４】
また、疎行列生成装置１０が生成した第一の疎行列（Ａ）と第二の疎行列（Ｂ）とは、本発明が適用される通信路すべてにおいて同一のものを使用してもよいが、例えば、本発明が適用される通信路それぞれにおいて、疎行列生成装置１０が、第一の疎行列（Ａ）と第二の疎行列（Ｂ）とを生成して使用する場合であってもよい。
【００８５】
また、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００８６】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【００８７】
なお、本実施例で説明した情報送受信方法は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。このプログラムは、インターネットなどのネットワークを介して配布することができる。また、このプログラムは、ハードディスク、フレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行することもできる。
【産業上の利用可能性】
【００８８】
以上のように、本発明に係る情報送受信方法、符号化装置および復号化装置は、送信対象である情報を符号化した符号語を生成して雑音を有する通信路に入力し、通信路から出力された符号語である出力符号語を復号化した復号語を生成して情報を受信する場合に有用であり、特に、一般の雑音を有する通信路の通信路容量に近い伝送レートで情報を送信できるとともに、復号時の誤り確率を限りなく「０」に近い値にすることができ、かつ、符号化および復号化が実時間で行なえることに適する。
【図面の簡単な説明】
【００８９】
【図１】本実施例における通信システムの概要を説明するための図である。
【図２】本実施例における通信システムの特徴を説明するための図である。
【図３】本実施例における疎行列生成装置の構成を示すブロック図である。
【図４】疎行列生成部を説明するための図である。
【図５】本実施例における符号器の構成を示すブロック図である。
【図６】符号語生成部を説明するための図である。
【図７】本実施例における復号器の構成を示すブロック図である。
【図８】復号メッセージ生成部を説明するための図である。
【図９】本実施例における疎行列生成装置の処理の手順を説明するための図である。
【図１０】本実施例における符号器の処理の手順を説明するための図である。
【図１１】本実施例における復号器の処理の手順を説明するための図である。
【符号の説明】
【００９０】
１０  疎行列生成装置
１１  通信制御Ｉ／Ｆ部
１２  処理部
１２ａ  疎行列生成部
２０  符号器
２１  入力部
２２  出力部
２３  通信制御部
２４  入出力制御Ｉ／Ｆ部
２５  記憶部
２５ａ  疎行列記憶部
２５ｂ  入力確率分布記憶部
２６  処理部
２６ａ  符号語生成部
３０  通信路
４０  復号器
４１  入力部
４２  出力部
４３  通信制御部
４４  入出力制御Ｉ／Ｆ部
４５  記憶部
４５ａ  疎行列記憶部
４５ｂ  入力確率分布記憶部
４５ｃ  条件付確率分布記憶部
４６  処理部
４６ａ  復号メッセージ生成部
【図１】
0004634423.tif 000002
【図２】
0004634423.tif 000003
【図３】
0004634423.tif 000004
【図４】
0004634423.tif 000005
【図５】
0004634423.tif 000006
【図６】
0004634423.tif 000007
【図７】
0004634423.tif 000008
【図８】
0004634423.tif 000009
【図９】
0004634423.tif 000010
【図１０】
0004634423.tif 000011
【図１１】
0004634423.tif 000012