正規正規形

ブール代数では、任意のブール関数は、最小項の論理和 (OR) として、標準選言正規形( CDNF ) ^{[1] 、} 最小項標準形、または積和( SoPまたはSOP )で表現できます。ド・モルガン双対は、最大項の論理積 (AND) である標準連言正規形( CCNF )、最大項標準形、または和の積( PoSまたはPOS )です。これらの形式はブール関数の簡略化に役立ち、ブール式全般、特に デジタル回路の最適化において非常に重要です。

他の標準形式には、素因数の完全な和またはブレイク標準形式（およびその双対）、および代数標準形式 （ジェガルキンまたはリード・ミュラーとも呼ばれる）が含まれます。

変数のブール関数の場合、最小項は各変数が正確に 1 回出現する積項です(補数形式または非補数形式のいずれか)。したがって、最小項は補数演算子と結合演算子 (論理 AND ) のみを使用するn変数の論理式です。最小項は、入力変数の 1 つの組み合わせに対してのみ true 値 (最小の非自明な量) を返します。たとえば、a b ' cは、 aとc の両方が true でbが false の場合にのみ true になります。つまり、入力の配置がa = 1、b = 0、c = 1 の場合、結果は 1 になります。 ${\displaystyle n}$${\displaystyle {x_{1},\dots ,x_{n}}}$${\displaystyle n}$

最小項式の変数は直接形式または補形式のいずれか、つまり変数ごとに 2 つの選択肢があるため、 n 個の変数の最小項は 2 ⁿ個あります。最小項は、変数の補形式パターンを 2 進数でエンコードして番号が付けられることが多く、変数は標準的な順序 (通常はアルファベット順) で記述されます。この規則により、直接形式 ( ) に値 1 が割り当てられ、補形式 ( ) に値 0 が割り当てられます。したがって、最小項は になります。たとえば、最小項は 110 ₂  = 6 ₁₀と番号が付けられ、 と表示されます。 ${\displaystyle x_{i}}$${\displaystyle x'_{i}}$${\displaystyle \sum \limits _{i=1}^{n}2^{i-1}\operatorname {値} (x_{i})}$${\displaystyle abc'}$${\displaystyle m_{6}}$

論理関数の真理値表が与えられれば、その関数を「積の和」または「最小項の和」として記述することができます。これは、選言正規形の特殊な形式です。たとえば、加算回路の 1 ビット位置のロジックの算術和ビットuの真理値表が、加数とキャリーインciからのxとyの関数として与えられている場合、次のようになります。

出力が 1 になる行は 2 番目、3 番目、5 番目、8 番目であることに注目すると、u をmintermとの合計として記述できます。これを検証する場合、3 つの変数の 8 つの組み合わせすべてについて評価すると、表と一致します。 ${\displaystyle m_{1},m_{2},m_{4},}$${\displaystyle m_{7}}$${\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}=(ci',x',y)+(ci',x,y' )+(ci,x',y')+(ci,x,y)}$

n個の変数のブール関数の場合、最大項はn 個の変数のそれぞれがちょうど 1 回出現する(補数形式または非補数形式のいずれか)和項です。したがって、最大項は、補数演算子と選言演算子 (論理 OR ) のみを使用するn 個の変数の論理式です。最大項は最小項の考え方の双対であり、ド・モルガンの法則の相補対称性に従います。AND と補数を使用する代わりに、OR と補数を使用して同様に処理します。最大項は、入力変数の 1 つの組み合わせに対してのみ偽の値を返すこと、つまり、可能性の最大数で真になることは明らかです。たとえば、最大項a ′ + b + c ′ は、 aとc が両方とも真でbが偽の場合にのみ偽になります。つまり、a = 1、b = 0、c = 1 の入力配置は 0 になります。 ${\displaystyle {x_{1},\dots ,x_{n}}}$

ここでも、n変数の 2 ^{n 個}の最大項があります。これは、最大項式の変数も直接形式または補形式のいずれかになる可能性があり、変数ごとに 2 つの選択肢があるためです。番号付けは、最小項の補形式がそれぞれの最大項になるように選択されます。つまり、各最大項には、最小項に使用される反対の従来の 2 進エンコードに基づいてインデックスが割り当てられます。最大項の規則では、直接形式に値 0 が割り当てられ、補形式に値 1 が割り当てられます。たとえば、最大項 (110) にインデックス 6 を割り当て、その最大項をM ₆と表記します。補形式は、ド・モルガンの法則を使用した最小項です。 ${\displaystyle (x_{i})}$${\displaystyle (x'_{i})}$${\displaystyle a'+b'+c}$${\displaystyle (a'+b'+c)'}$${\displaystyle abc'=m_{6}}$

論理関数の真理値表が与えられている場合、その関数を「和の積」または「最大項の積」として記述することができます。これは、連言正規形の特殊な形式です。たとえば、加算回路の 1 ビット位置のロジックのキャリーアウト ビットcoの真理値表が、加数とキャリーインciからのxとyの関数として与えられている場合、次のようになります。

出力が 0 になる行は 1 行目、2 行目、3 行目、5 行目であることに注目すると、co をmaxtermsとの積として記述できます。これを検証したい場合は、次のようにします。 ${\displaystyle M_{0},M_{1},M_{2}}$${\displaystyle M_{4}}$

${\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}=(ci+x+y)(ci+x+y')(ci+x'+ y)(ci'+x+y)}$

3 つの変数の 8 つの組み合わせすべてについて評価すると、表と一致します。

標準的な最小項形式は、より小さな SoP 形式と同等であることがよくあります。このより小さな形式は、依然として積項の合計で構成されますが、積項の数が少なくなったり、積項に含まれる変数の数が少なくなったりします。たとえば、次の 3 変数関数は次のようになります。

は標準的な最小項表現 を持ちますが、それと同等の SoP 形式 を持ちます。この些細な例では、 であることは明らかであり、より小さい形式では積項と各項内の変数の両方が少なくなります。この「最小」の概念に従った関数の最小SoP 表現は、最小 SoP 形式と呼ばれます。一般に、複数の最小 SoP 形式が存在する可能性があり、どれも他の形式よりも明らかに小さいか大きいわけではありません。^[2]同様に、標準的な最大項形式は、さまざまな最小 PoS 形式に縮小できます。 ${\displaystyle f=a'bc+abc}$${\displaystyle f=bc}$${\displaystyle bc=a'bc+abc}$

この例は通常の代数的手法 [ ] を適用して簡略化されていますが、それほど明白ではないケースでは、最大 4 つの変数を持つ関数の最小の PoS/SoP 形式を見つけるための便利な方法として、カルノー マップを使用する方法があります。クワインとマクラスキーのアルゴリズムは、少し大きな問題を解決できます。論理最適化の分野は、最小の PoS 形式や SoP 形式などのブール関数の最適な実装を見つける問題から発展しました。 ${\displaystyle f=(a'+a)bc}$

上記の最小項と最大項のサンプル真理値表は、2 進数の加算における 1 ビット位置の標準形式を確立するのに十分ですが、ゲートの在庫に AND と OR が含まれていない限り、デジタル ロジックを設計するには不十分です。パフォーマンスが問題となる場合 (アポロ ガイダンス コンピュータなど)、トランジスタ ロジックに固有の補完動作のため、使用可能な部品は NAND と NOR になる可能性が高くなります。値は電圧状態として定義され、1 つは接地近く、もう 1 つは DC 電源電圧 V _cc (例: +5 VDC) 近くです。高い方の電圧が 1 つの「真の」値として定義されている場合、NOR ゲートは最もシンプルで有用な論理要素です。

具体的には、3 入力 NOR ゲートは、エミッタがすべて接地され、コレクタが一緒に接続され、負荷インピーダンスを介して V _ccにリンクされた 3 つのバイポーラ接合トランジスタで構成されます。各ベースは入力信号に接続され、共通のコレクタ ポイントが出力信号を示します。ベースへの入力が 1 (高電圧) になると、トランジスタのエミッタがコレクタに短絡され、負荷インピーダンスに電流が流れ、コレクタ電圧 (出力) がグランドに非常に近くなります。この結果は、他の入力とは無関係です。3 つの入力信号がすべて 0 (低電圧) の場合にのみ、3 つのトランジスタすべてのエミッタ コレクタ インピーダンスが非常に高いままになります。そのときは電流はほとんど流れず、負荷インピーダンスによる分圧器効果により、コレクタ ポイントに V _ccに非常に近い高電圧がかかります。

これらのゲート回路の補完特性は、標準形式で関数を実装しようとするときには欠点のように思えるかもしれませんが、それを補う利点があります。つまり、入力が 1 つだけのゲートは、デジタル ロジックで頻繁に必要とされる補完機能を実装します。

この例では、Apollo の部品在庫として 3 入力 NOR ゲートのみを想定していますが、4 入力 NOR ゲートも使用可能であると仮定することで説明が簡略化されます (Apollo では、これらは 3 入力 NOR のペアから構成されていました)。

8 つの NOR ゲートのセットは、入力が 3 つの入力変数ci、x、 yの直接形式と補形式の組み合わせである場合、常に最小項を生成し、最大項は生成しません。つまり、3 つの入力変数のすべての組み合わせを処理するために必要な 8 つのゲートのうち、出力値 1 を持つのは 1 つだけです。これは、NOR ゲートはその名前にもかかわらず、入力信号の補数の AND として見た方が適切であるためです (ド・モルガンの法則を使用)。

これが問題にならない理由は、最小項と最大項の二重性、つまり各最大項が同様にインデックス付けされた最小項の補数であり、その逆もまた同様であるからです。

上記の最小項の例では、と書きましたが、これを4入力NORゲートで実行するには、合計が反対の最大項である合計の積（PoS）として書き直す必要があります。つまり、 ${\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}}$

${\displaystyle u(ci,x,y)=\mathrm {AND} (M_{0},M_{3},M_{5},M_{6})=\mathrm {NOR} (m_{0},m_{3},m_{5},m_{6}).}$

上記のmaxtermの例では、と書きましたが、これを4入力NORゲートで実行するには、同じmintermのNORとの等価性に注意する必要があります。つまり、 ${\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}}$

${\displaystyle co(ci,x,y)=\mathrm {AND} (M_{0},M_{1},M_{2},M_{4})=\mathrm {NOR} (m_{0},m_{1},m_{2},m_{4}).}$

加算器ステージの設計作業はこれで完了したと思われるかもしれませんが、3 つの入力変数すべてが直接形式と補数形式の両方で現れる必要があるという事実にはまだ対処していません。この点では、加数xとyについては問題はありません。なぜなら、これらは加算中は静的であり、したがって通常は直接出力と補数出力の両方を持つラッチ回路に保持されるからです。(NOR ゲートで作られた最も単純なラッチ回路は、フリップフロップを作るために交差結合された 2 つのゲートです。各ゲートの出力は、もう一方のゲートの入力の 1 つとして配線されます。) また、合計uの補数形式を作成する必要もありません。ただし、1 つのビット位置のキャリー出力は、直接形式と補数形式の両方で、次のビット位置へのキャリーとして渡す必要があります。これを行う最も簡単な方法は、co を1 入力 NOR ゲートに通し、出力にco ′ というラベルを付けることですが、最悪の場所でゲート遅延が追加され、右から左へのキャリーの波紋が遅くなります。co ′の標準形( coの反対の最小項から) を構築する追加の 4 入力 NOR ゲートにより、この問題は解決されます。

${\displaystyle co'(ci,x,y)=\mathrm {AND} (M_{3},M_{5},M_{6},M_{7})=\mathrm {NOR} (m_{3},m_{5},m_{6},m_{7}).}$

この方法でフルスピードを維持するためのトレードオフには、予期しないコスト（より大きなゲートを使用する必要があることに加えて）が含まれます。co を補完するために 1 入力ゲートを使用しただけであれば、 minterm は不要になり、それを生成するゲートは削除できます。それでも、これはまだ良いトレードオフです。 ${\displaystyle m_{7}}$

ここで、NOR ゲートを指定された関数に変換することで、これらの関数を SoP および PoS 標準形式に正確に従って実装できます。NOR ゲートは、出力を 1 入力 NOR ゲートに渡すことで OR ゲートになり、各入力を 1 入力 NOR ゲートに渡すことで AND ゲートになります。ただし、このアプローチでは、使用されるゲートの数が増えるだけでなく、信号を処理するゲート遅延の数も 2 倍になり、処理速度が半分に低下します。したがって、パフォーマンスが重要な場合は、標準形式を超えてブール代数を実行し、拡張されていない NOR ゲートで機能するようにすることは、十分に価値があります。

ここまで、minterm/maxterm ツールを使用して、ブール代数を追加した標準形式の加算器ステージを設計する方法を見てきました。出力ごとに 2 ゲートの遅延しかかかりません。これは、この機能のデジタル回路を設計する「トップダウン」方式ですが、最善の方法でしょうか。議論では、「最速」を「最良」と見なすことに焦点を当ててきましたが、拡張された標準形式は、その基準を完璧に満たしていますが、他の要因が優先される場合もあります。設計者の主な目標は、ゲートの数を最小限に抑えること、および/または、他のゲートへの信号のファンアウトを最小限に抑えることです。ファンアウトが大きいと、劣化した電源やその他の環境要因に対する耐性が低下するためです。このような場合、設計者は、標準形式の設計をベースラインとして開発し、次にボトムアップ開発を試みて、最終的に結果を比較します。

ボトムアップ開発では、 u = ci XOR ( x XOR y ) であることに注目します。ここで、XOR は排他的論理和 (どちらかの入力が真の場合は真だが、両方が真の場合は真ではない) を意味し、co = ci x + xy + y ciです。このような開発の 1 つでは、全部で 12 個の NOR ゲートが必要です。5ゲート遅延でu を生成するために 6 個の 2 入力ゲートと 2 個の 1入力ゲート、さらに2 ゲート遅延でco ′ を生成するために 3 個の 2 入力ゲートと 1 個の 3 入力ゲートが必要です。標準的なベースラインでは、2 ゲート遅延でu、co、co ′ を生成するために 8 個の 3 入力 NOR ゲートと 3 個の 4 入力 NOR ゲートが必要でした。回路インベントリに実際に 4 入力 NOR ゲートが含まれている場合、トップダウンの標準的な設計はゲート数と速度の両方で優れているように見えます。しかし、（私たちの都合の良い仮定に反して）回路が実際には 3 入力 NOR ゲートであり、各 4 入力 NOR 関数に 2 つ必要である場合、標準的な設計ではボトムアップ アプローチの 12 ゲートと比較して 14 ゲート必要になりますが、それでも合計桁u をかなり速く生成します。ファンアウトの比較は次のように表にまとめられます。

ボトムアップ展開の説明では、出力としてco ′ は言及されていますが、 co は言及されていません。この設計では、直接形式のキャリー出力は単に必要ではないのでしょうか。答えはイエスでもありノーでもあります。各ステージで、 co ′の計算はci ′、x ′、y ′のみに依存します。つまり、キャリーの伝播は、co を発生させることなく、標準的な設計と同じ速さでビット位置に沿って波及します。 uの計算では、1 入力 NOR によってci ′ からci を作成する必要がありますが、これは低速ですが、どのワード長でも、設計でそのペナルティが発生するのは 1 回だけです (左端の合計桁が展開されるとき)。これは、これらの計算が重複し、それぞれが独自の小さなパイプラインとなり、次のビット位置の合計ビットをいつ計算できるかには影響しないためです。また、確かに、左端のビット位置からのco ′ は、加算がオーバーフローしたかどうかを判断するロジックの一部として補完される必要があるでしょう。しかし、3 入力 NOR ゲートを使用すると、ボトムアップ設計は、重要なワード長での並列加算をほぼ同等の速度で実行でき、ゲート数を削減し、ファンアウトも少なくなります。したがって、ゲート数やファンアウトが最も重要である場合は、ボトムアップ設計が勝ります。

これらすべての記述が当てはまるボトムアップ設計の正確な回路については、もう 1 つの代数式を使用して、興味のある読者の演習として残しておきます: u = ci ( x XOR y ) + ci ′( x XOR y )′]′。このようにしてキャリーの伝播を合計形成から切り離すことで、キャリー ルックアヘッド加算器のパフォーマンスがリップル キャリー加算器よりも向上します。

ブール代数の応用例の 1 つはデジタル回路設計であり、ゲートの数を最小限に抑えることと、整定時間を最小限に抑えることを目標としています。

2 つの変数には 16 個の関数が考えられますが、デジタル ロジック ハードウェアでは、最も単純なゲート回路で実装されるのは、論理積(AND)、論理和(包含的 OR)、およびそれらの補数 (NAND と NOR) の 4 個だけです。

ほとんどのゲート回路は2つ以上の入力変数を受け入れます。たとえば、1960年代に集積回路の応用の先駆けとなった宇宙船搭載のアポロ誘導コンピュータは、3入力NORゲートという1種類のゲートのみで構築されました。このゲートの出力は、3つの入力がすべて偽の場合にのみ真になります。^{[3] [ページが必要] [4]}

• ブール代数のトピックのリスト

• ベンダー、エドワード A.; ウィリアムソン、S. ギル (2005)。離散数学短期コース。ミネオラ、ニューヨーク州: Dover Publications、Inc. ISBN 0-486-43946-1著者らは、任意のブール（論理）関数が、選言正規形または連言正規形のどちらかで表現できることを証明しています（5～6ページを参照）。証明は、N個のブール変数の2 N行すべてを作成し、各行（「^最小項」または「最大項」）が一意のブール式を持つことを実証するだけです。N変数の任意のブール関数は、最小項または最大項が論理1（「真」）である行の合成から導出できます。
  
• McCluskey, EJ (1965).スイッチング回路理論入門. NY: McGraw–Hill Book Company. p. 78. LCCN  65-17394.標準式が定義され、説明されている。
• Hill, Fredrick J.; Peterson, Gerald R. (1974)。スイッチング理論と論理設計入門（第 2 版）。NY: John Wiley & Sons。p. 101。ISBN 0-471-39882-9関数の最小項と最大項の指定

Wikibook Electronicsには、ブール代数に関するページがあります。

• ブール、ジョージ(1848)。「論理の微積分」。ケンブリッジおよびダブリン数学ジャーナル。III。ウィルキンス、デイビッド R. 訳: 183–198。