デジタル回路-K-Mapメソッド

前の章で、ブールの仮定と定理を使用してブール関数を簡略化しました。これは時間のかかるプロセスであり、各ステップの後に簡略化された式を書き直す必要があります。

この難しさを克服するために、 Karnaugh はブール関数を簡単な方法で単純化する方法を導入しました。この方法は、カルノーマップ法またはKマップ法として知られています。これはグラフィカルな方法で、「n」個の変数の2 ^ n ^個のセルで構成されます。隣接するセルは、単一ビット位置のみが異なります。

2〜5変数のKマップ

K-Mapメソッドは、2変数のブール関数を5変数に最小化するのに最適です。次に、2〜5個の変数のK-Mapsについて1つずつ説明します。

2可変Kマップ

変数の数が2であるため、2変数Kマップのセルの数は4です。次の図は、 2変数K-Map を示しています。

2変数K-Map

4つの隣接する最小用語をグループ化する可能性は1つだけです。
2つの隣接する最小項をグループ化する可能な組み合わせは、\ {（m〜0〜、m〜1〜）、（m〜2〜、m〜3〜）、（m〜0〜、m〜2〜）、および（m 〜1〜、m〜3〜）}。

3可変Kマップ

変数の数が3であるため、3変数Kマップのセルの数は8です。次の図は、 3変数K-Map を示しています。

3変数K-Map

8つの隣接する最小用語をグループ化する可能性は1つだけです。
4つの隣接する最小項をグループ化する可能な組み合わせは、\ {（m〜0〜、m〜1〜、m〜3〜、m〜2〜）、（m〜4〜、m〜5〜、m〜7〜、 m〜6〜）、（m〜0〜、m〜1〜、m〜4〜、m〜5〜）、（m〜1〜、m〜3〜、m〜5〜、m〜7〜）、（m〜3〜、m〜2〜、m〜7〜、m〜6〜）および（m〜2〜、m〜0〜、m〜6〜、m〜4〜）}。
2つの隣接する最小用語をグループ化する可能な組み合わせは、\ {（m〜0〜、m〜1〜）、（m〜1〜、m〜3〜）、（m〜3〜、m〜2〜）、（m 〜2〜、m〜0〜）、（m〜4〜、m〜5〜）、（m〜5〜、m〜7〜）、（m〜7〜、m〜6〜）、（m〜6 〜、m〜4〜）、（m〜0〜、m〜4〜）、（m〜1〜、m〜5〜）、（m〜3〜、m〜7〜）および（m〜2〜、 m〜6〜）}。
x = 0の場合、3変数Kマップは2変数Kマップになります。

4可変Kマップ

変数の数が4であるため、4変数Kマップのセルの数は16です。次の図は、 4変数K-Map を示しています。

image

16の隣接する最小用語をグループ化する可能性は1つだけです。
R〜1〜、R〜2〜、R〜3〜、およびR〜4〜は、それぞれ第1行、第2行、第3行、および第4行の最小項を表します。同様に、C〜1〜、C〜2〜、C〜3〜、C〜4〜は、それぞれ1列目、2列目、3列目、4列目の最小項を表します。 8つの隣接する最小用語をグループ化する可能な組み合わせは、\ {（R〜1〜、R〜2〜）、（R〜2〜、R〜3〜）、（R〜3〜、R〜4〜）、（R 〜4〜、R〜1〜）、（C〜1〜、C〜2〜）、（C〜2〜、C〜3〜）、（C〜3〜、C〜4〜）、（C〜4 〜、C〜1〜）}。
w = 0の場合、4変数Kマップは3変数Kマップになります。

5可変Kマップ

変数の数が5であるため、5変数Kマップのセルの数は32です。次の図は、 5変数K-Map を示しています。

5変数K-Map

32の隣接する最小用語をグループ化する可能性は1つだけです。
16個の隣接する最小用語をグループ化する方法は2つあります。すなわち、m〜0〜からm〜15〜およびm〜16〜からm〜31〜までの最小項のグループ化。
v = 0の場合、5変数Kマップは4変数Kマップになります。

上記のすべてのKマップでは、最小用語表記のみを使用しました。同様に、Max用語表記のみを使用できます。

K-Mapsを使用したブール関数の最小化

ブール関数が「1」である入力の組み合わせを検討する場合、ブールマップ関数を取得します。これは、Kマップを簡略化した後の*製品の標準和*形式です。

同様に、ブール関数が「0」である入力の組み合わせを考慮する場合、ブールマップ関数を取得します。これは、Kマップを単純化した後の「合計の標準積」形式になります。

製品の標準合計フォームを取得するには、Kマップを簡素化するためのこれらの*ルールに従ってください。

ブール関数に存在する変数の数に基づいて、それぞれのKマップを選択します。
ブール関数が最小項の合計形式として与えられる場合、K-mapのそれぞれの最小項セルに配置します。ブール関数が積の形式として与えられる場合、与えられた積の項が有効なKマップのすべての可能なセルにそれらを配置します。
隣接するものの最大数をグループ化する可能性を確認してください。 2のべき乗でなければなりません。 2の最大電力から2の最小電力まで開始します。最大電力はKマップで考慮される変数の数に等しく、最小電力はゼロです。 各グループ化は、リテラルまたは1つの製品用語のいずれかを提供します。 prime implicant *として知られています。少なくとも1つの「1」が他のグループでカバーされておらず、そのグループのみがカバーしている場合、プライムインプリカントは「必須のプライムインプリカント」と言われます。
すべての主な含意者と必須の主な含意者を書き留めてください。簡略化されたブール関数には、すべての必須のプライムインプリカントと必要なプライムインプリカントのみが含まれています。

注1 *-入力の組み合わせに対して出力が定義されていない場合、それらの出力値は *do n’t careシンボル 'x' で表されます。つまり、「0」または「1」のいずれかと見なすことができます。

注2 *-ドントケア用語も存在する場合、Kマップのそれぞれのセルにドントケア「x」を配置します。隣接するものの最大数をグループ化するのに役立つドントケア「x」のみを考慮してください。そのような場合、do n’t careの値を「1」として扱います。

例

Kマップを使用して、次のブール関数 f（W、X、Y、Z）= WX’Y ’+ WY + W’YZ’ を*単純化*しましょう。

指定されたブール関数は、製品の合計形式です。 4つの変数W、X、Y、Zがあります。したがって、 4変数K-map が必要です。次の図に、指定された積項に対応する変数を持つ 4変数K-map を示します。

最小化の例

ここでは、Kマップの次のセルに1が配置されます。

行4と列1と列2の共通部分に共通するセルは、製品用語* WX’Y ’*に対応しています。
行3と4と列3と4の共通部分に共通するセルは、積項 WY に対応しています。
行1と2、および列4の共通部分に共通するセルは、製品用語* W’YZ '*に対応しています。

16隣接するものまたは8隣接するものをグループ化する可能性はありません。 4つの隣接するものをグループ化する3つの可能性があります。これらの3つのグループ化の後、グループ化されていないものは1つもありません。したがって、2つの隣接するグループのグループ化をチェックする必要はありません。これらの3つの*グループ化*を持つ 4変数K-map を次の図に示します。

3つのグループ

ここには、3つの主要な含意者WX、WY、YZがあります。これらの主要な含意はすべて、以下の理由により*必須*です。

4番目の行のグループ化の2つの*（m〜8〜＆m〜9〜）*は、他のグループ化によってカバーされません。 4行のグループ化のみがこれら2つの行をカバーします。
正方形のグループ化の単一の*（m〜15〜）*は、他のグループ化によってカバーされません。正方形のグループのみがそのグループをカバーします。
4番目の列グループの2つの*（m〜2〜＆m〜6〜）*は、他のグループではカバーされません。これら2つをカバーするのは4番目の列グループのみです。

したがって、*簡略化されたブール関数*は

*f = WX ’+ WY + YZ’*

和形式の標準積を取得するには、Kマップを簡略化するためのこれらの*ルールに従ってください。

ブール関数に存在する変数の数に基づいて、それぞれのKマップを選択します。
ブール関数が最大項形式の積として与えられる場合、Kマップのそれぞれの最大項セルにゼロを配置します。ブール関数が合計の形式として与えられた場合、与えられた合計項が有効なKマップのすべての可能なセルにゼロを配置します。
隣接するゼロの最大数をグループ化する可能性を確認してください。 2のべき乗でなければなりません。 2の最大電力から2の最小電力まで開始します。最大電力はKマップで考慮される変数の数に等しく、最小電力はゼロです。 各グループ化は、リテラルまたは1つの合計項を提供します。 prime implicant として知られています。少なくとも1つの「0」が他のグループでカバーされておらず、そのグループのみがカバーしている場合、プライムインプリカントは *essential prime implicant と呼ばれます。
すべての主な含意者と必須の主な含意者を書き留めてください。簡略化されたブール関数には、すべての必須のプライムインプリカントと必要なプライムインプリカントのみが含まれています。

注-ドントケア用語も存在する場合は、Kマップの各セルにドントケア「x」を配置します。隣接するゼロの最大数をグループ化するのに役立つドントケア「x」のみを考慮してください。そのような場合、do n’t careの値を「0」として扱います。

例

Kマップを使用して、次のブール関数$ f \ left（X、Y、Z \ right）= \ prod M \ left（0,1,2,4 \ right）$を*単純化*しましょう。

指定されたブール関数は、最大項形式の製品です。 X、Y、Zの3つの変数があります。したがって、3つの可変Kマップが必要です。指定されたMaxの用語は、M〜0〜、M〜1〜、M〜2〜＆M〜4〜です。与えられたMax項に対応するゼロを持つ3つの*変数Kマップ*を次の図に示します。

Prime Implicants

8つの隣接するゼロまたは4つの隣接するゼロをグループ化する可能性はありません。 2つの隣接するゼロをグループ化する3つの可能性があります。これらの3つのグループ化の後、グループ化されていないゼロは1つもありません。これら3つの*グループ化*を持つ 3変数K-map を次の図に示します。

ungrouped

ここでは、X + Y、Y + Z、Z + Xの3つの主要なインプリカントを取得しました。各グループの1つのゼロは、個々のグループを除き、他のグループではカバーされないため、これらの主な暗黙のすべては*必須*です。