論理ゲートとブール代数

2つの式の真理値表が完全に一致していても、ゲート回路に実装すると異なるスパイク（グリッチ）が発生する可能性がある。また、ある出力が「ハイレベル」と呼ばれていても、別のチップで確実に認識できるとは限らない。デジタル・ロジックは、ブール機能、伝播タイミング、およびアナログ電圧の両方を同時に扱う必要がある。本章では、まず代数的な記述を明確にし、次にカーン図とパス遅延を用いてこれら3つの層の関係性を説明する。

演算と否定の範囲

ブール変数は 0 と 1 のみである。本稿では、AND を A·B、OR を A+B、NOT を ¬A、XOR を A⊕B で表す。ここで使われるプラス記号は通常の整数加法ではなく、1+1 も 1 となる。括弧は否定の範囲を明確にするものであり、¬(A·B) を誤って A·¬B と書いてはならない。

NOT は 0 を 1 に、1 を 0 に反転させる。2入力XORは入力が異なる場合に 1 を出力し、XNORはその否定である。複数入力の連続XORは、1の個数が奇数の場合に 1 を出力するものであり、「すべての入力が互いに異なる」という意味で解釈してはならない。

簡略化は恒等式に頼り、通常の代数の直感に頼らない

例えば AB+A¬B=A(B+¬B)=A となる。また Y=¬(AB)+C に対してド・モルガンの法則を適用すると ¬A+¬B+C となる。もし B だけを否定してしまうと、関数が変わってしまう。

NAND には機能完全性がある。A NAND A は NOT を生成し、NAND の結果をさらに否定すると AND になる。(A NAND A) NAND (B NAND B) は OR を生成する。したがって、状態を持たないブール関数のレベルでは、NAND によって任意の組み合わせ論理を構築できる。NOR も同様である。これは1種類のゲートだけで実装すれば必ず面積が最小になり、速度が最速になることを意味するものではない。メモリにおける NAND/NOR という名称も、「ゲートがすべての関数を実現できる」という事実から導き出されたものではない。

真理値表から被覆へ

n 個の入力に対して、完全な真理値表には 2ⁿ 行が存在する。各出力が 1 となる行を最小項として書き出し、それらを OR 演算で結合すると、積和形（SOP）の式が得られる。例えば、3変数符号化において ABC を高位から低位とし、2進数 001 に対応するのは ¬A¬BC である。

カーン図では、行と列がグレー順序で並べられており、隣接するセルは1ビットのみが変化する。隣接する 1 を矩形にグループ化でき、セル数は 1、2、4、8 などの 2 の累乗とする。グループ内で変化する変数は消去され、変化しない変数が残る。各グループは複数の最小項を被覆するインプリカント（含意項）を得るものであり、「大きく圈ってより多くの最小項を書く」ことではない。MIT：組み合わせ論理とカーン図

Y=Σm(1,3,6,7) を取る。図中で BC は 00、01、11、10 の順に並べられている。上段の2つの 1 では B が変化し、A=0、C=1 であるため、¬AC が得られる。下段の2つの 1 では C が変化し、A=1、B=1 であるため、AB が得られる。したがって Y=¬AC+AB となる。

端も隣接しており、適切なサイズの図では四隅が境界を跨ぐグループを形成できる。グループ化は重複してもよく、明確に 0 であるセルを含んではならない。「ドントケア（不定）」は、タスクで発生しないことが保証されているか、出力に要件がない条件からのみ由来するべきであり、ある入力が扱いにくいからといって任意に X とマークしてはならない。未初期化や故障状態が発生しうる場合は、それに対応する挙動を考慮すべきである。

ゲート数、入力数、論理深度、ファンアウト、および目標プロセスは実装コストに影響を与える。リテラル数が最短の式が、必ずしも最速または最小の回路に対応するわけではない。複雑な論理は通常、論理合成ツールを用いて行われるが、真理値表と被覆は結果を理解するための基礎である。

論理等価はタイミング等価ではない

引き続き Y=AB+¬AC を用い、B=C=1 とする。定常状態では A が 0 でも 1 でも、Y は 1 である。しかし、A が 1 から 0 に変化するとき、AB パスは先に 0 に変わる可能性があり、反転器を介した ¬AC パスは少し遅れて 1 になる。その間、2つの積項がともに 0 となる隙間が生じる。これを静的 1 ハザードと呼ぶ。

冗長項 BC を追加して Y=AB+¬AC+BC とすると、真理値表は変わらないが、B=C=1 で A が切り替わる際に 1 を維持するパスを提供する。カーン図上では、上下の BC=11 のセルを被覆する共通グループを追加することに対応する。MIT：組み合わせ論理のハザードと被覆

この結論は、対応する2段構成と、A のみを変更するという条件に対してのものであり、任意の多段マッピングや複数の入力が同時に変化する場合にスパイクが発生しないことを保証するものではない。論理合成ツールが面積をさらに削減するために冗長項を削除した場合、実装後の目標制約を確認する必要がある。動的ハザードや多入力機能ハザードも、この項だけですべて解決されるわけではない。

同期システムでは、組み合わせ論理が十分に安定した後にレジスタでサンプリングできるが、セットアップ/ホールド時間を満たす必要があり、スパイクは動的消費電力を増加させる可能性がある。クロック、非同期リセット、または外部動作を直接駆動する信号は、スパイクに対して特に敏感である。通常のゲート出力にコンデンサを並列接続して通用する修復策として安易に使用してはならない。それは負荷を増加させ、エッジを鈍らせ、入力変換時間の要件に違反する可能性がある。フィルタリングが必要な場合は、明確な RC と適切な入力構造を設計すべきである。

同じ真理値表なのになぜグリッチ？

到着時刻を離すだけで隙間が見える。順序を逆にすると重なりになり、このモデルの静的1ハザードが消える。BC追加でどちらもHighを保つが、本文の単入力変化に限る。

0/1 は電圧範囲である

V_IL(max) は低として認識される入力の上限値を保証し、V_IH(min) は高として認識される入力の下限値を保証する。この間の入力値は論理結果を保証するものではなく、デバイスに3番目の安定したブール値があることを意味しない。通常の入力の実際のスレッシュホールドは、デバイス、電源電圧、および温度に応じて変化する。

前段と後段を接続する際は、前段の指定電流下での V_OH(min)、V_OL(max) を、後段の V_IH(min)、V_IL(max) とそれぞれ照合する。ハイレベルの静電ノイズマージンは NM_H=V_OH(min)−V_IH(min)、ローレベルは NM_L=V_IL(max)−V_OL(max) である。

前段のハイ出力が少なくとも 2.9 V、ロー出力が最大 0.2 V であり、後段のハイ入力が少なくとも 2.0 V、ロー入力が最大 0.8 V を要求すると仮定すると、両者のマージンはそれぞれ 0.9 V と 0.6 V となる。これは静電レベルのみをチェックするものであり、絶対最大入力電圧、未給電許容、リファレンスグランドのオフセット、およびエッジ条件も確認する必要がある。

TTL/CMOS は、十分に詳細なレベル仕様ではない。CMOS 実装であっても、HC と HCT などのシリーズでは入力閾値が異なる可能性がある。電源が同じでもインターフェースの互換性が保証されるわけではなく、「CMOS」という言葉からノイズマージンがすべての TTL より優れていると推論することはできない。Nexperia：74HC00 / 74HCT00

フローティング、スローエッジ、およびシュミットトリガ入力

CMOS 入力がフローティング（浮遊）していると、リーク電流や結合によって電圧が転換領域に達し、出力が不確定になり、内部電流が増加する可能性がある。スローエッジやノイズによってスレッシュホールドを複数回横切ると、繰り返し切り替わる可能性がある。シュミットトリガ入力は上昇と下降の閾値が異なり、ヒステリシスを提供できるが、それでも電圧と使用条件を遵守する必要がある。TI：スローエッジとフローティング CMOS 入力

未使用入力はデバイスの要件に従って有効な状態に固定する。直接接続するか、適切な抵抗を用いる。出力ピンを随意に入力として電源レールに接続してはならない。プッシュプル出力は通常、直接並列接続して「駆動能力を強化」することはできない。オープンドレインなどの構造では、プルアップとワイヤード・アンド論理を対応するルールに従って使用する必要がある。

理想ゲートと実チップ

CMOS インバータは、プルアップ PMOS とプルダウン NMOS を使用する。入力がローレールに近いと PMOS が導通し、NMOS がオフになり、出力はハイに引き上げられる。入力がハイレールに近いと逆になる。遷移期間中、両方のトランジスタが部分的に同時に導通する可能性があり、出力負荷容量の充放電も必要である。したがって、実際には静電リークだけでなく、ショートカレントと動的消費電力も発生する。

一般的な推計式は P_dyn≈αC_LV_DD²f であり、本稿では α を、各参照周期における出力の 0→1 充電イベントの平均発生回数として定義する。資料によってアクティビティファクタの定義には異なるカウント規約が含まれる場合があり、この条件を見落としてはならない。出力が切り替わっていない場合でも、リーク、入力バイアス、および内部の他の活動が存在する可能性があるため、「切り替えの瞬間のみしか消費しない」と記述してはならない。

ファンアウトは単に最大で何個の入力を接続できるかというだけでなく、静電入力電流、容量、配線、および必要なタイミングが駆動負荷を決定する。伝播遅延 t_pLH/t_pHL は、電源電圧、温度、負荷、および入力変換条件に依存し、真理値表にはこれらの情報は含まれていない。

番号は単なる目次の入口であり、完全な型番の接頭辞・接尾辞、論理シリーズ、およびパッケージが実際の仕様を決定する。次の章 組み合わせ論理回路 では、これらのゲートを用いて加算器、デコーダ、およびマルチプレクサを構成する。

from itertools import product

def nand(a,b): return not (a and b)
for a,b,c in product([False,True], repeat=3):
    original = (a and b) or ((not a) and c)
    covered = original or (b and c)
    assert original == covered
    index = 4*int(a)+2*int(b)+int(c)
    assert original == (index in {1,3,6,7})
    assert (not (a and b)) == ((not a) or (not b))
    assert nand(nand(a,a),nand(b,b)) == (a or b)
assert (False or False) is False
assert (False or False or True) is True
print("8 種類の入力：カーン図、冗長被覆、ド・モルガン、および NAND による構築がすべて一致")

この列挙はブール機能を検証するが、ゲート遅延、実際のスパイク、またはインターフェース電圧は検証しない。物理実装には、対応するタイミングおよび電気的な検査が依然として必要である。