(57)【要約】【課題】多項式次数比較器の処理時間を短縮する。【解決手段】次数比較器４２は、ｍビットのガロアフィールド上で入力値の逆数を演算する逆数演算器に使用される。第１レジスタ７０、第２レジスタ７２はそれぞれ、入力ビット列Ｕ，Ｖの次数を示す値ＤＥＧ＿Ｕ，ＤＥＧ＿Ｖを保持する。最上位セットビット検出器７４は、入力ビット列Ｕ，Ｖのそれぞれ次数を示す値ＤＥＧ＿Ｕ、ＤＥＧ＿Ｖを生成する。次数更新器７６は、第１レジスタ７０、第２レジスタ７２に次数を示す値ＤＥＧ＿Ｕ，ＤＥＧ＿Ｖを格納する。次数更新器７６は、（ａ）入力ビット列Ｕが右シフト演算されたとき、その右シフト量ＳＨＦ＿Ｕに応じて、第１レジスタ７０が保持する値ＤＥＧ＿Ｕを更新し、入力ビット列Ｖが右シフト演算されたとき、その右シフト量ＳＨＦ＿Ｖに応じて対応する第２レジスタ７２が保持する値ＤＥＧ＿Ｖを更新する。【選択図】図４
2016206438.tif 000002
【特許請求の範囲】
【請求項１】
ｍビットのガロアフィールド上で入力値の逆数を演算する逆数演算器に使用される多項式次数比較器であって、
ガロアフィールド上で法として使用すべき規約多項式をビットベクトル表現で表す入力ビット列Ｕの次数を示す値ＤＥＧ＿Ｕを保持する第１レジスタと、
入力ビット列Ｖの次数を示す値ＤＥＧ＿Ｖを保持する第２レジスタと、
前記入力ビット列Ｕ，Ｖのそれぞれ次数を示す値ＤＥＧ＿Ｕ、ＤＥＧ＿Ｖを生成する最上位セットビット検出器と、
前記第１レジスタ、前記第２レジスタに次数を示す値ＤＥＧ＿Ｕ，ＤＥＧ＿Ｖを格納する次数更新器と、
を備え、
前記次数更新器は、（ａ）前記入力ビット列Ｕが右シフト演算されたとき、その右シフト量ＳＨＦ＿Ｕに応じて、前記第１レジスタが保持する値ＤＥＧ＿Ｕを更新し、前記入力ビット列Ｖが右シフト演算されたとき、その右シフト量ＳＨＦ＿Ｖに応じて対応する前記第２レジスタが保持する値ＤＥＧ＿Ｖを更新することを特徴とする多項式次数比較器。
【請求項２】
前記次数更新器は、（ｂ）前記入力ビット列ＵとＶの排他的論理和演算が行われ、前記第１レジスタ、前記第２レジスタそれぞれが保持する値ＤＥＧ＿ＵとＤＥＧ＿Ｖが異なる場合、それらの次数を維持することを特徴とする請求項１に記載の多項式次数比較器。
【請求項３】
前記次数更新器は、（ｂ）前記入力ビット列ＵとＶの排他的論理和演算が行われ、前記第１レジスタ、前記第２レジスタそれぞれが保持する値ＤＥＧ＿ＵとＤＥＧ＿Ｖが等しい場合、前記入力ビット列ＵとＶのうち更新すべき一方の次数を前記最上位セットビット検出器により検出し、その出力に応じて、前記第１レジスタと前記第２レジスタのうち対応する一方が保持する値を更新することを特徴とする請求項１または２に記載の多項式次数比較器。
【請求項４】
前記最上位セットビット検出器は、
次数の検出対象である入力ビット列を一定のビット幅のサブビット列に分割し、上位側から順次、出力するビット列分割器と、
前記ビット列分割器から順次出力される前記サブビット列に対して、最上位から連続する０の個数を出力するサブ検出器と、
前記サブ検出器の検出結果を累積する積算器と、
を含み、
前記サブ検出器により１が検出されると、前記積算器の値を、次数を示す値として出力することを特徴とする請求項１から３のいずれかに記載の多項式次数比較器。
【請求項５】
前記ビット列分割器は、次数を示す値に応じて、最初に出力するサブビット列を決定することを特徴とする請求項４に記載の多項式次数比較器。
【請求項６】
請求項１から５のいずれかに記載の多項式次数比較器を備えることを特徴とする逆数演算器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ガロア体上の逆数演算器に関する。
【背景技術】
【０００２】
近年、楕円曲線暗号方式が注目を集めている。楕円曲線暗号方式は、従来主流となっているＲＳＡ方式と同程度のセキュリティを、より短いビット長のキーを用いて実現でき、また処理時間も短時間で済むという利点を有する。この特徴により、低消費電力が求められる組み込み機器への適用が期待される。
【０００３】
楕円曲線暗号方式では、１６０ビットから５１２ビット程度のビット長で表現される有限体（ガロアフィールドあるいはガロア体という）という体系での加減乗除演算を行う必要がある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００３−２７１０５６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
このうち、特に除算ならびに逆数演算は処理が複雑であることから、できるだけ除算を回避するアルゴリズムが考案されているが、すべての除算をなくすことはできず、除算処理には多くのサイクル数を要しており、ボトルネックとなっていた。所定の時間内で決められた処理を完了するためには、クロック数を高める必要があり、消費電力が増大する一因となっている。
【０００６】
本発明者は、除算もしくは逆数演算を実装するアルゴリズムとして、拡張ユークリッドアルゴリズムを用いることを検討した。ガロアフィールドＧＦ（２ｍ）上の逆数演算の場合、以下の処理が行われる。
（i）１６０ビットから５１２ビット程度のビット列のシフト処理
（ii）排他的論理和（ＸＯＲ）処理
（iii）多項式次数比較処理
【０００７】
多項式次数比較処理は、入力となる２つの多項式を表現するビット列について、それぞれ１が立っている最上位の位置（最上位セットビット）を検出し、より高い位置に１が立っているビット列の次数が高いと判定する。最上位セットビットの検出処理は、ビット列の最上位ビットから最下位ビットに向かって１ビットずつスキャンし、１が立っているビットを探索する。この処理は、シフト処理やＸＯＲ処理に比べて処理量が多いため、ボトルネックとなる。
【０００８】
本発明はかかる状況においてなされたものであり、そのある態様の例示的な目的のひとつは、短い処理時間で次数比較処理が可能な多項式次数比較器の提供にある。
【課題を解決するための手段】
【０００９】
本発明のある態様は、ｍビットのガロアフィールド上で入力値の逆数を演算する逆数演算器に使用される多項式次数比較器に関する。多項式次数比較器は、ガロアフィールド上で法として使用すべき規約多項式をビットベクトル表現で表す入力ビット列Ｕの次数を示す値ＤＥＧ＿Ｕを保持する第１レジスタと、入力ビット列Ｖの次数を示す値ＤＥＧ＿Ｖを保持する第２レジスタと、入力ビット列Ｕ，Ｖのそれぞれ次数を検出し、次数を示す値ＤＥＧ＿Ｕ、ＤＥＧ＿Ｖを出力する最上位セットビット検出器と、第１レジスタ、第２レジスタに次数を示す値ＤＥＧ＿Ｕ，ＤＥＧ＿Ｖを格納する次数更新器と、を備える。次数更新器は、（ａ）入力ビット列Ｕが右シフト演算されたとき、その右シフト量ＳＨＦ＿Ｕに応じて、第１レジスタが保持する値ＤＥＧ＿Ｕを更新し、入力ビット列Ｖが右シフト演算されたとき、その右シフト量ＳＨＦ＿Ｖに応じて対応する第２レジスタが保持する値ＤＥＧ＿Ｖを更新する。
【００１０】
右シフト演算が発生したときは、次数の変化量は、ビットシフト量と等しい。そこで右シフト演算をした場合は、膨大な演算を必要とする最上位セットビット検出器を用いずに、次数を計算することで、処理時間を短縮できる。
【００１１】
次数更新器は、（ｂ）入力ビット列ＵとＶの排他的論理和（ＸＯＲ)演算が行われ、第１レジスタ、第２レジスタそれぞれが保持する値ＤＥＧ＿ＵとＤＥＧ＿Ｖが異なる場合、それらの次数を維持してもよい。
ＸＯＲ演算の結果の次数は、入力ビット列ＵとＶの次数の高い方と同じになる。従ってこの場合には、第１レジスタと第２レジスタの値を維持することで、処理時間を短縮できる。
【００１２】
次数更新器は、（ｃ）入力ビット列ＵとＶの排他的論理和演算が行われ、第１レジスタ、第２レジスタそれぞれが保持する値ＤＥＧ＿ＵとＤＥＧ＿Ｖが等しい場合、入力ビット列ＵとＶのうち更新すべき一方の次数を最上位セットビット検出器により検出し、その出力に応じて、第１レジスタと第２レジスタのうち対応する一方が保持する値を更新してもよい。
【００１３】
最上位セットビット検出器は、次数の検出対象である入力ビット列を一定のビット幅のサブビット列に分割し、上位側から順次、出力するビット列分割器と、ビット列分割器から順次出力されるサブビット列に対して、最上位から連続する０の個数を出力するサブ検出器と、サブ検出器の検出結果を累積する積算器と、を含んでもよい。サブ検出器により１が検出されると、積算器の値を、次数を示す値として出力してもよい。
１が立つビットが検出された時点で、それ以降のサブビット列に対する繰り返し演算をやめることで、サイクル数を削減できる。
【００１４】
ビット列分割器は、次数を示す値に応じて、最初に出力するサブビット列を決定してもよい。
レジスタに格納される値が示す次数よりも上位のビットはすべてゼロである。そこですべてが０であることが分かっているサブビット列については、繰り返し演算の対象から除外することで、サイクル数を削減できる。
【００１５】
本発明の別の態様は、逆数演算器に関する。逆数演算器は、上述のいずれかの多項式次数比較器を備える。
【００１６】
なお、以上の構成要素の任意の組み合わせや、本発明の構成要素や表現を、方法、装置、システムなどの間で相互に置換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１７】
本発明のある態様によれば、少ないサイクル数で次数を比較可能となり、ひいては逆数演算を高速化できる。
【図面の簡単な説明】
【００１８】
【図１】実施の形態に係る逆数演算器のブロック図である。
【図２】図１の逆数演算器の具体的な構成例を示すブロック図である。
【図３】１／Ｚ回路の構成例を示すブロック図である。
【図４】次数比較器のブロック図である。
【図５】最上位セットビット検出器のブロック図である。
【図６】サブ検出器の入出力を示す真理値表である。
【図７】図７（ａ）は、最上位セットビット検出器の動作を示す図であり、図７（ｂ）は、ビット列分割器の動作を示す図である。
【発明を実施するための形態】
【００１９】
以下、本発明を好適な実施の形態をもとに図面を参照しながら説明する。各図面に示される同一または同等の構成要素、部材、処理には、同一の符号を付するものとし、適宜重複した説明は省略する。また、実施の形態は、発明を限定するものではなく例示であって、実施の形態に記述されるすべての特徴やその組み合わせは、必ずしも発明の本質的なものであるとは限らない。
【００２０】
図１は、実施の形態に係る逆数演算器１００のブロック図である。逆数演算器１００は、ｍビット（ｍは２以上の整数）のガロアフィールド上で、入力値Ｘの逆数Ｘ−１を演算する。逆数演算器１００は、それぞれが変数を格納するＵレジスタ１０、Ｖレジスタ１２、Ｇ１レジスタ１４、Ｇ２レジスタ１６と、各レジスタの値に所定の演算処理を施す演算処理部２０と、を備える。Ｕレジスタ１０、Ｖレジスタ１２、Ｇ１レジスタ１４、Ｇ２レジスタ１６それぞれのビット長は等しくｍである。
【００２１】
（概要）
逆数演算器１００の演算アルゴリズムの概要を説明する。
Ｕレジスタ１０、Ｖレジスタ１２それぞれに関して、最下位ビットから上位に向かってｙビットにわたり連続して０が含まれるとき、Ｕレジスタ１０、Ｖレジスタ１２をｙビット右シフトする。それと連動して、Ｖレジスタ１２、Ｇ１レジスタ１４に、ｙ回の１／Ｚ処理を行う。Ｕレジスタ１０、Ｖレジスタ１２の最下位ビットが両方１のとき、次数が高い方を、Ｕレジスタ１０とＶレジスタ１２の加算結果で更新する。またそれと連動して、Ｕレジスタ１０の次数が高いとき、Ｇ１レジスタ１４を、Ｇ１レジスタ１４とＧ２レジスタ１６の加算結果で更新し、Ｖレジスタ１２の次数が高いとき、Ｇ２レジスタ１６を、Ｇ１レジスタ１４とＧ２レジスタ１６の加算結果で更新する。これを繰り返し、逆数を演算する。
【００２２】
（レジスタ）
ガロアフィールド上において、法Ｆとして使用すべき規約多項式は、ビットベクトル表現で、演算処理部２０のＦレジスタ１８に格納されている。Ｕレジスタ１０は、その初期値として入力値Ｘを格納する。Ｖレジスタ１２は、その初期値として、Ｆレジスタ１８と同じ値を格納する。Ｇ１レジスタ１４は、その初期値として１を格納する。Ｇ２レジスタ１６は、初期値として０を格納する。
【００２３】
（演算処理部）
続いて、演算処理部２０の行う処理を説明する。
ステップ（i）
Ｕレジスタ１０の下位ｎビット（ｎ＜ｍ）を参照し、最下位ビットから上位に向かってｙビット（ｙ≦ｎ）にわたり０が連続するとき、Ｕレジスタ１０の値をｙビット右シフトする。本実施の形態ではｎ＝４の場合を説明する。
【００２４】
ステップ（ii）
ステップ（i）と連動して、Ｇ１レジスタ１４にｙ回、１／Ｚ処理を行う。
１／Ｚ処理は、その入力の最下位ビットが０である場合に、入力を１ビット右シフトした値を出力し、その入力の最下位ビットが１である場合にはその入力に法Ｆの値をガロアフィールド上で加算した後に１ビット右シフトした値を出力するものである。ガロアフィールド上における加算は、ＸＯＲ（排他的論理和）演算である。
【００２５】
ステップ（iii）
Ｕレジスタ１０の最下位ビットが０であるとき、ステップ（i）、(ii)を繰り返す。
【００２６】
ステップ（iv）
Ｖレジスタ１２の下位ｎビット（ｎ＜ｍ）を参照し、最下位ビットから上位に向かってｙビットにわたり０が連続するとき、Ｖレジスタ１２の値をｙビット右シフトする。
ステップ(v)
ステップ（iv）と連動して、Ｇ２レジスタにｙ回、１／Ｚ処理を行う。
【００２７】
ステップ（vi）
Ｖレジスタ１２の最下位ビットが０であるとき、ステップ（iv）、(v)を繰り返す。
【００２８】
ステップ（vii）
上述のステップ（i）〜(vi)の結果、Ｕレジスタ１０の最下位ビットとＶレジスタ１２の最下位ビットが両方１となったとき、Ｕレジスタ１０とＶレジスタ１２の次数を比較する。次数は、レジスタに格納される各ビットのうち、最上位の１が、最下位ビットから何ビット目に位置するかを表す。
【００２９】
ステップ（viii）
Ｕレジスタ１０とＶレジスタ１２のガロアフィールド上の加算を行い、加算結果をＵレジスタ１０とＶレジスタ１２のうち、次数が高い方に格納する。
【００３０】
ステップ（ix）
Ｇ１レジスタ１４とＧ２レジスタ１６のガロアフィールド上の加算を行う。そしてステップ（vii）においてＵレジスタ１０の次数の方が高いとき、加算結果をＧ１レジスタ１４に格納する。反対にステップ（vii）においてＶレジスタ１２の次数の方が高いとき、加算結果をＧ２レジスタ１６に格納する。
【００３１】
ステップ（x）
以上のステップ(i)〜（ix）を、Ｕレジスタ１０およびＶレジスタ１２の一方が１になるまで繰り返す。そしてＵレジスタ１０が１となったとき、Ｇ１レジスタ１４の値を求めるべき逆数Ｘ−１として出力し、Ｖレジスタ１２が１となったとき、Ｇ２レジスタ１６の値を求めるべき逆数Ｘ−１として出力する。
【００３２】
続いて演算処理部２０の構成例を説明する。
【００３３】
図２は、図１の逆数演算器１００の具体的な構成例を示すブロック図である。
演算処理部２０は、コントローラ２２、シフター回路３０、第１ＸＯＲゲート４０、次数比較器４２、１／Ｚ演算部５０、第２ＸＯＲゲート６０、第２セレクタ６２、第４セレクタ６６を備える。
【００３４】
コントローラ２２は、Ｕレジスタ１０およびＶレジスタ１２それぞれの下位ｎビットを参照し、それぞれについて、最下位ビットから連続する０の個数ｙを判定する。コントローラ２２は、ステップ（iii）に関連してＵレジスタ１０の最下位ビットが０か否か、ステップ（vi）に関連してＶレジスタ１２の最下位ビットが０か否かを判定する。
【００３５】
コントローラ２２は、判定結果にもとづいて、第１セレクタ３２、次数比較器４２、第３セレクタ６４を制御する。
【００３６】
シフター回路３０は、ステップ（i）（iii）（iv）（vi）に関連する処理を実行するよう構成される。具体的にはシフター回路３０は、第１セレクタ３２、マルチビットシフタ３４を含む。第１セレクタ３２は、Ｕレジスタ１０とＶレジスタ１２の値のうち、コントローラ２２から指示された一方を選択する。すなわち、コントローラ２２がＵレジスタ１０に関するステップ（i）を実行するとき、第１セレクタ３２はＵレジスタ１０を選択し、コントローラ２２がＶレジスタ１２に関する処理（iv）を実行するとき、第１セレクタ３２はＶレジスタ１２を選択する。
【００３７】
マルチビットシフタ３４には、コントローラ２２により検出されたビット数ｙが入力される。マルチビットシフタ３４は、第１セレクタ３２の出力を、ｙビット右シフトする。
【００３８】
次数比較器４２は、ステップ（vii）と関連して、Ｕレジスタ１０の次数ｄｅｇ（Ｕ）と、Ｖレジスタ１２の次数ｄｅｇ（Ｖ）を比較する。次数比較器４２の出力は、次数ｄｅｇ（Ｕ）の方が高いときにＵを示し、次数ｄｅｇ（Ｖ）の方が高いときにＶを示すものとする。
【００３９】
第１ＸＯＲゲート４０は、ステップ（vii）に関連する処理を行う。すなわち第１ＸＯＲゲート４０は、Ｕレジスタ１０とＶレジスタ１２のガロアフィールド上の加算であるＸＯＲ演算を行う。
【００４０】
第２セレクタ６２は、第１ＸＯＲゲート４０およびシフター回路３０の出力を受け、選択した一方を、Ｕレジスタ１０およびＶレジスタ１２に出力する。
Ｕレジスタ１０およびＶレジスタ１２は、それぞれのラッチイネーブル信号がアサートされると、その値が更新される。次数比較器４２の出力がＵを示すとき、Ｕレジスタ１０のラッチイネーブルがアサートされ、第２セレクタ６２の出力がＵレジスタ１０に格納される。反対に、次数比較器４２の出力がＶを示すとき、Ｖレジスタ１２のラッチイネーブルがアサートされ、第２セレクタ６２の出力がＶレジスタ１２に格納される。これにより、ステップ（viii）の処理が可能となる。
【００４１】
１／Ｚ演算部５０は、ステップ（ii）を実行するよう構成される。１／Ｚ演算部５０は、縦続接続されたｎ個の１／Ｚ回路５２と、第３セレクタ６４と、を含む。
１／Ｚ回路５２はそれぞれ、入力に対して１／Ｚ処理を施すよう構成されている。第３セレクタ６４は、Ｇ１レジスタ１４とＧ２レジスタ１６の値の一方を選択し、初段の１／Ｚ回路５２に出力する。コントローラ２２による制御下で、第３セレクタ６４はステップ（ii）においてＧ１レジスタ１４を選択し、ステップ（v）においてＧ２レジスタ１６を選択する。
【００４２】
第２ＸＯＲゲート６０は、ステップ（ix）に関連して、Ｇ１レジスタ１４とＧ２レジスタ１６のガロアフィールド上の加算を行う。
【００４３】
第４セレクタ６６は、１／Ｚ演算部５０の出力および第２ＸＯＲゲート６０の出力を受け、入力された値を、Ｇ１レジスタ１４およびＧ２レジスタ１６に出力する。Ｇ１レジスタ１４およびＧ２レジスタ１６は、それぞれのラッチイネーブル信号がアサートされると、その値が更新される。次数比較器４２の出力がＵを示すとき、Ｇ１レジスタ１４のラッチイネーブルがアサートされ、第４セレクタ６６の出力がＧ１レジスタ１４に格納される。反対に、次数比較器４２の出力がＶを示すとき、Ｇ２レジスタ１６のラッチイネーブルがアサートされ、第４セレクタ６６の出力がＧ２レジスタ１６に格納される。これにより、ステップ（ix）の処理が可能となる。
【００４４】
図３は、１／Ｚ回路５２の構成例を示すブロック図である。１／Ｚ回路５２は、ＡＮＤゲート５４、第３ＸＯＲゲート５６、１ビットシフタ５８を含む。
ＡＮＤゲート５４は、入力の最下位ビットとＦレジスタ１８の論理積（ＡＮＤ）を生成する。第３ＸＯＲゲート５６は、ＡＮＤゲート５４の出力と入力の排他的論理積（ＸＯＲ）を生成する。１ビットシフタ５８は、第３ＸＯＲゲート５６の出力を１ビット右シフトする。
【００４５】
以上が逆数演算器１００の具体的な構成である。
【００４６】
この逆数演算器１００によれば、拡張ユークリッドアルゴリズムを用い、ｎビットを単位として演算処理を進めることで、少ないサイクル数で逆数Ｘ−１を演算できる。サイクル数を減らすことにより、逆数演算器１００を低周波数で動作させることが可能となるため、消費電力を低減できる。あるいは、従来と同じクロック周波数で動作させた場合、演算処理に要する時間を短縮できる。
【００４７】
続いて、次数比較器４２の好ましい構成、処理を説明する。図４は、次数比較器４２のブロック図である。次数比較器４２は、第１レジスタ７０、第２レジスタ７２、最上位セットビット検出器７４Ｕ，７４Ｖ、次数更新器７６Ｕ，７６Ｖを備える。
【００４８】
第１レジスタ７０は、入力ビット列Ｕの次数を示す値ＤＥＧ＿Ｕを保持する。第２レジスタ７２は、入力ビット列Ｖの次数を示す値ＤＥＧ＿Ｖを保持する。
本実施の形態では、第１レジスタ７０に格納される値ＤＥＧ＿Ｕは、次数そのものの値ｄｅｇ（Ｕ）ではなく、ビット列Ｕの最上位から各ビットをスキャンして１が検出されるまでに現れた０の個数を示すものとする。値ＤＥＧ＿Ｖも同様である。つまり以下の関係式が成り立つ。
ＤＥＧ＿Ｕ＝ｍ−１−ｄｅｇ（Ｕ）
ＤＥＧ＿Ｖ＝ｍ−１−ｄｅｇ（Ｖ）
【００４９】
最上位セットビット検出器７４Ｕ，７４Ｖは、入力ビット列Ｕ，Ｖのそれぞれ次数を検出し、次数を示す値ＤＥＧ＿Ｕ、ＤＥＧ＿Ｖを出力する。
【００５０】
次数更新器７６Ｕは、第１レジスタ７０に、次数を示す値ＤＥＧ＿Ｕを格納する。また次数更新器７６Ｖは、第２レジスタ７２に、次数を示す値ＤＥＧ＿Ｖを格納する。ここで最上位セットビット検出器７４Ｕ，７４Ｖによって次数を検出すると処理時間が長くなるため、次数更新器７６Ｕ，７６Ｖは可能な限り、最上位セットビット検出器７４を利用せずに、第１レジスタ７０、第２レジスタ７２の値ＤＥＧ＿Ｕ，ＤＥＧ＿Ｖを更新する。
【００５１】
次数更新器７６Ｕは、（ａ）入力ビット列Ｕが右シフト演算されたとき、その右シフト量ＳＨＦ＿Ｕに応じて、第１レジスタ７０が保持する値ＤＥＧ＿Ｕを更新する。更新後の値ＤＥＧ＿Ｕは、更新前の値ＤＥＧ＿Ｕ’に右シフト量ＳＨＦ＿Ｕを加算したものである。
【００５２】
また次数更新器７６Ｕは、（ｂ）入力ビット列ＵとＶのＸＯＲ演算が行われ、第１レジスタ７０、第２レジスタ７２それぞれが保持する値ＤＥＧ＿ＵとＤＥＧ＿Ｖが異なる場合、それらの次数を維持する。
【００５３】
次数更新器７６Ｖは、（ｃ）入力ビット列ＵとＶのＸＯＲ演算が行われ、第１レジスタ７０、第２レジスタ７２それぞれが保持する値ＤＥＧ＿ＵとＤＥＧ＿Ｖが等しい場合には、入力ビット列ＵとＶのうち更新すべき一方（ここではＶ）の次数を最上位セットビット検出器７４Ｖにより検出し、その出力に応じて、第１レジスタ７０と第２レジスタ７２のうち対応する一方（第２レジスタ７２）が保持する値ＤＥＧ＿Ｖを更新する。
【００５４】
次数更新器７６Ｕは、加算器８０、セレクタＳＥＬ＿Ｕを含む。加算器８０は、処理（ａ）に用いられ、ＤＥＧ＿ＵとＳＨＦ＿Ｕを加算する。このときセレクタ８２は、加算器８０の出力を選択し、第１レジスタ７０に出力する。処理（ｃ）の場合、セレクタ８２は最上位セットビット検出器７４Ｕの出力を選択し、第１レジスタ７０に出力する。
【００５５】
次数更新器７６Ｖの動作、構成は、次数更新器７６Ｕと同様である。
【００５６】
比較器７８は、第１レジスタ７０の値ＤＥＧ＿Ｕと第２レジスタ７２の値ＤＥＧ＿Ｖを比較する。比較器７８は、入力ビット列Ｕの次数ｄｅｇ（Ｕ）の方が高いとき１、そうでないとき、つまり入力ビット列Ｖの次数ｄｅｇ（Ｖ）の方が高いとき０を出力する。
【００５７】
続いて最上位セットビット検出器７４の特徴を説明する。図５は、最上位セットビット検出器７４のブロック図である。最上位セットビット検出器７４Ｕ，７４Ｖは同様に構成されるためここでは最上位セットビット検出器７４Ｕについて説明する。
【００５８】
最上位セットビット検出器７４Ｕは、ビット列分割器９０、サブ検出器９２、積算器９４を含む。ビット列分割器９０は、次数の検出対象である入力ビット列Ｕを一定のビット幅Ｗのサブビット列ＵＳＵＢに分割し、上位側から順次、出力する。サブビット列のビット幅は特に限定されないが、たとえば８ビット〜３２ビット程度とするのがよい。ビット列分割器９０は、入力ビット列Ｕのうち、所定ビット幅Ｗを選択するマルチプレクサ（ＭＵＸ）と把握することができる。
【００５９】
サブ検出器９２は、ビット列分割器９０から順次出力されるＷビットのサブビット列を受け、そのサブビット列内の最上位から連続する０の個数ＮＵＭ＿ＺＥＲＯを出力する。サブ検出器９２は、最上位セットビットを検索するＦＦＳＢ（Find First Set Bit）回路とも称される。図６は、サブ検出器９２の入出力を示す真理値表である。"X"は冗長（Don't Care）を示す。
【００６０】
積算器９４は、サブ検出器９２の検出結果を累積（積算）する。積算器９４は、サブ検出器９２により１が検出されると、つまり出力（ＮＵＭ＿ＺＥＲＯ）が"1000"以外の場合には、累積演算を停止する。そして積算器９４の値ＴＵが、次数ｄｅｇ（Ｕ）を示す値ＤＥＧ＿Ｕとして出力される。
【００６１】
積算器９４は、加算器９６、累積レジスタ９８を含む。加算器９６は、累積レジスタ９８の値ＴＵと、サブ検出器９２からの入力ＮＵＭ＿ＺＥＲＯを加算し、累積レジスタ９８の値ＴＵを更新する。
【００６２】
図７（ａ）は、積算器９４の動作を示す図である。ビット列分割器９０によって、入力ビット列Ｕが、Ｗ＝８ビットのサブビット列ＵＳＵＢ１，ＵＳＵＢ２，ＵＳＵＢ３…に分割される。累積レジスタ９８の初期値はＴＵ＝０である。サブ検出器９２は、サブビット列ＵＳＵＢ１を受け、連続ゼロの個数ＮＵＭ＿ＺＥＲＯ（＝"1000"=８）を出力する。その結果、累積レジスタ９８の値ＴＵは８に更新される。続いてサブ検出器９２は、サブビット列ＵＳＵＢ２を受け、連続ゼロの個数ＮＵＭ＿ＺＥＲＯ（＝"1000"=８）を出力する。その結果、累積レジスタ９８の値ＴＵは１６に更新される。続いてサブ検出器９２は、サブビット列ＵＳＵＢ２を受け、連続ゼロの個数ＮＵＭ＿ＺＥＲＯ（＝"1000"=８）を出力する。その結果、累積レジスタ９８の値ＴＵは１６に更新される。このサイクルにおいてＮＵＭ＿ＺＥＲＯが"1000"ではないため、累積演算は停止し、そのときの累積レジスタ９８の値ＴＵが出力される。
【００６３】
ビット列分割器９０は、動作開始において、そのときの第１レジスタ７０に格納される値ＤＥＧ＿Ｕに応じて、最初に出力するサブビット列を決定する。つまりレジスタ７０に格納される値ＤＥＧ＿Ｕが示す次数よりも上位のビットはすべてゼロである。そこですべてが０であることが分かっているサブビット列については、繰り返し演算の対象から除外する。図７（ｂ）は、ビット列分割器９０の動作を示す図である。Ｕ’はＸＯＲ演算が行われる前の、ＵはＸＯＲ演算後の入力ビット列を示す。ＸＯＲ演算前においてＤＥＧ＿Ｕ＝１２である。この場合、入力ビット列Ｕの１番目のサブビット列ＵＳＵＢ１には、１が存在しないことが保証される。そこでビット列分割器９０は２番目のサブビット列ＵＳＵＢ２から順に出力する。これにより一層、サイクル数を削減できる。
【００６４】
以上、本発明について、実施の形態をもとに説明した。この実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。以下、こうした変形例について説明する。
【００６５】
（第１変形例）
図２のシフター回路３０では、単一のマルチビットシフタ３４を、Ｕレジスタ１０とＶレジスタ１２の右シフト処理について共用したが、２系統のマルチビットシフタ３４を設けてもよい。
【００６６】
（第２変形例）
図２の１／Ｚ演算部５０では、Ｇ１レジスタ１４とＧ２レジスタ１６に対する１／Ｚ処理を、１系統の１／Ｚ回路群で共用したが、２系統の１／Ｚ回路群を設けてもよい。
【００６７】
実施の形態にもとづき、特定の語句を用いて本発明を説明したが、実施の形態は、本発明の原理、応用を示しているにすぎず、実施の形態には、請求の範囲に規定された本発明の思想を逸脱しない範囲において、多くの変形例や配置の変更が可能である。
【符号の説明】
【００６８】
１００…逆数演算器、１０…Ｕレジスタ、１２…Ｖレジスタ、１４…Ｇ１レジスタ、１６…Ｇ２レジスタ、１８…Ｆレジスタ、２０…演算処理部、２２…コントローラ、３０…シフター回路、３２…第１セレクタ、３４…マルチビットシフタ、４０…第１ＸＯＲゲート、４２…次数比較器、５０…１／Ｚ演算部、５２…１／Ｚ回路、５４…ＡＮＤゲート、５６…第３ＸＯＲゲート、５８…１ビットシフタ、６０…第２ＸＯＲゲート、６２…第２セレクタ、６４…第３セレクタ、６６…第４セレクタ、７０…第１レジスタ、７２…第２レジスタ、７４…最上位セットビット検出器、７６…次数更新器、７８…比較器、８０…加算器、８２…セレクタ、９０…ビット列分割器、９２…サブ検出器、９４…積算器、９６…加算器、９８…累積レジスタ。
【図１】
2016206438.tif 000003
【図２】
2016206438.tif 000004
【図３】
2016206438.tif 000005
【図４】
2016206438.tif 000006
【図５】
2016206438.tif 000007
【図６】
2016206438.tif 000008
【図７】
2016206438.tif 000009