VLSI設計支援工学３ • 論理合成 – これから２週間で積和形論理式簡単化を説明 – 商用ツールとしてほとんどのVLSIで広く利用されている – 離散値を扱う一般的関数に適用可能 – 実用的なアルゴリズムが開発されており、CAD以外の問題へも応用可能 • 例：積和形論理式簡単か → パターン認識 – 今日は、各種の定義と準備論理空間（Boolean space）のcubeによる表現 • • • • • B 0 n 次元cubeで論理関数を表現できる基本的にカルノーマップと同じ B = {0,1} B2 = {0,1}×{0,1} = {00, 01, 10, 11} B3 = {0,1} ×{0,1} ×{0,1} = {000, 001, 010, 011, 100, 101, 110, 111} B 1 B 2 B 3 B 4 論理関数（Boolean function） f(x) : Bn → Bm 0 1 B = {0,1}, x = (x1, x2, …, xn) 1 1 • 各頂点に値（０か１）が割り当てられる • Onset: {x| f(x) = 1} = f1 = f-1(1) 0 0 -1 • Offset: {x| f(x) = 0} = f = f (0) • f1 = Bnのとき tautology（恒真）という f≡1 • F0 = Bnのとき充足不可能という • 全ての x∈Bnに対しf(x) = g(x)にとき、f と g は等価であるという • x1, x2, …は変数 • x1, x’１, x２, x’2, …はリテラルと呼ばれる（x’はxの否定） 1 0 リテラルは論理関数 • リテラルとは、１つの変数か、その否定： x, x’であり、論理関数を表す 0 0 0 0 1 1 1 1 x1 f = x1 1 1 1 1 0 0 0 0 x1 _ f = x1 論理関数の表現 • 論理関数は以下の規則にしたがって表現できる（あるいは、記述できる） • 括弧：（、） • リテラル： x, y, z, x’, y’, z’, … • 論理演算：＋(OR)、・(AND 省略することもある） • 否定： (x + y)’ • 例 f = x1 x2’ + x1’ x2 = (x1 + x2) (x1’ + x2’) H = a + bc = (a’(b’ + c’))’ 論理関数 f(x): Bn → B（1出力論理回路） • Bn空間には、2n個の頂点がある x 1x2 x3 011 n 2 • 2 個の異なる論理関数がある x 000 3 111 x2 x1 000 001 010 011 100 101 110 111 x 1x2 x3 111 • ∞個の論理式が書ける f=x+y = xy’ + xy + x’y = xx’ + xy’ + y = (x + y)(x + y’) + x’y x3 000 x1 x2 000 1 001 0 010 1 011 =>0 100 0 101 1 110 0 111 1 "truth table" • 論理合成とは、「最も良い」論理式（論理関数の表現）を求めること Cube（積項） • いくつかのリテラルをANDしたものがcube（積項） – C = xy’ = (x=1)(y=0)はcube（積項） z => x=1 y=0 y _ xy x • fに含まれるcubeのことをimplicant（主項）という • Cube Cがk個のリテラルをもっていると、Cの中には 2n-k個の頂点がある例： C = xy’ ⊆B3, k = 2, n = 3 C = {100, 101}であり、23-2=2個の頂点をもつ • k = nのときのcubeを最小項（min-term）という積和形論理式（sum-of-products, SOP） • 任意の論理関数は、cubeの和として表現できる – f = ab + ac + bc • Cubeは積項なので、これは積和形論理式（SOP) • SOPはcubeの集合と考えられる – f = {ab, ac, bc} • 論理関数fを表すcubeの集合のことをfのカバーという – {ab, ac, bc}はf = ab + ac + bcのカバー bc ac ab c a b = onsetの頂点 Onsetの各頂点は、少なくとも１つのcubeでカバーされなければならない • カバーで多くの論理関数を効率よく表現できる – 多くの論理関数に対し、小さいカバーがある • 積和形論理式最適化あるいは、２段論理最適化とは、最小のカバー（cube数最小）を求めること非冗長性 • F = {c1, c2, …, ck}がf のカバーとする – f = Σki=1ci • cube ci∈Fが非冗長とは、F – {ci} ≠fのこと F - {ab} = /f F = ab+ac+bc bc ac bc ab ac c b a カバーされない最大項（prime） • Implicant（主項）ciが最大項（prime）であるとは、 ciからどれか１つのリテラルをとったcube cciについて、f + cci ≠f となってしまうこと • 例： F = ab + ac + bc ci = ab cci = a （リテラルbをとったもの） F + {cci} – {ci} = a + ac + bc bc ac a c b a offsetの一部もカバーしているのでf と等価ではない最大非冗長カバー • あるカバーが最大非冗長であるとは、そのカバーが最大項かつ非冗長cubeのみでできているとき • F の主項が必須項（essential prime）であるとは、その主項にしかカバーされない最小項がonsetにあるとき abc • 例： f = abc + b’d + c’d – abcが必須であるのはなぜか？ – 他に必須項はあるか？ – 必須項でないものはどれか？ c _ bd b a d _ cd 積和形論理式のハードウェアでの実現： PLA（Programmable Logic Array） • 多出力関数を表現 • PLAとは、f: Bn → BmをSOPとして実現するもの • 各cubeはPLAのANDプレーンに１度だけ現れ、 ORプレーンで複数の出力で共有される f1 = ab’cd + abc’d’ f2 = ab’c’d + ab’cd’ f3 = ab’cd’ + ab’d’ a b’ c d a b c’ a b’ c’ d’ d a b’ c d’ a b’ d’ f1 f 2 f3