(57)【要約】【課題】  冗長数系に基づく加算回路を計算機により自動合成することが可能な加算回路合成装置を提供する。【解決手段】  加算回路合成装置１０は、ＣＴＤ生成部１２、ＣＴＤ分解部１４、符号化部１６、及び回路変換部１８を備える。ＣＴＤ生成部１２は、冗長加算アルゴリズムに関して入力される入力変数及び出力変数を割り当てたＣＴＤを生成する。ＣＴＤ分解部１４は、ＣＴＤ生成部１２によって生成れたＣＴＤを分解し、未知パラメータの導出を行う。符号化部１６は、ＣＴＤ分解部１４によって生成されたＣＴＤのパラメータを符号化する。回路変換部１８は、符号化部１６によって得られた符合に基づく論理関数を回路に変換する。【選択図】  図１
2005250704.tif 000002
【特許請求の範囲】
【請求項１】
冗長数系に基づく加算回路合成装置であって、
wを重み、a及びｂをそれぞれ区間の下限のパラメータ、上限のパラメータとする重み付き区間を下式（１）、重み付き区間の加算を下式（２）とした場合に、
【数１】
2005250704.tif 000014
【数２】
2005250704.tif 000015
入力変数ｘｉ、出力変数yiとし、下式（３）及び（４）を満たすように入力変数を出力変数に変換するカウンタノードと、
【数３】
2005250704.tif 000016
【数４】
2005250704.tif 000017
（１）式で定義される重み付き区間を定義域としてもつ有向辺との集合によって構成されるＣＴＤ（Ｃｏｕｎｔｅｒ  Ｔｒｅｅ  Ｄｉａｇｒａｍ）の入力の有向辺及び出力の有向辺に、冗長加算アルゴリズムに関するパラメータとして入力される入力変数の定義域及び出力変数の定義域をそれぞれ割り当てるＣＴＤ生成手段と、
下式（５）で定義されるｎ（ｎ＞１）本の有向辺の有向辺の分解、
【数５】
2005250704.tif 000018
及び下式（６）及び（７）で定義されるカウンタノードの分解
【数６】
2005250704.tif 000019
【数７】
2005250704.tif 000020
によって、前段から次段への有向辺のパラメータ[ei,fi]、及び桁上げ伝播に関するパラメータ[ci,di]を式（４）及び下式（８）
【数８】
2005250704.tif 000021
の条件に基づいて演算し、前記ＣＴＤ生成手段によって生成されたＣＴＤを所望の段数のＣＴＤに分解するＣＴＤ分解手段と、
前記ＣＴＤ分解手段によって分解されたＣＴＤの前記パラメータに符号を割り当てる符号化手段と、
前記符号化手段によって割り当てられた符号に基づく論理関数を回路に変換する回路変換手段と、
を備える、加算回路合成装置。
【請求項２】
前記符号化手段は、前記変数を表現可能な最小限数のビットを用いて前記符号を割り当てる、請求項１に記載の加算回路合成装置。
【請求項３】
冗長数系に基づく加算回路を合成するための加算回路合成方法であって、
wを重み、a及びｂをそれぞれ区間の下限のパラメータ、上限のパラメータとする重み付き区間を下式（１）、重み付き区間の加算を下式（２）とした場合に、
【数９】
2005250704.tif 000022
【数１０】
2005250704.tif 000023
入力変数ｘｉ、出力変数yiとし、下式（３）及び（４）を満たすように入力変数を出力変数に変換するカウンタノードと、
【数１１】
2005250704.tif 000024
【数１２】
2005250704.tif 000025
（１）式で定義される重み付き区間を定義域としてもつ有向辺との集合によって構成されるＣＴＤ（Ｃｏｕｎｔｅｒ  Ｔｒｅｅ  Ｄｉａｇｒａｍ）の入力の有向辺及び出力の有向辺に、冗長加算アルゴリズムに関するパラメータとして入力される入力変数の定義域及び出力変数の定義域をそれぞれ割り当てるＣＴＤ生成ステップと、
下式（５）で定義されるｎ（ｎ＞１）本の有向辺の有向辺の分解、
【数１３】
2005250704.tif 000026
及び下式（６）及び（７）で定義されるカウンタノードの分解
【数１４】
2005250704.tif 000027
【数１５】
2005250704.tif 000028
によって、前段から次段への有向辺のパラメータ[ei,fi]、及び桁上げ伝播に関するパラメータ[ci,di]を式（４）及び下式（８）
【数１６】
2005250704.tif 000029
の条件に基づいて演算し、前記ＣＴＤ生成ステップにおいて生成されたＣＴＤを所望の段数のＣＴＤに分解するＣＴＤ分解ステップと、
前記ＣＴＤ分解ステップにおいて分解されたＣＴＤの前記パラメータに符号を割り当てる符号化ステップと、
前記符号化ステップにおいて割り当てられた符号に基づく論理関数を回路に変換する回路変換ステップと、
を含む、加算回路合成方法。
【請求項４】
前記符号化ステップにおいて、前記パラメータを表現可能な最小限数のビットを用いて前記符号を割り当てる、請求項３に記載の加算回路合成方法。
【請求項５】
冗長数系に基づく加算回路をコンピュータに合成させるための加算回路合成プログラムであって、
コンピュータを、
wを重み、a及びｂをそれぞれ区間の下限のパラメータ、上限のパラメータとする重み付き区間を下式（１）、重み付き区間の加算を下式（２）とした場合に、
【数１７】
2005250704.tif 000030
【数１８】
2005250704.tif 000031
入力変数ｘｉ、出力変数yiとし、下式（３）及び（４）を満たすように入力変数を出力変数に変換するカウンタノードと、
【数１９】
2005250704.tif 000032
【数２０】
2005250704.tif 000033
（１）式で定義される重み付き区間を定義域としてもつ有向辺との集合によって構成されるＣＴＤ（Ｃｏｕｎｔｅｒ  Ｔｒｅｅ  Ｄｉａｇｒａｍ）の入力の有向辺及び出力の有向辺に、冗長加算アルゴリズムに関するパラメータとして入力される入力変数の定義域及び出力変数の定義域をそれぞれ割り当てるＣＴＤ生成手段と、
下式（５）で定義されるｎ（ｎ＞１）本の有向辺の有向辺の分解、
【数２１】
2005250704.tif 000034
及び下式（６）及び（７）で定義されるカウンタノードの分解
【数２２】
2005250704.tif 000035
【数２３】
2005250704.tif 000036
によって、前段から次段への有向辺のパラメータ[ei,fi]、及び桁上げ伝播に関するパラメータ[ci,di]を式（４）及び下式（８）
【数２４】
2005250704.tif 000037
の条件に基づいて演算し、前記ＣＴＤ生成手段によって生成されたＣＴＤを所望の段数のＣＴＤに分解するＣＴＤ分解手段と、
前記ＣＴＤ分解手段によって分解されたＣＴＤの前記パラメータに符号を割り当てる符号化手段と、
前記符号化手段によって割り当てられた符号に基づく論理関数を回路に変換する回路変換手段と、
として機能させる、加算回路合成プログラム。
【請求項６】
前記符号化手段は、前記パラメータを表現可能な最小限数のビットを用いて前記符号を割り当てる、請求項５に記載の加算回路合成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、加算回路合成装置、加算回路合成方法、及び加算回路合成プログラムに関するものである。
【背景技術】
【０００２】
近年、音声、画像、映像などのマルチメディア信号処理に要求される演算能力は増加の一途をたどっており、用途に応じた多種多様な演算回路(データパス)の設計技術が要求されている。また、従来の２進数系にとらわれず、冗長数系や多進数系などの特殊数系を積極的に活用した演算アルゴリズムの有効性が示されており、２進数ＶＬＳＩの性能限界が顕在化するにつれて、特殊数系の演算回路の必要性はますます高まっている（例えば、非特許文献１）
【非特許文献１】I.Koren, Computer arithmetic algorithms 2nd Edition, A K Peters 2001.
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、現在、計算機を用いた自動合成技術においては、論理ゲートレベルの合成が主流となっている。既存の合成技術は、ランダム・ロジックを合成の基本としているため、加算回路に代表される算術演算回路を合成することは困難である。このため、算術演算回路に関しては、あらかじめ専門家が考案した回路をライブラリとして用意する知識ベースの設計を行っているのが現状である。したがって、ライブラリに存在しない機能については回路生成が不可能である。特に、冗長数系に基づく加算回路は、その優れた性能にも関わらず、ほとんど利用されていないのが現状である。このような設計問題を本質的に解消するためには、算術演算のアルゴリズム自体を自動的に合成する手法の開発が必須である。
【０００４】
そこで、本発明は、上記問題点を解決するためになされたもので、冗長数系に基づく加算回路を計算機により自動合成することが可能な加算回路合成装置、加算回路合成方法、及び加算回路合成プログラムを提供することを目的としている。
【課題を解決するための手段】
【０００５】
本発明の加算回路合成装置は、冗長数系に基づく加算回路合成装置であって、ＣＴＤ生成手段と、ＣＴＤ分解手段と、符号化手段と、回路変換手段とを備える。ここで、ｗを重み、ａ及びｂをそれぞれ、区間の下限のパラメータ、上限のパラメータとする重み付き区間を式（１）、
【数１】
2005250704.tif 000003
重み付き区間の加算を下式（２）
【数２】
2005250704.tif 000004
とした場合に、入力変数ｘｉ、出力変数ｙｉとし、下式（３）及び（４）
【数３】
2005250704.tif 000005
【数４】
2005250704.tif 000006
を満たすように入力変数を出力変数に変換するカウンタノードと、（１）式で定義される重み付き区間を定義域としてもつ有向辺との集合によって、冗長加算アルゴリズムを表現するためのＣＴＤ（Counter Tree Diagram）を構成することができる。ＣＴＤ生成手段は、入力の有向辺及び出力の有向辺に、冗長加算アルゴリズムに関するパラメータとして入力される入力変数の定義域及び出力変数の定義域をそれぞれ割り当てる。また、ＣＴＤにおいては、有向辺を下式（５）で定義されるように、ｎ（ｎ＞１）本の有向辺に分解することができ、
【数５】
2005250704.tif 000007
カウンタノードを、下式（６）及び（７）で定義されるように、多段に分解することができる。
【数６】
2005250704.tif 000008
【数７】
2005250704.tif 000009
ＣＴＤ分解手段は、前段から次段への有向辺のパラメータ［ｅｉ，ｆｉ］、及び桁上げ伝播に関するパラメータ［ｃｉ，ｄｉ］を式（４）及び下式（８）
【数８】
2005250704.tif 000010
の条件に基づいて演算し、ＣＴＤ生成手段によって生成されたＣＴＤを所望の段数のＣＴＤに分解する。符号化手段は、ＣＴＤ分解手段によって分解されたＣＴＤの前記パラメータに符号を割り当てる。回路変換手段は、符号化手段によって割り当てられた符号に基づく論理関数を回路に変換する。
【０００６】
また、本発明の加算回路合成方法は、冗長数系に基づく加算回路を合成するための加算回路合成方法であって、ＣＴＤ生成ステップと、ＣＴＤ分解ステップと、符号化ステップと、回路変換ステップと、を含む。ＣＴＤ生成ステップにおいては、上記のように定義されるＣＴＤの入力の有向辺及び出力の有向辺に、冗長加算アルゴリズムに関するパラメータとして入力される入力変数の定義域及び出力変数の定義域をそれぞれ割り当てる。ＣＴＤ分解ステップにおいては、式（５）、式（６）及び式（７）によって定義されるＣＴＤの分解操作を用いてＣＴＤを所望の段数のＣＴＤに分解する。ＣＴＤ分解ステップにおいては、前段から次段への有向辺のパラメータ［ｅｉ，ｆｉ］、及び桁上げ伝播に関するパラメータ［ｃｉ，ｄｉ］を式（４）及び式（８）の条件に基づいて演算する。符号化ステップにおいては、分解されたＣＴＤのパラメータに符号を割り当てる。回路変換ステップにおいては、符号化ステップにおいて割り当てられた符号に基づく論理関数を回路に変換する。
【０００７】
また、本発明の加算回路合成プログラムは、コンピュータを、上記のＣＴＤ生成手段、ＣＴＤ分解手段、符号化手段、及び回路変換手段として機能させる。
【０００８】
これらの本発明によれば、冗長加算アルゴリズムをＣＴＤによって表現することで、数系や演算アルゴリズムに関する専門的な知識を用いることなく、冗長加算回路が系統的に自動合成される。また、ＣＴＤ生成手段によって冗長加算アルゴリズムを抽象度の高いＣＴＤで表現した後、当該ＣＴＤを分解する処理を経て合成される冗長加算回路は、回路遅延、消費電力が少なくなっている。
【０００９】
また、上述した本発明においては、パラメータを表現可能な最小限数のビットを用いてＣＴＤのパラメータに符号を割り当てることが好ましい。
【００１０】
ＣＴＤのパラメータに符号を割り当てる符号化には無数の方法があるが、この発明によれば、最小限数のビットを用いて符号を割り当てるので、回路の配線数や素子数を削減することができる。
【発明の効果】
【００１１】
以上、説明したように、本発明によれば、数系や演算アルゴリズムに関する専門的な知識を用いることなく、冗長加算回路を系統的に自動合成することが可能な加算回路合成装置、加算回路合成方法、及び加算回路合成プログラムが提供される。また、本発明によって合成される冗長加算回路は、回路遅延、消費電力が少なくなっている。
【発明を実施するための最良の形態】
【００１２】
以下、図面を参照して本発明の好適な実施形態について詳細に説明する。なお、各図面において同一又は相当の部分に対しては同一の符号を附すこととする。
【００１３】
図１は、本発明の実施の形態にかかる加算回路合成装置の構成を概略的に示す図である。図１に示すように、本実施の形態にかかる加算回路合成装置１０は、ＣＴＤ生成部１２と、ＣＴＤ分解部１４と、符号化部１６と、回路変換部１８とを備えている。
【００１４】
ここで、ＣＴＤ（Ｃｏｕｎｔｅｒ  Ｔｒｅｅ  Ｄｉａｇｒａｍ）について説明する。図２は、ＣＴＤを説明するための図である。図２において、円記号はカウンタノードを表し、矢印付きの線は、有向辺を示している。
【００１５】
ＣＴＤは、ｗを重み、ａ及びｂをそれぞれ区間の下限のパラメータ、上限のパラメータとする重み付き区間を上述の（１）式、重み付き区間の加算を上述の（２）式と定義した場合に、入力変数ｘｉ、出力変数ｙｉとし、上述の（３）式及び（４）式を満たすように入力変数を出力変数に変換するカウンタノードと、（１）式で定義される重み付き区間を定義域としてもつ有向辺との集合によって構成される。
【００１６】
ここで、（３）式は、カウンタノードによる変数の総和が変化しないことを表している。（４）式は、任意の入力の組み合わせを出力側で表現できることを意味しており、カウンタノード条件と呼ばれる。
【００１７】
以上のように定義されたカウンタノードは、多進数系や冗長数系を含むあらゆる重み数系の加算を表現することができる。このようなＣＴＤは、カウンタノードのネットワークとして、加算アルゴリズムを様々な抽象度レベルで表現することができる。図２には、カウンタノードが一段のＣＴＤが示されており、当該ＣＴＤによって、高い抽象度で加算アルゴリズムを表現することができる。
【００１８】
また、ＣＴＤでは、カウンタノード及び有向辺を分解することができる。ＣＴＤにおいて有向辺の分解操作は、上述の（５）式を満足する有向辺の操作である。（５）式において、ｗ１［ａ１：ｂ１］，・・・，ｗｎ［ａｎ：ｂｎ］は、分解後の重み付き区間である。
【００１９】
図３（ａ）及び図３（ｂ）は、カウンタノードの分解操作を説明するための図であり、それぞれ、分解前のＣＴＤ、２段に分解されたＣＴＤを示している。カウンタノードの分解操作とは、図３（ａ）及び図３（ｂ）に示すように、カウンタノードを複数のカウンタノードに分解する操作であり、上述の（６）式及び（７）式を満たす操作である。
【００２０】
このようなＣＴＤの分解操作は、ＣＴＤが表現する加算機能を保存する等価変換操作である。ＣＴＤの分解操作によって、ＣＴＤを用いて高い抽象度で表現された冗長加算アルゴリズムを低い抽象度で表現することができる。なお、分解操作の可否は、上記（３）式によるカウンタノード条件を調べることによって判定することができる。
【００２１】
図１に戻り、加算回路合成装置１０を説明する。なお、以下においては、一桁の冗長加算器を例にとって説明を行う。図４（ａ）及び図４（ｂ）は、一桁の冗長加算器を異なる抽象度のＣＴＤによって表現した図であり、それぞれ、１桁の冗長加算器、（ｋ＋１）段分解された一桁の冗長加算器を示している。図４（ｂ）において、ｃｉ及びｄｉは、次段への桁上げ伝播を示す有向辺の定義域の下限パラメータ及び上限パラメータを示している。ｅｉ及びｆｉは、次段への出力を示す有向辺の定義粋の下限のパラメータ及び上限のパラメータを示している。
【００２２】
ＣＴＤ生成部１２は、入力される冗長加算アルゴリズムに関する入力変数及び出力変数それぞれについての定義域（下限パラメータ及び上限パラメータ）を、図４（ａ）に示すＣＴＤに割り当てる。
【００２３】
図５は、冗長２進加算器に入力変数及び出力変数を割り当てた場合のＣＴＤの一例を示す図である。以下、冗長２進加算器を例にとって説明すると、例えば、二つの入力変数の定義域として［−１：１］、出力変数の定義域として［−１：１］が入力された場合に、ＣＴＤ生成部１２は、図５に示すようにＣＴＤに、入力変数の定義域及び出力変数の定義域を設定する。
【００２４】
ＣＴＤ分解部１４は、上述したＣＴＤの分解操作によって、ＣＴＤを分解する。例えば、冗長加算アルゴリズムの場合には、図４（ａ）に示すＣＴＤを分解操作によって図４（ｂ）に示すＣＴＤとする。
【００２５】
ＣＴＤ分解部１４は、分解後のＣＴＤにおける未知パラメータであるｃｉ，ｄｉ，ｅｉ，ｆｉを決定する。ここで、実用的な並列加算器の場合に、上述した（８）式が成り立ち、ＣＴＤ分解部１４は、当該（８）式と（３）式を満たすようにｃｉ，ｄｉ，ｅｉ，ｆｉを決定する。
【００２６】
例えば、桁上げ伝搬がｋ（≧１）に制限されたＣＴＤの場合には、上記の連立不等式は、（９）式となる。
【数９】
2005250704.tif 000011
【００２７】
以下、一例として、桁上げ伝搬がｋ＝２に制限されている３段のＣＴＤを想定すると、（９）式は（１０）式の連立不等式になる。
【数１０】
2005250704.tif 000012
【００２８】
（１０）式における未知の整数パラメータ変数ｃｉ，ｄｉ，ｅｉ，ｆｉ（ｉ∈{１，２｝）は、（１１）式に示す必要条件から簡単に導出可能である。
【数１１】
2005250704.tif 000013
ここで、αｉ，βｉ（ｉ∈{１，２｝）は、αｉ＝ｄｉ−ｃｉ，βｉ＝ｅｉ−ｆｉである。
【００２９】
（１１）式の解としては、
Ｔｙｐｅ１：α１＝１，β１＝２，α２＝１，β２＝１
Ｔｙｐｅ２：α１＝２，β１＝１，α２＝１，β２＝１
の二通りの組み合わせが得られ、その結果、ＣＴＤ分解部１４は、図６（ａ）に示すＴｙｐｅ１の解に基づくＣＴＤ、及び図６（ｂ）に示すＴｙｐｅ２の解に基づくＣＴＤを得ることができる。
【００３０】
符号化部１６は、ＣＴＤ分解部１４によって分解されたＣＴＤのパラメータを符号化する。ＣＴＤにおけるパラメータの符号化には無数の符号化が存在するが、本実施形態の符号化部１６は、ＣＴＤのパラメータに、有向辺の定義域内の整数を最小限のビットで表現可能な符合を割り当てる。これによって、回路の配線数や素子数を削減することができる。
【００３１】
図７（ａ）、図７（ｂ）、図７（ｃ）、図７（ｄ）、図７（ｅ）は、図６（ａ）に示すＣＴＤのパラメータＸ，Ｙ，Ｚ，Ｕ，Ｖ，Ｃ１，Ｃ２それぞれへの符合の割り当てを示す表である。具体的に、符号化部１６は、図７（ａ）、図７（ｂ）、図７（ｃ）、図７（ｄ）、図７（ｅ）に示すように、パラメータＸ，Ｙ，Ｚ，Ｕ，Ｖ，Ｃ１，Ｃ２それぞれに、各々の定義域における整数を最小限のビットで表現するための符合を割り当てる。例えば、図７（ａ）に示すように、−１，０，１の３値をとるパラメータＸについては、ｘ１ｘ２の２ビットを用い、−１に対しては１０、０に対しては００、−１に対しては０１の符合を割り当てる。なお、符号化部１６は、例えば、定義域とその定義域における整数を表現するための符合値を割り当てるためのテーブルを記憶しておくことができ、ＣＴＤ分解部１４によって導出されたパラメータに基づいて当該テーブルを参照することによって、符合を割り当てることができる。
【００３２】
回路変換部１８は、符号化部１６によって得られた符合に基づいて論理関数を生成し、当該論理関数を回路に変換する。回路変換部１８は、例えば、上記の符合からＡＮＤ、ＯＲ等の論理関数を自動的に生成し、当該論理関数をＨＤＬ（Hardware Description Language)記述に変換する。回路変換部１８は、当該ＨＤＬ記述を回路に変換する。なお、ＨＤＬ記述からの回路への変換には、公知の論理合成ツールを用いることができる。例えば、上記のＴｙｐｅ１では、５７６０通り、Ｔｙｐｅ２では、１５３６通りの回路を論理合成することができる。
【００３３】
以下、本実施の形態にかかる加算回路合成装置１０の動作について説明し、併せて本実施の形態にかかる加算回路合成方法を説明する。図８は、本実施の形態にかかる加算回路合成方法を示すフローチャートである。
【００３４】
図８に示すように、本実施の形態の加算回路合成方法では、まず、ＣＴＤ生成部１２が、冗長加算アルゴリズムに関して入力される入力変数及び出力変数をＣＴＤに割り当てる（ステップＳ０１）。これによって、高い抽象度によって冗長加算アルゴリズムを表現したＣＴＤが生成される。
【００３５】
次いで、ＣＴＤ分解部１４が、ＣＴＤ生成部１２によって生成されたＣＴＤに分解操作を施し、カウンタノードを所望の段数としたＣＴＤを生成する。ＣＴＤ分解部１４は上述したように（３）式及び（８）式を満たすＣＴＤの未知のパラメータを、連立不等式の解として導出する（ステップＳ０２）。
【００３６】
次いで、符号化部１６が、ＣＴＤ分解部１４によって生成されたＣＴＤのパラメータを符号化する（ステップＳ０３）。上述したように、この符号化において符号化部１６は、その定義域における整数を最小限のビット数で表現可能な符合をＣＴＤのパラメータに割り当てる。
【００３７】
次いで、回路変換部１８が、符号化部１６によって生成された符合値に基づく論理関数を回路に変換する（ステップＳ０４）。上述したように、回路変換部１８は、符合値に基づいて生成する論理関数をＨＤＬ記述に変換し、当該ＨＤＬ記述を回路に自動変換する。以上のステップを経て、本実施の形態に係る加算回路合成方法の全ステップが終了となる。
【００３８】
以下、コンピュータを加算回路合成装置１０として動作させるための加算回路合成プログラムについて説明する。図９は、本実施の形態の加算回路合成プログラムの構成を示す図である。図９に示すように、本実施の形態の加算回路合成プログラム２０は、処理を統括するメインモジュール２１、ＣＴＤ生成モジュール２２、ＣＴＤ分解モジュール２４、符号化モジュール２６、及び回路変換モジュール２８によって構成される。ＣＴＤ生成モジュール２２、ＣＴＤ分解モジュール２４、符号化モジュール２６、回路変換モジュール２８がコンピュータに実現させる機能はそれぞれ、上述したＣＴＤ生成部１２、ＣＴＤ分解部１４、符号化部１６、回路変換部１８のうち、対応の要素の機能と同様である。
【００３９】
なお、加算回路合成プログラム２０は、例えば、ＣＤ−ＲＯＭ、ＤＶＤ、あるいはＲＯＭ等の記録媒体あるいは半導体メモリによって提供される。また、加算回路合成プログラム２０は、搬送波に重畳されたコンピュータデータ信号としてネットワークを介して提供されるものであってもよい。
【００４０】
以下、本実施形態にかかる加算回路合成装置１０の作用及び効果を説明する。まず、本実施の形態の加算回路合成装置１０によれば、桁上げ伝播の制限された冗長加算回路を系統的に設計することができる。従来において、冗長加算回路は、入出力の数系のみが与えられた図４（ａ）に示す一段のＣＴＤら設計されてきた。そのために、従来では、論理式の簡単化を基本とする論理合成の適用が困難であった。したがって、設計者は、桁上げ伝播が発生しないように論理レベルで冗長加算回路を手設計する必要があった。これに対して、加算回路合成装置１０によれば、例えば図６（ａ）又は図６（ｂ）に示すように、分解されたＣＴＤが導出されるので、桁上げ伝播の制限された冗長加算器を常に論理合成から得ることができる。
【００４１】
本願発明者らは、加算回路合成装置１０の効果を実証するために、１段のＣＴＤと３段のＣＴＤから得られるＨＤＬ記述を論理合成し、合成された回路構造を比較した。この比較においては、図１０及び図１１は、１段のＣＴＤと３段のＣＴＤに基づいて論理合成した回路の遅延時間と消費時間をグラフにマッピングした図であり、それぞれ８ビット冗長２進加算器、１６ビット冗長２進加算器のデータを示している。なお、図１０及び図１１において、「×」のプロットは、１段のＣＴＤから合成された回路のデータを示しており、「＋」のプロットは、３段のＣＴＤから合成された回路のデータを示している。図１０及び図１１に示すように、加算回路合成装置１０によれば、３段のＣＴＤから合成された回路が常に桁上げ伝播最小の高性能な冗長加算器となることが分る。一方、１段のＣＴＤから統制される冗長加算器には、論理合成による最適化にもかかわらず、入力語長分だけ桁上げ伝播の発生する構造が含まれていた。
【００４２】
このように、加算回路合成装置１０によれば、設計者に冗長加算アルゴリズムに関する知識を要求することなく、高性能な冗長加算器を系統的に設計することが可能となる。
【００４３】
また、加算回路合成装置１０によれば、冗長加算器の回路構造を最適化することが可能である。本願発明者らは、ＲＯＨＭ社製のＣＭＯＳ０．３５μｍプロセス（京都大学提供の低電力版スタンダードセルライブラリ．電源電圧３．０Ｖ，温度２５℃）を利用し、加算回路合成装置１０によって得られる回路と、従来の回路の遅延時間と消費電力を評価した。その結果を図１２に示す。図１２は、本実施形態の加算回路合成装置によって得られる回路及び従来の回路の遅延時間及び消費電力を示す表である。なお、図１２の表において、従来の回路１とは、IEEE Trans. Computers, Vol. 34, No. 9, pp. 789-796 September 1985に記載の従来の回路であり、従来の回路２とは、IEICE Trans. Electron., Vol. E76-C, No.3, pp436-445, March 1993.に記載の従来の回路である。また、従来の回路３とは、IEEE J. Solid-State Circuits, Vol. 31, No. 6, pp-773-783, June 1996.に記載の従来の回路である。この評価において、これら従来の回路は、上述したＴｙｐｅ１やＴｙｐｅ２の回路と同一の条件で合成された。図１２に示すように、加算回路合成装置１０によれば、消費電力、遅延時間、及び電力遅延積の面で従来の冗長加算器よりも優れていることが確認できる。
【図面の簡単な説明】
【００４４】
【図１】図１は、本発明の実施の形態にかかる加算回路合成装置の構成を概略的に示す図である。
【図２】図２は、ＣＴＤ（Counter Tree Diagram）を説明するための図である。
【図３】図３（ａ）は、カウンタノードの分解操作を説明するための図であり、分解前のＣＴＤを示している。  図３（ｂ）は、カウンタノードの分解操作を説明するための図であり、図３（ａ）に示すＣＴＤが２段に分解された状態を示している。
【図４】図４（ａ）及び図４（ｂ）は、一桁の冗長加算器を異なる抽象度のＣＴＤによって表現した図であり、それぞれ、１桁の冗長加算器、（ｋ＋１）段分解された一桁の冗長加算器を示している。
【図５】図５は、冗長２進加算器に入力変数及び出力変数を割り当てた場合のＣＴＤの一例を示す図である。
【図６】図６（ａ）及び図６（ｂ）はそれぞれ、桁上げ伝搬が２桁に制限された冗長２進加算回路の３段のＣＴＤを示す図である。
【図７】図７（ａ）、図７（ｂ）、図７（ｃ）、図７（ｄ）、図７（ｅ）は、図６（ａ）に示すＣＴＤのパラメータＸ，Ｙ，Ｚ，Ｕ，Ｖ，Ｃ１，Ｃ２それぞれへの符合の割り当てを示す表である。
【図８】図８は、本実施の形態にかかる加算回路合成方法を示すフローチャートである。
【図９】図９は、本実施の形態の加算回路合成プログラムの構成を示す図である。
【図１０】図１０は、１段のＣＴＤと３段のＣＴＤに基づいて論理合成した回路の遅延時間と消費時間をグラフにマッピングした図であり、８ビット冗長２進加算器のデータを示している。
【図１１】図１１は、図１０は、１段のＣＴＤと３段のＣＴＤに基づいて論理合成した回路の遅延時間と消費時間をグラフにマッピングした図であり、１６ビット冗長２進加算器のデータを示している。
【図１２】図１２は、本実施形態の加算回路合成装置によって得られる回路及び従来の回路の遅延時間及び消費電力を示す表である。
【符号の説明】
【００４５】
１０…加算回路合成装置、１２…ＣＴＤ生成部、１４…ＣＴＤ分解部、１６…符号化部、１８…回路変換部。
【図１】
2005250704.tif 000038
【図２】
2005250704.tif 000039
【図３】
2005250704.tif 000040
【図４】
2005250704.tif 000041
【図５】
2005250704.tif 000042
【図６】
2005250704.tif 000043
【図７】
2005250704.tif 000044
【図８】
2005250704.tif 000045
【図９】
2005250704.tif 000046
【図１０】
2005250704.tif 000047
【図１１】
2005250704.tif 000048
【図１２】
2005250704.tif 000049