OAK W4 Arytmetyka

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Organizacja i Architektura

Komputerów

Arytmetyka komputerów

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Alfabet: 0, 1

Dane w komputerach s

reprezentowane wył

cznie przy

yciu alfabetu dwójkowego (binarnego)

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Bity, bajty, słowa

Bity s

grupowane w wi

ksze zespoły o długo

cej pot

liczby 2:

–

tetrada

: 4 bity (

nibble

)

–

bajt

: 8 bitów

–

bajt

: 8 bitów

–

słowo

: 16, 32, 64 lub 128 bitów

–

podwójne słowo

(

doubleword

)

–

półsłowo

(

halfword

)

Długo

ść

słowa zale

y od

organizacji

komputera

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Kody liczbowe

2
3

3
4

4
5

5
6

6
7

10100111100

10100111100
1211122

1211122
110330

110330
20330

20330
10112

10112
3623

3623

(

)

(

)

dwójkowy (binarny)

Podstawy używane w

systemach cyfrowych

7
8

8
9

10
11

11
12

12
13

13
14

14
15

15
16

3623

3623
2474

2474
1748

1748
1340

1340
1009

1009
938

938
7C1

7C1
6BA

6BA
5E5

5E5
53C

53C

(

)

(

)

ktal

talny

dziesi

dziesię

ętny

tny

szesnastkowy, heksadecymalny,

szesnastkowy, heksadecymalny,
‘hex’

‘hex’

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Kod szesnastkowy HEX

Powszechnie
u

ywany przez

programistów
programuj

cych w

zyku asemblera

Cyfra HEX

kod binarny

0000

0001

0010

0011

0100

Skraca długo

ść

notacji liczby

Łatwa konwersja na
kod NKB i odwrotnie

da tetrada

reprezentuje cyfr

szesnastkow

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Konwersja HEX – radix 10

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Konwersja binarna – HEX

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Kod BCD

BCD (

binary coded decimal

)

–

da cyfra dziesi

tna jest

reprezentowana jako 4 bity

–

kod opracowany dla
wczesnych kalkulatorów

cyfra
dziesi

tna BCD

0 0000
1 0001
2

0010

0011

0100

wczesnych kalkulatorów

–

przykład: 359

= 0011 0101 1001

bcd

–

kod łatwy do zrozumienia
przez człowieka, niewygodny
dla komputerów

0100

0101

0110

0111

1000

1001

Kody od 1010 do 1111
nie s

ywane

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Porz

dek bajtów w pami

Problem

–

Pami

ęć

jest zwykle adresowana bajtami

–

Jak zapisa

w pami

ci słowo 32-bitowe ?

8 bit

8 bitów

ów

0x13579BDF

łł

owo 32

owo 32--

bitowe

w kodzie HEX

1248

1249

1250

1251

...

8 bit

8 bitów

ów

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Kolejno

ść

bajtów w pami

Rozwi

zanie

–

podziel słowo na bajty

–

zapisz kolejne bajty w kolejnych komórkach

8 bitów

0x13579BCF

każda cyfra

HEX

reprezentuje

tertadę, zatem

dwie cyfry

tworzą bajt

1248

1249

1250

1251

...

1 bajt tutaj

następny
bajt tutaj

kolejny bajt

tutaj

ostatni bajt

tutaj

8 bitów

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Kolejno

ść

bajtów

cd.

W jakiej kolejno

ci zapisywa

bajty?

–

Zaczynaj

c od najbardziej znacz

cego (“

big

”

end

...

0x13

1248

1249

1250

1251

...

0x13579BDF

0x13

0x57

0x9B

0xDF

kierunek

analizy

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Kolejno

ść

bajtów

cd.

W jakiej kolejno

ci zapisywa

bajty?

–

Zaczynaj

c od najmniej znacz

cego (“

little

”

end

...

0xDF

1248

1249

1250

1251

...

0x13579BDF

0x13

0x57

0x9B

0xDF

kierunek

analizy

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Kolejno

ść

bajtów

cd.

Stosuje si

dwa sposoby zapisu słów w pami

Big Endian

–

most significant byte

lowest address

–

store least significant byte in highest address

–

store least significant byte in highest address

Little Endian

–

store

least significant byte

lowest address

–

store most significant byte in highest address

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Kolejno

ść

bajtów

cd.

Wybór wersji kolejno

ci zapisu bajtów zale

y od

konstruktorów procesora

–

Big Endian

Motorola 680x0 (Amiga/Atari ST/Mac)

IBM/Motorola PowerPC (Macintosh)

MIPS (SGI Indy/Nintendo 64)

Motorola 6800

–

Little Endian

Intel 80x86/Pentium (IBM PC)

Rockwell 6502 (Commodore 64)

MIPS (Sony Playstation/Digital DECstation)

–

Niektóre procesory (np. MIPS) mo

na konfigurowa

zarówno w

trybie Big Endian jak i Little Endian

sza Szkoła Informatyki Stosowanej i Zarz

dzania

ALU

Jednostka arytmetyczno-logiczna (

ALU – arithmetic-logic unit

)

wykonuje operacje arytmetyczne na liczbach w kodzie dwójkowym

ALU jest centralnym blokiem komputera; wszystkie inne bloki
funkcjonalne słu

żą

do wła

ciwej obsługi ALU

Proste ALU wykonuje operacje na liczbach całkowitych (

integer

)

Proste ALU wykonuje operacje na liczbach całkowitych (

integer

)

Bardziej zło

one ALU mo

e wykonywa

operacje

zmiennoprzecinkowe FP na liczbach rzeczywistych

Najcz

ęś

ciej ALU_INT i ALU_FP (

FPU – Floating Point Unit

) s

wykonane jako dwa osobne bloki cyfrowe

–

FPU mo

e by

wykonane jako osobny układ scalony (koprocesor)

–

FPU mo

e by

wbudowane do procesora

sza Szkoła Informatyki Stosowanej i Zarz

dzania

ALU – wej

cia i wyj

cia

• CU – układ sterowania (Control Unit)

• Registers – rejestry wbudowane do CPU

• Flags – wska

niki, znaczniki stanu, flagi, warunki: zespół wska

ników

bitowych okre

laj

cych specyficzne wła

ciwo

ci wyniku operacji

(zero, znak, przeniesienie itp.)

sza Szkoła Informatyki Stosowanej i Zarz

dzania

ALU – symbol logiczny

Kod operacji pochodzi z
układu sterowania (CU)

Liczba bitów wyniku jest
taka sama jak liczba bitów
argumentów (operandów)
– w tym przykładzie

operacja

– w tym przykładzie
wynosi 32

ALU nie tylko generuje bity
wska

ników, ale tak

uwzgl

dnia poprzedni stan

wska

ników

wynik
operacji

ALU

wska

niki

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Wieloznaczno

ść

informacji

Co oznacza poni

szy zapis?

10010111

• Liczb

całkowit

bez znaku: 151

• Liczb

całkowit

bez znaku: 151

• Liczb

całkowit

w kodzie znak-moduł: - 23

• Liczb

całkowit

w kodzie uzupełnie

do dwóch: - 105

• Znak w rozszerzonym kodzie ASCII (IBM Latin 2):

• Kod operacji procesora x86:

XCHG AX,DI

To zale

y od kontekstu

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Liczby całkowite bez znaku

ywane s

tylko cyfry 0 i 1

{ }

∑

−

∈

∑

kod ten bywa nazywany NKB

(naturalny kod binarny)

zakres reprezentacji liczb dla
słowa n-bitowego wynosi:

<0, 2

n – 1

dla n = 8: <0, 255>

dla n = 16: <0, 65 535>

Przykłady:

00000000 = 0

00000001 = 1

00101001 = 41

10000000 = 128

11111111 = 255

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Kod znak-moduł (ZM)

Najbardziej znacz

cy bit

oznacza znak

0 oznacza liczb

dodatni

1 oznacza liczb

ujemn

Przykład

+18 = 00010010








−

∑

−

gdy

+18 = 00010010

−

18 = 10010010

Problemy

Układy arytmetyczne musz

osobno rozpatrywa

bit znaku

i moduł
Wyst

puj

dwie reprezentacje

zera:

+0 = 00000000

−

0 = 10000000






−

∑

−

gdy

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Kod uzupełnie

do 2 (U2)

Najbardziej znacz

cy bit

oznacza znak liczby

0 – liczba dodatnia

1 – liczba ujemna

Tylko jedna reprezentacja

Przykłady:

+3 = 00000011

+2 = 00000010

Tylko jedna reprezentacja
zera:

+0 = 00000000

Ogólna posta

U2:

∑

−

+2 = 00000010

+1 = 00000001

+0 = 00000000

-1 = 11111111

-2 = 11111110

-3 = 11111101

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Konwersja NKB – U2

liczba

binarna

ujemna

liczba

dodatnia

uzupełnienie

0 1
1 0

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Zalety kodu U2

Jedna reprezentacja zera

Układy arytmetyczne (ALU) maj

prostsz

budow

(wyka

emy to pó

niej)

Negacja (zmiana znaku liczby) jest bardzo prosta:

3 = 00000011

uzupełnienie do 1(negacja boolowska)

11111100

dodanie 1

11111101

−

3 = 11111101

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Kod U2 – ilustracja geometryczna

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Wada kodu U2

Zakres reprezentowanych liczb jest niesymetryczny

najmniejsza liczba:

−

(minint)

najwi

ksza liczba: 2

−

1 (maxint)

dla n=8

najmniejsza liczba:

−

128

najwi

ksza liczba: +127

dla n=16

najmniejsza liczba:

−

32 768

najwi

ksza liczba: +32 767

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Negacja w U2 – przypadki specjalne

0 =

00000000

negacja bitowa

11111111

dodaj 1 do LSB

wynik

1 00000000

przepełnienie jest ignorowane

przepełnienie jest ignorowane
wi

−0 = 0

√√√√

− 128 =

10000000

negacja bitowa

01111111

dodaj 1 do LSB

wynik

10000000

c −(− 128) = − 128

Wniosek:

nale

y sprawdza

bit znaku

po negacji
(powinien si

zmieni

)

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Konwersja długo

ci słowa w U2

Liczby dodatnie uzupełnia si

wiod

cymi zerami

+18 =

00010010

+18 = 00000000 00010010

Liczby ujemne uzupełnia si

wiod

cymi jedynkami

−

18 =

10010010

−

18 = 11111111 10010010

Ogólnie bior

c, powiela si

bit MSB (bit znaku)

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Dodawanie i odejmowanie w U2

Obydwie operacje wykonuje si

ywaj

c zwykłego

dodawania liczb dwójkowych

Nale

y sprawdza

bit znaku, aby wykry

nadmiar

(overflow)

Odejmowanie wykonuje si

przez negowanie odjemnej i

dodawanie:

a −b = a + (− b)

Do realizacji dodawania i odejmowania potrzebny jest
zatem tylko

układ negacji bitowej i sumator

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Układ dodawania i odejmowania U2

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Mno

enie

Mno

enie liczb dwójkowych jest znacznie

bardziej zło

one od dodawania i odejmowania

Podstawowy algorytm jest taki sam jak przy
pi

miennym mno

eniu liczb:

miennym mno

eniu liczb:

–

okre

la si

iloczyny cz

stkowe dla ka

dej cyfry

mno

nika

–

kolejne iloczyny cz

stkowe nale

y umieszcza

przesuni

ciem o jedn

pozycj

(kolumn

) w lewo

–

nale

y doda

do siebie iloczyny cz

stkowe

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Przykład mno

enia

(liczby bez znaku)

1011

mno

na (11 w kodzie dziesi

tnym)

x 1101

mno

nik (13 w kodzie dziesi

tnym)

1011

iloczyny cz

stkowe

0000

Uwaga: je

li bit mno

nika jest równy 1,

1011

iloczyn cz

stkowy jest równy mno

nej,

1011

iloczyn cz

stkowy jest równy mno

nej,

1011

w przeciwnym przypadku jest równy 0

10001111

wynik mno

enia (143 w kodzie dziesi

tnym)

Uwaga #1:

wynik ma podwójn

długo

ść

; potrzebujemy słowa

o podwójnej precyzji

Uwaga #2:

powy

szy algorytm funkcjonuje tylko dla liczb bez

znaku; je

li przyj

ąć

kod U2 mno

na = − 5,

mno

nik = − 3, natomiast iloraz wynosiłby − 113,

co oczywi

cie jest nieprawd

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Układ mno

enia liczb bez znaku

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Przykład mno

enia liczb bez znaku

wynik mno

enia

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Mno

enie liczb bez znaku

cd.

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Mno

enie liczb ze znakiem

Prosty algorytm podany wcze

niej nie działa

Rozwi

zanie 1

–

zamieni

czynniki ujemne na dodatnie

–

pomno

liczby korzystaj

c z podanego wcze

niej

–

pomno

liczby korzystaj

c z podanego wcze

niej

algorytmu

–

li znaki czynników (przed wykonaniem negacji)

były ró

ne, zanegowa

iloczyn

Rozwi

zanie 2

–

algorytm Booth’sa

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Algorytm Booth’sa

Q-1

dodatkowy bit

(przerzutnik) pami

taj

najmniej znacz

cy bit

rejestru Q opuszczaj

cy ten

rejestr przy przesuni

ciu w

prawo

Przesuni

cie arytmetyczne w

prawo

– przesuni

cie z

powieleniem bitu znaku

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Przykład działania metody Booth’sa

iloczyn: 3 x 7 = 21 testowane bity: 10 A:=A

01 A:=A+M

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Algorytm Booth’sa

(znak dowolny)

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Dzielenie

Dzielenie liczb dwójkowych jest znacznie bardziej skomplikowane
od mno

enia

Liczby ujemne sprawiaj

spore kłopoty (Stallings, s. 341

342)

Podstawowy algorytm podobny do dzielenia liczb na papierze:
kolejne operacje przesuwania, dodawania lub odejmowania

Przykład: dzielenie liczb bez znaku:

Iloraz

001111

1011

00001101

10010011

1011

001110

1011

100

Iloraz
(Quotient)

Dzielna
(Dividend)

Reszta
(Remainder)

Reszty
cz

stkowe

(Partial
Remainders)

Dzielnik
(Divisor)

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Liczby rzeczywiste

Liczby z cz

ęś

ułamkow

na je zapisa

korzystaj

c z kodu NKB i dodatkowo

znaków ‘

’ oraz ‘.’

1001.1010 = 2

+ 2

-1

+ 2

-3

=9.625

1001.1010 = 2 + 2 +2 + 2 =9.625

Problem: gdzie znajduje si

kropka dziesi

tna?

W stałym miejscu?

–

rozwi

zanie niedobre z punktu widzenia metod numerycznych

Na zmiennej pozycji?

–

jak poda

informacj

o miejscu poło

enia kropki?

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Liczby zmiennoprzecinkowe (FP)

przesuni

wykładnik
(exponent)

mantysa (significand or mantissa)

Warto

ść

liczby: +/

1. mantysa x 2

wykładnik

Podstawa 2 jest ustalona i nie musi by

przechowywana

Poło

eniu punktu dziesi

tnego jest ustalone: na lewo od

najbardziej znacz

cego bitu mantysy

sza Szkoła Informatyki Stosowanej i Zarz

dzania

FP – mantysa

Mantysa jest zapisana w kodzie U2

Wykładnik jest zapisany z przesuni

ciem (excess or

biased notation)

–

np. przesuni

cie równe 127 oznacza:

–

8-bitowe pole wykładnika

–

zakres liczb 0-255

–

od przesuni

tego wykładnika nale

y odj

ąć

127 aby otrzyma

prawdziw

warto

ść

–

zakres warto

ci wykładnika -127 to +128

sza Szkoła Informatyki Stosowanej i Zarz

dzania

FP – normalizacja

Liczby FP s

zwykle normalizowane, tzn. wykładnik jest

tak dobierany, aby najbardziej znacz

cy bit (MSB)

mantysy był równy 1

Poniewa

bit ten jest zawsze równy 1, nie musi by

przechowywany. Dlatego 23-bitowe pole mantysy w

przechowywany. Dlatego 23-bitowe pole mantysy w
rzeczywisto

ci odpowiada mantysie 24-bitowej, z cyfr

na najbardziej znacz

cej pozycji (mantysa mie

ci si

zatem w przedziale od 1 do 2

Uwaga:

w notacji naukowej FP (Scientific notation) liczby

normalizowane inaczej, tak aby mantysa miała jedn

znacz

cyfr

przed kropk

dziesi

np. 3.123 x 10

sza Szkoła Informatyki Stosowanej i Zarz

dzania

FP – przykład

pozycje mantysy

uzupełniane s

zerami

1,1010001 x 210100 = 0 10010011 10100010000000000000000

- 1,1010001 x 210100 = 1 10010011 10100010000000000000000

1,1010001 x 2-10100 = 0 01101011 10100010000000000000000

- 1,1010001 x 2-10100 = 1 01101011 10100010000000000000000

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Zakres reprezentacji liczb FP

Dla formatu 32-bitowego

8-bitowy wykładnik
+/

256

≈

1.5 x 10

Dokładno

ść

–

efekt nierównomiernego pokrycia osi liczb
rzeczywistych (zmienna warto

ść

LSB mantysy)

–

23-bitowa mantysa: 2

-23

≈

1.2 x 10

–

około 6 pozycji dziesi

tnych

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Zakresy liczb FP i U2

(format 32-bitowy)

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Standard IEEE 754

Dwa warianty: 32- i 64-bitowy format liczb

8- lub 11-bitowy wykładnik (bias = 127 lub 1023)

IEEE 754 dopuszcza ponadto tzw. formaty rozszerzone (extended
formats) dla oblicze

rednich w systemach cyfrowych

sza Szkoła Informatyki Stosowanej i Zarz

dzania

ANSI/IEEE Standard Floating-Point Format (IEEE 754)

Short (32-bit) format

8 bits,
bias = 127,

–

126 to 127

23 bits for fractional part
(plus hidden 1 in integer part)

Short exponent range is –127 to 128

but the two extreme values

are reserved for special operands

(similarly for the long format)

Revision (IEEE 754R) is being considered by a committee

The two ANSI/IEEE standard floating-point formats.

Long (64-bit) format

Sign Exponent

Significand

11 bits,
bias = 1023,

–

1022 to 1023

52 bits for fractional part
(plus hidden 1 in integer part)

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Standard IEEE 754

W rzeczywisto

ci standard IEEE 754 jest

bardziej skomplikowany:

–

dodatkowe dwa bity: guard i round
cztery warianty zaokr

glania

–

cztery warianty zaokr

glania

–

liczba dodatnia podzielona przez 0 daje
niesko

czono

ść

–

niesko

czono

ść

dzielona przez niesko

czono

ść

daje

NaN (not a number)

–

niektóre procesory nie s

w pełni zgodne z IEEE

754, skutki s

na ogół niedobre (Pentium bug)

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Some features of ANSI/IEEE standard floating-point formats

Feature

Single/Short

Double/Long

Word width in bits

Significand in bits

23 + 1 hidden

52 + 1 hidden

Significand range

[1, 2 – 2

–23

]

[1, 2 – 2

–52

]

Exponent bits

Exponent bias

127

1023

Zero (

e + bias = 0, f = 0

Denormal

e + bias = 0, f

≠

represents

0.f

–126

e + bias = 0, f

≠

represents

0.f

–1022

Infinity (

∞

)

e + bias = 255, f = 0

e + bias = 2047, f = 0

Not-a-number (NaN)

e + bias = 255, f

≠

e + bias = 2047, f

≠

Ordinary number

e + bias

∈

[1, 254]

∈

[–126, 127]

represents 1.f

e + bias

∈

[1, 2046]

∈

[–1022, 1023]

represents 1.f

min

–126

≅

1.2

–38

–1022

≅

2.2

–308

max

≅

128

≅

3.4

≅

1024

≅

1.8

308

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Arytmetyka FP +/

W arytmetyce FP dodawanie i odejmowanie s

bardziej zło

onymi operacjami ni

mno

enie i

dzielenie (powodem jest konieczno

ść

tzw.

wyrównywania składników)

Etapy dodawania i odejmowania

–

Sprawdzenie zer

–

Wyrównanie mantys (i korekcja wykładników)

–

Dodawanie lub odj

cie mantys

–

Normalizowanie wyniku

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Arytmetyka FP x /

Etapy mno

enia i dzielenia

–

sprawdzenie zer

–

dodawanie/odejmowanie wykładników

–

mno

enie/dzielenie mantys (uwaga na znak)

–

mno

enie/dzielenie mantys (uwaga na znak)

–

normalizacja

–

zaokr

glanie

–

Uwaga:

wszystkie wyniki oblicze

rednich

powinny by

wykonywane w podwójnej precyzji

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Mno

enie FP

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Dzielenie FP

sza Szkoła Informatyki Stosowanej i Zarz

dzania

Podsumowanie

Zapis słów w pami

ci (Endian)

Reprezentacje liczb: NKB, ZM, U2, BCD, HEX

Ogólna charakterystyka ALU

Operacje na liczbach całkowitych bez znaku

Operacje na liczbach całkowitych ze znakiem

Mno

enie – algorytm Booth’sa

Liczby zmiennoprzecinkowe FP

Formaty liczb FP, IEEE 754

Operacje na liczbach FP

Wyszukiwarka

Podobne podstrony:
OAK W4 Arytmetyka
W4 Proces wytwórczy oprogramowania
W4 2010
Statystyka SUM w4
w4 3
W4 2
W4 1
w4 skrócony
w4 orbitale molekularne hybrydyzacja
in w4
w4 Zazębienie ewolwentowe
TM w4

więcej podobnych podstron