Bài giảng kĩ thuật số ứng dụng

TRѬӠNG ĈҤI HӐC BÁCH KHOA ĈÀ NҸNG

KHOA Ĉ,ӊN TӰ VIӈN THÔNG

----- oOo -----

BÀI GIҦNG

.Ӻ THUҰT SӔӬNG DӨNG

Ĉà Nҹng, 08 / 2006

Chѭѫng 1. Ĉҥi sӕ Boole Trang 1

Chѭѫng 1

ĈҤI SӔ BOOLE

1.1. HӊĈӂM NHӎ PHÂN VÀ MÃ

1.1.1. HӋ thӕng sӕÿӃm

1. Khái niӋm và phân loҥi hӋÿӃ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ӕ

Oѭӧng xác ÿӏnh gӑi là các chӳ sӕ.

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ӕ

Oѭӧ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

Yӏ 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ӕ

Oѭӧ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Ӈ.

Các hӋÿӃm không theo vӏ trí sӁ không ÿѭӧc ÿӅ cұp ÿӃn trong giáo trình này.

2. Cѫ sӕ cӫa hӋÿӃm

0ӝt sӕ A bҩt kǤ có thӇ biӇu diӉn bҵng dãy sau:

A= am-1am-2.....a0a-1......a-n

Trong ÿó ai là các chӳ sӕ, (i = - n ¸ m -1); i là các hàng sӕ, i nhӓ: hàng trҿ, i lӟn: hàng già.

Giá trӏ sӕ lѭӧng cӫa các chӳ sӕ ai sӁ nhұn mӝt giá trӏ nào ÿó sao cho thӓa mãn bҩt ÿҷng thӭc sau:

0 a N 1 £ i £ - (ai 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ӱ

Gө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ӕ.

Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 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

KӋ 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 fi ai = 0, 1.

- HӋ thұp phân : N =10 fi ai = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

- HӋ bát phân : N =8 fi ai = 0, 1, 2, 3, 4, 5, 6, 7.

- HӋ thұp lөc phân : N =16 fi ai = 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(N) = am-1.Nm-1 + am-2.Nm-2 +...+ a0.N0

+ a-1.N-1 + ... + a-n.N-n

Hay:

Â

-

=-

=

m 1

i n

i

(N) i

A a N (1.1)

9ͣi N=10 (h͏ th̵p phân):

A(10) = am-1.10m-1 + am-2.10m-2 +....+ a0.100

+...+ a-n.10-n

1999,959(10) =1.103

+ 9.102

+ 9.101

+ 9.100

+ 9.10-1 + 5.10-2 + 9.10-3

9ͣi N=2 (h͏ nh͓ phân):

A(2) = am-1.2m-1 + am-2.2m-2 +...+ a0.20

....+a-n2

-n

1101(2) = 1.23

+1.22

+ 0.21

+ 1.20

= 13(10)

9ͣi N=16 (h͏ th̵p lͭc phân):

A(16) = am-1.16m-1 + am-2.16m-2 +...+ a0.160

+ a-116-1 + ... + a-n16-n

3FF(16) = 3.162

+ 15.161

+ 15.160

= 1023(10)

9ͣi N=8 (h͏ bát phân):

A(8) = am-1.8m-1 + am-2.8m-2 +...+ a0.80

+ a-1.8-1 + ... + a-n.8-n

376(8) = 3.82

+ 7.81

+ 6.80

= 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).

3. Ĉәi cѫ sӕ

a. Ĉ͝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ѫ

Vӕ d dѭӟi dҥng ÿa thӭc theo cѫ sӕ cӫa nó (theo biӇu thӭc 1.1).

Ví dͭ 1.1 Ĉәi sӕ 1101(2)ӣ hӋ nhӏ phân sang hӋ thұp phân nhѭ sau:

1011(2) = 1.23

+ 0.22

+ 1.21

+ 1.20

= 11(10)

b. Ĉ͝i tͳ c˯ s͙ 10 sang c˯ s͙ d

ĈӇ chuyӇn ÿәi mӝt sӕ tӯ cѫ sӕ 10 sang cѫ sӕ d (d = 2, 8, 16) ngѭӡi ta lҩy con sӕ trong cѫ sӕ 10

chia liên tiӃp cho d ÿӃn khi thѭѫng sӕ bҵng không thì dӯng lҥi. KӃt quҧ chuyӇn ÿәi có ÿѭӧc trong

KӋÿӃm cѫ sӕ d là tұp hӧp các sӕ dѭ cӫa phép chia ÿѭӧc viӃt theo thӭ tӵ ngѭӧc lҥi, nghƭa là sӕ dѭ

ÿҫu tiên có trӑng sӕ nhӓ nhҩt. (xem ví dө 1.2)

Chѭѫng 1. Ĉҥi sӕ Boole Trang 3

Ví dͭ 1.2:

.Ӄt luұn: Gӑi d1, d2, ..,dn lҫn lѭӧt là dѭ sӕ cӫa phép chia sӕ thұp phân cho cѫ sӕ d ӣ lҫn thӭ 1, 2,

3, 4, .., n thì kӃt quҧ chuyӇn ÿәi mӝt sӕ tӯ hӋÿӃm cѫ sӕ 10 (thұp phân) sang hӋÿӃm cѫ sӕ d sӁ là:

dndn-1dn-2...d1,

nghƭa là dѭ sӕ sau cùng cӫa phép chia là bít có trӑng sӕ cao nhҩt (MSB), còn dѭ sӕÿҫu tiên là bít

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 cNJng có thӇ ký

Wӵ 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.1.2. 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

ÿLӋ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), ...

Xét sӕ nhӏ phân 4 bít: a3a2a1a0. BiӇu diӉn dѭӟi dҥng ÿa thӭc theo cѫ sӕ cӫa nó là:

a3a2a1a0 (2) = a3.23

+ a2.22

+ a1.21

+ a0.20

Trong ÿó:

- 23

, 22

, 21

, 20

(hay 8, 4, 2, 1) ÿѭӧc gӑi là các trӑng sӕ.

- a0 ÿѭӧ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.

- a3 ÿѭӧc gӑi là bit có trӑng sӕ lӟn nhҩt, hay còn gӑi là bít có ý nghƭa lӟn nhҩt (MSB - Most

Significant Bit), còn gӑi là bít già 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

1 2

1 0

A(10)=13 Æ A(2)=1101

Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006 Trang 4

Nhѭ vұy, vӟi sӕ nhӏ phân 4 bit a3a2a1a0 trong ÿó mӛi chӳ sӕ ai (i tӯ 0 ÿӃn 3) chӍ nhұn ÿѭӧc hai

giá trӏ {0,1} ta có 2

4

= 16 tә hӧp nhӏ phân phân biӋt.

%ҧ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.

6ӕ thұp phân a3a2a1a0 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

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

00

01

02

03

04

05

06

07

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

6ӵ 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 23

= 8 và 24

= 16, tӯ bҧng mã trên có thӇ nhұn thҩy mӛi chӳ sӕ trong hӋ bát phân

Wѭѫ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

Wѭѫ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

Oөc phân hoһc bát phân.

Ví dͭ 1.3: Xét viӋc biӇu diӉn sӕ nhӏ phân 1011111011111110(2).

1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0

9ұy, có thӇ biӇu diӉn : 137376(8) theo hӋ bát phân

hoһc : BEFE(H) theo hӋ thұp lөc phân.

& Vͣi s͙ nh͓ phân n bít có bao nhiêu t͝ hͫp nh͓ phân khác nhau? Xét tr˱ͥng hͫp s͙ nh͓

phân 8 bít (n=8) a7a6a5a4a3a2a1a0 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

1 3 7 3 7 6

B E F E

Chѭѫng 1. Ĉҥi sӕ Boole Trang 5

ĈӇ 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.22

+ 1.20

= 5(10)

b. Phép trͳ

0 - 0 = 0 mѭӧn 0

0 - 1 = 1 mѭӧn 1

1 - 0 = 1 mѭӧn 0

1 - 1 = 0 mѭӧn 0

Ví dͭ 1.5:

7 Æ 0111

5 Æ 0101

2 Æ 0010 = 0.23

+ 0.22

+ 1.21

+ 0.20

= 2(10)

c. Phép nhân

0 . 0 = 0

0 . 1 = 0

1 . 0 = 0

1 . 1 = 1

Ví dͭ 1.6:

7 Æ 0111

5 Æ 0101

35 0111

0000

0111

0000

0100011 = 1.25

+ 1.21

+ 1.20

= 35(10)

d. Phép chia

0 : 1 = 0

1 : 1 = 1

/˱u ý: Khi chia s͙ chia ph̫i khác 0

Ví dͭ 1.7: 10 5 Æ 1010 101

2 101 10(2) = 2(10)

00

0

+ +

- -

x x