Comments
Description
Transcript
資料08 - 講義資料
８．記号処理のしくみ Mechanism of symbol processing 論理演算と論理回路 ― Logical operation and logical circuit コンピュータは記号を処理する機械で，演算，記憶，通信の機能を受け持つユニットがバスを通して接続 され，読み取ったプログラムやデータの内容により自動的に働く。処理される記号はコンピュータ内部では ２値記号で表現されるので，記号操作の基本は２値の論理演算になる。この章では，コンピュータの数学的 なモデルであるオートマトン，2値論理演算の基本であるブール代数，オートマトンやブール代数を実際の機 械で実行するための論理回路について学ぶ。 オートマトン ・・・あらゆる自動機械のモデル オートマトンは，記号を入力する部分，出力する部分，内部状態を記憶する部分（メモリ）を持つ記 号処理システムのモデルだ。自動的に動く機械やシステムは，このオートマトンによってモデル化でき る。自動販売機や電卓などもオートマトンとしてモデル化できるし，コンピュータもオートマトンの一 種ということになる。 １ オートマトンのいろいろ 有限状態オートマトン 入力 状態の個数が有限のオートマトン セル・オートマトン 格子状に配置された複数のセルで構成 交通流や自然現象などのモデル化にも使われる チューリングマシン コンピュータのモデルとして使われる仮想機械 状態 出力 論理回路設計の分野では，有限状態 オートマトンはステートマシンと呼 ばれる。ステートマシンの設計は， 【論理回路】および【マイクロプロ セッサとインタフェース】で学ぶ。 チューリングマシン ・・・コンピュータのモデル データを読み書きできる１本の「テープ」に対して入出力するオートマトン。データの入出力を行う 読み書きヘッドはテープ上で双方向に移動できる。チューリングマシンは，コンピュータを単純化した もので，コンピュータの動作を数学的に調べるために使われる。 チューリングマシンは，コンピュータがまだ存在していなかった1936年にアラン・チューリングが論 文の中で発表した仮想機械。コンピュータで解く問題の「難しさ」や問題を解く手順（アルゴリズム） の性能を理論的かつ厳密に解析するために使われる。 アラン・チューリングは人工知能が真に 知的かどうかを判断するテストを考案し たことでも知られている。web上の認証 の際に使われる，歪んだ文字を認識さ せるCAPTCHA（キャプチャ）もチューリン グテストの一種だ。 テープ ｖ 読書き用 ヘッド 状態 コンピュータも磁気テープもなかった時代 に，A.チューリングが考えていた入出力 用の“テープ”とは何だったのだろうか? おそらくジャカード織機の紙テープのよう なものを想定していたものと思われる。 CAPTCHA用画像の例 図 8.1 チューリングマシン ----------------------------------------------------------------------------------------------------------------------------------------オートマトン（automaton） 複数形は automata（オートマタ），元々は「自動人形」を意味していた チューリングマシン（Turing machine） CAPTCHA（キャプチャ，Completely Automated Public Turing test to tell Computers and Humans Apart） ジャカード織機（じゃかーど しょっき，Jacquard loom，日本では“ジャガード”と表記されることが多いようだ。 ） ：1801 年にフランスの発明家ジョゼフ・マリー・ジャカール（Joseph Marie Jacquard）によって発明された自動織機。穴開け された紙テープやカードを使って，複雑な模様の織物を作成できる。カードの入れ替えによって制御パターンを変更する 技術はコンピュータにも応用された。 「計算機基礎，計算機と情報社会・情報倫理」講義メモ 8-1 ２値論理演算 ２つの値を持つ変数（論理変数 ）を考える。コンピュータの内部では複数の論理変数に対する演算（論 理演算）が，論理回路と呼ばれる２値の信号を扱う電子回路で行われている。例えば，図8-2の回路で は，２値のデータx ，yを入力すると２値のデータs ，c が出力される。 x s = f (x, y ) 演算回路 y c = g (x, y ) 図8-2 演算回路ブロックの例 この例では，出力s ，c は，入力x ，yだけで定まる。そこで，x ，y，s ，c を論理変数とすると， 入出力の関係は， s = f (x, y) c = g (x, y) のように関数として表すことができる。f とgのような演算を表す関数を論理関数と呼ぶ。“関数”とい う名前から，何か難しい計算をしているように感じるかもしれない。しかし実は，どんな論理関数もシ ンプルな基本演算を組み合わせることで作れてしまうのだ。 ２ どんな論理関数も，論理積（AND），論理和（OR），否定（NOT）の組合せで実現できる。 基本的論理演算 論理変数A，Bに対して以下の３つの基本的な演算が定義される． 論理積（AND） A ⋅ B ・・・ A × B ， Aand B と書くこともある 論理和（OR） A+ B ・・・ Aor B と書くこともある 否定（NOT） A ・・・ not A と書くこともある この３つの演算の組合せですべての論理演算が表現できる。３つ 表 6-1 AND，OR，NOT の真理値表 の演算の論理値と論理変数A，Bの関係を表にして示すと表5-1のよ うになる。なお，このように入力の論理値の組合せと論理演算の結 A B A⋅ B A + B A 果を表にしたものを真理値表という． 0 0 0 0 1 0 1 ブール代数 1 0 論理演算の理論的な基礎となる論理代数は，ジョージ・ブールに 1 1 よって1854 年に発表された．（彼は17 歳のとき，つまり1832 年に この発想を得たという．）ブール代数の演算規則は，以下のようになっている。 1. 冪等則： x ⋅ x = x ， x + x = x 2. 交換則： x ⋅ y = y ⋅ x ， x + y = y + x 3. 結合則： ( x ⋅ y ) ⋅ z = x ⋅ ( y ⋅ z ) ， ( x + y ) + z = x + ( y + z ) 4. 吸収則： ( x ⋅ y ) + x = x ， ( x + y ) ⋅ x = x 5. 分配則： ( x + y ) ⋅ z = x ⋅ z + y ⋅ z ， ( x ⋅ y ) + z = ( x + z ) ⋅ ( y + z ) 6. 相補則： x + x = 1 ， x ⋅ x = 0 ． 0 0 1 1 1 1 1 0 0 ----------------------------------------------------------------------------------------------------------------------------------------論理変数（logical variable） 変数の値は，“0，1”の他，“true，false”，“真（しん），偽（ぎ）”などと呼ぶ 論理式（logical expression），論理関数（logical function），真理値表（truth table），ブール代数（Boolean algebra） 「計算機基礎，計算機と情報社会・情報倫理」講義メモ 8-2 NANDとNOR 論理積を求めてから否定する演算（ A ⋅ B ）をNANDと呼ぶ（NOT + AND）。また，論理和を求めて から否定する演算（ A + B ）をNORと呼ぶ（NOT + OR）。 ３ NANDだけ，あるいはNORだけの組合せでも，任意の論理関数が作れる。 演習問題[1] 以下の論理式から真理値 表を完成させよ。 ① y = a⋅b ② y =a+b 論理回路とMIL記法 Exclusive OR 私たちが日常使うOR は多少あいまいで，「AまたはB」と したとき，AとBが同時には成り立たないようなつもりでつ かうことがある．このようにどちらか一方が真値であるとき のみ真値であるようなOR 演算を排他的論理和（XOR）と呼び， ⊕ 等と表記する．その真理値表は A ブールの考え出した数学は人間精神 の論理的働きを数学的に表そうとした 多くの試みの一つと考えられる。彼の仕 事は100年間無視されたあと論理回路の 設計の強力な道具として再評価される ことになる。 以下では基本的な論理回路の表記方 法を示す。 B A⊕B ０ ０ ０ ０ １ １ １ ０ １ １ １ ０ となる．排他的論理和は，AND，OR，NOTの演算を使うと， A ⊕ B = A⋅B + A⋅B のように書ける．XOR は２つの入力が不一致のとき出力が真 となるので，一致回路などに利用できる 論理回路の実装 二値論理変数に対する演算は論理回路（デジタル回路）によって実装される．論理回路は，アナログ 信号回路とは異なり，信号の２つの状態のみを扱う．現在使われているほとんどの論理回路は信号の電 圧レベルによって論理変数の値を表現している．つまり，電圧レベルが高い（H）か低い（L）かを，２ つの論理変数“1”と“0”に対応させている． ゲート，AND，OR，NOT 論理回路を図として表現する場合は，扱われる信号の論理値のみに注目した表記法を使う。この表記 法はMIL論理記号と呼ばれる。MIL論理記号では，論理演算を構成しているAND，OR，NOT などの基 本演算を実現する論理回路を図8-3のような記号で書き表す．これらの演算を行う論理回路の要素を論 理ゲート（または単にゲート）と呼ぶ。 AND OR 図8-3 NOT バッファ（増幅器） MIL論理記号 ----------------------------------------------------------------------------------------------------------------------------------------NAND（なんど） ，NOR（のあ） 排他的論理和（Exclusive OR），論理回路（logic circuit），デジタル回路（digital circuit），アナログ回路（analog circuit） MIL 論理記号（MIL logic symbols）米軍の部品調達の規格 MIL-806 で定められた論理記号，MIL(Military Standard Specification)，ゲート（logic gate） 実装（名詞：implementation，動詞：implement）与えられた機能やアルゴリズムをハードウェアやソフトウェアで実現 すること。作ること。 バッファ（buffer）ここでは，入力と同じ論理値を出力する，電流増幅のための増幅回路のこと。 「計算機基礎，計算機と情報社会・情報倫理」講義メモ 8-3 AND ゲート A B OR ゲート A 0 0 1 1 C C = A ⋅B X X X Y Y = X1 ⋅ X 2 ⋅ X3 B 0 1 0 1 C 0 0 0 1 A B 真理値表（Truth Table） B 0 1 0 1 C 0 1 1 1 Y Y = X1 + X 2 + X3 X1 X2 X X • • • • C = A +B C X1 X2 X3 A 0 0 1 1 • • • • • Y X Y = X1 ⋅ X 2 LX N Y Y = X1 + X 2 + L + X N XN NOT 回路（インバータ） A B A A 否定を表す A B C C = A ⋅B ・・NAND（NOT+AND） A B C C = A ⋅B C C = A + B ・・NOR（NOT+OR） 図8-4 MIL記法を用いたゲート回路の表記法 MIL論理記号では，否定（NOT）は小さな○印で表されている．したがって， a）NANDゲート b）NORゲート 図8.5 NANDゲートとNORゲート 図8.5a)のような表記では入力A，BのANDをとってからその否定を出力Cとしていることを表す．つまり， A ⋅ B （NAND）を表している．また，図8.5b)はは A + B （NOR）を表す。 NANDやNORはこれ１種類で全ての論理演算が可能であり，NANDゲートやNORゲートとしてIC化されてい る． 「計算機基礎，計算機と情報社会・情報倫理」講義メモ 8-4 A A A+B A AB B B A A B A+B=A+B= A⋅ B A⋅ B = A⋅ B A=A⋅A 図8.6 NAND によるAND，OR，NOT の実現 演習問題[2] 以下の回路図から入出力の論理式を求めよ。 A B C E D （ E = A ⋅ B⋅C + C⋅ D ） 演習問題[3] 以下の論理式から回路図を示せ。 ① Z = X ⋅C +Y ⋅C 組合せ論理回路と順序回路 論理回路には２つの種類がある． ４ 組合せ論理回路 順序回路 → 出力は現在の入力だけで定まる →出力は過去の入力にも依存する（“記憶” （状態）を持つ） ステートマシン（State Machine）とも呼ばれる コンピュータの中心的な部品であるCPUもステートマシンだ。 ----------------------------------------------------------------------------------------------------------------------------------------組合せ論理回路（combinational logic） ，順序回路（sequential logic） ，ステートマシン（state machine） 「計算機基礎，計算機と情報社会・情報倫理」講義メモ 8-5 論理素子に必要な機能 電流のON/OFFをコントロールするスイッチング動作と，信号のパワーを増大する増幅が必要となる。 ①AND，OR，NOT などの論理演算はスイッチング動作で行われる． ②信号を減衰させず伝送させるために増幅としきい値動作による信号復元が必要である． 加算回路の例 x3 x2 x1 x0 y3 y2 y1 y0 FA FA FA z3 z2 z1 z0 た，1 桁分の加算回路） い，1 桁分の加算回路） HA cs ５ x y ０ ０ １ １ ０ １ ０ １ c 1 ・・・C 1 1 0・・・X 0 1 1・・・Y 0 0 1 Fill Adder（下位からの桁上げを考慮し Half Adder（下位からの桁上げの無 x y 1 1 + 1 1 1 HA x y cin s FA cs cin x y ０ ０ ０ ０ １ １ １ １ ０ １ ０ １ ０ １ ０ １ ０ ０ １ １ ０ ０ １ １ c s ハードウェア記述言語 プログラム（文字による文や式）で回路を設計 動作のシミュレーション（モノを作らないで，動作を検証）にも使う HDLのメリット （小林優，他：HDL独習ソフトで学ぶCQEndeavor VHDL，CQ出版社（2009）より） 論理合成ソフトウェアが使える 抽象度を高くできる → “回路にやらせたいこと”を直接指示できる 効率が高い ・・・ 回路図だとA3用紙百枚 → HDLだとA4用紙10枚（数百行） 論理シミュレーションが高速 編集しやすい テキストエディタがあればよい（回路図描きソフトが不要） HDLのデメリット ソフトウェアが必須 部品の相互接続がわかりにくい（接続は回路図の方が理解しやすい） ----------------------------------------------------------------------------------------------------------------------------------------スイッチング（switching），増幅（動詞：amplify，名詞：amplification） ，ハードウェア記述言語（Hardware Description Language，HDL），論理合成（logic synthesis）HDL の記述から実際に動く回路の構造を作ること 「計算機基礎，計算機と情報社会・情報倫理」講義メモ 8-6 x 演習問題[3]の解答例 z y c 質問意見（抜粋）と回答例（Q：質問，C：意見，R：要求，A：回答） （多数の指摘） C：演習問題[3]の解答例のスライドで， Z = X ⋅ C + Y ⋅ C ではなく Z = X ⋅ C + Y ⋅ C となっていた。 A：線が欠けていました。ご指摘ありがとうございます。（Very Good） C：最後の加算回路がよくわからなかった。（加算回路の動作がわからなかったというコメント多数） A：２進数の加算については，中間試験でも出題したので，よくわかるだろうと考えていました。筆算でやっている 処理をそのまま回路にしただけですが，講義の最後の方で，少し急いでしまったため，わかりにくかったようで す。次週に補足説明します。 C：論理和で 1 + 1 = 1 となることに違和感がある。加算回路では“1 + 1 → 0 かつ桁上がりが発生”となるのに。（というコ メント多数） A：ブール代数の論理和の話をしてから加算回路の話をしたのが悪かったのかもしれません。 「論理和」と「算術和」 は別のものであることに注意が必要です。これについても，来週，説明します。 Q：①ブール代数がよくわからない，ゲート回路が複雑でよくわからない，加算回路が全然わからない。 ②今日の話は，非常 によくわかった。③今回の講義は，何がわからないのかわからないという，最悪な状態となった。 A：全体に，よくわからなかった，という人が多かったかもしれません。午前中に小白川でやった講義が，ちょうど 同じ内容のところでした。わかりやすかった，という意見が多かったのですが，油断してはいけなかったようで す。 Q： A + B や A ⋅ B などの記号を見ながら，高校時代に習った数学 A の「集合」を思い出しました。 A：数学 A は，どれくらいの人がやっているのでしょうか？ 「集合と論理」を教わってるはずなんだけど・・・。 Q：①今日やったところは，実社会で具体的にどのようなことに役立っているのですか？ ②結局のところ，論理回路は中間前の ことと何か関係あるのでしょうか。 A：①コンピュータを作るのに役立っています。CPU もその周辺の部品もほとんどが論理回路です。 ②関係は大 有りです。中間前は，コンピュータの概略の構造（フォン・ノイマン型）の説明をし，そのあと内部表現とそれ を使った計算の方法について学びました。では，実際にコンピュータはどのようなもので作られているのか，計 算はどのようにして実行しているか，が今日の話です。ハードウェア構成の話は，もう少しやった方がいいので， 来週も続きをやります。 C：講義資料 8-1 図 8.1 の中の説明に， “A.チューリングが考えていた入出力用のテープは何だったのだろうか？”とありますが， この時代（第二次世界大戦直前？）には映像用ビデオテープと音声用テープはもう存在していたはずです。 A：ご指摘のように，音声用のテープレコーダはドイツで開発され最初の市販品は 1935 年に出たそうです。(音質は 悪かったとか。) しかし普及したのは第二次世界大戦後です。なお，映像用磁気テープの方は（確認できていな いのですが）開発と普及はオーディオ用より後になると思います。そして，これらの技術はアナログの記録技術 です。チューリングの原論文を読むと「 “tape”, (the analogue of paper)」となっていて， “紙”をモデル化したデ ジタル的なもののようです。区画に分かれ，文字が書いてあって書き直しもできるものを考えていたようです。 ですから，当時，チューリングが磁気テープの技術を知っていたとしても，論文では，かなり異なるものを想定 していたと思われます。（Very Good） Q： のような表記もありますか？ A：あります。なお，この回路は と同じになります。 （ “ド・モルガンの定理”です。 ） Q：MIL 論理記号を使って，コンピュータを論理回路図にすると，とても大きく複雑になってしまうと思ったのですが，何か工夫をして いるのでしょうか？ A：いい質問です。来週説明しますが，“階層化”して設計しています。 （Very Good） Q：NAND は何に使いますか？ A：2 入力の NAND ゲートを組み合わせれば，いろいろな回路が作れます。例えは，4 個の２入力 NAND ゲートを １個のパッケージに収めた IC が販売されていて，今でも私の研究室の部品ケースに入っています。 Q：資料 8-10 の図 8.1 の左上にある“ｖ ”みたいな文字は何ですか？ A：図をコピー&ペーストで貼り付けようとしたとき，Ctrl+V（コントロールキーと“v”の同時押し）でペースト しようとして失敗して文字“v”が挿入されたようです。 「計算機基礎，計算機と情報社会・情報倫理」講義メモ 8-7 昨年度まで及び関連する講義の質問と回答より Q：論理回路の真理値表でベン図を使わないのでしょうか？（使わなくても大丈夫ですが，念のため） A：使った方が良かったかな，と思っています。時間的な余裕がないのと，“ベン図を見るのが初めて”という人が いたら，かえって混乱のもとになるかもしれないので，使いませんでした。 「論理回路」やブール代数についての 講義では出てくると思います。 Q：①チューリングマシンを使えば理論的かつ厳密な解析ができる，とありますが，正直そんなに，どこがすごいのかわかりません。 勉強していけば有用性に気づけるのでしょうか？ ②オートマトンは，どのようなモデルなのか？ 実例はあるのか？ A：①勉強していけば，わかると思います。 （私は，実は，この分野の話は苦手みたいだ。）②オートマトンは，もと もとは“紙と鉛筆”で考えるためのモデルでした。ですから， “どんな自動機械でもオートマトンとしてモデル化 できる”と言えます。これも，次回に（時間があれば）実例を挙げましょう。 Q：無限状態のセル・オートマトンも存在するのか？ A：板書した“いろいろなオートマトン”は厳密な分類ではなく，よく使われるオートマトンの例を示したものです。 セル・オートマトンにはモデルとして無限状態のものもあり得ます。実際の機械のモデルでは，有限状態のもの が多いはずです。 Q：プログラムの勉強でライフゲームを作ったことがあるが，あれはセル・オートマトンでいいのだろうか？ A：生命の誕生、進化、淘汰のモデルを使うライフゲームは，セル・オートマトンの応用です。1970 年にイギリス の数学者ジョン・ホートン・コンウェイ (John Horton Conway) によって考案されたそうです。 Q：①CAPTHA で，歪んだ文字を認識できてしまうソフトが出来てしまったら，認証としては，意味のないものになってしまうのでしょう か？ ②電子辞書の文字認識は，手書きの汚い文字も認識できるようになっている。CAPTHA に対応するソフトもすぐにできるの では？ A：手書き文字認識をコンピュータで行う研究は，古くから行われていて，かなりのところまでできるようになって います。CAPTHA に対応する場合，難しいのは， “どこに文字があるか”，“文字の大きさ”というスタートの部 分の認識です。人間は，すぐにわかるのですが，自動認識システムでは，今のところ，枠を指定してあげないと 動きません。でも，今の CAPTHA をクリアする自動認識技術は，そんなに大変ではないような気もします。 Q：論理回路を式と図の２ 通りに表すことができるのですが，具体的に，どのように使い分けるのでしょうか？ A：どちらも論理回路の設計に使えます。回路図は，接続関係が直感的に把握できます。一方，式は，曖昧さが少な く，式変形を使った回路の簡単化もできます。図による表現と式による表現が互いに補い合う関係があります。 以前は，回路のハードウェア設計では回路図を使うことが多かったのですが，今回の講義の最後に説明したよう に，式や文を使ったハードウェア記述言語による設計が採用されるようになってきました。 Q：HDL の説明で“抽象度が高い”とありましたが，n 進数と n+1 進数の関係に似ていると思った。 “抽象度が高い→文字数が 多い”，“密度が高い→文字列の長さが少ない” A：“抽象度”については，今後の講義のどこかで，きちんとお話ししておいた方がいいと思います。 Q：資料 8-6 の板書５ で“シミュレーション”とあったが，“シュミレーション”では？ A：いいえ“simulation”なので，カタカナ表記では“シミュレーション”でよいのです。“シュミレーション”と 誤って書かれたり発音されたりすることが多いようです。私は研究でコンピュータシミュレーションをすること が多いので，この間違いは気になります。「趣味でするのがシュミレーション（誤） ，仕事でするのがシミュレー ション（正）」と教えたら，カタカナ用語に弱い人も一発で覚えてくれましたが。 Q： 「バッファ」という言葉が出てきました。インターネットでのストリーミング動画を見ているときに， 「バッファ中」という表示を見かけ たりしますが，その場合の「バッファ」とはどのような意味ですか？ A：“buffer”は，もともとは緩衝器（かんしょうき，衝撃を和らげるための装置）のことでした。電子回路や情報 機器で，急速な変動を和らげる働きをするものもバッファと呼ばれます。電子回路では，多数の付加に信号を供 給するためのアンプがバッファアンプです。論理回路のバッファも同じ働きです。出力の論理値は入力と同じで すが，供給できる電流が増えています。情報通信では，インターネットのストリーミングのように，ネットワー クの混雑のため送られてくるデータの速度が大きく変動する場合，ハードディスクなどに一旦データを貯めて出 力速度を一定に保つようにします。水道の水を供給するとき途中に置いて，流量の変動を防ぐバッファタンクと 同じ働きをします。（Very Good） Q：回路図の接続線の分岐を表す黒丸は省略してもよいのか？ A：配線が交差するとき，接続されているのかいないのか，明確にするため，黒丸を付けることがあります。 ----------------------------------------------------------------------------------------------------------------------------------------ベン図（Venn diagram），ライフゲーム（Conway's Game of Life）， シミュレーション（simulation）もともとは真似，模倣などを意味する。コンピュータ分野では，様々な現象をモデル化 して予測する技術などを指し，“模擬実験”などとも呼ばれる。シミュレーションゲームというゲームの分野もある。 「計算機基礎，計算機と情報社会・情報倫理」講義メモ 8-8