(57)【要約】【課題】同期式順序回路の設計工程において、状態割当て解候補中で回路面積が最も小さい解を得て回路面積の縮小化を図る。【解決手段】同期式順序回路の状態割当てを最適化する装置において、状態割当初期解に対してパリティ検査ビット付加した状態割当解（状態割当コード伸長解）を生成するコード伸長手段４１と、該状態割当コード伸長解からコードの一つの桁を削除して複数の状態割当解候補（状態割当コード削減解）を生成するコード削減手段４２と、該複数の状態割当コード削減解のそれぞれを用いて論理合成された複数の回路図情報に基づいて、それぞれの回路面積を比較して最小面積の回路を決める状態割当コード削減解を検出する回路面積比較手段４３とを備えた。【選択図】図１
2009003562.tif 000002
【特許請求の範囲】
【請求項１】
同期式順序回路の各状態へのコードの割当である状態割当を、該同期式順序回路の設計仕様から得られる状態割当初期解に基づいて最適化する装置であって、
該状態割当初期解を構成する各コードを、パリティ検査ビットを用いて該同期式順序回路の２状態のコードが同一コードとならないよう変更して、複数の状態割当候補解を生成する候補解生成部と、
該複数の状態割当解候補のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当候補解により決まる回路面積を該複数の状態割当候補解の間で比較して、最小の回路面積を決定する状態割当候補解を検出する回路面積比較手段とを備えた同期式順序回路の状態割当て最適化装置。
【請求項２】
前記回路面積比較手段により検出された、最小の回路面積を決定する状態割当候補解を、該同期式順序回路の状態割当最終解として出力する請求項１記載の同期式順序回路の状態割当て最適化装置。
【請求項３】
前記候補解生成部は、
前記状態割当初期解を構成する各コードに前記パリティ検査ビットを付加して状態割当コード伸長解を生成するコード伸長手段と、
該状態割当コード伸長解を構成する各コードの一つの桁を削除して得られる状態割当コード削減解を前記状態割当候補解として、該コードの桁数に応じて複数生成するコード削減手段とを有する請求項１に記載の同期式順序回路の状態割当て最適化装置。
【請求項４】
前記回路面積比較手段は、前記コード削減手段により前記状態割当候補解として生成された複数の状態割当コード削減解のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当コード削減解により決まる回路面積を該複数の状態割当コード削減解の間で比較するものであり、
前記候補解生成部は、最小の回路面積を決定する状態割当コード削減解を状態割当最終解として出力する請求項３に記載の同期式順序回路の状態割当て最適化装置。
【請求項５】
前記候補解生成部は、
前記状態割当初期解を構成する各コードに前記パリティ検査ビット付加して状態割当コード伸長解を生成するコード伸長手段と、
該状態割当コード伸長解を構成する各コードの一つの桁を削除して得られる状態割当コード削減解を前記状態割当候補解として、該コードの桁数に応じて複数生成するコード削減手段と、
該状態割当コード伸長解を構成する各コードの特定桁を削除し、該特定桁を削除して得られた状態割当解を構成する複数のコードのうちの、所定の桁の値が同じであるコードが割り当てられている状態を入れ替えて、状態割当コード交換解を、前記状態割当候補解として複数生成するコード交換手段とを有する請求項１に記載の同期式順序回路の状態割当て最適化装置。
【請求項６】
前記状態割当伸長解を構成する各コードの桁のうちの削除される桁は、その削除により最も回路面積が小さくなる桁であり、
該状態割当伸長解を構成する各コードの桁のうちの交換される桁は、その削除により回路面積が２番目に小さくなる桁である請求項５に記載の同期式順序回路の状態割当て最適化装置。
【請求項７】
前記回路面積比較手段は、該コード削減手段により前記状態割当候補解として生成された複数の状態割当コード削減解のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当コード削減解により決まる回路面積を該複数の状態割当コード削減解の間で比較し、かつ、該コード交換手段により前記状態割当候補解として生成された複数の状態割当コード交換解のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当コード交換解により決まる回路面積を該複数の状態割当コード交換解の間で比較するものであり、
前記候補解生成部は、該回路面積比較手段での比較結果に基づいて、最小の回路面積を決定する状態割当候補解である状態割当コード削減解あるいは状態割当コード交換解を、状態割当最終解として検出する請求項５または６に記載の同期式順序回路の状態割当て最適化装置。
【請求項８】
前記コード伸長手段は、前記同期式順序回路の設計仕様から得られる状態割当初期解とともに、前記コード交換手段により得られた複数の状態割当コード交換解のうちの、最小の回路面積を決定する状態割当コード交換解を、前記パリティ検査を付加する対象とするものであり、
前記候補解生成部は、最小の回路面積を決定する状態割当コード削減解を生成する第１の動作と、最小の回路面積を決定する状態割当コード交換解を生成する第２の動作とを、すでに生成された状態割当コード削減解あるいは状態割当コード交換解により決まる回路面積より小さい回路面積を決定する状態割当コード交換解がなくなるまで繰り返すものであり、
該第１の動作は、前記コード伸長手段およびコード削減手段により複数の状態割当コード削減解を生成し、該複数の状態割当コード削減解の間で、該状態割当コード削減解により決まる回路面積を比較して、最小の回路面積を決定する状態割当コード削減解を生成するものであり、
該第２の動作は、前記コード交換手段により複数の状態割当コード交換解を生成し、該複数の状態割当コード交換解の間で、該状態割当コード交換解により決まる回路面積を比較して、最小の回路面積を決定する状態割当コード交換解を生成するものである請求項６記載の同期式順序回路の状態割当て最適化装置。
【請求項９】
前記同期式順序回路の設計仕様は状態遷移表であり、
前記状態割当初期解は、該状態遷移表から得られる請求項１ないし８のいずれかに記載の同期式順序回路の状態割当て最適化装置。
【請求項１０】
請求項１ないし９のいずれかに記載の同期式順序回路の状態割当て最適化装置と、
該同期式順序回路の設計仕様から得られる遷移状態表と、該同期式順序回路の状態割当て最適化装置から得られる状態割当解とから、前記回路図情報として、組合せ回路と状態記憶回路とを含む同期式順序回路の回路図情報を論理合成する回路変換手段とを備えた論理合成装置。
【請求項１１】
前記状態遷移表を前記同期式順序回路の設計仕様として入力され、該状態遷移表から、該同期式順序回路の各状態にコードを割当てて、前記状態割当初期解として該一群のコードからなる状態割当解を出力する状態割当て手段を有する請求項１０記載の論理合成装置。
【請求項１２】
同期式順序回路の各状態へのコードの割当である状態割当を、該同期式順序回路の設計仕様から得られる状態割当初期解に基づいて最適化する方法であって、
該状態割当初期解を構成する各コードを、パリティ検査ビットを用いて該同期式順序回路の２状態のコードが同一コードとならないよう変更して、複数の状態割当候補解を生成する候補解生成ステップと、
該複数の状態割当解候補のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当候補解により決まる回路面積を該複数の状態割当候補解の間で比較して、最小の回路面積を決定する状態割当候補解を検出する回路面積比較ステップとを含む同期式順序回路の状態割当て最適化方法。
【請求項１３】
該回路面積比較ステップにより検出された、最小の回路面積を決定する状態割当候補解を、該同期式順序回路の状態割当最終解とする請求項１２に記載の同期式順序回路の状態割当て最適化方法。
【請求項１４】
前記候補解生成ステップでは、
前記状態割当初期解を構成する各コードに前記パリティ検査ビットを付加して状態割当コード伸長解を生成し、
該状態割当コード伸長解を構成する各コードの一つの桁を削除して得られる状態割当コード削減解を前記状態割当候補解として、該コードの桁数に応じて複数生成し、
前記回路面積比較ステップでは、前記状態割当候補解として生成された複数の状態割当コード削減解のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当コード削減解により決まる回路面積を該複数の状態割当コード削減解の間で比較して、最小の回路面積を決定する状態割当コード削減解を状態割当最終解として検出する請求項１２記載の同期式順序回路の状態割当て最適化方法。
【請求項１５】
前記候補解生成ステップでは、
前記状態割当初期解を構成する各コードに前記パリティ検査ビット付加して状態割当コード伸長解を生成し、
該状態割当コード伸長解を構成する各コードの一つの桁を削除して得られる状態割当コード削減解を前記状態割当候補解として、該コードの桁数に応じて複数生成し、
該状態割当伸長解を構成する各コードの特定桁を削除し、該特定桁を削除して得られた状態割当解を構成する複数のコードのうちの、所定の桁の値が同じであるコードが割り当てられている状態を入れ替えて、状態割当コード交換解を、前記状態割当候補解として複数生成し、
前記回路面積比較ステップでは、前記状態割当候補解として生成された複数の状態割当コード削減解のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当コード削減解により決まる回路面積を該複数の状態割当コード削減解の間で比較し、かつ、前記状態割当候補解として生成された複数の状態割当コード交換解のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当コード交換解により決まる回路面積を該複数の状態割当コード交換解の間で比較し、これらの比較結果に基づいて、最小の回路面積を決定する状態割当候補解である状態割当コード削減解あるいは状態割当コード交換解を、状態割当最終解として検出する請求項１２記載の同期式順序回路の状態割当て最適化方法。
【請求項１６】
前記状態割当コード伸長解を構成する各コードの桁のうちの、前記状態割当コード交換解を生成する際に削除する桁は、その削除により最も回路面積が小さくなる桁であり、
該状態割当コード伸長解を構成する各コードの桁のうちの、前記状態割当コード交換解を生成する際に前記状態の入れ替えが行われるよう交換される桁は、その削除により回路面積が２番目に小さくなる桁である請求項１５に記載の同期式順序回路の状態割当て最適化方法。
【請求項１７】
前記候補解生成ステップは、該同期式順序回路の設計仕様から得られる状態割当初期解とともに、前記複数の状態割当コード交換解のうちの、最小の回路面積を決定する状態割当コード交換解を、前記パリティ検査ビットを付加する対象とするものであり、
前記候補解生成ステップでは、最小の回路面積を決定する状態割当コード削減解を生成する第１の処理と、最小の回路面積を決定する状態割当コード交換解を生成する第２の処理とを、すでに生成された状態割当コード削減解あるいは状態割当コード変換解により決まる回路面積より小さい回路面積を決定する状態割当コード変換解がなくなるまで、繰り返すものであり、
該第１の処理は、前記複数の状態割当コード削減解を生成し、該複数の状態割当コード削減解の間で、該状態割当コード削減解により決まる回路面積を比較して、該最小の回路面積を決定する状態割当コード削減解を生成する処理であり、
該第２の処理は、前記複数の状態割当コード交換解を生成し、該状態割当コード交換解により決まる回路面積を比較して、該最小の回路面積を決定する状態割当コード交換解を生成する処理である請求項１６に記載の同期式順序回路の状態割当て最適化方法。
【請求項１８】
コンピュータにより、同期式順序回路の各状態へのコードの割当である状態割当を、該同期式順序回路の設計仕様から得られる状態割当初期解に基づいて最適化する方法であって、
該コンピュータが、該状態割当初期解を構成する各コードを、パリティ検査ビットを用いて該同期式順序回路の２状態のコードが同一コードとならないよう変更して、複数の状態割当候補解を生成する候補解生成ステップと、
該コンピュータが、該複数の状態割当解候補のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当候補解により決まる回路面積を該複数の状態割当候補解の間で比較して、最小の回路面積を決定する状態割当候補解を検出する回路面積比較ステップとを含む同期式順序回路の状態割当て最適化方法。
【請求項１９】
請求項１８に記載の同期式順序回路の状態割当て最適化方法を構成する各処理ステップを前記コンピュータに実行させるための処理手順が記述された同期式順序回路の状態割当て最適化処理プログラム。
【請求項２０】
請求項１９に記載の同期式順序回路の状態割当て最適化処理プログラムが記録されたコンピュータ読み取り可能な可読記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、同期式順序回路の状態割当て最適化装置、同期式順序回路の状態割当て最適化方法、論理合成装置、プログラム、および可読記録媒体に関し、デジタル回路などに幅広く利用される同期式順序回路の設計工程に用いられ、その設計仕様として与えられる状態遷移表に対する状態割当てを最適化する同期式順序回路の状態割当て最適化装置、これを用いた論理合成装置、同期式順序回路の状態割当て最適化方法、これを実行するための同期式順序回路の状態割当て最適化処理プログラム、およびこの処理プログラムが記録されたコンピュータ読み取り可能な可読記録媒体に関する。
【背景技術】
【０００２】
組合せ回路は、論理出力がその時刻の論理入力によってのみ決定される回路であり、インバータ、ＮＡＮＤ回路、ＮＯＲ回路およびこれらを組合せた論理回路である。このような論理回路では、論理入力を論理演算することによって論理出力が得られる。
【０００３】
また、順序回路は、ある時刻の出力がその時刻の論理入力だけでは決定されず、過去から現在までの入力の系列によって出力が決定される回路であり、ＣＰＵにおけるデータ転送や演算などを制御する信号が順序回路によって生成される。この順序回路は、基準となるタイミング信号であるクロック信号の下で複数の状態を遷移しながら動作が進められる同期式のものと、論理素子（論理ゲート）や配線の遅延に依存して動作が進められる非同期式のものに分けられる。
【０００４】
図１１は、このような同期式順序回路を説明するブロック図である。
【０００５】
図１１に示すように、同期式順序回路１００は、組合せ回路１０１と、レジスタなどの状態記憶回路１０２とを有し、該状態記憶回路１０２には現在の状態を示す現状態コードが記憶されている。この同期式順序回路１００は、同期信号であるクロック信号ＣＬに同期して、状態記憶回路１０２に記憶された現状態コードＣｓが組合せ回路１０１に出力され、入力信号Ｘｎと現状態コードＣｓに応じた出力信号Ｗｎが組合せ回路１０１から出力される。また、組合せ回路１０１からは、次の状態を示す次状態コードＮｓが状態記憶回路１０２に供給される。産業上でデジタル回路と呼ばれるものの殆どは、この同期式順序回路に該当している。
【０００６】
このような順序回路を構成する方法は、与えられた動作条件、つまり入力パターンとこれに対応する所望の出力パターンとの対応関係を満足するような状態遷移表を作成し、この状態遷移表から論理式を導き、該論理式に基づいて論理回路図情報を求めるというものであり、この同期式順序回路１００の設計工程では、その仕様として状態遷移表が与えられる。下記の表１はその一例として、入力数３、出力数５、状態数４の状態を記号として表現した状態遷移表を示している。
【０００７】
【表１】
2009003562.tif 000003
上記表１中の“−”は、ドントケア（０でも１でもよいこと）を意味する。例えば、上記表１中の１行目は、「入力ｘ１が”０”であり、かつ、現在の状態が状態ＨＧであるときに、出力ｗ１、ｗ２、ｗ３、ｗ４およびｗ５の各々に対して”０，０，０，１，０”が出力される。そこで同期信号が与えられても、次の状態は状態ＨＧのままである。」という仕様を表している。また、上記表１中の例えば５行目は、「入力ｘ３が”１”であり、かつ、現在の状態が状態ＨＹであるときに、出力ｗ１、ｗ２、ｗ３、ｗ４およびｗ５の各々に対して”１，０，１，１，０”が出力される。そこで同期信号が与えられると、次の状態として状態ＦＧに状態遷移する。」という仕様を表している。
【０００８】
上記状態遷移表（表１）は、各状態を円として表し、起り得る状態遷移を矢印として表して、図１２のような状態遷移図として表現される場合もある。図１２では、矢印Ａによって上記表１の１行目および２行目が表され、矢印Ｂによって上記表１の３行目が表され、矢印Ｃによって上記表１の４行目が表され、矢印Ｄによって上記表１の５行目が表され、矢印Ｅによって上記表１の６行目が表され、矢印Ｆによって上記表１の７行目および８行目が表され、矢印Ｇによって上記表１の９行目が表され、矢印Ｈによって上記表１の１０行目が表されている。
【０００９】
この他にも、状態遷移の表現方法としては、ＶＨＤＬやＶｅｒｉｌｏｇ−ＨＤＬなどのＨＤＬ（ハードウェア記述言語）によって記述される場合もある。
【００１０】
現在の状態を状態記憶回路１０２によって記憶するに際しては、各状態を何ビット（ｂｉｔ）かのコード（信号値の組）によって表す必要がある。例えば、状態数が４である場合には、２ビット（ｂｉｔ）の状態コード（００，０１，１０，１１）によって各状態を表すことが可能である。
【００１１】
ここで、個々の状態同士を区別するためには、状態数とコード長との間に
コード長≧ｌｏｇ２（状態数）   ・・・（式１）
という関係式が成り立つ必要がある。
【００１２】
しかしながら、コード長が短い方が状態記憶回路１０２の記憶容量が少なくてもよいため、状態記憶回路１０２の面積を小さくすることができる。また、どの状態にどのコードを割当てても図１１に示す組合せ回路１０１を構成することは可能であるが、コードの割当て方によって組合せ回路１０１に入力される現状態コードと組合せ回路１０１から出力される次状態コードが変化し、必要な組合せ論理が変化するため、それぞれの状態を適切なコードに割当てることによって、組合せ回路１０１の面積をより小さく設計することができる。したがって、各状態へのコードの割当て方は、回路面積の縮小化のために非常に重要である。
【００１３】
このように、コードを各状態に割当てる問題は、一般に状態割当て問題と呼ばれており、例えば非特許文献１および非特許文献２などに記載されているように、組合せ論理を表す論理式を共通項の括り出しなどによってより簡単化できる場合に、その組合せ論理を変換して得られる回路の面積をより小さくすることができると考えられる。
【００１４】
従来、回路面積削減を目的とした状態割当て方法または装置としては、例えば特許文献１〜特許文献７に開示されているようなものが挙げられる。
【００１５】
例えば、特許文献１には、被設計ＬＳＩの設計仕様データに基づいて論理回路ネットデータを自動出力する自動論理合成装置において、被設計ＬＳＩの対象回路毎に特質を見極めて、複数の状態割当てアルゴリズムが記憶された記憶手段から該対象回路に最適な状態割当てアルゴリズムを選択し、選択された状態割当てアルゴリズムに基づいて、複数の状態のそれぞれに状態コードを割当てる状態割当て処理を行うものが開示されている。
【００１６】
特許文献２には、状態遷移表現に対して状態コードを割り付ける方法において、（１）状態遷移表現中で他の状態から遷移してくることが最も多い状態を抽出して、その状態に所定の値を割当て、（２）状態遷移を引き起こす入力が最も複雑な状態を抽出して、その状態を表現するために使用される状態変数の数と状態変数を用いて表現可能な最大の状態数を算出し、算出された最大の状態数から状態変数のいくつかが不定である状態コードの組合せを抽出し、状態コードから状態変数の不定部分が最も多いコードを抽出して、入力が最も複雑な状態に状態変数の不定部分が最も多いコードを割当て、（３）状態コードを割当てた状態と隣接関係を有する状態を抽出して、コードの１桁だけが異なるコードに割当てる状態コード割り付け方法が開示されている。
【００１７】
特許文献３には、同期式順序回路の状態割当て装置において、設計仕様として与えられた状態遷移表に含まれる状態の数から状態コード長と評価関数とを求めて、その状態コード長から評価関数の値に基づいて、評価関数全体の変数の数が最も削減されるように所定のコードを割当てるものが開示されている。
【００１８】
特許文献４には、論理状態割当システムにおいて、機能記述において条件保護のように相関の強い保護状態を有する部分に、状態コードを優先的に割当てて、その保護部分以外の状態間の相関を計算し、相関の大きいところにハミング距離が小さくなるように状態コードを割当てるものが開示されている。
【００１９】
特許文献５には、有限状態機械の状態割当て方法において、状態遷移記述を解析して有限状態機械を構成する組合せ論理回路を表す論理式を作成して、各状態に２進コードをそれぞれ対応付けた状態割当て解（初期解）を作成し、この状態割当て解を用いて論理式の単純化処理を行って、その処理結果の論理式に基づいて組合せ論理回路の規模を評価し、その評価結果に基づいて状態割当て解を改善可能であるか否かを判定して、改善可能である場合には新しい状態割当て解を生成して評価処理に供するものが開示されている。
【００２０】
特許文献６には、同期式順序回路の状態割当て方法において、設計仕様として与えられた状態遷移表に含まれる状態の種類数から状態コード長を求め、状態遷移表から状態対である状態ｉとｊに関して同一状態間および異なる状態間のそれぞれで削減可能な状態変数の個数を考慮して回路の論理式中の変数の個数の削減を評価する関数を求めて、状態コード長と評価関数の値に基づいて、論理式の変数の個数が最も削減されるように各状態にコードを割当てるものが開示されている。
【００２１】
特許文献７には、同期式順序回路の状態割当て最適化方法において、与えられた状態割当て解に対し、状態コードの入替えによって別解候補を複数生成し、その各々を実際に論理合成してみて得られる回路面積が最も小さい解を選ぶことを繰返して、より得られる回路面積が小さくなるような状態割当て解を求める手法が示されている。
【非特許文献１】大学講座電子工学ディジタル代数学、１９６６年、共立出版、Ｐ２３２
【非特許文献２】情報処理ハンドブック、１９８９年、（社）情報処理学会編、Ｐ２０８
【特許文献１】特開平４−２６４９８２号公報
【特許文献２】特開平５−２７９７６号公報
【特許文献３】特開平６−２３０９３０号公報
【特許文献４】特開平７−１９２０２７号公報
【特許文献５】特開平９−２３１２５１号公報
【特許文献６】特開２００１−１１７９６５号公報
【特許文献７】特開２００６−１３４３０２号公報
【発明の開示】
【発明が解決しようとする課題】
【００２２】
このように、デジタル回路を設計開発する上で、回路面積削減は重要な課題である。例えばウェハ上の５０ｍｍ×５０ｍｍの領域を例として考えた場合に、その領域から５ｍｍ×５ｍｍの大きさの回路を１００個作製することができるが、４ｍｍ×４ｍｍの大きさの回路であれば１４４個作製することができる。回路の１個当りの原価は、後者の方が単純計算で３割程度安くなる。各回路を同一単価で売却することが可能であれば、その原価の差がそのまま利益増に繋がる。
【００２３】
一方、価格競争を勝ち抜くべく、原価の差を単価に反映させる販売戦略も考えられる。何れにせよ、可能な限りの回路面積削減を図る上で、人手により回路を設計する場合の設計者の能力向上や、論理合成プログラムを用いて回路設計を行う場合のプログラムの性能向上は当然のことながら、より優れた状態割当て方法を採用することが、特に、状態数が非常に大きい回路である場合には重要である。
【００２４】
しかしながら、上述した特許文献１ないし６に記載の同期式順序回路の状態割当て方法には、以下のような問題がある。
【００２５】
つまり、従来の状態割り当て方法は、「次状態コードと出力信号とを計算する組合せ論理を表す論理式における変数の数」といった評価関数を用いるのが一般的であるが、評価関数と回路面積との間には、完全相関の関係がある訳ではないという点である。
【００２６】
これに対し、特許文献７に記載の状態割り当て方法は、評価関数を用いず、複数の状態割当て解候補について各々実際に論理合成して面積を比較することによって、より面積が小さくなる解を得ようとする方法である。
【００２７】
ところで、もちろん、状態割当て解が取り得る全ての場合を尽くせば面積最小解が得られるが、全ての場合を尽くすのは現実的な時間内には不可能である。結局、解の良さと処理時間にはトレードオフの関係が生まれる。限られた時間の中でできるだけ良い解を得るには、面積が小さくなる可能性のより高い解候補を導き出すということと同時に、短時間で解候補を導き出すということが重要となる。短時間で解候補を導き出せれば、その分より多くの解候補を論理合成し面積を比較することができることになり、より良い解が得られる可能性が高まる。このような観点から、特許文献７の方法は、内部に論理合成後の回路の構造を解析する手段を持つことが必須であり、１個の解候補を導き出すのにそれなりの処理時間を要するという問題がある。
【００２８】
以下さらに具体的に従来の問題点について説明すると、回路面積は、状態遷移表と状態割当てを限定しても、何らかの計算によって直接的に求まるものではない。まず、回路に変換する際の条件（人手により変換する場合の設計者の癖、論理合成を適用する場合の論理合成プログラムの種類やバージョン、セルライブラリの構成、仕様や製造上の制限による様々な設計制約等）が異なると、設計される回路は、面積、動作速度、構造などが異なった多様なものになる。
【００２９】
また、回路に変換する際の条件を限定した場合でも、実際に回路に変換してみないと、正確な回路面積を知ることはできない。したがって、状態割当ての全ての場合について、各々回路に変換した後で面積を比較してみないと、回路面積が最小になる状態割当てを特定することはできない。
【００３０】
しかしながら、下記の表２に示すように、状態数が増えると、状態割当ての場合の数が爆発的に増える。
【００３１】
【表２】
2009003562.tif 000004
上記表２は、状態数と、状態割当ての場合の数との関係を示すものである。例えば、状態数が４の場合には、上記式１から状態コード長が２となり、００〜１１の４個のコードの中から４個を選んで４つの状態のそれぞれに割当てる状態割当ての場合の数は２４となる。しかしながら、状態数が５の場合には、上記式１から状態コード長が３となり、０００〜１１１の８個のコードの中から５個を選んで５つの状態のそれぞれに割当てる状態割当ての場合の数は６７２０となる。したがって、状態割当ての全ての場合について回路に変換して面積を比較するという方法は、状態数が５以上になると実用的でなくなる。
【００３２】
また、特許文献１〜６の状態割当て方法では、いずれも、評価基準として「次状態コードと出力信号とを計算する組合せ論理を表す論理式における変数の数」を採用しているため、回路面積が最も小さくなる状態割当て解が選択されず、捨てられてしまう可能性がある。
【００３３】
また、このような状態割当て方法の問題を解決したものとして、特許文献７では、状態割当て解候補を幾つか挙げた上で、その全てを実際に回路に変換し、回路面積そのものを評価基準として回路面積が最小のものを選択するという方法が提案されている。
【００３４】
この場合、回路面積そのものが評価基準であるため、状態割当て解候補の生成と解の選択とを繰返すことによって、より回路面積が小さい解にたどり着くことが可能であると考えられる。しかしながら、解候補を多数挙げてしまうと、回路に変換すべき解候補の数が膨大になってしまい、その結果、実用的な時間内に最適な状態割当て解を決定することができないという問題がある。
【００３５】
そこで、この特許文献７では、注目パス判定手段、注目パス特徴解析手段、注目パスと状態遷移の対応判定手段を用いることにより、解候補を絞り込んでいる。しかしながら、これらの手段は各々非常に複雑なものであるという問題がある。
【００３６】
本発明は、上記のような従来の問題を解決するためになされたもので、従来手法よりも、より短時間により多くの候補を比較してより回路面積の小さい解を得ることができる同期式順序回路の状態割当て最適化装置、これを用いた論理合成装置、同期式順序回路の状態割当て最適化方法、これを実行するための同期式順序回路の状態割当て最適化処理プログラムおよびこの処理プログラムが記録された可読記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００３７】
本発明の同期式順序回路の状態割当て最適化装置は、同期式順序回路の各状態へのコードの割当である状態割当を、該同期式順序回路の設計仕様から得られる状態割当初期解に基づいて最適化する装置であって、該状態割当初期解を構成する各コードを、パリティ検査ビットを用いて該同期式順序回路の２状態のコードが同一コードとならないよう変更して、複数の状態割当候補解を生成する候補解生成部と、該複数の状態割当解候補のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当候補解により決まる回路面積を該複数の状態割当候補解の間で比較して、最小の回路面積を決定する状態割当候補解を検出する回路面積比較手段とを備えたものであり、そのことにより上記目的が達成される。
【００３８】
本発明は、上記同期式順序回路の状態割当て最適化装置において、前記回路面積比較手段により検出された、最小の回路面積を決定する状態割当候補解を、該同期式順序回路の状態割当最終解として出力することが好ましい。
【００３９】
本発明は、上記同期式順序回路の状態割当て最適化装置において、前記候補解生成部は、前記状態割当初期解を構成する各コードに前記パリティ検査ビットを付加して状態割当コード伸長解を生成するコード伸長手段と、該状態割当コード伸長解を構成する各コードの一つの桁を削除して得られる状態割当コード削減解を前記状態割当候補解として、該コードの桁数に応じて複数生成するコード削減手段とを有することが好ましい。
【００４０】
本発明は、上記同期式順序回路の状態割当て最適化装置において、前記回路面積比較手段は、前記コード削減手段により前記状態割当候補解として生成された複数の状態割当コード削減解のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当コード削減解により決まる回路面積を該複数の状態割当コード削減解の間で比較するものであり、前記候補解生成部は、最小の回路面積を決定する状態割当コード削減解を状態割当最終解として出力することが好ましい。
【００４１】
本発明は、上記同期式順序回路の状態割当て最適化装置において、前記候補解生成部は、前記状態割当初期解を構成する各コードに前記パリティ検査ビット付加して状態割当コード伸長解を生成するコード伸長手段と、該状態割当コード伸長解を構成する各コードの一つの桁を削除して得られる状態割当コード削減解を前記状態割当候補解として、該コードの桁数に応じて複数生成するコード削減手段と、該状態割当コード伸長解を構成する各コードの特定桁を削除し、該特定桁を削除して得られた状態割当解を構成する複数のコードのうちの、所定の桁の値が同じであるコードが割り当てられている状態を入れ替えて、状態割当コード交換解を、前記状態割当候補解として複数生成するコード交換手段とを有することが好ましい。
【００４２】
本発明は、上記同期式順序回路の状態割当て最適化装置において、前記状態割当伸長解を構成する各コードの桁のうちの削除される桁は、その削除により最も回路面積が小さくなる桁であり、該状態割当伸長解を構成する各コードの桁のうちの交換される桁は、その削除により回路面積が２番目に小さくなる桁であることが好ましい。
【００４３】
本発明は、上記同期式順序回路の状態割当て最適化装置において、前記回路面積比較手段は、該コード削減手段により前記状態割当候補解として生成された複数の状態割当コード削減解のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当コード削減解により決まる回路面積を該複数の状態割当コード削減解の間で比較し、かつ、該コード交換手段により前記状態割当候補解として生成された複数の状態割当コード交換解のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当コード交換解により決まる回路面積を該複数の状態割当コード交換解の間で比較するものであり、前記候補解生成部は、該回路面積比較手段での比較結果に基づいて、最小の回路面積を決定する状態割当候補解である状態割当コード削減解あるいは状態割当コード交換解を、状態割当最終解として検出することが好ましい。
【００４４】
本発明は、上記同期式順序回路の状態割当て最適化装置において、前記コード伸長手段は、前記同期式順序回路の設計仕様から得られる状態割当初期解とともに、前記コード交換手段により得られた複数の状態割当コード交換解のうちの、最小の回路面積を決定する状態割当コード交換解を、前記パリティ検査を付加する対象とするものであり、前記候補解生成部は、最小の回路面積を決定する状態割当コード削減解を生成する第１の動作と、最小の回路面積を決定する状態割当コード交換解を生成する第２の動作とを、すでに生成された状態割当コード削減解あるいは状態割当コード交換解により決まる回路面積より小さい回路面積を決定する状態割当コード交換解がなくなるまで繰り返すものであり、該第１の動作は、前記コード伸長手段およびコード削減手段により複数の状態割当コード削減解を生成し、該複数の状態割当コード削減解の間で、該状態割当コード削減解により決まる回路面積を比較して、最小の回路面積を決定する状態割当コード削減解を生成するものであり、該第２の動作は、前記コード交換手段により複数の状態割当コード交換解を生成し、該複数の状態割当コード交換解の間で、該状態割当コード交換解により決まる回路面積を比較して、最小の回路面積を決定する状態割当コード交換解を生成するものであることが好ましい。
【００４５】
本発明は、上記同期式順序回路の状態割当て最適化装置において、前記同期式順序回路の設計仕様は状態遷移表であり、前記状態割当初期解は、該状態遷移表から得られることが好ましい。
【００４６】
本発明にかかる論理合成装置は、本発明の上記同期式順序回路の状態割当て最適化装置と、該同期式順序回路の設計仕様から得られる遷移状態表と、該同期式順序回路の状態割当て最適化装置から得られる状態割当解とから、前記回路図情報として、組合せ回路と状態記憶回路とを含む同期式順序回路の回路図情報を論理合成する回路変換手段とを備えたものであり、そのことにより上記目的が達成される。
【００４７】
本発明は、上記論理合成装置において、前記状態遷移表を前記同期式順序回路の設計仕様として入力され、該状態遷移表から、該同期式順序回路の各状態にコードを割当てて、前記状態割当初期解として該一群のコードからなる状態割当解を出力する状態割当て手段を有することが好ましい。
【００４８】
本発明にかかる同期式順序回路の状態割当て最適化方法は、同期式順序回路の各状態へのコードの割当である状態割当を、該同期式順序回路の設計仕様から得られる状態割当初期解に基づいて最適化する方法であって、該状態割当初期解を構成する各コードを、パリティ検査ビットを用いて該同期式順序回路の２状態のコードが同一コードとならないよう変更して、該コードの桁数に応じて複数の状態割当候補解を生成する候補解生成ステップと、該複数の状態割当解候補のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当候補解により決まる回路面積を該複数の状態割当候補解の間で比較して、最小の回路面積を決定する状態割当候補解を検出する回路面積比較ステップとを含むものであり、そのことにより上記目的が達成される。
【００４９】
本発明は、上記同期式順序回路の状態割当て最適化方法において、該回路面積比較ステップにより検出された、最小の回路面積を決定する状態割当候補解を、該同期式順序回路の状態割当最終解とすることが好ましい。
【００５０】
本発明は、上記同期式順序回路の状態割当て最適化方法において、前記候補解生成ステップでは、前記状態割当初期解を構成する各コードに前記パリティ検査ビットを付加して状態割当コード伸長解を生成し、該状態割当コード伸長解を構成する各コードの一つの桁を削除して得られる状態割当コード削減解を前記状態割当候補解として、該コードの桁数に応じて複数生成し、前記回路面積比較ステップでは、前記状態割当候補解として生成された複数の状態割当コード削減解のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当コード削減解により決まる回路面積を該複数の状態割当コード削減解の間で比較して、最小の回路面積を決定する状態割当コード削減解を状態割当最終解として検出することが好ましい。
【００５１】
本発明は、上記同期式順序回路の状態割当て最適化方法において、前記候補解生成ステップでは、前記状態割当初期解を構成する各コードに前記パリティ検査ビット付加して状態割当コード伸長解を生成し、該状態割当コード伸長解を構成する各コードの一つの桁を削除して得られる状態割当コード削減解を前記状態割当候補解として、該コードの桁数に応じて複数生成し、該状態割当伸長解を構成する各コードの特定桁を削除し、該特定桁を削除して得られた状態割当解を構成する複数のコードのうちの、所定の桁の値が同じであるコードが割り当てられている状態を入れ替えて、状態割当コード交換解を、前記状態割当候補解として複数生成し、前記回路面積比較ステップでは、前記状態割当候補解として生成された複数の状態割当コード削減解のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当コード削減解により決まる回路面積を該複数の状態割当コード削減解の間で比較し、かつ、前記状態割当候補解として生成された複数の状態割当コード交換解のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当コード交換解により決まる回路面積を該複数の状態割当コード交換解の間で比較し、これらの比較結果に基づいて、最小の回路面積を決定する状態割当候補解である状態割当コード削減解あるいは状態割当コード交換解を、状態割当最終解として検出することが好ましい。
【００５２】
本発明は、上記同期式順序回路の状態割当て最適化方法において、前記状態割当コード伸長解を構成する各コードの桁のうちの、前記状態割当コード交換解を生成する際に削除する桁は、その削除により最も回路面積が小さくなる桁であり、該状態割当コード伸長解を構成する各コードの桁のうちの、前記状態割当コード交換解を生成する際に前記状態の入れ替えが行われるよう交換される桁は、その削除により回路面積が２番目に小さくなる桁であることが好ましい。
【００５３】
本発明は、上記同期式順序回路の状態割当て最適化方法において、前記候補解生成ステップは、該同期式順序回路の設計仕様から得られる状態割当初期解とともに、前記複数の状態割当コード交換解のうちの、最小の回路面積を決定する状態割当コード交換解を、前記パリティ検査ビットを付加する対象とするものであり、前記候補解生成ステップでは、最小の回路面積を決定する状態割当コード削減解を生成する第１の処理と、最小の回路面積を決定する状態割当コード交換解を生成する第２の処理とを、すでに生成された状態割当コード削減解あるいは状態割当コード変換解により決まる回路面積より小さい回路面積を決定する状態割当コード変換解がなくなるまで、繰り返すものであり、該第１の処理は、前記複数の状態割当コード削減解を生成し、該複数の状態割当コード削減解の間で、該状態割当コード削減解により決まる回路面積を比較して、該最小の回路面積を決定する状態割当コード削減解を生成する処理であり、該第２の処理は、前記複数の状態割当コード交換解を生成し、該状態割当コード交換解により決まる回路面積を比較して、該最小の回路面積を決定する状態割当コード交換解を生成する処理であることが好ましい。
【００５４】
本発明にかかる同期式順序回路の状態割当て最適化方法は、コンピュータにより、同期式順序回路の各状態へのコードの割当である状態割当を、該同期式順序回路の設計仕様から得られる状態割当初期解に基づいて最適化する方法であって、該コンピュータが、該状態割当初期解を構成する各コードを、パリティ検査ビットを用いて該同期式順序回路の２状態のコードが同一コードとならないよう変更して、複数の状態割当候補解を生成する候補解生成ステップと、該コンピュータが、該複数の状態割当解候補のそれぞれを用いて論理合成して得られた複数の回路図情報に基づいて、該状態割当候補解により決まる回路面積を該複数の状態割当候補解の間で比較して、最小の回路面積を決定する状態割当候補解を検出する回路面積比較ステップとを含むものであり、そのことにより上記目的が達成される。
【００５５】
本発明にかかる同期式順序回路の状態割当て最適化処理プログラムは、本発明の上記同期式順序回路の状態割当て最適化方法を構成する各処理ステップを前記コンピュータに実行させるための処理手順が記述されたプログラムであり、そのことにより上記目的が達成される。
【００５６】
本発明にかかるコンピュータ読み取り可能な可読記録媒体は、本発明の上記同期式順序回路の状態割当て最適化処理プログラムが記録された可読記録媒体であり、そのことにより上記目的が達成される。
【００５７】
以上より、本発明の作用について説明する。
【００５８】
本発明では、状態割当初期解を構成する各コードを、パリティ検査ビットを用いて該同期式順序回路の２状態のコードが同一コードとならないよう変更して、該コードの桁数に応じて複数の状態割当候補解を生成する。
【００５９】
好ましくは、コード伸長手段により、状態に割り当てるコードのコード長である状態コード長が１ビット長い状態割当て解候補を生成し、更にコード削減手段によって状態コード長が元のコード長と同じ複数の状態割当て解候補を生成し、装置外部に設けられた回路変換手段に出力する。そして再度、回路面積比較手段によって、その複数の回路図情報を用いて、それぞれの回路の面積が比較されて、面積が最小となる回路（および解候補）が決定される。更に、コード交換手段により複数の状態割当て解候補を効率的に生成する。
【００６０】
従って、本発明では、状態コードの桁毎の良し悪しを容易に比較でき、このため、従来の総当たり的な評価よりもフィードバック回数が大幅に削減される。さらに、回路の構造解析といった複雑な処理を必要とせず、特許文献７の方法よりも１個の解候補の導出が短時間で行えるため、時間を限って考えればより多くの解候補を比較することができ、解候補数を限って考えればより短時間に処理を終えることができる。
【発明の効果】
【００６１】
以上により、本発明によれば、回路面積そのものを評価基準とし、かつ、解候補の絞込みにかけるコストを抑えたことによって、短時間で、回路面積がより小さくなるように状態コードを割当てることができる。つまり、従来の同期式順序回路の状態割当て方法により状態コードが割当てられた場合の回路面積以下とすることができるという特許文献７に記載の同期式順序回路の状態割当て最適化方法と同じ特長、つまり、より回路面積が小さい解にたどり着くことが可能であるという特長を持つ上に、この特長をこの最適化方法より低コストで提供することができる。
【００６２】
その結果、従来手法よりも、より短時間により多くの候補を比較してより回路面積の小さい解を得ることができる同期式順序回路の状態割当て最適化装置を得ることができる。
【発明を実施するための最良の形態】
【００６３】
以下に、本発明の実施形態について、図面を参照しながら説明する。
【００６４】
（実施形態１）
図１は、本発明の実施形態１による論理合成装置を説明するブロック図であり、この論理合成装置は、パリティ検査ｂｉｔを用いて同期式順序回路の状態割当てを最適化する装置を備えたものである。
【００６５】
図１に示すように、この実施形態１の論理合成装置１は、同期式順序回路の設計仕様として入力された状態遷移表を用いて、同期式順序回路に関する状態割当ての初期解を生成する状態割当て手段２と、同期式順序回路の状態遷移表および状態割当てに基づいて、同期式順序回路の回路図情報を論理合成により生成する回路変換手段３と、該状態割当て手段２からの状態割当ての初期解と該回路変換手段３で論理合成された回路図情報とに基づいて、同期式順序回路の状態割当てを最適化する最適化装置４とを備えている。
【００６６】
すなわち、上記状態割当て手段２は、予め設計仕様として入力される状態遷移表を用いて、複数の状態のそれぞれに、例えば２ビット符号などの状態コードを割当て、割当てられた一群のコードを状態割当ての初期解として出力するものである。
【００６７】
状態遷移表としては、例えば上記表１に示すようなものが入力される。上記表１は、上述したように、入力数３、出力数５および状態数４の状態遷移表の一例を示すものである。
【００６８】
下記の表３は、上記表１に示す状態遷移表に基づいて、上記状態割当て手段２によって行われる状態割当ての一例を示すものであり、これが状態割当ての初期解として上記状態割当て手段２から出力される。
【００６９】
【表３】
2009003562.tif 000005
上記表３では、その一例として、状態ＨＧに”００”が割当てられ、状態ＨＹに”０１”が割当てられ、状態ＦＧに”１１”が割当てられ、状態ＦＹに”１０”が割当てられている。
【００７０】
また、上記回路変換手段３は、上記状態割当て手段２から供給される状態遷移表と上記状態割当て最適化装置４から供給される状態割当てとを用いて、ある条件設定の下で論理合成を行って、同期式順序回路の回路図情報を出力する。ここで、同期式順序回路は、例えば、図１１に示すように、入力信号Ｘｎと現状態コードＣｓが入力されたときに出力信号Ｗｎと次状態コードＮｓとを生成して出力する組合せ回路１０１と、クロック信号ＣＬに同期して現状態コードＣｓを組合せ回路１０１に出力し、組合せ回路１０１から入力される次状態コードＮｓを記憶する状態記憶回路１０２とを有するものである。
【００７１】
図２は、上記表１の状態遷移表に上記表３の状態割当ての初期解を適用して、回路変換手段３により生成された回路図情報の一例を示している。
【００７２】
図２に示す同期式順序回路は、組合せ回路としての第１〜第５のインバータ回路５１〜５５、第１〜第３のＮＯＲ回路５６〜５８、ＯＲ回路５９、第１および第２のセレクタ６０，６１および第１〜第６のＮＡＮＤ回路６２〜６７と、状態記憶回路としての第１および第２のＤ型フリップフロップ６８および６９とによって構成されており、信号ｘ１〜ｘ３およびクロックＣＬがそれぞれ入力ノードＩ１〜Ｉ３およびＩｃに入力されて、信号ｗ１〜ｗ５が出力ノードＯ１〜Ｏ５から出力されるように構成されている。
【００７３】
そして、上記第１および第２の入力ノードＩ１およびＩ２にはそれぞれ、第１および第２のインバータ回路５１および５２の入力端が接続され、上記第１のＮＯＲ回路５６の３つの入力端には、該第１および第２のインバータ回路５１および５２の出力端、並びに上記第２のＤフリップフロップ回路６９のＱ出力端が接続されている。また、該第１のＮＯＲ回路５６の出力端は、上記ＯＲ回路５９の３つの入力端のうちの１つに接続され、該ＯＲ回路５９の出力端は、上記第１のＤフリップフロップ６８のＤ入力端に接続されている。これらのＤフリップフロップ６８および６９のクロック入力にはクロック信号ＣＬが入力されるようになっている。
【００７４】
該第１のＤフリップフロップ６８のＱ出力端は、第２のセレクタ６１の制御入力端に接続され、その反転Ｑ出力は、第１のセレクタ６０の一方の入力端に接続され、該第１のセレクタ６０の他方の入力端には、上記第２のＤフリップフロップ６９の反転Ｑ出力端が接続されている。また、該第１のセレクタ６０の制御入力端には第３の入力ノードＩ３が接続され、該第１のセレクタ６０の出力端は該第２のＤフリップフロップ６９のＤ入力端に接続されている。
【００７５】
上記第１のインバータ回路５１の出力端と第１の入力ノードＩ１とはそれぞれ、第１のＮＡＮＤ回路６２の第１および第２の入力端に接続され、該第１のＮＡＮＤ回路６２の出力端は第３のインバータ回路５３の入力端に接続されている。
【００７６】
さらに、上記第１のＤフリップフロップ６８のＱ出力端は第２のＮＡＮＤ回路６３の一方の入力端に、上記第２のＤフリップフロップ６９の反転Ｑ出力端は、第４の出力ノードＷ４および該第２のＮＡＮＤ回路６３の他方の入力端に接続されている。第１のＤフリップフロップ６８の反転Ｑ出力端は第３のＮＡＮＤ回路６４の一方の入力端に、第２のＤフリップフロップ６９のＱ出力端は、第２の出力ノードＷ２および該第３のＮＡＮＤ回路６４の他方の入力端に接続されている。該第２および第３のＮＡＮＤ回路６３および６４の出力はそれぞれ第４のＮＯＲ回路の２つの入力端に接続され、第４のＮＯＲ回路６５の出力端および第３の入力ノードｘ３は、第５のＮＡＮＤ回路６６の２つの入力端にそれぞれ接続されている。
【００７７】
また、上記第２のＮＯＲ回路６３の出力端は第５のインバータ回路５５の入力端に、第３のＮＯＲ回路６４の出力端は第４のインバータ回路５４の入力端に接続され、第４のインバータ回路５４の出力端は第５の出力ノードＷ５に、第５のインバータ回路５５の出力端は第３の出力ノードＷ３に接続されている。
【００７８】
また、第２のＮＯＲ回路５７の一方の入力端には該第３のインバータ回路５３の出力が接続され、第２のＮＯＲ回路５７の他方の入力端には上記第２のＤフリップフロップ６９の反転Ｑ出力端が接続され、該第２のＮＯＲ回路５７の出力端は、上記第２のセレクタ６１の一方の入力端に接続されている。この第２のセレクタ６１の他方の入力端には第１のＮＯＲ回路５６の出力端が接続されている。
【００７９】
また、第６のＮＡＮＤ回路６７の一方の入力端には該第２のセレクタ６１の出力端が接続され、該第６のＮＡＮＤ回路６７の他方の入力端には該第５のＮＡＮＤ回路６６の出力端が接続され、該第６のＮＡＮＤ回路６７の出力端には第１の出力ノードＷ１が接続されている。
【００８０】
また、上記第３のＮＯＲ回路５８の一方の入力端には上記第１のＤフリップフロップ６８の反転Ｑ出力端が接続され、該第３のＮＯＲ回路５８の他方の入力端には上記第１のＮＡＮＤ回路６２の出力端が接続されている。
【００８１】
そして、該第２のＮＯＲ回路５８の出力端は、上記第１のＮＯＲ回路５６の３つの入力端のうちの、第１のインバータ回路５２の出力端が接続されたもの以外の残りの２つの入力端の一方に接続され、該第１のＮＯＲ回路５６の該残りの２つの入力端の他方には上記第５のインバータ回路５５の出力端が接続されている。
【００８２】
ここで、現状態コードＣｓはフリップフロップ６９のＱ出力からＮＯＲ回路５６に出力され、次状態コードＮｓがＮＯＲ回路５９からフリップフロップ６８のＤ入力に入力される。
【００８３】
なお、状態割当て手段２および回路変換手段３について、その実現方法は特に限定されないが、近年では様々な論理合成技術が実用化されており、そのような論理合成技術を用いた自動処理装置を利用することができる。
【００８４】
そして、本実施形態の同期式順序回路の状態割当て最適化装置４は、コード伸長手段４１と、コード削減手段４２と、回路面積比較手段４３とを有している。
【００８５】
以下に、本実施形態１の同期式順序回路の状態割当て最適化装置４における各手段について順次詳細に説明する。
（コード伸長手段４１）
コード伸長手段４１は、状態割当て手段２から与えられた状態割当て初期解を、これにパリティ検査ｂｉｔを付加することより１ｂｉｔ長い状態割当て解（状態割当コード伸長解）に変更するものである。
【００８６】
すなわち、コード伸長手段４１では、状態割当て手段２から与えられた状態割当て初期解に各コードにパリティ検査ｂｉｔを付加することにより、各状態に対して１ｂｉｔ長く冗長な状態コードを割り当てて、状態割当コード伸長解を生成する。具体的には、パリティ検査ｂｉｔを、コード中に現れる１の数が偶数の時０で奇数の時１と決め、それをコードの右端に付加する場合、図３（ａ）に示すように、表３に示す状態ＨＧに”０００”が割当てられ、状態ＨＹに”０１１”が割当てられ、状態ＦＧに”１１０”が割当てられ、状態ＦＹに”１０１”が割当てられることとなる。
【００８７】
なお、本発明の実施形態では、コード（つまり状態割当て解の値）中に現れる１の数が偶数である時、パリティ検査ｂｉｔを０とし、該コード中の１の数が奇数である時、該パリティ検査ｂｉｔを１とする場合を示したが、パリティ検査ｂｉｔの値を０とするか１とするかの決め方は、上記のものに限らず、例えば、その決め方を上記のものとは逆にしたケース、つまり、コード（つまり状態割当て解の値）中に現れる１の数が偶数の時パリティ検査ｂｉｔを１とし、該コード中の１の数が奇数である時０とするようにしてもよい。
（コード削減手段４２）
コード削減手段４２は、コード伸長手段４１から与えられた状態割当て解を、これより１ｂｉｔ短い状態割当て解（状態割当コード削減解）に変更する。これについて以下、詳細に説明する。
【００８８】
コード削減手段４２では、コード伸長手段４１から与えられた状態割当て解（状態割当コード伸長解）の各コードにおける１つの桁を削除して得られる新たなコードを、削除する桁を変えたものを桁数分だけ作る。
【００８９】
例えば、本実施形態のコード伸長手段４１から与えられた状態割当て解のケース、つまり状態ＨＧに”０００”、状態ＨＹに”０１１”、状態ＦＧに”１１０”、状態ＦＹに”１０１”が割当てられているケースでは、計３通りの状態割当て解が生成される。つまり、コードの左から１桁目を削除した場合、図３（ｂ）に示すように、状態ＨＧに”００”、状態ＨＹに”１１”、状態ＦＧに”１０”、状態ＦＹに”０１”が割当てられる。また、コードの左から２桁目を削除した場合、図３（ｃ）に示すように状態ＨＧに”００”、状態ＨＹに”０１”、状態ＦＧに”１０”、状態ＦＹに”１１”が割当てられる。コードの左から３桁目を削除した場合は、パリティ検査ｂｉｔを削除した場合であり、図３（ｄ）に示すように、コード伸長手段４１で与えられた、状態割当ての初期解と同じものが、状態割当コード削減解として得られる。また、コード伸長手段４１で、各コードに付加したコードがパリティ検査ｂｉｔであるため、一つの桁を削除しても異なる２状態のコードが同じになることはない。
（回路面積比較手段４３）
回路面積比較手段４３は、上記コード削減手段４２により与えられた複数の状態割当て解候補（ここでは、図３（ｂ）〜図３（ｄ）に示す３つの状態割当コード削減解）のそれぞれを用いて装置外部の回路変換手段３により論理合成を行うことにより得られた複数の回路図情報に基づいて、各状態割当て候補解により決まる回路面積を比較して最小の回路面積を決める状態割当て候補解を検出するものである。
【００９０】
つまり、この回路面積比較手段４３は、コード削減手段４２により得られた複数の状態割当て候補解に対しては、上記コード伸長手段４１で得られた状態割当て解の各コードの桁を消すことにより回路面積が最も小さくなった候補解を最終解として選択する。
【００９１】
次に動作について説明する。
【００９２】
図４は本実施形態１の論理合成装置の動作を説明する図である。
【００９３】
本実施形態１の論理合成装置１に同期式順序回路の設計仕様として状態遷移表Ｔｓが入力され、論理合成処理が開始されると、状態割当て手段２は、該状態遷移表Ｔｓに基づいて、該同期式順序回路に関する状態割当て初期解ＩＡｓを生成し、該初期解ＩＡｓを最適化装置４に出力するとともに、状態遷移表Ｔｓを回路変換手段３に出力する。
【００９４】
すると、最適化装置４では、コード伸長手段４１は、状態割当て手段２から与えられた状態割当て初期解ＩＡｓの各コードにパリティ検査ｂｉｔを付加することにより、各状態に対して１ｂｉｔ長く冗長な状態コードを割り当てる（ステップＳ１）。つまり図３（ａ）に示すように、状態ＨＧに”０００”が割当てられ、状態ＨＹに”０１１”が割当てられ、状態ＦＧに”１１０”が割当てられ、状態ＦＹに”１０１”が割当てられることとなる。そして、コード伸長手段４１は、このように各状態に割り当てた一群のコードを状態割当コード伸長解として、その情報Ｅｃをコード削減手段４２に供給する。
【００９５】
次に、コード削減手段４２では、コード伸長手段４１から状態割当て解（状態割当コード伸長解）が与えられると、該状態割当コード伸長解の各コードにおける１つの桁を削除して得られる新たなコードを、削除する桁を変えて桁数分だけ作る（ステップＳ２）。ここでは、図３（ｂ）〜図３（ｄ）に示す３つの状態割当コード削減解、つまり状態割当コード伸長解の各コードの左端の桁を削除したもの（図３（ｂ））、状態割当コード伸長解の各コードの中央の桁を削除したもの（図３（ｃ））、状態割当コード伸長解の各コードの右端の桁を削除したもの（図３（ｄ））が作成され、これらの情報Ｄｃが該最適化装置４の外部の回路変換手段３に供給される。
【００９６】
すると、装置外部の回路変換手段３は、状態割当て手段２からの状態遷移表に、上記コード削減手段４２により与えられた複数の状態割当て解候補（ここでは、図３（ｂ）〜図３（ｄ）に示す３つの状態割当コード削減解）のそれぞれを適用して論理合成を行い、各状態割当て解候補（状態割当コード削減解）により決まる回路図情報Ｉｃを生成し、該回路図情報Ｉｃを最適化装置４に供給する。
【００９７】
すると、該最適化装置４では、該回路面積比較手段４３が、その外部の回路変換手段３からの複数の回路図情報に基づいて、各状態割当て候補解により決まる回路面積を比較して最小の回路面積を決める状態割当て候補解を検出する（ステップＳ３）。
【００９８】
そして、該最適化装置４は、該回路面積比較手段４３により検出された、最小の回路面積を決める状態割当て候補解を最終解としてその情報Ｃｐを出力する（ステップＳ４）。
【００９９】
このように本実施形態１では、コード伸長手段４１により、状態遷移表から得られた状態割当て初期解から、状態コード長、つまり状態に割り当てるコードのコード長が１ビット長い状態割当て解候補（状態割当コード伸長解）を生成し、更にコード削減手段４２によって状態コード長が元のコード長と同じ複数の状態割当て解候補（状態割当コード削減解）を生成し、これらの状態割当コード削減解から得られる回路図情報に基づいて、最小の回路面積を決定する状態割当コード削減解を検出するようにしたので、従来の総当たり的な状態割当ての評価に比べて非常に簡単な処理により、状態割当候補解の絞込みを行うことができる。
【０１００】
また、実際の回路図情報から状態割当候補解の絞込みを行っているので、回路の構造解析といった複雑な処理を必要とせず、特許文献７の方法よりも１個の解候補の導出が短時間で行える。このため、時間を限って考えればより多くの解候補を比較することができ、解候補数を限って考えればより短時間に処理を終えることができる。
【０１０１】
言い換えると、回路面積そのものを評価基準とし、かつ、解候補の絞込みにかけるコストを抑えたことによって、短時間で、回路面積がより小さくなるように状態コードを割当てることができる。つまり、従来の同期式順序回路の状態割当て方法により状態コードが割当てられた場合の回路面積以下とすることができるという特許文献７に記載の同期式順序回路の状態割当て最適化方法と同じ特長、つまりより回路面積が小さい状態割当解にたどり着くことが可能であるという特長を持つだけでなく、この特長をより低コストで具備することができる。
【０１０２】
なお、上記実施形態１では、コード伸長手段４１から回路面積比較手段４３までの処理を１回行った結果を状態割当て最終解とする場合を示したが、論理合成装置は、コード伸長手段４１から回路面積比較手段４３までの処理に引き続いて、この処理により得られた状態割当て最終解をさらに変更して、より小さい回路面積を決める状態割当解を求めるようにすることも可能である。
【０１０３】
（実施形態２）
図５は、本発明の実施形態２による論理合成装置を説明するブロック図であり、この論理合成装置は、上記のように、コード伸長手段４１から回路面積比較手段４３までの処理に引き続いて、さらなる状態割当て候補解の絞込みを行うものである。
【０１０４】
図５に示すように、この実施形態２の論理合成装置１ａは、実施形態１の論理合成装置１と同様、同期式順序回路の設計仕様として入力された状態遷移表を用いて、同期式順序回路に関する状態割当ての初期解を生成する状態割当て手段２と、同期式順序回路の状態遷移表および状態割当てに基づいて、同期式順序回路の回路図情報を論理合成により生成する回路変換手段３と、該状態割当て手段２からの状態割当ての初期解と該回路変換手段３で論理合成された回路図情報とに基づいて、同期式順序回路の状態割当てを最適化する最適化装置４ａとを備えている。
【０１０５】
そして、この実施形態２では、上記論理合成装置１ａにおける最適化装置４ａは、コード伸長手段４１、コード削減手段４２、回路面積比較手段４３ａ、およびコード交換手段４４を有しており、コード交換手段４４は、実施形態１の論理合成装置におけるコード伸長手段４１から回路面積比較手段４３までの処理により得られた状態割当て最終解に対してさらにコード交換処理を施すものである。
【０１０６】
ここで、上記コード伸長手段４１およびコード削減手段４２は、実施形態１におけるものと同一のものである。また、コード交換手段４４は、実施形態１のコード伸長手段４１から回路面積比較手段４３までの処理により得られた最良の状態割当て解に対してコード交換処理を施して得られる複数の状態割当コード交換解を生成するもの、回路面積比較手段４３ａは、コード伸長手段４１から回路面積比較手段４３までの処理により得られた最良の状態割当て解と、該最良の状態割当て解に対してコード交換処理を施して得られる複数の状態割当コード交換解のうちで、最も小さい回路面積を決める状態割当て解を最終解として出力するものであり、以下詳しく説明する。
（回路面積比較手段４３ａ）
回路面積比較手段４３ａは、上記コード削減手段４２あるいはコード交換手段４４により与えられた複数の状態割当て解候補のそれぞれを用いて装置外部の回路変換手段３により論理合成を行うことにより得られた複数の回路図情報の面積を比較して最小の回路を検出するものである。
（コード交換手段４４）
コード交換手段４４は、回路面積比較手段４３ａからの情報に基づいて同期式順序回路の１組の複数の状態に対して、複数の状態割当て解を生成するもので、これについて以下詳細に説明する。
【０１０７】
上記のように、状態割当ての初期解にコード伸長手段４１にてパリティ検査ｂｉｔを付加し、パリティ検査ｂｉｔを付加した初期解の各コードの桁を削除した複数組の状態割当て解をコード削減手段４２にて作成し、この複数組の状態割当て解を用いた論理合成により各状態割当て解に対する回路情報を回路変換手段３にて作成し、該作成された回路情報に基づいて各状態割当て解に対する回路面積が回路面積比較手段４３にて比較され、これにより、コード伸長手段４１で生成した状態割当て解について、各桁を各々消した場合に回路面積がどうなるかが判る。
【０１０８】
桁を消す事で回路面積がより小さくなる桁とは、言い換えると、桁をそのまま残す事で回路面積がより大きいままとなる桁と考えられる。そこで、そのような桁について、消すか、変化を与える対象とすることとする。
【０１０９】
本実施形態では、図６（ａ）〜図６（ｃ）に示すように、コード伸長手段４１の結果として、状態ＨＧに”０００”、状態ＨＹに”０１１”、状態ＦＧに”１１０”、状態ＦＹに”１０１”が割当てられている場合、仮にコードの左から見て１桁目を削除した場合に最も面積が小さくなり、２桁目を削除した場合に２番目に面積が小さくなったとすると、一桁目は消し、二桁目は変化を与える対象とする。
【０１１０】
先ず一桁目を消すと、図６（ａ）に示すように、状態ＨＧに”００”、状態ＨＹに”１１”、状態ＦＧに”１０”、状態ＦＹに”０１”が割当てるという解が初期解として得られる。そして元の解の２桁目（初期解の１桁目）だけに変化を与えるということで、この解を元として、図６（ｄ）に示すように、状態ＨＧと状態ＦＧのコードを交換した解、状態ＨＹと状態ＦＹのコードを交換した解の計２つの新たな別解候補が生成される。
【０１１１】
次に動作について説明する。
【０１１２】
図７は本実施形態２の論理合成装置の動作を説明する図である。
【０１１３】
本実施形態２の論理合成装置１ａに同期式順序回路の設計仕様として状態遷移表Ｔｓが入力され、論理合成処理が開始されると、実施形態１の論理合成装置１と同様、最適化装置４ａでは、コード伸長手段４１により、状態割当て初期解ＩＡｓの各コードにパリティ検査ｂｉｔを付加することにより状態割当コード伸長解が作成され（ステップＳ１１）、コード削減手段４２により、該状態割当コード伸長解の各コードにおける１つの桁を削除して得られる新たなコードとして、状態割当コード削減解が作成される（ステップＳ１２）。
【０１１４】
その後、回路面積比較手段４３ａでは、回路変換手段３で状態遷移表に状態割当コード削減解を適用して得た回路図情報に基づいて、各状態割当コード削減解により決まる回路面積を比較して、最小の回路面積を決める最良の状態割当コード削減解が検出される（ステップＳ１３）。
【０１１５】
そして、この実施形態２では、最良の状態割当コード削減解の情報が、回路面積比較手段４３ａからコード変換手段４４に供給され、コード変換手段４４では、最良の状態割当コード削減解に対して、コードを変更する処理が施される。
【０１１６】
具体的には、図６（ｄ）に示すように、最良の状態割当コード削減解における状態ＨＧと状態ＦＧのコードを交換した第１の状態割当コード交換解と、最良の状態割当コード削減解における状態ＨＹと状態ＦＹのコードを交換した第２の状態割当コード交換解との計２つの新たな別解候補が生成される（ステップＳ１４）。
【０１１７】
そして、回路面積比較手段４３ａでは、回路変換手段３で状態遷移表に第１および第２の状態割当コード交換解を適用して得た回路図情報に基づいて、各状態割当コード交換解により決まる回路面積を比較して、最小の回路面積を決める最良の状態割当コード交換解が検出される（ステップＳ１５）。
【０１１８】
その後、該最適化装置４では、該回路面積比較手段４３ａにより検出された、最良の状態割当コード削減解および最良の状態割当コード変換解のうちで、より小さい回路面積を決める状態割当解が最終解として出力される（ステップＳ１７）。
【０１１９】
このように本実施形態２では、コード伸長手段４１から回路面積比較手段４３までの処理に引き続いて、さらなる状態割当て候補解の絞込みを行うので、回路面積のより小さい状態割当解を選択することができる。
【０１２０】
また、最良の状態割当コード削減解からのさらなる状態割当て候補解の絞込みは、最良の状態割当コード削減解における状態ＨＧと状態ＦＧのコードを交換した第１の状態割当コード交換解と、最良の状態割当コード削減解における状態ＨＹと状態ＦＹのコードを交換した第２の状態割当コード交換解との計２つの新たな別解候補を用いるので、簡単にかつ効率よく、より小さい回路面積を決める状態割当解を見つけることが可能となる。
【０１２１】
なお、上記実施形態２は、コード伸長手段４１から回路面積比較手段４３までの処理に引き続いてコード交換手段４４から回路面積比較手段４３ａまでの処理を１回行った結果の中で最も良い状態割当解を最終解とする場合を示したが、コード伸長手段４１から回路面積比較手段４３ａまでの処理と、コード交換手段４４から回路面積比較手段４３ａまでの処理を交互に繰り返すようにしてもよい。
【０１２２】
（実施形態３）
図８は、本発明の実施形態３による論理合成装置を説明するブロック図であり、この論理合成装置１ｂは、実施形態２におけるコード伸長手段４１から回路面積比較手段４３までの処理と、コード交換手段４４から回路面積比較手段４３までの処理を交互に繰り返すことにより、状態割当解のさらなる絞込みを行うものである。
【０１２３】
図８に示すように、この実施形態３の論理合成装置１ｂは、実施形態１および２の論理合成装置１および１ａと同様、同期式順序回路の設計仕様として入力された状態遷移表を用いて、同期式順序回路に関する状態割当ての初期解を生成する状態割当て手段２と、同期式順序回路の状態遷移表および状態割当てに基づいて、同期式順序回路の回路図情報を論理合成により生成する回路変換手段３と、該状態割当て手段２からの状態割当ての初期解と該回路変換手段３で論理合成された回路図情報とに基づいて、同期式順序回路の状態割当てを最適化する最適化装置４ｂとを備えている。
【０１２４】
そして、この実施形態３では、上記論理合成装置１ｂにおける最適化装置４ｂは、コード伸長手段４１ｂ、コード削減手段４２、回路面積比較手段４３ｂ、およびコード交換手段４４ｂを有している。
【０１２５】
ここで、上記コード削減手段４２は、実施形態１および２におけるものと同一のものであるので、以下コード伸長手段４１ｂ、回路面積比較手段４３ｂ、およびコード交換手段４４ｂについて順次に説明する。
（コード伸長手段４１ｂ）
コード伸長手段４１ｂは、状態割当て手段２から与えられた状態割当て初期解、あるいはコード交換手段４４ｂから与えられた状態割当コード交換解を、これにパリティ検査ｂｉｔを付加することより１ｂｉｔ長い状態割当て解に変更するものである。
【０１２６】
なお、状態割当コード交換解にパリティ検査ｂｉｔを付加する方法は、実施形態１で説明した状態割当て初期解にパリティ検査ｂｉｔを付加する方法と同じである。
（回路面積比較手段４３ｂ）
回路面積比較手段４３ｂは、上記コード削減手段４２あるいはコード交換手段４４ｂにより与えられた複数の状態割当て解候補のそれぞれを用いて装置外部の回路変換手段３により論理合成を行うことにより得られた複数の回路図情報の面積を比較し、最小の回路を決める状態割当て候補解を検出するものである。
【０１２７】
これについて以下、詳細に説明する。
【０１２８】
この回路面積比較手段４３ｂは、コード削減手段４２により得られた複数の状態割当て候補解に対しては、上記コード伸長手段４１ｂで得られた状態割当て解の各コードの桁を消すことにより回路面積が最も小さくなった候補解を選択する。また、該回路面積比較手段４３ｂは、上記候補解の選択と同時に、該各候補解に対する回路面積の情報をコード交換手段４４ｂへ渡す。
【０１２９】
上記回路面積比較手段４３ｂは、上記コード交換手段４４ｂにより得られた複数の状態割当て解に対しては、状態割当ての初期解を回路変換して得られた結果の回路面積が最小であれば、その解を最終解と判定し出力する。初期解以外の解を回路変換して得られた結果の回路面積が最小であれば、回路面積が最小であると判断された、その初期解以外の解をコード伸長手段４１ｂへと渡す。
（コード交換手段４４ｂ）
コード交換手段４４ｂは、回路面積比較手段４３ｂからの情報に基づいて同期式順序回路の１組の複数の状態に対して、複数の状態割当て解を生成する。これについて以下、詳細に説明する。
【０１３０】
このコード変換手段４４ｂでは、コード削減手段４２からの複数の状態割当て候補解（状態割当コード削減解）のうちの最小の回路面積を決めるものに対して、実施形態２のコード変換手段４４ａと同様にコード交換が行われる。
【０１３１】
次に動作について説明する。
【０１３２】
図９は本実施形態３の論理合成装置１ｂの動作を説明する図である。
【０１３３】
本実施形態３の論理合成装置１ｂに同期式順序回路の設計仕様として状態遷移表Ｔｓが入力され、論理合成処理が開始されると、実施形態１の論理合成装置１と同様、最適化装置４ｂでは、コード伸長手段４１ｂにより、状態割当て初期解ＩＡｓの各コードにパリティ検査ｂｉｔを付加することにより状態割当コード伸長解が作成され（ステップＳ２１）、コード削減手段４２により、該状態割当コード伸長解の各コードにおける１つの桁を削除して得られる新たなコード（状態割当コード削減解）が作成される（ステップＳ２２）。
【０１３４】
その後、回路面積比較手段４３ｂでは、回路変換手段３で状態遷移表に状態割当コード削減解を適用して得た回路図情報に基づいて、各状態割当コード削減解により決まる回路面積を比較して、最小の回路面積を決める最良の状態割当コード削減解が検出される（ステップＳ２３）。
【０１３５】
そして、この実施形態３では、最良の状態割当コード削減解の情報が、回路面積比較手段４３ａからコード変換手段４４に供給され、コード変換手段４４では、最良の状態割当コード削減解に対して、コードを変更する処理が施される。
【０１３６】
具体的には、図６（ｄ）に示すように、最良の状態割当コード削減解における状態ＨＧと状態ＦＧのコードを交換した第１の状態割当コード交換解と、最良の状態割当コード削減解における状態ＨＹと状態ＦＹのコードを交換した第２の状態割当コード交換解との計２つの新たな別解候補が生成される（ステップＳ２４）。
【０１３７】
その後、回路面積比較手段４３ｂでは、回路変換手段３で状態遷移表に状態割当コード交換解を適用して得た回路図情報に基づいて、各状態割当コード交換解により決まる回路面積を比較して、最小の回路面積を決める最良の状態割当コード交換解が検出される（ステップＳ２５）。
【０１３８】
そして、回路面積比較手段４３ｂでは、該ステップＳ２５で検出された最良の状態割当コード交換解と、ステップＳ２３で検出された最良の状態割当コード削除解とのいずれが望ましいかが判定される（ステップＳ２６）。
【０１３９】
この判定では、ステップＳ２３で検出された最良の状態割当コード削除解により決まる回路面積が、該ステップＳ２５で検出された最良の状態割当コード交換解より決まる回路面積と同じか、あるいは小さい場合、ステップＳ２３で検出された最良の状態割当コード削除解が最終解として出力される。
【０１４０】
一方、該ステップＳ２５で検出された最良の状態割当コード交換解より決まる回路面積が、ステップＳ２３で検出された最良の状態割当コード削除解により決まる回路面積より小さい場合は、さらに、コード伸長手段４１ｂにて、この状態割当コード交換解の各コードにパリティ検査ｂｉｔを付加することにより新たな状態割当コード伸長解が求められ、この新たな状態割当コード伸長解に対して、ステップＳ２２〜Ｓ２５の処理が行われる。
【０１４１】
このように、この実施形態３では、最良の状態割当コード削減解により決まる回路面積より、該最良の状態割当コード削減解の所定の状態を入れ替えて得られる状態割当コード変換解により決まる回路面積の方が小さくなる限り、上記ステップＳ２２〜Ｓ２１の処理が繰り返され、より小さい回路面積を決める状態割当解の絞込みが行われることとなる。
【０１４２】
このように本実施形態３では、最良の状態割当コード削減解により決まる回路面積より、該最良の状態割当コード削減解の所定の状態を入れ替えて得られる状態割当コード変換解により決まる回路面積の方が小さくなる限り、状態割当解の絞込みが続けられるので、最適な状態割当解を求めることができる。
【０１４３】
また、この実施形態３では、網羅的な状態割当候補解を生成する場合でも、コード変換の際に削除する桁あるいは変換する桁に優先順位を付けることができ、状態割当候補解としての状態割当コード変換解を１／桁数に絞ることが可能である。
（実施形態４）
図１０は、本発明の実施形態１ないし３のいずれかによる同期式順序回路の状態割当て最適化方法をコンピュータによって実行するための論理合成装置の構成例を示すブロック図である。
【０１４４】
図１０に示すように、論理合成装置８０は、制御手段としてのＣＰＵ（中央演算処理装置）８１と、可読記録媒体（記憶手段）としてのＲＯＭ８２と、ＣＰＵ８１がワークメモリとして利用する記憶手段としてのＲＡＭ８３と、キーボードやマウスなどを含む入力部８４と、ディスプレイやプリンタなどを含む出力部８５とを有している。
【０１４５】
ＲＯＭ８２には、本実施形態１ないし３のいずれかの同期式順序回路の状態割当て最適化方法をコンピュータによって実行させるための各処理手順が記述された同期式順序回路の状態割当て最適化処理プログラムおよびそのデータが記憶されている。また、ＣＰＵ８１は、このプログラムおよびそのデータをＲＡＭ８３に読み出して、同期式順序回路の状態割当て最適化処理を実行する。操作者は、必要に応じて出力部８５の表示画面上の処理結果を目で確認しながら、入力部８４から操作指示や設定値などを入力指示することができる。処理結果データとしての回路図情報および状態割当て解はＲＯＭ８２に記憶される。
【０１４６】
可読記録媒体としては、各種ＩＣメモリ、光ディスク（例えばＣＤ）および磁気記録媒体（例えばＦＤ）などの小型携帯用記憶装置であり、本発明の処理プログラムおよびそのデータがコンピュータ読み取り可能な記録媒体である。
【０１４７】
このような論理合成装置８０では、同期式順序回路の状態割当て最適化処理プログラムおよびそのデータに基づいて、図４に示すステップＳ１〜４、図７に示すステップＳ１１〜Ｓ１７、あるいは９に示すステップＳ２１〜Ｓ２７が順次実行される。
【０１４８】
以上のように、本発明の好ましい実施形態を用いて本発明を例示してきたが、本発明は、この実施形態に限定して解釈されるべきものではない。本発明は、特許請求の範囲によってのみその範囲が解釈されるべきであることが理解される。当業者は、本発明の具体的な好ましい実施形態の記載から、本発明の記載および技術常識に基づいて等価な範囲を実施することができることが理解される。本明細書において引用した特許、特許出願および文献は、その内容自体が具体的に本明細書に記載されているのと同様にその内容が本明細書に対する参考として援用されるべきであることが理解される。
【産業上の利用可能性】
【０１４９】
本発明は、デジタル回路などに幅広く利用される同期式順序回路の設計工程に用いられ、その設計仕様として与えられる状態遷移表に対する状態割当てを最適化するための同期式順序回路の状態割当て最適化装置、これを用いた論理合成装置、同期式順序回路の状態割当て最適化方法、これを実行するための同期式順序回路の状態割当て最適化処理プログラムおよびこの処理プログラムが記録されたコンピュータ読み取り可能な可読記録媒体の分野において、複数の状態に状態コードを割当てる状態割当て処理時に、回路面積そのものを評価基準として最適化することによって、その状態割当て解を用いて論理合成された回路の面積を、従来の同期式順序回路の状態割当て方法により状態コードが割当てられた場合の回路面積以下とすることができる。また、回路解析といった高いコストを要する処理を含まないため、、処理時間を短縮化することができる。したがって、本発明を適用することによって、短縮化された処理時間によって回路面積の削減を図ることができるため、デジタル回路の製造コスト削減のために寄与することができる。
【図面の簡単な説明】
【０１５０】
【図１】図１は、本発明の実施形態１による論理合成装置を説明するブロック図であり、該論理合成装置を構成する同期式順序回路の状態割当て最適化装置の構成例を示している。
【図２】図２は、上記実施形態１の論理合成装置により得られる同期式順序回路の回路図であり、状態遷移表（表１）に対して状態割当て（表３）を適用した論理合成により得られたものである。
【図３】図３は、上記実施形態１の論理合成装置の動作を説明する図であり、状態割当て初期解を構成するコードにパリティ検査ビットを付加して状態割当コード伸長解を生成する処理（図３（ａ））、状態割当コード伸長解を構成するコードの桁を削除する処理（図３（ｂ）〜図３（ｄ））を示している。
【図４】図４は、上記実施形態１の論理合成装置の動作を説明するフロー図である。
【図５】図５は、本発明の実施形態２による論理合成装置を説明するブロック図であり、該論理合成装置を構成する同期式順序回路の状態割当て最適化装置の構成例を示している。
【図６】図６は、上記実施形態２の論理合成装置の動作を説明する図であり、状態割当てコード削減解に対する回路面積の比較結果（図６（ａ）〜図６（ｃ））、及び状態割当てコード交換解を生成する処理（図６（ｄ））を示している。
【図７】図７は、上記実施形態２の論理合成装置の動作を説明するフロー図である。
【図８】図８は、本発明の実施形態３による論理合成装置を説明するブロック図であり、該論理合成装置を構成する同期式順序回路の状態割当て最適化装置の構成例を示している。
【図９】図９は、上記実施形態３の論理合成装置の動作を説明するフロー図である。
【図１０】本発明の実施形態である同期式順序回路の状態割当て最適化方法をコンピュータによって処理するための論理合成装置の構成例を示すブロック図である。
【図１１】図１１は、従来の同期式順序回路の一般的な構成例を示す回路図である。
【図１２】図１２は、状態遷移表（表１）を状態遷移図として表現した場合の一例を示す図である。
【符号の説明】
【０１５１】
１，１ａ，１ｂ  ８０  論理合成装置
２  状態割当て手段
３  回路変換手段
４、４ａ、４ｂ  同期式順序回路の状態割当て最適化装置  
４１  コード伸長手段
４２  コード削減手段
４３，４３ａ，４３ｂ  回路面積比較手段
４４，４４ｂ  コード交換手段
８０  論理合成システム
８１  ＣＰＵ（制御手段）
８２  ＲＯＭ
８３  ＲＡＭ
８４  入力部
８５出力部
１００  同期式順序回路
１０１  組合せ回路
１０２  状態記憶回路
【図１】
2009003562.tif 000006
【図２】
2009003562.tif 000007
【図３】
2009003562.tif 000008
【図４】
2009003562.tif 000009
【図５】
2009003562.tif 000010
【図６】
2009003562.tif 000011
【図７】
2009003562.tif 000012
【図８】
2009003562.tif 000013
【図９】
2009003562.tif 000014
【図１０】
2009003562.tif 000015
【図１１】
2009003562.tif 000016
【図１２】
2009003562.tif 000017