トロイド構造を有するグラフおよびＬＤＰＣ符号を用いる量子鍵配送装置
量子鍵配送装置においてデータ通信装置の処理装置は、２進データ集合から選択される各データビットをモジュロ２加算した複数の順序演算結果を抽出する。データ通信装置はターゲットシンドロームを決定する処理装置を備える送信装置や誤り訂正を実行する処理装置を備える受信装置である。処理装置は、有限トロイドを形成するセルの連続体（７０）を定義する論理ネットワークに基づき、２進データ集合からビットを選択する。連続体（７０）がビット選択に与える構造化は、ネットワークのその他の構造（９０）により、また、２進データ集合ビットの連続体ノードへのランダムな接続により補正される。ノードおよびエッジからなる論理ネットワークは、量子鍵配送装置における誤り訂正に用いられるＬＤＰＣ符号のグラフを表す。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ通信装置において、雑音を発生するチャネルである雑音チャネル（ｎｏｉｓｙ ｃｈａｎｎｅｌ）を介して送信されるデータの誤り訂正に使用するデータ処理装置に関し、詳細には、量子鍵配送（ＱＫＤ：Ｑｕａｎｔｕｍ ｋｅｙ ｄｉｓｔｒｉｂｕｔｉｏｎ）方法および装置に関するが、これに限定されるものではない。
【背景技術】
【０００２】
ＱＫＤ方法および装置の開発により、非常に高い盗聴者検出率を有する方法で２つの当事者がランダムデータを共有することが可能である。すなわち、盗聴者が検出されない場合、当事者は、共有するランダムデータが秘匿であると高い確率で確信できる。ＱＫＤ方法および装置は、例えば特許文献１〜３に記載されている。例えばＢＢ８４プロトコルに基づく自由空間を利用した装置等、多くの公知のＱＫＤ装置において、ランダムに偏光した光子を送信装置から受信装置に送信する。
【０００３】
用いられるＱＫＤ装置がどのようなものであっても、ＱＫＤ方法は通常、ランダムデータ集合を、量子信号チャネルを介してＱＫＤ送信器からＱＫＤ受信器に送信し、その後、ＱＫＤ送信器および受信器は、量子信号チャネルを介して送受信したデータを、安全性の低い従来の通信チャネルを介してＱＫＤ送信器および受信器間で交換したメッセージを用いてそれぞれ処理し、ランダムデータ集合の共有サブセットを抽出する。量子信号チャネルは雑音を含むため、このチャネルを介して受信されるデータの処理は、誤り訂正する段階を含む。しかしながら、線形ブロック符号を用いたデータの符号化／復号等の標準技術では、送信される光子のうち数パーセントしか受信されないため、量子信号チャネルを介して送信されるデータの誤り訂正は無理である。代わりに、量子信号チャネルを介して送信されるデータの誤り訂正は、誤りがない、又は標準的な誤り訂正技術により誤りをなくした従来のチャネルを介して交換されるメッセージに依存する。従来の通信チャネルは、ランダム化技術により情報の漏洩を最小限にできるため、機密である必要がない。仮に従来のチャネルが機密であったとしても、盗聴者を検出する特性は有しておらず、したがって量子信号チャネルの代わりに用いることはできないと考えられる。
【０００４】
本発明は誤り訂正に関し、とりわけ、量子信号チャネルを介して送信されるランダムデータの訂正に用いることが可能である。
【０００５】
従来の通信チャネルを介して送信されるデータの誤り訂正を実行する際に線形ブロック符号を用いることは、公知である。簡単に説明すると、添付の図面の図１に示すとおり、雑音チャネルを介して送信するメッセージを各々がｋ個のシンボルからなるデータブロックｍに分割するが、このシンボルは通常２進ビットであり、以下においては、別途記載のない限り２進ビットからなるものとする。各メッセージブロックはｋビットの行ベクトルｍとして表すことができる。各メッセージブロックは符号器１１において対応するｎビットの符号語（行ベクトルｃで表す）に符号化され、この場合ｎ＞ｋである。使用する符号語ｃは、所定の符号語集合（「符号」Ｃ）から選択する。ｋビットのメッセージブロックおよびｎビット符号語の場合、対応する符号Ｃは（ｎ，ｋ）符号と称する。メッセージブロックｍを対応する符号語ｃに符号化した後、その符号語を雑音チャネル１０を介して送信器１３により送信し、チャネル終端において受信器１４で受信し、受信器からｎビットの受信語（行ベクトルｒで表す）として出力する。チャネル１０を介した送信において誤りが全く発生しない場合、受信語ｒは送信された符号語ｃに当然一致し、受信語ｒを元のメッセージブロックｍに変換するため復号器１２にそのまま送信される。しかしながら、一般的には受信語ｒは送信された符号語ｃには一致しないが、それでも復号器１２が、符号器１１が用いる符号Ｃを認識しており、かつ誤りの数が限られている場合、復号器１２はメッセージブロックｍを復元できる。
【０００６】
線形ブロック符号は生成器およびパリティ検査行列により定義される。詳細には、線形ブロック符号Ｃは対応するパリティ検査行列Ｈのゼロ空間により定義され、符号Ｃの各符号語ｃとパリティ検査行列Ｈの転置の積は以下のようにゼロベクトルとなる。
ｃ・ＨＴ＝０
添付の図面の図２は、（７、３）線形ブロック符号のパリティ検査行列Ｈ１の例を示す。図２に示すパリティ検査行列Ｈ１に対応する符号は、正則（ｒｅｇｕｌａｒ）「低密度パリティ検査」又は「ＬＤＰＣ（ｌｏｗ ｄｅｎｓｉｔｙ ｐａｒｉｔｙ ｃｈｅｃｋ）」符号と呼ばれるものであり、この名前はパリティ検査行列が疎行列であることを反映しており、「正則」という形容詞は、全ての行が同一の重みを有し、全ての列もまた同一の重みを有することを表す。ＬＤＰＣ符号は、サイズが大きいメッセージブロックとの使用に特に望ましい。
【０００７】
受信語ｒとパリティ検査行列の転置の積はｒの誤りシンドロームと呼ばれ、本明細書においてはベクトルＳで表し、次式が成り立つ。
Ｓ＝ｒ・ＨＴ
誤りシンドロームＳがゼロの場合は当然、受信語ｒは符号語ｃである。
【０００８】
実質的に、パリティ検査行列Ｈの各行は有効な符号語ｃと判断されるために受信語ｒが満たすべき制約を定義する。より詳細には、各行は受信語ｒにおいて値をモジュロ２加算（二進数シンボルの場合）するとゼロとなるべきビット位置を示す。言い換えると、パリティ検査行列の各行が示すモジュロ２加算の結果が誤りシンドロームの対応するビットを生成する。
【０００９】
パリティ検査行列Ｈの行により定義される制約集合はタナーグラフとして知られる二部グラフにより図で表現することができ、このグラフは、
各々が入力変数（ここでは受信語ｒ）の各ビット位置に対応する第１のノード群（本明細書において「変数」ノードと称し、アルファベットの「ｖ」で示す）と、
各々が各モジュロ２加算、およびしたがってパリティ検査行列の各行に対応する第２のノード群（本明細書において「総和（ｓｕｍ）」ノードと称し、非太字のアルファベットｓで示す）と、
各総和ノードｓをパリティ検査行列の対応する行に基づいて選択される各変数ノードｖに接続するエッジとを備える。
モジュロ２加算により総和ノードｓで生成される値および接続される入力変数（受信語ｒ）のビット位置の値により誤りシンドロームＳが得られる。添付の図面の図３は、図２に示すパリティ検査行列Ｈ１のタナーグラフ１５を示し、このグラフは７個の変数ノード１６（ｖ１〜ｖ７の記号で示す）、７個の総和ノード１７（ｓ１〜ｓ７の記号で示す）、およびエッジ１８を備える。
【００１０】
タナーグラフはすべて、変数ノードおよび総和ノードが、その他の視覚的ネットワーク配置図ではなく、グラフにより構築されるノードおよびエッジからなるネットワークにおいて相互接続することを特徴とするものと考えられ、例えば、タナーグラフ１５の変数ノードｖ１〜ｖ７を、入力変数のビット位置に対する変数ノードｖ１〜ｖ７の対応性又は総和ノードに対する各変数ノードの相互接続を変更することなく、図３に示す順番と異なる順番で配置しても、単に視覚的表現が変わるだけでタナーグラフが変化する訳ではない。この表現は当然視覚的である必要はなく、詳細には、コンピュータ環境においては理論的表現（ノードの種類および他のノードとの接続を示すノードのリスト等）からなっていてもよく、これは、グラフを作成又はグラフを用いて動作する処理装置が記載されている以下の本発明の説明にも適用されることする。
【００１１】
受信語ｒが少なくとも１個の誤りを含むか否かは誤りシンドロームＳが非ゼロか否かチェックすることにより容易に決定できるが、誤り訂正はより複雑である。誤り訂正方法（例えばＬＤＰＣ符号との使用に適する）の一つに、反復的確率伝搬法又は「Ｓｕｍ−Ｐｒｏｄｕｃｔ」アルゴリズムとしても知られる確率論的反復復号法がある。この方法は、引用することにより本明細書に組込む非特許文献１等、様々な参考文献に記載されており、上記の文献はインターネット上においてwww.inference.phy.cam.ac.uk/mackay/itila/book.htmlでも入手可能である。
【００１２】
このＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムは、パリティ検査行列により定義される制約の上述のようなグラフ表現に対応するノードおよびエッジからなるネットワークに基づく。より詳細には、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムは、入力変数（受信語ｒ）の対応するビットが特定の値（ゼロ等）である確率に対応する確率を、各変数ノードｖに事前に与える。この確率は受信語ｒを受信したチャネルの誤り率に依存し、例えば、チャネル誤り率が０．０５であった場合、受信語ｒにおける「０」が実際に「０」である確率は０．９５であり、受信語ｒにおける「１」が実際には「０」である確率は０．０５である。
【００１３】
各総和ノードｓは、変数ノードに符号語が提示されると総和ノードが生成する値に対応する出力値を与えられ、上述の条件において、この値は当然ゼロである。全総和ノードに対する出力値からなる順序集合は、本明細書においては、任意の誤りシンドローム値に対応することから「ターゲットシンドローム」Ｓと称し、すなわち、上述の条件においてはゼロベクトルである。
【００１４】
その後、確率は一連のサイクルでノード間でエッジに沿って交換され、各サイクルの度に、変数ノードの入力値が制約を満たす値（すなわち、ターゲットシンドロームに整合する総和ノードの出力値に一致する値）を取ることにより収束が得られるまで、変数ノードに与えられる確率が調節される。各サイクルは、以下の２個の段階を備える。
【００１５】
段階１：各変数ノードから接続する総和ノードにメッセージが送信され、これにより、各総和ノードは接続する各変数ノードに現在与えられている確率を知る。次に、各総和ノードは、接続する各変数ノードに対して、与えられている総和ノードの出力値およびその他の接続する変数ノードから受信する確率に基づいて、対象の変数ノードが前述の特定の値を有する確率を決定する。
【００１６】
段階２：各総和ノードから接続する変数ノードにメッセージが送信され、これにより、各変数ノードは接続する各総和ノードにより自己に対して現在決定されている確率を知る。次に、各変数ノードは、接続する総和ノードから受信した確率に基づいて自己に新しい確率を与える。
最終的には、各変数ノードにおける確率は、グラフにより設定される制約を満たす対応する入力値を示す推定値「１」又は「０」として収束および安定する必要がある。
【００１７】
以上においてＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを確率の観点から記載したが、この確率は直接的な確率の他に様々な方法で表わしてもよく、例えば、対数確率、又は尤度／対数尤度を用いることも同様に可能である。本明細書における、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムにより制御される確率に関する記載は、そのような他の表現方法も含むものとする。
【００１８】
上述したように、「ターゲットシンドローム」は受信語ｒに対応する符号語ｃを読出す場合ゼロ値を有する。しかしながら、それに制限されるものではない。例えば、ターゲットシンドロームは実際には誤りシンドローム自体であって、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを用いて雑音ベクトルに対する値を抽出してもよい（上述の参考文献の図４７．２ｃおよび５５８、５５９ページを参照）。
【先行技術文献】
【特許文献】
【００１９】
【特許文献１】米国特許第５，５１５，４３８号
【特許文献２】米国特許第５，９９９，２８５号
【特許文献３】英国特許出願公開公報２４２７３１７号
【非特許文献】
【００２０】
【非特許文献１】Ｄａｖｉｄ Ｊ． Ｍａｃｋａｙ著、「Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， Ｉｎｆｅｒｅｎｃｅ ａｎｄ Ｌｅａｒｎｉｎｇ Ａｌｇｏｒｉｔｈｍｓ」、Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ出版、２００３ ＩＳＢＮ０５２１６４２９８１、５５９ページ
【発明の概要】
【課題を解決するための手段】
【００２１】
本発明の一特性によれば、２進データ集合から選択される各データビットをモジュロ２加算した複数の順序演算結果を抽出する処理装置を備え、この選択は、有限トロイド（ｆｉｎｉｔｅ ｔｏｒｏｉｄ）を覆うセルの連続体を少なくとも定義するノードおよびエッジからなる論理ネットワークにおける総和ノードの変数ノードへの接続に基づいており、該セルの各々は、交互に配置され、エッジによりループ状に相互接続する同一数の変数ノードおよび総和ノードにより区切られており、変数ノードの各々は２進データ集合のビット位置にそれぞれ対応し、総和ノードの各々はモジュロ２加算した演算結果にそれぞれ対応するデータ通信装置を提供する。
【００２２】
本発明の他の特性によれば、反復的確率伝搬法を適用して受信される２進データ集合のビット値尤度を調節し、これにより受信されるデータ集合から選択される各ビットの推定値をモジュロ２加算した複数の順序演算結果がターゲットシンドロームと整合する誤り訂正装置であって、この選択は、有限トロイドを覆うセルの連続体を少なくとも定義するノードおよびエッジからなるネットワークにおける総和ノードの変数ノードへの接続に基づいており、該セルの各々は、交互に配置され、エッジによりループ状に相互接続する同一数の変数ノードおよび総和ノードにより区切られており、変数ノードの各々は受信されるデータ集合のビット位置にそれぞれ対応し、総和ノードの各々はモジュロ２加算した演算結果にそれぞれ対応する誤り訂正装置を提供する。
【００２３】
以下に、例示のみを目的として、実施例を示す添付の図面を参照して本発明を説明する。
【図面の簡単な説明】
【００２４】
【図１】図１は、雑音チャネルを介して公知の方法により送信するためのメッセージの符号化処理を示す図である。
【図２】図２は、公知の形態のパリティ検査行列の例を示す。
【図３】図３は、図２に示すパリティ検査行列に対応するタナーグラフを示す。
【図４】図４は、本発明の実施の形態による装置の一般的な形態を示す図である。
【図５】図５は、図４に示す装置により実行されたＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムにおける失敗率の、異なるチャネル誤り率に対するターゲットシンドロームサイズへの依存性を示すグラフである。
【図６】図６は、セルが平面方向に伸長して円環状に接続されてトロイダル連続体を形成する様子を示す図である。
【図７】図７は、エッジにより相互接続して、円環状に接続されてトロイド面を形成する１２個の六角形セルを定義する変数ノードおよび総和ノードからなるネットワークを示す図である。
【図８】図８は、図７に示すノードおよびエッジからなるネットワークにより定義される制約をタナーグラフ表現したものである。
【図９】図９は、ノードおよびエッジからなるクモ構造をトロイダル連続体に付加することにより伸長した図７に示すネットワークを示す図である。
【図１０】図１０は、図１０に示すノードおよびエッジからなるネットワークにより定義される制約をタナーグラフ表現したものである。
【図１１】図１１は、図９に示すノードおよびエッジからなるネットワークにより定義される制約をパリティ検査行列表現したものである。
【図１２】図１２は、複数の十字型セルを定義するノードおよびエッジからなるネットワークを示す図である。
【図１３】図１３は、オフセット配置される６個のノードからなる矩形セルを定義するノードおよびエッジからなるネットワークを示す図である。
【図１４】図１４は、非オフセット配置される６個のノードからなる矩形セルを定義するノードおよびエッジからなるネットワークを示す図である。
【図１５】図１５は、図４に示す装置により実行されたＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムにおける失敗率の、異なるネットワーク構成に対するターゲットシンドロームサイズへの依存性を示すグラフである。
【図１６】図１６は、図１４に示すセルの好ましい配置をノードおよびエッジからなる標準ビルディングブロックから形成する方法を示す図である。
【図１７】図１７は、図４に示す装置の受信装置の動作を示すフローチャートである。
【図１８】図１８は、図１７に示すフローチャートの誤り訂正段階において実行される終盤ルーチンの好ましい形態を示すフローチャートである。
【図１９】図１９は、シンドローム誤りパターンの候補を示す図である。
【図２０】図２０は、シンドローム誤りパターンの候補を示す図である。
【図２１】図２１は、シンドローム誤りパターンの候補を示す図である。
【図２２】図２２は、シンドローム誤りパターンの候補を示す図である。
【図２３】図２３は、シンドローム誤りパターンの候補を示す図である。
【図２４】図２４は、シンドローム誤りパターンの候補を示す図である。
【図２５】図２５は、シンドローム誤りパターンの候補を示す図である。
【図２６】図２６は、本発明の実施例による量子鍵配送（ＱＫＤ）装置の概略図である。
【図２７Ａ】図２７Ａは、図２７Ｂとともに、図２６に示すＱＫＤ装置の動作方法の例を示す機能フローチャートである。
【図２７Ｂ】図２７Ｂは、図２７Ａとともに、図２６に示すＱＫＤ装置の動作方法の例を示す機能フローチャートである。
【発明を実施するための形態】
【００２５】
以下においてはまず、本発明の実施例を図４に示す一般的な条件を参照して説明し、量子鍵配送という特定の条件の適用については、図２６および図２７を参照して後に説明する。
【００２６】
図４に示す装置において、対象データ（本明細書においては行ベクトルｍで表す２進データ集合）は、送信装置２０の第１の送信器２１により第１の雑音チャネル４０を介して受信装置３０の第１の受信器３２に送信され、第１の受信器３２の出力は誤りを含む受信データ（本明細書においては行ベクトルｒで表す２進データ集合）となる。便宜上、行ベクトルｍおよびｒを用いて対象データおよび受信データを表すが、これは第１のチャネル４０が、そうである場合が多いとは言え、ビットシリアルチャネルであることを意味するものではない。
【００２７】
送信側処理装置２３および受信側処理装置３３が連動することにより、受信側処理装置３４の誤り訂正ブロック３４は受信データｒにおける誤りを訂正でき、これにより元の対象データｍを復元できる。送信側処理装置２３および受信側装置３３は、データ項目（本明細書においては一般的に「補助」データと称する）を、それぞれ送受信器２２および３２を介して第２のチャネル４５を介して相互に送信できる。チャネルの信頼性が高く誤りが発生しないため、又はより典型的には、送受信器２２、３２が受信側の送受信器から確実に誤りのなく出力するのに適した技術（例えば、誤り検出と誤りデータ項目の再送を組合せたもの、線形ブロック符号又はその他の方法を用いて誤り訂正を実行するもの等）を採用しているため、各送受信器２２、３２により対応する処理装置２３、３３に出力される受信データ項目は誤りを含まない。
【００２８】
一般論として、送信側処理装置２３および受信側処理装置３３は以下のように連動して受信データｒの誤りを訂正する。
【００２９】
１．処理装置２３、３３は同一のタナーグラフに基づいて動作、すなわち、同一のタナーグラフのノードおよびエッジに対応する相互接続する変数ノードおよび総和ノード論理のネットワークに基づいて、演算を実行する。タナーグラフは固定ではないが、以下により詳細に説明するように、疑似ランダムではあるが、決定性を有する方法で対象データｍの各項目（又は項目群）に対して、各処理装置２３、３３により独立して作成される。
【００３０】
２．送信側処理装置２３は、タナーグラフを用いて対象データｍからターゲットシンドロームＳを演算、すなわち、対象データｍのビットがタナーグラフにより指定される論理ネットワークの変数ノードに適用される値を定義し、論理ネットワークの総和ノードにおいてモジュロ２加算により生成される値の順序集合がターゲットシンドロームＳを形成する。
【００３１】
３．ターゲットシンドロームＳは、送信側処理装置２３により補助データとしてチャネル４５を介して受信側処理装置３３に送信される。
【００３２】
４．受信側処理装置３３の誤り訂正ブロック３４はＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズム（反復的確率伝搬法）を論理ネットワークに適用するが、この論理ネットワークは、送信側処理装置２３から受信するターゲットシンドロームＳにより設定される総和ノードの出力値、および受信データｒのビット値およびチャネル４０の誤り率により設定される変数ノードの初期値を用いてタナーグラフにより指定される。
【００３３】
５．Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムは、誤り訂正ブロック３４により用いられる論理ネットワークの変数ノードにおいて、ターゲットシンドロームＳに一致する推定値を生成し、この推定値は対象データｍとして出力される。
【００３４】
処理装置２３および３３は通常、支援メモリおよびサブ入力／出力装置を備える、プログラム制御によるプロセッサの形式で設けられ、図４に示すとおり、機能的に以下のようなブロックを備える。
【００３５】
送信側処理装置２３の機能ブロック：
対象データｍの所定の選択されたビットをモジュロ２加算で演算した複数の順序付けされた演算結果を求めることによりターゲットシンドロームＳを決定するブロックであって、ビットの所定の選択は、局所的に作成されたタナーグラフにおける総和ノードの変数ノードへの接続により定義されるターゲットシンドローム決定ブロック２４；
ターゲットシンドローム決定ブロック２４用に、疑似ランダムではあるが決定性を有する方法でタナーグラフを生成するグラフ作成ブロック（別称、ネットワーク作成ブロック）２５；
シンドロームサイズ決定ブロック２７；および、
処理装置２３の送信側の動作および受信側処理装置３３との補助データの交換を制御する制御ブロック２６。
【００３６】
受信側処理装置２３の機能ブロック：
既に概略を上述した誤り訂正ブロック３４であって、反復的確率伝搬法を適用して受信データｒのビット値尤度を調節することにより受信データｒにおける誤りを訂正し、これにより、受信データｒの所定の選択されたビットの推定値をモジュロ２加算で演算した複数の順序付けされた演算結果が 送信側処理装置２３から受信したターゲットシンドロームＳに一致し、ビットの所定の選択は、ターゲットシンドローム生成に使用されたタナーグラフを局所的に作成したものであるタナーグラフにおける総和ノードの変数ノードへの接続により定義される、誤り訂正ブロック３４；
誤り訂正ブロック２４用に、疑似ランダムであるが決定性を有する方法によりタナーグラフを生成するグラフ作成ブロック（別称、ネットワーク作成ブロック）３５；および、
受信側処理装置３３の動作および送信側処理装置２３との補助データの交換を制御する制御ブロック３６。
【００３７】
ターゲットシンドローム決定ブロック２４および誤り訂正ブロック３４の一般的な動作は、当業者にとっては上述の記載から明らかであり、したがって、以下においては、誤り訂正ブロックがＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムが有効な一連の処理をいつ完了したか決定するための好ましい「終盤（ｅｎｄ ｇａｍｅ）」ルーチン（図１８および以下の関連する記載を参照）を除いては説明しない。代わりに、図４に示す実施の形態に関する記載の残りの部分においては主に、処理装置２３、３３のグラフ作成ブロック（別称、ネットワーク作成ブロック）２５、３５が、それぞれブロック２４および３４による使用に適合するタナーグラフを生成する方法を中心に説明する（なお、２個のグラフ作成ブロック２５、３５により対象データｍの任意の項目に対して生成されるグラフは同一の構成を有することとする）。詳細には、タナーグラフの、後に説明する理由から以下において「トロイダルウェブ（ｔｏｒｏｉｄａｌ ｗｅｂ）」クラスと称する一般的なクラスにそれぞれ属するグラフのサブクラスの様々な実施例の生成方法を（図６から図１７を参照して）説明する。タナーグラフのトロイダルウェブクラスは、構造が相対的に容易（したがって動的なグラフ作成に適する）で、得られるグラフに特定の特性を与える特に一般的な構造を有することを特徴とする。対応する疎なパリティ検査行列にマッピングできる上述のグラフは、例えば１メガビットの長さを有する大型のメッセージにおける誤りを反復的確率伝搬法（ＬＤＰＣ符号のタナーグラフを疎なパリティ検査行列にマッピングし、反復的確率伝搬法と組合せて実行するのに適した方法と同一の方法）により訂正するのに適している。
【００３８】
グラフ作成ブロック２５および３５は同一のグラフ構成アルゴリズムに基づいて動作するよう構成され、このアルゴリズムは、トロイダルウェブクラスグラフの事前選択されるサブクラスを作成するよう構成されることとするが、選択されたサブクラス内において、このアルゴリズムは様々なパラメータ値に応じて非常に多数の異なるタナーグラフを生成可能である。同一のグラフを生成するためには、グラフ作成ブロック２５、３５は同一のパラメータ値を使用する必要がある。そのようなパラメータは、
対象データ項目ｍのサイズ（この値は対象データ項目ｍ毎に異なっていてもよく、又は全対象データ項目ｍに対して事前に同一の特定の値に固定してもよい）と、
ターゲットシンドロームＳのサイズ、又はシンドロームサイズを決定するパラメータ値（この値も同様に固定値であってもよいが、以下から明らかなように、一般的には望ましくない）と、
グラフ作成の際に実行される所定の動作におけるランダム性を規定するパラメータとを含み、このパラメータは共有の秘匿なランダムデータ（例えば、共有のワンタイムパッドにより得られる）又は疑似ランダムであり決定性を有する数の生成器ＰＮＧの動作パラメータ（初期化ベクトル等）であってもよい（後者である動作パラメータ値は、定期的な同期チェック又は再初期化が望ましいものの、通常は固定値である）。
グラフ作成アルゴリズムのパラメータが動的に（すなわち、新しい対象データ項目ｍ毎、又は対象データ項目ｍ群毎に）決定される場合、この決定処理は通常、送信側処理装置２３およびチャネル４５を介して補助データとして受信側処理装置３３に伝送される値により実行されるが、適切な状況においては、受信側処理装置３３がパラメータ値を決定し、そのパラメータ値を送信側処理装置２３に送信してもよく、又は処理装置２３、３３間で使用する値を協議してもよい。
【００３９】
また、グラフ作成ブロック２５、３５により実行されるグラフ構成アルゴリズムを、トロイダルウェブクラスグラフの複数のサブクラス雑音れかを構成するよう構成してもよく、この場合、使用されるサブクラスは動的に決定されるグラフ作成パラメータの一つとなる。
【００４０】
図４に示す実施の形態に関する以下の説明において、シンドロームサイズのみが、各対象データ項目ｍ毎に新しく動的に決定されることとする。
【００４１】
より詳細には、送信側処理装置２３のブロック２７は、第１の雑音チャネル４０の現在の誤り率に基づいてシンドロームサイズを決定する。チャネル４０の誤り率は、既知の送信データを実際に受信したデータと比較することにより測定され、この比較処理は処理装置２３および処理装置３３のどちらにより実行してもよいが、本実施例においては送信側処理側のブロック２７により実行し、ブロック２７には、送信器２１から既知の送信データが、また受信側処理装置３３からチャネル４５を介して受信データが供給される。なお、誤り率の決定に使用されるデータは一般的に、対象データｍを、チャネル４０を使用して送信可能にする第１のチャネル４０の特定の特性を有していない（例えば、チャネル４０が量子信号チャネルである場合、チャネル４５はチャネル４０が有するような盗聴者を確実に検出する特性を有していない）チャネル４５を介して送信されるため、対象データｍとは異なっている（又は分離している）必要がある。
【００４２】
チャネル４０の誤り率を決定すると、ブロック２７はその誤り率を用いて任意のシンドロームサイズを決定し、その情報をグラフ作成ブロック２５および３５に送信する。又は、上述したように、ブロック２７は決定した誤り率を受信側処理装置３３に送信して、受信側処理装置３３自体がシンドロームサイズを決定するようにしてもよい（この決定処理はブロック２７と同一の方法で実行され、これによりグラフ作成ブロック２５、３５が同一のシンドロームサイズ値を得る）。
【００４３】
以下に、ブロック２７がチャネル４０の誤り率から任意のターゲットシンドロームサイズを決定する方法を、図５を参照して説明する。図５は、チャネル４０の異なる誤り率について、グラフ作成ブロック２５、３５により作成されるタナーグラフのサブクラスに適用される反復的確率伝搬法による処理（誤り訂正ブロック３４が用いる処理）における失敗率がシンドロームサイズに応じて異なる様子を示すグラフであり、この場合、失敗率とは、反復的確率伝搬法による処理において、タナーグラフの変数ノードにおいて、ターゲットシンドロームに一致する推定値の生成に失敗した場合をさす。図５において、シンドロームサイズは対象データｍのサイズに対する割合として表され、この割合は１００％より大きくてもよい。
【００４４】
図５は、チャネル４０の異なる誤り率にそれぞれ対応する３個の曲線５１、５２、５３を示し、最大の誤り率が曲線５１に対応し、最小の誤り率が曲線５３に対応する。各曲線５１〜５３は同一の略階段形状を有し、これは、ターゲットシンドロームが所定のサイズより小さい場合、失敗率は約１００％であり、シンドロームサイズ閾値より大きい場合、失敗率は低くなることを示している。曲線５１〜５３から分かるとおり、誤り率が増大するとシンドロームサイズ閾値も増大する。
【００４５】
シンドロームサイズ決定ブロック２７は、決定されるチャネル４０の誤り率に対して、シンドロームサイズ閾値より大きいシンドロームサイズを選択するよう構成され、これにより、誤り訂正ブロック３４が実行する反復的確率伝搬法による処理の失敗率を確実に低く抑えることができる。効率性の観点から、選択されるシンドロームサイズはサイズ閾値より数パーセントだけ大きいものとする。
【００４６】
以下において、各グラフ作成ブロック２５、３５が、対象データｍの任意のサイズｐ（ビット）およびターゲットシンドロームの任意のサイズｑ（ビット）に対応するタナーグラフのトロイダルウェブクラスの事前選択されるサブクラスのグラフを構成するために実行するグラフ構成アルゴリズムを考える。グラフ構成アルゴリズムは実際には、対象となるサブクラスに関わらず、エッジにより相互接続する変数ノードおよび総和ノード（すなわち、対象データｍの各ビットに対応する各変数ノードおよびターゲットシンドロームＳの各ビットに対応する各総和ノード）からなるネットワークを構成し、以下の２個の主段階を備える。
【００４７】
第１段階において、同一数の（ｐおよびｑのうち小さい方により決定される）変数ノードおよび総和ノードは有限トロイドを形成するセルの連続体内に配置され、各セルは、交互に配置され、エッジによりループ状に相互接続する同一数の変数ノードおよび総和ノードにより区切られている。
【００４８】
第２段階において、変数ノード又は総和ノードのうち一方（第１段階において全部が使用されていない方）のノードをそれぞれ備える複数の「クモ構造」が定義され、この変数ノード又は総和ノードのうち一方は、第１段階においてセルの連続体を定義する処理に用いられた変数ノード又は総和ノードのうち他方のノードからランダムに選択されたノードに所定数のエッジを介して接続される。
第２段階は、対象データのビット数ｐがターゲットシンドロームのビット数ｑと異なる場合のみ必要となる。変数ノードを総和ノードに有効に接続するのはエッジである。
【００４９】
上述のような一般的なグラフ構成アルゴリズムに基づいて作成可能なグラフは「トロイダルウェブ」クラスのグラフを形成し、この名前の重要性は今や明らかである。更に、グラフ構成アルゴリズムの第１段階において用いられるセルの形状および相互関係が、得られるグラフのサブクラスを決定する。
【００５０】
図６、図７、および図９は、対象データサイズｐが１５、およびターゲットシンドロームサイズｑが１２の場合の、「六角形」サブクラス（グラフ構成の第１段階で用いられるセルが六角形形状を有するため）のグラフを作成する実施例を簡略に示す。この場合、グラフ構成の第１段階において１２個の変数ノードおよび１２個の総和ノードにより１２個の六角形セル６１（図６参照）を形成し、この六角形セル６１は６個ずつ２列に配置されて端と端（矢印６３）および上と下（矢印６２）がそれぞれ接続されて円環のようになっており、有限トロイド面を形成するセルの連続体を形成する。図７はノードの配置をより詳細に示し、１２個の変数ノードはｖ１〜ｖ１２の記号で示し、１２個の総和ノードはｓ１〜ｓ１２の記号で示す。図から分かる通り、各六角形セルは交互に配置される３個の総和ノードおよび３個の変数ノードからなり、例えば、セル７７は、それぞれ変数ノードｖ１、総和ノードｓ１、変数ノードｖ２、総和ノードｓ８、変数ノードｖ７、および総和ノードｓ８からなるノード７１〜７６を備える。セルは共有のエッジを有し、これにより各ノードは実際には区切られた３個のセルで共有される。トロイド状のセルの連続体７０を形成するためにセルを円環状に接続する構造は、最上列のノード（ノードｖ１、ｓ１、ｖ２、ｓ２、ｖ３、ｓ３、ｖ４、ｓ４、ｖ５、ｓ５、ｖ６、ｓ６）を最下列のノードとして反復（点線で示す）し、最左列のノード（ｖ１、ｓ７、ｖ７、ｓ１）を最右列のノードとして反復するにより表す。
【００５１】
図８は、図７に示すノードおよびエッジからなるネットワークを、タナーグラフの図示においてより一般的に利用される形状８０（例えば図３において使用）に書き換えたものであり、変数ノードｖ１〜ｖ１２は上方で順番に配置され、総和ノードｓ１〜ｓ１２は下方で順番に配置される。図７においてセル７７を定義するエッジは、図８において太線（８１参照）で示す。なお、図７、およびしたがって図８は、本実施例に対して、部分的にのみ完成したグラフを表わしているものとする。
【００５２】
また、タナーグラフを図示する際、変数ノードの順序は一般的に対象データにおけるビットの順序に対応し、一方、図７に示すネットワークを書き換えたものである図８においては、変数ノードの順序は、以下に記載するように対象データｍにおけるビットの順序に対応する場合もしない場合もある、添字番号に基づく。図７に示すように変数ノードの番号が対象データｍの対応するビットの位置に一致しない場合、図７を、変数ノードを対象データｍの対応するビットの順序に基づいて順番に並べて書換えても、基底構造の規則性がはっきりと表れない可能性が高い。
【００５３】
グラフ構成の第２段階において、第１段階には関与しない３個の過剰な変数ノード（ノードｖ１３、ｖ１４、ｖ１５）は六角形セルからなるトロイダル連続体７０に接続される。この接続は以下のように実行される。３個の過剰な変数ノードｖ１３、ｖ１４、ｖ１５の各々は順次選択されて、自己を３個のランダムに選択される総和ノード（既にトロイダル連続体７０内に組込まれている）に接続するよう規定される。視覚的観点からすると、図９に示す通り、過剰な変数ノードｖ１３、ｖ１４、ｖ１５の各々は、自己をトロイダル連続体７０に接続する３個の脚を有するクモ構造９０の本体を形成し、したがって、図９は、総和ノードｓ１、ｓ１０、およびｓ１２に接続する過剰な変数ノードｖ１３、総和ノードｓ２、ｓ５、およびｓ９に接続する過剰な変数ノードｖ１４、総和ノードｓ６、ｓ８、およびｓ１１に接続する過剰な変数ノードｖ１５を示す。好ましくは、総和ノードを過剰な変数ノードにランダムに割当てる処理は、ランダムに構成した総和ノードのリストを作成し、各過剰な変数ノードｖ１３、ｖ１４、ｖ１５の各々に対して、作成したリストの最上位の３個組の総和ノードを順次選択することにより実行され、過剰な変数ノードに対して全てのクモ構造９０が作成される前にリストの総和ノードが使果たされた場合、総和ノードのリストを新しくランダムに構成して、残存する変数ノードに対して処理を繰返し実行する（処理は必要回数実行してもよい）。
【００５４】
シンドロームビット（すなわち総和ノード）の数ｑが対象データビット（すなわち変数ノード）の数ｐより大きい場合、上述のグラフ構成の第２段階において変数ノードおよび総和ノードの役割は逆になる。更に、各クモ構造における脚の数は３個に制限されるものではなく、好ましくは４個である。
【００５５】
上述の方法によりクモ構造を構成することにより、トロイダル連続体７０において「脚」が疑似ランダムではあるが非常に均等に配置され、正則（すなわち、効率的に構成可能）なトロイダル連続体７０にランダム性を付加する。
【００５６】
タナーグラフにおいて長さ４のサイクルは一般的に望ましくないため、好ましくは、新しくクモ構造９０が形成される度に長さ４のサイクルが作成されていないかチェックし、長さ４のサイクルが生成されていた場合、そのクモ構造は拒否され、代わりに新しいクモ構造が作成される。長さ４のサイクルのチェックは以下のように非常に単純である。
【００５７】
（ｉ）新しいクモ構造の「足先」（すなわち、クモ構造の本体を形成する過剰なノードに直接接続されるトロイダル連続体のノード）が、トロイダル連続体において、２個以上のノードを介して相互に分離されているかチェックし、
（ｉｉ）また、新しいクモ構造の２個の足先と別のクモ構造の２個の足先が異なっているか（すなわち異なるノードであるか）チェックする。
【００５８】
図１０は、図９に示すネットワーク（トロイダル連続体７０およびクモ構造９０の両方）をタナーグラフの図示においてより一般的に利用される形状１００に書換えたものである。図１０は、本実施例に対して構成される完全な六角形サブクラスグラフを表す。なお、図８に示す書替図と同様に、この書替図における変数ノードの順序は、対象データｍのビット順序に一致する場合もしない場合もある添字番号に基づく。
【００５９】
実際には、対象データ項目ｍのビット位置を図９に示すネットワークの変数ノードに対応させる処理は所定の方法（例えば、ノード添字により示すノード番号又はその他所定の対応パターンに基づいて）で実行してもよく、又は、疑似ランダムに（グラフ作成ブロック２５、３５のそれぞれで独立して実行可能な決定性を有する方法で）決定してもよい。総和ノードについては、必要なのは、ターゲットシンドローム決定ブロック２４がターゲットシンドロームＳを生成する際に使用する順序を、誤り訂正ブロック３４がターゲットシンドロームを用いる際にも使用するという点だけである。
【００６０】
図１１は、図１０に示すグラフに対応（当然、図９に示すネットワークにも対応）する、対象データｍのビット位置をノード添字に基づいて変数ノードに対応させるためのパリティ検査行列Ｈ２（参照符号１１０）を示す。図１１は、この行列が疎であることを示す。既に説明したように、行列Ｈ２の各行は、モジュロ２加算により対応するターゲットシンドロームのビット値を演算するために選択される対象データビットを表す。
【００６１】
上述のトロイダルウェブクラスのグラフの実施例は「六角形」サブクラスグラフであり、すなわち、トロイダル連続体が六角形セルからなる。図１２〜図１４は、トロイダルウェブクラスグラフの他のサブクラスのトロイダル連続体を構成するために使用される以下のような異なる形状のセルを示す。
【００６２】
図１２は、「十字型」サブクラスグラフのトロイダル連続体の一部１２０を示し、連続体の一部１２０は、各々が、交互に配置され、かつエッジを介して相互接続する６個の総和ノードおよび６個の変数ノードを備える４個の十字型セル１２１〜１２４からなる。完全な連続体において、各セルの境界上においてノードは３個おきに３個の隣接するセルにより共有され、エッジにより４個の他のノードに接続し、そのうち２個のノードが同一のセルに属する。各セルのその他のノードは、対象のセルのノードにのみ接続。
【００６３】
図１３は、図１４に示す実施例と比較する目的で、「六角形」サブクラスグラフのトロイダル連続体の一部１３０を示し、ここでは六角形セルはオフセット配置され６個のノードからなる矩形として書替られている。図示のトロイダル連続体の一部１３０は６個のノードからなる６個の矩形セル１３１〜１３６からなり、６個の矩形セル１３１〜１３６は３列に配置され、中央の列はその他の２列に対して水平方向にオフセット配置される。各セル１３１〜１３６は、交互に配置され、エッジを介して相互接続する３個の総和ノードおよび３個の変数ノードを備える。各セルにおいて、４個のノードはセルの頂点に配置され、（完全な連続体において）、この４個のノードは２個のその他のセルと共有であり、３個のその他のノードに接続し、そのうち２個のノードが同一のセルに属する。セルの残りの２個のノードは、セルの対向する１組の側部のそれぞれに沿って中央に配置され、また、２個のその他のセルと共有であり、かつ３個のその他のノードに接続し、そのうち２個のノードが同一のセルに属する。
【００６４】
図１４は、「非オフセット配置される６個のノードからなる矩形」サブクラスグラフのトロイダル連続体の一部１４０を示し、該連続体の一部１４０は６個のノードからなる８個の矩形セル１４１〜１４８からなり、各矩形セル１４１〜１４８は図１３に示す実施例の６個のノードからなる矩形と同一形状を有するが、非オフセットで配置される列として配置される。この場合、完全な連続体において、各セルにおいてセルの頂点に配置される４個のノードは３個の隣接するセルと共有されており、同一のセルに属する２個のその他のノードに接続し、セルの残りの２個のノードはそれぞれ対象のセルの２個のノードにのみ接続する。
【００６５】
セルの「形状」は主に、論理ネットワークを視覚表現する処理を説明する際の便宜上のもので、大切なのは、セルのノードの相互接続である。
【００６６】
図１５は、図５に示すグラフと同様に、タナーグラフの異なる形状について、対象のタナーグラフに適用される反復的確率伝搬法による処理（誤り訂正ブロック３４が用いる処理）における失敗率がシンドロームサイズに応じて異なる様子を示すグラフであり、チャネル誤り率は全ての場合において同一である。より詳細には、曲線１５１は「ランダム」グラフ（すなわち、構造を備えないものの、長さ４のサイクルが除去されたグラフ）に対応し、曲線１５２は「六角形」サブクラスグラフに対応し、曲線１５３は「非オフセット配置される６個のノードからなる矩形」サブクラスグラフに対応する。図から分かる通り、シンドローム閾値（各曲線が階段状に変化し始める部分）はトロイダルウェブクラスグラフのサブクラス両方ともにおいて、ランダムグラフにより得られる基準閾値より小さく、一般的に、トロイダルウェブクラスのグラフは基準となるランダムグラフと比べてより効率的である（任意のチャネル誤り率に対して必要となるシンドロームサイズがより小さい）ことが分かった。詳細には、「非オフセット配置される６個のノードからなる矩形」サブクラスのグラフが一番高い効率を有することが分かった。
【００６７】
図１６は、ノードおよびエッジからなる標準的なビルディングブロック１６０から、「非オフセット配置される６個のノード矩形」サブクラスグラフのトロイダル連続体を容易に構成する方法を示す。より詳細には、ビルディングブロック１６０は、交互に配置され、エッジを介して相互接続する２個の総和ノードおよび２個の変数ノードからなるライン（ｌｉｎｅ）を備え、終端のノードもエッジを介して相互接続する（図１６において矢印１６５で示す）。この交互に配置される総和ノードおよび変数ノードからなるラインの各ノード（本明細書においては「ラインノード」）はエッジからなる側枝を有し、この側枝は、他のビルディングブロックのラインノードに接続するために解放されているエッジを介して他のノードに接続する。図１６の左側は、上述のように、各ビルディングブロックの解放エッジを隣接するビルディングブロックの対応するラインノードに接続することにより結合した３個のビルディングブロック１６１、１６２、１６３を示す。十分な数のビルディングブロックが上述の方法で相互接続されて、最小のｐ（対象データビットの数）およびｑ（シンドロームビットの数）と同一数の総和ノード又は変数ノードが得られた場合、一番最初のビルディングブロック（図１６におけるブロック１６１）の解放されている終端は一番最後に付加されたビルディングブロック（図１６におけるブロック１６３）のラインノードに円環状に接続され、これによりトロイダル連続体を封止して完成させる。上述のように形成したトロイダル連続体は、端と端が結合された細長い管のような形状を有する（妥当なサイズの対象データ項目ｍを想定する）。
【００６８】
当然、上述のように構成されたトロイダル連続体における各種（総和又は変数）ノードの数は４の整数倍数であるのに対して、ｐおよびｑの最小値は４の整数倍数ではない場合がある。これに対処するためには様々な解決策が可能であり、例えば、シンドロームビットの数ｑは常に４の整数倍数となるよう選択してもよく、ｐおよびｑのうち対象データビットの数ｐの方が小さい場合、適切な数の対象データビットを切捨ててもよく（以下に説明するＱＫＤを用いた実施例等、所定の場合に望ましい）、又は適切な数のダミー対象データビットを付加してもよい。
【００６９】
上述のビルディングブロックを用いたトロイダル連続体の構成方法は、トロイダルウェブクラスのその他のサブクラスグラフに適用してもよく、そのような適用は当業者の裁量の範囲内であるとする。
【００７０】
グラフの生成および使用に関して上述した要点を整理および要約するため、以下に、受信器３２から受信データｒを受信した際の受信側処理装置３３の動作を図１７を参照して説明する。
【００７１】
まず、初期工程１７１において、受信側処理装置３３は規定値ではないグラフパラメータ値を取得するが、本実施例において、対象データｍにおけるビット数ｐは規定値であり、生成するトロイダルウェブグラフのサブクラスおよびグラフ生成に用いられる疑似乱数生成器のパラメータも同様である。本実施例の工程１７１において取得される唯一の動的パラメータは、受信側処理装置３３がチャネル４０の誤り率から導出するシンドロームサイズｑであり、チャネル４０の誤り率は送信側処理装置２３からチャネル４５を介して送信される補助データに含まれる。
【００７２】
その後、受信側処理装置３３はグラフ生成（図１７におけるブロック１７２）を開始する。上述したように、グラフ生成の第１段階はトロイダル連続体の生成であり、これは、工程１７３１における、最小のｐおよびｑに対応する数の総和／変数ノードを得るために必要な標準ビルディングブロック（例えば、図１６に示す、「非オフセット配置される６個のノードからなる矩形」グラフサブクラスに対応するビルディングブロック１６０）の数ｎを決定する第１の決定処理により実行される。ｎの値が決定されると、工程１７３２において、ビルディングブロックの追加がｎサイクルだけ実行され、ｎ個のビルディングブロックが結合されて求めるトロイダル連続体を形成する。
【００７３】
グラフ生成の第２段階は、各過剰なノード（すなわち、トロイダル連続体からは得られていない必要な総和／変数ノード）に対して適切な数のクモ構造の生成するものあり、図１７におけるブロック１７２を参照する。過剰なノードは全て一方の種類であり、工程１７４１において、この過剰なノードの各々を、ランダムに混合わせた他方の種類のノード群（全てトロイダル連続体に属する）の上から選択したｘ（例えば４）個のノードに対応付ける（論理的にはエッジ又は「クモの脚」により接続する）。工程１７４２において、トロイダル連続体に新たに接続された過剰なノードの各々に対して長さ４のサイクルチェックを実行する。
【００７４】
グラフ生成の最終段階は、工程１７５において、データ項目ｍのビット位置をグラフの変数ノードに割当てるものである。
【００７５】
送信側処理装置２３および処理装置受信側３３において略同一のタイミングで実行されるグラフ生成に続いて、受信側処理装置３３は、送信側処理装置２３からチャネル４５を介して受信側処理装置３３に送信される補助データに含まれるターゲットシンドロームＳを受信する（工程１７６参照）。
【００７６】
その後、受信側処理装置３３は、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを用いて受信データｒの誤り訂正を開始（図１７におけるブロック１７７参照）し、ターゲットシンドロームＳに一致する受信データビットの推定値を調節する。本実施例において、ｙサイクル１７８（ｙは例えば４）のＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムが終了する度に、「終盤（ｅｎｄ ｇａｍｅ）」ルーチン１７９を実行してＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムが結論を出したか（元のデータｍの復元成功か、又はＳｕｍ−Ｐｒｏｄｕｃｔサイクルを更に実行しても訂正不可能な失敗か）、又はＳｕｍ−Ｐｒｏｄｕｃｔサイクルを更に実行すべきかを決定し、後者の場合、処理は工程１７８に戻る。
【００７７】
多くの用途においては、変数ノードにおける推定値がターゲットシンドロームＳに一致すれば結果は成功であったと判断されるが、用途によってはより高い確実性が求められ、ターゲットシンドロームの整合性が元のデータｍのビット値に整合しないｖノード推定値に基づくものである可能性が考えられる。終盤ルーチンは、元のデータｍから導出したチェックサムに基づくチェックを含むことにより、そのような可能性を考慮することができ、このチェックを実行するためには、受信側処理装置３３は送信側処理装置２３から正確なチェックサムを（例えば、工程１７６において送信される補助データに含めて）受信する必要があると考えられる。
【００７８】
終盤ルーチンは、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムが有効な一連の処理を完了したか否か決定するとともに、変数ノードにおける推定値がターゲットシンドロームにほぼ一致する場合、誤り総和ノード（すなわち、総和ノードにおいて現在の推定ｖノード値から得た値がその総和ノードに対するターゲットシンドローム値と異なる）のパターンを認識し、そのパターンに基づいて選択ｖノード値を調節することにより整合性を実現してもよい。この、誤り総和ノードのパターンを認識することによる訂正処理について、以下により詳細に説明する。
【００７９】
以下に、「終盤」ルーチン１７９の好ましい形態について図１８を参照して説明し、上記のチェックサムチェックおよび誤り総和ノードのパターンの認識に基づく訂正処理を組込む。
【００８０】
図１８に示す終盤ルーチンはまず、実行中のグラフの変数ノードにおける現在の推定値を決定し、その後、その推定値を用いて現在のシンドローム、すなわちグラフの総和ノード値を抽出するが、これらのノードはターゲットシンドローム値とは対応していない（工程１８１参照）。その後、この現在のシンドロームをターゲットシンドロームＳと比較して異なるビット数のｄを決定する（工程１８２）。
【００８１】
このシンドロームとの差ｄの数が例えば６より大きい（工程１８３において確認する）場合、Ｓｕｍ−Ｐｒｏｄｕｃｔサイクルが更に必要であると判断されるが、既に上限回数（例えば、３００等）のサイクルが実行されていた場合（工程１８４において確認する）、Ｓｕｍ−Ｐｒｏｄｕｃｔサイクルを更に実行してもターゲットシンドロームＳに一致する推定ｖノード値集合への収束は難しいため、誤り訂正を停止し、失敗したと判断する。
【００８２】
工程１８３において、シンドロームとの差がない（ｄ ＝ ０）、すなわち推定ｖノード値がターゲットシンドロームＳに一致すると決定された場合、工程１８５において、推定ｖノード値からチェックサムを作成（ｖノード値を受信データｒに一致する順番に並べるために必要に応じて並び替えを考慮する）し、工程１８６において、元のデータｍから作成したチェックサムと比較する。チェックサムが一致する場合、誤り訂正は成功したとして処理を終了し、推定ｖノード値が復元された対象データｍとして出力される（同様に、必要に応じて並び替えを行う）。しかしながらチェックサムが一致しない場合も、Ｓｕｍ−Ｐｒｏｄｕｃｔサイクルを更に実行しても正しいｖノード値集合への収束は難しいため、誤り訂正は失敗したとして処理を終了する。
【００８３】
工程１８３において、シンドロームとの差ｄの数が１〜６（０＜ｄ≦６）の範囲の数あると決定された場合、上述した誤り総和ノードのパターンの認識に基づいた訂正処理が実行され（工程１８７）、選択されたｖノード値が反転される。値を反転した結果、シンドロームとの差がゼロまで減少した場合（工程１８８において確認する）、チェックサム作成工程１８５および比較工程１８６が実行されるが、値を反転してもシンドロームとの差がゼロまで減少しない場合、現在実行中の終盤ルーチンの直前に存在したｖノード推定値からＳｕｍ−Ｐｒｏｄｕｃｔサイクルを更に実行する（工程１８４の上限チェックを行う）。
【００８４】
誤り総和ノードのパターン認識に基づく訂正処理（工程１８７）に関して、図１９〜図２５はそれぞれ、トロイダルウェブグラフの「非オフセット配置される６個のノードからなる矩形」サブクラスに対応する誤り総和ノードのパターンを示し、各パターンにおいて、太線の円により囲まれた総和ノードが誤り総和ノードである。これらのパターンは工程１８７において系統的に検索され、パターンが検出されると、所定の変数ノードに対応にするビット値が不正値の候補として特定されて反転され、この変数ノードは、認識されたパターンにおいて値が変更された場合、対象のパターンにおける総和ノードの不正値を解消する。そのような変数ノードは、図１９〜図２５において点線の円で囲んで示す。その後、上述の検索処理が、グラフ全体が検索されるまで、又は訂正された総和ノード値の数がシンドロームとの元の差と同数になるまで継続して実行される。
【００８５】
図１９〜図２５において、誤り総和ノードがいくつ発生しているかに基づいてパターンを配置する。便宜上、各パターンに非制限的な記述による以下のようなラベルを付ける。
【００８６】
図１９および図２０はそれぞれ、誤り総和ノードが２個のみ発生しているパターンを示し、以下のラベルで表す：
「２ｓ−線上隣接型」；および
「２ｓ−線上三個組型」。
【００８７】
図２１〜図２３はそれぞれ、誤り総和ノードが４個発生しているパターンを示し、以下のラベルで表す：
「４ｓ−菱形」；
「４ｓ−燭台型」；および
「４ｓ−回転Ｌ字型」。
【００８８】
図２４〜図２５はそれぞれ、誤り総和ノードが６個発生しているパターンを示し、以下のラベルで表す：
「６ｓ−六角形」；および
「６ｓ−漏斗型」。
【００８９】
上述のラベルは誤り総和ノードパターンの特定の視覚的外見に言及しているものの、当然のことながら、視覚的外見は基本となるノードおよびエッジからなる論理ネットワークを視覚的に表現する特定の方法に依存し、様々な他の表現方法も可能なため、全く重要ではない。誤り総和ノードの各パターンは基本的に、任意の表現方法が与える視覚的パターンによってではなく、対象の総和ノードの相互関係のパターンにより定義される。
【００９０】
例として、図１９に示す単純な「２ｓ−線上隣接型」パターンは、他に接続先を有さない１個の変数ノードを介して接続される２個の誤り総和ノードからなる。したがって、「２ｓ−線上隣接型」パターンにおいて、誤り総和ノード間に配置される変数ノードに対応付するビット値が、この値を反転することによりその他の総和ノードではなく誤り総和ノードの値が反転するため不正値の候補となる。同様に、図２０に示す「２ｓ−線上三個組型」パターンにおいて、２個の誤り総和ノードはエッジおよびノードからなるラインを介して接続され、ライン上のノードは１個の非誤り総和ノードを間に挟んで配置される２個の変数ノードを備え、この変数ノードは間に挟まれる総和ノードおよび誤り総和ノードの一方にそれぞれ接続され、両方の変数ノードに対応するビット値が、この値を反転することによりその他の総和ノードではなく誤り総和ノードの値が反転するため不正値の候補となる。
【００９１】
図２２に示す「４ｓ−燭台型」パターンは、対象のグラフのトロイダル連続体が上から下まで円環上に接続されるため、実際には図２１に示す「４ｓ−菱形」パターンと同一の基本的パターンと考えられるかもしれないが、検索処理が（図示のように）「最下」列のノードを参照して実行された場合、パターンが異なる。各パターンにおいて、４個の誤り総和ノードは１個の中間変数ノードを介して相互接続され、中間変数ノードに対応するビット値が、この値を反転することによりその他の総和ノードではなく誤り総和ノードの値が反転するため不正値の候補となる。
【００９２】
図２４および図２５に示す「６ｓ−六角形」パターンおよび「６ｓ−漏斗型」パターンについても同様である。この場合、各パターンは以下を備える。
【００９３】
２個の変数ノードおよび間に配置される中間の非誤り総和ノードからなる３個組のノードにより接続される第１の誤り総和ノード対。各変数ノードは中間の総和ノードおよび第１の対の各誤り総和ノードにそれぞれ接続される。
【００９４】
その他の接続を有さない１個の中間変数ノードを介して接続される第２の誤り総和ノード対。第２の対の各誤り総和ノードは、第１の誤り総和ノード対を接続する上記の３個組ノードのうち変数ノードのそれぞれに接続される。
【００９５】
その他の接続を有さない１個の中間変数ノードを介して接続される第３の誤り総和ノード対。第３の対の各誤り総和ノードは、第１の誤り総和ノード対を接続する上記の３個組ノードのうち変数ノードのそれぞれに接続される。
【００９６】
第１の誤り総和ノード対を接続する３個組ノードのうち２個の変数ノードに対応するビット値が、この値を反転することによりその他の総和ノードではなく誤り総和ノードの値が反転するため不正値の候補となる。
【００９７】
より複雑なパターン（すなわち、より多くの誤り総和ノードを含むパターン）が優先的に検索されるが、これは、図１９に示す「２ｓ−線上隣接型」パターンのような単純なパターンは、実際には単に図２１〜図２３に示す４個の誤り総和ノードを含むパターンのようなより複雑なパターンの一部である場合があるためである。
【００９８】
図１９〜図２５に図示した誤り総和ノードのパターンは、全てのパターンを網羅することを意図するものではなく、工程１８７は任意の可能なパターンを検索するよう構成してもよい。更に、上述した誤り総和ノードのパターンは全て対象のグラフのトロイダル連続体に見られるパターンであるが、グラフの「クモ構造」を含むパターンを検索することも可能である。より詳細には、ｐ＞ｑであり、これにより各クモ構造の中心となるノードが変数ノードｖである場合、クモ構造の全ての脚における「足先」に対応する誤り総和ノードのパターンは、クモ構造の中心となる対象データビットが誤りである可能性が高く、反転すべきであることを示す。好ましくは、上述のような誤り総和ノードパターンを（例えば、各クモ構造を順次チェックすることにより）まず検索する。
【００９９】
既に述べたように、図１９〜図２５に図示したパターンはトロイダルウェブグラフの「非オフセット配置される６個のノードからなる矩形」サブクラスに適用可能であり、当業者は、トロイダルウェブグラフのその他のサブクラスに対応する類似の誤り総和ノードパターンを容易に導出できる。
【０１００】
当業者にとっては、誤り総和ノードのパターン（および各パターンに対応する誤り変数ノード又はノード群の候補）を表すデータは、装置が処理しようとする各種のグラフに対応して、受信装置により記憶され、記憶されたデータはプレインストールされていてもよく、又は必要に応じて読込んでもよいことは明らかである。また、誤り変数ノードの候補を特定する処理は、事前に受信データビット位置を変数ノードに対応付けするため、受信データの誤りビット候補を特定する処理（Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを適用して調節する）と同様に効率的である。
【０１０１】
応用例
ワンタイムパッド補充に用いられるＱＫＤ装置における誤り訂正
以下に、図２６および図２７を参照して、整合ワンタイムパッド（ＯＴＰ）の補充に用いられる量子鍵配送（ＱＫＤ）装置の誤り訂正に関する上述の誤り訂正方法および装置の応用例を説明する。
【０１０２】
公知のように、同一の秘匿なランダムデータを有する２つの当事者が、バーナム暗号を用いて解読不能で機密な通信を行ったり、また真正なメッセージと誤った、又は改ざんされたメッセージとを（例えばＷｅｇｍａｎ−Ｃａｒｔｅｒ認証を用いて）識別したりできることが分かっている。しかしながら、どちらの場合も、当事者が共有する秘匿なランダムデータから使用したデータは再使用すべきではない。したがって、「ワンタイムパッド」という用語は当事者が共有する秘匿なランダムデータをさすことが多く、本明細書においては、この用語又はその頭字語「ＯＴＰ（ｏｎｅ−ｔｉｍｅ ｐａｄ）」は複数の当事者が共有する秘匿なランダムデータをさすが、以下に記載の特定の例においては、この当事者を、ＱＫＤ送信装置に相当する当事者アリスおよびＱＫＤ受信装置に相当する当事者ボブとする。絶対的な安全性のためにはワンタイムパッドデータは真にランダムである必要があるが、本明細書においてワンタイムパッド（ＯＴＰ）に言及する場合、真にランダムではないかもしれないが、対象の目的に対して許容できるレベルの安全性を提供するには十分ランダムな秘匿データを含む。
【０１０３】
ＯＴＰデータは使用されると実質的に消費されてしまうため、ワンタイムパッドの様々な用途において、対象の複数の当事者が保持するＯＴＰデータを、ＯＴＰデータの使用により得られる安全性を損なわないよう非常に機密な方法で補充する必要が生じる。
【０１０４】
近年、量子鍵配送（ＱＫＤ）方法および装置が開発されており、２つの当事者が、非常に高い確率で盗聴者を検出可能な方法でランダムデータを共有することができる。すなわち、盗聴者が検出されない場合、当事者は共有のランダムデータが秘匿であると高い確率で確信することができ、したがってＱＫＤ方法および装置はＯＴＰデータを機密に補充するのに非常に適している。
【０１０５】
公知のＱＫＤ装置において、ランダムに偏光された光子は送信装置から受信装置に光ファイバケーブル又は自由空間を介して送信され、これらＱＫＤ装置は通常公知のＢＢ８４量子符号化プロトコル（Ｃ．Ｈ．ＢｅｎｎｅｔｔおよびＧ．Ｂｒａｓｓａｒｄによる「Ｑｕａｎｔｕｍ Ｃｒｙｐｔｏｇｒａｐｈｙ：Ｐｕｂｌｉｃ Ｋｅｙ Ｄｉｓｔｒｉｂｕｔｉｏｎ ａｎｄ Ｃｏｉｎ Ｔｏｓｓｉｎｇ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒｓ Ｓｙｓｔｅｍｓ ａｎｄ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ、インド国バンガロール市、１９８４年１２月、１７５〜１７９ページ参照）に基づいて動作する。ＢＢ８４プロトコル又はＱＫＤ送信器若しくは受信器の詳細は本発明の理解に必要ないため、本明細書においては詳細の大部分は省略してあるが、詳細が必要な場合、上記の文献又は類似の一般的に入手可能な文献を参照することにより容易に取得可能である。
【０１０６】
図２６はＱＫＤ装置の応用例を示し、ＱＫＤ装置は図４に示す装置を更に特化したものであり、対応する素子は同一の参照符号にアルファベット「Ｑ」を補足して示す。したがって、図２６に示すＱＫＤ装置は、量子信号チャネル４０Ｑ（雑音チャネル）および従来のチャネル４５Ｑ（誤りがない、又は誤り訂正される無線チャネル等の非量子信号チャネル）を介して通信を行うＱＫＤ送信装置２０Ｑ（当事者「アリス」に相当）およびＱＫＤ受信装置３０Ｑ（当事者「ボブ」に相当）を備える。ＱＫＤ送信装置２０Ｑは送信側処理装置２３Ｑを含み、ＱＫＤ受信装置３０Ｑは受信側処理装置３３Ｑを含む。処理装置２３Ｑおよび３３Ｑの各々は、対応する図４の処理装置２３および３３と同一の機能ブロック（図２６では図示せず）を備え、更に以下に説明する別の機能ブロックを備える。
【０１０７】
ＱＫＤ送信装置２０Ｑは、ＱＫＤ受信装置３０ＱのＱＫＤサブ受信装置５０２と量子信号チャネル４０Ｑおよび従来のチャネル４５Ｑを介して連動するＱＫＤサブ送信装置５０１（図２６において点線で示す）を有し、これによりランダムデータ集合ｍが送信装置２０Ｑから受信装置３０Ｑに送信され、ＱＫＤサブ受信装置５０２はランダムデータ集合ｍを誤り訂正すべき受信データｒとして出力する。
【０１０８】
ＱＫＤサブ送信装置５０１は、ＱＫＤ送信器２１Ｑ（光子を選択的に偏光する光学部材を提供する）、ランダムデータ源５０５、および送信側処理装置２３Ｑの機能ブロックとして設けられるＱＫＤ処理ブロック５０６を備える。ランダムデータ源５０５はランダムビット対を生成するが、その際、片面を銀めっきした反射鏡により光子を検出器に伝送／偏向して５０：５０の確率で「０」／「１」を生成する量子ベースの装置等のハードウェア乱数生成器によりランダム性を実現するが、その他の乱数生成器として、抵抗器又はダイオードをオーバドライブさせ、電子雑音を利用してランダム事象を誘起するような構成とすることも可能である。各ランダムビット対のうち一方が現在のタイムスロット内で送信器２１Ｑにより送信されるビット値を決定し、他方のビットがビット値の送信に用いる偏光基底を決定する。
【０１０９】
なお、ＱＫＤ送信器２１ＱおよびＱＫＤ受信器３１Ｑが共有するデータ集合ｍは、送信器２１Ｑにより送信されるビット値の非決定性サブセットであり、このサブセットは、以下のようなビット値を備える。
【０１１０】
ＱＫＤサブ受信装置５０２が対応するタイムスロット内で量子信号チャネル４０Ｑを介して信号を受信したもの。
【０１１１】
ＱＫＤサブ送信装置５０１およびＱＫＤサブ受信装置５０２が同一の偏光基底をランダムに用いる（例えばチャネル４０Ｑの誤り率を決定する際に従来のチャネルを介して送信されるビット値より低い）。ＱＫＤ処理ブロック５０６の役割は、送信器２１Ｑにより送信されるビット値、および従来のチャネル４５Ｑを介して受信するＱＫＤサブ受信装置５０２における信号受信およびＱＫＤサブ受信装置５０２が用いる基底に関する情報に基づいて、データ集合ｍの内容を決定することである。
【０１１２】
ＱＫＤサブ受信装置５０２は、ＱＫＤ受信器３２Ｑ（光子を受信し、その偏光を検出する光学部材を提供する）および受信側処理装置３３Ｑの機能ブロックとして設けられるＱＫＤ処理ブロック５０９を備える。ＱＫＤサブ受信装置５０２において、連続するタイムスロットにおいて使用される偏光基底は、片面を銀めっきした反射鏡を用いて入射する光子を検出器にランダムに誘導し、少なくとも１個の偏光基底を形成することによりランダムに選択される。ＱＫＤ処理ブロック５０９の役割は、受信されるビット値および従来のチャネル４５Ｑを介して受信される正しい基底が用いられたタイムスロットを特定する情報に基づいて受信データｒを決定することである。
【０１１３】
その後、図４〜図２５を参照して上述した方法により受信データｒの訂正が実行され、これによりＱＫＤ受信装置３０Ｑがランダムデータ集合ｍを復元できる。
【０１１４】
ＱＫＤ送信装置２０Ｑは、メモリ内に記憶され、送信側処理装置２３ＱのＯＴＰ制御機能ブロック５０７により制御されるワンタイムパッド５０３を保持し、同様に、ＱＫＤ受信装置３０Ｑは、メモリ内に記憶され、受信側処理装置３３ＱのＯＴＰ制御機能ブロック５１０により制御されるワンタイムパッド５０４を保持する。ＱＫＤ送信装置２０ＱおよびＱＫＤ受信装置３０Ｑが共有するランダムデータ集合ｍは、ワンタイムパッド５０３および５０４の内容が相互に整合し続けるようワンタイムパッド５０３および５０４を補充するために用いられる。
【０１１５】
ワンタイムパッド５０３および５０４から取得したデータはＱＫＤ送信装置２０ＱおよびＱＫＤ受信装置３０Ｑを相互に認証し、また、受信データｒに適用する誤り訂正処理に用いる疑似乱数生成器をランク付けするために用いる。実際には、非効率的ではあるが、ワンタイムパッドからのデータは誤り訂正処理において求められるランダム性を実現する手段として直接利用してもよい。
【０１１６】
以下に、ワンタイムパッド５０３、５０４を補充するためのＱＫＤ送信装置２０ＱおよびＱＫＤ受信装置３０Ｑの相互作用および動作の全体的流れを、図２７Ａおよび図２７Ｂを参照して説明する。便宜上、以下においてはアリスおよびボブが工程を実行するとして説明するが、対象の工程は実際にはＱＫＤ送信装置２０ＱおよびＱＫＤ受信装置３０Ｑによりそれぞれ実行されるものとし、更に、図２７Ａおよび図２７Ｂにおいて、特定の工程に関してブロック体の大文字で示すアリスおよび／又はボブ名前は、場合に応じて、その工程において対応する装置２０Ｑおよび／又は３０Ｑが能動的に関与することを示す。
【０１１７】
初期の認証段階（図２７Ａにおける工程５１４〜工程５２２）において、アリスは従来の通信チャネル４５Ｑを用いてボブと通話を開始し、アリスはボブに自己が誰であるか伝え、ボブはアリスに自己が誰であるか返答する。
【０１１８】
本例によれば、この認証はワンタイムパッド５０３、５０４からのデータを用いて行われる。説明の便宜上、ワンタイムパッドは「ａ‖ｂ‖ｃ‖ＯＴＰの残存部」からなると考えられ、この場合ａ、ｂ、およびｃはそれぞれ例えば６４ビットである（記号‖は文字列連結を表す）。工程５１４において、アリスは（ａ）ＸＯＲ（ｂ）をボブに送信し、この場合、ＸＯＲは排他的論理和機能である。工程５１６において、ボブは整合するものを求めて自己のワンタイムパッド５０４を検索する。整合するものが見つかると、ボブは工程５１８においてアリスに（ａ）ＸＯＲ（ｃ）を送信し返す。工程５２０において、アリスはそれが正しい応答かチェックする。その後、アリスおよびボブの両方は、工程５２２において自己のワンタイムパッド５０３、５０４から「ＯＴＰの残存部」を残してａ、ｂ、およびｃを消去する。
【０１１９】
次に、ＱＫＤ送信および処理段階が実行される（工程５２４〜工程５４１）が、本例においては、以下に説明するように、ＢＢ８４量子符号化プロトコルを変更したものを用いる。
【０１２０】
アリスおよびボブは、データユニットを出力するタイムスロット長について所定の了解を得ているものとする。初期同期を実行するため、アリスは工程５２４において量子信号チャネルを介して光子パルスを送信する。
【０１２１】
工程５２６において、アリスは多数の、通常は約１０８対程のビット対を（データ源５０５を用いて）ランダムに生成する。上述したように、各ビット対はデータビットおよび基底ビットからなり、基底ビットはデータビットを送信するための、垂直方向／水平方向又は対角方向／反対角方向からなる偏光方向の対を示す。水平方向又は対角方向に偏光された光子は二進数の１を示し、垂直方向又は反対角方向に偏光された光子は二進数の０を示す。したがって、各対のデータビットは同一対の基底ビットが示す偏光方向の対に基づいて符号化され、アリスにより量子信号チャネル４０Ｑを介して送信される。アリスから量子信号を受信すると、ボブは各タイムスロットにおいて、どの基底（偏光方向の対）を用いて量子信号を検出するかランダムに選択し、結果を記録する。量子チャネルを用いて行う必要のある通信は、ランダムに生成されたビット対のデータビットの送信のみである。
【０１２２】
工程５２８において、ボブは、実際には送信全体の１０％等ランダムに選択できる量子信号送信の一部における全受信データを従来のチャネル４５Ｑを介してアリスに送信し、これにより、アリスは量子信号チャネル４０Ｑの誤り率を決定できる。受信データは信号が受信されたタイムスロット、そのタイムスロットの各々において受信された際に決定されたデータビット値、およびその際の基底（すなわち偏光方向の対）を含む。工程５３０において、アリスはボブから受信したランダムに選択された送信の１０％に関する受信データを用いて、ボブが信号を受信し、かつ正しい基底を用いたタイムスロットについてチャネル４０Ｑの誤り率を決定する。
【０１２３】
工程５３２において、アリスは工程５３０において導出した誤り率に基づいて、量子信号が盗聴されたか否か決定する。誤り率が高ければ高い程、量子信号が盗聴された確率が高く、一般的に約１２％より高い誤り率は許容の範囲外であり、好ましくは８％の上限を設定する。誤り率が閾値である８％より高い場合、そのセッションは放棄され（工程５３４）、アリスは従来のチャネル４５Ｑを介してボブに受信した量子信号データを破棄するよう伝える。
【０１２４】
誤り率が閾値である８％より低い場合、アリスは従来のチャネル４５Ｑを介してボブに誤り率を送信し、その後、アリスおよびボブの両者はこの誤り率を上述した方法で用いて誤り訂正に用いるシンドロームサイズを決定する。アリスおよびボブの両者は誤り率の決定に用いたデータ値を破棄する。
【０１２５】
工程５３８において、ボブは、量子信号送信の残りの部分（例えば残りの９０％）における部分的受信データを従来のチャネル４５Ｑを介してアリスに送信し、この部分的受信データは信号を受信したタイムスロットおよびその際の基底（すなわち偏光方向の対）を含むが、受信された際に決定されたデータビット値は含まない。
【０１２６】
工程５４０において、アリスは、ボブが量子信号を受信し、かつ正しい基底を用いて受信したビット値を決定したタイムスロットに対して送信されたデータビット値ｍを決定する。アリスはまた、データビット値ｍを保持するタイムスロットを特定する情報を、従来のチャネル４５Ｑを介してボブに送信する。工程５４１において、ボブは受信データｒを形成するデータビット値を決定する。
【０１２７】
動作の次の段階（図２７Ｂにおける工程５４２〜工程５５０）は、図４〜図２５を参照して上述した方法による受信データｒの誤り訂正である。したがって、工程５４２において、アリスおよびボブは使用するターゲットシンドロームのサイズを決定し、その後、トロイダルウェブクラスの任意の又は同意したサブクラスからなる同一のグラフを独立して生成する。
【０１２８】
工程５４４において、アリスは、工程５４２において生成したグラフを用いてデータｍからターゲットシンドロームＳを決定し、また、ｍに対してチェックサムを計算する。アリスは、ターゲットシンドロームＳおよびチェックサムを従来のチャネル４５Ｑを介してボブに送信する。
【０１２９】
工程５４６において、ボブはＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを用いて受信データｒに対する誤り訂正を実行する。誤り訂正が失敗した場合（ここで、終盤ルーチン１７９の関連する検査は工程１５４で実行されると図示してあり、ターゲットシンドロームＳおよびｍから形成されるチェックサムの整合性をチェックする検査を含む）、ボブは工程５５０においてアリスにデータｍを破棄するよう伝え、ボブは受信データｒを破棄する。
【０１３０】
誤り訂正が成功して、アリスおよびボブの両者が量子信号チャネル４０Ｑを介して共有される新しいランダムデータｍを得た場合、アリスおよびボブの両者は同一のプライバシー増幅工程５５２を実行する。なお、この点において、工程５３２において実行される誤り率に基づく盗聴チェックにより量子信号送信のどの部分における盗聴も検出できるが、あるタイムスロットにおいて２個以上の光子が量子チャネルを介して送信されるという（非常に小さいものの）有限の確率が存在し、これにより、ボブが光子の一方を受信する一方で、ビームスプリッタを備える盗聴者が他方の光子を受信できるという可能性が残るため、盗聴者が量子信号のうち多少のビットの盗聴に成功する可能性がある。プライバシー増幅工程５５２を実行するのは、そのような盗聴者への情報漏洩の可能性を解消するためである。
【０１３１】
プライバシー増幅工程５５２において、アリスおよびボブはそれぞれ新しく共有した秘匿なデータｍのサイズを、必要な安全性のレベルに応じて、決定性を有するランダム置換を用いて縮小する。
【０１３２】
プライバシー増幅の結果、アリスおよびボブは非常に高い確率で同一の結果ｍ’を得る。しかしながら工程５５４において、アリスおよびボブは本当にそうであるかどうか、新しく共有した秘匿データｍ’のハッシュ値を交換することによりそれぞれ再確認するが、その際、送信されるハッシュ値を保護および認証するため、自己のワンタイムパッド５０３、５０４から選択したビットによりハッシュ値の排他的論理和をとる。ハッシュ値が異なる（工程５５６において確認する）場合、新しく共有したデータｍ’は破棄する（工程５５８）。
【０１３３】
交換したハッシュ値が整合する場合、アリスおよびボブは同一の新しい共有データｍ’を有すると再確認したことになり、それぞれ、新しいデータｍ’を自己のワンタイムパッド５０３、５０４の既存の内容に統合開始する。この統合処理においては、ハッシュ値機能を用いて、外部観測者がワンタイムパッド内の最終的に共有される秘匿なデータについて何ら知らないこと保証する。実際には、統合の前にワンタイムパッドに十分なデータ量が残っている場合、統合動作により十分に不明瞭化でき、ほとんどの場合、プライバシー増幅工程５５２および続く工程５５４は省略してもよい。
【０１３４】
その後、補充後のワンタイムパッドからのデータを用いて、例えば、送信装置２ＯＱおよび受信装置３ＯＱ間で従来のチャネルを介して行われるアプリケーションデータの交換を暗号化するためのセッション鍵（例えば、１２８ビットのセッション鍵）を生成してもよく、セッション鍵の作成に使用されたデータはワンタイムパッドから破棄される。
【０１３５】
上述のＱＫＤ方法は本発明の一例であり、図２７に示した本例の工程は（当業者には明らかな境界の範囲内で）変更および／又は異なる順序で実行してもよいこととする。
【０１３６】
図４〜図２５を参照して上述した誤り訂正方法に関しては、当然ながら様々な変更が可能である。例えば、処理を最小限に抑える目的で、ターゲットシンドロームのサイズはチャネル４０の誤り率に基づいて動的に決定されると記載したが、あるいは、全ての可能な誤り率を処理できる所定のシンドロームサイズを選択して動作を行ってもよく、この場合、その他のグラフパラメータも全て同様に規定値である場合、グラフ作成はグラフパラメータデータを交換することなく実行可能である。
【０１３７】
上述の記載において、誤り訂正グラフは、送信装置２０および受信装置３０により各対象データ項目ｍ（又は対象データ項目集合）に対して動的かつ独立して作成されるが、トロイダルウェブクラスのグラフは以下のような装置に用いてもよい。
【０１３８】
用いられる誤り訂正グラフが固定であって、送信装置および受信装置内にプレインストールされている装置。
【０１３９】
送信装置および受信装置のうち一方のみがグラフを生成し、形成されたグラフは他方の装置に送信される装置。
【０１４０】
および、ターゲットシンドロームが、例えばトロイダルウェブクラスの誤り訂正グラフが標準的な線形ブロック符号に基づく誤り訂正装置で使われた場合のようにゼロベクトル等の規定値である装置。
【技術分野】
【０００１】
本発明は、データ通信装置において、雑音を発生するチャネルである雑音チャネル（ｎｏｉｓｙ ｃｈａｎｎｅｌ）を介して送信されるデータの誤り訂正に使用するデータ処理装置に関し、詳細には、量子鍵配送（ＱＫＤ：Ｑｕａｎｔｕｍ ｋｅｙ ｄｉｓｔｒｉｂｕｔｉｏｎ）方法および装置に関するが、これに限定されるものではない。
【背景技術】
【０００２】
ＱＫＤ方法および装置の開発により、非常に高い盗聴者検出率を有する方法で２つの当事者がランダムデータを共有することが可能である。すなわち、盗聴者が検出されない場合、当事者は、共有するランダムデータが秘匿であると高い確率で確信できる。ＱＫＤ方法および装置は、例えば特許文献１〜３に記載されている。例えばＢＢ８４プロトコルに基づく自由空間を利用した装置等、多くの公知のＱＫＤ装置において、ランダムに偏光した光子を送信装置から受信装置に送信する。
【０００３】
用いられるＱＫＤ装置がどのようなものであっても、ＱＫＤ方法は通常、ランダムデータ集合を、量子信号チャネルを介してＱＫＤ送信器からＱＫＤ受信器に送信し、その後、ＱＫＤ送信器および受信器は、量子信号チャネルを介して送受信したデータを、安全性の低い従来の通信チャネルを介してＱＫＤ送信器および受信器間で交換したメッセージを用いてそれぞれ処理し、ランダムデータ集合の共有サブセットを抽出する。量子信号チャネルは雑音を含むため、このチャネルを介して受信されるデータの処理は、誤り訂正する段階を含む。しかしながら、線形ブロック符号を用いたデータの符号化／復号等の標準技術では、送信される光子のうち数パーセントしか受信されないため、量子信号チャネルを介して送信されるデータの誤り訂正は無理である。代わりに、量子信号チャネルを介して送信されるデータの誤り訂正は、誤りがない、又は標準的な誤り訂正技術により誤りをなくした従来のチャネルを介して交換されるメッセージに依存する。従来の通信チャネルは、ランダム化技術により情報の漏洩を最小限にできるため、機密である必要がない。仮に従来のチャネルが機密であったとしても、盗聴者を検出する特性は有しておらず、したがって量子信号チャネルの代わりに用いることはできないと考えられる。
【０００４】
本発明は誤り訂正に関し、とりわけ、量子信号チャネルを介して送信されるランダムデータの訂正に用いることが可能である。
【０００５】
従来の通信チャネルを介して送信されるデータの誤り訂正を実行する際に線形ブロック符号を用いることは、公知である。簡単に説明すると、添付の図面の図１に示すとおり、雑音チャネルを介して送信するメッセージを各々がｋ個のシンボルからなるデータブロックｍに分割するが、このシンボルは通常２進ビットであり、以下においては、別途記載のない限り２進ビットからなるものとする。各メッセージブロックはｋビットの行ベクトルｍとして表すことができる。各メッセージブロックは符号器１１において対応するｎビットの符号語（行ベクトルｃで表す）に符号化され、この場合ｎ＞ｋである。使用する符号語ｃは、所定の符号語集合（「符号」Ｃ）から選択する。ｋビットのメッセージブロックおよびｎビット符号語の場合、対応する符号Ｃは（ｎ，ｋ）符号と称する。メッセージブロックｍを対応する符号語ｃに符号化した後、その符号語を雑音チャネル１０を介して送信器１３により送信し、チャネル終端において受信器１４で受信し、受信器からｎビットの受信語（行ベクトルｒで表す）として出力する。チャネル１０を介した送信において誤りが全く発生しない場合、受信語ｒは送信された符号語ｃに当然一致し、受信語ｒを元のメッセージブロックｍに変換するため復号器１２にそのまま送信される。しかしながら、一般的には受信語ｒは送信された符号語ｃには一致しないが、それでも復号器１２が、符号器１１が用いる符号Ｃを認識しており、かつ誤りの数が限られている場合、復号器１２はメッセージブロックｍを復元できる。
【０００６】
線形ブロック符号は生成器およびパリティ検査行列により定義される。詳細には、線形ブロック符号Ｃは対応するパリティ検査行列Ｈのゼロ空間により定義され、符号Ｃの各符号語ｃとパリティ検査行列Ｈの転置の積は以下のようにゼロベクトルとなる。
ｃ・ＨＴ＝０
添付の図面の図２は、（７、３）線形ブロック符号のパリティ検査行列Ｈ１の例を示す。図２に示すパリティ検査行列Ｈ１に対応する符号は、正則（ｒｅｇｕｌａｒ）「低密度パリティ検査」又は「ＬＤＰＣ（ｌｏｗ ｄｅｎｓｉｔｙ ｐａｒｉｔｙ ｃｈｅｃｋ）」符号と呼ばれるものであり、この名前はパリティ検査行列が疎行列であることを反映しており、「正則」という形容詞は、全ての行が同一の重みを有し、全ての列もまた同一の重みを有することを表す。ＬＤＰＣ符号は、サイズが大きいメッセージブロックとの使用に特に望ましい。
【０００７】
受信語ｒとパリティ検査行列の転置の積はｒの誤りシンドロームと呼ばれ、本明細書においてはベクトルＳで表し、次式が成り立つ。
Ｓ＝ｒ・ＨＴ
誤りシンドロームＳがゼロの場合は当然、受信語ｒは符号語ｃである。
【０００８】
実質的に、パリティ検査行列Ｈの各行は有効な符号語ｃと判断されるために受信語ｒが満たすべき制約を定義する。より詳細には、各行は受信語ｒにおいて値をモジュロ２加算（二進数シンボルの場合）するとゼロとなるべきビット位置を示す。言い換えると、パリティ検査行列の各行が示すモジュロ２加算の結果が誤りシンドロームの対応するビットを生成する。
【０００９】
パリティ検査行列Ｈの行により定義される制約集合はタナーグラフとして知られる二部グラフにより図で表現することができ、このグラフは、
各々が入力変数（ここでは受信語ｒ）の各ビット位置に対応する第１のノード群（本明細書において「変数」ノードと称し、アルファベットの「ｖ」で示す）と、
各々が各モジュロ２加算、およびしたがってパリティ検査行列の各行に対応する第２のノード群（本明細書において「総和（ｓｕｍ）」ノードと称し、非太字のアルファベットｓで示す）と、
各総和ノードｓをパリティ検査行列の対応する行に基づいて選択される各変数ノードｖに接続するエッジとを備える。
モジュロ２加算により総和ノードｓで生成される値および接続される入力変数（受信語ｒ）のビット位置の値により誤りシンドロームＳが得られる。添付の図面の図３は、図２に示すパリティ検査行列Ｈ１のタナーグラフ１５を示し、このグラフは７個の変数ノード１６（ｖ１〜ｖ７の記号で示す）、７個の総和ノード１７（ｓ１〜ｓ７の記号で示す）、およびエッジ１８を備える。
【００１０】
タナーグラフはすべて、変数ノードおよび総和ノードが、その他の視覚的ネットワーク配置図ではなく、グラフにより構築されるノードおよびエッジからなるネットワークにおいて相互接続することを特徴とするものと考えられ、例えば、タナーグラフ１５の変数ノードｖ１〜ｖ７を、入力変数のビット位置に対する変数ノードｖ１〜ｖ７の対応性又は総和ノードに対する各変数ノードの相互接続を変更することなく、図３に示す順番と異なる順番で配置しても、単に視覚的表現が変わるだけでタナーグラフが変化する訳ではない。この表現は当然視覚的である必要はなく、詳細には、コンピュータ環境においては理論的表現（ノードの種類および他のノードとの接続を示すノードのリスト等）からなっていてもよく、これは、グラフを作成又はグラフを用いて動作する処理装置が記載されている以下の本発明の説明にも適用されることする。
【００１１】
受信語ｒが少なくとも１個の誤りを含むか否かは誤りシンドロームＳが非ゼロか否かチェックすることにより容易に決定できるが、誤り訂正はより複雑である。誤り訂正方法（例えばＬＤＰＣ符号との使用に適する）の一つに、反復的確率伝搬法又は「Ｓｕｍ−Ｐｒｏｄｕｃｔ」アルゴリズムとしても知られる確率論的反復復号法がある。この方法は、引用することにより本明細書に組込む非特許文献１等、様々な参考文献に記載されており、上記の文献はインターネット上においてwww.inference.phy.cam.ac.uk/mackay/itila/book.htmlでも入手可能である。
【００１２】
このＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムは、パリティ検査行列により定義される制約の上述のようなグラフ表現に対応するノードおよびエッジからなるネットワークに基づく。より詳細には、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムは、入力変数（受信語ｒ）の対応するビットが特定の値（ゼロ等）である確率に対応する確率を、各変数ノードｖに事前に与える。この確率は受信語ｒを受信したチャネルの誤り率に依存し、例えば、チャネル誤り率が０．０５であった場合、受信語ｒにおける「０」が実際に「０」である確率は０．９５であり、受信語ｒにおける「１」が実際には「０」である確率は０．０５である。
【００１３】
各総和ノードｓは、変数ノードに符号語が提示されると総和ノードが生成する値に対応する出力値を与えられ、上述の条件において、この値は当然ゼロである。全総和ノードに対する出力値からなる順序集合は、本明細書においては、任意の誤りシンドローム値に対応することから「ターゲットシンドローム」Ｓと称し、すなわち、上述の条件においてはゼロベクトルである。
【００１４】
その後、確率は一連のサイクルでノード間でエッジに沿って交換され、各サイクルの度に、変数ノードの入力値が制約を満たす値（すなわち、ターゲットシンドロームに整合する総和ノードの出力値に一致する値）を取ることにより収束が得られるまで、変数ノードに与えられる確率が調節される。各サイクルは、以下の２個の段階を備える。
【００１５】
段階１：各変数ノードから接続する総和ノードにメッセージが送信され、これにより、各総和ノードは接続する各変数ノードに現在与えられている確率を知る。次に、各総和ノードは、接続する各変数ノードに対して、与えられている総和ノードの出力値およびその他の接続する変数ノードから受信する確率に基づいて、対象の変数ノードが前述の特定の値を有する確率を決定する。
【００１６】
段階２：各総和ノードから接続する変数ノードにメッセージが送信され、これにより、各変数ノードは接続する各総和ノードにより自己に対して現在決定されている確率を知る。次に、各変数ノードは、接続する総和ノードから受信した確率に基づいて自己に新しい確率を与える。
最終的には、各変数ノードにおける確率は、グラフにより設定される制約を満たす対応する入力値を示す推定値「１」又は「０」として収束および安定する必要がある。
【００１７】
以上においてＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを確率の観点から記載したが、この確率は直接的な確率の他に様々な方法で表わしてもよく、例えば、対数確率、又は尤度／対数尤度を用いることも同様に可能である。本明細書における、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムにより制御される確率に関する記載は、そのような他の表現方法も含むものとする。
【００１８】
上述したように、「ターゲットシンドローム」は受信語ｒに対応する符号語ｃを読出す場合ゼロ値を有する。しかしながら、それに制限されるものではない。例えば、ターゲットシンドロームは実際には誤りシンドローム自体であって、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを用いて雑音ベクトルに対する値を抽出してもよい（上述の参考文献の図４７．２ｃおよび５５８、５５９ページを参照）。
【先行技術文献】
【特許文献】
【００１９】
【特許文献１】米国特許第５，５１５，４３８号
【特許文献２】米国特許第５，９９９，２８５号
【特許文献３】英国特許出願公開公報２４２７３１７号
【非特許文献】
【００２０】
【非特許文献１】Ｄａｖｉｄ Ｊ． Ｍａｃｋａｙ著、「Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， Ｉｎｆｅｒｅｎｃｅ ａｎｄ Ｌｅａｒｎｉｎｇ Ａｌｇｏｒｉｔｈｍｓ」、Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ出版、２００３ ＩＳＢＮ０５２１６４２９８１、５５９ページ
【発明の概要】
【課題を解決するための手段】
【００２１】
本発明の一特性によれば、２進データ集合から選択される各データビットをモジュロ２加算した複数の順序演算結果を抽出する処理装置を備え、この選択は、有限トロイド（ｆｉｎｉｔｅ ｔｏｒｏｉｄ）を覆うセルの連続体を少なくとも定義するノードおよびエッジからなる論理ネットワークにおける総和ノードの変数ノードへの接続に基づいており、該セルの各々は、交互に配置され、エッジによりループ状に相互接続する同一数の変数ノードおよび総和ノードにより区切られており、変数ノードの各々は２進データ集合のビット位置にそれぞれ対応し、総和ノードの各々はモジュロ２加算した演算結果にそれぞれ対応するデータ通信装置を提供する。
【００２２】
本発明の他の特性によれば、反復的確率伝搬法を適用して受信される２進データ集合のビット値尤度を調節し、これにより受信されるデータ集合から選択される各ビットの推定値をモジュロ２加算した複数の順序演算結果がターゲットシンドロームと整合する誤り訂正装置であって、この選択は、有限トロイドを覆うセルの連続体を少なくとも定義するノードおよびエッジからなるネットワークにおける総和ノードの変数ノードへの接続に基づいており、該セルの各々は、交互に配置され、エッジによりループ状に相互接続する同一数の変数ノードおよび総和ノードにより区切られており、変数ノードの各々は受信されるデータ集合のビット位置にそれぞれ対応し、総和ノードの各々はモジュロ２加算した演算結果にそれぞれ対応する誤り訂正装置を提供する。
【００２３】
以下に、例示のみを目的として、実施例を示す添付の図面を参照して本発明を説明する。
【図面の簡単な説明】
【００２４】
【図１】図１は、雑音チャネルを介して公知の方法により送信するためのメッセージの符号化処理を示す図である。
【図２】図２は、公知の形態のパリティ検査行列の例を示す。
【図３】図３は、図２に示すパリティ検査行列に対応するタナーグラフを示す。
【図４】図４は、本発明の実施の形態による装置の一般的な形態を示す図である。
【図５】図５は、図４に示す装置により実行されたＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムにおける失敗率の、異なるチャネル誤り率に対するターゲットシンドロームサイズへの依存性を示すグラフである。
【図６】図６は、セルが平面方向に伸長して円環状に接続されてトロイダル連続体を形成する様子を示す図である。
【図７】図７は、エッジにより相互接続して、円環状に接続されてトロイド面を形成する１２個の六角形セルを定義する変数ノードおよび総和ノードからなるネットワークを示す図である。
【図８】図８は、図７に示すノードおよびエッジからなるネットワークにより定義される制約をタナーグラフ表現したものである。
【図９】図９は、ノードおよびエッジからなるクモ構造をトロイダル連続体に付加することにより伸長した図７に示すネットワークを示す図である。
【図１０】図１０は、図１０に示すノードおよびエッジからなるネットワークにより定義される制約をタナーグラフ表現したものである。
【図１１】図１１は、図９に示すノードおよびエッジからなるネットワークにより定義される制約をパリティ検査行列表現したものである。
【図１２】図１２は、複数の十字型セルを定義するノードおよびエッジからなるネットワークを示す図である。
【図１３】図１３は、オフセット配置される６個のノードからなる矩形セルを定義するノードおよびエッジからなるネットワークを示す図である。
【図１４】図１４は、非オフセット配置される６個のノードからなる矩形セルを定義するノードおよびエッジからなるネットワークを示す図である。
【図１５】図１５は、図４に示す装置により実行されたＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムにおける失敗率の、異なるネットワーク構成に対するターゲットシンドロームサイズへの依存性を示すグラフである。
【図１６】図１６は、図１４に示すセルの好ましい配置をノードおよびエッジからなる標準ビルディングブロックから形成する方法を示す図である。
【図１７】図１７は、図４に示す装置の受信装置の動作を示すフローチャートである。
【図１８】図１８は、図１７に示すフローチャートの誤り訂正段階において実行される終盤ルーチンの好ましい形態を示すフローチャートである。
【図１９】図１９は、シンドローム誤りパターンの候補を示す図である。
【図２０】図２０は、シンドローム誤りパターンの候補を示す図である。
【図２１】図２１は、シンドローム誤りパターンの候補を示す図である。
【図２２】図２２は、シンドローム誤りパターンの候補を示す図である。
【図２３】図２３は、シンドローム誤りパターンの候補を示す図である。
【図２４】図２４は、シンドローム誤りパターンの候補を示す図である。
【図２５】図２５は、シンドローム誤りパターンの候補を示す図である。
【図２６】図２６は、本発明の実施例による量子鍵配送（ＱＫＤ）装置の概略図である。
【図２７Ａ】図２７Ａは、図２７Ｂとともに、図２６に示すＱＫＤ装置の動作方法の例を示す機能フローチャートである。
【図２７Ｂ】図２７Ｂは、図２７Ａとともに、図２６に示すＱＫＤ装置の動作方法の例を示す機能フローチャートである。
【発明を実施するための形態】
【００２５】
以下においてはまず、本発明の実施例を図４に示す一般的な条件を参照して説明し、量子鍵配送という特定の条件の適用については、図２６および図２７を参照して後に説明する。
【００２６】
図４に示す装置において、対象データ（本明細書においては行ベクトルｍで表す２進データ集合）は、送信装置２０の第１の送信器２１により第１の雑音チャネル４０を介して受信装置３０の第１の受信器３２に送信され、第１の受信器３２の出力は誤りを含む受信データ（本明細書においては行ベクトルｒで表す２進データ集合）となる。便宜上、行ベクトルｍおよびｒを用いて対象データおよび受信データを表すが、これは第１のチャネル４０が、そうである場合が多いとは言え、ビットシリアルチャネルであることを意味するものではない。
【００２７】
送信側処理装置２３および受信側処理装置３３が連動することにより、受信側処理装置３４の誤り訂正ブロック３４は受信データｒにおける誤りを訂正でき、これにより元の対象データｍを復元できる。送信側処理装置２３および受信側装置３３は、データ項目（本明細書においては一般的に「補助」データと称する）を、それぞれ送受信器２２および３２を介して第２のチャネル４５を介して相互に送信できる。チャネルの信頼性が高く誤りが発生しないため、又はより典型的には、送受信器２２、３２が受信側の送受信器から確実に誤りのなく出力するのに適した技術（例えば、誤り検出と誤りデータ項目の再送を組合せたもの、線形ブロック符号又はその他の方法を用いて誤り訂正を実行するもの等）を採用しているため、各送受信器２２、３２により対応する処理装置２３、３３に出力される受信データ項目は誤りを含まない。
【００２８】
一般論として、送信側処理装置２３および受信側処理装置３３は以下のように連動して受信データｒの誤りを訂正する。
【００２９】
１．処理装置２３、３３は同一のタナーグラフに基づいて動作、すなわち、同一のタナーグラフのノードおよびエッジに対応する相互接続する変数ノードおよび総和ノード論理のネットワークに基づいて、演算を実行する。タナーグラフは固定ではないが、以下により詳細に説明するように、疑似ランダムではあるが、決定性を有する方法で対象データｍの各項目（又は項目群）に対して、各処理装置２３、３３により独立して作成される。
【００３０】
２．送信側処理装置２３は、タナーグラフを用いて対象データｍからターゲットシンドロームＳを演算、すなわち、対象データｍのビットがタナーグラフにより指定される論理ネットワークの変数ノードに適用される値を定義し、論理ネットワークの総和ノードにおいてモジュロ２加算により生成される値の順序集合がターゲットシンドロームＳを形成する。
【００３１】
３．ターゲットシンドロームＳは、送信側処理装置２３により補助データとしてチャネル４５を介して受信側処理装置３３に送信される。
【００３２】
４．受信側処理装置３３の誤り訂正ブロック３４はＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズム（反復的確率伝搬法）を論理ネットワークに適用するが、この論理ネットワークは、送信側処理装置２３から受信するターゲットシンドロームＳにより設定される総和ノードの出力値、および受信データｒのビット値およびチャネル４０の誤り率により設定される変数ノードの初期値を用いてタナーグラフにより指定される。
【００３３】
５．Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムは、誤り訂正ブロック３４により用いられる論理ネットワークの変数ノードにおいて、ターゲットシンドロームＳに一致する推定値を生成し、この推定値は対象データｍとして出力される。
【００３４】
処理装置２３および３３は通常、支援メモリおよびサブ入力／出力装置を備える、プログラム制御によるプロセッサの形式で設けられ、図４に示すとおり、機能的に以下のようなブロックを備える。
【００３５】
送信側処理装置２３の機能ブロック：
対象データｍの所定の選択されたビットをモジュロ２加算で演算した複数の順序付けされた演算結果を求めることによりターゲットシンドロームＳを決定するブロックであって、ビットの所定の選択は、局所的に作成されたタナーグラフにおける総和ノードの変数ノードへの接続により定義されるターゲットシンドローム決定ブロック２４；
ターゲットシンドローム決定ブロック２４用に、疑似ランダムではあるが決定性を有する方法でタナーグラフを生成するグラフ作成ブロック（別称、ネットワーク作成ブロック）２５；
シンドロームサイズ決定ブロック２７；および、
処理装置２３の送信側の動作および受信側処理装置３３との補助データの交換を制御する制御ブロック２６。
【００３６】
受信側処理装置２３の機能ブロック：
既に概略を上述した誤り訂正ブロック３４であって、反復的確率伝搬法を適用して受信データｒのビット値尤度を調節することにより受信データｒにおける誤りを訂正し、これにより、受信データｒの所定の選択されたビットの推定値をモジュロ２加算で演算した複数の順序付けされた演算結果が 送信側処理装置２３から受信したターゲットシンドロームＳに一致し、ビットの所定の選択は、ターゲットシンドローム生成に使用されたタナーグラフを局所的に作成したものであるタナーグラフにおける総和ノードの変数ノードへの接続により定義される、誤り訂正ブロック３４；
誤り訂正ブロック２４用に、疑似ランダムであるが決定性を有する方法によりタナーグラフを生成するグラフ作成ブロック（別称、ネットワーク作成ブロック）３５；および、
受信側処理装置３３の動作および送信側処理装置２３との補助データの交換を制御する制御ブロック３６。
【００３７】
ターゲットシンドローム決定ブロック２４および誤り訂正ブロック３４の一般的な動作は、当業者にとっては上述の記載から明らかであり、したがって、以下においては、誤り訂正ブロックがＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムが有効な一連の処理をいつ完了したか決定するための好ましい「終盤（ｅｎｄ ｇａｍｅ）」ルーチン（図１８および以下の関連する記載を参照）を除いては説明しない。代わりに、図４に示す実施の形態に関する記載の残りの部分においては主に、処理装置２３、３３のグラフ作成ブロック（別称、ネットワーク作成ブロック）２５、３５が、それぞれブロック２４および３４による使用に適合するタナーグラフを生成する方法を中心に説明する（なお、２個のグラフ作成ブロック２５、３５により対象データｍの任意の項目に対して生成されるグラフは同一の構成を有することとする）。詳細には、タナーグラフの、後に説明する理由から以下において「トロイダルウェブ（ｔｏｒｏｉｄａｌ ｗｅｂ）」クラスと称する一般的なクラスにそれぞれ属するグラフのサブクラスの様々な実施例の生成方法を（図６から図１７を参照して）説明する。タナーグラフのトロイダルウェブクラスは、構造が相対的に容易（したがって動的なグラフ作成に適する）で、得られるグラフに特定の特性を与える特に一般的な構造を有することを特徴とする。対応する疎なパリティ検査行列にマッピングできる上述のグラフは、例えば１メガビットの長さを有する大型のメッセージにおける誤りを反復的確率伝搬法（ＬＤＰＣ符号のタナーグラフを疎なパリティ検査行列にマッピングし、反復的確率伝搬法と組合せて実行するのに適した方法と同一の方法）により訂正するのに適している。
【００３８】
グラフ作成ブロック２５および３５は同一のグラフ構成アルゴリズムに基づいて動作するよう構成され、このアルゴリズムは、トロイダルウェブクラスグラフの事前選択されるサブクラスを作成するよう構成されることとするが、選択されたサブクラス内において、このアルゴリズムは様々なパラメータ値に応じて非常に多数の異なるタナーグラフを生成可能である。同一のグラフを生成するためには、グラフ作成ブロック２５、３５は同一のパラメータ値を使用する必要がある。そのようなパラメータは、
対象データ項目ｍのサイズ（この値は対象データ項目ｍ毎に異なっていてもよく、又は全対象データ項目ｍに対して事前に同一の特定の値に固定してもよい）と、
ターゲットシンドロームＳのサイズ、又はシンドロームサイズを決定するパラメータ値（この値も同様に固定値であってもよいが、以下から明らかなように、一般的には望ましくない）と、
グラフ作成の際に実行される所定の動作におけるランダム性を規定するパラメータとを含み、このパラメータは共有の秘匿なランダムデータ（例えば、共有のワンタイムパッドにより得られる）又は疑似ランダムであり決定性を有する数の生成器ＰＮＧの動作パラメータ（初期化ベクトル等）であってもよい（後者である動作パラメータ値は、定期的な同期チェック又は再初期化が望ましいものの、通常は固定値である）。
グラフ作成アルゴリズムのパラメータが動的に（すなわち、新しい対象データ項目ｍ毎、又は対象データ項目ｍ群毎に）決定される場合、この決定処理は通常、送信側処理装置２３およびチャネル４５を介して補助データとして受信側処理装置３３に伝送される値により実行されるが、適切な状況においては、受信側処理装置３３がパラメータ値を決定し、そのパラメータ値を送信側処理装置２３に送信してもよく、又は処理装置２３、３３間で使用する値を協議してもよい。
【００３９】
また、グラフ作成ブロック２５、３５により実行されるグラフ構成アルゴリズムを、トロイダルウェブクラスグラフの複数のサブクラス雑音れかを構成するよう構成してもよく、この場合、使用されるサブクラスは動的に決定されるグラフ作成パラメータの一つとなる。
【００４０】
図４に示す実施の形態に関する以下の説明において、シンドロームサイズのみが、各対象データ項目ｍ毎に新しく動的に決定されることとする。
【００４１】
より詳細には、送信側処理装置２３のブロック２７は、第１の雑音チャネル４０の現在の誤り率に基づいてシンドロームサイズを決定する。チャネル４０の誤り率は、既知の送信データを実際に受信したデータと比較することにより測定され、この比較処理は処理装置２３および処理装置３３のどちらにより実行してもよいが、本実施例においては送信側処理側のブロック２７により実行し、ブロック２７には、送信器２１から既知の送信データが、また受信側処理装置３３からチャネル４５を介して受信データが供給される。なお、誤り率の決定に使用されるデータは一般的に、対象データｍを、チャネル４０を使用して送信可能にする第１のチャネル４０の特定の特性を有していない（例えば、チャネル４０が量子信号チャネルである場合、チャネル４５はチャネル４０が有するような盗聴者を確実に検出する特性を有していない）チャネル４５を介して送信されるため、対象データｍとは異なっている（又は分離している）必要がある。
【００４２】
チャネル４０の誤り率を決定すると、ブロック２７はその誤り率を用いて任意のシンドロームサイズを決定し、その情報をグラフ作成ブロック２５および３５に送信する。又は、上述したように、ブロック２７は決定した誤り率を受信側処理装置３３に送信して、受信側処理装置３３自体がシンドロームサイズを決定するようにしてもよい（この決定処理はブロック２７と同一の方法で実行され、これによりグラフ作成ブロック２５、３５が同一のシンドロームサイズ値を得る）。
【００４３】
以下に、ブロック２７がチャネル４０の誤り率から任意のターゲットシンドロームサイズを決定する方法を、図５を参照して説明する。図５は、チャネル４０の異なる誤り率について、グラフ作成ブロック２５、３５により作成されるタナーグラフのサブクラスに適用される反復的確率伝搬法による処理（誤り訂正ブロック３４が用いる処理）における失敗率がシンドロームサイズに応じて異なる様子を示すグラフであり、この場合、失敗率とは、反復的確率伝搬法による処理において、タナーグラフの変数ノードにおいて、ターゲットシンドロームに一致する推定値の生成に失敗した場合をさす。図５において、シンドロームサイズは対象データｍのサイズに対する割合として表され、この割合は１００％より大きくてもよい。
【００４４】
図５は、チャネル４０の異なる誤り率にそれぞれ対応する３個の曲線５１、５２、５３を示し、最大の誤り率が曲線５１に対応し、最小の誤り率が曲線５３に対応する。各曲線５１〜５３は同一の略階段形状を有し、これは、ターゲットシンドロームが所定のサイズより小さい場合、失敗率は約１００％であり、シンドロームサイズ閾値より大きい場合、失敗率は低くなることを示している。曲線５１〜５３から分かるとおり、誤り率が増大するとシンドロームサイズ閾値も増大する。
【００４５】
シンドロームサイズ決定ブロック２７は、決定されるチャネル４０の誤り率に対して、シンドロームサイズ閾値より大きいシンドロームサイズを選択するよう構成され、これにより、誤り訂正ブロック３４が実行する反復的確率伝搬法による処理の失敗率を確実に低く抑えることができる。効率性の観点から、選択されるシンドロームサイズはサイズ閾値より数パーセントだけ大きいものとする。
【００４６】
以下において、各グラフ作成ブロック２５、３５が、対象データｍの任意のサイズｐ（ビット）およびターゲットシンドロームの任意のサイズｑ（ビット）に対応するタナーグラフのトロイダルウェブクラスの事前選択されるサブクラスのグラフを構成するために実行するグラフ構成アルゴリズムを考える。グラフ構成アルゴリズムは実際には、対象となるサブクラスに関わらず、エッジにより相互接続する変数ノードおよび総和ノード（すなわち、対象データｍの各ビットに対応する各変数ノードおよびターゲットシンドロームＳの各ビットに対応する各総和ノード）からなるネットワークを構成し、以下の２個の主段階を備える。
【００４７】
第１段階において、同一数の（ｐおよびｑのうち小さい方により決定される）変数ノードおよび総和ノードは有限トロイドを形成するセルの連続体内に配置され、各セルは、交互に配置され、エッジによりループ状に相互接続する同一数の変数ノードおよび総和ノードにより区切られている。
【００４８】
第２段階において、変数ノード又は総和ノードのうち一方（第１段階において全部が使用されていない方）のノードをそれぞれ備える複数の「クモ構造」が定義され、この変数ノード又は総和ノードのうち一方は、第１段階においてセルの連続体を定義する処理に用いられた変数ノード又は総和ノードのうち他方のノードからランダムに選択されたノードに所定数のエッジを介して接続される。
第２段階は、対象データのビット数ｐがターゲットシンドロームのビット数ｑと異なる場合のみ必要となる。変数ノードを総和ノードに有効に接続するのはエッジである。
【００４９】
上述のような一般的なグラフ構成アルゴリズムに基づいて作成可能なグラフは「トロイダルウェブ」クラスのグラフを形成し、この名前の重要性は今や明らかである。更に、グラフ構成アルゴリズムの第１段階において用いられるセルの形状および相互関係が、得られるグラフのサブクラスを決定する。
【００５０】
図６、図７、および図９は、対象データサイズｐが１５、およびターゲットシンドロームサイズｑが１２の場合の、「六角形」サブクラス（グラフ構成の第１段階で用いられるセルが六角形形状を有するため）のグラフを作成する実施例を簡略に示す。この場合、グラフ構成の第１段階において１２個の変数ノードおよび１２個の総和ノードにより１２個の六角形セル６１（図６参照）を形成し、この六角形セル６１は６個ずつ２列に配置されて端と端（矢印６３）および上と下（矢印６２）がそれぞれ接続されて円環のようになっており、有限トロイド面を形成するセルの連続体を形成する。図７はノードの配置をより詳細に示し、１２個の変数ノードはｖ１〜ｖ１２の記号で示し、１２個の総和ノードはｓ１〜ｓ１２の記号で示す。図から分かる通り、各六角形セルは交互に配置される３個の総和ノードおよび３個の変数ノードからなり、例えば、セル７７は、それぞれ変数ノードｖ１、総和ノードｓ１、変数ノードｖ２、総和ノードｓ８、変数ノードｖ７、および総和ノードｓ８からなるノード７１〜７６を備える。セルは共有のエッジを有し、これにより各ノードは実際には区切られた３個のセルで共有される。トロイド状のセルの連続体７０を形成するためにセルを円環状に接続する構造は、最上列のノード（ノードｖ１、ｓ１、ｖ２、ｓ２、ｖ３、ｓ３、ｖ４、ｓ４、ｖ５、ｓ５、ｖ６、ｓ６）を最下列のノードとして反復（点線で示す）し、最左列のノード（ｖ１、ｓ７、ｖ７、ｓ１）を最右列のノードとして反復するにより表す。
【００５１】
図８は、図７に示すノードおよびエッジからなるネットワークを、タナーグラフの図示においてより一般的に利用される形状８０（例えば図３において使用）に書き換えたものであり、変数ノードｖ１〜ｖ１２は上方で順番に配置され、総和ノードｓ１〜ｓ１２は下方で順番に配置される。図７においてセル７７を定義するエッジは、図８において太線（８１参照）で示す。なお、図７、およびしたがって図８は、本実施例に対して、部分的にのみ完成したグラフを表わしているものとする。
【００５２】
また、タナーグラフを図示する際、変数ノードの順序は一般的に対象データにおけるビットの順序に対応し、一方、図７に示すネットワークを書き換えたものである図８においては、変数ノードの順序は、以下に記載するように対象データｍにおけるビットの順序に対応する場合もしない場合もある、添字番号に基づく。図７に示すように変数ノードの番号が対象データｍの対応するビットの位置に一致しない場合、図７を、変数ノードを対象データｍの対応するビットの順序に基づいて順番に並べて書換えても、基底構造の規則性がはっきりと表れない可能性が高い。
【００５３】
グラフ構成の第２段階において、第１段階には関与しない３個の過剰な変数ノード（ノードｖ１３、ｖ１４、ｖ１５）は六角形セルからなるトロイダル連続体７０に接続される。この接続は以下のように実行される。３個の過剰な変数ノードｖ１３、ｖ１４、ｖ１５の各々は順次選択されて、自己を３個のランダムに選択される総和ノード（既にトロイダル連続体７０内に組込まれている）に接続するよう規定される。視覚的観点からすると、図９に示す通り、過剰な変数ノードｖ１３、ｖ１４、ｖ１５の各々は、自己をトロイダル連続体７０に接続する３個の脚を有するクモ構造９０の本体を形成し、したがって、図９は、総和ノードｓ１、ｓ１０、およびｓ１２に接続する過剰な変数ノードｖ１３、総和ノードｓ２、ｓ５、およびｓ９に接続する過剰な変数ノードｖ１４、総和ノードｓ６、ｓ８、およびｓ１１に接続する過剰な変数ノードｖ１５を示す。好ましくは、総和ノードを過剰な変数ノードにランダムに割当てる処理は、ランダムに構成した総和ノードのリストを作成し、各過剰な変数ノードｖ１３、ｖ１４、ｖ１５の各々に対して、作成したリストの最上位の３個組の総和ノードを順次選択することにより実行され、過剰な変数ノードに対して全てのクモ構造９０が作成される前にリストの総和ノードが使果たされた場合、総和ノードのリストを新しくランダムに構成して、残存する変数ノードに対して処理を繰返し実行する（処理は必要回数実行してもよい）。
【００５４】
シンドロームビット（すなわち総和ノード）の数ｑが対象データビット（すなわち変数ノード）の数ｐより大きい場合、上述のグラフ構成の第２段階において変数ノードおよび総和ノードの役割は逆になる。更に、各クモ構造における脚の数は３個に制限されるものではなく、好ましくは４個である。
【００５５】
上述の方法によりクモ構造を構成することにより、トロイダル連続体７０において「脚」が疑似ランダムではあるが非常に均等に配置され、正則（すなわち、効率的に構成可能）なトロイダル連続体７０にランダム性を付加する。
【００５６】
タナーグラフにおいて長さ４のサイクルは一般的に望ましくないため、好ましくは、新しくクモ構造９０が形成される度に長さ４のサイクルが作成されていないかチェックし、長さ４のサイクルが生成されていた場合、そのクモ構造は拒否され、代わりに新しいクモ構造が作成される。長さ４のサイクルのチェックは以下のように非常に単純である。
【００５７】
（ｉ）新しいクモ構造の「足先」（すなわち、クモ構造の本体を形成する過剰なノードに直接接続されるトロイダル連続体のノード）が、トロイダル連続体において、２個以上のノードを介して相互に分離されているかチェックし、
（ｉｉ）また、新しいクモ構造の２個の足先と別のクモ構造の２個の足先が異なっているか（すなわち異なるノードであるか）チェックする。
【００５８】
図１０は、図９に示すネットワーク（トロイダル連続体７０およびクモ構造９０の両方）をタナーグラフの図示においてより一般的に利用される形状１００に書換えたものである。図１０は、本実施例に対して構成される完全な六角形サブクラスグラフを表す。なお、図８に示す書替図と同様に、この書替図における変数ノードの順序は、対象データｍのビット順序に一致する場合もしない場合もある添字番号に基づく。
【００５９】
実際には、対象データ項目ｍのビット位置を図９に示すネットワークの変数ノードに対応させる処理は所定の方法（例えば、ノード添字により示すノード番号又はその他所定の対応パターンに基づいて）で実行してもよく、又は、疑似ランダムに（グラフ作成ブロック２５、３５のそれぞれで独立して実行可能な決定性を有する方法で）決定してもよい。総和ノードについては、必要なのは、ターゲットシンドローム決定ブロック２４がターゲットシンドロームＳを生成する際に使用する順序を、誤り訂正ブロック３４がターゲットシンドロームを用いる際にも使用するという点だけである。
【００６０】
図１１は、図１０に示すグラフに対応（当然、図９に示すネットワークにも対応）する、対象データｍのビット位置をノード添字に基づいて変数ノードに対応させるためのパリティ検査行列Ｈ２（参照符号１１０）を示す。図１１は、この行列が疎であることを示す。既に説明したように、行列Ｈ２の各行は、モジュロ２加算により対応するターゲットシンドロームのビット値を演算するために選択される対象データビットを表す。
【００６１】
上述のトロイダルウェブクラスのグラフの実施例は「六角形」サブクラスグラフであり、すなわち、トロイダル連続体が六角形セルからなる。図１２〜図１４は、トロイダルウェブクラスグラフの他のサブクラスのトロイダル連続体を構成するために使用される以下のような異なる形状のセルを示す。
【００６２】
図１２は、「十字型」サブクラスグラフのトロイダル連続体の一部１２０を示し、連続体の一部１２０は、各々が、交互に配置され、かつエッジを介して相互接続する６個の総和ノードおよび６個の変数ノードを備える４個の十字型セル１２１〜１２４からなる。完全な連続体において、各セルの境界上においてノードは３個おきに３個の隣接するセルにより共有され、エッジにより４個の他のノードに接続し、そのうち２個のノードが同一のセルに属する。各セルのその他のノードは、対象のセルのノードにのみ接続。
【００６３】
図１３は、図１４に示す実施例と比較する目的で、「六角形」サブクラスグラフのトロイダル連続体の一部１３０を示し、ここでは六角形セルはオフセット配置され６個のノードからなる矩形として書替られている。図示のトロイダル連続体の一部１３０は６個のノードからなる６個の矩形セル１３１〜１３６からなり、６個の矩形セル１３１〜１３６は３列に配置され、中央の列はその他の２列に対して水平方向にオフセット配置される。各セル１３１〜１３６は、交互に配置され、エッジを介して相互接続する３個の総和ノードおよび３個の変数ノードを備える。各セルにおいて、４個のノードはセルの頂点に配置され、（完全な連続体において）、この４個のノードは２個のその他のセルと共有であり、３個のその他のノードに接続し、そのうち２個のノードが同一のセルに属する。セルの残りの２個のノードは、セルの対向する１組の側部のそれぞれに沿って中央に配置され、また、２個のその他のセルと共有であり、かつ３個のその他のノードに接続し、そのうち２個のノードが同一のセルに属する。
【００６４】
図１４は、「非オフセット配置される６個のノードからなる矩形」サブクラスグラフのトロイダル連続体の一部１４０を示し、該連続体の一部１４０は６個のノードからなる８個の矩形セル１４１〜１４８からなり、各矩形セル１４１〜１４８は図１３に示す実施例の６個のノードからなる矩形と同一形状を有するが、非オフセットで配置される列として配置される。この場合、完全な連続体において、各セルにおいてセルの頂点に配置される４個のノードは３個の隣接するセルと共有されており、同一のセルに属する２個のその他のノードに接続し、セルの残りの２個のノードはそれぞれ対象のセルの２個のノードにのみ接続する。
【００６５】
セルの「形状」は主に、論理ネットワークを視覚表現する処理を説明する際の便宜上のもので、大切なのは、セルのノードの相互接続である。
【００６６】
図１５は、図５に示すグラフと同様に、タナーグラフの異なる形状について、対象のタナーグラフに適用される反復的確率伝搬法による処理（誤り訂正ブロック３４が用いる処理）における失敗率がシンドロームサイズに応じて異なる様子を示すグラフであり、チャネル誤り率は全ての場合において同一である。より詳細には、曲線１５１は「ランダム」グラフ（すなわち、構造を備えないものの、長さ４のサイクルが除去されたグラフ）に対応し、曲線１５２は「六角形」サブクラスグラフに対応し、曲線１５３は「非オフセット配置される６個のノードからなる矩形」サブクラスグラフに対応する。図から分かる通り、シンドローム閾値（各曲線が階段状に変化し始める部分）はトロイダルウェブクラスグラフのサブクラス両方ともにおいて、ランダムグラフにより得られる基準閾値より小さく、一般的に、トロイダルウェブクラスのグラフは基準となるランダムグラフと比べてより効率的である（任意のチャネル誤り率に対して必要となるシンドロームサイズがより小さい）ことが分かった。詳細には、「非オフセット配置される６個のノードからなる矩形」サブクラスのグラフが一番高い効率を有することが分かった。
【００６７】
図１６は、ノードおよびエッジからなる標準的なビルディングブロック１６０から、「非オフセット配置される６個のノード矩形」サブクラスグラフのトロイダル連続体を容易に構成する方法を示す。より詳細には、ビルディングブロック１６０は、交互に配置され、エッジを介して相互接続する２個の総和ノードおよび２個の変数ノードからなるライン（ｌｉｎｅ）を備え、終端のノードもエッジを介して相互接続する（図１６において矢印１６５で示す）。この交互に配置される総和ノードおよび変数ノードからなるラインの各ノード（本明細書においては「ラインノード」）はエッジからなる側枝を有し、この側枝は、他のビルディングブロックのラインノードに接続するために解放されているエッジを介して他のノードに接続する。図１６の左側は、上述のように、各ビルディングブロックの解放エッジを隣接するビルディングブロックの対応するラインノードに接続することにより結合した３個のビルディングブロック１６１、１６２、１６３を示す。十分な数のビルディングブロックが上述の方法で相互接続されて、最小のｐ（対象データビットの数）およびｑ（シンドロームビットの数）と同一数の総和ノード又は変数ノードが得られた場合、一番最初のビルディングブロック（図１６におけるブロック１６１）の解放されている終端は一番最後に付加されたビルディングブロック（図１６におけるブロック１６３）のラインノードに円環状に接続され、これによりトロイダル連続体を封止して完成させる。上述のように形成したトロイダル連続体は、端と端が結合された細長い管のような形状を有する（妥当なサイズの対象データ項目ｍを想定する）。
【００６８】
当然、上述のように構成されたトロイダル連続体における各種（総和又は変数）ノードの数は４の整数倍数であるのに対して、ｐおよびｑの最小値は４の整数倍数ではない場合がある。これに対処するためには様々な解決策が可能であり、例えば、シンドロームビットの数ｑは常に４の整数倍数となるよう選択してもよく、ｐおよびｑのうち対象データビットの数ｐの方が小さい場合、適切な数の対象データビットを切捨ててもよく（以下に説明するＱＫＤを用いた実施例等、所定の場合に望ましい）、又は適切な数のダミー対象データビットを付加してもよい。
【００６９】
上述のビルディングブロックを用いたトロイダル連続体の構成方法は、トロイダルウェブクラスのその他のサブクラスグラフに適用してもよく、そのような適用は当業者の裁量の範囲内であるとする。
【００７０】
グラフの生成および使用に関して上述した要点を整理および要約するため、以下に、受信器３２から受信データｒを受信した際の受信側処理装置３３の動作を図１７を参照して説明する。
【００７１】
まず、初期工程１７１において、受信側処理装置３３は規定値ではないグラフパラメータ値を取得するが、本実施例において、対象データｍにおけるビット数ｐは規定値であり、生成するトロイダルウェブグラフのサブクラスおよびグラフ生成に用いられる疑似乱数生成器のパラメータも同様である。本実施例の工程１７１において取得される唯一の動的パラメータは、受信側処理装置３３がチャネル４０の誤り率から導出するシンドロームサイズｑであり、チャネル４０の誤り率は送信側処理装置２３からチャネル４５を介して送信される補助データに含まれる。
【００７２】
その後、受信側処理装置３３はグラフ生成（図１７におけるブロック１７２）を開始する。上述したように、グラフ生成の第１段階はトロイダル連続体の生成であり、これは、工程１７３１における、最小のｐおよびｑに対応する数の総和／変数ノードを得るために必要な標準ビルディングブロック（例えば、図１６に示す、「非オフセット配置される６個のノードからなる矩形」グラフサブクラスに対応するビルディングブロック１６０）の数ｎを決定する第１の決定処理により実行される。ｎの値が決定されると、工程１７３２において、ビルディングブロックの追加がｎサイクルだけ実行され、ｎ個のビルディングブロックが結合されて求めるトロイダル連続体を形成する。
【００７３】
グラフ生成の第２段階は、各過剰なノード（すなわち、トロイダル連続体からは得られていない必要な総和／変数ノード）に対して適切な数のクモ構造の生成するものあり、図１７におけるブロック１７２を参照する。過剰なノードは全て一方の種類であり、工程１７４１において、この過剰なノードの各々を、ランダムに混合わせた他方の種類のノード群（全てトロイダル連続体に属する）の上から選択したｘ（例えば４）個のノードに対応付ける（論理的にはエッジ又は「クモの脚」により接続する）。工程１７４２において、トロイダル連続体に新たに接続された過剰なノードの各々に対して長さ４のサイクルチェックを実行する。
【００７４】
グラフ生成の最終段階は、工程１７５において、データ項目ｍのビット位置をグラフの変数ノードに割当てるものである。
【００７５】
送信側処理装置２３および処理装置受信側３３において略同一のタイミングで実行されるグラフ生成に続いて、受信側処理装置３３は、送信側処理装置２３からチャネル４５を介して受信側処理装置３３に送信される補助データに含まれるターゲットシンドロームＳを受信する（工程１７６参照）。
【００７６】
その後、受信側処理装置３３は、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを用いて受信データｒの誤り訂正を開始（図１７におけるブロック１７７参照）し、ターゲットシンドロームＳに一致する受信データビットの推定値を調節する。本実施例において、ｙサイクル１７８（ｙは例えば４）のＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムが終了する度に、「終盤（ｅｎｄ ｇａｍｅ）」ルーチン１７９を実行してＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムが結論を出したか（元のデータｍの復元成功か、又はＳｕｍ−Ｐｒｏｄｕｃｔサイクルを更に実行しても訂正不可能な失敗か）、又はＳｕｍ−Ｐｒｏｄｕｃｔサイクルを更に実行すべきかを決定し、後者の場合、処理は工程１７８に戻る。
【００７７】
多くの用途においては、変数ノードにおける推定値がターゲットシンドロームＳに一致すれば結果は成功であったと判断されるが、用途によってはより高い確実性が求められ、ターゲットシンドロームの整合性が元のデータｍのビット値に整合しないｖノード推定値に基づくものである可能性が考えられる。終盤ルーチンは、元のデータｍから導出したチェックサムに基づくチェックを含むことにより、そのような可能性を考慮することができ、このチェックを実行するためには、受信側処理装置３３は送信側処理装置２３から正確なチェックサムを（例えば、工程１７６において送信される補助データに含めて）受信する必要があると考えられる。
【００７８】
終盤ルーチンは、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムが有効な一連の処理を完了したか否か決定するとともに、変数ノードにおける推定値がターゲットシンドロームにほぼ一致する場合、誤り総和ノード（すなわち、総和ノードにおいて現在の推定ｖノード値から得た値がその総和ノードに対するターゲットシンドローム値と異なる）のパターンを認識し、そのパターンに基づいて選択ｖノード値を調節することにより整合性を実現してもよい。この、誤り総和ノードのパターンを認識することによる訂正処理について、以下により詳細に説明する。
【００７９】
以下に、「終盤」ルーチン１７９の好ましい形態について図１８を参照して説明し、上記のチェックサムチェックおよび誤り総和ノードのパターンの認識に基づく訂正処理を組込む。
【００８０】
図１８に示す終盤ルーチンはまず、実行中のグラフの変数ノードにおける現在の推定値を決定し、その後、その推定値を用いて現在のシンドローム、すなわちグラフの総和ノード値を抽出するが、これらのノードはターゲットシンドローム値とは対応していない（工程１８１参照）。その後、この現在のシンドロームをターゲットシンドロームＳと比較して異なるビット数のｄを決定する（工程１８２）。
【００８１】
このシンドロームとの差ｄの数が例えば６より大きい（工程１８３において確認する）場合、Ｓｕｍ−Ｐｒｏｄｕｃｔサイクルが更に必要であると判断されるが、既に上限回数（例えば、３００等）のサイクルが実行されていた場合（工程１８４において確認する）、Ｓｕｍ−Ｐｒｏｄｕｃｔサイクルを更に実行してもターゲットシンドロームＳに一致する推定ｖノード値集合への収束は難しいため、誤り訂正を停止し、失敗したと判断する。
【００８２】
工程１８３において、シンドロームとの差がない（ｄ ＝ ０）、すなわち推定ｖノード値がターゲットシンドロームＳに一致すると決定された場合、工程１８５において、推定ｖノード値からチェックサムを作成（ｖノード値を受信データｒに一致する順番に並べるために必要に応じて並び替えを考慮する）し、工程１８６において、元のデータｍから作成したチェックサムと比較する。チェックサムが一致する場合、誤り訂正は成功したとして処理を終了し、推定ｖノード値が復元された対象データｍとして出力される（同様に、必要に応じて並び替えを行う）。しかしながらチェックサムが一致しない場合も、Ｓｕｍ−Ｐｒｏｄｕｃｔサイクルを更に実行しても正しいｖノード値集合への収束は難しいため、誤り訂正は失敗したとして処理を終了する。
【００８３】
工程１８３において、シンドロームとの差ｄの数が１〜６（０＜ｄ≦６）の範囲の数あると決定された場合、上述した誤り総和ノードのパターンの認識に基づいた訂正処理が実行され（工程１８７）、選択されたｖノード値が反転される。値を反転した結果、シンドロームとの差がゼロまで減少した場合（工程１８８において確認する）、チェックサム作成工程１８５および比較工程１８６が実行されるが、値を反転してもシンドロームとの差がゼロまで減少しない場合、現在実行中の終盤ルーチンの直前に存在したｖノード推定値からＳｕｍ−Ｐｒｏｄｕｃｔサイクルを更に実行する（工程１８４の上限チェックを行う）。
【００８４】
誤り総和ノードのパターン認識に基づく訂正処理（工程１８７）に関して、図１９〜図２５はそれぞれ、トロイダルウェブグラフの「非オフセット配置される６個のノードからなる矩形」サブクラスに対応する誤り総和ノードのパターンを示し、各パターンにおいて、太線の円により囲まれた総和ノードが誤り総和ノードである。これらのパターンは工程１８７において系統的に検索され、パターンが検出されると、所定の変数ノードに対応にするビット値が不正値の候補として特定されて反転され、この変数ノードは、認識されたパターンにおいて値が変更された場合、対象のパターンにおける総和ノードの不正値を解消する。そのような変数ノードは、図１９〜図２５において点線の円で囲んで示す。その後、上述の検索処理が、グラフ全体が検索されるまで、又は訂正された総和ノード値の数がシンドロームとの元の差と同数になるまで継続して実行される。
【００８５】
図１９〜図２５において、誤り総和ノードがいくつ発生しているかに基づいてパターンを配置する。便宜上、各パターンに非制限的な記述による以下のようなラベルを付ける。
【００８６】
図１９および図２０はそれぞれ、誤り総和ノードが２個のみ発生しているパターンを示し、以下のラベルで表す：
「２ｓ−線上隣接型」；および
「２ｓ−線上三個組型」。
【００８７】
図２１〜図２３はそれぞれ、誤り総和ノードが４個発生しているパターンを示し、以下のラベルで表す：
「４ｓ−菱形」；
「４ｓ−燭台型」；および
「４ｓ−回転Ｌ字型」。
【００８８】
図２４〜図２５はそれぞれ、誤り総和ノードが６個発生しているパターンを示し、以下のラベルで表す：
「６ｓ−六角形」；および
「６ｓ−漏斗型」。
【００８９】
上述のラベルは誤り総和ノードパターンの特定の視覚的外見に言及しているものの、当然のことながら、視覚的外見は基本となるノードおよびエッジからなる論理ネットワークを視覚的に表現する特定の方法に依存し、様々な他の表現方法も可能なため、全く重要ではない。誤り総和ノードの各パターンは基本的に、任意の表現方法が与える視覚的パターンによってではなく、対象の総和ノードの相互関係のパターンにより定義される。
【００９０】
例として、図１９に示す単純な「２ｓ−線上隣接型」パターンは、他に接続先を有さない１個の変数ノードを介して接続される２個の誤り総和ノードからなる。したがって、「２ｓ−線上隣接型」パターンにおいて、誤り総和ノード間に配置される変数ノードに対応付するビット値が、この値を反転することによりその他の総和ノードではなく誤り総和ノードの値が反転するため不正値の候補となる。同様に、図２０に示す「２ｓ−線上三個組型」パターンにおいて、２個の誤り総和ノードはエッジおよびノードからなるラインを介して接続され、ライン上のノードは１個の非誤り総和ノードを間に挟んで配置される２個の変数ノードを備え、この変数ノードは間に挟まれる総和ノードおよび誤り総和ノードの一方にそれぞれ接続され、両方の変数ノードに対応するビット値が、この値を反転することによりその他の総和ノードではなく誤り総和ノードの値が反転するため不正値の候補となる。
【００９１】
図２２に示す「４ｓ−燭台型」パターンは、対象のグラフのトロイダル連続体が上から下まで円環上に接続されるため、実際には図２１に示す「４ｓ−菱形」パターンと同一の基本的パターンと考えられるかもしれないが、検索処理が（図示のように）「最下」列のノードを参照して実行された場合、パターンが異なる。各パターンにおいて、４個の誤り総和ノードは１個の中間変数ノードを介して相互接続され、中間変数ノードに対応するビット値が、この値を反転することによりその他の総和ノードではなく誤り総和ノードの値が反転するため不正値の候補となる。
【００９２】
図２４および図２５に示す「６ｓ−六角形」パターンおよび「６ｓ−漏斗型」パターンについても同様である。この場合、各パターンは以下を備える。
【００９３】
２個の変数ノードおよび間に配置される中間の非誤り総和ノードからなる３個組のノードにより接続される第１の誤り総和ノード対。各変数ノードは中間の総和ノードおよび第１の対の各誤り総和ノードにそれぞれ接続される。
【００９４】
その他の接続を有さない１個の中間変数ノードを介して接続される第２の誤り総和ノード対。第２の対の各誤り総和ノードは、第１の誤り総和ノード対を接続する上記の３個組ノードのうち変数ノードのそれぞれに接続される。
【００９５】
その他の接続を有さない１個の中間変数ノードを介して接続される第３の誤り総和ノード対。第３の対の各誤り総和ノードは、第１の誤り総和ノード対を接続する上記の３個組ノードのうち変数ノードのそれぞれに接続される。
【００９６】
第１の誤り総和ノード対を接続する３個組ノードのうち２個の変数ノードに対応するビット値が、この値を反転することによりその他の総和ノードではなく誤り総和ノードの値が反転するため不正値の候補となる。
【００９７】
より複雑なパターン（すなわち、より多くの誤り総和ノードを含むパターン）が優先的に検索されるが、これは、図１９に示す「２ｓ−線上隣接型」パターンのような単純なパターンは、実際には単に図２１〜図２３に示す４個の誤り総和ノードを含むパターンのようなより複雑なパターンの一部である場合があるためである。
【００９８】
図１９〜図２５に図示した誤り総和ノードのパターンは、全てのパターンを網羅することを意図するものではなく、工程１８７は任意の可能なパターンを検索するよう構成してもよい。更に、上述した誤り総和ノードのパターンは全て対象のグラフのトロイダル連続体に見られるパターンであるが、グラフの「クモ構造」を含むパターンを検索することも可能である。より詳細には、ｐ＞ｑであり、これにより各クモ構造の中心となるノードが変数ノードｖである場合、クモ構造の全ての脚における「足先」に対応する誤り総和ノードのパターンは、クモ構造の中心となる対象データビットが誤りである可能性が高く、反転すべきであることを示す。好ましくは、上述のような誤り総和ノードパターンを（例えば、各クモ構造を順次チェックすることにより）まず検索する。
【００９９】
既に述べたように、図１９〜図２５に図示したパターンはトロイダルウェブグラフの「非オフセット配置される６個のノードからなる矩形」サブクラスに適用可能であり、当業者は、トロイダルウェブグラフのその他のサブクラスに対応する類似の誤り総和ノードパターンを容易に導出できる。
【０１００】
当業者にとっては、誤り総和ノードのパターン（および各パターンに対応する誤り変数ノード又はノード群の候補）を表すデータは、装置が処理しようとする各種のグラフに対応して、受信装置により記憶され、記憶されたデータはプレインストールされていてもよく、又は必要に応じて読込んでもよいことは明らかである。また、誤り変数ノードの候補を特定する処理は、事前に受信データビット位置を変数ノードに対応付けするため、受信データの誤りビット候補を特定する処理（Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを適用して調節する）と同様に効率的である。
【０１０１】
応用例
ワンタイムパッド補充に用いられるＱＫＤ装置における誤り訂正
以下に、図２６および図２７を参照して、整合ワンタイムパッド（ＯＴＰ）の補充に用いられる量子鍵配送（ＱＫＤ）装置の誤り訂正に関する上述の誤り訂正方法および装置の応用例を説明する。
【０１０２】
公知のように、同一の秘匿なランダムデータを有する２つの当事者が、バーナム暗号を用いて解読不能で機密な通信を行ったり、また真正なメッセージと誤った、又は改ざんされたメッセージとを（例えばＷｅｇｍａｎ−Ｃａｒｔｅｒ認証を用いて）識別したりできることが分かっている。しかしながら、どちらの場合も、当事者が共有する秘匿なランダムデータから使用したデータは再使用すべきではない。したがって、「ワンタイムパッド」という用語は当事者が共有する秘匿なランダムデータをさすことが多く、本明細書においては、この用語又はその頭字語「ＯＴＰ（ｏｎｅ−ｔｉｍｅ ｐａｄ）」は複数の当事者が共有する秘匿なランダムデータをさすが、以下に記載の特定の例においては、この当事者を、ＱＫＤ送信装置に相当する当事者アリスおよびＱＫＤ受信装置に相当する当事者ボブとする。絶対的な安全性のためにはワンタイムパッドデータは真にランダムである必要があるが、本明細書においてワンタイムパッド（ＯＴＰ）に言及する場合、真にランダムではないかもしれないが、対象の目的に対して許容できるレベルの安全性を提供するには十分ランダムな秘匿データを含む。
【０１０３】
ＯＴＰデータは使用されると実質的に消費されてしまうため、ワンタイムパッドの様々な用途において、対象の複数の当事者が保持するＯＴＰデータを、ＯＴＰデータの使用により得られる安全性を損なわないよう非常に機密な方法で補充する必要が生じる。
【０１０４】
近年、量子鍵配送（ＱＫＤ）方法および装置が開発されており、２つの当事者が、非常に高い確率で盗聴者を検出可能な方法でランダムデータを共有することができる。すなわち、盗聴者が検出されない場合、当事者は共有のランダムデータが秘匿であると高い確率で確信することができ、したがってＱＫＤ方法および装置はＯＴＰデータを機密に補充するのに非常に適している。
【０１０５】
公知のＱＫＤ装置において、ランダムに偏光された光子は送信装置から受信装置に光ファイバケーブル又は自由空間を介して送信され、これらＱＫＤ装置は通常公知のＢＢ８４量子符号化プロトコル（Ｃ．Ｈ．ＢｅｎｎｅｔｔおよびＧ．Ｂｒａｓｓａｒｄによる「Ｑｕａｎｔｕｍ Ｃｒｙｐｔｏｇｒａｐｈｙ：Ｐｕｂｌｉｃ Ｋｅｙ Ｄｉｓｔｒｉｂｕｔｉｏｎ ａｎｄ Ｃｏｉｎ Ｔｏｓｓｉｎｇ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒｓ Ｓｙｓｔｅｍｓ ａｎｄ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ、インド国バンガロール市、１９８４年１２月、１７５〜１７９ページ参照）に基づいて動作する。ＢＢ８４プロトコル又はＱＫＤ送信器若しくは受信器の詳細は本発明の理解に必要ないため、本明細書においては詳細の大部分は省略してあるが、詳細が必要な場合、上記の文献又は類似の一般的に入手可能な文献を参照することにより容易に取得可能である。
【０１０６】
図２６はＱＫＤ装置の応用例を示し、ＱＫＤ装置は図４に示す装置を更に特化したものであり、対応する素子は同一の参照符号にアルファベット「Ｑ」を補足して示す。したがって、図２６に示すＱＫＤ装置は、量子信号チャネル４０Ｑ（雑音チャネル）および従来のチャネル４５Ｑ（誤りがない、又は誤り訂正される無線チャネル等の非量子信号チャネル）を介して通信を行うＱＫＤ送信装置２０Ｑ（当事者「アリス」に相当）およびＱＫＤ受信装置３０Ｑ（当事者「ボブ」に相当）を備える。ＱＫＤ送信装置２０Ｑは送信側処理装置２３Ｑを含み、ＱＫＤ受信装置３０Ｑは受信側処理装置３３Ｑを含む。処理装置２３Ｑおよび３３Ｑの各々は、対応する図４の処理装置２３および３３と同一の機能ブロック（図２６では図示せず）を備え、更に以下に説明する別の機能ブロックを備える。
【０１０７】
ＱＫＤ送信装置２０Ｑは、ＱＫＤ受信装置３０ＱのＱＫＤサブ受信装置５０２と量子信号チャネル４０Ｑおよび従来のチャネル４５Ｑを介して連動するＱＫＤサブ送信装置５０１（図２６において点線で示す）を有し、これによりランダムデータ集合ｍが送信装置２０Ｑから受信装置３０Ｑに送信され、ＱＫＤサブ受信装置５０２はランダムデータ集合ｍを誤り訂正すべき受信データｒとして出力する。
【０１０８】
ＱＫＤサブ送信装置５０１は、ＱＫＤ送信器２１Ｑ（光子を選択的に偏光する光学部材を提供する）、ランダムデータ源５０５、および送信側処理装置２３Ｑの機能ブロックとして設けられるＱＫＤ処理ブロック５０６を備える。ランダムデータ源５０５はランダムビット対を生成するが、その際、片面を銀めっきした反射鏡により光子を検出器に伝送／偏向して５０：５０の確率で「０」／「１」を生成する量子ベースの装置等のハードウェア乱数生成器によりランダム性を実現するが、その他の乱数生成器として、抵抗器又はダイオードをオーバドライブさせ、電子雑音を利用してランダム事象を誘起するような構成とすることも可能である。各ランダムビット対のうち一方が現在のタイムスロット内で送信器２１Ｑにより送信されるビット値を決定し、他方のビットがビット値の送信に用いる偏光基底を決定する。
【０１０９】
なお、ＱＫＤ送信器２１ＱおよびＱＫＤ受信器３１Ｑが共有するデータ集合ｍは、送信器２１Ｑにより送信されるビット値の非決定性サブセットであり、このサブセットは、以下のようなビット値を備える。
【０１１０】
ＱＫＤサブ受信装置５０２が対応するタイムスロット内で量子信号チャネル４０Ｑを介して信号を受信したもの。
【０１１１】
ＱＫＤサブ送信装置５０１およびＱＫＤサブ受信装置５０２が同一の偏光基底をランダムに用いる（例えばチャネル４０Ｑの誤り率を決定する際に従来のチャネルを介して送信されるビット値より低い）。ＱＫＤ処理ブロック５０６の役割は、送信器２１Ｑにより送信されるビット値、および従来のチャネル４５Ｑを介して受信するＱＫＤサブ受信装置５０２における信号受信およびＱＫＤサブ受信装置５０２が用いる基底に関する情報に基づいて、データ集合ｍの内容を決定することである。
【０１１２】
ＱＫＤサブ受信装置５０２は、ＱＫＤ受信器３２Ｑ（光子を受信し、その偏光を検出する光学部材を提供する）および受信側処理装置３３Ｑの機能ブロックとして設けられるＱＫＤ処理ブロック５０９を備える。ＱＫＤサブ受信装置５０２において、連続するタイムスロットにおいて使用される偏光基底は、片面を銀めっきした反射鏡を用いて入射する光子を検出器にランダムに誘導し、少なくとも１個の偏光基底を形成することによりランダムに選択される。ＱＫＤ処理ブロック５０９の役割は、受信されるビット値および従来のチャネル４５Ｑを介して受信される正しい基底が用いられたタイムスロットを特定する情報に基づいて受信データｒを決定することである。
【０１１３】
その後、図４〜図２５を参照して上述した方法により受信データｒの訂正が実行され、これによりＱＫＤ受信装置３０Ｑがランダムデータ集合ｍを復元できる。
【０１１４】
ＱＫＤ送信装置２０Ｑは、メモリ内に記憶され、送信側処理装置２３ＱのＯＴＰ制御機能ブロック５０７により制御されるワンタイムパッド５０３を保持し、同様に、ＱＫＤ受信装置３０Ｑは、メモリ内に記憶され、受信側処理装置３３ＱのＯＴＰ制御機能ブロック５１０により制御されるワンタイムパッド５０４を保持する。ＱＫＤ送信装置２０ＱおよびＱＫＤ受信装置３０Ｑが共有するランダムデータ集合ｍは、ワンタイムパッド５０３および５０４の内容が相互に整合し続けるようワンタイムパッド５０３および５０４を補充するために用いられる。
【０１１５】
ワンタイムパッド５０３および５０４から取得したデータはＱＫＤ送信装置２０ＱおよびＱＫＤ受信装置３０Ｑを相互に認証し、また、受信データｒに適用する誤り訂正処理に用いる疑似乱数生成器をランク付けするために用いる。実際には、非効率的ではあるが、ワンタイムパッドからのデータは誤り訂正処理において求められるランダム性を実現する手段として直接利用してもよい。
【０１１６】
以下に、ワンタイムパッド５０３、５０４を補充するためのＱＫＤ送信装置２０ＱおよびＱＫＤ受信装置３０Ｑの相互作用および動作の全体的流れを、図２７Ａおよび図２７Ｂを参照して説明する。便宜上、以下においてはアリスおよびボブが工程を実行するとして説明するが、対象の工程は実際にはＱＫＤ送信装置２０ＱおよびＱＫＤ受信装置３０Ｑによりそれぞれ実行されるものとし、更に、図２７Ａおよび図２７Ｂにおいて、特定の工程に関してブロック体の大文字で示すアリスおよび／又はボブ名前は、場合に応じて、その工程において対応する装置２０Ｑおよび／又は３０Ｑが能動的に関与することを示す。
【０１１７】
初期の認証段階（図２７Ａにおける工程５１４〜工程５２２）において、アリスは従来の通信チャネル４５Ｑを用いてボブと通話を開始し、アリスはボブに自己が誰であるか伝え、ボブはアリスに自己が誰であるか返答する。
【０１１８】
本例によれば、この認証はワンタイムパッド５０３、５０４からのデータを用いて行われる。説明の便宜上、ワンタイムパッドは「ａ‖ｂ‖ｃ‖ＯＴＰの残存部」からなると考えられ、この場合ａ、ｂ、およびｃはそれぞれ例えば６４ビットである（記号‖は文字列連結を表す）。工程５１４において、アリスは（ａ）ＸＯＲ（ｂ）をボブに送信し、この場合、ＸＯＲは排他的論理和機能である。工程５１６において、ボブは整合するものを求めて自己のワンタイムパッド５０４を検索する。整合するものが見つかると、ボブは工程５１８においてアリスに（ａ）ＸＯＲ（ｃ）を送信し返す。工程５２０において、アリスはそれが正しい応答かチェックする。その後、アリスおよびボブの両方は、工程５２２において自己のワンタイムパッド５０３、５０４から「ＯＴＰの残存部」を残してａ、ｂ、およびｃを消去する。
【０１１９】
次に、ＱＫＤ送信および処理段階が実行される（工程５２４〜工程５４１）が、本例においては、以下に説明するように、ＢＢ８４量子符号化プロトコルを変更したものを用いる。
【０１２０】
アリスおよびボブは、データユニットを出力するタイムスロット長について所定の了解を得ているものとする。初期同期を実行するため、アリスは工程５２４において量子信号チャネルを介して光子パルスを送信する。
【０１２１】
工程５２６において、アリスは多数の、通常は約１０８対程のビット対を（データ源５０５を用いて）ランダムに生成する。上述したように、各ビット対はデータビットおよび基底ビットからなり、基底ビットはデータビットを送信するための、垂直方向／水平方向又は対角方向／反対角方向からなる偏光方向の対を示す。水平方向又は対角方向に偏光された光子は二進数の１を示し、垂直方向又は反対角方向に偏光された光子は二進数の０を示す。したがって、各対のデータビットは同一対の基底ビットが示す偏光方向の対に基づいて符号化され、アリスにより量子信号チャネル４０Ｑを介して送信される。アリスから量子信号を受信すると、ボブは各タイムスロットにおいて、どの基底（偏光方向の対）を用いて量子信号を検出するかランダムに選択し、結果を記録する。量子チャネルを用いて行う必要のある通信は、ランダムに生成されたビット対のデータビットの送信のみである。
【０１２２】
工程５２８において、ボブは、実際には送信全体の１０％等ランダムに選択できる量子信号送信の一部における全受信データを従来のチャネル４５Ｑを介してアリスに送信し、これにより、アリスは量子信号チャネル４０Ｑの誤り率を決定できる。受信データは信号が受信されたタイムスロット、そのタイムスロットの各々において受信された際に決定されたデータビット値、およびその際の基底（すなわち偏光方向の対）を含む。工程５３０において、アリスはボブから受信したランダムに選択された送信の１０％に関する受信データを用いて、ボブが信号を受信し、かつ正しい基底を用いたタイムスロットについてチャネル４０Ｑの誤り率を決定する。
【０１２３】
工程５３２において、アリスは工程５３０において導出した誤り率に基づいて、量子信号が盗聴されたか否か決定する。誤り率が高ければ高い程、量子信号が盗聴された確率が高く、一般的に約１２％より高い誤り率は許容の範囲外であり、好ましくは８％の上限を設定する。誤り率が閾値である８％より高い場合、そのセッションは放棄され（工程５３４）、アリスは従来のチャネル４５Ｑを介してボブに受信した量子信号データを破棄するよう伝える。
【０１２４】
誤り率が閾値である８％より低い場合、アリスは従来のチャネル４５Ｑを介してボブに誤り率を送信し、その後、アリスおよびボブの両者はこの誤り率を上述した方法で用いて誤り訂正に用いるシンドロームサイズを決定する。アリスおよびボブの両者は誤り率の決定に用いたデータ値を破棄する。
【０１２５】
工程５３８において、ボブは、量子信号送信の残りの部分（例えば残りの９０％）における部分的受信データを従来のチャネル４５Ｑを介してアリスに送信し、この部分的受信データは信号を受信したタイムスロットおよびその際の基底（すなわち偏光方向の対）を含むが、受信された際に決定されたデータビット値は含まない。
【０１２６】
工程５４０において、アリスは、ボブが量子信号を受信し、かつ正しい基底を用いて受信したビット値を決定したタイムスロットに対して送信されたデータビット値ｍを決定する。アリスはまた、データビット値ｍを保持するタイムスロットを特定する情報を、従来のチャネル４５Ｑを介してボブに送信する。工程５４１において、ボブは受信データｒを形成するデータビット値を決定する。
【０１２７】
動作の次の段階（図２７Ｂにおける工程５４２〜工程５５０）は、図４〜図２５を参照して上述した方法による受信データｒの誤り訂正である。したがって、工程５４２において、アリスおよびボブは使用するターゲットシンドロームのサイズを決定し、その後、トロイダルウェブクラスの任意の又は同意したサブクラスからなる同一のグラフを独立して生成する。
【０１２８】
工程５４４において、アリスは、工程５４２において生成したグラフを用いてデータｍからターゲットシンドロームＳを決定し、また、ｍに対してチェックサムを計算する。アリスは、ターゲットシンドロームＳおよびチェックサムを従来のチャネル４５Ｑを介してボブに送信する。
【０１２９】
工程５４６において、ボブはＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを用いて受信データｒに対する誤り訂正を実行する。誤り訂正が失敗した場合（ここで、終盤ルーチン１７９の関連する検査は工程１５４で実行されると図示してあり、ターゲットシンドロームＳおよびｍから形成されるチェックサムの整合性をチェックする検査を含む）、ボブは工程５５０においてアリスにデータｍを破棄するよう伝え、ボブは受信データｒを破棄する。
【０１３０】
誤り訂正が成功して、アリスおよびボブの両者が量子信号チャネル４０Ｑを介して共有される新しいランダムデータｍを得た場合、アリスおよびボブの両者は同一のプライバシー増幅工程５５２を実行する。なお、この点において、工程５３２において実行される誤り率に基づく盗聴チェックにより量子信号送信のどの部分における盗聴も検出できるが、あるタイムスロットにおいて２個以上の光子が量子チャネルを介して送信されるという（非常に小さいものの）有限の確率が存在し、これにより、ボブが光子の一方を受信する一方で、ビームスプリッタを備える盗聴者が他方の光子を受信できるという可能性が残るため、盗聴者が量子信号のうち多少のビットの盗聴に成功する可能性がある。プライバシー増幅工程５５２を実行するのは、そのような盗聴者への情報漏洩の可能性を解消するためである。
【０１３１】
プライバシー増幅工程５５２において、アリスおよびボブはそれぞれ新しく共有した秘匿なデータｍのサイズを、必要な安全性のレベルに応じて、決定性を有するランダム置換を用いて縮小する。
【０１３２】
プライバシー増幅の結果、アリスおよびボブは非常に高い確率で同一の結果ｍ’を得る。しかしながら工程５５４において、アリスおよびボブは本当にそうであるかどうか、新しく共有した秘匿データｍ’のハッシュ値を交換することによりそれぞれ再確認するが、その際、送信されるハッシュ値を保護および認証するため、自己のワンタイムパッド５０３、５０４から選択したビットによりハッシュ値の排他的論理和をとる。ハッシュ値が異なる（工程５５６において確認する）場合、新しく共有したデータｍ’は破棄する（工程５５８）。
【０１３３】
交換したハッシュ値が整合する場合、アリスおよびボブは同一の新しい共有データｍ’を有すると再確認したことになり、それぞれ、新しいデータｍ’を自己のワンタイムパッド５０３、５０４の既存の内容に統合開始する。この統合処理においては、ハッシュ値機能を用いて、外部観測者がワンタイムパッド内の最終的に共有される秘匿なデータについて何ら知らないこと保証する。実際には、統合の前にワンタイムパッドに十分なデータ量が残っている場合、統合動作により十分に不明瞭化でき、ほとんどの場合、プライバシー増幅工程５５２および続く工程５５４は省略してもよい。
【０１３４】
その後、補充後のワンタイムパッドからのデータを用いて、例えば、送信装置２ＯＱおよび受信装置３ＯＱ間で従来のチャネルを介して行われるアプリケーションデータの交換を暗号化するためのセッション鍵（例えば、１２８ビットのセッション鍵）を生成してもよく、セッション鍵の作成に使用されたデータはワンタイムパッドから破棄される。
【０１３５】
上述のＱＫＤ方法は本発明の一例であり、図２７に示した本例の工程は（当業者には明らかな境界の範囲内で）変更および／又は異なる順序で実行してもよいこととする。
【０１３６】
図４〜図２５を参照して上述した誤り訂正方法に関しては、当然ながら様々な変更が可能である。例えば、処理を最小限に抑える目的で、ターゲットシンドロームのサイズはチャネル４０の誤り率に基づいて動的に決定されると記載したが、あるいは、全ての可能な誤り率を処理できる所定のシンドロームサイズを選択して動作を行ってもよく、この場合、その他のグラフパラメータも全て同様に規定値である場合、グラフ作成はグラフパラメータデータを交換することなく実行可能である。
【０１３７】
上述の記載において、誤り訂正グラフは、送信装置２０および受信装置３０により各対象データ項目ｍ（又は対象データ項目集合）に対して動的かつ独立して作成されるが、トロイダルウェブクラスのグラフは以下のような装置に用いてもよい。
【０１３８】
用いられる誤り訂正グラフが固定であって、送信装置および受信装置内にプレインストールされている装置。
【０１３９】
送信装置および受信装置のうち一方のみがグラフを生成し、形成されたグラフは他方の装置に送信される装置。
【０１４０】
および、ターゲットシンドロームが、例えばトロイダルウェブクラスの誤り訂正グラフが標準的な線形ブロック符号に基づく誤り訂正装置で使われた場合のようにゼロベクトル等の規定値である装置。
【特許請求の範囲】
【請求項１】
２進データ集合（ｍ、ｒ）から選択される各データビットをモジュロ２加算した複数の順序演算結果を抽出する処理装置（２３、３３）を備え、
前記選択は、有限トロイドを覆うセルの連続体（７０、１２０、１３０、１４０）を少なくとも定義するノードおよびエッジからなる論理ネットワークにおける変数ノード（ｖ１〜ｖ１５）の総和ノード（ｓ１〜ｓ１２）への接続に基づいており、
前記セルの各々は交互に配置され、エッジによりループ状に相互接続する同一数の変数ノード（ｖ１〜ｖ１２）および総和ノード（ｓ１〜ｓ１２）により区切られており、
前記変数ノードの各々は２進データ集合のビット位置にそれぞれ対応し、
前記総和ノードの各々は前記モジュロ２加算した演算結果にそれぞれ対応する、
ことを特徴とするデータ通信装置（２０、３０）。
【請求項２】
前記連続体（７０、１２０、１３０、１４０）の前記変数ノードは前記２進データ集合のビット位置にランダムに対応付する、
ことを特徴とする請求項１に記載のデータ通信装置。
【請求項３】
前記セルの各々は、各々が、２個の隣接するセルに共有され、エッジにより３個のその他のノードに接続される６個のノードを有し、
前記３個のその他のノードのうち２個は同一のセルに属し、
前記連続体（７０）は六角形セル（７７）からなると表現できる、
ことを特徴とする請求項１に記載のデータ通信装置。
【請求項４】
前記セルの各々は、３個おきに３個の隣接するセルにより共有され、エッジにより４個のその他のノード接続される１２個のノードを有し、前記４個のその他のノードのうち２個は同一のセルに属し、前記３個おきのノード間のセルノードは対象のセルのノードにのみ接続され、前記連続体（１２０）は十字型セル（１２１−１２４）からなると表現できる、ことを特徴とする請求項１に記載のデータ通信装置。
【請求項５】
前記セルの各々は６個のノードを有し、
前記６個のノードのうち４個のノードの各々は３個の隣接するセルに共有され、かつエッジにより４個のその他のノード接続にされ、
前記４個のその他のノードのうち２個は同一のセルに属し、
前記セルの各々のその他の２個のノードは対象のセルのノードにのみ接続され、
前記連続体（１４０）は矩形セル（１４１−１４８）からなると表現できる、ことを特徴とする請求項１に記載のデータ通信装置。
【請求項６】
前記論理ネットワークの前記ノードおよびエッジは更に、
各々が変数ノード（ｖ）と総和ノード（ｓ）の一方の種類のノードを備え、
エッジにより総和ノード（ｓ）と変数ノード（ｖ）の他方の種類からランダムに選択されるノードに接続される複数のクモ構造（９０）を定義し、
前記他方の種類はまた前記セルの連続体（７０、１２０、１３０、１４０）を規定する際にも用いられる、
ことを特徴とする請求項１に記載のデータ通信装置。
【請求項７】
前記一方の種類のノードの各々は、エッジにより前記他方の種類からランダムに選択される４個のノードに接続される、
ことを特徴とする請求項６に記載のデータ通信装置。
【請求項８】
前記データ通信装置（３０）は雑音チャネル（４０）を介して２進データ集合（ｒ）を受信し、
前記処理装置（３３）は前記受信した２進データ集合（ｒ）の誤りを訂正する誤り訂正装置（３４）を備え、
前記誤り訂正装置（３４）は反復的確率伝搬法を適用して前記受信した２進データ集合（ｒ）のビット値尤度を調節し、これにより、前記受信データ集合の推定値集合である前記２進データ集合のために前記処理装置（２３）が形成する前記モジュロ２加算した複数の順序演算結果はターゲットシンドローム（Ｓ）に整合する、
ことを特徴とする請求項１に記載のデータ通信装置。
【請求項９】
前記データ通信装置（３０）は第１の雑音チャネル（４０）を介して前記２進データ集合（ｍ）を送信し、前記データ通信装置（３０）は更に、前記第１の雑音チャネルを介して前記２進データ集合を受信した後に前記２進データ集合の誤り訂正を実行するためのターゲットシンドローム（Ｓ）を出力し、前記処理装置（２３）は、前記ターゲットシンドローム（Ｓ）を前記モジュロ２加算した複数の順序演算結果として抽出する、ことを特徴とする請求項１に記載のデータ通信装置。
【請求項１０】
反復的確率伝搬法を適用して受信される２進データ列（ｒ）のビット値尤度を調節し、これにより受信されるデータ列から選択される各ビットの推定値をモジュロ２加算した複数の順序演算結果がターゲットシンドローム（Ｓ）と整合する誤り訂正装置（３４）であって、
前記選択は、有限トロイドを覆うセルの連続体（７０、１２０、１３０、１４０）を少なくとも定義するノードおよびエッジからなるネットワークにおける変数ノード（ｖ１〜ｖ１５）の総和ノード（ｓ１〜ｓ１２）への接続に基づいており、
前記セルの各々は、交互に配置され、エッジによりループ状に相互接続する同一数の変数ノード（ｖ１〜ｖ１２）および総和ノード（ｓ１〜ｓ１２）により区切られており、
前記変数ノードの各々は受信されるデータ列のビット位置にそれぞれ対応し、
前記総和ノードの各々は前記モジュロ２加算した演算結果にそれぞれ対応する、
ことを特徴とする誤り訂正装置。
【請求項１１】
前記ノードおよびエッジからなるネットワークは更に、
各々が変数ノード（ｖ）又は総和ノード（ｓ）の一方の種類のノードを備え、
エッジにより総和ノード（ｓ）又は変数ノード（ｖ）の他方の種類からランダムに選択されるノードに接続される複数のクモ構造（９０）を定義し、
前記他方の種類はまた前記セルの連続体（７０、１２０、１３０、１４０）を規定する際にも用いられる、
ことを特徴とする請求項１０に記載の誤り訂正装置。
【請求項１２】
前記変数ノードは受信されるデータ列のビット位置にランダムに対応する、ことを特徴とする請求項１０に記載の誤り訂正装置。
【請求項１】
２進データ集合（ｍ、ｒ）から選択される各データビットをモジュロ２加算した複数の順序演算結果を抽出する処理装置（２３、３３）を備え、
前記選択は、有限トロイドを覆うセルの連続体（７０、１２０、１３０、１４０）を少なくとも定義するノードおよびエッジからなる論理ネットワークにおける変数ノード（ｖ１〜ｖ１５）の総和ノード（ｓ１〜ｓ１２）への接続に基づいており、
前記セルの各々は交互に配置され、エッジによりループ状に相互接続する同一数の変数ノード（ｖ１〜ｖ１２）および総和ノード（ｓ１〜ｓ１２）により区切られており、
前記変数ノードの各々は２進データ集合のビット位置にそれぞれ対応し、
前記総和ノードの各々は前記モジュロ２加算した演算結果にそれぞれ対応する、
ことを特徴とするデータ通信装置（２０、３０）。
【請求項２】
前記連続体（７０、１２０、１３０、１４０）の前記変数ノードは前記２進データ集合のビット位置にランダムに対応付する、
ことを特徴とする請求項１に記載のデータ通信装置。
【請求項３】
前記セルの各々は、各々が、２個の隣接するセルに共有され、エッジにより３個のその他のノードに接続される６個のノードを有し、
前記３個のその他のノードのうち２個は同一のセルに属し、
前記連続体（７０）は六角形セル（７７）からなると表現できる、
ことを特徴とする請求項１に記載のデータ通信装置。
【請求項４】
前記セルの各々は、３個おきに３個の隣接するセルにより共有され、エッジにより４個のその他のノード接続される１２個のノードを有し、前記４個のその他のノードのうち２個は同一のセルに属し、前記３個おきのノード間のセルノードは対象のセルのノードにのみ接続され、前記連続体（１２０）は十字型セル（１２１−１２４）からなると表現できる、ことを特徴とする請求項１に記載のデータ通信装置。
【請求項５】
前記セルの各々は６個のノードを有し、
前記６個のノードのうち４個のノードの各々は３個の隣接するセルに共有され、かつエッジにより４個のその他のノード接続にされ、
前記４個のその他のノードのうち２個は同一のセルに属し、
前記セルの各々のその他の２個のノードは対象のセルのノードにのみ接続され、
前記連続体（１４０）は矩形セル（１４１−１４８）からなると表現できる、ことを特徴とする請求項１に記載のデータ通信装置。
【請求項６】
前記論理ネットワークの前記ノードおよびエッジは更に、
各々が変数ノード（ｖ）と総和ノード（ｓ）の一方の種類のノードを備え、
エッジにより総和ノード（ｓ）と変数ノード（ｖ）の他方の種類からランダムに選択されるノードに接続される複数のクモ構造（９０）を定義し、
前記他方の種類はまた前記セルの連続体（７０、１２０、１３０、１４０）を規定する際にも用いられる、
ことを特徴とする請求項１に記載のデータ通信装置。
【請求項７】
前記一方の種類のノードの各々は、エッジにより前記他方の種類からランダムに選択される４個のノードに接続される、
ことを特徴とする請求項６に記載のデータ通信装置。
【請求項８】
前記データ通信装置（３０）は雑音チャネル（４０）を介して２進データ集合（ｒ）を受信し、
前記処理装置（３３）は前記受信した２進データ集合（ｒ）の誤りを訂正する誤り訂正装置（３４）を備え、
前記誤り訂正装置（３４）は反復的確率伝搬法を適用して前記受信した２進データ集合（ｒ）のビット値尤度を調節し、これにより、前記受信データ集合の推定値集合である前記２進データ集合のために前記処理装置（２３）が形成する前記モジュロ２加算した複数の順序演算結果はターゲットシンドローム（Ｓ）に整合する、
ことを特徴とする請求項１に記載のデータ通信装置。
【請求項９】
前記データ通信装置（３０）は第１の雑音チャネル（４０）を介して前記２進データ集合（ｍ）を送信し、前記データ通信装置（３０）は更に、前記第１の雑音チャネルを介して前記２進データ集合を受信した後に前記２進データ集合の誤り訂正を実行するためのターゲットシンドローム（Ｓ）を出力し、前記処理装置（２３）は、前記ターゲットシンドローム（Ｓ）を前記モジュロ２加算した複数の順序演算結果として抽出する、ことを特徴とする請求項１に記載のデータ通信装置。
【請求項１０】
反復的確率伝搬法を適用して受信される２進データ列（ｒ）のビット値尤度を調節し、これにより受信されるデータ列から選択される各ビットの推定値をモジュロ２加算した複数の順序演算結果がターゲットシンドローム（Ｓ）と整合する誤り訂正装置（３４）であって、
前記選択は、有限トロイドを覆うセルの連続体（７０、１２０、１３０、１４０）を少なくとも定義するノードおよびエッジからなるネットワークにおける変数ノード（ｖ１〜ｖ１５）の総和ノード（ｓ１〜ｓ１２）への接続に基づいており、
前記セルの各々は、交互に配置され、エッジによりループ状に相互接続する同一数の変数ノード（ｖ１〜ｖ１２）および総和ノード（ｓ１〜ｓ１２）により区切られており、
前記変数ノードの各々は受信されるデータ列のビット位置にそれぞれ対応し、
前記総和ノードの各々は前記モジュロ２加算した演算結果にそれぞれ対応する、
ことを特徴とする誤り訂正装置。
【請求項１１】
前記ノードおよびエッジからなるネットワークは更に、
各々が変数ノード（ｖ）又は総和ノード（ｓ）の一方の種類のノードを備え、
エッジにより総和ノード（ｓ）又は変数ノード（ｖ）の他方の種類からランダムに選択されるノードに接続される複数のクモ構造（９０）を定義し、
前記他方の種類はまた前記セルの連続体（７０、１２０、１３０、１４０）を規定する際にも用いられる、
ことを特徴とする請求項１０に記載の誤り訂正装置。
【請求項１２】
前記変数ノードは受信されるデータ列のビット位置にランダムに対応する、ことを特徴とする請求項１０に記載の誤り訂正装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７Ａ】
【図２７Ｂ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７Ａ】
【図２７Ｂ】
【公表番号】特表２０１１−５０２３８９（Ｐ２０１１−５０２３８９Ａ）
【公表日】平成２３年１月２０日（２０１１．１．２０）
【国際特許分類】
【出願番号】特願２０１０−５３０５５８（Ｐ２０１０−５３０５５８）
【出願日】平成２０年１０月１４日（２００８．１０．１４）
【国際出願番号】ＰＣＴ／ＧＢ２００８／０５０９３９
【国際公開番号】ＷＯ２００９／０５６８７１
【国際公開日】平成２１年５月７日（２００９．５．７）
【出願人】（５０３００３８５４）ヒューレット−パッカード デベロップメント カンパニー エル．ピー． (1,145)
【Ｆターム（参考）】
【公表日】平成２３年１月２０日（２０１１．１．２０）
【国際特許分類】
【出願日】平成２０年１０月１４日（２００８．１０．１４）
【国際出願番号】ＰＣＴ／ＧＢ２００８／０５０９３９
【国際公開番号】ＷＯ２００９／０５６８７１
【国際公開日】平成２１年５月７日（２００９．５．７）
【出願人】（５０３００３８５４）ヒューレット−パッカード デベロップメント カンパニー エル．ピー． (1,145)
【Ｆターム（参考）】
[ Back to top ]