Izravni Shanonov teorem za opći izvor. Osnovni teoremi kodiranja

17.06.2019 Internet, Wi-Fi, lokalne mreže

Kodiranje informacija

Osnovni koncepti

Shannonovi teoremi o kodiranju poruka spomenuti su gore. Intuitivno je jasno da je kodiranje operacija pretvaranja informacija u oblik potreban za naknadnu obradu (prijenos komunikacijskim kanalom, pohranjivanje u memoriju računalnog sustava, korištenje za donošenje odluka itd.). Također je jasno da je pri izgradnji bilo kojeg informacijskog sustava nemoguće bez kodiranja: svaki prikaz informacija podrazumijeva korištenje nekih kodova. Stoga ćemo dalje detaljno analizirati teorijske osnove kodiranja informacija.

Neka A- proizvoljna abeceda. Elementi abecede A nazivaju se slovima (ili simbolima), a konačni nizovi sastavljeni od slova nazivaju se riječima u A... U ovom slučaju smatra se da u bilo kojoj abecedi postoji prazna riječ koja ne sadrži slova.

Riječ α 1 se naziva početak (prefiks) riječi α ako postoji riječ α 2, tako da α = α 1 α 2; dok je riječ α 1 naziva se pravi početak riječi α , ako α 2 nije prazna riječ. Duljina riječi je broj slova u riječi (prazna riječ ima duljinu 0). Snimanje α 1 α 2 označava povezanost (konkatenaciju) riječi α 1 i α 2. Riječ α 2 naziva se završetak (sufiks) riječi α ako postoji riječ α 1 takav da α = α 1 α 2; dok je riječ α 2 nazivati završetak vlastite riječi α , ako α 1 nije prazna riječ. Prazna riječ se po definiciji smatra početkom i krajem svake riječi. α .

Razmotrite abecedu B = {0, 1, …, D- 1), gdje D≥ 2, i proizvoljan skup C... Proizvoljno postavljeni prikaz C u razne riječi u abecedi B se zovu D-kodiranjem skupa C(na D= 2 kodiranje će biti binarno). Obrnuto preslikavanje naziva se dekodiranje. Evo nekoliko primjera kodiranja.

1. Kodiranje skupa prirodnih brojeva, u kojem je broj n= 0 odgovara riječi e(0) = 0 i broj n≥ 1 binarna riječ

e(n) = b 1 b 2 … b l (n)

najkraća duljina koja zadovoljava uvjet

Očito je da b 1 = 1, 2l (n) – 1 ≤ n < 2l (n) i stoga

l(n) = + 1 =] dnevnik ( n + 1)[,

gdje [ x] i ] x[označava, odnosno, najveći cijeli broj koji ne prelazi x, a najmanji cijeli broj veći od x... Riječ e(n) naziva se binarni zapis broja n, a ovo je kodiranje prikaz brojeva u binarnom brojevnom sustavu. Ovo kodiranje je jedan na jedan, budući da za n 1 ≠ n 2 riječi e(n 1) i e(n 2) različiti su. Tablica 5.1 prikazuje prikaz prvih 16 prirodnih brojeva u binarnom brojevnom sustavu.

Tablica 5.1

Kodiranje e(n)

n	e(n)	n	e(n)	n	e(n)	n	e(n)

2. Kodiranje prvih 2 k prirodni brojevi, za koje je svaki broj n (0 ≤ n < 2k) riječ

e k(n) = 0k – l (n) e(n),

gdje je unos 0 k – l (n) označava riječ koja se sastoji od k – l(n) nule, e(n) - brojčani prikaz n u binarnom brojevnom sustavu o kojem smo gore govorili. Ovo kodiranje za prvih 16 prirodnih brojeva ( k= 4) dat je u tablici 5.2.

Tablica 5.2

Kodiranje e k(n)

n	e k(n)	n	e k(n)	n	e k(n)	n	e k(n)

Neka A = {a i, i= 1, 2, ...) je konačna ili prebrojiva abeceda čija su slova numerirana prirodnim brojevima. U ovom slučaju, kodiranje slova abecede A može se postaviti u nizu D-osobne riječi V = {v i, i= 1, 2, ...), gdje je v i postoji slika slova a i... Takvi nizovi riječi (iz skupa V) nazivaju se kodovi (abeceda A). Ako je šifra data V abeceda A, zatim kodiranje riječi u kojima svaka riječ a i 1 a i 2 …a ik odgovara riječi v i 1 v i 2 …v ik naziva se kodiranje slovo po slovo.

U prijelazu s jednoznačnog kodiranja slova abecede na slovo po slovo kodiranja riječi u abecedi, svojstvo jedan-na-jedan možda neće biti očuvano. Na primjer kodiranje e(n) ne čuva ovo svojstvo, već kodiranje e k(n) sprema. Odvojivi kodovi zadržavaju svojstvo jedan na jedan. Kod V = {v i, i= 1, 2, ...) naziva se odvojivim ako je iz svake jednakosti oblika

v i 1 v i 2 …v ik = v j 1 v j 2 …v jl

slijedi to l = k i v i 1 = v j 1 , v i 2 = v j 2 , … , v ik = v jl... Odvojivi kodovi se također nazivaju jedinstveno dekodiranim kodovima.

Prefiksni kodovi pripadaju klasi odvojivih kodova. Kod V = {v i, i= 1, 2, ...) naziva se prefiks ako nema riječi v k nije početak (prefiks) nijedne riječi v l, l ≠ k... Ako se svaka riječ prefiksnog koda zamijeni svojim najmanjim početkom, koji nije početak ostalih kodnih riječi, tada će rezultirajući kod također biti s prefiksom. Ova se operacija naziva skraćivanje prefiksa.

Za proizvoljni kod V koji se sastoji od različitih riječi, možete izgraditi stablo koda. To je usmjereni graf koji ne sadrži cikluse, u kojem je vrh β 1 spojen na vrh β 2 s rubom usmjerenim od β 1 do β 2 ako i samo ako β 2 = β 1 b, gdje b Î B = {0, 1, …, D – 1}, D≥ 2. Za prefiksne kodove (i samo za njih) skup kodnih riječi poklapa se sa skupom terminalnih vrhova (vrhova iz kojih ne izlaze bridovi) kodnog stabla.

Osnovni teoremi kodiranja

Svojstva kodova korisna za njihovu praktičnu primjenu određena su osnovnim teoremima kodiranja.

Teorem 5.1. Craftova nejednakost. Za postojanje jedinstveno dekodiranog (odvojivog) koda koji sadrži N kodne riječi u skupu (0, 1, D- 1) s duljinama n 1 , n 2 , …, n N, potrebno je i dovoljno za nejednakost

Dokaz. Zamislite da imate stablo koda za prefiksni kod. Korijen stabla koda je razina 0, čvorovi povezani s korijenom su razine 1, itd. Mogući broj vrhova po k-th razina se označava kao D k... Svaki vrh k-th razina generira točno D n – k vrhovima n-th razina.

n 1 ≤ n 2 ≤…≤ n N = n.

Očito, kodna riječ duljine k točno zabranjuje D n – k mogući krajnji vrhovi (vrhovi posljednje razine). Tada sve kodne riječi prefiksnog koda zabranjuju krajnje vrhove. Budući da je ukupan broj krajnjih vrhova D n, zatim nejednakost

iz čega proizlazi da

Time je dokazana Kraftova nejednakost.

Kao rezultat dokaza teorema 5.1, zaključuje se da postoje barem prefiksni kodovi koji su jednoznačno dekodirani kodovi s duljinama kodne riječi n 1 , n 2 , …, n N zadovoljavajući Kraftovu nejednakost. Sljedeći teorem, nazvan McMillanova izjava, generalizira ovaj zaključak na sve jednoznačno dekodirane kodove.

Teorem 5.2. McMillanova nejednakost. Svaki jedinstveno dekodirani kod zadovoljava Craftovu nejednakost.

Dokaz. Podignimo zbroj na stepen L:

. (5.1)

Neka A k- broj kombinacija koje sadrže L kodne riječi ukupne duljine k... Tada se izraz (6.1) može predstaviti kao

gdje L max - maksimalna duljina poruke koja sadrži L kodne riječi. Ako je kod jednoznačno dekodiran, tada su sve sekvence iz L ukupne duljine kodnih riječi k su različiti. Pošto ima svega D k onda moguće sekvence A k ≤ D k i onda

Jer L Je li broj neovisnih kodnih riječi koje se koriste za konstruiranje svih mogućih nizova duljine koja ne prelazi L maks. Tako L ≤ L max i ... A iz ovoga proizlazi da

Budući da gornje razmišljanje vrijedi za svaki jedinstveno dekodirani kod, a ne samo za prefiksne kodove, McMillanova izjava je dokazana.

Sljedeći teoremi odnose se na entropiju izvora poruke i prosječnu duljinu kodne riječi.

Teorem 5.3. Teorem izvornog kodiranja I. Za bilo koji diskretni izvor bez memorije x s konačnom abecedom i entropijom H(x) postoji D-arnog prefiksnog koda u kojem prosječna duljina kodne riječi zadovoljava nejednakost

. (5.2)

Dokaz. Prije svega, razjasnimo da je diskretni izvor bez memorije opisan modelom koji ne uzima u obzir veze između simbola poruke. Sada dokazujemo lijevu stranu nejednakosti (6.2):

Za to koristimo definiciju entropije i Kraftove nejednakosti:

Da bismo dokazali desnu stranu nejednakosti (6.2), prepisujemo Kraftovu nejednakost u sljedećem obliku:

Zatim za svaki pojam biramo najmanji cijeli broj n i na kojem

Budući da je Kraftova nejednakost sačuvana za ovaj izbor, moguće je konstruirati odgovarajući prefiksni kod. Jer n i Je najmanji cijeli broj, tada za n i- 1 je istina

Tako je dokazan teorem izvornog kodiranja I. Određuje da prosječna duljina kodne riječi ne može biti manja od entropije izvora poruke. Primijetimo da smo u dokazu teorema koristili istu notaciju kao i pri razmatranju Kraftove nejednakosti.

Teorem 5.4. Teorem izvornog kodiranja II. Za dužinu bloka L postoji D-arnog prefiksnog koda u kojem prosječna duljina kodne riječi po znaku zadovoljava nejednakost

gdje .

Dokaz. Ovdje su blokovi znakova i H(x 1 , x 2 , …, x L) je entropija izvora poruke po bloku od L likovima. Da biste dokazali teorem, možete koristiti teorem izvornog kodiranja I:

Osim toga, budući da je minimalna dostižna duljina kodne riječi po simbolu vrijednost, tada za D= 2 redundantnost koda može se odrediti formulom .

1 | |

Program tečaja

"Teorija informacija i kodiranja"

Predavanja se održavaju u 4. godini VII semestra,

51 sat, predavač docent

Pojam informacije, entropija. Komunikacijski sustavi. Diskretni izvori. Opis izvora korištenjem slučajnog procesa. Statistička neovisnost. Markovi izvori. Ergodicnost. Ergodičnost Bernoullijevog izvora.

Izvođenje formule entropije (prema Fadeevu). Međusobne informacije i njihova svojstva. Entropijska svojstva. Teorem o maksimalnoj vrijednosti entropije. Entropija po jedinici vremena izvora poruke.

Problem kodiranja diskretnog izvora kodovima jednake duljine. Brzina kodiranja. Skupovi velike vjerojatnosti. Izravni i inverzni teoremi kodiranja diskretnog izvora kodovima jednake duljine.

Problem kodiranja izvora kodovima nejednake duljine. Trošak kodiranja. Nedvosmisleno dešifrirani kodovi. Prefiks kodovi. Kodiranje slovo po slovo. Neophodan i dovoljan uvjet za nedvosmisleno dešifriranje koda. Potpuni kodovi. Teorem za kodiranje diskretnog izvora s kodovima nejednake duljine. Algoritmi za konstruiranje optimalnih kodova (Fano, Shannon, Huffman). Konstrukcija binarnog optimalnog koda s jednakovjerojatnom distribucijom ulaznih vjerojatnosti. Primjena rezultata teorije informacija u dokazu donjih i gornjih granica za složenost realizacije Booleovih funkcija u nekim klasama upravljačkih sustava. Metoda za konstruiranje optimalnog koda pod uvjetom da je distribucija vjerojatnosti izvornih slova nepoznata. Markovljev teorem o nedvosmislenoj dešifriranju koda. Prilagodljivi algoritmi za kompresiju informacija.

Diskretni kanal bez memorije. Binarno balansirani kanal. Brzina prijenosa informacija u kanalu. Propusnost kanala. Prošireni kanal i njegova propusnost. Odlučujuće sheme i grupiranja opažanja. Vjerojatnost pogrešnog prijenosa informacija. Feinsteinova nejednakost. Izravni teorem kodiranja kanala bez memorije. Fanova nejednakost. Teorem obrade informacija. Inverzija teorema kodiranja.

Teorija kodiranja s ispravljanjem pogrešaka. Kriterij maksimalne vjerojatnosti. Udaljenost koda. Paritetni kodovi. Generativne i provjerene matrice. Sindrom. Algoritam za dekodiranje kodova za provjeru parnosti. Linearni kodovi i njihov algoritam dekodiranja. Hammingova granica. Hammingov kod. Ciklični kodovi. Ciklično kodiranje i dekodiranje.

KNJIŽEVNOST

1. Gallagher R. Teorija informacija i pouzdana komunikacija., M., Sov. Radio, 1979.

2. Krichevsky E. Predavanja o teoriji i informacijama, Novosibirsk, NSU, 1966.

3. Kolesnik V., Poltyrev G. Tečaj teorije informacija, znanost, 1982.

4. Feinstein A. Temelji teorije informacija, M., IL, 1960.

5. Peterson V., Weldon F. Kodovi za ispravljanje pogrešaka, M., Mir, 1976.

6. Bärlekamp, Algebarska teorija kodiranja, M., Mir, 1971.

Rad je dodan na web mjesto: 2016-03-30

; boja: # 000000 "xml: lang =" ru-RU "lang =" ru-RU "> 5. Kodiranje informacija

; boja: # 000000 "xml: lang =" ru-RU "lang =" ru-RU "> 5.1. Osnovni koncepti

Neka A - proizvoljna abeceda. Elementi abecede A nazivaju se slovima (ili simbolima), a konačni nizovi sastavljeni od slova nazivaju se riječima u A ... U ovom slučaju smatra se da u bilo kojoj abecedi postoji prazna riječ koja ne sadrži slova.

Riječ α 1 naziva početak (prefiks) riječiα ako postoji riječα 2 tako da je α = α 1 α 2; štoviše, riječ α 1 naziva vlastitim početkom riječiα ako je α 2 Nije prazna riječ. Duljina riječi je broj slova u riječi (prazna riječ ima duljinu 0). Snimanjeα 1 α 2 označava povezanost (konkatenaciju) riječiα 1 i α 2. Riječ α 2 naziva se završetak (sufiks) riječiα ako postoji riječα 1, tako da je α = α 1 α 2; štoviše, riječ α 2 nazivaju vlastiti završetak riječiα ako je α 1 Nije prazna riječ. Prazna riječ se po definiciji smatra početkom i krajem svake riječi.α .

Razmotrite abecedu B = (0, 1, ..., D - 1), gdje je D ≥ 2, i proizvoljan skup C ... Proizvoljno postavljeni prikaz C u razne riječi u abecedi B poziv D -kodiranjem skupa C (za D = 2 kodiranje će biti binarno). Obrnuto preslikavanje naziva se dekodiranje. Evo nekoliko primjera kodiranja.

1. Kodiranje skupa prirodnih brojeva, u kojem je broj n = 0 odgovara riječi e (0) = 0, a broj n ≥ 1 binarna riječ

e (n) = b 1 b 2 ... b l (n)

najkraća duljina koja zadovoljava uvjet

Očito, b 1 = 1, 2 l (n) - 1 ≤ n< 2 l (n ) i stoga

l (n) = + 1 =] log (n + 1) [,

gdje je [x] i] x [označava, odnosno, najveći cijeli broj koji ne prelazi x , a najmanji cijeli broj veći od x. Riječ e (n ) naziva se binarni zapis broja n , a ovo je kodiranje prikaz brojeva u binarnom brojevnom sustavu. Ovo kodiranje je jedan na jedan, budući da za n 1 ≠ n 2 riječi e (n 1) i e (n 2 ) različiti su. Tablica 5.1 prikazuje prikaz prvih 16 prirodnih brojeva u binarnom brojevnom sustavu.

"xml: lang =" ru-RU "lang =" ru-RU "> Tablica 5.1

"xml: lang =" ru-RU "lang =" ru-RU "> Kodiranje"xml: lang =" hr-US "lang =" hr-US "> e"xml: lang =" ru-RU "lang =" ru-RU "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" ru-RU "lang =" ru-RU ">)

"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)	"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)	"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)	"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)
"xml: lang =" hr-US "lang =" hr-US "> 0	"xml: lang =" hr-US "lang =" hr-US "> 0	"xml: lang =" hr-US "lang =" hr-US "> 4	"xml: lang =" hr-US "lang =" hr-US "> 100	"xml: lang =" hr-US "lang =" hr-US "> 8	"xml: lang =" hr-US "lang =" hr-US "> 1000	"xml: lang =" hr-US "lang =" hr-US "> 12	"xml: lang =" en-US "lang =" hr-US "> 1100
"xml: lang =" hr-US "lang =" hr-US "> 1	"xml: lang =" hr-US "lang =" hr-US "> 1	"xml: lang =" hr-US "lang =" hr-US "> 5	"xml: lang =" hr-US "lang =" hr-US "> 101	"xml: lang =" hr-US "lang =" hr-US "> 9	"xml: lang =" hr-US "lang =" hr-US "> 1001	"xml: lang =" hr-US "lang =" hr-US "> 13	"xml: lang =" hr-US "lang =" hr-US "> 1101
"xml: lang =" hr-US "lang =" hr-US "> 2	"xml: lang =" hr-US "lang =" hr-US "> 10	"xml: lang =" hr-US "lang =" hr-US "> 6	"xml: lang =" hr-US "lang =" hr-US "> 110	"xml: lang =" hr-US "lang =" hr-US "> 10	"xml: lang =" hr-US "lang =" hr-US "> 1010	"xml: lang =" hr-US "lang =" hr-US "> 14	"xml: lang =" hr-US "lang =" hr-US "> 1110
"xml: lang =" hr-US "lang =" hr-US "> 3	"xml: lang =" hr-US "lang =" hr-US "> 11	"xml: lang =" hr-US "lang =" hr-US "> 7	"xml: lang =" hr-US "lang =" hr-US "> 111	"xml: lang =" hr-US "lang =" hr-US "> 11	"xml: lang =" hr-US "lang =" hr-US "> 1011	"xml: lang =" hr-US "lang =" hr-US "> 15	"xml: lang =" hr-US "lang =" hr-US "> 1111

2. Kodiranje prvih 2 k prirodni brojevi, za koje je svaki broj n (0 ≤ n< 2 k ) riječ

e k (n) = 0 k - l (n) e (n),

gdje je oznaka 0 k - l (n) označava riječ koja se sastoji od k - l (n) nule, e (n ) - brojčani prikaz n u binarnom brojevnom sustavu o kojem smo gore govorili. Ovo kodiranje za prvih 16 prirodnih brojeva ( k = 4) dat je u tablici 5.2.

"xml: lang =" ru-RU "lang =" ru-RU "> Tablica 5."xml: lang =" hr-US "lang =" hr-US "> 2

"xml: lang =" ru-RU "lang =" ru-RU "> Kodiranje"xml: lang =" hr-US "lang =" hr-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" ru-RU "lang =" ru-RU "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" ru-RU "lang =" ru-RU ">)

"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)	"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)	"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)	"xml: lang =" hr-US "lang =" hr-US "> n	"xml: lang =" hr-US "lang =" hr-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" hr-US "lang =" hr-US "> ("xml: lang =" hr-US "lang =" hr-US "> n"xml: lang =" hr-US "lang =" hr-US ">)
"xml: lang =" hr-US "lang =" hr-US "> 0	"xml: lang =" hr-US "lang =" hr-US "> 0000	"xml: lang =" hr-US "lang =" hr-US "> 4	"xml: lang =" hr-US "lang =" hr-US "> 0100	"xml: lang =" hr-US "lang =" hr-US "> 8	"xml: lang =" hr-US "lang =" hr-US "> 1000	"xml: lang =" hr-US "lang =" hr-US "> 12	"xml: lang =" en-US "lang =" hr-US "> 1100
"xml: lang =" hr-US "lang =" hr-US "> 1	"xml: lang =" hr-US "lang =" hr-US "> 0001	"xml: lang =" hr-US "lang =" hr-US "> 5	"xml: lang =" hr-US "lang =" hr-US "> 0101	"xml: lang =" hr-US "lang =" hr-US "> 9	"xml: lang =" hr-US "lang =" hr-US "> 1001	"xml: lang =" hr-US "lang =" hr-US "> 13	"xml: lang =" hr-US "lang =" hr-US "> 1101
"xml: lang =" hr-US "lang =" hr-US "> 2	"xml: lang =" hr-US "lang =" hr-US "> 0010	"xml: lang =" hr-US "lang =" hr-US "> 6	"xml: lang =" hr-US "lang =" hr-US "> 0110	"xml: lang =" hr-US "lang =" hr-US "> 10	"xml: lang =" hr-US "lang =" hr-US "> 1010	"xml: lang =" hr-US "lang =" hr-US "> 14	"xml: lang =" hr-US "lang =" hr-US "> 1110
"xml: lang =" hr-US "lang =" hr-US "> 3	"xml: lang =" hr-US "lang =" hr-US "> 0011	"xml: lang =" hr-US "lang =" hr-US "> 7	"xml: lang =" hr-US "lang =" hr-US "> 0111	"xml: lang =" hr-US "lang =" hr-US "> 11	"xml: lang =" hr-US "lang =" hr-US "> 1011	"xml: lang =" hr-US "lang =" hr-US "> 15	"xml: lang =" hr-US "lang =" hr-US "> 1111

Neka je A = (a i, i = 1, 2, ...) je konačna ili prebrojiva abeceda čija su slova numerirana prirodnim brojevima. U ovom slučaju, kodiranje slova abecede A može se postaviti u nizu D -arne riječi V = (v i, i = 1, 2, ...), gdje je v i postoji slika slova a i ... Takvi nizovi riječi (iz skupa V ) nazivaju se kodovi (abeceda A). Ako je dan šifra V abecede A , zatim kodiranje riječi u kojima svaka riječ a i 1 a i 2 ... a ik odgovara riječi v i 1 v i 2 ... v ik naziva se kodiranje slovo po slovo.

U prijelazu s jednoznačnog kodiranja slova abecede na slovo po slovo kodiranja riječi u abecedi, svojstvo jedan-na-jedan možda neće biti očuvano. Na primjer kodiranje e (n ) ne čuva ovo svojstvo, već kodiranje e k (n ) sprema. Odvojivi kodovi zadržavaju svojstvo jedan na jedan. Kod V = (v i, i = 1, 2, ...) naziva se odvojivim ako je iz svake jednakosti oblika

v i 1 v i 2… v ik = v j 1 v j 2… v jl

slijedi da je l = k i v i 1 = v j 1, v i 2 = v j 2,..., v ik = v jl ... Odvojivi kodovi se također nazivaju jedinstveno dekodiranim kodovima.

Prefiksni kodovi pripadaju klasi odvojivih kodova. Kod V = (v i, i = 1, 2, ...) naziva se prefiks ako nema riječi v k nije početak (prefiks) nijedne riječi v l, l ≠ k ... Ako se svaka riječ prefiksnog koda zamijeni svojim najmanjim početkom, koji nije početak ostalih kodnih riječi, tada će rezultirajući kod također biti s prefiksom. Ova se operacija naziva skraćivanje prefiksa.

Za proizvoljni kod V koji se sastoji od različitih riječi, možete izgraditi stablo koda. To je usmjereni graf koji ne sadrži cikluse, u kojem je vrhβ 1 spojena na vrhβ 2 rub usmjeren odβ 1 do β 2 , ako i samo akoβ 2 = β 1 b, gdje je b  B = (0, 1, ..., D - 1), D ≥ 2. Za prefiksne kodove (i samo za njih) skup kodnih riječi poklapa se sa skupom terminalnih vrhova (vrhova iz kojih ne izlaze bridovi) kodnog stabla.

5.2. Osnovni teoremi kodiranja

Svojstva kodova korisna za njihovu praktičnu primjenu određena su osnovnim teoremima kodiranja.

Teorem 5.1. Craftova nejednakost.Za postojanje jedinstveno dekodiranog (odvojivog) koda koji sadrži N kodne riječi u skupu (0, 1, D - 1) s duljinama n 1, n 2, ..., n N , potrebno je i dovoljno za nejednakost

Dokaz. Zamislite da imate stablo koda za prefiksni kod. Korijen stabla koda je razina 0, čvorovi povezani s korijenom su razine 1, itd. Mogući broj vrhova po k -th razina se označava kao D k. Svaki vrh k -th razina generira točno D n - k vrhova n -te razine.

n 1 ≤ n 2 ≤… ≤ n N = n.

Očito, kodna riječ duljine k točno zabranjuje D n - k mogući krajnji vrhovi (vrhovi posljednje razine). Tada sve kodne riječi prefiksnog koda zabranjuju krajnje vrhove. Budući da je ukupan broj krajnjih vrhova D n , zatim nejednakost

iz čega proizlazi da

Time je dokazana Kraftova nejednakost.

Kao rezultat dokaza teorema 5.1, zaključuje se da postoje barem prefiksni kodovi koji su jednoznačno dekodirani kodovi s duljinama kodne riječi n 1, n 2, ..., n N zadovoljavajući Kraftovu nejednakost. Sljedeći teorem, nazvan McMillanova izjava, generalizira ovaj zaključak na sve jednoznačno dekodirane kodove.

Teorem 5.2. McMillanova nejednakost.Svaki jedinstveno dekodirani kod zadovoljava Craftovu nejednakost.

Dokaz. Podignimo zbroj na stepen L:

. (5.1)

Neka je A k - broj kombinacija koje sadrže L kodne riječi ukupne duljine k ... Tada se izraz (6.1) može predstaviti kao

gdje je L max - maksimalna duljina poruke koja sadrži L kodne riječi. Ako je kod jednoznačno dekodiran, tada su sve sekvence iz L ukupne duljine kodnih riječi k su različiti. Pošto ima svega D k onda moguće sekvence A k ≤ D k i tada

Budući da je L Je li broj neovisnih kodnih riječi koje se koriste za konstruiranje svih mogućih nizova duljine koja ne prelazi L max. Dakle, L ≤ L max i. A iz ovoga proizlazi da

Budući da gornje razmišljanje vrijedi za svaki jedinstveno dekodirani kod, a ne samo za prefiksne kodove, McMillanova izjava je dokazana.

Sljedeći teoremi odnose se na entropiju izvora poruke i prosječnu duljinu kodne riječi.

Teorem 5.3. Teorem izvornog kodiranja ja Za bilo koji diskretni izvor bez memorije x s konačnom abecedom i entropijom H (X) postoji D -arnog prefiksnog koda u kojem prosječna duljina kodne riječi zadovoljava nejednakost

. (5.2)

Dokaz. Prije svega, razjasnimo da je diskretni izvor bez memorije opisan modelom koji ne uzima u obzir veze između simbola poruke. Sada dokazujemo lijevu stranu nejednakosti (6.2):

Za to koristimo definiciju entropije i Kraftove nejednakosti:

Da bismo dokazali desnu stranu nejednakosti (6.2), prepisujemo Kraftovu nejednakost u sljedećem obliku:

Zatim za svaki pojam biramo najmanji cijeli broj n i za koje

Budući da je Kraftova nejednakost sačuvana za ovaj izbor, moguće je konstruirati odgovarajući prefiksni kod. Jer n i Je najmanji cijeli broj, tada za n i - 1

Zatim

Dakle, teorem izvornog kodiranja ja dokazano. Određuje da prosječna duljina kodne riječi ne može biti manja od entropije izvora poruke. Primijetimo da smo u dokazu teorema koristili istu notaciju kao i pri razmatranju Kraftove nejednakosti.

Teorem 5.4. Teorem izvornog kodiranja II. Za blok duljine L postoji D -arnog prefiksnog koda u kojem prosječna duljina kodne riječi po znaku zadovoljava nejednakost

gdje.

Dokaz. Ovdje su blokovi znakova i H (X 1, X 2, ..., X L ) Je li entropija izvora poruke po bloku od L likovima. Da biste dokazali teorem, možete koristiti teorem izvornog kodiranja ja:

Teorem izvornog kodiranja II omogućuje nam da tvrdimo da postoje takve metode kodiranja za dovoljno dugu poruku da se prosječna duljina kodne riječi može proizvoljno približiti vrijednosti. Doista, za L  ∞, H L (X)  H, gdje je H Da li je entropija izvora poruke po jednom simbolu, nejednakost je istinita

, (5.3)

gdje. To se također može protumačiti na sljedeći način: za bilo koji proizvoljno mali brojε , postoji metoda za kodiranje blokova koji sadrže simbole, u kojoj je nejednakost (5.3) zadovoljena za prosječnu duljinu kodne riječi po simbolu.

Osim toga, budući da je minimalna dostižna duljina kodne riječi po simbolu vrijednost, tada za D = 2 redundantnost koda može se odrediti formulom.

; boja: # 000000 "xml: lang =" ru-RU "lang =" ru-RU "> 5.3. Optimalno kodiranje

Zadatak konstruiranja optimalnog koda je pronaći pozitivne cijele brojeve n 1, n 2, ..., n N minimiziranje prosječne duljine kodne riječi, pod uvjetom da je zadovoljena Kraftova nejednakost:

Prilikom konstruiranja kodova u slučaju abecede A = (a i, i = 1, 2, ..., N ) s poznatom distribucijom vjerojatnosti P = (p i, i = 1, 2, ..., N ) bez gubitka općenitosti, možemo pretpostaviti da su slova abecede A numerirani su silaznim redoslijedom njihovih vjerojatnosti, tj. p 1 ≥ p 2 ≥… ≥ p N ... Osim toga, razmotrit ćemo samo binarne kodove.

Postoje dvije poznate metode (Fano i Shannon) za konstruiranje kodova koji su blizu optimalnih. Fanova metoda je sljedeća. Popis slova, poredan silaznim redoslijedom vjerojatnosti, podijeljen je u dva uzastopna dijela tako da se zbrojevi vjerojatnosti slova koja su u njima što manje razlikuju jedan od drugog. Slova iz prvog dijela dobivaju znak 0, a slovima iz drugog dijela oznaku 1. Nadalje, isto se radi sa svakim od primljenih dijelova, ako sadrži najmanje dva slova. Proces se nastavlja sve dok se cijeli popis ne podijeli na dijelove koji sadrže po jedno slovo. Svako slovo je povezano s nizom znakova koji su kao rezultat ovog procesa dodijeljeni ovom slovu. Lako je vidjeti da je rezultirajući kod s prefiksom.

Shanonova metoda je primjenjiva samo kada su sve vjerojatnosti pozitivne. Sastoji se u tome da slov a i s vjerojatnošću p i > 0, niz iz n i =] log (1 / p i ) [prve znamenke nakon decimalne točke u proširenju broja u beskonačni razlomak (za a 1 pretpostavljamo da je q 1 = 0). Budući da je u l> k (s obzirom na činjenicu da p l ≤ p k) n l ≥ n k a zatim se tako dobiveni kod stavlja prefiks. Na temelju dobivenog prefiksnog koda konstruira se skraćeni prefiksni kod koji je rezultat kodiranja Shannon metodom.

Na primjer, neka postoji skup slova A = (a 1, a 2, a 3, a 4, a 5, a 6, a 7 ) s distribucijom vjerojatnosti P = (0,2, 0,2, 0,19, 0,12, 0,11, 0,09, 0,09). Provedimo kodiranje slova Fano metodom.

1. Popis podijelite na dva dijela tako da se zbroji vjerojatnosti slova uključenih u njih što manje razlikuju jedan od drugog:

A 1 = (a 1, a 2, a 3), P 1 = (0,2, 0,2, 0,19);

A 2 = (a 4, a 5, a 6, a 7), P 2 = (0,12, 0,11, 0,09, 0,09).

2. Dodijelimo slovima iz prvog dijela simbol 0, a slovima drugog dijela simbol 1:

A 1 = (a 1/0, a 2/0, a 3/0);

A 2 = (a 4/1, a 5/1, a 6/1, a 7/1).

3. Ponovimo gore navedene korake u nizu za svaki od dijelova posebno. V kao rezultat dobivamo:

A 1 1 = (a 1/00);

A 121 = (a 2/010);

A 122 = (a 3/011);

A 211 = (a 4/100);

A 212 = (a 5/101);

A 221 = (a 6/110);

A 222 = (a 7/111).

Rezultirajuće kodne riječi prikazane su za svako slovo desno od kose crte. U ovom slučaju redoslijed indeksa dobivenih jednoslovnih popisa pokazuje slijed dijeljenja izvornog popisa skupina na dijelove.

Fano proces kodiranja prikladno je oblikovan u obliku tablice. Za razmatrani primjer prikazan je u tablici 5.3.

"xml: lang =" ru-RU "lang =" ru-RU "> Tablica 5.3

"xml: lang =" ru-RU "lang =" ru-RU "> Fano kodiranje

"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0,20	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 00
"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 2	"xml: lang =" ru-RU "lang =" ru-RU "> 0,20		"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 010
"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 3	"xml: lang =" ru-RU "lang =" ru-RU "> 0,19			"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 011
"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 4	"xml: lang =" ru-RU "lang =" ru-RU "> 0.12	"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 100
"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 5	"xml: lang =" ru-RU "lang =" ru-RU "> 0.11			"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 101
"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 6	"xml: lang =" ru-RU "lang =" ru-RU "> 0.09		"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 110
"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 7	"xml: lang =" ru-RU "lang =" ru-RU "> 0.09			"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 111

Odredimo prosječnu duljinu kodne riječi:

Sada napravimo Shannon kodiranje. Proces kodiranja prikazan je u tablici 5.4.

"xml: lang =" ru-RU "lang =" ru-RU "> Tablica 5.4

"xml: lang =" ru-RU "lang =" ru-RU "> Shannon kodiranje

"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" hr-US "lang =" hr-US "> n; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" hr-US "lang =" hr-US "> q; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" ru-RU "lang =" ru-RU "> Kôd"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" ru-RU "lang =" ru-RU "> Skraćeni kod"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i
"xml: lang =" hr-US "lang =" hr-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" hr-US "lang =" hr-US ">] 2.321… [= 3	"xml: lang =" hr-US "lang =" hr-US "> 0	000	000
a 2	] 2.321… [= 3	0.2	001	001
a 3	] 2.395… [= 3	0.4	011	01
a 4	] 3.058… [= 4	0,59	1001	100
a 5	] 3.183… [= 4	0,71	1011	101
a 6	] 3.472… [= 4	0,82	1101	110
a 7	] 3.472… [= 4	0,91	1110	111

Kao i u prethodnom slučaju, nalazimo prosječnu duljinu kodne riječi:

Kao što možete vidjeti, rezultati kodiranja Fano i Shannon metodama u smislu minimiziranja prosječne duljine koda praktički su se poklopili. Stoga se ove metode često smatraju jednom (u Fanovoj formulaciji) i nazivaju Shannon-Fano metoda.

David Huffman je 1952. godine predložio metodu optimalnog prefiksnog kodiranja za diskretne izvore, koja se, za razliku od metoda Shannon i Fano, još uvijek koristi u praksi. D. Huffman je dokazao da će prosječna duljina kodne riječi, dobivena njegovom metodom, biti minimalna. Huffmanovo kodiranje radi se u tri koraka.

1. Redoslijed: slova su poredana silaznim redoslijedom njihovih vjerojatnosti.

2. Redukcija: dva slova s najmanjom vjerojatnošću spajaju se u jedno s ukupnom vjerojatnošću; popis slova se preuređuje prema koraku 1; proces se nastavlja dok se sva slova ne spoje u jedno. U ovom slučaju moguće je postići izjednačavanje duljina kodnih riječi koristeći sljedeću strategiju: ako nekoliko slova ima iste vjerojatnosti, tada se ona dva od njih koja su prethodno imala najmanji broj spojeva kombiniraju (iako to neće utjecati na prosječnu duljinu koda).

3. Kodiranje: počevši od posljednjeg spoja, jednoj komponenti složenog slova uzastopno se dodjeljuje simbol 0, a drugoj - simbolu 1; proces se nastavlja sve dok se sva izvorna slova ne kodiraju.

Izvedimo Huffmanovo kodiranje za skup razmatran u primjerima primjene Fano i Shannon metoda.

1. Izvorni popis pisamaA = { a1 , a2 , a3 , a4 , a5 , a6 , a7 ) je već naručeno odP = {0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}.

2. Kombinirajte slovaa6 ia7 u jednom slovua1 s vjerojatnošću0.18 ipreureditipopis:

P1 = {0.2, 0.2, 0.19, 0.18, 0.12, 0.11}, A1 = { a1 , a2 , a3 , a1 , a4 , a5 }.

3. Ponovite korak 2 dok na popisu ne ostane samo jedno slovo:

P2 = {0.23, 0.2, 0.2, 0.19, 0.18}, A2 = { a2 , a1 , a2 , a3 , a1 };

P3 = {0.37, 0.23, 0.2, 0.2}, A3 = { a3 , a2 , a1 , a2 };

P4 = {0.4, 0.37, 0.23}, A4 = { a4 , a3 , a2 };

P5 = {0.6, 0.4}, A5 = { a5 , a4 };

P6 = {1}, A6 = { a6 }.

4. Dodijelimobinarnikodovisimboli:

a6 : a5 = 0, a4 = 1;

a5 : a3 = 00, a2 = 01;

a4 : a1 = 10, a2 = 11;

a3 : a3 = 000, a1 = 001;

a2 : a4 = 010, a5 = 011;

a1 : a6 = 0010, a7 = 0011.

Stoga su sljedeći binarni kodovi dodijeljeni izvornim slovima:a1 = 10, a2 = 11, a3 = 000, a4 = 010, a5 = 011, a6 = 0010, a7 = 0011, što daje prosječnu duljinu koda koja je manja nego u slučaju kodiranja Fano i Shannon.

Definirajmo redundanciju primljenih kodova. Da bismo to učinili, nalazimo entropiju izvora poruke:

Tada kodovi imaju sljedeću redundanciju:

Fano kod:;

Shannon kod:;

Huffmanova šifra:.

Dakle, redundantnost Huffmanovog koda je minimalna.

Za smanjenje redundancije, t.j. smanjujući prosječnu duljinu kodne riječi za jedan simbol, možete koristiti blok kodiranje, čije je obrazloženje dano u teoremu izvornog kodiranjaII... U tom slučaju potrebno je dobiti sve moguće skupine slova zadane duljine, pronaći vjerojatnosti grupa, kao vjerojatnosti zajedničkog pojavljivanja slova grupe u isto vrijeme, te izvršiti kodiranje, s obzirom na grupe kao simboli nove abecede.

STRANA 43

Izravni Shanonov teorem za opći izvor. Osnovni teoremi kodiranja

; boja: # 000000 "xml: lang =" ru-RU "lang =" ru-RU "> 5. Kodiranje informacija

; boja: # 000000 "xml: lang =" ru-RU "lang =" ru-RU "> 5.1. Osnovni koncepti

; boja: # 000000 "xml: lang =" ru-RU "lang =" ru-RU "> 5.3. Optimalno kodiranje

Vrhunski povezani članci