(57)【要約】【課題】データ復号技術を提供する。【解決手段】  コンピュータに実装された方法は、第１エントロピー符号化ルックアップテーブルに従って各々の一連の画素データを符号化する一連の符号語を含むデータストリームの受信、および第２エントロピー符号化ルックアップテーブルに第１符号語および連続した第２符号語間の一致、および符号語エントリがあるかどうかを判断するための前記データストリームの処理を備える。前記方法には、また、一致がある場合、前記第２エントロピー符号化ルックアップテーブルを使用した前記第１符号語および前記第２符号語の復号を含む。さらに、前記方法には、一致がない場合、前記第１エントロピー符号化ルックアップテーブルを使用した前記第１符号語の復号を含む。【選択図】図１
2016178639.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータであって、
少なくとも１つのプロセッサと、
メモリと、
前記メモリに記憶されたプログラム命令であって、前記少なくとも１つのプロセッサによる実行の際に、前記コンピュータに、
第１エントロピー符号化ルックアップテーブルに従って各々の一連の画素データを符号化する一連の符号語を含むデータストリームを受信する工程と、
第２エントロピー符号化ルックアップテーブルに第１符号語および第２符号語間の一致、および符号語エントリがあるかどうか判断するためのデータストリームを処理する工程であって、前記第１符号語および前記第２符号語は、前記データストリーム内の連続した符号語であり、前記第２エントロピー符号化ルックアップテーブルは、前記第１エントロピー符号化ルックアップテーブルと異なる工程と、
前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリがある場合、前記第２エントロピー符号化ルックアップテーブルを使用して前記第１符号語および前記第２符号語を復号する工程と、
前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリがない場合、前記第１エントロピー符号化ルックアップテーブルを使用して前記第１符号語を復号する工程と、を含む工程を実施させるプログラム命令を備える、コンピュータ。
【請求項２】
請求項１に記載のコンピュータであって、さらに、
前記第１エントロピー符号化ルックアップテーブルの前記第１符号語および符号語エントリ間の一致を識別するために前記データストリームを処理する工程であって、前記コンピューティング・デバイスは、前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリがあるかどうか判断するための前記データストリームの処理と並行して、前記第１エントロピー符号化ルックアップテーブルの前記第１符号語および符号語エントリ間の一致を識別するために前記データストリームの処理を行う工程を実施させるプログラム命令を備える、コンピュータ。
【請求項３】
請求項１又は２に記載のコンピュータであって、
前記第２エントロピー符号化ルックアップテーブルは、一組の第１符号語および第２符号語をそれぞれが備える少なくとも複数のエントリを含む工程であって、前記各組の第１符号語は、ゼロのランに相当する前記第１エントロピー符号化ルックアップテーブルの１以上のエントリから選択され、前記各組の第２符号語は、ゼロのランまたは１のランに相当する前記第１エントロピー符号化ルックアップテーブルの１以上のエントリから選択されるコンピュータ。
【請求項４】
請求項３に記載のコンピュータであって、
前記第２エントロピー符号化ルックアップテーブルは、前記第１符号語および前記第２符号語の組の各固有の組み合わせを含むコンピュータ。
【請求項５】
請求項１乃至４のいずれか１項に記載のコンピュータであって、さらに、
前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリがある場合、前記第２エントロピー符号化ルックアップテーブルに第３符号語および第４符号語間の一致、および符号語エントリがあるかどうか判断するために前記データストリームを処理する工程であって、前記第１、第２、第３、および第４符号語は、前記データストリームの連続した符号語である工程を実施させるプログラム命令を備える、コンピュータ。
【請求項６】
請求項５に記載のコンピュータであって、さらに、
（ｉ）前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリ、および（ｉｉ）前記第２エントロピー符号化ルックアップテーブルに前記第３符号語および前記第４符号語間の一致、および符号語エントリがある場合、前記第２エントロピー符号化ルックアップテーブルを使用して前記第３符号語および前記第４符号語を復号する工程と、
（ｉ）前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリがある場合、および（ｉｉ）前記第２エントロピー符号化ルックアップテーブルに前記第３符号語および前記第４符号語間の一致、および符号語エントリがない場合、前記第１エントロピー符号化ルックアップテーブルを使用して前記第３符号語を復号する工程と、を実施させるプログラム命令を備えるコンピュータ。
【請求項７】
請求項１乃至６のいずれか１項に記載のコンピュータであって、さらに、
前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリがない場合、前記第２エントロピー符号化ルックアップテーブルに前記第２符号語および第３符号語間の一致、および符号語エントリがあるかどうか判断するために前記データストリームを処理する工程であって、前記第２および第３符号語は、前記データストリーム内の連続した符号語である工程を実施させるプログラム命令を備えるコンピュータ。
【請求項８】
請求項７に記載のコンピュータであって、さらに、
（ｉ）前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリがない場合、および（ｉｉ）前記第２エントロピー符号化ルックアップテーブルに前記第２符号語および前記第３符号語間の一致、および符号語エントリがある場合、前記第２エントロピー符号化ルックアップテーブルを使用して前記第２符号語および前記第３符号語を復号する工程と、
（ｉ）前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリがない場合、および（ｉｉ）前記第２エントロピー符号化ルックアップテーブルに前記第２符号語および前記第３符号語間の一致、および符号語エントリがない場合、前記第１エントロピー符号化ルックアップテーブルを使用して前記第２符号語を復号する工程と、
を実施させるプログラム命令を備えるコンピュータ。
【請求項９】
請求項１乃至８のいずれか１項に記載のコンピュータであって、
前記第２エントロピー符号化ルックアップテーブルを使用して前記第１符号語および前記第２符号語を復号する工程は、クロックサイクル・スループット当たり平均２画素を保証するコンピュータ。
【請求項１０】
請求項１乃至９のいずれか１項に記載のコンピュータであって、
前記第１エントロピー符号化ルックアップテーブルは、Ｈｕｆｆｍａｎエントロピー符号化ルックアップテーブルであるコンピュータ。
【請求項１１】
請求項１乃至１０のいずれか１項に記載のコンピュータであって、さらに、
前記第１符号語、または前記第１符号語および前記第２符号語の前記復号する工程に基づき、１以上の印刷エンジンまたは表示モニタに出力データストリームを提供する工程を実施させるプログラム命令を備えるコンピュータ。
【請求項１２】
請求項１１に記載のコンピュータであって、さらに、
１以上の前記印刷エンジンまたは前記表示モニタに前記出力データストリームを提供する工程の前に、前記出力データストリームを逆量子化する工程と、前記出力データストリームに逆空間周波数変換を実行する工程とを実施させるプログラム命令を備えるコンピュータ。
【請求項１３】
データストリームを復号するためのシステムであって、
前記データストリームを受信するための入力バッファであって、前記データストリームは、エントロピー符号化ルックアップテーブルに従って一連の符号語に符号化されたデータを含む入力バッファと、
前記入力バッファに接続されたプロセッサであって、
前記データストリーム内の連続した符号語がゼロのランまたは１のランに続くゼロのランに相当するかどうかを判断し、
前記連続した符号語がゼロのランまたは１のランに続くゼロのランに相当する場合、修正されたエントロピー符号化ルックアップテーブルを使用して前記連続した符号語を復号する工程の少なくとも一部に基づく出力を提供し、
前記連続した符号語がゼロのランまたは１のランに続くゼロのランに相当しない場合、前記エントロピー符号化ルックアップテーブルを使用して前記連続した符号語の第１符号語を復号する工程の少なくとも一部に基づく前記出力を提供するように構成されたプロセッサと、
を備えるシステム。
【請求項１４】
請求項１３に記載のシステムであって、
前記修正されたエントロピー符号化ルックアップテーブルは、一組の第１符号語および第２符号語をそれぞれが備える少なくとも複数のエントリを含み、前記各組の第１符号語は、ゼロのランに相当する前記エントロピー符号化ルックアップテーブルの１以上のエントリから選択され、前記各組の第２符号語は、ゼロのランまたは１のランに相当する前記エントロピー符号化ルックアップテーブルの１以上のエントリから選択されるシステム。
【請求項１５】
請求項１３又は１４に記載のシステムであって、
前記修正されたエントロピー符号化ルックアップテーブルを使用して前記連続した符号語を復号する工程の少なくとも一部に基づく前記出力を提供する工程は、クロックサイクル・スループット当たり平均２画素を保証するシステム。
【請求項１６】
請求項１３乃至１５のいずれか１項に記載のシステムであって、
前記エントロピー符号化ルックアップテーブルは、Ｈｕｆｆｍａｎエントロピー符号化ルックアップテーブルであるシステム。
【請求項１７】
請求項１３乃至１６のいずれか１項に記載のシステムであって、
前記入力バッファおよび前記プロセッサは、印刷デバイスに含まれるシステム。
【請求項１８】
コンピュータプログラムであって、
第１エントロピー符号化ルックアップテーブルに従って各々の一連の画素データを符号化する一連の符号語を含むデータストリームを受信する工程と、
第２エントロピー符号化ルックアップテーブルに第１符号語および第２符号語間の一致、および符号語エントリがあるかどうか判断するために前記データストリームを処理する工程であって、前記第１符号語および前記第２符号語は、前記データストリーム内の連続した符号語であり、前記第２エントロピー符号化ルックアップテーブルは、前記第１エントロピー符号化ルックアップテーブルと異なる工程と、
前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリがある場合、前記第２エントロピー符号化ルックアップテーブルを使用して前記第１符号語および前記第２符号語を復号する工程と、
前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリがない場合、前記第１エントロピー符号化ルックアップテーブルを使用して前記第１符号語を復号する工程と、
を備える一連の動作をプロセッサに実行させるプログラム。
【請求項１９】
請求項１８に記載のコンピュータプログラムであって、
前記一連の動作は、さらに、
前記第１エントロピー符号化ルックアップテーブルの前記第１符号語および符号語エントリ間の一致を識別するために前記データストリームを処理する工程であって、前記第１エントロピー符号化ルックアップテーブルの前記第１符号語および符号語エントリ間の一致を識別するために前記データストリームを処理する工程は、前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリがあるかどうか判断するために前記データストリームを処理する工程と並行して行われる工程を備えるプログラム。
【請求項２０】
請求項１８又は１９に記載のコンピュータプログラムであって、
前記第２エントロピー符号化ルックアップテーブルは、一組の第１符号語および第２符号語をそれぞれが備える少なくとも複数のエントリを含み、前記各組の第１符号語は、ゼロのランに相当する前記第１エントロピー符号化ルックアップテーブルの１以上のエントリから選択され、前記各組の第２符号語は、ゼロのランまたは１のランに相当する前記第１エントロピー符号化ルックアップテーブルの１以上のエントリから選択されるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ復号技術に関する。
【背景技術】
【０００２】
近年、さまざまな種類の印刷デバイスが業務用および民生用の両方で普及してきている。従来の白黒のプリンタに加え、カラープリンタ、スキャナ、コピー機、ファックス機、およびその他の装置も今日では一般的である。これらの機能の２つ以上に対応している複合機（ＭＦＰ）もまた広く普及している。他の機能のうち、これらの装置は画像データの処理に利用される。
【０００３】
画像データの処理には、例えば、圧縮および符号化操作、および／または解凍および復号操作を含めてもよい。画像処理技術の一例は、ジョイント・フォトグラフィック・エキスパート・グループ（ＪＰＥＧ）規格により定義される。一般に、画像データのＪＰＥＧ符号化処理には、空間周波数変換、量子化、データシーケンシング（順序付け）、およびエントロピー符号化が含まれ、画像データのＪＰＥＧ復号処理には、エントロピー復号のようなＪＰＥＧ符号化処理の逆、逆データシーケンシング（順序付け）、逆量子化、および逆空間周波数変換が含まれる。
【０００４】
より効率的で、確実な、およびより速いデータ処理に役立てるため、従来の方法およびシステムの配置が改善されること、または少なくとも１以上の有益な代替を提供することが望ましい。
【発明の概要】
【０００５】
例示の実施形態において、コンピュータに実装された方法は、コンピューティング・デバイスによる、第１エントロピー符号化ルックアップテーブルに従った各々の一連の画素データを符号化する一連の符号語を含むデータストリームを受信する工程、および前記コンピューティング・デバイスによる、第２エントロピー符号化ルックアップテーブルに第１符号語および第２符号語間の一致、および符号語エントリがあるかどうか判断するため前記データストリームを処理する工程を備える。本例では、前記第１符号語および前記第２符号語は、前記データストリーム内の連続した符号語であり、前記第２エントロピー符号化ルックアップテーブルは、前記第１エントロピー符号化ルックアップテーブルとは異なる。本例の方法には、また、前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリがある場合、前記コンピューティング・デバイスにより、前記第２エントロピー符号化ルックアップテーブルを使用して前記第１符号語および前記第２符号語を復号する工程が含まれる。さらに、本例の方法には、前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリがない場合、前記コンピューティング・デバイスにより、前記第１エントロピー符号化ルックアップテーブルを使用して前記第１符号語を復号する工程が含まれる。
【０００６】
他の例示の実施形態においては、データストリームの復号のためのシステムは、エントロピー符号化ルックアップテーブルに従って一連の符号語に符号化されたデータを含むデータストリームを受信するための入力バッファ、および前記入力バッファに接続されたプロセッサを備える。本例では、前記プロセッサは、データストリーム内の連続した符号語がゼロのランまたは１のランに続くゼロのランに相当するかどうか判断し、前記連続した符号語がゼロのランまたは１のランに続くゼロのランに相当する場合、修正されたエントロピー符号化ルックアップテーブルを使用した前記連続した符号語の復号の少なくとも一部に基づく出力を提供するように構成される。さらに、本例では、前記プロセッサは、前記連続した符号語がゼロのランまたは１のランに続くゼロのランに相当しない場合、前記エントロピー符号化ルックアップテーブルを使用した前記連続した符号語の第１符号語の復号の少なくとも一部に基づく出力を提供するように構成される。
【０００７】
さらなる例示の実施形態においては、コンピュータプログラムは、コンピューティング・デバイスによる、第１エントロピー符号化ルックアップテーブルに従って各々の一連の画素データを符号化する一連の符号語を含むデータストリームを受信する工程と、第２エントロピー符号化ルックアップテーブルに第１符号語および第２符号語間の一致、および符号語エントリがあるかどうか判断するためデータストリームを処理する工程とを備える一連の動作を実行させる。本例では、前記第１符号語および前記第２符号語は、前記データストリーム内の連続した符号語であり、前記第２エントロピー符号化ルックアップテーブルは、前記第１エントロピー符号化ルックアップテーブルとは異なる。本例では、前記一連の動作には、また、前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリがある場合、前記第２エントロピー符号化ルックアップテーブルを使用して前記第１符号語および前記第２符号語を復号する工程が含まれる。さらに、本例では、前記一連の動作には、前記第２エントロピー符号化ルックアップテーブルに前記第１符号語および前記第２符号語間の一致、および符号語エントリがない場合、前記第１エントロピー符号化ルックアップテーブルを使用して前記第１符号語を復号する工程が含まれる。
【０００８】
他の態様、有利な点、および代替案と同様、これらのことは、必要に応じて添付図面を参照して以下の詳細な説明を読むことによって当業者にとって明白になるであろう。さらに、本明細書における当該概要および他のセクションで提供されている説明は、請求されている主題を限定のためでなく例として示すことを意図していることを理解されたい。
【図面の簡単な説明】
【０００９】
【図１】従来のカスケード型Ｈｕｆｆｍａｎ復号器の図表ブロックおよび処理図を示す。
【図２】例示の実施形態に係るコンピューティング・デバイスを示す。
【図３】例示の実施形態に係るコンピューティング・デバイスのデータ処理構成要素をブロック図にて示す。
【図４】例示の実施形態に係る画像処理に利用する格納要素およびデータをブロック図にて示す。
【図５】８×８データブロック用の所定のデータシーケンスの一例を示す。
【図６】例示の実施形態に係るコンピューティング・デバイスのデータ処理構成要素をブロック図にて示す。
【図７】例示の実施形態に係る画像処理に利用する格納要素およびデータをブロック図にて示す。
【図８】例示の実施形態に従ったデータ復号器システムをブロック図にて示す。
【図９】例示の実施形態に従ったデータの復号方法を示す。
【発明を実施するための形態】
【００１０】
本明細書において、例示の方法およびシステムを記述する。さらに他の例示的な実施形態または特徴を利用してもよく、また本明細書において提示されている主題の主旨または範囲から逸脱することなく、その他の変更がなされてもよい。以下の詳細な説明において、本明細書の一部を構成する添付図面を参照する。
【００１１】
本明細書において記載されている例示的な実施形態は限定することを意図するものではない。本明細書において全般的に記載され、そして図面に示されているように、本開示の諸態様は、様々に異なる構成に配置し、置き換え、結合し、分割し、および設計することができ、そしてそれらの全てが本明細書において明瞭に熟慮されていることは容易に理解されるであろう。説明の目的のため、印刷デバイスおよび画像データの処理に関して、特徴および機能が説明される。しかしながら、本明細書中に開示される特徴および機能は、また、他のタイプのコンピューティング・デバイス（例えば、表示デバイス）、コンピューティング・デバイスの構成要素（例えば、データ復号器、プロセッサ、格納要素、など）、および他のタイプのデータ（例えば、音声データおよび／または映像データ）の処理に適用可能でもよい。
［１．概要］
【００１２】
印刷技術は、白黒画像のみを生成する簡単なドットマトリクスベースの出力デバイスから高解像度のカラー画像を生成することができる今日の進歩したレーザーベースの印刷デバイスへと過去３０年以上にわたって発展してきた。それと共に、最近の印刷デバイスは、また、コピー機、スキャナ、およびファックス機として機能してもよい。そうするため、印刷デバイスは、印刷しまたはファックスするために待ち行列に入れられた、またはスキャンされた多くの電子文書のための画像データを格納することができてもよい。従って、多くの印刷デバイスは、例えば、１以上のプロセッサ、データ記憶部、および入出力インターフェースを含めてもよいコンピューティング・デバイスの特殊な形態である。
【００１３】
住宅、企業または別の種類の場所で使用されるかどうかにかかわらず、印刷デバイスは、他のいろいろなコンピューティング・デバイスと通信可能に接続可能な共有のリソースであってもよい。従って、状況によっては、多くのコンピューティング・デバイスが印刷のために電子文書を印刷デバイスに送信する場合があるので、印刷デバイスに対する格納および処理の要求はかなり高い場合がある。一般的には、印刷デバイスは、早着順に一度に一つの電子文書を印刷、コピー、ファックス、および／またはスキャンすることがよくある。従って、印刷デバイスは、ともすれば、処理されるのを待っている多数の電子文書を格納してもよい。データ記憶部（例えば、ランダム・アクセス・メモリ（ＲＡＭ）、固体メモリ、ハードドライブメモリ、および／またはフラッシュメモリのようなメモリ）の費用は高価な可能性が高いため、印刷デバイスのデータ格納要件を減少するために、格納された電子文書を圧縮することは有益かもしれない。それと共に、電子文書によっては印刷デバイスおよびコンピューティング・デバイスに、および／または印刷デバイスおよびコンピューティング・デバイスに、および／またはから転送される可能性があるため、これらの電子文書を圧縮することは、転送をより速くし、ネットワーク容量の利用をより少なくするかもしれない。
【００１４】
さらに、印刷ジョブは大きい可能性があるため（例えば、印刷ジョブには何百ものページを含む１以上の電子文書を含む可能性がある）、待ち行列に並んだ印刷ジョブを圧縮することにより、各ジョブの印刷前の短期的なストレージスペースが省かれる。これに加えて、ユーザは、後で印刷するために長期的なストレージに印刷ジョブを保存することを望むかもしれない。このように、印刷ジョブの圧縮は、より多くの印刷ジョブの保存を可能にするかもしれない。さらに、大きな印刷ジョブを長期メモリに保存し、取得する動作は時間がかかる可能性があるが、印刷ジョブを圧縮してサイズを小さくすることより、動作が速められるかもしれない。
【００１５】
印刷ジョブ（および他のタイプのデータ）を圧縮し、続いて解凍する１つ技術では、エントロピー符号化を利用する。Ｈｕｆｆｍａｎ符号化は、画像データ、映像データ、音声データ、などを圧縮するために通常利用されるエントロピー符号化の一例である。一般に、Ｈｕｆｆｍａｎ符号化は、統計的確率に従って割り当てられる可変長のバイナリコードまたは符号語で記号（例えば、画素データ、ＤＣＴ係数、音声データ、など）を符号化する。例えば、より頻繁に利用される記号には、長さ２〜３ビットのみのコードが割り当てられ、あまり頻繁に利用されない記号には、ビット数が増加した長さ（例えば、長さ１６ビットまで）のコードが割り当てられる。Ｈｕｆｆｍａｎ符号化では、データを符号化および復号するための各々可能性のある可変長コードをリスト化するルックアップテーブルを利用する。Ｈｕｆｆｍａｎテーブルの一例は、表Ｋ．５もおいてＪＰＥＧ規格（ＩＳＯ／ＩＥＣ１０９１８）で提供される。表Ｋ．５は付録（  「ＪＰＥＧ・Ｈｕｆｆｍａｎルックアップテーブル」）で本明細書に添付される。Ｈｕｆｆｍａｎテーブルの他の例もまた可能であり、本開示の適用範囲である。
【００１６】
Ｈｕｆｆｍａｎ符号化では可変長コードを利用するため、Ｈｕｆｆｍａｎ符号化が行われたデータのストリームの復号は、データのストリーム内の各コードが次のコードが決定される前に決定されるように、本来順次的である。従来の復号器は、クロックレートまたはサイクル当たり１コードで動作する。通常、各Ｈｕｆｆｍａｎコードには、クロックレート当たりの画素の平均解凍率が適切に高くなるように、多数の画素が含まれる。しかしながら、アプリケーションによっては、保証された画素スループット（例えば、クロック当たり２画素）を必要とし、一時的な最悪な状況、つまりクロック当たりの１画素の低画素率が、データアンダーランおよび画像アーチファクトを引き起こす可能性がある。実際、２画素／クロック未満のスループットは、例えば、画像の非常にざらつく領域である可能性が高い。
【００１７】
２画素／クロック・スループットを保証する従来の試みには、様々な欠点がある。あるアプローチにおいては、２つのカスケード型Ｈｕｆｆｍａｎ復号器は少なくとも２画素／クロックを復号できるが、このスループットは処理論理のクリティカル・パスの遅延を倍にする犠牲を払う。図１を参照すると、例えば、第１Ｈｕｆｆｍａｎ復号器を第２Ｈｕｆｆｍａｎ復号器にカスケード接続すると、２つの完全なＨｕｆｆｍａｎルックアップテーブルを使用したデータストリームの処理のため、基本的にクリティカル・パスの遅延が倍になる。Ｈｕｆｆｍａｎルックアップテーブルは、基本的に最大処理周波数を半分にカットする。ＪＰＥＧ処理に通常利用される１６０エントリのＨｕｆｆｍａｎルックアップテーブルの場合、比較的大きなＨｕｆｆｍａｎルックアップテーブルは、カスケード型復号器が実行できる最大クロック周波数を制限する。
【００１８】
他のアプローチにおいては、並行なＨｕｆｆｍａｎ復号器が少なくとも２画素／クロックを復号するために利用される。しかしながら、このアプローチでは、並行なＨｕｆｆｍａｎ復号器のために別々のデータストリームを生成するために追加のデータバッファおよび動的なメモリ割り当てを利用する。データストリームを復号するために利用されるコンピューティング・デバイスによっては、このような追加のデータバッファが利用できないかもしれない。これに加えて、この状況における追加のデータバッファおよび動的なメモリ割り当ての利用は、メモリフラグメンテーションを増加させ、処理レイテンシを増加させる可能性がある。
【００１９】
本開示では、平均２画素／クロックの復号スループット（例えば、２クロックサイクル・スループット当たり４画素）を保証する確実で効率的なアプローチを提供する。開示されたアプローチでは、符号化されたデータストリームを復号する修正されたＨｕｆｆｍａｎルックアップテーブルを利用する。比較的大きなＪＰＥＧ・Ｈｕｆｆｍａｎルックアップテーブルを参照すると、エントリの内１０のみがゼロのランに相当する。一般に、ランレングスは、ゼロ振幅ＡＣ係数のランの長さに相当する。この状況において、ゼロのランは、最後の（復号された）ＡＣ係数および次の非ゼロＡＣ係数間にゼロ振幅のＡＣ係数がないことを意味し、１のランは、１つの非ゼロ振幅のＡＣ係数に続く１つのゼロ振幅のＡＣ係数があることを意味し、２のランは、１つの非ゼロ振幅のＡＣ係数に続く２つのゼロ振幅のＡＣ係数があることを意味し、整数（ｎ）のランは、１つの非ゼロ振幅のＡＣ係数に続くｎ個のゼロ振幅のＡＣ係数があることを意味する。
【００２０】
ＪＰＥＧ・Ｈｕｆｆｍａｎルックアップテーブル（および他の可変または固定長の符号化テーブル）のゼロのランの符号語は、２画素／クロックのスループットを保証するためクロック当たり１符号語より速く復号する必要があるという唯一のケースである。これは、１倍のランが２画素／クロック復号率（ゼロ振幅のＡＣ係数画素および１つの非ゼロ振幅のＡＣ係数画素）となり、２倍のランが３画素／クロック復号率となり、３倍のランが４画素／クロック復号率となり、ｎ倍のランが（ｎ＋１）画素／クロック復号率となるスループットだからである。
【００２１】
本開示では、ゼロのランに応じた完全なルックアップテーブルのエントリをゼロのランまたは１のランに応じた完全なルックアップテーブルのエントリにカスケード接続する修正された符号化ルックアップテーブルを利用する。得られた修正された符号化ルックアップテーブルによれば、従来の技術のように、完全なルックアップテーブルの全体をカスケード接続することなく、１クロックサイクルで２つの符号語を復号する復号器が可能になる。要するに、現在の符号語が１画素に相当し、次の符号語が１または２画素に相当する場合、これらの連続した符号語は、修正された符号化ルックアップテーブルを使用して共に復号される。そうでない場合は、１つの符号語（２以上のランは、３以上の画素に相当する）は、スループット率が２画素／クロック以下に減少することなく、クロックサイクルごとに復号できる。
【００２２】
カスケード型復号器に比べて、上記のように、完全なルックアップテーブルに加え、および並行して、修正された符号化ルックアップテーブルを使用したこのアプローチは、およそ同量の回路および論理（例えば、ルックアップテーブルに２００以上のエントリを持つことにより）を必要とする。しかしながら、符号語ペア復号は通常の復号処理と並行して起こるため、カスケード型復号器のような直列復号と対照的に、開示されたアプローチは本質的により高速である。
［２．印刷デバイスの例］
【００２３】
図２は、例示の印刷デバイス２０を示す。印刷デバイス２０は、様々なタイプの物理的出力媒体に部分的に記憶された、および／または全て記憶された電子文書を印刷するように構成されてもよい。これらの出力媒体には、様々なサイズおよびタイプの用紙、オーバーヘッド・スライドなどが含まれるが、これに限定されない。印刷デバイス２０を、「プリンタ」と区別しないで呼んでもよい。
【００２４】
印刷デバイス２０は、パーソナルコンピュータ、表示モニタ、サーバ装置、印刷サーバなどのような他のコンピューティング・デバイスへのローカル周辺機器として機能してもよい。これらの場合、印刷デバイス２０は、シリアルポートケーブル、パラレルポートケーブル、ユニバーサル・シリアル・バス（ＵＳＢ）ケーブル、Ｆｉｒｅｗｉｒｅ（ＩＥＥＥ１３９４）ケーブル、または高精細度マルチメディアインターフェース（ＨＤＭＩ（登録商標））ケーブルのようなケーブルにより、コンピューティング・デバイスに備え付けられてもよい。このように、コンピューティング・デバイスは、印刷デバイス２０用の電子文書のソースとして機能してもよい。
【００２５】
一方、印刷デバイス２０には、イーサネット（登録商標）またはＩＥＥＥ８０２．１１（ＷＬＡＮまたはＷｉ−Ｆｉ）インターフェースのような、有線または無線ネットワークインターフェースを含めてもよい。そのように配置された場合、印刷デバイス２０は、印刷デバイス２０とネットワークを介して通信可能な任意の数のコンピューティング・デバイス用の印刷デバイスとして機能してもよい。実施形態によっては、印刷デバイス２０は、ローカル周辺機器およびネットワーク化されたプリンタの両方として同時に機能してもよい。印刷デバイス２０を利用するために、コンピューティング・デバイスは、１以上のプリンタドライバをインストールしてもよい。これらのプリンタドライバには、印刷される電子文書を表す画像データをコンピューティング・デバイスに記憶された様々なローカル表現から印刷デバイス２０によりサポートされる１以上の表現に変換するソフトウェア構成要素を含めてもよい。それでも、印刷デバイス２０をコンピューティング・デバイスとみなしてもよいし、印刷関連および非印刷関連タスクの両方を実行してもよい。
【００２６】
上述したように、印刷デバイス２０にはまた、コピー機、ファクス、およびスキャナ機能を含めてもよい。実施形態によっては、印刷デバイス２０は、コピー機および／またはファクス機能を簡略化するスキャナ機能を利用してもよい。例えば、印刷デバイス２０は、物理的文書を電子フォーマットにスキャンした後、コピーを提供するために得られた電子文書を印刷、および／またはファクス機能を提供するために電話インターフェースを介して得られた電子文書を送信してもよい。
【００２７】
その様々な機能をサポートするために、印刷デバイス２０には、原稿送り装置／出力トレイ２２、用紙保管部２４、ユーザインターフェース２６、スキャン要素２８、および筐体３０を含めてもよい。印刷デバイスは多種多様な形をとってもよいことは、理解されるべきである。そのため、印刷デバイス２０には、図１に示されているよりも多い、または少ない構成要素、および／または図１に示されている方法とは異なる方法で配置された構成要素を含めてもよい。
【００２８】
原稿送り装置／出力トレイ２２は、スキャン、コピー、またはファクスされる物理的文書（例えば、１枚以上の用紙の積み重ね）を保持してもよい。原稿送り装置／出力トレイ２２は、手動での介入を必要とすることなしに、印刷デバイス２０により処理される多数の物理的文書の自動的な搬送を印刷デバイス２０に許可にしてもよい。原稿送り装置／出力トレイ２２にはまた、印刷デバイス２０により処理された物理的文書を保持する１以上の別々の出力トレイを含めてもよい。これらには、例えば、印刷デバイス２０のファクスおよび／またはコピー機能で作成された物理的文書と同様に、印刷デバイス２０によりスキャン、コピー、またはファクスされた物理的文書を含めてもよい。
【００２９】
用紙保管部２４には、様々なタイプの物理的媒体のためにトレイおよび／または搬送要素を含めてもよい。例えば、用紙保管部２４には、８．５×１１インチ用紙、Ａ４用紙、レターヘッドのある用紙、封筒などのための別々のトレイを含めてもよい。物理的媒体の作成（例えば、ファクスの印刷、コピー、および／または受信）を含む印刷デバイス２０の任意の機能のため、用紙保管部２４は物理的媒体を供給してもよい。
【００３０】
ユーザインターフェース２６は、ユーザから入力を受信およびユーザに出力を提供するような、人間または人間でないユーザと印刷デバイス２０の相互作用を簡略化してもよい。よって、ユーザインターフェース２６には、キーパッド、キーボード、タッチセンサー式または存在感知パネル、ジョイスティック、マイクロホン、さらにカメラおよび／またはビデオ・カメラのような入力構成要素を含めてもよい。ユーザインターフェース２６にはまた、既知のまたは今後開発される、（例えば、存在感知パネルに結合されてもよい）表示画面、陰極線管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）、発光ダイオード（ＬＥＤ）ベースのディスプレイ、デジタル光処理（ＤＬＰ（登録商標））技術を使用したディスプレイ、電球、および／または他の１以上の同様な装置のような、１以上の出力構成要素を含めてもよい。ユーザインターフェース２６はまた、既知または将来開発される、スピーカ、スピーカジャック、音声出力ポート、音声出力装置、イヤホン、および／または他の同様な装置を介して、可聴出力を生成可能に構成されてもよい。
【００３１】
スキャン要素２８はガラスパネルでよく、ガラスパネルの下では移動可能な光源が動作し、ガラスパネルの上に置かれた物理的媒体をスキャンする。あるいは、ガラスパネルの下のデジタルカメラが、物理的媒体の写真を撮ることによりガラスパネルの上に置かれた物理的媒体を「スキャン」してもよい。スキャンされた物理的媒体の画像は、印刷デバイス２０に関連付けられているデータ記憶部に記憶されてもよい。
【００３２】
筐体３０には、原稿送り装置／出力トレイ２２、用紙保管部２４、ユーザインターフェース２６、およびスキャン要素２８のような、印刷デバイス２０の様々な構成要素を含む、および／または相互接続する物理的ハウジングを含めてもよい。それと共に、筐体３０は、図１には図示されない他の構成要素を収容してもよい。例えば、筐体３０には、１以上のトナーカートリッジ、液体インクジェット、ベルト、ローラ、および／または電源を含めてもよい。さらに、筐体３０には、有線および／または無線ネットワークインターフェース、電話による通信インターフェース（例えば、ＲＪ４５ジャック）、ＵＳＢインターフェース、ＢＬＵＥＴＯＯＴＨ（登録商標）インターフェース、カードリーダーポートなどのような、通信インターフェースを含めてもよい。
【００３３】
さらに、印刷デバイス２０が多目的および／または特別に設計されたコンピューティング・デバイス構成要素に基づいてもよいように、筐体３０もまた、これらの構成要素のいくつかまたは全てを収容してもよい。例えば、印刷デバイス２０には、プロセッサおよびデータ記憶部（明示的に図示せず）を含めてもよい。一般に、プロセッサには、１以上の汎用プロセッサおよび／または１以上の専用プロセッサ（例えば、特定用途向け集積回路（ＡＳＩＣ）またはデジタル・シグナル・プロセッサ（ＤＳＰ）、など）のような１以上の中央処理装置（ＣＰＵ）を含めてもよい。データ記憶部は、揮発性および／または不揮発性データ記憶部を含めてもよく、プロセッサと全体または一部統合可能である。データ記憶部は、本明細書中に説明されている様々な方法、処理、または機能を実行するため、プロセッサにより実行可能なプログラム命令、およびこれらの命令により操作されるデータを記憶してもよい。あるいは、これらの方法、処理、または機能は、ハードウェア、ファームウェア、および／またはハードウェア、ファームウェア、およびソフトウェアの任意の組み合わせにより定義可能である。従って、データ記憶部には、有形で非一時的なコンピュータ読み取り可能な記録媒体を含めてもよく、記録媒体には、１以上のプロセッサによる実行に応じて、本明細書または添付図面に開示されている方法、処理、または機能のいずれかを印刷デバイス２０に実行させるプログラム命令が記憶されている。
【００３４】
さらに、印刷デバイス２０の構成要素には、また、画像データを圧縮／符号化および／または解凍／復号するためのハードウェアおよび／またはソフトウェア構成要素を含めてもよい。
［３．符号化器および復号器の例］
【００３５】
図３および図６は、印刷デバイス２０に含まれてもよいコンピューティング・デバイス構成要素（例えば、コンピューティング・デバイスの機能要素）の例示の実施形態を示す。最初に図３を参照すると、例示の画像データ符号化器４０が示されている。符号化器４０は、画像データ４２を受け取るように構成されている。図示の例において、画像データ４２は、画像データブロック（例えば、８×８画素ブロック）に分割されており、画像データブロックは、符号化器４０の空間周波数変換器４４に提供される。空間周波数変換器４４は、画像データへ離散コサイン変換（ＤＣＴ）の実行等、空間周波数変換を行う。画像データに空間周波数変換を行うことにより、画像データブロックに対する空間周波数変換を表す１以上の周波数係数のセットをもたらす。８×８画素ブロックの例において、空間周波数変換器４４は、単一のクロックサイクルで１個と６４個の間の周波数係数を生成するように構成されている。図４を参照して、一例を挙げれば、当該得られた周波数係数Ｓｕｖは、格納要素６０に格納されてもよい。別の例では、得られた１個乃至６４個の周波数係数Ｓｕｖのセットは、別個に格納される必要はなく、量子化器およびデータシーケンサによる単一操作（例えば、単一クロックサイクル）で操作される。
【００３６】
例えば，１個乃至６４個の周波数係数Ｓｕｖのセットは、次に直ちに量子化器４６により操作されてもよい。量子化器４６は、１以上の量子化された周波数係数のセット等、量子化されたデータを生成する。一般に、量子化は、画像データが空間周波数変換操作により周波数領域に変換された後で、高周波成分を低減または除去するための処理である。量子化器４６は、量子化係数を含む量子化テーブルを用いて、周波数係数を操作する。より具体的には、符号化器４０において、量子化器４６は、周波数係数Ｓｕｖを対応する量子化係数で除算して量子化された周波数係数のセットを生成する。図４は、量子化係数Ｑｕｖが、格納要素６２に格納されてもよく、またはそうでない場合、クロックサイクルごとに１個または６４個までの量子化係数Ｑｕｖが使用できる量子化器に対して入力として使用可能とされる例を示す。量子化器４６は、また、除算の結果を丸めて重要でない高周波成分を除去してもよい。
【００３７】
本例において、量子化器４６により生成された量子化された周波数係数Ｓｑｕｖのセットは、次に、直ちに、単一操作または単一クロックサイクルで、データシーケンサ４８に提供されてもよい。データシーケンサ４８は、量子化された周波数係数Ｓｑｕｖのセットを所定のシーケンスで配列するように構成されている。そのような一つのシーケンスは、図５で示されているジグザグシーケンスである。図４は、また、ジグザグシーケンス操作を実行するハードウェアおよび／またはソフトウェア構成要素を表すブロック６４を示す。
【００３８】
所定のシーケンスに配列された得られた量子化された周波数係数Ｓｑｕｖのセットは、格納要素６６に格納されてもよい。他の例では、得られた１個乃至６４個の量子化された周波数係数Ｓｑｕｖのセットは、別個に格納される必要はなく、データ符号化器５０により単一操作（例えば、単一クロックサイクル）で操作される。データ符号化器５０は、ストレージ、転送、または他の処理のため符号化されたデータ５２を提供するため、抽出された、量子化された周波数係数ＳｑｕｖにエントロピーまたはＨｕｆｆｍａｎ符号化を実行する。
【００３９】
次に図６および図７を参照すると、例示の画像データ復号器７０が示されている。復号器７０は、符号化された画像データ５２（例えば、図３の符号化データ）を受け取るように構成されている。図示されている例では、符号化データは、直ちにデータ復号器７２に提供される。データ復号器７２は、データ符号化器５０の逆の機能、例えば、逆エントロピーまたはＨｕｆｆｍａｎ復号を実行し、量子化された周波数係数Ｓｑｕｖを生成する。８×８画素ブロックの例において、データ復号器７２は、単一のクロックサイクルで、１個と６４個の間の量子化された周波数係数Ｓｑｕｖを生成するように構成されている。係数Ｓｑｕｖの数は、一つには、受け取られた符号化された画像データに依存してもよい。図７において、一例を挙げれば、得られた量子化された周波数係数Ｓｑｕｖは、格納要素９０に格納されてもよい。別の例では、得られた１個乃至６４個の量子化された周波数係数Ｓｑｕｖのセットは、別個に格納される必要はなく、より詳細に後述されるように、データ逆シーケンサ、および逆量子化器により単一操作（例えば、単一クロックサイクル）で操作される。
【００４０】
本例では、１個乃至６４個の量子化された周波数係数Ｓｑｕｖのセットは、図３のデータシーケンサ４８の操作に起因する所定のシーケンスで配列されてもよい。従って、量子化された周波数係数Ｓｑｕｖは、データ逆シーケンサ７４に提供されてもよく、データ逆シーケンサ７４は量子化された周波数係数Ｓｑｕｖを所定のシーケンスの逆に配列する。図７を参照して、一例を挙げれば、再配列された、得られた量子化された周波数係数Ｓｑｕｖは、格納要素９２に格納されてもよい。
【００４１】
別の例では、再配列された、得られた量子化された周波数係数Ｓｑｕｖは別個に格納される必要はなく、データ逆シーケンサ７４の後に、量子化された周波数係数Ｓｑｕｖは直ちに逆量子化器７６に提供され、逆量子化器７６は、量子化された周波数係数Ｓｑｕｖを逆量子化する。一例において、逆量子化器７６は、図３の量子化器４６に関連して上述したときと同じ量子化テーブルおよび量子化係数を用いる。しかしながら，逆量子化器７６は量子化された周波数係数Ｓｑｕｖに対応する量子化係数Ｑｕｖを掛ける、そして量子化器４６により実行された丸めの逆を実行して周波数係数Ｓｕｖを抽出する。周波数係数Ｓｕｖは、格納要素９４に記憶されてもよく、直ちに逆空間周波数変換器７８に提供されてもよい。逆空間周波数変換器７８は、表示、印刷、または他の処理のため元の画像データ４２を抽出するために、図３の変換器４４により実行された空間周波数変換の逆を実行する。
［４．復号器システムの例］
【００４２】
次に図８を参照して、例示の復号器システム１００を説明する。図８において、システム１００には、エントロピー符号化ルックアップテーブルに従って各々の一連の画素データ（例えば、ＤＣＴ係数）を符号化する一連の可変長符号語を含む、次に来るデータストリーム１０４を受信するように構成されたバッファ要素１０２が含まれる。一例では、第１エントロピー符号化ルックアップテーブルは、全１６０エントリを含むＪＰＥＧ・Ｈｕｆｆｍａｎルックアップテーブルである。第１符号化ルックアップテーブル（例えば、画素データを符号化するために利用される同一の「完全な」エントロピー符号化ルックアップテーブル）を利用するブロック１０６（例えば、プロセッサまたは処理論理）による処理のため、および第２符号化ルックアップテーブルを利用するブロック１０８（例えば、ブロック１０６と同一または異なるプロセッサまたは処理論理）による処理のために、バッファ要素１０２から、データストリーム１０４（またはそれに続く部分）が提供される。
【００４３】
本例では、第２符号化ルックアップテーブルは、第１エントロピー符号化ルックアップテーブルの修正バージョンであり、一組の第１符号語および第２符号語をそれぞれが備える複数のエントリが含まれる。例えば、各組の第１符号語は、ゼロのランに相当する第１ルックアップテーブルの１以上のエントリから選択され、各組の第２符号語は、ゼロのランまたは１のランに相当する第１ルックアップテーブルの１以上のエントリから選択される。ＪＰＥＧ・Ｈｕｆｆｍａｎルックアップテーブルを参照すると、ゼロのランに相当する１０の符号語および１のランに相当する１０の符号語がある。本例では、第２符号化ルックアップテーブルには、ゼロのランの符号語または１のランの符号語に続くゼロのランの符号語の各組み合わせが含まれる。ＪＰＥＧ・Ｈｕｆｆｍａｎルックアップテーブルに基づき、このような修正された、第２符号化ルックアップテーブルには、一般に以下のような２００のエントリが含まれ得る。
（ゼロのランの符号語に続くゼロのランの符号語）
０／１＿０／１、０／１＿０／２、…、０／１＿０／Ａ、
０／２＿０／１、０／２＿０／２、…、０／２＿０／Ａ、
０／３＿０／１、０／３＿０／２、…、０／３＿０／Ａ、
…
０／Ａ＿０／１、０／Ａ＿０／２、…、０／Ａ＿０／Ａ、
（１のランの符号語に続くゼロのランの符号語）
０／１＿１／１、０／１＿１／２、…、０／１＿１／Ａ、
０／２＿１／１、０／２＿１／２、…、０／２＿１／Ａ、
０／３＿１／１、０／３＿１／２、…、０／３＿１／Ａ、
…
０／Ａ＿１／１、０／Ａ＿１／２、…、０／Ａ＿１／Ａ、
【００４４】
第１および第２符号化ルックアップテーブル・ブロック１０６、１０８では、受信されたデータストリーム内の符号語および各々のルックアップテーブルのエントリ間の一致を識別するため、データストリーム１０４を並行に処理する。ブロック１０６は、第１符号化ルックアップテーブルの一致する符号語エントリを見つけるため、一度にデータストリーム１０４を１符号語毎に処理し、一致する符号語を出力１１０として、選択部要素１１２に提供する。選択部要素１１２は、複数の入力から出力を選択的に提供するように構成された優先度ベースのマルチプレクサまたは他のハードウェアおよび／またはソフトウェア構成要素でもよい。
【００４５】
ブロック１０８では、第２符号化ルックアップテーブルを使用してデータストリーム１０４を処理し、データストリーム１０４がゼロのランまたは１のランに続くゼロのランに相当する連続した符号語を含むかどうか判断する。ブロック１０８で、データストリーム内の連続した符号語の一致および第２符号化ルックアップテーブルの符号語エントリがあると判断された場合、ブロック１０８では一致する組の符号語を出力１１４として、選択部要素１１２に提供する。ブロック１０８で一致があると判断されると、ブロック１０８では選択部要素１１２に出力１１４に基づき出力１１６を選択的に提供するように指示する優先信号を提供する。ブロック１０８で一致がないと判断されると、ブロック１０８では優先信号を提供せず（あるいは異なる信号を提供し）、そして、異なる信号は、選択部要素１１２に出力１１０に基づき出力１１６を選択的に提供するように指示する。
【００４６】
図８の例において、パッキング論理ブロック１１８は選択部要素１１２から出力１１６を受信し、ブロック１０６からの可変長符号語出力１１０またはブロック１０８からの可変長符号語ペア出力１１４を固定長キューである画素キュー１２０にパックするように構成される。図８のシステム１００にはまた、逆データシーケンシング（順序付け）、逆量子化、逆空間周波数変換などのような機能を行うように構成される１以上の復号ステージ１２２が含まれる。さらに、図８の例において、出力デバイス１２４は、復号ステージ１２２に接続される。本例において、出力デバイス１２４は、復号ステージ１２２により処理されたように、画素キュー１２０のコンテンツを画像の対応する部分を印刷するための制御信号に変換するように構成された印刷エンジンでもよい。出力デバイス１２４にはまた、画素キュー１２０のコンテンツを画像の対応する部分を表示するための制御信号に変換するように構成された、表示モニタのような、いくつかの他の表示デバイスを含めてもよい。
【００４７】
システム１００において、ブロック１０６、１０８はまた、バッファ要素１０２に接続されるフィードバック出力１２６を提供するように構成されてもよく、バッファ要素１０２はハードウェアおよび／またはソフトウェアベースのピッカーブロックとしても機能できる。より具体的には、ブロック１０６、１０８がデータストリーム１０４内で可変長符号語を識別する場合、ブロック１０６、１０８は、符号語の長さをピッカーブロック（バッファ要素１０２）に通知するため、フィードバック出力１２６を生成してもよい。ピッカーブロック（バッファ要素１０２）は続いて、ビットの可動ウィンドウをシフトさせ、処理のためブロック１０６、１０８にデータストリームの次に続く部分を提供してもよい。
［５．操作の例］
【００４８】
上記に加え、図９は例示の実施形態のフローチャートを示す。本フローチャートにより説明されるステップは、印刷デバイス２０、復号器７２、およびシステム１００のような、１以上のコンピューティング・デバイス、システム、またはその構成要素により実行されてもよい。さらに、各個別のステップの態様は、必要に応じて多数のコンピューティング・デバイス間で分けられてもよい。
【００４９】
図９は、例えば、図６および図８の構成要素を利用可能な例示の符号化処理１５０を示す。処理１５０のブロック１５２において、システム１００は、例えば、第１エントロピー符号化ルックアップテーブルに従って各々の一連の画素データを符号化する符号語を含むデータストリームを受信する。例えば、第１エントロピー符号化ルックアップテーブルは、本明細書中に説明されているＪＰＥＧ・Ｈｕｆｆｍａｎルックアップテーブルであり得る。
【００５０】
ブロック１５４において、システム１００はデータストリームを処理し、第２エントロピー符号化ルックアップテーブルに第１符号語および第２符号語間の一致、および符号語エントリがあるかどうか判断する。本例において、第１符号語および第２符号語は、データストリーム内の連続した符号語であり、第２エントロピー符号化ルックアップテーブルは、図８の第２符号化ルックアップテーブル・ブロック１０８により利用された、修正された符号化ルックアップテーブルであり得る。ブロック１５６において、システム１００はデータストリームを処理し、第１エントロピー符号化ルックアップテーブルの第１符号語および符号語エントリ間の一致を識別する。一例において、ブロック１５６におけるこの処理は、ブロック１５４の処理と並行に行われる。
【００５１】
ブロック１５８において、第２エントロピー符号化ルックアップテーブルに第１符号語および第２符号語間の一致、および符号語エントリがある場合、システム１００は、第２エントロピー符号化ルックアップテーブルを使用して第１符号語および第２符号語を復号、またはそうでない場合は、出力として提供する。ブロック１６０において、第２エントロピー符号化ルックアップテーブルに第１符号語および第２符号語間の一致、および符号語エントリがない場合、システム１００は、第１エントロピー符号化ルックアップテーブルを使用して第１符号語を復号、またはそうでない場合は、出力として提供する。
【００５２】
図９の例では、ブロック１６２において、システム１００は処理を次の符号語のセットにシフトさせる。一実施形態に従って、システム１００がブロック１５４において一致を識別しない場合、続いてブロック１６２において、システム１００は１符号語ずつ処理をシフトさせ、制御はブロック１５４に戻って受信されたデータストリームの処理を続ける。その結果として、ブロック１５４の次の反復において、システム１００は第２エントロピー符号化ルックアップテーブルに第２符号語および次の連続した（第３）符号語間の一致、および符号語エントリがあるかどうか判断する。さらに、ブロック１５６の次の反復において、システム１００はデータストリームを処理し、第１エントロピー符号化ルックアップテーブルの第２符号語および符号語エントリ間の一致を識別する。その後、ブロック１５８において、第２エントロピー符号化ルックアップテーブルに第２符号語および第３符号語間の一致、および符号語エントリがある場合、システム１００は第２エントロピー符号化ルックアップテーブルを使用して第２符号語および第３符号語を復号、またはそうでない場合は、出力として提供する。ブロック１６０において、第２エントロピー符号化ルックアップテーブルに第２符号語および第３符号語間の一致、および符号語エントリがない場合、システム１００は第１エントロピー符号化ルックアップテーブルを使用して第２符号語を復号、またはそうでない場合は、出力として提供する。
【００５３】
ブロック１６２を再び参照すると、本実施形態に従って、システム１００がブロック１５４において一致を識別する場合、続いてブロック１６２において、システム１００は２符号語ずつ処理をシフトさせ、制御はブロック１５４に戻って受信されたデータストリームの処理を続ける。その結果として、ブロック１５４の次の反復において、システム１００は第２エントロピー符号化ルックアップテーブルに次の連続した一組の符号語（例えば、第３および第４符号語）間の一致、および符号語エントリがあるかどうか判断する。さらに、ブロック１５６の次の反復において、システム１００はデータストリームを処理し、第１エントロピー符号化ルックアップテーブルで第３符号語および符号語エントリ間の一致を識別する。その後、ブロック１５８において、第２エントロピー符号化ルックアップテーブルに第３符号語および第４符号語間の一致、および符号語エントリがある場合、システム１００は第２エントロピー符号化ルックアップテーブルを使用して第３符号語および第４符号語を復号、またはそうでない場合は、出力として提供する。ブロック１６０において、第２エントロピー符号化ルックアップテーブルに第３符号語および第４符号語間の一致、および符号語エントリがない場合、システム１００は第１エントロピー符号化ルックアップテーブルを使用して第３符号語を復号、またはそうでない場合は、出力として提供する。
【００５４】
一般に、ブロック１６２における処理は、符号語が復号されて出力に提供されるように、データストリームを通して順次横断する可動ウィンドウを提供する。
［６．結論］
【００５５】
本出願において記述されている具体的な実施形態に関して、本開示は限定されるべきではなく、それらはいろいろな態様の実例として意図されている。当業者にとって明白であるように、本開示の主旨と範囲から逸脱することなく多くの変更および変形をすることが可能である。本記載に列挙されていることに加え、本開示の範囲内の機能的に等価な方法および装置は前述の記載から明白であろう。そのような変更および変形は、添付された請求項の範囲内に入るように意図されている。
【００５６】
図面における、任意のすなわち全てのラダー図、シナリオ、およびフローチャートに関しておよび本記載で述べられたように、各ブロックおよび／または通信は、例示の実施形態に従って情報を処理しおよび／または情報を送信することを表してもよい。他の実施形態もそのような例示の実施形態の範囲に含まれてもよい。さらに、より多くのまたはより少ないブロックおよび／または機能が、本記載に記述されているどのラダー図、シナリオ、およびフローチャートと共に使用されてもよいし、また当該ラダー図、シナリオ、およびフローチャートは、部分的にまたは全体的にお互いに結合されてもよい。
【００５７】
情報の処理を表すステップまたはブロックは、本記載の方法または技術の具体的な論理機能を実行するように構成することが可能な回路に相当してもよい。それに代えてまたはさらに、情報の処理を表すステップまたはブロックは、モジュール、セグメント、またはプログラムコードの一部分（関連するデータを含めて）に相当してもよい。プログラムコードは、方法または技術における具体的な論理機能または動作を実行するための、プロセッサにより実行可能な１以上の命令を含んでもよい。プログラムコードおよび／または関連するデータは、ディスクドライブ、ハードドライブ、またはその他の記憶媒体を含む記憶装置等の任意の種類のコンピュータ読み取り可能な媒体に格納してもよい。
【００５８】
コンピュータ読み取り可能な媒体は、また、レジスタメモリ、プロセッサキャッシュ、および／またはランダムアクセスメモリ（ＲＡＭ）のような短期間データを格納するコンピュータ読み取り可能な媒体等の、非一時的でコンピュータ読み取り可能な媒体を含んでもよい。コンピュータ読み取り可能な媒体は、また、例えば、リードオンリーメモリー（ＲＯＭ）、光学または磁気ディスク、および／またはコンパクトディスク・リードオンリーメモリー（ＣＤ―ＲＯＭ）のような、二次的または持続的長期記憶装置等、より長期間プログラムコードおよび／またはデータを格納する非一時的でコンピュータ読み取り可能な媒体を含んでもよい。コンピュータ読み取り可能な媒体は、また、他の揮発性または不揮発性記憶システムでもよい。コンピュータ読み取り可能な媒体は、例えば、コンピュータ読み取り可能な記憶媒体および／または有形の記憶デバイスと考えてもよい。
【００５９】
本記載においてさまざまな態様および実施形態が開示されてきたが、他の態様および実施形態も当業者にとって明白であろう。本記載において開示されたさまざまな態様および実施形態は、例示目的であって限定することを意図するものではなく、真の範囲と主旨は以下の請求項により示されている。
付録
【００６０】
2016178639.tif 000003
2016178639.tif 000004
2016178639.tif 000005
2016178639.tif 000006
符号の説明
【００６１】
２２  原稿送り装置／出力トレイ
２４  用紙保管部
２６  ユーザインターフェース
２８  スキャン要素
３０  筐体
【図１】
2016178639.tif 000007
【図２】
2016178639.tif 000008
【図３】
2016178639.tif 000009
【図４】
2016178639.tif 000010
【図５】
2016178639.tif 000011
【図６】
2016178639.tif 000012
【図７】
2016178639.tif 000013
【図８】
2016178639.tif 000014
【図９】
2016178639.tif 000015
【外国語明細書】
Apparatus and Method for Data Decoding
Field
[0001]                 The present invention relates to a data decoding technique.
Background
[0002]               In recent years, various types of printing devices have become popular for both business and consumer use.  In addition to traditional black and white printers, color printers, scanners, copiers, fax machines, and other components are now common.  Multi-function peripherals (MFPs), that support two or more of these functions, are also widely available.  Among other functions, these devices are used to process image data.    
[0003]               The processing of image data may include, for instance, compressing and encoding operations, and/or decompressing and decoding operations.  One example image processing technology is defined by the Joint Photographic Experts Group (JPEG) standard.  Generally, a JPEG encoding process of image data includes spatial frequency conversion, quantization, data sequencing, and entropy encoding; and a JPEG decoding process of image data includes an inverse of the JPEG encoding processes, such as entropy decoding, inverse data sequencing, de-quantization, and inverse spatial frequency conversion.   
[0004]               It is desirable to improve on the arrangements of conventional methods and systems or at least to provide one or more useful alternatives to help to make data processing more efficient, reliable, and faster.
Summary
[0005]               In an example embodiment, a computer-implemented method comprises receiving, by a computing device, a data stream that includes a series of code words that encodes a respective series of pixel data according to a first entropy coding lookup table; and processing, by the computing device, the data stream to determine if there is a match between a first code word and a second code word, and a code word entry in a second entropy coding lookup table.  In this example, the first code word and the second code word are consecutive code words in the data stream, and the second entropy coding lookup table is different than the first entropy coding lookup table.  This example method also includes, if there is a match between the first code word and the second code word, and a code word entry in the second entropy coding lookup table, decoding, by the computing device, the first code word and the second code word using the second entropy coding lookup table.  Further, this example method includes, if there is not a match between the first code word and the second code word and a code word entry in the second entropy coding lookup table, decoding, by the computing device, the first code word using the first entropy coding lookup table.
[0006]               In another example embodiment, a system for decoding a data stream comprises an input buffer for receiving the data stream that includes data encoded into a series of code words according to an entropy coding lookup table, and a processor coupled to the input buffer.  In this example, the processor is configured to determine if consecutive code words in the data stream correspond to a run of zero followed by a run of zero or a run of one and to, if the consecutive code words correspond to a run of zero followed by a run of zero or a run of one, provide an output based at least in part on decoding the consecutive code words using a modified entropy coding lookup table.  Further, in this example, the processor is configured to, if the consecutive code words do not correspond to a run of zero followed by a run of zero or a run of one, provide the output based at least in part on decoding a first code word of the consecutive code words using the entropy coding lookup table. 
[0007]               In a further example embodiment, a non-transitory computer-readable medium has stored thereon program instructions that, upon execution by a processor cause performance of a set of acts comprising receiving, by a computing device, a data stream that includes a series of code words that encodes a respective series of pixel data according to a first entropy coding lookup table; and processing the data stream to determine if there is a match between a first code word and a second code word, and a code word entry in a second entropy coding lookup table.  In this example, the first code word and the second code word are consecutive code words in the data stream, and the second entropy coding lookup table is different than the first entropy coding lookup table.  In this example, the set of acts also includes, if there is a match between the first code word and the second code word, and a code word entry in the second entropy coding lookup table, decoding the first code word and the second code word using the second entropy coding lookup table.  Further, in this example, the set of acts includes, if there is not a match between the first code word and the second code word and a code word entry in the second entropy coding lookup table, decoding the first code word using the first entropy coding lookup table.  
[0008]               These as well as other aspects, advantages, and alternatives will become apparent to those of ordinary skill in the art by reading the following detailed description with reference where appropriate to the accompanying drawings.  Further, it should be understood that the description provided in this summary section and elsewhere in this document is intended to illustrate the claimed subject matter by way of example and not by way of limitation.
Brief Description of the Drawings
[0009]               Figure 1 depicts a diagrammatic block and processing diagram of a conventional cascaded Huffman decoder. 
Figure 2 depicts a computing device, according to an example embodiment.
Figure 3 is a block diagram illustrating data processing components of a computing device, according to an example embodiment. 
Figure 4 is a block diagram illustrating storage components and data for use in image processing, according to an example embodiment.  
Figure 5 is an example of a predetermined data sequence for an 8x8 data block. 
Figure 6 is a block diagram illustrating data processing components of a computing device, according to an example embodiment.
Figure 7 is a block diagram illustrating storage components and data for use in image processing, according to an example embodiment.  
Figure 8 depicts a block diagram of a data decoder system in accordance with an example embodiment. 
Figure 9 depicts a method of decoding data in accordance with an example embodiment.
Detailed Description of the Drawings
[0010]               Example methods and systems are described herein.  Other example embodiments or features may further be utilized, and other changes may be made, without departing from the spirit or scope of the subject matter presented herein.  In the following detailed description, reference is made to the accompanying figures, which form a part thereof.   
[0011]               The example embodiments described herein are not meant to be limiting.  It will be readily understood that the aspects of the present disclosure, as generally described herein, and illustrated in the figures, can be arranged, substituted, combined, separated, and designed in a wide variety of different configurations, all of which are explicitly contemplated herein.  For illustration purposes, features and functions are described with respect to printing devices and processing of image data.  However, the features and functions disclosed herein may also be applicable to other types of computing devices (e.g., display devices), components of computing devices (e.g., data decoders, processors, storage components, and the like), and to processing other types of data (e.g., audio data and/or video data).  
1.               Introduction
[0012]               Printing technology has evolved over the last 30-plus years from simple dot-matrix-based output devices producing only black and white images to today’s advanced laser-based printing devices that can produce high-resolution color images.  Additionally, modern printing devices may also function as copiers, scanners, and fax machines.  To do so, they may be able to store image data for numerous electronic documents that are queued for printing or faxing, or that have been scanned.  Thus, many printing devices are specialized forms of computing devices that may include, for example, one or more processors, data storage, and input/output interfaces.
[0013]               Regardless of whether a printing device is used in a residence, a business, or in another type of location, the printing device may be a shared resource that can be communicatively coupled to various other computing devices.  Consequently, in some environments, the storage and processing requirements of a printing device may be quite high, as numerous computing devices may be transmitting electronic documents to the printing device for printing.  Typically, a printing device will print, copy, fax, and/or scan one electronic document at a time, in a first-come-first-served fashion.  Therefore, the printing device may store a potentially large number of electronic documents that are waiting to be serviced.  Since the cost of data storage (e.g., memory such as random access memory (RAM), solid-state memory, hard-drive memory, and/or flash memory) can be expensive, it may be beneficial to compress the stored electronic documents, in order to reduce the data storage requirements of the printing device.  Additionally, since some electronic documents may be transferred to and/or from the printing device and a computing device, compressing these electronic documents may make transfers faster and use less network capacity.  
[0014]               Moreover, since print jobs may be large (e.g., a print job may include one or more electronic documents encompassing hundreds of pages), compressing queued print jobs in the queue saves short-term storage space before each job is printed.  In addition, users may want to save print jobs in long-term storage for printing at a later time.  Thus, compressing print jobs may allow more print jobs to be saved.  Furthermore, the act of storing and retrieving large print jobs from long-term memory can be slow, but it may be expedited by compressing the print jobs to make them smaller in size.
[0015]               One technique for compressing and subsequently decompressing print jobs (and other types of data) utilizes entropy coding.  Huffman coding is one example of entropy coding that is commonly used to compress image data, video data, audio data, and the like.  Generally, Huffman coding encodes symbols (e.g., pixel data, DCT coefficients, audio data, and the like) with variable-length binary code or code words that are assigned in accordance with statistical probabilities.  For instance, more frequently used symbols are assigned codes that may be only a couple of bits in length, and less frequently used symbols are assigned codes that are increasing numbers of bits in length (e.g., up to 16 bits in length).  Huffman coding uses a lookup table that lists each possible variable length code to encode and decode data.  One example Huffman table is provided in the JPEG standard (ISO/IEC 10918) at Table K.5, and which is also attached hereto in the appendix (the “JPEG Huffman lookup table”).  Other example Huffman tables are also possible and within the scope of the present disclosure. 
[0016]               Because Huffman coding uses variable-length codes, decoding a stream of Huffman-encoded data is sequential in nature, such that each code in the stream of data is determined before a next code is determined.  Conventional decoders operate at one code per clock rate or cycle.  Commonly, each Huffman code contains multiple pixels so that an average decompression rate of pixels per clock rate is suitably high.  However, some applications require a guaranteed pixel throughput (e.g., two pixels per clock), and the transient worst-case, low-pixel rate of one pixel per clock can cause data under-run and image artifacts.  In practice, the potential for less than two pixel/clock throughput is more likely in very noisy areas of an image, for example.  
[0017]               Conventional attempts to guarantee a two pixel/clock throughput have various shortcomings.  In one approach, two cascaded Huffman decoders can decode at least two pixels/clock, but this throughput comes at the cost of doubling the critical path delay of the processing logic.  Referring to Figure 1, for example, cascading a first Huffman decoder with a second Huffman decoder essentially doubles the critical path delay due to processing a data stream using two full Huffman lookup tables, which essentially cuts in half the maximum processing frequency.  In the case of the 160 entry Huffman lookup table that is commonly used in JPEG processing, the relatively large Huffman lookup table limits the maximum clock frequency at which the cascaded decoders can run.  
[0018]               In another approach, parallel Huffman decoders are used to decode at least two pixels/clock.  However, this approach uses additional data buffers and dynamic memory allocation to generate separate data streams for the parallel Huffman decoders.  Depending on the computing device that is being used to decode the data stream, such additional data buffers may not be available.  In addition, the use of additional data buffers and dynamic memory allocation in this context can increase memory fragmentation and increase processing latency.  
[0019]               The present disclosure provides reliable and efficient approach to guarantee an average two pixel/clock decoding throughput (e.g., a four-pixel per two-clock cycle throughput). The disclosed approach utilizes a modified Huffman lookup table to decode an encoded data stream.  Referring to the relatively large JPEG Huffman lookup table, only ten of the entries correspond to a run of zero.  Generally, the run length corresponds to the length of run of zero amplitude AC coefficients.  In this context, a run of zero means that there is no zero amplitude AC coefficient in between the last (decoded) AC coefficient and the next non-zero AC coefficient, a run of one means that there is one zero amplitude AC coefficient followed by one non-zero amplitude AC coefficient, a run of two means that there are two zero amplitude AC coefficients followed by one non-zero amplitude AC coefficient, and a run of an integer (n) means that there are n zero amplitude AC coefficients followed by one non-zero amplitude AC coefficient.  
[0020]               The run of zero code words in the JPEG Huffman lookup table (and other variable or fixed length encoding tables) are the only cases where there would be a need to decode faster than one code word per clock to guarantee a two pixel/clock throughput.  This is because throughput for runs of one amount to a two pixel/clock decoding rate (the zero amplitude AC coefficient pixel and the one non-zero amplitude AC coefficient pixel), runs of two amount to a three pixel/clock decoding rate, runs of three amount to a four pixel/clock decoding rate, and runs of n amount to an (n+1) pixel/clock decoding rate.  
[0021]               The present disclosure uses a modified coding lookup table that cascades the entries of the full lookup table corresponding to a run of zero with entries of the full lookup table corresponding to a run of zero or a run of one.  The resulting modified coding lookup table enables the decoder to decode two code words in one clock cycle, without cascading the entire full lookup table, as in conventional techniques.  In short, when the current code word corresponds to one pixel, and the next code word corresponds to one or two pixels, these consecutive code words are decoded together using the modified coding lookup table.  Otherwise, one code word (runs of two or more correspond to three or more pixels) can be decoded per clock cycle without reducing the throughput rate below two pixels/clock.  
[0022]               Compared with the cascaded decoder, discussed above, this approach of using a modified coding lookup table in addition to and in parallel with the full lookup table requires about the same amount of circuitry and logic (e.g., by having 200 or more entries in the lookup table).  However, since the code word pair decoding happens in parallel with the normal decoding process, in contrast to the serial decoding as in cascaded decoder, the disclosed approach is inherently faster.
2.               Example Printing Device  
[0023]               Figure 2 depicts an example printing device 20.  Printing device 20 may be configured to print partially-stored and/or fully-stored electronic documents on various types of physical output media.  These output media include, but are not limited to, various sizes and types of paper, overhead transparencies, and so on.  Printing device 20 may be interchangeably referred to as a “printer.”
[0024]               Printing device 20 may serve as local peripheral to another computing device, such as a personal computer, a display monitor, a server device, a print server, and the like.  In these cases, printing device 20 may be attached to the computing device by cable, such as a serial port cable, parallel port cable, Universal Serial Bus (USB) cable, Firewire (IEEE 1394) cable, or High-Definition Multimedia Interface (HDMI) cable.  Thus, the computing device may serve as a source of electronic documents for printing device 20. 
[0025]               On the other hand, printing device 20 may include a wireline or wireless network interface, such as an Ethernet or IEEE 802.11 (WLAN or Wi-Fi) interface.  So arranged, printing device 20 may serve as a printing device for any number of computing devices that can communicate with printing device 20 over a network.  In some embodiments, printing device 20 may serve as both a local peripheral and a networked printer at the same time.  In order to use printing device 20, computing devices may install one or more printer drivers.  These printer drivers may include software components that convert the image data representing electronic documents to be printed from various local representations stored on the computing devices to one or more representations supported by printing device 20.  Regardless, printing device 20 may be considered to be a computing device, and may carry out both printing-related and non-printing related tasks.
[0026]               As noted above, printing device 20 may also include copier, fax, and scanner functions.  In some embodiments, printing device 20 may use a scanner function to facilitate copier and/or fax functions.  For instance, printing device 20 may scan a physical document into an electronic format, and then print the resulting electronic document to provide a copy, and/or transmit the resulting electronic document via a telephone interface to provide a fax function.
[0027]               In order to support its various functions, printing device 20 may include a document feeder / output tray 22, paper storage 24, user interface 26, scanning element 28, and chassis 30.  It should be understood that printing devices may take on a wide variety of forms.  Therefore printing device 20 may include more or fewer components than depicted in Figure 1, and/or components arranged in a different fashion than depicted in Figure 1.
[0028]               Document feeder / output tray 22 may hold physical documents (e.g., a stack of one or more sheets of paper) that are to be scanned, copied or faxed.  Document feeder / output tray 22 may allow printing device 20 to automatically feed multiple physical documents for processing by printing device 20 without requiring manual intervention.  Document feeder / output tray 22 may also include one or more separate output trays for holding physical documents that have been processed by printing device 20.  These may include physical documents that have been scanned, copied, or faxed by printing device 20, as well as physical documents that have been produced by the fax and/or copying functions, for example, of printing device 20.
[0029]               Paper storage 24 may include trays and/or feeding elements for various types of physical media.  For instance, paper storage 24 may include separate trays for 8 1/2 x 11 inch paper, A4 paper, letterhead paper, envelopes, and so on.  For any function of printing device 20 that involves producing physical media (e.g., printing, copying, and/or receiving a fax), paper storage 24 may supply the physical media.
[0030]               User interface 26 may facilitate the interaction of printing device 20 with a human or non-human user, such as to receive input from a user and to provide output to the user.  Thus, user interface 26 may include input components such as a keypad, keyboard, touch-sensitive or presence-sensitive panel, joystick, microphone, still camera and/or video camera.  User interface 26 may also include one or more output components such as a display screen (which, for example, may be combined with a presence-sensitive panel), a cathode ray tube (CRT), a liquid crystal display (LCD), a light emitting diode (LED) based display, a display using digital light processing (DLP (Trade mark)) technology, a light bulb, and/or one or more other similar devices, now known or later developed.  User interface 26 may also be configured to be able to generate audible output(s), via a speaker, speaker jack, audio output port, audio output device, earphones, and/or other similar devices, now known or later developed in the future.
[0031]               Scanning element 28 may be a glass panel below which a movable light source operates to scan physical media placed on top of the glass panel.  Alternatively, a digital camera below the glass panel may “scan” the physical media placed on top of the glass panel by taking a picture of the physical media.  Images of scanned physical media may be stored in data storage associated with printing device 20.  
[0032]               Chassis 30 may include a physical housing that contains and or interconnects various components of printing device 20, such as document feeder / output tray 22, paper storage 24, user interface 26, and scanning element 28.  Additionally, chassis 30 may house other components not shown in Figure 1.  For example, chassis 30 may contain one or more toner cartridges, liquid ink jets, belts, rollers, and/or power supplies.  Further, chassis 30 may include communication interfaces, such as a wireline and/or wireless network interfaces, a telephony interface (e.g., a RJ45 jack), a USB interface, a BLUETOOTH (Trade mark) interface, a card reader port, etc.
[0033]               Moreover, as printing device 20 may be based on general-purpose and/or specially-designed computing device components, chassis 30 may also house some or all of these components.  For instance, the printing device 20 may include a processor and data storage (not explicitly shown).  Generally, the processor may include one or more central processing units (CPUs), such as one or more general purpose processors and/or one or more dedicated processors (e.g., application specific integrated circuits (ASICs) or digital signal processors (DSPs), etc.).  The data storage may include volatile and/or non-volatile data storage and can be integrated in whole or in part with processor.  The data storage may store program instructions, executable by processor, and data that are manipulated by these instructions to carry out the various methods, processes, or functions described herein.  Alternatively, these methods, processes, or functions can be defined by hardware, firmware, and/or any combination of hardware, firmware and software.  Therefore, the data storage may include a tangible, non-transitory computer-readable medium, having stored thereon program instructions that, upon execution by one or more processors, cause printing device 20 to carry out any of the methods, processes, or functions disclosed in this specification or the accompanying drawings.  
[0034]               Further, the components of the printing device 20 may also include hardware and/or software components for compressing/encoding and/or decompressing/decoding image data.  
3.           Example Encoder and Decoder 
[0035]               Figures 3 and 6 depict example embodiments of computing device components (e.g., functional elements of a computing device) that may be included in printing device 20.  Referring first to Figure 3, an example image data encoder 40 is illustrated.  The encoder 40 is configured to receive image data 42.  In the illustrated example, the image data 42 is divided into image data blocks (e.g., 8x8 pixel blocks), and the image data blocks are provided to a spatial frequency converter 44 of the encoder 40.  The spatial frequency converter 44 performs spatial frequency conversion, such as by executing a discrete cosine transform (DCT) on the image data.  Performing the spatial frequency conversion on the image data results in a set of one or more frequency coefficients that represent the spatial frequency conversion of the image data block.  In the example of an 8x8 pixel block, the spatial frequency converter 44 is configured to produce between one and sixty-four frequency coefficients in a single clock cycle.  Referring to Figure 4, in one example, these resulting frequency coefficients Suv may be stored in a storage component 60.  In another example, a resulting set of one to sixty-four frequency coefficients Suv need not be stored separately, but are operated upon in a single operation (e.g., a single clock cycle) by a quantizer and data sequencer. 
[0036]                 For instance, the set of one to sixty-four frequency coefficients Suv may then be immediately operated upon by a quantizer 46.  The quantizer 46 generates quantized data, such as a set of one or more quantized frequency coefficients.  Generally, quantization is a process for reducing or eliminating high frequency components after the image data has been transformed into the frequency domain by the spatial frequency conversion operation.  The quantizer 46 operates on the frequency coefficients using a quantization table that includes quantization factors.  More particularly, in the encoder 40, the quantizer 46 divides the frequency coefficients Suv by corresponding quantization factors to generate the set of quantized frequency coefficients.  Figure 4 illustrates an example where the quantization factors Quv may be stored in a storage component 62 or otherwise made available as inputs to the quantizer where one or up to sixty-four quantization factors Quv are available per clock cycle.  The quantizer 46 may also round the result of the division operation to eliminate insignificant high frequency components.  
[0037]               In the present example, the set of quantized frequency coefficients Squv produced by the quantizer 46 may then be provided immediately, in a single operation or single clock cycle, to a data sequencer 48.  The data sequencer 48 is configured to arrange the set of quantized frequency coefficients Squv in a predetermined sequence.  One such sequence is a zig-zag sequence that is illustrated by Figure 5.  Figure 4 also illustrates a block 64 that represents hardware and/or software components that execute the zig-zag sequencing operation.  
[0038]               The resulting set of quantized frequency coefficients Squv arranged in the predetermined sequence may be stored in a storage component 66.  In another example, the resulting set of one to sixty-four quantized frequency coefficients Squv need not be stored separately, but are operated upon in a single operation (e.g., a single clock cycle) by a data encoder 50.  The data encoder 50 performs entropy or Huffman coding on the extracted, quantized frequency coefficients Squv to provide encoded data 52 for storage, transfer, or other processing.  
[0039]               Referring now to Figures 6 and 7, an example image data decoder 70 is illustrated.  The decoder 70 is configured to receive encoded image data 52 (such as the encoded data of Figure 3).  In the illustrated example, the encoded data is provided immediately to a data decoder 72.  The data decoder 72 performs the inverse function of the data encoder 50, e.g., an inverse entropy or Huffman decoding to produce quantized frequency coefficients Squv.  In the example of an 8x8 pixel block, the data decoder 72 is configured to produce between one and sixty-four quantized frequency coefficients Squv in a single clock cycle.  The number of coefficients Squv may depend, in part, on the received encoded image data.  In Figure 7, in one example, the resulting quantized frequency coefficients Squv may be stored in a storage component 90.   In another example, a resulting set of one to sixty-four quantized frequency coefficients Squv need not be stored separately, but are operated upon in a single operation (e.g., a single clock cycle) by a data inverse sequencer and a de-quantizer, as will be described in more detail hereinafter.   
[0040]               In the present example, the set of one to sixty-four quantized frequency coefficients Squv may be arranged in the predetermined sequence resulting from the operation of the data sequencer 48 of Figure 3.  Accordingly, the quantized frequency coefficients Squv may be provided to a data inverse sequencer 74, which arranges the quantized frequency coefficients Squv in an inverse of the predetermined sequence.  Referring to Figure 7, in one example, the resulting re-arranged quantized frequency coefficients Squv may be stored in a storage component 92. 
[0041]                 In another example, the resulting re-arranged quantized frequency coefficients Squv need not be stored separately, and after the data inverse sequencer 74, the quantized frequency coefficients Squv are provided immediately to a de-quantizer 76, which de-quantizes the quantized frequency coefficients Squv.  In one example, the de-quantizer 76 uses the same quantization table and quantization factor as discussed above in relation to the quantizer 46 of Figure 3.  However, the de-quantizer 76 multiplies the quantized frequency coefficients Squv with corresponding quantization factors Quv and performs an inverse of the rounding performed by the quantizer 46 to extract the frequency coefficients Suv, which may be stored in a storage component 94 or provided immediately to an inverse spatial frequency converter 78.  The inverse spatial frequency converter 78 performs an inverse of the spatial frequency conversion performed by the converter 44 of Figure 3 in order to extract the original image data 42 for display, printing, or other processing.  
4.           Example Decoder System
[0042]               Referring now to Figure 8, an example decoder system 100 is illustrated.  In Figure 8, the system 100 includes a buffer component 102 that is configured to receive an incoming data stream 104 that includes a series of variable length code words that encode a respective series of pixel data (e.g., DCT coefficients) according to an entropy coding lookup table.  In one example, the first entropy coding lookup table is the JPEG Huffman lookup table including all 160 entries.  From the buffer component 102, the data stream 104 (or sequential portions thereof) is provided for processing by a block 106 (e.g., a processor or processing logic) that uses a first coding lookup table (e.g., the same “full” entropy coding lookup table used to encode the pixel data), and for processing by a block 108 (e.g., the same or different processor or processing logic from block 106) that uses a second coding lookup table.  
[0043]               In this example, the second coding lookup table is a modified version of the first entropy coding lookup table and includes a plurality of entries that each comprises a pair of a first code word and a second code word.  For instance, the first code word of each pair is selected from one or more entries of the first lookup table that correspond to a run of zero, and the second code word of each pair is selected from one or more entries of the first lookup table that correspond to a run of zero or a run of one.  Referring to the JPEG Huffman lookup table, there are ten code words that correspond to a run of zero and ten code words that correspond to a run of one.  In this example, the second coding lookup table includes each combination of run of zero code words followed by run of zero code words or run of one code words.  Based on the JPEG Huffman lookup table, such a modified, second coding lookup table would include 200 entries generally as follows: 
(Run of zero code words followed by run of zero code words)
0/1_0/1, 0/1_0/2, … , 0/1_0/A,
0/2_0/1, 0/2_0/2, … , 0/2_0/A,
0/3_0/1, 0/3_0/2, … , 0/3_0/A,
…
0/A_0/1, 0/A_0/2, … , 0/A_0/A,
(Run of zero code words followed by run of one code words)
0/1_1/1, 0/1_1/2, … , 0/1_1/A,
0/2_1/1, 0/2_1/2, … , 0/2_1/A,
0/3_1/1, 0/3_1/2, … , 0/3_1/A,
…
0/A_1/1, 0/A_1/2, … , 0/A_1/A,
[0044]               The first and second coding lookup tables blocks 106, 108 process the data stream 104 in parallel to identify matches between code words in the received data stream and entries of the respective lookup tables.  The block 106 processes the data stream 104 one code word at a time to find a matching code word entry in the first coding lookup table and provides, as an output 110, the matching code word to a selector component 112.  The selector component 112 may be a priority based multiplexer or other hardware and/or software components configured to selectively provide an output from a plurality of inputs. 
[0045]               The block 108 processes the data stream 104 using the second coding lookup table to determine whether the data stream 104 includes consecutive code words that correspond to a run of zero followed by a run of zero or a run of one.  If the block 108 determines that there is a match between consecutive code words in the data stream, and a code word entry in the second coding lookup table, the block 108 provides, as an output 114, the matching pair of code words to the selector component 112.  If the block 108 determines that there is a match, the block 108 provides a priority signal that instructs the selector component 112 to selectively provide an output 116 based on the output 114.  If the block 108 determines that there is not match, the block 108 does not provide the priority signal (or otherwise provides a different signal), which then instructs the selector component 112 to selectively provide the output 116 based on the output 110.  
[0046]               In the example of Figure 8, a packing logic block 118 receives the output 116 from the selector component 112, and is configured to pack the variable length code word output 110 from block 106 or the variable length code word pair output 114 from block 108 in a pixel queue 120, which may be a fixed-length queue.  The system 100 of Figure 8 also includes one or more decoding stages 122 that are configured to perform functions, such as inverse data sequencing, dequantizing, inverse spatial frequency conversion, and the like.  Further, in the example of Figure 8, an output device 124 is coupled to the decoding stage(s) 122.  In the present example, the output device 124 may be a print engine configured to translate the contents of the pixel queue 120, as processed by the decoding stage(s) 122, into control signals for printing a corresponding portion of an image.  The output device 124 may also include some other display device, such as a display monitor, that is configured to translate the contents of the pixel queue 120 into control signals for displaying a corresponding portion of an image.  
[0047]               In the system 100, the blocks 106, 108 may also be configured to provide a feedback output 126 coupled to the buffer component 102, which also can function as a hardware and/or software based picker block.  More particularly, when the blocks 106, 108 identify a variable length code word in the data stream 104, the blocks 106, 108 may generate the feedback output 126 to inform the picker block (buffer component 102) of the length of the code word.  The picker block (buffer component 102) may then shift a moving window of bits to provide a next sequential portion of the data stream to the blocks 106, 108 for processing.  
5.           Example Operation 
[0048]               In addition to the above description, Figure 9 illustrates a flow chart of an example embodiment. The steps illustrated by this flow chart may be carried out by one or more computing devices, systems, or components thereof, such as printing device 20, decoder 72, and system 100.  Further, aspects of each individual step may be distributed between multiple computing devices, as appropriate. 
[0049]               Figure 9 illustrates an example encoding process 150 that can use the components of Figures 6 and 8, for example.  In the process 150 at block 152, the system 100, for example, receives a data stream that includes code words that encode a respective series of pixel data according to a first entropy encoding lookup table.  For instance, the first entropy encoding lookup table can be the JPEG Huffman lookup table described herein.  
[0050]               At block 154, the system 100 processes the data stream to determine if there is a match between a first code word and a second code word, and a code word entry in a second entropy coding lookup table.  In the present example, the first code word and the second code word are consecutive code words in the data stream, and the second entropy coding lookup table can be the modified coding lookup table used by the second coding lookup table block 108 of Figure 8.  At block 156, the system 100 processes the data stream to identify a match between the first code word and a code word entry in the first entropy coding lookup table.  In one example, this processing at block 156 is performed in parallel with the processing of block 154.  
[0051]               At block 158, if there is a match between the first code word and the second code word, and a code word entry in the second entropy coding lookup table, the system 100 decodes or otherwise provides as an output the first code word and the second code word using the second entropy coding lookup table.  At block 160, if there is not a match between the first code word and the second code word and a code word entry in the second entropy coding lookup table, the system 100 decodes or otherwise provides as an output the first code word using the first entropy coding lookup table. 
[0052]               In the example of Figure 9, at block 162, the system 100 shifts processing to a next set of code words.  In accordance with one embodiment, if the system 100 does not identify a match at block 154, then at block 162, the system 100 shifts processing by one code word, and control passes back to block 154 to continue processing the received data stream.  Consequently, at a next iteration of block 154 the system 100 determines if there is a match between the second code word and a next consecutive (third) code word, and a code word entry in the second entropy coding lookup table.  Further, at a next iteration of block 156 the system 100 processes the data stream to identify a match between the second code word and a code word entry in the first entropy coding lookup table.  Thereafter, at block 158, if there is a match between the second code word and the third code word, and a code word entry in the second entropy coding lookup table, the system 100 decodes or otherwise provides as an output the second code word and the third code word using the second entropy coding lookup table.  At block 160, if there is not a match between the second code word and the third code word and a code word entry in the second entropy coding lookup table, the system 100 decodes or otherwise provides as an output the second code word using the first entropy coding lookup table. 
[0053]               Referring again to block 162, in accordance with the present embodiment, if the system 100 does identify a match at block 154, then at block 162, the system 100 shifts processing by two code words, and control passes back to block 154 to continue processing the received data stream.  Consequently, at a next iteration of block 154 the system 100 determines if there is a match between a next consecutive pair of code words (e.g., third and fourth code words), and a code word entry in the second entropy coding lookup table.  Further, at a next iteration of block 156 the system 100 processes the data stream to identify a match between the third code word and a code word entry in the first entropy coding lookup table.  Thereafter, at block 158, if there is a match between the third code word and the fourth code word, and a code word entry in the second entropy coding lookup table, the system 100 decodes or otherwise provides as an output the third code word and the fourth code word using the second entropy coding lookup table.  At block 160, if there is not a match between the third code word and the fourth code word and a code word entry in the second entropy coding lookup table, the system 100 decodes or otherwise provides as an output the third code word using the first entropy coding lookup table.
[0054]               Generally, the processing at block 162 provides a moving window that traverses sequentially through the data stream as code words are decoded and provided to an output. 
6.           Conclusion 
[0055]               The present disclosure is not to be limited in terms of the particular embodiments described in this application, which are intended as illustrations of various aspects.  Many modifications and variations can be made without departing from its spirit and scope, as will be apparent to those skilled in the art.  Functionally equivalent methods and apparatuses within the scope of the disclosure, in addition to those enumerated herein, will be apparent from the foregoing descriptions.  Such modifications and variations are intended to fall within the scope of the appended claims.  
[0056]               With respect to any or all of the ladder diagrams, scenarios, and flow charts in the figures and as discussed herein, each block and/or communication may represent a processing of information and/or a transmission of information in accordance with example embodiments.  Alternative embodiments may be included within the scope of such example embodiments.  Further, more or fewer blocks and/or functions may be used with any of the ladder diagrams, scenarios, and flow charts discussed herein, and these ladder diagrams, scenarios, and flow charts may be combined with one another, in part or in whole.    
[0057]               A step or block that represents a processing of information may correspond to circuitry that can be configured to perform the specific logical functions of a herein-described method or technique.  Alternatively or additionally, a step or block that represents a processing of information may correspond to a module, a segment, or a portion of program code (including related data).  The program code may include one or more instructions executable by a processor for implementing specific logical functions or actions in the method or technique.  The program code and/or related data may be stored on any type of computer-readable medium, such as a storage device, including a disk drive, a hard drive, or other storage media.
[0058]               The computer-readable medium may also include non-transitory computer-readable media such as computer-readable media that stores data for short periods of time like register memory, processor cache, and/or random access memory (RAM).  The computer-readable media may also include non-transitory computer-readable media that stores program code and/or data for longer periods of time, such as secondary or persistent long term storage, like read only memory (ROM), optical or magnetic disks, and/or compact-disc read only memory (CD-ROM), for example.  The computer-readable media may also be any other volatile or non-volatile storage systems.  A computer-readable medium may be considered a computer-readable storage medium, for example, and/or a tangible storage device.
[0059]               While various aspects and embodiments have been disclosed herein, other aspects and embodiments will be apparent to those skilled in the art.  The various aspects and embodiments disclosed herein are for purposes of illustration and are not intended to be limiting, with the true scope and spirit being indicated by the following claims.
APPENDIX
[0060]                
2016178639.tif 000016
2016178639.tif 000017
2016178639.tif 000018
2016178639.tif 000019
REFFERENCE SIGNS LIST
[0061]                  
22    document feeder / output tray
24    paper storage
26    user interface
28    scanning element
30    chassis
CLAIMS
We claim:
1.  A computer comprising:
at least one processor;
memory; and
program instructions, stored in the memory, that upon execution by the at least one processor cause the computer to perform operations including:
receiving a data stream that includes a series of code words that encode a respective series of pixel data according to a first entropy coding lookup table;
processing the data stream to determine if there is a match between a first code word and a second code word, and a code word entry in a second entropy coding lookup table, wherein the first code word and the second code word are consecutive code words in the data stream, and wherein the second entropy coding lookup table is different than the first entropy coding lookup table; 
if there is a match between the first code word and the second code word, and a code word entry in the second entropy coding lookup table, decoding the first code word and the second code word using the second entropy coding lookup table; and
if there is not a match between the first code word and the second code word and a code word entry in the second entropy coding lookup table, decoding the first code word using the first entropy coding lookup table.  
2.  The computer of claim 1, wherein
the program instructions cause the computer to perform operations including processing the data stream to identify a match between the first code word and a code word entry in the first entropy coding lookup table, wherein the computing device performs processing of the data stream to identify a match between the first code word and a code word entry in the first entropy coding lookup table in parallel with processing of the data stream to determine if there is a match between the first code word and the second code word, and a code word entry in the second entropy coding lookup table.
3.  The computer of claim 1 or 2, wherein
the second entropy coding lookup table includes at least a plurality of entries that each comprises a pair of a first code word and a second code word, wherein the first code word of each pair is selected from one or more entries of the first entropy coding lookup table that correspond to a run of zero, and the second code word of each pair is selected from one or more entries of the first entropy coding lookup table that correspond to a run of zero or a run of one. 
4.  The computer of claim 3, wherein
the second entropy coding lookup table includes each unique combination of pairs of the first code word and the second code word. 
5.  The computer of any of claims 1 to 4, wherein
the program instructions cause the computer to perform operations including if there is a match between the first code word and the second code word, and a code word entry in the second entropy coding lookup table, processing the data stream to determine if there is a match between a third code word and a fourth code word, and a code word entry in the second entropy coding lookup table, wherein the first, second, third, and fourth code words are consecutive code words in the data stream.  
6.  The computer of claim 5, wherein
the program instructions cause the computer to perform operations including:
if there is (i) a match between the first code word and the second code word, and a code word entry in the second entropy coding lookup table, and (ii) a match between the third code word and the fourth code word, and a code word entry in the second entropy coding lookup table, decoding the third code word and the fourth code word using the second entropy coding lookup table; and
if there is (i) a match between the first code word and the second code word, and a code word entry in the second entropy coding lookup table, and if there is (ii) not a match between the third code word and the fourth code word and a code word entry in the second entropy coding lookup table, decoding the third code word using the first entropy coding lookup table.  
7.  The computer of any of claims 1 to 6, wherein
the program instructions cause the computer to perform operations including if there is not a match between the first code word and the second code word, and a code word entry in the second entropy coding lookup table, processing the data stream to determine if there is a match between the second code word and a third code word, and a code word entry in the second entropy coding lookup table, wherein the second and third code words are consecutive code words in the data stream.
8.  The computer of claim 7, wherein
the program instructions cause the computer to perform operations including:
if there is (i) not a match between the first code word and the second code word, and a code word entry in the second entropy coding lookup table, and if there is (ii) a match between the second code word and the third code word, and a code word entry in the second entropy coding lookup table, decoding the second code word and the third code word using the second entropy coding lookup table; and
if there is (i) not a match between the first code word and the second code word, and a code word entry in the second entropy coding lookup table, and if there is (ii) not a match between the second code word and the third code word, and a code word entry in the second entropy coding lookup table, decoding the second code word using the first entropy coding lookup table.  
9.  The computer of any of claims 1 to 8, wherein decoding the first code word and the second code word using the second entropy coding lookup table guarantees an average two pixel per clock cycle throughput.  
10.  The computer of any of claims 1 to 9, wherein the first entropy coding lookup table is a Huffman entropy coding lookup table. 
11.  The computer of any of claims 1 to 10, wherein
the program instructions cause the computer to perform operations including providing, based on the decoding of the first code word or the first code word and the second code word, an output data stream to one or more of a print engine or a display monitor. 
12.  The computer of claim 11, wherein
the program instructions cause the computer to perform operations including dequantizing the output data stream and performing an inverse spatial frequency conversion on the output data stream before providing the output data stream to one or more of the print engine or the display monitor. 
13.  A system for decoding a data stream comprising:
an input buffer for receiving the data stream, wherein the data stream includes data encoded into a series of code words according to an entropy coding lookup table; and
a processor coupled to the input buffer and configured to:
determine if consecutive code words in the data stream correspond to a run of zero followed by a run of zero or a run of one; 
if the consecutive code words correspond to a run of zero followed by a run of zero or a run of one, provide an output based at least in part on decoding the consecutive code words using a modified entropy coding lookup table; and
if the consecutive code words do not correspond to a run of zero followed by a run of zero or a run of one, provide the output based at least in part on decoding a first code word of the consecutive code words using the entropy coding lookup table. 
14.  The system of claim 13, wherein the modified entropy coding lookup table includes at least a plurality of entries that each comprises a pair of a first code word and a second code word, wherein the first code word of each pair is selected from one or more entries of the entropy coding lookup table that correspond to a run of zero, and the second code word of each pair is selected from one or more entries of the entropy coding lookup table that correspond to a run of zero or a run of one. 
15.  The system of claim 13 or 14, wherein providing the output based at least in part on decoding the consecutive code words using the modified entropy coding lookup table guarantees an average two pixel per clock cycle throughput.  
16.  The system of any of claims 13 to 15, wherein the entropy coding lookup table is a Huffman entropy coding lookup table. 
17.  The system of any of claims 13 to 16, wherein the input buffer and the processor are included in a printing device. 
18.  A program causing a processor to perform a set of acts comprising:
receiving a data stream that includes a series of code words that encodes a respective series of pixel data according to a first entropy coding lookup table;
processing the data stream to determine if there is a match between a first code word and a second code word, and a code word entry in a second entropy coding lookup table, wherein the first code word and the second code word are consecutive code words in the data stream, and wherein the second entropy coding lookup table is different than the first entropy coding lookup table; 
if there is a match between the first code word and the second code word, and a code word entry in the second entropy coding lookup table, decoding the first code word and the second code word using the second entropy coding lookup table; and
if there is not a match between the first code word and the second code word and a code word entry in the second entropy coding lookup table, decoding the first code word using the first entropy coding lookup table.  
19.  The program of claim 18, the set of acts further comprising: 
processing the data stream to identify a match between the first code word and a code word entry in the first entropy coding lookup table, wherein processing of the data stream to identify a match between the first code word and a code word entry in the first entropy coding lookup table is performed in parallel with processing of the data stream to determine if there is a match between the first code word and the second code word, and a code word entry in the second entropy coding lookup table.
20.  The program of claim 18 or 19, wherein the second entropy coding lookup table includes at least a plurality of entries that each comprises a pair of a first code word and a second code word, wherein the first code word of each pair is selected from one or more entries of the first entropy coding lookup table that correspond to a run of zero, and the second code word of each pair is selected from one or more entries of the first entropy coding lookup table that correspond to a run of zero or a run of one.
1. Abstract
PROBLEM TO BE SOLVED
To provide a technique for a digital decoding.
2. SOLUTION
A computer-implemented method comprises receiving a data stream that includes a series of code words that encodes a respective series of pixel data according to a first entropy coding lookup table, and processing the data stream to determine if there is a match between a first code word and a consecutive second code word, and a code word entry in a second entropy coding lookup table.  The method also includes, if there is a match, decoding the first code word and the second code word using the second entropy coding lookup table.  Further, the method includes, if there is not a match, decoding the first code word using the first entropy coding lookup table.  
3. Representative Drawing: Fig. 1
2016178639.tif 000020
2016178639.tif 000021
2016178639.tif 000022
2016178639.tif 000023
2016178639.tif 000024
2016178639.tif 000025
2016178639.tif 000026
2016178639.tif 000027
2016178639.tif 000028