情報量と二進法での四則演算 香川大学工学部 富永浩之 情報数学１ 第 3-2 章

概 要 ■ 情報量と単位 ビットとバイト、キロ・メガ・ギガ・テラ ■ 情報量とデータ 基底表現と整除表現 ■ 多進数への変換 多進数への変換 ■ 整数の記数法 多進数からの変換 ホーナー法 ■ 符号付二進数の あ

第 01 節 [1] 情報量と情報量の単位 ● 情報量の単位 ・ その情報の存在により、何通りの異なる状態を区別できるかという尺度 ・ ある状態であるかないか (1 か 0 か ) を表すのに必要な情報を最小単位 ・ これを 1 ビット [bit] といい、ビットを表す単位記号として、小文字の頭文字 b を 用いる ● ビット列 ○ ビット列 0 と 1 の数字の列 , 1011 ・ 長さ n のビット列は、 n ビットの情報を表し、 2 n 通りの異なる状態が区別され る ○ 自由桁二進数 通常の表記の二進数で、 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 バイトの情報量があれば区別される。 ハードディスクやメモリの容量は、普通、バイト単位で表す。 8 b ＝ 1 B 256 ※ ASCII コード文字 ( 英数字 ) 8 ビットマイコン 色階調指定 16 b ＝ 2 B 65,536 ※ JIS コード文字 ( 日本語文字 ) 16 ビット DOS ハイカラー表示 24 b ＝ 3 B 16,777,216 ※ フルカラー表示 32 b ＝ 4 B 約 43 億 ※ 32 ビット OS(Windows) IP アドレス 64 b ＝ 8 B 約 1800 京 ※ 64 ビット次世代 OS 128 b ＝ 16 B 約 3.4×10^38 ※ 次世代 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 個 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z ○ 数字 10 個 ○ 記号 32 個 ! ? # $ % & | \,. ; ' " ` ^ ~ _ + - * / = ( ) [ ] { } ○ 空白 1 個 英語圏で必要な文字は、約 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 枚程度であ る。

● モノクロ画像データ ‥ 各画素 ( 画面上のドット ) の輝度情報 ○ VGA 640 × 480 ＝ 307,200 ○ SVGA 800 × 600 ＝ 480,000 ○ XGA 1024 × 768 ＝ ○ SXGA 1280 × 1024 ＝ 計算機のディスプレイ上の画像は、ドット ( 画素 ) から構成されている。 各画素に白 / 黒の 1 ビットの情報量を割り当てれば、モノクロ二値の画像が表現され る。 1 画素に 8 ビットを割り当てれば、黒から白への輝度を 256 段階の階調として 表現することができる。これをモノクロ階調という。 第 02 節 [3] 情報量と画像データ

● カラー画像データ ‥ 光の三原色 (RGB) の輝度情報の組合せ ○ フルカラー 24 ビット (RGB 8,8,8) 約 1677 万色 ○ ハイカラー 16 ビット (RGB 5,6,5) 色 ○ 8 ビット (RGB 3,3,2) 256 色 色彩を表すために用いるビット数を色深度という。 第 02 節 [4] 情報量と画像データ 人間の視覚は 緑 に対する感度が高く青 に対する感度が低い

● 第 節 スキャナ画像の情報量 [ 展開 ] スキャナでは、解像度の単位として、 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 の情報量が必要になる。 第 02 節 [5] 情報量と画像データ

第 03 節 [1] 情報量と音声データ ● 音声 ( 音波 ) ‥ 空気の振動 ( 各時刻の振幅 ) ○ A/D 変換 アナログ波形 ( 振幅量 ) ⇒ 離散近似 ⇒ デジタル信号 ○ D/A 変換 デジタル信号 ( ビット列 ) ⇒ 連続補間 ⇒ アナログ波形 ● 音声データの標本化と量子化 ○ 標本化 ( 時間的 ) 一定時間ごとに振幅量を記録 標本化周波数 ○ 量子化 ( 空間的 ) 振幅量を離散値で近似 量子化ビット数 ● 音声データの情報量 ○ CD の音質 標本化 44,100Hz 量子化 16bit ( 段階 ) ステレオ 2ch （左 右） ○ 1 秒間 44,100×16×2 ＝ 1,411,200 bit (÷8÷1024) ＝ KB ○ 記録容量 650MB 650×1024÷172.2 ＝ ‥ 秒 ≒ 約 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] 情報量と映像データ ● 第 節 マルチメディアデータの標準規格 [ 参考 ] ○ MPEG-2 DVD の動画データの記録形式 高品位を保ちながら高圧縮 圧縮と解凍に高性能の処理装置を要求 ( 現在は普通の PC でも OK) ハイビジョンのデジタルテレビ放送では、 MPEG-2 が用いられている。 なお、インターネット上での音声データの標準規格となっている MP3 は、 MPEG-2 Layer-3 の略である。すなわち、 MPEG-2 規格の音声部分のみを利用している。 やや古いメディアであるビデオ CD では、 MPEG-1 という規格を用いている。 これは、 MPEG-2 より画質が劣る。 また、インターネットテレビなど、通信容量が低くてもある程度の品質を保ち、 ユーザからの操作を受け付ける双方向的な映像通信では、 MPEG-4 が採用されている。 なお、 Windows や各種のソフトでは、独自のデータ形式を用いている場合がある。

二進法での加減算は、 各桁同士の計算結果を表す加法表および減法表に基づき、 筆算の形で行う。 加法表・減法表においては、 0 － 1 ＝ -1 のような 1 桁の数同士の単独の計算結果ではなく、 筆算の途中の各桁において、計算結果として現れる数字と、 繰上り、繰下りの有無を記入しておく。 第 04 節 [1] 二進法での加法と減法 被加数 ＋ 加数 ↑1111 繰上り 和 被減数 ＋ 減数 ↓1111 繰下り 和

第 05 節 [1] 二進法での乗法 被乗数 ×11101 乗数 乗数の桁が 0 なら 左シフトしながらコ ピー ＋ 積 二進法の乗法 ＝ 乗法表 ( 論理積 ) ＋ 左桁シフト × ∧ ∨

第 05 節 [1] 二進法での除法 101 整商 被除数 ≧ 1011 より商 1 を立てる 1000 差を求める <1011 より商 0 を立てる 除数より小となるまで 110 剰余

43×29 ＝ 43 × [2] ＝ 43 × (1 ＋ 4 ＋ 8 ＋ 16) ＝ 43 ＋ (43×2)×2 ＋ (43×4)×2 ＋ (43×8)×2 ＝ 43 ＋ 172 ＋ 344 ＋ 688 ＝ 1247 第 06 節 ロシア乗算法と二分累乗法 ＋ ＋ __100 ＋ ___1000 ＋ ____ × × 倍 半分 奇偶 二進数での乗算

第 07 節 整数の記数法 ● 符号付二進数 ‥ 符号桁 ＋ 数値桁 in 固定桁 ・ 整数の記数法には、符号と数値が必要 ・ 符号付二進数では、符号も含め、ビット列 (0/1 のみ ) として整数を表記 ・ 上位桁の 0 を省略しない、固定長のビット列で考える ・ 最上位での繰上りは、桁溢れ ( オーバーフロー ) となる ・ 固定桁の最上位桁を符号桁に使う (0 正 1 負 ) 正数 負数 ・ 数値部分は、符号無二進数より 1 ビット減 ( 絶対値での範囲が縮小 ) ・ 正負を含めた範囲は同じ ・ 数値桁の解釈の相違で 2 通りの方式がある ( 絶対値表示 / 補数表示 ) ・ どの方式も自然数の表記は、符号無二進数と同じ ・ 符号付二進数として、通常は補数表示を採用

第 08 節 符号付二進数の方式 ● 絶対値表示 ・ 数値桁は絶対値 ・ 変換は簡単 ・ 加減算には別の算法が必要 ・ 0 に +0 と -0 の 2 つの表記が存 在 ・ 範囲は 8 ビットで -127 ～ ＝ [A] -107 ＝ [A] [U] ＝ [A] ＝ -74 ＝ -( ) ● 補数表示 ・ 数値桁は補数 ・ 変換には手順が必要 ・ 加算は符号無と全く同様 ・ 減算は反数の加算として実行 ・ 範囲は 8 ビットで -128 ～ ＝ [S] -107 ＝ [S] [U] ＝ [S] ＝ -54 ＝ ○ 符号無 [U] 、絶対値表示 [A] 、補数表示 [S] の相互変換 ○ ビット列の各方式での解釈 ○ 十進数からの各方式への変換

第 09 節 符号付二進数の変換と桁

第 10 節 [1] 符号付二進数の加減算