Microsoft Word - 0-オリエンテーション.doc

Transcription

1 論理回路 (1 年前期金 3 限履修コード T513) 論理回路はコンピュータの算数 ( 数学ではない ) 身につけないと デジタルシステムを何ら理解することはできない 0. オリエンテーション授業中 質問はいつでも 大きな声ですること 0.1. 自己紹介川口博 (S 神戸市垂水区産 明石市育ち ) 明石高専電気工学科 修士 ( 千葉大学電子工学専攻 ) コナミ アーケードゲーム H/W 研究開発 - スラムダンク - ヘンリーエクスプローラーズ - スピードキング - 他にいくつか 東京大学生産技術研究所 ( 六本木! 駒場 ) - 現在 国立新美術館 博士 ( 東京大学 ) 2005 から神戸大学情報知能工学科 現在准教授 専門は半導体集積回路 (LSI) 0.2. コンタクト mail kawapy@godzilla.kobe-u.ac.jp URL 上記 URL に授業に必要な情報を載せることあり 0.3. 授業の進め方 教科書 参考書 板書中心 教科書はなし 参考書 : コロナ社 論理回路の設計 浅川毅著 ISN: 評価方法 **(** は最重要な項目を表す * は重要な項目 ) 小テスト 2 割 期末試験 8 割 出席点なし 期末試験の再試験は行わない 0.5. 授業内容 1 2 進数 2 論理関数の基礎 3 論理関数の簡単化 4 組み合わせ論理回路 5 ラッチとフリップフロップ 6 順序回路 0-1

2 メモ 0-2

3 1. 2 進数 1.1. q 進数 進数 (decimal number) おなじみ 例えば 55 [1001] 10 添え字の 10 は 10 進数を表す 10 種類の記号 (0, 1, 2,, 9) で表現される数 進数 進数 (binary number)** 最もシンプルな表現 2 種類の記号 (0, 1) で表現される [110] 2 = =[6] 進数の小数部小数部も整数部と同様に扱う [ ] = = =[6.625] q 進数 ( 一般化 ) 例題 : 以下の 2 進数を 10 進数で表現しなさい [ ] 2 = [ ] 2 =[E1] 16 =E1h=0xE1(2 桁の 16 進数 ) 16 進数は E1h とか 0xE1 と書くことが多い 言語 ( プログラム言語の一種 ) でも 16 進数は 0x???? と書く 進数から q 進数への変換 進数の整数 N から q 進数への変換 N=[a k-1 a k-2 a 1 a 0 ] q とする N/q=S 0 あまり a 0 S 0 /q=s 1 あまり a 1 S k-2 /q=0 あまり a k-1 商 S i が 0 になりまで繰り返す 進数の小数部 n から q 進数への変換 n=[. a -1 a -2 a -m+1 a -m ] q とする q n=a -1 ( 整数部 )+d -1 ( 小数部 ) q d -1 =a -2 ( 整数部 )+d -2 ( 小数部 ) q d -m+1 =a -m ( 整数部 )+d -m ( 小数部 ) 小数部 d i が 0 にならない場合がある ( 循環小数 ) 裏面に例題あり 1.3. ビットとバイト ビット (bit)** 2 進数の 1 桁のことをビットという [1011] 2 は 4 ビット 4bit または 4b(b は小文字 ) とも書く b は 2 進数の意味で使われることもある [1011] 2 =1011b b が桁または 2 進数の意味かどうかは 文脈で判断するしかないので注意 2 進数の最上位ビットを MS (most significant bit) 最下位ビットを LS (least significant bit) という 進数 (hexadecimal number hex number)* 16 種類の記号 (0, 1, 2,, 9,,,, D, E, F) を使う [0] 16 =[0000] 2 =[0] 10 [1] 16 =[0001] 2 =[1] 10 [2] 16 =[0010] 2 =[2] 10 [3] 16 =[0011] 2 =[3] 10 [4] 16 =[0100] 2 =[4] 10 [5] 16 =[0101] 2 =[5] 10 [6] 16 =[0110] 2 =[6] 10 [7] 16 =[0111] 2 =[7] 10 [8] 16 =[1000] 2 =[8] 10 [9] 16 =[1001] 2 =[9] 10 [] 16 =[1010] 2 =[10] 10 [] 16 =[1011] 2 =[11] 10 [] 16 =[1100] 2 =[12] 10 [D] 16 =[1101] 2 =[13] 10 [E] 16 =[1110] 2 =[14] 10 [F] 16 =[1111] 2 =[15] 10 16=2 4 なので 16 進数 1 桁が 2 進数 4 桁に対応する バイト (byte)** 8 ビットを 1 バイトという [ ] 2 は 1 バイト 1yte または 1( は大文字 ) とも書く 1 バイトで 0 から 255 までの 10 進数を表現可能 0xF0 は 2 バイト (2yte, 2) は 16 進数と間違いやすいので 文脈に注意 例題 :0x は何ビット? 例題 :[65] 10 は何バイト? 工学単位系とビットの関係 * 工学単位系 : k=10 3 =1000 M=10 6 = G=10 9 = 計算機の単位系 : k=2 10 =1024 M=2 20 = G=2 30 = 文脈で使い分けること この授業では特に断らない限り計算機の単位系 ( ビットの世界 ) を使う

4 例題 : を 2 進数で表現しなさい 例題 :0.1 を 2 進数で表現しなさい ( 循環小数 ) 1-2

5 1.4. 負数の表現今までの数は全て正数 ( 符号なし :unsigned) であった この節では負数を含む体系 ( 符号つき :signed) について述べる 符号と絶対値最上位桁に符号を割り当てる 10 進数の場合は + または - [+3.625] [-3.625] 進数の場合は MS を符号とする [ ] 2 [ ] [ ] 2 [ ] 補数 q 進数 k 桁の整数 N を N=[a k-1 a k-2 a 1 a 0 ] q とする -N はいずれかの補数で定義される N の q の補数 M q M q =q k -N N の (q-1) の補数 M q-1 M q-1 =(q k -1)-N 結局 M q-1 は q 進数 k 桁の最大の整数 q k -1 から N を引いたものとなり M q は M q-1 に 1 を加えたものとなる 例題 :N=[3] 10 例題 :N=[01] 2 -N=(N の 2 の補数 M 2 )= N=[01011] 2 -N=(N の 2 の補数 M 2 )= 2 の補数は 1 の補数に 1 を足したものである すなわち 2 の補数は 各ビットを反転させたものに 1 を加えれば得られる 進数小数の 2 の補数 * 同様に 足して MS+1 桁目に桁上がりを生じさせる数が 2 進数小数の 2 の補数である すなわち全ビットを反転させて LS に 1 を加えればよい 例題 :[ ] 2 の 2 の補数 = [0111.1] 2 の 2 の補数 = 進数の補数のまとめ 裏面に重要な例題 ** あり -N=(N の 9 の補数 M 9 )= -N=(N の 10 の補数 M 10 )= N=[256] 10 -N=(N の 9 の補数 M 9 )= -N=(N の 10 の補数 M 10 )= 進数の 1 の補数 * 例題 :N=[01] 2 -N=(N の 1 の補数 M 1 )= N=[01011] 2 -N=(N の 1 の補数 M 1 )= やはり 2 進数 k 桁最大の数 2 k -1 から N を引いたものが 2 進数の 1 の補数である 2 進数の 1 補数の場合は各ビットを反転 ( ) させればよい 進数の 2 の補数 ** 2 進数 k 桁の整数 N とする 2 k から N を引いたものが 2 進数の 2 の補数 M 2 である 定義上 N+M 2 =2 k となり MS+1 桁目に桁上がり (carry) が生じる 1-3

6 例題 :8 ビットの 2 進数を考える 以下の表を埋めなさい 符号なし 10 進数 (unsigned) 符号なし 2 進数 ** (unsigned) 符号つき 10 進数 (signed) 2 進数 1 の補数 (signed) 2 進数 2 の補数 ** (signed) なし ビットの 2 進数は 符号なし** 0~255 を表現できる 1 の補数 -127~127 を表現できる 零が-0 と 0 の 2 種類 存在する 結果的に MS は符号を表している 1 の場合 負数 0 の場合 正数または零 2 の補数 ** -128~127 を表現できる 零は 0 の 1 種類のみ 結果的に MS は符号を表している 1 の場合 負数 0 の場合 正数または零 例題 :8 ビットの 2 進数の補数を考える 以下の表を埋めなさい 2 進数 1 の補数 (signed) 符号つき 10 進数 (signed) 2 進数 2 の補数 ** (signed) 符号つき 10 進数 (signed) 進数の補数を符号つき 10 進数で表現するには 1 の補数 :-N=(N の 1 の補数 ) N=(N の 1 の補数 ) の 1 の補数 2 の補数 **:-N=(N の 2 の補数 ) N=(N の 2 の補数 ) の 2 の補数. 1-4

7 1.5. 減算 q 進数の減算に q の補数を使うと 減算も加算操作で行うことができる q 進数 k 桁の整数の減算 - =+( の q の補数 ) =+(q k -) =-+q k ここで q k は桁上がりである これを無視すれば と の減算は と ( の q の補数 ) の加算と等価である 進数の減算 例題 : =432+( )= = しかし 10 の補数の生成に 結局 減数が必要となる つまり 10 進数の減数においては 10 の補数を用いても 減算操作が必要である 進数の減算 ** 例題 :[ ] 2 -[ ] 2 =[ ] 2 +[ ] 2 +1 = 2 進数の減算を 2 の補数を用いて行うと 反転操作と加算操作だけでよい つまり減算操作は必要ない メリット : 1.6. オーバーフローとアンダーフロー * オーバーフロー (overflow) 加算等で発生 演算結果が表現できる最大値を上回ってしまうこと 意図せぬ桁上がりが生じ 誤った演算結果になる 符号なし 8 ビット 2 進数の場合の例題 : 254+3=[ ] 2 +[ ] 2 = 8 ビット 2 進数の 2 の補数の場合の例題 : 126+3=[ ] 2 +[ ] 2 = アンダーフロー (underflow) 減算等で発生 演算結果が表現できる最小値を下回ってしまうこと 意図した桁上がりが生じず 誤った演算結果になる 符号なし 8 ビット 2 進数の場合の例題 : 2-4=[ ] 2 +[ ] 2 = 8 ビット 2 進数の 2 の補数の場合の例題 : =[ ] 2 +[ ] 2 = 小数乗除演算の場合に 演算結果が限りなく零に近づき 有効桁が小数分解能未満 (LS 未満 ) になってしまうことも アンダーフローという 1.7. シフト (shift)* 左シフト (left shift) 左にあふれたビットは消え 右に空いたビットには 0 を埋める m ビット左シフトすると数値が 2 m 倍になる 簡単なシフト操作だけで 2 m 倍の乗算が可能 符号なし 8 ビット 2 進数の場合の例題 : 24([ ] 2 ) の 3 ビット左シフト =[ ] 2 <<3= 252([ ] 2 ) の 2 ビット左シフト =[ ] 2 <<2= 8 ビット 2 進数の 2 の補数の場合の例題 : 77([ ] 2 ) の 1 ビット左シフト =[ ] 2 <<1= -22([ ] 2 ) の 2 ビット左シフト =[ ] 2 <<2= 右シフト (right shift) 右にあふれたビットは消え 左に空いたビットには符号を埋める m ビット右シフトすると数値が 2 -m 倍になる 簡単なシフト操作だけで 2 -m 倍の乗算 ( すなわち 2 m で割る除算 ) が可能 符号なし 8 ビット 2 進数の場合の例題 : 24([ ] 2 ) の 5 ビット右シフト =[ ] 2 >>5= 252([ ] 2 ) の 3 ビット右シフト =[ ] 2 >>3= 8 ビット 2 進数の 2 の補数の場合の例題 : 77([ ] 2 ) の 1 ビット右シフト =[ ] 2 >>1= -22([ ] 2 ) の 4 ビット右シフト =[ ] 2 >>4= 1.8. ローテート (rotate) 環状シフト ( あふれたビットを空いたビットに埋め戻すシフト ) をローテートと呼ぶ 1-5

8 メモ 1-6

9 2. 論理関数の基礎 19 世紀 英国の数学者 ジョージ ブールが提唱した論理数学はブール代数と呼ばれている 後に米国のシャノンが論理設計の基礎理論として発展させた 原則として 変数および関数は 0 と 1 の 2 値しか持たない 2.1. 真理値表入力変数とその論理関数出力の関係を表にしたものを真理値表という m 変数関数の入力の組み合わせ数は 2 m である 例 : ある 3 変数関数 F=F(,, ) の真理値表 入力の組み合わせ数は 2 3 =8 入力 出力 変数 変数 変数 関数 F m 変数関数 m 変数関数の入力の組み合わせ数は : m 変数関数の出力の組み合わせ数 ( 出力パターン数 ) は : 2 変数関数の網羅的真理値表は以下のとおり F 0 F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8 F 9 F F F F D F E F F 基本論理ゲート ** NOT ND OR EXOR NND NOR EXNOR は基本論理ゲートと呼ばれており 記号 ( シンボル ) が MIL 記号として定められている 論理積 ND 論理式 真理値表 記号 : 否定 NOT (INV) 論理式 真理値表 記号 : 2-1

10 論理和 OR 論理式 真理値表 記号 : NOR(OR の NOT) 論理式 真理値表 記号 : 排他的論理和 EXOR (XOR) 論理式 真理値表 記号 : EXNOR(EXOR の NOT) 論理式 真理値表 記号 : NND(ND の NOT) 論理式 真理値表 記号 : 2-2

11 2.4. 論理演算の適用順序優先順位 : 1 否定 >2 論理積 >3 論理和 >4 排他的論理和 集合関係 * 例 : 積集合 例 :+ D= 2.5. ベン図集合関係と集合範囲を視覚的に図式化したもの つまり 真理値表を図式化したもの 一般に演算値が 1 のところを塗りつぶす ベン図では 4 要素以上を含む集合を円では表現できない 全集合 ( 普遍集合 ) 例 : 長方形の内部は全集合 L 例 : 和集合 + 例 : 積集合 要素 ( 元 ) 例 :L に属する要素 例 : 和集合 ++ 例 :Ā( の補集合 ) EXOR 例 : 空集合例 : 何も含まない集合 φ NND 例 : NOR 例 : + 例 : Ā(=φ) EXNOR 例 : 2-3

12 2.6. ブール代数の公理,, L 公理 1: +0= ( 単位元 ) 1= 公理 2: +Ā=1 ( 補元 ) Ā=0 公理 3: +=+ ( 交換則 ) = 公理 4: + =(+) (+) ( 分配則 ) (+)= ブール代数の双対性 ** ここで公理をよく見る に置き換えても同じく公理となり これを双対性という つまり m 変数論理関数 f(x 1, X 2,, X m, 0, 1,, +) =g(x 1, X 2,, X m, 0, 1,, +) その双対でも f(x 1, X 2,, X m, 1, 0, +, ) =g(x 1, X 2,, X m, 1, 0, +, ) 例題 : ド モルガンの定理を真理値表で確認せよ 例題 : ド モルガンの定理をベン図で確認せよ 2.8. ブール代数の代表的な定理 ^( あまり重要でない ) 定理 1: += ( べき等則 ) = 定理 2: +1=1 ( 零元 ) 0=0 定理 3: = ( 復元則 二重否定 ) 定理 4: +(+)=(+)+ ( 結合則 ) ( )=( ) 定理 5: + = ( 吸収則 ) (+)= 定理 6: +Ā =+ (Ā+)= 定理 7: + + Ā= + Ā (+) (+) (+Ā)=(+) (+Ā) 定理 8: (+) (Ā+)= +Ā +Ā =(+) (Ā+) 定理 9: (+) (+D)= + D+ + D + D=(+) (+D) (+) (+D) ( 分配則の分配則 ) 2.9. ド モルガンの定理 ** 以下の定理 10 を特に ド モルガンの定理という 定理 10**: +=Ā =Ā+ 論理積を論理和で ( 論理和を論理積で ) 表現できることを示している重要な定理 ド モルガンの定理は以下の定理 11 を用いると解析的に証明できる ( 板書参照 ) 定理 11^: +Ā=1, Ā=0 = 2-4 ド モルガンの定理の応用 定理 12^: + =Ā + ( + ) ( + ) =(Ā+) ( + ) m 変数論理関数におけるド モルガンの定理 * 一般化 f(x 1, X 2,, X m,, +) =f( X 1, X 2,, X m, +, ) 排他的論理和における代表的な定理 ^ 定理 EX1: 0 = 1 = 定理 EX2: =0 Ā=1 定理 EX3: = 定理 EX4: ( )=( ) ( ) ただし +( ) (+) (+) 定理 EX5: ( )=( )

13 2.12. シャノンの展開定理 * 任意の m 変数論理関数 f(x 1, X 2,, X m ) を X 1 について展開する f(x 1, X 2,, X m ) =( X 1 +X 1 ) f(x 1, X 2,, X m ) = X 1 f(x 1, X 2,, X m )+X 1 f(x 1, X 2,, X m ) = X 1 f(0, X 2,, X m )+X 1 f(1, X 2,, X m ) これをシャノンの展開定理という ( 証明 ) X 1 =0 の時左辺 =f(0, X 2,, X m ) 右辺 =1 f(0,x 2,., X m )+0 f(1, X 2,, X m ) =f(0, X 2,, X m ) 左辺 = 右辺 X 1 =1 の時左辺 =f(1, X 2,, X m ) 右辺 =0 f(0,x 2,., X m )+1 f(1, X 2,, X m ) =f(1, X 2,, X m ) 左辺 = 右辺 以下同様に f を X 2, X 3,, X m で展開し切ると 項数は 2 m となる ( 最小項展開 ) f(x 1, X 2,, X m ) = X 1 X 2 f(0, 0,, X m )+ X 1 X 2 f(0, 1,, X m ) +X 1 X 2 f(1, 0,, X m )+X 1 X 2 f(1, 1,, X m ) = X 1 X 2 X m f(0, 0,, 0) + X 1 X 2 X m f(0, 0,, 1) + +X 1 X 2 X m f(1, 1,, 0) +X 1 X 2 X m f(1, 1,, 1) それぞれの項は全ての変数を必ず 1 つ含む論理積であり これを最小項という 同じく この関数 f をベン図で表現し ベン図上の最小区分が最小項に対応することを確認しなさい L 例題 2: 以下の真理値表で示される関数 f を主加法標 準形で表しなさい f シャノンの展開定理 ( 双対 )* f(x 1, X 2,, X m ) =(X 1 X 1 )+f(x 1, X 2,, X m ) =(X 1 +f(x 1, X 2,, X m )) ( X 1 +f(x 1, X 2,, X m )) =(X 1 +f(0, X 2,, X m )) ( X 1 +f(1, X 2,, X m )) 例題 1: シャノンの展開定理 ( 双対 ) を証明しなさい 例題 :f(,, )=++ をシャノンの展開定理を用いて で展開しなさい 主加法標準形 ** 最小項展開は最小項の論理和で表されており これを主加法標準形ともいう 例題 1: 以下の真理値表で示される関数 f を主加法標 準形で表しなさい ( ヒント f(,, )=1 となる最小 項だけを足し合わせればよい ) f(,, ) 以下 f を X 2, X 3,, X m で展開し切ると 項数は同様に 2 m となる ( 最大項展開 ) f(x 1, X 2,, X m ) =(X 1 +X 2 + +X m +f(0, 0,, 0)) (X 1 +X X m +f(0, 0,, 1)) ( X 1 + X 2 + +X m +f(0, 0,, 1)) ( X 1 + X X m +f(1, 1,, 1)) それぞれの項は全ての変数を必ず 1 つ含む論理和であり これを最小項という 例題 2:f(,, )=++ をシャノンの展開定理 ( 双対 ) を用いて で展開しなさい 2-5

14 2.15. 主乗法標準形 ** 最大項展開は最大項の論理積で表されており これを主乗法標準形ともいう 例題 1: 以下の真理値表で示される関数 f を主乗法標 準形で表しなさい ( ヒント f(,, )=0 となる最大 項だけを掛け合わせればよい ) f(,, ) 例題 :3 変数,, を含む最小項 最大項それぞれをベン図で表現し それぞれがド モルガンの定理に示す関係にあることを確認しなさい ( すなわち 最小項を除いた部分が最大項となる ) L L 最小項 L L 最大項 L L 例題 2: 以下の真理値表で示される関数 f を主乗法標 準形で表しなさい f L L L L ( 検算 ) L L まとめ 3 変数,, を含む真理値表において最小項 最大 項は以下の通り 最小項 最大項 Ā Ā Ā Ā Ā Ā Ā Ā+ + L L L L 2-6

15 3. 論理関数の簡単化 3.1. 必要性 * f=++ を主加法標準形で表すと f= + + +Ā となる 3 変数 ( 上下は で連続している ) 例題 : 以下を基本論理ゲートで設計し その数と種類を挙げなさい f=++ ( 簡単化 ) 4 変数 ( 上下は で 左右は D で連続している ) f= + + +Ā ( 展開 ) なお 5 変数以上のカルノー図は実用的ではない 同じ論理関数を実現してもゲート数やゲートの入力 ( ファンイン ) 数 配線数が違う すなわち論理を簡単化すると チップ面積 実装面積の削減 ( コスト ) 低消費電力 ( 電力 ) 長持ち ( 長寿命 ) 小型電池 ( 低容積 ) 故障率の低減 ( 歩留まり ) などの工学的目的を達成できる 論理関数の簡単化の一般的手法として カルノー図を用いた簡単化 クワイン マクラスキー法 (uine-mcluskey: M 法 ) による簡単化がある 3.2. カルノー図本講義ではクワイン マクラスキー法 ( 参考書参照 ) は扱わず カルノー図による簡単化のみ取り上げる カルノー図とは マス目に関数値を記入した図で 論理関数の全ての最小項を 平面状に規則的に配列している すなわち m 変数の場合 2 m 個のマス目から構成されている 例 :2 変数 3.3. カルノー図を用いた簡単化 ( 加法標準形 )** 以下の真理値表で表現される論理関数 f を考える D f 準備 : 関数値が 1 のマスに 1 と記入する f D

16 主項できるだけ大きな で 1 を囲む は長方形の 1,2,,2 m 個のマスとする で囲まれた論理積項を主項という f D マス以上を含む主項は 変数を消去できる 2 マスの主項は 1 変数を消去できる 4 マスの主項は 2 変数を消去できる 8 マスの主項は 3 変数を消去できる 必須主項唯一の主項に囲まれた 1 がある場合 その主項は必須主項である 必須主項は最終解に含める 上図は全ての主項が必須主項である その他の主項必須主項に含まれない 1 がある場合 これを含む最大の主項も最終解に含める 最終解結局 上図の場合 f= と簡単化できる まとめ 1. できるだけ大きな で 1 を囲む ( 主項 ) 2. 必須主項 最終解 3. 残った 1 を含む最大の主項 最終解 3-2

17 例題 : 以下のカルノー図を簡単化せよ f D f D f D f D 組み合わせ禁止 (don t care) 入力の特定の組み合わせが禁止されていること 例 :4 ビットの入力は 10 進数 0~9 に限定されており 0x~0xF は入力されない場合 は組み合わせ禁止である 組み合わせ禁止は カルノー図中では X で表わす 入力が禁止されているので 関数値は 0 でも 1 でも都合のよい方でかまわない 例題 : 以下のカルノー図を簡単化せよ f D X X 10 X 1 f f D X 1 X 11 X 1 X X

18 3.5. カルノー図を用いた簡単化 ( 乗法標準形 )** 乗法標準形の場合は カルノー図の 0 を囲めばよい 例 : 以下の論理関数 f を考える (3.3 と同じ ) D f 加法標準形 乗法標準形による簡単化の比較同じ論理関数であっても 加法標準形による簡略化と乗法標準形による簡略化では 論理回路の複雑さが一般的に異なる 例 : 上述の論理関数 f の場合 加法標準形における基本論理ゲートの種類と数 乗法標準形における基本論理ゲートの種類と数 関数値が 0 のマスに 0 と記入する 以下同様 f D

19 3.7. 加法標準形と乗法標準形の組み合わせによる簡単化両者を組み合わせると 論理回路をより簡単化できる場合がある ( 決定論的でなく センスが必要 ) 例 : 以下の論理関数 f を加法標準形で簡単化する f D 例 : 以下の論理関数 f を加法標準形で簡単化する f D f= 必要な基本論理ゲートの種類と数は f= 必要な基本論理ゲートの種類と数は 以下の f 1 と f 2 を定義し f=f 1 +f 2 とする 以下の f 1 と f 2 を定義し f=f 1 f 2 とする f 1 D f 1 D f 2 D f 2 D f= 必要な基本論理ゲートの種類と数は f= 必要な基本論理ゲートの種類と数は 3-5

20 メモ 3-6

21 4. 組み合わせ論理回路組み合わせ論理回路とは 現時点での変数入力のみによって 関数出力が決まる論理回路 NOT ND OR NND NOR EXOR EXNOR などの基本論理ゲートを組み合わせて構成 なお今までの講義内容は全て 組み合わせ論理回路 組み合わせ論理回路の例 : f= 万能ゲート ** 万能ゲート NND NND のみで NOT ND OR を表現できる NOT: Ā ND: OR: + = + = ( ド モルガンの定理 ) また = + と表現することがある ここで 反転記号の は = すなわち NOT を意味する NND ゲートのみで NOT ND OR を表現可能 加法標準形 乗法標準形を表現可能 NND は万能ゲート ( 任意の関数を表現可能 ) 万能ゲート NOR NOR も万能ゲートである NOT: Ā OR: 組み合わせ論理回路の設計法 * i) 論理関数の導出 簡単化 ii) ( 必要ならば ) 高次元化 = ファクタリング iii) 回路化 iv) ( 必要ならば ) テクノロジ マッピング 例 1: i) f= +D+ D ( 加法標準形で簡単化済 ) ii) ここでは高次元化は行わない 次元とは 論理積 論理和の深さ ( レベル ) を表す 高次元化とは 論理積 論理和の項数 ( すなわちファンイン ) を減らし 論理の深さを深くすることであり ファクタリングともよぶ 論理の深さについては 次を参照 iii) D 深さ 1 深さ 2 ND OR 入力から見た 論理積 論理和の順番を論理の深さという 通常 入力変数の否定を作る NOT は 論理の深さに含めない 加法標準形をそのまま回路化すると 2 次元 ( 深さ=2) で ND-OR 型になる iv) テクノロジ マッピングとは 利用可能な論理ゲートに置換することをいう 製造技術によって利用可能な論理ゲートは異なり 全ての基本論理ゲート その他が何でも利用可能とは限らない ここでは NND のみ利用可能とする 出力から入力に向かって NND のみになるように 置換していく 深さ 2 の置換 3 入力 OR を 3 入力 NND に置換 D = f f ND: = = + ( ド モルガンの定理 ) 深さ 1 の置換置換された 3 入力 NND の入力にある反転記号 を各 2 入力 ND に移動 D また = と表現することがある 4-1 f

22 NOT の置換 D f のであり 後段の を作る NOT は省略できる ( は入力としてすでに与えられており 二重否定で作る必要はない ) すなわち D 入力 D が与えられたとき 出力 f は NND のみで表現されている 例 2: i) f= +D+ D ( 例 1 と同じ ) ii) f=( +D)+( )D ( 例 1 の 3 入力 ND と 3 入力 OR を 2 入力 ND と 2 入力 OR に限定するように 高次元化する ) iii) D となる 8 個の 2 入力 NND 例 4: i) f= +D+ D ( 例 1 と同じ ) ii) f= +(+ )D (4 次元化 ) iii) 回路化 f f 3 次元 2 入力 ND と 2 入力 OR( と入力の否定を作る NOT) に限定されている iv) ここでは 2 入力 NND に限定する D iv) ここでも 2 入力 NND に限定する f 9 個の 2 入力 NND 例 3: i) f= +D+ D ( 例 1 と同じ ) ii) f=( +D)+( )D ( 別の 3 次元化 ) iii) D 以上のように 回路は設計条件によって さまざまに変わる f 3 次元 iv) ここでも 2 入力 NND に限定する D f しかし 楕円で囲った 2 連続 NOT は と を作るも 4-2

23 例 5: i) f=(+ )(+D)( + ) ( 乗法標準形で簡単化済 ) iii) 回路化 例 6: i) f=(+ )(+D)( + ) ( 例 5 と同じ ) ii) f=(+ D)( + ) ( でくくり 3 次元化 ) iii) 回路化 乗法標準形は 2 次元で OR-ND 型になる iv) ここでは NOR に限定する iv) ここでは 2 入力 NOR に限定する 深さ 2 の置換 3 入力 ND を 3 入力 NOR に置換 深さ 1 の置換置換された 3 入力 NOR の入力にある反転記号 を各 2 入力 OR に移動 例 7: i) f=(+ )(+D)( + ) ( 例 5 と同じ ) ii) f=( + )(+D) ( でくくり 3 次元化 ) iii) 回路化 NOT の置換 iv) ここでも 2 入力 NOR に限定する 入力 D が与えられたとき 出力 f は NOR のみで表現されている 4-3

24 4.3. 組み合わせ論理回路の設計例 加算器 符号なし k 桁 2 進数 =[ k-1 k ] 2 と =[ k-1 k ] 2 の加算 + を 筆算で考 える ( 便宜上 以下 符号なし 2 進数を用いている しかし たとえ符号つきであっても 得られる回路 は同じである ) k-1 k k-1 k arry つの1bitの arry 加算 ( 半加算 ) つの1bitの 2 加算 ( 全加算 ) k-2 + k-2 + k-2 k-1 + k-1 + k-1 Sum Sum Sum S k-1 S k-2 S 2 S 1 S 0 0 桁目は すなわち 2 つの 1bit の加算になる これを半加算という 0 桁目の和 (Sum) は S 0 となる 桁上がり (arry) が 1 桁目に 1 として繰り上がる 1 桁目以降の i 桁目では i + i + i すなわち 3 つの 1bit の加算となる これを全加算という ここでも Sum が S i となり i+1 が i+1 桁目に繰り上がる 半加算器 (H: half adder)** 半加算 + の真理値表は + (=arry) S (=Sum) = S= 半加算器の回路は ところで + = S= と表現することもできる この講義では半加算器の記号( シンボル ) を 以下で表現する H +S + (=) S(= ) 全加算器 (F: full adder)** 全加算 ++ の真理値表は + (=arry) S (=Sum) のカルノー図は = S のカルノー図は S S= 4-4

25 結局 全加算器の回路は リップルキャリーアダー * 符号なし k 桁 2 進数の加算器は 1 個の半加算器と k-1 個の全加算器で構成できる + S また真理値表から + =Ā +Ā + +Ā なので + = となり 3 入力 NND3 個を + と S で共用できる この加算器はさざなみ ( リップル ) のように桁上がりが伝播する方式であり リップルキャリーアダーと呼ばれる また k 個全て 全加算器を用いてもよい ところで S = = ( + ) + ( + ) = ( ) + ( ) = ( ) = + + = + (+ ) = + ( ( + ) + ( + ) = + ( + + ) = + + ( + ) = + ( ) ) と変形でき 全加算器は半加算器 2 個と 2 入力 OR で構成できる この講義では全加算器の記号を 以下で表現する +S + (=++) F S(= ) 減算器 * 符号なし k 桁 2 進数 =[ k-1 k ] 2 と =[ k-1 k ] 2 の減算 - を考える の 2 の補数は [ k-1 k ] 2 +1 なので 筆算は以下のようになる 4-5

26 k-1 k k-1 k arry arry k-2 + k-2 + k-2 k-1 + k-1 + k-1 Sum Sum Sum S k-1 S k-2 S 2 S 1 すなわち 減算器は k 個の全加算器と k 個の NOT で構成できる S 0 2 進数 ( コード ) に対応した番号を持つ入力に 1 が入ると そのコードを出力する 例えば の 4 入力と Y 1 Y 0 の 2 出力を持つ 4 入力 2 出力エンコーダでは 2 =1 のときには [Y 1 Y 0 ] 2 =2 となる このとき 一般には i =0 (i 2) とし 組 み合わせ禁止にする すなわち の 4 入力のうちの 1 つのみが 必ず 1 となることを前提 とする 真理値表は Y 1 Y Y 0 のカルノー図は Y エンコーダ (2 k 入力 k 出力 ) あるキーとたたくと SII コードが出るような キーボードに代表される動作 Y 0 = Y 1 のカルノー図は Y Y 1 = 結局 4 入力 2 出力エンコーダの回路は 4-6

27 プライオリティエンコーダ 上記エンコーダから 組み合わせ禁止の前提をな くしたもの 入力が 1 であるビットのうち 最大の 番号に対応するコードを出力する 例えば 3 = 2 =1 のときには [Y 1 Y 0 ] 2 =3 となる 真理値表は Y 1 Y 0 N Y 0 のカルノー図は デコーダ (k 入力 2 k 出力 )* エンコーダと逆の動作 PU の命令解読 ( 回路選択 ) などに使われている Y Y 0 = Y 1 のカルノー図は Y Y 1 = なお真理値表から N= である N はいずれの入力にも 1 がないことを示し [ ] 2 =0 と [ ] 2 =1 を区別するために用いる 結局 4 入力 2 出力プライオリティエンコーダの回路は 入力コードに対応した番号を持つ出力を 1 とする 例えば の 3 入力と Y 7 Y 6 Y 5 Y 4 Y 3 Y 2 Y 1 Y 0 の 8 出力を持つ 3 入力 8 出力デコーダ では [ ] 2 =5 のときには Y 5 =1 となる こ のとき Y i =0 (i 5) である 真理値表は Y 7 Y 6 Y 5 Y 4 Y 3 Y 2 Y 1 Y Y 0 = Y 1 = Y 2 = Y 3 = Y 4 = Y 5 = Y 6 = Y 7 = 4-7

28 3 入力 8 出力デコーダの回路は Y のカルノー図は Y S Y= 結局 2 入力マルチプレクサの回路は この講義では 3 入力 8 出力デコーダの記号を 以下で表現する Y 0 Y 1 Y 2 Y 3 Y 4 Y 5 Y 6 Y マルチプレクサ (k 入力 )* 入力 S 1 0 と出力 Y を持つ 2 入力マルチプレ クサでは 入力 S の値によって 入力 1 または 0 のどちらかを 出力 Y として選択する セレクタと もいう すなわち S=0 のとき Y= 0 となる S =1 のとき Y= 1 となる 真理値表は S 1 0 Y (S=0 Y= 0, S=1 Y= 1 ) この講義では 2 入力マルチプレクサの記号を 以下で表現する S もちろん 3 以上の入力を持ったマルチプレクサも存在する 例えば 4 入力マルチプレクサは の 4 入力うちの 1 つを S=[S 1 S 0 ] で選択する 記号と論理式は Y= S 1 S 0 各項の S 1 S 0 S 1 S 0 S 1 S 0 S 1 S 0 は S 1 と S 0 を入力とした 2 入力 4 出力デコーダの出力そのものであるので 以下でも構成できる Y Y 4-8

29 デマルチプレクサ * マルチプレクサとは逆の動作 複数の出力のうち の 1 つに 入力を分配する 入力 S と出力 Y 1 Y 0 を持つ 2 出力デマルチプレクサは 入力 S の値に よって 出力 Y 1 または Y 0 のどちらかに 入力 を 分配する 入力 が分配されない出力は 0 とする すなわち S=0 のとき Y 0 = (Y 1 =0) となる S=1 のとき Y 1 = (Y 0 =0) となる 真理値表は S Y 1 (S=1 Y 1 =) Y 0 (S=0 Y 0 =) 各式の S 1 S 0 S 1 S 0 S 1 S 0 S 1 S 0 は S 1 と S 0 を入力とした 2 入力 4 出力デコーダの出力そのものであるので 以下でも構成できる Y 0 = Y 1 = 2 出力デマルチプレクサの回路は また =1 ならば デマルチプレクサはデコーダとして動作する この講義では 2 出力デマルチプレクサの記号を 以下で表現する 0 1 S Y 0 Y 1 もちろん 3 以上の出力を持ったデマルチプレクサも存在する 例えば 4 出力デマルチプレクサは Y 3 Y 2 Y 1 Y 0 の 4 出力のうちの 1 つに S=[S 1 S 0 ] で分配する 記号と論理式は Y 0 = Y 1 = Y 2 = Y 3 = S 1 S 0 Y 0 Y 1 Y 2 Y 3 4-9

30 メモ 4-10

31 5. ラッチ (latch) とフリップフロップ (flip-flop) 論理回路で用いられる記憶素子の総称 5.1. 記憶回路の出力変化のタイミング 同期型入力にクロックがあり クロックに同期して 出力が変化 または出力を保持 非同期型入力にクロックがなく クロックとは無関係に 入力の変化に応じて 出力が変化 5.2. 記憶回路の分類 Dフリップフロップエッジ感知型 Tフリップフロップ同期型 JKフリップフロップ Dラッチレベル感知型ゲートつきSRラッチ非同期型 SRラッチ フリップフロップクロックのエッジ ( 立ち上がり 立ち下がり ) に同期して 出力が変化するもの ラッチクロックのエッジ以外のタイミング すなわち入力の変化に応じて 出力が変化するもの 5.3. SR( セットリセット ) ラッチ非同期型の基本的なラッチ RS ラッチということもある 回路 S R S=0 =1 R=0 =0 S=0 =0 R=0 = セット (S=1 R=0) S=1 R=0 にすると =1( セット ) になる S=0! S=1! S=0 =1! =0!=0 R=0!R=0! R=0 =0!=1! =1 S=0! S=1! S=0 =0! =0!=0 R=0!R=0!R=0 =1!=1! = リセット (S=0 R=1) S=0 R=1 にすると =0( リセット ) になる S=0! S=0! S=0 =1! =1!=1 R=0!R=1! R=0 =0!=0! =0 S=0! S=0! S=0 =0! =1!=1 R=0!R=1!R= 入力禁止 (S=R=1) =1!=0! = 特性表 ( 機能表ということもある )* S R (の直前の状態を保持) 0 1 0( リセット ) 1 0 1( セット ) 1 1 X( 入力禁止 ) S=1 で セット (を 1 にする ) R=1 で リセット (を 0 にする ) S=R=0 で の直前の状態を保持 (= - ) S=R=1 は入力禁止 記号 S R 動作波形 ( タイミングチャート )** 双安定性 ( 保持 :S=R=0) S=R=0 の時 =1 =0 =0 =1 の 2 つの状態で安定 すなわち S=R=0 となる直前の状態 ( - =0 or 1) を保持できる 5-1 S R

32 NND 型への変形 動作波形 G S R 5.4. ゲートつき SR ラッチ SR ラッチにゲート入力 G を追加し G=0 直前の状態を保持 G=1 SR ラッチと同様の動作となる G のレベル ( 値 ) に応じて動作するラッチ 回路 S G R S R G=0 S =R =1 双安定 S =1 = 双安定 R =1 G=1 SRラッチ S R = SR ラッチ 5.5. D( データ ) ラッチゲートつき SR ラッチの変形 S=D R= D とする 回路 D G ( わかりにくい ) 特性表 G D (=D - :G=0 になる直前のDの値 ) (=D - :G=0 になる直前のDの値 ) 1 0 0(=D) 1 1 1(=D) 記号 * 動作波形 ** D G 特性表 G S R (の直前の状態を保持) (の直前の状態を保持) (の直前の状態を保持) (の直前の状態を保持) (の直前の状態を保持) ( リセット ) ( セット ) X( 入力禁止 ) 記号 S R G 5-2 G D ( わかりやすい ) 特性表を こう書くこともある ** G D 0 0(=D - :Gが立下がる直前のDの値) 1 1(=D - :Gが立下がる直前のDの値) 1 0 0(=D) 1 1 1(=D)

33 5.6. D フリップフロップ D ラッチをカスケード接続 ( マスター スレイブ構成 ) したもの 回路 D K D G P D G ( わかりにくい ) 特性表 K D P (の直前の状態を保持) (の直前の状態を保持) 1 0 P - (=D - :K=1 になる直前のDの値 ) P(=P - =D - :K=1 になる直前のDの値 ) 1 1 P - (=D - :K=1 になる直前のDの値 ) P(=P - =D - :K=1 になる直前のDの値 ) 記号 * D > はクロック入力 (K) を示す 出力がない場合の記号は 以下のとおり D 動作波形 ** K D P ( わかりやすい ) 特性表を こう書くこともある ** K D 0 0(=D - :Kが立上がる直前のDの値) 1 1(=D - :Kが立上がる直前のDの値) 5-3

34 例題 1: シフトレジスタ * D フリップフロップを以下のように多段接続し 入力 D を与えたときの動作波形を描け ただし初期値として 0 = 1 = 2 = 3 =0 とする D D 0 D D D K K D このように 1 クロックずつ 波形が遅れる機能を持つ回路をシフトレジスタという 例題 2:T( トグル ) フリップフロップ * D フリップフロップを以下のように接続したときの 動作波形を描け ただし初期値として =0 とする K D または K K D は K の周波数を半分にしたものであり 一般に 周波数を半分にする回路を分周器という また 出力がクロック入力に同期して反転することをトグルといい フリップフロップで実装したこの回路を T( トグル ) フリップフロップという 5.7. T( トグル ) フリップフロップ Tフリップフロップは クロック入力 Tの半分の周波数を から出力する 特性表と記号 T - ( 反転 ) T または T 5.8. JKフリップフロップ^ その他のフリップフロップの1つに JKフリップフロップがある 特性表と記号 K J( セットに対応 ) K( リセットに対応 ) ( 保持 ) 0 1 0( リセット ) 1 0 1( セット ) ( 反転 ) J K 5-4

35 6. 順序回路出力が 現時点の変数入力と 過去の状態に依存する論理回路 すなわち 過去の状態を記憶する回路 ( 記憶回路 : ラッチ フリップフロップ ) が含まれる 6.1. モデル 組み合わせ論理回路のモデル 現時点での入力のみによって 出力が決まる 入力 組み合わせ論理回路 出力 Y 順序回路のモデル ( ミーリー型モデル ) 現時点での入力 + 過去の状態で 出力と次の状態が決まる 記憶回路 入力 過去の状態 S 組み合わせ論理回路 出力 Y 6.2. 同期式順序回路同期式順序回路とは クロックに同期して 出力が変化する順序回路 D フリップフロップを記憶回路として用いれば 同期式順序回路を構成できる この講義では 非同期式順序回路については触れない 同期式順序回路モデル ( ミーリー型モデル )* S (t+1) K D S (t) 入力 組み合わせ論理回路現在の記憶状態 S (t) 出力 Y 次の (1 クロック後の ) 記憶状態 S (t+1) 具体的な回路図で書くと 以下のとおり 6-1

36 6.3. 状態遷移図と状態遷移表順序回路の設計には 状態遷移図と状態遷移表を用いる 状態遷移図 ** 状態の変化を 入力 出力とともに図示したもの ラベルは入力 / 出力 (=/Y) を表す 接点 ( ) は状態を表し 現在はいずれかの状態にある 1 クロックごとに必ず どこかの状態に遷移する 矢印はその遷移を表す /Y 0/0 0/0 0/ 回路化 ** S (t) =[ 1 (t) 0 (t) ] 2 S (t+1) =[ 1 (t+1) 0 (t+1) ] 2 とする 1 (t+1) のカルノー図は 以下で与えられる 1 (t+1) 1 (t) 0 (t) (t+1) = 1 (t)ā+ 0 (t) 1/0 S 0 S 1 1/1 S 2 0 (t+1) のカルノー図は 以下で与えられる 0 (t+1) 1 (t) 0 (t) 0 1 1/1 1/ S (t+1) 0 = (t) 1 + (t)ā 0 0/0 この場合, 状態数は 4 であり,2 個の D フリップフロップが必要である 状態遷移表 ** 状態遷移図を表に書下したもの 現在の状態 S (t) 次の状態 S (t+1) 出力 Y 入力 入力 S 0 S 0 S S 1 S 1 S S 2 S 2 S S 3 S 3 S Y のカルノー図は 以下で与えられる Y (t) (t) Y=( (t) 1 + (t) 0 ) 結局 回路は以下のようになる 状態変数 次に 状態に固有の変数を割り当てる k ビットの変 数で 2 k 状態まで表現できる S 0 S 1 S 2 S 3 は 4 状態であり 2 ビット (2 つの D フリップフロップ ) で表現できる どの状態に [00] 2 [01] 2 [10] 2 [11] 2 を割り当てるかは 一般に任意で あるが 割り当て方によって 回路規模は異なる ここでは S 0 =[00] 2 S 1 =[01] 2 S 2 =[11] 2 S 3 =[10] 2 とすると 状態遷移表は以下となる 現在の状態 S (t) 次の状態 S (t+1) 出力 Y 入力 入力 S 0 :00 S 0 :00 S 1 : S 1 :01 S 1 :01 S 2 : S 2 :11 S 2 :11 S 3 : S 3 :10 S 3 :10 S 0 :

37 例題 1 クロック入力 K に同期して 記憶している値を 1 ずつ増やす回路をアップカウンタという 入力 が =0 のときには 出力 Y=[Y 1 Y 0 ] は [00] [01] [10] [11] とカウントアップし =1 のときには ホールド ( 出力そのまま ) するカウンタを設計せよ 結局 回路は以下のようになる 状態遷移図 : /Y 1 Y 0 1/00 1/01 S 0 [00] 0/00 S 1 [01] 0/11 0/01 S 3 [11] 0/10 S 2 [10] 1/11 1/10 状態遷移図 : (t) (t) 1 0 (t+1) (t+1) 1 0 Y 1 Y S 0 :00 S 1 :01 S 0 : S 1 :01 S 2 :10 S 1 : S 2 :10 S 3 :11 S 2 : S 3 :11 S 0 :00 S 3 : (t+1) のカルノー図 : 1 (t+1) 1 (t) 0 (t) (t+1) 0 のカルノー図 : 0 (t+1) 1 (t) 0 (t)

38 例題 2 クロック入力 K に同期して 出力 Y=[Y 1 Y 0 ] を [01] [01] [10] [11] とカウントアップする回路を設計せよ 状態遷移図 : S 0 [00] 入力なし /Y 1 Y 0 X/01 S 1 [01] 例題 3 以下の状態遷移図を有する順序回路を示せ 状態遷移図 : 0/0 /Y 1/1 S 0 [0] 1/0 0/1 S 1 [1] X/11 X/01 S 3 [11] X/10 S 2 [10] 状態遷移図 : (t) (t) 1 0 (t+1) (t+1) 1 0 Y 1 Y 0 S 0 :00 S 1 :01 01 S 1 :01 S 2 :10 01 S 2 :10 S 3 :11 10 S 3 :11 S 0 :00 11 結局 回路は以下のようになる 6-4