(57)【特許請求の範囲】
【請求項１】
各々が１ビットデータからなるｎ個の入力信号の値と、各々が異なる第１乃至第ｎの所定値とを比較する比較手段と、
第１乃至第ｎ＋１のワード線、これらのワード線と交差するように設けられたｍ（２ｍ  ≧ｎ＋１）個のビット線、および各ワード線と各ビット線の交差点毎に設けられて１ビットデータが記憶されたメモリセルを有している不揮発性メモリと、
前記比較手段のｎ個の比較結果に基づいて前記ｎ＋１個のワード線の中から１本のワード線を選択し、この選択されたワード線を活性化する選択手段と、
を備えたことを特徴とする加算器。
【請求項２】
前記第ｉ（ｉ＝１，…ｎ）の所定値はｉ−１より大きくｉより小さな値であり、前記比較手段は第１乃至第ｎの比較器を有し、前記第ｉ（ｉ＝１，…ｎ）の比較器は、前記ｎ個の入力信号の値と前記第ｉの所定値とに基づいて前記ｎ個の入力信号のうち論理値が１である入力信号の個数の合計が前記第ｉの所定値を超えているか否かを決定し、第ｉの比較結果信号を出力し、
前記選択手段は前記第１乃至第ｎの比較結果信号に基づいて１本のワード線を選択することを特徴とする請求項１記載の加算器。
【請求項３】
前記第ｉ（ｉ＝１，…ｎ）の比較器は、ソースに第１の電源電圧が印加される第１導電型の第１および第２のトランジスタと、
ドレインが前記第１のトランジスタのドレインに接続され、ゲートが前記第１のトランジスタのゲートとともに前記第２のトランジスタのドレインに接続される、前記第１導電型と異なる第２導電型の第３のトランジスタと、
ドレインが前記第２のトランジスタのドレインに接続され、ゲートが前記第２のトランジスタのゲートとともに前記第１のトランジスタのドレインに接続される第２導電型の第４のトランジスタと、
ソースが前記第１の電源電圧と異なる第２の電源電圧に接続され、ゲートに外部からのイネーブル信号を受ける第２導電型の第５のトランジスタと、
前記第３のトランジスタのソースと前記第５のトランジスタのドレインとの間に並列に接続されて、各々のゲートに前記第１の電源電圧が印加されるｉ個の第２導電型のトランジスタからなる第１のトランジスタ群と、
前記第４のトランジスタのソースと前記第５のトランジスタのドレインとの間に並列に接続された第２導電型のｎ個のトランジスタからなる第２のトランジスタ群と、
を備え、
前記第２のトランジスタ群の第ｊ（ｊ＝１，…ｎ）番目のトランジスタのゲートには前記ｎ個の入力信号のうち第ｊ番目の入力信号が印加され、
前記第２のトランジスタ群を構成する各トランジスタの電流駆動能力は等しく、
ｉ＝１の場合は前記第１のトランジスタ群を構成する１個のトランジスタの電流駆動能力は前記第２のトランジスタ群を構成する各トランジスタの電流駆動能力より小さく、
ｉ≠１の場合は、前記第１のトランジスタ群のうち、１個のトランジスタを除いた残りの各トランジスタの電流駆動能力は、前記第２のトランジスタ群を構成する各トランジスタの電流駆動能力に等しくてかつ前記１個のトランジスタの電流駆動能力よりも大きく、
前記第１のトランジスタのドレインから前記第ｉの比較結果信号が出力され、前記第２のトランジスタのドレインから、前記第ｉの比較結果信号の反転信号が出力されることを特徴とする請求項２記載の加算器。
【請求項４】
前記選択手段は、
前記第１の比較結果信号を反転して前記第１のワード線に送出する第１の反転ゲートと、
前記第１乃至第ｎ−１のＮＯＲゲートと、
前記第ｎの比較結果信号の反転信号を反転して前記第ｎ＋１のワード線に送出する第２の反転ゲートとを有し、
前記第ｉ（ｉ＝１，…ｎ−１）のＮＯＲゲートは、前記第ｉの比較結果信号を反転した信号と前記第ｉ＋１の比較結果信号とに基づいてＮＯＲ演算を行い、この演算結果を前記第ｉ＋１のワード線に送出する
ことを特徴とする請求項２または３に記載の加算器。
【請求項５】
前記不揮発性メモリは、前記第ｉ（ｉ＝１，…ｎ）のワード線が選択されたときに、ｉ−１を２進数で表現したｍビットデータが前記第１乃至第ｍのビット線を介して出力されるように前記第ｉのワード線に接続された前記メモリセルの各々にデータが記憶されていることを特徴とする請求項１乃至４のいずれかに記載の加算器。
【請求項６】
同一桁の部分積の加算に、請求項１乃至５のいずれかに記載の加算器を少なくとも１個用いたことを特徴とする乗算器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は複数個のビットの加算を行う加算器に関するものであって、特に乗算における部分積の同一桁の加算に用いられるものである。
【０００２】
【従来の技術】
従来、ｎビットの被乗数Ｘ（＝Ｘｎ−１  ２ｎ−１  ＋…＋Ｘ１  ２＋Ｘ０  ）とｎビットの乗数Ｙ（＝Ｙｎ−１  ２ｎ−１  ＋…＋Ｙ１  ２＋Ｙ０  ）を乗算する場合にはアレイ式並列乗算方式が用いられていた。このアレイ式並列乗算方式は、まずｎ２  個のＡＮＤゲートを用いて、被乗数Ｘの各ビット値Ｘｉ  （ｉ＝０，…，ｎ−１）と、乗数Ｙの各ビット値Ｙｊ  （ｊ＝０，…，ｎ−１）との部分積Ｐｉｊ（＝Ｘｉ  ・Ｙｊ  ）を求め、これらの部分積Ｐｉｊを各桁で加算している。そして、これらの部分積の加算には、アレイ状に配置された全加算器が用いられ、また部分積内を渡る桁上げ信号がリップルキャリー接続となっている。
【０００３】
【発明が解決しようとする課題】
このようにアレイ式乗算方式においては、部分積の加算にはアレイ状に配置された全加算器が用いられるとともに、部分積内を渡る桁上げ信号がリップルキャリー接続となっている。このため、１つ下の桁の全加算器からの桁上げ信号を待たなければ自分の桁の加算ができない。このことは演算の高速化を進める上で非常に問題であった。
【０００４】
本発明は上記事情を考慮してなされたものであって、複数のビットの加算を高速に行うことのできる加算器を提供することを目的とする。
【０００５】
【課題を解決するための手段】
本発明による加算器は、各々が１ビットデータからなるｎ個の入力信号の値と、各々が異なる第１乃至第ｎの所定値とを比較する比較手段と、第１乃至第ｎ＋１のワード線、これらのワード線と交差するように設けられたｍ（２ｍ  ≧ｎ＋１）個のビット線、および各ワード線と各ビット線の交差点毎に設けられて１ビットデータが記憶されたメモリセルを有している不揮発性メモリと、前記比較手段のｎ個の比較結果に基づいて前記ｎ＋１個のワード線の中から１本のワード線を選択し、この選択されたワード線を活性化する選択手段と、を備えたことを特徴とする。
【０００６】
なお、前記第ｉ（ｉ＝１，…ｎ）の所定値はｉ−１より大きくｉより小さな値であり、前記比較手段は第１乃至第ｎの比較器を有し、前記第ｉ（ｉ＝１，…ｎ）の比較器は、前記ｎ個の入力信号の値と前記第ｉの所定値とに基づいて前記ｎ個の入力信号のうち論理値が１である入力信号の個数の合計が前記第ｉの所定値を超えているか否かを決定し、第ｉの比較結果信号を出力し、前記選択手段は前記第１乃至第ｎの比較結果信号に基づいて１本のワード線を選択するように構成しても良い。
【０００７】
また、前記第ｉ（ｉ＝１，…ｎ）の比較器は、ソースに第１の電源電圧が印加される第１導電型の第１および第２のトランジスタと、ドレインが前記第１のトランジスタのドレインに接続され、ゲートが前記第１のトランジスタのゲートとともに前記第２のトランジスタのドレインに接続される、前記第１導電型と異なる第２導電型の第３のトランジスタと、ドレインが前記第２のトランジスタのドレインに接続され、ゲートが前記第２のトランジスタのゲートとともに前記第１のトランジスタのドレインに接続される第２導電型の第４のトランジスタと、ソースが前記第１の電源電圧と異なる第２の電源電圧に接続され、ゲーに外部からのイネーブル信号を受ける第２導電型の第５のトランジスタと、前記第３のトランジスタのソースと前記第５のトランジスタのドレインとの間に並列に接続されて、各々のゲートに前記第１の電源電圧が印加されるｉ個の第２導電型のトランジスタからなる第１のトランジスタ群と、前記第４のトランジスタのソースと前記第５のトランジスタのドレインとの間に並列に接続された第２導電型のｎ個のトランジスタからなる第２のトランジスタ群と、を備え、前記第２のトランジスタ群の第ｊ（ｊ＝１，…ｎ）番目のトランジスタのゲートには前記ｎ個の入力信号のうち第ｊ番目の入力信号が印加され、前記第２のトランジスタ群を構成する各トランジスタの電流駆動能力は等しく、ｉ＝１の場合は前記第１のトランジスタ群を構成する１個のトランジスタの電流駆動能力は前記第２のトランジスタ群を構成する各トランジスタの電流駆動能力より小さく、ｉ≠１の場合は、前記第１のトランジスタ群のうち、１個のトランジスタを除いた残りの各トランジスタの電流駆動能力は、前記第２のトランジスタ群を構成する各トランジスタの電流駆動能力に等しくてかつ前記１個のトランジスタの電流駆動能力よりも大きく、前記第１のトランジスタのドレインから前記第ｉの比較結果信号が出力され、前記第２のトランジスタのドレインから、前記第ｉの比較結果信号の反転信号が出力されるように構成しても良い。
【０００８】
また、前記選択手段は、前記第１の比較結果信号を反転して前記第１のワード線に送出する第１の反転ゲートと、前記第１乃至第ｎ−１のＮＯＲゲートと、前記第ｎの比較結果信号の反転信号を反転して前記第ｎ＋１のワード線に送出する第２の反転ゲートとを有し、前記第ｉ（ｉ＝１，…ｎ−１）のＮＯＲゲートは、前記第ｉの比較結果信号を反転した信号と前記第ｉ＋１の比較結果信号とに基づいてＮＯＲ演算を行い、この演算結果を前記第ｉ＋１のワード線に送出するように構成しても良い。
【０００９】
また、前記不揮発性メモリは、前記第ｉ（ｉ＝１，…ｎ）のワード線が選択されたときに、ｉ−１を２進数で表現したｍビットデータが前記第１乃至第ｍのビット線を介して出力されるように前記第ｉのワード線に接続された前記メモリセルの各々にデータが記憶されていることが好ましい。
【００１０】
また、乗算の同一桁の部分積の加算に、上述の加算器を少なくとも１個用いることが好ましい。
【００１１】
【発明の実施の形態】
本発明の実施の形態を図面を参照して説明する。
本発明による加算器の一実施の形態の構成を図１に示す。この実施の形態の加算器は比較手段２と、選択回路４と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）６とを備えている。
【００１２】
比較手段２はｎ個の比較器２１  ，…２ｎ  を有している。各比較器２ｉ  （ｉ＝１，…ｎ）は、各々が１ビットデータからなるｎ個の入力ＰＰ１  ，…ＰＰｎ  に基づいて、これらのｎ個の入力ＰＰ１  ，…Ｐｎ  のうち論理値が「１」である入力の総数が所定の数αｉ  （例えばαｉ  ＝ｉ−０．５）よりも大きいか否かを比較し、比較結果を示す信号ＣＰｉ  とその反転信号ＣＰｉ  バーを出力する。ここで論理値が「１」である入力の総数が上記所定の数αｉ  よりも大きい場合はＣＰｉ  ＝１、ＣＰｉ  バー＝０とし、上記総数が上記所定の数αｉ  より小さい場合はＣＰｉ  ＝０、ＣＰｉ  バー＝１とする。例えば、ｎ個の入力ＰＰ１  ，…ＰＰｎ  のうち論理値が「１」である入力の総数が３個である場合には、ＣＰ１  ＝ＣＰ２  ＝ＣＰ３  ＝１、ＣＰ１  バー＝ＣＰ２  バー＝ＣＰ３  バー＝０，ＣＰ４  ＝…＝ＣＰｎ  ＝０，ＣＰ４  バー＝…＝ＣＰｎ  バー＝１となる。
【００１３】
したがって比較手段２はｎ個の入力ＰＰ１  ，…ＰＰｎ  のうち論理値が「１」である入力の総数と、ｎ個の異なる所定値α１  ，…αｎ  とを比較するように構成されていることになる。ここでαｉ  は例えばαｉ  ＝０．５×（２・ｉ−１）である。
【００１４】
ＲＯＭ６はｎ＋１個のワード線ＷＬ０  ，…ＷＬｎ  と、ｍ個のビット線ＢＬ１  ，…ＢＬｍ  と、各ワード線と各ビット線の交差点毎に設けられた（ｎ＋１）×ｍ個のメモリセル（図示せず）とを有し、ｎ＋１個のワード線ＷＬ０  ，…ＷＬｎ  のうち１個のワード線ＷＬｉ  （ｉ＝０，…ｎ）が選択されたときに、数「ｉ」の２進数の最下位からｊ（ｊ＝１，…ｍ）番目の桁のビット値がビット線ＢＬｊ  から出力されるようにデータが上記メモリセルに記憶された構成となっている。例えばｎ＝２ｍ  −１の場合ＲＯＭ６の具体例を図２に示す。このＲＯＭ６の各ワード線ＷＬｉ  （ｉ＝０，…２ｍ  −１）と各ビット線ＢＬｊ  （ｊ−１，…ｍ）との交差点近傍に、メモリセルを構成するＮチャネルＭＯＳトランジスタ１２ｉｊが設けられている。このトランジスタ１２ｉｊのゲートはワード線ＷＬｉ  に接続され、ソースまたはドレインの一方はビット線ＢＬｊ  に接続され、他方は、電源Ｖｃｃまたは接地電源ＧＮＤに接続されている。図２において、ワード線ＷＬ３  が選択されると、ビット線ＢＬ１  ，ＢＬ２  からは「Ｈ」レベル、すなわち論理値「１」の信号が出力され、他のビット線ＢＬ３  ，…ＢＬｍ  からは「Ｌ」レベル、すなわち論理値「０」の信号が出力される。したがって、ワード線ＷＬ３  が選択された場合はビット線ＢＬ１  ，…ＢＬｍ  からは、１０進数で「３」を表わすｍ桁の２進数００…０１１が出力されることになる。なお、ｍは条件２ｍ  ≧ｎを満している。
【００１５】
選択回路４は比較手段２の出力に基づいて、ＲＯＭ６のｎ＋１個のワード線ＷＬ０  ，…ＷＬｎ  の中から１個のワード線を選択するものであって比較手段２のｎ個の入力ＰＰ１  ，…ＰＰｎ  のうち論理値が「１」である入力の数がｉであるときにワードＷＬｉ  を選択し、活性化する構成となっている。
【００１６】
上述のように構成された実施の形態の加算器において、論理値が「１」である入力の総数がｉ（ｉ≦ｎ）であるｎ個の入力ＰＰ１  ，…ＰＰｎ  が外部から供給されると、比較器２１  ，…２ｉ  からＣＰ１  ＝…ＣＰｉ  ＝１，ＣＰ１  バー＝…＝ＣＰｉ  バー＝０となる比較結果信号が出力されるとともに比較器２ｉ＋１  ，…２ｎ  からはＣＰｉ＋１  ＝…＝ＣＰｎ  ＝０、ＣＰｉ＋１  バー＝…＝ＣＰｎ  バー＝１となる比較結果信号が出力される。これらの比較結果信号に基づいて選択回路４によってＲＯＭ６の１個ワード線ＷＬ０  ，…ＷＬｎ  の中から１本のワード線ＷＬｉ  が選択され、この選択されたワード線ＷＬｉ  のみが活性化される。これにより、ワード線ＷＬｉ  に接続されていた、ＲＯＭ６のメモリセルから、１０進法の数「ｉ」の２進数表現したデータがビット線ＢＬ１  ，…ＢＬｍ  を介して出力される。これは、ｎ個の入力ＰＰ１  ，…ＰＰｎ  の加算結果がＲＯＭ６から出力されることを表わしている。
【００１７】
次にこのような加算器に係る各比較器２ｉ  （ｉ＝１，…ｎ）の具体例を図３に示す。この具体例の比較器２ｉ  は、ＰチャネルＭＯＳトランジスタ２１，２２と、ＮチャネルＭＯＳトランジスタ２３，２４と、ｉ個のＮチャネルＭＯＳトランジスタ２５１  ，…２５ｉ  と、ｎ個のｎチャネルＭＯＳトランジスタ２６１  ，…２６ｎ  と、ｎチャネルＭＯＳトランジスタ２７とを備えている。
【００１８】
トランジスタ２１およびトランジスタ２３のドレインは共通に接続され、トランジスタ２１のソースは電源電圧Ｖｃｃが印加される。また、トランジスタ２２およびトランジスタ２４のドレインは共通に接続され、トランジスタ２２のソースは電源電圧Ｖｃｃが印加される。そしてトランジスタ２１とトランジスタ２３のゲートはトランジスタ２２のドレインに接続され、トランジスタ２２とトランジスタ２４のゲートはトランジスタ２１のドレインに接続される。
【００１９】
トランジスタ２７のソースは接地され、ゲートには外部からイネーブル信号ＥＮが印加される。そしてトランジスタ２３のソースとトランジスタ２７のドレインとの間にｉ個のトランジスタ２５１  ，…２５ｉ  が並列に接続される。なお、これらのｉ個のトランジスタ２５１  ，…２５ｉ  の各ゲートは電源電圧Ｖｃｃが印加される。
【００２０】
また、トランジスタ２４のソースとトランジスタ２７のドレインとの間にｎ個のトランジスタ２６１  ，…２６ｎ  が並列に接続される。そして各トランジスタ２６ｊ  （ｊ＝１，…ｎ）のゲートには入力信号ＰＰｊ  が印加される。
【００２１】
そしてトランジスタ２１とトランジスタ２３の共通に接続されたドレイン端から出力信号ＣＰｉ  が出力され、トランジスタ２２とトランジスタ２４の共通に接続されたドレイン端から信号ＣＰｉ  の反転信号ＣＰｉ  バーが出力される。
【００２２】
なお、上述の比較器２ｉ  において、トランジスタ２５１  の電流駆動能力を０．５とすると、トランジスタ２５２  ，…２５ｉ  およびトランジスタ２６１  ，…２６ｎ  の各電流駆動能力は１となるように設定される。
【００２３】
このように構成された比較器２ｉ  においてｎ個の入力ＰＰ２  ，…ＰＰｎ  が入力されているときにイネーブル信号ＥＮが「０」レベルから「１」レベルになると、トランジスタ２７がＯＮし、トランジスタ２７のドレインの電位が低下する。するとトランジスタ２５１  ，…２５ｉ  は常にＯＮ状態であるからトランジスタ２３のソースの電位も低下する。またｎ個のトランジスタ２６１  ，…２６ｎ  のうち、ゲートに入力される入力信号ＰＰｊ  の論理値が１であるトランジスタ２６ｊ  がＯＮ状態となるから、トランジスタ２４のソースの電位も低下する。
【００２４】
トランジスタ２３のソースの電位とトランジスタ２４のソースの電位のどちらが、より早く低下するかは、ｎ個の入力信号ＰＰ１  ，…ＰＰｎ  の論理値が「１」であるものの総数βによって決定される。
【００２５】
今、β＜ｉと仮定すると、ｎ個のトランジスタ２６１  ，…２６ｎ  のうちＯＮ状態となるものの総数はβであるから、このときのｎ個のトランジスタ２６１  ，…２６ｎ  からなる並列回路を流れる電流はβ（＝β×１）となる。一方、ｉ個のトランジスタ２５１  ，…２５ｉ  からなる並列回路を流れる電流はｉ−０．５（＝（ｉ−１）×１＋０．５）である。これによりｉ個のトランジスタ２５１  ，…２５ｉ  からなる並列回路を流れる電流がｎ個のトランジスタ２６１  ，…２６ｎ  からなる並列回路を流れる電流よりも大きく、トランジスタ２３のソースの電位はトランジスタ２４のソースの電位よりも早く低下する。このため、トランジスタ２３がトランジスタ２４よりも早くＯＮし、トランジスタ２３のドレインの電位はトランジスタ２４のドレインの電位よりも早く低下する。このため、トランジスタ２２がトランジスタ２１よりも早くＯＮし、出力信号ＣＰｉ  は「０」となり、出力信号ＣＰｉ  バーは「１」となる。
【００２６】
一方β≧ｉの場合は、トランジスタ２４のソース電位がトランジスタ２３のソース電位よりも早く低下する。このためβ＜ｉの場合とは逆となり、出力信号ＣＰｉ  は「１」となり出力信号ＣＰｉ  バーは「０」となる。
【００２７】
次に本実施の形態の加算器にかかる選択回路４の具体例を図４に示す。この具体例の選択回路４は２個の反転ゲート４０  ，４ｎ  と、ｎ−１個のＮＯＲゲート４１  ，…４ｎ−１  とを備えている。
【００２８】
反転ゲート４０  は比較器２１  の出力信号ＣＰ１  を受け、この出力信号ＣＰ１  を反転した信号をＲＯＭ６のワード線ＷＬ０  に送出する。
【００２９】
ＮＯＲゲート４ｉ  （ｉ＝１，…ｎ−１）は比較器２ｉ  の出力信号ＣＰｉ  バーと、比較器２ｉ＋１  の出力信号ＣＰｉ＋１  とに基づいてＮＯＲ演算を行い、演算結果をＲＯＭ６のワード線ＷＬｉ  に送出する。
【００３０】
また反転ゲート４ｎ  は比較器２ｎ  の出力信号ＣＰｎ  バーを受け、この出力信号ＣＰｎ  バーを反転した信号をＲＯＭ６のワード線ＷＬｎ  に送出する。
【００３１】
今、ｎ個の入力信号ＰＰ１  ，…ＰＰｎ  の論理値が「１」である入力信号の総数がｉ（０≦ｉ≦ｎ）と仮定すると、ＣＰ１  ＝…＝ＣＰｉ  ＝１、ＣＰｉ＋１  ＝…＝ＣＰｎ  ＝０、ＣＰ１  バー＝…＝ＣＰｉ  バー＝０、ＣＰｉ＋１  バー＝…＝ＣＰｎ  バー＝１であるから、選択回路４からワード線ＷＬｉ  に送出される出力信号のみが「１」となり、他のワード線ＷＬｊ  （ｊ≠ｉ）に送出される出力信号は「０」となる。このため、ワードＷＬｉ  のみが選択されて活性化されることになる。
【００３２】
次に本実施の形態の加算器を、乗算器の同一桁の部分積の加算に用いる場合を図５を参照して説明する。
【００３３】
まず図５（ａ）に示すように８ビットの被乗数（＝００１１０１１１）に８ビットの乗数（＝０１００１１０１）を乗算する場合を考える。
【００３４】
まず乗数の各桁のビットと被乗数の各桁のビットとの部分積が求められる。これらの部分積は８×８個のＡＮＤゲートにより実現される。最下位から８番目の桁の部分積の加算に本実施の形態の加算器を用いる場合を考えると、図１に示す比較手段２の８個の入力信号ＰＰ１  ，…ＰＰ８  の値は図５（ｂ）に示すようにＰＰ１  ＝０、ＰＰ２  ＝０、ＰＰ３  ＝１、ＰＰ４  ＝１、ＰＰ５  ＝０、ＰＰ６  ＝０、ＰＰ７  ＝１、ＰＰ８  ＝０となる。すなわち８個の入力信号ＰＰ１  ，…ＰＰ８  のうち論理値が「１」である入力信号の総数は「３」であるから、「３」を２進数で表現したデータ（＝００１１）がＲＯＭ６のビット線ＢＬ１  ，ＢＬ２  ，ＢＬ３  ，ＢＬ４  から出力される（図５（ｃ）参照）。
【００３５】
なお、乗算の部分積の加算の全てに本実施の形態の加算器を用いる必要はなく、加算すべきビットの数が小さい桁の加算には全加算器を用いることが望ましい。したがって乗算の部分積の加算には本実施の形態の加算器と全加算器とを組合せて用いることが望ましい。
【００３６】
次に本実施の形態の加算器（以下、複数入力加算器ともいう）を乗算器の部分積の加算に用いた場合に高速化が可能であることを図６乃至図１０を参照して説明する。
【００３７】
今、乗算器は３２ビット×３２ビットの乗算器とする。３２ビット×３２ビットの乗算においては、まず始めに部分積の演算が行われる。この部分積は、従来の場合と同様に３２×３２個のＡＮＤゲートによって求められる。そして、同一桁の部分積の加算には複数入力加算器と全加算器とを組合せた部分積加算器を用いて行う。
【００３８】
複数入力加算器の最大入力数が１５であるときにある桁の３２個の部分積の加算を行う部分積加算器においては、図６に示すように複数入力加算器３１，３２を２個並列に使用する。これらの複数入力加算器３１，３２は各々、１５個のＡＮＤゲートからの信号を受けて上記桁の和信号と、１つ上の桁、２つ上の桁、３つ上の桁への桁上げ信号Ｃを出力する。したがってこれらの複数入力加算器３１，３２の次段には３個の全加算器３３，３４，３５が設けられる。更にこれらの３個の全加算器３３，３４，３５の次段には２個の全加算器３６，３７が設けられ、これらの２個の全加算器３６，３７の次段には１個の全加算器３８が設けられている。また、全加算器３８の次段には全加算器３９が設けられ、この全加算器３９の次段には全加算器４０が設けられている。そしてこの全加算器４０から、上記桁の和信号と桁上げ信号が出力される。
【００３９】
次に図６に示す部分積加算器のゲート段数を数えてみると、まず、部分積を求めるＡＮＤゲートは一般にＮＡＮＤゲートと反転ゲートとを組合せて構成されるから、ＡＮＤゲートの段数は２段となる。また複数入力加算器は図１に示すように比較手段２、選択回路４、およびＲＯＭ６から構成されるから複数入力加算器のゲート段数は３段となる。また全加算器のゲート段数は一般に３段となる。したがって図６に示す部分積加算器のゲート段数は最大で２０（＝２＋３×６）段となる（図６参照）。
【００４０】
また加算すべき部分積の個数（入力数）が１５未満である部分積加算器の例を図７乃至図１０に示す。図７は入力数が１４の場合の部分積加算器を、入力数が１５の複数入力加算器と２個の全加算器から構成した一具体例のブロック図である。この図７に示す部分積加算器のゲート段数は最大で１１段となる。
【００４１】
また、入力数が１４の場合の部分積加算器を全加算器のみを用いて構成した例を図８に示す。この図８に示す部分積加算器は１３個の全加算器から構成されており、ゲート段数は最大で２０段となる。
【００４２】
また、入力数が９の場合の部分積加算器の一具体例の構成を図９に示す。この具体例の部分積加算器は７個の全加算器から構成されており、ゲート段数は最大で１４段となる（図９参照）。
【００４３】
また、入力数が１２の場合の部分積加算器の一具体例の構成を図１０に示す。この具体例の部分積加算器は９個の全加算器から構成されており、ゲート段数は最大で１４段となる（図１０参照）。
【００４４】
なお入力数が１３の場合は、図７に示す部分積加算器において、接地電源に接続していない１４個の入力の１つを更に接地電源に接続するか、または図７に示す部分積加算器において、１５個の入力のうちの２つを接地電源に接続して、上記入力を「０」に設定すれば、部分積加算を行うことが可能となる。
【００４５】
同様にして図７乃至図１０に示す部分積加算器において、いくつかの入力を接地電源に接続して、それらの入力を「０」に設定すれば、入力数が４，５，６，７，８，９，１０，１１，の場合の部分積加算を行うことができる。
【００４６】
したがって３２ビット×３２ビットの乗算においては、本実施の形態の加算器（複数入力加算器）を部分積の加算に用いることにより、部分積加算におけるゲート段数は最大でも２０段にすることが可能となる。
【００４７】
これに対して、従来のようにｎビット×ｎビットのアレイ式並列乗算器においては、ｎ×ｎ個のＡＮＤゲートと、ｎ×（ｎ−１）個の全加算器が必要となるので、乗算器全体におけるゲート段数はＡＮＤゲートの２段と全加算器の３段×（ｎ−１）との和、すなわち３ｎ−１段となる。
【００４８】
したがって３２ビット×３２ビットの乗算器においては、最大９５（＝３×３２−１）段のゲートを通って出力されることになる。
【００４９】
以上説明したことにより、本実施の形態の加算器（複数入力加算器）を部分積加算に用いた場合の方が従来の場合に比べてゲート段数を非常に少なくすることが可能となり、高速化することができる。
【００５０】
なお、３２ビット×３２ビットの乗算においては図１１または図１２に示すように部分積アレイ７０の空白部分（同一桁の部分積の個数（ビット数）が１５以上である領域）の同一桁の部分積加算に本実施の形態の加算器と全加算器とを組合せて用い、斜線部（同一桁の部分積の個数が１４以下である領域）の同一桁の部分積加算には図７乃至図１０に示した部分積加算器を用いて行えば、ゲート段数を２０段以下にすることが可能となる。この場合、最終段の加算にはＣＬＡ（Ｃａｒｒｙ  Ｌｏｏｋ  Ａｈｅａｄ）方式の加算器７２を用いれば良い。
【００５１】
なお、図１１および図１２は３２ビット×３２ビットの乗算における部分積アレイ７０を模式的に示した模式図である。この部分積アレイにおいてｘ軸方向において記載されている数字は、この数字のｙ軸方向に配置されている部分積（同一桁の部分積）の個数を示している。
【００５２】
なお、本実施の形態の加算器のＲＯＭ６の代わりに、例えばＥ２  ＰＲＯＭ等の不揮発性メモリを用いても良いことは言うまでもない。
【００５３】
【発明の効果】
以上述べたように本発明によれば、複数ビットの加算を高速に行うことができる。
【００５４】
また、部分積加算を高速に行うことのできる乗算器を得ることができる。
【図面の簡単な説明】
【図１】本発明による加算器の一実施の形態の構成を示すブロック図。
【図２】本発明の加算器にかかるＲＯＭの一具体例の構成を示す回路図。
【図３】本発明の加算器にかかる比較器の一具体例の構成を示す回路図。
【図４】本発明の加算器にかかる選択回路の一具体例の構成を示す回路図。
【図５】本発明の加算器を乗算の部分積加算に用いる場合の説明図。
【図６】入力数が３２の場合の部分積加算器の一具体例の構成を示すブロック図。
【図７】入力数が１４の場合の部分積加算器の一具体例の構成を示すブロック図。
【図８】入力数が１４の場合の部分積加算器の他の具体例の構成を示すブロック図。
【図９】入力数が９の場合の部分積加算器の一具体例の構成を示すブロック図。
【図１０】入力数が１２の場合の部分積加算器の一具体例の構成を示すブロック図。
【図１１】３２ビット×３２ビットの乗算における部分積加算に、本発明の加算器を用いる場合の一例を説明する部分積アレイの構成図。
【図１２】３２ビット×３２ビットの乗算における部分積加算に、本発明の加算器を用いる場合の他の例を説明する、部分積アレイの構成図。
【符号の説明】
２  比較手段
２ｉ  （ｉ＝１，…ｎ）  比較器
４  選択回路
６  ＲＯＭ
【図１】
0003607494.tif 000002
【図２】
0003607494.tif 000003
【図３】
0003607494.tif 000004
【図４】
0003607494.tif 000005
【図５】
0003607494.tif 000006
【図６】
0003607494.tif 000007
【図７】
0003607494.tif 000008
【図８】
0003607494.tif 000009
【図９】
0003607494.tif 000010
【図１０】
0003607494.tif 000011
【図１１】
0003607494.tif 000012
【図１２】
0003607494.tif 000013