Metodyki i techniki programowania 1

2011

B. Butryło

1

Metodyki i techniki

programowania 1

Metodyki i techniki

programowania 1

Politechnika Białostocka

Wydział Elektryczny

Politechnika Białostocka

Wydział Elektryczny

•Kierunek:

elektronika i telekomunikacja

•Studia:

I stopnia

•Kierunek:

elektronika i telekomunikacja

•Studia:

I stopnia

Nowe zagadnienie

Reprezentacja danych

Reprezentacja danych

Metodyki i techniki programowania 1

2011

B. Butryło

2

Reprezentacja danych

3

3

Klasyfikacja kodów

Klasyfikacja kodów

Kody

Kody

Liczbowe

Liczbowe

Alfanumeryczne

Alfanumeryczne

Inne

Inne

EDBIDC, ASCII

EDBIDC, ASCII

ISO-646

ISO-646

ISO-8859

ISO-8859

ISO-10646, Unicode

ISO-10646, Unicode

inne

inne

BCN

BCN

U2 – uzupełnienia do 2

U2 – uzupełnienia do 2

BCD

BCD

2 z 5

2 z 5

dwupiątkowe

dwupiątkowe

1 z N

1 z N

inne

inne

inne

inne

Grey’a

Grey’a

Reprezentacja danych

4

4

Klasyfikacja kodów

Klasyfikacja kodów

Kody

Kody

proste

proste

detekcyjne

detekcyjne

2 z 5

2 z 5

dwupiątkowe

dwupiątkowe

1 z N

1 z N

Grey’a

Grey’a

ASCII

ASCII

ISO-646

ISO-646

ISO-8859

ISO-8859

BCN

BCN

U2 – uzupełnienia do 2

U2 – uzupełnienia do 2

BCD

BCD

ISO-10646, Unicode

ISO-10646, Unicode

Metodyki i techniki programowania 1

2011

B. Butryło

3

Reprezentacja danych

Reprezentacja liczb

Reprezentacja liczb

Reprezentacja danych / reprezentacja liczb

6

6

System dziesiętny pozycyjny

System dziesiętny pozycyjny

d

0

d

0

10

0

d

1

d

1

10

1

d

2

d

2

10

2

d

3

d

3

10

3

d

4

d

4

10

4

d

5

d

5

10

5

d

-5

d

-5

10

-5

d

-4

d

-4

10

-4

d

-3

d

-3

10

-3

d

-2

d

-2

10

-2

d

-1

d

-1

10

-1

,

...

...

P=10
d={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

∑

∑

∑

=

=

−

−

⋅

+

⋅

=

⋅

=

=

I

i

F

f

f

f

i

i

n

n

n

d

d

d

X

liczba

0

1

10

10

10

10

Przykład

X

10

= 472,58

X

10

= 4·10

2

+ 7·10

1

+ 2·10

0

+ 5·10

-1

+ 8·10

-2

= 400 + 70 + 2 + 0,5 + 0,08

i=0, 1, 2, ..., I

f=1, 2, 3, ..., F

Metodyki i techniki programowania 1

2011

B. Butryło

4

Reprezentacja danych / reprezentacja liczb

7

7

System dwójkowy pozycyjny

System dwójkowy pozycyjny

d

0

d

0

2

0

d

1

d

1

2

1

d

2

d

2

2

2

d

3

d

3

2

3

d

4

d

4

2

4

d

5

d

5

2

5

d

-5

d

-5

2

-5

d

-4

d

-4

2

-4

d

-3

d

-3

2

-3

d

-2

d

-2

2

-2

d

-1

d

-1

2

-1

,

...

...

P=2
d={0, 1}

∑

∑

∑

=

=

−

−

⋅

+

⋅

=

⋅

=

=

I

i

F

f

f

f

i

i

n

n

n

d

d

d

X

liczba

0

1

10

2

2

2

Przykład

X

2

= 101,011

X

10

= 1·2

2

+ 0·2

1

+ 1·2

0

+ 0·2

-1

+ 1·2

-2

+ 1·2

-3

= 4+0+1 + 0+0,25+0,125 =

= 5,375

10

i=0, 1, 2, ..., I

f=1, 2, 3, ..., F

1

10

2

10

4

10

8

10

16

10

32

10

0

,0

3

12

5

0

,0

6

2

5

0

,1

2

5

0

,2

5

0

,5

Reprezentacja danych / reprezentacja liczb

8

8

Klasyfikacja

Klasyfikacja

Liczby

Liczby

Stałopozycyjna

Stałopozycyjna

Zmiennoprzecinkowa

Zmiennoprzecinkowa

pojedynczej precyzji

pojedynczej precyzji

podwójnej precyzji

podwójnej precyzji

rozszerzonej precyzji

rozszerzonej precyzji

bez znaku

bez znaku

ze znakiem

ze znakiem

krótka (1B)

krótka (1B)

słowo (2B)

słowo (2B)

rozszerzona

rozszerzona

krótka (1B)

krótka (1B)

słowo (2B)

słowo (2B)

rozszerzona

rozszerzona

Metodyki i techniki programowania 1

2011

B. Butryło

5

Reprezentacja danych / reprezentacja liczb

9

9

Liczby bez znaku – kod BCN

Liczby bez znaku – kod BCN

0

0

d

d

o

o

d

d

a

a

t

t

n

n

i

i

e

e

x

⊂ℑ

+

ℜ

n

n

a

a

d

d

m

m

i

i

a

a

r

r

-

-

n

n

a

a

d

d

m

m

i

i

a

a

r

r

+

+

0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1

2

7

2

6

2

5

2

4

2

3

2

2

2

1

2

0

MSB

LSB

N bitów

1

2

0

10

−

≤

≤

N

x

0

0

1

1

2

2

1

1

10

2

2

...

2

2

⋅

+

⋅

+

+

⋅

+

⋅

=

−

−

−

−

b

b

b

b

x

N

N

N

N

unsigned char

0

1B

2

8

-1 = 255

unsigned short int

0

2B

2

16

-1 = 65535

unsigned long

0

4B

2

32

-1 = 4 294 967 295

Nazwa typu

Kres dolny

Rozmiar

Kres górny

C++

C++

C++

C++

C++

C++

C++

C++

Reprezentacja danych / reprezentacja liczb

10

10

Liczby ze znakiem - kod U2

Liczby ze znakiem - kod U2

1

2

2

1

1

10

1

−

≤

≤

⋅

−

−

−

N

N

x

0

0

1

1

2

2

1

1

10

2

2

...

2

2

1

⋅

+

⋅

+

+

⋅

+

⋅

⋅

−

=

−

−

−

−

b

b

b

b

x

N

N

N

N

0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1

-1·2

7

2

6

2

5

2

4

2

3

2

2

2

1

2

0

MSB

LSB

N bitów

SB

0 - dla liczb dodatnich
1 - dla liczb ujemnych

(

)







<

+

∪

≥

∪

=

−

−

0

1

1

0

0

10

1

10

1

2

x

X

x

X

x

LSB

BCN

N

BCN

N

U

Przykład: X

10

X

U2

X

10

=93

0 1 0 1 1 1 0 1

64 32 16 8 4 2 1

X

10

=-93

1 0 1 0 0 0 1 1

64 32 16 8 4 2 1

-128

-128

u

u

j

j

e

e

m

m

n

n

e

e

0

0

d

d

o

o

d

d

a

a

t

t

n

n

i

i

e

e

x

⊂ℑ

-

x

⊂ℑ

+

ℜ

n

n

a

a

d

d

m

m

i

i

a

a

r

r

-

-

n

n

a

a

d

d

m

m

i

i

a

a

r

r

+

+

Metodyki i techniki programowania 1

2011

B. Butryło

6

Reprezentacja danych / reprezentacja liczb

11

11

Liczby ze znakiem

Liczby ze znakiem

char

-1·2

8-1

= -128

1B

2

8-1

-1 = 127

short int

-1·2

16-1

= -32768

2B

2

16-1

-1 = 32767

int, long, long int

-1·2

32-1

= -2 147 483 648

4B

2

32-1

-1 = 2 147 483 647

Nazwa typu

Kres dolny

Rozmiar

Kres górny

byte

-1·2

8-1

= -128

1B

2

8-1

-1 = 127

short

-1·2

16-1

= -32768

2B

2

16-1

-1 = 32767

int

-1·2

32-1

= -2 147 483 648

4B

2

32-1

-1 = 2 147 483 647

Nazwa typu

Kres dolny

Rozmiar

Kres górny

long

-1·2

64-1

= ...

8B

2

64-1

-1 = ...

C++

C++

C++

C++

C++

C++

C++

C++

8B

Reprezentacja danych / reprezentacja liczb

12

12

Reprezentacja zmiennoprzecinkowa

Reprezentacja zmiennoprzecinkowa

X

10

=±M·10

±

E

X

10

±

M

2

·2

±

e

2

IEEE

754

IEEE

754

pojedynczej precyzji
(single precision)

pojedynczej precyzji
(single precision)

podwójnej precyzji
(double precision)

podwójnej precyzji
(double precision)

rozszerzonej precyzji
(extended precision)

rozszerzonej precyzji
(extended precision)

IEEE

The Institute of

Electric and

Electronic Engineers

0 = 0+, 0-
liczby normalizowane
liczby nienormalizowane
kody informacyjne / błędy

0 = 0+, 0-
liczby normalizowane
liczby nienormalizowane
kody informacyjne / błędy

Metodyki i techniki programowania 1

2011

B. Butryło

7

Reprezentacja danych / reprezentacja liczb

13

13

Reprezentacja zmiennoprzecinkowa

Reprezentacja zmiennoprzecinkowa

ℜ

0

0

Nadmiar -

Nadmiar +

Niedomiar -

Niedomiar +

x

∈ℜ

-

x

∈ℜ

+

Zakres liczb -

Zakres liczb +

0/1

0/1

0/10/10/10/10/10/10/1

0/10/10/10/10/10/10/1

0/10/10/10/10/10/10/10/1

0/1 0/10/10/10/10/10/10/1

X

10

±

M

2

·2

±

e

2

X

10

-1

SB

· 1,fffffffffffff · 2

E

exc

bit znaku

SB

0 jeżeli x >= 0
1 jeżeli x < 0

wykładnik

E

Liczby całkowite

w kodzie Excess

mantysa

M

Znormalizowana liczba w zapisie stałopozycyjnym

bez wiodącej jedynki

Reprezentacja danych / reprezentacja liczb

14

14

IEEE 754

IEEE 754

0/1

0/1

0/10/10/10/10/10/10/1

0/10/10/10/10/10/10/1

0/10/10/10/10/10/10/10/1

0/1 0/10/10/10/10/10/10/1

bit

znaku

SB

wykładnik

E

mantysa

M

IEEE 754

pojedyncza precyzja

IEEE 754

podwójna precyzja

N

SB

1b

1b

N

E

8b

11b

N

M

23b

52b

N

32b

64b

E

0 ... 255

0 ... 2047

e

E - 127

E - 1023

e

min

-126

-1022

e

max

127

1023

specjalne e

-127, 0, 128

-1023, 0, 1024

Metodyki i techniki programowania 1

2011

B. Butryło

8

Reprezentacja danych / reprezentacja liczb

15

15

IEEE 754

IEEE 754

0/1

0/1

0/10/10/10/10/10/10/1

0/10/10/10/10/10/10/1

0/10/10/10/10/10/10/10/1

0/1 0/10/10/10/10/10/10/1

bit

znaku

SB

wykładnik

E

mantysa

M

IEEE 754

pojedyncza precyzja

IEEE 754

podwójna precyzja

x

MIN,10

~1,175 · 10

-38

~2,225 · 10

-308

x

MAX,10

~3,403 · 10

38

~1,798 · 10

308

d

2

2

-(23+1)

2

-(52+1)

d

10

~5,96 · 10

-8

~1,11 · 10

-16

Liczby, których zapis przekracza dopuszczalną długość mantysy są zaokrąglane do

najbliższej reprezentowalnej liczby.

fl(

X

R

)=

X

R

(1+

δδδδ

)

fl(

X

R

)=

X

R

(1+

δδδδ

)

Reprezentacja danych / reprezentacja liczb

16

16

IEEE 754 – pojedyncza precyzja

IEEE 754 – pojedyncza precyzja

bit znaku

SB

wykładnik

E

mantysa

M

0

0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0

0 0 0 0 0 0 0

x = +0

1

0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0

0 0 0 0 0 0 0

x = -0

0/1

0

0 0 0 0 0 0 0

0/10/10/10/10/10/10/1

0/10/10/10/10/10/10/10/1

0/1 0/10/10/10/10/10/10/1

x,

brak normalizacji

(bez wiodącej jedynki)

0

1

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0

0 0 0 0 0 0 0

+x

min (norm)

0

0

1

1

1

1

1

1

1

+x

max (norm)

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

1

0

0 0 0 0 0 0 0

+x

min (denorm)

+x

max (denorm)

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

0

0 0 0 0 0 0 0

Metodyki i techniki programowania 1

2011

B. Butryło

9

Reprezentacja danych / reprezentacja liczb

17

17

IEEE 754 – pojedyncza precyzja

IEEE 754 – pojedyncza precyzja

bit znaku

SB

wykładnik

E

mantysa

M

0

1

1

1

1

1

1

1

1

0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0

0 0 0 0 0 0 0

x = +Inf

1

1

1

1

1

1

1

1

1

0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0

0 0 0 0 0 0 0

x = -Inf

0/1

1

1

1

1

1

1

1

1

0/10/10/10/10/10/10/1

0/10/10/10/10/10/10/10/1

0/1 0/10/10/10/10/10/10/1

x = NaN

Reprezentacja danych / reprezentacja liczb

18

18

IEEE 754

IEEE 754

float

3.4 · 10

-38

4B

3.4 · 10

38

double

1.8 · 10

-308

8B

1.8 · 10

308

long double

3.4 · 10

-4932

10B

3.4 · 10

4932

Nazwa typu

minimalna dodatnia

Rozmiar

maksymalna dodatnia

7

16

22

Precyzja

C++

C++

C++

C++

C++

C++

C++

C++

float

3.4 · 10

-38

4B

3.4 · 10

38

double

1.8 · 10

-308

8B

1.8 · 10

308

Nazwa typu

minimalna dodatnia

Rozmiar

maksymalna dodatnia

7

16

Precyzja

Metodyki i techniki programowania 1

2011

B. Butryło

10

Reprezentacja danych / reprezentacja liczb

19

19

IEEE 754 – wyjątki od standardu w Java

IEEE 754 – wyjątki od standardu w Java

• Nie sygnalizuje wyraźnie wyjątków i błędów

związanych z obliczeniami (np. dzielenie przez
zero, nadmiar, utrata dokładności). Wszystkie
tego typu przypadki są sygnalizowane przez NaN.

• Konwersja z liczby zmiennoprzecinkowej na

stałopozycyjną jest zawsze zaokrągleniem do
wartości bliższej zera.

• Nie ma w standardzie operacji zaokrąglania w dół,

w górę.

• Nie przewidziano typu zmiennej extended.

Wstęp

Arytmetyka stałopozycyjna

Błędy obliczeń

Arytmetyka stałopozycyjna

Błędy obliczeń

Metodyki i techniki programowania 1

2011

B. Butryło

11

Reprezentacja stałopozycyjna / przetwarzanie

21

21

Dane analogowe i reprezentacja dyskretna

Dane analogowe i reprezentacja dyskretna

Błąd względny kwantyzacji

%

100

%

100

%

100

min

max

min

max

min

max

⋅

−

−

=

⋅

−

∆

=

⋅

∆

=

A

A

k

A

A

A

A

A

A

zakres

A

k

x

x

Q

x

x

x

x

x

x

x

δ

%

100

2

1

%

100

1

⋅

=

⋅

=

N

k

k

Q

δ

z

(n)

t

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

x

(t)

t

x

max

x

min

A/D

A/D

Reprezentacja stałopozycyjna / przetwarzanie

22

22

Informacja dyskretna: kwantyzacja

Informacja dyskretna: kwantyzacja

Błąd względny kwantyzacji

2

^

1

6

=

6

5

5

3

6

2

^

1

=

2

2

^

1

5

=

3

2

7

6

8

2

^

1

4

=

1

6

3

8

4

2

^

1

3

=

8

1

9

2

2

^

1

2

=

4

0

9

6

2

^

1

1

=

2

0

4

8

2

^

1

0

=

1

0

2

4

2

^

9

=

5

1

2

2

^

8

=

2

5

6

2

^

7

=

1

2

8

2

^

6

=

6

4

2

^

5

=

3

2

2

^

4

=

1

6

2

^

3

=

8

2

^

2

=

4

0,001%

0,010%

0,100%

1,000%

10,000%

100,000%

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

δδδδ

k

N

Typowe oscyloskopy cyfrowe (A/D):
N=8 bitów; Q

k

=2

8

=256

Typowe oscyloskopy cyfrowe (A/D):
N=8 bitów; Q

k

=2

8

=256

Typowe przetworniki D/A:
N=10 bitów; Q

k

=2

10

=1024

Typowe przetworniki D/A:
N=10 bitów; Q

k

=2

10

=1024

Typowe przetworniki A/D:
N=12 bitów; Q

k

=2

12

=4096

Typowe przetworniki A/D:
N=12 bitów; Q

k

=2

12

=4096

%

100

2

1

⋅

=

N

k

δ

Kwantowanie danych (sygnałów)
wejściowych.

Dyskretyzacja

zbioru

stanów

(ograniczenie

zbioru stanów).
Błędy kwantowania:

• błędy zaokrągleń,
• błędy nieokreśloności dla

wartości granicznych,

• błąd pływania zera,
• błąd

pływania

najmniej

znaczących bitów.

Kwantowanie danych (sygnałów)
wejściowych.

Dyskretyzacja

zbioru

stanów

(ograniczenie

zbioru stanów).
Błędy kwantowania:

• błędy zaokrągleń,
• błędy nieokreśloności dla

wartości granicznych,

• błąd pływania zera,
• błąd

pływania

najmniej

znaczących bitów.

Metodyki i techniki programowania 1

2011

B. Butryło

12

Wstęp

Arytmetyka zmiennopozycyjna

Błędy obliczeń

Arytmetyka zmiennopozycyjna

Błędy obliczeń

Reprezentacja zmiennoprzecinkowa / przetwarzanie

24

24

Kumulacja, propagacja i generacja błędów

Kumulacja, propagacja i generacja błędów

Y

X

⊗

• Kumulacja, propagacja i generacja błędów.
• Rejestry w jednostkach zmiennoprzecinkowych mają

zwykle dodatkowe bity chroniące.

( )

( )

(

)

(

) (

)

(

)(

)

3

2

1

1

1

1

δ

δ

δ

+

+

⊗

+

=

⊗

Y

X

Y

fl

X

fl

fl

Błędy obliczeń!

Kolejność operacji!

Liczba operacji!

Wartości argumentów!

Zakres liczb.

Czas wykonywania

obliczeń.

Błędy obliczeń!

Kolejność operacji!

Liczba operacji!

Wartości argumentów!

Zakres liczb.

Czas wykonywania

obliczeń.

Metodyki i techniki programowania 1

2011

B. Butryło

13

Reprezentacja zmiennoprzecinkowa / przetwarzanie

25

25

Y

X

E

E

+

2

...

,

1

...

,

1

3

3

3

3

2

1

Y

Y

Y

X

X

X

b

b

b

b

b

b

⋅

...

,

1

3

2

1

W

W

W

b

b

b

( )

(

)

2

%

1

Y

X

SB

SB

+

−

( )

(

)

Y

X

SB

SB

XOR

,

1

−

Mnożenie liczb

Mnożenie liczb

( )

X

X

E

X

SB

M

X

2

1

⋅

⋅

−

=

( )

Y

Y

E

Y

SB

M

Y

2

1

⋅

⋅

−

=

( )

( )

Y

Y

X

X

E

Y

SB

E

X

SB

M

M

Y

X

W

2

1

2

1

⋅

⋅

−

⋅

⋅

⋅

−

=

⋅

=

( ) ( )

[

]

[

]

[

]

Y

X

Y

X

E

E

Y

X

SB

SB

M

M

W

2

2

1

1

⋅

⋅

⋅

⋅

−

⋅

−

=

( )

D

W

W

E

D

W

SB

D

M

W

,

2

1

,

⋅

⋅

−

=

IEEE 754

Mnożenie i dzielenie

zmiennoprzecinkowe są

znacznie bardziej

czasochłonne i

„kłopotliwe” w realizacji

niż dodawanie i

odejmowanie

zmiennoprzecinkowe

.

Mnożenie i dzielenie

zmiennoprzecinkowe są

znacznie bardziej

czasochłonne i

„kłopotliwe” w realizacji

niż dodawanie i

odejmowanie

zmiennoprzecinkowe

.

Reprezentacja zmiennoprzecinkowa / przetwarzanie

26

26

Błędy operacji zmiennoprzecinkowych

Błędy operacji zmiennoprzecinkowych

x

x

x

∆

+

=

ˆ

y

y

y

∆

+

=

ˆ

Dodawanie liczb:

Dane:

(

)

y

x

y

x

y

x

∆

+

∆

+

+

=

+

ˆ

ˆ

y

x

S

∆

+

∆

=

∆

y

x

y

y

y

x

x

x

y

x

y

x

y

x

y

x

y

x

S

S

ˆ

ˆ

ˆ

ˆ

ˆ

ˆ

ˆ

ˆ

ˆ

ˆ

ˆ

ˆ

ˆ

ˆ

+

⋅

∆

+

+

⋅

∆

=

+

∆

+

+

∆

=

+

∆

=

δ

y

y

x

x

S

w

w

⋅

+

⋅

=

δ

δ

δ

Przykład:
a = (0,1

10

)

2

+ (0,1

10

)

2

+ (0,1

10

)

2

+ (0,1

10

)

2

+ (0,1

10

)

2

+

(0,1

10

)

2

+ (0,1

10

)

2

+ (0,1

10

)

2

+ (0,1

10

)

2

+ (0,1

10

)

2

= ??

( )

( )

( ) ( )

y

fl

x

fl

y

fl

x

fl

ˆ

ˆ

ˆ

ˆ

+

=

⊗

Metodyki i techniki programowania 1

2011

B. Butryło

14

Reprezentacja zmiennoprzecinkowa / przetwarzanie

27

27

0

Błędy operacji zmiennoprzecinkowych

Błędy operacji zmiennoprzecinkowych

x

x

x

∆

+

=

ˆ

y

y

y

∆

+

=

ˆ

Iloczyn liczb:

Dane:

y

x

x

y

y

x

y

x

y

x

∆

⋅

∆

+

∆

⋅

+

∆

⋅

+

⋅

=

⋅

ˆ

ˆ

ˆ

ˆ

x

y

I

y

x

∆

⋅

+

∆

⋅

=

∆

ˆ

ˆ

y

x

y

x

y

x

I

I

ˆ

ˆ

ˆ

ˆ

∆

+

∆

=

⋅

∆

=

δ

y

x

I

δ

δ

δ

+

=

Przykład. Dla 0,99 <= x <= 1.01 oblicz
a = (x-1)

8

b = x

8

– 8x

7

+ 28x

6

– 56x

5

+ 70x

4

– 56x

3

+ 28x

2

– 8x + 1

c = ( ( ( ( ( ( (x – 8) x + 28) x – 56) x + 70) x – 56) x + 28) x – 8) x + 1

( )

( )

( ) ( )

y

fl

x

fl

y

fl

x

fl

ˆ

ˆ

ˆ

ˆ

⋅

=

⊗

Reprezentacja danych

Kody alfanumeryczne

Kody alfanumeryczne

Metodyki i techniki programowania 1

2011

B. Butryło

15

Reprezentacja danych / kody alfanumeryczne

29

29

Kody alfanumeryczne

Kody alfanumeryczne

Alfanumeryczne

Alfanumeryczne

ASCII

1968

ASCII

1968

ISO-646

1972

ISO-646

1972

ISO-8859

1985

ISO-8859

1985

ISO-10646, Unicode

To nie jest kod!

ISO-10646, Unicode

To nie jest kod!

inne

inne

EBCDIC

EBCDIC

• Nie są wzajemnie jednoznaczne.
• Nie są detekcyjne.
• Obowiązuje (zwykle) zasada zgodności wstecz.

Reprezentacja danych / kody alfanumeryczne

30

30

Reprezentacja zmiennych znakowych

Reprezentacja zmiennych znakowych

char

ASCII

1B

Nazwa typu

Kod podstawowy

Rozmiar

C++

C++

C++

C++

C++

C++

C++

C++

char

Unicode (UCS-2)

2B

Nazwa typu

Kod podstawowy

Rozmiar

Metodyki i techniki programowania 1

2011

B. Butryło

16

Reprezentacja danych / kody alfanumeryczne

31

31

ASCII, ISO-7

ASCII, ISO-7

0 1 2 3 4 5 6 7 8 9 A B C D E F

0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F

0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1

b

7

b

6

b

5

b

4

b

3

b

2

b

1

b

0

• American Standard Code for

Information Interchange
(1968)

• Kod 8 bitowy, czyli możliwe 2

8

kombinacji binarnych.

• Kodowanie znaków na 7 bitach,

czyli 2

7

aktywnych kombinacji

binarnych.

• Kod prosty.

7 bitów do kodowania znaków

Reprezentacja danych / kody alfanumeryczne

32

32

ASCII, ISO-7

ASCII, ISO-7

0 1 2 3 4 5 6 7 8 9 A B C D E F

0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F

00

NUL

01

SOH

02

STX

03

ETX

04

EOT

05

ENQ

06

ACK

07

BEL

08

BS

09

HT

0A

LF

0B

VT

0C

FF

0D

CR

0E

SO

0F

SI

10

DLE

11

DC1

12

DC2

13

DC3

14

DC4

15

NAK

16

SYN

17

ETB

18

CAN

19

EM

1A

SUB

1B

ESC

1C

FS

1D

GS

1E

RS

1F

US

7F

DEL

Metodyki i techniki programowania 1

2011

B. Butryło

17

Reprezentacja danych / kody alfanumeryczne

33

33

ASCII, ISO-7

ASCII, ISO-7

0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1

b

7

b

6

b

5

b

4

b

3

b

2

b

1

b

0

7 bitów do kodowania znaków

4

2

1

8

4

2

1

Reprezentacja danych / kody alfanumeryczne

34

34

RS232C – pirometr

RS232C – pirometr

Znacznik początku (1 znak)

Tryb pracy (1 znak ASCII)

L

C/P

H/C

spacja

Cyfra 100

Znacznik końca (1 znak)

CR

Odbiorca

Odbiorca

Nadawca

Nadawca

Tryb pracy (1 znak ASCII)

1 cyfra znacząca (ASCII)

Cyfra 10

Cyfra 1

2 cyfra znacząca (ASCII)

3 cyfra znacząca (ASCII)

Metodyki i techniki programowania 1

2011

B. Butryło

18

Reprezentacja danych / kody alfanumeryczne

35

35

MODBUS – tryb ASCII

MODBUS – tryb ASCII

Znacznik początku (1 znaki)

Adres

(2 znaki ASCII)

zakres adresów: 0 - 247

Funkcja

(2 znaki ASCII)

kody operacji: 1-255

:

znak 1

znak 2

znak 1

znak 2

znak 1

znak 2

Dane

(n znaków ASCII)

znak 3

...

znak n

Kontrola LRC (longitudinal

redundancy check)

(2 znaki ASCII)

Znacznik końca

(2 znaki)

znak 1

znak 2

CR

LF

Odbiorca

Odbiorca

Nadawca

Nadawca

• Standard

komunikacji

sterowników

przemysłowych,

wymiana

informacji

między

urządzeniami systemów kontrolno-
pomiarowych.

• Komunikacja w trybie Master-

Slave,

asynchroniczna.

Komunikację inicjuje wyłącznie
Master.

• Możliwe adresowanie indywidualne

lub

transmisja

w

trybie

rozgłaszania.

• Wiadomości są przesyłane w

ramkach, w trybie ASCII lub RTU.

• Niekompletna ramka lub błąd

inicjuje komunikat o wystąpieniu
błędu, przesyłany do Master.

• Przesyłanie półbajtów. Każdy bajt

wiadomości jest przesyłany jako
dwa znaki ASCII kodowane 16.

Reprezentacja danych / kody alfanumeryczne

36

36

MODBUS – tryb RTU

MODBUS – tryb RTU

Znacznik początku

(3,5 czas* 1znak)

Adres (8b)

Funkcja (8b)

cisza na

łączu

8b
8b
8b

Dane

(n zestawów po 8 bitów)

8b

...

8b

Kontrola CRC (cyclical

redundancy check)

(16b)

Znacznik końca

(3,5 czas* 1znak)

8b
8b

Odbiorca

Odbiorca

Nadawca

Nadawca

8b

cisza na

łączu

Metodyki i techniki programowania 1

2011

B. Butryło

19

Reprezentacja danych / kody alfanumeryczne

37

37

Inter IC BUS, I

2

CBUS

Inter IC BUS, I

2

CBUS

Znacznik początku (8b)

Adres

(16b)

zakres adresów: 0 - 1024

Tryb (bit kierunku) 1b

start

adres

Dane

(n słów 8b + potwierdzenie)

Znacznik końca (8b)

Odbiorca

Odbiorca

Nadawca

Nadawca

• Opracowany

przez

firmę

Philips.

• Wbudowane sterowniki oparte

na

układach

CMOS

–

ograniczona moc.

• Transmisja szeregowa.
• Możliwe występowanie wielu

urządzeń master i slave oraz
zmiana roli.

• Wysoka

odporność

na

zakłócenia zewnętrzne.

• Możliwe

dołączanie

i

wyłączanie

dodatkowych

układów do magistrali bez
konieczności

ingerencji

w

pozostały układ połączeń.

• Każdy

bajt

wymaga

potwierdzenia

R/W

potwierdzenie

...

znak 1

potwierdzenie

znak 2

potwierdzenie

znak 3

potwierdzenie

potwierdzenie

start

Reprezentacja danych / kody alfanumeryczne

38

38

ISO-8859

ISO-8859

0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1

b

7

b

6

b

5

b

4

b

3

b

2

b

1

b

0

• International Standard

Organization 8859 (1985).

• Kod 8 bitowy, czyli możliwe 2

8

kombinacji binarnych.

• Kodowanie znaków na 8 bitach,

czyli 2

8

aktywnych kombinacji

binarnych.

• Kod prosty.
• Można interpretować jako zbiór

tablic kodowych tworzonych dla
wybranych krajów, stref
językowych lub geograficznych.

8 bitów do kodowania znaków

0 1 2 3 4 5 6 7 8 9 A B C D E F

0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F

ISO-8859-1

0 1 2 3 4 5 6 7 8 9 A B C D E F

0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F

ISO-8859-2

0 1 2 3 4 5 6 7 8 9 A B C D E F

0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F

ISO-8859-3

0 1 2 3 4 5 6 7 8 9 A B C D E F

0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F

ISO-8859-n

ASCII

(ISO-7)

ASCII

(ISO-7)

ASCII

(ISO-7)

ASCII

(ISO-7)

lokalna 1

lokalna 2

lokalna 3

lokalna n

Metodyki i techniki programowania 1

2011

B. Butryło

20

Reprezentacja danych / kody alfanumeryczne

39

39

ISO-8859

ISO-8859

0 1 2 3 4 5 6 7 8 9 A B C D E F

0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F

ISO-8859-n

ASCII

(ISO-7)

lokalna n

ISO-8859-1

Latin1

Zachodnia Europa

ISO-8859-2

Latin2

Wschodnia Europa

ISO-8859-3

Latin3

Południowa Europa

ISO-8859-4

Latin4

Północna Europa

ISO-8859-5

Cyrylica

ISO-8859-6

Arabski

ISO-8859-7

Grecki

ISO-8859-8

Hebrajski

ISO-8859-9

Latin5

Turecki

ISO-8859-10

Latin6

Nordycki

Reprezentacja danych / kody alfanumeryczne

40

40

ISO-8859

ISO-8859

0 1 2 3 4 5 6 7 8 9 A B C D E F

0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F

ISO-8859-n

ASCII

(ISO-7)

lokalna n

Część lokalna ISO-8859-

1 (Latin1, ..., 0)

Część lokalna ISO-8859-2 (Latin2)

Część lokalna ISO-8859-4 (Latin4)

Metodyki i techniki programowania 1

2011

B. Butryło

21

Reprezentacja danych / kody alfanumeryczne

41

41

ISO-8859-1 kontra WinLatin1 (CP1252)

ISO-8859-1 kontra WinLatin1 (CP1252)

ISO-8859-1
podstawowy kod w internecie

WinLatin1 (CP1252)
kod preferowany przez Microsoft

Reprezentacja danych / kody alfanumeryczne

42

42

Unicode

Unicode

• Unicode
• Universal Character Set (UCS)
• ISO-10646

• Unicode 1.0

1991

• Unicode 2.0

1996

• Unicode 3.0

1999

• Unicode 4.0

2003

• Unicode 5.0

2006

• Unicode 5.1

2008

‰

ż

a

µ

Ê

¼

®

ð

€

ą

ÿ

œ

я

щ

ش





♫

♠

™



☺

∫

≈

∞

┴

╢

♥

☼

c

b

a
à
ą

α

ش

b
á
ć
µ



c
ç
ő



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

€

╢

¼

╖

‰

┴

...
...

я

♫

щ



ÿ

♪

...
...

®

∞

☺

∫

♠

≈

...
...

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

UTF

UTF

-

-

16

16

zmienna długość transferu

zmienna długość transferu

0100100101001001 0100100101001001

UTF

UTF

-

-

32

32

stała długość transferu, czyli

stała długość transferu, czyli

możliwe 2

możliwe 2

32

32

=4 294 967 296

=4 294 967 296

01001001010010010100100101001001

UTF

UTF

-

-

8

8

zmienna długość transferu

zmienna długość transferu

01001001 01001001 01001001 01001001 01001001 01001001

Metodyki i techniki programowania 1

2011

B. Butryło

22

Reprezentacja danych / kody alfanumeryczne

43

43

Unicode

Unicode

• Definiowane znaki są (powinny być) określone przez kształt i funkcję a nie

przez język.

• Znaki mają przydzielone:

• oficjalną nazwę,
• rodzaj znaku (znak, ideogram, symbol, cyfra, ...),
• wielkość znaku litery (mała/duża), wartość cyfry,
• opis kompatybilności,
• znaki pokrewne,
• wygląd wzorcowy,
• numer porządkowy: U+xxxx, U-xxxxxxxx,
• ...

• Kodowanie – określenie sposobu w jaki znaki ze zbioru mają być zapisane w

formie binarnej.

Reprezentacja danych / kody alfanumeryczne

44

44

Unicode

Unicode

Przykład:

U+0041

U-00000041

Latin capital letter A

A

U+00C0

U-000000C0

Latin capital letter A with grave

À

U+0141

U-00000141

Latin capital letter L with dash

Ł

U+041F

U-0000041F

Cyrilic capital letter Pe

П

U+03A8

U-000003A8

Greek capital letter Psi

Ψ

U+05DE

U-000005DE

Hebrew letter Mem

מ

U+067F

U-0000067F

Arabic letter Teheh

U+06F7

U-000006F7

Extended arabic-indic digit 7

٧

U+20AC

U-000020AC

Euro sign

€

U+2248

U-00002248

Almost equal to

≈

U+2122

U-00002122

Trade mark sign

™

U+263A

U-0000263A

White smiling face

☺

...

...

...

...

...

...

...

...

...

...

...

...

U+0391

U-00000391

Greek capital letter Alpha

A

U+20A0

U-000020A0

Euro currency sign (ECU)

...

...

Metodyki i techniki programowania 1

2011

B. Butryło

23

Reprezentacja danych / kody alfanumeryczne

45

45

UCS Basic Multilingual Plane (2

16

znaków)

UCS Basic Multilingual Plane (2

16

znaków)

0 1 2 3 4 5 6 7 8 9 A B C D E F

000
001
002
003
004
005
006
007
008
009
00A
00B
00C
00D
00E
00F
010
011
012
013
014
015
016
017
018
019
01A
01B
01C
01D
01E
01F
020
021
022
023
024
025
026
027
028
029

FFB
FFC
FFD
FFE
FFF

...

Typowe przedstawienie:
• 16 kolumn
• 4096 wierszy

ASCII

LATIN 1

LATIN

Extended

A-zone (alphabetic): {U+0000, U+33FF}

Basic Latin (US-ASCII): {U+0000, U+007F}
Latin-1 (ISO-8859-1): {U+0080, U+00FF}
Latin extended: {U+0100, U+024F}
…
Greek: {U+0370..U+03FF}
Cyrillic: {U+0400..U+04FF}
Armenian: {U+0530..U+058F}
Hebrew: {U+0590..U+05FF}
Arabic: {U+0600..U+06FF}
Syriac: {U+0700..U+074D}
Thaana: {U+0780..U+07B1}
...

Symbolic Area: {U+2000, U+2EFF}

General punctuation: {U+2000, U+206F}
Superscripts and subscripts: {U+2070, U+209F}
Currency symbols: {U+20A0, U+20CF}
…

Phonetics and Symbolic Area: {U+2F00, U+33FF}
…
I-zone (ideographic): {U+3400, U+9FFF}
...
O-zone (other): {U+A000, U+D7FF}
...
S-zone (surrogates): {U+D800, U+DFFF}
...
R-zone (reserved): {U+E000, U+FFFF}
…

Reprezentacja danych / kody alfanumeryczne

46

46

Unicode w internecie

Unicode w internecie

• UTF-8

- 8 bitowe kodowanie. Zmienna długość reprezentacji znaków.

zapis znaku 1B („0” + 7b)

0*******

zapis znaku 2B (5b+11b)

110***** 10******

zapis znaku 3B (8b+16b)

1110**** 10****** 10******

zapis znaku 4B (11b+21b)

11110*** 10****** 10****** 10******

zapis znaku 5B (14b+26b)

111110** 10****** 10****** 10****** 10******

1111110* 10****** 10****** 10****** 10****** 10******

zapis znaku 6B (17b+31b)

ASCII

Przykład:
Dziś U+0044, U+007A, U+0069, U+015B
Ołów U+004F, U+0142, U+00D3, U+0077

β

=5Å U+003D, U+007A, U+0035, U+00C5

Metodyki i techniki programowania 1

2011

B. Butryło

24

Reprezentacja danych / kody alfanumeryczne

47

47

Unicode w internecie

Unicode w internecie

• UTF-8

- 8 bitowe kodowanie. Zmienna długość reprezentacji znaków.

zapis znaku 1B („0” + 7b)

0*******

zapis znaku 2B (5b+11b)

110***** 10******

zapis znaku 3B (8b+16b)

1110**** 10****** 10******

zapis znaku 4B (11b+21b)

11110*** 10****** 10****** 10******

zapis znaku 5B (14b+26b)

111110** 10****** 10****** 10****** 10******

1111110* 10****** 10****** 10****** 10****** 10******

zapis znaku 6B (17b+31b)

ASCII

• Zgodność w dół i prosta reprezentacja

kodu ASCII.

• Łatwe wykrycie sekwencji wiodącej

11****** od kolejnej (kodującej)
10******.

• Łatwe przetwarzanie w programach

przez wykorzystanie operacji
maskowania w ramach operacji w
procesorach.

• Kompresja danych.
• Kolejność bajtów w sekwencji nie ma

znaczenia.

• Zmienna długość pól kodujących.
• Strata bitów na zaznaczanie sekwencji

wiodących.

• Występują sekwencje bitów, które są

błędnie interpretowane przez niektóre
programy i mogą powodować ich
zawieszenie.

• Niezgodność z EBCDIC i Latin 1.

?

?

Reprezentacja danych / kody alfanumeryczne

48

48

Unicode

Unicode

32 bity do kodowania znaków

0/10/10/10/10/10/10/10/1

b

23

b

22

b

21

b

20

b

19

b

18

b

17

b

16

0/1 0/10/10/10/10/10/10/1

b

31

b

30

b

29

b

28

b

27

b

26

b

25

b

24

U-xxxxxxxx

0/10/10/10/10/10/10/10/1

b

7

b

6

b

5

b

4

b

3

b

2

b

1

b

0

0/1 0/10/10/10/10/10/10/1

b

15

b

14

b

13

b

12

b

11

b

10

b

9

b

8

• UTF-32

- stała długość transferu, możliwe kodowanie 2

32

znaków.

UCS-4

16 bitów do kodowania znaków

0/10/10/10/10/10/10/10/1

b

7

b

6

b

5

b

4

b

3

b

2

b

1

b

0

0/1 0/10/10/10/10/10/10/1

b

15

b

14

b

13

b

12

b

11

b

10

b

9

b

8

U+xxxx

0/10/10/10/1 0/10/10/10/1

0/1 0/10/10/1 0/10/10/10/1

• UTF-16

- zmienna długość transferu, słowo 2B

UCS-2

Metodyki i techniki programowania 1

2011

B. Butryło

25

Reprezentacja danych

Kody detekcyjne

(przykłady)

Kody detekcyjne

(przykłady)

Kilka ciekawych przykładów ...

50

50

Przykłady kodów wagowych: Pesel

Przykłady kodów wagowych: Pesel

*

*

*

*

*

*

*

*

*

*

?

rok urodzin

rok urodzin

miesiąc urodzin

miesiąc urodzin

dzień urodzin

dzień urodzin

płeć: mężczyźni – 1,3,5,7,9;

kobiety – 0,2,4,6,8

płeć: mężczyźni – 1,3,5,7,9;

kobiety – 0,2,4,6,8

numer „porządkowy”

w bazie

numer „porządkowy”

w bazie

CK - cyfra kontrolna

CK - cyfra kontrolna

1 3 7 9 1 3 7 9 1 3

(

) (

)

i

i

i

waga

cyfra

suma

⋅

=

∑

=

10

1

10

%

suma

reszta

=

reszta

CK

−

=

10

;

10

)

0

(

=

=

=

reszta

reszta

Jeżeli

Metodyki i techniki programowania 1

2011

B. Butryło

26

Kilka ciekawych przykładów ...

51

51

Przykłady kodów wagowych: EAN

Przykłady kodów wagowych: EAN

System numerowy

kod kraju (3): PL 590

System numerowy

kod kraju (3): PL 590

numer wytwórcy (4 lub więcej)

numer wytwórcy (4 lub więcej)

numer towaru (5 lub mniej)

numer towaru (5 lub mniej)

CK - cyfra kontrolna (1)

CK - cyfra kontrolna (1)

znak start/stop

znak start/stop

znak rozdzielający

znak rozdzielający

znak start/stop

znak start/stop

9 0 1 2 3

5

4 1 2 3 4 5 7

U

niversal

P

roduct

C

ode

U

niversal

P

roduct

C

ode

E

uropean

A

rticle

N

umbering

E

uropean

A

rticle

N

umbering

EAN-13

EAN-13

EAN-8

EAN-8

Kilka ciekawych przykładów ...

52

52

Przykłady kodów wagowych: EAN

Przykłady kodów wagowych: EAN

9 0 1 2 3

5

4 1 2 3 4 5 7

(

) (

)

i

i

i

waga

cyfra

suma

⋅

=

∑

=

12

1

10

%

suma

reszta

=

reszta

CK

−

=

10

;

10

)

0

(

=

=

=

reszta

reszta

Jeżeli

*

*

*

*

*

*

*

*

?

1 3 1 3 1 3 1 3

*

*

*

*

1 3 1 3

4 8 0 0 0 0 1 8 2

88

=

suma

8

=

reszta

2

10

=

−

=

reszta

CK

5 9 0 1

Towar A: