情報基礎 I

NAGASAKA Yasunori

2006/04/08

http://edu.isc.chubu.ac.jp/naga/index.html で公開中


 Table of Contents


1   はじめに

2   数の表現
 2.1   数の表記に関する注意
 2.2   2 進数と 10 進数
 2.3   10 進数の表現の原理
 2.4   2 進数の表現の原理
 2.5   コンピュータで 2 進数を採用する理由
 2.6   10 進数と 2 進数の簡単な対応表
 2.7   m 進数の表現の原理
 2.8   m 進数における小数点以下の表現
 2.9   2 進数 → 10 進数の変換
 2.10   2 進数 → 10 進数の変換 (その2)
 2.11   m 進数 → 10 進数の変換
 2.12   m 進数 → 10 進数の変換 (その2)
 2.13   10 進数 → 2 進数の変換
  2.13.1   整数部分の変換
  2.13.2   小数部分の変換
  2.13.3   計算の例
  2.13.4   無限小数の問題
 2.14   10 進数 → m 進数の変換
  2.14.1   整数部分の変換
  2.14.2   小数部分の変換
 2.15   16 進数と 8 進数
  2.15.1   16 進数の表現の原理
  2.15.2   16 進数と 2 進数との間の相互変換
  2.15.3   8 進数の表現の原理
  2.15.4   8 進数と 2 進数との間の相互変換
  2.15.5   16 進数と 8 進数との間の相互変換
 2.16   2 進数の加算
 2.17   2 進数の乗算
 2.18   2 の補数 (負の数の表現)
  2.18.1   2 の補数の表現法
  2.18.2   2 の補数の様々な性質
  2.18.3   桁数の重要性
  2.18.4   加算による減算の実現
  2.18.5   桁数と表現可能な数の範囲の関係
  2.18.6   練習問題

3   ブール代数の基礎と簡単な論理回路
 3.1   ブール代数
 3.2   真と偽の値の様々な表現
 3.3   代表的な論理演算
  3.3.1   凡例, ここには演算の名前を書く
  3.3.2   論理積 AND
  3.3.3   論理和 OR
  3.3.4   否定 NOT
  3.3.5   排他的論理和 EXOR, XOR
  3.3.6   論理積否定 NAND
  3.3.7   論理和否定 NOR
 3.4   ブール代数の定理
  3.4.1   論理和に関する定理
  3.4.2   論理積に関する定理
  3.4.3   否定に関する定理
  3.4.4   交換法則
  3.4.5   結合法則
  3.4.6   分配法則
  3.4.7   吸収法則
  3.4.8   ド・モルガンの定理
  3.4.9   その他
  3.4.10   定理の証明
 3.5   3 変数の論理演算
  3.5.1   3 変数の論理積 AND
  3.5.2   3 変数の論理和 OR
  3.5.3   n 変数の論理演算
 3.6   一般的な論理式、論理関数
 3.7   論理回路による加算器の設計
  3.7.1   半加算器
  3.7.2   全加算器
  3.7.3   複数桁加算器の設計

4   コンピュータの構造
 4.1   コンピュータに関する基礎的な知識
  4.1.1   プログラム内蔵方式
  4.1.2   コンピュータのプログラム
  4.1.3   プログラミング言語
  4.1.4   プログラミング言語と自然言語の違い
  4.1.5   オペレーティングシステム, OS
 4.2   コンピュータを構成する装置
  4.2.1   Central Processing Unit
  4.2.2   Main Memory Unit
  4.2.3   Input Device
  4.2.4   OutPut Device
  4.2.5   Secondary Memory Unit
  4.2.6   Communication Control Unit
  4.2.7   主記憶装置と補助記憶装置の違い
 4.3   CPU、マイクロプロセッサの機能
  4.3.1   データサイズ
  4.3.2   CPU の内部構成、各部の機能
  4.3.3   CPU の動作原理
 4.4   コンピュータに関連する単位
  4.4.1   記憶容量
  4.4.2   時間

5   情報社会の倫理、法律、安全管理



1   はじめに

  電子情報工学科でこれから 4 年間「コンピュータ」、「情報工学」について学ぶ上で、 基本となる知識や考え方を習得する。 主要な内容として (1) 数の表現 (2 進数と 16 進数)、(2) ブール代数の基礎と簡単な論理回路、 (3) コンピュータの構造と動作原理 (4) 情報社会の倫理、法律、安全管理 を取り上げる。




2   数の表現


2.1   数の表記に関する注意

  この後出てくる数の表記に関して、n^m は n の m 乗を表す。10^3 なら 1000 である。 説明中の数は文脈から明らかに何進数かわかる場合は特に明示しない。紛らわしい場合は次のように 表記する。(24)10 なら 10 進数の 24 を表す。 (1011)2 なら 2 進数の 1011 である。 10 進数以外の数の表現の説明中でも、多くの場合理解し易いように 10 進数を使って説明する。



2.2   2 進数と 10 進数

  人間は数を表現したり計算をする場合、特別に指定されなければ 10 進数を用いる。 コンピュータ内部で数を表現したり計算をする場合、ほとんどの場合 2 進数が用いられる。 以下では 10 進数と 2 進数の表現の原理を比較して、共通点と相違点を明らかにする。 10 進数の説明の中の 10 を 2 に書き換えるとほぼそのまま 2 進数の説明になるといえる。



2.3   10 進数の表現の原理

  10 進数は 0 〜 9 の 10 種類の数字を使用する。

1 から数えて 10 (10^1)個目の数で桁上げ、10 という表現になる。
1 から数えて 100 (10^2)個目の数で桁上げ、100 という表現になる。
1 から数えて 1000 (10^3)個目の数で桁上げ、1000 という表現になる。
1 から数えて 10000 (10^4)個目の数で桁上げ、10000 という表現になる。
  一般に 10n 個目の数で桁上がりが発生し、n+1 桁の表現になる。 また右から数えて n 桁目の数は 10n-1が何個あるかを表す。 例として、23456 の右から 3 桁目の 4 は、102が 4 個あることを表す。



2.4   2 進数の表現の原理

  2 進数は 0, 1 の 2 種類の数字を使用する。

1 から数えて 2 (2^1)個目の数で桁上げ、10 という表現になる。
1 から数えて 4 (2^2)個目の数で桁上げ、100 という表現になる。
1 から数えて 8 (2^3)個目の数で桁上げ、1000 という表現になる。
1 から数えて 16 (2^4)個目の数で桁上げ、10000 という表現になる。
  一般に 2n 個目の数で桁上がりが発生し、n+1 桁の表現になる。 また右から数えて n 桁目の数は 2n-1が何個あるかを表す。 例として、10010111 の右から 3 桁目の 1 は、22が 1 個あることを表す。

  補足として、2 進数の各桁は 0 か 1 しか取り得ないので、その桁に対応する数が「ある」か、 「ない」かを表しているといえる。2 進数による表現は、 各桁が表現できる数の種類が 2 種類しかないため、同じ大きさの数を表現する場合すぐに桁数が 大きくなってしまうという特徴がある。



2.5   コンピュータで 2 進数を採用する理由

  なぜコンピュータでは 2 進数を使って数を表現したり計算したりするのか ?

  → CPU (コンピュータ内部で実際に計算を行なう中枢部分) 内部では、2 進数 1 桁をスイッチの ON と OFF に割り当て、そのスイッチの端子間が接続されているか/電流が流れるかどうかで表現するから。

  → 3 種類以上の状態を表現するのは回路が複雑になり、作るのが難しい。コスト増の要因となる。 1 桁で表現できる状態を 2 種類に限定することで非常に実現し易くなるため。 それには 2 進数が最も適している。

  2 進数 1 桁を 1 bit, 8 桁 (8 bit) をまとめて 1 Byte と呼ぶ。



2.6   10 進数と 2 進数の簡単な対応表

  ここでは 2 進数 4 桁で表現できる数を 10 進数と 2 進数で対応させて記載する。 これらの数は 2 進数を扱う場合頻繁に出てくるので覚えておくとよい。 しばらく 2 進数を扱っているとある程度自然に覚えられる。


10 進数と 2 進数の対応表

10 進数 2 進数 | | 10 進数 2 進数
0 0 | | 8 1000
1 1 | | 9 1001
2 10 | | 10 1010
3 11 | | 11 1011
4 100 | | 12 1100
5 101 | | 13 1101
6 110 | | 14 1110
7 111 | | 15 1111



2.7   m 進数の表現の原理

  2 進数と 10 進数の表現の原理をもとにして、共通する部分を抜き出して一般化すると、 任意の m 進数の表現の原理は次のように記述できる。

  m 進数は 0, 1, ... m-1 の m 種類の数字を使用する。

1 から数えて (m^1)個目の数で桁上げ、10 という表現になる。
1 から数えて (m^2)個目の数で桁上げ、100 という表現になる。
1 から数えて (m^3)個目の数で桁上げ、1000 という表現になる。
1 から数えて (m^4)個目の数で桁上げ、10000 という表現になる。
  一般に mn 個目の数で桁上がりが発生し、n+1 桁の表現になる。 また右から数えて n 桁目の数は mn-1が何個あるかを表す。

  例として、(123456)7の左端の 1 は 75の個数を、 真中あたりの 4 は 72の個数をそれぞれ表している。



2.8   m 進数における小数点以下の表現

  上記 m 進数の表現の原理を拡張すると、 m 進数における小数点以下の表現の原理も同様の考え方で定義できる。

  m 進数で表現した数 ??????.???? (? は m 進数の 1 桁を表す) の各桁は、 小数点の左に移動するにつれて、m0, m1, m2, m3 のように値が大きくなっていく。小数点の右に移動すると、 m-1, m-2, m-3 のように値が小さくなっていく。

  例として、(1122.3344)5の左端の 1 は 53の個数を、 右端の 4 は 5-4の個数をそれぞれ表している。



2.9   2 進数 → 10 進数の変換

  2 進数から 10 進数への変換は、2 進数の表現の中で 1 になっている桁が 2 の何乗に対応するかをそれぞれ求めて、 その和を計算することにより実行できる。

  例として、(10011101)2の 1 の桁を順に求めると、 右から 20 , 22 , 23 , 24 , 27 となるため、その和 20 + 22 + 23 + 24 + 27 を計算する。すなわち、 1 + 4 + 8 + 16 + 128 = (157)10 となる。

  参考までに、2n を順に示すと、 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536 となる。

  2 進数の小数部分を 10 進数に変換する手順も同様に定義でき、 2 進数の表現の中で 1 になっている桁が 2 の何乗に対応するかをそれぞれ求めて、 その和を計算することにより実行できる。

  例として、(0.1011)2の 1 の桁を順に求めると、 左から 2-1 , 2-3 , 2-4 となるため、その和 2-1 + 2-3 + 2-4 を計算する。すなわち、 1/2 + 1/8 + 1/16 = (11/16)10 となる。 小数の表現では、0.5 + 0.125 + 0.0625 = (0.6875)10 となる。 結果は必要に応じて、分数、小数どちらの表現にしてもよい。

  整数部分と小数部分を同時に含む数は、前述の手順を両方計算する。 例として、(10111.111)2であれば、 1 の各桁が表す値は左から 24 , 22 , 21 , 20 , 2-1 , 2-2 , 2-3 となるため、その和 24 + 22 + 21 + 20 + 2-1 + 2-2 + 2-3 を計算する。すなわち、 16 + 4 + 2 + 1 + 0.5 + 0.25 + 0.125 = (23.875)10 となる。



2.10   2 進数 → 10 進数の変換 (その2)

  2 進数から 10 進数への変換は、整数に関してはもう一つの方法がある。 前述の方法とどちらを使ってもよいので、自分が理解し易い、 覚え易い方法が正しく使えるようになればよい。

  この方法は、2 進数の表現の左端の桁から 1 桁ずつ取り出してきて、 「それまでの結果を 2 倍して、次の桁を加える」という操作を再帰的に繰り返す。 これにより計算式を記述して、その後演算の優先順位を考慮して計算する。

  例として、(10011101)2 の場合は、 次のように式を組み立ててから計算する。
1 * 2 + 0
(1 * 2 + 0) * 2 + 0
((1 * 2 + 0) * 2 + 0) * 2 + 1
(((1 * 2 + 0) * 2 + 0) * 2 + 1) * 2 + 1
((((1 * 2 + 0) * 2 + 0) * 2 + 1) * 2 + 1) * 2 + 1
(((((1 * 2 + 0) * 2 + 0) * 2 + 1) * 2 + 1) * 2 + 1) * 2 + 0
((((((1 * 2 + 0) * 2 + 0) * 2 + 1) * 2 + 1) * 2 + 1) * 2 + 0) * 2 + 1
最終的に、
((((((1 * 2 + 0) * 2 + 0) * 2 + 1) * 2 + 1) * 2 + 1) * 2 + 0) * 2 + 1 = (157)10
が得られる。 上記の式を内側の括弧から順に計算していくと、2, 4, 9, 19, 39, 78, 157 となり答が求められる。 ここで、式の中の 1 と 0 に注目すると、左から順に 1,0,0,1,1,1,0,1 となり、 もとの 2 進数と一致する。別のいい方をすると、もとの 2 進数の左から 1 桁ずつ取り出してきて、 2 倍して次の桁を加えるという計算を最後まで繰り返すことで、対応する 10 進数が求められる。

  別の例として、(110011)2 の場合は、
(((((1 * 2 + 1) * 2 + 0) * 2 + 0) * 2 + 1) * 2 + 1) = (51)10
計算の過程は、3, 6, 12, 25, 51 となる。

  この方法は、式の書き方を正確に覚えていないと正しい答えにならないので、 使う場合には注意する。



2.11   m 進数 → 10 進数の変換

  前述の 2 進数から 10 進数への変換をもとにして、2 を m に置き換えることで、 m 進数から 10 進数への変換を同様に定義できる。すなわち、 m 進数の表現の中で 0 以外の値の桁が m の何乗に対応するかをそれぞれ求めて、 重みをかけた和を計算することにより実行できる。

  例として、(1234.123)5の各桁が対応する値を順に求めると、 左から 53 , 52 , 51 , 50 , 5-1 , 5-2 , 5-3 となるため、それぞれの値に各桁の値をかけた和 (1 * 53) + (2 * 52) + (3 * 51) + (4 * 50) + (1 * 5-1) + (2 * 5-2) + (3 * 5-3) を計算する。すなわち、 125 + 50 + 15 + 4 + 1/5 + 2/25 + 3/125 = (194.304)10 となる。



2.12   m 進数 → 10 進数の変換 (その2)

  m 進数から 10 進数への変換は、整数に関してはもう一つの方法がある。 2 進数で示した括弧が多数出てくる計算方法が、 2 を m に置き換えるだけでそのまま適用できる。

  例として、(1234)5 の場合は次のように計算する。
(((1 * 5 + 2) * 5 + 3) * 5 + 4) = (194)10
この式を内側の括弧から順に計算していくと、7, 38, 194 となり答が求められる。 ここで、式の中の 5 以外の数字に注目すると、左から順に 1,2,3,4 となり、 もとの 5 進数と一致する。これは先ほどの 2 進数の方法と同じ原理である。



2.13   10 進数 → 2 進数の変換

  ここではこれまでとは逆に、10 進数から 2 進数への変換方法を示す。 10 進数からの変換では整数部分と小数部分で全く異なった方法を用いる。


2.13.1   整数部分の変換

  整数部分は 2 による除算を繰り返し実行して、 その商と余りを順次求めて最後にそれらの値を並べることで答が得られる。

  例として、(13)10 を変換すると次のようになる。
2 ) 13
  ------
2 )  6 ... 1
  ------
2 )  3 ... 0
  ------
     1 ... 1
これは、13 / 2 = 6 ... 1, 6 / 2 = 3 ... 0, 3 / 2 = 1 ... 1 を連続して計算している。 答が 1 になったら終了する。 ここで得た最後の商と途中の余りを下から順に並べた表現 1101 が対応する 2 進数となる。



2.13.2   小数部分の変換

  小数部分は 2 による乗算を繰り返し実行して、 その答を順次求めて最後にそれらの整数部分を並べることで答が得られる。

  例として、(0.625)10 を変換すると次のようになる。
0.625     (1)
x   2
-------
1.250     (2)
x   2
-------
0.500     (3)
x   2
-------
1.00      (4)
これは、0.625 * 2 = 1.250, 0.250 * 2 = 0.500, 0.500 * 2 = 1.000 を連続して計算している。 この計算は小数点以下が 0 になったら終了する。 ここで得た途中の答の整数部分((2), (3), (4))を上から順に並べた表現 101 が対応する 2 進数の小数部分となり、 答えは (0.101)2となる。

  小数部分の変換では間違え易い部分があるが、以下の点に気をつける。



2.13.3   計算の例

  例として (53.6875)10を 2 進数に変換する。
2 ) 53
  ------
2 ) 26 ... 1
  ------
2 ) 13 ... 0
  ------
2 )  6 ... 1
  ------
2 )  3 ... 0
  ------
     1 ... 1
したがって整数部分は (110101)2となる。
0.6875
x    2
--------
1.3750
x    2
--------
0.7500
x    2
--------
1.5000
x    2
--------
1.0000
したがって小数部分は (0.1011)2となる。 両方の結果から、(53.6875)10 = (110101.1011)2 という結果が得られる。



2.13.4   無限小数の問題

  10 進数から 2 進数への変換では、整数部分は必ず答が求められるが、 小数部分はしばしば桁が無限に続く数となり有限の桁数では正しく表現できない。

  例として、(0.4)10 を 2 進数に変換すると、
0.40
x  2
--------
0.80
x  2
--------
1.60
x  2
--------
1.20
x  2
--------
0.40
x  2
--------
となり、途中でもとの数 0.4 に戻ってしまったので以後の計算は循環して終了しない。 (0.4)10 = (0.011001100110...)2 となる。

  他の値では、例えば (0.3)10 = (0.01001100110...)2となり、また (0.33333333...)10 = (0.0101010101010...)2となり、 いずれも無限小数となる。




2.14   10 進数 → m 進数の変換

  10 進数から 2 進数への変換方法において、 2 を m に置き換えることで、 10 進数から m 進数への変換が定義できる。 以下では (123.45)10を 5 進数に変換する。


2.14.1   整数部分の変換

  整数部分は m による除算を繰り返し実行して、 その商と余りを順次求めて最後にそれらの値を並べることで答が得られる。
5 ) 123
  -------
5 )  24 ... 3
  ------
      4 ... 4
これは、123 / 5 = 24 ... 3, 24 / 5 = 4 ... 4 を連続して計算している。 答が 4 以下になったら終了する。 ここで得た最後の商と途中の余りを下から順に並べた表現 443 が対応する 5 進数となる。



2.14.2   小数部分の変換

  小数部分は 5 による乗算を繰り返し実行して、 その答を順次求めて最後にそれらの整数部分を並べることで答が得られる。
0.45     (1)
x  5
-------
2.25     (2)
x  5
-------
1.25     (3)
x  5
-------
1.25     (4)
これは、0.45 * 5 = 2.25, 0.25 * 5 = 1.25, 0.25 * 5 = 1.25 を連続して計算している。 この計算は小数点以下が 0 になったら終了する。 ここで得た途中の答の整数部分((2), (3), (4))を上から順に並べた表現 211 が対応する 5 進数の小数部分となり、 答えは (0.211)5となる。 のは 2 進数の場合と同様である。 また無限小数に関する注意も同様である。上記の例では (3) から (4) で同じ値となったので、 以下無限に同じ値が続き計算は終了しない。




2.15   16 進数と 8 進数

  コンピュータに関する分野及び情報工学で、 2 進数と同じようによく使われる数の表現として 16 進数と 8 進数がある。

  コンピュータ内部で実際に使用されるのは 2 進数であるが、 2 進数はすぐに桁数が大きくなってしまい、 人間にとって内容を直感的に理解するのが難しいという問題がある。 この問題に対処するため、 2 進数を 16 進数や 8 進数に変換して表示/計算することがよく行なわれる。 16 進数と 8 進数は 2 進数との間の相互変換が簡単なのでこのような用途に用いられる。

  8 進数はこれまでに出てきた m 進数の表現の原理がそのまま適用できるが、 16 進数は数字が足らないという問題があり、慣例としてアルファベットの A, B, C, D, E, F を数字として代用する。


2.15.1   16 進数の表現の原理

  16 進数は 0 〜 9 と A, B, C, D, E, F の 16 種類の数字を使用する。 A, B, C, D, E, F は通常アルファベットの文字として使われるが、 慣例として 16 進数における数字として使用する。 場合によって小文字で表記する場合もある。

1 から数えて 16 (16^1)個目の数で桁上げ、10 という表現になる。
1 から数えて 256 (16^2)個目の数で桁上げ、100 という表現になる。
1 から数えて 4096 (16^3)個目の数で桁上げ、1000 という表現になる。
1 から数えて 65536 (16^4)個目の数で桁上げ、10000 という表現になる。
  一般に 16n 個目の数で桁上がりが発生し、n+1 桁の表現になる。 また右から数えて n 桁目の数は 16n-1が何個あるかを表す。 例として、AB45C6 の右から 2 桁目の C は、161が 12 個あることを表す。



2.15.2   16 進数と 2 進数との間の相互変換

  16 進数と 2 進数との間の相互変換は、他の m 進数との間の変換とは異なり、 簡単な値の置換えで実現できる。 2 進数の 4 桁と 16 進数 1 桁との間には 1 対 1 の対応関係があり、 その関係を利用すれば複雑な計算を行なわなくても変換が行なえる。 2 進数の 4 桁では 10 進数の 0 〜 15 まで表現できるが、 この範囲がちょうど 16 進数 1 桁の 0 〜 F に対応する。


10 進数と 2 進数, 8 進数, 16 進数の対応表

10 進数 2 進数 8 進数 16 進数 | | 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

  例として、(1110010101111010)2 を 16 進数に変換する場合は、 次のように右から 4 桁ずつに区切り、
1110 0101 0111 1010
それぞれを対応する 16 進数 1 桁に置き換えることで、(E57A)16 という結果が得られる。

  逆に 16 進数から 2 進数に変換する場合は、 16 進数の各桁を 4 桁の 2 進数に書き換えてそれをそのまま連結すればよい。 注意する点として、2 進数 4 桁に満たない小さな値の場合でも、 必ず左に 0 を補って 4 桁にして書く点がある。 そうしないと正しい答が得られない。

  例として、(72CB)16 を 2 進数に変換する場合は、 各桁を 2 進数 4 桁で表して、
0111 0010 1100 1011
となるが、 これを連結して (0111001011001011)2 という結果が得られる。 この場合、左端の 0 だけは省略できるが、他の 0 は一切省略できない。



2.15.3   8 進数の表現の原理

  8 進数は 0 〜 7 の 8 種類の数字を使用する。

1 から数えて 8 (8^1)個目の数で桁上げ、10 という表現になる。
1 から数えて 64 (8^2)個目の数で桁上げ、100 という表現になる。
1 から数えて 512 (8^3)個目の数で桁上げ、1000 という表現になる。
1 から数えて 4096 (8^4)個目の数で桁上げ、10000 という表現になる。
  一般に 8n 個目の数で桁上がりが発生し、n+1 桁の表現になる。 また右から数えて n 桁目の数は 8n-1が何個あるかを表す。 例として、332461 の右から 3 桁目の 4 は、82が 4 個あることを表す。



2.15.4   8 進数と 2 進数との間の相互変換

  8 進数と 2 進数との間の相互変換は、16 進数と 2 進数との変換と同様に、 簡単な値の置換えで実現できる。 2 進数の 3 桁と 8 進数 1 桁との間には 1 対 1 の対応関係があり、 その関係を利用すれば複雑な計算を行なわなくても変換が行なえる。 2 進数の 3 桁では 10 進数の 0 〜 7 まで表現できるが、 この範囲がちょうど 8 進数 1 桁の 0 〜 7 に対応する。

  例として、(1110010101111010)2 を 8 進数に変換する場合は、 次のように右から 3 桁ずつに区切り、
1 110 010 101 111 010
それぞれを対応する 8 進数 1 桁に置き換えることで、(162572)8 という結果が得られる。

  逆に 8 進数から 2 進数に変換する場合は、 8 進数の各桁を 3 桁の 2 進数に書き換えてそれをそのまま連結すればよい。 注意する点として、2 進数 3 桁に満たない小さな値の場合でも、 必ず左に 0 を補って 3 桁にして書く点がある。 そうしないと正しい答が得られない。

  例として、(37264)8 を 2 進数に変換する場合は、 各桁を 2 進数 3 桁で表して、
011 111 010 110 100
となるが、これを連結して (011111010110100)2 という結果が得られる。 この場合、左端の 0 だけは省略できるが、他の 0 は一切省略できない。



2.15.5   16 進数と 8 進数との間の相互変換

  16 進数と 8 進数との間で相互に変換するときは、一旦 2 進数の表現を経由するとわかりやすい。

  例として、(E9A3)16 を 8 進数に変換したい場合は、 まず 2 進数に変換して、 (E9A3)16 = 1110 1001 1010 0011 = (1110100110100011)2 その後で 8 進数に変換する。 1 110 100 110 100 011 = (164643)8

  別の例として、(314256)8 を 16 進数に変換したい場合は、 まず 2 進数に変換して、 (314256)8 = 011 001 100 010 101 110 = (011001100010101110)2 その後で 16 進数に変換する。 01 1001 1000 1010 1110 = (198AE)16




2.16   2 進数の加算

  2 進数 1 桁の加算は次のようになる。
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10
また複数桁の加算をする場合は、 下位の桁からの桁上がりが加わって 3 個の数の加算になることがある。
0 + 0 + 1 = 1
0 + 1 + 1 = 10
1 + 0 + 1 = 10
1 + 1 + 1 = 11


  複数桁の加算の場合は、10 進数の加算を筆算で行なう場合と同様に、 下位の桁から順に計算していけばよい。例として、
(1)
  10101101
+ 11001011
-----------
 101111000
      111

(2)
  1011
+ 1101
-------
 11000
   11
のように計算できる。 なおこの例では通常小さな数字で表す桁上がりの 1 を答の下に書いているので気をつけて欲しい。



2.17   2 進数の乗算

  2 進数 1 桁の乗算は次のようになる。
0 * 0 = 0
0 * 1 = 0
1 * 0 = 0
1 * 1 = 1
2 進数 1 桁の乗算はすべての数が 1 の場合だけ答が 1 になる。

  複数桁の乗算の場合は、10 進数の乗算を筆算で行なう場合と同様に、 下位の桁から順に計算していけばよい。例として、
(1)
     1011   (10 進数の 11)
   * 1101   (10 進数の 13)
----------
     1011
   1011
  1011
----------
 10001111   (10 進数の 143)
  111

(2)
     1111   (10 進数の 15)
   * 1111   (10 進数の 15)
----------
     1111
    1111
   1111
  1111
----------
 11100001   (10 進数の 225)
  111 1
  1

(3)
      1111  (10 進数の 15)
   * 11111  (10 進数の 31)
-----------
      1111
     1111
    1111
   1111
  1111
-----------
 111010001  (10 進数の 465)
  1111 1
  1
のように計算できる。 なおこの例では通常小さな数字で表す桁上がりの 1 を答の下に書いているので気をつけて欲しい。

  2 進数の乗算では特有の桁上がりが発生するので気をつける必要がある。 上記の例 (2), (3) において、答を求めるために加算をする段階があるが、 その時縦に 4 個以上 1 が並ぶとその和が (100)2 以上になり、 1 桁飛ばしてその隣に桁上がりが現れる。



2.18   2 の補数 (負の数の表現)

  人が 10 進数で数を表現する場合、符号と絶対値の組み合わせで正負の数を表現する。 例として (+)100, -100 などの表現となる。一般的に正の数の場合は符号を付けず省略する。

  2 進数でも同様に表現することができる。例として (+)101011, -101011 などの表現となる。 人が 2 進数で数を表現したり計算する場合はこれで問題はない。

  コンピュータ内部では、スイッチの ON, OFF で 2 進数の 0, 1 を表すが、 +, - の符号を表す仕組みがない。そのための専用の仕組みを作ろうと思えばできなくはないが、 このような符号と絶対値の組み合わせで表現する方法には次のような問題がある。 よって通常は、符号と絶対値の組み合わせを使うかわりに、 数の中に符号を埋め込んで表現する「2 の補数」という表現法が用いられる。 別の言い方をすると、コンピュータ内部で整数を表現する場合、 符号と絶対値の組み合わせでは表現していない。


2.18.1   2 の補数の表現法

  2 の補数は、(正の整数の 0, 1 を反転した値) + 1 として求める。 例として、8 桁で表現した 2 進数の整数 00001101, (13)10 の 2 の補数を求めて (-13)10 に相当する表現を作ってみる。

  00001101  (10 進数では 13)
  11110010  反転
  11110011  +1, (10 進数では -13)
  この 11110011 が -13 として妥当かどうか 13 と加算して確かめてみる。 (13)10 + (-13)10 = (0)10 なので、 同じ結果が 2 の補数で得られるかどうか調べてみる。

   00001101  (10 進数では 13)
 + 11110011  (10 進数では -13)
------------
  100000000
  結果は 100000000 となったが、 この例の最初に記したとおりここでは 8 桁で数を表現しているため、 有効なのは下位の 8 桁の 00000000 となり 10 進数の 0 に相当する結果が正しく得られた。 すなわち (13)10 に相当する 00001101 と 11110011 を足して答が 0 になったので 11110011 は (-13)10 を表す表現として妥当と言えるだろう。

  上記の例にあったとおり、2 の補数では常に桁数が重要な意味を持つので気を付ける。



2.18.2   2 の補数の様々な性質

  2 の補数では最上位ビット(左端のビット)が符号に相当する (ただし最上位ビットが独立して符号を表しているわけではない)ので、 表現可能な数の範囲に気をつける必要がある。 すなわち、ごく一部の例外の値(後述)を除いて、 (全体のビット数-1)ビットに表したい数の絶対値が収まらなければならない。

  上記の例として、8 ビットの整数は符号を考えなければ 0 〜 255 まで表現できる。 一方、2 の補数表現では -128 〜 127 が表現できる範囲となる。 どちらも表現可能な数の種類は 256 (28)だが、 2 の補数ではその半分を負数の表現に割り当てていると言える。

 0 0 0 0 0 0 0 0
        |
 1 1 1 1 1 1 1 1
  符号なし整数では 8 ビットすべてが数の表現に割り当てられ 0 〜 255 を表す。
2 の補数では左端の 1 ビットが符号、 7 ビットが数の表現に割り当てられ -128 〜 127 を表す。 ただしこの 1 ビット, 7 ビットはそのような解釈ができるというだけで、 それぞれが独立して決まるものではない。

  符号ビットは表現する数が正のとき 0 に、負のとき 1 になる。

  2 の補数表現の特徴は以下のようになる。 先に出てきた符号と絶対値の組み合わせを使う場合の問題とちょうど逆の特徴がある。

  2 の補数の 2 の補数を求めるともとの数に戻る。

例
   00001111 (15)
   11110000 反転
   11110001 +1, (-15)

   11110001 (-15)
   00001110 反転
   00001111 +1, (15)


2.18.3   桁数の重要性

  2 の補数では桁数や符号ビットを考慮せずに適当に計算すると間違った結果になる。 例として、(1101)2, (13)10 の 2 の補数表現をいくつかの桁数で求めて比較する。

(1) 4 ビットの場合 | (2) 5 ビットの場合 | (3) 6 ビットの場合
                   |                    |
  1101  もとの数   |   01101  もとの数  |   001101  もとの数
  0010  反転       |   10010  反転      |   110010  反転
  0011  +1         |   10011  +1        |   110011  +1
                   |                    |
    間違い         |      正しい        |       正しい
  (1) の結果の 0011 は符号なし整数としても 2 の補数としても (3)10 であり (-13)10ではない。 (2),(3) の結果はいずれも (-13)10 を表す 2 の補数として正しい表現である。 この場合、もとの数 (13)10 の絶対値を表すのに 4 ビット必要であるが、(1) は桁数や符号ビットを考慮せずにそのまま 2 の補数を求めたため間違ってしまった。 このように 2 の補数では符号を表すために最低でも 1 ビットの余裕が必要である。



2.18.4   加算による減算の実現

  2 の補数を使用する利点の一つとして減算が加算で実行できることがある。 例として 40 - 15 を計算したい場合、15 の 2 の補数 -15 を求めておいて、 もとの計算を 40 + (-15) で置き換えることができる。すなわち、 2 の補数を用いれば減算回路を用意する必要がない。 減算回路は複雑であるが、 2 の補数は 0/1 の反転と 1 を加算する回路で実現できるので、 コンピュータ内部の回路の削減に効果がある。

例  40 - 15 = 40 + (-15) = 25

   00001111 (15)
   11110000 反転
   11110001 +1, (-15)

   00101000 (40)
 + 11110001 (-15)
-----------------
  100011001 (25)

例  3 - 15 = 3 + (-15) = -12

   00000011 (3)
 + 11110001 (-15)
-----------------
   11110100 (-??)

11110100 がいくつであるかは 2 の補数を求めてみればわかる。

   11110100 (-??)
   00001011 反転
   00001100 +1, (12) したがってもとの数は (-12) とわかる


2.18.5   桁数と表現可能な数の範囲の関係

  n ビットの 2 の補数では -2n-1 〜 2n-1-1 まで表現できる。この時、
1111111111 = -1
1111111110 = -2
1111111101 = -3
1111111100 = -4
  ...
1000000010 = -2^(n-1) + 2
1000000001 = -2^(n-1) + 1
1000000000 = -2^(n-1)
という数が対応する。簡単に言うと、すべて 1 が並ぶと -1 になり、 1 の後に 0 が並ぶと負の数で絶対値最大の -2n-1となる。

  例として、以下では 4 ビットで表した場合の符号なし整数と 2 の補数の一覧を示す。 負の数の表現部分では、大小関係が符号なし整数と反転する特徴がある。


2 進数, 符号なし整数, 2 の補数の対応表

2 進数 符号なし整数 2 の補数 | | 2 進数 符号なし整数 2 の補数
0000 0 0 | | 1000 8 -8
0001 1 1 | | 1001 9 -7
0010 2 2 | | 1010 10 -6
0011 3 3 | | 1011 11 -5
0100 4 4 | | 1100 12 -4
0101 5 5 | | 1101 13 -3
0110 6 6 | | 1110 14 -2
0111 7 7 | | 1111 15 -1

  n ビットの 2 の補数で表現可能な数のうち、最小の数 -2n-1 は次に示す特別な性質を持っているので扱いに気をつける。 2 番目の特徴を、例として 8 ビットの 2 の補数の最小値 10000000, (-128) を使って示す。
  10000000 (-128)
  01111111 反転
  10000000 +1, もとの値に戻ってしまう
2 の補数で表現しようとする数がこのような数に該当する場合は扱いに気をつける。



2.18.6   練習問題

  (1) 次の計算を 8 ビットの 2 の補数を用いて行ないなさい。
  1. 80 - 20

  2. 20 - 80

  3. 127 - 128



  (2) 次の計算を 8 ビットの 2 の補数を用いて行ないなさい。 結果は 2 進数と 10 進数の両方で示しなさい。
  1. 01110101 - 00110100

  2. 01001111 - 01101000

  3. 00001111 - 01111000








3   ブール代数の基礎と簡単な論理回路

  コンピュータは半導体回路を組み合わせて作られている。 ダイオードやトランジスタを組み合わせることでスイッチを構成することができ、 スイッチの ON / OFF を 2 進数の 1, 0 に対応させることで、 コンピュータ内部で 2 進数を表現している。 この章では、コンピュータの半導体回路と 2 進数による数の表現、 計算を結び付ける働きがあるブール代数、論理回路の基礎を学ぶ。


3.1   ブール代数

  2 個の状態 (真, 偽) のみを計算の対象とする数学の一分野として「ブール代数」がある。 ブール代数における計算を「論理演算」と呼び、 論理演算を組み合わせると「論理関数」を決めることができる。 ブール代数の計算の原理を「記号論理」と呼ぶ。 ブール代数の計算を実現する回路を「論理回路」と呼ぶ。 コンピュータは非常に複雑な論理回路であると言うことができる。

  2 進数の 1, 0 は、ブール代数の (真, 偽) に対応させることができる。 また、2 進数の計算はブール代数、論理演算で表現できる。 これは、ブール代数、論理演算を用いると入力と出力の詳しい関係まで定義、 記述することが可能なためである。 逆にブール代数、論理演算を 2 進数の計算で表現するということは行なわれない。

2 進数の          ブール代数の        回路内のスイッチ

 (1, 0)    ←→    (真, 偽)    ←→    (ON, OFF)

 計算              論理回路           半導体回路
  コンピュータの設計は、非常に大規模な論理回路の組み合わせを考えることだといえる。



3.2   真と偽の値の様々な表現

  ブール代数における真と偽の値は場合によって様々な表現がされる場合がある。 ここでそれらの表現をまとめて示す。 次の図で、横一列はすべて同じ値を表す。 1, 0 がもっとも頻繁に使用され、次に T, F がよく使用される。

真  1  True   T

偽  0  False  F


3.3   代表的な論理演算

  論理演算は入力に対する出力を規定することによって決めることができる。 まずここでは 2 入力 (2 変数) の場合を取り上げる。 後に 3 入力、更に任意の n 入力の場合を取り上げる。 入力の数に関わらず出力は 1 個 (1 出力) である。 出力が枝別れした場合は同じ値がコピーされる。


3.3.1   凡例, ここには演算の名前を書く

  以下の 2 つの項目で式の内容を示す。
○ 入力の変数の名前を A, B とした時の記号表現、式の表現をここに書く。例 A ? B
○ その演算がどのような意味を持っているか文章で説明する。


  次の表は入力と出力の関係を表の形式で表したものである。 このような表を論理演算の「真理値表」と呼び、論理演算では重要な意味を持つ。 真理値表を正しく書けば、その論理演算の入出力関係が一意に定まる。

 入力   出力
 A  B | A ? B
--------------
 0  0 |   0
 0  1 |   0
 1  0 |   0
 1  1 |   0
  次の図は論理演算を図で表す時に使う記号で「MIL 記号」(ミル記号) と呼ばれる。 論理回路を図で表現する時は、各演算の MIL 記号を並べて描き、 必要なところを線で接続することで回路全体の構成を示す。



例 : MIL 記号



3.3.2   論理積 AND

  式の内容
○ A・B または AB
○ A が真かつ B が真(のとき出力が真)。A,B 両方とも真(のとき出力が真)。
その他の場合は出力が偽。


 入力   出力
 A  B | A・B
--------------
 0  0 |   0
 0  1 |   0
 1  0 |   0
 1  1 |   1


AND の MIL 記号



3.3.3   論理和 OR

  式の内容
○ A + B
○ A または B が真(のとき出力が真)。A,B どちらかが真(のとき出力が真)。
その他の場合は出力が偽。


 A  B | A + B
--------------
 0  0 |   0
 0  1 |   1
 1  0 |   1
 1  1 |   1


OR の MIL 記号



3.3.4   否定 NOT

式の内容
   _
○ A (この演算は入力が 1 個)
○ A が真のとき出力が偽、A が偽のとき出力が真。入力の真偽を反転する。
  A ではないという感じで、入力の値を否定する。
          _
  A   |   A
--------------
  0   |   1
  1   |   0


NOT の MIL 記号


  ここまでの 3 個の論理演算 (AND, OR, NOT) が、 基本の論理演算でありもっともよく使用される。 また、すべての論理演算はこの 3 個の論理演算の組み合わせで表現できる。

  次に、上記の 3 個の基本論理演算に次いでよく使用される論理演算を示す。


3.3.5   排他的論理和 EXOR, XOR

  式の内容
○ A +O B
○ A == B のとき出力が偽、A != B のとき出力が真。
A と B が等しいとき出力が偽、A と B が異なる時出力が真。
※ 排他的論理和の演算子は正しくは ○ の中に + を書くが、 このページでは対応する適切なフォントがないため + の横に O を描いて表すことにする。

 入力   出力
 A  B | A +O B
--------------
 0  0 |   0
 0  1 |   1
 1  0 |   1
 1  1 |   0

○ OR と最後だけが異なる。


EXOR の MIL 記号



3.3.6   論理積否定 NAND

式の内容
   ____        __
○ A・B または AB
○ A が真かつ B が真(のとき出力が偽)。A,B 両方とも真(のとき出力が偽)。
   その他の場合は出力が真。AND の否定。 
        ____
 A  B | A・B
--------------
 0  0 |   1
 0  1 |   1
 1  0 |   1
 1  1 |   0


NAND の MIL 記号



3.3.7   論理和否定 NOR

式の内容
   _____
○ A + B
○ A または B が真(のとき出力が偽)。A,B どちらかが真(のとき出力が偽)。
   その他の場合は出力が真。OR の否定。 
        _____
 A  B | A + B
--------------
 0  0 |   1
 0  1 |   0
 1  0 |   0
 1  1 |   0


NOR の MIL 記号




3.4   ブール代数の定理

  ブール代数における様々な定理を以下に示す。これらの定理は式を簡単な形に書き直す時、 式を変形する時の項の置き換えなどに活用できる。


3.4.1   論理和に関する定理

 A + 0 = A   … (1)
 A + 1 = 1   … (2)
 A + A = A   … (3)


3.4.2   論理積に関する定理

 A・0 = 0   … (4)
 A・1 = A   … (5)
 A・A = A   … (6)


3.4.3   否定に関する定理

 =
 A = A      … (7)
     _
 A + A = 1  … (8)
    _
 A・A = 0   … (9)


3.4.4   交換法則

  変数の順番は結果に影響を与えない。

 A + B = B + A  … (10)
 A・B = B・A    … (11)


3.4.5   結合法則

  同種の論理演算を行なう場合は演算の順番は結果に影響を与えない。

 (A + B) + C = A + (B + C)  … (12)
 (A・B)・C = A・(B・C)      … (13)
  * 論理演算における括弧は、通常の数学の式と同様に括弧の中を先に計算することを表す。



3.4.6   分配法則

 A・B + A・C = A・(B + C)     … (14)
 (A + B)・(A + C) = A + B・C  … (15)
  * AND, OR が混在する場合は AND の優先順位が高い(先に計算する)。



3.4.7   吸収法則

 A・(A + B) = A   … (16)
 A + A・B = A     … (17)


3.4.8   ド・モルガンの定理

 _____   _  _
 A + B = A・B   … (18)
 ____   _   _
 A・B = A + B   … (19)


3.4.9   その他

  以下は定理ではないが間違え易いところなので記しておく。 下の 2 個の式の右辺と左辺は一致しないので注意する必要がある。 例えば (20) の左辺では A + B を求めてからその結果を否定する。 右辺は A, B の否定を求めてからその結果の OR を求める。 演算の順序が異なり、また真理値表も異なる。

 _____    _   _
 A + B != A + B   … (20)
 ____    _  _
 A・B != A・B     … (21)


3.4.10   定理の証明

  これらの定理は、いずれも右辺と左辺の真理値表を書いて、 それらの一致を示すことで証明ができる。

  例として、(1),(2),(3),(4),(5),(6) の関係式の真理値表を示す。 いずれも変数が 1 個なので入力の値は 2 種類だけとなる。 個別に真理値表を書くこともできるが、簡単な内容なので 6 個まとめて示す。

 A | 0 | 1 | A + 0 | A + 1 | A + A | A・0 | A・1 | A・A
--------------------------------------------------------
 0 | 0 | 1 |   0   |   1   |   0   |   0  |   0  |   0
 1 | 0 | 1 |   1   |   1   |   1   |   0  |   1  |   1
  真理値表から、 6 個の関係式はすべての入力に関して右辺と左辺の出力が一致することがわかる。

  2 番目の例として、分配法則 (14) の関係式の真理値表を示す。

 A  B  C | A・B | A・C | A・B + A・C | B + C | A・(B + C) 
----------------------------------------------------------
 0  0  0 |   0  |   0  |      0      |   0   |     0
 0  0  1 |   0  |   0  |      0      |   1   |     0
 0  1  0 |   0  |   0  |      0      |   1   |     0
 0  1  1 |   0  |   0  |      0      |   1   |     0
 1  0  0 |   0  |   0  |      0      |   0   |     0
 1  0  1 |   0  |   1  |      1      |   1   |     1
 1  1  0 |   1  |   0  |      1      |   1   |     1
 1  1  1 |   1  |   1  |      1      |   1   |     1
  真理値表から、8 個の入力のすべての組み合わせにおいて、 右辺と左辺の出力が一致することがわかる。 よって分配法則 (14) は成立する。

  3 番目の例として、ド・モルガンの定理 (18) の関係式の真理値表を示す。

                _____   _   _   _  _
 A  B | A + B | A + B | A | B | A・B
-------------------------------------
 0  0 |   0   |   1   | 1 | 1 |   1
 0  1 |   1   |   0   | 1 | 0 |   0
 1  0 |   1   |   0   | 0 | 1 |   0
 1  1 |   1   |   0   | 0 | 0 |   0
  真理値表から、4 個の入力のすべての組み合わせにおいて、 右辺と左辺の出力が一致することがわかる。 よってド・モルガンの定理 (18) は成立する。




3.5   3 変数の論理演算


3.5.1   3 変数の論理積 AND

  式の内容
○ A・B・C または ABC
○ A が真かつ B が真かつ C が真(のとき出力が真)。A,B,C すべて真(のとき出力が真)。
その他の場合は出力が偽。


 A  B  C | A・B・C
-------------------
 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


3 変数の AND の MIL 記号



3.5.2   3 変数の論理和 OR

  式の内容
○ A + B + C
○ A または B または C が真(のとき出力が真)。A,B,C のどれかが真(のとき出力が真)。
その他の場合は出力が偽。


 A  B  C | A + B + C
---------------------
 0  0  0 |     0
 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 |     1


3 変数の OR の MIL 記号



3.5.3   n 変数の論理演算

  上記 3 変数の AND, OR の他にも様々な 3 変数の論理演算があり、 更に入力の変数を任意の n 個に拡張した n 変数の論理演算も存在する。 しかしすべてを一度に理解することは難しいので、ここでは対象を限定する。 この科目では、2 変数の論理演算は最初に登場した 6 個、 3 変数の論理演算は上記 AND, OR の 2 個だけを対象とする。

  参考までに、 n 変数の論理演算では 2n通りの入力の値の組み合わせがある。




3.6   一般的な論理式、論理関数

  ここまでに登場した 2 変数、3 変数の論理演算を組み合わせると、 様々な論理式、論理関数を表現できる。 以下ではこのような一般的な論理式、論理関数について、真理値表を求める、 論理式を求める、回路図を求めるといった課題を通して理解を深める。

  例題 (1) 次の論理演算の真理値表を示しなさい。また MIL 記号による回路図を示しなさい。

     _   _
(1) AB + AB
  答 (1) の真理値表と回路図

  真理値表は次のように書く。 まず入力の組み合わせをすべて書く。 今回の問題では入力が A, B の 2 個なので、 0 0 から 1 1 まで 4 種類の組み合わせを次の順番で書く。 書く順番も下記のように書くのが望ましい。 その後は、式に現れる項を順に作っていき、 最後にそれらを OR で結合することで完成する。

  式の最初の項で B の否定が必要なのでその欄を書く。 暗算でできる場合は省略することが可能。

        _
 A  B | B
----------
 0  0 | 1
 0  1 | 0
 1  0 | 1
 1  1 | 0
  次に A と B の否定の AND の欄を書く。

        _    _
 A  B | B | AB
---------------
 0  0 | 1 |  0
 0  1 | 0 |  0
 1  0 | 1 |  1
 1  1 | 0 |  0
  同様に A の否定、及び A の否定と B の AND の欄を書く。

        _    _   _   _ 
 A  B | B | AB | A | AB
------------------------
 0  0 | 1 |  0 | 1 |  0
 0  1 | 0 |  0 | 1 |  1
 1  0 | 1 |  1 | 0 |  0
 1  1 | 0 |  0 | 0 |  0
  最後に、(A と B の否定の AND) と (A の否定と B の AND) を OR で結合して完成する。

        _    _   _   _     _   _
 A  B | B | AB | A | AB | AB + AB
----------------------------------
 0  0 | 1 |  0 | 1 |  0 |    0
 0  1 | 0 |  0 | 1 |  1 |    1
 1  0 | 1 |  1 | 0 |  0 |    1
 1  1 | 0 |  0 | 0 |  0 |    0
  回路図を描く時は、一般的には式中の AND の項を順に描いて、最後にそれらを OR で連結する。 ただし、式中に括弧が使用されていて OR の演算を AND よりも先に行なう必要がある時は、 描く順番も異なってくる。

  今回の問題は、AND の項を OR で連結する標準的な形なので、 先に必要な AND の素子を用意して OR で連結すればよい。 結果は次のようになる。



例題 (1) の回路図

  例題 (2) 次の論理演算の真理値表を示しなさい。また MIL 記号による回路図を示しなさい。

      _
(2) ABC + AC
  答 (2) の真理値表と回路図

           _     _          _
 A  B  C | C | ABC | AC | ABC + AC
-----------------------------------
 0  0  0 | 1 |  0  |  0 |    0
 0  0  1 | 0 |  0  |  0 |    0
 0  1  0 | 1 |  0  |  0 |    0
 0  1  1 | 0 |  0  |  0 |    0
 1  0  0 | 1 |  0  |  0 |    0
 1  0  1 | 0 |  0  |  1 |    1
 1  1  0 | 1 |  1  |  0 |    1
 1  1  1 | 0 |  0  |  1 |    1


例題 (2) の回路図

  例題 (3) 入出力の関係が次の真理値表で表される論理関数の式を示しなさい。 また MIL 記号による回路図を示しなさい。

 A  B  C | 出力
----------------
 0  0  0 |   0
 0  0  1 |   0
 0  1  0 |   1  … (a)
 0  1  1 |   0
 1  0  0 |   1  … (b)
 1  0  1 |   1  … (c)
 1  1  0 |   0
 1  1  1 |   1  … (d)
  答 (3) の論理式と回路図

  ※ 論理式の表示で複数の否定が連続する場合は、 このページでは以下のように少し間隔を空けることで分かれていることを示すことにする。

_ _    _ _    _
ABC + AB C + ABC + ABC
  このような形式の問題は、 出力が 1 になっている部分の入力に注目することで、 機械的な操作で論理式を求めることができる。

  例として、上記 (a) の行に注目すると入力が 0 1 0 となっている。 ここで 0 の場合は変数名に否定を加えて、1 の場合はそのままにして変数名を並べると、

 _ _
 ABC
  という表現が得られるが、これが (a) の出力に対応する項となる。 同様に、(b),(c),(d) の各行の入力に注目すると、

  _ _    _
 AB C , ABC , ABC
  の 3 個の項が得られるが、これらの項を OR で連結すると答が得られる。



例題 (3) の回路図

  例題 (4) 次の回路図で表される論理回路の論理式と真理値表を示しなさい。



例題 (4) の回路図

  答 (4) の論理式と真理値表

  回路図の左上、左中、左下の AND の入力を見ると、 これらの素子がそれぞれ次の演算を実現していることがわかる。

     _ _       _        _
左上 A B, 左中 BC, 左下ABC
  したがってこれら 3 個の演算が OR で結合されているので、 最終的な論理式は次のようになる。

_ _   _     _
A B + BC + ABC
           _   _   __   _     _    __   _     _
 A  B  C | A | B | AB | BC | ABC | AB + BC + ABC
-------------------------------------------------
 0  0  0 | 1 | 1 |  1 |  0 |  0  |      1
 0  0  1 | 1 | 1 |  1 |  1 |  0  |      1
 0  1  0 | 1 | 0 |  0 |  0 |  0  |      0
 0  1  1 | 1 | 0 |  0 |  0 |  0  |      0
 1  0  0 | 0 | 1 |  0 |  0 |  0  |      0
 1  0  1 | 0 | 1 |  0 |  1 |  1  |      1
 1  1  0 | 0 | 0 |  0 |  0 |  0  |      0
 1  1  1 | 0 | 0 |  0 |  0 |  0  |      0


3.7   論理回路による加算器の設計

  加算器とは加算を行なう回路を表す。 以下では論理回路を組み合わせて 2 進数の加算を行なえる回路、簡単な計算機を構成する。 はじめに機能は限定されるが内容が単純でわかりやすい半加算器を構成する。 その後、半加算器を拡張して必要な機能をすべて備えた全加算器を構成する。 半加算器、全加算器はどちらも 2 進数 1 桁の加算を行なうことができる。 最後に半加算器、全加算器を必要な個数組み合わせることで、2 進数の複数桁加算器を設計する。


3.7.1   半加算器

  2 進数 1 桁の加算は次のようになる。

0 + 0 = 0, 桁上がり 0
0 + 1 = 1, 桁上がり 0
1 + 0 = 1, 桁上がり 0
1 + 1 = 0, 桁上がり 1
  ここで、2 個の入力を変数 A, B で、出力 を S で、桁上がりの出力を C で表すことにすると、 上記の入出力の関係は次の真理値表で表すことができる。

 A  B | S | C
--------------
 0  0 | 0 | 0
 0  1 | 1 | 0 
 1  0 | 1 | 0
 1  1 | 0 | 1
  すなわち上記の真理値表をもとにして論理式、論理回路を求めると、 それにより 2 進数 1 桁の加算が実行できることになる。

  上記の S, C をこれまでに出てきた論理演算で表すと次のようになる。 S は A, B の排他的論理和、または下記の式のように AND, OR, NOT の組み合わせでも表現できる。 C は A, B の AND となる。

              _   _
S = A +O B = AB + AB

C = AB
  S の演算を排他的論理和で表すと、次の回路図となる。



半加算器の回路図 (1)

  S の演算を AND, OR, NOT の組み合わせで表すと、次の回路図となる。



半加算器の回路図 (2)

  同じように AND, OR, NOT の組み合わせで回路を構成する場合、 次のような回路にすると必要な素子数を減らすことができる。 上記 (2) の回路では 6 個の素子を使用しているが、(3) の回路では 4 個で実現できる。 回路 (1), (2), (3) はすべて同じ入出力関係を持っている。



半加算器の回路図 (3)

  この回路が半加算器になっていることは、回路図を見ただけではわからないが、 次のように式を変形すると (3) の回路の論理式が得られる。 ただし、この式の変形はこの科目の学習範囲を越えるので、 現時点では自分でできるようになる必要はない。 ここでは参考までに示す。

 _   _     _    _   _     _    _   _      _   _
AB + AB = AA + AB + AB + BB = (A + B)A + (A + B)B =
__    __    __
ABA + ABB = AB(A + B)
  ポイントは、C の定義で AB が現れるので、 S の定義にも AB が含まれるように式を変形することで AB が共通となり、 素子数を減らすことができる。

  ここまでの内容で半加算器の回路を求めることができたが、 今後は半加算器を下記の図のように 1 個の素子として扱う。 半加算器は英語で Half Adder というが、下記図中の H.A. はその省略形である。



半加算器の回路図 (4)



3.7.2   全加算器

  半加算器によって 2 進数 1 桁の加算ができるが、実は半加算器は機能が十分ではない。 半加算器の問題は、下位桁からの桁上がり入力を考慮していないため、 そのままでは複数桁加算器に拡張できない点である。 この問題を解決するには、入力として桁上がり入力も正しく処理できるようにする必要がある。

  全加算器はこの桁上がり入力を処理できるようにした 2 進数 1 桁の加算回路である。 全加算器は 3 入力 2 出力の回路となる。 桁上がり入力を含めると 2 進数 1 桁の加算は次のようになる。

0 + 0 + 0 = 0, 桁上がり 0
0 + 0 + 1 = 1, 桁上がり 0
0 + 1 + 0 = 1, 桁上がり 0
0 + 1 + 1 = 0, 桁上がり 1
1 + 0 + 0 = 1, 桁上がり 0
1 + 0 + 1 = 0, 桁上がり 1
1 + 1 + 0 = 0, 桁上がり 1
1 + 1 + 1 = 1, 桁上がり 1
  ここで、2 個の入力を変数 A, B で、桁上がり入力を C で、出力 を S で、 桁上がりの出力を CN で表すことにすると、 全加算器の入出力関係は次の真理値表で表すことができる。

 A  B  C | S | CN
------------------
 0  0  0 | 0 |  0
 0  0  1 | 1 |  0 
 0  1  0 | 1 |  0
 0  1  1 | 0 |  1
 1  0  0 | 1 |  0
 1  0  1 | 0 |  1 
 1  1  0 | 0 |  1
 1  1  1 | 1 |  1
  すなわち上記の真理値表をもとにして論理式、論理回路を求めると、 それにより桁上がり入力も含めた 2 進数 1 桁の加算が実行できることになる。

  上記の S, CN をこれまでに出てきた基本の 3 論理演算(AND, OR, NOT)で表すと次のようになる。

    _ _    _ _   _ _
S = ABC + AB C + A BC + ABC
       _   _      _
CN = ABC + ABC + ABC + ABC
  上記の論理式に基づいて回路を構成すれば全加算器を作ることができるが、 回路を簡単にするために次のように論理式を変形する。 この式の変形はこの科目の範囲を越えるので、自分でできなくてもよい。 変形のポイントは、先に作った半加算器を部品として活用できるように、 半加算器の出力 S = A +O B, C = AB が式中に現れるようにする。

  S については次のように変形する。

    _ _    _ _   _ _                _ _       _   _  _
S = ABC + AB C + A BC + ABC = (AB + A B)C + (AB + AB)C
     _______
      _   _        _   _  _
  = (AB + AB)C + (AB + AB)C
                        _   _
半加算器の和の出力 S = AB + AB なので、これを S' とすると、
     _______
      _   _        _   _  _   _       _     _   _
S = (AB + AB)C + (AB + AB)C = S'C + S'C = S'C + S'C
  すなわち、A, B を入力とした 1 個目の半加算器の出力 S' と C を、 2 個目の半加算器で加算した和の出力 S が全加算器の和の出力となる。

  CN については次のように変形する。

       _   _      _                 _      _   _
CN = ABC + ABC + ABC + ABC = AB(C + C) + (AB + AB)C

   = AB + S'C = C' + S'C  (半加算器の出力 C = AB を C' とした)
  すなわち、A, B を入力とした 1 個目の半加算器の出力 S' と C' と、もともとの桁上がり入力 C により求めた、 CN = C' + S'C が全加算器の桁上がりの出力となる。

  以上の結果をもとにして回路図を描くと、次の回路が得られる。 半加算器 2 個を部品として使って、 あとは OR を 1 個追加するだけで全加算器が構成できる。



全加算器の回路図 (1)

  ここまでの内容で全加算器の回路を求めることができたが、 今後は全加算器を下記の図のように 1 個の素子として扱う。 全加算器は英語で Full Adder というが、下記図中の F.A. はその省略形である。



全加算器の回路図 (2)



3.7.3   複数桁加算器の設計

  全加算器、半加算器を組み合わせると複数桁加算器を構成することができる。 なおここで示す回路では原理を示すにとどめ、動作時のタイミングの問題は考慮しない。 各桁を同時に加算できるようにするには、桁上がりの処理に工夫が必要となるが、 ここでは取り上げない。

  例として、下記のような 4 桁の 2 進数の加算を行なう回路を示す。

  1011   各桁を左から A4 -- A1 とする, A4=1, A3=0, A2=1, A1=1
+ 1101   各桁を左から B4 -- B1 とする, B4=1, B3=1, B2=0, B1=1
-------
 11000   結果の各桁を左から S5 -- S1 とする


4 桁の加算器の回路図

  この回路では上から下に向けて信号が流れる。 2 進数 4 桁の加算の例と同じ位置に入力、出力信号が描かれるようにしてある。 この回路では 2 個の 4 桁の 2 進数 A4,A3,A2,A1 と B4,B3,B2,B1 を入力として、 加算の結果を 5 桁の 2 進数 S5,S4,S3,S2,S1 として出力する。 桁上がりの処理が正しく行なわれるように、全加算器、 半加算器の桁上がりの出力と入力が接続してある。

  ここでは 4 桁の加算器を例として示したが、 同じ原理で全加算器を接続することで更に多くの桁数の加算が可能となる。






4   コンピュータの構造


4.1   コンピュータに関する基礎的な知識


4.1.1   プログラム内蔵方式

  現在のコンピュータはほぼすべて「プログラム内蔵方式」と呼ばれる原理に基づいて動作するもので、 別名「ノイマン型コンピュータ」とも呼ばれる。 プログラム内蔵方式でないコンピュータも存在するが広く実用化される段階にはない。

  プログラム内蔵方式とは、コンピュータ内部に プログラム (下記参照)を記憶させておいて、その内容を順番に読み出して実行する。



4.1.2   コンピュータのプログラム

  プログラムとは、 どのようなことをコンピュータにやらせるかという命令の集まりである。 プログラムは得られる結果が複雑であっても、 その動作を決める一つ一つの動作は非常に単純である。 代表的な動作の例として、以下がある。

  単純な動作を組み合わせて希望する結果を得られるようにするのが「プログラムを作る」 (プログラミング)ということである。個々の命令でできることが非常に単純なため、 結果として実用的な仕事に使えるような複雑な動作をするプログラムは非常に多くの命令の 組み合わせとなる。例として Windows XP は 4000 万行のプログラムから構成され、 非常に規模が大きい。



4.1.3   プログラミング言語

  プログラムを作成する(書く)ための専用の言語(プログラミング言語) がこれまでに多数開発されている。 それらの言語はコンピュータの動作に直結した内容を記述するか、 人間の思考方法に近い記述をするかで分類される。 前者を低級言語、後者を高級言語と呼ぶが、この低級/高級という表現は分類を表す名前であり、 低級言語が高級言語より劣っているという意味ではない。 低級言語から高級言語までは言語の記述内容のレベルにより大きく次の 3 段階に分けられる。



4.1.4   プログラミング言語と自然言語の違い

  人間が使う言語は自然発生的で、地域の違いにより非常に多くの種類がある。 日本語、中国語、韓国語、英語、フランス語、ドイツ語、イタリア語、 スペイン語、ポルトガル語、ロシア語など。

  プログラミング言語は目的に応じて人工的に開発されたもので様々な種類があるが、 自然言語ほど多くはなく、 ある程度広く使われているものは 30 程度かと思われる。

  自然言語に対するプログラミング言語の特徴は、 (1) 曖昧さがなく表現の解釈は一通りしかない、 (2) 言語により異なるが総じて使用する語数が少ない といった点である。



4.1.5   オペレーティングシステム, OS

  オペレーティングシステム (OS) とは、人間がコンピュータの機能を利用し易いように、 コンピュータのハードウェアを管理して、 使用時に発生する様々な処理のハードウェアに関わる基本的な部分を担当するプログラムである。

  例として、文書作成のプログラムが入力された文字を画面に表示する場合、 プログラムは OS に対して文字を画面に表示して欲しいと要求を出し、 OS はそれを受け取ると関連するハードウェア(ディスプレイ)を制御して文字を表示する。

  OS が用意されていないコンピュータは、電源を入れても使用することができない。 OS はそれだけ重要な処理を実行しており、基本ソフトウェアとも呼ばれる。

  参考 : ハードウェアとはコンピュータ本体および周辺装置全般を表す名称、 物理的な装置のこと。ソフトウェアとは OS も含み、プログラム全般を表す。




4.2   コンピュータを構成する装置



コンピュータを構成する装置


4.2.1   Central Processing Unit

  英語名の頭文字を取って CPU, 日本語では中央処理装置と呼ばれる。 コンピュータの各装置の制御とデータ処理、演算を行うコンピュータの中枢である。 その機能から、制御装置と演算装置の組み合わされたものと考えることもできる。 マイクロプロセッサ、または単にプロセッサと呼ばれることもある。 外部から入力されるクロック波形と呼ばれる信号に同期して内部の処理が行われる。 現在はクロック周波数が 3 GHz を超えるものが開発されており、非常に高速になっている。



4.2.2   Main Memory Unit

  日本語では主記憶(装置)、メモリと呼ぶ。 半導体の記憶素子を集積した LSI で構成される。 コンピュータで処理する対象のデータは主にここに置かれる。 メモリはその性質から次の 2 種類に分けることができる。

  RAM は、記憶原理の違いから SRAM (Static RAM) と DRAM (Dynamic RAM) に分類することができる。 SRAM はフリップフロップという回路でデータを記録する。 特徴として速度は速いが高価である。 DRAM はコンデンサに蓄えた電荷でデータを記録する。 速度が遅い反面、集積度を上げるのが容易で安価である。



4.2.3   Input Device

  日本語では入力装置と呼ぶ。コンピュータに対してデータを入力する時に使う。 キーボード、マウス、スキャナ、デジタイザ、デジタルカメラなどが該当する。



4.2.4   OutPut Device

  日本語では出力装置と呼ぶ。 コンピュータで処理した結果を人間に提示するために使う。 CRT ディスプレイ、プリンタ、プロッタなどが該当する。



4.2.5   Secondary Memory Unit

  日本語では二次記憶装置、補助記憶装置などと呼ぶ。 プログラムやデータを記録するために使う。ハードディスクドライブ(HDD)、 フロッピーディスク(FD)、磁気テープなど様々な種類がある。 記憶容量は現在では数十 GB 程度が広く使われている。


補助記憶装置の例

メディア 記憶容量
ハードディスクドライブ (HDD) 40 GB 〜 250 GB
フロッピーディスク (FD) 1.44 MB
磁気テープ 1 GB 〜 100 GB
光磁気ディスク (MO) 128 MB 〜 1GB 程度
交換式 HDD 数 GB 程度
フラッシュメモリ 32MB 〜 2GB 程度



4.2.6   Communication Control Unit

  日本語では通信制御装置と呼ぶ。 他のコンピュータと通信をする場合の制御を行う。 モデム装置を使った通信や TCP/IP に基づく通信が該当する。 現在では 1Gbits/sec 以上の高速な通信が実用化されており、 100Mbits/sec 程度の能力の装置なら非常に安価に購入できる。 また無線通信によるコンピュータ間の通信も広く使われるようになっている。



4.2.7   主記憶装置と補助記憶装置の違い

  主記憶装置と補助記憶装置はそれぞれ異なった特徴を備えているので次の表にまとめて示す。


主記憶装置と補助記憶装置の違い

項目 主記憶装置 補助記憶装置
反応時間 高速 (10 〜 100 nsec 程度) 低速 (10 msec 程度)
記憶容量 小容量 256MB/10000yen 大容量 120GB/10000yen
記憶の保持 電源を切ると消える 電源を切っても消えない




4.3   CPU、マイクロプロセッサの機能


4.3.1   データサイズ

  n ビットの CPU という場合、一般にはレジスタ長が n ビットであることを表す。 またデータバスのサイズも n ビットであることが多い。


CPU のレジスタ長と直接扱える数値の範囲

ビット数 扱える数値の範囲
4 24 = 16
8 28 = 256
16 216 = 65536
32 232 = 4.295 × 109
64 264 = (232)2

  プロセッサの基本的な動作原理は 4 bit CPU でも、32 bit CPU でもほとんど同じである。 よってビット数の小さい古い CPU についての知識でも、 最近の高性能な 32 bit CPU, 64 bit CPU の機能の理解に役立つ。 処理能力を上げるための特別な仕組みがないため、 CPU そのものの機能を理解するための教材としてちょうどよいといえる。



4.3.2   CPU の内部構成、各部の機能



内部構成

  CPU には、上記の内部構成の図にあるように様々な要素があり、 相互にデータや信号をやりとりしてプログラムを実行していく。



4.3.3   CPU の動作原理



CPU とメモリ

  プログラム記憶方式に基づいて作られている CPU は、 次の手順にしたがってメモリの先頭から順に命令を読み出し、実行していく。 この動作原理は、特殊な CPU の場合を除いて、すべての CPU に共通する。

  1. PC に実行開始番地をセットする。

  2. AB に PC の内容を出力して番地を指定する。

  3. DB から、指定した番地の内容を読み取り、IR にセットする。 これをフェッチと呼ぶ。 PC ← PC + 1

  4. システム制御部により IR の内容が解読される。これをデコード と呼ぶ。

  5. 命令を実行する。

  6. 2 に戻る。




4.4   コンピュータに関連する単位


4.4.1   記憶容量

  記憶容量を表す単位は以下のようなものがあるが、これらの単位は通常の単位と異なり、 10n で表す場合と、1024n で表す場合の 2 種類の解釈があるので注意する。どちらの方式で計算されているかは、 単位を見ただけではわからないので、正確な値が必要な場合は確認する必要がある。


記憶容量の単位

単位 (読み方) 表す内容
1 kB (キロバイト) 103 または 1024 バイト
1 MB (メガバイト) 106 または 10242 バイト
1 GB (ギガバイト) 109 または 10243 バイト
1 TB (テラバイト) 1012 または 10244 バイト
1 PB (ペタバイト) 1015 または 10245 バイト
1 EB (エクサバイト) 1018 または 10246 バイト



4.4.2   時間

  時間を表す単位は以下のようなものがある。記憶容量とは異なり、 こちらは 10n だけである。1 秒より長い時間を表す場合は、 60 や 24 など不規則な値が単位の変化する区切りとして使用されるが、 1 秒より短い時間はすべて 10n が使用されるので、長さや重さと 同じように考えやすい。


時間の単位

単位 (読み方) 表す内容
1 msec (ミリ秒) 10-3
1 μsec (マイクロ秒) 10-6
1 nsec (ナノ秒) 10-9
1 psec (ピコ秒) 10-12
1 fsec (フェムト秒) 10-15






5   情報社会の倫理、法律、安全管理