›
›

Cấu trúc máy tính - Chương 2: Biểu diễn dữ liệu và số học máy tính

pdf 106 trang vanle 4720
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cấu trúc máy tính - Chương 2: Biểu diễn dữ liệu và số học máy tính", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfcau_truc_may_tinh_chuong_2_bieu_dien_du_lieu_va_so_hoc_may_t.pdf

Nội dung text: Cấu trúc máy tính - Chương 2: Biểu diễn dữ liệu và số học máy tính

  1. Cấu trúc máy tính Chương 2 BIỂU DIỄN DỮ LIỆU & SỐ HỌC MÁY TÍNH 1
  2. Nội dung chương 2 2.1. C|c hệ đếm cơ bản 2.2. M~ hóa v{ lưu trữ dữ liệu trong m|y tính 2.3. Biểu diễn số nguyên 2.4. C|c phép to|n số học với số nguyên 2.5. Biểu diễn số thực 2.6. Biểu diễn kí tự 2
  3. Các hệ đếm cơ bản . Về mặt to|n học, ta có thể biểu diễn số theo hệ đếm cơ số bất kì. . Khi nghiên cứu về m|y tính, ta chỉ quan t}m đến c|c hệ đếm sau đ}y:  Hệ thập ph}n (Decimal System) → con người sử dụng  Hệ nhị ph}n (Binary System) → m|y tính sử dụng  Hệ mười s|u (Hexadecimal System) → dùng để viết gọn cho số nhị ph}n 3
  4. Hệ thập phân . Sử dụng 10 chữ số: 0,1,2,3,4,5,6,7,8,9 để biểu diễn số . Dùng n chữ số thập ph}n có thể biểu diễn được 10n gi| trị nguyên khác nhau: . 00 000 = 0 . . 99 999 = 10n-1 . Giả sử một số A được biểu diễn dưới dạng:  A = an an-1 a1 a0 . a-1 a-2 a-m . Gi| trị của A được hiểu như sau: n n 1 1 0 1 m A an10 an 110 a110 a010 a 110 a m10 n i A ai10 i m 4
  5. Ví dụ . Số thập ph}n 472.38 có gi| trị được hiểu như sau: 472.38 = 4 x 102 + 7 x 101 + 2 x 100 + 3 x 10-1 + 8 x 10-2 5
  6. Mở rộng cho hệ cơ số r (r>1) . Sử dụng r chữ số có gi| trị riêng từ 0 đến r-1 để biểu diễn số . Giả sử có số A được biểu diễn bằng c|c chữ số của hệ đếm theo cơ số r như sau:  A = an an-1 a1 a0 . a-1 a-2 a-m . Gi| trị của A l{: n n 1 1 0 1 2 m A anr an 1r a1r a0r a 1r a 2r a mr n i A air i m . Một chuỗi n chữ số của hệ đếm cơ số r sẽ biểu diễn được rn giá trị nguyên khác nhau. 6
  7. Hệ nhị phân . Sử dụng 2 chữ số: 0,1 . Chữ số nhị ph}n gọi l{ bit (binary digit) . Bit l{ đơn vị thông tin nhỏ nhất . Dùng n bit có thể biểu diễn được 2n gi| trị kh|c nhau:  00 000 = 0  n  11 111 = 2 -1 . Giả sử có số A được biểu diễn theo hệ nhị ph}n như sau: A = an an-1 a1 a0 . a-1 a-2 a-m . Với ai l{ c|c chữ số nhị ph}n, khi đó gi| trị của A l{: n n 1 1 0 1 2 m A an 2 an 1 2 a1 2 a0 2 a 1 2 a 2 2 a m 2 n i A ai 2 i m 7
  8. Ví dụ . Số nhị ph}n 1101001.1011 có gi| trị được x|c định như sau: 6 5 3 0 -1 -3 -4 1101001.1011(2) = 2 + 2 + 2 + 2 + 2 + 2 + 2 = 64 + 32 + 8 + 1 + 0.5 + 0.125 + 0.0625 = 105.6875(10) 8
  9. Đổi số thập phân sang nhị phân . Thực hiện chuyển đổi phần nguyên v{ phần lẻ riêng. . Chuyển đổi phần nguyên:  Cách 1: chia dần số đó cho 2, x|c định c|c phần dư, rồi viết c|c số dư theo chiều ngược lại. . Ví dụ: chuyển đổi 105(10) sang hệ nhị ph}n ta l{m như sau: 105 : 2 = 52 dư 1 52 : 2 = 26 dư 0 26 : 2 = 13 dư 0 13 : 2 = 6 dư 1 6 : 2 = 3 dư 0 3 : 2 = 1 dư 1 1 : 2 = 0 dư 1 Như vậy, ta có: 105(10) = 1101001(2) 9
  10. Đổi số thập phân sang nhị phân . Chuyển đổi phần nguyên (tiếp):  Cách 2: ph}n tích số đó th{nh tổng c|c lũy thừa của 2, sau đó dựa v{o c|c số mũ để x|c định dạng biểu diễn nhị ph}n. . Ví dụ: 105 = 64 + 32 + 8 + 1 = 26 + 25 + 23 + 20 105(10) = 1101001(2) . Chuyển đổi phần lẻ:  Nh}n phần lẻ với 2 rồi lấy phần nguyên Sau đó viết c|c phần nguyên theo chiều thuận. . Ví dụ: chuyển đổi số 0.6875(10) sang hệ nhị ph}n: 0.6875 x 2 = 1.3750 phần nguyên = 1 0.375 x 2 = 0.750 phần nguyên = 0 0.75 x 2 = 1.50 phần nguyên = 1 0.5 x 2 = 1.0 phần nguyên = 1 Kết quả l{: 0.6875(10) = 0.1011(2) 10
  11. 3. Hệ mười sáu (Hexa) . Sử dụng 16 chữ số, kí hiệu như sau: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F . Dùng để viết gọn cho số nhị phân. 11
  12. Một số ví dụ . Nhị ph}n Hexa: 11 1011 1110 0110.01101(2) = 3BE6.68(16) . Hexa Nhị ph}n: 3E8(16) = 11 1110 1000(2) . Thập ph}n Hexa: 14988 ? 14988 : 16 = 936 dư 12 tức l{ C 936 : 16 = 58 dư 8 58 : 16 = 3 dư 10 tức l{ A 3 : 16 = 0 dư 3 Như vậy, ta có: 14988(10) = 3A8C(16) . Hexa Thập ph}n: 3A8C ? 3 2 1 0 3A8C (16) = 3 x 16 + 10 x 16 + 8 x 16 +12 x 16 = 12288 + 2560 + 128 + 12 = 14988(10) 12
  13. Chuyển đổi nhanh . 105 = 6x16 + 9 = 69(16)= 110 1001 . 35 = 2x16 + 3 = 23(16) = 10 0011 13
  14. Cộng trừ số Hexa 8A9B B46E B7E5 FA9D + - + - 37CD 1AC9 2AF9 2BC5 C268 99A5 E2DE CED8 B800 8E9A 1234 4B6D + - + - 0FFF 3FE2 ABCD 3FEA CFFF A78D 879D 98BA + - + - 1FFF 45FB 5DF8 8A9D 14
  15. Nội dung chương 2 2.1. C|c hệ đếm cơ bản 2.2. M~ hóa v{ lưu trữ dữ liệu trong m|y tính 2.3. Biểu diễn số nguyên 2.4. C|c phép to|n số học với số nguyên 2.5. Biểu diễn số thực 2.6. Biểu diễn kí tự 15
  16. Mã hóa và lưu trữ dữ liệu 1. Nguyên tắc chung về m~ hóa dữ liệu 2. Lưu trữ thông tin trong bộ nhớ chính 16
  17. 1. Nguyên tắc chung về mã hóa dữ liệu . Mọi dữ liệu đưa v{o m|y tính đều phải được m~ hóa th{nh số nhị ph}n. . C|c loại dữ liệu :  Dữ liệu nh}n tạo: do con người quy ước  Dữ liệu tự nhiên: tồn tại kh|ch quan với con người 17
  18. Nguyên tắc mã hóa dữ liệu . M~ hóa dữ liệu nh}n tạo:  Dữ liệu số nguyên: m~ hóa theo chuẩn qui ước  Dữ liệu số thực: m~ hóa bằng số dấu chấm động  Dữ liệu ký tự: m~ hóa theo bộ m~ ký tự 18
  19. Nguyên tắc mã hóa dữ liệu (tiếp) . M~ hóa dữ liệu tự nhiên:  Phổ biến l{ c|c tín hiệu vật lý như }m thanh, hình ảnh,  C|c dữ liệu tự nhiên cần phải được số hóa (digitalized) trước khi đưa vào trong máy tính.  Sơ đồ m~ hóa v{ t|i tạo tín hiệu vật lý: 19
  20. Độ dài từ dữ liệu . Độ d{i từ dữ liệu:  L{ số bit được sử dụng để m~ hóa loại dữ liệu tương ứng  Trong thực tế, độ d{i từ dữ liệu thường l{ bội số của 8 bit, ví dụ: 8, 16, 32, 64 bit 10 20 30  1GB = 2 MB = 2 KB = 2 Byte 32  4GB = 2 Byte 20
  21. 2. Lưu trữ thông tin trong bộ nhớ chính . Bộ nhớ chính thường được tổ chức theo Byte . Độ d{i từ dữ liệu có thể chiếm 1 hoặc nhiều Byte . Cần phải biết thứ tự lưu trữ c|c byte trong bộ nhớ chính:  Lưu trữ kiểu đầu nhỏ (Little-endian)  Lưu trữ kiểu đầu to (Big-endian) . Little-endian: Byte có ý nghĩa thấp hơn được lưu trữ trong bộ nhớ ở vị trí có địa chỉ nhỏ hơn. . Big-endian: Byte có ý nghĩa thấp hơn được lưu trữ trong bộ nhớ ở vị trí có địa chỉ lớn hơn. 21
  22. Ví dụ  Intel 80x86, Pentium: Little-endian  Motorola 680x0, c|c bộ xử lý RISC: Big-endian  Power PC, Itanium: hỗ trợ cả hai (Bi-endian) 22
  23. Bài tập . Dữ liệu 16 bit có gi| trị l{ 5B9D được lưu trữ v{o bộ nhớ chính tổ chức theo kiểu Little-endian bắt đầu từ byte nhớ có địa chỉ l{ 1234. H~y x|c định nội dung c|c byte nhớ chứa lưu trữ dữ liệu đó dưới dạng nhị ph}n. 23
  24. Nội dung chương 2 2.1. C|c hệ đếm cơ bản 2.2. M~ hóa v{ lưu trữ dữ liệu trong m|y tính 2.3. Biểu diễn số nguyên 2.4. C|c phép to|n số học với số nguyên 2.5. Biểu diễn số thực 2.6. Biểu diễn kí tự 24
  25. Biểu diễn số nguyên 1. Số nguyên không dấu 2. Số nguyên có dấu 3. Biểu diễn số nguyên theo m~ BCD 25
  26. 1. Số nguyên không dấu . Dạng tổng qu|t: giả sử dùng n bit để biểu diễn cho một số nguyên không dấu A: an-1an-2 a3a2a1a0 . Gi| trị của A được tính như sau: n 1 n 2 1 0 A an 1 2 an 2 2 a1 2 a0 2 n 1 i A ai 2 i 0 . Dải biểu diễn của A: từ 0 đến 2n-1 26
  27. Các ví dụ . Ví dụ 1. Biểu diễn c|c số nguyên không dấu sau đ}y bằng 8 bit: A = 45 B = 156 Giải: A = 45 = 32 + 8 + 4 + 1 = 25 + 23 + 22 + 20 A = 0010 1101 B = 156 = 128 + 16 + 8 + 4 = 27 + 24 + 23 + 22 B = 1001 1100 27
  28. Các ví dụ (tiếp) . Ví dụ 2. Cho c|c số nguyên không dấu X, Y được biểu diễn bằng 8 bit như sau: X = 0010 1011 Y = 1001 0110 Giải: X = 0010 1011 = 25 + 23 + 21 + 20 = 32 + 8 + 2 + 1 = 43 Y = 1001 0110 = 27 + 24 + 22 + 21 = 128 + 16 + 4 + 2 = 150 28
  29. Trường hợp cụ thể: với n = 8 bit . Dải biểu diễn l{ [0, 255] . Trục số học máy tính: 0000 0000 = 0 255 0 1 0000 0001 = 1 254 2 0000 0010 = 2 3 0000 0011 = 3 1111 1111 = 255 . Trục số học: 0 1 2 255 29
  30. Với n = 8 bit . Kiểu dữ liệu tương ứng trong Turbo C l{ kiểu unsigned char. . Ví dụ: unsigned char a; 1111 1111 a = 255; + 0000 0001 a = a + 1; 1 0000 0000 printf(“%d”,a); //Kết quả sai l{ 0 KQ sai: 255 + 1 = 0 ? (do phép cộng bị nhớ ra ngoài) 30
  31. Với n = 16 bit, 32 bit, 64 bit . n = 16 bit:  Dải biểu diễn l{ [0, 65535]  Kiểu dữ liệu tương ứng trong Turbo C l{ kiểu unsigned int  Ví dụ: unsigned int a; a = 0xffff; a = a + 1; printf(“%d”,a); . n = 32 bit: 32  Dải biểu diễn l{ [0, 2 -1] . n = 64 bit: 64  Dải biểu diễn l{ [0, 2 -1] 31
  32. 2. Số nguyên có dấu a. Khái niệm về số bù . Số bù chín v{ số bù mười (hệ thập ph}n):  Giả sử có một số nguyên thập ph}n A được biểu diễn bởi n chữ số thập ph}n. Khi đó ta có: . Số bù chín của A = (10n - 1) - A . Số bù mười của A = 10n - A . NX: Số bù mười = Số bù chín + 1  Ví dụ: . Xét n = 4 chữ số, A = 2874 . Số bù chín của A = (104 - 1) - 2874 = 7125 . Số bù mười của A = 104 - 2874 = 7126 32
  33. Khái niệm về số bù . Số bù một v{ số bù hai (hệ nhị ph}n):  Giả sử có một số nguyên nhị ph}n A được biểu diễn bởi n bit. Khi đó ta có: . Số bù một của A = (2n - 1) - A . Số bù hai của A = 2n - A . NX: Số bù hai = Số bù một + 1  Ví dụ: . Xét n = 4 bit, A = 0110 . Số bù một của A = (24 - 1) - 0110 = 1001 . Số bù hai của A = 24 - 0110 = 1010 33
  34. Nhận xét . Có thể tìm số bù một của A bằng c|ch đảo tất cả c|c bit của A . Số bù hai của A = Số bù một của A + 1 34
  35. Nhận xét Ví dụ: cho A =0110 0101 Số bù một của A =1001 1010 + 1 Số bù hai của A =1001 1011 Nhận xét A = 0110 0101 Số bù hai của A += 1001 1011 1 0000 0000 = 0 (bỏ qua bit nhớ ra ngo{i) ->Số bù hai của A=-A 35
  36. Biểu diễn số nguyên có dấu b. Biểu diễn số nguyên có dấu bằng số bù hai . Dùng n bit biểu diễn số nguyên có dấu A: an-1an-2 a2a1a0 . Với số dương: . Bit an-1 = 0 . C|c bit còn lại biểu diễn độ lớn của số dương đó  Dạng tổng qu|t của số dương: 0an-2 a2a1a0  Gi| trị của số dương: n 2 i A ai 2 i 0 n-1  Dải biểu diễn của số dương: [0, 2 -1] 36
  37. Biểu diễn số nguyên có dấu (tiếp) . Với số }m: . Được biểu diễn bằng số bù hai của số dương tương ứng . Bit an-1 = 1  Dạng tổng qu|t của số }m: 1an-2 a2a1a0  Gi| trị của số }m: n 2 n 1 i A 2 ai 2 i 0 n-1  Dải biểu diễn của số }m: [-2 , -1] . Dải biểu diễn của số nguyên có dấu n bit l{ [-2n-1, 2n-1-1] 37
  38. Biểu diễn số nguyên có dấu (tiếp) . Dạng tổng qu|t của số nguyên có dấu A: an-1an-2 a2a1a0 . Gi| trị của A được x|c định như sau: n 2 n 1 i A an 12 ai 2 i 0 . Dải biểu diễn: [-2n-1, 2n-1-1] 38
  39. Các ví dụ . Ví dụ 1. Biểu diễn c|c số nguyên có dấu sau đ}y bằng 8 bit A = +50 B = -70 Giải: A = +50 = 32 + 16 + 2 = 25 + 24 + 21 A = 0011 0010 B = -70 Ta có: +70 = 64 + 4 + 2 = 26 + 22 + 21 +70 = 0100 0110 Số bù 1 = 1011 1001 + 1 Số bù 2 = 1011 1010 B = 1011 1010 39
  40. Các ví dụ (tiếp) . Ví dụ 2. X|c định gi| trị của c|c số nguyên có dấu 8 bit sau đ}y: A = 0101 0110 B = 1101 0010 Giải: A = 26 + 24 + 22 + 21 = 64 + 16 + 4 + 2 = +86 B = -27 + 26 + 24 + 21 = -128 + 64 + 16 + 2 = -46 40
  41. Trường hợp cụ thể: với n = 8 bit . Dải biểu diễn l{ [-128, +127] . Trục số học máy tính: 0000 0000 = 0 0000 0001 = +1 -1 0 +1 0000 0010 = +2 -2 +2 0111 1111 = +127 1000 0000 = -128 1000 0001 = -127 1111 1110 = -2 -128 +127 1111 1111 = -1 . Trục số học: -128 -2 -1 0 1 2 127 41
  42. Với n = 8 bit (tiếp) . Kiểu dữ liệu tương ứng trong Turbo C l{ kiểu char. . Ví dụ: char a; a = 127; 0111 1111 a = a + 1; + 0000 0001 printf(“%d”,a); //Kết quả sai l{ -128 1000 0000 KQ sai: 127 + 1 = -128 ? (do phép cộng bị tràn số học) 42
  43. Với n = 16 bit, 32 bit, 64 bit . n = 16 bit:  Dải biểu diễn l{ [-32768, +32767]  Kiểu dữ liệu tương ứng trong Turbo C l{ kiểu int . n = 32 bit: 31 31  Dải biểu diễn l{ [-2 , 2 -1]  Kiểu dữ liệu tương ứng trong Turbo C l{ kiểu long int . n = 64 bit: 63 63  Dải biểu diễn l{ [-2 , 2 -1] 43
  44. Chuyển từ 8 bit sang 16 bit . Với số dương: +35 = 0010 0011 (8 bit) +35 = 0000 0000 0010 0011 (16 bit) Thêm 8 bit 0 vào bên trái . Với số }m: -79 = 1011 0001 (8 bit) -79 = 1111 1111 1011 0001 (16 bit) Thêm 8 bit 1 vào bên trái . Kết luận: mở rộng sang bên tr|i 8 bit bằng bit dấu 44
  45. 3. Biểu diễn số nguyên theo mã BCD . BCD – Binary Coded Decimal (M~ hóa số nguyên thập ph}n bằng nhị ph}n) . Dùng 4 bit để m~ hóa cho c|c chữ số thập ph}n từ 0 đến 9 0 0000 5 0101 1 0001 6 0110 2 0010 7 0111 3 0011 8 1000 4 0100 9 1001 . Có 6 tổ hợp không sử dụng: 1010, 1011, 1100, 1101, 1110, 1111 45
  46. Ví dụ về số BCD . 35 0011 0101BCD . 79 0111 1001BCD . 2281 0010 0010 1000 0001BCD . 1304 0001 0011 0000 0100BCD 46
  47. Phép cộng số BCD . 35 0011 0101BCD + 24 + 0010 0100BCD 59  0101 1001BCD Kết quả đúng (không phải hiệu chỉnh) . 89 1000 1001BCD + 52 + 0101 0010BCD 141 1101 1011 kết quả sai + 0110 0110  hiệu chỉnh 0001 0100 0001BCD kết quả đúng 1 4 1 . Hiệu chỉnh: cộng thêm 6 ở những h{ng có nhớ 47
  48. Các kiểu lưu trữ số BCD . BCD dạng nén (Packed BCD): Hai số BCD được lưu trữ trong 1 Byte.  Ví dụ số 52 được lưu trữ như sau: 0101 0010 . BCD dạng không nén (Unpacked BCD): Mỗi số BCD được lưu trữ trong 4 bit thấp của mỗi Byte.  Ví dụ số 52 được lưu trữ như sau: 0101 0010 48
  49. Nội dung chương 2 2.1. C|c hệ đếm cơ bản 2.2. M~ hóa v{ lưu trữ dữ liệu trong m|y tính 2.3. Biểu diễn số nguyên 2.4. C|c phép to|n số học với số nguyên 2.5. Biểu diễn số thực 2.6. Biểu diễn kí tự 49
  50. Các phép toán số học với số nguyên 1. Bộ cộng 2. Cộng số nguyên không dấu 3. Cộng/trừ số nguyên có dấu 4. Nh}n số nguyên 5. Chia số nguyên 50
  51. 1. Bộ cộng . Bộ cộng 1 bit to{n phần (Full Adder) 51
  52. Bộ cộng (tiếp) . Bộ cộng n bit 52
  53. 2. Cộng số nguyên không dấu . Nguyên tắc: Sử dụng bộ cộng n bit để cộng 2 số nguyên không dấu n bit, kết quả nhận được cũng l{ n bit.  Nếu không có nhớ ra khỏi bit cao nhất (Cout=0) thì kết quả nhận được l{ đúng.  Nếu có nhớ ra khỏi bit cao nhất (Cout=1) thì kết quả nhận được l{ sai, khi đó đ~ xảy ra hiện tượng nhớ ra ngo{i. . Hiện tượng nhớ ra ngoài (Carry-out) xảy ra khi tổng của 2 số nguyên không dấu n bit > 2n-1 53
  54. VD cộng số nguyên không dấu 8 bit . Trường hợp không xảy ra carry-out: X = 1001 0110 = 150 Y = 0001 0011 = 19 S = 1010 1001 = 169 Cout = 0 . Trường hợp có xảy ra carry-out: unsigned char x, y, s; X = 1100 0101 = 197 x = 197; Y = 0100 0110 = 70 y = 70; S = 0000 1011 267 s = x + y; C = 1 carry-out out printf(“%d”,s); (KQ sai = 23 + 21 + 20 = 11) 54
  55. 3. Cộng/trừ số nguyên có dấu . Khi cộng hai số nguyên có dấu n bit, ta không quan t}m đến bit Cout v{ kết quả nhận được cũng l{ n bit.  Cộng hai số kh|c dấu: kết quả luôn đúng  Cộng hai số cùng dấu: . Nếu tổng nhận được cùng dấu với 2 số hạng thì kết quả l{ đúng . Nếu tổng nhận được kh|c dấu với 2 số hạng thì đ~ xảy ra hiện tượng tràn số học (Overflow) v{ kết quả nhận được l{ sai  Tr{n số học xảy ra khi tổng thực sự của hai số nằm ngo{i dải biểu diễn của số nguyên có dấu n bit: [-2n-1, 2n-1-1] 55
  56. Phép trừ số nguyên có dấu . Nguyên tắc thực hiện phép trừ:  Ta có: X – Y = X + (-Y)  C|ch thực hiện: lấy X cộng với số bù 2 của Y n-bit Y n-bit X Bù 2 Bộ cộng n bit n-bit S 56
  57. Ví dụ cộng 2 số nguyên có dấu (không tràn) 57
  58. Ví dụ cộng 2 số nguyên có dấu (Overflow) 58
  59. 4. Nhân số nguyên a. Nh}n số nguyên không dấu b. Nh}n số nguyên có dấu 59
  60. a. Nhân số nguyên không dấu . C|c tích riêng phần được x|c định như sau:  Nếu bit của số nh}n = 0 → tích riêng phần = 0  Nếu bit của số nh}n = 1 → tích riêng phần = số bị nh}n  Tích riêng phần tiếp theo được dịch tr|i 1 bit so với tích riêng phần trước đó . Tích = tổng c|c tích riêng phần . Nh}n 2 số nguyên n bit, tích có độ d{i 2n bit → không tr{n 60
  61. Bộ nhân số nguyên không dấu Số bị nhân M Mn-1 M1 M0 Điều khiển cộng Bộ cộng n bit Bộ điều khiển dịch và cộng Điều khiển dịch phải C An-1 A1 A0 Qn-1 Q1 Q0 Số nhân Q 61
  62. Lưu đồ thực hiện Bắt đầu C, A ¬ 0 M ¬ Số bị nhân Q ¬ Số nhân Bộ đếm ¬ n S Đ Q0 = 1 ? C, A ¬ A M Dịch phải C, A, Q Bộ đếm ¬ Bộ đếm - 1 S Đ Bộ đếm = 0 ? Kết thúc 62
  63. Ví dụ nhân số nguyên không dấu . M = 1011 (11 - Số bị nhân) . Q = 1101 (13 - Số nhân) . = 1000 1111 (143 - Tích) C A Q . 0 0000 1101 Các giá trị khởi đầu + 1011 . 0 1011 1101 A ¬ A + M 0 0101 1110 Dịch phải . 0 0010 1111 Dịch phải + 1011 . 0 1101 1111 A ¬ A + M 0 0110 1111 Dịch phải + 1011 . 1 0001 1111 A ¬ A + M 0 1000 1111 Dịch phải 63
  64. b. Nhân số nguyên có dấu . Sử dụng thuật giải nh}n không dấu:  Bước 1: Chuyển đổi số nh}n v{ số bị nh}n th{nh số dương tương ứng.  Bước 2: Nhân 2 số bằng thuật giải nh}n số nguyên không dấu → được tích 2 số dương.  Bước 3: Hiệu chỉnh dấu của tích: . Nếu 2 thừa số ban đầu cùng dấu thì tích nhận được ở bước 2 l{ kết quả cần tính. . Nếu 2 thừa số ban đầu kh|c dấu nhau thì kết quả l{ số bù 2 của tích nhận được ở bước 2. 64
  65. Nhân số nguyên có dấu . Sử dụng thuật giải Booth:  Với số nh}n dương: . Ta có: 2i + 2i-1 + + 2j = 2i+1 - 2j (với i j) . VD: M * 01110010 = M * (27 – 24 + 22 – 21) . Quy tắc: duyệt từ tr|i sang phải:  Nếu gặp 10 thì trừ A đi M rồi dịch phải  Nếu gặp 01 thì cộng A với M rồi dịch phải  Nếu gặp 00 hay 11 thì chỉ dịch phải  Với số nh}n }m: . Ta có: n-1 n-2 k+1 k-1 0 11 10ak-1ak-2 a0 = -2 + 2 + + 2 + ak-12 + + a02 n-1 n-1 k+1 k-1 0 = -2 + 2 - 2 + ak-12 + + a02 . -2k+1 ứng với bit 10 nên vẫn đảm bảo quy tắc ở TH trên 65
  66. Lưu đồ thực hiện thuật toán Booth Bắt đầu A Q Q-1 A ¬ 0 Q-1 ¬ 0 M ¬ Số bị nhân Q ¬ Số nhân Bộ đếm ¬ n = 10 = 01 Q0Q-1 A ¬ A M = 00 / 11 A ¬ A M Dịch phải A, Q, Q-1 (Giữ nguyên bit dấu của A) Bộ đếm ¬ Bộ đếm - 1 S Đ Bộ đếm = 0 ? Kết thúc 66
  67. Ví dụ về thuật toán Booth Ví dụ 1: Ví dụ 2: n = 4 bit, M = +7, Q = +3 n = 4 bit, M = +7, Q = -3 M = 0111, Q = 0011, -M = 1001 M = 0111, Q = 1101, -M = 1001 A Q Q-1 A Q Q-1 0000 0011 0 ; khởi tạo 0000 1101 0 ; khởi tạo +1001 +1001 1001 0011 0 ; A ¬ A - M 1001 1101 0 ; A ¬ A - M 1100 1001 1 ; dịch phải 1100 1110 1 ; dịch phải 1110 0100 1 ; dịch phải +0111 +0111 10011 1110 1 ; A ¬ A + M 10101 0100 1 ; A ¬ A + M 0001 1111 0 ; dịch phải 0010 1010 0 ; dịch phải +1001 0001 0101 0 ; dịch phải 1010 1111 0 ; A ¬ A - M 1101 0111 1 ; dịch phải 1110 1011 1 ; dịch phải 67
  68. 5. Chia số nguyên a. Chia số nguyên không dấu b. Chia số nguyên có dấu 68
  69. a. Chia số nguyên không dấu . Ví dụ: 69
  70. Bộ chia số nguyên không dấu Số chia M Mn-1 M1 M0 Điều khiển cộng/trừ Bộ logic điều khiển Bộ cộng/trừ n bit cộng, trừ và dịch Điều khiển dịch trái An-1 A1 A0 Qn-1 Q1 Q0 Số bị chia Q 70
  71. Lưu đồ thực hiện Bắt đầu A ¬ 0 M ¬ Số chia Q ¬ Số bị chia Bộ đếm ¬ 0 Dịch trái A, Q A ¬ A M S Đ A < 0 ? Q ¬ 0 Q ¬ 1 0 0 A ¬ A M Bộ đếm ¬ Bộ đếm - 1 S Đ Bộ đếm = 0 ? Kết thúc 71
  72. b. Chia số nguyên có dấu . Bước 1: Chuyển đổi số chia v{ số bị chia th{nh số dương tương ứng . Bước 2: Sử dụng thuật giải chia số nguyên không dấu để chia 2 số dương, kết quả nhận được l{ thương Q v{ phần dư R đều dương . Bước 3: Hiệu chỉnh dấu kết quả theo quy tắc sau: 72
  73. Nội dung chương 2 2.1. C|c hệ đếm cơ bản 2.2. M~ hóa v{ lưu trữ dữ liệu trong m|y tính 2.3. Biểu diễn số nguyên 2.4. C|c phép to|n số học với số nguyên 2.5. Biểu diễn số thực 2.6. Biểu diễn kí tự 73
  74. Biểu diễn số thực 1. Kh|i niệm về số dấu chấm tĩnh 2. Kh|i niệm về số dấu chấm động 3. Chuẩn IEEE 754/85 74
  75. Biểu diễn số thực . Quy ước: "dấu chấm" (point) được hiểu l{ kí hiệu ngăn c|ch giữa phần nguyên v{ phần lẻ của 1 số thực. . Có 2 c|ch biểu diễn số thực trong m|y tính:  Só dáu chám tĩnh (fixed-point number): . Dấu chấm l{ cố định (số bit d{nh cho phần nguyên v{ phần lẻ l{ cố định) . Dù ng trong các bo ̣ vi xử lý hay vi đièu khiẻn thế hệ cũ .  Só dáu chám đo ̣ng (floating-point number): . Dấu chấm không cố định . Dù ng trong các bo ̣ vi xử lý hie ̣n nay, có đo ̣ chính xác cao hơn. 75
  76. 1. Khái niệm về số dấu chấm tĩnh . Số bit d{nh cho phần nguyên v{ số bit phần lẻ l{ cố định. . Giả sử rằng:  U(a,b) là ta ̣p các só dáu chám tĩnh không dấu có a bit trướ c dáu chám và b bit sau dáu chám.  A(a,b) là ta ̣p các só dáu chám tĩnh có dấu có a bit (không kẻ bit dáu) trướ c dáu chám và b bit sau dáu chám. 76
  77. Số dấu chấm tĩnh không dấu . Khoảng x|c định của số dấu chấm tĩnh không dấu: [0, 2a - 2-b] . Ví dụ:  Dùng 8 bit để m~ hóa cho kiểu số dấu chấm tĩnh, trong đó có 2 bit d{nh cho phần lẻ. Khoảng x|c định của kiểu dữ liệu này là: 0 R 26 – 2-2 = 63.75 -2  VD: gi| trị của 101011.11 = 10101111 x 2 = 43.75 77
  78. Số dấu chấm tĩnh có dấu . Khoảng x|c định của số dấu chấm tĩnh có dấu: [-2a, 2a - 2-b] . Ví dụ:  Dùng 8 bit đẻ biẻu diẽn só chám tĩnh có dáu với a=5, b=2  Ta đượ c ta ̣p các só chấm tĩnh thuo ̣c A(5,2) nàm trong khoảng: [-25, 25 – 2-2] hay [-32, 31.75] 78
  79. Đặc điểm của số dấu chấm tĩnh . C|c phép to|n thực hiện nhanh. . Độ chính x|c khi thực hiện c|c phép to|n không cao, đạ c bie ̣t là với phép tính nhân. . Ví dụ:  Khi thực hiện phép nh}n ta cần phải có thêm một số lượng bit nhất định để biểu diễn kết quả.  Đói vớ i só không dáu: U(a1, b1) x U(a2, b2) = U(a1 + a2, b1 + b2)  Đói vớ i só có dáu: A(a1, b1) x A(a2, b2) = A(a1 + a2 + 1, b1 + b2) 79
  80. 2. Khái niệm về số dấu chấm động . Floating Point Number biểu diễn cho số thực . Một số thực X được biểu diễn theo kiểu số dấu chấm động như sau: X = M * RE Trong đó:  M l{ phần định trị (Mantissa)  R l{ cơ số (Radix)  E l{ phần mũ (Exponent) . Với R cố định thì để lưu trữ X ta chỉ cần lưu trữ M v{ E (dưới dạng số nguyên) 80
  81. 3. Chuẩn IEEE 754/85 . L{ chuẩn m~ hóa số dấu chấm động . Cơ số R = 2 . Có c|c dạng cơ bản:  Dạng có độ chính x|c đơn, 32-bit  Dạng có độ chính x|c kép, 64-bit  Dạng có độ chính x|c kép mở rộng, 80-bit . Khuôn dạng m~ hóa: 31 30 23 22 0 S e m 63 62 52 51 0 S e m 79 78 64 63 0 S e m 81
  82. Khuôn dạng mã hóa . S l{ bit dấu, S=0 đó l{ số dương, S=1 đó l{ số }m. . e l{ m~ lệch (excess) của phần mũ E, tức l{: E = e – b Trong đó b l{ độ lệch (bias):  Dạng 32-bit : b = 127, hay E = e - 127  Dạng 64-bit : b = 1023, hay E = e - 1023  Dạng 80-bit : b = 16383, hay E = e - 16383 . m l{ c|c bit phần lẻ của phần định trị M, phần định trị được ngầm định như sau: M = 1.m . Công thức x|c định gi| trị của số thực tương ứng l{: X = (-1)S x 1.m x 2e-b 82
  83. Ví dụ về số dấu chấm động . Ví dụ 1: Có một số thực X có dạng biểu diễn nhị ph}n theo chuẩn IEEE 754 dạng 32 bit như sau: 1100 0001 0101 0110 0000 0000 0000 0000 X|c định gi| trị thập ph}n của số thực đó. . Giải:  S = 1 X l{ số }m  e = 1000 0010 = 130  m = 10101100 00 1 130-127  Vậy X = (-1) x 1.10101100 00 x 2 = -1.101011 x 23 = -1101.011 = -13.375 83
  84. Ví dụ về số dấu chấm động (tiếp) . Ví dụ 2: X|c định gi| trị thập ph}n của số thực X có dạng biểu diễn theo chuẩn IEEE 754 dạng 32 bit như sau: 0011 1111 1000 0000 0000 0000 0000 0000 . Giải: 84
  85. Ví dụ về số dấu chấm động (tiếp) . Ví dụ 3: Biểu diễn số thực X = 9.6875 về dạng số dấu chấm động theo chuẩn IEEE 754 dạng 32 bit . Giải: 3 X = 9.6875(10) = 1001.1011(2) = 1.0011011 x 2 Ta có:  S = 0 vì đ}y l{ số dương  E = e – 127 nên e = 127 + 3 = 130(10) = 1000 0010(2)  m = 001101100 00 (23 bit) Vậy: X = 0100 0001 0001 1011 0000 0000 0000 0000 85
  86. Các quy ước đặc biệt . Nếu tất cả c|c bit của e đều bằng 0, c|c bit của m đều bằng 0, thì X = 0 . Nếu tất cả c|c bit của e đều bằng 1, c|c bit của m đều bằng 0, thì X = . Nếu tất cả c|c bit của e đều bằng 1, m có ít nhất một bit bằng 1, thì X không phải l{ số (not a number - NaN) 86
  87. Trục số biểu diễn underflow overflow overflow -b -a -0 +0 a b . Dạng 32 bit: a = 2-127 ≈ 10-38 b = 2+127 ≈ 10+38 . Dạng 64 bit: a = 2-1023 ≈ 10-308 b = 2+1023 ≈ 10+308 . Dạng 80 bit: a = 2-16383 ≈ 10-4932 b = 2+16383 ≈ 10+4932 87
  88. Thực hiện các phép toán E1 . X1 = M1 * R E2 . X2 = M2 * R . Ta có E1-E2 E2  X1 X2 = (M1 * R M2) * R , với E2 E1 E1+E2  X1 * X2 = (M1 * M2) * R E1-E2  X1 / X2 = (M1 / M2) * R 88
  89. Các khả năng tràn số . Tr{n trên số mũ (Exponent Overflow): mũ dương vượt ra khỏi gi| trị cực đại của số mũ dương có thể. . Tr{n dưới số mũ (Exponent Underflow): mũ }m vượt ra khỏi gi| trị cực đại của số mũ }m có thể. . Tr{n trên phần định trị (Mantissa Overflow): cộng hai phần định trị có cùng dấu, kết quả bị nhớ ra ngo{i bit cao nhất. . Tr{n dưới phần định trị (Mantissa Underflow): Khi hiệu chỉnh phần định trị, c|c số bị mất ở bên phải phần định trị. 89
  90. Phép cộng và phép trừ . Kiểm tra c|c số hạng có bằng 0 hay không  Nếu có thì g|n kết quả dựa trên số còn lại. . Hiệu chỉnh phần định trị  Sao cho 2 số có phần mũ giống nhau: tăng số mũ nhỏ v{ dịch phải phần định trị tương ứng (dịch phải để hạn chế sai số nếu có). 3 3 3  VD: 1.01 * 2 + 1.11 = 1.01 * 2 + 0.00111 * 2 . Cộng hoặc trừ phần định trị  Nếu tr{n thì dịch phải v{ tăng số mũ, nếu bị tr{n số mũ thì b|o lỗi tr{n số. . Chuẩn hóa kết quả  Dịch tr|i phần định trị để bit tr|i nhất (bit MSB) kh|c 0.  Tương ứng với việc giảm số mũ nên có thể dẫn đến hiện tượng tr{n dưới số mũ. 90
  91. Nội dung chương 2 2.1. C|c hệ đếm cơ bản 2.2. M~ hóa v{ lưu trữ dữ liệu trong m|y tính 2.3. Biểu diễn số nguyên 2.4. C|c phép to|n số học với số nguyên 2.5. Biểu diễn số thực 2.6. Biểu diễn kí tự 91
  92. Biểu diễn kí tự trong máy tính 1. Bộ m~ ASCII (American Standard Code for Information Interchange) 2. Bộ m~ Unicode 92
  93. 1. Bộ mã ASCII . Do ANSI (American National Standard Institute) thiết kế . L{ bộ m~ 8 bit m~ hóa được cho 28 = 256 kí tự, có m~ từ 0016  FF16, bao gồm:  128 kí tự chuẩn có m~ từ 0016  7F16  128 kí tự mở rộng có m~ từ 8016  FF16 93
  94. HEXA 0 1 2 3 4 5 6 7 0 0 @ P ` p 0 16 32 48 64 80 96 112 1 ! 1 A Q a q 1 17 33 49 65 81 97 113 2 " 2 B R b r 2 18 34 50 66 82 98 114 3 # 3 C S c s 3 19 35 51 67 83 99 115 4 $ 4 D T d t 4 20 36 52 68 84 100 116 5 % 5 E U e u 5 21 37 53 69 85 101 117 6 & 6 F V f v 6 22 38 54 70 86 102 118 7 ' 7 G W g w 7 23 39 55 71 87 103 119 8 ( 8 H X h x 8 24 40 56 72 88 104 120 9 ) 9 I Y i y 9 25 41 57 73 89 105 121 A * : J Z j z 10 26 42 58 74 90 106 122 B + ; K [ k { 11 27 43 59 75 91 107 123 C , - = M ] m } 13 29 45 61 77 93 109 125 E . > N ^ n ~ 14 30 46 62 78 94 110 126 F / ? O - o 15 31 47 63 79 95 111 127 94
  95. a. Các kí tự chuẩn . 95 kí tự hiển thị được: có m~ từ 2016 ÷ 7E16  26 chữ c|i hoa Latin 'A' ÷ 'Z' có m~ từ 4116 ÷ 5A16  26 chữ c|i thường Latin 'a' ÷ 'z' có m~ từ 6116 ÷ 7A16  10 chữ số thập ph}n '0' ÷ '9' có m~ từ 3016 ÷ 3916  C|c dấu c}u: . , ? ! : ;  C|c dấu phép to|n: + - * /  Một số kí tự thông dụng: #, $, &, @,  Dấu c|ch (m~ l{ 2016) . 33 m~ điều khiển: m~ từ 0016 ÷ 1F16 và 7F16 dùng để m~ hóa cho c|c chức năng điều khiển 95
  96. Điều khiển định dạng BS Backspace - Lùi lại một vị trí: Ký tự điều khiển con trỏ lùi lại một vị trí. HT Horizontal Tab - Tab ngang: Ký tự điều khiển con trỏ dịch tiếp một khoảng đã định trước. LF Line Feed - Xuống một dòng: Ký tự điều khiển con trỏ chuyển xuống dòng dưới. VT Vertical Tab - Tab đứng: Ký tự điều khiển con trỏ chuyển qua một số dòng đã định trước. FF Form Feed - Đẩy sang đầu trang: Ký tự điều khiển con trỏ di chuyển xuống đầu trang tiếp theo. CR Carriage Return - Về đầu dòng: Ký tự điều khiển con trỏ di chuyển về đầu dòng hiện hành. 96
  97. Điều khiển truyền số liệu SOH Start of Heading - Bắt đầu tiêu đề: Ký tự đánh dấu bắt đầu phần thông tin tiêu đề. STX Start of Text - Bắt đầu văn bản: Ký tự đánh dấu bắt đầu khối dữ liệu văn bản và cũng chính là để kết thúc phần thông tin tiêu đề. ETX End of Text - Kết thúc văn bản: Ký tự đánh dấu kết thúc khối dữ liệu văn bản đã được bắt đầu bằng STX. EOT End of Transmission - Kết thúc truyền: Chỉ ra cho bên thu biết kết thúc truyền. ENQ Enquiry - Hỏi: Tín hiệu yêu cầu đáp ứng từ một máy ở xa. ACK Acknowledge - Báo nhận: Ký tự được phát ra từ phía thu báo cho phía phát biết rằng dữ liệu đã được nhận thành công. NAK Negative Aknowledge - Báo phủ nhận: Ký tự được phát ra từ phía thu báo cho phía phát biết rằng việc nhận dữ liệu không thành công. SYN Synchronous / Idle - Đồng bộ hóa: Được sử dụng bởi hệ thống truyền đồng bộ để đồng bộ hoá quá trình truyền dữ liệu. ETB End of Transmission Block - Kết thúc khối truyền: Chỉ ra kết thúc khối dữ liệu được truyền. 97
  98. Điều khiển phân cách thông tin FS File Separator - Ký hiệu phân cách tập tin: Đánh dấu ranh giới giữa các tập tin. GS Group Separator - Ký hiệu phân cách nhóm: Đánh dấu ranh giới giữa các nhóm tin (tập hợp các bản ghi). RS Record Separator - Ký hiệu phân cách bản ghi: Đánh dấu ranh giới giữa các bản ghi. US Unit Separator - Ký hiệu phân cách đơn vị: Đánh dấu ranh giới giữa các phần của bản ghi. 98
  99. Các kí tự điều khiển khác NUL Null - Ký tự rỗng: Được sử dụng để điền khoảng trống khi không có dữ liệu. BEL Bell - Chuông: Được sử dụng phát ra tiếng bíp khi cần gọi sự chú ý của con người. SO Shift Out - Dịch ra: Chỉ ra rằng các mã tiếp theo sẽ nằm ngoài tập ký tự chuẩn cho đến khi gặp ký tự SI. SI Shift In - Dịch vào: Chỉ ra rằng các mã tiếp theo sẽ nằm trong tập ký tự chuẩn. DLE Data Link Escape - Thoát liên kết dữ liệu: Ký tự sẽ thay đổi ý nghĩa của một hoặc nhiều ký tự liên tiếp sau đó. DC1 ÷ Device Control - Điều khiển thiết bị : Các ký tự dùng để điều khiển các thiết bị DC4 phụ trợ. CAN Cancel - Hủy bỏ: Chỉ ra rằng một số ký tự nằm trước nó cần phải bỏ qua. EM End of Medium - Kết thúc phương tiện: Chỉ ra ký tự ngay trước nó là ký tự cuối cùng có tác dụng với phương tiện vật lý. SUB Substitute - Thay thế: Được thay thế cho ký tự nào được xác định là bị lỗi. ESC Escape - Thoát: Ký tự được dùng để cung cấp các mã mở rộng bằng cách kết hợp với ký tự sau đó. DEL Delete - Xóa: Dùng để xóa các ký tự không mong muốn. 99
  100. b. Các kí tự mở rộng . Được định nghĩa bởi:  Nh{ chế tạo m|y tính  Người ph|t triển phần mềm . Ví dụ:  Bộ m~ ký tự mở rộng của IBM: được dùng trên m|y tính IBM-PC.  Bộ m~ ký tự mở rộng của Apple: được dùng trên m|y tính Macintosh.  C|c nh{ ph|t triển phần mềm tiếng Việt cũng đ~ thay đổi phần n{y để m~ ho| cho c|c ký tự riêng của chữ Việt, ví dụ như bộ m~ TCVN 5712. 100
  101. 2. Bộ mã Unicode . Do c|c h~ng m|y tính h{ng đầu thiết kế . L{ bộ m~ 16-bit . Được thiết ké cho đa ngôn ngữ, trong đó có tiếng Việt 101
  102. Bài tập 1 . Giả sử có c|c biến nhớ dưới đ}y chứa c|c số nguyên có dấu 8-bit với nội dung biểu diễn theo hệ 16 như sau: P = 3A Q = 7C R = DE S = FF H~y x|c định gi| trị của c|c biến nhớ đó dưới dạng số thập ph}n. 102
  103. Bài tập 2 . Giả sử có X thuộc kiểu số nguyên có dấu 16-bit, nó được g|n gi| trị dưới dạng thập ph}n bằng -1234. H~y cho biết nội dung của c|c byte nhớ chứa biến đó dưới dạng Hexa, biết rằng bộ nhớ lưu trữ theo kiểu đầu nhỏ (little-endian). 103
  104. Bài tập 3 . Giả sử có biến P chứa số nguyên có dấu 16 bit. Nội dung của biến P được cho trong bộ nhớ như sau: 9D(16) Địa chỉ 80 tăng dần (16) H~y x|c định gi| trị(Lit tlcủae-end biếnian) P dưới dạng thập ph}n. 104
  105. Bài tập 4 . Giả sử có một biến số thực X được biểu diễn bằng số dấu chấm động theo chuẩn IEEE 754 dạng 32 bit, nó chiếm 4 byte trong bộ nhớ với nội dung được chỉ ra ở hình vẽ sau. 00(16) 80(16) Địa chỉ tăng dần D9(16) C3(16) Biết rằng bộ nhớ tổ chức theo kiểu đầu nhỏ (little-endian), hãy x|c định gi| trị thập ph}n của số thực đó. 105
  106. Bài tập 5 . Giả sử có biến X thuộc kiểu số dấu chấm động theo chuẩn IEEE 754 dạng 32 bit. Nó được g|n gi| trị dưới dạng thập ph}n bằng -124.125 v{ lưu trữ v{o bộ nhớ bắt đầu từ byte nhớ có địa chỉ l{ 200. H~y cho biết nội dung của c|c byte nhớ chứa biến đó dưới dạng Hexa, biết rằng bộ nhớ lưu trữ theo kiểu đầu nhỏ (little- endian). 106