Digital-circuits-quine-mccluskey-tabular-method
Quine-McCluskey表形式メソッド
前の章で、ブール関数を最大5変数まで最小化する便利な方法であるKマップ法について説明しました。 ただし、この方法を使用して5つ以上の変数を持つブール関数を単純化することは困難です。
Quine-McClukeyテーブル方式は、プライムインプリカントの概念に基づいたテーブル方式です。 primim implicant は積（または合計）項であり、特定のブール関数の他の積（または合計）項と組み合わせてさらに削減することはできません。
この表形式のメソッドは、次のブールIDを繰り返し使用して、プライムインプリカントを取得するのに役立ちます。
xy + xy ’= x（y + y’）= x.1 = x
Quine-McCluskey表法の手順
Quine-McClukeyテーブル方式を使用してブール関数を単純化するには、次の手順に従います。
- ステップ1 *-与えられた最小項を*昇順*に配置し、バイナリ表現に存在するものの数に基づいてグループを作成します。 そのため、ブール関数に「n」個のブール変数が存在する場合、または最小項に相当するバイナリに「n」個のビットが存在する場合、*最大で「n + 1」個のグループ*が存在します。
- ステップ2 *-*連続グループ*に存在する最小用語を比較します。 1ビットの位置のみに変更がある場合は、これらの2つの最小項のペアを取得します。 このシンボル「_」を異なるビット位置に配置し、残りのビットをそのままにします。
ステップ3 *-すべての *prime implicants が得られるまで、新しく形成された用語でstep2を繰り返します。
ステップ4 *- *prime implicant table を作成します。 行と列のセットで構成されます。 プライムインプリカントは行単位で配置でき、最小項は列単位で配置できます。 各プライムインプリカントでカバーされる最小項に対応するセルに「1」を配置します。
ステップ5 *-各列を観察することにより、重要なプライムインプリカントを見つけます。 最小項が1つのプライムインプリカントのみでカバーされている場合、それは *essential prime implicant です。 これらの重要な主要なインプリカントは、単純化されたブール関数の一部になります。
- ステップ6 *-各必須プライムインプリカントの行と、その必須プライムインプリカントでカバーされている最小項に対応する列を削除して、プライムインプリカントテーブルを縮小します。 Reduced prime implicantテーブルに対して手順5を繰り返します。 指定されたブール関数のすべての最小項が終了したときに、このプロセスを停止します。
例
次のブール関数$ f \ left（W、X、Y、Z \ right）= \ sum m \ left（2,6,8,9,10,11,14,15 \ right）を*単純化*しましょう$ Quine-McClukeyテーブル方式を使用。
指定されたブール関数は、最小項の合計*形式です。 4つの変数W、X、Y、Zがあります。 指定された最小条件は、2、6、8、9、10、11、14、および15です。 これらのバイナリ相当に存在するものの数に基づくこれらの最小項の昇順は、2、8、6、9、10、11、14、および15です。 次の表は、これらの min項と同等のバイナリ*表現を示しています。
グループ名
最小条件
W
X
Y
Z
GA1
2
0
0
1
0
8
1
0
0
0
GA2
6
0
1
1
0
9
1
0
0
1
10
1
0
1
0
GA3
11
1
0
1
1
14
1
1
1
0
GA4
15
1
1
1
1
与えられた最小項は、それらのバイナリ等価物に存在するものの数に基づいて4つのグループに配置されます。 次の表は、隣接するグループからの*最小用語のマージ*を示しています。
グループ名
最小条件
W
X
Y
Z
GB1
2,6
0
-
1
0
2,10
-
0
1
0
8,9
1
0
0
-
8,10
1
0
-
0
GB2
6,14
-
1
1
0
9,11
1
0
-
1
10,11
1
0
1
-
10,14
1
-
1
0
GB3
11,15
1
-
1
1
14,15
1
1
1
-
隣接するグループと1ビットの位置のみが異なる最小条件はマージされます。 その異なるビットは、この記号「-」で表されます。 この場合、3つのグループがあり、各グループには2つの最小用語の組み合わせが含まれています。 次の表は、隣接グループからの*最小用語ペアのマージ*を示しています。
グループ名
最小条件
W
X
Y
Z
GB1
2,6,10,14
-
-
1
0
2,10,6,14
-
-
1
0
8,9,10,11
1
0
-
-
8,10,9,11
1
0
-
-
GB2
10,11,14,15
1
-
1
-
10,14,11,15
1
-
1
-
1ビット位置のみが異なるmin項ペアの連続したグループがマージされます。 その異なるビットは、この記号「-」で表されます。 この場合、2つのグループがあり、各グループには4つの最小用語の組み合わせが含まれています。 ここでは、これらの4分の用語の組み合わせを2行で使用できます。 したがって、繰り返し行を削除できます。 冗長な行を削除した後の縮小されたテーブルを以下に示します。
| Group Name | Min terms | W | X | Y | Z |
|---|---|---|---|---|---|
| GC1 | 2,6,10,14 | - | - | 1 | 0 |
| 8,9,10,11 | 1 | 0 | - | - | |
| GC2 | 10,11,14,15 | 1 | - | 1 | - |
隣接するグループからの最小項の組み合わせをさらにマージすることはできません。それらは1ビット以上の位置で異なるためです。 上記の表には3つの行があります。 したがって、各行には1つのプライムインプリカントが与えられます。 したがって、 prime implicants はYZ '、WX’およびWYです。
*prime implicant table* を以下に示します。| Min terms/Prime Implicants | 2 | 6 | 8 | 9 | 10 | 11 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|
| YZ’ | 1 | 1 | 1 | 1 | ||||
| WX’ | 1 | 1 | 1 | 1 | ||||
| WY | 1 | 1 | 1 | 1 |
プライムインプリカントは行単位で配置され、最小項は列単位で配置されます。 1は、暗黙の主な行と対応する最小項の列の共通セルに配置されます。
最小項2および6は、1つの主な暗黙の* YZ ’*によってのみカバーされます。 したがって、これは*本質的なプライムインプリカント*です。 これは、単純化されたブール関数の一部になります。 次に、この主な暗黙の行と対応する最小項の列を削除します。 縮約プライムインプリカントテーブルを以下に示します。
| Min terms/Prime Implicants | 8 | 9 | 11 | 15 |
|---|---|---|---|---|
| WX’ | 1 | 1 | 1 | |
| WY | 1 | 1 |
最小用語8および9は、1つの主な暗黙の* WX ’*によってのみカバーされます。 したがって、これは*本質的なプライムインプリカント*です。 これは、単純化されたブール関数の一部になります。 次に、この主な暗黙の行と対応する最小項の列を削除します。 縮約プライムインプリカントテーブルを以下に示します。
| Min terms/Prime Implicants | 15 |
|---|---|
| WY | 1 |
最小ターム15は、1つの主な暗黙の WY によってのみカバーされます。 したがって、これは*本質的なプライムインプリカント*です。 これは、単純化されたブール関数の一部になります。
この例の問題では、3つの主要なインプリカントがあり、3つすべてが必須です。 したがって、*簡略化されたブール関数*は
*f（W、X、Y、Z）= YZ ’+ WX’ + WY*