( )
Page 2
Page 3
0 = 1 = Page 4
1 0 13 = 8 + 4 + 1 = 2 3 1 + 2 2 1 + 2 1 0 + 2 0 1 = 1101 ( ) b n 1 b n 2 b 0 (b n 1,,b 0 {0,1}) = 2 n 1 b n 1 + 2 n 2 b n 2 + + 2 0 b 0 n n bit( ) Page 5
n n n {}}{{}}{ 00 0 = 0 11 1 = 2 n 1 1 0 2 k 1/2 k 2 k b n 1 b 0 b n 1 b 0 1/2 k b n 1 b k b k 1 b 0 k {}}{ 0 0 k {}}{ 0 0b n 1 b k Page 6
Page 7
8bit Page 8
0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 10 Page 9
1 0 1 1 1 1 0 1 + 0 0 0 1 0 1 1 0 1 1 0 1 0 0 1 1 Page 10
1 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 1 1 1 1 1 Page 11
34 34 = 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 +1 = 34 = 34 Page 12
225 34 =? 225 34 = 225 + ( 34) 1 1 1 0 0 0 0 1 + 1 1 0 1 1 1 1 0 34 1 1 0 1 1 1 1 1 1 = 191 Page 13
b 7 b 6 b 5 b 4 b 3 b 2 b 1 b 0 b 7 b 6 b 5 b 4 b 3 b 2 b 1 b 0 + 1 (b bit b ) b 7 b 6 b 5 b 4 b 3 b 2 b 1 b 0 + (b 7 b 6 b 5 b 4 b 3 b 2 b 1 b 0 + 1) = (b 7 b 6 b 5 b 4 b 3 b 2 b 1 b 0 + b 7 b 6 b 5 b 4 b 3 b 2 b 1 b 0 ) + 1 = 11111111 + 1 = 100000000 bit 1 ( )+( )=0 Page 14
( : n bit 0 2 n 1 ) a b modulo m a bmodm : k Z a b = km (a m b m ) a mod m a + mz = {b a bmodm} (= {a + mk k Z}) : a bmodm c d modm a + c b + d mod m, a c b d mod m Page 15
= : m = 2 8 (= 256) ( 1) + 2 8 Z = {, 513, 257, 1,255,511, }, 0 + 2 8 Z = {, 512, 256,0,256,512, }, 1 + 2 8 Z = {, 511, 255,1,257,513, }, 2 + 2 8 Z = {, 510, 254,2,258,514, }, 2 1 2 + ( 1) 2 + 255 257 1 (mod 2 8 ) Page 16
= bit 1 = 2 8 (= 256) bit n n + 2 8 Z 00000000 0 {, 256,0,256, } +0 00000001 1 {, 255,1,257, } +1.... 01111111 127 {, 129,127,383, } +127 10000000 128 {, 128,128,384, } 128 10000001 129 {, 127,129,385, } 127.... 11111111 255 {, 1,255,511, } 1 bit Page 17
nbit n 1 n 1 {}}{{}}{ 10 0 = 2 n 1 01 1 = 2 n 1 1 bit 1 0 1 0 Page 18
(unsigned) (signed) 0 2 n 1 2 n 1 2 n 1 1 bit bit 11011110 222 34 Page 19
Page 20
1bit 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 10 0 + 0 = 1 0 + 1 = 10 1 + 0 = 10 1 + 1 = 11 1bit : 1bit (carry in) : 1bit (carry out) Page 21
1bit a b cin cout sum 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 Page 22
1bit bit (cout) (sum) 1bit Page 23
(cout=1 ) (a,b,cin) 1 (cout=0) cout = (a b cin) (a b) (a cin) (b cin) = (a b) (a cin) (b cin) Page 24
cout = (a b) (a cin) (b cin) Page 25
1(sum=1) (a,b,cin) 1 0(sum=0) sum = (a b cin) (a b cin) ( a b cin) ( a b cin) Exercise. Page 26
1bit Page 27
n bit n = 4 : a n a 1, b n b 1 (n bit ) : d n d 1 ( ) cout ( 1bit) Page 28
n bit n = 4 : a n a 1, b n b 1 (n bit ) : d n d 1 ( b n b 1 a n a 1 ) Page 29
1101 + 0100(= 13 + 4) = 0001(= 1) 0110 + 0101(= 6 + 5) = 1011(= 5) 0011 1011(= 3 ( 5)) = 1000(= 8) 1011 0110(= ( 5) 6) = 0101(= 5) ( 5) 6 5 mod 2 4, etc. Page 30
4bit a 4 a 3 a 2 a 1 7 7bit 2 d 7 d 6 d 5 d 4 d 3 d 2 d 1 1101(= 13) 1011011(= 91) 7 4 2 1 2 n bit (bit ) ( ) 2 Page 31
7 = 8 1 8 (1) 8 a 4 a 3 a 2 a 1 a 4 a 3 a 2 a 1 000 (3bit ) (2) a 4 a 3 a 2 a 1 000 7 (2 ) 8 a 4 a 3 a 2 a 1 000 0a 4 a 3 a 2 a 1 000 a 4 a 3 a 2 a 1 0000a 4 a 3 a 2 a 1 0a 4 a 3 a 2 a 1 000 0000a 4 a 3 a 2 a 1 2 (3) 8bit 7bit 0 105(= 15 7 127) 8 2 ( 0 ) Page 32
Page 33
http://www.math.kyoto-u.ac.jp/ susumu/lecture/digital11.pdf Page 34