(57)【特許請求の範囲】
【請求項１】
使用されるべき所定数の素数に対応している素数パラメータを含んでいる少なくとも１つの圧縮パラメータを選択するステップと、
前記少なくとも１つの圧縮パラメータに基づきデータを１つの圧縮データ・ブロックに圧縮するステップと、
前記少なくとも１つの圧縮パラメータを含むヘッダーを構築するステップと、
前記ヘッダーを圧縮バッファへ転送するステップと、
前記データ・ストリームを前記圧縮バッファへ転送するステップと、
を有することを特徴とするデータ圧縮方法。
【請求項２】
前記ヘッダーを前記圧縮データ・ブロックに添付するステップを更に含む請求項１に記載のデータ圧縮方法。
【請求項３】
前記選択ステップが、ユーザが少なくとも１つの圧縮パラメータを入力するステップを含む請求項１に記載のデータ圧縮方法。
【請求項４】
前記選択ステップが、前記システムに関連する演算処理ユニットが所定状態に基づき少なくとも１つの圧縮パラメータを決定するステップを含む請求項１に記載のデータ圧縮方法。
【請求項５】
前記選択ステップが、
前記データ・ストリームを圧縮するのに使用されるべき所定指数値に対応する限定パラメータを選択するステップと、
各サイクル中に圧縮されるべき最大バイト・セットに対応するサイズ・パラメータを選択するステップと、
を更に含む、請求項１に記載のデータ圧縮方法。
【請求項６】
前記転送ステップに先行して、前記データ・ストリームを前記サイズ・パラメータに従って１つ以上のデータ・ブロックにセグメント化するステップと、
前記１つ以上のデータ・ブロックを前記圧縮バッファへ転送するステップと、
前記圧縮ステップからの結果としての１つ以上の圧縮データ・ブロックを１つの圧縮データ・ストリームにアセンブルするステップと、
を更に含む、請求項５に記載のデータ圧縮方法。
【請求項７】
前記圧縮ステップが、
残りが獲得されるまで或は商が最大素数未満となるまで、前記圧縮バッファの内容を連続的な各素数で繰り返して分割するステップと、
各素数に対して、前記繰り返して分割するステップの最中に各素数を用いて実行される繰り返し数を表示する指数パラメータを生成するステップと、
前記選択された素数パラメータに基づき、残りを獲得すること無しに、前記繰り返して分割するステップを首尾良く実行すべく圧縮バッファの内容を補償するステップと、
前記補償が実行される回数を表示するフォルト・パラメータを生成するステップと、
を更に含む、請求項１に記載のデータ圧縮方法。
【請求項８】
圧縮データに関連するヘッダーから、前記圧縮データを圧縮するのに用いた所定数の素数に対応している素数パラメータを含む少なくとも１つの圧縮パラメータを検索するステップと、
前記少なくとも１つの圧縮パラメータに従って前記データを解凍データ・ブロックに解凍するステップと、
前記圧縮データを分析バッファへ転送するステップと、
を含む、圧縮データ解凍方法。
【請求項９】
前記転送に先行して、前記ヘッダーから検索された前記少なくとも１つの圧縮パラメータに従って、前記圧縮データを１つ以上の圧縮データ・ブロックにセグメント化するステップと、
前記解凍ステップから生ずる１つ以上の解凍データ・ブロックを１つのデータ・ストリームにアセンブルするステップと、
を更に含む、請求項８に記載の圧縮データ解凍方法。
【請求項１０】
前記解凍が、
分析バッファ内に現行記憶されている前記圧縮データ・ブロックに対して生成された前記指数パラメータに対応している指数値に、各素数を立てることによって複数の評価素数を生成するステップと、
前記評価素数の積を計算するステップと、
前記評価素数の前記積を構築バッファ内に記憶するステップと、
フォルト・パラメータと、前記圧縮データ・ブロックに関連する調整アルゴリズムとによって指示される値を、前記評価素数の前記積に加えるステップと、
を更に含む、請求項８に記載の圧縮データ解凍方法。
【請求項１１】
伝送されるべきデータ・ストリームを検索するエンコーダであり、使用されるべき所定数の素数に対応している素数パラメータである所定指数値に対応している限定パラメータ、及び、各サイクル中に圧縮されるべき最大バイト・セットに対するサイズ・パラメータを含んでいる圧縮パラメータを有するヘッダーを構築し、前記データ・ストリームのサイズが前記サイズ・パラメータを超えたことを決定するに及んで、該サイズ・パラメータに従って前記データ・ストリームを所定長の１つ以上のデータ・ブロックにセグメント化し、前記１つ以上のデータ・ブロックを前記圧縮パラメータに従って圧縮して１つ以上の圧縮データ・ブロックを形成し、前記１つ以上の圧縮データ・ブロック各々に対して指数パラメータを生成し、前記１つ以上の圧縮データ・ブロックを１つの圧縮データ・ストリームにアセンブルすべく構成されているエンコーダと、
前記ヘッダー及び前記圧縮データ・ストリームを伝送するデータ伝送装置と、前記ヘッダー及び前記圧縮データ・ストリームを前記データ伝送装置から受信するデータ受信装置と、
前記ヘッダー及び前記圧縮データ・ストリームを前記受信装置から検索するデコーダであり、前記ヘッダーから前記圧縮パラメータを検索し、前記圧縮データ・ストリームを受信された前記圧縮パラメータに従って１つ以上の圧縮データ・ブロックにセグメント化し、前記１つ以上の圧縮データ・ブロックを解凍して、１つ以上の解凍データ・ブロックを獲得し、前記１つ以上の解凍データ・ブロックを前記エンコーダによって検索される前記データ・ストリームに再アセンブルすべく構成されているデコーダと、
を備えることを特徴とする圧縮データ伝送装置。
【請求項１２】
少なくとも２つのステーションであり、各ステーションが、
データ・ストリームを検索するエンコーダであり、使用されるべき所定数の素数に対応している素数パラメータ、所定指数値に対応している限定パラメータ、並びに、各サイクル中に圧縮されるべき最大バイト・セットに対しているサイズ・パラメータを含んでいる、複数の圧縮パラメータを有するヘッダーを構築し、前記前記サイズ・パラメータに従って、前記データ・ストリームを所定長の１つ以上のデータ・ブロックにセグメント化し、前記１つ以上のデータ・ブロックを前記素数パラメータに従って圧縮するように構成されたエンコーダと、
前記ヘッダー及び前記圧縮データ・ブロックを前記少なくとも２つのステーションの内の他の１つへ伝送するデータ伝送装置と、前記少なくとも２つのステーションの内の他の１つから、前記ヘッダー及び前記圧縮データ・ブロックを受信するデータ受信装置と、
前記データ受信装置から前記ヘッダー及び前記圧縮データを検索するデコーダであり、前記ヘッダーから圧縮パラメータを検索し、前記１つ以上の圧縮データ・ブロックの各々を解凍して１つ以上の対応する解凍データ・ブロックを獲得し、前記１つ以上の解凍データ・ブロックを１つのデータ・ストリームに変換するように構成されているデコーダと、
を備えることを特徴とする圧縮データ伝送装置。
【請求項１３】
使用されるべき所定数の素数に対応している素数パラメータ、所定指数値に対応している限定パラメータ、並びに、各サイクル中に圧縮されるべき最大バイト・セットに対応しているサイズ・パラメータを含んでいる複数の圧縮パラメータを有するヘッダーを第１ステーションによって構築するステップと、
前記ヘッダーを第２ステーションへ伝送するステップと、
前記ヘッダーの良好な受信を前記第２ステーションによって受領確認するステップと、
前記第１ステーションで、前記サイズ・パラメータに従ってデータ・ストリームを所定長の１つ以上のデータ・ブロックにセグメント化するステップと、
前記圧縮パラメータに従って前記１つ以上のデータ・ブロックに圧縮して、１つ以上の圧縮データ・ブロックを形成するステップと、
前記１つ以上の圧縮データ・ブロックを前記第２ステーションへ順次伝送するステップと、
前記第２ステーションで、前記ヘッダーから圧縮パラメータを検索するステップと、
前記１つ以上の圧縮データ・ブロックを解凍して１つ以上の解凍データ・ブロックを獲得するステップと、
前記１つ以上の解凍データ・ブロックを１つのデータ・ストリームに変換するステップと、
を有することを特徴とする圧縮データ伝送方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はデータ圧縮及び解凍の技術に関し、より詳細には、素数列を用いてデータを圧縮及び或いは解凍する方法に関する。
【０００２】
【従来の技術】
データの転送及び記憶には増大された帯域幅が必要とされている。しかしながら、リアルタイムでのデータの使用増大は、演算処理エラーによる損失を最少限にして最大限の伝送速度を必要とする。この必要要件はデータ圧縮を含む様々なアプリケーションの増加を誘発した。
【０００３】
数多くの進歩が演算処理速度及びデータ圧縮技術において為されてきている一方で、演算処理速度における改善がデータ圧縮に関連された改善に大いに取って代わってきている。加えて、現行での通信システムでデータを伝送するために利用可能な限定された帯域幅は効果的なデータ圧縮技術を益々当てにしてきている。
【０００４】
現行のデータ圧縮には２つの一般的なカテゴリー、即ち無損失性及び損失性がある。無損失性データ圧縮技術は、何等データ損失無しにデータ冗長性を除去すべく設計されている。反対に、損失性圧縮技術は、冗長データとデータ用途に特定される所定の基準に従って重要でないと判断されたデータとの双方を除去するものである。
【０００５】
無損失性圧縮技術は益々効率的になってきたが、数多くの用途において可能性がある無損失性圧縮の量が限定されている。画像圧縮の場合、２：１或はそれ以下の最大圧縮比が典型的には実現されている。損失性データ圧縮技術は、アナログ信号（例えば、スピーチ或はミュージック）及び画像（静止動画或はビデオ）を表す二次元アレイのリアルタイム列表現を含む各種用途において実質的により大きな圧縮比が可能であり、再構築の際に顕著なエラー無しにデータの一部が廃棄され得る。更なる圧縮の有益性は、再構築位相における検出可能なエラーに対しての許容公差の度合いを特定の用途に依存して変動することによって獲得され得ることである。
【０００６】
無損失性及び損失性の圧縮技術双方に共通な１つの特徴は、利用可能な帯域幅によって据えられる制限である。データの転送に先行して圧縮される殆どの用途において、一般的には帯域幅の関数である伝送時間は制御因子である。ひとたびデータが受信されると、典型的には解凍はデータ圧縮ルーチンの逆を実行する現行の演算処理ユニットの高速性により簡単なタスクである。結果として、大量の時間が、限定された帯域幅にわたってのデータの伝送及び受信に費やされる。それ故に、プロセッサ速度を最大限に活用する一方で最小限の帯域幅を利用するデータ圧縮及び解凍を為すシステムが望ましくなる。
【０００７】
【発明が解決しようとする課題】
従って本発明の主な目的は、現行の演算処理能力を充分に利用する一方で必要とされる帯域幅を最小化するデータ圧縮方法を提供することである。
【０００８】
本発明の他の目的は、プロセッサ速度を最大限に活用する一方で帯域幅を最小化するデータ解凍方法を提供することである。
【０００９】
本発明の更なる目的は、圧縮データを伝送するシステムを提供することである。
【００１０】
本発明の更なる目的は、圧縮データをリアルタイムで伝送する方法を提供することである。
【００１１】
【課題を解決するための手段】
本発明の１つの目的に従えば、本発明のデータを圧縮する方法は、使用されるべき所定数の素数に対応している素数パラメータを含んでいる少なくとも１つの圧縮パラメータを選択するステップと、前記少なくとも１つの圧縮パラメータに基づき前記データを１つの圧縮データ・ブロックに圧縮するステップと、前記圧縮パラメータを含むヘッダーを構築するステップと、前記ヘッダーを圧縮バッファへ転送するステップと、前記データ・ストリームを前記圧縮バッファへ転送するステップと、の各ステップを含む。このように、本発明によるデータ・ストリームの圧縮は、素数列及びそれらの指数を利用して、高圧縮比を伴う無損失データ圧縮を提供しようとするものである。
【００１３】
結果としての圧縮データ・ブロック及びヘッダーは、前記データ・ストリームを再構築するに充分な初期化パラメータを含む。その結果として、データ伝送に必要とされる帯域幅は、演算要件が増大される一方で最小化される。
【００１４】
もし圧縮されるべきデータが前記圧縮バッファ内に保存できなければ、更なる好適特徴としては、前記圧縮パラメータに従って前記データ・ストリームを転送に先行して１つ以上のデータ・ブロックにセグメント化（分割又は分断）するステップと、前記圧縮ステップに引き続いて、それら１つ以上の圧縮データ・ブロックを圧縮データ・ストリームにアセンブルするステップとを含む。
【００１５】
本発明の他の目的に従えば、圧縮データを解凍する方法は、データを圧縮すべく使用された所定数の素数に対応している素数パラメータを有する、圧縮データ・ブロックに関連されたヘッダーから少なくとも１つの圧縮パラメータを検索するステップと、前記データを前記少なくとも１つの圧縮パラメータに従って解凍データ・ブロックに解凍するステップとを含む。好適な特徴に従えば、この方法は、前記解凍データ・ブロックを分析バッファへ転送するステップを更に含む。前記データ圧縮位相中に生成された圧縮パラメータを検索することは、伝送中の帯域幅に重い要件を課すこと無しにオリジナル・データの無損失性再構築を可能とする。もし前記データが、圧縮に先行してセグメント化された圧縮データ・ストリームの形態であれば、本方法はその圧縮データを前記ヘッダーから検索された前記圧縮パラメータに従って１つ以上の圧縮データ・ブロックにセグメント化するステップと、前記解凍ステップで生ずる１つ以上の解凍データ・ブロックを１つのデータ・ストリームにアセンブルするステップとを更に含むことができる。
【００１６】
本発明の他の目的に従えば、圧縮データを伝送するためのシステムは、
伝送されるべきデータ・ストリームを検索するエンコーダであり、
使用されるべき所定数の素数に対応している素数パラメータ（所定指数値に対応している限定パラメータ、及び、各サイクル中に圧縮されるべき複数バイトから成る最大セット（最大バイト・セット）に対するサイズ・パラメータ）を含んでいる、圧縮パラメータを含むヘッダーを構築し、
前記データ・ストリームのサイズが前記サイズ・パラメータを超えたことを決定するに及んで、該サイズ・パラメータに従って前記データ・ストリームを所定長の１つ以上のデータ・ブロックにセグメント化し、
前記１つ以上のデータ・ブロックを前記圧縮パラメータに従って圧縮して１つ以上の圧縮データ・ブロックを形成し、前記１つ以上の圧縮データ・ブロック各々に対して指数パラメータを生成し、前記１つ以上の圧縮データ・ブロックを１つの圧縮データ・ストリームにアセンブルすべく構成されているエンコーダと、前記ヘッダー及び前記圧縮データ・ストリームを伝送するデータ伝送装置と、前記ヘッダー及び前記圧縮データ・ストリームを前記データ伝送装置から受信するデータ受信装置と、前記ヘッダー及び前記圧縮データ・ストリームを前記受信装置から検索するデコーダであり、前記ヘッダーから前記圧縮パラメータを検索し、前記圧縮データ・ストリームを受信された前記圧縮パラメータに従って１つ以上の圧縮データ・ブロックにセグメント化し、前記１つ以上の圧縮データ・ブロックを解凍して、１つ以上の解凍データ・ブロックを獲得し、前記１つ以上の解凍データ・ブロックを前記エンコーダによって検索される前記データ・ストリームに再アセンブルすべく構成されているデコーダと、を備える。
【００１７】
本発明は、添付請求項１４に記載されているような通信システムや、添付請求項１５に記載されているような圧縮データを伝送する方法をも提供する。
【００１８】
本通信システムは、信頼性ある無損失性データ圧縮を提供し、帯域幅を最小化し、現行の演算処理ユニットの長所を活用するものである。このシステムは、回路交換方式、パケット交換方式、有線方式、並びに、無線方式を含む様々な通信ネットワークにわたって使用され得る。更には、このシステムは半導体装置を用いてリアルタイムで使用され得て、圧縮及び解凍のアルゴリズムを実行する。
【００１９】
本発明及びその長所のより完全な理解のために、同様番号が同様パーツを示している添付図面を組み合わせての以下の説明が参照される。
【００２０】
【発明の実施の形態】
本発明は、データ・ストリームに対する圧縮及び解凍の例示的例によって説明される。先ず、本発明を実施できる一般的なコンピュータ・ハードウェアについての説明が為され、次いでデータの圧縮及び解凍のための一般的手続きが追従される。しかしながら明らかとなることは、本発明が種々のデータ伝送及び通信システムにも適用し得ることである。
コンピュータ・ハードウェアの概要
図１を参照すると、本発明の実施例が実施され得るコンピュータ・システム１０が示されている。このコンピュータ・システム１０はバス或は情報通信のための他の通信手段を備える。このコンピュータ・システム１０は、バス１２に接続されて、情報や、プロセッサ１４によって実行される命令を記憶するランダム・メモリ（ＲＡＭ）或は他のダイナミック記憶装置１６（以降、メインメモリと呼称する）を更に備える。メインメモリ１６は、一時的な変数、或は、プロセッサ１４によっての命令の実行中における他の中間情報を記憶するためにも使用され得る。またこのコンピュータ・システム１０は、バス１２に接続されて、プロセッサ１４に対するスタティック情報及び命令を記憶するための読み出し専用メモリ（ＲＯＭ）及び／或は他のスタティック記憶装置１８を備える。データ記憶装置２０はバス１２に接続されて、情報及び命令を記憶する。
【００２１】
磁気ディスク或は光ディスク等のデータ記憶装置とその対応ディスク・ドライブとは、コンピュータ・システム１０に接続可能である。このコンピュータ・システム１０は、バス１２を介して、コンピュータ・ユーザに対して情報を表示するための陰極線管（ＣＲＴ）等のディスプレイ（表示）装置２２に接続可能でもある。英数字及びその他のキーを含んでいる英数字入力装置２４は、典型的には、バス１２に接続されて、プロセッサ１４に対して情報及びコマンド選択を通信している。他のタイプのユーザ入力装置は、方向情報及びコマンド選択をプロセッサ１４へ通信するため且つディスプレイ上のカーソル動作を制御するためのマウス、トラックボール、カーソル方向キー等のカーソル・コントロール２６である。この入力装置は、典型的には、当該装置に平面内での位置を指定させることを可能とする、第１軸（例えばＸ）及び第２軸（例えばＹ）等の２軸における２つの自由度を有する。
【００２２】
代替的には、スタイラス或はペン等の他の入力装置がディスプレイ２２と相互作用すべく使用可能である。コンピュータ・スクリーン上に表示されたオブジェクトは、スタイラス或はペンを用いてその表示されたオブジェクトをタッチすることによって選択され得る。コンピュータはタッチセンシティブスクリーンを実装することによってその選択を検出する。同様に、光ペン及び感光性スクリーンが表示オブジェクトを選択するために用いられ得る。こうして、そうした装置は、マウス或はトラックボールを組み入れているシステムにおけるような「ポイント及びクリック」の代わりに、単一動作としての選択位置及び選択を検出できる。入力装置に基づくスタイラス及びペンは、タッチセンシティブスクリーン及び感光性スクリーンと共に当業界においては周知である。そうしたシステムは英数字入力装置２４等のキーボードを欠如することもあり得て、全てのインタフェースが書込みインストルメント（ペン等）としてのスタイラスを介して提供され、書込まれたテキストが光学的文字認識（ＯＣＲ）技術を用いて解釈される。
【００２３】
本発明は、データを圧縮及び解凍するためにコンピュータ・システム１０を使用することに関連している。一実施例に従えば、データの圧縮及び解凍は、メモリ１６に含まれた命令シーケンスを実行するプロセッサ１４に応じてコンピュータ・システム１０によって行われる。メモリ１６内に含まれる命令シーケンスの実行は、これ以降に説明されるように、プロセッサ１４に様々な計算及びデータ操作を実行させる。代替実施例において、半導体装置或はマイクロチップは本発明を実施するソフトウェア命令の代わりに或はそれと組合わされて使用可能である。こうして本発明は、ハードウェア回路及びソフトウェアの任意の特定組合せに限定されることはない。
【００２４】
図２Ａ乃至Ｅで参照されるように、本発明に従ってデータを圧縮する方法が示されている。ステップＳ１０で、システムの初期化が圧縮アルゴリズムで使用されるべき複数個の素数の内の最大数を選択することに（キー・パラメータ）によって始まる。ステップＳ１２で、複数個の素数の内の指数に対する最大値（指数パラメータ）が選択される。所与のサイクルで圧縮されることになる複数バイトから成る最大セット（最大バイト・セット）のサイズが、ステップ１４で選択される。種々の初期化パラメータ（或は圧縮パラメータ）がユーザによって入力され得るか、或は、所定条件に基づいて自動的に選択され得る。
【００２５】
ひとたび初期化パラメータが選択されたならば、ヘッダーがステップＳ１６で構築される。従って、そのヘッダーはデータを圧縮すると共に適切に解凍すべく使用されることになる３つのパラメータを有益にも含む。初期化（圧縮）パラメータ用に選択された値は、利用可能な演算処理速度に依存してシステム毎に変動し得る。ステップＳ１８で、構築されたヘッダーが伝送される。使用されている通信ネットワークのタイプに依存して、データ圧縮シーケンスの継続に先行して応答が望まれることもある。代替的には、ヘッダーは後で圧縮データとアセンブルされて伝送され得る。
【００２６】
ステップＳ２０で、レシーバ又は受信器がそのヘッダーの受領を確認する。圧縮サイクルがこれで開始される。ステップＳ２２で、図２Ｂに示されるように、圧縮アルゴリズムにおいて使用されることになる複数個の素数を含んでアレイが作成される。本発明に従えば、もし選択された素数パラメータが５であれば、素数アレイは５の長さを有し、そのアレイ内に含まれる各種要素の値は［２，３，５，７，１１］に対応する。
【００２７】
ステップＳ２４で、初期化（圧縮）パラメータは、データ・ストリームを圧縮すべく使用されるコンピュータ或はシステムのメモリへロードされ、カウンタ（Ｉ）の値が０にセットされる。圧縮されるべきデータ・ストリームのサイズに依存して、そのデータ・ストリームをサイズ・パラメータに従って複数のデータ・ブロックにセグメント化する必要性があり得る。これは、そのデータのサイズが、圧縮プロセス中にデータを記憶するために使用される圧縮バッファの限界を超えないことを確保する。ステップＳ２６で、データ・ストリームが受信バッファ内に受信される。データ・ストリーム、代替的には第１のセグメント化されたデータ・ブロックは圧縮バッファへ転送される。ひとたび圧縮バッファが一杯に成ると、データ圧縮サイクルが始まる。ステップＳ２８で、図２Ｃに示されるように、圧縮バッファ内のデータが第１素数によって分割される。この第１素数は前記素数アレイ内の第１要素に対応している。
【００２８】
ステップＳ３０で、分割プロセスの結果が評価される。もし残りが０であれば、分割を実行すべく使用される素数の指数カウントに１が追加される。もし残りが０でなければ、ステップＳ３４でカウンタが１だけ増分（インクリメント）される。ステップＳ３６でカウンタの値が検査される。もしカウンタの値が選択された素数の最大数（キー・パラメータ）の値と同等であれば、フォルト（ＦＡＵＬＴ）値が１つだけ増分されて、カウンタの値が再初期化される。圧縮バッファ内のデータの値が調整アルゴリズムに従って調整される。調整アルゴリズムは初期化に先行して決定される。それには様々な動作があり得る。図には簡単な減分が用いられている。プログラムはステップＳ２８へ戻り、圧縮バッファの内容が素数アレイの第１要素、即ち第１素数で再度分割される。もしカウンタが複数個の素数の内の最大数（キー・パラメータ）として選択された値と同等でなければ、プログラムはステップＳ２８へ戻り、圧縮バッファの内容が素数アレイの次に続く要素、即ち次の素数で分割される。
【００２９】
ステップＳ４０で、分割プロセスの商が評価される。もしその商が最大素数の値に満たなければ、プログラムはステップＳ４６へ進む。もしその商が最大素数の値以上であれば、カウンタの値が評価される。もしカウンタの値が素数パラメータとして選択された値から１を引いたものと同等であれば、フォルト値が増分されて、カウンタは０にリセットされる。またプログラムは調整アルゴリズムを圧縮バッファに適合させもする。プログラムはステップＳ２８へ戻り、分割シーケンスを繰り返す。もしカウンタが複数個の素数の内の最大数（素数パラメータ）と同等でなければ、プログラムはフォルト値を増分すること無しに分割シーケンスを続行する。圧縮バッファの値が、残りが０になる度に、分割プロセスの商で置き換えられる。
【００３０】
ステップＳ４６で、図２Ｄに示されるように、圧縮バッファの値が評価される。もしその値が１と同等であれば、プログラムはステップＳ６４へ移動する。もし圧縮バッファの値が１と同等でなければ、ステップＳ４８で素数アレイにおける各種要素と比較される。こうして、圧縮バッファの値が圧縮アルゴリズム内で用いられている複数個の素数の各々と比較される。もし圧縮バッファの値がそれら素数の何れかと同等であれば、ステップＳ５０で素数の指数カウントに１が追加される。次いでプログラムはステップＳ６４へ仕向けられる。もし圧縮バッファの値が複数個の素数の内の何れとも同等でなければ、ステップＳ５２でカウンタは０にリセットされる。
【００３１】
圧縮バッファの値はステップＳ５４で第１素数で分割される。ステップＳ５６で、その分割の結果が評価される。もし残りが０であれば、ステップＳ５８で分割に用いられた素数の指数カウントに１が追加される。プログラムはステップＳ５４へ戻り、圧縮バッファの内容が同一素数で再度分割される。もし残りが０でなければ、圧縮バッファの内容がステップＳ６０で評価される。もし圧縮バッファの内容が１と同等であれば、プログラムはステップＳ６４へジャンプする。もし圧縮バッファの内容が１と同等でなければ、カウンタは１だけ増分され、ステップＳ６２でプログラムがステップＳ５４へ戻る。分割プロセスは再度繰り返される。
【００３２】
このプロセスは、圧縮バッファの値が１と同等になるまで続行され、プログラムが図２ＥでのステップＳ６４へ進むことが許容される。データ・ブロックの本体はステップＳ６４で圧縮データ・ストリームにアセンブルされて、ステップＳ６６で受信器へ伝送されることによって、圧縮プロセスが完了する。圧縮データ・ストリームは、圧縮サイクル中に決定された各素数に対する指数値とフォルト値を含むアレイの形態である。上述したように、圧縮データ・ストリームはヘッダーをも含み得る。所望に応じて、その圧縮データ・ストリームの受領の確認を受信器から獲得することが可能である。
データ解凍
次に図３Ａ及び３Ｂには、本発明に従ってデータを解凍する方法が示されている。ステップＳ７０で、圧縮パラメータを含むヘッダーが受信ステーションによって受信される。ステップＳ７２で、そのヘッダーの受領確認が伝送ステーションへ伝送し返される。ステップＳ７４で、データ・ストリームの本体長がヘッダーから検索された圧縮パラメータに基づき計算される。これで受信器は、ステップＳ７６で、データ・ブロックの伝送を待機する。
【００３３】
ステップＳ７６で伝送されたデータ・ブロックが、構築バッファ全体に受信されるまで該構築バッファ内に置かれる。ステップＳ７８で、図３Ｂに示されるように、データ・ブロックの内容が解凍のための分析バッファへ移動される。ステップＳ８０で、圧縮位相において決定された指数カウントに対して各素数を先ず立てることによってデータを解凍する。指数評価からの結果的な数は相互に乗算されて、構築バッファ内に記憶される。ステップＳ８２で、フォルト・パラメータの値がその構築バッファの内容に追加される。一般に、調整アルゴリズムはそのフォルト・パラメータ内で指定された回数だけ逆転される。もし調整アルゴリズムが「減分」であれば、フォルト・パラメータはそれで追加可能となる。この時点で、オリジナルのデータ・ストリームは再構築されたことになる。
【００３４】
例えば、ヘッダから検索された素数が［２，３，５］であることを仮定すると、生成された指数カウントは［３，５，２］であり、フォルト・パラメータは３である。解凍データは（２３）＊（３５）＊（５２）＋３或は４８６０３となる。ステップＳ８４で、データはバイナリ（２進法）形態で分析のためにコンピュータ或は適切なシステムへ伝送され得る。もし解凍されるべき追加のブロックがあれば、プログラムはステップＳ７６へ戻って、解凍プロセスを繰り返す。
例示例
図４は、本発明に従ったデータ・ストリームの圧縮中における各種のステップの結果を示す。伝送されるべきデータはステップＳ１００で先ず選択される。そのデータは、ディジタル的に抽出された信号等の、システム内に記憶された２進法或はテキストのファイルに対応する。このステップ中、データは２進数の大きなストリームとして扱われる。データはステップＳ１１０でその等価な１０進値に変換されて圧縮され得る。次に、アルゴリズムで使用されるべき複数個の素数の数（キー・パラメータ）、及び、各素数に対する最大指数（指数パラメータ）がステップＳ１１２で選択される。この例に従って、１バイトがフォルト・パラメータの値を記憶するために割り当てられる。これは実際の場合には充分であり得ず、フォルト・フィールドの長さはヘッダーの定義文中における両端での仮定値である。初期化パラメータは、受信ステーションへ伝送されるヘッダー内に典型的にはコード化（符号化）されることになる値に対応する。加えて、伝送されるべきデータの数値が圧縮バッファの限界以内であると仮定すれば、セグメント化の必要性はない。
【００３５】
プログラムはステップＳ１１４で圧縮アルゴリズムに進み、データを全ての素数で分割する。ステップ１１６での第１サイクルで、第１素数の指数カウントに対する１を生ずる。残りの素数は、残余無しで圧縮バッファ内に含まれるデータの値に分割され得ない。よってフォルト状況が作り出される。ステップＳ１１８で、圧縮バッファ内のデータの値が１だけ減分され、フォルト・パラメータが１だけ増分される。ステップＳ１２０で、圧縮アルゴリズムが再度適用され、データが全ての素数で分割される。
【００３６】
第２サイクルの結果がステップＳ１２２に示されている。第１素数に対して生成された指数値は何等ない。第２素数は４の指数を生成し、第３素数は５の指数を生成し、第４素数は４の指数を生成し、第５素数及び第６素数は３の指数をそれぞれ生成し、第７素数及び第８素数は４の指数をそれぞれ生成し、そして、第９素数は５の指数を生成する。これら指数の値は、全て以下の通りに、初期化ステップでの最大指数に対して選択された値である。圧縮サイクルの結果、伝送されるべき圧縮データは１の形態であり、それは圧縮サイクル中に遭遇するフォルトの数に対応し、９個の数は圧縮サイクルにおいて使用される複数個の素数の各々に対する指数値に対応している。
【００３７】
このデータはステップＳ１２４で２進法形態に変換され、その第１の８ビットがフォルト値に対応しており、続く９組の３ビット値が各素数に対して獲得される指数に対応している。伝送されるべき圧縮データは、ブロックＲに示されるように、長さ３５ビットである。オリジナルのデータ・ストリームが１０３ビットの２進ストリームに変換される。２つの２進データ・ストリームの比較で、２．９４対１の圧縮比となる。受信ステーションによってのデータの解凍は以下の数学的表現を用いて達成される。
【００３８】
（２０）＊（３４）＊（５５）＊（７４）＊（１１３）＊（１３３）＊（１７４）＊（１９４）＊（２３５）＋１
次に図５には、圧縮データを伝送するためのシステムが示されている。このシステムは第１ステーション３０及び第２ステーション４０を含む。各ステーション３０，４０は、エンコーダ、データ伝送装置、データ受信装置、並びに、デコーダを含む。エンコーダ及びデコーダは、トランスミッタ（送信器）及びレシーバ（受信器）等のデータ伝送及び受信用の規格ハードウェア或は通信装置の形態か、或は、プログラム命令のシーケンスを実行してプロセッサに必要とされる伝送及び受信操作を行わせるディジタル・コンピュータの形態であってよい。
【００３９】
エンコーダは、圧縮サイクル用に使用されるべき圧縮パラメータを含むヘッダーを構築すべく構成されている。よってヘッダーは、圧縮ルーチンで使用される複数個の素数の数に対応しているキー・パラメータ、指数に対する最大値に対応している限定パラメータ、各サイクルで圧縮されるべき最大バイト・セットに対応しているサイズ・パラメータ、並びに、圧縮ルーチンの失敗の回数に対応しているフォルト・パラメータを含む。エンコーダは、もし必要であれば、データ・ストリームをサイズ・パラメータの値に従って１つ以上のデータ・ブロックにセグメント化するように構成されてもいる。
【００４０】
エンコーダは、データの値を記憶する圧縮バッファを含む。圧縮バッファはランダム・アクセス・メモリ（ＲＡＭ）、磁気記憶媒体等々の形態であることが可能である。エンコーダは、圧縮バッファの値を複数個の素数で連続的に分割することによってデータ・ブロックを圧縮し、その結果としてそれら素数各々に関連された指数パラメータを生成する。もし多数のデータ・ブロックが用いられたならば、エンコーダはそれらデータ・ブロックを再アセンブルして、単一の圧縮データ・ストリームを形成する。更にエンコーダは２進法形態から１０進法形態への或はその逆での適切なデータ変換に供する。次いでデータ・ストリームは、伝送装置から受信装置へ通信リンクにわたって伝送される。データ伝送装置は、コンピュータ・システムに接続されて、従来通りの電話線３６、衛星伝送３８等々にわたって動作するトランスミッタ３２、マイクロウェーブ・アンテナ３４、モデム（不図示）の形態であってよい。従って、データ伝送は無線方式、光学方式、物理的方式等々が可能である。
【００４１】
ひとたびデータが第２ステーション４０の受信装置によって受信されたならば、デコーダがそのヘッダー及び圧縮データ・ストリームを検索する。圧縮パラメータはヘッダーからデコード（復号化）されて、解凍サイクルが始まる。デコーダは圧縮データ・ストリームをサイズ・パラメータから検索された情報に基づき１つ以上の圧縮データ・ブロックにセグメント化する。デコーダは構築バッファ及び分析バッファを含み、それらがデータ解凍に使用される。圧縮バッファの場合のように、構築バッファ及び分析バッファはＲＡＭ、磁気媒体等々の形態であることが可能である。
【００４２】
各圧縮データ・ブロックは分析バッファ内に移動されて各素数を圧縮サイクル中に獲得された指数値に立てて、その積を取ることによって解凍させられる。このプロセスの結果は複数の解凍データ・ブロックである。次いでデコーダはそれら解凍データ・ブロックを何等損失無しにオリジナルのデータ・ストリームに再アセンブルする。
【００４３】
図５に示されるシステムは、パケット及び回路交換ネットワークを含む様々な通信ネットワークにわたって動作に適合させられている。加えて、このシステムは相互作用的なデータ転送及び通信のためにリアルタイムで使用され得る。そうした構成において、第１及び第２ステーションは再度使用される。各ステーションはエンコーダ、データ伝送装置、データ受信装置、並びに、デコーダを含む。第１ステーションは第２ステーションへ伝送される第１ヘッダーを構築する。第２ステーションのデコーダは第１ヘッダーから圧縮パラメータを検索して第１ステーションに対して受領確認を送出する。受領確認は、もし双方向通信が望ましければ、第２ステーションによって生成された圧縮パラメータを含む第２ヘッダーをも含む。ひとたび受領確認が受信されると、第１ステーションはデータ・ブロックを圧縮して第２ステーションへ伝送することを開始する。第１ステーションは第２ステーションから受信されたデータ・ブロックを受信して解凍することもできる。同様に、第２ステーションは第１ステーションからのデータ・ブロックを受信し解凍して、それらデータ・ブロックを圧縮して第１ステーションへ伝送する。通信システムでのリアルタイムの動作は完全であるか或は半二重であり得る。
【００４４】
この同一技術は、伝送媒体がバス、例えばＣＰＵ及びディスク間のバスであって、該ディスク内の記憶スペースは低減され得るような場合に用いられる。
【００４５】
本発明の数多くの特徴及び長所は詳述された明細書から明らかであり、よって、添付請求項が、本発明の真の精神及び範囲内に入る本発明の全てのそうした特徴及び長所を包含すべく企図されている。更に、数多くの変更及び変形が当業者には容易に思い付くことであろうことから、本発明を図示され且つ説明された正確な構成及び動作に限定することは望ましくなく、そしてそれ故に、全ての適切な変更及び等価物が頼られるものは本発明の範囲内に入る。
【図面の簡単な説明】
【図１】図１は、本発明を実施すべく使用され得るコンピュータ・システムを示すブロック図である。
【図２】図２は、本発明に従ってデータを圧縮する詳細なコンピュータ・プロセスを示すフローチャートである。
【図３】図３は、本発明に従ってデータを解凍する詳細なコンピュータ・プロセスを示すフローチャートである。
【図４】図４は本発明に従ってのデータ圧縮及び解凍の際における種々のステップの結果を示すブロック図である。
【図５】図５は、本発明に従って圧縮データを伝送するシステムを示すブロック図である。
【図１】
0004812146.tif 000002
【図２】
0004812146.tif 000003
【図３】
0004812146.tif 000004
【図４】
0004812146.tif 000005
【図５】
0004812146.tif 000006