TOP > 国内特許検索 > データ圧縮器及びデータ解凍器 > 明細書

明細書 :データ圧縮器及びデータ解凍器

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第6168595号 (P6168595)
公開番号 特開2014-236449 (P2014-236449A)
登録日 平成29年7月7日(2017.7.7)
発行日 平成29年7月26日(2017.7.26)
公開日 平成26年12月15日(2014.12.15)
発明の名称または考案の名称 データ圧縮器及びデータ解凍器
国際特許分類 H03M   7/42        (2006.01)
FI H03M 7/42
請求項の数または発明の数 12
全頁数 26
出願番号 特願2013-118356 (P2013-118356)
出願日 平成25年6月4日(2013.6.4)
審査請求日 平成28年4月13日(2016.4.13)
特許権者または実用新案権者 【識別番号】504171134
【氏名又は名称】国立大学法人 筑波大学
【識別番号】504174135
【氏名又は名称】国立大学法人九州工業大学
発明者または考案者 【氏名】山際 伸一
【氏名】坂本 比呂志
早期審査対象出願または早期審理対象出願 早期審査対象出願
個別代理人の代理人 【識別番号】100123319、【弁理士】、【氏名又は名称】関根 武彦
【識別番号】100123098、【弁理士】、【氏名又は名称】今堀 克彦
審査官 【審査官】北村 智彦
参考文献・文献 国際公開第2011/105463(WO,A1)
特開平06-274310(JP,A)
特開平06-266532(JP,A)
特表2005-535175(JP,A)
特開平04-288618(JP,A)
Shinichi Yamagiwa, Hiroshi Sakamoto,A Reconfigurable Stream Compression Hardware based on Static Symbol-Lookup Table,Big Data, 2013 IEEE International Conference on,2013年10月,pp.86-93
調査した分野 H03M 3/00-11/00
IEEE Xplore
CiNii
特許請求の範囲 【請求項1】
受信側の通信機器にストリームデータを送信する送信側の通信機器に搭載されるデータ圧縮器であって、
複数の固定長のシンボルからなる前記ストリームデータである入力データ列の入力を受け、前記入力データ列をシンボル単位で保持及び出力するラッチと、
シンボル数が固定の2以上のシンボルに対応する変換先の1つのシンボルをそれぞれ示す複数のエントリが登録されたメモリであって、前記ラッチから出力された、連続する2以上のシンボルに対応する1つのシンボルを前記複数のエントリから検索する処理を1回行い、前記連続する2以上のシンボルに対応する1つのシンボルがヒットした場合に、前記ヒットした1つのシンボルを出力すると共に、前記ヒットした1つのシンボルの出力を示す信号を出力するメモリと、
前記ラッチから出力される前記連続する2以上のシンボルと、前記メモリから出力される前記ヒットした1つのシンボルと前記信号とを入力可能であり、前記メモリから出力された前記信号に基づいて前記ラッチから出力された前記連続する2以上のシンボルと前記メモリから出力された前記ヒットした1つのシンボルとの一方を出力するセレクタと、
を含み、
前記メモリにおける処理遅延がほぼ固定されており、前記セレクタの処理遅延がほぼ一定であり、前記ラッチから前記連続する2以上のシンボルが出力されてから前記セレクタが前記連続する2以上のシンボルと前記メモリから出力された前記1つのシンボルとの一方を出力するまでの処理遅延が固定化されている
データ圧縮器。
【請求項2】
前記入力データ列に含まれる前記シンボル間の大小関係に基づいて、前記入力データ列に含まれる前記シンボル間の区切位置を決定する区切位置決定回路
をさらに含み、
前記メモリは、前記ラッチから出力される前記2以上のシンボルであって、前記区切位置を基準とした所定数ずつのシンボルに対し、対応する1つのシンボルを出力すると共に
、前記1つのシンボルの出力を示す信号を出力する
請求項1に記載のデータ圧縮器。
【請求項3】
前記セレクタの、前記2以上のシンボルが1つのシンボルに変換された場合の出力は、そうでない場合の出力が取り得ない値となる
請求項1又は2に記載のデータ圧縮器。
【請求項4】
前記メモリは、CAM(Content Addressable Memory)である
請求項1から3のいずれか一項に記載のデータ圧縮器。
【請求項5】
前記メモリは、前記ラッチから出力された連続する2つのシンボルに対応する1つのシンボルを出力する
請求項1から4のいずれか一項に記載のデータ圧縮器。
【請求項6】
前記ラッチは、所定のクロック信号に従って動作する第1~第3のフリップフロップを含み、
前記第1のフリップフロップは、入力された前記シンボルを保持すると共に前記クロック信号に従い保持しているシンボルを前記第2のフリップフロップ及び前記メモリに出力し、
前記第2のフリップフロップは、前記第1のフリップフロップが出力した前記シンボルを保持すると共に前記クロック信号に従い保持しているシンボルを前記第3のフリップフロップ及び前記メモリに出力し、
前記第3のフリップフロップは、前記第2のフリップフロップが出力した前記シンボルを保持すると共に前記クロック信号に従い保持しているシンボルを前記セレクタに出力し、
第1のタイミングにおいて、前記第1のフリップフロップ及び前記第2のフリップフロップに保持された連続する2つのシンボルが、それぞれ後段のフリップフロップ及び前記メモリに出力されると、
第2のタイミングにおいて、前記メモリが、前記1つのシンボルの出力を示す信号を出力した場合、前記セレクタは前記メモリが出力した1つのシンボルを出力し、
前記第2のタイミングにおいて、前記メモリが、前記1つのシンボルの出力を示す信号を出力しない場合、前記セレクタは、当該第2のタイミングにおいて前記第2のフリップフロップ及び前記第3のフリップフロップに保持されている連続する2つのシンボルを逐次出力する
請求項5に記載のデータ圧縮器。
【請求項7】
前記1つシンボルの出力を示す信号は、前記セレクタが出力するシンボルを解凍するデータ解凍器へ接続される信号線にも出力される
請求項1から6のいずれか一項に記載のデータ圧縮器。
【請求項8】
請求項7に記載のデータ圧縮器を複数直列に接続し、
前段のデータ圧縮器の前記セレクタが出力するシンボルを後段のデータ圧縮器に前記入力データ列として入力するデータ圧縮装置であって、
より後段のデータ圧縮器において置き換えられたシンボルほど、複数直列に接続される前記データ解凍器のうち前段のデータ圧縮器において解凍される
データ圧縮装置。
【請求項9】
データ圧縮器に搭載された送信側の通信機器から送信されるストリームデータを受信する受信側の通信機器に搭載されるデータ解凍器であって、
固定長のシンボルを含む前記ストリームデータである入力データ列の入力を受け、前記
入力データ列をシンボル単位で保持及び出力するラッチと、
圧縮処理を行い前記入力データ列を生成したデータ圧縮器において変換される2以上のシンボルが、変換前の1つのシンボルに対応付けて登録されるメモリであって、前記ラッチから出力された1つのシンボルに対応する2以上のシンボルを出力するメモリと、
前記メモリから2以上のシンボルが出力された場合、所定の制御信号を出力する検知回路と、
前記制御信号が入力される場合、前記メモリが出力した前記2以上のシンボルを出力し、そうでない場合、前記ラッチから入力される前記1つのシンボルを出力するセレクタと、
を含み、前記メモリ、前記検知回路及び前記セレクタは解凍処理の処理遅延を固定的にする
データ解凍器。
【請求項10】
送信側の通信機器から送信されるストリームデータを受信する受信側の通信機器に搭載されるデータ解凍器であって、
固定長のシンボルを含む前記ストリームデータである入力データ列の入力を受け、前記入力データ列をシンボル単位で保持及び出力するラッチと、
1つのシンボルに対応付けて、2以上のシンボルが登録されるメモリであって、前記ラッチから出力された1つのシンボルに対応する2以上のシンボルを出力するメモリと、
圧縮処理を行い前記入力データ列を生成したデータ圧縮器から、前記入力データ列に含まれる前記シンボルが前記データ圧縮器において変換されたものであるか否かの少なくとも一方を示すフラグの入力を受けると共に、前記フラグが、前記入力データ列に含まれる前記シンボルが前記データ圧縮器において変換されたものであることを示す場合、前記メモリが出力した前記2以上のシンボルを出力し、前記フラグが、前記入力データ列に含まれる前記シンボルが前記データ圧縮器において変換されたものでないことを示す場合、前記ラッチから入力される前記1つのシンボルを出力するセレクタと、
を含み、前記メモリ及び前記セレクタは解凍処理の処理遅延を固定的にする
データ解凍器。
【請求項11】
前記メモリは、前記データ圧縮器が有するCAMにおいてアドレスとして保持されているシンボルに対応付けて保持している2以上のシンボルを出力する
請求項9又は10に記載のデータ解凍器。
【請求項12】
前記データ圧縮器と同数の、前記データ圧縮器に各々が対応する、請求項9~11の何れか一項に記載のデータ解凍器を直列に接続し、対応するデータ圧縮器から受信したフラグに基づいて、データ解凍器のセレクタが2以上のシンボル又は入力データ列に含まれるシンボルを出力する
データ解凍装置。
発明の詳細な説明 【技術分野】
【0001】
本発明は、データ圧縮器及びデータ解凍器に関する。
【背景技術】
【0002】
近年における、データストリームがネットワーク上を流れる環境下では、データストリームを形成するストリームデータに対するリアルタイム処理を行うため、ストリームデータを送受信する様々なエンティティ間におけるデータ伝送時間の短縮化が求められている。エンティティは、例えば、ネットワークに接続された様々な通信機器(端末装置,中継装置)である。また、データストリームは、通信機器内に搭載されたプロセッサ,LSI(Large Scale Integrated Circuit),FPGA(Field Programmable Gate Array)の
ような様々なストリームデータに対する処理を行う電子回路チップ間を流れる。電子回路チップもエンティティの1つであり、エンティティ間の通信は、通信機器間の通信だけでなく、通信機器内部の電子回路チップ間の通信(いわゆる内部通信)を含む。
【0003】
近年では、ストリームデータ量が増大する傾向にある。或る量のストリームデータを送信側から受信側へ効率的に伝送する手法として、エンティティ間を結ぶ伝送路の周波数を上げる(伝送帯域を広げる)ことや、エンティティ間を複数の伝送路で結び、ストリームデータを並列に送信することが考えられる。しかしながら、これらの手法は、物理的、周波数的な限界がいずれ来ると考えられている。
【0004】
そこで、送信側エンティティでストリームデータの圧縮を行うことで、送信データ量の減少に伴うデータ伝送時間の短縮化を以て、データ伝送の効率化を図ることが考えられている。例えば、通信機器において、送信データを圧縮装置(LZWやRLEなど複数の圧縮アルゴリズムを含む)に接続し、元の送信データと、複数の圧縮アルゴリズムのそれぞれによる処理を経たデータとのそれぞれのデータサイズを比較し、最も小さいサイズのデータを通信機器から送出する技術がある(例えば、特許文献1)。
【先行技術文献】
【0005】

【特許文献1】特開2007-65828号公報
【特許文献2】特許第3748003号公報
【0006】

【非特許文献1】J. Ziv and A. Lempel, "A universal algorithm for sequential data compression." IEEE Transactions on Information Theory, Vol. IT-23, No.3, May 1977, p.337-343
【非特許文献2】T. Welch, "A technique for high-performance data compression." IEEE Computer. 1984, p. 8-19
【発明の概要】
【発明が解決しようとする課題】
【0007】
しかしながら、例えば、上記した特許文献1における技術(従来技術)では、ソフトウェア処理による既存の可逆圧縮アルゴリズムの適用を前提としている。このため、以下のような問題があった。
【0008】
既存の圧縮アルゴリズムでは、例えば、“abcd・・・”というデータシンボル(以下、単に「シンボル」と表記)列に対して圧縮処理が実行される場合、最初に、 シンボ
ル“a”についてルックアップテーブルが検索される。“a”がヒットした場合には、次に、“ab”についてルックアップテーブルが検索される。“ab”がヒットしなかった場合に、データ列“a”が所定の圧縮データ(例えば“x”)に変換される一方で、“ab”に対する変換用のエントリ(例えば“ab”→“y”)が新たにルックアップテーブルに登録される。
【0009】
上記手法では、検索対象がヒットしなくなるまでルックアップテーブルの検索が繰り返される。従って、ルックアップテーブルの検索回数に応じて、1回の圧縮処理に係る処理ステップが可変となる。また、ストリームデータにおいて、データ列の傾向(或る変換可能なシンボル列の出現頻度)によって、処理ステップ数が左右される。このため、1回の圧縮処理に要する時間が一定とならない。これが第1の問題である。
【0010】
また、上記手法では、ルックアップテーブルの更新によって、圧縮可能なシンボル列が増加する一方で、解凍側に解凍処理用のテーブルエントリ(“y”→“ab”)を送らなければ、解凍側で解凍を行うことができない。このとき、圧縮されたデータと解凍処理用データの合計サイズが元のデータのサイズと同等、或いは元のデータのサイズを上回る場合には、伝送路上のデータ量減少に貢献しない。これが、第2の問題である。
【0011】
さらに、上記手法では、ルックアップテーブルにおいて、圧縮されるシンボル列をなすシンボル数は、一定ではなく、どのような長さ(個数)のシンボル列でも登録可能となっている。これが第3の問題である。
【0012】
圧縮処理は、送信側エンティティがストリームデータを受信側エンティティで送信する前に実行される複数の工程(ステップ)の一つとして挿入される。このとき、圧縮処理がボトルネックとなることは回避されるべきである。また、圧縮処理において揺らぎ(ジッタ)を生じさせることも、後段に位置する工程への影響に鑑み回避されるべきである。これらの観点からは、処理ステップ数(処理遅延)が一定とならない第1の問題及び第3の問題を含む従来技術は採用し得ず、また、第2の問題に鑑みても従来技術は採用し得ない。
【0013】
さらに、圧縮処理は、処理速度の観点から、ソフトウェア処理ではなくハードウェア処理にて行われることが好ましいと考えられる。このとき、従来技術で行われる圧縮処理(アルゴリズム)を行うディジタル回路を形成しようとすると、処理が複雑なために、回路内にタイミング調整のための様々な遅延を挿入が求められ、結果として回路が複雑化し、回路規模が増大する虞があった。
【0014】
圧縮データを解凍するには、解凍処理として圧縮処理と逆の処理が受信側で実行される。このため、圧縮処理に係る上記の問題点は、そのまま解凍処理に係る問題として提起される。
【0015】
本発明は、上記の事情に鑑みなされたものであり、一定化された処理遅延での圧縮及び解凍処理を用いた送受信間における効率的なデータ伝送を行うことを可能とする技術を提供することを目的とする。
【課題を解決するための手段】
【0016】
本発明の一側面に係るデータ圧縮器は、複数の固定長のシンボルからなる入力データ列に含まれた、連続する2以上のシンボルが登録されている場合、2以上のシンボルを1つのシンボルに変換する変換部と、変換部で2以上のシンボルが1つのシンボルに変換された場合は、当該1つのシンボルを出力し、そうでない場合は、2以上のシンボルを出力する出力部とを含む。
【0017】
また、本発明の他の側面に係るデータ解凍器は、入力データ列に含まれる固定長のシンボルが、圧縮処理において2以上のシンボルから変換されたシンボルとして登録されている場合、当該シンボルを2以上のシンボルに変換する変換部と、変換部でシンボルが2以上のシンボルに変換された場合は、2以上のシンボルを出力し、そうでない場合は、入力データ列に含まれるシンボルを出力する出力部とを含む。
【発明の効果】
【0018】
本発明によれば、一定化された処理遅延での圧縮及び解凍処理を用いた送受信間における効率的なデータ伝送を行うことを可能とする技術を提供することができる。
【図面の簡単な説明】
【0019】
【図1】圧縮・解凍器の構成を示す図である。
【図2】データ圧縮器の一例を示す機能ブロック図である。
【図3】ルックアップテーブルに登録されるエントリの一例を示す図である。
【図4】データ圧縮器の一例を示す回路構成図である。
【図5】データ解凍器の一例を示す回路構成図である。
【図6】圧縮処理及び解凍処理の具体例を説明するための図である。
【図7】実施形態2に係るデータ圧縮器の一例を示す機能ブロック図である。
【図8】実施形態2に係るデータ圧縮器の一例を示す回路構成図である。
【図9】実施形態2に係るデータ解凍器の一例を示す回路構成図である。
【図10】実施形態3に係るデータ圧縮装置の処理を説明するための図である。
【図11】実施形態3に係るデータ圧縮器の一例を示す機能ブロック図である。
【図12】実施形態3に係るデータ解凍装置の処理を説明するための図である。
【図13】実施形態3に係るデータ解凍器の一例を示す回路構成図である。
【図14】実施形態4に係るデータ圧縮器の一例を示す機能ブロック図である。
【図15】実施形態4に係る区切位置決定部の一例を示す回路構成図である。
【図16】エンコーダの入出力を説明するための図である。
【図17】区切位置を決定する処理を説明する図である。
【図18】実施形態4に係る圧縮部の一例を示す回路構成図である。
【図19】データ圧縮器及びデータ解凍器の間で送受信されるデータのフォーマットの一例を説明するための図である。
【発明を実施するための形態】
【0020】
以下、本発明の実施の形態について、図面に基づいて説明する。なお、実施の形態は本発明の一例であり、本発明の構成は以下の例には限られない。

【0021】
〔実施形態1〕
図1は、データ圧縮/解凍システムを模式的に示す図である。図1において、データ圧縮/解凍システムは、データ圧縮器10と、データ解凍器20とを含む。

【0022】
データ圧縮器10は、図示しない送信側エンティティが図示しない受信側エンティティへ送信すべきデータ(例えば、ストリームデータ)に対する圧縮処理を行い、圧縮データを出力する。圧縮データは、伝送路3を通ってデータ解凍器20に到達する。データ解凍器20は、解凍処理によって、圧縮データを元のデータに戻す。そして、元のデータが受信側エンティティに供給される。圧縮処理によって、伝送路3へ送出されるデータ量が減少することで、或るサイズを有するデータが送信側エンティティから受信側エンティティに受信される迄の時間を、圧縮処理が行われない場合に比べて短縮することができる。

【0023】
データ圧縮/解凍システムは、通信機器間の通信に適用されても良く、通信機器内の構
成要素(電子回路チップ)間通信(いわゆる内部通信)に適用されても良い。通信機器間の通信のために、データ圧縮器10は、送信側の通信機器に搭載され、データ解凍器20は、受信側の通信機器に搭載されることができる。内部通信のために、データ圧縮器10及びデータ解凍器20は、通信機器や各種の情報処理装置(コンピュータ)内に構成要素の一つとして搭載されることができる。

【0024】
なお、通信機器が双方向通信を行う場合には、送信側及び受信側の通信機器のそれぞれにデータ圧縮器10及びデータ解凍器20が搭載され、上り通信と下り通信とのそれぞれにおいてデータの圧縮/解凍が行われる構成を適用可能である。

【0025】
<データ圧縮器>
図2は、図1に示したデータ圧縮器10の一例を示すブロック図である。データ圧縮器10は、例えば、送信側エンティティ(送信側装置)から入力されるストリームデータに対する可逆圧縮処理(符号化処理とも呼ばれる)を行い、可逆圧縮処理が施されたストリームデータを出力する。データ圧縮器10は、可逆圧縮の手法として、いわゆる文法圧縮を用いた静的符号化を行う。具体的には、データ圧縮器10は、ストリームデータに含まれる所定のシンボル列に対する変換ルールを規定したルックアップテーブルを有し、ルックアップテーブルに従って、所定のデータシンボル列を、当該シンボル列よりサイズの小さい1つのシンボル(圧縮シンボルとも呼ぶ)に圧縮(符号化)する。

【0026】
<<ルックアップテーブル>>
図3は、データ圧縮器10が備えるルックアップテーブルの一例を示す。ルックアップテーブルは、「入力(圧縮前)」の2つのシンボル(シンボルペアと称する)と圧縮(符号化)処理によって変換される「出力(圧縮後)」の1つのシンボルとの対応関係が登録された複数のエントリを含む。エントリ数は、ルックアップテーブルを記憶するメモリ101の記憶容量に応じた有限値である。

【0027】
図3において、1つの英文字は、1つのデータシンボルを意味する。1シンボルのサイズは固定サイズ(固定長)であり、例えば、1シンボルのサイズは1バイト(8ビット)である。ただし、シンボルのサイズは1バイトには限定されず、所定のサイズを採用することができる。

【0028】
また、図3に示すルックアップテーブルでは、圧縮後のシンボルを便宜的に英字で表しているが、実施形態1では、圧縮後のシンボルの値として、圧縮前のシンボルには存在し得ない値が登録される。換言すれば、圧縮後のシンボルは、圧縮前のシンボルが取り得る値の集合に属さない値である。これによって、データ解凍器20において、圧縮されたシンボルと圧縮されていないシンボルとを区別した解凍処理を行うことができる。

【0029】
例えば、ストリームデータが所定の文字コードが直列に並べられたテキストデータである場合には、圧縮前のシンボルとして2文字のペアが登録され、圧縮後のシンボルとしては当該文字コードにおいて未使用のビット列が登録される。また、例えば、ストリームデータが遺伝子データ(「A」、「G」、「T」及び「C」の核酸コード配列)である場合には、ルックアップテーブルの圧縮前の2シンボルとして、「A」、「G」、「T」及び「C」から2文字を取り出した順列が登録され、圧縮後の1シンボルとして、「A」、「G」、「T」及び「C」以外の値が登録される。

【0030】
実施形態に係るデータ圧縮器10及びデータ解凍器20には、静的に作成された同内容のエントリ群(シンボルペアリスト)を記憶したルックアップテーブルが備えられる。「静的に」とは、ルックアップテーブルの登録内容が、検索結果に応じて動的に変更(更新)されないことを意味する。但し、ルックアップテーブルの登録内容は、例えば随時の保
守作業や、周期的な更新作業によって変更され得る。また、シンボルペアは、ストリームデータにおける出現率が高い順(いわゆる尤度が高い順)で登録される。

【0031】
<<データ圧縮器の構成>>
図2に戻ってデータ圧縮器10は、上記したルックアップテーブル(以下、単に「テーブル」と表記することもある)の構成を前提として、テーブルでの検索対象となるシンボルペアを特定するための構成と、シンボルペアがテーブルに登録されているときに、シンボルペアを対応する1シンボル(「圧縮シンボル」と称する)に変換するための構成と、テーブルにおけるシンボルペアがヒットしたか否かに応じて元のシンボルペアと圧縮シンボルとの一方を出力する構成とを備える。

【0032】
具体的には、データ圧縮器10は、ストリームデータのような入力データを保持するラッチ110と、ルックアップテーブルが記憶された変換部に相当するメモリ101(読み書き回路含む)と、入力順にシンボルを出力するシリアライザ(マルチプレクサ:MUX)102と、圧縮シンボル又は元のシンボルペアを出力するための出力部に相当するセレクタ(マルチプレクサ)103と、出力データを保持するラッチ120とを含み、これらが信号線で接続されている。

【0033】
ラッチ110は、入力されたストリームデータを一時的に保持するバッファ機能を有する。ストリームデータは有限長のビット列であり、データ圧縮器10において、固定サイズ(1バイト)のシンボル単位で扱われる。ラッチ110は、ストリームデータの先頭から順に、所定タイミングで、シンボルペアを形成する、隣接した2つのシンボル(シンボル1,シンボル2)を並列に出力する。シンボルペアは、メモリ101とシリアライザ102とに入力される。

【0034】
メモリ101では、入力されたシンボルペアがテーブルから検索される。検索は、テーブル(図3)の各エントリに登録された“入力(圧縮前)”のシンボルペアと入力されたシンボルペアとのマッチングにより実行される。入力されたシンボルペアと一致する(マッチする)エントリが見つかった(ヒットした)場合)には、当該エントリに登録されている“出力(圧縮後)”のシンボル(圧縮シンボル)と、検索がヒットしたことを示すマッチ信号が出力される。圧縮シンボルは、セレクタ12へ入力され、マッチ信号はセレクタ103の制御信号としてセレクタ103に入力される。

【0035】
メモリ101として、例えば連想メモリ(CAM(Content Addressable Memory)を適用することができる。CAMは、入力されたデータワード(データ語)に対応するアドレスを出力することのできる高速検索用のコンピュータメモリである。CAMが適用される場合には、データワードとしてのシンボルペアがCAMに入力され、CAMはエントリがヒットしたときに、データワードに対応するアドレスとして圧縮シンボルを出力するとともに、真(True)信号(“1”信号)を出力する。True信号は、上記したマッチ信号として使用される。一方、エントリがヒットしなかった場合には、CAMからのアドレス(圧縮シンボル)の出力は行われず、偽(False)信号(“0”信号)の出力が行われる。

【0036】
シリアライザ(マルチプレクサ)102は、入力されたシンボルペアを、所定順序(シンボル1,シンボル2)でセレクタ103に出力することができる。セレクタ103は、マッチ信号が入力されたとき(True入力)に、元のシンボルペアと圧縮シンボルとのうち、圧縮シンボルを出力する。これに対し、マッチ信号が入力されないとき(False入力)に
は、シリアライザ102から出力された元のシンボルペアを出力する。セレクタ103の出力は、ラッチ120にて一時的に保持される。このような処理が、ストリームデータの先頭から順に繰り返されることで、ラッチ120には、元のストリームデータに対して圧縮処理が施された圧縮データが蓄積される。圧縮データは適宜のタイミングでラッチ12
0から出力され、伝送路3を介してデータ解凍器20へ送られる。

【0037】
なお、メモリ101は、CAMとRAM(Random Access Memory)との組合せであってもよい。この場合、CAMが出力するRAMのアドレスに圧縮シンボルが記憶され、当該アドレスの圧縮シンボルがセレクタ12に供給される。RAMはDRAMでもSRAMでも良いが、CAMとの連動に鑑み、高速動作が可能なものを選択するのが好ましい。

【0038】
図2に示したデータ圧縮器10において、メモリ101における動作は、「テーブル検索→ヒット判定→圧縮シンボル出力→True/False信号出力」のシーケンシャルな処理である。そして、テーブル検索は、シンボルペアと各エントリに格納されたシンボルペアとの1回のマッチングであり、従来技術のような、検索対象(入力シンボル列)を変更しての再度の検索処理は行われない。換言すれば、1回目の検索でエントリがヒットしたときに、ラッチ110から次のシンボルを得て再度の検索を行うことがない。従って、テーブル検索の所要時間(処理遅延)は、最長でも、シンボルペアと全エントリのシンボルペアとのマッチングを行う時間内に収まる。

【0039】
ヒット判定、圧縮シンボル出力、及びTrue/False信号出力の処理遅延はほぼ固定である。従ってメモリ101(CAM)における処理遅延が固定的になる。従って、メモリ101からの圧縮シンボル及びTrue/False信号の出力タイミングを固定化することができる。また、シリアライザ102及びセレクタ103での処理開始タイミングは、メモリ101からの圧縮シンボル及びTrue/False信号の出力タイミングに依存する。

【0040】
圧縮シンボル及びTrue/False信号の出力タイミングが固定されることで、シリアライザ102及びセレクタ103の処理開始タイミングも固定化できる。そして、シリアライザ102及びセレクタ103の処理遅延はほぼ一定である。従って、或るシンボルペアがラッチ110から出力されてから、圧縮シンボル又は元のシンボルペアがラッチ120に入力されるまでの所要時間(処理遅延)を固定化することができる。

【0041】
これによって、図2に示したデータ圧縮器10をハードウェア(ディジタル回路)で実現する(実装する)場合におけるタイミング調整が容易となり、ディジタル回路の簡易化を図ることができる。

【0042】
図4は、図2に示したデータ圧縮器10のディジタル回路で構成する場合の一例を示す。データ圧縮器10は、ルックアップテーブルを記憶するCAM101と、ストリームデータをシンボル単位で保持し、クロック信号に従って伝送するD-FF(D型フリップフロップ)111~D-FF113と、セレクタ103と、セレクタ103に出力されたシンボルを保持するD-FF121とを備えている。これらの各構成要素には、共通のクロック信号が供給され、クロック信号に従ったタイミングで同期した動作を行う。

【0043】
ストリームデータは、シンボル単位で、D-FF111に入力される。次のシンボルがD-FF111に入力される毎に、先に入力されたシンボルは、次段のD-FF112やD-FF113へ進んでいく。

【0044】
一方、CAM101には、イネーブル(有効化)信号又はディスエイブル(無効化)信号が交互に規則的に入力される。例えば、D-FF112から1番目のシンボルが出力され、D-FF111から2番目のシンボルが出力されるタイミングで、CAM101へイネーブル信号が入力される。イネーブル信号に基づき、CAM101は、1番目と2番目のシンボルペアを用いてルックアップテーブルを検索する(すなわち、圧縮を試みる)。

【0045】
次に、D-FF112から2番目のシンボルが出力され、D-FF111から3番目の
シンボルが出力されるタイミングでは、CAM101へディスエイブル信号が入力される。CAM101は2番目と3番目のシンボルペアについては圧縮を試みない。さらに、D-FF112から3番目のシンボルが出力され、D-FF111から4番目のシンボルが出力されるタイミングでは、CAM101へイネーブル信号が入力され、3番目と4番目のシンボルペアを用いて圧縮を試みる。実施形態1では、ストリームデータの先頭から順にシンボルを2つずつペアにして、圧縮を試みる。

【0046】
セレクタ103では、1番目のシンボルがD-FF113に保持されている間に、圧縮シンボルの入力(ヒットした場合)と、マッチ信号の入力とが行われる。マッチ信号の入力時には、D-FF121に対する圧縮シンボルがセレクタ103からD-FF121に入力される。一方、マッチ信号が入力されない場合には、セレクタ103は、1番目のシンボルと2番目のシンボルとを所定タイミングでD-FF121に入力する。

【0047】
その後、3番目と4番目、5番目と6番目のようなシンボルペアに関して、上記した1番目及び2番目のシンボルに対して説明した動作が繰り返し行われる。このように、直列接続された複数のD-FF上を、各シンボルが進んでいく間に、CAMによる圧縮処理(圧縮シンボルへの変換)が行われる簡易な回路構成を採用することができる。

【0048】
なお、図2に図示した、隣接するシンボル(シンボルペア)を伝送する並列な経路及びシリアライザ102を例示したが、図4に示すような、シンボルペアを直列に伝送するD-FFの多段回路を採用することで、並列な経路及びシリアライザ102を備えた場合と同様の(等価な)構成を採ることができる。

【0049】
以上のようなデータ圧縮器10によれば、シンボルペアを1つの圧縮シンボルに置き換えた分だけ、伝送路3を流れるデータ量を削減することができる。また、シンボル(すなわち、処理単位のデータサイズ)を固定長とすること等によって、データ圧縮器10における圧縮処理が簡素化され、且つ処理遅延が固定化されることで、大幅な遅延や揺らぎが生じるのを回避できる。このようにして、効率的なデータ伝送を行うことが可能になる。さらに、例えば、図4に示したようなパイプライン処理を行うハードウェアを容易に形成できる。

【0050】
<データ解凍器>
次に、図1に示したデータ解凍器20について説明する。図5は、データ解凍器20の一例を示すブロック図である。データ解凍器20は、圧縮シンボルと圧縮前の(元の)シンボルペアとを対応付けて記憶するメモリ201(読み書き回路含む)と、圧縮前のシンボルペアを2つのシンボルに分離する分離器(デマルチプレクサ:DMUX)202と、2つのシンボルを元のストリームデータの順に出力するシリアライザ203と、シリアライザ203を制御する信号を出力する1ビットカウンタ204と、当該データ解凍器20に入力されたシンボル又は復号されたシンボルペアを選択的に出力するセレクタ205とを有し、これらが信号線で接続されている。データ解凍器20は、所定のクロックに従って同期した動作を行う。

【0051】
まず、伝送路3からデータ解凍器20に入力されるストリームデータ(シンボル列)は、ラッチ200にて一時的に保持され、所定のタイミングでシンボル毎に出力される。出力されたシンボルは、データ解凍器20のメモリ201とセレクタ205とに入力される。

【0052】
メモリ201は、例えばRAMのような記憶装置である。メモリ201には、データ圧縮器10のメモリ101と対応するシンボルの組み合わせを登録しておく。すなわち、メモリ201は、図3に示したようなルックアップテーブルを記憶する。但し、メモリ20
1に記憶されるルックアップテーブルには、メモリ101に記憶されるルックアップテーブルの入力の値及び出力の値を入れ替えたエントリが登録される。例えば、メモリ201に記憶されるルックアップテーブルの入力の値には、データ圧縮機10のCAMが出力するアドレスが登録される。

【0053】
また、メモリ201は、テーブルの入力フィールドに入力されたシンボルを含むエントリが登録されている場合(すなわち、入力されたシンボルが圧縮シンボルである場合)には、当該エントリに登録された元の(圧縮前の)シンボルペアに置換して分離器202に出力する。

【0054】
分離器202は、シンボルペアを2つのシンボルに分割し、シリアライザ203に供給する。シリアライザ203は、シンボルペアをなす2つのシンボル(シンボル1,シンボル2)を、本来の並び順でセレクタ205へ出力する。データ解凍器20は、所定のタイミングで“1”又は“0”を出力する1ビットカウンタ204を有している。例えば、1ビットカウンタ204が“1”を出力しているときに、シリアライザ203からシンボル1が出力される。これに対し、1ビットカウンタ204が“0”を出力しているときに、シリアライザ203からシンボル2が出力される。カウンタ値とシンボルとの対応関係は逆でも良い。なお、メモリ201と205との経路は、図4に示したようなD-FFの直列回路に置換することができる。

【0055】
セレクタ205は、メモリ201から入力されたシンボルペア、又はラッチから出力されたシンボルとの一方を出力する。図5に示す例では、データ解凍器20は、メモリ201から分離器202へのデータ出力を検知する検知回路205Aを備えている。検知回路205Aは、メモリ201から読み出されるデータの信号線を監視しており、所定の監視タイミングにおいて、データの読み出しを検知した場合に、セレクタ205がシリアライザ203からのシンボルペアを出力するための制御信号(True信号に相当)をセレクタ205に供給する。これに対し、所定の監視タイミングでデータ出力が検知されないときには、セレクタ205がラッチ200からのシンボルを出力するための制御信号(False信
号に相当)をセレクタ205に与える。

【0056】
以上の構成によって、データ解凍器20は、ルックアップテーブルを用いて、圧縮シンボルを、元のシンボルペアに変換(復元)することができる。そして、解凍処理の処理遅延を固定的にすることができる。

【0057】
<データ圧縮/解凍システムの動作>
図6を用いて圧縮処理及び解凍処理の全体を説明する。図6において、データ圧縮/解凍システムは、送信側エンティティとしての送信側装置1と、データ圧縮器10と、受信側エンティティとしての受信側装置2と、データ解凍器20とを含む。送信側装置1及び受信側装置2のそれぞれは、例えば、通信機能を有する通信機器(端末装置、中継装置)であり、データ圧縮/解凍システムは、通信機器間の通信(「機器間通信」と称する)で転送されるデータを圧縮及び解凍する。

【0058】
また、送信側装置1及び受信側装置2は、例えば、通信機器に搭載されたプロセッサやLSI,ASIC,プログラマブルロジックデバイス(PLD(例えばFPGA))のような電子回路チップであり、データ圧縮/解凍システムは、チップ間の通信(いわゆる内部通信)で伝送されるデータを圧縮及び解凍する。伝送路3は、機器間通信の場合、機器間を有線又は無線で接続する通信回線であり、内部通信では、チップ間を接続する信号線である。

【0059】
メモリ101には、図3に示したようなルックアップテーブルが登録され、メモリ20
1には入出力の値が逆のテーブルが登録されている。最初に、送信側装置1からデータ圧縮器10へ、送信対象のストリームデータが出力される。ここで、ストリームデータが「abdaabaa」(右側が先頭)のようなシンボル列を含む場合を仮定する。

【0060】
データ圧縮器10は、メモリ101に登録されている圧縮前のシンボルペアを圧縮シンボルに置換して伝送路3へ出力する。ストリームデータ中の上記シンボル列は、ルックアップテーブルに基づいて、圧縮データ「TdaTS」に変換される。一方、データ解凍器20は、伝送路3を介して到着したストリームデータの中の圧縮シンボルを、圧縮前のシンボルペアに変換する。図6の例では、メモリ201が図示のようなテーブルを記憶しており、データ解凍器20での解凍処理によって、ストリーム中の圧縮データ「TdaTS」は、元の「abdaabaa」と変換(復元)される。

【0061】
〔実施形態2〕
以下、本発明の実施形態2について説明する。実施形態2は実施形態1と共通する構成を含むので、共通する構成については同一の符号を付して説明を省略し、主として相違点について説明する。

【0062】
実施形態1では、変換後のシンボルとして、変換前のシンボルが取り得る値の集合に属さない値をルックアップテーブルに登録していた。しかしながら、ストリームデータがバイナリデータである場合のように、変換前のシンボルがあらゆるビット列を取り得る場合では、圧縮シンボルとして変換されるシンボルの値が、ストリームデータに含まれないことは保証できない。すなわち、ストリームデータに含まれるシンボル値と、圧縮シンボルの値とが同じになることが起こり得る。

【0063】
実施形態2では、各シンボルに対し、シンボルが圧縮シンボルか否かを示すフラグ(識別子)を設定する。データ圧縮器は、シンボルと当該シンボルに対応するフラグとを出力し、データ解凍器は、フラグが対応シンボルが圧縮シンボルであることを示す場合に、対応シンボルを変換前のシンボルに置換する。フラグは、例えば1ビットのデータ(シンボルに付加される識別子ビットとの意で「付加ビット」とも呼ぶ)であり、例えば、ビット値“1”のときに圧縮シンボルであることを示し、ビット値“0”のときに非圧縮シンボルであることを示す。

【0064】
なお、シンボル及びフラグのそれぞれは、ストリームデータ中の順序を保つことにより、先頭から処理すれば自ずと対応付けられる。このようにすれば、データ解凍器において圧縮されたシンボルと圧縮されていないシンボルとを区別して解凍処理を行うことができる。

【0065】
図7は、実施形態2に係るデータ圧縮器の一例(データ圧縮器10a)を示すブロック図である。図2に示したデータ圧縮器10との相違は、メモリ101aから出力されるマッチ信号が、フラグとして扱われる点にある。すなわち、メモリ101aは、シンボルペアがテーブルにてヒットしたときに、フラグ“1”を出力し、ヒットしなかったときにフラグ“0”を出力する。フラグ“1”を示す信号は、実施形態1におけるマッチ信号としてセレクタ103の動作制御に使用される。

【0066】
図8は、データ圧縮器10aの機能を実現するディジタル回路構成の一例を示す。図4に示したデータ圧縮器10との相違点は、CAM101aから出力されるTrue/False信
号をラッチするD-FF122を備え、D-FF122からの出力値が、フラグ(付加ビット)として出力される。

【0067】
図9は、実施形態2に係るデータ解凍器(データ解凍器20a)の一例を示すブロック
図である。図5に示すデータ解凍器20との相違点は、データ圧縮器10a側から受信されたフラグ(付加ビット)がセレクタ205の制御信号として使用される点にある。データ圧縮器20aで生成される各付加ビット(フラグ)は、シンボル数に応じたビット数のビット列として、データ解凍器20aに伝達される。データ解凍器20aでは、ラッチ200からのシンボルの出力に応じて、対応するフラグ(付加ビット)がセレクタ205に入力される。これによって、フラグ値“1”の場合に、メモリ201から出力された復元後のシンボルペアをセレクタ205から出力することができる。逆に、フラグ値“0”の時に、ラッチ200から出力されたシンボルをセレクタ205から出力することができる。

【0068】
以上のように、実施形態2では、データ圧縮器10aにて、シンボル毎に圧縮/非圧縮を示すビット(フラグ)が生成され、データ解凍器20aへ送信される。これによって、データ解凍器20aは、フラグ値に応じた解凍処理を実行することが可能となる。したがって、例えばバイナリデータが圧縮される場合であっても、データ解凍器20aは、圧縮シンボルと非圧縮シンボルとを区別した解凍処理を実行できる。実施形態2に係る圧縮・解凍処理では、圧縮対象のデータの属性を問わない点で、実施形態1よりも汎用的である。

【0069】
〔実施形態3〕
以下、本発明の実施形態3について説明する。実施形態3は実施形態1及び2と共通する構成を含むので、共通する構成については同一の符号を付して説明を省略し、主として相違点について説明する。

【0070】
実施形態3では、実施形態2で説明したデータ圧縮器10a及びデータ解凍器20aをそれぞれ複数段直列に接続することで圧縮率を高めるようにした例を示す。図10は、データ圧縮器10bを多段接続した装置(データ圧縮装置とも呼ぶ)の一例を示す。図10に示すデータ圧縮装置は、直列に接続された4つのデータ圧縮器10bから形成される。但し、データ圧縮装置を形成するデータ圧縮器の数は適宜選択可能である。

【0071】
データ圧縮装置に含まれる複数のデータ圧縮器10b1~データ圧縮器10b4を、伝送路3から遠い順に1段目、2段目、・・・4段目と呼ぶ。1段目のデータ圧縮器10b1は、圧縮処理の結果として得られた圧縮シンボルを含むデータ列(圧縮データ(1))と、圧縮データ(1)を形成する各シンボルに対応するフラグ(付加ビット)が、シンボル順と一致する順序で並べられたビット列(第1フラグ列と称する)とが出力される。

【0072】
2段目のデータ圧縮器10b2では、データ圧縮器10b1からの圧縮データ(1)に対する圧縮処理によって得られた圧縮データ(圧縮データ(2))と、圧縮データ(2)に対応するフラグ群で形成されたビット列(第2フラグ列と称する)と、第1フラグ列とが出力される。

【0073】
3段目のデータ圧縮器10b3では、データ圧縮器10b2からの圧縮データ(2)に対する圧縮処理によって得られた圧縮データ(圧縮データ(3))と、圧縮データ(3)に対応するフラグ群で形成されたビット列(第3フラグ列と称する)と、第1フラグ列と、第2フラグ列とが出力される。

【0074】
4段目(図10の例における最終段)のデータ圧縮器10b4では、データ圧縮器10b3からの圧縮データ(3)に対する圧縮処理によって得られた圧縮データ(圧縮データ(4))と、圧縮データ(4)に対応するフラグ群で形成されたビット列(第4フラグ列と称する)と、第1~第3フラグ列とが出力される。これらの圧縮データ(4)及び第1~第4フラグ列が、伝送路を介してデータ解凍器側へ送信される。

【0075】
図11は、図10に示したデータ圧縮器10b2~10b4の構成例の説明図である。データ圧縮器10b1は、実施形態2で説明したデータ圧縮器10a(図7)と同じ構成を有するので説明を省略する。図11に図示された構成は、最終段(4段目)のデータ圧縮器10b4が備える構成を示す。

【0076】
図11において、データ圧縮器10b4は、データ圧縮器10aが備える構成に加えて、データ圧縮器10b4の入力ポートと出力ポートとを結ぶ3つの信号線131~133を含んでいる。信号線131は、上記した第1フラグ列の伝送用に使用され、信号線132は、第2フラグ列の伝送用に使用され、信号線133は、第3フラグ列の伝送用に使用される。信号線134には、第4フラグ列が出力される。

【0077】
3段目のデータ圧縮器10b3は、図11の構成を以下のように変形した構成を持つ。すなわち、図11に図示した信号線133が省略される。図11に図示した信号線134が信号線133として機能する。また、2段目のデータ圧縮器10b2では、図11に図示した信号線133及び132が省略される。そして、信号線134が信号線132として扱われる。なお、データ圧縮器10b1に関しては、図7に示した付加ビットを出力する信号線が、信号線131に相当する。

【0078】
図12は、データ解凍器20bを複数接続したデータ解凍装置の一例を示す。図12に示すデータ解凍装置は、図10に示したデータ圧縮装置に対応するものであり、4段のデータ解凍器20bから形成されている。伝送路3から遠い順に1段目、2段目、・・・n(n=4、nは自然数)段目と呼ぶ。

【0079】
4段目のデータ解凍器20b4は、伝送路3を介して、圧縮データ(4)及び第1~第4フラグ列を受信する。図12の例でも、シンボルの経路を太い矢印で示し、付加ビット(フラグ列)を細い矢印で示している。データ解凍器20b4は、第4フラグ列に基づいて圧縮データ(4)の解凍処理を実行し、圧縮データ(3)と第1~第3フラグ列を出力する。データ解凍器20b3は、第3フラグ列に基づいて圧縮データ(3)の解凍処理を実行し、圧縮データ(2)と第1及び第2フラグ列を出力する。データ解凍器20b2は、第2フラグ列に基づいて圧縮データ(2)の解凍処理を実行し、圧縮データ(1)と第1フラグ列とを出力する。最後に、データ解凍器20b1が、第1フラグ列に基づいて圧縮データ(2)の解凍処理を実行する。これによって、データ解凍器20b1(データ解凍装置)から元のストリームデータが出力される。

【0080】
図13は、実施形態3に係るデータ解凍器20b(20b2~20b4)の構成例を説明するブロック図である。図13に示すデータ解凍器20bの構成は、図12に示したデータ解凍装置の1段目に位置するデータ解凍器20b4の構成を示す。データ解凍器20b4は、データ解凍器20bの構成(図9)に加えて、データ圧縮器10b1~データ圧縮器10b3が出力した第1~第3フラグ列をデータ解凍器20b1~データ解凍器20b3へ伝送するための信号線211~213を有する。なお、ラッチ200には、圧縮データ(4)が入力され、信号線214には第4フラグ列が入力される。

【0081】
データ解凍器20b3は、図13に図示する構成から、信号線213を省略し、信号線214が213とされた構成を備える。データ解凍器20b2は、図13に図示する構成から、信号線213及び212を省略し、信号線214が212とされた構成を備える。そして、データ解凍器20b1は、図9と同じ構成を有し、付加ビットとして第1フラグ列が入力される。このように、ある段のデータ圧縮器によって圧縮された圧縮シンボルを、対応する段のデータ解凍器によって解凍するため、伝送路へ送信されるデータ量を削減しつつ、オリジナルデータに復号することができる。

【0082】
また、前段のデータ圧縮器の出力を、後段のデータ圧縮器がさらに圧縮するため、複数段のデータ圧縮器を経て伝送路3へ出力される転送データは、1段のデータ圧縮器を用いた場合よりも圧縮率が高くなる。例えば、実施形態2の場合、仮にすべてのシンボルペアを圧縮シンボルに置き換えたとしても、付加ビット(フラグ)の分だけデータは増加するため、圧縮率は50%以下にはなり得ない。複数段のデータ圧縮器を用いる場合、データサイズの観点では、1段増加するごとに圧縮率が向上し得る。また、複数段のデータ圧縮器又はデータ解凍器にわたってパイプライン処理を行うことができるため、処理速度の点でも有利である。

【0083】
なお、実施形態3では、実施形態2のデータ圧縮器10a及びデータ解凍器20aをそれぞれ複数段に接続したが、実施形態1に示したデータ圧縮器10及びデータ解凍器20をそれぞれ複数段接続するようにしてもよい。

【0084】
〔実施形態4〕
以下、本発明の実施形態4について説明する。実施形態4は実施形態1~3と共通する構成を含むので、共通する構成については同一の符号を付して説明を省略し、主として相違点について説明する。

【0085】
実施形態1~3では、ストリームデータの先頭から順に、2つのシンボルをペアにして圧縮するか否かを判断した。ここで、データストリームを2シンボルより長い或る長さの単位で見た場合、仮にデータストリームの異なる位置に同一の或る長さのシンボル列が出現する場合であっても、シンボルペアの区切り目が前後にずれた場合は、別のシンボルペアの列として処理される。

【0086】
ここで、例えばCAMに記憶されるルックアップテーブルに登録できるエントリの数には限界があるところ、何らかのルールに基づいて、同一のシンボル列は同一のシンボルペアに区切ることができれば、より少ないエントリで同一の或る長さのシンボル列を圧縮できる。すなわち、全体として圧縮率の向上が期待できる。実施形態4では、シンボル間の区切位置を決定する回路を含むデータ圧縮器を用いて、決定された各区切位置の先頭から2つずつのシンボルを組み合わせてシンボルペアにする。

【0087】
図14に、本実施の形態に係るデータ圧縮器10cのブロック図を示す。図14のデータ圧縮器10cは、入力データとしてのストリームデータを一時的に記憶するラッチ105と、メモリ101aと、シリアライザ102と、セレクタ103と、区切位置決定回路104とを有し、これらが信号線で接続されている。データ圧縮器10cは、図11に示したデータ圧縮器10bに、区切位置決定回路104を加えた構成になっている。ここでは、図11に示したデータ圧縮器10bとの差異を中心に説明する。

【0088】
区切位置決定回路104は、シンボル列の入力を受け、所定の条件に基づいてシンボル間の区切位置を決定する。実施形態4では、予め定められた優先度に基づいて隣接する4つのシンボルを比較し、区切位置を決定する。また、区切位置決定回路104は、入力されたシンボル列の順にシンボルを出力するとともに、区切位置を示す信号を出力する。また、シリアライザ13は、シンボルペアを、入力されたシンボル列と同じ順序で出力する。なお、実施形態4では、便宜的に、区切位置決定回路104までの部分を区切位置決定部と呼び、これ以降の部分を圧縮部と呼ぶ。圧縮部は、データ圧縮器10bと同様の構成を備える。

【0089】
実施形態4では、区切位置決定回路104は、例えば、シンボルが示す値の大小関係を用いて、予め定められた、連結する2シンボルの大小関係の優先度に基づき、シンボル間
の区切位置を決定する。具体的には、区切位置決定回路104は、シンボルが示すビット列を数値として扱い、隣接する2つのシンボルの大小を比較する。そして、数値が増加し続けている単調増加区間(「増加列」とも呼ぶ)、数値が減少し続けている単調減少区間(「減少列」とも呼ぶ)、又は数値が等しい区間(「等価列」とも呼ぶ)に分割し、区間の境界を区切位置とする。このとき、例えば「等価列」、「増加列」、「減少列」の順に優先順位を定め、区間の境界に位置するシンボルを優先順位の高い区間に組み入れるようにしてもよい。なお、区間に1つのシンボルしか含まれない場合は、例えば同様の優先順位に基づいて前後の区間に組み入れるようにしてもよい。

【0090】
以上をまとめると、本実施の形態では、次の2点のルールが予め定められている。
(1)文字の大小関係:a<b<c<d・・・
(2)区切目の優先順位:等価列>増加列>減少列

【0091】
このようなルールによれば、隣接する4つのシンボルを比較することによって区切位置を決定することができる。換言すれば、前後のシンボルを4つ保持するだけで当該区切位置決定処理を実行することができる。このため、回路構成の増大を抑えることができる。

【0092】
次に、区切位置決定回路104を含むデータ圧縮器およびこれに対応するデータ解凍器の実装例を説明する。図15は、図14に示した区切位置決定回路104の一例を示す回路構成図である。図15に示す区切位置決定回路104は、ストリームデータをシンボル単位で保持し、クロック信号に従って伝送するD-FF141a~141cと、2シンボルの大小関係を比較する比較器142a~142cと、比較結果を保持するQ-FF143a~143dと、比較結果に基づいて圧縮部のCAM101を有効化するタイミング(すなわち、ルックアップテーブルを検索するタイミング)を示す信号を出力するエンコーダ144とを有する。

【0093】
D-FF141a、D-FF141b、及びD-FF141cは、直列に圧縮部と送信側装置1との間を接続し、送信側装置1が出力したストリームデータをシンボル単位で圧縮部へ伝送する。比較器142aは、D-FF141aの出力とD-FF141bの出力と(すなわち、ある時点における、ストリームデータ中の隣接する1番目及び2番目のシンボル)を受け取り、シンボルの示す数値の関係を「増加(<)」、「等価(=)」又は「減少(>)」のいずれかで出力する。なお、「増加」、「等価」又は「減少」を示す信号として、例えばそれぞれ「1」、「2」又は「3」のような識別子を出力する。同様に、比較器142bは、D-FF141bの出力とD-FF141cの出力と(同様に、隣接する2番目及び3番目のシンボル)を受け取り、「増加」、「等価」又は「減少」のいずれかを出力する。また、比較器142cは、D-FF141cの出力と、区切位置決定部への新たな入力と(同様に、隣接する3番目及び4番目のシンボル)を受け取り、「増加」、「等価」又は「減少」のいずれかを出力する。なお、長さが1シンボルの区間を前後いずれかの区間に組み入れるようにしてもよい。

【0094】
比較器142a~比較器142cの出力は、それぞれQ-FF143a~Q-FF143cに保持される。さらに、Q-FF143a~Q-FF143cに保持された値および後述するQ-FF143dに保持される値は、エンコーダ144に入力される。Q-FF143dの入力はエンコーダ144の出力と接続され、1クロック前にエンコーダ144が出力した信号が保持されている。なお、エンコーダ144の出力が「TRUE」のタイミングで、後述する圧縮部ではシンボルペアをメモリから検索し、圧縮を試みる。

【0095】
図16に、エンコーダ144の入力と出力との組合せを示す。図16の表は、「入力」の列(「1・2番目」、「2・3番目」、「3・4番目」及び「前回の出力」)と、「出力」の列を有している。入力の各列は、対応するシンボルを比較する比較器における大小
関係を示している。「1・2番目」の列は、Q-FF143aに保持される大小関係に相当する。「2・3番目」の列は、Q-FF143bに保持される大小関係に相当する。「3・4番目」の列は、Q-FF143cに保持される大小関係に相当する。そして、エンコーダ144は、各比較器における大小関係が一致するレコードの「出力」列に記載された信号を出力する。

【0096】
1行目は、比較器142bに入力される2シンボルが等しく、エンコーダ144からの1クロック前の出力がFALSEの場合、前後のシンボルにかかわらず、当該クロックでのエンコーダ144からの出力がTRUEになることを表す。なお、入力列の「1・2番目」及び「3・4番目」に記載された「ANY」は、「<」、「>」及び「=」のいずれでもよいことを示している。2行目、3行目は、それぞれ、単調増加区間、単調減少区間であって、エンコーダ144からの1クロック前の出力がFALSEの場合に、当該クロックでのエンコーダ144からの出力がTRUEになることを表す。すなわち、等価区間、単調増加区間、単調減少区間においては、エンコーダ144の出力は1シンボルごとにTRUEとFALSEを繰り返し、区切位置決定部における2番目及び3番目のシンボルを、圧縮部においてシンボルペアとしてルックアップテーブルを検索して変換を試みる。また、4行目は、比較器142bに入力される2シンボルが単調増加区間の終わりに相当し、エンコーダ144からの1クロック前の出力がFALSEの場合、当該クロックでのエンコーダ144からの出力がTRUEになることを表す。5行目は、比較器142bに入力される2シンボルが単調増加区間の始まりに相当し、エンコーダ144からの1クロック前の出力がFALSEの場合、当該クロックでのエンコーダ144からの出力がTRUEになることを表す。6行目は、比較器142bに入力される2シンボルが、2つの単調減少区間の境界に位置する、長さが2シンボルの単調増加区間に相当し、エンコーダ144からの1クロック前の出力がFALSEの場合、当該クロックでのエンコーダ144からの出力がTRUEになることを表す。

【0097】
図16の例では、区切り目に当たるシンボルを組み入れる先を、「等価列>増加列>減少列」の優先順位に基づいて決定している。すなわち、1行目からわかるように、前後のシンボルとの大小に関係なく、等価列が最も優先的に連結され、区間を形成する。また、4~6行目からわかるように、減少列よりも増加列が優先して連結され、区間を形成する。このようなルールは一例であり、所定のルールに従って区切位置を決定すれば、同一のシンボル列を同一のシンボルペアに区切ることができる。

【0098】
図17を用いて、区切位置を決定する処理を説明する。例えば、図3に示したルックアップテーブルを用いて、図17のシンボル列1を圧縮する場合を説明する。

【0099】
シンボル列1には「bcdeacbdddabcdaaadc」という長いシンボル列が2つ含まれている(図17:シンボル列1の下線部)。実施形態4では、まずシンボル列の先頭を最初の区切位置として、シンボル列の先頭から2シンボルをシンボルペアにしてルックアップテーブルを検索する(図17:ステップS1)。ここで、S1に示すように、ルックアップテーブルにシンボルペアが登録されていなければ、変換はされない。また、区間の境界となる区切位置があれば、区切位置の次から2シンボルをシンボルペアとしてルックアップテーブルを検索する(図17:S2)。ここで、S2に示すように、ルックアップテーブルにシンボルペアが登録されていれば、変換シンボルに置換される。なお、図17の「cc」は等価区間、「bcde」は増加区間であり、これらの境界が区切位置となる。以降も同様にして、区切位置を検出しつつ、各区間の先頭からシンボルペアの変換を行う(図17:S3)。なお、図17では、これ以降の処理の説明は省略する。

【0100】
シンボル列1は、S1~S3の処理によって、図17のシンボル列2に示すような区切りが挿入された状態になる。シンボル列2が図3に示した内容のルックアップテーブルに
基づいて変換されると、図17のシンボル列3で示すような圧縮データになる。なお、図17では便宜的に区切り記号を記載しているが、ストリームデータに区切り記号を示すシンボルやビットが追加されるわけではない。

【0101】
シンボル列3で、シンボル列1に含まれていた2つの「bcdeacbdddabcdaaadc」は、それぞれ「VZ|U|b|Yd|TW|Sa|X」及び「TWe|Ub|Yd|TW|Sa|X」に変換されている。このように、複数の区間にわたってシンボル列が一致する場合、シンボル列が一致する複数の区間のうち、両端の区間以外は同じシンボルペアが生成される。図17の例では、シンボル列2中の2つのシンボル列において、最初の区間のシンボル列のそれぞれは、「cc」と「abcde」であり、両者は異なっている。同様に、最後の区間のシンボル列のそれぞれは、「dca」と「dcc」とであり、両者は異なっている。これに対し、これらの最初及び最後のシンボル列で挟まれた区間のシンボル列(シンボル2の斜体参照)は一致する。よって、当該挟まれた区間は、同一のロジックで変換されることになる(シンボル3の斜体参照)。

【0102】
一方、図3に示したルックアップテーブルを用いて、シンボル列1を先頭から2シンボルずつシンボルペアにして圧縮した場合(すなわち、実施形態1~3の場合)、図17のシンボル列4になる。

【0103】
シンボル列4は、シンボル列3よりも3シンボル分だけデータ量が多く、すなわち、圧縮率が悪い。換言すれば、同程度の圧縮率を達成するためには、ルックアップテーブルにより多くのエントリが必要になる。このように、実施形態4によれば、より少ないエントリ数で同一の長いシンボル列を圧縮できるため、全体として圧縮率を向上させることができる。

【0104】
実施形態4における圧縮部の回路構成は、図4、図8に示したものをそれぞれ採用することができる。より詳細には、図18に示すようにエンコーダの出力(CAMを有効化するための信号)は、タイミング合わせのディレイ回路(D-FF114~D-FF116)を経由してCAMへ入力される。また、実施形態4においては、例えば、図5、図9、図13と同様のデータ解凍器を採用することができる。

【0105】
実施形態4に示したデータ圧縮器及びデータ解凍器は、実施形態1~3の少なくとも一部と組み合わせることもできる。すなわち、付加ビット(フラグ)を用いずに、ルックアップテーブルには圧縮後のシンボルとして圧縮前のシンボルが取り得ない値を登録しておいてもよい。また、実施形態4に示すデータ圧縮器及びデータ解凍器をそれぞれ複数段接続するようにしてもよい。

【0106】
また、区切位置の決め方は上記の方法には限定されない。例えば、LCA(Lowest Common Ancestor:最少共通祖先)と呼ばれるアルゴリズムを用いて、効率のよいシンボルペアを特定して区切位置を決定してもよいし、その他の方法を用いてもよい。

【0107】
<変形例>
上記の実施形態では、2つのシンボルを1つのシンボルに圧縮したが、圧縮前のシンボルの組合せは2つには限られない。複数のシンボルを、それ未満の数のシンボルに置き換えるという構成であれば、データ圧縮器として機能する。ただし、ルックアップテーブルのエントリとストリームデータのシンボルペアとの一致率を向上させるという観点や、データの記憶容量を抑えるといった観点からは、2つのシンボルを1つのシンボルに圧縮するという態様が好ましいといえる。

【0108】
また、上記の実施形態では、1番目のシンボル及び2番目のシンボルのシンボルペアが
ルックアップテーブルに登録されていない場合、次の処理対象は3番目のシンボル及び4番目のシンボルとし、これらのシンボルペアがルックアップテーブルに登録されているか判断していた。ここで、1番目のシンボル及び2番目のシンボルのシンボルペアがルックアップテーブルに登録されていない場合、次の処理対象を2番目のシンボル及び3番目のシンボルのシンボルペアとしてもよい。このようにすれば、圧縮率の向上が期待できる。

【0109】
ルックアップテーブルのエントリは、圧縮対象のデータにおけるシンボルの出現尤度に基づいて変更するようにしてもよい。例えば、メモリがシンボルペアとエントリとの一致率を算出し、一致率が所定の閾値以下に下がった場合、ルックアップテーブルのエントリを更新するようにしてもよい。このとき、ルックアップテーブルのエントリは、送信側装置1及び受信側装置2に接続された管理装置が配布するようにしてもよい。例えば、圧縮対象のデータが、いわゆるミニブログのタイムラインである場合、時間の経過と共に投稿される話題が変化し、これに伴い圧縮対象として好ましいシンボルペアも変化する。シンボルペアとエントリとの一致率が所定の閾値以下になった場合、ルックアップテーブルのエントリを更新することで、圧縮率の低下を避けることができる。

【0110】
本発明に係るデータ圧縮器及びデータ解凍器は、例えば、ネットワークに接続されたコンピュータのネットワークインターフェイス(ネットワークカード)に設けてもよいし、複数のプロセッサを接続するバスの2点間に設けてもよい。ネットワークインターフェイスに設ける場合は、例えばイーサネット(登録商標)においてフレーム(MTU:Max Transmission Unit,パケットとも呼ぶ)に分割(フラグメント)する前の段階に設ける。
なお、フレーム内に、例えばシンボル列(圧縮データ)及び各段の付加ビット列(フラグ列)のそれぞれを識別可能な識別子を追加してもよい。識別子は、例えば、圧縮データ及び各フラグ列がフレーム上にマッピングされた際の位置情報のような、受信側で、多重された圧縮データ及びフラグ列を切り分け可能とする情報を含む。

【0111】
また、本発明に係るデータ圧縮器及びデータ解凍器は、いわゆるビッグデータの転送に適用してもよいし、特定の装置間でのデータのバックアップに適用してもよい。また、例えば、コンピュータウィルスのパターンデータとネットワークを流れるデータとをそれぞれ圧縮した状態で比較するような場合も、処理速度の向上が期待できる。

【0112】
ところで、上述した実施形態2では、データ圧縮器からは、シンボル列(圧縮データ)とフラグ列との2つのデータ系列が出力される。また、実施形態3では、シンボル列(圧縮データ)に加え、データ圧縮器の段数に応じた2以上のフラグ列が出力される。データ圧縮器から出力される圧縮データは、上記したように、伝送路3を介してデータ解凍器へ伝送される。このとき、データ圧縮器とデータ解凍器との間が並列な専用回線で接続される構成が採られる場合には、データ圧縮器が備える各出力ポートからの出力(各データ系列)をデータ解凍器に備えられた、各データ系列に対応する入力ポートに接続することができる。

【0113】
これに対し、データ圧縮器からの出力が、所定の伝送媒体(例えばMACフレーム)にマッピングされて伝送路3上を伝送される場合がある。このとき、圧縮データ及びフラグ列の伝送媒体へのマッピングは、データ圧縮器よりも下位に位置するレイヤのプロトコルに従う。この結果、データ解凍器側の下位レイヤが、圧縮データとフラグ列とが直列に接続されたデータ列を、データ解凍器の位置するレイヤ(「解凍レイヤ」と称する)に引き渡すことが起こり得る。この場合、解凍レイヤにおいて、圧縮データ及びフラグ列を適正なデータ解凍器の入力ポートに接続するために、圧縮データとフラグ列とを切り分ける(分離する)ことが要求される。このため、例えば以下のような構成が採られる。

【0114】
図19に、圧縮データとフラグ列とが直列に接続されたデータ列(ビット列)を、デー
タ解凍器においてデータ系列ごとに分離可能なデータフォーマットの一例を示す。図11及び図13に示したデータ圧縮器10b,データ解凍器20bを例に説明すると、データ圧縮器10dから出力される圧縮データ(4)及び第1~第4フラグ列の5つのデータ系列は、例えば、図示しないパラレル/シリアル変換器で、所定順序(例えば、圧縮データ,第1フラグ列,第2フラグ列,第3フラグ列,第4フラグ列)を有する1つのシリアルなデータ列に変換される。データ列は、1つのデータブロックとして扱われる。さらに、各データ系列のビット数が図示しないカウンタで計数され、計数結果に基づくヘッダが生成される。ヘッダは、例えばヘッダサイズと、データブロック中における各データ系列のサイズとを少なくとも含む。ヘッダ中のヘッダサイズ及びデータ系列のサイズは、例えば、固定長ビットで表現される(これにより、ヘッダサイズは固定長となる。なお、ヘッダサイズが固定長(解凍側にて既知)のとき、ヘッダにヘッダサイズを含めるのを省略できる)。このようなヘッダが、データブロックの前段にセットされて、下位レイヤに渡される。なお、ヘッダには、データサイズの代わりにオフセット(各データ系列の開始位置)及びデータブロックのサイズを記憶させるようにしてもよい。

【0115】
データ解凍器20b(図14)側では、データ解凍器の前段に、図示しないヘッダ解析回路が置かれる。ヘッダ解析回路は、下位レイヤからヘッダ及びデータブロックからなるデータ列(図19)を受け取り、ヘッダに格納された情報(ヘッダサイズ、各データ系列のサイズ)を参照して、データブロックを5つのデータ系列に分離する。図19の例では、ヘッダは固定長であり、ヘッダに後続するデータブロックの開始位置は決まっている。また、第1フラグ列の開始位置は、データブロックの先頭から圧縮データのサイズだけ後方になる。同様に、第2~第4フラグ列の開始位置も、圧縮データのサイズ及び第1~第3フラグ列のサイズを用いて求めることができる。また、データブロック全体のサイズは、圧縮データのサイズ及び第1~第4フラグ列のサイズの合計になる。このように、データ解凍器側は、各データ系列のオフセット及びサイズを求めることができ、データブロックを各データ系列に分離することができる。分離されたデータ系列の一つ(圧縮データ(4))は、ラッチ200へ入力(接続)される。また、第4フラグ列は、セレクタ205aに適宜のタイミングでフラグ値を供給するためのバッファ(図示せず)に蓄積される。第1~第3フラグ列は、後段に位置する他のデータ解凍器へ送られる。以上のように、解凍側で複数のデータ系列を分離するためのプロトコルが、圧縮側と解凍側との間で決められる。

【0116】
以上説明した実施形態1~4の構成は、適宜組み合わせることができる。
【符号の説明】
【0117】
10,10a,10b データ圧縮器
101,101a メモリ(CAM)
102 シリアライザ(マルチプレクサ)
103 セレクタ(マルチプレクサ)
104 区切位置決定回路
20,20a,20b データ解凍器
201 メモリ
202 分離器(デマルチプレクサ)
203,205 セレクタ
204 1ビットカウンタ
3 伝送路
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18