Janusz Biernat, profesor nadzw.

Politechnika Wrocławska
Wydział Elektroniki
Instytut Informatyki, Automatyki i Robotyki
Zakład Architektury Komputerów

ARYTMETYKA KOMPUTERÓW

↸ Wrocław

 p. 201 bud. C3

(

071 320 3916 (071 320 2745)

-

[e-mail]

http://www.zak.ict.pwr.wroc.pl/materialy/arytmetyka

A

RYTMETYKA KOMPUTERÓW

– program wykładu 2006

1. Reprezentacje stałoprzecinkowe dodatnich liczb wymiernych, konwersje podstawy.

2. Reprezentacje liczb znakowanych - uzupełnieniowa, spolaryzowana, SD.

Dodawanie i odejmowanie liczb znakowanych, nadmiar.

3. Mno enie w systemach uzupełnieniowych. Algorytm Booth’a-McSorleya.

4. Dzielenie w systemach uzupełnieniowych. Obliczanie pierwiastka kwadratowego.

5. Kongruencje. Twierdzenie Eulera. Chi skie twierdzenie o resztach.

Systemy resztowe RNS. Konwersja na reprezentacj RNS i konwersja odwrotna.

6. Rozszerzanie zakresu działa arytmetycznych. Reprezentacje zmiennoprzecinkowe.

Standard IEEE754. Obliczenia zmiennoprzecinkowe, dokładno , zaokr glanie.

7. Dzielenie numeryczne. Metoda Newtona-Raphsona. Algorytm CORDIC – obliczanie

funkcji elementarnych.

8. Kolokwium (algorytmy oblicze ).

9. Podstawy algebry Boole'a, realizacja funkcji logicznych. Sumatory.

10. Szybkie sumatory stałoprzecinkowe (CSA, PPA, COSA, CSLA, CSKA).

11. Układy szybkiego mno enia liczb w reprezentacjach stałoprzecinkowych.

12. Przy pieszanie dzielenia i obliczania pierwiastka kwadratowego.

13. Kolokwium (układy cyfrowe).

14. Architektura układów arytmetyki resztowej RNS.

A

RYTMETYKA KOMPUTERÓW

– program ćwiczeń

Kodowanie liczb, konwersje podstawy
Dodawanie i odejmowanie w systemach naturalnych i uzupełnieniowych
Mno enie
Dzielenie i obliczanie pierwiastka kwadratowego
Arytmetyka resztowa
Arytmetyka zmiennoprzecinkowa i obliczenia numeryczne
Logika i układy cyfrowe

Układy mno

ce

Układy arytmetyki resztowej
Arytmometr zmiennoprzecinkowy

Literatura

Literatura podstawowa

J.B

IERNAT

, Metody i układy arytmetyki komputerowej, Wrocław, Oficyna Wydawnicza

Politechniki Wrocławskiej, 2001.

I.K

OREN

, Computer Arithmetic Algorithms, A.K.Peters, Natick, MA, 2002

(wyd.1: Prentice Hall, Englewood Cliffs, NJ, 1993).

R.Z

IMMERMANN

, Lecture Notes on Computer Arithmetic: Principles, Architectures and

VLSI Design, Institut für Integrierte Systeme, Eidgenössische Technische
Hochschule, Zurich, March, 1999.

Literatura uzupełniaj

ą

ca

B.P

ARHAMI

, Computer Arithmetic. Algorithms and Hardware Designs, New York-Oxford, Oxford

University Press, 2000

J-M.M

UELLER

, Elementary functions. Boston: Birkhauser 1997

B.P

OCHOPIE

, Arytmetyka w systemach cyfrowych, Warszawa, AOW Exit, 2004

(Arytmetyka systemów komputerowych, Gliwice, Wyd. Polit. l skiej, 2000, wyd.V)

J.B

IERNAT

, Architektura komputerów, Wrocław, Oficyna Wydawnicza Politechniki Wrocławskiej,

2005 (wyd.IV).

J.B

IERNAT

, Arytmetyka komputerów, Warszawa, PWN, 1996.

N.K

OBLITZ

, Wykład z teorii liczb i kryptografii, WNT, 1995.

S.W

ASSER

, M.J.F

LYNN

, Introduction to arithmetic for digital system designers, New York, Holt,

Rinehart, Winston 1982.

Arytmetyka

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

AR–I

Algebra – abstrakcyjne uogólnienie arytmetyki

System algebraiczny – zbiór z działaniami zamkni tymi w tym zbiorze

•

grupa (ang. group) – zbiór z jednym działaniem ł cznym (dodawanie)

istnieje element przeciwny do ka dego oraz element neutralny

– w grupie mo na „dodawa ” i „odejmowa ”

•

pier cie (ang. ring) – zbiór z dwoma działaniami (dodawanie, mno enie):

grupa przemienna wzgl dem dodawania, zamkni ty dla mno enia
„mno enie” jest ł czne i obustronnie rozdzielne wzgl dem „dodawania”

– w pier cieniu mo na „dodawa ”, „odejmowa ” i „mno y ”

Pier cie przemienny (niesko czony) liczb całkowitych .

•

ciało (ang. field) – zbiór z dwoma powi zanymi działaniami przemiennymi

jest grup ze wzgl du na dodawanie, dodawanie rozdzielne wzgl dem
mno enia, a bez elementu „0” jest grup ze wzgl du na „mno enie”

–w ciele mo na „dodawa ”, „odejmowa ”, „mno y ” i „dzieli ” (mno y przez odwrotno )

Ciała liczb: całkowitych modulo liczba pierwsza p

p (sko czone)

wymiernych ; rzeczywistych ; zespolonych (niesko czone).

Arytmetyka

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

AR–II

Arytmetyka

Teoria liczb – wła ciwo ci liczb naturalnych

Sposoby obliczania wyniku działa podstawowych (arytmetycznych)

•

odejmowanie i dodawanie (... mo na wykona przez odejmowanie)

•

mno enie – sekwencyjne lub równoległe

o

skalowanie – mno enie przez całkowit pot g bazy

•

dzielenie – sekwencyjne lub mno enie przez odwrotno dzielnika

•

wyci ganie pierwiastka kwadratowego – sekwencyjne

Arytmetyka klasyczna – dowolny rozmiar liczb (rozszerzenia niesko czone)

✧

problem – algorytm (jak to zrobi ?)

Arytmetyka komputerowa – ograniczony zakres argumentów

✧

problem – nadmiar (przekroczenie zakresu)

✧

problem – szybko wykonania działa

✧

problem – dokładno wyniku

Arytmetyka

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

AR–III

Dokładno i szybko oblicze

Dodawanie, odejmowanie, mno enie

•

argumenty dokładne – wynik tak e dokładny

•

argumenty przybli one ze znan dokładno ci :
– łatwa kontrola dokładno ci wyniku, kumulacja bł dów przybli e

Dzielenie, obliczanie pierwiastka kwadratowego

•

wynik zwykle niedokładny (nawet gdy argumenty s dokładne)

•

konieczna kontrola dokładno ci wyniku

W

NIOSEK

: Nale y najpierw wykona działania dokładne.

Obliczenia: działania składowe + przepis (algorytm)

działania składowe:

•

elementarne – szybkie

→

czasochłonny algorytm (program)

•

zło one – czasochłonne

→

prosty krótki algorytm (układ cyfrowy)

Arytmetyka

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

AR–IV

Liczby i cyfry

Liczba – abstrakcyjny wynik oblicze , warto , opis ilo ciowy obiektu
Cyfra – znak (symbol) u ywany do zapisu (reprezentacji) liczb

Cyfry rzymskie

I

V

X

L

C

D

M / (I)

D /(V) M /((I))

jeden

pi

ę

ć

dziesi

ę

ć

pi

ę

ć

dziesi

ą

t

sto

pi

ę

ć

set

tysi

ą

c

5 tysi

ę

cy

10 tysi

ę

cy

Cyfry arabskie (pochodz ce z Persji)

0

1

2

3

4

5

6

7

8

9

Cyfry indyjskie, u ywane w zapisie w j zyku arabskim

0

1

2

3

4

5

6

7

8

9

Umowa (niepisana) o zapisie cyfr o warto ciach wi kszych od dziewi ciu

0

1

2

3

4

5

6

7

8

9

„10“ „11“ „12“ „13“ „14“ „15“

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

Systemy liczenia

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SL–I

Miary i liczby – systemy wagowe

– system pomiaru czasu – 1 doba =24 h, 1 h=60 min, 1 min =60 s
– brytyjski system miar i wag

miary odległo ci

miary wagi

inch (cal)

– 1 in (25,3995 mm)

grain (ziarno) – 1 gr (64,79891 mg)

foot (stopa) – 1 ft = 12 in

dram

– 1 dr (1,77185 g)

yard (jard)

– 1 yd = 3 ft

ounce (uncja) – 1 oz = 16 dr = 437

1

/

2

gr

fathom

– 1 fathom= 2 yd

pound (funt)

– 1 lb = 8 oz

rod (pr t)

– 1 rod = 5

1

/

2

yd

stone (kamie ) – 1 st = 14 lb

chain

– 1 chain = 4 rods

quarter

– 1 q = 2 st

furlong

– 1 furlong = 10 chains

hundredweight – 1 cwt = 2 q

mile (mila)

– 1 mi = 8 furlongs

ton (tona)

– 1 t = 20 cwt

league

– 1 lg = 3 m

central

– 1 st = 100 Ib

Systemy abstrakcyjne – system rzymski (tak e babilo ski)

I

(= 2

0

5

0

)

jedno

C

(= 2

2

5

2

)

setka

V (= 2

0

5

1

)

pi tka

D

(= 2

2

5

3

)

pi

setka

X (= 2

1

5

1

)

dziesi tka

M

(= 2

3

5

3

)

tysi c

L (= 2

1

5

2

)

pi

dziesi tka

D

(= 2

3

5

4

)

pi

tysi cy

Systemy liczenia

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SL–II

Działania w systemach wagowych

Systemy wagowe (weighted)

•

reprezentacja warto ci – zbiór par (liczba, waga), wiele reprezentacji

•

zb dny (a wi c nieu ywany) symbol zera

skomplikowane algorytmy działa :

1q

6st

2lb

7oz

8 yd

+

9st

9oz

×

9 in

2q

1st

3lb

2¼ sqft

M C M X L V I

I

I

C M X L I

–

M D C C X I V

×

C D I V

?? M M M D C L X I

I

!? M C C C X L V

W

NIOSEK

:

Wagi warto uporz dkowa a zapis unormowa .

Systemy liczenia

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SL–III

Systemy pozycyjne

Systemy pozycyjne (positional, place-value)

•

wagi uporz dkowane i przypisane pozycjom

→

niezb dny symbol „zero”

•

z ka d pozycj (wag ) skojarzona cyfra (mno nik wagi)

•

reprezentacja liczby – wektor warto ci, zwanych te cyframi (ang. digit)

Systemy z ustalon podstaw (radix-based)

•

stałobazowe (fixed-radix) – waga pozycji = pot ga podstawy (radix)

– naturalne
– negabazowe (negative radix) – ujemna podstawa (baza)
– z cyfr znakowan (signed digit, SD) – cyfry ujemne

•

uzupełnieniowe (radix-complement) – ujemna waga pozycji najwy szej

Systemy z mieszanymi podstawami (mixed-radix) – waga = iloczyn pot g baz

×

system aramejski – dwunastkowo-pi tkowy (Mezopotamia, Babilon)

×

system rzymski – regularne wagi przypisane znakom (a nie pozycjom):
(I = 2

0

5

0

, V = 2

0

5

1

, X = 2

1

5

1

, L = 2

1

5

2

, C = 2

2

5

2

, D = 2

2

5

3

, M = 2

3

5

3

,...)

System resztowy (residue number system, RNS) – liczba=: wektor reszt

Systemy liczenia

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SL–IV

Systemy stałobazowe (pozycyjne)

System stałobazowy 〈

β

,D〉 (fixed-radix), popularnie zwany pozycyjnym:

•

ustalona podstawa (baza) – zwykle liczba całkowita taka, e |

β

|≥2

•

dla ka dej pozycji okre lone:

o

reguła tworzenia wag

}

,...,

,

,...,

{

0

1

1

m

k

w

w

w

w

−

−

=

W

,

i

i

w

β

=

o

zbiór dozwolonych cyfr

}

0

,

,...,

{

0

1

1

=

=

−

i

i

i
p

i

d

d

d

D

, x

i

∈

D

i

(zawiera zero)

Warto ci X liczby o reprezentacji

β

}

,...,

,

,...,

{

0

1

1

m

k

x

x

x

x

−

−

=

X

,

i

i

x

D

∈

, jest:

∑

−

=

−

=

−

−

−

−

−

−

=

+

+

+

+

+

=

1

1

1

0

1

1

1

...

...

k

i

m

i

i

i

m

m

k

k

x

x

x

x

x

x

X

β

β

β

β

β

•

dokładno bezwzgl dna = waga najmniej znacz cej pozycji

m

ulp

−

=

β

•

standardowy zbiór cyfr

}

1

,...,

1

,

0

{

−

=

β

D

,

β

∈

(

β

≥2)

•

redundantny zbiór cyfr ||D

+

|| >

β

,...}

,

,

1

,...,

2

,

1

,

0

{

1

1

1

2

2

1

1

+

−

−

+

+

−

=

+

=

+

=

=

β

β

β

β

β

β

β

β

d

d

a

d

a

d

a

d

D

Systemy liczenia

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SL–

V

Popularne systemy pozycyjne

naturalny 〈

β

,D〉

,

β

≥2

,

•

standardowy zbiór cyfr

}

1

,...,

1

,

0

{

−

=

β

D

z cyfr znakowan (signed digit, SD

) 〈

β

,D〉

, reprezentacja liczb ujemnych

•

zbiór cyfr

: D = {d

p–1

, ..., d

1

, d

0

= 0; p

≥

β

, |

d

i

|

<

β

},

dozwolone s ujemne warto ci cyfr, np. D={…, 2, 1, 0, 1, 2, …}

•

nieredundantny

β

β

mod

},

,...,

,

0

{

1

1

i

d

d

d

i

e

≡

=

−

D

Np:

β

= 10, D={0,1,8,3,4,5,4,7,2,1} (d =

−

d

): 2 = 18, 56 = 144, 63 = 143

negabazowy

〈

β

,D〉

,

−

β

≥2

, reprezentacja liczb ujemnych

•

standardowy zbiór cyfr

:

}

1

,...,

1

,

0

{

−

=

β

D

•

(du a asymetria), specyficzna arytmetyka

uzupełnieniowy

(radix-complement) 〈

β

,D/D

H

〉

•

niestandardowy i nieredundantny zbiór cyfr na pozycji najwy szej,

D

H

= {–

α

,–

α

+1

,…,0,1, …, (

β

–1–

α

)}, 2

α

=

β

Systemy liczenia

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SL–

VI

Reprezentacje systematyczne liczb

Reprezentacje stałoprzecinkowe
– stałobazowe (i uzupełnieniowe) ustalone poło enie przecinka pozycyjnego

327145,123

10

, 0,0000000000031459

10

, 327145,123

8

, 01011101011

2

Reprezentacje zmiennoprzecinkowe – zło enie pól

•

znak liczby

(sign),

•

znacznik

(significand) (cz

ułamkowa (fraction), mantysa (mantissa)),

•

wykładnik

(exponent) pot gi bazy (radix) (podstawy)

o

podstawa (baza) – domniemana (stała dla systemu).

+3,27145123

E5 ( = 3,27145123

10

×

10

5

),

−

31415,9

10

×

10

–4

, 1,01001

2

×

2

1011

Reprezentacje resztowe

(residue number system, RNS)

•

reprezentacja liczby – wektor reszt wzgl dem stałych bazy RNS

•

tylko liczby całkowite

56

{2 , 3, 5, 7}

= {56 mod 2, 56 mod 3, 56 mod 5, 56 mod 7}={0, 2, 1, 0}

Reprezentacje logarytmiczne – znak + logarytm warto ci bezwzgl dnej

Systemy liczenia

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SL–

VII

Dodawanie i odejmowanie w systemach stałobazowych

β

β

}

,...,

,

,...,

{

,

}

,...,

,

,...,

{

0

1

1

0

1

1

m

k

m

k

y

y

y

y

x

x

x

x

−

−

−

−

=

=

Y

X

,

i

i

i

y

x

D

∈

,

⇓ (

i

i

s

D

∈

)

Y

X

Y

X

±

=

⇔

=

±

−

−

−

−

β

β

}

,...,

,

,...,

{

}

,...,

,

,...,

{

0

1

1

0

1

1

m

k

m

k

s

s

s

s

s

s

s

s

Rekurencyjna reguła wyznaczania cyfr sumy lub ró nicy

istnieje tylko wtedy, gdy istnieje ogólne rozwi zanie równania:

i

i

i

i

i

s

c

c

y

x

+

±

=

±

±

+

1

β

,

i

i

i

i

s

y

x

D

∈

•

standardowy zbiór cyfr: D

i

= D = {0,1,…,

β

−

1} – rozwi zaniem jest:

1

1

=

=

≥

±

±

<

±

±







±

±

±

±

=

+

+

i

i

i

i

i

i

i

i

i

i

i

i

i

i

i

c

c

c

y

x

c

y

x

c

y

x

c

y

x

s

β

β

β

m

•

niestandardowy zbiór cyfr D = {0, d

1

,d

2

,…,d

β

−

1

,…; d

i

mod

β

=

i }

k

c

k

c

y

x

s

i

i

i

i

i

=

±

±

=

+

1

β

m

,

D

∈

β

mod

k

Systemy liczenia

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SL–VIII

Jednoznaczno reprezentacji stałobazowej

T

WIERDZENIE

Reprezentacja liczby w standardowym systemie stałobazowym jest unikatowa.

D o w ó d . Niech

β

}

0

|

,...,

,

,...,

,

0

,...,

0

{

0

1

≠

=

−

j

m

j

j

x

x

x

x

x

X

. Jako, e

0

≠

j

x

, wi c

m

j

j

j

j

j

j

−

+

−

≤

=

−

<

−

β

β

1

min

max

Z

N

P

X

X

.

Z kolei, warto dowolnej liczby

1

+

j

X

)

1

(

1

≥

+

j

x

mo na obliczy jako

1

1

1

1

+

+

+

≤

+

+

=

j

j

j

j

s

j

x

β

λ

X

X

.

Poniewa |

λ

j+1

|=1, zatem

!

!

1

1

1

0

+

+

+

+

≤

+

≤

=

−

<

j

j

j

j

j

s

j

x

β

β

λ

X

X

. Skoro jednak

rozpi to zakresu liczb

j

s

<

X

nie przekracza

β

j+1

, zatem

j

s

j

≤

+

≠

X

X

1

.

Wynika st d dalej, e

2

1

2

1

j

j

j

j

x

x

X

X

≠

⇒

≠

, bo wówczas albo

2

1

2

2

1

1

1

1

2

1

2

1

gdy

}

,

..

,.

,

0

{

}

,

..

,.

,

{

j

j

m

j

m

j

j

j

j

j

x

x

x

x

x

x

x

x

>

−

−

=

−

−

−

−

−

X

X

albo

2

1

2

2

1

1

2

1

1

1

2

1

gdy

}

,

..

,.

,

{

}

,

..

,.

,

0

{

j

j

m

j

j

j

m

j

j

j

x

x

x

x

x

x

x

x

<

−

−

=

−

−

−

−

−

X

X

Gdy za

2

1

2

1

2

1

to

,

:

s

s

j

j

i

i

x

x

j

i

s

X

X

X

X

−

=

−

=

≤

<

∀

, co dowodzi tezy.

Działania

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

DZ–

I

Dodawanie i odejmowanie w systemach naturalnych

W standardowym systemie naturalnym (

λ

i

= 1) równaniem dodawania jest

i

i

i

i

i

s

c

c

y

x

+

±

=

±

±

+

1

β

przy tym

})

1

,

0

{

}

1

,

0

{

(

}

1

,...,

1

,

0

{

,

,

1

∈

⇒

∈

⇒

−

∈

+

i

i

i

i

i

c

c

s

y

x

β

oraz







≤

±

±

≤

≤

±

±

≤

±

±

±

±

=

+

β

β

β

β

m

m

i

i

i

i

i

i

i

i

i

i

i

i

i

i

c

y

x

c

y

x

c

y

x

c

y

x

s

c

0

0

gdy

gdy

}

,

1

{

}

,

0

{

}

,

{

1

x

k–1

x

k–2

…

x

–m+3

x

–m+2

x

–m+1

x

–m

±

y

k–1

y

k–2

…

y

–m+3

y

–m+2

y

–m+1

y

–m

c

–m+1

s

–m

c

–m+2

s

–m+1

c

–m+3

s

–m+2

s

–m+3

c

k–2

…

c

k–1

s

k–2

c

k

s

k–1

Działania

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

DZ–II

Dodawanie wieloargumentowe w systemach naturalnych (1)

•

dodawanie jest przemienne i ł czne, wi c:

∑

∑

∑

∑

−

=

−

=

−

=

−

=

+

+

=

+

+

+

=

+

+

+

1

0

1

0

1

0

1

0

...)

(

...

...

n

i

i

i

i

i

n

i

i

i

n

i

i

i

n

i

i

i

z

y

x

z

y

x

Z

Y

X

β

β

β

β

•

ka da suma warto ci cyfr na ka dej pozycji i mo e by zapisana jako

liczba wielocyfrowa o wadze takiej jak waga pozycji (

β

i

):

i

i

i

i

i

i

u

v

r

z

y

x

+

+

+

=

+

+

+

+

+

1

2

2

...

...

β

β

przy tym

}

1

,...,

1

,

0

{

,

,

,

,...,

,

2

1

−

∈

+

+

β

i

i

i

i

i

i

r

v

u

z

y

x

•

je li suma oryginalna X+Y+Z+... ma m składników, to suma:

...

...

...)

(

...

1

2

1

1

0

...

0

V

R

U

r

v

u

r

v

u

Z

Y

X

n

i

i

i

n

i

i

i

n

i

i

i

n

i

i

i

i

i

+

+

=

+

+

+

=

+

+

=

+

+

∑

∑

∑

∑

+

=

=

−

=

+

=

β

β

β

β

ma około 1+log

β

m składników, czyli znacznie mniej ni X+Y+Z+..

Działania

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

DZ–III

Dodawanie wieloargumentowe w systemach naturalnych (2)

i

i

i

i

i

i

u

v

r

z

y

x

+

+

+

=

+

+

+

+

+

1

2

2

...

...

β

β

przy tym

}

1

,...,

1

,

0

{

,

,

,

,...,

,

2

1

−

∈

+

+

β

i

i

i

i

i

i

r

v

u

z

y

x

Je li liczba składników jest

≤

β

+1

, suma jest dwucyfrowa:

β

β

β

<

−

+

+

+

≤

−

+

+

+

=

+

k

z

y

x

k

z

y

x

k

u

v

i

i

i

i

i

i

i

i

...

0

gdy

}

...

,

{

}

,

{

1

,

dodawanie mo na wykona dwuetapowo:

•

niezale nie obliczy sum na ka dej pozycji

•

doda otrzymane liczby dwucyfrowe

x

k–1

x

k–2

x

k–3

…

x

–m+3

x

–m+2

x

–m+1

x

–m

y

k–1

y

k–2

y

k–3

…

y

–m+3

y

–m+2

y

–m+1

y

–m

…

…

…

…

…

…

…

…

±

z

k–1

z

k–2

z

k–3

…

z

–m+3

z

–m+2

z

–m+1

z

–m

u

k–1

u

k–2

u

k–3

…

u

–m+3

u

–m+2

u

–m+1

u

–m

v

k

v

k–1

v

k–2

…

v

–m+4

v

–m+3

v

–m+2

v

–m+1

s

k

s

k–1

s

k–2

…

…

s

–m+3

s

–m+2

s

–m+1

s

–m

Działania

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

DZ–IV

Sekwencyjny algorytm mno enia w systemie naturalnym

Mno na (multiplicand)

|

}

,

,...,

{

|

1

1

β

p

p

s

a

a

a

A

−

+

−

−

=

,

Mno nik (multiplier)

|

}

,

,...,

{

|

1

1

β

m

m

k

x

x

x

X

−

+

−

−

=

,

∑

∑

−

−

=

−

−

=

=













⋅

=

⋅

1

1

)

(

k

m

i

i

i

k

m

i

i

i

A

x

x

A

X

A

β

β

algorytm pisemny – dodawanie skalowanych iloczynów cz ciowych (

0

=

−

m

S

)

)

(

1

A

x

S

S

i

i

i

i

β

+

=

+

, i =

−

m,

−

m+1,...,k

−

1

algorytm dodaj-przesu (add-and-shift) – skalowanie sum cz ciowych

i

i

i

S

P

−

=

β

)

(

1

1

A

x

P

P

i

i

i

+

=

−

+

β

X

A

x

A

P

P

k

m

i

i

i

m

k

k

⋅

=

+

=

∑

−

−

=

−

1

}

{

β

β

Działania

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

DZ–V

Konstrukcja tabliczki mno enia w systemach naturalnych (1)

•

dla 1

≤

k

≤

β

−1

cyframi iloczynu k

⋅

(

β

−1

) s k

−1

i

β

– k (suma równa

β

– 1):

0

1

)

(

)

1

(

)

(

)

1

(

)

1

(

β

β

β

β

β

β

k

k

k

k

k

−

+

−

=

−

+

−

=

−

•

iloczyn jest przemienny (a*b=b*a) – wystarczy wypełni od przek tnej

•

odległo ci liczb w rz dach i kolumnach s stałe

•

przek tna: x

2

=(x–1)(x+1)+1 (np. 3

2

=(3–1)*(3+1)+1=4*2+1

↓

+2

↓

+3

↓

+4

↓

+5

…

ββββ

2

3

4

5

…

β−

2

β−

1

→

+2

2

4

6

8

…

1(

β−

2)

–2

←

→

+3

3

6

9

3*4

5*3

…

2(

β−

3)

–3

←

→

+4

4

8

4*3 5*3+1

…

3(

β−

4)

–4

←

→

+5

5

5*3

6

6

6

*

*

*

4

4

4

+

+

+

1

1

1

…

…

–5

←

…

…

…

…

…

…

…

…

β−

2

… (

β−

4)4 (

β−

3)2

β−

1 1(

β−

2) 2(

β−

3) 3(

β−

4) 4(

β−

5)

… (

β−

3)2 (

β−

2)1

↑

–2

↑

–3

↑

–4

↑

–5

…



suma cyfr

β−

1

W

NIOSEK

: wi kszo oblicze mo na wykona bez przeniesie …

Działania

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

DZ–VI

Konstrukcja tabliczki mno enia w systemach naturalnych (2)

•

odległo ci przek tnych te s stałe

•

przek tne „styczne wierzchołkami” odliczane od przek tnej głównej

te mo na wypełnia niemal automatycznie, bo (n

2

=1+3+5+...+2n

−

1)

x

2

=(x–2)(x+2)+4=(x–2)(x+2)+1+3

(np. 4

2

=(4–2)*(4+2)+4=6*2+4)

x

2

=(x–3)(x+3)+9=(x–3)(x+3)+1+3+5 (np. 5

2

=(4–2)*(4+2)+4=6*2+4)

a

2

−

1

...−

1

−

3

a

2

...−

1

a

2

−−−−

1

...

x

2

−

1

...−

...−

...−

...−

1

x

2

...−

...−

...−

...−

1

−−−−

3

x

2

−−−−

1

…

x

2

−−−−

4

…

−−−−

1

x

2

−−−−

9

−−−−

3

−−−−

5

•

pozostałe przek tne s odległe od siebie kolejno o 2, o 4, o 6 itd.

x (x–1) =(x+1)(x–2)+2,

(np. 5*4=6*3+2)

x (x–1) =(x+2)(x–3)+2+4, ...

(np. 5*4=7*2+2+4)

Działania

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

DZ–VII

Tabliczki mno enia w systemach naturalnych

5

2

3

4

6

2

3

4

5

7

2

3

4

5

6

2

4 — —

2

4 — — —

2

4 — — — —

3

11 14 —

3

10 13 — —

3

6 12 — — —

4

13 22 31

4

12 20 24 —

4

11 15 22 — —

5

14 23 32 41

5

13 21 26 34 —

6

15 24 33 42 51

9

2

3

4

5

6

7

8

11

2

3

4

5

6

7

8

9

A

2

4 — — — — — —

2

4 — — — — — — — —

3

6 10 — — — — —

3

6 9 — — — — — — —

4

8 13 17 — — — —

4

8 11 15 — — — — — —

5

11 16 22 27 — — —

5

A 14 19 23 — — — — —

6

13 20 26 33 40 — —

6

11 17 22 28 33 — — — —

7

15 23 31 38 46 54 —

7

13 1A 26 32 39 45 — — —

8

17 26 35 44 53 62 71

8

15 22 2A 37 44 51 59 — —

9

17 25 33 41 4A 58 66 74 —

A

19 28 37 46 55 64 73 82 91

Działania

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

DZ–VIII

Dzielenie całkowite

X, D, Q, R – liczby całkowite

X – dzielna (dividend), D

≠

0 – dzielnik (divisor)

X = Q

⋅

D + R, |R| < |D|

→

Q – iloraz (quotient), R – reszta (remainder) z dzielenia X przez D

Równanie dzielenia mo e mie 2 rozwi zania spełniaj ce warunek |R| < |D|

|R

1

–R

2

| = |D| , 0<

−

R

1

, R

2

< |D|

X – R

i

= Q

i

⋅

D

dzielenie znakowane (signed division) – znak reszty jest taki jak znak dzielnej
dzielenie modularne (modulus division) – znak reszty jest zawsze dodatni

Działania

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

DZ–IX

Dzielenie sekwencyjne

W systemie pozycyjnym o danej podstawie

β

dzieln i dzielnik mo na łatwo skalowa przez pot gi podstawy,
ergo
iloraz mo na obliczy z dowoln dokładno ci

β

–p

.

Je li

β

}

,...,

,

,...,

{

0

1

1

m

k

x

x

x

x

X

−

−

=

oraz

β

}

,...,

,

,...,

{

0

1

1

s

l

d

d

d

d

D

−

−

=

,

to obliczony z dokładno ci

β

–p

iloraz X/D jest równy:

i

l

k

p

i

i

p

l

k

l

k

q

q

q

q

q

Q

β

β

∑

+

−

−

=

−

−

+

−

=

=

1

0

1

}

,...

,...,

,

{

przy tym reszta jest nie wi ksza ni D*

β

–p

.

Algorytm oblicze jest iteracyjny

– na podstawie ju obliczonego przybli enia z dokładno ci

β

–s

obliczamy przybli enie z dokładno ci

β

–(s+1)

(kolejn cyfr ilorazu)

Działania

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

DZ–X

Przybli enia ilorazu

Pierwszym przybli eniem ilorazu jest

s

s

s

s

q

Q

q

β

β

=

=

1

,

}

0

,...,

0

,

{

takie, e

D

q

X

D

q

s

s

s

s

β

β

)

1

(

+

<

≤

,

D

D

q

X

R

s

s

s

β

β

<

−

=

≤

1

0

Dokładniejsze przybli enie to

1

1

1

,

2

,

1

}

0

,...,

,

{

−

−

−

+

=

=

s

s

s

s

s

s

q

Q

Q

q

q

β

β

takie, e

D

q

D

Q

X

R

D

q

s

s

s

s

s

1

1

1

,

1

1

1

)

1

(

−

−

−

−

+

<

−

=

≤

β

β

,

D

D

q

R

R

s

s

s

1

1

1

1

2

0

−

−

−

<

−

=

≤

β

β

Kolejnymi przybli eniami ilorazu s zatem

i

s

i

s

i

s

i

s

q

Q

Q

−

−

+

+

=

β

,

1

,

takie, e

D

q

D

Q

X

R

D

q

i

s

i

s

i

s

i

i

s

i

s

−

−

−

−

+

<

−

=

≤

β

β

)

1

(

,

,

D

D

q

R

R

i

s

i

s

i

s

i

i

−

−

−

+

<

−

=

≤

β

β

1

0

co po skalowaniu (

1

−

−

=

s

i

i

i

R

r

β

) prowadzi do nierówno ci parametrycznej

D

D

q

r

r

i

s

i

i

<

−

=

≤

−

+

β

1

0

Konwersja podstawy

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

KP–1

Pozycyjne rozwini cie liczby w systemie naturalnym

Jednoznaczn reprezentacj liczby X

≥

0 w systemie naturalnym o podstawie

β

jest rozwi zanie równania

X

x

x

x

x

x

k

m

i

i

i

m

k

=

=

∑

−

−

=

−

−

−

1

1

0

1

}

,...,

,

,...,

{

β

β

, gdzie

}

1

...,

,

1

,

0

{

−

∈

β

i

x

Metoda tablicowa

1. Obliczamy wszystkie potrzebne dodatnie pot gi podstawy

β

n

< X i tyle pot g

ujemnych, aby zapewni wymagan dokładno reprezentacji
problem: warto ci pot g ujemnych s przybli one, np. 0,1

10

= 0,(00011)

2

2. Obliczamy cyfry metod „odejmij i porównaj”:

X

n–1

= X – q

β

n

> 0 ale X – ( q+1)

β

n

< 0, to x

n-1

=q

,

X

n–2

= X

n–1

– p

β

n–1

, …

Bezpo rednie obliczenie

Znamy tabliczk mno enia w systemie ródłowym z zapisem warto ci

w systemie docelowym (na przykład konwersja na system dziesi tny)

Konwersja podstawy

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

KP–2

Generowanie reprezentacji pozycyjnej

Dla cz ci całkowitej X

I

oraz ułamkowej X

F

liczby X mamy odpowiednio

)]}

(

...

[

{

1

2

2

1

0

1

0

−

−

−

=

+

+

+

+

=

=

∑

k

k

k

i

i

i

I

x

x

x

x

x

x

X

β

β

β

β

β

)...]}

(

...

[

{

1

1

1

2

1

1

1

1

m

m

m

i

i

i

F

x

x

x

x

x

X

−

−

+

−

−

−

−

−

−

−

−

=

+

+

+

+

=

=

∑

β

β

β

β

β

Regularno wyra e prowadzi do algorytmów generowania reprezentacji:

•

uniwersalnych – niezale nych od systemu,

•

dynamicznych – niezale nych od warto ci liczby.

Algorytmy musz uwzgl dnia specyfik arytmetyki systemu pozycyjnego

•

ujemn podstaw w systemach negabazowych

•

ujemne cyfry w systemach SD

•

ujemn wag /cyfry na najwy szej pozycji w systemach uzupełnieniowych

Najprostsze s algorytmy dla reprezentacji naturalnych

Konwersja podstawy

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

KP–3

Konwersja cz ci całkowitej liczby

A mod b – reszta z dzielenia A przez b

A div b – iloraz całkowity A przez b

)...)]}

(

...

(

[

{

1

2

3

2

1

0

0

−

−

+

+

+

+

+

=

=

k

k

I

x

x

x

x

x

x

I

X

β

β

β

β

β

β

mod

0

0

I

x

=

)...])]

(

...

[

(

[

div

1

2

4

3

2

1

1

0

−

−

+

+

+

+

+

=

=

k

k

x

x

x

x

x

x

I

I

β

β

β

β

β

β

β

mod

1

1

I

x

=

)...)])

(

...

(

[

(

div

1

2

5

4

3

2

2

1

−

−

+

+

+

+

+

=

=

k

k

x

x

x

x

x

x

I

I

β

β

β

β

β

β

β

mod

2

2

I

x

=

…
cyframi rozwini cia cz ci całkowitej X

I

liczby X w systemie o podstawie

β

s :

I

0

1

1

,

int

div

,

mod

X

I

I

I

I

I

x

j

j

j

j

j

=

=

=

=

−

+

β

β

β

Je li I

r

= 0, to x

r+1

= 0, I

r+1

= 0 itd.

(kolejne cyfry lewostronnego rozwini cia s zerami)

Konwersja podstawy

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

KP–4

Algorytm konwersji cz ci całkowitej liczby

Procedura (na podstawie rozwini cia Hornera)

1. Podziel liczb przez podstaw systemu docelowego

β

2. Otrzymana reszta jest kolejn cyfr rozwini cia pozycyjnego
3. Otrzymany iloraz ponownie poddaj procedurze
4. Powtarzaj dopóki nie uzyskasz ilorazu równego 0

Algorytm wyznaczania reprezentacji cz ci całkowitej (A naturalne)

0. X

(0)

= A

; podstaw warto ci pocz tkowe

i = 0

1. X

(i+1)

= int(X

(i)

/

β

)

; iloraz całkowity

2. x

i

= X

(i)

–

β

X

(i+1)

; reszta

3. i ++

; zwi ksz i

4. if X

(i+1)

≠

0 goto 1

; powtarzaj dopóki iloraz

≠

0

Konwersja podstawy

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

KP–5

Konwersja cz ci ułamkowej liczby

int A – cz

całkowita liczby A

)...)]}

(

...

(

[

{

1

1

1

3

1

2

1

1

1

1

m

m

F

x

x

x

x

x

F

X

−

−

+

−

−

−

−

−

−

−

−

+

+

+

+

+

=

=

β

β

β

β

β

1

1

int

F

x

β

=

−

)...])]}

(

...

[

(

[

1

1

1

4

1

3

1

2

1

2

1

1

m

m

x

x

x

x

x

F

x

F

−

−

+

−

−

−

−

−

−

−

−

−

+

+

+

+

+

=

=

−

β

β

β

β

β

β

2

2

int

F

x

β

=

−

)...)])

(

...

(

[

(

1

1

1

5

1

4

1

3

1

3

2

2

m

m

x

x

x

x

x

F

x

F

−

−

+

−

−

−

−

−

−

−

−

−

+

+

+

+

+

=

=

−

β

β

β

β

β

β

3

3

int

F

x

β

=

−

cyframi rozwini cia cz ci ułamkowej X

F

liczby X w systemie o podstawie

β

s

1

,

1

,

int

F

1

1

<

=

<

−

=

=

−

+

−

X

F

x

F

F

F

x

j

j

j

j

j

β

β

Je li F

r

= 0, to x

–(r+1)

= 0, F

r+1

= 0 itd.

(kolejne cyfry prawostronnego rozwini cia s zerami)

Je li F

r

= F

r–k

to rozwini cie jest okresowe (okres ma k cyfr)

Konwersja podstawy

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

KP–6

Algorytm konwersji cz ci ułamkowej liczby

Procedura (na podstawie rozwini cia rekurencyjnego)

1. Pomnó ułamek przez podstaw systemu docelowego

β

2. Cz

całkowita iloczynu kolejn cyfr rozwini cia pozycyjnego

3. Cz

ułamkow iloczynu ponownie poddaj procedurze

4. Powtarzaj tak długo a :

a) uzyskasz wymagan dokładno

β

–m

(odpowiedni liczb cyfr),

b) otrzymasz iloczyn równy 0,
c) wykryjesz okresowo (pojawi si taki sam ułamek jak wcze niej).

Reprezentacja cz ci ułamkowej (A < 1) z dokładno ci

β

– m

0. X

(0)

= A, x

0

= 0

; podstaw warto ci pocz tkowe

i = 0

1. x

–i

= int(

β

X

(i)

)

; cz

całkowita iloczynu

2. X

(i+1)

=

β

X

(i)

– x

–i

; cz

ułamkowa iloczynu

3. i ++

; zwi ksz i

4. if i

≤

m goto 1

; powtarzaj dopóki mała dokładno

Konwersja podstawy

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

KP–7

Konwersja podstawy w systemach naturalnych

•

działania wykonywane s w systemie ródłowym (o podstawie

ω

)

•

je li podstawa systemu docelowego

β

jest wi ksza od podstawy systemu

ródłowego, to nale y wykonywa mno enie lub dzielenie przez warto

podstawy zakodowan w systemie ródłowym

β

= |{b

p

, …, b

1

, b

0

}

ω

|

•

wyniki {z

s–1

, z

s–1

, …, z

–r

}

β

– w systemie o podstawie

β

(

ω

β

log

k

s

≤

)

Konwersja ułamka okresowego

Zamiana ułamka okresowego na ułamek wymierny













−

+

=













−

+

=

−

−

−

−

−

−

−

−

−

1

1

1

1

)

...

(

...

,

0

1

1

c

c

k

c

c

k

c

k

k

k

z

x

z

x

z

z

x

x

β

β

β

β

β

β

β

x =

β

k

|{x

−1

, … , x

−

k

}|

β

, z =

β

c

|{z

−

k

−

1

, … , z

−

k

−

m

}|

β

k – liczba pozycji cz ci nieokresowej ułamka, c – liczba pozycji okresu

Ułamek sko czony w bazie danej

ω

mo e by okresowy w bazie docelowej

β

za wynikiem konwersji ułamka okresowego mo e by ułamek sko czony.

Konwersja podstawy

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

KP–8

Konwersja ułamka wymiernego w systemach naturalnych

Uwaga

Wynikiem konwersji ułamka wymiernego jest ułamek sko czony lub okresowy

W

ŁA CIWO

konwersji ułamka

Je li ka dy dzielnik podstawy ródłowej

ω

jest dzielnikiem podstawy docelowej

β

, to wynikiem konwersji ułamka sko czonego jest ułamek sko czony

∑

∑

−

=

−

=

−

=

−

=

=

∞

<

∃

⇒

=

⇒

=

∈

∀

1

1

:

]

)

,

(

)

,

(

:

[

i

r

i

i

i

i

m

i

i

i

z

x

r

p

p

NWD

p

p

NWD

p

β

ω

β

ω

P

D o w ó d . Je li F jest ułamkiem sko czonym m-pozycyjnym w bazie

ω

, to

N

∈

−

≤

≤

=

=

=

−

−

=

−

−

−

−

=

∑

∑

A

A

A

x

x

F

m

m

m

i

i

m

i

m

m

i

i

i

,

1

0

,

1

0

1

ω

ω

ω

ω

ω

.

F ma sko czone rozwini cie tak e w bazie

β

, je eli istnieje B

∈

N

i r <

∞

takie,

e

1

0

,

−

≤

≤

=

−

r

r

B

B

F

β

β

. Załó my, e NWD(p,

β

) = 1. Ale wówczas byłoby

m

m

m

r

p

A

p

NWD

p

p

NWD

p

NWD

B

A

=

⇒

=

=

=

)

,

(

)

,

(

&

1

)

,

(

&

ω

β

ω

β

,

wi c rozwini cie F byłoby niesko czone, chyba e A = k p

m

.

Konwersja podstawy

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

KP–9

Konwersja podstawy skojarzonej w systemach naturalnych – przykłady

...

100

15

100

32

100

71

100

56

100

34

100

2

...

10

15

10

32

10

71

10

56

10

34

10

2

...

3215

,

2345671

2

1

0

1

2

3

4

2

0

2

4

6

−

−

−

−

⋅

+

⋅

+

⋅

+

⋅

+

⋅

+

⋅

=

=

⋅

+

⋅

+

⋅

+

⋅

+

⋅

+

⋅

=

8

2

8

1

8

0

8

1

8

2

8

6

2

3

2

0

2

3

2

6

2

2

35

,

347

8

5

8

3

8

7

8

4

8

3

2

101

2

011

2

111

2

100

2

11

101

011

,

111

100

11

=

⋅

+

⋅

+

⋅

+

⋅

+

⋅

=

=

⋅

+

⋅

+

⋅

+

⋅

+

⋅

=

−

−

−

−

16

8

2

4

2

0

2

4

2

8

2

2

2

6

2

3

2

0

2

3

2

6

2

9

2

2

1

0

1

2

3

8

74

,

7

E

4

2

0100

2

0111

2

0111

2

1110

2

0100

0100

0111

,

0111

1110

0100

101

011

,

111

100

011

010

2

101

2

011

2

111

2

100

2

011

2

010

8

5

8

3

8

7

8

4

8

3

8

2

35

,

2347

=

⋅

+

⋅

+

⋅

+

⋅

+

⋅

=

=

=

=

=

⋅

+

⋅

+

⋅

+

⋅

+

⋅

+

⋅

=

=

⋅

+

⋅

+

⋅

+

⋅

+

⋅

+

⋅

=

−

−

−

−

−

−

Przykład (...)

10

→

(...)

8

→

(...)

2

(8

3

=512, 8

2

=64, 8

–1

=0,125, 8

–2

=0,16625)

2

8

2

0

1

2

3

64

1

10

010

000

,

001

010

011

011

02

,

3321

8

2

8

1

8

2

8

3

8

3

2

1

8

2

64

3

512

3

03125

,

1937

=

=

=

⋅

+

⋅

+

⋅

+

⋅

+

⋅

=

⋅

+

+

⋅

+

⋅

+

⋅

=

−

Konwersja podstawy

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

KP–10

Konwersja podstawy skojarzonej w systemach naturalnych

...

)

(

)

(

)

...(

...

)

(

)

(

)

(

)

...(

...

...

3

3

2

2

1

0

0

1

2

2

3

3

4

2

5

2

2

1

0

0

1

2

2

3

4

4

5

2

2

1

1

0

0

1

1

2

2

2

3

4

4

5

5

+

+

+

+

+

+

+

+

+

=

=

+

+

+

+

+

+

+

+

=

=

+

+

+

+

+

+

+

+

=

−

−

−

−

−

−

−

−

−

−

−

β

β

β

β

β

β

β

β

β

β

β

β

β

β

β

β

β

β

β

β

β

β

β

β

β

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

X

a zatem:

∑

∑

∑

−

−

=

−

−

=

+

−

−

+

−

−

=

=

+

+

+

=

1

1

1

1

1

1

)

(

)

(

)

...

(

t

r

j

j

s

j

t

r

j

j

s

js

js

s

s

js

k

m

i

i

i

z

x

x

x

x

β

β

β

β

β

czyli

{

}

{

}

s

r

t

m

k

z

z

z

z

x

x

x

x

β

β

−

−

−

−

=

,...,

,

,...,

,...,

,

,...,

0

1

1

0

1

1

gdzie

}

1

,...,

1

,

0

{

...

1

1

1

−

∈

+

+

+

=

+

−

−

+

s

js

js

s

s

js

j

x

x

x

z

β

β

β

– warto cyfry w (..)

β

↑

s

Zło enie konwersji – (..)

ββββ

↑↑↑↑

k

→

→

→

→

(..)

ββββ

↑↑↑↑

s

(..)

β

↑

k

→

(..)

β

↑

s

⇔

(..)

β

↑

k

→

(..)

β

|| (..)

β

→

(..)

β

↑

s

ω

<

β

s

⇒ zamiast konwersji (..)

ω

→

(..)

β

wygodniej realizowa (..)

ω

→

(..)

β

↑

s

Konwersja podstawy

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

KP–11

Konwersja podstawy w systemach naturalnych – przykłady

157,386

10

→

X

8

→

Z

2

oraz 157,386

10

→

X

9

→

Z

3

(8=2

3

9=3

2

).

I

i

mod 2

3

×2

3

F

i

I

i

mod 3

2

×3

2

F

i

157

0 386

157

0 386

19 5 =x

0

x

-1

=

3 088

17 4 =x

0

x

-1

=

3 474

2 3 =x

1

x

-2

=

0 704

1 8 =x

1

x

-2

=

4 266

0 2 =x

2

x

-3

=

5 632

0 1 =x

2

x

-3

=

2 394

157,386

10

= 235,305...

8

= 10011101,011000101...

2

157,386

10

= 184,342

9

= 12211,101102...

3

.

235,305

8

→

X

10

oraz 235,305

8

→

X

9

→

Z

3

(działania w systemie ósemkowym)

I

i

mod 12

8

×12

8

F

i

I

i

mod 11

8

×3 F

i

235

8

0

305

8

235

8

0 305

8

17

8

7 =x

0

x

-1

=

3

662

8

21

8

4 =x

0

x

-1

=

3 355

8

1

5 =x

1

x

-2

=

10

8

364

8

1 8 =x

1

x

-2

=

4 125

8

0 1 =x

2

x

-3

=

4

610

8

0 1 =x

2

x

-3

=

1 375

8

235,305

8

=157,384...

10

= 184,341...

9

= 12211,101101...

3

.

Konwersja podstawy

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

KP–12

Konwersja ułamka wymiernego na system pozycyjny

•

konwersja licznika i mianownika na system docelowy i dzielenie

•

zgodnie z algorytmem:

o

mno enie przez podstaw systemu docelowego

o

odcinanie cz ci całkowitej uzyskanego iloczynu

10

8

8

61

54

X

→

x

0

=0

0

×12

8

=10

10

x

–1

=8

=10

8

8

8

8

8

61

670

61

60

=

+

x

–2

=9

=11

8

8

8

8

8

61

740

61

47

=

+

x

–3

=7

=7

8

8

8

8

8

61

606

61

57

=

+

…

0,1

10

= 0,00011001100110011…

2

= 0,0(0011)

2

Konwersja podstawy

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

KP–13

Konwersja ułamków okresowych w systemach naturalnych

•

zamiana na ułamek wymierny

•

u ycie rozwini cia niesko czonego – korekcja skróconego rozwini cia

•

automatyczna korekcja okresu podczas mno enia

ułamek wymierny

rozwini cie niesko czone

tylko 0,(xy...z)

β

0,5(37)

10

=

8

10

10

990

532

X

→

0,5(37)

10

→

X

8

0,(386)

10

→

X

7

×8

×8

×8

F

i

×7

F

i

0

0 5 37 37 37 …

0 (386)

x

–1

=

4 2 98 98 96

x

–1

=

2 (702)

x

–1

=

4

10

10

10

10

990

4256

990

296

=

+

2 98 98 98

(704)

x

–2

=

2 3 91 91 84

x

–2

=

4 (928)

x

–2

=

2

10

10

10

10

990

2368

990

388

=

+

3 91 91 91

(932)

x

–3

=

3 1 35 35 28

x

–3

=

6 (524)

x

–3

=

3

10

10

10

10

990

3104

990

134

=

+

1 35 35 35

(530)

Konwersja podstawy

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

KP–14

Konwersja podstawy w systemach stałobazowych

Ka da liczba w systemie stałobazowym ma rozwini cie pozycyjne,

wi c mo e by te rozwini ta wg schematu Hornera

W

NIOSEK

Algorytmy konwersji dla systemu naturalnego mo na stosowa tak e

w dowolnym systemie stałobazowym.

Problem: arytmetyka musi by odpowiednia do wła ciwo ci systemu

Przykład:
157,386

10

→

(..)

SD-8

. (D = { 4 , 3, 2, 1, 0, 1, 2, 3}

I

i

I

i

mod 8

×8

F

i

(!<500)

×8

F

i

157

0 386

0 386

19 5

→

20 3 =x

0

x

-1

=

3 088

x

-1

=

3 088

3 4 =x

1

x

-2

=

0 704 !!

x

-2

=

1 296

0 3 =x

2

x

-3

=

5 632

↑

 x

-3

=

2 368

x

-4

=

3 056

Liczby ujemne

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

INT–1

Reprezentacja znak-moduł

pseudonaturalna – +32,317, –214,554, ...

β

}

,...,

,

,...,

{

||

}

{

0

1

1

m

k

x

x

x

x

s

−

−

=

X

}

1

,

0

{

},

1

...,

,

1

,

0

{

,

)

1

(

1

∈

−

∈

−

=

∑

−

−

=

s

x

x

i

k

m

i

i

i

s

β

β

X

•

dwie reprezentacje zera : „+ 0” i „

−

0”

•

na ograniczonej liczbie pozycji zakres liczb jest symetryczny

•

problem w dodawaniu i odejmowaniu

o

efektywne działanie zale y od znaków

§

komplikacja algorytmu i dłu szy czas wykonania

§

bardziej skomplikowany układ

Liczby ujemne

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

INT–2

System negabazowy

(z baz ujemn )

i

i

w

)

(

β

−

=

,

β

≥2

}

1

...,

,

1

,

0

{

,

)

(

}

,...,

,

,...,

,

{

1

1

0

2

1

−

∈

−

=

=

∑

−

−

=

−

−

−

−

−

β

β

β

i

k

m

i

i

i

m

k

k

x

x

x

x

x

x

x

X

•

znaczna asymetria (dodatnia je li k nieparzyste, ujemna gdy k parzyste)

]

)

(

)

[(

1

1

k

m

Q

β

β

β

β

−

−

−

+

−

=

−

•

znak liczby okre la indeks najbardziej znacz cej pozycji niezerowej k

•

zmiana znaku wykonalna tylko dla około 2/(

β

+1) liczb

•

skomplikowany algorytm i układ

o

aby unikn

odejmowania przeniesienia

i

i

i

i

i

s

c

c

y

x

+

−

±

=

±

±

+

1

)

(

β

wytwarzane s dwa przeniesienia:

1

1

,

)

1

(

+

+

−

=

i

i

i

c

c

β

oraz

1

2

,

+

+

=

i

i

i

c

c

1

1

,

+

+

=

i

i

i

c

c

β

, co daje

1

1

1

2

,

1

,

)

1

(

+

+

+

+

+

−

=

−

−

=

−

i

i

i

i

i

i

i

c

c

c

c

c

β

β

β

Liczby ujemne

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

INT–3

Reprezentacja nadmiarowa – system ze znakowan cyfr (SD)

System stałobazowy (pozycyjny) 〈

β

,

1111

,

D〉

•

zbiór cyfr

d

d

a

a

a

a

a

−

=

≤

−

≤

−

=

,

2

1

},

,

1

,...,

1

,

0

,

1

,...,

{

β

D

a

a

a

a

a

x

x

i

n

m

i

i

i

2

1

},

,

1

,...,

1

,

0

,

1

,...,

{

,

|

|

1

SD

≤

−

≤

−

∈

=

∑

−

−

=

β

β

X

SD

2

1

SD

2

1

}

,...,

,

{

}

,...,

,

{

m

k

k

m

k

k

x

x

x

x

x

x

−

−

−

−

−

−

−

−

−

=

−

−

+

−

=

X

X

X

SD

:







≥

<

=

=

+

+

−

+

+

−

+

−

+

,

0

gdy

,

,

0

gdy

,

0

,

}

,

,...,

,

0

{

1

1

i

i

i

i

m

m

k

x

x

x

x

x

x

x

β

X







<

−

≥

=

=

−

−

−

−

+

−

−

−

−

.

0

gdy

,

,

0

gdy

,

0

,

}

,

,...,

,

0

{

1

1

i

i

i

i

m

m

k

x

x

x

x

x

x

x

β

X

−

+

−

X

X

– wykonalne w systemie SD, jak i w systemie uzupełnieniowym

Konwersja odwrotna mo e by niejednoznaczna – wiele reprezentacji liczby.

Liczby ujemne

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

INT–4

Reprezentacja minimalna w dwójkowym systemie SD

reprezentacja minimalna

}

,

,..,

{

1

1

m

m

k

z

z

z

−

+

−

−

=

Z

– zawieraj ca najwi cej zer

)]

0

(

[

)]

1

(

)

1

(

[

1

1

1

1

1

1

=

∧

=

∨

=

−

−

≤

≤

+

−

−

≤

<

−

≤

<

−

≤

∀

∀

∀

∃

i

i

s

i

m

j

k

j

s

j

k

j

s

k

s

z

z

z

z

D

OWÓD

(dla dwójkowego systemu SD):

•

ci g zawieraj cy izolowan cyfr 1 lub

1

nie daje si minimalizowa

•

izolowany ci g 1 lub

1

,...)

0

,

,...,

,

0

(...,

x

x

jest równowa ny

,...)

0

,

,...,

0

,

(...,

x

x

•

1

,

1

,

,...}

,

,

0

,

{...,

,...}

,

,

,

{...,

=

=

b

z

b

x

z

b

b

x

•

nie da si przekodowa ci gu cyfr 1 lub

1

na najwy szych pozycjach.



reprezentacja kanoniczna – minimalna z wykluczeniem s siaduj cych nie-zer


Jest k reprezentacji liczby –1 oraz k reprezentacji liczby +1

–1 = {0, 0, …, 0, –1} = {0, 0, …, –1, 1} = … = {–1, 1, …, 1, 1}

•

liczb reprezentowanych jest 2

⋅

2

k

, ró nych reprezentacji jest 3

k

Liczby ujemne

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

INT–5

Dwójkowa reprezentacja uzupełnieniowa – intuicja

…rozszerzenie

0

...

0

0

0

0

1

0

0

0

0

0

0

0

0

0

...

0

0

0

0

0

1

1

1

1

1

1

1

1

+2

8

–1

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

0

...

0

0

0

0

0

1

0

0

0

0

0

0

1

+2

7

+1

0

...

0

0

0

0

0

1

0

0

0

0

0

0

0

+2

7

0

...

0

0

0

0

0

0

1

1

1

1

1

1

1

+2

7

–1

0

...

0

0

0

0

0

0

1

1

1

1

1

1

0

+2

7

–2

... ... ... ... ... ... ... ... ... ... ... ... ... ... ...

...

0

...

0

0

0

0

0

0

0

0

0

0

0

1

0

+2

0

...

0

0

0

0

0

0

0

0

0

0

0

0

1

+1

0

...

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

...

1

1

1

1

1

1

1

1

1

1

1

1

1

–1

1

...

1

1

1

1

1

1

1

1

1

1

1

1

0

–2

... ... ... ... ... ... ... ... ... ... ... ... ... ... ...

...

1

...

1

1

1

1

1

1

0

0

0

0

0

1

0

–2

7

+2

1

...

1

1

1

1

1

1

0

0

0

0

0

0

1

–2

7

+1

1

...

1

1

1

1

1

1

0

0

0

0

0

0

0

–2

7

1

...

1

1

1

1

1

0

1

1

1

1

1

1

1

–2

7

–1

1

...

1

1

1

1

1

0

1

1

1

1

1

1

0

–2

7

–2

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

1

...

1

1

1

1

1

0

0

0

0

0

0

0

0

–2

8

1

...

1

1

1

1

0

1

1

1

1

1

1

1

1

Liczby ujemne

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

INT–6

Dziesi tna reprezentacja uzupełnieniowa – intuicja

…rozszerzenie

0

...

0

0

0

0

5

0

0

0

0

0

0

0

0

...

0

0

0

0

4

9

9

9

9

9

9

9

+5

⋅

10

7

–1

... ... ... ... ... ... ... ... ... ... ... ... ... ...

...

0

...

0

0

0

0

0

5

0

0

0

0

0

9

+5

⋅

10

6

+2

0

...

0

0

0

0

0

5

0

0

0

0

0

0

+5

⋅

10

6

+1

0

...

0

0

0

0

0

4

9

9

9

9

9

9

+5

⋅

10

6

–1

0

...

0

0

0

0

0

4

9

9

9

9

9

0

+5

⋅

10

6

–2

... ... ... ... ... ... ... ... ... ... ... ... ... ...

...

0

...

0

0

0

0

0

0

0

0

0

0

0

2

+2

0

...

0

0

0

0

0

0

0

0

0

0

0

1

+1

0

...

0

0

0

0

0

0

0

0

0

0

0

0

0

9

...

9

9

9

9

9

9

9

9

9

9

9

9

–1

9

...

9

9

9

9

9

9

9

9

9

9

9

8

–2

... ... ... ... ... ... ... ... ... ... ... ... ... ...

...

9

...

9

9

9

9

9

5

0

0

0

0

0

2

–5

⋅

10

6

+2

9

...

9

9

9

9

9

5

0

0

0

0

0

1

–5

⋅

10

6

+1

9

...

9

9

9

9

9

5

0

0

0

0

0

0

–5

⋅

10

6

9

...

9

9

9

9

9

4

9

9

9

9

9

9

–5

⋅

10

6

–1

9

...

9

9

9

9

9

4

9

9

9

9

9

8

–5

⋅

10

6

–2

... ... ... ... ... ... ... ... ... ... ... ... ... ...

...

9

...

9

9

9

9

5

0

0

0

0

0

0

0

–5

⋅

10

7

Liczby ujemne

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

INT–7

Reprezentacja uzupełnieniowa

Jednolita formuła na obliczenie warto ci liczby

∑

−

−

=

−

+

−

=

1

1

)

(

|

|

k

m

i

i

i

k

k

U

x

x

β

β

ϕ

β

X

,

gdzie

))

1

2

(

sgn

1

(

)

(

1

2

1

1

+

−

+

=

−

−

β

ϕ

k

k

x

x

– funkcja znaku liczby

Rozszerzenie niesko czone (arytmetyczne)

?

β

β

U

p

m

m

k

k

U

m

k

x

x

x

x

x

x

x

x

x

x

x

}

,..,

,.

,...,

,

,...,

,

{...,

}

,...,

,

,...,

{

1

0

1

1

0

1

1

−

−

−

−

−

−

−

=

→

intuicje

325,17

U10

(+325,17

10

) 0..0325,17

U10

325,1

U8

(+325,1

8

) 0..0325,10

U8

674,83

U10

(–325,17

10

) 9..9674,83

U10

452,7

U8

(–325,1

8

) 7..7452,70

U8

Je li wi c

)

1

)(

(

1

−

=

−

β

ϕ

k

e

x

x

, to (zauwa , e

)

)

1

)(

(

e

e

x

x

=

−

β

ϕ

,...}

0

,

,

,...,

,

{...,

1

1

e

m

m

k

e

x

x

x

x

−

+

−

−

=

X

Uwaga: Zauwa my, e poprawne cyfry reprezentacji liczby przeciwnej

otrzymamy przez odejmowanie danej od zera

Liczby ujemne

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

INT–8

Dwójkowa reprezentacja uzupełnieniowa U2

β

=2

⇒

}

1

,

0

{

∈

i

x

⇒

1

1

)

(

−

−

=

k

k

x

x

ϕ

←

(…bit znaku)

System uzupełnieniowy do 2 (2’s complement) (U2)

∑

−

−

=

−

−

−

−

+

−

=

=

2

1

1

2

U

0

1

1

2

U

2

2

|

}

,...,

,

,...,

{

|

k

m

i

i

i

k

k

m

k

x

x

x

x

x

x

X

Rozszerzenie niesko czone liczby w kodzie U2

U2

1

2

1

1

e

,...}

0

,

0

,

,

,...,

,

,

{...,

m

m

k

k

k

x

x

x

x

x

−

+

−

−

−

−

=

X

.

Alternatywna interpretacja

∑

−

−

=

−

−

=

=

1

2

U

0

1

1

2

U

2

|

}

,...,

,

,...,

{

|

k

m

i

i

i

m

k

x

x

x

x

x

X

,

}

0

,

1

{

1

∈

−

k

x

,

}

1

,

0

{

∈

i

x

Liczby ujemne

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

INT–9

Reprezentacja spolaryzowana (liczb całkowitych)

przypisanie reprezentacji naturalnej warto ci pomniejszonej o N (obci

enie)

}

1

,...,

1

,

0

{

0

,

|

}

,

,...,

{

|

1

0

0

1

1

−

∈

<

<

−

=

=

∑

−

=

+

−

β

β

β

i

k

k

i

i

i

N

k

x

N

N

x

x

x

x

X

reprezentacja z obci

eniem N (biased N, excess N, XS-N)

zalety:

•

zakres liczb dodatnich i ujemnych jest niesymetryczny

•

unikatowa reprezentacja zera

•

zgodno uporz dkowania liczb i ich reprezentacji (kodów)

wady:

•

konieczno korekcji wyników działa arytmetycznych

•

problematyczne u ycie w mno eniu lub dzieleniu

reprezentacja spolaryzowana quasisymetryczna (Q =

β

k

– 1 – 2N)

•

z asymetri ujemn

k

N

β

2

1

=

(Q = – 1)

•

z asymetri dodatni

1

2

1

−

=

k

N

β

(Q = + 1)

Liczby ujemne

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

INT–10

Reprezentacja spolaryzowana liczb całkowitych w systemie dwójkowym

N =

2

m–1

N =

2

m–1

−1

2

m

−1

−1

1

1

1

...

1

1

1

2

m

−1

2

m

−1

−2

1

1

1

...

1

1

0

2

m

−1

−1

...

...

...

...

...

...

...

...

...

0

1

0

0

...

0

0

0

1

−1

0

1

1

...

1

1

1

0

...

...

...

...

...

...

...

...

...

−2

m

−1

+1

0

0

0

...

0

0

1

−2

m

−1

+2

−2

m

−1

0

0

0

...

0

0

0

−2

m

−1

+1

•

porz dek liczb zgodny z porz dkiem kodów

•

dodawanie i odejmowanie wymaga korekcji

•

łatwa konwersja na kod U2 i odwrotnie

m

2

0

1

2

1

U2

0

1

2

1

}

,

,...,

),

1

{(

}

,

,...,

,

{

↑

+

−

−

−

−

−

=

x

x

x

x

x

x

x

x

m

m

m

m

1

-

m

2

0

1

2

1

U2

0

1

2

1

)}

1

(

),

1

(

),...,

1

(

,

{

}

,

,...,

,

{

↑

+

−

−

−

−

−

−

−

=

−

x

x

x

x

x

x

x

x

m

m

m

m

Liczby ujemne

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

INT–11

Dwójkowa reprezentacja spolaryzowana i uzupełnieniowa

Gdy

1

2

−

=

k

N

jest

∑

∑

−

=

−

−

−

=

−

+

+

−

−

=

−

=

2

0

1

1

1

0

1

2

2

)

1

(

2

2

k

i

i

i

k

k

k

i

k

i

i

N

x

x

x

X

,

⇒

)

1

(

2

0

2

1

U2

0

2

1

}

,...,

,

{

}

,...,

,

{

−

↑

+

−

−

−

−

=

k

k

k

k

k

x

x

x

x

x

x

Gdy

1

2

1

−

=

−

k

N

, to poniewa

∑

−

=

−

=

−

2

0

1

2

)

1

2

(

k

i

i

k

, wi c otrzymamy













−

+

−

−

=

−

+

=

−

−

=

∑

∑

∑

−

=

−

−

−

=

−

−

−

−

=

+

2

0

1

1

2

0

1

1

1

1

0

2

)

1

(

2

2

)

1

(

2

)

1

2

(

2

k

i

i

i

k

k

k

i

i

i

k

k

k

k

i

i

i

N

x

x

x

x

x

X

⇒

1

)

1

(

2

2

1

U2

2

1

}

,...,

,

{

}

,...,

,

{

−

−

↑

+

−

−

−

−

−

−

=

−

k

m

k

k

m

k

k

x

x

x

x

x

x

Liczby ujemne

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

INT–12

Bezpo rednia konwersja liczby na system uzupełnieniowy

Poniewa wagi / warto ci wszystkich cyfr reprezentacji uzupełnieniowych
oprócz najwy szej s dodatnie, wi c:

a) konwersja cz ci całkowitej wymaga nast puj cego post powania:

1) kolejne ilorazy maj taki znak jak liczba przetwarzana,

2) warunek stopu: iloraz równy warto ci cyfry rozszerzenia (0 lub –1)

b) konwersja ułamka wła ciwego

– zamiana na posta 0+f lub –1+f

– konwersja dodatniej cz ci ułamkowej f – jak dla liczb dodatnich

Liczby ujemne

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

INT–13

Dopełnienie liczby i liczba przeciwna

Dopełnienie liczby

β

}

,...,

,

,...,

{

0

1

1

m

k

x

x

x

x

−

−

=

X

(digit-complement)

β

β

}

)

1

(

:

,...,

,

,...,

{

0

1

1

i

i

m

k

x

x

x

x

x

x

−

−

=

=

−

−

X

Q

X

X

=

−

−

=

+

β

β

β

}

1

,...,

1

{

X

X

=

i

0

Q

=

Je li jest wykonalne działanie

Y

X

+

, to mamy

Y

X

Y

X

Q

Y

X

Q

Y

X

+

=

+

−

=

−

−

=

−

)

(

)

(

Odwrotno addytywna liczby

β

}

,...,

,

,...,

{

0

1

1

m

k

x

x

x

x

−

−

=

X

– liczba przeciwna

0

X

X

X

=

+

⇔

=

−

−

~

}

~

,...,

~

,

~

,...,

~

{

~

0

1

1

β

m

k

x

x

x

x

Odwrotno addytywna jest relacj równowa no ci

Je li istnieje liczba Q

~

, to

X

Q

X

Q

Q

X

0

X

+

=

−

+

=

−

=

~

~

i wtedy

)

~

(

Q

Y

X

Y

X

+

+

=

−

Liczby ujemne

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

INT–14

Reprezentacje dziesi tne kodowane dwójkowo

•

do binarnego zakodowania jednej z

β

cyfr potrzeba log

2

β

 bitów

•

jest

1

6

1

0

=

⋅

⋅

⋅

⋅

⋅

⋅

⋅

⋅

⋅

=

mo liwo ci kodowania cyfr 0…9

Kod BCD (Binary Coded Decimal)

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

0

1

2

3

4

5

6

7

8

9 –

–

–

–

–

–

Kod BCD+3 (Excess-3, XS-3) i jego dopełnienie (~1930)

–

–

–

0

1

2

3

4

5

6

7

8

9 –

–

–

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
1111 1110 1101 1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001 0000

–

–

–

9

−

0 9

−

1

9

−

2

9

−

3

9

−

4

9

−

5

9

−

6

9

−

7

9

−

8

9

−

9

–

–

–

•

samodopełnianie – negacja bitów cyfry

→

dopełnienie warto ci cyfry

Systemy komplementarne*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–1

Systemy komplementarne

Dla liczb z ograniczonego zakresu 0

≤

| X |

≤

| R |

liczb przeciwn mo e reprezentowa jej uzupełnienie do stałej R

X

X

X

R

X

−

=

⇔

−

=

~

~

Uzupełnianie jest odwracalne

X

X

=

~

~

, a poniewa

0

|

~

|

~

=

⇒

=

R

0

R

wi c tak e

X

0

X

R

X

−

=

−

=

~

~

Systemy komplementarne (

}

1

,

1

,...,

1

{

−

−

−

=

β

β

β

Q

, ulp

={0,...,0,1})

•

do podstawy (radix-complement), uzupełnieniowe (pełne) –

ulp

Q

R

Q

=

−

=

~

o

nie istnieje reprezentacja R = Q + ulp

o

unikatowa reprezentacja zera:

R

0

=

~

nie ma reprezentacji

•

do cyfry (digit-complement), dopełnieniowe, u.niepełne (diminished r-c.)

0

Q

R

Q

=

−

=

~

,

Q

0

R

0

=

−

=

~

o

R = Q

→

dwie reprezentacje zera: 0 oraz Q

Systemy komplementarne*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–2

Reprezentacja liczby przeciwnej

X

Q

X

−

=

−

−

=

=

−

−

β

β

}

)

1

(

:

,...,

,

,...,

{

0

1

1

i

i

m

k

x

x

x

x

x

x

– dopełnienie liczby X

liczb przeciwn (odwrotno addytywn ) – je li istnieje – reprezentuje kod

)

(

~

Q

R

X

X

R

X

−

+

=

−

=

•

w systemie uzupełnieniowym (pełnym) R = Q + ulp, wi c

ulp

X

X

R

X

+

=

−

=

~

•

w systemie dopełnieniowym (niepełnym) R = Q, wi c

X

X

R

X

=

−

=

~

W systemie uzupełnieniowym liczba

ulp

Q

=

~

zawsze istnieje, ergo

⇒ ka de odejmowanie mo na zast pi dodawaniem

Q

Y

X

Q

R

Y

X

Y

X

Y

X

~

)

(

~

+

+

=

−

+

+

=

+

=

−

Systemy komplementarne*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–3

Wła ciwo ci systemów komplementarnych

Reprezentacja liczb dodatnich – jak w kreuj cym systemie naturalnym

! Q nie jest miar asymetrii w systemie uzupełnieniowym.

Je eli podstawa systemu

β

jest liczb nieparzyst , to

•

w systemach dopełnieniowych musi wyst pi niewielka asymetria

•

w systemach uzupełnieniowych zakres liczb mo e by symetryczny

•

trudne wykrycie znaku – niezb dne testowanie wszystkich pozycji

Je li podstawa systemu

β

jest liczb parzyst , to

•

w systemach dopełnieniowych zakres liczb mo e by symetryczny

•

w systemach uzupełnieniowych musi wyst pi niewielka asymetria

•

mo liwe łatwe wykrycie znaku („+” gdy

β

<

−

1

2

k

x

, „–” gdy

β

≥

−

1

2

k

x

),

⇒ w systemach pełnych ujemna asymetria.

⇒ podstawa systemu komplementarnego

β

jest zwykle liczb parzyst

•

uzupełnieniowy do podstawy

β

(U2/ 2’s complement, U10/ 10’s compl.)

•

dopełnieniowy do cyfr

β

−1

(U1/ 1s’ complement/ D1)

Systemy komplementarne*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–4

Dodawanie i odejmowanie w systemach uzupełnieniowych

W systemach naturalnych reprezentacj liczby wi kszej (mniejszej) o jednostk
(ulp=

β

–m

o reprezentacji {0,…,0,1}) od danej jest wynik pozycyjnego dodania

(odj cia) ulp do (od) tej liczby.

•

przeniesienie z pozycji najwy szej wiadczy o niewykonalno ci działania

Brak argumentów przeciw stosowaniu reguły w systemach uzupełnieniowych
(reprezentacj liczby przeciwnej jest 0 –X}

•

dodawanie i odejmowanie jednostki mo na wykona zgodnie z reguł

(i)

1

+

±

=

±

±

i

i

i

i

i

c

s

c

y

x

β

,

•

dodanie jednostki

β

–m

do liczby najwi kszej ujemnej

}

1

,

1

,...,

1

{

−

−

−

β

β

β

o warto ci „–

β

–m

”, zgodnie z reguł (i) daje w wyniku poprawne 0

•

odj cie jednostki

β

–m

od 0, zgodnie z reguł (i) daje

}

1

,

1

,...,

1

{

−

−

−

β

β

β

•

problem wykonalno ci działania

o

jednopozycyjne rozszerzenie zakresu zapewnia poprawno wyniku
ka dego dodawania lub odejmowania wykonanego zgodnie z reguł (i)

Systemy komplementarne*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–5

Reprezentacja uzupełnieniowa w systemie pełnym i niepełnym

podstawa

β

parzysta

U2

D1/U1

1

/

2

β

k

−

β

–m

1

/

2

β

–1

β

–1

β

–1

...

β

–1

β

–1

β

–1

1

/

2

β

k

−

β

–m

1

/

2

β

k

−

2

β

–m

1

/

2

β

–1

β

–1

β

–1

...

β

–1

β

–1

β

–2

1

/

2

β

k

−

2

β

–m

…

…

…

…

…

…

…

…

…

+

β

–m

0

0

0

...

0

0

1

+

β

–m

0

0

0

0

...

0

0

0

+0

−

β

–m

β

–1

β

–1

β

–1

...

β

–1

β

–1

β

–1

−0

−

2

β

–m

β

–1

β

–1

β

–1

...

β

–1

β

–1

β

–2

−

β

–m

…

…

…

…

…

…

…

…

…

−

1

/

2

β

k

+

β

–m

1

/

2

β

0

0

...

0

0

1

−

1

/

2

β

k

+

2

β

–m

−

1

/

2

β

k

1

/

2

β

0

0

...

0

0

0

−

1

/

2

β

k

+

β

–m

R

=

β

k

R

=

β

k

−

β

–m

⇒

≥

0

β

U

X

∑

−

−

=

−

−

+

=

2

1

1

k

m

i

i

i

k

k

U

x

x

β

β

β

X

,

⇒

<

0

β

U

X

∑

−

−

=

−

−

+

−

=

2

1

1

k

m

i

i

i

k

k

U

x

R

x

β

β

β

X

Systemy komplementarne*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–

6

Warto liczby w systemie komplementarnym

∑

−

−

=

−

+

−

=

1

1

)

(

|

|

k

m

i

i

i

k

U

x

R

x

β

ϕ

β

X

,

gdzie

))

1

2

(

sgn

1

(

)

(

1

2

1

1

+

−

+

=

−

−

β

ϕ

k

k

x

x

– funkcja znaku liczby, R =

β

k

–

δ⋅β

– m

(

δ

= 0 w systemie uzupełnieniowym lub 1 w dopełnieniowym), sk d

m

k

k

m

i

i

i

k

k

U

x

x

x

−

−

−

−

=

−

+

+

−

=

∑

β

ϕ

δ

β

β

ϕ

β

)

(

)

(

|

|

1

1

1

X

Rozszerzenie niesko czone (arytmetyczne)

?

}

,..,

,.

,...,

,

,...,

,

,...,

{

}

,...,

,

,...,

{

1

0

1

1

1

0

1

1

p

m

m

k

k

s

m

k

x

x

x

x

x

x

x

x

x

x

x

x

−

−

−

−

−

−

−

−

=

→

intuicje

325

U10

(+325

10

)

00325,00

U10

325

U9

(+325

10

)

00325,00

U9

675

U10

(–325

10

)

99675,00

U10

674

U9

(–325

10

)

99674,99

U9

Je li wi c

)

1

)(

(

1

−

=

−

β

ϕ

k

e

x

x

, to (zauwa , e

)

)

1

)(

(

e

e

x

x

=

−

β

ϕ

•

system uzupełnieniowy:

,...}

0

,

,

,...,

,

{...,

1

1

e

m

m

k

e

x

x

x

x

−

+

−

−

=

X

,

•

system dopełnieniowy:

,...}

,

,

,...,

,

{...,

1

1

e

e

m

m

k

e

x

x

x

x

x

−

+

−

−

=

X

Systemy komplementarne*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–7

Dwójkowe systemy uzupełnieniowe

β

=2

⇒

}

1

,

0

{

∈

i

x

⇒

1

1

)

(

−

−

=

k

k

x

x

ϕ

←

(bit znaku!)

System uzupełnieniowy do 2 (2’s complement) (U2)

∑

−

−

=

−

−

−

−

+

−

=

=

2

1

1

2

U

0

1

1

2

U

2

2

|

}

,...,

,

,...,

{

|

k

m

i

i

i

k

k

m

k

x

x

x

x

x

x

X

Rozszerzenie niesko czone liczby w kodzie U2

U2

1

2

1

1

e

,...}

0

,

0

,

,

,...,

,

,

{...,

m

m

k

k

k

x

x

x

x

x

−

+

−

−

−

−

=

X

.

System dopełnieniowy do „1” (1’s complement) (D1/U1)

∑

−

−

=

−

−

−

−

−

+

−

−

=

=

2

1

1

1

U

0

1

1

1

U

2

)

2

2

(

|

}

,...,

,

,...,

{

|

k

m

i

i

i

m

k

k

m

k

x

x

x

x

x

x

X

Rozszerzenie niesko czone liczby w kodzie U1

1

1

1

1

2

1

1

e

,...}

,

,

,

,...,

,

,

{...,

U

k

k

m

m

k

k

k

x

x

x

x

x

x

x

−

−

−

+

−

−

−

−

=

X

.

Konwersja U1

↔

U2: |

X

U1

| – |

X

U2

| =

m

k

k

x

ulp

x

−

=

2

Systemy komplementarne*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–8

Kod uzupełnieniowy do 2 (U2) i dopełnieniowy do „1” (niepełny, D1)

U2

D1/U1

+

2

m

−

1

−

1 0

1

1

...

1

1

1

+

2

m

−

1

−

1

+

2

m

−

1

−

2 0

1

1

...

1

1

0

+

2

m

−

1

−

2

+

2

0

0

0

...

0

1

0

+

1

0

0

0

...

0

0

1

+1

0 0

0

0

...

0

0

0

+0

−

1

1

1

1

...

1

1

1

−0

−

2

1

1

1

...

1

1

0

−1

−

2

m

−

1

+

1 1

0

0

...

0

0

1

−

2

m

−

1

+2

−

2

m

−

1

1

0

0

...

0

0

0

−

2

m

−

1

+

1

R

=−

2

m

−

1

R

=−

2

m

−

1

+

1

∑

−

−

=

−

−

−

+

−

=

=

2

1

0

1

1

2

|

}

,...,

,

,...,

{

|

|

|

k

m

i

i

i

k

m

k

x

R

x

x

x

x

x

X

Systemy komplementarne*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–9

Kod uzupełnieniowy do 10 (U10) i dopełnieniowy do „9” (niepełny, D9/U9)

U10

D9/U9

+5∗1

0

k

−

1

−

1 (0)

4

9

9

…

9

9

9

+5∗1

0

k

−

1

−

1

+5∗1

0

k

−

1

−

2 (0)

4

9

9

…

9

9

8

+5∗1

0

k

−

1

−

2

…

…

…

…

…

…

…

…

+

2

(0)

0

0

0

…

0

0

2

+

1

(0)

0

0

0

…

0

0

1

+1

0

0

0

0

0

…

0

0

0

+0

−

1

(9)

9

9

9

…

9

9

9

−0

−

2

(9)

9

9

9

…

9

9

8

−1

…

…

…

…

…

…

…

…

−5∗1

0

k

−

1

+

1 (9)

5

0

0

…

0

0

2

−5∗1

0

k

−

1

+

2

−5∗1

0

k

−

1

(9)

5

0

0

…

0

0

1

−5∗1

0

k

−

1

+

1

R

=−1

0

k

−

1

R

=−1

0

k

−

1

+

1

∑

−

−

=

−

−

−

+

−

=

=

1

1

0

1

1

)

(

|

}

,...,

,

,...,

{

|

|

|

k

m

i

i

i

k

m

k

x

R

x

x

x

x

x

β

ϕ

X

Systemy komplementarne*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–10

Kod uzupełnieniowy do 8 (U8) i dopełnieniowy do „7” (niepełny, D7/U7)

U9

D7/U7

+4∗8

k

−

1

−

1 (0)

3

7

7

...

7

7

7

+4∗8

k

−

1

−

1

+4∗8

k

−

1

−

2 (0)

3

7

7

...

7

7

6

+4∗8

k

−

1

−

2

…

…

…

…

…

…

…

…

+

2

(0)

0

0

0

...

0

0

2

+2

+

1

(0)

0

0

0

...

0

0

1

+1

0

0

0

0

0

...

0

0

0

+0

−

1

(7)

7

7

7

...

7

7

7

−0

−

2

(7)

7

7

7

...

7

7

6

−1

…

…

…

…

…

…

…

…

−4∗8

k

−

1

+

1 (7)

4

0

0

...

0

0

2

−4∗8

k

−

1

+

2

−4∗8

k

−

1

(7)

4

0

0

...

0

0

1

−4∗8

k

−

1

+

1

R

=−8

k

−

1

R

=−8

k

−

1

+

1

∑

−

−

=

−

−

−

+

−

=

=

1

1

0

1

1

)

(

|

}

,...,

,

,...,

{

|

|

|

k

m

i

i

i

k

m

k

x

R

x

x

x

x

x

β

ϕ

X

R =

β

k

–

ε⋅

ulp

Liczby i wielomiany*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–1

Liczby zespolone (1)

Liczba zespolona – para liczb (

a, b), której przypisano warto zespolon

|(

a, b)| = a + i b, i

2

=−

1

Dodawanie i odejmowanie

[

a + i b]

±

[

a + i b] = [ a

±

c] + i [ b

±

d]

Mno enie

[

a + i b]

⋅

[

c + i d] = [ a c

−

b d ] + i [ a d

+

b c ]

Dzielenie

[

a + i b] / [ c + i d] = [ a + i b] [ c

−

i d] / [ c + i d] [ c

−

i d] =

= { [

a c

+

b d ] + i [ a d

+

b c ] } / [ c

2

+ d

2

]

Liczby i wielomiany*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–2

Liczby zespolone (2)

Posta wykładnicza













+

+

+

+

=

+

2

2

2

2

2

2

b

a

b

i

b

a

a

b

a

ib

a

wi c je li podstawimy

2

2

b

a

z

+

=

,

)

/

arctan(

a

b

x

=

, to

a + i b = z ( cos x + i sin x ) = z e

i x

Wzór Laplace’a

e

i

π

+ 1 = 0

Wzór de’Moivre’a-Laplace’a

(

e

i x

)

n

= ( cos

x + i sin x )

n

= cos

n x + i sin n x = e

i n x

Liczby i wielomiany*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–3

Wielomiany (1)

∑

=

−

−

=

+

+

+

+

=

n

i

i

i

n

n

n

n

n

x

a

x

a

x

a

x

a

x

a

x

W

0

0

0

1

1

1

1

)

(

...

)

(

A

LGORYTM DZIELENIA

Ka dy wielomian mo na zapisa w postaci

)

(

)

(

)

(

)

(

)

1

(

)

(

)

(

)

(

x

R

x

Q

x

P

x

W

k

k

k

n

n

−

−

+

=

Q

(k)

(

x) – dzielnik wielomianu (stopnia k)

R

(k–1)

(

x) – reszta z dzielenia (stopnia ni szego ni k)

W

NIOSEK

1:

)

(

)

(

)

(

)

(

0

)

(

)

1

(

0

)

(

x

W

x

P

x

x

x

W

n

n

n

+

−

=

−

W

NIOSEK

2:

Je li

x

i

s pierwiastkami wielomianu (

W

(n)

(

x

i

) = 0), to

)

(

)

)...(

)(

(

)

(

)

(

2

1

)

(

x

P

x

x

x

x

x

x

a

x

W

s

n

s

n

n

−

−

−

−

=

gdzie

P

(n–s)

(

x) – dzielnik nierozkładalny na czynniki liniowe.

Liczby i wielomiany*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–4

Wielomiany (2)

R

OZKŁAD WIELOMIANU NA CZYNNIKI

W

NIOSEK

3:

Całkowite pierwiastki wielomianu o współczynnikach całkowitych

s podzielnikami wyrazu wolnego

a

0

=

a

n

x

1

x

2

…

x

s

.

W

NIOSEK

4:

Mamy

∑

=

−

−

−

−

=

+

+

+

+

=

n

i

i

n

i

n

n

n

n

n

n

x

a

x

a

x

a

x

a

a

x

W

x

0

0

1

1

1

1

)

(

...

)

(

wi c pierwiastki wymierne wielomianu o współczynnikach całkowitych

s podzielnikami wyrazu najwy szego

a

n

=

a

0

x

1

x

2

…

x

s

.

Liczby i wielomiany*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–5

Wielomian i wielomian podstawy

Wielomian (polynomial)

W

n

= {

a

n

,

a

n–1

, …

a

1

,

a

0

}:

a

i

– parametry,

x – zmienna

0

0

1

1

1

1

...

)

(

x

a

x

a

x

a

x

a

x

W

n

n

n

n

n

+

+

+

+

=

−

−

∑

=

=

n

i

i

i

n

x

a

x

W

0

)

(

Wielomian podstawy (radix polynomial) – reprezentacja stałobazowa jednolita

Z

= {z

n

, z

n–1

, … z

1

, z

0

}: z

i

– zmienne,

β

– parametr

0

0

1

1

1

1

...

)

(

β

β

β

β

β

z

z

z

z

Z

n

n

n

n

+

+

+

+

=

−

−

∑

=

=

=

n

i

i

i

z

Z

Z

0

)

(

β

β

reprezentacja standardowa (pozycyjna) – 0

≤

z

i

≤

β

−1

Liczby i wielomiany*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–6

Algebra wielomianów i algebra liczb

Algebra wielomianów

∑

∑

=

=

=

+

=

+

n

i

i

i

n

i

i

i

i

n

b

n

a

x

s

x

b

a

x

W

x

W

0

0

)

(

)

(

)

(

i

i

i

b

a

s

+

=

Algebra liczb – reprezentacja pozycyjna (stałobazowa standardowa)

algorytm dodawania:

∑

∑

=

=

=

+

=

+

n

i

i

i

n

i

i

i

i

s

y

z

Y

Z

0

0

)

(

)

(

)

(

β

β

β

β

1

,

0

,

1

1

=

−

+

+

=

⇒

≥

+

+

=

+

+

=

⇒

<

+

+

+

+

i

i

i

i

i

i

i

i

i

i

i

i

i

i

i

i

c

c

y

z

s

c

y

z

c

c

y

z

s

c

y

z

β

β

β

Liczby i wielomiany*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–7

Obliczenia – schemat Hornera

Warto wielomianu mo na obliczy jako

))]}

(

...

(

[

{

)

(

1

3

2

1

0

0

)

(

n

n

n

i

i

i

n

a

x

a

x

a

x

a

x

a

x

a

x

a

x

W

+

+

+

+

+

+

=

=

−

=

∑

zło ono obliczeniowa

•

schemat klasyczny – suma iloczynów przez pot gi zmiennej

o

n dodawa ,

o

n mno e ,

o

n–1 oblicze pot g,

o

pami

pot g

•

schemat Hornera – suma iloczynów przez zmienn

o

n dodawa

o

n mno e ,

o

zb dna pami

Liczby i wielomiany*

© Janusz Biernat,

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

SK–8

Szybkie obliczanie warto ci liczby – schemat Hornera

liczby całkowite

n

n

n

i

i

i

n

z

z

z

z

z

z

z

z

Z

β

β

β

β

β

β

+

+

+

+

=

=

=

∑

=

...

}

,

,...,

{

2

2

1

0

0

0

1

obliczanie rekurencyjne

0

1

2

1

0

}

...

]

)

{[(

z

z

z

z

z

z

Z

n

n

n

n

i

i

i

+

+

+

+

+

=

=

−

−

=

∑

β

β

β

β

β

β

liczby ułamkowe

m

m

m

i

i

i

m

m

z

z

z

z

z

z

z

Z

−

−

−

−

−

−

−

−

=

−

+

−

−

+

+

+

=

=

=

∑

β

β

β

β

β

β

...

}

,

,...,

{

2

2

1

1

1

1

1

obliczanie rekurencyjne – warto w postaci ułamka wymiernego

}

]

...

)

{[(

1

2

1

1

m

m

m

m

i

i

i

z

z

z

z

z

Z

−

+

−

−

−

−

−

−

=

+

+

+

+

=

=

∑

β

β

β

β

β

β