がんばれ！！しんちゃん
子育てから、音楽・ビデオ鑑賞などの趣味、学問や能力開発等生活全般に関する話題を断片的に書き綴る。
コンピュータ科学基礎��
コンピュータ科学基礎��


論理演算・論理回路



(1)命題

●命題の真偽
　真　...　True　又は、1
　偽　...　False　又は、0

(2)論理演算

●論理和(OR)　...　いずれか一方が真であれば、結果が真となる








論理和の真理値表
ABA　OR　B
０００
０１１
１０１
１１１


●論理積(AND)　...　双方が真の場合のみ、結果が真となる








論理積の真理値表
ABA　OR　B
０００
０１０
１００
１１１


●排他的論理和(Exclusive OR：EOR又はXOR)　...　いずれか一方が真の場合は結果が真に、双方の値が一致した場合は結果が偽となる








排他的論理和の真理値表
ABA　OR　B
０００
０１１
１０１
１１０



●否定(NOT)　...　真偽を反転させる






排他的論理和の真理値表
ANOT A
０１
１０




(3)論理演算の公式

●分配則
　A・（B＋C）＝（A・B)＋（A・C）
　A＋（B・C）＝（A＋B）・（A＋C）

●吸収則
　A＋（A・B）＝A
　A・（A＋B）＝A
　A＋（¬A・B）＝A＋B

●ド・モルガンの法則
　¬（A・B）＝¬A＋¬B
　¬（A＋B）＝¬A・¬B

(例)　X・¬Yの真理値表は？






XYX　AND　¬Y
０００
０１０
１０１
１１０


(例)ビット数が等しい任意のビット列aとbに対して、等式a=bと a XOR同じことを表すものはどれか？

　(ア)a　AND　b　＝　００・・・０
　(イ)a　OR　ｂ　＝　１１・・１
　(ウ)a　XOR　ｂ　＝　００・・・０
　(エ)a　XOR　ｂ　＝　１１・・・１





AND　・・・双方のビットが１の場合のみ結果が１となる
OR　・・・一方のビットが１であれば結果が１となる
XOR　・・・同じビットパターンの場合、結果が０となる


a　XOR　ｂ　＝　００・・・０　は成り立つ

(4)論理回路

mil



●半加算回路　...　下位桁からの桁上がりを考慮しない1桁の2進数の加算を行う回路。

２つの入力AとBに対し、AとBの加算の結果をSに、桁上がりがあればCに出力する。








半加算回路の真理値表
入力A入力B出力C出力S
００００
０１０１
１００１
１１１０



mil_han



●全加算回路　...　下位桁からの桁上がりも考慮に入れた加算回路。

半加算回路を組み合わせることで、下位桁からの桁上がりを考慮した2進数1桁の加算を行うことができる。
最下位桁は半加算回路、それ以外を全加算回路として構築できる。
加算回路があれば、負の数を補数表示することにより減算も可能になり、加算を繰り返すことで乗算を、減算を繰り返して除算を行うことが可能にる。

mil_zen


(5)シフト演算

ビット列に対する演算も1ビットごとに独立した演算と考えればよく、この場合、算術演算と異なり、桁上がりを考慮する必要がない。
なお、ビット列を右や左に移動(シフト)することによって演算(2x倍のみ)を行うシフト演算がある。









A・Bのビット演算
Ａ０１０１０１０１
・・・・・・・・
・・・・・・・・
・）Ｂ００１１１１００
______________________________
０００１０１００












A＋Bのビット演算
Ａ０１０１０１０１
・・・・・・・・
・・・・・・・・
+）Ｂ００１１１１００
______________________________
０１１１１１０１


●論理シフト演算
論理シフトは、指定されたビット数だけ全体をシフトし、空いたビットには０を挿入する。
右にｎビットシフトすると数値を２−ｎ倍、左にシフトすると数値を２ｎ倍にすることができる。
ただし、値がオーバフロー、またはアンダフローを起こさない場合に限る。








A＋Bのビット演算
１００１００１０・・・146
右に１ビットシフト（×２−１）↓↑アンダフローされるビット
０１００１００１・・・73
↑挿入されたビット


●算術シフト演算
符号ビット(一番左のビット)を固定することで、負の数のシフト演算も可能にする。
右シフトした場合は、符号ビットと同じ値を空いたビットに挿入する。
左シフトの場合は、空いたビットに０を挿入する。






１１１１００００・・・-32
右に１ビットシフト（×２−１）↓↑アンダフローされるビット
１１１１００００・・・-16
↑挿入されたビット








１１１０００００・・・-32
左に１ビットシフト（×２１）　↓　↑オーバフローされるビット
１１００００００・・・-16
↑挿入されたビット


●シフト演算の組み合わせによる計算

シフト演算では、2n倍しかできないが、シフト演算を組み合わせることによって、様々な演算を行うことができる。
例えば、５倍したい場合は、２ビット左シフト(２2＝４倍)したものと元の値を加算すれば丁度５倍になる。

(例)32ビットレジスタに(ABCD)16が入っているとき、2ビットだけ右に論理シフトしたときの値は？

まず、2進数に変換する。
(ABCD)16　→　(1010　1011　1100　1101)2

次に、右に2ビット論理シフト演算をする。
(1010　1011　1100　1101)2　→　(001010　1011　1100　1101)2
2進数を１６進数に戻す。
(001010　1011　1100　11)2　→　(2AF3)16

構文と数式の表現



(1)BNF(Back-Naur Form)

つづく
2006/10/01(日) 19:14:25| 情報処理| トラックバック：0 コメント：0
コンピュータ科学基礎��
普段使わないことは、すぐに忘れてしまうので、おさらいをしよう。

●16進数から10進数への変換
(2D.8)16
各桁の値に、桁の重みを乗じる。

2×161+13×160+8×16-1
=45.5

●2進数から10進数への変換
(10110110)2
2進数の各桁の重みを乗じる。





10桁目9桁目8桁目7桁目6桁目5桁目4桁目3桁目2桁目1桁目桁位置
29282726252423222120桁の重み
512256128643216842110進数の値




●10進数から2進数への変換

(23.625)10
計算による基数変換



　□　 □ 　□ 　□ 　□　.　□ 　□ 　□
　16　8　4　2　1　0.5　0.250.125

23.625の中には、16が1つ取り出せるので、先頭は、1になり、残りは23.625-16=7.625となる。
次は、7.625は、8より小さいので、0になり、その次は、4が取り出せるので1となり、7.625-4=3.625。
この操作を残りが0になるまで繰り返すと、10111.101となる。


(23)10

2で割り、商と余りを求めことを繰り返す。

23÷2=11 ...1
11÷2= 5 ...1
5÷2= 2 ...1
2÷2= 1 ...0

最後の商と余りを(逆さまに)並べる。

10111


(0.625)10

2を掛け、積の小数部分に、また2を掛けることを0になるまで繰り返す。

0.625×2=1.25
0.25 ×2=0.5
0.5 ×2=1.0

0.の後に積を(上から)並べる。

0.101


●2進数と16進数の変換
(11000011.0100)2




11000011.0100
C3.4


なので、C3.4

負数の表現
補数には、「基数の補数」と「基数 -1の補数」があり、基数の補数が負の数として扱える。
補数を使って負の値を表すときは、表現できる値の範囲が狭まる。




正の数のみ0〜99
補数使用正の数(0〜49)、負の数(-1〜-50)


●n進数のnの補数の求め方

(36)10の補数64を求めるには、





99
99-36=63...9の補数
63+1=64...10の補数


(0011)2の2の補数を求めるには、




1010　を全部反転して、0101...1の補数
0101 + 1 = 0110 1を足す...2の補数


数値の表現範囲
1バイト(8bit)では、0000 0000 〜 1111 1111までの256種類。
負の値を2の補数表示で表した場合、-128〜127までの値を表現できることになる。




・正の数だけの場合...0〜2n-1
・負数に2の補数表現を使った場合...-2n-1〜2n-1-1









表示(2進数)表示(16進数)値(10進数)
0111　11117F127　(MAX)
0000　0001011
0000　000000.0
1111　1111FF-1
1000　000080-128　(MIN)


●10進表示の桁数Dと2進表示の桁数Bの関係


















ある桁数の表現可能な最大値は「基数桁数-1」で求めることができる。
凡その計算でよいので、「基数桁数」としておく。

10進数の表現可能な桁数xと2進数の表現可能な桁数yは、

10x = 2y
　が成り立つ。
2y=log1010x
そして、

10x=log102y

なので

log1010x=log102y

(log1010は、1なので)

x=ylog102

D≒Blog102




logaxn = nlogax


「100000の対数」を log10100000　と表記する。
log10100000=5
になる。
これは、「10を何乗したら、100000になるか」を表している。
105=100000だから、5である。


２を底とする対数
23=8　は、　log28=3　となる。
これは、「底2を何乗したら8になるか」を表す。






浮動小数点数

「仮数×基数桁数」で表す。
(例)(999)2は、
不動小数点表記を用いて3桁のうち2桁を仮数、1桁を指数とすれば、
最大で99×109の数値を表現できる。

指数を負数にすることで、小さな数も表現可能。

●不動小数点表記の正規化

有効桁数とは、信頼できる数値の桁数。
(例)



0.001×103有効桁数は1
0.100×101有効桁数は3


浮動小数点表記の表現として、有効桁数が多い方が望ましく、有効な数字の前のゼロは取り除き、有効桁数を増やす作業を正規化と呼ぶ。
小数点の位置を動かして、指数を変更する。

0.001×103を正規化すると、0.100×101


●浮動小数点数の表現形式
コンピュータによって異なる。
1. IEEE方式(標準)






IEEE方式の浮動小数点数の仕様
1ビット8ビット23ビット
SEM

S：仮数部の符号(0が正、1が負)

E：指数部(イクセス表記であり、実際の値は127を引いた値)

M：仮数部(1.Mの形式に正規化されている)

基数：2

式：(-1)s×2E-127×(1+M)


イクセス表記とは、本来8ビットで表現できる値(0〜255)に対し、元の値に127を加算することで、-127〜128までの表現を可能としている。
仮数部が1.Mの形式なのは、仮数部の桁数を拡大するため。
正規化して、0.1xxx...となった場合、仮数部の先頭ビットは、1となる。
1.xxx...とすることによって、整数部の1を仮数部から省いている。
このため、仮数部で表現できる桁数が1桁増えている。

(例)(28)10の場合

仮数部を2進数にする　：　(28)10　→　(111000)2
仮数部の正規化　：　(111000)2×20　→　(1.1100)2×24
指数部をイクセス表記に　：　24　→　2131




SEM
010000111100　0000　0000　0000　0000　0000



2. 試験によく出る方式





試験で出題される浮動小数点数の仕様
1ビット7ビット24ビット
SEM

S：仮数部の符号(0が正、1が負)

E：指数部(2の補数表示)

M：仮数部(0.M)

基数：16

式：(-1)s×16E×(M)


試験によく出題される方式では、指数部は、イクセス表記ではなく、2の補数表示を使用している。
基数が16進数のため、仮数も16進数で考える。
仮数部の1の前に0があっても、正規化のために1の前の0はとらない。

(例)(28)10を浮動小数点数で表す。
仮数部を16進数に　...　(28)10　→　(1C)16
仮数部の正規化　...　(1C)16×160　→　(0.1C)16×162
指数部　...　2




SEM
000000100001　1100　0000　0000　0000　0000


(例)実数aを　a=f×reと表す浮動小数点表記

　f　...　仮数
　r　...　基数
　e　...　指数


●誤差

１．丸め誤差　...　仮数部分の桁数に限度があることによって、最小桁より小さい部分について四捨五入や切り上げ、切捨てを行うために生ずる誤差のこと。

２．情報落ち　...　絶対値が大きい値に対し、極端に小さい値を加減算すると、小さい方の値が計算結果から欠落すること。絶対値の小さい方から順に加算することで回避することができる。

(例)0.100×104に0.100×101を加算する。

　0.100×104+0.100×101
=0.100×104+0.0001×104
=0.100×104+0.000×104
=0.100×104

となり、0.100×101の情報がアンダフローにより失われる。
数多くの数値の加算を行うなら、絶対値の小さなものから計算すると、値が大きくなり、指数部の値が大きくなれば、情報落ちを防ぐことができる。

３．桁落ち　...　絶対値の差が小さい値同士の減算において、演算結果の有効桁数が少なくなる誤差のこと。

４．打ち切り誤差　...　循環小数などの計算を、途中で打ち切ったために発生する誤差。


＊循環小数とは、n進数における小数点以下の表記が次のようになる形式。
　0.a1a2...an{b1b2...bm}

循環小数は分数で表せる。
1/3＝0.333333333333・・・・・
1/7=0.142857142857142857・・・・

■様々なデータ表現

●2進化10進数
金額や数量を表す際に10進数を2進数に基数変換しないで、10進数1桁をそのまま2進数に変換して取り扱う方法。
BCD(Binary Coded Decimals)コードは、4桁の2進数で10進数の1桁を表す。
BCDコードは、符号の概念がない。

符号の概念を持つ2進化10進数に、ゾーン10進数とパック10進数がある。

ゾーン10進数　...　1桁を8ビットで表し、上位4ビットをゾーン部と呼ぶ。数値は下位4ビットに格納される。
最後の1桁のゾーン部が符号を表す。

パック10進数　...　1桁の数字を4ビットで表し、最下位の4ビットで符号を表す。
(例) (102)10の場合





ゾーン10進数
111100011111000011000010
ゾーン部1ゾーン部0符号部2






パック10進数
0001000000101100
102符号部




(例)6桁の符号付き10進数をパック10進表記法で表すのに必要なバイト数は？
　1桁を4ビットで表すので、
　6桁　×　4ビット　+　符号ビット(4ビット)　=　 28ビット
　28ビットを格納するために必要なバイト数は、
　28ビット　÷　8ビット　＝　3.5　≒　4バイト



●文字の表現
[JISコード]　日本工業規格で、規格化された8ビットの文字コード体系。256種類が定められている。16ビットのJIS漢字コードというのもある。

[シフトJISコード]　JISコードをベースにした文字コード体系で、16ビットの漢字コードのデータと8ビットのコードが混在している場合でも識別できるようにした。
SI(シフトイン)、SO(シフトアウト)という特別コードを使って、16ビットの漢字コードの始まりと終わりを示しており、漢字コードの上位8ビットを8ビットコードと干渉しない領域に割り当てることで、SI及びSOなしに8ビットコードと16ビットコードを識別できるようにしている。

[ASCIIコード]　ANSI(米国規格協会)で規格化された文字コード体系で、基本は7ビットだが、拡張版では8ビットとなっている。
JISコードのベースとなった。

[EBCDIC(Extended BCD Interchange Code]　IBM作成のメインフレーム(汎用コンピュータ)向けの文字コード体系。
本来は、各メーカーが拡張して日本語を使えるようにしている。

[EUC(Extended Unix Code)]　主にUNIXで利用されている文字コード体系で、拡張UNIXコードとも言う。

[Unicode]　ISO(国際標準化機構)で標準化された、世界の多くの文字を表現するための」16ビット文字コード体系。


●まとめ

(例)　(0.6875)10を2進数で表したら？

　0.6875　×　2　＝　1.375　...　1　↓
　0.375　×　2　＝　0.75　...　0　
　0.75　×　2　＝ 1.5　...　1　
　0.5　×　2　＝　1.0　...　1　

(0.1011)2

(例)　

(例)　(0.11101)2を10進数に変換するには？

(0.11101)2　×　23　=　(111.01)0　×　20

(111.01)0　=　(7.25)10


(例)　2の補数(1111110)2を元の値に戻すには？

　2の補数を取る作業と同じ手順
　1111110　→　0000001　→　0000010　=　(2)10


(例)　(0.0011)2　×　2-2の仮数部を3にするには？

　(0.0011)2　×　2-2　=　(11)2　×　2-6　=　3　×　2-6

(例)3　×　2-6を正規化(仮数部最上桁が1となるように)するには？


3　×　2-6　=　(11)2　×　2-6　=　(0.11)2　× 2-4
数値は、プラスなので、符号部は0。
指数部は、-4なので、2の補数にすると、
4　=　(0000100)2　→ 1111100
仮数部は、0.11なので、先頭から、1100 そして残りは全て 0で埋める。




符号部指数部仮数部
　0　　11111000　　1100　|　0000　|　0000　|　00 ...　00　

≫[コンピュータ科学基礎��]の続きを読む
2006/09/21(木) 21:10:06| 情報処理| トラックバック：0 コメント：0
| ホーム |
無料ホームページ アフィリエイト レンタルサーバー FC2ブログ