YaQzi
Kodowanie arytmetyczne
TiK? TAK! TiK? TAK!
TiK? TAK! … TiK-TAK!
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…