Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek
|
SPIS TREŚCI |
Podrozdziały |
Podstawowe cechy każdego systemu pozycyjnego można scharakteryzować w sposób następujący:
Rozważmy pewien system pozycyjny o dowolnej podstawie
p, p > 1. W systemie tym mamy
p cyfr, które oznaczymy literką c.
Zapiszmy pewną liczbę za pomocą n cyfr: cn-1cn-2...c2c1c0.
Wartość tak zapisanej liczby możemy obliczyć zgodnie z podanym powyżej sposobem:
waga pozycji | pn-1 | pn-2 | p2 | p1 | p0 | = c0·p0 + c1·p1 + c2·p2 + ... + cn-2·pn-2 + cn-1·pn-1 | |
cyfra | cn-1 | cn-2 | ... | c2 | c1 | c0 |
Matematycznie zapisujemy to w następujący sposób:
cn-1cn-2...c2c1c0 = |
n-1 i = 0 |
ci·pi |
Obliczmy wartość kilku liczb zapisanych w systemach pozycyjnych o różnych
podstawach.
p = 7, zbiór cyfr to {0,1,2,3,4,5,6}
43521(7) = ???(10) mały
indeks u dołu oznacza podstawę systemu, w którym zapisano liczbę.
43521(7) =
1 · 70 +
2 · 71 +
5 · 72 +
3 · 73 +
4 · 74
43521(7)
=
1 · 1 + 2 · 7 +
5 · 49 + 3 · 343 +
4
· 2401
43521(7) = 1 + 14 + 245 + 1029 + 9604
43521(7) = 10893(10)
p = 3, zbiór cyfr to {0,1,2}
2101122(3) = ???(10)
2101122(3) =
2 · 30 +
2 · 31 +
1 · 32 +
1 · 33 +
0 · 34 +
1 · 35 +
2 · 36
2101122(3) =
2 · 1 + 2 · 3 +
1
· 9 +
1 · 27 + 0 · 81 +
1
· 243 +
2 · 729
2101122(3)
= 2 + 6 + 9 + 27 + 243 + 1458
2101122(3) =
1745(10)
p = 17, zbiór cyfr to {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G} - brakujące cyfry
10..16 wyrażamy literkami A...G
AGF63B(17) = ???(10)
AGF63B(17) = 11 · 170 + 3 · 171
+ 6 · 172
+ 15 · 173 + 16 · 174 + 10 · 175
AGF63B(17) = 11 · 1 + 3 · 17 + 6 · 289 + 15 · 4.913 + 16 ·
83.521 + 10 · 1.419.857
AGF63B(17) = 11 +
51 + 1.734 + 73.695 + 1.336.336 + 14.198.570
AGF63B(17)
=
15.610.397(10)
Wartość liczby całkowitej | |
INSTRUKCJA:
Do pierwszego pola u góry wprowadź liczbę w systemie o podstawie p, ustaw tę podstawę na drugim polu i kliknij przycisk obliczania wartości. Wynik ukaże się w dolnym oknie tekstowym. Jeśli wprowadzona liczba nie będzie prawidłowa, to w oknie ukaże się odpowiedni komunikat. Cyferki literowe można wprowadzać jako duże lub małe znaki. |
|
JavaScript - (C)2002 Jerzy Wałaszek |
Podany schemat zapisu liczb pozwala na zapisywanie jedynie liczb całkowitych.
Aby umożliwić również zapis liczb ułamkowych, musimy rozszerzyć wagi pozycji w
stronę ujemnych potęg podstawy. Część ułamkową oddzielimy od części całkowitej
zapisu za pomocą znaku przecinka.
wagi | pn-1 | p2 | p1 | p0 | p-1 | p-2 | p-m | |||
cyfry | cn-1 | ... | c2 | c1 | c0 | , | c-1 | c-2 | ... | c-m |
n cyfr | m cyfr |
Wbrew pozorom obliczenie wartości tak zapisanej liczby wcale nie jest trudniejsze. Zasada nie zmienia się i musimy sumować kolejne iloczyny wartości cyfr przez wartości wag pozycji. Obliczenia rozpoczynamy od pierwszej pozycji po prawej stronie.
cn-1...c2c1c0,c-1c-2...c-m
= c-m·p-m
+ ... + c-2·p-2
+ c-1·p-1
+ c0·p0
+ c1·p1
+ c2·p2
+ ... + cn-1·pn-1
cn-1cn-2...c2c1c0 , c-1c-2...c-m= |
n-1 i = -m |
ci·pi |
Obliczyć wartość liczby stałoprzecinkowej 245,133
zapisanej w systemie pozycyjnym o podstawie p = 6.
245,133(6) =
3 · 6-3 + 3 · 6-2
+ 1
· 6-1 +
5 · 60 + 4 · 61
+ 2
· 62
245,133(6) =
3 · 1/216 + 3
· 1/36 + 1 · 1/6
+ 5
· 1+ 4 · 6 + 2 · 36
245,133(6) = 3/216 +
3/36 + 1/6 + 5 + 24 + 72
245,133(6) = 1/72 +
1/12 + 1/6 + 5 + 24 + 72
245,133(6) = (1 + 6 + 12)/72
+ 101
245,133(6) = 101 19/72
= 101,263888888888...(10)
Wartość liczby stałoprzecinkowej | |
INSTRUKCJA:
Do pierwszego pola u góry wprowadź liczbę stałoprzecinkową w systemie o podstawie p, Jako przecinka użyj znaku kropki,. Ustaw podstawę systemu na drugim polu i kliknij przycisk. Wynik ukaże się w dolnym oknie tekstowym. Jeśli wprowadzona liczba nie będzie prawidłowa, to w oknie ukaże się odpowiedni komunikat. Cyferki literowe można wprowadzać jako duże lub małe znaki. |
|
JavaScript - (C)2002 Jerzy Wałaszek |
Podany sposób obliczania wartości liczby zapisanej w dowolnym systemie pozycyjnym jest poprawny, lecz z punktu widzenia wykonywania obliczeń ma dosyć istotną wadę. Występują w nim potęgi podstawy. Działanie potęgowania jest czasochłonne - komputery dużo szybciej wykonują mnożenie i dodawanie. Zastanówmy się, czy nie można obliczyć wartości liczby bez odwoływania się do kolejnych potęg podstawy. W tym celu dokonamy prostych przekształceń podstawowego wzoru obliczeniowego.
Dla dowolnej podstawy p wartość liczby wyrażonej
n cyframi c
ze zbioru {0,1,...(p cyfr)} obliczamy jako:
cn-1cn-2cn-3...c2c1c0 = c0·p0 + c1·p1 + c2·p2 + ... + cn-3·pn-3 + cn-2·pn-2 + cn-1·pn-1
Ponieważ p0 = 1, a
p1 = p dla dowolnego
p, więc możemy zapisać:
cn-1cn-2cn-3...c2c1c0 = c0 + c1·p + c2·p2 + ... + cn-3·pn-3 + cn-2·pn-2 + cn-1·pn-1
Z iloczynów c1p, c2p2, ...,cn-1pn-1 wyciągamy przed nawias wspólny czynnik, czyli p
cn-1cn-2cn-3...c2c1c0
= c0 + p·(c1
+ c2·p + ... +
cn-3·pn-4 +
cn-2·pn-3 +
cn-1·pn-2)
Teraz podobnie postępujemy z iloczynami c2·p,...,cn-1·pn-2
cn-1cn-2cn-3...c2c1c0
= c0 +
p·(c1
+ p·(c2 + ... +
cn-3·pn-5 +
cn-2·pn-4 +
cn-1·pn-3))
Zwróćcie uwagę, iż po każdej takiej operacji maleje stopień pozostałego
wielomianu utworzonego z potęg podstawy p. Wyciąganie
wspólnego czynnika
p
kontynuujemy, aż do otrzymania wielomianu, w którym czynnik
p występuje tylko w pierwszej potędze.
cn-1cn-2cn-3...c2c1c0
= c0 + p·(c1
+ p·(c2 + ... +
p·(cn-3
+ p·(cn-2 +
cn-1·p))...))
Otrzymaliśmy nowy wzór, w którym nie występuje już potęgowanie. Nosi on nazwę
Schematu Hornera. Na jego podstawie można zaprojektować algorytm
obliczania wartości liczby w zapisie pozycyjnym o dowolnej podstawie. Algorytm
ten jest następujący:
Algorytm Hornera obliczania wartości liczby całkowitejn - liczba cyfr w zapisie pozycyjnym danej
liczby
|
Aby lepiej zrozumieć działanie tego algorytmu, przetestujmy go w praktyce. Załóżmy, że mamy czterocyfrową liczbę w systemie pozycyjnym o podstawie p.
Liczbę tę zapiszmy jako: c3c2c1c0, gdzie ci, i = 0,1,2,3 jest kolejną cyfrą systemu pozycyjnego o podstawie p. Wykonujemy kolejne obliczenia zgodne z podanym algorytmem Hornera:
w ← 0
w ← c3 + w · p, czyli w ← c3
w ← c2 + w · p, czyli w ←
c2 + c3·p
w ← c1 + w · p, czyli w ← c1
+
c2·p + c3·p2
w ← c0 + w · p, czyli w ←
c0 + c1·p +
c2·p2 +
c3·p3 i kończymy, ponieważ
użyliśmy wszystkich cyfr
W wyniku wykonania algorytmu Hornera otrzymaliśmy wzór potęgowy, ale w algorytmie nigdzie nie wykonywane było działanie potęgowania. Algorytm Hornera jest powszechnie stosowany w programach komputerowych do efektywnego obliczania wartości liczby w zapisie pozycyjnym.
Obliczyć przy pomocy algorytmu Hornera wartość liczby
742031 zapisanej w systemie pozycyjnym o podstawie
p=8.
w ← 0
w ← 7 + 0 · 8 = 7
w ← 4 + 7 · 8 = 60
w ← 2 + 60 · 8 = 482
w ← 0 + 482 · 8 = 3856
w ← 3 + 3856 · 8 = 30851
w ← 1 + 30851 · 8 = 246809 i kończymy, ponieważ
osiągnęliśmy ostatnią cyfrę
Obliczyć przy pomocy algorytmu Hornera wartość liczby 2210112 zapisanej w systemie pozycyjnym o podstawie p=3.
w ← 0
w ← 2 + 0 · 3 = 2
w ← 2 + 2 · 3 = 8
w ← 1 + 8 · 3 = 25
w ← 0 + 25 · 3 = 75
w ← 1 + 75 · 3 = 226
w ← 1 + 226 · 3 = 679
w ← 2 + 679 · 3 = 2039 i kończymy, gdyż osiągnęliśmy
już ostatnią cyfrę
Chociaż we wzorze formalnym i w algorytmie pojawia się numer pozycji cyfry (oznaczony jako i), to przykłady praktyczne pokazują nam, iż właściwie do poprawnego obliczenia wartości liczby musimy jedynie wiedzieć, że osiągnęliśmy ostatnią cyfrę. Ilość cyfr nie jest specjalnie istotna. Jest to bardzo miła cecha algorytmu Hornera, z której często będziemy korzystać przy programowaniu - cyfry mogą być kolejno podawane jako strumień danych, a program zlicza je aż do stwierdzenia końca strumienia.
Pierwsze podejście będzie polegało na oddzielnym obliczeniu wartości części całkowitej oraz części ułamkowej. Dla części całkowitej mamy podany już sposób postępowania. Zajmijmy się częścią ułamkową.
c-1c-2c-3...c-m+1c-m = c-1·p-1 + c-2·p-2 + c-3·p-3 + ... + c-m+1·p-m+1 + c-m·p-m
Postępujemy podobnie jak w poprzednim podrozdziale - wyciągamy przed nawias wspólny czynnik p-1. kolejno otrzymamy coraz prostsze wyrażenie w nawiasach. Operację tę kontynuujemy, aż do zredukowania wszystkich potęg podstawy mniejszych od -1.
,c-1c-2c-3...c-m+1c-m
= p-1·(c-1
+ c-2·p-1
+ c-3·p-2
+ ... + c-m+1·p-m+2
+ c-m·p-m+1)
,c-1c-2c-3...c-m+1c-m
= p-1·(c-1
+ p-1·(c-2
+ c-3·p-1
+ ... + c-m+1·p-m+3
+ c-m·p-m+2))
,c-1c-2c-3...c-m+1c-m
= p-1·(c-1
+ p-1·(c-2
+ p-1·(c-3
+ ... + c-m+1·p-m+4
+ c-m·p-m+3)))
,c-1c-2c-3...c-m+1c-m
= p-1·(c-1
+ p-1·(c-2
+ p-1·(c-3
+ ... + p-1·(c-m+1
+ c-m·p-1)...)))
Z otrzymanego wzoru wynika, iż obliczenia musimy rozpocząć od ostatniej cyfry, a więc odwrotnie niż dla części całkowitej. Reszta schematu jest podobna do poprzednio podanej wersji.
Algorytm Hornera obliczania wartości liczby stałoprzecinkowejm - liczba cyfr po przecinku w zapisie pozycyjnym danej liczbyp - podstawa systemu pozycyjnego, w którym jest zapisana liczba ci - cyfra stojąca na i-tej pozycji. Pozycja o numerze -m jest pierwszą pozycją od strony prawej. w - obliczana wartość liczby
|
Obliczyć przy pomocy algorytmu Hornera wartość liczby 237,745 zapisanej w systemie pozycyjnym o podstawie p=8.
Najpierw obliczamy wartość części całkowitej:
w ← 0
w ← 2 + 0 · 8 = 2
w ←
3 + 2 · 8 = 19
w ← 7 + 19 · 8 = 159
Teraz obliczamy część ułamkową:
w ← 0
w ← (5
+ 0) / 8 = 5/8
w ← (4
+ 5/8) / 8 = 37/64
w ← (7
+ 37/64) / 8 = 485/512
Czyli ostatecznie możemy zapisać: 237,745(8) = 159 485/512 = 159,947265625
Opisany powyżej sposób ma poważną wadę - musimy zmieniać kierunek przeglądania cyfr w zapisie liczby. Często kolejne cyfry otrzymujemy odczytując je z urządzenia wejściowego (np. klawiatury) i nie ma możliwości zmiany kierunku przeglądania. Dlatego zastosujemy inne podejście do problemu. Wielomian tworzący wartość liczby pomnóżmy przez wagę ostatniej pozycji, a następnie podzielmy przez tą wagę. Jeśli jakiekolwiek wyrażenie pomnożymy i podzielimy przez tą samą liczbę różną od zera, to wartość tego wyrażenia nie ulegnie zmianie.
cn-1...c0c-1...c-m = (cn-1·pn-1 + ... + c0·p0 + c-1·p-1 + ... + c-m·p-m)·p-m / p-m
Dzielenie przez p-m jest równoważne mnożeniu przez pm.
cn-1...c0c-1...c-m = (cn-1·pn-1 + ... + c0·p0 + c-1·p-1 + ... + c-m·p-m)·p-m·pm
Teraz wymnażamy wielomian w nawiasie przez pm i otrzymujemy:
cn-1...c0c-1...c-m = (cn-1·pn-1·pm + ... + c0·p0·pm + c-1·p-1·pm+ ... + c-m·p-m·pm)·p-m
Po uproszczeniu:
cn-1...c0c-1...c-m = (cn-1·pn-1+m + ... + c0·pm + c-1·p-1+m+ ... + c-m·p0)·p-m
Co otrzymaliśmy w nawiasie? Jest to wartość liczby całkowitej, której zapis zbudowany jest ze wszystkich cyfr liczby stałoprzecinkowej po pominięciu przecinka. Jak wynika ze wzoru wartość tę należy pomnożyć przez wagę ostatniej pozycji. W efekcie dochodzimy do wniosku, iż wartość liczby stałoprzecinkowej można obliczać algorytmem Hornera identycznie jak liczby całkowitej. Na końcu wynik należy pomnożyć przez wagę ostatniej pozycji. Jest to znaczne ułatwienie w stosunku do poprzedniego przykładu, ponieważ cyfry możemy kolejno pobierać. Zmodyfikowany algorytm Hornera będzie więc następujący:
Zmodyfikowany algorytm Hornera obliczania wartości liczby stałoprzecinkowejn - liczba cyfr w części całkowitejm - liczba cyfr w części ułamkowej p - podstawa systemu pozycyjnego, w którym jest zapisana liczba ci - cyfra stojąca na i-tej pozycji. Pozycja o numerze 0 jest pierwszą pozycją od strony prawej. w - obliczana wartość liczby
|
Obliczyć przy pomocy algorytmu Hornera wartość liczby 237,745 zapisanej w systemie pozycyjnym o podstawie p=8.
w ← 0
w ← 2 + 0 · 8 = 2
w ←
3 + 2 · 8 = 19
w ← 7 + 19 · 8 = 159
w ←
7 + 159 · 8 = 1279 (od tego momentu występują
cyfry części ułamkowej)
w ← 4 + 1279 · 8 =
10236
w ←
5 + 10236 · 8 = 81893 (ostatnia cyfra,
kończymy)
w ← 81893 × 1/512
= 159 485/512 = 159,947265625
Otrzymaliśmy identyczny wynik jak w poprzednim przykładzie, ale teraz nie musieliśmy rozbijać wątku obliczeniowego na dwie części - osobną dla części całkowitej i osobną dla części ułamkowej.
Nauczyliśmy się obliczyć wartość liczby zapisanej w dowolnym systemie pozycyjnym. Jak jednak znaleźć postać zapisu wartości liczby w dowolnym systemie pozycyjnym. Najpierw zdefiniujmy dokładnie problem:
Dana jest dowolna wartość całkowita w0. Szukamy jej przedstawienia w systemie pozycyjnym o podstawie p. Zapis tej liczby będzie się składał z ciągu cyfr systemu p. Nie wiemy jakie są to cyfry i ile ich jest, ale możemy zapisać je symbolicznie jako: cn-1cn-2...c2c1c0, gdzie n oznacza ilość tych cyfr. Skoro tak, to wartość w musi być równa:
w0 = cn-1·pn-1
+ cn-2·pn-2
+ ... + c2·p2
+ c1·p1
+ c0·p0, a po pominięciu w
zapisie p0 i przyjęciu p1 =
p
w0 =
cn-1·pn-1
+ cn-2·pn-2
+ ... + c2·p2
+ c1·p
+ c0
Teraz wykonamy dzielenie całkowite tego wielomianu przez wartość p. W wyniku otrzymamy nową wartość w1 równą:
w1 = w0 / p = cn-1·pn-1 / p + cn-2·pn-2 / p + ... + c2·p2 / p + c1·p / p + c0 / p
Ponieważ dla każdego systemu pozycyjnego wartość podstawy p jest o 1 większa od wartości największej cyfry, więc c0 nie dzieli się przez p i jest resztą z dzielenia. Pozostałe wyrazy dzielą się przez p i otrzymujemy nową wartość w1:
w1 = cn-1·pn-2 + cn-2·pn-3 + ... + c2·p + c1 i reszta z dzielenia całkowitego równa c0
Po pierwszym podzieleniu stopień wielomianu spadł o 1 oraz otrzymaliśmy jako resztę wartość ostatniej cyfry w systemie pozycyjnym o podstawie p. Kontynuujemy więc to samo postępowanie z nową wartością wielomianu w1:
w2 = w1
/ p = cn-1·pn-2
/ p + cn-2·pn-3
/ p + ... + c2·p
/
p + c1
/ p
w2 =
cn-1·pn-3
+ cn-2·pn-4
+ ... + c2·p
i reszta zdzielenia całkowitego równa c1
Mamy już drugą cyfrę. Kontynuujemy w identyczny sposób, aż w końcu otrzymamy wartość wn-1 = 0. Kolejne cyfry będą resztami z dzielenia przez p. Ujmijmy tę metodę w formę algorytmu:
Znajdowanie rozwinięcia liczby w systemie pozycyjnym o podstawie pw - wartość liczbyp - podstawa systemu pozycyjnego ci - cyfra na i-tej pozycji w systemie pozycyjnym o podstawie p
|
Przeliczyć wartość 12786 na system piątkowy.
w ← 12786 / 5 = 2557 i reszta 1
w ← 2557 / 5 = 511 i reszta 2
w ← 511 / 5 = 102 i reszta 1
w ← 102 / 5 = 20 i reszta 2
w ← 20 / 5 = 4 i reszta 0
w ← 4 / 5 = 0 i reszta 4
(koniec obliczeń, ponieważ otrzymaliśmy wartość 0)
12786(10) = 402121(5)
Przeliczyć wartość 86597 na system dwójkowy.
w ← 86597 / 2 = 43298 i reszta 1
w ← 43298 / 2 = 21649 i reszta 0
w ← 21649 / 2 = 10824 i reszta 1
w ← 10824 / 2 = 5412 i reszta 0
w ← 5412 / 2 = 2706 i reszta 0
w ← 2706 / 2 = 1353 i reszta 0
w ← 1353 / 2 = 676 i reszta 1
w ← 676 / 2 = 338 i reszta 0
w ← 338 / 2 = 169 i reszta 0
w ← 169 / 2 = 84 i reszta 1
w ← 84 / 2 = 42 i reszta 0
w ← 42 / 2 = 21 i reszta 0
w ← 21 / 2 = 10 i reszta 1
w ← 10 / 2 = 5 i reszta 0
w ← 5 / 2 = 2 i reszta 1
w ← 2 / 2 = 1 i reszta 0
w ← 1 / 2 = 0 i reszta 1
(koniec)
86597(10) = 10101001001000101(2)
Zapis liczby całkowitej w innym systemie pozycyjnym | |
INSTRUKCJA:
Do pierwszego pola u góry wprowadź nieujemną wartość całkowitą. Wybierz podstawę docelowego systemu pozycyjnego i kliknij przycisk konwersji. W dolnym polu zobaczysz zapis twojej wartości w wybranym systemie pozycyjnym. |
|
JavaScript - (C)2002 Jerzy Wałaszek |
Powyższe reguły pozwalają nam znaleźć rozwinięcie wartości całkowitej w dowolnym systemie pozycyjnym. Co jednak z wartościami niecałkowitymi? Tutaj musimy zastosować pewną umowę. Będziemy dokonywać rozwinięć z określoną ilością miejsc po przecinku. Założenie to jest ważne, ponieważ niektóre wartości mają nieskończone rozwinięcia w danym systemie pozycyjnym - np. rozwinięcie dziesiętne ułamka 1/3 jest liczbą okresową i nieskończoną 0,3333... Skorzystamy z następującej własności zapisu liczby w dowolnym systemie pozycyjnym:
Jeśli wartość w ma w danym systemie pozycyjnym o podstawie p rozwinięcie cn-1cn-2...c1c0, to pomnożenie tej wartości przez podstawę systemu p spowoduje w rozwinięciu przesunięcie wszystkich cyfr o jedną pozycję w lewo, czyli nowa wartość będzie mieć w tym systemie rozwinięcie cn-1cn-2...c1c00. Jeśli mnożenie wykonamy przez potęgę podstawy pm, m > 0, to cyfry przesuną się o m miejsc w lewo. |
Co z tego wynika? To proste. Przed wykonaniem rozwinięcia danej liczby mnożymy ją przez podstawę systemu docelowego podniesioną do potęgi równej liczbie miejsc po przecinku, które mają się znaleźć w rozwinięciu liczby. Następnie dokonujemy rozwinięcia części całkowitej nowej wartości wg starych zasad. W rozwinięciu odkładamy po przecinku odpowiednią ilość ostatnich cyfr.
Znaleźć rozwinięcie liczby 12 8/9 na system trójkowy z dokładnością do dwóch miejsc po przecinku.
w ← 12 8/9 · 32 =
12 8/9 · 9 = 116 (mnożymy przez
podstawę podniesioną do odpowiedniej potęgi)
w ← 116 / 3 = 38 i reszta 2
w ← 38 / 3 = 12 i reszta 2
w ← 12 / 3 = 4 i reszta 0
w ← 4 / 3 = 1 i reszta 1
w ← 1 / 3 = 0 i reszta 1
(koniec)
Otrzymaliśmy kolejne cyfry 11022. Dwie ostatnie cyfry umieszczamy po przecinku. Więc ostatecznie:
12 8/9 = 110,22(3)
Znaleźć rozwinięcie liczby 1/10 na system dwójkowy z dokładnością do 8 miejsc po przecinku.
w ←1/10 · 28 =
1/10
· 256 = 256/10 = 25 (zaokrąglamy do
wartości całkowitej)
w
←
25 / 2 = 12 i reszta 1
w ←12 / 2 = 6 i reszta 0
w ←6 / 2 = 3 i reszta 0
w ←3 / 2 = 1 i reszta 1
w ←1 / 2 = 0 i reszta 1
(koniec)
Otrzymaliśmy cyfry 11001. Jest ich za mało, więc dopisujemy na początku odpowiednią liczbę zer. Takie dopisanie zer nie zmienia wartości liczby.
1/10 = 0,00011001(2)
Zwróćcie uwagę na ciekawy fakt, iż w systemie dwójkowym rozwinięcie wartości 1/10 jest nieskończone (0,000110011001100110011...(2)). Skoro tak, to nie może być dokładnie przedstawione na dowolnej, skończonej liczbie miejsc po przecinku. Dlatego otrzymane przez nas rozwinięcie tej wartości nie jest dokładne (co można prosto sprawdzić obliczając wartość tej liczby dwójkowej, która wyniesie 25/256). Z tego powodu ułamki dziesiętne źle konwertują się na system dwójkowy, co powoduje błędy zaokrągleń przy obliczeniach numerycznych.
Zapis liczby stałoprzecinkowej w innym systemie pozycyjnym | |
INSTRUKCJA:
Do pierwszego pola u góry wprowadź nieujemną wartość stałoprzecinkową. Jako przecinka użyj znaku kropki. Wybierz podstawę docelowego systemu pozycyjnego oraz precyzję (liczbę miejsc po przecinku) i kliknij przycisk konwersji. W dolnym polu zobaczysz zapis twojej wartości w wybranym systemie pozycyjnym. |
|
JavaScript - (C)2002 Jerzy Wałaszek |
Z zapisem zmiennoprzecinkowym możesz spotkać się na lekcjach fizyki, gdzie przy jego pomocy przedstawia się albo bardzo duże wartości, albo bardzo małe. Zapis ten nazywa się często notacją naukową:
Gwiazda Proxima Centauri znajduje się w odległości 9460800000000 [km], czyli 9,4608 · 1012.
Masa elektronu wynosi me = 0,00000000000000000000000000091095 [g], czyli 9,1095 · 10-28 [g]
Liczba zapisana w systemie zmiennoprzecinkowym składa się z dwóch części: liczby stałoprzecinkowej, której wartość bezwzględna jest mniejsza od wartości podstawy systemu pozycyjnego oraz z podstawy podniesionej do pewnej potęgi zwanej wykładnikiem lub cechą. Wartość liczby jest równa iloczynowi części stałoprzecinkowej i wykładniczej:
w =
m ·
pe, m - mantysa, p - podstawa systemu, e - wykładnik potęgowy. |
Z poprzedniego rozdziału wiemy, iż pomnożenie wartości liczby przez podstawę systemu powoduje przesunięcie wszystkich jej cyfr o jedno miejsce w lewo. Podobnie podzielenie tej wartości przez podstawę powoduje przesunięcie wszystkich cyfr w prawo. Własność ta pozwala nam w prosty sposób przekształcać liczby z postaci stałoprzecinkowej na zmiennoprzecinkową. Działanie to wykonujemy dotąd, aż otrzymamy największą wartość stałoprzecinkową na moduł mniejszą od 1 (jest to tzw. postać znormalizowana liczby zmiennoprzecinkowej). Musimy jedynie pamiętać iż podstawę i potęgę również zapisujemy w tym samym systemie pozycyjnym, co część stałoprzecinkową. Zatem zapis:
3,21 · 1012(4)
nie oznacza mnożenia części ułamkowej przez 1012 (1.000.000.000.000), jak myślą uczniowie, lecz przez 46 (4096). A to jest przecież bardzo istotna różnica!!!
Przedstawić liczbę 5420000000(8) w ósemkowej notacji zmiennoprzecinkowej.
5420000000(8) =
5420000000(8) · 100(8)
5420000000(8) =
542000000(8) · 101(8)
- przesuwamy cyfry w prawo i dodajemy 1 do wykładnika
5420000000(8) =
54200000(8) · 102(8)
5420000000(8) =
5420000(8) · 103(8)
5420000000(8) =
542000(8) · 104(8)
5420000000(8) =
54200(8) · 105(8)
5420000000(8) =
5420(8) · 106(8)
5420000000(8) =
542(8) · 107(8)
5420000000(8) =
54,2(8) ·
1010(8)
5420000000(8) =
5,42(8) ·
1011(8)
5420000000(8) =
0,542(8) · 1012(8) -
kończymy, gdyż osiągnęliśmy postać znormalizowaną
Przedstawić liczbę 0,00000FD56(16)
w szesnastkowej notacji zmiennoprzecinkowej.
0,00000FD56(16)
= 0,00000FD56(16) ·
100(16)
0,00000FD56(16)
= 0,0000FD56(16) ·
101(16)
0,00000FD56(16)
= 0,000FD56(16) ·
102(16)
0,00000FD56(16)
= 0,00FD56(16) ·
103(16)
0,00000FD56(16)
= 0,0FD56(16) ·
104(16)
0,00000FD56(16)
= 0,FD56(16) ·
105(16) - kończymy na
wartości znormalizowanej
Z przedstawionych przykładów wynika prosta reguła przekształcania postaci stałoprzecinkowej na zmiennoprzecinkową:
Zamiana zapisu stałoprzecinkowego na zmiennoprzecinkowy:Przypadek 1Liczba stałoprzecinkowa na moduł większa od zera.
Oznaczmy przez
n ilość cyfr części całkowitej. Wtedy
przecinek w zapisie stałoprzecinkowym przesuwamy o
n
pozycji w lewo. Wykładnik potęgowy jest równy
12,57 = 0,1257
· 102, e
= 2,
21211,2(3) =
0,212112(3) ·
1012(3),
n = 5, e = 12(3)
= 5 Przypadek 2Liczba stałoprzecinkowa na moduł jest mniejsza od zera. Oznaczmy przez n ilość zer po przecinku. Przecinek przesuwamy o n pozycji w prawo. Wykładnik potęgowy równy jest e = -n: 0,000046 = 0,46 · 10-4, n = 4 0,00000000763(8) =
0,763(8) ·
10-10(8),
n = 8, e = -10(8)
= -8 |
Obliczenie wartości liczby zmiennoprzecinkowej zapisanej w danym systemie pozycyjnym o podstawie p sprowadza się do obliczenia wartości części stałoprzecinkowej m oraz wartości wykładnika e. Następnie stosujemy wzór na wartość liczby zmiennoprzecinkowej w = m · pe.
Obliczyć wartość liczby zmiennoprzecinkowej 0,111(2) · 10111(2).
m = 0,111(2) = 1/2 + 1/4 + 1/8 = 7/8
e = 111(2) = 4 + 2 + 1 = 7
p = 10(2) = 2(10)
więc
w = m · pe = 7/8 · 27 = 7/8 · 128 = 896/8 = 112(10)
0,111(2) · 10111(2) = 112(10)
Jeśli dobrnąłeś do tego miejsca, to reszta materiału będzie już dla ciebie zupełnie prosta. System dwójkowy ma dla nas specjalne znaczenie, ponieważ jest podstawą wszystkich obliczeń wykonywanych przez komputer.
Cechy charakterystyczne dwójkowego systemu pozycyjnego, to:
p = 2, zbiór cyfr c - {0,1}
Wartość liczby całkowitej w zapisie dwójkowym obliczamy według wzoru podstawowego:
n - liczba cyfr, które w systemie dwójkowym będziemy nazywali bitami
cn-1cn-1...c2c1c0 = c0·20 + c1·21 + c2·22 + ... + cn-2·2n-2 + cn-1·2n-1 = | n-1 i = 0 |
ci·2i |
lub poznanym wcześniej algorytmem Hornera.
Obliczyć wartość liczby dwójkowej 110111(2) za pomocą wzoru potęgowego i algorytmu Hornera.
1. Wzór potęgowy.
p = 2, c - {0,1}
110111(2) =
1 × 20 + 1 × 21
+ 1
× 22 +
0 × 23 + 1 × 24
+ 1
× 2 5
110111(2) = 1 × 1 +
1 × 2 + 1 × 4 +
0 × 8 + 1 × 16 +
1 × 32
110111(2) = 1
+ 2 + 4 + 16 + 32
110111(2) = 55(10)
2. Algorytm Hornera
w ← 0
w ← 1
+ 0 · 2 = 1
w
← 1 + 1 · 2 = 3
w ← 0 + 3 · 2 = 6
w
← 1 + 6 · 2 = 13
w ← 1 + 13 · 2 = 27
w
← 1 + 27 · 2 = 55 (koniec, wyczerpano
wszystkie cyfry)
110111(2) = 55(10)
Zastanówmy się teraz jaki jest zakres wartości dla n bitów. Najmniejszą liczbą będzie oczywiście 0. Największa liczba posiada wszystkie cyfry maksymalne, więc w systemie dwójkowym będą to cyfry 1.
minn-bitów = 0
maxn-bitów = 1 · 20 + 1 · 21
+ 1 · 22 + ... + 1 · 2n-2 + 1 · 2n-1
maxn-bitów = 1 + 2 + 4 + ... + 2n-2
+ 2n-1
Zwróćcie uwagę, iż suma dowolnej ilości początkowych składników tego szeregu jest o 1 mniejsza od wyrazu następnego:
1 = 2 - 1
1 +
2 = 4 - 1
1 +
2 +
4 = 8 - 1
...
1 +
2 +
4 + ... + 2n-2
= 2n-1 - 1
1 +
2 +
4 + ... + 2n-2
+ 2n-1 = 2n - 1 =
maxn-bitów
Zapamiętaj!Na n bitach można zapisać w naturalnym kodzie binarnym liczby z przedziału: (0, 2n - 1) |
Kolejnym zagadnieniem są dwójkowe liczby stałoprzecinkowe. Zapis ten omówiliśmy już wcześniej dla przypadku ogólnego. Wartość liczby stałoprzecinkowej o n bitach całkowitych i m bitach po przecinku możemy obliczyć tradycyjnie wzorem potęgowym:
cn-1...c1c0 , c-1c-2...c-m = c-m·2-m + ...+ c-2·2-2 + c-1·2-1 + c0·20 + c1·21 + ...+ cn-1·2n-1 = | n-1 i = -m |
ci·2i |
lub przy pomocy algorytmu Hornera dla liczb stałoprzecinkowych.
Obliczyć wartość liczby dwójkowej 11101,011(2) za pomocą wzoru potęgowego i algorytmu Hornera.
1. Wzór potęgowy
11101,011(2) =
1 · 2-3 + 1 · 2-2
+ 0
· 2-1 +
1 · 20 + 0 · 21
+ 1
· 22 +
1 · 23 + 1 · 24
11101,011(2) =
1 · 1/8 +
1 · 1/4 +
0 · 1/2 +
1 · 1 + 0 · 2 +
1 · 4 + 1 · 8 +
1 · 16
11101,011(2)
=
1/8
+ 1/4 + 1 + 4 + 8 + 16
11101,011(2)
= 29
3/8
2. Algorytm Hornera
w ← 0
w ← 1
+ 0 · 2 = 1
w
← 1 + 1 · 2 = 3
w ← 1 + 3 · 2 = 7
w
← 0 + 7 · 2 = 14
w ← 1 + 14 · 2 = 29,
(tutaj kończy się część całkowita)
w
← 0 + 29 · 2 = 58
w ← 1 + 58 · 2 = 117
w
← 1 + 117 · 2 = 235 (koniec części
ułamkowej)
w ← 235 · 2-3 = 235/8 =
29 3/8
(wynik mnożymy przez wagę ostatniej cyfry)
11101,011(2) = 29 3/8
Problem jest następujący: mamy do dyspozycji n bitów dla części całkowitej oraz m bitów dla części ułamkowej. Jaki jest zakres liczb, które można przedstawić za pomocą wymienionych bitów w dwójkowym zapisie stałoprzecinkowym. Dzielimy liczbę stałoprzecinkową na dwie części: część całkowitą oraz część ułamkową:
liczba stałoprzecinkowa = część całkowita + część ułamkowa. |
Najmniejszą liczbą jest oczywiście 0 (wszystkie bity mają wartość 0). Największa liczba powstanie wtedy, gdy zarówno część całkowita jak i ułamkowa będą największe. Czyli:
minn,m - bitów = 0
minn,m - bitów = mincałkowita + minułamkowa
Maksymalną wartość dla części całkowitej wyprowadziliśmy w poprzednim podrozdziale:
maxcałkowita = 2n-1
Teraz zajmiemy się częścią ułamkową. Część ta przyjmie największą wartość, gdy wszystkie cyfry będą maksymalne, czyli będą wynosić 1. Rozpiszmy wzór na wartość części ułamkowej:
maxułamkowa = 1 · 2-1
+ 1 · 2-2 + 1 · 23 + ... + 1 · 2 -m
maxułamkowa = 1/2
+ 1/4 + 1/8 + ... + 1/2-m
Możemy zauważyć iż suma dowolnej liczby początkowych wyrazów tego ciągu jest równa 1 - ostatni wyraz tego ciągu:
1/2 = 1 - 1/2
1/2
+
1/4 = 3/4 = 1 - 1/4
= 3/4
1/2 + 1/4
+
1/8
= 1 - 1/8 = 7/8
1/2
+
1/4 + 1/8 + ... + 1/2m
= 1 - 1/2m = (2m - 1) / 2m
= maxułamkowa
Wiec ostatecznie:
maxn,m bitów = maxcałkowita + maxułamkowa= 2n - 1 + (2m - 1) / 2m
Zapamiętaj!Na n bitach całkowitych i m bitach ułamkowych można zapisać w binarnym kodzie stałoprzecinkowym liczby z przedziału: (0, 2n - 1 + (2m - 1)/2m) |
Dotychczas omawialiśmy jedynie postać liczb w różnych systemach pozycyjnych. Nie mówiliśmy nic na temat zasad wykonywania na tych liczbach działań arytmetycznych. W zasadzie działania te nie różnią się niczym od wyuczonego przez nas schematu obliczeń - we wszystkich systemach pozycyjnych rachunki wykonuje się podobnie. Jeśli chcemy wykonywać w danym systemie pozycyjnym dodawanie, to najpierw musimy wyuczyć się tabliczki dodawania. Dla systemu dziesiętnego tabliczka ta składa się ze stu pozycji - każda cyfra z każdą. Na pewno śniła wam się po nocach w czasie nauki arytmetyki w szkole podstawowej. W systemie dwójkowym na szczęście mamy tylko dwie cyfry, więc tabliczka dodawania jest zupełnie prosta:
Tabliczka dodawania |
0 + 0 = 0 |
0 + 1 = 1 |
1 + 0 = 1 |
1 + 1 = 10 |
Mając tabliczkę dodawania możemy przystąpić do wykonywania rachunków:
0101= 5(10) + 0110= 6(10) 1011=11(10) |
1100=12(10) + 0011= 3(10) 1111=15(10) |
1010=10(10) + 1010=10(10) 10100=20(10) |
1111=15(10) + 0001= 1(10) 10000=16(10) |
Przy dodawaniu 1 + 1 występuje tzw. przeniesienie do następnej kolumny - w bieżącej kolumnie zapisujemy 0, a 1 dodajemy w następnej kolumnie. Identycznie postępujemy przy dodawaniu w naszym systemie dziesiętnym.
Wbrew pozorom mnożenie liczb dwójkowych jest bardzo proste - nawet dużo prostsze niż w naszym systemie dziesiętnym. Najpierw musimy nauczyć się tabliczki mnożenia:
Tabliczka mnożenia |
0 · 0 = 0 |
0 · 1 = 0 |
1 · 0 = 0 |
1 · 1 = 1 |
Zasady mnożenia binarnego są identyczne z zasadami w systemie dziesiętnym. Wymnażamy przez siebie kolejne cyfry mnożnej i mnożnika, a iloczyny częściowe dodajemy.
0101 = 5(10) · 0110 = 6(10) 0000 0101 0101 + 0000 0011110 = 30(10) |
W mnożeniu uczestniczą tylko cyfry 1. Dla cyfry 0 wynik jest zerowy i można go pominąć. Wynika stąd bardzo prosta zasada dla systemu binarnego: przeglądamy od strony prawej kolejne cyfry mnożnika. Gdy natrafimy na 1, to przepisujemy na dole cyfry mnożnej przesunięte na kolumnę mnożącej cyfry. Przypadek ten zaznaczyliśmy na słupku mnożenia.
Przyglądając się liczbom binarnym bardzo łatwo zauważyć fakt, iż dla ludzi są one mało czytelne. Nasz mózg lubi różnorodność i w gąszczu zer oraz jedynek bardzo łatwo nam się pogubić. Programiści, którzy muszą operować bitami (np. przy programowaniu różnych portów I/O) wymyślili na to lekarstwo - zamiast zapisywać liczby w systemie dwójkowym zapisują je w systemie ósemkowym lub szesnastkowym. Na pierwszy rzut oka wydaje się to dziwne. Ale zobaczymy zaraz, iż ma sens i w sumie jest dosyć proste.
Podstawa systemu ósemkowego i szesnastkowego jest potęgą podstawy systemu binarnego. Konwersja pomiędzy systemami pozycyjnymi, które mają tę własność jest bardzo prosta.
cyfry ósemkowe | |
cyfra | wartość |
0 | 000(2) |
1 | 001(2) |
2 | 010(2) |
3 | 011(2) |
4 | 100(2) |
5 | 101(2) |
6 | 110(2) |
7 | 111(2) |
Mamy liczbę binarną 110101111011010101011101(2) i chcemy zapisać ją w systemie ósemkowym. Najpierw zbudujemy tablicę przeliczeń cyfr ósemkowych na ich wartość w systemie dwójkowym. Każdej cyfrze ósemkowej będą odpowiadały trzy cyfry dwójkowe. Następnie dzielimy liczbę dwójkową na grupy po trzy cyfry dwójkowe. Dzielenie rozpoczynamy od strony prawej:
110 101 111 011 010 101 011 101(2)
Każdą grupę trzech cyfr binarnych zastępujemy jedną cyfrą ósemkową zgodnie z tabelką wartości cyfr:
110 ↓ 6 |
101 ↓ 5 |
111 ↓ 7 |
011 ↓ 3 |
010 ↓ 2 |
101 ↓ 5 |
011 ↓ 3 |
101 ↓ 5 |
Otrzymana liczba jest zapisem danej liczby binarnej w systemie ósemkowym, czyli:
110101111011010101011101(2) = 65732535(8)
Zapis ósemkowy jest dla nas bardziej czytelny - przypomina nam nasz własny system i zmniejsza możliwość popełnienia błędu przy zapisie (przecież bardzo łatwo zgubić w systemie dwójkowym jedno zero lub jedynkę). I o to chodzi.
W drugą stronę postępujemy odwrotnie. Jeśli mamy daną liczbę ósemkową, np. 752401(8), to każdą jej cyfrę zastępujemy grupą trzech cyfr dwójkowych z tabelki. Grupy te łączymy ze sobą i otrzymujemy w wyniku zapis dwójkowy tej samej wartości.
7 ↓ 111 |
5 ↓ 101 |
2 ↓ 010 |
4 ↓ 100 |
0 ↓ 000 |
1 ↓ 001 |
752401(8) = 111101010100000001(2)
cyfry szesnastkowe | |||
cyfra | wartość | cyfra | wartość |
0 | 0000(2) | 8 | 1000(2) |
1 | 0001(2) | 9 | 1001(2) |
2 | 0010(2) | A | 1010(2) |
3 | 0011(2) | B | 1011(2) |
4 | 0100(2) | C | 1100(2) |
5 | 0101(2) | D | 1101(2) |
6 | 0110(2) | E | 1110(2) |
7 | 0111(2) | F | 1111(2) |
Drugim często używanym systemem pozycyjnym przy operowaniu na wartościach dwójkowych jest system szesnastkowy. Przy konwersji postępujemy identycznie jak w poprzednim przypadku, tylko teraz jedna cyfra szesnastkowa zastępuje grupę 4 cyfr dwójkowych. Zamieńmy na system szesnastkowy tę samą liczbę dwójkową, co poprzednim razem:
1101 0111 1011 0101 0101 1101(2)
1101 ↓ D |
0111 ↓ 7 |
1011 ↓ B |
0101 ↓ 5 |
0101 ↓ 5 |
1101 ↓ D |
110101111011010101011101(2) = D7B55D(16)
I odwrotnie, zamieńmy liczbę szesnastkową A68F27(16) na binarną:
A ↓ 1010 |
6 ↓ 0110 |
8 ↓ 1000 |
F ↓ 1111 |
2 ↓ 0010 |
7 ↓ 0111 |
Czyli A68F27(16) = 101001101000111100100111(2)
Dotychczas opisany sposób kodowania dwójkowego umożliwia przedstawianie liczb dodatnich i zera. Z drugiej strony wiemy, jak ważne w zastosowaniach są liczby ujemne. W systemie dziesiętnym sprawę rozwiązaliśmy przez wprowadzenie znaku przed zapisem cyfr liczby. Jeśli liczby chcemy przetwarzać za pomocą komputera, to mamy do dyspozycji jedynie bity o wartościach 0 lub 1. Bity mogą kodować cyfry dwójkowe, ale brakuje tutaj wartości dla znaku '+' lub '-'. Jak więc rozwiązano ten problem? Niestety musimy odejść nieco od naturalnego systemu dwójkowego i wprowadzić kilka dodatkowych ustaleń.
Istnieją dwa główne sposoby kodowania liczb ze znakiem - kod ZNAK-MODUŁ, kod U2.
W systemie tym stosujemy bardzo prostą metodę kodowania liczb ze znakiem. Najstarszy bit liczby jest bitem znaku. Reszta bitów określa wartość bezwzględną (moduł) liczby: Jeśli przyjmiemy do zapisu liczb format całkowity n-bitowy, to liczby w kodzie znak-moduł mają następującą postać:
cn-1 | cn-2cn-3...c2c1c0 |
znak | moduł |
Wartość n-bitowej, całkowitej liczby w dwójkowym kodzie znak-moduł obliczamy wg wzoru:
cn-1cn-2cn-3...c2c1c0 = (1 - 2 · cn-1) × | n-2 i = 0 |
ci·2i |
Wyrażenie (1 - 2 · bit znaku) przyjmuje odpowiednio wartość 1, gdy bit znaku jest równy 0, a -1, gdy bit znaku ma wartość 1, czyli określa liczbę ujemną. W dalszej części wzoru mamy obliczanie wartości pozostałych bitów, czyli modułu. Moduł jest przemnażany przez wyrażenie znakowe i w efekcie otrzymujemy wartość dodatnią lub ujemną w zależności od stanu bitu znaku.
n = 4 bity
0110(z-m)
= (1 - 2 · 0) · (0
· 20 + 1 · 21 +
1 · 22)
0110(z-m)
= (1 - 2 · 0) · (0
· 1 + 1 · 2 + 1
· 4)
0110(z-m)
= 1 · ( 2 + 4)
0110(z-m)
= 6(10)
1011(z-m)
= (1 - 2 · 1) · (1
· 20 + 1 · 21 +
0 · 22)
1011(z-m)
= (1 - 2 · 1) · (1
· 1 + 1 · 2 + 0
· 4)
1011(z-m)
= -1 · (1 + 2)
1011(z-m)
= -3(10)
Jeśli chcemy daną wartość przedstawić w dwójkowym kodzie znak-moduł, to najpierw znajdujemy przedstawienie dwójkowe modułu tej wartości, następnie uzupełniamy bity do zadanego formatu i dodajemy bit znaku 0 dla wartości dodatniej lub 1 dla ujemnej.
Przedstawić wartość -69 w 8-bitowym kodzie znak-moduł.
1. Znajdujemy przedstawienie dwójkowe modułu
w ← 69 / 2 = 34 i reszta 1
w
← 34 /2 = 17 i reszta
0
w
← 17 / 2 = 8 i reszta
1
w
← 8 / 2 = 4 i reszta 0
w
← 4 / 2 = 2 i reszta
0
w
← 2 / 2 = 1 i reszta
0
w
← 1 / 2 = 0 i reszta
1
69(10) = 1000101(2)
2. Otrzymaną liczbę dwójkową uzupełniamy bitem znaku i otrzymujemy:
-69(10) = 11000101(z-m)
Teraz sprawdzimy, jak zachowują się liczby w kodzie znak-moduł przy wykonywaniu dodawania. Dodajmy do siebie dwie 4-bitowe liczby w tym kodzie o wartości 3 i -3.
0011(z-m) = 3(10) + 1011(z-m) = -3(10) 1110(z-m) = -6(10) |
Otrzymany przez nas wynik jest oczywiście błędny. Oznacza to, iż nie możemy w zwykły sposób dodawać dowolnych liczb zapisanych w tym kodzie. Stanowi to poważne utrudnienie w obliczeniach komputerowych. Dlatego zastosowanie kodu znak-moduł jest ograniczone.
Zakres liczb Z-M wynika bezpośrednio ze wzoru obliczeniowego. Wartość maksymalną otrzymamy przy znaku dodatnim i maksymalnym module. Wartość minimalną otrzymamy przy znaku ujemnym i również maksymalnym module. Ponieważ moduł jest o jeden bit mniejszy niż wynosi długość liczby Z-M, to
maxZ-M = 2n-1 - 1, minZ-M = -2n-1 + 1 |
Np. dla n = 8 mamy:
maxZ-M 8b = 28-1 - 1 = 27
- 1 = 128 - 1 = 127
minZ-M 8b = -28-1
+ 1 = -27 + 1 = -128 + 1 = -127
Zwróćcie uwagę, iż w kodzie Z-M można na dwa sposoby zapisać wartość 0, raz z bitem znaku 0, i raz z bitem znaku 1, np. dla n=4:
0000Z-M = 0 (zero
dodatnie)
1000Z-M = 0 (zero ujemne,
ale też zero)
Jest to nieefektywność kodu Z-M, ponieważ tracimy jeden wyraz kodowy, co zmniejsza ilość możliwych do zawarcia w tym kodzie informacji (tzn. możemy zakodować mniej liczb).
Wniosek z rozdziału o liczbach w kodzie Z-M jest pesymistyczny. Wymyśliliśmy sposób kodowania liczb ze znakiem, który jednak sprawia kłopoty przy obliczeniach. Nie może być inaczej, ponieważ bit znaku jest sztucznie dołączony do reszty bitów tworzących wartość liczby. Zachodzi więc pytanie, czy można opracować kodowanie liczb ze znakiem o takiej własności, iż wykonywanie podstawowych działań arytmetycznych na liczbach w tym kodzie prowadzi do poprawnych wyników. Okazuje się, że tak. Kod ten nazwano Kodem Uzupełnień do 2 (lub Uzupełnień do Podstawy), w skrócie U2. Budowa liczby w kodzie U2 jest podobna do kodu znak-moduł. Jednak teraz pozycja znakowa (najstarszy bit) posiada swoją wagę i uczestniczy w wartości liczby jak każda inna pozycja.
Waga pozycji znakowej jest ujemna:
-2n-1 cn-1 |
2n-22n-3...222120 cn-2cn-3...c2c1c0 |
znak | moduł |
Wartość n-bitowej liczby zapisanej w kodzie U2 obliczamy w standardowy sposób: sumując kolejne iloczyny cyfr przez wagi pozycji.
cn-1cn-2cn-3...c2c1c0 = cn-1(-2n-1) + | n-2 i = 0 |
ci2i |
n = 4 bity
0110(U2)
= 0 · (-23) +
0 · 20 +
1 · 21 + 1 · 22
0110(U2)
= 0 · (-8) + 0
· 1 + 1 · 2 + 1
· 4
0110(U2)
= 2 + 4
0110(U2)
= 6(10)
1110(U2)
= 1 · (-23) +
0 · 20 +
1 · 21 + 1 · 22
1110(U2)
= 1 · (-8) + 0
· 1 + 1 · 2 + 1
· 4
1110(U2)
= -8 + 2 + 4
1110(U2)
= -2
Proszę zwrócić uwagę na istotną różnicę w stosunku do kodu Z-M. Liczby ujemne wyglądają inaczej niż poprzednio. Jak więc kodować liczby w kodzie U2?. Musimy rozpatrzyć dwa przypadki:
3(10) = 11(2)
Ponieważ format ma 4 bity, to dodajemy na początku dwie cyfry 0 i
otrzymujemy liczbę dodatnią w kodzie U2:
3(10) = 0011(U2)
-8 +
5 = -3
1101(U2)
= -3(10)
Możemy również znaleźć przedstawienie modułu tej liczby, a następnie wyliczyć wartość przeciwną w kodzie U2 wg przepisu:
Aby znaleźć wartość przeciwną w kodzie U2 należy wykonać następujące czynności:
|
Czyli w naszym przykładzie najpierw znajdujemy zapis dwójkowy liczby 3:
3(10) = 11(2)
Następnie uzupełniamy cyfry do 4 bitów:
3(10) = 0011(U2)
Teraz postępujemy zgodnie z opisaną metodą: zamieniamy bity na przeciwne i dodajemy 1
0011(U2) = 3(10) 1100 + 0001 1101(2) = -3(10)
Otrzymaliśmy identyczną liczbę, jak poprzednio.
Sprawdźmy teraz jak zachowuje się kodowanie U2 w działaniach arytmetycznych. Dodajmy do siebie liczby 3 i -3 zapisane w kodzie U2:
0011(U2) = 3(10) + 1101(U2) = -3(10) 10000(U2) = 0(10) - przeniesienie poza najstarszy bit ignorujemy
Otrzymaliśmy poprawny wynik po zignorowaniu przeniesienia poza bit znaku. Można wykazać, iż dodawanie dowolnych liczb w kodzie U2 daje poprawny wynik zawsze wtedy, gdy mieści się on w zakresie liczb dla danego formatu.
Największą wartość otrzymamy, gdy bit znaku ma stan 0, a reszta bitów liczby ma stan 1. Ponieważ dla n-bitowego formatu U2 bitych o wartości 1 jest n-1, to
maxU2 n-bitów = 2n-1 - 1 |
A więc tyle samo co w kodzie Z-M. Najmniejszą wartość ujemną otrzymamy, gdy bit znaku przyjmie stan 1, a reszta bitów będzie miała stan 0. Wynika z tego, iż najmniejszą wartością liczby w kodzie U2 jest waga pozycji znakowej.
minU2 n-bitów = -2n-1 |
Dla n = 8 otrzymamy odpowiednio:
maxU2 8b = 28-1 - 1 = 27
- 1 = 128 - 1 = 127
minU2 8b = -28-1
= -27
= -128
Zwróćcie uwagę, iż górna i dolna granica liczb są niesymetryczne. W kodzie U2 każda kombinacja kodowa odpowiada dokładnie jednej liczbie - zero nie powtarza się, jak w kodzie Z-M. Jest to więc kod efektywny.
Przyjmijmy następujące ustalenia. Dwójkowa liczba zmiennoprzecinkowa zbudowana jest z dwóch części: z mantysy m i wykładnika potęgowego e (zwanego również cechą). Ponieważ podstawa systemu liczenia jest znana i wynosi 2, więc nie ma potrzeby umieszczać jej w zapisie liczby. Mantysa m jest liczbą stałoprzecinkową na moduł mniejszą od 1. Wykładnik e jest liczbą całkowitą. Obie części mogą być zapisane np. w kodzie U2 lub kodzie Z-M.
wykładnik e | mantysa m |
n-bitów | m-bitów |
liczba zmiennoprzecinkowa |
Wartość liczby liczymy wg poznanego wcześniej wzoru:
w = m · 2e
Określmy teraz sposób obliczania wartości mantysy oraz wykładnika, gdy mamy dany ich zapis w kodzie U2. Niech wykładnik zbudowany będzie z n bitów. Ponieważ jest to liczba całkowita, więc jej wartość obliczamy w poznany wcześniej sposób:
e = cn-1cn-2cn-3...c2c1c0 = cn-1(-2n-1) + | n-2 i = 0 |
ci·2i |
Dla przykładowego, 4-bitowego wykładnika wzór ten będzie następujący:
e
=
c3c2c1c0
= c3·(-23)
+ c2·22 +
c1·21
+ c0·20
e =
c3c2c1c0
= c3 ·
-8
+ c2 · 4 +
c1 · 2 + c0
Mantysa ma być ułamkiem mniejszym na moduł od 1. Jeśli jest zbudowana z m bitów, to waga najstarszego bitu wynosi w kodzie U2 -20, czyli -1. Następna pozycja ma wagę 2-1, czyli 1/2, itd. Rozpiszmy to następująco:
m = cn-1 , cn-2cn-3...c2c1c0 = cn-1·(-20) + cn-2·2-1 + cn-3·2-2 + ... + c2·2-n+3 + c1·2-n+2 + c0·2-n+1
Dla przykładowej, 4-bitowej mantysy wzór ten przyjmie następującą postać:
m =
c3 , c2c1c0
= c3·(-20)
+ c2·2-1 +
c1·2-2
+ c0·2-3
m = c3
, c2c1c0
= c3 · (-1)+
c2
· 1/2
+ c1 · 1/4 +
c0 · 1/8
m =
c3
, c2c1c0
= - c3
+ c2 / 2 +
c1
/ 4 + c0 / 8
Rozważmy teraz kilka przykładowych, 8-bitowych liczb zmiennoprzecinkowych, w których wykładnik i mantysa mają po 4 bity.
00110111(ZP) = ...?(10)
Najpierw wydobywamy z liczby wykładnik e i mantysę m:
0011 e |
0111 m |
Teraz obliczamy kolejno wartość wykładnika i mantysy:
e = 0011(U2)
= 0 · (-8) + 0
· 4 + 1 · 2 + 1
· 1
e = 0011(U2)
= 2 + 1
e =
0011(U2)
= 3(10)
m = 0,111(U2)
= - 0 + 1/2 + 1/4 + 1/8
m = 0,111(U2)
= 1/2 + 1/4 + 1/8
m = 0,111(U2)
= 4/8 + 2/8 + 1/8
m = 0,111(U2)
= 7/8
Mając wykładnik i mantysę mogę podstawić je do wzoru i obliczyć wartość liczby:
w = m · 2e
w =
7/8 · 23
w =
7/8 ·
8
w = 7, więc
ostatecznie:
00110111(ZP) = 7(10)
Mamy określony format zapisu liczby zmiennoprzecinkowej w systemie dwójkowym. Wiemy, że wykładnik ma zawierać n - bitów w kodzie U2, a cecha m bitów w zapisie stałoprzecinkowym U2. Znajdowanie reprezentacji liczby w zapisie zmiennoprzecinkowym przedstawimy na przykładzie prostego systemu zmiennoprzecinkowego, w którym wykładnik i cecha mają po 4 bity długości. Przykładową liczbą niech będzie wartość 56.
Znajdujemy przedstawienie stałopozycyjne danej wartości w systemie U2. Na razie nie jest istotna liczba bitów wynikowych.
w ← 56 / 2 = 28 i reszta 0
w ← 28 / 2 = 14 i reszta 0
w ← 14 / 2 = 7 i reszta 0
w ← 7 / 2 = 3 i reszta 1
w ← 3 / 2 = 1 i reszta 1
w ← 1 / 2 = 0 i reszta 1
56(10) = 111000(2) = 0111000(U2) - dodajemy zero, aby zaznaczyć, iż jest to liczba dodatnia.
Zapiszemy wzór obliczeniowy, a następnie będziemy przesuwać w prawo cyfry mantysy dodając jednocześnie 1 do wykładnika, aż znacząca jedynka znajdzie się na pozycji o wadze 1/2.
0111000,000(U2)
= 011100,000(U2) = 01110,000(U2) = 0111,000(U2) = 011,100(U2) = 01,110(U2) = 0,111(U2) = |
100000(U2) - pamiętaj, iż
podstawa 2 jest zapisana jako 10! 100001(U2) - przesuwamy cyfry mantysy w prawo, zwiększamy wykładnik 100010(U2) 100011(U2) 100100(U2) 100101(U2) 100110(U2) - kończymy, mantysa jest znormalizowana |
Otrzymujemy więc:
w =
0110 = 6(10) m = 0,111 = 7/8 |
,sprawdzamy: 7/8 · 26 = 448/8 = 56 |
Jeśli połączymy te składniki w jeden kod, to otrzymamy postać wynikową w naszym przykładowym, dwójkowym systemie zmiennoprzecinkowym:
56(10) = 01100111(ZP) - kolorem zaznaczyliśmy wykładnik i mantysę
Dwójkowy kod zmiennoprzecinkowy nie jest kodem dokładnym. Niektórych liczb nie da się w nim przedstawić. Otrzymamy jedynie pewne przybliżenie. Aby zilustrować wam ten problem, spróbujmy zakodować wartość 9 (poprzednio udało się zakodować 56, więc z 9 nie spodziewamy się kłopotów...)
w ← 9 / 2 = 4 i reszta 1
w ← 4 / 2 = 2 i reszta 0
w ← 2 / 2 = 1 i reszta 0
w ← 1 / 2 = 0 i reszta 1
9(10) = 1001(2) = 01001(U2)
01001,000(U2)
= 0100,100(U2) = 010,010(U2) = 01,001(U2) = 0,100(U2) = |
100000(U2) 100001(U2) 100010(U2) 100011(U2) , ostatnia jedynka zaraz zniknie!!! 100100(U2) , kończymy |
Otrzymaliśmy wynik:
w =
0100 = 4(10) m = 0,100 = 1/2 |
,sprawdzamy: 1/2 · 24 = 16/2 = 8 |
9(10) =? 01000100(ZP)
Co się właściwie stało? Otóż w trakcie normalizowania mantysy nastąpiła utrata precyzji. Aby zapisać poprawnie wartość 9 musimy mieć 4 bity : 1001, a mantysa ma do dyspozycji jedynie 3. Więc ostatnia jedynka nie zmieściła się w przyjętym przez nas formacie zapisu liczb zmiennoprzecinkowych. W efekcie otrzymaliśmy wartość przybliżoną, najbliższą 9 i możliwą do zakodowania w tym systemie. Problem ten jest cechą wszystkich dwójkowych systemów pozycyjnych. Liczby są zapisywane tylko z pewną dokładnością, którą nazywamy precyzją. Oczywiście zwiększając liczbę bitów dla mantysy, zwiększymy rozdzielczość systemu, czyli jego precyzję. Dlatego większość języków programowania stosuje kilka różnych formatów zmiennoprzecinkowych. Np. w języku C++ możesz się spotkać z następującymi formatami:
Formaty zmiennoprzecinkowe | |||
Nazwa | Zakres | Precyzja | Liczba bitów |
float double long double |
1,5·10-45...3,4 · 1038 5,0·10-324...1,7 · 10308 3,4·10-4092...1,1 · 104932 |
7..8 cyfr 15..16 cyfr 19..20 cyfr |
32 64 80 |
Ponieważ liczby zmiennoprzecinkowe nie przechowują dokładnych wartości, to obliczenia wykonywane z ich pomocą również nie są dokładne i mogą prowadzić do błędów (np. przy sumowaniu lub mnożeniu dużej ilości czynników). W informatyce stworzono specjalny dział zwany analizą błędów obliczeniowych, który zajmuje się minimalizacją błędów przy obliczeniach.
Typowym przykładem występowania błędów zaokrągleń w systemie zmiennoprzecinkowym jest dziesiętny ułamek 1/10, który ma nieskończone rozwinięcie dwójkowe - w systemie dwójkowym jest to ułamek okresowy, podobnie jak ułamek 1/3 w systemie dziesiętnym równy 0,33333... Jeśli teraz wykonamy na dowolnym komputerze dziesięciokrotne sumowanie liczby 0,1, to spodziewamy się, iż dostaniemy wartość 1. Niestety, będzie to wartość bardzo bliska 1, ale nie równa dokładnie 1.
Niektóre programy, np. arkusz kalkulacyjny Microsoft Excel, stosują własne, specjalne metody zapamiętywania wartości zmiennoprzecinkowych, które w znacznym stopniu niwelują występowanie błędów zaokrągleń. W każdym razie jest to dziedzina bardzo skomplikowana i wykracza poza nasze opracowanie.
cyfry dziesiętne | |
cyfra | BCD |
0 | 0000(2) |
1 | 0001(2) |
2 | 0010(2) |
3 | 0011(2) |
4 | 0100(2) |
5 | 0101(2) |
6 | 0110(2) |
7 | 0111(2) |
8 | 1000(2) |
9 | 1001(2) |
W niektórych zastosowaniach urządzenia komputerowe muszą bezpośrednio operować cyframi dziesiętnymi: np. kasy sklepowe, liczniki, kalkulatory. Aby ułatwić to zadanie, wymyślono specjalny kod zapisu liczby dziesiętnej w systemie dwójkowym. Jest to kod BCD (ang. Binary Coded Decimal - Dziesiętny Kodowany Dwójkowo). W systemie tym nie koduje się wartości binarnej liczby, tylko jej poszczególne cyfry dziesiętne. Każdą cyfrę dziesiętną przedstawia się za pomocą 4 bitów według tabeli kodu BCD.
Zapis liczby dziesiętnej polega więc na zastąpieniu każdej z jej cyfr 4 bitami z tabeli kodowej. Oto odpowiedni przykład:
9234(10) = 1001 0010 0011 0100 = 1001001000110100(BCD)
Postępując odwrotnie otrzymamy zapis dziesiętny liczby przedstawionej w kodzie BCD:
10000110000001110001(BCD) = 1000 0110 0000 0111 0001 = 86071(10)
Zwróć uwagę, iż liczba zapisana w kodzie BCD po zamianie na system szesnastkowy da się bezpośrednio odczytać jako liczba dziesiętna. Jest to bardzo miła cecha liczb BCD, z której często korzystają programiści pracujący z takimi liczbami.
W wielu zastosowaniach konieczny jest kod binarny, w którym kolejne wyrazy
kodowe różnią się od siebie wartością tylko jednego bitu. Zwykłe kody binarne
nie posiadają tej własności, bo np. wyraz
Operacja XOR |
0 XOR 0 = 0 0 XOR 1 = 1 1 XOR 0 = 1 1 XOR 1 = 0 |
Zanim zaczniemy konstruować kolejne wyrazy w kodzie Gray'a (właściwie w jednym z możliwych kodów, gdyż można zdefiniować bardzo wiele różnych kodów Gray'a), musimy wprowadzić pewną operację nad bitami, która nosi nazwę XOR lub sumy modulo 2. Obok podajemy tabelkę wartości tej operacji dla wszystkich kombinacji bitów. Operacja XOR nad dwoma bitami daje wartość 0, gdy są one takie same, lub 1, gdy są różne.
Będziemy tworzyć 3-bitowy kod Gray'a. Sposób jest bardzo prosty. Najpierw tworzymy 3-bitowy kod binarny. W tabelce zapisujemy wyraz kodowy, a u dołu ten sam wyraz przesunięty w prawo o 1 bit (czyli o jedną pozycję). Prawy bit przesuniętego wyrazu ignorujemy (w tabelce zaznaczyliśmy go bladym kolorem). Lewy bit przepisujemy bezpośrednio do wyniku (w tabelce zaznaczyliśmy go kolorem zielonym). Nad pozostałymi bitami wykonujemy operację XOR i otrzymujemy w wyniku wyraz kodu Gray'a.
Kod binarny | XOR | Kod Gray'a |
0 000(2) |
000 000 000(Gray) |
000(Gray) |
1 001(2) |
001 001 001(Gray) |
001(Gray) |
2 010(2) |
010 010 011(Gray) |
011(Gray) |
3 011(2) |
011 011 010(Gray) |
010(Gray) |
4 100(2) |
100 100 110(Gray) |
110(Gray) |
5 101(2) |
101 101 111(Gray) |
111(Gray) |
6 110(2) |
110 110 101(Gray) |
101(Gray) |
7 111(2) |
111 111 100(Gray) |
100(Gray) |
Taki kod Gray'a nosi nazwę kodu odzwierciedlonego binarnie (binary reflected Gray Code). Otrzymanie wartości binarnej z wyrazu w kodzie Gray'a jest dla tych kodów równie proste. W tym celu kopiujemy najstarszy bit wyrazu w kodzie Gray'a do najstarszego bitu wyrazu binarnego. Resztę bitów binarnych otrzymamy wykonując operację XOR na i-tym bicie kodu Gray'a i (i+1) bicie wyrazu binarnego. Oto przykład.
Najpierw utwórzmy ze słowa binarnego 1101 wyraz w kodzie Gray'a:
1101(2) 1101 1011(Gray)
Teraz dokonamy konwersji odwrotnej:
1011 1xxx |
Przepisujemy do wyniku najstarszy bit |
1011 1 11xx |
Bit ten zapisujemy pod spodem na pozycji przesuniętej w prawo i obliczamy funkcję XOR z bitem kodu Gray'a |
1011 11 110x |
Otrzymany w wyniku operacji XOR bit umieszczamy pod spodem obok poprzedniego bitu |
1011 110 1101 |
Operację tę wykonujemy ponownie i otrzymujemy słowo binarne |
Konwersja: kod binarny ↔ kod Gray'a | |
INSTRUKCJA:
W górne pole wpisz wyraz kodu binarnego i kliknij przycisk Kod Gray'a, a w dolnym polu odczytasz odpowiadający mu wyraz w kodzie Gray'a. W dolne pole wpisz wyraz kodu Gray'a i kliknij przycisk Kod Binarny, a w górnym polu odczytasz odpowiadający mu kod binarny. |
|
JavaScript - (C)2002 Jerzy Wałaszek |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.