KODOWANIE LICZB

background image

Architektura Komputera – Kodowanie Liczb

1

KODOWANIE LICZB

WSTĘP

Współczesne komputery przetwarzają informację w postaci bitów, czyli symboli o dwóch podstawowych postaciach, które oznaczamy
zwykle cyframi 0 i 1 (stąd pochodzi nazwa systemów zerojedynkowych). Nazwę

bit

wymyślił w czasie drugiego śniadania John Turkey w

roku 1947. Słowo to pochodzi od liter angielskich wyrażeń

bi

nary (dwójkowy) oraz digi

t

(cyfra), oznacza więc cyfrę dwójkową. John

rozważał jeszcze dwie inne nazwy -

binit

oraz

bigit

, lecz, jak już wiemy, nie przyjęły się one i mamy obecnie bit.

Bity są bardzo wygodne. Poniżej zebraliśmy kilka najważniejszych powodów ich popularności

:

bit

ma tylko dwa stany,

0

i

1

, dzięki czemu w prosty sposób można konstruować układy elektroniczne, które

przetwarzają bity.

łącząc bity w grupy można otrzymywać dowolną liczbę symboli złożonych, w których jednak wciąż występują
podstawowe elementy o prostej postaci - bity. Ta własność umożliwia kodowanie dowolnie skomplikowanych
informacji w postaci ciągu bitów.

dwójkowy system zapisu liczb może być bezpośrednio przeniesiony na bity, co
umożliwia kodowanie dowolnych liczb - dzięki temu komputery mogą wykonywać
najbardziej skomplikowane obliczenia.

operacje arytmetyczne w systemie dwójkowym są bardzo proste, więc również
stosunkowo proste są układy liczące zrealizowane na bazie tego systemu

dla bitów można zastosować bezpośrednio reguły algebry Boole'a, co umożliwia
przeprowadzanie dowolnych operacji logicznych.

w trakcie transmisji bitów, są one bardzo odporne na zakłócenia, więc system ten
sprzyja tworzeniu sieci komputerowych.

Pierwszy na świecie

mikroprocesor Intel 4004

background image

Architektura Komputera – Kodowanie Liczb

2

JEDNOSTKI INFORMACJI

Podstawową jednostką informacji jest

bit

. To fakt ogólnie znany, jednak trudniej odpowiedzieć na pytanie, co właściwie oznacza to

stwierdzenie. W jaki sposób bity można powiązać z informacją.

Informacja jest tworem czysto abstrakcyjnym. Nie istnieje materialnie. Nie można jej dotknąć, poczuć, zobaczyć. Informację da się
natomiast wyrażać za pomocą symboli, znaków, kodu. Człowiek najczęściej używa słów, pisma, gestów do przekazywania informacji. Ta
sama informacja (idea) może przybierać formę symboli, które, chociaż różne, oznaczają to samo pojęcie. Np. człowiek, human (ang.),
Mensch (niem.), el hombre (hisz.), il uomo (wł.) - w każdym języku symbol (słowo) jest inne, lecz ich wspólną cechę stanowi to samo
znaczenie, czyli właśnie informacja. Skoro do wyrażania informacji możemy używać różnych symboli (słów), to dlaczego nie zastosować
do tego celu bitów? Należy tylko pokazać sposób, jak to zrobić. I tym właśnie się zajmiemy.

Bit

Bit

jest symbolem, który może przyjmować dwie różne postacie. Jeśli chcemy zapisać go na papierze, to

stosujemy symbole pomocnicze

0

i

1

. Technicznie bit realizowany jest za pomocą dwóch różnych sygnałów.

W technice cyfrowej określa się poziomy napięć, które odpowiadają bezpośrednio dwóm postaciom bitu:

0,4 ... 0,8 V - stan

0

(oznaczany również

L - Low

- Niski)

2,0 ... 2,4 V - stan

1

(oznaczany również

H - High

- Wysoki)

Taśma dziurkowana.

Tak kiedyś zapisywano dane.

Każda dziurka odpowiadała

bitowi o stanie 1. Brak dziurki

oznaczał stan 0.

background image

Architektura Komputera – Kodowanie Liczb

3

Układy elektroniczne komputera reagują na te napięcia i w ten sposób przetwarzają bity. Zamiast napięć mogą to być również prądy o
różnych natężeniach lub zwrotach, sygnały o dwóch rozróżnialnych częstotliwościach oraz wiele innych ciekawych sposobów, których
opisanie zajęłoby nam co najmniej kilka lat ciężkiej pracy. Poprzestańmy więc na stwierdzeniu, iż bit to sygnał dwustanowy - jeden stan
oznaczamy jako 0, a drugi jako 1.

Każdy ze stanów bitu może przenosić jedną wiadomość w identyczny sposób, jak np. słówko "stół" przenosi wiadomość na temat rzeczy
z płaskim blatem i zwykle czterema nogami. Tyle tylko, iż słowa naszego języka mają ustalone od stuleci znaczenia, bity natomiast
możemy przystosowywać do dowolnych wiadomości w miarę potrzeb. Jeden bit pozwoli w ten sposób przekazać jedną z dwóch
wiadomości.

Czujnik ruchu.

W razie wykrycia ruchu

w okolicy przekazuje bit

o stanie 1.

background image

Architektura Komputera – Kodowanie Liczb

4

Przykład

Pojedyncze bity używane są do komunikacji z prostymi czujnikami, które reagują na określoną sytuację - np. gaz w chronionym
pomieszczeniu, wzrost temperatury ponad wartość dopuszczalną, osiągnięcie przez ciecz w naczyniu określonego poziomu, otwarcie
drzwi, przerwanie wiązki światła, itp.

Bit informacyjny z czujnika przekazywany jest do centrali na różne sposoby - przewodem elektrycznym, linią światłowodową, torem
radiowym, itp. Ważne jest tylko to, iż w każdym z tych kanałów transmisyjnych wolno pojawić się tylko jednemu z dwóch stanów bitu -
stanowi 0 (np. niskie napięcie, brak prądu, sygnał radiowy o małej amplitudzie itp.) lub stanowi 1 (np. wysokie napięcie, prąd w
przewodzie, sygnał radiowy o dużej amplitudzie itp.).

Jeśli wiemy jak reaguje dany czujnik na określone zdarzenie (co oznaczają stany 0 i 1 przekazywane przez ten czujnik), to w prosty
sposób możemy zinterpretować przekazywaną przezeń informację. Np. otrzymujemy sygnał o stanie 0 i wiemy, że oznacza on, iż czujnik
nic nie wykrył. Jeśli teraz otrzymamy sygnał o stanie 1, oznaczający wystąpienie sytuacji, na którą reaguje dany czujnik, to od razu
możemy to odpowiednio zinterpretować - np. wysłać ekipę strażacką do chronionego czujnikiem pomieszczenia lub włączyć samoczynną
instalację przeciwpożarową. Możliwości jest bez liku, a wszystko za sprawą jednego bitu informacji.

ZAPAMIĘTAJ

1 bit

może przekazać informację o dwóch różnych zdarzeniach.

Bit oznaczamy małą literką

b

.

background image

Architektura Komputera – Kodowanie Liczb

5

Grupa bitów

Aparat cyfrowy

Zapamiętuje obraz

jako długi ciąg bitów

Świat jest zbyt skomplikowany, aby zawrzeć go w dwóch wiadomościach. Dlatego bardzo prędko dojdziemy do sytuacji, gdzie należy operować
kilkoma różnymi wiadomościami i bit stanie się niewystarczający. Na szczęście bity możemy łączyć w grupy i traktować je wspólnie jako symbol
złożony. Przy takim podejściu otrzymujemy nieograniczone możliwości tworzenia słów binarnych i przypisywania im znaczeń.Grupa dwóch bitów
oddaje nam do dyspozycji cztery różne symbole, które powstają z kombinacji stanów tworzących je bitów:

00

- symbol pierwszy

01

- symbol drugi

10

- symbol trzeci

11

- symbol czwarty

Każdemu symbolowi możemy przypisać informację o osobnym zdarzeniu. Grupa dwóch bitów może więc przekazać informację o
czterech różnych zdarzeniach.

background image

Architektura Komputera – Kodowanie Liczb

6

Przykład

Załóżmy, iż chcemy zakodować binarnie obrazek pokazany poniżej: Jest on złożony z różnokolorowych punktów, które

nazywamy pikselami (z języka ang. picture element - element obrazu, punkt).








Od razu zauważamy, że punkty są tylko w czterech kolorach. Układamy tablicę kodową kolorów, w której każdemu kolorowi punktu
przyporządkujemy jeden symbol dwubitowy:

- 00

- 01

- 10

- 11

Powiązaliśmy w ten sposób informację z reprezentującymi ją symbolami. Teraz wystarczy już tylko każdy piksel zastąpić symbolem
dwubitowym. W tej postaci obrazek może być przechowywany w pamięci komputera, przesyłany przez sieci teleinformatyczne oraz
przetwarzany.

00 00 00 00 00 00 00 00

0000000000000000

00 00 11 11 11 11 00 00

0000111111110000

00 11 11 11 11 11 00 00

0011111111110000

00 00 11 11 11 11 11 00

0000111111111100

00 00 00 11 11 00 00 00

0000001111000000

00 00 00 00 10 00 00 00

0000000010000000

00 00 00 00 10 00 00 00

0000000010000000

01 01 01 01 01 01 01 01

0101010101010101

background image

Architektura Komputera – Kodowanie Liczb

7

Zwróćmy uwagę na małą czytelność dla ludzi informacji zapisanej w systemie binarnym. Szczególnie, jeśli wszystkie bity zapiszemy w
jednym ciągu:

0000000000000000000011111111000000111111111100000000111111111100000000111100000000000000100000000101010101010101

Należy jednak pamiętać o tym, iż system ten jest przeznaczony dla maszyn, które nie nudzą się i nie męczą.

Dwa bity dają nam cztery symbole. Jeśli zwiększymy liczbę bitów w grupie do trzech, to dostępna ilość symboli wzrośnie do ośmiu:

0

00

- symbol pierwszy

0

01

- symbol drugi

0

10

- symbol trzeci

0

11

- symbol czwarty

1

00

- symbol piąty

1

01

- symbol szósty

1

10

- symbol siódmy

1

11

- symbol ósmy

Wynika z tego, iż zwiększenie liczby bitów w grupie zwiększa dwukrotnie liczbę dostępnych symboli binarnych, które mogą przenosić
informację o zdarzeniu. W poniższej tabeli dokonaliśmy odpowiednich obliczeń dla grup bitowych o długościach od 1 do 32 bitów.

background image

Architektura Komputera – Kodowanie Liczb

8

liczba bitów liczba symboli liczba bitów liczba symboli

1

2

17

131072

2

4

18

262144

3

8

19

524288

4

16

20

1048576

5

32

21

2097152

6

64

22

2097152

7

128

23

8388608

8

256

24

16777216

9

512

25

33554432

10

1024

26

67108864

11

2048

27

134217728

12

4096

28

268435456

13

8192

29

536870912

14

16384

30

1073741824

15

32768

31

2147483648

16

65536

32

4294967296

background image

Architektura Komputera – Kodowanie Liczb

9

Liczba symboli wzrasta geometrycznie. Ogólnie dla grupy n bitowej liczba możliwych do wykorzystania symboli binarnych wyraża się
liczbą 2

n

. Dla każdej skończonej liczby wiadomości zawsze możemy dobrać taką liczbę bitów, aby liczba słówek bitowych była równa lub

większa

od liczby wiadomości. Dla n wiadomości wystarczy, aby liczba bitów była równa części całkowitej wyrażenia

(log

2

(n - 1) + 1).

ZAPAMIĘTAJ

n

bitów daje

2

n

symboli

n

symboli wymaga

[log

2

(n - 1) + 1]

bitów

Przykład

Drukarka komputerowa.

Dane do druku przekazywane

są w postaci ciągu bitów.

Zaprojektować kod binarny przeznaczony do kodowania małych liter alfabetu łacińskiego.

background image

Architektura Komputera – Kodowanie Liczb

10

W tym przypadku wiadomościami będą literki. W alfabecie łacińskim jest ich 26:

a

bcdefghijklmnopqrstuvwxyz

. Każda literka musi

być kodowana innym symbolem binarnym. Musimy określić zatem niezbędną liczbę bitów tworzących te symbole. W tym celu
wykorzystujemy drugi z podanych wzorów i otrzymujemy:

[log

2

(26 - 1) + 1] = [log

2

25 + 1] = [4,64 + 1] = [5,64] = 5 bitów

5 bitów tworzy 32 symbole. Nam potrzebne jest 26, więc 6 symboli nie zostanie wykorzystanych. Od przybytku głowa nie boli. Ważne
jest, aby symboli nie było mniej niż liczba wiadomości do zakodowania. Więcej w niczym nam nie przeszkadza - nawet lepiej, gdyż w
przyszłości będzie można do takiego systemu dodać 6 nowych znaków (n. spacja, przecinek, kropka itp.).

W następnym kroku układamy tabelkę kodu znakowego, w której każdej literce przydzielamy jeden symbol binarny. Po tej operacji
można literki przedstawiać jako symbole binarne oraz z symboli binarnych odczytywać literki. Odwzorowanie jest zatem obustronne.

Binarny kod znakowy

Znak Kod

Znak Kod

Znak Kod

Znak Kod

a

00000

h

00111

o

01110

v

10101

b

00001

i

01000

p

01111

w

10110

c

00010

j

01001

q

10000

x

10111

d

00011

k

01010

r

10001

y

11000

e

00100

l

01011

s

10010

z

11001

f

00101

m

01100

t

10011

g

00110

n

01101

u

10100

background image

Architektura Komputera – Kodowanie Liczb

11

Zamieńmy na bity wg opracowanego schematu słowo "sowa":

s

- 10010

o

- 01110

w

- 10110

a

- 00000

Po połączeniu bitów w jeden ciąg otrzymujemy ostatecznie:

10010011101011000000

Dla człowieka zapis ten staje się zupełnie nieczytelny, lecz komputery radzą sobie z nim znakomicie - bity to ich żywioł. Spróbujmy teraz
dokonać operacji odwrotnej, tzn. odczytać słowo zakodowane w bitach, które np. otrzymaliśmy za pomocą sieci teleinformatycznej z
drugiego końca świata:

1001101110010101100001110

Najpierw rozdzielamy otrzymane bity na grupy po pięć sztuk:

10011 01110 01010 11000 01110

Dla każdej grupy bitów (symbolu binarnego) odszukujemy w tabelce kodu odpowiednią literkę:

10011

- t

01110

- o

01010

- k

11000

- y

01110

- o

background image

Architektura Komputera – Kodowanie Liczb

12

Bajt

Chociaż wolno nam tworzyć kody binarne o dowolnej liczbie bitów na symbol, to jednak z technicznego punktu widzenia wygodnie jest
przyjąć pewne ustalone jednostki. Standardowe grupy bitów można w prosty sposób przechowywać w pamięciach komputerów, na
nośnikach danych oraz przesyłać za pomocą sieci teleinformatycznych.

Bajt

jest taką właśnie standaryzacją. Najczęściej przyjmuje się, iż jest to grupa 8 bitów. Komórki pamięci komputera przechowują

informację w postaci bajtów. Również wiele urządzeń przystosowane zostało do danych przekazywanych w takiej formie (porcjami po 8
bitów) - np. drukarki, terminale, modemy, dyski elastyczne i twarde, itp. Dlatego bajt stał się kolejną po bicie jednostką informacji. Bajt
utożsamiany jest ze znakiem, literą, ponieważ używa się często 8 bitowego kodu do przekazywania znaków (

ASCII

-

A

merican

S

tandard

C

ode for

I

nformation

I

nterchange).

ZAPAMIĘTAJ

Bajt

jest grupą 8 bitów.

Oznaczamy go dużą literką

B

w odróżnieniu od bitu -

b

.

1 B

pozwala przekazywać informację o

256

zdarzeniach

.

Mnożniki binarne

W fizyce i technice stosowane są wielokrotności jednostek podstawowych. Oznaczamy je odpowiednimi przyrostkami kilo, mega, giga i
tera. Podstawą tych wielokrotności jest liczba 10:

kilo

= 1000

= 10

3

mega

= 1000000

= 10

6

= kilo x 1000

giga

= 1000000000

= 10

9

= mega x 1000

tera

= 1000000000000 = 10

12

= giga x 1000

background image

Architektura Komputera – Kodowanie Liczb

13

W systemie binarnym, ze względu na podobieństwo, zastosowano również podobne mnożniki, jednakże podstawą ich jest liczba 2, nie 10,
gdyż tak jest dużo wygodniej (pod koniec tego opracowania zrozumiesz dlaczego). Starano się przy tym, aby mnożnik binarny był jak
najbliższy odpowiednikowi dziesiętnemu. I tak otrzymano:

Kilo

= 1024

= 2

10

Mega

= 1048576

= 2

20

= Kilo x 1024

Giga

= 1073741824

= 2

30

= Mega x 1024

Tera

= 1099511627776 = 2

40

= Giga x 1024

Dla odróżnienia mnożników binarnych od dziesiętnych zapisujemy je dużą literką. Jednostki binarne dzielimy na bitowe (podstawą jest
bit) oraz bajtowe (podstawą jest bajt).

Jednostki binarne

bitowe

bajtowe

1b

bit

1B

bajt

1Kb

kilobit

1KB

kilobajt

1Mb

megabit

1MB

megabajt

1Gb

gigabit

1GB

gigabajt

1Tb

terabit

1TB

terabajt

ZAPAMIĘTAJ

Podstawą mnożników binarnych jest liczba

2

, a nie

10

. Więc zamiast

1000 = 10

3

mamy

1024 = 2

10

.

background image

Architektura Komputera – Kodowanie Liczb

14

Zadania

1

. Skoro informacja jest tworem niematerialnym, to w jaki sposób może być przetwarzana za pomocą maszyn liczących?

2

. Ile bitów potrzebne jest do zakodowania każdej cyfry dziesiętnej? Podaj odpowiedni przykład.

3

. Jak wzrośnie liczba słówek kodowych, jeśli zwiększymy dwukrotnie liczbę tworzących je bitów?

4

. Ile bitów zawiera 1MB?

5

. Ile bajtów zawiera 1,5GB?











background image

Architektura Komputera – Kodowanie Liczb

15

NATURALNY KOD BINARNY

W poprzednim rozdziale pokazaliśmy sposoby tworzenia złożonych symboli binarnych z grup bitów. Liczby moglibyśmy w zasadzie
zakodować binarnie podobnie jak znaki - każdej z nich przypisując określoną kombinację stanów bitów. Jednakże w przeciwieństwie do
znaków na liczbach chcemy przeprowadzać różne operacje arytmetyczne i otrzymywać wyniki zgodne z zasadami arytmetyki. Dlatego
sposób przypisania bitów liczbom nie może być dowolny, lecz musi tworzyć system ułatwiający wykonywanie obliczeń - w przeciwnym
razie elektroniczne układy arytmetyczne ogromnie by się skomplikowały, a tego nie chcemy.

Rozwiązanie tego problemu istnieje już od dawna, a nawet posługujemy się nim na co dzień - jest to pozycyjny system liczenia

.

Systemy pozycyjne

Abakus.

Prosty przyrząd wykorzystujący
własności systemu pozycyjnego

background image

Architektura Komputera – Kodowanie Liczb

16

Ponad tysiąc lat temu pewien hinduski geniusz wymyślił system zapisu liczb, w którym stosuje się jedynie dziesięć różnych znaków,
zwanych cyframi. Za sprawą kupców arabskich system ten został rozpowszechniony w ówczesnym świecie i dzisiaj powszechnie jest
znany pod nazwą systemu arabskiego. Cechą charakterystyczną tego systemu jest to, iż wartość cyfr w zapisie liczby zależy od ich
pozycji. Np.

333

w liczbie tej występują trzy jednakowe cyfry - 3. Pierwsza jednak oznacza trzy setki, druga trzy dziesiątki, a ostatnia trzy jednostki.
System ten jest dla nas tak naturalny, iż utożsamiamy wręcz wartość liczby z jej zapisem.

W systemie dziesiętnym podstawą jest liczba dziesięć. Wagi kolejnych pozycji licząc od prawej strony do lewej mają wartość kolejnych
potęg podstawy. Wartość liczby jest sumą iloczynów wartości cyfr przez wagi swoich pozycji. Powyższy zapis możemy więc zapisać
następująco:

333 = 3 x 10

2

+ 3 x 10

1

+ 3 x 10

0

Jeśli przez

p

oznaczymy podstawę systemu (czyli 10), a przez

c

cyfrę ze zbioru

{0,1,...,9}

, to wartość dowolnej,

n

-cyfrowej liczby

dziesiętnej wyrazi się wzorem:

c

n-1

c

n-2

...c

2

c

1

c

0

= c

n-1

x p

n-1

+ c

n-2

x p

n-2

+ ... + c

2

x p

2

+ c

1

x p

1

+ c

0

x p

0

Powyższy wzór jest również prawdziwy, jeśli dokonamy zmiany wartości podstawy p. Na przykład dla p = 5 otrzymujemy system
piątkowy. W systemie piątkowym mamy cyfry {0,1,2,3,4} - cyfry 5 nie ma z tych samych powodów, dla których w naszym systemie nie
występuje cyfra 10. Obliczmy dla przykładu wartość liczby piątkowej 3214

(5)

.

3214

(5)

= 3 x 5

3

+ 2 x 5

2

+ 1 x 5

1

+ 4 x 5

0

3214

(5)

= 3 x 125 + 2 x 25 + 1 x 5 + 4 x 1

3214

(5)

= 375 + 50 + 5 + 4

3214

(5)

= 434

background image

Architektura Komputera – Kodowanie Liczb

17

A teraz liczba trójkowa (

p

= 3,

c

- {0,1,2} ) 2012

(3)

:

2012

(3)

= 2 x 3

3

+ 0 x 3

2

+ 1 x 3

1

+ 2 x 3

0

2012

(3)

= 2 x 27 + 0 x 9 + 1 x 3 + 2 x 1

2012

(3)

= 54 + 0 + 3 + 2

2012

(3)

= 59

Z przedstawionych przykładów można wysnuć wniosek, iż każdy system pozycyjny jest równie dobry do zapisu liczb.
System dziesiętny jest tutaj o tyle wyjątkowy, iż stosujemy go do zapisu liczb i wydaje się on nam naturalnym
systemem liczbowym. Jeśli jednak będziemy zmniejszać wartość podstawy, to w końcu dojdziemy do liczby 2. System
liczenia oparty na liczbie 2 jest najprostszym systemem pozycyjnym i z tego powodu doskonale nadaje się do
zastosowania w maszynowych rachunkach.

ZAPAMIĘTAJ

W dowolnym systemie pozycyjnym o podstawie

p

mamy

p

cyfr

c

- {0,1,...,p-1}. Wagi kolejnych

pozycji od strony prawej do lewej są kolejnymi od zera potęgami podstawy. Wartość liczby
obliczamy jako sumę iloczynów cyfr przez wagi swoich pozycji.

c

n-1

c

n-2

...c

1

c

0

= c

n-1

p

n-1

+ c

n-2

p

n-2

+ ... + c

1

p

1

+ c

0

p

0

background image

Architektura Komputera – Kodowanie Liczb

18

Dwójkowy system pozycyjny

W systemie dwójkowym podstawa wynosi 2. Cyfr jest tylko dwie: 0 i 1. Dzięki temu cyfry dwójkowe mogą być
bezpośrednio przedstawiane przy pomocy bitów, które również przyjmują dwa stany. Wartość liczby oblicza się
szczególnie prosto - w sumie bierzemy tylko te wagi pozycji, na których występują cyfry 1. Oto przykład:

110111

(2)

= 1 x 2

5

+ 1 x 2

4

+ 0 x 2

3

+ 1 x 2

2

+ 1 x 2

1

+ 1 x 2

0

110111

(2)

= 1 x 32 + 1 x 16 + 0 x 8 + 1 x 4 + 1 x 2 + 1 x 1

110111

(2)

= 32 + 16 + 4 + 2 + 1

110111

(2)

= 55

Liczby binarne zapisujemy najczęściej z określoną liczbą bitów (np. 4, 8, 16, 32...). Podyktowane to jest względami
technicznymi. Na przykład pamięć komputera zapamiętuje w jednej komórce 8 bitów, więc rozsądnie jest przyjąć
format zapisu liczby, który jest wielokrotnością 8 bitów. Bardzo pomocna jest znajomość pierwszych 16 liczb
zapisanych w systemie binarnym. Proponujemy wyuczenie się na pamięć poniższej tabelki, co bardzo przyda się przy
konwersjach pomiędzy systemami ósemkowym i szesnastkowym. Zwróćcie uwagę, iż dla początkowych liczb starsze
wagi pozycji zawierają cyfry 0.

background image

Architektura Komputera – Kodowanie Liczb

19

Pierwsze 16 liczb binarnych

0

0000

=

0

x 2

3

+

0

x 2

2

+

0

x 2

1

+

0

x 2

0

1

0001

=

0

x 2

3

+

0

x 2

2

+

0

x 2

1

+

1

x 2

0

2

0010

=

0

x 2

3

+

0

x 2

2

+

1

x 2

1

+

0

x 2

0

3

0011

=

0

x 2

3

+

0

x 2

2

+

1

x 2

1

+

1

x 2

0

4

0100

=

0

x 2

3

+

1

x 2

2

+

0

x 2

1

+

0

x 2

0

5

0101

=

0

x 2

3

+

1

x 2

2

+

0

x 2

1

+

1

x 2

0

6

0110

=

0

x 2

3

+

1

x 2

2

+

1

x 2

1

+

0

x 2

0

7

0111

=

0

x 2

3

+

1

x 2

2

+

1

x 2

1

+

1

x 2

0

8

1000

=

1

x 2

3

+

0

x 2

2

+

0

x 2

1

+

0

x 2

0

9

1001

=

1

x 2

3

+

0

x 2

2

+

0

x 2

1

+

1

x 2

0

10

1010

=

1

x 2

3

+

0

x 2

2

+

1

x 2

1

+

0

x 2

0

11

1011

=

1

x 2

3

+

0

x 2

2

+

1

x 2

1

+

1

x 2

0

12

1100

=

1

x 2

3

+

1

x 2

2

+

0

x 2

1

+

0

x 2

0

13

1101

=

1

x 2

3

+

1

x 2

2

+

0

x 2

1

+

1

x 2

0

14

1110

=

1

x 2

3

+

1

x 2

2

+

1

x 2

1

+

0

x 2

0

background image

Architektura Komputera – Kodowanie Liczb

20

ZAPAMIĘTAJ

W systemie dwójkowym waga pozycji ma wartość

2

. Występują tylko dwie cyfry

0

i

1

.

Wartość liczby obliczamy zgodnie ze wzorem:

c

n-1

c

n-2

...c

1

c

0

= c

n-1

2

n-1

+ c

n-2

2

n-2

+ ... + c

1

2

1

+ c

0

2

0

Zakres naturalnych liczb dwójkowych

Oparliśmy system zapisu liczb binarnych na pozycyjnym systemie dwójkowym, ponieważ pozwalał on bezpośrednio
kodować cyfry przy pomocy bitów. W następnym kroku określimy zakres liczb, które można przedstawić przy
pomocy n bitów. Na początek dolna granica. Najmniejszą liczbę otrzymamy, gdy wszystkie cyfry przyjmą wartość 0.
Wartość takiej liczby jest równa zero. Dolną granicą jest zatem liczba zero.

Górną granicę dla n bitów otrzymamy ustawiając wszystkie cyfry na 1. Będzie to największa liczba możliwa do
zapisania przy pomocy n bitów. Jaką wartość ma taka liczba. Szybko przekonamy się wypisując kilka początkowych
wartości:

dla n = 1 mamy 1

(2)

= 1

= 2

1

- 1

dla n = 2 mamy 11

(2)

= 3

= 2

2

- 1

dla n = 3 mamy 111

(2)

= 7

= 2

3

- 1

dla n = 4 mamy 1111

(2)

= 15 = 2

4

- 1

background image

Architektura Komputera – Kodowanie Liczb

21

W każdym przypadku otrzymujemy za górną granicę liczbę równą

2

n

- 1

. Podsumujmy:

ZAPAMIĘTAJ

Dla

n

bitów możemy utworzyć w naturalnym kodzie binarnym liczby z zakresu:

<0, 2

n

- 1>

Sytuację odwrotną mamy, gdy dana jest określona liczba naturalna

W

, a chcemy poznać ilość bitów potrzebnych do

jej zapisu w naturalnym systemie binarnym. W tym celu wystarczy, aby była spełniona prosta nierówność:

W ≤ 2

n

- 1

,

gdzie

n

jest poszukiwaną liczbą bitów

Liczbę

n

obliczamy następująco:

n = [log

2

W + 1]

ZAPAMIĘTAJ

Do zapisu liczby naturalnej

n

potrzebne jest co najmniej

[log

2

n + 1]

bitów

.

background image

Architektura Komputera – Kodowanie Liczb

22

Ósemkowy system pozycyjny

Liczby binarne są niewygodne dla ludzi. Cyfry 0 i 1 dają zbyt małą różnorodność i nasze mózgi szybko się nużą przy analizowaniu
długich ciągów bitów. Dlatego programiści często zastępują zapis binarny zapisem ósemkowym. Chociaż na początku może się to
wydawać dziwne, to jednak ma sens. Otóż system ósemkowy i dwójkowy posiadają wspólną cechę - podstawą ich jest potęga liczby 2.
Dzięki temu szczególnie prosto można przeliczać liczby pomiędzy tymi systemami.Do zamiany liczb binarnych i ósemkowych potrzebna
nam będzie prosta tabelka, w której każdą cyfrę ósemkową przedstawiamy w postaci trzech bitów.

cyfra

ósemkowa

wartość

dwójkowa

0

000

1

001

2

010

3

011

4

100

5

101

6

110

7

111

ZAPAMIĘTAJ

W systemie ósemkowym waga pozycji ma wartość 8. Występuje osiem cyfr {0,1,2,3,4,5,6,7}.

Wartość liczby obliczamy zgodnie ze wzorem:

c

n-1

c

n-2

...c

1

c

0

= c

n-1

8

n-1

+ c

n-2

8

n-2

+ ... + c

1

8

1

+ c

0

8

0

background image

Architektura Komputera – Kodowanie Liczb

23

Zamiana liczby dwójkowej na ósemkową

Mamy liczbę dwójkową

10111011010101

(2)

. Zamienimy ją na liczbę w systemie ósemkowym o tej samej wartości. W

tym celu bity dzielimy na grupy trzybitowe poczynając od końca. Jeśli w ostatniej grupie nie będzie trzech bitów, to
dopisujemy na początku odpowiednią liczbę zer:

10111011010101

010 111 011 010 101

Każdą z grup trzybitowych zastępujemy cyfrą ósemkową z tabelki:

010

2

111

7

011

3

010

2

101

5

W wyniku otrzymujemy liczbę ósemkową o tej samej wartości:

10111011010101

(2)

. = 27325

(8)

background image

Architektura Komputera – Kodowanie Liczb

24

Sprawdźmy to:

10111011010101

(2)

. = 8192 + 2048 + 1024 + 512 + 128 + 64 + 16 + 4 + 1 =

11989

27325

(8)

= 2 x 4096 + 7 x 512 + 3 x 64 + 2 x 8 + 5 x 1 = 8192 + 3584 + 192 + 16 + 5 =

11989

Otrzymaliśmy w obu wypadkach ten sam wynik, wobec tego zapis

10111011010101

(2)

oraz

27325

(8)

odnosi się do tej

samej liczby o wartości dziesiętnej

11989

.

ZAPAMIĘTAJ

Przeliczeń pomiędzy systemem ósemkowym a binarnym dokonujemy zastępując cyfry ósemkowe ich trzybitową
wartością w systemie dwójkowym. W odwrotną stronę zastępujemy grupy trzybitowe cyfrą ósemkową, która
odpowiada im wartością.

Zamiana liczby ósemkowej na dwójkową

Operacja odwrotna jest równie prosta. W tym przypadku każdą cyfrę ósemkową zastępujemy trzybitową wartością z tabelki. W
Wyniku otrzymamy liczbę dwójkową o tej samej wartości. Zamieńmy liczbę ósemkową

336724076102

(8)

na odpowiadającą jej liczbę

binarną:

3

011

3

011

6

110

7

111

2

010

4

100

0

000

7

111

6

110

1

001

0

000

2

010

Zatem

336724076102

(8)

= 011011110111010100000111110001000010

(2)

Zwróćcie uwagę, iż zapis ósemkowy jest krótszy i bardziej czytelny dla ludzi od zapisu dwójkowego. Z tego właśnie powodu programiści
wolą stosować liczby ósemkowe zamiast binarnych - zawsze przecież można je szybko przeliczyć w jedną i drugą stronę.

background image

Architektura Komputera – Kodowanie Liczb

25

Szesnastkowy system pozycyjny

Drugim popularnym systemem służącym do zastępowania liczb binarnych jest system szesnastkowy. Podstawa w tym
systemie ma wartość 16. Potrzebujemy zatem 16 cyfr, jednakże dorobiliśmy się ich tylko 10 - {0,1,2,3,4,5,6,7,8,9}.
Brakujące 6 cyfr zastępujemy kolejnymi literkami alfabetu A,B,C,D,E i F. Cyfry te mają kolejne wartości: A = 10, B
= 11, C = 12, D = 13, E = 14 i F = 15. Po tych ustaleniach możemy już zapisywać liczby w systemie szesnastkowym
oraz obliczać ich wartość. Np. obliczmy wartość liczby 25FE

(16)

. Korzystamy ze znanego wzoru:

25FE

(16)

= 2 x 4096 + 5 x 256 + 15 x 16 + 14 x 1 = 9726

ZAPAMIĘTAJ

W systemie szesnastkowym, zwanym również heksadecymalnym, podstawa p = 16. Zbiór cyfr tworzą znaki:
{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. Dodatkowe cyfry A,...,F mają wartości dziesiętne równe kolejno od 10 do 15.
Wartość liczby szesnastkowej obliczamy według wzoru:

c

n-1

c

n-2

...c

1

c

0

= c

n-1

16

n-1

+ c

n-2

16

n-2

+ ... + c

1

16

1

+ c

0

16

0

background image

Architektura Komputera – Kodowanie Liczb

26

Konwersję pomiędzy systemem szesnastkowym a dwójkowym wykonujemy podobnie jak dla systemu ósemkowego - 16 jest również
potęgą liczby 2. Potrzebna nam będzie tabelka wartości cyfr szesnastkowych w systemie dwójkowym. Każdej cyfrze szesnastkowej
odpowiada grupa czterech bitów:

cyfra

szesnastkowa

wartość

dwójkowa

0

0000

1

0001

2

0010

3

0011

4

0100

5

0101

6

0110

7

0111

8

1000

9

1001

A

1010

B

1011

C

1100

D

1101

E

1110

F

1111

background image

Architektura Komputera – Kodowanie Liczb

27

Zamiana liczby dwójkowej na szesnastkową

Liczbę dwójkową dzielimy na grupy czterobitowe poczynając od prawej strony. Jeśli w ostatniej grupie wypadnie
mniej bitów, to dopełniamy je zerami. Następnie każdą grupę zastępujemy odpowiednią cyfrą szesnastkową. Dla
przykładu zamieńmy liczbę binarną

111010100011101010101101101001110

(2)

na odpowiadającą jej wartość w

systemie szesnastkowym:

111010100011101010101101101001110

0001

1

1101

D

0100

4

0111

7

0101

5

0101

5

1011

B

0100

4

1110

E

111010100011101010101101101001110

(2)

= 1D4755B4E

(16)

Czytelnikom pozostawiamy sprawdzenie, iż są to te same liczby.

Zamiana liczby szesnastkowej na dwójkową

Zamiana polega na zastąpieniu każdej cyfry szesnastkowej odpowiadającą jej grupą czterech bitów z tabelki. W
wyniku otrzymamy liczbę dwójkową o tej samej wartości. Dla przykładu zamieńmy liczbę FDA73201

(16)

na postać

binarną:

F

1111

D

1101

A

1010

7

0111

3

0011

2

0010

0

0000

1

0001

Zatem

FDA73201

(16)

= 11111101101001110011001000000001

(2)

.

background image

Architektura Komputera – Kodowanie Liczb

28

Dwójkowe liczby stałoprzecinkowe

System stałopozycyjny zapisu liczb jest rozszerzeniem zapisu liczb naturalnych w stronę wartości ułamkowych. W
systemie dziesiętnym za cyfrą jednostek umieszcza się przecinek, a kolejne wagi pozycji są teraz ujemnymi potęgami
podstawy:

253,763 = 2 x 10

2

+ 5 x 10

1

+ 3 x 10

0

+ 7 x 10

-1

+ 6 x 10

-2

+ 3 x 10

-3

Zasada ta obowiązuje również w innych systemach pozycyjnych. Dla przykładu obliczmy wartość stałopozycyjnej
liczby piątkowej:

432,321

(5)

:

432,321

(5)

= 4 x 5

2

+ 3 x 5

1

+ 2 x 5

0

+ 3 x 5

-1

+ 2 x 5

-2

+ 1 x 5

-3

432,331

(5)

= 4 x 25 + 3 x 5 + 2 x 1 + 3 x

1

/

5

+ 2 x

1

/

25

+ 1 x

1

/

125

432,331

(5)

= 100 + 15 + 2 +

3

/

5

+

2

/

25

+

1

/

125

432,331

(5)

= 117

86

/

125

432,331

(5)

= 117,688

ZAPAMIĘTAJ

W dowolnym systemie pozycyjnym o podstawie

p

wartość liczby stałoprzecinkowej obliczamy wg wzoru:

c

n-1

...c

0

,c

-1

c

-2

...c

-m

= c

n-1

p

n-1

+ ... + c

0

p

0

+ c

-1

p

-1

+ c

-2

p

-2

+ ... +c

-m

p

-m

gdzie

n

- liczba cyfr przed przecinkiem,

m

- liczba cyfr po przecinku

background image

Architektura Komputera – Kodowanie Liczb

29

Znając tą zasadę nie napotkamy żadnych trudności w systemie dwójkowym. Obliczymy wartość dwójkowej liczby
stałoprzecinkowej

1101,1011

(2)

:

1101,1011

(2)

= 1 x 2

3

+ 1 x 2

2

+ 0 x 2

1

+ 1 x 2

0

+ 1 x 2

-1

+ 0 x 2

-2

+ 1 x 2

-3

+ 1 x 2

-4

1101,1011

(2)

= 1 x 8 + 1 x 4 + 0 x 1 + 1 x 1 + 1 x

1

/

2

+ 0 x

1

/

4

+ 1 x

1

/

8

+ 1 x

1

/

16

1101,1011

(2)

= 8 + 4 + 1 +

1

/

2

+

1

/

8

+

1

/

16

1101,1011

(2)

= 13 +

10

/

16

1101,1011

(2)

= 13,625

Zakres dwójkowych liczb stałoprzecinkowych

Określimy zakres liczb stałoprzecinkowych, w których

n

bitów przechowuje część całkowitą, a

m

bitów część

ułamkową. Wartość takiej liczby można zapisać jako sumę części całkowitej oraz części ułamkowej:

Jeśli liczbę zapiszemy za pomocą cyfr binarnych

c

, należących do zbioru {0,1}, to

W - wartość liczby = c

n-1

c

n-2

...c

2

c

1

c

0

,c

-1

c

-2

...c

-m+1

c

-m

W

c

- wartość części całkowitej = c

n-1

c

n-2

...c

2

c

1

c

0

W

u

- wartość części ułamkowej = c

-1

c

-2

...c

-m+1

c

-m

W = W

c

+ W

u

W

c

= c

n-1

2

n-1

+ c

n-2

2

n-2

+ ... + c

2

2

2

+ c

1

2

1

+ c

0

2

0

W

u

= c

-1

2

-1

+ c

-2

2

-2

+ ... + c

-m+1

2

-m+1

+ c

-m

2

-m

background image

Architektura Komputera – Kodowanie Liczb

30

Zakres części całkowitej

policzyliśmy już wcześniej i wynosi on

<0,2

n

- 1>.

Policzymy zatem zakres części ułamkowej. Najmniejszą liczbę

otrzymamy, gdy wszystkie cyfry będą zerami. Wartość ta wynosi oczywiście zero. Największą liczbę otrzymamy przy wszystkich cyfrach
równych 1.

Sprawdźmy ile to będzie dla kolejnych wartości

m

:

m = 1, 0,1

= 1 x 2

-1

= 1 x

1

/

2

=

1

/

2

m = 2, 0,11

= 1 x 2

-1

+ 1 x 2

-2

= 1 x

1

/

2

+ 1 x

1

/

4

=

3

/

4

m = 3 0,111 = 1 x 2

-1

+ 1 x 2

-2

+ 1 x 2

-3

= 1 x

1

/

2

+ 1 x

1

/

4

+ 1 x

1

/

8

=

7

/

8

Jeśli przyjrzycie się otrzymanym wynikom, to na pewno zauważycie, iż mianownik otrzymanego ułamka ma wartość

2

m

, natomiast

licznik jest o 1 mniejszy, czyli

2

m

- 1

. Stąd zakres części ułamkowej wynosi:

2

m

-

1

<0,

2

m

>

Jeśli teraz połączymy zakresy części całkowitej i ułamkowej, to otrzymamy zakres liczby stałoprzecinkowej o

n

cyfrach całkowitych i

m

cyfrach ułamkowych, który wynosi:

2

m

-

1

<0, 2

n

- 1 +

2

m

>

background image

Architektura Komputera – Kodowanie Liczb

31

Zadania

1

. Oblicz wartość następujących liczb:

1234

(5)

, 3456

(7)

, 5678

(9)

2

. Oblicz wartość następujących liczb binarnych:

110011

(2)

, 1110111

(2)

, 11001110011

(2)

3

. Jak wzrośnie zakres n bitowej liczby binarnej, jeśli zwiększymy jej długość o 3 bity?

4

. Załóżmy, iż pewna liczba binarna posiada 3n bitów. Taką liczbę da się przedstawić w systemie ósemkowym za pomocą n cyfr. Jak

rozpoznać w zapisie ósemkowym, iż najstarszy bit liczby binarnej ma wartość 1?

5

. Jak określić liczbę cyfr ósemkowych liczby binarnej zapisanej w systemie szesnastkowym za pomocą n cyfr?

6

. Oblicz wartość następującej liczby binarnej:

1100111,011101

(2)

background image

Architektura Komputera – Kodowanie Liczb

32

ALGORYTM HORNERA

Algorytm Hornera dla dowolnego systemu pozycyjnego

We wzorze obliczania wartości liczby zapisanej w dowolnym systemie pozycyjnym występują kolejne potęgi podstawy. Konieczność
wykonywania operacji potęgowania może być kłopotliwa, szczególnie, gdy obliczamy wartość liczby ze strumienia danych wejściowych.
W strumieniu takim otrzymujemy kolejne cyfry liczby oraz informację o ich końcu. Rozwiązaniem problemu jest algorytm Hornera,
który w pierwotnej postaci służy do obliczania wartości wielomianów potęgowych.

Załóżmy, że mamy daną pięciocyfrową liczbę

c

4

c

3

c

2

c

1

c

0

zapisaną w dowolnym systemie pozycyjnym o podstawie

p

(dla większej ilości

cyfr postępujemy identycznie). Obliczmy wartość liczby wg znanego nam wzoru potęgowego:

c

4

c

3

c

2

c

1

c

0

= c

4

p

4

+ c

3

p

3

+ c

2

p

2

+ c

1

p

1

+ c

0

p

0

Potęgę

p

1

zapiszmy jako

p

, a

p

0

jest równe 1, wobec czego wzór ten przyjmie postać:

c

4

c

3

c

2

c

1

c

0

= c

4

p

4

+ c

3

p

3

+ c

2

p

2

+ c

1

p + c

0

Wyprowadzamy czynnik

p

kolejno przed nawiasy:

c

4

c

3

c

2

c

1

c

0

= (c

4

p

3

+ c

3

p

2

+ c

2

p + c

1

)p + c

0

c

4

c

3

c

2

c

1

c

0

= ((c

4

p

2

+ c

3

p + c

2

)p + c

1

)p + c

0

c

4

c

3

c

2

c

1

c

0

= (((c

4

p + c

3

)p + c

2

)p + c

1

)p + c

0

Zwróćcie uwagę, iż w otrzymanym na końcu wzorze nie występuje już potęgowanie, lecz same mnożenia i dodawania. W jaki sposób
obliczamy wartość liczby?

background image

Architektura Komputera – Kodowanie Liczb

33

Wykonując obliczenia w nawiasach:

w

0

= c

4

w

1

= w

0

p + c

3

w

2

= w

1

p + c

2

w

3

= w

2

p + c

1

w

4

= w

3

p + c

0

- koniec, w

4

jest wartością liczby

Przy wykorzystaniu algorytmu Hornera w programach komputerowych podany schemat obliczeń jest nieco zmodyfikowany.
Mianowicie za wartość początkową liczby przyjmujemy zero, a następnie wykonujemy mnożenia przez podstawę i dodajemy kolejne
cyfry. Przy tej modyfikacji otrzymamy:

w

0

= 0

w

1

= w

0

p + c

4

w

2

= w

1

p + c

3

w

3

= w

2

p + c

2

w

4

= w

3

p + c

1

w

5

= w

4

p + c

0

- koniec, w

5

jest wartością liczby.

W tej wersji algorytm jest bardziej spójny z danymi - dla każdej kolejnej cyfry wykonywana jest ta sama operacja - przemnożenie
poprzedniej wartości liczby przez podstawę systemu i dodanie wartości cyfry.

background image

Architektura Komputera – Kodowanie Liczb

34

ZAPAMIĘTAJ

Algorytm Hornera obliczania wartości liczby zapisanej jako ciąg cyfr w dowolnym systemie pozycyjnym jest
następujący:

1. Za początkową wartość liczby przyjmij zero
2. Pobierz kolejną cyfrę liczby
3. Jeśli cyfra istnieje, to pomnóż wartość liczby przez podstawę systemu, dodaj do niej wartość cyfry i przejdź

do punktu 2

4. Jeśli cyfry skończyły się, to zakończ algorytm. Wartość liczby została obliczona.

Przykład

Obliczmy tą metodą wartość liczby szóstkowej

25314

(6)

. Podstawa systemu szóstkowego wynosi 6.

w

0

=

0

w

1

=

0 x 6 +

2

= 2

w

2

=

2 x 6 +

5

= 17

w

3

=

17 x 6 +

3

= 105

w

4

=

105 x 6 +

1

= 631

w

5

=

631 x 6 +

4

=

3790

A teraz sprawdźmy ten wynik normalną metodą przy zastosowaniu wzoru potęgowego:

25314

(6)

= 2 x 6

4

+ 5 x 6

3

+ 3 x 6

2

+ 1 x 6

1

+ 4 x 6

0

25314

(6)

= 2 x 1296 + 5 x 216 + 3 x 36 + 1 x 6 + 4 x 1

25314

(6)

= 2592 + 1080 + 108 + 6 + 4

25314

(6)

=

3790

background image

Architektura Komputera – Kodowanie Liczb

35

Algorytm Hornera dla naturalnych liczb dwójkowych

Ponieważ system dwójkowy jest systemem pozycyjnym, to obowiązują w nim te same zasady, co w innych systemach pozycyjnych.
Dzięki temu algorytm Hornera będzie identyczny z opisanym wcześniej, a nawet prostszy, ponieważ mnożenie przez dwa możemy
zastąpić dodawaniem, co znacznie przyspiesza obliczenia.

ZAPAMIĘTAJ

Algorytm Hornera obliczania wartości liczby dwójkowej jest następujący

:

1. Za początkową wartość liczby przyjmij zero
2. Pobierz kolejną cyfrę liczby
3. Jeśli cyfra istnieje, to dodaj do siebie poprzednią wartość liczby a do wyniku dodaj wartość pobranej cyfry i przejdź do punktu 2
4. Jeśli cyfry skończyły się, to zakończ algorytm. Wartość liczby została obliczona.

background image

Architektura Komputera – Kodowanie Liczb

36

Przykład

Obliczmy opisanym sposobem wartość liczby

11001011011

(2)

:

w

0

= 0

w

1

= 0 + 0 +

1

= 1

w

2

= 1 + 1 +

1

= 3

w

3

= 3 + 3 +

0

= 6

w

4

= 6 + 6 +

0

= 12

w

5

= 12 + 12 +

1

= 25

w

6

= 25 + 25 +

0

= 50

w

7

= 50 + 50 +

1

= 101

w

8

= 101 + 101 +

1

= 203

w

9

= 203 + 203 +

0

= 406

w

10

= 406 + 406 +

1

= 813

w

11

= 813 + 813 +

1

=

1627

background image

Architektura Komputera – Kodowanie Liczb

37

Algorytm Hornera dla liczb stałoprzecinkowych

Jeśli mamy daną liczbę stałoprzecinkową zapisaną w postaci

n

cyfr części całkowitej i

m

cyfr części ułamkowej, to do obliczenia jej

wartości możemy również zastosować algorytm Hornera po drobnej modyfikacji. Otóż obliczamy wartość liczby tak, jakby nie było
przecinka, a następnie wynik dzielimy przez wartość podstawy podniesionej do potęgi

m

.

Przykład

Obliczmy tą metodą wartość liczby siódemkowej 52,354

(7)

:

n = 2, m = 3

w

0

= 0

w

1

= 0 x 7 + 5 = 5

w

2

= 5 x 7 + 2 = 37

w

3

= 37 x 7 + 3 = 262

w

4

= 262 x 7 + 5 = 1839

w

5

= 1839 x 7 + 4 = 12877

- ostatnia cyfra, kończymy

Wynik dzielimy przez

7

m

= 7

3

= 343

w

5

1287

7

186

w

6

=

7

m

=

343

=

3

7

343

background image

Architektura Komputera – Kodowanie Liczb

38

Sprawdźmy otrzymany wynik za pomocą tradycyjnej metody obliczania wartości liczby stałoprzecinkowej:

52,354

(7)

= 5 x 7

1

+ 2 x 7

0

+ 3 x 7

-1

+ 5 x 7

-2

+ 4 x 7

-3

52,354

(7)

= 5 x 7 + 2 x 1 + 3 x

1

/

7

+ 5 x

1

/

49

+ 4 x

1

/

343

52,354

(7)

= 35 + 2 +

3

/

7

+

5

/

49

+

4

/

343

52,354

(7)

= 37 +

147

/

343

+

35

/

343

+

4

/

343

52,354

(7)

=

37

186

/

343

ZAPAMIĘTAJ

Algorytm Hornera obliczania wartości liczby stałoprzecinkowej zapisanej jako ciąg cyfr w dowolnym systemie
pozycyjnym jest następujący:

1. Oblicz wartość liczby tak, jakby nie było przecinka
2. Wynik podziel przez podstawę systemu pozycyjnego podniesioną do potęgi równej liczbie cyfr po przecinku

background image

Architektura Komputera – Kodowanie Liczb

39

Przeliczanie liczb na dowolny system pozycyjny

Rozważmy następujący problem: mamy liczbę dziesiętną o wartości

W

. Chcemy znaleźć kolejne cyfry

c

n-1

c

n-2

...c

2

c

1

c

0

zapisu tej liczby w systemie pozycyjnym o podstawie

p

. Zapiszmy:

W = c

n-1

p

n-1

+ c

n-2

p

n-2

+ ... + c

2

p

2

+ c

1

p + c

0

Podzielmy wartość

W

przez

p

. Otrzymamy wtedy:

W

c

0

p

= c

n-1

p

n-2

+ c

n-2

p

n-3

+ ... + c

2

p + c

1

+

p

Ponieważ wartość każdej cyfry jest zawsze mniejsza od podstawy systemu liczbowego, ułamek

c

0

/ p

jest ułamkiem

właściwym. Wobec tego wartość cyfry

c

0

otrzymamy jako resztę z dzielenia

W

przez

p

. Za nową wartość

W

przyjmijmy część całkowitą z dzielenia, czyli

W

W

1

= [

p

] = c

n-1

p

n-2

+ c

n-2

p

n-3

+ ... + c

2

p +

c

1

Zwróćcie uwagę, iż otrzymaliśmy nową wartość, której zapis w systemie o podstawie

p

składa się z tych samych cyfr

co

W

z pominięciem ostatniej

c

0

. Możemy teraz znów przeprowadzić identyczną operację i otrzymać kolejną cyfrę

c

1

jako resztę z dzielenia

W

1

przez

p

. Za nowe

W

przyjmujemy część całkowitą z dzielenia

W

1

przez

p

, czyli:

W

1

W

2

= [

p

] = c

n-1

p

n-3

+ c

n-2

p

n-2

+ ... +

c

2

background image

Architektura Komputera – Kodowanie Liczb

40

I znów mamy sytuację identyczną jak poprzednio. Możemy więc opisane działania kontynuować, aż do uzyskania
wszystkich cyfr. Wyliczanie cyfr przerywamy w chwili otrzymania wartości zero w wyniku dzielenia

W

i

przez

podstawę

p

.

Przykład

Dla przykładu znajdźmy wg opisanej metody cyfry w systemie czwórkowym liczby dziesiętnej

1000

.

W = 1000

c

0

= reszta z dzielenia 1000 przez 4 =

0

,

W

1

= [1000 : 4) = [250] = 250

c

1

= reszta z dzielenia 250 przez 4 =

2

W

2

= [250 : 4] = [62,5] = 62

c

2

= reszta z dzielenia 62 przez 4 =

2

W

3

= [62 : 4] = [15,5] = 15

c

3

= reszta z dzielenia 15 przez 4 =

3

W

4

= [15 : 4] = [3,75] = 3

c

4

= reszta z dzielenia 3 przez 4 =

3

W

5

= [3 : 4] = [0,75] = 0

- kończymy, gdyż wynik wynosi zero.

background image

Architektura Komputera – Kodowanie Liczb

41

Otrzymaliśmy cyfry:

33220

(4)

. Zauważcie, iż cyfry otrzymywaliśmy w odwrotnej do zapisu kolejności, tzn. od

najmłodszej do najstarszej. Sprawdźmy rachunkiem, czy otrzymana liczba czwórkowa ma w systemie dziesiętnym
wartość 1000.

33220

(4)

= 3 x 4

4

+ 3 x 4

3

+ 2 x 4

2

+ 2 x 4

1

+ 0 x 4

0

33220

(4)

= 3 x 256 + 3 x 64 + 2 x 16 + 2 x 4 + 0 x 1

33220

(4)

= 768 + 192 + 32 + 8

33220

(4)

=

1000

ZAPAMIĘTAJ

Zapis liczby dziesiętnej

W

w dowolnym systemie pozycyjnym o podstawie

p

znajdujemy następująco:

1. Wartość kolejnej od końca cyfry znajdujemy jako resztę z dzielenia W przez p.
2. Za nowe
W przyjmujemy część całkowitą z dzielenia W przez p.

3.

Jeśli W jest większe od zera, to przechodzimy do punktu 3. W przeciwnym razie kończymy.

Przeliczanie liczb dwójkowych

Wartości dziesiętne przeliczamy na system dwójkowy w identyczny sposób jak na inne systemy pozycyjne. Jedynym
ułatwieniem może być rozpoznawanie reszt z dzielenia przez 2. Jeśli dzielona liczba jest nieparzysta, to reszta zawsze
wyniesie 1. Dla liczb parzystych reszta z dzielenia przez 2 wynosi 0.

background image

Architektura Komputera – Kodowanie Liczb

42

Przykład

Znajdźmy reprezentację binarną liczby

253651

:

253651 : 2 = 126825

i reszta

c

0

=

1

126825 : 2 = 63412

i reszta

c

1

=

1

63412 : 2 = 31706

i reszta

c

2

=

0

31706 : 2 = 15853

i reszta

c

3

=

0

15853 : 2 = 7926

i reszta

c

4

=

1

7926 : 2 =

3963

i reszta

c

5

=

0

3963 : 2 =

1981

i reszta

c

6

=

1

1981 : 2 =

990

i reszta

c

7

=

1

990 : 2 =

495

i reszta

c

8

=

0

495 : 2 =

247

i reszta

c

9

=

1

247 : 2 =

123

i reszta

c

10

=

1

123 : 2 =

61

i reszta

c

11

=

1

61 : 2 =

30

i reszta

c

12

=

1

30 : 2 =

15

i reszta

c

13

=

0

15 : 2 =

7

i reszta

c

14

=

1

7 : 2 =

3

i reszta

c

15

=

1

3 : 2 =

1

i reszta

c

16

=

1

1 : 2 =

0

i reszta

c

17

=

1

- koniec, wynik dzielenia równy zero

253651 = 111101111011010011

(2)

background image

Architektura Komputera – Kodowanie Liczb

43

Przeliczanie liczb stałoprzecinkowych

Przy wyznaczaniu rozwinięcia liczb stałoprzecinkowych w dowolnych systemach pozycyjnych musimy dokonać
prostych modyfikacji przedstawionych algorytmów. Załóżmy, iż mamy pewną wartość

W

, która w docelowym

systemie pozycyjnym

p

posiada następujące rozwinięcie:

W = c

n-1

p

n-1

+ ...c

0

p

0

+ c

-1

p

-1

+ ... +c

-m

p

-m

gdzie

c

i

, i = -m...n-1

są cyframi rozwinięcia w systemie

p

,

n

określa liczbę cyfr części całkowitej, a

m

określa liczbę

cyfr części ułamkowej. Podane algorytmy pozwalają jedynie wyznaczać rozwinięcie liczb naturalnych. Dlatego przed
ich zastosowaniem musimy wartość liczby pomnożyć przez

p

m

, aby pozbyć się części ułamkowej:

W x p

m

= (c

n-1

p

n-1

+ ...c

0

p

0

+ c

-1

p

-1

+ ... +c

-m

p

-m

)p

m

W x p

m

= c

n-1

p

n-1

p

m

+ ...c

0

p

0

p

m

+ c

-1

p

-1

p

m

+ ... +c

-m

p

-m

p

m

W x p

m

= c

n-1

p

n-1+m

+ ...c

0

p

m

+ c

-1

p

m-1

+ ... +c

-m

p

0

Zwróćcie uwagę, iż takie przemnożenie nie zmienia cyfr rozwinięcia. W wyniku otrzymujemy liczbę całkowitą (jeśli
po przemnożeniu zostanie część ułamkowa, to liczby

W

nie można przedstawić dokładnie za pomocą

m

cyfr części

ułamkowej w systemie pozycyjnym

p

- w takim przypadku zaokrąglamy

W

do najbliższej liczby całkowitej). Po

wykonaniu mnożenia dokonujemy konwersji na system

p

. Następnie oddzielamy

m

ostatnich cyfr. Będzie to część

ułamkowa. Reszta cyfr tworzy część całkowitą.

background image

Architektura Komputera – Kodowanie Liczb

44

Przykład

Przeliczmy wartość dziesiętną 113,688 na system piątkowy z trzema cyframi po przecinku.

m = 3
W = 113,688 x 5

3

= 113,688 x 125 = 14211

Otrzymaliśmy liczbę całkowitą, więc wartość 113,688 da się przedstawić w systemie piątkowym z trzema cyframi po
przecinku. Obliczamy kolejne cyfry:

14211 : 5 = 2842 i reszta c

0

=

1

2842 : 5 = 568 i reszta c

1

=

2

568 : 5 = 113 i reszta c

2

=

3

113 : 5 =

22 i reszta c

3

=

3

22 : 5 =

4 i reszta c

4

=

2

4 : 5 =

0 i reszta c

5

=

4

- koniec, wynik dzielenia zero

Otrzymaliśmy

423321

. Oddzielamy od końca trzy cyfry (

m

= 3) części ułamkowej i otrzymujemy ostatecznie:

113,688 = 423,321

(5)

background image

Architektura Komputera – Kodowanie Liczb

45

ZAPAMIĘTAJ

Aby znaleźć rozwinięcie cyfr w dowolnym systemie pozycyjnym

p

wartości

W

z dokładnością do

m

cyfr po przecinku, należy:

1. Wartość

W

pomnożyć przez

p

m

. Jeśli otrzymamy liczbę całkowitą, to

W

można przedstawić dokładnie w systemie pozycyjnym

p

. Jeśli otrzymamy liczbę z częścią ułamkową, to wartości

W

nie da się przedstawić dokładnie na zadanej liczbie cyfr

ułamkowych w systemie pozycyjnym

p

. W takim przypadku zaokrąglamy iloczyn do najbliższej liczby całkowitej.

2. Obliczamy kolejne cyfry nowej wartości

W

.

3. Rozdzielamy przecinkiem

m

ostatnich cyfr od reszty otrzymanych cyfr. Jeśli cyfr tych jest mniej niż

m

, to dopisujemy przed

nimi odpowiednią liczbę zer.

Przykład

Obliczmy jeszcze rozwinięcie dwójkowe wartości

0,1

(jedna dziesiąta) na 8 cyfrach po przecinku.

m = 8
W = 0,1 x 2

8

= 0,1 x 256 = 25,6

Otrzymaliśmy liczbę ułamkową.

background image

Architektura Komputera – Kodowanie Liczb

46

Oznacza to, iż wartość dziesiętna 0,1 nie może być przedstawiona dokładnie w systemie binarnym na 8 cyfrach po
przecinku. Co gorsza, nie da się tego zrobić na dowolnej liczbie cyfr po przecinku, ponieważ nie istnieje taka potęga
liczby 2, aby jej iloczyn przez 0,1 dawał wartość całkowitą (wszystkie potęgi liczby 2 kończą się jedną z cyfr 2,4,6 lub
8). Wobec tego w systemie binarnym ułamek 0,1 ma nieskończone rozwinięcie. W naszym przypadku najbliższą
liczbą całkowitą będzie W = 26 i dla niej znajdziemy kolejne cyfry dwójkowe:

26 : 2 = 13

i reszta

c

0

=

0

13 : 2 = 6

i reszta

c

1

=

1

6 : 2 = 3

i reszta

c

2

=

0

3 : 2 = 1

i reszta

c

3

=

1

1 : 2 = 0

i reszta

c

4

=

1

- kończymy, wynik dzielenia zero

Otrzymaliśmy 5 cyfr:

11010

. Ponieważ po przecinku ma ich być 8, dopisujemy na początku 4 zera (jedno dla części

całkowitej), a następnie oddzielamy przecinkiem 8 końcowych cyfr i ostatecznie:

0,1

(10)

0,00011010

(2)

ZAPAMIĘTAJ

W systemie dwójkowym nie da się dokładnie przedstawić niektórych wartości dziesiętnych. Obliczenia na takich
liczbach prowadzą więc do tzw. błędów zaokrągleń. Podobną cechę mają np. ułamki

1

/

3

,

1

/

6

,

1

/

7

itp.

background image

Architektura Komputera – Kodowanie Liczb

47

Zadania

1

. Oblicz za pomocą algorytmu Hornera wartość następujących liczb pozycyjnych:

6243

(8)

, 132211

(4)

, 9FF35

(16)

2

. Oblicz algorytmem Hornera wartość liczby dwójkowej:

11001110001111000011111

(2)

3

. Oblicz algorytmem Hornera wartość następujących, pozycyjnych liczb stałoprzecinkowych:

221,1022

(3)

, 412,301

(5)

, 634,1252

(7)

4

. Przelicz na system szóstkowy następujące liczby dziesiętne:

100, 500, 1000, 10000

5

. Przelicz na system dwójkowy następujące liczby dziesiętne:

100, 1000, 10000

6

. Przelicz na system trójkowy z dokładnością do 4 cyfr po przecinku następujące dwie liczby dziesiętne:

10,5 15,86


Wyszukiwarka

Podobne podstrony:
Kodowanie liczb i tekstu
KODOWANIE LICZB
Kodowanie liczb
Kodowanie liczb
Kodowanie liczb 3
kodowanie liczb calkowitych
Kodowanie liczb i tekstu
KODOWANIE LICZB
Binarne Kodowanie Liczb Naturalny system dwójkowy
KODOWANIE LICZB
10 Reprezentacja liczb w systemie komputerowymid 11082 ppt
Wykład 6 6 kodowanie mowy
Kodowanie informacji

więcej podobnych podstron