INTRODUCERE Noile tendințe care au apărut în matematică în secolul al XX-lea operează de obicei cu concepte și concepte complexe care sunt greu de popularizat. Pe acest fond, meritul remarcabilului matematician și inginer american Claude Shannon, care în 1947-1948, pe baza unor considerații elementare, a descoperit zona noua matematică – teoria informaţiei. Impulsul de a crea noua stiinta erau curate probleme tehnice transmiterea de informații prin cabluri telegrafice și telefonice, totuși, datorită naturii sale generale, teoria informației este acum utilizată în cercetările legate de transmiterea și stocarea oricărei informații din natură și tehnologie. La sfârșitul anilor patruzeci, în zorii dezvoltării teoriei informației, ideea de a dezvolta noi moduri eficiente informațiile de codificare erau în aer. Cercetătorii s-au ocupat de probleme de entropie, conținut informațional și redundanță. Ma intreb ce astea lucrări inițialeîn domeniul compresiei informaţiei au fost efectuate înainte de apariţia calculatorului digital modern. Astăzi, teoria informației se dezvoltă în paralel cu programarea, dar la acea vreme ideea dezvoltării algoritmilor folosind aritmetica binară pentru a codifica caractere a fost un pas semnificativ înainte. Algoritmii Shannon - Fano și Huffman au fost unul dintre primii algoritmi de codificare eficientă a informațiilor. Această lucrare are în vedere Noțiuni de bază entropia și informația, și, de asemenea, descrie principiile de codificare a mesajelor conform lui Shannon - Fano și Huffman, arată rolul lor important în transmiterea informațiilor pe liniile de comunicare. Dar liniile de comunicare pentru care au fost dezvoltate aceste metode de codificare a informațiilor sunt deja în trecut. Din fericire, principiile Shannon-Fano și Huffman au fost aplicate în lumea modernă: pentru a comprima informații. Arhivare PKZIP, ARJ, precum și parte a binecunoscutului standard JPEG (compresie informatii grafice cu pierderi) lucrează tocmai pe aceste principii. Codurile Shannon-Fano și Huffman sunt predate în toate universitățile tehnice din lume și, în plus, sunt incluse în programul de studiu avansat al informaticii la școală. Prin urmare, studiul metodelor de codificare Shannon - Fano și Huffman este relevant. Scopul acestei lucrări este de a studia principiile de codificare a informațiilor lui Shannon - Fano și Huffman și aplicarea acestora în rezolvarea problemelor. Sarcina este de a studia entropia și redundanța unor tipuri specifice de mesaje pentru aplicarea ulterioară a principiilor Shannon-Fano și Huffman. 1. Informații și codare. Codurile Shannon - Fano și Huffman. 1.1 Informații și codare. Cuvântul „informație” este cunoscut de toată lumea din timpul nostru. Provine din latinescul „informatio”, care înseamnă - clarificare, mesaj, conștientizare. Cu toate acestea, a intrat în uz constant nu cu mult timp în urmă, la mijlocul secolului al XX-lea, la sugestia lui Claude Shannon. El a introdus acest termen într-un sens tehnic restrâns în raport cu teoria comunicării sau transmiterii codurilor, care a fost numită „Teoria informației”. Aici, nu orice informație este importantă, ci doar cele care înlătură sau reduc complet incertitudinea existentă. O definiție filozofică și, prin urmare, mai largă a acestui termen este dată de unul dintre fondatorii informaticii, celebrul om de știință american Norbert Wiener: „Informația este o desemnare a conținutului pe care îl extragem din lumea exterioară în procesul adaptării noastre la și aducând gândirea noastră în concordanță cu ea.” Desigur, acestea sunt departe de definiții unice ale informațiilor. În prezent, acest termen are un sens mai profund și mai multifațetat. Rămânând în mare măsură intuitivă, primește conținut semantic diferit în diferite ramuri ale activității umane: * în aspectul cotidian, informația este înțeleasă ca informații despre lumea din jurul ei și despre procesele care au loc în ea, percepute de o persoană sau dispozitive speciale; * în tehnologie, informația este înțeleasă ca mesaje transmise sub formă de semne sau semnale; * în teoria informaţiei (după K. Shannon), nu orice informaţie este importantă, ci doar cele care înlătură sau reduc complet incertitudinea existentă; * în teoria semantică (sensul unui mesaj) - aceasta este o informație care are o noutate și așa mai departe ... O astfel de varietate de abordări nu este întâmplătoare, ci o consecință a faptului că necesitatea unei organizări conștiente a procese de mișcare și prelucrare a ceea ce are o denumire comună – au apărut informații. Pentru o considerație suplimentară, avem nevoie de conceptul de informație, care presupune transmiterea de mesaje informaționale pe liniile de comunicare. Considera schema generala transmiterea de mesaje; pentru certitudine, vom vorbi, de exemplu, de telegrafie. La un capăt al liniei, expeditorul trimite un mesaj, scris folosind oricare dintre alfabetele sau numerele cunoscute de noi, sau ambele litere și cifre combinate. Pentru transmiterea acestui gen de mesaje se folosesc secvenţe de semnale de curent continuu, unele dintre caracteristicile cărora operatorul de telegrafie le poate modifica la discreţia sa, percepute de cel de-al doilea operator de telegrafie la capătul de recepţie al liniei. Cele mai simple semnale distinctive, utilizate pe scară largă în practică, sunt trimiterea unui curent (adică pornirea acestuia pentru unele complet). anumit timp) și fără trimitere - pauză (închiderea curentului în același timp); numai cu ajutorul acestor două semnale, puteți deja transmite orice mesaj, dacă sunteți de acord să înlocuiți fiecare literă sau număr o anumită combinație trimiteri de curent și pauze. În ingineria comunicațiilor, regula care asociază fiecare mesaj transmis cu o anumită combinație de semnale este de obicei numită cod (în cazul telegrafiei, un cod telegrafic), iar operația în sine de traducere a unui mesaj într-o secvență. semnale diferite- codificarea mesajelor. Un „cod” va fi înțeles ca un astfel de set de n desemnări de cod, corelate cu n litere ale alfabetului, pentru care este îndeplinită următoarea condiție: nicio desemnare de cod a unei litere nu coincide cu începutul oricărei alte denumiri de cod mai lungi, de exemplu. codurile trebuie să fie decodificate în mod unic. Cu toate acestea, codurile care folosesc doar două cipuri diferite (de exemplu, trimitere curent și pauză) sunt numite coduri binare. În unele seturi de telegraf, cu excepția simpla includereși oprind curentul, puteți, de asemenea, să-i inversați direcția. În acest caz, devine posibil, în loc de a trimite curent și pauze, să se utilizeze trimiterea curentului în două direcții diferite ca semnale principale sau să se utilizeze simultan trei semnale elementare diferite de aceeași durată - trimiterea curentului într-o singură direcție, trimiterea curentului în cealaltă direcție și pauză (această metodă de codificare se numește cod ternar). Sunt posibile și dispozitive telegrafice și mai complexe, în care trimiterile curentului diferă nu numai în direcție, ci și în puterea curentului; astfel avem posibilitatea de a mări și mai mult numărul de semnale elementare diferite. Creșterea numărului de semnale elementare diferite vă permite să faceți codul mai comprimat. Cu toate acestea, de asemenea, complică și crește costul sistemului de transmisie, astfel încât codurile de cip reduse sunt încă preferate în domeniu. Să fie un mesaj scris folosind un „alfabet” care conține n „litere”. Este necesar să „codăm” acest mesaj, adică. indicați o regulă care asociază fiecare astfel de mesaj cu o secvență specifică de m „cipuri” diferite care alcătuiesc „alfabetul” transmisiei. Vom considera codificarea cu cât mai profitabilă, cu atât mai puține semnale elementare trebuie cheltuite pentru transmiterea unui mesaj. Dacă presupunem că fiecare dintre semnalele elementare durează în același timp, atunci codul cel mai avantajos va permite cel mai mic timp să fie alocat transmiterii mesajelor. Proprietatea principală evenimente aleatorii este lipsa încrederii deplină în producerea lor, ceea ce creează o anumită incertitudine la efectuarea experimentelor legate de aceste evenimente. Cu toate acestea, este destul de clar că gradul acestei incertitudini în diferite cazuri va fi complet diferit. Pentru practică, este important să se poată estima numeric gradul de incertitudine al unei game largi de experimente pentru a le putea compara din această parte. Luați în considerare două experiențe independente și, precum și o experiență complexă constând din executare simultană experimente și. Lăsați experiența să aibă k rezultate echiprobabile, iar experiența să aibă l rezultate echiprobabile. Evident, incertitudinea experienței este mai mare decât incertitudinea experienței, deoarece aici la incertitudine se adaugă incertitudinea rezultatului experienței. Este firesc să presupunem că gradul de incertitudine al experienței este egal cu suma incertitudinilor care caracterizează experimentele, adică:. O singură funcție îndeplinește condițiile, când -:. Luați în considerare experimentul A, constând din experiențe și probabilități. Atunci va fi egală incertitudinea totală pentru experimentul A. Acest ultim număr va fi numit entropia experimentului și notat cu. Dacă numărul de litere din „alfabet” este egal cu n, iar numărul de semnale elementare utilizate este egal cu m, atunci pentru orice metodă de codare numărul mediu de semnale elementare pe o literă a alfabetului nu poate fi mai mic de; cu toate acestea, se poate face întotdeauna în mod arbitrar aproape de acest raport, dacă numai desemnările de cod individuale sunt imediat comparate cu „blocuri” suficient de lungi constând din un numar mare scrisori. Vom lua în considerare doar aici cel mai simplu caz mesaje scrise folosind câteva n „litere”, a căror frecvență de apariție în orice loc al mesajului este pe deplin caracterizată de probabilitățile p1, p2, ... ..., pn, unde, desigur, p1 + p2 + . .. + pn = 1, la care probabilitatea pi manifestări ale i-a se presupune că literele din orice loc al mesajului sunt aceleași, indiferent de ce litere au fost în toate locurile anterioare, adică literele consecutive ale mesajului sunt independente unele de altele. De fapt, în mesajele reale, acest lucru nu este adesea cazul; în special, în limba rusă, probabilitatea apariției unei anumite litere depinde în mod semnificativ de scrisoarea anterioară. Cu toate acestea, luarea în considerare strictă a dependenței reciproce a literelor ar face toate considerațiile ulterioare foarte dificile, dar nu va schimba în niciun fel rezultatele viitoare. Vom analiza codurile binare pentru moment; generalizarea rezultatelor obţinute în acest caz pentru coduri folosind număr arbitrar t semnalele elementare este, ca întotdeauna, extrem de simplă. Să începem cu cel mai simplu caz de coduri care asociază o desemnare de cod separată - o secvență de numere 0 și 1 - cu fiecare „litera” a unui mesaj. Fiecare cod binar pentru un alfabet n-alfabet poate fi asociat cu o metodă de ghicire a unui număr x ascuns, care să nu depășească n, folosind întrebări la care se răspunde doar „da” (1) sau „nu” (0), ceea ce ne conduce la codul binar. Pentru probabilitățile date p1, p2, ..., pn de litere individuale, transmiterea unui mesaj cu mai multe litere va fi codul cel mai economic pentru care, cu aceste probabilități n valori x, valoarea medie a numărului de întrebări întrebat (semne binare: 0 și 1 sau semnale elementare) se dovedește a fi cel mai mic. În primul rând, numărul mediu de semnale elementare binare din mesajul codificat pe o literă a mesajului original nu poate fi mai mic decât H, unde H = - p1 log p1 - p2 log p2 - ... - pn log pn este entropia a experienței constând în recunoașterea unei litere a textului (sau, pe scurt, doar entropia unei litere). Din aceasta rezultă imediat că pentru orice metodă de codare, pentru a scrie un mesaj lung de M litere, este necesar cel puțin MH de caractere binare și în niciun caz nu poate depăși un bit. Dacă probabilitățile p1, p2, ... ..., pn nu sunt toate egale între ele, atunci 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 по возможности с одинаковой вероятностью. Разумеется, количество цифр в denumiri diferiteîn acest caz, se dovedește a fi diferit (în special, în al doilea dintre exemplele analizate variază de la doi la șapte), adică codul Shannon - Fano este neuniform. Nu este greu de înțeles, totuși, că nicio desemnare de cod aici nu poate fi începutul unei alte desemnări mai lungi; prin urmare, mesajul codificat poate fi întotdeauna decodat fără ambiguitate. Ca rezultat, valoarea medie a lungimii unei astfel de denumiri se dovedește a fi încă doar puțin mai mare decât valoarea minimă a lui H permisă de considerentele de păstrare a cantității de informații în timpul codificării. Deci, pentru exemplul unui alfabet de 6 litere considerat mai sus, cel mai bun cod uniform constă din denumiri de cod din trei cifre (deoarece 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 Легко видеть, что из самого построения получаемого таким образом кода Хафмана вытекает, что он удовлетворяет starea generala: niciun semn de cod nu este aici începutul altui marcaj de cod mai lung. De asemenea, rețineți că codificarea unui anumit alfabet prin metoda Huffman (precum și prin metoda Shannon - Fano) nu este o procedură clară. Deci, de exemplu, în orice etapă a construirii codului, puteți, desigur, să înlocuiți numărul 1 cu numărul 0 și invers; cu asta obținem două coduri diferite(foarte nesemnificativ diferite unele de altele). Dar, în plus, în unele cazuri, este posibil să se construiască mai multe coduri Huffman semnificativ diferite; Deci, de exemplu, în exemplul dezasamblat mai sus, puteți construi un cod în conformitate cu următorul tabel: Numărul literei Probabilități alfabetul original Alfabete comprimate A1A2A3A410.4 110.4 110.4 11 0.4 00.6 120.2 010.2 010.2 010.2 010.2 010.40 .010.40 . 1000,1 1010,2 00 50,05 10110,1 100 60,05 1010 Tabelul 5 cod nou este, de asemenea, un cod Huffman, dar lungimile denumirilor de cod existente se dovedesc acum a fi complet diferite. Rețineți că numărul mediu de semnale elementare pe literă este exact același pentru ambele coduri Huffman construite: în primul caz, este egal, iar în al doilea, este egal. Se poate demonstra că codul Huffman este întotdeauna cel mai economic dintre toate posibil, în sensul că pentru nicio altă metodă de codificare a literelor dintr-un anumit alfabet, numărul mediu de semnale elementare pe literă poate fi mai mic decât cel obținut la codificarea de către Metoda Huffman (din aceasta, desigur, rezultă imediat că pentru oricare două coduri Huffman lungimea medie a desemnării codului trebuie să fie exact aceeași - la urma urmei, ambele sunt cele mai economice). Raționamentul prezentat în paragrafele 1.2 și 1.3 este pe deplin implementat la rezolvarea problemelor (un exemplu de astfel de problemă este dat în Anexa A). 2. Entropia unor tipuri specifice de mesaje. 2.1 Teorema principală despre codificare. Gradul de apropiere a numărului mediu de caractere binare pe o literă a mesajului față de valoarea lui H atinsă în exemplele considerate mai sus poate fi crescut și mai mult în mod arbitrar prin trecerea la codificarea blocurilor din ce în ce mai lungi. Aceasta rezultă din următoarea afirmație generală, pe care o vom numi în continuare teorema principală de codare, mai precis, teorema principală de codare în absența interferenței: la codificarea unui mesaj împărțit în blocuri de N litere, alegând N suficient de mare, putem realizați ca numărul mediu de cipuri binare pe literă a mesajului original să fie în mod arbitrar apropiat de H. Codificarea blocurilor lungi deodată are avantaje semnificative în prezența interferențelor care împiedică funcționarea liniei de comunicație. Având în vedere marea importanță a teoremei principale de codare formulată aici, prezentăm mai jos demonstrația acesteia bazată pe utilizarea metodei de codificare Shannon - Fano. În primul rând, să presupunem că prin metoda Shannon - Fano, care stă la baza împărțirii secvențiale a setului de litere codificate (prin care pot fi înțelese și „blocuri” întregi) în grupuri din ce în ce mai mici, de fiecare dată reușim să ne asigurăm că probabilitățile celor două grupuri rezultate sunt exact egale între ele... În acest caz, după prima diviziune, ajungem la grupuri cu o probabilitate totală de 1/2, după a doua - la grupuri cu o probabilitate totală de 1/4, ..., după a l-a diviziune - la grupuri cu o probabilitate totală de 1 / 2l. În acest caz, desemnarea codului cu l cifre va avea acele litere care se dovedesc a fi alocate într-un grup de un element exact după l diviziuni; cu alte cuvinte, dacă această condiție este îndeplinită, lungimea li a desemnării codului va fi raportată la probabilitatea pi a literei corespunzătoare prin formula B caz general cantitate - log pi, unde pi - probabilitatea i-a litera alfabetului nu va fi un întreg, deci lungimea li a codului notația i-a literele nu pot fi egale cu log pi. Deoarece atunci când codificăm prin metoda Shannon - Fano, împărțim secvenţial alfabetul nostru în grupuri cât mai apropiate de probabilitatea totală, lungimea desemnării codului literei i-a cu o astfel de codificare va fi apropiată de - log pi. În acest sens, notăm cu li primul număr întreg nu mai mic decât - log pi: (A) Ultima inegalitate poate fi rescrisă după cum urmează: sau (B) Aici observăm că în cazul oricăror n numere care satisfac inegalitatea, ( 1) există un cod binar pentru care aceste numere sunt lungimile denumirilor de cod asociate cu n litere ale unui anumit alfabet. Medie l semnale binare pe o literă a mesajului original (sau lungimea medie a desemnării codului) este dată de suma. Să înmulțim acum inegalitatea (A) care dă valoarea li cu pi, să adunăm toate inegalitățile obținute în acest fel corespunzătoare valorilor i = 1, 2, ..., n și să ținem cont de faptul că, unde este entropia experimentului constând în determinarea unei litere a mesajului, și că p1 + p2 + ... + pn = 1. Ca rezultat, obținem că. Să aplicăm această inegalitate în cazul în care metoda descrisă mai sus este folosită pentru a codifica toate blocurile posibile cu N litere (care pot fi considerate litere ale noului alfabet). În virtutea ipotezei despre independența literelor consecutive ale mesajului, entropia experimentului, care constă în determinarea tuturor literelor blocului, este. În consecință, lungimea medie lN a desemnării codului blocului cu N litere satisface inegalități Dar atunci când se codifică blocuri cu N litere simultan, numărul mediu l de semnale elementare binare pentru fiecare literă a mesajului va fi egal cu lungimea medie lN a desemnării codului unui bloc împărțit la numărul N litere din bloc. :. Prin urmare, cu o astfel de codificare, adică aici numărul mediu de semnale elementare pe literă diferă de valoarea minimă a lui H cu cel mult. Presupunând că ajungem imediat la teorema principală despre codificare. Dovada de mai sus poate fi aplicată și în cazul mai general în care literele succesive ale textului sunt reciproc dependente. În acest caz, trebuie doar să scrieți inegalitatea pentru valoarea lN în formă, unde este entropia blocului cu N litere, care în cazul dependenței literelor mesajului una de cealaltă va fi întotdeauna mai mică decât NH (pentru și). De aici rezultă că, prin urmare, în acest caz mai general (cu o creștere nelimitată a lungimii blocurilor) numărul mediu de semnale elementare cheltuite pentru transmiterea unei litere se apropie nelimitat de valoarea în care există „entropie specifică” pentru o literă dintr-un text cu mai multe litere. Existența unei limite rezultă din inegalitățile care arată că o secvență este o secvență monoton necrescătoare de numere pozitive (0 mari). Toate afirmațiile anterioare sunt ușor transferate în cazul codurilor t-are folosind t semnale elementare. Deci, pentru a construi coduri m-ary Shannon - Fano, trebuie doar să împărțiți grupurile de simboluri nu în două, ci în m părți cât mai apropiate posibil și pentru a construi codul t-ary Huffman, trebuie să folosiți operația de comprimarea alfabetului, în care de fiecare dată nu sunt îmbinate două, și m litere ale alfabetului original care au cele mai puține probabilități. Având în vedere importanța codurilor Huffman, să ne oprim puțin mai detaliat la ultima întrebare. Comprimarea alfabetului, în care m litere sunt înlocuite cu una, duce la o scădere a numărului de litere cu m - 1; întrucât pentru a construi un cod t-ary, evident, se cere ca succesiunea „contracțiilor” să ne conducă în cele din urmă la un alfabet de m litere (asociate cu m semnale ale codului), este necesar ca numărul n litere ale codului. alfabetul inițial poate fi reprezentat sub forma n = m + k (m - 1), unde k este un număr întreg. Acest lucru, însă, se poate realiza oricând prin adăugarea, dacă este necesar, la alfabetul original a câtorva „litere false”, ale căror probabilități sunt calculate. egal cu zero... După aceasta, construirea unui cod t-ary Huffman și dovada optimității acestuia (dintre toate codurile t-ary) se realizează exact în același mod ca și în cazul cod binar... Deci, de exemplu, în cazul alfabetului deja considerat mai sus de 6 litere, care au probabilități de 0,4, 0,2, 0,2, 0,1, 0,05 și 0,05 pentru construirea codului ternar Huffman, trebuie să adăugăm la alfabetul nostru încă o literă. de probabilitate zero și apoi procedați după cum urmează: Numărul de denumiri de litere și coduri de probabilitate alfabetul original alfabete comprimate 10.4 00.4 00.4 020.2 20.2 20.4 130.2 100.2 100.2 240, 1 110.1 110.1 110.1 11 11 15 20 24 24 la cazul codurilor t-are și la demonstrația de mai sus a teoremei principale de codare. În special, modificarea corespunzătoare se bazează pe faptul că orice n numere l1, l2, ..., în satisfacerea inegalității sunt lungimile denumirilor de cod ale unui cod t-ary pentru un alfabet cu n litere. Repetând raționamentul pentru cazul m = 2, se obține cu ușurință următorul rezultat (numit teorema principală de codare pentru codurile t-ary): pentru orice metodă de codare folosind un cod t-ary, numărul mediu de cipuri pe literă de mesaj nu poate fi niciodată mai mic decât raportul (unde H este entropia unei litere a mesajului); cu toate acestea, poate fi întotdeauna făcută în mod arbitrar aproape de această valoare dacă sunt codificate simultan „blocuri” suficient de lungi de N litere. Prin urmare, este clar că dacă L semnale elementare (luând m valori diferite) pot fi transmise pe o linie de comunicație pe unitate de timp, atunci viteza de transmitere a mesajelor pe o astfel de linie nu poate fi mai mare decât literele/unitatea. timp; cu toate acestea, transmisia la o viteză arbitrar apropiată de v (dar mai mică de v!) este deja posibilă. Valoarea în numărător a expresiei pentru v depinde doar de linia de comunicație în sine (în timp ce numitorul H caracterizează mesajul transmis). Această valoare indică cel mai mare număr unități de informații care pot fi transmise de-a lungul liniei noastre pe unitatea de timp (deoarece un semnal elementar, după cum știm, poate conține cel mult log m unități de informație); se numește lățimea de bandă a liniei de comunicație. Concept lățimea de bandă joacă rol important în teoria comunicării. 2.2 Entropie și informații despre tipuri specifice de mesaje. 2.2.1 Discursul scris Pentru a transmite un mesaj cu literă M care să permită m semnale elementare diferite, este necesar să se cheltuiască nu mai puțin de semnale, unde n este numărul de litere ale „alfabetului”. Deoarece alfabetul „telegrafic” rusesc conține 32 de litere. (literele e și e nu se disting, b și b, ci sunt numărate printre litere și „litera zero” este un spațiu gol între cuvinte), atunci semnalele elementare trebuie cheltuite pentru transmiterea unui mesaj cu literă M. Text rusesc, cu condiția ca toate literele să fie considerate la fel de probabile. Pentru a obține un text în care fiecare literă conține 5 biți de informații, trebuie să scrieți 32 de litere pe bilete separate, să puneți toate aceste bilete într-o urnă și apoi să le scoateți unul. câte unul, de fiecare dată notând scrisoarea alungită și returnând biletul înapoi la coșul de gunoi și amestecând din nou conținutul acestuia. După ce am făcut un astfel de experiment, ajungem la o „frază” ca următoarea: RYS Desigur, acest text are foarte puține în comun cu limba rusă! Pentru un calcul mai precis al informațiilor conținute într-o literă a textului rus, trebuie să cunoașteți probabilitățile de apariție a diferitelor litere. Valorile aproximative ale frecvenței literelor individuale ale limbii ruse sunt colectate în următorul tabel: relativă literă. frecvență - 0,175o 0,090e, d 0,072a 0,062 și 0,062t 0,053n 0,053s 0,045 literă relativă frecvență 0,040v 0,038l 0,035k 0,028m 0,026d 0,025p 0,023u 0,021 literă relativă frecvență 0,018y 0,016z 0,016b, b 0,014b 0,014g 0,013h 0,012y 0,010 literă relativă frecvențe 0.009zh 0.007yu 0.006sh 0.006ts 0.004sh 0.003e 0.003f 0.002 Dintr-o comparație a acestei valori cu valoarea Н0 = log 32 = 5 biți, se poate observa că aspectul neuniform al diferitelor litere ale alfabetului duce la o scădere a informațiilor conținute într-o literă a textului rusesc cu aproximativ 0,65 biți. . Reducerea numărului de semnale elementare necesare poate fi demonstrată prin codificarea literelor individuale ale alfabetului rus folosind metoda Shannon-Fano: cod alfabetic. codul literei de desemnare codul literei de desemnare obozn.111k01000h0000100a1010l01001ts00000010b000101m00111ch000011v01010n0111sh00000011g000100o110sch00000001d001101p001100y001000e, o1011r01011,00111t1000yu00000010i1001Tabelul 8 Numărul mediu de chips-uri în această metodă de codificare este aceeași, atunci va fi foarte aproape de valoarea în determinarea experimentul entropie a fost de a determina o literă textul rusesc, am considerat toate scrisorile independente . Aceasta înseamnă că pentru a alcătui un „text” în care fiecare literă să conțină un pic de informație, trebuie să apelăm la ajutorul unei urne, în care sunt amestecate cu grijă 1000 de bucăți de hârtie, dintre care 175 nu au nimic scris. , 90 - se scrie litera o, 72 - litera e, ..., în final, pe 2 bucăți de hârtie - litera f (vezi Tabelul 7). Extragând bucăți de hârtie dintr-o astfel de urnă una câte una, ajungem la o „expresie” ca următoarea: YYNT TSIYAA OERV ODNG YUEMLOLIK ZBYA ENVTSHA. Această „frază” este oarecum mai asemănătoare cu un discurs rusesc semnificativ decât precedentul, dar, desigur, este încă foarte departe de un text rezonabil. Deosebirea frazei noastre cu un text semnificativ se explică în mod firesc prin faptul că, de fapt, literele succesive ale textului rus nu sunt deloc independente unele de altele. Deci, de exemplu, dacă știm că o vocală este următoarea literă, atunci probabilitatea ca o literă consoanică să apară în locul următor crește semnificativ; litera „ь” nu poate în niciun caz să urmeze nici un spațiu, nici o vocală; literele „s”, „I” sau „u” nu pot apărea în spatele literei „h”, dar cel mai probabil va exista una dintre vocalele „și” și „e” sau consoana „t”, etc. Prezența în Limba rusă a regularităților suplimentare care nu este luată în considerare în „fraza” noastră duce la o scădere suplimentară a gradului de incertitudine a unei litere a textului rus. Pentru a face acest lucru, este necesar doar să se calculeze entropia condiționată a experimentului constând în determinarea unei litere a textului rusesc, cu condiția să cunoaștem rezultatul experimentului, care constă în determinarea literei precedente a aceluiași text. Entropia condiționată este determinată de următoarea formulă: unde p (-), p (a), p (b), ..., p (i) denotă probabilitățile (frecvențele) literelor individuale ale limbii ruse. Desigur, se poate spune dinainte că probabilitățile p (- -), p (nb) și multe altele (de exemplu, p (bb), p (- b), p (w), etc.) vor fi egal cu zero. Putem fi siguri că entropia condiționată va fi mai mică decât entropia necondiționată. Valoarea poate fi specificată ca „informația medie” conținută în determinarea rezultatului experienței următoare. Există 32 de urne, desemnate cu 32 de litere ale alfabetului rus; fiecare dintre urne conține bucăți de hârtie pe care sunt scrise combinații de două litere, începând cu litera indicată pe urnă, iar numărul de bucăți de hârtie cu perechi diferite de litere este proporțional cu frecvențele (probabilitățile) celor două corespunzătoare. -combinații de litere. Experiența constă în a scoate în mod repetat bucăți de hârtie din urne și a scrie ultima scrisoare din acestea. În acest caz, de fiecare dată (începând cu a doua), se scoate din urna o bucată de hârtie, care conține combinațiile care încep cu ultima literă scrisă; după ce scrisoarea este scrisă, bucata de hârtie este returnată în urnă, al cărei conținut este amestecat din nou bine. O experiență de acest fel duce la o „frază” ca următoarea: UMARONO KACH VANOZVANYE DOSYA NYKH CARPET NEDARE. Sunetul acestei „fraze” este mult mai apropiat de limba rusă. Cunoașterea celor două litere precedente reduce și mai mult incertitudinea experimentului constând în determinarea literei următoare, care se reflectă în pozitivitatea diferenței, unde este „entropia condiționată de ordinul doi”: fiecare dintre acestea conține bucăți de hârtie începând cu aceleași două litere (sau un experiment cu o carte rusă, în care prima repetare a ultimei combinații deja scrise de două litere se găsește la întâmplare de multe ori și litera care o urmează este scrisă) duce la o „expresie” ca următoarele: ÎN CÂT timp ce sudoarea ROCKERULUI NORMAL CUNOAȘTEREA ȚI-A BOTIT OBNIL, chiar mai aproape de vorbirea rusă decât cea anterioară. În mod similar, este posibil să se determine entropia corespunzătoare experienței de determinare a literei textului rusesc, cu condiția ca cele trei litere precedente să fie cunoscute. Constă în extragerea bucăților de hârtie din 323 de urne cu combinații de patru litere (sau - un experiment similar experimentului descris mai sus cu o carte rusească), duce la o „expresie” ca următoarea: FUN TO GATE NOT DRY AND NEPO ȘI CORKO, O aproximare și mai bună a entropiei unui text rusesc semnificativ este valorile la N = 5,6, .... Este ușor de observat că, cu o creștere a N, entropia HN poate doar să scadă. Dacă luăm în considerare și faptul că toate valorile HN sunt pozitive, atunci se va putea deduce din aceasta că valoarea la tinde către o anumită limită. Știm deja că numărul mediu de semnale elementare necesare pentru a transmite o literă a textului rus nu poate fi mai mic. Diferența care arată cât de mai mică decât unitatea este raportul dintre „entropia limită” și valoarea caracterizatoare cele mai multe informații, care poate fi cuprinsă într-o singură literă a alfabetului cu un număr dat de litere, Shannon a numit redundanța limbii. Redundanța limbii ruse (precum și redundanța altor limbi europene) depășește semnificativ 50%. Adică, putem spune că alegerea următoarei litere a unui text semnificativ este determinată în proporție de peste 50% de structura limbii în sine și, prin urmare, este aleatorie doar într-o măsură relativ mică. Redundanța lui R este o caracteristică statistică foarte importantă a unei limbi, dar valoarea sa numerică nu a fost încă determinată cu o acuratețe satisfăcătoare pentru nicio limbă. În ceea ce privește limba rusă, în special, există doar date despre valorile cantităților H2 și H3. Н0Н1Н2Н3log 32 = 54.353.523.01 (pentru a fi complet, am dat aici și valorile entropiei Н0 și Н1). Din aceasta se poate deduce doar că pentru limba rusă, de fapt, valoarea lui R este mult mai mare decât acest număr. Este clar că pentru toate limbile care folosesc alfabet latin, informația maximă Н0, care ar putea cădea pe o literă a textului, are aceeași semnificație: bit (26 de litere diferite ale alfabetului și a 27-a „litera” este un spațiu gol între cuvinte). Folosind tabelele de frecvențe relative ale diferitelor litere în engleză, germană, franceză și spaniolă, se poate demonstra că entropia H1 pentru aceste limbi este egală (în biți): limbă Germană Franceză Franceză Spaniolă Н14,034,103,963,98 Vedem că în toate cazurile, valoarea lui H1 este vizibil mai mică decât H0 = log 27 4,76 biți, iar valorile sale pentru limbi diferite nu sunt foarte diferite unele de altele. Valorile H2 și H3 pentru limba engleză au fost calculate de Shannon, în timp ce el a folosit tabelele de frecvență disponibile în engleză pentru diferite combinații de două și trei litere. Ținând cont și de statisticile privind frecvențele de apariție cuvinte diferiteîn engleză, Shannon a reușit să estimeze aproximativ valorile lui H5 și H8. Ca urmare, el a primit: Н0Н1 Н2Н3Н5Н84.764.03 3.323.10≈2.1≈1.9 Din aceasta putem concluziona că pentru limba engleză redundanța lui R este în orice caz nu mai mică decât, adică depășește 60%. Numărarea valorilor lui H9, H10 etc. conform formulei cunoscute nouă este imposibilă, deoarece calculul lui H9 necesită cunoașterea probabilităților tuturor combinațiilor de 9 litere, al căror număr este exprimat printr-un număr de 13 cifre. număr (trilioane!). Prin urmare, pentru a estima valorile HN la valori mari N trebuie să fie limitat metode indirecte... Să ne oprim asupra uneia dintre aceste metode propuse de Shannon. „Entropia condiționată” НN este o măsură a gradului de incertitudine al experienței, care constă în determinarea A N-a litera text, cu condiția ca literele N - 1 precedente să ne fie cunoscute. Un experiment de ghicire a celei de-a N-a litere poate fi configurat cu ușurință: pentru aceasta, este suficient să selectați un fragment (N - 1) -alfat dintr-un text semnificativ și să invitați pe cineva să ghicească următoarea literă. Un astfel de experiment poate fi repetat de mai multe ori, iar dificultatea de a ghici a N-a litere poate fi estimată folosind valoarea medie QN a numărului de încercări necesare pentru a găsi răspunsul corect. Este clar că cantitățile QN definite pentru sensuri diferite N, sunt anumite caracteristici ale structurii statistice a limbii, în special, redundanța acesteia. Shannon a efectuat o serie de experimente similare, în care N a preluat valorile 1, 2, 3, ..., 14, 15 și 100. Făcând acest lucru, a descoperit că ghicirea celei de-a 100-a litere de către 99 anterioare a fost o sarcină mult mai ușoară decât ghicirea celei de-a 15-a litere pe 14 anterioare. Prin urmare, putem concluziona că H15 este vizibil mai mare decât H100, adică că H15 nu poate fi încă identificat cu valoarea limită. Ulterior, aceleași experimente au fost efectuate pe un material puțin mai mare pentru N = 1, 2, 4, 8, 16, 32, 64, 128 și N ≈ 10.000. Н128) practic nu diferă de Н10000, în timp ce „entropia condiționată „Н16 este chiar vizibil mai mare decât această valoare. Astfel, se poate presupune că, cu o creștere a lui N, valoarea lui HN scade până la valorile de N = 30, dar cu o creștere suplimentară a N, practic nu se schimbă; prin urmare, în loc de „limitarea entropiei” se poate vorbi, de exemplu, de entropia condiționată H30 sau H40. Experimentele privind ghicirea literelor nu ne permit doar să judecăm valoare comparativă entropiile condiționate HN pentru N diferit, dar fac și posibilă separarea valorilor HN în sine. Conform datelor unor astfel de experimente, este posibil să se determine nu numai numărul mediu de încercări QN necesare pentru a ghici a N-a literă a textului prin N - 1 precedente, ci și probabilitatea (frecvența) ca litera să fie corectă. ghicit din a 1-a, 2-a, 3-a, ..., a-a încercare (unde n = 27 este numărul de litere ale alfabetului; QN =). Este ușor de înțeles că probabilitățile sunt egale cu probabilitățile literelor alfabetului, dispuse în ordinea descrescătoare a frecvenței. Într-adevăr, dacă nici una dintre literele care preced litera x care este ghicită nu ne este cunoscută, atunci este firesc în primul rând să presupunem că x coincide cu cea mai comună litera a1 (și probabilitatea de a ghici corect aici va fi egală cu p ( a1)); atunci ar trebui să presupunem că x coincide cu a2 (probabilitatea unui răspuns corect aici va fi egală cu p (a2)), și așa mai departe. Prin urmare, rezultă că entropia lui H1 este egală cu suma. Dacă N> 1, atunci se poate demonstra că suma (*) nu va depăși entropia condiționată HN (acest lucru se datorează faptului că valorile reprezintă într-un anumit fel probabilitățile medii ale rezultatelor experimentului) . Pe de altă parte, considerații ceva mai complicate, asupra cărora nu ne vom opri aici, ne permit să demonstrăm că suma (**) pentru orice N nu va fi mai mare decât entropia condiționată НN. Astfel, expresiile (*) și (**) (compuse din probabilități care pot fi estimate din datele experimentale) determină granițele între care ar trebui să se situeze valoarea HN. Trebuie doar să rețineți că ambele estimări (*) și (**) sunt obținute în ipoteza că acestea sunt probabilitățile de a ghici o literă din N - 1 litere anterioare din prima, a doua, a treia încercare etc. sunt obținute din ipoteza că ghicitorul numește întotdeauna următoarea literă cel mai eficient - luând în considerare pe deplin toate legile statistice a acestei limbi... În cazul în care experiente reale orice greșeli în strategia persoanei care ghiceste (adică diferențele dintre literele pe care le sună și cele care ar trebui denumite pe baza statisticilor exacte ale limbii) vor duce inevitabil la o supraestimare atât a sumelor (*) cât și a ( **); de aceea este recomandabil să luați în considerare doar datele „cel mai de succes ghicitor”, deoarece pentru el această supraestimare va fi cea mai mică. Deoarece fiecare persoană care ghicește greșește uneori, estimarea (**) în practică nu poate fi considerată o estimare inferioară complet fiabilă a entropiei adevărate (spre deosebire de estimarea superioară (*), care, din cauza erorilor ghicitorului, poate deveni doar chiar mai mare). În plus, valorile sumelor (*) și (**), din păcate, nu se apropie la infinit cu creșterea N (începând de la N ≈ 30, aceste sume încetează, în general, să mai depindă de N); prin urmare, estimările redundantei limbajului obținute pe această cale nu vor fi deosebit de precise. În special, experimentele lui Shannon au arătat doar că valoarea lui H100 pare să fie între 0,6 și 1,3 biți. Prin urmare, putem concluziona că redundanța pentru limba engleză în ordinea mărimii ar trebui să fie aproape de 80%. 2.2.2 Discurs oral. Ne întoarcem acum la problema entropiei și a informațiilor în vorbirea orală. Este firesc să credem că toate caracteristicile statistice ale unui astfel de discurs vor depinde și mai mult de alegerea oamenilor care vorbesc și de natura conversației lor. Valoarea redusă a entropiei vorbirii orale se poate datora faptului că într-o conversație folosim adesea mai multe repetări ale acelorași cuvinte și adesea adăugăm destul de multe cuvinte „în plus” - acest lucru se face atât pentru a facilita percepția vorbirii. , și pur și simplu pentru ca vorbitorul să aibă timp să se gândească la ce vrea să spună în continuare. După ce s-a determinat numărul mediu de litere pronunțate pe unitatea de timp, se poate estima aproximativ cantitatea de informații comunicate în timpul unei conversații în 1 secundă; este de obicei de ordinul a 5 până la 6 biți. Din conversație, putem judeca starea de spirit a vorbitorului și atitudinea acestuia față de cele spuse; putem recunoaște vorbitorul, chiar dacă nicio altă sursă de informare nu ni-l indică; putem determina în multe cazuri locul nașterii unui străin prin pronunția sa; putem estima volumul vorbirii orale, care în cazul transmisiei vocii printr-o linie de comunicație este în mare măsură determinată pur caracteristici tehnice linii de transmisie etc. Cuantificarea tuturor acestor informații este o sarcină foarte dificilă care necesită mult mai multe cunoștințe ale limbii. O excepție în acest sens este problema relativ restrânsă a accentuărilor logice care subliniază cuvintele individuale dintr-o frază. Accentul cade cel mai adesea pe cuvintele cele mai rar folosite (ceea ce, totuși, este destul de firesc - este clar că aproape nimeni nu va sublinia cel mai comun elefant cu un accent logic - de exemplu, prepoziții sau conjuncții). Dacă probabilitatea ca cuvânt dat Wr este sub stres, îl notăm cu qr, atunci informația medie, constând în informații despre prezența sau absența stresului pe acest cuvânt, va fi egală.Fie acum probabilitățile (frecvențele) tuturor cuvintelor W1, W2,. ... ., WK (aici K - numărul total toate cuvintele folosite. În acest caz, pentru informația medie H, cuprinsă într-o stres logic, se poate scrie următoarea formulă: Informația medie pe care o obținem aflând pe ce cuvinte se încadrează stresul logic este apropiată în ordinea mărimii de 0,65 biți/cuvânt. . În timpul unei conversații, literele individuale nu sunt niciodată pronunțate, dar sunt pronunțate sunete care sunt semnificativ diferite de litere. Prin urmare, elementul principal al vorbirii orale ar trebui considerat un sunet separat - un fonem. Limbajul vorbit semnificativ este alcătuit din foneme în același mod în care limbajul scris semnificativ este alcătuit din litere. Prin urmare, în toate cazurile în care ne interesează doar transmiterea de „informații semantice” a vorbirii orale cel mai mare interes reprezintă nu entropia și informațiile unei „litere rostite”, ci entropia și informațiile unui fonem pronunțat efectiv. Lista de foneme ale unei anumite limbi, desigur, nu coincide cu lista de litere ale alfabetului, deoarece aceeași literă în cazuri diferite poate suna diferit. Există 42 de foneme diferite în limba rusă și au numărat frecvențele fonemelor individuale (precum și diferite combinații două şi trei foneme consecutive). Н0 = log 42 al unui fonem, entropia de ordinul întâi (unde sunt frecvențele relative ale diferitelor foneme) și „entropia condiționată” Н2 și Н3: Н0Н1Н2Н3log 42 ≈ 5,38 4,77 3,62 0,70 Dacă comparăm aceste valori de Н0 , Н1, Н2, H3 pentru vorbirea rusă scrisă, atunci scăderea numărului de entropie condiționată pentru foneme are loc semnificativ mai rapid decât în cazul literelor din textul scris. Pentru a determina redundanța lui R (cuvinte), puteți stabili o relație între redundanțele vorbirii și scrisului. Din faptul că vorbirea orală poate fi înregistrată și scrisă – citită, rezultă că „informația completă” conținută într-un anumit text nu depinde de forma în care – oral sau scris – este prezentat acest text, adică . .. De aici rezultă că unde este numărul mediu de litere per fonem ("lungimea medie a fonemului"). Această valoare este o caracteristică statistică importantă a limbii care leagă vorbirea vorbită și cea scrisă. De asemenea, din ultima formulă rezultă că sau unde k este numărul total de foneme, iar n este numărul de litere; căci aici este mai firesc să iei. Cu toate acestea, utilizarea acestei formule este îngreunată de lipsa datelor statistice pentru a determina valoarea. 2.2.3 Muzica. Cercetări de același fel pot fi efectuate în ceea ce privește mesajele muzicale. Este firesc să credem că legăturile dintre sunetele succesive ale unei anumite melodii, exprimate prin semne de note individuale, sunt suficient de puternice: întrucât unele combinații de sunete vor fi mai armonioase decât altele, primele se vor găsi în operele muzicale mai des decât cele. din urmă. Dacă scriem o serie de note la întâmplare, atunci informațiile conținute în fiecare notă a acestei înregistrări vor fi cele mai mari; totuși, din punct de vedere muzical, o astfel de secvență haotică de note nu ar avea nicio valoare. Pentru a obține un sunet plăcut, este necesar să introducem o anumită redundanță în gama noastră; în același timp, se poate teme că în cazul unei redundanțe prea mari, în care notele ulterioare sunt determinate aproape fără ambiguitate de cele precedente, nu vom obține decât muzică extrem de monotonă și neinteresantă. Care este redundanța la care se poate obține muzica „bună”? Redundanţă melodii simple nimic mai puțin decât redundanța vorbirii cu sens. Ar fi necesar să se studieze în mod special problema redundanței diferitelor forme opere muzicale sau lucrări ale diverșilor compozitori. De exemplu, analizați un album popular de cântece pentru copii din punct de vedere al teoriei informației. Pentru simplitate, această lucrare a presupus că toate sunetele sunt într-o octavă; întrucât așa-numitele cromatisme nu au apărut în melodiile luate în considerare, toate aceste melodii puteau fi reduse la șapte sunete de bază; Do, re, mi, fa, sol, la și si, fiecare al optulea ca durată. Contabilitatea sunetelor cu o durată mai mare de o optime a fost efectuată prin adăugarea la cele șapte note a celui de al optulea „element principal” O, care denotă extinderea sunetului anterior pentru o altă perioadă de timp de o optime (sau o pauză de o optime). Astfel, „entropia maximă posibilă” H0 a unei note este aici egală cu H0 = log 8 = 3 biți. După ce am calculat frecvențele (probabilitățile) notelor individuale în toate cele 39 de melodii analizate, constatăm că folosind probabilitățile găsite de combinații a două note, putem calcula și entropia condiționată H2, aceasta se dovedește a fi aproape de 2,42. Numai din valorile H1 și H2, se poate spune foarte puțin despre gradul de redundanță al celor considerate, aparent, este vizibil mai mare decât. Această concluzie este susținută de cercetările multor autori cunoscuți. 2.2.4 Transfer imagini de televiziune... Ochiul nostru este capabil să distingă doar un număr finit de grade de luminozitate ale unei imagini și doar părți nu prea apropiate ale acesteia, prin urmare orice imagine poate fi transmisă „punct cu punct”, fiecare dintre acestea fiind un semnal care ia doar un număr finit. a valorilor. Este necesar să se țină seama de un număr semnificativ (câteva zeci) de gradații ale gradului de înnegrire („luminozitate”) fiecărui element, în plus, 25 de cadre sunt înlocuite pe ecranul televizorului în fiecare secundă, creând impresia de „mișcare”. ". Cu toate acestea, linia de comunicare de fapt nu transmite rezultatul experimentului, care constă în determinarea valorii schimbării continue de la un punct la altul, în timp, și a culorii sau luminozității imaginii, ci rezultatul unei complet diferite " experiment cuantizat”, constând în determinarea culorii (alb sau negru) sau a luminozității gradațiilor într-un număr finit de „puncte”. Această nouă experiență poate avea deja doar un număr finit de rezultate și îi putem măsura entropia H. Numărul total de elemente ("puncte") pentru televiziunea alb-negru, în care imaginea ar trebui să fie descompusă, este determinat în primul rând prin așa-numita „putere de rezoluție” a ochiului, adică capacitatea sa de a distinge zonele apropiate ale imaginii. În televiziunea modernă, acest număr este de obicei de ordinul a câteva sute de mii (în programele de televiziune sovietice, imaginea descompusă în 400.000 - 500.000 de elemente, în americană - cu aproximativ 200.000 - 300.000, în programele unor centre de televiziune franceze și belgiene - cu aproape 1.000.000)... Este ușor de înțeles că din acest motiv entropia unei imagini de televiziune este enormă. Chiar dacă presupunem că ochiul uman distinge doar 16 gradări diferite de luminozitate (valoarea este clar subestimată) și că imaginea este descompusă în doar 200.000 de elemente, atunci aflăm că „entropia de ordinul zero” aici este egală cu Н0 = log 16.200.000 = 800.000 de biți. Valoarea adevăratei entropie H, desigur, va fi mai mică, deoarece imaginea de televiziune are o redundanță semnificativă. Când am calculat valoarea lui H0, am presupus că valorile luminozității în oricare două „puncte” ale imaginii sunt independente unele de altele, în timp ce, de fapt, luminozitatea se schimbă de obicei foarte puțin atunci când mergeți la elemente învecinate aceeași imagine (sau chiar diferită, dar apropiată în timp). Semnificația vizuală a acestei redundanțe R este că, dintre cele 16.200.000 de combinații posibile ale valorilor de luminozitate în toate punctele ecranului, combinațiile semnificative care pot fi numite „imagini” vor constitui doar o parte neglijabilă, iar restul va fi complet dezordonat. colecție de puncte de luminozitate diferită.foarte departe de orice „tramă”. Între timp, „gradul de incertitudine” real H al imaginii de televiziune ar trebui să țină cont doar de acele combinații de valori de luminozitate care au cel puțin șanse de a fi transmise. Pentru a determina valoarea exactă a entropiei H (sau redundanței R) a unei imagini de televiziune, este necesar să se studieze în detaliu relațiile statistice dintre luminozitatea diferitelor puncte de pe ecran. Astfel, valorile entropiilor H0, H1, H2 și H3 au fost găsite pentru două imagini de televiziune specifice, dintre care prima (imaginea A - un parc cu copaci și clădiri) a fost mai complexă, iar a doua (imaginea B -). o galerie destul de întunecată cu trecători) era mai monocromatică după culoare și conținea mai puține detalii, în timp ce distingea 64 de gradații diferite de luminozitate ale unui element dintr-o imagine de televiziune, prin urmare entropia H0 (referită la un element și nu la întreaga imagine). ca un întreg) aici s-a dovedit a fi egal cu H0 = log 64 = 6 biți. Apoi, folosind un dispozitiv radio special, frecvențele (probabilitățile) relative ale tuturor gradațiilor de luminozitate distinse au fost calculate pentru ambele imagini luate în considerare și s-a determinat „entropia de ordinul întâi” a cărei prim element are o valoare a luminozității și al doilea j-e, precum și frecvențele relative pijk ale triplelor elementelor învecinate (tot numai pe orizontală), în care primul element avea valoarea i-e de luminozitate, al doilea j-e și a treia kth(numerele i, j și k au trecut prin toate valorile de la 1 la 64). Aceste frecvențe au făcut posibilă determinarea „entropiilor experimentelor complexe” și apoi a „entropiilor condiționate” și ultima în care s-a calculat însă doar pentru imaginea B. Rezultatele obținute sunt rezumate în următorul tabel: , 91.5 Redundanță R, estimat prin valoarea lui H2 pentru imaginea A este de 44%, iar pentru imaginea B - 68%; valoarea reală nu poate exista decât mai multă redundanță decât aceasta. În ceea ce privește entropia condiționată H3 pentru luminozitatea cunoscută a celor două elemente anterioare ale aceleiași linii, aceasta diferă relativ puțin de H2 (imaginea B, 75%); de aici putem concluziona că cunoaşterea luminozităţii celui mai apropiat element determină o parte foarte mare din redundanţa totală. O altă experiență care se bazează pe divizare are, de asemenea, un caracter similar. valori posibile luminozitatea unui element de imagine de televiziune cu 8, nu 64 de gradații, pentru care entropiile H0 și H1 și un număr de entropii condiționate H2, H3 și H4 ale unui element de imagine sunt calculate pentru următoarele patru parcele de televiziune sportivă: A - rulare rapidă baschetbalisti, B - fața unui prim-plan al unui spectator pe tribuna stadionului, C - panoramă a vederii spectatorilor de pe tribună și D - jucători de fotbal rapid. Vom nota cu cifrele 1 și 2 elementele de imagine adiacente datelor pe orizontală și pe verticală, cu numărul 3 - elementul adiacent în diagonală, cu numărul 4 - același cu cel în cauză, elementul de pe cadrul precedent al difuzarea televiziunii, cu numărul 5 - elementul de pe aceeași orizontală adiacent elementului 1, și, în final, numărul 6 - același element de pe cadrul premergător celui care conține elementul 4 (fig. 1), a) b) Fig. 1. și vom indica în notarea entropiilor condiționate de sus între paranteze numărul de imagini de elemente, al căror grad de luminozitate este considerat a fi cunoscut. În acest caz, valorile entropiei (în biți) pot fi rezumate în următorul tabel: A31,960,690,98-1,77B31,950,360.36 - B32,781,341,952,78-G32.45-2.002.08 A0. -0 , 56 - B0.35-0.270.26-B - 1.221.181.19G-1.83 --- Rezultatele ultimului experiment conduc la concluzia că pentru imaginea săracă în detalii ("față") redundanța nu este mai puțin de 90%, iar pentru o imagine bogată în detalii ("spectatori"), este de nu mai puțin de 60%. Motivele acestei discrepanțe sunt încă neclare. Pentru imaginile de televiziune color, informațiile sunt în ordinea mărimii comparabile cu informațiile dublate conținute în imaginea alb-negru corespunzătoare. CONCLUZIE În această lucrare au fost stabilite următoarele scopuri și obiective. Scop: studierea principiilor de codificare a informațiilor lui Shannon - Fano și Huffman și aplicarea acestora în rezolvarea problemelor. Obiectiv: studierea entropiei și redundanței unor tipuri specifice de mesaje pentru aplicarea ulterioară a principiilor lui Shannon - Fano și Huffman la acestea. După îndeplinirea scopurilor și obiectivelor teza s-au făcut următoarele concluzii. Înainte de apariția lucrărilor lui Shannon și Fano, codificarea caracterelor alfabetului la transmiterea unui mesaj prin canalele de comunicare se realiza cu același număr de biți, obținuți prin formula Hartley. Odată cu apariția acestor lucrări, au început să apară metode care codifică caractere cu un număr diferit de biți, în funcție de probabilitatea apariției lor în text, adică caracterele mai probabile sunt codificate cu coduri scurte, iar caracterele rare sunt codificate cu cele lungi (mai lungi decât media). De când D.A. Huffman și-a publicat lucrarea „Metoda pentru construirea de coduri cu redundanță minimă” în 1952, algoritmul său de codare a devenit baza pentru sumă uriașă cercetări ulterioare în acest domeniu. Este de remarcat faptul că peste 50 de ani de la data publicării, codul Huffman nu și-a pierdut deloc relevanța și semnificația. Așa că putem spune cu încredere că ne confruntăm cu el, într-o formă sau alta (adevărul este că codul Huffman este rareori folosit separat, lucrând mai des împreună cu alți algoritmi), aproape de fiecare dată când arhivăm fișiere, ne uităm la fotografii. , filme , trimiterea unui fax sau ascultarea muzicii. Avantajele acestor metode sunt ușurința lor evidentă de implementare și, în consecință, viteza mare codificare și decodare. Principalul dezavantaj este că nu sunt optime în cazul general. 3
Luați în considerare algoritmul pentru calcularea codurilor Shannon-Fano (pentru claritate, să luăm ca exemplu secvența „aa bbb cccc ddddd”). Pentru a calcula codurile, trebuie să creați un tabel cu simboluri unice pentru mesaje c (i)și probabilitățile lor p (c (i)), și sortați-l în ordinea necrescătoare a probabilității simbolului.
| c (i) | p (c (i)) |
| d | 5 / 17 |
| c | 4 / 17 |
| spaţiu | 3 / 17 |
| b | 3 / 17 |
| A | 2 / 17 |
În plus, tabelul de simboluri este împărțit în două grupuri, astfel încât fiecare dintre grupuri are aproximativ aceeași frecvență în suma simbolurilor. Primul grup este setat la începutul codului la „0”, al doilea la „1”. Pentru a calcula următorii biți ai codurilor de caractere, această procedură se repetă recursiv pentru fiecare grup care conține mai mult de un caracter. Astfel, pentru cazul nostru, obținem următoarele coduri de caractere:
Lungimea codului s (i)în tabelul rezultat este int (-lg p (c (i))), dacă sivolele ar putea fi împărțite în grupuri cu aceeasi frecventaîn caz contrar, lungimea codului este int (-lg p (c (i))) + 1.
39 de biți lungime. Având în vedere că originalul avea o lungime de 136 de biți, obținem un raport de compresie de ~ 28% - nu chiar atât de rău.
Privind secvența rezultată, apare întrebarea: „Cum poți decomprima asta acum?” Nu putem, ca și în cazul codificării, să înlocuim fiecare 8 biți ai fluxului de intrare cu un cod de lungime variabilă. Când decomprimăm, trebuie să facem opusul - înlocuiți codul cu lungime variabilă cu un caracter de 8 biți. V în acest caz, cel mai bine ar fi să folosiți un arbore binar, ale cărui frunze vor fi simboluri (analog arborelui Huffman).
Codarea Shannon-Fano este o metodă de compresie destul de veche, iar astăzi nu prezintă un interes practic deosebit (cu excepția unui exercițiu în cursul structurilor de date). În majoritatea cazurilor, lungimea secvenței comprimate, conform acestei metode, este egală cu lungimea secvenței comprimate folosind codarea Huffman. Dar pe unele secvențe, codurile Shannon-Fano neoptimale sunt încă formate, prin urmare, compresia prin metoda Huffman este considerată a fi mai eficientă. De exemplu, luați în considerare o secvență cu următorul conținut de caractere: "a" - 14, "b" - 7, "c" - 5, "d" - 5, "e" - 4. Metoda Huffman o comprimă la 77 de biți , dar Shannon-Fano până la 79 de biți.
|
Cum ne-am împărțit în grupuri? Destul de simplu:
Din cauza acestei ambiguități, unii chiar au astfel de gânduri: „... programul uneori atribuie unor simboluri...” și așa mai departe - raționând cu privire la lungimea codurilor. Dacă nu scrieți AI, atunci un astfel de lucru precum „programul uneori” face ceva sună ridicol. Un algoritm implementat corect funcționează într-o manieră strict definită.
Același mesaj poate fi codificat căi diferite... Cel mai avantajos cod este cel care petrece cel mai mic timp transmisiei mesajelor. Dacă transmiterea fiecărui element al caracterului (de exemplu, 0 sau 1) durează același timp, atunci codul optim va fi astfel încât atunci când este utilizat pentru a transmite un mesaj lungimea dată se va cheltui numărul minim de caractere elementare. Codurile Shannon - Fano sunt prefixe, adică Nu cuvânt de cod nu este un prefix al altuia. Această proprietate permite decodarea fără ambiguitate a oricărei secvențe de cuvinte de cod
Să luăm în considerare principiul construirii unuia dintre primii algoritmi de compresie, care a fost formulat de oamenii de știință americani Shannon și Fano folosind exemplul literelor alfabetului rus. Algoritmul folosește coduri de lungime variabilă, de ex. un caracter comun este codificat cu un cod de lungime mai scurtă, unul rar - un cod mai lung.
Pentru a compune un astfel de cod, evident, trebuie să cunoașteți frecvența de apariție a literelor în textul rus. Aceste frecvențe sunt prezentate în tabelul 1. Literele din tabel sunt aranjate în ordinea descrescătoare a frecvenței.
tabelul 1
Frecvența apariției literelor alfabetului rus
Folosind tabelul, puteți compune cel mai economic cod pe baza considerațiilor legate de informații. Evident, codul va fi cel mai economic atunci când fiecare caracter elementar va transmite informatii maxime... Considerați un simbol elementar (adică, reprezentând semnalul său) ca sistem fizic cu două stări posibile: 0 și 1. Informația pe care o dă acest simbol este egală cu entropia acestui sistem și este maximă în cazul în care ambele stări sunt la fel de probabile; în acest caz, simbolul elementar transmite informația 1 (binara). Prin urmare, baza pentru codificare optimă va fi cerința ca caracterele elementare din textul codificat să apară în medie la fel de des.
Ideea codificării este că caracterele codificate (litere sau combinații de litere) sunt împărțite în două grupuri aproximativ la fel de probabile: pentru primul grup de caractere, primul loc al combinației este 0 (primul caracter al numărului binar reprezentarea personajului); pentru al doilea grup - 1. În plus, fiecare grup este din nou împărțit în două subgrupuri aproximativ la fel de probabile; pentru simbolurile primului subgrup, 0 este pus pe locul doi; pentru al doilea subgrup - unul etc.
Să demonstrăm principiul construirii codului Shannon-Fano folosind exemplul materialului alfabetului rus (vezi Tabelul 1). Să numărăm primele șase litere (de la „-” la „t”); însumând probabilitățile (frecvențele) lor, obținem 0,498; toate celelalte litere de la „n” la „f” vor avea aproximativ aceeași probabilitate de 0,502. Primele șase litere (de la „-” la „t”) vor avea semnul binar în primul rând 0. Restul literelor (de la „n” la „f”) vor avea în primul rând 1. Mai departe, vom împărți din nou primul grup în două subgrupuri aproximativ la fel de probabile: de la „-” la „o” și de la „e” la „t”; pentru toate literele primului subgrup de pe locul doi punem zero, iar al doilea subgrup - unul. Vom continua procesul până când există exact o literă în fiecare subdiviziune, care va fi codificată într-o anumită număr binar... Mecanismul de construcție este prezentat în Tabelul 2, iar codul în sine este prezentat în Tabelul 3.
masa 2
Mecanismul de construire a codului Shannon - Fano pe exemplul alfabetului rus
| Semne binare | |||||||||
| Scrisori | 1 | al 2-lea | al 3-lea | al 4-lea | al 5-lea | al 6-lea | al 7-lea | al 8-lea | al 9-lea |
| - | |||||||||
| O | |||||||||
| e | |||||||||
| A | |||||||||
| și | |||||||||
| T | |||||||||
| n | |||||||||
| Cu | |||||||||
| R | |||||||||
| v | |||||||||
| l | |||||||||
| La | |||||||||
| m | |||||||||
| d | |||||||||
| P | |||||||||
| la | |||||||||
| eu sunt | |||||||||
| s | |||||||||
| s | |||||||||
| b, b | |||||||||
| b | |||||||||
| G | |||||||||
| h | |||||||||
| th | |||||||||
| X | |||||||||
| f | |||||||||
| Yu | |||||||||
| w | |||||||||
| c | |||||||||
| SCH | |||||||||
| eh | |||||||||
| f |
Tabelul 3
Rezultatul codificării literelor alfabetului rus cu codul Shannon - Fano
Exemplul 4. Să scriem expresia „metoda de codificare” folosind codul Shannon - Fano.
Soluţie: Să folosim tabelul 3 și să obținem următorul rezultat:
(1001) s (110011) n (001) o (1001) s (001) o (111010) b (000) spațiu
(10111) până la (001) o (110010) d (0110) și (10100) r (001) o (10101) c
(0101) a (1000) n (0110) și (110110) i
Rețineți că nu este nevoie să separați literele unele de altele cu un caracter special, deoarece chiar și fără această decodare se realizează fără ambiguitate datorită proprietății prefixului: niciun cuvânt de cod mai scurt nu este începutul unui cuvânt de cod mai lung. Într-adevăr, Tabelul 3 arată că cele mai scurte sunt codurile pentru caracterele „spațiu” și „o”. Mai mult, nici unul mai mult cod lung nu are 000 ("spațiu") și 001 ("o") la începutul secvenței. Același lucru poate fi observat pentru toate celelalte secvențe binare ale codului Shannon - Fano, care sunt prezentate în Tabelul 3.
Trebuie remarcat faptul că orice eroare de codare (amestecare accidentală a 0 sau 1 caractere) cu un astfel de cod este fatală, deoarece decodarea întregului text în urma erorii devine imposibilă.
Exemplul 5. Stabiliți dacă codul pe care l-am considerat este optim în absența erorilor?
Soluţie: Să găsim informația medie pentru un simbol elementar (0 sau 1) și să o comparăm cu maximul posibile informații, care este egal cu unu. Pentru a face acest lucru, găsim mai întâi informația medie conținută într-o literă a textului transmis, adică entropia pe literă (vezi formula 8):
Conform tabelului 1, determinăm numărul mediu de caractere elementare pe literă:
Astfel, informația pe caracter este foarte aproape de limita sa superioară de unu și codul dat foarte aproape de optim.
În cazul utilizării unui cod binar pe cinci biți, informații pe caracter:
Exemplul 6. Lăsați un mesaj (un cuvânt în rusă) să fie primit prin canalul de comunicare codificat cu codul Shannon-Fano: 10111001110010010010100.
Este necesar să decodați secvența dată.
Soluţie: Procesul de decodare se bazează pe proprietatea prefixului codului și se realizează de la stânga la dreapta. Tabelul 3 arată că lungimea minimă a codului este de trei biți. Va număra trei biți de la începutul cuvântului de cod primit, obținem - 101. Nu există un astfel de cod în tabel, așa că mai adăugăm un bit, obținem - 1011. Acest cod nu este, de asemenea, în tabel, prin urmare, acesta este necesar să adăugați încă un bit, obținem combinația - 10111, care corespunde literei „k”. Cuvântul de cod 10111 este exclus din cuvântul de cod primit și este înlocuit cu simbolul original (litera „k”). Procesul de decodare a restului literelor mesaj primit se desfășoară într-un mod similar.
Procesul complet de decodare este prezentat în Tabelul 4. Semnul „-” din tabel înseamnă că codul selectat este absent în Tabelul 3.
Tabelul 4
Procesul de decodare a mesajelor
| Secvența de cod primită | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| La | ||||||||||||||||||||||
| La | O | |||||||||||||||||||||
| La | O | - | ||||||||||||||||||||
| La | O | - | ||||||||||||||||||||
| La | O | - | ||||||||||||||||||||
| La | O | d | ||||||||||||||||||||
| La | O | d | - | |||||||||||||||||||
| La | O | d | e | |||||||||||||||||||
| La | O | d | e | - | ||||||||||||||||||
| La | O | d | e | - | ||||||||||||||||||
| La | O | d | e | R |
Deci, cuvântul obținut ca urmare a decodării cuvântului de cod primit este „encoder”.
Codificare optimă
Teorema de codificare a lui Shannon. Metode optime de codare literă cu literă. Criterii de optimizare pentru cod. Codare bloc. un singur sistem codificarea informațiilor text.
Codificarea,minimizând redundanța codului,se numeste optim.
Întrebarea existenței unor astfel de coduri este esența uneia dintre principalele teoreme ale teoriei informației - teorema de codificare demonstrată de K. Shannon. Iată una dintre formulările echivalente ale acestei teoreme.
Teorema de codificare. Mesaje ale unei surse arbitrare de informații Z cu entropie H(Z)poate fi întotdeauna codificat cu secvențe din alfabetul B,format din M caractere,Asa de,că lungimea medie a cuvântului de cod va fi în mod arbitrar apropiată de valoare 
,dar nu mai puțin decât ea.
Datorită complexității sale, demonstrarea acestei teoreme nu este luată în considerare.
Teorema afirmă că diferența poate fi făcută arbitrar de mică. Aceasta este sarcina metodelor optime de codare.
Să revenim la luarea în considerare a unei surse de informații alfabetice care generează mesaje în caractere alfabetice A... Deoarece redundanța codului este dată de formula
este evident că cu cât este mai puțin, cu atât este mai optim codul. Pentru scădere caracterele care apar frecvent ar trebui să fie codificate cu cuvinte mai scurte și invers. Toate metodele optime de codare se bazează pe această cerință. În plus, pentru a asigura decodarea unui cod neuniform, este important să se observe principiul prefixului: Niciun cuvânt de cod nu trebuie să fie începutul altui cuvânt de cod.
Iată două dintre cele mai cunoscute metode de codificare optimă literă cu literă. Pentru simplitate, luăm alfabet binar ca cod.
Pasul 1. Aranjam simbolurile alfabetului original în ordinea necreșterii probabilităților lor. (Le scriem într-un șir.)
Pasul 2. Fără a schimba ordinea simbolurilor, le împărțim în două grupe astfel încât probabilitățile totale ale simbolurilor din grupuri să fie cât mai egale.
Pasul 3. Atribuim grupului din stânga „0” și grupului din dreapta „1” ca elemente ale codurilor lor.
Pasul 4. Parcurgeți grupurile. Dacă numărul de elemente din grup este mai mare de unul, mergeți la Pasul 2. Dacă există un element în grup, construirea codului pentru acesta este completă.
Orez. 4.1. Arbore binar corespunzătoare codării Shannon - Fano
Luați în considerare funcționarea algoritmului descris folosind exemplul de codificare a alfabetului 
, ale căror simboluri apar cu probabilități (0,25; 0,05; 0,25; 0,1; 0,25; 0,1), respectiv. Rezultatul codificării este prezentat în Fig. 4.1.
Este evident că procesul de construire a codului în cazul general conține ambiguitate, deoarece nu putem împărți întotdeauna secvența în două submulțimi la fel de probabile. Fie în stânga, fie în dreapta, suma probabilităților va fi mai mare. Criteriul cel mai bun caz este redundanța codului mai mică. De asemenea, rețineți că citirea corectă a codului - de la rădăcina arborelui până la simbol - va asigura că acesta este prefixat.
