貪欲アルゴリズム

Size: px

Start display at page:

Download "貪欲アルゴリズム"

れんかくまじ
4 years ago
Views:

1 コードコンピュータ基礎 (3) 菊池浩明

2 講義概要教科書 2 章データ表現 4. 浮動小数点数 6. コード» 進コード» 文字コード» ハミングコード

3 浮動小数点 (floating-point format) 定義小数点の位置を固定しない小数の表現. 符号 s+ 仮数 ƒ + 指数 e (sign) (mantissa) (exponent) 例 ).25 x 7 s = ( 負 ), ƒ =.25 =. (2) = /8 (M で表す時もある ) e = 7 = (2) ( 実際はもう少し複雑 )

4 IEEE 754 浮動小数点の表示規格 IEEE (Institute of Electrical and Electronics Engineering; 米国電気電子学会 ) 短精度 (float)» s = bit, e = 8bit, ƒ = 23 bit: 計 32 bit (4 byte) 倍精度 (double)» s = bit, e = bit, ƒ = 52 bit: 計 64 bit (8 byte)

5 IEEE 754 単精度 32 ビット s e ƒ 倍精度 64 ビット 2 63 s e ƒ

6 正規化仮数部の正規化.5625 () =. (2) =. x 2 ; ƒ =, e= =. x 2-3 ; ƒ =, e = -3 =. x 2-3 ; ƒ =, e = -3 (MSB は必ずに正規化されるので省略 ; ケチ表現 )

7 浮動小数点数の演算加算 3 () +.2 () = 3 x 2 + 2x - = 3 x x - ; 2 と - の最小値に揃える乗算 = 3.2 x 2 3 () x.2 () = 3 x 2 x 2x - = 3 x 2 x 2- ; 仮数部は乗算, 指数部は加算 = 6 x 指数部の計算を簡単化するためバイアス表示を導入

8 負数の表現 ( 指数部のみ ) 進数 2 進数絶対値 ( 符号なし ) 一般の整数 IEEE 754 符号 2 の補数符号バイアス表示 FF 最大 +28 FE 最小 F 27 + 最大最小 27

9 バイアス表示の理由理由指数部の計算の効率化理由 2 クリーンゼロ = x -23 の時,s=ƒ=e= となるアンダーフローしても安全オーバーフロー e=24, ƒ=

10 IEEE 754 による表現符号部 s, 仮数部 ƒ, 指数部 e による浮動小数点数 x x = (-) s 2 e-27 x (.ƒ) -27 = 7F (6) は指数のバイアス表示.ƒ のはケチ表現

11 例例 ) を IEEE754 単精度で表せ = -. (2) = -. x 2 3 s = (-) ƒ= (2) = 35 (6) e= 7F+3 = 82 (6) =

12 演習 ) s =, ƒ=, e = 8 で表される浮動小数点 x を進実数で示せ. x = (-)s x.ƒ x 2 8-7F =- x. x 2 = (2) = () 2) 進数を浮動小数点表記せよ () =. (2) =. x 2 3 s =, f =, e = 7f +3 = (6)

13 実際のメモリ上の値実行例 (Intel, Gcc) c f=5, s=, e = f=5, s=, e = d 4 f=6d, s=, e = 8

14 特殊な浮動小数点数特殊な数 s=, ƒ =, e = x= クリーン» s =, ƒ =, e = ( 未定義?)» s=, ƒ =, e = 禁止 s =, ƒ =, e= FF オーバーフロー s =, ƒ, e= FF 非数 (NaN;» / や, - など Not a Number) 通常の数値の範囲 : -26 e +27 FE

15 コード文字コード ASCII, Unicode

16 コード code ( 符号 ) 情報の表現方法符号化 encode, 復号化 decode 例 ) 値 2 () を2 進数 4bitでで符号化する

big endian v.s. little endian Big endian X = 234 (6) アドレス値 2 2 2 34 ネットワークでの通信.

17 big endian v.s. little endian Big endian X = 234 (6) アドレス値ネットワークでの通信.Motrora, Sun SPARC など Little Endian X = 234 (6) アドレス値 Intel x86 卵を大きい方から割る人々. ガリバー旅行記

18 進数のコード BCD コード (Binary Coded Decimal) 進数ケタを 2 進数 4bit で表現する. 例 )23 () = ゾーン進数進数ケタを,byte で表現. 符号は最後の byte の上位 4bit ( = 正, = 負 ) 例 ) -23 () = パック進数 BCD コードに, 符号を加える. 例 ) +23 () =

19 例 -24 をパック進数で表せ. BCD コード, ゾーン進数, パック進数で表現された値がある. どれがどれか

20 L 文字コード ASCII コード national Standard Code for Information Interchange ( 情報交換の為の米国標準コード ),7 bit の英数文字コード NUL P ` p! A Q a q 2 " 2 B R b r 3 # 3 C S c s 4 $ 4 D T d t 5 % 5 E U e u 6 & 6 F V f v 7 ' 7 G W g w 8 BS ( 8 H X h x 9 ) 9 I Y I y A LF * : J Z j z B ESC + ; K [ k { C, < L l D CR - = M ] m } E. > N ^ n ~ F /? O _ o

21 例文字列の表現 "ABC" = 4 (6) (3 byte) "23" = 3 (6) 大文字から小文字の変換 "A" = (6) = 6 = "a" "D" = (6) = 64 = "d" 8 を表す文字列 = (6) = 38 (6) 次の符号はどんな文字列か? D 53

改行コード改行に関する制御コード LF (Line Feed) CR (Carriage Return) OS の違い a d http://www.kurzweilai.

22 改行コード改行に関する制御コード LF (Line Feed) CR (Carriage Return) OS の違い a d ing-of-the-typewriter 改行 LF OS Linux, Mac OS X CR + LF CR Mac OS 9 Windows, Network 標準形

23 日本語文字コードコード符号語数特徴代表例 JIS (Japanese Industrial Standard) X 28 可変長 7 bit 文字コード, モードにより英数漢字を分ける電子メール Shift JIS (sjis) 2バイト固定長 8 bit 2byte コード PC (Windows, MacOS) EUC (Extended Unix Code) Unicode (UTF-6) 2 バイト固定長 8 bit 2 byte コード (2 バイト目に制約 ) 2 バイト固定長多国語 ( 日中韓の漢字を同一コードで統一 ) UTF-8 ~3バイト可変長 8 bitコードの組み合わせ Linux など Java の内部コード Web

24 文字コード表示例文字列 "OhOh 明治 n" BOM "O" "h" "O" "h" ESC$ B JIS 4f 68 3f 68 b " 明 " " 治 " CR LF 4c 4 3c 23 d a SJIS 4f 68 4f be 8e a d a EUC 4f 68 4f 68 cc c bc a3 d a UTF6 ff fe 4f 68 UTF-8 ef bb bf 4f 68 4f 68 e6 98 8e 4f 68 e 66 bb 6c d a e6 b2 bb d a

25 JIS 概要 JIS X 28 ( 第水準 2965 文字, 第 2 水準 339 文字 ) と ASCII を混在して使う符号化形式 (ISO-222- JP). 電子メールなどの標準エスケープシーケンス例 ) B ESC ( B ASCII B 28 4A ESC ( J JIS X 2 ラテン文字 B 24 4 ESC JIX X 版 B ESC $ B JIS X 版 A 7 計算 ; a 4 37 B B 3B B 28 4A 3B a 問題点 statefull ( 現在の状態によって符号化が変わる )

26 Shift_JIS 概要 JIS X 2 の隙間に JIS X 28 を押し込んだ符号化形式.PC でのスタンダード. 特徴 2 バイトの固定長コード. 第一バイト目に 8~9F, E~EF が来たら漢字 (2 バイトコード ) 問題点第 2 バイト目に 7F 以降 (ASCII) が使われていて, 処理系では誤動作する可能性.

27 EUC (Extended Unix Code) 概要 Unix 系の OS の業界団体が定めたコード.2 バイトの固定長符号. 特徴 A~FE で始まるデータは 2 バイトコード (7F 以下は必ず ASCII). 問題点第バイトと 2 バイトが同じ範囲の値を取るので, 区切りの判別が困難.

28 Unicode (UTF-6) 概要ベンダーのコンソーシアムで策定された 6 ビットの国際文字コード仕様. 漢字の統合などが行われたが, 現在は ISO と統合して UTF-6, UTF-8 などに拡張された. 特徴符号語の単位で UTF-8, UTF-6, UTF-32 など複数の符号化がある.

29 UTF-8 ASCII と互換性がある,8 ビット単位の Unicode 符号化方式.ISO/IEC 646 や RFC 3629 でも定義されている. 符号値域長 UTF-8 の符号化バイト列 - 7F 8-7FF 8- FFFF - FFFF xxxxxxx (ASCII) 2 xxxxx xxxxxx 3 xxxx xxxxxx xxxxxx 4 xxx xxxxxx xxxxxx xxxxxx byte (ASCII) 多バイ 9 ト符号語の2 A バイト B 目以降 C D E F 2 byte 3 byte 4 byte

30 例 ef bb bf e3 8 af e5 b9 b4 3a b b 3a b b BOM H a r r y は 9 8 年 5 6f e5 ae b6 e3 8 ae e9 95 b7 e7 94 9f

31 BOM BOM (Byte Order Mark) UTF-6 などで多バイトコードのエンディアンを示すために先頭につけられたコード.» FE FF = Big Endian» FF FE = Little Endian UTF-8 では,Uncode を示すために使われる.» FE BB BF

32 Unicode の問題点表記の問題明治大学先端メディアサイエンス 24 明治大学先端メディアサイエンス 24 漢字の統合円記号の問題

33 機種依存文字概要 ( 環境依存文字 ) JIX X 28 の空き領域にベンダーが独自に定義した文字外字 Windows 2,ⅢⅣ, km, kg, Macintosh ( 月 )( 火 ) メールなどで送ると文字化けを引き起こすので極力避ける. 授業名プログラミング演習 Ⅱ

34 漢字の違い簡体字 ( 中国本土 ) simplified 繁体字 ( 香港, 台湾 ) traditional 日本語簡体字繁体字豊丰豐万万萬東东東习业广廣

35 文字コードの変換エディターによる自動変換文字コード指定保存 (Tera Pad) 変換ツール nkf (Network Kanji Filter)» nkf j < input > output» -j (jis), -s (shift jis), -e (EUC), -w (Utf-8), -w6 (Utf- 6)

36 誤り訂正コードパリティコードハミングコード

37 誤り訂正検出技術誤り訂正符号パリティ検査符号» 通信, 記憶装置ハミング符号» 基本理論的整理 BCH 符号» Reed-Solomon 符号 (CD) 誤り検出符号巡回符号» 実用的 ( 容易な復号回路 )» CRC チェック ( パケットの通信誤り )

38 水平垂直パリティ検査符号検査方程式 c =x +x 2 c 2 =x 3 +x 4 c 3 =x +x 3 c 4 =x 2 +x 4 x x 2 c x 3 x 4 c 2 c 5 =c +c 2 +c 3 +c 4 (9,4) 符号符号語 w=(x, x 2, x 3, x 4, c, c 2, c 3, c 4, c 5 ) c 3 c 4 c 5

39 誤り訂正の原理正しい受信語誤りのある受信語 y=(,,,,,,,,) y=(,,,,,,,,) w=(,,,,,,,,)

Richard Wesley Hamming ハミング符号誤り訂正, 検出符号 95-998

40 Richard Wesley Hamming ハミング符号誤り訂正, 検出符号 Bell Lab. Turing Prize in 968 IEEE, Hamming Medal

41 (7,4) ハミング符号水平垂直パリティ検査符号 c =x +x 2 (mod 2) c 2 =x 3 +x 4 c 3 =x +x 3 c 4 =x 2 +x 4 c 5 =c +c 2 +c 3 +c 4 (9,4) 符号 w=(x, x 2, x 3, x 4, c, c 2, c 3, c 4, c 5 ) ハミング符号 c =x +x 2 +x 3 c 2 = x 2 +x 3 +x 4 c 3 =x +x 2 +x 4 (7,4) 符号 w=(x, x 2, x 3, x 4, c, c 2, c 3 ) 符号化率 η=4/7

42 情報ビットの符号化符号語情報ビット x,x 2,x 3,x 4 = (,,,) 検査ビット c =x +x 2 +x 3 =++= c 2 =++= c 3 =++= 符号語 w=(,,,,,,) 検査方程式 c =x +x 2 +x 3 c 2 = x 2 +x 3 +x 4 c 3 =x +x 2 +x 4 x +x 2 +x 3 +c = x 2 +x 3 +x 4 +c 2 = x +x 2 +x 4 +c 3 =

43 符号語 C x x 2 x 3 x 4 c 検査方程式 c =x +x 2 +x 3 c 2 = x 2 +x 3 +x 4 c 3 =x +x 2 +x 4 x +x 2 +x 3 +c = x 2 +x 3 +x 4 +c 2 = x +x 2 +x 4 +c 3 =

44 符号語 C x x 2 x 3 x 4 c c 2 検査方程式 c =x +x 2 +x 3 c 2 = x 2 +x 3 +x 4 c 3 =x +x 2 +x 4 x +x 2 +x 3 +c = x 2 +x 3 +x 4 +c 2 = x +x 2 +x 4 +c 3 =

45 符号語 C x x 2 x 3 x 4 c c 2 c 3 =w =w =w 2 =w 3 =w 4 =w 5 =w 6 =w 7 =w 8 =w 9 =w =w =w 2 =w 3 =w 4 =w 5 検査方程式 c =x +x 2 +x 3 c 2 = x 2 +x 3 +x 4 c 3 =x +x 2 +x 4 x +x 2 +x 3 +c = x 2 +x 3 +x 4 +c 2 = x +x 2 +x 4 +c 3 =

46 誤りが発生したら? 単一誤り符号語 w 3 =(,,,,,,) 誤りベクトル e =(,,,,,,) 受信語 y =(,,,,,,) 検査方程式 x +x 2 +x 3 +c =++ + = =s x 2 +x 3 +x 4 +c 2 = = =s 2 x +x 2 +x 4 +c 3 =+ + + = =s 3 シンドローム

47 単一誤りのシンドローム誤りベクトル x x 2 x 3 x 4 c c 2 c 3 シンドローム s s 2 s 3 シンドローム s = x +x 2 +x 3 +c s 2 = x 2 +x 3 +x 4 +c 2 s 3 = x +x 2 +x 4 +c 3

48 誤り訂正誤りベクトル x x 2 x 3 x 4 c c 2 c 3 シンドローム s s 2 s 3 シンドローム例全て異なる誤りパターンと一対一に対応 y=(,,,,,,) s=(,,) e=(,,,,,,) w=(,,,,,,)

49 演習 (6,3) ハミング検査符号» x +x 2 +c =» x +x 2 +x 3 +c 2 =» x +x 3 +c 3 = 次の受信語のシンドロームを求め, 誤りを正せ» y =(,,,,,)» y 2 =(,,,,,)» y 3 =(,,,,,)» y 4 =(,,,,,)

50 ( ヒント ) 符号語 C x x 2 x 3 c c 2 c 3 検査方程式 x +x 2 +c = x +x 2 +x 3 +c 2 = x +x 3 +c 3 =

51 ( ヒント ) 単一誤りの全シンドローム x x 2 x 3 c c 2 c 3 s s 2 s 3 x +x 2 +c = =s x +x 2 +x 3 +c 2 = =s 2 x +x 3 +c 3 = =s 3 誤り訂正 s=(,,) 検査方程式 e 2 =(,,,,,) y 2 =(,,,,,) w =(,,,,,) =y 2 +e 2

52 シンドロームの性質誤りが同じ時, シンドロームも同じ w 2 =(,,,,,) y 2 =(,,,,,) e 2 =(,,,,,) s 2 =(,,) w 3 =(,,,,,) y 3 =(,,,,,)

53 宿題 2 章問 4 ( 文字コード ) 問 6 問 7 問 8 問 9 問

54 まとめ浮動小数点数は, 符号 sと ( )fと指数( ) の 3つの要素で表現される.IEEE754では指数部は2の補数ではなく ( ) で表現される. 日本語文字コードには,7ビットの( ),PC のディファクト標準である ( ), 多国語に対応した可変長の ( ) がある. ( ) 符号は代表的な誤り訂正符号である. 検査方程式で符号語を検査した結果 ( ) により誤り位置を検出する.

４　Ｍｕｌｅ（Ｅｍａｃｓ）

４　Ｍｕｌｅ（Ｅｍａｃｓ）文字コードとは文字コードとコード系 character code コンピュータ内部での表現の際あるいはコンピュータ間の通信の際には文字や記号はある一定のビットパターン (bit pattern, 0,1の列 ) で表されているこのような文字とビットパターンの対応を文字コードという広く使われている文字コードと文字コード系 ( 文字コードをどのように使うかも含めて規定したコード体系のこと )