(57)【特許請求の範囲】
【請求項１】
遷移情報が格納され逐次読み出しを繰り返し行うことが可能なメモリ、前記メモリから読み出した内容を設定可能な状態記憶手段、および状態遷移回路が次の状態に遷移する遷移条件を設定可能な遷移条件記憶手段から構成され、前記状態記憶手段は前記メモリから読み出した内容と前記状態記憶手段に設定されている内容とが予め定められた条件を満足するまで順次メモリの内容を読み出す機能を有し、前記遷移条件記憶手段は遷移条件が設定されると前記メモリからの読み出しと前記遷移条件記憶手段の内容の更新とを繰り返し、前記遷移条件記憶手段に設定されている内容が予め定められた値となった時点で前記メモリから読み出した内容に基づき前記状態記憶手段の内容を更新する状態遷移回路において、
前記遷移情報の全部又は１部を重複して前記メモリに格納しておくことを特徴とする状態遷移回路。
【請求項２】
逐次読み出しを繰り返し行うことが可能なメモリ、前記メモリから読み出した内容を設定可能な状態記憶手段、および状態遷移回路が次の条件に遷移する遷移条件を設定するとともに前記メモリからの逐次読み出し毎にその内容を更新する遷移条件記憶手段で構成される状態遷移回路の制御方法であって、
前記メモリに遷移情報の全部又は１部を重複して格納し、前記メモリから読み出した内容と前記状態記憶手段の設定内容とが所定条件を満足するまで順次前記メモリの内容を読み出し、
前記遷移条件記憶手段に遷移条件が設定されると、前記メモリからの読み出しと前記遷移条件記憶手段の設定内容の更新とを繰り返し、前記遷移条件記憶手段の設定内容が所定値となった時点で前記メモリから読み出した内容を前記状態記憶手段に設定する、
ことを特徴とする状態遷移回路の制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、現在の状態と外部入力される遷移条件とに基づき次の状態を選択して設定する状態遷移回路（順序回路）およびその制御方法に係り、特に複数のセルで構成され各セルがメモリまたは論理回路の何れとしても選択利用可能なハードウェア上に構成するのに好適な状態遷移回路およびその制御方法に関するものである。
【０００２】
【従来の技術】
図６に示すように、従来の状態遷移回路は状態を記憶する複数のフリップフロップ（ＦＦ）１と、それらフリップフロップ１に格納された内容と外部から与えられた状態遷移条件とを入力とする組み合わせ回路２とで構成されている。そして、組み合わせ回路２の出力がフリップフロップ１に設定されることでフリップフロップ１に次の状態が設定されることになる。
【０００３】
このような状態遷移回路の構成方法では状態を遷移させる条件が複雑になると組み合わせ回路２が急激に増加するという欠点がある。特に、近年広く利用されるようになったＦＰＧＡ（Field Programmable Gate Array）では、組み合わせ回路２をセルと呼ばれる小規模メモリの接続によって実現するが、小規模メモリ間の接続が複雑になると回路を割り当てるために必要となるセルが増加するとともに、その動作も低速になる欠点がある。
【０００４】
そこで、これらの欠点を回避するために、状態遷移条件（遷移情報）を、逐次読み出しを繰り返し行うことが可能なメモリに格納し、現在の状態と外部から入力される遷移条件とからそのメモリ内に格納されている次の状態を選択することで、組み合わせ回路が遷移条件の複雑さに影響されない状態遷移回路を構成する手法が「状態遷移回路およびその制御方法」（特願2000-366464）で示されている。
【０００５】
【発明が解決しようとする課題】
ところが、この手法では、状態が遷移してから次の状態に遷移するまでの最長の時間がメモリを最初から最後まで読み出す時間に等しくなってしまう欠点がある。さらに、一般の状態遷移回路は全ての状態に均一に遷移するのではなく、特定の状態間の遷移確率が高いという特徴があることから、このような特徴を利用して特定の状態遷移の時間を短縮可能な手段を実現することが望まれる。
【０００６】
本発明はこれらの欠点に鑑みてなされたもので、第１の目的は、状態遷移条件（遷移情報）の複雑さによらず、最長の状態遷移時間がメモリを最初から最後まで読み出す時間によって決定されることがないように、最長となる状態遷移時間を短縮できるようにすることである。また、第２の目的は、特定の状態間の遷移確率が高い場合には、その特定の状態間の状態遷移時間を短縮できるようにすることである。
【０００７】
【課題を解決するための手段】
このために請求項１の発明は、遷移情報が格納され逐次読み出しを繰り返し行うことが可能なメモリ、前記メモリから読み出した内容を設定可能な状態記憶手段、および状態遷移回路が次の状態に遷移する遷移条件を設定可能な遷移条件記憶手段から構成され、前記状態記憶手段は前記メモリから読み出した内容と前記状態記憶手段に設定されている内容とが予め定められた条件を満足するまで順次メモリの内容を読み出す機能を有し、前記遷移条件記憶手段は遷移条件が設定されると前記メモリからの読み出しと前記遷移条件記憶手段の内容の更新とを繰り返し、前記遷移条件記憶手段に設定されている内容が予め定められた値となった時点で前記メモリから読み出した内容に基づき前記状態記憶手段の内容を更新する状態遷移回路において、前記遷移情報の全部又は１部を重複して前記メモリに格納しておくことを特徴とする状態遷移回路とした。
【０００８】
請求項２の発明は、逐次読み出しを繰り返し行うことが可能なメモリ、前記メモリから読み出した内容を設定可能な状態記憶手段、および状態遷移回路が次の条件に遷移する遷移条件を設定するとともに前記メモリからの逐次読み出し毎にその内容を更新する遷移条件記憶手段で構成される状態遷移回路の制御方法であって、前記メモリに遷移情報の全部又は１部を重複して格納し、前記メモリから読み出した内容と前記状態記憶手段の設定内容とが所定条件を満足するまで順次前記メモリの内容を読み出し、前記遷移条件記憶手段に遷移条件が設定されると、前記メモリからの読み出しと前記遷移条件記憶手段の設定内容の更新とを繰り返し、前記遷移条件記憶手段の設定内容が所定値となった時点で前記メモリから読み出した内容を前記状態記憶手段に設定する、ことを特徴とする状態遷移回路の制御方法とした。
【０００９】
【発明の実施の形態】
本発明では、メモリに格納するデータ（遷移情報）の複製を当該のメモリに格納することにより、最長となる状態遷移時間を短縮し、また、特定の状態間の遷移確率が高い場合でも当該特定の状態間の状態遷移時間を短縮する。
【００１０】
まず、メモリに格納した状態遷移条件（遷移情報）を繰り返し読み出すことで状態遷移回路を実現する方法について説明する。
【００１１】
図１は本発明の一実施形態の状態遷移回路の構成例のブロック図である。メモリ１０は、格納されているデータ（遷移情報）を固定長のビット幅（ワード）で逐次読み出しが可能な逐次読み出しメモリ１０１と、その逐次読み出しメモリ１０１に対して読み出しの指示および格納されている最後のワードを読み出した場合には最初（先頭）からの読み出しを指示するメモリ制御部１０２とで構成される。
【００１２】
遷移条件記憶手段２０は、入力信号の値（遷移条件）を設定する遷移レジスタ２０１と、その遷移レジスタ２０１の内容を読み出すとともに次の値を設定する遷移条件判定部２０２とで構成される。
【００１３】
状態記憶手段３０は、状態遷移回路の状態を設定する状態レジスタ３０１と、メモリ１０から読み出した内容を監視するとともにその内容を状態レジスタ３０１に設定することを指示する状態制御部３０２とから構成される。
【００１４】
図２は状態遷移回路の現状態と各状態に対して入力信号が与えられた時に何れの状態に遷移するかを定義する状態遷移図の例である。この例では３ビットで定義される５つの状態が存在し、入力信号は４ビットで与えられる。
【００１５】
図３は図２の状態遷移を図１に示す構成の状態遷移回路で実現するために図１の逐次読み出しメモリ１０１に格納するデータ内容の一例を示す図である。逐次読み出しメモリ１０１は、メモリ制御部１０２の指示により４ビット単位（ワード）で内部に格納されている図３のデータが読み出される。
【００１６】
図３に示す４ビットで構成されるワードの先頭ビットはフラグであり、残りの３ビットは状態を示している。先頭ビットが「１」のワードは以下の３ビットで現在の状態を示し、先頭ビットが「０」のワードは以下の３ビットで次に遷移する状態を示す。先頭ビットが「１」であるワードの次のワードには入力信号が「００００」の時に遷移する状態が格納されており、同様にその次のワードには入力信号が「０００１」の時に遷移する状態が格納されている。
【００１７】
一般に、入力信号が４ビットの場合には１６通りの遷移先をワードに格納する必要があるが、入力信号が限定される場合にはワード数を削減することが可能である。たとえば、図２で状態「００１」から遷移が発生するのは、入力信号が「００００」、「００１１」および「０ｄ０ｌ」（「０００１」および「０１０１」）の４通りの場合のみである。よって、図３に示すように入力信号が「０００」から「０１０１」となるまでの６個のワードのみを格納すればよい。なお、ここで、図中の”＝＞”で指定されるワードはメモリに格納される状態遷移条件の末尾であり、それ以降のメモリの空き領域には「００００」が格納される。
【００１８】
以下に、図１の状態遷移回路の逐次読み出しメモリ１０１に図３に示すデータを格納することによって、図２に示すような状態遷移を行う状態遷移回路が実現可能となることを説明する。
【００１９】
いま、状態レジスタ３０１に例えば状態「００１」が現状態として設定されているとする。状態制御部３０２はメモリ制御部１０２に対して逐次読み出しメモリ１０１からワードを読み出すことを指示する。メモリ制御部１０２は逐次読み出しメモリ１０１に対して現時点で読み出しているワードの次のワードを読み出して状態制御部３０２に転送する。状態制御部３０２はメモリ１０から読み出されたワードの先頭ビットが「１」であり、かつ状態レジスタ３０１に設定されている現状態とワードの下位３ビットが等しい値となるワードの次のワードまでメモリ制御部１０２にワードを逐次読み出す指示を繰り返し行う。この例では、逐次読み出しメモリ１０１からワード「１００１」が読み出された後のワード「０００１」を読み出した状態で動作が停止する。
【００２０】
このように、状態記憶手段３０の状態レジスタ３０１に特定のワードの下３ビット（現状態）が設定されると、状態制御部３０２によって、その状態レジスタ３０１に設定されている現状態に応じた読み出し位置に逐次読み出しメモリ１０１の読み出しスタート位置がセットされる。
【００２１】
次に、外部から入力信号が与えられると、その値は遷移レジスタ２０１に設定されるとともに遷移条件判定部２０２に通知される。遷移条件判定部２０２は遷移レジスタ２０１に設定されている値が予め定められた値になるまで以下の指示を繰り返す。すなわち、遷移条件判定部２０２は入力信号を受信したことを状態制御部３０２に通知すると、状態制御部３０２はメモリ制御部１０２に対して逐次読み出しメモリ１０１からワードを読み出すことを指示する。メモリ制御部１０２は逐次読み出しメモリ１０１に対して、現時点で読み出しているワードの次のワードを読み出して状態レジスタ３０１に転送するとともに、遷移条件判定部２０２にワードを読み出したことを通知する。遷移条件判定部２０２は遷移レジスタ２０１に設定されている値を予め定められた方法で更新して設定する。この例では１による減算を行った結果を遷移レジスタ２０１に設定するものとする。遷移条件判定部２０２は遷移レジスタ２０１に設定されている値が予め定められた値になるまで状態制御部３０２に対してワードの逐次読み出しを行う指示を繰り返す。この例では、遷移レジスタ２０１に設定されている値が「００００」になった時に指示の繰り返しを停止する。遷移条件判定部２０２が遷移レジスタ２０１に設定されている値が予め定められた値になったことを状態制御部３０２に通知すると、状態制御部３０２は状態レジスタ３０１に対してメモリ１０から読み出されているワードの下位３ビットを設定することを指示する。
【００２２】
このように、外部から遷移条件が遷移条件記憶手段２０の遷移レジスタ２０１に設定されると、遷移条件判定部２０２によってその遷移レジスタ２０１の内容が例えば「００００」になるまでその遷移レジスタ２０１の内容を１づつ減算更新する。そして逐次読み出しメモリ１０１ではこの更新回数だけ前記したスタート位置からワードが逐次読み出され、最後に読み出されたワードの下３ビットで状態レジスタ３０１が更新される。なお、外部入力する遷移条件が前記の「００００」のときは遷移レジスタ２０１の内容は更新されない。このときは状態レジスタ３０１は逐次読み出しメモリ１０１のスタート位置のワードの下３ビットで更新されることになる。
【００２３】
以上述べた方法によって、メモリ１０１に格納した状態遷移条件（遷移情報）に従って状態遷移を行う状態遷移回路が実現できる。また、状態遷移条件が変更となった場合には、メモリ１０に格納されている内容を変更するのみで状態遷移回路を構成することが可能となる。この構成の特徴としては遷移条件記憶手段２０の中で遷移レジスタ２０１の値を更新する処理が必要となり、これ自身が状態遷移回路と見なされるが、一般にこの部分は単純なカウンタで構成することが可能であり、本来実現する状態遷移回路の状態遷移の複雑さとは無関係である。
【００２４】
次に、本発明の特徴である「最長となる状態遷移時間を短縮する」ことを実現する実施例について説明する。
【００２５】
最長の状態遷移時間を短縮するために、図２で定義される状態遷移回路において、逐次読み出しメモリ１０１へ遷移情報を格納する例を図４に示す。ここでは、図３で空き領域として使用されていなかった「００００」の領域に、全部の遷移情報の複製を格納している。上述したように逐次読み出しメモリ１０１の内容は繰り返し読み込まれるので、このような方法で複製を逐次読み出しメモリ１０１の空き領域に格納しても状態遷移回路を実現する上で矛盾は生じない。
【００２６】
状態「００１」から状態「００１」へ遷移する際に、図３の例のように逐次読み出しメモリ１０１に遷移情報を格納した場合には、逐次読み出しメモリ１０１内の空き領域を含む全てのワード（１００ワード）を読み出すことで初めて遷移後の次の入力信号が受け付け可能となり、状態遷移時間が長くなる。これに対して、図４の例のように逐次読み出しメモリ１０１の空き領域であった部分にへ全部の遷移情報の複製を格納した場合には、逐次読み出しメモリ１０１内の約半分のワード（４６ワードまたは５４ワード）を読み出すことで遷移後の次の入力信号が受け付け可能となり、状態遷移時間を短縮できる。
【００２７】
次に、本発明の特徴である「特定の状態間の遷移時間を短縮する」ことを実現する実施例について説明する。
【００２８】
特定の状態間の遷移時間を短縮するために、図２で定義される状態遷移回路において、逐次読み出しメモリ１０１へ遷移情報を格納する例を図５に示す。ここでは、図３で空き領域として使用されていなかった領域に、状態「１０１」に関する遷移情報の複製を３組（元の遷移情報を入れると合計４組）格納している。上述したように逐次読み出しメモリ１０１の内容は繰り返し読み込まれるので、このような方法で特定の状態に関する遷移情報の複製を逐次読み出しメモリ１０１の空き領域に格納しても状態遷移回路を実現する上で矛盾は生じない。
【００２９】
この状態遷移回路に入力される信号のパターンでは、状態「１０１」に遷移した後、３回連続して信号「０００１」が入力される確率が高い時、図３の例のように逐次読み出しメモリ１０１に遷移情報を格納した場合には、逐次読み出しメモリ１０１内の空き領域を含む全てのワード（１００ワード）を読み出すことで初めて遷移後の次の入力信号が受け付け可能となり、状態遷移時間が長くなる。これに対して、図５の例のように逐次読み出しメモリ１０１の空き領域であった部分に状態「１０１」に関する遷移情報の複製を格納した場合には、状態「１０１」に遷移した以後、信号「０００１」が３回入力された時の各状態遷移では逐次読み出しメモリ１０１内の３ワードを読み出すことで各回毎に次の入力信号が受け付け可能となり、状態遷移時間を短縮できる。
【００３０】
以上のように、逐次読み出しメモリ１０１の空き領域であった部分に全部の遷移情報の複製を格納することによって、逐次読み出しメモリ１０１を最初から最後まで読み出す必要がなくなり状態遷移時間を短縮できる。また、特定の状態間での遷移確率が高いことが予測できる場合には、それに応じて逐次読み出しメモリ１０１に当該状態の遷移情報の複製を１乃至複数格納するよう内容を書き換えることで、入力信号のパターンに応じた状態遷移回路を構成することも可能である。なお、実施例で述べた「最長の状態遷移時間を短縮する」方法と「特定の状態遷移の時間を短くする」方法を組み合わせて使用することも可能である。
【００３１】
【発明の効果】
以上から本発明によれば、状態遷移条件（遷移情報）を格納する逐次読み出しメモリの読み出し周期に依存せず状態遷移動作が可能な状態遷移回路を構成することが可能となる。また、特定の状態間の遷移確率が高い場合に状態遷移回路がこれらの状態間を遷移する時間を短縮することが可能となる。
【図面の簡単な説明】
【図１】  本発明の１つの実施形態の状態遷移回路のブロック図である。
【図２】  状態遷移回路の状態遷移条件を定義する状態遷移図である。
【図３】  図２の状態遷移図を実現するために逐次読み出しメモリに格納されるデータの説明図である。
【図４】  最長の状態遷移時間を短縮するためにメモリに格納されるデータの説明図である。
【図５】  特定の状態間の遷移時間を短縮するためにメモリに格納されるデータの説明図である。
【図６】  従来の状態遷移回路のブロック図である。
【符号の説明】
１０：メモリ、１０１：逐次読み出しメモリ、１０２：メモリ制御部
２０：遷移条件記憶手段、２０１：遷移レジスタ、２０２：遷移条件判定部
３０：状態記憶手段、３０１：状態レジスタ、３０２：状態制御部
【図１】
0003648174.tif 000002
【図２】
0003648174.tif 000003
【図３】
0003648174.tif 000004
【図４】
0003648174.tif 000005
【図５】
0003648174.tif 000006
【図６】
0003648174.tif 000007