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
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.
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.
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
.
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.
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
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.
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
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.
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
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
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
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
.
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?
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
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
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
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.
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
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
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
.
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
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)
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ę.
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
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
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)
.
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
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
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
>
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)
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?
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.
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
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.
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
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
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
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
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.
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.
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)
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ą.
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)
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ą.
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.
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