順序論理

オートマトン理論 において、順序論理は、出力が入力信号の現在の値と過去の入力のシーケンス、つまり入力履歴に依存する論理回路の一種です。 ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]}これは、出力が現在の入力のみの関数である組み合わせ論理とは対照的です。つまり、順序論理は状態（メモリ）を持ちますが、組み合わせ論理は持ちません。

順序論理は、すべてのデジタル回路の基本構成要素である有限状態機械を構築するために使用されます。実用的なデジタル機器の回路は、ほぼすべて組み合わせ論理と順序論理の組み合わせで構成されています。

シーケンシャルロジックを備えたデバイスの身近な例としては、「チャンネルアップ」ボタンと「チャンネルダウン」ボタンを備えたテレビがあります。 ^{[ 1 ]}「アップ」ボタンを押すと、テレビは現在受信しているチャンネルの次のチャンネルに切り替えるように指示する入力を受け取ります。テレビがチャンネル 5 の場合、「アップ」を押すとチャンネル 6 に切り替わります。しかし、テレビがチャンネル 8 の場合、「アップ」を押すとチャンネル 9 に切り替わります。チャンネル選択が正しく機能するためには、テレビは過去のチャンネル選択によって決定された現在受信しているチャンネルを認識している必要があります。^{[ 1 ]}テレビは現在のチャンネルを状態の一部として保存します。「チャンネルアップ」または「チャンネルダウン」の入力が与えられると、チャンネル選択回路のシーケンシャルロジックは入力と現在のチャンネルから新しいチャンネルを計算します。

デジタル順序回路は、同期型と非同期型に分類されます。同期型順序回路では、デバイスの状態はクロック信号に応じて離散的なタイミングでのみ変化します。一方、非同期型回路では、入力の変化に応じてデバイスの状態はいつでも変化します。

今日の順序論理回路のほぼすべては、クロック同期論理回路です。同期回路では、クロック（またはクロックジェネレータ）と呼ばれる電子発振器が、クロック信号と呼ばれる一連の繰り返しパルスを生成し、回路内のすべてのメモリ素子に分配します。同期論理回路の基本的なメモリ素子はフリップフロップです。各フリップフロップの出力はクロックパルスによってトリガーされたときにのみ変化するため、回路全体の論理信号の変化はすべて、クロックによって同期された一定の間隔で同時に開始されます。

回路内のすべての記憶素子（フリップフロップ）の出力、つまりそれらが格納するバイナリデータは、回路の状態と呼ばれます。同期回路の状態はクロックパルスによってのみ変化します。各サイクルにおいて、次の状態は、クロックパルスが発生した時点での現在の状態と入力信号の値によって決定されます。

同期論理回路の主な利点はそのシンプルさです。データに対して演算を行う論理ゲートは、入力の変化に応答するのに一定の時間を要します。これを伝搬遅延と呼びます。クロックパルスの間隔は、すべての論理ゲートが変化に応答し、次のクロックパルスが発生する前に出力が安定した論理値に「落ち着く」のに十分な長さでなければなりません。この条件が満たされている限り（他のいくつかの詳細を無視すれば）、回路は安定かつ信頼できることが保証されます。これが同期回路の最大動作速度を決定します。

同期ロジックには主に2つの欠点がある。

• クロックの最大レートは、回路内で最も遅い論理パス、すなわちクリティカルパスによって決まります。最も単純なものから最も複雑なものまで、すべての論理演算は1クロックサイクルで完了する必要があります。そのため、演算を迅速に完了する論理パスは、次のクロックパルスを待つため、ほとんどの時間アイドル状態になります。したがって、同期論理は非同期論理よりも遅くなる可能性があります。同期回路を高速化する1つの方法は、複雑な演算を連続するクロックサイクルで実行できる複数の単純な演算に分割することです。この手法はパイプライン処理として知られています。この手法はマイクロプロセッサの設計で広く用いられており、最新のプロセッサの性能向上に貢献しています。
• クロック信号は回路内のすべてのフリップフロップに分配されなければなりません。クロック信号は通常高周波信号であるため、この分配には比較的多くの電力が消費され、大量の熱が発生します。何も動作していないフリップフロップでさえもわずかな電力を消費し、チップ内で廃熱を発生させます。バッテリー駆動デバイスでは、バッテリー寿命を維持するために、デバイスがアクティブに使用されていない間はクロック速度を下げたり、一時的にクロックをオフにしたりするための、追加のハードウェアおよびソフトウェアの複雑さが必要となります。

非同期（クロックレスまたは自己同期）順序回路はクロック信号によって同期されません。回路の出力は入力の変化に直接応答して変化します。非同期回路の利点は、入力処理のためにクロック信号を待つ必要がないため、同期回路よりも高速に動作できることです。デバイスの速度は、使用される論理ゲートの伝搬遅延によってのみ制限される可能性があります。

しかし、非同期ロジックは設計がより難しく、同期設計では発生しない問題が生じます。主な問題は、デジタルメモリ素子が入力信号の到着順序に敏感であることです。2つの信号がフリップフロップまたはラッチにほぼ同時に到着した場合、回路がどの状態になるかは、どちらの信号が先にゲートに到達するかによって決まります。そのため、ロジックゲートの伝搬遅延のわずかな違いによって、回路が誤った状態になることがあります。これは「競合状態」と呼ばれます。同期回路では、メモリ素子の出力はクロックパルスごとにしか変化しないため、この問題はそれほど深刻ではありません。クロック信号間の間隔は、メモリ素子の出力が「安定」して次のクロックが来たときに変化しないのに十分な長さに設計されています。したがって、タイミングの問題は「非同期入力」、つまりクロック信号に同期していない他のシステムからの回路への入力によってのみ発生します。

非同期順序回路は、マイクロプロセッサやデジタル信号処理回路の一部など、速度が特に重要な同期システムのごく一部の重要な部分でのみ使用されるのが一般的です。

非同期論理の設計は、同期論理とは異なる数学モデルと技術を用いており、活発な研究分野である。

• 組み合わせ論理
• 同期回路
• 非同期回路
• 論理設計
• 特定用途向け集積回路

• ランディ・カッツ;ボリエッロ、ガエターノ(2005)。現代論理設計(第 2 版)。プレンティスホール。ISBN 0-201-30857-6。
• コハヴィ、ツヴィ。ジャー、ニラジ K. (2009)。スイッチングと有限オートマトン理論(第 3 版)。ケンブリッジ大学出版局。ISBN 978-0-521-85748-2。
• Vasyukevich, Vadim O. (2009). "非同期論理要素。Venjunctionとsequintion" (PDF) . 2011年7月22日にオリジナルからアーカイブされました(PDF) 。（118ページ）
• Vasyukevich, Vadim O. (2011). ラトビア、リガにて執筆。「順序論理の非同期演算子：分岐と順序付け ― デジタル回路の解析と設計」。Lecture Notes in Electrical Engineering (LNEE)。第101巻 （第1版）。ドイツ、 ベルリン／ハイデルベルク：Springer -Verlag。doi：10.1007 /978-3-642-21611-4。ISBN 978-3-642-21610-7ISSN 1876-1100 LCCN 2011929655​​​  （xiii+1+123+7ページ）（注：本書の裏表紙には誤って第4巻と記載されていますが、実際は第101巻です。）