デジタル回路
回路の複雑さを低減させるためには、なるべく単純化して機能を最小限にすることが多いが、これにより誤りも少なくなり安価となる。回路の単純化のためのアルゴリズムとしては、CADシステムに組み込まれたエスプレッソ・ヒューリスティック・ロジック・ミニママイザー(英語版)などがよく使われているが、古典的な二分決定図、自動化したクワイン・マクラスキー法、真理値表、カルノー図、ブール代数なども使われてきた。
デジタル回路の設計にとって、その表現は重要である。一部の解析手法は特定の表現でないと使えない。デジタル回路の古典的表現として論理ゲートを使ったものがある。もう1つの表現はトランジスタなどの電子スイッチを使って構成を表す方法がある。簡単な方法の1つとして、真理値表をメモリー上に配置する方法がある。入力群をメモリのアドレスとして使い、そのアドレスの指すメモリの内容が論理関数の出力となる。自動解析のために、これらの表現にはデジタルのファイルフォーマットがあり、コンピュータプログラムで処理することができる。
表現の選択にあたってはデジタルシステムの種類を考慮する。ほとんどのデジタルシステムは組合わせ回路と順序回路に分けられる。組合わせ回路は入力(の組合わせ)が同じであれば常に同じ出力を示す。これは論理関数を組み合わせたもの(基本論理ゲートの組合せ)といえる。
順序回路は一部の出力が入力にフィードバックされる組合わせ回路ということができる。これによって「逐次的」な動作を実現できる。
一般的手法としては、個々の状態が存在しうる最短時間と最長時間の表を作成し、そのような状態の数が最小になるよう回路を調整していき、全体が周期的に「自己再同期」と呼ばれる互換状態に入って待つようにする。そのように注意深く設計しないと容易に不安定な状態になり、個々の電子部品の値の公差などに起因する遅延が蓄積して予測不可能な結果となる。ある種の回路は本質的に非同期であり(フリップフロップで構成されるシンクロナイザ、スイッチデバウンサ、調停回路、外部からの非同期な信号が同期順序回路に入るような回路など)、このような設計が必須である。
2005年現在、同期設計の方が設計と検証が容易なため、デジタルシステムのほとんどが同期設計となっている。設計/シミュレーションツールも非同期回路用のものはほとんど存在しない。しかしうまく設計できればクロック周波数に制限されないぶんだけ非同期の方が優れていると言われている。
多くのデジタル回路はデータフローマシンと見なせる。この場合、同期式レジスタ転送レベルで設計ができ、VHDLやVerilogなどのハードウェア記述言語を使うことができる。
レジスタ転送レベルでは、一連のフリップフロップで構成されるレジスタに二進数の数を格納する。レジスタの出力は「バス」と呼ばれる配線の束に繋がっており、バスがその数を他の計算機構に向けて転送する。計算機構は単なる組合わせ回路である。計算機構にも出力バスがあり、いくつかのレジスタの入力と繋がっている。レジスタの入力にはマルチプレクサが配置されていることもあり、いくつかのバスから選択して数を格納することができる。
あるいは、複数の出力をスリーステート・バッファ経由でバスに接続し、1つを除いて他の出力を遮断することができる。逐次状態機械は、それぞれのレジスタが入力から新たなデータを受け取る時点を制御する。
1980年代、一部の研究者はFIFO式同期論理を使うことでほとんどの同期式レジスタ転送機械を非同期設計に変換できることを発見した。この場合デジタル機械はデータフローの集合と見なせる。フローの各ステップにおいて、非同期の「同期回路」はその出力が妥当なものかどうかを判断でき、次のステップに対して「データを使ってよい」という信号を出すことができる。したがって、相対的に単純なステップ間の同期回路だけを設置すればよい。
コンピュータは最も汎用的なレジスタ転送論理機械である。コンピュータの制御装置は一般にマイクロシーケンサ上でマイクロプログラムを動作させるよう設計されている。マイクロプログラムは自動ピアノの巻紙に似ている。マイクロプログラムの「ワード」またはテーブルのエントリは、コンピュータを制御する全てのビットの状態を指揮する。マイクロシーケンサはカウントし、そのカウントが次のマイクロプログラムを格納したメモリ位置や組合わせ回路を指定する。マイクロプログラムの個々のビットは演算論理装置やメモリや他のコンピュータの部分を制御し、それにはマイクロシーケンサ自身も含まれる。
このようにして、コンピュータを制御するという複雑な設計をもっと単純な論理回路の集合体のプログラミングという比較的単純な作業に還元することができる。