基礎理論(1)

基礎理論

離散数学

・データ量などを扱うもの
・コンピュータの理論回路やデータ構造、言語理論などの基礎

2・10・8・16進数

2進数・10進数・8進数16進数

2進数：コンピュータ内部での電流の有無などに
　　　　　　　よって識別されたデータ
　　　　　　　「0」と「1」で表現
10進数：通常の数字を使用した表現
　　　　　　　0～9の数字
8進数：コンピュータで扱う数量の表現方法
　　　　　　　0～7の数字
16進数：コンピュータで扱う数量の表現方法
　　　　　　　0～9の数字＋a～fのアルファベット

基数

数量を表現する際に、位取りの基準となる数のこと
10進数：10倍ごとに桁が上がり、基数は10
2進数　：基数は2、2倍ごとに桁が上がっていく
16進数：基数は16、16倍ごとに桁が上がり、
　　　　　　　「1、16、256、～の位」となる

桁の重み

10進数なら下位桁から1,10,100,1000,～と、桁が上がるごとに10倍され、2進数では下位桁から1,2,4,8,～と、桁が上がるごとに2倍される。これが「桁の重み（おもみ）」

基数変換

ある進数から別の進数に置き換えること

n進数→10進数

桁の重みに桁に書かれた数値(n)を掛け、その結果をすげて加算する

10進数→n進数

整数部：10進数をnで割って商と余りを求め、商が1になるまで繰り返し、
　　　　求めた余りと1を下位桁から並べる
小数部：10進数にnを掛けて、小数部が0になるまで繰り返し、
　　　　整数部を上から記述する

無限小数

10進数の小数部を2進数に変換時、2を掛けた演算結果の小数部が0にならない小数。 (例：(0.1)₁₀＝(0.00011001100…)₂　故に(0.1)₁₀は無限小数)
見分け方：先ず分数にして、2の累乗のみの数字で構成されていたら有限小数

2進数→8進数・16進数

小数点を基点にして、8進数であれば3桁ごと、16進数であれば4桁ごとに区切る
整数部は右→左に、小数部は左→右に区切り、それぞれを8進数or16進数に変換
※3桁(8進数)、4桁(16進数)にならない場合は、不足している桁数ぶん0を補充する

8進数・16進数→2進数

1桁ずつ2進数に変換し、記述する

基数変換
2進数→8進数：3桁に区切って、2進数の桁の重みを掛けて足す 2進数→16進数：4桁に区切って、2進数の桁の重みを掛けて足す n進数→10進数：n進数の各桁の数値と桁の重みを掛けて足す　　　　　　　(整数部、小数部共に) 10進数→n進数：10進数をnで割り、余りを下位桁から並べる(整数部) 　　　　　　　：10進数にnを掛けて小数部が0になるまで繰り返し、　　　　　　　　整数部を上から記述(小数部)

文字の表現

コンピュータでは文字を2進数の数値として扱っている。コンピュータ上で扱う文字に割り与えられた2進数コードを「文字コード」と呼んでいる。欧米では1バイトで構成するが、日本ではひらがな・カタカナ・漢字などの文字種を常用するため2バイトでコード化されている

代表的な文字コード

名称	説明
ASCII	ANSI(米国規格協会)が規格した文字コード。1バイト文字。1文字につき7ビットを使用し、8ビット目はエラー確認用のパリティ。欧文文字および欧文記号
JIS	JIS(日本工業規格)が規格した文字コード。英数字・記号などの1バイト文字とひらがな、漢字等の2バイト文字を含む
シフトJIS	JISの一種。Microsoftによって定義された。WindowsやMac OSなどで採用されており、国内で最も普及
EUC	AT&T社が規格。拡張UNIXコードともいう。主にUNIXで利用されている。2バイト文字にも対応
EBCDIC	米国IBM社が規格。8ビットの文字コード。主に汎用大型コンピュータで採用
Unicode	ISOとIECが規格。全世界の文字を2バイトで表現することで、1つのコードでほとんどの文字を収録

パリティビット

文字コードなどの誤りを検査するためのビットのこと

ビットとバイト

コンピュータで取り扱われるデータは、ビット(binary digit:bit)とバイト(byte)という単位で取り扱われ、ビットはコンピュータ内部における情報表現の最小単位で、1ビットでは"0"または"1"が格納される
データの記憶容量などを表すときに用いられる

ビットとバイト
・ビットはコンピュータ内部における情報表現の最小単位・データの容量を表す単位・1ビットでは"0"または"1"が格納される・8ビット＝1バイト

数値の表現

コンピュータ上の限られたビット数で数値を表現するための表現方法には以下のものがある

10進数の表現方法

BCD表現

BCD　(2進化10進)

2進数4桁を用いて、10進数における1桁分を表現する方法
【特徴】
●正負の符号を表現できない
●本来、2進数で4桁を使用すると16種類が表現可能だが、BCDでは0～9の10種類
　を表現している
●10進数において桁が1つ増えるごとに、BCDでは4桁増えることになる

ソーン・パック10進数

ゾーン10進数　(アンパック10進数)

1桁の数値を1バイト(8ビット)で表す方法
1バイトの上位4ビットをゾーン部といい、JISコードの場合は0011、EBCDICこーどの場合は1111が設定される
1バイトの階ビットが数値を表す
最下位桁のゾーン部は正負の符号を表す(正：1100、負：1101とすることが多い)
【特徴】
●1バイトでその数値の文字コードを表す
●数値と文字の変換が簡単に行える

パック10進数

1桁の数値を4ビットで表す方法
最下位桁の4ビットは正負の符号を表す(正：1100、負：1101とすることが多い)
桁数が偶数のときは、左端に0000を入れ、データを整数バイトで表せるようにする
【特徴】
●ゾーン10進数と比較して、必要な桁数が少なくてすむ

正負の表現方法

絶対値表現

絶対値表現は、一番左端のビットである最上位のビットを符号ビットにする正の数値であれば0、負の数値であれば1をセットする

補数表現

補数とは

ある数値の桁をひとつ繰り上げるために加算する数値のこと
(例：10進数では6＋4＝10であるから6の補数は4)

1の補数

ある正の数を表すビット列をすべて反転させた表現形式]
これを負の数として定義する
1の補数の欠点：0が00000000と11111111という二通りの表現形式を持つ

2の補数

ある正の数を表すビット列をすべて反転させ、1を加算した表現形式(1の補数で表された数に1を加えたもの)を負の数として定義する
0が二通りに表現される問題は消滅する
2の補数の最大のメリットは足し算を行うときにプラスであるかマイナスであるかによって場合分けをしなくて済むこと

2進数の減算

2の補数を使用することで、2進数の減算を加算として計算可能

表現可能な数値の範囲

2の補数の場合、nビットで表現可能な数値の範囲：－2^n-1～2^n-1－1

1の補数の求め方
　　　　各桁の1と0を反転する
2の補数の求め方
　　　　1の補数＋1
マイナスの10進数を2の補数表現する
　　　　10進数を2進数に変換し、その2進数を2の補数表現する
2の補数表現されたマイナスの2進数を10進数に変換する
　　　　最上位ビットに注目して、
　　　　　　1ならばマイナスだから2の補数を求める
　　　　　　０ならばそのまま2進数を10進数に変換する

小数の表現方法

固定小数点数

小数点の位置を特定の位置に固定して数値を表現する方法
●表現できる値の範囲がはるかに狭い
●桁落ちが起こらない
●高速に演算可能
●符号なし固定小数点数：負の数を表現できない
●符号付き固定小数点数：最上位のビットが正負の符号ビットになる

浮動小数点数

小数点の位置を移動し、より詳細な数値を実現する方法
一般的にコンピュータなどは、整数部と小数部を分けて数値管理を行い、小数部のデータ表現において浮動小数点数を用いている
浮動小数点数では、実数aを「a＝0.f×r^e」(f＝仮数、e＝指数、r＝基数)という形で表現する

名称	説明
符号部	数値が正か負かを表す。正の場合0、負の場合1
指数部	基数のべき乗を2進数で表す。負のべき乗は2の補数を使用
仮数部	小数点以下の数値を表す。正規化しておく

浮動小数点数の正規化

小数点の直後に0以外の数値が並ぶように調整して表現すること
(例：0.0023578＝0.23578×10^-2)

補数部のビット

浮動小数点数の指数部のビットは一般的に2の補数を用いる場合と「エクセス」と呼ばれる手法を使って表現する場合がある
●エクセスN指数部の負の数値を正の数値に置き換えるために63や127など、一定の数値を加算してからビット表現をする

単精度浮動小数点数

1つの数値を32ビットで表現する浮動小数点数型
一般的に、1ビットの符号部、7ビットの指数部、24ビットの仮数部の32ビットで表現する。表現できる値の範囲－3.40282×10³⁸～3.40282×10³⁸で、精度は6桁、C言語などでは「float型」などと呼ばれている

倍精度浮動小数点数

1つの数値を64ビットで表現する浮動小数点数
一般的に、1ビットの符号部、11ビットの指数部、52ビットの仮数部の計64ビットで表現する。表現できる値の範囲は－1.79769×10³⁰⁸～1.79769×10³⁰⁸で、精度は15桁

誤差

コンピュータ上で数値表現に使用できるビット数が決まっているため、演算結果に実際の数値とコンピュータで表現する数値の差「誤差」が生じる

丸め誤差

小数点以下の極めて小さい単位で値を丸めて計算した結果、計算結果と正しい値がわずかにずれること
最下位桁より小さい部分を四捨五入や切捨て、切り上げを行うときに生じる誤差

けた落ち

浮動小数点演算で、計算結果が0に極端に近くなる加減算を行ったときに、有効数字の桁数が極端に少なくなること
(例：「0.123456x10²-0.123455x10²」のような計算を行うと、「1x10^-4」となり、有効数字の桁数は7桁から一気に1桁に減少してしまう)
浮動小数点形式では常に有効数字の桁数を一定にして扱っているため、けた落ち時に不足した桁数を自動的に0で埋めてしまい、真の値との間に誤差が発生してしまう。その値を計算に使用することで大きな誤差を含んだ値が返されることがある

情報落ち

絶対値の大きさが極端に異なる数字の加・減算時に小さい値の情報が無視されること。そのことによって起きる計算の誤差
大きさが極端に異なる値を多数計算する場合、情報落ちの影響で適切な計算結果が得られないことがあるため、工夫必要となる

オーバーフロー(桁あふれ)

数値演算を行った結果の絶対値が、扱える数値の最大値を超えること
一つの数値を表現するために割り当てられた記憶容量の上限を超えた状態

アンダーフロー

浮動小数点演算処理で、計算結果の指数部分が小さくなり過ぎ、使用している記述方法では数値が表示できなくなる状態

シフト演算

ビットの位置を左や右にずらすことで、数値の乗・除算を高速に処理する方法

●左にずらす(左シフト):元の数値の2のn乗倍(2のn乗で乗算)
●右にずらす(右シフト):元の数値の2の－n乗倍(2のn乗で除算)

算術シフト

正負を考慮した数値演算を行う時に使用

a)符号ビットを除くビット列をシフトする　---①
b)はみ出したビットは切り捨てる　---①
c)空いたビット位置には
　　　　左シフト："0"　---②
　　　　右シフト：符号ビットと同じ値　---③ 　　を格納する

論理シフト

数値演算ではなく、単にビットの位置を移動するときに使用

a)符号ビットを含むすべてのビット列をシフトする　---①
b)はみ出したビットは切り捨てる　---①
c)空いたビット位置には"0"を格納する　---②

集合と論理演算

集合：ある条件に基づいてグループ化されたデータの集まりのことで「AまたはB」などの文章で表現可能。このような文章や条件式(論理式)という。ベン図により図式化することが可能

論理演算と論理回路

論理演算：複数の条件(論理)の組み合わせを条件式で表した時の演算方法
論理回路：コンピュータ内部の論理演算を担当する電子回路
　　　　　　「回路記号(MIL記号)」を使って図で表現する

論理記号

論理演算を行うときに使われる記号

代表的な論理記号
論理記号	意味	例
・　,　∧	論理積(AND)	X・Y　,　X∧Y
＋　,　∨	論理和(OR)	X＋Y　,　X∨Y
^―　,　￢	否定(NOT)	X　,　￢X
,∀	排他的論理和(EOR,XOR)	XY　,　X∀Y

順序回路と組み合わせ回路

論理回路は「順序回路」と「組み合わせ回路」に分類される

順序回路

入力値と論理回路の内部状態によって出力が決まる論理回路
フリップフロップ回路

組み合わせ回路

論理回路の内部状態とは関係なく、入力値だけによって出力が決まる論理回路

フリップフロップ回路

「0」と「1」のによって1回路に1ビットの情報を一時的に記憶できる論理回路のこと

基本的な論理演算

基本的な論理演算
名称	説明	回路記号
論理積(AND)	2つの入力値がともに1のとき1、それ以外は0を出力
論理和(OR)	2つの入力値がともに0のとき0、それ以外は1を出力
否定(NOT)	入力値が1ならば0、 0ならば1を出力

真理値表
		論理積	論理和	否定
		AND	OR	NOT
X	Y	X・Y	X＋Y	X
0	0	0	0	1
0	1	0	1	1
1	0	0	1	0
1	1	1	1	0

組合せの論理演算

基本的な論理演算を組み合わせて演算を行うことが出来る

論理演算の組合せ
名称	説明	回路記号
否定論理積 (NAND)	論理積と否定を組み合わせた論理演算 2つの入力値がともに1のとき0、それ以外は1を出力
否定論理和 (NOR)	論理和と否定を組合わせた論理演算 2つの入力値がともに0のとき1、それ以外は0を出力
排他的論理和 (EOR　,　XOR)	論理積tと論理和と否定を組合わせた論理演算 2つの入力値が同じなら0、異なるなら1を出力

真理値表
		否定論理積	否定論理和	排他的論理和
		NAND	NOR	EOR　,　XOR
X	Y	X・Y	X＋Y	X∀Y
0	0	1	1	0
0	1	1	0	1
1	0	1	0	1
1	1	0	0	0

論理演算の法則

ド・モルガンの法則

1)論理和の否定は、否定の論理積に等しい
A＋B＝A・B 2)論理積の否定は否定の論理和に等しい
A・B＝A＋B

分配則

A・(B＋C)＝A・B＋A・C
A＋(B・C)＝(A＋B)・(A＋C)

論理積の法則

A・A＝0
A・0＝0
A・1＝A

論理和の法則

A＋A＝1
A＋0＝A
A＋1＝1

設計回路(回路設計)

論理回路を組合わせて実際に必要な回路の構造を論理的に設計すること
性能、操作性、信頼性、設計効率やコストの削減も含めて設計する

半加算器と全加算器

四則計算や論理演算を行う回路を「演算回路」といい、2進数の加算を行う演算回路を「加算器」という。加算器には「半加算器」と「全加算器」がある

半加算器

2進数の加算で下位桁からの桁上がりを考慮しない加算器のこと
論理積と排他的論理和の回路の組み合わせで構成される
【特徴】
●2進数の加算を行うための、最下位のビット加算
●半加算器は2ビット以上の桁を持つ加算には使用できない

【真理値表】
入力		出力
A	B	C	S
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

半加算器回路図

全加算器

2進数の加算で下位の桁からの桁上がりを含める加算器のこと
2個の半加算器と論理和の回路の組み合わせで構成される
【特徴】
●半加算器は2ビット以上のけたを持つ加算には使用できない

全加算器回路図

【真理値表】
入力			出力
A	B	X	C	S
0	0	0	0	0
0	1	0	0	1
1	0	0	0	1
1	1	0	1	0
0	0	1	0	1
0	1	1	1	0
1	0	1	1	0
1	1	1	1	1