Strona główna

Rozważa się dwa zbiory


Pobieranie 87.8 Kb.
Data18.06.2016
Rozmiar87.8 Kb.
Elementy kompresji danych – kodowanie nienadmiarowe
1. Zagadnienia podstawowe

Rozważa się dwa zbiory




Zbiór jest zbiorem informacji dyskretnych, natomiast zbiór jest zbiorem sygnałów kodowych. Zbiór nazywany jest często alfabetem kodu.

Kodowaniem nazywana jest operacja przyporządkowania poszczególnym informacjom

ciągów kodowych



Tak więc w procesie kodowania następuje odwzorowanie zbioru informacji w zbiór ciągów kodowych



Wprowadzając operator odwzorowania , operację kodowania zapisuje się w następujący sposób



Zbiór informacji , zbiór ciągów kodowych oraz operator odwzorowania opisują kod



Operacją odwrotną do kodowania jest dekodowanie. Wprowadzając operator dekodowania, operację tę zapisuje się w postaci



Należy podkreślić, że powyższe pojęcia odnoszą się do tzw. kodów blokowych, w których można wyróżnić ciągi kodowe przyporządkowane poszczególnym ciągom informacyjnych. W dalszej części rozpatrywana będzie tylko ta klasa kodów.

Istotnym jest, że liczność alfabetu kodu jest znacznie mniejsza od liczności zbioru informacji

Najbardziej rozpowszechnione, zwłaszcza w technice cyfrowej i telegrafii są kody binarne q=2.




2. Rodzaje kodów

Analizowane w niniejszym punkcie kody cechują się różnymi własnościami dekodowania informacji.

Pierwszym wyróżnionym rodzajem kodu jest kod jednoznaczny. W kodzie tym różnym informacjom przyporządkowywane są różne ciągi kodowe, tzn.

Przykład 2.1

Kod jednoznaczny czterech informacji podano w poniższej tabeli


Informacje

Ciągi kodowe

x1

0

x2

11

x3

00

x4

01

Dla przedstawionego w powyższym przykładzie kodu ciąg sygnałów kodowych 0011 może zostać zdekodowany jako jeden z ciągów informacji x1, x1, x2 lub x3, x2.

Z powyższego wynika, że wymaganie jednoznaczności kodu jest wymaganiem zbyt słabym, ponieważ nie zapewnia jednoznacznego dekodowania. Cechą tą charakteryzują się tzw. kody jednoznacznie dekodowalne. Są to kody których dowolne k-te rozszerzenie jest kodem jednoznacznym. Kod będący k-tym rozszerzeniem przyporządkowuje k-elementowym ciągom informacji xi ciągi kodowe złożone z ciągów odwzorowujących poszczególne informacje. Tak więc warunek jednoznacznego dekodowania ma następującą postać

gdzie:







Przykład 2.2

Rozważa się dwukrotne rozszerzenie kodu podanego w przykładzie 2.2. Ciągi kodowe tego kodu podano w poniższej tablicy.

Ciągi informacyjne

Ciągi kodowe

Ciągi informacyjne

Ciągi kodowe

x1,x1

00

x3,x1

000

x1,x2

011

x3,x2

0011

x1,x3

000

x3,x3

0000

x1,x4

001

x3,x4

0001

x2,x1

110

x4,x1

010

x2,x2

1111

x4,x2

0111

x2,x3

1100

x4,x3

0100

x2,x4

1101

x4,x4

0101

Należy zauważyć, że dwóm ciągom informacyjnym x1,x3 oraz x3,x1 przyporządkowane są identyczne ciągi kodowe. Kod będący drugim rozszerzeniem kodu rozważanego nie jest kodem jednoznacznym. Powoduje to, że kod rozważany nie jest kodem jednoznacznie dekodowalnym.

Do klasy kodów jednoznacznie dekodowalnych należą m.in. kody równomierne, zdefiniowane powyżej oraz kody przecinkowe. W kodzie przecinkowym wydziela się w kodzie przecinka jeden sygnał kodowy ze zbioru alfabetu kodu. Zadaniem tego sygnału jest oddzielenie od siebie ciągów kodowych. Kody powyższe są kodami jednoznacznie dekodowalnymi, jeżeli są tylko kodami jednoznacznymi.


Przykład 2.3

W tablicy poniżej zamieszczono kod równomierny A oraz kody przecinkowe B i C.



Informacje elementarne

Ciągi kodowe

Kod A

Kod B

Kod C

x1

00

0

0

x2

01

01

10

X3

10

011

110

x4

11

0111

1110

W powyżej przedstawionych kodach przecinkowych rolę przecinka spełnia sygnał 0. Zwraca się uwagę na wpływ znajdowania się sygnału – przecinka na proces dekodowania ciągów kodowych. W kodzie B przecinek znajduje się na początku ciągów kodowych. Dekodowanie kolejnego ciągu kodowego może więc nastąpić po uzyskaniu pierwszego elementu następnego ciągu kodowego . Zdekodowanie informacji uzyskanej w chwili następuje w chwili po uzyskaniu przecinka. Kod B jest więc kodem dekodowalnym z opóźnieniem.

W kodzie równomiernym praktycznie także występuje przecinek. Jest on ukryty w stałej długości ciągów kodowych.

W kodzie C przecinek znajduje się na końcu ciągów kodowych. Dekodowanie kolejnego ciągu kodowego następuje zatem po uzyskaniu ostatniego elementu ciągu kodowego. W tym przypadku zdekodowanie informacji xi uzyskanej w chwili ti. Kod C jest więc kodem dekodowalnym bez opóźnienia.



Wprowadzony powyżej kod dekodowalny bez opóźnienia ogólnie definiuje się jako kod, którego ciągi kodowe można dekodować bez oczekiwania, aż pojawią się kolejne sygnały następnego ciągu kodowego. Kody dekodowalne bez opóźnienia nazywane będą dalej kodami chwilowymi. Oczywistym jest, że do klasy kodów chwilowych zaliczają się również kody równomierne.

Cechą charakterystyczną kodów chwilowych jest to, że żaden ciąg kodowy nie jest przedrostkiem innego ciągu kodowego. Należy dodać, że przedrostkami ciągu kodowego



Są dowolne ciągi



;

Związek pomiędzy rozpatrzonymi powyżej rodzajami kodów przedstawiono na rysunku 1.

Dalsze rozważania ograniczono do charakterystycznej klasy kodów jaką stanowią kody chwilowe.



3. Kody chwilowe

Rozpatruje się kod przyporządkowujący informacjom ze zbioru



ciągi kodowe o długościach



utworzone z sygnałów alfabetu kodu



Dla tak zdefiniowanego kodu podstawowym jego wskaźnikiem jakości jest średnia długość jego ciągów kodowych



gdzie: - prawdopodobieństwo występowania informacji ;



- długość ciągu kodowego przyporządkowanego informacji .

Dla kodów chwilowych średnią długość ciągów kodowych można oszacować wstępnie wykorzystując zależność



gdzie: - miara nieokreśloności (entropia) kodowanego źródła informacji.



Istnieje zatem zawsze możliwość skonstruowania kodu chwilowego, którego średnia długość będzie mniejsza od zwiększonej o jeden entropii kodowanych informacji. Z kolei przed konstrukcją kodu chwilowego można wstępnie oszacować średnią długość jego ciągów kodowych. Nie można jednak skonstruować kodu o średniej długości mniejszej od entropii.


4. Konstrukcje kodów metodą Huffmana. Kody zwarte

Metoda Huffmana jest ogólną metodą konstrukcji kodów zwartych. Kodem zwartym nazywany jest kod chwilowy, którego średnia długość ciągów kodowych jest najmniejsza z możliwych.

Kodowanie metodą Huffmana realizowane jest w dwóch etapach. W etapie pierwszym dokonuje się redukcji zbioru kodowanych informacji, przy czym redukcja ta składa się z ciągu redukcji elementarnych. W wyniku wykonania każdej redukcji elementarnej otrzymuje się zbiór informacji o liczności zmniejszonej o q-1 w stosunku do zbioru redukowanego. Redukcję prowadzi się aż do otrzymania zbioru informacji o liczności równej q. Uzyskanie takiego zbioru rozpoczyna drugi etap kodowania. Jeżeli w wyniku redukcji elementarnych nie uzyska się zbioru zredukowanego o liczności q należy do podstawowego zbioru informacji dodać nowe informacje (rozszerzyć zbiór podstawowy) występujące z prawdopodobieństwem równym zero. Etap drugi metody Huffmana składa się z ciągu tzw. kodowań elementarnych, realizowanych dla poszczególnych zbiorów informacji, które zostały otrzymane w wyniku kolejnych redukcji elementarnych. Należy zaznaczyć, że dla zakodowania zbioru otrzymanego w m-tym kroku redukcji, wykorzystuje się kod określony w m+1 kroku redukcji. Zakodowanie zbioru otrzymanego po zakończeniu redukcji (pierwsze kodowanie elementarne) jest bardzo proste, ponieważ zbiór ten zawiera tylko q informacji. Proces kodowania prowadzi się aż do momentu uzyskania ciągów kodowych wszystkich informacji.

Z powyższego wynika, że wyjaśnienie procedury Huffmana sprowadza się do sprecyzowania sposobu wykonywania redukcji elementarnej i kodowania elementarnego.

Redukcja elementarna

Rozważa się zbiór informacji otrzymany w kolejnym m-tym kroku redukcji



Prawdopodobieństwa występowania poszczególnych informacji wynoszą



Przyjmuje się, że informacje składowe zbioru wejściowego są uporządkowane według malejących prawdopodobieństw, tzn.



Redukcja elementarna sprowadza się do zrezygnowania z rozróżniania dwóch najmniej prawdopodobnych informacji oraz przez wprowadzenie zamiast nich nowej informacji . Prawdopodobieństwo występowania tej informacji wynosi



Tak więc w wyniku redukcji elementarnej otrzymuje się zbiór informacji



Dokonując uporządkowania informacji tego zbioru (przez przeindekso-wanie) według malejących prawdopodobieństw, otrzymuje się ostatecznie zbiór informacji będących wynikiem m+1 redukcji elementarnej




Kodowanie elementarne

Zakłada się, że dane są ciągi kodowe, za pomocą których zakodowano informacje ze zbioru wejściowego



Kodowanie elementarne, w wyniku którego otrzymuje się ciągi kodowe informacji zbioru polega na tym, że informacjom oraz przyporządkowuje się ciągi kodowe utworzone z ciągu kodowego informacji



przez dołączenie na jego końcu odpowiednio sygnałów 0 i 1.

Z kolei pozostałym informacjom zbioru przyporządkowuje się takie same ciągi kodowe jakimi zakodowane były odpowiadające im informacje zbioru .

Przykład 2.4

Konstruuje się kod zwarty zbioru informacji

Prawdopodobieństwa występowania poszczególnych informacji wynoszą odpowiednio

0,2; 0,1; 0,12; 0,3; 0,15; 0,13

Przyjmuje się binarny alfabet kodu q=2



Sposób konstrukcji kodu przedstawiono w poniższej tablicy.

X

X0

X1

X2





































0,2

0,1


0,12

0,3


0,15

0,13


00

010


011

11

101



100













0,3

0,2


0,15

0,13


0,12

0,1


11

00

101



100

011


010











0,3

0,22


0,2

0,15


0,13

11

01

00



101

100










0,3

0,28


0,22

0,2


11

10

01



00

X2

X3

X4

































0,3

0,28


0,22

0,2


11

10

01



00







0,42

0,3


0,28

0

11

10








0,58

0,42



1

0





Średnia długość ciągów kodowych dla tego kodu wynosi

L= 2(0,3+0,2) + 3(0,15+0,13+0,12+0,1) = 2,5bita/inf

Na zakończenie rozważań należy podać ważną uwagę dotyczącą przedstawionej metody: procedura Huffmana nie jest jednoznaczna, tzn. w jej wyniku można otrzymać zbiór ciągów kodowych o różnych długościach, ale dających taką samą średnią długość.



Przykład 2.5

Konstruuje się kod zwarty zbioru informacji



występujących z prawdopodobieństwami

0,4; 0,2; 0,2; 0,1; 0,05; 0,05

Sposób konstrukcji tego kodu przedstawiono w poniższych tablicach.

Średnia długość ciągów kodowych kodu projektowanego w pierwszej tablicy wynosi

L’ = 1*0,4+2*0,2+3*0,3+4*0,1+5*0,05+ =2,3bitu/inf





Zbiór pierwotny

Zbiory zredukowane

X1

X2

X3

X3













0,4

0,2


0,2

0,1


0,05

0,05


0

10

111



1101

11001


11000

0,4

0,2


0,2

0,1


0,1

0

10

111



1101

1100


0,4

0,2


0,2

0,2


0

10

111



110

0,4

0,4


0,2

0

11

10



0,6

0,4


1

0







Zbiór pierwotny

Zbiory zredukowane

X1

X2

X3

X3













0,4

0,2


0,2

0,1


0,05

0,05


11

01

00



100

1011


1010

0,4

0,2


0,2

0,1


0,1

11

01

00



101

100


0,4

0,2


0,2

0,2


11

10

01



00

0,4

0,4


0,2

0

11

10



0,6

0,4


1

0

Dla kodu projektowanego w drugiej tabeli średnia długość ciągów kodowych wynosi

L” = 2*(0,4+0,2+0,2) + 3*0,1 + 4*(0,05+0,05) = 2,3bitu/inf



Otrzymano więc

L’ = L”


©snauka.pl 2016
wyślij wiadomość