(57)【要約】【課題】装置規模を小型化し、且つ演算速度を高速化することが可能な定数乗算装置を提供する。【解決手段】２進６桁の被乗数Ｙの、各桁中に含まれる「１」の個数が４である場合に、１２列、３段の複数の加算点を設定し、被乗数Ｙの最も下の位の「１」が第１桁に存在する場合に、第１段の、第１列から第６列までの加算点の各ａ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を入力する。また、第２〜第３段の各加算点に、乗数Ｘを所定の桁だけシフトした数値を入力する。そして、各加算点の３つの入力のうち２以上が常時０となる場合は、この加算点に加算器を設置せず、１つの入力が常時０となる場合にはこの加算点に半加算器（ＨＡ）を設置し、それ以外の加算点に全加算器（ＦＡ）を設置する。このような構成により、装置規模を小型化し、更に演算速度を高速化することができる。【選択図】図２
2011165060.tif 000002
【特許請求の範囲】
【請求項１】
２進Ｎ桁（Ｎ≧１）の定数とされた被乗数Ｙに、２進数の任意の乗数Ｘを乗じる定数乗算装置において、
前記被乗数Ｙの、各桁中に含まれる「１」の個数がＰ（２≦Ｐ≦Ｎ）である場合に、２Ｎ列、（Ｐ−１）段の複数の加算器から成る加算器群を設け、
前記各加算器は、ａ、ｂ、ｃの入力、及びＳ、Ｃの出力を有し、
前記被乗数Ｙの、最も下の位の「１」が第Ｑ1桁（１≦Ｑ1≦Ｎ）に存在する場合に、第１段の、第Ｑ1列から第（Ｑ1＋Ｎ−１）列までの加算器の各ａ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、
下からｐ番目（２≦ｐ≦Ｐ）の位の「１」が第Ｑp桁に存在する場合に、第（ｐ−１）段の加算器に対して、第Ｑp列から第（Ｑp＋Ｎ−１）列までの加算器の各ｃ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、
Ｐ≧３の場合には、
第ｍ段（２≦ｍ≦Ｐ−１）、第ｎ列（１≦ｎ≦Ｎ）の加算器のａ入力に、第（ｍ−１）段、第ｎ列の加算器のＳ出力を供給し、第ｍ段、第ｎ列の加算器のｂ入力には、第（ｍ−１）段、第（ｎ−１）列の加算器のＣ出力を供給し、
第（Ｐ−１）段の各加算器のＣ出力、及びＳ出力を、最終段加算器に入力し、該最終段加算器の出力信号、及び第（Ｐ−１）段、第１列の加算器のＳ出力を、乗算結果とすることを特徴とする定数乗算装置。
【請求項２】
２進Ｎ桁（Ｎ≧１）の定数とされた被乗数Ｙに、２進数の任意の乗数Ｘを乗じる定数乗算装置において、
前記被乗数Ｙの、各桁中に含まれる「１」の個数がＰ（２≦Ｐ≦Ｎ）である場合に、２Ｎ列、（Ｐ−１）段の複数の加算点を設定した加算手段を設け、
前記各加算点は、ａ、ｂ、ｃの入力、及びＳ、Ｃの出力を有し、
前記被乗数Ｙの、最も下の位の「１」が第Ｑ1桁（１≦Ｑ1≦Ｎ）に存在する場合に、第１段の、第Ｑ1列から第（Ｑ1＋Ｎ−１）列までの加算点の各ａ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を入力し、
下からｐ番目（２≦ｐ≦Ｐ）の位の「１」が第Ｑp桁に存在する場合に、第（ｐ−１）段の加算点に対して、第Ｑp列から第（Ｑp＋Ｎ−１）列までの加算点の各ｃ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、
Ｐ≧３の場合には、
第ｍ段（２≦ｍ≦Ｐ−１）、第ｎ列（１≦ｎ≦Ｎ）の加算点の各ａ入力に、第（ｍ−１）段、第ｎ列の加算器の各Ｓ出力を供給し、第ｍ段、第ｎ列の加算点のｂ入力には、第（ｍ−１）段、第（ｎ−１）列の加算点の各Ｃ出力を供給し、
第（Ｐ−１）段の各加算点のＣ出力、及びＳ出力を、最終段加算器に入力し、該最終段加算器の出力信号、及び第（Ｐ−１）段、第１列の加算点のＳ出力を、乗算結果とすると共に、
各入力ａ、ｂ、ｃのうち、２以上の入力に常時「０」が入力される加算点には、加算器を設けず、各入力ａ、ｂ、ｃのうち、１つの入力に常時「０」が入力される加算点には半加算器を設け、上記以外の加算点に全加算器を設けることを特徴とする定数乗算装置。
【請求項３】
２進Ｎ桁（Ｎ≧１）の定数とされた被乗数Ｙに、２進数の任意の乗数Ｘを乗じる定数乗算装置において、
前記被乗数Ｙの、各桁中に含まれる「１」の個数がＰ（３≦Ｐ≦Ｎ）である場合に、２Ｎ列、（Ｐ−２）段の複数の加算点を設定した加算手段を設け、
前記各加算点は、ａ、ｂ、ｃの入力、及びＳ、Ｃの出力を有し、
前記被乗数Ｙの、最も下の位の「１」が第Ｑ1桁（１≦Ｑ1≦Ｎ）に存在する場合に、第１段の、第Ｑ1列から第（Ｑ1＋Ｎ−１）列までの加算点の各ａ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、
下から２番目の位の「１」が第Ｑ2桁（２≦Ｑ2≦Ｎ）に存在する場合に、第１段の加算点に対して、第Ｑ2列から第（Ｑ2＋Ｎ−１）列までの加算点の各ｂ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、
下からｐ番目（３≦ｐ≦Ｐ）の位の「１」が第Ｑp桁に存在する場合に、第（ｐ−２）段の加算点に対して、第Ｑp列から第（Ｑp＋Ｎ−１）列までの加算点の各ｃ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、
且つ、
第ｍ段（２≦ｍ≦Ｐ−２）、第ｎ列（１≦ｎ≦Ｎ）の加算点のａ入力に、第（ｍ−１）段、第ｎ列の加算点のＳ出力を供給し、第ｍ段、第ｎ列の加算点のｂ入力には、第（ｍ−１）段、第（ｎ−１）列の加算点のＣ出力を供給し、
第（Ｐ−２）段の各加算点のＣ出力、及びＳ出力を、最終段加算器に入力し、該最終段加算器の出力信号、及び第（Ｐ−２）段、第１列の加算点のＳ出力を、乗算結果とすると共に、
各入力ａ、ｂ、ｃのうち、２以上の入力に常時「０」が入力される加算点には、加算器を設けず、各入力ａ、ｂ、ｃのうち、１つの入力に常時「０」が入力される加算点には半加算器を設け、上記以外の加算点に全加算器を設けることを特徴とする定数乗算装置。
【請求項４】
前記最終段加算器を、桁上げ先見加算器とすることを特徴とする請求項１〜請求項３のいずれか１項に記載の定数乗算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２進数で示された２つの数値の乗算を実行する乗算装置に係り、特に、一方の数値が予め決められた定数である定数乗算装置に関する。
【背景技術】
【０００２】
桁数が同一である２進数どうしの乗算を実行する従来の手順を図８に示す。図８では、２進数の乗数Ｘ（＝１１０１０１）と、２進数の被乗数Ｙ（＝１０１１０１）との乗算手順を示しており、被乗数Ｙの最下位の桁（２の０乗の桁）から最上位の桁（２の５乗の桁）に向けて順次「０」であるか「１」であるかを判断し、「１」である場合には、乗数Ｘの値を桁数分だけシフトした数値を決定し、「０」である場合にはその桁は全て「０」とする。
【０００３】
即ち、図８に示す例では、２*0（「*0」はべき乗を示す、即ち２の０乗）の桁、２*2の桁、２*3の桁、２*5の桁が「１」であり、２*1の桁、及び２*4の桁は「０」であるので、乗数Ｘをシフトしない数値ｑ１、乗数Ｘを２桁分上位にシフトした数値ｑ２、乗数Ｘを３桁分上位にシフトした数値ｑ３、及び乗数Ｘを５桁分上位にシフトした数値ｑ４を部分積とし、これらの数値ｑ１〜ｑ４を加算することにより、乗算結果Ｚ１を得ることができる。
【０００４】
この際、被乗数Ｙの２*1の桁の「０」（数値ｒ１）、及び２*4の桁の「０」（数値ｒ２）についても加算処理を行っている。従って、数値ｑ１〜ｑ４、及び数値ｒ１、ｒ２の６個の数値を加算することにより（６回の加算処理を行うことにより）、乗算結果Ｚ１を算出している。ここで、被乗数Ｙが定数である場合には、数値ｒ１、ｒ２が「０」になることは事前に判っているので、この加算処理に所要する時間は、演算時間の短縮化の妨げになってしまう。
【０００５】
そこで、２進数の定数とされた被乗数Ｙと、この被乗数Ｙと同一の桁数を有する任意の乗数Ｘを乗算するために、例えば、特開２００３−１４０８８４号公報（特許文献１）に記載された定数乗算装置が提案されている。
【０００６】
上記の特許文献１では、各桁毎に求められた部分積をシフト加算することにより、演算の回数を減少することが開示されている。即ち、図９に示すように、加算装置２１に図８に示した数値ｑ１とｑ２を入力し、この加算結果を加算装置２３、及びシフト補正回路２２に出力する。シフト補正回路２２では、数値ｑ１とｑ２との加算結果を３桁分シフトさせる処理を行い、シフト後の数値を加算装置２３に出力する。そして、加算装置２３では、加算装置２１の出力値とシフト補正回路２２の出力値の加算を行い、この加算結果を乗数Ｘと被乗数Ｙとの乗算結果Ｚ１とする。
【０００７】
上記の処理では、被乗数Ｙが「１０１１０１」であり、「１０１」が２度繰り返される数値となっているので、数値ｑ１とｑ２を加算し、この加算結果を３桁分上位にシフトし、これらを加算することにより、乗算結果Ｚ１を算出している。
【０００８】
ところが、特許文献１に記載された手法では、乗算の取り扱い桁が増加したり、被乗数Ｙ値に含まれる「１」、「０」の配列パターン（ここでは「１０１」）が複数存在しない場合は、加算装置の種類が増え、それらを加算する加算装置が２段、３段と徐々に増加する。更に、桁数ｎが奇数の場合には、最低でも１つの部分積が余るので、これを加算する加算装置が必要になる。その結果、扱う桁数が小さい場合には有効であるが、桁数が大きくなるに連れて、加算装置による加算処理が増加して行き、乗算結果を算出するまでの演算時間が長くなり、演算処理が遅くなるという欠点がある。
【０００９】
他方、２進数の乗算を高速度で実行する演算装置として、配列型乗算器が知られている。図１０は、２進６桁の乗数Ｘ（１１０１０１）と被乗数Ｙ（１０１１０１）との乗算を実行する配列型乗算器の構成を示す説明図である。
【００１０】
図１０に示すように、配列型乗算器３９は、５段の桁上げ保存加算器３２〜３６を備えており、各桁上げ保存加算器３２〜３６にはそれぞれ５個の全加算器（ＦＡ）が設けられている。以下では、最上段の桁上げ保存加算器３２を第１段、最下段の桁上げ保存加算器３６を第５段とし、各桁上げ保存加算器３２〜３６に設けられる全加算器（ＦＡ）のうち右端を第１列、左端を第５列として示すことにする。そして、第５段の桁上げ保存加算器３６の下段には、桁上げ先見加算器３８が設けられている。
【００１１】
全加算器（ＦＡ）は、図４（ａ）に示すように、３つの入力、及び２つの出力を有しており、このうち上側からの入力をａ入力、右上からの入力をｂ入力、右側からの入力をｃ入力とする。また、下側への出力をＳ出力、左下への出力をＣ出力とする。そして、ａ入力、ｂ入力、ｃ入力に入力されるデータが全て１である場合には、Ｓ出力、Ｃ出力を共に１とし、１が２個存在する場合にはＳ出力を０、Ｃ出力を１とし、１が１個存在する場合にはＳ出力を１、Ｃ出力を０とし、１が存在しない場合（全て０の場合）にはＳ出力、Ｃ出力共に０とする。等価回路は、図４（ｂ）のような構成となり、真理値表は図４（ｃ）のようになる。
【００１２】
ここで、「乗数Ｘ＝１１０１０１」の右側の桁から左側の桁に向けて符号ｘ0〜ｘ5で示す。従って、ｘ0＝１、ｘ1＝０、ｘ2＝１、ｘ3＝０、ｘ4＝１、ｘ5＝１である。また、「被乗数Ｙ＝１０１１０１」の右側の桁から左側の桁に向けて符号ｙ0〜ｙ5で示す。従って、ｙ0＝１、ｙ1＝０、ｙ2＝１、ｙ3＝１、ｙ4＝０、ｙ5＝１である。
【００１３】
そして、図１０に示すように、第１段の第１〜第５列の全加算器（ＦＡ）のａ入力には、「ｘm＊ｙ0」（但し、ｍ＝１〜５）の演算結果が入力される。また、「ｘ0＊ｙ0」の演算結果は、その後加算されることが無いので、そのまま出力Ｐ０とされる。なお、図１０に示すＰ０(1)は、Ｐ０の数値が１であることを示している。
【００１４】
また、第１段の第１〜第５列の全加算器（ＦＡ）のｂ入力には、上段からの桁上げが存在しないので、全て０が入力される。
【００１５】
更に、第１段の第１〜第５列の全加算器（ＦＡ）のｃ入力には、「ｘm-1＊ｙ1」（但し、１≦ｍ≦５）の演算結果が入力される。上記のように、ｙ1＝０であるから、第１段の第１〜第５列の全加算器（ＦＡ）のｃ入力は、全て０となる。また、第１段、第１列の全加算器（ＦＡ）のＳ出力は、その後加算されることが無いので、そのまま出力Ｐ１とされる。
【００１６】
一方、第２段、第１〜第４列の全加算器（ＦＡ）のａ入力には、第１段、第２〜第５列の全加算器（ＦＡ）のＳ出力が入力され、第２段、第５列の全加算器（ＦＡ）のａ入力には「ｘ5＊ｙ1」の演算結果が入力される。第２段、第１〜第５列の全加算器（ＦＡ）のｂ入力には、第１段、第１〜第５列の全加算器（ＦＡ）のＣ出力が入力される。更に、第２段、第１〜第５列の全加算器（ＦＡ）のｃ入力には、「ｘm-1＊ｙ2」（但し、１≦ｍ≦５）の演算結果が入力される。第２段、第１列のＳ出力は、その後加算されることが無いので、そのまま出力Ｐ２とされる。
【００１７】
同様に、第３段、第４段、第５段における第１〜第５列の全加算器（ＦＡ）のａ、ｂ、ｃ入力に各種のデータが入力され、Ｓ出力、Ｃ出力を出力する。そして、第３段、第１列の全加算器（ＦＡ）のＳ出力が、出力Ｐ３とされ、第４段、第１列の全加算器（ＦＡ）のＳ出力が、出力Ｐ４とされ、第５段、第１列の全加算器（ＦＡ）のＳ出力が、出力Ｐ５とされる。
【００１８】
更に、第５段、第１列の全加算器（ＦＡ）のＣ出力、及び第５段、第２〜第５列の全加算器（ＦＡ）のＳ及びＣ出力、及び「ｘ5＊ｙ5」の演算結果は、桁上げ先見加算器３８に入力され、該桁上げ先見加算器３８による演算により、出力Ｐ６〜Ｐ１１が得られる。
【００１９】
こうして、２進１２桁の出力Ｐ０〜Ｐ１１を求めることができ、この数値が乗数Ｘと被乗数Ｙとの乗算結果となる。
【先行技術文献】
【特許文献】
【００２０】
【特許文献１】特開２００３−１４０８８４号公報
【発明の概要】
【発明が解決しようとする課題】
【００２１】
上述したように、特許文献１に開示された従来例は、乗数Ｘ及び被乗数Ｙの桁数が大きくなると、加算装置の数が増大し、且つ加算処理の回数が増大するので、装置が大規模化し、且つ、演算時間が長くなるという問題が発生する。
【００２２】
一方、図１０に示したように、複数段の桁上げ保存加算器３２〜３６を有する配列型乗算器３９を用いる方法では、被乗数Ｙに含まれる「０」の桁に対しても乗数Ｘとの論理和を求め、加算処理しても意味を成さない論理和の値「０」を入力する桁上げ保存加算器が存在する場合がある。例えば、図１０に示す第４段の桁上げ保存加算器３５に設けられた各全加算器（ＦＡ）は、ｃ入力が全て０となるので、これらの全加算器（ＦＡ）は不要である。しかし、従来の配列型乗算器３９では、被乗数Ｙを固定することについて考慮されていないので、従来の配列型乗算器３９を、被乗数Ｙが固定された定数乗算装置として用いる場合には、本来不要である加算器が設けられ、且つ加算処理が行われるので、装置規模が大型化するばかりでなく、演算速度が遅くなるという欠点があった。
【００２３】
本発明は、このような従来の課題を解決するためになされたものであり、その目的とするところは、装置規模を小型化し、且つ演算速度を高速化することが可能な定数乗算装置を提供することにある。
【課題を解決するための手段】
【００２４】
上記目的を達成するため、本願請求項１に記載の発明は、２進Ｎ桁（Ｎ≧１）の定数とされた被乗数Ｙに、２進数の任意の乗数Ｘを乗じる定数乗算装置において、前記被乗数Ｙの、各桁中に含まれる「１」の個数がＰ（２≦Ｐ≦Ｎ）である場合に、２Ｎ列、（Ｐ−１）段の複数の加算器から成る加算器群を設け、前記各加算器は、ａ、ｂ、ｃの入力、及びＳ、Ｃの出力を有し、前記被乗数Ｙの、最も下の位の「１」が第Ｑ1桁（１≦Ｑ1≦Ｎ）に存在する場合に、第１段の、第Ｑ1列から第（Ｑ1＋Ｎ−１）列までの加算器の各ａ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、下からｐ番目（２≦ｐ≦Ｐ）の位の「１」が第Ｑp桁に存在する場合に、第（ｐ−１）段の加算器に対して、第Ｑp列から第（Ｑp＋Ｎ−１）列までの加算器の各ｃ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、Ｐ≧３の場合には、第ｍ段（２≦ｍ≦Ｐ−１）、第ｎ列（１≦ｎ≦Ｎ）の加算器のａ入力に、第（ｍ−１）段、第ｎ列の加算器のＳ出力を供給し、第ｍ段、第ｎ列の加算器のｂ入力には、第（ｍ−１）段、第（ｎ−１）列の加算器のＣ出力を供給し、第（Ｐ−１）段の各加算器のＣ出力、及びＳ出力を、最終段加算器に入力し、該最終段加算器の出力信号、及び第（Ｐ−１）段、第１列の加算器のＳ出力を、乗算結果とすることを特徴とする。
【００２５】
また、２進Ｎ桁（Ｎ≧１）の定数とされた被乗数Ｙに、２進数の任意の乗数Ｘを乗じる定数乗算装置において、前記被乗数Ｙの、各桁中に含まれる「１」の個数がＰ（２≦Ｐ≦Ｎ）である場合に、２Ｎ列、（Ｐ−１）段の複数の加算点を設定した加算手段を設け、前記各加算点は、ａ、ｂ、ｃの入力、及びＳ、Ｃの出力を有し、前記被乗数Ｙの、最も下の位の「１」が第Ｑ1桁（１≦Ｑ1≦Ｎ）に存在する場合に、第１段の、第Ｑ1列から第（Ｑ1＋Ｎ−１）列までの加算点の各ａ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を入力し、下からｐ番目（２≦ｐ≦Ｐ）の位の「１」が第Ｑp桁に存在する場合に、第（ｐ−１）段の加算点に対して、第Ｑp列から第（Ｑp＋Ｎ−１）列までの加算点の各ｃ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、Ｐ≧３の場合には、第ｍ段（２≦ｍ≦Ｐ−１）、第ｎ列（１≦ｎ≦Ｎ）の加算点の各ａ入力に、第（ｍ−１）段、第ｎ列の加算点の各Ｓ出力を供給し、第ｍ段、第ｎ列の加算点のｂ入力には、第（ｍ−１）段、第（ｎ−１）列の加算点の各Ｃ出力を供給し、第（Ｐ−１）段の各加算点のＣ出力、及びＳ出力を、最終段加算器に入力し、該最終段加算器の出力信号、及び第（Ｐ−１）段、第１列の加算点のＳ出力を、乗算結果とすると共に、前記加算手段に設定した各加算点で、各入力ａ、ｂ、ｃのうち、２以上の入力に常時「０」が入力される加算点には、加算器を設けず、それ以外の加算点に加算器を設ける構成とすることも可能である。
【００２６】
請求項２に記載の発明は、２進Ｎ桁（Ｎ≧１）の定数とされた被乗数Ｙに、２進数の任意の乗数Ｘを乗じる定数乗算装置において、前記被乗数Ｙの、各桁中に含まれる「１」の個数がＰ（２≦Ｐ≦Ｎ）である場合に、２Ｎ列、（Ｐ−１）段の複数の加算点を設定した加算手段を設け、前記各加算点は、ａ、ｂ、ｃの入力、及びＳ、Ｃの出力を有し、前記被乗数Ｙの、最も下の位の「１」が第Ｑ1桁（１≦Ｑ1≦Ｎ）に存在する場合に、第１段の、第Ｑ1列から第（Ｑ1＋Ｎ−１）列までの加算点の各ａ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を入力し、下からｐ番目（２≦ｐ≦Ｐ）の位の「１」が第Ｑp桁に存在する場合に、第（ｐ−１）段の加算点に対して、第Ｑp列から第（Ｑp＋Ｎ−１）列までの加算点の各ｃ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、Ｐ≧３の場合には、第ｍ段（２≦ｍ≦Ｐ−１）、第ｎ列（１≦ｎ≦Ｎ）の加算点の各ａ入力に、第（ｍ−１）段、第ｎ列の加算器の各Ｓ出力を供給し、第ｍ段、第ｎ列の加算点のｂ入力には、第（ｍ−１）段、第（ｎ−１）列の加算点の各Ｃ出力を供給し、第（Ｐ−１）段の各加算点のＣ出力、及びＳ出力を、最終段加算器に入力し、該最終段加算器の出力信号、及び第（Ｐ−１）段、第１列の加算点のＳ出力を、乗算結果とすると共に、各入力ａ、ｂ、ｃのうち、２以上の入力に常時「０」が入力される加算点には、加算器を設けず、各入力ａ、ｂ、ｃのうち、１つの入力に常時「０」が入力される加算点には半加算器を設け、上記以外の加算点に全加算器を設けることを特徴とする。
【００２７】
また、２進Ｎ桁（Ｎ≧１）の定数とされた被乗数Ｙに、２進数の任意の乗数Ｘを乗じる定数乗算装置において、前記被乗数Ｙの、各桁中に含まれる「１」の個数がＰ（３≦Ｐ≦Ｎ）である場合に、２Ｎ列、（Ｐ−２）段の複数の加算器から成る加算器群を設け、前記各加算器は、ａ、ｂ、ｃの入力、及びＳ、Ｃの出力を有し、前記被乗数Ｙの、最も下の位の「１」が第Ｑ1桁（１≦Ｑ1≦Ｎ）に存在する場合に、第１段の、第Ｑ1列から第（Ｑ1＋Ｎ−１）列までの加算器の各ａ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、下から２番目の位の「１」が第Ｑ2桁（２≦Ｑ2≦Ｎ）に存在する場合に、第１段の加算器に対して、第Ｑ2列から第（Ｑ2＋Ｎ−１）列までの加算器の各ｂ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、下からｐ番目（３≦ｐ≦Ｐ）の位の「１」が第Ｑp桁に存在する場合に、第（ｐ−２）段の加算器に対して、第Ｑp列から第（Ｑp＋Ｎ−１）列までの加算器の各ｃ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、且つ、第ｍ段（２≦ｍ≦Ｐ−２）、第ｎ列（１≦ｎ≦Ｎ）の加算器のａ入力に、第（ｍ−１）段、第ｎ列の加算器のＳ出力を供給し、第ｍ段、第ｎ列の加算器のｂ入力には、第（ｍ−１）段、第（ｎ−１）列の加算器のＣ出力を供給し、第（Ｐ−２）段の各加算器のＣ出力、及びＳ出力を、最終段加算器に入力し、該最終段加算器の出力信号、及び第（Ｐ−２）段、第１列の加算器のＳ出力を、乗算結果とすることも可能である。
【００２８】
更に、２進Ｎ桁（Ｎ≧１）の定数とされた被乗数Ｙに、２進数の任意の乗数Ｘを乗じる定数乗算装置において、前記被乗数Ｙの、各桁中に含まれる「１」の個数がＰ（３≦Ｐ≦Ｎ）である場合に、２Ｎ列、（Ｐ−２）段の複数の加算点を設定した加算手段を設け、前記各加算点は、ａ、ｂ、ｃの入力、及びＳ、Ｃの出力を有し、前記被乗数Ｙの、最も下の位の「１」が第Ｑ1桁（１≦Ｑ1≦Ｎ）に存在する場合に、第１段の、第Ｑ1列から第（Ｑ1＋Ｎ−１）列までの加算点の各ａ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、下から２番目の位の「１」が第Ｑ2桁（２≦Ｑ2≦Ｎ）に存在する場合に、第１段の加算点に対して、第Ｑ2列から第（Ｑ2＋Ｎ−１）列までの加算点の各ｂ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、下からｐ番目（３≦ｐ≦Ｐ）の位の「１」が第Ｑp桁に存在する場合に、第（ｐ−２）段の加算点に対して、第Ｑp列から第（Ｑp＋Ｎ−１）列までの加算点の各ｃ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、且つ、第ｍ段（２≦ｍ≦Ｐ−２）、第ｎ列（１≦ｎ≦Ｎ）の加算点のａ入力に、第（ｍ−１）段、第ｎ列の加算点のＳ出力を供給し、第ｍ段、第ｎ列の加算点のｂ入力には、第（ｍ−１）段、第（ｎ−１）列の加算点のＣ出力を供給し、第（Ｐ−２）段の各加算点のＣ出力、及びＳ出力を、最終段加算器に入力し、該最終段加算器の出力信号、及び第（Ｐ−２）段、第１列の加算点のＳ出力を、乗算結果とすると共に、前記加算手段に設定した各加算点で、各入力ａ、ｂ、ｃのうち、２以上の入力に常時「０」が入力される加算点には、加算器を設けず、それ以外の加算点に加算器を設ける構成とすることも可能である。
【００２９】
請求項３に記載の発明は、２進Ｎ桁（Ｎ≧１）の定数とされた被乗数Ｙに、２進数の任意の乗数Ｘを乗じる定数乗算装置において、前記被乗数Ｙの、各桁中に含まれる「１」の個数がＰ（３≦Ｐ≦Ｎ）である場合に、２Ｎ列、（Ｐ−２）段の複数の加算点を設定した加算手段を設け、前記各加算点は、ａ、ｂ、ｃの入力、及びＳ、Ｃの出力を有し、前記被乗数Ｙの、最も下の位の「１」が第Ｑ1桁（１≦Ｑ1≦Ｎ）に存在する場合に、第１段の、第Ｑ1列から第（Ｑ1＋Ｎ−１）列までの加算点の各ａ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、下から２番目の位の「１」が第Ｑ2桁（２≦Ｑ2≦Ｎ）に存在する場合に、第１段の加算点に対して、第Ｑ2列から第（Ｑ2＋Ｎ−１）列までの加算点の各ｂ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、下からｐ番目（３≦ｐ≦Ｐ）の位の「１」が第Ｑp桁に存在する場合に、第（ｐ−２）段の加算点に対して、第Ｑp列から第（Ｑp＋Ｎ−１）列までの加算点の各ｃ入力にＮ桁の乗数Ｘの、第１桁から第Ｎ桁までの各数値を代入し、且つ、第ｍ段（２≦ｍ≦Ｐ−２）、第ｎ列（１≦ｎ≦Ｎ）の加算点のａ入力に、第（ｍ−１）段、第ｎ列の加算点のＳ出力を供給し、第ｍ段、第ｎ列の加算点のｂ入力には、第（ｍ−１）段、第（ｎ−１）列の加算点のＣ出力を供給し、第（Ｐ−２）段の各加算点のＣ出力、及びＳ出力を、最終段加算器に入力し、該最終段加算器の出力信号、及び第（Ｐ−２）段、第１列の加算点のＳ出力を、乗算結果とすると共に、各入力ａ、ｂ、ｃのうち、２以上の入力に常時「０」が入力される加算点には、加算器を設けず、各入力ａ、ｂ、ｃのうち、１つの入力に常時「０」が入力される加算点には半加算器を設け、上記以外の加算点に全加算器を設けることを特徴とする。
【００３０】
請求項４に記載の発明は、前記最終段加算器を、桁上げ先見加算器とすることを特徴とする。
【発明の効果】
【００３１】
請求項１の発明では、２進数の任意の乗数Ｘと２進Ｎ桁の定数である被乗数Ｙを、桁上げ保存加算器を用いて乗算する際に、Ｎ桁の数値に含まれる「１」の個数をＰとした場合に、（Ｐ−１）段（「１」が４個の場合には３段）の桁上げ保存加算器を設置すれば良いので、従来のように（Ｎ−１）段（６桁の場合には５段）の桁上げ保存加算器を設置する必要が無い。従って、被乗数Ｙに含まれる０の個数が多くなるほど（Ｐが小さくなるほど）、加算器の個数を削減でき、且つ加算処理の回数を削減することができるので、装置を小規模化することができ、且つ、演算速度を高速化することができる。
【００３２】
また、２Ｎ列、（Ｐ−１）段の加算点を設定し、各加算点の３つの入力のうちの２以上が常時０となるか否かに応じて、加算器を設置するか否かを決定している。即ち、３つの入力のうちの２以上が常時０である加算点では、そもそも加算処理は行われないので加算器を割愛し、それ以外の加算点に加算器を設置する構成としている。従って、不要な加算点に設置する加算器を削減することができ、装置全体を小規模化することができ、且つ、コストダウンを図ることができる。
【００３３】
請求項２の発明では、２Ｎ列、（Ｐ−１）段の加算点を設定し、各加算点の３つの入力のうち、常時０となる個数に応じて、全加算器（ＦＡ）を設置するか、半加算器（ＨＡ）を設置するか、或いは加算器を設置しないかを決定する。即ち、３つの入力のうちの２以上が常時０である加算点では、そもそも加算処理は行われないので加算器を割愛し、３つの入力のうち１つが常時０である場合には、多くても２値の加算が行われるだけであるので半加算器（ＨＡ）を設置し、それ以外の加算点に全加算器（ＦＡ）を設置する構成としている。従って、不要な加算点に設置する加算器を削減することができ、装置全体をより一層小規模化することができ、且つ、コストダウンを図ることができる。
【００３４】
また、前述した請求項１の定数乗算装置の構成において、第１段の加算器のｂ入力に、乗数Ｘの数値を入力するので、請求項１の発明と対比して、更に１段分の桁上げ保存加算器の各加算器を割愛することができ、装置規模をより一層小型化することができる。なおかつ演算速度を高速化することができる。
【００３５】
更に、前述した請求項２の定数乗算装置の構成において、第１段の加算器のｂ入力に、乗数Ｘの数値を入力するので、請求項１の発明と対比して、更に１段分の桁上げ保存加算器の各加算器を割愛することができ、装置規模をより一層小型化することができる。なおかつ、演算速度を高速化することができる。
【００３６】
請求項３の発明では、前述した請求項３の定数乗算装置の構成において、第１段の加算器のｂ入力に、乗数Ｘの数値を入力するので、請求項１の発明と対比して、更に１段分の桁上げ保存加算器の各加算器を割愛することができ、装置規模をより一層小型化することができる。なおかつ、演算速度を高速化することができる。
【００３７】
請求項４の発明では、最終段に設ける加算器を桁上げ先見加算器とするので、乗数、及び被乗数の桁数が増大した場合でも演算速度が低下することなく乗算処理を実行することができる。
【図面の簡単な説明】
【００３８】
【図１】本発明の第１実施形態に係る定数乗算装置の構成を示す説明図である。
【図２】本発明の第２実施形態に係る定数乗算装置の構成を示す説明図である。
【図３】半加算器の動作を示す説明図であり、（ａ）は接続図、（ｂ）は等価回路、（ｃ）は真理値表である。
【図４】全加算器の動作を示す説明図であり、（ａ）は接続図、（ｂ）は等価回路、（ｃ）は真理値表である。
【図５】本発明に係る定数乗算装置による演算処理の概要を示す説明図である。
【図６】本発明の第３実施形態に係る定数乗算装置の構成を示す説明図である。
【図７】本発明の第４実施形態に係る定数乗算装置の構成を示す説明図である。
【図８】従来における２進数の乗算手順を示す説明図である。
【図９】特許文献１に記載された２進数の乗算手順を示す説明図である。
【図１０】２進数の乗算を配列型乗算器を用いて実行する場合の説明図である。
【発明を実施するための形態】
【００３９】
以下、本発明の実施形態を図面に基づいて説明する。まず、本発明の考え方を図５に示す演算式を参照して説明する。まず、定数とされた被乗数Ｙを２のべき乗毎に分割する。図５（ａ）に示す例では、被乗数Ｙ＝１０１１０１（２進）＝４５（１０進）であるから、２*5＝３２と、２*3＝８と、２*2＝４と、２*0＝１との合計となる。そして、これらの数値に任意に設定される乗数Ｘを乗算し、各乗算結果を加算した結果が、ＸとＹの乗算結果となる。
【００４０】
つまり、任意の乗数Ｘと定数である被乗数Ｙ（＝４５）の乗算は、次の（１）式となる。
【００４１】
Ｙ＊Ｘ＝４５＊Ｘ
＝（３２＋８＋４＋１）＊Ｘ
＝３２Ｘ＋８Ｘ＋４Ｘ＋１Ｘ          ・・・（１）
（１）式中の３２Ｘは、２*5とＸを掛け合わせているので、２進数で表現される乗数Ｘの値を上位に５桁シフトさせれば良い（図５（ｂ）のａ１）。同様に、８Ｘは、乗数Ｘの値を上位に３桁シフトし（図５（ｂ）のａ２）、４Ｘは、乗数Ｘの値を上位に２桁シフト（図５（ｂ）のａ３）し、１Ｘは、追加する０が無いのでそのままで良い（図５（ｂ）のａ４）。即ち、シフトしない。そして、上記のａ１、ａ２、ａ３、ａ４を加算することにより、乗数Ｘと被乗数Ｙ（＝４５）との乗算結果Ａ１が得られる。
【００４２】
即ち、本発明では、２進６桁で示される被乗数Ｙのうち、「０」の桁が存在する場合に、この桁における加算処理を割愛することにより、加算器の個数を削減し、且つ加算処理の実行回数を削減する。上記の例では、第２桁（２*1の桁）と第５桁（２*4の桁）が「０」であるので、この桁の加算処理が割愛されている。以下、各実施形態について説明する。
【００４３】
［第１実施形態の説明］
図１は、本発明の第１実施形態に係る定数乗算装置の構成を示す説明図である。この定数乗算装置５６は、２進６桁の定数である被乗数Ｙ（＝１０１１０１）と、やはり２進６桁の任意の乗数（本実施形態ではＸ＝１１０１０１としている）の乗算を行うものである。
【００４４】
図１に示すように、定数乗算装置５６は、３段の桁上げ保存加算器５２，５３，５４を備えており、各桁上げ保存加算器５２，５３，５４には、それぞれ１２個の全加算器（ＦＡ）が設けられている。以下では、１２個の全加算器（ＦＡ）のうち、右端を第１列、左端を第１２列とする。
【００４５】
ここで、被乗数Ｙの６桁の数値のうち、「１」は４個存在するので、桁上げ保存加算器の個数は１を減じて３個とされている。また、乗数Ｘ及び被乗数Ｙが６桁であるので、各桁上げ保存加算器５２，５３，５４に設けられる全加算器（ＦＡ）の個数は６を２倍して１２個とされている。一般化して表現すれば、被乗数ＹがＮ桁であり、被乗数Ｙに含まれる「１」の個数がＰ（Ｐ≦Ｎ）である場合には、桁上げ保存加算器の個数はＰ−１段とされ、更に、各桁上げ保存加算器５２，５３，５４に設けられる全加算器（ＦＡ）の個数は２Ｎ個である。即ち、２Ｎ列、（Ｐ−１）段の全加算器（ＦＡ）が設けられる。
【００４６】
また、３段目に設けられる桁上げ保存加算器５４の下段には、桁上げ先見加算器（最終段加算器）５５が設けられている。
【００４７】
全加算器（ＦＡ）は、図４（ａ）に示すように３つの入力、及び２つの出力を有しており、このうち上側からの入力をａ入力、右上からの入力をｂ入力、右側からの入力をｃ入力とする。また、下側への出力を和としてＳ（サム）出力、左下への出力を桁上がりとしてＣ（キャリー）出力とする。また、図４（ｂ）に示す如くの論理回路で示すことができる。故に、ａ入力、ｂ入力、ｃ入力に入力されるデータが全て１である場合には、Ｓ出力、Ｃ出力を共に１とし、１が２個存在する場合にはＳ出力を０、Ｃ出力を１とし、１が１個存在する場合にはＳ出力を１、Ｃ出力を０とし、１が存在しない場合（全て０の場合）にはＳ出力、Ｃ出力共に０とする。なお、真理値表は図４（ｃ）に示す通りである。
【００４８】
図１に示す桁上げ先見加算器５５は、周知の技術であり、２つの数値を加算する際に、これに先んじて各桁の桁上がり値（全加算器のＣ出力に相当）を算出する。従って、各桁の全加算器（ＦＡ）での演算では、下位の桁からの桁上げが事前に判っているので、各桁の全加算器（ＦＡ）ではこれを考慮して加算処理を行えば良い。そして、桁上げ先見加算器５５では、加算対象となる２つの値が何桁であっても演算処理時間は変化せず、順次桁上げ加算器のように取り扱う数値の桁数の増加に伴って演算処理に要する時間が長くなるということは無いので、演算の高速化に極めて有利であるといえる。
【００４９】
同時に桁上げ先見加算器は桁数の２乗に比例してハードウェア量が増えることが知られており、桁数が増える場合は一般的に４ビット単位の比較的小さい回路で構成できる桁上げ先見加算器を木状に組み合わせて使う。本実施形態では、より演算時間の短い桁上げ先見加算器を用いる。
【００５０】
次に、上述のように構成された第１実施形態に係る定数乗算装置５６の作動について説明する。
【００５１】
第１段の桁上げ保存加算器５２の、第１列（最も右側の列）の全加算器（ＦＡ）のａ入力には、乗数Ｘの第１桁の数値ｘ0（本実施形態では１）が入力され、第２列の全加算器（ＦＡ）のａ入力には、乗数Ｘの第２桁の数値ｘ1（本実施形態では０）が入力され、同様に第３列〜第６列の全加算器（ＦＡ）のａ入力には、乗数Ｘの第３桁〜第６桁の数値ｘ2〜ｘ5が入力される。
【００５２】
即ち、２進６桁で示される被乗数Ｙの、第１桁（最も右側）の数値が１であるので、第１段の桁上げ保存加算器５２の第１列〜第６列の全加算器（ＦＡ）のａ入力に、乗数Ｘの６桁の数値をそれぞれ入力する。これは、図５（ｂ）に示したａ４に相当する。一般化して表現すれば、２進Ｎ桁で示される被乗数Ｙの最も下位の「１」が、第Ｑ1桁（１≦Ｑ1≦Ｎ）に存在する場合には、第Ｑ1列から第（Ｑ1＋Ｎ−１）列までの各全加算器（ＦＡ）のａ入力に、Ｎ桁の乗数Ｘの第１桁から第Ｎ桁までの数値を入力する。なお、第１段の桁上げ保存加算器５２の、上記以外の全加算器（ＦＡ）（第７列〜第１２列のＦＡ）のａ入力には、０が入力される。
【００５３】
また、第１段の桁上げ保存加算器５２の、第３列の全加算器（ＦＡ）のｃ入力には、乗数Ｘの第１桁の数値ｘ0（本実施形態では１）が入力され、第４列の全加算器（ＦＡ）のｃ入力には、乗数Ｘの第２桁の数値ｘ1（本実施形態では０）が入力され、同様に第５列〜第８列の全加算器（ＦＡ）のｃ入力には、乗数Ｘの第３桁〜第６桁の数値ｘ2〜ｘ5が入力される。これは、図５（ｂ）に示したａ３に相当する。
【００５４】
即ち、２進６桁で示される被乗数Ｙの、第３桁（右から３番目）の数値が１であるので、第１段の桁上げ保存加算器５２の第３列〜第８列の全加算器（ＦＡ）のｃ入力に、乗数Ｘの６桁の数値がそれぞれ入力される。なお、第１段の桁上げ保存加算器５２の、上記以外の全加算器（ＦＡ）（第１列、第２列、第９列〜第１２列のＦＡ）のｃ入力には、０が入力される。
【００５５】
更に、第２段の桁上げ保存加算器５３の、第４列の全加算器（ＦＡ）のｃ入力には、乗数Ｘの第１桁の数値ｘ0（本実施形態では１）が入力され、第５列の全加算器（ＦＡ）のｃ入力には、乗数Ｘの第２桁の数値ｘ1（本実施形態では０）が入力され、同様に第６列〜第９列の全加算器（ＦＡ）のｃ入力には、乗数Ｘの第３桁〜第６桁の数値ｘ2〜ｘ5が入力される。これは、図５（ｂ）に示したａ２に相当する。
【００５６】
即ち、２進６桁で示される被乗数Ｙの、第４桁（右から４番目）の数値が１であるので、第２段の桁上げ保存加算器５３の第４列〜第９列の全加算器（ＦＡ）のｃ入力に、乗数Ｘの６桁の数値がそれぞれ入力される。なお、第２段の桁上げ保存加算器５３の、上記以外の全加算器（ＦＡ）（第１列〜第３列、第１０列〜第１２列のＦＡ）のｃ入力には、０が入力される。
【００５７】
また、第３段の桁上げ保存加算器５４の、第６列の全加算器（ＦＡ）のｃ入力には、乗数Ｘの第１桁の数値ｘ0（本実施形態では１）が入力され、第７列の全加算器（ＦＡ）のｃ入力には、乗数Ｘの第２桁の数値ｘ1（本実施形態では０）が入力され、同様に第８列〜第１１列の全加算器（ＦＡ）のｃ入力には、乗数Ｘの第３桁〜第６桁の数値ｘ2〜ｘ5が入力される。これは、図５（ｂ）のａ１に相当する。
【００５８】
即ち、２進６桁で示される被乗数Ｙの、第６桁（右から６番目、即ち左端）の数値が１であるので、第３段の桁上げ保存加算器５４の第６列〜第１１列の全加算器（ＦＡ）のｃ入力に、乗数Ｘの６桁の数値がそれぞれ入力される。なお、第３段の桁上げ保存加算器５４の、上記以外の全加算器（ＦＡ）（第１列〜第５列、第１２列のＦＡ）のｃ入力には、０が入力される。
【００５９】
上記の内容を一般化して表現すれば、第１段〜第３段の各桁上げ保存加算器５２〜５４において、２進Ｎ桁で示される被乗数Ｙの下からｐ番目（２≦ｐ≦Ｐ；Ｐは１の個数）の「１」が、第Ｑp桁（１≦Ｑp≦Ｎ）に存在する場合には、第Ｑp列から第（Ｑp＋Ｎ−１）列までの各全加算器（ＦＡ）のｃ入力に、Ｎ桁の乗数Ｘの第１桁から第Ｎ桁までの数値を入力する。
【００６０】
また、第１段の桁上げ保存加算器５２の各全加算器（ＦＡ）のｂ入力には、全て０が入力され、Ｓ出力は第２段の桁上げ保存加算器５３のａ入力に供給され、Ｃ出力は第２段の桁上げ保存加算器５３の、１列だけ上位桁（左側）の全加算器（ＦＡ）のｂ入力に供給される。
【００６１】
第２段の桁上げ保存加算器５３の各全加算器（ＦＡ）の、Ｓ出力は第３段の桁上げ保存加算器５４のａ入力に供給され、Ｃ出力は第３段の桁上げ保存加算器５４の、１列だけ上位桁（左側）の全加算器（ＦＡ）のｂ入力に供給される。
【００６２】
また、第３段の桁上げ保存加算器５４の各全加算器（ＦＡ）の、Ｓ出力、及びＣ出力は桁上げ先見加算器５５に供給される。但し、第３段、第１列の全加算器（ＦＡ）のＳ出力は、桁上げ先見加算器５５に供給されなくても良く、このＳ出力はそのまま出力Ｐ０とされる。
【００６３】
つまり、第ｍ段（２≦ｍ≦Ｐ−１；Ｐは１の個数）、第ｎ列（１≦ｎ≦Ｎ）の全加算器（ＦＡ）のａ入力に、第（ｍ−１）段、第ｎ列の全加算器（ＦＡ）のＳ出力を供給し、第ｍ段、第ｎ列の全加算器（ＦＡ）のｂ入力には、第（ｍ−１）段、第（ｎ−１）列の全加算器（ＦＡ）のＣ出力を供給する。更に、第（Ｐ−１）段の各全加算器（ＦＡ）のＣ出力、及びＳ出力を、桁上げ先見加算器５５（最終段加算器）に入力し、加算処理を実行する。なお、第（Ｐ−１）段、第１列の全加算器（ＦＡ）のＳ出力は、その後加算されることなくそのまま出力Ｐ０となるので、桁上げ先見加算器５５に供給されなくても良い。
【００６４】
桁上げ先見加算器５５では、第３段の桁上げ保存加算器５４の第１列の全加算器（ＦＡ）のＣ出力と、第２列の全加算器（ＦＡ）のＳ出力を加算し、その加算結果のＳ出力を出力Ｐ１とし、第２列の全加算器（ＦＡ）のＣ出力と、第３列の全加算器（ＦＡ）のＳ出力を加算し、その加算結果のＳ出力を出力Ｐ２とする。そして、これと同様の処理を繰り返して、出力Ｐ３〜Ｐ１１を決定する。また、第３段の桁上げ保存加算器５４の第１列の全加算器（ＦＡ）のＳ出力を、出力Ｐ０とする。こうして決定された２進１２桁の出力Ｐ０〜Ｐ１１が乗数Ｘと被乗数Ｙとの乗算結果となる。
【００６５】
このようにして、第１実施形態に係る定数乗算装置５６では、２進Ｎ桁で示される被乗数Ｙが定数である場合に、Ｎ桁の数値に含まれる「１」の個数をＰとすると、（Ｐ−１）段（「１」が４個の場合には３段）の桁上げ保存加算器を用いれば良いので、従来のように（Ｎ−１）段（６桁の場合には５段）の桁上げ保存加算器を設置する必要が無い。従って、被乗数Ｙに含まれる「０」の個数が多くなるほど、加算器の個数を削減でき、且つ加算処理の回数を削減することができる。このため、装置を小規模化することができ、また、演算速度を高速化することができる。
【００６６】
［第２実施形態の説明］
次に、本発明の第２実施形態について説明する。図２は、第２実施形態に係る定数乗算装置６３の構成を示す説明図である。図２に示すように、この定数乗算装置６３は、桁上げ保存加算器群６１と、桁上げ先見加算器６２を備えている。
【００６７】
桁上げ保存加算器群６１は、第１段に４列の半加算器（ＨＡ）を備え、第２段に４列の全加算器（ＦＡ）及び１列の半加算器（ＨＡ）を備え、更に、第３段に、１列の半加算器（ＨＡ）及び４列の全加算器（ＦＡ）を有している。
【００６８】
半加算器（ＨＡ）は、図３（ａ）に示すように、図４（ａ）に示した全加算器（ＦＡ）のｂ入力が存在しない構成である。また、図３（ｂ）に示す論理回路で示すことができる。従って、ａ入力、ｃ入力に入力されるデータが共に１である場合には、Ｓ出力を０、Ｃ出力を１とし、いずれか一方が１である場合にはＳ出力を１、Ｃ出力を０とし、１が存在しない場合（双方が０の場合）にはＳ出力、Ｃ出力共に０とする。なお、真理値表は図３（ｃ）に示す通りである。
【００６９】
次に、第２実施形態に係る定数乗算装置６３の作動について説明する。図２に示す定数乗算装置６３は、図１に示した定数乗算装置５６から不要な全加算器（ＦＡ）を取り除き、更に、半加算器（ＨＡ）で代用できるものについては、半加算器（ＨＡ）に置き換えることにより、全体の構成を簡素化している。以下、詳細に説明する。
【００７０】
上述した第１実施形態では、被乗数Ｙが２進Ｎ桁であり、且つ被乗数Ｙに存在する１の個数がＰである場合には、２Ｎ列、（Ｐ−１）段の全加算器（ＦＡ）を設ける構成とした。これに対して、第２実施形態では、まず、２Ｎ列、（Ｐ−１）段の加算点を設定する。即ち、図１に示した１２列（２Ｎ列）、３段（Ｐ−１段）の各全加算器（ＦＡ）の設置位置を加算点として設定する。この際、加算点は３６箇所に存在することになる。
【００７１】
そして、各加算点の３つの入力（全加算器のａ、ｂ、ｃの３入力に対応）のうち、２以上の入力が常時０である加算点には、加算器を設置しない。例えば、図１において、第１段、第１列の加算点では、ｂ入力が常時０、且つｃ入力が常時０であるから、この加算点には、加算器を設置しない。
【００７２】
また、各加算点の３つの入力のうち、１つの入力が常時０である加算点には、半加算器（ＨＡ）を設置する。例えば、図１において、第１段、第３列〜第６列の各加算点では、ｂ入力が常時０であるから、この加算点に半加算器（ＨＡ）を設置する。同様に、第２段、第８列の加算点ではｂ入力が常時０であり、且つ、第３段、第５列の加算点ではｃ入力が常時０であるから、この加算点に半加算器（ＨＡ）を設置する。更に、上記以外の加算点には全加算器（ＦＡ）を設置する。
【００７３】
その結果、桁上げ保存加算器群６１は、図２に示す如くとなり、８個の全加算器（ＦＡ）と６個の半加算器（ＨＡ）の、合計１４個の加算器のみの構成となる。そして、乗数Ｘの第１桁の数値ｘ0を出力Ｐ０とし、第２桁の数値ｘ1を出力Ｐ１とし、第１段、第３列の半加算器（ＨＡ）のＳ出力を出力Ｐ２とし、第２段、第４列の全加算器（ＦＡ）のＳ出力を出力Ｐ３とし、第３段、第５列の半加算器（ＨＡ）のＳ出力を出力Ｐ４とし、更に、桁上げ先見加算器６２の出力を、出力Ｐ５〜Ｐ１１とする。こうして、乗数Ｘと被乗数Ｙとの乗算結果がＰ０〜Ｐ１１として得られるのである。
【００７４】
このようにして、第２実施形態に係る定数乗算装置では、２Ｎ列、（Ｐ−１）段の加算点を設定し、各加算点の３つの入力のうち、常時０となる個数に応じて、全加算器（ＦＡ）を設置するか、半加算器（ＨＡ）を設置するか、或いは加算器を設置しないかを決定する。
【００７５】
即ち、３つの入力のうちの２つが常時０である加算点では、そもそも加算処理は行われないので加算器を割愛し、３つの入力のうち１つが常時０である場合には、多くても２値の加算が行われるだけであるので、半加算器（ＨＡ）を設置し、それ以外の加算点に全加算器（ＦＡ）を設置する構成としている。
【００７６】
従って、不要な加算点に設置する加算器を削減することができ、前述した第１実施形態の効果に加え、使用する加算器の個数をより一層削減することができ、装置全体を小規模化することができ、且つ、コストダウンを図ることができる。
【００７７】
なお、上述した第２実施形態では、３つの入力のうちの１つが常時０である加算点に半加算器（ＨＡ）を設ける例について説明したが、この半加算器（ＨＡ）を全加算器（ＦＡ）とすることも可能である。即ち、加算器の設置を省略できる加算点以外に、全て全加算器（ＦＡ）を設ける構成とすることもできる。
【００７８】
［第３実施形態の説明］
次に、本発明に係る定数乗算装置の第３実施形態について説明する。図６は、本発明の第３実施形態に係る定数乗算装置の構成を示す説明図である。この定数乗算装置７５は、前述した第１実施形態と同様に、２進６桁の定数である被乗数Ｙ（＝１０１１０１）と、やはり２進６桁の任意の乗数（本実施形態ではＸ＝１１０１０１としている）の乗算を行うものである。
【００７９】
図６に示すように、定数乗算装置７５は、２段の桁上げ保存加算器７２，７３を備えており、各桁上げ保存加算器７２，７３には、それぞれ１２個の全加算器（ＦＡ）が設けられている。以下では、１２個の全加算器（ＦＡ）のうち、右端を第１列、左端を第１２列とする。
【００８０】
ここで、被乗数Ｙの６桁の数値のうち、「１」は４個存在するので、桁上げ保存加算器の個数は２を減じて２個とされている。また、被乗数Ｙが６桁であるので、各桁上げ保存加算器７２，７３に設けられる全加算器（ＦＡ）の個数は６を２倍して１２個とされている。一般化して表現すれば、被乗数ＹがＮ桁であり、被乗数Ｙに含まれる「１」の個数がＰ（Ｐ≦２）である場合は、桁上げ保存加算器の個数は１段とされ、Ｐ（３≦Ｐ≦Ｎ）である場合には、桁上げ保存加算器の個数は（Ｐ−２）段とされ、更に、各桁上げ保存加算器７２，７３に設けられる全加算器（ＦＡ）の個数は２Ｎ個である。即ち、２Ｎ列、（Ｐ−２）段（Ｐ−２の値が０以下の場合は１段）の全加算器（ＦＡ）が設けられる。
【００８１】
また、２段目に設けられる桁上げ保存加算器７３の下段には、桁上げ先見加算器（最終段加算器）７４が設けられている。
【００８２】
次に、上述のように構成された第３実施形態に係る定数乗算装置７５の作動について説明する。
【００８３】
第１段の桁上げ保存加算器７２の、第１列（最も右側の列）の全加算器（ＦＡ）のａ入力には、乗数Ｘの第１桁の数値ｘ0（本実施形態では１）が入力され、第２列の全加算器（ＦＡ）のａ入力には、乗数Ｘの第２桁の数値ｘ1（本実施形態では０）が入力され、同様に第３列〜第６列の全加算器（ＦＡ）のａ入力には、乗数Ｘの第３桁〜第６桁の数値ｘ2〜ｘ5が入力される。
【００８４】
即ち、２進６桁で示される被乗数Ｙの、第１桁（最も右側）の数値が１であるので、第１段の桁上げ保存加算器７２の第１列〜第６列の全加算器（ＦＡ）のａ入力に、乗数Ｘの６桁の数値をそれぞれ入力する。一般化して表現すれば、２進Ｎ桁で示される被乗数Ｙの最も下位の「１」が、第Ｑ1桁（１≦Ｑ1≦Ｎ）に存在する場合には、第Ｑ1列から第（Ｑ1＋Ｎ−１）列までの各全加算器（ＦＡ）のａ入力に、Ｎ桁の乗数Ｘの第１桁から第Ｎ桁までの数値を入力する。なお、第１段の桁上げ保存加算器７２の、上記以外の全加算器（ＦＡ）（第７列〜第１２列のＦＡ）のａ入力には、０が入力される。
【００８５】
また、第１段の桁上げ保存加算器７２の、第３列の全加算器（ＦＡ）のｂ入力には、乗数Ｘの第１桁の数値ｘ0（本実施形態では１）が入力され、第４列の全加算器（ＦＡ）のｂ入力には、乗数Ｘの第２桁の数値ｘ1（本実施形態では０）が入力され、同様に第５列〜第８列の全加算器（ＦＡ）のｂ入力には、乗数Ｘの第３桁〜第６桁の数値ｘ2〜ｘ5が入力される。
【００８６】
即ち、２進６桁で示される被乗数Ｙの、第３桁（右から３番目）の数値が１であるので、第１段の桁上げ保存加算器７２の第３列〜第８列の全加算器（ＦＡ）のｂ入力に、乗数Ｘの６桁の数値がそれぞれ入力される。なお、第１段の桁上げ保存加算器７２の、上記以外の全加算器（ＦＡ）（第１列、第２列、第９列〜第１２列のＦＡ）のｂ入力には、０が入力される。
【００８７】
これを一般化して表現すれば、下から２番目の位の「１」が第Ｑ2桁（２≦Ｑ2≦Ｎ）に存在する場合に、第１段に設けられる全加算器（ＦＡ）に対して、第Ｑ2列から第（Ｑ2＋Ｎ−１）列までの全加算器（ＦＡ）の各ｂ入力に、Ｎ桁の乗数Ｘの第１桁から第Ｎ桁までの各数値ｘ0〜ｘ5を入力する。
【００８８】
更に、第１段の桁上げ保存加算器７２の、第４列の全加算器（ＦＡ）のｃ入力には、乗数Ｘの第１桁の数値ｘ0（本実施形態では１）が入力され、第５列の全加算器（ＦＡ）のｃ入力には、乗数Ｘの第２桁の数値ｘ1（本実施形態では０）が入力され、同様に第６列〜第９列の全加算器（ＦＡ）のｃ入力には、乗数Ｘの第３桁〜第６桁の数値ｘ2〜ｘ5が入力される。
【００８９】
即ち、２進６桁で示される被乗数Ｙの、第４桁（右から４番目）の数値が１であるので、第１段の桁上げ保存加算器７２の第４列〜第９列の全加算器（ＦＡ）のｃ入力に、乗数Ｘの６桁の数値がそれぞれ入力される。なお、第１段の桁上げ保存加算器７２の、上記以外の全加算器（ＦＡ）（第１列〜第３列、第１０列〜第１２列のＦＡ）のｃ入力には、０が入力される。
【００９０】
また、第２段の桁上げ保存加算器７３の、第６列の全加算器（ＦＡ）のｃ入力には、乗数Ｘの第１桁の数値ｘ0（本実施形態では１）が入力され、第７列の全加算器（ＦＡ）のｃ入力には、乗数Ｘの第２桁の数値ｘ1（本実施形態では０）が入力され、同様に第８列〜第１１列の全加算器（ＦＡ）のｃ入力には、乗数Ｘの第３桁〜第６桁の数値ｘ2〜ｘ5が入力される。
【００９１】
即ち、２進６桁で示される被乗数Ｙの、第６桁（右から６番目、即ち左端）の数値が１であるので、第２段の桁上げ保存加算器７３の第６列〜第１１列の全加算器（ＦＡ）のｃ入力に、乗数Ｘの６桁の数値がそれぞれ入力される。なお、第２段の桁上げ保存加算器７３の、上記以外の全加算器（ＦＡ）（第１列〜第５列、第１２列のＦＡ）のｃ入力には、０が入力される。
【００９２】
上記の内容を一般化して表現すれば、第１段、第２段の各桁上げ保存加算器７２，７３において、２進Ｎ桁で示される被乗数Ｙの下からｐ番目（３≦ｐ≦Ｐ；Ｐは１の個数）の「１」が、第Ｑp桁（１≦Ｑp≦Ｎ）に存在する場合には、第Ｑp列から第（Ｑp＋Ｎ−１）列までの各全加算器（ＦＡ）のｃ入力に、Ｎ桁の乗数Ｘの第１桁から第Ｎ桁までの数値を入力する。
【００９３】
また、第１段の桁上げ保存加算器７２の各全加算器（ＦＡ）のＳ出力は、第２段の桁上げ保存加算器７３のａ入力に供給され、Ｃ出力は第２段の桁上げ保存加算器７３の、１列だけ上位桁（左側）の全加算器（ＦＡ）のｂ入力に供給される。
【００９４】
第２段の桁上げ保存加算器７３の各全加算器（ＦＡ）の、Ｓ出力、及びＣ出力は桁上げ先見加算器７４（最終段加算器）に供給される。但し、第２段、第１列の全加算器（ＦＡ）のＳ出力は、その後加算されること無く出力Ｐ０となるので桁上げ先見加算器７４に入力されなくても良い。
【００９５】
つまり、第ｍ段（２≦ｍ≦Ｐ−２；Ｐは１の個数）、第ｎ列（１≦ｎ≦Ｎ）の全加算器（ＦＡ）のａ入力に、第（ｍ−１）段、第ｎ列の全加算器（ＦＡ）のＳ出力を供給し、第ｍ段、第ｎ列の全加算器（ＦＡ）のｂ入力には、第（ｍ−１）段、第（ｎ−１）列の全加算器（ＦＡ）のＣ出力を供給する。更に、第（Ｐ−２）段の各全加算器（ＦＡ）のＣ出力、及びＳ出力を、桁上げ先見加算器７４に入力し、加算処理を実行する。
【００９６】
即ち、桁上げ先見加算器７４では、第２段の桁上げ保存加算器７３の第１列の全加算器（ＦＡ）のＣ出力と、第２列の全加算器（ＦＡ）のＳ出力を加算し、その加算結果のＳ出力を出力Ｐ１とし、第２列の全加算器（ＦＡ）のＣ出力と、第３列の全加算器（ＦＡ）のＳ出力を加算し、その加算結果のＳ出力を出力Ｐ２とする。そして、これと同様の処理を繰り返して、出力Ｐ３〜Ｐ１１を決定する。また、第２段の桁上げ保存加算器７３の第１列の全加算器（ＦＡ）のＳ出力を、出力Ｐ０とする。こうして決定された２進１２桁の出力Ｐ０〜Ｐ１１が乗数Ｘと被乗数Ｙとの乗算結果となる。
【００９７】
このようにして、第３実施形態に係る定数乗算装置７５では、２進Ｎ桁で示される被乗数Ｙが定数である場合に、Ｎ桁の数値に含まれる「１」の個数をＰとすると、（Ｐ−２）段（「１」が４個の場合には２段、また、Ｐ−２が０以下の場合は１段）の桁上げ保存加算器を用いれば良いので、従来のように（Ｎ−１）段（６桁の場合には５段）の桁上げ保存加算器を設置する必要が無い。従って、被乗数Ｙに含まれる０の個数が多くなるほど、加算器の個数を削減でき、且つ加算処理の回数を削減することができる。このため、装置を小規模化することができ、また、演算速度を高速化することができる。
【００９８】
［第４実施形態の説明］
次に、本発明の第４実施形態について説明する。図７は、第４実施形態に係る定数乗算装置８３の構成を示す説明図である。図７に示すように、この定数乗算装置８３は、桁上げ保存加算器群８１と、桁上げ先見加算器８２を備えている。
【００９９】
桁上げ保存加算器群８１は、第１段に３列の半加算器（ＨＡ）、及び３列の全加算器（ＦＡ）を備え、第２段に２列の半加算器（ＨＡ）及び４列の全加算器（ＦＡ）を備えている。
【０１００】
次に、第４実施形態に係る定数乗算装置８３の作動について説明する。図７に示す定数乗算装置８３は、図６に示した定数乗算装置７５から不要な全加算器（ＦＡ）を取り除き、更に、半加算器（ＨＡ）で代用できるものについては、半加算器（ＨＡ）に置き換えることにより、全体の構成を簡素化している。以下、詳細に説明する。
【０１０１】
上述した第３実施形態では、被乗数Ｙが２進Ｎ桁であり、且つ被乗数Ｙに存在する１の個数がＰである場合には、２Ｎ列、（Ｐ−２）段の全加算器（ＦＡ）を設ける構成とした。これに対して、第４実施形態では、まず、２Ｎ列、（Ｐ−２）段の加算点を設定する。即ち、図６に示した１２列（２Ｎ列）、２段（Ｐ−２段）の各全加算器（ＦＡ）の設置位置を加算点として設定する。この際、加算点は２４箇所に存在することになる。
【０１０２】
そして、各加算点の３つの入力（全加算器のａ、ｂ、ｃの３入力に対応）のうち、２以上の入力が常時０である加算点には、加算器を設置しない。例えば、図６において、第１段、第１列の加算点では、ｂ入力が常時０、且つｃ入力が常時０であるから、この加算点には、加算器を設置しない。
【０１０３】
また、各加算点の３つの入力のうち、１つの入力が常時０である加算点には、半加算器（ＨＡ）を設置する。例えば、図６において、第１段の、第３列、第７列、第８列の各加算点では、ａ入力またはｃ入力が常時０であるから、この加算点に半加算器（ＨＡ）を設置する。同様に、第２段の、第４列、第５列の加算点ではｃ入力が常時０であるから、この加算点に半加算器（ＨＡ）を設置する。更に、上記以外の加算点には全加算器（ＦＡ）を設置する。
【０１０４】
その結果、桁上げ保存加算器群８１は、図７に示す如くとなり、７個の全加算器（ＦＡ）と５個の半加算器（ＨＡ）の、合計１２個の加算器のみの構成となる。そして、乗数Ｘの第１桁の数値ｘ0を出力Ｐ０とし、第２桁の数値ｘ1を出力Ｐ１とし、第１段、第３列の半加算器（ＨＡ）のＳ出力を出力Ｐ２とし、第２段、第４列の全加算器（ＦＡ）のＳ出力を出力Ｐ３とし、更に、桁上げ先見加算器８２の出力を、出力Ｐ４〜Ｐ１１とする。こうして、乗数Ｘと被乗数Ｙとの乗算結果がＰ０〜Ｐ１１として得られるのである。
【０１０５】
このようにして、第４実施形態に係る定数乗算装置では、２Ｎ列、（Ｐ−２）段の加算点を設定し、各加算点の３つの入力のうち、常時０となる個数に応じて、全加算器（ＦＡ）を設置するか、半加算器（ＨＡ）を設置するか、或いは加算器を設置しないかを決定する。
【０１０６】
即ち、３つの入力のうちの２つ以上が常時０である加算点では、そもそも加算処理は行われないので加算器を割愛し、３つの入力のうち１つが常時０である場合には、多くても２値の加算が行われるだけであるので、半加算器（ＨＡ）を設置し、それ以外の加算点に全加算器（ＦＡ）を設置する構成としている。
【０１０７】
従って、不要な加算点に設置する加算器を削減することができ、前述した第３実施形態の効果に加え、使用する加算器の個数をより一層削減することができ、装置全体を小規模化することができ、且つ、コストダウンを図ることができる。
【０１０８】
なお、上述した第４実施形態では、３つの入力のうちの１つが常時０である加算点に半加算器（ＨＡ）を設ける例について説明したが、この半加算器（ＨＡ）を全加算器（ＦＡ）とすることも可能である。即ち、加算器の設置を省略できる加算点以外に、全て全加算器（ＦＡ）を設ける構成とすることもできる。
【０１０９】
以上、本発明の定数乗算装置を図示の実施形態に基づいて説明したが、本発明はこれに限定されるものではなく、各部の構成は、同様の機能を有する任意の構成のものに置き換えることができる。
【０１１０】
例えば、上述した各実施形態では、乗数Ｘ、及び被乗数Ｙが共に２進６桁である例について説明したが、本発明はこれに限定されるものではなく、２進Ｎ桁の被乗数Ｙに２進数の乗数を乗じる場合に使用することができる。この際、乗数Ｘと被乗数Ｙの桁数が相違する場合でも、上位桁に「０」を付して同一桁に揃えることにより、上記した各実施形態の定数乗算装置を採用することができる。例えば、乗数Ｘが２進３桁で被乗数Ｙが２進６桁であるならば、乗数Ｘの上位桁に「０００」を付して２進６桁に合わせることができる。反対に、乗数Ｘが２進６桁で被乗数Ｙが２進３桁であるならば、被乗数Ｙの上位桁に「０００」を付して２進６桁に合わせることができる。
【産業上の利用可能性】
【０１１１】
本発明は、２進Ｎ桁の定数とされた被乗数Ｙに、２進数の任意の乗数Ｘを乗じる乗算処理を演算する際に利用することができる。
【符号の説明】
【０１１２】
２１，２３  加算装置
２２  シフト補正回路
３２〜３６  桁上げ保存加算器
３８  桁上げ先見加算器
３９  配列型乗算器
５２〜５４  桁上げ保存加算器
５５  桁上げ先見加算器
５６  定数乗算装置
６１  桁上げ保存加算器群
６２  桁上げ先見加算器
６３  定数乗算装置
７２，７３  桁上げ保存加算器
７４  桁上げ先見加算器
７５  定数乗算装置
８１  桁上げ保存加算器群
８２  桁上げ先見加算器
８３  定数乗算装置
【図１】
2011165060.tif 000003
【図２】
2011165060.tif 000004
【図３】
2011165060.tif 000005
【図４】
2011165060.tif 000006
【図５】
2011165060.tif 000007
【図６】
2011165060.tif 000008
【図７】
2011165060.tif 000009
【図８】
2011165060.tif 000010
【図９】
2011165060.tif 000011
【図１０】
2011165060.tif 000012