(57)【特許請求の範囲】
【請求項１】
状態0, 1, 2, ..., N-1からなる有限状態機械を表す記述を受け付ける受付部、
当該状態0, 1, 2, ..., N-1をグループ0, 1, 2, ..., M-1に分割する分割部であって、
グループ0に当該状態0, 1, ..., L[0]-1を割り当て、
グループ1に当該状態L[0], L[0]+1, ..., L[1]-1を割り当て、
グループ2に当該状態L[1], L[1]+1, ..., L[2]-1を割り当て、
...、
グループM-1に当該状態L[M-2], L[M-2]+1, ..., L[M-1]-1=N-1を割り当てる分割部、
レジスタ転送レベル記述を生成する生成部
を備え、
当該レジスタ転送レベル記述は、
（ａ）現在の状態がグループ0, 1, 2, ..., M-1のいずれのグループにあるかを記憶するレジスタT及びレジスタTに記憶されうる値のそれぞれに対応付けられる信号t[0], t[1], t[2], ..., t[M-1]を出力するデコーダEと、
（ｂ）現在の状態がグループ0にある場合に現在の状態が当該状態0, 1, ..., L[0]-1のいずれであるかを記憶するレジスタG[0]及びレジスタG[0]に記憶されうる値のそれぞれに対応付けられる信号s[0], s[1], ..., s[L[0]-1]]を出力するデコーダD[0]と、
現在の状態がグループ1にある場合に現在の状態が当該状態L[0], L[0]+1, ..., L[1]-1のいずれであるかを記憶するレジスタG[1]及びレジスタG[1]に記憶されうる値のそれぞれに対応付けられる信号s[L[0]], s[L[0]+1], ..., s[L[1]-1]]を出力するデコーダD[1]と、
現在の状態がグループ2にある場合に現在の状態が当該状態L[1], L[1]+1, ..., L[2]-1のいずれであるかを記憶するレジスタG[2]及びレジスタG[2]に記憶されうる値のそれぞれに対応付けられる信号s[L[1]], s[L[1]+1], ..., s[L[2]-1]を出力するデコーダD[2]と、
...、
現在の状態がグループM-1にある場合に現在の状態が当該状態L[M-2], L[M-2]+1, ..., L[M-1]-1=N-1のいずれであるかを記憶するレジスタG[M-1]及びレジスタG[M-1]に記憶されうる値のそれぞれに対応付けられる信号s[L[M-2]], s[L[M-2]+1], ..., s[L[M-1]-1]を出力するデコーダD[M-1]と、
信号s[0], s[1], ..., s[L[0]-1]]のそれぞれと信号t[0]とから信号g[0], g[1], ..., g[L[0]-1]]を出力し、
信号s[L[0]], s[L[0]+1], ..., s[L[1]-1]]のそれぞれと信号t[1]とから信号g[L[0]], g[L[0]+1], ..., g[L[1]-1]]を出力し、
信号s[L[1]], s[L[1]+1], ..., s[L[2]-1]のそれぞれと信号t[2]とから信号g[L[1]], g[L[1]+1], ..., g[L[2]-1]を出力し、
...、
信号s[L[M-2]], s[L[M-2]+1], ..., s[L[M-1]-1]のそれぞれと信号t[M-1]とから信号g[L[M-2]], g[L[M-2]+1], ..., g[L[M-1]-1]を出力して、
取りうる状態0, 1, 2, ..., N-1のそれぞれに対応付けられる信号g[0], g[1], g[2], ..., g[N-1]を出力する論理回路と、
信号g[0], g[1], g[2], ..., g[N-1]に基づいて次の状態を計算し、当該次の状態が、
グループ0に属する場合、レジスタTに0を記憶させ、レジスタG[0]に当該次の状態を記憶させ、
グループ1に属する場合、レジスタTに1を記憶させ、レジスタG[1]に当該次の状態を記憶させ、
グループ2に属する場合、レジスタTに2を記憶させ、レジスタG[2]に当該次の状態を記憶させ、
...、
グループM-1に属する場合、レジスタTにM-１を記憶させ、レジスタG[M-1]に当該次の状態を記憶させる遷移回路、
を表す
ことを特徴とする記述処理装置。
【請求項２】
請求項１に記載の記述処理装置であって、
L[0]並びにL[1]-L[0], L[2]-L[1], ..., L[M-1]-L[M-2]はいずれも、NをMで除算した結果の整数部の値、若しくは当該整数部の値に1を加算した値である、
ことを特徴とする記述処理装置。
【請求項３】
受付部、分割部、生成部を備える記述処理装置が実行する記述処理方法であって、
前記受付部が、状態0, 1, 2, ..., N-1からなる有限状態機械を表す記述を受け付ける受付ステップ、
前記分割部が、当該状態0, 1, 2, ..., N-1をグループ0, 1, 2, ..., M-1に分割する分割ステップであって、
グループ0に当該状態0, 1, ..., L[0]-1を割り当て、
グループ1に当該状態L[0], L[0]+1, ..., L[1]-1を割り当て、
グループ2に当該状態L[1], L[1]+1, ..., L[2]-1を割り当て、
...、
グループM-1に当該状態L[M-2], L[M-2]+1, ..., L[M-1]-1=N-1を割り当てる分割ステップ、
前記生成部が、レジスタ転送レベル記述を生成する生成ステップ、
を備え、
当該レジスタ転送レベル記述は、
（ａ）現在の状態がグループ0, 1, 2, ..., M-1のいずれのグループにあるかを記憶するレジスタT及びレジスタTに記憶されうる値のそれぞれに対応付けられる信号t[0], t[1], t[2], ..., t[M-1]を出力するデコーダEと、
（ｂ）現在の状態がグループ0にある場合に現在の状態が当該状態0, 1, ..., L[0]-1のいずれであるかを記憶するレジスタG[0]及びレジスタG[0]に記憶されうる値のそれぞれに対応付けられる信号s[0], s[1], ..., s[L[0]-1]]を出力するデコーダD[0]と、
現在の状態がグループ1にある場合に現在の状態が当該状態L[0], L[0]+1, ..., L[1]-1のいずれであるかを記憶するレジスタG[1]及びレジスタG[1]に記憶されうる値のそれぞれに対応付けられる信号s[L[0]], s[L[0]+1], ..., s[L[1]-1]]を出力するデコーダD[1]と、
現在の状態がグループ2にある場合に現在の状態が当該状態L[1], L[1]+1, ..., L[2]-1のいずれであるかを記憶するレジスタG[2]及びレジスタG[2]に記憶されうる値のそれぞれに対応付けられる信号s[L[1]], s[L[1]+1], ..., s[L[2]-1]を出力するデコーダD[2]と、
...、
現在の状態がグループM-1にある場合に現在の状態が当該状態L[M-2], L[M-2]+1, ..., L[M-1]-1=N-1のいずれであるかを記憶するレジスタG[M-1]及びレジスタG[M-1]に記憶されうる値のそれぞれに対応付けられる信号s[L[M-2]], s[L[M-2]+1], ..., s[L[M-1]-1]を出力するデコーダD[M-1]と、
信号s[0], s[1], ..., s[L[0]-1]]のそれぞれと信号t[0]とから信号g[0], g[1], ..., g[L[0]-1]]を出力し、
信号s[L[0]], s[L[0]+1], ..., s[L[1]-1]]のそれぞれと信号t[1]とから信号g[L[0]], g[L[0]+1], ..., g[L[1]-1]]を出力し、
信号s[L[1]], s[L[1]+1], ..., s[L[2]-1]のそれぞれと信号t[2]とから信号g[L[1]], g[L[1]+1], ..., g[L[2]-1]を出力し、
...、
信号s[L[M-2]], s[L[M-2]+1], ..., s[L[M-1]-1]のそれぞれと信号t[M-1]とから信号g[L[M-2]], g[L[M-2]+1], ..., g[L[M-1]-1]を出力して、
取りうる状態0, 1, 2, ..., N-1のそれぞれに対応付けられる信号g[0], g[1], g[2], ..., g[N-1]を出力する論理回路と、
信号g[0], g[1], g[2], ..., g[N-1]に基づいて次の状態を計算し、当該次の状態が、
グループ0に属する場合、レジスタTに0を記憶させ、レジスタG[0]に当該次の状態を記憶させ、
グループ1に属する場合、レジスタTに1を記憶させ、レジスタG[1]に当該次の状態を記憶させ、
グループ2に属する場合、レジスタTに2を記憶させ、レジスタG[2]に当該次の状態を記憶させ、
...、
グループM-1に属する場合、レジスタTにM-１を記憶させ、レジスタG[M-1]に当該次の状態を記憶させる遷移回路、
を表す
ことを特徴とする記述処理方法。
【請求項４】
コンピュータを、
状態0, 1, 2, ..., N-1からなる有限状態機械を表す記述を受け付ける受付部、
当該状態0, 1, 2, ..., N-1をグループ0, 1, 2, ..., M-1に分割する分割部であって、
グループ0に当該状態0, 1, ..., L[0]-1を割り当て、
グループ1に当該状態L[0], L[0]+1, ..., L[1]-1を割り当て、
グループ2に当該状態L[1], L[1]+1, ..., L[2]-1を割り当て、
...、
グループM-1に当該状態L[M-2], L[M-2]+1, ..., L[M-1]-1=N-1を割り当てる分割部、
レジスタ転送レベル記述を生成する生成部
として機能させるプログラムであって、
当該レジスタ転送レベル記述は、
（ａ）現在の状態がグループ0, 1, 2, ..., M-1のいずれのグループにあるかを記憶するレジスタT及びレジスタTに記憶されうる値のそれぞれに対応付けられる信号t[0], t[1], t[2], ..., t[M-1]を出力するデコーダEと、
（ｂ）現在の状態がグループ0にある場合に現在の状態が当該状態0, 1, ..., L[0]-1のいずれであるかを記憶するレジスタG[0]及びレジスタG[0]に記憶されうる値のそれぞれに対応付けられる信号s[0], s[1], ..., s[L[0]-1]]を出力するデコーダD[0]と、
現在の状態がグループ1にある場合に現在の状態が当該状態L[0], L[0]+1, ..., L[1]-1のいずれであるかを記憶するレジスタG[1]及びレジスタG[1]に記憶されうる値のそれぞれに対応付けられる信号s[L[0]], s[L[0]+1], ..., s[L[1]-1]]を出力するデコーダD[1]と、
現在の状態がグループ2にある場合に現在の状態が当該状態L[1], L[1]+1, ..., L[2]-1のいずれであるかを記憶するレジスタG[2]及びレジスタG[2]に記憶されうる値のそれぞれに対応付けられる信号s[L[1]], s[L[1]+1], ..., s[L[2]-1]を出力するデコーダD[2]と、
...、
現在の状態がグループM-1にある場合に現在の状態が当該状態L[M-2], L[M-2]+1, ..., L[M-1]-1=N-1のいずれであるかを記憶するレジスタG[M-1]及びレジスタG[M-1]に記憶されうる値のそれぞれに対応付けられる信号s[L[M-2]], s[L[M-2]+1], ..., s[L[M-1]-1]を出力するデコーダD[M-1]と、
信号s[0], s[1], ..., s[L[0]-1]]のそれぞれと信号t[0]とから信号g[0], g[1], ..., g[L[0]-1]]を出力し、
信号s[L[0]], s[L[0]+1], ..., s[L[1]-1]]のそれぞれと信号t[1]とから信号g[L[0]], g[L[0]+1], ..., g[L[1]-1]]を出力し、
信号s[L[1]], s[L[1]+1], ..., s[L[2]-1]のそれぞれと信号t[2]とから信号g[L[1]], g[L[1]+1], ..., g[L[2]-1]を出力し、
...、
信号s[L[M-2]], s[L[M-2]+1], ..., s[L[M-1]-1]のそれぞれと信号t[M-1]とから信号g[L[M-2]], g[L[M-2]+1], ..., g[L[M-1]-1]を出力して、
取りうる状態0, 1, 2, ..., N-1のそれぞれに対応付けられる信号g[0], g[1], g[2], ..., g[N-1]を出力する論理回路と、
信号g[0], g[1], g[2], ..., g[N-1]に基づいて次の状態を計算し、当該次の状態が、
グループ0に属する場合、レジスタTに0を記憶させ、レジスタG[0]に当該次の状態を記憶させ、
グループ1に属する場合、レジスタTに1を記憶させ、レジスタG[1]に当該次の状態を記憶させ、
グループ2に属する場合、レジスタTに2を記憶させ、レジスタG[2]に当該次の状態を記憶させ、
...、
グループM-1に属する場合、レジスタTにM-１を記憶させ、レジスタG[M-1]に当該次の状態を記憶させる遷移回路、
を表す
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限状態機械の現在の状態を高速に取得する電子回路を実現するのに好適な記述処理装置、記述処理方法並びにこれらをコンピュータ上で実現するためのプログラムに関する。
【背景技術】
【０００２】
コンピュータ技術の進歩により、動作合成ツールや論理合成ツールを備えるＣＡＤ（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ）システムを使用して半導体集積回路の設計、解析および評価等を行うのが一般的になっている。例えば、特許文献１には、動作合成ツールや論理合成ツールを備える回路設計支援システムが開示されている。
【０００３】
回路設計支援システムを用いて半導体集積回路を設計する場合、設計者は、まず、入力ポートや変数のビット幅等のＨ／Ｗ化に必要な情報を含んだ動作レベル記述を用意する。
【０００４】
次に、設計者は、動作合成ツールを用いて、動作レベル記述を、実現する論理をレジスタとレジスタ間の論理機能で表現したＲＴＬ（Ｒｅｇｉｓｔｅｒ  Ｔｒａｎｓｆｅｒ  Ｌｅｖｅｌ（レジスタ転送レベル））記述に変換する。そして、設計者は、論理合成ツールを用いて、ＲＴＬ記述をゲートレベルの論理回路に変換する。
【０００５】
有限状態機械、すなわちステートマシンを含む半導体集積回路を設計する場合も、上述した回路設計支援システムを用いて半導体集積回路を設計する。なお、ステートマシンは、特殊な動作を行うカウンタであり、現在の状態を記憶するフリップフロップ、遷移すべき状態を生成する次状態生成回路およびフリップフロップの状態出力をデコードする状態抽出回路の組み合わせにより構成される。ステートマシンの構成については、例えば、特許文献２に開示されている。
【特許文献１】特開２００７−２７２６７１号公報
【特許文献２】特開平１０−２３３６７２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ステートマシンの動作速度は、半導体集積回路全体の動作速度に大きく影響を及ぼす。このため、ステートマシンが現在の状態をデコードするのに要する時間はできるだけ短いことが望ましい。特に、特許文献１に開示された設計支援システムを用いてステートマシンを備える半導体集積回路を自動生成する場合、生成する半導体集積回路の取りうる状態数が増大するので、高速なデコードを行う技術が求められている。
【０００７】
本発明は、上記問題に鑑みてなされたものであり、有限状態機械の現在の状態を高速に取得する電子回路を実現するのに好適な記述処理装置、記述処理方法並びにこれらをコンピュータ上で実現するためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、本発明の第１の観点に係る記述処理装置は、受付部、分割部、生成部を備え、以下のように構成する。
まず、受付部は、状態0, 1, 2, ..., N-1からなる有限状態機械を表す記述を受け付ける。
次に、分割部は、当該状態0, 1, 2, ..., N-1をグループ0, 1, 2, ..., M-1に分割する。
さらに、分割部は、グループ0に当該状態0, 1, ..., L[0]-1を割り当て、グループ1に当該状態L[0], L[0]+1, ..., L[1]-1を割り当て、グループ2に当該状態L[1], L[1]+1, ..., L[2]-1を割り当て、...、グループM-1に当該状態L[M-2], L[M-2]+1, ..., L[M-1]-1=N-1を割り当てる。
また、生成部は、レジスタ転送レベル記述を生成する。
そして、当該レジスタ転送レベル記述は、以下のものを表す。  （ａ）現在の状態がグループ0, 1, 2, ..., M-1のいずれのグループにあるかを記憶するレジスタT及びレジスタTに記憶されうる値のそれぞれに対応付けられる信号t[0], t[1], t[2], ..., t[M-1]を出力するデコーダE。
（ｂ）現在の状態がグループ0にある場合に現在の状態が当該状態0, 1, ..., L[0]-1のいずれであるかを記憶するレジスタG[0]及びレジスタG[0]に記憶されうる値のそれぞれに対応付けられる信号s[0], s[1], ..., s[L[0]-1]]を出力するデコーダD[0]。
現在の状態がグループ1にある場合に現在の状態が当該状態L[0], L[0]+1, ..., L[1]-1のいずれであるかを記憶するレジスタG[1]及びレジスタG[1]に記憶されうる値のそれぞれに対応付けられる信号s[L[0]], s[L[0]+1], ..., s[L[1]-1]]を出力するデコーダD[1]。
現在の状態がグループ2にある場合に現在の状態が当該状態L[1], L[1]+1, ..., L[2]-1のいずれであるかを記憶するレジスタG[2]及びレジスタG[2]に記憶されうる値のそれぞれに対応付けられる信号s[L[1]], s[L[1]+1], ..., s[L[2]-1]を出力するデコーダD[2]。
現在の状態がグループM-1にある場合に現在の状態が当該状態L[M-2], L[M-2]+1, ..., L[M-1]-1=N-1のいずれであるかを記憶するレジスタG[M-1]及びレジスタG[M-1]に記憶されうる値のそれぞれに対応付けられる信号s[L[M-2]], s[L[M-2]+1], ..., s[L[M-1]-1]を出力するデコーダD[M-1]。
信号s[0], s[1], ..., s[L[0]-1]]のそれぞれと信号t[0]とから信号g[0], g[1], ..., g[L[0]-1]]を出力し、信号s[L[0]], s[L[0]+1], ..., s[L[1]-1]]のそれぞれと信号t[1]とから信号g[L[0]], g[L[0]+1], ..., g[L[1]-1]]を出力し、信号s[L[1]], s[L[1]+1], ..., s[L[2]-1]のそれぞれと信号t[2]とから信号g[L[1]], g[L[1]+1], ..., g[L[2]-1]を出力し、...、信号s[L[M-2]], s[L[M-2]+1], ..., s[L[M-1]-1]のそれぞれと信号t[M-1]とから信号g[L[M-2]], g[L[M-2]+1], ..., g[L[M-1]-1]を出力して、取りうる状態0, 1, 2, ..., N-1のそれぞれに対応付けられる信号g[0], g[1], g[2], ..., g[N-1]を出力する論理回路。
信号g[0], g[1], g[2], ..., g[N-1]に基づいて次の状態を計算し、当該次の状態が、グループ0に属する場合、レジスタTに0を記憶させ、レジスタG[0]に当該次の状態を記憶させ、グループ1に属する場合、レジスタTに1を記憶させ、レジスタG[1]に当該次の状態を記憶させ、グループ2に属する場合、レジスタTに2を記憶させ、レジスタG[2]に当該次の状態を記憶させ、...、グループM-1に属する場合、レジスタTにM-１を記憶させ、レジスタG[M-1]に当該次の状態を記憶させる遷移回路。
【０００９】
上記目的を達成するために、その他の観点に係る記述処理方法は、受付部、分割部、生成部を備える記述処理装置が実行する記述処理方法であって、受付ステップ、分割ステップ、生成ステップを備え、以下のように構成する。
すなわち、受付ステップでは、受付部が、状態0, 1, 2, ..., N-1からなる有限状態機械を表す記述を受け付ける。
そして、分割ステップでは、分割部が、当該状態0, 1, 2, ..., N-1をグループ0, 1, 2, ..., M-1に分割する。
また、分割ステップでは、分割部が、グループ0に当該状態0, 1, ..., L[0]-1を割り当て、グループ1に当該状態L[0], L[0]+1, ..., L[1]-1を割り当て、グループ2に当該状態L[1], L[1]+1, ..., L[2]-1を割り当て、...、グループM-1に当該状態L[M-2], L[M-2]+1, ..., L[M-1]-1=N-1を割り当てる。
さらに、生成ステップでは、生成部が、レジスタ転送レベル記述を生成する。
そして、当該レジスタ転送レベル記述は、以下のものを表す。  （ａ）現在の状態がグループ0, 1, 2, ..., M-1のいずれのグループにあるかを記憶するレジスタT及びレジスタTに記憶されうる値のそれぞれに対応付けられる信号t[0], t[1], t[2], ..., t[M-1]を出力するデコーダE。
（ｂ）現在の状態がグループ0にある場合に現在の状態が当該状態0, 1, ..., L[0]-1のいずれであるかを記憶するレジスタG[0]及びレジスタG[0]に記憶されうる値のそれぞれに対応付けられる信号s[0], s[1], ..., s[L[0]-1]]を出力するデコーダD[0]。
現在の状態がグループ1にある場合に現在の状態が当該状態L[0], L[0]+1, ..., L[1]-1のいずれであるかを記憶するレジスタG[1]及びレジスタG[1]に記憶されうる値のそれぞれに対応付けられる信号s[L[0]], s[L[0]+1], ..., s[L[1]-1]]を出力するデコーダD[1]。
現在の状態がグループ2にある場合に現在の状態が当該状態L[1], L[1]+1, ..., L[2]-1のいずれであるかを記憶するレジスタG[2]及びレジスタG[2]に記憶されうる値のそれぞれに対応付けられる信号s[L[1]], s[L[1]+1], ..., s[L[2]-1]を出力するデコーダD[2]。
現在の状態がグループM-1にある場合に現在の状態が当該状態L[M-2], L[M-2]+1, ..., L[M-1]-1=N-1のいずれであるかを記憶するレジスタG[M-1]及びレジスタG[M-1]に記憶されうる値のそれぞれに対応付けられる信号s[L[M-2]], s[L[M-2]+1], ..., s[L[M-1]-1]を出力するデコーダD[M-1]。
信号s[0], s[1], ..., s[L[0]-1]]のそれぞれと信号t[0]とから信号g[0], g[1], ..., g[L[0]-1]]を出力し、信号s[L[0]], s[L[0]+1], ..., s[L[1]-1]]のそれぞれと信号t[1]とから信号g[L[0]], g[L[0]+1], ..., g[L[1]-1]]を出力し、信号s[L[1]], s[L[1]+1], ..., s[L[2]-1]のそれぞれと信号t[2]とから信号g[L[1]], g[L[1]+1], ..., g[L[2]-1]を出力し、...、信号s[L[M-2]], s[L[M-2]+1], ..., s[L[M-1]-1]のそれぞれと信号t[M-1]とから信号g[L[M-2]], g[L[M-2]+1], ..., g[L[M-1]-1]を出力して、取りうる状態0, 1, 2, ..., N-1のそれぞれに対応付けられる信号g[0], g[1], g[2], ..., g[N-1]を出力する論理回路。
信号g[0], g[1], g[2], ..., g[N-1]に基づいて次の状態を計算し、当該次の状態が、グループ0に属する場合、レジスタTに0を記憶させ、レジスタG[0]に当該次の状態を記憶させ、グループ1に属する場合、レジスタTに1を記憶させ、レジスタG[1]に当該次の状態を記憶させ、グループ2に属する場合、レジスタTに2を記憶させ、レジスタG[2]に当該次の状態を記憶させ、...、グループM-1に属する場合、レジスタTにM-１を記憶させ、レジスタG[M-1]に当該次の状態を記憶させる遷移回路。
【００１０】
上記目的を達成するために、その他の観点に係るプログラムは、コンピュータを、受付部、分割部、生成部として、以下のように機能させる。
まず、受付部は、状態0, 1, 2, ..., N-1からなる有限状態機械を表す記述を受け付ける。
次に、分割部は、当該状態0, 1, 2, ..., N-1をグループ0, 1, 2, ..., M-1に分割する。
さらに、分割部は、グループ0に当該状態0, 1, ..., L[0]-1を割り当て、グループ1に当該状態L[0], L[0]+1, ..., L[1]-1を割り当て、グループ2に当該状態L[1], L[1]+1, ..., L[2]-1を割り当て、...、グループM-1に当該状態L[M-2], L[M-2]+1, ..., L[M-1]-1=N-1を割り当てる。
また、生成部は、レジスタ転送レベル記述を生成する。
そして、当該レジスタ転送レベル記述は、以下のものを表す。  （ａ）現在の状態がグループ0, 1, 2, ..., M-1のいずれのグループにあるかを記憶するレジスタT及びレジスタTに記憶されうる値のそれぞれに対応付けられる信号t[0], t[1], t[2], ..., t[M-1]を出力するデコーダE。
（ｂ）現在の状態がグループ0にある場合に現在の状態が当該状態0, 1, ..., L[0]-1のいずれであるかを記憶するレジスタG[0]及びレジスタG[0]に記憶されうる値のそれぞれに対応付けられる信号s[0], s[1], ..., s[L[0]-1]]を出力するデコーダD[0]。
現在の状態がグループ1にある場合に現在の状態が当該状態L[0], L[0]+1, ..., L[1]-1のいずれであるかを記憶するレジスタG[1]及びレジスタG[1]に記憶されうる値のそれぞれに対応付けられる信号s[L[0]], s[L[0]+1], ..., s[L[1]-1]]を出力するデコーダD[1]。
現在の状態がグループ2にある場合に現在の状態が当該状態L[1], L[1]+1, ..., L[2]-1のいずれであるかを記憶するレジスタG[2]及びレジスタG[2]に記憶されうる値のそれぞれに対応付けられる信号s[L[1]], s[L[1]+1], ..., s[L[2]-1]を出力するデコーダD[2]。
現在の状態がグループM-1にある場合に現在の状態が当該状態L[M-2], L[M-2]+1, ..., L[M-1]-1=N-1のいずれであるかを記憶するレジスタG[M-1]及びレジスタG[M-1]に記憶されうる値のそれぞれに対応付けられる信号s[L[M-2]], s[L[M-2]+1], ..., s[L[M-1]-1]を出力するデコーダD[M-1]。
信号s[0], s[1], ..., s[L[0]-1]]のそれぞれと信号t[0]とから信号g[0], g[1], ..., g[L[0]-1]]を出力し、信号s[L[0]], s[L[0]+1], ..., s[L[1]-1]]のそれぞれと信号t[1]とから信号g[L[0]], g[L[0]+1], ..., g[L[1]-1]]を出力し、信号s[L[1]], s[L[1]+1], ..., s[L[2]-1]のそれぞれと信号t[2]とから信号g[L[1]], g[L[1]+1], ..., g[L[2]-1]を出力し、...、信号s[L[M-2]], s[L[M-2]+1], ..., s[L[M-1]-1]のそれぞれと信号t[M-1]とから信号g[L[M-2]], g[L[M-2]+1], ..., g[L[M-1]-1]を出力して、取りうる状態0, 1, 2, ..., N-1のそれぞれに対応付けられる信号g[0], g[1], g[2], ..., g[N-1]を出力する論理回路。
信号g[0], g[1], g[2], ..., g[N-1]に基づいて次の状態を計算し、当該次の状態が、グループ0に属する場合、レジスタTに0を記憶させ、レジスタG[0]に当該次の状態を記憶させ、グループ1に属する場合、レジスタTに1を記憶させ、レジスタG[1]に当該次の状態を記憶させ、グループ2に属する場合、レジスタTに2を記憶させ、レジスタG[2]に当該次の状態を記憶させ、...、グループM-1に属する場合、レジスタTにM-１を記憶させ、レジスタG[M-1]に当該次の状態を記憶させる遷移回路。
【発明の効果】
【００１１】
本発明によれば、有限状態機械の現在の状態を高速に取得する電子回路を実現するのに好適な記述処理装置、記述処理方法並びにこれらをコンピュータ上で実現するためのプログラムを提供することができる。
【発明を実施するための最良の形態】
【００１２】
以下、図面を参照して、本実施形態に係る記述処理装置について説明する。
【００１３】
まず、図１を参照して、本実施形態に係る記述処理装置１００の構成について説明する。記述処理装置１００は、状態0, 1, 2, ..., N-1からなる有限状態機械を表す記述に基づいて、半導体集積回路の構成、配置、配線を記述するＲＴＬ（Ｒｅｇｉｓｔｅｒ  Ｔｒａｎｓｆｅｒ  Ｌｅｖｅｌ（レジスタ転送レベル））記述を生成する装置である。
【００１４】
状態0, 1, 2, ..., N-1からなる有限状態機械を表す記述は、例えば、入力ポートや変数のビット幅等のＨ／Ｗ化に必要な情報を含んだ動作レベル記述、動作レベル記述からＲＴＬ記述を得るための中間記述、或いは、ＲＴＬ記述そのものである。また、記述処理装置１００は、有限状態機械の現在の状態を高速に取得する電子回路を表すＲＴＬ記述を生成する。
【００１５】
図１に示すように、記述処理装置１００は、物理的には、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１１と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１２と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１３と、ハードディスク装置１４と、入力装置１５と、表示装置１６と、出力装置１７と、を備える。記述処理装置１００が備える各構成要素はバスを介して接続される。
【００１６】
ＣＰＵ１１は、ハードディスク装置１４に記憶されたプログラムに従って記述処理装置１００全体の動作を制御する。ＣＰＵ１１は、各構成要素とバスを介して接続され制御信号やデータのやりとりをする。
【００１７】
ＲＯＭ１２は、電源投入直後に実行されるＩＰＬ（Ｉｎｉｔｉａｌ  Ｐｒｏｇｒａｍ  Ｌｏａｄｅｒ）を記憶する。ＩＰＬが実行された後、ＣＰＵ１１は、ハードディスク装置１４に記憶されたプログラムをＲＡＭ１３に読み出して実行する。
【００１８】
ＲＡＭ１３は、データやプログラムを一時的に記憶する。ＲＡＭ１３は、ハードディスク装置１４から読み出されたプログラムや、動作合成処理に必要なデータ等を一時記憶する。
【００１９】
ハードディスク装置１４は、ＣＰＵ１１により実行されるプログラムを記憶する。また、ハードディスク装置１４は、動作合成すべき動作レベル記述や、動作合成により得られたＲＴＬ記述等を記憶する。
【００２０】
入力装置１５は、ＣＰＵ１１による制御のもと、動作合成に必要なパラメータ等の入力をユーザから受け付け、また、動作合成開始要求等の要求をユーザから受け付ける。入力装置１５は、例えば、キーボードやマウスから構成される。
【００２１】
表示装置１６は、ＣＰＵ１１による制御のもと、ユーザからのパラメータ等の入力や動作合成開始要求等の要求を受け付けるための画面、動作レベル記述を表示するための画面、ＲＴＬ記述を表示するための画面等を表示する。表示装置１６は、例えば、液晶ディスプレイ装置から構成される。
【００２２】
出力装置１７は、ＣＰＵ１１による制御のもと、動作合成により得られたＲＴＬ記述等を出力する。出力装置１７は、例えば、ＵＳＢポート等の汎用の通信インターフェースや、ディジタル出力ポート等から構成される。
【００２３】
次に、本実施形態に係る記述処理装置１００の基本構成について説明する。
【００２４】
図２は、本実施形態に係る記述処理装置１００の基本構成を示すブロック図である。図２に示すように、記述処理装置１００は、機能的には、受付部２０と、分割部３０と、生成部４０と、を備える。
【００２５】
受付部２０は、状態0, 1, 2, ..., N-1からなる有限状態機械を表す記述を受け付ける。なお、Nは有限状態機械が取りうる状態の数であり、２以上の整数である。受付部２０は、ＣＰＵ１１が、ＲＯＭ１２、ＲＡＭ１３及び入力装置１５と協働することにより実現される。
【００２６】
なお、状態0, 1, 2, ..., N-1の番号の付け方は任意である。従って、受け付けた記述における状態の番号を適宜入れ替えるなどしてもよいし、状態の情報を受け付けた順に番号を振ることとしても良い。
【００２７】
分割部３０は、状態0, 1, 2, ..., N-1をグループ0, 1, 2, ..., M-1に分割する。具体的には、分割部３０は、グループ0に当該状態0, 1, ..., L[0]-1を割り当て、グループ1に当該状態L[0], L[0]+1, ..., L[1]-1を割り当て、グループ2に当該状態L[1], L[1]+1, ..., L[2]-1を割り当て、...、グループM-1に当該状態L[M-2], L[M-2]+1, ..., L[M-1]-1=N-1を割り当てる。
【００２８】
なお、Mは何グループに分割するかを示す数、すなわち、グループ数であり、２以上の整数である。分割部３０は、ＣＰＵ１１が、ＲＯＭ１２及びＲＡＭ１３と協働することにより実現される。
【００２９】
上記のように、状態番号は、任意の順序とすることが可能であるから、状態の分割に特段の制限はない。従来の有限状態機械の分割においては、遷移の切断数を小さくすることが必要とされていたが、本実施形態においては、このような制限はない。従って、グループの構成の自由度が高い点が従来の技術と異なる。
【００３０】
生成部４０は、以下の構成要素を表すＲＴＬ記述を生成する。
すなわち、生成部４０は、現在の状態がグループ0, 1, 2, ..., M-1のいずれのグループにあるかを記憶するレジスタT及びレジスタTに記憶されうる値のそれぞれに対応付けられる信号t[0], t[1], t[2], ..., t[M-1]を出力するデコーダEを表すＲＴＬ記述を生成する。
【００３１】
また、生成部４０は、現在の状態が、現在の状態が属するグループの取りうる状態のうちいずれの状態にあるかを記憶するレジスタと、当該レジスタに記憶されうる値のそれぞれに対応付けられる信号を出力するデコーダとをグループ毎に表すＲＴＬ記述を生成する。
【００３２】
具体的には、生成部４０は、現在の状態がグループ0にある場合に現在の状態が当該状態0, 1, ..., L[0]-1のいずれであるかを記憶するレジスタG[0]及びレジスタG[0]に記憶されうる値のそれぞれに対応付けられる信号s[0], s[1], ..., s[L[0]-1]]を出力するデコーダD[0]を表すＲＴＬ記述を生成する。
【００３３】
また、生成部４０は、現在の状態がグループ1にある場合に現在の状態が当該状態L[0], L[0]+1, ..., L[1]-1のいずれであるかを記憶するレジスタG[1]及びレジスタG[1]に記憶されうる値のそれぞれに対応付けられる信号s[L[0]], s[L[0]+1], ..., s[L[1]-1]]を出力するデコーダD[1]を表すＲＴＬ記述を生成する。
【００３４】
また、生成部４０は、現在の状態がグループ2にある場合に現在の状態が当該状態L[1], L[1]+1, ..., L[2]-1のいずれであるかを記憶するレジスタG[2]及びレジスタG[2]に記憶されうる値のそれぞれに対応付けられる信号s[L[1]], s[L[1]+1], ..., s[L[2]-1]を出力するデコーダD[2]を表すＲＴＬ記述を生成する。
【００３５】
同様に、論理回路は、グループ3〜M-2のそれぞれに対応するレジスタとデコーダとを表すＲＴＬ記述を生成する。
【００３６】
そして、生成部４０は、現在の状態がグループM-1にある場合に現在の状態が当該状態L[M-2], L[M-2]+1, ..., L[M-1]-1=N-1のいずれであるかを記憶するレジスタG[M-1]及びレジスタG[M-1]に記憶されうる値のそれぞれに対応付けられる信号s[L[M-2]], s[L[M-2]+1], ..., s[L[M-1]-1]を出力するデコーダD[M-1]を表すＲＴＬ記述を生成する。
【００３７】
また、生成部４０は、信号s[0], s[1], ..., s[L[0]-1]]のそれぞれと信号t[0]とから信号g[0], g[1], ..., g[L[0]-1]]を出力し、信号s[L[0]], s[L[0]+1], ..., s[L[1]-1]]のそれぞれと信号t[1]とから信号g[L[0]], g[L[0]+1], ..., g[L[1]-1]]を出力し、信号s[L[1]], s[L[1]+1], ..., s[L[2]-1]のそれぞれと信号t[2]とから信号g[L[1]], g[L[1]+1], ..., g[L[2]-1]を出力し、グループ3〜M-2のそれぞれに対応するデコーダから出力される信号に対応する信号を出力し、信号s[L[M-2]], s[L[M-2]+1], ..., s[L[M-1]-1]のそれぞれと信号t[M-1]とから信号g[L[M-2]], g[L[M-2]+1], ..., g[L[M-1]-1]を出力して、取りうる状態0, 1, 2, ..., N-1のそれぞれに対応付けられる信号g[0], g[1], g[2], ..., g[N-1]を出力する論理回路を表すＲＴＬ記述を生成する。
【００３８】
また、生成部４０は、信号g[0], g[1], g[2], ..., g[N-1]に基づいて次の状態を計算し、当該次の状態が、グループ0に属する場合、レジスタTに0を記憶させ、レジスタG[0]に当該次の状態を記憶させ、グループ1に属する場合、レジスタTに1を記憶させ、レジスタG[1]に当該次の状態を記憶させ、グループ2に属する場合、レジスタTに2を記憶させ、レジスタG[2]に当該次の状態を記憶させ、グループ3〜M-2に属する場合も、それぞれに対応するレジスタに対応する値を記憶させ、グループM-1に属する場合、レジスタTにM-１を記憶させ、レジスタG[M-1]に当該次の状態を記憶させる遷移回路を表すＲＴＬ記述を生成する。
なお、生成部４０は、ＣＰＵ１１が、ＲＯＭ１２及びＲＡＭ１３と協働することにより実現される。
【００３９】
次に、本実施形態に係る記述処理装置１００が実行する記述処理について図３及び図４を参照して詳細に説明する。なお、記述処理装置１００は、動作合成の処理中に記述処理を実行するものとして説明する。
【００４０】
図３は、記述処理装置１００が実行する動作合成処理の一例を示すフローチャートである。また、図４は、記述処理装置１００が出力するＲＴＬ記述により表現される有限状態機械を説明するための図である。なお、有限状態機械は、計算部２１０と更新部２２０とから構成される遷移回路２００と、レジスタ４０１〜４１６と、デコーダ５０１〜５１６と、ＡＮＤゲート６００〜６６３と、レジスタ４５０と、デコーダ５５０と、を備える。有限状態機械が備える各構成要素の詳細については後述する。
【００４１】
記述処理装置１００は、例えば、動作合成の開始要求を入力装置１５を介してユーザから受けると、図３のフローチャートに示す動作合成処理を開始する。なお、図３には、記述処理装置１００が実行する動作合成処理のうち有限状態機械を表現する記述を動作合成する処理についてのみ示す。
【００４２】
まず、記述処理装置１００は、初期化を実行する（ステップＳ１０１）。記述処理装置１００は、ＲＡＭ１３に記憶された動作合成処理で使用する変数を初期化する。
【００４３】
そして、受付部２０は、ユーザから動作合成対象の動作レベル記述を受け付ける（ステップＳ１０２）。具体的には、受付部２０は、ユーザから状態0, 1, 2, ..., N-1からなる有限状態機械を表す動作レベル記述の指定を受け付け、ユーザから指定された動作レベル記述をハードディスク装置１４から読み出してＲＡＭ１３に記憶する。
【００４４】
次に、分割部３０は、ユーザから受け付けた動作レベル記述により表現される有限状態機械の取りうる状態0, 1, 2, ..., N-1をグループ0, 1, 2, ..., M-1に分割する（ステップＳ１０３）。より詳細には、分割部３０は、グループ0に当該状態0, 1, ..., L[0]-1を割り当て、グループ1に当該状態L[0], L[0]+1, ..., L[1]-1を割り当て、グループ2に当該状態L[1], L[1]+1, ..., L[2]-1を割り当てる。
【００４５】
同様に、分割部３０は、グループ3〜M-2についても状態を割り当てる。そして、分割部３０は、グループM-1に当該状態L[M-2], L[M-2]+1, ..., L[M-1]-1=N-1を割り当てる。
【００４６】
分割部３０は、各グループに属する状態の数がなるべく同じになるように、N個の状態をM個のグループに分割する（区分けする）。ここで、NがMで割り切れない場合は、各グループに属する状態の数を全て同じ数にすることはできない。この場合、分割部３０は、NをMで除算した結果の整数部の値、若しくは当該整数部の値に1を加算した値が各グループに属する状態の数となるように分割する。
【００４７】
また、分割部３０は、生成する回路の、サイズ（面積）、動作時の処理速度、或いは取りうる状態の数等を考慮してMを決定する。例えば、分割部３０は、生成する回路のサイズに余裕があると判別した場合にMを大きくし、余裕がないと判別した場合にMを小さくする。また、分割部３０は、生成する回路の動作時の処理速度を極めて速くする必要があると判別した場合はMを大きくし、そこまで速くする必要はないと判別した場合はMを小さくする。また、分割部３０は、生成する回路の取りうる状態の数が多いと判別した場合はMを大きくし、それほど多くないと判別した場合はMを小さくする。
【００４８】
図４に、有限状態機械の取りうる６４個の状態（N=64）を１６個のグループに分割（M=16）した場合の例を示す。この場合、各グループに属する状態の数はいずれも４である。従って、各グループに対応して生成されるデコーダは４個の状態から現在の状態を判別すれば良い。
【００４９】
比較例として、図５に、有限状態機械の取りうる６４個の状態（N=64）をグループ分けせずに、１つのレジスタと１つのデコーダとから有限状態機械を構成した場合の例を示す。図５に示す例では、レジスタ４００は６４個の状態を６ビットで記憶し、デコーダ５００はレジスタ４００に記憶された６ビットの値に基づいて、６４個の状態から現在の状態を判別しなければならない。
【００５０】
上述のように有限状態機械の取りうる状態を複数のグループに分割した場合、各グループに対応して生成されるデコーダは比較的少数の状態から現在の状態を判別すれば良い。このため、デコーダを１つだけ生成して多数の状態から現在の状態を判別する場合に比べデコード時間の大幅な短縮が期待できる。
【００５１】
次に、生成部４０は、現在の状態がグループ0, 1, 2, ..., M-1のいずれのグループにあるかを記憶するレジスタT（以下、レジスタ４５０とする。）を表現する記述を生成する（ステップＳ１０４）。以下、理解を容易にするため、レジスタ４５０を表現する記述を生成することを、単に、レジスタ４５０を生成すると記載する。同様に、デコーダE、レジスタG、デコーダD、ＡＮＤゲート、計算部２１０及び更新部２２０を表現する記述を生成することも、単に、デコーダE、レジスタG、デコーダD、ＡＮＤゲート、計算部２１０及び更新部２２０を生成すると記載する。
【００５２】
そして、生成部４０は、レジスタ４５０に記憶されうる値のそれぞれに対応付けられる信号t[0], t[1], t[2], ..., t[M-1]を出力するデコーダE（以下、デコーダ５５０とする。）を生成する（ステップＳ１０５）。図４を参照して、レジスタ４５０とデコーダ５５０について具体的に説明する。
【００５３】
レジスタ４５０は、現在の状態が、グループ0, 1, 2, ..., M-1のいずれのグループに属するかを示す値を記憶する。図４に示す例では、グループは１６のグループ（グループ0〜15）に分割されているため、レジスタ４５０は、0〜15のうちいずれかの値を記憶する。レジスタ４５０は、例えば、４ビットのバイナリデータを記憶するＳＲＡＭから構成される。なお、レジスタ４５０とデコーダ５５０とは、例えば、４ビットのデータ線で接続される。
【００５４】
また、図４に示す例では、デコーダ５５０は、レジスタ４５０に記憶された0〜15のうちいずれかの値に対応付けられた信号（信号t[0]〜t[15]のいずれかの信号）を当該信号に対応付けられた信号線から出力する。例えば、レジスタ４５０に記憶された値が「０」である場合、信号t[0]に対応付けられた信号線の信号レベルを「Ｈレベル」に設定し、信号t[1]〜t[15]のそれぞれに対応付けられた信号線の信号レベルを全て「Ｌレベル」に設定する。そして、例えば、レジスタ４５０に記憶された値が「１」である場合、信号t[1]に対応付けられた信号線の信号レベルを「Ｈレベル」に設定し、信号t[0]及び信号t[2]〜t[15]のそれぞれに対応付けられた信号線の信号レベルを全て「Ｌレベル」に設定する。
【００５５】
次に、生成部４０は、現在の状態が、現在の状態が属するグループの取りうる状態のうちいずれの状態にあるかを記憶するレジスタGをグループの数分（M個）生成する（ステップＳ１０６）。以下、グループ0〜M-1に対応付けてそれぞれ生成したレジスタGを、レジスタ４０１〜４１６とする。
【００５６】
また、生成部４０は、レジスタGに記憶されうる値のそれぞれに対応付けられる信号を出力するデコーダDをグループの数分（M個）生成する（ステップＳ１０７）。以下、グループ0〜M-1に対応付けてそれぞれ生成したデコーダDを、デコーダ５０１〜５１６とする。
【００５７】
また、生成部４０は、デコーダ５０１〜５１６のいずれかのデコーダから出力された信号のうちいずれかの信号レベルと、デコーダ５５０から出力された信号のうちいずれかの信号レベルとの論理積をとるＡＮＤゲートを、有限状態機械のとりうる状態の数分（N個）生成する（ステップＳ１０８）。以下、状態0〜N-1に対応付けてそれぞれ生成したＡＮＤゲートを、ＡＮＤゲート６０１〜６６３とする。
【００５８】
以下、図４を参照して、レジスタ４０１〜４１６、デコーダ５０１〜５１６及びＡＮＤゲート６０１〜６６３について具体的に説明する。まず、グループ0に対応して生成される、レジスタ４０１とデコーダ５０１とＡＮＤゲート６００〜６０３とについて説明する。
【００５９】
レジスタ４０１は、現在の状態がグループ0に有る場合（すなわち、現在の状態が状態0〜3のいずれかである場合）に、現在の状態が状態0〜3のいずれであるかを0〜3のいずれかの値として記憶する。レジスタ４０１は、例えば、２ビットのバイナリデータを記憶するＳＲＡＭから構成される。なお、レジスタ４０１とデコーダ５０１とは、例えば、４ビットのデータ線で接続される。
【００６０】
デコーダ５０１は、レジスタ４０１に記憶された0〜3のうちいずれかの値に対応付けられた信号（信号s[0]〜s[3]のいずれか）を当該信号に対応付けられた信号線から出力する。例えば、レジスタ４０１に記憶された値が「０」である場合、信号s[0]に対応付けられた信号線の信号レベルを「Ｈレベル」に設定し、信号s[1]〜s[3]のそれぞれに対応付けられた信号線の信号レベルを全て「Ｌレベル」に設定する。そして、例えば、レジスタ４０１に記憶された値が「１」である場合、信号s[1]に対応付けられた信号線の信号レベルを「Ｈレベル」に設定し、信号s[0]、s[2]及びs[3]のそれぞれに対応付けられた信号線の信号レベルを全て「Ｌレベル」に設定する。
【００６１】
ＡＮＤゲート６００は、デコーダ５０１から供給された信号s[0]の信号レベルとデコーダ５５０から供給された信号t[0]の信号レベルとの論理積をとる。そして、ＡＮＤゲート６００は、信号g[0]に対応付けられた信号線の信号レベルを、求めた論理積により示される信号レベルに設定する。例えば、信号s[0]の信号レベルが「Ｈレベル」で、且つ、信号t[0]の信号レベルが「Ｈレベル」の場合のみ信号g[0]に対応付けられた信号線の信号レベルを「Ｈレベル」に設定する。そして、例えば、信号s[0]の信号レベルと信号t[0]の信号レベルとのうちいずれか一方の信号レベルが「Ｌレベル」の場合には、信号g[0]に対応付けられた信号線の信号レベルを「Ｌレベル」に設定する。
【００６２】
ＡＮＤゲート６００と同様に、ＡＮＤゲート６０１〜６０３は、デコーダ５０１から供給された信号s[1]〜s[3]のそれぞれの信号レベルとデコーダ５５０から供給された信号t[0]の信号レベルとの論理積をとる。そして、ＡＮＤゲート６０１〜６０３は、信号g[1]〜g[3]のそれぞれに対応付けられた信号線の信号レベルを、それぞれ求めた論理積により示される信号レベルに設定する。
【００６３】
次に、グループ1に対応して生成される、レジスタ４０２とデコーダ５０２とＡＮＤゲート６０４〜６０７とについて説明する。
【００６４】
レジスタ４０２は、現在の状態がグループ1に有る場合（すなわち、現在の状態が状態4〜7のいずれかである場合）に、現在の状態が状態4〜7のいずれであるかを0〜3のいずれかの値として記憶する。レジスタ４０１は、例えば、２ビットのバイナリデータを記憶するＳＲＡＭから構成される。なお、レジスタ４０２とデコーダ５０２とは、例えば、４ビットのデータ線で接続される。
【００６５】
デコーダ５０２は、レジスタ４０２に記憶された0〜3のうちいずれかの値に対応付けられた信号（信号s[4]〜s[7]のいずれかの信号）を当該信号に対応付けられた信号線から出力する。例えば、レジスタ４０２に記憶された値が「０」である場合、信号s[4]に対応付けられた信号線の信号レベルを「Ｈレベル」に設定し、信号s[5]〜s[7]のそれぞれに対応付けられた信号線の信号レベルを全て「Ｌレベル」に設定する。そして、例えば、レジスタ４０２に記憶された値が「１」である場合、信号s[5]に対応付けられた信号線の信号レベルを「Ｈレベル」に設定し、信号s[4]、s[6]及びs[7]のそれぞれに対応付けられた信号線の信号レベルを全て「Ｌレベル」に設定する。
【００６６】
ＡＮＤゲート６０４は、デコーダ５０２から供給された信号s[4]の信号レベルとデコーダ５５０から供給された信号t[1]の信号レベルとの論理積をとる。そして、ＡＮＤゲート６０４は、信号g[4]に対応付けられた信号線の信号レベルを、求めた論理積により示される信号レベルに設定する。例えば、信号s[4]の信号レベルが「Ｈレベル」で、且つ、信号t[1]の信号レベルが「Ｈレベル」の場合のみ信号g[4]に対応付けられた信号線の信号レベルを「Ｈレベル」に設定する。そして、例えば、信号s[5]の信号レベルと信号t[1]の信号レベルとのうちいずれか一方の信号レベルが「Ｌレベル」の場合には、信号g[5]に対応付けられた信号線の信号レベルを「Ｌレベル」に設定する。
【００６７】
ＡＮＤゲート６０４と同様に、ＡＮＤゲート６０５〜６０７は、デコーダ５０２から供給された信号s[5]〜s[7]のそれぞれの信号レベルとデコーダ５５０から供給された信号t[1]の信号レベルとの論理積をとる。そして、ＡＮＤゲート６０５〜６０７は、信号g[5]〜g[7]のそれぞれに対応付けられた信号線の信号レベルを、それぞれ求めた論理積により示される信号レベルに設定する。
【００６８】
グループ２〜１５に対応してそれぞれ生成される、レジスタ４０３〜４１６とデコーダ５０３〜５１６とＡＮＤゲート６０８〜６６３とについても同様である。
【００６９】
次に、生成部４０は、信号g[0]〜g[N-1]に基づいて次の状態を計算する計算部２１０を生成する（ステップＳ１０９）。計算部２１０は、信号g[0]〜g[N-1]から現在の状態を求める。具体的には、計算部２１０は、信号g[0]〜g[N-1]のうち信号レベルが「Ｈレベル」であると判別した信号に対応付けられた状態を現在の状態として求める。
【００７０】
また、計算部２１０は、現在の状態を次の状態に変化させることを指示する状態更新指示信号に応答して、次の状態を計算する。状態更新指示信号は、状態の更新のタイミングを指示する信号であり、例えば、クロック信号などに相当するものである。なお、現在の状態とユーザの指示入力や時間の経過等とに基づいて次の状態を決める場合には、ユーザの指示入力や現在の時刻などの情報を状態更新指示信号の一部として与えても良い。状態更新指示信号が状態の更新のタイミングのみを指示する信号である場合、計算部２１０は、現在の状態からあらかじめ定められた次の状態を求める。
【００７１】
次に、生成部４０は、次の状態が属するグループを示す値をレジスタ４５０に記憶させ、レジスタ４０１〜４１６のうち次の状態が属するグループに対応付けられたレジスタに次の状態を示す値を記憶させる更新部２２０を生成する（ステップＳ１１０）。
【００７２】
以下、図４を参照して、計算部２１０と更新部２２０について具体例を示して説明する。まず、計算部２１０に供給される状態更新指示信号が状態の更新のタイミングのみを指示する信号である場合について説明する。
【００７３】
計算部２１０は、状態更新指示信号に応答して、信号g[0]〜g[63]の全ての信号レベルを判別する。計算部２１０は、例えば、信号g[3]の信号レベルが「Ｈレベル」で他の信号の信号レベルが全て「Ｌレベル」であると判別すると、現在の状態は状態3であることを認識する。そして、計算部２１０は、現在の状態を一つ進めた状態として状態4を求め、状態4を次の状態に設定する。
【００７４】
更新部２１０は、計算部２１０から次の状態が状態4であることを示す信号を供給されることに応答して、状態4が属するグループを求める。更新部２１０は、状態4が属するグループがグループ1であると判別すると、レジスタ４５０にグループ1であることを示す値として1を記憶させる。また、更新部２１０は、グループ1に対応付けられたレジスタ４０２に状態4であることを示す値として０を記憶させる。このように更新部２１０は、次の状態の番号と当該グループに属する状態の中で最も番号が小さい状態の番号との差分をレジスタに記憶させる。
【００７５】
次に、計算部２１０に供給される状態更新指示信号が状態の更新のタイミングに加え、次の状態を直接を指示する信号である場合について説明する。
【００７６】
計算部２１０は、状態更新指示信号に応答して、状態更新指示信号により指示される次の状態を認識する。例えば、計算部２１０は、状態更新指示信号により次の状態として状態5を指示されると、信号g[0]〜g[63]の信号レベルにかかわらず次の状態として状態5を設定する。
【００７７】
更新部２２０は、計算部２１０から次の状態が状態5であることを示す信号を供給されることに応答して、状態5が属するグループを求める。更新部２２０は、状態5が属するグループがグループ1であると判別すると、レジスタ４５０にグループ1であることを示す値として1を記憶させる。また、更新部２２０は、グループ1に対応付けられたレジスタ４０２に状態5であることを示す値として１を記憶させる。
【００７８】
生成部４０が更新部２２０を生成すると動作合成処理が完了する。
【００７９】
本実施形態に係る記述処理装置１００によれば、有限状態機械が取りうるN個の状態をM個のグループに分割し、グループ毎にデコーダを生成し、グループ毎にデコードする。このため、デコーダを１つだけ生成し全ての状態を１つのデコーダでデコードする場合に比べ、１つのデコーダで判別しなければならない状態の数を減らすことができる。従って、有限状態機械がデコードにかける時間を減らすことができる。
【００８０】
また、分割部３０は、NをMで除算した結果の整数部の値、若しくは当該整数部の値に1を加算した値が各グループに属する状態の数となるように分割する。このため、各グループに属する状態の数は、最大でも１しか異ならない。従って、各グループにおいて、デコードにかかる時間を揃えることができる。
【００８１】
なお、上記実施形態では、受付部２０は、動作レベル記述を受け付けたが、動作レベル記述からＲＴＬ記述を生成する過程で得られる中間記述等を受け付けてもよい。受け付けた中間記述が、１つのレジスタと１つのデコーダにより有限状態機械が構成されている記述である場合、当該１つのレジスタと当該１つのデコーダとをそれぞれ複数のレジスタと複数のデコーダとに分割してＲＴＬ記述を生成する。
【００８２】
上記実施形態では、プログラムが、記憶装置に予め記憶されているものとして説明した。しかし、記述処理装置を、装置の全部又は一部として動作させ、あるいは、上述の処理を実行させるためのプログラムを、フレキシブルディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅａｄ−Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）、ＭＯ（Ｍａｇｎｅｔｏ  Ｏｐｔｉｃａｌ  Ｄｉｓｋ）などのコンピュータ読み取り可能な記録媒体に格納して配布し、これを別のコンピュータにインストールし、上述の手段として動作させ、あるいは、上述の工程を実行させてもよい。
【００８３】
さらに、インターネット上のサーバ装置が有するディスク装置等にプログラムを格納しておき、例えば、搬送波に重畳させて、コンピュータにダウンロード等してプログラムを実行してもよい。
【００８４】
上述のように、本発明によれば、有限状態機械の現在の状態を高速に取得する電子回路を実現するのに好適な記述処理装置、記述処理方法並びにこれらをコンピュータ上で実現するためのプログラムを提供することができる。
【図面の簡単な説明】
【００８５】
【図１】本発明の実施形態に係る記述処理装置の構成を示すブロック図である。
【図２】記述処理装置の基本構成を示すブロック図である。
【図３】動作合成処理を示すフローチャートである。
【図４】本発明の実施形態に係る記述処理装置が出力するＲＴＬ記述により表現される有限状態機械を説明するための図である。
【図５】取りうる状態を複数のグループに分割しない場合の有限状態機械を説明するための図である。
【符号の説明】
【００８６】
１１  ＣＰＵ
１２  ＲＯＭ
１３  ＲＡＭ
１４  ハードディスク装置
１５  入力装置
１６  表示装置
１７  出力装置
２０  受付部
３０  分割部
４０  生成部
１００  記述処理装置
２００  遷移回路
２１０  計算部
２２０  更新部
４０１〜４１６、４５０  レジスタ
５０１〜５１６、５５０  デコーダ
６００〜６６３  ＡＮＤゲート
【図１】
0005206063.tif 000002
【図２】
0005206063.tif 000003
【図３】
0005206063.tif 000004
【図４】
0005206063.tif 000005
【図５】
0005206063.tif 000006