論理演算の基本的な事項は、「論理演算」(stat-ronri-enzan)を参照してください。
排他的論理和(XOR、EOR)、否定論理和(NOR)、否定論理積(NAND)、等価演算、論理回路、ビット操作、半加算器、全加算器、フリップフロップ回路
論理回路とは、論理演算を行う電子回路です。真理値の「真/偽」、2進法の「0/1」、電気の「ON/OFF」のように2つの状態をもちます。コンピュータは、多数の記憶素子と多数の論理回路を複雑に組み合わせたものだといえます。
論理回路は、次の2つに大別されます。
名称 | ベン図 | 真理値表 | 論理回路 | 名称 | ベン図 | 真理値表 | 論理回路 | |
---|---|---|---|---|---|---|---|---|
否定 NOT |
A X |
|||||||
論理和 OR + |
A B X |
否定論理和 NOR |
A B X |
|||||
論理積 AND × |
A B X |
否定論理積 NAND |
A B X |
|||||
排他的論理和 XOR EOR |
A B X |
等価演算 一致演算 IFF |
A B X |
AとB AND XOR OR NOR IFF NAND
共に0 0 0 0 1 1 1
一方1 0 1 1 0 0 1
共に1 1 0 1 0 1 0
二つの2進数(ここでは8ビットとします)に、各ビットで論理和や論理積をすることをビット演算といいます。任意の2進数Xに、00001111=0F16(Y)をビット演算します。このとき規則的なビット列Yをマスクといいます。
ここでは、X=01010101とします。
論理和(OR):1を与えたビットをすべて1にする
0101 0101
OR) 0000 1111
0101 1111
└──┘ └──┘
元のまま すべて1
論理積(AND):0を与えたビットをすべて1にする
0101 0101
AND) 0000 1111
0000 0101
└──┘ └──┘
すべて0 元のまま
排他的論理和(XOR):1を与えたビットを反転
0101 0101
XOR) 0000 1111
0101 1010
└──┘ └──┘
元のまま 反転
否定論理積(NAND):0を与えたビットをすべて1、1を与えたビットを反転
0101 0101
NAND)0000 1111
1111 1010
└──┘ └──┘
すべて1 反転
多数ビットの排他的論理和:
Pn=b1
b2
… bn
=1 (1のビットの個数が奇数のとき)
=0 (1のビットの個数が偶数のとき)
→パリティチェックに利用される
(証明)。
数学的帰納法で考える。
n=1のとき、
P1=b1 であるから、
1のビットの個数が奇数(1個)ならば1
1のビットの個数が偶数(0個)ならば0
で正しい。
n>1のとき、n-1まで正しいとすれば、
Pn=Pn-1bn であり、
Pn-1=1、bn=1 ならば Pn=0
b1~bn-1 までで1のビット数が奇数で bnが1ならば全体で偶数
以下、同様に検討すれば、正しいことがわかる。
1ビットの数AとBを加算して、その結果を1ビットの数Sに入れ、繰り上がり(キャリーという)を1ビットの数Cに入れる回路を半加算器といいます。
入力 出力
A B S C
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
となるので、SはXOR回路、CはAND回路で実現することができます。
下位の桁からの繰り上げを取り込んだ加算回路を全加算器といいます。全加算器は、半加算器を2つ用いて構成します。
入力 中 間 出力 単純計算
C A B S1 C1 S2 C2 S C C+A+B
0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1
0 1 1 0 1 0 0 0 1 10
1 0 0 0 0 1 0 1 0 1
1 0 1 1 0 0 1 0 1 10
1 1 0 1 0 0 1 0 1 10
1 1 1 0 1 1 0 1 1 11
過去の信号を記憶しておき、新規の信号が与えられると、その関係によって信号を出力する回路を順序回路といいます。その代表的なものが、フリップフロップ回路です(その語源?)。フリップフロップ回路は1ビットの信号を記憶でき、高速に入出力できるので、高速な記憶素子であるSRAMに用いられています。
フリップフロップとは、シーソーの「ギッタンバッタン」の擬音からだそうだ。上がりっぱなし、下がりっぱなし、上がったり下がったりすることからであろう。そのためか、ON(1)/OFF(0)の状態をHigh/Lowで示す人もいる。
フリップフロップ回路には多様な回路がありますが、単純な回路は「SR-フリップフロップ回路」で、OR回路とNOT回路を組み合わせたものです。
現在の状況をQ(その否定をQ)とします。そして、セット信号S、リセット信号Rを与えたとき、その結果として出力されるQおよびQは、次のようになります。
S=0、R=0:現在の状況がそのまま保持される(Q、Qは変化しない)
S=1、R=0:Q=1(Q=0)にセットされる
S=0、R=1:Q=0(Q=1)にリセットされる
S=1、R=1:セットとリセットを同時に行うことはないとする
Q=1のとき
Q=0のとき