›
›

Bài giảng 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 105 trang ngocly 60
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng 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:

  • pdfbai_giang_cau_truc_may_tinh_chuong_2_bieu_dien_du_lieu_va_so.pdf

Nội dung text: Bài giảng 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 62
  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ự 63
  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 64
  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ị 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 65
  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 66
  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ị khác nhau. 67
  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   11 111 = 2n-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 68
  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) 69
  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) 70
  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) 71
  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. 72
  12. Một số ví dụ . Nhị phân Hexa: 11 1011 1110 0110(2) = 3BE6(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) 73
  13. 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 74
  14. 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ự 75
  15. 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 76
  16. 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 77
  17. 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ự 78
  18. 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ý: TÝn hiÖu ®iÖn Bé c¶m biÕn Bé chuyÓn ®æi TÝn hiÖu vËt lý liªn tôc TÝn hiÖu sè tÝn hiÖu t•¬ng tù - sè (sensor) (ADC) M¸y tÝnh TÝn hiÖu ®iÖn Bé chuyÓn ®æi TÝn hiÖu vËt lý Bé t¸i t¹o liªn tôc TÝn hiÖu sè sè - t•¬ng tù tÝn hiÖu (DAC) 79
  19. Độ 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 80
  20. 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. 81
  21. 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) 82
  22. 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. 83
  23. 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ự 84
  24. 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 85
  25. 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 86
  26. 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 87
  27. 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 88
  28. 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 89
  29. 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) 90
  30. 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] 91
  31. 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 92
  32. 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 93
  33. 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 94
  34. 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 95
  35. 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] 96
  36. 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] 97
  37. 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 1 2 ai 2 i 0 . Dải biểu diễn: [-2n-1, 2n-1-1] 98
  38. 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 99
  39. 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 100
  40. 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 101
  41. 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) 102
  42. 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] 103
  43. 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 104
  44. 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 105
  45. Ví dụ về số BCD . 35 0011 0101BCD . 79 0111 1001BCD . 2281 0010 0010 1000 0001BCD . 1304 0001 0011 0000 0100BCD 106
  46. 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ớ 107
  47. 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 108
  48. 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ự 109
  49. 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 110
  50. 1. Bộ cộng . Bộ cộng 1 bit toàn phần (Full Adder) 111
  51. Bộ cộng (tiếp) . Bộ cộng n bit 112
  52. 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 113
  53. 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) 114
  54. 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] 115
  55. 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ï hai Bé céng n-bit n-bit S 116
  56. Ví dụ cộng 2 số nguyên có dấu (không tràn) 117
  57. Ví dụ cộng 2 số nguyên có dấu (Overflow) 118
  58. 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 119
  59. 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 120
  60. 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 121
  61. 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 122
  62. 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 123
  63. 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. 124
  64. 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 125
  65. 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 126
  66. 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 127
  67. 5. Chia số nguyên a. Chia số nguyên không dấu b. Chia số nguyên có dấu 128
  68. a. Chia số nguyên không dấu . Ví dụ: 129
  69. 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 130
  70. 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 131
  71. 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: 132
  72. 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ự 133
  73. 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 134
  74. 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 bộ vi xử lý hay vi điều khiển thế hệ cũ.  Số dấu chấm động (floating-point number): . Dấu chấm không cố định . Dùng trong các bộ vi xử lý hiện nay, có độ chính xác cao hơn. 135
  75. 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à tậ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à tậ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. 136
  76. 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 137
  77. 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 tập các số chấm tĩnh thuộc A(5,2) nằm trong khoảng: [-25, 25 – 2-2] hay [-32, 31.75] 138
  78. Đặ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 biệ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) 139
  79. 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) 140
  80. 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 141
  81. 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 142
  82. 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 143
  83. 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: 144
  84. 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 145
  85. 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) 146
  86. 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 147
  87. 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 148
  88. 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ị. 149
  89. 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ũ. 150
  90. 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ự 151
  91. 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 152
  92. 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 153
  93. 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 154
  94. 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 155
  95. Đ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. 156
  96. Đ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. 157
  97. Đ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. 158
  98. 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. 159
  99. 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. 160
  100. 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 161
  101. 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. 162
  102. 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). 163
  103. 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ỉ tăng dần 80(16) (Little-endian) Hãy xác định giá trị của biến P dƣới dạng thập phân. 164
  104. 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 đó. 165
  105. 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). 166