情報数学1 第2-2章 - Tominaga Lab, Chausson

情報数学１第3-2章
情報量と二進法での四則演算
香川大学工学部富永浩之
[email protected]
概
要
■ 自然数の記数法
位取記数法、多進法と多進法
■ 多進法の原理
切捨
切上
四捨五入
ガウス記号
■ 多進数への変換
多進数への変換
■ 多進数からの変換とホーナー法
多進数からの変換
■ 多進法の応用
あ
ホーナー法
第01節 [1] 情報量と情報量の単位
● 情報量の単位
・情報量は、その情報の存在により、何通りの異なる状態を区別できるかという尺度
・ある状態であるかないか(1か0か)を表すのに必要な情報を最小単位とする
・これを1ビット[bit]といい、ビットを表す単位記号として、小文字の頭文字 b を用いる
● ビット列
○ ビット列
0と1の数字の列
010010, 1011
・長さ nのビット列は、 n ビットの情報を表し、 2n 通りの異なる状態が区別される
○ 自由桁二進数通常の表記の二進数で、0を例外として、他は1から始まるビット列
○ 固定桁二進数二進数の先頭に0を追加した表記も許すことにし、桁を揃える
n桁の固定桁二進数をnビット二進数ともいう
1011[2]＝11[10] は4ビットの情報であり、256 通りの中で11番目の状態を表している。
2ビット二進数の 00[2]＝0[10] は、通りの中で0番目の状態を表している。
第01節 [2] ビットとバイトの単位
8 b (ビット) ＝ 1 B (バイト)
現実の計算機の構造上、8ビット単位でデータ処理が基本
1バイトの情報量は、 2^8＝256 通りの情報を区別する。
英数字は、1バイトの情報量があれば区別される。
ハードディスクやメモリの容量は、普通、バイト単位で表す。
8b＝
1B
256
16 b ＝ 2 B
65,536
24 b ＝
32 b ＝
64 b ＝
128 b ＝
3B
4B
8B
16 B
16,777,216
約43億
約1800京
約3.4×10^38
※ ASCIIコード文字(英数字)
8ビットマイコン色階調指定
※ JISコード文字(日本語文字)
16ビットDOS ハイカラー表示
※ フルカラー表示
※ 32ビットOS(Windows) IPアドレス
※ 64ビット次世代OS
※ 次世代IPアドレス
第01節 [3] 情報量の上位単位
○ キロ
1KB ＝ 1024B
※ 原稿用紙1枚と1/4(約500字)
○ メガ
1MB ＝ 1024KB
※ FDの容量 1.44MB(原稿用紙1800枚)
○ ギガ
1GB ＝ 1024MB ≒ 100万KB ≒ 10億B
※ CD-ROMの容量 0.65GB＝650MB(FD約450枚) ステレオ音声70分
○ テラ
1TB ＝ 1024GB ≒ 100万MB ≒ 10億KB ≒ 1兆B
※ ビデオ配信サーバなどの記憶容量(CD約1600枚 DVD約200枚 BD約)
○ ペタ
1PB ＝ 1024TB ≒ 100万GB ≒ 10億MB ≒ 1兆KB ≒ 1000兆B
※ 大規模データベースサーバの記憶容量
○ エクサ 1EB＝ 1024PB ≒ 100万ＴB ≒ 10億GB ≒ 1兆MB ≒ 1000兆KB
第02節 [1] 情報量と文字データ
○ 英字 52個
○ 数字 10個
○ 記号 32個
○ 空白 1個
ABCDEFGHIJKLMNOPQRSTUVWXYZ
abcdefghijklmnopqrstuvwxyz
0123456789
!?#$%&|\,.;:@'"`^~_+-*/=<>()[]{}
英語圏で必要な文字は、約100個程度
これらの文字を区別するには、27＝128 より、7ビットあれば十分
これに、エラーチェック用の1ビットを加えると、
8ビットすなわち1バイトで1文字が表される
これが、計算機がバイト単位が基本となっている理由
第02節 [2] 情報量と文字データ
英数字と記号および空白は、ASCIIコード文字と呼ばれる。
俗に、半角文字ということがある。
日本語をには、漢字、ひらがな、カタカナと文字種が多く、
1文字に2バイトが必要である。
これらは、JISコード文字と呼ばれる。俗に、全角文字ということがある。
他の言語でも、2バイト以上必要な文字をマルチバイト文字という。
● 情報量の概算
日本人約1億2000万人分の電話番号の情報量を概算しよう。
電話番号は最大11桁であり、各桁はBDCでは4ビットで表されるから、44ビットとなる。
よって、120,000,000×44÷8 ＝ 660,000,000B ≒ 660MB であり、CD 1枚程度となる。
電話番号DBとして活用するには、氏名と電話番号の組として収録する必要がある。
氏名の長さは不定であるが、漢字10字以内と仮定すれば、1人につき20バイトとなる。
よって、120,000,000×20 ＝ 2,400,000,000B ≒ 2.4GB であり、DVD 1枚程度である。
第02節 [3] 情報量と画像データ
● モノクロ画像データ ‥ 各画素(画面上のドット)の輝度情報
○
○
○
○
VGA
SVGA
XGA
SXGA
640 ×
800 ×
1024 ×
1280 ×
480 ＝ 307,200
600 ＝ 480,000
768 ＝
1024 ＝
計算機のディスプレイ上の画像は、ドット(画素)から構成されている。
各画素に白/黒の1ビットの情報量を割り当てれば、モノクロ二値の画像が表現される。
1画素に8ビットを割り当てれば、黒から白への輝度を256段階の階調として
表現することができる。これをモノクロ階調という。
第02節 [4] 情報量と画像データ
● カラー画像データ ‥ 光の三原色(RGB)の輝度情報の組合せ
○ フルカラー 24ビット(RGB 8,8,8) 約1677万色
○ ハイカラー 16ビット(RGB 5,6,5)
65536色
○
8ビット(RGB 3,3,2)
256色
色彩を表すために用いるビット数を色深度という。
人間の視覚は
緑に対する感度が高く
青に対する感度が低い
第02節 [5] 情報量と画像データ
● 第02-06節スキャナ画像の情報量
[展開]
スキャナでは、解像度の単位として、dpiが使われている。
これは、dot per inch の略であり、1インチ(2.54cm)当たりのドット数を意味している。
例えば、スナップ写真E判(11.7cm×8.3cm)を300dpiの解像度、フルカラー24ビットで取り込むと、
(11.7÷2.54×300)×(8.3÷2.54×300)×24÷8÷1024÷1024＝3.88 より
、約4MBの情報量が必要になる。
第03節 [1] 情報量と音声データ
● 音声(音波) ‥ 空気の振動(各時刻の振幅)
○ A/D変換
○ D/A変換
アナログ波形(振幅量) ⇒ 離散近似 ⇒ デジタル信号
デジタル信号(ビット列) ⇒ 連続補間 ⇒ アナログ波形
● 音声データの標本化と量子化
○ 標本化(時間的)
○ 量子化(空間的)
一定時間ごとに振幅量を記録
振幅量を離散値で近似
標本化周波数
量子化ビット数
● 音声データの情報量
○ CDの音質標本化 44,100Hz 量子化 16bit (65536段階) ステレオ2ch （左右）
○ 1秒間
○ 記録容量
○ 通信容量
44,100×16×2 ＝ 1,411,200 bit (÷8÷1024)＝ 172.2 KB
650MB 650×1024÷172.2 ＝ 3865.‥ 秒 ≒ 約64分
1,411,200÷1024÷1024＝1.34‥ ≒ 1.4 Mbps
100Mbpの通信回線で74人まで
第03節 [2] 情報量と映像データ
● 動画データの情報量
動画は、定期的な間隔で再生される静止画の列である。
動画の構成要素として再生される静止画をフレームという。
動画データが、アナログかデジタルかは、個々の静止画がアナログかデジタルかによる。
したがって、LDはアナログであり、DVDはデジタルである。
フレームを再生していく間隔すなわち標本化の周波数をフレームレートという。
人間の視覚の残像効果により、1秒間に30コマの割合で、
連続的にフレームを再生すれば、滑らかな動画として認識される。
例えば、320×240サイズで16ビットカラーの静止画データを
1秒間に30コマの割合で再生するとすれば、
1秒間に 320×240×16×30＝73,728,000 ビットで、73,728,000÷8÷1024＝9
すなわち9MBの情報量が必要となる。
動画の場合、実用的には、人間の視覚特性を考慮した大幅なデータ圧縮が必要となる。
第03節 [3] 情報量と映像データ
● 第03-05節
○ MPEG-2
マルチメディアデータの標準規格
[参考]
DVDの動画データの記録形式高品位を保ちながら高圧縮
圧縮と解凍に高性能の処理装置を要求(現在は普通のPCでもOK)
ハイビジョンのデジタルテレビ放送では、MPEG-2が用いられている。
なお、インターネット上での音声データの標準規格となっているMP3は、
MPEG-2 Layer-3 の略である。すなわち、MPEG-2規格の音声部分のみを利用している。
やや古いメディアであるビデオCDでは、MPEG-1という規格を用いている。
これは、MPEG-2より画質が劣る。
また、インターネットテレビなど、通信容量が低くてもある程度の品質を保ち、
ユーザからの操作を受け付ける双方向的な映像通信では、MPEG-4が採用されている。
なお、Windowsや各種のソフトでは、独自のデータ形式を用いている場合がある。
第04節 [1] 二進法での加法と減法
二進法での加減算は、
各桁同士の計算結果を表す加法表および減法表に基づき、
筆算の形で行う。
加法表・減法表においては、
0－1＝-1 のような1桁の数同士の単独の計算結果ではなく、
筆算の途中の各桁において、計算結果として現れる数字と、
繰上り、繰下りの有無を記入しておく。
1 1 1 0 1 1 被加数
＋
1 1 0 0 1 1 加数
↑ 1 1
1 1
繰上り
1 1 0 1 1 1 0 和
1 1 0 1 1 1 0 被減数
＋
1 1 0 0 1 1 減数
↓ 1 1
1 1
繰下り
1 1 1 0 1 1 和
第05節 [1] 二進法での乗法
二進法の乗法＝乗法表(論理積) ＋左桁シフト
×
0
1
0
0
0
1
0
1
1
1
0
1
0
1
1
1
1
0
1
1
1
0
1
1
1 0 1 0 1 1 被乗数
∧
0
1
0
0
0
1
0
1
×
1 1 1 0 1 乗数
1 0 1 0 1 1
0
1 0 1 0 1 1
∨
0
1
0
0
1
1
1
1
乗数の桁が0なら0
左シフトしながらコピー
1 0 1 0 1 1
＋
1 0 1 0 1 1
1 0 0 1 1 0 1 1 1 1 1 積
第05節 [1] 二進法での除法
1 0 1 整商
1 0 1 1 1 1 1 1 0 1 被除数
1111≧1011 より商1を立てる
1 0 1 1
1 0 0 0
0
差を求める
1000<1011 より商0を立てる
1 0 0 0 0
1 0 1 1 除数より小となるまで
1 1 0 剰余
第06節ロシア乗算法と二分累乗法
43 × 29
＋
101011 × 11101
43
29
1
101011
1
86
14
0
＋
172
7
1
101011__
100
＋
344
3
1
101011___
1000
＋
688
1
1
1247
2倍
43×29 ＝
＝
＝
＝
＝
101011____ 10000
10011011111 11101
半分
奇偶
二進数での乗算
43 × 1 1 1 0 1 [2]
43 × (1＋4＋8＋16)
43 ＋ (43×2)×2 ＋ (43×4)×2
43 ＋ 172 ＋ 344 ＋ 688
1247
＋ (43×8)×2
第07節整数の記数法
● 符号付二進数 ‥ 符号桁＋数値桁 in 固定桁
・整数の記数法には、符号と数値が必要
・符号付二進数では、符号も含め、ビット列(0/1のみ)として整数を表記
・上位桁の0を省略しない、固定長のビット列で考える
・最上位での繰上りは、桁溢れ(オーバーフロー)となる
・固定桁の最上位桁を符号桁に使う (0 正 1 負)
0 0 0 0 0 0 0 1 正数
1 0 0 0 0 0 0 1 負数
・数値部分は、符号無二進数より1ビット減 (絶対値での範囲が縮小)
・正負を含めた範囲は同じ
・数値桁の解釈の相違で2通りの方式がある (絶対値表示 / 補数表示)
・どの方式も自然数の表記は、符号無二進数と同じ
・符号付二進数として、通常は補数表示を採用
第08節符号付二進数の方式
○ 符号無[U]、絶対値表示[A]、補数表示[S] の相互変換
○ ビット列の各方式での解釈
○ 十進数からの各方式への変換
● 絶対値表示
● 補数表示
・
・
・
・
・
・
・
・
・
・
数値桁は絶対値
変換は簡単
加減算には別の算法が必要
0に +0 と -0 の2つの表記が存在
範囲は8ビットで -127 ～ +127
数値桁は補数
変換には手順が必要
加算は符号無と全く同様
減算は反数の加算として実行
範囲は8ビットで -128 ～ +127
+107 ＝ 0110 1011 [A]
-107 ＝ 1110 1011 [A]
+107 ＝ 0100 1011 [S]
-107 ＝ 1011 0101 [S]
1100 1010 [U] ＝ +202
1100 1010 [A] ＝ -74
1100 1010 [U] ＝ +202
1100 1010 [S] ＝ -54
＝ -(202-128)
＝ 202-256
第09節符号付二進数の変換と桁
第10節 [1] 符号付二進数の加減算

Download Report