(57)【特許請求の範囲】
【請求項１】
入力された２進数を記数法変換してn進数（nは、２の冪乗で表されない３以上の整数とする）を出力する記数法変換装置であり、
Lをnの２進法表記におけるビット数とし、mを1≦m<Lを満たす整数とし、
予め、0以上2L未満の2L個の整数を分類して得られる要素数が同じ2m個の集合S0，…，S2^m-1と（ただし、これら集合族には、n以上2L-1以下の各整数を含む集合SMAXが含まれるとする）、2m個の単射写像Bi：[0,2L-1]→[0,2L-1]（i=0,…,2m-1）（ただし、記号[a,b]はa以上b以下のb-a+1個の整数を要素に持つ集合であり、写像Bi（i=0,…,2m-1）は、[0,2L-1]-Siの要素をすべて[0,2L-1]-SMAXに写す、という性質を満たすものとする）が定められており、
２進数であるL(2m-1)ビット以下のバイナリデータDを連続するLビットごとに分割し、z個（z≦2m-1）のデータ区間a0,…,az-1（ただし、ai（i=0,…,z-1）は１０進法で0以上2L未満の数である）を得る分割部と、
上記ai（i=0,…,z-1）のいずれの値も属さない集合Se（e∈{0,…,2m-1}）に対応する上記単射写像Beを特定する制御部と、
各上記a0,…,az-1の上記単射写像Beによる像Be(a0),…,Be(az-1)を求め、当該単射写像Beを一意に識別する値ID(e)と像Be(a0),…,Be(az-1)との組を上記記数法変換されたn進数として出力する変換部と
を含む記数法変換装置。
【請求項２】
請求項１に記載の記数法変換装置であって、
値a（a∈{a0,…,az-1}）の上記単射写像Bi（i=0,…,2m-1）による像Bi(a)と上記ID(e)を、Ci=((i+1) mod 2m)<<(L-m)として、Bi(a)=(a - Ci) mod n'、ID(e)=Ceとする（ただし、n'はn≦n'<n+2L-mを満たす整数、記号<<は左ビットシフト演算である）
ことを特徴とする記数法変換装置。
【請求項３】
請求項１または請求項２に記載の記数法変換装置であって、
上記入力された２進数であるバイナリデータのビット長がL(2m-1)ビットよりも長い場合、上記分割部が、当該バイナリデータのビット長がL(2m-1)ビットの整数倍ならば当該バイナリデータをL(2m-1)ビットの一つ以上のバイナリデータに区分し、当該バイナリデータのビット長がL(2m-1)ビットの整数倍でないならば当該バイナリデータをL(2m-1)ビットのバイナリデータとL(2m-1)ビットよりも短いバイナリデータに区分し、これにより得られた各区分のバイナリデータを上記バイナリデータDと看做して、各区分につき上記データ区間を得て、
上記制御部は、上記区分ごとに上記単射写像Beを特定し、
上記変換部は、上記区分ごとに得られた上記組を連結したものを、入力されたバイナリデータに対応するn進数として出力する
ことを特徴とする記数法変換装置。
【請求項４】
請求項１から請求項３のいずれかに記載の記数法変換装置（以下、n進数記数法変換装置という）によって得られたデータID(e),b0,…,bk-2（ただし、kは2≦kを満たす整数とする）からバイナリデータを出力する記数法変換装置であり、
Lをn（nは、２の冪乗で表されない３以上の整数とする）の２進法表記におけるビット数とし、mを1≦m<Lを満たす整数とし、
0以上2L未満の2L個の整数を分類して得られる要素数が同じ2m個の集合S0，…，S2^m-1（ただし、これら集合族には、n以上2L-1以下の各整数を含む集合SMAXが含まれるとする）を、上記データを生成した上記n進数記数法変換装置が用いた2m個の上記集合S0，…，S2^m-1とし、2m個の単射写像Bi：[0,2L-1]→[0,2L-1]（i=0,…,2m-1）（ただし、記号[a,b]はa以上b以下のb-a+1個の整数を要素に持つ集合であり、写像Bi（i=0,…,2m-1）は、[0,2L-1]-Siの要素をすべて[0,2L-1]-SMAXに写す、という性質を満たすものとする）を、上記データを生成した上記n進数記数法変換装置が用いた2m個の上記単射写像Bi：[0,2L-1]→[0,2L-1]（i=0,…,2m-1）とし、
上記ID(e)から単射写像Beを特定し、各上記bi(i=0,…,k-2)の逆写像Be-1による像Be-1(bi)を求め2L未満の数に変換する逆変換部と、
Be-1(b0),…,Be-1(bk-2)をビット連結して上記バイナリデータを出力する結合部と
を含む記数法変換装置。
【請求項５】
入力された２進数を記数法変換してn進数（nは、２の冪乗で表されない３以上の整数とする）を出力する記数法変換方法であり、
Lをnの２進法表記におけるビット数とし、mを1≦m<Lを満たす整数とし、
予め、0以上2L未満の2L個の整数を分類して得られる要素数が同じ2m個の集合S0，…，S2^m-1と（ただし、これら集合族には、n以上2L-1以下の各整数を含む集合SMAXが含まれるとする）、2m個の単射写像Bi：[0,2L-1]→[0,2L-1]（i=0,…,2m-1）（ただし、記号[a,b]はa以上b以下のb-a+1個の整数を要素に持つ集合であり、写像Bi（i=0,…,2m-1）は、[0,2L-1]-Siの要素をすべて[0,2L-1]-SMAXに写す、という性質を満たすものとする）が定められており、
分割部が、２進数であるL(2m-1)ビット以下のバイナリデータDを連続するLビットごとに分割し、z個（z≦2m-1）のデータ区間a0,…,az-1（ただし、ai（i=0,…,z-1）は１０進法で0以上2L未満の数である）を得る分割ステップと、
制御部が、上記ai（i=0,…,z-1）のいずれの値も属さない集合Se（e∈{0,…,2m-1}）に対応する上記単射写像Beを特定する制御ステップと、
変換部が、各上記a0,…,az-1の上記単射写像Beによる像Be(a0),…,Be(az-1)を求め、当該単射写像Beを一意に識別する値ID(e)と像Be(a0),…,Be(az-1)との組を上記記数法変換されたn進数として出力する変換ステップと
を有する記数法変換方法。
【請求項６】
請求項５に記載の記数法変換方法（以下、n進数記数法変換方法という）によって得られたデータID(e),b0,…,bk-2（ただし、kは2≦kを満たす整数とする）からバイナリデータを出力する記数法変換方法であり、
Lをn（nは、２の冪乗で表されない３以上の整数とする）の２進法表記におけるビット数とし、mを1≦m<Lを満たす整数とし、
0以上2L未満の2L個の整数を分類して得られる要素数が同じ2m個の集合S0，…，S2^m-1（ただし、これら集合族には、n以上2L-1以下の各整数を含む集合SMAXが含まれるとする）を、上記データを生成した上記n進数記数法変換方法で用いられた2m個の上記集合S0，…，S2^m-1とし、2m個の単射写像Bi：[0,2L-1]→[0,2L-1]（i=0,…,2m-1）（ただし、記号[a,b]はa以上b以下のb-a+1個の整数を要素に持つ集合であり、写像Bi（i=0,…,2m-1）は、[0,2L-1]-Siの要素をすべて[0,2L-1]-SMAXに写す、という性質を満たすものとする）を、上記データを生成した上記n進数記数法変換方法で用いられた2m個の上記単射写像Bi：[0,2L-1]→[0,2L-1]（i=0,…,2m-1）とし、
逆変換部が、上記ID(e)から単射写像Beを特定し、各上記bi(i=0,…,k-2)の逆写像Be-1による像Be-1(bi)を求め2L未満の数に変換する逆変換ステップと、
結合部が、Be-1(b0),…,Be-1(bk-2)をビット連結して上記バイナリデータを出力する結合ステップと
を含む記数法変換方法。
【請求項７】
請求項１から請求項４のいずれかに記載の記数法変換装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記数法変換技術に関わり、詳しくは２進法で表された数とn進法（ただし、nは３以上の所定の整数とする）で表された数との間の基数変更による記数法変換技術に関する。
【背景技術】
【０００２】
本明細書での記数法は、いわゆる位取り記数法に限定されない、広義の記数法を指す。また、m進法で表された数をm進数（ただし、mは１０進法で表された数であって２以上の所定の整数とする）ともいう。従来、２進数（バイナリデータ）をn進数に変換する方法として、2k<nを満たす最大の整数kを定め、n進数の各桁にバイナリデータから順次抽出されたkビットを割り当てる、つまり、抽出されたk個のビットで構成されるビット列をb0…bk-1（bi∈{0,1}）としたとき、当該ビット列に対応するn進数の一つの桁の数字をΣ0≦i＜k2ibiで与える方法が知られている（先行技術文献を挙げるまでもない）。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
例えばn=127のとき、n進数の一桁はlog2127、すなわちほぼ７ビットの情報量を持つことができる。しかし、上述の従来技術によると、n=127のときk=6となり、約14%のデータ容量を無駄にすることとなる。このように、上述の従来技術によると、データ容量ロスが大きいという課題がある。
【０００４】
そこで本発明は、記数法変換の際のデータ容量ロスを低減できる、２進数とn進数との間の基数変更による記数法変換技術を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の記数法変換技術は、次のとおりである。
入力された２進数を記数法変換してn進数（nは、２の冪乗で表されない３以上の整数とする）を出力する場合：
Lをnの２進法表記におけるビット数とし、mを1≦m<Lを満たす整数とし、予め、0以上2L未満の2L個の整数を分類して得られる要素数が同じ2m個の集合S0，…，S2^m-1と（ただし、これら集合族には、n以上2L-1以下の各整数を含む集合SMAXが含まれるとする）、2m個の単射写像Bi：[0,2L-1]→[0,2L-1]（i=0,…,2m-1）（ただし、記号[a,b]はa以上b以下のb-a+1個の整数を要素に持つ集合であり、写像Bi（i=0,…,2m-1）は、[0,2L-1]-Siの要素をすべて[0,2L-1]-SMAXに写す、という性質を満たすものとする）が定められているとする。２進数であるL(2m-1)ビット以下のバイナリデータDを連続するLビットごとに分割し、z個（z≦2m-1）のデータ区間a0,…,az-1（ただし、ai（i=0,…,z-1）は１０進法で0以上2L未満の数である）を得る分割処理と、ai（i=0,…,z-1）のいずれの値も属さない集合Se（e∈{0,…,2m-1}）に対応する単射写像Beを特定する制御処理と、各a0,…,az-1の単射写像Beによる像Be(a0),…,Be(az-1)を求め、当該単射写像Beを一意に識別する値ID(e)と像Be(a0),…,Be(az-1)との組を記数法変換されたn進数として出力する変換処理を行う。
【０００６】
上記記数法変換技術（以下、n進数記数法変換手法という）によって得られたデータID(e),b0,…,bk-2（kは2≦kを満たす整数とする）からバイナリデータを出力する場合：
Lをn（nは、２の冪乗で表されない３以上の整数とする）の２進法表記におけるビット数とし、mを1≦m<Lを満たす整数とし、0以上2L未満の2L個の整数を分類して得られる要素数が同じ2m個の集合S0，…，S2^m-1（ただし、これら集合族には、n以上2L-1以下の各整数を含む集合SMAXが含まれるとする）を、データを生成したn進数記数法変換手法で用いられた2m個の集合S0，…，S2^m-1とし、2m個の単射写像Bi：[0,2L-1]→[0,2L-1]（i=0,…,2m-1）（ただし、記号[a,b]はa以上b以下のb-a+1個の整数を要素に持つ集合であり、写像Bi（i=0,…,2m-1）は、[0,2L-1]-Siの要素をすべて[0,2L-1]-SMAXに写す、という性質を満たすものとする）を、データを生成したn進数記数法変換手法で用いられた2m個の単射写像Bi：[0,2L-1]→[0,2L-1]（i=0,…,2m-1）として、ID(e)から単射写像Beを特定し、各bi(i=0,…,k-2)の逆写像Be-1による像Be-1(bi)を求め2L未満の数に変換する逆変換処理と、Be-1(b0),…,Be-1(bk-2)をビット連結してバイナリデータを出力する結合処理とを行う。
【発明の効果】
【０００７】
本発明に拠れば、詳細は後述の実施形態に譲るが、0以上2L未満の2L個の整数を分類して得られる要素数が同じ2m個の集合S0，…，S2^m-1と（この集合族にはn以上2L-1以下の各整数を含む集合SMAXが含まれる）、2m個の単射写像Bi：[0,2L-1]→[0,2L-1]（i=0,…,2m-1）（写像Biは、[0,2L-1]-Siの要素をすべて[0,2L-1]-SMAXに写す）を定めておいて、L(2m-1)ビット以下のバイナリデータDをLビットごとに分割し、2m-1個以下のz個のデータ区間ai（i=0,…,z-1）を得る。このため、いずれのaiの値も属さない集合Seが必ず存在する。よって、この集合Seに対応する写像Beによる像Be(ai)はSMAXには属さない。つまり、n未満の数に変換されている。いずれのaiの値も属さない集合Seに対応する写像Beによる像Be(ai)を求め、写像Beを一意に識別する値ID(e)と各Be(ai)との組を記数法変換されたn進数として出力する。このとき、データ容量のロスはLビットであり、比率はL/(L(2m-1))=1/(2m-1)でパラメータmに応じてデータ容量ロスを低減できる。
【図面の簡単な説明】
【０００８】
【図１】実施形態に関わる記数法変換装置（２進法→n進法）の機能構成を示す図。
【図２】実施形態における記数法変換（２進法→n進法）の処理手順を示す図。
【図３】実施形態に関わる記数法変換装置（n進法→２進法）の機能構成を示す図。
【図４】実施形態における記数法変換（n進法→２進法）の処理手順を示す図。
【発明を実施するための形態】
【０００９】
本発明の実施形態に係る記数法変換装置１は、入力された２進数を記数法変換してn進数を出力する装置であり、準備部１１０、分割部１２０、制御部１３０、変換部１４０、記憶部１５０を含む。
【００１０】
記数法変換装置１は、２進法から基数変更した後の基数n（ただし、nは、１０進数であって、２の冪乗で表されない３以上の整数とする）、パラメータm（ただしmは1≦m<Lを満たす整数であって、Lはnの２進法表記におけるビット数（つまり、n≦2hを満たす最小のh）とする）、L(2m-1)ビットの２進数（バイナリデータ）Dが入力され、2m個の整数（ただし各整数は0以上n未満とする）の組であってバイナリデータDを復元可能なものを出力する。
以下、記数法変換装置１による処理を叙述する。
【００１１】
ステップＳ１
準備部１１０は、１０進数である0以上2L未満の2L個の整数を要素数が同じ2m個の集合S0，…，S2^m-1に分類する（|S0|=|S1|=…=|S2^m-1|=2L-m）。記号＾はべき乗を表す。ただし、これら集合族にはSMAX⊇[n,2L-1]が含まれるとする（これは、パラメータmの取り方によって実現される）。また、i≠j（i,j∈{0,…,2m-1}）についてSi≠Sjである。a,bをそれぞれ整数として区間表示[a,b]はa以上b以下のb-a+1個の整数を要素に持つ集合を表す。一般的な集合の表示を用いれば、[a,b]={a,a+1,…,b-1,b}である。以下、a,bをそれぞれ整数とする区間表示[a,b]であって、集合を表す区間表示[a,b]に全順序関係を導入したもの、つまり、通常の整数の順序関係（大小関係）を区間表示[a,b]に導入した全順序集合を整数区間[a,b]と呼称する。この分類の例として整数区間[0,2L-1]の等分割が挙げられる。ただし、整数区間[a,b]={a,a+1,…,b-1,b}の等分割は、整数区間の有限列I1,I2,…,Inであって、(1) 任意のi,j∈{1,…,n}，i≠jに対してIi∩Ij≠φ、(2) ∪i=1nIi=[a,b]、(3) 任意のi,j∈{1,…,n}，j＞iに対して∀p∈Ii，∀q∈Ij，q＞p、(4) |I1|=|I2|=…=|In|、を満たすものとする。例として、n=127でm=5のとき、L=7であり、[0,127]を最下位ビットから2L-m個ずつ区分する（整数区間[0,127]の等分割）、つまり区間表示される32個の集合[0,3],[4,7],[8,11],…,[120,123],[124,127]（SMAX=[124,127]⊇[127,127]）に分類することができる。このような整数区間[0,2L-1]の等分割によると、与えられた整数値がどの集合に属するかの判断のために特定ビットだけを見ればよいので高速処理できるという特徴がある（このパラメータ例では下から3ビット目から7ビット目だけ見ればよい）。2m個の集合S0，…，S2^m-1は記憶部１５０に保存される。
【００１２】
ステップＳ２
準備部１１０は、各i（ただしi=0,…,2m-1）に対して、相異なる単射写像Bi：[0,2L-1]→[0,2L-1]を定める。ただし写像Bi（i=0,…,2m-1）は、Si以外（つまり、[0,2L-1]-Si）の要素をすべてSMAX以外（つまり、[0,2L-1]-SMAX）に写す、という性質を満たすものとする。このような単射写像は全単射写像も含む。たとえば上述の分類の例では、単射写像Biの例として、Siの元とSMAXの元を入れ替える、つまりSiの元に対してはmin SMAX - min Siを加算した値の元を対応させ、SMAXの元に対してはmin SMAX - min Siを減算した値の元を対応させ、SiとSMAXのいずれにも属さない元に対しては同じ元を対応させるという写像（下記式参照）などを例示できる。単射写像Bi（i=0,…,2m-1）は記憶部１５０に保存される。
【数１】
0005506961.tif 000002
【００１３】
ステップＳ３
分割部１２０は、バイナリデータDを連続するLビットごとに分割し、2m-1個のデータ区間を得る。各区間のデータ（ビット列）はLビットであり、各区間のデータは１０進法で0以上2L未満の数として表すことができ、以下、これをa0,…,a2^m-2とする（つまり、ai（i=0,…,2m-2）は１０進法で0以上2L未満の数である）。
【００１４】
ステップＳ４
制御部１３０は、フラグf0,…,f2^m-1∈{0,1}を用意し、全てに値0をセットする。フラグfjは同じ添字jを持つ集合Sjに対応する。
【００１５】
ステップＳ５
制御部１３０は、各ai（ただしi=0,…,2m-2）に対し、aiの値の属する集合Sjとすると、集合Sjに対応するフラグfjを1に書き換える。たとえば上述の例で、ai=10とすると、10は[8,11]に属し、最初の集合を0番目とすると[8,11]は2番目の区間だから、f2を1に書き換える。jはai>>(L-m)によって高速に計算することができる。ただし、記号>>は右ビットシフトである。書き換え後のフラグf0,…,f2^m-1の値は記憶部１５０に保存される。
【００１６】
ステップＳ６
制御部１３０は、フラグf0,…,f2^m-1の中で値が0となっているフラグを探索し、そのフラグの添字をeとする（ステップＳ１の処理で得られた集合族の要素数が2m個であり、ステップＳ３の処理で得られたデータ区間の個数が2m-1個であることから、「フラグf0,…,f2^m-1の中で値が0となっているフラグ」は必ず存在する）。もし、値が0となっているフラグが複数存在する場合は、制御部１３０は、その中から任意のフラグを選択して、当該選択されたフラグの添字をeとする。この段階で、いずれのai（ただしi=0,…,2m-2）の値も属さない集合Se（e∈{0,…,2m-1}）に対応する単射写像Beが特定されたことになる。
【００１７】
ステップＳ７
変換部１４０は、各a0,…,a2^m-2の写像Beによる像Be(a0),…,Be(a2^m-2)を求め、ID(e),Be(a0),…,Be(a2^m-2)の組を出力する。通常、少なくとも像Be(a0),…,Be(a2^m-2)の順序はこのとおりとする。ID(e),Be(a0),…,Be(a2^m-2)の組が記数法変換装置１の出力であり、バイナリデータDのn進数である。ただし、ID(e)は、e（つまり、単射写像Be）を一意に識別する値であり、たとえばeそのものである。
【００１８】
a0,…,a2^m-2がいずれもSeに属さないことをステップＳ６の処理が保証している。したがってBe(a0),…,Be(a2^m-2)はいずれもSeのBeによる写像先であるSMAXには属さない。つまり、n未満の数に変換されている。
【００１９】
上述の実施形態によると、データ容量のロスは、L(2m-1)ビットがL2mビットになるので差はLビットであり、比率はL/(L(2m-1))=1/(2m-1)、すなわち上述の例では1/31≒3.2%である。また、上の例でm=7とすれば、1/127≒0.79%となり、ほぼデータ容量のロスを皆無にすることができる。
【００２０】
バイナリデータDのビット長がL(2m-1)ビットよりも短い場合、ステップＳ３の処理にてバイナリデータDを例えば最下位ビットから連続するLビットごとに分割していき、2m-1個未満の区間にバイナリデータDを分割すればよい。Lビットよりも短い区間については、ゼロパディングによってLビットの区間にする。この場合、分割部１２０がバイナリデータDをz個（1≦z＜2m-1）の区間に分割したとすると、各区間のデータはいわゆる位取り記数法によってn進法で0以上2L未満の数として表すことができ、これをa0,…,az-1とする。a0,…,az-1に対して上記ステップＳ４からステップＳ７の各処理を実行し、ID(e),Be(a0),…,Be(az-1)が出力される。したがって、入力されるバイナリデータDのビット長はL(2m-1)ビット以下であればよく、バイナリデータDのビット長がL(2m-1)ビットの場合はz=2m-1となる。
【００２１】
また、入力されたバイナリデータのビット長がL(2m-1)ビットよりも長い場合、分割部１２０は、まず、入力されたバイナリデータのビット長がL(2m-1)ビットの整数倍ならばこの入力バイナリデータをL(2m-1)ビットの一つ以上のバイナリデータに区分し、入力されたバイナリデータのビット長がL(2m-1)ビットの整数倍でないならばこの入力バイナリデータをL(2m-1)ビットの一つ以上のバイナリデータとL(2m-1)ビットよりも短い一つ以上のバイナリデータに区分し、当該区分で得られた各バイナリデータを上述の実施形態のバイナリデータDと看做して既述の各処理（具体的には上記ステップＳ３からステップＳ７の各処理）を実施すればよい。変換部１４０は、区分ごとに得られた上記組を連結したものを、入力されたバイナリデータに対応するn進数として出力する。
【００２２】
次に、記数法変換装置１が出力したデータからバイナリデータDを復元する、つまりn進数から２進数への記数法変換について説明する。本発明の実施形態に係る記数法変換装置２は、入力されたn進数を記数法変換して２進数を出力する装置であり、逆変換部２１０、結合部２２０、記憶部２３０を含む。
【００２３】
記数法変換装置２は、ID(e),b0,…,bk-2（ただし、kは2≦kを満たす整数とする）が入力され、バイナリデータDを出力する。
以下、記数法変換装置２による処理を叙述する。
【００２４】
ステップＳ１ｄ
逆変換部２１０は、ID(e)からeを特定し、各bi(i=0,…,k-2)の逆写像Be-1による像Be-1(bi)を求め2L未満の数に変換する。写像Beが上記ステップＳ２で示した式で表される場合、逆写像Be-1(bi)は、
１．di ← bi
２．if bi∈Se then di ← di + min SMAX - min Se
３．output di as Be-1(bi)
によって得られる。記号←は代入操作を表す。得られた値Be-1(b0),…,Be-1(bk-2)は記憶部２３０に記憶される。なお、記数法変換装置２が記数法変換装置１と同一の装置ではない場合、予め記数法変換装置１が準備した2m個の集合S0，…，S2^m-1と単射写像Bi（i=0,…,2m-1）は記数法変換装置２の記憶部２３０に記憶されているとする。
【００２５】
ステップＳ２ｄ
結合部２２０は、Be-1(b0),…,Be-1(bk-2)をビット連結してバイナリデータDを出力する。
【００２６】
＜変形例１＞
ステップＳ１の処理にて整数区間[0,2L-1]の等分割を採用した場合、ステップＳ２の処理にて、相異なる単射写像Bi：[0,2L-1]→[0,2L-1]をCi=((i+1) mod 2m)<<(L-m)としてBi(a)=(a-Ci) mod 2Lと定め、ステップＳ７の処理にて、値a（a∈{a0,…,az-1}）の写像Be（i=0,…,2m-1）による像Be(a)とID(e)を求める。ただし、記号<<は左ビットシフト演算である。
【００２７】
写像Beが上記ステップＳ２で示した式で表される場合、逆変換部２１０の処理にて、上記プロセス２．のように条件分岐処理が必要となる。他方、この変形例によると、Be(a)=(a-Ce) mod 2Lで表されるため、逆写像Be-1(bi)はBe-1(bi)=(bi+Ce) mod 2Lで表される。このため、逆写像Be-1(bi)は
１．Be-1(bi) ← (bi+Ce)&(2L-1)
によって得られる。ただし、記号＆はビットAND演算を表している。このように、この変形例によると、逆変換部２１０の処理にて条件分岐処理が不要である。CPUの設計仕様にもよるが、CPUが条件分岐処理に対して分岐予測を行うことなどを考慮すると、条件分岐処理が不要なアルゴリズムで処理できる単射写像を利用することは高速処理の観点から有利である。
【００２８】
＜変形例２＞
変形例１の変形例である変形例２を説明する。変形例１では2Lを法とする剰余演算を用いたが、2Lを法とすることに限定されない。ステップＳ６の処理では、入力の値a（a∈{a0,…,az-1}）がいずれも属さないSiが必ず存在する。Ci=((i+1) mod 2m)<<(L-m)とすると、Si=[Ci-Δ,Ci）なので、入力の値a（a∈{a0,…,az-1}）はいずれもCi-Δ≦a＜Ci以外の値である。このとき、a-Ciを計算すると、入力の値a（a∈{a0,…,az-1}）に対して¬(-Δ≦a-Ci＜0)が成立する。さらに、法の値をn'とすると、入力の値a（a∈{a0,…,az-1}）に対して、¬(-Δ mod n'=n'-Δ≦(a-Ci) mod n'＜n'=0 mod n')、つまり、Bi(a)=(a-Ci) mod n'とおくと、¬(-Δmod n'=n'-Δ≦Bi(a)＜n'=0 mod n')が言える。n'-Δ≦nであれば、入力の値a（a∈{a0,…,az-1}）の基数変換後の値Bi(a)はn未満の数に変換されていることになる。よって、nが基数であることも考慮すると、n≦n'<n+Δを満たす整数n'を法としてもよい。ただし、Δは、ステップＳ１の処理にて整数区間[0,2L-1]の等2m分割を採用した場合の分割で得られた任意の整数区間Iiの幅、つまり2L-mである。このとき、変形例１と異なり、値a（a∈{a0,…,az-1}）の写像Bi（i=0,…,2m-1）による像Bi(a)はBi(a)=(a - Ci) mod n'で表される。CiとID(e)は変形例１と同じである。この変形例２によると、2Lを法とする演算に限定されず、n≦n'<n+Δ=n+2L-mを満たすn'を法に用いて像Bi(a)を得ることができる。
【００２９】
＜応用例＞
本発明は、セキュリティ技術である秘密分散技術と組み合わせて利用できる。秘密分散技術を用いると、暗号のようにデータを安全に保管することができる。秘密分散技術の一例であるShamirの秘密分散（例えば所謂k-out-of-n分散方式）では、データの処理単位は素数p未満の整数をとることが多い（たとえばp=127である）。本発明に従ってバイナリデータをp未満の整数の列に変換し、それから秘密分散を行い、データ復元の際はShamirの秘密分散の復元を行い、その後、復元結果を本発明に従って逆変換によりバイナリデータに戻すことで、データ容量のロスを最低限に抑えることができる。
【００３０】
＜記数法変換装置のハードウェア構成例＞
上述の実施形態に関わる記数法変換装置は、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、記数法変換装置の外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit）〔キャッシュメモリやレジスタなどを備えていてもよい〕、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００３１】
記数法変換装置の外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくなどでもよい。）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。上述の説明では、演算結果やその格納領域のアドレスなどを記憶するＲＡＭやレジスタなどの記憶装置を単に「記憶部」とした。
【００３２】
記数法変換装置では、外部記憶装置〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（例えば、準備部、分割部、制御部、変換部、逆変換部、結合部など）を実現する。
【００３３】
＜補記＞
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００３４】
また、上記実施形態において説明したハードウェアエンティティ（記数法変換装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００３５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００３６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００３７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００３８】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【要約】
【課題】記数法変換の際のデータ容量ロスを低減できる、２進数とn進数との間の基数変更による記数法変換技術を提供する。
【解決手段】Lをnの２進ビット数、mを1≦m<Lを満たす整数とし、0以上2L未満の2L個の整数を分類して得られる要素数が同じ2m個の集合S0，…，S2^m-1と（n以上2L-1以下の各整数を含む集合SMAXを含む）、2m個の単射写像Bi：[0,2L-1]→[0,2L-1]（i=0,…,2m-1）（写像Biは、[0,2L-1]-Siの要素をすべて[0,2L-1]-SMAXに写す）が定められており、L(2m-1)ビット以下のバイナリデータDをLビットごとに分割し、z個（z≦2m-1）のデータ区間ai（i=0,…,z-1）を得る。いずれのaiの値も属さない集合Seに対応する写像Beによる像Be(ai)を求め、写像Beを一意に識別する値ID(e)と各Be(ai)との組を記数法変換されたn進数として出力する。
【選択図】図２【図１】
0005506961.tif 000003
【図２】
0005506961.tif 000004
【図３】
0005506961.tif 000005
【図４】
0005506961.tif 000006