(57)【要約】【課題】符号化処理の高速化を達成するとともに、高い圧縮効率を維持することのできるハフマン符号化に適した符号化装置を得る。【解決手段】  テーブル作成部２は、生起確率算出回路２１及び最大値検出／符号割り当てモジュール２２を有し、符号化処理部１による符号化テーブル１３ａ，あるいは１３ｂを用いた符号化処理と並行して、更新用符号化テーブルを作成する。生起確率算出回路２１は、符号化処理部１のＣＡＭ１１より提供される符号化処理情報Ｓ１ａに基づき、符号データ毎に出現回数をカウントすることにより、最新の符号化前データＤ０に関する生起確率算出処理を行う。さらに、テーブル作成部２は、圧縮効率があらかじめ設定したしきい値を下回った場合に、符号化テーブル１３ａ，１３ｂ間における使用対象符号化テーブルと更新用符号化テーブルとの交換処理制御を行う。【選択図】図２
2006324944.tif 000002
【特許請求の範囲】
【請求項１】
符号化前データを受け、該符号化前データを使用対象符号化テーブルを用いて符号化処理を行い符号化後データを生成するとともに、前記符号化前データの出現状況を含む符号化処理情報を出力する符号化処理部と、
前記符号化処理部による前記符号化処理と並行して、前記符号化処理情報に基づき、前記符号化前データの生起確率算出処理を行い、その算出結果に基づき更新用符号化テーブルを作成するテーブル作成部とを備え、
前記テーブル作成部は、前記符号化処理における圧縮効率が所定の基準を満足しない場合、前記使用対象符号化テーブルを前記更新用符号化テーブルに置き換えることを特徴とする、
符号化装置。
【請求項２】
請求項１記載の符号化装置であって、
前記使用対象符号化テーブル及び更新用符号化テーブルは、それぞれアドレスに対応させて読み出しデータを格納する形式のテーブルを含み、
前記符号化処理部は、符号化前データの全パターンをアドレスに対応させて複数の参照データとして格納した参照データ格納領域を有するＣＡＭを含み、
前記ＣＡＭは、一致検索時に、所定の前記符号化前データを符号化対象データとし、前記複数の参照データのうち前記符号化対象データに一致する前記参照データのアドレスである一致信号アドレスを生成し、
前記符号化処理部は、前記使用対象符号化テーブルを参照し、前記一致信号アドレスに対応する読み出しデータを前記符号化後データとして出力する、
符号化装置。
【請求項３】
請求項２記載の符号化装置であって、
前記ＣＡＭは、前記複数の参照データに対応した複数の第１の検索結果ビットを格納する第１の検索結果格納レジスタをさらに有し、前記複数の第１の検索結果ビットは、前記一致検索時に対応する前記参照データと前記符号化対象データとの一致時にセット状態に設定され、
前記テーブル作成部は、前記複数の第１の検索結果ビットの内容に基づき、前記複数の参照データ単位の出現数をカウントすることにより前記生起確率算出処理を行う生起確率算出回路を有する、
符号化装置。
【請求項４】
請求項２記載の符号化装置であって、
前記ＣＡＭは、所定数の符号化前データを所定数の格納データとして格納する符号化前データ格納領域と、前記所定数の格納データに対応した所定数の第２の検索結果ビットを格納する第２の検索結果格納レジスタとをさらに有し、
前記ＣＡＭは、前記一致検索時に、前記符号化前データ格納領域に格納された前記所定数の格納データのうち一のデータを前記符号化対象データとして読み出し、前記符号化対象データと前記所定数の格納データそれぞれとが比較され、前記第２の検索結果格納レジスタにおける前記所定数の第２の検索結果ビットは対応する前記格納データの前記符号化対象データとの一致時にセット状態に設定され、
前記テーブル作成部は、前記所定数の第２の検索結果ビットのうちセット状態のビット数をカウントすることにより前記生起確率算出処理を行う生起確率算出回路を有する、
符号化装置。
【請求項５】
請求項４記載の符号化装置であって、
前記一致検索時において、前記所定数の格納データのうち、前記符号化対象データと同一値のデータが複数存在する場合、前記符号処理部による前記符号化対象データに対応する符号化後データの生成後に、前記符号化前データ格納領域内の前記所定数の格納データのうち、前記符号化対象データと同一値のデータを、前記符号化後データに書き換える書き換え処理を行う書き換え処理部をさらに備え、
前記ＣＡＭは、前記所定数の格納データに対応して設けられ、各々が前記書き換え処理の実行の有無を指示する所定数の書き換えフラグを格納するフラグビット格納レジスタをさらに有し、前記書き換え処理時に、前記書き換え処理対象となった前記格納データに対応する前記書き換えフラグをセット状態に設定し、
前記符号化処理部は、前記格納データを前記符号化対象データとして読み出す際、対応の前記書き換えフラグがセット状態のとき、前記格納データを符号化処理することなくそのまま符号化後データとして出力する、
符号化装置。
【請求項６】
請求項４あるいは請求項５記載の符号化装置であって、
前記生起確率算出回路は、
前記所定数の第２の検索結果ビットを一括して受ける少なくとも一つのシフトレジスタと、
前記少なくとも一つのシフトレジスタ内に取り込んだ前記所定数の第２の検索結果ビットの前記セット状態数をカウントするカウント部とを備える、
符号化装置。
【請求項７】
請求項６記載の符号化装置であって、
前記少なくとも一つのシフトレジスタは、各々が前記所定数の第２の検索結果ビットを一括して取り込み可能な複数のシフトレジスタを含み、
前記複数のシフトレジスタは、順次得られる前記所定数の第２の検索結果ビットに対し、前記複数のシフトレジスタのうち一のシフトレジスタが前記所定数の第２の検索結果ビットを取り込み、他のシフトレジスタがシフト動作を行うパイプライン処理が可能であり、
前記カウント部は前記複数のシフトレジスタの出力を選択的にカウントする選択的カウント部を含む、
符号化装置。
【請求項８】
請求項６記載の符号化装置であって、
前記少なくとも一つのシフトレジスタは、前記所定数の第２の検索結果ビットの一部を各々が取り込む複数の部分シフトレジスタを含み、
前記カウント部は、前記複数の部分シフトレジスタそれぞれ内に取り込んだ前記所定数の第２の検索結果ビットの一部のセット状態数を並列にカウントし、その総計を得る並列カウント部を含む、
符号化装置。
【請求項９】
請求項４あるいは請求項５記載の符号化装置であって、
前記生起確率算出回路は、
前記所定数の第２の検索結果ビットをビット単位に順次ツリー状に加算することにより前記生起確率算出処理を行う加算器群を含む、
符号化装置。
【請求項１０】
請求項４あるいは請求項５記載の符号化装置であって、
前記ＣＡＭにおける前記符号化前データ格納領域はデータの大小関係に基づき前記所定数の格納データをソーティングするソーティング機能を有し、
前記生起確率算出回路は、
ソーティング後の符号化前データ格納領域に対する前記一致検索時における前記所定数の第２の検索結果ビットの対応アドレスに基づき、前記所定数の第２の検索結果ビットのセット状態数をカウントするカウント部を含む、
符号化装置。
【請求項１１】
請求項４あるいは請求項５記載の符号化装置であって、
前記生起確率算出回路は、
前記所定数の第２の検索結果ビットを前記所定数の格納ビットとして取り込み、前記所定数の格納ビットのセット状態の有無に基づき分類するビットソーティング処理を行うソーティング回路と、
前記ビットソーティング処理後の前記ソーティング回路における前記所定数の格納ビットに基づき、前記所定数の格納ビットのセット状態数をカウントするカウント部とを含む、
符号化装置。
【請求項１２】
請求項４あるいは請求項５記載の符号化装置であって、
前記生起確率算出回路は、
前記所定数の第２の検索結果ビットを受け、前記所定数の第２の検索結果ビットのうち複数のビットがセット状態の場合に一のビットのみを有効するエンコード処理を行いプライオリティ処理後ビットデータを出力するプライオリティエンコード部と、
前記プライオリティ処理後ビットデータ中にセット状態のビット有無を認識可能なカウント部と、
前記所定数の第２の検索結果ビットのうち、前記プライオリティ処理後ビットデータにおいて一致を指示するビットに対応するビットのセット状態をリセットするリセット回路とを備え、
前記プライオリティエンコード部は、前記所定数の第２の検索結果ビット中にセット状態のビットが存在しなくなるまで前記エンコード処理を繰り返し行い、
前記カウント部はセット状態のビットを含む前記プライオリティ処理後ビットデータの受信回数に基づき、前記一致検索直後の前記所定数の第２の検索結果ビット中のセット状態数をカウントする、
符号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
ハフマン符号化は，データ圧縮で主流となっている方式の一つであり、音声、画像及び動画等のマルチメディアにおいてISOにより標準化されているJPEGやMPEG、ファイル圧縮形式の標準となっているZIP及びLHA等、ソフトウェアやハードウェアで幅広く実装されている効果的なロスレス圧縮手法である。
【０００２】
具体的には、JPEGやMPEGにおいて、画素の冗長なデータを削除した後に総データ量を圧縮するのに用いられ、LHAではデータ内に存在する同様の文字列を圧縮するのにハフマン符号化が用いられている。ハフマン符号化処理を行うハフマン符号化器及び画像処理装置として、例えば特許文献１に開示された符号化装置、特許文献２に開示された画像処理装置がある。
【背景技術】
【０００３】
【特許文献１】特開平８−５１３７０号公報
【特許文献２】特開２００５−１２４９５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
一般的なハフマン符号化のアルゴリズムは、符号化に用いる出現頻度表(符号化テーブル)を作成する必要があるため、圧縮前に一度全符号化前データを走査する必要があり、その後圧縮を行う仕組みになっている。そのためオンラインでの圧縮が難しい。
【０００５】
また、出現頻度を調べる処理を省くために既存の符号化テーブルを用いる方法やアルゴリズムの改良でその都度非符号化データと符号化したデータを混在して送る方法も提案されている。しかしながら、これらの方法は、前者の場合、既存の符号化テーブルが存在しないときには圧縮が不可能であり、後者の場合には圧縮効率（符号化前データに対する符号化後データのデータ量の比）が悪化し、実装が複雑になる等の問題がある。そのためハフマン符号化を様々なアプリケーションに適用したり、コンパクトに実装することが困難であるという問題点がある。以下、これらの問題点について詳述する。
【０００６】
（静的ハフマン符号化方式の問題点）
静的ハフマン符号化は最も広く実装されている形態である。現れる記号列を基にして、はじめに符号化テーブルを作成し、再び同様の記号列に対し作成した符号化テーブルを用いて圧縮を行う。しかしながらこの方法では、圧縮を行うためにデータを２回スキャンする必要があるため、オンラインでのリアルタイム圧縮は困難となる。
【０００７】
そのため実際はその都度符号化テーブルを作成することは少なく、標準的なデータを基に作成した既存のテーブル等を用意して符号化することが多い。この既存のテーブル(「静的テーブル」と呼ばれる)を用いた方法には、マイクロプロセッサベース、SRAMベース、PLA (Programmable Logic Array)ベース、並びにCAM(Content Addresable Memory)ベースのアーキテクチャが提案されている。マイクロプロセッサベースのアーキテクチャはソフトウェアで符号化が実現されるため、ハードウェアと比較して処理効率は低い。またSRAMベースアーキテクチャでは符号化する際、符号化テーブルから変換データを見つけるためのアドレスを計算することに数クロックサイクル必要となる。PLAベースアーキテクチャは、符号化テーブルの規模が大きくなるにつれてハードウエア量が増大する傾向にある。また、従来のCAMベースアーキテクチャは符号化テーブルを用いて単純に一致検索機能を行うだけなので、高速であるが柔軟性に欠ける。
【０００８】
これらの実装方法はいずれも、標準的なデータに基づく既存の符号化テーブルを利用するため、画像の傾向が急激に変化するような動画等のコンテンツの場合、圧縮効率が減少する恐れがあり、更に既存の符号化テーブルが存在しないようなアプリケーションには適用できない等の問題点があった。
【０００９】
（適応型ハフマン符号化方式の問題点）
静的ハフマン符号化の問題点である、オンラインでの圧縮、及び既存のテーブルが存在しない任意の記号列にあわせた圧縮を改善するために考えられたのが適応型ハフマン符号化である。
【００１０】
その特徴は記号を処理するごとにハフマン木を更新し、その時点で構成されたツリーによって符号化を行うものである。すなわち、符号化前の記号列全体を見て符号化を行わないため、オンラインでの処理が可能となり、符号化テーブルも作成する必要がない。
【００１１】
しかしながら、圧縮効率及びリアルタイム性についていくつかの問題も存在している。すなわち、アルゴリズムの特性上、符号化データに加えて初出現の記号は符号化せずに送らなければならないため、その分データ量が増加することになる。
【００１２】
更にデータの局所性により、集中的に出現した記号に短い符号が割り当てられたとしても、それ以降出現しない場合にはデータ量が大きくなるにつれて静的ハフマン符号化よりも圧縮効率が下がる場合があるという問題がある。
【００１３】
これに対しては符号化テーブルの定期的なリフレッシュという技法が取られることもあるが、過去のデータの生起確率を破棄することは逆に圧縮効率を悪化させることにもなる。
【００１４】
また、符号化の際にその都度ハフマン木を更新するため、処理により多くの時間を必要とする。これによりオンラインでの処理が可能だとしてもリアルタイムアプリケーションへの適用は向かない場合がある。
【００１５】
このハフマン木の更新処理時間を改善するためにアルゴリズムを改良する研究や木の更新にCAMを用いた高速化に関する研究が行われているが、適応型ハフマン符号化のハードウェアでの実装は難しく、その圧縮効果と比較してメリットが少ないという問題点があった。
【００１６】
この発明は上記問題点を解決するためになされたもので、符号化処理の高速化を達成するとともに、高い圧縮効率を維持することのできるハフマン符号化に適した符号化装置を得ることを目的とする。
【課題を解決するための手段】
【００１７】
この発明に係る請求項１記載の符号化装置は、符号化前データを受け、該符号化前データを使用対象符号化テーブルを用いて符号化処理を行い符号化後データを生成するとともに、前記符号化前データの出現状況を含む符号化処理情報を出力する符号化処理部と、前記符号化処理部による前記符号化処理と並行して、前記符号化処理情報に基づき、前記符号化前データの生起確率算出処理を行い、その算出結果に基づき更新用符号化テーブルを作成するテーブル作成部とを備え、前記テーブル作成部は、前記符号化処理における圧縮効率が所定の基準を満足しない場合、前記使用対象符号化テーブルを前記更新用符号化テーブルに置き換えている。
【発明の効果】
【００１８】
この発明における請求項１記載の符号化装置のテーブル作成部は、符号化処理部による符号化処理と並行して、更新用符号化テーブルを作成しているため、符号化処理の高速性を妨げることなく、最新の符号化前データに基づく更新用符号化テーブルを作成することができる。
【００１９】
さらに、テーブル作成部は、符号化処理における圧縮効率が所定の基準を満足しない場合、使用対象符号化テーブルを更新用符号化テーブルに置き換えるため、常に高い圧縮効率を維持できる。
【発明を実施するための最良の形態】
【００２０】
＜ＣＡＭの概要＞
本発明に係る符号化装置は、ＣＡＭ(Content Addressable Memory)を用いたハフマン符号化アーキテクチャを有している。まず、ＣＡＭの一般的な概要について説明する。
【００２１】
図１８はＣＡＭの概念を示す説明図である。ＣＡＭは連想メモリと呼ばれる機能メモリの一種である。図１８(a) に示す一般的なＲＡＭ (Random Access Memory)等のメモリは、アドレスを用いて格納している各データを参照するのに対して、ＣＡＭは同図(b) に示すように、CAMは格納しているデータの内容に基づいて、比較データとの比較結果（一致信号及び一致したデータの格納アドレス）を出力する機能を有してるため、各格納データを参照することができる、「内容番地付けメモリ」とみなすことができる。
【００２２】
そのため通常のメモリは、内部にデータを格納する際、各々に固有の番号であるアドレスを付加している。そのためアドレスが入力されたならば、それに応じて格納しているデータを出力することができる。従って、ある比較データに一致するデータをＲＡＭ内で検索する場合には、順にアドレスを入力し、そこに格納されているデータを順に確認していかなければならない。
【００２３】
これに対し、ＣＡＭは、内部のメモリ領域に格納している参照 (比較対照)データに対し、検索データとなる比較データが入力された場合、内部に有する比較器によって全参照データを一定のクロックサイクルで全て一致検索し、一致しているものがあれば該当するデータに対して一致信号を出力することができる。また、同時に一致した参照データのアドレスを出力することもできる。その他の機能としては、マスクを用いて特定のビットのみを一致検索することも可能である。
【００２４】
ＣＡＭの一致検索は、本質的に並列に行われるため、メモリ内の参照データ数が増加するにつれて、通常のＲＡＭと比較して非常に高速かつ効率的に検索結果を得ることができる利点を有する。
【００２５】
＜基本構成＞
図１は、この発明に発明に係るＣＡＭベースのハフマン符号化アーキテクチャを有する符号化装置の内部構成の概略を示すブロック図である。同図において、符号化処理部１は内部に現在の符号化に用いる使用対象符号化テーブル（図１では図示せず）と次に置き換えるべき更新用符号化テーブル（図１では図示せず）を少なくも有していることを前提としている。
【００２６】
同図に示すように、符号化処理部１は符号化前データＤ０を入力し、内部の使用対象符号化テーブルを用いて符号化前データＤ０をハフマン符号化して得られる符号化後データＤ１を出力処理部３に出力するとともに、同時に得られる符号化前データＤ０の出現情報を含む符号化処理情報Ｓ１をテーブル作成部２に出力する。そして、出力処理部３は符号化後データＤ１に基づき出力データＤ３を出力する。
【００２７】
テーブル作成部２は、符号化処理部１の符号化処理と並行して、符号化処理情報Ｓ１に基づき、符号化前データＤ０の生起確率算出処理を行い、その算出結果に基づきハフマン木を更新して更新用符号化テーブルの更新処理を行う。上記更新処理の内容はテーブル更新情報Ｓ２として符号化処理部１に適宜与えられる。
【００２８】
そして、テーブル作成部２は、圧縮効率が所定の基準を満足しない場合、符号化テーブル変更の必要性があると判断し、図示しない符号化テーブル更新指令を符号化処理部１に与え、符号化処理部１内部の使用対象符号化テーブルを更新用符号化テーブルに置き換えさせる。
【００２９】
＜（逐次符号化方式）＞
アプリケーションによっては，符号化前のデータが逐次的に次々送られてくる状況が考えられる。このようなアプリケーションに対して設けられたのが、逐次符号化方式を採用したＣＡＭベースの符号化アーキテクチャを有する、実施の形態１の符号化装置である。
【００３０】
図２は実施の形態１の符号化装置の全体構成の示す説明図である。同図に示すように、符号化前データＤ０を取り込む符号化処理部１は内部にＣＡＭ１１、スイッチ１７、符号化テーブル１３ａ，１３ｂ（ＲＡＭ１３）を有している。
【００３１】
符号化処理部１内のＣＡＭ１１は、逐次的に送られてくる符号化前データＤ０を比較データとして逐次取り込み、一致検索処理を実行する。ＣＡＭ１１には符号化テーブル１３ａ，１３ｂ（ＲＡＭ１３）に対応すべく符号化前データの全パターンが参照データとして格納されているため、検索結果によって得られる、比較データとの一致を指示する一致信号のアドレス（一致信号アドレス）を含む一致検出結果信号Ｓ１１をスイッチ１７に出力することができる。
【００３２】
さらに、符号化処理部１は上記一致検索処理時に得られた符号化処理情報Ｓ１ａをテーブル作成部２に出力する。
【００３３】
また、符号化処理部１は内部に２つの符号化テーブル１３ａ，１３ｂを有しており、スイッチ１７によって符号化テーブル１３ａ，１３ｂのうち、一方が使用対象符号化テーブルとなり、他方が更新用符号化テーブルとして選択される。したがって、一致検出結果信号Ｓ１１はスイッチ１７によって符号化テーブル１３ａ，１３ｂのうち使用対象符号化テーブルとなっているテーブルに選択的に出力される。
【００３４】
テーブル作成部２は、符号化処理部１による符号化テーブル１３ａ，あるいは１３ｂを用いた符号化処理と並行して、更新用符号化テーブルを作成する処理部である。テーブル作成部２は内部に生起確率算出回路２１及び最大値検出／符号割り当てモジュール２２を有している。
【００３５】
生起確率算出回路２１は、符号化処理部１のＣＡＭ１１より提供される符号化処理情報Ｓ１ａに基づき、符号データ毎に出現回数をカウントすることにより、最新の符号化前データＤ０に関する生起確率算出処理を行う。そして、生起確率算出回路２１により算出された生起確率算出処結果は最大値検出／符号割り当てモジュール２２に入力される。
【００３６】
最大値検出／符号割り当てモジュール２２は、符号データ毎の出現回数があらかじめ決めた設定値になるか，カウント可能な最大値（ＭＡＸ）になるか，もしくは圧縮効率がしきい値を下回った場合に、頻度の大きいものから順にビット長の短いハフマン符号の割り当てを行い，新規な更新用符号化テーブル作成用の符号テーブル作成用データＳ２２を作成する。
【００３７】
テーブル作成部２による更新用符号化テーブル作成処理は、符号化処理部１による符号化処理と並行に実行され，最近の符号化前データＤ０の出現頻度に基づいた，新規の更新用符号化テーブル作成用の符号テーブル作成用データＳ２２が得られる。
【００３８】
さらに、テーブル作成部２は、圧縮効率があらかじめ設定したしきい値を下回った場合に、符号化テーブル１３ａ，１３ｂ間における使用対象符号化テーブルと更新用符号化テーブルとの交換処理制御を行う。例えば、使用対象符号化テーブルが符号化テーブル１３ａ、更新用符号化テーブルが符号化テーブル１３ｂの場合に、使用対象符号化テーブルを符号化テーブル１３ｂに、更新用符号化テーブルを符号化テーブル１３ａに置き換える指令をスイッチ１７に与える。その結果、符号化処理部１は常に圧縮効率がしきい値を下回るこのなく、高い圧縮効率を維持することができる。
【００３９】
テーブル作成部２による圧縮効率がしきい値を下回るか否かは、符号長が長い符号前データのカウント値が大きくなったことをロジックで判定する等により行うことができる。
【００４０】
符号化テーブル１３ａ，１３ｂより出力される符号化後データＤ１は、出力処理部３に取り込まれる。出力処理部３は、内部にシフタ３１、バッファ３２ａ，３２ｂ、及びスイッチ３３を有し、符号化後データＤ１をシフタ３１及びバッファ３２ａ，３２ｂにてバファリング処理して、出力データＤ３として出力する。
【００４１】
図３は実施の形態１の符号化装置の詳細構成を示す説明図である。同図に示すように、ＣＡＭ１１は、アドレスデコーダ１４、比較レジスタＲＣ、マスクレジスタＲＭ、参照データ格納領域ＲＧ１、第１の検索結果格納レジスタである検索結果格納レジスタＲ１、プライオリティエンコーダ１５、一致信号及びアドレス生成回路１６から構成される。スイッチ１７はセレクタ１７ａ，１７ｂにより構成され、符号化テーブル１３ａ，１３ｂの後段にはセレクタ１８が設けられる。
【００４２】
比較レジスタＲＣは符号化前データＤ０を取り込み、マスクレジスタＲＭはマスクするビットを指示するマスクデータを格納する。参照データ格納領域ＲＧ１には記号等を指示する符号化前データの全パターンが参照データＤＲ１〜ＤＲｎとして格納されている。
【００４３】
アドレスデコーダ１４は読み出し／書き込みアドレスＡｄをデコードして選択アドレスを決定し、符号化処理部１から選択アドレスｉ（ｉ＝１〜ｎ）に対応する参照データＤＲｉにアクセスし、読み出し時には参照データＤＲとして出力することができる。検索結果格納レジスタＲ１は参照データ格納領域ＲＧ１内に格納された参照データＤＲ１〜ＤＲｎに対応して検索結果ビットＤＢ１〜ＤＢｎを格納するレジスタである。検索結果格納レジスタＲ１は、内部の検索結果ビットＤＢ１〜ＤＢｎを読み出し可能にプライオリティエンコーダ１５に接続される。
【００４４】
プライオリティエンコーダ１５は検索結果ビットＤＢ１〜ＤＢｎの情報に基づき、セット状態（“１”格納）の一致検索結果ビットＤＢｉに対応するアドレスを一致信号アドレスとして一致信号及びアドレス生成回路１６に出力する。一致信号及びアドレス生成回路１６は、検索結果が一致したことを示す一致信号Ｓ１１ａと、一致信号アドレスを指示する一致アドレス信号Ｓ１１ｂをセレクタ１７ａ，１７ｂに出力する。
【００４５】
セレクタ１７ａ，１７ｂは活性状態時に符号化テーブル１３ａ，１３ｂに対し、活性／非活性を指示するイネーブル信号ＥＮａ，ＥＮｂ、書き込み／読み出しを指示する書き込み信号ＷＲａ，ＷＲｂ、選択アドレスを指示する選択アドレス信号ＳＡａ，ＳＡｂ、書き込みデータを指示する符号データＤＨａ，ＤＨｂを出力する。セレクタ１７ａ，１７ｂの活性／非活性は制御回路２３からの制御信号Ｓ２５によって制御される。
【００４６】
符号化テーブル１３ａ，１３ｂはセレクタ１７ａ，１７ｂからの上述した各種信号に基づき、読み出しデータＤ１３ａ，Ｄ１３ｂをセレクタ１８に出力する。セレクタ１８は制御回路２３からの制御信号Ｓ３２に基づき、読み出しデータＤ１３ａ，Ｄ１３ｂのうちの一方を符号化後データＤ１として出力する。
【００４７】
生起確率算出回路２１は内部にカウンタＣＴ１〜ＣＴｎを有し、これらのカウンタＣＴ１〜ＣＴｎは検索結果格納レジスタＲ１の検索結果ビットＤＢ１〜ＤＢｎに対応して設けられ、対応する検索結果ビットＤＢが一致検索結果ビットＤＢｉとして“１”（セット状態）になる度にカウントアップする。したがって、検索結果ビットＤＢ１〜ＤＢｎが図２の符号化処理情報Ｓ１ａとなる。
【００４８】
最大値検出／符号割り当てモジュール２２は、カウンタＣＴ１〜ＣＴｎそれぞれのカウント値である生起確率算出結果に基づき、カウント値の大きいカウンタＣＴに対応するアドレスから順にハフマン符号を割り当てることにより、ハフマン符号による符号化テーブルを新たに作成するための符号用アドレス信号Ｓ２２ａ、符号用データ信号Ｓ２２ｂをセレクタ１７ａ，１７ｂに出力する。
【００４９】
制御回路２３は符号化後データＤ１、閾値データＤ２１、設定値データＤ２２を受けるとともに、最大値検出／符号割り当てモジュール２２から制御信号Ｓ２２ｃを受け、これらの信号に基づき、最大値検出／符号割り当てモジュール２２に情報伝達信号Ｓ２３を、プライオリティエンコーダ１５に制御信号Ｓ２４を、セレクタ１７ａ，１７ｂに制御信号Ｓ２５を、セレクタ２０に制御信号Ｓ３２を与える。なお、情報伝達信号Ｓ２３には閾値データＤ２１、設定値データＤ２２及び符号化後データＤ１等の情報が含まれる。
【００５０】
セレクタ１７ａ，１７ｂは制御信号Ｓ２５に基づき、一方は一致信号及びアドレス生成回路１６からの一致信号Ｓ１１ａ及び一致アドレス信号Ｓ１１ｂに基づく符号化処理用に機能し、他方は最大値検出／符号割り当てモジュール２２からの符号用アドレス信号Ｓ２２ａ及び符号用データ信号Ｓ２２ａに基づく符号化テーブル更新処理用に機能する。
【００５１】
図４は実施の形態１の符号化装置における符号化処理及び符号化テーブル作成処理を示すフローチャートである。以下、同図を参照して、実施の形態１の動作について詳述する。なお、説明の都合上、現在の使用対象符号化テーブルを符号化テーブル１３ａ、更新用符号化テーブルを符号化テーブル１３ｂと仮定する。なお、図４で述べる処理は、全体的な制御は制御回路２３によって行われ、個々の動作は符号化処理部１、テーブル作成部２及び出力処理部３によってそれぞれ実行される。また、図４において、各構成部１〜３の実行として便宜上分類していているが、実際には他の構成部が行う場合もある。
【００５２】
図４のステップＳＴ１において、符号化前データＤ０を逐次入力する。符号化前データＤ０はＣＡＭ１１の比較レジスタＲＣ内に取り込まれる。図３の例では、比較レジスタＲＣに符号化前データＤ０である“０００…００１”が比較データＤＣとして格納され、マスクレジスタＲＭはマスクをかけていない状態である全て“０”のマスクデータが設定されている場合を示している。
【００５３】
次に、ステップＳＴ２において、セレクタ１７ａ，１７ｂは、最大値検出／符号割り当てモジュール２２からの制御信号Ｓ２２ｃ及び制御回路２３からの制御信号Ｓ２５を介して、「圧縮効率≦しきい値」である（YES）か否か（NO）を認識し、ＹＥＳの場合はステップＳＴ３に移行し、ＮＯの場合はステップＳＴ７で符号化テーブルの交換処理（使用対象符号化テーブルである符号化テーブル１３ａと更新用符号化テーブルである符号化テーブル１３ｂとを置き換える理）を行った後、ステップＳＴ３に移行する。
【００５４】
ステップＳＴ３において、ＣＡＭ１１内で符号化前データＤ０と参照データ格納領域ＲＧ１の参照データＤＲ１〜ＤＲｎとの一致検索を行う。一致検索において、参照データ格納領域ＲＧ１内の参照データのいずれかと符号化前データＤ０とは必ず一致し、一致した参照データ（一致参照データＤＲｉ（ｉ＝１〜ｎのいずれか））に対応する検索結果格納レジスタＲ１の一致検索結果ビットＤＢｉが“１”（セット状態）に設定される。図３では比較データＤＣである“０００…００１”に対応する検索結果ビットＤＢが“１”にセットされている。
【００５５】
その後、ステップＳＴ４において、符号化テーブル１３ａへの一致信号アドレスへの送信処理を行う。以下、この処理について詳述する。
【００５６】
前述したように、プライオリティエンコーダ１５が検索結果格納レジスタＲ１内の検索結果ビットＤＢ１〜ＤＢｎの情報に基づき、一致検索結果ビットＤＢｉに対応するアドレスを一致信号アドレスとして一致信号及びアドレス生成回路１６に出力する。一致信号及びアドレス生成回路１６は、検索結果が一致したことを示す一致信号Ｓ１１ａと、一致信号アドレスを指示する一致アドレス信号Ｓ１１ｂをセレクタ１７ａ，１７ｂに出力する。
【００５７】
このとき、制御信号Ｓ２５によって、符号化テーブル１３ａに対応するセレクタ１７ａが有効状態とされているため、セレクタ１７ａはイネーブル信号ＥＮａを活性状態、書き込み信号ＷＲａを非活性状態（読み出し状態）にし、一致信号Ｓ１１ａ及び一致アドレス信号Ｓ１１ｂに基づき、一致信号アドレスを指示する選択アドレス信号ＳＡａを符号化テーブル１３ａに出力する。
【００５８】
その結果、ステップＳＴ５において、符号化処理部１は、符号化テーブル１３ａを参照し、選択アドレス信号ＳＡａで指示されたアドレスに格納された符号データを読み出しデータＤ１３ａとしてセレクタ１８に出力する。そして、セレクタ１８は制御回路２３からの制御信号Ｓ３２に従い、読み出しデータＤ１３ａを符号化後データＤ１として出力する。
【００５９】
そして、ステップＳ６において、最終的に出力処理部３から出力データＤ３が出力される。すなわち、出力処理部３は、符号化後データＤ１をシフタ３１によってバッファ３２ａ，３２ｂの一方に出力し、フル状態になれば他方のバッファに出力先を切り換え、この間、スイッチ３３の制御下でフル状態となった一方のバッファから出力データＤ３として出力する。
【００６０】
図５はステップＳＴ５の処理におけるＣＡＭ１１とＲＡＭ１３との関係を示す概念図である。説明の都合上、ＣＡＭ１１及びＲＡＭ１３のアドレスを２ビットで示し、ＣＡＭ１１が格納する参照データ、ＲＡＭ１３が格納する符号データをそれぞれ３ビットで示している。
【００６１】
図５に示すように、符号化前データＤ０として“１１１”が入力された場合、ＣＡＭ１１の参照データ格納領域ＲＧ１内における“１１１”と一致し、この“１１１”はアドレス３５の“１０”に相当する。図３の構成で説明すれば、検索結果ビットＤＢ１〜ＤＢｎのうち“１”を格納したビットについて、プライオリティエンコーダ１５よってエンコードされたアドレスが“１０”となる。このアドレス“１０”を規定した信号が一致アドレス信号Ｓ１１ｂとなる。
【００６２】
一致アドレス信号Ｓ１１ｂを受けたＲＡＭ１３（符号化テーブル１３ａ，１３ｂ）は、一致アドレス信号Ｓ１１ｂに基づき、格納符号データ３７中のデータから、符号データ用アドレス３６における“１０”に対応するデータ“０１０”を読み出し、このデータ“０１０”を符号化後データＤ１として出力する。
【００６３】
このように、一致アドレス信号Ｓ１１ｂに基づくＣＡＭ１１とＲＡＭ１３とによる連携によって高速に符号化後データＤ１を得ることができる。
【００６４】
図６は、ＣＡＭ１１とＲＡＭ１３との接続例を示す説明図である。同図に示すように、ＣＡＭ１１の一致信号線ＣＬ１〜ＣＬｎとＲＡＭ１３のワード線ＷＬ１〜ＷＬｎとを結線部４９により結線している。
【００６５】
ＣＡＭ１１の一致信号線ＣＬ１〜ＣＬｎは、参照データＤＲ１〜ＤＲｎに対応して設けられ、参照データＤＲ１〜ＤＲｎそれぞれに対応して所定ビット数のメモリセルＭＣ１１が設けられ、メモリセルＭＣ１１毎に比較器ＣＰ１〜ＣＰｎ（参照データＤＲ１〜ＤＲｎに対応）が設けられる。
【００６６】
一方、ＲＡＭ１３のワード線ＷＬ１〜ＷＬｎは、符号データＤＨ１〜ＤＨｎに対応して設けられ、符号データＤＨ１〜ＤＨｎそれぞれに対応して所定ビット数のメモリセルＭＣ１３が設けられる。
【００６７】
このような接続関係のＣＡＭ１１，ＲＡＭ１３において、一致参照データＤＲｉ（ｉ＝１〜ｎのいずれか）に対応する一致信号線ＣＬｉのみが、所定ビット数の比較器ＣＰｉによって活性状態に設定される。
【００６８】
その結果、一致信号線ＣＬｉに接続されるワード線ＷＬｉのみが活性状態となり、当該ワード線ＷＬｉに接続されたメモリセルＭＣ１３の格納データである符号データＤＨｉが読み出しデータＤ１３として読み出される。
【００６９】
このように、ＣＡＭ１１の一致信号線ＣＬ１〜ＣＬｎとＲＡＭ１３のワード線ＷＬ１〜ＷＬｎとを結線部４９により結線することにより、図５で示すＣＡＭ１１のアドレス３５、ＲＡＭ１３の符号データ用アドレス３６の設定を不要にできる分、より小さい面積に集積することが可能となる効果を奏する。
【００７０】
図３及び図４に戻って、テーブル作成部２は、符号化処理部１によるステップＳＴ３の一致検索処理に並行して、ステップＳＴ８において、参照データＤＲ１〜ＤＲｎ毎の一致回数をカウントする処理を行う。以下、この処理内容ついて詳述する。
【００７１】
生起確率算出回路２１の内部のカウンタＣＴ１〜ＣＴｎは、対応する検索結果ビットＤＢ１〜ＤＢｎが“１”になる度にカウントアップする。したがって、逐次入力される符号化前データＤ０において、検索結果ビットＤＢ１〜ＤＢｎ、すなわち、参照データＤＲ１〜ＤＲｎそれぞれの一致回数をカウンタＣＴ１〜ＣＴｎによってカウントする。
【００７２】
そして、ステップＳＴ９で、カウンタＣＴ１〜ＣＴｎのカウント値のいずれかが設定値（設定値データＤ２２で規定）に達するか(YES)否か(NO)、ステップＳＴ１０でカウンタＣＴ１〜ＣＴｎのいずれかがカウント可能な最大値（MAX）に達するか(YES)否か(NO)、ステップＳＴ１１で圧縮効率がしきい値（閾値データＤ２１で規定）を下回っているか(YES)否か(NO)がチェックされる。
【００７３】
そして、ステップＳＴ９でＹＥＳ，ＳＴ１０でＹＥＳ、あるいはステップＳＴ１１でＮＯと判定されると、ステップＳＴ１２の処理に移行する。
【００７４】
ステップＳＴ１２において、最大値検出／符号割り当てモジュール２２は、カウンタＣＴ１〜ＣＴｎそれぞれのカウント値に基づき、カウント値の大きいカウンタＣＴに対応するアドレス（符号前データ）から順にハフマン符号を割り当てることにより、更新用符号化テーブルに必要なハフマン符号による新規符号化テーブルを作成する。
【００７５】
そして、ステップＳＴ１３に移行し、ステップＳＴ１２で作成された新規符号化テーブルに基づきアドレスを規定する符号用アドレス信号Ｓ２２ａと、アドレスに対応する符号データを規定する符号用データ信号Ｓ２２ａとをセレクタ１７ａ，１７ｂに出力することにより、符号化テーブル更新処理を実行する。
【００７６】
現在の更新用符号化テーブルは符号化テーブル１３ｂであるため、制御信号Ｓ２５の制御下でセレクタ１７ｂは活性状態を指示するイネーブル信号ＥＮｂ、書き込みを指示する書き込み信号ＷＲｂにするとともに、符号用アドレス信号Ｓ２２ａにより規定されたアドレスを指示する選択アドレス信号ＳＡｂ、及び符号用データ信号Ｓ２２ａにより規定された符号データを指示する符号データＤＨｂを、符号化テーブル１３ｂに順次出力することにより、符号化テーブル１３ｂの内容を更新する。
【００７７】
その後、ステップＳＴ７に移行し、ステップＳＴ１２の実行原因がステップＳＴ１１がＮＯの場合（圧縮効率がしきい値を下回っていた場合）、使用対象の符号化テーブルを符号化テーブル１３ａから符号化テーブル１３ｂに切り換える。なお、ステップＳＴ１３後にステップＳＴ７が実行される場合は、ステップＳＴ７で終了し、ステップＳＴ２に移行することはない。ステップＳＴ２に移行するのはステップＳＴ１でＮＯと判断され後にステップＳＴ７が実行された場合のみである。
【００７８】
このように、実施の形態１の符号化装置においては、逐次的に入力される符号化前データＤ０に対し、リアルタイムに符号化処理部１によって符号化を行いながら，圧縮効率を維持するために，常に最適な更新用符号化テーブルをテーブル作成部２によって用意することが可能となる。
【００７９】
そして、テーブル作成部２の生起確率算出回路２１は、検索結果格納レジスタＲ１に検索結果ビットＤＢ１〜ＤＢｎの内容に基づくことにより、最新の符号化前データＤ０の出現情報を正確かつ高速に認識可能な生起確率算出処理を行うことができる。
【００８０】
その結果、静的ハフマン符号化や適応型ハフマン符号化の問題点を解決し、ハフマン符号化処理の高速化を達成するとともに、高い圧縮効率を維持することのできるハフマン符号化に適した符号化装置を得ることができる。
【００８１】
＜実施の形態２（格納符号化方式）＞
符号化前のデータが事前にメモリ等に格納されている，もしくは格納してから符号化処理を行うようなアプリケーションに対して設けられたのが、格納符号化方式を採用したＣＡＭベースの符号化アーキテクチャを有する、実施の形態２の符号化装置である。
【００８２】
図７は実施の形態２の符号化装置の全体構成の示す説明図である。同図に示すように、符号化前データＤ０を取り込む符号化処理部５は内部にＣＡＭ１９、スイッチ１７、符号化テーブル１３ａ，１３ｂ（ＲＡＭ１３）を有している。
【００８３】
符号化処理部５内のＣＡＭ１９は、順次入力される符号化前データＤ０を所定数分を所定数の格納データとして内部に符号化前データ格納領域ＲＧ２（後に示す図８参照）に取り込んだ後、一括して一致検索処理を実行する。ＣＡＭ１９には、実施の形態１のＣＡＭ１１と同様、符号化テーブル１３ａ，１３ｂに対応すべく符号化前データの全パターンが参照データ格納領域ＲＧ１に格納されているため、検索結果によって得られる、比較データとの一致を指示する一致信号のアドレス（一致信号アドレス）を含む一致検出結果信号Ｓ１９をスイッチ１７に出力する。
【００８４】
さらに、符号化処理部５は上記一致検索処理時に得られた符号化処理情報Ｓ１ｂをテーブル作成部６に出力する。
【００８５】
また、符号化処理部５は内部に２つの符号化テーブル１３ａ，１３ｂを有しており、スイッチ１７によって符号化テーブル１３ａ，１３ｂのうち、一方が使用対象符号化テーブルとなり、他方が更新用符号化テーブルとして選択される。したがって、一致検出結果信号Ｓ１９はスイッチ１７によって符号化テーブル１３ａ，１３ｂのうち使用対象符号化テーブルとなっているテーブルに選択的に出力される。
【００８６】
なお、ＣＡＭ１９、ＲＡＭ１３（符号化テーブル１３ａ，１３ｂ）間は、実施の形態１における図６の例と同様、ＣＡＭ１９の一致信号線とＲＡＭ１３のワード線をスイッチ１７を介して結線するように構成し、集積度の向上を図ることができる。
【００８７】
符号化テーブル１３ａ，１３ｂより出力される符号化後データＤ１は、出力処理部３に取り込まれる。出力処理部３は、符号化後データＤ１をシフタ３１によってバッファ３２ａ，３２ｂの一方に出力し、フル状態になれば他方のバッファに出力先を切り換え、この間、スイッチ３３の制御下でフル状態となった一方のバッファから出力データＤ３として出力する。
【００８８】
テーブル作成部６は、実施の形態１のテーブル作成部２と同様、符号化処理部５の処理と並行し更新用符号化テーブルを作成する処理部である。テーブル作成部６は内部に生起確率算出回路２４及び最大値検出／符号割り当てモジュール２２を有する。
【００８９】
さらに、テーブル作成部６は、実施の形態１のテーブル作成部２と同様、圧縮効率があらかじめ設定したしきい値を下回った場合に、符号化テーブル１３ａ，１３ｂ間における使用対象符号化テーブルと更新用符号化テーブルとの交換処理制御を行う。
【００９０】
テーブル作成部６内の生起確率算出回路２４は、符号化処理部５のＣＡＭ１９より提供される符号化処理情報Ｓ１ｂに基づき、符号化前データ格納領域ＲＧ２（後に示す図８参照）の格納データ（符号化前データＤ０）の生起確率算出処理を行う。そして、生起確率算出回路２４の生起確率算出結果は最大値検出／符号割り当てモジュール２２に入力される。
【００９１】
最大値検出／符号割り当てモジュール２２は、生起確率算出結果に基づき、（符号化前データの内容に対応する）アドレス単位の出現回数（一致回数）を認識し、当該出現回数があらかじめ決めた設定値になるか，カウント可能な最大値（ＭＡＸ）になるか，もしくは圧縮効率がしきい値を下回った場合に、頻度の大きいものから順にビット長の短いハフマン符号の割り当てを行い，新規の更新用符号化テーブルを作成する。
【００９２】
テーブル作成部６による新規符号化テーブル作成処理は、符号化処理部５による符号化処理と並行に実行される。
【００９３】
また、参照データ書き換え処理部４は内部にフィードバック回路４１を有し、符号化後データＤ１受け、ＣＡＭ１９に書き換え制御信号Ｓ４１を与え、ＣＡＭ１９の符号化前データ格納領域ＲＧ２（後に示す図８参照）内に符号化前データＤ０が複数格納されている場合に、一括して符号化後データＤ１に書き換える書き換え処理を符号化前データ格納領域ＲＧ２（後に示す図８参照）内の格納データに対して行う。
【００９４】
図８は実施の形態２の符号化装置の詳細構成を示す説明図である。同図に示すように、ＣＡＭ１９は、アドレスデコーダ１４、比較レジスタＲＣ、マスクレジスタＲＭ、参照データ格納領域ＲＧ１、符号化前データ格納領域ＲＧ２、検索結果格納レジスタＲ１、第２の検索結果格納レジスタである検索結果格納レジスタＲ２、及びフラグビット格納レジスタＲ４、一致信号及びアドレス生成回路１６から構成される。スイッチ１７はセレクタ１７ａ，１７ｂにより構成され、符号化テーブル１３ａ，１３ｂの後段にはセレクタ２０が設けられる。
【００９５】
比較レジスタＲＣは、アドレスデコーダ１４によって選択された符号化前データ格納領域ＲＧ２内の符号処理選択アドレスに格納された符号化前データを取り込み、マスクレジスタＲＭはマスクするビットを指示するマスクデータを格納する。参照データ格納領域ＲＧ１には、符号化前データの全パターンが参照データＤＲ１〜ＤＲｎとして格納されている。
【００９６】
アドレスデコーダ１４は読み出し／書き込みアドレスＡｄをデコードして参照データ格納領域ＲＧ１あるいは符号化前データ格納領域ＲＧ２用の符号処理選択アドレスを決定する。ＣＡＭ１９は、符号化処理時には符号化前データ格納領域ＲＧ２内に格納された符号化前データを比較レジスタＲＣに順次出力され、比較レジスタＲＣの比較データＤＣと参照データ格納領域ＲＧ１内の参照データＤＲ１〜ＤＲｎとの一致検索処理を行い、書き換え処理時に、比較データＤＣに一致する符号化前データ格納領域ＲＧ２内の格納データを全て符号化後データＤ１に書き換える。
【００９７】
検索結果格納レジスタＲ１は参照データ格納領域ＲＧ１内に格納された参照データＤＲ１〜ＤＲｎに対応して、第１の検索結果ビットである検索結果ビットＤＢ１〜ＤＢｎを格納するレジスタである。検索結果格納レジスタＲ１は、内部の検索結果ビットＤＢ１〜ＤＢｎを読み出し可能に一致信号及びアドレス生成回路１６に接続される。
【００９８】
検索結果格納レジスタＲ２は符号化前データ格納領域ＲＧ２（アドレスに対応してｍ個格納可能と仮定）内に格納された格納データＤＳ１〜ＤＳｍに対応して第２の検索結果ビットである検出結果ビットＣＤ１〜ＣＤｍを格納するレジスタである。検索結果格納レジスタＲ２は、内部の検出結果ビットＣＤ１〜ＣＤｍを読み出し可能に生起確率算出回路２４に接続される。
【００９９】
一致信号及びアドレス生成回路１６は検索結果ビットＤＢ１〜ＤＢｎの情報に基づき、一致検索結果ビットＤＢｉに対応するアドレスを一致信号アドレスとし、検索結果が一致したことを示す一致信号Ｓ１１ａと、一致信号アドレスを指示する一致アドレス信号Ｓ１１ｂをセレクタ１７ａ，１７ｂに出力する。
【０１００】
セレクタ１７ａ，１７ｂは符号化テーブル１３ａ，１３ｂに対し、活性／非活性を指示するイネーブル信号ＥＮａ，ＥＮｂ、書き込み／読み出しを指示する書き込み信号ＷＲａ，ＷＲｂ、選択アドレスを指示する選択アドレス信号ＳＡａ，ＳＡｂ、書き込みデータを指示する符号データＤＨａ，ＤＨｂを出力する。セレクタ１７ａ，１７ｂの活性／非活性は制御回路２５からの制御信号Ｓ２５によって制御される。
【０１０１】
符号化テーブル１３ａ，１３ｂはセレクタ１７ａ，１７ｂからの各種信号に基づき、読み出しデータＤ１３ａ，Ｄ１３ｂをセレクタ２０に出力する。セレクタ２０は制御回路２５からの制御信号Ｓ３２に基づき、読み出しデータＤ１３ａ，Ｄ１３ｂのうちの一方を符号化後データＤ１として出力する。
【０１０２】
生起確率算出回路２４は検索結果格納レジスタＲ２の検出結果ビットＣＤ１〜ＣＤｍ及び一致アドレス信号Ｓ１１ｂに基づき、参照データＤＲ１〜ＤＲｎのうち一致アドレス信号Ｓ１１ｂの指示する参照データ（符号化前データ）の一致回数（出現回数）をカウントする生起確率算出処理を行う。したがって、符号化処理情報Ｓ１ｂは、検出結果ビットＣＤ１〜ＣＤｍ及び一致アドレス信号Ｓ１１ｂとなる。なお、一致アドレス信号Ｓ１１ｂの代わりに比較データＤＣやセット状態の格納データＤＳ等を取り込んでもよい。
【０１０３】
最大値検出／符号割り当てモジュール２２は、生起確率算出回路２４より得られる生起確率算出結果に基づき、カウント値の大きいカウンタＣＴに対応するアドレス（符号前データ）から順にハフマン符号を割り当てることにより、ハフマン符号による新たな更新用符号化テーブルを作成し、当該更新用符号化テーブル作成用の符号用アドレス信号Ｓ２２ａ、符号用データ信号Ｓ２２ｂをセレクタ１７ａ，１７ｂに出力する。
【０１０４】
制御回路２５は符号化後データＤ１、閾値データＤ２１、設定値データＤ２２を受けるとともに、最大値検出／符号割り当てモジュール２２から制御信号Ｓ２２ｃを受け、これらの信号に基づき、最大値検出／符号割り当てモジュール２２に情報伝達信号Ｓ２３を、セレクタ１７ａ，１７ｂに制御信号Ｓ２５を、セレクタ２０に制御信号Ｓ３２を、生起確率算出回路２４に制御信号Ｓ２０を、フラグビット格納レジスタＲ４及び生起確率算出回路２４にリセット信号Ｓ２６を与える。なお、情報伝達信号Ｓ２３には閾値データＤ２１、設定値データＤ２２及び符号化後データＤ１等の情報が含まれる。
【０１０５】
さらに、制御回路２５及び符号化後データＤ１がＣＡＭ１９に帰還する信号線５０と共に、参照データ書き換え処理部４内のフィードバック回路４１として機能し、書き換えを指示する書き換え制御信号Ｓ４１をＣＡＭ１９に与え、符号化前データ格納領域ＲＧ２内に比較レジスタＲＣ内の比較データＤＣと同一値をとる格納データＤＳが複数存在する場合、当該格納データを符号化後データＤ１に置き換える書き換え処理を実行させる。
【０１０６】
セレクタ１７ａ，１７ｂは制御信号Ｓ２５に基づき、一方は一致信号及びアドレス生成回路１６からの一致信号Ｓ１１ａ及び一致アドレス信号Ｓ１１ｂに基づく符号化処理用に機能し、他方は最大値検出／符号割り当てモジュール２２からの符号用アドレス信号Ｓ２２ａ及び符号用データ信号Ｓ２２ｂに基づく符号化テーブル更新処理用に機能する。
【０１０７】
図９は実施の形態２の符号化装置における符号化処理及び符号化テーブル作成処理を示すフローチャートである。以下、同図を参照して、実施の形態２の動作について詳述する。なお、説明の都合上、現在の使用対象符号化テーブルを符号化テーブル１３ａ、更新用符号化テーブルを符号化テーブル１３ｂと仮定する。なお、図９で述べる処理は、全体的な制御は制御回路２５によって行われ、個々の動作は符号化処理部５、テーブル作成部６、出力処理部３及び参照データ書き換え処理部４によってそれぞれ実行される。また、図９において、各構成部３〜６の実行として便宜上分類していているが、実際には他の構成部が行う場合もある。
【０１０８】
図９のステップＳＴ２１において、符号化前データＤ０を順次取り込み、符号化前データ格納領域ＲＧ２内にアドレスに対応させて格納データＤＳ１〜ＤＳｍを格納するするデータセット処理を行う。
【０１０９】
次に、ステップＳＴ２２において、セレクタ１７ａ，１７ｂは、最大値検出／符号割り当てモジュール２２からの制御信号Ｓ２２ｃ及び制御回路２５からの制御信号Ｓ２５を介して、「圧縮効率≦しきい値」である（YES）か否か（NO）を認識し、ＹＥＳの場合はステップＳＴ２３に移行し、ＮＯの場合はステップＳＴ３２で符号化テーブルの交換処理（使用対象の符号化テーブルが符号化テーブル１３ａを符号化テーブル１３ｂに変更する処理）を行った後、ステップＳＴ２３に移行する。
【０１１０】
そして、ステップＳＴ２３において、ＣＡＭ１９を読み出し／書き込みアドレスＡｄに基づく符号化前データ格納領域ＲＧ２からのデータ読み出しモードに設定した後、読み出し／書き込みアドレスＡｄのアドレスを初期値“０”に設定する。
【０１１１】
そして、ステップＳＴ２４において、読み出し／書き込みアドレスＡｄ（＝“０”）に対応するフラグビット格納レジスタＲ４内のビットが“１”であるか(YES)否か(NO)をチェックし、ＮＯであれば符号化後データＤ１への置き換え前と判断しステップＳＴ２５に移行し、ＹＥＳであれば符号化後データＤ１への置き換え後と判断しステップＳＴ２７に移行する。
【０１１２】
ステップＳＴ２５において、ＣＡＭ１９内で読み出し／書き込みアドレスＡｄで指定された符号化前データ格納領域ＲＧ２内の格納データＤＳを比較レジスタＲＣの比較データＤＣとして読み出し、この比較データＤＣと参照データ格納領域ＲＧ１の参照データＤＲ１〜ＤＲｎとの一致検索を行う。
【０１１３】
一致検索において、参照データ格納領域ＲＧ１内の参照データのいずれかと比較データＤＣとは必ず一致し、一致した参照データ（一致参照データＤＲｉ（ｉ＝１〜ｎのいずれか））に対応する検索結果格納レジスタＲ１の一致検索結果ビットＤＢｉが“１”（セット状態）に設定される。図８では比較データＤＣである“０００…００１”に対応する検索結果格納レジスタＲ１内の検索結果ビット（ＤＢ）が“１”に設定されている。
【０１１４】
同時に、符号化前データ格納領域ＲＧ２内に“０００…００１”が少なくとも一つ存在し、“０００…００１”に対応する検索結果格納レジスタＲ２内の格納データＤＳに対応する検索結果ビットＣＤが全て“１”（セット状態）に設定される。図８の例では、符号化前データ格納領域ＲＧ２内に格納データＤＳして“０００…００１”を示す同一データが２つ格納され、検索結果格納レジスタＲ２が２箇所で“１”にセットされている例を示している。
【０１１５】
その後、ステップＳＴ２６において、実施の形態１のステップＳＴ４と同様に、符号化テーブル１３ａへの一致信号アドレスへの送信処理を行う。
【０１１６】
その後、ステップＳＴ３１において、符号化テーブル１３ａを参照して、選択アドレス信号ＳＡａで指示されたアドレスに格納された符号データが読み出しデータＤ１３ａとしてセレクタ２０に出力され、セレクタ２０は制御回路２５からの制御信号Ｓ３２に従い、読み出しデータＤ１３ａを符号化後データＤ１として出力する。そして、最終的に出力処理部３から出力データＤ３が出力される。
【０１１７】
また、ステップＳＴ２６後のステップＳＴ３０において、出力処理部３によるステップＳＴ３１の処理と並行してフィードバック回路４１として機能する制御回路２５及び信号線５０による書き換え処理が実行される。
【０１１８】
すなわち、制御回路２５はＣＡＭ１９に書き換え制御信号Ｓ４１を与えることにより、信号線５０を介してＣＡＭ１９に符号化後データＤ１を与え、符号化前データ格納領域ＲＧ２内において符号処理選択アドレス以外に“０００…００１”を格納している格納データＤＳ（比較データＤＣと一致するデータ）が存在する場合、符号化後データＤ１に書き換える書き換え処理を実行させ、対応する参照データ書き換え処理部４のフラグビットを“１”（セット状態）に設定する。
【０１１９】
以下、図８を例にして具体例を説明する、読み出し／書き込みアドレスＡｄで規定される符号処理選択アドレスがアドレスＡＤｐがある場合に、他のアドレスＡＤｑも“０００…００１”を格納している（検索結果格納レジスタＲ２内の検索結果ビットＣＤにより認識可能）ため、符号化後データＤ１に書き換え、当該アドレスＡＤｐ及びアドレスＡＤｑに対応するフラグビット格納レジスタＲ４のビットを“１”に設定する。
【０１２０】
ステップＳＴ２４でＹＥＳと判定された場合に実行されるステップＳＴ２７において、符号処理選択アドレスは符号化後データＤ１への書き換え処理（前述したステップＳＴ３０の処理）が既になされているため、符号化前データ格納領域ＲＧ２内における符号処理選択アドレスに対応する格納データＤＳをそのままレジスタ２６に読み出し、レジスタ２６に格納されたレジスタ格納符号化後データＤ２６をセレクタ２０を介して符号化後データＤ１として読み出す。
【０１２１】
この際、図８では図示しないが、レジスタ２６からレジスタ格納符号化後データＤ２６を出力した旨の情報が制御回路２５に与えられることにより、制御回路２５によってセレクタ２０はレジスタ格納符号化後データＤ２６を符号化後データＤ１として出力する。
【０１２２】
その後、ステップＳＴ２８において符号処理選択アドレスが最終アドレス（ｍ−１）に到達したか(YES)否か(NO)をチェックし、ＹＥＳであれば、制御回路２５からリセット信号Ｓ２６を与えることにより、フラグビット格納レジスタＲ４の全フラグを“０”にリセットした後、ステップＳＴ２１に戻る。
【０１２３】
ステップＳＴ２８においてＮＯであれば、ステップＳＴ２９で符号処理選択アドレスを１インクリメントした後、ステップＳＴ２４に戻る。
【０１２４】
一方、テーブル作成部６の生起確率算出回路２４は、符号化処理部５によるステップＳＴ２５の一致検索処理に並行して、ステップＳＴ３３において、ステップＳＴ２５の比較データＤＣと同一値をとる符号化前データ格納領域ＲＧ２内の格納データＤＳの数（一致データ数）をカウントしてカウント値（生起確率算出結果）を最大値検出／符号割り当てモジュール２２に出力する。
【０１２５】
そして、ステップＳＴ３４において、最大値検出／符号割り当てモジュール２２は、生起確率算出回路２４からのカウント値と一致信号及びアドレス生成回路１６からの一致アドレス信号Ｓ１１ｂとに基づき、一致信号アドレス（に規定される符号化前データ）に対応するカウント数を認識する。このように、最大値検出／符号割り当てモジュール２２は、生起確率算出回路２４からのカウント結果と一致アドレス信号Ｓ１１ｂとに基づき、参照データ格納領域ＲＧ１のアドレスに対応するカウント数を順次認識することができる。
【０１２６】
そして、ステップＳＴ３５で、参照データ格納領域ＲＧ１内の各アドレスに対応するカウント値のいずれかが設定値（設定値データＤ２２で規定）に達するか(YES)否か(NO)、ステップＳＴ３６で参照データ格納領域ＲＧ１のアドレスに対応するカウント値のいずれかカウント可能な最大値(MAX)に達するか(YES)否か(NO)、ステップＳＴ３７で圧縮効率がしきい値（閾値データＤ２１で規定）を下回っているか(YES)否か(NO)がチェックされる。
【０１２７】
そして、ステップＳＴ３５，あるいはＳＴ３６でＹＥＳ、又はステップＳＴ３７でＮＯと判定されると、ステップＳＴ３８の処理に移行する。
【０１２８】
ステップＳＴ３８において、最大値検出／符号割り当てモジュール２２は、生起確率算出回路２４より得られる生起確率算出結果（カウント値）に基づき、カウント値の大きいカウンタＣＴに対応するアドレスから順にハフマン符号を割り当てることにより、更新用符号化テーブル用のハフマン符号による符号化テーブルを新たに作成する。
【０１２９】
そして、ステップＳＴ３９に移行し、ステップＳＴ３８で作成された新規符号化テーブルに基づき、アドレスを規定する符号用アドレス信号Ｓ２２ａと、アドレスに対応する符号データを規定する符号用データ信号Ｓ２２ｂとをセレクタ１７ａ，１７ｂに出力することにより、符号化テーブル更新処理を実行する。
【０１３０】
現在の更新用符号化テーブルは符号化テーブル１３ｂであるため、セレクタ１７ｂは活性状態を指示するイネーブル信号ＥＮｂ、書き込みを指示する書き込み信号ＷＲｂにするとともに、符号用アドレス信号Ｓ２２ａにより規定されたアドレスを指示する選択アドレス信号ＳＡｂ、及び符号用データ信号Ｓ２２ｂにより規定された符号データを指示する符号データＤＨｂを、符号化テーブル１３ｂに順次出力することにより、符号化テーブル１３ｂの内容を更新する。
【０１３１】
その後、ステップＳＴ３２に移行し、ステップＳＴ３８の実行原因がステップＳＴ３７がＮＯの場合（圧縮効率がしきい値を下回っていた場合）、使用対象の符号化テーブルを符号化テーブル１３ａから符号化テーブル１３ｂに切り換える。なお、ステップＳＴ３９後にステップＳＴ３２が実行される場合は、ステップＳＴ３２で終了し、ステップＳＴ２３に移行することはない。ステップＳＴ２３に移行するのはステップＳＴ２２でＮＯと判断され後にステップＳＴ３２が実行された場合のみである。
【０１３２】
このように、実施の形態２の符号化装置においては、ＣＡＭ１９内に一旦格納される符号化前データＤ０に対し、リアルタイムに符号化処理部５によって符号化を行いながら，圧縮効率を維持するために，常に最適な符号化テーブルをテーブル作成部６によって用意することが可能となる。
【０１３３】
その結果、静的ハフマン符号化や適応型ハフマン符号化の問題点を解決し、ハフマン符号化処理の高速化を達成するとともに、高い圧縮効率を維持することのできるハフマン符号化に適した符号化装置を得ることができる。
【０１３４】
さらに、参照データ書き換え処理部４によって、既に符号化後データＤ１に符号化された符号化前データＤ０と同一値のデータが符号化前データ格納領域ＲＧ２に複数存在する場合に、符号化前データ格納領域ＲＧ２内の符号化前データＤ０を符号化後データＤ１に書き換えることにより、符号化処理部５による符号化処理を不要にできる分、より高速な符号処理が実現可能となる。
【０１３５】
（生起確率算出回路の詳細）
（第１の態様）
図１０は生起確率算出回路２４の第１の態様を示す回路図である。同図に示すように、生起確率算出回路２４は、クロックＣＬＫを共通に入力し、制御回路２５からのリセット信号Ｓ２６を共通にリセット入力に受ける、ｍ段の直列接続のフリップフロップＦＦ１〜ＦＦｍより構成される。
【０１３６】
フリップフロップＦＦ１〜ＦＦｍは、符号化処理情報Ｓ１ｂとして検索結果格納レジスタＲ２内の検出結果ビットＣＤ１〜ＣＤｍを入力し、外部より受けるクロックＣＬＫの入力により取り込んだビットデータを次段のフリップフロップに出力し、フリップフロップＦＦｍの出力がカウンタ２７に与えられる。
【０１３７】
したがって、ｍ回分のクロックＣＬＫをフリップフロップＦＦ１〜ＦＦｍに与え、フリップフロップＦＦｍの出力データに現れる“１”をカウンタ２７がカウントすることにより、フリップフロップＦＦ１〜ＦＦｍに取り込まれた検出結果ビットＣＤ１〜ＣＤｍにおける“１”（セット状態）の個数をカウントすることができる。
【０１３８】
このように、生起確率算出回路２４の第１の態様は、一致信号アドレスに対応する参照データＤＲに一致する格納データＤＳが符号化前データ格納領域ＲＧ２内に幾つ存在するかを示す一致データ数をカウント値として得ることができるため、最新の符号化前データＤ０の出現情報を正確かつ高速に認識可能な生起確率算出処理を行うことができる。
【０１３９】
このカウンタ２７によりカウント値が最大値検出／符号割り当てモジュール２２に与えられる。図１０で示す第１の態様は、１単位のシフトレジスタを構成するフリップフロップＦＦ１〜ＦＦｍとカウンタ２７のみで実現できるため、実装が単純という利点があり，リソースの消費をできるだけ抑え削減する場合や，より小さい実装を目指す場合に有効である。
【０１４０】
（第２の態様）
図１１は生起確率算出回路２４の第２の態様を示す回路図である。同図に示すように、ｋ個のシフトレジスタＳＲ１〜ＳＲｋを設けている。シフトレジスタＳＲ１〜ＳＲｋはそれぞれ図１０で示すフリップフロップＦＦ１〜ＦＦｍと等価な回路で構成され、シフトレジスタＳＲ１〜ＳＲｋはそれぞれ符号化処理情報Ｓ１ｂを受ける。
【０１４１】
シフトレジスタＳＲ１〜ＳＲｋの出力を選択的カウント部であるサブカウンタＳＣＴ１〜ＳＣＴｋが受け、サブカウンタＳＣＴ１〜ＳＣＴｋの出力をセレクタ２８を受け、セレクタ２８の出力が最大値検出／符号割り当てモジュール２２に付与される。
【０１４２】
シフトレジスタＳＲ１〜ＳＲｋは制御回路２５の制御信号Ｓ２０ａによって動作（格納動作、シフト動作）制御され、セレクタ２８は制御信号Ｓ２０ｂによってサブカウンタＳＣＴ１〜ＳＣＴｋのうち、選択すべきサブカウンタＳＣＴの内容が制御される。制御信号Ｓ２０ａ及び２０ｂは図８の制御信号Ｓ２０に相当する。
【０１４３】
このような構成において、第２の態様は、シフトレジスタＳＲ１〜ＳＲｋに対しパイプライン処理を実行させ、符号化処理情報Ｓ１ｂを入力する一のシフトレジスタＳＲと、シフト動作を行う他のシフトレジスタＳＲとをそれぞれ独立に動作させる。例えば、シフトレジスタＳＲ１，ＳＲ３〜ＳＲｋがカウント処理（シフト動作）を行っているときに、シフトレジスタＳＲ２に符号化処理情報Ｓ１ｂを取り込ませる。そして、シフトレジスタＳＲ２についてカウント処理動作を始めると、他のカウント処理が終了しているシフトレジスタＳＲに符号化処理情報Ｓ１ｂを取り込ませる。
【０１４４】
そして、サブカウンタＳＣＴ１〜ＳＣＴｋのうち、対応するシフトレジスタＳＲからのカウント処理が終了したサブカウンタＳＣＴを、セレクタ２８により選択させ、カウント処理が終了したサブカウンタＳＣＴのカウント値が順次最大値検出／符号割り当てモジュール２２に与えられる。
【０１４５】
この様に，シフトレジスタＳＲ１〜ＳＲｋ間において、符号化処理情報Ｓ１ｂの格納とカウント処理とを重複することなくパインラインカウンティング処理を実行させることにより、第１の態様に比べ処理時間を短縮することができる。
【０１４６】
（第３の態様）
図１２は生起確率算出回路２４の第３の態様を示す回路図である。同図に示すように部分シフトレジスタＳＳＲ１〜ＳＳＲｊ（２≦ｊ＜ｍ）及び並列カウント部である部分カウンタＰＣＴ１〜ＰＣＴｊにより構成され、部分シフトレジスタＳＳＲ１〜ＳＳＲｊは符号化処理情報Ｓ１ｂがｊ分割されたビット検出結果群ＣＤＧ１〜ＣＤＧｊを受ける。部分カウンタＰＣＴ１〜ＰＣＴｊは部分シフトレジスタＳＳＲ１〜ＳＳＲｊの出力側に設けられる。
【０１４７】
ＡＬＵ２９は部分カウンタＰＣＴ１〜ＰＣＴｊの出力を受け、その合計値をカウント値として最大値検出／符号割り当てモジュール２２に付与する。
【０１４８】
第３の態様では、部分シフトレジスタＳＳＲ１〜ＳＳＲｊ及び部分カウンタＰＣＴ１〜ＰＣＴｊがそれぞれカウントすべきビット数は（ｍ／ｊ）であり、それぞれ並列動作可能である。したがって、第３の態様では、第１の態様のフリップフロップＦＦ１〜ＦＦｍをｊ分割することにより、レイテンシを１／ｊに削減することができ、高速なカウントが可能となる効果を奏する。
【０１４９】
第３の態様は、符号化前データＤ０の内容によっては圧縮効率の変化が急であったり，既存の符号化テーブルとデータの傾向が合わない場合等に特に有効である。
【０１５０】
（第４の態様）
図１３は生起確率算出回路２４の第４の態様を示す回路図である。同図に示すように、検出結果ビットＣＤ１〜ＣＤｍに対応してレジスタＣＲ１〜ＣＲｍを設け、レジスタＣＲ１〜ＣＲｍにおいて隣接する２つのレジスタＣＲ間の出力を加算可能に複数の加算器群ＡＤ１からなる第１の加算器群を設ける、さらに、第１の加算器１群において隣接する２つの加算器ＡＤ１，ＡＤ１の出力を加算可能に接続した二段目の加算器ＡＤ２からなる第２の加算器群を設ける、以降同様に、ｐ段のＡＤｐ（２p≧ｍ）を設ける。なお、第１〜第ｐの加算器群を構成する加算器ＡＤ１〜ＡＤｐは段数が増えることに加算可能ビット数を１ビットずつ増やす必要がある。
【０１５１】
そして、加算器ＡＤｐの出力がカウント値として最大値検出／符号割り当てモジュール２２に付与される。なお、レジスタＣＲ１〜ＣＲｍ及び加算器（群）ＡＤ１〜ＡＤｐは制御回路２５のリセット信号Ｓ２６よって適宜リセット制御される。
【０１５２】
このように、加算器ＡＤ１〜ＡＤｐからなる第１〜第ｐの加算器群をツリー上に配置した組み合わせ回路を用いて、符号化処理情報Ｓ１ｂ（検出結果ビットＣＤ１〜ＣＤｍ）に基づくカウント値を得ることができる。また、第１〜第ｐの加算器群の各段の間にレジスタを挿入することにより、パイプライン処理を行いスループットを向上することも可能である。
【０１５３】
（第５の態様）
図１４及び図１５は生起確率算出回路２４の第５の態様を示す説明図及びブロック図である。第５の態様では、図１４で示すように取り込まれた符号化前データ格納領域ＲＧ２内の格納データを、図１５に示すように、降順にソーティングした後に、カウント値を求めている。なお、ＣＡＭ１９による最大値検索は，マスクを用いて格納データの一番左のビット (MSB: Most Significant Bit)から比較を始めて，右へ順々に検索データを“１”にして検索していくことにより行えるため、降順のソーティングを比較的容易に実現することができる。
【０１５４】
図１５に示すよう符号化前データ格納領域ＲＧ２内をソーティングすると、一致検索時において、検索結果格納レジスタＲ２内のデータは、検索結果格納レジスタＲ２内において比較データＤＣと同一データに関しては“１”が連続してアドレス順に配置されることとなる。
【０１５５】
最大及び最小一致アドレス生成回路３０は検索結果格納レジスタＲ２内において“１”を示すビット検出結果ＣＤに対応する最大アドレスをスイッチ３８を介してレジスタ３９に出力し、“１”を示すビット検出結果ＣＤに対応する最小アドレスをスイッチ３８を介して減算器４０に出力する。減算器４０は、最大アドレスと最小アドレスとの差分値に基づき、“１”を示すビット検出結果ＣＤの個数であるカウント値を求め、最大値検出／符号割り当てモジュール２２に出力する。
【０１５６】
このように、第５の態様は、カウント部を構成する一致信号及びアドレス生成回路３０、スイッチ３８、レジスタ３９及び減算器４０によって、データ比較時における“１”が設定された検出結果ビットＣＤ１〜ＣＤｍの最大／最小アドレスに基づき、検出結果ビットＣＤ１〜ＣＤｍの“１”（セット状態）数を迅速にカウントすることができる。
【０１５７】
なお、検索結果格納レジスタＲ２、最大及び最小一致アドレス生成回路３０、スイッチ３８、レジスタ３９、及び減算器４０は制御回路２５からの制御信号Ｓ２０によって動作制御される。
【０１５８】
第５の態様は符号化前データの順番に依存しないアプリケーションに有効である。なお、図１５では図８のセレクタ１７ａ，１７ｂ及び符号化テーブル１３ａ，１３ｂを簡略化してセレクタ及び符号化テーブル３４として示している。
【０１５９】
（第６の態様）
図１６は生起確率算出回路２４の第６の態様を示す回路図である。同図に示すように、検索結果格納レジスタＲ２の検出結果ビットＣＤ１〜ＣＤｍが全て取り込み可能なソーティング回路４２を設け、ソーティング回路４２は検出結果ビットＣＤ１〜ＣＤｍを取り込んだ後、内部で“１”が上位、“０”が下位になるようにソーティングする。すなわち、ソーティング回路４２は、“１”の有無に基づき分類するビットソーティング処理を実行する。
【０１６０】
そして、ソーティング回路４２の格納ビット群のうち、隣接するビット間を入力する（ｍ−１）個のＥＸＯＲゲートＧ４３からなるＥＸＯＲゲート群４３を設け、ＥＸＯＲゲート群４３の出力をアドレス生成回路４４が入力する。
【０１６１】
アドレス生成回路４４は（ｍ−１）個のＥＸＯＲゲートＧ４３の出力を受け、“１”を示すＥＸＯＲゲートＧ４３の出力に対応するアドレスに基づき、カウント値を得て最大値検出／符号割り当てモジュール２２に出力する。すなわち、ＥＸＯＲゲート群４３及びアドレス生成回路４４がカウント部して機能する。
【０１６２】
図１６の例では、ＥＸＯＲゲート群４３における上から３段目のＥＸＯＲゲートＧ４３の出力のみ“１”となるため、アドレス生成回路４４は上記３段目のＥＸＯＲゲートＧ４３を認識することにより、カウント値を最大値検出／符号割り当てモジュール２２に出力することができる。
【０１６３】
なお、検索結果格納レジスタＲ２、ソーティング回路４２、及びアドレス生成回路４４は、制御回路２５の制御信号Ｓ２０によって動作制御される。
【０１６４】
第６の態様は、ソーティング回路４２におけるソーティング後のビットに基づく、ＥＸＯＲゲート群４３及びアドレス生成回路４４によってカウント値を算出することにより、検出結果ビットＣＤ１〜ＣＤｍの“１”の個数を迅速にカウントすることができる。
【０１６５】
このような構成の第６の態様は、高速にカウント値を得ることが可能である。なお、図１６では図８のセレクタ１７ａ，１７ｂ及び符号化テーブル１３ａ，１３ｂを簡略化してセレクタ及び符号化テーブル３４として示している。
【０１６６】
（第７の態様）
通常、ＣＡＭは，複数ビットが一致状態（“１”）を示す検索結果ビット群の中から１つのデータを選択・出力するプライオリティエンコーダを備えている。第７の態様のプライオリティエンコーダ方式はＣＡＭのプライオリティエンコーダを用いることにより、検索結果格納レジスタＲ２内で“１”を示すビット検出結果ＣＤをカウントする方法を用いている。
【０１６７】
図１７は生起確率算出回路２４の第７の態様を示すブロック図である。同図に示すように、検索結果格納レジスタＲ２の検出結果ビットＣＤ１〜ＣＤｍをプライオリティエンコーダ４５が受け、検出結果ビットＣＤ１〜ＣＤｍが複数の“１”を示す場合に最小アドレスの“１”のみを有効したビット群を検索結果格納レジスタＲ５に出力する。このように、プライオリティエンコーダ４５及び検索結果格納レジスタＲ５によってプライオリティエンコーダ部を構成する。
【０１６８】
検索結果格納レジスタＲ５の内容はリセット回路４７によってフィードバックされ、検索結果格納レジスタＲ５内で“１”を格納するビット位置に対応する検索結果格納レジスタＲ２内のビットを“１”から“０”にリセットする。
【０１６９】
一方、多入力ＯＲゲート４６は検索結果格納レジスタＲ５の全格納ビットを入力し、その出力をカウンタ４８に出力する。カウンタ４８は多入力ＯＲゲート４６の出力のから“１”が出力される回数をカウントし、そのカウント結果をカウント値として最大値検出／符号割り当てモジュール２２に出力する。このように、多入力ＯＲゲート４６及びカウンタ４８によってカウント部を構成する。なお、検索結果格納レジスタＲ２及びカウンタ４８はリセット信号Ｓ２６によってリセット制御される。
【０１７０】
このような構成において、多入力ＯＲゲート４６から“１”が出力され、カウンタ４８によりカウントされると同時に，リセット回路４７からのリセット信号Ｓ４７によって検索結果格納レジスタＲ２内の一の“１”が“０”にリセットされる。上記の一連の処理を１サイクルとして実施すると、検索結果格納レジスタＲ２内の検出結果ビットＣＤ１〜ＣＤｍの“１”の数に相当する回数分、多入力ＯＲゲート４６から“１”が出力されることになるため、カウンタ４８は検出結果ビットＣＤ１〜ＣＤｍにおける“１”の個数を正確にカウントすることができる。
【０１７１】
第７の態様は既存のＣＡＭマクロに検索結果格納レジスタＲ５、多入力ＯＲゲート４６、リセット回路４７及びカウンタ４８に相当するカウンタ機能を追加することにより実現することが可能であるため，適用範囲が広く，新たに付加する回路を少なく抑えることができる利点を奏する。
【０１７２】
第７の態様は、サイクル数が検索結果格納レジスタＲ２内の“１”を示すビット数分必要となるが，符号化処理と並行して作業するには充分高速なレイテンシであると考えられる。なお、図１７では図８のセレクタ１７ａ，１７ｂ及び符号化テーブル１３ａ，１３ｂを簡略化してセレクタ及び符号化テーブル３４として示している。
【０１７３】
＜その他＞
上記した実施の形態１及び実施の形態２の符号化装置は、様々なアプリケーションに対する柔軟な適応，リアルタイム処理，及び圧縮効率の維持を改善したアーキテクチャとなっている。
【０１７４】
このアーキテクチャはハイビジョン等の超高精細画像の静止画像符号化や，ブロードバンドの普及に伴う音声・動画等のマルチメディアデータ圧縮，及びデジタル通信回線を利用したテレビ電話・テレビ会議システム等のリアルタイムオンラインシステムやＣＤ，ＤＶＤ及びデジタルカメラ装置等の単体で使用されるシステムのハフマン符号化を高速・高効率に行える符号化装置として有効に機能するものと考えられる。
【図面の簡単な説明】
【０１７５】
【図１】この発明に発明に係るＣＡＭベースのハフマン符号化アーキテクチャを有する符号化装置の内部構成の概略を示すブロック図である。
【図２】実施の形態１の符号化装置の全体構成の示す説明図である。
【図３】実施の形態１の符号化装置の詳細構成を示す説明図である。
【図４】実施の形態１の符号化装置における符号化処理及び符号化テーブル作成処理を示すフローチャートである。
【図５】図４で示した符号化データ読み出しステップにおけるＣＡＭ１１とＲＡＭ１３との関係を示す概念図である。
【図６】ＣＡＭとＲＡＭとの接続例を示す説明図である。
【図７】実施の形態２の符号化装置の全体構成の示す説明図である。
【図８】実施の形態２の符号化装置の詳細構成を示す説明図である。
【図９】実施の形態２の符号化装置における符号化処理及び符号化テーブル作成処理を示すフローチャートである。
【図１０】実施の形態２の生起確率算出回路の第１の態様を示す回路図である。
【図１１】実施の形態２の生起確率算出回路の第２の態様を示す回路図である。
【図１２】実施の形態２の生起確率算出回路の第３の態様を示す回路図である。
【図１３】実施の形態２の生起確率算出回路の第４の態様を示すブロック図である。
【図１４】実施の形態２の生起確率算出回路の第５の態様の説明用の説明図である。
【図１５】実施の形態２の生起確率算出回路の第５の態様を示すフロック図である。
【図１６】実施の形態２の生起確率算出回路の第６の態様を示すブロック図である。
【図１７】実施の形態２の生起確率算出回路の第７の態様を示すブロック図である。
【図１８】ＣＡＭの概念を示す説明図である。
【符号の説明】
【０１７６】
１，５  符号化処理部、２，６  テーブル作成部、３  出力処理部、４  参照データ書き換え処理部、１１，１９  ＣＡＭ、１３ａ，１３ｂ  符号化テーブル、１７  スイッチ、２１，２４  生起確率算出回路、２２  最大値検出／符号割り当てモジュール、２３，２５  制御回路、４１  フィードバック回路。
【図１】
2006324944.tif 000003
【図２】
2006324944.tif 000004
【図３】
2006324944.tif 000005
【図４】
2006324944.tif 000006
【図５】
2006324944.tif 000007
【図６】
2006324944.tif 000008
【図７】
2006324944.tif 000009
【図８】
2006324944.tif 000010
【図９】
2006324944.tif 000011
【図１０】
2006324944.tif 000012
【図１１】
2006324944.tif 000013
【図１２】
2006324944.tif 000014
【図１３】
2006324944.tif 000015
【図１４】
2006324944.tif 000016
【図１５】
2006324944.tif 000017
【図１６】
2006324944.tif 000018
【図１７】
2006324944.tif 000019
【図１８】
2006324944.tif 000020