Autor artykułu: mgr Jerzy Wałaszek, wersja 1.0
©2008 mgr
Jerzy Wałaszek
I LO w Tarnowie
|
Autor artykułu: mgr Jerzy Wałaszek, wersja 1.0 |
©2008 mgr
Jerzy Wałaszek
|
Zapoznaj się z artykułem o binarnym kodowaniu liczb
Poznane dotychczas kody binarne - NBC i U2 - pozwalają kodować jedynie liczby całkowite. Na szczęście ich definicje można rozszerzyć, tak aby możliwym stało się kodowanie liczb ułamkowych. Wykorzystamy tutaj rozwiązanie zastosowane w systemie dziesiętnym. Zapiszmy z oznaczeniem wag liczbę 2754,8932:
| wagi pozycji | 1000 | 100 | 10 | 1 | 0,1 | 0,01 | 0,001 | 0,0001 | |
| 103 | 102 | 101 | 100 | 10-1 | 10-2 | 10-3 | 10-4 | ||
cyfry |
2 | 7 | 5 | 4 | , | 8 | 9 | 3 | 2 |
| numery pozycji | 3 | 2 | 1 | 0 | -1 | -2 | -3 | -4 |
Zapis liczby składa się z dwóch części oddzielonych przecinkiem:
części całkowitej 2754
części ułamkowej 8932
Jeśli oznaczymy numery pozycji ułamkowych kolejnymi liczbami ułamkowymi (co jest naturalne, ponieważ tworzy ciąg 3 2 1 0 -1 -2 -3 ...), to wagi pozycji w całym zapisie liczby są równe podstawie systemu 10 podniesionej do potęgi równej numerowi pozycji. Na przykład cyfra 9 znajduje się na pozycji -2. Waga tej pozycji to 10-2 = 0,01. Zatem cyfra 9 określa 9 setnych. Taki sposób zapisu liczby nosi nazwę zapisu stałoprzecinkowego (ang. fixed point notation), a liczba nazywa się liczbą stałoprzecinkową (ang. fixed point number).
Zasadę tę możemy w prosty sposób rozszerzyć na dowolny system pozycyjny:
Niech p będzie podstawą systemu pozycyjnego, C jego cyfrą należącą do zbioru {0,1,...,p-1} cyfr, a L zapisem liczby o n cyfrach całkowitych i m cyfrach ułamkowych:
L = Cn-1Cn-2...C2C1C0,C-1C-2...C-m
Wtedy wartość W liczby obliczamy sumując iloczyny wszystkich cyfr zapisu liczby przez ich wagi pozycji:
W = Cn-1pn-1 + Cn-2pn-2 + ...+ C2p2 + C1p1 + C0p0 + C-1p-1 + C-2p-2 + ...+ C-mp-m
Przykłady:
p = 5, L = 32,213
W = 3 × p1 + 2 × p0 + 2 × p-1 +
1 × p-2 + 3 × p-3
W = 3 × 51 + 2 × 50 + 2 × 5-1 + 1 ×
5-2 + 3 × 5-3
W = 3 × 5 + 2 × 1 + 2 × 1/5 + 1 × 1/25
+ 3 × 1/125
W = 15 + 2 + 2/5 + 1/25 + 3/125
W = 17 58/125
p = 3, L = 2201,2212
W = 2 × 33 + 2 × 32 + 0 × 31 + 1
× 30 + 2 × 3-1 + 2 × 3-2 + 1 × 3-3 +
2 × 3-4
W = 2 × 27 + 2 × 9 + 0 × 3 + 1 × 1 + 2 × 1/3 + 2 ×
1/9 + 1 × 1/27 + 2 × 1/81
W = 54 + 18 + 1 + 2/3 + 2/9 + 1/27
+ 2/81
W = 73 77/81
p = 2, L = 11011,11101
W = 1 × 24 + 1 × 23 + 0 × 22 + 1
× 21 + 1 × 20 + 1 × 2-1 + 1 × 2-2 +
1 × 2-3 + 0 × 2-4 + 1 × 2-5
W = 1 × 16 + 1 × 8 + 0 × 4 + 1 × 2 + 1 × 1 + 1 × 1/2
+ 1 × 1/4 + 1 × 1/8 + 0 × 1/16
+ 1 × 1/32
W = 16 + 8 + 2 + 1 + 1/2 + 1/4 +
1/8 + 1/32
W = 27 29/32
W kodzie binarnym możemy stosować tylko bity o wartościach 0 lub 1. Nie można zatem umieścić znaku przecinka w słowie kodowym. Dwójkowy zapis stałoprzecinkowy polega na określeniu w definicji pozycji przecinka i wg tej pozycji obliczamy wagi pozostałych bitów liczby.
Przykład:
W 8 bitowym kodzie stałopozycyjnym NBC przecinek znajduje się pomiędzy bitem b2 a b1. Obliczyć wartość liczby 11011011 zapisanej w tym systemie.
Najpierw zapisujemy liczbę z przecinkiem wstawionym pomiędzy bity b2 a b1:
| b7 | b6 | b5 | b4 | b3 | b2 | b1 | b0 | ||
| L = | 1 | 1 | 0 | 1 | 1 | 0 | , | 1 | 1 |
Teraz wyznaczamy wagi pozycji i obliczamy wartość liczby sumując wagi pozycji, na których stoi cyfra 1:
| 25 | 24 | 23 | 22 | 21 | 20 | 2-1 | 2-2 | ||
| L = | 1 | 1 | 0 | 1 | 1 | 0 | , | 1 | 1 |
W = 25 + 24 + 22 + 21
+ 2-1 + 2-2
W = 32 + 16 + 4 + 2 + 1/2 + 1/4
W = 54 3/4
Zadania
1. Przecinek na pozycji pomiędzy b3 a b2, L = 11001111. Obliczyć wartość L w systemie dziesiętnym.
2. Przecinek na pozycji pomiędzy b4 a b3, L = 11011101. Obliczyć wartość L w systemie dziesiętnym.
3. Przecinek na pozycji pomiędzy b5 a b4, L = 11101011. Obliczyć wartość L w systemie dziesiętnym.
Przeliczanie liczby dziesiętnej na stałoprzecinkową w systemie dwójkowym wykonujemy wg następującego algorytmu:
Liczbę dziesiętną rozdzielamy na część całkowitą LC oraz ułamkową LU.
Część całkowitą LC przeliczamy na system NBC wg poznanych wcześniej zasad - dzielimy ją przez 2, otrzymane reszty są cyframi liczby binarnej branymi w kierunku odwrotnym. Po podziale za nową liczbę przyjmujemy część całkowitą z dzielenia. Operację kontynuujemy dotąd, aż otrzymamy w dzieleniu wynik 0.
Część ułamkową mnożymy przez 2. Za kolejne cyfry ułamkowe w NBC przyjmujemy część całkowitą z wyniku mnożenia. Za nowe LU przyjmujemy część ułamkową. Operację powtarzamy dotąd, aż otrzymamy część ułamkową równą 0 lub zadaną liczbę cyfr ułamkowych.
Przykład:
Przeliczyć na stałoprzecinkowy zapis NBC liczbę dziesiętną 137,609375.
Rozdzielamy liczbę na część całkowitą i ułamkową:
LC = 137
LU = 0,609375
Przeliczamy część całkowitą LC na NBC:
| 137 : 2 = | 68 | i reszta 1 |
| 68 : 2 = | 34 | i reszta 0 |
| 34 : 2 = | 17 | i reszta 0 |
| 17 : 2 = | 8 | i reszta 1 |
| 8 : 2 = | 4 | i reszta 0 |
| 4 : 2 = | 2 | i reszta 0 |
| 2 : 2 = | 1 | i reszta 0 |
| 1 : 2 = | 0 | i reszta 1 - koniec, ponieważ wynikiem dzielenia jest 0 |
LC = 10001001(2)
Teraz przeliczamy część ułamkową LU na ułamkowe cyfry NBC:
| 0,609375 × 2 = | 1,21875 | → 0,1 |
| 0,21875 × 2 = | 0,4385 | → 0,10 |
| 0,4385 × 2 = | 0,875 | → 0,100 |
| 0,875 × 2 = | 1,75 | → 0,1001 |
| 0,75 × 2 = | 1,5 | → 0,10011 |
| 0,5 × 2 = | 1,0 | → 0,100111 - koniec, ponieważ część ułamkowa wyniku jest równa 0 |
Łączymy ze sobą wyznaczone części całkowitą i ułamkową:
L = 137,609375(10) = 10001001,100111(2)
Zadania
Przeliczyć na system NBC następujące liczby dziesiętne:
121,828125 438,375 511,998046875
Spróbujmy przeliczyć na system dwójkowy ułamek dziesiętny 0,1 (jedna dziesiąta):
| 0,1 × 2 = | 0,2 | → 0,0 |
| 0,2 × 2 = | 0,4 | → 0,00 |
| 0,4 × 2 = | 0,8 | → 0,000 |
| 0,8 × 2 = | 1,6 | → 0,0001 |
| 0,6 × 2 = | 1,2 | → 0,00011 |
| 0,2 × 2 = | 0,4 | → 0,000110 |
| 0,4 × 2 = | 0,8 | → 0,0001100 |
| 0,8 × 2 = | 1,6 | → 0,00011001 |
| 0,6 × 2 = | 1,2 | → 0,000110011 |
| ... | ... | → 0,0001100110011001100110011... |
Widzimy wyraźnie, iż obliczenia powtarzają się w kółko od wartości 0,2. Otrzymujemy ułamek okresowy nieskończony:
0,1(10) = 0,0(0011)
Obliczenia będą również wykonywane w nieskończoność dla ułamków 0,2 0,4 0,6 i 0,8 - a także 0,3 i 0,9. Ułamki te w systemie binarnym są nieskończonymi ułamkami okresowymi. Ponieważ komputer operuje na liczbach skończonych - np. 16, 32, 64, 80 bitowych, to nie będą one zapamiętane dokładnie. Obliczenia, w których występują takie ułamki będą obliczeniami przybliżonymi, obarczonymi błędami zaokrągleń. Jak zobaczymy później, wynikają z tego bardzo poważne konsekwencje, o których musi wiedzieć każdy informatyk.
Okazuje się, iż części ułamkowej liczby binarnej wcale nie musimy obliczać jako ułamka. Możemy przenieść na system binarny sposób odczytu części ułamkowej w systemie dziesiętnym. Przyjrzyj się poniższym przykładom:
| 5,6 | → 5 6/10 | : waga ostatniej pozycji 1/10 |
| 5,69 | → 5 69/100 | : waga ostatniej pozycji 1/100 |
| 5,692 | → 5 692/1000 | : waga ostatniej pozycji 1/1000 |
| 5,6924 | → 5 6924/10000 | : waga ostatniej pozycji 1/10000 |
Reguła jest następująca - część ułamkową traktujemy jak liczbę całkowitą, którą mnożymy przez wagę ostatniej pozycji. Zatem w systemie dwójkowym mamy:
| 101,1 | = 5 1/2 | : waga ostatniej pozycji 1/2 |
| 101,011 | = 5 3/8 | : waga ostatniej pozycji 1/8 |
| 110,1101 | = 6 13/16 | : waga ostatniej pozycji 1/16 |
| 111,11101 | = 7 29/32 | : waga ostatniej pozycji 1/32, itd. |
Mamy daną liczbę stałoprzecinkową NBC o n bitach całkowitych i m bitach ułamkowych. Zakres określamy wyznaczając najmniejszą i największą liczbę, którą da się przedstawić w tym systemie.
Najmniejsza liczba będzie wtedy, gdy wszystkie bity są ustawione na 0:
| 000...000 | , | 000...000 |
| n bitów całkowitych |
m bitów ułamkowych |
Wmin = 0
Największą liczbę otrzymamy, gdy wszystkie bity są ustawione na 1:
| 111...111 | , | 111...111 |
| n bitów całkowitych |
m bitów ułamkowych |
Część całkowita tej liczby jest równa:
WC = 2n - 1
Część ułamkowa jest równa:
WU = 1 - 2-m (wyprowadź ten wzór jako ćwiczenie - rozważ kolejne wartości 0,1 0,11 0,111 itd.)
Zatem
Wmax = WC + WU = 2n - 1 + 1 - 2-m
Wmax = 2n - 2-m
Stąd zakres liczb NBC dla n bitów całkowitych i m bitów ułamkowych wynosi
Z = <0, ... 2n - 2-m>
Zadania
1. Oblicz zakresy liczb NBC:
n = 8, m = 8
n = 12, m = 4
n = 24, m = 8
2. Oblicz zakres 16 bitowej stałoprzecinkowej liczby NBC, w której pozycja przecinka znajduje się pomiędzy bitami b5 i b4
W systemie U2 najstarszy bit posiada wagę ujemną. Wartość bezwzględna tej wagi jest taka sama jak w systemie NBC. Zatem wzór obliczeniowy jest następujący
LU2 = bn-1bn-2 ... b1b0 , b-1b-2...b-m
WU2 = bn-1 × (- 2n-1) + bn-2 × 2n-2 + ... + b1 × 21 + b0 × 20 + b-1 × 2-1 + b-2 × 2-2 + ...+ b-m × 2-m
Przykład:
Obliczyć wartość liczby U2: 1001,1101
W = 1 × (-23) + 0 × 22 + 0 × 21
+ 1 × 20 + 1 × 2-1 + 1 × 2-2 + 0 × 2-3
+ 1 × 2-4
W = 1 × (-8) + 0 × 4 + 0 × 2 + 1 × 1 + 1 × 1/2 + 1 ×
1/4 + 0 × 1/8 + 1 × 1/16
W = -8 + 1 + 1/2 + 1/4 + 1/16
W = -7 + 13/16
W = -6 3/16
Zadania
Obliczyć wartość poniższych liczb U2:
1000,0001 1111,1111 1,0000011
Przeliczanie liczb dziesiętnych na U2 najprościej można wykonać wg następującego algorytmu:
Jeśli liczba jest dodatnia, to przeliczamy ją wg metody podanej dla liczb NBC, a wynik uzupełniamy bitami 0 do wymaganego formatu.
Jeśli liczba jest ujemna, to znajdujemy reprezentację jej modułu w NBC, wynik uzupełniamy bitami 0 do wymaganego formatu, po czym przekształcamy go na liczbę ujemną U2 wg algorytmu:
Idziemy po kolejnych bitach od strony lewej do prawej. Końcowe zera przepisujemy bez zmian aż napotkamy pierwszą jedynkę. Jedynkę przepisujemy a pozostałe bity przepisując negujemy.
Przykłady:
Przeliczyć liczbę 7 3/4 na liczbę U2 o n = 5, m = 3:
7 = 111
3/4 = 0,11
L = 00111,110 (po uzupełnieniu bitami 0 do wymagań formatu U2)
Przeliczyć liczbę -35 15/32 na liczbę U2 o n = 8, m = 8
Przeliczamy moduł liczby:
35 = 100011
15/32 = 0,01111
Tworzymy dodatnią liczbę U2 uzupełniając bitami 0 do wymagań tego formatu:
00100011,01111000
Stosujemy podany algorytm zamiany na liczbę ujemną:
Końcowe zera przepisujemy wraz z pierwszą jedynką
| 00100011,01111000 1000 |
Pozostałe bity przepisujemy zanegowane:
| 00100011,01111000 11011100,10001000 |
I ostatecznie:
-35 15/32 = 11011100,10001000
Zadania
Przeliczyć podane liczy na stałoprzecinkowy system U2 o parametrach n = 5 i m = 3:
-21/4 -113/4 -51/2
Z liczbami zmiennoprzecinkowymi (ang. floating point numbers) w systemie dziesiętnym spotkałeś się na fizyce, gdzie bardzo duże lub bardzo małe wartości przedstawia się w tzw. notacji naukowej:
3,6 × 1025 1,8 × 10-12 itd.
Zapis liczby zmiennoprzecinkowej zbudowany jest z trzech liczb:
WFP = m × pc
m - mantysa, liczba stałoprzecinkowa
p - podstawa systemu
c - cecha, liczba całkowita ze znakiem
W systemie dwójkowym podstawa p jest równa 2, zatem otrzymujemy następujący wzór na wartość dwójkowej liczby zmiennoprzecinkowej:
WFP = m × 2c
W dwójkowym kodzie zmiennoprzecinkowym bity są odpowiednio rozdzielone na bity reprezentujące wartość cechy oraz bity reprezentujące wartość mantysy. Na potrzeby szkolne zdefiniujmy prosty kod zmiennoprzecinkowy. Słowo kodowe będzie zbudowane z 8 bitów podzielonych po połowie na bity cechy i bity mantysy:
| słowo kodu FP | b7b6b5b4 | b3b2b1b0 |
| cecha | mantysa |
Umawiamy się, iż bity cechy reprezentują 4-ro bitową liczbę U2. Wagi tych bitów są zatem następujące:
| wagi bitów | -8 | 4 | 2 | 1 |
| bity cechy: | b7 | b6 | b5 | b4 |
Bity mantysy reprezentują 4-ro bitową stałoprzecinkową liczbę U2. Miejsce przecinka ustalamy pomiędzy b3 a b2. Zatem wagi bitów mantysy są następujące:
| wagi bitów | -1 | 1/2 | 1/4 | 1/8 | |
| bity mantysy: | b3 | , | b2 | b1 | b0 |
Przykłady:
Obliczyć wartość liczby LFP = 00110101
Wartość liczby obliczamy korzystając z powyższej definicji znaczenia bitów w kodzie FP. Najpierw bity rozdzielamy na bity cechy i bity mantysy:
c = 0011
m = 0101
Teraz traktujemy te bity zgodnie z definicją kodu i wyliczamy wartość cechy oraz mantysy:
c = 0011U2 = 3
m = 0,101U2 = 5/8
Mając wyliczoną mantysę m i cechę c obliczamy wartość liczby zmiennoprzecinkowej wg wzoru:
WFP = m × 2c
WFP = 5/8 × 23 = 5/8
× 8 = 5
Obliczyć wartość liczby LFP = 11100011
c = 1110U2 = -2
m = 0,011U2 = 3/8
WFP = 3/8 × 2-2 = 3/8 × 1/4 = 3/32
Obliczyć wartość liczby LFP = 10001111
c = 1000U2 = -8
m = 1,111U2 = -1 + 7/8 = -1/8
WFP = -1/8 × 2-8 = -1/8 × 1/256 = -1/2048
Zadania
Obliczyć wartość liczb FP zgodnie z podaną definicją:
11001100 01110001 00001000
Obliczymy teraz największą dodatnią oraz najmniejszą ujemną liczbę, którą da się przedstawić w zdefiniowanym powyżej kodzie FP.
Liczba FP jest iloczynem mantysy m oraz potęgi 2c. Zatem wartość największą przyjmie wtedy, gdy mantysa i cecha będą największe. Cecha jest 4-ro bitową całkowitą liczbą U2 i największą wartość przyjmuje dla kodu:
cmax = 0111U2 = 7
Mantysa jest 4-bitową stałoprzecinkową liczbą U2 i największą wartość przyjmuje, podobnie do cechy, dla kodu:
mmax = 0,111U2 = 7/8
Stąd:
WFPmax = mmax × 2Cmax = 7/8 × 27 = 7/8 × 128 = 7 × 16 = 112
Teraz policzymy najmniejszą liczbę ujemną. Znów korzystamy z faktu, iż wartość liczby FP jest iloczynem mantysy i potęgi liczby 2. Najmniejszą ujemną liczbę FP otrzymamy dla maksymalnej cechy:
cmax = 0111U2 = 7
oraz dla najmniejszej ujemnej mantysy:
mmin = 1,000U2 = -1
Stąd:
WFPmin = mmin × 2Cmax = -1 × 27 = -1 × 128 = -128
Zakres możliwych do przedstawienia liczb zmiennoprzecinkowych w zdefiniowanym powyżej kodzie FP obejmuje przedział od -128 do 112.
Po wyznaczeniu zakresu liczb FP możemy przypuszczać, iż nasz kod będzie w stanie przedstawić każdą liczbę całkowitą z tego zakresu. Sprawdźmy to. Spróbujmy zakodować liczbę 9. W tym celu musimy wyznaczyć mantysę m < 1 oraz wykładnik c taki, aby zachodziła równość:
9 = m × 2c
Do rozwiązania dojdziemy stosując kolejne tożsamości:
9 = 9 × 20
9 = 9/2 × 21
9 = 9/4 × 22
9 = 9/8 × 23
9 = 9/16 × 24
Zatem m = 9/16, a c = 4. Wyznaczamy kod binarny cechy i mantysy:
c = 4 = 0100U2
m = 9/16 = 0,1001U2
I tutaj napotykamy na problem - mantysa wyszła nam 5-bitowa, tymczasem nasz kod definiuje mantysę 4-bitową. Ostatni bit wyznaczonej mantysy nie mieści się w kodzie i musi zostać odrzucony, zatem:
m = 0,100U2
Otrzymujemy słowo kodu FP:
LFP = 01000100
Teraz obliczmy jego wartość:
c = 0100U2 = 4
m = 0,100U2 = 1/2
WFP = m × 2c = 1/2 × 24 = 1/2 × 16 = 8, a miało być 9!
Co się tutaj stało. Otóż nasz system zapamiętuje liczby tylko z precyzją do 3 bitów, gdyż tyle potrafi zapamiętać mantysa Za precyzję będziemy rozumieli liczbę bitów liczby, które pozostają po odrzuceniu z przodu i z tyłu jej zapisu dwójkowego wszystkich zer. Np:
| 01000 → | 1 | - precyzja 1 bit |
| 01100 → | 11 | - precyzja 2 bity |
| 010100 → | 101 | - precyzja 3 bity |
| 010110 → | 1011 | - precyzja 4 bity |
| 0010000010 → | 1000001 | - precyzja 7 bitów |
Ponieważ liczba 9 = 1001 wymaga precyzji 4-bitowej, to nie może być dokładnie zapamiętana w naszej mantysie, która na ten cel ma tylko 3 bity (dla liczb dodatnich, dla ujemnych bitów jest 4). Co ciekawe, liczbę 10 = 1010 da się bez problemu zapisać w naszym systemie FP:
10 = 10 × 20
10 = 10/2 × 21 = 5 × 21
10 = 5/2 × 22
10 = 5/4 × 23
10 = 5/8 × 24 - koniec, ponieważ mamy
mantysę mniejszą od 1:
c = 4 = 0100U2
m = 5/8 = 0,101U2
LFP = 01000101
Nie utraciliśmy żadnego bitu, zatem kod reprezentuje dokładną wartość liczby.
|
Zapamiętaj: Mantysa wpływa na precyzję liczby FP. Im więcej bitów posiada mantysa, tym dokładniej można zapisać w niej daną liczbę rzeczywistą. Liczby wymagające większej precyzji niż może zapewnić mantysa są przechowywane z zaokrągleniem, czyli z pewnym błędem. Cecha wpływa na zakres możliwych do zakodowania liczb w danym systemie FP. Im więcej bitów posiada cecha, tym większy jest zakres liczb FP. |
Zadania
Stosując tożsamości przelicz podane liczby dziesiętne na kod FP, który zdefiniowaliśmy powyżej:
31/2 7 3/64
 | I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe