香川大学創造工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp 情報数学１ 第3-2章 情報量と二進法での四則演算 香川大学創造工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp

概 要 ■ 情報量と単位 ■ 情報量とデータ ■ 二進法での四則演算 ■ 符号付二進数 ■ 符号付二進数の加減算 概 要 ■ 情報量と単位 ビットとバイト キロ・メガ・ギガ・テラ ■ 情報量とデータ 文字データ 画像データ 動画データ ■ 二進法での四則演算 多進数への変換 ■ 符号付二進数 絶対値表示と補数表示 符号桁と数値桁 相互の変換 ■ 符号付二進数の加減算 符号付二進数の加減算 論理シフトと算術シフト

第01節 [1] 情報量と情報量の単位 ● 情報量の単位 ● ビット列 ○ ビット列 0と1の数字の列 010010, 1011 ・ その情報の存在により、何通りの異なる状態を区別できるかという尺度 ・ ある状態であるかないか(1か0か)を表すのに必要な情報を最小単位 ・ これを1ビット[bit]といい、ビットを表す単位記号として、小文字の頭文字 b を用いる ● ビット列 ○ ビット列 0と1の数字の列 010010, 1011 ・ 長さ nのビット列は、 n ビットの情報を表し、 2n 通りの異なる状態が区別される ○ 自由桁二進数 通常の表記の二進数で、0を例外として、他は1から始まるビット列 ○ 固定桁二進数 二進数の先頭に0を追加した表記も許すことにし、桁を揃える n桁の固定桁二進数をnビット二進数ともいう 1011[2]＝11[10] は4ビットの情報であり、16 通りの中で11番目の状態を表している。 2ビット二進数の 00[2]＝0[10] は、 4通りの中で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 最近は、1000と1024を厳密に区別するため、KiB や MiB が使われる。

第02節 [1] 情報量と文字データ 英語圏で必要な文字は、約100個程度 ○ 英字 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個 0 1 2 3 4 5 6 7 8 9 ○ 記号 32個 ! ? # $ % & | \ , . ; : @ ' " ` ^ ~ _ + - * / = < > ( ) [ ] { } ○ 空白 1個 英語圏で必要な文字は、約100個程度 これらの文字を区別するには、2^7＝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 4:3 640 × 480 ＝ 307,200 ○ SVGA 4:3 800 × 600 ＝ 480,000 ○ XGA 4:3 1024 × 768 ＝ 786,432 ○ SXGA 5:4 1280 × 1024 ＝ 1,313,720 ○ UXGA 4:3 1600 × 1200 ＝ 1,920,000 ○ WUXGA 8:5 1920 × 1200 ＝ 2,304,000 計算機のディスプレイ上の画像は、ドット(画素)から構成されている。 各画素に白/黒の1ビットの情報量を割り当てれば、 モノクロ二値の画像が表現される。 1画素に8ビットを割り当てれば、黒から白への輝度を256段階の階調として 表現することができる。これをモノクロ階調という。

第02節 [4] 情報量と画像データ ● カラー画像データ ‥ 光の三原色(RGB)の輝度情報の組合せ 色彩を表すために用いるビット数を色深度という。 人間の視覚は 緑に対する感度が高く青に対する感度が低い

第02節 [5] 情報量と画像データ ● 第02-06節 スキャナ画像の情報量 [展開] ● 第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節 マルチメディアデータの標準規格 ● 第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 被減数 ＋ 減数 ↓ 繰下り 和

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

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

第06節 [1] ロシア乗算法と二分累乗法 43×29 ＝ 43 × 1 1 1 0 1 [2] ＝ 43 × (1＋4＋8＋16) 43 × 29 101011 × 11101 ＋ 43 29 1 101011 86 14 172 7 101011__ 100 344 3 101011___ 1000 688 101011____ 10000 1247 10011011111 11101 2倍 半分 奇偶 二進数での乗算 43×29 ＝ 43 × 1 1 1 0 1 [2] ＝ 43 × (1＋4＋8＋16) ＝ 43 ＋ (43×2)×2 ＋ (43×4)×2 ＋ (43×8)×2 ＝ 43 ＋ 172 ＋ 344 ＋ 688 ＝ 1247

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

第07節 [2] 量子計算機とキュービット ● 量子計算機とキュービット ● 量子計算機の技術的課題 量子計算機は、量子力学における状態の重ね合せの原理を利用して、 複数の情報を同時に表し、並列的に処理を行うものである。 通常の計算機では、4ビットの情報量で、2^4＝16 通りの異なる状態を表せるが、 この全ての状態を調べるには、16回の計算が必要になる。 量子計算機では、情報を格納する各素子が同時に0と1の状態を保持することができ、 一度に16通りの場合を調べることができる。 このような情報素子をキュービット[qubit]という。 キュービットが1つ増えれば、2倍の性能を持つことになる。 ● 量子計算機の技術的課題 量子計算機の技術的課題は、キュービットの重ね合せ状態を安定的に保持すること、 キュービットの重ね合せ状態から解となる1つの状態を正確に取り出すことである。 また、量子計算機に最適な並列処理の算法を見つけることも必要となる。 現在は、数キュービットの実験が行われており、簡単な素因数分解などが計算できる。 将来、100キュービット程度になれば、2^100≒10^30 通りの並列計算が可能になり、 現在のスーパーコンピュータを遥かに凌ぐ驚異的な性能となる。 計算量的に現実的な処理が不可能とされていた多くの問題が解けるようになる。

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

第08節 [2] 符号付二進数の例題 -97を8ビット固定桁の符号付二進数で表す。 [A] および [S] で記せ。 絶対値表示では、符号を取って、7ビットの符号無二進数 97＝110 0001[U] に変換し、 符号桁を付けて 1110 0001[A] とする。 補数表示では、符号を取って、8ビットの符号無二進数 97＝0110 0001[U] に変換する。 反転した 1001 1110 に 1 を加算して、 1001 1111[S] とする。 あるいは、 -97＋128＝31 より、31＝001 1111[U] から、 符号桁を付けて 1001 1111[S] とする。  ビット列 1011 0110 を8ビット固定桁の符号付二進数として、 [A] および [S] で解釈したときの値を求めよ。 絶対値表示で解釈するには、数値桁 011 0110 を10進数 54 に直し、 符号を付けて -54 とする。 補数表示で解釈するときは、数値桁 011 0110 を10進数 54 に直し、 27＝128 を引いて、-74 とする。 あるいは、1011 0110 から 1 を減算した 1011 0101 を反転した 0100 1010 を 10進数 74 に直し、符号を付けて -74 とする。

第09節 [1] 符号付二進数の変換と符号反転 ● 自然数の符号付二進数への変換 [0] 2^(M-1)-1 以下の自然数しか表せない。2^(M-1) 以上だと桁溢れである。 [1] 変換可能な場合、そのまま二進数に変換する。 [2] 数値桁の桁数に満たない場合は 上位桁を0で埋め、符号桁も0にする。 ● 負整数の符号付二進数への変換 [0] -2^(M-1) 以上の負整数しか表せない。-2^(M-1)-1 以下だと桁溢れである。 [1] 2^M を加え、そのまま二進数に変換する。 [2] 数値桁の桁数に満たない場合は 上位桁を0で埋め、符号桁は1にする。   ● 符号反転 負数を符号付二進数に変換する場合や、減算を加算に変換するときに使う。 なお、0の符号反転および-128の符号反転は元のままである。 [1] 符号付整数の各桁を反転する(0は1に、1は0に)。 [2] 通常の二進法の計算として1を加える。桁溢れは無視する。

第09節 [2] 論理シフトと算術シフト 右論理シフトの最上位桁は0 左シフトの最下位桁は0 右算術シフトの最上位桁は同符号 正数の右論理シフト 負数の右論理シフト 正数の左論理シフト 負数の左論理シフト 符 数 1 符 数 1 符 数 1 符 数 1 右算術シフトの最上位桁は同符号 左算術シフトの最上位桁は同符号 正数の右算術シフト 負数の右算術シフト 正数の左算術シフト 負数の左算術シフト 符 数 1 ∥ 符 数 1 ∥ 符 数 1 ∥ 符 数 1 ∥

第10節 [1] 符号付二進数の加減算 固定桁の符号付二進数の加減算は、以下の手順で行なう。 [1] 減算は減数(引く方の数)を補数表示における符号反転を行い、加算に直す。 [2] 符号桁も含め、普通の二進法での加算を行う。桁溢れは無視する。 [3] 符号桁の変化を調べ、正しい値がどうか吟味する。 ○ 異符号 オーバーフローなし 正しい計算結果 ○ 同符号 計算結果が同符号(オーバーフローによらず) 正しい計算結果 ○ 同符号 計算結果が異符号(オーバーフローによらず) 正しくない計算結果(符号不正) 数値桁 繰上り 符号桁 正数A + 正数B ＜ +2^(M-1) 無 真の値 正数A + 正数B ≧ +2^(M-1) 有 偽の値(符号不正) 正数A + 負数B ＜ 0 正数A + 負数B ≧ 0 有(無視) 負数A + 負数B ＜ -2^(M-1) 負数A + 負数B ≧ -2^(M-1)