(57)【要約】【課題】メモリを用いて状態遷移の管理を行う状態遷移管理装置において、メモリの使用効率を高める。【解決手段】現在の状態番号に対する次状態番号候補を格納したメモリ１０１と、メモリから読み出した次状態番号候補の中から次状態番号を選択する選択回路（１０４、１０５、１１３、１１４）を備える。メモリは、現在の状態番号に対する分岐先である次状態番号候補の数が少ない状態番号に対しては、複数の状態番号に対する次状態番号候補をメモリの同時に読み出し可能なアドレスに格納する。選択回路は、イベント識別コード（１０９、１１０）と、現在の状態番号１０８と、から次状態番号を選択する。【選択図】図１
2010045581.tif 000002
【特許請求の範囲】
【請求項１】
状態遷移のルールを格納したメモリであって、状態番号に基づく第一の信号をアドレスとして入力すると複数の次状態番号候補が読み出されるメモリと、
前記読み出された複数の次状態番号候補から次状態番号を選択する選択回路と、
を備えた状態遷移管理装置であって、
前記状態番号に基づく第二の信号を入力して選択方法指定信号を出力する選択方法指定部を備え、
前記選択回路が、前記選択方法指定部から読み出された選択方法指定信号と、イベントに基づく信号と、前記状態番号に基づく第三の信号とを入力し、前記複数の次状態番号候補の中から次状態番号を選択する
ことを特徴とする状態遷移管理装置。
【請求項２】
前記第一の信号、前記第二の信号が共に、前記状態番号の一部のビットであり、
前記第三の信号が、前記状態番号の前記第一、第二の信号とは異なるビットであり、
前記イベントに基づく信号が、イベント識別コードである
ことを特徴とする請求項１記載の状態遷移管理装置。
【請求項３】
前記選択回路が、前記イベントに基づく信号と、前記第三の信号と、前記選択方法指定信号と、を入力し、前記選択方法指定信号に基づいて、前記イベントに基づく信号と、前記第三の信号と、から選択信号を生成する選択信号生成部と、
前記選択信号に基づいて、前記複数の次状態番号候補から次状態番号を選択する次状態番号選択部と、
を有することを特徴とする請求項１または２記載の状態遷移管理装置。
【請求項４】
前記イベントに基づく信号、前記第三の信号、前記選択方法指定信号は、いずれも複数ビットで構成される信号であって、
前記選択信号生成部が、並列に接続された複数の選択信号セレクタを含み、
前記複数の選択信号セレクタは、それぞれ、前記イベントに基づく信号の一部のビット、前記第三の信号の一部のビット、前記選択方法指定信号の一部のビットを入力し、前記選択方法指定信号の一部のビットに基づいて、前記イベントに基づく信号の一部のビットまたは、前記第三の信号の一部のビットを選択して出力するセレクタ回路であって、
前記次状態番号選択部が、多段に接続された複数の次状態番号セレクタを含み、
前記複数の次状態番号セレクタが、それぞれ、前記複数の選択信号セレクタのいずれかの出力信号に基づいて、複数の次状態番号候補の中から次状態番号となりうる次状態番号候補を絞り込み、次段の次状態番号セレクタの次状態番号候補とする次状態番号セレクタであって、最終段の次状態番号セレクタが次状態番号を選択して出力する
ことを特徴とする請求項３記載の状態遷移管理装置。
【請求項５】
前記メモリの少なくとも一部のアドレスについて、前記第一の信号を入力すると複数の状態番号に対する次状態番号候補が読み出され、
前記選択回路が、複数の次状態番号候補の中から、当該状態番号に対する次状態番号候補であるか否かの選択を前記第三の信号により選択し、当該状態番号に対する次状態番号候補の中から当該状態番号に対する次状態番号の選択を前記イベントに基づく信号により選択する
ことを特徴とする請求項１乃至４いずれか１項記載の状態遷移管理装置。
【請求項６】
多分岐先を有する状態番号であって、１回のアクセスで前記メモリから読み出し可能な次状態番号候補の数を超える次状態番号候補を有する状態番号に対する少なくとも一部の次状態番号候補を記憶する拡張メモリをさらに備え、
前記選択回路が、前記拡張メモリから読み出させた次状態番号候補も含めて次状態番号を選択する選択回路である請求項１乃至５いずれか１項記載の状態遷移管理装置。
【請求項７】
前記選択回路が、
前記イベントに基づく信号の一部のビットに基づいて、前記拡張メモリから読み出された複数の次状態番号候補から一つの次状態番号候補を選択する拡張セレクタと、
前記メモリから読み出された複数の次状態番号候補から選択された次状態番号候補と、前記拡張セレクタにより選択された次状態番号候補と、から次状態番号を選択する拡張次状態番号セレクタと、
をさらに有することを特徴とする請求項６記載の状態遷移管理装置。
【請求項８】
前記選択方法指定部が前記メモリの一部であって、前記メモリが、前記第一の信号をアドレスとして入力すると前記複数の次状態番号候補と共に、前記選択方法指定信号が読み出されるメモリであることを特徴とする請求項１乃至７いずれか１項記載の状態遷移管理装置。
【請求項９】
前記選択方法指定部が論理回路により構成されていることを特徴とする請求項１乃至７いずれか１項記載の状態遷移管理装置。
【請求項１０】
現在の状態番号に基づくアドレスを与えたときに、次の取りうる状態番号である次状態番号候補が読み出されるメモリを用い、
状態番号に対する次状態番号候補が複数ある場合に外部から入力されるイベントに基づいて、前記複数の次状態番号候補の中から次状態番号を選択する状態遷移管理装置の状態遷移管理方法であって、
次状態番号候補の数が少ない状態番号に対してアドレスを与えると複数の状態番号に対する次状態番号候補が前記メモリから読み出され、
前記読み出された複数の次状態番号候補の中から当該状態番号に対する次状態番号候補の選択を当該状態番号の少なくとも一部のビットを用いて行い、
当該状態番号に対する複数の次状態番号候補の中から次状態番号の選択は、前記イベントに基づいて選択することを特徴とする状態遷移管理装置の状態遷移管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、状態遷移管理装置及びその状態遷移管理方法に関する。特に、ＬＳＩ等のデジタル回路で用いられる状態遷移管理装置及びその状態遷移管理方法に関する。
【背景技術】
【０００２】
近年のデジタル技術の発展に伴い、ＬＳＩ製造後にプログラムで動作を決めることができるプログラマブルデバイスが、数多く使用されている。その中でも、特許文献１に記載されているアレイ型プロセッサでは、搭載するアプリケーションを状態遷移とデータパスに分離し、それぞれに適した構成のハードウェアでの動作を実現している。
【０００３】
この状態遷移を実現する状態遷移管理装置は、特許文献１の図１５に示されるように、状態遷移のルールを状態遷移管理装置内のメモリ（テーブル）に格納し、このメモリに状態番号を入力すると出力される複数の次状態番号候補の中から、イベント識別コードにより１つを選択している。以下に例を用いて詳細を説明する。
【０００４】
図２５（ａ）に、例として用いる状態遷移図を示す。丸の中の数字は状態番号であり、矢印の指す状態へのみ遷移することができる。また矢印に添えられた文字は、その矢印へ進むための条件（イベント識別コード）を示している。図２５（ａ）の場合、状態０をスタートとすると、イベント識別コードｅ０の入力により状態１へ遷移する。すると、状態１には、状態２、３、４の３つの遷移先（分岐）が存在する。ここで、イベント識別コードｅ０が入力した場合は状態２へ、ｅ１が入力した場合は状態３へ、ｅ２が入力した場合は状態４へ進むことを示している。以降、同様に、状態２の次はイベント識別コードｅ０により状態５へ、状態３の次は同じくｅ０により状態５へ遷移する。状態４の次は、状態５と６の２つがあるが、イベント識別コードｅ０の場合は状態５へ、ｅ１の場合は状態６へ遷移する。状態５の場合は、ｅ０により状態６へ遷移する。
【０００５】
次に、図２５（ａ）の状態遷移図を実現する状態遷移管理装置の例を図２５（ｂ）に示す。まず現状態番号２５０１がメモリ２５０２に入力すると、入力値に応じて４つの次状態番号候補が２５０３に出力される。その中の１つを、イベント識別コード２５０４を用いてセレクタ２５０５で選択し、次状態番号２５０６が出力される。なお次状態番号２５０６は次のクロックサイクルにおいて現状態番号２５０１となり、２５０２へ入力して次の状態番号を決めるという動作が繰り返し行われることで、状態遷移が継続して行われることになる。
【０００６】
動作例を用いて、これを説明する。まず図２５（ａ）の２５０８の枠内に示す、状態０においてイベント識別コードｅ０が入力すると状態１に遷移するという動作を説明する。  この場合、現状態番号入力２５０１として０が入力するので、メモリ２５０２における２５０７が０の行、すなわち２５０９の枠内の値が２５０３へ出力される。ここでイベント識別コード２５０４としてｅ０が入力するので、ｅ０の列にある値１がセレクタ２５０５で選択され、次状態番号２５０６となる。
【０００７】
続いて図２５（ａ）の２５１０の枠内に示す、状態１においてイベント識別信号ｅ０、ｅ１、ｅ２のいずれかが入力すると、それぞれ状態２、３、４へ遷移するという動作を説明する。この場合、現状態番号入力２５０１として１が入力するので、メモリ２５０２における２５０７が１の行、すなわち２５１１の枠内の値が２５０３へ出力される。ここでイベント識別コード２５０４としてｅ０が入力すれば、ｅ０の列にある値２が、ｅ１が入力すればｅ１の列にある値３が、ｅ２が入力すればｅ２の列にある値４がセレクタ２５０５で選択され、次状態番号２５０６となる。
【０００８】
もう１例として図２５（ａ）の２５１２の枠内に示す、状態４においてイベント識別信号ｅ０が入力すると状態５へ、ｅ１が入力すると状態６へ遷移するという動作を説明する。この場合、現状態番号入力２５０１として４が入力するので、メモリ２５０２における２５０７が４の行、すなわち２５１３の枠内の値が２５０３へ出力される。ここでイベント識別コード２５０４としてｅ０が入力すればｅ０の列にある値５が、ｅ１が入力すればｅ１の列にある値６がセレクタ２５０５で選択され、次状態番号２５０６となる。
【０００９】
なお、この状態遷移管理装置の実現を実現するメモリは、現状態番号入力２５０１をアドレス入力、複数の次状態番号候補の出力２５０３をデータ出力と考えればよい。
【特許文献１】特許第３６７４５１５号公報
【特許文献２】特開平３−２８２６０２号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら特許文献１に開示された状態遷移管理装置には、内部メモリの使用効率という点で問題がある。プログラマブルという特性から、様々な状態遷移図への対応を考えると、状態遷移管理装置は、実現可能な状態数および分岐数が多いほうが良い。しかし、状態遷移のルールの格納に使用するメモリは、一般的にアドレス毎のデータビット幅が全て等しい。これは、次状態番号候補の数（＝データビット幅）は、現状態番号入力（＝アドレス）に依存せず固定となることを意味する。ゆえに、搭載可能な状態数を増やすには、状態遷移管理装置を構成するメモリのアドレス方向のサイズを増やし、搭載可能な分岐数を増やすには、同じくメモリのビット幅方向のサイズを増やす必要がある。
【００１１】
ところが、図２５の例からも分かるように、分岐数は状態毎に異なっており、多数の分岐が使用される状態は少ないことが多い。ゆえに、全状態で分岐可能な数が同じ状態遷移管理装置であるとすれば、状態遷移テーブルにおいて使用されないメモリの部分（図２５（ｂ）では、空欄になっている部分）が数多く発生してしまうことになる。
【００１２】
このように、一般的なメモリを用いて、アドレス方向のサイズを実現可能な状態数、ビット幅方向のサイズを分岐可能な状態数とすると、状態遷移管理装置を構成するメモリの使用効率が良くないという問題点がある。
【課題を解決するための手段】
【００１３】
本発明の１つのアスペクト（側面）に係る状態遷移管理装置は、状態遷移のルールを格納したメモリであって状態番号に基づく第一の信号をアドレスとして入力すると複数の次状態番号候補が読み出されるメモリと、前記読み出された複数の次状態番号候補から次状態番号を選択する選択回路と、を備えた状態遷移管理装置であって、前記状態番号に基づく第二の信号を入力して選択方法指定信号を出力する選択方法指定部を備え、前記選択回路が、前記選択方法指定部から読み出された選択方法指定信号とイベントに基づく信号と前記状態番号に基づく第三の信号とを入力し前記複数の次状態番号候補の中から次状態番号を選択することを特徴とする。
【００１４】
また、本発明の別なアスペクトに係る状態遷移管理方法は、現在の状態番号に基づくアドレスを与えたときに次の取りうる状態番号である次状態番号候補が読み出されるメモリを用い、状態番号に対する次状態番号候補が複数ある場合に外部から入力されるイベントに基づいて前記複数の次状態番号候補の中から次状態番号を選択する状態遷移管理装置の状態遷移管理方法であって、次状態番号候補の数が少ない状態番号に対してアドレスを与えると複数の状態番号に対する次状態番号候補が前記メモリから読み出され、前記読み出された複数の次状態番号候補の中から当該状態番号に対する次状態番号候補の選択を当該状態番号の少なくとも一部のビットを用いて行い、当該状態番号に対する複数の次状態番号候補の中から次状態番号の選択は、前記イベントに基づいて選択することを特徴とする。
【発明の効果】
【００１５】
本発明によれば、メモリに対する１回のアクセスで読み出せる範囲に、複数の状態番号（現状態番号）各々に対応する、１つまたは複数の次状態番号候補を格納することができるので、メモリの使用効率を高めることができる。
【発明を実施するための最良の形態】
【００１６】
本発明の実施形態の概要について、必要に応じて図面を参照して説明する。
【００１７】
図１、図１４、図１６、図１９に示すように、一実施形態の状態遷移装置は、状態遷移のルールを格納したメモリ（１０１、１４０１）であって、状態番号（１０８、１０６、１６０７）に基づく第一の信号（１０２、１４０２）をアドレスとして入力すると複数の次状態番号候補１０３が読み出されるメモリ（１０１、１４０１）と、読み出された複数の次状態番号候補１０３から次状態番号を選択する選択回路（１０４、１０５、１１３、１１４）と、を備えた状態遷移管理装置であって、状態番号に基づく第二の信号（１１６、１４０２）を入力して選択方法指定信号（１１７、１１８）を出力する選択方法指定部（１１５、図１５の１５０２）を備え、選択回路（１０４、１０５、１１３、１１４）が、選択方法指定部（１１５、図１５の１５０２）から読み出された選択方法指定信号（１１７、１１８）と、イベントに基づく信号（１０９、１１１）と、状態番号（１０８、１０６、１６０７）に基づく第三の信号（１１０、１１２）とを入力し、複数の次状態番号候補１０３の中から次状態番号（１０６、１６０７）を選択する。
【００１８】
上記の構成により、状態遷移管理装置で必要とするメモリのワード数を削減できる。すなわち、メモリから同時出力される次状態番号候補１０３の中に混在させる遷移元の状態の数を、現状態番号に応じて変えることができるようになる。これにより、従来はメモリの１ワードが現状態番号１個に対応していたのに対し、本発明の手法では、１ワードに複数の現状態番号を対応させることができるようになるため、必要とするメモリのワード数が削減される。
【００１９】
また、上記の構成により、実現可能な状態数と分岐数の組み合わせを多彩にすることができる。すなわち、メモリの１ワード内に組み合わせる、遷移元の状態の数を変更可能とすることによるものである。分岐数が少なければ、１ワードの中への組み合わせる状態数を多数にすることが可能となり、分岐数が多い場合は１ワードへの組み合わせる状態数を減らすことができる。
【００２０】
また、図１、図１４、図１６、図１９に示すように、一実施形態の状態遷移装置は、第一の信号（１０２、１４０２）、第二の信号（１１６、１４０２）が共に、状態番号（１０８、１０６、１６０７）の一部のビットであり、第三の信号（１１０、１１２）が、状態番号（１０８、１０６、１６０７）の第一の信号（１０２、１４０２）、第二の信号（１１６、１４０２）とは異なるビットであり、イベントに基づく信号（１０９、１１１）が、イベント識別コードであるものとすることができる。
【００２１】
また、図１、図１４、図１６、図１９に示すように、一実施形態の状態遷移装置は、選択回路（１０４、１０５、１１３、１１４）が、イベントに基づく信号（１０９、１１１）と第三の信号（１１０、１１２）と選択方法指定信号（１１７、１１８）とを入力し、選択方法指定信号（１１７、１１８）に基づいてイベントに基づく信号（１０９、１１１）と第三の信号（１１０、１１２）とから選択信号（１５１、１５２)を生成する選択信号生成部（１１３、１１４）と、選択信号（１５１、１５２)に基づいて複数の次状態番号候補１０３から次状態番号１０６を選択する次状態番号選択部（１０４、１０５）と、
を有するものであってもよい。
【００２２】
また、図１、図１４、図１６、図１９に示すように、一実施形態の状態遷移装置は、イベントに基づく信号（１０９、１１１）、第三の信号（１１０、１１２）、選択方法指定信号（１１７、１１８）は、いずれも複数ビットで構成される信号であって、選択信号生成部（１１３、１１４）が、並列に接続された複数の選択信号セレクタ（１１３、１１４）を含み、複数の選択信号セレクタ（１１３、１１４）は、それぞれ、イベントに基づく信号の一部のビット（１０９、１１１）、第三の信号の一部のビット（１１０、１１２）、選択方法指定信号の一部のビット（１１７、１１８）を入力し、選択方法指定信号の一部のビット（１１７、１１８）に基づいて、イベントに基づく信号の一部のビット（１０９、１１１）または、第三の信号の一部のビット（１１０、１１２）を選択して出力するセレクタ回路（１１３、１１４）であって、次状態番号選択部（１０４、１０５）が、多段に接続された複数の次状態番号セレクタ（１０４、１０５）を含み、複数の次状態番号セレクタ（１０４、１０５）が、それぞれ、複数の選択信号セレクタ（１１３、１１４）のいずれかの出力信号（１５１、１５２）に基づいて、複数の次状態番号候補１０３の中から次状態番号となりうる次状態番号候補を絞り込み、次段の次状態番号セレクタの次状態番号候補とする次状態番号セレクタであって、最終段の次状態番号セレクタ１０５が次状態番号１０６を選択して出力してもよい。
【００２３】
また、図１、図１４、図１６、図１９に示すように、一実施形態の状態遷移装置は、メモリ（１０１、１４０１）の少なくとも一部のアドレス（図９（ｂ）の９０４、９０５、図１０（ｂ）の１００４、１００５、図１１（ｂ）の１１０３、１１０４、図１２（ｂ）の１２０１、１２０２、図１５の０〜５行目、図１８の１８０２、１８０３、図２１の２００２、２００３）について、第一の信号（１０２、１４０２）を入力すると複数の状態番号に対する次状態番号候補１０３が読み出され、選択回路（１０４、１０５、１１３、１１４）が、複数の次状態番号候補１０３の中から、当該状態番号に対する次状態番号候補であるか否かの選択を第三の信号（１１０、１１２）により選択し、当該状態番号に対する次状態番号候補の中から当該状態番号に対する次状態番号の選択を前記イベントに基づく信号（１０９、１１１）により選択してもよい。
【００２４】
また、図１６、図１９に示すように、一実施形態の状態遷移装置は、多分岐先を有する状態番号であって、１回のアクセスで前記メモリから読み出し可能な次状態番号候補の数を超える次状態番号候補を有する状態番号に対する少なくとも一部の次状態番号候補を記憶する拡張メモリ（１６０１、１９０１）をさらに備え、選択回路（１０４、１０５、１１３、１１４、１６０３、１６０６、１９０３、１９０６、１９１２）が、拡張メモリ（１６０１、１９０１）から読み出させた次状態番号候補（１６０２、１９０２）も含めて次状態番号を選択する選択回路であってもよい。
【００２５】
また、図１６、図１９に示すように、一実施形態の状態遷移装置は、選択回路（１０４、１０５、１１３、１１４、１６０３、１６０６、１９０３、１９０６、１９１２）が、
イベントに基づく信号の一部のビット（１６１０、１９１０）に基づいて、拡張メモリ（１６０１、１９０１）から読み出された複数の次状態番号候補（１６０２、１９０２）から一つの次状態番号候補（１６０４、１９０４）を選択する拡張セレクタ（１６０３、１９０３）と、メモリ（１４０１）から読み出された複数の次状態番号候補から選択された次状態番号候補１６０５と、拡張セレクタ（１６０３、１９０３）により選択された次状態番号候補１６０５と、から次状態番号を選択する拡張次状態番号セレクタ（１６０６、１９０６）と、をさらに有するものであってもよい。
【００２６】
また、図１４、図１５、図１６、図１９に示すように、一実施形態の状態遷移装置は、選択方法指定部１５０２がメモリ１４０１の一部であって、メモリ１４０１が、第一の信号１４０２をアドレスとして入力すると複数の次状態番号候補１０３と共に、選択方法指定信号（１１７、１１８）が読み出されるメモリであってもよい。この実施形態では、第二の信号１４０２は第一の信号１４０２と同一である。
【００２７】
また、図１に示すように、一実施形態の状態遷移装置は、選択方法指定部１１５が論理回路により構成されているものであってもよい。
【００２８】
さらに、本発明の一実施形態の状態遷移方法は、図１、図１４、図１６、図１９に示すように、現在の状態番号に基づくアドレス（１０２、１４０２）を与えたときに、次の取りうる状態番号である次状態番号候補１０３が読み出されるメモリ（１０１、１４０１）を用い、状態番号に対する次状態番号候補が複数ある場合に外部から入力されるイベント（１０９、１１１）に基づいて、前記複数の次状態番号候補１０３の中から次状態番号１０６を選択する状態遷移管理装置の状態遷移管理方法であって、次状態番号候補の数が少ない状態番号に対してアドレスを与えると複数の状態番号に対する次状態番号候補がメモリ（１０１、１４０１）から読み出され、読み出された複数の次状態番号候補１０３の中から当該状態番号に対する次状態番号候補の選択を当該状態番号の少なくとも一部のビット（１１０、１１２）を用いて行い、当該状態番号に対する複数の次状態番号候補の中から次状態番号の選択は、イベント（１０９、１１１）に基づいて選択する。
【００２９】
以下、本発明の各実施形態について、図面を参照し、詳しく説明する。
【００３０】
［第１の実施形態］
図１は、本発明の第１の実施形態による状態遷移管理装置の全体構成を示すブロック図である。１０１は状態遷移のルールを格納するメモリ、１０２は状態番号に基づく第一の信号であり、現状態番号１０８の一部のビットである。また、１０３はメモリ１０１から出力される次状態番号候補である。ここでは現状態番号１０８および次状態番号１０６、１０３に含まれる各次状態番号候補のそれぞれが５ｂｉｔで表わされる値とし、１０２は現状態番号１０８の上位３ｂｉｔとする。またメモリ１０１は、アドレス入力として１０２と同じ３ｂｉｔ幅を、データ出力として次状態番号候補１０３と同じビット幅を必要とし、アドレスを入力すればデータが出力される非同期動作のメモリとする。
【００３１】
セレクタ１０４、１０５、１１３、１１４は全体として、複数の次状態番号候補１０３から一つの次状態番号１０６を選択する選択回路として機能する。選択信号セレクタ１１３と１１４は、それぞれ、イベント識別コード１０９、１１１と、現状態番号１０８の一部のビット（状態信号に基づく第三の信号）１１０、１１２と、選択方法指定信号１１７、１１８が入力される。
【００３２】
イベント識別コード１０９、１１１は状態遷移管理装置の外部から入力するものとし、状態遷移図において１つの状態が複数の遷移先を持つ場合に、いずれの遷移先を次の状態とするか選択するための信号である。例えばデータパス内に持つ変数Ａが正か負かによって状態の遷移先が異なる場合、値Ａの正負でイベント識別コードの値が異なるようにするものである。
【００３３】
また、１１０と１１２には、現状態番号１０８の下位２ｂｉｔの１ｂｉｔずつを使用するものとする。選択信号セレクタ１１３と１１４は、それぞれ、選択方法指定信号１１７、１１８に基づいて、選択イベント識別コードの一部のビット１０９、１１１、または、現状態番号１０８の一部のビット１１０、１１２を次状態番号セレクタ１０４、１０５の選択信号１５１、１５２として出力する。
【００３４】
次状態番号セレクタ１０４、１０５は、選択信号１５１、１５２に基づいて、複数の次状態番号候補１０３から一つの次状態番号１０６を選択して出力する。この次状態番号１０６は状態遷移管理装置から外へ出力され、データパスの動作を切り替えるためなどに使用される。なお図１では次状態番号１０６を状態遷移管理装置から外へ出力しているが、現状態番号１０８を出力しても良い。
【００３５】
１０７は次状態番号１０６を現状態番号１０８に変えるレジスタ、１０８はレジスタ１０７から出力される現状態番号である。レジスタ１０７は、１０６から入力した次状態番号を、次のクロックサイクルにおいて１０８へ出力するものである。またリセット信号により、出力１０８を初期化できると都合が良い。
【００３６】
選択方法指定部１１５は、状態番号に基づく第二の信号１１６を入力し、選択方法指定信号１１７、１１８を出力する。選択方法指定部１１５は、選択信号セレクタ１１３と１１４においてイベント識別コード１０９と１１１、現状態番号の下位２ｂｉｔ（状態信号に基づく第三の信号）１１０、１１２のいずれを選ぶかを決め、その選択を選択方法指定信号１１７、１１８として出力する。なお、状態番号に基づく第二の信号１１６は、現状態番号１０８の一部であり、ここでは、現状態番号１０８の上位３ｂｉｔを割り当てるものとする。
【００３７】
図２は選択方法指定部１１５の内部構成を示す図である。２０１は、状態番号に基づく第二の信号（現状態番号の上位３ｂｉｔ入力）１１６に対応する値を示しており、３ｂｉｔ幅すなわち０〜７の入力値１１６に応じて、１１５のどの行の値が選択方法指定信号１１７、１１８として出力されるかを示しているものである。例えば１１６から値として１が入力すれば、１１７には２０２の値ｓ、１１８には２０３の値ｓが出力される。また１１６から値として５が入力すれば、１１７には２０４の値ｓが、１１８には２０５の値ｅが出力される。なお２０２などに示される値ｓは、１１７および１１８を通じてセレクタ１１３および１１４に入力した際、現状態番号の下位２ｂｉｔ  １１０および１１２を選択することを示し、２０５などに示される値ｅは、１１７および１１８を通じてセレクタ１１３および１１４に入力した際、イベント識別コード１０９および１１１を選択することを示している。
【００３８】
次に、図３〜５を用いて本発明の状態遷移管理装置の動作について説明する。まず図３を用いて４分岐の動作を説明する。図３（ａ）では、状態番号に基づく第二の信号（現状態番号の上位３ｂｉｔ）１１６の値により、選択方法指定部１１５から選択方法指定信号１１７、１１８として共に値ｅが出力されている。そのため、選択信号セレクタ１１３および１１４では、それぞれイベント識別コード１０９、１１１が選択される。すると、次状態番号セレクタ１０４および１０５は、次状態番号候補１０３の中から１つの次状態番号１０６を、イベント識別コード１０９、１１１の値で選択することになる。これは、現状態番号の上位３ｂｉｔ（状態番号に基づく第一の信号）１０２をメモリ１０１に入力すると、そこから出力される４つの次状態番号候補１０３の中から１つを、２ｂｉｔのイベント識別コード１０９、１１１により選択していることになる。すなわち、図３（ｂ）に示すように、現状態３０１の次の状態は４つの可能性３０２、３０３、３０４、３０５があり、２ｂｉｔのイベント識別コードの値３０６により１つを選択するという、４分岐を実現している。イベント識別コードの値３０６がｂ００の場合は状態１から状態２へ、イベント識別コードの値３０６がｂ０１の場合は状態１から状態３へ、イベント識別コードの値３０６がｂ１０の場合は状態１から状態４へ、イベント識別コードの値３０６がｂ１１の場合は状態１から状態５へ遷移する。
【００３９】
次に図４を用いて２分岐の動作を説明する。図４（ａ）では、現状態番号の上位３ｂｉｔ  １１６により、選択方法指定部１１５から、１１７に対して値ｅが、１１８に対して値ｓが出力されているため、選択信号セレクタ１１３ではイベント識別コード１０９が、選択信号セレクタ１１４では現状態番号の上位から２ｂｉｔ目の値  １１２が選択される。すると次状態番号セレクタ１０４はイベント識別コード１０９の値、次状態番号セレクタ１０５は現状態番号の下位から２ｂｉｔ目の値  １１２により、次状態番号候補１０３の中から１つを選択することになる。メモリ１０１から出力される次状態番号候補１０３の４値ｓ０、ｓ１、ｓ２、ｓ３に対し、イベント識別コード１０９の値により次状態番号セレクタ１０４においてｓ０、ｓ１もしくはｓ２、ｓ３のいずれかが選択され、さらに現状態番号の下位から２ｂｉｔ目１１２により次状態番号セレクタ１０５において、ｓ０かｓ１のいずれか、もしくはｓ２かｓ３のいずれかが選択される。これは、現状態番号の上位３ｂｉｔ  １０２および現状態番号の下位から２ｂｉｔ目の  １１２すなわち現状態番号の上位４ｂｉｔにより、４つの次状態番号候補１０３の中から２つが、メモリ１０１とセレクタ１０５の組み合わせで選択され、そのうちの１つがイベント識別コード１０９の値に応じてセレクタ１０４にて選択されていることを意味する。よって図４（ｂ）に示すように、現状態４０２の次の状態は２つの可能性４０３と４０４があり、１ｂｉｔのイベント識別コードの値４０５により１つを選択するという２分岐を実現している。イベント識別コードの値４０５が０の場合は状態１から状態２へ、イベント識別コードの値４０５が１の場合は状態１から状態３へ遷移する。
【００４０】
最後に図５を用いて分岐無しの場合の動作を説明する。図５（ａ）では、状態番号に基づく第二の信号（現状態番号の上位３ｂｉｔ）１１６により、選択方法指定部１１５から選択方法指定信号１１７、１１８として共に値ｓが出力されている。そのため、選択信号セレクタ１１３および１１４では、それぞれ状態番号に基づく第三の信号（現状態番号の下位２ｂｉｔ）１１０、１１２が選択される。すると、次状態番号セレクタ１０５および１０４は、次状態番号候補１０３の中から１つの次状態番号１０６を、状態番号に基づく第三の信号（現状態番号の下位２ｂｉｔ）１１２、１１０の値により選択することになる。これは、状態番号に基づく第一の信号（現状態番号の上位３ｂｉｔ）１０２と状態番号に基づく第三の信号（現状態番号の下位２ｂｉｔ）１１２、１１０、すなわち現状態番号の全ビットにより、メモリ１０１とセレクタ１０４、１０５を組み合わせた５０１において、次状態番号が１つに決まることになる。よって図５（ｂ）に示すように、現状態５０２の次の状態は１つ５０３に決まっており、イベント識別コードの値に依存せず遷移先が決まるという分岐なし（＝１分岐）を実現している。この例の場合、状態１の次は必ず状態２となる。
【００４１】
なお現状態番号と分岐可能数の関係は選択方法指定部１１５の構成により決められる。図２を用いてこれを説明する。図２では、現状態番号の上位３ｂｉｔである１１６（状態番号に基づく第二の信号）の入力により、１１７と１１８へ値が出力される。１１６の入力値が０〜３の場合は選択方法指定信号１１７と１１８へｓとｓが出力されるので、図５に示した分岐無しが実現される。また１１６の入力値が４か５の場合は１１７と１１８へｅとｓが出力されるので、図４に示した２分岐が実現される。１１６の入力値が６か７の場合は１１７と１１８へｅとｅが出力されるので、図３に示した４分岐が実現される。
【００４２】
次に図６、７、８を用いて、メモリ１０１における状態遷移ルールの保持方法を説明する。メモリ１０１内部の格納方法は選択方法指定部１１５の内容に依存するため、選択方法指定部１１５内部の格納方法と合わせて説明する。
【００４３】
まず分岐を持たない場合の保持方法を図６に示す。分岐を持たない状態のため、図６（ａ）に示すように、選択方法指定部１１５では現状態番号の上位３ｂｉｔ（状態番号に基づく第二の信号）１１６の値により値ｓを１１７、１１８に出力する。この場合、メモリ１０１の内部には図６（ｂ）に示すような構成で状態遷移ルールを保持する。ここで６０７は、現状態番号の上位３ｂｉｔ（状態番号に基づく第一の信号）１０２の入力値に対応する値を説明するために示しており、１０２の入力値が６０７の中で一致する行の１０１内の４値が１０３に出力されることを意味する。また６０３に示すＳ０は、状態０の次状態番号を保持するための１０１内の領域を示している。同様に６０４に示すＳ１は状態１の次状態番号を保持する領域、６０５に示すＳ２は状態２の次状態番号を保持する領域、６０６に示すＳ３は状態３の次状態番号を保持する領域を示している。これにより、たとえば現状態番号の上位３ｂｉｔ（状態番号に基づく第一の信号）１０２に０が入力すると、６０７の０に対応する行の４値である６０３、６０４、６０５、６０６の各領域に保持されたＳ０、Ｓ１、Ｓ２、Ｓ３が１０３に出力される。したがって、分岐を持たない状態遷移の場合は、異なる４つの現状態番号（例では０、１、２、３）に対する次状態番号（例ではＳ０、Ｓ１、Ｓ３、Ｓ４）をメモリ１０１の同一行に保持させれば良い。なお組み合わせる４つの状態番号は上位３ｂｉｔを同一値としている。これは、１０３へ同時に出力される次状態番号候補が、現状態番号の上位３ｂｉｔ（状態番号に基づく第一の信号）１０２により判定されるためである。
【００４４】
またメモリ１０１の同一行に含める次状態番号の並びは左から順に現状態番号の小さい順としている。これはセレクタ１０４および１０５の構成と、そこで使用する現状態番号の下位２ｂｉｔ（状態番号に基づく第三の信号）１１０、１１２の接続で決まる。図６（ｂ）の構成では、現状態番号の下位２ｂｉｔ  １１２、１１０がｂ００の場合は６０８が、ｂ０１の場合は  ６０９が、ｂ１０の場合は  ６１０が、ｂ１１の場合は６１１が次状態番号１０６として選択される。ゆえに６０３はＳ０、６０４はＳ１、６０５はＳ２、６０６はＳ３という順番になっている。図６（ｂ）全体で見ると、現状態番号の上位３ｂｉｔ（ｂｉｔ４：２）である１０２（状態番号に基づく第一の信号）と、下位２ｂｉｔ（ｂｉｔ１とｂｉｔ０）である１１２、１１０（状態番号に基づく第三の信号）を合わせた５ｂｉｔ、すなわち現状態番号１０８で見れば、現状態番号が０の場合はＳ０が、１の場合はＳ１が、２の場合はＳ２が、３の場合はＳ３が次状態番号として選ばれる。
【００４５】
続いて２分岐を実現する場合の保持方法を図７に示す。２分岐を持つ場合は図５で示したように選択方法指定信号１１７と１１８としてそれぞれ値ｅとｓが出力される。この場合、メモリ１０１の内部には図７（ｂ）に示すような構成で状態遷移ルールを保持する。ここで７０３と７０４に示すＳ０＿０、Ｓ０＿１は、状態０に対する２つの次状態番号を保持するためのメモリ１０１内の領域を示しており、イベント識別コードが０の場合は７０３のＳ０＿０、イベント識別コードが１の場合は７０４のＳ０＿１の領域の値が次状態番号となることを示している。同様に７０５と７０６に示すＳ２＿０、Ｓ２＿１は、状態２の次状態番号を保持するための１０１内の領域を示しており、イベント識別コードが０の場合は７０５のＳ２＿０、イベント識別コードが１の場合は７０６のＳ２＿１の領域の値が次状態番号となることを示している。これにより、現状態番号の上位３ｂｉｔ（状態番号に基づく第一の信号）１０２に０が入力すると、６０７の０に対応する行の４値である７０３、７０４、７０５、７０６の各領域に保持されたＳ０＿０、Ｓ０＿１、Ｓ２＿０、Ｓ２＿１が１０３に出力される。このように、２分岐を持つ状態遷移の場合は、異なる２つの現状態番号（例では０、２）に対する２つの次状態番号候補（例ではＳ０＿０、Ｓ０＿１とＳ２＿０、Ｓ２＿１）を１０１の同一行に保持させれば良い。なお組み合わせる２つの状態番号は上位３ｂｉｔを同一値としている。これは、１０３へ同時に出力される次状態番号候補が、現状態番号の上位３ｂｉｔ  １０２により判定されているためである。
【００４６】
また１０１の同一行に含める次状態番号の並び順は、左から現状態番号の小さい順の組み合わせとしており（７０３と７０４・７０５と７０６）、各組み合わせの中では左側にイベント識別コードが０の場合（７０３）、右側に１の場合（７０４）というように並べている。これはセレクタ１０４および１０５の構成と、そこで使用する現状態番号の下位から２ｂｉｔ目１１２とイベント識別コード１０９の接続で決まる。図７（ｂ）の例では、イベント識別コードが０の場合は７０８と７１０が、１の場合は７０９と７１１が選択される。また現状態番号の下位から２ｂｉｔ目１１２の値が０の場合は７０８か７０９、１の場合は７１０か７１１が選択される。そのため、ある状態からの２つの次状態番号候補を並べ、左側にイベント識別コードが０の場合、右側に１の場合のものを並べている。さらにその組み合わせを、左側に現状態番号が小さいものを格納している。
【００４７】
最後に４分岐を実現する場合の保持方法を図８に示す。４分岐を持つ場合は図４で示したように１１７と１１８へ共に値ｅが出力される。この場合、メモリ１０１の内部には図８（ｂ）に示すような構成で状態遷移ルールを保持する。ここで８０３、８０４、８０５、８０６に示すＳ０＿０、Ｓ０＿１、Ｓ０＿２、Ｓ０＿３は、いずれも状態０に対する４つの次状態番号候補を保持するための１０１内の領域を示しており、２ｂｉｔのイベント識別コード１１１、１１０がｂ００の場合は８０３のＳ０＿０、ｂ０１の場合は８０４のＳ０＿１、ｂ１０の場合は８０５のＳ０＿２、ｂ１１の場合は８０６のＳ０＿３の領域の値が次状態番号となることを示している。これにより、現状態番号の上位３ｂｉｔ  １０２に０が入力すると、６０７の０に対応する行の４値である８０３、８０４、８０５、８０６の各領域に保持されたＳ０＿０、Ｓ０＿１、Ｓ０＿２、Ｓ０＿３が１０３に出力される。このように、４分岐を持つ状態の場合は、１つの現状態番号に対する４つの次状態番号候補を１０１の同一行に保持させればよい。
【００４８】
また１０１の同一行に含める次状態番号候補の並び順は、左から、２ｂｉｔのイベント識別コード１１１、１０９の値が小さい順としている。これはセレクタ１０４および１０５の構成と、そこで使用するイベント識別コード１１１、１０９の接続で決まる。図８（ｂ）の例では、イベント識別コード１１１、１０９がｂ００の場合は８０８が、ｂ０１の場合は８０９が、ｂ１０の場合は８１０が、ｂ１１の場合は８１１が次状態番号１０６として選択される構成のため、８０３はＳ０＿０、８０４はＳ０＿１、８０５はＳ０＿２、８０６はＳ０＿３という順番になっている。
【００４９】
以上でメモリ１０１における分岐なし、２分岐、４分岐それぞれの場合の状態遷移ルールの保持方法を説明したが、これを組み合わせた例が図９となる。まず選択方法指定部１１５の構成を図９（ａ）に示す。現状態番号の上位３ｂｉｔ（状態番号に基づく第二の信号）１１６の入力値が０〜３の場合は分岐なし（１分岐）としており、９０１に示すように１１７と１１８には共にｓが出力される。１１６が４、５の場合は２分岐としており、９０２に示すように１１７と１１８にはそれぞれｅとｓが出力される。１１６が６、７の場合は４分岐としており、９０３に示すように１１７と１１８には共にｅが出力される。続いてメモリ１０１内部の保持方法であるが、分岐なしである１１５の９０１に対応する９０４の範囲は、図６に示したように各領域が１つずつ現状態番号０〜１５に対応している。一方２分岐となる１１５の９０２に対応する９０５の範囲は、２つずつの領域が現状態番号１６、１８、２０、２２それぞれに対応している。また４分岐となる１１６の９０３に対応する９０６の範囲は、４つずつの領域が現状態番号２４、２８の各々に対応している。
【００５０】
以上をまとめると、図９（ｃ）に示すようになる。分岐数が１のものは現状態番号が０〜１５の１６個、分岐数が２のものは現状態番号が１６、１８、２０、２２の４個、分岐数が４のものは現状態番号が２４、２８の２個までが実現可能となる。なお従来の構成では、図９（ｂ）のメモリでは、４分岐を８状態までしか搭載可能でなかった。
また説明に用いた図９の構成は１例であり、たとえば図１０に示すような構成も可能である。この場合、１分岐のものが１００４の領域に示すように現状態番号の０から７の８個、２分岐のものが１００５の領域に示すように現状態番号８、１０、１２、１４、１６、１８の６個、４分岐のものが１００６の領域に示すように現状態番号２０、２４、２８の３個まで実現可能な構成である。
【００５１】
このように、選択方法指定部１１５の構成により、実現可能な分岐数と状態数を決めることができる。ＬＳＩの設計時にあらかじめ選択方法指定部１１５の構成を決めてしまい、論理回路で実現することもできるし、メモリで構成しておき、ＬＳＩの製造後にプログラムによって実現可能な分岐数と状態数を決めることもできる。前者の固定式の場合、図９の例では（ｄ）に示すように、１１７の値は１１６の上位２ｂｉｔのａｎｄ論理、１１８の値は１１６の上位１ｂｉｔの値を用いるだけであり、仕様は固定となるが非常に簡単な構成となる。一方、後者のプログラム可能な方式の場合は、３ｂｉｔ幅のアドレス入力と２ｂｉｔ幅の出力を持つメモリで実現すれば良く、このメモリへの書き込みにより、実現する分岐数と状態数を柔軟に設定できるという特性を持つことができる。
【００５２】
ここで、メモリ１０１の内部構成に関して別の見方を示す。図１１（ａ）内に示されている数字は全て２進数で表現されており、１１０１には現状態番号の上位３ｂｉｔ  １０２に対応する値、１１０２には現状態番号の下位２ｂｉｔ  １１２、１１０に対応する値を示している。そして１０１内の各領域は、１１０１の値を上位３ｂｉｔ、１１０２の値を下位２ｂｉｔとした計５ｂｉｔの値を記載している。さらに図１１（ｂ）では、（ａ）の１０１内の値の途中にアンダーバーを加えており、１１０３の領域は変更なし、１１０４の領域は右側の１ｂｉｔのみアンダーバーで分離、１１０５の領域は右側２ｂｉｔをアンダーバーで分離している。そして、アンダーバーの右側の値をイベント識別コードとし、アンダーバーの右側を０に置き換えて５桁の数字を読めば、図９（ｂ）と同じになる。例えば１１０６の領域は１０１０＿１であるから、アンダーバーの右側の数字１がイベント識別コードとなり、アンダーバーの右側の数字を０とした５ｂｉｔの数字ｂ１０１００すなわち２０が状態番号となる。また１１０７の領域は１１１＿１０であるが、アンダーバーの右側の数字ｂ１０すなわち２がイベント識別コードとなり、アンダーバーの右側の数字を０とした５ｂｉｔの数字ｂ１１１００すなわち２８が状態番号となる。このように、図１１（ａ）に示す元の値のままとすれば分岐なし、同一行に横に並んだ４値の右側の１ｂｉｔをアンダーバーで分離すれば２分岐が２つ、２ｂｉｔを分離すれば４分岐が１つできることになる。なお、横１行の中に分岐無しを２つと２分岐を１つというように、１つの行の中に異なる分岐を組み合わせることも可能であるが、１０３の後段にあるセレクタの制御が複雑になるため、好ましくない構成となる。
【００５３】
［第２の実施形態］
図１４は、本発明の第２の実施形態２による状態遷移管理装置のブロック図である。図１４では、図１の形態に対して、２つの改善を行っている。１点は使用するメモリを同期式としている点、もう１点は１０１のメモリと選択方法指定部１１５を１つのメモリにまとめている点である。
【００５４】
まず前者の同期式メモリの使用であるが、一般的に高速動作のメモリは同期式が主流となっているため、図１のように非同期式メモリを使用するより同期式メモリを使用したほうが効率が良い。そこでレジスタの位置を工夫することで同期式メモリを用いた実現としている。図１では、セレクタ１０４、１０５で選択された次状態番号に対し、レジスタを通すことで現状態番号とし、１１３、１１４のセレクタ、および１０１のメモリ、１１５のブロックで使用していた。しかし同期式メモリでは、内部にアドレス入力を取り込んで保持するレジスタが設けられており、アドレス入力の次サイクルにデータが出力される。そこで図１のレジスタ１０７とメモリ１０１を合わせた形で、図１４では同期式メモリ１４０１を用いている。従って、図１４では、同期式メモリ１４０１に入力する１４０２は次状態番号の上位３ｂｉｔになっているが、現在の状態番号の一部のビットをアドレス入力として次状態番号を読み出すという点では、実施形態１と何ら相違しない。一方、セレクタ１１３と１１４の入力は図１と同様に現状態番号を必要としているため、レジスタ１４０４を使用して次状態番号１０６から現状態番号１４０３に変換している。
【００５５】
続いて後者のメモリ１０１と選択方法指定部１１５の統合であるが、図１において、いずれも現状態番号の上位３ｂｉｔを入力すると、ある値を出力するという動作であった。そこで、アドレス入力として次状態番号の上位３ｂｉｔを使用し、出力として、次状態番号候補の１０３と、セレクタ１１３、１１４向けの値１１７、１１８を出力する１つの同期式メモリ１４０１とした。構成は図１５に示すように、図１のメモリ１０１と選択方法指定部１１５のアドレス入力を共通とし、出力のビット幅を足し合わせたものとすれば良い。１４０２は次状態番号の上位３ｂｉｔであり、１５０３は、１４０２の値に応じて使用する行を示す値である。また１５０１の領域は図１のメモリ１０１に相当する領域、１５０２の領域は選択方法指定部１１５に相当する領域であり、出力は図１と同様に次状態番号候補１０３と、セレクタ１１３、１１４向け信号１１７と１１８を出力する。
【００５６】
なお上記では２つの改良を合わせて適用したが、いずれかのみを図１の形態に適用しても良い。
【００５７】
［第３の実施形態］
図１６は、本発明の第３の実施形態による状態遷移管理装置のブロック図である。図１および図１４の形態では、最大分岐数が状態遷移のルールを保存するメモリの出力幅、すなわち次状態番号候補１０３の数に制限されていた。そのため、非常に多くの分岐数を必要とする構成のためには、それに合わせたビット幅のメモリが必要となり、実現が難しい場合や、効率が良くない場合がある。これに対し図１６の構成では、同期式メモリ１４０１の他に多分岐用のメモリ１６０１を別に搭載している。分岐数が多く、メモリ１４０１では実現できない状態のみ１６０１で対応し、その他は１４０１で対応する。これにより１４０１のビット幅を極端に広くせずに済む。図１６における１６０９の枠内は図１４の動作と同じであるため、その他の部分を説明する。なおここでは、図１４に対し多分岐用の状態を付加する構成で説明するため、現状態番号１４０３および次状態番号１６０７は図１４の場合より１ｂｉｔ増やし６ｂｉｔとし、また８分岐まで対応するためイベント識別コードのビット幅を、１ｂｉｔ増やした３ｂｉｔとしている。
【００５８】
まず拡張メモリ１６０１は多分岐専用に使用する同期式メモリであり、同期式メモリ１４０１と同様の動作をする。次状態番号のビット４〜２である１４０２（状態番号に基づく第一の信号）の入力により、次サイクルに次状態番号候補１６０２を出力する。図では８個の次状態番号候補１６０２を出力する構成を示している。続いて拡張セレクタ１６０３は、８つの次状態番号候補１６０２の中から１つを、３ｂｉｔのイベント識別コード１６１０により選択し、次状態番号候補１６０４として出力する。さらにセレクタ１６０６（拡張次状態番号セレクタ）は、状態番号の最上位ビット５である１６０８により、１４０１からの出力による次状態番号候補１６０５と１６０１からの出力による次状態番号候補１６０４のいずれかを選択し、次状態番号１６０７として出力する。続いて拡張メモリ１６０１の構成を図１７に示す。図１７では、２つの８分岐可能な状態の追加に対応する場合を示している。動作は図１５等と同様であり、次状態番号の入力１４０２の値が０の場合は１７０１の０の行に保持された８つの次状態番号候補Ｓ３２＿０、Ｓ３２＿１、Ｓ３２＿２、…、Ｓ３２＿７が１６０２に出力され、１の場合は１７０１の１の行に保持された８つの次状態番号候補Ｓ４０＿０、Ｓ４０＿１、Ｓ４０＿２、…、Ｓ４０＿７が１６０２に出力される。ここで１４０１と１６０１を合わせると、図１８に示す構成のメモリのような動作として見ることができる。次状態番号の上位４ｂｉｔ（状態番号に基づく第一の信号）１４０２の入力により、その値が１８０１の値に一致した行の値が１８０６に出力される。次状態番号１４０２が０〜７の場合はメモリ１４０１が使用され、４つの次状態番号候補が出力されるが、８か９の場合はメモリ１６０１が使用され、８つの次状態番号が出力される。この１４０１と１６０１のいずれの出力を使用するかの選択を行うのがセレクタ１６０６であり、制御信号は現状態番号の最上位ビット１６０８が使用されている。
【００５９】
なお多分岐用のメモリ１６０１は、対応する状態の数１７０１が少なくても十分である場合が多いため、メモリよりはレジスタで構成するほうが適している。これにより適度なサイズのメモリ１４０１と、多少のレジスタ１６０１の組み合わせにより、１４０１の出力ビット幅を抑えながら多分岐にも対応させることができる。
【００６０】
［第４の実施形態］
図１９は、本発明の第４の実施形態による状態遷移管理装置のブロック図である。この構成により図１６のメモリ効率を更に高めることができる。図１９の構成は、図１４の構成に対し、同期式メモリ１４０１では不足する分岐数のみを拡張メモリ１９０１にて対応するものである。図１６では、多分岐の状態は全て拡張メモリ１６０１で対応していたが、図１９では多分岐の次状態番号候補のうち、メモリ１４０１に入るものは１４０１内に格納し、不足するもののみ拡張メモリ１９０１に搭載する。例えば１４０１では４分岐まで対応している場合において、図１９の構成で８分岐まで対応する場合、８つの次状態番号候補の中の４つの次状態番号候補はメモリ１４０１に格納し、残りの４つの次状態番号を１９０１に格納する。
【００６１】
図１９の詳細を説明する。まず拡張メモリ１９０１は、同時に必要とする次状態番号候補のうち、メモリ１４０１に格納しきれないものを格納する同期式メモリである。１９０２は、次状態番号１４０２の入力により１９０１から出力される次状態番号候補である。１９０３は、イベント識別コードの下位２ｂｉｔ  １９１０を用いて１９０２の中から１つの次状態番号候補１９０４を選択する拡張セレクタ、１９０６はイベント識別コードの最上位ビット  １９１１と現状態番号の最上位ビット１９０８を用いて、次状態番号候補である１９０４と１６０５のいずれかを選択し次状態番号１６０７を出力する拡張次状態番号セレクタである。拡張次状態番号セレクタ１９０６による選択は、次状態番号が１９０１と１４０１のいずれのメモリに格納されているかを判断する信号を用いるが、図１９の場合は状態番号が８以上（現状態番号の最上位ビットが１）かつイベント識別コードの値が４以上（イベント識別コードの最上位ビットが１）とすれば良いため、１９１２の論理積としている。
【００６２】
拡張メモリ１９０１の内部格納方式を図２０に示す。拡張１９０１には、メモリ１４０１へ格納しきれない次状態番号候補のみを格納するため、イベント識別コードが４以上のもののみ１４０１と同様の形式で格納している。１４０２の入力値が８の場合には、２００１が８の行に格納された状態３２の次状態番号候補の一部であるＳ３２＿４、Ｓ３２＿５、Ｓ３２＿６、Ｓ３２＿７が、１の場合には２００１が９の行に格納された状態３６の次状態番号候補の一部であるＳ３６＿４、Ｓ３６＿５、Ｓ３６＿６、Ｓ３６＿７が１９０２に出力される。図２１は図１８と同様、メモリ１４０１と１９０１を合わせた動作を説明するためのものである。２１０１は次状態番号１４０２に対応する値であるが、値が０〜７の場合は１４０１単体の場合と同様に動作し、１４０２の入力値に応じた２００２、２００３、２００４の中のいずれかの行の次状態番号候補４つが１０３に出力され、セレクタ２００６にて１つの次状態番号１６０７が選択される。一方、１４０２の入力値が８か９の場合は、２１０１が８か９の行すなわち２００５の領域から選択され、８個の次状態番号候補が、１４０１からのものは１０３へ、１９０１からのものは１９０２へ出力され、セレクタ２００６により１つが選択され次状態番号１６０７となる。
【００６３】
図１６、１９いずれの場合でも、２つのメモリを合わせて図１８、１９のようにＬ字型のメモリを仮想的に構成しているが、多分岐用に導入するメモリ１６０１、１９０１をレジスタで構成することを考えると、そのビット数がより少なくなる図１９の構成のほうが面積の観点で望ましいと言える。
【実施例１】
【００６４】
図１２の例を用いて、本発明の図１の構成の使用例を示す。図１２（ａ）が対象となる状態遷移図である。まず状態番号の振り方として、分岐なしのもの、２分岐のもの、４分岐以内のものとなるようにしている。すると分岐なしのものが６個、２分岐のものが２個、４分岐のものが１つであるため、図１２（ｂ）のメモリに示すように、分岐無しを１２０１の８領域で８状態、２分岐を１２０２の４領域で２状態、４分岐を１２０３の４領域１状態が必要となる。その際の選択方法指定部１１５の構成は図１２（ｃ）に示す通りであり、１２１０の範囲が分岐なし、１２１１の範囲が２分岐、１２１２の範囲が４分岐となっている。そして図１２（ｂ）の各領域の内、左上の値が現状態番号とイベント識別コードの組み合わせであり、右下の値が次状態番号を示している。例えば１２０４の領域は、左上のＳ０が、現状態番号０の次状態番号を示しており、右下の値１２が、次状態番号が１２であることを示している。同様に１２０５の領域は、状態１の次状態番号が１０であることを示している。また１２０６、１２０７、１２０８、１２０９は状態１２の次状態番号を保持する領域であり、イベント識別コードが０の時は１２０６の領域を使用し、次状態番号が１、イベント識別コードが１の時は１２０７の領域を使用し、次状態番号が２、イベント識別コードが２の時は１２０８の領域を使用し、次状態番号が８、イベント識別コードが３の時は１２０９の領域を使用するが、（ａ）の状態遷移図ではそのような場合が無いのでドントケア”−−“としている。なお動作時に１０３へ出力されるのは領域右下の値である。このようにして図１２（ａ）の状態遷移図を実装すると、図１２（ｂ）に示すように、縦に４個、横に４個の計１６領域があれば十分であることが分かる。
【００６５】
一方、参考として従来の方式を図１３に示す。図１３（ａ）は図１２の状態遷移図と同じ遷移をするものであるが、状態番号が０からの連続値となるように番号を付け替えている。実装結果は図１３（ｂ）となるが、どの現状態番号１３０１に対しても、それぞれ４分岐の領域を有しているため、縦方向に状態数と同じ９行が必要となり、計３６領域を必要としている。これは本発明の場合の図１２に対して２倍以上のサイズとなっている。図１２（ｂ）と図１３の（ｂ）を比べれば一目瞭然であるが、使用されない領域を示すドントケア”−−“が、従来の図１３（ｂ）では非常に多いことが分かる。逆に本発明の図１２（ｂ）では、ドントケアが少なく、従来に比べて非常に効率よく状態遷移のルールをメモリ内に格納できていることがわかる。
【実施例２】
【００６６】
次に図１６および図１９の構成時の使用例を示す。図２２が例として用いる状態遷移図である。２２０１に示す状態３２が７分岐を持つ状態であり、次状態番号として１２、１、２、３、１４、４、５の計７個を持つ。そのため、図１や図１４のような４分岐までの構成では、このままの状態遷移を実現することはできない。図１や図１４において、次状態番号候補の出力を７個まで増やせば図２２の状態遷移図を実現可能であるが、メモリ１０１や１４０１のビット幅が非常に広くなってしまう。そのような場合には図１６や図１９の構成が有効となる。
【００６７】
まず図１６の構成におけるメモリ１４０１および拡張メモリ１６０１の内部への格納方式を図２３に示す。メモリ１４０１の格納方式は図１２の場合と同様であり、２３０２の領域には分岐無しの状態の情報が、２３０３の領域には２分岐の状態の情報が格納されている。例えば２３０５の領域には左上のＳ２が示すように状態２の次状態番号が格納されており、その値は１６である。ゆえに状態２の次は状態１６であることを示している。
【００６８】
また２３０６と２３０７の領域は、左上のＳ１２＿０、Ｓ１２＿１が示すように状態１２の次の状態番号を格納しており、イベント識別コードが０の場合はＳ１２＿０の領域に格納されている値６が、１の場合はＳ１２＿１の領域に格納されている値７が次状態番号となることを示している。一方、１４０１に格納可能な４分岐を超えた７分岐となる状態３２に関しては、拡張メモリ１６０１に格納されている。例えば２３０６の領域は左上のＳ３２＿０が示すように、状態３２においてイベント識別コードが０の場合の次状態番号が１２であることを、２３０７の領域は左上のＳ３２＿４が示すように、同じく状態３２においてイベント識別コードが４の場合は次状態番号が１４であることを示している。なお状態３２は７分岐であるため、８分岐に対応する２３０４のうち使用されない２３０８の領域の値はドントケアとしている。このようにメモリ１４０１と１６０１に分割されてはいるが、次状態番号１４０２の入力に一致する２３０１の値の行の内容が次状態番号候補１０３もしくは１６０２として出力され、図１６のセレクタ１６０６により次状態番号１６０７として選択される。
【実施例３】
【００６９】
次に図１９の構成におけるメモリ１４０１および拡張メモリ１９０１の内部への格納方式を図２４に示す。メモリ１４０１の格納方式は図２３の場合と同様であるが、１４０１に収まらない分岐数を持つ状態に関しても、１４０１の最大分岐数である４個の次状態番号は１４０１の中に格納し、収まらない残りの次状態番号のみメモリ１９０１に格納している。そのため、分岐なしのルールを格納する２４０２の範囲、および２分岐のルールを格納する２４０３の範囲は、それぞれ図２３の２３０２の範囲および２３０３の範囲と全く同じになっている。一方、メモリ１４０１に収まらない７分岐を持つ状態３２に関しては、イベント識別コードが０〜３のものが１４０１内に、４〜７のものが１９０１内に格納されている。状態３２においてイベント識別コードが０の場合の次状態番号の格納は、１４０１内の領域２４０５が使用され、ここに次状態番号１２が格納されている。同様にイベント識別コードが１の場合は領域２４０６が、２の場合は領域２４０７が、３の場合は領域２４０８が使用され、それぞれ次状態番号１、２、３が格納されている。一方、イベント識別コードが４の場合の次状態番号は、拡張メモリ１９０１内の領域２４０９が使用され、ここに次状態番号１４が格納されている。同様にイベント識別コードが５の場合は領域２４１０が、６の場合は領域２４１１が、７の場合は領域２４１２が使用され、それぞれ次状態番号４、５、ドントケア（未使用）が格納されている。
【００７０】
ここまで説明に用いてきた状態数や分岐数、メモリのサイズ、状態番号内から切り出すビット数やビットの位置などの数は、あくまでも例として示したものであり、記載した値に限られるものではない。
【００７１】
本発明は、例えば図９、１０に示すように、メモリに対する１回のアクセスで読み出せる範囲（１ワード）に、複数の状態番号（現状態番号）各々に対応する、１つまたは複数の次状態番号候補を格納するようにメモリマッピングしている。さらに、このメモリマッピングは、メモリ全体にわたって、１ワードに対応付ける状態番号（現状態番号）の数を固定的にしてもよい。また、さらには、１ワードに対応付ける状態番号（現状態番号）の数をワード毎に変え、１ワードに対応付ける状態番号（現状態番号）の数が異なるようにしてもよい。
【００７２】
状態番号に基づく第一乃至第三の信号は、それぞれ、状態番号の一部のビット信号として説明したが、例えば、状態信号の全ビットあるいは一部のビットをデコードした信号を用いても構わない。また、イベント識別信号は狭く解釈する必要はなく、何らかのイベントに基づく信号であればよい。
【００７３】
また、イベントの発生と状態遷移については、様々な扱いが可能である。たとえば、イベントが１クロック毎に必ず発生するものであれば、１クロック毎に次の状態へ遷移する構成にすることができる。また、イベントが１クロック毎に必ず発生しない場合でも、イベントが発生していないことを一つのイベントとして扱い、１クロック毎に次の状態へ遷移するように構成することもできる。さらに、なんらかのイベントが発生したことを検知する回路（たとえば、各イベント信号のＡＮＤ回路等を用いて構成できる）を設け、イベントが発生したときに、次の状態に遷移する構成にすることもできる。
【００７４】
以上、本発明を実施例に即して説明したが、本発明は上記実施例の構成にのみ制限されるものでなく、本発明の範囲内で当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【産業上の利用可能性】
【００７５】
本発明の活用例としては、所望のアプリケーションをプログラム可能なデバイスに搭載する際、状態遷移とデータパスに分離するアーキテクチャにおいて、状態遷移を実現するハードウェアの構成として使用することができる。例えば特許文献１に示されているようなアレイ型プロセッサにおいて、状態遷移を司る状態遷移管理装置に適用することができる。
【図面の簡単な説明】
【００７６】
【図１】本発明の第１の実施形態の構成を示すブロック図である。
【図２】本発明の第１の実施形態における選択方法指定部１１５の内部構成を示す図である。
【図３】本発明の第１の実施形態において、４分岐の動作を説明する図である。
【図４】本発明の第１の実施形態において、２分岐の動作を説明する図である。
【図５】本発明の第１の実施形態において、１分岐の動作を説明する図である。
【図６】本発明の第１の実施形態において、メモリ１０１と選択方法指定部１１５の４分岐時の動作を説明する図である。
【図７】本発明の第１の実施形態において、メモリ１０１と選択方法指定部１１５の２分岐時の動作を説明する図である。
【図８】本発明の第１の実施形態において、メモリ１０１と選択方法指定部１１５の１分岐時の動作を説明する図である。
【図９】本発明の第１の実施形態において、メモリ１０１と選択方法指定部１１５に１、２、４分岐の情報を同時に格納する場合の内部構成例を示す図である。
【図１０】本発明の第１の実施形態において、メモリ１０１と選択方法指定部１１５に１、２、４分岐の情報を同時に格納する場合の、図９とは異なる内部構成例を示す図である。
【図１１】本発明の第１の実施形態において、メモリ１０１内部における１、２、４分岐を混在させる考え方を説明する図である。
【図１２】本発明の第１の実施形態の使用例を示す図である。
【図１３】図１２と同じ状態遷移を従来の構成で実現した場合を示す図である。
【図１４】本発明の第２の実施形態を示すブロック図である。
【図１５】本発明の第２の実施形態のメモリ１４０１の内部構成を示す図である。
【図１６】本発明の第３の実施形態を示す図である。
【図１７】本発明の第３の実施形態のメモリ１６０１の内部構成を示す図である。
【図１８】本発明の第３の実施形態におけるメモリ１４０１と１６０１を合わせた動作を説明する図である。
【図１９】本発明の第４の実施形態を示すブロック図である。
【図２０】本発明の第４の実施形態のメモリ１９０１の内部構成を示す図である。
【図２１】本発明の第４の実施形態におけるメモリ１４０１と１９０１を合わせた動作を説明する図である。
【図２２】本発明の第３、第４の実施形態の使用例として使用する状態遷移図である。
【図２３】本発明の第３の実施形態にて図２２の状態遷移図を実現した場合のメモリ１４０１と１６０１の内部を示す図である。
【図２４】本発明の第４の実施形態にて図２２の状態遷移図を実現した場合のメモリ１４０１と１９０１の内部を示す図である。
【図２５】従来のデータ処理装置の構成を示すブロック図である。
【符号の説明】
【００７７】
１０１：メモリ
１０２：現状態番号の一部（現状態番号の上位３ビット、状態番号に基づく第一の信号）
１０３、１６０２：次状態番号候補
１０４、１０５：セレクタ（次状態番号セレクタ）
１０６：次状態番号
１０７、１４０４：レジスタ
１０８、１３０１、１４０３：現状態番号（状態番号）
１０９、１１１：イベント識別コード（イベントに基づく信号）
１１０、１１２：現状態番号１０８の一部のビット（状態番号に基づく第三の信号）
１１３、１１４：セレクタ（選択信号セレクタ）
１１５：選択方法指定部
１１６：現状態番号の一部のビット（状態番号に基づく第二の信号）
１１７、１１８：選択方法指定信号
１５１、１５２：選択信号
３０１、４０２、５０２：現状態
３０６、４０５：イベント識別コードの値
１４０１：同期式メモリ（メモリ１０１と選択方法指定部１１５の機能を含む）
１４０２：次状態番号の一部（状態番号に基づく第一の信号）
１４０３：現状態番号
１６０１、１９０１：拡張メモリ
１６０３：拡張セレクタ
１６０６、１９０６：セレクタ（拡張次状態番号セレクタ）
【図１】
2010045581.tif 000003
【図２】
2010045581.tif 000004
【図３】
2010045581.tif 000005
【図４】
2010045581.tif 000006
【図５】
2010045581.tif 000007
【図６】
2010045581.tif 000008
【図７】
2010045581.tif 000009
【図８】
2010045581.tif 000010
【図９】
2010045581.tif 000011
【図１０】
2010045581.tif 000012
【図１１】
2010045581.tif 000013
【図１２】
2010045581.tif 000014
【図１３】
2010045581.tif 000015
【図１４】
2010045581.tif 000016
【図１５】
2010045581.tif 000017
【図１６】
2010045581.tif 000018
【図１７】
2010045581.tif 000019
【図１８】
2010045581.tif 000020
【図１９】
2010045581.tif 000021
【図２０】
2010045581.tif 000022
【図２１】
2010045581.tif 000023
【図２２】
2010045581.tif 000024
【図２３】
2010045581.tif 000025
【図２４】
2010045581.tif 000026
【図２５】
2010045581.tif 000027