YaQzi

Kodowanie arytmetyczne

TiK? TAK! TiK? TAK!

TiK? TAK! … TiK-TAK!

YaQzi

Kodowanie

Do zakodowania wiadomości tym sposobem potrzebny nam

będzie zestaw znaków, których użyjemy w wiadomości oraz częstość
występowania każdego z tych znaków. Musimy znaleźć taki podprzedział
przedziału (0;1), który jednoznacznie określi ciąg znaków wyznaczany
rekursywnie na podstawie prawdopodobieństwa ich wystąpienia. Brzmi
skomplikowanie ale robi się to prosto.

Dla przykładu załóżmy sobie takie dane:

Znak

Częstość występowania

A

0.5

B

0.3

C

0.2

chcemy zakodować ciąg „BACA”

YaQzi

Znak

Częstość występowania

A

0.5

B

0.3

C

0.2

0

0.5

0.8

1

Bierzemy przedział (0;1) i dzielimy go na części, z których każda będzie
odpowiadać danemu znakowi. Szerokość podprzedziałów musi być
proporcjonalna do częstości wystąpienia danego znaku. Mamy więc coś
takiego:

0.5

0.3

0.2

A

B

C

YaQzi

Znak

Częstość występowania

A

0.5

B

0.3

C

0.2

0

0.5

0.8

1

B

ACA

A

B

C

Jako pierwszy kodujemy znak „B”. Odpowiada mu przedział (0.5;0.8).

Zaznaczamy go i dzielimy na nowe podprzedziały

proporcjonalne

do tych

pierwszych.

0.5

0.65

0.74

0.8

YaQzi

Znak

Częstość występowania

A

0.5

B

0.3

C

0.2

B

A

CA

Drugi znak to „A”. Wybieramy podprzedział z otrzymanego przed chwilą
przedziału, odpowiadający znakowi A, a więc (0.5;0.65). Zaznaczamy go i
dzielimy na proporcjonalne podprzedziały.

0.5

0.65

0.74

0.8

A

B

C

0.5

0.575

0.62

0.65

YaQzi

Znak

Częstość występowania

A

0.5

B

0.3

C

0.2

BA

C

A

Analogicznie postępujemy ze znakiem C…

0.5

0.575

0.62

0.65

A

B

C

0.62

0.635

0.644

0.65

YaQzi

Znak

Częstość występowania

A

0.5

B

0.3

C

0.2

BAC

A

Ostatni znak to „A”. Odpowiada mu podprzedział (0.62;0.635) i to właśnie
ten podprzedział trzeba zakodować binarnie, ale żeby nie było za łatwo
trzeba go zakodować jednoznacznie, tzn. z odpowiednią ilością zer na
końcu.

A

B

C

0.62

0.635

0.644

0.65

YaQzi

0.620 … 0.635

Jak wiadomo nie wszystkie liczby

zmiennoprzecinkowe można zapisać w postaci binarnej.
Wystarczy jednak, że znajdziemy dowolną, która zmieści
się w tym przedziale. No i najlepiej, żeby była ona jak
najkrótsza. Żeby było lepiej widać o co chodzi wklejam
tablicę z wartościami poszczególnych bitów rozwinięcia
dziesiętnego.

1

0,50000000

2

0,25000000

3

0,12500000

4

0,06250000

5

0,03125000

6

0,01562500

7

0,00781250

8

0,00390625

9

0,00195313

10

0,00097656

11

0,00048828

12

0,00024414

13

0,00012207

14

0,00006104

15

0,00003052

16

0,00001526

17

0,00000763

18

0,00000381

19

0,00000191

20

0,00000095

Widać, że suma bitów 1 i 3 jest cacy:

0,101

2

= 0.5 + 0.125 = 0.625

„0,” występuje w każdej liczbie z przedziału (0;1) więc w

kodzie arytmetycznym jest to pomijane. Mamy więc

wstępną formę zakodowanego ciągu „BACA”:

101

YaQzi

0.62 … 0.635

1

0,50000000

2

0,25000000

3

0,12500000

4

0,06250000

5

0,03125000

6

0,01562500

7

0,00781250

8

0,00390625

9

0,00195313

10

0,00097656

11

0,00048828

12

0,00024414

13

0,00012207

14

0,00006104

15

0,00003052

16

0,00001526

17

0,00000763

18

0,00000381

19

0,00000191

20

0,00000095

101

Teraz musimy sprawdzić, czy jeśli za przesłaniem kodu
wystąpią jakieś domyślne dla kanału jedynki – liczba
wyskoczy z potrzebnego nam przedziału. Jeśli tak –
musimy na końcu kodu dopisać 0 i sprawdzić wariant z
jedynkami ponownie – dopóki dopisanie jedynek niczego
nie zmieni. No więc…

Teraz mamy: 0,101 -> 0.625

Po dopisaniu: 0,10111111111… -> ???

Ale skąd wiadomo ile to jest 0,0001111111… ? Nie
zagłębiając się w szczegóły – patrzymy na którym bicie
jest ostatnie zero po przecinku. W tym wypadku jest na
trzecim miejscu. Patrzymy w tabelce jaka jest wartość 3
bitu -> 0,125. Suma wszystkich jedynek za trzecim
bitem, a więc wartość 0,0001111111… jest równa

prawie

0,125, a więc 0,12499999999… Taka fajna

własność każdemu systemu. Kto nie wierzy niech sobie
policzy. ;)

YaQzi

0.62 … 0.635

1

0,50000000

2

0,25000000

3

0,12500000

4

0,06250000

5

0,03125000

6

0,01562500

7

0,00781250

8

0,00390625

9

0,00195313

10

0,00097656

11

0,00048828

12

0,00024414

13

0,00012207

14

0,00006104

15

0,00003052

16

0,00001526

17

0,00000763

18

0,00000381

19

0,00000191

20

0,00000095

101

No to sprawdzamy:

Teraz mamy: 0,101 -> 0.625

Po dopisaniu: 0,10111111111… -> 0.625 + 0.124(9) =
0.76(9)

Górne ograniczenie przedziału to 0.635 więc jedynki
przeskoczyły przedział – trzeba dopisać 0

YaQzi

0.62 … 0.635

1

0,50000000

2

0,25000000

3

0,12500000

4

0,06250000

5

0,03125000

6

0,01562500

7

0,00781250

8

0,00390625

9

0,00195313

10

0,00097656

11

0,00048828

12

0,00024414

13

0,00012207

14

0,00006104

15

0,00003052

16

0,00001526

17

0,00000763

18

0,00000381

19

0,00000191

20

0,00000095

1010

Sprawdzamy znowu:

Teraz mamy: 0,1010 -> 0.625

Po dopisaniu: 0,10101111111… -> 0.625 + 0.0624(9) =
0.6874(9)

Znowu pojechało za przedział. Dopisujemy kolejne 0.

YaQzi

0.62 … 0.635

1

0,50000000

2

0,25000000

3

0,12500000

4

0,06250000

5

0,03125000

6

0,01562500

7

0,00781250

8

0,00390625

9

0,00195313

10

0,00097656

11

0,00048828

12

0,00024414

13

0,00012207

14

0,00006104

15

0,00003052

16

0,00001526

17

0,00000763

18

0,00000381

19

0,00000191

20

0,00000095

10100

Sprawdzamy znowu:

Teraz mamy: 0,10100 -> 0.625

Po dopisaniu: 0,10100111111…

-> 0.625 + 0.03124(9) =

0.65624(9)

Znowu za dużo. Dopisujemy kolejne 0.

101000

Sprawdzamy znowu:

Teraz mamy: 0,101000 -> 0.625
Po dopisaniu: 0,10100011111…

->

0.625 + 0.015624(9) =

0.640624(9)

Nadal dupa… czyli kolejne zero na koniec.

YaQzi

0.62 … 0.635

1

0,50000000

2

0,25000000

3

0,12500000

4

0,06250000

5

0,03125000

6

0,01562500

7

0,00781250

8

0,00390625

9

0,00195313

10

0,00097656

11

0,00048828

12

0,00024414

13

0,00012207

14

0,00006104

15

0,00003052

16

0,00001526

17

0,00000763

18

0,00000381

19

0,00000191

20

0,00000095

1010000

Sprawdzamy znowu:

Teraz mamy: 0,1010000 -> 0.625
Po dopisaniu:

0,10100001111… -> 0.625 + 0.0078124(9) =

0.6328124(9)

Tym razem górny przedział nie zostanie przekroczony.
Mamy więc zakodowany ciąg „BACA”:

1010000

Użyliśmy 7 bitów do zakodowania 4 znaków.

Średnia wyszła więc 1,75 bitu na słowo.

YaQzi

Jeśli ktoś chce poćwiczyć sobie kodowanie na innym zestawie znaków i
prawdopodobieństwach, może skorzystać do sprawdzenia wyniku z
programu:

Nie zabezpieczałem go przed niepoprawnymi wartościami więc bardzo
łatwo go wyłożyć, ale dla poprawnych wartości i odpowiednio krótkich
ciągów działa. Trzeba pamiętać, że suma prawdopodobieństw musi być
równa 1.

Przykład z prezentacji:

program

YaQzi

Dekodowanie

1

0,50000000

2

0,25000000

3

0,12500000

4

0,06250000

5

0,03125000

6

0,01562500

7

0,00781250

8

0,00390625

9

0,00195313

10

0,00097656

11

0,00048828

12

0,00024414

13

0,00012207

14

0,00006104

15

0,00003052

16

0,00001526

17

0,00000763

18

0,00000381

19

0,00000191

20

0,00000095

1010000

Zamieniamy 0,101 na wartość dziesiętną: 0,625,
rozpisujemy sobie przedziały i patrzymy, do którego
podprzedziału ona trafi. Wybrany podprzedział dzielimy
ponownie na podprzedziały, szukamy, w którym jest
0,625 itd…

A

B

C

0

0.5

0.8

1

A

B

C

0.5

0.65

0.74

0.8

A

B

C

0.5

0.575

0.62

0.65

A

B

C

0.62

0.635

0.644

0.65

YaQzi

Uwaga końcowa

Skąd wiadomo kiedy zatrzymać się w tym odczytywaniu? Przecież po
odczytaniu BACA można dalej podzielić sobie to ostatnie A i czytać
kolejne znaki. Ano można i nie wiadomo kiedy się zatrzymać. Problem
ten rozwiązuje się na dwa sposoby:

- podaje się po prostu ile znaków należy odczytać,
- do zestawu znaków dodaje się ‘znak końca’ - # albo inny szlaczek.

Wtedy przy kodowaniu po ostatniej literze ‘trafiamy’ właśnie w tą # i
kodujemy jej przedział a przy odczytywaniu po prostu czytamy do
momentu trafienia na #. Tyle…