ブール論理と論理ゲート
論理ゲートの安定した入出力関係は真理値表で表せる。一入力なら 2 行、二入力なら 4 行だ。AND は両入力が 1 のときだけ 1、OR は少なくとも一つが 1 なら 1、NOT は入力を反転する。同じ二入力を XOR と AND へ接続すると、1+1 を二進数の 10 として出せる。
配線が複合回路の真理値表を決める。一組の入力で一行を確認し、全入力を列挙すればこの小さな加算回路を検証できる。
ゲートの真理値表
二入力の組は (0,0)、(0,1)、(1,0)、(1,1) の四つ。AND は 0,0,0,1 を返す。全出力を反転すると NAND の 1,1,1,0。AND の最後の 1 だけを 0 に変えれば、常にゼロの関数となる。
各行に 0 か 1 を置くので、二入力ブール関数は 2⁴=16 種類ある。真理値表が定めるのは安定時の論理で、伝搬中のタイミングではない。このフィードバックのない組み合わせゲートは記憶を持たず、現在の入力だけで出力が決まる。計数や記憶にはフィードバックと状態を持つ構造が必要だ。
ステップ実行
既定回路は半加算器で、a = 1, b = 1 を XOR と AND の両方へ送る。
- 最初から回路の形は描かれるが、ゲートと配線は薄く、入力信号はまだ示さない。
- a と b が 1 になり、各線が二つのゲートへ分岐する。このモデルではファンアウトにコストはないが、実回路では複数負荷の駆動に代価がある。
- XOR を強調し、4 行の表の
(1,1)を選ぶ。出力は 0。 - 0 が sum 出力へ届く。パルスは伝搬を示し、線には最終値を先に表示するので、一時停止しても値を読める。
- AND は同じ入力を受け、
(1,1)の行から 1 を出す。 - carry が 1 になる。
sum=0, carry=1を、上位 carry、下位 sum の10と読む。十進数 2 で、carry は重み 2 の桁だ。- 残る三つの入力を一つずつ試す。配線の値を再計算し、
a+bの参照列と並べる。 - 全 4 行が一致し、この半加算器が二入力の全組で正しいと分かる。変えたのは入力だけで、配線は同じだ。
ステップ 3 と 4 は一回のゲート評価を「表の行を選ぶ」「出力へ届く」に分けて見せる。独立した計算を二回行う意味ではない。
配線が機能を決める
半加算器には桁上がり入力がなく、そのまま多桁へ連結できない。Full adder: 1+1+1 は XOR 二つ、AND 二つ、OR 一つの 5 ゲートを使う。OR が二つのキャリー発生経路をまとめる。三入力の表は 8 行で、1+1+1 は sum=1, carry=1、つまり 11=3 を返す。
全加算器を 8 個つなぎ、各 carry out を次の carry in に入れると、8 ビットのリップルキャリー加算器になる。二の補数の列加算を回路にしたものだ。符号付き・符号なしで下位ビットの加算ロジックは共通し、オーバーフローの解釈は別に行う。
XOR from AND/OR/NOT は (a OR b) AND NOT(a AND b) で XOR を作る。少なくとも片方が 1 で、両方同時には 1 でない条件だ。XOR はセルライブラリーの単位にもできるが、AND、OR、NOT から構成でき、全ブール関数の実現に追加必須の原始要素ではない。
AND from NAND はさらに小さい出発点を示す。同じ線を NAND の両入力へ入れると (0,0) と (1,1) だけに制限され、NOT になる。NAND から NOT、AND、OR を構成でき、任意のブール関数へ進める。一般的な静的 CMOS の二入力 NAND はトランジスター 4 個、後段に反転器を付ける AND は通常 6 個で、物理コストが実装選択に影響する。
境界ケース
- NOT は
0→1、1→0の 2 行。二つ連結すると論理値は元へ戻るが、物理的な遅延は残る。 - 同じ線を二つのピンへつなぐと、一入力の関数へ制限される。反転器を作る方法にも、誤配線による不具合にもなる。
Broken: OR instead of XORは一ゲートを置き換える。OR と XOR が違うのは(1,1)だけなので、残る三行は加算に一致する。0+1と1+0だけの試験では見逃す。- n 入力の表は
2ⁿ行。二入力は 4、三入力は 8、32 ビット加算器の全入力組は手で列挙できる規模ではない。約 4 入力までなら表を確認し、それ以上はブール代数、選択ベクトルのシミュレーション、形式的等価検証を組み合わせる。等価検証は全行を一つずつ訪ねずに全入力の一致を証明できる。 - ゲート数だけがコストではない。リップルキャリーは小さいが、最悪ではビット 0 から 31 までキャリーが伝わる。桁上がり先見構造は論理を増やして経路を短縮する。同じ安定出力でも面積とタイミングは異なる。
よくある間違い
- XOR の記号が独立した機能基盤を必須にすると考える。AND、OR、NOT で全ブール表を構成でき、XOR は頻用する機能の名前だ。
- ゲートの説明順をソフトウェアの実行順と読む。実ゲートは連続かつ並行して応答し、経路上の伝搬遅延がある。
- ビット演算と論理演算を混同する。C 系の
&は各ビットへ AND を適用し、&&は真偽値として評価して短絡する。if (flags & MASK && x)はif ((flags & MASK) && x)の結合になる。括弧で意図を示せる。 - OR が片方だけを許すと思う。ブール OR は両方を含み、
1 OR 1=1。同時成立を除くのは XOR。 - 同じ真理値表なら物理動作も同じと考える。経路の到着時刻が違うと切り替え中にグリッチが出る。表は安定結果を定め、途中経過は定めない。
モデルの範囲
ゲートは即座に評価し、配線は理想的で、ファンアウトは無制限とする。実ゲートには伝搬遅延があり、負荷が多すぎれば遅くなったり正常に駆動できなくなったりする。到着時刻の差は過渡グリッチを生み、同期設計はクロック境界で安定した結果を取り込む。電力、面積、タイミング解析は範囲外だ。組み合わせ論理と半加算器の配線規則は正しいが、実回路の状態構造や物理制約まで省けるわけではない。