論理回路 1 論理演算と完全系

2015 年 5 月 22 日
小野寺秀俊
論理回路
論理演算と完全系
1
1.1
2 変数論理演算
2 変数の論理演算は、変数の値の組合わせ—(0,0), (0,1), (1,0), (1,1) の 4 通り— のそれ
ぞれについて演算結果を 0 か 1 と定義できるため、(22 )2 = 16 種類存在する。その全てを
以下の表に示す。これらの演算の幾つかについては、実際に論理ゲートで実現し、論理回
路の設計や動作解析に用いられる。これらの演算名は英字で示した。
x
y
1.2
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1 記号
1
0
0
1 x·y
0 x−y
1
x
0 y−x
1
y
0 x⊕y
1 x+y
0 x↓y
1 x≡y
0
y
1 y→x
0
x
1 x→y
0 x|y
1
1
演算名
基本演算に
よる表現
恒偽
AND
抑止
x·y
抑止
x·y
EXOR
OR
NOR
XNOR (同値)
NOT
含意
NOT
含意
NAND
恒真
x·y+x·y
x+y
x·y+x·y
x+y
x+y
x·y
完全系
論理演算と論理値の集合 Ω に対して、Ω の演算・値と論理変数から任意の n 変数論理
関数を表現する論理式が構成できるとき、Ω は完全系であるという。
• {AND, OR, NOT} は完全系である。
積和標準形、和積標準形により任意の n 変数論理関数が表現可能である。
• {AND, NOT} は完全系である。
ド・モルガンの定理より、OR 演算は AND 演算と NOT 演算で実現できる。
x+y =x+y =x·y
• {OR, NOT} は完全系である。
ド・モルガンの定理より、AND 演算は OR 演算と NOT 演算で実現できる。
x·y =x·y =x+y
• {NAND} は完全系である。
以下のように NOT 演算、AND 演算、OR 演算が実現できる。
x=x·x
x·y =x·y =x·y·x·y
x+y =x+y =x·y =x·x·y·y
• {NOR} は完全系である。
以下のように NOT 演算、AND 演算、OR 演算が実現できる。
x=x+x
x·y =x·y =x+y =x+x+y+y
x+y =x+y =x+y+x+y
• {1, AND, EXOR} は完全系である。
以下のように NOT 演算と OR 演算が実現できる。
x=1⊕x
x + y = (x ⊕ y) ⊕ (x · y)
この演算系を用いた論理関数の表現法として、リード-マラー標準形 (Reed-Muller
canonical form) と呼ばれる標準形がある。
1.3
n 項演算への拡張
一つの変数に対する演算 (例えば NOT 演算) を単項演算、二つの変数に対する演算を 2
項演算という。論理回路の設計や動作解析において良く使われる OR 演算、AND 演算、
NOR 演算、NAND 演算、EXOR 演算について、n 項演算に拡張する。
• n 項 OR 演算:= x1 + x2 + · · · + xn
n 変数の値のうち、少なくとも一つが 1 であれば演算結果は 1 となる。
• n 項 AND 演算:= x1 · x2 · · · · · xn
n 変数の値が全て 1 であるときに限り演算結果は 1 となる。
• n 項 NOR 演算:= x1 + x2 + · · · + xn
n 変数の値が全て 0 であるときに限り演算結果は 1 となる。
• n 項 NAND 演算:= x1 · x2 · · · · · xn
n 変数の値のうち、少なくとも一つが 0 であれば演算結果は 1 となる。
• n 変数 EXOR 演算:= x1 ⊕ x2 ⊕ · · · ⊕ xn
奇数個の変数の値が 1 であるときに限り演算結果は 1 となる。
積和形
論理関数の表現
真理値表
解析木
一
x7塘十鞄
XlXvXg
優れた論理関数表現の条件
BDD
一
q■■■■■
XiXa+Xo
変数節点．．
︽叩︾︽叩︾今可■Ｕ一口■９−︹叩︾︽叩︾己■０舎己９０
関数間の論理演算、等価、恒偽、
包含判定の計算量が小さい
典
鼠菖
Ib
Id
l＞
点･uuldl1ll1lm何F
O『deredBDD
熟
ー
XjXp+Xg
蕊熱
一○一一１．−０’１︵Ｕ言１０三一画●●．
︽一叩︾八ｍ︾︽叩︶︽叩︾画■０−屯■■一己■０皇宅８９
表現が小さい
olll
XfXo+Xg
識
UnorderedBDDReducedOrderedBDD(ROBDD)
既約な順序付きBDD
冗長節点の削除
等価節点
●
今
〔）C
BODの既約化
一
−
x7埴十堵
−
XjX^+Xg
今
XfXj+Xo
篭蕊
の
0111
画
変数のI煩序を固定すれば、既約なBDDは輪理関数の標準形となる
多くの実用的に重要な議理関数が現実的な節点数で表現できる
C■一
へ①
論理関数に対する演算が表現のサイズに比例する時間で行える
表現のサイズは変数の順序に大きく依存する

Download Report