コード コンピュータ基礎 (3) 菊池浩明
講義概要 教科書 2 章データ表現 4. 浮動小数点数 6. コード» 進コード» 文字コード» ハミングコード
浮動小数点 (floating-point format) 定義 小数点の位置を固定しない小数の表現. 符号 s+ 仮数 ƒ + 指数 e (sign) (mantissa) (exponent) 例 ).25 x 7 s = ( 負 ), ƒ =.25 =. (2) = /8 (M で表す時もある ) e = 7 = (2) ( 実際はもう少し複雑 )
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)
IEEE 754 単精度 32 ビット 8 9 3 s e ƒ 倍精度 64 ビット 2 63 s e ƒ
正規化 仮数部の正規化.5625 () =. (2) =. x 2 ; ƒ =, e= =. x 2-3 ; ƒ =, e = -3 =. x 2-3 ; ƒ =, e = -3 (MSB は必ず に正規化されるので省略 ; ケチ表現 )
浮動小数点数の演算 加算 3 () +.2 () = 3 x 2 + 2x - = 3 x - + 2 x - ; 2 と - の最小値に揃える 乗算 = 3.2 x 2 3 () x.2 () = 3 x 2 x 2x - = 3 x 2 x 2- ; 仮数部は乗算, 指数部は加算 = 6 x 指数部の計算を簡単化するためバイアス表示を導入
負数の表現 ( 指数部のみ ) 進数 2 進数 絶対値 ( 符号な し ) 一般の整数 IEEE 754 符号 2 の補数符号 バイアス表示 FF 255 + 最大 +28 FE 254 2 +27 8 28 最小 28 + 7F 27 + 最大 +27 26 最小 27
バイアス表示の理由 理由 指数部の計算の効率化 理由 2 クリーンゼロ = x -23 の時,s=ƒ=e= となる アンダーフローしても安全 オーバーフロー e=24, ƒ=
IEEE 754 による表現 符号部 s, 仮数部 ƒ, 指数部 e による浮動小数点数 x x = (-) s 2 e-27 x (.ƒ) -27 = 7F (6) は指数のバイアス表示.ƒ の はケチ表現
例 例 ) -4.625 を IEEE754 単精度で表せ. -4.625 = -. (2) = -. x 2 3 s = (-) ƒ= (2) = 35 (6) e= 7F+3 = 82 (6) =
演習 ) s =, ƒ=, e = 8 で表される浮動小数点 x を 進実数で示せ. x = (-)s x.ƒ x 2 8-7F =- x. x 2 = (2) = () 2) 進数 4.825 を浮動小数点表記せよ. 4.825 () =. (2) =. x 2 3 s =, f =, e = 7f +3 = (6)
実際のメモリ上の値 実行例 (Intel, Gcc) -3.25 5 c f=5, s=, e = 8 3.25 5 4 f=5, s=, e = 8 4.825 6d 4 f=6d, s=, e = 8
特殊な浮動小数点数 特殊な数 s=, ƒ =, e = x= クリーン» s =, ƒ =, e = ( 未定義?)» s=, ƒ =, e = 禁止 s =, ƒ =, e= FF オーバーフロー s =, ƒ, e= FF 非数 (NaN;» / や, - など Not a Number) 通常の数値の範囲 : -26 e +27 FE
コード 文字コード ASCII, Unicode
コード code ( 符号 ) 情報の表現方法 符号化 encode, 復号化 decode 例 ) 値 2 () を2 進数 4bitでで符号化する
big endian v.s. little endian Big endian X = 234 (6) アドレス 値 2 2 2 34 ネットワークでの通信.Motrora, Sun SPARC など Little Endian X = 234 (6) アドレス 値 2 34 2 2 Intel x86 卵を大きい方から割る人々. ガリバー旅行記 http://hareenlaks.blogspot.jp/2/2/big-endian-
進数のコード BCD コード (Binary Coded Decimal) 進数 ケタを 2 進数 4bit で表現する. 例 )23 () = ゾーン 進数 進数 ケタを,byte で表現. 符号は最後の byte の上位 4bit ( = 正, = 負 ) 例 ) -23 () = パック 進数 BCD コードに, 符号を加える. 例 ) +23 () =
例 -24 をパック 進数で表せ. BCD コード, ゾーン 進数, パック 進数で表現された値がある. どれがどれか.. 2. 3.
L 2 3 4 5 6 7 文字コード ASCII コード national Standard Code for Information Interchange ( 情報交換の為の米国標準コード ),7 bit の英数文字コード NUL SP @ 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
例 文字列の表現 "ABC" = 4 (6) (3 byte) "23" = 3 (6) 大文字から小文字の変換 "A" = 4 + 2 (6) = 6 = "a" "D" = 44 + 2 (6) = 64 = "d" 8 を表す文字列 = 8 + 3 (6) = 38 (6) 次の符号はどんな文字列か? 3 73 74 46 4D 53
改行コード 改行に関する制御コード LF (Line Feed) CR (Carriage Return) OS の違い a d http://www.kurzweilai.net/pass ing-of-the-typewriter 改行 LF OS Linux, Mac OS X CR + LF CR Mac OS 9 Windows, Network 標準形
日本語文字コード コード符号語数特徴代表例 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
文字コード表示例 文字列 "OhOh 明治 n" BOM "O" "h" "O" "h" ESC$ B JIS 4f 68 3f 68 b 24 42 " 明 " " 治 " CR LF 4c 4 3c 23 d a SJIS 4f 68 4f 68 96 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
JIS 概要 JIS X 28 ( 第 水準 2965 文字, 第 2 水準 339 文字 ) と ASCII を混在して使う符号化形式 (ISO-222- JP). 電子メールなどの標準 エスケープシーケンス 例 ) B 28 42 ESC ( B ASCII B 28 4A ESC ( J JIS X 2 ラテン文字 B 24 4 ESC $ @ JIX X 28 978 版 B 24 42 ESC $ B JIS X 28 983 版 A 7 計算 ; a 4 37 B 24 42 37 57 3B 3B B 28 4A 3B a 問題点 statefull ( 現在の状態によって符号化が変わる )
Shift_JIS 概要 JIS X 2 の隙間に JIS X 28 を押し込んだ符号化形式.PC での スタンダード. 特徴 2 バイトの固定長コード. 第一バイト目に 8~9F, E~EF が来たら漢字 (2 バイトコード ) 問題点 第 2 バイト目に 7F 以降 (ASCII) が使われていて, 処理系では誤動作する可能性.
EUC (Extended Unix Code) 概要 Unix 系の OS の業界団体が定めたコード.2 バイトの固定長符号. 特徴 A~FE で始まるデータは 2 バイトコード (7F 以下は必ず ASCII). 問題点 第 バイトと 2 バイトが同じ範囲の値を取るので, 区切りの判別が困難.
Unicode (UTF-6) 概要 ベンダーのコンソーシアムで策定された 6 ビットの国際文字コード仕様. 漢字の統合などが行われたが, 現在は ISO と統合して UTF-6, UTF-8 などに拡張された. 特徴 符号語の単位で UTF-8, UTF-6, UTF-32 など複数の符号化がある.
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) 2 3 4 5 6 7 8 多バイ 9 ト符号語の2 A バイト B 目以降 C D E F 2 byte 3 byte 4 byte
例 ef bb bf 48 6 72 72 79 e3 8 af 3 39 38 3 e5 b9 b4 3a b b 3a b b BOM H a r r y は 9 8 年 5 6f 74 74 65 72 e5 ae b6 e3 8 ae e9 95 b7 e7 94 9f
BOM BOM (Byte Order Mark) UTF-6 などで多バイトコードのエンディアンを示すために先頭につけられたコード.» FE FF = Big Endian» FF FE = Little Endian UTF-8 では,Uncode を示すために使われる.» FE BB BF
Unicode の問題点 表記の問題 明治大学先端メディアサイエンス 24 明治大学先端メディアサイエンス 24 漢字の統合 円記号の問題
機種依存文字 概要 ( 環境依存文字 ) JIX X 28 の空き領域にベンダーが独自に定義した文字 外字 Windows 2,ⅢⅣ, km, kg, Macintosh ( 月 )( 火 ) メールなどで送ると文字化けを引き起こすので極力避ける. 授業名 プログラミング演習 Ⅱ
漢字の違い 簡体字 ( 中国本土 ) simplified 繁体字 ( 香港, 台湾 ) traditional 日本語簡体字繁体字 豊 丰 豐 万 万 萬 東 东 東 习业广 廣
文字コードの変換 エディターによる自動変換 文字コード指定保存 (Tera Pad) 変換ツール nkf (Network Kanji Filter)» nkf j < input > output» -j (jis), -s (shift jis), -e (EUC), -w (Utf-8), -w6 (Utf- 6)
誤り訂正コード パリティコード ハミングコード
誤り訂正 検出技術 誤り訂正符号 パリティ検査符号» 通信, 記憶装置 ハミング符号» 基本 理論的整理 BCH 符号» Reed-Solomon 符号 (CD) 誤り検出符号 巡回符号» 実用的 ( 容易な復号回路 )» CRC チェック ( パケットの通信誤り )
水平垂直パリティ検査符号 検査方程式 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
誤り訂正の原理 正しい受信語 誤りのある受信語 y=(,,,,,,,,) y=(,,,,,,,,) w=(,,,,,,,,)
Richard Wesley Hamming ハミング符号 誤り訂正, 検出符号 95-998 Bell Lab. Turing Prize in 968 IEEE, Hamming Medal
(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
情報ビットの符号化 符号語 情報ビット 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 =
符号語 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 =
符号語 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 =
符号語 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 =
誤りが発生したら? 単一誤り 符号語 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 シンドローム
単一誤りのシンドローム 誤りベクトル 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
誤り訂正 誤りベクトル x x 2 x 3 x 4 c c 2 c 3 シンドローム s s 2 s 3 シンドローム 例 全て異なる 誤りパターンと一対一に対応 y=(,,,,,,) s=(,,) e=(,,,,,,) w=(,,,,,,)
演習 (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 =(,,,,,)
( ヒント ) 符号語 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 =
( ヒント ) 単一誤りの全シンドローム 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
シンドロームの性質 誤りが同じ時, シンドロームも同じ w 2 =(,,,,,) y 2 =(,,,,,) e 2 =(,,,,,) s 2 =(,,) w 3 =(,,,,,) y 3 =(,,,,,)
宿題 2 章 問 4 ( 文字コード ) 問 6 問 7 問 8 問 9 問
まとめ 浮動小数点数は, 符号 sと ( )fと指数( ) の 3つの要素で表現される.IEEE754では指数部は2の補数ではなく ( ) で表現される. 日本語文字コードには,7ビットの( ),PC のディファクト標準である ( ), 多国語に対応した可変長の ( ) がある. ( ) 符号は代表的な誤り訂正符号である. 検査方程式で符号語を検査した結果 ( ) により誤り位置を検出する.