SystemyLiczbowe.pdf

Elementy arytmetyki komputerowej

cz. I Elementy systemów liczbowych

/ materiał pomocniczy do wykładu Informatyka sem II/

Spis treści

1. Wprowadzenie.....................................................................................................................................2

2. Wstępne uwagi o systemach liczbowych...........................................................................................2

3. Przegląd wybranych systemów liczbowych......................................................................................3

4. Systemy binarny naturalny, oktalny i heksalny...............................................................................8

5. Konwersje międzysystemowe.............................................................................................................9

5.1.System binarny system dziesiętny...............................................................................................10

5.2. System oktalny system dziesiętny...............................................................................................12

5.3. System heksalny system dziesiętny.............................................................................................12

5.4. System binarny ⇔ oktalny..............................................................................................................13

5.5. System binarny heksalny.............................................................................................................13

6. Przesunięcia liczby binarnej............................................................................................................14

7. Działania arytmetyczne w systemie binarnym naturalnym..........................................................17

7.1.Dodawanie........................................................................................................................................17

7.2. Odejmowanie...................................................................................................................................18

7.3. Mnożenie.........................................................................................................................................20

7.4 Dzielenie...........................................................................................................................................22

8. Wybrane reprezentacje liczb ze znakiem.......................................................................................24

8.1. Reprezentacja znak-moduł...............................................................................................................25

8.2 Reprezentacja z uzupełnieniem do 1 ( kod U1)................................................................................26

8.3 Reprezentacja z uzupełnieniem do 2 ( kod U2)................................................................................27

8.4. Uwagi o systemach uzupełnieniowych............................................................................................28

9. Wybrane działania arytmetyczne w systemach uzupełnieniowych..............................................29

9.1. Dodawanie w kodzie U2..................................................................................................................29

9.2. Odejmowanie w kodzie U2..............................................................................................................33

1. Wprowadzenie

⇔

Arytmetyka komputerowa (ang. computer arithmetic) zajmuje się problemami realizacji

obliczeń w urządzeniach cyfrowych. Obejmuje ona zagadnienia teoretyczne takie jak systemy

liczbowe przydatne w projektowaniu urządzeń liczących lub w programowej realizacji

obliczeń. Zagadnienia związane z systemami liczbowymi obejmują konstrukcję nowych

systemów liczbowych i badanie własności systemów. Przedmiotem arytmetyki komputerowej

jest ponadto realizacja podstawowych operacji arytmetycznych takich jak dodawanie i

odejmowanie liczb bez znaku i ze znakiem, mnożenie i dzielenie jak i obliczanie

standardowych funkcji arytmetycznych (sinus, cosinus, logarytm naturalny, arcus sinus, arcus

tangens, pierwiastek kwadratowy i funkcja ). Arytmetyka komputerowa zajmuje się także

syntezą szybkich i efektywnych układów do realizacji wyżej wymienionych operacji. Ten

dział arytmetyki komputerowej wiąże się ścisle z technologią wielkiej skali integracji VLSI

(Very Large Scale of Integration). Aktualne zagadnienia arytmetyki cyfrowej to m.in. bardzo

szybka realizacja obliczeń z wykorzystaniem potokowania (ang. pipelining) i wykonywanie

operacji arytmetycznych z małym poborem mocy (ang. low-power arithmetic). Zagadnienie

to ma szczególne znaczenie w związku z rozwojem urządzeń przenośnych, jak również ze

wzrostem stosowanych częstotliwości zegarowych, zważywszy na fakt iż pobór mocy w

urządzeniach VLSI jest liniowo proporcjonalny do częstotliwości zegara. Do aktualnych

zagadnień należy również arytmetyka odporna na błędy (ang. fault-tolerant arithmetic).

W poniższym opracowaniu zestawiono nieco rozszerzoną treść czterech wykładów w

ramach części I wykładu Informatyka obejmującej podstawy informatyki.

2. Uwagi wstępne o systemach liczbowych

Systemy reprezentacji liczb rozwijały się wraz z rozwojem języka. Najstarsze metody

reprezentacji liczb to reprezentowanie przy użyciu różnych przedmiotów np. kamieni lub

patyczków (łac. calculus oznacza kamyczek). Jednak gdy powstała konieczność stosowania

większych liczb, ich reprezentowanie z użyciem pojedynczych przedmiotów jak też

porównywanie takich liczb stawało się coraz trudniejsze. Pierwszym udoskonaleniem było

grupowanie przedmiotów reprezentujących jednostki (np. liczbę 23 reprezentowano jako 4

grupy po 5 kamyczków oraz 3 osobne). Główny przełom stanowiło jednak wprowadzenie

większych przedmiotów reprezentujących grupę 5 lub 10 jednostek.

Metoda ta rozwinęła się do formy symbolicznej, gdy zaczęto stosować specjalne symbole

do oznaczenia większych jednostek. Znanym przykładem jest zapis rzymski. Jednostkami w

tym systemie są 1, 5, 10, 50, 100, 500, 1000, 10000 i 100000, które są oznaczane

odpowiednio symbolami I, V, X, L, C, D, M, ((I)) i (((I))). Liczbę w tym systemie

reprezentuje się w postaci łańcucha symboli o wartości malejącej od lewej strony. Aby

skrócić zapis przyjęto, że symbol znajdujący się po lewej stronie większego symbolu

reprezentuje wartość ujemną. Np. liczbę 9 bezpośrednio można by zapisać jako VIIII, jednak

wygodniejszy jest zapis IX. Podobnie liczbę 450 można by zapisać jako CCCCL, jednak

zapis LD jest bardziej dogodny.

System rzymski nie jest odpowiedni do reprezentowania dużych liczb jak również trudno

jest wykonywać operacje arytmetyczne z jego użyciem. Istotną innowacją było wprowadzenie

przez Chińczyków systemu pozycyjnego(wagowego), w którym wartość reprezentowana

przez symbol nie zależy tylko od niego samego, ale także od jego położenia względem innych

symboli. Przykładowo, w liczbie 444 każda z cyfr "4", reprezentuje inną wartość. Skrajna od

lewej reprezentuje 400, środkowa 40, a skrajna z prawej 4.

System liczbowy, S można określić jako zbiór

S ={X, X , F}, (1)

gdzie

X- zbiór wartości abstrakcyjnych liczb,

X - zbiór reprezentacji liczb,

F: X → X.

Ogólnie reprezentację liczby można zapisać następująco

(

−

,...,

) , (2)

gdzie , i =0,1,2,..., n -1 są cyframi reprezentacji. Dla popularnych systemów pozycyjnych nie

stosuje się zwykle przy zapisie nawiasów ani przecinków.

3. Przegląd wybranych systemów liczbowych

W systemie wagowym liczba X jest przedstawiana w sposób następujący:

∑ −

−

i w

, (3)

gdzie

w i ∈

{}

, a

d i ∈

{ D

, zbiór W zwany jest zbiorem wag, a zbiór D zbiorem cyfr.

Jeżeli wszystkie wagi są potęgami pewnej stałej r ,

w =

, to taki system wagowy

nazywamy systemem z stałą podstawą ( ang. fixed- radix number system). Liczbę X w takim

systemie można zapisać jako

X ∑ −

−

i r

. (4)

Zbiór dozwolonych cyfr jest taki sam na każdej pozycji.

Istnieją też , będące w powszechnym użyciu, systemy wagowe nie będące systemami o

stałej podstawie, np. system zliczania czasu. Niech T oznacza czas w ciągu doby wyrażony w

sekundach dla pewnej liczby godzin, minut i sekund. T możemy zapisać jako

⋅

, (5)

gdzie poszczególne cyfry mogą przyjmować wartości z następujących zakresów

≤ E

0 <

≤ E

1 <

≤ E

2 <

Bezwzględną dokładność reprezentacji liczby w systemie wagowym wyznacza waga

najmniej znaczącej pozycji czyli

r −

. W systemie ze stałą podstawą reprezentacja zera

unikalna, gdyż nie istnieje liczba różna od {0,0,...,0}, której wartością byłoby zero. W

systemie takim liczby najmniejsza, N i największa, P reprezentowalne na n pozycjach, mają

postać

(

,...,

)

, (6)

oraz

(

−

,...,

−

. (7)

Sposób reprezentacji liczb wpływa nie tylko na łatwość odczytywania liczb, a także na

złożoność algorytmów arytmetycznych stosowanych przy realizacji operacji na liczbach.

Systemy pozycyjne zawdzięczają swą popularność, przynajmniej częściowo, dostępności

prostych i wygodnych algorytmów do realizacji działań na liczbach reprezentowanych w tych

systemach. Istnieją jednak systemy niepozycyjne, takie jak resztowy system liczbowy, które

mają przewagę nad systemami pozycyjnymi przy realizacji niektórych działań

arytmetycznych w pewnych dziedzinach zastosowań.

W systemach cyfrowych liczby są kodowane przy użyciu cyfr binarnych zwanych bitami.

Stosowanie systemu binarnego wynika z powodów technologicznych, gdyż w fizycznych

urządzeniach łatwiej jest reprezentować dwa stany, którym przypisuje się cyfry binarne.

Operandami algorytmów arytmetyki komputerowej są więc kody reprezentujące liczby. Zbiór

kodów takich jest jednak zbiorem dyskretnym i skończonym, stąd nie wszystkie reguły

arytmetyki konwencjonalnej, stosują się do algorytmów arytmetyki komputerowej. Stosuje się

zasadniczo dwa rodzaje reprezentacji liczb w komputerach :

-reprezentację stałoprzecinkową (ang. fixed-point representation), gdzie liczba pozycji

przeznaczonych do zakodowania części całkowitej liczby i części ułamkowej liczby jest stała,

-reprezentację zmiennoprzecinkową ( ang. floating-point representation), w której

osobno jest kodowana jest mantysa wraz ze znakiem oraz osobno cecha określająca relację

między liczbą a mantysą.

Przykład 3.1. Reprezentacja stałoprzecinkowa o 8 pozycjach może być zapisana

następująco

xxxx.xxxx, (8)

kropka (przecinek) oddziela cześć całkowitą od części ułamkowej. W systemie dziesiętnym

można przy użyciu takiej reprezentacji przedstawiać liczby z zakresu [0000.000, 9999.9999],

a w systemie binarnym [0000.0000,1111.1111].

Reprezentacja zmiennoprzecinkowa w systemie dziesiętnym ma postać

⋅ , (9)

gdzie m jest mantysą a c cechą. Mantysa i cecha są liczbami stałoprzecinkowymi.

Reprezentacja taka nie jest jednoznaczna, np. liczba 12.35 może być reprezentowana jako

1 ⋅

235

, czy też

0 ⋅

1235

, zwykle przyjmuje się, że

0 <

≤ m

Reprezentacja zmiennoprzecinkowa w systemie binarnym w najprostszym przypadku

może mieć następującą postać

⋅ , (10)

w której m i c są liczbami binarnymi stałoprzecinkowymi oraz

0 <

≤ m

. Zakres ten

wynika stąd, że jeżeli chcemy aby ułamek binarny miał cyfrę 1 po kropce oddzielającej część

ułamkową od części całkowitej, to jego minimalną wartością będzie

−

1 =

. W praktyce

stosuje się jednak z różnych względów reprezentacje o bardziej złożonej formie niż (10).

Zwykle stosuje się standardowe reprezentacje zmiennoprzecinkowe okreslone standardami

IEEE 754 i IEEE 854.

Jak zaznaczono powyżej, liczby w systemach cyfrowych są kodowane przy użyciu bitów.

Kodowanie oznacza, że każdej liczbie, która ma być reprezentowana w danym systemie

cyfrowym, przypisuje się pewien kod-ciąg bitów reprezentujący tę liczbę. Przypisanie to

powinno być logiczne i systematyczne, tak aby umożliwiało prostą realizację operacji

arytmetycznych, jak również proste sprawdzanie osobliwości lub specjalnych przypadków.

Może to być np.sprawdzanie, czy kod otrzymany w wyniku jakiejś operacji reprezentuje

m 10

m 2

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: