図面 (/)

技術 データ圧縮方法と、該方法を行う装置

出願人 三星電子株式会社
発明者 徐萬根金大旭孫弘樂孔駿鎭
出願日 2013年12月19日 (5年8ヶ月経過) 出願番号 2013-262636
公開日 2014年7月17日 (5年2ヶ月経過) 公開番号 2014-132750
状態 特許登録済
技術分野 圧縮、伸長・符号変換及びデコーダ
主要キーワード 直接距離 電子メモリ素子 各参照データ モバイルインターネット装置 遅延調節 期待寿命 バッファメモリコントローラ 以前データ
関連する未来課題
重要な関連分野

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

図面 (15)

課題

データ圧縮方法と、該方法を行う装置を提供する。

解決手段

データ圧縮方法は、以前データブロックと現在データブロックとを含む入力データストリームを受信する段階と、以前データブロックの一部と以前参照データブロックの一部とを比較する第1比較と、現在データブロックと現在参照データブロックとを比較する第2比較とを並列的に実行する段階と、第1比較と第2比較との結果に基づいて、現在データブロックを出力するか、または拡張データブロックを圧縮する段階と、を含み、拡張データブロックは、以前データブロックの一部と現在データブロックとを含む。

概要

背景

データ圧縮技術は、通信装置及び/またはデータ保存装置に、データの伝送速度を高め、装置の保存空間活用性を高めるために多様な方式で適用されている。
このデータ圧縮技術は、フラッシュメモリ装置基盤のデータ保存装置に保存されるデータのサイズを減らすことができるため、保存装置に対するライト回数及び/またはリード回数を減らすことができるだけではなく、保存装置の期待寿命を増加させることができる。

データ保存装置で使われるデータ圧縮方式として、無損失圧縮(loseless compression)方式と損失圧縮(lossy compression)方式とがある。無損失圧縮方式として、1977年と1978年とにAbraham LempelとJacob Zivとによって論文として公開された2つの無損失データ圧縮アルゴリズムであるLZ77とLZ78、Abraham Lempel、Jacob Ziv、及びTerry Welchによって創造された一般的な無損失データ圧縮アルゴリズムであるLZW、またはLempel−Ziv Ross Williams(LZRW)と呼ばれる無損失データ圧縮アルゴリズムが使われる。

概要

データ圧縮方法と、該方法を行う装置を提供する。データ圧縮方法は、以前データブロックと現在データブロックとを含む入力データストリームを受信する段階と、以前データブロックの一部と以前参照データブロックの一部とを比較する第1比較と、現在データブロックと現在参照データブロックとを比較する第2比較とを並列的に実行する段階と、第1比較と第2比較との結果に基づいて、現在データブロックを出力するか、または拡張データブロックを圧縮する段階と、を含み、拡張データブロックは、以前データブロックの一部と現在データブロックとを含む。

目的

本発明が解決しようとする技術的な課題は、データ圧縮加速化と、データ圧縮加速化時に失なわれるデータ圧縮率補償することができるデータ圧縮方法と、該方法を行う装置とを提供する

効果

実績

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

この技術が所属する分野

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

請求項1

以前データブロックと現在データブロックとを含む入力データストリームを受信する段階と、前記以前データブロックの一部と以前参照データブロックの一部とを比較する第1比較と、前記現在データブロックと現在参照データブロックとを比較する第2比較とを並列的に実行する段階と、前記第1比較と前記第2比較との結果に基づいて、前記現在データブロックを出力するか、または拡張データブロックを圧縮する段階と、を含み、前記拡張データブロックは、前記以前データブロックの前記一部と前記現在データブロックとを含むデータ圧縮方法

請求項2

前記現在参照データブロックが保存された第1メモリ領域と前記以前参照データブロックが保存された第2メモリ領域のそれぞれは、インターリービング方式で割り当てられ、独立してアクセス可能な互いに異なるメモリに具現される請求項1に記載のデータ圧縮方法。

請求項3

前記拡張データブロックのサイズと前記現在データブロックのサイズとの比は、帯小数である請求項1に記載のデータ圧縮方法。

請求項4

バッファメモリから前記以前参照データブロックの前記一部と前記現在参照データブロックとを並列的にリードする段階をさらに含む請求項1に記載のデータ圧縮方法。

請求項5

以前データブロックと現在データブロックとを含む入力データストリームを受信する段階と、メモリから以前参照データブロックの一部と現在参照データブロックとを並列的にリードする段階と、前記以前データブロックの一部と前記以前参照データブロックの前記一部とに対する比較と、前記現在データブロックと前記現在参照データブロックとに対する比較とを並列的に行う段階と、前記以前データブロックの前記一部と前記以前参照データブロックの前記一部とがマッチされ、前記現在データブロックと前記現在参照データブロックとがマッチされる時、拡張データブロックを圧縮する段階と、を含み、前記拡張データブロックは、前記以前データブロックの前記一部と前記現在データブロックとを含むデータ圧縮方法。

請求項6

前記データ圧縮方法は、前記以前データブロックの前記一部の少なくとも一部と前記以前参照データブロックの前記一部とがマッチされず、前記現在データブロックと前記現在参照データブロックとがマッチされない時、前記現在データブロックを選択的に圧縮または圧縮しない段階を含む請求項5に記載のデータ圧縮方法。

請求項7

前記メモリは、前記現在参照データブロックが保存された第1メモリ領域と前記以前参照データブロックが保存された第2メモリ領域とを含むバッファメモリであり、前記第1メモリ領域と前記第2メモリ領域のそれぞれは、インターリービング方式で割り当てられ、独立してアクセス可能な互いに異なるメモリに具現される請求項5に記載のデータ圧縮方法。

請求項8

第1メモリ領域、第2メモリ領域、及び第3メモリ領域を含むバッファメモリと、アドレス応答して、前記第1メモリ領域に保存された以前参照データブロックの一部と前記第2メモリ領域に保存された現在参照データブロックとを出力するバッファメモリコントローラと、以前データブロックの一部と前記以前参照データブロックの一部とがマッチするか否かと、現在データブロックと前記現在参照データブロックとがマッチするか否かとを判断し、該判断の結果によって、制御情報を生成する比較回路と、前記制御情報に基づいて、前記現在データブロックを出力するか、圧縮データを出力する圧縮データ生成回路と、を含み、前記圧縮データは、前記以前データブロックの前記一部と前記現在データブロックとを含む拡張データブロックを圧縮して生成されるデータ圧縮回路

請求項9

前記第1メモリ領域、前記第2メモリ領域、及び前記第3メモリ領域のそれぞれは、インターリービング方式で割り当てられ、独立してアクセス可能な互いに異なるメモリに具現される請求項8に記載のデータ圧縮回路。

請求項10

前記バッファメモリコントローラは、前記第1メモリ領域から前記以前参照データブロックの前記一部と、前記第2メモリ領域から前記現在参照データブロックとを並列的にリードした後、前記現在データブロックを前記第3メモリ領域にライトする請求項8に記載のデータ圧縮回路。

請求項11

前記バッファメモリコントローラは、前記アドレスを用いて、前記第1メモリ領域に対する第1アドレスと前記第2メモリ領域に対する第2アドレスとを生成するアドレス生成器と、前記第1アドレスを用いて、前記第1メモリ領域から前記以前参照データブロックの前記一部と、前記第2アドレスを用いて、前記第2メモリ領域から前記現在参照データブロックとを並列的にリードし、前記現在データブロックに対する第3アドレスに基づいて、前記現在データブロックを前記第3メモリ領域にライトするバッファメモリアクセス制御回路と、を含む請求項8に記載のデータ圧縮回路。

請求項12

前記比較回路は、前記以前データブロックの前記一部と前記以前参照データブロックの前記一部とがマッチするか否かと、前記現在データブロックと前記現在参照データブロックとがマッチするか否かとを並列的に判断する請求項8に記載のデータ圧縮回路。

請求項13

前記比較回路は、前記以前データブロックの前記一部を保存するレジスタと、前記レジスタから出力された前記以前データブロックの前記一部と前記バッファメモリコントローラから出力された前記以前参照データブロックの前記一部とがマッチするか否かを判断する第1比較器と、前記現在データブロックと前記現在参照データブロックとがマッチするか否かを判断する第2比較器と、前記第1比較器の出力信号と前記第2比較器の出力信号とに基づいて、前記マッチの有無を示すマッチ情報とマッチされたデータ長を示す長さ情報とを出力する長さ計算回路と、前記以前データブロックの前記一部に対するアドレスと前記現在データブロックに対するアドレスとに基づいて距離情報を出力する距離計算回路と、を含み、前記制御情報は、前記マッチ情報、前記長さ情報、及び前記距離情報を含む請求項8に記載のデータ圧縮回路。

請求項14

前記圧縮データ生成回路は、前記マッチ情報に基づいて選択信号を生成する選択信号生成回路と、前記長さ情報と前記距離情報とに基づいて、前記圧縮データを生成するコード生成回路と、前記選択信号に応答して、前記現在データブロックまたは前記圧縮データを出力する選択回路と、を含む請求項13に記載のデータ圧縮回路。

請求項15

データ保存装置と、以前データブロックと現在データブロックとを含むデータストリームを出力するホストと、前記ホストから出力された前記データストリームをデータブロック単位または拡張データブロック単位でマッチするか否かを判断し、該判断の結果によって、前記データストリームを前記データブロック単位または前記拡張データブロック単位で圧縮し、該圧縮されたデータを前記データ保存装置に出力するメモリコントローラと、を含み、前記メモリコントローラは、前記以前データブロックに対してマッチするか否かを判断した後、前記以前データブロックの一部と前記現在データブロックとを含む拡張データブロックに対してマッチするか否かを判断するデータ処理装置

請求項16

前記メモリコントローラは、第1メモリ領域、第2メモリ領域、及び第3メモリ領域を含むバッファメモリと、アドレスに応答して、前記第1メモリ領域に保存された以前参照データブロックの一部と前記第2メモリ領域に保存された現在参照データブロックとを並列的に出力するバッファメモリコントローラと、前記以前データブロックの前記一部と前記以前参照データブロックの前記一部とがマッチするか否かと、前記現在データブロックと前記現在参照データブロックとがマッチするか否かとを並列的に判断し、該判断の結果によって、制御情報を生成する比較回路と、前記制御情報に基づいて、前記現在データブロックを出力するか、前記拡張データブロックを圧縮して生成された前記圧縮データを出力する圧縮データ生成回路と、を含む請求項15に記載のデータ処理装置。

請求項17

前記第1メモリ領域、前記第2メモリ領域、及び前記第3メモリ領域のそれぞれは、インターリービング方式で割り当てられた互いに異なるアドレスを有する互いに異なるメモリに具現される請求項16に記載のデータ処理装置。

請求項18

前記バッファメモリコントローラは、前記アドレスを用いて、前記第1メモリ領域に対する第1アドレスと前記第2メモリ領域に対する第2アドレスとを生成するアドレス生成器と、前記第1アドレスを用いて、前記第1メモリ領域から前記以前参照データブロックの前記一部と、前記第2アドレスを用いて、前記第2メモリ領域から前記現在参照データブロックとを並列的にリードし、前記現在データブロックに対する第3アドレスに基づいて、前記現在データブロックを前記第3メモリ領域にライトするバッファメモリアクセス制御回路と、を含む請求項16に記載のデータ処理装置。

請求項19

前記比較回路は、前記以前データブロックの前記一部を保存するレジスタと、前記レジスタから出力された前記以前データブロックの前記一部と前記バッファメモリコントローラから出力された前記以前参照データブロックの前記一部とがマッチするか否かを判断する第1比較器と、前記現在データブロックと前記現在参照データブロックとがマッチするか否かを判断する第2比較器と、前記第1比較器の出力信号と前記第2比較器の出力信号とに基づいて、前記マッチの有無を示すマッチ情報とマッチされたデータ長を示す長さ情報とを出力する長さ計算回路と、前記以前データブロックの前記一部に対するアドレスと前記現在データブロックに対するアドレスとに基づいて距離情報を出力する距離計算回路と、を含み、前記制御情報は、前記マッチ情報、前記長さ情報、及び前記距離情報を含む請求項16に記載のデータ処理装置。

請求項20

前記圧縮データ生成回路は、前記マッチ情報に基づいて選択信号を生成する選択信号生成回路と、前記長さ情報と前記距離情報とに基づいて、前記圧縮データを生成するコード生成回路と、前記選択信号に応答して、前記現在データブロックまたは前記圧縮データを出力する選択回路と、を含む請求項19に記載のデータ処理装置。

請求項21

前記拡張データブロックのサイズと前記現在データブロックのサイズとの比は、整数ではない請求項15に記載のデータ処理装置。

請求項22

前記データ保存装置は、フラッシュメモリ、eMMC、UFSUSBフラッシュドライバ、またはSSDである請求項15に記載のデータ処理装置。

請求項23

前記データ処理装置は、スマートフォンタブレットPC、モバイルインターネット装置、または電子ブックである請求項15に記載のデータ処理装置。

技術分野

0001

本発明は、データ圧縮技術に係り、特に、データ圧縮加速化(data compression acceleration)と、データ圧縮加速化時に失なわれるデータ圧縮率(data compression ratio)を補償することができるデータ圧縮方法と、該方法を行う装置とに関する。

背景技術

0002

データ圧縮技術は、通信装置及び/またはデータ保存装置に、データの伝送速度を高め、装置の保存空間活用性を高めるために多様な方式で適用されている。
このデータ圧縮技術は、フラッシュメモリ装置基盤のデータ保存装置に保存されるデータのサイズを減らすことができるため、保存装置に対するライト回数及び/またはリード回数を減らすことができるだけではなく、保存装置の期待寿命を増加させることができる。

0003

データ保存装置で使われるデータ圧縮方式として、無損失圧縮(loseless compression)方式と損失圧縮(lossy compression)方式とがある。無損失圧縮方式として、1977年と1978年とにAbraham LempelとJacob Zivとによって論文として公開された2つの無損失データ圧縮アルゴリズムであるLZ77とLZ78、Abraham Lempel、Jacob Ziv、及びTerry Welchによって創造された一般的な無損失データ圧縮アルゴリズムであるLZW、またはLempel−Ziv Ross Williams(LZRW)と呼ばれる無損失データ圧縮アルゴリズムが使われる。

先行技術

0004

米国特許第6658148号公報
米国特許第7441156号公報
国際公開2007−138600号公報
米国特許出願公開第2004−0250009号明細書
米国特許出願公開第2007−0050514号明細書

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

0005

本発明が解決しようとする技術的な課題は、データ圧縮加速化と、データ圧縮加速化時に失なわれるデータ圧縮率を補償することができるデータ圧縮方法と、該方法を行う装置とを提供することにある。

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

0006

本発明の実施形態によるデータ圧縮方法は、以前データブロックと現在データブロックとを含む入力データストリームを受信する段階と、前記以前データブロックの一部と以前参照データブロックの一部とを比較する第1比較と、前記現在データブロックと現在参照データブロックとを比較する第2比較とを並列的に実行する段階と、前記第1比較と前記第2比較との結果に基づいて、前記現在データブロックを出力するか、または拡張データブロックを圧縮する段階と、を含み、前記拡張データブロックは、前記以前データブロックの前記一部と前記現在データブロックとを含む。

0007

前記現在参照データブロックが保存された第1メモリ領域と前記以前参照データブロックが保存された第2メモリ領域のそれぞれは、インターリービング方式で割り当てられ、独立してアクセス可能な互いに異なるメモリに具現される。前記拡張データブロックのサイズと前記現在データブロックのサイズとの比は、帯小数(mixed decimal)であり得る。
前記データ圧縮方法は、バッファメモリから前記以前参照データブロックの前記一部と前記現在参照データブロックとを並列的にリードする段階をさらに含む。

0008

本発明の実施形態によるデータ圧縮方法は、以前データブロックと現在データブロックとを含む入力データストリームを受信する段階と、メモリから以前参照データブロックの一部と現在参照データブロックとを並列的にリードする段階と、前記以前データブロックの一部と前記以前参照データブロックの前記一部とに対する比較と、前記現在データブロックと前記現在参照データブロックとに対する比較とを並列的に行う段階と、前記以前データブロックの前記一部と前記以前参照データブロックの前記一部とがマッチ(match)され、前記現在データブロックと前記現在参照データブロックとがマッチされる時、拡張データブロックを圧縮する段階と、を含み、前記拡張データブロックは、前記以前データブロックの前記一部と前記現在データブロックとを含む。

0009

前記データ圧縮方法は、前記以前データブロックの前記一部の少なくとも一部と前記以前参照データブロックの前記一部とがマッチされず、前記現在データブロックと前記現在参照データブロックとがマッチされない時、前記現在データブロックを選択的に圧縮または圧縮しない段階をさらに含む。
前記メモリは、前記現在参照データブロックが保存された第1メモリ領域と前記以前参照データブロックが保存された第2メモリ領域とを含むバッファメモリであり、前記第1メモリ領域と前記第2メモリ領域のそれぞれは、インターリービング方式で割り当てられ、独立してアクセス可能な互いに異なるメモリに具現される。

0010

本発明の実施形態によるデータ圧縮回路は、第1メモリ領域、第2メモリ領域、及び第3メモリ領域を含むバッファメモリと、アドレス応答して、前記第1メモリ領域に保存された以前参照データブロックの一部と前記第2メモリ領域に保存された現在参照データブロックとを出力するバッファメモリコントローラと、以前データブロックの一部と前記以前参照データブロックの一部とがマッチするか否かと、現在データブロックと前記現在参照データブロックとがマッチするか否かとを判断し、該判断の結果によって、制御情報を生成する比較回路と、前記制御情報に基づいて、前記現在データブロックを出力するか、圧縮データを出力する圧縮データ生成回路と、を含み、前記圧縮データは、前記以前データブロックの前記一部と前記現在データブロックとを含む拡張データブロックを圧縮して生成される。

0011

前記バッファメモリコントローラは、前記第1メモリ領域から前記以前参照データブロックの前記一部と、前記第2メモリ領域から前記現在参照データブロックとを並列的にリードした後、前記現在データブロックを前記第3メモリ領域にライトする。
前記バッファメモリコントローラは、前記アドレスを用いて、前記第1メモリ領域に対する第1アドレスと前記第2メモリ領域に対する第2アドレスとを生成するアドレス生成器と、前記第1アドレスを用いて、前記第1メモリ領域から前記以前参照データブロックの前記一部と、前記第2アドレスを用いて、前記第2メモリ領域から前記現在参照データブロックとを並列的にリードし、前記現在データブロックに対する第3アドレスに基づいて、前記現在データブロックを前記第3メモリ領域にライトするバッファメモリアクセス制御回路と、を含む。

0012

本発明の実施形態によるデータ処理装置は、データ保存装置と、以前データブロックと現在データブロックとを含むデータストリームを出力するホストと、前記ホストから出力された前記データストリームをデータブロック単位または拡張データブロック単位でマッチするか否かを判断し、該判断の結果によって、前記データストリームを前記データブロック単位または前記拡張データブロック単位で圧縮し、該圧縮されたデータを前記データ保存装置に出力するメモリコントローラと、を含み、前記メモリコントローラは、前記以前データブロックに対してマッチするか否かを判断した後、前記以前データブロックの一部と前記現在データブロックとを含む拡張データブロックに対してマッチするか否かを判断する。

0013

前記メモリコントローラは、第1メモリ領域、第2メモリ領域、及び第3メモリ領域を含むバッファメモリと、アドレスに応答して、前記第1メモリ領域に保存された以前参照データブロックの一部と前記第2メモリ領域に保存された現在参照データブロックとを並列的に出力するバッファメモリコントローラと、前記以前データブロックの前記一部と前記以前参照データブロックの前記一部とがマッチするか否かと、前記現在データブロックと前記現在参照データブロックとがマッチするか否かとを並列的に判断し、該判断の結果によって、制御情報を生成する比較回路と、前記制御情報に基づいて、前記現在データブロックを出力するか、前記拡張データブロックを圧縮して生成された前記圧縮データを出力する圧縮データ生成回路と、を含む。

0014

前記第1メモリ領域、前記第2メモリ領域、及び前記第3メモリ領域のそれぞれは、インターリービング方式で割り当てられた互いに異なるアドレスを有する互いに異なるメモリに具現される。
前記拡張データブロックのサイズと前記現在データブロックのサイズとの比は、整数ではない。前記データ保存装置は、フラッシュメモリ、eMMC(embedded MultiMedia Card)、UFS(Universal Flash Storage)、USBフラッシュドライバ、またはSSD(Solid−State Drive)である。前記データ処理装置は、スマートフォンタブレットPC、モバイルインターネット装置(mobile internet device)、または電子ブックである。

発明の効果

0015

本発明の実施形態によるデータ圧縮方法とデータ圧縮装置は、データブロック単位でデータブロックを圧縮することができるので、データ圧縮速度を増加させうるだけではなく、拡張データブロックを圧縮することができるので、圧縮率の減少を防止することができる。
本発明の実施形態によるデータ圧縮方法とデータ圧縮装置は、インターリーブされたメモリ、または互いに独立してアクセス可能なメモリを使って、拡張参照データブロックを処理するので、圧縮効率を向上させうる。本発明の実施形態によるデータ圧縮方法とデータ圧縮装置は、既に処理されたデータブロックの一部に対しても、以前参照データブロックの一部とマッチするか否かを判断することができるので、データ圧縮率またはデータ圧縮効率を向上させうる。

図面の簡単な説明

0016

本発明の実施形態によるデータ処理装置のブロック図。
本発明の他の実施形態によるデータ処理装置のブロック図。
本発明の他の実施形態によるデータ処理装置のブロック図。
図1Aに示されたデータ圧縮回路のブロック図。
図2に示されたハッシュキー生成回路のブロック図。
図2に示されたハッシュキー生成回路の動作を説明する概念図。
図2に示されたバッファメモリコントローラとバッファメモリのブロック図。
図2に示されたバッファメモリコントローラのブロック図。
図2に示された比較回路のブロック図。
図2に示された圧縮データ生成回路のブロック図。
図2に示されたデータ圧縮解除回路のブロック図。
本発明の一実施形態によるデータ圧縮方法を説明するフローチャート
本発明の他の実施形態によるデータ圧縮方法を説明するフローチャート。
図11に示されたデータ圧縮方法を説明する概念図。

実施例

0017

以下、添付した図面を参照して、本発明を詳しく説明する。
図1Aは、本発明の実施形態によるデータ処理装置のブロック図を示す。図1Aを参照すれば、データ処理装置100は、ホスト110、メモリコントローラ200、第1データ保存装置130、及び第2データ保存装置150を含む。
メモリコントローラ200と第1データ保存装置130は、1つのパッケージ、例えば、マルチチップパッケージ(multi−chip package)でパッケージング(packing)されうる。

0018

データ処理装置100は、PC(Personal Computer)、データサーバ、または携帯用電子装置(portable electronic device)として具現可能である。携帯用電子装置は、ラップトップコンピュータ(laptop computer)、携帯電話、スマートフォン(smart phone)、タブレット(tablet)PC、PDA(Personal Digital Assistant)、EDA(Enterprise Digital Assistant)、デジタルスチルカメラ(digital still camera)、デジタルビデオカメラ(digital video camera)、PMP(Portable MultimediaPlayer)、PND(Personal Navigation DeviceまたはPortable Navigation Device)、携帯用ゲームコンソール(handheld game console)、モバイルインターネット装置(mobile internet device)、または電子ブック(e−book)として具現可能である。

0019

ホスト110は、複数のデータブロックを含む入力データストリームIDSをメモリコントローラ200に出力することができる。データ圧縮を迅速に処理するために、複数のデータブロックのそれぞれは、N(Nは、2以上の自然数バイト(byte)単位で処理されうる。また、ホスト110は、メモリコントローラ200から出力された出力データストリームDDSを受信することができる。

0020

メモリコントローラ200は、データブロック単位で複数のデータブロックのそれぞれを処理、例えば、圧縮またはバイパス(bypass)することができる。また、圧縮率を向上させるために、メモリコントローラ200は、処理される現在データブロックと以前データブロックとの一部を含む拡張データブロックを圧縮することができる。例えば、拡張データブロックのサイズとデータブロックのサイズとの比は、帯小数、例えば、拡張データブロックのバイトサイズ(byte size)は、データブロックのバイトサイズよりも大きい。しかし、拡張データブロックのバイトサイズは、データブロックのバイトサイズの正確な倍数ではない。

0021

本明細書では、説明の便宜上、データブロックは、4バイトであり、拡張データブロックは、6バイトであると仮定するが、発明の概念は、処理されるバイトの数に限定されるものではない。
メモリコントローラ200は、ホスト110、第1データ保存装置130、及び第2データ保存装置150の間で送受信するデータ及び/または命令を対応するインターフェースプロトコル(interface protocol)によってインターフェーシング(inferfacing)または処理することができる。

0022

メモリコントローラ200は、ホストインターフェース210、データ圧縮回路(data compression circuit)230、CPU(または、プロセッサ)240、第1メモリコントローラ250、第2メモリコントローラ260、及びデータ圧縮解除回路(data de−compression circuit)270を含む。例えば、メモリコントローラ200は、システムオンチップ(system on chip:SoC)として具現可能である。

0023

ホストインターフェース210、例えば、ホストサイドインターフェース(host side interface)は、ホスト110とメモリコントローラ200との間で送受信するデータ及び/または命令をインターフェーシングする。
例えば、ホストインターフェース210は、データ圧縮動作の間には、ホスト110から出力された入力データストリームIDSをデータ圧縮回路230に伝送し、データ圧縮解除動作の間には、データ圧縮解除回路270から出力された圧縮解除されたデータストリームDDSをホスト110に伝送する。

0024

データ圧縮回路230は、CPU240の制御によって、データブロック単位でブロックデータを処理(例えば、圧縮またはバイパス)するか、または拡張データを処理(例えば、圧縮)することができる。したがって、データブロックまたは拡張データブロックを処理するデータ圧縮回路230は、圧縮処理を加速化しながらも、圧縮率低下を最小化することができる。データ圧縮回路230は、エンコーダの機能を行う。
CPU240は、データバス241を通じてデータ圧縮回路230、第1メモリコントローラ250、第2メモリコントローラ260、及びデータ圧縮解除回路270のうちの少なくとも1つの動作を制御することができる。

0025

第1メモリコントローラ250は、第1データ保存装置130のインターフェースプロトコルによって、メモリコントローラ200と第1データ保存装置130との間で送受信するデータ及び/または命令をインターフェーシングすることができる。例えば、第1データ保存装置130が、NANDフラッシュメモリである時、第1メモリコントローラ250は、NANDフラッシュメモリコントローラとして具現可能である。

0026

第2メモリコントローラ260は、第2データ保存装置150のインターフェースプロトコルによって、メモリコントローラ200と第2データ保存装置150との間で送受信するデータ及び/または命令をインターフェーシングすることができる。例えば、第2データ保存装置150が、DRAMである時、第2メモリコントローラ260は、DRAMコントローラとして具現可能である。

0027

データ圧縮解除回路270は、圧縮されたデータを圧縮解除し、この圧縮解除されたデータストリームDDSをホストインターフェース210を通じてホスト110に伝送しうる。データ圧縮解除回路270は、デコーダの機能を行う。
実施形態によって、第1データ保存装置130は、フラッシュ−基盤のメモリ、例えば、フラッシュメモリ、eMMC、UFS、USBフラッシュドライブ(USB flashdrive)、またはSSDであり得る。

0028

他の実施形態によって、第1データ保存装置130は、不揮発性メモリであり得る。この不揮発性メモリは、EEPROM(Electrically Erasable Programmable Read−Only Memory)、MRAM(Magnetic RAM)、スピン伝達トルクMRAM(Spin−Transfer TorqueMRAM)、Conductive bridging RAM(CBRAM)、FeRAM(Ferroelectric RAM)、PRAM(Phase change RAM)、抵抗メモリ(Resistive RAM:ReRAM)、ナノチューブRRAM(登録商標)(Nanotube RRAM)、ポリマーRAM(Polymer RAM:PoRAM)、ナノ浮遊ゲートメモリ(Nano Floating Gate Memory:NFGM)、ホログラフィックメモリ(holographic memory)、分子電子メモリ素子(Molecular Electronics Memory Device)、または絶縁抵抗変化メモリ(Insulator Resistance ChangeMemory)であり得る。

0029

さらに他の実施形態によって、第1データ保存装置130は、ハードディスクドライブ(Hard Disk Drive)であり得る。第2データ保存装置150は、DRAM(Dynamic Random Access Memory)またはDDR SDRAM(Double Data Rate Synchronous DynamicRandom Access Memory)であり得る。
例えば、第1データ保存装置130に/から入力/出力されるデータは、第2メモリコントローラ260の制御によって第2データ保存装置150に臨時保存することができる。

0030

図1B図1Cは、本発明の他の実施形態によるデータ処理装置のブロック図を示す。図1Aから図1Cに示したように、データ圧縮回路230及び/またはデータ圧縮解除回路270の設計位置は、実施形態によって多様に変更されうる。
例えば、図1Bで、データ圧縮回路230は、データバス241を通じてホストインターフェース210から入力データストリームIDSを受信し、データ圧縮解除回路270は、データバス241を通じてホストインターフェース210に出力データストリームDDSを出力する。図1Cで、データ圧縮回路230とデータ圧縮解除回路270は、データバス241と第1メモリコントローラ250との間に位置する。

0031

図2は、図1Aに示されたデータ圧縮回路のブロック図を示す。図2を参照すれば、データ圧縮回路230は、入力データレジスタ231、ハッシュキー(hash key)生成回路233、バッファメモリコントローラ237、バッファメモリ239、比較回路241、及び圧縮データ生成回路243を含む。
入力データレジスタ231は、入力データストリームIDSを受信し、入力データストリームIDSに含まれた複数のデータブロックのそれぞれの遅延(delay)を対応する遅延回路D1、D2、及びD3を用いて調節し、遅延調節された複数のデータブロックのそれぞれDATA2、DATA3、及びDATA4を複数の処理回路237、241、及び243のそれぞれに伝送する。

0032

各遅延回路D1、D2、及びD3の遅延は、各処理回路233、237、及び241の処理時間によって調節される。
入力データレジスタ231は、入力データストリームIDSに含まれたデータブロックDATA1をハッシュキー生成回路233に伝送し、第1遅延データブロックDATA2をバッファメモリコントローラ237に伝送し、第2遅延データブロックDATA3を比較回路241に伝送し、第3遅延データブロックDATA4を圧縮データ生成回路243に伝送する。遅延を無視すれば、各データブロックDATA1、DATA2、DATA3、及びDATA4は、同じデータブロックである。

0033

図3は、図2に示されたハッシュキー生成回路のブロック図を示す。図3を参照すれば、ハッシュキー生成回路233は、順次に入力される各データブロック(または、各データパターン)DATA1に対応するハッシュキーHiを生成し、この生成されたハッシュキーHiに該当するハッシュキーテーブル235のエントリ(entry)に前記各データブロックが存在する(または、保存された)バッファメモリ239に含まれた各保存領域の位置(position)またはアドレス(address)をライト(write)する。
ハッシュキー生成回路233は、ハッシュキー生成器233−1、第1カウンター233−2、及びハッシュキーテーブル235を含む。

0034

図4は、図2に示されたハッシュキー生成回路の動作を説明する概念図である。図3図4とを参照すれば、ハッシュキー生成器233−1は、1つのデータブロックを構成するL(Lは、自然数、説明の便宜上、本明細書で、L=4)バイト単位でハッシュキーHiを生成し、この生成されたハッシュキーHiをハッシュキーテーブル235に出力する。

0035

第1カウンタ233−2は、各データブロックDATA1に含まれた複数のバイトをバイト単位でカウントし、このカウントの結果によって、第1カウント値BCNTをハッシュキーテーブル235に出力する。
ハッシュキーテーブル235は、ハッシュキーHiによって指定されたエントリに第1カウント値BCNTを保存する。この際、第1カウント値BCNTは、アドレスADDに対応しうる。

0036

例えば、ハッシュキー生成器233−1は、第1処理ユニットPU1、すなわち、4バイト(A1A2A3A4)に相応するハッシュキーH0を生成し、カウンタ233−2は、4バイト(A1A2A3A4)の開始位置を指示する第1カウント値BCNTとしてOx00を生成する。
ハッシュキーテーブル235は、ハッシュキーH0によって指定されたエントリに第1カウント値BCNTまたはアドレスADD、すなわち、Ox00を保存する。この際、ハッシュキーテーブル235は、第1処理ユニット(PU1=A1A2A3A4)に対するアドレスADDとしてOx00を出力することができる。

0037

また、ハッシュキー生成器233−1は、次の4バイト(A2A3A4B5)に相応するハッシュキーH2を生成し、カウンタ233−2は、次の4バイト(A2A3A4B5)の開始位置を指示する第1カウント値BCNTとしてOx01を生成する。
ハッシュキー生成器233−1は、次の4バイト(A3A4B5B6)に相応するハッシュキーH4を生成し、カウンタ233−2は、4バイト(A3A4B5B6)の開始位置を指示する第1カウント値BCNTとしてOx02を生成する。ハッシュキー生成器233−1は、次の4バイト(A4B5B6B7)に相応するハッシュキーH6を生成し、カウンタ233−2は、4バイト(A4B5B6B7)の開始位置を指示する第1カウント値BCNTとしてOx03を生成する。

0038

ハッシュキー生成器233−1は、第2処理ユニットPU2、すなわち、4バイト(B5B6B7B8)に相応するハッシュキーH8を生成し、カウンタ233−2は、4バイト(B5B6B7B8)の開始位置を指示する第1カウント値BCNTとしてOx04を生成する。この際、ハッシュキーテーブル235は、第2処理ユニット(PU2=B5B6B7B8)に対するアドレスADDとしてOx04を出力することができる。

0039

ハッシュキー生成器233−1は、第3処理ユニットPU3、すなわち、4バイト(C1C2A3A4)に相応するハッシュキーを生成し、カウンタ233−2は、4バイト(C1C2A3A4)の開始位置を指示する第1カウント値BCNTとしてOx08を生成する。この際、ハッシュキーテーブル235は、第3処理ユニット(PU3=C1C2A3A4)に対するアドレスADDとしてOx08を出力することができる。

0040

ハッシュキー生成器233−1は、第4処理ユニットPU4、すなわち、4バイト(B1B2B3B4)に相応するハッシュキーH1を生成し、カウンタ233−2は、4バイト(B1B2B3B4)の開始位置を指示する第1カウント値BCNTとしてOx0Cを生成する。この際、ハッシュキーテーブル235は、アドレスADDとしてOx0Cを出力することができる。

0041

ハッシュキー生成器233−1は、第5処理ユニットPU5、すなわち、4バイト(C3C4A3A4)に相応するハッシュキーH7を生成し、カウンタ233−2は、4バイト(C3C4A3A4)の開始位置を指示する第1カウント値BCNTとしてOx40を生成する。この際、ハッシュキーテーブル235は、アドレスADDとしてOx40を出力することができる。

0042

第4処理ユニット(PU4=B1B2B3B4)と同一の第6処理ユニット(PU6=B1B2B3B4)が、ハッシュキー生成器233−1に入力されれば、ハッシュキー生成器233−1は、第4処理ユニットPU4に対するハッシュキーH1と同一のハッシュキーH1を生成し、カウンタ233−2は、第6処理ユニットPU6の4バイト(B1B2B3B4)の開始位置を指示する第1カウント値BCNTとしてOx44を生成する。

0043

この際、ハッシュキーテーブル235は、第6処理ユニット(PU6=B1B2B3B4)に対するアドレスADDとしてOx44を出力する代わりに、OxOCを出力する。この際、ハッシュキーH1に相応するエントリのアドレスADDは、Ox0CからOx44にアップデートされる。
処理される現在データブロックが、以前データブロックとマッチまたは同一である時、ハッシュキーテーブル235は、データブロック単位で生成されたハッシュキーHiに対応するアドレスADDをバッファメモリコントローラ237に出力することができる。

0044

図5は、図2に示されたバッファメモリコントローラとバッファメモリとのブロック図を示す。バッファメモリコントローラ237は、ハッシュキー生成回路233から出力されたアドレスADDに基づいて、互いに異なるメモリ239−1〜239−4のうちの何れか1つに保存された以前参照データブロックの一部とメモリ239−1〜239−4のうちの他の1つに保存された現在参照データブロックとを含む拡張参照データブロックMDATAと、拡張参照データブロックMDATAの開始位置を指示する拡張参照データブロック開始アドレスMDATA_ADDを比較回路241に伝送する。

0045

また、バッファメモリコントローラ237は、第1遅延データブロックDATA2の開始位置を指示するライトアドレスに応答して、第1遅延データブロックDATA2をインターリーブされた構造を有する複数のメモリ239−1〜239−4のうちの何れか1つにライトする。
バッファメモリ239は、インターリービング(interleaving)方式で割り当てられ、独立してアクセス可能な互いに異なる複数のメモリ239−1〜239−4を含む。複数のメモリ239−1〜239−4のそれぞれは、デュアルポート(dual−port)SRAMとして具現可能である。このデュアルポートSRAMは、シングルポート(single−port)SRAMと異なって、同一のサイクル内でリード動作ライト動作とを同時に行うことができる。

0046

バッファメモリコントローラ237が、インターリービング方式で割り当てられた互いに異なるアドレスを有する互いに異なる複数のメモリ239−1〜239−4を利用できるので、バッファメモリコントローラ237は、以前参照データブロックの一部と現在参照データブロックとを同時、または並列的にリード(read)することができる。

0047

図6は、図2に示されたバッファメモリコントローラのブロック図を示す。第1処理ユニットPU1、すなわち、最初データブロック(A1A2A3A4)が処理される過程が、図1Aから図8までを参照して詳しく説明される。
ハッシュキー生成回路233から第1処理ユニットPU1に対するハッシュキーH0に対応するデータブロック(A1A2A3A4)の開始位置を指示するアドレス(ADD=Ox00)が入力され、第1遅延データブロック(DATA2=A1A2A3A4)が入力データレジスタ231を通じて入力されれば、バッファメモリコントローラ237のアドレス生成器237−1は、現在参照アドレスADD_Cと直前(immediately previous;または、以前(previous))参照アドレスADD_Pとを生成する。

0048

この際、現在参照アドレスADD_Cは、ハッシュキー生成回路233から出力されたアドレス(ADD=Ox00)と同一であり、直前参照アドレスADD_Pは、すぐ隣接するメモリのメモリ領域のアドレスを示す。第1処理ユニットPU1のデータブロックが最初データブロックである時、直前参照アドレスADD_Pは、デフォルトとして設定されたアドレスであり得る。
図6の第2カウンタ237−2は、第1遅延データブロック(DATA2=A1A2A3A4)の開始位置をカウントし、第2カウント値(BCNT1=Ox00)を生成する。この際、第2カウント値BCNT1は、第1遅延データブロック(DATA2=A1A2A3A4)が保存されるメモリ領域のアドレスに相応する。

0049

図6では、第2カウンタ237−2が示されているが、実施形態によって、第2カウンタ237−2が具現されない場合、第2カウント値BCNT1の代わりに、図3の第1カウンタ233−2の第1カウント値(BCNT=Ox00)が、直接バッファメモリアクセス制御回路273−3に入力されうる。
バッファメモリアクセス制御回路273−3は、現在参照アドレス(ADD_C=Ox00)に対応する第1メモリ領域MR1に保存された現在参照データブロック、例えば、4バイト(X1X2X3X4)とデフォルトとして設定された直前参照アドレスADD_Pに対応するメモリ領域に保存された直前参照データブロックの一部、例えば、2バイトを並列的にリードする。ここで、直前参照データブロックは、デフォルトとして選択されたメモリ領域に保存されたデータブロックであり得る。

0050

次いで、バッファメモリアクセス制御回路273−3は、アドレス(ADD=Ox00)に対応する第1メモリ239−1の第1メモリ領域MR1に第1遅延データブロック(DATA2=A1A2A3A4)をライトする。したがって、現在参照データブロック(X1X2X3X4)は、第1遅延データブロック(DATA2=A1A2A3A4)にアップデートされる。

0051

バッファメモリアクセス制御回路273−3は、直前参照データブロックの一部と第1メモリ領域MR1に保存された現在参照データブロック(X1X2X3X4)とを含む拡張参照データブロックMDATA、例えば、6バイトを比較回路241に出力することができる。また、バッファメモリアクセス制御回路273−3は、拡張参照データブロックMDATAの開始位置を示す拡張参照データブロック開始アドレスMDATA_ADDを比較回路241に出力することができる。

0052

図7は、図2に示された比較回路のブロック図を示す。レジスタ301は、第2遅延データブロック(DATA3=A1A2A3A4)が入力される直前のデータブロックのうちの一部を保存する。第2遅延データブロック(DATA3=A1A2A3A4)が最初データブロックである時、レジスタ301に保存された2バイトは、デフォルトとして設定されたデータであり得る。

0053

第1比較器303は、レジスタ301に保存された2バイトPDATA1と直前参照データブロックの一部PDATAとを互いに比較し、この比較の結果によって、第1比較信号CP1を生成する。それと同時に、または並列的に、第2比較器305は、現在参照データブロック(RDATA=X1X2X3X4)と第2遅延データブロック(DATA3=A1A2A3A4)とを互いに比較し、この比較の結果によって、第2比較信号CP2を生成する。

0054

長さ計算回路311は、第1比較信号CP1と第2比較信号CP2とに基づいて繰り返しデータ(repeated data)の長さを示す長さ情報Match_LENとマッチするか否かを示すマッチ情報Match_FLAGとを生成する。
レジスタ301に保存された2バイトPDATA1と直前参照データブロックの一部PDATAとが互いに一致せず、現在参照データブロック(RDATA=X1X2X3X4)と第2遅延データブロック(DATA3=A1A2A3A4)とが互いに一致しないので、長さ計算回路311は、第1レベル、例えば、ハイレベルを有するマッチ情報Match_FLAGを出力することができる。この際、長さ計算回路311は、長さ情報Match_LENを生成しないこともある。

0055

距離計算回路309は、拡張参照データブロック開始アドレスMDATA_ADDと第3カウント値BCNT2とに基づいて拡張データブロックの相対的な位置、距離またはオフセット(offset)を示す距離情報Match_DISを生成することができる。実施形態によって、距離計算回路309は、マッチ情報Match_FLAGに基づいてイネーブルまたはディセーブルされうる。
第3カウンタ307は、第2遅延データブロック(DATA3=A1A2A3A4)の開始位置をカウントし、このカウントの結果によって、第3カウント値BCNT2を生成することができる。

0056

図7では、第3カウンタ307が別途に具現された例が示されているが、実施形態によって、第3カウンタ307が具現されない時、カウント値BCNT2の代わりに、図3に示された第1カウンタ233−2の第1カウント値BCNTが、直接距離計算回路309に入力されることもある。
圧縮データ生成回路243の動作を制御することができる制御情報COMPは、長さ情報Match_LEN、マッチ情報Match_FLAG、及び距離情報Match_DISを含む。

0057

図8は、図2に示された圧縮データ生成回路のブロック図を示す。圧縮データ生成回路243は、制御情報COMPと第3遅延データブロックDATA4とに基づいてLLD(literals and length/distance)データを生成することができる。
すなわち、圧縮データ生成回路243は、制御情報COMPに基づいて、処理される第3遅延データブロックDATA4が繰り返し(repeated)データブロックまたは繰り返しデータパターンであるか否かを判断し、この判断の結果によって、第3遅延データブロックDATA4を圧縮せず、そのまま出力するか、または第3遅延データブロックDATA4を含む拡張データブロックを圧縮することができる。

0058

この際、圧縮されていないデータブロックは、第1エンコーディング方式によって生成されたデータ、例えば、“リテラル(literal)データ”と言い、圧縮されたデータブロックまたは圧縮された拡張データブロックは、第2エンコーディング方式によって生成されたデータ、例えば、“長さ/距離データ”と言う。例えば、圧縮データ生成回路243は、有限状態マシン(finite state machine)として具現可能である。

0059

選択信号生成回路401は、マッチ情報Match_FLAGに応答して選択信号SELを生成する。例えば、マッチ情報Match_FLAGが第1レベルを有する信号である時、選択回路405は、第1レベルを有するマッチ情報Match_FLAGに応答して、第2遅延データブロック(DATA4=A1A2A3A4)を圧縮せず、そのまま出力する。したがって、リテラルデータ(A1A2A3A4)が出力データDATAOとして出力される。引き続き第2処理ユニットPU2のデータブロック(B5B6B7B8)が処理される過程が、図1Aから図8までを参照して詳しく説明される。

0060

ハッシュキー生成回路233から第2処理ユニットPU2のデータブロック(B5B6B7B8)の開始位置を指示するアドレス(ADD=Ox04)が入力され、第1遅延データブロック(DATA2=B5B6B7B8)が入力データレジスタ231を通じて入力されれば、アドレス生成器237−1は、現在参照アドレス(ADD_C=Ox04)と直前参照アドレス(ADD_P=Ox00)とを生成する。

0061

アドレス生成器237−1の具現例によって、直前参照アドレスADD_PとしてOx02が出力される時、バッファメモリアクセス制御回路237−3は、Ox02とOx03とに保存されたデータを読み取る。また、アドレス生成器237−1の具現例によって、直前参照アドレスADD_PとしてOx00が出力される時、バッファメモリアクセス制御回路237−3は、Ox02とOx03とに保存されたデータを読み取る。

0062

カウンタ237−2は、第1遅延データブロック(DATA2=B5B6B7B8)の開始位置をカウントし、このカウントの結果によって、第2カウント値(BCNT1=Ox04)、すなわち、ライトアドレスを生成する。
バッファメモリアクセス制御回路273−3は、現在参照アドレス(ADD_C=Ox04)に対応する第2メモリ239−2の第2メモリ領域MR2に保存された現在参照データブロック(X5X6X7X8)をリードすると同時に、直前参照アドレス(ADD_P=Ox00)に対応する第1メモリ239−1の第1メモリ領域MR1に保存された直前参照データブロック(A1A2A3A4)の一部、例えば、2バイト(A3A4)をリードする。

0063

そして、バッファメモリアクセス制御回路273−3は、ライトアドレス(BCNT1=Ox04、または実施形態によって、BCNT=Ox04)に応答して第2メモリ239−2の第2メモリ領域MR2に第1遅延データブロック(DATA2=B5B6B7B8)をライトする。したがって、第2メモリ領域MR2に保存された現在参照データブロック(X5X6X7X8)は、第1遅延データブロック(DATA2=B5B6B7B8)にアップデートされる。

0064

バッファメモリアクセス制御回路273−3は、第1メモリ領域MR1に保存された直前参照データブロック(A1A2A3A4)の一部(A3A4)と第2メモリ領域MR2に保存された現在参照データブロック(X5X6X7X8)とを含む拡張参照データブロック(MDATA=A3A4X5X6X7X8)、例えば、6バイトを比較回路241に出力する。また、バッファメモリアクセス制御回路273−3は、拡張参照データブロックMDATAの開始位置を示す拡張参照データブロック開始アドレス(MDATA_ADD=Ox02)を比較回路241に出力することができる。

0065

図7のレジスタ301は、第2遅延データブロック(DATA3=B5B6B7B8)が入力される直前の複数のデータブロック(A1A2A3A4)のうちの一部(A3A4)を保存する。
第1比較器303は、レジスタ301に保存された2バイト(PDATA1=A3A4)と直前参照データブロックの一部(PDATA=A3A4)とを互いに比較し、この比較の結果によって、第1比較信号CP1を生成する。それと同時に、または並列的に、第2比較器305は、現在参照データブロック(RDATA=X5X6X7X8)と第2遅延データブロック(DATA3=B5B6B7B8)とを互いに比較し、この比較の結果によって、第2比較信号CP2を生成する。

0066

長さ計算回路311は、第1比較信号CP1と第2比較信号CP2とに基づいて長さ情報Match_LENとマッチ情報Match_FLAGとを生成する。
レジスタ301に保存された2バイト(PDATA1=A3A4)と直前参照データブロックの一部(PDATA=A3A4)とが互いに一致し、現在参照データブロック(RDATA=X5X6X7X8)と第2遅延データブロック(DATA3=B5B6B7B8)とが互いに一致しないので、長さ計算回路311は、第1レベル、例えば、ハイレベルを有するマッチ情報Match_FLAGを出力する。

0067

距離計算回路309は、拡張参照データブロック開始アドレス(MDATA_ADD=Ox02)とカウント値(BCNT2=Ox04)とに基づいて距離情報Match_DISを生成する。上述したように、距離計算回路309が、マッチ情報Match_FLAGによってイネーブル(enable)またはディセーブル(disable)される時、距離計算回路309は、第1レベルを有するマッチ情報Match_FLAGに応答してディセーブルされうる。

0068

図8の選択回路405は、第1レベルを有するマッチ情報Match_FLAGに応答して第2遅延データブロック(DATA4=B5B6B7B8)を圧縮せず、そのまま出力する。すなわち、第2遅延データブロック(DATA4=B5B6B7B8)は、リテラルデータDATAOとして出力される。
第3処理ユニットPU3のデータブロック(C1C2A3A4)、第4処理ユニットPU4のデータブロック(B1B2B34B)、及び第5処理ユニットPU5のデータブロック(C3C4A3A4)が処理される過程は、第2処理ユニットPU2のデータブロック(B5B6B7B8)が処理される過程と実質的に同一または類似している。
したがって、各メモリ領域MR3、MR4、及びMR5に保存された各参照データブロックY1Y2Y3Y4、Y5Y6Y7Y8、及びZ1Z2Z3Z4は、各データブロックC1C2A3A4、B1B2B34B、及びC3C4A3A4にアップデートされる。

0069

図8の選択回路405は、第1レベルを有するマッチ情報Match_FLAGに応答して、各第3遅延データブロック(DATA4=C1C2A3A4、B1B2B34B、及びC3C4A3A4)を圧縮せず、そのまま出力する。すなわち、各第3遅延データブロック(DATA4=C1C2A3A4、B1B2B34B、及びC3C4A3A4)は、リテラルデータDATAOとして出力される。

0070

第6処理ユニットPU6のデータブロック(B1B2B3B4)が処理される過程が、図1Aから図8までを参照して詳しく説明される。
ハッシュキー生成回路233は、第6処理ユニットPU6のデータブロック(B1B2B3B4)に対するハッシュキーH1を生成し、この生成されたハッシュキーH1に対応するハッシュキーテーブル235のエントリに保存された第1カウント値BCNT、例えば、第4処理ユニットPU4のデータブロック(B1B2B3B4)の開始位置を指示するアドレス(ADD=Ox0C)をバッファメモリコントローラ237に出力する。

0071

そして、ハッシュキー生成回路233は、生成されたハッシュキーH1に対応するエントリに保存された第1カウント値BCNT、Ox0Cを第6処理ユニットPU6のデータブロック(B1B2B3B4)の開始位置を示す第1カウント値BCNT、Ox44にアップデートする。したがって、新たなデータブロック(B1B2B3B4)が入力されれば、ハッシュキー生成回路233は、アップデートされた第1カウント値BCNT、Ox44をアドレスADDとして出力する。

0072

バッファメモリコントローラ237のアドレス生成器237−1は、アドレス(ADD=Ox0C)に応答して、現在参照アドレス(ADD_C=Ox0C)と直前参照アドレス(ADD_P=Ox08)とを生成する。この際、カウンタ237−2は、第1遅延データブロック(DATA2=PU6=B1B2B3B4)の開始位置をカウントし、該カウントの結果によって、第2カウント値(BCNT1=Ox44)、すなわち、ライトアドレスを生成する。

0073

図6のバッファメモリアクセス制御回路273−3は、現在参照アドレス(ADD_C=Ox0C)に対応する第4メモリ領域MR4に保存された現在参照データブロック(B1B2B3B4)をリードすると同時に、直前参照アドレス(ADD_P=Ox08)に対応する第3メモリ領域MR3に保存された直前参照データブロック(C1C2A3A4)の一部、例えば、2バイト(A3A4)をリードする。

0074

そして、バッファメモリアクセス制御回路273−3は、ライトアドレス(ADD=Ox44)に応答して、第2メモリ239−2の第6メモリ領域MR6に第1遅延データブロック(DATA2=PU6=B1B2B3B4)をライトする。したがって、第6メモリ領域MR6に保存された現在参照データブロック(Z5Z6Z7Z8)は、第1遅延データブロック(DATA2=PU6=B1B2B3B4)にアップデートされる。

0075

バッファメモリアクセス制御回路273−3は、第3メモリ領域MR3に保存された直前参照データブロック(C1C2A3A4)の一部(A3A4)と第4メモリ領域MR4に保存された現在参照データブロック(B1B2B3B4)とを含む拡張参照データブロック(MDATA=A3A4B1B2B3B4)、例えば、6バイトを比較回路241に出力することができる。また、バッファメモリアクセス制御回路273−3は、拡張参照データブロックMDATAの開始位置を示す拡張参照データブロック開始アドレス(MDATA_ADD=Ox0A)を比較回路241に出力することができる。

0076

レジスタ301は、第2遅延データブロック(DATA3=PU6=B1B2B3B4)が入力される直前の複数のデータブロック(PU5=C3C4A3A4)のうちの一部(A3A4)を保存する。
第1比較器303は、レジスタ301に保存された2バイト(PDATA1=A3A4)と直前参照データブロックの一部(PDATA=A3A4)とを互いに比較し、この比較の結果によって、第1比較信号CP1を生成する。それと同時に、または並列的に、第2比較器305は、現在参照データブロック(RDATA=B1B2B3B4)と第2遅延データブロック(DATA3=PU6=B1B2B3B4)とを互いに比較し、この比較の結果によって、第2比較信号CP2を生成する。

0077

長さ計算回路311は、第1比較信号CP1と第2比較信号CP2とに基づいて長さ情報Match_LENとマッチ情報Match_FLAGとを生成する。
レジスタ301に保存された2バイト(PDATA1=A3A4)と直前参照データブロックの一部(PDATA=A3A4)とが互いに一致し、現在参照データブロック(RDATA=B1B2B3B4)と第2遅延データブロック(DATA3=PU6=B1B2B3B4)とが互いに一致するので、長さ計算回路311は、第2レベル、例えば、ローレベルを有するマッチ情報Match_FLAGを出力する。

0078

距離計算回路309は、拡張参照データブロック開始アドレスMDATA_ADDとカウント値BCNT2とに基づいて距離情報Match_DISを生成する。選択回路405は、第2レベルを有するマッチ情報Match_FLAGに応答して、コード生成回路403によって生成されたコード、すなわち、長さ/距離データを出力データDATAOとして出力する。

0079

コード生成回路403は、長さ情報Match_LENと距離情報Match_DISとに基づいて長さ/距離データ、例えば、圧縮データを生成する。したがって、選択回路405は、第5処理ユニットPU5に含まれた2バイト(A3A4)と第6処理ユニットPU6に含まれた4バイト(B1B2B3B4)とを含む拡張データ、すなわち、6バイトを出力する代わりに、コード、例えば、長さと距離とを示す圧縮データ([6,50])を出力する。

0080

本発明の実施形態によるデータ圧縮回路230は、データブロック単位で圧縮有無を判断してデータ圧縮速度を向上させうるだけではなく、拡張データを圧縮することができるので、圧縮率を向上させうる効果がある。
例えば、第1メモリコントローラ250は、データ圧縮回路230から出力されたデータDATAOの圧縮有無を示すフラグ(flag)を生成し、該生成されたフラグと共にリテラルデータまたは長さ/距離データを第1データ保存装置130に保存することができる。この際、リテラルデータまたは長さ/距離データは、第2データ保存装置150を通じて第1データ保存装置130に保存することができる。

0081

図9は、図2に示されたデータ圧縮解除回路のブロック図を示す。図9を参照すれば、データ圧縮解除回路270は、有限状態マシン(FSM)271、出力データ生成回路273、及び出力データバッファ275を含む。
有限状態マシン271は、圧縮データ、すなわち、リテラルデータと長さ/距離データとを含む圧縮データCDATAと圧縮有無を示すフラグとを含むヘッダHEADERを受信し、ヘッダHEADERに基づいて圧縮データCDATAの圧縮解除を指示する制御信号を出力する。

0082

出力データ生成回路273は、有限状態マシン271から出力された圧縮データCDATAと制御信号とに基づいて圧縮データCDATAに対する圧縮を解除し、圧縮解除されたデータストリームを出力データバッファ275に出力する。出力データバッファ275は、圧縮解除されたデータストリームDDSをホストインターフェース210に伝送する。

0083

図10は、本発明の一実施形態によるデータ圧縮方法を説明するフローチャートである。図1Aから図8まで、及び図10を参照すれば、データ圧縮回路230のバッファメモリコントローラ237は、ハッシュキー生成回路233から出力されたアドレスADDに基づいて互いに異なる複数のメモリ239−1〜239−4のそれぞれに保存された以前参照データブロックの一部と現在参照データブロックとを同時に読み取り、これら読み取られたデータを比較回路241に伝送する(ステップS110)。

0084

比較回路241は、以前参照データブロックの一部と以前データブロックの一部とを比較すると同時に、現在参照データブロックと現在データブロックとを比較する(ステップS120)。以前参照データブロックの一部と以前データブロックの一部とが互いにマッチングされ、現在参照データブロックと現在データブロックとが互いにマッチングされる時、圧縮データ生成回路243は、以前データブロックの一部と現在データブロックとを含む拡張データブロックを圧縮し、圧縮データ、すなわち、長さ/距離データを出力する(ステップS140)。
しかし、以前参照データブロックの一部と以前データブロックの一部とが互いにマッチングされ、現在参照データブロックと現在データブロックとが互いにマッチングされない時、現在参照データブロックを圧縮するか、またはバイパスすることができる(ステップS150)。

0085

上述したように、以前データブロックと以前参照データブロックとがマッチされず、現在データブロックと現在参照データブロックとがマッチされる時、データ圧縮回路230は、拡張参照データブロックをバッファメモリ239から同時にリードし、このリードされた拡張参照データブロックと拡張データブロックとを同時に比較し、この比較の結果に基づいて、拡張データブロックを圧縮することができる。
ここで、拡張参照データブロックは、以前参照データブロックの一部と現在参照データブロックとを含む。拡張参照データブロックのサイズと現在参照データブロックのサイズとの比は、整数ではない帯小数である。

0086

上述したように、データ圧縮回路230は、以前データブロックの繰り返し有無と現在データブロックの繰り返し有無とによって、(i)現在データブロックをリテラルデータとして出力するか、(ii)以前データブロックと現在データブロックとを圧縮して生成された長さ/距離データを出力するか、(iii)以前データブロックの一部と現在データブロックとを含む拡張データブロックを圧縮して生成された長さ/距離データを出力することができる。
拡張データブロックのサイズと現在データブロックのサイズとの比は、整数ではない帯小数である。

0087

図11は、本発明の他の実施形態によるデータ圧縮方法を説明するフローチャートであり、図12は、図11に示されたデータ圧縮方法を説明する概念図である。コーディング位置(coding position)を変更させながら、データブロックを圧縮する方法は、図1A図11、及び図12を参照して詳しく説明される。

0088

図12に示したように、コーディング位置CD1、CD2、及びCD3は、圧縮されるデータブロックの開始位置を意味する。データ圧縮回路230は、処理される現在データブロック(CDB=A3A4B1B2)と参照データブロックRDBとがマッチするか否か、または繰り返し有無を判断するために、第iコーディング位置CD1で現在データブロック(CDB=A3A4B1B2)と第1参照データブロック(RDB=A1A2A3A4)とがマッチするか否かをデータブロック単位で判断する(ステップS210)。ここで、iは、自然数であって、1から始め、Nは、自然数3であると仮定する。

0089

第iコーディング位置CD1でマッチングデータブロックが発見されない時(ステップS220)、すなわち、現在データブロック(CDB=A3A4B1B2)と第1参照データブロック(RDB=A1A2A3A4)とがマッチされない時、データ圧縮回路230は、第iコーディング位置CD1を第(i+1)コーディング位置CD2に変更する(ステップS230)。(i+1)が、Nよりも小さい時(ステップS250)、データ圧縮回路230は、第(i+1)コーディング位置CD2で現在データブロック(CDB=A3A4B1B2)と第2参照データブロック(RDB=B1B2B3B4)とがマッチするか否かをデータブロック単位で判断する(ステップS210)。

0090

第(i+1)コーディング位置CD2でマッチングデータブロックが発見されない時(ステップS220)、データ圧縮回路230は、第(i+1)コーディング位置CD2を第(i+2)コーディング位置CD3に変更する(ステップS230)。(i+1)が、Nよりも小さい時(ステップS250)、データ圧縮回路230は、第(i+2)コーディング位置CD3で現在データブロック(CDB=A3A4B1B2)と第3参照データブロック(RDB=A3A4B1B2)とがマッチするか否かをデータブロック単位で判断する(ステップS210)。

0091

第(i+2)コーディング位置CD3でマッチングデータブロックが発見される時(ステップS220)、データ圧縮回路230は、第3参照データブロック(RDB=A3A4B1B2)に基づいて現在データブロック(CDB=A3A4B1B2)を長さ/距離データに圧縮する(ステップS240)。しかし、第(i+2)コーディング位置CD3でもマッチングデータブロックが発見されない時(ステップS220)、データ圧縮回路230は、第(i+2)コーディング位置CD3を第(i+3)コーディング位置に変更する(ステップS230)。しかし、(i+1)が、Nよりも大きいので(ステップS250)、現在データブロック(CDB=A3A4B1B2)は、リテラルデータとして出力される(ステップS240)。

0092

本発明は、データ圧縮回路と、それを含む装置に使われる。

0093

100:データ処理装置
110:ホスト
130:第1データ保存装置
150:第2データ保存装置
200:メモリコントローラ
210:ホストインターフェース
230:データ圧縮回路
231:入力データレジスタ
233:ハッシュキー生成回路
237:バッファメモリコントローラ
239:バッファメモリ
241:比較回路
243:圧縮データ生成回路
240:CPU
250:第1メモリコントローラ
260:第2メモリコントローラ
270:データ圧縮解除回路

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

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

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

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

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

関連性が強い 技術一覧

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

関連性が強い人物一覧

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

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

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

関連する公募課題一覧

astavision 新着記事

サイト情報について

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

主たる情報の出典

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