(57)【要約】本発明は、剰余演算を用いて計算を実行する方法および装置に属する。本発明の方法および装置は、論理ゲートを使用して定数による掛算などの計算を実行し、所与の基数ａｉおよび法ｐに関する剰余の整数論的対数を算出し、２つの剰余のｐを法とした積を算出することができる。論理ゲートを使用すると、集積ＲＮＳデジタル信号プロセッサの実施において、テーブル参照機能にＲＯＭを使用する場合と比べて利点をもたらすことができる。
2004514960.tif 000002
【特許請求の範囲】
【請求項１】
剰余演算を用いて数学的計算を実行する方法であって、
二進符号のデータを剰余に変換する段階、
剰余をＣＲＮＳからＱＲＮＳに変換する段階、
剰余のモジュラー積を算出する段階、
剰余をＱＲＮＳからＣＲＮＳに変換する段階、および
剰余を二進符号のデータに変換する段階
のうちの１つまたは複数を含み、
該段階のうちの少なくとも１つが、対応する少なくとも１つの、複数の論理ゲートを用いて実現される方法。
【請求項２】
二進符号の入力データを受け取る段階、および
該二進コードの入力データを剰余に変換する段階を含む、請求項１記載の方法。
【請求項３】
剰余をＣＲＮＳからＱＲＮＳに変換する段階を含む、請求項２記載の方法。
【請求項４】
ＱＲＮＳ剰余のモジュラー積（ｍｏｄｕｌａｒ ｐｒｏｄｕｃｔ）を算出する段階を含む、請求項３記載の方法。
【請求項５】
剰余の積のモジュラー和（ｍｏｄｕｌａｒ ｓｕｍ）を算出する段階を含む、請求項４記載の方法。
【請求項６】
モジュラー和をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項５記載の方法。
【請求項７】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項６記載の方法。
【請求項８】
ＱＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項５記載の方法。
【請求項９】
モジュラー積をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項４記載の方法。
【請求項１０】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項９記載の方法。
【請求項１１】
モジュラー積を二進符号のデータに変換する段階を含む、請求項４記載の方法。
【請求項１２】
ＱＲＮＳ剰余のモジュラー和を算出する段階を含む、請求項３記載の方法。
【請求項１３】
モジュラー和をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項１２記載の方法。
【請求項１４】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項１３記載の方法。
【請求項１５】
モジュラー和を二進符号のデータに変換する段階を含む、請求項１２記載の方法。
【請求項１６】
ＱＲＮＳ剰余をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項３記載の方法。
【請求項１７】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項１６記載の方法。
【請求項１８】
ＱＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項３記載の方法。
【請求項１９】
剰余のモジュラー積を算出する段階を含む、請求項２記載の方法。
【請求項２０】
剰余のモジュラー積のモジュラー和を算出する段階を含む、請求項１９記載の方法。
【請求項２１】
モジュラー和をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項２０記載の方法。
【請求項２２】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項２１記載の方法。
【請求項２３】
モジュラー和を二進符号のデータに変換する段階を含む、請求項２０記載の方法。
【請求項２４】
モジュラー積をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項１９記載の方法。
【請求項２５】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項２４記載の方法。
【請求項２６】
モジュラー積を二進符号のデータに変換する段階を含む、請求項１９記載の方法。
【請求項２７】
剰余のモジュラー和を算出する段階を含む、請求項２記載の方法。
【請求項２８】
モジュラー和をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項２７記載の方法。
【請求項２９】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項２８記載の方法。
【請求項３０】
モジュラー和を二進符号のデータに変換する段階を含む、請求項２７記載の方法。
【請求項３１】
剰余をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項２記載の方法。
【請求項３２】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項３１記載の方法。
【請求項３３】
剰余を二進符号のデータに変換する段階を含む、請求項２記載の方法。
【請求項３４】
剰余フォーマットの入力データを受け取る段階、および
剰余をＣＲＮＳからＱＲＮＳに変換する段階を含む、請求項１記載の方法。
【請求項３５】
ＱＲＮＳ剰余のモジュラー積を算出する段階を含む、請求項３４記載の方法。
【請求項３６】
剰余の積のモジュラー和を算出する段階を含む、請求項３５記載の方法。
【請求項３７】
モジュラー和をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項３６記載の方法。
【請求項３８】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項３７記載の方法。
【請求項３９】
ＱＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項３６記載の方法。
【請求項４０】
モジュラー積をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項３５記載の方法。
【請求項４１】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項４０記載の方法。
【請求項４２】
モジュラー積を二進符号のデータに変換する段階を含む、請求項３５記載の方法。
【請求項４３】
ＱＲＮＳ剰余のモジュラー和を算出する段階を含む、請求項３４記載の方法。
【請求項４４】
モジュラー和をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項４３記載の方法。
【請求項４５】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項４４記載の方法。
【請求項４６】
モジュラー和を二進符号のデータに変換する段階を含む、請求項４３記載の方法。
【請求項４７】
ＱＲＮＳ剰余をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項３４記載の方法。
【請求項４８】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項４７記載の方法。
【請求項４９】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項３４記載の方法。
【請求項５０】
剰余フォーマットの入力データを受け取る段階、および
剰余のモジュラー積を算出する段階を含む、請求項１記載の方法。
【請求項５１】
剰余の積のモジュラー和を算出する段階を含む、請求項５０記載の方法。
【請求項５２】
モジュラー和をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項５１記載の方法。
【請求項５３】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項５２記載の方法。
【請求項５４】
モジュラー和を二進符号のデータに変換する段階を含む、請求項５１記載の方法。
【請求項５５】
モジュラー積をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項５０記載の方法。
【請求項５６】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項５５記載の方法。
【請求項５７】
モジュラー積を二進符号のデータに変換する段階を含む、請求項５０記載の方法。
【請求項５８】
剰余フォーマットの入力データを受け取る段階、および
剰余のモジュラー和を算出する段階を含む、請求項１記載の方法。
【請求項５９】
剰余をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項５８記載の方法。
【請求項６０】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項５９記載の方法。
【請求項６１】
剰余を二進符号のデータに変換する段階を含む、請求項５８記載の方法。
【請求項６２】
剰余フォーマットの入力データを受け取る段階、および
剰余をＱＲＮＳからＣＲＮＳに変換する段階を含む、請求項１記載の方法。
【請求項６３】
ＣＲＮＳ剰余を二進符号のデータに変換する段階を含む、請求項６２記載の方法。
【請求項６４】
剰余フォーマットの入力データを受け取る段階、および
剰余を二進符号のデータに変換する段階を含む、請求項１記載の方法。
【請求項６５】
複数の論理ゲートが、カスタム・デジタル論理、標準セル論理、セルベースの論理アレイ、ゲート・アレイ、フィールドプログラム可能なゲート・アレイ、およびプログラム可能な論理デバイスから成る群より選択される、請求項１記載の方法。
【請求項６６】
二進符号が、１の補数、符号の大きさ（ｓｉｇｎ−ｍａｇｎｉｔｕｄｅ）、符号なし二進数、２の補数、固定基数、および浮動基数から成る群より選択される、請求項２記載の方法。
【請求項６７】
定数とモジュラー・データ・オペランドとの積の計算を実現する方法であって、
可能な各モジュラー・データ・オペランドに関する定数関数による掛算の値を算出する段階、
定数関数によりされた掛算の値を表す論理式を導き出す段階、および
複数の論理ゲートに論理式を写像する段階
を含み、ここで複数の論理ゲートがモジュラー・データ・オペランドを受け取り、かつ定数と該モジュラー・データ・オペランドとの積を出力する方法。
【請求項６８】
複数の論理ゲートに論理式を写像する段階の前に、論理式を最小にする段階をさらに含む、請求項６７記載の方法。
【請求項６９】
所与の基数ａｉおよび法（ｍｏｄｕｌｕｓ）ｐｉに関する剰余の整数論的対数の計算を実現する方法であって、
可能な各剰余入力に関する整数論的対数関数の値を算出する段階、
整数論的対数関数の算出された値を表す論理式を導き出す段階、および
複数の論理ゲートに論理式を写像する段階
を含み、ここで複数の論理ゲートが剰余入力を受け取り、所与の基数ａｉおよび法ｐｉに関する剰余入力の整数論的対数を出力する方法。
【請求項７０】
複数の論理ゲートに論理式を写像する段階の前に、論理式を最小にする段階をさらに含む、請求項６９記載の方法。
【請求項７１】
入力オペランドがゼロである場合に、ゼロ記号を出力する段階をさらに含む、請求項６９記載の方法。
【請求項７２】
ゼロ記号がすべての１を有する二進語である、請求項７１記載の方法。
【請求項７３】
複数の可能な生成元のそれぞれに関する整数論的対数関数を実現する段階、および
最適な生成元を選択する段階
をさらに含み、ここで最適な生成元の選択が、速度、面積、および電力から成る群より選択される、少なくとも１つの基準に基づく、請求項６９記載の方法。
【請求項７４】
所与の基数ａｉおよび法ｐｉに関する剰余の整数論的指数の計算を実現する方法であって、
可能な各剰余入力に関する整数論的指数関数の値を算出する段階、
整数論的指数関数の算出された値を表す論理式を導き出す段階、および
複数の論理ゲートに論理式を写像する段階
を含み、ここで複数の論理ゲートが剰余入力を受け取り、かつ所与の基数ａｉおよび法ｐｉに関する剰余入力の整数論的指数を出力する方法。
【請求項７５】
複数の論理ゲートに論理式を写像する段階の前に、論理式を最小にする段階をさらに含む、請求項７４記載の方法。
【請求項７６】
入力オペランドがゼロ記号である場合に、ゼロを出力する段階をさらに含む、請求項７４記載の方法。
【請求項７７】
複数の可能な生成元のそれぞれに関する整数論的指数関数を実現する段階、および
最適な生成元を選択する段階をさらに含み、ここで最適な生成元の選択が、速度、面積、および電力から成る群より選択される、少なくとも１つの基準に基づく、請求項６９記載の方法。
【請求項７８】
ｐｉを法とした２つの剰余の積を算出する方法であって、
第１の剰余がゼロである場合に第１の整数論がゼロ記号である、第１の入力オペランドに対応する第１の剰余の第１の整数論的対数を受け取る段階、
第２の剰余がゼロである場合に第２の整数論がゼロ記号である、第２の入力オペランドに対応する第２の剰余の第２の整数論的対数を受け取る段階、
ｐｉ−１を法とした第１の整数論的対数および第２の整数論的対数を加算し、第１の入力オペランドと第２の入力オペランドのｐｉ−１を法とした和を生成する段階、ならびに
第１の入力オペランドと第２の入力オペランドのｐｉ−１を法とした和の指数を生成する段階であって、指数を生成する段階が、ｐｉ−１を法とした和を複数の論理ゲートに入力することによって達成され、複数の論理ゲートが、
可能な各入力に関する整数論的指数関数の値を算出する段階、
整数論的指数関数の算出された値を表す論理式を導き出す段階、および
複数の論理ゲートに論理式を写像する段階
により選択される段階
を含み、ここで複数の論理ゲートの出力が、第１の剰余と第２の剰余のｐｉを法とした積である方法。
【請求項７９】
第１および第２の整数論的対数を加算する段階が、モジュラー加算器回路を用いて達成される、請求項７８記載の方法。
【請求項８０】
第１の整数論的対数および第２の整数論的対数の一方または両方がゼロ記号であるときに、複数の論理ゲートの出力をゼロに設定する段階をさらに含む、請求項７８記載の方法。
【請求項８１】
Ｎビット二進オペランドを剰余にｐｉを法として換算する方法であって、
ｑｉ＋１のビット群に分割されたＮビット・オペランドを受け取る段階、
Ｎｉ−１最下位ビットをゼロ拡張させる（ｚｅｒｏ ｅｘｔｅｎｄ）段階、ならびに
【数１】
2004514960.tif 000039
に関するビットＱｉｊの残りのｑｉの分割をそれぞれ、複数の論理ゲートのうちの各ｑｉが、剰余を生成する複数の論理ゲートのうちの対応するｑｉに入力する段階であって、ゼロ拡張されたＮｉ−１最下位ビットおよびｑｉの分割のｑｉの剰余をｐｉを法として加算し、Ｎビット・オペランドのｐｉを法とした剰余を生成する段階
を含む方法。
【請求項８２】
ｑｉの複数の論理ゲートが、
残りのｑｉの分割のそれぞれに関する、可能な各入力に関するモジュラー換算関数の値を算出する段階、
モジュラー換算関数の算出された値を表す論理式を導き出す段階、および
論理式をｑｉの複数の倫理ゲートに写像する段階
によって選択される、請求項８１記載の方法。
【請求項８３】
複数の論理ゲートに論理式を写像する段階の前に、論理式を最小にする段階をさらに含む、請求項８２記載の方法。
【請求項８４】
ｐｉを法としたＬのオペランドの和の計算を実行する方法であって、
Ｌのオペランドを加算してＮｉ＋［ｌｏｇ２Ｌ］ビット符号なし和を生成する段階、
［ｌｏｇ２Ｌ］＋１最上位ビットの剰余を生成する複数の論理ゲートに、［ｌｏｇ２Ｌ］＋１最上位ビットを入力する段階、
Ｎｉ−１最下位ビットをゼロ拡張させる段階、ならびに
ゼロ拡張されたＮｉ−１最下位ビットおよび［ｌｏｇ２Ｌ］＋１最上位ビットをｐｉを法として加算して、ｐｉを法としたＬオペランドの和を生成する段階
を含み、ここで複数の論理ゲートが、
可能な各入力に関するモジュラー変換関数の値を算出する段階、
モジュラー変換関数の算出された値を表す論理式を導き出す段階、および
複数の論理ゲートに論理式を写像する段階
によって選択され、ここで複数の論理ゲートの出力が［ｌｏｇ２Ｌ］＋１最上位ビットの剰余である方法。
【請求項８５】
複数の論理ゲートに論理式を写像する段階の前に、論理式を最小にする段階をさらに含む、請求項８４記載の方法。
【請求項８６】
中国式剰余定理（ＣＲＴ）を用いて、ＬオペランドＲＮＳ値を二進表現に変換する方法であって、
Ｌの剰余を対応するＬの複数の論理ゲートに入力し、Ｌの結果を生成する段階、および
Ｌの結果をＭを法として加算し、ＬオペランドＲＮＳ値の二進表現を生成する段階
を含み、複数の論理ゲートが、
可能な各入力に関するＣＲＴ関数の値を算出する段階、
ＣＲＴ関数の算出された値を表す論理式を導き出す段階、および
複数の論理ゲートに論理式を写像する段階
によって選択される方法。
【請求項８７】
複数の論理ゲートに論理式を写像する段階の前に論理式を最小にする段階をさらに含む、請求項８６記載の方法。
【請求項８８】
Ｌオペランド値を二進表現に変換する方法であって、
ＬオペランドＲＮＳ値に関連するＬの剰余をＬの複数の論理ゲートに入力し、Ｌのスケールされた（ｓｃａｌｅｄ）結果を得る段階、および
Ｌのスケールされた結果を２ｋを法として加算し、ＬオペランドＲＮＳ値の二進表現を生成する段階
を含み、複数の論理ゲートが、
可能な各入力に関するＬＣＲＴ関数の値を算出する段階、
ＬＣＲＴ関数の算出された値を表す論理式を導き出す段階、および
複数の論理ゲートに論理式を写像する段階
によって選択される方法。
【請求項８９】
複数の論理ゲートに論理式を写像する段階の前に、論理式を最小にする段階をさらに含む、請求項８８記載の方法。
【請求項９０】
複素剰余数システム（ＣＲＮＳ）値を平方剰余数システム（ＱＲＮＳ）値に変換する方法であって、
ＣＲＮＳ値の虚数成分ｂｉを複数の論理ゲートに入力し、積
【外１】2004514960.tif 000040
を生成する段階、
実数オペランドａｉと積
【外２】2004514960.tif 000041
をｐｉを法として加算し、第１のＱＲＮＳ成分ｚｉ＊を生成する段階、および
実数オペランドａｉから積
【外３】2004514960.tif 000042
をｐｉを法として減算し、第２のＱＲＮＳ成分ｚｉ＊を生成する段階
を含み、ここで複数の論理ゲートが、
可能な各入力に関する
【外４】2004514960.tif 000043
関数により掛算の値を算出する段階、
【外５】2004514960.tif 000044
関数により算出された掛算の値を表す論理式を導き出す段階、および
複数の論理ゲートに論理式を写像する段階
によって選択され、ここで複数の論理ゲートの出力が、ＣＲＮＳ値の虚数成分と
【外６】2004514960.tif 000045
の積である方法。
【請求項９１】
複数の論理ゲートに論理式を写像する段階の前に、論理式を最小にする段階をさらに含む、請求項９０記載の方法。
【請求項９２】
剰余をＣＲＮＳからＱＲＮＳに変換する段階が、
ＣＲＮＳ値の虚数成分ｂｉを複数の論理ゲートに入力し、積
【外７】2004514960.tif 000046
を生成する段階、
実数オペランドａｉと積
【外８】2004514960.tif 000047
をｐｉを法として加算し、第１のＱＲＮＳ成分ｚｉ＊を生成する段階、および
実数オペランドａｉから積
【外９】2004514960.tif 000048
をｐｉを法として減算し、第２のＱＲＮＳ成分ｚｉ＊を生成する段階
を含み、ここで複数の論理ゲートが、
可能な各入力に関する
【外１０】2004514960.tif 000049
関数により掛算の値を算出する段階、
【外１１】2004514960.tif 000050
関数により算出された掛算の値を表す論理式を導き出す段階、および
複数の論理ゲートに論理式を写像する段階
によって選択され、ここで複数の論理ゲートの出力が、ＣＲＮＳ値の虚数成分と
【外１２】2004514960.tif 000051
の積である、請求項２記載の方法。
【請求項９３】
複数の論理ゲートに論理式を写像する段階の前に、論理式を最小にする段階をさらに含む、請求項９２記載の方法。
【請求項９４】
平方剰余数システム（ＱＲＮＳ）値を複素剰余数システム（ＣＲＮＳ）値に変換する方法であって、
第１のＱＲＮＳ成分ｚｉをｐｉを法として第２のＱＲＮＳ成分ｚｉ＊に加算して、和を生成する段階、
第１のＱＲＮＳ成分ｚｉから第２のＱＲＮＳ成分ｚｉ＊をｐｉを法として減算して、差を生成する段階、
第１の複数の論理ゲートに和を入力し、ＣＲＮＳ表現の実数成分ａｉを生成する段階、および
第２の複数の論理ゲートに差を入力し、ＣＲＮＳ表現の虚数成分ｂｉを生成する段階を含み、ここで第１の複数の論理ゲートが、
可能な各入力に関する２−１関数により掛算の値を算出する段階、
２−１関数により算出された掛算の値を表す論理式を導き出す段階、および
複数の論理ゲートに論理式を写像する段階
によって選択され、ここで第１の複数の論理ゲートの出力が和と２−１の積であり、第２の複数の論理ゲートが、
可能な各入力に関する２−１関数による掛算の値を算出する段階、
２−１関数によりされた掛算の値を表す論理式を導き出す段階、および
複数の論理ゲートに論理式を写像する段階
によって選択され、ここで第２の複数の論理ゲートの出力が差と
【外１３】2004514960.tif 000052
の積である方法。
【請求項９５】
第１の複数の論理ゲートに論理式を写像する段階の前に、論理式を最小にする段階をさらに含む、請求項９４記載の方法。
【請求項９６】
第２の複数の論理ゲートに論理式を写像する段階の前に、論理式を最小にする段階をさらに含む、請求項９４記載の方法。
【請求項９７】
剰余演算を用いて数学的計算を実行するための装置であって、
二進符号のデータを剰余に変換する手段、
剰余をＣＲＮＳからＱＲＮＳに変換する手段、
剰余のモジュラー積を算出する手段、
剰余のモジュラー和を算出する手段、
剰余をＱＲＮＳからＣＲＮＳに変換する手段、および
剰余を二進符号のデータに変換する手段
のうちの１つまたは複数を含み、ここで該手段のうちの少なくとも１つが、対応する少なくとも１つの、複数の論理ゲートを含む装置。
【発明の詳細な説明】
【０００１】
本発明は、国立標準・技術研究所協同合意（Ｎａｔｉｏｎａｌ Ｉｎｓｔｉｔｕｔｅｓ Ｓｔａｎｄａｒｄ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ｃｏｏｐｅｒａｔｉｖｅ Ａｇｒｅｅｍｅｎｔ）第Ｆ０ＮＡＮＢ７Ｈ３０２１号によって支持される研究プロジェクトの下で、政府の支持によってなされたものである。政府は、本発明に一定の権利を有する。
【０００２】
発明の背景
本発明は、剰余計算を使用した計算を実行する方法および装置に関する。本方法および装置は、剰余数システム（ＲＮＳ）を用いて自動計算機を実現することができる。ＲＮＳの使用は、ガーナー（Ｇａｒｎｅｒ）， Ｈ．Ｌ．著「剰余システム（Ｔｈｅ Ｒｅｓｉｄｕｅ Ｎｕｍｂｅｒ Ｓｙｓｔｅｍ）」電子計算機に関するＩＲＥ紀要、第ＥＬ−８巻、第６号、１９５９年７月、１４０ページ〜１４７ページおよびテイラー（Ｔａｙｌｏｒ）， Ｆ．Ｊ．著「剰余演算：実例付き説明書（Ｒｅｓｉｄｕｅ Ａｒｉｔｈｍｅｔｉｃ： Ａ Ｔｕｔｏｒｉａｌ ｗｉｔｈ Ｅｘａｍｐｌｅｓ）」ＩＥＥＥコンピュータ、第１７巻、第５号、１９８４年５月、５０ページ〜６１ページで提案されている。ＲＮＳは一般に、デジタル信号処理用の自動計算機を実現するのに用いられる。デジタル信号処理（ＤＳＰ）は、積の和の反復計算によって支配される。ＲＮＳは、以下の文献で示されているように、この種の計算を実行するのに特に適している。メロット（Ｍｅｌｌｏｔｔ）， Ｊ．Ｄ．、ルイス（Ｌｅｗｉｓ）， Ｍ．Ｐ．、テイラー（Ｔａｙｌｏｒ）、Ｆ．Ｊ．著「２Ｄ ＤＦＴ ＶＬＳＩプロセッサおよび構造（Ａ ２Ｄ ＤＦＴ ＶＬＳＩ Ｐｒｏｃｅｓｓｏｒ ａｎｄ Ａｒｃｈｉｔｅｃｔｕｒｅ）」、聴覚、言語および信号処理に関するＩＥＥＥ国際会議会報、アトランタ、１９９６年、およびメロット（Ｍｅｌｌｏｔｔ）， Ｊ．Ｄ．、スミス（Ｓｍｉｔｈ）， Ｊ．Ｃ．、テイラー（Ｔａｙｌｏｒ）、Ｆ．Ｊ．著「ガウス装置−ガロア増強された平方剰余数システムの収縮アレイ（Ｔｈｅ Ｇａｕｓｓ Ｍａｃｈｉｎｅ−Ａ Ｇａｌｏｉｓ−Ｅｎｈａｎｃｅｄ Ｑｕａｄｒａｔｉｃ Ｒｅｓｉｄｕｅ Ｎｕｍｂｅｒ Ｓｙｓｔｅｍ Ｓｙｓｔｏｌｉｃ Ａｒｒａｙ）」、コンピュータ演算に関する第１１回ＩＥＥＥシンポジウム会報、ウィンザー、オンタリオ、１９９３年、１５６ページ〜１６２ページ。
【０００３】
従来、単一の半導体デバイスを用いて大規模なデジタル信号プロセッサを実現することは、このようなデバイス上に配置できる論理の量が制限されるために実際的ではないことが多かった。その代わりに、通常、離散論理を用いて大規模なデジタル信号プロセッサが実現された。ＲＮＳは、小さな加算器とテーブル参照機能が必要であり、それに対応して、離散的に実装された小さな加算器および小さなプログラム可能読取り専用メモリ（ＰＲＯＭ）が一般に利用可能であるため、この実現方法に特に適している。この実現方法の例には、メロット（Ｍｅｌｌｏｔｔ）らの前記の文献で論じられたガウス装置が挙げられる。単一の半導体デバイス上に大規模なデジタル信号プロセッサを一体化することが可能になったので、小さな加算器およびメモリを使用する方法が発展した。このようなデジタル信号プロセッサの例は、スミス（Ｓｍｉｔｈ）， Ｊ．Ｃ．、テイラー（Ｔａｙｌｏｒ）， Ｆ．Ｊ．著「直線収縮アレイＤＳＰ適用のための、障害許容性ＧＥＱＲＮＳ処理要素の設計（Ｔｈｅ Ｄｅｓｉｇｎ ｏｆ ａ Ｆａｕｌｔ Ｔｏｌｅｒａｎｔ ＧＥＱＲＮＳ Ｐｒｏｃｅｓｓｉｎｇ Ｅｌｅｍｅｎｔ ｆｏｒ Ｌｉｎｅａｒ Ｓｙｓｔｏｌｉｃ Ａｒｒａｙ ＤＳＰ Ａｐｐｌｉｃａｔｉｏｎｓ）」ＶＬＳＩに関するＩＥＥＥグレートレーク・シンポジウム会報、インディアナ州ノートルダム、１９９４年によって与えられている。ＲＮＳデジタル信号プロセッサの他の例は、１９９２年５月２６日に発行された米国特許第５，１１７，３８３号（Ｆｕｊｉｔａら）、１９９１年４月１６日に発行された米国特許第５，００８，６６８号（Ｔａｋａｙａｍａら）、１９９０年８月１４日に発行された米国特許第４，９４９，２９４号（Ｗａｍｂｅｒｇｕｅ）、１９８１年７月２８日に発行された米国特許第４，２８１，３９１号（Ｈｕａｎｇ）に記載されている。
【０００４】
前記の例には、ＲＯＭを用いてテーブル参照機能を実現することが開示されている。通常ＲＮＳデジタル信号プロセッサの実施で使用される小規模のテーブル参照機能の場合、ＲＯＭは、プログラムが容易であり、既知の速度特性、面積特性、および電力特性を有するので魅力的である。これに対して、テーブル参照機能を実現するように論理ゲートの集合を手動で設計するのは厄介である場合があり、速度特性、面積特性、および電力特性は一般に、回路が設計されるときまで十分に判明しない。従来のように、離散ＲＮＳデジタル信号プロセッサの実施ではなく集積ＲＮＳデジタル信号プロセッサの実施でＲＯＭを使用することに伴う他の特徴として、ＲＯＭのダイ面積は、小規模のテーブル参照を実現する他の可能な手段と比べて好ましい。
【０００５】
ＲＮＳを用いて計算を実行する従来の技術には、メモリ、通常ＲＯＭを用いて参照機能を実現することに関する１つまたは複数の欠点がある。これらの欠点には、どのＡＳＩＣ実現技術でも、ＲＮＳ計算で使用するのに必要な特性を有するメモリとして十分な量のメモリが得られないこと、回路にスイッチング機能がない場合でも顕著な電力を使用するアナログ回路がメモリに含まれることが多いこと、たいていのメモリで使用されるアナログ回路が深サブミクロン半導体製造技術に対してうまくスケーリングできないこと、メモリがアナログ回路（たとえば、差動増幅器）に依存するため、デジタル論理回路よりも試験が困難であることがあり、デジタル論理回路とは異なる試験および試験機構が必要であることがあり、一般に、漏れ電流（ＩＤＤＱ）試験方法に適合しないこと、速度、電力、および面積のうちの１つまたは複数に対してメモリを最適化する融通性がほとんどまたはまったくないこと、メモリをパイプライン化することが困難である場合があり、多くの実現技術には、パイプライン・メモリの現実的なオプションがないこと、メモリのサイズが通常、入出力の数によって固定され、基本的にメモリの内容に依存すること、信頼性のために、通常、メモリに関係のないワイヤが半導体デバイス上のメモリ上を通ることはできず、したがって、ＲＮＳを用いた計算を実行する装置で使用されるような多数の小さなメモリが半導体デバイス上に存在すると、デバイス上で様々なメモリ機能と非メモリ機能の両方を接続する能力が損なわれることが含まれる。
【０００６】
発明の簡単な概要
本発明は、剰余数システム（ＲＮＳ）を用いて計算を実行する方法および装置に関する。特定の態様では、複数の論理ゲートを利用して、ＲＮＳを用いた計算を実現することができる。本発明は、半導体デバイスのスケーリング設計方法の最近の変化を考慮して、集積ＲＮＳデジタル信号プロセッサの実施において、小規模テーブル参照機能にＲＯＭを用いることに勝る利点をもたらすことができる。これらの利点のいくつかは、以下を含む：論理ゲートのサイズおよび電力の規模を、ＲＯＭ回路のアナログ部分、たとえば差動センス増幅器よりもうまく縮小できること；集積ＲＮＳの実施の場合、ゲートによって実現される小規模テーブル参照機能で必要とされるダイ面積が、ＲＯＭによって実現される同じ機能よりも狭いこと；一般に、論理ゲートがゼロ入力電流試験方法に適合する一方で、メモリ装置がゼロ入力電流すなわち漏れ電流試験方法（ＩＤＤＱ試験とも呼ばれる）に適合しないこと；論理ゲートが一般にスキャン試験可能である一方で、メモリ装置は特殊な試験構造を必要とし、スキャン試験方法に直接は適合しないこと；信号ワイヤを論理ゲート上に配線することができる一方で、たいていの設計方法では、オンチップ・メモリ上にワイヤを配線することができず、したがって、構造内に多数の小さなメモリが存在すると、ワイヤの配線が煩雑になり、場合によっては設計費用が増大し、回路動作が低速になり、電力消費量が増え、シリコン・ダイ面積消費量が増え、したがって製造費用が増大する恐れがあること。
【０００７】
本発明は、以下の利点のうちの１つまたは複数をもたらすことができる：カスタム・デジタル論理、標準セル論理、セルベースの論理アレイ、ゲート・アレイ、フィールドプログラム可能なゲート・アレイ、およびプログラム論理装置を含むがこれらに限定されない、様々な技術を用いて容易に実現できるように、テーブル参照動作用のメモリをそれほどまたはまったく利用せずに、剰余演算計算回路を実現する手段を提供する段階、回路にスイッチング機能が存在しなくても顕著な電力を消費しない剰余演算計算回路を実現する手段を提供する段階、直接深サブミクロン半導体製造技術に対してスケーリングできる剰余演算計算回路を実現する手段を提供する段階、標準論理試験方法（たとえば、スキャンＩＤＤＱ）に適合する剰余演算計算回路を実現する手段を提供する段階、速度、電力、および面積のうちの１つまたは複数について剰余演算計算回路の数学的機能を最適化する手段を提供する段階、パイプライン化を可能にし、自動パイプライン化用の電子設計自動化（ＥＤＡ）方法に完全に適合する、剰余演算計算回路の数学的機能を実現する手段を提供する段階、数学的機能によって得られる値の構造を利用して、メモリ・ベースの実施で可能なよりも小形で高速の実施を得る、剰余演算計算回路の数学的機能を実現する手段を提供する段階、半導体デバイス上のワイヤの配線に過度に干渉しない、剰余演算計算回路の数学的機能を実現する手段を提供する段階。
【０００８】
発明の詳細な説明
数学的理論を使用可能にする
以下の節には、本発明の動作に関連する数学的属性を示す。この数学的属性は公知であるが、ここでは表記および記号の一貫した骨組みを示すようにこの理論について説明する。
【０００９】
中国式剰余定理
【数２】
Ｓ＝｛ｐ０， ｐ１， ｐ２， ．．．， ｐＬ−１｝
であり、すべての
【数３】
2004514960.tif 000003
および
【数４】
2004514960.tif 000004
についてｇｃｄ（ｐｉ， ｐｊ）＝１であると仮定すると、ここでｇｃｄは最大公分母を表す。
【数５】
2004514960.tif 000005
および
【数６】
2004514960.tif 000006
と仮定すると、ここでＺは整数の環を示す。中国式剰余定理によって、同型写像が存在する：
2004514960.tif 000007
写像ψは次式によって与えられる：
ψ（Ｘ）→（ｘ０， ｘ１， ．．．， ｘＬ−１）
式中、すべての
【数７】
2004514960.tif 000008
について
【数８】
2004514960.tif 000009
である。逆写像は次式によって与えられる：
ψ−１［（ｘ０， ｘ１， ．．．， ｘＬ−１）］→Ｘ
式中、
【数９】
2004514960.tif 000010
【数１０】
2004514960.tif 000011
であり、かつ＜ｘ＞ｐは、ｐを法としたｘと合同の集合｛０， １， ２，．．．， ｐ−１｝中の値を示す。
【００１０】
整数論的対数
ｐｉが素数である場合、環Ｚ／ｐｉＺには、
【数１１】
2004514960.tif 000012
のような生成元
【数１２】
2004514960.tif 000013
が存在する。
【数１３】
2004514960.tif 000014
の場合、
【数１４】
2004514960.tif 000015
のような固有の
【数１５】
2004514960.tif 000016
が存在する。値
2004514960.tif 000017
は、ｐｉを法とした基数ａｉに対するｘｉの整数論的対数と呼ばれる。
【００１１】
整数論的対数を利用して環Ｚ／ｐｉＺ内の積を算出することができる。
【数１６】
2004514960.tif 000018
である場合、
【数１７】
2004514960.tif 000019
のような固有の
【数１８】
2004514960.tif 000020
が存在する。ｘｉ、ｙｉのいずれかまたは両方がゼロである場合、積ｘｉｙｉはゼロである。
【００１２】
複素演算
Ｚ［ｊ］／（ｊ２＋１）が加算および掛算の通常の演算の下で、ガウス整数の環、すなわち、形式ａ＋ｊｂの数を示すと仮定し、式中
【数１９】
2004514960.tif 000021
およびｊ２＝１である。この場合、（Ｚ［ｊ］／（ｊ２＋１））／ｐｉＺは、ｐｉを法としたガウス整数の環であり、かつ
【数２０】
2004514960.tif 000022
の場合、写像ψ：Ｚ［ｊ］／（ｊ２＋１）→（Ｚ［ｊ］／（ｊ２＋１））／ｐｉＺは、
ψ（（ａ＋ｊｂ））→ａｉ＋ｊｂｉ
によって与えられ、式中、
【数２１】
2004514960.tif 000023
である。集合（Ｚ［ｊ］／（ｊ２＋１））／ｐｉＺは、掛算および加算の通常の複素演算の下で環である。すなわち、
【数２２】
2004514960.tif 000024
である場合、
（ａｉ＋ｊｂｉ）＋（ｃｉ＋ｊｄｉ）＝（（ａｉ＋ｃｉ）＋ｊ（ｂｉ＋ｄｉ））
（ａｉ＋ｊｂｉ）ｘ（ｃｉ＋ｊｄｉ）＝（（ａｉｃｉ−ｂｉｄｉ）＋ｊ（ａｉｂｉ＋ｂｉｃｉ））
【００１３】
ｐｉが素数であり、ｐｉ＝４ｋｉ＋１であり、式中
【数２３】
2004514960.tif 000025
であると仮定する。この場合、写像
Ψ（（ａｉ＋ｊｂｉ）→（ｚｉ，ｚｉ＊）
（式中、
【数２４】
2004514960.tif 000026
である）により、上記で示した通常の複素演算の下でｐｉを法としたガウス整数と、成分ごとの加算および掛算の下でｐｉを法としたガウス整数との間に、同型写像
2004514960.tif 000027
が存在する。逆写像は、
Ψ−１（（ｚｉ，ｚｉ＊）→（ａｉ＋ｊｂｉ）
によって得られ、式中、
【数２５】
2004514960.tif 000028
である。
【００１４】
【数２６】
2004514960.tif 000029
に関するＺ／ｐｉＺにおいて計算をＬの独立の計算に分解することにより、中国式剰余定理（ＣＲＴ）を利用してＭを法とした整数、Ｚ／ＭＺの環内の値の加算、減算、掛算を行うことができる。各
【数２７】
2004514960.tif 000030
が素数である場合、整数論的対数を利用して掛算の複雑さを低減させることができる。さらに、各
【数２８】
2004514960.tif 000031
が素数であり、かつｐｉ＝４ｋｉ＋１（式中、
【数２９】
2004514960.tif 000032
）である場合、複素掛算を実現するのに必要な演算の数を、同型写像Ψを利用して４つの実数掛算および２つの実数加算から、２つの実数掛算に低減させることが可能である。
【００１５】
図１は、剰余演算を使用して、符号なし実二進数または２の補数、１の補数、符号の大きさ、または他の固定基数オペランドまたは浮動基数オペランドの積の和を生成するのに用いることのできる、本発明の特定の態様を示している。図１に示すシステムは、データを１の補数、符号の大きさ、符号なし二進数、２の補数のような従来の表現を、１組のＬの剰余に変換する回路１を有することができる。掛算が必要である場合、回路３によって入力オペランドの剰余に１つまたは複数の係数を掛けることができる。回路３は、加算を行うだけでよい場合には削除してよい。これらの係数は一定の係数および／またはプログラムされた係数であってよい。次に、回路３によって生成されたモジュラー積を回路４によって加算して、積のモジュラー和を生成することができる。次に、回路６によって積のモジュラー和を従来の表現に変換することができる。モジュラー積および和の特定の構成は、アルゴリズムの設計に依存し、必要に応じて最適化することができる。
【００１６】
図１を参照すると、実数オペランドを処理することのできる態様が示されている。たとえば２の補数のような従来のフォーマットのデータ・オペランドを回路１（図７の議論において詳しく説明する）に入力し、オペランドをＲＮＳ形式に変換することができる。アルゴリズムで掛算が必要である場合、次いで、回路３によって積を算出することができ、回路３は、図３の１つまたは複数の素子、および／または図５および図６の１つまたは複数の素子を含んでよい。次いで、回路４により、必要に応じて任意の和を算出することができ、回路４は、２つのオペランド・モジュラー加算器を含み、さらに選択的に、図８の１つまたは複数のモジュラー加算器ツリーを含む。レジスタ、ラッチ、ランダム・アクセス・メモリ（ＲＡＭ）を含むが、これらに限定されない算術素子および中間記憶素子の特定の構成は、状況に応じて異なる構成であってよい。たとえば、算術素子および中間記憶素子は、畳込み、相関、有限インパルス応答フィルタ、高速フーリエ変換、離散余弦変換、ウェーブレット変換、フィルタ・バンク、縦続積分器くし形フィルタ、デジタル受信機、デジタル送信機を含むが、これらに限定されない機能を実現するように構成してよい。次いで、回路６によって計算の結果を２の補数のような従来のフォーマットに変換することができる。回路６は、たとえば図９に示すようなＣＲＴ変換または図１０に示すようなＬ−ＣＲＴ変換を含んでよい。
【００１７】
図２は、剰余演算を使用して符号なし複素二進数オペランドまたは２の補数オペランドの積の和を生成するのに用いることのできる、本発明の他の特定の態様を示している。図２に示すシステムは、データを、各オペランドの各実数成分および虚数成分について、１の補数、符号の大きさ、符号なし二進値、２の補数などであるがこれらに限定されない従来の表現から、１組のＬの剰余に変換する回路１を有してよい。次いで、回路２によって複素剰余を平方剰余表現に変換することができる。これらの係数は、一定の係数および／またはプログラムされた係数であってよい。次いで、回路３によって生成されたモジュラー積を加算して、積のモジュラー積を生成することができる。次いで、回路５によって積の平方モジュラー和を複素剰余に変換することができる。次いで、回路６によって積の複素和を複素符号なし二進値や２の補数のような従来の表現に変換することができる。モジュラー積および和の特定の構成は、アルゴリズムの設計に依存し、必要に応じて最適化することができる。いくつかの例では、実数入力をオペランドとして受け入れて複素結果を得るか、または複素入力を受け入れて実数結果を得るようにアルゴリズムを構成することができる。このような場合、必要に応じて回路２および／または回路５を削除してよい。
【００１８】
図２に示す態様を参照すると分かるように、本発明は複素オペランドを処理することができる。たとえば２の補数のような従来の形式のデータ・オペランドを回路１（図７の議論において詳しく説明する）に入力して、オペランドをＣＲＮＳ形式に変換することができる。ＣＲＮＳオペランドを回路２に渡してオペランドをＱＲＮＳフォーマットに変換することができる。このような回路２の一例を図１１に示す。アルゴリズムで掛算が必要である場合、次いで、回路３によって積を算出することができる。回路３は、図３の１つまたは複数の素子、および／または図５および図６の１つまたは複数の素子を含んでよい。次いで、回路４により、必要に応じて任意の和を算出することができる。回路４は、２つのオペランド・モジュラー加算器を含み、さらに任意選択で、図８に示すような１つまたは複数のモジュラー加算器ツリーを含む。レジスタ、ラッチ、ランダム・アクセス・メモリ（ＲＡＭ）を含むが、これらに限定されない算術素子および中間記憶素子の特定の構成は、状況に応じて異なる構成であってよい。たとえば、算術素子および中間記憶素子は、畳込み、相関、有限インパルス応答フィルタ、高速フーリエ変換、離散余弦変換、ウェーブレット変換、フィルタ・バンク、縦続積分器くし形フィルタ、デジタル受信機、デジタル送信機を含むがこれらに限定されない機能を実現するように構成してよい。次いで、たとえば図１２に示すように、回路５によって計算のＱＲＮＳ結果をＣＲＮＳ表現に変換し直すことができる。次いで、回路６によってＣＲＮＳ結果を２の補数のような従来のフォーマットに変換することができる。回路６は、たとえば図９に示すようなＣＲＴ変換または図１０に示すようなＬ−ＣＲＴ変換を含んでよい。
【００１９】
定数とモジュラー・データ・オペランドとのモジュラー積を計算する態様を図３に示す。この積は、Ｎｉビット・オペランドを受け入れ、このオペランドとｐｉを法とした定数ｃｉの積を求め、Ｎｉビット結果を得る回路７によって、生成することができる。図３は、オペランドと、回路の設計によって固定される定数とのモジュラー積を生成する回路７の態様のブロック図である。回路７は、まず可能な各モジュラー・データ・オペランドに関する定数関数による掛算の値を算出し、次いで定数関数によりされた掛算の値を表す論理式を導き出すことによって選択される、複数の論理ゲートを利用することができる。次いで、この複数の論理ゲートに論理式を写像することができる。望ましいならば、複数の論理ゲートに論理式を写像する前に、たとえば無効な入力の場合、出力の値は任意の値であってよいことを利用する公知の論理最小化技術を使用することによって、論理式を最小にすることができる。論理式を最小化された論理関数に変換した後、複数の論理ゲートを利用しての実施に写像することができる。複数の論理ゲートへの写像は、たとえば、手動で行っても、またはカリフォルニア州マウンテンビューのサノプシス・インク（Ｓｙｎｏｐｓｙｓ， Ｉｎｃ．）から市販されているデザイン・コンピラー（ＤＥＳＩＧＮ ＣＯＭＰＩＬＥＲ）などのソフトウェアを用いて行ってもよい。
【００２０】
図４は、定数掛算器２および５を法とした値ｘ（最上位ビットから最下位ビットへｘ２、ｘ１、およびｘ０）用の積参照テーブルの一例を示している。真理値テーブル３３は、テーブルへのすべての可能な入力とテーブルの出力ｙ（最上位ビットから最下位ビットへｙ２、ｙ１、およびｙ０）を示している。テーブル中の「ｘ」エントリは、出力の値が任意であることを示している。テーブルは、カルノー図３４Ａ、３４Ｂ、および３４Ｃを用いて、最小にされた１組の論理式３５Ａに変換されている。論理式３５Ａを実現するのに用いることのできる複数の論理ゲート３５Ｂの一例を図４に示す。より大きな法、したがってより大きなテーブルの場合、手動手段によるこのテーブルの論理式の最小化は実際的でない場合があり、したがって、コンピュータ・プログラムを用いて論理式を最小にすることができる。すべての可能な入力が与えられた場合の最小にされた論理式の結果を、真理値テーブル３６に示す。
【００２１】
所与の基数ａｉおよび法ｐｉに関する整数論的対数を計算する態様を図５に示す。ＲＮＳにおいて２つのオペランドを掛算する場合、図５に示すように回路８によってオペランドの対数を算出することができる。この対数は、Ｎｉビット・オペランドを受け入れ、このオペランドのＮｉビット対数を生成する回路８によって生成することができる。入力オペランドがゼロである場合、回路８の出力は、有効な整数論的対数ではない記号である。
【００２２】
図５は、入力オペランドがゼロである場合に剰余の整数論的対数、すなわち特殊ゼロ記号を生成する回路８の態様のブロック図である。所与の基数ａｉおよび法ｐｉに関して、集合｛１， ２， ３， ．．．， ｐｉ−１｝内の値の整数論的対数は、集合｛０， １， ２， ．．．， ｐｉ−２｝内に存在する。回路８の好ましい態様において、入力がゼロであるときに結果として得られる特殊記号は、すべて１の二進語である。図３の説明で論じた手順を用いてテーブル参照関数８を回路に変換することができる。
【００２３】
図６は、オペランドの整数論的対数の和を用いて、ｐｉを法とした２つの剰余の積を算出する回路の態様のブロック図である。図６の回路は、２つのオペランド、すなわち、掛算すべき剰余の整数論的対数、または入力ゼロを与えられたときに回路８によって生成されるゼロの記号を受け入れることができる。オペランドはモジュラー加算器回路９に与えることができ、モジュラー加算器回路９はｐｉ−１を法としたオペランドの和を生成する。この出力が有効であるのは、どちらのオペランドもゼロ記号でない場合だけである。オペランドを回路１０に与えてゼロの記号を検出することができる。次いで、回路９によって求められた対数の和を、整数論的指数テーブル参照回路１１に入力することができる。テーブル参照機能１１は、図３の説明で論じた手順を用いて回路に変換することができる。次いで、ゼロ検出回路１０の出力の論理和をたとえばＯＲゲート１２によって生成することができる。入力されたオペランドのいずれかがゼロ記号であったことをＯＲゲート１２の出力が示している場合、マルチプレクサ１３の出力をゼロに設定することができ、その他の場合は、指数回路１１の出力をマルチプレクサの出力に渡すことができる。図１および図２に示すシステムの大部分の実施において、整数論的指数テーブル参照回路１１は、システムにおいて最もよく使用されるテーブル参照機能である。一般に、特定の（Ｚ／ｐｉＺ）＼０の場合、多数の可能な生成元がある。任意の法ｐｉの場合、可能な生成元の組全体にわたって指数回路のサイズは２０％も変化する。したがって、生成元は１つまたは複数の因子に基づいて選択されうる。本発明の好ましい態様では、各法ｐｉについて、サイズ、速度、電力、他の何らかの費用関数のような、１つまたは複数の基準に基づいて最適な生成元ａｉを選択することができる。次いで、この最適な生成元を用いて整数論的指数回路１１および／または整数論的対数回路８を形成することができる。
【００２４】
図６に示す態様において、オペランドの対数はゼロ検出回路１０によって検査される。いずれかの対数入力が、論理ＯＲゲート１２によって求められるゼロの特殊記号である場合、積出力はマルチプレクサ１３によってゼロに設定される。そうでない場合、モジュラー加算器回路９によって対数のｍｏｄ ｐｉ−１加算を行うことができる。回路９の出力は指数回路１１に入力することができる。次いで、指数回路１１の出力をマルチプレクサ１３に渡すことができ、ＯＲゲート１２の出力により、どちらのオペランドも特殊ゼロ記号ではないと判定された場合、マルチプレクサ１３の出力を指数回路１１の出力に設定することができる。
【００２５】
図７は、Ｎビット二進オペランドをｐｉを法としたその剰余に変換する態様のブロック図である。この二進オペランドはたとえば符号なし補数や２の補数であってよい。ゼロ拡張（ｚｅｒｏ ｅｘｔｅｎｓｉｏｎ）１４は、入力されたオペランドの最下位Ｎｉ−１ビットを取り出し、ｐｉを法としたそのＮｉビット剰余を生成することができる。この従来のＮビット・オペランドはｑｉ＋１のビット群に分割することができる。最下位Ｎｉ−１ビットは、すでにｐｉを法として変換されているが、ゼロ拡張１４によってゼロを加えられてＮｉビットになる。入力オペランドの残りの
2004514960.tif 000033
ビットはｑｉのビット群に分割することができ、これらのビット群はｑｉのテーブル参照回路１５Ａ、１５Ｂ、および１５Ｃに入力される。
【数３０】
2004514960.tif 000034
に関するビットＱｉｊの各分割をテーブル参照回路１５Ａ、１５Ｂ、および１５Ｃに入力することができる。次いで、テーブル参照回路１５Ａ、１５Ｂ、および１５Ｃは、この重み付き入力の剰余を生成することができる。テーブル参照回路１５Ａ、１５Ｂ、および１５Ｃによって実行される数学的機能は、図３の説明で論じた手順を用いて回路に変換することができる。ｑｉ＋１オペランド・モジュラー加算器１６によってｑｉ＋１の剰余を加算して、ｐｉを法とした最初の入力オペランドの剰余を生成することができる。たとえば、ｑｉ＋１オペランド・モジュラー加算器回路１６によって、スプリッタ１４およびテーブル参照回路１５Ａ、１５Ｂ、１５Ｃの出力を加算することができ、この和は、最初のＮビット・オペランドをｐｉを法として変換した値である。
【００２６】
図８は、Ｌ＞２のオペランド（Ｌの剰余）のｐｉを法とした和を算出する回路の態様のブロック図である。二進加算器ツリー１７によってＬのオペランドを加算して、Ｌのオペランドの全和を生成することができる。たとえば、二進加算器１７は、入力オペランドのＮｉ＋［ｌｏｇ２Ｌ］ビット符号なし和を生成することができる。全和からＮｉ−１最下位ビットを分割することができ、ゼロ拡張２１によってＮｉビットをゼロ拡張させることができる。図示のように、スプリッタ２０によって二進加算器１７の出力を分割して、最上位［ｌｏｇ２Ｌ］＋１ビットをｐｉを法としたテーブル参照回路１８に渡す一方で、最下位Ｎｉ−１ビットをゼロ拡張２１に渡すことができる。テーブル参照機構１８は、図３の態様に関して論じた手順を用いて回路に変換することができる。ｐｉを法としたテーブル参照回路とゼロ拡張２１の出力は、ｐｉを法とした加算器１９によって組み合わされ、ｐｉを法としたＬオペランドの和が求められる。
【００２７】
本発明の態様を利用して、中国式剰余定理を用いてＬオペランドＲＮＳ値を従来の値に変換することができる。図９は、中国式剰余定理によってある値のＬ剰余表現を、その符号なし二進表現に変換する回路の態様のブロック図である。Ｌの剰余｛ｘ０， ｘ１， ｘ２， ．．．， ｘＬ−１｝をＬの別々のＣＲＴ関数テーブル参照回路２２Ａ、２２Ｂ、２２Ｃ、および２２Ｄに入力し、Ｌの結果を得ることができる。テーブル参照関数２２Ａ、２２Ｂ、２２Ｃ、および２２Ｄは、図３の説明で論じた手順を用いて回路に変換することができる。この結果、モジュラー加算器回路２３はたとえば、入力値の符号なし二進表現を生成する。
【００２８】
本発明の態様を利用して、Ｌ−ＣＲＴを用いてＬオペランドＲＮＳ値を従来の値に変換することができる。図１０は、Ｌ−ＣＲＴ変換を用いて、ある値のＬ剰余表現を、スケールされた符号なし二進表現または２の補数表現に変換する回路の態様のブロック図である。Ｌの剰余｛ｘ０， ｘ１， ｘ２， ．．．， ｘＬ−１｝を、Ｌの別々のＬ−ＣＲＴ関数テーブル参照回路２４Ａ、２４Ｂ、２４Ｃ、および２４Ｄに入力し、Ｌのスケールされた結果を得ることができる。テーブル参照関数２４Ａ、２４Ｂ、２４Ｃ、および２４Ｄは、図３の説明で論じた手順を用いて回路に変換することができる。次いで、テーブル参照回路２４Ａ、２４Ｂ、２４Ｃ、および２４Ｄによって得られた結果を、二進加算器回路２５によって加算し、たとえば入力値のスケールされた符号なし二進表現または２の補数表現を生成することができる。
【００２９】
本発明の態様を利用してＣＲＮＳオペランドをＱＲＮＳ形式に変換することができる。図１１は、複素剰余数システム（ＣＲＮＳ）値を平方剰余数システム（ＱＲＮＳ）値に変換する回路の態様のブロック図である。ＣＲＮＳ入力の虚数成分ｂｉは
【外１４】
2004514960.tif 000035
回路２６による定数掛算に入力することができる。たとえば、虚数剰余オペランドｂｉは、このオペランドと
【外１５】
2004514960.tif 000036
の積を参照する回路２６に入力することができる。テーブル参照関数２６は、図３の態様に関して論じた手順を用いて回路に変換することができる。テーブル参照回路２６の出力とＣＲＮＳ入力の実数部分を、モジュラー加算器回路２７によってｐｉを法として加算し、ＱＲＮＳ成分ｚｉを生成することができる。次いで、テーブル参照回路２６の出力を、モジュラー減算器回路２８によるＣＲＮＳ入力の実数部分からｐｉを法として減算し、ＱＲＮＳ成分ｚｉ＊を生成することができる。
【００３０】
本発明の態様を利用してＱＲＮＳオペランドをＣＲＮＳ形式に変換することができる。図１２は、平方剰余数システム値を複素剰余数システム値に変換する回路の態様のブロック図である。モジュラー加算器回路２９によってＱＲＮＳ成分ｚｉおよびｚｉ＊をｐｉを法として加算することができる。モジュラー減算器回路３０によって、ＱＲＮＳ成分ｚｉ＊を成分ｚからｐｉを法として減算することができる。モジュラー加算器回路２９の出力は、２−１テーブル参照回路３１による定数掛算に入力することができ、２−１テーブル参照回路３１の出力は、このデータのＣＲＮＳ表現の実数成分である。モジュラー加算器回路２９の出力は、この和の２−１との積を参照する回路３１に入力することができる。モジュラー減算器回路３０の出力は、
【外１６】
2004514960.tif 000037
テーブル参照回路３２による定数掛算に入力することができ、このテーブル参照回路３２の出力は、このデータのＣＲＮＳ表現の虚数成分である。モジュラー減算器３０の出力は、この和の
【外１７】
2004514960.tif 000038
との積を参照する回路３２に入力することができる。積テーブル参照機能３１および３２は、図３の態様に関して論じた手順を使用して回路に変換することができる。
【００３１】
論理ゲートを用いて本発明による様々なテーブル参照動作を実現すると、メモリ装置を使用する従来の方法に勝る多数の利点をもたらすことができる。論理ゲートを使用すると、すでにいくつかの技術が、ＲＮＳ技術の使用に適合されている様々な技術で、ＲＮＳ計算回路を効率的に実現することができる。さらに、ＲＮＳ計算回路にメモリではなく論理ゲートを使用すると、以下の利点のうちの１つまたは複数を得ることができる。相補型金属酸化膜半導体（ＣＭＯＳ）スタティック論理で実現される論理ゲートは、回路にスイッチング機能がないため消費電力が非常に少ない。論理ゲートは、直接深サブミクロン半導体製造技術に対してスケーリングすることができる。論理ゲートは標準論理試験方法に適合することができる。論理ゲート群を速度、電力、および面積について最適化することができる。論理ゲート群を手動手段または自動化手段によって容易にパイプライン化することができる。論理ゲートは、メモリと比べて半導体デバイス上のワイヤの配線に対する干渉を低減させることができる。
【００３２】
所与の入出力サイズの任意の所与のテーブル参照機能に関して、一定の面積および速度を有するメモリとは異なり、論理ゲート群は実現すべき特定のテーブル参照機能に関して最小にすることができる。多くの場合、最小にすべき論理機能は、テーブルを調べても分からないある基本的な構造を有する可能性がある。この構造によって、論理ゲート群では、メモリでは得られない面積および速度面の顕著な利点を得ることができる。たとえば、０．２ミクロン標準セル特定用途向け集積回路（ＡＳＩＣ）プロセスで読取り専用メモリ（ＲＯＭ）で生成される２４１を法とした８ビット入力と２４１を法とした２−１との積に関するテーブル参照では、２２５０ゲートの等価面積が必要であり、１００ＭＨｚにおける電力損失が３．６ｍＷであるが、ゲートとして形成された同じテーブルでは、３６ゲートの面積が必要であり、同じ速度における電力損失は０．２３ｍＷである。同じサイズの他のテーブル、すなわち２４１を法とした指数テーブルでは、６７５ゲートの面積のみが必要であり、かつ同じ速度における電力損失は１．３ｍＷである。
【００３３】
これらの結果は、図３の態様に関してすでに説明したプロセスを用いて得られた結果である。前述のＲＯＭの最短クロック周期は３．０ｎｓであり、一方、ゲートとして実現された前述の積参照回路の、入力から出力までの最長遅延は１．０ｎｓであり、ゲートとして実現された指数参照機能の最長遅延は３．０ｎｓである。指数参照機能の場合、１．２ｎｓの遅延を実現することができる。ただし、この機能の面積は９５７ゲートに増大する。この例は、ＲＯＭなどのメモリではなく論理ゲートを用いてＲＮＳテーブル参照機能を実現することによって、速度、面積、および電力の釣合いの最適化を可能にする、本発明の能力を顕著に示している。所与の実施技術の場合、ＲＯＭは、すべての種類のメモリのうちで最高の記憶密度を有する。たとえば、前述のＲＯＭと同じ技術で、かつ同じサイズ特性および速度特性で実現されたスタティックＲＡＭでは、３６６０ゲートの等価面積が必要である。この例は、論理ゲートを用いてテーブル参照機能を実現することによって、特定の設計のニーズに最もうまく適合するように面積と速度の兼合いをとることができることも示している。
【００３４】
本明細書で説明した例および態様が例示のためのものに過ぎず、当業者は、それを考慮して様々な修正または変更を示唆し、かつそのような修正または変更が本出願の趣旨および範囲内ならびに添付の特許請求の範囲内に含まれるべきである。
【図面の簡単な説明】
【図１】剰余演算を用いて実数オペランドを処理して実数結果を得る、デジタル信号処理用の装置のブロック図である。
【図２】剰余演算を用いて複素オペランドを処理して複素結果を得る、デジタル信号処理用の装置のブロック図である。
【図３】定数掛算器用のモジュラー積テーブル参照機能のブロック図である。
【図４】２と５を法とした変数との５を法とした積に関するテーブル、カルノー図を使用したテーブル用の数式の最小化、変換された数式を実現する複数の論理ゲート、および結果として得られたテーブルを示す。
【図５】整数論的対数参照テーブルを示す。
【図６】オペランドの整数論的対数を用いて積を算出する掛算器のブロック図である。
【図７】符号なしＮビットまたは２の補数の剰余を算出する構造を示す。
【図８】マルチオペランド・モジュラー加算器ツリーのブロック図である。
【図９】中国式剰余定理を用いて、値をＲＮＳ表現から二進表現に変換する構造を示す。
【図１０】Ｌ−ＣＲＴアルゴリズムを用いて、値をＲＮＳ表現から二進表現に変換する構造を示す。
【図１１】複素ＲＮＳ値からＱＲＮＳ値に変換する構造を示す。
【図１２】ＱＲＮＳ値を複素ＲＮＳ値に変換する構造を示す。
【図１】
2004514960.tif 000053
【図２】
2004514960.tif 000054
【図３】
2004514960.tif 000055
【図４】
2004514960.tif 000056
【図５】
2004514960.tif 000057
【図６】
2004514960.tif 000058
【図７】
2004514960.tif 000059
【図８】
2004514960.tif 000060
【図９】
2004514960.tif 000061
【図１０】
2004514960.tif 000062
【図１１】
2004514960.tif 000063
【図１２】
2004514960.tif 000064
【国際公開パンフレット】
2004514960.tif 000065
2004514960.tif 000066
2004514960.tif 000067
2004514960.tif 000068
2004514960.tif 000069
2004514960.tif 000070
2004514960.tif 000071
2004514960.tif 000072
2004514960.tif 000073
2004514960.tif 000074
2004514960.tif 000075
2004514960.tif 000076
2004514960.tif 000077
2004514960.tif 000078
2004514960.tif 000079
2004514960.tif 000080
2004514960.tif 000081
2004514960.tif 000082
2004514960.tif 000083
2004514960.tif 000084
2004514960.tif 000085
2004514960.tif 000086
2004514960.tif 000087
2004514960.tif 000088
2004514960.tif 000089
2004514960.tif 000090
2004514960.tif 000091
2004514960.tif 000092
2004514960.tif 000093
2004514960.tif 000094
2004514960.tif 000095
2004514960.tif 000096
2004514960.tif 000097
2004514960.tif 000098
2004514960.tif 000099
2004514960.tif 000100
2004514960.tif 000101
2004514960.tif 000102
2004514960.tif 000103
2004514960.tif 000104
【国際調査報告】
2004514960.tif 000105
2004514960.tif 000106
2004514960.tif 000107
2004514960.tif 000108
2004514960.tif 000109