Teorema e drejtpërdrejtë e Shanonit për një burim të formës së përgjithshme. Teoremat bazë të kodimit

Informacion kodues

Konceptet themelore

Teoremat e Shannon-it mbi kodimin e mesazheve u përmendën më lart. Është intuitivisht e qartë se kodimi është operacioni i konvertimit të informacionit në formën e kërkuar për përpunimin e mëvonshëm (transmetimi përmes një kanali komunikimi, ruajtja në memorie sistemi informatik, përdorim për vendimmarrje, etj.). Është gjithashtu e qartë se kur ndërtohet ndonjë sistemi i informacionitËshtë e pamundur të bëhet pa kodim: çdo paraqitje e informacionit nënkupton përdorimin e një lloj kodi. Prandaj, ne do të analizojmë më tej në detaje bazë teorike informacion kodues.

Le A– alfabet arbitrar. Elementet e alfabetit A quhen shkronja (ose simbole), dhe sekuencat e fundme të përbëra nga shkronja quhen fjalë në A. Besohet se në çdo alfabet ka një fjalë boshe që nuk përmban shkronja.

fjalë α 1 quhet fillimi (parashtesa) i një fjale α , nëse fjala ekziston α 2, e tillë që α = α 1 α 2 ; në të njëjtën kohë fjala α 1 quhet fillimi i duhur i një fjale α , Nëse α 2 nuk është një fjalë boshe. Gjatësia e fjalës është numri i shkronjave në fjalë (një fjalë boshe ka gjatësi 0). Regjistro α 1 α 2 tregon lidhjen (lidhjen) e fjalëve α 1 dhe α 2. fjalë α 2 quhet mbaresa (prapashtesa) e një fjale α , nëse fjala ekziston α 1, e tillë që α = α 1 α 2 ; në të njëjtën kohë fjala α 2 quhet mbarimi i duhur i një fjale α , Nëse α 1 nuk është një fjalë boshe. Një fjalë boshe sipas përkufizimit konsiderohet fillimi dhe mbarimi i çdo fjale α .

Merrni parasysh alfabetin B = {0, 1, …, D– 1), ku D≥ 2, dhe një grup arbitrar C. Shfaqja arbitrare e një grupi C me shumë fjalë në alfabet B thirrur D Kodimi i grupit ary C(në D= 2 kodimi do të jetë binar). Hartëzimi i anasjelltë quhet dekodim. Le të japim shembuj të kodimeve.

1. Kodimi i bashkësisë së numrave natyrorë, në të cilin numri n= 0 përputhet me fjalën e(0) = 0, dhe numri n ≥ 1 fjalë binare

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

gjatësia më e vogël që plotëson kushtin

Është e qartë se b 1 = 1, 2l (n) – 1 ≤ n < 2l (n) dhe për këtë arsye

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

ku [ x] Dhe ] x[ tregon numrin më të madh të plotë që nuk tejkalon x, dhe numri i plotë më i vogël më i madh se x. fjalë e(n) quhet shënimi binar i një numri n, dhe ky kodim është përfaqësimi i numrave në sistemi binar Duke llogaritur. Ky kodimështë një me një sepse kur n 1 ≠ n 2 fjalë e(n 1) dhe e(n 2) të ndryshme. Tabela 5.1 tregon paraqitjen e 16 numrave të parë natyrorë në sistemin e numrave binar.

Tabela 5.1

Kodimi e(n)

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

2. Kodimi i 2 të parëve k numrat natyrorë, për të cilët çdo numër n (0 ≤ n < 2k) përputhet me fjalën

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

ku hyrja 0 k – l (n) tregon një fjalë të përbërë nga k – l(n) zero, e(n) – paraqitje e një numri n në sistemin e numrave binar të diskutuar më sipër. Ky kodim është për 16 numrat e parë natyrorë ( k= 4) është dhënë në tabelën 5.2.

Tabela 5.2

Kodimi e k(n)

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

Le A = {a i, i= 1, 2, ...) - një alfabet i fundëm ose numërues, shkronjat e të cilit janë të numëruara numrat natyrorë. Në këtë rast, kodimi i shkronjave të alfabetit A mund të specifikohet me sekuencë D-fjalë fjalë për fjalë V = {v i, i= 1, 2, ...), ku v i ka një imazh të një letre a i. Sekuenca të tilla fjalësh (nga grupi V) quhen kode (të alfabetit A). Nëse jepet kodi V alfabeti A, pastaj kodimi i fjalëve, në të cilin çdo fjalë a i 1 a i 2 …një ik përputhet me fjalën v i 1 v i 2 …v ik, quhet kodim shkronjë për shkronjë.

Kur kaloni nga kodimi një-në-një i shkronjave të alfabetit në kodimin shkronjë për shkronjë të fjalëve në alfabet, vetia e karakterit një-për-një mund të mos ruhet. Për shembull, kodimi e(n) nuk kursen këtë pronë, dhe kodimi e k(n) e ruan atë. Prona një-për-një ruhet nga kode të ndashme. Kodi V = {v i, i= 1, 2, …) quhet i ndashëm nëse nga çdo barazi e formës

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

vijon se l = k Dhe v i 1 = v j 1 , v i 2 = v j 2 , … , v ik = vjl. Kodet e ndashme quhen gjithashtu kode unike të dekodueshme.

Kodet e parashtesave i përkasin klasës së kodeve të ndashme. Kodi V = {v i, i= 1, 2, ...) quhet parashtesë nëse nuk ka fjalë vk nuk është fillimi (parashtesa) i asnjë fjale v l, l ≠ k. Nëse çdo fjalë e një kodi prefiks zëvendësohet nga fillimi i saj më i vogël, i cili nuk është fillimi i fjalëve të tjera të kodit, atëherë kodi që rezulton do të jetë gjithashtu një parashtesë. Ky operacion quhet shkurtimi i kodit të prefiksit.

Për kodin arbitrar V, përbërë nga fjalë të ndryshme, mund të ndërtoni një pemë kodi. Ky është një grafik i drejtuar që nuk përmban cikle, në të cilat kulmi β 1 i lidhur në krye β 2 buzë drejtuar nga β 1 deri në β 2 nëse dhe vetëm nëse β 2 = β 1 b, Ku b Î B = {0, 1, …, D – 1}, D≥ 2. Për kodet e parashtesave (dhe vetëm për to), grupi i fjalëve kodike përkon me bashkësinë e kulmeve fundore (kulme nga të cilat nuk buron asnjë skaj) pema e kodit.

Teoremat bazë të kodimit

Vetitë e kodeve të dobishme për to aplikim praktik, përcaktohen nga teoremat bazë të kodimit.

Teorema 5.1. Pabarazia e Kraft. Për ekzistencën e një kodi unik të dekodueshëm (të ndashëm) që përmban N fjalët e kodit në grup (0, 1, D– 1) me gjatësi n 1 , n 2 , …, n N, është e nevojshme dhe e mjaftueshme që pabarazia të mbahet

Dëshmi. Le të imagjinojmë se kemi një pemë kodi për një kod prefiks. Rrënja e pemës së kodit formon nivelin 0, kulmet e lidhura me formën rrënjë niveli 1, etj. Numri i mundshëm i kulmeve për k-nivelin e shënojmë si Dk. Çdo majë k niveli pjell saktësisht Dn – k majat n- niveli.

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

Natyrisht, kodi i gjatësisë k ndalon saktësisht Dn – k kulme të mundshme fundore (kulme të nivelit të fundit). Pastaj të gjitha fjalët kodike të kodit të prefiksit ndalojnë kulmet fundore. Sepse numri total kulmet fundore janë të barabarta Dn, atëherë pabarazia është e vërtetë

,

nga e cila rrjedh se

Kështu, pabarazia e Kraft-it vërtetohet.

Si rezultat i vërtetimit të Teoremës 5.1, është konkluduar se ka të paktën kode prefikse që janë kode unike të dekodueshme me gjatësi fjalësh kodike. n 1 , n 2 , …, n N, duke kënaqur pabarazinë e Kraft. Teorema e mëposhtme, e quajtur pohimi i McMillanit, përgjithësohet këtë përfundim për të gjitha kodet unike të dekodueshme.

Teorema 5.2. Pabarazia e McMillanit.Çdo kod i dekodueshëm në mënyrë unike plotëson pabarazinë e Kraft.

Dëshmi. Le ta ngremë shumën në një fuqi L:

. (5.1)

Le Një k– numri i kombinimeve që përmbajnë L fjalë kodesh me gjatësi totale k. Atëherë shprehja (6.1) mund të paraqitet si

,

Ku L maksimumi - gjatësia maksimale mesazhet që përmbajnë L fjalë kodike. Nëse kodi është i dekodueshëm në mënyrë unike, atëherë të gjitha sekuencat nga L fjalë kodike me gjatësi totale k janë të ndryshme. Meqenëse ka vetëm Dk sekuencat e mundshme, atëherë Një k ≤ Dk dhe pastaj

Sepse Lështë numri i fjalëve kodike të pavarura që përdoren për të ndërtuar të gjitha sekuencat e mundshme të gjatësisë që nuk i kalon L maksimumi Kjo është arsyeja pse L ≤ L max dhe . Dhe nga kjo rrjedh se

Meqenëse arsyetimi i mësipërm është i vlefshëm për çdo kod të dekodueshëm në mënyrë unike, dhe jo vetëm për kodet e parashtesave, pohimi i McMillan është i vërtetuar.

Teoremat e mëposhtme lidhin entropinë e burimit të mesazhit dhe gjatësinë mesatare fjalë kodike.

Teorema 5.3. Teorema e kodimit burimor I. Për çdo burim diskret pa memorie X me alfabet dhe entropi të fundme H(X) ekziston D-ichny kodi i prefiksit, në të cilën gjatësia mesatare e fjalës së koduar plotëson pabarazinë

. (5.2)

Dëshmi. Fillimisht, le të shpjegojmë se një burim diskret pa memorie përshkruhet nga një model që nuk merr parasysh lidhjet midis simboleve të mesazhit. Tani vërtetojmë anën e majtë të pabarazisë (6.2):

Për ta bërë këtë, ne përdorim përkufizimin e entropisë dhe pabarazisë së Kraft:

Për të vërtetuar anën e djathtë të pabarazisë (6.2), ne rishkruajmë pabarazinë e Kraft në formën e mëposhtme:

.

Pastaj zgjedhim për çdo term numrin më të vogël të plotë n i, në të cilën

Meqenëse pabarazia e Kraft mbetet e njëjtë me këtë zgjedhje, ne mund të ndërtojmë kodin përkatës të prefiksit. Sepse n iështë numri i plotë më i vogël, atëherë për n i- 1 është e drejtë

Kështu, vërtetohet teorema e kodimit burimor I. Ai përcakton që gjatësia mesatare e një fjale kod nuk mund të jetë më e vogël se entropia e burimit të mesazhit. Vini re se vërtetimi i teoremës përdori të njëjtin shënim si kur merret parasysh pabarazia e Kraft.

Teorema 5.4. Teorema e kodimit burimor II. Për gjatësinë e bllokut L ekziston D-kodi i prefiksit ary në të cilin gjatësia mesatare e një fjale kode për karakter plotëson pabarazinë

,

Ku .

Dëshmi. Këtu, blloqe personazhesh dhe H(X 1 , X 2 , …, X L) është entropia e burimit të mesazhit për bllok të L personazhet. Për të vërtetuar teoremën, mund të përdorni teoremën e kodimit burimor I:

Përveç kësaj, meqenëse gjatësia minimale e arritshme e një fjale kodi për simbol është vlera , atëherë kur D= 2 teprica e kodit mund të përcaktohet nga formula .

1 | |

Programi i kursit

"Teoria e informacionit dhe kodimit"

Ligjëratat mbahen në vitin e 4-të, semestri VII,

51 orë, pedagog profesor i asociuar

Koncepti i informacionit, entropia. Sistemet e komunikimit. Burime diskrete. Përshkrimi i burimit duke përdorur proces i rastësishëm. Pavarësia statistikore. Burimet e Markovit. Ergodiciteti. Ergodiciteti i burimit Bernoulli.

Nxjerrja e formulës së entropisë (sipas Fadeev). Informacioni i ndërsjellë dhe vetitë e tij. Vetitë e entropisë. Teorema rreth vlera maksimale entropia. Entropia për njësi të kohës së burimit të mesazhit.

Problemi i kodimit të një burimi diskret me kode gjatësi të barabartë. Shpejtësia e kodimit. Komplete me probabilitet të lartë. Teorema direkte dhe inverse për kodimin e një burimi diskret me kode me gjatësi të barabartë.

Problemi i kodimit të një burimi me kode me gjatësi të pabarabartë. Kostoja e kodimit. Kodet e deshifrueshme pa mëdyshje. Kodet e parashtesave. Kodimi shkronjë për shkronjë. Një kusht i domosdoshëm dhe i mjaftueshëm për deshifrueshmërinë unike të një kodi. Kodet e plota. Teorema për kodimin e një burimi diskret me kode me gjatësi të pabarabartë. Algoritme për ndërtimin e kodeve optimale (Fano, Shannon, Huffman). Ndërtimi i një kodi binar optimal me një shpërndarje probabiliteti të barabartë të probabiliteteve hyrëse. Zbatimi i teorisë së informacionit rezulton në vërtetimin e kufijve të poshtëm dhe të sipërm për kompleksitetin e zbatimit Funksionet Boolean në disa klasa të sistemeve të kontrollit. Një metodë për ndërtimin e një kodi optimal me kushtin që shpërndarja e probabilitetit të shkronjave burimore të jetë e panjohur. Teorema e Markovit mbi deshifrueshmërinë unike të një kodi. Algoritme adaptive për kompresimin e informacionit.

Kanal diskret pa memorie. Binar kanal simetrik. Shpejtësia e transmetimit të informacionit në kanal. Kapaciteti i kanalit. Kanali i zgjeruar dhe ai xhiros. Modele dhe grupime vendimtare të vëzhgimeve. Mundësia e transmetimit të gabuar të informacionit. Pabarazia e Feinstein. Teorema direkte për kodimin e kanalit pa memorie. Pabarazia e Fanos. Teorema e përpunimit të informacionit. Përmbysja e teoremës së kodimit.

Teoria e kodimit rezistent ndaj zhurmës. Kriteri i gjasave maksimale. Distanca e kodit. Kodet e barazisë. Gjenerative dhe kontrolloni matricat. Sindromi. Algoritmi i dekodimit për kodet e kontrollit të barazisë. Kodet lineare dhe algoritmin e tyre të dekodimit. Hamming i lidhur. Kodi Hamming. Kodet ciklike. Kodimi dhe dekodimi i kodeve ciklike.

LITERATURA

1. Gallagher R. Teoria e informacionit dhe lidhje e besueshme., M., Sov. Radio, 1979.

2. Krichevsky E. Leksione mbi teorinë dhe informacionin, Novosibirsk, NSU, 1966.

3. Kolesnik V., Poltyrev G. Kursi në teorinë e informacionit, Nauka, 1982.

4. Fainstein A. Fundamentals of Information Theory, M., IL, 1960.

5. Peterson V., Weldon F. Kodet e korrigjimit të gabimeve, M., Mir, 1976.

6. Teoria e kodimit algjebrike Berlekamp, ​​M., Mir, 1971.

Puna u shtua në faqen e internetit: 2016-03-30

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5. Kodimi i informacionit

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5.1. Konceptet themelore

Teoremat e Shannon-it mbi kodimin e mesazheve u përmendën më lart. Është intuitivisht e qartë se kodimi është operacioni i konvertimit të informacionit në formën e kërkuar për përpunimin e mëvonshëm (transmetimi përmes një kanali komunikimi, ruajtja në kujtesën e një sistemi kompjuterik, përdorimi për vendimmarrje, etj.). Është gjithashtu e qartë se kur ndërtohet ndonjë sistem informacioni është e pamundur të bëhet pa kodim: çdo paraqitje e informacionit nënkupton përdorimin e një lloj kodi. Prandaj, në vijim do të analizojmë në detaje bazat teorike të kodimit të informacionit.

Le të A ndonjë alfabet. Elementet e alfabetit A quhen shkronja (ose simbole), dhe sekuencat e fundme të përbëra nga shkronja quhen fjalë në A . Besohet se në çdo alfabet ka një fjalë boshe që nuk përmban shkronja.

Fjala α 1 quhet fillimi (parashtesa) i një fjaleα , nëse fjala ekzistonα 2 i tillë që α = α 1 α 2 ; në këtë rast fjala α 1 quhet fillimi i duhur i një fjaleα nëse α 2 nuk është një fjalë boshe. Gjatësia e fjalës është numri i shkronjave në fjalë (një fjalë boshe ka gjatësi 0). Regjistroα 1 α 2 tregon një lidhje (lidhje) fjalëshα 1 dhe α 2. Fjala α 2 quhet mbaresa (prapashtesa) e një fjaleα , nëse fjala ekzistonα 1 i tillë që α = α 1 α 2 ; në këtë rast fjala α 2 quhet mbaresa e duhur e një fjaleα nëse α 1 nuk është një fjalë boshe. Një fjalë boshe sipas përkufizimit konsiderohet fillimi dhe mbarimi i çdo fjaleα .

Merrni parasysh alfabetin B = (0, 1, ..., D 1), ku D ≥ 2, dhe një grup arbitrar C . Shfaqja arbitrare e një grupi C me shumë fjalë në alfabet B quhet D Kodimi i grupit ary C (në D = 2 kodimi do të jetë binar). Hartëzimi i anasjelltë quhet dekodim. Le të japim shembuj të kodimeve.

1. Kodimi i bashkësisë së numrave natyrorë, në të cilin numri n = 0 përputhet me fjalën e (0) = 0, dhe numri n ≥ 1 fjalë binare

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

gjatësia më e vogël që plotëson kushtin

Është e qartë se b 1 = 1, 2 l (n) 1 ≤ n< 2 l (n ) dhe për këtë arsye

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

ku [ x ] dhe ] x [ tregon numrin më të madh të plotë që nuk tejkalon x , dhe numri i plotë më i vogël më i madh se x. Fjala e(n ) quhet shënimi binar i një numri n , dhe ky kodim është një paraqitje e numrave në sistemin e numrave binar. Ky kodim është një-për-një sepse kur n 1 ≠ n 2 fjalë e (n 1 ) dhe e (n 2 ) janë të ndryshme. Tabela 5.1 tregon paraqitjen e 16 numrave të parë natyrorë në sistemin e numrave binar.

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

" xml:lang="ru-RU" lang="ru-RU"> Kodimi" xml:lang="en-SHBA" lang="en-SHBA">e" xml:lang="ru-RU" lang="ru-RU">(" xml:lang="en-SHBA" lang="en-SHBA">n" xml:lang="ru-RU" lang="ru-RU">)

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

2. Kodimi i 2 të parëve k numrat natyrorë, për të cilët çdo numër n (0 ≤ n< 2 k ) përputhet me fjalën

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

ku hyrja është 0 k l (n) do të thotë një fjalë e përbërë nga k l (n) zero, e (n ) paraqitjen e numrit n në sistemin e numrave binar të diskutuar më sipër. Ky kodim është për 16 numrat e parë natyrorë ( k = 4) është dhënë në tabelën 5.2.

" xml:lang="ru-RU" lang="ru-RU">Tabela 5." xml:lang="en-SHBA" lang="sq-SHBA">2

" xml:lang="ru-RU" lang="ru-RU"> Kodimi" xml:lang="en-SHBA" lang="en-SHBA">e;vertical-align:sub" xml:lang="en-SHBA" lang="en-SHBA">k" xml:lang="ru-RU" lang="ru-RU">(" xml:lang="en-SHBA" lang="en-SHBA">n" xml:lang="ru-RU" lang="ru-RU">)

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

Le të A = (a i, i = 1, 2, ...) një alfabet i fundëm ose i numërueshëm, shkronjat e të cilit numërohen me numra natyrorë. Në këtë rast, kodimi i shkronjave të alfabetit A mund të specifikohet me sekuencë Fjalët D-ary V = (v i, i = 1, 2, ...), ku v i ka një imazh të një letre a i . Sekuenca të tilla fjalësh (nga grupi V ) quhen kode (të alfabetit A). Nëse jepet kodi V i alfabetit A , pastaj kodimi i fjalëve, në të cilin çdo fjalë a i 1 a i 2 … a ik përputhet me fjalën v i 1 v i 2 … v ik , quhet kodim shkronjë për shkronjë.

Kur kaloni nga kodimi një-në-një i shkronjave të alfabetit në kodimin shkronjë për shkronjë të fjalëve në alfabet, vetia e karakterit një-për-një mund të mos ruhet. Për shembull, kodimi e(n ) nuk ruan këtë veti, por kodimin e k (n ) e ruan atë. Prona një-për-një ruhet nga kode të ndashme. Kodi V = (v i, i = 1, 2, …) quhet i ndashëm nëse nga çdo barazi e formës

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

rrjedh se l = k dhe v i 1 = v j 1, v i 2 = v j 2, …, v ik = v jl . Kodet e ndashme quhen gjithashtu kode unike të dekodueshme.

Kodet e parashtesave i përkasin klasës së kodeve të ndashme. Kodi V = (v i, i = 1, 2, ...) quhet parashtesë nëse nuk ka fjalë vk nuk është fillimi (parashtesa) i asnjë fjale v l , l ≠ k . Nëse çdo fjalë e një kodi prefiks zëvendësohet nga fillimi i saj më i vogël, i cili nuk është fillimi i fjalëve të tjera të kodit, atëherë kodi që rezulton do të jetë gjithashtu një parashtesë. Ky operacion quhet shkurtimi i kodit të prefiksit.

Për kodin arbitrar V i përbërë nga fjalë të ndryshme, ju mund të ndërtoni një pemë kodi. Ky është një grafik i drejtuar që nuk përmban cikle, në të cilat kulmiβ 1 i lidhur në kryeβ 2 buzë drejtuar larg ngaβ 1 deri në β 2 , nese dhe vetem neseβ 2 = β 1 b, ku b  B = (0, 1, …, D 1), D ≥ 2. Për kodet e parashtesave (dhe vetëm për to), grupi i fjalëve kodike përkon me bashkësinë e kulmeve fundore (kulme nga të cilat nuk ka skaj) të pemës së kodit.

5.2. Teoremat bazë të kodimit

Vetitë e kodeve që janë të dobishme për zbatimin e tyre praktik përcaktohen nga teoremat bazë të kodimit.

Teorema 5.1. Pabarazia e Kraft.Për ekzistencën e një kodi unik të dekodueshëm (të ndashëm) që përmban N fjalët e kodit në grup (0, 1, D 1) me gjatësi n 1, n 2, ..., n N , është e nevojshme dhe e mjaftueshme që pabarazia të mbahet

Dëshmi. Le të imagjinojmë se kemi një pemë kodi për një kod prefiks. Rrënja e pemës së kodit formon nivelin 0, kulmet e lidhura me formën rrënjë niveli 1, etj. Numri i mundshëm i kulmeve për k -nivelin e shënojmë si Dk. Çdo kulm k niveli pjell saktësisht D n k kulme të nivelit të n-të.

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

Natyrisht, kodi i gjatësisë k ndalon saktësisht D n k kulme të mundshme fundore (kulme të nivelit të fundit). Pastaj të gjitha fjalët kodike të kodit të prefiksit ndalojnë kulmet fundore. Meqenëse numri i përgjithshëm i kulmeve fundore është Dn , atëherë pabarazia është e vërtetë

nga e cila rrjedh se

Kështu, pabarazia e Kraft-it vërtetohet.

Si rezultat i vërtetimit të Teoremës 5.1, arrihet në përfundimin se ka të paktën kode prefikse që janë kode unike të dekodueshme me gjatësi të fjalëve të koduara. n 1, n 2, …, n N , duke kënaqur pabarazinë e Kraft. Teorema e mëposhtme, e quajtur deklarata e McMillanit, e përgjithëson këtë derivacion për të gjitha kodet unike të dekodueshme.

Teorema 5.2. Pabarazia e McMillanit.Çdo kod i dekodueshëm në mënyrë unike plotëson pabarazinë e Kraft.

Dëshmi. Le ta ngremë shumën në një fuqi L:

. (5.1)

Le të A k numri i kombinimeve që përmbajnë L fjalë kodesh me gjatësi totale k . Atëherë shprehja (6.1) mund të paraqitet si

ku L max gjatësia maksimale e një mesazhi që përmban L fjalë kodike. Nëse kodi është i dekodueshëm në mënyrë unike, atëherë të gjitha sekuencat nga L fjalë kodike me gjatësi totale k janë të ndryshme. Meqenëse ka vetëm Dk sekuencat e mundshme, atëherë A k ≤ D k dhe më pas

Që nga L ky është numri i fjalëve kodike të pavarura që përdoren për të ndërtuar të gjitha sekuencat e mundshme të gjatësisë që nuk i kalon L max. Prandaj L ≤ L max Dhe. Dhe nga kjo rrjedh se

Meqenëse arsyetimi i mësipërm është i vlefshëm për çdo kod të dekodueshëm në mënyrë unike, dhe jo vetëm për kodet e parashtesave, pohimi i McMillan është i vërtetuar.

Teoremat e mëposhtme lidhen me entropinë e një burimi mesazhi dhe gjatësinë mesatare të një fjale kodi.

Teorema 5.3. Teorema e kodimit burimor I. Për çdo burim diskret pa memorie X me alfabet dhe entropi të fundme H(X) ekziston D -kodi i prefiksit ary në të cilin gjatësia mesatare e fjalës së koduar plotëson pabarazinë

. (5.2)

Dëshmi. Së pari, le të shpjegojmë se një burim diskret pa memorie përshkruhet nga një model që nuk merr parasysh lidhjet midis simboleve të mesazhit. Tani vërtetojmë anën e majtë të pabarazisë (6.2):

Për ta bërë këtë, ne përdorim përkufizimin e entropisë dhe pabarazisë Kraft:

Për të vërtetuar anën e djathtë të pabarazisë (6.2), ne rishkruajmë pabarazinë e Kraft në formën e mëposhtme:

Pastaj zgjedhim për çdo term numrin më të vogël të plotë n i , në të cilën

Meqenëse pabarazia e Kraft mbetet e njëjtë me këtë zgjedhje, ne mund të ndërtojmë kodin përkatës të prefiksit. Sepse n i është numri i plotë më i vogël, atëherë për n i 1 e vërtetë

Pastaj

Kështu, teorema e kodimit burimor I e provuar. Ai përcakton që gjatësia mesatare e një fjale kod nuk mund të jetë më e vogël se entropia e burimit të mesazhit. Vini re se vërtetimi i teoremës përdori të njëjtin shënim si kur merret parasysh pabarazia e Kraft.

Teorema 5.4. Teorema e kodimit burimor II. Për një bllok me gjatësi L ka D -kodi i prefiksit ary në të cilin gjatësia mesatare e fjalës së koduar për karakter plotëson pabarazinë

Ku.

Dëshmi. Këtu, blloqe personazhesh dhe H (X 1, X 2, …, X L ) është entropia e burimit të mesazhit për bllokun e L personazhet. Për të vërtetuar teoremën, mund të përdorni teoremën e kodimit burimor Unë:

Teorema e kodimit burimor II na lejon të deklarojmë se ekzistojnë metoda të tilla kodimi për një mesazh mjaft të gjatë që gjatësia mesatare e fjalës së kodit mund të bëhet në mënyrë arbitrare afër vlerës. Në të vërtetë, kur L  ∞, H L (X )  H , ku H entropia e burimit të mesazhit për karakter, pabarazia e mëposhtme është e vërtetë:

, (5.3)

Ku. Kjo mund të interpretohet edhe si vijon: për çdo numër të vogël arbitrarishtε , ekziston një metodë për kodimin e blloqeve që përmbajnë simbole në të cilat pabarazia (5.3) vlen për gjatësinë mesatare të fjalës së koduar për simbol.

Përveç kësaj, meqenëse gjatësia minimale e arritshme e një fjale kodi për simbol është vlera, atëherë kur D = 2 teprica e kodit mund të përcaktohet nga formula.

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5.3. Kodimi optimal

Problemi i ndërtimit të një kodi optimal është gjetja e numrave të plotë pozitivë n 1, n 2, …, n N , duke minimizuar gjatësinë mesatare të fjalës së kodit që i nënshtrohet pabarazisë së Kraft:

Gjatë ndërtimit të kodeve në rastin e një alfabeti A = (a i, i = 1, 2, …, N ) me një shpërndarje probabiliteti të njohur P = (p i, i = 1, 2, …, N ) pa humbje të përgjithshme mund të supozojmë se shkronjat e alfabetit A numërohen në rend zbritës të probabiliteteve të tyre, d.m.th. p 1 ≥ p 2 ≥ … ≥ p N . Përveç kësaj, ne do të shqyrtojmë vetëm kodet binare.

Ka dy metoda të njohura (Fano dhe Shannon) për ndërtimin e kodeve që janë afër optimales. Metoda e Fano është si më poshtë. Lista e shkronjave, të renditura në rend zbritës të gjasave, ndahet në dy pjesë të njëpasnjëshme në mënyrë që shumat e probabiliteteve të shkronjave të përfshira në to të ndryshojnë sa më pak nga njëra-tjetra. Shkronjave nga pjesa e parë u caktohet simboli 0 dhe shkronjave nga pjesa e dytë simboli 1. Më pas, bëni të njëjtën gjë me secilën nga pjesët që rezultojnë, nëse përmban, të paktën, dy shkronja. Procesi vazhdon derisa e gjithë lista të ndahet në pjesë që përmbajnë nga një shkronjë secila. Secilës shkronjë i caktohet një sekuencë simbolesh të caktuara për atë shkronjë si rezultat i këtij procesi. Është e lehtë të shihet se kodi që rezulton është një prefiks.

Metoda e Shannon është e zbatueshme vetëm kur të gjitha probabilitetet janë pozitive. Ai konsiston në faktin se letra a i , e cila ka një probabilitet p i > 0, sekuenca e n i = ] log (1/ p i )[ shifrat e para pas pikës thyesore të zbërthimit të një numri në një thyesë të pafundme (për a 1 supozojmë se q 1 = 0). Qe kur l > k (për faktin se p l ≤ p k ) n l ≥ n k dhe më pas kodi i marrë në këtë mënyrë është prefiks. Bazuar në kodin e prefiksit të marrë, ndërtohet një kod prefiks i cunguar, i cili është rezultat i kodimit duke përdorur metodën Shannon.

Le të ketë, për shembull, një grup shkronjash A = ( a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 ) me shpërndarje probabiliteti P = (0,2, 0,2, 0,19, 0,12, 0,11, 0,09, 0,09). Le të kodojmë shkronjat duke përdorur metodën Fano.

1. Le ta ndajmë listën në dy pjesë, në mënyrë që shumat e probabiliteteve të shkronjave të përfshira në to të ndryshojnë sa më pak nga njëra-tjetra:

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. Le t'ua caktojmë simbolin 0 shkronjave të pjesës së parë, dhe simbolin 1 shkronjave të pjesës së dytë:

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

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

3. Përsëriteni në mënyrë sekuenciale veprimet e specifikuara për secilën pjesë veç e veç. NË si rezultat marrim:

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).

Fjalët kodike të marra si rezultat i kodimit jepen për secilën shkronjë në të djathtë të vijës së pjerrët. Në këtë rast, rendi i indekseve të listave me një shkronjë rezultuese tregon sekuencën e ndarjes së listës origjinale të grupeve në pjesë.

Procesi i kodimit duke përdorur metodën Fano është paraqitur me lehtësi në formën e një tabele. Për shembullin në shqyrtim, është paraqitur në tabelën 5.3.

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

" xml:lang="ru-RU" lang="ru-RU"> Kodimi duke përdorur metodën Fano

" xml:lang="en-SHBA" lang="en-SHBA">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="en-SHBA" lang="en-SHBA">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="en-SHBA" lang="en-SHBA">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="en-SHBA" lang="en-SHBA">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="en-SHBA" lang="en-SHBA">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="en-SHBA" lang="en-SHBA">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="en-SHBA" lang="en-SHBA">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

Le të përcaktojmë gjatësinë mesatare të fjalës së kodit:

Tani le të bëjmë kodimin duke përdorur metodën e Shannon. Procesi i kodimit është dhënë në tabelën 5.4.

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

" xml:lang="ru-RU" lang="ru-RU"> Kodimi duke përdorur metodën Shannon

" xml:lang="en-SHBA" lang="en-SHBA">a;vertical-align:sub" xml:lang="en-SHBA" lang="en-SHBA">i	" xml:lang="en-SHBA" lang="en-SHBA">n;vertical-align:sub" xml:lang="en-SHBA" lang="en-SHBA">i	" xml:lang="en-SHBA" lang="en-SHBA">q;vertical-align:sub" xml:lang="en-SHBA" lang="en-SHBA">i	" xml:lang="ru-RU" lang="ru-RU">Kodi" xml:lang="en-SHBA" lang="en-SHBA">a;vertical-align:sub" xml:lang="en-SHBA" lang="en-SHBA">i	" xml:lang="ru-RU" lang="ru-RU">Kodi i shkurtuar" xml:lang="en-SHBA" lang="en-SHBA">a;vertical-align:sub" xml:lang="en-SHBA" lang="en-SHBA">i
" xml:lang="en-SHBA" lang="en-SHBA">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="en-SHBA" lang="sq-SHBA">]2.321…[ = 3	" xml:lang="en-SHBA" lang="sq-SHBA">0	000	000
a2	]2.321…[ = 3	0.2	001	001
a3	]2.395…[ = 3	0.4	011	01
a4	]3.058…[ = 4	0.59	1001	100
a5	]3.183…[ = 4	0.71	1011	101
a6	]3.472…[ = 4	0.82	1101	110
a7	]3.472…[ = 4	0.91	1110	111

Si në rastin e mëparshëm, gjejmë gjatësinë mesatare të fjalës së koduar:

.

Siç mund ta shihni, rezultatet e kodimit duke përdorur metodat Fano dhe Shannon për sa i përket minimizimit të gjatësisë mesatare të kodit praktikisht përkonin. Prandaj, këto metoda shpesh konsiderohen si një (në formulimin e Fano) dhe quhen metoda Shannon-Fano.

Në vitin 1952, David Huffman propozoi një metodë optimale të kodimit të prefiksit për burime diskrete, e cila, ndryshe nga metodat e Shannon dhe Fano, përdoret ende në praktikë. D. Huffman vërtetoi se gjatësia mesatare e një fjale kodi të marrë duke përdorur metodën e tij do të jetë minimale. Kodimi Huffman bëhet në tre hapa.

1. Renditja: shkronjat renditen në rend zbritës të probabiliteteve të tyre.

2. Reduktimi: dy shkronja me probabilitet më të ulët kombinohen në një me probabilitet total; lista e shkronjave rirenditet sipas hapit 1; procesi vazhdon derisa të gjitha shkronjat të kombinohen në një. Në këtë rast, është e mundur të arrihet barazimi i gjatësisë së fjalëve të kodit duke përdorur strategjinë e mëposhtme: nëse disa shkronja kanë të njëjtat probabilitete, atëherë kombinoni ato dy prej tyre që më parë kishin numrin më të vogël të kombinimeve (edhe pse kjo nuk do të ndikojë në gjatësia mesatare e kodit).

3. Kodimi: duke filluar nga kombinimi i fundit, simboli 0 i caktohet në mënyrë sekuenciale njërit komponent të shkronjës së përbërë, dhe simboli 1 në të dytën; procesi vazhdon derisa të jenë koduar të gjitha shkronjat origjinale.

Le të kryejmë kodimin duke përdorur metodën Huffman për grupin e konsideruar në shembujt e përdorimit të metodave Fano dhe Shannon.

1. Lista fillestare e shkronjaveA = { a1 , a2 , a3 , a4 , a5 , a6 , a7 ) është porositur tashmë, pasiP = {0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}.

2. Le të bashkojmë shkronjata6 Dhea7 në një letëra1 me probabilitet0.18 Dherirenditlistë:

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

3. Përsëriteni hapin 2 derisa një shkronjë të mbetet në listë:

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. Le të përshtasimbinarekodetsimbolet:

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.

Kështu, kodet binare të mëposhtme u caktohen shkronjave fillestare:a1 = 10, a2 = 11, a3 = 000, a4 = 010, a5 = 011, a6 = 0010, a7 = 0011, e cila jep një gjatësi mesatare të kodit që është më e vogël se në rastin e kodimit Fano dhe Shannon.

Le të përcaktojmë tepricën e kodeve të marra. Për ta bërë këtë, le të gjejmë entropinë e burimit të mesazhit:

.

Atëherë kodet kanë tepricën e mëposhtme:

Kodi Fano: ;

Kodi Shannon: ;

Kodi Huffman: .

Kështu, teprica e kodit Huffman është minimale.

Për të reduktuar tepricën, d.m.th. Për të zvogëluar gjatësinë mesatare të një fjale kodi me një simbol, mund të përdorni kodimin në bllok, arsyetimi për të cilin është dhënë në teoremën e kodimit burimorII. Në këtë rast, është e nevojshme të merren të gjitha grupet e mundshme të shkronjave gjatësia e dhënë, gjeni probabilitetet e grupeve si probabilitetet që shkronjat e grupit të shfaqen së bashku në të njëjtën kohë dhe kryeni kodimin, duke i trajtuar grupet si simbole të një alfabeti të ri.

FAQJA 43