(57)【要約】      （修正有）【課題】圧縮速度または復元速度を大きく低下させることなく、デジタル装置のメモリを効率よく使用するデータ圧縮装置および方法を提供する。【解決手段】データ圧縮装置が、探索範囲内のドメインブロックを探索し、探索されたドメインブロックとレンジブロックのデータを比較して差異値を発生し、差異値によるコストを生成する探索器と、探索器で選択されたコストのドメインブロックとの距離情報およびコスト情報をレンジブロックの圧縮データにコーディングするコーダーとから構成され、レンジブロックは圧縮対象データのブロックであり、ドメインブロックはレンジブロックとの比較対象データのブロックである。【選択図】図９
2011250431.tif 000002
【特許請求の範囲】
【請求項１】
圧縮装置において、
グローバルテーブルのインデックスを格納するコストテーブルをさらに備え、探索範囲内のドメインブロックを正方向に探索してレンジブロックと前記ドメインブロック間のコストを計算し、その後、計算されたコストと、前記探索範囲内のドメインブロックを逆方向探索して計算されたコストとを比較して、最小コストを生成し、前記コストテーブルに前記生成された最小コストを前記グローバルテーブルのインデックスに格納する探索器と、
前記グローバルテーブルを備え、前記コストテーブルに格納されたグローバルテーブルインデックスによる前記グローバルテーブルのデータを差異値に設定し、前記距離値を含む距離情報および前記差異値を含む差異情報を生成して前記レンジブロックの圧縮データにコーディングするコーダーと、から構成され、
前記正方向は、前記探索範囲において、最も距離が遠いブロックから前記レンジブロックへ向う方向であり、
前記逆方向検索は、１以上のブロックをグループ化して探索することを特徴とする圧縮装置。
【請求項２】
前記探索器で生成されたコストが前記テーブルインデックスを生成できない場合、例外処理フラグを生成し、
前記例外処理フラグの発生時、前記コーダーは前記例外処理フラグおよびレンジブロックデータを圧縮データにコーディングすることを特徴とする請求項１に記載の圧縮装置。
【請求項３】
前記グローバルテーブルに格納される差異値は、レンジブロックとドメインブロックの排他的論理和であることを特徴とする請求項２に記載の圧縮装置。
【請求項４】
前記探索器のコストテーブルがグローバルテーブルおよびローカルテーブルのインデックスを格納し、前記探索器が前記グローバルテーブルに存在しないコストの生成時、これを前記コストテーブルにローカルテーブルのインデックスに登録して、ローカルテーブルの対応するインデックスの位置に二つのブロックの差異値を格納し、
前記コーダーは、ローカルテーブルをさらに備え、前記グローバルテーブルインデックスまたはローカルテーブルインデックスによる前記グローバルテーブルまたはローカルテーブルのデータを差異値に設定し、前記差異値を含む距離情報および前記差異値を含む差異情報を生成して前記レンジブロックの圧縮データにコーディングすることを特徴とする請求項１に記載の圧縮装置。
【請求項５】
前記探索器で生成されたコストが前記テーブルインデックスを生成できない場合、例外処理フラグを生成し、
前記例外処理フラグの発生時、前記コーダーは前記例外処理フラグおよびレンジブロックデータを圧縮データにコーディングすることを特徴とする請求項４に記載の圧縮装置。
【請求項６】
前記グローバルテーブルおよびローカルテーブルに格納される差異値は、レンジブロックとドメインブロックの排他的論理和であることを特徴とする請求項５に記載の圧縮装置。
【請求項７】
データを圧縮する方法において、
グローバルテーブルと、前記グローバルテーブルのインデックスを格納するコストテーブルとを備え、
探索範囲内のドメインブロックを正方向に探索してレンジブロックと前記ドメインブロック間のコストを計算し、その後、計算されたコストと、前記探索範囲内のドメインブロックを逆方向探索して計算されたコストとを比較して、最小コストを生成し、前記生成された最小コストを前記コストテーブルにグローバルテーブルのインデックスに格納する探索ステップと、
前記グローバルテーブルのインデックスによる前記グローバルテーブルのデータを差異値に設定し、前記距離値を含む距離情報および前記差異値を含む差異情報を生成して前記レンジブロックの圧縮データにコーディングするコーディングステップと、からなり、
前記レンジブロックは圧縮対象データのブロックであり、ドメインブロックは前記レンジブロックと比較対象データのブロックであり、
前記正方向は、前記探索範囲において、最も距離が遠いブロックから前記レンジブロックへ向う方向であり、
前記逆方向探索は、１以上のブロックをグループ化して探索することを特徴とするデータ圧縮方法。
【請求項８】
前記探索ステップは、前記生成されたコストが前記テーブルインデックスを生成できない場合、例外処理フラグを生成し、
前記コーディングステップは、前記例外処理フラグの発生時、前記例外処理フラグおよびレンジブロックデータを圧縮データにコーディングすることを特徴とする請求項７に記載のデータ圧縮方法。
【請求項９】
前記グローバルテーブルに格納される差異値は、レンジブロックとドメインブロックの排他的論理和であることを特徴とする請求項８に記載のデータ圧縮方法。
【請求項１０】
可変データを格納するローカルテーブルと、前記ローカルテーブルのテーブルインデックスを格納するコストテーブルをさらに備え、
前記探索ステップは、前記グローバルテーブルに存在しないコストの生成時、これをコストテーブルにローカルテーブルのインデックスに登録し、前記ローカルテーブルに二つのブロックの差異値を格納し、
前記コーディングステップは、前記テーブルインデックスによる前記グローバルテーブルまたはローカルテーブルのデータを差異値に設定し、前記距離値を含む距離情報および前記差異値を含む差異情報を生成して前記レンジブロックの圧縮データにコーディングすることを特徴とするデータ圧縮方法。
【請求項１１】
前記探索ステップは、前記生成されたコストが前記テーブルインデックスを生成できない場合、例外処理フラグを生成し、
前記コーディングステップは、前記例外処理フラグの発生時、前記例外処理フラグおよびレンジブロックデータを圧縮データにコーディングすることを特徴とする請求項１０に記載のデータ圧縮方法。
【請求項１２】
前記グローバルテーブルに格納される差異値は、レンジブロックとドメインブロックの排他的論理和であることを特徴とする請求項１１に記載のデータ圧縮方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ圧縮装置および方法に関する。
【背景技術】
【０００２】
一般的に、メモリを使用するデジタルデータ処理装置は、メモリを効果的に使用するための多様な方法が用いられている。その一つの方法が、ライトモード時、データを圧縮してメモリに格納し、リードモード時、圧縮格納されたデータを復元する技術である。この場合、前記圧縮率を高めればメモリ効率は高まるが、圧縮速度および復元速度が低下してメモリアクセスタイムが長くなり、圧縮率を低くすればメモリアクセスタイムは短くできるが、メモリ効率が低下する。そのため、デジタル装置のメモリを効率よく使用するためには、高圧縮率および高速復元を満足する圧縮および復元方法が必要である。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】国際公開第２００６／０２８１５６号
【発明の概要】
【発明が解決しようとする課題】
【０００４】
一般的に、メモリを備えるデジタル装置において、圧縮率を高めるためには圧縮速度または復元速度を大きく低下させることになる。このような問題を解決するために、本発明の実施形態では、逆方向コーディング(ｂａｃｋｗａｒｄ ｃｏｄｉｎｇ)方法を用いて圧縮速度を大きく低下させずに圧縮率を高められる方法を提案する。また、よく使用される圧縮データをテーブルに格納し、コーディング時、テーブルを用いて圧縮データを生成することによって圧縮率を向上させる。また、マクロブロック単位の例外処理ブロックの調整によって圧縮率と復元速度の調整を可能にする。
【課題を解決するための手段】
【０００５】
本発明の実施形態に係るデータ圧縮方法は、マクロブロックのデータを正方向および逆方向コーディングしながら、圧縮速度を大きく低下させずに最小のコストを有するドメインブロックを探索して、圧縮率を向上させられる方法を提案する。また、テーブル(ｇｌｏｂａｌ ｔａｂｌｅ，ｌｏｃａｌ ｔａｂｌｅ等)に圧縮データを効率よく格納し、圧縮時によく発生するブロック差異値に対するコストを低く設定することによって格納されるデータの圧縮率を向上させられる方法を提案する。また、圧縮率のよくないマクロブロックは例外処理して圧縮率と復元速度の調整を可能にする方法を提案する。
【発明の効果】
【０００６】
本発明の実施形態に係るデータ圧縮装置および方法は、逆方向コーディング(ｂａｃｋｗａｒｄ ｃｏｄｉｎｇ)方法を用いて圧縮速度を大きく低下させずに圧縮率を高めることができ、また、よく使用される圧縮データをテーブルに格納し、コーディング時、テーブルを用いて圧縮データを生成することによって圧縮率を向上させることができ、圧縮効率のよくないブロックは例外処理ブロックとして処理し、圧縮率と復元速度の調整を可能にすることができる。
【図面の簡単な説明】
【０００７】
【図１】図１は、本発明の実施形態に係るレンジブロックおよびドメインブロックの構成を説明するための図面である。
【図２】図２は、本発明の実施形態に係る逆方向探索による圧縮効果を例示する図面である。
【図３ａ】図３ａは、本発明の実施形態に係る探索範囲内でドメインブロックを正方向および逆方向検索して、圧縮対象であるレンジブロックに対する最適のドメインブロックを選択する方法を説明するための図面である。
【図３ｂ】図３ｂは、本発明の実施形態に係る探索範囲内でドメインブロックを正方向および逆方向検索して、圧縮対象であるレンジブロックに対する最適のドメインブロックを選択する方法を説明するための図面である。
【図４】図４は、本発明の実施形態に係る圧縮方法(ｒａｎｇｅ ｂｌｏｃｋ ｅｎｃｏｄｉｎｇ)のステップを示すフロー図である。
【図５】図５は、前記図４における最適化ステップを行う動作を説明するための図面である。
【図６】図６は、前記図４における差異コーディングテーブルを更新するステップを示すフロー図である。
【図７ａ】図７ａは、本発明の実施形態に係るグローバルテーブルの特性を説明するための図面である。
【図７ｂ】図７ｂは、本発明の実施形態に係るローカルテーブルの特性を説明するための図面である。
【図８】図８は、本発明の実施形態に係る前記圧縮機の構成を示す図面である。
【図９】図９は、図８における前記探索器の動作を説明するための図面である。
【図１０】図１０は、図８における前記コーダーでレンジブロックのデータを圧縮するステップを示すフロー図である。
【図１１】図１１は、図１０のようなステップを行うコーダーが、距離情報および差異情報を用いて各レンジブロックのデータをコーディングするステップを具体的に示す図面である。
【発明を実施するための形態】
【０００８】
以下、本発明の好ましい実施形態を図面を参照しながら説明する。図面において、同一構成には、なるべく同一符号を付している。
【０００９】
下記の説明において、マクロブロックのビット数、ショートブロックの数およびビット数、距離情報および差異情報、テーブルの臨界値等のような具体例等といった特定詳細が本発明をより理解しやすくするために示されている。これらの特定詳細がなくても、また、これらの変形によっても本発明が容易に実施できるということは、この技術分野における通常の知識を有する者にとって自明なことである。
【００１０】
本発明の実施形態において、「マクロブロック(ｍａｃｒｏ ｂｌｏｃｋ)」とは、データを圧縮する最小単位を意味する。「ショートブロック(ｓｈｏｒｔ ｂｌｏｃｋ)」は、マクロブロックを構成する単位であって、２個以上から構成され、本発明の実施形態における前記ショートブロックは１６ビットのサイズを有すると仮定する。本発明の実施形態における前記マクロブロックは２個のショートブロックから構成されていると仮定する。「レンジブロック(ｒａｎｇｅ ｂｌｏｃｋ)」とは、圧縮しようとする一つ以上のマクロブロックを意味する。「ドメインブロック(ｄｏｍａｉｎ ｂｌｏｃｋ)」とは、レンジブロックを圧縮するために参照されるマクロブロックを意味する。「距離情報(ｄｉｓｔａｎｃｅ ｉｎｆｏｍａｔｉｏｎ)」は、レンジブロックとドメインブロックとの距離を意味する距離値(ｄｉｓｔａｎｃｅ ｖａｌｕｅ)および距離値の変更有無を表示する距離フラグ(ｄｉｓｔａｎｃｅ ｆｌａｇ)等を含む。距離フラグは、各マクロブロックに与えられ、レンジブロックの構成を表す。「差異情報(ｄｉｆｆｅｒｅｎｃｅ ｉｎｆｏｍａｔｉｏｎ)」は、レンジブロックとドメインブロック間のデータ差を意味する差異値(ｄｉｆｆｅｒｅｎｃｅ ｖａｌｕｅ)および差異値の存在有無を表示する差異フラグ(ｄｉｆｆｅｒｎｃｅ ｆｌａｇ)を含むことができる。ここで、データ差異とは、二つのブロックのデータを排他的論理和(ｅｘｃｌｕｓｉｖｅ ＯＲ，ＸＯＲ)した値を意味する。「コスト(ｃｏｓｔ)」は、前記差異値を計算して圧縮データとしてメモリに格納されるデータの長さ(ビット数)を決定する。「例外処理(ｅｘｃｅｐｔｉｏｎ ｈａｎｄｌｉｎｇ)」とは、圧縮率が高くない場合、データ圧縮をしない(ｒａｗ ｄａｔａをそのまま使用)ことを意味する。「グローバルテーブル(ｇｌｏｂａｌ ｔａｂｌｅ)」は、固定テーブル(ｆｉｘｅｄ ｅｎｔｒｙ ｔａｂｌｅ)であって、前記差異値(ｄｉｆｆｅｒｅｎｃｅ ｖａｌｕｅ)をインデックスにする。「ローカルテーブル(ｌｏｃａｌ ｔａｂｌｅ)」は、可変テーブル(ｆｌｏａｔｉｎｇ ｅｎｔｒｙ ｔａｂｌｅ)であって、圧縮中に発生頻度数の高いマクロブロックをインデックスにする。「探索範囲(ｓｅａｒｃｈｉｎｇ ｒａｎｇｅ)」とは、レンジブロックの位置でドメインブロックを探索するための範囲を意味する。「正方向コーディング(ｆｏｒｗａｒｄ ｃｏｄｉｎｇ)」とは、現在コーディングされる一つのマクロブロックから構成されたレンジブロックを最小のコストでコーディングするドメインブロックを探索範囲でコーディングすることを意味し、「逆方向コーディング(ｂａｃｋｗａｒｄ ｃｏｄｉｎｇ)」とは、現在コーディングされた一つのマクロブロックを含み、以前コーディングされたレンジブロックを再構成してコストを節減するためのコーディングを意味する。すなわち、前記正方向コーディングとは、圧縮機が、順次に選択される一つのマクロブロックから構成されるレンジブロックを一次的にコーディングすることを意味し、逆方向コーディングとは、現在コーディングしたマクロブロックを含み、以前コーディングされたレンジブロックを再構成して圧縮率を向上させることを意味する。「データ(ｄａｔａ)」とは、プログラムおよび使用者データを含む用語���あって、全てのデータを総称する意味として使われる。
【００１１】
本発明の圧縮機(ｃｏｍｐｒｅｓｓｏｒ)は、データを圧縮する時、圧縮するデータであるレンジブロックの長さを決定し、前記レンジブロックと同一、または、類似のデータを有するドメインブロックを探索し、前記レンジブロックと探索されたドメインブロック間の距離および差異をコーディングして圧縮する方法を提案する。ここで、データは、バイナリデータ(ｂｉｎａｒｙ ｄａｔａ)であってもよく、ファームウェア(ｆｉｒｍｗａｒｅ)およびソフトウェア(ｓｏｆｔｗａｒｅ)といったプログラムのコーディングデータを含む全てのデータであってもよい。
【００１２】
一般的に、データを圧縮する圧縮機および圧縮解除機(ｄｅｃｏｍｐｒｅｓｓｏｒ)は、高圧縮率および高速の復元機能を有するのが好ましい。ここで、圧縮機の圧縮率を高めれば、圧縮機の圧縮速度または圧縮解除機の復元速度が低下する。本発明は、前記探索範囲内でドメインブロックを探索する時、以下のような方法で圧縮率および復元速度を向上させる。
【００１３】
まず、圧縮機は、レンジブロックを探索範囲内のドメインブロックと比較する時、以前マクロブロックをコーディングする時に構成された検索対象(ｒｅｆｅｒｅｎｃｅ ｌｉｓｔ)に対し正方向および逆方向にコーディングして、探索範囲内で前記レンジブロックと最小差異値を有するドメインブロックとを選択する。
【００１４】
次に、レンジブロックと選択されたドメインブロック間の距離情報および差異情報を用いてレンジブロックのデータを圧縮する。本発明の実施形態では、圧縮方法は、第１に、二つのブロックの差異値をそのまま用いてデータを圧縮する方法、第２に、よく発生するブロックの差異値を実験的に測定してテーブルに登録し、圧縮時にこれを差異値にして圧縮する方法、第３に、よく発生するブロックの差異値を実験的に測定して固定テーブルに登録し、圧縮中によく発生するブロックの差異値を可変テーブルに登録し、圧縮時にこれを差異値にして圧縮する方法を使用することができる。
【００１５】
ここで、前記１番目の圧縮方法の差異値は、最小差異値を有するレンジブロックとドメインブロックとの排他的論理和値（ｅｘｃｌｕｓｉｖｅ ＯＲ ｏｐｅｒａｔｉｏｎ ｖａｌｕｅ)となる。また、２番目の圧縮方法のテーブルは、固定テーブルであって３番目の圧縮方法のグローバルテーブルとなる。
【００１６】
また、前記テーブルを用いる圧縮方法は、圧縮時、レンジブロックとドメインブロックとで頻繁に発生するブロックの差異値を実験的に測定し、前記測定された差異値によるコストを生成する。前記ブロック差異値をインデックスに使用し、当該インデックス位置に前記生成されたコストで差異値をコーディングする値を格納する。ここで、最も頻繁に発生するブロックの差異値を最小コストでマップすることでデータの圧縮率を向上させることができる。圧縮率をさらに向上させるため、全体頻度数によるグローバルテーブルと領域別頻度数によるローカルテーブルを設ける。ここで、前記グローバルテーブルは固定テーブルであって、前記圧縮機自体に備えることができ、また、圧縮時、メモリの特定位置に格納することもできる。前記ローカルテーブルは可変テーブルであって、圧縮機がデータを圧縮する際に、グローバルテーブルにはないが特定の領域に頻繁に発生するレンジブロックとドメインブロックとの差異値およびコストをテーブル化してメモリに格納することができる。ここで、前記グローバルテーブルは、圧縮前に予め設けられる固定テーブルであり、前記圧縮機がライトモード時に格納される全てのデータに適用されるテーブルとなる。前記ローカルメモリは可変テーブルであって、部分領域データの圧縮のみで使用されるテーブルとなる。
【００１７】
最後に、圧縮機は、マクロブロック単位のデータを圧縮し、探索範囲内でレンジブロックと同一、または、類似のドメインブロックがなければ、前記レンジブロックのデータを圧縮せずに例外処理する。すなわち、前記レンジブロックが探索範囲内の全てのドメインブロックと比較して同一のドメインブロック、または、類似のドメインブロックがない場合(例えば、複数のショートブロック中、少なくとも一つのショートブロックも同一でない場合)、前記レンジブロックの圧縮は、圧縮していない場合に比べてよくない。この場合、前記圧縮機は、該当するレンジブロックを例外ブロックとして処理し、例外処理フラグと共に当該レンジブロックのデータを圧縮せずにそのまま格納する。上記のように、例外処理ブロックを使用すれば、圧縮率および圧縮解除時の復元速度を向上させることができる。
【００１８】
しかし、上記のように、二つのブロックの差異値で圧縮する方法、または、グローバルテーブルを用いて圧縮する方法、または、グローバルテーブルおよびローカルテーブルを用いる圧縮方法を使用することができ、また、前記のような圧縮方法に例外処理機能を含ませて圧縮する方法を使用することができる。
【００１９】
以下、説明する本発明の実施形態は、グローバルテーブルおよびローカルテーブルを備え、例外処理圧縮方法を用いる場合を仮定して説明する。すなわち、以下、説明する本発明の実施形態では、本発明の実施形態に係るデータ圧縮方法は、マクロブロックのデータを正方向および逆方向コーディングしながら、圧縮速度を大きく低下させずに最も低いコストを有するドメインブロックを探索して圧縮率を向上させられる方法を提案する。また、テーブル(ｇｌｏｂａｌ ｔａｂｌｅ，ｌｏｃａｌ ｔａｂｌｅ等)に圧縮データを効率よく格納し、圧縮時によく発生するブロック差異値に対するコストを低く設定することによって格納されるデータの圧縮率を向上させられる方法を提案する。また、圧縮率のよくないマクロブロックは例外処理して圧縮率と復元速度の調整を可能にする方法を提案する。
【００２０】
図1は、本発明の実施形態に係るレンジブロックおよびドメインブロックの構成を説明するための図面である。
【００２１】
前記図1を参照すると、本発明の実施形態に係る圧縮機は、圧縮対象ブロックであるレンジブロックＲと参照ブロックであるドメインブロック間の距離(ｄｉｓｔａｎｃｅ＝レンジブロックとドメインブロックとの距離)を計算し、前記レンジブロックデータを前記ドメインブロックデータと比較してその差異(レンジブロックデータとドメインブロックデータとのＸＯＲ演算値)を計算した後、この二つの計算値(距離および差異)でレンジブロックの圧縮データを生成する。ここで、前記レンジブロックは一つ以上のマクロブロックから構成され、前記ドメインブロックのサイズは前記レンジブロックと同じサイズを有するブロックにすることができる。前記マクロブロックは、ショートブロックで分割(ｐａｒｔｉｔｉｏｎ)されるか、または、ショートブロックを使用しないこともある。以下、説明する本発明の実施形態では、前記図１に示すように、マクロブロックが２個のショートブロックから構成された場合を仮定して説明する。
【００２２】
本発明の実施形態では、前記マクロブロックは２個のショートブロックから構成され、前記ショートブロックは１６ビット(２ｂｙｔｅ)から構成されると仮定する。前記レンジブロックのドメインブロックは、前記レンジブロック以前の一定の範囲(すなわち、探索範囲)内にある同じサイズを有するマクロブロックにすることができる。ここで、前記レンジブロックは、互いに重なることなく整数(ｉｎｔｅｇｅｒ)単位で割当てられる(ａｌｉｇｎ)。また、ドメインブロックは互いに重なることもあり、ショートブロック単位(ショートブロックが８ビットであればバイト単位、１６ビットであれば２バイト単位)で割当てられる。例えば、圧縮するデータが５個のマクロブロック(ＭＢ０−ＭＢ４)であり、ショートブロックの番号がＳＢ０−ＳＢ９である場合、前記レンジブロックはＳＢ０−ＳＢ１，ＳＢ２−ＳＢ３，ＳＢ４−ＳＢ５，．．．，ＳＢ８−ＳＢ９の順に割当てられる。また、前記レンジブロックがＳＢ８−ＳＢ９である場合、前記ドメインブロックはＳＢ６−ＳＢ７，ＳＢ５−ＳＢ６，ＳＢ４−ＳＢ５，．．．，ＳＢ１−ＳＢ２，ＳＢ０−ＳＢ１で割当てられる。前記レンジブロックの圧縮は、前記ドメインブロックの距離情報および差異情報から構成され、この時、選択されるドメインブロックは、探索範囲内で前記レンジブロックと最も低いコストの距離情報および差異情報を有するドメインブロックとなる。
【００２３】
前記距離は、レンジブロックと選択されたドメインブロック間の離隔距離を意味し、各レンジブロックの圧縮データに用いられるため圧縮率に大きい影響を及ぼす。そのため、前記距離は、一定のサイズに制限して使用するのが好ましく、前記設定された距離によって前記探索範囲が決定される。また、前記レンジブロックの長さが長ければ距離に使用するビットは節減されるが、差異値を表すビット数が増加し、これによって前記レンジブロックの長さも圧縮率に大きな影響を及ぼす。前記情報の圧縮を効果的にするためには、前記探索範囲(差異のビット数)およびレンジブロックの長さを適宜に設定しなければならない。
【００２４】
また、本発明の実施形態では、前記レンジブロックを圧縮する時、正方向および逆方向コーディング方法を用いて短時間で最適(ｎｅａｒ ｏｐｔｉｍｕｍ ｓｏｌｕｔｉｏｎ)にドメインブロックを探索する方法を提案する。本発明の実施形態では、マクロブロックを圧縮する時、マクロブロックを圧縮するコスト(ｃｏｓｔ)を最小にした後、後方向に、マクロブロックを含みすでに圧縮されたマクロブロックのコストが最小になるよう更新(ｕｐｄａｔｅ)する。すなわち、本発明の実施形態では、探索範囲内で正方向(前方向)のマクロブロックを探索してコストが最小になるよう圧縮し、その後、再び後方向(逆方向)にすでに圧縮されたマクロブロックのコストを確認してドメインブロックの長さおよび距離を調整する。
【００２５】
図２は、本発明の実施形態に係る逆方向コーディングによる圧縮効果を例示する図面である。
【００２６】
本発明の実施形態では、逆方向に現在圧縮するマクロブロックを含みすでに圧縮されたマクロブロックに対し、距離コスト(ｄｉｓｔａｎｃｅ ｃｏｓｔ)と差異コスト(ｄｉｆｆｅｒｅｎｃｅ ｃｏｓｔ)が最適化されるレンジブロックサイズ(ｒａｎｇｅ ｂｌｏｃｋ ｓｉｚｅ)ｋを求める。この場合、一般的方法は、レファレンスブロック(ｒｅｆｅｒｅｎｃｅ ｂｌｏｃｋ)と一致しないマクロブロックは同じレンジブロックに属さない。しかし、本発明の実施形態に係るマクロブロックがドメインブロックと同じでない場合でもレンジブロックに属するようにする。
【００２７】
前記図２のような場合、レンジブロックを３個にしてコストＴ＝ｃｏｓｔ(Ａ，Ａ)＋ｃｏｓｔ(Ｘ，Ｙ)＋ｃｏｓｔ(Ｂ，Ｂ)にならなければならないが、本発明の実施形態では、レンジブロックを１個にしてコストＵ＝ｃｏｓｔ(ＡＸＢ，ＡＹＢ)となる。この場合、コストＴは、少なくとも二つの距離値を有する一方、コストＵは一つの距離値を有する。従って、ＸとＹとが同じでなくてもＸとＹとの差異値をコーディングしたｃｏｓｔ(Ｘ，Ｙ)は、小さい値を有することができるため、Ｕ＜Ｔが可能である。前記図２において、マクロブロックＸがレファレンスブロックＹと同じでない場合でも、同じレンジブロックに属することができる。
【００２８】
図３ａおよび図３ｂは、本発明の実施形態に係る探索範囲内でドメインブロックを正方向および逆方向コーディングして圧縮対象であるレンジブロックに対する最適のドメインブロックを選択する方法を説明するための図面である。前記圧縮機は、レンジブロックが設定されれば、探索範囲内に存在するドメインブロックを正方向および逆方向コーディングしてコストの最も低いドメインブロックを選択した後、前記選択されたドメインブロックとレンジブロック間の距離およびコストを圧縮データに生成する。図３ａは、本発明の実施形態に係る正方向コーディングの実行ステップを説明するための図面であり、図３ｂは、本発明の実施形態に係る逆方向コーディングの実行ステップを説明するための図面である。ここで、前記レンジブロックはＢ，Ｃ[２６，２７](２６および２７番目ショートブロック)であり、探索範囲は[１０，１１，１２，．．．，２５](１０番ショートブロックから２５番ショートブロック)の場合を仮定して説明する。
【００２９】
前記図３ａおよび図３ｂを参照すると、前記レンジブロックＢ，Ｃ[２６:２７]に対する正方向コーディングは、探索範囲内のドメインブロックを順次に選択し、前記選択されたドメインブロックと前記レンジブロックＢ，Ｃ[２６，２７]のショートブロックデータを比較する。ここで、前記圧縮機は、正方向コーディングを行いながら前記レンジブロックの前に位置する探索範囲内のドメインブロックとの距離および差異値を計算する。その後、前記圧縮機は、前記逆方向コーディングを行いながら前記計算された距離および差異値を分析して比較されたドメインブロック中、前記レンジブロックと距離が最も近くて差異値の小さいドメインブロックを選択する。すなわち、前記図３ａのような場合、前記圧縮機は、正方向および逆方向コーディングを行いながら、前記レンジブロックＢ，Ｃ[２６:２７]と最も類似していて距離の近いドメインブロックＢ，Ｃ[２０:２１]を探す。ここで、ドメインブロックＢ，Ｃ[１４:１５]は、差異値ではドメインブロックＢ，Ｃ[２０:２１]と同じコストを有するが、距離コストがより大きいためドメインブロックＢ，Ｃ[２０:２１]が選択され、これに関する距離情報と差異値とが格納される。この場合、前記圧縮機は、前記レンジブロックＡ，Ｂ[２２，２３]は、距離値が４で差異値が０のドメインブロック(Ａ，Ｂ[１８，１９])を選択し、レンジブロックＥ，Ｆ[２４，２５]は、距離値が８で差異値が０のドメインブロック(Ｅ，Ｆ[１６，１７])を選択し、レンジブロックＢ，Ｃ[２６，２７]は、距離値が６で差異値が０のドメインブロック(Ｂ，Ｃ[２１，２２])を選択する。
【００３０】
この時、前記逆方向コーディングを行うステップにおいて、多数のマクロブロックをグループ化して探索する。例えば、前記図３ｂにおいて、前記レンジブロックＢ，Ｃ[２６:２７]に対する逆方向コーディングは、レンジブロックＡ，Ｂ，Ｅ，Ｆ，Ｂ，Ｃ[２２:２７]−ドメインブロックＡ，Ｂ，Ｄ，Ｆ，Ｂ，Ｃ[１０:１５]の一つの距離値から構成されたコーディングは、図３に示すように、ドメインブロックＢ，Ｃ[２０:２１]−レンジブロックＢ，Ｃ[２６:２７]、ドメインブロックＥ，Ｆ[１６:１７]−レンジブロックＥ，Ｆ[２４:２５]、ドメインブロックＡ，Ｂ[１８:１９]−レンジブロックＡ，Ｂ[２２:２３]の３個の距離値から構成されたコーディングより小さいコストを有するため、以前コーディングされた結果を再構成して圧縮率を高めることができるようになる。ここで、一つの距離値から構成されたコーディングが、同じでない値が(Ｆ[２５]，Ｅ[２４]，Ｄ[１２])あって、差異値に対するコストが３個の距離値から構成されたコーディングより大きいが、距離値を２個少なく使用するため、全体コストは節減する。この場合、前記圧縮機は、レンジブロックＡ，Ｂ，Ｅ，Ｆ，Ｂ，Ｃ[２２:２７]をドメインブロックＡ，Ｂ，Ｄ，Ｆ，Ｂ，Ｃ[１０:１５]と比較して距離値１２、差異値は０，ＤＦ ＸＯＲ ＥＦ，０でコーディングするようになる。
【００３１】
図４は、本発明の実施形態に係る圧縮方法(ｒａｎｇｅ ｂｌｏｃｋ ｅｎｃｏｄｉｎｇ)のステップを示すフロー図である。まず、前記圧縮機は、ブロックの各参照位置(ｒｅｆｅｒｅｎｃｅ ｐｏｓｉｔｉｏｎ)に対し、後方向(逆方向)に現在のコストを最大に節減する長さ(ｌｅｎｇｔｈ)を求め、セーブが最大セーブ(ｍａｘｉｍｕｍ ｓａｖｉｎｇ)より大きければ、最適長さ(ｏｐｔｉｍｕｍ ｌｅｎｇｔｈ)と参照ブロックとに対する情報を更新する。ここで、前記セーブ(ｓａｖｉｎｇ)とは、長さ内でレンジブロックのコスト節減の和を意味する。次に、前記圧縮機は、最適参照ブロックと最適長さとに対するブロックのコーディングを更新する。最後に、前記圧縮機は、一定の範囲ごとに差異コーディングを最適化するローカルテーブルを生成し、前記ローカルテーブルはグローバルテーブルを参照して圧縮格納する。
【００３２】
前記図４を参照すると、圧縮機は１１１ステップで、設定されたレンジブロックの参照ブロック位置に対して逆方向コストセーブ(ｂａｃｋｗａｒｄ ｃｏｓｔ ｓａｖｉｎｇ)が最大になる長さを求める。図５は、前記図４の１１１ステップで、最適化ステップを行う動作を説明するための図面である。前記図５を参照すると、図５の１５１ステップで、圧縮機は長さ以内の各レンジブロックに対し、セーブ値、すなわちコストの和(ｓａｖｉｎｇ＝ｏｌｄ ｃｏｓｔ−ｎｅｗ ｃｏｓｔ)を求める。前記セーブ値を求めた後、圧縮機は１５３ステップで、前記セーブ値が最大セーブ値より大きいかを検査し、大きくない場合には、以前の値をそのまま維持し１５７ステップへ進む。前記１５３ステップで、前記セーブ値が最大セーブ値より大きい場合には、１５５ステップで前記最大セーブ値を前記で計算されたセーブ値に更新し、最適長さ(ｏｐｔｉｍｕｍ ｌｅｎｇｔｈ)を前記１５１ステップの長さに更新し、最適参照ブロック(ｒｅｆｅｒｅｎｃｅ)を前記１５１ステップの参照ブロックに変更する。その後、圧縮機は１５７ステップで長さが最大長さより大きいかを検査し、大きくなければ１５９ステップで長さを1増加させた後前記１５１ステップに戻り、前記最大長さより大きければ、圧縮機は１５７ステップでこれを感知し１６１ステップでレンジブロックの位置をハッシュテーブル(ｈａｓｈ ｔａｂｌｅ)に挿入して前記図４にリターンする。
【００３３】
すると、圧縮機は、図４の１１３ステップおよび１１５ステップを行いながら前記セーブ値が最大セーブ値より大きいかを検査し、大きくない場合には以前の値をそのまま維持し、セーブ値が最大セーブ値より大きい場合には前記最大セーブ値を更新し、最適長さ(ｏｐｔｉｍｕｍ ｌｅｎｇｔｈ)を更新して、最適参照ブロック(ｒｅｆｅｒｅｎｃｅ)を変更する。その後、圧縮機は、１１７ステップで前記参照ブロックがテーブルにあるかを検査し、参照リストにあれば参照リストから当該データを読んだ後、１１１ステップへ進み、なければ１２１ステップで最適参照ブロックと最適長さとに対してレンジブロックのコーディングを更新する。参照リストは、以前のレンジブロックをコーディングする時、その後のレンジブロックに対する迅速な探索を行うために、ショート(ｓｈｏｒｔ:１６ ｂｉｔ)単位でキュー(ｑｕｅｕｅ)に登録される。一つのマクロブロックに対する探索対象は、２個のショート中少なくとも１個が同じ位置のものから構成される。
【００３４】
コーディング後、圧縮機は１２３ステップで差異コーディングテーブル(ｄｉｆｆｅｒｅｎｃｅ ｃｏｄｉｎｇ ｔａｂｌｅ)を更新する。図６は、前記図４の１２３ステップで差異コーディングテーブルを更新するステップを示すフロー図である。前記図６を参照すると、圧縮機は１８１ステップで特定のレンジブロックＲをコーディングした後、１８３ステップ−１８４ステップを行いながら当該コーディングレンジブロックＲが反復的に処理された回数Ｎ(初期値は０)の値を1増加させ、増加されたＮの値が決められているＴ(Ｔｈｒｅｓｈｏｌｄ)値より小さければ、再び次のレンジブロックＲをコーディングし、前記のステップを反復する。もし、増加されたＮ値がＴ(Ｔｈｒｅｓｈｏｌｄ)より大きければ、１８５ステップでローカルフリークエンシー(ｌｏｃａｌ ｆｒｅｑｕｅｎｃｙ)とコストセーブ(ｃｏｓｔ ｓａｖｉｎｇ)値とによってローカルテーブルを構成する。その後、圧縮機は１８７ステップで、更新コストがコストセーブ値より小さいかを検査し、小さければ１８９ステップでローカルテーブルのコーディングテーブルを更新する。
【００３５】
上記のように生成されるローカルテーブルは、前記グローバルテーブルと共にレンジブロックのデータを圧縮するためのテーブルとして使用される。図７ａは、本発明の実施形態に係るグローバルテーブルの特性を説明するための図面であり、図７ｂは、ローカルテーブルの特性を説明するための図面である。
【００３６】
前記図７ａを参照すると、グローバルテーブルは予め設けられるテーブル(Ｐｒｅ−ｄｅｆｉｎｅｄ ｓｔａｔｉｓｔｉｃｓ ｖａｌｕｅ)であって、データ圧縮時、実験的に頻繁に発生する差異値を抽出して格納した値を格納する。従って、前記グローバルテーブルは更新できないテーブルであり、圧縮時、グローバルテーブルのデータを読むことのみ可能である。グローバルテーブルは固定テーブルであって、固定されたテーブルサイズを有する。本発明の実施形態において、前記グローバルテーブルは８ビットより小さいサイズを[０，．．．，２５５]有すると仮定する。前記グローバルテーブルのインデックスは０から２５５にすることができ、各インデックスに格納されるデータは、レンジブロックおよびドメインブロックの排他的論理和値である(ｘ ｒｅｓｕｌｔ＝[ｓｔａｔｉｓｔｉｃｓ ｖａｌｕｅ Ａ]ＸＯＲ[ｓｔａｔｉｓｔｉｃｓ ｖａｌｕｅ Ｂ])。前記図７ａのようなグローバルテーブルを用いる場合、圧縮機は二つのマクロブロックの差異値中、最も頻繁に発生する差異値を０，１，２，３，．．．，２５５に割り当てて圧縮効率を高めることができる。
【００３７】
前記図７ｂを参照すると、ローカルテーブルはデータの圧縮中に生成するテーブルであって、本発明の実施形態では、同じ値が３回以上発生し、前記発生された同じ値が前記グローバルテーブルに登録されていない値である場合、当該値をローカルテーブルに登録する。前記ローカルテーブルは圧縮機の探索器で生成することができる。前記ローカルテーブルは、更新が可能であり、データの圧縮中に前記テーブルにリードおよびライトが可能である。前記ローカルテーブルは、可変的に登録が可能であり(ｆｌｏａｔｉｎｇ ｅｎｔｒｙ)、前記ローカルテーブルのサイズは前記グローバルテーブルのサイズより大きい値に設定する。本発明の実施形態における前記ローカルテーブルのサイズは８ビット[２５６，．．．，５１１]であると仮定する。この場合、前記ローカルテーブルのインデックスは２５６から５１１にすることができ、各インデックスに格納されるデータは、前記レンジブロックおよびドメインブロックの排他的論理和値である(ｙ ｒｅｓｕｌｔ＝[ｄｙｎａｍｉｃ ｖａｌｕｅ Ａ]ＸＯＲ[ｄｙｎａｍｉｃ ｖａｌｕｅ Ｂ]。従って、前記図７ｂのようなローカルテーブルは、圧縮機がデータを圧縮するときに生成することになり、先に発生する差異値からテーブルインデックス２５６，２５７，．．．，５１１に割り当てることができる。
【００３８】
ここで、前記圧縮機の特徴を圧縮の構成、逆方向コストセーブ(ｂａｃｋｗａｒｄ ｃｏｓｔ ｓａｖｉｎｇ)、差異コーディング(ｄｉｆｆｅｒｅｎｃｅ ｃｏｄｉｎｇ)、距離コーディング(ｄｉｓｔａｎｃｅ ｃｏｄｉｎｇ)、圧縮解除速度制御(ｄｅｃｏｄｉｎｇ ｓｐｅｅｄ ｃｏｎｔｒｏｌ)の順に説明する。
【００３９】
まず、前記圧縮の構成は、各マクロブロックは２個のショートブロックから構成されると仮定し、各ショートブロックは１６ビットから構成されると仮定する。前記レンジブロックのドメインブロックは、前記レンジブロック以前の探索範囲内に存在する同じサイズのブロックにすることができる。また、前記レンジブロックは互いに重なることなく整数(ｉｎｔｅｇｅｒ)単位で配列(ａｌｉｇｎ)され、前記ドメインブロックは互いに重なることもありバイト(ｂｙｔｅ)単位で配列される。レンジブロックの圧縮はドメインブロックとの距離および差異から構成される。
【００４０】
２番目に、逆方向コストセーブの動作は、マクロブロックの参照リスト(ｒｅｆｅｒｅｎｃｅ ｌｉｓｔ)は、マクロブロックと少なくとも一つのショートブロックとが一致する位置から構成され、マクロブロック以前のマクロブロックが圧縮されるハッシュテーブル(ｈａｓｈ ｔａｂｌｅ)に格納される。また、逆方向に同じ距離値で現在のコストを最大にセーブする長さｋを求める。ここで、前記セーブはｋ個のレンジブロックにおけるコスト節減の和を意味する。その後、最適レファレンスと最適長さとに対しレンジブロックの圧縮を更新する。すなわち、前記圧縮機は、図４の１１１ステップ−１２１ステップを行いながら最適化ステップを行うが、これは次のようである。まず、圧縮機は長さ以内の各レンジブロックに対しｓａｖｉｎｇ＝ｏｌｄ ｃｏｓｔ−ｎｅｗ ｃｏｓｔの和を求める。その後、前記圧縮機は、現在のセーブが最大セーブより大きいか(ｓａｖｉｎｇ＞ｍａｘ ｓａｖｉｎｇ)を検査し、大きければ前記圧縮機はパラメーター値を更新する。その後、圧縮機は、長さが最大長さより小さいかを(ｌｅｎｇｔｈ＜ｍａｘ ｌｅｎｇｔｈ)検査する。ここで、前記長さが最大長さより小さければ前記長さを１増加させた後、次のステップを進行するために前記ステップに戻り、前記長さが最大長さであれば、前記レンジブロックの位置をハッシュテーブル(ｈａｓｈ＿ｔａｂｌｅ，(Ｒ))に挿入する。
【００４１】
３番目に、前記圧縮機の差異値を決定するステップは、前記差異圧縮(ｄｉｆｆｅｒｅｎｃｅ ｃｏｄｉｎｇ)は、ショートブロック単位の排他的論理和値をコーディングするが、前記コーディング方法は復元速度の要求事項によって選択される。グローバルテーブル(ｇｌｏｂａｌ ｔａｂｌｅ)は、大きい範囲(ｇｌｏｂａｌ ｆｒｅｑｕｅｎｃｙ)の圧縮に効率のよいエントロピー符号化テーブル(ｅｎｔｒｏｐｙ ｃｏｄｉｎｇ ｔａｂｌｅ)である。ローカルテーブルは、前記グローバルテーブルを参照して圧縮した後格納する。前記ローカルテーブルの構成は、テーブル圧縮率と差異圧縮コスト(ｄｉｆｆｅｒｅｎｃｅ ｃｏｄｉｎｇ ｃｏｓｔ)とを考慮してテーブルエントリー(ｔａｂｌｅ ｅｎｔｒｙ)の更新が決定される。
【００４２】
４番目に、前記圧縮機の距離値を決定するステップは、前記距離圧縮(ｄｉｓｔａｎｃｅ ｃｏｄｉｎｇ)は、復元速度および圧縮率を考慮して次のような２種類の方法を選択することができる。その一つは、現在のレンジブロックの距離が以前のレンジブロックの距離と同じであれば、以前のレンジブロックと同一であることを示す１ビットで表し、以前のレンジブロックの距離と異なっていて２５６以下であれば１０ビットで表し、その他の場合には１８ビットで表示する。また、他の方法は、距離は全て１６ビットで表示し、距離シークエンス(ｄｉｓｔａｎｃｅ ｓｅｑｕｅｎｃｅ)を圧縮して別途格納する。本発明の実施形態では前者の方法を使用すると仮定する。
【００４３】
最後に、復元速度制御(ｄｅｃｏｄｉｎｇ ｓｐｅｅｄ ｃｏｎｔｒｏｌ)方法では、大型マクロブロック(ｌａｒｇｅ ｍａｃｒｏ ｂｌｏｃｋ:ＬＭＢ)はｍ個のマクロブロックから構成される。また、各ＬＭＢの圧縮コストが臨界値(ｔｈｒｅｓｈｏｌｄ ｖａｌｕｅ:ｔ)より大きければコーディングせずにそれ自体を別途格納する。このようなＬＭＢは、例外処理ブロック(ｅｘｃｅｐｔｉｏｎ ｈａｎｄｌｉｎｇ ｂｌｏｃｋ)と称することにする。前記例外処理ブロックは、復元ステップが非常に簡単であるため、復元速度が向上する。前記復元速度の調整は、単純に臨界値ｔを調整すればよい。
【００４４】
上記のように、本発明の実施形態に係るデータ圧縮機は次のような特徴を有する。まず、一つのマクロブロックを圧縮する時、レンジブロックの範囲(ｐａｒｔｉｔｉｏｎ)を調整することでマクロブロックのデータ圧縮率を向上させることができる。２番目に、コストを直接最小化(ｍｉｎｉｍｉｚｅ)せずに、すでに圧縮されたコストのセーブが最大化(ｍａｘｉｍｉｚｅ)する位置を探し、前記１番目で実行する圧縮時間を改善することができる。すなわち、コストを直接最小化すれば、レンジブロックの長さが可変であるため、時間複雑度(ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ)が非常に大きくなる。３番目に、本発明の実施形態では、マクロブロックを多数のショートブロック(ここでは２個のショートブロックを使用)を用い、圧縮時、レンジブロックの少なくとも一つのショートブロックが一致するポジションをハッシュ(ｈａｓｈｉｎｇ)して、圧縮実行速度を向上させると共にレンジブロックの連続性を保障する。４番目に、グローバルテーブルに備えてローカルテーブル構成をコストセーブ演算によって決定する。最後に、グローバルテーブルとローカルテーブルとを圧縮によって格納し、圧縮時にこれを用いてマクロブロックのデータを圧縮する。
【００４５】
前記のような本発明の実施形態に係る圧縮機の構成および動作を具体的に説明する。
図８は、本発明の実施形態に係る前記圧縮機の構成を示す図面である。
前記図８を参照すると、ローダー(ｌｏａｄｅｒ)２１０は、ダウンロードされるデータ(ｒａｗ ｂｉｎａｒｙ ｄａｔａ)をロードする。ここで、前記ローダー２１０は、前記コーダー２４０で圧縮するデータのサイズ(圧縮フレームのサイズ)のデータをロードする。ここで、前記圧縮フレーム(ｃｏｄｉｎｇ ｆｒａｍｅ)とは、前記コーダーがデータを圧縮するサイズ(または、探索器で決定される探索範囲のサイズ)を意味する。また、バッファーは、前記ローダー２１０によってロードされる圧縮フレームのデータを一時バッファーする機能を行う。
【００４６】
探索器２２０は、前記ロードされた圧縮フレームのデータから探索範囲を決定し、レンジブロックを確認した後、前記探索範囲内に位置されたドメインブロックと前記レンジブロックとを比較して二つのブロック間の差異値を生成し、前記生成された差異値によるコストを計算し、最もコストの低いドメインブロックの距離情報およびコスト値を決定する。ここで、前記探索器２２０は、正方向コーディングで前記マクロブロックのサイズのレンジブロックと探索範囲内のドメインブロック間のコストを計算し、逆方向コーディングで以前コーディングされたレンジブロックと前記マクロブロックとが含まれたコストを最適化するレンジブロックの長さおよび距離を決定する。また、前記探索ステップにおいて、前記レンジブロックとドメインブロックとの差異値を計算した後、同一であればドメインブロックとの距離情報および同一であることを表す差異情報を生成し、異なれば前記ドメインブロックの距離情報および二つのブロックが異なることを表す差異情報を生成する。ここで、前記差異情報は、二つのブロックが同一である場合、同一であることを表す差異フラグになり、異なる場合、二つのブロックが異なることを表す差異フラグおよび差異値から構成される。ここで、前記差異値は、二つのブロックの比較結果値(例えば、排他的論理和値)をそのまま使用することができ、前記差異値をコストに変換した値、または前記コストを変形した値等で使用することもできる。本発明の実施形態では、前記比較結果値からコストを計算し、前記計算されたコストをテーブルのインデックスに変換して差異値を生成する場合を例に挙げて説明する。この場合、前記探索器２２０はコストテーブルを備えることができる。ここで、前記コストテーブルは、計算されたコストに対応されるテーブルのインデックス情報を格納するテーブルとなる。前記テーブルは、グローバルテーブルおよびローカルテーブルであり、前記テーブルインデックスに対応される位置に前記差異値を格納することができる。また、前記探索器２２０は、前記探索範囲内で正方向コーディングをしながらレンジブロックと選択されるドメインブロックのデータを比較して差異値を生成し、前記コストテーブルで差異値に対応されるコストを計算する。また、逆方向コーディングをして前記生成されたコストを保管しているコストと比較して、現在生成されたコストの方が低ければ前記コストを更新し、そうでなければ以前のコストを維持する。前記のような動作を繰り返し、前記レンジブロックと探索範囲内のドメインブロックとを比較して最も低いコストを探索し、探索終了時、前記コストテーブルで探索された最も低いコストに該当するテーブルインデックスを選択する。その後、前記探索器２２０は、前記選択されたコストに対応されるドメイン情報との距離情報およびテーブルインデックスを前記コーダー２４０に伝達し、次のレンジブロックを選択して前記のような動作を繰り返し行う。
【００４７】
前記コーダー２４０は、グローバルテーブルおよび/またはローカルテーブルを備えることができる。また、前記グローバルテーブルおよびローカルテーブルは前記バッファーにバッファーすることができる。前記グローバルテーブルは、前記図７aで説明したように、固定テーブル(ｆｉｘｅｄ ｔａｂｌｅ)であって、実験的に測定してこれをテーブル化する。前記ローカルテーブルは、前記図７bで説明したように、可変テーブル(ｖａｒｉａｂｌｅ ｔａｂｌｅ)であって、現在圧縮するデータに対してのみ可変的に生成するテーブルである。ここで、前記グローバルテーブルおよびローカルテーブルは、前記コストによって決定されるテーブルインデックスによって位置が指定され、前記テーブルインデックス位置にレンジブロックとドメインブロックとの差異値が格納されるテーブルである。以下、説明する本発明の実施形態では、グローバルテーブルおよびローカルテーブルを両方とも使用する場合を仮定して説明する。しかし、前記グローバルテーブルまたはローカルテーブル中のいずれか一つのみを用いてデータを圧縮することもある。前記コーダー２４０は、前記コスト値に対応される位置に格納されたテーブルインデックスをレンジブロックのコーディングデータに処理する。ここで、前記コストは前記探索器２２０で計算される。前記探索器２２０は、レンジブロックとドメインブロックとの差異情報に基づいて前記コストを計算することができ、前記コストを用いてコストテーブルでテーブルインデックスにアクセスする。ここで、前記テーブルインデックスは、グローバルテーブルおよび/またはローカルテーブルのインデックスである。前記探索器２２０は、前記レンジブロックとドメインブロックとの距離情報(距離フラグおよび距離値)および前記テーブルインデックスを含む差異情報を前記コーダー２４０に伝達する。すると、前記コーダー２４０は、前記距離情報および差異情報を圧縮データにコーディングする。
【００４８】
前記探索器２２０およびコーダー２４０の動作を説明する。本発明の実施形態では、前記レンジブロックは２個以上のショートブロックから構成される場合を仮定している。前記探索器２２０は、前記レンジブロックとドメインブロックとの差異を計算してコストを計算する。この時、レンジブロックとドメインブロックとの差異値が０であれば、すなわち同一であれば、コスト値は０(または、非常に小さいコスト値)と計算される。また、レンジブロックとドメインブロックとを構成するショートブロックが少なくとも一つ以上同一であれば、同一のショートブロックのコストは０となり、異なるショートブロックのコストは２個のショートブロックの差異値によって計算される。前記のような方法で、前記探索器２２０は、前記レンジブロックのショートブロックデータと前記探索範囲内のドメインブロックのショートブロックデータとを比較し、最も低いコストを有するショートブロックから構成されたドメインブロックを選択する。この時、前記探索器２２０は、探索範囲内でドメインブロックを正方向検索しながらコストを計算し、前記計算されたコストを逆方向に探索しながら現在保管している最も低いコストと比較した後、現在探索されたコストの方が低ければ、現在ドメインブロックとの距離情報およびコストを更新する。前記探索範囲内のドメインブロックの探索を終了すれば、前記探索器２２０は、探索範囲内で前記レンジブロックと最も低いコストを有するドメインブロックとの距離情報およびコスト値を保管するようになる。その後、前記探索器２２０は、前記コストを用いてコストテーブルでテーブルインデックスを求め、前記距離情報と共に前記テーブルインデックスを含む差異情報をコーダー２４０に伝達する。この時、前記差異情報は、差異フラグおよびテーブルインデックスを含むことができ、レンジブロックとドメインブロックとが同一である場合、前記テーブルインデックスは含まれない。本発明の実施形態では、前記探索器２２０が差異情報を生成する時、レンジブロックとドメインブロックのデータが一致すれば、差異フラグをリセット(差異フラグ＝０)し、差異フラグのみからなる差異情報を生成する。しかし、前記レンジブロックとドメインブロックのデータが一致しなければ、前記探索器２２０は、差異フラグをセット(差異フラグ＝１)し、差異値によるコストによって選択されるテーブルインデックス情報を含む差異情報を生成する。
【００４９】
すると、前記コーダー２４０は、前記差異情報の差異フラグを分析して二つのブロックが同一のデータであれば、前記距離情報および差異フラグをレンジブロックの圧縮データにコーディングする。ここで、前記差異情報はテーブルインデックスを含むことができる。この時、前記テーブルインデックスが含まれていれば、前記コーダー２４０は、前記テーブルインデックスに対応されるテーブル(グローバルテーブルおよび/またはローカルテーブル)で二つのブロックの差異値を確認した後、前記差異値が正常の差異値(すなわち、前記探索器２２０で探索された差異値と同一の差異値)であれば、前記距離情報および差異情報をレンジブロックの圧縮データにコーディングする。
【００５０】
また、本発明の実施形態では、前記圧縮機は例外ブロック処理部２５０をさらに備えることができる。ここで、前記例外ブロックは、レンジブロックとドメインブロックとの差異値が設定された臨界値より大きく、圧縮効果がほとんどないブロックになることもある。例えば、前記レンジブロックおよびドメインブロックは、前記図1で説明したように、マクロブロック単位のサイズを有し、前記マクロブロックは２個以上のショートブロックから構成される。この場合、前記探索器２２０は、上記のようにレンジブロックを決定し、探索範囲内のドメインブロックを正方向および逆方向コーディングして差異値(すなわち、コスト)が最も小さいドメインブロックを選択する。しかし、前記設定されたレンジブロックと選択されたドメインブロックのショートブロックデータが全て同一でなければ(すなわち、レンジブロックおよびドメインブロックのショートブロックデータが全て異なれば)、現在のレンジブロックデータを圧縮する効果が大幅に落ちる。この場合、本発明の実施形態では、該当するレンジブロックのデータを圧縮せずに(ｎｏ ｃｏｄｉｎｇ)そのまま格納し、例外ブロックとして処理したことを表示するフラグを生成する。これは、圧縮解除機でメモリに圧縮格納されたデータを復元する時、例外処理ブロックのデータは圧縮解除ステップを経ることなく直接復元できるため、デコーディング速度が改善できる。本発明の第２実施形態では、前記コーダー２４０がグローバルテーブルおよびローカルテーブルを備え、差異情報の差異フラグを２ビットから構成し、前記例外ブロックに処理する例外フラグを共に表示する方法を提案する。この場合、前記差異フラグは、下記表１のように構成することができる。
【００５１】
【表１】
2011250431.tif 000003
【００５２】
前記探索器２２０は、レンジブロックと選択されたドメインブロックのショートブロックのデータを上記のように探索範囲内のドメインブロックを正方向および逆方向検索し、最も低いコストを有するドメインブロックを選択する。まず、選択されたドメインブロックのデータが前記レンジブロックのデータと同一であれば、前記探索器２２０は、選択されたドメインブロックとレンジブロックとの距離情報および同一であることを表す差異フラグ(差異フラグ＝０)を生成してコーダー２４０に伝達する。２番目に、選択されたドメインブロックのデータが前記レンジブロックデータと異なり、二つのブロックの差異値によって生成されたコストがグローバルテーブルのインデックスであれば、前記探索器２２０は、前記選択されたドメインブロックとレンジブロックとの距離情報およびグローバルテーブルインデックスに存在することを表す差異フラグ(差異フラグ＝０１)およびグローバルテーブルインデックスを含む差異情報を生成して前記コーダー２４０に伝達する。３番目に、選択されたドメインブロックのデータが前記レンジブロックデータと異なり、二つのブロックの差異値によって生成されたコストがローカルテーブルのインデックスであれば、前記探索器２２０は、前記選択されたドメインブロックとレンジブロックとの距離情報およびローカルテーブルインデックスに存在することを表す差異フラグ(差異フラグ＝１０)およびローカルテーブルインデックスを含む差異情報を生成して前記コーダー２４０に伝達する。最後に、前記レンジブロックとドメインブロックのデータが異なり、二つのブロックの差異値によって生成されたコストがグローバルテーブルおよびローカルテーブルに存在しなければ、前記探索器２２０は、前記差異フラグを例外処理フラグに設定してこれを前記コーダー２４０に通知する。
【００５３】
すると、前記コーダー２４０は、前記差異フラグを分析してレンジブロックのデータをコーディングする。まず、前記差異フラグが、二つのブロックのデータが同一であることを表すフラグ(差異フラグ＝０)であれば、前記コーダー２４０は、前記選択されたドメインブロックの距離情報および差異フラグを前記レンジブロックの圧縮データにコーディングする。２番目に、前記差異フラグが、グローバルテーブルのインデックスを有するデータであることを表すフラグ(差異フラグ＝０１)であれば、前記コーダー２４０は、前記選択されたドメインブロックの距離情報および差異フラグおよびグローバルテーブルインデックスからなる差異情報をレンジブロックの圧縮データにコーディングする。３番目に、前記差異フラグが、ローカルテーブルのインデックスを有するデータであることを表すフラグ(差異フラグ＝１０)であれば、前記コーダー２４０は、前記選択されたドメインブロックの距離情報および差異フラグおよびローカルテーブルインデックスからなる差異情報をレンジブロックの圧縮データにコーディングする。
【００５４】
最後に、前記差異フラグが例外処理フラグ(差異フラグ＝１１)であれば、前記コーダー２４０は、例外ブロック処理部２５０を駆動して前記レンジブロックのデータをコーディングせずにそのままメモリに格納する。この場合、前記メモリには、前記例外ブロックに処理されたレンジブロックのコーディングされていないデータが格納され、差異フラグには、例外処理フラグが格納される。本発明の実施形態では、前記例外ブロック処理部２５０が、前記コーダー２４０と独立して構成される場合を仮定して説明しているが、前記例外ブロック処理部２５０は、前記コーダー２４０に含まれる構成としても具現できる。
【００５５】
図９は、前記探索器２２０の動作を説明するための図面である。前記図９において、レンジブロックは、３９１のように８番および９番ショートブロックの場合を仮定している。この場合、ドメインブロックは２個のショートブロックを対象にし、図９の場合、ドメインブロックは、６番および７番ショートブロック、５番および６番ショートブロック、４番および５番ショートブロック、３番および４番ショートブロック、２番および３番ショートブロック、１番および２番ショートブロック、また、０番および１番ショートブロック等にすることができる。前記図９の３９３のような圧縮対象のデータがダウンロードされ、ローダー２１０によってバッファーにバッファーされた状態である。
【００５６】
前記図９を参照すると、３１０ステップで探索器２２０は探索範囲をロードし、ここで探索範囲は２，４，８，１６，．．．，６５５３６マクロブロックにすることができる。ここで、前記探索範囲は、上記のようにコーダー２４０がデータを圧縮するための単位(圧縮フレーム)である。前記探索範囲を決定した後、探索器２２０は３２０ステップで圧縮する対象であるレンジブロックをロードし、ここで、前記レンジブロックは８番および９番ショートブロックと仮定する。その後、前記探索器２２０は、３３０ステップで前記レンジブロックを探索範囲内の各ドメインブロックと比較できるようにドメインブロックを選択する。ここで、前記ドメインブロックの選択は、レンジブロックの位置で正方向コーディングしながらドメインブロックを選択し、この時、前記ドメインブロックはショートブロック単位で移動しながら選択される。前記ドメインブロックを選択した後、探索器２２０は３４０ステップで前記選択されたドメインブロックのデータを前記レンジブロックのデータと比較する。この時、前記比較演算は、排他的論理和演算である。その後、前記探索器２２０は、３５０ステップで前記ドメインブロックとの距離情報を算出し、３６０ステップで前記二つのブロック間の差異値によるコストを計算する。ここで、前記距離情報は、距離フラグおよび距離値から構成される。また、前記コストは、二つのブロックの比較結果値の差異値に基づいて計算する。前記探索器２２０は、テーブルインデックスを格納するコストテーブルを備え、コストはコストテーブルのアドレスに使用される。従って、前記コストが計算されれば、探索器２２０は、前記コストに対応されるアドレスに格納されたコストテーブルの値を発生し、この時、コストテーブルの値はテーブルインデックスとなる。ここで、前記テーブルインデックスは、前記グローバルテーブルまたはローカルテーブルのインデックスにすることができる。
【００５７】
前記のようなステップを行い前記探索器２２０は前記レンジブロックと探索範囲内のドメインブロックとの距離情報およびコストを計算し、前記計算されたコストをコストテーブルで探索してテーブルインデックスを求める。ここで、前記探索器２２０は、前記コストによって探索されるテーブルインデックスの中から最も小さい値を有するテーブルインデックスを選択する。すなわち、正方向コーディングをしながらドメインブロックとの距離情報およびコストを計算し（すなわち、レンジブロックを選択した後、順次にドメインブロックを選択しながら距離情報およびコストを計算し）、前記コストを用いてコストテーブルでテーブルインデックスを決定する。その後、逆方向コーディングし、前記決定されたテーブルインデックスと現在まで探索しながら保管している最も低いテーブルインデックスとを比較して、以前のテーブルインデックスの方が小さい値を有していれば、以前のテーブルインデックスを維持し、そうでなければ（すなわち、現在のテーブルインデックスの方が小さい値を有していれば）、前記テーブルインデックス値を更新して格納する。すなわち、前記探索器２２０は、現在のテーブルのインデックスの方が小さければ、現在探索されたドメインブロックとの距離情報および差異値によるテーブルインデックスを更新格納し、そうでなければ、以前の探索ステップで保管していた距離情報およびテーブルインデックスをそのまま維持する。前記のような動作を繰り返し行ない、前記探索器２２０は、前記レンジブロックと探索範囲内で最も低いコストを有するドメインブロックとの距離情報およびテーブルインデックスを格納する。
【００５８】
しかし、前記探索器２２０において、レンジブロックを構成するショートブロック中、いずれのショートブロックも探索範囲内のショートブロックと同一でない場合、当該レンジブロックの圧縮効果はよくない。この場合、本発明の実施形態では、該当するレンジブロックを例外ブロックに処理する。すなわち、探索器２２０は、レンジブロックのショートブロックを探索範囲内のドメインブロックのショートブロックと比較し、一致する数以上のショートブロックを探索できなかった場合、例外処理フラグを生成して該当するレンジブロックのコストを計算しない。例えば、レンジブロックおよびドメインブロックのサイズを有するマクロブロックがＮ個のショートブロックから構成され、レンジブロックおよび探索領域内のドメインブロックを比較するとき、二つのマクロブロックにおいて一致するショートブロックの数がＭ個以下である場合、前記探索器２２０は、該当するレンジブロックを例外処理ブロックに設定することができる。この場合、前記探索器２２０は、当該レンジブロックを例外処理ブロックに決定して例外処理フラグをセットする。この場合、本発明の実施形態では、前記差異フラグを例外処理フラグとして処理し（前記表１の場合、差異フラグは１１となる）、テーブルインデックスは生成しない。
【００５９】
本発明の実施形態において、前記レンジブロックおよびドメインブロックは２個のショートブロックから構成される場合を仮定して説明している。この場合、前記Ｎ＝２、Ｍ＝０に設定することができる。また、前記探索器２２０は、レンジブロックのショートブロックと探索範囲内の全てのドメインブロックのショートブロックとが同一でない場合、当該レンジブロックを例外処理ブロックに決定し、差異フラグを「１１」に決定して例外処理ブロックであることを表示する。
【００６０】
また、前記探索器２２０はローカルテーブルを生成することができる。すなわち、前記図７ｂに示すように、前記探索器２２０は、グローバルテーブルに登録されてはいないが同一の差異値（レンジブロックとドメインブロックとの差異値）が設定された回数（ここでは、３回）以上発生すれば、これをローカルテーブルに登録する。この時、前記ローカルテーブルのコスト（テーブルインデックス）は、前記グローバルテーブルのコスト（テーブルインデックス）よりは大きい値を有するように設定する。また、前記コストおよびテーブルインデックスはコストテーブルに登録する。上記のように、ローカルテーブルを使用する場合、圧縮機は前記グローバルテーブルには登録されていないが、よく発生する差異値をテーブルに登録して圧縮を効率よく行うことができる。
【００６１】
前記のような探索ステップが終了すれば、前記探索器２２０は、３７０ステップで前記格納している距離情報および差異情報（テーブルインデックスを含む）をコーダー２４０に伝達する。
【００６２】
前記図９の場合、前記探索器２２０は、図９の３９３のように、バッファーされたデータをマクロブロック単位に設定し、現在のレンジブロックである８番および９番ブロックの前に位置するドメインブロックを６番および７番、５番および６番、４番および５番、．．．、０番および１番ブロックの順にインデックスして探索をする。また、前記探索器２２０は、前記レンジブロックのデータを選択されるドメインブロックのデータと比較して、その結果値を出力する。この場合、前記探索器２２０は、レンジブロックとドメインブロックとを比較して差異値を生成するが、６番および７番ショートブロックがドメインブロックに選択される時点でＥ ＸＯＲ Ｂ、Ｃ ＸＯＲ Ｂを生成し、５番および６番ショートブロックがドメインブロックに選択される時点でＢ ＸＯＲ Ｂ、Ｅ ＸＯＲ Ｂを生成し、４番および５番ブロックがドメインブロックに選択される時点でＢ ＸＯＲ Ｂ、Ｂ ＸＯＲ Ｂを生成し、３番および４番ショートブロックがドメインブロックに選択される時点でＦ ＸＯＲ Ｂ、Ｂ ＸＯＲ Ｂを生成し、２番および３番ショートブロックがドメインブロックに選択される時点でＤ ＸＯＲ Ｂ、Ｆ ＸＯＲ Ｂを生成し、１番および２番ショートブロックがドメインブロックに選択される時点でＢ ＸＯＲ Ｂ、Ｄ ＸＯＲ Ｂを生成し、０番および１番ショートブロックがドメインブロックに選択される時点でＡ ＸＯＲ Ｂ、Ｂ ＸＯＲ Ｂを生成する。また、前記ドメインブロックとレンジブロック間の距離情報も生成する。
【００６３】
その後、前記探索器２２０は、生成された差異値に基づいてコストを計算するが、レンジブロックがドメインブロックと同一である場合（図９において４番および５番ショートブロック）、コストは０となり、２個のショートブロック中一つのショートブロックが同一である場合（５番および６番ショートブロック、３番および４番ショートブロック、１番および２番ショートブロック、０番および１番ショートブロック）、コストは最小コストで計算され、２個のショートブロックが両方とも異なる場合、コストは高いコストで計算される。図９のような場合、前記探索器２２０は３７０ステップで前記４番および５番ショートブロックの距離情報（距離フラグ１、距離値４）と二つのブロックデータが同一であることを表す差異フラグ（ここでは、差異フラグ＝０）とを前記コーダー２４０に伝達する。しかし、前記４番および５番ショートブロックと同じコストが０（または、０に近い値）のドメインブロックがない場合、前記探索器２２０は、コストが最も低いドメインブロックの距離情報および差異情報を生成してコーダー２４０に伝達する。ここで、前記差異情報は、二つのブロックのデータが互いに異なることを表す差異フラグ（ここでは、差異フラグ＝０１または１０）およびテーブルインデックス（前記計算されたコストに対応されるコストテーブルに格納されたテーブルインデックス）を含む情報である（例えば、０番および１番ショートブロックの場合、距離情報（距離フラグ１、距離値８）および差異情報（差異フラグ０１、テーブルインデックス））。
【００６４】
すると、コーダー２４０は、前記距離情報および差異情報(差異フラグおよびテーブルインデックス)を用いてレンジブロックのデータを圧縮する。図１０は、前記コーダー２４０において、レンジブロックのデータを圧縮するステップを示すフロー図である。前記図１０は、コーダー２４０が例外ブロック処理機能を備える場合を示している。しかし、前記コーダー２４０は、前記例外ブロック処理機能を備えないこともある。この場合、前記圧縮機は例外ブロック処理部２５０を備えず、コーダー２４０は、前記例外ブロックに処理すべきブロック(例えば、レンジブロックを構成するショートブロック中、いずれのショートブロックも探索範囲内の全てのショートブロックと同一でない場合)も上記のようにコストを計算してコーディングすることができる。
【００６５】
前記図１０を参照すると、ローダー２１０は４１１ステップでダウンロードされたデータをロードしてバッファーにバッファーするが、この時、前記ロードされるデータはマクロブロックおよびショートブロック単位に分割(ｐａｒｔｉｔｉｏｎ)される。この時、前記ロードされるデータの前の段に位置するマクロブロックは、比較する対象、すなわちドメインブロックがないか、または、少数のドメインブロックと比較してコーディングされる。この場合、比較する対象であるドメインブロックが多くないため、前記圧縮機はレンジブロックの圧縮を効果的にすることができなくなる。そのため、圧縮時、圧縮フレームの前に位置する設定された数のマクロブロックは、圧縮ステップを行わずに例外処理ブロックに処理するのが好ましい。前記ローダー２１０は、前記圧縮フレームサイズにデータをロードし、探索器２２０は、ロードされるデータをレンジブロックおよびドメインブロックに分割して探索し始める。この時、ロードされるデータの前の部分は、参照対象であるドメインブロックがないか、または非常に少数のドメインブロックを有するようになる。この場合、本発明の実施形態において、前記探索器２２０は、ロードされる圧縮フレームデータから設定されたサイズのマクロブロックは例外ブロックに処理する。前記図１０では、ロードされる圧縮フレームデータから１６マクロブロック(ＭＢ０−ＭＢ１５)を例外ブロック処理することを例示している。従って、圧縮開始時、前記コーダー２４０は、４３５ステップで前記マクロブロックＭＢ０−ＭＢ１５を例外処理ブロックに処理した後、４３３ステップで例外処理ブロックとして格納する。この時、前記コーダー２４０は、前記例外処理ブロックのデータを圧縮せずにそのまま格納する。
【００６６】
前記例外処理ブロック処理後、探索器２２０は、前記図９に示すように探索範囲を設定した後、レンジブロックと探索範囲内のドメインブロックとをロードした後、これらのブロックを比較し、前記レンジブロックに対する距離情報および差異情報をコーダー２４０に伝達する。
【００６７】
すると、前記コーダー２４０は、４１５ステップで差異フラグを検査してレンジブロックとドメインブロックのデータが同一であるか(コスト＝０)を検査し、同一であれば４１７ステップで、探索器２２０で前記レンジブロックのデータを生成された距離情報および差異フラグにコーディングして圧縮データを生成した後、４１９ステップでメモリにバッファーする。すなわち、前記レンジブロックおよび探索されたドメインブロックのデータが同一であれば、前記コーダー２４０は、レンジブロックとドメインブロック間の距離情報およびレンジブロックと同一であることを表す差異フラグ(差異フラグ＝０)を前記レンジブロックの圧縮データに生成する。
【００６８】
しかし、前記４１５ステップでレンジブロックと同一のドメインブロックがない場合(差異フラグ≠０)、前記コーダー２４０は、４２１ステップで前記テーブルインデックスを確認し、４２３ステップで、前記テーブルでこれを確認する。この時、前記テーブルインデックスは、前記探索器２２０で二つのブロックの差異値によって生成される情報であり、前記グローバルテーブル(および/または、ローカルテーブル)のテーブルインデックスとなる。ここで、前記テーブルインデックスを確認する理由は、前記探索器２２０で探索されたコストがグローバルテーブル(および/または、ローカルテーブル)に存在するかを確認するためである。すなわち、前記グローバルテーブル(および/または、ローカルテーブル)は、前記コストによって決定されるテーブルインデックスを用いて、圧縮解除機が圧縮データを復元する時、前記テーブルインデックスによってレンジブロックとドメインブロックとの差異値を抽出することができるようになる。以下の説明では、グローバルテーブルおよびローカルテーブルを両方とも使用する場合と仮定して説明する。前記探索器２２０で生成されたテーブルインデックスが前記テーブルのインデックスに用いられなければ、当該レンジブロックの圧縮データは復元できない。この時、前記差異フラグが、グローバルテーブルのインデックスであることを表示する差異フラグ(差異フラグ＝０１)であれば、前記コーダー２４０は４２５ステップで前記テーブルインデックス値がグローバルテーブルに存在するかを検査し、前記グローバルテーブルに存在すれば４１９ステップで距離情報および差異情報をメモリに格納する。この時、距離情報は、前記レンジブロックと距離フラグおよび該当するドメインブロックとの距離値であり、差異情報は、差異フラグおよびグローバルテーブルのインデックス値である。また、前記差異フラグがローカルテーブルのインデックスであることを表示する差異フラグ(差異フラグ＝１０)であれば、前記コーダー２４０は４２７ステップでローカルテーブルを探索する。ここで、前記ローカルテーブルは、前記図７ｂに示すように、探索器２２０に生成されるテーブルであって、前記グローバルテーブルには登録されていないが設定回数以上に反復的に探索される差異値が登録される。この時、前記ローカルテーブルに前記テーブルインデックス値が存在すれば、前記コーダー２４０は４２９ステップでこれを感知し、４１９ステップで距離情報および差異情報をメモリに格納する。上記のように、前記差異フラグが０でなく、前記差異フラグが「０１」または「１０」であれば、前記コーダー２４０は、前記差異フラグ値および前記グローバルテーブルまたはローカルテーブルのテーブルインデックスからなる差異情報を前記距離情報と共にメモリに格納する。
【００６９】
しかし、前記４２９ステップで前記差異フラグが例外処理フラグであれば、前記コーダー２４０は４２９ステップでこれを感知し、４３１ステップで例外ブロック処理部２５０を駆動する。すると、例外ブロック処理部２５０は、４３１ステップで例外処理フラグをメモリに格納した後、４３３ステップでレンジブロックのデータを圧縮せずにそのまま格納する。すなわち、前記レンジブロックが探索範囲内のドメインブロックと同一でなく、また、前記グローバルテーブルおよびローカルテーブルに存在しなければ、コーダー２４０は、例外ブロック処理部２５０を介して例外処理フラグと共に圧縮されていないデータをそのまま格納する。
【００７０】
上記のように、前記コーダー２４０は、レンジブロックのデータを圧縮せずにメモリに格納することができる。例えば、前記レンジブロックを構成するショートブロックデータが探索範囲内に存在するドメインブロックのショートブロックデータと同一でないか、または、同一のショートブロックが存在するとしてもコストが高い場合、前記レンジブロックを例外処理ブロックに処理する。すなわち、レンジブロックとドメインブロックとの差異値がグローバルテーブルおよびローカルテーブルに存在しなければ、当該レンジブロックのデータを圧縮せずにそのまま格納する。この場合、前記コーダー２４０は、これを例外ブロック処理部(ｅｘｃｅｐｔｉｏｎ ｈａｎｄｌｅｒ)２５０に通知し、前記例外ブロック処理部２５０は、当該レンジブロックのデータを圧縮せずにメモリにそのまま格納する。ここで、前記例外ブロック処理部２５０はコーダー２４０の内部に構成することもできる。
【００７１】
前記圧縮機は、前記のような動作を繰り返しながらロードされるレンジブロックのデータを圧縮した後、前記メモリに格納する。この時、前記第２補助メモリに格納される圧縮データは、距離情報、差異情報、および例外処理ブロック等から構成される。前記メモリに下記表２のように、距離情報、差異情報、および例外処理ブロックが格納される。
【００７２】
【表２】
2011250431.tif 000004
【００７３】
上記のように、前記圧縮機は、レンジブロックの前に位置する探索範囲内に存在するドメインブロックをレンジブロックと比較して差異値を求めた後、差異値によるコストを計算し、最も低いコストを有するドメインブロックとの距離情報および差異情報を用いてレンジブロックのデータを圧縮する。前記図９において、レンジブロックと探索範囲内の３番目[４，５]のドメインブロック間の差異が０であるため、前記コーダー２４０は、前記３番目のドメインブロックまでの距離および差異値を圧縮データに生成する。
【００７４】
しかし、前記図９において、１番目[６，７]および５番目[２，３]のドメインブロックのように、探索範囲内のドメインブロック中、前記レンジブロックと同じショートブロックがない場合、前記コーダー２４０は、前記レンジブロックを例外処理ブロックに処理する。
【００７５】
また、２番目[５，６]、４番目[３，４]、６番目[１，２]および７番目[０，１]のドメインブロックのように、前記レンジブロックのショートブロック中の一つのショートブロックと探索範囲内のドメインブロック中の一つのショートブロックとが同一である場合、前記コーダー２４０は、前記探索範囲内のドメインブロックとレンジブロックのコストの和を計算し、最も低いコストの和を有するドメインブロックと前記レンジブロック間の距離情報および差異情報(差異フラグおよびテーブルインデックス)を圧縮データに決定する。この時、前記コーダー２４０が、グローバルテーブルおよび/またはローカルテーブルを備える場合、前記コーダー２４０は、前記差異値を前記テーブルのインデックスに適用してテーブルの当該インデックス位置に存在する情報を圧縮データに決定する。この場合、前記レンジブロックの圧縮データは、ドメインブロックとの距離および前記テーブルの情報となる。
【００７６】
図１１は、前記図９に示すようなデータがローダー２１０によってロードされバッファーにバッファーされた後、探索器２２０によってレンジブロックと最も低い値を有するドメインブロックのコストを計算する場合、コーダー２４０が、前記探索器２２０で出力される距離情報および差異情報を用いて各レンジブロックのデータをコーディングするステップを具体的に示す図面である。
【００７７】
前記図１１において、ショートブロック[０，１，２，３，４，５](ｐｒｏｃ−１)は、ロード時、例外ブロックに処理するブロックと仮定し、[６，７](ｐｒｏｃ−２)，[８，９](ｐｒｏｃ−３)，[１０，１１](ｐｒｏｃ−４)がレンジブロックに選択される場合の探索器２２０およびコーダー２４０の動作ステップを具体的に説明する。
前記図１１を参照すると、ローダー２１０は、図１１の参照番号５１０のような圧縮フレームデータをロードして内部バッファーにバッファーする。すると、コーダー２４０は、５１２ステップで前記５１０のようなデータから例外処理するブロックのデータをロードした後、５１４ステップおよび５１６ステップで前記ロードしたブロックデータを例外処理する。この時、前記例外処理されるブロックは６個のショートブロック(３個のマクロブロック)[０，１，２，３，４，５]である。前記５１６ステップで例外処理されるブロックは、図１１の参照番号５１８のようにメモリに格納される。上記のように、ロードされる圧縮フレームデータから設定された数のマクロブロックを例外処理するのは、上記のように圧縮効率がよくないためであって、この場合、ロードされる圧縮フレームデータの始まる部分に位置する設定された数のマクロブロックを例外処理して復号効率を向上させるのが好ましい。従って、前記メモリには例外処理されたブロックのデータ(ｒａｗ ｄａｔａ)が格納される。
【００７８】
上記のように、ロードされた圧縮フレームデータの例外処理ブロックを処理した後、圧縮機は、５２２ステップでその後続くマクロブロックからレンジブロックを選択し、前記選択されたレンジブロックの前に位置するドメインブロックを探索して距離情報および差異情報を計算し、前記選択されたレンジブロックのデータを圧縮する。前記図１１では、マクロブロックｐｒｏｃ−２[６，７]，ｐｒｏｃ−３[８，９]，ｐｒｏｃ−４[１０，１１]がレンジブロックに選択される場合の圧縮ステップを説明する。
【００７９】
まず、ｐｒｏｃ−２[６，７]の圧縮ステップにおいて、探索器２２０は５２４ステップで前記レンジブロック[６，７]をロードした後、探索範囲を設定する。ここで、前記探索範囲はブロック[０−５]にすることができる。その後、探索器２２０は、５２６ステップで正方向および逆方向コーディングステップを行うが、前記探索範囲内に同一のブロックがないため、グローバルテーブルおよびローカルテーブルのインデックスを生成できず、当該レンジブロックを例外処理するための差異フラグ(すなわち、例外処理フラグ)(「１１」)を生成する。従って、コーダー２４０は、５６２ステップで前記探索器２２０で生成される例外処理フラグによって前記レンジブロック[６，７]を例外処理するようになる。前記例外ブロック処理時、前記コーダー２４０は、前記差異フラグを格納する領域に例外処理されるブロックであることを表すフラグ(「１１」)を格納して例外ブロックのデータを圧縮せずにそのまま格納し、この時、前記メモリに格納される例外処理ブロックのデータは、図１１の参照番号５６４のような形態を有する。
【００８０】
次に、ｐｒｏｃ−３[８，９]の圧縮ステップにおいて、探索器２２０は、５２４ステップで前記レンジブロック[８，９]をロードした後、探索範囲を設定する。ここで、前記探索範囲はブロック[０−７]にすることができる。その後、探索器２２０は、５２６ステップで前記探索範囲のドメインブロックを正方向および逆方向コーディングステップを行う。ドメインブロック[４，５]を探索する時、探索器２２０は、前記レンジブロック[８，９]と同一であることを感知して前記ドメインブロック[４，５]で差異値が０であることを表す差異情報を生成する。この場合、探索器２２０は、前記レンジブロックのショートブロック[８]に対しては差異フラグ＝１、差異値＝４を有する距離情報を生成し、差異フラグ＝０の差異情報を生成し、ショートブロック[９]に対しては距離フラグ＝０の距離情報および差異フラグ＝０(前記ショートブロック[９]からショートブロック[５]までの距離は、ショートブロック[８]からショートブロック[４]までの距離と同一であるため)の差異情報を生成してコーダー２４０に出力する。すると、前記コーダー２４０は、５３２ステップおよび５３４ステップでレンジブロックとドメインブロックのデータが同一であることを確認し、前記距離情報(ｄｉｓｔａｎｃｅ ｆｌａｇ＝１０、ｄｉｓｔａｎｃｅ ｖａｌｕｅ＝４)および差異フラグ(ｄｉｆｆｅｒｅｎｃｅ ｆｌａｇ＝０,０)から構成される圧縮データを生成してメモリに格納する。この時、前記メモリに格納されるブロック[８，９]の圧縮データは、図１１の参照番号５３６のように、距離情報は１０[ｄｉｓｔａｎｃｅ ｆｌａｇ]、４[ｄｉｓｔａｎｃｅ ｖａｌｕｅ]であり、差異情報は００[ｄｉｆｆｅｒｅｎｃｅ ｆｌａｇ＝００]である。
【００８１】
最後に、ｐｒｏｃ-４[１０，１１]の圧縮ステップにおいて、探索器２２０は５２４ステップで前記レンジブロック[１０，１１]をロードした後、探索範囲を設定する。ここで、前記探索範囲はブロック[０-９]にすることができる。その後、探索器２２０は５２６ステップで前記探索範囲のドメインブロックを正方向および逆方向コーディングステップを行う。ドメインブロック[０，１]を探索する時、探索器２２０は、前記レンジブロック[１０，１１]と類似していることを感知し、これによる距離情報および差異情報を生成する。この時、前記レンジブロックのショートブロック[１０]とドメインブロックのショートブロック[０]とは同一であるため、探索器２２０は、当該ショートブロックの位置に差異値が０であることを表す差異情報を生成する。この場合、探索器２２０は、距離フラグ＝１、距離値＝１０を有する距離情報を生成し、差異フラグ＝０の差異情報を生成してコーダー２４０に出力する。また、レンジブロックのショートブロック[１１]とドメインブロックのショートブロック[１]とは互いに異なるデータであるため、探索器２２０は、２個のショートブロックの差異値[Ｃ ＸＯＲ Ｂ]を計算し、前記差異値に対応されるコストを計算した後、前記コストテーブルで前記コストによるテーブルインデックスを決定する。この場合、探索器２２０は、距離フラグ＝０(前記ショートブロック[１１]からショートブロック[１]までの距離は、ショートブロック[１０]からショートブロック[０]までの距離と同一であるため)に生成し、差異フラグおよび前記決定されたテーブルインデックスからなる差異情報をコーダー２４０に出力する。ここで、前記テーブルインデックスはグローバルテーブルのインデックスと仮定する。この場合、前記差異情報は、差異フラグ＝０１およびグローバルテーブルインデックスＧｔｂｌ ｉｄｘからなる。
【００８２】
すると、前記コーダー２４０は、５３２ステップおよび５３４ステップでレンジブロックのショートブロック[１０]とドメインブロックのショートブロック[０]のデータとが同一であることを確認し、前記距離情報(ｄｉｓｔａｎｃｅ ｆｌａｇ＝１、ｄｉｓｔａｎｃｅ ｖａｌｕｅ＝１０)および差異フラグ(ｄｉｆｆｅｒｅｎｃｅ ｆｌａｇ＝０)から構成される圧縮データを生成してメモリに格納する。また、前記レンジブロックのショートブロック[１１]はドメインブロックのショートブロック[１]と同一でないため、コーダー２４０は、５４２ステップおよび５４４ステップを行い探索器２２０で出力されるテーブルインデックスを５４４のようなテーブルで探索する。この時、前記テーブルインデックスが、前記図１１の参照番号５４４のようなテーブルで検索されれば、コーダー２４０は、５４８ステップで前記検索されたコスト[Ｇｔｂｌ ｉｄｘ=ｃｏｄｅ(Ｃ:Ｂ)]を差異値(ｄｉｆｆｅｒｃｅ ｖａｌｕｅ)として格納する。すなわち、コーダー２４０は、レンジブロックのショートブロック[１１]の圧縮データで、距離フラグ＝０の距離情報と差異フラグ＝０１、差異値＝[Ｇｔｂｌ ｉｄｘ=ｃｏｄｅ(Ｃ:Ｂ)]の差異情報とを圧縮データに生成して５５０のようにメモリに格納する。
【００８３】
図１１の参照番号５５０は、図１１の参照番号５１０のような圧縮フレームデータをロードした後、探索器２２０およびコーダー２４０がショートブロック[０-１１]のデータを圧縮してメモリに格納する形態を表示している。
【００８４】
上記のように、本発明の実施形態では、レンジブロックと探索範囲内のドメインブロックとの距離情報および差異情報を確認してレンジブロックを圧縮する。ここで、前記距離情報は、レンジブロックと対応されるドメインブロック間の距離情報であり、距離フラグと距離値とからなる。前記距離フラグは、１ビットを使用してセット状態またはリセット状態に設定することができる。すなわち、現在、圧縮対象であるレンジブロックと対応されるドメインブロック間の距離値が、以前圧縮対象であったレンジブロックと対応されるドメインブロック間の距離値と同一である場合、距離フラグはリセットされた状態(前記表２の場合、「０」)に設定し、そうでなければ(すなわち、距離値が異なれば)、前記距離フラグはセット(前記表２の場合、「１」)に設定する。この場合、前記距離情報は、距離フラグがセット状態(「１」)であれば、前記距離フラグおよび対応されるドメインブロックとの距離値から構成され、距離フラグがリセット状態(「０」)であれば、距離フラグのみから構成され、距離値は格納しない。
【００８５】
前記差異情報は、レンジブロックと対応されるドメインブロック間の差異情報であり、差異フラグおよび差異値からなる。ここで、差異フラグは、差異値の種類によって多様な形態に設定することができる。すなわち、差異値が一つの形態に生成される場合、差異フラグは１ビットを用いてセットまたはリセット状態に設定することができる。しかし、差異値が少なくとも２種類の形態を有する場合、形態の数によって差異フラグのビット数を決めることができる。本発明の実施形態では、上記のように、まず、レンジブロックと対応されるドメインブロック間の差異値をそのまま使用する方法、２番目に、グローバルテーブルを備え、レンジブロックとドメインブロックとの差異値を計算した後、差異値によるグローバルテーブルのテーブルインデックスを差異値に使用する方法、３番目に、グローバルテーブルおよびローカルテーブルを備え、レンジブロックとドメインブロック間の差異値を計算した後、差異値によるグローバルまたはローカルテーブルのテーブルインデックスを差異値に使用する方法、最後に、前記２番目および３番目の方法を使用する場合に、圧縮効果の小さいレンジブロックを例外処理ブロックに処理する方法の中から、いずれか一つの方法を使用することができる。
【００８６】
前記１番目の差異情報を生成する方法は、現在、圧縮対象であるレンジブロックと対応されるドメインブロック間の距離値が、以前圧縮対象であったレンジブロックと対応されるドメインブロックとで同一である場合、差異フラグはリセットされた状態(「０」)に設定し、そうでなければ(すなわち、二つのブロックが異なれば)、前記差異フラグはセット(「１」)に設定する。この時、前記二つのブロックの差異値は、レンジブロックとドメインブロックとを
1308722754188_0
1308722754188_1
演算した後、その演算の結果値を差異値に使用する。この場合、前記差異情報は、差異フラグがセット状態(「１」)であれば、前記差異フラグおよび対応されるドメインブロックの排他的論理和値(ｅｘｃｌｕｓｉｖｅ ＯＲ ｖａｌｕｅ)から構成され、差異フラグがリセット状態(「０」)であれば、差異フラグのみから構成され差異値は格納しない。
【００８７】
前記２番目の差異情報を生成する方法は、現在、圧縮対象であるレンジブロックと対応されるドメインブロック間の距離値が、以前圧縮対象であったレンジブロックと対応されるドメインブロックとで同一である場合、差異フラグはリセットされた状態(「０」)に設定し、そうでなければ（すなわち、二つのブロックが異なれば)、前記差異フラグはセット(「１」)に設定する。この時、前記二つのブロックの差異値は、レンジブロックとドメインブロックとを
1308722754188_2
1308722754188_3
演算した後、その演算結果値を用いてコストを計算する。また、このコストを用いてグローバルテーブルのテーブルインデックスを決定した後、前記決定されたテーブルインデックスを差異値に設定する。この場合、前記差異情報は、差異フラグがセット状態(「１」)であれば、差異フラグおよびグローバルテーブルのテーブルインデックスから構成され、差異フラグがリセット状態(「０」)であれば、差異フラグのみから構成され差異値は格納しない。ここで、グローバルテーブルは、前記レンジブロックとドメインブロック間の差異値が格納され、ここでの差異値は二つのブロック間の排他的論理和値である。
【００８８】
前記３番目の差異情報を生成する方法は、現在、圧縮対象であるレンジブロックと対応されるドメインブロック間の距離値が、以前圧縮対象であったレンジブロックと対応されるドメインブロックとで同一である場合、差異フラグはリセットされた状態(「０」)に設定し、そうでなければ(すなわち、二つのブロックが異なれば)、前記差異フラグはセット状態に設定する。この時、前記二つのブロックの差異値は、レンジブロックとドメインブロックとを
1308722754188_4
1308722754188_5
演算した後、その演算結果値を用いてコストを計算する。また、このコストを用いてグローバルまたはローカルテーブルのインデックスを決定した後、決定されたテーブルインデックスを差異値に設定する。ここで、グローバルテーブルは固定テーブルであり、ローカルテーブルは可変テーブルである。また、前記ローカルテーブル(可変テーブル)は、前記グローバルテーブルに存在しないが頻繁に発生する差異値を分析した後、圧縮ステップでテーブル化して生成されるテーブルである。この場合、前記圧縮機は、レンジブロックと該当するドメインブロックとの差異値をローカルテーブルに登録し、前記ローカルテーブルのテーブルインデックスをコストテーブルに登録する。前記差異情報は、差異フラグがセット状態(「０１」)であれば、前記差異フラグおよびグローバルテーブルのテーブルインデックスから構成され、差異フラグがセット状態(「１０」)であれば、前記差異フラグおよびローカルテーブルのテーブルインデックスから構成される。また、差異フラグがリセット状態(「０」)であれば、差異フラグのみから構成され差異値は格納しない。
【００８９】
前記４番目の差異情報を生成する方法は、グローバルテーブルを用いて圧縮する方法、または、グローバルテーブルおよびローカルテーブルを用いて圧縮する方法を使用する場合、レンジブロックおよびドメインブロックの差異値が前記テーブルに存在しない場合もある。この場合、レンジブロックのデータは圧縮しないほうがよいこともある。すなわち、前記のようなレンジブロックのデータを圧縮する方法は、デコーディング時に長い時間がかかる。そのため、レンジブロックとドメインブロックとの差異値がグローバルテーブルおよびローカルテーブルに登録されていない場合、当該レンジブロックのデータは例外ブロックに処理して圧縮しない方法を使用する。この場合(すなわち、二つのブロックの差異値が前記グローバルテーブルおよびローカルテーブルに存在しない場合)、前記差異フラグを例外処理フラグ(「１１」)にセットし、差異値はレンジブロックのデータをそのまま使用する。
【００９０】
圧縮機は、上記のように生成される差異情報を距離情報と共に該当するレンジブロックの圧縮データにコーディングする。上記のようにコーディングされた圧縮データはメモリに格納されるか、または、通信部を介して外部に伝送される。
【符号の説明】
【００９１】
２１０  ローダー
２２０  探索器
２４０  コーダー
２５０  例外ブロック処理部
【図１】
2011250431.tif 000005
【図２】
2011250431.tif 000006
【図３ａ】
2011250431.tif 000007
【図３ｂ】
2011250431.tif 000008
【図４】
2011250431.tif 000009
【図５】
2011250431.tif 000010
【図６】
2011250431.tif 000011
【図７ａ】
2011250431.tif 000012
【図７ｂ】
2011250431.tif 000013
【図８】
2011250431.tif 000014
【図９】
2011250431.tif 000015
【図１０】
2011250431.tif 000016
【図１１】
2011250431.tif 000017