(57)【要約】      （修正有）【課題】ハフマン木生成の高速化を図る。【解決手段】複数のソート部４(1)〜４(n)が、パッケージ結合によって生じた新たな出現頻度とを比較する比較処理を互いに並行して行う。そして、自己の比較結果に応じて、記憶部２間で出現頻度をシフトすることで、出現頻度列Ｄinを値の大きさ順に並び替える。【効果】パッケージ結合の構成が論理的に維持されるので、正しいハフマン木生成が得られるのを保証できる。新たな出現頻度の比較や、この新たな出現頻度の出現頻度列への挿入を、各ソート部で同時並行的に行われているので、ハードウェア化により、処理の高速化を図ることが可能になる。【選択図】図１
2007243880.tif 000002
【特許請求の範囲】
【請求項１】
一対の出現頻度を入力としたパッケージ結合を繰り返すことによって、出現頻度のハフマン木を生成するハフマン木生成回路において、
複数段に直列接続され、それぞれが、値の大きさ順に並んだ出現頻度列における個々の出現頻度を格納する複数の記憶部と、
パッケージ結合に際して、値が最も小さい側にある一対の前記記憶部から読み出された一対の出現頻度を加算し、当該加算結果をパッケージ結合によって生じた新たな出現頻度として出力する加算部と、
前記一対の記憶部を除く前記記憶部のそれぞれから読み出された出現頻度と、前記加算部より出力された前記新たな出現頻度とを比較する比較処理を互いに並行して行い、それぞれが、自己の比較結果に応じて、前記記憶部間で出現頻度をシフトして格納することによって、前記新たな出現頻度が挿入された出現頻度列を値の大きさ順に並び替える複数のソート部と
を有することを特徴とするハフマン木生成回路。
【請求項２】
前記加算部が読み出す一対の前記記憶部は、前記複数の記憶部のうち、不変に設定されることを特徴とする請求項１に記載されたハフマン木生成回路。
【請求項３】
前記複数のソート部は、複数段に直列接続され、
それぞれが、
前記記憶部から読み出された出現頻度と、前記加算部より出力された前記新たな出現頻度とを比較する判定部と、
当該判定部の比較結果に応じて、隣接したソート部に出力する出現頻度を選択する第１のスイッチと、
隣接したソート部の判定部の比較結果に応じて、前記記憶部に格納する出現頻度を選択する第２のスイッチと
を有することを特徴とする請求項１または２に記載されたハフマン木生成回路。    
【請求項４】
前記加算部が読み出す一対の前記記憶部は、前記複数の記憶部のうち、サイクル毎に可変に設定されることを特徴とする請求項１に記載されたハフマン木生成回路。
【請求項５】
前記複数のソート部は、複数段に直列接続され、
それぞれが、
前記記憶部から読み出された出現頻度と、前記加算部より出力された前記新たな出現頻度とを比較する判定部と、
当該判定部の比較結果に応じて、隣接したソート部に出力する出現頻度を選択する第１のスイッチと、
当該判定部の比較結果に応じて、前記記憶部に格納する出現頻度を選択する第２のスイッチと
を有することを特徴とする請求項１または４に記載されたハフマン木生成回路。    
【請求項６】
前記ハフマン木生成回路は、
前記複数の記憶部の同期制御を行う制御部をさらに有することを特徴とする請求項１から５のいずれかに記載されたハフマン木生成回路。
【請求項７】
前記制御部は、前記出力信号の回数をカウントし、当該カウントされた回数が所定の回数に到達した場合、パッケージ結合の繰り返しを終了することを特徴とする請求項６に記載されたハフマン木生成回路。
【請求項８】
前記所定の回数は、少なくとも前記出現頻度列を構成する出現頻度の個数に基づいて、予め設定されていることを特徴とする請求項６または７に記載されたハフマン木生成回路。
【請求項９】
請求項１から８のいずれかに記載されたハフマン木生成回路と、
前記ハフマン木生成回路によって出現頻度の大きさ順に並び替えられた前記出現頻度列に基づいて、前記出現頻度のそれぞれに対応する符号データを生成する符号生成回路と
を有することを特徴とするハフマンテーブル生成システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一対の出現頻度を入力としたパッケージ結合を繰り返すことによって、出現頻度のハフマン木を生成する技術に関する。
【背景技術】
【０００２】
ハフマン符号化は、シンボル（パターン）の出現頻度に着目し、出現頻度がより高いシンボルに対してより短い符号を与えることによって、データ圧縮を行う代表的なアルゴリズムである。この符号化のために用いられるハフマン木の生成に際しては、値が最も小さな一対の出現頻度を入力としたパッケージ結合が繰り返し実行される。そのため、現在の出現頻度グループの中から最小の２つの出現頻度を検索・抽出するという演算量が大きな処理を、パッケージ結合を行う度（サイクル毎）に実行しなければならない。そこで、演算負荷の軽減を図るべく、非特許文献１および非特許文献２には、出現頻度があらかじめ昇順または降順にソートされているという条件下において、各サイクルでのサーチ処理を最小限に留め、ハフマン木生成の高速化を図る手法が提案されている。具体的には、パッケージ結合前の出現頻度（ハフマン木の葉）の配列とは別に、パッケージ結合後の出現頻度（ハフマン木の節）の配列を設ける。各サイクルにおいて、最小の出現頻度となるパッケージのノードは、結合前または結合後のパッケージ配列のいずれかの先頭の値であるため、全体検索を必要とせず、１回または２回の比較処理と１回の加算処理だけで、パッケージ結合が完了する。
【０００３】
【非特許文献１】A. Moffat and J. Katajainen,          "In-place calculation of minimum-redundancy codes,"          Proc. Workshop on Algorithms and Data Structures,          pp.393-402, 1995.
【非特許文献２】A. Moffat and J. Katajainen,          "Conmpression and coding algorithms"          Kluwer Academic Publishers,          2002.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
非特許文献１，２の手法は、演算量が少なく、メモリの使用量も少ないというメリットがある反面、特にハードウェア化した際に高速化を図る余地があまりない。
【０００５】
そこで、本発明の目的は、処理速度の一層の向上を図ることが可能なハフマン木生成回路を提供することである。
【課題を解決するための手段】
【０００６】
かかる課題を解決するために、第１の発明は、一対の出現頻度を入力としたパッケージ結合を繰り返すことによって、出現頻度のハフマン木を生成するハフマン木生成回路を提供する。このハフマン木生成回路は、複数の記憶部と、加算部と、複数のソート部とを有する。複数の記憶部は、複数段に直列接続され、値の大きさ順に並んだ出現頻度列を格納する。加算部は、パッケージ結合に際して、値が最も小さい側にある一対の記憶部から読み出された一対の出現頻度を加算し、加算結果をパッケージ結合によって生じた新たな出現頻度として出力する。複数のソート部は、一対の記憶部を除く記憶部のそれぞれから読み出された出現頻度と、加算部より出力された新たな出現頻度とを比較する比較処理を互いに並行して行う。そして、複数のソート部のそれぞれは、自己の比較結果に応じて、記憶部間で出現頻度をシフトして格納することによって、新たな出現頻度が挿入された出現頻度列を値の大きさ順に並び替える。
【０００７】
ここで、第１の発明において、加算部が読み出す一対の記憶部は、複数の記憶部のうち、不変に設定されることが好ましい。このとき、複数のソート部は、複数段に直列接続されており、それぞれが、判定部と、第１のスイッチと、第２のスイッチを有することが好ましい。判定部は、記憶部から読み出された出現頻度と、加算部より出力された新たな出現頻度とを比較する。第１のスイッチは、この判定部の比較結果に応じて、隣接したソート部に出力する出現頻度を選択する。第２のスイッチは、隣接したソート部の判定部の比較結果に応じて、記憶部に格納する出現頻度を選択する。
【０００８】
また、第１の発明において、加算部が読み出す一対の記憶部は、複数の記憶部のうち、サイクル毎に可変に設定されることが好ましい。このとき、複数のソート部は、複数段に直列接続され、それぞれが、判定部と、第１のスイッチと、第２のスイッチとを有することが好ましい。判定部は、記憶部から読み出された出現頻度と、加算部より出力された新たな出現頻度とを比較する。第１のスイッチは、この判定部の比較結果に応じて、隣接したソート部に出力する出現頻度を選択する。第２のスイッチは、この判定部の比較結果に応じて、記憶部に格納する出現頻度を選択する。
【０００９】
さらに、第１の発明のハフマン木生成回路は、複数の記憶部の同期制御を行う制御部をさらに有することが好ましい。また、制御部は、出力信号の回数をカウントし、カウントされた回数が所定の回数に到達した場合、パッケージ結合の繰り返しを終了することが好ましい。このとき、所定の回数は、少なくとも出現頻度列を構成する出現頻度の個数に基づいて、予め設定されていることが好ましい。
【００１０】
第２の発明は、上述したような構成を有する第１の発明にかかるハフマン木生成回路と、このハフマン木生成回路によって出現頻度の大きさ順に並び替えられた前記出現頻度列に基づいて、前記出現頻度のそれぞれに対応する符号データを生成する符号生成回路とを有するハフマンテーブル生成システムを提供する。
【発明の効果】
【００１１】
第１の発明によれば、各ソート部が、パッケージ結合によって生じた新たな出現頻度とを比較する比較処理を互いに並行して行っている。そして、自己の比較結果に応じて、記憶部間で出現頻度をシフトして格納することで、出現頻度列を値の大きさ順に並び替えている。これにより、新たな出現頻度（パッケージ結合後）の配列を別個の出現頻度列として設けなくとも、パッケージ結合の構成が論理的に維持されるので、正しいハフマン木生成が得られるのを保証できる。特に、新たな出現頻度の比較や、この新たな出現頻度の出現頻度列への挿入が、同時並行的に行われているので、全体的な処理の高速化を図ることが可能になる。
【００１２】
また、第２の発明によれば、ハフマン符号化に先立って必要となるハフマン木生成が高速化されるので、全体的なハフマン符号化の高速化を図ることができる。
【発明を実施するための最良の形態】
【００１３】
（第１の実施形態）
図１は、第１の実施形態にかかるハフマン木生成回路１の全体構成図である。このハフマン木生成回路１は、複数の出現頻度で構成される出現頻度列Ｄinに基づいて、一対の出現頻度（値が最小となる２つ）を入力としたパッケージ結合を繰り返すことによってハフマン木を生成する。ハフマン木生成回路１は、複数の記憶部２(1)〜２(n)（ｎ≧３）と、加算部３と、複数のソート部４(3)〜４(n)と、入力部５と、制御部６とから構成されている。
【００１４】
複数の記憶部２(1)〜２(n)は、複数段に直列接続され、出現頻度の大きさ順に並んだ出現頻度列Ｄinを格納する。具体的には、それぞれの記憶部２（ここで、符号２は２(1)〜２(n)のいずれかを指す）には、出現頻度列Ｄinを構成する個々の出現頻度が格納される。入力部５を介して記憶部２に格納される出現頻度列Ｄinは、ハフマン木生成回路１に接続するソート回路（例えば、バブルソート回路）等によって出現頻度の大きさ順に整列されているものとする。初期状態時（入力部５による入力時）において、記憶部２(m)（１≦ｍ≦ｎ）には、出現頻度列Ｄinの中でｍ番目に小さい出現頻度が格納される。すなわち、同図において最右の記憶部２(1)には最小の出現頻度が格納され、これ以降、最左の記憶部(n)に至るまで、値が順番に大きくなるように出現頻度が格納される。
【００１５】
加算部３は、パッケージ結合に際して、出現頻度が最も小さい側にある一対の記憶部２(1)，２(2)から読み出された一対の出現頻度を加算し、この加算結果をパッケージ結合によって生じた新たな出現頻度として出力する。具体的には、加算部３は、記憶部２(1)から読み出された最も小さな値と、記憶部２(2)から読み出された２番目に小さな値とを加算して、新たな出現頻度Ｐを算出する。この新たな出現頻度Ｐは、パッケージ結合によって新たに生成されるパッケージ（ハフマン木の節）の出現頻度に相当する。
【００１６】
複数のソート部４(3)〜４(n)は、複数段に直列接続され、一対の記憶部２(1)，２(2)を除く記憶部２(3)〜２(n)から読み出された個々の出現頻度と、加算部３より出力された新たな出現頻度Ｐとを比較する比較処理を互いに並行して行う。具体的には、ソート部４（ここで、符号４は４(3)〜４(n)のいずれかを指す）が、記憶部２(1)，２(2)を除いた記憶部２から読み出された出現頻度と、加算部３より出力された新たな出現頻度Ｐとの比較を互いに平行して行う。そして、自己の比較結果に応じて、記憶部間で出現頻度をシフトさせることによって、新たな出現頻度Ｐが挿入された出現頻度列Ｄinを出現頻度の大きさ順に並び替える。並び替えられた出現頻度列Ｄinは、記憶部２(1)から昇順に格納される。なお、記憶部２(1)，２(2)には、ソート部４は接続されず、また、格納された出現頻度の大小関係は考慮されない。これは、加算部３は、出現頻度列Ｄinのうち出現頻度の少ない２つの出現頻度が、固定して設定された一対の記憶部２(1)，２(2)に格納されていることが保証されていれば、この２つの出現頻度が次のサイクルにおいて合算されるため、その大小関係を必要としないからである。なお、説明上、記憶部２(3)〜２(n)のそれぞれと、ソート部４(3)〜４(n)のそれぞれとを対応させることによって、複数のユニットＵＮ(3)〜ＵＮ(n)と定義する。また、小さい出現頻度を格納する記憶部２を有するユニットＵＮを前段とし、大きい出現頻度を格納する記憶部２を有するユニットＵＮを後段とする。
【００１７】
入力部５は、出現頻度列Ｄinの並び替えに先立ち、外部から入力されたソート処理前の出現頻度列Ｄinを記憶部２に格納する。なお、入力される出現頻度列Ｄinは、バブルソート回路（図示せず）等によって、既に昇順または降順に整列されているものを用いる。制御部６は、記憶部２の読み書きの同期制御を行う。具体的には、記憶部２に対して、出力信号ＳＮＣを出力することにより、記憶部２に格納された出現頻度を出力する。これにより、記憶部２に格納された出現頻度の更新が同時並行的に行われる。また、制御部６は、サイクルの推移をカウントアップする。具体的には、出力信号の回数をカウントし、このカウントされた回数が所定の回数に到達した場合、パッケージ結合の繰り返し処理を終了する。出現頻度列Ｄinの並び替えが完了するサイクル数は、基本的に、入力部５を介して通知された出現頻度列Ｄinを構成する出現頻度の個数ｋ（ｋ≧３）に基づいて、一義的に特定され、予め設定される。例えば、出現頻度の個数がｋの場合、ｋ−２番目のサイクルのおけるソート処理の完了を以て、一連の処理が終了したと判定される。
【００１８】
図２は、本実施形態にかかる単一のユニットＵＮの構成図である。なお、具体的には、両端のユニットＵＮ(3)，ＵＮ(n)を除くユニットＵＮ(m)の構成図である。ユニットＵＮ(m)は、記憶部２(m)とソート部４(m)とで構成し。ソート部４(m)は、判定部４ａ(m)と２つのスイッチ４ｂ(m)，４ｃ(m)とを有する。判定部４ａ(m)は、記憶部２(m)から読み出された出現頻度と、加算部３から出力された新たな出現頻度Ｐとを比較する。そして、この比較結果（出現頻度の大小）に応じて、自己のユニットＵＮ(m)のスイッチ４ｂ(m)と、１段前のユニットＵＮ(m-1)のスイッチ４ｃ(m-1)とを制御する。
【００１９】
スイッチ４ｂ(m)は、判定部４ａ(m)の比較結果に応じて、隣接した２段前のソート部４(m-2)に出力する出現頻度を選択する。スイッチ４ｂ(m)の一方の入力端子は、記憶部２(m)に接続されており、その他方の入力端子は、加算部３（新たな出現頻度Ｐ）に接続されている。そして、自己のユニットＵＮ(m)の判定部４ａ(m)による切換信号ＣＯＭ(m)の下、記憶部２(m)に格納された出現頻度と、加算部３からの新たな出現頻度Ｐとで構成される一対の出現頻度のいずれかが、出力出現頻度ＯＰ２(m)として、２段前のユニットＵＮ(m-2)（ソート部４(m+2)）に入力される。なお、スイッチ４ｂ(m)の選択に関係なく、記憶部２(m)に格納された出現頻度は、出力出現頻度ＯＰ１(m)として、１段前のユニットＵＮ(m-1)（ソート部４(m+1)）に入力される。スイッチ４ｃ(m)は、隣接した１段後のソート部４(m+1)の判定部４ａ（m+1）比較の結果に応じて、記憶部２(m)に格納される出現頻度を選択する。スイッチ４ｃ(m)の一方の入力端子は、２段後のユニットＵＮ(m+2)（ソート部４(m+2)）に接続されており、その他方の入力端子は、１段後のユニットＵＮ(m+1)（ソート部４(m+1)）に接続されている。そして、１段前のユニットＵＮ(m+1)の判定部４ａ(m+1)による切替信号ＣＯＭ(m+1)の下、２段後のユニットＵＮ(m+2)からの出力出現頻度とＯＰ２(m+2)と、１段後のユニットＵＮ(m+1)からのＯＰ１(m+1)とで構成される一対の出現頻度のいずれかが、記憶部２(m)に適宜格納される。
【００２０】
判定部４ａ(m)によって、自己のユニットＵＮ(m)のスイッチ４ｂ(m)と、１段前のユニットＵＮ(m-1)のスイッチ４ｃ(m-1)との切換状態は、記憶部２(m)，加算部３から読み出された出現頻度の大小とに応じて、下表のように設定される。なお、同表において、”ｐ”は記憶部２から読み出された出現頻度を指し、”Ｐ”は加算部３から読み出された新たな出現頻度を指す。
【００２１】
［スイッチ４ｂ(m)，スイッチ４ｃ(m-1)の状態］
判定部４ａ(m)  切替信号ＣＯＭ(m)  スイッチ４ｂ(m)  スイッチ４ｃ(m-1)
Ｐ＜ｐ            Ｈ            加算部３側      ＯＰ２(m+1)側
Ｐ＞ｐ            Ｌ            記憶部２(m)側   ＯＰ１(m)側
【００２２】
判定部４ａ(m)は、記憶部２(m)と加算部３とから読み出された出現頻度のセットｐ，Ｐの値の大小を比較し、この比較結果に応じて、スイッチ４ｂ(m)およびスイッチ４ｃ(m-1)の状態を設定する。Ｐ＜ｐの場合（ＣＯＭ(m)＝Ｈレベル）には、スイッチ４ｂ(m)が加算部３側、スイッチ４ｃ(m-1)がＯＰ２(m+1)側に設定される。これにより、出現頻度セットの一部である新たな出現頻度Ｐは、スイッチ４ｂ(m)を介して出力出現頻度ＯＰ２(m)として出力される。また、このセットの残りである出現頻度ｐは、出力出現頻度ＯＰ１(m)として出力される。さらに、１段前のユニットＵＮ(m-1)から、２段後のユニット、つまり自己のユニットＵＮ(m)から１段後のユニットＵＮ(m+1)からＯＰ２(m+1)として出力された出現頻度が、スイッチ４ｃ(m-1)を介して記憶部２(m-1)に格納される。一方、Ｐ＞ｐの場合（ＣＯＭ(m)＝Ｌレベル）には、スイッチ４ｂ(m)が記憶部２側、スイッチ４ｃ(m-1)がＯＰ１(m)側に設定される。これにより、出現頻度セットの一部である出現頻度ｐは、スイッチ４ｂ(m)を介して出力出現頻度ＯＰ２(m)として出力される。また、この出現頻度ｐは、出力出現頻度ＯＰ１(m)として出力される。さらに、自己のユニットＵＮ(m)から、ＯＰ１(m)として出力された出現頻度（出現頻度ｐ）が、スイッチ４ｃ(m-1)を介して記憶部２(m-1)に格納される。
【００２３】
以上により、記憶部２(m)に格納される出現頻度は、１段前のユニットＵＮ(m+1)の判定部４ａ(m+1)と、２段前のユニットＵＮ(m+2)の判定部４ａ(m+2)との比較結果に応じて、下表のように集約される。なお、同表において、”Ａ”は記憶部２(m+2)に格納された出現頻度を指し、”Ｂ”は記憶部２(m+2)に格納された出現頻度を指し（Ｂ＞Ａ）、”Ｐ”は加算部３から読み出された新たな出現頻度を指す。
【００２４】
［記憶部２(m)に格納される出現頻度］
判定部４ａ(m+1)    判定部４ａ(m+2)      記憶部２(m)
Ｐ＜Ａ              Ｐ＜Ｂ              Ａ
Ｐ＞Ａ              Ｐ＜Ｂ              Ｐ
Ｐ＞Ａ              Ｐ＞Ｂ              Ｂ
【００２５】
判定部４ａ(m+1)でＰ＜Ａであり、かつ、判定部４ａ(m+2)でＰ＜Ｂである場合、Ｂ＞Ａ＞Ｐが成立するので、新たな出現頻度Ｐは、出現頻度Ｂ−Ａ間に挿入されず、かつ、出現頻度Ａ，Ｂよりさらに前段の出現頻度の間に格納されれる。したがって、記憶部２(m)には、１段後の記憶部２(m+1)に格納された出現頻度Ａが格納される。判定部４ａ(m+1)でＰ＞Ａであり、かつ、判定部４ａ(m+2)でＰ＜Ｂである場合、Ｂ＞Ｐ＞Ａが成立するので、新たな出現頻度Ｐは、出現頻度Ｂ−Ａ間に挿入される。したがって、記憶部２(m)には、新たな出現頻度出現頻度Ｐが格納される。また、判定部４ａ(m+1)でＰ＞Ａであり、かつ、判定部４ａ(m+2)でＰ＞Ｂである場合、Ｐ＞Ｂ＞Ａが成立するので、出現頻度Ｂ−Ａ間に挿入されず、かつ、出現頻度Ａ，Ｂよりさらに後段の出現頻度の間に格納される。したがって、記憶部２(m)には、２段後の記憶部２(m+2)に格納された出現頻度Ａが格納される。
【００２６】
最後段のユニットＵＮ(n)は、記憶部２(n)とソート部４(n)とを有するが、ソート部４(n)は、上述のソート部４(m)のうち、スイッチ４ｃ(m)に相当するものがない。したがって、記憶部２(n)に格納された出現頻度は、そのまま更新されないまま保持される。なぜなら、並べ替えられる出現頻度列Ｄinは、サイクル毎に、自己より前段の記憶部２に格納されていくので、新たな出現頻度が記憶部(n)に格納されることは無いからである。また、最前段のユニットＵＮ(3)は、記憶部２(3)とソート部４(3)とを有するが、ソート部４(3)は、上述のソート部４(m)のうち、スイッチ４ｂ(m)に相当するものがない。したがって、記憶部２(3)に格納された出現頻度は、そのまま記憶部２(1)に出力される。なぜなら、記憶部２(3)に格納される出現頻度は、今回のサイクルにおいて出現頻度列Ｄinの中で３番目に小さい値であり、新たな出現頻度との大小関係を問わず、次回のサイクルにおいて必ず加算対象となる出現頻度だからである。
【００２７】
図３は、本実施形態にかかる一例の構成図である。なお、同図は、本実施形態の特徴的な部分のみを概略的に示したものであり、入力部５や制御部６については省略されている点に留意されたい（この点は後出の図８についても同様）。このハフマン木生成回路１では、６つの記憶部２(1)〜２(6)と、このうち記憶部２(3)〜(6)のそれぞれを含むユニットＵＮ(3)〜ＵＮ(6)とで構成されており、各ユニットＵＮは各サイクルで互いに並列に動作する。つまり、このハフマン木生成回路１は、６つの出現頻度で構成される出現頻度列Ｄinのソート処理を行う。
【００２８】
一例として、昇順に整列された出現頻度列Ｄin”４，５，６，７，１１，６７”から、ハフマン木を生成するためのソート処理の一連の動作について、図４および図５を参照しながら説明する。図４は図３にかかる一例の説明図であり、図６はその一例のタイミングチャート図である。図５は各サイクル前後における記憶部２(1)〜２(n)に格納する出現頻度を示し、図６は同じサイクル中における加算部３、ソート部４および制御部６の処理・信号を示しており、各サイクルは対応している。まず、ソート処理の開始に先立ち、記憶部２(1)から順に出現頻度”４”が格納され、これ続いて、記憶部２(2)に”５”が、記憶部２(3)に”６”が、記憶部２(4)に”７”が、記憶部２(5)に”１１”が、記憶部２(6)に”６７”がそれぞれ格納される（初期状態）。なお、この一例において、出現頻度の数が６（＝ｋ）個なので、一連の処理に要するサイクル数は４回となる。
【００２９】
初回のサイクル（ｃ＝１）において、まず、加算部３によって記憶部２(1)，２(2)とから出現頻度”４”，”５”が読み出され、この２つの出現頻度の加算処理が行われ、新たな出現頻度”９”（＝Ｐ）が生成される。つぎに、ユニットＵＮによって加算部３から新たな出現頻度”９”が読み出され、判定部４ａによって自己のユニットＵＮに属する記憶部２に格納された出現頻度が同時並行的に比較される（比較処理）。これにより、ＣＯＭ（6)はＨレベルに、ＣＯＭ（5)はＨレベルに、ＣＯＭ（4)はＬレベルに、ＣＯＭ（3)はＬレベルにそれぞれ設定され、これに対応するようにスイッチ４ｂ，４ｃの接続先が選択される。そして、制御部６によって記憶部２に格納された出現頻度が出力され、記憶部２(1)から順に出現頻度”６”が格納され、続いて、記憶部２(2)に”７”が、記憶部２(3)に”９”が、記憶部２(4)に”１１”が、記憶部２(5)に”６７”がそれぞれ入力される。出力信号ＳＮＣによって記憶部２に格納された出現頻度が更新されると全ての切替信号ＣＯＭはＬレベルにリセットされる。これは、他のサイクルにおいても同様である。
【００３０】
なお、１つのサイクルを経る毎に、出現頻度列Ｄinの出現頻度の数が１減少するため、以降のサイクルで利用されない記憶部２の後段から、適当な出現頻度”−”が格納されることになる。この適当な出現頻度”−”は、出現頻度Ｄinに含まれるどの出現頻度以上の値であるが、実装上、ソート処理中に入力部５から新たな出現頻度が格納されることはないので、最も値の大きい出現頻度が、その適当な出現頻度となる。つまり、この場合１つのサイクルを経る毎に、出現頻度”６７”が１段前の記憶部２に順次コピーされて格納されることになる。この点に関しては、以降のサイクルにおいても同様である。
【００３１】
２番目のサイクル（ｃ＝２）において、まず、加算部３によって記憶部２(1)，２(2)とから出現頻度”７”，”６”が読み出され、新たな出現頻度”１３”が生成される。つぎに、加算部３から新たな出現頻度”１３”が、記憶部２に格納された出現頻度と同時並行的に比較される。これにより、ＣＯＭ（6)，ＣＯＭ（5)はＨレベルに、ＣＯＭ（4)，ＣＯＭ（3)はＬレベルにそれぞれ設定される。そして、記憶部２に格納された出現頻度が出力され、記憶部２(1)から順に出現頻度”９”が、記憶部２(2)に”１１”が、記憶部２(3)に”１３”が、記憶部２(4)に”６７”がそれぞれ入力される。
【００３２】
３番目のサイクル（ｃ＝３）において、まず、加算部３によって記憶部２(1)，２(2)とから出現頻度”９”，”１１”が読み出され、新たな出現頻度”２０”が生成される。つぎに、加算部３から新たな出現頻度”１３”が、記憶部２に格納された出現頻度と同時並行的に比較される。これにより、ＣＯＭ（6)〜(4)はＨレベルに、ＣＯＭ（3)はＬレベルにそれぞれ設定される。そして、記憶部２に格納された出現頻度が出力され、記憶部２(1)から順に出現頻度”１３”が、記憶部２(2)に”２０”が、記憶部２(3)に”６７”がそれぞれ入力される。
【００３３】
４番目のサイクル（ｃ＝４）において、まず、加算部３によって記憶部２(1)，２(2)とから出現頻度”７”，”６”が読み出され、新たな出現頻度”３３”が生成される。つぎに、加算部３から新たな出現頻度”１３”が、記憶部２に格納された出現頻度と同時並行的に比較される。これにより、すべてのＣＯＭはＨレベルにそれぞれ設定される。そして、記憶部２に格納された出現頻度が出力され、記憶部２(1)に出現頻度”６７”が、記憶部２(2)に”３３”がそれぞれ入力される。なお、記憶部２(2)に格納される新たな出現頻度”３３”はユニットＵＮ(4)から供給される。これは、ユニットＵＮ(4)の記憶部２(4)には、従前のサイクルによって出現頻度”６７（−）”が格納されており、判定部４ａ(4)によって新たな出現頻度”３３”が出力されるためである。
【００３４】
本実施形態によれば、各ソート部４が、パッケージ結合によって生じた新たな出現頻度Ｐとを比較する比較処理を互いに並行して行っている。そして、自己の比較結果に応じて、ソート部４を介して隣接した記憶部２間で出現頻度をシフトすることで、出現頻度列Ｄinを出現頻度の大きさ順に並び替えている。これにより、新たな出現頻度（パッケージ結合後）の配列を別個の出現頻度列Ｄinとして設けなくとも、パッケージ結合の構成が論理的に維持されるので、正しいハフマン木生成が得られるのを保証できる。
【００３５】
特に、新たな出現頻度の比較や、この新たな出現頻度の出現頻度列Ｄinへの挿入を、各ソート部４が同時並行的に行われているので、ハードウェア化により、全体的な処理の高速化を図ることが可能になる。
【００３６】
（第２の実施形態）
上述の実施形態は、パッケージ結合対象となる出現頻度列Ｄinを、前段の記憶部２に詰めるようにシフトする前段詰めシフト型に関するのに対し、第２の実施形態は、後段の記憶部２に詰めるようにシフトする後段詰め型に関する。図６は、第２の実施形態にかかるハフマン木生成回路１の全体構成図である。ハフマン木生成回路１は、第１の実施形態と同様に、複数の記憶部２(1)〜２(n)（ｎ≧３）と、加算部３と、複数のソート部４(3)〜４(n)（ｎ≧３）と、入力部５と、制御部６とを有するが、第２の実施形態のハフマン木生成回路は、さらに複数のスイッチ７(1)〜７(n)を有する。
【００３７】
スイッチ７（スイッチ７(1)〜７(n)のいずれかを指す）は、記憶部２−加算部３間の導通を行っており、その制御を制御部６が行う。制御部６は、制御信号ＣＴＬによって、互いに隣接する２つのスイッチ７をオン状態（Ｈレベル）にさせ、記憶部２−加算部３の導通をさせる。導通させる２つのスイッチ７は、前段の記憶部２に接続されたスイッチ７(1)，７(2)からサイクル毎に順次選択される。具体的には、最初のサイクルにおいて１段目の記憶部２(1)と２段目の記憶部２(2)とが導通され、次のサイクルで２段目の記憶部２(2)と３段目の記憶部２(3)とが導通され、さらにその次のサイクルで３段目の記憶部２(3)と４段目の記憶部２(4)とが導通されるといった如くである。これにより、加算部３が読み出す一対の記憶部２は、サイクル毎に可変に設定される。
【００３８】
図７は、本実施形態にかかる単一のＵＮの構成図である。具体的には、両端のユニットＵＮ(n)を除くユニットＵＮ(m)の構成図である。ユニットＵＮ(m)は、記憶部２(m)とソート部４(m)とから構成されている。記憶部２(m)は、スイッチ７(m)に接続されている。ソート部４(m)は、判定部４ａ(m)と２つのスイッチ４ｂ(m)，４ｃ(m)とを有する。また、記憶部２(m)と加算部３から読み出された出現頻度の大小に応じて、自己のユニットＵＮ(m)のスイッチ４ｂ(m)，４ｃ(m)とを制御する。
【００３９】
スイッチ４ｂ(m)は、判定部４ａ(m)の比較結果に応じて、隣接した１段前のソート部４(m-1)に出力する出現頻度を選択する。スイッチ４ｂ(m)の一方の入力端子は、記憶部２(m)に接続されており、その他方の入力端子は、加算部３（新たな出現頻度Ｐ）に接続されている。そして、自己のユニットＵＮ(m)の判定部４ａ(m)による切換信号ＣＯＭ(m)の下、記憶部２(m)に格納された出現頻度と、加算部３からの新たな出現頻度Ｐとで構成される一対の出現頻度のいずれかが、出力出現頻度ＯＰ２(m)として前段のユニットに出力される。なお、出力出現頻度ＯＰ(m)は、１段前のユニットＵＮ(m-1)（ソート部４(m-1)）に入力される。また、スイッチ４ｃ(m)は、判定部４ａ(m)の比較結果に応じて、記憶部２(m)に格納する出現頻度を選択する。スイッチ４ｃ(m)の入力端子は、隣接した１段後のユニットＵＮ(m+1)に接続されており、その出力端子は、記憶部２(m)に接続されている。判定部４ａ(m)による導通制御の下、ユニットＵＮ(m+1)から読み出された出現頻度が記憶部２(m)に適宜格納される。
【００４０】
判定部４ａ(m)によって、自己のユニットＵＮ(m)のスイッチ４ｂ(m)，４ｃ(m)との切換状態は、記憶部２(m)，加算部３から読み出された出現頻度の大小とに応じて、下表のように設定される。なお、同表において、”ｐ”は記憶部２(m)から読み出された出現頻度を指し、”Ｐ”は加算部３から読み出された新たな出現頻度を指す。
【００４１】
［スイッチ４ｂ(m)，スイッチ４ｃ(m)の状態］
判定部４ａ(m)  切替信号ＣＯＭ(m)  スイッチ４ｂ(m)  スイッチ４ｃ(m)
Ｐ＜ｐ            Ｈ            加算部３側          オフ
Ｐ＞ｐ            Ｌ            記憶部２(m)側       オン
【００４２】
判定部４ａ(m)は、記憶部２(m)と加算部３とから読み出された出現頻度のセットｐ，Ｐの値の大小を比較し、この比較結果に応じて、スイッチ４ｂ(m)およびスイッチ４ｃ(m-1)の状態を設定する。Ｐ＜ｐの場合（ＣＯＭ(m)＝Ｈレベル）には、スイッチ４ｂ(m)が加算部３側、スイッチ４ｃ(m)がオフに設定される。これにより、新たな出現頻度Ｐは、スイッチ４ｂ(m)を介して出力出現頻度ＯＰ(m)として後段に出力される。また、１段後のユニットＵＮ(m+1)からＯＰ(m+1)として出力された出現頻度は、記憶部２(m)に格納されない。一方、Ｐ＞ｐの場合（ＣＯＭ(m)＝Ｌレベル）には、スイッチ４ｂ(m)が記憶部２側、スイッチ４ｃ(m)がオン状態に設定される。これにより、出現頻度ｐは、スイッチ４ｂ(m)を介して出力出現頻度ＯＰ(m)として後段に出力される。また、１段後のユニットＵＮ(m+1)からＯＰ(m+1)として出力された出現頻度は、スイッチ４ｃ(m)を介して記憶部２(m)に格納される。
【００４３】
以上より、記憶部２(m)に格納される出現頻度は、自己のユニットＵＮ(m)の判定部４ａ(m)と、１段前のユニットＵＮ(m+1)の判定部４ａ(m+1)との比較結果に応じて、下表に集約される。なお、同表において、”Ａ”は記憶部２(m)に格納された出現頻度を指し、”Ｂ”は記憶部２(m+1)に格納された出現頻度を指し（Ｂ＞Ａ）、”Ｐ”は加算部３から読み出された新たな出現頻度を指す。
【００４４】
［記憶部２(m)に格納される出現頻度］
判定部４ａ(m)    判定部４ａ(m+1)      記憶部２(m)
Ｐ＜Ａ            Ｐ＜Ｂ              Ａ
Ｐ＞Ａ            Ｐ＜Ｂ              Ｐ
Ｐ＞Ａ            Ｐ＞Ｂ              Ｂ
【００４５】
判定部４ａ(m)でＰ＜Ａであり、かつ、判定部４ａ(m+1)でＰ＜Ｂである場合、Ｂ＞Ａ＞Ｐが成立するので、新たな出現頻度Ｐは、出現頻度Ｂ−Ａ間に挿入されず、かつ、出現頻度Ａ，Ｂよりさらに前段の出現頻度の間に格納されれる。本実施形態では、出現頻度列Ｄinを後段の記憶部２に詰めるので、出現頻度Ｐは、出現頻度”Ａ”を格納する記憶部２(m)より後段となる記憶部２に格納されることになる。したがって、記憶部２(m)には出現頻度Ａが保持される。判定部４ａ(m)でＰ＞Ａであり、かつ、判定部４ａ(m+1)でＰ＜Ｂである場合、Ｂ＞Ｐ＞Ａが成立するので、新たな出現頻度Ｐは、出現頻度Ｂ−Ａ間に挿入される。したがって、記憶部２(m)には、新たな出現頻度出現頻度Ｐが格納される。また、判定部４ａ(m)でＰ＞Ａであり、かつ、判定部４ａ(m+1)でＰ＞Ｂである場合、Ｐ＞Ｂ＞Ａが成立するので、出現頻度Ｂ−Ａ間に挿入されず、かつ、出現頻度Ａ，Ｂよりさらに後段の出現頻度の間に格納される。したがって、記憶部２(m)には、１段後の記憶部２(m+1)に格納された出現頻度”Ｂ”が格納される。
【００４６】
最後段のユニットＵＮ(n)は、記憶部２(n)とソート部４(n)とを有するが、ソート部４(n)は、上述したソート部４(m)のうち、スイッチ４ｃ(m)に相当するものがない。したがって、記憶部２(n)に格納された出現頻度は、そのまま更新されないまま保持される。なぜなら、並べ替えられる出現頻度列Ｄinは、サイクル毎に、前段の記憶部２に格納されていくので、新たな出現頻度が記憶部(n)に格納されることは無いからである。
【００４７】
図８は、本実施形態にかかる一例の構成図である。このハフマン木生成回路１では、６つの記憶部２(1)〜２(6)と、このうち記憶部２(3)〜(6)のそれぞれを含むユニットＵＮ(3)〜ＵＮ(6)とで構成されており、各ユニットＵＮは各サイクルで互いに並列に動作する。つまり、このハフマン木生成回路１は、６つの出現頻度で構成される出現頻度列Ｄinのソート処理を行う。なお、スイッチ７(1)〜７(6)の制御は、制御部６からの制御信号ＣＴＬ（ＣＴＬ(1)〜ＣＴＬ(6)のいずれかを指す）に基づいて行われる。
【００４８】
一例として、整列された出現頻度列Ｄin”４，５，６，７，１１，６７”から、ハフマン木を生成するためのソート処理の一連の動作について、図９および図１０を参照しながら説明する。図９は図８にかかる一例の説明図であり、図１０はその一例のタイミングチャート図である。図９は各サイクル前後における記憶部２(1)〜２(n)に格納する出現頻度を示し、図１０は同じサイクル中における加算部３、ソート部４および制御部６の処理・信号を示しており、各サイクルは対応している。まず、ソート処理の開始に先立ち、第１の実施形態と同様に、記憶部２(1)から順に出現頻度が昇順に格納される。
【００４９】
初回のサイクル（ｃ＝１）において、制御信号ＣＴＬ(1)，ＣＴＬ(2)のみがＨレベルになり、スイッチ７(1)，７(2)はオン状態となる。これにより、加算部３によって記憶部２(1)，２(2)とから出現頻度”４”，”５”が読み出され、この２つの出現頻度の加算処理が行われ、新たな出現頻度”９”が生成される。つぎに、ユニットＵＮによって加算部３から新たな出現頻度”９”が読み出され、自己のユニットＵＮの記憶部２に格納された出現頻度と同時並行的に比較される（比較処理）。これにより、ＣＯＭ（6)，ＣＯＭ（5)はＨレベルに、ＣＯＭ（4)，ＣＯＭ（3)はＬレベルにそれぞれ設定され、これに対応するようにスイッチ４ｂ，４ｃの接続先が選択される。そして、制御部６の出力信号ＳＮＣによって記憶部２に格納された出現頻度が出力され、記憶部２(2)から順に出現頻度”６”が、記憶部２(3)に”７”が、記憶部２(4)に”９”が、記憶部２(5)に”１１”が、記憶部２(6)に”６７”がそれぞれ入力される。出力信号ＳＮＣによって記憶部２に格納された出現頻度が更新されると、全ての切替信号ＣＯＭはＬレベルにリセットされる。これは他のサイクルにおいても同様である。
【００５０】
なお、１つのサイクルを経る毎に、出現頻度列Ｄinの出現頻度の数が１減少するため、以降のサイクルで利用されない記憶部２の前段から、適当な出現頻度”−”が格納されることになる。この適当な出現頻度”−”は、実装上、ソート処理中に入力部５から新たな出現頻度が格納されることはないので、今回のサイクルで最前段の記憶部２に格納されていた出現頻度が、そのまま保持されたままとなる。この点に関しては、以降のサイクルにおいても同様である。
【００５１】
２番目のサイクル（ｃ＝２）において、制御信号ＣＴＬ(2)，ＣＴＬ(3)のみがＨレベルになり、スイッチ７(2)，７(3)はオン状態となる。これにより、加算部３によって記憶部２(2)，２(3)とから出現頻度”７”，”６”が読み出され、新たな出現頻度”１３”が生成される。つぎに、ユニットＵＮによって加算部３から新たな出現頻度”１３”が、記憶部２に格納された出現頻度と同時並行的に比較される。これにより、ＣＯＭ（6)のみがＨレベルに設定される。そして、記憶部２に格納された出現頻度が出力され、記憶部２(3)から順に出現頻度”９”が格納され、続いて、記憶部２(4)に”１１”が、記憶部２(5)に”１３”が、記憶部２(6)に”６７”がそれぞれ入力される。
【００５２】
３番目のサイクル（ｃ＝３）において、制御信号ＣＴＬ(3)，ＣＴＬ(4)のみがＨレベルになり、スイッチ７(3)，７(4)はオン状態となる。これにより、加算部３によって記憶部２(1)，２(2)とから出現頻度”９”，”１１”が読み出され、新たな出現頻度”２０”が生成される。つぎに、ユニットＵＮによって加算部３から新たな出現頻度”１３”が、記憶部２に格納された出現頻度と同時並行的に比較される。これにより、ＣＯＭ（6)のみがＨレベルに設定される。そして、記憶部２に格納された出現頻度が出力され、記憶部２(4)から順に出現頻度”１３”が格納され、続いて、記憶部２(5)に”２０”が、記憶部２(6)に”６７”がそれぞれ入力される。
【００５３】
４番目のサイクル（ｃ＝４）において、制御信号ＣＴＬ(4)，ＣＴＬ(5)のみがＨレベルになり、スイッチ７(1)，７(2)はオン状態となる。これにより、加算部３によって記憶部２(1)，２(2)とから出現頻度”７”，”６”が読み出され、新たな出現頻度”３３”が生成される。つぎに、ユニットＵＮによって加算部３から新たな出現頻度”１３”が、記憶部２に格納された出現頻度と同時並行的に比較される。これにより、ＣＯＭ（6)のみがＨレベルに設定される。そして、記憶部２に格納された出現頻度が出力され、記憶部２(1)に出現頻度”６７”が格納され、記憶部２(2)に”３３”がそれぞれ入力される。
【００５４】
本実施形態によれば、第１の実施形態と比べて、ソートされた出現頻度列Ｄinが後段の記憶部２に詰めるようにシフトする回路であっても、制御部６およびスイッチ７によって、加算対象となる出現頻度は常に最も値の小さい二つの出現頻度を選択する。したがって、第１の実施形態と同様に、パッケージ結合の構成が論理的に維持されるので、正しいハフマン木生成が得られるのを保証できる。特に、新たな出現頻度の比較や、この新たな出現頻度の出現頻度列Ｄinへの挿入を、各ソート部４が同時並行的に行われているので、ハードウェア化により、全体的な処理の高速化を図ることが可能になる。
【００５５】
（第３の実施形態）
図１１は、上述したハフマン木生成回路１を実装したハフマンテーブル生成システム１０の構成図である。ハフマンテーブル生成システム１０は、シンボルの出現頻度の規則性に着目してデータ圧縮を行う代表的なアルゴリズムであり、各出現頻度に対応する符号長（または符号）を個々のデータに割り当てたハフマンテーブルを生成するハフマンテーブル生成処理を行う。このとき、このハフマンテーブル生成処理には、パッケージ結合(ノード結合)の各ステップにおいて、最小の出現頻度を抽出する過程が必要となる。つまり、上述した実施形態のハフマン木生成回路１を用いることで、常に、整列された出現頻度表が得られ、シームレスなハフマンテーブル生成処理を行うことができる。ハフマンテーブル生成システム１０は、上述した第１または第２の実施形態のハフマン木生成回路１と、符号生成回路１１とで構成されている。ハフマン木生成回路１には、ソート処理が施された（整列された）出現頻度列Ｄinが入力される。符号生成回路１１は、周知の構成を有し、パッケージ結合の対象（加算部３の処理対象）となる出現頻度を、出現頻度と対応するノード番号を用いて管理する。そして、サイクル毎にパッケージ結合の対象となるノード番号に対応する符号長（または符号）を更新し、全ての出現頻度のパッケージ結合を終了した時点で、各出現頻度に対応する符号長（または符号）を出力する。
【００５６】
本実施形態によれば、ハフマンテーブルの生成に先立ち必要となる出現頻度列Ｄinのソート処理が高速化されるので、全体的なデータ圧縮処理の高速化を図ることができる。
【図面の簡単な説明】
【００５７】
【図１】第１の実施形態にかかるハフマン木生成回路の全体構成図
【図２】第１の実施形態にかかる単一のユニットの構成図
【図３】第１の実施形態にかかる一例の構成図
【図４】第１の実施形態にかかる一例の説明図
【図５】第１の実施形態にかかる一例の説明図
【図６】第２の実施形態にかかるハフマン木生成回路の全体構成図
【図７】第２の実施形態にかかる単一のユニットの構成図
【図８】第２の実施形態にかかる一例の構成図
【図９】第２の実施形態にかかる一例の説明図
【図１０】第２の実施形態にかかる一例の説明図
【図１１】第３の実施形態にかかるハフマンテーブル生成システムの構成図
【符号の説明】
【００５８】
ＵＮ  ユニット
１  ハフマン木生成回路
２  記憶部
３  加算部
４  ソート部
４ａ  判定部
４ｂ，４ｃスイッチ
５  入力部
６  制御部
７  スイッチ
１０  ハフマンテーブル生成システム
１１  符号生成回路
【図１】
2007243880.tif 000003
【図２】
2007243880.tif 000004
【図３】
2007243880.tif 000005
【図４】
2007243880.tif 000006
【図５】
2007243880.tif 000007
【図６】
2007243880.tif 000008
【図７】
2007243880.tif 000009
【図８】
2007243880.tif 000010
【図９】
2007243880.tif 000011
【図１０】
2007243880.tif 000012
【図１１】
2007243880.tif 000013