標準正規形

n個の変数には 2 ⁿ個の最小項があります。これは、最小項式の変数は直接形式または補数形式のいずれかになる可能性があるためです。つまり、変数ごとに 2 つの選択肢があります。最小項は、変数の補数パターンのバイナリ エンコーディングによって番号付けされることが多く、変数は通常、アルファベット順の標準的な順序で記述されます。この慣例では、直接形式 (${\displaystyle x_{i}}$）と0を補数形式（${\displaystyle x'_{i}}$）最小項は${\displaystyle \sum \limits _{i=1}^{n}2^{i-1}\operatorname {value} (x_{i})}$例えば、minterm${\displaystyle abc'}$番号は 110 ₂  =  6 ₁₀で、${\displaystyle m_{6}}$。

論理関数の真理値表が与えられた場合、その関数を「積和」または「最小項和」として記述することができます。これは、選言標準形の特殊な形式です。たとえば、加算器回路の1ビット位置の論理における算術和ビットuの真理値表が、加数と桁上げ入力ciからのxとyの関数として与えられた場合、次のようになります。

出力が 1 となる行が 2 番目、3 番目、5 番目、8 番目であることに注目すると、u を最小項の和として表すことができます。${\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)}$3つの変数の8つの組み合わせすべてについて評価すると、表と一致します。

最大項式では変数が直接形式または補数形式のいずれかになる可能性があるため、 n個の変数に対して 2 ^{n 個}の最大項が存在します。つまり、変数ごとに 2 つの選択肢があります。番号付けは、最小項の補数が対応する最大項になるように選択されています。つまり、各最大項には、最小項に使用される従来のバイナリ符号化とは逆のインデックスが割り当てられます。最大項の規則では、直接形式に値 0 が割り当てられます。${\displaystyle (x_{i})}$そして補形に1つ${\displaystyle (x'_{i})}$例えば、最大項にインデックス6を割り当てます。${\displaystyle a'+b'+c}$(110) 最大項をM ₆と表記する。補数は${\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つの組み合わせすべてについて評価すると、表と一致します。

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

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

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

${\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の例では、次のように書きました。${\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}}$しかし、これを4入力NORゲートで実行するには、同じ最小項のNORとの等価性に注意する必要があります。つまり、

${\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 ゲートで構成される最も単純なラッチ回路は、フリップフロップを構成するために相互に結合された一対のゲートです。それぞれの出力は、もう一方の入力の 1 つとして配線されます。）また、和uの補数形式を作成する必要もありません。ただし、あるビット位置からのキャリー出力は、直接形式と補数形式の両方で次のビット位置へのキャリーとして渡されなければなりません。これを行う最も簡単な方法は、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}).}$

このようにフルスピードを維持するためのトレードオフには、予期せぬコスト（より大きなゲートを使用する必要があることに加えて）が含まれます。もしその1入力ゲートをcoの補数にのみ使用していたならば、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 は排他的 OR [どちらかの入力が真の場合に真、両方が真の場合には偽] を意味し、co = ci x + xy + y ciです。このような開発では、合計 12 個の NOR ゲートが必要です。6 個の 2 入力ゲートと 2 個の 1 入力ゲートでu を5 ゲート遅延で生成し、3 個の 2 入力ゲートと 1 個の 3 入力ゲートでco ′ を2 ゲート遅延で生成します。標準的なベースラインでは、8 個の 3 入力 NOR ゲートと 3 個の 4 入力 NOR ゲートでu、co、co ′ を2 ゲート遅延で生成します。回路構成に実際に 4 入力 NOR ゲートが含まれている場合、トップダウンの標準的な設計は、ゲート数と速度の両方で優れているように見えます。しかし、（我々の都合の良い仮定に反して）回路が実際には3入力NORゲートであり、4入力NOR関数ごとに2つの3入力NORゲートが必要な場合、標準的な設計ではボトムアップ方式の12ゲートに対して14ゲートが必要になりますが、それでも合計桁uをかなり高速に生成します。ファンアウトの比較は、次の表にまとめられています。

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

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