組み合わせ論理回路

「1つのパスを選択する」という点では同じですが、MUXはデータの中から1つを選択し、デコーダは番号をチップセレクトに変換し、優先エンコーダは複数の要求の中からどのリクエストを先にサービスするかを決定します。これらの入力制約、有効極性、および変化のタイミングを理解することは、単にデバイスの名称を暗記するよりもはるかに役立ちます。本稿では、選択と算術演算を主軸とし、真理値表、ゲートレベルの構造、および実際のインターフェースを対応付けます。

「記憶がない」ことと「遅延がない」ことは同じではない

理想的な組み合わせ回路は Y=F(X) を満たします。現在の入力が与えられれば、出力の定常値は一意に定まり、過去の入力を解釈するために記憶を必要としません。通常、組み合わせフィードバックのないゲートネットワークで実装されます。ラッチ、フリップフロップ、カウンタ、シフトレジスタは状態を保持するため、順序論理回路に分類されます。外部クロックの有無だけでは不十分です。ラッチはイネーブルのレベルでデータを保持でき、クロックのないフィードバック回路でも状態や振動を持つ可能性があります。

実際の組み合わせ論理では、入力が変化した後に安定するまでに時間がかかります。伝播遅延は、入力から出力までのパス、立ち上がり/立ち下がりの方向、電源電圧、温度、および負荷によって決まります。遷移の過程では一時的なエラー（グリンチ）が発生する可能性があります。機能真理値表は安定した結果を記述するものであり、それに基づいて任意の時刻の出力が正しいと推論することはできません。

MUX：選択と論理分解は同じこと

2:1 MUX のデータ入力を A、B、選択入力を S とします。

Y=¬S·A+S·B。

否定は S に対して行わなければなりません。¬A·S+B·S は S=0 のときに常に 0 となり、2:1 の選択を行うことができません。幅が 8 bit の 2:1 MUX は、8つのデータビットが1つの選択信号を共有するものであり、1ビットのMUX 1つで1バイトを収められるわけではありません。

一般に、任意のブール関数は変数 S について F=¬S·F|S=0+S·F|S=1 に展開できます。これを Shannon 展開と呼びます。2つのサブ関数を MUX に接続することで、代数的分解を回路に変換できます。例えば F=A⊕B において、A を選択信号とすると、A=0 のときのサブ関数は B、A=1 のときのサブ関数は ¬B となり、反転器1つと MUX 1つで実現できます。

4:1 MUX には2ビットの選択コードが必要ですが、3つのユニットと2層の 2:1 MUX ツリーでも実現できます。第1層でそれぞれグループを選択し、第2層で2つのグループのいずれかを選択します。ここでは 3つの MUX と2層の遅延 となり、ユニット数とパスの深さを混同してはいけません。より大きな選択ネットワークでは、選択線のファンアウト、配線、および負荷の影響も受けます。

MUX 自体は、どの入力が順番で回ってくるかを保持しません。並列から直列への変換には、カウント/状態およびサンプリングのタイミングが必要です。グルッチフリーなクロッチスイッチングも、通常のデータ MUX だけでは保証できません。選択線が2つのクロックで異なる電位で変化すると、短いパルス（グリンチ）が発生する可能性があるためです。

デコーダ：有効極性とアドレスの被覆範囲がチップセレクトの動作を決定する

ローアクティブなイネーブル E、入力 A₁A₀ に対して、理想的なローアクティブな 2-to-4 デコーダは以下のようになります：Y₀=E¬A₁¬A₀，Y₁=E¬A₁A₀，Y₂=EA₁¬A₀，Y₃=EA₁A₀。E=1 のとき、ちょうど1つの出力が 1 になります。E=0 のとき、すべて 0 になります。ここで言う one-hot は定常状態の機能制約です。

実際のチップは必ずしもローアクティブ出力を備えているわけではありません。74HC138 の選択出力はローアクティブです。2つのローアクティブイネーブルはローでなければならず、もう1つのローアクティブイネーブルはハイでなければならず、そうでなければすべての出力がハイになります。したがって、データシートを読む際は、まずイネーブルを確認し、どのパスがローに引き下げられるかを確認します。Nexperia：74HC/HCT138 機能表

例えば、16ビットアドレス空間において、8 KiB のメモリが 0x8000～0x9FFF に配置されているとします。A₁₅A₁₄A₁₃ は 100 でなければなりません。下位 13 ビットはデバイス内部のアドレスに使用されます。ローアクティブなヒット条件は hit=A₁₅¬A₁₄¬A₁₃ です。さらにローアクティブな access で実際のアクセスを制限する場合、ローアクティブなチップセレクトは CS_n=¬(hit·access) となります。A₁₅ だけをデコードすると、0x8000～0xFFFF のすべてが選択され、同じチップが複数のアドレスウィンドウでミラーリングされます。

複数のアドレスビットが切り替わる際、各ビットが絶対的に同時に到達するわけではないため、デコーダの出力は一時的に間違ったデバイスを選択する可能性があります。特に、制限されていないアドレスデコードのグリンチが直接ライトパルスとならないようにする必要があります。バスプロトコルに従ってアドレスの安定ウィンドウを保証し、適切なリード/ライト/アクセス制御で制限する必要があります。レジスタを追加することでサンプリング方法を変更できますが、問題が解決するかどうかは、セットアップ/ホールド時間とシステムの遅延要件に依存します。

7セグメントディスプレイのデコーディングは、1ビット有効出力ではありません。1つの数字に対して複数のセグメントが点灯し、コモンアノード/コモンカソードの区別と駆動電流も考慮する必要があります。デコーダは論理マッピングを解決しますが、LED を十分に駆動する能力を自動的に備えているわけではありません。

エンコーダ：番号は「有効な番号」と一緒に伝達されなければならない

通常のエンコーダは通常、入力が one-hot であることを要求します。優先エンコーダは複数の要求が同時に有効であることを許可し、固定された順序でそのうちの1つの番号を出力します。ローアクティブな4路の要求 R₃ が最も高い優先度を持つと仮定すると：

• valid=R₃+R₂+R₁+R₀；
• code₁=R₃+R₂；
• code₀=R₃+¬R₂·R₁。

例えば、要求 0110 は R₂ と R₁ を同時に含み、結果は code=10、valid=1 となります。0001 は code=00、valid=1 を生成し、0000 は code=00、valid=0 となります。valid が欠如していると、「要求がない」状態と「パス 0 が要求している」状態を区別できません。実際のデバイスでは、カスケード接続用のグループ選択とイネーブル出力を提供する場合もあります。74HC148 の要求入力およびエンコード出力はローアクティブ論理を採用しており、上記のローアクティブな公式をそのまま適用することはできません。TI：SN74HC148

固定優先エンコーダは、毎回最も高い優先度の要求を優先し、誰が長く待っているかを記憶しません。公平なラウンドロビンが必要な場合は、最後のサービス位置を保存する必要があり、状態を持つアービトレータとなります。また、出力番号がサービス完了を意味するわけではないため、grant、accept、および要求の取り消しはプロトコルで定義する必要があります。

加算器：1ビット演算からビット幅とオーバーフローへ

半加算器は A+B を処理し、出力 S=A⊕B、C=AB を生成し、整数等式 A+B=S+2C を満たします。全加算器はさらに下位からのキャリー Cᵢ を受け取ります：

Sᵢ=Aᵢ⊕Bᵢ⊕Cᵢ，Cᵢ₊₁=AᵢBᵢ+(Aᵢ⊕Bᵢ)Cᵢ。

半加算器は、入力キャリーがないことが確定している2ビットの加算に適しており、「最下位ビットでのみ使用できる」という物理的な制限があるわけではありません。複数ビットの加算では、カスケード接続とキャリー入力のサポートを容易にするため、通常、全加算器が使用されます。

リップルキャリーは下位から順に伝播します。生成項 Gᵢ=AᵢBᵢ、伝播項 Pᵢ=Aᵢ⊕Bᵢ とすると、Cᵢ₊₁=Gᵢ+PᵢCᵢ です。2段展開すると C₂=G₁+P₁G₀+P₁P₀C₀ となり、中間のキャリー出力を待つことなく、元の入力から直接計算できます。

アドバンスドキャリーはこの展開を利用し、グループ化やプレフィックス構造によって論理深度をさらに制御します。無謀にすべての項を大きなファンインのゲートに展開すると、ファンイン、負荷、および配線の制限に直面します。すべての「アドバンスドキャリー」を固定された O(log n) の遅延として一括りにすることはできません。制限されたファンインモデルでは、バランスの取れたプレフィックスネットワークは対数論理深度を実現できますが、実際のチップでは配線の影響も受けます。

キャリーとオーバーフローは異なる質問に答える

4ビット加算器で下位4ビットのみを保持する場合、結果は mod 16 でラップアラウンドします。1111+0001 は下位 0000、キャリー 1 を生成します。無符号では 15+1 は範囲外ですが、有符号の2の補数では −1+1=0 でオーバーフローしていません。0111+0001 は 1000、キャリー 0 を生成します。無符号では 7+1 は正常ですが、有符号の範囲 −8～7 ではオーバーフローしています。

2の補数加算におけるオーバーフローの条件は、「2つのオペランドが同じ符号であり、結果が異なる符号である」ことです。これは、符号ビットの入力キャリーと出力キャリーの XOR によって検出できます。減算は A+¬B+1 を使用して加算器を再利用できます。この実装では、最終的なキャリー 1 は無符号減算においてボローなしを意味しますが、プロセッサのフラグビットの名前と極性はアーキテクチャの定義を別途参照する必要があります。

比較器もまた、符号の規約を必要とします。1000 と 0111 を無符号で比較すると 8>7 となりますが、4ビットの2の補数では −8<7 となります。無符号比較は最上位ビットから開始し、最初に異なるビットの位置で大小が決定されます。符号が異なる場合、有符号比較はまず符号ビットによって決定され、無符号のキャリー判断をそのまま適用することはできません。

同じビットで桁上げとオーバーフローが違う理由は？

既定の7+1は最終キャリーなしでも1000へ越える。Aを1111にすると加算でキャリーが出るが、補数の−1+1はオーバーフローしない。表の最後列は次桁へのキャリーで和ビットではない。

$$V=C_{in,MSB}\oplus C_{out,MSB}$$

LUT と HDL：組み合わせ関数がどのようにプログラム可能なデバイスに実装されるか

n 入力、1 出力 の LUT には、2ⁿ 個の真理値表ビットが必要です。「2ⁿ 入力の LUT」ではありません。例えば、3入力の関数は8つの入力組み合わせを持ち、8つの出力ビットを保存し、入力が選択アドレスとして機能します。SRAM 型 FPGA では、設定用メモリビットと選択ネットワークを使用してこの構造が実装されることが一般的です。実際には、分割可能な LUT、マルチ出力ユニット、専用キャリーチェーン、および論理ブロックがアーキテクチャに応じて組み合わさり、単一の LUT 数で全製品を概括することはできません。

HDL で組み合わせ論理を記述する際、各出力はすべての分岐で定義されている必要があります。以下に、2:1 MUX の SystemVerilog 連続代入を示します：

assign y = sel ? b : a;

プロシージャルブロックで特定の分岐の出力を漏らすと、「その分岐では古い値を保持する」ことを意味し、ラッチが推論される可能性があります。重要なのはクロックがあるかどうかではなく、記述が記憶を要求しているかどうかです。論理合成後、推論されたユニットとタイミングパスを確認する必要があります。PAL/GAL の積項構造、CPLD のマクロセル、および FPGA の LUT は異なる実装リソースであり、実現可能な関数の規模とタイミングには制限があります。任意の規模の論理が任意のデバイスにロードできるとは限りません。

組み合わせ遅延から同期タイミング予算へ

レジスタの間に組み合わせ論理を挿入した後、ゼロクロックスキューの簡略化されたセットアップ時間の条件は以下の通りです：

Tclk ≥ tCQ,max + tcomb,max + tsetup + 追加のタイミングマージン。

例えば、教育用の予算として tCQ=1 ns、組み合わせの最悪遅延 7 ns、セットアップ時間 1 ns、追加マージン 1 ns とすると、周期は少なくとも 10 ns となり、理想的な予算の上限は 100 MHz となります。これはチップの実測周波数ではなく、各パスの静的タイミング解析に取って代わるものではありません。最速パスはホールド要件も満たさなければならず、最長パスのみをチェックすることはできません。クロックスキュー、ジッター、および外部 I/O 制約は、実際の分析に追加する必要があります。MIT：同期組み合わせとタイミング制約

最終段のレジスタは、サンプリング条件が満たされた場合にのみ中間のグリンチをマスクします。グリンチがクロック、非同期リセット、またはライトイネーブルなどの敏感な制御パスに入ると、すでに副作用を生じている可能性があります。クロックドメイン間問題も、「1クロック分遅らせればよい」と概括することはできません。

網羅的な検証で機能を確認し、1つの例だけを見ない

以下に、2:1 MUX、全加算器、優先エンコーダを検証し、4ビット加算のキャリーと有符号オーバーフローを列挙します。これは離散機能を検証するものであり、ゲート遅延、グリンチ、または電気的特性をシミュレートするものではありません。

from itertools import product

for a, b, s in product((0, 1), repeat=3):
    assert ((1-s)*a | s*b) == (b if s else a)
    total = a+b+s
    out = a ^ b ^ s
    carry = (a & b) | ((a ^ b) & s)
    assert total == out + 2*carry

for req in range(16):
    r0, r1, r2, r3 = [(req >> i) & 1 for i in range(4)]
    valid = r0 | r1 | r2 | r3
    code = ((r3 | r2) << 1) | (r3 | ((1-r2) & r1))
    assert valid == int(req != 0)
    assert code == (req.bit_length()-1 if req else 0)

signed = lambda x: x if x < 8 else x-16
for a, b in product(range(16), repeat=2):
    result = (a+b) & 15
    carry = (a+b) >> 4
    overflow = ((a ^ b) & 8) == 0 and ((a ^ result) & 8) != 0
    assert carry == int(a+b > 15)
    assert overflow == (not -8 <= signed(a)+signed(b) <= 7)

print("MUX、全加算器、優先エンコーダ、および 256 組の 4ビット加算チェック通過")

さらに調べる

• 論理ゲートとブール代数：カルノ図、冗長な被覆、および静的グリンチ。
• 順序論理回路：状態、フリップフロップ、セットアップ/ホールド、および同期。
• 論理レベルとインターフェース物理層：電圧範囲、出力駆動、およびバス接続。