"1つのサンプルに割り当て可能な最大ビット数をLとして、N個のサンプルにMaxbit個のビットを割り当てるビット割当装置において、上記N個のサンプルのサンプル番号を0,1,...,i,...,N-1とし、サンプル番号iのサンプルに与えられた重要度を表す指標をkiとし、指標kiの取り得る値の数L-1個のビットカウンタbitcountの初期値を0として、指標ki,...,ki-L-1に対応する各ビットカウンタbitcountki,...,bitcountki-L-1に1を加算する処理を、i=0,1,...,N-1のそれぞれに対して行うビットカウント部と、指標kiの最大値をMとして、下記式1で定義される値T以上の指標を有する各サンプルiに対して、ki-T1とLのうち小さい方の数のビットを割り当てる第一割当部と、上記値T-1以上の指標を有しまだL個のビットが割り当てられていないサンプルのうち下記式2で定義される個数の各サンプルに対して、1個のビットを割り当てる第二割当部と、を含むビット割当装置。1つのサンプルに割り当て可能な最大ビット数をLとして、N個のサンプルにMaxbit個のビットを割り当てるビット割当装置において、上記N個のサンプルに与えられた重要度を表す指標に基づいて、上記N個のサンプルを重要な順に並び替えるソート部と、上記並び替えられたN個のサンプルのサンプル番号を新たに0,1,...,i,...,N-1とし、サンプル番号iのサンプルに与えられた重要度を表す指標をkiとし、指標kiの取り得る値の数L-1個のビットカウンタbitcountの初期値を0として、指標ki,...,ki-L-1に対応する各ビットカウンタbitcountki,...,bitcountki-L-1に1を加算する処理を、i=0,1,...,N-1のそれぞれに対して行うビットカウント部と、指標kiの最大値をMとして、下記式1で定義される値T以上の指標を有する各サンプルiに対して、ki-T1とLのうち小さい方の数のビットを割り当てる第一割当部と、上記値T-1以上の指標を有しまだL個のビットが割り当てられていないサンプルのうち上記並び替えの前のサンプル番号が小さい方から下記式2で定義される個数の各サンプルに対して、1個のビットを割り当てる第二割当部と、を含むビット割当装置。1つのサンプルに割り当て可能な最大ビット数をLとして、N個のサンプルにMaxbit個のビットを割り当てるビット割当方法において、ビットカウント部が、上記N個のサンプルのサンプル番号を0,1,...,i,...,N-1とし、サンプル番号iのサンプルに与えられた重要度を表す指標をkiとし、指標kiの取り得る値の数L-1個のビットカウンタbitcountの初期値を0として、指標ki,...,ki-L-1に対応する各ビットカウンタbitcountki,...,bitcountki-L-1に1を加算する処理を、i=0,1,...,N-1のそれぞれに対して行うビットカウントステップと、第一割当部が、指標kiの最大値をMとして、下記式1で定義される値T以上の指標を有する各サンプルiに対して、ki-T1とLのうち小さい方の数のビットを割り当てる第一割当ステップと、第二割当部が、上記値T-1以上の指標を有しまだL個のビットが割り当てられていないサンプルのうち下記式2で定義される個数の各サンプルに対して、1個のビットを割り当てる第二割当ステップと、を含むビット割当方法。1つのサンプルに割り当て可能な最大ビット数をLとして、N個のサンプルにMaxbit個のビットを割り当てるビット割当方法において、ソート部が、上記N個のサンプルに与えられた重要度を表す指標に基づいて、上記N個のサンプルを重要な順に並び替えるソートステップと、ビットカウント部が、上記並び替えられたN個のサンプルのサンプル番号を新たに0,1,...,i,...,N-1とし、サンプル番号iのサンプルに与えられた重要度を表す指標をkiとし、指標kiの取り得る値の数L-1個のビットカウンタbitcountの初期値を0として、指標ki,...,ki-L-1に対応する各ビットカウンタbitcountki,...,bitcountki-L-1に1を加算する処理を、i=0,1,...,N-1のそれぞれに対して行うビットカウントステップと、第一割当部が、指標kiの最大値をMとして、下記式1で定義される値T以上の指標を有する各サンプルiに対して、ki-T1とLのうち小さい方の数のビットを割り当てる第一割当ステップと、第二割当部が、上記値T-1以上の指標を有しまだL個のビットが割り当てられていないサンプルのうち上記並び替えの前のサンプル番号が小さい方から下記式2で定義される個数の各サンプルに対して、1個のビットを割り当てる第二割当ステップと、を含むビット割当方法。請求項3又は4に記載されたビット割当方法の各ステップをコンピュータに実行させるためのプログラム。請求項3又は4に記載されたビット割当方法の各ステップをコンピュータに実行させるためのプログラムが記録されたコンピュータ読み取り可能な記録媒体。非特許文献1に記載された手法によりビットの割り当てを行うためには、ML×Nの二次元の配列を用意する必要がある。L、M及びNが大きくなると、配列が大きくなり、メモリの消費量が大きくなるという問題があった。この発明の課題は、メモリの消費量が従来よりも小さいビット割当装置、方法、プログラム及びその記録媒体を提供することである。この発明の一態様によるビット割当装置によれば、1つのサンプルに割り当て可能な最大ビット数をLとして、N個のサンプルにMaxbit個のビットを割り当てるために、N個のサンプルのサンプル番号を0,1,...,i,...,N-1とし、サンプル番号iのサンプルに与えられた重要度を表す指標をkiとし、指標kiの取り得る値の数L-1個のビットカウンタbitcountの初期値を0として、指標ki,...,ki-L-1に対応する各ビットカウンタbitcountki,...,bitcountki-L-1に1を加算する処理を、i=0,1,...,N-1のそれぞれに対して行う。指標kiの最大値をMとして、Σt=T-1Mbitcountt>Maxbit≧Σt=TMbitcounttという関係を満たす値T以上の指標を有する各サンプルiに対して、ki-T1とLのうち小さい方の数のビットを割り当てる。値T-1以上の指標を有しまだL個のビットが割り当てられていないサンプルのうちMaxbit-Σt=TMbitcountt個の各サンプルに対して、1個のビットを割り当てる。この発明の他の一態様によるビット割当装置によれば、1つのサンプルに割り当て可能な最大ビット数をLとして、N個のサンプルにMaxbit個のビットを割り当てるために、N個のサンプルに与えられた重要度を表す指標に基づいて、N個のサンプルを重要な順に並び替える。並び替えられたN個のサンプルのサンプル番号を新たに0,1,...,i,...,N-1とし、サンプル番号iのサンプルに与えられた重要度を表す指標をkiとし、指標kiの取り得る値の数L-1個のビットカウンタbitcountの初期値を0として、指標ki,...,ki-L-1に対応する各ビットカウンタbitcountki,...,bitcountki-L-1に1を加算する処理を、i=0,1,...,N-1のそれぞれに対して行う。指標kiの最大値をMとして、Σt=T-1Mbitcountt>Maxbit≧Σt=TMbitcounttという関係を満たす値T以上の指標を有する各サンプルiに対して、ki-T1とLのうち小さい方の数のビットを割り当てる。値T-1以上の指標を有しまだL個のビットが割り当てられていないサンプルのうち上記並び替え前のサンプル番号が小さい方からMaxbit-Σt=TMbitcountt個の各サンプルに対して、1個のビットを割り当てる。二次元の配列ではなく一次元の配列を用いてビット割り当てを行うことにより、従来よりもメモリの消費量を小さくすることができる。以下、この発明の一実施形態のビット割当装置及び方法について、詳細に説明する。この発明は、1つのサンプルに割り当て可能な最大ビット数をLとして、N個のサンプルにMaxbit個のビットを割り当てる。L,N及びMaxbitは、予め定められた正の整数である。ビット割当装置は、図1に示すように、ソート部10、ビットカウント部20、閾値決定部30、第一割当部40、第二割当部50を例えば含む。ビット割当方法は、図2に示すように、ステップS1からステップS5から例えば構成される。N個のサンプルには、それぞれサンプル番号0,1,...,n,...,N-1が付されている。n=0,1,...,N-1として、サンプル番号nのサンプルを、サンプルnと表す。各サンプル0,1,...,n,...,N-1には、その各サンプルの重要度を表す指標が対応付けられている。n=0,1,...,N-1として、サンプルnの重要度を表す指標をknと表す。knは、例えばサンプルnのサンプル値xnの大きさのlog値を後述する関数fに入力した場合の出力値flogxnである。logの底は2である。fは、の小数点以下を切り捨て、切り上げ若しくは四捨五入する関数、又は、以下の最大の整数を出力する関数である。knは、サンプルnのサンプル値xnのlog値が正になるように、logxnに所定の定数cを加算した値を関数fに入力した場合の出力値flogxncであってもよい。<ステップS1>サンプルと指標の組0,k0,1,k1,...,N-1,kN-1が用意され、これらがソート部10に入力される。ソート部10は、指標k0,k1,...,kN-1に基づいて、N個のサンプル0,1,...,N-1を重要な順に並び替えるステップS1。より重要なサンプルに値が大きい指標が与えられている場合には、サンプル0,1,...,N-1は、指標k0,k1,...,kN-1が降順になるように並び替えられる。並び替えられた後のサンプルには、0,1,...,i,...,N-1の新たなサンプル番号が付される。新たなサンプル番号iのサンプルに付されていた元のサンプル番号は、変数posiに代入される。また、kposiは、変数expiに代入される。すなわち、expi=kposiである。図7に例示するように、サンプルnと指標knの組が、0,5,1,5,2,3,3,3,4,2,5,7,6,6,7,2,8,7,9,5である場合には、これらのサンプルnと指標knの組は図8に示すようにソートされる。少なくとも、指標kiの取り得る値の数L-1個のビットカウンタbitcountが用意される。各ビットカウンタbitcountは、初期値が0であり整数値を取る変数である。i=0,1,...,N-1として、指標kiに対応するビットカウンタを、bitcountkiと表記する。<ステップS2>ビットカウント部20は、指標ki,...,ki-L-1に対応する各ビットカウンタbitcountki,...,bitcountki-L-1に1を加算する処理を、i=0,1,...,N-1のそれぞれに対して行うステップS2。ビットカウント部20は、例えば図3に示すステップS21からステップS27を行うことにより、ステップS2を行う。ビットカウント部20は、iに0を代入するステップS21。ビットカウント部20は、jに0を代入するステップS22。ビットカウント部20は、ビットカウンタbitcountexpi-jに1を加算するステップS23。ビットカウント部20は、j=L-1であるか判定するステップS24。j=L-1でなければ、ビットカウント部20は、jにj1を代入しステップS25、その後ステップS23に進む。j=L-1であれば、ビットカウント部20は、i=N-1であるか判定するステップS26。j=N-1でなければ、ビットカウント部20は、iにi1を代入しステップS27、その後ステップS22に進む。j=N-1であれば、ステップS2を終了して、後述するステップS3に進む。図7及び図8のようにサンプルと指標の組が与えられて、Maxbit=10,L=3である場合には、図9の中央に示すように各ビットカウンタbitcountの値が計算される。図9の左は、1を加算するビットカウンタbitcountの位置を表す。図9の左は、ビットカウンタbitcountの計算を説明するためのイメージ図であり、実際にはこのような二次元配列のテーブルは不要である。<ステップS3>閾値決定部30は、Σt=Thres-1Mbitcountt>Maxbit≧Σt=ThresMbitcounttという関係を満たす閾値Thresを決定するステップS3。Mは、指標kiの最大値である。決定された閾値Thresについての情報は、第一割当部40に送られる。上記関係は、より正確には下記式1のように表現することができる。なお、ThresをTと表記することもある。閾値決定部30は、例えば図4に示すステップS31からステップS35を行うことにより、ステップS3を行う。閾値決定部30は、iにMを代入し、bitsrvにMaxbitを代入し、bitsumにbitcountMを代入するステップS31。bitsrvは割り当て可能なビットの数を示す。閾値決定部30は、iにi-1を代入するステップS32。閾値決定部30は、bitsumとbitsrvとを比較するステップS33。bitsum>bitsrvでなければ、閾値決定部30は、bitsumにbitsumbitcountiを代入しステップS34、ステップS32に進む。bitsum>bitsrvであれば、閾値決定部30は、bitsumにbitsum-bitcounti1を代入し、Thresにi2を代入するステップS35。その後、後述するステップS4に進む。ステップS31からステップS35により得られる閾値Thresは、Σt=Thres-1Mbitcountt>Maxbit≧Σt=ThresMbitcounttという関係を満たす。図9の例では、i=5のときにステップS34で計算されたbitsumが11となり、その後のi=4のときのステップS33ではbitsumがMaxbitの値10を超える。したがって、閾値Thresは、42=6となる。なお、図4に破線で示すように、ステップS32の代わりに、ステップS31の後にiにi-1を代入するステップS321と、ステップS34の後にiにi-1を代入するステップS322とを閾値決定部30が実行してもよい。<ステップS4>第一割当部40は、閾値Thres以上の指標を有する各サンプルiに対して、ki-Thres1とLのうち小さい方の数のビットを割り当てるステップS4。第一割当部40は、例えば図5に示すステップS41からステップS47を行うことにより、ステップS4を行う。第一割当部40は、iに0を代入し、bitalloc0,bitalloc1,...,bitallocN-1に0を代入するステップS41。bitallociは、サンプル番号iのサンプルに割り当てるビットの数を示す。第一割当部40は、expiと閾値Thresとを比較するステップS42。expi≦Thres-1であれば、ステップS4を終えて、後述するステップS6に進む。expi≦Thres-1でなければ、第一割当部40は、bitallocposiにexpi-Thres1とLのうち小さい方の数を代入するステップS43。言い換えれば、第一割当部40は、サンプル番号posiのサンプルに、minexpi-Thres1,L個のビットを割り当てる。minx1,x2は、x1とx2のうち小さい方の数を出力する関数である。第一割当部40は、bitsrvにbitsrv-bitallocposiを代入するステップS44。すなわち、第一割当部40は、割り当て可能なビットの数bitsrvから、サンプル番号posiのサンプルに割り当てたビットの数bitallocposiを差し引く。第一割当部40は、bitallocposiとLとを比較するステップS45。bitallocposi<Lであれば、第一割当部40は、kposiにThres-1を代入するステップS46。その後、ステップS47に進む。bitallocposi<Lでなければ、または、ステップS46の後に、第一割当部40はiにi1を代入するステップS47。その後、ステップS42に進む。この例では、閾値Thres以上の値を有する各サンプルiに対してexpi-Thres1とLのうち小さい方の数のビットを割り当てているが、expi=kposiであることを考慮すれば、閾値Thres以上の値を有する各サンプルiに対してexpi-Thres1とLのうち小さい方の数のビットを割り当てることと、閾値Thres以上の値を有する各サンプルiに対してki-Thres1とLのうち小さい方の数のビットを割り当てることは同義である。図7から図9の例に対応する第一割当部40によるビット割当の例を図10に示す。図10のように、閾値Thres=6以上の値を有する各サンプルiに対して、expi-Thres1とLのうち小さい方の数のビットを割り当てられる。閾値Thresの定義により、expi≧ThresであればbitsumがMaxbitを超えることはないため、閾値Thres以上の指標を有する各サンプルiに対してビットを割り当てても問題はない。<ステップS5>第二割当部50は、閾値Thres-1以上の指標を有しまだL個のビットが割り当てられていないサンプルのうちMaxbit-Σt=ThresMbitcountt個の各サンプルに対して、1個のビットを割り当てるステップS51。すなわち、第二割当部50は、閾値Thres-1以上の指標を有しまだL個のビットが割り当てられていないサンプルのうち下記式2で定義される個数のサンプルに対して、1個のビットを割り当てる。第二割当部50は、例えば図6に示すステップS51からステップS54を行うことにより、ステップS5を行う。第二割当部50は、iに0を代入するステップS51第二割当部50は、bitsrvと0とを比較するステップS52。bitsrv>0でなければ、第二割当部50は処理を終える。このときのbitallociの値が、最終的にサンプル番号iのサンプルに割り当てるビットの数となる。bitsrv>0であれば、第二割当部50は、ki=Thres-1かつbitalloci<Lであるか判定するステップS53。ki=Thres-1かつbitalloci<Lであれば、第二割当部50は、bitallociにbitalloci1を代入し、bitsrvにbitsrv-1を代入するステップS54。その後、ステップS55に進む。ki=Thres-1かつbitalloci<Lでなければ、または、ステップS54の後に、第二割当部50はiにi1を代入するステップS55。その後、ステップS52に進む。図7から図10の例に対応する第二割当部50によるビット割当の例を図11に示す。図11のように、閾値Thres-1以上の指標この例では5を有しまだL個のビットが割り当てられていないサンプルのうち並び替え前のサンプル番号が小さい方からMaxbit-Σt=ThresMbitcountt個この例では5個の各サンプルに対して、1個のビットが割り当てられる。なお、それぞれに1個のビットを割り当てるサンプルは、閾値Thres-1以上の指標を有しまだL個のビットが割り当てられていないサンプルのうちのMaxbit-Σt=ThresMbitcountt個のサンプルであれば、並び替え前のサンプル番号が小さい方からMaxbit-Σt=ThresMbitcountt個のサンプルでなくてもよい。このように、従来技術で用いた二次元の配列ではなく、一次元の配列であるビットカウンタbitcountiを用いてビット割り当てを行うことにより、G.711.1の低域拡張符号化で用いられているビット割当と同じビット割り当て結果を実現しつつ、従来よりもメモリの消費量を小さくすることができる。その効果は、M,L,Nの値が大きいほど大きい。ビット割当装置及び方法は、コンピュータによって実現することができる。この場合、ビット割当装置の各部、及び、ビット割当方法の各ステップはプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、ビット割当装置の各部、及び、ビット割当方法の各ステップが、コンピュータ上で実現される。このプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。例えば、上記の実施形態では、ステップS1においてサンプルを降順にソートしてから、ステップS2及びステップS3の処理により閾値Thresを計算しているが、このステップS1のソートは行わなくてもよい。"