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

(1)

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

(2)

(3)

1. 2 進数 1.1. q 進数 1.1.1. 10 進数(decimal number) おなじみ。例えば、・55 ・[1001]10 添え字の10 は 10 進数を表す。 10 種類の記号(0, 1, 2, …, 9)で表現される数。 1.1.2. 1 進数 1.1.3. 2 進数(binary number)** 最もシンプルな表現。 2 種類の記号(0, 1)で表現される。・[110]2 ＝1×22_＋1×21_＋0×20 ＝[6]10 1.1.4. 2 進数の小数部 小数部も整数部と同様に扱う。・[110.101] ＝6＋1×2-1_＋_0×2-2_＋_1×2-3 ＝6+0.5+0+0.125 ＝[6.625]10 1.1.5. q 進数（一般化） 例題：以下の2 進数を 10 進数で表現しなさい。 [11100001.1]2＝

1.1.6. 16 進数(hexadecimal number、hex number)* 16 種類の記号(0, 1, 2, …, 9, A, B, C, 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 ・[A]16＝[1010]2＝[10]10 ・[B]16＝[1011]2＝[11]10 ・[C]16＝[1100]2＝[12]10 ・[D]16＝[1101]2＝[13]10 ・[E]16＝[1110]2＝[14]10 ・[F]16＝[1111]2＝[15]10 16＝24_なので_{16 進数 1 桁が 2 進数 4 桁に対応する。} ・[11100001]2＝[E1]16＝E1h=0xE1（2 桁の 16 進数） 16 進数は E1h とか 0xE1 と書くことが多い。 C 言語（プログラム言語の一種）でも 16 進数は 0x???? と書く。 1.2. 10 進数から q 進数への変換 1.2.1. 10 進数の整数 N から q 進数への変換 N＝[ak－1 ak－2 … a1 a0]qとする。 N／q＝S0 あまり a0 S0／q＝S1 あまり a1 … Sk－2／q＝0 あまり ak－1 商Siが0 になりまで繰り返す。 1.2.2. 10 進数の小数部 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（小数部） … 小数部diが0 にならない場合がある（循環小数）。裏面に例題あり。 1.3. ビットとバイト 1.3.1. ビット(bit)** 2 進数の 1 桁のことをビットという。・[1011]2は4 ビット。 4bit または 4b（b は小文字）とも書く。 b は 2 進数の意味で使われることもある。・[1011]2＝1011b b が桁または 2 進数の意味かどうかは、文脈で判断するしかないので注意。

2 進数の最上位ビットを MSB (most significant bit)、最下位ビットをLSB (least significant bit)という。 1.3.2. バイト(byte)** 8 ビットを 1 バイトという。・[10111111]2は1 バイト。 1Byte または 1B（B は大文字）とも書く。 1 バイトで 0 から 255 までの 10 進数を表現可能。・0xBFC0 は 2 バイト(2Byte, 2B)。 B は 16 進数と間違いやすいので、文脈に注意。例題：0xB は何ビット？例題：[65]10は何バイト？ 1.3.3. 工学単位系とビットの関係* 工学単位系：・k＝103_＝₁₀₀₀ ・M＝106_＝1000000 ・G＝109_＝_1000000000 計算機の単位系：・k＝210₌₁₀₂₄ ・M＝220_＝_1048576 ・G＝230_{＝1073741824} 文脈で使い分けること。この授業では特に断らない

(4)

(5)

1.4. 負数の表現 今までの数は全て正数（符号なし：unsigned）であった。この節では負数を含む体系（符号つき：signed）について述べる。 1.4.1. 符号と絶対値 最上位桁に符号を割り当てる。・10 進数の場合は“＋”または“－”。 [＋3.625]10→3.625 [－3.625]10→－3.625 ・2 進数の場合は MSB を符号とする。 “0”→“＋”、“1”→“－”。 [011.101]2→[＋11.101]2→3.625 [111.101]2→[－11.101]2→－3.625 1.4.2. 補数 q 進数 k 桁の整数 N を N＝[ak－1 ak－2 … a1 a0]qとする。－N はいずれかの補数で定義される。・N の q の補数 Mq Mq=qk－N ・N の(q－1)の補数 Mq－1 Mq－1=(qk－1)－N 結局、Mq－1はq 進数 k 桁の最大の整数 qk－1 から N を引いたものとなり、MqはMq－1に1 を加えたものとなる。例題：N=[3]10 －N＝（N の 9 の補数 M9）＝－N＝（N の 10 の補数 M10）＝ N=[256]10 －N＝（N の 9 の補数 M9）＝－N＝（N の 10 の補数 M10）＝ 1.4.3. 2 進数の 1 の補数* 例題：N=[01]2 －N＝（N の 1 の補数 M1）＝ N=[01011]2 －N＝（N の 1 の補数 M1）＝やはり2 進数 k 桁最大の数 2k_{－1 から N を引いたも} のが2 進数の 1 の補数である。2 進数の 1 補数の場合は各ビットを反転（0→1、1→0）させればよい。 1.4.4. 2 進数の 2 の補数** 2 進数 k 桁の整数 N とする。2k_から_{N を引いたもの} が2 進数の 2 の補数 M2である。定義上、N＋M2＝2k となり、MSB＋1 桁目に桁上がり(carry)が生じる。例題：N=[01]2 －N＝（N の 2 の補数 M2）＝ N=[01011]2 －N＝（N の 2 の補数 M2）＝ 2 の補数は 1 の補数に 1 を足したものである。すなわち2 の補数は、各ビットを反転させたものに 1 を加えれば得られる。 1.4.5. 2 進数小数の 2 の補数* 同様に、足して MSB+1 桁目に桁上がりを生じさせる数が、2 進数小数の 2 の補数である。すなわち全ビットを反転させて、LSB に 1 を加えればよい。例題：[0101.0101]2の2 の補数＝ [0111.1]2の2 の補数＝ 1.4.6. 2 進数の補数のまとめ 裏面に重要な例題**あり。

(6)

例題：8 ビットの 2 進数を考える。以下の表を埋めなさい。符号なし 10 進数 (unsigned) 符号なし 2 進数** (unsigned) 符号つき 10 進数 (signed) 2 進数 1 の補数 (signed) 2 進数 2 の補数** (signed) 0 00000000 －128 なし 10000000 1 00000001 －127 10000000 10000001 2 00000010 －126 10000001 10000010 3 00000011 －125 10000010 10000011 … … … … … 124 01111100 －3 11111100 11111101 125 01111101 －2 11111101 11111110 126 01111110 －1 11111110 11111111 127 01111111 －0 11111111 128 10000000 0 00000000 00000000 129 10000001 1 00000001 00000001 130 10000010 2 00000010 00000010 131 10000011 3 00000011 00000011 … … … … … 252 11111100 124 01111100 01111100 253 11111101 125 01111101 01111101 254 11111110 126 01111110 01111110 255 11111111 127 01111111 01111111 8 ビットの 2 進数は、、、・符号なし** 0～255 を表現できる。・1 の補数－127～127 を表現できる。零が－0 と 0 の 2 種類、存在する。結果的にMSB は符号を表している。1 の場合、負数。0 の場合、正数または零。・2 の補数** －128～127 を表現できる。零は 0 の 1 種類のみ。結果的にMSB は符号を表している。1 の場合、負数。0 の場合、正数または零。例題：8 ビットの 2 進数の補数を考える。以下の表を埋めなさい。 2 進数 1 の補数 (signed) 符号つき 10 進数 (signed) 2 進数 2 の補数** (signed) 符号つき 10 進数 (signed) 00000000 0 00000000 0 00000001 1 00000001 1 00000010 2 00000010 2 00000011 3 00000011 3 … … … … 01111100 124 01111100 124 01111101 125 01111101 125 01111110 126 01111110 126 01111111 127 01111111 127 10000000 －127 10000000 －128 10000001 －126 10000001 －127 10000010 －125 10000010 －126 10000011 －124 10000011 －125 … … … … 11111100 －3 11111100 －4 11111101 －2 11111101 －3 11111110 －1 11111110 －2 11111111 －0 11111111 －1 2 進数の補数を符号つき 10 進数で表現するには、、、・1 の補数：－N＝（N の 1 の補数） ⇒ N＝（N の 1 の補数）の 1 の補数・2 の補数**：－N＝（N の 2 の補数） ⇒ N＝（N の 2 の補数）の 2 の補数.

(7)

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

(8)

(9)

2. 論理関数の基礎 19 世紀、英国の数学者、ジョージ・ブールが提唱した論理数学はブール代数と呼ばれている。後に米国のシャノンが論理設計の基礎理論として発展させた。原則として、変数および関数は0 と 1 の 2 値しか持たない。 2.1. 真理値表 入力変数とその論理関数出力の関係を表にしたものを真理値表という。m 変数関数の入力の組み合わせ数は 2m_である。例：ある3 変数関数 F＝F(A, B, C)の真理値表。入力の組み合わせ数は 23_＝_8。入力出力変数A 変数 B 変数 C 関数 F 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 2.2. m 変数関数 m 変数関数の入力の組み合わせ数は： m 変数関数の出力の組み合わせ数（出力パターン数）は： 2 変数関数の網羅的真理値表は以下のとおり。 A B F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 FA FB FC FD FE FF 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2.3. 基本論理ゲート** NOT、AND、OR、EXOR、NAND、NOR、EXNOR は基本論理ゲートと呼ばれており、記号（シンボル）がMIL 記号として定められている。 2.3.1. 否定 NOT (INV) 論理式、真理値表、記号： 2.3.2. 論理積 AND 論理式、真理値表、記号：

(10)

2.3.3. 論理和 OR 論理式、真理値表、記号： 2.3.4. 排他的論理和 EXOR (XOR) 論理式、真理値表、記号： 2.3.5. NAND（AND の NOT） 論理式、真理値表、記号： 2.3.6. NOR（OR の NOT） 論理式、真理値表、記号： 2.3.7. EXNOR（EXOR の NOT） 論理式、真理値表、記号：

(11)

2.4. 論理演算の適用順序 優先順位： ①否定＞②論理積＞③論理和＞④排他的論理和例：A＋¯B･C⊕D＝ 2.5. ベン図 集合関係と集合範囲を視覚的に図式化したもの。つまり、真理値表を図式化したもの。一般に演算値が1 のところを塗りつぶす。ベン図では 4 要素以上を含む集合を円では表現できない。 2.5.1. 全集合（普遍集合） 例：長方形の内部は全集合L 2.5.2. 要素（元） 例：L に属する要素 A 例：A（A の補集合） ¯ 2.5.3. 空集合 例：何も含まない集合φ 例：A･¯A（＝φ） 2.5.4. 集合関係* 例：積集合A･B 例：和集合A＋B 例：積集合A･B･C 例：和集合A＋B＋C 2.5.5. EXOR 例：A⊕B 2.5.6. NAND 例：¯¯¯¯A･B 2.5.7. NOR 例：¯¯¯¯¯A＋B 2.5.8. EXNOR 例：¯¯¯¯A⊕B

(12)

2.6. ブール代数の公理 A, B, C∈L ⇒ ・公理1: A＋0＝A （単位元） A･1＝A ・公理2: A＋¯A＝1 （補元） A･¯A＝0 ・公理3: A＋B＝B＋A （交換則） A･B＝B･A ・公理4: A＋B･C＝(A＋B)･(A＋C) （分配則） A･(B＋C)＝A･B＋A･C 2.7. ブール代数の双対性** ここで公理をよく見る 0→1 1→0 ･→＋＋→･に置き換えても同じく公理となり、これを双対性という。つまり m 変数論理関数 f(X1, X2, …, Xm, 0, 1, ･, +) ＝g(X1, X2, …, Xm, 0, 1, ･, +) ⇒ その双対でも f(X1, X2, …, Xm, 1, 0, +, ･) ＝g(X1, X2, …, Xm, 1, 0, +, ･) 2.8. ブール代数の代表的な定理^（あまり重要でない）・定理1: A＋A＝A （べき等則） A･A＝A ・定理2: A＋1＝1 （零元） A･0＝0 ・定理3: A＝A （復元則、二重否定）・定理4: A＋(B＋C)＝(A＋B)＋C （結合則） A･(B･C)＝(A･B)･C ・定理5: A＋A･B＝A （吸収則） A･(A＋B)＝A ・定理6: A＋¯A･B＝A＋B A･(¯A＋B)＝A･B ・定理7: A･B＋B･C＋C･¯A＝A･B＋C･¯A (A＋B)･(B＋C)･(C＋¯A)＝(A＋B)･(C＋¯A) ・定理8: (A＋B)･(¯A＋C)＝A･C＋¯A･B

A･B＋¯A･C＝(A＋C)･(¯A＋B)

・定理9: (A+B)･(C+D)＝A･C+A･D+B･C+B･D A･B+C･D＝(A+C)･(A+D)･(B+C)･(B+D) （分配則の分配則） 2.9. ド・モルガンの定理** 以下の定理10 を特に、ド・モルガンの定理という。・定理10**: ¯¯¯¯¯A＋B＝¯A･¯B ¯¯¯¯A･B＝¯A＋¯B 論理積を論理和で（論理和を論理積で）表現できることを示している重要な定理。ド・モルガンの定理は以下の定理11 を用いると解析的に証明できる（板書参照）。

・定理11^: B+ ¯A＝1, B･¯A＝0 ⇒ A＝B

例題：ド・モルガンの定理を真理値表で確認せよ。例題：ド・モルガンの定理をベン図で確認せよ。ド･モルガンの定理の応用・定理12^: A⋅C+B⋅C＝¯A･C＋¯B･¯C ) C (B C) (A+ ⋅ + ＝(¯A＋C)･(¯B＋¯C) 2.10. m 変数論理関数におけるド･モルガンの定理* 一般化 ¯f(X1, X2, …, Xm, ･, +) ＝f(¯¯X1, ¯¯X2, …, ¯¯Xm, +, ･) 2.11. 排他的論理和における代表的な定理^ ・定理EX1: 0⊕B＝B 1⊕B＝¯B ・定理EX2: A⊕A＝0 A⊕¯A＝1 ・定理EX3: A⊕B＝B⊕A ・定理EX4: A･(B⊕C)＝(A･B)⊕(A･C) ただし A＋(B⊕C)≠(A＋B)⊕(A＋C) ・定理EX5: A⊕(B⊕C)＝(A⊕B)⊕C

(13)

2.12. シャノンの展開定理* 任意のm 変数論理関数 f(X1, X2, …, Xm)を X1について展開する。 f(X1, X2, …, Xm) ＝(¯¯X1＋X1)･f(X1, X2, …, Xm) ＝¯¯X1･f(X1, X2, …, Xm)＋X1･f(X1, X2, …, Xm) ＝¯¯X1･f(0, X2, …, Xm)＋X1･f(1, X2, …, Xm) これをシャノンの展開定理という。 (証明） X1＝0 の時左辺＝f(0, X2, …, Xm) 右辺＝1･f(0,X2,…., Xm)＋0･f(1, X2, …, Xm) ＝f(0, X2, …, Xm) ∴左辺＝右辺 X1=1 の時左辺＝f(1, X2, …, Xm) 右辺＝0･f(0,X2,…., Xm)＋1･f(1, X2, …, Xm) ＝f(1, X2, …, Xm) ∴左辺＝右辺 □ 以下同様に、f を X2, X3, …, Xmで展開し切ると、項数は2m_{となる（最小項展開）。} f(X1, X2, …, Xm) ＝¯¯X1･X¯¯2･f(0, 0, …, Xm)＋¯¯X1･X2･f(0, 1, …, Xm) ＋X1･¯¯X2･f(1, 0, …, Xm)＋X1･X2･f(1, 1, …, Xm) ＝¯¯X1･X¯¯2･…･ ¯¯Xm･f(0, 0, …, 0) ＋¯¯X1･¯¯X2･…･Xm･f(0, 0, …, 1) ＋… ＋X1･X2･…･ ¯¯Xm･f(1, 1, …, 0) ＋X1･X2･…･Xm･f(1, 1, …, 1) それぞれの項は全ての変数を必ず 1 つ含む論理積であり、これを最小項という。例題：f(A, B, C)＝AB＋BC＋AC をシャノンの展開定理を用いてA で展開しなさい。 2.13. 主加法標準形** 最小項展開は最小項の論理和で表されており、これを主加法標準形ともいう。例題1：以下の真理値表で示される関数 f を主加法標準形で表しなさい（ヒント、f(A, B, C)＝1 となる最小項だけを足し合わせればよい）。 A B C f(A, B, C) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 同じく、この関数f をベン図で表現し、ベン図上の最小区分が最小項に対応することを確認しなさい。

L

C

A

B

L

C

A

B

例題2：以下の真理値表で示される関数 f を主加法標準形で表しなさい。 A B f 0 0 0 0 1 1 1 0 1 1 1 0 2.14. シャノンの展開定理（双対）* f(X1, X2, …, Xm) ＝(X1･¯¯X1)＋f(X1, X2, …, Xm) ＝(X1＋f(X1, X2, …, Xm))･(¯¯X1＋f(X1, X2, …, Xm)) ＝(X1＋f(0, X2, …, Xm))･(¯¯X1＋f(1, X2, …, Xm)) 例題1：シャノンの展開定理（双対）を証明しなさい。以下、f を X2, X3, …, Xmで展開し切ると、項数は同様に2m_{となる（最大項展開）。} f(X1, X2, …, Xm) ＝(X1＋X2＋…＋Xm＋f(0, 0, …, 0)) ･(X1＋X2＋…＋ ¯¯Xm＋f(0, 0, …, 1)) ･… ･(¯¯X1＋X¯¯2＋…＋Xm＋f(0, 0, …, 1)) ･(¯¯X1＋¯¯X2＋…＋ ¯¯Xm＋f(1, 1, …, 1)) それぞれの項は全ての変数を必ず 1 つ含む論理和であり、これを最小項という。例題2：f(A, B, C)＝AB＋BC＋AC をシャノンの展開定理（双対）を用いてA で展開しなさい。

(14)

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

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

L

C

A

B

(15)

3. 論理関数の簡単化 3.1. 必要性*

f＝AB＋BC＋AC を主加法標準形で表すと、 f＝A･B･C＋A･B･¯C＋A･¯B･C＋¯A･B･C となる。例題：以下を基本論理ゲートで設計し、その数と種類を挙げなさい。

f＝AB＋BC＋AC （簡単化）

f＝A･B･C＋A･B･¯C＋A･¯B･C＋¯A･B･C （展開）

同じ論理関数を実現してもゲート数やゲートの入力（ファンイン）数、配線数が違う。すなわち論理を簡単化すると・チップ面積・実装面積の削減（コスト）・低消費電力（電力）・長持ち（長寿命）・小型電池（低容積）・故障率の低減（歩留まり）などの工学的目的を達成できる。論理関数の簡単化の一般的手法として・カルノー図を用いた簡単化・クワイン・マクラスキー法（Quine-McCluskey: QM 法）による簡単化がある。 3.2. カルノー図 本講義ではクワイン・マクラスキー法（参考書参照）は扱わず、カルノー図による簡単化のみ取り上げる。カルノー図とは、マス目に関数値を記入した図で、論理関数の全ての最小項を、平面状に規則的に配列している。すなわちm 変数の場合、2m_{個のマス目か} ら構成されている。例：2 変数 3 変数（上下は¯Bで連続している） 4 変数（上下は¯Bで、左右は¯Dで連続している）なお、5 変数以上のカルノー図は実用的ではない。 3.3. カルノー図を用いた簡単化（加法標準形）** 以下の真理値表で表現される論理関数f を考える。 A B C D f 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 準備：関数値が1 のマスに、1 と記入する。 f CD AB 00 01 11 10 00

01

11

10

(16)

3.3.1. 主項 できるだけ大きな○で1 を囲む。○は長方形の 1，2，…，2m_{個のマスとする。○で囲まれた論理積項を主項} という。 f CD AB 00 01 11 10 00

01

11

10

2 マス以上を含む主項は、変数を消去できる。・2 マスの主項は、1 変数を消去できる。・4 マスの主項は、2 変数を消去できる。・8 マスの主項は、3 変数を消去できる。 3.3.2. 必須主項 唯一の主項に囲まれた1 がある場合、その主項は必須主項である。必須主項は最終解に含める。上図は全ての主項が必須主項である。 3.3.3. その他の主項 必須主項に含まれない1 がある場合、これを含む最大の主項も最終解に含める。 3.3.4. 最終解 結局、上図の場合、 f＝と簡単化できる。 3.3.5. まとめ 1. できるだけ大きな○で 1 を囲む（主項）。 2. 必須主項 ⇒ 最終解。 3. 残った 1 を含む最大の主項 ⇒ 最終解。

(17)

例題：以下のカルノー図を簡単化せよ。 f CD AB 00 01 11 10 00 1

1 01 1 1 1 11

10 1

1 f CD AB 00 01 11 10 00 1 1 1 01 1

1 11 1

10

f CD AB 00 01 11 10 00 1 1

01 1 1

11

1 1 10 1

1 f C AB 0 1 00 1 01 1

11 1 10 1

f CD AB 00 01 11 10 00 1 1 1 01 1 1 1 1 11 1 1 1 1 10 1 1 1 1 3.4. 組み合わせ禁止(don’t care) 入力の特定の組み合わせが禁止されていること。例：4 ビットの入力は 10 進数 0～9 に限定されており、 0xA～0xF は入力されない場合、・1010 ・1011 ・1100 ・1101 ・1110 ・1111 は組み合わせ禁止である。組み合わせ禁止は、カルノー図中では”X”で表わす。入力が禁止されているので、関数値は0 でも 1 でも都合のよい方でかまわない。例題：以下のカルノー図を簡単化せよ。 f CD AB 00 01 11 10 00

1 01 1 1 1 11 1 X X 10

X 1 f CD AB 00 01 11 10 00 1

1 01 X 1 X 11 X 1 X X 10 1

1

(18)

3.5. カルノー図を用いた簡単化（乗法標準形）** 乗法標準形の場合は、カルノー図の0 を囲めばよい。例：以下の論理関数f を考える（3.3 と同じ）。 A B C D f 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 関数値が0 のマスに、0 と記入する。以下同様。 f CD AB 00 01 11 10 00

01

11

10

3.6. 加法標準形・乗法標準形による簡単化の比較 同じ論理関数であっても、加法標準形による簡略化と乗法標準形による簡略化では、論理回路の複雑さが一般的に異なる。例：上述の論理関数f の場合。・加法標準形における基本論理ゲートの種類と数・乗法標準形における基本論理ゲートの種類と数

(19)

3.7. 加法標準形と乗法標準形の組み合わせによる 簡単化両者を組み合わせると、論理回路をより簡単化できる場合がある（決定論的でなく、センスが必要）。例：以下の論理関数f を加法標準形で簡単化する。 f CD AB 00 01 11 10 00

1 01 1

1 11 1 1

10

1

f＝必要な基本論理ゲートの種類と数は、以下のf1とf2を定義し、f＝f1･f2とする。 f1 CD AB 00 01 11 10 00 1

1 01 1

1 11 1 1

10 1 1

f2 CD AB 00 01 11 10 00 0 0

01

11

10 0 0

f＝必要な基本論理ゲートの種類と数は、例：以下の論理関数f を加法標準形で簡単化する。 f CD AB 00 01 11 10 00

1 01 1 1 1 11

1 1 10

1 f＝必要な基本論理ゲートの種類と数は、以下のf1とf2を定義し、f＝f1＋f2とする。 f1 CD AB 00 01 11 10 00 0 0 0 01 0 0

11 0 0

10 0 0 0 f2 CD AB 00 01 11 10 00

01 1 1 11

10

f＝必要な基本論理ゲートの種類と数は、

(20)

(21)

4. 組み合わせ論理回路組み合わせ論理回路とは、現時点での変数入力のみによって、関数出力が決まる論理回路。 NOT・AND・OR・NAND・NOR・EXOR・EXNOR などの基本論理ゲートを組み合わせて構成。なお今までの講義内容は全て、組み合わせ論理回路。組み合わせ論理回路の例：

A

B

f=AB+C

C

A

B

f=AB+C

C

4.1. 万能ゲート** 4.1.1. 万能ゲート NAND NAND のみで NOT・AND・OR を表現できる。・NOT: ¯A ・AND: AB ・OR: A+B=A+B=A⋅B（ド・モルガンの定理）また

A

B

A+B

=

と表現することがある。ここで、反転記号の○は

=

すなわち、NOT を意味する。 NAND ゲートのみで NOT・AND・OR を表現可能 ⇒ 加法標準形・乗法標準形を表現可能 ⇒ NAND は万能ゲート（任意の関数を表現可能）。 4.1.2. 万能ゲート NOR NOR も万能ゲートである。・NOT: ¯A ・OR: A+B ・AND: AB=AB=A+B（ド・モルガンの定理）また

A

B

AB

=

4.2. 組み合わせ論理回路の設計法* i) 論理関数の導出・簡単化 ii) （必要ならば）高次元化＝ファクタリング iii) 回路化 iv) （必要ならば）テクノロジ・マッピング例１： i) f＝A¯B＋AD＋¯BCD （加法標準形で簡単化済） ii) ここでは高次元化は行わない。・次元とは、論理積・論理和の深さ（レベル）を表す。・高次元化とは、論理積・論理和の項数（すなわちファンイン）を減らし、論理の深さを深くすることであり、ファクタリングともよぶ。・論理の深さについては、次を参照。 iii)

A B C D

f

深さ

1 AND

深さ

2 OR

A B C D

f

深さ

1 AND

深さ

2 OR

入力から見た、論理積・論理和の順番を論理の深さという。通常、入力変数の否定を作るNOT は、論理の深さに含めない。加法標準形をそのまま回路化すると、2 次元（深さ＝2）で、AND-OR 型になる。 iv) テクノロジ・マッピングとは、利用可能な論理ゲートに置換することをいう。製造技術によって利用可能な論理ゲートは異なり、全ての基本論理ゲート・その他が何でも利用可能とは限らない。ここでは、NAND のみ利用可能とする。・出力から入力に向かって、NAND のみになるように、置換していく。・深さ2 の置換 3 入力 OR を 3 入力 NAND に置換。

A B C D

f

=

A B C D

f

=

3次元

2 入力 AND と 2 入力 OR（と入力の否定を作る NOT）に限定されている。 iv) ここでは、2 入力 NAND に限定する。

A B C D

f

A B C D

f

9 個の 2 入力 NAND。例３： i) f＝A¯B＋AD＋¯BCD （例１と同じ） ii) f＝A(¯B＋D)＋(¯BC)D （別の 3 次元化） iii)

A B C D

f

3次元

A B C D

f

3次元

iv) ここでも、2 入力 NAND に限定する。

A B C D

f

A B C D

f

しかし、楕円で囲った2 連続 NOT は¯Bと B を作るものであり、後段のB を作る NOT は省略できる（B は入力としてすでに与えられており、二重否定で作る必要はない）。すなわち

A B C D

f

A B C D

f

となる。8 個の 2 入力 NAND。例４： i) f＝A¯B＋AD＋¯BCD （例１と同じ） ii) f＝A¯B＋(A＋¯BC)D （4 次元化） iii) 回路化

iv) ここでも、2 入力 NAND に限定する。

・以上のように、回路は設計条件によって、さまざまに変わる。

(23)

例５： i) f＝(A＋¯B)(A＋D)(¯B＋¯C) （乗法標準形で簡単化済） iii) 回路化乗法標準形は、2 次元で OR-AND 型になる。 iv) ここでは、NOR に限定する。・深さ2 の置換 3 入力 AND を 3 入力 NOR に置換。・深さ1 の置換置換された3 入力 NOR の入力にある反転記号○を各 2 入力 OR に移動。・NOT の置換入力A、B、C、D が与えられたとき、出力 f は NOR 例６： i) f＝(A＋¯B)(A＋D)(¯B＋¯C) （例５と同じ） ii) f＝(A＋¯BD)(¯B＋¯C) （A でくくり、3 次元化） iii) 回路化

iv) ここでは、2 入力 NOR に限定する。

例７：

i) f＝(A＋¯B)(A＋D)(¯B＋¯C) （例５と同じ） ii) f＝(¯B＋A¯C)(A＋D) （¯Bでくくり、3 次元化） iii) 回路化

(24)

4.3. 組み合わせ論理回路の設計例 4.3.1. 加算器 ・符号なしk 桁 2 進数 A＝[Ak－1 Ak－2 … A2 A1 A0]2と B＝[Bk－1 Bk－2 … B2 B1 B0]2の加算A＋B を、筆算で考える。（便宜上、以下、符号なし2 進数を用いている。しかし、たとえ符号つきであっても、得られる回路は同じである。） A_k-1 A₀ B₀ A₀+B₀ C₁+A₁+B₁ A₁ B₁ C₂+A₂+B₂ Carry A₂ B₂ A_k-2 B_k-1 B_k-2 … … S₀ S₁ S₂ S_k-2 S_k-1 + … … C_k-2+A_k-2+B_k-2 C_k-1+A_k-1+B_k-1 Carry Sum Sum Sum 2つの1bitの 加算（半加算） 3つの1bitの 加算（全加算）・0 桁目は A0＋B0、すなわち2 つの 1bit の加算になる。これを半加算という。0 桁目の和(Sum)は S0となる。桁上がり(Carry)が 1 桁目に C1として繰り上がる。・1 桁目以降の i 桁目では Ci＋Ai＋Bi、すなわち3 つの 1bit の加算となる。これを全加算という。ここでもSum が Siとなり、Ci＋1がi＋1 桁目に繰り上がる。

4.3.2. 半加算器(HA: half adder)** ・半加算A＋B の真理値表は、 A B C＋ (＝Carry) S (＝Sum) 0 0 0 1 1 0 1 1 C＋＝ S＝・半加算器の回路は、・ところで、 C＋＝ S＝と表現することもできる。・この講義では半加算器の記号（シンボル）を、以下で表現する。

A

B

AB

HA

CS+

S(=A

C

+

(=AB)

⊕B)

4.3.3. 全加算器(FA: full adder)** ・全加算C＋A＋B の真理値表は、 C A B C＋ (＝Carry) S (＝Sum) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 ・C＋のカルノー図は、 C＋ C AB 0 1 00 01 11 10 C＋＝・S のカルノー図は、 S C AB 0 1 00 01 11 10 S＝

(25)

・結局、全加算器の回路は、

A

B

C

₊

S

・また真理値表から、 ¯¯

C+＝¯A·¯B·C＋¯A·B·¯C＋A·¯B·¯C＋¯A·¯B·¯C

なので C B A C B A C B A C B A C₊= ⋅ ⋅ + ⋅ ⋅ + ⋅ ⋅ + ⋅ ⋅ となり、3 入力 NAND3 個を C＋とS で共用できる。・ところで、

(

)

C ) B A ( AB )C B A B A ( ABC AB AB)C B A B A ( AB C )B A (A ) B A(B AB C B) (A AB CA BC AB C C ) B A ( C ) B A ( C B) (A C ) B A B A ( C ) B A B A ( C B A C B A C B A C B A S ⊕ + = + + + = + + + = + + + + = + + = + + = ⊕ ⊕ = ⋅ ⊕ + ⋅ ⊕ = ⋅ ⋅ + ⋅ + ⋅ ⋅ + ⋅ = ⋅ ⋅ + ⋅ ⋅ + ⋅ ⋅ + ⋅ ⋅ = + と変形でき、全加算器は半加算器 2 個と 2 入力 OR で構成できる。・この講義では全加算器の記号を、以下で表現する。

A

B

AB

FA

CS+

C

₊

(=AB+BC+CA)

S(=A

⊕B⊕C)

4.3.4. リップルキャリーアダー* ・符号なしk 桁 2 進数の加算器は 1 個の半加算器と k－1 個の全加算器で構成できる。この加算器はさざなみ（リップル）のように桁上がりが伝播する方式であり、リップルキャリーアダーと呼ばれる。・またk 個全て、全加算器を用いてもよい。 4.3.5. 減算器* ・符号なしk 桁 2 進数 A＝[Ak－1 Ak－2 … A2 A1 A0]2と B＝[Bk－1 Bk－2 … B2 B1 B0]2の減算A－B を考える。B の2 の補数は[¯¯¯¯Bk－1 ¯¯¯¯Bk－2 … ¯¯B2 ¯¯B1 ¯¯B0]2＋1 なので、筆算は以下のようになる。

(26)

A_k-1 A₀ B₀ 1+A₀+B₀ C₁+A₁+B₁ A₁ B₁ C₂+A₂+B₂ Carry A₂ B₂ A_k-2 B_k-1 B_k-2 … … S₀ S₁ S₂ S_k-2 S_k-1 + … … C_k-2+A_k-2+B_k-2 C_k-1+A_k-1+B_k-1 Carry Sum Sum Sum 1 ・すなわち、減算器はk 個の全加算器と k 個の NOT で構成できる。 4.3.6. エンコーダ（2k_入力・_{k 出力）} ・あるキーとたたくと、ASCII コードが出るような、キーボードに代表される動作。・2 進数（コード）に対応した番号を持つ入力に、1 が入ると、そのコードを出力する。例えばA3、A2、 A1、A0の4 入力と Y1、Y0の2 出力を持つ 4 入力・2 出力エンコーダでは、A2＝1 のときには、[Y1 Y0]2＝2 となる。このとき、一般には、Ai＝0 (i≠2)とし、組

み合わせ禁止にする。すなわち、A3、A2、A1、A0の

4 入力のうちの 1 つのみが、必ず 1 となることを前提とする。真理値表は、 A3 A2 A1 A0 Y1 Y0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 ・Y0のカルノー図は、 Y0 A1A0 A3A2 00 01 11 10 00 01 11 10 Y0＝・Y1のカルノー図は、 Y1 A1A0 A3A2 00 01 11 10 00 01 11 10 Y1＝A3＋A2 ・結局、4 入力・2 出力エンコーダの回路は、

(27)

4.3.7. プライオリティエンコーダ ・上記エンコーダから、組み合わせ禁止の前提をなくしたもの。入力が 1 であるビットのうち、最大の番号に対応するコードを出力する。例えばA3＝A2＝1 のときには、[Y1 Y0]2＝3 となる。真理値表は、 A3 A2 A1 A0 Y1 Y0 N 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0 ・Y0のカルノー図は、 Y0 A1A0 A3A2 00 01 11 10 00 01 11 10 Y0＝・Y1のカルノー図は、 Y1 A1A0 A3A2 00 01 11 10 00 01 11 10 Y1＝・なお真理値表から、N＝¯¯A3·¯¯A2·¯¯A1·¯¯A0である。N はいずれの入力にも1 がないことを示し、[A3 A2 A1 A0]2 ＝0 と[A3 A2 A1 A0]2＝1 を区別するために用いる。・結局、4 入力・2 出力プライオリティエンコーダの回路は、 4.3.8. デコーダ（k 入力・2k_出力）_* ・エンコーダと逆の動作。CPU の命令解読（回路選択）などに使われている。入力コードに対応した番号を持つ出力を、1 とする。例えばA2、A1、A0の3 入力と Y7、Y6、Y5、Y4、Y3、 Y2、Y1、Y0の8 出力を持つ、3 入力・8 出力デコーダでは、[A2 A1 A0]2＝5 のときには、Y5＝1 となる。このとき、Yi＝0 (i≠5)である。真理値表は、 A2 A1 A0 Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Y0＝ Y1＝ Y2＝ Y3＝ Y4＝ Y5＝ Y6＝

(28)

7

0

1

2

A

₃

0

1

2

3 S

₀

Y

Y＝・各項の¯¯S1･¯¯S0、¯¯S1･S0、S1･¯¯S0、S1･S0は、S1と S0を入力とした2 入力・4 出力デコーダの出力そのものであるので、以下でも構成できる。

(29)

4.3.10. デマルチプレクサ* ・マルチプレクサとは逆の動作。複数の出力のうちの1 つに、入力を分配する。入力 S、A と出力 Y1、 Y0を持つ2 出力デマルチプレクサは、入力 S の値によって、出力Y1またはY0のどちらかに、入力A を分配する。入力A が分配されない出力は 0 とする。すなわち、S＝0 のとき、Y0＝A (Y1＝0)となる。S＝1 のとき、Y1＝A (Y0＝0)となる。真理値表は、 S A Y1 (S＝1 ⇒ Y1＝A) Y0 (S＝0 ⇒ Y0＝A) 0 0 0 1 1 0 1 1 Y0＝ Y1＝・2 出力デマルチプレクサの回路は、・この講義では 2 出力デマルチプレクサの記号を、以下で表現する。

0

1 S

0

1

2

3 S

₀

A

Y0＝ Y1＝ Y2＝ Y3＝・各式の¯¯S1･¯¯S0、¯¯S1･S0、S1･¯¯S0、S1･S0は、S1と S0を入力とした2 入力・4 出力デコーダの出力そのものであるので、以下でも構成できる。・またA＝1 ならば、デマルチプレクサはデコーダとして動作する。

(30)

(31)

Q=0

Q=1

!

S=1

R=0

!

S=0

R=0

Q=0

Q=1

Q=0

!

Q=1

!

Q=0

Q=1

S=0

R=0

!

S=1

R=0

!

S=0

R=0

5.3.6. リセット（S＝0、R＝1） S＝0、R＝1 にすると、Q＝0（リセット）になる。

Q=1

S=0

R=0

Q=0

Q=1

!

Q=0

!

!Q=1

Q=0

!

S=0

R=1

!

S=0

R=0

Q=0

Q=1

!

Q=0

!

Q=1

Q=0

S=0

R=0

!

S=0

R=1

!

S=0

R=0

5.3.7. 入力禁止（S＝R＝1） 5.3.8. 動作波形（タイミングチャート）**

Q

R

S

(32)

5.3.9. NAND型への変形 5.4. ゲートつきSRラッチ SRラッチにゲート入力Gを追加し、・G＝0 ⇒ 直前の状態を保持・G＝1 ⇒ SRラッチと同様の動作となる。Gのレベル（値）に応じて動作するラッチ。 5.4.1. 回路

G

S

Q

R

S’

R’

・G＝0 ⇒ S’＝R’＝1 ⇒ 双安定

S’=1

Q

R’=1

＝双安定・G＝1 ⇒ SRラッチ

Q

S

R

＝ SRラッチ 5.4.2. 特性表 G S R Q 0 0 0 Q－（Qの直前の状態を保持） 0 0 1 Q－（Qの直前の状態を保持） 0 1 0 Q－（Qの直前の状態を保持） 0 1 1 Q－（Qの直前の状態を保持） 1 0 0 Q－（Qの直前の状態を保持） 1 0 1 0（リセット） 1 1 0 1（セット） 1 1 1 X（入力禁止） 5.4.3. 記号

Q

S Q

R

G

5.4.4. 動作波形

Q

R

S

G

Q

5.5. D（データ）ラッチ ゲートつきSRラッチの変形。S＝D、R＝¯Dとする。 5.5.1. 回路

G

D

Q

5.5.2. （わかりにくい）特性表 G D Q 0 0 Q－（＝D－：G＝0 になる直前のDの値） 0 1 Q－（＝D－：G＝0 になる直前のDの値） 1 0 0（＝D） 1 1 1（＝D） 5.5.3. 記号*

Q

D Q

G

5.5.4. 動作波形**

Q

D

G

Q

・（わかりやすい）特性表を、こう書くこともある**。 G D Q 0 0（＝D－：Gが立下がる直前のDの値） 1 1（＝D－：Gが立下がる直前のDの値） 1 0 0（＝D） 1 1 1（＝D）

(33)

5.6. Dフリップフロップ Dラッチをカスケード接続（マスター・スレイブ構成）したもの。 5.6.1. 回路

Q

D Q

G

Q

D Q

G Q

Q

D Q

G

CK

D

Q

P

5.6.2. （わかりにくい）特性表 CK D P Q 0 0 0 Q－（Qの直前の状態を保持） 0 1 1 Q－（Qの直前の状態を保持） 1 0 P－（＝D－：CK＝1 になる直前のDの値） P（＝P－＝D－：CK＝1 になる直前のDの値） 1 1 P－（＝D－：CK＝1 になる直前のDの値） P（＝P－＝D－：CK＝1 になる直前のDの値） 5.6.3. 記号*

Q

D Q

“>”はクロック入力（CK）を示す。¯Q出力がない場合の記号は、以下のとおり。

D Q

5.6.4. 動作波形**

CK

D

P

Q

・（わかりやすい）特性表を、こう書くこともある**。 CK D Q 0 0（＝D－：CKが立上がる直前のDの値） 1 1（＝D－：CKが立上がる直前のDの値）

(34)

例題１：シフトレジスタ* Dフリップフロップを以下のように多段接続し、入力Dを与えたときの動作波形を描け。ただし初期値として、 Q0＝Q1＝Q2＝Q3＝0 とする。

Q

₀

CK

D

_{D Q}

Q

1

_{D Q}

Q

2

_{D Q}

Q

3

CK

D

Q

₀

Q

₁

Q

₂

Q

3 このように1 クロックずつ、波形が遅れる機能を持つ回路をシフトレジスタという。例題２：T（トグル）フリップフロップ* Dフリップフロップを以下のように接続したときの、動作波形を描け。ただし初期値として、Q＝0 とする。

Q

D Q

CK

Q

または

CK

D Q

Q

CK

Q

QはCKの周波数を半分にしたものであり、一般に、周波数を半分にする回路を分周器という。また、出力がクロック入力に同期して反転することをトグルといい、フリップフロップで実装したこの回路をT（トグル）フリップフロップという。 5.7. T（トグル）フリップフロップ Tフリップフロップは、クロック入力Tの半分の周波数を、Qから出力する。・特性表と記号 T Q ¯¯ Q－（反転）

Q

T

または

Q

T

5.8. JKフリップフロップ^ その他のフリップフロップの１つに、JKフリップフロップがある。・特性表と記号 CK J（セットに対応） K（リセットに対応） Q 0 0 Q－（保持） 0 1 0（リセット） 1 0 1（セット） 1 1 Q¯¯－（反転）

Q

J Q

K

(35)

6. 順序回路 出力が、現時点の変数入力と、過去の状態に依存する論理回路。すなわち、過去の状態を記憶する回路（記憶回路：ラッチ、フリップフロップ）が含まれる。 6.1. モデル 6.1.1. 組み合わせ論理回路のモデル 現時点での入力のみによって、出力が決まる。

組み合わせ

論理回路

入力

A

出力

Y

6.1.2. 順序回路のモデル（ミーリー型モデル） 現時点での入力＋過去の状態で、出力と次の状態が決まる。

組み合わせ

論理回路

入力

A

出力

Y

記憶回路

過去の

状態

S

6.2. 同期式順序回路 同期式順序回路とは、クロックに同期して、出力が変化する順序回路。D フリップフロップを記憶回路として用いれば、同期式順序回路を構成できる。この講義では、非同期式順序回路については触れない。 6.2.1. 同期式順序回路モデル（ミーリー型モデル）*

組み合わせ

論理回路

入力

A

出力

Y

現在の

記憶状態

S

(t)

D Q

S

(t+1)

CK

S

(t)

次の（

1クロック後の）

記憶状態

S

(t+1) 具体的な回路図で書くと、以下のとおり。

(36)

0/0

A/Y

0/0

この場合，状態数は4 であり，2 個の D フリップフロップが必要である。 6.3.2. 状態遷移表** 状態遷移図を表に書下したもの。現在の状態S(t)_{次の状態 S}(t+1)_{出力 Y} 入力A 入力A 0 1 0 1 S0 S0 S1 0 0 S1 S1 S2 0 1 S2 S2 S3 0 1 S3 S3 S0 0 1 6.3.3. 状態変数 次に、状態に固有の変数を割り当てる。k ビットの変数で、2k_{状態まで表現できる。} S0、S1、S2、S3は4 状態であり、2 ビット（2 つの D フリップフロップ）で表現できる。どの状態に、[00]2、 [01]2、[10]2、[11]2を割り当てるかは、一般に任意であるが、割り当て方によって、回路規模は異なる。ここでは、S0＝[00]2、S1＝[01]2、S2＝[11]2、S3＝[10]2 とすると、状態遷移表は以下となる現在の状態S(t)_{次の状態 S}(t+1)_{出力 Y} 入力A 入力A 0 1 0 1 S0:00 S0:00 S1:01 0 0 S1:01 S1:01 S2:11 0 1 S2:11 S2:11 S3:10 0 1 S3:10 S3:10 S0:00 0 1 6.3.4. 回路化** S(t)_＝[Q 1(t) Q0(t)]2、S(t+1)＝[Q1(t+1) Q0(t+1)]2とする。・Q1(t+1)のカルノー図は、以下で与えられる。 Q1(t+1) A Q1(t)Q0(t) 0 1 00 0 0 01 0 1 11 1 1 10 1 0 Q1(t+1)＝Q1(t)A＋Q¯ 0(t)A ・Q0(t+1)のカルノー図は、以下で与えられる。 Q0(t+1) A Q1(t)Q0(t) 0 1 00 0 1 01 1 1 11 1 0 10 0 0 Q0(t+1)＝Q

¯¯

1(t)A＋Q0(t)A ¯ ・Y のカルノー図は、以下で与えられる。 Y A Q1(t)Q0(t) 0 1 00 0 0 01 0 1 11 0 1 10 0 1 Y＝(Q1(t)＋Q0(t))A ・結局、回路は以下のようになる。

(37)

・例題1 クロック入力 CK に同期して、記憶している値を 1 ずつ増やす回路をアップカウンタという。入力A が A＝0 のときには、出力 Y＝[Y1Y0]は[00]→[01]→[10] →[11]…とカウントアップし、A＝1 のときには、ホールド（出力そのまま）するカウンタを設計せよ。状態遷移図：

S

₃

[11]

S

₀

[00]

S

₁

[01]

S

₂

[10]

0/01

0/11

0/00

0/10

1/00

1/01

1/10

1/11

A/Y

₁

Y

₀ 状態遷移図： Q1(t)Q0(t) Q1(t+1)Q0(t+1) Y1Y0 A A 0 1 0 1 S0:00 S1:01 S0:00 00 00 S1:01 S2:10 S1:01 01 01 S2:10 S3:11 S2:10 10 10 S3:11 S0:00 S3:11 11 11 Q1(t+1)のカルノー図： Q1(t+1) A Q1(t)Q0(t) 0 1 00 0 0 01 1 0 11 0 1 10 1 1 Q0(t+1)のカルノー図： Q0(t+1) A Q1(t)Q0(t) 0 1 00 1 0 01 0 1 11 0 1 10 1 0 結局、回路は以下のようになる。

(38)

・例題2 クロック入力CK に同期して、出力 Y＝[Y1Y0]を[01] →[01]→[10]→[11]…とカウントアップする回路を設計せよ。状態遷移図：

S

₃

[11]

S

₀

[00]

S

₁

[01]

S

₂

[10]

X/01

X/11

X/01

X/10

入力なし

/Y

₁

Y

₀ 状態遷移図： Q1(t)Q0(t) Q1(t+1)Q0(t+1) Y1Y0 S0:00 S1:01 01 S1:01 S2:10 01 S2:10 S3:11 10 S3:11 S0:00 11 結局、回路は以下のようになる。・例題3 以下の状態遷移図を有する順序回路を示せ。状態遷移図：

S

₀

[0]

S

₁