(57)【特許請求の範囲】
【請求項１】
入力信号伝播路、出力信号伝播路、入出力信号伝播路から選ばれる３本以下の信号伝播路と連結される演算子からなる非同期回路であって、
前記演算子が、
２つの入力信号伝播路と１つ出力信号伝播路とに接続された演算手段であって、前記２つの入力信号伝播路のいずれかから演算手段に入力信号が入力された場合に、前記出力信号伝播路に出力信号を出力するように機能させ、更に前記２つの入力信号伝播路から演算手段に入力信号が同時に入力された場合に、前記出力信号伝播路に順次２つの出力信号を出力するように機能させる第１の演算手段と、
３つの入出力信号伝播路とに接続された演算手段であって、前記３つの入出力信号伝播路のうち２つから入力信号が演算手段に入力された場合に、残りの入出力信号伝播路から出力信号が出力されるように機能させる第２の演算手段と、
１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連続された演算手段であって、前記入力信号伝播路から入力信号が演算手段に入力された場合に前記入出力信号伝播路から出力信号が出力されるように機能させ、前記入出力信号伝播路から入力信号が演算手段に入力された場合に、前記出力信号伝播路から出力信号が出力されるように機能させる第３の演算手段と、
２つの入出力信号伝播路とに連結され、かつ０と１のいずれかの状態を持つ演算手段であって、初期状態は１の状態であり、ひとつの入出力信号伝播路から入力信号を演算手段に入力された場合に、どちらの入出力伝播路にも出力信号を出力せずに演算手段を０の状態とし、残りの入出力信号伝播路から入力信号が演算手段に入力された場合に、演算手段が１の状態であれば、前記のひとつの入出力信号伝播路から出力信号を出力し、演算手段が０の状態であれば、前記残りの入出力信号伝播路から出力信号を出力して演算手段の状態を１に戻し、両方の入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる第４の演算手段と、
ひとつの入力信号伝播路と２つの出力信号伝播路とに連結された演算手段であって、前記入力信号伝播路から演算手段に入力信号が入力された場合、前記２つの出力信号伝播路から出力信号を出力するように機能させる第５の演算手段と、
からなる非同期回路。
【請求項２】
前記第４の演算手段の代りに、又は前記第４の演算手段とともに
前記演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連結され、かつ０と１のいずれかの状態を持つ演算手段であって、
初期状態は１の状態であり、前記入出力信号伝播路から入力信号が演算手段に入力された場合に、出力伝播路と入出力伝播路に出力信号を出力せずに演算手段を０の状態とし、入力信号伝播路からの入力信号を入力された場合に、演算手段が１の状態であれば、前記出力信号伝播路から出力信号を出力し、演算手段が０の状態であれば、前記入出力信号伝播路から出力信号を出力して演算手段の状態を１に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる演算手段を用いる請求項１に記載の非同期回路。
【請求項３】
前記第４の演算手段の代りに、又は前記第４の演算手段とともに
前記演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連結された、かつ０と１のいずれかの状態を持つ演算手段であって、初期状態は１の状態であり、前記入力信号伝播路から入力信号が演算手段に入力された場合に、出力伝播路と入出力伝播路に出力信号を出力せずに演算手段を０の状態とし、入出力信号伝播路からの入力信号が入力された場合に、演算手段が１の状態であれば、前記入出力信号伝播路から出力信号を出力し、演算手段が０の状態であれば、前記出力信号伝播路から出力信号を出力して演算手段の状態を１に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる演算手段を用いる請求項１に記載の非同期回路。
【請求項４】
請求項１〜３のいずれか１項に記載の非同期回路を含むコンピュータ。
【請求項５】
２つの入力信号伝播路と１ つ出力信号伝播路とに接続された演算手段であって、前記２つの入力信号伝播路のいずれかから演算手段に入力信号が入力された場合に、前記出力信号伝播路に出力信号を出力するように機能させ、更に前記２つの入力信号伝播路から演算手段に入力信号が同時に入力された場合に、前記出力信号伝播路に順次２つの出力信号を出力するように機能させる第１の演算手段と、
３つの入出力信号伝播路とに接続された演算手段であって、前記３つの入出力信号伝播路のうち２つから入力信号が演算手段に入力された場合に、残りの入出力信号伝播路から出力信号が出力されるように機能させる第２の演算手段と、
１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連続された演算手段であって、前記入力信号伝播路から入力信号が演算手段に入力された場合に前記入出力信号伝播路から出力信号が出力されるように機能させ、前記入出力信号伝播路から入力信号が演算手段に入力された場合に、前記出力信号伝播路から出力信号が出力されるように機能させる第３の演算手段と、
２つの入出力信号伝播路とに連結され、かつ０と１のいずれかの状態を持つ演算手段であって、初期状態は１の状態であり、ひとつの入出力信号伝播路から入力信号が演算手段に入力された場合に、どちらの入出力伝播路にも出力信号を出力せずに演算手段を０の状態とし、残りの入出力信号伝播路に入力信号を演算手段に入力された場合に、演算手段が１の状態であれば、前記のひとつの入出力信号伝播路から出力信号を出力し、演算手段が０の状態であれば、前記残りの出力信号伝播路から出力信号を出力して演算手段の状態を１に戻し、両方の入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる第４の演算手段と、
ひとつの入力信号伝播路と２つの出力信号伝播路とに連結された演算手段であって、前記入力信号伝播路から演算手段に入力信号が入力された場合、前記２つの出力信号伝播路から出力信号を出力するように機能させる第５の演算手段と、
からなる基本演算子群を用いた非同期回路の設計方法。
【請求項６】
前記第４の演算手段の代りに、又は前記第４の演算手段とともに
前記演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連結された、かつ０と１のいずれかの状態を持つ演算手段であって、初期状態は１の状態であり、前記入出力信号伝播路から入力信号が演算手段に入力された場合に、出力伝播路と入出力伝播路に出力信号を出力せずに演算手段を０の状態とし、入力信号伝播路からの入力信号を入力された場合に、演算手段が１の状態であれば、前記出力信号伝播路から出力信号を出力し、演算手段が０の状態であれば、前記入出力信号伝播路から出力信号を出力して演算手段の状態を１に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる演算手段を用いる請求項５に記載の非同期回路の設計方法。
【請求項７】
前記第４の演算手段の代りに、又は前記第４の演算手段とともに
前記演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連結された、かつ０と１のいずれかの状態を持つ演算手段であって、
初期状態は１の状態であり、前記入力信号伝播路から入力信号が演算手段に入力された場合に、出力伝播路と入出力伝播路に出力信号を出力せずに演算手段を０の状態とし、入出力信号伝播路からの入力信号を入力された場合に、演算手段が１の状態であれば、前記入出力信号伝播路から出力信号を出力し、演算手段が０の状態であれば、前記出力信号伝播路から出力信号を出力して演算手段の状態を１に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる演算手段を用いる請求項５に記載の非同期回路の設計方法。
【請求項８】
請求項５、請求項６、又は請求項７に記載の回路の設計方法を用いて設計された非同期回路を有するコンピュータ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、新規な基本演算子（モジュール）群からなる非同期回路、および非同期回路の設計方法、およびコンピュータなどに関する。
【０００２】
【従来の技術】
オートマトンは、例えば、コンピュータなどの基本回路を設計する際などに用いられる。例えば、オートマトンを用いた情報検索回路が知られている（例えば、特許文献１参照）。基本演算子群は、このオートマトンの考え方を利用し、種々の回路の設計などに利用できる。
【０００３】
また、セルオートマトンを用いたデータ記録システム及び伝送システムが知られている（例えば、特許文献２参照）。また、ニューロセルラオートマトンおよび最適化装置が知られている（例えば、特許文献３参照）。このように、オートマトン、およびセルラオートマトンは、コンピュータシステムの設計などに利用されてきた。
【０００４】
なお、Ｋｅｌｌｅｒ（ケラー）は、ケラー氏の条件のもとで、全ての耐遅延回路（非同期回路）を設計することができる基本モジュールの群を提案した。後にＰａｔｒａ（パトラ）は、基本モジュール群[ＭＥＲＧＥ、ＦＯＲＫ、ＴＲＩＡ、ＳＥＱＵＥＮＣＥＲ]を提案した。この基本モジュールを用いれば、演算などに必要とされる全ての非同期回路を設計することができる。また、この基本モジュール群は、ケラー氏が提案した全ての条件を満足する。以下、モジュールＭＥＲＧＥ、ＦＯＲＫ、ＴＲＩＡ、ＳＥＱＵＥＮＣＥＲの作用を説明する。
【０００５】
図２に、ＭＥＲＧＥを示す。
ＭＥＲＧＥによれば、入力ライン（信号伝播路ともいう）Ｉ1（Ｉ2）から入力信号を入力されて、出力ラインＯに出力信号を出力される。Ｉ1とＩ2に同時に入力信号を入力されることは禁止される。
【０００６】
図３に、ＦＯＲＫを示す。
ＦＯＲＫは、演算部を、ひとつの入力信号伝播路と２つの出力信号伝播路とに連結された演算部であって、前記入力信号伝播路から演算部に入力信号が入力された場合、前記２つの出力信号伝播路から出力信号を出力するように機能させるモジュールであり、演算手段を、ひとつの入力信号伝播路と２つの出力信号伝播路とに連結された演算手段であって、前記入力信号伝播路から演算手段に入力信号が入力された場合、前記２つの出力信号伝播路から出力信号を出力するように機能させる演算手段として機能する。（本発明の非同期回路においては、第５の演算手段として機能する。）
【０００７】
ＦＯＲＫによれば、入力ラインＩから入力信号が入力されて、出力ラインＯ1とＯ2に出力信号が出力される。
【０００８】
図４に、ＴＲＩＡを示す。
ＴＲＩＡによれば、入力ラインＩ1（Ｉ2）＜Ｉ3＞とＩ2（Ｉ3）＜Ｉ1＞から入力信号が入力されて、出力ラインＯ3（Ｏ1）＜Ｏ2＞に出力信号が出力される。Ｉ1、Ｉ2、Ｉ3の全てのラインに、同時に入力信号を入力されることは禁止される。入力ラインのひとつが受領状態（信号を受け取った状態）になるときに、他の入力ラインに入力信号を入力されるまでに、待ち状態に維持される。
【０００９】
図５に、ＳＥＱＵＥＮＣＥＲを示す。
ＳＥＱＵＥＮＣＥＲは以下のように作用する。入力ラインｃと、入力ラインａi（ｂi）から入力信号が入力された場合に、出力ラインａo（ｂo）に出力信号が出力される。入力ラインｃとともに、入力ラインａiと入力ラインｂiに同時に信号が入力された場合は、ａiとｂiの中から任意に選ばれた信号のみが対応するａoかｂoの出力ラインに出力され、残ったラインｂiかａi上の信号は、次の入力信号が入力ラインｃに入力されるまで待ちつづける。
【００１０】
【特許文献１】
特許第２６９６８３２号公報
【特許文献２】
特許第３１４６３５５号公報
【特許文献３】
特許第３０６９０５８号公報
【００１１】
【発明が解決しようとする課題】
パトラ氏による基本モジュール群のそれぞれのモジュールは、入力、出力の信号伝播路を数多く（例えば、５〜６個）必要とするものであり、より簡便な非同期回路を設計し得る基本演算子（モジュール）群が望まれている。
【００１２】
【課題を解決するための手段】
本発明では、入力ライン、出力ライン、入出力ラインからなるライン（信号伝播路ともいう）のうち多くても３つのを有する新規基本モジュール群を用いた非同期回路及びその設計方法などを提供する。本発明は、公知の基本モジュールＦＯＲＫに、新たな基本モジュール群[Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ]を加えた基本演算子群からなる非同期回路などを提供するものである。そして、これら基本モジュールの組は、耐遅延（Delay Insensitive）回路において汎用性がある。すなわち、これらの基本モジュール群を用いることで、全ての耐遅延非同期回路を設計することができる（例えば、図１参照）。
【００１３】
より具体的には、以下の発明などを提供する。
（１）入力信号伝播路、出力信号伝播路、入出力信号伝播路から選ばれる３本以下の信号伝播路と連結される演算子からなる非同期回路。
（２）  前記演算子が、
２つの入力信号伝播路と１つ出力信号伝播路とに接続された演算手段であって、前記２つの入力信号伝播路のいずれかから演算手段に入力信号が入力された場合に、前記出力信号伝播路に出力信号を出力するように機能させ、更に前記２つの入力信号伝播路から演算手段に入力信号が同時に入力された場合に、前記出力信号伝播路に順次２つの出力信号を出力するように機能させる第１の演算手段と、
３つの入出力信号伝播路とに接続された演算手段であって、前記３つの入出力信号伝播路のうち２つから入力信号が演算手段に入力された場合に、残りの入出力信号伝播路から出力信号が出力されるように機能させる第２の演算手段と、
１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連続された演算手段であって、前記入力信号伝播路から入力信号が演算手段に入力された場合に前記入出力信号伝播路から出力信号が出力されるように機能させ、前記入出力信号伝播路から入力信号が演算手段に入力された場合に、前記出力信号伝播路から出力信号が出力されるように機能させる第３の演算手段と、
２つの入出力信号伝播路とに連結され、かつ０と１のいずれかの状態を持つ演算手段であって、
初期状態は１の状態であり、ひとつの入出力信号伝播路から入力信号を演算手段に入力された場合に、どちらの入出力伝播路にも出力信号を出力せずに演算手段を０の状態とし、残りの入出力信号伝播路から入力信号が演算手段に入力された場合に、演算手段が１の状態であれば、前記のひとつの入出力信号伝播路から出力信号を出力し、演算手段が０の状態であれば、前記残りの出力信号伝播路から出力信号を出力して演算手段の状態を１に戻し、両方の入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる第４の演算手段と、
ひとつの入力信号伝播路と２つの出力信号伝播路とに連結された演算手段であって、前記入力信号伝播路から演算手段に入力信号が入力された場合、前記２つの出力信号伝播路から出力信号を出力するように機能させる第５の演算手段と、
からなる（１）に記載の非同期回路。
（３）前記第４の演算手段の代りに、又は前記第４の演算手段とともに
前記演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連結され、かつ０と１のいずれかの状態を持つ演算手段であって、
初期状態は１の状態であり、前記入出力信号伝播路から入力信号が演算手段に入力された場合に、出力伝播路と入出力伝播路に出力信号を出力せずに演算手段を０の状態とし、入力信号伝播路からの入力信号を入力された場合に、演算手段が１の状態であれば、前記出力信号伝播路から出力信号を出力し、演算手段が０の状態であれば、前記入出力信号伝播路から出力信号を出力して演算手段の状態を１に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる演算手段を用いる（２）に記載の非同期回路。
（４）前記第４の演算手段の代りに、又は前記第４の演算手段とともに
前記演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連結された、かつ０と１のいずれかの状態を持つ演算手段であって、
初期状態は１の状態であり、前記入力信号伝播路から入力信号が演算手段に入力された場合に、出力伝播路と入出力伝播路に出力信号を出力せずに演算手段を０の状態とし、入出力信号伝播路からの入力信号が入力された場合に、演算手段が１の状態であれば、前記入出力信号伝播路から出力信号を出力し、演算手段が０の状態であれば、前記出力信号伝播路から出力信号を出力して演算手段の状態を１に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる演算手段を用いる（２）に記載の非同期回路。
（５）（１）〜（４）のいずれかに記載の非同期回路を含むコンピュータ。
【００１４】
（６）２つの入力信号伝播路と１つ出力信号伝播路とに接続された演算手段であって、前記２つの入力信号伝播路のいずれかから演算手段に入力信号が入力された場合に、前記出力信号伝播路に出力信号を出力するように機能させ、更に前記２つの入力信号伝播路から演算手段に入力信号が同時に入力された場合に、前記出力信号伝播路に順次２つの出力信号を出力するように機能させる第１の演算手段と、
３つの入出力信号伝播路とに接続された演算手段であって、前記３つの入出力信号伝播路のうち２つから入力信号が演算手段に入力された場合に、残りの入出力信号伝播路から出力信号が出力されるように機能させる第２の演算手段と、
１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連続された演算手段であって、前記入力信号伝播路から入力信号が演算手段に入力された場合に前記入出力信号伝播路から出力信号が出力されるように機能させ、前記入出力信号伝播路から入力信号が演算手段に入力された場合に、前記出力信号伝播路から出力信号が出力されるように機能させる第３の演算手段と、
２つの入出力信号伝播路とに連結され、かつ０と１のいずれかの状態を持つ演算手段であって、
初期状態は１の状態であり、ひとつの入出力信号伝播路から入力信号が演算手段に入力された場合に、どちらの入出力伝播路にも出力信号を出力せずに演算手段を０の状態とし、残りの入出力信号伝播路に入力信号を演算手段に入力された場合に、演算手段が１の状態であれば、前記のひとつの入出力信号伝播路から出力信号を出力し、演算手段が０の状態であれば、前記残りの出力信号伝播路から出力信号を出力して演算手段の状態を１に戻し、両方の入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる第４の演算手段と、
ひとつの入力信号伝播路と２つの出力信号伝播路とに連結された演算手段であって、前記入力信号伝播路から演算手段に入力信号が入力された場合、前記２つの出力信号伝播路から出力信号を出力するように機能させる第５の演算手段と、
からなる基本演算子群を用いた非同期回路の設計方法。
（７）  前記第４の演算手段の代りに、又は前記第４の演算手段とともに
前記演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連結された、かつ０と１のいずれかの状態を持つ演算手段であって、
初期状態は１の状態であり、前記入出力信号伝播路から入力信号が演算手段に入力された場合に、出力伝播路と入出力伝播路に出力信号を出力せずに演算手段を０の状態とし、入力信号伝播路からの入力信号を入力された場合に、演算手段が１の状態であれば、前記出力信号伝播路から出力信号を出力し、演算手段が０の状態であれば、前記入出力信号伝播路から出力信号を出力して演算手段の状態を１に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる演算手段を用いる（６）に記載の非同期回路の設計方法。
（８）前記第４の演算手段の代りに、又は前記第４の演算手段とともに
前記演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連結された、かつ０と１のいずれかの状態を持つ演算手段であって、
初期状態は１の状態であり、前記入力信号伝播路から入力信号が演算手段に入力された場合に、出力伝播路と入出力伝播路に出力信号を出力せずに演算手段を０の状態とし、入出力信号伝播路からの入力信号を入力された場合に、演算手段が１の状態であれば、前記入出力信号伝播路から出力信号を出力し、演算手段が０の状態であれば、前記出力信号伝播路から出力信号を出力して演算手段の状態を１に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる演算手段を用いる（６）に記載の非同期回路の設計方法。
（９）（６）、（７）、又は（８）に記載の回路の設計方法を用いて設計された非同期回路を有するコンピュータ。
【００１５】
パトラ氏とケラー氏による基本モジュール群と異なり、ラインは、双方向（ｂｉ−ｄｉｒｅｃｔｉｏｎａｌ）であってもよく、ラインは、バッファーとして機能しても良い。ここで、双方向とは、ひとつのラインがモジュールへの入力ラインとして機能しても、出力ラインとして機能しても良いことを意味する。すなわち、たとえば、セルラオートマトン上では、このような回路を実装するために信号伝播路が、入力信号伝播路または出力信号伝播路だけではなく、入出力信号伝播路としての機能があれば良い。
【００１６】
【発明の実施の形態】
本発明は、[Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ]を有する基本演算子群を用いた非同期回路の設計方法、及びこれら基本演算子群からなる非同期回路などに関する。また、本発明の基本演算子群にオ−トマン法を適用することにより、単純な条件を用いて、例えば、カオス状態などの複雑な事象、生物や生体に類似する複雑なパターン等を導くことが可能である。
【００１７】
なお、オートマトンに関する一般的な用語については、例えば、飯島泰蔵編集森北出版株式会社発行  基礎情報工学シリーズ５  オートマトン・言語理論などに記載されている。
【００１８】
本明細書において、信号は、ラインにおける値または状態の変化である。そして、信号はモジュールの出力ラインから、接続された他のモジュールの入力ラインへと移動する。信号は、図６（ａ）のようなのトークンとして表される。そして、あるモジュールに入力されたが、他の信号が到着するまで当モジュールは出力されない信号である待ち状態信号（ペンディング信号）は、図６（ｂ）のように表される。
【００１９】
信号は、モジュール間の情報伝達に用いる。モジュールは、そのモジュールに連結された他のモジュールからの入力信号を受け取り、その後、その信号を処理して、時にはそのモジュールの状態を変化させて、出力ラインから出力信号を出す。モジュールの動作は、入力信号により駆動されるため、セントラルクロック（中央駆動）信号は必要とされない。モジュールは、記録された状態についての情報と新たな入力情報との組み合わせによって次の動作が決まるような順序機械（Sequential Machine）であって、その記録される情報は、有限である。順序機械は、Ｎ＝（Ｑ、ｑ0、Σ、Δ、ｆ、ｇ）で定義される。ここで、Ｑは、状態の有限集合であり、ｑ0は初期状態であり、Σは入力記号の有限集合であり、Δは、出力記号の有限集合であり、ｆは、ｆ：Ｑ×Σ→Ｑのような状態遷移関数であり、ｇは、ｇ：Ｑ×Σ→Δのような出力関数である。
【００２０】
以下本明細書における定義等を説明する。
定義１．耐遅延回路（Delay Insensitive (DI) Circuit）
耐遅延回路は特殊なクラスの非同期回路であり、その動作の正確性は、モジュールまたは相互接続ラインにおける不定遅延の影響を受けない。DI回路の動作は信号で駆動される。信号がモジュールに到達すると、そのモジュールはそれに対して働きかける。その結果、通常、その相互接続ライン上に１つ以上の出力信号を出され、その後、そのモジュールは、その次の入力信号を受信するまで待ち状態になる。
【００２１】  ＤＩ回路は、モジュール間の入出力のタイミングに無関係であるため、（１）低消費電力と低熱損失、（２）クロック信号分配用の配線不要、（３）高速な平均速度、（４）物理条件と実装の依存度が小さいこと、そして（５）モジュール設計技術によく適していることなど、同期タイプに比べて非同期回路の完全な利点を有している（詳細については[Hauck, S. Asynchronous design methodologies: an overview. Proc. IEEE 83(1), 69-93 (1995)、Patra, P. Approaches to design of circuits for low-power computation, Ph.D. thesis. (The university of Texas at Austin, 1995).]を参照）。但し、中央クロックが無いため、ANDゲートとNOTゲートなど、論理ゲートだけを使用したDI回路の設計は不可能である[Martin, A.J. The limitations to delay-insensitivity in asynchronous circuits. Proc. 6th MIT Conf. on Advanced Research in VLSI (MIT Press, MA: Cambridge) 263-278 (1990)、Brzozowski, J.A., Ebergen, C. On the delay-sensitivity of gate networks. IEEE Tr. Comp. 41(11), 1349-1360 (1992)].
]。この結果、ハードウェア（たとえば、セルオートマトンとして構成されたハードウェア）にDI回路を実装するためには、任意のDI回路の構築に使用する基関数モジュールの集合を定義することが必要となる。
【００２２】
双方向およびバッファリングラインの使用を可能にする基関数モジュールの耐遅延回路構成万能性がある集合が提示されている（Lee, J., Peper, F., Adachi, S. & Morita, K. Compact designs of universal delay-insensitive circuits with bi-directional and buffering lines. Submitted to IEEE Transactions on Computers (June 2002).）。この集合内の基関数は、一定の時刻に、１つのラインを入力ラインとして使用してそれから入力信号を受信し、別の時刻に同一のラインを出力ラインとして出力信号を出力するように使用することができる。更に、モジュール間のラインは複数の信号を同時に伝播することができ、この結果、その送付先の方へ送信される信号のバッファとして働く。明らかに、ラインを双方向にするのを許可すれば、各モジュールに連結されるライン数は少なくてすむ。しかも、ライン内にバッファを設けると、信号のスループットが高まり、DI回路[Lee, J., Peper, F., Adachi, S. & Morita, K. Compact designs of universal delay-insensitive circuits with bi-directional and buffering lines. Submitted to IEEE Transactions on Computers (June 2002).]の演算効率を高めることができる。
【００２３】
定義２．１  「順序機械」は、N=(Q, q0,Σ,Δ,h,g)として定義される。但し、Qは状態の有限集合、q0は初期状態、ΣとΔはそれぞれ入力および出力記号の有限集合である。h:Q×Σ→Ｑは状態遷移関数、そしてg:Q×Σ→Δは出力関数である。
【００２４】
定義２．２  「モジュール」は、（I,O,T(O), N）として定義される。但し、Iは入力ラインの有限集合、Oが出力ラインの有限集合、T(O)=[[ ]M]∪[a1,・・・,an]M[a1,・・・,an ∈0,1＜ｎ＜∞]は、O1上の有限サイズ多集合の有限集合であり、そこでは、｛・・・｝Mが多集合（Multiset）を示し、また、N=(Q,q0,Σ,Δ,f,g)は、ΣがIと1対1の対応関係にあり、ΔがT(O)と1対１の対応関係にある順序機械である。
【００２５】
定義２．３  モジュールM＝（I,O,T(O),N）であり、ラインa∈I∪Oであると想定する。ラインaは、a∈I∩Oの場合のみに限って「双方向ライン」と呼ばれ、またこれは⇔など（双方向矢印）によって示される。また、ラインaは、それが一時に複数の信号をバッファリングし、バッファリングした信号をすべて、a∈Iのときには確実にMの方向へ、あるいはa∈OのときにはMに接続されたモジュールの方へ送信することができる場合のみに限り「バッファリングライン」と呼ばれる。ラインのバッファは、通常、有限容量を有する。
【００２６】
定義２．４  「信号」とは、ラインの状態または値の変化であり、モジュールの出力ラインから他のモジュールの入力ラインへ転送される。一価である信号は、図６（a）に示すようにライン上のトークンによって示される。「待ち状態の信号」は、モジュールのラインから到着した入力信号であるが、他の入力信号が到着しない限り、モジュールの出力を生じない。待ち状態の信号は、図６（ｂ）のように示される。
【００２７】
定義２．５  「ネットワーク」は、相互接続されたいくつかのラインを有するモジュールが集まったものである。未接続の端部を有するラインは、ネットワークの入力または出力ラインである。
【００２８】
本明細書で使用される耐遅延（ＤＩ）モジュールのクラスは、［Lee, J., Peper, F., Adachi, S. & Morita, K. Compact designs of universal delay-insensitive circuits with bi-directional and buffering lines. Submitted to IEEE Transactions on Computers (June 2002)、 Keller, R.M. Towards a theory of universal speed-independent modules. IEEE Tr. Comp. C-23(1), 21-33 (1974).］に基づいた以下の動作条件を満足するすべてのモジュールで構成されることが好ましい。
【００２９】
−条件１：  ラインは、その端部に多くて２台のモジュールを接続することが許可されるのみである。また、ラインとは、一定の時刻において、モジュール１台だけへの入力であり、またモジュール１台だけへの出力である。
【００３０】
−条件２：  モジュールが一旦信号を出力すると、そのラインからその信号を引き込めることは不可能である。
【００３１】
−条件３：  ライン上の信号は最終的にはその伝播先のモジュールによって処理される必要がある。しかし、信号は到着前に任意の遅延を被る場合がある。
【００３２】
−条件４：  ２つの入力信号がモジュールの異なるラインに同時に到着すると、モジュールが任意に指定した順序で、まず２つの入力信号の内の１つを先に処理して、次に残った信号を処理する場合がある。これは、「アービトレーション」条件と呼ばれる。
【００３３】
−条件５：  モジュールは、入力信号の到着から対応する出力信号の生成までの間に不定（しかし有限の）遅延を受ける場合がある。
【００３４】
−条件６：  ラインへの信号の出力は、そのライン上のバッファが満杯の場合には遅延を生じる。
【００３５】
−条件７：  いかなるモジュールも、同一双方向ラインからの全入力信号を処理してからでなければ同じライン上に信号を出力できない。
【００３６】
−条件８：  同時刻にライン上に存在するすべての信号は、同一方向に伝播する。
【００３７】
定義２．６  モジュールのネットワークは、モジュールまたは相互接続ラインの不定の（しかし有限の）遅延にかかわらず、その外部論理機能が変更を受けない場合に「耐遅延」（DI）である。
【００３８】
定義２．７  モジュールは、いずれかの入力ラインから高々一つの入力信号を受け取り、そしていずれかの出力ラインに確実に一つの出力信号を出力する。さらに、そのモジュールは二つ以上の入力信号を同時に処理することが禁止されている場合「シリアル」である。
【００３９】
定義２．８  モジュールは、入力信号が必ずしも出力信号によって区切られること必要なく複数の入力信号を許可するか、あるいは出力信号が必ずしも入力信号で区切られる必要なく複数の信号を出力できる場合には、「パラレル」である。
【００４０】
定義２．９  モジュールのネットワークは、十分長い間ネットワークへの全入力ライン上に信号がないことが、最終的にネットワーク内に信号が残っていないかまたはネットワーク内に残っているすべての信号が待ち状態になるか、そのいずれかを意味する場合は常に、ウイズアウトビジーウエイティング（without busy waiting）である。
【００４１】
without busy waitingであることの実際的な重要性は、この条件が、入力信号がないときにもネットワークが無際限に動作する必要はなく、その結果ネットワークの電力消費を最小限にすることを保証することである。
【００４２】
定義２．１０  基関数モジュールの集合は、ＤＩモジュールクラスに対して、そのクラスの各モジュールがこの集合の基関数のwithout-busy-waitingネットワークによって実現可能な場合のみに限り、「without-busy-waiting構成万能」（または「構成万能」と略す）であると呼ばれる。
【００４３】
定理２．１  ［Lee, J., Peper, F., Adachi, S. & Morita, K. Compact designs of universal delay-insensitive circuits with bi-directional and buffering lines. Submitted to IEEE Transactions on Computers (June 2002)］｛ＭＥＲＧＥ，  ＦＯＲＫ，  ＩＯＭ，  Ｓ−ＪＯＩＮ，  ＡＴＳ｝は、ＤＩモジュールクラスに対して、without-busy-waiting構成万能である。
【００４４】
定理２．２  ［Lee, J., Peper, F., Adachi, S. & Morita, K. Compact designs of universal delay-insensitive circuits with bi-directional and buffering lines. Submitted to IEEE Transactions on Computers (June 2002)］  ｛ＭＥＲＧＥ，  ＦＯＲＫ，  ＩＯＭ，  Ｓ−ＪＯＩＮ｝は計算万能である。
【００４５】
図７に、セルオートマトンにその初期状相を埋め込んだ基関数耐遅延モジュールを示す。［Lee, J., Peper, F., Adachi, S. & Morita, K. Compact designs of universal delay-insensitive circuits with bi-directional and buffering lines. Submitted to IEEE Transactions on Computers (June 2002)］内のＰａｒａｌｌｅｌ  ＭＥＲＧＥモジュールはここでは簡潔にするためＭＥＲＧＥと呼ぶ。
【００４６】
図７において、ＭＥＲＧＥでは、入力ラインＩ1またはＩ2上の信号が出力ラインＯに転送される。
【００４７】
図７において、ＦＯＲＫでは、入力ラインＩ上の信号は出力ラインＯ1およびＯ2上に複製されて転送される。
【００４８】
図７において、ＩＯＭ（入力／出力マルチプレクサ）では、入力ラインａ上の信号がｂに出力される。ラインｂからモジュールへの信号がｃに出力される。
【００４９】
図７において、Ｓ−ＪＯＩＮ  （Ｓｙｍｍｅｔｒｉｃ  ＪＯＩＮ）では、２本のラインａ（ｂ）［ｃ］とｂ（ｃ）［ａ］からモジュールへの入力信号が処理されて、１つの信号が残りのラインｃ（ａ）［ｂ］へ出力される。モジュールへのラインのうちの１本からの信号が、他のいずれかのラインから信号が到着するまで待ち状態となる。
【００５０】
図７において、ＡＴＳ  （Ａｒｂｉｔｒａｔｉｎｇ  Ｔｅｓｔ  ＆  Ｓｅｔ）について、ＡＴＳには０と１の２つの状態がある。入力ラインＴ上の信号は常に状態を１に設定し、入力ラインＲ上の信号は状態を常に０にリセットするが信号を出力しない。Ｔ上の信号は、モジュールが状態１（０）のときに出力ラインＴ1（Ｔ0）に転送される。ＴとＲ両方の２つの同時信号は、１つの信号が最初に入力され、次にもう１つというように、アービトレーションされる。
【００５１】
以下、本発明の第２の実施の態様について説明する。本発明のセルラオートマトンの演算手段を構成する基本モジュール群である[Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ]はいかなる非同期回路をも構成することができる。非同期回路は、同期回路と異なり中央駆動信号を必要としない。このため、非論理同期回路を構成することには様々な利点がある。
【００５２】
本発明の非同期回路の演算手段を構成する基本モジュール群である[Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ]が、いかなる非同期回路をも構成することができることを説明する。
以下、基本モジュール群[Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ]を構成するそれぞれモジュールの作用を説明する。
【００５３】
図８に、Ｐ−ＭＥＲＧＥ（Parallel−ＭＥＲＧＥ）を示す。
Ｐ−ＭＥＲＧＥは、演算部を、２つの入力信号伝播路と１つ出力信号伝播路とに接続された演算部であって、前記２つの入力信号伝播路のいずれかから演算手段に入力信号が入力された場合に、前記出力信号伝播路に出力信号を出力するように機能させ、更に前記２つの入力信号伝播路から演算部に入力信号が同時に入力された場合に、前記出力信号伝播路に２つの出力信号を出力するように機能させるモジュールであり、演算手段を、２つの入力信号伝播路と１つ出力信号伝播路とに接続された演算手段であって、前記２つの入力信号伝播路のいずれかから演算手段に入力信号が入力された場合に、前記出力信号伝播路に出力信号を出力するように機能させ、更に前記２つの入力信号伝播路から演算手段に入力信号が同時に入力された場合に、前記出力信号伝播路に２つの出力信号を出力するように機能させる第１の演算手段として機能する。
【００５４】
Ｐ−ＭＥＲＧＥによれば、入力ラインの信号ａまたはｂは、出力ラインｃに出力される。ＭＥＲＧＥと異なり、ａとｂとが、同時に入力されることは禁止されない。したがって、Ｐ−ＭＥＲＧＥは、ＭＥＲＧＥの機能を真に含むものである。
【００５５】
図９に、Ｓ−ＪＯＩＮ（Ｓｙｍｍｅｔｒｉｃ−ＪＯＩＮ）を示す。
Ｓ−ＪＯＩＮは、演算部を、３つの入出力信号伝播路とに接続された演算部であって、前記３つの入出力信号伝播路のうち２つから入力信号が演算部に入力された場合に、残りの入出力信号伝播路から出力信号が出力されるように機能させるモジュールであり、演算手段を、３つの入出力信号伝播路とに接続された演算手段であって、前記３つの入出力信号伝播路のうち２つから入力信号が演算手段に入力された場合に、残りの入出力信号伝播路から出力信号が出力されるように機能させる第２の演算手段として機能する。
【００５６】
Ｓ−ＪＯＩＮによれば、入力ラインａ（ｂ）＜ｃ＞とｂ（ｃ）＜ａ＞からの信号は、同期されてｃ（ａ）＜ｂ＞からの出力信号となる。ａ、ｂ、ｃが、同時に入力されることは禁止される。ひとつの入力ラインが受領状態（信号を受け取った状態）にあるときは、他の入力ラインからの信号を受領するまで待ち状態に維持される。
【００５７】
図１０に、ＩＯＭ（Ｉｎｐｕｔ−Ｏｕｔｐｕｔ  Ｍｕｌｔｉｐｌｅｘｅｒ）を示す。
ＩＯＭは、演算部を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連続された演算部であって、前記入力信号伝播路から入力信号が演算部に入力された場合に前記入出力信号伝播路から出力信号が出力されるように機能させ、前記入出力信号伝播路から入力信号が演算部に入力された場合に、前記出力信号伝播路から出力信号が出力されるように機能させるモジュールであり、演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路とに連続された演算手段であって、前記入力信号伝播路から入力信号が演算手段に入力された場合に前記入出力信号伝播路から出力信号が出力されるように機能させ、前記入出力信号伝播路から入力信号が演算手段に入力された場合に、前記出力信号伝播路から出力信号が出力されるように機能させる第３の演算手段として機能する。
【００５８】
ＩＯＭによれば、入力ラインａからの信号は、同期されてｂからの出力信号となる。また、ＩＯＭによれば、入力ラインｂからの信号は、同期されてａからの出力信号となる。
【００５９】
図１１に、Ｒ−ＡＴＳ（Ｒｅｆｌｅｘｉｖｅ−ＡＴＳ）を示す。
Ｒ−ＡＴＳは、演算部を、２つの入出力信号伝播路に連結された演算部であって、ひとつの入出力信号伝播路に信号が届いた場合に、演算部を１の状態とし、残りの入出力信号伝播路からの信号は出力せずに状態を１から０に戻し、演算部が１の状態のときにひとつの入出力信号伝播路から演算部に入力された信号をそのまま同じ入出力信号伝播路に戻し、演算部が０の状態のときにひとつの入出力信号伝播路から演算部に入力された入力信号を残りの入出力信号伝播路から出力信号として出力し、両方の入出力信号伝播路から入力信号が演算部へ入力されたときは、どちらかの入力信号が演算部に先に入力され、残りの入力信号が遅れて演算部に入力されたようにアービトレーションするように機能させるモジュールである。
【００６０】
Ｒ−ＡＴＳは、演算手段を、２つの入出力信号伝播路に連結された演算手段であって、ひとつの入出力信号伝播路に信号が届いた場合に、演算手段を１の状態とし、残りの入出力信号伝播路の状態を出力せずに１から０に戻し、演算手段が１の状態のときにひとつの入出力信号伝播路から演算手段に入力された信号をそのまま同じ入出力信号伝播路に戻し、演算手段が０の状態のときにひとつの入出力信号伝播路から演算手段に入力された入力信号を残りの入出力信号伝播路から出力信号として出力し、両方の入出力信号伝播路から入力信号が演算手段へ入力されたときは、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる第４の演算手段として機能する。
【００６１】
なお、前記第４のモジュール（Ｒ−ＡＴＳ）の代りに、又は前記第４のモジュールとともに前記演算部を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路に連結された演算手段であって、初期状態は１の状態であり、前記入出力信号伝播路に信号が届いた場合に、演算部を０の状態とし、入力信号伝播路からの信号を入力された場合に、演算部が１の状態であれば、前記出力信号伝播路からその信号を出力信号として出力し、演算部が０の状態であれば、前記入出力信号伝播路からその信号を出力信号として出力し、その後演算部の状態を０に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算部へ入力された場合は、どちらかの入力信号が演算部に先に入力され、残りの入力信号が遅れて演算部に入力されたように調整するように機能させるモジュールを用いてもよく、このモジュールは、前記演算手段を、１つの入力信号伝播路と１つの出力信号伝播路と１つの入出力信号伝播路に連結された演算手段であって、初期状態は１の状態であり、前記入出力信号伝播路に信号が届いた場合に、演算手段を０の状態とし、入力信号伝播路からの信号を入力された場合に、演算手段が１の状態であれば、前記出力信号伝播路からその信号を出力信号として出力し、演算手段が０の状態であれば、前記入出力信号伝播路からその信号を出力信号として出力し、その後演算手段の状態を０に戻し、入力信号伝播路と入出力信号伝播路から入力信号が同時に演算手段へ入力された場合は、どちらかの入力信号が演算手段に先に入力され、残りの入力信号が遅れて演算手段に入力されたように調整するように機能させる演算手段として機能する。
【００６２】
また、ケラー氏によればＡＴＳおよびＳと呼ばれる２つの有用なモジュールも提案されている。図１２に、モジュールＡＴＳ（Ａｒｂｉｔｒａｔｉｎｇ  Ｔｅｓｔ−ａｎｄ−Ｓｅｔ）を表す。
ＡＴＳは、０と１の状態がある。入力ラインＴからの信号は、常にＡＴＳを１の状態とし、入力ラインＲからの信号は、信号を出力せずに、常にＡＴＳの１の状態を０の状態に戻す。ＡＴＳモジュールの状態が１の場合は、ラインＴからの信号は、ラインＴ1から出力される。また、ＡＴＳモジュールの状態が０の場合は、ラインＴからの信号は、ラインＴ0から出力される。もしも、ラインＴとラインＲから同時に信号がＡＴＳに入力された場合、いずれかが先で、いずれかが後に入力されたと同様にして信号が出力される。
【００６３】
図１３は、ＡＴＳが、基本モジュール群｛Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ｝を用いて表現できることを表す図である。
【００６４】
入力ラインｃ1とｃ2に待ち信号があり、それらをそれぞれJ1とJ2とする。なお、ここで、ｃ1とｃ2をJ1とJ2と記載したのは、その方向が決まっているからである。入力ラインＴから信号が伝達されたとすると、入力ラインｃ1の信号とあわさって、ラインＴ'からＲ−ＡＴＳに転送される。こののちに、ラインｃ1には待ち信号が残らないから、ラインＴ上の別の信号は、新しい信号がラインｃ1に伝達されるまでラインJ1の外で待つことになる。入力ラインＲの場合も同様である。このように、J1（J2）とは、入力ラインＴ（Ｒ）からの信号がライン（ｃ1）（ｃ2）上の制御信号を用いるときに入力した場合にのみスイッチの役割を果たす。
もしもＲ−ＡＴＳが１の状態であれば、Ｔ’からの出力信号は、ＦＯＲＫモジュールによって分枝される。分枝された信号のひとつは、ラインＴ1に、もうひとつはラインｃ1に戻り、次の入力のための制御（待ち）信号となる。もしもＲ−ＡＴＳが０の状態であれば、Ｒ’からの出力信号は、ＦＯＲＫモジュールによって分枝される。分枝された信号のひとつは、ラインＴ0に、もうひとつはラインｃ2に戻る。したがって、このネットワークは、先に説明したＡＴＳを実現しているといえる。
【００６５】
先に説明したとおり、ＭＥＲＧＥは、Ｐ−ＭＥＲＧＥによって表現できる。
【００６６】
ＴＲＩＡを本発明の基本モジュール群の[Ｓ−ＪＯＩＮ，ＩＯＭ]を用いて表現できることを図１４を用いて説明する。図１４から、入力ライン[Ｉ1，Ｉ2，Ｉ3]と、出力ライン[Ｏ1，Ｏ2，Ｏ3]は、ＴＲＩＡと等価であることが明らかである。
ＳＥＱＵＥＮＣＥＲをモジュール群｛Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ｝を用いて表現すると図１５のようになる。
【００６７】
Ｓ−ＪＯＩＮモジュールＪ3，Ｊ5，Ｊ6は、それぞれ入力ラインｃ，ai，ｂi上にある信号のスイッチとして使用される。ＡＴＳモジュールにおいて説明したように、Ｊ1とＪ2は、ＴとＲにスイッチされる。ＳＥＱＵＥＮCＥＲの機能は、２つのＡＴＳと、ひとつのＰ−ＭＥＲＧＥを含む回路によって実現できる。入力ラインｃ上の信号は、Ｓ−ＪＯＩＮモジュールＪ4のために回路に直接入ることができない。十分長い時間にわたりラインｃ，ai，ｂiに信号がない場合、ラインｃに到達した新しいシグナルは、モジュールＪ4の入力ラインｃ4上に待ち状態となる。Ｓ−ＪＯＩＮモジュールＪ4は、入力信号ｂ4がある状態で、入力ラインｃ（ｃ4）からの入力信号を出力するスイッチとして機能する。ラインｂ4に到達する信号の数は、Ｐ−ＭＥＲＧＥ（Ｍ）のために、ＲaまたはＲbに到達する信号の数と同じである。このようにして、ＲaまたはＲb上のシグナルの結果、回路上の信号は、最終的にはラインａ0またはｂ0に送られる。
【００６８】
以上より、without-busy waitingのＳＥＱＵＥＮＣＥＲを本発明の基本モジュール群を用いて表現できる。
【００６９】
パトラ氏によれば、以下の基本モジュール群[ＭＥＲＧＥ、ＦＯＲＫ、ＴＲＩＡ、ＳＥＱＵＥＮＣＥＲ]を用いれば、全ての非同期回路を設計することができる。そして、本発明の基本モジュール群を用いて、これら全てのモジュールを表現することができる。したがって、本発明の基本モジュール群は、全ての非同期回路を設計することができる。
【００７０】
[ＮＡＮＤ回路]
本発明の基本モジュール群を用いた耐遅延ＮＡＮＤ回路（ゲート）を図１６に示す。
ＮＡＮＤゲートは、２つの入力がともに１のときにのみ出力を０とし、それ以外の場合は、出力を１とするゲートである。ＮＡＮＤ回路を用いれば、全ての論理回路を組み立てることができる。
ＮＡＮＤ回路によれば、入力ライン（a0，ｂ0）、（a1，ｂ0）、（a0，ｂ1）からの信号のペアが入力された場合は、出力ラインｃ1から信号が出力される。一方、入力ライン（a1，ｂ1）からの信号のペアが入力された場合は、出力ラインｃ0から信号が出力される。したがって、本発明の基本モジュール群を用いれば、ＮＡＮＤゲートを組み立てることができることがわかる。ＮＡＮＤゲート（回路）を、用いれば、論理積（ＡＮＤ）、論理和（ＯＲ）、論理否定（ＮＯＴ）などの基本論理回路を設計することができる、また、ＮＡＮＤ回路を用いれば、双安定回路（ＦＦ回路）や、加算器なども設計できる。したがって、本発明の基本モジュール群を用いて、全ての論理回路（非同期回路）を設計することができる。さらに、非同期回路を設計し、コンピュータを設計することもできる。
【００７１】
また、本発明のオートマトンを用いて演算装置を設計し、公知の入力装置、制御装置、記憶装置、出力装置と組み合わせたコンピュータを得ることができる。
【００７２】
【発明の効果】
本発明の基本演算子群は、最大でも３つの入力ライン、出力ライン、入出力ラインから選ばれるラインのみを有する。そして、本発明の基本モジュール群は、汎用性がある。
本発明の基本演算子群を用いれば、非同期回路やコンピュータを簡便に設計できる。
基本演算子群が簡単な構成からなっていることは、ナノ・バイオ素子などを用いて回路やコンピュータを設計する際に大いに有用である。
【図面の簡単な説明】
【図１】図１は、本発明の基本モジュール群と、ケラー氏の基本モジュール群との対応を表す図である。
【図２】ＭＥＲＧＥを表す。
【図３】ＦＯＲＫを表す。
【図４】ＴＲＩＡを表す。
【図５】ＳＥＱＵＥＮＣＥＲを表す。
【図６】信号を表す。ある値の信号は、図６（ａ）のトークンのように表される。待ち信号は、図６（ｂ）のように表される。
【図７】図７に、セルオートマトンにその初期構成を埋め込んだ基関数耐遅延モジュールを示す。
【図８】図８は、Ｐ−ＭＥＲＧＥ（Parallel−ＭＥＲＧＥ）を示す。
【図９】図９は、Ｓ−ＪＯＩＮ（Ｓｙｍｍｅｔｒｉｃ−ＪＯＩＮ）を示す。
【図１０】図１０は、ＩＯＭ（Ｉｎｐｕｔ−Ｏｕｔｐｕｔ  Ｍｕｌｔｉｐｌｅｘｅｒ）を示す。
【図１１】  図１１は、Ｒ−ＡＴＳ（Ｒｅｆｌｅｘｉｖｅ−ＡＴＳ）を示す。
【図１２】  図１２は、モジュールＡＴＳ（Ａｒｂｉｔｒａｔｉｎｇ  Ｔｅｓｔ−ａｎｄ−Ｓｅｔ）を表す。
【図１３】  図１３は、ＡＴＳが、基本モジュール群｛Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ｝を用いて表現できることを表す図である。
【図１４】  図１４は、ＴＲＩＡを本発明の基本モジュール群の[Ｓ−ＪＯＩＮ，ＩＯＭ]を用いて表現できることを示す図である。
【図１５】  図１５は、ＳＥＱＵＥＮＣＥＲをモジュール群｛Ｐ−ＭＥＲＧＥ、Ｓ−ＪＯＩＮ、ＩＯＭ、Ｒ−ＡＴＳ、ＦＯＲＫ｝を用いて表現した図である。
【図１６】  図１６は、本発明の基本モジュール群を用いたＮＡＮＤ回路を表す。
【図１】
0003718715.tif 000002
【図２】
0003718715.tif 000003
【図３】
0003718715.tif 000004
【図４】
0003718715.tif 000005
【図５】
0003718715.tif 000006
【図６】
0003718715.tif 000007
【図７】
0003718715.tif 000008
【図８】
0003718715.tif 000009
【図９】
0003718715.tif 000010
【図１０】
0003718715.tif 000011
【図１１】
0003718715.tif 000012
【図１２】
0003718715.tif 000013
【図１３】
0003718715.tif 000014
【図１４】
0003718715.tif 000015
【図１５】
0003718715.tif 000016
【図１６】
0003718715.tif 000017