(57)【要約】開示される発明は、暗号化オペレーションの回数を減らしつつ入力データ（１）をセキュア化することを意図する暗号化方法に特に関する。発明は、可変長非プレフィックスフリー（ＮＰＦ、non-prefix-free）コードの固有的デコード可能性の困難性を活用することによってセキュリティを得ている。提案されている暗号化システムは次のステップに従って動作する：入力データ（１）の圧縮（２）ステップと、導入されたＮＰＦエンコーディング（５）を伴うコーディングによって独立的且つ同一的に分布（ＩＩＤ、independent and identically distributed）したデータ（４）を２つのストリームに分割するステップであって、一方はＮＰＦ符号語ストリーム（７）の境界についての全ての情報を有する符号語境界情報（６）データであり、他方は符号語境界情報（６）以外のエンコードされたＩＩＤデータ（４）の全てのペイロードを有するＮＰＦ符号語ストリーム（７）である、分割するステップと、ＮＰＦ符号語ストリームを伴わずにして符号語境界情報（６）を暗号化（８）するステップ。
2019536357.tif 000002
【特許請求の範囲】
【請求項１】
暗号化方法であって、該方法は、
全ての符号化オペレーションの前に入力データ（１）を圧縮（２）するステップを含み、該方法は更に、
圧縮データ（３）についてのＮＰＦ（非プレフィックスフリー）エンコーディング（５）オペレーションを伴うコーディングステップと、
圧縮データ（３）を２つのストリームに分割するステップであって、一方のストリームは符号語境界情報（６）データでありこれはＮＰＦ符号語ストリーム７の境界情報を全て有しており、他方のストリームはＮＰＦ符号語ストリーム（７）でありこれは符号語境界情報（６）以外のエンコードされた圧縮データ（３）の全てのペイロードを有している、分割ステップと、
ＮＰＦ符号語ストリーム（７）を伴わずにして符号語境界情報（６）を暗号化（８）するステップとを含むことによって特徴付けられる、方法。
【請求項２】
暗号化方法であって、該方法は、
入力データを得るステップであって、前記入力データ（１）内でのシンボルの分布は同一的且つ独立的分布（ＩＩＤ、identically and independently distributed）となっているステップを含み、該方法は更に、
入力データ（１）についてのＮＰＦ（非プレフィックスフリー）エンコーディング（５）オペレーションを伴うコーディングステップと、
前記入力データ（１）を２つのストリームに分割するステップであって、一方のストリームは符号語境界情報（６）データでありこれはＮＰＦ符号語ストリーム（７）の境界情報を全て有しており、他方のストリームはＮＰＦ符号語ストリーム（７）でありこれは符号語境界情報（６）以外のエンコードされた入力データ（１）の全てのペイロードを有している、分割ステップと、
ＮＰＦ符号語ストリーム（７）を伴わずにして符号語境界情報（６）を暗号化（８）するステップとを含むことによって特徴付けられる、方法。
【請求項３】
請求項１に記載の提案された方法をもってセキュア化されたデータの復号化であって、
暗号化された符号語境界情報（６）の復号化ステップと、
復号化された符号語境界情報（６）に基づいてなされる符号語ストリーム（７）のＮＰＦ（非プレフィックスフリー）コーディングのデコードステップと、
抽出された圧縮データ（２）を展開することによって元のデータを生成するステップとを含む、復号化。
【請求項４】
請求項２に記載の提案された方法をもってセキュア化されたデータの復号化であって、
暗号化された符号語境界情報（６）の復号化ステップと、
復号化された符号語境界情報（６）に基づいてなされる符号語ストリーム（７）のＮＰＦ（非プレフィックスフリー）コーディングのデコードステップと、
元の入力データ（１）を生成するステップとを含む、復号化。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号化方法に関するのであり、該方法は要求される暗号化オペレーションの回数を減らす。
【０００２】
本発明は暗号化方法に特に関するのであり、可変長非プレフィックスフリー（ＮＰＦ、non-prefix-free）コードの固有的デコード可能性の困難性を活用することによってセキュリティを得ている。
【背景技術】
【０００３】
計算負荷の観点からは、暗号化オペレーションは相当量のＣＰＵ時間を占有する重たい処理であり、故に重量級の電力消費事象である。センサネットワーク、無人飛行体、モバイルビデオ送信等の限定的な処理能力しか持ち合わせないバッテリー制約型演算環境下において、当該負荷を減ずることが特に重要となる。
【０００４】
ビデオ送信のような場面即ちデータ量が膨大である場合、データ全体の暗号化をなしたのでは重い計算負荷がもたらされることになり、また同時に重大な電力消費事象が惹起される。したがって、該負荷を減じるための方法が、相当程度注目の的となっている。データをセキュア化しようとしつつ暗号化オペレーションの量を減じようと目論む幾つかの発展が既知の技術水準にはみられる。これらの研究における主たるアプローチは、データについて選択的（又は部分的）暗号化を行うことである。選択的暗号化では、データの重要情報コンテンツと目される選択された部分が暗号化されるのであり、データの残余の部分は平文フォーマットで送信／格納される。
【０００５】
データのセキュア化における日常的慣行では、先ずデータを圧縮して、そして安全と仮定されている暗号化スキームを用いてそれを暗号化する。この観点においては、圧縮及び暗号化ステップを一緒に行うことも検討されている。しかし、このアプローチでは暗号化オペレーションの回数は削減されておらず、主たる目的は単一のステップで圧縮及び暗号化ステップをなすことであり、それによって経過時間を取り戻すことにすぎない。以下、組み合わされた圧縮及び暗号化ステップについての特許並びに部分的（選択的）暗号化についての特許について、例示する。
【０００６】
例えば、これらの発展の例として挙げることができる特許文献１では、セキュア暗号化アルゴリズムが開示されており、生データに対して単一のオペレーションとして適用でき圧縮及び暗号化されたデータがもたらされる。実施形態では、本明細書中に開示されるアルゴリズムは、任意のタイプの辞書ベースド暗号化を用いて行われ得る。１つの実施形態では、辞書テーブルに新たなプレフィックスを追加した後、辞書テーブルを並べ替えてエントリをランダム化してテーブル内に入れることができる。ランダム化は、決定論的擬似乱数生成器及び／又は擬似乱数関数によって生成された並び替え値に基づいて、なされ得る。ランダム化に関しての他の実施形態を用いてセキュア圧縮を提供してもよい。
【０００７】
既知の技術水準内の特許文献２の発明は、メディアファイルを部分的に暗号化する手法の改良版に関する。暗号化はメディアファイル内の一部のメディアデータのみを暗号学的にセキュアするだけで、メディアデータの残余の部分は暗号学的に保護されない。部分的暗号化が用いられるだけであっても、暗号化される部分によって、メディアファイルの他の部分であってまだ暗号化されていない部分の有用性が相当程度に毀損される。換言するに、部分的暗号化が、不正ユーザによるメディアファイルの利用を実質的に妨害する。
【０００８】
既知の技術水準内の特許文献３の発明は、対称的な暗号学的アルゴリズムに関してスループットを加速させる及び／又は電力消費を削減するための方法及び装置を、開示する。対称暗号化又は対称復号化アルゴリズムの特定の演算が第１段階で行われ、その結果がメモリに格納され、そして結果が検索されて第２段階でデータがエンコードされる。第１段階が電池が充電されている際になされて、第２段階がシステムが電池駆動されている際になされる場合、全段階が専ら電池電力を用いてなされる場合の電池寿命に比して電池寿命が格段に延長される。
【０００９】
既知の技術水準内の特許文献４の発明では、メッセージの特定部分が高強度暗号化処理を施され、他方でメッセージの他の部分はより低い強度の暗号化処理を施されるか或いは暗号化さえされないのであり、差別的に暗号化されたデータセットが結果として得られる。データセットは受信側端へと送信され、そこでは所望されれば復号化され得る。暗号化情報を必要としており且つ許可されたアクセスを有する受信局はこれを復号化でき、他の局はこの情報を部分的に復号化できたり全くできなかったりする。クライアントサイド及びチャンネル処理の双方において要求演算能力が削減される。なぜならば、メッセージの選定部分のみが高強度暗号化処理・復号化処理に服するのであり、レイテンシ及びレイテンシ関連問題は減る。
【００１０】
既知の技術水準内の特許文献５の発明は、データの圧縮及び暗号化に関連する方法及び装置に関するものである。暗号化及び圧縮すべきデータが先ず受信され、そして物理的メモリ内に格納される。物理メモリ内のデータ構造内に格納されたらば、データは処理部へとストリーミングされ、それがデータを圧縮する。そして、圧縮されたデータは物理メモリから暗号化プロセスへとストリーミングされる。そして、圧縮及び暗号化されたデータは送信されることができる。復号化及び展開するためには、圧縮及び暗号化されたデータは、先ず別のデータ構造内へと読み込まれるのであり、それによってデータが物理メモリ内に格納される。そして、データは物理メモリから復号化プロセスへとストリーミングされ、そして展開プロセスへと続く。
【００１１】
選択的（部分的）暗号化に基づいた特許は多数あり、マルチメディアデータ送信・格納を対象とするものが特に該当し、例えば次のものが挙げられる：特許文献６−選択的マルチメディアデータ暗号化（SCM microsystems）、特許文献７−自動化データ記憶ライブラリ内の取り外し可能メディア上に格納されたデータの選択的暗号化（IBM（登録商標））、特許文献８−ビデオ オン デマンド用の選択的暗号化、特許文献９−圧縮ビデオデータに関してのポリシーベースド選択的暗号化（Intel（登録商標））、等々。
【００１２】
従来においては、対称的セキュリティアルゴリズムを用いるとそれらの環境下における通常オペレーションのエネルギー消費が約２倍になると示されており、また、非対称セキュリティアルゴリズムを用いるとビット当たりのエネルギー消費がマグニチュードに関して数オーダーほど増大することが示されている。そのようなプラットフォーム内においてデータセキュリティを提供するということはより重要なことになってくる。なぜならば、急展開するＩｏＴ（モノのインターネット）時代においてそれらは広範に広まっているのであり、プライバシーに対する要望は希望事項ではなく必須事項となるはずであるからである。
【００１３】
上述の文献に類する文献からも理解されるように、上記の異なる方法は、圧縮されたデータに対して適用されるべき暗号化手法を開発するために用いられている。提案される案と選択的（部分的）暗号化との相違は、前者たる提案される発明では全データのセキュリティが提供されるのに対して、後者たる選択的暗号化ではデータの被選択部分のみがセキュア化される点に求められる。提案される手法に関して述べるに、暗号化量の削減はより大きなファイルになるにつれて向上するのであり、そのような場合にはデータを１０％程度暗号化するだけで十分となることになる。選択的暗号化では、データのサイズにかかわらず比率は固定されている。暗号化／圧縮を組み合わせるスキームと比べると、それらのスキームは暗号化オペレーション回数を減らすことを意図はしておらず、総オペレーションの所要時間を減じることを意図しているのであり、本発明の意図とは大して関連してはいない。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】米国特許出願公開第２０１６１２４９８３号明細書
【特許文献２】米国特許出願公開第２００７０８３４６７号明細書
【特許文献３】米国特許出願公開第２００７１１０２２５号明細書
【特許文献４】米国特許出願公開第２００４１９３８７１号明細書
【特許文献５】米国特許出願公開第２００７２６３８７６号明細書
【特許文献６】米国特許出願公開第２００５０１４１７１３号明細書
【特許文献７】米国特許出願公開第２００８００６５９０３号明細書
【特許文献８】米国特許第７０３９９３８号明細書
【特許文献９】米国特許第５８０５７００号明細書
【発明の概要】
【００１５】
本発明の目的は、必要とされる暗号化オペレーションの量を削減するようなデータ暗号化方法を提供することである。
【００１６】
本発明の目的を達成するために提供されるデータ暗号化方法は、符号語境界に関するのであり、これは正しいデコーディングのために絶対的に必要的である。
【００１７】
提案されるデータ暗号化方法では、ランダムに分布する入力データに対してプロセスが適用されるのであり、データ自体が独立的且つ同一的に分布（independent and identically distributed）しているものではないと仮定される場合に、入力データに対して圧縮アルゴリズムを適用することによってそれが得られる。データ自体がランダム分布を反映している場合、圧縮ステップを省略でき、提案された方法を入力データに対して直接的に適用できる。以下においては、圧縮された入力データ又は圧縮なくして既にｉ．ｉ．ｄな入力データをＩＩＤデータと称し、提案されるＮＰＦコーディングスキームをそのようなＩＩＤデータに対して適用する。
【００１８】
提案される発明によれば、最大で９０％減少させた暗号化を用いてＩＩＤデータをセキュア化することが可能となり得る。暗号化量に関してのお得度合いは、パラメータｄに基づいており、これはビット単位でのブロックサイズを指定するのであり、これは圧縮データのサイズに従って選択される。ブロックサイズパラメータたるｄは、n≧d.2dとして選択されるのであり、ここでｎはＩＩＤデータ内のビット数である。したがって、ｎ値が大きければ大きいほどより大きなｄ値を選択しやすくなる。より大きなｄ値を伴うと、符号語境界情報はボリューム的にはより小さくなり、セキュリティのためだけに暗号化がされている故に、暗号化におけるお得度合いは向上していく。
【図面の簡単な説明】
【００１９】
発明の目的を達成するために提供されるデータ暗号化方法は、添付の図面において例示されているのであり、図面においては次のとおりである。
【００２０】
【図１】データ暗号化方法に関しての概略図であって、該図における部分は次のように付番されている：１．  入力データ２．  圧縮３．  圧縮データ４．  ＩＩＤデータ５．  ＮＰＦエンコーディング６．  符号語境界情報７．  符号語ストリーム８．  暗号化９．  暗号化された符号語境界情報１０．  セキュア化されたデータ
【発明を実施するための形態】
【００２１】
提案される手法では、ビット長がｎであるＩＩＤデータ（４）がビット長がｄであるブロック単位で処理されるのであり、長さｄビットの各ブロックがそれに対応する可変長ＮＰＦ（non-prefix-free、非プレフィックスフリー）符号語で代替されるのでありそれは導入された新たなコーディングスキームに従って生成されている。ＩＩＤデータ（４）は、入力データ（１）を圧縮（２）することによって取得される。入力データ（１）が独立的且つ同一的に分布しているものと仮定できる場合、ＩＩＤデータ（４）はそれ自体直接に入力データ（１）とされ、圧縮（２）ステップが省略される。
【００２２】
典型的なブロック長パラメータｄが選択されるのであり、n≧d.2dとされる。ＩＩＤデータ（４）は、導入された方法たる可変長ＮＰＦコーディングスキーム（ＮＰＦ）（５）をもってエンコードされる。ＮＰＦエンコーディング（５）のステップは２つのデータストリームを作成する。第１のストリームは、符号語ストリーム（７）であり、ＩＩＤデータ（４）の固定ビット長ｄの各ブロックがＮＰＦエンコーディング（５）されるのであり、可変ビット長の符号語を伴う。第２のストリームは、符号語境界情報（６）であり、符号語ストリーム（７）内の各符号語の長さを指定するものである。
【００２３】
ＮＰＦ符号語はプレフィックスフリー制約なくして生成されるのであり、符号語はプレフィックスか別のものたり得る。よって、ＮＰＦ符号語ストリーム（７）は曖昧であり、符号語境界情報（６）についての知識なくしてはデコードできない。ＮＰＦエンコーディングにおける符号語境界情報（６）なき場合の固有的なデコード可能性の欠如は、セキュリティに関しては特殊な機会を提供する。したがって、適切なアルゴリズムを伴って符号語境界情報（６）を暗号化（８）することで十分に入力データ（１）にセキュリティをもたらすことができる。
【００２４】
符号語ストリーム（７）はそのままにされる。なぜならば、符号語境界情報（６）なくしてはデコードできないからであり、これは既に暗号化（８）されている。
【００２５】
一般に、システムのセキュリティは、数学的問題を解くに際しての困難性に依存しており、例えば離散的対数や因数分解問題等が想起される。本発明では、符号語境界情報（６）を欠いている場合のデコード困難性を用いているのであり、対象は可変長ＮＰＦコードをもってエンコード（５）されたシーケンスＮＰＦである。文献においては、ＮＰＦ符号やプレフィックス符号についての、暗文を用いてのみの攻撃の困難性が既に検討されている（論文からの引用）。
【００２６】
詳細を検討するに、A＝a1a2 ... anは独立的且つ同一的に分布した（ｉ．ｉ．ｄ、independently and identically distributed）ランダムなビットシーケンスであり、ｄ>１はビットブロック長を示す整数である。一般性を失わない点で論じるに、ｎはｄで割り切れるものと仮定する。なぜならば、そうでないような場合でも、必要な個数のランダム生成ビットをＡにパディングしていくことは常に可能であるからである。
【００２７】
2019536357.tif 000003
【００２８】
定義１．
整数i≧2の最小二進数表現（ＭＢＲ、minimum binary representation）は、一番左の１ビット分をなくした二進数表記である。
例を挙げるに、２１のＭＢＲは、ＭＢＲ（２１）＝０１０１であり、これはその二進数表記
2019536357.tif 000004
の一番左のセットビットをなくしたものである。
【００２９】
定義２．
ｚ＝２ｄについて、
2019536357.tif 000005
はアルファベット
2019536357.tif 000006
のランダムな並び替えであるとして、W = {w1, w2, ,wz }は次のような符号語セットであるとする：
【表１】
2019536357.tif 000007
【００３０】
入力シーケンスとして
2019536357.tif 000008
を仮定する場合であって、全ての1≦i≦rについて0≦bi≦2dであるとする場合、
2019536357.tif 000009
のＮＰＦエンコーディング（４）は
2019536357.tif 000010
として表記されるのであり、各ｂｉによって決定された符号語をつなぎ合わせることによって生成される。
2019536357.tif 000011
の場合のように符号語が複数の複数の選択肢を呈する場合、諸々の可能性の中からランダムな符号語を選択する。
【００３１】
定義１及び定義２によるサンプルシーケンスについてのＮＰＦエンコーディング（４）であって、パラメータｄ＝３とした場合のエンコーディングは、スキーム２に示されている。符号語たるｗ１及びｗ５は各々次の値に対応するセットである：
2019536357.tif 000012
及び
2019536357.tif 000013
。したがって、ｂｉ＝４又はｂｉ＝０の場合、それぞれ集合ｗ５又はｗ１からランダムに選択された符号語が、
2019536357.tif 000014
ストリーム内へと挿入される。一見すると、２つの
2019536357.tif 000015
値についての例外として複数の符号語を用いることは若干奇異にも見える。こうすることの理由は起こり得る統計学的な攻撃を回避することにある。
【００３２】
提案１．
定義２．によるブロック長ｄ＞１について生成された符号語セットＷについて符号語のビット長は{1, 2, ...,d}である。
各
2019536357.tif 000016
についてのビット長
2019536357.tif 000017
の符号語の個数は
2019536357.tif 000018
であり、
2019536357.tif 000019
については２セットの符号語が存在するのであり、それぞれは２ｄ−１個の符号語を含む。
【表２】
2019536357.tif 000020
【００３３】
スキーム２．
入力データ（１）のビットシーケンスについてのＮＰＦエンコーディング（４）についての簡単なスケッチ。
Ａが入力データ（１）であり、
2019536357.tif 000021
はブロック長がｄ＝３であると仮定した場合のＡについての表現であるとする。
2019536357.tif 000022
は対応するアルファベット
2019536357.tif 000023
からランダムに選択された並び替えであり、Ｗは定義２．西多賀って
2019536357.tif 000024
について生成されたＮＰＦ符号語セットである。
【００３４】
証明
定義２．によれば、Ｗ内のエンティティは数たる{2, 3, ... , 2d+1 - 1}についての最小二進数表現である。それらの数のＭＢＲビット長は１からｄの範囲にあるため、Ｗ内には異なるｄ個の符号語長が存在する。各符号語長
2019536357.tif 000025
は
2019536357.tif 000026
個の異なる符号語を定義するのであり、故に、全ての可能な
2019536357.tif 000027
値によって定義される符号語の総数は次のように表される：
【数１】
2019536357.tif 000028
【００３５】
|W|  = 2dのアイテムのうちの残る２つの符号語は、ビット長がｄビットであるビットシーケンスを要する。例えば、ｄ＝３である場合、|W|はビット長が１ビットの符号語を2(= 21)個含み、長さが２である符号語を4(= 22)個含み、ビット長が３ビットの符号語を2(= 23 - 6)個含むのであり、スキーム２の通りである。
【００３６】
補助定理１．
2019536357.tif 000029
が入力シーケンスを表すものと仮定し、1≦i≦r及びｄ＞１についてのビット長がｄビットのｂｉ値が{0, 1, 2, ..., 2d- 1}にわたってＩＩＤである場合、
2019536357.tif 000030
シーケンスをエンコードするＮＰＦ符号語の総ビット長は次のとおりとなる：
【数２】
2019536357.tif 000031
【００３７】
2019536357.tif 000032
【数３】
2019536357.tif 000033
【００３８】
下記の総和を算出するに際して、
【数４】
2019536357.tif 000034
下記の初歩的代数公式を用いるのであり、
【数５】
2019536357.tif 000035
ｐ＝ｄ−１と代入する。
【００３９】
入力シーケンス
2019536357.tif 000036
のビット長は元々ｒ．ｄビットであり、ＮＰＦエンコーディング（５）はその空間を次のように減じる：
【数６】
2019536357.tif 000037
【００４０】
もっとも、ＮＰＦ符号は一意的にデコード可能ではないため、
2019536357.tif 000038
についての符号語境界情報（６）を欠いていては、
2019536357.tif 000039
を元の
2019536357.tif 000040
シーケンスへと逆変換することができない。したがって、適切なデコードをなすには、
2019536357.tif 000041
についての符号語境界情報（６）を表すことが厳密に必要とされる。補助定理２．はこのタスクの達成に関して効率的な方法を提示する。
【００４１】
補助定理２．
2019536357.tif 000042
が入力シーケンスを表すものとし、ｂｉの値は{0, 1, 2, ... , 2d- 1}にわたってｉ．ｉ．ｄ．である。
2019536357.tif 000043
における符号語境界情報（６）を表すのに必要なビット数は次のように表せる：
【数７】
2019536357.tif 000044
【００４２】
2019536357.tif 000045
【数８】
2019536357.tif 000046
そして、同様に、
2019536357.tif 000047
の場合、
【数９】
2019536357.tif 000048
個の長さｄ−２の符号語が現れる。一般化するに、i={1, 2, ... , d - 1}の場合の
2019536357.tif 000049
については、
【数１０】
2019536357.tif 000050
2019536357.tif 000051
【００４３】
例えば、第１レベルビットマップ
2019536357.tif 000052
上では、長さ
2019536357.tif 000053
の符号語の位置が１で指定されており、残りは０で示されている。
2019536357.tif 000054
はｒ個のビットを含み、ゼロと１のビット数は等しい。なぜならば、
【数１１】
2019536357.tif 000055
2019536357.tif 000056
【数１２】
2019536357.tif 000057
【表３】
2019536357.tif 000058
【００４４】
スキーム３．
提案された方法を介してサンプル
2019536357.tif 000059
上で符号語境界情報（５）をマーキングすること。
ビット長が２ビットである符号語は、第１ビットマップたる
2019536357.tif 000060
上で１ビットでマーキングされている。
2019536357.tif 000061
上で０として表されるものの長さは、第２ビットマップ
2019536357.tif 000062
で表されており、ビット長が１ビット及び３ビットの符号語がそれぞれ１及び０のビットで表されている。
【００４５】
スキーム２は提案された方法を示しているのであり、該方法ではスキーム２で導入されたサンプル
2019536357.tif 000063
上で符号語境界情報（６）をマーキングする。当該サンプルではｄ＝３であるため、ｄ−１＝２個のビットマップが存在する。長さが８ビットである第１ビットマップ
2019536357.tif 000064
では、１のビットで表される位置は、対応する符号語のビット長がｄ−１＝２ビットであることを示す。ビット長がｒ／２＝４ビットである第２ビットマップ
2019536357.tif 000065
では、１のビットを有する位置は、ビット長が（ｄ−２）＝１ビットである符号語をマーキングするのであり、０のビットを有する位置はビット長ｄ＝３ビットである符号語を表す。合計するに、
2019536357.tif 000066
個のビットが用いられる。
【００４６】
定理１．
2019536357.tif 000067
を入力シーケンスとし、1≦i≦rについてのｂｉの値が
2019536357.tif 000068
にわたってｉ．ｉ．ｄ．であるとし、ｄビットで表されるものとする。符号語境界情報（５）を伴うシーケンス
2019536357.tif 000069
のＮＰＦエンコーディング（４）の総ビット長は次のとおりである：
【数１３】
2019536357.tif 000070
【００４７】
証明
補助定理１及び２で記述された空間消費の合計がこれを与える。
【数１４】
2019536357.tif 000071
【００４８】
元々はビット長がｒ・ｄビットである入力シーケンス
2019536357.tif 000072
のＮＰＦエンコーディング（５）は、定理１で見られるように次のような余剰なビットを伴うオーバーヘッドをもたらす：
【数１５】
2019536357.tif 000073
2019536357.tif 000074
内のオリジナルビット毎の余計なビット数は次式で算出できる：
【数１６】
2019536357.tif 000075
【表４】
2019536357.tif 000076
【００４９】
テーブル１．
幾つかの選択されたｄ値についての、提案されたＮＰＦエンコーディング（４）によって導入された、オリジナルビット毎のオーバーヘッドたる
2019536357.tif 000077
について。ｄ値が増大するにつれてオーバーヘッドが無視可能になっていくことに留意されたい。
【００５０】
テーブル１は、提案されたＮＰＦエンコーディング（５）によってＩＩＤデータ（４）の各オリジナルビット毎にもたらされる余計なビット数について要約している。次式に関して述べるに、指数関数的に増大する分母たる（２ｄ−１）のお陰で、
【数１７】
2019536357.tif 000078
余剰空間消費が急速に微少なものになるのであり、大きなｄ値に関しては場合によっては無視可能なまでに減る。ｄ＝８の場合、提案されたＮＰＦエンコーディング（５）の方法は１０００ビット当たりでたったの６．８の余剰ビットをもたらす。同様に、ｄ＝１６やｄ＝２０とすると、それぞれ、１００Ｋビット当たりで余剰ビットは３ビット未満及び１００万ビット当たりで余剰ビットは２ビット未満となる。よって、ｄを選ぶに際しては、空間を浪費しないために高い値のｄを選ぶべきであるも、実用的用途では最低ｄ＝８で有用となると思われる。
【図１】
2019536357.tif 000079
【国際調査報告】
2019536357.tif 000080
2019536357.tif 000081
2019536357.tif 000082