(57)【要約】【課題】ウォレスツリー回路などの加算回路の設計を自動化することができる加算回路の設計装置とその方法ならびにプログラムを提供する。【解決手段】設計対象とする加算回路には、ツリー状に接続された複数の桁上げ保存加算器が含まれており、そのツリーの初段には、加算される複数の部分積の各桁の信号が入力されている。入力信号数算出部２０において、部分積のビット幅の情報と、部分積が加算に際して最下位桁より上位桁に向かってシフトされるシフト数の情報とに基づいて、加算回路の各桁の入力信号数が算出される。回路構成決定部３０においては、まず、ツリーの初段を構成する桁上げ保存加算器の回路構成が、入力信号数算出部２０において算出された入力信号数に応じてそれぞれ決定される。次いで、初段に続く各段の桁上げ保存加算器の回路構成が、前段の桁上げ保存加算器から入力される信号数に応じて順に決定される。【選択図】　　　図１
2004133861.tif 000002
【特許請求の範囲】
【請求項１】
入力信号を加算して和信号および桁上げ信号を出力する複数の桁上げ保存加算器がツリー状に接続され、複数の入力データの各桁の信号が、上記ツリーの初段を構成する各桁の桁上げ保存加算器に入力される加算回路を構成するため、
上記入力データのビット幅の情報と、上記入力データが加算に際して最下位桁より上位桁に向かってシフトされるシフト数の情報とに基づいて、上記加算回路の各桁の入力信号数を算出する入力信号数算出手段と、
上記ツリーの初段を構成する各桁の桁上げ保存加算器の回路構成を、上記算出された各桁の入力信号数に応じて決定し、初段に続く各段の桁上げ保存加算器の回路構成を、前段の桁上げ保存加算器から入力される信号数に応じて順に決定する回路構成決定手段と
を有する加算回路の設計装置。
【請求項２】
上記ツリーの初段を除く各段に含まれる上記桁上げ保存加算器には、前段の同位桁の桁上げ保存加算器から出力される上記和信号と、前段の下位桁の桁上げ保存加算器から出力される上記桁上げ信号とが入力されており、
上記回路構成決定手段は、それぞれの桁上げ保存加算器に入力される上記和信号の数と上記桁上げ信号の数との和に応じて、当該桁上げ保存加算器の回路構成を決定する、
請求項１に記載の加算回路の設計装置。
【請求項３】
上記回路構成決定手段は、
段方向の回路構成決定処理として、回路構成決定後の桁上げ保存加算器の出力信号数が２と等しいか２より少なく、かつ、同位桁の後段に続く桁上げ保存加算器に対して下位桁からの上記桁上げ信号が生じない段まで、上記ツリーの初段から後段に向かって順に回路構成の決定を行なう段方向の回路構成決定処理を、上記加算回路に対する入力信号の最大桁数より大きく、かつ、上位桁への上記桁上げ信号の数がゼロになる桁まで、上記ツリーの最下位桁から上位桁に向かって順に実行する、
請求項２に記載の加算回路の設計装置。
【請求項４】
上記回路構成決定手段は、
桁方向の回路構成決定処理として、入力信号数がゼロになる桁の下位桁まで、上記ツリーの最下位桁から上位桁に向かって順に回路構成の決定を行なう桁方向の回路構成決定処理を、全ての桁上げ保存加算器の入力信号数が２と等しいか２より少なくなる段まで、上記ツリーの初段から後段に向かって順に実行する、
請求項２に記載の加算回路の設計装置。
【請求項５】
上記回路構成決定手段は、
回路構成の決定対象とする桁上げ保存加算器の入力信号数が１より大きい場合、３つの入力信号を加算して１つの和信号および１つの桁上げ信号を出力する全加算器、２つの入力信号を加算して１つの和信号および１つの桁上げ信号を出力する半加算器、または、１つの入力信号を１つの和信号として出力する信号出力回路のうちの少なくとも１つを、当該入力信号数に応じた数だけ含むように、当該対象とする桁上げ保存加算器の回路構成を決定する、
請求項２に記載の加算回路の設計装置。
【請求項６】
上記回路構成決定手段は、
回路構成の決定対象とする桁上げ保存加算器の入力信号数を３で除した商に応じた数の上記全加算器を含むように、当該対象とする桁上げ保存加算器の回路構成を決定する、
請求項５に記載の加算回路の設計装置。
【請求項７】
上記回路構成決定手段は、
回路構成の決定対象とする桁上げ保存加算器の入力信号数を３で除した余りが２の場合、上記半加算器を１つ含むように、当該対象とする桁上げ保存加算器の回路構成を決定する、
請求項６に記載の加算回路の設計装置。
【請求項８】
上記回路構成決定手段は、
回路構成の決定対象とする桁上げ保存加算器の入力信号数を３で除した余りが１の場合、上記信号出力回路を１つ含むように、当該対象とする桁上げ保存加算器の回路構成を決定する、
請求項６に記載の加算回路の設計装置。
【請求項９】
上記回路構成決定手段は、
回路構成の決定対象とする桁上げ保存加算器の入力信号数が３であり、かつ、当該対象とする桁上げ保存加算器より後段の同位桁の桁上げ保存加算器に対して下位桁からの上記桁上げ信号が生じない場合は、上記半加算器および上記信号出力回路を１つずつ含むように当該対象とする桁上げ保存加算器の回路構成を決定する、
請求項６に記載の加算回路の設計装置。
【請求項１０】
上記回路構成決定手段は、
回路構成の決定対象とする桁上げ保存加算器の入力信号数が２であり、かつ、当該対象とする桁上げ保存加算器より後段の同位桁の桁上げ保存加算器に対して下位桁からの上記桁上げ信号が生じない場合は、上記信号出力回路を２つ含むように当該対象とする桁上げ保存加算器の回路構成を決定する、
請求項７に記載の加算回路の設計装置。
【請求項１１】
上記回路構成決定手段において決定されたそれぞれの桁上げ保存加算器の回路構成に基づいて、上記加算回路の回路構成の情報を生成する回路情報生成手段を含む、
請求項１に記載の加算回路の設計装置。
【請求項１２】
上記回路情報生成手段は、それぞれの桁上げ保存加算器の回路構成に基づいて、所定の記述様式による上記加算回路の回路記述を生成する、
請求項１１に記載の加算回路の設計装置。
【請求項１３】
上記回路情報生成手段において生成された上記加算回路の回路構成の情報を表示する情報表示手段を含む、
請求項１１に記載の加算回路の設計装置。
【請求項１４】
入力信号を加算して和信号および桁上げ信号を出力する複数の桁上げ保存加算器がツリー状に接続され、複数の入力データの各桁の信号が、上記ツリーの初段を構成する各桁の桁上げ保存加算器に入力される加算回路を構成するため、
上記入力データのビット幅の情報と、上記入力データが加算に際して最下位桁より上位桁に向かってシフトされるシフト数の情報とに基づいて、上記加算回路の各桁の入力信号数を算出する第１のステップと、
上記ツリーの初段を構成する各桁の桁上げ保存加算器の回路構成を、上記算出された各桁の入力信号数に応じて決定し、初段に続く各段の桁上げ保存加算器の回路構成を、前段の桁上げ保存加算器から入力される信号数に応じて順に決定する第２のステップと
を有する加算回路の設計方法。
【請求項１５】
上記ツリーの初段を除く各段に含まれる上記桁上げ保存加算器には、前段の同位桁の桁上げ保存加算器から出力される上記和信号と、前段の下位桁の桁上げ保存加算器から出力される上記桁上げ信号とが入力されており、
上記第２のステップにおいて、それぞれの桁上げ保存加算器に入力される上記和信号の数と上記桁上げ信号の数との和に応じて、当該桁上げ保存加算器の回路構成を決定する、
請求項１４に記載の加算回路の設計方法。
【請求項１６】
上記第２のステップは、
回路構成決定後の桁上げ保存加算器の出力信号数が２と等しいか２より少なく、かつ、同位桁の後段に続く桁上げ保存加算器に対して下位桁からの上記桁上げ信号が生じない段まで、上記ツリーの初段から後段に向かって順に回路構成の決定を行なう段方向の回路構成決定ステップと、
上記加算回路に対する入力信号の最大桁数より大きく、かつ、上位桁への上記桁上げ信号の数がゼロになる桁まで、上記段方向の回路構成決定ステップを上記ツリーの最下位桁から上位桁に向かって順に実行する桁方向の回路構成決定ステップとを含む、
請求項１５に記載の加算回路の設計方法。
【請求項１７】
上記第２のステップは、
入力信号数がゼロになる桁の下位桁まで、最下位桁から上位桁に向かって順に回路構成の決定を行なう桁方向の回路構成決定ステップと、
全ての桁上げ保存加算器の入力信号数が２と等しいか２より少なくなる段まで、上記桁方向の回路構成決定ステップを上記ツリーの初段から後段に向かって順に実行する段方向の回路構成決定ステップとを含む、
請求項１５に記載の加算回路の設計方法。
【請求項１８】
上記第２のステップにおいて、
回路構成の決定対象とする桁上げ保存加算器の入力信号数が１より大きい場合、３つの入力信号を加算して１つの和信号および１つの桁上げ信号を出力する全加算器、２つの入力信号を加算して１つの和信号および１つの桁上げ信号を出力する半加算器、または、１つの入力信号を１つの和信号として出力する信号出力回路のうちの少なくとも１つを、当該入力信号数に応じた数だけ含むように、当該対象とする桁上げ保存加算器の回路構成を決定する、
請求項１５に記載の加算回路の設計方法。
【請求項１９】
上記第２のステップにおいて、
回路構成の決定対象とする桁上げ保存加算器の入力信号数を３で除した商に応じた数の上記全加算器を含むように、当該対象とする桁上げ保存加算器の回路構成を決定する、
請求項１８に記載の加算回路の設計方法。
【請求項２０】
上記第２のステップにおいて、
回路構成の決定対象とする桁上げ保存加算器の入力信号数を３で除した余りが２の場合、上記半加算器を１つ含むように、当該対象とする桁上げ保存加算器の回路構成を決定する、
請求項１９に記載の加算回路の設計方法。
【請求項２１】
上記第２のステップにおいて、
回路構成の決定対象とする桁上げ保存加算器の入力信号数を３で除した余りが１の場合、上記信号出力回路を１つ含むように、当該対象とする桁上げ保存加算器の回路構成を決定する、
請求項１９に記載の加算回路の設計方法。
【請求項２２】
上記第２のステップにおいて、
回路構成の決定対象とする桁上げ保存加算器の入力信号数が３であり、かつ、当該対象とする桁上げ保存加算器より後段の同位桁の桁上げ保存加算器に対して下位桁からの上記桁上げ信号が生じない場合は、上記半加算器および上記信号出力回路を１つずつ含むように当該対象とする桁上げ保存加算器の回路構成を決定する、
請求項１９に記載の加算回路の設計方法。
【請求項２３】
上記回路構成決定手段は、
回路構成の決定対象とする桁上げ保存加算器の入力信号数が２であり、かつ、当該対象とする桁上げ保存加算器より後段の同位桁の桁上げ保存加算器に対して下位桁からの上記桁上げ信号が生じない場合は、上記信号出力回路を２つ含むように当該対象とする桁上げ保存加算器の回路構成を決定する、
請求項２０に記載の加算回路の設計方法。
【請求項２４】
それぞれの桁上げ保存加算器の回路構成に基づいて、所定の記述様式による上記加算回路の回路記述を生成する第３のステップを含む、
請求項１５に記載の加算回路の設計方法。
【請求項２５】
入力信号を加算して和信号および桁上げ信号を出力する複数の桁上げ保存加算器がツリー状に接続され、複数の入力データの各桁の信号が、上記ツリーの初段を構成する各桁の桁上げ保存加算器に入力される加算回路を設計する処理装置に、
上記入力データのビット幅の情報と、上記入力データが加算に際して最下位桁より上位桁に向かってシフトされるシフト数の情報とに基づいて、上記加算回路の各桁の入力信号数を算出する第１のステップと、
上記ツリーの初段を構成する各桁の桁上げ保存加算器の回路構成を、上記算出された各桁の入力信号数に応じて決定し、初段に続く各段の桁上げ保存加算器の回路構成を、前段の桁上げ保存加算器から入力される信号数に応じて順に決定する第２のステップと
を有する処理を実行させるプログラム。
【請求項２６】
上記ツリーの初段を除く各段に含まれる上記桁上げ保存加算器には、前段の同位桁の桁上げ保存加算器から出力される上記和信号と、前段の下位桁の桁上げ保存加算器から出力される上記桁上げ信号とが入力されており、
上記第２のステップにおいて、それぞれの桁上げ保存加算器に入力される上記和信号の数と上記桁上げ信号の数との和に応じて、当該桁上げ保存加算器の回路構成を決定する、
請求項２５に記載のプログラム。
【請求項２７】
上記第２のステップは、
回路構成決定後の桁上げ保存加算器の出力信号数が２と等しいか２より少なく、かつ、同位桁の後段に続く桁上げ保存加算器に対して下位桁からの上記桁上げ信号が生じない段まで、上記ツリーの初段から後段に向かって順に回路構成の決定を行なう段方向の回路構成決定ステップと、
上記加算回路に対する入力信号の最大桁数より大きく、かつ、上位桁への上記桁上げ信号の数がゼロになる桁まで、上記段方向の回路構成決定ステップを上記ツリーの最下位桁から上位桁に向かって順に実行する桁方向の回路構成決定ステップとを含む、
請求項２６に記載のプログラム。
【請求項２８】
上記第２のステップは、
入力信号数がゼロになる桁の下位桁まで、最下位桁から上位桁に向かって順に回路構成の決定を行なう桁方向の回路構成決定ステップと、
全ての桁上げ保存加算器の入力信号数が２と等しいか２より少なくなる段まで、上記桁方向の回路構成決定ステップを上記ツリーの初段から後段に向かって順に実行する段方向の回路構成決定ステップとを含む、
請求項２６に記載のプログラム。
【請求項２９】
上記第２のステップにおいて、
回路構成の決定対象とする桁上げ保存加算器の入力信号数が１より大きい場合、３つの入力信号を加算して１つの和信号および１つの桁上げ信号を出力する全加算器、２つの入力信号を加算して１つの和信号および１つの桁上げ信号を出力する半加算器、または、１つの入力信号を１つの和信号として出力する信号出力回路のうちの少なくとも１つを、当該入力信号数に応じた数だけ含むように、当該対象とする桁上げ保存加算器の回路構成を決定する、
請求項２６に記載のプログラム。
【請求項３０】
入力信号を加算して和信号および桁上げ信号を出力する複数の桁上げ保存加算器を有し、
上記複数の桁上げ保存加算器がツリー状に接続され、
複数の入力データの各桁の信号が、上記ツリーの初段を構成する各桁の桁上げ保存加算器に入力され、
上記ツリーの初段を除く各段に含まれる上記桁上げ保存加算器には、前段の同位桁の桁上げ保存加算器から出力される上記和信号と、前段の下位桁の桁上げ保存加算器から出力される上記桁上げ信号とが入力された、
加算回路。
【請求項３１】
上記桁上げ保存加算器は、
３つの入力信号を加算して１つの和信号および１つの桁上げ信号を出力する全加算器、２つの入力信号を加算して１つの和信号および１つの桁上げ信号を出力する半加算器、または、１つの入力信号を１つの和信号として出力する信号出力回路のうちの少なくとも１つを、入力信号数に応じた数だけ含む、
請求項３０に記載の加算回路。
【請求項３２】
上記桁上げ保存加算器は、
入力信号数を３で除した商に応じた数の上記全加算器を含み、
上記入力信号数を３で除した余りが２の場合、上記半加算器を１つ含み、
上記入力信号数を３で除した余りが１の場合、上記信号出力回路を１つ含み、
上記入力信号数が３であり、かつ、自らより後段の同位桁の桁上げ保存加算器に対して下位桁からの上記桁上げ信号が生じない場合は、上記半加算器および上記信号出力回路を１つずつ含み、
上記入力信号数が２であり、かつ、自らより後段の同位桁の桁上げ保存加算器に対して下位桁からの上記桁上げ信号が生じない場合は、上記信号出力回路を２つ含む、
請求項３１に記載の加算回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、電子回路の設計装置およびその方法ならびに設計装置のプログラムに関するものである。
【０００２】
【従来の技術】
従来、デジタル信号処理において用いられる演算回路は、加算、減算、シフトなどの基本演算を組み合わせることで実現されていたが、その動作速度は低速であった。近年では、演算の高速化を図るために、桁上げ保存加算器を使用した演算回路が用いられている。
【０００３】
桁上げ保存加算方式を用いた乗算器や積和演算器などの演算回路は、通常、部分積生成回路、桁上げ保存型の加算回路、および、２入力桁上げ伝播加算回路の３つで構成される。
部分積生成回路では、演算回路に対する入力信号から、部分積が生成される。桁上げ保存型の加算回路では、部分積生成回路から出力された部分積に対し桁上げ保存加算が行われ、部分積の数が２つまで削減される。２入力桁上げ伝播加算回路では、桁上げ保存型の加算回路から出力される２つの部分積の最終的な加算が行われ、１つの演算結果が得られる。
【０００４】
桁上げ保存型の加算回路の１つとして、ウォレスツリー（Ｗａｌｌａｃｅ　ｔｒｅｅ）回路がある。
ウォレスツリー回路は、桁上げ保存加算器（ｃａｒｒｙ　ｓａｖｅ　ａｄｄｅｒ）がツリー状に接続された構造を有している。ツリーの根元には、互いに加算される各桁の信号が入力される。入力された信号は末端に向かうにつれて上位桁に桁上げされることにより減少し、ツリーの末端において最終的に加算される各桁の信号数は２つ以下になる。このため、ウォレスツリー回路の出力では、部分積の数が２つ以下まで削減される。また、ウォレスツリー回路において、加算回路の各桁の加算が並列的に行われるため、演算が高速化される。
たとえば特許文献１に、ウォレスツリー乗算器の従来技術が記載されている。
【０００５】
このウォレスツリー回路は、一般に、他の桁上げ保存型の加算回路と比較して回路構造が不規則になることが知られており、その構成方法に関して明確に形式化された方法が存在しない。
たとえば特許文献２には、桁上げ保存型の加算回路の回路記述を発生する方法が記載されているが、ウォレスツリー回路の回路記述を発生する方法についての記載はない。
【０００６】
【特許文献１】
特開平１０−３０７７０６号公報（第３図、第５図）
【特許文献２】
特開平６−２２３０９７号公報（第１３図）
【０００７】
【発明が解決しようとする課題】
ウォレスツリー回路の不規則性の程度は、ウォレスツリー回路において処理される部分積の構造によって決まる。乗算や積和演算において処理される部分積の構造は一般に規則性を有しており、ウォレスツリー回路の構造も規則的になる。こうしたウォレスツリー回路の構造や構成方法は一般的に良く知られており、その設計は比較的容易である。
【０００８】
しかしながら、一般的な複合演算において処理される部分積は、通常、その構造が不規則であり、こうした不規則な部分積を処理するウォレスツリー回路については、明確に形式化された構成方法が今まで知られていなかった。この場合、ウォレスツリー回路の設計は難易度が高く、設計のための手間と時間を要する問題がある。
【０００９】
また、ウォレスツリー回路は、それが処理する部分積の数と、部分積の信号幅と、最下位桁より上位桁に向かって部分積がシフトされるシフト数とに依存した構造を有するので、各々のウォレスツリー回路は汎用性が低い。このため、演算器の仕様に変更が生じた場合、ウォレスツリー回路を新たに設計し直さなくてはならなくなることが多く、設計期間の長期化を招いてしまう問題がある。
【００１０】
また、各々のウォレスツリー回路の汎用性が低いことから、設計資産としての価値が小さい問題もある。
【００１１】
本発明はかかる事情に鑑みてなされたものであり、その第１の目的は、複数の桁上げ保存加算器がツリー状に接続された加算回路の設計を自動化することができる加算回路の設計装置を提供することにある。
第２の目的は、複数の桁上げ保存加算器がツリー状に接続された加算回路の設計方法を提供することにある。
第３の目的は、複数の桁上げ保存加算器がツリー状に接続された加算回路の設計を自動化することができる加算回路の設計装置のプログラムを提供することにある。
第４の目的は、複数の桁上げ保存加算器が規則的にツリー状に接続され、各桁の加算を並列的に行なうことができる加算回路を提供することにある。
【００１２】
【課題を解決するための手段】
上記の目的を達するため、本発明の第１の観点の加算回路の設計装置は、入力信号を加算して和信号および桁上げ信号を出力する複数の桁上げ保存加算器がツリー状に接続され、複数の入力データの各桁の信号が、上記ツリーの初段を構成する各桁の桁上げ保存加算器に入力される加算回路を構成するため、上記入力データのビット幅の情報と、上記入力データが加算に際して最下位桁より上位桁に向かってシフトされるシフト数の情報とに基づいて、上記加算回路の各桁の入力信号数を算出する入力信号数算出手段と、上記ツリーの初段を構成する各桁の桁上げ保存加算器の回路構成を、上記算出された各桁の入力信号数に応じて決定し、初段に続く各段の桁上げ保存加算器の回路構成を、前段の桁上げ保存加算器から入力される信号数に応じて順に決定する回路構成決定手段とを有する。
好適には、上記ツリーの初段を除く各段に含まれる上記桁上げ保存加算器には、前段の同位桁の桁上げ保存加算器から出力される上記和信号と、前段の下位桁の桁上げ保存加算器から出力される上記桁上げ信号とが入力されており、上記回路構成決定手段は、それぞれの桁上げ保存加算器に入力される上記和信号の数と上記桁上げ信号の数との和に応じて、当該桁上げ保存加算器の回路構成を決定する。
【００１３】
本発明の第１の観点によれば、設計対象とする加算回路には、入力信号を加算して和信号および桁上げ信号を出力する複数の桁上げ保存加算器が含まれている。この複数の桁上げ保存加算器がツリー状に接続され、加算回路へ入力される複数の入力データの各桁の信号が、ツリーの初段を構成する各桁の桁上げ保存加算器に入力されている。入力信号数算出手段において、入力データのビット幅の情報と、入力データが加算に際して最下位桁より上位桁に向かってシフトされるシフト数の情報とに基づいて、加算回路の各桁の入力信号数が算出される。回路構成決定手段では、ツリーの初段を構成する各桁の桁上げ保存加算器の回路構成が、入力信号数算出手段において算出された各桁の入力信号数に応じて決定される。初段に続く各段の桁上げ保存加算器の回路構成は、前段の桁上げ保存加算器から入力される信号数に応じて順に決定される。
また、ツリーの初段を除く各段に含まれる上記桁上げ保存加算器には、前段の同位桁の桁上げ保存加算器から出力される和信号と、前段の下位桁の桁上げ保存加算器から出力される桁上げ信号とが入力されている。回路構成決定手段では、それぞれの桁上げ保存加算器に入力される和信号の数と桁上げ信号の数との和に応じて、桁上げ保存加算器の回路構成が決定される。
【００１４】
本発明の第２の観点の加算回路の設計方法は、入力信号を加算して和信号および桁上げ信号を出力する複数の桁上げ保存加算器がツリー状に接続され、複数の入力データの各桁の信号が、上記ツリーの初段を構成する各桁の桁上げ保存加算器に入力される加算回路を構成するため、上記入力データのビット幅の情報と、上記入力データが加算に際して最下位桁より上位桁に向かってシフトされるシフト数の情報とに基づいて、上記加算回路の各桁の入力信号数を算出する第１のステップと、上記ツリーの初段を構成する各桁の桁上げ保存加算器の回路構成を、上記算出された各桁の入力信号数に応じて決定し、初段に続く各段の桁上げ保存加算器の回路構成を、前段の桁上げ保存加算器から入力される信号数に応じて順に決定する第２のステップとを有する。
好適には、上記ツリーの初段を除く各段に含まれる上記桁上げ保存加算器には、前段の同位桁の桁上げ保存加算器から出力される上記和信号と、前段の下位桁の桁上げ保存加算器から出力される上記桁上げ信号とが入力されており、上記第２のステップにおいて、それぞれの桁上げ保存加算器に入力される上記和信号の数と上記桁上げ信号の数との和に応じて、当該桁上げ保存加算器の回路構成を決定する。
【００１５】
本発明の第３の観点のプログラムは、入力信号を加算して和信号および桁上げ信号を出力する複数の桁上げ保存加算器がツリー状に接続され、複数の入力データの各桁の信号が、上記ツリーの初段を構成する各桁の桁上げ保存加算器に入力される加算回路を設計する処理装置に、上記入力データのビット幅の情報と、上記入力データが加算に際して最下位桁より上位桁に向かってシフトされるシフト数の情報とに基づいて、上記加算回路の各桁の入力信号数を算出する第１のステップと、上記ツリーの初段を構成する各桁の桁上げ保存加算器の回路構成を、上記算出された各桁の入力信号数に応じて決定し、初段に続く各段の桁上げ保存加算器の回路構成を、前段の桁上げ保存加算器から入力される信号数に応じて順に決定する第２のステップとを有する処理を実行させる。
好適には、上記ツリーの初段を除く各段に含まれる上記桁上げ保存加算器には、前段の同位桁の桁上げ保存加算器から出力される上記和信号と、前段の下位桁の桁上げ保存加算器から出力される上記桁上げ信号とが入力されており、上記第２のステップにおいて、それぞれの桁上げ保存加算器に入力される上記和信号の数と上記桁上げ信号の数との和に応じて、当該桁上げ保存加算器の回路構成を決定する。
【００１６】
本発明の第４の観点の加算回路は、入力信号を加算して和信号および桁上げ信号を出力する複数の桁上げ保存加算器を有し、上記複数の桁上げ保存加算器がツリー状に接続され、複数の入力データの各桁の信号が、上記ツリーの初段を構成する各桁の桁上げ保存加算器に入力され、上記ツリーの初段を除く各段に含まれる上記桁上げ保存加算器には、前段の同位桁の桁上げ保存加算器から出力される上記和信号と、前段の下位桁の桁上げ保存加算器から出力される上記桁上げ信号とが入力される。
好適には、３つの入力信号を加算して１つの和信号および１つの桁上げ信号を出力する全加算器、２つの入力信号を加算して１つの和信号および１つの桁上げ信号を出力する半加算器、または、１つの入力信号を１つの和信号として出力する信号出力回路のうちの少なくとも１つを、入力信号数に応じた数だけ含む。
【００１７】
【発明の実施の形態】
本発明の実施形態について、図面を参照しながら述べる。
図１は、本発明の実施形態に係る加算回路の設計装置の構成の一例を示すブロック図である。
図１に示す設計装置は、情報入力部１０と、入力信号数算出部２０と、回路構成決定部８０と、回路情報生成部４０と、情報表示部５０とを有する。
入力信号数算出部２０は、本発明の入力信号数算出手段の一実施形態である。
回路構成決定部３０は、本発明の回路構成決定手段の一実施形態である。
回路情報生成部４０は、本発明の回路情報生成手段の一実施形態である。
情報表示部５０は、本発明の情報表示手段の一実施形態である。
【００１８】
（情報入力部１０）
情報入力部１０は、加算される複数の入力データのビット幅の情報、および、この複数の入力データが加算に際して最下位桁より上位桁に向かってシフトされるシフト数の情報をそれぞれ入力する。
【００１９】
たとえば、乗算や積和演算などにおいて生じるＫ個（Ｋは、‘０’を含む正の整数を示す）の部分積Ｐ（０）〜Ｐ（Ｋ−１）が、上述の複数の入力データとして加算されるものとすると、部分積の全体構造は、部分積Ｐ（０）〜Ｐ（Ｋ−１）のビット幅Ｗ（０）〜Ｗ（Ｋ−１）とシフト数Ｆ（０）〜Ｆ（Ｋ−１）とによって決定される。情報入力部１０は、部分積の全体構造を決めるこれらの情報を入力する。
【００２０】
図２は、設計対象の加算回路において加算される部分積の全体構造の一例を図解した図である。
符号Ａ（ｉ，ｊ）は、部分積Ｐ（ｉ）の最下位ビットを０ビットとした場合において、この最下位ビットからｊビット目の信号を示す。なお、整数ｉは、‘０’から‘Ｋ−１’までの値を有する。また、整数ｊは、‘０’から‘Ｗ（ｉ）−１’の最大値までの値を有する。
図２の例において、加算される部分積の数Ｋは‘５’である。部分積Ｐ（０）のビット幅Ｗ（０）は‘７’、シフト数Ｆ（０）は‘０’である。部分積Ｐ（１）のビット幅Ｗ（１）は‘８’、シフト数Ｆ（１）は‘１’である。部分積Ｐ（２）のビット幅Ｗ（２）は‘５’、シフト数Ｆ（２）は‘３’である。部分積Ｐ（３）のビット幅Ｗ（０）は‘９’、シフト数Ｆ（３）は‘１’である。部分積Ｐ（４）のビット幅Ｗ（４）は‘７’、シフト数Ｆ（４）は‘２’である。
図２に図解されるように、加算される部分積の全体構造は、各部分積のビット幅およびシフト数によって一意に決定される。
【００２１】
情報入力部１０は、たとえばキーボードやマウス、スイッチなど、後段の入力信号数算出部２０へ情報を入力するための種々の装置によって構成される。
【００２２】
（入力信号数算出部２０）
入力信号数算出部２０は、情報入力部１０において入力したビット幅およびシフト数の情報に基づいて、加算回路の各桁の入力信号数を算出する。
【００２３】
たとえば、加算回路の第（ｋ＋１）桁への入力信号の総数を符号Ｉ（ｋ，０）と表した場合、入力信号数Ｉ（ｋ，０）は次式によって求められる。
【００２４】
【数１】
Ｉ（ｋ，０）　＝　Ｄ（０，ｋ−Ｆ（０））　＋　Ｄ（１，ｋ−Ｆ（１））＋…＋Ｄ（Ｋ−１，ｋ−Ｆ（Ｋ−１））　…　（１）
【００２５】
ただし式（１）において、関数Ｄ（ｉ，ｊ）は、部分積Ｐ（ｉ）の最下位からｊビット目の信号Ａ（ｉ，ｊ）が定義されている場合に‘１’、定義されていない場合に‘０’となる。
また式（１）において、整数ｋは、‘０’から最大値Ｌまでの値を有する。最大値Ｌは、次式で表される。
【００２６】
【数２】
Ｌ　＝　ｍａｘ（Ｗ（ｉ）　＋　Ｓ（ｉ））　…　（２）
【００２７】
式（２）において、関数ｍａｘ（Ｗ（ｉ）＋Ｓ（ｉ））は、ビット幅Ｗ（ｉ）とシフト数Ｓ（ｉ）との和の最大値を示している。
【００２８】
たとえば図２に示すように、第１桁すなわちｋ＝０の場合において、シフト数Ｆ（０）は‘０’なので、ｋ−Ｆ（０）＝０が成立する。このため信号Ａ（ｋ−Ｆ（０），０）は信号Ａ（０，０）と等しくなる。図２に示すように、信号Ａ（０，０）は定義されているので、関数Ｄ（０，ｋ−Ｆ（０））は‘１’となる。これに対し、シフト数Ｆ（１）〜Ｆ（４）は‘０’より大きいため、ｋ−Ｆ（１）＜０、ｋ−Ｆ（２）＜０、ｋ−Ｆ（３）＜０、ｋ−Ｆ（４）＜０が成立する。このため、信号Ａ（ｋ−Ｆ（１），０）〜Ａ（ｋ−Ｆ（４），０）は定義されておらず、関数Ｄ（０，ｋ−Ｆ（１））〜Ｄ（０，ｋ−Ｆ（４））は‘０’となる。これらを式（１）に代入することにより、入力信号数Ｉ（０，０）は‘１’となる。
同様に、図２の例において、第２桁の入力信号数Ｉ（１，０）は‘３’、第３桁の入力信号数Ｉ（２，０）は‘４’、第４桁の入力信号数Ｉ（３，０）は‘５’、第５桁の入力信号数Ｉ（４，０）は‘５’、第６桁の入力信号数Ｉ（５，０）は‘５’、第７桁の入力信号数Ｉ（６，０）は‘５’、第８桁の入力信号数Ｉ（７，０）は‘４’、第９桁の入力信号数Ｉ（８，０）は‘３’、第１０桁の入力信号数Ｉ（９，０）は‘１’となる。
【００２９】
（回路構成決定部３０）
回路構成決定部３０は、設計対象の加算回路を構成する複数の桁上げ保存加算器の回路構成を、桁上げ保存加算器への入力信号数に応じてそれぞれ決定する。
【００３０】
図３は、設計対象の加算回路の構成の一例を示すブロック図である。また図４は、図３に示す加算回路の一部を抜き出して示したブロック図である。
設計対象の加算回路は、複数の桁上げ保存加算器Ｍ（ｍ，ｎ）（ｍおよびｎは、‘０’を含む正の整数を示す）がツリー状に接続された構造を有している。
【００３１】
図３に示すように、このツリーの初段を構成する各桁の桁上げ保存加算器Ｍ（０，０）〜Ｍ（Ｌ，０）には、部分積Ｐ（０）〜Ｐ（Ｋ−１）の各桁の信号が入力される。
桁上げ保存加算器Ｍ（０，０）〜Ｍ（Ｌ，０）に対する入力信号数は、加算回路の各桁への入力信号数Ｉ（０，０）〜Ｉ（Ｌ，０）として、入力信号数算出部２０により既に算出されている。回路構成決定部３０は、この算出された入力信号数Ｉ（０，０）〜Ｉ（Ｌ，０）に応じて、桁上げ保存加算器Ｍ（０，０）〜Ｍ（Ｌ，０）の回路構成を決定する。初段に続く各段の桁上げ保存加算器の回路構成については、前段の桁上げ保存加算器から入力される信号数に応じて順に決定する。
【００３２】
図４に示すように、ツリーの初段を除く各段に含まれる桁上げ保存加算器Ｍ（ｍ，ｎ）には、前段の同位桁の桁上げ保存加算器Ｍ（ｍ，ｎ−１）から出力される信号数Ｓ（ｍ，ｎ−１）の和信号と、前段の下位桁の桁上げ保存加算器Ｍ（ｍ−１，ｎ−１）から出力される信号数Ｃ（ｍ−１，ｎ−１）の桁上げ信号とが入力されている。桁上げ保存加算器Ｍ（ｍ，ｎ）への入力信号の総数Ｉ（ｍ，ｎ）は、和信号の信号数Ｓ（ｍ，ｎ−１）と桁上げ信号の信号数Ｃ（ｍ−１，ｎ−１）との和になり、次式が成立する。
【００３３】
【数３】
Ｉ（ｍ，ｎ）　＝　Ｓ（ｍ，（ｎ−１））　＋　Ｃ（（ｍ−１），（ｎ−１））　…　（３）
【００３４】
ただし、式（３）において整数ｎが‘０’の場合、すなわちツリーの初段を構成する桁上げ保存加算器Ｍ（０，０）〜Ｍ（Ｌ，０）に対する入力信号数Ｉ（０，０）〜Ｉ（Ｌ，０）は、入力信号数算出部２０において既に算出されたものと等しい。
また、式（３）において整数ｍが‘０’の場合、すなわちツリーの最下位桁の桁上げ保存加算器の場合、さらにその下位桁からの桁上げ信号は存在しないので、入力信号数Ｉ（ｍ，ｎ）は上段から出力される和信号の信号数Ｓ（ｍ，（ｎ−１））と等しくなる。
【００３５】
すなわち、回路構成決定部３０は、式（２）に示す入力信号の総和に応じて、それぞれの桁上げ保存加算器の回路構成を決定する。
【００３６】
（回路情報生成部４０）
回路情報生成部４０は、回路構成決定部３０において決定されたそれぞれの桁上げ保存加算器の回路構成に基づいて、加算回路の回路構成の情報を生成する。たとえば、決定された桁上げ保存加算器の回路構成に基づいて、ネット・リストやハードウェア記述言語など、所定の記述様式による加算回路の回路記述を生成する。
（情報表示部５０）
情報表示部５０は、回路情報生成部４０において生成された加算回路の回路構成の情報を表示する。たとえば液晶ディスプレイやスピーカなど、回路構成の情報を表示することが可能な種々の装置によって構成される。
【００３７】
ここで、上述した構成を有する加算回路の設計装置の動作について説明する。図５は、図１に示した加算回路の設計装置の動作例を示すフローチャートである。
【００３８】
（ステップＳＴ１０）
情報入力部１０において、部分積Ｐ（０）〜Ｐ（Ｋ−１）のビット幅Ｗ（０）〜Ｗ（Ｋ−１）とシフト数Ｆ（０）〜Ｆ（Ｋ−１）とが入力される。この入力された情報によって、たとえば図２に示すような、部分積の全体構造が決定される。
【００３９】
（ステップＳＴ２０）
情報入力部１０において入力されたビット幅Ｗ（０）〜Ｗ（Ｋ−１）とシフト数Ｆ（０）〜Ｆ（Ｋ−１）とに基づいて、設計対象の加算回路における各桁の入力信号数Ｉ（０，０）〜Ｉ（Ｌ，０）が入力信号数算出部２０により算出される。
【００４０】
ステップＳＴ２０における入力信号数算出処理の更に詳細な処理フローの一例について、図６のフローチャートを参照しながら説明する。
【００４１】
ステップＳＴ２０１：
各部分積に対応する整数の変数ｐが‘０’に初期化される。
ステップＳＴ２０２：
部分積の各ビットに対応する整数の変数ｑが‘０’に初期化される。また、入力信号数Ｉ（ｐ，０）も‘０’に初期化される。
【００４２】
ステップＳＴ２０３：
関数Ｄ（ｑ，ｐ−Ｆ（ｑ））の値が求められる。すなわち、情報入力部１０において入力されたビット幅およびシフト数の情報によって決定される部分積の全体構造において、部分積Ｐ（ｑ）の信号Ａ（ｑ，ｐ−Ｆ（ｑ））が定義されているか否かが調べられ、定義されている場合に関数Ｄ（ｑ，ｐ−Ｆ（ｑ））は‘１’となり、定義されていない場合に関数Ｄ（ｑ，ｐ−Ｆ（ｑ））は‘０’となる。
この求められた関数Ｄ（ｑ，ｐ−Ｆ（ｑ））の値は、入力信号数Ｉ（ｐ，０）に加算される。
【００４３】
ステップＳＴ２０４：
変数ｑが、部分積の数を示す値Ｋに対して、条件式ｑ＝Ｋ−１を満たすか否か判定される。すなわち、全ての部分積に対応する関数Ｄの値が入力信号数Ｉ（ｐ，０）に加算されたか否かが判定される。変数ｑがこの条件式を満たす場合にはステップＳＴ２０５へ、この条件式を満たさない場合にはステップＳＴ２０６へ処理が移行される。
【００４４】
ステップＳＴ２０５：
変数ｑが条件式ｑ＝Ｋ−１を満たさない場合、すなわち、全ての部分積に対応する関数Ｄの値が入力信号数Ｉ（ｐ，０）に加算されていない場合は、変数ｑの値が‘１’だけインクリメントされ、再びステップＳＴ２０３およびステップＳＴ２０４の処理が反復される。
【００４５】
ステップＳＴ２０６：
変数ｑの値が条件式ｑ＝Ｋ−１を満たす場合、ステップＳＴ２０６において、変数ｐが最大値Ｌと等しくなるか否かが判定される。
変数ｐが最大値Ｌに達していない場合は、ステップＳＴ２０７へ処理が移行され、変数ｐの値が‘１’だけインクリメントされる。その後、ステップＳＴ２０２〜ステップＳＴ２０４の処理が再び反復される。変数ｐが最大値Ｌに達している場合は、ステップＳＴ２０の処理が終了される。
以上が、ステップＳＴ２０の説明である。
【００４６】
（ステップＳＴ３０）
ステップＳＴ２０において算出された各桁の入力信号数Ｉ（ｋ，０）を用いて、計算対象の加算回路に含まれる複数の桁上げ保存加算器の回路構成が回路構成決定部３０によりそれぞれ決定される。
【００４７】
ステップＳＴ３０における回路構成決定処理の更に詳細な処理フローの一例について、図７のフローチャートを参照しながら説明する。
【００４８】
ステップＳＴ３０１：
図３に示すような加算回路のツリー構造の各桁に対応する変数ｍが‘０’に初期化される。
ステップＳＴ３０２：
図３に示すような加算回路のツリー構造の各段に対応する変数ｎが‘０’に初期化される。
【００４９】
ステップＳＴ３０３：
桁上げ保存加算器Ｍ（ｍ，ｎ）の回路構成が、その入力信号数Ｉ（ｍ，ｎ）に応じて決定される。また、これに応じて、桁上げ保存加算器Ｍ（ｍ，ｎ）から出力される和信号の信号数Ｓ（ｍ，ｎ）および桁上げ信号の信号数Ｃ（ｍ，ｎ）が決定される。
【００５０】
桁上げ保存加算器Ｍ（ｍ，ｎ）の回路構成は、入力信号数Ｉ（ｍ，ｎ）が１より大きい場合において、全加算器、半加算器、または信号出力回路のうちの少なくとも１つを、入力信号Ｉ（ｍ，ｎ）に応じた数だけ含むように決定される。ただし、全加算器は、３つの入力信号を加算して１つの和信号および１つの桁上げ信号を出力する回路である。半加算器は、２つの入力信号を加算して１つの和信号および１つの桁上げ信号を出力する回路である。信号出力回路は、１つの入力信号を１つの和信号として出力する回路である。
【００５１】
たとえば、次に述べる５つの場合分け（ａ）〜（ｅ）に応じて、桁上げ保存加算器Ｍ（ｍ，ｎ）の回路構成が決定される。
【００５２】
（ａ）入力信号数Ｉ（ｍ，ｎ）が‘０’の場合。
この場合、桁上げ保存加算器Ｍ（ｍ，ｎ）は内部に回路を有さない。したがって、和信号の出力信号数Ｓ（ｍ，ｎ）および桁上げ信号の出力信号数Ｃ（ｍ，ｎ）は何れも‘０’に決定される。
【００５３】
（ｂ）入力信号数Ｉ（ｍ，ｎ）が‘１’の場合。
この場合は、１つの信号出力回路を含むように回路構成が決定される。たとえば、図８に示すように、入力信号の入力端子と和信号の出力端子とを接続する配線Ｌ１によって、桁上げ保存加算器Ｍ（ｍ，ｎ）が構成される。
この回路構成から、和信号の出力信号数Ｓ（ｍ，ｎ）は‘１’、桁上げ信号の出力信号数Ｃ（ｍ，ｎ）は‘０’に決定される。
【００５４】
（ｃ）入力信号数Ｉ（ｍ，ｎ）が‘２’であり、かつ、条件式ｙ≧ｎを満たす整数ｙについて桁上げ信号の信号数Ｃ（ｍ−１，ｙ）が‘０’となる場合。
２つの条件のうち後半の条件は、桁上げ保存加算器Ｍ（ｍ，ｎ）より後段の同位桁の桁上げ保存加算器（Ｍ（ｍ，ｎ＋１），Ｍ（ｍ，ｎ＋２），…）に対して、下位桁からの桁上げ信号が生じなくなることを示している。この場合、桁上げ保存加算器Ｍ（ｍ，ｎ）の回路構成は、信号出力回路を２つ含んだ回路構成に決定される。たとえば、図９に示すように、２つの入力信号の入力端子と２つの和信号の出力端子とを接続する２本の配線Ｌ２およびＬ３によって桁上げ保存加算器Ｍ（ｍ，ｎ）が構成される。
この回路構成から、和信号の出力信号数Ｓ（ｍ，ｎ）は‘２’、桁上げ信号の出力信号数Ｃ（ｍ，ｎ）は‘０’に決定される。
【００５５】
（ｄ）入力信号数Ｉ（ｍ，ｎ）が‘３’であり、かつ、条件式ｙ≧ｎを満たす整数ｙについて桁上げ信号の信号数Ｃ（ｍ−１，ｙ）が‘０’となる場合。
（ｃ）の場合と同様に、２つの条件のうち後半の条件は、桁上げ保存加算器Ｍ（ｍ，ｎ）より後段の同位桁の桁上げ保存加算器に対して、下位桁からの桁上げ信号が生じなくなることを示している。この場合、桁上げ保存加算器Ｍ（ｍ，ｎ）の回路構成は、半加算器および信号出力回路を１つずつ含んだ回路構成に決定される。たとえば、図１０に示すように、１つの半加算器ＨＡ１と１つの配線Ｌ４とによって桁上げ保存加算器Ｍ（ｍ，ｎ）が構成される。
この回路構成から、和信号の出力信号数Ｓ（ｍ，ｎ）は‘２’、桁上げ信号の出力信号数Ｃ（ｍ，ｎ）は‘１’に決定される。
【００５６】
（ｅ）（ａ）〜（ｄ）の何れにも当てはまらない場合。
この場合、桁上げ保存加算器Ｍ（ｍ，ｎ）に含まれる全加算器の数Ｒ１は、入力信号数（ｍ，ｎ）を‘３’で除した商と等しくなるように決定される。
【００５７】
入力信号数（ｍ，ｎ）を‘３’で除した余りが‘０’の場合、桁上げ保存加算器Ｍ（ｍ，ｎ）の回路構成は、たとえば図１１に示すように、１つまたは複数の全加算器ＦＡ１〜ＦＡ５を含んだ回路構成に決定され、これに半加算器および信号出力回路は含まれない。
この回路構成から、和信号の出力信号数Ｓ（ｍ，ｎ）および桁上げ信号の出力信号数Ｃ（ｍ，ｎ）は、全加算器の数Ｒ１と等しい数に決定される。
【００５８】
入力信号数（ｍ，ｎ）を‘３’で除した余りが‘２’の場合、桁上げ保存加算器Ｍ（ｍ，ｎ）の回路構成は、たとえば図１２に示すように、１つまたは複数の全加算器ＦＡ６〜ＦＡ９と１つの半加算器ＨＡ２とを含んだ回路構成に決定される。
この回路構成から、和信号の出力信号数Ｓ（ｍ，ｎ）および桁上げ信号の出力信号数Ｃ（ｍ，ｎ）は、全加算器の数Ｒ１と半加算器の数Ｒ２との和と等しい数に決定される。
【００５９】
入力信号数（ｍ，ｎ）を‘３’で除した余りが‘１’の場合、桁上げ保存加算器Ｍ（ｍ，ｎ）の回路構成は、たとえば図１３に示すように、１つまたは複数の全加算器ＦＡ１０〜ＦＡ１３と、信号出力回路としての１つの配線Ｌ５とを含んだ回路構成に決定される。
この回路構成から、和信号の出力信号数Ｓ（ｍ，ｎ）は、全加算器の数Ｒ１と信号出力回路の数Ｒ３との和と等しい数に決定される。桁上げ信号の出力信号数Ｃ（ｍ，ｎ）は、全加算器の数Ｒ１と等しい数に決定される。
【００６０】
すなわち、この５つの場合わけ（ａ）〜（ｅ）によって、全加算器の数Ｒ１、半加算器の数Ｒ２、信号出力回路の数Ｒ３、和信号の出力信号数Ｓ（ｍ，ｎ）、および桁上げ信号の出力信号数Ｃ（ｍ，ｎ）は、それぞれ次式のように表される。
【００６１】
【数４】
Ｒ１　＝　Ｉ（ｍ，ｎ）　ｄｉｖ　３　　　　　…　（４）
Ｒ２　＝　（Ｉ（ｍ，ｎ）　ｍｏｄ　３）　ｄｉｖ　２　…　（５）
Ｒ３　＝　（Ｉ（ｍ，ｎ）　ｍｏｄ　３）　ｍｏｄ　２　…　（６）
Ｓ（ｍ，ｎ）　＝　Ｒ１　＋　Ｒ２　＋　Ｒ３　　　…　（７）
Ｃ（ｍ，ｎ）　＝　Ｒ１　＋　Ｒ２　　　　　…　（８）
【００６２】
ただし、式（４）〜（８）において、演算記号ｄｉｖは整数の除算を示し、演算記号ｍｏｄは剰余算を示す。
【００６３】
ステップＳＴ３０４：
和信号の出力信号数Ｓ（ｍ，ｎ）が２と等しいか２より少なく、かつ、条件式ｙ≧ｎを満たす整数ｙについて桁上げ信号の信号数Ｃ（ｍ−１，ｙ）が‘０’となるか否か判定される。
２つの条件のうち後半の条件は、同位桁の後段に続く桁上げ保存加算器に対して下位桁からの上記桁上げ信号が生じなくなることを示している。２つの条件が満たされると、この桁における信号数が最終的に２まで削減されたことになるため、この段より後段の桁上げ保存加算器は、図８および図９に示すように、入力信号をそのまま出力信号として出力する回路になる。
この２つの条件の一方または両方を満たさないと判定された場合にはステップＳＴ３０５へ、両方ともに満たすと判定された場合にはステップＳＴ３０６へ処理が移行される。
【００６４】
ステップＳＴ３０５：
変数ｎの値が‘１’だけインクリメントされ、ステップＳＴ３０３およびＳＴ３０４の処理が反復される。
【００６５】
ステップＳＴ３０６：
条件式ｘ≧ｍ＋１を満たす整数ｘについて入力信号数Ｉ（ｘ，０）が全て‘０’になり、かつ、条件式ｚ≧０を満たす整数ｚについて桁上げ信号の信号数Ｃ（ｍ，ｚ）が‘０’となるか否か判定される。
２つの条件のうち前半の条件は、次回以降に回路構成の決定処理を行う桁の初段の入力信号数が全てゼロになる場合を示す。これは、変数（ｍ＋１）に対応する桁が、加算回路に入力される信号の最上位桁より大きくなる場合に相当する。たとえば図３に示すツリー構造において、内部回路が存在しない桁上げ保存加算器Ｍ（Ｌ＋１，０），Ｍ（Ｌ＋２，０），…への入力信号数Ｉ（Ｌ＋１，０），Ｉ（Ｌ＋２，０），…が全て‘０’になることに相当する。
２つの条件のうち後半の条件は、変数ｍに対応する桁から上位桁への桁上げ信号の信号数が全てゼロになることを示す。
２つの条件を両方満たす場合、変数ｍに対応する桁より上位の桁の桁上げ保存加算回路に対する入力信号数は全てゼロになる。
この２つの条件の一方または両方が満たされていないと判定された場合にはステップＳＴ３０７へ処理が移行され、両方とも満たすと判定された場合にはステップＳＴ３０の処理が終了される。
以上がステップＳＴ３０の説明である。
【００６６】
（ステップＳＴ４０）
回路構成決定部３０において決定されたそれぞれの桁上げ保存加算器の回路構成に基づいて、加算回路の回路構成の情報が回路情報生成部４０により生成される。たとえば、ネット・リストやハードウェア記述言語など、所定の記述様式による加算回路の回路記述が生成される。
生成された加算回路の回路構成は、たとえば液晶ディスプレイなどによって構成される情報表示部５０により表示される。
【００６７】
以上説明したように、図１に示す加算回路の設計装置によれば、部分積のビット幅の情報と、この部分積が加算に際して最下位桁より上位桁に向かってシフトされるシフト数の情報とに基づいて、設計対象とする加算回路の各桁の入力信号数が算出される。ツリーの初段を構成する各桁の桁上げ保存加算器の回路構成は、この算出された各桁の入力信号数に応じて決定され、初段に続く各段の桁上げ保存加算器の回路構成は、前段の桁上げ保存加算器から入力される信号数に応じて順に決定される。したがって、たとえばウォレスツリー回路のように、複数の桁上げ保存加算器がツリー状に接続された加算回路の回路構成を、各部分積のビット幅とシフト数とによって決まる部分積の全体構造に対応して一意に決定することができる。
【００６８】
一般的な複合演算器に用いられるウォレスツリー回路のように、不規則な構造の部分積を処理する加算回路は、その形式化された構成方法が確立されていなかったことから、熟練者の経験を頼りに人手によって設計されていたが、上述した設計装置を用いれば、どのように複雑な構造の部分積を処理する加算回路でも、明確に形式化された方法によって自動的に設計することが可能になる。したがって、形式化された設計手法を用いない従来の方法に比べて回路の設計が容易になり、設計時間を短縮することができる。このような加算回路を有する乗算器、積和演算器、複合演算器など回路の設計時間の短縮にも貢献する。
【００６９】
部分積の全体構造に対応して加算回路の回路構成が一意に決定できることから、演算器の仕様に変更が生じた場合でも、その変更に対して迅速かつ柔軟に対応することができる。
【００７０】
また、図１に示す加算回路の設計装置によれば、入力信号数Ｉ（ｍ，ｎ）が１より大きい場合において、全加算器、半加算器、または信号出力回路のうちの少なくとも１つを入力信号Ｉ（ｍ，ｎ）に応じた数だけ含むように、桁上げ保存加算器Ｍ（ｍ，ｎ）の回路構成が決定される。桁上げ保存加算器に含まれる全加算器、半加算器および信号出力回路の数Ｒ１〜Ｒ３、和信号の出力信号数Ｓ（ｍ，ｎ）、および桁上げ信号の出力信号数Ｃ（ｍ，ｎ）は、上述した５つの場合わけ（ａ）〜（ｅ）に応じて適切に決定される。これにより、加算回路から出力される部分積の各桁の信号数を２または２より小さくすることができるので、出力における部分積の数を確実に２つ以下まで削減することができる。
【００７１】
（ａ）の場合、桁上げ保存加算器が作られないことから、無駄な回路が省略される。
（ｂ）の場合、たとえば１本の配線だけを有する単純な信号出力回路によって桁上げ保存加算器が構成されることから、回路が簡易化される。
（ｃ）および（ｄ）の場合、たとえば１本の配線だけを有する単純な信号出力回路によって後段に続く桁上げ保存加算器が構成されることから、回路が簡易化される。
（ｅ）の場合、１つまたは複数の全加算器と、必要に応じて１つの半加算器または１つの信号出力回路とによって桁上げ保存加算器が構成されることから、入力信号数Ｉ（ｍ，ｎ）に対して和信号の出力信号数Ｓ（ｍ，ｎ）を確実に少なくすることができる。
このように、５つの場合わけ（ａ）〜（ｅ）に応じて桁上げ保存加算器が構成されることにより、回路の構成が簡易化され、回路の小面積化を図ることができ、また、回路の低電力化を実現することができる。
【００７２】
図１に示す設計装置において設計できる加算回路は、入力信号を加算して和信号および桁上げ信号を出力する複数の桁上げ保存加算器を有し、この複数の桁上げ保存加算器がツリー状に接続されるた構造を有している。
複数の部分積の各桁の信号は、ツリーの初段を構成する各桁の桁上げ保存加算器に入力される。ツリーの初段を除く各段に含まれる桁上げ保存加算器には、前段の同位桁の桁上げ保存加算器から出力される和信号と、前段の下位桁の桁上げ保存加算器から出力される桁上げ信号とが入力される。
それぞれの桁上げ保存加算器は、全加算器、半加算器、または信号出力回路のうちの少なくとも１つを、入力信号数に応じた数だけ含む。
すなわち、それぞれの桁上げ保存加算器は、入力信号数を３で除した商に応じた数の全加算器を含む。入力信号数を３で除した余りが２の場合、半加算器を１つ含む。入力信号数を３で除した余りが１の場合、上記信号出力回路を１つ含む。入力信号数が３であり、かつ、自らより後段の同位桁の桁上げ保存加算器に対して下位桁からの上記桁上げ信号が入力されない場合は、半加算器および信号出力回路を１つずつ含む。入力信号数が２であり、かつ、自らより後段の同位桁の桁上げ保存加算器に対して下位桁からの上記桁上げ信号が入力されない場合は、信号出力回路を２つ含む。
したがって、図１に示す設計装置において設計できる加算回路は、形式化された設計手順に基づいて複数の桁上げ保存加算器が規則的にツリー状に接続されており、人手によって設計されるウォレスツリー回路の生じ易い不規則性が排除されるので、設計された回路の解析や回路動作の予測が容易になる。また、各桁の加算を並列的に行なうことができ、加算処理の高速化を図ることができる。たとえば、この加算回路を複合演算器に適用することにより、回路の小面積化と高速化を図ることができる。
【００７３】
本発明は上述した実施形態に限定されない。
上述した構成の少なくとも一部、たとえば入力信号数算出部２０、回路構成決定部３０および回路情報生成部４０を、プログラムに応じて処理を実行する１つまたは複数のコンピュータ等の処理装置によって実現しても良い。この場合のプログラムは、たとえば図５〜図７に示すようなステップを含む処理フローによって実現することができる。また、このプログラムは、たとえばハードディスクなどの記憶装置や、光磁気ディスクなどの記録媒体を介して処理装置に供給しても良いし、ネットワークを介して伝送されるプログラムを処理装置に供給しても良い。
【００７４】
図７に示すフローチャートでは、段方向の回路構成決定処理（ステップＳＴ３０２〜ステップＳＴ３０５）を、桁方向の回路構成決定処理（ステップＳＴ３０２、ＳＴ３０６およびＳＴ３０７）において最下位桁から上位桁に向かって順に反復実行させている。本発明はこの例に限定されず、たとえば、桁方向の回路構成決定処理を、段方向の回路構成決定処理において初段から後段に向かって順に反復実行させても良い。
すなわち、桁方向の回路構成決定処理では、入力信号数がゼロになる桁の下位桁まで、ツリーの最下位桁から上位桁に向かって順に回路構成の決定を行なう。この桁方向の回路構成決定処理を、全ての桁上げ保存加算器の入力信号数が２と等しいか２より少なくなる段まで、ツリーの初段から後段に向かって順に実行する。
このような処理フローでも、上述と同様の効果を奏することができる。
【００７５】
回路情報生成部４０において生成された回路構成の情報は、図１に示すように情報表示部５０において表示させても良いが、この他に、たとえば適当なインターフェース装置を介して、ハードディスクなどの記憶装置や光磁気ディスクなどの記録媒体に記憶させても良いし、ネットワークへ送出しても良い。
【００７６】
【発明の効果】
本発明によれば、第１に、複数の桁上げ保存加算器がツリー状に接続された加算回路の設計を自動化する設計装置を提供することができる。
第２に、複数の桁上げ保存加算器がツリー状に接続された加算回路の設計方法を提供することができる。
第３に、複数の桁上げ保存加算器がツリー状に接続された加算回路の設計を自動化する加算回路の設計装置のプログラムを提供することができる。
第４に、複数の桁上げ保存加算器が規則的にツリー状に接続され、各桁の加算を並列的に行なう加算回路を提供することができる。
【図面の簡単な説明】
【図１】図１は、本発明の実施形態に係る加算回路の設計装置の構成の一例を示すブロック図である。
【図２】設計対象の加算回路において加算される部分積の全体構造の一例を図解した図である。
【図３】設計対象の加算回路の構成の一例を示すブロック図である。
【図４】図３に示す加算回路の一部を抜き出して示したブロック図である。
【図５】図１に示した加算回路の設計装置の動作例を示すフローチャートである。
【図６】図５のフローチャートにおける入力信号数算出処理の更に詳細な処理フローの一例を示すフローチャートである。
【図７】図５のフローチャートにおける回路構成決定処理の更に詳細な処理フローの一例を示すフローチャートである。
【図８】回路構成決定部において決定される桁上げ保存加算器の回路構成を示す第１の図である。
【図９】回路構成決定部において決定される桁上げ保存加算器の回路構成を示す第２の図である。
【図１０】回路構成決定部において決定される桁上げ保存加算器の回路構成を示す第３の図である。
【図１１】回路構成決定部において決定される桁上げ保存加算器の回路構成を示す第４の図である。
【図１２】回路構成決定部において決定される桁上げ保存加算器の回路構成を示す第５の図である。
【図１３】回路構成決定部において決定される桁上げ保存加算器の回路構成を示す第６の図である。
【符号の説明】
１０…情報入力部、２０…入力信号数算出部、３０…回路構成決定部、４０…回路情報生成部、５０…情報表示部、Ｌ１〜Ｌ５…配線、ＨＡ１，ＨＡ２…半加算器、ＦＡ１〜ＦＡ１３…全加算器
【図１】
2004133861.tif 000003
【図２】
2004133861.tif 000004
【図３】
2004133861.tif 000005
【図４】
2004133861.tif 000006
【図５】
2004133861.tif 000007
【図６】
2004133861.tif 000008
【図７】
2004133861.tif 000009
【図８】
2004133861.tif 000010
【図９】
2004133861.tif 000011
【図１０】
2004133861.tif 000012
【図１１】
2004133861.tif 000013
【図１２】
2004133861.tif 000014
【図１３】
2004133861.tif 000015