(57)【要約】 【課題】  回路規模の増大を抑制しながら、効率的に、符号付き２進表現を求め得る演算装置を提供する。【解決手段】  乗数データは、最下位ビットから順に遅延処理部１１に入力され、Ｋ２、Ｋ１、Ｋ０とされる。Ｋ２、Ｋ１、Ｋ０が開始パターンに一致してから終了パターンに一致するまでの間、フリップフロップ１５１がセットされ、ウインドウ（window）がオープンとなる。ウインドウがオープンとなっているときは、Ｋ１の反転値がＥＸ−ＯＲ回路１６２から出力される。また、この間に、Ｋ２、Ｋ１、Ｋ０が負符号パターンに一致すると、ＡＮＤ回路１７１の出力が立ち上がり、ＯＲ回路１７２の出力が１となる。ＥＸ−ＯＲ回路１６２からの出力は、乗数データを符号付き２進数表現に変換したときの重みを与える。また、ＯＲ回路１７２からの出力は、乗数データを符号付き２進数表現に変換したときの符号を与える。【選択図】    図５
2005190323.tif 000002
【特許請求の範囲】
【請求項１】
２進数表現されたスカラー量を符号付き２進数表現に変換する演算装置であって、
前記２進数表現されたスカラー量を最下位ビットから順に検査して開始パターンを検出する開始パターン検出手段と、
前記２進数表現されたスカラー量を最下位ビットから順に検査して終了パターンを検出する終了パターン検出手段と、
前記２進数表現されたスカラー量を最下位ビットから順に検査して負符号パターンを検出する負符号パターン検出手段と、
前記開始パターンが検出されたビット位置と前記終了パターンが検出されたビット位置から反転区間を設定する反転区間設定手段と、
前記２進数表現されたスカラー量のビット列のうち、前記反転区間のビット値を反転させるとともに、その他の区間のビット値をそのまま維持する重み設定手段と、
前記開始パターンが検出されたビット位置と、前記反転区間内で且つ前記負符号パターンが検出されたビット位置とを負符号とし、その他の区間を正符号とする符号設定手段と、
を有することを特徴とする演算装置。
【請求項２】
２進数表現されたスカラー量を符号付き２進数表現に変換する演算装置であって、
前記２進数表現されたスカラー量を最下位ビットから順に検査して１が連続するビット区間の先頭のビット位置を検出する開始パターン検出手段と、
前記２進数表現されたスカラー量を最下位ビットから順に検査して０が連続するビット区間の先頭のビット位置を検出する終了パターン検出手段と、
前記２進数表現されたスカラー量を最下位ビットから順に検査して１に挟まれた０のビット位置を検出する負符号パターン検出手段と、
前記１が連続するビット区間の先頭のビット位置よりも１ビット上位のビット位置から前記０が連続するビット区間の先頭のビット位置までの区間を反転区間として設定する反転区間設定手段と、
前記２進数表現されたスカラー量のビット列のうち、前記反転区間のビット値を反転させるとともに、その他の区間のビット値をそのまま維持する重み設定手段と、
前記１が連続するビット区間の先頭のビット位置と、前記反転区間内で且つ前記１に挟まれた０のビット位置とを負符号とし、その他の区間を正符号とする符号設定手段と、
を有することを特徴とする演算装置。
【請求項３】
請求項１または２において、
前記重み設定手段は、前記スカラー量の最上位ビットが前記反転区間に含まれるとき、最上位ビットよりも１ビット上位に重み１の符号付き２進数表現のビット値を追加する、
ことを特徴とする演算装置。
【請求項４】
２進数表現されたスカラー量を符号付き２進数表現に変換する演算装置であって、
前記２進数表現されたスカラー量が最下位ビットから順に入力されるとともに、入力ビット列Ｋ２に対して１ビット遅延したビット列Ｋ１とさらに１ビット遅延したビット列Ｋ０を生成するビット列生成手段と、
前記ビット列Ｋ２、Ｋ１、Ｋ０があらかじめ設定された開始パターンに一致するとき検出信号を発する開始パターン検出手段と、
前記ビット列Ｋ２、Ｋ１、Ｋ０があらかじめ設定された終了パターンに一致するとき検出信号を発する終了パターン検出手段と、
前記ビット列Ｋ２、Ｋ１、Ｋ０があらかじめ設定された負符号パターンに一致するとき検出信号を発する負符号パターン検出手段と、
前記開始パターン検出信号と前記終了パターン検出信号に基づいてウインドウを設定するウインドウ設定手段と、
前記Ｋ１のビット列のうち、前記ウインドウの設定区間におけるビット値を反転させるとともに、その他の区間のビット値をそのまま維持する重み設定手段と、
前記Ｋ１のビット列のうち、前記開始パターンが検出されたビット位置と、前記ウインドウ設定区間内で且つ前記負符号パターンが検出されたビット位置とを負符号とし、その他の区間を正符号とする符号設定手段と、
を有することを特徴とする演算装置。
【請求項５】
請求項４において、
前記重み設定手段は、前記Ｋ１の最上位ビットが前記ウインドウ設定区間に含まれるとき、当該最上位ビットよりも１ビット上位に重み１の符号付き２進数表現のビット値を追加する、
ことを特徴とする演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算装置に関し、特に、所定のデータを暗号鍵により暗号化する際に用いて好適なものである。
【背景技術】
【０００２】
近年のコンピュータネットワークの発達により、電子メール、電子ニュース等の電子化された情報をネットワーク経由で送受信する機会が急速に増加してきている。さらに、かかるネットワークを利用して、オンラインショッピング等のサービスも提供されつつある。しかし、その一方で、ネットワーク上の電子化されたデータを盗聴・改竄し、あるいは、他人になりすまして不正にサービスの提供を受ける等の違法行為の問題が浮上してきている。
【０００３】
これらの問題に対し、暗号化技術を応用した暗号化電子メールや利用者認証システムが提案され、種々のネットワークに導入されつつある。コンピュータネットワークにおいて、暗号化技術は必須の技術になりつつある。
【０００４】
かかる暗号化技術は、大別すると、秘密鍵暗号系と公開鍵暗号系の２つに分類できる。「秘密鍵暗号系」は、送信者と受信者が同じ鍵を持つことにより、暗号通信を行う暗号化方式である。すなわち、あるデータを秘密鍵に基づいて暗号化して送信し、受け手側は、この秘密鍵を用いて暗号化データを復号し、暗号化のない元のデータを取得する。
【０００５】
また、「公開鍵暗号系」は、受信者側から公開されている公開鍵でデータを暗号化して送信し、受け手側は、この公開鍵とペアになっている秘密鍵で暗号化データを復号し、暗号化のない元のデータを取得するものである。すなわち、公開鍵で暗号化された暗号化データは、これとペアになっている秘密鍵でのみ復号でき、これにより、データの秘匿性を保持するものである。
【０００６】
「公開鍵暗号系」の中で、現在標準化が進んでいるものに、楕円曲線暗号（Elliptic Curve Cryptography）がある。これは、楕円曲線の離散対数問題に基づくもので、N.Koblitz（非特許文献１参照）と、V.Miller（非特許文献２参照）により提案された。
【０００７】
かかる楕円曲線暗号に用いる主な楕円曲線は、素体上の楕円曲線（標準形：y2=X3+aX+b(mod p), p：素数）と、２次拡大体上の楕円曲線（標準形：y2+xy=X3+aX2+b(mod f), f：既約多項式）である。この楕円曲線状のP(x,y)および単位元となる無限遠点Ｏの集合は、加算に関して群をなす。楕円曲線暗号は、この点の集合による離散対数問題に基づく暗号である。
【０００８】
楕円曲線上の点に関する演算は以下のものが定義されている。
加算：  Ｒ＝Ｐ＋Ｑ＝Ｑ＋Ｐ
２倍算：  Ｒ＝２Ｐ＝Ｐ＋Ｐ
減算：  Ｒ＝Ｐ−Ｑ
零点：  ０＝Ｐ−Ｐ
スカラー倍算：ｋＰ＝Ｐ＋Ｐ＋Ｐ＋…＋Ｐ（ｋ個のＰの和）
【０００９】
ここで、ｋＰとＰからｋを演算することは困難である。このことは、楕円曲線の離散対数問題と呼ばれており、この離散対数問題に関連する計算の困難性に基づいて、公開鍵暗号系の暗号を構成することができる。
【００１０】
ところで、上記の演算規則に従って、公開鍵暗号系として知られる有限体上のディフィーへルマン（Diffie-Hellman）鍵交換（送り手と受け手が互いに共通鍵を得るためのアルゴリズム）と同様の鍵交換を実現できる。
【００１１】
楕円曲線上のベースポイントをＧとし、送り手Ａの秘密鍵をＳａとし、その公開鍵ＰａをＰａ＝ＳａＧとする。一方、受け手Ｂの秘密鍵をＳｂとし、その公開鍵ＰｂをＰｂ＝ＳｂＧとする。このとき、送り手Ａは、受けてＢの公開鍵Ｐｂと自身の秘密鍵Ｓａから、共通鍵Ｋａｂ＝ＳａＰｂ＝ＳａＳｂＧを、演算により得ることができる。同様に、受け手Ｂは、送り手Ａの公開鍵Ｐａと自身の秘密鍵Ｓｂから、共通鍵Ｋｂａ＝ＳｂＰａ＝ＳｂＳａＧを、演算により得ることができる。
【００１２】
この鍵交換方式は、ＥＣＤＨ（Elliptic Curve Deffie-Hellman）方式と呼ばれている。この鍵交換方式では、共通鍵を得るために、秘密鍵Ｓａ、Ｓｂをスカラー量として楕円曲線上の点Ｇ、Ｐａ、Ｐｂに乗算する必要があるため、暗号化／複号の際に膨大な演算処理が必要となる。つまり、秘密鍵Ｓａ、Ｓｂに応じた回数だけ加算処理を繰り返す必要がある。
【００１３】
かかる処理を軽減するために、加算と２倍算、減算を組み合わせたサイドバイナリメソッド（非特許文献３参照）を用いて計算を行うことが提案されている。かかるサイドバイナリメソッドは、乗数ｋを符号付き２進表現し、これを最上位ビットから最下位ビットまで順に検査してゆき、そのビットの値が０であれば２倍算を行い、１であれば２倍算を行った後加算し、−１であれば減算するものである。
【００１４】
たとえば、乗数ｋをｋ＝８７とすると、乗数ｋは、符号付き２進表現でｋ＝１０１０１００１（１は、−１）と表わされる。このとき、サイドバイナリメソッドでｋＧを求めると、
ｋＧ＝（（２Ｇ×２−Ｇ）×２×２−Ｇ）×２×２×２−Ｇ＝８７Ｇ
となる。
【００１５】
乗数ｋを符号付き２進表現するための手法として、以下の非特許文献４に記載のものが知られている。かかる手法を実現するアルゴリズムを図６に示す。このアルゴリズムは、乗数ｋを２進表現したときの各ビットを、最下位ビットから最上位ビットまで順に検査し、検査結果に応じて当該ビットの値を求めている。
【００１６】
たとえば、乗数ｋをｋ＝８７とすると、乗数ｋは、２進表現でｋ＝０１０１０１１１と表現される。ここで、乗数ｋは奇数であるのでＳ１１、Ｓ１２からＳ１３へと進み、最下位ビットのサイドバイナリ（sb）が求められる。ここでは、２進表現されたｋの下位２ビットを１０進数で表現した値（ｋ＆３）を２から減算する演算がなされる。よって、最下位ビットのサイドバイナリ（sb）は、sb＝２−３＝−１となる。
【００１７】
このようにして得られたsbは負であるので、Ｓ１５からＳ１６へと進み、ｋ＝ｋ＋１＝０１０１１０００（２進数）を演算し、さらに、Ｓ１７にて、ｋ＝ｋ／２＝０１０１１００（２進数）を演算する。これにより最下位ビットの処理が終了し、Ｓ１１に戻って、最下位ビットよりも１桁上位のビットの処理を行う。
【００１８】
ここで、Ｓ１７で求めたｋ＝０１０１１００（２進数）は偶数であるので、Ｓ１１、Ｓ１２からＳ１４へと進み、当該ビットのサイドバイナリ（sb)は、sb＝０とされる。そして、Ｓ１７によってｋ＝ｋ／２＝０１０１１０（２進数）が演算され、当該ビットの処理が終了される。
【００１９】
以下、同様の処理を最上位ビットまで行う。これにより、乗数ｋの符号付き２進表現として、ｋ＝１０１０１００１（符号付２進数：１は−１）を得る。
【非特許文献１】“A course in number theory and cryptography”,Spring-Verlag,1997
【非特許文献２】“Use of elliptic curves in cryptography”,Advances in Cryptology-Proceedings of Crypto '85, Lecture Notes in Computer Science, 218 (1986), Spring-Verlag, pp417-426
【非特許文献３】F.Morain and J.Olivos, “Speeding up the computations on an elliptic curve using addition-subtraction chains”, Theoretical Informatics and Applications, vol.24, no.6, pp.531-544, 1990
【非特許文献４】M.Rosing, “Implementing Elliptic Curve Cryptography”, Manning, 1998
【発明の開示】
【発明が解決しようとする課題】
【００２０】
しかしながら、上記アルゴリズムに従うサイドバイナリ処理（図６）では、ｋ＝ｋ＋１の加算処理がまれており、この加算処理は最大で、（乗数ｋの２進表現ビット長＋１）ビットとなる。このため、上記サイドバイナリ処理をハードウエアにて実現しようとすると、乗数ｋの値が大きくなるにしたがって回路規模が増大する。暗号化処理においては、通常、乗数ｋである秘密鍵Ｓａ、Ｓｂの値が大きいため、上記アルゴリズムにて符号付き２進数を得ようとすると、回路規模が膨大となってしまうとの問題が生じる。
【００２１】
そこで、本発明は、回路規模の増大を抑制しながら、効率的に、符号付き２進表現を求め得る演算装置を提供することを課題とする。
【課題を解決するための手段】
【００２２】
請求項１の発明は、２進数表現されたスカラー量を符号付き２進数表現に変換する演算装置であって、前記２進数表現されたスカラー量を最下位ビットから順に検査して開始パターンを検出する開始パターン検出手段と、前記２進数表現されたスカラー量を最下位ビットから順に検査して終了パターンを検出する終了パターン検出手段と、前記２進数表現されたスカラー量を最下位ビットから順に検査して負符号パターンを検出する負符号パターン検出手段と、前記開始パターンが検出されたビット位置と前記終了パターンが検出されたビット位置から反転区間を設定する反転区間設定手段と、前記２進数表現されたスカラー量のビット列のうち、前記反転区間のビット値を反転させるとともに、その他の区間のビット値をそのまま維持する重み設定手段と、前記開始パターンが検出されたビット位置と、前記反転区間内で且つ前記負符号パターンが検出されたビット位置とを負符号とし、その他の区間を正符号とする符号設定手段とを有することを特徴とする。
【００２３】
請求項２の発明は、２進数表現されたスカラー量を符号付き２進数表現に変換する演算装置であって、前記２進数表現されたスカラー量を最下位ビットから順に検査して１が連続するビット区間の先頭のビット位置を検出する開始パターン検出手段と、前記２進数表現されたスカラー量を最下位ビットから順に検査して０が連続するビット区間の先頭のビット位置を検出する終了パターン検出手段と、前記２進数表現されたスカラー量を最下位ビットから順に検査して１に挟まれた０のビット位置を検出する負符号パターン検出手段と、前記１が連続するビット区間の先頭のビット位置よりも１ビット上位のビット位置から前記０が連続するビット区間の先頭のビット位置までの区間を反転区間として設定する反転区間設定手段と、前記２進数表現されたスカラー量のビット列のうち、前記反転区間のビット値を反転させるとともに、その他の区間のビット値をそのまま維持する重み設定手段と、前記１が連続するビット区間の先頭のビット位置と、前記反転区間内で且つ前記１に挟まれた０のビット位置とを負符号とし、その他の区間を正符号とする符号設定手段とを有することを特徴とする。
【００２４】
請求項３の発明は、請求項１または２に記載の演算装置において、前記重み設定手段は、前記スカラー量の最上位ビットが前記反転区間に含まれるとき、最上位ビットよりも１ビット上位に重み１の符号付き２進数表現のビット値を追加することを特徴とする。
【００２５】
請求項４の発明は、２進数表現されたスカラー量を符号付き２進数表現に変換する演算装置であって、前記２進数表現されたスカラー量が最下位ビットから順に入力されるとともに、入力ビット列Ｋ２に対して１ビット遅延したビット列Ｋ１とさらに１ビット遅延したビット列Ｋ０を生成するビット列生成手段と、前記ビット列Ｋ２、Ｋ１、Ｋ０があらかじめ設定された開始パターンに一致するとき検出信号を発する開始パターン検出手段と、前記ビット列Ｋ２、Ｋ１、Ｋ０があらかじめ設定された終了パターンに一致するとき検出信号を発する終了パターン検出手段と、前記ビット列Ｋ２、Ｋ１、Ｋ０があらかじめ設定された負符号パターンに一致するとき検出信号を発する負符号パターン検出手段と、前記開始パターン検出信号と前記終了パターン検出信号に基づいてウインドウを設定するウインドウ設定手段と、前記Ｋ１のビット列のうち、前記ウインドウの設定区間におけるビット値を反転させるとともに、その他の区間のビット値をそのまま維持する重み設定手段と、前記Ｋ１のビット列のうち、前記開始パターンが検出されたビット位置と、前記ウインドウ設定区間内で且つ前記負符号パターンが検出されたビット位置とを負符号とし、その他の区間を正符号とする符号設定手段とを有することを特徴とする。
【００２６】
請求項５の発明は、請求項４に記載の演算装置において、前記重み設定手段は、前記Ｋ１の最上位ビットが前記ウインドウ設定区間に含まれるとき、当該最上位ビットよりも１ビット上位に重み１の符号付き２進数表現のビット値を追加することを特徴とする。
【００２７】
本発明の特徴は、以下に示す実施の形態の説明により更に明らかとなろう。ただし、以下の実施の形態は、あくまでも、本発明の一つの実施形態であって、本発明ないし各構成要件の用語の意義は、以下の実施の形態に記載されたものに制限されるものではない。
【発明の効果】
【００２８】
本発明によれば、２進数表現されたスカラー量のビット値が開始パターン、終了パターン、負符号パターンに一致するかを検査し、検査結果に応じて、ビット値を反転処理し、あるいは、負符号を付加することにより、スカラー量を符号付き２進数表現に変換することができる。よって、上記図６のアルゴリズムにおいて示したような加算処理（ｋ＝ｋ＋１）が不要となり、スカラー量（乗数ｋ）の値が大きくなっても、演算装置のハードウエア構成が膨大になることはない。
【発明を実施するための最良の形態】
【００２９】
以下、本発明の実施の形態につき図面を参照して説明する。
【００３０】
まず、図１に実施の形態に係る演算装置の構成を示す。
【００３１】
なお、同図は、実施例に係る演算装置を機能ブロックとして示したものであり、ハードウェア的には、ＣＰＵ、メモリ、その他のＬＳＩなどによって実現でき、ソフトウェア的には、メモリにロードされた記録制御機能のあるプログラムなどによって実現できる。また、ハードウエアとソフトウエアの組合せによっても実現できることは言うまでもない。
【００３２】
図示のとおり、演算装置は、遅延処理部１１と、開始パターン検出部１２と、終了パターン検出部１３と、負符号パターン検出部１４と、ウインドウ設定部１５と、ビット反転処理部１６と、負符号負荷部１７とを備えている。
【００３３】
遅延処理部１１は、入力された乗数データ（１、０の符号列）を１ビットずつ遅延させてＫ０、Ｋ１、Ｋ２の符号列を生成する。ここで、Ｋ１はＫ２よりも１ビット遅延し、さらに、Ｋ０はＫ１よりも１ビット遅延している。なお、乗数データは最下位ビットから順に入力される。
【００３４】
開始パターン検出部１２は、Ｋ０、Ｋ１、Ｋ２が入力され、ビットクロックタイミング毎に、Ｋ０、Ｋ１、Ｋ２が開始パターン（図２参照）に一致するかを判別する。そして、開始パターンに一致すれば、後段のウインドウ設定部１５および負符号付加部１７にSet信号を出力する。
【００３５】
終了パターン検出部１３は、Ｋ０、Ｋ１、Ｋ２が入力され、ビットクロックタイミング毎に、Ｋ０、Ｋ１、Ｋ２が終了パターン（図２参照）に一致するかを判別する。そして、終了パターンに一致すれば、後段のウインドウ設定部１５にReset信号を出力する。
【００３６】
負符号パターン検出部１４は、Ｋ０、Ｋ１、Ｋ２が入力され、ビットクロックタイミング毎に、Ｋ０、Ｋ１、Ｋ２が負符号パターン（図２参照）に一致するかを判別する。そして、負符号パターンに一致すれば、後段の負符号付加部１７にSign信号を出力する。
【００３７】
ウインドウ設定部１５は、開始パターン検出部１２から検出信号（Set信号）の供給を受けたときから、終了パターン検出部１３から検出信号（Reset信号）の供給を受けるまでの間、ウインドウ信号（Window）を出力する。但し、ウインドウ信号（window）の出力中に、ウインドウ補正部１８から補正信号（msb）を受信したときは、ウインドウ信号（window）の出力を中止する。
【００３８】
ビット反転処理部１６は、ウインドウ設定部１５からウインドウ信号（window）を受信している期間、Ｋ１を反転して出力し、ウインドウ信号（window）を受信していない期間は、Ｋ１を反転せずにそのまま出力する。但し、ウインドウ補正部１８から補正信号（ｍｓｂ）を受信したときにウインドウ信号（window）が閉じていなければ、重み＝１を出力する。なお、かかる重み信号は、乗数データを符号付き２進表現したときの、各ビットの重みを表す。
【００３９】
負符号付加部１７は、開始パターン検出部１２から検出信号（Set信号）の供給を受けたとき、または、ウインドウ検出部１５からのウインドウ信号（window）がオープンのときに負符号パターン検出部１４から検出信号（Sign信号）の供給を受けたとき、負符号を出力し、これ以外のときは、正符号を出力する。なお、かかる符号信号は、乗数データを符号付き２進表現したときの、各ビットの符号を表す。
【００４０】
ウインドウ補正部１８は、Ｋ１の最上位ビットを検出したタイミングでウインドウ信号（window）が閉じているかを判別し、閉じていないときに、補正信号（msb）を出力する。
【００４１】
次に、上記演算装置の動作について、具体的変換例を例示して説明する。
【００４２】
図３に、乗数データとしてｋ＝８７＝０１０１０１１１（２進数）が入力されたときのタイミングチャートを示す。なお、乗数データは、演算装置に対して最下位ビットから順に入力される。また、図中、“ビット長カウンタ”の値は、たとえばウインドウ補正部１８に内蔵されたビット長カウンタのカウント値を示すものである。
【００４３】
乗数データが入力されると、Ｔ０においてビット長カウンタがリセットされ、ビット長のカウントが開始される。ビットタイミングＴ１において、Ｋ０、Ｋ１、Ｋ２が開始パターン（図２）に一致するため、開始パターン検出部１２から検出信号（Set）が出力される。かかる検出信号（Set）の出力を受けて、負符号付加部１７から、負符号（＝１）が出力される。このとき、ウインドウ設定部１５からはウインドウ信号（window）が未だ出力されていないため、ビット反転処理部１６からは、Ｋ１の値（＝１）がそのまま重みとして出力される。
【００４４】
次のビットタイミングＴ２では、Ｔ１における検出信号（Set）の出力を受けて、ウインドウ設定部１５からウインドウ信号（window）が出力される。これにより、ビット反転処理部１６における反転処理が開始される。すなわち、Ｋ１の反転値が重みとして出力される。かかる反転処理は、ウインドウ信号（window）がオフとされる直前のビットタイミングＴ８まで行われる。
【００４５】
ウインドウ信号が出力されているＴ２からＴ８までの期間のうち、Ｔ４とＴ６のビットタイミングにおいて、Ｋ０、Ｋ１、Ｋ２が負符号パターン（図２）に一致するため、負符号パターン検出部１７から検出信号（Sign）が出力される。よって、Ｔ４とＴ６のビットタイミングにおいて、負符号付加部１７から負符号（＝１）が出力される。
【００４６】
ビットタイミングＴ８においては、Ｋ０、Ｋ１、Ｋ２が終了パターン（図２）に一致するため、終了パターン検出部１３から検出信号（Sign）が出力される。この検出信号（Sign）の出力を受けて、ビットタイミングＴ９において、ウインドウ設定部１５におけるウインドウ信号（window）の出力が中止される。このため、ビットタイミングＴ９においては、ビット反転処理部１６におけるビット反転処理は行われず、Ｋ１の値がそのまま重みとして出力される。また、負符号付加部１７における負符号出力も行われず、Ｔ９における符号は正符号（＝０）とされる。
【００４７】
しかして、Ｔ９におけるビット長カウンタのカウント値が乗数データｋのビット長（＝８）に一致したことに応じて、乗数データｋの符号付き２進表現処理が終了される。かかる処理により、乗数データｋ＝８７＝０１０１０１１１（２進数）は、重みと符号によって符号付き２進表現に変換される。
【００４８】
なお、この変換例では、ビット長カウンタのカウント値が乗数データｋのビット長に達する前に終了パターンが検出される。かかる場合、符号付き２進数によって表現される乗数データは、終了パターンが検出されたタイミング（図３ではＴ８）のビット位置を最上位ビットとし、Ｋ１の最下位ビットが入力されたタイミング（図３ではＴ１）のビット位置を最下位ビットとするようにして構成される。よって、乗数データｋ＝８７＝０１０１０１１１（２進数）は、ｋ＝１０１０１００１（符号付２進数：１は−１）に変換される。
【００４９】
次に、他の具体例について、図４を参照して説明する。なお、同図は、乗数データｋ＝２１５＝１１０１０１１１（２進数）が入力されたときの変換動作を示すものである。
【００５０】
乗数データｋ＝２１５＝１１０１０１１１（２進数）の場合、Ｔ７までは、上述のｋ＝８７＝０１０１０１１１（２進数）の場合と同様にして処理が進められる。ただし、ビットタイミングＴ８においては、上記の場合と異なり、Ｋ０、Ｋ１、Ｋ２が終了パターン（図２）に一致しないため、終了パターン検出部１３からは検出信号（Sign）が出力されない。このため、ウインドウ設定部１５からのウインドウ信号（window）は、ビットタイミングＴ９においてもなお、オンのままである。
【００５１】
この場合、ビットタイミングＴ９において、ウインドウ補正部１８から補正信号（msb）が出力される。かかる補正信号（msb）の出力によって、ビット反転処理部１６から重み１が出力される。また、次のビットタイミングにおいてウインドウ信号（window）がオフとされる。
【００５２】
しかして、Ｔ９におけるビット長カウンタのカウント値が乗数データｋのビット長（＝８）に一致したことに応じて、乗数データｋの符号付き２進表現処理が終了される。かかる処理により、乗数データｋ＝２１５＝１１０１０１１１（２進数）は、重みと符号によって符号付き２進表現に変換される。
【００５３】
なお、この変換例では、終了パターンが検出されずにビット長カウンタのカウント値が乗数データｋのビット長に達する。かかる場合、符号付き２進数によって表現される乗数データは、補正信号（msb）が出力されたタイミング（図４ではＴ９）のビット位置を最上位ビットとし、Ｋ１の最下位ビットが入力されたタイミング（図３ではＴ１）のビット位置を最下位ビットとするようにして構成される。よって、乗数データｋ＝２１５＝１１０１０１１１（２進数）は、ｋ＝１００１０１００１（符号付２進数：１は−１）に変換される。
【００５４】
このように、本実施の形態によれば、Ｋ０、Ｋ１、Ｋ２の状態とビット長カウンタのカウント値を参照するのみで、乗数データを符号付き２進表現に変換できる。よって、上記図６のアルゴリズムに従う場合に比べ、演算装置の回路規模の増大を抑制しながら、効率的に、符号付き２進表現を求めることができる。
【実施例１】
【００５５】
上記実施の形態に示す演算装置をハードウエアにて構成したときの構成例を、図５に示す。
【００５６】
図示の如く、遅延処理部１１は、乗数データＫ２に対し１ビット遅延を行う２つの遅延回路１１１、１１２によって構成できる。また、開始パターン検出部１２、終了パターン検出部１３および負符号パターン検出部１４は、それぞれ、図２のパターンが入力されたときにＨレベル信号を出力するＮＡＮＤ回路１２１、１３１、１４１によって構成できる。
【００５７】
また、ウインドウ設定部１５は、ＮＡＮＤ回路１２１からのSet信号によってセットされ、ＮＡＮＤ回路１３１からのReset信号またはウインドウ補正部１８からの補正信号（msb）によってリセットされるフリップフロップ１５１と、ＯＲ回路１５２によって構成できる。
【００５８】
また、ビット反転処理部１６は、ウインドウ補正部１８からの補正信号（msb）がＬレベルのときＫ１に応じた出力を発するＮＡＮＤ回路１６１とＥＸ−ＯＲ回路１６２によって構成できる。
【００５９】
また、負符号付加部１７は、ウインドウ信号（window）がオンのときにＮＡＮＤ回路１４からのSign信号が入力されることによりＨレベルの信号を出力するＡＮＤ回路１７１と、ＯＲ回路１７２によって構成できる。
【００６０】
また、ウインドウ補正部１８は、上述のビット長カウンタ１８１と、ウインドウ信号（window）がオンのときにビット長カウンタ１８１からmsb信号が入力されることにより補正信号（msb）を出力するＡＮＤ回路１８２によって構成できる。
【００６１】
かかる回路構成により、上述した各部の処理および機能が実現される。すなわち、乗数データｋ＝８７＝０１０１０１１１（２進数）または乗数データｋ＝２１５＝１１０１０１１１（２進数）が入力されると、各部から、上記図３および図４のタイミングチャートに示す信号が出力され、これにより、符号付き２進表現への変換処理が実現される。
【００６２】
同図に示すように、本実施例では、乗数データを格納するためのレジスタを配備する必要がない。よって、乗数ｋの値が大きくなっても、演算装置のハードウエア構成が膨大になることもない。
【００６３】
以上、本発明に係る実施の形態について説明したが、本発明は係る実施の形態に限定されるものではなく、種々の変更が可能であることは言うまでもない。本発明の実施の形態は、特許請求の範囲に示された技術的思想の範囲内において、適宜、種々の変更が可能である。
【図面の簡単な説明】
【００６４】
【図１】実施の形態に係る演算装置の構成を示す図
【図２】実施の形態に係る各種パターンの内容を示す図
【図３】実施の形態に係る具体的変換例を示すタイミングチャート
【図４】実施の形態に係る具体的変換例を示すタイミングチャート
【図５】実施例に係る演算装置の構成を示す図
【図６】従来例に係る乗数ｋを符号付き２進表現するためのアルゴリズム
【符号の説明】
【００６５】
１１  遅延処理部
１２  開始パターン検出部
１３  終了パターン検出部
１４  負符号パターン検出部
１５  ウインドウ設定部
１６  ビット反転処理部
１７  負符号付加部
１８  ウインドウ補正部
【図１】
2005190323.tif 000003
【図２】
2005190323.tif 000004
【図３】
2005190323.tif 000005
【図４】
2005190323.tif 000006
【図５】
2005190323.tif 000007
【図６】
2005190323.tif 000008