(57)【特許請求の範囲】
【請求項１】
１曲が複数のフレームで構成されるとともに、複数のハフマン符号表をフレーム単位で適宜切り換え適用して符号化されたＭＰ３規格等の時系列オーディオデータを復号する方法であって、
前記時系列データの各フレーム毎に、該フレームがどのハフマン符号表を適用して符号化されているかを分析し、
前記複数のハフマン符号表のうち最大符号長の短い一部のハフマン符号表を適用して符号化されたフレームについては復号テーブルを用いた直接法でデータを復号し、前記一部のハフマン符号表以外の大部分のハフマン符号表を適用して符号化されたフレームについてはバイナリツリー検索法でデータを復号するハフマン符号の復号方法。
【請求項２】
１曲が複数のフレームで構成されるとともに、複数のハフマン符号表をフレーム単位で適宜切り換え適用して符号化されたＭＰ３規格等の時系列オーディオデータを復号する装置であって、
前記複数のハフマン符号表のうち最大符号長の短い一部のハフマン符号表を適用して符号化されたフレームを復号テーブルを用いた直接法でデータを復号する直接法復号手段と、
前記一部のハフマン符号表以外の大部分のハフマン符号表を適用して符号化されたフレームをバイナリツリー検索法でデータを復号するバイナリツリー復号手段と、
前記符号化データがどのハフマン符号表を適用して符号化されているかを先頭から順次分析する分析手段と、
分析部の分析結果に基づいて復号部を選択し、選択した復号部に符号化データを順次入力する選択手段と、
を備えたハフマン符号復号装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、限られたメモリで高速にハフマン符号を復号化する復号化方法および装置に関する。
【０００２】
【従来の技術】
ハフマン符号を復号するための技術として、一般的には、バイナリツリー検索法、直接法などの手法がある。バイナリツリー検索法は、可変長のハフマン符号を先頭ビットから１ビットずつ順に検査して０／１で分岐してゆき、最後に到達したところで指定されている値を出力するものであり、主としてソフトウェア的に実現されるものである。また、直接法は、可変長符号の最大ビット長のアドレスを有するメモリエリアを確保し、各アドレスのうちハフマン符号が割り当てられているエリアにその値を書き込み、ハフマン符号をアドレスにしてこのメモリエリアをアクセスし、アクセスされたエリアの値を出力するものである。
【０００３】
【発明が解決しようとする課題】
しかし、上記バイナリツリー検索法は、ハフマン符号を１ビットずつ検査してゆくものであるため、復号化に時間が掛かるという欠点があった。また、直接法は、ハフマン符号でメモリをアクセスすることによって直接その値を読み出すことができるため高速であるが、最大ビット長のアドレスを有するメモリエリアを確保しなければならないため、実際にハフマン符号が割り当てられているエリアよりもはるかに大きいエリアを有する復号テーブルが必要になるという欠点があった。
【０００４】
特に、複数のハフマン符号表を持ち、場合に応じてそのいずれかが選択されるデータの場合、全てのハフマン符号表に対応する復号テーブルを設けることは非常に大きなメモリが必要になるため実現が困難で、このような形式のデータを復号化する装置では、バイナリツリー検索法が用いられることが一般的であった。しかし、上記したようにバイナリツリー検索法では復号化に時間が掛かるという問題点があった。
【０００５】
この発明は、複数のハフマン符号表を用いるデータを、小さいメモリで高速に復号化できる復号化方法および装置を提供することを目的とする。
【０００６】
【課題を解決するための手段】
この発明は、１曲が複数のフレームで構成されるとともに、複数のハフマン符号表をフレーム単位で適宜切り換え適用して符号化されたＭＰ３規格等の時系列オーディオデータを復号する方法であって、前記時系列データの各フレーム毎に、該フレームがどのハフマン符号表を適用して符号化されているかを分析し、前記複数のハフマン符号表のうち最大符号長の短い一部のハフマン符号表を適用して符号化されたフレームについては復号テーブルを用いた直接法でデータを復号し、前記一部のハフマン符号表以外の大部分のハフマン符号表を適用して符号化されたフレームについてはバイナリツリー検索法でデータを復号することを特徴とする。
【０００７】
この発明は、１曲が複数のフレームで構成されるとともに、複数のハフマン符号表をフレーム単位で適宜切り換え適用して符号化されたＭＰ３規格等の時系列オーディオデータを復号する装置であって、前記複数のハフマン符号表のうち最大符号長の短い一部のハフマン符号表を適用して符号化されたフレームを復号テーブルを用いた直接法でデータを復号する直接法復号手段と、前記一部のハフマン符号表以外の大部分のハフマン符号表を適用して符号化されたフレームをバイナリツリー検索法でデータを復号するバイナリツリー復号手段と、前記符号化データがどのハフマン符号表を適用して符号化されているかを先頭から順次分析する分析手段と、分析部の分析結果に基づいて復号部を選択し、選択した復号部に符号化データを順次入力する選択手段と、を備えたことを特徴とする。
【０００８】
この発明は、上記発明において、前記複数のハフマン符号表のうち、データを符号化するときに適用される頻度の高い符号表を前記所定のハフマン符号表とすることを特徴とする。
この発明は、上記発明において、前記複数のハフマン符号表のうち、最大符号長の短い符号表を前記所定のハフマン符号表とすることを特徴とする。
【０００９】
この発明は、「短い符号はよく出現する。したがって、短い符号を持つ符号表はよく指定される。このよく指定される符号表に含まれる符号だけでも高速に復号できれば、全体の復号処理を高速化することができる。」という考えに基づいている。具体的には、基本的にはバイナリツリー検索法で復号するが、よく出現する（最大符号長の短い）符号表については直接法によって復号するようにする。これにより、小さい復号テーブルで復号処理をすることができ、且つ高速で復号することが可能になる。
【００１０】
【発明の実施の形態】
図面を参照してこの発明の実施形態について説明する。ＭＰ３規格などのビットストリーム形式のデータでは、予め規格で定められた複数のハフマン符号表のうち最適なものをフレーム毎に選択して適用する。各フレームにどのハフマン符号表が適用されているかは、各フレームのヘッダに書き込まれている。復号装置では、ヘッダを参照して各フレーム毎にハフマン符号表を選択し、そのハフマン符号表を用いてデータを復号化する。ＭＰ３規格では、３４のハフマン符号表が定められているが、以下は説明を簡略化するため、図２に示すような２つの符号表が定められている場合を例にあげて説明する。
【００１１】
入力されるビットストリームは、図２に示す２つのハフマン符号表のいずれかを使用して符号化されたものとする。図１はこの発明の実施形態である復号装置のブロック図である。この復号装置では、上記ビットストリームを回路規模を大きくせずにできるだけ高速に復号化するため、最大符号長の小さな符号表＃０が指定された場合は、直接法による復号を行い、最大符号長の大きな符号表＃１が指定された場合にはバイナリツリー検索法で復号するようにしている。
【００１２】
図１において、ビットストリームはＲＡＭ１０に入力される。ハフマン符号表分析部１１は、入力されたビットストリームの（各フレーム）のヘッダを分析してそのフレームがどのハフマン符号表を用いているかを分析する。この実施形態では、符号表＃０、符号表＃１のどちらを用いているかを分析する。分析結果は、復号方法選択部１２、取得ビット数算出部１３および２つの復号部１５，１６に入力される。２つの復号部は、それぞれ直接法復号部１５およびバイナリツリー復号部１６である。
【００１３】
復号方法選択部１２は、入力されたビットストリームが＃０、＃１どちらの符号表を用いているかに対応して復号部１５，１６のうちどちらの復号部を使用するかを選択し、データの流れを切り換える。取得ビット数算出部１３は、符号表＃０に直接法を適用する場合に１回に読み出すデータのビット数（３ビット）、および、符号表＃１にバイナリツリー検索法を適用する場合に１回に読み出すデータのビット数（１ビット）を割り出して、ビット取り出し／巻き戻し部１４に出力する。取得ビット算出部１３には、図３に示すデータを記憶したメモリ（ＲＯＭ）が設けられている。
【００１４】
ビット取り出し／巻き戻し部１４は、取得ビット数算出部１３から入力されたビット数のデータをＲＡＭ１０から読み出して復号方法選択部１２で選択されている復号部に供給する。また、直接法復号部１５から返信されたきた巻き戻しビット数を受信し、ＲＡＭ１０の読出ポインタを巻き戻しビット数だけ巻き戻す。なお、バイナリツリー検索法によるハフマン符号の復号の場合、１ビットずつ読み出されていずれかのハフマン符号にヒットしたとき復号が行われるため、巻き戻しビット数は常に０である。
【００１５】
直接法復号部１５は、復号テーブルを備え、最大符号長分のビットを入力して復号テーブルをアクセスし、対応する値（復号データ）を次段（図示せず）に出力する。また、この復号処理によって今回のハフマン符号の実際のビット数を割り出し、余分に読み出したビット数（最大符号長のビット数−実際のビット数）である巻き戻しビット数をビット取り出し／巻き戻し部１４に出力する。
【００１６】
また、バイナリツリー復号部１６は、ビットストリームを１ビットずつ入力し、これで符号表＃１を復号するためのバイナリツリーを検索してハフマン符号を復号する。復号データは次段に出力される。
【００１７】
ビットストリームがＲＡＭ１０に入力され、ハフマン符号表番号分析部１１がそのデータに用いられている符号表を割り出すと、この符号表番号情報に基づいて、復号方法選択部１２が復号部１５，１６のうち一方を選択し、取得ビット算出部１３が取得すべきビット数を算出してビット取り出し／巻き戻し部１４にそのビット数情報を入力する。
【００１８】
ビット取り出し／巻き戻し部１４は、そのビット数のデータをＲＡＭ１０から読み出して、上記選択された復号部１５または１６に出力する。選択された復号部は、入力されるデータのハフマン符号を復号し、復号データを出力する。直接法復号部１５でハフマン符号を復号処理した場合には、復号データとともに巻き戻しビット数が出力され、これがビット取り出し／巻き戻し部１４に返信される。ビット取り出し／巻き戻し部１４はこのビット数だけＲＡＭ１０の読出ポインタを巻き戻し、巻き戻した位置から次の復号処理のためのデータを読み出す。
【００１９】
上記の構成で、たとえば図４に示すようなビットストリームのフレームデータ（ハフマン符号列）が入力されたとする。フレームデータの先頭位置と用いられているハフマン符号表はハフマン符号表番号分析部１１によって分析済である。ここで、２つ以上の処理方法を切り換えることで演算量が削減されることを見るために、（１）バイナリツリー検索法のみで復号化する場合の復号部アクセス回数と、（２）直接法とバイナリツリー検索法とを符号表番号で切り換えた場合の復号部アクセス回数を比較する。バイナリツリー検索法では１ビット毎にアクセスが発生するのに対し、直接法では１回のアクセスで１つのハフマン符号が復号可能である。
【００２０】
よって、（１）では計１４回、（２）では計１１回のアクセスが発生する。このことは、直接法とバイナリツリー検索法とを表番号で切り換えることにより、アクセス回数が２１％削減されたことを示す。
【００２１】
また、バイナリツリー法で使用するテーブルは一般に２ｎ−１ワードで構成され、１ワードには復号値とテーブル内アドレスが格納される。表番号＃０の場合、ｎ＝４であるからテーブルのワード数は７である。この７ワードのテーブルにアクセスするためのアドレスフィールドはｌｏｇ（２）７≒２．８ビット以上必要であり、ビット数は整数であるため、必要ビット数は３ビットとなる。復号値を表現するには２ビット必要であるから、このテーブルの１ワードは３＋２＝５ビットとなる。したがって、全ワードを表現するためには５×７＝３５ビットのメモリエリアが必要である。同様に表番号＃１の場合も同様に、ｌｏｇ（２）３１≒４．９５で必要ビット数は５ビットとなり、（５＋４）×３１＝２７９ビットのメモリエリアが必要である。
【００２２】
一方、直接法で使用するテーブルの１ワードには、復号値と符号長が格納される。また符号表に定義されている符号数をｎとすると、それを実現するテーブルのワード数＝２n ワードとなる。表番号＃０の復号テーブルの場合、復号値を表現するために必要なビット数は２ビット、符号長を表現するために必要なビット数は２ビットであるから、１ワードは２＋２＝４ビットでよい。このワードが２3 ＝８個必要なので、全ワードを表現するためには４×８＝３２ビットのメモリエリアが必要である。同様に表番号＃１の復号テーブルの場合には、（４＋４）×２8 ＝２０４８ビットのメモリエリアが必要である。
【００２３】
以上より、表番号＃０、表番号＃１ともにバイナリツリー法で復号する場合には３５＋２７９＝３１４ビットのＲＯＭが必要である。これをすべて直接法に置き換えると３２＋２０４８＝２０８０ビットのＲＯＭが必要になる。この場合、確かに演算量は劇的に少なくなるが、急激にメモリ量が増大しており、実際のアプリケーションでは現実的でなくなる。
【００２４】
これに対して、表番号＃０だけを直接法で置き換えた場合、必要なメモリは３２＋２７９＝３１１ビットとなり、上述のとおり両方ともバイナリツリー法で復号する場合に比べて、若干のメモリ量が増大するのみで大幅に演算量を削減することができる。
【００２５】
以下、図５、図６を参照して、実際のＰＣＭオーディオデータをＭＰ３エンコードした場合の実験結果を示す。
まず、実験には２種類のエンコーダ（Ｅｎｃｏｄｅｒ１，Ｅｎｃｏｄｅｒ２）を用いた。この２種類のエンコーダに２種類のＰＣＭオーディオデータを入力して合計４種類のビットストリーム（ステレオ、１２８ｂｐｓ）を作成した。第１のＰＣＭオーディオデータ（音楽ソースＡ）は全体に音量の大きいポップスの曲であり、第２のＰＣＭオーディオデータ（音楽ソースＢ）は静かなピアノソロ曲である。これら４種類のビットストリームについてどの符号表が指定されているかを１符号語毎にカウントした。この結果を図５に示す。
【００２６】
図５より、Ｅｎｃｏｄｅｒ１，２の両方とも、ソースＡでは番号の小さな符号表が多く選ばれ、Ｂでは番号の大きな符号表が多く選ばれる傾向がある。ただし、Ｅｎｃｏｄｅｒ１ではソースＢでもＮｏ２の符号表が最も多く使用されている。また、符号表Ｑｕａｄ（Ａ），Ｑｕａｄ（Ｂ）の利用頻度も高いが、これは各フレーム中のｃｏｕｎｔ１領域ついては、符号表Ｑｕａｄ（Ａ）またはＱｕａｄ（Ｂ）が二者択一で必ず使用されるためである。
【００２７】
図５より、他の符号表に比べて選択回数の多い符号表はＴａｂｌｅ２，３，５，１５，Ｑｕａｄ（Ａ），Ｑｕａｄ（Ｂ）などになるが、直接法による復号を行う場合は実現のしやすさから、ここでは最長符号長が短いＴａｂｌｅ２，３，Ｑｕａｄ（Ａ），Ｑｕａｄ（Ｂ）についてのみ直接法によって復号することとし、その他の符号表ではバイナリツリー検索法で復号するようにする。
【００２８】
以上の方法でのハフマン復号処理に必要な演算量と、純粋にバイナリツリー検索法のみによるハフマン復号処理に必要な演算量を算出し、比較した。結果を図６に示す。
【００２９】
図６は、１フレーム当たりのハフマン復号に必要な演算量を算出し、時間軸に並べたものであり、上で使用した４種類のビットストリームに対してそれぞれ（Ａ−１）、（Ａ−２）、（Ｂ−１）、（Ｂ−２）が対応する。この図においてＢｉｎがバイナリツリー検索法のみで復号化した場合のフレームあたりの処理ステップ数であり、ＤＴＬが本発明の方式で直接法とバイナリツリー検索法とを組み合わせて復号化した場合のフレームあたりの処理ステップ数である。
【００３０】
なお、上記のようにＴａｂｌｅ２，３，Ｑｕａｄ（Ａ），Ｑｕａｄ（Ｂ）を直接法で復号化した場合、音楽ソースＡの演算量が大きく削減され、音楽ソースＢの場合にはそれほどでもない。これは、上記の直接法で復号するハフマン符号表の選択が音楽ソースＡによりよく適合していたことを示し、音楽ソースＢをより効率的に復号化する（演算量を削減する）ためには、Ｔａｂｌｅ２，５，１５，２６などを直接法で復号化するようにすればよい。
【００３１】
このように、復号装置において、よく復号（再生）するオーディオソースのジャンルに応じて直接法で復号する符号表を変えるようにしてもよい。
【００３２】
【発明の効果】
以上のようにこの発明によれば、ハフマン符号表に応じて直接法とバイナリツリー法とを切り換えるようにしたことにより、小さい復号テーブルで復号処理をすることができ、且つ高速で復号することが可能になる。
【図面の簡単な説明】
【図１】この発明の実施形態であるハフマン符号復号装置のブロック図
【図２】同ハフマン符号復号装置で用いられるハフマン符号表を示す図
【図３】同ハフマン符号復号装置の取得ビット数算出部に内蔵されるＲＯＭの記憶内容を示す図
【図４】同ハフマン符号復号装置で復号される入力データの例を示す図
【図５】ＰＣＭオーディオデータをＭＰ３データにエンコードした場合の各ハフマン符号表の使用頻度分布を示す図
【図６】上記ＭＰ３データをバイナリツリー検索法で復号化した場合と本願発明の方法で復号化した場合の復号に要する処理ステップ数を比較した図
【符号の説明】
１０…ＲＡＭ、１１…ハフマン符号表番号分析部、１２…復号方法選択部、１３…取得ビット数算出部、１４…ビット取り出し／巻き戻し部、１５…直接法復号部、１６…バイナリツリー復号部
【図１】
0003659196.tif 000002
【図２】
0003659196.tif 000003
【図３】
0003659196.tif 000004
【図４】
0003659196.tif 000005
【図５】
0003659196.tif 000006
【図６】
0003659196.tif 000007