(57)【特許請求の範囲】
【請求項１】
逐次読み出しを繰り返し行うことが可能なメモリ、前記メモリから読み出した内容に応じて定まる内容を設定可能な状態記憶手段、状態遷移回路が次の条件に遷移する遷移条件を設定可能な遷移条件記憶手段から構成され、
前記状態記憶手段は前記メモリから読み出した内容と前記状態記憶手段の設定内容とが所定条件を満足するまで順次前記メモリから読み出す機能を有し、
前記遷移条件記憶手段は遷移条件が設定されると、前記メモリからの読み出しと前記遷移条件記憶手段の設定内容の更新とを繰り返し、前記遷移条件記憶手段の設定内容が所定値となった時点で前記状態記憶手段に前記メモリから読み出した内容に応じて定まる内容を設定させる機能を有する、
ことを特徴とする状態遷移回路。
【請求項２】
逐次読み出しを繰り返し行うことが可能なメモリ、前記メモリから読み出した内容に応じて定まる内容を設定可能な状態記憶手段、状態遷移回路が次の条件に遷移する遷移条件を設定するとともに前記メモリからの逐次読み出し毎にその内容を更新する遷移条件記憶手段で構成される状態遷移回路の制御方法であって、
前記メモリから読み出した内容と前記状態記憶手段の設定内容とが所定条件を満足するまで順次前記メモリの内容を読み出し、
前記遷移条件記憶手段に遷移条件が設定されると、前記メモリからの読み出しと前記遷移条件記憶手段の設定内容の更新とを繰り返し、前記遷移条件記憶手段の設定内容が所定値となった時点で前記メモリから読み出した内容に応じて定まる内容を前記状態記憶手段に設定する、
ことを特徴とする状態遷移回路の制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、現在の状態と外部入力される遷移条件とに基づき次の状態を選択して設定する状態遷移回路（順序回路）およびその制御方法に係り、特に複数のセルで構成され各セルがメモリまたは論理回路として利用可能なハードウェア上に構成するのに好適な状態遷移回路およびその制御方法に関するものである。
【０００２】
【従来の技術】
第４図に示すように従来の状態遷移回路は、状態を記憶する複数のフリップフロップ（ＦＦ）１と、それらフリップフロップ１に格納された内容と外部から与えられた状態遷移条件を入力とする組み合わせ回路２とで構成されている。そして組み合わせ回路２の出力がフリップフロップ１に設定されることで、フリップフロップ１に次の状態が設定されることになる。
【０００３】
【発明が解決しようとする課題】
ところが、このような状態遷移回路の構成方法では、状態を遷移させる条件が複雑になると組み合わせ回路２が急激に増加するという欠点がある。特に近年広く利用されるようになったＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）では、組み合わせ回路をセルと呼ばれる小規模メモリの接続によって実現するが、小規模メモリ間の接続が複雑になると回路を割り当てるために必要となるセルが増加するとともにその動作も低速になる欠点がある。
【０００４】
本発明はこのような点に鑑みてなされたもので、その目的は、遷移させる条件が複雑な場合でも組み合わせ回路が複雑とならないようにした状態遷移回路およびその制御方法を提供することである。
【０００５】
【課題を解決するための手段】
この目的を達成するに第１の発明の状態遷移回路は、逐次読み出しを繰り返し行うことが可能なメモリ、前記メモリから読み出した内容に応じて定まる内容を設定可能な状態記憶手段、状態遷移回路が次の条件に遷移する遷移条件を設定可能な遷移条件記憶手段から構成され、前記状態記憶手段は前記メモリから読み出した内容と前記状態記憶手段の設定内容とが所定条件を満足するまで順次前記メモリから読み出す機能を有し、前記遷移条件記憶手段は遷移条件が設定されると、前記メモリからの読み出しと前記遷移条件記憶手段の設定内容の更新とを繰り返し、前記遷移条件記憶手段の設定内容が所定値となった時点で前記状態記憶手段に前記メモリから読み出した内容に応じて定まる内容を設定させる機能を有するよう構成した。
【０００６】
第２の発明は、逐次読み出しを繰り返し行うことが可能なメモリ、前記メモリから読み出した内容に応じて定まる内容を設定可能な状態記憶手段、状態遷移回路が次の条件に遷移する遷移条件を設定するとともに前記メモリからの逐次読み出し毎にその内容を更新する遷移条件記憶手段で構成される状態遷移回路の制御方法であって、前記メモリから読み出した内容と前記状態記憶手段の設定内容とが所定条件を満足するまで順次前記メモリの内容を読み出し、前記遷移条件記憶手段に遷移条件が設定されると、前記メモリからの読み出しと前記遷移条件記憶手段の設定内容の更新とを繰り返し、前記遷移条件記憶手段の設定内容が所定値となった時点で前記メモリから読み出した内容に応じて定まる内容を前記状態記憶手段に設定するよう構成した。
【０００７】
【発明の実施の形態】
本発明では、状態遷移の条件を逐次読み出しを繰り返し行うことが可能なメモリに格納し、現在の状態と外部から入力される遷移条件とから該メモリ内に格納されている次の状態を選択することで、遷移させる条件が複雑な場合でも組み合わせ回路が複雑とならないようにした状態遷移回路を実現する。
【０００８】
図１は本発明の状態遷移回路の１つの実施形態のブロック図である。１０はメモリであり、格納されているデータを固定長のビット幅（ワード）で逐次読み出す逐次読み出しメモリ１０１と、その逐次読み出しメモリ１０１に対して読み出しの指示および格納されている最後のワードを読み出した場合には最初からの読み出しを指示するメモリ制御部１０２とで構成される。
【０００９】
２０は遷移条件記憶手段であり、入力信号の値を設定する遷移レジスタ２０１と、その遷移レジスタ２０１の内容を読み出すとともに次の値をその遷移レジスタ２０１に設定する遷移条件判定部２０２とで構成される。
【００１０】
３０は状態記憶手段であり、状態遷移回路の状態が設定される状態レジスタ３０１と、メモリ１０から読み出した内容を監視するとともにその内容を状態レジスタ３０１に設定することを指示する状態制御部３０２とから構成される。
【００１１】
第２図は状態遷移回路の現状態と各状態に対して入力信号が与えられた時に何れの状態に遷移するかを定義する状態遷移の例を示す図である。この例では３ビットで定義される７つの状態が存在し、入力信号は４ビットで与えられる。
【００１２】
第３図は第２図に示した状態遷移を本発明で実現するために第１図の逐次読み出しメモリ１０１に格納するデータ内容の一例である。逐次読み出しメモリ１０１は、メモリ制御部１０２の指示により４ビット単位（ワード）で内部に格納されている第３図のデータを読み出す。
【００１３】
第３図において、４ビットで構成されるワードの先頭ビットはフラグであり、残りの３ビットは状態を示している。先頭ビットが「１」のワードは以下の３ビットで現在の状態を示し、先頭ビットが「０」のワードは以下の３ビットで次に遷移する状態を示す。先頭ビットが「１」であるワードの次のワードには入力信号が「００００」の時に遷移する状態が格納され、同様にその次のワードには入力信号が「０００１」の時に遷移する状態が格納され、同様にその次のワードには入力信号が「００１０」の時に遷移する状態が格納され、以下同様に入力信号が４ビットの場合であるので全部で１６通りの遷移先のワードが格納されている。
【００１４】
このように、一般に、入力信号が４ビットの場合には１６通りの遷移先をワードに格納する必要がある。しかし、入力信号が限定される場合にはワード数を削減することが可能である。たとえば、第２図で状態「００１」から遷移が発生するのは入力信号が「００１１」および「０ｄ０１」（「０００１」および「０１０１」）の３通りの場合のみである。よって、この場合は、第３図に示すように網掛け表示の「１００１」以下には、入力信号が「０１０１」となるまでの６個のワードのみを格納すればよい。
【００１５】
以下では、第１図の状態遷移回路の逐次読み出しメモリ１０１に第３図に示すデータを格納することによって第２図に示すような状態遷移を行う状態遷移回路が実現可能となることを説明する。
【００１６】
いま、状態レジスタ３０１に例えば状態「００１」が現在の状態として設定されているとする。このとき状態制御部３０２はメモリ制御部１０２に対して逐次読み出しメモリ１０１からワードを読み出すことを指示する。メモリ制御部１０２は逐次読み出しメモリ１０１に対して現時点で読み出しているワードの次のワードを読み出して状態制御部３０２に転送する。状態制御部３０２はメモリから読み出されたワードの先頭ビットが「１」であり、かつ状態レジスタ３０１に設定されている現状態とワードの下位３ビットが等しい値となるワードの次のワードまでメモリ制御部１０２にワードを逐次読み出す指示を繰り返し行う。この例では逐次読み出しメモリ１０１からワード「１００１」が読み出された後の「０ｄｄｄ」を読み出した状態で動作が停止する。
【００１７】
このように、状態記憶手段３０の状態レジスタ３０１に特定のワードの下３ビットが設定されると、状態制御部３０２によって、その状態レジスタ３０１に設定されている現在の状態に応じた読み出し位置に逐次読み出しメモリ１０１の読み出しスタート位置がセットされる。
【００１８】
次に、外部から入力信号が与えられると、その値は遷移レジスタ２０１に設定されるとともに遷移条件判定部２０２に通知される。遷移条件判定部２０２は、遷移レジスタ２０１に設定されている値が予め定められた値になるまで以下の指示を繰り返す。遷移条件判定部２０２は、入力信号を受信したことを状態制御部３０２に通知すると、状態制御部３０２はメモリ制御部１０２に対して逐次読み出しメモリ１０１からワードを読み出すことを指示する。メモリ制御部１０２は、逐次読み出しメモリ１０１に対して、現時点で読み出しているワードの次のワードを読み出して状態レジスタ３０１に転送するとともに、遷移条件判定部２０２にワードを読み出したことを通知する。遷移条件判定部２０２は遷移レジスタ２０１に設定されている値を予め定められた方法で更新して設定する。この例では１による減算を行った結果を遷移レジスタ２０１に設定するものとする。遷移条件判定部２０２は遷移レジスタ２０１に設定されている値が予め定められた値になるまで状態制御部３０２に対してワードの逐次読み出しを行う指示を繰り返す。この例では遷移レジスタ２０１に設定されている値が「００００」になった時に指示の繰り返しを停止する。遷移条件判定部２０２が遷移レジスタ２０１に設定されている値が予め定められた値になったことを状態制御部３０２に通知すると、状態制御部３０２は状態レジスタ３０１に対してメモリから読み出されているワードの下位３ビットを設定することを指示する。
【００１９】
このように、外部から遷移条件が遷移条件記憶手段２０の遷移レジスタ２０１に設定されると、遷移条件判定部２０２によってその遷移レジスタ２０１の内容がたとえば「００００」になるまでその遷移レジスタ２０１の内容を１づつ減算更新する。そして逐次読み出しメモリ１０１ではこの更新回数だけ前記したスタート位置からワードが逐次読み出され、最後に読み出されたワードの下３ビットで状態レジスタ３０１が更新される。なお、外部入力する遷移条件が前記の「００００」のときは遷移レジスタ２０１の内容は更新されない。このときは状態レジスタ３０１は逐次読み出しメモリ１０１のスタート位置のワードの下３ビットで更新されることになる。
【００２０】
以上説明した方法を用いることによって、状態遷移の条件が変更となった場合でも、メモリ１０に格納されている内容を変更するのみで状態遷移回路を構成することが可能となる。この構成の特徴としては遷移条件記憶手段２０の中で遷移レジスタ２０１の値を更新する処理が必要となり、これ自身が状態遷移回路と見なされるが、一般にこの部分は単純なカウンタで構成することが可能であり、本来実現する状態遷移回路の状態遷移の複雑さとは無関係である。
【００２１】
また、本発明で述べた構成では、状態遷移回路の状態数が増加した場合には、状態レジスタ３０１のビット幅の拡張および逐次読み出しメモリ１０１のワード幅の拡張によって容易に対応可能である。
【００２２】
また、状態遷移の契機となる外部条件を与える入力信号の数が増加した場合には、遷移レジスタ２０１のビット幅を拡張するとともに、更新のための回路のビット幅を増やすことで容易に対応可能である。
【００２３】
以上のような特徴は、複数のセルで構成され各セルが論理回路またはメモリとして選択的に利用可能なハードウエア上に状態遷移回路を構成するのに適している。
【００２４】
【発明の効果】
以上から本発明によれば、状態遷移条件の複雑さに影響されない組み合わせ回路（遷移条件記憶手段と状態記憶手段）によって状態遷移回路を構成することが可能となる。また、状態の遷移条件が変更となった場合でも、メモリに格納されている内容を変更するのみで組み合わせ回路を変更することなく状態遷移回路を再構成することが可能となる。
【図面の簡単な説明】
【図１】本発明の１つの実施形態の状態遷移回路のブロック図である。
【図２】状態遷移回路の状態遷移条件を定義する状態遷移図である。
【図３】第２図の状態遷移図を実現するために逐次読み出しメモリに格納されるデータの説明図である。
【図４】従来の状態遷移回路のブロック図である。
【符号の説明】
１０：メモリ、１０１：逐次読み出しメモリ、１０２：メモリ制御部
２０：遷移条件記憶手段、２０１：遷移レジスタ、２０２：遷移条件判定部
３０：状態記憶手段、３０１：状態レジスタ、３０２：状態制御部
【図１】
0003573417.tif 000002
【図２】
0003573417.tif 000003
【図３】
0003573417.tif 000004
【図４】
0003573417.tif 000005