(57)【要約】  指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタに１を加算する処理をｉ＝０，１，…，Ｎ−１のそれぞれに対して行う。Σｔ＝Ｔｈｒｅｓ−１Ｍｂｉｔｃｏｕｎｔ（ｔ）＞Ｍａｘｂｉｔ≧Σｔ＝ＴｈｒｅｓＭｂｉｔｃｏｕｎｔ（ｔ）という関係を満たす値Ｔｈｒｅｓ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔｈｒｅｓ＋１とＬのうち小さい方の数のビットを割り当てる。値Ｔｈｒｅｓ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうちＭａｘｂｉｔ−Σｔ＝ＴｈｒｅｓＭｂｉｔｃｏｕｎｔ（ｔ）個の各サンプルに対して、１個のビットを割り当てる。
2012002348.tif 000002
【特許請求の範囲】
【請求項１】
１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てるビット割当装置において、
上記Ｎ個のサンプルのサンプル番号を０，１，…，ｉ，…，Ｎ−１とし、サンプル番号ｉのサンプルに与えられた重要度を表す指標をｋ（ｉ）とし、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタｂｉｔｃｏｕｎｔの初期値を０として、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行うビットカウント部と、
指標ｋ（ｉ）の最大値をＭとして、下記式（１）で定義される値Ｔ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔ＋１とＬのうち小さい方の数のビットを割り当てる第一割当部と、
【数３】
2012002348.tif 000005
上記値Ｔ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうち下記式（２）で定義される個数の各サンプルに対して、１個のビットを割り当てる第二割当部と、
【数４】
2012002348.tif 000006
を含むビット割当装置。
【請求項２】
１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てるビット割当装置において、
上記Ｎ個のサンプルに与えられた重要度を表す指標に基づいて、上記Ｎ個のサンプルを重要な順に並び替えるソート部と、
上記並び替えられたＮ個のサンプルのサンプル番号を新たに０，１，…，ｉ，…，Ｎ−１とし、サンプル番号ｉのサンプルに与えられた重要度を表す指標をｋ（ｉ）とし、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタｂｉｔｃｏｕｎｔの初期値を０として、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行うビットカウント部と、
指標ｋ（ｉ）の最大値をＭとして、下記式（１）で定義される値Ｔ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔ＋１とＬのうち小さい方の数のビットを割り当てる第一割当部と、
【数５】
2012002348.tif 000007
上記値Ｔ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうち上記並び替えの前のサンプル番号が小さい方から下記式（２）で定義される個数の各サンプルに対して、１個のビットを割り当てる第二割当部と、
【数６】
2012002348.tif 000008
を含むビット割当装置。
【請求項３】
１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てるビット割当方法において、
ビットカウント部が、上記Ｎ個のサンプルのサンプル番号を０，１，…，ｉ，…，Ｎ−１とし、サンプル番号ｉのサンプルに与えられた重要度を表す指標をｋ（ｉ）とし、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタｂｉｔｃｏｕｎｔの初期値を０として、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行うビットカウントステップと、
第一割当部が、指標ｋ（ｉ）の最大値をＭとして、下記式（１）で定義される値Ｔ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔ＋１とＬのうち小さい方の数のビットを割り当てる第一割当ステップと、
【数７】
2012002348.tif 000009
第二割当部が、上記値Ｔ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうち下記式（２）で定義される個数の各サンプルに対して、１個のビットを割り当てる第二割当ステップと、
【数８】
2012002348.tif 000010
を含むビット割当方法。
【請求項４】
１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てるビット割当方法において、
ソート部が、上記Ｎ個のサンプルに与えられた重要度を表す指標に基づいて、上記Ｎ個のサンプルを重要な順に並び替えるソートステップと、
ビットカウント部が、上記並び替えられたＮ個のサンプルのサンプル番号を新たに０，１，…，ｉ，…，Ｎ−１とし、サンプル番号ｉのサンプルに与えられた重要度を表す指標をｋ（ｉ）とし、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタｂｉｔｃｏｕｎｔの初期値を０として、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行うビットカウントステップと、
第一割当部が、指標ｋ（ｉ）の最大値をＭとして、下記式（１）で定義される値Ｔ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔ＋１とＬのうち小さい方の数のビットを割り当てる第一割当ステップと、
【数９】
2012002348.tif 000011
第二割当部が、上記値Ｔ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうち上記並び替えの前のサンプル番号が小さい方から下記式（２）で定義される個数の各サンプルに対して、１個のビットを割り当てる第二割当ステップと、
【数１０】
2012002348.tif 000012
を含むビット割当方法。
【請求項５】
請求項３又は４に記載されたビット割当方法の各ステップをコンピュータに実行させるためのプログラム。
【請求項６】
請求項３又は４に記載されたビット割当方法の各ステップをコンピュータに実行させるためのプログラムが記録されたコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、音声、音楽等の音信号を符号化する技術に関する。
【背景技術】
【０００２】
音声、音楽等の音信号を符号化する際、符号化すべき情報毎に必要なビット数を計算し、その計算されたビット数でその情報を符号化する技術がある。例えば、非特許文献１に記載されたＩＴＵ−Ｔ標準Ｇ．７１１．１の低域拡張符号化で用いられているビット割当技術が知られている。非特許文献１では、１つのサンプルに割り当て可能な最大ビット数をＬとして、フレーム内のＮ個のサンプルにＭａｘｂｉｔ個のビットを割り当てる。この割り当てたビットで、低域入力信号とＧ．７１１復号信号との差分信号を符号化する。【０００３】
以下、非特許文献１の割り当て方法の概要を説明する。まず、各サンプルｎ（ｎ＝０，１，…，Ｎ−１）に対して、０以上の整数であるｋ（ｎ）を割り当てる。ここでは、サンプルｎのサンプル値をｘ（ｎ）とし、ｉｎｔ（・）を・の小数点以下を切り捨てる関数として、ｋ（ｎ）＝ｉｎｔ（ｌｏｇ|ｘ（ｎ）|）とする。【０００４】
次に、サンプル番号ｎとｋ（ｎ）との組の情報に基づいて、（Ｍ＋Ｌ）×Ｌ個の要素から構成される二次元配列のテーブルを作成する。Ｍはｋ（ｎ）の最大値である。具体的には、ｋ（ｎ）＋２行のサンプル番号が代入されていない最も左の列、ｋ（ｎ）＋１行のサンプル番号が代入されていない最も左の列、及び、ｋ（ｎ）行のサンプル番号が代入されていない最も左の列のそれぞれにサンプル番号ｎを代入する処理を、ｎ＝０，１，…，Ｎ−１のそれぞれについて行う。【０００５】
例えば、図１２に示すように、サンプル番号とそのｋ（ｎ）の値が与えられたとする。この場合、図１３のようなテーブルが作成される。図１２及び図１３の例では、Ｌ＝３、Ｎ＝１０、Ｍａｘｂｉｔ＝１０であるとする。【０００６】
次に、（Ｍ＋Ｌ−１）行から０行まで、０列からＮ−１列の順に要素を確認する。要素にサンプル番号が代入されている場合には、そのサンプル番号のサンプルの割当ビットに１を追加する。この作業を、割当ビットの総数が１０（＝Ｍａｘｂｉｔ）になるまで繰り返す。【０００７】
図１３の例では、太線で囲まれたサンプル番号のサンプルのそれぞれに１ビットが割り当てられる。この結果、図１２の最下欄のようにビットが割り当てられることになる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Rec. ITU-T G.711.1 (03/2008) “7.3.4.1 Generation of bits allocation table”
【発明の概要】
【発明が解決しようとする課題】
【０００９】
非特許文献１に記載された手法によりビットの割り当てを行うためには、（Ｍ＋Ｌ）×Ｎの二次元の配列を用意する必要がある。Ｌ、Ｍ及びＮが大きくなると、配列が大きくなり、メモリの消費量が大きくなるという問題があった。【００１０】
この発明の課題は、メモリの消費量が従来よりも小さいビット割当装置、方法、プログラム及びその記録媒体を提供することである。
【課題を解決するための手段】
【００１１】
この発明の一態様によるビット割当装置によれば、１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てるために、Ｎ個のサンプルのサンプル番号を０，１，…，ｉ，…，Ｎ−１とし、サンプル番号ｉのサンプルに与えられた重要度を表す指標をｋ（ｉ）とし、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタｂｉｔｃｏｕｎｔの初期値を０として、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行う。指標ｋ（ｉ）の最大値をＭとして、Σｔ＝Ｔ−１Ｍｂｉｔｃｏｕｎｔ（ｔ）＞Ｍａｘｂｉｔ≧Σｔ＝ＴＭｂｉｔｃｏｕｎｔ（ｔ）という関係を満たす値Ｔ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔ＋１とＬのうち小さい方の数のビットを割り当てる。値Ｔ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうちＭａｘｂｉｔ−Σｔ＝ＴＭｂｉｔｃｏｕｎｔ（ｔ）個の各サンプルに対して、１個のビットを割り当てる。
この発明の他の一態様によるビット割当装置によれば、１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てるために、Ｎ個のサンプルに与えられた重要度を表す指標に基づいて、Ｎ個のサンプルを重要な順に並び替える。並び替えられたＮ個のサンプルのサンプル番号を新たに０，１，…，ｉ，…，Ｎ−１とし、サンプル番号ｉのサンプルに与えられた重要度を表す指標をｋ（ｉ）とし、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタｂｉｔｃｏｕｎｔの初期値を０として、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行う。指標ｋ（ｉ）の最大値をＭとして、Σｔ＝Ｔ−１Ｍｂｉｔｃｏｕｎｔ（ｔ）＞Ｍａｘｂｉｔ≧Σｔ＝ＴＭｂｉｔｃｏｕｎｔ（ｔ）という関係を満たす値Ｔ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔ＋１とＬのうち小さい方の数のビットを割り当てる。値Ｔ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうち上記並び替え前のサンプル番号が小さい方からＭａｘｂｉｔ−Σｔ＝ＴＭｂｉｔｃｏｕｎｔ（ｔ）個の各サンプルに対して、１個のビットを割り当てる。
【発明の効果】
【００１２】
二次元の配列ではなく一次元の配列を用いてビット割り当てを行うことにより、従来よりもメモリの消費量を小さくすることができる。
【図面の簡単な説明】
【００１３】
【図１】ビット割当装置の例の機能ブロック図。
【図２】ビット割当方法の例を示す流れ図。
【図３】ステップＳ２の例を示す流れ図。
【図４】ステップＳ３の例を示す流れ図。
【図５】ステップＳ４の例を示す流れ図。
【図６】ステップＳ５の例を示す流れ図。
【図７】この発明によるビット割当の例を説明するための図。
【図８】この発明によるビット割当の例を説明するための図。
【図９】この発明によるビット割当の例を説明するための図。
【図１０】この発明によるビット割当の例を説明するための図。
【図１１】この発明によるビット割当の例を説明するための図。
【図１２】従来技術によるビット割当の例を説明するための図。
【図１３】従来技術によるビット割当の例を説明するための図。
【発明を実施するための形態】
【００１４】
以下、この発明の一実施形態のビット割当装置及び方法について、詳細に説明する。
【００１５】
この発明は、１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てる。Ｌ，Ｎ及びＭａｘｂｉｔは、予め定められた正の整数である。
【００１６】
ビット割当装置は、図１に示すように、ソート部１０、ビットカウント部２０、閾値決定部３０、第一割当部４０、第二割当部５０を例えば含む。ビット割当方法は、図２に示すように、ステップＳ１からステップＳ５から例えば構成される。
【００１７】
Ｎ個のサンプルには、それぞれサンプル番号０，１，…，ｎ，…，Ｎ−１が付されている。ｎ＝０，１，…，Ｎ−１として、サンプル番号ｎのサンプルを、サンプルｎと表す。各サンプル０，１，…，ｎ，…，Ｎ−１には、その各サンプルの重要度を表す指標が対応付けられている。ｎ＝０，１，…，Ｎ−１として、サンプルｎの重要度を表す指標をｋ（ｎ）と表す。ｋ（ｎ）は、例えばサンプルｎのサンプル値ｘ（ｎ）の大きさのｌｏｇ値を後述する関数ｆに入力した場合の出力値ｆ（ｌｏｇ|ｘ（ｎ）|）である。ｌｏｇの底は２である。ｆ（・）は、・の小数点以下を切り捨て、切り上げ若しくは四捨五入する関数、又は、・以下の最大の整数を出力する関数である。ｋ（ｎ）は、サンプルｎのサンプル値ｘ（ｎ）のｌｏｇ値が正になるように、ｌｏｇｘ（ｎ）に所定の定数ｃを加算した値を関数ｆに入力した場合の出力値ｆ（ｌｏｇ|ｘ（ｎ）|＋ｃ）であってもよい。
【００１８】
＜ステップＳ１＞
サンプルと指標の組（０，ｋ（０）），（１，ｋ（１）），…，（Ｎ−１，ｋ（Ｎ−１））が用意され、これらがソート部１０に入力される。ソート部１０は、指標ｋ（０），ｋ（１），…，ｋ（Ｎ−１）に基づいて、Ｎ個のサンプル０，１，…，Ｎ−１を重要な順に並び替える（ステップＳ１）。より重要なサンプルに値が大きい指標が与えられている場合には、サンプル０，１，…，Ｎ−１は、指標ｋ（０），ｋ（１），…，ｋ（Ｎ−１）が降順になるように並び替えられる。
【００１９】
並び替えられた後のサンプルには、０，１，…，ｉ，…，Ｎ−１の新たなサンプル番号が付される。新たなサンプル番号ｉのサンプルに付されていた元のサンプル番号は、変数ｐｏｓ（ｉ）に代入される。また、ｋ（ｐｏｓ（ｉ））は、変数ｅｘｐ（ｉ）に代入される。すなわち、ｅｘｐ（ｉ）＝ｋ（ｐｏｓ（ｉ））である。
【００２０】
図７に例示するように、サンプルｎと指標ｋ（ｎ）の組が、（０，５），（１，５），（２，３），（３，３），（４，２），（５，７），（６，６），（７，２），（８，７），（９，５）である場合には、これらのサンプルｎと指標ｋ（ｎ）の組は図８に示すようにソートされる。
【００２１】
少なくとも、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタｂｉｔｃｏｕｎｔが用意される。各ビットカウンタｂｉｔｃｏｕｎｔは、初期値が０であり整数値を取る変数である。ｉ＝０，１，…，Ｎ−１として、指標ｋ（ｉ）に対応するビットカウンタを、ｂｉｔｃｏｕｎｔ（ｋ（ｉ））と表記する。
【００２２】
＜ステップＳ２＞
ビットカウント部２０は、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行う（ステップＳ２）。
【００２３】
ビットカウント部２０は、例えば図３に示すステップＳ２１からステップＳ２７を行うことにより、ステップＳ２を行う。
【００２４】
ビットカウント部２０は、ｉに０を代入する（ステップＳ２１）。
【００２５】
ビットカウント部２０は、ｊに０を代入する（ステップＳ２２）。
【００２６】
ビットカウント部２０は、ビットカウンタｂｉｔｃｏｕｎｔ（ｅｘｐ（ｉ）−ｊ）に１を加算する（ステップＳ２３）。
【００２７】
ビットカウント部２０は、ｊ＝Ｌ−１であるか判定する（ステップＳ２４）。
【００２８】
ｊ＝Ｌ−１でなければ、ビットカウント部２０は、ｊにｊ＋１を代入し（ステップＳ２５）、その後ステップＳ２３に進む。
【００２９】
ｊ＝Ｌ−１であれば、ビットカウント部２０は、ｉ＝Ｎ−１であるか判定する（ステップＳ２６）。
【００３０】
ｊ＝Ｎ−１でなければ、ビットカウント部２０は、ｉにｉ＋１を代入し（ステップＳ２７）、その後ステップＳ２２に進む。
【００３１】
ｊ＝Ｎ−１であれば、ステップＳ２を終了して、後述するステップＳ３に進む。
【００３２】
図７及び図８のようにサンプルと指標の組が与えられて、Ｍａｘｂｉｔ＝１０，Ｌ＝３である場合には、図９の中央に示すように各ビットカウンタｂｉｔｃｏｕｎｔの値が計算される。図９の左は、１を加算するビットカウンタｂｉｔｃｏｕｎｔの位置を表す。図９の左は、ビットカウンタｂｉｔｃｏｕｎｔの計算を説明するためのイメージ図であり、実際にはこのような二次元配列のテーブルは不要である。
【００３３】
＜ステップＳ３＞
閾値決定部３０は、Σｔ＝Ｔｈｒｅｓ−１Ｍｂｉｔｃｏｕｎｔ（ｔ）＞Ｍａｘｂｉｔ≧Σｔ＝ＴｈｒｅｓＭｂｉｔｃｏｕｎｔ（ｔ）という関係を満たす閾値Ｔｈｒｅｓを決定する（ステップＳ３）。Ｍは、指標ｋ（ｉ）の最大値である。決定された閾値Ｔｈｒｅｓについての情報は、第一割当部４０に送られる。
上記関係は、より正確には下記式（１）のように表現することができる。なお、ＴｈｒｅｓをＴと表記することもある。
【数１】
2012002348.tif 000003
【００３４】
閾値決定部３０は、例えば図４に示すステップＳ３１からステップＳ３５を行うことにより、ステップＳ３を行う。
【００３５】
閾値決定部３０は、ｉにＭを代入し、ｂｉｔｓｒｖにＭａｘｂｉｔを代入し、ｂｉｔｓｕｍにｂｉｔｃｏｕｎｔ（Ｍ）を代入する（ステップＳ３１）。ｂｉｔｓｒｖは割り当て可能なビットの数を示す。
【００３６】
閾値決定部３０は、ｉにｉ−１を代入する（ステップＳ３２）。
【００３７】
閾値決定部３０は、ｂｉｔｓｕｍとｂｉｔｓｒｖとを比較する（ステップＳ３３）。
【００３８】
ｂｉｔｓｕｍ＞ｂｉｔｓｒｖでなければ、閾値決定部３０は、ｂｉｔｓｕｍにｂｉｔｓｕｍ＋ｂｉｔｃｏｕｎｔ（ｉ）を代入し（ステップＳ３４）、ステップＳ３２に進む。
【００３９】
ｂｉｔｓｕｍ＞ｂｉｔｓｒｖであれば、閾値決定部３０は、ｂｉｔｓｕｍにｂｉｔｓｕｍ−ｂｉｔｃｏｕｎｔ（ｉ＋１）を代入し、Ｔｈｒｅｓにｉ＋２を代入する（ステップＳ３５）。その後、後述するステップＳ４に進む。
【００４０】
ステップＳ３１からステップＳ３５により得られる閾値Ｔｈｒｅｓは、Σｔ＝Ｔｈｒｅｓ−１Ｍｂｉｔｃｏｕｎｔ（ｔ）＞Ｍａｘｂｉｔ≧Σｔ＝ＴｈｒｅｓＭｂｉｔｃｏｕｎｔ（ｔ）という関係を満たす。
【００４１】
図９の例では、ｉ＝５のときにステップＳ３４で計算されたｂｉｔｓｕｍが１１となり、その後のｉ＝４のときのステップＳ３３ではｂｉｔｓｕｍがＭａｘｂｉｔの値１０を超える。したがって、閾値Ｔｈｒｅｓは、４＋２＝６となる。
【００４２】
なお、図４に破線で示すように、ステップＳ３２の代わりに、ステップＳ３１の後にｉにｉ−１を代入するステップＳ３２１と、ステップＳ３４の後にｉにｉ−１を代入するステップＳ３２２とを閾値決定部３０が実行してもよい。
【００４３】
＜ステップＳ４＞
第一割当部４０は、閾値Ｔｈｒｅｓ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔｈｒｅｓ＋１とＬのうち小さい方の数のビットを割り当てる（ステップＳ４）。
【００４４】
第一割当部４０は、例えば図５に示すステップＳ４１からステップＳ４７を行うことにより、ステップＳ４を行う。
【００４５】
第一割当部４０は、ｉに０を代入し、ｂｉｔａｌｌｏｃ（０），ｂｉｔａｌｌｏｃ（１），…，ｂｉｔａｌｌｏｃ（Ｎ−１）に０を代入する（ステップＳ４１）。ｂｉｔａｌｌｏｃ（ｉ）は、サンプル番号ｉのサンプルに割り当てるビットの数を示す。
【００４６】
第一割当部４０は、ｅｘｐ（ｉ）と閾値Ｔｈｒｅｓとを比較する（ステップＳ４２）。
【００４７】
ｅｘｐ（ｉ）≦Ｔｈｒｅｓ−１であれば、ステップＳ４を終えて、後述するステップＳ６に進む。
【００４８】
ｅｘｐ（ｉ）≦Ｔｈｒｅｓ−１でなければ、第一割当部４０は、ｂｉｔａｌｌｏｃ（ｐｏｓ（ｉ））にｅｘｐ（ｉ）−Ｔｈｒｅｓ＋１とＬのうち小さい方の数を代入する（ステップＳ４３）。言い換えれば、第一割当部４０は、サンプル番号ｐｏｓ（ｉ）のサンプルに、ｍｉｎ（ｅｘｐ（ｉ）−Ｔｈｒｅｓ＋１，Ｌ）個のビットを割り当てる。ｍｉｎ（ｘ１，ｘ２）は、ｘ１とｘ２のうち小さい方の数を出力する関数である。
【００４９】
第一割当部４０は、ｂｉｔｓｒｖにｂｉｔｓｒｖ−ｂｉｔａｌｌｏｃ（ｐｏｓ（ｉ））を代入する（ステップＳ４４）。すなわち、第一割当部４０は、割り当て可能なビットの数ｂｉｔｓｒｖから、サンプル番号ｐｏｓ（ｉ）のサンプルに割り当てたビットの数ｂｉｔａｌｌｏｃ（ｐｏｓ（ｉ））を差し引く。
【００５０】
第一割当部４０は、ｂｉｔａｌｌｏｃ（ｐｏｓ（ｉ））とＬとを比較する（ステップＳ４５）。
【００５１】
ｂｉｔａｌｌｏｃ（ｐｏｓ（ｉ））＜Ｌであれば、第一割当部４０は、ｋ（ｐｏｓ（ｉ））にＴｈｒｅｓ−１を代入する（ステップＳ４６）。その後、ステップＳ４７に進む。
【００５２】
ｂｉｔａｌｌｏｃ（ｐｏｓ（ｉ））＜Ｌでなければ、または、ステップＳ４６の後に、第一割当部４０はｉにｉ＋１を代入する（ステップＳ４７）。その後、ステップＳ４２に進む。
【００５３】
この例では、閾値Ｔｈｒｅｓ以上の値を有する各サンプルｉに対してｅｘｐ（ｉ）−Ｔｈｒｅｓ＋１とＬのうち小さい方の数のビットを割り当てているが、ｅｘｐ（ｉ）＝ｋ（ｐｏｓ（ｉ））であることを考慮すれば、閾値Ｔｈｒｅｓ以上の値を有する各サンプルｉに対してｅｘｐ（ｉ）−Ｔｈｒｅｓ＋１とＬのうち小さい方の数のビットを割り当てることと、閾値Ｔｈｒｅｓ以上の値を有する各サンプルｉに対してｋ（ｉ）−Ｔｈｒｅｓ＋１とＬのうち小さい方の数のビットを割り当てることは同義である。
【００５４】
図７から図９の例に対応する第一割当部４０によるビット割当の例を図１０に示す。図１０のように、閾値Ｔｈｒｅｓ＝６以上の値を有する各サンプルｉに対して、ｅｘｐ（ｉ）−Ｔｈｒｅｓ＋１とＬのうち小さい方の数のビットを割り当てられる。閾値Ｔｈｒｅｓの定義により、ｅｘｐ（ｉ）≧ＴｈｒｅｓであればｂｉｔｓｕｍがＭａｘｂｉｔを超えることはないため、閾値Ｔｈｒｅｓ以上の指標を有する各サンプルｉに対してビットを割り当てても問題はない。
【００５５】
＜ステップＳ５＞
第二割当部５０は、閾値Ｔｈｒｅｓ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうちＭａｘｂｉｔ−Σｔ＝ＴｈｒｅｓＭｂｉｔｃｏｕｎｔ（ｔ）個の各サンプルに対して、１個のビットを割り当てる（ステップＳ５１）。
すなわち、第二割当部５０は、閾値Ｔｈｒｅｓ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうち下記式（２）で定義される個数のサンプルに対して、１個のビットを割り当てる。
【数２】
2012002348.tif 000004
【００５６】
第二割当部５０は、例えば図６に示すステップＳ５１からステップＳ５４を行うことにより、ステップＳ５を行う。
【００５７】
第二割当部５０は、ｉに０を代入する（ステップＳ５１）
第二割当部５０は、ｂｉｔｓｒｖと０とを比較する（ステップＳ５２）。
【００５８】
ｂｉｔｓｒｖ＞０でなければ、第二割当部５０は処理を終える。このときのｂｉｔａｌｌｏｃ（ｉ）の値が、最終的にサンプル番号ｉのサンプルに割り当てるビットの数となる。
【００５９】
ｂｉｔｓｒｖ＞０であれば、第二割当部５０は、ｋ（ｉ）＝Ｔｈｒｅｓ−１かつｂｉｔａｌｌｏｃ（ｉ）＜Ｌであるか判定する（ステップＳ５３）。
【００６０】
ｋ（ｉ）＝Ｔｈｒｅｓ−１かつｂｉｔａｌｌｏｃ（ｉ）＜Ｌであれば、第二割当部５０は、ｂｉｔａｌｌｏｃ（ｉ）にｂｉｔａｌｌｏｃ（ｉ）＋１を代入し、ｂｉｔｓｒｖにｂｉｔｓｒｖ−１を代入する（ステップＳ５４）。その後、ステップＳ５５に進む。
【００６１】
ｋ（ｉ）＝Ｔｈｒｅｓ−１かつｂｉｔａｌｌｏｃ（ｉ）＜Ｌでなければ、または、ステップＳ５４の後に、第二割当部５０はｉにｉ＋１を代入する（ステップＳ５５）。その後、ステップＳ５２に進む。
【００６２】
図７から図１０の例に対応する第二割当部５０によるビット割当の例を図１１に示す。図１１のように、閾値Ｔｈｒｅｓ−１以上の指標（この例では５）を有しまだＬ個のビットが割り当てられていないサンプルのうち並び替え前のサンプル番号が小さい方からＭａｘｂｉｔ−Σｔ＝ＴｈｒｅｓＭｂｉｔｃｏｕｎｔ（ｔ）個（この例では５個）の各サンプルに対して、１個のビットが割り当てられる。
なお、それぞれに１個のビットを割り当てるサンプルは、閾値Ｔｈｒｅｓ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうちのＭａｘｂｉｔ−Σｔ＝ＴｈｒｅｓＭｂｉｔｃｏｕｎｔ（ｔ）個のサンプルであれば、並び替え前のサンプル番号が小さい方からＭａｘｂｉｔ−Σｔ＝ＴｈｒｅｓＭｂｉｔｃｏｕｎｔ（ｔ）個のサンプルでなくてもよい。
【００６３】
このように、従来技術で用いた二次元の配列ではなく、一次元の配列であるビットカウンタｂｉｔｃｏｕｎｔ（ｉ）を用いてビット割り当てを行うことにより、Ｇ．７１１．１の低域拡張符号化で用いられているビット割当と同じビット割り当て結果を実現しつつ、従来よりもメモリの消費量を小さくすることができる。その効果は、Ｍ，Ｌ，Ｎの値が大きいほど大きい。
【００６４】
ビット割当装置及び方法は、コンピュータによって実現することができる。この場合、ビット割当装置の各部、及び、ビット割当方法の各ステップはプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、ビット割当装置の各部、及び、ビット割当方法の各ステップが、コンピュータ上で実現される。
【００６５】
このプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００６６】
この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【００６７】
例えば、上記の実施形態では、ステップＳ１においてサンプルを降順にソートしてから、ステップＳ２及びステップＳ３の処理により閾値Ｔｈｒｅｓを計算しているが、このステップＳ１のソートは行わなくてもよい。
【符号の説明】
【００６８】
２０ ビットカウント部
３０ 閾値決定部
４０ 第一割当部
５０ 第二割当部
【図１】
2012002348.tif 000013
【図２】
2012002348.tif 000014
【図３】
2012002348.tif 000015
【図４】
2012002348.tif 000016
【図５】
2012002348.tif 000017
【図６】
2012002348.tif 000018
【図７】
2012002348.tif 000019
【図８】
2012002348.tif 000020
【図９】
2012002348.tif 000021
【図１０】
2012002348.tif 000022
【図１１】
2012002348.tif 000023
【図１２】
2012002348.tif 000024
【図１３】
2012002348.tif 000025
【手続補正書】
【提出日】平成24年9月21日(2012.9.21)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
この発明の一態様によるビット割当装置によれば、１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てるために、Ｎ個のサンプルのサンプル番号を０，１，…，ｉ，…，Ｎ−１とし、サンプル番号ｉのサンプルに与えられた重要度を表す指標をｋ（ｉ）とし、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタの初期値を０として、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行う。指標ｋ（ｉ）の最大値をＭとして、Σｔ＝Ｔ−１Ｍｂｉｔｃｏｕｎｔ（ｔ）＞Ｍａｘｂｉｔ≧Σｔ＝ＴＭｂｉｔｃｏｕｎｔ（ｔ）という関係を満たす値Ｔ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔ＋１とＬのうち小さい方の数のビットを割り当てる。値Ｔ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうちＭａｘｂｉｔ−Σｔ＝ＴＭｂｉｔｃｏｕｎｔ（ｔ）個の各サンプルに対して、１個のビットを割り当てる。
この発明の他の一態様によるビット割当装置によれば、１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てるために、Ｎ個のサンプルに与えられた重要度を表す指標に基づいて、Ｎ個のサンプルを重要な順に並び替える。並び替えられたＮ個のサンプルのサンプル番号を新たに０，１，…，ｉ，…，Ｎ−１とし、サンプル番号ｉのサンプルに与えられた重要度を表す指標をｋ（ｉ）とし、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタｂｉｔｃｏｕｎｔの初期値を０として、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行う。指標ｋ（ｉ）の最大値をＭとして、Σｔ＝Ｔ−１Ｍｂｉｔｃｏｕｎｔ（ｔ）＞Ｍａｘｂｉｔ≧Σｔ＝ＴＭｂｉｔｃｏｕｎｔ（ｔ）という関係を満たす値Ｔ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔ＋１とＬのうち小さい方の数のビットを割り当てる。値Ｔ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうち上記並び替え前のサンプル番号が小さい方からＭａｘｂｉｔ−Σｔ＝ＴＭｂｉｔｃｏｕｎｔ（ｔ）個の各サンプルに対して、１個のビットを割り当てる。
この発明の他の一態様によるビット割当装置によれば、１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てるために、Ｎ個のサンプルに与えられた重要度を表す指標に基づいて、Ｎ個のサンプルを重要な順に並び替える。並び替えられたＮ個のサンプルのサンプル番号を新たに０，１，…，ｉ，…，Ｎ−１とし、サンプル番号ｉのサンプルに与えられた重要度を表す指標をｋ（ｉ）とし、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタの初期値を０として、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行う。指標ｋ（ｉ）の最大値をＭとし、割り当て可能ビット数ｂｉｔｓｒｖの初期値をＭａｘｂｉｔとして、Σｔ＝Ｔ−１Ｍｂｉｔｃｏｕｎｔ（ｔ）＞Ｍａｘｂｉｔ≧Σｔ＝ＴＭｂｉｔｃｏｕｎｔ（ｔ）という関係を満たす値Ｔ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔ＋１とＬのうち小さい方の数のビットを割り当て、割り当て可能ビット数ｂｉｔｓｒｖから割り当てたビット数を差し引く。並び替え前のサンプル番号が小さい方から順に、割り当て可能ビット数ｂｉｔｓｒｖが０より大きく、かつ、値Ｔ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルである場合に、各該サンプルに対する割り当てビット数に１を加算し、割り当て可能ビット数ｂｉｔｓｒｖから１を差し引く処理を行う。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てるビット割当装置において、
上記Ｎ個のサンプルのサンプル番号を０，１，…，ｉ，…，Ｎ−１とし、サンプル番号ｉのサンプルに与えられた重要度を表す指標をｋ（ｉ）とし、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタの初期値を０として、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行うビットカウント部と、
指標ｋ（ｉ）の最大値をＭとして、下記式（１）で定義される値Ｔ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔ＋１とＬのうち小さい方の数のビットを割り当てる第一割当部と、
【数３】
2012002348.tif 000026
上記値Ｔ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうち下記式（２）で定義される個数の各サンプルに対して、１個のビットを割り当てる第二割当部と、
【数４】
2012002348.tif 000027
を含むビット割当装置。
【請求項２】
１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てるビット割当装置において、
上記Ｎ個のサンプルに与えられた重要度を表す指標に基づいて、上記Ｎ個のサンプルを重要な順に並び替えるソート部と、
上記並び替えられたＮ個のサンプルのサンプル番号を新たに０，１，…，ｉ，…，Ｎ−１とし、サンプル番号ｉのサンプルに与えられた重要度を表す指標をｋ（ｉ）とし、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタの初期値を０として、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行うビットカウント部と、
指標ｋ（ｉ）の最大値をＭとして、下記式（１）で定義される値Ｔ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔ＋１とＬのうち小さい方の数のビットを割り当てる第一割当部と、
【数５】
2012002348.tif 000028
上記値Ｔ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうち上記並び替えの前のサンプル番号が小さい方から下記式（２）で定義される個数の各サンプルに対して、１個のビットを割り当てる第二割当部と、
【数６】
2012002348.tif 000029
を含むビット割当装置。
【請求項３】
１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てるビット割当装置において、
上記Ｎ個のサンプルに与えられた重要度を表す指標に基づいて、上記Ｎ個のサンプルを重要な順に並び替えるソート部と、
上記並び替えられたＮ個のサンプルのサンプル番号を新たに０，１，…，ｉ，…，Ｎ−１とし、サンプル番号ｉのサンプルに与えられた重要度を表す指標をｋ（ｉ）とし、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタの初期値を０として、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行うビットカウント部と、
指標ｋ（ｉ）の最大値をＭとし、割り当て可能ビット数ｂｉｔｓｒｖの初期値をＭａｘｂｉｔとして、下記式（１）で定義される値Ｔ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔ＋１とＬのうち小さい方の数のビットを割り当て、割り当て可能ビット数ｂｉｔｓｒｖから割り当てたビット数を差し引く第一割当部と、
【数５】
2012002348.tif 000030
上記並び替え前のサンプル番号が小さい方から順に、割り当て可能ビット数ｂｉｔｓｒｖが０より大きく、かつ、上記値Ｔ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルである場合に、各該サンプルに対する割り当てビット数に１を加算し、割り当て可能ビット数ｂｉｔｓｒｖから１を差し引く処理を行う第二割当部と、
を含むビット割当装置。
【請求項４】
１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てるビット割当方法において、
ビットカウント部が、上記Ｎ個のサンプルのサンプル番号を０，１，…，ｉ，…，Ｎ−１とし、サンプル番号ｉのサンプルに与えられた重要度を表す指標をｋ（ｉ）とし、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタの初期値を０として、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行うビットカウントステップと、
第一割当部が、指標ｋ（ｉ）の最大値をＭとして、下記式（１）で定義される値Ｔ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔ＋１とＬのうち小さい方の数のビットを割り当てる第一割当ステップと、
【数７】
2012002348.tif 000031
第二割当部が、上記値Ｔ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうち下記式（２）で定義される個数の各サンプルに対して、１個のビットを割り当てる第二割当ステップと、
【数８】
2012002348.tif 000032
を含むビット割当方法。
【請求項５】
１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てるビット割当方法において、
ソート部が、上記Ｎ個のサンプルに与えられた重要度を表す指標に基づいて、上記Ｎ個のサンプルを重要な順に並び替えるソートステップと、
ビットカウント部が、上記並び替えられたＮ個のサンプルのサンプル番号を新たに０，１，…，ｉ，…，Ｎ−１とし、サンプル番号ｉのサンプルに与えられた重要度を表す指標をｋ（ｉ）とし、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタの初期値を０として、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行うビットカウントステップと、
第一割当部が、指標ｋ（ｉ）の最大値をＭとして、下記式（１）で定義される値Ｔ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔ＋１とＬのうち小さい方の数のビットを割り当てる第一割当ステップと、
【数９】
2012002348.tif 000033
第二割当部が、上記値Ｔ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルのうち上記並び替えの前のサンプル番号が小さい方から下記式（２）で定義される個数の各サンプルに対して、１個のビットを割り当てる第二割当ステップと、
【数１０】
2012002348.tif 000034
を含むビット割当方法。
【請求項６】
１つのサンプルに割り当て可能な最大ビット数をＬとして、Ｎ個のサンプルにＭａｘｂｉｔ個のビットを割り当てるビット割当方法において、
ソート部が、上記Ｎ個のサンプルに与えられた重要度を表す指標に基づいて、上記Ｎ個のサンプルを重要な順に並び替えるソートステップと、
ビットカウント部が、上記並び替えられたＮ個のサンプルのサンプル番号を新たに０，１，…，ｉ，…，Ｎ−１とし、サンプル番号ｉのサンプルに与えられた重要度を表す指標をｋ（ｉ）とし、指標ｋ（ｉ）の取り得る値の数＋Ｌ−１個のビットカウンタの初期値を０として、指標ｋ（ｉ），…，ｋ（ｉ）−（Ｌ−１）に対応する各ビットカウンタｂｉｔｃｏｕｎｔ（ｋ（ｉ）），…，ｂｉｔｃｏｕｎｔ（ｋ（ｉ）−（Ｌ−１））に１を加算する処理を、ｉ＝０，１，…，Ｎ−１のそれぞれに対して行うビットカウントステップと、
第一割当部が、指標ｋ（ｉ）の最大値をＭとし、割り当て可能ビット数ｂｉｔｓｒｖの初期値をＭａｘｂｉｔとして、下記式（１）で定義される値Ｔ以上の指標を有する各サンプルｉに対して、ｋ（ｉ）−Ｔ＋１とＬのうち小さい方の数のビットを割り当て、割り当て可能ビット数ｂｉｔｓｒｖから割り当てたビット数を差し引く第一割当ステップと、
【数５】
2012002348.tif 000035
第二割当部が、上記並び替え前のサンプル番号が小さい方から順に、割り当て可能ビット数ｂｉｔｓｒｖが０より大きく、かつ、上記値Ｔ−１以上の指標を有しまだＬ個のビットが割り当てられていないサンプルである場合に、各該サンプルに対する割り当てビット数に１を加算し、割り当て可能ビット数ｂｉｔｓｒｖから１を差し引く処理を行う第二割当ステップと、
を含むビット割当方法。
【請求項７】
請求項４から６の何れかに記載されたビット割当方法の各ステップをコンピュータに実行させるためのプログラム。
【請求項８】
請求項４から６の何れかに記載されたビット割当方法の各ステップをコンピュータに実行させるためのプログラムが記録されたコンピュータ読み取り可能な記録媒体。
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】図３
【補正方法】変更
【補正の内容】
【図３】
2012002348.tif 000036
【国際調査報告】
2012002348.tif 000037
2012002348.tif 000038
2012002348.tif 000039
2012002348.tif 000040