JPH10307706A5 - - Google Patents

Claims (11)

1. ２進ビットの複数のカラムを加算して複数の部分和及び桁上げビットを発生する装置であって、特定のカラムのビットは、大きさの桁が同じであり、そして異なるカラムのビットは、大きさの桁が相違するような装置において、
   上記特定のカラムの３つのビットを第１入力として受け取って、第１の和のビット及び第１の桁上げビットを出力として発生するための全加算器と、
   上記特定のカラムの２つのビットを第２入力として受け取って、第２の和のビット及び第２の桁上げビットを出力として発生するための半加算器とを備え、該半加算器及び上記全加算器は、複数の相互接続カラム加算器として構成され、各カラム加算器は、少なくとも１つのカラムの入力のビットを加算しそして部分和及び桁上げビットを発生し、各カラム加算器は、複数の段を有し、そして
   各カラム加算器の段を、同じカラム加算器の他の段及び他のカラム加算器の段と相互接続するための複数の導体を備えており、
   上記半加算器は、上記特定のカラムが上記特定のカラムにおけるビット数を３で除算した後に２つの残余ビットを有するときに、上記特定のカラムにおいて使用され、大きさのより低い桁のビットを有する隣接カラムは、上記特定のカラムより多いビットを有することを特徴とする装置。
2. 上記半加算器は、更に、
   第２入力の２つのビットを受け取って、第２の和ビットを発生するＸＯＲゲートと、
   第２入力の２つのビットを受け取って、第２の桁上げビットを発生するＡＮＤゲートとを備えた請求項１に記載の装置。
3. 特定の段は、手前の隣接カラムから到来する桁上げビットと同数の出て行く桁上げビットを次に隣接するカラムへ発生するための半加算器を含む請求項１に記載の装置。
4. ウォレスツリー乗算器を使用して２進ビットの複数のカラムを加算して複数の部分和及び桁上げビットを発生する方法において、
   ａ）特定のカラムのビットに大きさの同じ桁を与え、異なるカラムのビットに大きさの異なる桁を与え、
   ｂ）３つのビットの第１のセットを上記特定のカラムの全加算器へ入力して、第１の和のビットおよび第１の桁上げビットを出力として発生し、
   ｃ）２つのビットの第２のセットを上記特定のカラムの半加算器へ入力して、第２の和のビットおよび第２の桁上げビットを別の出力として発生し、上記半加算器は、上記特定のカラムが上記特定のカラムにおけるビット数を３で除算した後に２つの残余ビットを有するときに、上記特定のカラムにおいて使用され、大きさのより低い桁のビットを有する隣接カラムは、上記特定のカラムより多いビットを有しており、
   ｄ）上記全加算器および半加算器の複数個を複数の相互接続カラム加算器として構成し、
   ｅ）少なくとも１つの特定のカラムの加算ビットを加え、部分和および桁上げビットを発生する、
   という段階を備えたことを特徴とする方法。
5. 上記入力する段階ｃ）は、上記第２のセットをＸＯＲゲートへ入力して上記第２の和のビットを発生し、上記第２のセットをＡＮＤゲートへ入力して上記第２の桁上げビットを発生することを含む請求項４に記載の方法。
6. 各カラム加算器は、部分和および桁上げビットを発生するように段にグループ分けされる請求項４に記載の方法。
7. 上記構成する段階ｄ）は、複数の導体を使用して、各カラム加算器の段を同じカラム加算器の他の段および他のカラム加算器の段と相互接続することを含む請求項６に記載の方法。
8. 複数のカラムを有するウォレスツリー乗算器における段数を減少させる方法において、
   ａ）ある数のビットをカラムに与え、
   ｂ）上記段階ａ）からの３つのビット毎に少なくとも１つの全加算器を第１の入力として使用して、第１の出力和および桁上げビットを発生し、
   ｃ）大きさのより低い桁のビットを有する隣接カラムが特定のカラムより多いビットを有するときに、半加算器を使用して上記段階ｂ）の後に２つの残余ビットを受け取る毎に第２の出力和および桁上げビットを発生し、上記半および全加算器は、複数の相互接続カラム加算器として構成されており、各カラムは、複数の段を有しており、
   ｄ）各カラムに対する第１および第２の入力の加算ビットを加え、部分和および桁上げビットを発生する、
   という段階を備えており、それにより、第１の段において２つの残余ビットを受け取るのに半加算器を使用することで、２つの残余ビットを受け取るのに第２の段における全加算器を使用するのに比較してカラム加算器における段数が減少させられるようにしたことを特徴とする方法。
9. 上記半加算器を使用する段階ｂ）は、上記２つの残余ビットをＸＯＲゲートへ入力して上記第２の出力和ビットを発生し、上記２つの残余ビットをＡＮＤゲートへ入力して上記第２の出力桁上げビットを発生することを含む請求項８に記載の方法。
10. Ｍビット乗数とＮビット被乗数との積を得るための乗算回路において、
    上記乗数および被乗数を受け取り加数マトリクスを発生し上記積を出力する１組の相互接続カラム加算器を備えており、上記加数マトリクスは、Ｍロー及びＮカラムを有するＭ×Ｎ加数マトリクスビットを有しており、各カラム加算器は、上記カラムの１つにおける加数マトリクスビットを加え、各カラムは、上記積における異なるビット位置を表し、上記異なるカラムの加数マトリクスビットは、大きさの桁において異なっており、上記カラム加算器は、上記加数マトリクスビットの桁の大きさを増大させるように構成されており、
    上記少なくとも１つのカラム加算器の特定のカラム加算器は、
    上記加数マトリクスの３つのビットを第１の入力として受け取り第１の和のビットおよび桁上げビットを発生する少なくとも１つの全加算器と、
    ２つの加数マトリクスビットを第２の入力として受け取り、上記特定のカラム加算器の加数マトリクスビットが上記特定のカラムにおける加数マトリクスビット数を３で除算した後に２つの残余ビットを有するときに、第２の和のビットおよび第２の桁上げビットを出力として発生する少なくとも１つの半加算器とを含み、大きさのより低い桁の加数マトリクスビットの隣接カラム加算器は、上記特定のカラムの加数マトリクスビットの数を越えるある数の加数マトリクスビットを有していることを特徴とする乗算回路。
11. 上記半加算器は、更に、
    第２入力の２つのビットを受け取って、第２の和のビットを発生するＸＯＲゲートと、
    第２入力の２つのビットを受け取って、第２の桁上げビットを発生するＡＮＤゲートとを備えた請求項１０に記載の乗算回路。