デジタルコンパレーター解説: 等価性と大小

等価比較器と大小比較器を導出し、4 ビットブロックをカスケード接続し、符号付き・符号なしの順序を区別し、greater/equal/less 出力を検証します。

Denny

2026年5月7日読了まで約9分

Chalkboard feature illustration for “デジタルコンパレーター解説: 等価性と大小”

要約: 等価性はビット単位 XNOR の結果をリダクション AND したものです。符号なしの大小は、A と B が異なる最上位位置で決まります。符号付きの大小には、符号ビットの別の解釈または減算フラグが必要です。コンパレーターが正しいのは、幅、符号付きかどうか、出力極性、カスケード入力がすべて定義されている場合だけです。

コンパレーターは、二つのビットベクトルを一つの関係へ変換します。

A < B, A = B, or A > B

同じビットを別に解釈すると、これは曖昧ではなくなります。4 ビットでは、1000 は符号なしなら 8、2 の補数では -8 です。0111 と比べると、符号なし解釈では大きく、符号付き解釈では小さくなります。

このガイドでは、最初に等価比較器を作り、符号なし大小ネットワークを導出し、次に符号付き比較とブロックのカスケード接続が設計をどう変えるかを示します。

契約を定義する

有効な $n$ ビット入力 A と B に対し、三出力の大小比較器は普通、次を生成します。

G: A は B より大きい。
E: A は B と等しい。
L: A は B より小さい。

有効な二値入力モデルでは:

G+E+L=1

どの二つの出力も同時に High にはなりません。このワンホット関係は完全な実装と有効な論理レベルに依存します。イネーブル入力、アクティブ Low インターフェース、未知のシミュレーション値、誤って初期化したカスケード入力は、見える動作を変える場合があります。

等価性は符号付きかどうかに依存しません。ビットベクトルが一致するか、しないかです。大なりと小なりは異なります。

XNOR から作る等価性

一つの位置について:

E_i=A_i\odot B_i=\overline{A_i\oplus B_i}

二つのビットが一致すると $E_i=1$ です。語全体が等しいのは、すべての位置が一致するときだけです。

E=\bigwedge_{i=0}^{n-1}E_i

4 ビットでは:

E=(A_3\odot B_3)(A_2\odot B_2)(A_1\odot B_1)(A_0\odot B_0)

直接的な回路図では、四つの XNOR ゲートの後に AND リダクションを置きます。

これを「幅にかかわらず二つのゲート遅延」と呼びたくなるかもしれません。しかしそれは入力数無制限のブールレベルの図にすぎません。物理実装では、リダクションを平衡ツリーとして作り、複合セルに因数分解し、または FPGA ルックアップテーブルへマップする場合があります。二入力 AND ゲートでは、平衡化したときのリダクション深さはおよそ $\lceil\log_2 n\rceil$ で増加します。

符号なし大小: 最上位の差が勝つ

各ビットについて次を定義します。

G_i=A_i\overline{B_i}

L_i=\overline{A_i}B_i

E_i=A_i\odot B_i

最上位の異なる位置で、A が 1、B が 0 なら A は大きく、逆なら A は小さいです。下位位置が重要になるのは、上位のすべての位置が一致するときだけです。

4 ビット符号なし値では:

\begin{aligned} G={}&G_3 +E_3G_2 +E_3E_2G_1 +E_3E_2E_1G_0 \end{aligned}

\begin{aligned} L={}&L_3 +E_3L_2 +E_3E_2L_1 +E_3E_2E_1L_0 \end{aligned}

E=E_3E_2E_1E_0

各 G 項は「上位ビットがすべて引き分けで、ここで A が勝つ」を表します。各 L 項は対称なケースを表します。

符号なしの例

次を比較します。

A = 0110 (6)
B = 0101 (5)

ビット 3 と 2 は一致します。ビット 1 で A は 1、B は 0 なので、 $G_1=1$ です。より上位の差がすでにあるため、ビット 0 は関係ありません。

G=1, E=0, L=0

これは優先機能ですが、優先順位は最上位データビットから最下位データビットへ向かいます。

再帰的なコンパレーターセル

長い積和形を展開する代わりに、グループを階層的に組み合わせます。H が上位グループ、Lw が下位グループを表すとします。

G_{\text{all}}=G_H\lor(E_H\land G_{Lw})

E_{\text{all}}=E_H\land E_{Lw}

L_{\text{all}}=L_H\lor(E_H\land L_{Lw})

上位グループが一致しない限り決定し、一致したときだけ下位グループが通過します。この結合は線形カスケードまたは平衡階層を作れます。

この方程式は、4 ビット大小比較器 IC の拡張入力を説明します。ブロックは、ローカルな 4 ビットが引き分けの場合に備え、下位の G/E/L 結果を必要とします。

SN74LS85 ブロックをカスケード接続する

SN74LS85 は、二つの 4 ビットのストレートバイナリーまたは 8-4-2-1 BCD 語を比較し、三つの拡張入力と三つの関係出力を公開します。

8 ビット比較では:

下位デバイスがビット 3:0 を比較する。
その拡張関係を等価として初期化する: G_in=0, E_in=1, L_in=0。
その G/E/L 出力を上位デバイスの対応する拡張入力へ接続する。
上位デバイスがビット 7:4 を比較し、最終結果を生成する。

上位半分が異なる場合、そのローカル判断が下位入力を上書きします。上位半分が一致する場合、下位の関係が伝播します。

ピン極性、ファンアウト、電圧、タイミングについては、正確なデータシートに従ってください。論理的な再帰は電気設計の代わりにはなりません。

符号付き 2 の補数比較

等価性は、符号付き値と符号なし値のいずれでも同じ XNOR ネットワークを使います。順序は異なります。

方法 1: 符号ビットを別に解釈する

$s_A=A_{n-1}$ 、 $s_B=B_{n-1}$ とします。

$s_A\ne s_B$ なら、符号ビット 1 のオペランドが小さい。
符号が一致するなら、残りの関係の通常の辞書順比較が正しい順序を与える。

便利なハードウェア変換は、符号なしコンパレーターへ送る前に各オペランドの MSB を反転することです。

A'=A\oplus 2^{n-1}

B'=B\oplus 2^{n-1}

符号ビットを反転すると、2 の補数の順序が符号なし順序へバイアスされます。4 ビットでは:

signed -8 = 1000  → biased 0000
signed -1 = 1111  → biased 0111
signed  0 = 0000  → biased 1000
signed +7 = 0111  → biased 1111

バイアスした値は、符号付き数と同じ順序で増加します。

方法 2: 減算してフラグを解釈する

ALU が $R=A-B$ を計算する場合:

E は Z。
符号付き L は $N\oplus V$ 。
符号付き G は $\overline Z\land\overline{N\oplus V}$ 。

符号なし小なりは、減算のキャリー規約に依存します。生のキャリー出力が非ボローを意味する場合、符号なし L は $\overline C$ です。x86 に似たボローフラグでは、符号なし L は C です。CPU フラグガイドは両方の規約を導出しています。

符号付き小なりに N 単独を使ってはいけません。符号付きオーバーフローは、保存結果の見かけの符号を反転できます。

異なる解釈の例

A = 1000
B = 0111

符号なし:

8 > 7

符号付き 2 の補数:

-8 < +7

「A>B」とだけラベルを付けたコンパレーターは、符号付きかどうかが分かるまで仕様不足です。

タイミングと実装の選択

線形の優先チェーンは、幅に比例する深さを持ちます。平衡化したグループ結合ネットワークは論理深さを減らせます。合成では次のものを使う場合があります。

幅広いまたは複合のゲート。
プレフィックス風の equality/greater 結合。
ALU にすでにある減算ハードウェア。
FPGA のキャリーチェーンまたはルックアップテーブルリソース。
選択された用途向けの早期終了構造。

どのトポロジーも普遍的に最速ではありません。専用コンパレーターはある設計では算術結果を待つことを避けられる一方、加算器の再利用は別の設計では面積を節約できます。現代のプロセッサーも、一つの巨大なコンパレーターを実装するのではなく、分岐、アドレス生成、ベクター、その他の実行ロジックへ比較を分散します。

タイミングパスには、発生元のクロックから Q、入力選択、コンパレーターロジック、配線、宛先セットアップ、クロック効果が含まれます。ゲート数だけでは最大周波数は確立しません。

実用的な用途

正確なアドレス一致

等価コンパレーターは、アドレスが固定値と等しいときにチップ選択を生成できます。整列した 2 のべき乗領域では、上位アドレスビットだけを比較し、下位ビットをオフセットとして扱います。任意の範囲では代わりに不等式または因数分解したデコードロジックを使う場合があります。

バスの正しさには、等価性以上のものが必要です。イネーブル、アクセス種別、特権、相互排他的な所有権も選択を修飾する場合があります。

しきい値とウィンドウチェック

制御ロジックは、二つの大小比較で次をテストできます。

LOW\le X\le HIGH

端点を含むか除外するか、また X が符号付きかに注意してください。

min/max と compare–select

大小結果はマルチプレクサーを駆動できます。

min = (A < B) ? A : B
max = (A < B) ? B : A

各値がメタデータを運ぶ場合や安定した順序付けが必要な場合、同値時の方針が重要です。

ソーティングネットワーク

比較交換セルは、一つのコンパレーターとデータルーティングマルチプレクサーを組み合わせます。固定ネットワークはこれらのセルを段階的に合成します。そのレイテンシーは、セル数だけでなくコンパレーターの深さと比較交換段数の両方に依存します。

DigiSim で構築・検証する

コンパレーターコンポーネントを参照し、次にゲートから方程式を構築します。

XNOR で四つの $E_i$ 信号を作る。
それらを E へリダクションする。
各位置の $G_i$ と $L_i$ を作る。
MSB から LSB へ結合する。
有効な各入力ペアで、G/E/L のちょうど一つが High になることをアサートする。
MSB バイアスオプションを加え、符号なし比較と符号付き比較を切り替える。

4 ビットでは、網羅テストが実用的です。全 $16\times16=256$ ペアを評価します。

各ペアについて、次を確認します。

E がビットベクトルの等価性と一致する。
符号なし G/L が整数 0–15 と一致する。
符号付き G/L が整数 -8–7 と一致する。
A と B を交換すると G と L は交換され、E は保持される。
G、E、L は相互排他的で、かつ網羅的である。

次に四ビットブロック二つをカスケード接続し、0x0F/0x10、0x7F/0x80、上位半分が等しく下位半分が異なるものなどの境界ペアを狙います。

機能シミュレーターはブール関係を確立します。最終技術における物理的な伝搬遅延、電気的互換性、タイミングクロージャを確立するものではありません。

参考資料

Texas Instruments SN74LS85 4 ビット大小比較器の製品ページとデータシート