TRNG I HC BÁCH KHOA À NNG
KHOA N T VIN THÔNG
oOo
BÀI GING
N T S 1
à Nng, 08 / 2007
Chng 1. H thng sm và khái nim v mã Trang 1
Chng 1
 THNG SM VÀ KHÁI NIM V MÃ
1.1. H THNG SM
1.1.1. Hm
1. Khái nim
m là tp hp các phng pháp gi và biu din các con s bng các kí hiu có giá tr s
ng xác nh gi là các ch s.
2. Phân loi
Có th chia các hm làm hai loi: hm theo v trí và hm không theo v trí.
a. Hm theo v trí:
m theo v trí là hm mà trong ó giá tr s lng ca ch s còn ph thuc vào v trí ca
nó ng trong con s c th.
Ví d: H thp phân là mt hm theo v trí. S 1991 trong h thp phân c biu din bng
2 ch s “1” và “9”, nhng do v trí ng ca các ch s này trong con s là khác nhau nên s mang
các giá tr s lng khác nhau, chng hn ch s “1”  v trí hàng n v biu din cho giá tr s
ng là 1 song ch s “1”  v trí hàng nghìn li biu din cho giá tr s lng là 1000, hay ch s
“9” khi  hàng chc biu din giá tr là 90 còn khi  hàng trm li biu din cho giá tr là 900.
b. Hm không theo v trí:
m không theo v trí là hm mà trong ó giá tr s lng ca ch s không ph thuc vào
 trí ca nó ng trong con s.
m La Mã là mt hm không theo v trí. Hm này s dng các ký t “I”, “V”, “X”
 biu din các con s, trong ó “I” biu din cho giá tr s lng 1, “V” biu din cho giá tr s
ng 5, “X” biu din cho giá tr s lng 10 mà không ph thuc vào v trí các ch s này ng
trong con s c th.

−≤≤
(a
i
nguyên)
N c gi là c s ca hm.  s ca mt hm là s lng ký t phân bit c s
ng trong mt hm. Các h thng sm c phân bit vi nhau bng mt c s N ca h
m ó. Mi ký t biu din mt ch s.
Bài ging K THUT S Trang 2
Trong i sng hng ngày chúng ta quen s dng hm thp phân (decimal) vi N=10. Trong
 thng s còn s dng nhng hm khác là hm nh phân (binary) vi N=2, hm bát phân
(octal) vi N=8 và hm thp lc phân (hexadecimal) vi N=16.
- H nh phân : N =2 ⇒ a
i
= 0, 1.
- H thp phân : N =10 ⇒ a
i
= 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
- H bát phân : N =8
⇒
a
i
= 0, 1, 2, 3, 4, 5, 6, 7.
- H thp lc phân : N =16 ⇒ a
i
= 0, 1, 2, …8, 9, A, B, C,D, E, F.
Khi ã xut hin c s N, ta có th biu din s A di dng mt a thc theo c s N, c ký
hiu là A
(N)
:
A

NaA
(1.1)
i N=10 (h thp phân):
A
(10)
= a
m-1
.10
m-1
+ a
m-2
.10
m-2
+ + a
0
.10
0
+ + a
-n
.10
-n
1999,959
(10)
=1.10
3
+ 9.10
2
+ 9.10
1
+ 9.10

+1.2
2
+ 0.2
1
+ 1.2
0
= 13
(10)
i N=16 (h thp lc phân):
A
(16)
= a
m-1
.16
m-1
+ a
m-2
.16
m-2
+ + a
0
.16
0
+ a
-1
16
-1
+ + a
-n
16

+ + a
-n
.8
-n
376
(8)
= 3.8
2
+ 7.8
1
+ 6.8
0
= 254
(10)
Nh vy, biu thc (1.1) cho phép i các s bt k h nào sang h thp phân (h 10).
1.1.3. i c s
1. i t c s d sang c s 10
 chuyn i mt s hm c s d sang hm c s 10 ngi ta khai trin con s trong c
 d di dng a thc theo c s ca nó (theo biu thc 1.3).
Ví d 1.1
i s 1101
(2)
 h nh phân sang h thp phân nh sau:
1011
(2)
= 1.2
3
+ 0.2
2
+ 1.2

có trng s nh nht (LSB).
Trong các ví d trên, c s ca hm c ghi  dng ch s bên di. Ngoài ra cng có th ký
 ch phân bit nh sau:
B - H nh phân (Binary) O - H bát phân (Octal)
D - H thp phân (Decmal) H - H thp lc phân (Hexadecimal)
Ví d: 1010B có ngha là 1010
(2)
37FH có ngha là 37F
(16)
& Quy tc chuyn i gia các hm c s 2, 8, 16 ?
1.2. HM NH PHÂN VÀ KHÁI NIM V MÃ
1.2.1. Hm nh phân
1. Khái nim
m nh phân, còn gi là hm c s 2, là hm trong ó ngi ta ch s dng hai kí hiu
0 và 1  biu din tt c các s. Hai ký hiu ó gi chung là bit hoc digit, nó c trng cho mch
n t có hai trng thái n nh hay còn gi là 2 trng thái bn ca FLIP- FLOP (ký hiu là FF).
Trong hm nh phân ngi ta quy c nh sau:
- Mt nhóm 4 bít gi là 1 nibble.
- Mt nhóm 8 bít gi là 1 byte.
- Nhóm nhiu bytes gi là t (word), có th có t 2 bytes (16 bít), t 4 bytes (32 bít),
 hiu rõ hn mt s khái nim, ta xét s nh phân 4 bít: a
3
a
2
a
1
a
0
. Biu din di dng a thc
theo c s ca nó là:

1
, 2
0
(hay 8, 4, 2, 1) c gi là các trng s.
- a
0
 c gi là bit có trng s nh nht, hay còn gi bit có ý ngha nh nht (LSB - Least
Significant Bit), còn gi là bít tr nht.
1023 16
63 16
3 16
0
15
15
3
A
(10)
=1023
→
A
(16)
=3FFH
13
2
6 2
3
2
1
1
0

ng sau ây lit kê các t hp mã nh phân 4 bít cùng các giá tr s thp phân, s bát phân và s
thp lc phân tng ng.
& T bng này hãy cho bit mi quan h gia các s trong h nh phân vi các s trong h
bát phân (N=8) và h thp lc phân (N=16)? Tó suy ra phng pháp chuyn i nhanh gia các
 này?
 thp phân a
3
a
2
a
1
a
0
S bát phân S thp lc phân
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

16
17
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
ng 1.1. Các t hp mã nh phân 4 bít
 chuyn i gia các h thng s m khác nhau gi vai trò quan trng trong máy tính s.
Chúng ta bit rng 2
3
= 8 và 2
4
= 16, t bng mã trên có th nhn thy mi ch s trong h bát phân
ng ng vi mt nhóm ba ch s (3 bít) trong h nh phân, mi ch s trong h thp lc phân
ng ng vi mt nhóm bn ch s (4 bít) trong h nh phân. Do ó, khi biu din s nh phân
nhiu bit trên máy tính  tránh sai sót ngi ta thng biu din thông qua s thp phân hoc thp
c phân hoc bát phân.
Ví d 1.3

a
1
a
0
có bao nhiêu t hp nh phân (t mã nh phân) khác nhau?
2. Các phép tính trên s nh phân
a. Phép cng
 cng hai s nh phân, ngi ta da trên qui tc cng nh sau:
0 + 0 = 0 nh 0
0 + 1 = 1 nh 0
1 + 0 = 1 nh 0
1 + 1 = 0 nh 1
Ví d 1.4
:
3
→
0011
2
→
0010
5
→
0101 = 1.2
2
+ 1.2
0
= 5
(10)
b. Phép tr
0 - 0 = 0 mn 0

7
→
0111
5
→
0101
35 0111
0000
0111
0000
0100011 = 1.2
5
+ 1.2
1
+ 1.2
0
= 35
(10)
d. Phép chia
0 : 1 = 0
1 : 1 = 1
u ý: Khi chia s chia phi khác 0
+
+
-
-
x
x
Bài ging K THUT S Trang 6
Ví d 1.7: 10 5

cách s dng các t mã nh phân. Vic mã hóa ký t, tp lnh, ting nói, hình nh u da trên c
 mã hóa s thp phân.
0 0 0 0 0 1 011 0
0 0 0 0 0 0 111
Thanh ghi ban u
Thanh ghi sau khi dch trái 1 bít
ch trái 1 bít
↔
nhân 2
0 0 0 0 0 0 10 1 1
0
Thanh ghi sau khi dch phi 1 bít
ch phi 1 bít
↔
chia 20

Hình 1.1. ng dng thanh ghi dch thc hin phép toán nhân và chia 2
Chng 1. H thng sm và khái nim v mã Trang 7
2. Mã hóa s thp phân
a. Khái nim
Trong thc t mã hóa s thp phân ngi ta s dng các s nh phân 4 bit (a
3
a
2
a
1
a
0
) theo quy
c sau:

c trng ca mã BCD s hc là có tính cht i xng qua mt ng trung gian. Do
y,  tìm t mã BCD ca mt s thp phân nào ó ta ly bù (o) t mã BCD ca s bù 9
ng ng.
Ví d xét mã BCD 2421. ây là mã BCD s hc (tng các trng s bng 9), trong ó s 3
(thp phân) có t mã là 0011, s 6 (thp phân) là bù 9 ca 3. Do vy, có th suy ra t mã ca 6
ng cách ly bù t mã ca 3, ngha là ly bù 0011, ta s có t mã ca 6 là 1100.
b2. Mã BCD không có trng s là loi mã không cho phép phân tích thành a thc theo trng
 ca nó. Các mã BCD không có trng s là: Mã Gray, Mã Gray tha 3.
c trng ca mã Gray là b mã trong ó hai t mã nh phân ng k tip nhau bao gi cng ch
khác nhau 1 bit.
Ví d:
Các bng di ây trình bày mt s loi mã thông dng.
Mã Gray: 2
→
0011
3
→
0010
4
→
0110
Còn vi mã BCD 8421:
3
→
0011
4
→
0100
Bài ging K THUT S Trang 8
ng 1.2: Các mã BCD t nhiên.

0 0 1 1 0 0 1 1 0 1 1 0 3
0 1 0 0 0 1 0 0 0 1 1 1 4
0 1 0 1 1 0 0 0 1 0 0 0 5
0 1 1 0 1 0 0 1 1 0 0 1 6
0 1 1 1 1 0 1 0 1 0 1 0 7
1 0 0 0 1 0 1 1 1 0 1 1 8
1 0 0 1 1 1 0 0 1 1 0 0 9
ng 1.3: Các mã BCD s hc
BCD 2421 BCD 5121 BCD 84-2-1
a
3
a
2
a
1
a
0
b
3
b
2
b
1
b
0
c
3
c
2
c

c
1
c
0
G
3
G
2
G
1
G
0
g
3
g
2
g
1
g
0
 thp
phân
0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0
0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 1
0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 2
0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 3
0 1 0 0 0 1 1 1 0 1 1 0 0 1 0 0 4
0 1 0 1 1 0 0 0 0 1 1 1 1 1 0 0 5
0 1 1 0 1 0 0 1 0 1 0 1 1 1 0 1 6
0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 1 7

0
không phi s BCD 8421
- Nu y = 0 thì a
3
a
2
a
1
a
0
là s BCD 8421
Nh vy, nu mt s nh phân 4 bit không phi là mt s BCD 8421 thì ngõ ra y = 1. T bng
1.1 ta thy mt s nh phân 4 bít không phi là s BCD 8421 khi bít a
3
luôn luôn bng 1 và (bit a
1
ng 1 hoc bít a
2
bng 1).
Suy ra phng trình logic ca ngõ ra y: y = a
3
(a
1
+ a
2
) = a
3
a
1
+ a

0110
0001 0010
ch nhn dng
 BCD 8421
y
a
3
a
2
a
1
a
1
a
2
a
3
y
a
1
a
2
a
3
y
 hiu chnh
+ + + +
+
Bài ging K THUT S Trang 10
Có hai trng hp phi hiu chnh kt qu ca phép cng 2 s BCD 8421:

0111 0111
5
→
0101 1010
2 0010 1 0001
1
0010
u ý:
- Bù 1 ca mt s nh phân là ly o tt c các bít ca só (bit 0 thành 1, bit 1 thành 0).
- Bù 2 ca mt s nh phân bng s bù 1 cng thêm 1 vào bít LSB.
Xét các trng hp m rng sau ây:
1. Thc hin tr 2 s BCD 1 các mà s b tr nh hn s tr ?
2. M rng cho cng và tr 2 s BCD nhiu các ?
 hiu chnh (6)
+ +
t qu là s BCD 8421 nh
ng
i xut hin s nh bng 1
t qu sau khi hiu chnh là 17
Bù 1 ca 5
- -
+
+
ng 1 LSB  có bù 2 ca 5
i s nh
t qu cui cùng
Chng 2. i s BOOLE Trang 11
Chng 2
I S BOOLE
2.1. CÁC TIÊN  VÀ NH LÝ I S BOOLE

x
, sao cho luôn tha mãn:
x +
x
= 1 và x.
x
= 0
Bài ging N T S 1 Trang 12
u B = B* = {0,1} (B* ch gm 2 phn t 0 và 1) và tha mãn 5 tiên  trên thì cng lp thành
u trúc i s Boole nhng là cu trúc i s Boole nh nht.
2.1.2. Các nh lý c bn ca i s Boole
1. Vn i ngu trong i s Boole
Hai mnh  (hai biu thc, hai nh lý) c gi là i ngu vi nhau nu trong mnh  này
ngi ta thay phép toán cng thành phép toán nhân và ngc li, thay 0 bng 1 và ngc li, thì s
suy ra c mnh  kia.
Khi hai mnh i ngu vi nhau, nu 1 trong 2 mnh c chng minh là úng thì mnh
 còn li là úng. Di ây là ví d v các cp mnh i ngu vi nhau.
Ví d 2.1
: x.(y+z) = (x.y) + (x.z)
x + (y.z) = (x+y).(x+z)
Ví d 2.2
: x +
x
= 1
x.
x
= 0
2. Các nh lý
a. nh lí 1 (nh lý v phn t bù là duy nht)
∀x, y ∈ B, ta có:

x. y. z = x.y.z = zyx ++
e. nh lí 5 (nh lý dán)
∀x, y ∈ B, ta có:
x. (
x
+ y) = x.y
x + (
x
.y) = x + y
Hai m
nh  này là i ngu
Hai m
nh  này là i ngu