(57)【要約】【課題】Ｎ個のチャネルを用いてデータを安全に分散させ格納する方法および装置が提供される。【解決手段】入力データ・シーケンスＸは、複数Ｎのチャネルを用いて分散される。一実施形態では、入力データ・シーケンスＸはＮ個のサブシーケンスに分割され、そのＮ個のサブシーケンスは、Ｎ個の別々のエンコーダおよびジョイント・デコーダを有するスレピアン・ウルフ符合のセットを用いて符号化されてＮ個のビット・ストリームとされる。スレピアン・ウルフ符号は、入力データ・シーケンスの一部を得るための計算の複雑さが、Ｎ個のビット・ストリームの全てが危険にさらされるのでなければ、入力データ・シーケンスの長さに関して指数関数的に増大することを保証するように選択され得る。他の１つの実施形態では、入力データ・シーケンスＸは無損失データ圧縮手法を用いて圧縮され、その圧縮された入力データ・シーケンスは分割されて、分散されるＮ個のサブシーケンスとされる。【選択図】図３
2013520926.tif 000002
【特許請求の範囲】
【請求項１】
複数Ｎのチャネルを用いて入力データ・シーケンスＸを分散させる方法であって、
前記入力データ・シーケンスＸをＮ個のサブシーケンスに分割すること、
Ｎ個の別々のエンコーダおよびジョイント・デコーダを有するスレピアン・ウルフ符合のセットを用いて前記Ｎ個のサブシーケンスを符号化してＮ個のビット・ストリームとすること、および
前記Ｎ個のチャネルを用いて前記Ｎ個のビット・ストリームを分散させること、
を含む方法。
【請求項２】
前記スレピアン・ウルフ符号は、前記入力データ・シーケンスの一部を得るための計算の複雑さが、前記Ｎ個のビット・ストリームの全てが危険にさらされるのでなければ、前記入力データ・シーケンスの長さに関して指数関数的に増大することを保証するように選択される、請求項１に記載の方法。
【請求項３】
前記Ｎ個のビット・ストリームを結合させて前記入力データ・シーケンスとする前記ステップをさらに含む、請求項１に記載の方法。
【請求項４】
前記スレピアン・ウルフ符号は、Ｎ個のビット・ストリームの全てが利用可能であれば前記Ｎ個のサブシーケンスが完全に復号されることを保証するように選択される、請求項１に記載の方法。
【請求項５】
前記分散ステップは、前記Ｎ個のビット・ストリームを送信することおよび前記Ｎ個のビット・ストリームを記憶媒体に格納することのうちの１つ以上を含む、請求項１に記載の方法。
【請求項６】
前記Ｎ個のチャネルは、一時的にかつ空間的に分散させられている宛て先のうちの１つ以上を含む、請求項１に記載の方法。
【請求項７】
前記Ｎ個のサブシーケンスは、長さＬ１、Ｌ２、・・・ＬＮをそれぞれ有するデータＸ１、Ｘ２、・・・、ＸＮを含み、前記スレピアン・ウルフ符号は前記データＸ１、Ｘ２、・・・、ＸＮを率Ｒ１、Ｒ２、・・・、ＲＮで符号化してＮ個のビット・ストリームとする、請求項１に記載の方法。
【請求項８】
前記スレピアン・ウルフ符号は、Ｘが完全に復号され得るという条件のもとで０≦（Ｒ１＋Ｒ２＋・・・＋ＲＮ）／Ｎ−Ｈ（Ｘ）が実質的に最小にされることを保証するように選択され、ここでＨ（Ｘ）はＸのエントロピー・レートを意味する、請求項１に記載の方法。
【請求項９】
前記スレピアン・ウルフ符号は、Ｘが完全に復号され得るという条件のもとで０≦Ｈ（Ｘｉ｜Ｔｉ）−Ｒｉが実質的に最大にされることを保証するように選択され、ここでＴｉは｛Ｘ１、・・・Ｘｉ−１、Ｘｉ＋１、・・・ＸＮ｝の任意の真部分集合であり、Ｈ（Ｘｉ｜Ｔｉ）はＴｉが与えられたときのＸｉの条件付きエントロピー・レートを意味する、請求項１に記載の方法。
【請求項１０】
前記スレピアン・ウルフ符号は低密度パリティ検査（ＬＤＰＣ：ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ）符号として実装される、請求項１に記載の方法。
【請求項１１】
前記スレピアン・ウルフ符号は、前記Ｎ個のサブシーケンスを符号化して、その率がユーザ入力、送信チャネルの状態、および格納要件のうちの１つ以上から生じる制約条件に従う前記Ｎ個のビット・ストリームとするように選択される、請求項１に記載の方法。
【請求項１２】
前記分割ステップの前に可逆変換を用いて前記入力データ・シーケンスを処理する前記ステップをさらに含む、請求項１に記載の方法。
【請求項１３】
複数Ｎのチャネルを用いて入力データ・シーケンスＸを分散させる方法であって、
無損失データ圧縮手法を用いて前記入力データ・シーケンスＸを圧縮すること、
前記圧縮された入力データ・シーケンスをＮ個のサブシーケンスに分割すること、および
前記Ｎ個のチャネルを用いて前記Ｎ個のサブシーケンスを分散させること、
を含む方法。
【請求項１４】
前記Ｎ個のサブシーケンスを結合させて前記入力データ・シーケンスとする前記ステップをさらに含む、請求項１３に記載の方法。
【請求項１５】
前記分散ステップは、前記Ｎ個のサブシーケンスを送信することおよび前記Ｎ個のサブシーケンスを記憶媒体に格納することのうちの１つ以上を含む、請求項１３に記載の方法。
【請求項１６】
前記Ｎ個のチャネルは、一時的にかつ空間的に分散させられている宛て先のうちの１つ以上を含む、請求項１３に記載の方法。
【請求項１７】
前記分割ステップの前に可逆変換を用いて前記入力データ・シーケンスを処理する前記ステップをさらに含む、請求項１３に記載の方法。
【請求項１８】
複数Ｎのチャネルを用いて入力データ・シーケンスＸを分散させるためのコンピュータ・プログラム製品であって、前記コンピュータ・プログラム製品は、コンピュータ可読プログラム・コードが具体化されているコンピュータ可読記憶媒体を含み、前記コンピュータ可読プログラム・コードは、
前記入力データ・シーケンスＸをＮ個のサブシーケンスに分割するように構成されているコンピュータ可読プログラム・コード、
Ｎ個の別々のエンコーダおよびジョイント・デコーダを有するスレピアン・ウルフ符合のセットを用いて前記Ｎ個のサブシーケンスを符号化してＮ個のビット・ストリームとするように構成されているコンピュータ可読プログラム・コード、および
前記Ｎ個のチャネルを用いて前記Ｎ個のビット・ストリームを分散させるように構成されているコンピュータ可読プログラム・コード、
を含むコンピュータ・プログラム製品。
【請求項１９】
前記スレピアン・ウルフ符号は、前記入力データ・シーケンスの一部を得るための計算の複雑さが、前記Ｎ個のビット・ストリームの全てが危険にさらされるのでなければ、前記入力データ・シーケンスの長さに関して指数関数的に増大することを保証するように選択される、請求項１８に記載のコンピュータ・プログラム製品。
【請求項２０】
前記スレピアン・ウルフ符号は、Ｎ個のビット・ストリームの全てが利用可能であれば前記Ｎ個のサブシーケンスが完全に復号されることを保証するように選択される、請求項１８に記載のコンピュータ・プログラム製品。
【請求項２１】
前記分散は前記Ｎ個のビット・ストリームを送信することおよび前記Ｎ個のビット・ストリームを記憶媒体に格納することのうちの１つ以上を含む、請求項１８に記載のコンピュータ・プログラム製品。
【請求項２２】
複数Ｎのチャネルを用いて入力データ・シーケンスＸを分散させるための装置であって、
前記入力データ・シーケンスをＮ個のサブシーケンスに分割するスプリッタ、
前記Ｎ個のサブシーケンスを符号化してＮ個のビット・ストリームとするためのＮ個の別々のエンコーダおよび１つのジョイント・デコーダを有するスレピアン・ウルフ符号のセット、および
前記入力データ・シーケンスの一部を得るための計算の複雑さが、前記Ｎ個のビット・ストリームの全てが危険にさらされるのでなければ、前記入力データ・シーケンスの長さに関して指数関数的に増大することを保証するように前記スレピアン・ウルフ符号を選択する符号セレクタ、
を含む装置。
【請求項２３】
前記スレピアン・ウルフ符号は、前記入力データ・シーケンスの一部を得るための計算の複雑さが、前記Ｎ個のビット・ストリームの全てが危険にさらされるのでなければ、前記入力データ・シーケンスの長さに関して指数関数的に増大することを保証するように選択される、請求項２２に記載の装置。
【請求項２４】
前記スレピアン・ウルフ符号は、Ｎ個のビット・ストリームの全てが利用可能であれば前記Ｎ個のサブシーケンスが完全に復号されることを保証するように選択される、請求項２２に記載の装置。
【請求項２５】
前記Ｎ個のチャネルは一時的にかつ空間的に分散させられている宛て先のうちの１つ以上を含む、請求項２２に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には電気、電子およびコンピュータ技術に関し、特にデータの格納および分散に関する。
【背景技術】
【０００２】
１つまたは複数の通信チャネルを通してデータを送信するとき、幾つかの技術上の難題に遭遇する。第１に、その１つまたは複数の通信チャネルの帯域幅が効率的に利用されることが重要である。さらに、意図的でないアクセスあるいは許可されていないアクセスからデータが保護されることが重要である。伝統的に、この２つの難題は、それぞれ圧縮技術および暗号化技術を用いて別々に対処されている。例えば、意図された１つまたは複数の受け側によってデータが完全に回復されなければならないときには、それは、ハフマン符号またはレンペル・ジフ（Ｌｅｍｐｅｌ−Ｚｉｖ）アルゴリズムのような無損失圧縮アルゴリズムを用いて圧縮され、その後にＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ（データ暗号化標準））標準またはＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ（アドバンスト暗号化標準））標準に基づく秘密鍵ベースのサイファ、あるいはＲＳＡ暗号化技術にもとづくもののような公開鍵ベースのサイファを用いて暗号化されることができる。
【０００３】
唯一の通信チャネルが使用される場合には、暗号化鍵を入手する攻撃が成功すればデータは完全に危険にさらされる。従って、データを送るために複数の通信チャネルを使用することによってリスクを減少させたいであろう。例えば、Ｎ個の通信チャネルが利用可能であるならば、データはＮ個の部分に分割されることができ、その各々が、Ｎ個のチャネルのうちの１つを通して送信される前に圧縮され暗号化される。従って、アタッカーは、データを完全に危うくする前にＮ個のチャネルの全てにおいて使用されている暗号化サイファを解読しなければならない。しかし、解読された各サイファで、アタッカーはデータの少なくとも一部を習得する。この部分的セキュリティ・ブリーチは、特にデータが高度にセンシティブであるとき（例えば、社会保障番号のようなプライベート情報）、なお望ましくない。
【０００４】
データのセキュリティが特に重要であるとき、データが危険にさらされるのはＮ個のチャネルのすべてが危険にさらされた場合だけに限られるべきである。換言すれば、部分的セキュリティ・ブリーチは許されない。通例、このセキュリティ制約条件は、（Ｎ，Ｎ）秘密共有法を用いて満たされる。例えば、参照により本明細書に組み込まれるエイ・シャミア（Ａ．Ｓｈａｍｉｒ）の非特許文献１：「秘密を共有する方法（Ｈｏｗ  ｔｏ  Ｓｈａｒｅ  ａ  Ｓｅｃｒｅｔ）」、ＡＣＭ通信（Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ）、第２２巻、６１２−１３（１９７９年）を参照されたい。一般的に、（Ｎ，Ｎ）秘密共有法は秘密（すなわち、データ）をＮ個の関係者に分配する。しかし、完全な秘密共有法は、その秘密の各分け前がその秘密自体と同じ大きさであることを必要とする。従って、完全な（Ｎ，Ｎ）秘密共有法を用いて送信されるべき合計ビット数は、圧縮されたデータのビット単位での長さのＮ倍である。送信されるべきビットの数のこの増大は、帯域幅利用という観点からは余りに高コストであることが分かるであろう。
【０００５】
完全な秘密共有を成し遂げずに、部分的セキュリティ・ブリーチからデータをより良く保護するために、１つの可能な方法は、（ｉ）可逆変換を用いてデータを変換し、（ｉｉ）その変換済みデータをＮ個の部分に分解し、その後に（ｉｉｉ）送信する前にそのＮ個の部分を別々に圧縮し暗号化することである。この方法の主な問題点は、各サイファを解読した結果としてアタッカーが得る該データに関する情報の量がなお著しいことである。例えば、該変換が可逆フーリエ変換であるならば、各々の解読されたサイファで、アタッカーは変換（周波数）領域における該データに関する情報を入手するであろう。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ａ．Ｓｈａｍｉｒ，“Ｈｏｗ  ｔｏ  Ｓｈａｒｅ  ａ  Ｓｅｃｒｅｔ，”Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ，Ｖｏｌ．２２，６１２−１３（１９７９）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
従って、Ｎ個の通信チャネルにデータを分散させる（あるいはＮ個の宛て先にデータを格納する）改良された方法および装置に対する需要がある。
【課題を解決するための手段】
【０００８】
一般的に、Ｎ個のチャネルを用いてデータを安全に分散させ格納する方法および装置が提供される。本発明の１つの側面に従って、入力データ・シーケンスＸは複数Ｎのチャネルを用いて分散させられる。入力データ・シーケンスＸはＮ個のサブシーケンスに分割され、そのＮ個のサブシーケンスは、Ｎ個の別々のエンコーダおよびジョイント・デコーダを有するスレピアン・ウルフ（Ｓｌｅｐｉａｎ−Ｗｏｌｆ）符号のセットを用いて符号化されてＮ個のビット・ストリームとされる。スレピアン・ウルフ符号は、Ｎ個のビット・ストリームの全てが危険にさらされない限り、入力データ・シーケンスの一部分を得るための計算の複雑さが該入力データ・シーケンスの長さに関して指数関数的に増大することを保証するように選択され得る。Ｎ個のビット・ストリームは、その後、送信または格納される。レシーバにおいて、Ｎ個のビット・ストリームは、オプションで結合されて該入力データ・シーケンスとされ得る。
【０００９】
スレピアン・ウルフ符号は、Ｎ個のビット・ストリームの全てが利用可能であれば、Ｎ個のサブシーケンスが完全に復号されることを保証するようにも選択され得る。Ｎ個のサブシーケンスは長さＬ１、Ｌ２、・・・ＬＮをそれぞれ有するデータＸ１、Ｘ２、・・・、ＸＮを含み、スレピアン・ウルフ符号はデータＸ１、Ｘ２、・・・、ＸＮをＲ１、Ｒ２、・・・ＲＮの率で符号化してＮ個のビット・ストリームとする。スレピアン・ウルフ符号は、（ｉ）Ｘが完全に復号され得るという条件のもとで、０≦（Ｒ１＋Ｒ２＋・・・＋ＲＮ）／Ｎ−Ｈ（Ｘ）が実質的に最小にされることであって、ここでＨ（Ｘ）はＸのエントロピー・レートを意味する、該最小にされることと；（ｉｉ）Ｘが完全に復号され得るという条件のもとで０≦Ｈ（Ｘｉ｜Ｔｉ）−Ｒｉが実質的に最大にされることであって、ここでＴｉは｛Ｘ１、・・・Ｘｉ−１、Ｘｉ＋１、・・・ＸＮ｝の任意の真部分集合を意味し、Ｈ（Ｘｉ｜Ｔｉ）はＴｉが与えられたときのＸｉの条件付きエントロピー・レートを意味する、該最大にされること、のうちの一方または両方を保証するように選択され得る。
【００１０】
スレピアン・ウルフ符号は、Ｎ個のサブシーケンスを符号化して、その率がユーザ入力、送信チャネルの状態、および格納要件のうちの１つ以上から生じる制約条件に従うＮ個のビット・ストリームとするように選択され得る。入力データ・シーケンスは、オプションで、分割ステップの前に可逆変換を用いて前処理されることができる。
【００１１】
本発明の他の１つの側面に従って、入力データ・シーケンスＸは、複数Ｎのチャネルを用いて分散させられる。入力データ・シーケンスＸは、無損失データ圧縮技術を用いて圧縮され；その圧縮された入力データ・シーケンスを分割してＮ個のサブシーケンスとし；そのＮ個のサブシーケンスは分散させられる。
【００１２】
本発明、および本発明のさらなる特徴および利点のより詳しい理解は、以下の詳細な説明および図面を参照することにより得られるであろう。
【図面の簡単な説明】
【００１３】
【図１】データ・シーケンスを保護するために暗号化を使用する伝統的な（Ｎ，Ｎ）秘密共有法１００を示す。
【図２】伝統的なスレピアン・ウルフ符号化システムを示す。
【図３】本発明の１つの実施態様に従うスレピアン・ウルフ符号化システムを組み込んだ安全なデータ分散／格納システムを示す。
【図４】本発明の１つの代わりの実施態様に従うスレピアン・ウルフ符号化システムを組み込んだ安全なデータ分散／格納システムを示す。
【図５】本発明の１つの代わりの実施態様に従う伝統的な無損失データ圧縮を使用する安全なデータ分散／格納システムを示す。
【図６】本発明の１つ以上の側面もしくは要素またはその両方を実施するのに有益であり得るコンピュータ・システム６００を表している。
【発明を実施するための形態】
【００１４】
本発明は、データをＮ個の通信チャネルに分散させる（またはデータをＮ個の宛て先に格納する）方法および装置を提供する。本発明の１つの側面はデータ・シーケンスを符号化してＮ個のビット・ストリームとし、それから該データは完全に回復され得る。そのＮ個のビット・ストリームは、その後、Ｎ個のチャネルに分散させられ、あるいはＮ個の宛て先に格納される。該データは、該Ｎ個のビット・ストリームの中のビットの総数は符号化前の該データを記述するために使われるそれより通例小さいので、圧縮される。該データのどの部分も、著しい計算上の努力が無ければ危険にさらされないので、該データの分散もしくは格納またはその両方は安全である。換言すれば、Ｎ個のビット・ストリームの全てが危険にさらされない限り、データのどんな部分を得るために必要な計算の複雑さもデータの長さに関して指数関数的に増大する。本明細書で使用される「Ｎ個のチャネルを通してのデータの送信」および「Ｎ個のチャネルへのデータの分散」という用語ならびにこれらの用語の変化形は、Ｎ個のチャネルを通してのデータの格納を含むものとする。
【００１５】
１つの実施態様では、本発明は、下記の制約条件を満たしながらデータをＮ個の通信チャネルに分散させる（あるいはデータをＮ個の宛て先に格納する）：
１．  帯域幅（または格納）リソースが効率的に利用される（例えば、送信されるビットの総数は、圧縮済みデータのビット数で表された長さに近い）；
２．  データは部分的セキュリティ・ブリーチから保護される（例えば、データのどの部分も、著しい計算上の努力が無ければ危険にさらされない；すなわち、Ｎ個のビット・ストリームの全てが危険にさらされない限り、データのどんな部分を得るために必要な計算の複雑さもデータの長さに関して指数関数的に増大する。
【００１６】
以下でさらに論じられる、本発明の１つの側面に従って、データＸを次のように符号化してＮ個のビット・ストリームとするためにＮ個の別々のエンコーダを有するスレピアン・ウルフ符号が使用される：Ｘは始めに等しい長さＬを有するＮ個の部分Ｘ１、Ｘ２、・・・、ＸＮに分解され、その後：
１．  ＸがＮ個のビット・ストリームから完全に回復され得るように；
２．  （Ｒ１＋Ｒ２＋・・・＋ＲＮ）／ＮがＸのエントロピー・レートＨ（Ｘ）に近いように；かつ
３．  全てのｉ＝１、２、・・・ＮについてＲｉ＜Ｈ（Ｘｉ）であって、ただしＨ（Ｘｉ）はＸｉのエントロピー・レートを意味する、ように；
Ｘ１、Ｘ２、・・・、ＸＮを符号化して率（入力シンボル当たりのビット数で表した）Ｒ１、Ｒ２、・・・、ＲＮをそれぞれ有するＮ個のビット・ストリームＢ１、Ｂ２、・・・、ＢＮとするためにスレピアン・ウルフ符号のＮ個のエンコーダが使用される。
【００１７】
第１の条件（すなわち、ＸがＮ個のビット・ストリームから完全に回復され得ること）は、もし
（Ｒ１＋Ｒ２＋・・・＋ＲＮ）／Ｎ＞Ｈ（Ｘ）
であるならば満たされ得る；
【００１８】
第２の条件は、圧縮を成し遂げるという目的に直接関連する。最後に、第３の条件は、たとえＢｉが危険にさらされても、アタッカーはＬｉに関して指数関数的である計算の複雑さを伴わずにＢｉからＸｉを回復することはできないということを示唆する。
【００１９】
以下でさらに論じられる本発明の他の１つの側面に従って、データは初めに圧縮され、その後にその圧縮済みデータは、送信または格納されるべくＮ個のビット・ストリームに分割される。もしその圧縮がほとんど完璧であるならば（すなわち、その圧縮が、データのエントロピー・レートにより与えられる理論上の限界を達成するならば）、圧縮済みデータを表すビット・ストリームは実質的に完全にランダムである。従って、少なくとも１つのビット・ストリームが危険にさらされない限り、データを完全に危険にさらすためにアタッカーは依然として指数関数的に大きな計算の複雑さを必要とする。もしデータがどのように分割されて送信されているかをアタッカーが知ったならば、アタッカーは、短時間にわたってＮ個の通信チャネルの全てを観察することによって、圧縮済みデータの連続的部分を解読することに自分の努力を集中しようと試みることができる。使用される圧縮アルゴリズムが圧縮済みデータの連続的部分を首尾よく復号することを阻止するように慎重に設計され作られていなければ、これは、ともすれば部分的セキュリティ・ブリーチに至ることがあり得る。
【００２０】
（Ｎ，Ｎ）秘密共有法
図１は、データ・シーケンスＸを保護するために暗号化を使用する伝統的な（Ｎ，Ｎ）秘密共有法１００を示す。図１に示されているように、送信側において、代表的（Ｎ，Ｎ）秘密共有法は、例えば可逆変換を用いてデータを変換する変換１１０と、変換済みデータをＮ個の部分に分解するスプリッタ１２０と、そのＮ個の部分を送信前に別々に圧縮しもしくは暗号化し、またはその両方を行うＮ個のオプションの圧縮／暗号化ブロック１３０−１ないし１３０−Ｎとを含む。
【００２１】
受信側において、代表的（Ｎ，Ｎ）秘密共有法１００は、送信されたＮ個の部分を解凍しもしくは復号し、またはその両方を行うＮ個の解凍／復号ブロック１４０−１ないし１４０−Ｎと、そのＮ個のオプションの解凍／復号ブロック１４０−１ないし１４０−Ｎの出力を結合させるマージ・ブロック１５０と、ブロック１１０により用いられた変換の逆を行う逆変換ブロック１６０とを含む。
【００２２】
スレピアン・ウルフ符号化
一般的に、スレピアン・ウルフ定理は、２つ以上の相関するデータ・ストリームの無損失圧縮を扱う。参照により本明細書に組み込まれる、ディー・スレピアン（Ｄ．Ｓｌｅｐｉａｎ）およびジェー・ケー・ウルフ（Ｊ．Ｋ．Ｗｏｌｆ）の「相関する情報源の無雑音符号化（Ｎｏｉｓｅｌｅｓｓ  Ｃｏｄｉｎｇ  ｏｆ  Ｃｏｒｒｅｌａｔｅｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｏｕｒｃｅｓ）」、情報理論に関するＩＥＥＥ会報（ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ）、第１９巻、４７１−８０．（１９７３年）を参照されたい。通例、相関するストリームの各々は別々に符号化され、これらエンコーダの全てからの圧縮済みデータは単一のデコーダによって共同的に復号される。一般的に、データ・ストリーム同士が独立していると仮定するエンコーダと比べて、別々のエンコーダは、データ・ストリーム同士が相関しているという事実を利用することによってより良好な圧縮率を達成することができる。
【００２３】
図２は、伝統的なスレピアン・ウルフ符号化システム２００を示す。図２に示されているように、代表的スレピアン・ウルフ符号化システム２００は、Ｎ個のエンコーダ２１０−１ないし２１０−Ｎおよびジョイント・デコーダ２５０を含む。スレピアン・ウルフ符号化システム２００は、Ｎ個のデータ・シーケンスＸ１、Ｘ２、・・・ＸＮを別々に圧縮してＮ個のビット・ストリームとする。そのＮ個のビット・ストリームは、それぞれ、シンボル当たりのビット数で表される率Ｒ１、Ｒ２、・・・、ＲＮを有する。ジョイント・デコーダ２５０は、Ｎ個のビット・ストリームを共同的に復号してＮ個のデータ・シーケンスＸ１、Ｘ２、・・・ＸＮとする。各エンコーダ２１０は、同じまたは異なるデータ率Ｒｉを独立に採用することができる。
Ｒｉ≧Ｈ（Ｘｉ｜Ｘ１・・・Ｘｉ−１Ｘｉ＋１・・・ＸＮ）
Ｒ１＋Ｒ２＋・・・＋ＲＮ≧Ｈ（Ｘ１Ｘ２・・・ＸＮ）
であることが特筆され、ここでＨ（Ｘ）はＸのエントロピー・レートを意味し、Ｔｉは｛Ｘ１、・・・Ｘｉ−１、Ｘｉ＋１、・・・ＸＮ｝の任意の真部分集合であり、Ｈ（Ｘｉ｜Ｔｉ）はＴｉが与えられたときのＸｉの条件付きエントロピー・レートを意味する。
【００２４】
スレピアン・ウルフ符号を用いる安全な分散／格納
前に指摘されたように、本発明の幾つかの側面はデータをＮ個の通信チャネルに分散させる（あるいはデータをＮ個の宛て先に格納する）。本発明の１つの側面に従って、データＸを次のように符号化してＮ個のビット・ストリームとするためにＮ個の別々のエンコーダを有するスレピアン・ウルフ符号が使用される：入力データＸは初めに等しい長さＬを有するＮ個の部分Ｘ１、Ｘ２、・・・、ＸＮに分解され、その後、Ｘ１、Ｘ２、・・・、ＸＮを符号化して率（入力シンボル当たりのビット数で表した）Ｒ１、Ｒ２、・・・、ＲＮをそれぞれ有するＮ個のビット・ストリームＢ１、Ｂ２、・・・、ＢＮとするためにスレピアン・ウルフ符号のＮ個のエンコーダが使用される。Ｎ個のエンコーダからの圧縮済みのＮ個のビット・ストリームＢ１、Ｂ２、・・・、ＢＮは単一のデコーダによって共同的に復号される。
【００２５】
図３は、本発明の１つの実施態様に従うスレピアン・ウルフ符号化システムを組み込んだ安全なデータ分散／格納システム３００を示す。一般的に、安全なデータ分散システム３００は、データＸを符号化してＮ個のビット・ストリームとするＮ個のエンコーダを有するスレピアン・ウルフ符号を採用する。
【００２６】
図３に示されているように、安全なデータ分散／格納システム３００は、スプリッタ３１０と、スレピアン・ウルフ符号化システム３２０と、マージャー３５０とを含む。代表的なスレピアン・ウルフ符号化システム３２０は、図２の対応するコンポーネントと同様に動作するＮ個のエンコーダ３３０−１ないし３３０−Ｎおよびジョイント・デコーダ３４０を含む。
【００２７】
図３に示されているように、入力データＸはスプリッタ３１０によって分割されて、等しい長さＬを有するＮ個の部分Ｘ１、Ｘ２、・・・、ＸＮとされる。Ｎ個のエンコーダ３３０−１ないし３３０−Ｎは、Ｘ１、Ｘ２、・・・、ＸＮを符号化して率（入力シンボル当たりのビット数で表した）Ｒ１、Ｒ２、・・・、ＲＮをそれぞれ有するＮ個のビット・ストリームＢ１、Ｂ２、・・・、ＢＮとする。Ｎ個のエンコーダ３３０−１ないし３３０−Ｎからの圧縮されたＮ個のビット・ストリームＢ１、Ｂ２、・・・、ＢＮは、単一のジョイント・デコーダ３４０によって共同的に復号される。マージ・ブロック３５０は、入力データＸを再生するために、復号された出力Ｘ１、Ｘ２、・・・、ＸＮを結合させる。マージ・ブロック３５０は、Ｎ個のサブシーケンスをマージして単一のデータ・シーケンスとすることによってスプリッタ３１０のプロセスを逆にする。
【００２８】
図４は、本発明の１つの代わりの実施態様に従うスレピアン・ウルフ符号化システムを組み込んだ安全なデータ分散／格納システム４００を示す。図４に示されているように、代表的な安全なデータ分散／格納システム４００は、スプリッタ４１０と、スレピアン・ウルフ符号セレクタ４１５と、スレピアン・ウルフ符号化システム４２０と、マージャー４５０とを含む。代表的なスレピアン・ウルフ符号化システム４２０は、図２の対応するコンポーネントと同様に動作するＮ個のエンコーダ４３０−１ないし４３０−Ｎおよびジョイント・デコーダ４４０を含む。
【００２９】
図４に示されているように、入力データＸは、スプリッタ４１０により、等しい長さＬを有するＮ個の部分Ｘ１、Ｘ２、・・・、ＸＮに分割される。符号セレクタ４１５は、以下でさらに論じられる方法で、Ｎ個のビット・ストリームの全てが利用可能であればＮ個のサブシーケンスが完全に復号され得、Ｎ個のビット・ストリームのうちの少なくとも１つが紛失していればＮ個のサブシーケンスのどれもが復号され得ないように、スプリッタ４１０の出力を符号化してＮ個のビット・ストリームとするために適切なスレピアン・ウルフ符号を選択するべく入力データＸを処理する。
【００３０】
選択されたスレピアン・ウルフ符号（Ｓｌｅｐｉａｎ−Ｗｏｌｆ  ｃｏｄｅ（ＳＷ符号））を用いて、Ｎ個のエンコーダ４３０は、Ｘ１、Ｘ２、・・・、ＸＮを符号化して率（入力シンボル当たりのビット数で表した）Ｒ１、Ｒ２、・・・、ＲＮをそれぞれ有するＮ個のビット・ストリームＢ１、Ｂ２、・・・、ＢＮとする。Ｎ個のエンコーダ４３０からの圧縮されているＮ個のビット・ストリームＢ１、Ｂ２、・・・、ＢＮは、選択されたスレピアン・ウルフ符号を再び用いて、単一のジョイント・デコーダ４４０によって共同的に復号される。マージ・ブロック４５０は、入力データＸを再生するために、復号された出力Ｘ１、Ｘ２、・・・、ＸＮを結合させる。
【００３１】
スレピアン・ウルフ符号の選択
以下の例を考察されたい。Ｘは、分散（または格納）されるべき長さＬを有するバイナリ・データ・シーケンスであると仮定する。Ｘを入力と見なして、スプリッタ４１０は入力データＸを等しい長さＬを有するＮ個のサブシーケンスＸ１、Ｘ２、・・・、ＸＮに分解する。並行して、符号セレクタ４１５は、Ｘのための符号のライブラリからＮ個のエンコーダ４３０を有する１つのスレピアン・ウルフ符号を選択する。その後、各Ｘｉ、ｉ＝１、２、・・・、Ｎ、は選択されたスレピアン・ウルフ符号の１つのエンコーダ４３０によって率Ｒｉで符号化されてビット・ストリームＢｉとされる。
【００３２】
帯域幅（または格納）リソースを効率的に利用するという目的のために、符号セレクタ４１５は、Ｘが完全に復号され得るという条件のもとで
０≦（Ｒ１＋Ｒ２＋・・・＋ＲＮ）／Ｎ−Ｈ（Ｘ）          制約条件（１）
が実質的に最小にされるように１つのスレピアン・ウルフ符号を発見しようと試み、ここでＨ（Ｘ）はＸのエントロピー・レートを意味する。
【００３３】
部分的セキュリティ・ブリーチからデータを保護するという目的のために、符号セレクタ４１５は、再びＸが完全に復号され得るという条件のもとで
０≦Ｈ（Ｘｉ｜Ｔｉ）−Ｒｉ                            制約条件（２）
が実質的に最大にされるように１つのスレピアン・ウルフ符号を発見しようと試み、ここでＴｉは｛Ｘ１、・・・Ｘｉ−１、Ｘｉ＋１、・・・ＸＮ｝の任意の真部分集合であり、Ｈ（Ｘｉ｜Ｔｉ）はＴｉが与えられたときのＸｉの条件付きエントロピー・レートを意味する。制約条件（２）が成り立つと仮定する。すると、Ｂｉが危険にさらされるとすれば、アタッカーがＢｉからＸｉを回復するために必要とする計算の複雑さはＬに関して指数関数的に増大する（その濃度｜Ｓｉ｜が
ｌｏｇ｜Ｓｉ｜〜Ｌ［Ｈ（Ｘｉ）−Ｒｉ］
を満たす集合Ｓｉの中での探索。ここで対数は底２に対するものである）。実際、安全なままであるＢｊが存在する限り、アタッカーがＢ１、・・・Ｂｊ−１、Ｂｊ＋１、・・・ＢＮからいずれかのＸｉ、ｉ≠ｊ、を回復するために必要とされる計算の複雑さは依然としてＬに関して指数関数的に増大する。
【００３４】
Ｈ（Ｘｉ｜Ｔｉ）＞Ｈ（Ｘｉ｜Ｘ１、・・・、Ｘｉ−１、Ｘｉ＋１、・・・、ＸＮ）
が全てのｉ＝１、２、・・・、Ｎ、およびＴｉの全ての選択肢について成り立つならば、制約条件（１）および（２）を同時に満たすスレピアン・ウルフ符号が存在することに留意されたい。ここでＨ（Ｘｉ｜Ｘ１、・・・、Ｘｉ−１、Ｘｉ＋１、・・・、ＸＮ）は、Ｘ１、・・・、Ｘｉ−１、Ｘｉ＋１、・・・、ＸＮが与えられたときのＸｉの条件付きエントロピー・レートを意味する。
【００３５】
圧縮されたデータの分割を用いる安全な分散／格納
前に指摘されたように、本発明の他の１つの態様は、初めに入力データを圧縮し、その後にその圧縮されたデータは、安全に送信または格納されるべくＮ個のビット・ストリームに分割される。本発明は、もしその圧縮がほとんど完璧であるならば（すなわち、その圧縮が、データのエントロピー・レートにより与えられる理論上の限界を実質的に達成するならば）、圧縮済みデータを表すビット・ストリームは実質的に完全にランダムであることを認識している。従って、少なくとも１つのビット・ストリームが危険にさらされない限り、データを完全に危険にさらすためにアタッカーは依然として指数関数的に大きな計算の複雑さを必要とする。もしデータがどのように分割されて送信されているかをアタッカーが知ったならば、アタッカーは、短時間にわたってＮ個の通信チャネルの全てを観察することによって、圧縮済みデータの連続的部分を解読することに自分の努力を集中しようと試みることができる。使用される圧縮アルゴリズムが圧縮済みデータの連続的部分を首尾よく復号することを阻止するように慎重に設計され作られていなければ、これは、ともすれば部分的セキュリティ・ブリーチに至ることがあり得る。
【００３６】
図５は、本発明の１つの代わりの実施態様に従う伝統的な無損失データ圧縮を使用する安全なデータ分散／格納システム５００を示す。図５に示されているように、安全なデータ分散／格納システム５００は、無損失データ・コンプレッサ５１０およびスプリッタ５２０を含む。従って、安全なデータ分散／格納システム５００は入力データを無損失データ・コンプレッサ５１０で圧縮し、その後、圧縮済みデータは安全に送信または格納されるべくスプリッタ５２０によってＮ個のビット・ストリームに分割される。
【００３７】
少なくとも１つのビット・ストリームが危険にさらされない限り、データを完全に危険にさらすためには指数関数的に大きな計算の複雑さが必要とされる。
【００３８】
ハフマン符号化手法またはランプ・ジフ（Ｌａｍｐ−Ｚｉｖ）符号化手法のような、適切な無損失圧縮手法が幾つか存在する。
【００３９】
代表的システムおよび製造品の詳細
当業者に認められるであろうように、本発明の態様はシステム、方法またはコンピュータ・プログラム製品として具体化され得る。従って、本発明の態様は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）またはソフトウェアと、本明細書では「回路」、「モジュール」もしくは「システム」と全く一般的に称され得るハードウェア側面とを結合させた実施形態の形をとることができる。さらに、本発明の態様は、コンピュータ可読プログラム・コードが具体化されている１つ以上のコンピュータ可読媒体において具体化されたコンピュータ・プログラム製品の形をとることができる。
【００４０】
本発明の１つ以上の実施形態、あるいはその要素は、メモリと、該メモリに結合されて代表的方法ステップを実行するように動作することのできる少なくとも１つのプロセッサとを含む装置の形で実施され得る。
【００４１】
１つ以上の実施形態は、汎用コンピュータまたはワークステーション上で動作するソフトウェアを使用することができる。図６は、本発明の１つ以上の側面もしくは要素またはその両方を実施するうえで有益であり得るコンピュータ・システム６００を表している。図６を参照すると、そのような実施は、例えば、プロセッサ６０２と、メモリ６０４と、例えばディスプレイ６０６およびキーボード６０８により形成される入力／出力インターフェースとを採用することができる。本明細書で使用される用語「プロセッサ」は、例えば、中央処理装置（ＣＰＵ：ｃｅｎｔｒａｌ  ｐｒｏｃｅｓｓｉｎｇ  ｕｎｉｔ）もしくは他の形の処理回路またはその両方を含むもののような任意の処理装置を含むように意図されている。さらに、用語「プロセッサ」は、２つ以上の個々のプロセッサを指すことがあり得る。用語「メモリ」は、例えば、ランダム・アクセス・メモリ（ＲＡＭ：ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）、読み出し専用メモリ（ＲＯＭ：ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ）、固定記憶装置（例えば、ハードディスク）、取り外し可能な記憶装置（例えば、ディスケット）、フラッシュ・メモリ等の、プロセッサまたはＣＰＵと関連付けられたメモリを含むように意図されている。さらに、本明細書で使用される句「入力／出力インターフェース」は、例えば、データを処理装置に入力するための１つ以上のメカニズム（例えば、マウス）と、処理装置と関連付けられた結果を提供するための１つ以上のメカニズム（例えば、プリンタ）とを含むように意図されている。プロセッサ６０２と、メモリ６０４と、ディスプレイ６０６およびキーボード６０８のような入力／出力インターフェースとは、例えば、データ処理装置６１２の一部としてのバス６１０を介して相互に接続され得る。例えばバス６１０を介する、適切な相互接続は、コンピュータ・ネットワークとインターフェースするように設けられ得るネットワーク・カードのようなネットワーク・インターフェース６１４にも、さらに、媒体６１８とインターフェースするように設けられ得るディスケットまたはＣＤ−ＲＯＭドライブのような媒体インターフェース６１６にも、提供され得る。
【００４２】
１つまたは複数のアナログ・デジタル変換器６２０は、アナログ・ビデオ・フィードのようなアナログ入力を受け取ってそれをデジタル化するために設けられ得る。そのような１つ以上の変換器は、システム・バス６１０と相互接続され得る。
【００４３】
従って、本明細書に記載された、本発明の方法論を実行するための命令またはコードを含むコンピュータ・ソフトウェアは、関連付けられた記憶装置（例えば、ＲＯＭ、固定されたまたは取り外し可能なメモリ）のうちの１つ以上に格納され、利用され得る状態であるとき、一部または全部がロードされ（例えば、ＲＡＭに）ＣＰＵによって実行され得る。そのようなソフトウェアは、ファームウェア、常駐ソフトウェア、マイクロコード等を含み得るが、これらに限定されない。
【００４４】
プログラム・コードを格納しもしくは実行するために、またはそれら両方のために適切なデータ処理システムは、システム・バス６１０を通してメモリ素子６０４に直接的にまたは間接的に結合された少なくとも１つのプロセッサ６０２を含むことになる。該メモリ素子は、プログラム・コードの実際の実行中に使用されるローカル・メモリ、大容量記憶装置、および実行中にコードが大容量記憶装置から取り出されなければならない回数を減らすために少なくとも一部のプログラム・コードの一時的格納を提供するキャッシュ・メモリを含むことができる。
【００４５】
入力／出力またはＩ／Ｏデバイス（キーボード６０８、ディスプレイ６０６、ポインティング・デバイス等を含むが、これらに限定されない）は、直接に（バス６１０を介するなどして）または介在するＩ／Ｏコントローラ（明瞭性を目的として省略されている）を介して該システムに結合され得る。
【００４６】
ネットワーク・インターフェース６１４のようなネットワーク・アダプタも、該データ処理システムが介在する私的または公衆ネットワークを通して、他のデータ処理システムもしくはリモート・プリンタもしくは記憶装置に結合され得るように、該システムに結合され得る。モデム、ケーブル・モデムおよびイーサネット（Ｒ）・カードは、現在利用し得るタイプのネットワーク・アダプタのうちのほんの一部である。
【００４７】
請求項を含んで、本明細書で使用される「サーバ」は、サーバ・プログラムを実行する物理的データ処理システム（例えば、図６に示されているシステム６１２）を含む。そのような物理的サーバはディスプレイおよびキーボードを含むことも含まないこともあるということが理解されるであろう。
【００４８】
特筆されたように、本発明の態様は、コンピュータ可読プログラム・コードが具体化されている１つ以上のコンピュータ可読媒体において具体化されたコンピュータ・プログラム製品の形をとることができる。１つ以上のコンピュータ可読媒体の任意の組み合わせが利用され得る。コンピュータ可読媒体は、コンピュータ可読信号媒体またはコンピュータ可読記憶媒体であり得る。コンピュータ可読記憶媒体は、例えば、電子、磁気、光学、電磁、赤外線もしくは半導体のシステム、装置、もしくはデバイス、または前記のものの任意の適切な組み合わせであり得るが、これらに限定されない。媒体ブロック６１８は、１つの非限定的な例である。コンピュータ可読記憶媒体のさらに具体的な例（非網羅的なリスト）は、次のもの、すなわち、１つ以上のワイヤを有する電気的結線、携帯用コンピュータ・ディスケット、ハード・ディスク、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、消去可能でプログラマブルな読み出し専用メモリ（ＥＰＲＯＭ：ｅｒａｓａｂｌｅ  ｐｒｏｇｒａｍｍａｂｌｅ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙまたはフラッシュ・メモリ）、光ファイバ、携帯用コンパクト・ディスク読み出し専用メモリ（ＣＤ−ＲＯＭ：ｃｏｍｐａｃｔ  ｄｉｓｃ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）、光学記憶装置、磁気記憶装置、または前記のものの任意の適切な組み合わせを含むであろう。この文書の文脈において、コンピュータ可読記憶媒体は、命令実行システム、装置、またはデバイスにより、あるいはこれらと関連して、使用されるプログラムを包含あるいは記憶することのできる任意の有形媒体であり得る。
【００４９】
コンピュータ可読信号媒体は、コンピュータ可読プログラム・コードが中に具体化されている、例えばベースバンドにおいて、あるいは搬送波の一部として、伝播されるデータ信号を含み得る。そのような伝播される信号は、電磁、光学、またはそれらの任意の適切な組み合わせを含むがこれらに限定されない、種々の形のうちのいずれをもとることができる。コンピュータ可読信号媒体は、コンピュータ可読記憶媒体ではなくて、命令実行システム、装置、またはデバイスにより、あるいはこれらと関連して、使用されるプログラムを伝達し、伝播し、あるいはトランスポートすることのできる任意のコンピュータ可読媒体であり得る。
【００５０】
コンピュータ可読媒体上で具体化されるプログラム・コードは、無線、ワイヤライン、光ファイバ・ケーブル、ＲＦ等、あるいは前記のものの任意の適切な組み合わせを含むがこれらに限定されない任意の適切な媒体を用いて送信され得る。
【００５１】
本発明の態様のための動作を実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ（Ｒ）、Ｓｍａｌｌｔａｌｋ（Ｒ）、Ｃ＋＋等のようなオブジェクト指向プログラミング言語と、“Ｃ”プログラミング言語もしくは類似のプログラミング言語のような伝統的な手続き型プログラミング言語とを含む１つ以上のプログラミング言語の任意の組み合わせで書かれ得る。該プログラム・コードは、完全にユーザのコンピュータ上で、スタンド・アロン・ソフトウェア・パッケージとして部分的にユーザのコンピュータ上で、部分的にユーザのコンピュータ上でかつ部分的にリモート・コンピュータ上で、あるいは完全にリモート・コンピュータもしくはサーバ上で実行することができる。後者のシナリオでは、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ：ｌｏｃａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ）もしくはワイド・エリア・ネットワーク（ＷＡＮ：ｗｉｄｅ  ａｒｅａ  ｎｅｔｗｏｒｋ）を含む任意のタイプのネットワークを通してユーザのコンピュータに接続されることができ、あるいは（例えば、インターネット・サービス・プロバイダを用いてインターネットを通して）外部コンピュータに接続されることができる。
【００５２】
本発明の実施形態に従う方法、装置（システム）およびコンピュータ・プログラム製品のフローチャート図もしくはブロック図またはその両方を参照して本発明の態様が以下に記述される。該フローチャート図もしくはブロック図またはその両方の各ブロック、ならびに該フローチャート図もしくはブロック図またはその両方の中のブロックの組み合わせはコンピュータ・プログラム命令によって実行され得るということが理解されるであろう。コンピュータまたは他のプログラマブルなデータ処理装置のプロセッサを介して実行する命令が、該フローチャートもしくはブロック図またはその両方の１つまたは複数のブロックにおいて明示されている機能／行為を実行するための手段を創造するように、これらのコンピュータ・プログラム命令は１つのマシンを作るべく汎用コンピュータ、専用コンピュータ、または他のプログラマブルなデータ処理装置のプロセッサに提供され得る。
【００５３】
コンピュータ可読媒体に格納された命令が、該フローチャートもしくはブロック図またはその両方の中の１つまたは複数のブロックにおいて明示されている機能／行為を実行する命令を含む製造品を作るように、これらのコンピュータ・プログラム命令は、コンピュータ、他のプログラマブルなデータ処理装置、または他のデバイスに特定の仕方で機能するように指令することのできるコンピュータ可読媒体に格納されることもできる。
【００５４】
コンピュータまたは他のプログラマブルな装置上で実行する命令が、該フローチャートもしくはブロック図またはその両方の１つまたは複数のブロックにおいて明示されている機能／行為を実行するためのプロセスを提供するように、該コンピュータ・プログラム命令は、コンピュータ実行プロセスを生じさせるために一連の動作ステップを該コンピュータ、他のプログラマブルな装置または他のデバイス上で実行させるべくコンピュータ、他のプログラマブルなデータ処理装置、または他のデバイスにロードされることもできる。
【００５５】
図面のフローチャートおよびブロック図は、本発明の種々の実施形態に従うシステム、方法およびコンピュータ・プログラム製品の可能なインプリメンテーション（実現形態）のアーキテクチャ、機能、および動作を示す。この点について、フローチャートまたはブロック図の中の各ブロックは、コードのモジュール、セグメント、または部分を表すことができ、それには、明示された１つまたは複数の論理機能を実行するための１つ以上の実行可能な命令が含まれる。幾つかの代わりのインプリメンテーションでは、ブロックの中に記されている機能は図面に記されている順序とは異なる順序で行われることがあるということも留意されるべきである。例えば、連続して示されている２つのブロックは、実際には、実質的に同時に実行されることができ、あるいはそれらのブロックは、時には、関係する機能によっては逆の順序で実行され得る。ブロック図もしくはフローチャート図またはその両方の各ブロック、ならびにブロック図もしくはフローチャート図またはその両方の複数のブロックの組み合わせは、明示された機能または行為を実行する専用ハードウェア・ベースのシステムにより、あるいは専用ハードウェアおよびコンピュータ命令の組み合わせにより、実行され得るということも留意されるであろう。
【００５６】
本明細書に記載されている方法のステップは、例えば、そのようなステップを実行するようにプログラムされた汎用コンピュータに、あるいは、本明細書に記載されたように、そのようなステップを実行するためのハードウェアに、結び付けられ得る。さらに、例えばデータ・ストリームを獲得して該ストリームを符号化することを含む、本明細書に記載されている方法のステップは、該データ・ストリームが獲得されるカメラあるいはマイクロフォンのような物理的センサにも結び付けられ得る。
【００５７】
本明細書に記載されている方法のいずれもが、コンピュータ可読記憶媒体において具体化される複数の別々のソフトウェア・モジュールを含むシステムを提供するという追加のステップを含み得るということが留意されるべきである。そのとき方法のステップは、１つ以上のハードウェア・プロセッサ６０２上で実行する、上記の、該システムの該別々のソフトウェア・モジュールもしくはサブ・モジュールまたはその両方を用いて実行され得る。或る場合には、ここに記載された機能のうちの１つ以上を実行するために専用のハードウェアが使用され得る。さらに、コンピュータ・プログラム製品は、別々のソフトウェア・モジュールを伴う該システムを提供することを含む、本明細書に記載された１つ以上の方法のステップを実行するために実行されるように適合させられているコードを有するコンピュータ可読記憶媒体を含むことができる。
【００５８】
いずれの場合も、本明細書に示されているコンポーネントは、例えば、１つまたは複数の特定用途向け集積回路（ＡＳＩＣ：ａｐｐｌｉｃａｔｉｏｎ  ｓｐｅｃｉｆｉｃ  ｃｉｒｃｕｉｔ（ｓ））、機能回路、メモリと関連付けられた１つ以上の適宜プログラムされた汎用デジタル・コンピュータ等の、種々の形のハードウェア、ソフトウェア、またはそれらの組み合わせで実施され得ることが理解されるべきである。本明細書で提供されている本発明の教示が与えられれば、当業者は本発明のコンポーネントの他のインプリメンテーションを考えることができるであろう。
【００５９】
本明細書で使用されている用語は、特定の実施形態だけを記述することを目的とし、本発明を限定するように意図されてはいない。本明細書で使用される、単数形“ａ”、“ａｎ”および“ｔｈｅ”は、文脈が明らかに別様に意味していなければ、複数形をも含むように意図されている。用語“ｃｏｍｐｒｉｓｅｓ”もしくは“ｃｏｍｐｒｉｓｉｎｇ”またはその両方は、この明細書で使用されるとき、述べられた特徴、整数、ステップ、動作、要素、およびコンポーネントのうちの少なくとも１つの存在を明示するが、１つ以上の他の特徴、整数、ステップ、動作、要素、コンポーネントおよびそれらのグループのうちの少なくとも１つの存在または追加を除外しないことがさらに理解されるであろう。
【００６０】
添付されている請求項の中の全てのミーンズ・プラス・ファンクションまたはステップ・プラス・ファンクションの要素の対応する構造、材料、行為、および同等物は、明確に請求項に記載された他の要素と組み合わされた機能を実行するための任意の構造、材料、または行為を含むように意図されている。本発明の記述は解説および記述を目的として提示されているが、網羅的であることや、開示された形の発明に限定されることは意図されていない。本発明の範囲および趣旨から逸脱すること無く、多くの改変および変化形が当業者にとっては明らかであろう。実施形態は、本発明の原理および実際的な応用を最善に説明し、当業者が、考慮されている特定の使用法に適する種々の改変を伴う種々の実施形態を得るべく本発明を理解できるようにするために、選択され記述された。
【図１】
2013520926.tif 000003
【図２】
2013520926.tif 000004
【図３】
2013520926.tif 000005
【図４】
2013520926.tif 000006
【図５】
2013520926.tif 000007
【図６】
2013520926.tif 000008
【手続補正書】
【提出日】平成24年8月27日(2012.8.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数Ｎのチャネルを用いて入力データ・シーケンスＸを分散させる方法であって、
前記入力データ・シーケンスＸをＮ個のサブシーケンスに分割すること、
Ｎ個の別々のエンコーダおよびジョイント・デコーダを有するスレピアン・ウルフ符合のセットを用いて前記Ｎ個のサブシーケンスを符号化してＮ個のビット・ストリームとすること、および
前記Ｎ個のチャネルを用いて前記Ｎ個のビット・ストリームを分散させること、
を含む方法。
【請求項２】
前記スレピアン・ウルフ符号は、前記入力データ・シーケンスの一部を得るための計算の複雑さが、前記Ｎ個のビット・ストリームの全てが危険にさらされるのでなければ、前記入力データ・シーケンスの長さに関して指数関数的に増大することを保証するように選択される、請求項１に記載の方法。
【請求項３】
前記Ｎ個のビット・ストリームを結合させて前記入力データ・シーケンスとする前記ステップをさらに含む、請求項１に記載の方法。
【請求項４】
前記スレピアン・ウルフ符号は、Ｎ個のビット・ストリームの全てが利用可能であれば前記Ｎ個のサブシーケンスが完全に復号されることを保証するように選択される、請求項１に記載の方法。
【請求項５】
前記分散ステップは、前記Ｎ個のビット・ストリームを送信することおよび前記Ｎ個のビット・ストリームを記憶媒体に格納することのうちの１つ以上を含む、請求項１に記載の方法。
【請求項６】
前記Ｎ個のチャネルは、一時的にかつ空間的に分散させられている宛て先のうちの１つ以上を含む、請求項１に記載の方法。
【請求項７】
前記Ｎ個のサブシーケンスは、長さＬ１、Ｌ２、・・・ＬＮをそれぞれ有するデータＸ１、Ｘ２、・・・、ＸＮを含み、前記スレピアン・ウルフ符号は前記データＸ１、Ｘ２、・・・、ＸＮを率Ｒ１、Ｒ２、・・・、ＲＮで符号化してＮ個のビット・ストリームとする、請求項１に記載の方法。
【請求項８】
前記スレピアン・ウルフ符号は、Ｘが完全に復号され得るという条件のもとで０≦（Ｒ１＋Ｒ２＋・・・＋ＲＮ）／Ｎ−Ｈ（Ｘ）が実質的に最小にされることを保証するように選択され、ここでＨ（Ｘ）はＸのエントロピー・レートを意味する、請求項１に記載の方法。
【請求項９】
前記スレピアン・ウルフ符号は、Ｘが完全に復号され得るという条件のもとで０≦Ｈ（Ｘｉ｜Ｔｉ）−Ｒｉが実質的に最大にされることを保証するように選択され、ここでＴｉは｛Ｘ１、・・・Ｘｉ−１、Ｘｉ＋１、・・・ＸＮ｝の任意の真部分集合であり、Ｈ（Ｘｉ｜Ｔｉ）はＴｉが与えられたときのＸｉの条件付きエントロピー・レートを意味する、請求項１に記載の方法。
【請求項１０】
前記スレピアン・ウルフ符号は低密度パリティ検査（ＬＤＰＣ：ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ）符号として実装される、請求項１に記載の方法。
【請求項１１】
前記スレピアン・ウルフ符号は、前記Ｎ個のサブシーケンスを符号化して、その率がユーザ入力、送信チャネルの状態、および格納要件のうちの１つ以上から生じる制約条件に従う前記Ｎ個のビット・ストリームとするように選択される、請求項１に記載の方法。
【請求項１２】
前記分割ステップの前に可逆変換を用いて前記入力データ・シーケンスを処理する前記ステップをさらに含む、請求項１に記載の方法。
【請求項１３】
複数Ｎのチャネルを用いて入力データ・シーケンスＸを分散させる方法であって、
無損失データ圧縮手法を用いて前記入力データ・シーケンスＸを圧縮すること、
前記圧縮された入力データ・シーケンスをＮ個のサブシーケンスに分割すること、および
前記Ｎ個のチャネルを用いて前記Ｎ個のサブシーケンスを分散させること、
を含む方法。
【請求項１４】
前記Ｎ個のサブシーケンスを結合させて前記入力データ・シーケンスとする前記ステップをさらに含む、請求項１３に記載の方法。
【請求項１５】
前記分散ステップは、前記Ｎ個のサブシーケンスを送信することおよび前記Ｎ個のサブシーケンスを記憶媒体に格納することのうちの１つ以上を含む、請求項１３に記載の方法。
【請求項１６】
前記Ｎ個のチャネルは、一時的にかつ空間的に分散させられている宛て先のうちの１つ以上を含む、請求項１３に記載の方法。
【請求項１７】
前記分割ステップの前に可逆変換を用いて前記入力データ・シーケンスを処理する前記ステップをさらに含む、請求項１３に記載の方法。
【請求項１８】
複数Ｎのチャネルを用いて入力データ・シーケンスＸを分散させるためのコンピュータ・プログラムであって、前記コンピュータ・プログラムは、コンピュータ可読プログラム・コードを含み、前記コンピュータ可読プログラム・コードは、
前記入力データ・シーケンスＸをＮ個のサブシーケンスに分割するように構成されているコンピュータ可読プログラム・コード、
Ｎ個の別々のエンコーダおよびジョイント・デコーダを有するスレピアン・ウルフ符合のセットを用いて前記Ｎ個のサブシーケンスを符号化してＮ個のビット・ストリームとするように構成されているコンピュータ可読プログラム・コード、および
前記Ｎ個のチャネルを用いて前記Ｎ個のビット・ストリームを分散させるように構成されているコンピュータ可読プログラム・コード、
を含むコンピュータ・プログラム。
【請求項１９】
前記スレピアン・ウルフ符号は、前記入力データ・シーケンスの一部を得るための計算の複雑さが、前記Ｎ個のビット・ストリームの全てが危険にさらされるのでなければ、前記入力データ・シーケンスの長さに関して指数関数的に増大することを保証するように選択される、請求項１８に記載のコンピュータ・プログラム。
【請求項２０】
前記スレピアン・ウルフ符号は、Ｎ個のビット・ストリームの全てが利用可能であれば前記Ｎ個のサブシーケンスが完全に復号されることを保証するように選択される、請求項１８に記載のコンピュータ・プログラム。
【請求項２１】
前記分散は前記Ｎ個のビット・ストリームを送信することおよび前記Ｎ個のビット・ストリームを記憶媒体に格納することのうちの１つ以上を含む、請求項１８に記載のコンピュータ・プログラム。
【請求項２２】
複数Ｎのチャネルを用いて入力データ・シーケンスＸを分散させるための装置であって、
前記入力データ・シーケンスをＮ個のサブシーケンスに分割するスプリッタ、
前記Ｎ個のサブシーケンスを符号化してＮ個のビット・ストリームとするためのＮ個の別々のエンコーダおよび１つのジョイント・デコーダを有するスレピアン・ウルフ符号のセット、および
前記入力データ・シーケンスの一部を得るための計算の複雑さが、前記Ｎ個のビット・ストリームの全てが危険にさらされるのでなければ、前記入力データ・シーケンスの長さに関して指数関数的に増大することを保証するように前記スレピアン・ウルフ符号を選択する符号セレクタ、
を含む装置。
【請求項２３】
前記スレピアン・ウルフ符号は、前記入力データ・シーケンスの一部を得るための計算の複雑さが、前記Ｎ個のビット・ストリームの全てが危険にさらされるのでなければ、前記入力データ・シーケンスの長さに関して指数関数的に増大することを保証するように選択される、請求項２２に記載の装置。
【請求項２４】
前記スレピアン・ウルフ符号は、Ｎ個のビット・ストリームの全てが利用可能であれば前記Ｎ個のサブシーケンスが完全に復号されることを保証するように選択される、請求項２２に記載の装置。
【請求項２５】
前記Ｎ個のチャネルは一時的にかつ空間的に分散させられている宛て先のうちの１つ以上を含む、請求項２２に記載の装置。
【国際調査報告】
2013520926.tif 000009