デジタル論理：ゲート・カルノー図・フリップフロップ：ステップごとの解答つき練習問題

11、0、そしてゲート

デジタル回路は 0（低電圧、偽）と 1（高電圧、真）の 2 つの値で動作します。論理ゲートは 1 つ以上の入力を受け取り、1 つの出力を返します。

• AND は、すべての入力が 1 のときだけ 1 を出力します。A·B または AB と書きます。
• OR は、少なくとも 1 つの入力が 1 のとき 1 を出力します。A + B と書きます。
• NOT は反転します：0 は 1 に、1 は 0 になります。A′（または A の上にバー）と書きます。
• NAND と NOR は、AND と OR のあとに NOT を付けたものです。記号の小さな丸は「反転」を意味します。
• XOR（A ⊕ B）は、入力が異なるとき 1 を出力します。

真理値表は、入力のすべての組み合わせに対する出力を一覧にしたもので、n 個の入力なら 2ⁿ 行になります。行 ABC = 101 は 5 番目の行で、最小項 m₅ と呼ばれます。

2ブール代数

論理式は、通常の代数と似た規則に加えて、いくつか独自の規則に従います。特に役立つものは次のとおりです：

結合則 X·Y + X·Y′ = X は簡単化の核心です：1 つの変数だけが異なる 2 つの項は 1 つにまとまり、その変数は消えます。

積和形（SOP）は AND 項の OR で、たとえば F = AB′ + C です。和積形（POS）は OR 項の AND で、たとえば F = (A + B)(B′ + C) です。各積項はリテラル、つまりプライム付きまたはなしの変数からつくられます。

3カルノー図

カルノー図は、隣り合うセルがちょうど 1 つの変数だけ異なるように描いた格子状の真理値表です。そのため、行と列は 2 進数の順ではなく 00、01、11、10（グレイコード）の順に並びます。

1. すべての最小項のセルに 1 を書き込みます。各セルの小さな数字は、その最小項の番号です。
2. 1 のまわりに、1、2、4、8、16 個のセルからなる長方形を描きます。グループは端をまたいでもかまいません：左端と右端の列は隣り合っており、上端と下端の行も同様です。
3. 各グループはできるだけ大きくし、すべての 1 が覆われるまで、グループの数はできるだけ少なくします。
4. 各グループを積項として読みます：グループの中で変化しない変数だけを残します。2ᵏ 個のセルのグループでは、k 個の変数が消えます。

上の図では、4 つの 1 が 1 つのグループになります。その中で A と C は変化し、B = 1 だけが変わらないので、F = B です。

X と書かれたセルはドントケアで、決して現れない入力の組み合わせです。グループが大きくなるときは X を 1 として使い、そうでなければ無視します。代わりに 0 をグループにすると、最小の POS 形が得られます。

4例題

すべてのステップをたどりましょう。開く前に次のステップを予想してみましょう。

5フリップフロップとカウンタ

ゲートは入力にすぐ反応します。フリップフロップは 1 ビットを記憶し、クロックの有効エッジ（ふつうは立ち上がりエッジ）でしか変化しません。

• D フリップフロップ：クロックエッジごとに Q が D になります（Q⁺ = D）。
• T フリップフロップ：T = 1 のときトグル（反転）し、T = 0 のとき保持します。
• JK フリップフロップ：JK = 00 は保持、01 は 0 にリセット、10 は 1 にセット、11 はトグルです。

トグルするフリップフロップは立ち上がりエッジごとに変化するので、出力の周波数はクロックの半分になります。n 個をつなぐと、2ⁿ 個の状態をもつ n ビットの2 進カウンタになります。mod-N カウンタは 0, 1, …, N − 1 と数えて 0 に戻ります。2ⁿ ≥ N を満たす最小の n が必要で、最後の出力は f_clk/N で動作します。

リップルカウンタでは各段が前の段でクロックされるので、遅延が足し合わされます：クロック周期は少なくとも n·t_pd 必要です。シフトレジスタ型のカウンタは状態数が少なくなります：n 個のフリップフロップのリングカウンタは n 状態、ジョンソンカウンタは 2n 状態です。

6よくある間違い

• カルノー図の列を 00, 01, 10, 11 と書いてしまう。順序はグレイコードで、00, 01, 11, 10 です。
• グループが図の端をまたげることを忘れる。
• 3 個や 6 個のセルでグループをつくる。グループのセル数は 1, 2, 4, 8, 16 個です。
• 役に立たないドントケアまで覆ってしまう：X は必ずしも覆う必要はありません。
• グループを読むときに、変化する変数を残してしまう。残すのは一定のままの変数だけです。
• カウンタが折り返すことを忘れる：n ビットのカウンタは 2ⁿ を法として数えます。

7試験問題の例

• やさしい：与えられた入力でゲート回路を評価する、真理値表の 1 を数える、カルノー図に最小項を置く、ある関数に必要な NAND ゲートの数や最悪の場合の伝搬遅延を求める、といった問題です。
• ふつう：式の簡単化、カルノー図による最小の SOP 形または POS 形、マルチプレクサで構成した関数、図の孤立した 1 を扱います。
• むずかしい：ドントケアのある図、必須主項、フリップフロップのタイミング図、多数のパルスのあとのカウンタ、フリップフロップの個数や出力周波数、シフトレジスタを扱います。

簡単化した式は、真理値表の 1、2 行で確かめましょう：元の式と簡単化した式は、同じ出力にならなければなりません。