Bài giảng Nhập môn điện toán - Chương I: Khái niệm cơ bản

 
Chia lấy số dư
Dec2Xxx
Chia cơ số
Kết quả 
Số hệ 10
Chia cơ số
Kết quả 
Chia cơ số
Kết quả 
Chia cơ số
kq = 0 : dừng Số dư Số dư Số dư Số dư . . .
Số hệ Xxx
Khoa KH & KT ynh, CH KHOA TP.HCM
Ví dụ Dec2Bin
Nhập môn Điện Toán -Chương 1 Slide 23
2
17
1
35
1
= 0
Số hệ 2
2
8
2
0
4
2
2
2
00
1
2
1
Số hệ 10
1x201x21Số hệ 10 : 35 = 0x220x230x241x25
Chuyển đổi từ hệ thập
phân sang hệ nhị phân. 
Vd:
35 = 100011B
Khoa KH & KT ynh, CH KHOA TP.HCM
Ví dụ Dec2Hex
Nhập môn Điện Toán -Chương 1 Slide 24
16
125
2004
= 0
Số hệ 16
7
Số hệ 10
Số hệ 10 : 2004 = 7 x 162
16
13 x 161 4 x 160
7 D 4
16
Chuyển đổi từ hệ thập
phân sang hệ thập lục
phân (hệ 16). Vd:
35 = 23H
2004 = 7D4H
Khoa KH & KT ynh, CH KHOA TP.HCM
Đổi hệ 2 ra hệ 8, 16
Nhập môn Điện Toán -Chương 1 Slide 25
Ghép nhóm + bảng chuyển
miêu tả số
11Số hệ 2 000101
3Số hệ 8 42
(011)(100)(010)
3 bit
11Số hệ 2 000101
3Số hệ 16
(0011)
4 bit
A
(1010)Mã 8421
Mã 8421
Bin2Oct
Bin2Hex
3 bit3 bit
4 bit10100011B = 163
10100011B = 243O
10100011B = A3H
Khoa KH & KT ynh, CH KHOA TP.HCM
Bảng chuyển miêu tả số
Nhập môn Điện Toán -Chương 1 Slide 26
Số hệ 10 Số hệ 16 Số hệ 8 Số hệ 2
0 0 0 0000
1 1 1 0001
2 2 2 0010
3 3 3 0011
4 4 4 0100
5 5 5 0101
6 6 6 0110
7 7 7 0111
8 8 10 1000
9 9 11 1001
10 A 12 1010
11 B 13 1011
12 C 14 1100
13 D 15 1101
14 E 16 1110
15 F 17 1111
Khoa KH & KT ynh, CH KHOA TP.HCM
Chuyển đổi số
Nhập môn Điện Toán -Chương 1 Slide 27
1A2H =
642O =
110100010B =
Ví dụ
1*162+10*161+2*160 = 256+160+2 = 418D
6*82+4*81+2*80 = 384+32+2 = 418D
28+27+25+21 = 256+128+32+2 = 418D
Khoa KH & KT ynh, CH KHOA TP.HCM
Hệ thống số đếm và các phép tính
 Các phép tính cơ bản trong 1 hệ thống số là :
1. phép cộng (+).
2. phép trừ (-).
3. phép chia (/).
4. phép nhân (*).
5. phép dịch trái n ký số (<< n).
6. phép dịch phải n ký số (>> n).
 Ngoài ra do đặc điểm của hệ nhị phân, hệ này còn cung cấp 1 số phép tính
sau (các phép tính luận lý) :
1. phép OR bit (|).
2. phép AND bit (&).
3. phép XOR bit (^).
4. ....
Nhập môn Điện Toán -Chương 1 Slide 28
Khoa KH & KT ynh, CH KHOA TP.HCM
1 0 0 1 
0 1 0 1
1 0 0 1
0 0 0 0 
1 0 0 1
0 0 0 0
0 1 0 1 1 0 1
x
Hệ thống số đếm và các phép tính
Nhập môn Điện Toán -Chương 1 Slide 29
0 1 1 0
0 0 1 1
1 0 0 1
+
1 0 0 1 
0 0 1 1
0 1 1 0
-
1 0 1 1 10 
1 0 101
0 1 
0 0 
1 1 
1 0
0 1
-
-
-
Vd: các số sau đều ở hệ nhị phân
Khoa KH & KT ynh, CH KHOA TP.HCM
Các phép tính của đại số Boole (1)
X NOT X
0 1
1 0
Nhập môn Điện Toán -Chương 1 Slide 30
Biểu thức Boole là 1 biểu thức toán học cấu thành từ các phép toán
Boole trên các toán hạng là các biến chỉ chứa 2 trị 0 và 1.
X : biến mang giá trị {0, 1}
NOT: toán tử
X NOT X
True False
False True
Khoa KH & KT ynh, CH KHOA TP.HCM
Các phép tính của đại số Boole (2)
X Y X AND Y
0 0 0
0 1 0
1 0 0
1 1 1
Nhập môn Điện Toán -Chương 1 Slide 31
Biểu thức Boole là 1 biểu thức toán học cấu thành từ các phép toán
Boole trên các toán hạng là các biến chỉ chứa 2 trị 0 và 1.
X, Y : hai biến
AND: toán tử
X Y X AND Y
False False False
False True False
True False False
True True True
Khoa KH & KT ynh, CH KHOA TP.HCM
Các phép tính của đại số Boole (3)
X Y X AND Y X NAND Y
0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 0
Nhập môn Điện Toán -Chương 1 Slide 32
Biểu thức Boole là 1 biểu thức toán học cấu thành từ các phép toán
Boole trên các toán hạng là các biến chỉ chứa 2 trị 0 và 1.
Khoa KH & KT ynh, CH KHOA TP.HCM
Các phép tính của đại số Boole (4)
X Y X OR Y X NOR Y X XOR Y
0 0 0 1 0
0 1 1 0 1
1 0 1 0 1
1 1 1 0 0
Nhập môn Điện Toán -Chương 1 Slide 33
Biểu thức Boole là 1 biểu thức toán học cấu thành từ các phép toán
Boole trên các toán hạng là các biến chỉ chứa 2 trị 0 và 1.
Khoa KH & KT ynh, CH KHOA TP.HCM
Các phép tính của đại số Boole (5)
X Y NOT X X AND Y X NAND Y X OR Y X NOR Y X XOR Y
0 0 1 0 1 0 1 0
0 1 1 0 1 1 0 1
1 0 0 0 1 1 0 1
1 1 0 1 0 1 0 0
Nhập môn Điện Toán -Chương 1 Slide 34
Biểu thức Boole là 1 biểu thức toán học cấu thành từ các phép toán
Boole trên các toán hạng là các biến chỉ chứa 2 trị 0 và 1.
Khoa KH & KT ynh, CH KHOA TP.HCM
Biểu diễn thông tin bằng hệ nhị phân
Nhập môn Điện Toán -Chương 1 Slide 35
BIT ( BInary digiT ) : 0,1
BYTE = tổ hợp 8 bit : 01001101, 11111111
(BYTE được chọn làm đơn vị tổ chức thông tin trong máy tính)
WORD = tổ hợp 2 byte : 01011010 11100101
DWORD = tổ hợp 4 byte
1 KiloByte (KB) = 1024 bytes= 210 bytes
1 MegaByte (MB) = 1024 KB = 220 bytes
1 GigaByte (GB) = 1024 MB = 230 bytes
1 TetraByte (TB) = 1024 GB = 240 bytes
1 PetaByte (PB) = 1024 TB = 250 bytes
1 số dài n bit thì biểu diễn được 2n giá trị
Khoa KH & KT ynh, CH KHOA TP.HCM
1.4. Biểu diễn dữ liệu
Máy tính làm việc trên số nhị phân.
 Con người không thể làm việc với số nhị phân vì dài, khó
nhớ.
 Dữ liệu cần biểu diễn, xử lý, lưu trữ bằng máy tính gồm có
đại lượng số và phi số.
 Dữ liệu đưa vào máy tính phải được mã hóa thành số nhị
phân (code) rồi mới xử lý.
Nhập môn Điện Toán -Chương 1 Slide 36
Khoa KH & KT ynh, CH KHOA TP.HCM
Mã hóa thông tin đầu vào
Nhập môn Điện Toán -Chương 1 Slide 37
Thông tin
Mã hóa
Tổ hợp bit
Âm thanh Hình ảnh
Nhiệt độ
Chữ
Số
Ánh sáng
Áp suất
Độ ẩm
Điện áp
Dòng 
điện
Xử lý
Khoa KH & KT ynh, CH KHOA TP.HCM
Biểu diễn số (nguyên) n-bit
Nhập môn Điện Toán -Chương 1 Slide 38
Số n bit có giá trị : 0  (2n – 1)
Số 8 bit có giá trị : 0  255
Số 16 bit có giá trị : 0  65 535
Số 32 bit có giá trị : 0  4 294 967 295
Số không dấu
Số có dấu Qui ước: chọn bit có trọng số cao
nhất (MSB) làm bit dấu
Số 8 bit có dấu có giá trị : -128  +127
Số 16 bit có dấu có giá trị: -32768  +32767
bit dấu = 0 là số dương - bit dấu = 1 là số âm
sử dụng số bù 2 : -1 = 1111 1111, -2 = 1111 1110, . . .
-127 = 1000 0001, -128 = 1000 0000
MSB
(Most Significant Bit) LSB
(Least Significant Bit)
Khoa KH & KT ynh, CH KHOA TP.HCM
Biểu diễn số nguyên có dấu (1)
Số nguyên 16-bit có dấu:
 Phần dương: [0, 1, ..., 32767], được
miêu tả theo công thức Q.
 Phần âm: [-1, -2,..., -32768], được 
miêu tả ở dạng số bù 2 như sau :
 Số bù 1 của 1 số n bit là n bit mà
mỗi bit là ngược với bit gốc (0 → 1 
và 1 → 0)
 Số bù 2 của 1 số n bit là số bù 1 của 
số đó rồi tăng lên 1 đơn vị.
Nhập môn Điện Toán -Chương 1 Slide 39
Sự biểu diễn Giá trị
0000 0000 0000 0000
0000 0000 0000 0001
0111 1111 1111 1111
0
1
...
32767
1000 0000 0000 0000
1000 0000 0000 0001
1111 1111 1111 1111
-32768
-32767
...
-1
Khoa KH & KT ynh, CH KHOA TP.HCM
Biểu diễn số nguyên có dấu (2)
 Vì mỗi ô nhớ máy tính chỉ chứa được 1 byte, do đó ta phải dùng nhiều ô 
liên tiếp (2 hay 4) để chứa số nguyên. Có 2 cách chứa các byte của số
nguyên (hay dữ liệu khác) vào các ô nhớ : BE & LE.
 Cách BE (Big Endian) chứa byte trọng số cao nhất vào ô nhớ địa chỉ thấp 
trước, sau đó lần lượt đến các byte còn lại. 
 Cách LE (Little Endian) chứa byte trong số nhỏ nhất vào ô nhớ địa chỉ 
thấp trước, sau đó lần lượt đến các byte còn lại.
 CPU Intel & HĐH Windows sử dụng cách LE để chứa số nguyên vào bộ
nhớ (Integer và Long).
Nhập môn Điện Toán -Chương 1 Slide 40
Khoa KH & KT ynh, CH KHOA TP.HCM
Biểu diễn số nguyên có dấu (3)
 Số 15 được miêu tả dưới dạng nhị phân 16 bit như sau :
0000 0000 0000 1111
• Nếu dùng 2 byte để lưu trữ, có thể dùng dạng 16 bit viết ngắn gọn là 
000FH. Nếu lưu vào bộ nhớ dưới dạng LE (Little Endian) thì ô nhớ 
có địa chỉ thấp (i) chứa byte 0FH, và ô nhớ kế (i+1) chứa byte 00H. 
• Trường hợp dùng 4 byte: 0000000FH và lưu vào bộ nhớ dạng LE tốn 
4 ô nhớ với giá trị lần lượt từ địa chỉ thấp đến cao là 0FH, 00H, 00H, 
00H.
 Số bù 1 của 15 là 1111 1111 1111 0000, 
 Số bù 2 của 15 là 1111 1111 1111 0001
 Như vậy -15 được lưu vào máy dạng Integer là 2 byte có giá trị 
FFF1H. Nếu lưu vào ô nhớ dạng LE thì ô nhớ có địa chỉ thấp (i) 
chứa byte F1H, và ô nhớ kế (i+1) chứa byte FFH.
Nhập môn Điện Toán -Chương 1 Slide 41
Khoa KH & KT ynh, CH KHOA TP.HCM
Số thực - số chấm động
Nhập môn Điện Toán -Chương 1 Slide 42
Số chấm động (floating point) dùng để tính 
toán trên số thực.
± m B ± e
m (mantissa) quyết định độ chính xác
B (base)
e (exponent) quyết định độ lớn/nhỏ
Một giá trị có thể biểu diễn dưới nhiều dạng
913.5512
9.135512 102
91.35512 101
0.9135512 103
9135.512 10-1
91355.12 10-2
Khó xử lý
Cần chuẩn hóa
Khoa KH & KT ynh, CH KHOA TP.HCM
Số chấm động theo chuẩn IEEE 754
Nhập môn Điện Toán -Chương 1 Slide 43
Chuẩn IEEE 754 qui định
(-1)S2E-127(1.M)Có 2 dạng Chính xác đơn
Chính
xác
kép
dài 64 bit
1 11 52
S E M
dài 32 bit
Mũ thừa 1023
Cơ số 2
1 (1.M) < 2
(-1)S2E-1023(1.M)
Mũ thừa 127
Cơ số 2
1 (1.M) < 2
1 8 23
E MS
Significand
(also mantissa)
Khoa KH & KT ynh, CH KHOA TP.HCM
Ví dụ số chấm động độ chính xác đơn
Nhập môn Điện Toán -Chương 1 Slide 44
Số N = -1.5
E = 127
M = 1.1
(-1)12127-127(1.1)
Giới hạn
(-1)02-126(1.0)  2+127(2-2-23)
1.18 10-38  3.40 10+38nghĩa là
S = 1
N = 1011 1111 1100 0000 0000 0000 0000 0000
B F C 0 0 0 0 0
Khoa KH & KT ynh, CH KHOA TP.HCM
Các bảng mã dùng cho ký tự
Nhập môn Điện Toán -Chương 1 Slide 45
6 bit = 2 bit vùng + 4 bit số = 64 ký tự
Mã BCD
8 bit = 256 ký tự
Mã EBCDIC
(Binary Coded Decimal)
(Extended Binary Coded Decimal Interchange Code)
7 bit = 128 ký tự
Mã ASCII American Standard Code for Information Interchange
8 bit = 256 ký tự
Mã extended ASCII, ISO8859-1
lưu trữ 1 byte/ký tự
16 bit = 65536 ký tự
Mã Unicode
lưu trữ 2 byte/ký tự
Máy tính ngày nay
Yếu tố
chữ viết
các dân
tộc
(Tiếng Việt trên máy tính chưa thống nhất)
Khoa KH & KT ynh, CH KHOA TP.HCM
 được dùng để tính toán trên số thập phân trong hệ nhị phân.
 được viết theo hệ 16 nhưng giá trị tính theo hệ 10.
 Số 12BCD được viết trong hệ 2 là 0001 0010 nhưng có giá trị là 12 thay vì
18 (1216 = 1810).
Số BCD (Binary Coded Decimal)
Nhập môn Điện Toán -Chương 1 Slide 47
không chỉnh
kết quả đúng
18
01
+
19
Chỉnh dạng số BCD sau khi cộng
Khoa KH & KT ynh, CH KHOA TP.HCM
 được dùng để tính toán trên số thập phân trong hệ nhị phân.
 được viết theo hệ 16 nhưng giá trị tính theo hệ 10.
 Số 12BCD được viết trong hệ 2 là 0001 0010 nhưng có giá trị là 12 thay vì
18 (1216 = 1810).
Số BCD (Binary Coded Decimal)
Nhập môn Điện Toán -Chương 1 Slide 48
chỉnh dạng
kết quả không đúng
+
18
02
+
1A
6
20
18
09
+
21
6
+
27
Chỉnh dạng vì A không
phải là số BCD
Chỉnh dạng vì có
nhớ ở hàng đơn vị
Chỉnh dạng số BCD sau khi cộng
Khoa KH & KT ynh, CH KHOA TP.HCM
Mã ASCII 
Nhập môn Điện Toán -Chương 1 Slide 49
Khoa KH & KT ynh, CH KHOA TP.HCM
Mã ISO8859-1
Nhập môn Điện Toán -Chương 1 Slide 50
Khoa KH & KT ynh, CH KHOA TP.HCM
Lưu trữ bằng mã ASCII
Nhập môn Điện Toán -Chương 1 Slide 52
8 ký tự
8 byte
Khoa KH & KT ynh, CH KHOA TP.HCM
1.5. Luận lý máy tính
• Luận lý máy tính dựa trên nền tảng một nhánh của
luận lý toán học được gọi là đại số Boole (George 
Boole).
• Biến luận lý (boolean variable) có hai giá trị, 
thường được biểu diễn bằng 1 và 0 (bit).
• Về mặt hiện thực, biến luận lý thể hiện trạng thái
điện áp trên giây dẫn tín hiệu (1 = 5V; 0 = 0V).
Nhập môn Điện Toán -Chương 1 Slide 53
Khoa KH & KT ynh, CH KHOA TP.HCM
Các phép toán trên đại số Boole
Nhập môn Điện Toán -Chương 1 Slide 54
Not
And
Nand
Or
XorNor
Phép
luận lý
Ex-Nor
(Not And)
(Not Or)
(Not Xor)
(Ex-Or)
Khoa KH & KT ynh, CH KHOA TP.HCM
Phép Not
Nhập môn Điện Toán -Chương 1 Slide 55
Ký hiệu dấu gạch
ngang trên đầu
x = 1011 x = 0100
 x = 1011 = x
x x
0 1
1 0
Bảng sự thật
Khoa KH & KT ynh, CH KHOA TP.HCM
x y x . y
0 0 0
0 1 0
1 0 0
1 1 1
Phép And
Nhập môn Điện Toán -Chương 1 Slide 56
Ký hiệu dấu chấm
như phép nhân
y . 0 = 0
y . 1 = y
Nhận xét
Bảng sự thật
Khoa KH & KT ynh, CH KHOA TP.HCM
x y x + y
0 0 0
0 1 1
1 0 1
1 1 1
Phép Or
Nhập môn Điện Toán -Chương 1 Slide 57
Ký hiệu dấu cộng
như phép cộng
y + 0 = y
y + 1 = 1
Nhận xét
Bảng sự thật
Khoa KH & KT ynh, CH KHOA TP.HCM
Ví dụ phép luận lý
Nhập môn Điện Toán -Chương 1 Slide 58
x . yx . yyx
0000011
1011001
1100110
0001100
f(x,y)yx
Tính hàm f(x,y) = x . y + x . y
Khoa KH & KT ynh, CH KHOA TP.HCM
x y x  y
0 0 0
0 1 1
1 0 1
1 1 0
Phép Xor (Ex-Or)
Nhập môn Điện Toán -Chương 1 Slide 59
Ký hiệu dấu cộng trong vòng tròn
như phép modulo
y  0 = y
y  1 = y
Nhận xét
Bảng sự thật
Khoa KH & KT ynh, CH KHOA TP.HCM
Bảng tóm tắt
Nhập môn Điện Toán -Chương 1 Slide 60
NOT AND OR XOR
x y not y x and y x or y x xor y
0 0 1 0 0 0
0 1 0 0 1 1
1 0 1 0 1 1
1 1 0 1 1 0
y and 0 = 0
y and 1 = y
y or 0 = y
y or 1 = 1
y xor 0 = y
y xor 1 = not y
Bảng sự thật
Khoa KH & KT ynh, CH KHOA TP.HCM
Cổng luận lý
Nhập môn Điện Toán -Chương 1 Slide 61
NOT
AND
OR
XOR
BUFFER
NAND
NOR
EX-NOR
Khoa KH & KT ynh, CH KHOA TP.HCM
Chức năng đóng mở
Nhập môn Điện Toán -Chương 1 Slide 62
VCC
R1
S1
mức luận lý 1 = 5V
mức luận lý 0 = 0V
y and 1 = y
mức 1
mức 0
0 = đóng
Cổng AND
10
1 = mở
0
y and 0 = 0
Khoa KH & KT ynh, CH KHOA TP.HCM
Chức năng đóng mở (tt.)
Nhập môn Điện Toán -Chương 1 Slide 63
VCC
R1
S1
mức luận lý 1 = 5V
mức luận lý 0 = 0V
y or 1 = 1
mức 1
mức 0
0 = mở
Cổng OR
10
1 = đóng
y or 0 = y
1
Khoa KH & KT ynh, CH KHOA TP.HCM
Ứng dụng đơn giản của cổng luận lý
• Mạch cộng bán phần thực hiện phép cộng trên hai 
bit, cho ra kết quả là bit tổng S và bit nhớ C.
• Mạch cộng toàn phần cũng tương tự mạch cộng 
bán phần nhưng đầu vào có cộng thêm bit nhớ C0.
• Mạch cộng toàn phần có thể được thiết kế dựa vào 
mạch cộng bán phần.
Nhập môn Điện Toán -Chương 1 Slide 64
Khoa KH & KT ynh, CH KHOA TP.HCM
Mạch cộng bán phần
Nhập môn Điện Toán -Chương 1 Slide 65
Mạch
cộngy
S
C
x
x
y
S
C
x y S C
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
ANDXOR
AND
XOR
Khoa KH & KT ynh, CH KHOA TP.HCM
Mạch cộng toàn phần
Nhập môn Điện Toán -Chương 1 Slide 66
Mạch 
cộng 
toàn 
phầny
S
C
x
C0
S = x + y + C0
S = (x + y) + C0
Tính: S1 = x + y
Tính: S2 = S1 + C0
Cần bộ cộng
bán phần 1
Cần bộ cộng
bán phần 2
Khoa KH & KT ynh, CH KHOA TP.HCM
Mạch cộng toàn phần (tt.)
Nhập môn Điện Toán -Chương 1 Slide 67
Bán 
phần
S
Bán 
phầny
S1
x
C1
C2
Cổng 
gì?
C
C0
Nhớ (C = 1) 
trong trường
hợp nào ?
Khoa KH & KT ynh, CH KHOA TP.HCM
Mạch cộng toàn phần (tt.)
Nhập môn Điện Toán -Chương 1 Slide 68
C0 x y S C C0 S1 C1 C2 C
0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 1 0 0 0
0 1 0 1 0 0 1 0 0 0
0 1 1 0 1 0 0 1 0 1
1 0 0 1 0 1 0 0 0 0
1 0 1 0 1 1 1 0 1 1
1 1 0 0 1 1 1 0 1 1
1 1 1 1 1 1 0 1 0 1
C = 1 khi C1 = 1 hoặc C2 = 1
Khoa KH & KT ynh, CH KHOA TP.HCM Nhập môn Điện Toán -Chương 1 Slide 69
C0
x
y
S1
S
C1
C2
C
Mạch
cộng
bán
phầnMạch
cộng
bán
phần
Khoa KH & KT ynh, CH KHOA TP.HCM
Mạch cộng nhiều bit
Nhập môn Điện Toán -Chương 1 Slide 70
y0
S0
x0
0
S1
S2
S3
C
x1
x2
x3
y1
y2
y3
Cộng 0
Cộng 1
Cộng 2
Cộng 3
x3x2x1x0
S4 S3S2S1S0
y3y2y1y0
+