図面 (/)

技術 データ通信方法及びデータ通信装置

出願人 ルーセントテクノロジーズインコーポレーテッド
発明者 ショーンマシューショーンクインラン
出願日 2001年3月16日 (20年2ヶ月経過) 出願番号 2001-076121
公開日 2001年10月26日 (19年7ヶ月経過) 公開番号 2001-298369
状態 特許登録済
技術分野 TV信号の圧縮,符号化方式 TV信号の圧縮,符号化方式 圧縮、伸長・符号変換及びデコーダ
主要キーワード 仮コード データ処理要件 繰り返しシーケンス 符号化入力データ 伝送利得 ストリングテーブル 圧縮テスト 置換符号
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2001年10月26日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (6)

課題

パケット喪失による悪影響の拡大を有さず、頑強性を増し圧縮比率を増加させるような圧縮技術と装置を提供すること。

解決手段

本発明の態様によれば、所謂、受領確認ベクトル(acknowledgement vector)の関数として決定された選択披瀝状態(select history state)が採用される。この受領確認ベクトルは通信チャネルを介し従来の転送の際、成功裏受領したパケットの識別子に関する情報を含む。通信チャネルの送信器側には、受信器が成功裏に受信したパケットに関連するある種の情報が与えられる。脱圧縮器には選択履歴が与えられ、これにより送信器側から送信された圧縮パケットを効率的に脱圧縮する(戻す)。即ち脱圧縮は、このようなパケットを圧縮する間の履歴、すなわち選択履歴状態として用いられたパケットに基づいて行われる。

概要

背景

従来のデータ圧縮技術とそのシステムは、デジタルデータのストリームをこの圧縮符号ストリームに符号化して、この圧縮符号ストリームを対応する元のデータストリーム復号化(脱圧縮)している。この符号ストリームは、「圧縮された」と称するが、その理由は通常ストリームは元のデータストリーム内に含まれるシンボルよりも少ない数の符号から成り立っているからである。このような符号の数が少なくなることにより、データをより少量のメモリ内に記憶することが出来る。更に圧縮された符号ストリームは、通信システム内で、例えば有線通信システム無線通信システム、或いは光ファイバ通信システム内で圧縮されない状態の元のデータよりもより短時間で送信することが出来る。今日の通信ネットワークにおいてデータ伝送と記憶容量の向上に対する需要は常に高まっている。斯くして、データ圧縮は、現代伝送プロトコル及び通信ネットワークにおいて重要な役目を果たす。

従来公知のように、データを圧縮するのには2種類の方法があり、所謂特殊目的圧縮と汎用目的圧縮である。特殊目的の圧縮技術は、特殊な形式のデータを圧縮し実現するのは比較的安上がりである。例えば、特殊目的の圧縮技術はランレングス符号化、0−抑制符号化、ヌル圧縮符号化パターン置換符号化を含む。これらの技術は圧縮比率が低いが、通常の特性及び冗長性を有するデータを圧縮するからである。圧縮比率は、圧縮された符号の長さ対元のデータの長さの比である。しかし、特殊目的の圧縮技術は、より一般的な特性を有するデータ(即ち、共通の特性を高いレベル所有することのないデータ)を圧縮するのには効率的でなくなる傾向がある。

これに対し汎用目的の圧縮技術は、あるタイプのデータを特別に圧縮するよう設計されたものではなく、種々雑多なタイプのデータを圧縮するのに適している。最も広く知られ有効な汎用目的の圧縮技術は、J.ZivとA.Lempelの開発したアルゴリズム群から得られたものである。これを通常「ランペルジブ(Lempel−Ziv)符号化」と称する。特にZiv et al.著の「“A Universal Algorithm for Sequential Data CompressionM”,IEEE Transactions on InformationTheory,IT−23(3):337−343,May 19977(describing the comonly denominated“LZl”algorithm)」(通常LZ1アルゴリズムと称する)とZiv et al.著の「“Compression of Individual Sequences Via Variable−Rate Coding”,“IEEE Transactions on Information Technology,IT−24(5):530−536,September 1978(describing the commonly denominated“LZ2”algorithm)」(LZ2アルゴリズムと称する)を参照のこと。LZ1とLZ2のデータ圧縮技術は、従来公知であるのでその詳細な説明は割愛する。

しかし簡単に説明すると、LZ1(LZ77とも称する)データ圧縮プロセスは、前に現れたシーケンス(即ち、マッチングシーケンス)を参照して文字繰り返しシーケンス置換するという原理に基づいている。基準(reference;例えばポインター)は、以前に発生した位置の表示(繰り返しシーケンスの開始点からオフセット(ずれた)されたバイトと繰り返されるキャラクターの長さ、すなわちマッチした長さ)で表される。通常基準は、従来のLZ1符号化によれば、<offset length>ペアとして表される。これに対しLZ2(LZ78とも称する)の圧縮は、入力データキャラクターのストリームを、自動的に成長するルックアップテーブル、あるいは圧縮プロセスの間生成される字引に基づいて符号化値解析している。すなわちLZ2は、任意のバイト境界及びLZ1符号化内の長さでもってマッチングを見いだすことはなく、字引のワードソースストリングにマッチングしたときには、新たなワードが字引に追加される。そしてこの字引は後続のソースストリングバイトとマッチングしたワードを加えたものから成り立っている。LZ2符号化によれば、マッチングはポインターとして、あるいは字引内のワードに対するインデックスとして符号化される。

前述したようにLZ1アルゴリズムとLZ2アルゴリズムにより具体化された基本原理に基づいて派生した沢山の圧縮系が存在する。例えば、TerryA.Welch(T.A.Welch,“A.Technique for High Performance Data Compression”,IEEE Computer,pp.8-19,June 1984,and U.S.Patent No.4,558,302,issued to welch on December 10,1985,each of which is incorporated by reference for all purposes)は、LZ2符号化プロセスを公知のLempel-Ziv-Welch(LZW)圧縮プロセスとしてまとめ上げた。LZ2圧縮技術とLZW圧縮技術の両方は、入力キャラクターのストリング固定長さの符号にマッピングするような、いわゆるストリングテーブルの生成及び使用に基づいている。具体的に説明すると、これらの圧縮技術は、データキャラクターのストリームを圧縮ストリームに圧縮するために、キャラクターストリームを直列的サーチし、テーブル内、すなわち字引内に以前に記憶された対応する最長の可能性のあるストリングにマッチするたシンボルのシーケンスに基づいて符号を生成することによりデータキャラクターのストリームを圧縮している。マッチングが行われ符号シンボルが生成されると、この圧縮プロセスはデータストリーム内のマッチングしたシーケンスとデータストリーム内の次のキャラクターシンボル遭遇を加えたものを含む字引内の新たなストリングエントリーを記憶する。

前述したようにLempel-Ziv符号化の本質は、元のデータストリーム内、例えば送信すべきドキュメント内で繰り返されるストリングとサブストリングを見いだすことである。圧縮された状態のドキュメント中に繰り返されるフレーズは、ポインターでもってそれらが元のデータストリーム、例えばドキュメント中に以前に発生した場所に置換される。斯くして復号化データ、例えばこのようにして圧縮されたテキストは、ポインターが指摘した、すでに復号化されたテキストでもってポインターを置換することが必要となる。従来公知のようにLempel-Ziv符号化技術を採用する際に考慮すべき重要な点は、ポインターがどこまで後ろにさかのぼるかに対する制限を設定すべきか否かを決定すること、及びこの制限はどんなものであるかを決定することである。Lempel-Ziv符号化でさらに設計的に考慮すべき事項は、所望の制限内にどのサブストリングがポインターの目標となり得るかである。即ち、ポインターが前のテキストに到達することが制限されていない場合、所謂、ウィンドウを成長させるか、あるいは前のN個のキャラクターから成る固定サイズのウィンドウに制限されるかである。ここでNは数千キャラクター、例えば3キロバイトの範囲内にある。この符号化によれば、ストリングの繰り返しが発見されると、それらの両方がウィンドウ内に現れる場合にのみ圧縮される。Lempel-Ziv符号化設計に関し、なされた考慮すべき事項は、速度とメモリーの大きさとその圧縮比率の間の妥協点を見いだすことである。

圧縮はネットワークの効率を改善するためには考慮すべき点である。例えば、利用可能な計算資源、即ちデータ処理要件が利用可能なネットワークの帯域幅に比較して大きい場合には、ネットワークにデータパケット伝送する前にデータパケットを圧縮するのが好ましい。当然のことながら実際に採用する圧縮系は速度と全体的な圧縮効率の関係から注意深く選択しなければならない。即ち、遅い圧縮系は、ネットワークの性能を低下させ、非効率な圧縮系は潜在的な伝送利得を制限してしまう。

さらに複雑なネットワーク効率の問題は、多くのパケットネットワークが本来的に信頼性を有しないということである。即ち、現在知られているパケットネットワーク、例えばインターネットは、ネットワーク内を伝送されるパケット日常的にドロップしたり、あるいは再度順序付けているが、これによりデータ伝送にエラーが発生する。例えば、ある圧縮系がパケット間のある種の相互依存性を導入し、そしてその後ネットワークがこのパケットをドロップしたり、再度要求するような場合そして受信器で前のパケットが失われている場合には、パケット間の相互依存性により、特定のパケットを脱圧縮することはできない(元に戻すことはできない)。斯くして、ある種のアプローチがこのような問題を解決するために採用されている。(1)ネットワークの信頼性の改善。これによりインターネットにおいては、より信頼性のある端末間のトランスポート層サービス、例えば公知のトランスミッション制御プロトコル(Transmission Control Protocol; TCP)が適用されてトランスポートレベルでパケットを圧縮する。(2)無状態(ステイトレス)圧縮を採用する。これは、各パケットは独立に圧縮され、これにより各パケットが受信器で脱圧縮される。(3)ストリーミング(Streaming)圧縮は信頼性が広く行き渡っていることを仮定し、この仮定が破られた時にはリセットメカニズムを採用する。具体的に説明すると、パケットが失われたときには受信器は圧縮がリセットされるまで後続の各パケットを廃棄する。リセットの後はそれ以降のパケットは前のパケットには依存せず、脱圧縮は通常の形態で再開される。これら2つの公知のストリーミングタイプの圧縮技術は、Point−to−Point Protocol(PPP)圧縮制御プロトコルとUse Datagram Protocol(UDP)パケットに対し採用されるIPヘッダー圧縮プロトコルを有する。

上に説明したパケット圧縮系は、パケットの相互依存性から発生する問題を解決するのには有効であるが、このような圧縮系はまた別の問題を発生させる。例えば、トランスポートレベルでのパケットの圧縮は端末間の利用を必要とし、通常、伝送中にアプリケーションによるあるレベルの共同作業を必要とする。同様にステイトレスの圧縮は、ある種の頑強さを提供するが、ステイトレスの圧縮のパケットの独立性の特性により、実際の圧縮比率が下がるが、これはこのような圧縮が1個のパケット内のデータを検査するからである。斯くして、例えば、この圧縮アプローチは隣接するパケットのネットワークヘッダー内に通常見いだされる大量の冗長性を除去することができない。さらにまた、ストリーミング圧縮はより大きな圧縮技術を与えることができるが、これらの圧縮系はパケットがネットワーク内で喪失した場合には、パケットの喪失の影響を大幅に増やし、これにより受信器が他の数個のパケットを受領できないことになる。信頼性が低いネットワーク、例えばインターネットにおいてはこのパケットの大きな影響は、ストリーミング圧縮を採用する利便性を低下させることになる。

概要

パケットの喪失による悪影響の拡大を有さず、頑強性を増し、圧縮比率を増加させるような圧縮技術と装置を提供すること。

本発明の態様によれば、所謂、受領確認ベクトル(acknowledgement vector)の関数として決定された選択披瀝状態(select history state)が採用される。この受領確認ベクトルは通信チャネルを介し従来の転送の際、成功裏に受領したパケットの識別子に関する情報を含む。通信チャネルの送信器側には、受信器が成功裏に受信したパケットに関連するある種の情報が与えられる。脱圧縮器には選択履歴が与えられ、これにより送信器側から送信された圧縮パケットを効率的に脱圧縮する(戻す)。即ち脱圧縮は、このようなパケットを圧縮する間の履歴、すなわち選択履歴状態として用いられたパケットに基づいて行われる。

目的

本発明の目的は、従来の圧縮系の欠点を有さず、頑強性を増し、圧縮比率を増加させるような圧縮技術を提供することである。本発明の目的は、従来の圧縮系の欠点、例えばパケットの喪失による悪影響の拡大を有さず、頑強性を増し、圧縮比率を増加させるような圧縮方法と装置を提供することである。

効果

実績

技術文献被引用数
0件
牽制数
1件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

(A) データの入力ストリームを複数のパケットに分割するステップと、(B) 前記複数のパケットの内の特定のパケットに対し、それぞれのパケットヒストリー状態を少なくとも1つの受領確認ベクトル関数として特定するステップと、(C) 前記複数のパケットの内の特定のパケットを、関連するパケットヒストリーの関数として符号化するステップと、(D) 前記複数のパケットを圧縮データストリーム圧縮するステップとから成ることを特徴とするデータ通信方法

請求項2

前記パケットに関連するそれぞれのパケットヒストリー状態を複数の受信したパケットの関数として特定することを特徴とする請求項1記載の方法。

請求項3

前記複数の受信したパケットは、受信器伝送エラーなしで以前に受信したパケットを表すことを特徴とする請求項2記載の方法。

請求項4

各パケットは、それぞれパケットヘッダーを有し、前記パケットヘッダーは、前記パケットのそれぞれのパケットヒストリー状態を特定する少なくとも1つのヒストリーベクトルを含むことを特徴とする請求項2記載の方法。

請求項5

前記受領確認ベクトルは、受信器により生成されることを特徴とする請求項3記載の方法。

請求項6

前記受領確認ベクトルは、最後に受領した特定の受領パケットシーケンス番号を含むことを特徴とする請求項3記載の方法。

請求項7

前記パケットヘッダーは、特定の受領パケットを特定するシーケンス番号を含むことを特徴とする請求項4記載の方法。

請求項8

通信チャネルを介して送信側と受信側との間で通信ストリームを送信する方法において、(A) 通信ストリームを複数のパケットに分割するステップと、(B) 前記パケットの特定のパケットに対するそれぞれのパケットヒストリー状態を第1の受領確認ベクトルの関数として特定するステップと、前記第1受領確認ベクトルは、受信側から送られて送信側が受領し、(C) 前記パケットの内、特定のパケットはそれに関連するそれぞれのパケットヒストリーの関数として符号化するステップと、前記各パケットは、それに関連するパケットヘッダーを有し、前記パケットヘッダーは、パケットのそれぞれのパケットヒストリー状態を特定する少なくともヒストリーベクトルを含み、(D) 複数のパケットを圧縮データストリームに圧縮するステップと、(E) 通信チャネルを介してこの圧縮データストリームを送信側から受信側に送信するステップとからなることを特徴とする通信ストリームの送信方法

請求項9

前記パケットに関連するそれぞれのパケットヒストリー状態は、受信器側が受信した複数のパケットの関数として特定されることを特徴とする請求項8記載の方法。

請求項10

前記第1受領確認ベクトルは、受信側が最後に受信した特定の受領パケットのシーケンス番号を含むことを特徴とする請求項9記載の方法。

請求項11

ランペルジブ符号化をパケットを圧縮するステップで用いることを特徴とする請求項9記載の方法。

請求項12

(F) 受信側で圧縮データストリームを受領するステップと、(G)パケットの内の特定のパケットに関連するそれぞれのパケットヒストリー状態を抽出するステップと、(H) 複数のパケットを再生するために、前記圧縮データストリームを脱圧縮するステップと、を更に有し、前記符号化されたパケットの内の特定のパケットは、それに関連して抽出されたパケットヒストリーの関数として脱圧縮されることを特徴とする請求項8記載の方法。

請求項13

(I) 前記受領したパケット状態を脱圧縮したパケットの関数として更新するステップを更に有することを特徴とする請求項12記載の方法。

請求項14

(J)受領側が脱圧縮されたパケットの受領を確認する第2受領確認ベクトルを構成するステップと、(K) 受信側から送信側に前記第2受領確認ベクトルを送信するステップとを更に有することを特徴とする請求項13記載の方法。

請求項15

圧縮されたデータストリームからデータを再生する方法において、(A) 圧縮されたデータストリームを受領するステップと、前記圧縮されたデータストリームは、複数の符号化パケットを含み、(B) 符号化パケットの内の特定のパケットに関連するそれぞれのパケットヒストリー状態を特定するステップと、(C) データを再生するために前記圧縮されたデータストリームを脱圧縮するステップと、を有し、前記符号化パケットの内の特定のパケットは、前記それぞれのパケットヒストリーの関数で脱圧縮されることを特徴とする圧縮されたデータストリームからデータを再生する方法。

請求項16

(D) 前記受領したパケット状態を脱圧縮したパケットの関数として更新するステップことを特徴とする請求項15記載の方法。

請求項17

(E)受領確認ベクトルを構成するステップと、(F)受信器側から送信器側に前記受領確認ベクトルを送信するステップと、を更に有し、前記受信器と送信器は、少なくとも1つの通信チャネルを介して圧縮データストリームを交換することを特徴とする請求項16記載の方法。

請求項18

送信用に、複数のパケットを有するデータストリームを受領する受信器と、前記パケットに関連する複数のパケットヒストリー状態を、少なくとも1つの受領確認ベクトルの関数として特定し、前記複数のパケットを複数のヒストリー状態の関数として符号化する符号化器と、前記パケットを圧縮データストリームに圧縮する圧縮器とから成ることを特徴とするデータ通信装置

請求項19

前記圧縮されたデータストリームを通信チャネルを介して送信する送信器を更に有することを特徴とする請求項18記載の通信装置

請求項20

通信チャネルは、インターネットの一部であることを特徴とする請求項19記載の通信装置。

請求項21

脱圧縮器を更に有し、前記脱圧縮器は、複数の圧縮パケットを有する入力データストリームを受領し、前記圧縮されたパケットの特定のパケットに関連するそれぞれのヒストリー状態を特定し、前記複数の圧縮されたパケットを脱圧縮し、前記圧縮されたパケットの内の特定のパケットは、それぞれのパケットヒストリーの関数として脱圧縮されることを特徴とする請求項18記載の通信装置。

請求項22

前記脱圧縮器は、データ通信装置から送信された少なくとも1つの受領確認ベクトルを構成することを特徴とする請求項21記載の通信装置。

請求項23

前記受領確認ベクトルは、データ通信装置により脱圧縮されたパケットの受領を確認することを特徴とする請求項22記載の通信装置。

請求項24

前記圧縮器は、レンペル−ジブ符号化を用いて前記パケットを圧縮データストリームに圧縮することを特徴とする請求項18記載の通信装置。

請求項25

通信チャネルから圧縮されたデジタル信号を受領する受信器と、前記受信した圧縮デジタル信号を脱圧縮し、この脱圧縮されたデジタル信号からデジタルデータの入力ストリームを再生する脱圧縮器とを有する圧縮されたデジタル信号を処理する装置において、前記圧縮されたデジタル信号は、(A) データの入力ストリームを複数のパケットに分割するステップと、(B) 複数のパケットの内の特定のパケットに対し、それぞれのパケットヒストリー状態を少なくとも1つの受領確認ベクトルの関数として特定するステップと、(C) 前記複数のパケットの内の特定のパケットをそれに関連するパケットヒストリーの関数として符号化するステップと、(D) 前記複数のパケットを圧縮データストリームに圧縮するステップと、(E) 前記圧縮されたデジタル信号を通信チャネルに入力するステップと により処理され、各パケットは、それぞれパケットヘッダーを有し、前記パケットヘッダーは、前記パケットのそれぞれのパケットヒストリー状態を特定する少なくともヒストリーベクトルを含むことを特徴とする圧縮されたデジタル信号を処理する装置。

請求項26

前記パケットの内の特定のパケットは、圧縮されたデジタル信号からそれぞれのパケットのヒストリーの関数として脱圧縮されることを特徴とする請求項25記載の装置。

請求項27

前記脱圧縮器は、受領確認ベクトルを形成し、前記受領確認ベクトルを受信器から送信器に送信し、前記受信器と送信器は、圧縮されたデジタル信号を通信チャネルを介して交換することを特徴とする請求項26記載の装置。

請求項28

前記パケットを圧縮する操作は、レンペル−ジブ符号化を用いることを特徴とする請求項27記載の装置。

請求項29

前記脱圧縮器は、脱圧縮された関連パケットのヒストリー状態を更新することを特徴とする請求項27記載の装置。

請求項30

複数のインストラクションを記憶する記憶媒体において、前記複数のインストラクションは、機械により実行されたときには、送信側と受信側との間で通信チャネルを介して、以下のステップ(A)通信ストリームを複数のパケットに分割するステップと、(B) 前記パケットの特定のパケットに対するそれぞれのパケットヒストリー状態を第1の受領確認ベクトルの関数として特定するステップと、前記第1受領確認ベクトルは、受信側から送られて送信側が受領する(C) 前記パケットの内、特定のパケットはそれに関連するそれぞれのパケットヒストリーの関数として符号化し、前記各パケットは、それに関連するパケットヘッダーを有し、前記パケットヘッダーはパケットのそれぞれのパケットヒストリー状態を特定する少なくともヒストリーベクトルを含み、(D) 複数のパケットを圧縮データストリームに圧縮するステップと、(E) 通信チャネルを介してこの圧縮データストリームを送信側から受信側に送信するステップとを実行することを特徴とする複数のインストラクションを記憶する記憶媒体。

請求項31

前記パケットに関連するそれぞれのパケットヒストリー状態は、受信器側が受信した複数のパケットの関数として特定されることを特徴とする請求項30記載の記憶媒体。

請求項32

前記インストラクションは更に、(F) 受信側で圧縮データストリームを受領するステップと、(G)パケットの内の特定のパケットに関連するそれぞれのパケットヒストリー状態を抽出するステップと、(H) 複数のパケットを再生するために前記圧縮データストリームを脱圧縮するステップと、を含み前記符号化されたパケットの内の特定のパケットは、それに関連して抽出されたパケットヒストリーの関数として脱圧縮されことを特徴とする請求項31記載の記憶媒体。

請求項33

前記インストラクションは更に、(J) 第2受領確認ベクトルを構成するステップと、前記第2受領確認ベクトルは、受信が受領側の脱圧縮されたパケットの受領を確認し、(K) 受信側から送信側に前記第2受領確認ベクトルを送信するステップとを更に有することを特徴とする請求項31記載の記憶媒体。

技術分野

0001

本発明は、データ圧縮に関し、特にパケットネットワーク内で行われるデータ圧縮を改善する方法に関する。

背景技術

0002

従来のデータ圧縮技術とそのシステムは、デジタルデータのストリームをこの圧縮符号ストリームに符号化して、この圧縮符号ストリームを対応する元のデータストリーム復号化(脱圧縮)している。この符号ストリームは、「圧縮された」と称するが、その理由は通常ストリームは元のデータストリーム内に含まれるシンボルよりも少ない数の符号から成り立っているからである。このような符号の数が少なくなることにより、データをより少量のメモリ内に記憶することが出来る。更に圧縮された符号ストリームは、通信システム内で、例えば有線通信システム無線通信システム、或いは光ファイバ通信システム内で圧縮されない状態の元のデータよりもより短時間で送信することが出来る。今日の通信ネットワークにおいてデータ伝送と記憶容量の向上に対する需要は常に高まっている。斯くして、データ圧縮は、現代伝送プロトコル及び通信ネットワークにおいて重要な役目を果たす。

0003

従来公知のように、データを圧縮するのには2種類の方法があり、所謂特殊目的圧縮と汎用目的圧縮である。特殊目的の圧縮技術は、特殊な形式のデータを圧縮し実現するのは比較的安上がりである。例えば、特殊目的の圧縮技術はランレングス符号化、0−抑制符号化、ヌル圧縮符号化パターン置換符号化を含む。これらの技術は圧縮比率が低いが、通常の特性及び冗長性を有するデータを圧縮するからである。圧縮比率は、圧縮された符号の長さ対元のデータの長さの比である。しかし、特殊目的の圧縮技術は、より一般的な特性を有するデータ(即ち、共通の特性を高いレベル所有することのないデータ)を圧縮するのには効率的でなくなる傾向がある。

0004

これに対し汎用目的の圧縮技術は、あるタイプのデータを特別に圧縮するよう設計されたものではなく、種々雑多なタイプのデータを圧縮するのに適している。最も広く知られ有効な汎用目的の圧縮技術は、J.ZivとA.Lempelの開発したアルゴリズム群から得られたものである。これを通常「ランペルジブ(Lempel−Ziv)符号化」と称する。特にZiv et al.著の「“A Universal Algorithm for Sequential Data CompressionM”,IEEE Transactions on InformationTheory,IT−23(3):337−343,May 19977(describing the comonly denominated“LZl”algorithm)」(通常LZ1アルゴリズムと称する)とZiv et al.著の「“Compression of Individual Sequences Via Variable−Rate Coding”,“IEEE Transactions on Information Technology,IT−24(5):530−536,September 1978(describing the commonly denominated“LZ2”algorithm)」(LZ2アルゴリズムと称する)を参照のこと。LZ1とLZ2のデータ圧縮技術は、従来公知であるのでその詳細な説明は割愛する。

0005

しかし簡単に説明すると、LZ1(LZ77とも称する)データ圧縮プロセスは、前に現れたシーケンス(即ち、マッチングシーケンス)を参照して文字繰り返しシーケンス置換するという原理に基づいている。基準(reference;例えばポインター)は、以前に発生した位置の表示(繰り返しシーケンスの開始点からオフセット(ずれた)されたバイトと繰り返されるキャラクターの長さ、すなわちマッチした長さ)で表される。通常基準は、従来のLZ1符号化によれば、<offset length>ペアとして表される。これに対しLZ2(LZ78とも称する)の圧縮は、入力データキャラクターのストリームを、自動的に成長するルックアップテーブル、あるいは圧縮プロセスの間生成される字引に基づいて符号化値解析している。すなわちLZ2は、任意のバイト境界及びLZ1符号化内の長さでもってマッチングを見いだすことはなく、字引のワードソースストリングにマッチングしたときには、新たなワードが字引に追加される。そしてこの字引は後続のソースストリングバイトとマッチングしたワードを加えたものから成り立っている。LZ2符号化によれば、マッチングはポインターとして、あるいは字引内のワードに対するインデックスとして符号化される。

0006

前述したようにLZ1アルゴリズムとLZ2アルゴリズムにより具体化された基本原理に基づいて派生した沢山の圧縮系が存在する。例えば、TerryA.Welch(T.A.Welch,“A.Technique for High Performance Data Compression”,IEEE Computer,pp.8-19,June 1984,and U.S.Patent No.4,558,302,issued to welch on December 10,1985,each of which is incorporated by reference for all purposes)は、LZ2符号化プロセスを公知のLempel-Ziv-Welch(LZW)圧縮プロセスとしてまとめ上げた。LZ2圧縮技術とLZW圧縮技術の両方は、入力キャラクターのストリング固定長さの符号にマッピングするような、いわゆるストリングテーブルの生成及び使用に基づいている。具体的に説明すると、これらの圧縮技術は、データキャラクターのストリームを圧縮ストリームに圧縮するために、キャラクターストリームを直列的サーチし、テーブル内、すなわち字引内に以前に記憶された対応する最長の可能性のあるストリングにマッチするたシンボルのシーケンスに基づいて符号を生成することによりデータキャラクターのストリームを圧縮している。マッチングが行われ符号シンボルが生成されると、この圧縮プロセスはデータストリーム内のマッチングしたシーケンスとデータストリーム内の次のキャラクターシンボル遭遇を加えたものを含む字引内の新たなストリングエントリーを記憶する。

0007

前述したようにLempel-Ziv符号化の本質は、元のデータストリーム内、例えば送信すべきドキュメント内で繰り返されるストリングとサブストリングを見いだすことである。圧縮された状態のドキュメント中に繰り返されるフレーズは、ポインターでもってそれらが元のデータストリーム、例えばドキュメント中に以前に発生した場所に置換される。斯くして復号化データ、例えばこのようにして圧縮されたテキストは、ポインターが指摘した、すでに復号化されたテキストでもってポインターを置換することが必要となる。従来公知のようにLempel-Ziv符号化技術を採用する際に考慮すべき重要な点は、ポインターがどこまで後ろにさかのぼるかに対する制限を設定すべきか否かを決定すること、及びこの制限はどんなものであるかを決定することである。Lempel-Ziv符号化でさらに設計的に考慮すべき事項は、所望の制限内にどのサブストリングがポインターの目標となり得るかである。即ち、ポインターが前のテキストに到達することが制限されていない場合、所謂、ウィンドウを成長させるか、あるいは前のN個のキャラクターから成る固定サイズのウィンドウに制限されるかである。ここでNは数千キャラクター、例えば3キロバイトの範囲内にある。この符号化によれば、ストリングの繰り返しが発見されると、それらの両方がウィンドウ内に現れる場合にのみ圧縮される。Lempel-Ziv符号化設計に関し、なされた考慮すべき事項は、速度とメモリーの大きさとその圧縮比率の間の妥協点を見いだすことである。

0008

圧縮はネットワークの効率を改善するためには考慮すべき点である。例えば、利用可能な計算資源、即ちデータ処理要件が利用可能なネットワークの帯域幅に比較して大きい場合には、ネットワークにデータパケット伝送する前にデータパケットを圧縮するのが好ましい。当然のことながら実際に採用する圧縮系は速度と全体的な圧縮効率の関係から注意深く選択しなければならない。即ち、遅い圧縮系は、ネットワークの性能を低下させ、非効率な圧縮系は潜在的な伝送利得を制限してしまう。

0009

さらに複雑なネットワーク効率の問題は、多くのパケットネットワークが本来的に信頼性を有しないということである。即ち、現在知られているパケットネットワーク、例えばインターネットは、ネットワーク内を伝送されるパケット日常的にドロップしたり、あるいは再度順序付けているが、これによりデータ伝送にエラーが発生する。例えば、ある圧縮系がパケット間のある種の相互依存性を導入し、そしてその後ネットワークがこのパケットをドロップしたり、再度要求するような場合そして受信器で前のパケットが失われている場合には、パケット間の相互依存性により、特定のパケットを脱圧縮することはできない(元に戻すことはできない)。斯くして、ある種のアプローチがこのような問題を解決するために採用されている。(1)ネットワークの信頼性の改善。これによりインターネットにおいては、より信頼性のある端末間のトランスポート層サービス、例えば公知のトランスミッション制御プロトコル(Transmission Control Protocol; TCP)が適用されてトランスポートレベルでパケットを圧縮する。(2)無状態(ステイトレス)圧縮を採用する。これは、各パケットは独立に圧縮され、これにより各パケットが受信器で脱圧縮される。(3)ストリーミング(Streaming)圧縮は信頼性が広く行き渡っていることを仮定し、この仮定が破られた時にはリセットメカニズムを採用する。具体的に説明すると、パケットが失われたときには受信器は圧縮がリセットされるまで後続の各パケットを廃棄する。リセットの後はそれ以降のパケットは前のパケットには依存せず、脱圧縮は通常の形態で再開される。これら2つの公知のストリーミングタイプの圧縮技術は、Point−to−Point Protocol(PPP)圧縮制御プロトコルとUse Datagram Protocol(UDP)パケットに対し採用されるIPヘッダー圧縮プロトコルを有する。

0010

上に説明したパケット圧縮系は、パケットの相互依存性から発生する問題を解決するのには有効であるが、このような圧縮系はまた別の問題を発生させる。例えば、トランスポートレベルでのパケットの圧縮は端末間の利用を必要とし、通常、伝送中にアプリケーションによるあるレベルの共同作業を必要とする。同様にステイトレスの圧縮は、ある種の頑強さを提供するが、ステイトレスの圧縮のパケットの独立性の特性により、実際の圧縮比率が下がるが、これはこのような圧縮が1個のパケット内のデータを検査するからである。斯くして、例えば、この圧縮アプローチは隣接するパケットのネットワークヘッダー内に通常見いだされる大量の冗長性を除去することができない。さらにまた、ストリーミング圧縮はより大きな圧縮技術を与えることができるが、これらの圧縮系はパケットがネットワーク内で喪失した場合には、パケットの喪失の影響を大幅に増やし、これにより受信器が他の数個のパケットを受領できないことになる。信頼性が低いネットワーク、例えばインターネットにおいてはこのパケットの大きな影響は、ストリーミング圧縮を採用する利便性を低下させることになる。

発明が解決しようとする課題

0011

本発明の目的は、従来の圧縮系の欠点を有さず、頑強性を増し、圧縮比率を増加させるような圧縮技術を提供することである。本発明の目的は、従来の圧縮系の欠点、例えばパケットの喪失による悪影響の拡大を有さず、頑強性を増し、圧縮比率を増加させるような圧縮方法と装置を提供することである。

課題を解決するための手段

0012

本発明の態様によれば、所謂、受領確認ベクトル(acknowledgement vector)の関数として決定された選択ヒストリー状態(select history state)が採用される。本発明の一態様によれば、この受領確認ベクトルは通信チャネルを介し従来どうり転送する際、成功裏に受領したパケットの識別子に関する情報を含む。即ちパケットヒストリー状態はそれぞれのパケットの選択ヒストリー状態である。通信チャネルの第1端(例、送信器側)には、第2端(例、受信器)が成功裏に受信したパケットに関連するある種の情報が与えられ、それを認識している。脱圧縮器には選択ヒストリーが与えられ、それを認識し、これにより送信器側から送信された圧縮パケットを効率的に脱圧縮する(伸張する、戻す)。即ち脱圧縮は、このようなパケットを圧縮する間のヒストリーすなわち選択ヒストリー状態として用いられたパケットの関数として(基づいて)行われる。斯くして本発明の選択ヒストリー状態と受領確認の観点により圧縮器と脱圧縮器(通信チャネルの何れかの側にある)は、共同して機能して通信チャネルで行われた圧縮を改善している。

0013

本発明の一実施例によれパケットは符号化され、少なくともヒストリーベクトルを含むヘッダーが付与される。このヒストリー状態は、パケットのそれぞれのヒストリー状態を特定している。さらにまた、本発明の一態様によれば受領確認ベクトルが構築され、送信器側に送られて、これにより送信器側の特定の圧縮アルゴリズムが成功裏に受領したパケットに対する圧縮アルゴリズムにより使用されたヒストリーを制限することができる。斯くして、本発明の一態様によれば、ヒストリーとして用いたパケットを特定するベクターが圧縮されたパケット内に含まれて、これにより受信器がパケットを脱圧縮するのに必要なパケットヒストリー状態を再構築する。

0014

本発明の一態様によれば、頑強さ及び圧縮比率の向上は様々な圧縮方法、あるいは通信チャネルの装置で達成することができる。即ち、本発明の原理は特定の種類の圧縮系によらず、そのため本発明の様々な態様を採用することにより圧縮技法及び通信チャネル技法で本発明の利点は実現できる。

発明を実施するための最良の形態

0015

本発明は様々な装置及び方法で実現することができる。本発明はフロッピー登録商標ディスクCD−ROMハードドライブあるは他の機械読み取り可能な記憶媒体等で具体化されるプログラムコードの形態で実現できる。また、プログラムコードはコンピュータ内に組み込み実行できる場合には、このようなコンピュータは本発明を実行するための装置である。本発明はまた、記憶媒体中のプログラムコードの形態でも実現でき、記憶媒体中でそして機械により搭載、及び機械により実行され伝送媒体を通して送信されるようなプログラムコード の形態で実現できる。プログラムコードがコンピュータのような機械で実現できる場合には、このような機械は本発明の装置となる。汎用プロセッサーで本発明が実現される場合にはプログラムコードは、プロセッサープログラム構造セグメントプロセッサと組み合わされて特定の論理回路を実行するような装置を提供できる。

0016

図1はデータを脱圧縮したりするシステム100のブロック図である。このシステム100は特に伝送媒体、例えば有線無線あるいは光ファイバーを介して情報を送受信するのに有効である。さらにまた、システム100はコンピュータディスクドライブのような磁気記録媒体、あるいはCD−ROMのような光学的に読み取り可能な媒体から情報を読み出したり、そこに情報を記録するのに有効である。斯くして、磁気ディスクドライブのような磁気媒体、CD−ROMのような光学読み取り可能な媒体を含む記録媒体に本発明により圧縮されたデータを記録することができる。図1において入力データストリーム105、例えばテキストがデータ符号化器110に与えられる。データ符号化器110は本発明によれば可変のヒストリー状態パケット間圧縮を適応して入力データストリームをあらかじめ処理し符号化する。符号化プロセスにおける本発明の様々な態様は、図2を参照して以下詳述する。

0017

図1のシステム100において、本発明により生成された符号化入力データストリーム115が圧縮器120に与えられる。この圧縮器120は本発明により圧縮技法例えばLempel-Ziv圧縮を適応して符号化入力データストリーム115を圧縮して圧縮データ125を形成する。前述したようにLempel-Ziv形の圧縮は本発明により符号化入力データストリーム115を圧縮する際有効に用いられる。圧縮データ125はその後チャネル符号化器130により符号化され、チャネル符号化情報135を生成する。チャネル符号化技術が情報を圧縮した情報に加えられ、データ読み取りプロセスにおいてエラー検出及び/または訂正が可能となる。従来のチャネル符号化技術は、公知のリードソロモン符号化技術を含み、これにより1ビットあるいは複数のビットにより表されるシンボルのシーケンスを符号化する。これらのシンボルはその後、変調符号化器140により変調符号化され変調されたデータストリーム145を生成し、この変調されたデータストリーム145がチャネル/媒体150上に記録されるか、あるいは通信チャネルを介して送信されるチャネルシーケンスを規定する。

0018

データストリームの伝送あるいは記録プロセスの間、ノイズ干渉がチャネル/媒体150内に時に導入されることがある。斯くして、変調復号化器155とチャネル復号化器160はノイズを含んだ変調されたデータストリーム145を受領し、そして公知の方法でそれぞれチャネル符号化器130と変調符号化器140の符号化処理の逆を行う。チャネル復号化器160からのデータストリームは圧縮器120により生成された圧縮データ125に対応する。その後、このデータストリームを本発明により脱圧縮器165で脱圧縮され、データ復号化器170で復合化されて図4で詳述するように出力データストリーム175を生成する。

0019

本発明の様々な態様は、圧縮の頑強性及び圧縮技術の改善を実現するのに向けられる。図2図1のシステムで用いられ、本発明によりデータを圧縮する動作200のフローチャートを示す。具体的に説明すると、入力データストリームを受領し、そして成功裏に受領したパケットが検査される(図2ブロック210)。本発明によればこの成功裏に受領したパケットを検査することにより、パケットのヒストリー状態の特定が受領確認ベクターの関数として可能となる(ブロック220)。本発明の一実施例によればパケットのヒストリー状態は、現在のパケットの圧縮が決定される元となったパケットの前の組である。例えば、Lempel-Ziv77においては、圧縮ヒストリー状態はこのLempel-Ziv圧縮で採用された、所謂、字引との直接相関である。興味深いことにネットワークパケットのステイトレス圧縮と、ストリーミング圧縮との間の大きな違いは、各形が採用する特定のヒストリー状態である。即ち、ステイトレス圧縮はヒストリー状態を採用せず、一方ストリーミング圧縮によれば前のパケットをヒストリーとして採用する。このような差は、本発明の原理でも依然として存在する。

0020

さらに具体的に説明すると、本発明の一実施例によれば、パケットヒストリー状態は受信器側により通信チャネルを介して成功裏に受領した特定のパケットに関連する選択ヒストリー状態である。そしてこの受信器側には、送信され圧縮されたパケットを効率的に脱圧縮することができるような選択ヒストリーが与えられ、通知される。好ましいことに本発明によれば、選択されたパケット間ヒストリー状態を用いることにより、本来的にパケットの喪失の被害を受ける従来のストリーミング圧縮系に対し、圧縮の頑強性及び圧縮比率の改善を図ることができる。

0021

前述したように選択パケットヒストリー状態を特定した後、このヒストリー状態を採用して送信側から送信するために待機しているパケットに対し、ある種の情報を符号化する。具体的に説明すると本発明によれば、個々のパケットはそれに関連するそれぞれのパケットヒストリー状態の関数として符号化される(ブロック230)。本発明によれば各パケットにはヘッダーが付与され、このヘッダーは例えばパケットに関連したそれぞれのパケットヒストリーを特定するヒストリーベルトルを含む。図2を参照すると300が図2の操作に従って圧縮された状態を示す。図3の実施例においては、パケットヘッダーはシーケンス番号及び受領確認ベクトルのような付属アイテムを含む。即ち、本発明によれば前述した受領確認ベクトルはパケットヘッダーの一部として送信される。受領確認ベクトルが符号化パケットとは別個に送信されたか、あるいはパケットヘッダーの一部として送信されたかの決定は、本発明の適応にあたっては、設計的選択事項である。例えば、受領確認ベクトルはいわゆるpiggybacking技術を用いて送信者側に送信することができる。そしてこのpiggybacking技術は受信器から送信器側への反対方向内のデータストリームが存在する。

0022

例えば300は一連のパケットを含む(例、図3ではパケット1からパケットNはパケット305−311として示されている)。さらにまた各パケットはヘッダーを含む(例、H1からHnはヘッダー320−330として示されている)。さらにまた、ヘッダー1 320はシーケンス番号335とヒストリーベクトル340と受領確認ベクトルを含む。

0023

本発明の一実施例によれば、シーケンス番号、例えばシーケンス番号335は送信器側と受信器側の両方で用いられ、本発明により圧縮されたパケットを特定する。シーケンス番号を符号化するのに必要とされるビットの数は、ネットワーク全体を移動するのに必要な最大時間の間、所謂「ラッピング;wrapping」される悪影響を回避するのに十分な程度に必要である。例えば、シーケンス番号335は24ビットの長さで示されている。

0024

さらにまた本発明の一実施例においては、ヒストリーベクトル、例えばヒストリーベクトル340は圧縮するのに用いられた前のパケットの組、即ち選択ヒストリー状態を記述する。ヒストリーを決定するために受領確認パケットを利用する本発明の実施例においては、パケットが送信される時間とパケットがヒストリーとして用いられる時間との間のネットワークの往復時間に関連する時間遅延が発生する。斯くして、本発明の一実施例によれば、ヒストリーベクトルはオフセットとビットマスクを用いて符号化され、その結果オフセットはパケットのシーケンス番号から減算されて、最も最後のヒストリーパケットのシーケンス番号を確立する。ビットマスクは最後のヒストリーパケットの直前の付加的なヒストリーパケットを特定する。具体的に説明すると、ヘッダー1 320においては、ヒストリーベクトル340は8ビットのオフセットと8ビットのマスクとを含み、これによりヒストリー状態を最後の263内の最大9個の連続パケットに制限する。

0025

前述したように図3のパケットヘッダーは、最後の方で受信したパケットの組を記述する受領確認ベクトル、例えば受領確認ベクトルを含む形で具体化されている。この受領確認ベクトルは、最後に受領したパケットのシーケンス番号と、その直前のパケットの状態を記述するビットマスクを少なくとも含む。例えば受領確認ベクトルは32ビットの長さで、シーケンス番号に対しては24ビットをカバーし、関連マスクに対しては8ビットをカバーする。

0026

図2に戻ってパケットを本発明により、それぞれパケットヒストリー状態の関数として符号化した後(ブロック230)、これらのパケットはその後圧縮される。前述したように本発明の利点は、様々な既存の圧縮技術と共に適応可能な点である点である。例えば、以下に詳述するように本発明は基地デフレート(Deflate)圧縮系、あるいはLZ77圧縮に適用されるパケットストリームの圧縮技術を改善する。選択的な圧縮系を符号化パケットに適用した後(ブロック240)、この圧縮されたパケットは送信用に待機する(ブロック250)。

0027

本発明の一態様によれば、ネットワーク内を伝送するパケットの関数として選択ヒストリー状態を採用することにより、洗練された圧縮ツールが達成できる。即ち、本発明によれば各パケットに関連するパケットヒストリー状態が送信器側で選択ヒストリー状態であり、この送信器側に受信器側が成功裏に受領したパケットに関連するある種の情報を与え通知される。そして、受信器側にはこのパケットに関連する選択ヒストリー状態が与えられ通知され、これにより送信器側から送信された圧縮パケットの効率的な脱圧縮が可能となる。斯くして本発明の選択ヒストリー状態と受領確認の技術により送信器側と受信器側は共同して通信チャネルにおける圧縮を改善する。

0028

具体的に説明すると本発明によれば、受領確認ベクトルを特定の圧縮アルゴリズムと共に用いて送信器側が正確に受領したパケットに対し、圧縮アルゴリズムで用いたヒストリーを定める。斯くして本発明の一実施例によればヒストリーとして用いられたパケットを特定するベクトルが圧縮されたパケットに含まれ、これにより受信器は、パケットを脱圧縮するのに必要なパケットヒストリー状態を再構築する。さらに本発明によれば、受領確認ベクトルは、圧縮されたパケットとは別に送信される。更に又、実施例では単一の通信チャネル構成について議論しているが、本発明は複数の通信チャネル構成についても等しく適用可能である。さらに本発明の態様によれば、選択ヒストリー状態を用いることにより圧縮の頑強性及び圧縮比率を従来のストリーミング圧縮系(パケット喪失の場合に妥協せざるを得ない従来のストリーミング)よりも改善する。

0029

本発明の圧縮テスト結果を記述する前に本発明の脱圧縮について説明する。図4は、本発明によりデータを脱圧縮する操作400のフローチャートである。受信したパケットの圧縮ストリームから(ブロック410)ヒストリーベクトルをパケット毎ベースで抽出する(ブロック420)。例えば、以下の擬似符号が本発明の一実施例によりこれらのアイテムの抽出を記述する。
────────────────────────────────────
────────────────────────────────────
パケットからシーケンス番号を抽出する。
ヒストリーベクトルのオフセットとマスクを抽出する。
オフセットが0の場合には、ヒストリーは存在しない。
それ以外の場合{
「シーケンス番号からオフセットを抽出してヒストリーの第1パケットを与え
る。」マスク!=0{
シーケンス番号から1を減算する。
低ビットがマスク内に設定された場合には、パケットをヒストリーに追加する

マスクを最も右の1ビットにシフトする。


パケットを脱圧縮する。
受領確認ベクトルと最後に受信したパケットのシーケンス番号とビットマスク
を抽出する。
────────────────────────────────────
────────────────────────────────────
上記の仮コードを用いて本発明を実行するCプログラム言語でコンピュータをプログラムすることが出来る。ヒストリーベクトルの抽出から脱圧縮状態のパケットのヒストリー状態が特定される(ブロック430)。さらに本発明によれば、抽出は受領確認ベクトルとパケットヘッダーからのシーケンス番号の抽出を含む。現行パケットの脱圧縮は、特定されたヒストリー状態の関数として行われる(ブロック440)。その結果現在の未圧縮パケットがそれぞれの脱圧縮器、例えば特定の通信チャネルの受信器側にある脱圧縮器の現在受領したパケット状態に追加される(ブロック450)。これにより受信したパケットの組を更新する。最後に現行パケットを脱圧縮した後、受領確認ベクトルが構築され、送信者側に送信して戻される(ブロック460)。前述したように受領確認ベクトルは、最後に受領したパケットの組を記述し、送信器側がそれを用いて選択ヒストリー状態と共に今後のパケットを圧縮する。

0030

本発明は、従来公知の2つの圧縮フォーマットを用いるある種の圧縮シミュレーションでも適用可能である。具体的に説明すると、Deflate圧縮フォーマットは、データパケットの所定のシーケンスと共に用いられた。Deflateは、gzip、zip、pmgのような公知のファイルフォーマット基礎となる一般的な圧縮フォーマットである。Deflateは、LZ77とハフマン符号化技術とを組み合わせ、ネットワークプロトコル内ではPPPと共に使用される。上記のフォーマットは、http:www.cdrom.com/pub/infozip/zlibでインターネットを介して入手可能である。DeflateのZlibの実行は、6個のデフォルタ値に設定された圧縮レベルと共に用いられる。

0031

具体的に説明すると、公知のCalgary Corpus(a widely used standard reference for evauating the effectiveness of compression algorithms;圧縮アルゴリズムの有効性を評価する広く用いられている標準基準)からの14個の通常使用されているファイル(これに関してはT.C.Bell et al.著の「Modeling fortext compression,Computing Surveys 21(4):557-591,December 1989」を参照のこと)を用いて圧縮用の入力データストリームを特定した。バイトシーケンスアルファベット順番で14個のCalgary Corpusファイルを連続させることにより形成され、1600バイトのパケットと125バイトのパケットから成る固定サイズのパケットに入力ストリームを分割した。本発明は、通信チャネルを伝送させるパケットの受領確認を含む。本発明の圧縮シミュレーションの例とモデルと圧縮器に到達した様々な受領確認の中の圧縮器に到達した受領確認、即ちパケットが遅延する。

0032

ここに示した実施例は、1600バイトと125バイトのパケットサイズに対し、入力バイトに対する出力バイトの数に対する遅延の影響の比較を示す。特に図5は、公知のstateless圧縮系(520)と公知のstreaming圧縮系(530)と本発明による圧縮(受領確認圧縮 ;acknowledged compression ;Ackと称する)の間を比較するためにそれぞれのパケットサイズに対するシミュレーションの結果である500と510を示す。Ack結果540と、シミュレーション結果500と510から判るように、Ack結果540はstateless圧縮の結果520よりもより大きな圧縮を示すが、streaming圧縮の結果530程ではない。streaming圧縮の結果530は、このような圧縮に本来的に付随するパッケット喪失の影響を考慮に入れていない。これに対し本発明のAck結果540は、このようなパケット喪失による影響を受けない。

0033

図に示したブロックは、本発明を実現する回路概念を表すものである。フローチャート、フローダイヤグラム状態遷移図、仮コード、プログラムコード等は、コンピュータで読み込み可能な媒体の中で行われる様々なプロセスを表し、そしてコンピュータ、マシンプロセッサーにより実行されるが、このようなコンピュータ、マシンプロセッサーは図には明確には示していない。

0034

特許請求の範囲に発明の構成要件の後の括弧内の符号が記載されている場合は、構成要件と実施例と対応づけて発明を容易に理解させる為であり、特許請求の範囲の解釈に用いるべきのものではない。

図面の簡単な説明

0035

図1データを圧縮したり、脱圧縮したりするシステムのブロック図。
図2図1のシステムで使用される本発明によるデータを圧縮する操作を表すフローチャート図。
図3図2の動作に従って圧縮されたパケットストリームを表す図。
図4図1のシステムで使用される本発明によるデータを脱圧縮する操作を表すフローチャート図。
図5従来の圧縮系と本発明の圧縮系との間の比較を行うために様々な大きさのパケットに対する圧縮結果を表す図。

--

0036

100 システム
105入力データストリーム
110データ符号化器
115符号化入力データストリーム
120圧縮器
125圧縮データ
130チャネル符号化器
135チャネル符号化情報
140変調符号化器
145変調されたデータストリーム
150チャネル/媒体
155 変調復号化器
160チャネル復号化器
165 脱圧縮器
170データ復号化器
175出力データストリーム
210受領パケットを検査する
220受領確認ベクトルの関数としてパケットヒストリー状態を特定する
230 個々のパケットヒストリー状態の関数として符号化する
240符号化パケットを圧縮する
250 圧縮されたパケットを送信する
305 パケット1
320ヘッダー1
325 ヘッダー2
310パッケト
330 ヘッダーN
315 パッケトN
335シーケンス番号
340 ヒストリーベクトル
345 受領確認ベクトル
410 圧縮されたパケットを受領する
420パケット毎にヒストリーベクトルを抽出する
430 ヒストリー状態を特定する
440現パケットをヒストリー状態の関数として脱圧縮する
450 圧縮していない現パケットを受領したパッケト状態に追加する
460 受領確認ベクトルを構築し送信する

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ