(57)【要約】【課題】少ないハードウェア量で高速に剰余系の数値を２進数に変換する。【解決手段】剰余系における第１のモジュラスは、２を自然数によりべき乗した、当該第１モジュラスより小さいモジュラスの積より大きいべき乗値に、１を加えた値をとり、各モジュラスについて、剰余値に当該モジュラス以外のモジュラスの積を乗じた値に基づくモジュラス対応変換値を生成するモジュラス対応変換値生成部と、各モジュラス対応変換値を加算して、２進数の被変換数を算出するモジュラス対応変換値加算部とを備え、モジュラス対応変換値生成部は、第１モジュラスより小さい第２モジュラスに対応する剰余値のビット列に基づいて、当該第２モジュラスに対応するモジュラス対応変換値の一部となる部分ビット列を生成する部分ビット列生成部と、当該モジュラス対応変換値の複数箇所に部分ビット列を複製する部分ビット列複製部とを有する変換装置を提供する。【選択図】図6
2006065116.tif 000002
【特許請求の範囲】
【請求項１】
剰余系により表現された被変換数を２進数に変換する変換装置であって、
前記剰余系は、複数のモジュラスのそれぞれにより前記被変換数を割った複数の剰余値の組により、前記被変換数を表現するものであり、
第１の前記モジュラスは、２を自然数によりべき乗した、当該第１モジュラスより小さい前記モジュラスの積より大きいべき乗値に、１を加えた値をとり、
複数のモジュラスのそれぞれについて、当該モジュラスについての前記剰余値に当該モジュラス以外のモジュラスの積を乗じた値に基づく２進数の値である、当該モジュラスに対応するモジュラス対応変換値の、少なくとも一部に含まれる部分ビット列を生成する部分ビット列生成部と、
前記複数のモジュラスのそれぞれについての前記部分ビット列に基づいて、前記複数のモジュラスのそれぞれについての前記モジュラス対応変換値を加算した２進数の前記被変換数を算出するモジュラス対応変換値加算部と
を備え、
前記モジュラス対応変換値加算部は、
前記第１モジュラスより小さい少なくとも１つの前記モジュラスに対応する前記モジュラス対応変換値の和である第１部分和の一部に含まれる予め定められたビット数の下位ビット列を、当該下位ビット列より上位桁の上位ビット列として複製し、同一の上位ビット列及び下位ビット列を含む被加算数を生成する下位ビット列複製部と、
前記被加算数に、前記第１モジュラスに対応する前記部分ビット列を加算して、前記第１部分和に前記第１モジュラスについての前記モジュラス対応変換値を加えた第２部分和の少なくとも一部に含まれる下位ビット列を算出するビット列加算部と
を有する変換装置。
【請求項２】
最小の前記モジュラスは、２の自然数によるべき乗値から１を減じた２以上の自然数であり、
前記複数のモジュラスのうち最小でない前記モジュラスのそれぞれは、２を自然数によりべき乗した、当該モジュラスより小さい前記モジュラスの積より大きいべき乗値に、１を加えた値をとり、
前記下位ビット列複製部は、前記複数のモジュラスのうち最小でない前記モジュラスのそれぞれについて、当該モジュラスより小さい全ての前記モジュラスに対応する前記モジュラス対応変換値の和である前記第１部分和の一部に含まれる予め定められたビット数の下位ビット列を、当該下位ビット列より上位桁の上位ビット列として複製して、当該モジュラスについての前記被加算数を生成し、
前記ビット列加算部は、前記複数のモジュラスのうち最小でない前記モジュラスのそれぞれについて、当該モジュラスについての前記被加算数に、当該モジュラスに対応する前記部分ビット列を加算して、前記第１部分和に当該モジュラスについての前記モジュラス対応変換値を加えた前記第２部分和の少なくとも一部に含まれる下位ビット列を算出する
請求項１記載の変換装置。
【請求項３】
前記複数のモジュラスは、以下の数１に示す値をとり、
前記下位ビット列複製部は、前記複数のモジュラスのうち最小でない前記モジュラスmi（i=1,…,k+1）のそれぞれについて、当該モジュラスmiより小さい全てのモジュラスに対応する前記モジュラス対応変換値の和である前記第１部分和におけるp・2i-1ビットの下位ビット列を、当該下位ビット列より上位桁のp・2i-1ビットの上位ビット列として複製して、p・2iビットの前記被加算数を生成し、
前記ビット列加算部は、前記複数のモジュラスのうち最小でない前記モジュラスmi（i=1,…,k+1）のそれぞれについて、当該モジュラスmiについての前記被加算数に、当該モジュラスmiに対応する前記モジュラス対応変換値における下位p・2iビットの前記部分ビット列を加算して、前記第１部分和に当該モジュラスについての前記モジュラス対応変換値を加えた前記第２部分和におけるp・2iビットの下位ビット列を算出する
請求項１記載の変換装置。
【数１】
2006065116.tif 000048
ただし、kは0以上の整数であり、pは自然数である。
【請求項４】
前記ビット列加算部は、
前記第１モジュラスmi1について、p・2i1ビットの前記被加算数に、前記モジュラス対応変換値におけるp・2i1ビットの前記部分ビット列を加算するp・2i1ビットの加算器と、
第２の前記モジュラスmi2について、p・2i2ビットの前記被加算数に、前記モジュラス対応変換値におけるp・2i2ビットの前記部分ビット列を加算するp・2i2ビットの加算器と
を含む請求項３記載の変換装置。
【請求項５】
前記ビット列加算部は、前記加算により前記被加算数及び前記部分ビット列のビット数を越える桁あふれが生じた場合に、前記加算の結果得られたビット列における前記被加算数と同一ビット数の下位ビット列の下位ビットに、前記桁あふれしたビットを加えて前記第２部分和の下位ビット列を算出する請求項２記載の変換装置。
【請求項６】
剰余系により表現された被変換数を２進数に変換する変換装置であって、
前記剰余系は、複数のモジュラスのそれぞれにより前記被変換数を割った複数の剰余値の組により、前記被変換数を表現するものであり、
第１の前記モジュラスは、２を自然数によりべき乗した、当該第１モジュラスより小さい前記モジュラスの積より大きいべき乗値に、１を加えた値をとり、
複数のモジュラスのそれぞれについて、当該モジュラスについての前記剰余値に当該モジュラス以外のモジュラスの積を乗じた値に基づいて、当該モジュラスに対応する２進数の値であるモジュラス対応変換値を生成するモジュラス対応変換値生成部と、
前記複数のモジュラスのそれぞれについての前記モジュラス対応変換値を加算して、２進数の前記被変換数を算出するモジュラス対応変換値加算部と
を備え、
前記モジュラス対応変換値生成部は、
前記第１モジュラスより小さい第２モジュラスにより前記被変換数を割った剰余値のビット列に基づいて、当該第２モジュラスに対応する前記モジュラス対応変換値の一部となる部分ビット列を生成する部分ビット列生成部と、
当該第２モジュラスに対応する前記モジュラス対応変換値の複数箇所に前記部分ビット列を複製することにより、前記部分ビット列に前記第１モジュラスを乗じた当該モジュラス対応変換値を生成する部分ビット列複製部と
を有する
変換装置。
【請求項７】
最小の前記モジュラスは、２の自然数によるべき乗値から１を減じた２以上の自然数であり、
前記複数のモジュラスのうち最小でない前記モジュラスのそれぞれは、２を自然数によりべき乗した、当該モジュラスより小さい前記モジュラスの積より大きいべき乗値に、１を加えた値をとり、
前記部分ビット列生成部は、複数のモジュラスのうち最小でない前記モジュラスのそれぞれについて、前記被変換数の当該モジュラスによる剰余値を当該モジュラスに対応する前記自然数分のビット数だけ上位桁側にシフトした値から当該剰余値を減じた前記部分ビット列を生成する
請求項６記載の変換装置。
【請求項８】
前記複数のモジュラスは、以下の数２に示す値をとり、
前記部分ビット列生成部は、複数のモジュラスのうち最小でない前記モジュラスmi（i=1,…,k+1）のそれぞれについて、前記被変換数の当該モジュラスmiによる剰余値を2i-1・pビット分上位桁側へシフトした値から当該剰余値を減じた2i・pビットの前記部分ビット列を生成し、
前記部分ビット列複製部は、複数のモジュラスのうち最小及び最大でない前記モジュラスmiのそれぞれについて、当該モジュラスmiに対応する前記モジュラス対応変換値の複数箇所に、前記部分ビット列を2i・pビット間隔で複製することにより、当該モジュラスmiに対応する前記モジュラス対応変換値を生成する
請求項６記載の変換装置。
【数２】
2006065116.tif 000049
ただし、kは0以上の整数であり、pは自然数である。
【請求項９】
前記モジュラス対応変換値生成部は、
前記第１モジュラスmi1について、前記被変換数の前記第１モジュラスmi1による剰余値に基づいて、2i1・pビットの第１の前記部分ビット列を生成する第１の前記部分ビット列生成部と、
前記第２モジュラスmi2について、前記被変換数の前記第１モジュラスmi2による剰余値に基づいて、2i2・pビットの第２の前記部分ビット列を生成する第２の前記部分ビット列生成部と、
前記第１の部分ビット列を2i1・pビット間隔で複製することにより、当該モジュラスmi1に対応する前記モジュラス対応変換値を生成する第１の前記部分ビット列複製部と、
前記第２の部分ビット列を2i2・pビット間隔で複製することにより、当該モジュラスmi2に対応する前記モジュラス対応変換値を生成する第２の前記部分ビット複製部と
を有する請求項８記載の変換装置。
【請求項１０】
剰余系により表現された被変換数を変換装置により２進数に変換する変換方法であって、
前記剰余系は、複数のモジュラスのそれぞれにより前記被変換数を割った複数の剰余値の組により、前記被変換数を表現するものであり、
第１の前記モジュラスは、２を自然数によりべき乗した、当該第１モジュラスより小さい前記モジュラスの積より大きいべき乗値に、１を加えた値をとり、
複数のモジュラスのそれぞれについて、当該モジュラスについての前記剰余値に当該モジュラス以外のモジュラスの積を乗じた値に基づく２進数の値である、当該モジュラスに対応するモジュラス対応変換値の、少なくとも一部に含まれる部分ビット列を生成する部分ビット列生成段階と、
前記複数のモジュラスのそれぞれについての前記部分ビット列に基づいて、前記複数のモジュラスのそれぞれについての前記モジュラス対応変換値を加算した２進数の前記被変換数を算出するモジュラス対応変換値加算段階と
を備え、
前記モジュラス対応変換値加算段階は、
前記第１モジュラスより小さい少なくとも１つの前記モジュラスに対応する前記モジュラス対応変換値の和である第１部分和の一部に含まれる予め定められたビット数の下位ビット列を、当該下位ビット列より上位桁の上位ビット列として複製し、同一の上位ビット列及び下位ビット列を含む被加算数を生成する下位ビット列複製段階と、
前記被加算数に、前記第１モジュラスに対応する前記部分ビット列を加算して、前記第１部分和に前記第１モジュラスについての前記モジュラス対応変換値を加えた第２部分和の少なくとも一部に含まれる下位ビット列を算出するビット列加算段階と
を有する変換方法。
【請求項１１】
剰余系により表現された被変換数を変換装置２進数に変換する変換方法であって、
前記剰余系は、複数のモジュラスのそれぞれにより前記被変換数を割った複数の剰余値の組により、前記被変換数を表現するものであり、
第１の前記モジュラスは、２を自然数によりべき乗した、当該第１モジュラスより小さい前記モジュラスの積より大きいべき乗値に、１を加えた値をとり、
複数のモジュラスのそれぞれについて、当該モジュラスについての前記剰余値に当該モジュラス以外のモジュラスの積を乗じた値に基づいて、当該モジュラスに対応する２進数の値であるモジュラス対応変換値を生成するモジュラス対応変換値生成段階と、
前記複数のモジュラスのそれぞれについての前記モジュラス対応変換値を加算して、２進数の前記被変換数を算出するモジュラス対応変換値加算段階と
を備え、
前記モジュラス対応変換値生成段階は、
前記第１モジュラスより小さい第２モジュラスにより前記被変換数を割った剰余値のビット列に基づいて、当該第２モジュラスに対応する前記モジュラス対応変換値の一部となる部分ビット列を生成する部分ビット列生成段階と、
当該第２モジュラスに対応する前記モジュラス対応変換値の複数箇所に前記部分ビット列を複製することにより、前記部分ビット列に前記第１モジュラスを乗じた当該モジュラス対応変換値を生成する部分ビット列複製段階と
を有する
変換方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、剰余系の被変換数を２進数に変換する変換装置及び変換方法に関する。特に本発明は、少ないハードウェア量で高速に変換を行う剰余系の被変換数を２進数に変換する変換装置及び変換方法に関する。
【背景技術】
【０００２】
従来、ディジタル回路による数値演算は、２進数にもとづく論理回路により実現されている。また近年、剰余系(Residue Number System; RNS)による数値演算方法が提案されている（非特許文献１）。剰余系による加算、減算、及び乗算は、次に述べる理由により、従来の２進数による演算よりも高速に計算できることが知られている。
【０００３】
２進数での加算は、各ビットの演算から桁上がり（キャリー）信号が生じ、さらにLSB側からMSB側に伝播する。このため、(i-１)番目のビットのキャリーが到達するまで。i番目の桁の計算結果は決定できない。したがって、演算対象となるオペランドのビット数に比例して遅延量は大きくなる。一方、剰余系による演算は、各剰余桁で独立して並列に計算することができ、計算速度が計算ビット数に依存しないため、高速化することができる。
【０００４】
剰余系では１つの数値Xを、N個の剰余数（剰余値）の組み合わせで表現する。
【０００５】
【数１】
2006065116.tif 000003
【０００６】
式（１−１）においてxi = X mod mi（xi = |X|miとも表現する）であり、Xをi番目のモジュラス（modulus：法）miで割った剰余 (Residue)である。また，xiを剰余桁(Residue Digit) 、又は、モジュラスmiによる剰余値ともよぶ。ここで、modはmoduloの略であり、以下の式（１−２）が成立することを意味する。
【０００７】
【数２】
2006065116.tif 000004
【０００８】
ここでpはXをmiで割った商である。このときXとxiはモジュラスmiについて合同(congruent)であるといい、合同式(congruence)をもちいて以下の式により表現してもよい。
【０００９】
【数３】
2006065116.tif 000005
【００１０】
N個のモジュラスmi(i = 0,1,2,…,N-1)が互いに素(relatively prime)であるとき、以下に示す範囲のすべての数値Xを、N個の剰余数の一意的組み合わせで表現することができる。このとき、{m0, m1, m2, …, mN-1}をモジュラスセットとよぶ。
【００１１】
【数４】
2006065116.tif 000006
【００１２】
例として、モジュラスセット{m0, m1, m2, m3}= {8,7,5,3}をもちいた剰余表現を考えると、この剰余系では M = 8×7×5×3 = 840個の整数を表現することができる。例えば、(0,0,0,0)RNS は 0 または 840 または 1680…、(1,1,1,1)RNS は 1 または 841 または 1681…、(0,1,3,2)RNS は 8 または 848 または 1688…、(0,1,4,1)RNS は 64 または 904 または 1744…、となる。そしてモジュラス セット{8,7,5,3}の場合、各剰余桁を表現するために必要となるビット数は、 [3bit, 3bit, 3bit, 2bit ] = 11bitである。
【００１３】
剰余系においては、加算、減算、乗算について、各剰余桁同士を独立に演算することにより実現することができ、剰余桁間の情報の伝播は不要である。すなわち、次に示す定理が成立する。
【００１４】
（剰余系加減乗算の定理）
演算子「〇」を加算、減算、又は乗算を表現する演算子とし、剰余系のモジュラスを{m0,m1,…,mN-1}、オペランドをA= (a0,a1,a2,...,aN-1)、B= (b0,b1,b2,...,bN-1)とすると、Z=A〇Bは、オペランドの各モジュラスに対する剰余桁同士の演算により実現できる。
【００１５】
【数５】
2006065116.tif 000007
【００１６】
ここで、左辺はYのmiによる剰余値である。また、式（１−５）による演算を剰余加算、剰余減算、又は剰余乗算とよぶ。剰余系加減乗算の定理は、以下に示すように証明される。
【００１７】
（剰余系加減乗算の定理の証明）
剰余系の数値表現の定義から、以下の式（１−６）が成立する。
【００１８】
【数６】
2006065116.tif 000008
【００１９】
ここで、piはAをモジュラスmiで割った商であり、qiはBをモジュラスmiで割った商である。
【００２０】
加減算においては、以下の式（１−７）が成立する。
【００２１】
【数７】
2006065116.tif 000009
【００２２】
ここで、(pi+qi)mi≡0より、以下の式（１−８）が成立する。
【００２３】
【数８】
2006065116.tif 000010
【００２４】
一方、乗算においては、以下の式（１−９）が成立する。
【００２５】
【数９】
2006065116.tif 000011
【００２６】
ここで、(piqimi+pibi+qiai)mi≡0より、以下の式（１−１０）が成立する。
【００２７】
【数１０】
2006065116.tif 000012
【００２８】
上記の式（１−８）及び式（１−１０）から、A及びBの各剰余桁同士の演算により、Yの各剰余桁を算出できることが分かる。したがって、式（１−５）の定理が成立することが証明される。
【００２９】
剰余系加減乗算の定理より、剰余系での加減乗算は、入力される２つのオペランドA及びBと、出力される演算結果Yの対応する剰余桁毎に、当該剰余桁についての演算を行う剰余演算ＡＬＵ（Arithmetic Logic Unit）を設けることにより実現することができる。そして、ある剰余桁の計算は、他の剰余桁の計算と独立に行うことができる。各剰余桁に対応する剰余演算ＡＬＵでの演算においては、キャリー伝搬による遅延が当該剰余桁のビット数分に限定できるため、より高速に計算することができる。
【００３０】
剰余系を用いて数値演算を高速化するためには、２進数系又は１０進数系から剰余系への変換(Binary-to-Residue (B/R) converter)、および剰余系から２進数系又は１０進数系への変換(Residue-to-Binary (R/B) converter)が必要である。B/R converterは比較的簡単に実現でき、R/B converterを実現する方法はいくつか検討されている。
【００３１】
R/B converterとしては、中国人の剰余定理（Chinese Remainder Theorem）を用いるものが一般的である。モジュラスセットが{m0,m1,m2,m3}={8,7,5,3}の場合において、Y = (y0,y1,y2,y3)=(5,3,4,2)を10進数に変換する場合を例に示す。
(5,3,4,2)は、式（１−５）に示した剰余系加減乗算の定理から以下の式（１−１１）に示すように変形でき、更に式（１−１２）を得ることができる。
【００３２】
【数１１】
2006065116.tif 000013
【００３３】
【数１２】
2006065116.tif 000014
【００３４】
このように、(1,0,0,0) , (0,1,0,0), (0,0,1,0), (0,0,0,1)に対応する１０進数表現を予め求めておけば、以下の式（１−１３）を用いて任意の剰余表現(y0,y1,y2,y3)を１０進数表現に変換できる。
【００３５】
【数１３】
2006065116.tif 000015
【００３６】
ここで、(1,0,0,0)は、モジュラス8(=m0)に対する剰余が１、かつ、モジュラスのサブセット{7,5,3}={m1,m2,m3}に対する剰余が０である数値である。後者の条件は、m1, m2, m3の最小公倍数であることを条件として(1,0,0,0)を算出すれば満たすことができる。これらの条件は、以下の式（１−１４）により表すことができる。
【００３７】
【数１４】
2006065116.tif 000016
【００３８】
ここでβ0は自然数である。そして、m1,m2,m3が互いに素であれば、式（１−４）よりa)及びb)の条件は以下の式（１−１５）に書き換えることができる。
【００３９】
【数１５】
2006065116.tif 000017
【００４０】
上記の自然数β0を求めることにより、(1,0,0,0)の10進数表現を求めることができる。以下に、{8,7,5,3}剰余系について(1,0,0,0) , (0,1,0,0), (0,0,1,0), (0,0,0,1)の10進数表現を示す。
【００４１】
【数１６】
2006065116.tif 000018
【００４２】
式（１−１６）から、{8,7,5,3}剰余系で表現された数値(5,3,4,2)の１０進数への変換は、5×105 + 3×120 + 4×336 + 2×280 = 2117となる。ただし、この剰余系で表現できる数値は0≦Y＜M=840であるため、Y =|2117|M = 437となる。
【００４３】
一般に，中国人の剰余定理は次式で導かれる。
【００４４】
【数１７】
2006065116.tif 000019
【００４５】
ここで、βi・(M/mi)を、中国人の剰余定理における逆数（multiplicative inverse）（以後単に「逆数」）と呼ぶ。
【００４６】
中国人の剰余定理をそのまま用いる場合、式（１−１７）に示すように、各剰余桁yiと定数βi・(M/mi)との乗算を行う必要があり、計算時間を要する。このため、剰余系で乗算するメリット（計算速度向上）を著しく損なう。
【００４７】
この問題に対して、特定のモジュラスセットを選択することにより、小規模な回路を用いて高速に中国人の剰余定理の計算を行う方法が開示されている（非特許文献２参照。）。
【００４８】
非特許文献２においては、モジュラスセットをつぎのように定義する。
【数１８】
2006065116.tif 000020
【００４９】
ただしkは０以上の整数、pは自然数である。たとえばp=3, k=1のとき、Sk = {7, 9, 65}となる。式（１−４）から、式（１−１８）の剰余系で表現できる数値の個数Mは以下の式（１−１９） となる。
【数１９】
2006065116.tif 000021
【００５０】
モジュラスセットSkにたいして中国人の剰余定理を適用するために、式（１−１４）のｂ）の条件を満たすβiを求め、逆数を定める。
【００５１】
（１）m0（=2p-1） について
式（１−４）及び式（１−１８）から、以下の式（１−２０）をえる。
【数２０】
2006065116.tif 000022
【００５２】
ここで、式（１−１８）から2p mod m0=1となるため、式（１−２０）は、以下の式（１−２１）に変形することができる。
【数２１】
2006065116.tif 000023
【００５３】
さらに、式（１−１４）のａ）の条件を適用すると、式（１−２１）は、以下の式（１−２２）に変形することができる。
【数２２】
2006065116.tif 000024
【００５４】
したがって、式（１−１８）のモジュラスセットを用いた場合、以下の式（１−２３）が成立する。
【数２３】
2006065116.tif 000025
【００５５】
（２）mi（=2^(2i-1p)+1、ただしi＞0）について
式（１−１４）のｂ）の条件、及び式（１−１８）より、以下の式（１−２４）が成立する。
【数２４】
2006065116.tif 000026
【００５６】
ここで、式（１−２４）のＡの部分は、以下の式（１−２５）となる。
【数２５】
2006065116.tif 000027
この変形においては、式（１−１８）により導かれる式2^(2i-1p) mod mi = -1をもちいた。 
【００５７】
一方、式（１−２４）のＢの部分は、以下の式（１−２６）となる。
【数２６】
2006065116.tif 000028
【００５８】
したがって、式（１−２４）は、式（１−２５）及び（１−２６）により、以下の式（１−２７）に変形することができる。
【数２７】
2006065116.tif 000029
【００５９】
式（１−２７）が1と合同であれば、式（１−１４）のａ）の条件と式（１−１８）とを満たす。したがって、βi(-2k-i+2) ≡ 1 mod miをβiについて解くと、以下の式（１−２８）をえる。
【数２８】
2006065116.tif 000030
【００６０】
以上に示した式（１−２３）及び（１−２８）を式（１−１７）に代入することにより、式（１−１８）に示したモジュラスセットに対する中国人の剰余定理は、以下の式（１−２９）となる。
【数２９】
2006065116.tif 000031
【００６１】
次に、Sk ={m0, m1, m2} = {7, 9, 65}として、式（１−２９）の具体的な計算例を示す。
本例においては、k=1であるから、式（１−２９）は、以下の式（１−３０）となる。
【数３０】
2006065116.tif 000032
【００６２】
式（１−３０）を展開して整理すると、式（１−３１）がえられる。
【数３１】
2006065116.tif 000033
【００６３】
式（１−３１）の各項の逆数は全て２のべき乗であるから、２進数のビットシフト演算で実現できる。これより、式（１−３１）の各項は、y0とy1の加減算とy2の加減算のみで計算可能である。k ≧ 2のときも、式（１−３１）と同様の変形が可能である。したがって、非特許文献２の技術を利用することにより、従来乗算と加算が必要であった中国人の剰余定理の計算を加減算のみで実現することができる。この結果、中国人の剰余定理をハードウェアでインプリメントした場合に回路面積を小さくすることができ、かつ計算時間を短縮することができる。
【非特許文献１】B. Parhami, Computer Arithmetic, Oxford University Press, ２０００年, pp. 54-72
【非特許文献２】W. Wang, M. N. S. Swamy, M.O. Ahmad, Y. Wang, "A Parallel Residue-to-Binary Converter," in Proc. IEEE Inte. Conf. Acoustics, Speech, ad Signal Processing, Phenix, AZ, １９９９年３月, pp.1541-1544
【発明の開示】
【発明が解決しようとする課題】
【００６４】
非特許文献２においては、式（１−３１）の計算に、約4・2kpkビットの加算器及び／又は減算器が必要となる。たとえばk=1, p=3のとき、(y0 + y1)と(y0−y1)の演算にそれぞれpビットの加算器が必要となり、y2の加算には4・2kpビットの加算器が必要となる。そして、この加算を(モジュラス数−１)回(= k回)繰り返すので、合計で約4・2kpビット分の加算器が必要となる。
【００６５】
そこで本発明は、上記の課題を解決することのできる変換装置及び変換方法を提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【００６６】
本発明の第１の形態によると、剰余系により表現された被変換数を２進数に変換する変換装置であって、前記剰余系は、複数のモジュラスのそれぞれにより前記被変換数を割った複数の剰余値の組により、前記被変換数を表現するものであり、第１の前記モジュラスは、２を自然数によりべき乗した、当該第１モジュラスより小さい前記モジュラスの積より大きいべき乗値に、１を加えた値をとり、複数のモジュラスのそれぞれについて、当該モジュラスについての前記剰余値に当該モジュラス以外のモジュラスの積を乗じた値に基づく２進数の値である、当該モジュラスに対応するモジュラス対応変換値の、少なくとも一部に含まれる部分ビット列を生成する部分ビット列生成部と、前記複数のモジュラスのそれぞれについての前記部分ビット列に基づいて、前記複数のモジュラスのそれぞれについての前記モジュラス対応変換値を加算した２進数の前記被変換数を算出するモジュラス対応変換値加算部とを備え、前記モジュラス対応変換値加算部は、前記第１モジュラスより小さい少なくとも１つの前記モジュラスに対応する前記モジュラス対応変換値の和である第１部分和の一部に含まれる予め定められたビット数の下位ビット列を、当該下位ビット列より上位桁の上位ビット列として複製し、同一の上位ビット列及び下位ビット列を含む被加算数を生成する下位ビット列複製部と、前記被加算数に、前記第１モジュラスに対応する前記部分ビット列を加算して、前記第１部分和に前記第１モジュラスについての前記モジュラス対応変換値を加えた第２部分和の少なくとも一部に含まれる下位ビット列を算出するビット列加算部とを有する変換装置を提供する。
【００６７】
最小の前記モジュラスは、２の自然数によるべき乗値から１を減じた２以上の自然数であり、前記複数のモジュラスのうち最小でない前記モジュラスのそれぞれは、２を自然数によりべき乗した、当該モジュラスより小さい前記モジュラスの積より大きいべき乗値に、１を加えた値をとり、前記下位ビット列複製部は、前記複数のモジュラスのうち最小でない前記モジュラスのそれぞれについて、当該モジュラスより小さい全ての前記モジュラスに対応する前記モジュラス対応変換値の和である前記第１部分和の一部に含まれる予め定められたビット数の下位ビット列を、当該下位ビット列より上位桁の上位ビット列として複製して、当該モジュラスについての前記被加算数を生成し、前記ビット列加算部は、前記複数のモジュラスのうち最小でない前記モジュラスのそれぞれについて、当該モジュラスについての前記被加算数に、当該モジュラスに対応する前記部分ビット列を加算して、前記第１部分和に当該モジュラスについての前記モジュラス対応変換値を加えた前記第２部分和の少なくとも一部に含まれる下位ビット列を算出してもよい。
【００６８】
前記複数のモジュラスは、以下の数３２に示す値をとり、前記下位ビット列複製部は、前記複数のモジュラスのうち最小でない前記モジュラスmi（i=1,…,k+1）のそれぞれについて、当該モジュラスmiより小さい全てのモジュラスに対応する前記モジュラス対応変換値の和である前記第１部分和におけるp・2i-1ビットの下位ビット列を、当該下位ビット列より上位桁のp・2i-1ビットの上位ビット列として複製して、p・2iビットの前記被加算数を生成し、前記ビット列加算部は、前記複数のモジュラスのうち最小でない前記モジュラスmi（i=1,…,k+1）のそれぞれについて、当該モジュラスmiについての前記被加算数に、当該モジュラスmiに対応する前記モジュラス対応変換値における下位p・2iビットの前記部分ビット列を加算して、前記第１部分和に当該モジュラスについての前記モジュラス対応変換値を加えた前記第２部分和におけるp・2iビットの下位ビット列を算出してもよい。
【数３２】
2006065116.tif 000034
ただし、kは0以上の整数であり、pは自然数である。
【００６９】
前記ビット列加算部は、前記第１モジュラスmi1について、p・2i1ビットの前記被加算数に、前記モジュラス対応変換値におけるp・2i1ビットの前記部分ビット列を加算するp・2i1ビットの加算器と、第２の前記モジュラスmi2について、p・2i2ビットの前記被加算数に、前記モジュラス対応変換値におけるp・2i2ビットの前記部分ビット列を加算するp・2i2ビットの加算器とを含んでもよい。
【００７０】
前記ビット列加算部は、前記加算により前記被加算数及び前記部分ビット列のビット数を越える桁あふれが生じた場合に、前記加算の結果得られたビット列における前記被加算数と同一ビット数の下位ビット列の下位ビットに、前記桁あふれしたビットを加えて前記第２部分和の下位ビット列を算出してもよい。
【００７１】
本発明の第２の形態によると、剰余系により表現された被変換数を２進数に変換する変換装置であって、前記剰余系は、複数のモジュラスのそれぞれにより前記被変換数を割った複数の剰余値の組により、前記被変換数を表現するものであり、第１の前記モジュラスは、２を自然数によりべき乗した、当該第１モジュラスより小さい前記モジュラスの積より大きいべき乗値に、１を加えた値をとり、複数のモジュラスのそれぞれについて、当該モジュラスについての前記剰余値に当該モジュラス以外のモジュラスの積を乗じた値に基づいて、当該モジュラスに対応する２進数の値であるモジュラス対応変換値を生成するモジュラス対応変換値生成部と、前記複数のモジュラスのそれぞれについての前記モジュラス対応変換値を加算して、２進数の前記被変換数を算出するモジュラス対応変換値加算部とを備え、前記モジュラス対応変換値生成部は、前記第１モジュラスより小さい第２モジュラスにより前記被変換数を割った剰余値のビット列に基づいて、当該第２モジュラスに対応する前記モジュラス対応変換値の一部となる部分ビット列を生成する部分ビット列生成部と、当該第２モジュラスに対応する前記モジュラス対応変換値の複数箇所に前記部分ビット列を複製することにより、前記部分ビット列に前記第１モジュラスを乗じた当該モジュラス対応変換値を生成する部分ビット列複製部とを有する変換装置を提供する。
【００７２】
最小の前記モジュラスは、２の自然数によるべき乗値から１を減じた２以上の自然数であり、前記複数のモジュラスのうち最小でない前記モジュラスのそれぞれは、２を自然数によりべき乗した、当該モジュラスより小さい前記モジュラスの積より大きいべき乗値に、１を加えた値をとり、前記部分ビット列生成部は、複数のモジュラスのうち最小でない前記モジュラスのそれぞれについて、前記被変換数の当該モジュラスによる剰余値を当該モジュラスに対応する前記自然数分のビット数だけ上位桁側にシフトした値から当該剰余値を減じた前記部分ビット列を生成してもよい。
【００７３】
前記複数のモジュラスは、以下の数３３に示す値をとり、前記部分ビット列生成部は、複数のモジュラスのうち最小でない前記モジュラスmi（i=1,…,k+1）のそれぞれについて、前記被変換数の当該モジュラスmiによる剰余値を2i-1・pビット分上位桁側へシフトした値から当該剰余値を減じた2i・pビットの前記部分ビット列を生成し、前記部分ビット列複製部は、複数のモジュラスのうち最小及び最大でない前記モジュラスmiのそれぞれについて、当該モジュラスmiに対応する前記モジュラス対応変換値の複数箇所に、前記部分ビット列を2i・pビット間隔で複製することにより、当該モジュラスmiに対応する前記モジュラス対応変換値を生成してもよい。
【数３３】
2006065116.tif 000035
ただし、kは0以上の整数であり、pは自然数である。
【００７４】
前記モジュラス対応変換値生成部は、前記第１モジュラスmi1について、前記被変換数の前記第１モジュラスmi1による剰余値に基づいて、2i1・pビットの第１の前記部分ビット列を生成する第１の前記部分ビット列生成部と、前記第２モジュラスmi2について、前記被変換数の前記第１モジュラスmi2による剰余値に基づいて、2i2・pビットの第２の前記部分ビット列を生成する第２の前記部分ビット列生成部と、前記第１の部分ビット列を2i1・pビット間隔で複製することにより、当該モジュラスmi1に対応する前記モジュラス対応変換値を生成する第１の前記部分ビット列複製部と、前記第２の部分ビット列を2i2・pビット間隔で複製することにより、当該モジュラスmi2に対応する前記モジュラス対応変換値を生成する第２の前記部分ビット複製部とを有してもよい。
【００７５】
本発明の第３の形態によると、剰余系により表現された被変換数を変換装置により２進数に変換する変換方法であって、前記剰余系は、複数のモジュラスのそれぞれにより前記被変換数を割った複数の剰余値の組により、前記被変換数を表現するものであり、第１の前記モジュラスは、２を自然数によりべき乗した、当該第１モジュラスより小さい前記モジュラスの積より大きいべき乗値に、１を加えた値をとり、複数のモジュラスのそれぞれについて、当該モジュラスについての前記剰余値に当該モジュラス以外のモジュラスの積を乗じた値に基づく２進数の値である、当該モジュラスに対応するモジュラス対応変換値の、少なくとも一部に含まれる部分ビット列を生成する部分ビット列生成段階と、前記複数のモジュラスのそれぞれについての前記部分ビット列に基づいて、前記複数のモジュラスのそれぞれについての前記モジュラス対応変換値を加算した２進数の前記被変換数を算出するモジュラス対応変換値加算段階とを備え、前記モジュラス対応変換値加算段階は、前記第１モジュラスより小さい少なくとも１つの前記モジュラスに対応する前記モジュラス対応変換値の和である第１部分和の一部に含まれる予め定められたビット数の下位ビット列を、当該下位ビット列より上位桁の上位ビット列として複製し、同一の上位ビット列及び下位ビット列を含む被加算数を生成する下位ビット列複製段階と、前記被加算数に、前記第１モジュラスに対応する前記部分ビット列を加算して、前記第１部分和に前記第１モジュラスについての前記モジュラス対応変換値を加えた第２部分和の少なくとも一部に含まれる下位ビット列を算出するビット列加算段階とを有する変換方法を提供する。
【００７６】
本発明の第４の形態によると、剰余系により表現された被変換数を変換装置２進数に変換する変換方法であって、前記剰余系は、複数のモジュラスのそれぞれにより前記被変換数を割った複数の剰余値の組により、前記被変換数を表現するものであり、第１の前記モジュラスは、２を自然数によりべき乗した、当該第１モジュラスより小さい前記モジュラスの積より大きいべき乗値に、１を加えた値をとり、複数のモジュラスのそれぞれについて、当該モジュラスについての前記剰余値に当該モジュラス以外のモジュラスの積を乗じた値に基づいて、当該モジュラスに対応する２進数の値であるモジュラス対応変換値を生成するモジュラス対応変換値生成段階と、前記複数のモジュラスのそれぞれについての前記モジュラス対応変換値を加算して、２進数の前記被変換数を算出するモジュラス対応変換値加算段階とを備え、前記モジュラス対応変換値生成段階は、前記第１モジュラスより小さい第２モジュラスにより前記被変換数を割った剰余値のビット列に基づいて、当該第２モジュラスに対応する前記モジュラス対応変換値の一部となる部分ビット列を生成する部分ビット列生成段階と、当該第２モジュラスに対応する前記モジュラス対応変換値の複数箇所に前記部分ビット列を複製することにより、前記部分ビット列に前記第１モジュラスを乗じた当該モジュラス対応変換値を生成する部分ビット列複製段階とを有する変換方法を提供する。
【００７７】
本発明の第５の形態によると、剰余系により表現された被変換数をコンピュータにより２進数に変換するプログラムであって、前記剰余系は、複数のモジュラスのそれぞれにより前記被変換数を割った複数の剰余値の組により、前記被変換数を表現するものであり、第１の前記モジュラスは、２を自然数によりべき乗した、当該第１モジュラスより小さい前記モジュラスの積より大きいべき乗値に、１を加えた値をとり、当該プログラムは、前記コンピュータを、複数のモジュラスのそれぞれについて、当該モジュラスについての前記剰余値に当該モジュラス以外のモジュラスの積を乗じた値に基づく２進数の値である、当該モジュラスに対応するモジュラス対応変換値の、少なくとも一部に含まれる部分ビット列を生成する部分ビット列生成部と、前記複数のモジュラスのそれぞれについての前記部分ビット列に基づいて、前記複数のモジュラスのそれぞれについての前記モジュラス対応変換値を加算した２進数の前記被変換数を算出するモジュラス対応変換値加算部として機能させ、前記モジュラス対応変換値加算部は、前記第１モジュラスより小さい少なくとも１つの前記モジュラスに対応する前記モジュラス対応変換値の和である第１部分和の一部に含まれる予め定められたビット数の下位ビット列を、当該下位ビット列より上位桁の上位ビット列として複製し、同一の上位ビット列及び下位ビット列を含む被加算数を生成する下位ビット列複製部と、前記被加算数に、前記第１モジュラスに対応する前記部分ビット列を加算して、前記第１部分和に前記第１モジュラスについての前記モジュラス対応変換値を加えた第２部分和の少なくとも一部に含まれる下位ビット列を算出するビット列加算部とを有するものであるプログラムを提供する。
【００７８】
本発明の第６の形態によると、剰余系により表現された被変換数をコンピュータにより２進数に変換するプログラムであって、前記剰余系は、複数のモジュラスのそれぞれにより前記被変換数を割った複数の剰余値の組により、前記被変換数を表現するものであり、第１の前記モジュラスは、２を自然数によりべき乗した、当該第１モジュラスより小さい前記モジュラスの積より大きいべき乗値に、１を加えた値をとり、当該プログラムは、前記コンピュータを、複数のモジュラスのそれぞれについて、当該モジュラスについての前記剰余値に当該モジュラス以外のモジュラスの積を乗じた値に基づいて、当該モジュラスに対応する２進数の値であるモジュラス対応変換値を生成するモジュラス対応変換値生成部と、前記複数のモジュラスのそれぞれについての前記モジュラス対応変換値を加算して、２進数の前記被変換数を算出するモジュラス対応変換値加算部として機能させ、前記モジュラス対応変換値生成部は、前記第１モジュラスより小さい第２モジュラスにより前記被変換数を割った剰余値のビット列に基づいて、当該第２モジュラスに対応する前記モジュラス対応変換値の一部となる部分ビット列を生成する部分ビット列生成部と、当該第２モジュラスに対応する前記モジュラス対応変換値の複数箇所に前記部分ビット列を複製することにより、前記部分ビット列に前記第１モジュラスを乗じた当該モジュラス対応変換値を生成する部分ビット列複製部とを有するものであるプログラムを提供する。
【００７９】
本発明の第７の形態によると、上記のプログラムを記録した、コンピュータにより読み取り可能な記録媒体を提供する。
【００８０】
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【発明の効果】
【００８１】
本発明によれば、少ないハードウェア量で高速に剰余系の数値を２進数に変換することができる。
【発明を実施するための最良の形態】
【００８２】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００８３】
以下に、本実施形態における、剰余系から２進数系へ変換する変換装置（R/B converter）の原理を示す。
【００８４】
（１）式（１−１８）のモジュラスセットに対する中国人の剰余定理の性質
式（１−１８）のモジュラスセットに対する中国人の剰余定理においては、式（１−２９）における逆数βi・(M/mi)の２進数表現のビット列は、以下の２つの性質を有する。なお、以下数値をビット列により表現するが、複数ビットをまとめて１桁と見なしてもよい。
【００８５】
（１ａ）性質１：逆数の循環性
・β0・(M/m0)の場合
β0・(M/m0)の場合、以下の式（２−１ａ）が成立する。
【数３４】
2006065116.tif 000036
【００８６】
すなわち、(2^(20p)+1)を1×(2^(20p)+1) = "00...01（pビット）" ×(2^(20p)+1)と見なせば、最下位ビットが"1"かつ他のビットが"0"のpビットのビット列"00…01"を、下位pビット、及びpビット分上位桁側にシフトしたpビットの部分に複製した2pビットのビット列"00…0100…01"（第0ビット（最下位ビット）及び第pビットが"1"、その他のビットは"0"）であることがわかる。
【００８７】
同様に、上記の2pビットのビット列"00…0100…01"に(2^(21p)+1)を乗じれば、当該2pビットのビット列を下位2pビット、及び2pビット分上位桁にシフトした2pビットの部分に複製した4pビットのビット列"00…0100…0100…0100…01"となることがわかる。このビット列は、最下位ビットが"1"かつ他のビットが"0"のpビットのビット列"00…01"を、４箇所に複製したビット列であり、言い換えれば当該pビットのビット列を４つ結合したビット列である。
【００８８】
以下同様にして、(2^(22p)+1)、(2^(23p)+1)、…、(2^(2kp)+1)を順に乗じた値は、最下位ビットが"1"かつ他のビットが"0"のpビットのビット列"00…01"を、2k+1箇所に循環的(cyclic)に複製した2k+1 pビットのビット列となることがわかる。言い換えれば、当該pビットのビット列を、2k+1個結合したビット列である。
【００８９】
そして、上記の2k+1 pビットのビット列に2p-(k+1)を乗じた値は、上記の2k+1 pビットのビット列の下位桁にp-(k+1)個の"0"を付加することにより当該ビット列をp-(k+1)ビット分上位桁側にシフトしたビット列となる。
【００９０】
・βi・(M/mi)の場合（ただし1≦i≦k+1）
β1・(M/m1)の場合、以下の式（２−１ｂ）が成立する。
【数３５】
2006065116.tif 000037
【００９１】
すなわち、(2p-1)を上位pビットが"0"かつ下位pビットが"1"の2pビットのビット列"00…0011…11"と見なせば、この値に(2^(21p)+1)を乗じた値は、当該2pビットのビット列を、下位2pビット、及び2pビット分上位桁側にシフトした2pビットの部分に複製した4pビットのビット列"00…0011…1100…0011…11"（第0ビット（最下位ビット）から第p-1ビット、及び第2pビットから第3p-1ビットが"1"、その他は"0"）となることがわかる。
【００９２】
以下β0・(M/m0)の場合と同様にして、(2^(22p)+1)、(2^(23p)+1)、…、(2^(2kp)+1)を順に乗じた値は、上位pビットが"0"かつ下位pビットが"1"の2pビットのビット列"00…0011…11"を、2k箇所に複製した2k+1 pビットのビット列となることがわかる。言い換えれば、当該2pビットのビット列を、2k個結合したビット列である。
【００９３】
そして、β0・(M/m0)の場合と同様にして、上記の2k+1 pビットのビット列に2p-(k+1)を乗じた値は、上記の2k+1 pビットのビット列の下位桁にp-(k+1)個の"0"を付加することにより当該ビット列をp-(k+1)ビット分上位桁側にシフトしたビット列となる。
【００９４】
また、(2p-1)を2pと-1の組み合わせと見なせば、(2p-1)は、第pビットが"1"、第0ビットが"-1"、かつ他のビットが"0"の2pビットのビット列"00…0100…0(-1)"と見なすことができる。ここで、式（２−１ｂ）においては、１の補数表現の(-1)を、ハイフン付の"1"で表す。この表現形式を用いれば、β1・(M/m1)は、最下位ビットが"1"のpビットのビット列"00…01"と最下位ビットが"-1"のpビットのビット列の組を、2kp箇所に複製したビット列となることがわかる。
【００９５】
β1・(M/m1)の場合と同様に、βi・(M/mi)（i＜k+1）の場合、以下の式（２−１ｃ）が成立する。
【数３６】
2006065116.tif 000038
【００９６】
すなわち、(2^(2i-1p)-1)を上位2i-1pビットが"0"かつ下位2i-1pビットが"1"の2ipビットのビット列"00…0011…11"と見なせば、この値に(2^(2ip)+1)を乗じた値は、当該2ipビットのビット列を、下位2ipビット、及び2 ipビット分上位桁側の2 ipビットの部分に複製した2 i+1pビットのビット列"00…0011…1100…0011…11"（第0ビット（最下位ビット）から第2i-1p-1ビット、及び第2・2i-1pビットから第3・2i-1p-1ビットが"1"、その他は"0"）となることがわかる。
【００９７】
以下β1・(M/m1)の場合と同様にして、(2^(2i+1p)+1)、…、(2^(2kp)+1)を順に乗じた値は、上位2i-1pビットが"0"かつ下位2i-1pビットが"1"の2ipビットのビット列"00…0011…11"を、2k-I+1箇所に複製した2k+1 pビットのビット列となることがわかる。言い換えれば、当該2 ipビットのビット列を、2k-i個結合したビット列である。
【００９８】
そして、β1・(M/m1)の場合と同様にして、上記の2k+1 pビットのビット列に2^(2i-1p-(k-i+2))を乗じた値は、上記の2k+1 pビットのビット列の下位桁に2i-1p-(k-i+2)個の"0"を付加することにより当該ビット列を2i-1p-(k-i+2)ビット分上位桁側にシフトしたビット列となる。
【００９９】
また、(2^(2i-1p)-1)を2^(2i-1p)と-1の組み合わせと見なせば、(2^(2i-1p)-1)は、第2i-1pビットが"1"、第0ビットが"-1"、かつ他のビットが"0"の2ipビットのビット列"00…0100…0(-1)"と見なすことができる。この表現形式を用いれば、βi・(M/mi)は、最下位ビットが"1"の2i-1pビットのビット列"00…01"と最下位ビットが"-1"の2i-1pビットのビット列の組を、2k-I+1箇所に複製したビット列となることがわかる。
【０１００】
βk+1・(M/m k+1)の場合、以下の式（２−１ｄ）が成立する。
【数３７】
2006065116.tif 000039
【０１０１】
すなわち、(2^(2kp)-1)は、上位2kpビットが"0"かつ下位2kpビットが"1"の2k+1pビットのビット列"00…0011…11"と見なせる。そして、この2k+1 pビットのビット列に2^(2kp-1)を乗じた値は、上記の2k+1 pビットのビット列の下位桁に2kp-1個の"0"を付加して当該ビット列を2kp-1ビット分上位桁側にシフトしたビット列となる。
【０１０２】
（１ｂ）性質２：被乗数のビット数
式（１−１８）をモジュラスセットとする剰余系により表現された被変換数Y=(y0,y1,…,yk+1)の各剰余桁の剰余値yiは、以下に示す性質を有する。
【０１０３】
・y0の場合
y0は、モジュラス(2p-1)の剰余値であるから、２進数pビットで表現できる。
・yi（1≦i≦k+1）の場合
yiは、モジュラス(2^(2i-1p)+1)の剰余値であるから、２進数2i-1p+1ビットで表現できる。ただし、最上位ビットが"1"となるのはyiが最大値2^(2i-1p)="100…00（2i-1p+1ビット）である場合のみであり、この場合最上位ビット以外のビットは全て"0"となる。
【０１０４】
以下の式（２−２ａ）から（２−２ｄ）に、剰余値yiのビット列を示す。
【数３８】
2006065116.tif 000040
ここで、an,bn,cn,及びdnは、２進表現の各桁である。
【０１０５】
（２）剰余桁毎の２進数への変換の高速化
上記の性質１及び性質２により、中国人の剰余定理の乗算部 は、被乗数yiを複製してして連結することにより実現することができる。これにより、本実施形態に係る変換装置においては、通常の乗算に必要なAND回路（部分積）と全加算器を不要とすることができる。
【０１０６】
y0についての計算例を、以下の式（２−３）に示す。
【数３９】
2006065116.tif 000041
【０１０７】
性質２に示したように、y0(="ap-1 ap-2 … a0")はpビットである。一方、式（２−１ａ）に示したように、β0・(M/m0)は、pビット毎に"1"となるビット列である。したがって、y0をpビット毎に複製していき下位ビットに"0"を付加すれば、乗算及び加算を行うことなくモジュラスm0に対応する剰余桁を２進数に変換したモジュラス対応変換値y0・β0・(M/m0)を求めることができる。
【０１０８】
次に、yiについての計算例を、以下の式（２−４）に示す。
【数４０】
2006065116.tif 000042
【０１０９】
性質２に示したように、yi(="c2^(i-1)p c2^(i-1)p-1 … c0")は2i-1p+1ビットであるが、最大値は2^(2i-1p)である。このため、yiに(2^(2^i-1p)-1)（="00..0100..0(-1)"）を乗じた値の最大値は、2^(2ip)- 2^(2i-1p)となり、2ipビットのビット列(="c2^ip-1' c2^ip-2' … c0'")で表現することができる。一方、式（２−１ｂ）から（２−１ｄ）に示したように、βi・(M/mi)は、2ipビット毎に"00…0100…0(-1)"となるビット列である。したがって、y0の場合と同様にしてyi・(2^(2^i-1p)-1) (="c2^ip-1' c2^ip-2' … c0'")のビット列を2ipビット毎に複製して下位ビットに"0"を付加すれば、当該ビット列に基づいて、乗算及び加算を行うことなくモジュラスmiに対応する剰余桁を２進数に変換したモジュラス対応変換値yi・βi・(M/mi)を求めることができる。
このモジュラス対応変換値yi・βi・(M/mi)を以下の式（２−５）に示す。
【数４１】
2006065116.tif 000043
【０１１０】
（３）EAC（End-Around Carry）処理
中国人の剰余定理の式（１−１７）によれば、被乗数と逆数の積和演算の後に、モジュラスセットSkによる剰余系で表現できる数値の最大個数M=2^(2k+1p)+1にたいする剰余を計算する必要がある。この剰余計算は、以下に示すEAC処理により実現することができる。
【０１１１】
式（１−１８）に示したモジュラスセットを用いた場合、モジュラスM=2^(2k+1p)+1であるから、2^(2k+1p)≡1（mod M）が成立する。したがって、剰余系の加減乗算定理より、次の等式（２−６）が成立する。
【数４２】
2006065116.tif 000044
【０１１２】
ここで、2^(2k+1p)は2k+1pビットの２進数である。したがって、式（２−６）は、以下の式（２−７）に示すように、2k+1pビットより上位のビット桁を、2k+1pビット下位桁側へシフトすることにより、モジュラスMによる剰余を算出できることを示す。
【数４３】
2006065116.tif 000045
【０１１３】
これを利用して、EAC処理においては、剰余桁の値と逆数を積和演算した値における2k+1pビットより上位のビット桁を最下位ビット側に循環シフト（cyclic shift）して加え、モジュラスMによる剰余値を算出する。
【０１１４】
式（２−５）に示したyi・βi・(M/mi)に対するEAC処理を以下の式（２−８）に示す。
【数４４】
2006065116.tif 000046
【０１１５】
式（２−５）に示したように、yi・βi・(M/mi)における2k+1pビットより上位のビットは、2i-1p-(k-i+2)ビットである。一方、yi・βi・(M/mi)は、下位2i-1p-(k-i+2)ビットが"0"であるから、yi・βi・(M/mi)における2k+1pビットより上位のビット桁を、下位ビットに移動させるのみで、yi・βi・(M/mi)のMによる剰余値を求めることができる。
【０１１６】
（４）剰余桁間の加算の高速化
式（１−２９）におけるモジュラス対応変換値yi・βi・(M/mi)の加算は、以下に示す方法により回路規模の低減及び高速化を図ることができる。ここでは、簡単のため、式（１−１８）においてp=3, k=2としたモジュラスセットを例として示す。すなわち、モジュラスセットSk ={m0, m1, m2, m3} = {7(=23-1), 9(=23+1), 65(=26+1), 4097(=212+1)}である。この剰余系で表現できる数値の個数Mは(224-1)である。この剰余系で表現されたある数値を(y0,y1,y2,y3)とすると、それぞれの２進数表現は、つぎの式（２−９ａ）から（２−９ｄ）となる。
【数４５】
2006065116.tif 000047
【０１１７】
上記の（１）で示した中国人の剰余定理の性質、（２）で示した剰余桁の性質、及び、（３）で示したEAC処理を用いれば、図１に示した計算方法により中国人の剰余定理の計算をすることができる。
【０１１８】
まず、モジュラスm0に対応して、3(=p)ビットの部分ビット列y0(="a2 a1 a0")を上位桁の3ビットのビット列として複製し、同一の部分ビット列を上位ビット列及び下位ビット列として含む6ビットの被加算数"a2 a1 a0 a2 a1 a0"を生成する。この被加算数は、式（２−１ａ）における2pビットの"00…0100…01"とy0との積に対応するビット列であり、式（２−３）における"ap-1 ap-2 … a0 ap-1 ap-2 … a0"に対応する。
【０１１９】
次に、モジュラスm1に対応して、4(=2(1-1)p+1)ビットの剰余値y1を3(=2(1-1)pビット上位桁側へシフトした値から当該剰余値y1を減じた6(=21p) ビットの部分ビット列"b5' b4' b3' b2' b1' b0'"を生成する。
【０１２０】
次に、上記の6ビットの被加算数"a2 a1 a0 a2 a1 a0"及び部分ビット列"b5' b4' b3' b2' b1' b0'"を、6ビット加算器により加算し、EAC処理を行って6ビットのビット列"s5 s4 s3 s2 s1 s0"をえる。このEAC処理は、本来24ビットの加算を行った結果最上位ビットのキャリーを最下位ビットに加えるものである。しかし、被加算数及びモジュラス対応変換値の規則性から、最上位ビットのキャリービットは下位6ビットの加算からえられるキャリービットと同一となるため、6ビット加算によるキャリービットを用いることができる。
【０１２１】
ここで、モジュラスm0及びm1に対応するモジュラス対応変換値は、式（２−１ａ）、（２−１ｂ）、（２−４）及び（２−５）に示したように上記の被加算数及び部分ビット列を４個結合したビット列である。したがって、モジュラスm0及びm1に対応するモジュラス対応変換値の和は、6ビットのビット列"s5 s4 s3 s2 s1 s0"を４個結合したビット列となる。そこで、この和にモジュラスm2に対応するモジュラス対応変換値を加えるために、当該6ビットのビット列"s5 s4 s3 s2 s1 s0"を上位桁6ビットのビット列として複製し、当該ビット列を上位ビット列及び下位ビット列として含む12ビットの被加算数"s5 s4 s3 s2 s1 s0 s5 s4 s3 s2 s1 s0"を生成する。
【０１２２】
次に、モジュラスm2に対応して、7(=2(2-1)p+1)ビットの剰余値y2を6(=2(2-1)p)ビット上位桁側へシフトした値から当該剰余値y2を減じ、下位桁に"0 0 0 0"(=22-1p-(k-i+2) )ビットを付加したビット列"c11' c10' c9' c8' c7' c6' c5' c4' c3' c2' c1' c0' 0 0 0 0"を生成する。そして、式（２−８）に示したEAC処理を行い、12(=22p) ビットの部分ビット列"c7' c6' c5' c4' c3' c2' c1' c0' c11' c10' c9' c8'"を生成する。
【０１２３】
次に、上記の12ビットの被加算数"s5 s4 s3 s2 s1 s0 s5 s4 s3 s2 s1 s0"及び部分ビット列"c7' c6' c5' c4' c3' c2' c1' c0' c11' c10' c9' c8'"を12ビット加算器により加算し、モジュラスm0及びm1に対する加算と同様にEAC処理を行って、12ビットのビット列"t11 t10 t9 t8 t7 t6 t5 t4 t3 t2 t1 t0"をえる。
【０１２４】
以下同様にして、当該12ビットのビット列を上位桁12ビットに複製し、当該12ビットのビット列を上位ビット列及び下位ビット列として含む24ビットの被加算数を生成する。そして、当該被加算数に、モジュラスm3に対応するモジュラス対応変換値を加え、EAC処理を行うことにより、被変換数を２進数に変換した変換値を求めることができる。
【０１２５】
本実施形態に係る変換装置においては、以上に示したように、逆数の２進数表現が規則性をもつことを利用することにより、より少ないハードウェア量で高速に中国人の剰余定理を計算できる。
【０１２６】
図２は、本実施形態に係る変換装置１０の構成を示す。変換装置１０は、剰余系により表現された被変換数を２進数に変換する。この剰余系は、複数のモジュラスmiのそれぞれにより被変換数Yを割った複数の剰余値yiの組により、被変換数Yを表現するものである。一例として、本実施形態に係る変換装置１０は、この複数のモジュラスmiの組として、式（１−１８）に示したモジュラスセットSkを用いる。
【０１２７】
式（１−１８）に示したモジュラスセットSkにおける最小のモジュラスm0は、２の自然数pによるべき乗値から１を減じた２以上の自然数である。また、複数のモジュラスのうち最小でないモジュラスm1,…,mk+1のそれぞれは、２を自然数によりべき乗したべき乗値に１を加えた値をとる。ここで、当該べき乗値は、当該モジュラスより小さいモジュラスの積より大きい値をとり、当該モジュラスより小さいモジュラスの積より大きい最小のべき乗値2^(2i-1p)であってよい。
【０１２８】
本実施形態に係る変換装置１０は、剰余値と中国人の剰余定理における逆数との積である２進数のモジュラス対応変換値yi・βi・(M/mi)を、ビット列の複製により実現する。これにより変換装置１０は、被変換数Yを、少ないハードウェア量で高速に２進数に変換することができる。
【０１２９】
変換装置１０は、モジュラス対応変換値生成部１００と、モジュラス対応変換値加算部１３０とを備える。
モジュラス対応変換値生成部１００は、複数のモジュラスm0,…mk+1のそれぞれについて、当該モジュラスの剰余値yi(="α2^(i-1)p α2^(i-1)p-1 … α0")に当該モジュラスmi以外のモジュラスの積(M/mi)を乗じた値yi・ (M/mi)に基づいて、当該モジュラスに対応する２進数の値であるモジュラス対応変換値yi・βi・(M/mi)を生成する。
【０１３０】
モジュラス対応変換値生成部１００は、１又は複数の部分ビット列生成部１１０（１１０ａ〜ｄ）と、１又は複数の部分ビット列複製部１２０（１２０ａ〜ｄ）とを有する。部分ビット列生成部１１０ａ〜ｄのそれぞれは、当該部分ビット列生成部１１０に対応するモジュラスmiにより被変換数Yを割った剰余値yiに基づいて、当該モジュラスmiに対応するモジュラス対応変換値yi・βi・(M/mi)の一部となる部分ビット列(="α2^ip-1' α2^ip-2' … α0')を生成する。ここで、最小のモジュラスm0に対応する部分ビット列生成部１１０ａは、部分ビット列として、y0(="ap-1 ap-2 … a0")の値を出力する。一方、最小でないモジュラスmiに対応する部分ビット列生成部１１０ｂ〜ｄは、部分ビット列として、剰余値yiに(2^(2^i-1p)-1)（="00..0100..0(-1)"）を乗じた値を出力する。
【０１３１】
部分ビット列複製部１２０ａ〜ｄのそれぞれは、当該部分ビット列複製部１２０に対応するモジュラス対応変換値yi・βi・(M/mi)の複数箇所に部分ビット列生成部１１０が生成した部分ビット列を複製する。これにより部分ビット列複製部１２０は、部分ビット列に当該モジュラスmiを乗じたモジュラス対応変換値yi・βi・(M/mi)を生成する。ここで、最大のモジュラスmk+1に対応する部分ビット列複製部１２０ｄは、部分ビット列生成部１１０が生成したビット列を、モジュラス対応変換値yk+1・βk+1・(M/m k+1)の１箇所に複製する。
【０１３２】
モジュラス対応変換値加算部１３０は、複数のモジュラスm0,…mk+1のそれぞれについてのモジュラス対応変換値を加算して、２進数の被変換数bin Yを算出する。なお、以上に示した各部分ビット列生成部１１０及び各部分ビット列複製部１２０は、モジュラス毎に別個の回路により実現されるのが望ましいが、これに代えて同一の回路を用いてモジュラス毎に順次処理する構成を採ることもできる。
なお、被変換数Yの各剰余値yiの組は、モジュラスセットSkの順序と異なる並びで入力されてもよい。この場合、変換装置１０は、複数の剰余値yiの順序をモジュラスセットSkの順序に並べ替える剰余値並べ替え部を更に備えてもよい。
【０１３３】
図３は、本実施形態に係る部分ビット列生成部１１０の構成を示す。図３に示した部分ビット列生成部１１０は、最小で無い各モジュラスm1,…mk+1に対応して設けられ、当該モジュラスmiについての剰余値yi(="α2^(i-1)p α2^(i-1)p-1 … α0")から、部分ビット列 (="α2^ip-1' α2^ip-2' … α0'")を生成する。この部分ビット列は、式（２−４）におけるビット列"c2^ip-1' c2^ip-2' … c0'"に対応する。
【０１３４】
部分ビット列生成部１１０は、補数演算器２００と、加算器２１０とを含む。補数演算器２００は、モジュラスmiに対応する2i-1p+1ビットの剰余値yi(="α2^(i-1)p α2^(i-1)p-1 … α0")を入力し、当該剰余値yiの補数を算出する。本実施形態に係る補数演算器２００は、当該剰余値yiの２の補数である2ipビットのビット列を出力する。
【０１３５】
加算器２１０は、剰余値yi(="α2^(i-1)p α2^(i-1)p-1 … α0")の下位2i-1pビットに補数演算器２００が出力した補数の上位2i-1pビットを加える。そして加算器２１０は、加算結果を補数の下位2i-1pビットの上位桁に付加して、2ipビットの部分ビット列(="α2^ip-1 α2^ip-2 … α0")を生成する。これにより、加算器２１０は、剰余値yi(="α2^(i-1)p α2^(i-1)p-1 … α0")を当該モジュラスmiに対応する自然数分のビット数2i-1pだけ上位桁側にシフトした値から、当該剰余値を減じた値となる部分ビット列を生成することができる。
【０１３６】
図４は、本実施形態に係る部分ビット列複製部１２０の構成を示す。部分ビット列複製部１２０は、複製器３００と、ＥＡＣ演算器３１０とを含む。最小のモジュラスm0に対応する複製器３００は、式（２−３）に示したように、当該モジュラスm0に対応するモジュラス対応変換値の複数箇所、より具体的には2k+1箇所に、部分ビット列をpビット間隔で複製する。最小及び最大でないモジュラスmiに対応する複製器３００は、式（２−４）で示したように、当該モジュラスmiに対応するモジュラス対応変換値の複数箇所、より具体的には2k-i+1箇所に、部分ビット列を2i・pビット間隔で複製する。これにより複製器３００は、2k-i+1個の部分ビット列を結合する。このようにして得られるビット列は、下位ビットに2i-1p-(k-i+2)ビットの値を付加すればモジュラス対応変換値yi・βi・(M/mi)となる値をとる。最大のモジュラスmk+1に対応する複製器３００は、式（２−１ｄ）からわかるように、当該モジュラスmiに対応するモジュラス対応変換値の１箇所に、部分ビット列を複製する。
【０１３７】
ＥＡＣ演算器３１０は、式（２−８）に示したように、複製器３００が出力したビット列の上位2i-1p-(k-i+2)ビットを、当該ビット列の下位ビット側に循環シフトすることによりEAC処理を行う。これにより、ＥＡＣ演算器３１０は、EAC処理済みのモジュラス対応変換値yi・βi・(M/mi)を得ることができる。
【０１３８】
以上に示した部分ビット列複製部１２０によれば、部分ビット列を複数箇所に複製し、上位ビットを下位ビットに移動させることにより、モジュラス対応変換値yi・βi・(M/mi)を得ることができる。したがって、部分ビット列複製部１２０は、乗算器や加算器等の演算回路を用いることなく、部分ビット列の複製及び一部のビットの移動によりモジュラス対応変換値yi・βi・(M/mi)を生成することができ、少ないハードウェア量で高速に処理を行うことができる。
【０１３９】
図５は、本実施形態に係る変換装置１０の動作フローを示す。
まず、複数の部分ビット列生成部１１０のそれぞれは、対応する剰余桁についての剰余値yiに基づいて、当該剰余桁に対応する部分ビット列を生成する（Ｓ４００）。
【０１４０】
次に、複数の部分ビット列複製部１２０のそれぞれは、対応する剰余桁についての部分ビット列を複製してEAC処理を行う（Ｓ４１０）。この処理により部分ビット列複製部１２０は、被変換数Yの当該モジュラスmiによる剰余値yiに、当該モジュラスmiに対応する剰余値が１かつ他のモジュラスに対応する剰余値が０となる２進数の値、すなわち式（１−１４）のｂ）等の値を乗じて、当該剰余桁についてのモジュラス対応変換値yi・βi・(M/mi)を生成することができる。
【０１４１】
そして、モジュラス対応変換値加算部１３０は、全てのモジュラス対応変換値を加算していくことにより合計を算出し、被変換数Yの２進表現として出力する。
【０１４２】
以上に示した変換装置１０によれば、剰余系の被変換数Yを、少ないハードウェア量で高速に２進数に変換することができる。
【０１４３】
以上に代えて変換装置１０は、一部のモジュラスについてのみビット列の複製を用いてモジュラス対応変換値を求めてもよい。すなわち、２を自然数によりべき乗した、当該モジュラスより小さいモジュラスの積より大きいべき乗値に、１を加えた値をとるあるモジュラスmiが存在する場合に、当該モジュラスmiより小さいモジュラスmjについて上記のＳ４１０の処理を行ってもよい。
【０１４４】
図６は、本実施形態の変形例に係る変換装置１０の構成を示す。本変形例に係る変換装置１０は、剰余系により表現された被変換数を２進数に変換する。この剰余系は、図２に関連して説明した剰余系と同様である。
【０１４５】
本変形例に係る変換装置１０は、各モジュラスに対応する部分ビット列を加算していく際に、部分和の下位ビット列を上位ビット列に複製した被加算数を用いる。これにより、変換装置１０は、各モジュラスに対応する剰余値のビット数に合わせて加算器のビット数を低減することができ、剰余系の被変換数Yを、少ないハードウェア量で高速に２進数に変換することができる。
【０１４６】
変換装置１０は、１又は複数の部分ビット列生成部１１０（１１０ａ〜ｄ）と、モジュラス対応変換値加算部６００とを備える。部分ビット列生成部１１０のそれぞれは、複数のモジュラスm0,…,mk+1のそれぞれについて、当該モジュラスmiに対応するモジュラス対応変換値yi・βi・(M/mi)の少なくとも一部に含まれる部分ビット列(="α2^ip-1 α2^ip-2 … α0")を生成する。このモジュラス対応変換値は、図１の変換装置１０と同様に、複数のモジュラスのうち当該モジュラス以外のモジュラスを乗じた値に基づく２進数の値である。ここで、本変形例に係る部分ビット列生成部１１０は、図２及び図３に示した部分ビット列生成部１１０と同一の機能及び構成を採るため、説明を省略する。
【０１４７】
モジュラス対応変換値加算部６００は、複数のモジュラスm0,…,mk+1のそれぞれについての部分ビット列に基づいて、複数のモジュラスm0,…,mk+1のそれぞれについてのモジュラス対応変換値yi・βi・(M/mi)を加算した２進数の被変換数を算出する。モジュラス対応変換値加算部６００は、１又は複数の下位ビット列複製部６１０（６１０ａ、６１０ｂ、６１０ｃ、…）と、１又は複数のビット列加算部６２０（６２０ａ、６２０ｂ、…、６２０ｄ）とを有する。
【０１４８】
それぞれの下位ビット列複製部６１０は、複数のモジュラスm0,…,mk+1のうち最小でないモジュラスm1,…,mk+1のそれぞれに対応して設けられる。下位ビット列複製部６１０は、図１に示したように、対応するモジュラスmiより小さい全てのモジュラスに対応するモジュラス対応変換値y0・β0・(M/m0)、…、yi-1・βi-1・(M/mi-1)の和である第１の部分和の一部に含まれる予め定められたビット数の下位ビット列を、当該下位ビット列より上位桁の上位ビット列として複製する。これにより下位ビット列複製部６１０は、同一の上位ビット列及び下位ビット列を含む被加算数を生成する。この際、モジュラスm1に対応して設けられた下位ビット列複製部６１０ａは、第１の部分和の下位ビット列として、部分ビット列生成部１１０ａが出力した剰余値y0のビット列を用いる。
【０１４９】
それぞれのビット列加算部６２０は、複数のモジュラスm0,…,mk+1のうち最小でないモジュラスm1,…,mk+1のそれぞれに対応して設けられる。ビット列加算部６２０は、図１に示したように、対応するモジュラスmiについて下位ビット列複製部６１０により生成された被加算数に、当該モジュラスmiに対応して部分ビット列生成部１１０により生成された部分ビット列を加算する。これによりビット列加算部６２０は、当該モジュラスmiより小さい全てのモジュラスm0,…,mi-1について算出された第１の部分和に、当該モジュラスmiについてのモジュラス対応変換値を加えた第２の部分和の、少なくとも一部に含まれる下位ビット列を算出する。この下位ビット列は、モジュラスm0,…,miについて算出された部分和の下位ビット列として、当該モジュラスmiの次に大きいモジュラスmi+1に対応する下位ビット列複製部６１０に入力される。そして、最大のモジュラスmk+1に対応するビット列加算部６２０ｄにより算出されたビット列は、全てのモジュラス対応変換値の和となり、被変換数の２進数表現bin Yとして出力される。
【０１５０】
図７は、本実施形態の変形例に係る下位ビット列複製部６１０の構成を示す。下位ビット列複製部６１０は、対応するモジュラスmiより小さい全てのモジュラスに対応するモジュラス対応変換値y0・β0・(M/m0)、…、yi-1・βi-1・(M/mi-1)の和である第１の部分和の下位ビット列を入力する。そして、このp・2i-1ビットの下位ビット列を、当該下位ビット列より上位桁のp・2i-1ビットの上位ビット列として複製して、p・2iビットの被加算数を生成する。
【０１５１】
以上に示した下位ビット列複製部６１０によれば、モジュラスmiに対応する部分ビット列と同一ビット数の被加算数をビット列の複製により生成することができる。
【０１５２】
図８は、本実施形態の変形例に係るビット列加算部６２０の構成を示す。ビット列加算部６２０は、加算器８００と、ＥＡＣ演算器８１０とを含む。加算器８００は、図１に示したように、対応するモジュラスmiについての被加算数に、当該モジュラスmiに対応するモジュラス対応変換値における下位p・2iビットの部分ビット列を加算する。ＥＡＣ演算器８１０は、加算により被加算数及び部分ビット列のビット数を越える桁あふれが生じた場合に、式（２−８）及び図１に示したように、加算の結果得られたビット列における、被加算数と同一ビット数の下位ビット列の下位ビットに、桁あふれしたビットを加えることによりEAC処理を行う。
【０１５３】
以上に示したビット列加算部６２０によれば、第１の部分和に当該モジュラスmiについてのモジュラス対応変換値yi・βi・(M/mi)を加えた第２の部分和におけるp・2iビットの下位ビット列を算出することができる。
【０１５４】
図９は、本実施形態の変形例に係る変換装置１０の動作フローを示す。
まず、複数の部分ビット列生成部１１０のそれぞれは、対応する剰余桁についての剰余値yiに基づいて、当該剰余桁に対応する部分ビット列を生成する（Ｓ４００）。次に、モジュラス対応変換値加算部６００は、最小でないモジュラスm1,…,mk+1のそれぞれに対応してＳ９１０からＳ９３０の処理を繰り返す（Ｓ９００、Ｓ９４０）。
【０１５５】
繰返し処理において、処理対象のモジュラスmiに対応する下位ビット列複製部６１０は、i-1番目の部分和の下位ビット列を上位ビット列に複製して、i番目の被加算数を生成する（Ｓ９１０）。次に、処理対象のモジュラスmiに対応するビット列加算部６２０は、i番目の被加算数に、i番目の部分ビット列を加算する（Ｓ９２０）。そして、ビット列加算部６２０は、加算結果に対しEAC処理を行い、i番目の部分和の下位ビット列を生成する（Ｓ９３０）。
【０１５６】
以上の処理を繰り返すことにより（Ｓ９４０）、最終段のビット列加算部６２０から全てのモジュラス対応変換値の和を出力することができる。
【０１５７】
一例として、p=3, k=2とし、モジュラスセットをSk ={m0, m1, m2, m3} = {7(=23-1), 9(=23+1), 65(=26+1), 4097(=212+1)}とした場合において、この剰余系で表現された被変換数(y0、 y1、 y2、 y3) = (5、 6、47、3125)に中国人の剰余定理を適用して２進数表現に変換する計算を示す。各剰余値の２進数表現は、y0=”101”、 y1=”110”、 y2 = “101111”、 y3 = “110000110101”である。
【０１５８】
まず、補数演算器２００は、y1、 y2、 y3について、２の補数 (-y1)= “111010”、 (-y2)= “111111010001”、 (-y3)= “111111111111001111001011”を算出する。次に、加算器２１０は、(-y1)のMSB側にy1を加算して、部分ビット列“101010”をえる。同様に、加算器２１０は、(-y2)のMSB側、(-y3)のMSB側にy2、 y3を加算し、部分ビット列“101110010001”、 “110000110100001111001011”をえる。加算器２１０は、前述した性質１にもとづいて、y2・β2・(M/m2) については4ビット、 y3・β3・(M/m3)については11ビットのEAC処理を行う。これにより、加算器２１０は、EAC処理済みの部分ビット列 “100100011011”及び“000111100101111000011010”をえる。これが、中国人の剰余定理における乗算部 の部分積に相当する。
【０１５９】
次に、下位ビット列複製部６１０ａは、y0=“101”を２箇所に複製して被加算数“101101”とする。ビット列加算部６２０ａは、当該被加算数と部分ビット列“101010”を加算したビット列”1010111”のMSBをEAC処理し、モジュラスm1に対応する部分和（部分和１）の下位ビット列”011000”をえる。
【０１６０】
次に、下位ビット列複製部６１０ｂは、この部分和１を２箇所に複製して被加算数”011000011000”とする。ビット列加算部６２０ｂは、当該被加算数と部分ビット列“100100011011”を加算したビット列”111100110011”をえる。13ビット目にキャリーが発生していないので、EAC処理は不要となり、このビット列がモジュラスm2に対応する部分和（部分和２）の下位ビット列となる。
【０１６１】
次に、下位ビット列複製部６１０ｃは、この部分和２を２箇所に複製して被加算数”111100110011111100110011”とする。ビット列加算部６２０ｃは、当該被加算数と部分ビット列“000111100101111000011010”を加算したビット列”1000100011001110101001101”のMSBをEAC処理し、被変換数を２進数に変換した24ビットの数値”000100011001110101001110”をえる。この数値を１０進数で表現すると1154382となり、この数値が(y0、 y1、 y2、 y3) = (5、 6、47、3125)にたいする中国人の剰余定理の計算結果となる。
【０１６２】
以上に示した変換装置１０によれば、モジュラス対応変換値加算部６００は、各モジュラスmiに対応して被加算数及び部分ビット列を加算するために、被加算数及び部分ビット列のビット数に応じたビット数の加算器８００を用いることができる。すなわち、ビット列加算部６２０は、第１のモジュラスmi1について、p・2i1ビットの被加算数に、モジュラス対応変換値におけるp・2i1ビットの部分ビット列を加算するp・2i1ビットの加算器２１０と、第２のモジュラスmi2について、p・2i2ビットの被加算数に、モジュラス対応変換値におけるp・2i2ビットの部分ビット列を加算するp・2i2ビットの加算器２１０とを別個に用意しておくことができる。これにより、値が小さいモジュラスについては少ないビット数の加算器を使用することができ、少ないハードウェア量でより高速に被変換数の変換を行うことができる。
【０１６３】
以上に代えて変換装置１０は、一部のモジュラスについてのみビット列の複製を用いて被加算数を求めてもよい。すなわち、ある第１のモジュラスmiについて、下位ビット列複製部６１０は、第１のモジュラスmiより小さい少なくとも１つのモジュラスに対応するモジュラス対応変換値の和である第１部分和の一部に含まれる下位ビット列を上位ビット列として複製し、同一の上位ビット列及び下位ビット列を含む被加算数を生成してもよい。この場合、ビット列加算部６２０は、この被加算数に、第１のモジュラスmiに対応する部分ビット列を加算して、第２の部分和の少なくとも一部に含まれるビット列を生成する。
【０１６４】
図１０は、本実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。本実施形態に係るコンピュータ１９００は、ホスト・コントローラ２０８２により相互に接続されるＣＰＵ２０００、ＲＡＭ２０２０、グラフィック・コントローラ２０７５、及び表示装置２０８０を有するＣＰＵ周辺部と、入出力コントローラ２０８４によりホスト・コントローラ２０８２に接続される通信インターフェイス２０３０、ハードディスクドライブ２０４０、及びＣＤ−ＲＯＭドライブ２０６０を有する入出力部と、入出力コントローラ２０８４に接続されるＲＯＭ２０１０、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０を有するレガシー入出力部とを備える。
【０１６５】
ホスト・コントローラ２０８２は、ＲＡＭ２０２０と、高い転送レートでＲＡＭ２０２０をアクセスするＣＰＵ２０００及びグラフィック・コントローラ２０７５とを接続する。ＣＰＵ２０００は、ＲＯＭ２０１０及びＲＡＭ２０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィック・コントローラ２０７５は、ＣＰＵ２０００等がＲＡＭ２０２０内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置２０８０上に表示させる。これに代えて、グラフィック・コントローラ２０７５は、ＣＰＵ２０００等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。
【０１６６】
入出力コントローラ２０８４は、ホスト・コントローラ２０８２と、比較的高速な入出力装置である通信インターフェイス２０３０、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０を接続する。通信インターフェイス２０３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ２０４０は、コンピュータ１９００内のＣＰＵ２０００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ２０６０は、ＣＤ−ＲＯＭ２０９５からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。
【０１６７】
また、入出力コントローラ２０８４には、ＲＯＭ２０１０と、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０の比較的低速な入出力装置とが接続される。ＲＯＭ２０１０は、コンピュータ１９００が起動時に実行するブート・プログラムや、コンピュータ１９００のハードウェアに依存するプログラム等を格納する。フレキシブルディスク・ドライブ２０５０は、フレキシブルディスク２０９０からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。入出力チップ２０７０は、フレキシブルディスク・ドライブ２０５０や、例えばパラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を接続する。
【０１６８】
ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供されるプログラムは、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ２０２０を介してコンピュータ１９００内のハードディスクドライブ２０４０にインストールされ、ＣＰＵ２０００において実行される。
【０１６９】
コンピュータ１９００にインストールされ、コンピュータ１９００を図２に示した変換装置１０として機能させるプログラムは、部分ビット列生成モジュール及び部分ビット列複製モジュールを有するモジュラス対応変換値生成モジュールと、モジュラス対応変換値加算モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、１又は複数の部分ビット列生成部１１０及び１又は複数の部分ビット列複製部１２０を有するモジュラス対応変換値生成部１００と、モジュラス対応変換値加算部１３０としてそれぞれ機能させる。部分ビット列生成モジュールは、補数演算プログラムと、加算プログラムとを含む。これらのプログラムは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、補数演算器２００及び加算器２１０としてそれぞれ機能させる。部分ビット列複製モジュールは、複製プログラムと、ＥＡＣ演算プログラムとを含む。これらのプログラムは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、複製器３００及びＥＡＣ演算器３１０としてそれぞれ機能させる。
【０１７０】
また、コンピュータ１９００にインストールされ、コンピュータ１９００を図６に示した変換装置１０として機能させるプログラムは、部分ビット列生成モジュールと、下位ビット列複製モジュール及びビット列加算モジュールを有するモジュラス対応変換値生成モジュールと、モジュラス対応変換値加算モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、１又は複数の部分ビット列生成部１１０と、１又は複数の下位ビット列複製部６１０及びビット列加算部６２０を有するモジュラス対応変換値加算部６００としてそれぞれ機能させる。ビット列加算モジュールは、加算プログラムと、ＥＡＣ演算プログラムとを含む。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、加算器８００及びＥＡＣ演算器８１０としてそれぞれ機能させる。
【０１７１】
以上に示したプログラム又はモジュールは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５の他に、ＤＶＤやＣＤ等の光学記録媒体、ＭＯ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ１９００に提供してもよい。
【０１７２】
図１１は、図６に示した変換装置１０の回路規模及び計算時間を、従来技術（非特許文献２）における計算方法と比較した結果を示す。ここでは、1ビット半加算器のトランジスタ数(約15トランジスタ)を1HA、1ビット半加算器の遅延を1Dとして比較する。この場合、1ビット全加算器の回路規模及び遅延はそれぞれ2HA及び 2Dとなる。補数演算については、従来技術及び変換装置１０において共通して行われるため、省略する。
【０１７３】
モジュラスセットがSk ={m0, m1, m2, m3} = {7(=23-1)、 9(=23+1)、 65(=26+1)、 4097(=212+1)}の場合、従来技術においては、24ビットの全加算器が３段とEAC処理のための半加算器(12ビット)が３段必要となり、回路規模は24×2HA×3+12HA×3 = 180HAとなる。また、非特許文献２においては、遅延量は、(24ビット加算器の遅延３段分)＋（EACの遅延）= 24×2D×3+12×1D = 156Dとなる。
【０１７４】
これに対し、変換装置１０によれば、回路規模は(6ビット全加算器)＋(12ビット全加算器)＋(24ビット全加算器)＋(3ビットEAC)＋(6ビットEAC)＋(12ビットEAC)  ＋(3ビットEAC)＋(6ビットEAC)＋(12ビットEAC) = 6×2HA+12×2HA+24×2HA+3HA+6HA+12HA +3HA+6HA+12HA = 126HAとなる。また、遅延は、(6ビット加算器の遅延)＋(12ビット加算器の遅延) ＋(24ビット加算器の遅延)＋（12ビットEACの遅延）＋（12ビットEACの遅延）= 6×2D + 12×2D+24×2D+12×1D +12×1D = 108Dとなる。
【０１７５】
したがって、上記のモジュラスセットを用いた場合、変換装置１０は、従来技術に対して回路規模を30%縮小し、遅延を30%短縮することができる。また、任意のp、kを考慮した場合、従来技術は、回路規模及び遅延がkに比例して大きくなっていく。これに対し、変換装置１０においては、回路規模及び遅延は(2+2-k)に比例する。したがって、変換装置１０は、kが大きくなるほど、従来技術と比較して回路規模及び遅延を小さくすることができる。
【０１７６】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【図面の簡単な説明】
【０１７７】
【図１】本発明の実施形態に係る中国人の剰余定理の計算方法の一例を示す。
【図２】本発明の実施形態に係る変換装置１０の構成を示す。
【図３】本発明の実施形態に係る部分ビット列生成部１１０の構成を示す。
【図４】本発明の実施形態に係る部分ビット列複製部１２０の構成を示す。
【図５】本発明の実施形態に係る変換装置１０の動作フローを示す。
【図６】本発明の実施形態の変形例に係る変換装置１０の構成を示す。
【図７】本発明の実施形態の変形例に係る下位ビット列複製部６１０の構成を示す。
【図８】本発明の実施形態の変形例に係るビット列加算部６２０の構成を示す。
【図９】本発明の実施形態の変形例に係る変換装置１０の動作フローを示す。
【図１０】本発明の実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。
【図１１】本発明の実施形態に係る変換装置１０と、従来技術との比較結果を示す。
【符号の説明】
【０１７８】
１０  変換装置
１００  モジュラス対応変換値生成部
１１０ａ〜ｄ  部分ビット列生成部
１２０ａ〜ｄ  部分ビット列複製部
１３０  モジュラス対応変換値加算部
２００  補数演算器
２１０  加算器
３００  複製器
３１０  ＥＡＣ演算器
６００  モジュラス対応変換値加算部
６１０ａ〜ｄ  下位ビット列複製部
６２０ａ〜ｄ  ビット列加算部
８００  加算器
８１０  ＥＡＣ演算器
１９００  コンピュータ
２０００  ＣＰＵ
２０１０  ＲＯＭ
２０２０  ＲＡＭ
２０３０  通信インターフェイス
２０４０  ハードディスクドライブ
２０５０  フレキシブルディスク・ドライブ
２０６０  ＣＤ−ＲＯＭドライブ
２０７０  入出力チップ
２０７５  グラフィック・コントローラ
２０８０  表示装置
２０８２  ホスト・コントローラ
２０８４  入出力コントローラ
２０９０  フレキシブルディスク
２０９５  ＣＤ−ＲＯＭ
【図１】
2006065116.tif 000050
【図２】
2006065116.tif 000051
【図３】
2006065116.tif 000052
【図４】
2006065116.tif 000053
【図５】
2006065116.tif 000054
【図６】
2006065116.tif 000055
【図７】
2006065116.tif 000056
【図８】
2006065116.tif 000057
【図９】
2006065116.tif 000058
【図１０】
2006065116.tif 000059
【図１１】
2006065116.tif 000060