このスライドは以下の URL からダウンロード可能です 2

計算機学

計算機学

伊藤彰則

aito@spcom.ecei.tohoku.ac.jp

このスライドは以下のURLからダウンロード可能です

参考書の紹介

● 計算機学入門　デジタル世界の原理を学ぶ 阿曽弘具著　共立出版　￥_2,900 以前教科書だった本の改訂版。講義の内容と一致しており、説明は詳しい。 ● CPUの創りかた　渡波郁著　 毎日コミュニケーションズ￥_2,940 個人的おすすめだが講義の前半部分しかカバーしていない。 ● ソフトウェアの20世紀　長谷川裕行著 翔泳社　￥_2,400 コンピュータとソフトウェアの歴史。講義と直接の関連はないが面白い。 ● コンピュータはなぜ動くのか　矢沢久雄著　

講義の流れ

(1)

● イントロダクション（今回） – _{コンピュータの歴史} – _{2進法・8進法・16進法} ● ハードウェアの原理 – _{論理関数と論理回路} – _{論理関数の簡単化} ● 論理関数の数学 – _{ブール代数と代数系}

講義の流れ

(2)

● ソフトウェアの原理 – _{CPUと機械語} – _{アセンブリ言語と高級言語} – _{データ構造とその操作} – _{計算のモデルと計算量} ● 試験

計算機（コンピュータ）とは何か

● 誰が何のために作ったのか。

● 計算機とは(原理的に)何なのか。

● 現在どのように使われているのか。

誰が：計算機をめぐる年表

● 17世紀 – _{ブレース・パスカル} (1623-1662) ● 考える葦の人 ● 世界で初めて「計算機」 (calculator)を試作

誰が：計算機をめぐる年表

● 17世紀 – _{ゴットフリート･ウィルヘルム・フォン・} ライプニッツ (1646-1716) ● 2進法の発明者 ● ｢自動的に真なる概念を導くための計 算方法｣を研究 ● 計算機も試作 ● ニュートンとは永遠のライバル

誰が：計算機をめぐる年表

● 19世紀 – _{チャールズ・バッベジ} (1791-1871) ● 2つの自動計算機械を設計 – _{階差機関(Difference Engine)} – _{解析機関(Analytical Engine)} ● でも完成しなかった…

Babbageの解析機関

● 世界初の機械式計算機 – _{加減乗除算} – _{あらかじめ決められた順序で} 計算する – _{結果の印字}

誰が：計算機をめぐる年表

● 世界初のプログラマ(Translator) – _{エイダ・オーガスタ・} ラブレス公爵夫人 (1815-1852) ● 詩人バイロンの娘 ● ド・モルガンに師事 ● チャールズ・バッベジを支援した ● 不遇な晩年

誰が：計算機をめぐる年表

● 20世紀 – _{アラン・チューリング(1912-1954)} ● 自動機械による証明についての理論的考察 ● 実際に計算をする「機械」を想定(チューリン グマシン) ● 計算の可能性についての理論を構築 ● 暗号解読器「コロッサス」の開発に参加 ● 不遇な晩年

誰が：計算機をめぐる年表

● 20世紀 – _{エッカート＆モークリー} (UPENN) ● 世界初の(実用化された)電子 式コンピュータENIACを開発 ● 弾道計算に特化した計算機

これが

ENIACだ

● 真空管17468本 ● コンデンサ10000 個 ● スイッチ6000個 ● ケーブルの接続 で実行を制御

何のために？

● 正しい推論のため（ライプニッツ)

● 数表を作るため（バッベジ)

● ｢計算｣とは何かを考えるため（チューリング)

原理的に何なのか？

● 計算モデル：原理的に何が計算できるかを考える ための数学モデル – _{コンピュータを抽象化したもの} – _{速度やメモリ容量などの制約を考えない} ● さまざまな計算モデル – _{チューリングマシン(TM)} – _{ランダムアクセスマシン(RAM)} – _{帰納的関数}

チューリングマシン

● 仮想的な計算機械 by Alan Turing 0 ; B A = 1 = A + 2 ; F 状態 ヘッド

ランダムアクセスマシン

● 現在のコンピュータに近い – _{計算部とメモリがある} – _{メモリは必要に応じていくらでも大きい} – _{どのメモリにアクセス（読み書き）するときにもかかる時} 間は同じ（ランダムアクセス） 無限に大きいメモリ 計算部 12312番目のメモリの値と

現在どのように使われているのか？

● 汎用の何でも機械として。 – _電話。 – _{ごはんの炊け具合を監視する。} – _{お部屋の温度をいい具合に調節する。} – _{大きいお友達のゲーム。} – _{テレビを録画する。あるいはテレビそのもの。}

どのようにして実現されるのか？

コンピュータの実現のための階層

ソフトウェア アプリケーション _{MS-Wordとか}

プログラミング言語 _{C, C++, Java, Ruby, Python, ...}

OS Windows, MacOS, iOS, Linux, Android, ... ハードウェア _{CPU IA32, x86-64, ARM, MIPS, PowerPC, PIC, ...}

論理回路 機能ブロック レジスタ、ALU、メモリ、... 論理ゲート _{AND, OR, NOT, ...}

この講義では何をするのか

1.計算機の動作原理を理解するための論理回路の 理解（主に組み合わせ論理回路）。 (進んだ内容は「ディジタルコンピューティング」の範疇) 2.それに伴う論理演算・論理関数の理解。 3.計算機のネイティブな動作（機械語_{)の理解。} 4.抽象的な計算機としての計算モデルの理解と、計 算量についての初歩的な理解。

あらゆる計算が１と０で実現できる

● 10進法の数字⇔2進法の数字（１と０） ● 文字⇔数字 ● 文字列⇔数字列＝数字 ● 画像⇔数字 ● 音声⇔数字 ● その他のデータ⇔数字

計算機が行うすべての処理は

10進法、2進法、8進法、16進法

１０進 ２進 ８進 １６進 １０進 ２進 ８進 １６進 0 0 0 0 8 1000 10 8 1 1 1 1 9 1001 11 9 2 10 2 2 10 1010 12 A 3 11 3 3 11 1011 13 B 4 100 4 4 12 1100 14 C 5 101 5 5 13 1101 15 D 6 110 6 6 14 1110 16 E 7 111 7 7 15 1111 17 F

10進・2進・16進数の変換

● 例題 – 108₍₁₀₎を２進法で表せ。 ● 解答 – _{ある数xを２進数で表したとき、それが偶数ならば下１桁} は_{0、奇数ならば1になる。したがって2で割った余りを計} 算すれば、_{2進数の最下桁が求まる。以下同様。} ) 2 108 ...0 2 54 ...0 2 27 ...1) )

10進・2進・16進数の変換

● 例題 – 110010₍₂₎を10進法で表せ。 ● 解答 – _{2進数のn桁目だけが1である数は2}n-1_である。 したがって･･･ 110010 = 10 + 10000 2 1 _{= 2} 24 _{= 16} 2+16+32=50

10進・2進・16進数の変換

● 例題 – 10110110010₍₂₎を16進法で表せ。 ● 解答 – _{16進数の1桁は2進数の4桁にそのまま対応する。ただ} し下から割り当てていく。

10110110010

2

B

5

5B2

演習

● 次の2進数を8進数と16進数で表せ。

　

　

0010 0100 0010 0110

● 次の10進数を2進数と16進数で表せ。

2進数の演算

● 加算 0+0=0, 0+1=1+0=1, 1+1=10 ● 減算　 0-0=0, 0-1=-1, 1-0=1, 1-1=0 ● 乗算　 0×0=0×1=1×0=0, 1×1=1, 1×10=10×1=10, 10×10=100, 10×11=11×10=110,...

これらは「算術演算」と呼ばれる

２進数の演算

● どんなデータも０と１で表せる →すべての計算は０１の列に対する関数で表現で きる ● 例 f _{(0101...)=001011....} f ₍₀₀₎₌₀ f ₍₀₁₎₌₁ f ₍₁₀₎₌₁ f ₍₁₁₎₌₁ 入力の桁数が有限ならば入力 のパターンも有限 すべての入力に対して出力を

基本的な論理関数（論理演算）

● AND演算（論理積） ● OR演算（論理和） 0_⋅0=0 0_⋅1=0 1_⋅0=0 1_⋅1=1

x

_{⋅y , x y , x∧ y}

2つの引数の両方が１の場合だけ１

x

_{+ y , x∨ y}

0_{+ 0=0} 0_{+ 1=1 2つの引数の両方が0の場合だけ0}

基本的な論理関数（論理演算）

● NOT演算（否定） ● XOR演算（排他的論理和） ̄0=1 ̄1=0

̄x , ¬x

x

_{⊕ y , x∨ y}

0_⊕0=0 0_⊕1=1 1_⊕0=1

~

2つの引数が異なる場合だけ1 実は_{AND,OR,NOTで作れる}

組み合わせて作れる論理演算

● NAND演算 ● NOR演算

x y

x

_{+ y}

0_{+ 0=1} 0_{+ 1=0} 0_⋅0=1 0_⋅1=1 1_⋅0=1 1_⋅1=0

論理演算の基本的性質

● 交換則（交換律）

● 結合則（結合律）

● 分配則（分配律）

● ド・モルガン則（ド・モルガン律）

x_{⋅y= y⋅x x+ y= y+x}

x_{⋅( y⋅z)=(x⋅y)⋅z} x_{+ ( y+ z)=(x+ y)+ z}

x_{⋅( y+ z)=(x⋅y)+ ( x⋅z)} x_{+ ( y⋅z)=( x+ y)⋅(x+ z)}

論理演算の記述の優先順位

● 通常はAND演算をOR演算より優先して書く

（算術演算の記述法と同じ）

● 紛らわしい場合はカッコを使う

論理関数（論理演算）は何種類あるか

● 論理関数の引数の数を固定する →入力、出力ともに有限のパターンしかないので、 　　論理関数は有限個しかない ● 例：１変数論理関数は４種類 f ₀₍₀₎₌₀ f ₀₍₁₎₌₀ f _0(x)=0 f ₁₍₀₎₌₀ f ₁₍₁₎₌₁ f _1(x)=x f ₂₍₀₎₌₁ f ₂₍₁₎₌₀ f _2(x)=̄x f ₃₍₀₎₌₁ f ₃₍₁₎₌₁ f _{3( x)=1}

論理関数（論理演算）は何種類あるか

● n変数関数の場合、入力のパターンは2n通り

● それぞれに対して、出力のパターンは0か1

入出力のパターン数＝

2

2

真理値表

● すべての入力パターンに対して出力を定義すれば 論理関数が定義できる →表にするとわかりやすい

真理値表

(truth table)

x y x+y 0 0 0 0 1 1 1 0 1 x y x·y 0 0 0 0 1 0 1 0 0 x x 0 1 1 0

AND

OR

NOT

真理値表

● 注意事項 – _{引数（入力）のパターンは、その並びを２進数と見たとき} に「だんだん増えていく」順番に記述するのが普通 – _{対応関係が同じでも、思いついた順番に並べるのはよ} くない！ x y x·y 0 0 0 1 1 1 x y x·y 0 0 0 0 1 0 GOOD

真理値表による証明

● 真理値表によってド・モルガン則を確かめてみよ

う。

x y x y x·y x+y x·y x+y x·y x+y

0 0 1 1 0 0 1 1 1 1

0 1 1 0 0 1 1 0 0 1

1 0 0 1 0 1 1 0 0 1

基本論理演算と論理関数

● AND, OR, NOT演算の組み合わせだけでどんな

論理関数でも作ることができる。 ● 証明：引数の数に関する数学的帰納法 – _{引数１つの時} ● 引数１つの論理関数は前述の通り４種類しかない。 f _{0( x)=0=x⋅̄x} f _1(x)=x f _{( x)=̄x}

成立

基本論理演算と論理関数

– _{引数n個のとき、引数n-1個では成立を仮定} ● 任意のn変数論理関数 – _{次のn-1変数論理関数を考える} – _{ここで次の式を考える：「x=0ならa、x=1ならb」} f _(x1 , x₂ ,_{…, xn)} g₀( x₁ , x₂ ,… , x_n−1)= f (x₁ ,…, x_n−1 ,0) g_{1( x1} , x₂ ,_{… , xn−1)= f ( x1} ,_{…, xn−1} ,1₎ ̄x a+ x b x a b xa xb xa+ab 1 0 0 0 0 0 1 0 1 0 1 1 x a b xa xb xa+ab 0 0 0 0 0 0 0 0 1 0 0 0

基本論理演算と論理関数

● x_nの値によって関数を切り替える – x_n=0 ⇒ – x_n=1 ⇒ ● 前ページの考察により、 ● 仮定よりg 0とg1はAND,OR,NOTのみで表せるの f ( x₁,… , x_n−1, x_n)=g₀( x₁ ,…, x_n−1) f _{( x1},_{… , xn−1}, x_{n)=g1( x1} ,_{… , xn−1)} f ( x₁ ,… , x_n−1 , x_n)=x_n g₀( x₁ ,… , x_n−1)+ x_n g_{1( x1},_{… , xn−1)}

演習

● 分配律が成立していることを真理値表で確かめ

よ。

x_{⋅( y+ z)=( x⋅y)+ ( x⋅z)} x_{+ ( y⋅z)=(x+ y)⋅(x+ z)}

x y z xy xz y+z x(y+z) xy+xz

0 0 0 0 0 0 0 0

論理演算と論理素子

● ある論理演算を実現するための電子回路 （論理ゲート） ANDゲート ORゲート NOTゲート

MIL記号

論理演算と論理素子

● ゲートの端にある○が「反転」を表す

NANDゲート NORゲート NOTゲート

等価な論理ゲート

● ド・モルガン律などによる ＝ A B B

NANDゲートは万能

● NANDゲートですべてのゲートの代用ができる ＝ ＝ ＝ x_⋅x=̄x x_⋅y=x⋅y

NANDゲートの実現例

● Diode-Transistor Logic (DTL) – _{簡略化した回路図（実際はもう少し複雑）} – _{DTLは遅くて消費電力が大きいので、実際にはあまり} 使われない V+ V+ V+ V+ V+ V+ H L L H

半導体でなくても論理ゲートは作れる

● リレーで作る論理ゲート

コイルに電流を流すと隣にある

スイッチが_ON/OFF

論理演算と論理回路

● 論理式⇔論理回路 ● 例

Z

= ABBCCA

A B C Z

演習

● 次の論理式に基づく論理回路を描け。

S

_{= X⋅Y  X⋅Y}

C

_{= X⋅Y}

?

X Y C S

半加算器

● さっきの論理式の真理値表 X Y C S 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 X, Yを１桁の２進数、CSを２桁の２進数と見 C: Carry （桁上げ） S: Sum （和）

桁の多い加算

● ２桁以上の２進数の加算をするにはどうする？ – _{桁上げを考慮⇒３つの２進数の和を計算しなければな} らない – _{３つの１桁の２進数 a,b,cを加算→２桁の２進数CS} a b c C S 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0

全加算器

(full adder)

発展

● 前ページの回路の入出力関係がその前の真理値 表と同じになっていることを確かめよう ● ２ページ前の真理値表を直接表現する論理式を考 えてみよう C_{= f (a , b , c)} S_{=g (a ,b , c)}

桁の多い加算器

● 筆算と同じ要領（下から順に桁上げ）

1111

+1111

---10000

1 1 1 1

論理関数の設計

● これまでは論理式から論理回路を描いていた ● 本当にやりたいこと – _{要求仕様（欲しい入出力関係）を実現する論理回路} ● やるべきこと – _{要求仕様（真理値表）→論理式（関数）→論理回路} ● 問題点 – _{どうやって真理値表を満たす論理式を作るか} – _{真理値表を満たす論理式は１つではない} どういう論理式を作ればいいか

真理値表から論理関数へ

● 次の真理値表で表される論理式（論理関数）は？ x y z f(x,y,z) 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1

真理値表から論理関数へ

● 次の真理値表で表される論理式（論理関数）は？ x y z f(x,y,z) 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1

答えは唯一ではない

f _{=̄x y ̄z+ x ̄y z+ x y ̄z} f _{= (x+ y+ z)( x+ y+ ̄z)} (x+ ̄y+ ̄z)(̄x+ y+ z) (̄x+ ̄y+ ̄z) f _{= y ̄z+ x ̄y z}

真理値表から論理関数へ

● 論理関数への変換の考え方 – _{できるだけ機械的に変換できたほうがいい} ● 真理値表から標準形論理式への変換 – _{できるだけ論理演算が少ないほうがいい} ● 論理回路として実現した時の素子数が少ない – _{低コスト、高速} ● 演算数が最小の論理式：最簡形論理式 ● 最簡形論理式の導出 – カルノー図 – _{クワイン・マクラスキ法}

基礎的な概念

● 基本的に積和形（論理積の論理和）で考える ● リテラル：変数または変数の否定 ̄y z+ x y ̄z リテラル ̄y z+ x y ̄z リテラル リテラル 項（積項）

標準形論理式

● 積和標準形（主加法標準形） Sum-of-product – _{リテラルの論理積の論理和} – _{すべての項がすべての変数を含む} – _{同じ項は１回しか出てこない} – _{積和標準形の例} – _{積和標準形でない例} f _{( x , y , z)=̄x ̄y z+ x ̄y z+ x y ̄z} f _{( x , y , z)=̄y z+ x ȳz}

標準形論理式

● 和積標準形（主乗法標準形） Product-of-sum – _{リテラルの論理和の論理積} – _{すべての論理和がすべての変数を含む} – _{同じ論理和は１回しか出てこない} – _{和積標準形の例} – _{和積標準形でない例} f _{( x , y , z)=( x+ y+ z)(x+ y+ ̄z)(̄x+ y+ z)} f _{( x , y , z)=( x+ z)(̄x+ y+ z)} f _{( x , y , z)=( x+ z)(̄x y+ z)}

2つの標準形の関係

● どんな論理式でも、積和標準形と和積標準形の両 表で表現できる。 – _{証明（変数の数による数学的帰納法）} ● 1変数の場合は自明 ● k変数の場合に成立を仮定。 任意の_{k+1変数論理関数を考える} 次の_{k変数関数を考える} f _(x1 , x₂ ,_{…, xk+ 1)} g0_(x1 ,_{…, xk)= f ( x1} , x₂ ,_{…, xk} , 0₎ g1_{( x} ,_{…, x )= f (x} , x ,_{…, x} ,1₎

2つの標準形の関係

● gをそれぞれ積和と和積標準形で表した論理式 ● 以前と同じ議論により、 g0_{( x1} ,_{…, xk)→ gSOP}0 _{( x1} ,_{…, xk), g}0_{POS (x1} ,_{…, xk)} g1_(x1 ,_{…, xk)→ g}1_{SOP( x1} ,_{…, xk) , g}1_{POS (x1} ,_{…, xk)} f _(x1, x₂ ,_{…, xk} , x_{k+ 1)=xk+ 1} g0_{( x1} ,_{…, xk)+ xk+ 1} g1_{( x1} ,_{…, xk)} =x_{k+ 1} g0_SOP( x₁ ,…, x_k)+ x_{k+ 1} g1_SOP( x₁ ,…, x_k) これを分配律によって展開すれば、_{fも積和標準形で表} せる。

2つの標準形の関係

● 和積標準形の場合、まず次の関係を考える

x=0ならa、x=1ならbとなる論理式

● したがって

(x+ a)(̄x+ b)

x_{=0 →( x+ a)(̄x+ b)=(0+ a)(1+ b)=a⋅1=a} x_{=1 →( x+ a)(̄x+ b)=(1+ a)(0+ b)=1⋅b=b} f _{( x1}, x₂ ,_{…, xk} , x_{k+ 1)=( xk+ 1+ g}0_{( x1} ,_{…, xk))( xk+ 1+ g}1_(x1,_{…, xk))} =( xk_{+ 1}+ gPOS 0 ( x1,…, xk))( xk_{+ 1}+ gPOS 1 ( x1,…, xk)) これを分配律によって展開すれば、_{fも和積標準形で表} せる。

標準形論理式と論理回路設計

● ある標準形は、１つの仕様（真理値表）に対して基 本的に_{1つしか存在しない} 真理値表 一対一 標準形 論理式 一対一 論理回路 x y f(x,y) 0 0 0 0 1 1 1 0 1 1 1 0 ̄x y+ x ̄y

真理値表から積和標準形へ

x y x・y x・y x・y x・y

0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 ● 最小項：すべての変数のリテラルを含む積項 ● ある入力の組み合わせの時だけ１になり、それ以外の組み合わせでは0になる。 x y f(x,y) 0 0 0 0 1 1 1 0 1 1 1 0 実現したい真理値表のうち、１になる組み合わせの最小項だけを OR で つなぐと積和標準形になる。 f _{(x , y)=̄x y+ x ̄y}

真理値表から和積標準形へ

x y x+y x+y x+y x+y

0 0 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0 ● 最大項：すべての変数のリテラルを含む論理和 ● ある入力の組み合わせの時だけ0になり、それ以外の組み合わせでは1になる。 x y f(x,y) 0 0 0 0 1 1 1 0 1 1 1 0 実現したい真理値表のうち、0になる組み合わせの最大項だけを AND でつなぐと和積標準形になる。

演習

● 次の真理値表による論理関数を積和標準形と和 積標準形で表せ。 x y z f(x,y,z) 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1

論理式の簡単化

● 標準形で表現した論理式は一般に冗長 x y f(x,y) 0 0 0 0 1 1 1 0 1 1 1 1 ̄x y+ x ̄y+ x y x y

̄x y+ x ̄y+ x y=̄x y+ x ̄y+ x y+ x y =(̄x+ x) y+ x( y+ ̄y)=1⋅y+ x⋅1=x+ y

x y

基礎的な概念

● 論理関数の順序 – _{値の順序：0≤0, 0≤1, 1≤1} – _{論理関数の順序：f(x),g(x)について、} ∀x(f(x)≤g(x))↔f≤g – _{例：確かめてみよう} ● xy ≤ x ≤ x+y – （真理値表を書き、左辺が１のところが右辺でも必ず1になっているな らば≤が成立）

基礎的な概念

● 系 – _{論理関数a,b,c,dについて} ● a ≤ c, b ≤ d ならば a+b ≤ c+d ● a ≤ c, a ≤ d ならば a ≤ c+d ● a ≤ c, b ≤ c ならば a+b ≤ c

基礎的な概念

● 論理式 f の主項とは – _{リテラルの論理積 t のうち、次の条件を満たすもの} ● t ≤ f であり、 ● tからそれ以上リテラルを取り除くと t ≤ f でなくなる ● 例 x y z f x・y・z x・y x 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 1 1 f _{≤x ̄y ̄z} f _{≤x ̄y} f _≤x これが主項

主項と論理式

● ある論理式 f の主項を全部列挙し、その論理和を とれば、それは f と一致する。 – _{ただし一般には冗長} x y z f x・y x・z y・z 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 f _{= x y+ x ̄z+ y z=x ̄z+ y z}

必須主項

● ある論理式を構成するために必ず必要な主項 x y z f x・y x・z y・z 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0

f

_{=x y+ x ̄z+ y z=x ̄z+ y z}

必須 主項

最簡形論理式とは

● 次の条件を満たす論理式： – _{ある論理関数を実現する論理式のうち、} – _{積項の数が最小で、} – _{かつ式全体のリテラルの数が最小のもの} ● 論理式を簡単化するときの目標 ● 論理関数の仕様（真理値表）に対して最簡形が一 意に決まるとは限らない

最簡形を求めるには

● 次のような手順を踏む 1. 与えられた論理関数の主項をすべて求める 2. 求まった主項のなかの必須主項を調べる 3. すべての必須主項と、それ以外の主項のうちできるだ けリテラルの少ない主項を組み合わせて元の論理関数 を表現する ● これらの求め方でいくつかの方法がある ● カルノー図 ● クワイン・マクラスキ―法

最簡形を求める方法

● カルノー図　(Karnaugh map) – _{真理値表に似た表と四角形でできた図を使う} – _人間向き – _{変数の数はふつう4個ぐらいまで} ● クワイン・マクラスキ―法 (Quine-McClusky alg.) – _{文字列処理} – _{計算機向き（人間にはつらい）} – _{変数の数は多くてもよいが、変数が多いと時間がかか} る

カルノー図

● 2次元の真理値表をもとに主項を発見する ● 3変数(x,y,z)、４変数(x,y,z,w)の表の例 – _{0,1の並びに注意} xy\zw 00 01 11 10 00 01 11 xy\z 0 1 00 01 11

カルノー図

● カルノー図では積項は長方形になる xy\zw 00 01 11 10 00 01 11 10

z

y

x

カルノー図

● カルノー図は表の上下左右がつながっている xy\zw 00 01 11 10 00 01 11

y

w

カルノー図

● リテラルの多い積項の例 xy\zw 00 01 11 10 00 01 11 10

x・z

z・w

x・y・z・w

x・y・w

カルノー図による論理式の簡単化

●カルノー図の表を描き、目標となる論理式が１となる マス目に“１”を記入 ●“１”を囲む、できるだけ大きい長方形（＝主項）を探 す ● 辺の長さは２のn乗のみ ● 上下左右が連続していることを忘れずに ●すべての“１”をカバーする、できるだけ少ない数の、 できるだけ大きい長方形の組み合わせを探す

カルノー図の例

カルノー図の表を描き、目標となる論理式が１となる マス目に“１”を記入 xy\zw 00 01 11 10 00 1 1 1 01 1 1 11 1 1 10 1 1

カルノー図の例

“１”を囲む、できるだけ大きい長方形（＝主項）を探す – _{辺の長さは２のn乗のみ} – _{上下左右が連続していることを忘れずに} xy\zw 00 01 11 10 00 1 1 1 01 1 1 11 1 1 1 1

カルノー図の例

すべての“１”をカバーする、できるだけ少ない数の、 できるだけ大きい長方形の組み合わせを探す xy\zw 00 01 11 10 00 1 1 1 01 1 1 11 1 1 10 1 1 この２つは必須 ではない→大き いほうを選ぶ

カルノー図の例

その長方形の組み合わせに対応する論理式が最簡 形になっている xy\zw 00 01 11 10 00 1 1 1 01 1 1 11 1 1 1 1 使わない x w_{+ y w+ z w+ ̄x ̄y ̄w}

演習

● 次のカルノー図を使って最簡形論理式を求めよ。 xy\z 0 1 00 1 01 1 11 1 1 10 1 xy\zw 00 01 11 10 00 01 1 1 1 11 1 1 1 10 1 1 1

部分論理関数とカルノー図

● 入力のすべてのパターンを考えなくてよい場合 – _{例：7セグメントLEDに0～4の数字を表示} 0 1 2 3 4 5 6 LED エンコーダ x₁ x₂ x₃ b₀ b₆

部分論理関数とカルノー図

● b1～b6の真理値表 – _{下3行の入力は想定しなくてよい→部分論理関数} 0 1 2 3 4 5 ₆ x1 x2 x3 b0 b1 b2 b3 b4 b5 b6 0 0 0 1 1 1 1 1 1 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 0 1 N/A 1 1 0 N/A 1 1 1 N/A

部分論理関数とカルノー図

● b0の論理関数の設計 x1x2\x3 0 1 0 0 1 0 1 1 1 1 1 1 0 x1x2\x3 0 1 0 0 1 0 1 1 1 1 1 * * 1 0 * 想定外の入力に対し て０を出力 想定外の入力に対して何を出力してもよい

部分論理関数とカルノー図

● 演習：b6に対応する論理関数を設計しよう。 x1 x2 x3 b6 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 N/A 1 1 0 N/A

クワイン・マクラスキー法

● 機械的に最簡形を求める方法 ● 文字列処理によって主項を発見する ● 手順 ● すべての最小項を文字列で表現する ● 組み合わせ表を使って文字列をまとめていく （主項の発見） ● 主項表を作り、必須主項を発見する ● 必須主項以外の主項を発見する

クワイン・マクラスキ―法

● 項を文字列化する例（変数 xyzw の場合） – _{x・y・z・w → 1111} – _{x・y・z・w → 0101} – _{x・y・z →} 111-– _{x・z・w → 1-00} – _{x・z →} 1-0-● 0と1が1か所だけ違う文字列をまとめる – _{1111+1110=111-} x y z w+ x y z ̄w=x y z(w+ ̄w)=x y z

クワイン・マクラスキー法

● 表を使った主項の発見 1. すべての最小項の組み合わせ表を作り、第０表とする。 n←0とする。 2. まとめられる文字列はまとめる。まとめられなかった項 に印をつける。 3. 文字列をまとめることができた場合は、それらを集めて 第_{(n+1)表を作る。2.へ。} 4. 印のついた項が主項である。

表を使った主項の発見

g _{x , y , z ,w= x y wx y z w y z wx y z w x y z wx z} 最小項は0001 0010 0011 0111 1001 1010 1011 1100 1110 1111 第０表 0010 0011 0111 1001 1010 1011 1100 1110 1111 0001 00-1 -001 0010 001- -010 0011 0-11 -011 0111 -111 1001 10-1 1010 101- 1-10 1011 1-11

表を使った主項の発見

第１表 001- 0-11 -001 -010 -011 10-1 101- 1-10 11-0 -111 1-11 111-00-1 -0-1 001- -01-0-11 --11 -001 -0-1 -010 -01--011 --11 10-1 101- 1-1-1-10 1-1-11-0 -111

表を使った主項の発見

第2表 -01- --11 1-1--0-1 -01---11 まとめられる組み 合わせはない 発見された主項は _{-0-1, -01-, --11, 1-1-, 11-0} 次にこの中から必須主項を探す→主項表

主項表

0001 0010 0011 0111 1001 1010 1011 1100 1110 1111 -0-1 x x x x -01- x x x x --11 x x x x 1-1- x x x x 11-0 x x ある主項がどの最小項をカバーするか記入する

主項表

0001 0010 0011 0111 1001 1010 1011 1100 1110 1111 -0-1 x x x x -01- x x x x --11 x x x x 1-1- x x x x 11-0 x x 最小項のうち印が_{1個しかついてないものをチェック}

主項表

0001 0010 0011 0111 1001 1010 1011 1100 1110 1111 -0-1 x x x x -01- x x x x --11 x x x x 1-1- x x x x 11-0 x x その印がある行の主項が必須主項 -0-1, -01-, --11, 11-0 は必須主項 1-1- は必須主項でない

主項表

0001 0010 0011 0111 1001 1010 1011 1100 1110 1111 -0-1 x x x x -01- x x x x --11 x x x x 1-1- x x x x 11-0 x x 必須主項がカバーする最小項をチェック 必須主項だけですべての最小項がカバーできる →必須主項だけで最簡形が構成される g _{( x , y , z , w)=¯y w+¯y z+z w+x y ¯w}

カルノー図による

QM法の理解

xy \ zw 00 01 11 10 00 0001 0011 0010 01 0111 11 1100 1111 1110 10 1001 1011 1010 第_0表 xy \ zw 00 01 11 10 00 01 第_1表 00-1 -111 001- 111--001 1-11

カルノー図による

QM法の理解

xy \ zw 00 01 11 10 00 01 11 10 第_2表 xy \ zw 00 01 11 10 00 01 最適な組み合わせ -0-1 -01---11

1-1-必須主項以外が必要な例

g _{( x , y , z)=̄x ̄y z+ ̄x y z+ x y ̄z+ x y z+ x ̄ȳz} 001 011 110 111 100 第_0表 011 110 111 100 001 0-1 011 -11 110 11- 1-0 111 0-1 -11 11- 1-0 第_1表 -11 11- 1-0 0-1

必須主項以外が必要な例

主項表 001 011 110 111 110 0-1 * * -11 * * 11- * * 1-0 * * 必須 必須 001 011 110 111 110 0-1 * * -11 * * 11- * * 1-0 * * 必須主項でカバーされる最小項 どちらでもよいこ とがわかる

演習

x y z

_{x y zx y zx y zx y z}

を簡単化せよ。 クワイン・マクラスキー法を使って