UVOD Novi trendovi koji su se pojavili u matematici u dvadesetom stoljeću obično operiraju složenim konceptima i konceptima koje je teško popularizirati. U tom kontekstu, zasluga izvanrednog američkog matematičara i inženjera Claudea Shannona, koji je 1947.-1948., na temelju elementarnih razmatranja, otkrio novo područje matematika – teorija informacija. Poticaj za stvaranje nova znanost bili čisti tehnički problemi prijenos informacija telegrafskim i telefonskim žicama, međutim, zbog svoje opće prirode, teorija informacija danas se koristi u istraživanjima vezanim uz prijenos i pohranu bilo koje informacije u prirodi i tehnologiji. Krajem četrdesetih, u zoru razvoja teorije informacija, ideja o razvoju novih učinkovite načine informacije o kodiranju bile su u zraku. Istraživači su se bavili pitanjima entropije, informacijskog sadržaja i redundancije. Pitam se što ovi početni radovi u području kompresije informacija provedene su prije pojave modernog digitalnog računala. Danas se teorija informacija razvija paralelno s programiranjem, ali u to vrijeme ideja o razvoju algoritama koji koriste binarnu aritmetiku za kodiranje znakova bila je značajan korak naprijed. Algoritmi Shannon - Fano i Huffman bili su jedan od prvih algoritama za učinkovito kodiranje informacija. Ovaj rad razmatra Osnovni koncepti entropiju i informaciju, a također opisuje principe kodiranja poruka prema Shannon - Fano i Huffmanu, pokazuje njihovu važnu ulogu u prijenosu informacija preko komunikacijskih linija. No, komunikacijske linije za koje su razvijene ove metode kodiranja informacija već su u prošlosti. Na sreću, principi Shannon-Fano i Huffman su primijenjeni u moderni svijet: komprimirati informacije. Arhiveri PKZIP, ARJ, kao i dio poznatog JPEG standarda (kompresija grafičke informacije s gubicima) rade upravo na tim principima. Kodovi Shannon-Fano i Huffman predaju se na svim tehničkim sveučilištima u svijetu, a uz to su uključeni u program za napredni studij informatike u školi. Stoga je relevantno proučavanje metoda kodiranja Shannon - Fano i Huffman. Svrha ovog rada je proučavanje principa kodiranja informacija Shannon - Fano i Huffman i njihova primjena u rješavanju problema. Zadatak je proučiti entropiju i redundantnost određenih vrsta poruka za naknadnu primjenu Shannon-Fano i Huffmanovih principa na njih. 1. Informacije i kodiranje. Shannon kodovi - Fano i Huffman. 1.1 Informacije i kodiranje. Riječ "informacija" svima je poznata u našem vremenu. Dolazi od latinskog “informatio”, što znači – pojašnjenje, poruka, svijest. No, u stalnu upotrebu ušao je ne tako davno, sredinom dvadesetog stoljeća, na prijedlog Claudea Shanona. Uveo je ovaj pojam u užem tehničkom smislu u odnosu na teoriju komunikacije ili prijenosa kodova, koja je nazvana "Teorija informacija". Ovdje nisu važne informacije, već samo one koje u potpunosti otklanjaju ili smanjuju postojeću nesigurnost. Filozofsku, a time i širu definiciju ovog pojma daje jedan od utemeljitelja računalne znanosti, poznati američki znanstvenik Norbert Wiener: „Informacija je oznaka sadržaja koji crpimo iz vanjskog svijeta u procesu naše prilagodbe na i dovođenje naših razmišljanja u skladu s tim." Naravno, ovo su daleko od jedinstvenih definicija informacija. Trenutno ovaj pojam ima dublje i višestruko značenje. Ostajući uglavnom intuitivan, prima različite semantičke sadržaje u različitim granama ljudske djelatnosti: * u svakodnevnom aspektu informacije se shvaćaju kao informacije o okolnom svijetu i procesima koji se u njemu događaju, a koje percipira osoba ili posebni uređaji; * u tehnologiji se informacija shvaća kao poruke koje se prenose u obliku znakova ili signala; * u teoriji informacija (prema K. Shannon) nisu važne informacije, već samo one koje potpuno otklanjaju ili smanjuju postojeću nesigurnost; * u semantičkoj teoriji (značenje poruke) - to je informacija koja ima novinu, i tako dalje... Ovakva raznolikost pristupa nije slučajna, već posljedica činjenice da postoji potreba za svjesnom organizacijom procesa. kretanja i obrade onoga što ima zajednički naziv – pojavila se informacija. Za daljnje razmatranje potreban nam je koncept informacije, koji podrazumijeva prijenos informacijskih poruka preko komunikacijskih linija. Smatrati opća shema prijenos poruka; radi određenosti, govorit ćemo, na primjer, o telegrafiji. Na jednom kraju retka pošiljatelj šalje neku poruku, napisanu bilo kojom od nama poznatih abeceda ili brojeva, ili u kombinaciji slova i brojeva. Za prijenos ove vrste poruka koriste se nizovi jednosmjernih signala, čije neke karakteristike telegrafist može mijenjati po svom nahođenju, koje opaža drugi telegrafista na prijemnom kraju linije. Najjednostavniji prepoznatljivi signali, koji se široko koriste u praksi, je odašiljanje struje (tj. uključivanje na neko potpuno Određeno vrijeme) i bez slanja - pauza (isključivanje struje za isto vrijeme); samo uz pomoć ova dva signala već možete prenijeti bilo koju poruku, ako pristanete zamijeniti svako slovo ili broj određenu kombinaciju slanja struje i pauze. U komunikacijskom inženjerstvu pravilo koje svaku odaslanu poruku povezuje s određenom kombinacijom signala obično se naziva kodom (u slučaju telegrafije, telegrafskim kodom), a sama operacija prevođenja poruke u niz različiti signali- kodiranje poruke. "Šifra" će se shvaćati kao takav skup od n kodnih oznaka, koji se podudaraju s n slova abecede, za koji je ispunjen sljedeći uvjet: nijedna kodna oznaka jednog slova ne podudara se s početkom bilo koje druge duže kodne oznake, t.j. kodovi moraju biti jedinstveno dekodirani. Međutim, kodovi koji koriste samo dva različita čipa (npr. slanje struje i pauza) nazivaju se binarni kodovi. U nekim telegrafskim aparatima, osim jednostavno uključivanje a isključivanjem struje možete i obrnuti njezin smjer. U tom slučaju postaje moguće, umjesto slanja struje i pauza, koristiti slanje struje u dva različita smjera kao glavne signale ili koristiti tri različita elementarna signala istog trajanja odjednom - slanje struje u jednom smjeru, slanje struje u drugom smjeru i pauza (ova metoda kodiranja naziva se ternarnim kodom). Mogući su i složeniji telegrafski uređaji, kod kojih se slanja struje razlikuju ne samo po smjeru, nego i po jakosti struje; tako dobivamo priliku da broj različitih elementarnih signala bude još veći. Povećanje broja različitih elementarnih signala omogućuje vam da učinite kod komprimiranijim. Međutim, to također komplicira i povećava cijenu prijenosnog sustava, tako da se u struci još uvijek preferiraju niski kodovi čipa. Neka postoji poruka napisana pomoću neke "abecede" koja sadrži n "slova". Potrebno je "kodirati" ovu poruku, t.j. označavaju pravilo koje povezuje svaku takvu poruku s određenim nizom od m različitih "čipova" koji čine "abecedu" prijenosa. Smatrat ćemo da je kodiranje isplativije, što je manje elementarnih signala potrebno potrošiti na prijenos poruke. Ako pretpostavimo da svaki od elementarnih signala traje isto vrijeme, tada će najpovoljniji kod omogućiti da se najmanje vremena potroši na prijenos poruke. Glavno vlasništvo slučajni događaji je nedostatak potpunog povjerenja u njihovu pojavu, što stvara određenu nesigurnost pri izvođenju eksperimenata vezanih za te događaje. Međutim, sasvim je jasno da će stupanj te nesigurnosti u različitim slučajevima biti potpuno različit. Za praksu je važno biti sposoban brojčano procijeniti stupanj nesigurnosti širokog spektra eksperimenata kako bi se mogli usporediti s ove strane. Razmotrite dva nezavisna iskustva, kao i kompleksno iskustvo koje se sastoji od istovremeno izvršenje eksperimenti i. Neka iskustvo ima k jednako vjerojatnih ishoda, a iskustvo ima l jednako vjerojatnih ishoda. Očito je neizvjesnost iskustva veća od nesigurnosti iskustva, budući da se neizvjesnost ishoda iskustva pridodaje neizvjesnosti. Prirodno je pretpostaviti da je stupanj nesigurnosti iskustva jednak zbroju nesigurnosti koje karakteriziraju pokuse, tj.:. Samo jedna funkcija zadovoljava uvjete, kada -:. Razmotrimo eksperiment A koji se sastoji od iskustava i ima vjerojatnosti. Tada će ukupna nesigurnost pokusa A biti jednaka. Ovaj posljednji broj nazvat ćemo entropijom pokusa i označiti ga s. Ako je broj slova u "abecedi" jednak n, a broj korištenih elementarnih signala jednak je m, tada za bilo koju metodu kodiranja prosječan broj elementarnih signala po jednom slovu abecede ne može biti manji od; međutim, uvijek se može proizvoljno približiti ovom omjeru, ako se samo pojedinačne oznake koda odmah usporede s dovoljno dugim "blokovima" koji se sastoje od veliki broj slova. Razmotrit ćemo samo ovdje najjednostavniji slučaj poruke napisane korištenjem nekih n "slova", čija je učestalost pojavljivanja bilo gdje u poruci u potpunosti karakterizirana vjerojatnostima p1, p2, ... ..., pn, gdje je, naravno, p1 + p2 + ... + pn = 1, pri čemu je vjerojatnost pi manifestacije i-tog Pretpostavlja se da su slova na bilo kojem mjestu poruke ista, bez obzira koja su slova bila na svim prethodnim mjestima, t.j. uzastopna slova poruke neovisna su jedno o drugom. Zapravo, u stvarnim porukama to često nije slučaj; posebno, u ruskom jeziku, vjerojatnost pojave određenog slova značajno ovisi o prethodnom slovu. No, striktno uvažavanje međusobne ovisnosti slova uvelike bi otežalo sva daljnja razmatranja, ali ni na koji način neće promijeniti buduće rezultate. Za sada ćemo gledati binarne kodove; generalizacija rezultata dobivenih u ovom slučaju za kodove koji koriste proizvoljan broj t elementarni signali je, kao i uvijek, krajnje jednostavan. Počnimo s najjednostavnijim slučajem kodova koji svakom "slovu" poruke pridružuju zasebnu oznaku koda - niz brojeva 0 i 1. Svaki binarni kod za n-slovnu abecedu može se povezati s nekom metodom pogađanja nekog skrivenog broja x, koji ne prelazi n, korištenjem pitanja na koja se odgovara samo "da" (1) ili "ne" (0), što nas vodi na binarni kod. Za dane vjerojatnosti p1, p2, ..., pn pojedinačnih slova, prijenos višeslovne poruke bit će najekonomičniji kod za koji je, s ovim vjerojatnostima n vrijednosti x, prosječna vrijednost broja postavljenih pitanja (binarni predznaci: 0 i 1 ili elementarni signali) ispada najmanji. Prije svega, prosječan broj binarnih elementarnih signala u kodiranoj poruci po jednom slovu izvorne poruke ne može biti manji od H, gdje je H = - p1 log p1 - p2 log p2 - ... - pn log pn entropija iskustva koje se sastoji u prepoznavanju jednog slova teksta (ili, ukratko, samo entropije jednog slova). Iz ovoga odmah proizlazi da je za bilo koju metodu kodiranja, za pisanje dugačke poruke od M slova, potreban najmanje MH binarnih znakova, koji ni na koji način ne smije prelaziti jedan bit. Ako vjerojatnosti p1, p2, ... ..., pn nisu sve jednake jedna drugoj, tada je H< log n; поэтому естественно думать, что учет статистических закономерностей сообщения может позволить построить код более экономичный, чем наилучший равномерный код, требующий не менее М log n двоичных знаков для записи текста из М букв. 1.2 Коды Шеннона - Фано. Для удобства расположим все имеющиеся п букв в один столбик в порядке убывания вероятностей. Затем все эти буквы следует разбить на две группы - верхнюю и нижнюю - так, чтобы суммарная вероятность первой группы была наиболее близка к суммарной вероятности второй группы. Для букв первой группы в качестве первой цифры кодового обозначения используется цифра 1, а для букв второй группы - цифра 0. Далее, каждую из двух групп подобным образом снова надо разделить на две части и в качестве второй цифры кодового обозначения мы будем использовать цифру 1 или 0 в зависимости от того, принадлежит ли наша группа к первой или ко второй из этих подгрупп. Затем, каждая из содержащих более одной буквы групп снова делится на две части возможно более близкой суммарной вероятности и т.д.; процесс повторяется до тех пор, пока мы не придем к группам, каждая из которых содержит по одной единственной букве. Такой метод кодирования сообщений был впервые предложен в 1948 - 1949 гг. независимо друг от друга Р. Фано и К. Шенноном; поэтому соответствующий код обычно называется кодом Шеннона - Фано. Так, например, если наш алфавит содержит всего шесть букв, вероятность которых (в порядке убывания) равны 0,4, 0,2, 0,2, 0,1, 0,05 и 0,05, то на первом этапе деления букв на группы мы отщепим лишь одну первую букву (1-я группа), оставив во второй группе все остальные. Далее, вторая буква составит 1-ю подгруппу 2-й группы; 2-я же подгруппа той же группы, состоящая из оставшихся четырех букв, будет и далее последовательно делиться на части так, что каждый раз 1-я часть будет состоять лишь из одной буквы. № буквывероят-ностьразбиение на подгруппы (римские цифры обозначают номера групп и подгрупп)кодовое обозначение10,4} I 120,2} II} I 0130,2} II} I 00140,1} II} I 000150,05} II} I0000160,05} II00000 Табл.1 Аналогично предыдущему примеру разобран случай "алфавита", включающего 18 букв, имеющих следующие вероятности: 0,3; 0,2; 0,1 (2 буквы); 0,05; 0,03 (5 букв); 0,02(2 буквы); 0,01 (6 букв). (Табл. 2) № буквывероят-ностьразбиение на подгруппы кодовое обозначение10,3} I} I 1120,2} II 1030,1} II} I} I 01140,1} II} I 010150,05} II 010060,03} II} I} I} I 0011170,03} II 0011080,03} II} I 0010190,03} II 00100100,03} II} I} I 00011110,02} II} I 000101120,02} II 000100130,01} II} I} I 000011140,01} II} I0000101150,01} II0000100160,01} II} I 000001170,01} II} I0000001180,01} II0000000 Табл.2 Основной принцип, положенный в основу кодирования по методу Шеннона - Фано, заключается в том, что при выборе каждой цифры кодового обозначения мы стараемся, чтобы содержащееся в ней количество информации было наибольшим, т. е. чтобы независимо от значений всех предыдущих цифр эта цифра принимала оба возможных для нее значения 0 и 1 по возможности с одинаковой вероятностью. Разумеется, количество цифр в različite oznake u ovom slučaju ispada da je drugačiji (posebno u drugom od analiziranih primjera varira od dva do sedam), tj. kod Shannon - Fano je neuniforman. Međutim, nije teško razumjeti da ovdje nijedna kodna oznaka ne može biti početak druge, duže oznake; stoga se kodirana poruka uvijek može nedvosmisleno dekodirati. Kao rezultat toga, prosječna vrijednost duljine takve oznake još uvijek se ispostavi da je tek nešto veća od minimalne vrijednosti H dopuštene razmatranjem očuvanja količine informacija tijekom kodiranja. Dakle, za primjer abecede od 6 slova koja je gore razmatrana, najbolji uniformni kod sastoji se od troznamenkastih oznaka koda (jer 22< 6 < 23), и поэтому в нем на каждую букву исходного сообщения приходится ровно 3 элементарных сигнала; при использовании же кода Шеннона - Фано среднее число элементарных сигналов, приходящихся на одну букву сообщения, равно Это значение заметно меньше, чем 3, и не очень далеко от энтропии Аналогично этому для рассмотрения примера 18-буквенного алфавита наилучший равномерный код состоит из пятизначных кодовых обозначений (так как 24 < 18 < 25); в случае же кода Шеннона - Фано имеются буквы, кодируемые даже семью двоичными сигналами, но зато среднее число элементарных сигналов, приходящихся на одну букву, здесь равно Последнее значение заметно меньше, чем 5, - и уже не намного отличается от величины Особенно выгодно бывает кодировать по методу Шеннона - Фано не отдельные буквы, а сразу целые блоки из нескольких букв. Правда, при этом все равно невозможно превзойти предельное значение Н двоичных знаков на одну букву сообщения. Рассмотрим, например, случай, когда имеются лишь две различные буквы А и Б, имеющие вероятности р(А) = 0,7 и р(Б) = 0,3; тогда H = - 0,7 log0,7 - 0,3 log0,3 = 0,881... Применение метода Шеннона - Фано к исходному двухбуквенному алфавиту здесь оказывается бесцельным: оно приводит нас лишь к простейшему равномерному коду буква вероятность кодовое обозначение А 0,7 1 Б 0,3 0 требующему для передачи каждой буквы одного двоичного знака - на 12% больше минимального достижимого значения 0,881 дв.зн./букву. Применяя же метод Шеннона - Фано к кодированию всевозможных двухбуквенных комбинаций (вероятность которых определяется правилом умножения вероятностей для независимых событий), мы придем к следующему коду: комбина- ция букв вероятность кодовое обозначение АА 0,49 1 АБ 0,21 01 БА 0,21 001 ББ 0,09 000 Среднее значение длины кодового обозначения здесь равно, так что на одну букву алфавита здесь приходится в среднем двоичных знаков - лишь на 3% больше значения 0,881 дв.зн./букву. Еще лучше результаты мы получим, применив метод Шеннона - Фано к кодированию трехбуквенной комбинации; при этом мы придем к следующему коду: комбина- ция букв вероятность кодовое обозначение ААА 0,343 11 ААБ 0,147 10 АБА 0,147 011 БАА 0,147 010 АББ 0,063 0010 БАБ 0,063 0011 ББА 0,063 0001 БББ 0,027 0000 Среднее значение длины кодового обозначения здесь равно 2,686, т.е. на одну букву текста приходится в среднем 0,895 двоичных знаков, что всего на 1,5% больше значения дв.зн./букву. В случае еще большей разницы в вероятностях букв А и Б приближение к минимально возможному значению Н дв.зн./букву может несколько менее быстрым, но оно проявляется не менее наглядно. Так, при р(А) = 0,89 и р(Б) = 0,11 это значение равно - 0,89 log0,89 - 0,11 log0,11 ≈ 0,5 дв.зн./букву, а равномерный код (равносильный применению кода Шеннона - Фано к совокупности двух имеющихся букв) требует затраты одного двоичного знака на каждую букву - в два раза больше. Нетрудно проверить, что применение кода Шеннона - Фано к всевозможным двухбуквенным комбинациям здесь приводит к коду, в котором на каждую букву приходится в среднем 0,66 двоичных знаков, применение к трехбуквенным комбинациям - 0,55, а к четырехбуквенным блокам - в среднем 0,52 двоичных знаков - всего на 4% больше минимального значения 0,50 дв.зн./букву. 1.3 Коды Хафмана. Близок к коду Шеннона - Фано, но еще выгоднее, чем последний, так называемый код Хафмана. Построение этого кода опирается на простое преобразование используемого алфавита, называемое сжатием алфавита. Пусть мы имеем алфавит А, содержащий буквы, вероятности появления которых в сообщении соответственно равны; при этом мы считаем буквы расположенными в порядке убывания их вероятностей (или частот), т.е. полагаем, что. Условимся теперь не различать между собой две наименее вероятные буквы нашего алфавита, т.е. будем считать, что ап-1 и ап - это одна и та же буква b нового алфавита А1, содержащего теперь уже буквы и b (т.е. ап-1 или ап), вероятности появления которых в сообщении соответственно равны и рп-1 + рп. Алфавит А1 и называется полученным из алфавита А с помощью сжатия (или однократного сжатия). Расположим буквы нового алфавита А1 в порядке убывания их вероятностей и подвергнем сжатию алфавит А1; при этом мы придем к алфавиту А2, который получается из первоначального алфавита А с помощью двукратного сжатия (а из алфавита А1 - с помощью простого или однократного сжатия). Ясно, что алфавит А2 будет содержать уже всего п - 2 буквы. Продолжая эту процедуру, мы будем приходить ко все более коротким алфавитам; после (п - 2)-кратного сжатия мы придем к алфавиту Ап-2, содержащему уже всего две буквы. Вот, например, как преобразуется с помощью последовательных сжатий рассмотренный выше алфавит, содержащий 6 букв, вероятности которых равны 0,4, 0,2, 0,2, 0,1, 0,05 и 0,05: № буквыВероятностиисходный алфавит Асжатые алфавитыА1А2А3А410,40,40,40,40,620,20,20,20,40,430,20,20,20,240,10,10,250,050,160,05 Табл.3 Условимся теперь приписывать двум буквам последнего алфавита Ап-2 кодовые обозначения 1 и 0. Далее, если кодовые обозначения уже приписаны всем буквам алфавита Aj, то буквам "предыдущего" алфавита Aj-1 (где, разумеется, А1-1 = А0 - это исходный алфавит А), сохранившимся и в алфавите Aj, мы пишем те же кодовые обозначения, которые они имели в алфавите Aj-1; двум же буквам a" и a"" алфавита Aj, "слившимся" в одну букву b алфавита Aj-1, мы припишем обозначения, получившиеся из кодового обозначения буквы b добавлением цифр 1 и 0 в конце. (Табл.4) № буквыВероятностиисходный алфавит Асжатые алфавитыА1А2А3А410,4 00,4 00,4 0 0,4 00,6 120,2 100,2 100,2 100,4 11 0,4 030,2 1110,2 1110,2 1110,2 10 40,1 11010,1 11010,2 110 50,05 110010,1 1100 60,05 11000 Табл. 4 Легко видеть, что из самого построения получаемого таким образом кода Хафмана вытекает, что он удовлетворяет opće stanje: nema kodne oznake ovdje je početak druge, duže kodne oznake. Također imajte na umu da kodiranje određene abecede Huffman metodom (kao i Shannon - Fano metodom) nije jednoznačan postupak. Tako, na primjer, u bilo kojoj fazi izrade koda, možete, naravno, zamijeniti broj 1 brojem 0 i obrnuto; s ovim dobivamo dva različite šifre(vrlo neznatno različite jedna od druge). No osim toga, u nekim je slučajevima moguće konstruirati nekoliko značajno različitih Huffmanovih kodova; Tako, na primjer, u gore rastavljenom primjeru možete izraditi kod u skladu sa sljedećom tablicom: Broj slova Vjerojatnosti izvorna abeceda Komprimirane abecede A1A2A3A410.4 110.4 110.4 11 0.4 00.6 120.2 010.2 010.2 01 02 01 02 01 02 02 01 02 01 01 1000,1 1010,2 00 50,05 10110,1 100 60,05 1010 Tablica 5 novi kod je također Huffmanova šifra, ali se ispostavilo da su duljine postojećih oznaka koda potpuno različite. Imajte na umu da je prosječni broj elementarnih signala po slovu potpuno isti za oba konstruirana Huffmanova koda: u prvom slučaju jednak je, au drugom jednak. Može se pokazati da je Huffmanov kod uvijek najekonomičniji od svih mogućih u smislu da ni za jednu drugu metodu kodiranja slova određene abecede prosječan broj elementarnih signala po slovu ne može biti manji od onog dobivenog kodiranjem pomoću Huffmanova metoda (iz ovoga, naravno, odmah slijedi da za bilo koja dva Huffmanova koda prosječna duljina oznake koda mora biti potpuno ista - uostalom, oba su najekonomičnija). Obrazloženje dano u paragrafima 1.2 i 1.3 u potpunosti se provodi pri rješavanju problema (primjer takvog problema dat je u Dodatku A). 2. Entropija pojedinih vrsta poruka. 2.1 Glavni teorem o kodiranju. Stupanj bliskosti prosječnog broja binarnih znakova po jednom slovu poruke vrijednosti H postignute u gore razmatranim primjerima može se dalje proizvoljno povećati prijelazom na kodiranje sve dužih blokova. To proizlazi iz sljedeće opće tvrdnje, koju ćemo dalje nazvati glavnim teoremom kodiranja, točnije, glavnim teoremom kodiranja u odsutnosti smetnji: kod kodiranja poruke podijeljene u blokove N slova, odabirom N dovoljno velikog, možemo postići da prosječni broj binarnih čipova po slovu izvorne poruke bude proizvoljno blizu H. Kodiranje dugih blokova odjednom ima značajne prednosti u prisutnosti smetnji koje ometaju rad komunikacijske linije. S obzirom na veliku važnost ovdje formuliranog glavnog teorema kodiranja, u nastavku donosimo njegov dokaz koji se temelji na korištenju Shannon - Fano metode kodiranja. Najprije pretpostavimo da metodom Shannon - Fano, koja je osnova sekvencijalne podjele skupa kodiranih slova (po kojima se mogu razumjeti i cijeli "blokovi") na sve manje grupe, svaki put uspijemo osigurati da vjerojatnosti dviju rezultirajućih skupina su točno jednake jedna drugoj... U ovom slučaju, nakon prvog dijeljenja dolazimo do skupina s ukupnom vjerojatnošću 1/2, nakon drugog - do skupina s ukupnom vjerojatnošću od 1/4, ..., nakon l. dijeljenja - do grupa s ukupna vjerojatnost od 1 / 2l. U ovom slučaju, l-znamenkasta oznaka koda imat će ona slova za koja se ispostavi da su dodijeljena grupi od jednog elementa točno nakon l podjela; drugim riječima, ako je ovaj uvjet zadovoljen, duljina li oznake koda bit će povezana s vjerojatnošću pi odgovarajućeg slova formulom B opći slučaj količina - log pi, gdje je pi - vjerojatnost i-tog slovo abecede, neće biti cijeli broj, dakle duljina li koda i-ta notacija slova ne mogu biti jednaka log pi. Budući da kod kodiranja metodom Shannon - Fano, svoju abecedu sekvencijalno dijelimo u grupe što je moguće bliže ukupnoj vjerojatnosti, duljina oznake koda i-tog slova s takvim kodiranjem bit će bliska - log pi. S tim u vezi, s li označavamo prvi cijeli broj ne manji od - log pi: (A) Posljednja nejednakost se može prepisati na sljedeći način: ili (B) Ovdje napominjemo da u slučaju bilo kojeg n brojeva koji zadovoljavaju nejednakost, ( 1) postoji binarni kod za koji su ti brojevi duljine kodnih oznaka povezanih s n slova određene abecede. Prosječno l binarni signali po jednom slovu izvorne poruke (ili, prosječna duljina oznake koda) zadana je zbrojem. Pomnožimo sada nejednakost (A) koja daje vrijednost li sa pi, zbrojimo sve tako dobivene nejednadžbe koje odgovaraju vrijednostima i = 1, 2, ..., n i uzmemo u obzir da je, gdje je entropija eksperimenta koji se sastoji u određivanju jednog slova poruke, i da je p1 + p2 + ... + pn = 1. Kao rezultat, dobivamo to. Primijenimo ovu nejednakost na slučaj kada se gore opisana metoda koristi za kodiranje svih mogućih N-slovnih blokova (koji se mogu smatrati slovima nove abecede). Na temelju pretpostavke o neovisnosti uzastopnih slova poruke, entropija eksperimenta, koji se sastoji u određivanju svih slova bloka, je Posljedično, prosječna duljina lN kodne oznake bloka N-slova zadovoljava nejednakosti Ali kada se kodiraju N-slovni blokovi odjednom, prosječni broj l binarnih elementarnih signala po jednom slovu poruke bit će jednak prosječnoj dužini lN kodne oznake jednog bloka podijeljenom s brojem N slova u bloku :. Stoga se kod takvog kodiranja, odnosno ovdje prosječni broj elementarnih signala po slovu razlikuje od minimalne vrijednosti H za najviše. Uz pretpostavku, odmah dolazimo do glavnog teorema o kodiranju. Gornji dokaz može se primijeniti i na općenitiji slučaj kada su uzastopna slova teksta međusobno ovisna. U ovom slučaju morate samo napisati nejednakost za vrijednost lN u obliku, gdje je entropija bloka N-slova, koja će u slučaju ovisnosti slova poruke jedno od drugog uvijek biti manja od NH (za i). Iz ovoga proizlazi da se, dakle, u ovom općenitijem slučaju (uz neograničeno povećanje duljine blokova) prosječan broj elementarnih signala utrošenih na prijenos jednog slova neograničeno približava vrijednosti u kojoj postoji "specifična entropija" po jednom slovu višeslovnog teksta. Postojanje granice proizlazi iz nejednakosti koje pokazuju da je niz monotono nerastući niz pozitivnih (velikih 0) brojeva. Sve prethodne izjave lako se prenose na slučaj t-arnih kodova koji koriste t elementarne signale. Dakle, da bi se konstruirali m-arni Shannon - Fano kodovi, potrebno je samo podijeliti grupe simbola ne na dva, već na m dijelova što je bliže moguće, a za konstruiranje t-arnog Huffmanovog koda potrebno je koristiti operaciju sažimanje abecede, u kojoj svaki put nisu spojena dva, i m slova izvorne abecede koja imaju najmanje vjerojatnosti. S obzirom na važnost Huffmanovih kodova, zadržimo se na posljednjem pitanju malo detaljnije. Kompresija abecede, u kojoj je m slova zamijenjeno jednim, dovodi do smanjenja broja slova za m - 1; budući da je za konstruiranje t-arnog koda, očito, potrebno da nas slijed "kontrakcija" u konačnici dovede do abecede od m slova (povezanih s m signala koda), potrebno je da broj n slova koda početna abeceda se može predstaviti u obliku n = m + k (m - 1), gdje je k cijeli broj. To se, međutim, uvijek može postići dodavanjem, ako je potrebno, izvornoj abecedi još nekoliko "lažnih slova", čije se vjerojatnosti izračunavaju jednaka nuli... Nakon toga, konstrukcija t-arnog Huffmanovog koda i dokaz njegove optimalnosti (među svim t-arnim kodovima) se provode na potpuno isti način kao u slučaju binarni kod... Tako, na primjer, u slučaju već razmatrane abecede od 6 slova, koja imaju vjerojatnosti od 0,4, 0,2, 0,2, 0,1, 0,05 i 0,05 za konstruiranje ternarnog Huffmanovog koda, našoj abecedi moramo dodati još jedno slovo nulte vjerojatnosti, a zatim postupite na sljedeći način: Broj slovnih i kodnih oznaka vjerojatnosti izvorne abecede komprimirane abecede 10,4 00,4 00,4 020,2 20,2 20,4 130,2 100,2 100,2 240, 1 110,1 01 01 01 0 1 1 110 240, 1 110,1 01 01 01 05 01 05 01 01 01 05 prijeći na slučaj t-arnih kodova i na gornji dokaz glavnog teorema kodiranja. Konkretno, odgovarajuća modifikacija temelji se na činjenici da su bilo koji n brojeva l1, l2, ..., ln koji zadovoljavaju nejednakost duljine kodnih oznaka nekog t-arnog koda za n-slovnu abecedu. Ponavljajući razmišljanje za slučaj m = 2, lako je dobiti sljedeći rezultat (koji se naziva glavni teorem kodiranja za t-arne kodove): za bilo koju metodu kodiranja koja koristi t-arni kod, prosječan broj čipova po slovu poruke nikada ne može biti manji od omjera (gdje je H entropija jednog slova poruke); međutim, uvijek se može proizvoljno približiti ovoj vrijednosti ako se istovremeno kodiraju dovoljno dugi "blokovi" od N slova. Dakle, jasno je da ako se L elementarnih signala (koji uzimaju m različitih vrijednosti) može prenijeti preko komunikacijske linije u jedinici vremena, tada brzina prijenosa poruke na takvoj liniji ne može biti veća od slova/jedinica. vrijeme; međutim, prijenos brzinom proizvoljno blizu v (ali manjoj od v!) je već moguć. Vrijednost u brojniku izraza za v ovisi samo o samoj komunikacijskoj liniji (dok nazivnik H karakterizira odaslanu poruku). Ova vrijednost označava najveći broj jedinice informacija koje se mogu prenijeti duž naše linije u jedinici vremena (jer jedan elementarni signal, kao što znamo, može sadržavati najviše log m jedinica informacije); naziva se širina pojasa komunikacijske linije. Koncept širina pojasa igra važna uloga u teoriji komunikacije. 2.2 Entropija i informacije o određenim vrstama poruka. 2.2.1 Pismeni govor Za prijenos poruke M-slovom koja dopušta m različitih elementarnih signala, potrebno je potrošiti ne manje od signala, gdje je n broj slova "abecede. Budući da ruska "telegrafska" abeceda sadrži 32 slova (slova e i e se ne razlikuju, b i b, već se ubrajaju među slova i "nulto slovo" je prazan prostor između riječi), tada se elementarni signali moraju potrošiti na prijenos poruke M-slova. Ruski tekst, pod uvjetom da se sva slova smatraju jednako vjerojatnim. Da biste dobili tekst u kojem svako slovo sadrži 5 bitova informacije, trebate napisati 32 slova na zasebnim ulaznicama, staviti sve te karte u urnu i zatim ih izvaditi jednu po jedan, svaki put zapisujući izduženo slovo, vraćajući kartu natrag u kantu za smeće i ponovno miješajući njezin sadržaj. Nakon takvog eksperimenta dolazimo do "fraze" poput sljedeće: RYS Naravno, ovaj tekst ima vrlo malo zajedničkog s ruskim jezikom! Za točniji izračun informacija sadržanih u jednom slovu ruskog teksta, morate znati vjerojatnosti pojave različitih slova. Približne vrijednosti učestalosti pojedinih slova ruskog jezika prikupljene su u sljedećoj tablici: relativno slovo. frekvencija - 0,175o 0,090e, d 0,072a 0,062 i 0,062t 0,053n 0,053s 0,045 slova relativno frekvencija 0,040v 0,038l 0,035k 0,028m 0,026d 0,025p 0,023u 0,021 slovo relativno frekvencija 0,018y 0,016z 0,016b, b 0,014b 0,014g 0,013h 0,012y 0,010 relativna slova frekvencije 0,009zh 0,007u 0,006sh 0,006ts 0,004sh 0,003e 0,003f 0,002 Iz usporedbe ove vrijednosti s vrijednošću N0 = log 32 = 5 bita, može se vidjeti da neujednačen izgled različitih slova abecede dovodi do smanjenja informacija sadržanih u jednom slovu ruskog teksta za oko 0,65 bita . Smanjenje broja potrebnih elementarnih signala može se prikazati kodiranjem pojedinih slova ruske abecede pomoću Shannon-Fano metode: abecedni kod. oznaka slova kod oznaka slova kod obozn.111k01000h0000100a1010l01001ts00000010b000101m00111ch000011v01010n0111sh00000011g000100o110sch00000001d001101p001100y001000e, o1011r01011,00111t1000yu00000010i1001Tablica 8. Prosječan broj žetona u ovom načinu kodiranja je isti, onda će biti vrlo blizu vrijednosti u određivanju entropije eksperiment bio je odrediti jednog slova ruski tekst, smatra da sva slova neovisna . To znači da za sastavljanje "teksta" u kojem svako slovo sadrži ponešto informacija, moramo pribjeći pomoći urne, u kojoj je pažljivo izmiješanih 1000 papirića, od kojih 175 nema ništa napisano. , 90 - napisano je slovo o, 72 - slovo e, ..., konačno, na 2 komada papira - slovo f (vidi tablicu 7). Izvlačeći komade papira iz takve urne jedan po jedan, dolazimo do "fraze" poput sljedeće: YYNT TSIYAA OERV ODNG YUEMLOLIK ZBYA ENVTSHA. Ova "fraza" je nešto sličnija suvislom ruskom govoru od prethodnog, ali je, naravno, još uvijek vrlo daleko od razumnog teksta. Različitost naše fraze sa smislenim tekstom prirodno se objašnjava činjenicom da, zapravo, uzastopna slova ruskog teksta uopće nisu neovisna jedno o drugom. Tako, na primjer, ako znamo da je samoglasnik sljedeće slovo, tada se vjerojatnost da se suglasno slovo pojavi na sljedećem mjestu značajno povećava; slovo "ʹ" nikako ne može pratiti ni razmak ni samoglasnik; slova "s", "I" ili "u" ne mogu se pojaviti iza slova "h", ali će se najvjerojatnije nalaziti jedan od samoglasnika "and" i "e" ili suglasnik "t", itd. Prisutnost u Ruski jezik dodatnih pravilnosti koje nisu uzete u obzir u našoj "frazi" dovodi do daljnjeg smanjenja stupnja nesigurnosti jednog slova ruskog teksta. Da biste to učinili, potrebno je samo izračunati uvjetnu entropiju eksperimenta koji se sastoji u određivanju jednog slova ruskog teksta, pod uvjetom da znamo ishod pokusa, koji se sastoji u određivanju prethodnog slova istog teksta. Uvjetna entropija određena je sljedećom formulom: gdje p (-), p (a), p (b), ..., p (i) označavaju vjerojatnosti (učestalosti) pojedinih slova ruskog jezika. Naravno, može se unaprijed reći da će vjerojatnosti p (- -), p (nb) i mnoge druge (na primjer, p (bb), p (- b), p (w), itd.) biti jednaka nuli. Možemo biti sigurni da će uvjetna entropija biti manja od bezuvjetne entropije. Vrijednost se može odrediti kao "prosječne informacije" sadržane u određivanju ishoda sljedećeg iskustva. Postoje 32 urne, označene s 32 slova ruske abecede; svaka od urni sadrži komadiće papira na kojima su ispisane dvoslovne kombinacije, počevši od slova naznačenog na urni, a broj papirića s različitim parovima slova proporcionalan je učestalosti (vjerojatnosti) odgovarajućih dvaju - kombinacije slova. Iskustvo se sastoji u stalnom vađenju komadića papira iz urni i ispisivanju posljednjeg slova iz njih. U tom slučaju svaki put (počevši od drugog) iz urne se vadi komad papira koji sadrži kombinacije koje počinju zadnjim ispisanim slovom; nakon što je pismo ispisano, komad papira se vraća u urnu, čiji se sadržaj ponovno dobro promiješa. Iskustvo ove vrste dovodi do "fraze" poput sljedeće: UMARONO KACH VANOZVANYE DOSYA NYKH CARPET NEDARE. Zvuk ove "fraze" mnogo je bliži ruskom jeziku. Poznavanje dva prethodna slova dodatno smanjuje nesigurnost eksperimenta koji se sastoji u određivanju sljedećeg slova, što se ogleda u pozitivnosti razlike, gdje je "uvjetna entropija drugog reda": svako od njih sadrži komadiće papira koji počinju s ista dva slova (ili pokus s ruskom knjigom, u kojem se prvo ponavljanje posljednje već napisane dvoslovne kombinacije nalazi nasumično mnogo puta i slovo koje slijedi ispisuje) dovodi do "fraze" poput slijedeće: DOK JE ZNOJ NORMOUSNOG ROCKERA POSTOPENO ZNANJE BUČVALO VAŠ OBNIL, još bliži ruskom govoru od prethodnog. Slično, moguće je odrediti entropiju koja odgovara iskustvu određivanja slova ruskog teksta, pod uvjetom da su poznata tri prethodna slova. Sastoji se od vađenja komadića papira iz 323 urne s kombinacijama od četiri slova (ili - eksperiment sličan gore opisanom eksperimentu s ruskom knjigom), dovodi do "fraze" poput sljedeće: ZABAVNA NA KAPIJA NE SUŠI I NEPO I CORKO, Još bolja aproksimacija entropiji smislenog ruskog teksta su vrijednosti na N = 5,6, .... Lako je vidjeti da s povećanjem N entropija HN može samo opadati. Ako također uzmemo u obzir da su sve vrijednosti HN pozitivne, iz toga će se moći zaključiti da vrijednost at teži određenoj granici. Već znamo da prosječan broj elementarnih signala potrebnih za prijenos jednog slova ruskog teksta ne može biti manji. Razlika koja pokazuje koliko je manji od jedinice omjer "granične entropije" i vrijednosti koja karakterizira najviše informacija, koji može biti sadržan u jednom slovu abecede s zadanim brojem slova, Shannon je nazvao redundancijom jezika. Suvišnost ruskog jezika (kao i redundancija drugih europskih jezika) znatno premašuje 50%. Odnosno, možemo reći da je izbor sljedećeg slova smislenog teksta više od 50% određen strukturom samog jezika i stoga je slučajan samo u relativno maloj mjeri. Redundantnost R vrlo je važna statistička karakteristika jezika, ali njezina brojčana vrijednost još nije određena sa zadovoljavajućom točnošću ni za jedan jezik. U odnosu na ruski jezik, posebno, postoje samo podaci o vrijednostima veličina H2 i H3. N0N1N2N3log 32 = 54.353.523.01 (radi potpunosti, ovdje smo dali i vrijednosti entropije N0 i N1). Iz ovoga se može samo zaključiti da je za ruski jezik zapravo vrijednost R mnogo veća od ovog broja. Jasno je da za sve jezike koji se koriste latinično pismo, maksimalna informacija N0, koja bi mogla pasti na jedno slovo teksta, ima isto značenje: bit (26 različitih slova abecede i 27. "slovo" je prazan prostor između riječi). Koristeći tablice relativnih frekvencija različitih slova u engleskom, njemačkom, francuskom i španjolskom, može se pokazati da je entropija H1 za ove jezike jednaka (u bitovima): jezik njemački francuski francuski španjolski N14,034,103,963,98 Vidimo da je u svim slučajevima, vrijednost H1 je primjetno manja od H0 = log 27 4,76 bita, a njegove vrijednosti za različiti jezici nisu jako različite jedna od druge. Vrijednosti H2 i H3 za engleski jezik izračunao je Shannon, dok je on koristio dostupne tablice učestalosti na engleskom za različite dvoslovne i troslovne kombinacije. Uzimajući u obzir i statistiku o učestalosti pojavljivanja različite riječi na engleskom, Shannon je mogla grubo procijeniti vrijednosti H5 i H8. Kao rezultat toga, dobio je: N0N1 N2N3N5N84.764.03 3.323.10≈2.1≈1.9 Iz ovoga možemo zaključiti da za engleski jezik redundancija R u svakom slučaju nije manja, tj. prelazi 60%. Brojanje vrijednosti H9, H10 itd. prema formuli poznatoj nam je nemoguće, jer izračun H9 zahtijeva poznavanje vjerojatnosti svih kombinacija od 9 slova, čiji je broj izražen 13-znamenkastim broj (trilijuni!). Stoga, za procjenu vrijednosti HN at velike vrijednosti N mora biti ograničeno neizravne metode... Zaustavimo se na jednoj od ovakvih metoda koje je predložio Shannon. "Uvjetna entropija" NN je mjera stupnja nesigurnosti iskustva, koja se sastoji u određivanju N-to slovo teksta, pod uvjetom da su nam poznata prethodna N - 1 slova. Pokus pogađanja N-tog slova lako se može postaviti: za to je dovoljno odabrati (N - 1) -alfatni fragment smislenog teksta i pozvati nekoga da pogodi sljedeće slovo. Takav se pokus može ponoviti mnogo puta, a teškoća pogađanja N-tog slova može se procijeniti pomoću prosječne vrijednosti QN broja pokušaja potrebnih za pronalaženje točnog odgovora. Jasno je da su veličine QN definirane za različita značenja N, određene su karakteristike statističke strukture jezika, posebice njegova redundantnost. Shannon je izveo niz sličnih eksperimenata, u kojima je N poprimio vrijednosti 1, 2, 3, ..., 14, 15 i 100. Pritom je otkrio da je pogađanje 100. slova po 99 prethodnih bilo mnogo lakši zadatak nego pogoditi 15-to slovo na prethodnih 14. Dakle, možemo zaključiti da je H15 osjetno veći od H100, odnosno da se H15 još ne može identificirati s graničnom vrijednošću. Nakon toga, isti su eksperimenti provedeni na nešto većem materijalu za N = 1, 2, 4, 8, 16, 32, 64, 128 i N ≈ 10 000. N128) se praktički ne razlikuje od N10000, dok se "uvjetna entropija " N16 je čak osjetno veći od ove vrijednosti. Dakle, može se pretpostaviti da se s povećanjem N vrijednost HN smanjuje do vrijednosti od N = 30, ali s daljnjim povećanjem N praktički se ne mijenja; stoga se umjesto o "ograničavanju entropije" može govoriti, na primjer, o uvjetnoj entropiji H30 ili H40. Eksperimenti s pogađanjem slova ne samo da nam omogućuju prosuđivanje komparativna vrijednost uvjetne entropije HN za različite N, ali također omogućuju da se ograde same vrijednosti HN. Prema podacima takvih eksperimenata, moguće je odrediti ne samo prosječan broj QN pokušaja potrebnih da se N-to slovo teksta pogodi po N - 1 prethodnim, već i vjerojatnost (učestalost) da će slovo biti ispravno pogodio iz 1., 2., 3., ..., n-og pokušaja (gdje je n = 27 broj slova abecede; QN =). Lako je razumjeti da su vjerojatnosti jednake vjerojatnosti slova abecede, poredanih silaznim redoslijedom učestalosti. Doista, ako ne znamo nijedno od slova koje prethodi slovu x koje treba pogoditi, onda je prirodno prije svega pretpostaviti da se x poklapa s najčešćim slovom a1 (i vjerojatnost ispravnog pogađanja ovdje će biti jednaka p (a1)); onda treba pretpostaviti da se x poklapa s a2 (vjerojatnost točnog odgovora ovdje će biti jednaka p (a2)) i tako dalje. Otuda slijedi da je entropija H1 jednaka zbroju. Ako je N> 1, tada se može pokazati da zbroj (*) neće premašiti uvjetnu entropiju HN (to je zbog činjenice da vrijednosti na određeni način predstavljaju prosječne vjerojatnosti ishoda eksperimenta) . S druge strane, nešto kompliciranija razmatranja, na kojima se ovdje nećemo zadržavati, omogućuju nam da dokažemo da zbroj (**) za bilo koji N neće biti veći od uvjetne entropije NN. Dakle, izrazi (*) i (**) (sastavljeni od vjerojatnosti koje se mogu procijeniti iz eksperimentalnih podataka) određuju granice između kojih treba ležati vrijednost HN. Samo trebate imati na umu da su obje procjene (*) i (**) dobivene pod pretpostavkom da su to vjerojatnosti pogađanja slova iz N - 1 prethodnih slova iz prvog, drugog, trećeg itd. pokušaja koji dobivaju se pod pretpostavkom da nagađač uvijek najpovoljnije imenuje sljedeće slovo - uz puno uvažavanje svih statističkih zakona ovog jezika... U slučaju stvarna iskustva bilo kakve pogreške u strategiji osobe koja pogađa (odnosno, razlike između slova koje naziva i onih koja bi trebala biti imenovana na temelju točne statistike jezika) neminovno će dovesti do precjenjivanja i zbroja (*) i ( **); zato je preporučljivo uzeti u obzir samo podatke "najuspješnijeg pogađača", jer će za njega ovo precjenjivanje biti najmanje. Budući da svaki nagađač ponekad griješi, procjena (**) u praksi se ne može smatrati potpuno pouzdanom donjom procjenom stvarne entropije (za razliku od gornje procjene (*), koja zbog pogrešaka nagađača može postati samo čak i veći). Osim toga, vrijednosti zbroja (*) i (**), nažalost, ne približavaju se beskonačno s povećanjem N (počevši od N ≈ 30, ovi zbroji općenito prestaju ovisiti o N); stoga procjene redundancije jezika dobivene na ovom putu neće biti osobito točne. Konkretno, Shanonovi eksperimenti pokazali su samo da se čini da je vrijednost H100 između 0,6 i 1,3 bita. Dakle, možemo zaključiti da bi redundancija za engleski jezik po redu veličine trebala biti blizu 80%. 2.2.2 Usmeni govor. Sada prelazimo na pitanje entropije i informacija u usmenom govoru. Prirodno je misliti da će sve statističke karakteristike takvog govora još više ovisiti o izboru ljudi koji govore i o prirodi njihovog razgovora. Smanjena vrijednost entropije usmenog govora može biti posljedica činjenice da u razgovoru često koristimo više ponavljanja istih riječi i često dodajemo dosta "dodatnih" riječi - to se čini kako bi se olakšala percepcija govora. , i jednostavno tako da govornik ima vremena razmisliti što sljedeće želi reći. Odredivši prosječan broj izgovorenih slova u jedinici vremena, može se grubo procijeniti količina informacija prenesenih tijekom razgovora u 1 sekundi; obično je reda veličine 5 do 6 bita. Iz razgovora možemo suditi o raspoloženju govornika i njegovom odnosu prema izrečenom; možemo prepoznati govornika, čak i ako nam ga nijedan drugi izvor informacija ne ukazuje; u mnogim slučajevima možemo odrediti mjesto rođenja stranca po njegovom izgovoru; možemo procijeniti glasnoću usmenog govora, koja je u slučaju prijenosa glasa preko komunikacijske linije u velikoj mjeri određena isključivo tehničke karakteristike dalekovode itd. Kvantificiranje svih ovih informacija vrlo je težak zadatak koji zahtijeva puno više znanja jezika. Iznimka u tom pogledu je relativno usko pitanje logičkih naglasaka koji naglašavaju pojedine riječi u frazi. Naglasak najčešće pada na najrjeđe korištene riječi (što je, međutim, sasvim prirodno - jasno je da će teško da će itko logičnim naglaskom naglasiti najčešći slon - primjerice prijedlozi ili veznici). Ako je vjerojatnost da danu riječ Wr je pod naglaskom, označavamo ga s qr, tada će prosječna informacija, koja se sastoji od informacija o prisutnosti ili odsutnosti naglaska na ovoj riječi, biti jednaka. Neka su sada vjerojatnosti (učestalosti) svih riječi W1, W2,. ... ., WK (ovdje K - ukupni broj sve korištene riječi. U ovom slučaju, za prosječnu informaciju H, zatvorenu u logički naglasak, možete napisati sljedeću formulu: Prosječna informacija koju dobivamo otkrivanjem na koje riječi pada logički naglasak bliska je po redu veličine 0,65 bita po riječi . Tijekom razgovora nikada se ne izgovaraju pojedina slova, već se izgovaraju glasovi koji se bitno razlikuju od slova. Stoga glavni element usmenog govora treba smatrati zasebnim zvukom - fonemom. Smisleni govorni jezik sastavljen je od fonema na isti način na koji se smisleni pisani jezik sastoji od slova. Dakle, u svim slučajevima kada nas zanima samo prijenos „semantičkih informacija“ usmenog govora najveći interes ne predstavlja entropiju i informaciju jednog "govornog slova", već entropiju i informaciju jednog stvarno izgovorenog fonema. Popis fonema datog jezika, naravno, ne podudara se s popisom slova abecede, budući da je isto slovo u različitim slučajevima može zvučati drugačije. U ruskom jeziku postoje 42 različita fonema i broje se frekvencije pojedinih fonema (kao i različite kombinacije dva i tri uzastopna fonema). N0 = log 42 jednog fonema, entropije prvog reda (gdje su relativne frekvencije različitih fonema) i "uvjetne entropije" N2 i N3: N0N1N2N3log 42 ≈ 5,38 4,77 3,62 0,70 Ako ove vrijednosti usporedimo s vrijednostima od N0 , N1, N2, H3 za pisani ruski govor, tada se smanjenje broja uvjetne entropije za foneme događa zamjetno brže nego u slučaju slova pisanog teksta. Da biste odredili redundanciju R (riječi), možete uspostaviti odnos između suvišnosti govora i pisanja. Iz činjenice da se usmeni govor može snimati i pisati - čitati, proizlazi da "cjelovita informacija" sadržana u određenom tekstu ne ovisi o obliku u kojem je - usmenom ili pisanom - ovaj tekst prikazan, odnosno . .. Otuda slijedi gdje je prosječan broj slova po fonemu ("prosječna dužina fonema"). Ova vrijednost je važna statistička karakteristika jezika koja povezuje govorni i pisani govor. Iz posljednje formule također slijedi da je ili gdje je k ukupan broj fonema, a n broj slova; jer ovdje je prirodnije uzeti. Međutim, korištenje ove formule otežava nedostatak statističkih podataka za određivanje vrijednosti. 2.2.3 Glazba. Istraživanja iste vrste mogu se provesti u pogledu glazbenih poruka. Prirodno je misliti da su veze između uzastopnih zvukova određene melodije, izražene pojedinačnim notnim znakovima, dovoljno jake: budući da će neke kombinacije zvukova biti skladnije od drugih, one će se češće naći u glazbenim djelima od potonji. Ako nasumce ispišemo niz bilješki, tada će informacije sadržane u svakoj bilješci ovog zapisa biti najveće; međutim, s glazbene točke gledišta, takav kaotičan slijed nota ne bi imao nikakvu vrijednost. Da bismo dobili zvuk ugodnog zvuka, potrebno je u naš raspon uvesti određenu redundantnost; istodobno se može bojati da ćemo u slučaju prevelike suvišnosti, u kojoj su sljedeće note gotovo nedvosmisleno određene prethodnim, dobiti samo izrazito monotonu i nezanimljivu glazbu. Koja je redundancija na kojoj se može dobiti "dobra" glazba? Redundancija jednostavne melodije ništa manje nego suvišnost smislenog govora. Bilo bi potrebno posebno proučiti pitanje redundancije raznih oblika glazbena djela ili djela raznih skladatelja. Na primjer, analizirajte popularni album dječjih pjesama s gledišta teorije informacija. Radi jednostavnosti, ovaj rad pretpostavlja da su svi zvukovi unutar jedne oktave; budući da se u razmatranim melodijama nisu javljali takozvani kromatizmi, sve bi se te melodije mogle svesti na sedam osnovnih glasova; Do, re, mi, fa, sol, la i si, svaki osmi u trajanju. Obračun zvukova s trajanjem dužim od jedne osmine obavljen je tako da se sedam tona doda osmi "glavni element" O, koji označava produljenje prethodnog zvuka za još jedno vremensko razdoblje od jedne osmine (ili pauzu od jedna osmina). Dakle, "maksimalna moguća entropija" H0 jedne note ovdje je jednaka H0 = log 8 = 3 bita. Izračunavši frekvencije (vjerojatnosti) pojedinih nota u svih 39 analiziranih pjesama, nalazimo da pomoću pronađenih vjerojatnosti kombinacija dviju nota možemo izračunati i uvjetnu entropiju H2, koja se ispostavila blizu 2,42. Samo od vrijednosti H1 i H2, vrlo se malo može reći o stupnju redundancije razmatranih, očito je osjetno veći od. Ovaj zaključak podupiru i istraživanja mnogih poznatih autora. 2.2.4 Prijenos televizijske slike... Naše oko može razlikovati samo konačan broj stupnjeva svjetline slike i samo ne previše bliske dijelove, stoga se bilo koja slika može prenijeti "točku po točku", od kojih je svaki signal koji uzima samo konačan broj vrijednosti. Potrebno je uzeti u obzir značajan broj (nekoliko desetaka) stupnjevanja stupnja zacrnjenja ("svjetline") svakog elementa, osim toga, svake sekunde se na TV ekranu mijenja 25 kadrova, stvarajući dojam "kretanja ". Međutim, komunikacijska linija zapravo ne prenosi ishod eksperimenta, koji se sastoji u određivanju vrijednosti kontinuirane promjene od točke do točke, u vremenu, te boje ili svjetline slike, već ishod potpuno drugačijeg " kvantizirani" eksperiment koji se sastoji u određivanju boje (bijele ili crne) ili gradacije svjetline u konačnom broju "točaka". Ovo novo iskustvo već može imati samo konačan broj ishoda, a možemo izmjeriti njegovu entropiju H. Ukupan broj elemenata ("točaka") za crno-bijelu televiziju, na koje treba razložiti sliku, određen je prvenstveno takozvanom "moći razlučivanja" oka, odnosno njegovom sposobnošću da razlikuje bliska područja slike. U modernoj televiziji taj je broj obično reda veličine nekoliko stotina tisuća (u sovjetskim televizijskim programima slika se razlaže na 400.000 - 500.000 elemenata, u američkoj - za oko 200.000 - 300.000, u programima nekih francuskih i belgijskih televizijskih centara - za gotovo 1.000.000) ... Lako je razumjeti da je iz tog razloga entropija televizijske slike ogromna. Čak i ako pretpostavimo da ljudsko oko razlikuje samo 16 različitih gradacija svjetline (vrijednost je očito podcijenjena) i da je slika razložena na samo 200.000 elemenata, tada nalazimo da je "entropija nultog reda" ovdje jednaka N0 = log 16.200.000 = 800.000 bita. Vrijednost prave entropije H, naravno, bit će manja, budući da televizijska slika ima značajnu redundanciju. Prilikom izračunavanja vrijednosti H0, pretpostavili smo da su vrijednosti svjetline na bilo koje dvije "točke" slike neovisne jedna o drugoj, dok se zapravo svjetlina obično vrlo malo mijenja kada se ide na susjedni elementi ista (ili čak drugačija, ali vremenski bliska) slika. Vizualno značenje ove redundancije R je da će među naših 16.200.000 mogućih kombinacija vrijednosti svjetline na svim točkama zaslona, smislene kombinacije koje se mogu nazvati "slike" činiti samo zanemariv dio, a ostatak će biti potpuno neuređen skup točaka različite svjetline.vrlo daleko od bilo kakvog "zapleta". U međuvremenu, stvarni "stupanj neizvjesnosti" H televizijske slike trebao bi uzeti u obzir samo one kombinacije vrijednosti svjetline koje imaju barem neke šanse da se prenesu. Da bi se odredila točna vrijednost entropije H (ili redundancije R) televizijske slike, potrebno je detaljno proučiti statističke odnose između svjetline različitih točaka na ekranu. Tako su pronađene vrijednosti entropija H0, H1, H2 i H3 za dvije specifične televizijske slike, od kojih je prva (slika A - park sa drvećem i zgradama) bila složenija, a druga (slika B - prilično mračna galerija s prolaznicima) bila je jednobojnija po boji i sadržavala je manje detalja, a razlikovala je 64 različite gradacije svjetline elementa televizijske slike, dakle entropiju H0 (odnosi se na jedan element, a ne na cijelu sliku u cjelini) ovdje se pokazalo jednakim H0 = log 64 = 6 bita. Zatim su pomoću posebnog radiouređaja izračunate relativne frekvencije (vjerojatnosti) svih vidljivih gradacija svjetline za obje razmatrane slike i odredile "entropiju prvog reda". Isti radio uređaj je zatim korišten za izračunavanje relativnih frekvencija pij od parovi susjednih (horizontalno) elemenata od kojih prvi element ima tj. vrijednost svjetline, i drugi j-e, kao i relativne frekvencije pijk trojki susjednih (također samo vodoravno) elemenata, u kojima je prvi element imao i-e vrijednost svjetline, drugi j-e, i treći kth(brojevi i, j i k prolazili su kroz sve vrijednosti od 1 do 64). Ove frekvencije omogućile su određivanje "entropija složenih eksperimenata", a zatim "uvjetnih entropija" i posljednje u kojoj je, međutim, izračunata samo za sliku B. Dobiveni rezultati sažeti su u sljedećoj tablici: , 91.5 Redundancy R, procijenjen vrijednošću H2 za sliku A je 44%, a za sliku B - 68%; stvarna vrijednost može postojati samo više zaliha od ovoga. Što se tiče uvjetne entropije H3 za poznatu svjetlinu dva prethodna elementa iste linije, ona se relativno malo razlikuje od H2 (slika B, 75%); iz ovoga možemo zaključiti da poznavanje svjetline najbližeg elementa određuje vrlo velik dio ukupne redundancije. Još jedno iskustvo koje se oslanja na cijepanje također ima sličan karakter. moguće vrijednosti svjetlina televizijskog slikovnog elementa za 8, a ne za 64 gradacije, za koje su izračunate entropije H0 i H1 i broj uvjetnih entropija H2, H3 i H4 jednog slikovnog elementa za sljedeća četiri sportska televizijska grafika: A - brzo trčanje košarkaši, B - krupni plan lica jednog gledatelja na tribini stadiona, C - pomicanje pogleda gledatelja na tribini i D - brzotrčači nogometaši. Brojkama 1 i 2 označit ćemo elemente slike koji se nalaze uz podatke vodoravno i okomito, brojem 3 - dijagonalno susjedni element, brojem 4 - isti kao onaj koji se razmatra, element na prethodnom okviru televizijski prijenos, brojem 5 - element na istoj horizontali, uz element 1, i, konačno, broj 6 - isti element na kadru koji prethodi onom koji sadrži element 4 (slika 1), a) b ) Slika 1.a u zapisu uvjetnih entropija odozgo u zagradama naznačit ćemo brojeve slika elemenata čiji se stupanj svjetline smatra poznatim. U ovom slučaju, vrijednosti entropije (u bitovima) mogu se sažeti u sljedeću tablicu: A31,960,690,98-1,77B31,950,360.36 - B32,781,341,952.78-G32.45-2.002.08-0 A0 , 56 - B0.35-0.270.26-B - 1.221.181.19G-1.83 --- Rezultati posljednjeg eksperimenta navode na zaključak da za sliku siromašnu detaljima ("lice") redundantnost nije manja od 90%, a za sliku bogatu detaljima („gledatelji“) nije manje od 60%. Razlozi ovog odstupanja su još uvijek nejasni. Za televizijske slike u boji, informacije su po redu veličine usporedive s udvostručenim informacijama sadržanim u odgovarajućoj crno-bijeloj slici. ZAKLJUČAK U ovom radu postavljeni su sljedeći ciljevi i zadaci. Svrha: proučiti principe kodiranja informacija Shannon - Fano i Huffman i njihovu primjenu u rješavanju problema. Cilj: proučiti entropiju i redundantnost određenih vrsta poruka za naknadnu primjenu principa Shannon - Fano i Huffman na njih. Nakon ostvarenja ciljeva i zadataka teza doneseni su sljedeći zaključci. Prije pojave djela Shannon i Fano, kodiranje znakova abecede pri prijenosu poruke komunikacijskim kanalima provedeno je s istim brojem bitova, dobivenih Hartleyevom formulom. Pojavom ovih radova počele su se pojavljivati metode koje kodiraju znakove s različitim brojem bitova, ovisno o vjerojatnosti njihovog pojavljivanja u tekstu, odnosno vjerojatniji znakovi se kodiraju kratkim kodovima, a rijetki znakovi kodiraju s duge (duže od prosjeka). Otkako je D.A. Huffman 1952. objavio svoje djelo "Metoda za konstruiranje kodova s minimalnom redundantnošću", njegov algoritam kodiranja postao je temelj za veliki iznos daljnja istraživanja u ovom području. Vrijedi napomenuti da više od 50 godina od datuma objave Huffmanov kod uopće nije izgubio svoju relevantnost i značaj. Dakle, možemo s povjerenjem reći da smo suočeni s tim, u ovom ili onom obliku (činjenica je da se Huffmanov kod rijetko koristi zasebno, češće radi u sprezi s drugim algoritmima), gotovo svaki put kada arhiviramo datoteke, gledamo fotografije , filmovi , slanje faksa ili slušanje glazbe. Prednosti ovih metoda su njihova očita jednostavnost implementacije i, kao posljedica toga, velika brzina kodiranje i dekodiranje. Glavni nedostatak je što nisu optimalni u općem slučaju. 3
Razmotrimo algoritam za izračunavanje Shannon-Fano kodova (radi jasnoće, uzmimo slijed "aa bbb cccc ddddd" kao primjer). Da biste izračunali kodove, morate izraditi tablicu jedinstvenih simbola poruka c (i) i njihove vjerojatnosti p (c (i)), i sortirati ga po nerastućem redoslijedu vjerojatnosti simbola.
| c (i) | p (c (i)) |
| d | 5 / 17 |
| c | 4 / 17 |
| prostor | 3 / 17 |
| b | 3 / 17 |
| a | 2 / 17 |
Nadalje, tablica simbola je podijeljena u dvije skupine tako da svaka od skupina ima približno istu frekvenciju u zbroju simbola. Prva grupa je postavljena na početak koda na "0", druga na "1". Za izračunavanje sljedećih bitova znakovnih kodova, ovaj postupak se ponavlja rekurzivno za svaku grupu koja sadrži više od jednog znaka. Tako za naš slučaj dobivamo sljedeće znakovne kodove:
Dužina koda s (i) u rezultirajućoj tablici je int (-lg p (c (i))), ako bi se sivole mogle podijeliti u skupine s istu frekvenciju inače, duljina koda je int (-lg p (c (i))) + 1.
39 bita duga. Uzimajući u obzir da je original bio dugačak 136 bita, dobivamo omjer kompresije od ~ 28% - nije tako loše.
Gledajući rezultirajući slijed, postavlja se pitanje: "Kako to sada možete dekomprimirati?" Ne možemo, kao u slučaju kodiranja, zamijeniti svakih 8 bitova ulaznog toka s kodom promjenjive duljine. Prilikom dekompresije trebamo učiniti suprotno – zamijeniti kod varijabilne duljine 8-bitnim znakom. V u ovom slučaju, najbolje bi bilo koristiti binarno stablo, čiji će listovi biti simboli (analogno Huffmanovu stablu).
Shannon-Fano kodiranje je prilično stara metoda kompresije, a danas nije od posebnog praktičnog interesa (osim kao vježba u tijeku strukture podataka). U većini slučajeva, duljina komprimirane sekvence, prema ovoj metodi, jednaka je duljini komprimirane sekvence korištenjem Huffmanovog kodiranja. Ali na nekim sekvencama još uvijek se formiraju neoptimalni Shannon-Fano kodovi, stoga se kompresija po Huffmanovoj metodi smatra učinkovitijom. Na primjer, razmotrite niz sa sljedećim sadržajem znakova: "a" - 14, "b" - 7, "c" - 5, "d" - 5, "e" - 4. Huffmanova metoda ga komprimira na 77 bita , ali Shannon-Fano do 79 bita.
|
Kako smo se podijelili u grupe? dovoljno jednostavno:
Zbog ove dvosmislenosti, neki ljudi čak imaju takve misli: "... program ponekad dodjeljuje neke simbole ..." i tako dalje - razmišljanje o duljini kodova. Ako ne pišete AI, onda takva stvar kao što je "program ponekad" čini nešto zvuči smiješno. Ispravno implementirani algoritam radi na strogo definiran način.
Ista poruka se može kodirati različiti putevi... Najpovoljniji kod je onaj koji troši najmanje vremena na prijenos poruke. Ako prijenos svakog elementa znaka (na primjer, 0 ili 1) traje isto vrijeme, tada će optimalni kod biti takav da kada se koristi za prijenos poruke zadane dužine bit će potrošen minimalni broj elementarnih znakova. Shannon - Fano kodovi su prefiksni, t.j. Ne kodna riječ nije prefiks nijednog drugog. Ova nekretnina omogućuje nedvosmisleno dekodiranje bilo kojeg niza kodnih riječi
Razmotrimo princip izgradnje jednog od prvih algoritama kompresije, koji su formulirali američki znanstvenici Shannon i Fano na primjeru slova ruske abecede. Algoritam koristi kodove promjenjive duljine, tj. uobičajeni znak kodiran je kodom kraće duljine, rijedak - dužim kodom.
Da biste sastavili takav kod, očito morate znati učestalost pojavljivanja slova u ruskom tekstu. Ove frekvencije su prikazane u tablici 1. Slova u tablici poredana su silaznim redoslijedom po učestalosti.
stol 1
Učestalost pojavljivanja slova ruske abecede
Pomoću tablice možete sastaviti najekonomičniji kod na temelju razmatranja vezanih uz informacije. Očito, kod će biti najekonomičniji kada će svaki elementarni znak prenositi maksimalne informacije... Razmotrite elementarni simbol (tj. koji predstavlja njegov signal) kao fizički sustav s dva moguća stanja: 0 i 1. Informacija koju daje ovaj simbol jednaka je entropiji ovog sustava i maksimalna je u slučaju kada su oba stanja jednako vjerojatna; u ovom slučaju, elementarni simbol prenosi informaciju 1 (binarni). Stoga će osnova za optimalno kodiranje biti zahtjev da se elementarni znakovi u kodiranom tekstu pojavljuju u prosjeku jednako često.
Ideja kodiranja je da se kodirani znakovi (slova ili kombinacije slova) dijele u dvije približno jednako vjerojatne skupine: za prvu grupu znakova, prvo mjesto kombinacije je 0 (prvi znak binarnog broja predstavljanje lika); za drugu skupinu - 1. Nadalje, svaka se skupina ponovno dijeli na dvije približno jednako vjerojatne podskupine; za simbole prve podskupine, 0 se stavlja na drugo mjesto; za drugu podskupinu - jedan itd.
Pokažimo princip konstruiranja Shannon-Fano koda na primjeru materijala ruske abecede (vidi tablicu 1). Izbrojimo prvih šest slova (od "-" do "t"); zbrajajući njihove vjerojatnosti (frekvencije), dobivamo 0,498; sva ostala slova od "n" do "f" imat će približno istu vjerojatnost od 0,502. Prvih šest slova (od "-" do "t") imat će na prvom mjestu binarni predznak 0. Ostala slova (od "n" do "f") će imati 1 na prvom mjestu. Nadalje, ponovno ćemo prvu skupinu podijeliti u dvije približno jednako vjerojatne podskupine: od "-" do "o" i od "e" do "t"; za sva slova prve podskupine na drugo mjesto stavljamo nulu, a drugu podskupinu - jedan. Nastavit ćemo proces sve dok u svakoj podrazdjeli ne bude točno jedno slovo koje će biti kodirano u određenom binarni broj... Mehanizam konstrukcije prikazan je u tablici 2, a sam kod je prikazan u tablici 3.
tablica 2
Mehanizam za konstruiranje Shannon - Fano koda na primjeru ruske abecede
| Binarni znakovi | |||||||||
| pisma | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| - | |||||||||
| O | |||||||||
| e | |||||||||
| a | |||||||||
| i | |||||||||
| T | |||||||||
| n | |||||||||
| S | |||||||||
| R | |||||||||
| v | |||||||||
| l | |||||||||
| Do | |||||||||
| m | |||||||||
| d | |||||||||
| P | |||||||||
| na | |||||||||
| Ja sam | |||||||||
| s | |||||||||
| s | |||||||||
| b, b | |||||||||
| b | |||||||||
| G | |||||||||
| h | |||||||||
| th | |||||||||
| x | |||||||||
| f | |||||||||
| Yu | |||||||||
| w | |||||||||
| c | |||||||||
| SCH | |||||||||
| Eh | |||||||||
| f |
Tablica 3
Rezultat kodiranja slova ruske abecede kodom Shannon - Fano
Primjer 4. Napišimo izraz "metoda kodiranja" koristeći Shannon - Fano kod.
Riješenje: Koristimo tablicu 3 i dobićemo sljedeći rezultat:
(1001) s (110011) n (001) o (1001) s (001) o (111010) b (000) razmak
(10111) do (001) o (110010) d (0110) i (10100) r (001) o (10101) c
(0101) a (1000) n (0110) i (110110) i
Imajte na umu da nema potrebe odvajati slova jedno od drugog posebnim znakom, jer se čak i bez ovog dekodiranja nedvosmisleno izvodi zbog svojstva prefiksa: nijedna kraća kodna riječ nije početak duže kodne riječi. Doista, tablica 3 pokazuje da su najkraći kodovi za znakove "razmak" i "o". Štoviše, niti jedan drugi više dugi kod nema 000 ("razmak") i 001 ("o") na početku niza. Isto se može primijetiti i za sve ostale binarne sekvence Shannon - Fano koda, koje su prikazane u tablici 3.
Treba napomenuti da je svaka pogreška kodiranja (slučajno miješanje 0 ili 1 znaka) s takvim kodom fatalna, jer dekodiranje cijelog teksta nakon pogreške postaje nemoguće.
Primjer 5. Utvrdite je li kod koji smo razmatrali optimalan u nedostatku pogrešaka?
Riješenje: Pronađimo prosječnu informaciju po jednom elementarnom simbolu (0 ili 1) i usporedimo je s maksimumom moguće informacije, što je jednako jedan. Da bismo to učinili, prvo pronalazimo prosječnu informaciju sadržanu u jednom slovu poslanog teksta, tj. entropiju po slovu (vidi formulu 8):
Prema tablici 1 određujemo prosječan broj elementarnih znakova po slovu:
Dakle, informacija po znaku je vrlo blizu svoje gornje granice od jedan, i dati kod vrlo blizu optimalnog.
U slučaju korištenja pet-bitnog binarnog koda, informacije po znaku:
Primjer 6. Neka se poruka (riječ na ruskom) primi putem komunikacijskog kanala kodiranog kodom Shannon-Fano: 10111001110010010010100.
Potrebno je dekodirati zadani niz.
Riješenje: Proces dekodiranja temelji se na svojstvu prefiksa koda i izvodi se s lijeva na desno. Tablica 3 pokazuje da je minimalna duljina koda tri bita. Broji tri bita od početka primljene kodne riječi, dobivamo - 101. U tablici nema takvog koda, pa dodajemo još jedan bit, dobivamo - 1011. Ovaj kod također nije u tablici, stoga je potrebno dodati još jedan bit, dobivamo kombinaciju - 10111, što odgovara slovu "k". Kodna riječ 10111 isključena je iz primljene kodne riječi i zamijenjena je izvornim simbolom (slovo "k"). Proces dekodiranja ostatka slova primljenu poruku provodi se na sličan način.
Kompletan proces dekodiranja prikazan je u tablici 4. Znak “-” u tablici znači da odabrani kod nema u tablici 3.
Tablica 4
Proces dekodiranja poruke
| Primljeni kodni slijed | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| Do | ||||||||||||||||||||||
| Do | O | |||||||||||||||||||||
| Do | O | - | ||||||||||||||||||||
| Do | O | - | ||||||||||||||||||||
| Do | O | - | ||||||||||||||||||||
| Do | O | d | ||||||||||||||||||||
| Do | O | d | - | |||||||||||||||||||
| Do | O | d | e | |||||||||||||||||||
| Do | O | d | e | - | ||||||||||||||||||
| Do | O | d | e | - | ||||||||||||||||||
| Do | O | d | e | R |
Dakle, riječ dobivena kao rezultat dekodiranja primljene kodne riječi je "koder".
Optimalno kodiranje
Shanonov teorem kodiranja. Optimalne metode kodiranja slovo po slovo. Kriteriji optimalnosti koda. Blok kodiranje. jedan sustav kodiranje tekstualnih informacija.
Kodiranje,minimiziranje redundancije koda,naziva se optimalnim.
Pitanje postojanja takvih kodova bit je jednog od glavnih teorema teorije informacija – teorema kodiranja koji je dokazao K. Shannon. Ovdje je jedna od ekvivalentnih formulacija ovog teorema.
Teorem kodiranja. Poruke proizvoljnog izvora informacija Z s entropijom H(Z)uvijek se može kodirati nizovima u abecedi B,koji se sastoji od M znakova,Tako,da će prosječna duljina kodne riječi biti proizvoljno blizu vrijednosti 
,ali ne manje od nje.
Zbog svoje složenosti, dokaz ovog teorema se ne razmatra.
Teorem kaže da se razlika može učiniti proizvoljno malom. To je zadatak optimalnih metoda kodiranja.
Vratimo se na razmatranje abecednog izvora informacija koji generira poruke abecednim znakovima A... Budući da je redundantnost koda data formulom
očito je da što je manje, to je kod optimalniji. Za smanjenje znakove koji se često pojavljuju trebaju biti kodirani kraćim riječima i obrnuto. Sve optimalne metode kodiranja temelje se na ovom zahtjevu. Osim toga, kako bi se osiguralo dekodiranje neujednačenog koda, važno je promatrati princip prefiksa: Nijedna kodna riječ ne smije biti početak druge kodne riječi.
Ovdje su dvije od najpoznatijih metoda optimalnog kodiranja slovo po slovo. Radi jednostavnosti, uzimamo binarna abeceda kao kod.
Korak 1. Slažemo simbole izvorne abecede redoslijedom nerastanja njihovih vjerojatnosti. (Zapisujemo ih u niz.)
Korak 2. Ne mijenjajući redoslijed simbola, dijelimo ih u dvije skupine kako bi ukupne vjerojatnosti simbola u skupinama bile što jednakije.
Korak 3. Grupi s lijeve strane dodjeljujemo "0", a grupi s desne strane "1" kao elemente njihovih kodova.
Korak 4. Pregledajte grupe. Ako je broj elemenata u grupi više od jednog, idite na korak 2. Ako postoji jedan element u grupi, izrada koda za njega je dovršena.
Riža. 4.1. Binarno stablo odgovara Shannon - Fano kodiranju
Razmotrimo rad opisanog algoritma na primjeru kodiranja abecede 
, čiji se simboli pojavljuju s vjerojatnostima (0,25; 0,05; 0,25; 0,1; 0,25; 0,1). Rezultat kodiranja prikazan je na Sl. 4.1.
Očito je da proces konstruiranja koda u općem slučaju sadrži dvosmislenost, budući da sekvencu ne možemo uvijek podijeliti na dva jednako vjerojatna podskupa. Ili s lijeve ili desne strane, zbroj vjerojatnosti će biti veći. Kriterij najboljeg slučaja je manje redundancije koda. Također imajte na umu da će ispravno čitanje koda - od korijena stabla do simbola - osigurati da je s prefiksom.
