← ブログに戻るブール代数

カルノー図におけるドントケア条件

K-mapのドントケアを安全に使いましょう。到達不能な入力と無関係な出力を区別し、ケアセットを最小化して、シミュレーション、HDL、違法状態の落とし穴を避けます。

DennyDenny
読了まで約13分
Chalkboard feature illustration for “カルノー図におけるドントケア条件”

要約： ドントケアとは、システム契約が出力値を制約しない場所で0か1を選んでよいという許可です。K-mapでは、Xセルは有用なグループを大きくできる場合にだけ含め、SOPでは必須の0を、POSでは必須の1を決して覆ってはいけません。この最適化が有効なのは、使用箇所でケアセットの仮定が真である場合だけです。HDLの X、シミュレーションにおける未知値、合成時のドントケアは自動的に同じものではありません。

通常、論理最小化は可能なすべての入力で関数を保存します。ドントケア条件はこの要件を緩めます。選択した入出力ケースには0または1のどちらを割り当ててもよく、実際に重要なケースに対する実装をより小さくできます。

この自由により、リテラルやゲートを取り除けます。一方で、仮定が誤っていれば、リセット復帰をなくし、無効な表示パターンを露出させ、シミュレーションとシリコンの不一致を生むこともあります。専門的な設計では、次の3つを一緒に記録します。

  1. 出力が1でなければならない必須の on-set。
  2. 出力が0でなければならない必須の off-set。
  3. どちらの結果でもシステム契約を満たす ドントケア集合。

出力が制約されない2つの理由

1. 入力に到達できない

環境が、関連する観測時点において特定の入力ベクトルがこの論理へ到達しないことを保証しています。

有効なBCD数字は0～9の集合に属するため、次の条件が満たされるなら10～15は到達不能にできます。

  • 発生源が常に有効なBCDを出力する。
  • リセットと電源投入時に別の値が露出しない。
  • 中間遷移が数字としてサンプリングされない。
  • コードを破損させる故障が、設計で必要とされる故障モデルの範囲外である。

2つの有効なレジスタ値の間で変化するとき、4ビットバスが一時的に 1100 になる可能性があるなら、「アルゴリズムは12を要求しない」だけでは不十分です。

2. 入力は起こり得るが、この出力は観測されない

パイプラインステージは、valid=0 の間、任意のデータを運ぶことがあります。すべての消費側が同じvalid状態でデータを修飾するなら、無効サイクル中のデータ出力は無関係です。

これは到達不能な入力ではなく、可観測性の条件です。どの消費側も名目上無関係なフィールドをログ、比較、転送、その他の形で使用しない場合に限り、安全です。

どちらのケースも、2値最小化問題ではXセルになります。しかし証明は異なるため、仕様には理由を残してください。

Xは1つの普遍的な意味ではない

記号Xには複数の意味があります。

  • K-mapでのXは「実装が0または1を選んでよい」という意味です。
  • 4状態HDLシミュレーションでの X は、しばしば「未知、競合、または未初期化」を意味します。
  • 真理値表の文書では、Xはその行に対して入力値が無関係であることを意味する場合があります。
  • 合成ディレクティブでは、ツール固有の構文が最適化を許可する場合があります。

これらの意味は交換可能ではありません。

RTLで 'x を代入すると、一部のフローでは最適化が改善される一方、シミュレーションで未知を伝播させたり、別のフローでは無視または変換されたり、真の初期化バグを見えにくくしたりします。不完全な組合せ代入は、ドントケアではなくラッチを推論する可能性があります。full_case のようなツールディレクティブも、合成後の動作をシミュレーションと異ならせる場合があり、Intelのドキュメントはこの可能性を明示的に警告しています。

対象の言語、シミュレーター、合成ツール、lint規則、形式検証フローがサポートする方法で意図を表してください。そして同じ環境仮定のもとで、合成された結果を検証してください。

K-mapの規則

最小化された積和形については、次のとおりです。

  1. 各セルを必須0、必須1、またはXとしてプロットする。
  2. 1とXだけを含む2のべき乗個の長方形を作る。
  3. すべての必須1を覆う。
  4. 必須0を決して含めない。
  5. カバーを改善しないXは使わないままにする。
  6. リテラル数、セル数、深さ、共有項、または別の実装指標といった、実際のコスト目標に従ってカバーを選ぶ。

積和形については、双対を適用します。

  • 必須0を任意のXとグループ化する。
  • すべての必須0を覆う。
  • 必須1を決して含めない。

各出力は同じXを異なる方法で使用できます。あるセグメント関数は、ある無効BCDセルを1に選び、別の関数は0に選ぶかもしれません。インターフェース仕様がそう要求しない限り、1つのグローバルな無効パターンを割り当てる必要はありません。

例：有効なBCD数字が5以上

AをBCDのMSB、DをLSBとします。必要な動作は次のとおりです。

  • 0～4の数字ではF=0。
  • 5～9の数字ではF=1。
  • 10～15のコードではX。
10進数 / コードABCDF
0～40000～01000
501011
601101
701111
810001
910011
10～151010～1111X

グレイコードの行・列順を使うと、次のようになります。

              CD
           00  01  11  10
AB = 00     0   0   0   0
AB = 01     0   1   1   1
AB = 11     X   X   X   X
AB = 10     1   1   X   X

Xセルにより、次の3つの有用なグループができます。

  • A=1の両行は8セルのグループを作り、Aを与える。
  • 0110、0111、1110、1111 はBCを与える。
  • 0101、0111、1101、1111 はBDを与える。

したがって、

F=A+BC+BDF=A+BC+BD

因数分解すると、

F=A+B(C+D)F=A+B(C+D)

ケアセットを確認しましょう。

  • 0～4の数字では0になる。
  • 5～7の数字では B(C+D)B(C+D) を満たす。
  • 8～9の数字ではAを満たす。

この式は、たまたま無効コード10～15すべてに対して1を出力します。これは、それらの行が明示的に制約されていないからこそ許容されます。

無効コードが0を出力しなければならない場合

もはやドントケアではありません。10～15でF=0とすると、有効なSOPの1つは次のとおりです。

F=A‾BC+A‾BD+AB‾C‾F= \overline A BC +\overline A BD +A\overline B\overline C

この版は、無効コードで必要な0を保持します。インターフェース契約がより強いので、より大きくなります。

ドントケアが役に立たない場合

有効なBCD数字について、「偶数か」は次のとおりです。

F=D‾F=\overline D

LSBがすでにパリティを符号化しています。10～15のコードをXにしても、必要な値を変えずに唯一のリテラルを取り除くことはできないため、最小値は同じです。

ドントケアは最適化空間を広げますが、改善を保証するものではありません。

1つのリテラルが消える場合

有効なBCD数字の8と9でF=1、0～7でF=0と定義します。

無効コード10～15も0を出力しなければならない場合は、

F=AB‾C‾F=A\overline B\overline C

1000 と 1001 だけがこの式を満たします。

10～15がドントケアなら、必須の1を6つのXセルすべてとグループ化できます。

F=AF=A

どちらの実装も有効なBCDでは一致します。無効な入力の一部では、意図的に異なります。

この正しい比較は重要です。無効セルをグループ拡張に使いながら、設計が「ドントケアなし」と主張することはできません。

過渡入力とサンプリング境界

発生元と宛先のレジスタが有効なコードを含んでいても、組合せビットは同時に切り替わりません。BCD 7（0111）から8（1000）への遷移では4ビットが変わり、ほかの電気的組合せを通る可能性があります。

それが重要かどうかは、境界に依存します。

  • デコーダが安定した後にだけサンプリングする宛先レジスタは、中間結果を決して捕捉しないかもしれません。
  • 最小化された論理から導かれる非同期出力イネーブル、書き込みストローブ、またはクロックは、過渡状態に反応する可能性があります。
  • 多重化表示は短いゴーストパターンを示すかもしれません。
  • ロジックアナライザは、ソフトウェアが決して観測しない値を示すかもしれません。

したがって、到達不能集合の証明では、ソフトウェアがどの定常値を意図するかだけでなく、出力がいつ重要になるかを述べなければなりません。

入力または出力をレジスタ化する、タイミングを制約する、ハザードのない制御を設計する、ブランキングを追加するといった方法で、仮定を真にできます。K-mapでXを宣言しても、そうなるわけではありません。

状態機械の無効状態

5つの状態を3ビットで符号化するとします。通常動作中には3つのコードが未使用です。リセットが保証され、状態破損が対象外なら、それらのコードをドントケアとして次状態論理と出力論理を最適化することは合理的かもしれません。

単一イベントアップセット、CDCエラー、部分リセット、故障注入が対象なら、これらのコードは無関係ではありません。設計では次が必要になるかもしれません。

  • 違法状態を検出する。
  • 危険な出力を直ちに抑止する。
  • リセットまたは別の安全な状態へ戻す。
  • 故障を報告する。
  • 必要なハミング距離を持つ符号化を使う。

FPGAツールは明示的なセーフステート機構を提供しています。たとえばAMD Vivadoの FSM_SAFE_STATE は、面積と性能のトレードオフとともに、無効状態の検出および復帰論理を追加します。Intel Quartusの文書も同様に、通常の合成とセーフステートマシンのオプションを区別しています。

違法状態を最適化で消し去りながら、そこからの復帰を保証すると主張してはいけません。これは別の仕様です。

ワンホット入力と優先入力

厳密に1本だけがHighとなるnビットのインターフェースには、n個の有効ベクトルと、ほかに 2n−n2^n-n 個のベクトルがあります。プロトコルがone-hot-or-zeroであれば、ゼロベクトルも有効です。

プレーンエンコーダは、上流論理が厳密なワンホット入力を保証するなら、複数ビットがアサートされた場合をドントケアとして扱えます。優先エンコーダは、多重アサート行を意図的に定義するため、制約なしとしては扱えません。ただし、要求がアクティブでないときは、valid出力がコードを修飾することを条件に、コードを無関係と定義できます。

この違いは、「エンコーダ」のような名前から入力仮定を推測せず、モジュール境界で記録するべき理由の1つです。

出力に無関係なデータ

次を考えてください。

valid = 0
data  = anything

すべての観測可能な影響がゲートされる場合に限り、データ依存の下流論理を最適化しても安全です。

write_enable = valid AND condition(data)

しかしここでも、condition(data) の物理的なスイッチングは電力を消費し、サイドチャネル漏洩を生み、タイミングへ影響する可能性があります。「機能的に観測されない」ことは、必ずしも「電気的に無関係」ではありません。

シミュレーションを明快にするため、多くのチームは無効データへ決定論的な値を割り当てつつ、明示的な制約または周囲のイネーブルを通して合成に最適化を任せます。最適な選択は検証フローと実装フローに依存します。

HDLの指針

K-map表記を、そのまま気軽なHDLのX代入へ翻訳することは避けてください。

保守的な組合せパターンでは、すべての出力を定義します。

always_comb begin
  valid = (bcd <= 4'd9);
  ge_five = 1'b0;
  if (valid)
    ge_five = (bcd >= 4'd5);
end

これは無効時の動作を0として指定します。プロジェクトが無効入力を合成上のドントケアにしたいなら、レビュー済みでツールがサポートする機構と、それに付随する仮定で意図を表現してください。例として、形式検証における入力制約、合成属性、制約付きモジュールインターフェース、技術固有のプリミティブなどがあります。

どの方法を選ぶ場合も、次を行います。

  • 不完全な代入と意図しないラッチをlintする。
  • フローで必要なら、RTLとゲートレベルの動作を比較する。
  • ケアセット上の等価性を証明する。
  • 環境仮定が成り立つことを検証する。
  • 到達不能状態とcase網羅性に関する警告を確認する。
  • その動作を特に意図していない限り、未知の制御ビットを隠しうる casex やワイルドカード一致を避ける。

検証計画

ドントケア最適化には、相補的な2つの確認が必要です。

ケアセット上の機能等価性

必要なすべての入力について、

Fimplementation=FspecificationF_{\text{implementation}}=F_{\text{specification}}

4変数なら、完全な真理値表を列挙します。より大きな論理では、明示的なケアセット制約を伴うアサーションまたは形式的等価性を使います。

仮定の検証

次を証明またはテストします。

  • 出力が重要なときに無効符号化をサンプリングできない。
  • リセットと電源投入が仮定を尊重する。
  • CDC経路が未対応の組合せを作れない。
  • 故障要件に「到達不能」集合が含まれない。
  • 下流のvalidゲーティングがすべての副作用を覆う。
  • テストおよびデバッグモードが修飾子をバイパスしない。

最小化されたブール式だけをテストしても、Xを正当化するのが環境であるなら、契約の誤った半分を検証していることになります。

DigiSimでBCDの例を作る

2つの digit ≥ 5 検出器を構成します。

  1. 無効時も定義する版： 次を実装します。 F=A‾BC+A‾BD+AB‾C‾F=\overline A BC+\overline A BD+A\overline B\overline C。
  2. ドントケア最適化版： F=A+BC+BDF=A+BC+BD を実装します。
  3. 16通りの入力をすべて走査します。
  4. どちらも0～9で一致することを確認します。
  5. 10～15で意図的に異なる点を記録します。
  6. BCD 0～9用に valid = NOT(A AND (B OR C)) を加え、観測可能な出力をゲートします。
  7. 複数の入力ビットを同時に変え、シミュレーターが中間遷移をモデル化するか調べます。理想的な同時更新を使うなら、アナログのハザード動作を推論してはいけません。

この演習は正しい取引を示します。より小さい論理と引き換えに、より狭い動作上の約束を受け入れることです。

レビューチェックリスト

セルをXと記す前に、次を問いかけてください。

  • なぜこの出力は制約されないのか。到達不能な入力か、観測されない出力か。
  • その主張は、どのサンプリングまたは観測境界で真なのか。
  • リセット、CDC、テストモード、故障動作がそれを破らないか。
  • XはK-mapでの許可か、HDLの未知値か、ツールディレクティブか。
  • 違法状態は復帰しなければならないか。
  • 最適化実装はケアセットのすべての入力で検証されているか。
  • 仮定そのものがアサートまたは証明されているか。

ドントケアは「ただで減らせるゲート」ではありません。定義されたケアセットの外側の動作を、実装の自由度と交換するものです。ケアセットが明示され検証されているなら、これは規律ある最適化です。単に仮定されているなら、隠れた機能です。

符号化契約についてはBCDの基礎、7出力の応用についてはBCDから7セグメントへのデコード、遷移時の動作については静的・動的ハザードを続けて読んでください。

参考文献

関連記事

アイデアを実際に動く回路にしましょう。

ワークベンチを開く