INTRODUZIONE Le nuove tendenze emerse in matematica nel ventesimo secolo di solito operano con concetti complessi e difficili da divulgare. In questo contesto, il merito dell'eminente matematico e ingegnere americano Claude Shannon, che nel 1947-1948, sulla base di considerazioni elementari, scoprì nuova area matematica - teoria dell'informazione. La spinta a creare nuova scienza erano puliti problemi tecnici trasmissione di informazioni tramite cavi telegrafici e telefonici, tuttavia, a causa della sua natura generale, la teoria dell'informazione è ora utilizzata nella ricerca relativa alla trasmissione e all'archiviazione di qualsiasi informazione in natura e tecnologia. Alla fine degli anni Quaranta, agli albori dello sviluppo della teoria dell'informazione, l'idea di svilupparne di nuovi modi efficaci le informazioni di codifica erano nell'aria. I ricercatori si sono occupati di problemi di entropia, contenuto informativo e ridondanza. Mi chiedo cosa questi lavori iniziali nel campo della compressione delle informazioni sono state effettuate prima dell'avvento del moderno computer digitale. Oggi, la teoria dell'informazione si sta sviluppando parallelamente alla programmazione, ma a quel tempo l'idea di sviluppare algoritmi utilizzando l'aritmetica binaria per codificare i caratteri era un significativo passo avanti. Gli algoritmi Shannon - Fano e Huffman sono stati uno dei primi algoritmi per la codifica efficiente delle informazioni. Questo documento considera concetti basilari entropia e informazione, e descrive anche i principi di codifica dei messaggi secondo Shannon - Fano e Huffman, mostra il loro ruolo importante nella trasmissione di informazioni sulle linee di comunicazione. Ma le linee di comunicazione per le quali sono stati sviluppati questi metodi di codifica delle informazioni sono già nel passato. Fortunatamente, i principi di Shannon-Fano e Huffman sono stati applicati in mondo moderno: per comprimere le informazioni. Archiver PKZIP, ARJ, nonché parte del noto standard JPEG (compressione informazioni grafiche con perdite) lavorano proprio su questi principi. I codici Shannon-Fano e Huffman sono insegnati in tutte le università tecniche del mondo e, inoltre, sono inclusi nel programma per lo studio avanzato dell'informatica a scuola. Pertanto, lo studio dei metodi di codifica Shannon - Fano e Huffman è rilevante. Lo scopo di questo lavoro è studiare i principi della codifica delle informazioni di Shannon - Fano e Huffman e la loro applicazione nella risoluzione dei problemi. Il compito è studiare l'entropia e la ridondanza di specifici tipi di messaggi per la successiva applicazione ad essi dei principi di Shannon-Fano e di Huffman. 1. Informazione e codifica. Codici Shannon - Fano e Huffman. 1.1 Informazioni e codifica. La parola "informazione" è nota a tutti nel nostro tempo. Deriva dal latino "informatio", che significa - chiarimento, messaggio, consapevolezza. Tuttavia, è entrato in uso costante non molto tempo fa, a metà del ventesimo secolo, su suggerimento di Claude Shannon. Ha introdotto questo termine in un senso tecnico ristretto in relazione alla teoria della comunicazione o trasmissione dei codici, che è stata chiamata "Teoria dell'informazione". Qui, non tutte le informazioni sono importanti, ma solo quelle che rimuovono o riducono completamente l'incertezza esistente. Una definizione filosofica, e quindi più ampia, di questo termine è data da uno dei fondatori dell'informatica, il famoso scienziato americano Norbert Wiener: "L'informazione è una designazione del contenuto che traiamo dal mondo esterno nel processo del nostro adattamento a esso e allineare il nostro pensiero con esso." Naturalmente, queste sono tutt'altro che definizioni univoche di informazione. Attualmente, questo termine ha un significato più profondo e sfaccettato. Rimanendo in gran parte intuitivo, riceve contenuti semantici diversi in diversi rami dell'attività umana: * nell'aspetto quotidiano, l'informazione è intesa come informazione sul mondo che lo circonda e sui processi che si svolgono in esso, percepiti da una persona o da dispositivi speciali; * in tecnologia, l'informazione è intesa come messaggi trasmessi sotto forma di segni o segnali; * nella teoria dell'informazione (secondo K. Shannon), non tutte le informazioni sono importanti, ma solo quelle che rimuovono o riducono completamente l'incertezza esistente; * nella teoria semantica (il significato di un messaggio) - questa è un'informazione che ha una novità, e così via ... Una tale varietà di approcci non è casuale, ma una conseguenza del fatto che la necessità di un'organizzazione consapevole del processi di movimento ed elaborazione di ciò che ha un nome comune - sono emerse informazioni. Per un'ulteriore considerazione, abbiamo bisogno del concetto di informazione, che implica la trasmissione di messaggi informativi su linee di comunicazione. Tenere conto schema generale trasmissione di messaggi; per determinatezza parleremo, ad esempio, di telegrafia. A un'estremità della linea, il mittente invia un messaggio, scritto utilizzando uno qualsiasi degli alfabeti o numeri a noi noti, o sia lettere che numeri combinati. Per trasmettere questo tipo di messaggi vengono utilizzate sequenze di segnali in corrente continua, alcune delle cui caratteristiche il telegrafista può variare a sua discrezione, percepite dal secondo telegrafista all'estremità ricevente della linea. Il più semplice segnale distinguibile, largamente utilizzato in pratica, è l'invio di una corrente (cioè l'accensione per alcuni completamente certo tempo) e nessun invio - pausa (spegnendo la corrente per lo stesso tempo); con l'aiuto di questi due soli segnali, puoi già trasmettere qualsiasi messaggio, se accetti di sostituire ogni lettera o numero una certa combinazione invii di corrente e pause. In ingegneria delle comunicazioni, la regola che associa ad ogni messaggio trasmesso una determinata combinazione di segnali è solitamente chiamata codice (nel caso della telegrafia, codice telegrafico), e l'operazione stessa di tradurre un messaggio in una sequenza segnali diversi- codifica dei messaggi. Un "codice" sarà inteso come un tale insieme di n designazioni di codice, abbinate a n lettere dell'alfabeto, per il quale è soddisfatta la seguente condizione: nessuna designazione di codice di una lettera coincide con l'inizio di qualsiasi altra designazione di codice più lunga, ad es. i codici devono essere decodificati in modo univoco. Tuttavia, i codici che utilizzano solo due chip diversi (ad esempio, invia corrente e pausa) sono chiamati codici binari. In alcuni telegrafi, eccetto semplice inclusione e togliendo la corrente, puoi anche invertire la sua direzione. In questo caso, diventa possibile, invece di inviare corrente e pause, utilizzare l'invio di corrente in due direzioni diverse come segnali principali, oppure utilizzare tre diversi segnali elementari della stessa durata contemporaneamente - inviare corrente in una direzione, invio di corrente nell'altra direzione e pausa (questo metodo di codifica è chiamato codice ternario). Sono possibili anche dispositivi telegrafici anche più complessi, in cui le trasmissioni della corrente differiscono non solo nella direzione, ma anche nell'intensità della corrente; così abbiamo l'opportunità di aumentare ulteriormente il numero dei diversi segnali elementari. L'aumento del numero dei diversi segnali elementari permette di rendere il codice più compresso. Tuttavia, complica e aumenta anche il costo del sistema di trasmissione, per cui nell'arte sono ancora preferiti codici a basso chip. Ci sia un messaggio scritto usando un "alfabeto" contenente n "lettere". È necessario "codificare" questo messaggio, ad es. indicare una regola che associa a ciascuno di tali messaggi una sequenza specifica di m diversi "chip" che compongono l'"alfabeto" della trasmissione. Considereremo la codifica più redditizia, meno segnali elementari devono essere spesi per trasmettere un messaggio. Se assumiamo che ciascuno dei segnali elementari duri lo stesso tempo, il codice più vantaggioso consentirà di dedicare il minor tempo alla trasmissione del messaggio. La proprietà principale eventi casualiè la mancanza di completa fiducia nel loro verificarsi, che crea una certa incertezza durante l'esecuzione di esperimenti relativi a questi eventi. Tuttavia, è abbastanza chiaro che il grado di questa incertezza nei diversi casi sarà completamente diverso. Per la pratica, è importante essere in grado di stimare numericamente il grado di incertezza di un'ampia varietà di esperimenti per poterli confrontare da questo lato. Considera due esperienze indipendenti e un'esperienza complessa composta da esecuzione simultanea esperimenti e. Lascia che l'esperienza abbia k esiti equiprobabili e che l'esperienza abbia l esiti equiprobabili. Ovviamente, l'incertezza dell'esperienza è maggiore dell'incertezza dell'esperienza, poiché qui all'incertezza si aggiunge l'incertezza dell'esito dell'esperienza. È naturale supporre che il grado di incertezza dell'esperienza sia pari alla somma delle incertezze che caratterizzano gli esperimenti, ovvero:. Solo una funzione soddisfa le condizioni, quando -:. Consideriamo l'esperimento A, consistente in esperienze e con probabilità. Allora l'incertezza totale per l'esperimento A sarà uguale Quest'ultimo numero sarà chiamato l'entropia dell'esperimento e denotato con. Se il numero di lettere nell'"alfabeto" è uguale a n e il numero di segnali elementari utilizzati è uguale a m, allora per qualsiasi metodo di codifica il numero medio di segnali elementari per una lettera dell'alfabeto non può essere inferiore a; tuttavia, può sempre essere arbitrariamente avvicinato a questo rapporto, se solo le singole designazioni di codice vengono immediatamente confrontate con "blocchi" sufficientemente lunghi costituiti da un largo numero lettere. Considereremo solo qui caso più semplice messaggi scritti utilizzando alcune n "lettere", la cui frequenza di manifestazione in qualsiasi punto del messaggio è pienamente caratterizzata dalle probabilità p1, p2, ... ..., pn, dove, ovviamente, p1 + p2 + ... + pn = 1, alla quale la probabilità pi manifestazioni dell'i-th si presume che le lettere in qualsiasi punto del messaggio siano le stesse, indipendentemente da quali lettere si trovassero in tutti i punti precedenti, ad es. le lettere consecutive del messaggio sono indipendenti l'una dall'altra. In effetti, nei messaggi reali spesso non è così; in particolare, nella lingua russa, la probabilità della comparsa di una particolare lettera dipende in modo significativo dalla lettera precedente. Tuttavia, una rigorosa considerazione della reciproca dipendenza delle lettere renderebbe molto difficili tutte le ulteriori considerazioni, ma non modificherebbe in alcun modo i risultati futuri. Per ora esamineremo i codici binari; generalizzazione dei risultati ottenuti in questo caso per codici che utilizzano numero arbitrario t segnali elementari è, come sempre, estremamente semplice. Iniziamo con il caso più semplice di codici che associano una designazione di codice separata - una sequenza di numeri 0 e 1 - a ciascuna "lettera" di un messaggio. Ogni codice binario per un alfabeto n-alfabetico può essere associato a un metodo per indovinare un numero nascosto x, non superiore a n, utilizzando domande a cui si risponde solo "sì" (1) o "no" (0), il che ci porta al codice binario. Per date probabilità p1, p2, ..., pn di singole lettere, la trasmissione di un messaggio multilettera sarà il codice più economico per il quale, con queste probabilità n valori x, il valore medio del numero di domande chiesto (segni binari: 0 e 1 o segnali elementari ) risulta essere il più piccolo. Innanzitutto, il numero medio di segnali binari elementari nel messaggio codificato per una lettera del messaggio originale non può essere inferiore a H, dove H = - p1 log p1 - p2 log p2 - ... - pn log pn è l'entropia dell'esperienza consistente nel riconoscimento di una lettera del testo (o, in breve, solo dell'entropia di una lettera). Da ciò segue immediatamente che per qualsiasi metodo di codifica, per scrivere un messaggio lungo di M lettere, sono necessari almeno MH di caratteri binari, e in nessun modo può superare un bit. Se le probabilità p1, p2, ... ..., pn non sono tutte uguali tra loro, allora 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 по возможности с одинаковой вероятностью. Разумеется, количество цифр в designazioni diverse in questo caso risulta diverso (in particolare, nel secondo degli esempi analizzati varia da due a sette), ovvero il codice Shannon - Fano è non uniforme. Non è difficile capire, tuttavia, che nessuna designazione di codice qui può essere l'inizio di un'altra designazione più lunga; pertanto, il messaggio codificato può sempre essere decodificato in modo univoco. Di conseguenza, il valore medio della lunghezza di tale designazione risulta ancora solo leggermente superiore al valore minimo di H consentito da considerazioni sulla conservazione della quantità di informazioni durante la codifica. Quindi, per l'esempio di un alfabeto di 6 lettere considerato sopra, il miglior codice uniforme è costituito da designazioni di codice a tre cifre (perché 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 Легко видеть, что из самого построения получаемого таким образом кода Хафмана вытекает, что он удовлетворяет condizione generale: nessun segno di codice è qui l'inizio di un altro segno di codice più lungo. Nota anche che la codifica di un certo alfabeto con il metodo Huffman (oltre che con il metodo Shannon - Fano) non è una procedura univoca. Quindi, ad esempio, in qualsiasi fase della costruzione del codice, puoi, ovviamente, sostituire il numero 1 con il numero 0 e viceversa; con questo otteniamo due codici diversi(molto insignificantemente diversi l'uno dall'altro). Ma in aggiunta, in alcuni casi, è possibile costruire diversi codici di Huffman significativamente differenti; Quindi, ad esempio, nell'esempio smontato sopra, puoi costruire un codice secondo la seguente tabella: Numero di lettere Probabilità alfabeto originale Alfabeti compressi A1A2A3A410.4 110,4 110,4 11 0,4 00.6 120,2 010.2 010.2 100,4 11 0,4 030.2 000.2 000.2 010.2 10 40.1 1000.1 1010.2 00 50.05 10110.1 100 60.05 1010 Tabella 5 nuovo codice è anche un codice Huffman, ma le lunghezze delle designazioni di codice esistenti ora risultano essere completamente diverse. Si noti che il numero medio di segnali elementari per lettera è esattamente lo stesso per entrambi i codici di Huffman costruiti: nel primo caso è uguale e nel secondo è uguale. Si può dimostrare che il codice di Huffman è sempre il più economico di tutti possibile, nel senso che per nessun altro metodo di codifica delle lettere di un certo alfabeto, il numero medio di segnali elementari per lettera può essere inferiore a quello ottenuto durante la codifica dal Metodo Huffman (da questo, ovviamente, segue immediatamente che per due codici Huffman qualsiasi la lunghezza media della designazione del codice deve essere esattamente la stessa - dopotutto, entrambi sono i più economici). Il ragionamento fornito nei paragrafi 1.2 e 1.3 è pienamente implementato quando si risolvono problemi (un esempio di tale problema è fornito nell'Appendice A). 2. Entropia di specifici tipi di messaggi. 2.1 Il teorema principale sulla codifica. Il grado di vicinanza del numero medio di caratteri binari per una lettera del messaggio al valore di H raggiunto negli esempi sopra considerati può essere ulteriormente aumentato arbitrariamente passando alla codifica di blocchi sempre più lunghi. Ciò deriva dalla seguente affermazione generale, che chiameremo ulteriormente teorema di codifica principale, più precisamente, teorema di codifica principale in assenza di interferenza: quando si codifica un messaggio suddiviso in blocchi di N lettere, scegliendo N abbastanza grande, possiamo ottenere che il numero medio di chip binari per lettera del messaggio originale fosse arbitrariamente vicino a H. La codifica di blocchi lunghi contemporaneamente presenta vantaggi significativi in presenza di interferenze che impediscono il funzionamento della linea di comunicazione. Data la grande importanza del principale teorema di codifica qui formulato, ne presentiamo di seguito la dimostrazione basata sull'utilizzo del metodo di codifica Shannon - Fano. Innanzitutto, supponiamo che con il metodo Shannon - Fano, che sta alla base della divisione sequenziale dell'insieme di lettere codificate (con cui si possono intendere anche interi "blocchi") in gruppi sempre più piccoli, si riesca ogni volta a far sì che le probabilità dei due gruppi risultanti sono esattamente uguali tra loro ... In questo caso, dopo la prima divisione, arriviamo a gruppi con una probabilità totale di 1/2, dopo la seconda - a gruppi con una probabilità totale di 1/4, ..., dopo la l-esima divisione - a gruppi con una probabilità totale di 1/2l. In questo caso, la designazione del codice l-digit avrà quelle lettere che risultano allocate in un gruppo di un elemento esattamente dopo l divisioni; in altre parole, se questa condizione è soddisfatta, la lunghezza li della designazione del codice sarà rapportata alla probabilità pi della lettera corrispondente dalla formula B caso generale quantità - log pi, dove pi - probabilità di i-th la lettera dell'alfabeto, non sarà un intero, quindi la lunghezza li del codice i-esima notazione le lettere non possono essere uguali a log pi. Poiché durante la codifica con il metodo Shannon - Fano, dividiamo in sequenza il nostro alfabeto in gruppi il più vicino possibile alla probabilità totale, la lunghezza della designazione del codice della i-esima lettera con tale codifica sarà vicina a - log pi. A questo proposito, indichiamo con li il primo intero non minore di - log pi: (A) L'ultima disuguaglianza può essere riscritta come segue: oppure (B) Qui notiamo che nel caso di n numeri che soddisfano la disuguaglianza, ( 1) esiste un codice binario per cui questi numeri sono le lunghezze delle designazioni di codice associate a n lettere di un certo alfabeto. l . medio segnali binari per una lettera del messaggio originale (o, la lunghezza media della designazione del codice) è data dalla somma. Moltiplichiamo ora la disuguaglianza (A) dando il valore li per pi, sommiamo tutte le disuguaglianze così ottenute corrispondenti ai valori i = 1, 2, ..., n, e teniamo conto che, dove è l'entropia dell'esperimento consistente nel determinare una lettera del messaggio, e che p1 + p2 + ... + pn = 1. Di conseguenza, lo otteniamo. Applichiamo questa disuguaglianza al caso in cui il metodo sopra descritto viene utilizzato per codificare tutti i possibili blocchi di N-lettere (che possono essere considerati lettere del nuovo alfabeto). In virtù del presupposto dell'indipendenza delle lettere consecutive del messaggio, l'entropia dell'esperimento, che consiste nel determinare tutte le lettere del blocco, è Di conseguenza, la lunghezza media lN della designazione di codice del blocco di N lettere soddisfa la disuguaglianze Ma quando si codificano blocchi di N lettere contemporaneamente, il numero medio l di segnali elementari binari per una lettera del messaggio sarà uguale alla lunghezza media lN della designazione del codice di un blocco diviso per il numero di N lettere nel blocco :. Pertanto, con tale codifica, cioè qui il numero medio di segnali elementari per lettera differisce dal valore minimo di H di non più di. Supponendo, arriviamo subito al teorema principale sulla codifica. La prova di cui sopra può essere applicata anche al caso più generale in cui lettere successive del testo sono mutuamente dipendenti. In questo caso, è solo necessario scrivere la disuguaglianza per il valore lN nella forma, dove è l'entropia del blocco di N lettere, che nel caso di dipendenza delle lettere del messaggio l'una dall'altra sarà sempre inferiore di NH (per e). Ne consegue che, quindi, in questo caso più generale (con un aumento illimitato della lunghezza dei blocchi), il numero medio di segnali elementari spesi per la trasmissione di una lettera, si avvicina illimitatamente al valore dove c'è "entropia specifica" per una lettera di un testo composto da più lettere. L'esistenza di un limite deriva dalle disuguaglianze che mostrano che una sequenza è una sequenza monotona non crescente di numeri positivi (grande 0). Tutte le precedenti affermazioni sono facilmente trasferibili al caso di codici t-ary che utilizzano segnali t elementari. Quindi, per costruire codici m-ary Shannon - Fano, basta dividere i gruppi di simboli non in due, ma in m parti il più vicino possibile, e per costruire il codice t-ary Huffman, si deve usare l'operazione di comprimendo l'alfabeto, in cui ogni volta non due vengono fusi, e m lettere dell'alfabeto originale che hanno le minori probabilità. Vista l'importanza dei codici di Huffman, soffermiamoci un po' più in dettaglio sull'ultima domanda. La compressione dell'alfabeto, in cui m lettere sono sostituite da una, porta a una diminuzione del numero di lettere di m - 1; poiché per costruire un codice t-ary, ovviamente, è necessario che la sequenza delle "contrazioni" alla fine ci porti ad un alfabeto di m lettere (associate a m segnali del codice), è necessario che il numero n lettere del alfabeto iniziale essere rappresentabile nella forma n = m + k (m - 1), dove k è un numero intero. Ciò, tuttavia, può sempre essere ottenuto aggiungendo, se necessario, all'alfabeto originale alcune "lettere fittizie" in più, le cui probabilità sono calcolate uguale a zero... Successivamente, la costruzione di un codice t-ary Huffman e la prova della sua ottimalità (tra tutti i codici t-ary) vengono eseguiti esattamente come nel caso codice binario... Quindi, ad esempio, nel caso dell'alfabeto già considerato sopra di 6 lettere, che hanno probabilità di 0.4, 0.2, 0.2, 0.1, 0.05, e 0.05 per costruire il codice ternario di Huffman, dobbiamo aggiungere al nostro alfabeto una lettera in più di probabilità zero e quindi procedere come segue: Numero di probabilità lettere e codici alfabeto originale alfabeti compressi 10,4 00,4 00.4 020,2 20,2 20,4 130,2 100,2 100,2 240, 1 110,1 11 50,05 1200,1 12 60,05 121 70 - Tabella 6 È altrettanto facile da trasportare oltre al caso dei codici t-ary e alla dimostrazione precedente del teorema di codificazione principale. In particolare, la modifica corrispondente si basa sul fatto che qualsiasi n numeri l1, l2, ..., ln che soddisfa la disuguaglianza sono le lunghezze delle designazioni di codice di un codice t-ary per un alfabeto di n lettere. Ripetendo il ragionamento per il caso m = 2, è facile ottenere il seguente risultato (chiamato teorema di codifica principale per codici t-ary): per qualsiasi metodo di codifica che utilizza un codice t-ary, il numero medio di chip per lettera di messaggio non può mai essere inferiore al rapporto (dove H è l'entropia di una lettera del messaggio); tuttavia, può sempre essere arbitrariamente avvicinato a questo valore se vengono codificati contemporaneamente "blocchi" di N lettere sufficientemente lunghi. Quindi, è chiaro che se L segnali elementari (che assumono m valori diversi) possono essere trasmessi su una linea di comunicazione per unità di tempo, allora la velocità di trasmissione del messaggio su tale linea non può essere maggiore di lettere / unità. volta; tuttavia, è già possibile la trasmissione ad una velocità arbitrariamente prossima a v (ma inferiore a v!). Il valore al numeratore dell'espressione per v dipende solo dalla linea di comunicazione stessa (mentre il denominatore H caratterizza il messaggio trasmesso). Questo valore indica il numero più grande unità di informazione che possono essere trasmesse lungo la nostra linea per unità di tempo (perché un segnale elementare, come sappiamo, può contenere al massimo log m unità di informazione); si chiama larghezza di banda della linea di comunicazione. Concetto larghezza di banda suona ruolo importante nella teoria della comunicazione. 2.2 Entropia e informazioni su specifici tipi di messaggio. 2.2.1 Discorso scritto Per trasmettere un messaggio di lettera M che consente m diversi segnali elementari, è necessario spendere non meno di segnali, dove n è il numero di lettere dell '"alfabeto. Poiché l'alfabeto "telegrafico" russo contiene 32 lettere (le lettere e ed e non sono distinte, b e b, ma sono contate tra le lettere e la "lettera zero" è uno spazio vuoto tra le parole), quindi i segnali elementari devono essere spesi per la trasmissione di un messaggio di lettera M. Testo russo, a condizione che tutte le lettere siano considerate ugualmente probabili. Per ottenere un testo in cui ogni lettera contenga 5 bit di informazione, è necessario scrivere 32 lettere su biglietti separati, mettere tutti questi biglietti in un'urna e poi tirarli fuori uno per uno, annotando ogni volta la lettera allungata, e rimettendo il biglietto nel cestino e mescolando di nuovo il suo contenuto.Fatto un tale esperimento, arriviamo a una "frase" come la seguente: RYS Certo, questo testo ha ben poco in comune con la lingua russa! Per un calcolo più accurato delle informazioni contenute in una lettera del testo russo, è necessario conoscere le probabilità di comparsa di lettere diverse. I valori approssimativi delle frequenze delle singole lettere della lingua russa sono raccolti nella seguente tabella: lettera relativa. frequenza - 0,175o 0,090e, d 0,072a 0,062 e 0,062t 0,053n 0,053s 0,045 lettera relativa frequenza 0,040v 0,038l 0,035k 0,028m 0,026d 0,025p 0,023u 0,021 lettera relativa frequenza 0,018y 0,016z 0,016b, b 0,014b 0,014g 0,013h 0,012y 0,010 lettera relativa frequenze 0.009zh 0.007yu 0.006sh 0.006ts 0.004sh 0.003e 0.003f 0.002 Da un confronto di questo valore con il valore Н0 = log 32 = 5 bit, si può notare che l'aspetto irregolare di varie lettere dell'alfabeto porta ad una diminuzione delle informazioni contenute in una lettera del testo russo di circa 0,65 bit . La riduzione del numero di segnali elementari richiesti può essere mostrata codificando singole lettere dell'alfabeto russo utilizzando il metodo Shannon-Fano: codice alfabetico. codice lettera designatore codice lettera designatore obozn.111k01000h0000100a1010l01001ts00000010b000101m00111ch000011v01010n0111sh00000011g000100o110sch00000001d001101p001100y001000e, o1011r01011,00111t1000yu00000010i1001Tabella 8 Numero medio di patatine fritte in questo metodo di codifica è lo stesso, allora non ci sarà molto vicino al valore nel determinare l'esperimento entropia è stato quello di determinare il testo russo una lettera, abbiamo preso in considerazione tutte le lettere indipendenti . Ciò significa che per comporre un "testo" in cui ogni lettera contenga un po' di informazione, dobbiamo ricorrere all'aiuto di un'urna, nella quale sono mescolati con cura 1000 fogli, 175 dei quali non hanno scritto nulla , 90 - la lettera o è scritta, 72 - la lettera e, ..., infine, su 2 pezzi di carta - la lettera f (vedi Tabella 7). Estraendo pezzi di carta da tale urna uno per uno, arriviamo a una "frase" come la seguente: YYNT TSIYAA OERV ODNG YUEMLOLIK ZBYA ENVTSHA. Questa "frase" è in qualche modo più simile a un discorso russo significativo rispetto al precedente, ma è, ovviamente, ancora molto lontana da un testo ragionevole. La dissomiglianza della nostra frase con un testo significativo è naturalmente spiegata dal fatto che, in effetti, le lettere successive del testo russo non sono affatto indipendenti l'una dall'altra. Quindi, ad esempio, se sappiamo che una vocale è la lettera successiva, la probabilità che una consonante appaia nel posto successivo aumenta in modo significativo; la lettera "ь" non può in alcun modo seguire né uno spazio né una vocale; le lettere "s", "I" o "u" non possono comparire dietro la lettera "h", ma molto probabilmente ci sarà una delle vocali "and" ed "e" o la consonante "t", ecc. Presenza in Russo la lingua delle regolarità aggiuntive non prese in considerazione nella nostra "frase" porta ad un'ulteriore diminuzione del grado di incertezza di una lettera del testo russo. Per fare ciò, è sufficiente calcolare l'entropia condizionale dell'esperimento consistente nel determinare una lettera del testo russo, a patto di conoscere l'esito dell'esperimento, che consiste nel determinare la lettera precedente dello stesso testo. L'entropia condizionale è determinata dalla seguente formula: dove p (-), p (a), p (b), ..., p (i) indicano le probabilità (frequenze) delle singole lettere della lingua russa. Certo, si può dire in anticipo che le probabilità p (- -), p (nb) e molte altre (ad esempio p (bb), p (- b), p (w), ecc.) saranno uguale a zero. Possiamo essere sicuri che l'entropia condizionata sarà minore dell'entropia incondizionata. Il valore può essere specificato come "informazione media" contenuta nel determinare l'esito dell'esperienza successiva. Ci sono 32 urne, designate da 32 lettere dell'alfabeto russo; ciascuna delle urne contiene fogli su cui sono scritte combinazioni di due lettere, a partire dalla lettera indicata sull'urna, e il numero di fogli con diverse coppie di lettere è proporzionale alle frequenze (probabilità) dei due corrispondenti -combinazioni di lettere. L'esperienza consiste nel rimuovere ripetutamente pezzi di carta dalle urne e trascriverne l'ultima lettera. In questo caso, ogni volta (a partire dalla seconda), si toglie dall'urna un foglietto che contiene le combinazioni che iniziano con l'ultima lettera scritta; dopo che la lettera è stata scritta, il pezzo di carta viene restituito all'urna, il cui contenuto viene nuovamente mescolato accuratamente. Un'esperienza del genere porta ad una "frase" come la seguente: UMARONO KACH INSERITO DA DEW NYKH TAPPETO NEDARE. Il suono di questa "frase" è molto più vicino alla lingua russa. La conoscenza delle due lettere precedenti riduce ulteriormente l'incertezza dell'esperimento consistente nel determinare la lettera successiva, che si riflette nella positività della differenza, dove è "l'entropia condizionata del secondo ordine": ciascuna delle quali contiene pezzi di carta che iniziano con le stesse due lettere (o un esperimento con un libro russo, in cui si trova a caso la prima ripetizione dell'ultima combinazione di due lettere già scritta e si scrive la lettera che segue) porta a una "frase" come la seguente : MENTRE IL SUDORE DEL NORMOSO ROCKER LA CONOSCENZA GRADUALMENTE HA CANCELLATO IL TUO OBNIL, ancora più vicino al discorso russo rispetto al precedente. Allo stesso modo, è possibile determinare l'entropia corrispondente all'esperienza di determinazione della lettera del testo russo, a condizione che le tre lettere precedenti siano note. Consiste nell'estrarre pezzi di carta da 323 urne con combinazioni di quattro lettere (oppure - un esperimento simile all'esperimento sopra descritto con un libro russo), porta ad una "frase" come la seguente: DIVERTIMENTO A GATE NON ASCIUTTO E NEPO E CORKO, Un'approssimazione ancora migliore all'entropia di un testo russo significativo è valori a N = 5,6, .... È facile vedere che con un aumento di N, l'entropia HN può solo diminuire. Se teniamo conto anche che tutti i valori di HN sono positivi, allora sarà possibile dedurne che il valore a tende ad un certo limite. Sappiamo già che il numero medio di segnali elementari necessari per trasmettere una lettera del testo russo non può essere inferiore. La differenza che mostra quanto meno dell'unità è il rapporto tra "l'entropia limitante" e il valore che caratterizza la maggior parte delle informazioni, che può essere contenuto in una lettera dell'alfabeto con un dato numero di lettere, Shannon chiamò la ridondanza della lingua. La ridondanza della lingua russa (così come la ridondanza di altre lingue europee) supera significativamente il 50%. Cioè, possiamo dire che la scelta della lettera successiva di un testo significativo è determinata per oltre il 50% dalla struttura della lingua stessa e, quindi, è casuale solo in misura relativamente piccola. La ridondanza di R è una caratteristica statistica molto importante di una lingua, ma il suo valore numerico non è stato ancora determinato con una precisione soddisfacente per nessuna lingua. In relazione alla lingua russa, in particolare, esistono solo dati sui valori delle grandezze H2 e H3. Н0Н1Н2Н3log 32 = 54.353.523.01 (per completezza abbiamo dato anche qui i valori dell'entropia Н0 e Н1). Da ciò si può solo dedurre che per la lingua russa, infatti, il valore di R è molto maggiore di questo numero. È chiaro che per tutte le lingue che utilizzano alfabeto latino, la massima informazione Н0, che potrebbe cadere su una lettera del testo, ha lo stesso significato: bit (26 lettere diverse dell'alfabeto e la 27a "lettera" è uno spazio vuoto tra le parole). Utilizzando tabelle di frequenze relative di varie lettere in inglese, tedesco, francese e spagnolo, si può dimostrare che l'entropia H1 per queste lingue è uguale (in bit): lingua tedesco francese francese spagnolo Н14.034.103.963,98 Vediamo che in tutti i casi, il valore di H1 è notevolmente inferiore a H0 = log 27 4,76 bit, e i suoi valori per lingue differenti non sono molto diversi tra loro. I valori di H2 e H3 per la lingua inglese sono stati calcolati da Shannon, mentre ha utilizzato le tabelle di frequenza disponibili in inglese per varie combinazioni di due e tre lettere. Tenendo conto anche delle statistiche sulle frequenze di occorrenza parole diverse in inglese, Shannon è stato in grado di stimare approssimativamente i valori di H5 e H8. Di conseguenza, ha ricevuto: Н0Н1 Н2Н3Н5Н84.764.03 3.323.10≈2.1≈1.9 Da ciò si può concludere che per la lingua inglese la ridondanza di R è comunque non inferiore, ovvero superiore al 60%. Contare i valori di H9, H10, ecc. secondo la formula a noi nota è impossibile, poiché il calcolo di H9 richiede la conoscenza delle probabilità di tutte le combinazioni di 9 lettere, il cui numero è espresso da una cifra di 13 numero (trilioni!). Pertanto, per stimare i valori di HN a grandi valori N deve essere limitato metodi indiretti... Soffermiamoci su uno di questo tipo di metodo proposto da Shannon. "Entropia condizionata" НN è una misura del grado di incertezza dell'esperienza, che consiste nel determinare N-esima lettera testo, a condizione che le lettere N - 1 precedenti ci siano note. Un esperimento per indovinare l'ennesima lettera può essere facilmente impostato: per questo, è sufficiente selezionare un frammento (N - 1) -alphate di un testo significativo e invitare qualcuno a indovinare la lettera successiva. Tale esperimento può essere ripetuto molte volte e la difficoltà di indovinare l'ennesima lettera può essere stimata utilizzando il valore medio QN del numero di tentativi necessari per trovare la risposta corretta. È chiaro che le quantità QN definite per significati diversi N, sono alcune caratteristiche della struttura statistica della lingua, in particolare, la sua ridondanza. Shannon eseguì una serie di esperimenti simili, in cui N assumeva i valori 1, 2, 3, ..., 14, 15 e 100. Così facendo, scoprì che indovinare la centesima lettera per 99 precedenti era un compito molto più semplice che indovinare la 15-esima lettera sulla precedente 14. Quindi, possiamo concludere che H15 è notevolmente più grande di H100, cioè che H15 non può ancora essere identificato con il valore limite. Successivamente, gli stessi esperimenti sono stati effettuati su un materiale leggermente più grande per N = 1, 2, 4, 8, 16, 32, 64, 128 e N 10.000. Н128) praticamente non differisce da Н10000, mentre l'"entropia condizionata " Н16 è anche notevolmente maggiore di questo valore. Quindi, si può presumere che con un aumento di N, il valore di HN diminuisca fino a valori di N = 30, ma con un ulteriore aumento di N, praticamente non cambia; quindi, invece di "limitare l'entropia" si può parlare, ad esempio, dell'entropia condizionata H30 o H40. Gli esperimenti sulle lettere indovinate non solo ci permettono di giudicare valore comparativo entropie condizionali HN per N diversi, ma consentono anche di isolare i valori di HN stessi. In base ai dati di tali esperimenti, è possibile determinare non solo il numero medio di tentativi QN necessari per indovinare l'ennesima lettera del testo da N - 1 precedenti, ma anche la probabilità (frequenza) che la lettera sia corretta indovinato dal 1°, 2°, 3°, ..., n-esimo tentativo (dove n = 27 è il numero di lettere dell'alfabeto; QN =). È facile intuire che le probabilità sono uguali alle probabilità delle lettere dell'alfabeto, disposte in ordine decrescente di frequenza. Infatti, se non conosciamo nessuna delle lettere che precedono la lettera x da indovinare, allora è naturale supporre innanzitutto che x coincida con la lettera più comune a1 (e la probabilità di indovinare qui sarà pari a p (a1)); allora si dovrebbe assumere che x coincida con a2 (la probabilità di una risposta corretta qui sarà pari a p (a2)), e così via. Ne segue che l'entropia di H1 è uguale alla somma. Se N> 1, allora si può dimostrare che la somma (*) non supererà l'entropia condizionale HN (ciò è dovuto al fatto che i valori rappresentano in un certo modo le probabilità medie degli esiti dell'esperimento) . D'altra parte, considerazioni un po' più complicate, sulle quali non ci soffermeremo qui, ci permettono di dimostrare che la somma (**) per ogni N non sarà maggiore dell'entropia condizionata НN. Pertanto, le espressioni (*) e (**) (composte da probabilità stimabili dai dati sperimentali) determinano i confini entro i quali dovrebbe trovarsi il valore di HN. Devi solo tenere presente che entrambe le stime (*) e (**) sono ottenute assumendo che queste siano le probabilità di indovinare una lettera da N - 1 lettere precedenti dal primo, secondo, terzo, ecc. tentativi che si ottengono partendo dal presupposto che l'indovino nomi sempre la lettera successiva nel modo più opportuno - con la piena considerazione di tutte le leggi statistiche di questa lingua... In caso di esperienze reali eventuali errori nella strategia dell'indovino (cioè le differenze tra le lettere che chiama e quelle che dovrebbero essere nominate in base alle statistiche esatte della lingua) porteranno inevitabilmente a sopravvalutare sia le somme (*) che ( **); ecco perché è consigliabile prendere in considerazione solo i dati dell'"indovino di maggior successo", poiché per lui questa sopravvalutazione sarà la più piccola. Poiché ogni persona che indovina a volte commette errori, la stima (**) in pratica non può essere considerata una stima inferiore completamente affidabile della vera entropia (in contrasto con la stima superiore (*), che, a causa degli errori dell'indovino, può solo diventare anche più grande). Inoltre i valori delle somme (*) e (**), purtroppo, non si avvicinano all'infinito all'aumentare di N (a partire da N ≈ 30, queste somme generalmente cessano di dipendere da N); pertanto, le stime della ridondanza della lingua ottenute lungo questo percorso non saranno particolarmente accurate. In particolare, gli esperimenti di Shannon hanno mostrato solo che il valore di H100 sembra essere compreso tra 0,6 e 1,3 bit. Quindi, possiamo concludere che la ridondanza per la lingua inglese in ordine di grandezza dovrebbe essere vicina all'80%. 2.2.2 Discorso orale. Passiamo ora alla questione dell'entropia e dell'informazione nel discorso orale. È naturale pensare che tutte le caratteristiche statistiche di un tale discorso dipenderanno ancor di più dalla scelta delle persone che parlano e dalla natura della loro conversazione. Il valore ridotto dell'entropia del discorso orale può essere dovuto al fatto che in una conversazione usiamo spesso più ripetizioni delle stesse parole e spesso aggiungiamo molte parole "extra" - questo viene fatto sia per facilitare la percezione del discorso , e semplicemente in modo che l'oratore abbia il tempo di considerare ciò che vuole dire dopo. Determinato il numero medio di lettere pronunciate nell'unità di tempo, si può stimare approssimativamente la quantità di informazioni comunicate durante una conversazione in 1 secondo; di solito è nell'ordine da 5 a 6 bit. Dalla conversazione, possiamo giudicare l'umore dell'oratore e il suo atteggiamento nei confronti di ciò che è stato detto; possiamo riconoscere chi parla, anche se nessun'altra fonte di informazione ce lo indica; in molti casi possiamo determinare il luogo di nascita di uno sconosciuto dalla sua pronuncia; possiamo stimare il volume del discorso orale, che nel caso della trasmissione vocale su una linea di comunicazione è in gran parte determinato puramente caratteristiche tecniche linee di trasmissione, ecc. Quantificare tutte queste informazioni è un compito molto difficile che richiede molta più conoscenza della lingua. Un'eccezione a questo riguardo è la questione relativamente ristretta degli accenti logici che enfatizzano le singole parole in una frase. L'accento più spesso cade sulle parole usate più raramente (che, tuttavia, è abbastanza naturale - è chiaro che quasi nessuno enfatizzerà l'elefante più comune con un accento logico - ad esempio preposizioni o congiunzioni). Se la probabilità che data parola Wr è sotto stress, lo indichiamo con qr, quindi l'informazione media, consistente in informazioni sulla presenza o assenza di stress su questa parola, sarà uguale.Siamo ora le probabilità (frequenze) di tutte le parole W1, W2,. ... ., WK (qui K - numero totale tutte le parole usate In questo caso, per l'informazione media H, racchiusa in un accento logico, si può scrivere la seguente formula: L'informazione media che si ottiene scoprendo su quali parole ricade l'accento logico è vicina in ordine di grandezza a 0,65 bit/parola . Durante una conversazione, le singole lettere non vengono mai pronunciate, ma vengono pronunciati suoni significativamente diversi dalle lettere. Pertanto, l'elemento principale del discorso orale dovrebbe essere considerato un suono separato: un fonema. La lingua parlata significativa è composta da fonemi nello stesso modo in cui la lingua scritta significativa è composta da lettere. Pertanto, in tutti i casi in cui siamo interessati solo alla trasmissione di "informazioni semantiche" del discorso orale maggior interesse rappresenta non l'entropia e l'informazione di una "lettera pronunciata", ma l'entropia e l'informazione di un fonema effettivamente pronunciato. L'elenco dei fonemi di una data lingua, ovviamente, non coincide con l'elenco delle lettere dell'alfabeto, poiché la stessa lettera in casi diversi potrebbe suonare diverso. Ci sono 42 diversi fonemi in russo e hanno contato le frequenze dei singoli fonemi (oltre a diverse combinazioni due e tre fonemi consecutivi). Н0 = log 42 di un fonema, entropia del primo ordine (dove sono le frequenze relative dei diversi fonemi) ed "entropia condizionata" Н2 e Н3: Н0Н1Н2Н3log 42 ≈ 5,38 4,77 3,62 0,70 Se confrontiamo questi valori con i valori di Н0 , Н1, Н2, H3 per il discorso russo scritto, quindi la diminuzione del numero di entropia condizionale per i fonemi avviene notevolmente più velocemente che nel caso delle lettere del testo scritto. Per determinare la ridondanza di R (parole), è possibile stabilire una relazione tra le ridondanza del parlato e della scrittura. Dal fatto che il discorso orale può essere registrato e scritto - letto, ne consegue che le "informazioni complete" contenute in un certo testo non dipendono dalla forma in cui - orale o scritta - questo testo è presentato, cioè quello. .. Ne consegue che dove è il numero medio di lettere per fonema ("lunghezza media del fonema"). Questo valore è un'importante caratteristica statistica della lingua che collega discorso parlato e scritto. Dall'ultima formula segue anche che o dove k è il numero totale di fonemi, ed n è il numero di lettere; perché qui è più naturale prendere. Tuttavia, l'uso di questa formula è ostacolato dalla mancanza di dati statistici per determinare il valore. 2.2.3 Musica. Ricerche dello stesso tipo possono essere effettuate per quanto riguarda i messaggi musicali. È naturale pensare che le connessioni tra suoni successivi di una certa melodia, espresse dai singoli segni di nota, siano abbastanza forti: poiché alcune combinazioni di suoni saranno più armoniche di altre, le prime si troveranno nelle opere musicali più spesso delle quest'ultimo. Se scriviamo una serie di note a caso, allora le informazioni contenute in ciascuna nota di questo record saranno le più grandi; tuttavia, da un punto di vista musicale, una sequenza di note così caotica non avrebbe alcun valore. Per ottenere un suono gradevole è necessario introdurre una certa ridondanza nella nostra gamma; allo stesso tempo, si può temere che in caso di troppa ridondanza, in cui le note successive sono quasi univocamente determinate dalle precedenti, si otterrà solo musica estremamente monotona e poco interessante. Qual è la ridondanza alla quale si può ottenere musica "buona"? Ridondanza melodie semplici niente di meno che la ridondanza del discorso significativo. Bisognerebbe studiare in modo specifico la questione della ridondanza delle varie forme opere musicali o opere di vari compositori. Ad esempio, analizza un popolare album di canzoni per bambini dal punto di vista della teoria dell'informazione. Per semplicità, questo lavoro ha supposto che tutti i suoni siano entro un'ottava; poiché nelle melodie in esame non si verificavano i cosiddetti cromatismi, tutte queste melodie potevano essere ridotte a sette suoni fondamentali; Do, re, mi, fa, sol, la e si, ciascuno ottavo di durata. La contabilizzazione dei suoni con durata superiore a un ottavo è stata effettuata aggiungendo alle sette note l'ottavo "elemento principale" O, che denota l'estensione del suono precedente per un altro periodo di tempo di un ottavo (o una pausa di un ottavo). Quindi, la "massima entropia possibile" H0 di una nota è qui uguale a H0 = log 8 = 3 bit. Dopo aver calcolato le frequenze (probabilità) delle singole note in tutte le 39 canzoni analizzate, troviamo che utilizzando le probabilità trovate di combinazioni di due note, possiamo anche calcolare l'entropia condizionale H2, risulta essere vicina a 2,42. Dai soli valori di H1 e H2, si può dire molto poco sul grado di ridondanza di quelli considerati, a quanto pare, è notevolmente superiore a. Questa conclusione è supportata dalle ricerche di molti noti autori. 2.2.4 Trasferimento immagini televisive... Il nostro occhio è in grado di distinguere solo un numero finito di gradi di luminosità di un'immagine e solo parti di essa non troppo vicine, quindi qualsiasi immagine può essere trasmessa "punto per punto", ognuno dei quali è un segnale che prende solo un numero finito di valori. È necessario tenere conto di un numero significativo (diverse decine) di gradazioni del grado di annerimento ("luminosità") di ciascun elemento, inoltre, ogni secondo sullo schermo TV vengono sostituiti 25 fotogrammi, creando l'impressione di "movimento ". Tuttavia, la linea di comunicazione in realtà non trasmette l'esito dell'esperimento, che consiste nel determinare il valore del continuo mutare da punto a punto, nel tempo, e il colore o la luminosità dell'immagine, ma l'esito di un tutt'altro” esperimento quantizzato", consistente nel determinare la luminosità del colore (bianco o nero) o delle gradazioni in un numero finito di "punti". Questa nuova esperienza può già avere solo un numero finito di esiti, e possiamo misurarne l'entropia H. Il numero totale di elementi ("punti") per la televisione in bianco e nero, in cui l'immagine dovrebbe essere scomposta, è determinato principalmente dal cosiddetto "potere risolutivo" dell'occhio, cioè la sua capacità di distinguere aree ravvicinate dell'immagine. Nella televisione moderna, questo numero è solitamente dell'ordine di diverse centinaia di migliaia (nei programmi televisivi sovietici, l'immagine si scompone in 400.000 - 500.000 elementi, in America - di circa 200.000 - 300.000, nei programmi di alcuni centri televisivi francesi e belgi - di quasi 1.000.000) ... È facile capire che per questo motivo l'entropia di un'immagine televisiva è enorme. Anche supponendo che l'occhio umano distingua solo 16 diverse gradazioni di luminosità (il valore è chiaramente sottostimato) e che l'immagine sia scomposta in soli 200.000 elementi, allora troviamo che l'"entropia di ordine zero" qui è uguale a Н0 = log 16.200.000 = 800.000 bit. Il valore della vera entropia H, ovviamente, sarà inferiore, poiché l'immagine televisiva ha una ridondanza significativa. Nel calcolare il valore di H0, abbiamo ipotizzato che i valori di luminosità in corrispondenza di due "punti" qualsiasi dell'immagine siano indipendenti l'uno dall'altro, mentre in effetti la luminosità di solito cambia molto poco quando si va a elementi vicini la stessa immagine (o anche diversa, ma ravvicinata nel tempo). Il significato visivo di questa ridondanza R è che tra le nostre 16.200.000 possibili combinazioni di valori di luminosità in tutti i punti dello schermo, combinazioni significative che possono essere chiamate "immagini" costituiranno solo una parte trascurabile, e il resto sarà completamente disordinato insieme di punti di diversa luminosità molto lontani da qualsiasi "trama". Nel frattempo, il vero "grado di incertezza" H dell'immagine televisiva dovrebbe tenere conto solo di quelle combinazioni di valori di luminosità che hanno almeno qualche possibilità di essere trasmesse. Per determinare il valore esatto dell'entropia H (o ridondanza R) di un'immagine televisiva, è necessario studiare in dettaglio le relazioni statistiche tra la luminosità dei diversi punti dello schermo. Pertanto, i valori delle entropie H0, H1, H2 e H3 sono stati trovati per due immagini televisive specifiche, la prima delle quali (immagine A - un parco con alberi ed edifici) era più complessa e la seconda (immagine B - una galleria piuttosto buia con i passanti) era più monocromatica per colore e conteneva meno dettagli, pur distinguendo 64 diverse gradazioni di luminosità di un elemento di un'immagine televisiva, quindi l'entropia H0 (riferita ad un elemento, e non all'intera immagine complessivamente) qui è risultato uguale a H0 = log 64 = 6 bit. Quindi, utilizzando un apposito dispositivo radio, sono state calcolate le frequenze relative (probabilità) di tutte le gradazioni di luminosità distinguibili per entrambe le immagini in esame e determinate "l'entropia del primo ordine" di cui il primo elemento ha un valore cioè di luminosità, e secondo j-e, così come le frequenze relative pijk di triple di elementi vicini (anche solo orizzontalmente), in cui il primo elemento aveva il valore di luminosità i-e, il secondo j-e, e terzo kth(i numeri i, j e k hanno attraversato tutti i valori da 1 a 64). Queste frequenze hanno permesso di determinare le "entropie di esperimenti complessi" e quindi le "entropie condizionali" e quest'ultima in cui però è stata calcolata solo per l'immagine B. I risultati ottenuti sono riassunti nella seguente tabella: , 91.5 Ridondanza R, stimato dal valore di H2 per l'immagine A è del 44% e per l'immagine B - 68%; valore attuale ci può essere solo più ridondanza di così. Quanto all'entropia condizionale H3 per la luminosità nota dei due elementi precedenti della stessa linea, essa differisce relativamente poco da H2 (immagine B, 75%); da ciò si può concludere che la conoscenza della luminosità dell'elemento più vicino determina una parte molto ampia della ridondanza totale. Un'altra esperienza che si basa sulla scissione ha anch'essa un carattere simile. valori possibili la luminosità di un elemento dell'immagine televisiva di 8, non 64 gradazioni, per cui vengono calcolate le entropie H0 e H1 e un numero di entropie condizionali H2, H3 e H4 di un elemento dell'immagine per i seguenti quattro grafici televisivi sportivi: A - corsa veloce giocatori di basket, B - il volto di uno spettatore in primo piano sulla tribuna dello stadio, C - panoramica della vista degli spettatori sullo stand e D - calciatori veloci. Indicheremo con i numeri 1 e 2 gli elementi dell'immagine adiacenti ai dati orizzontalmente e verticalmente, con il numero 3 - l'elemento diagonalmente adiacente, con il numero 4 - uguale a quello in esame, l'elemento sul frame precedente di la trasmissione televisiva, con il numero 5 - l'elemento sullo stesso piano orizzontale, adiacente all'elemento 1, e, infine, il numero 6 - lo stesso elemento sul frame che precede quello che contiene l'elemento 4 (Fig. 1), a) b ) Fig. 1.e indicheremo nella notazione delle entropie condizionali dall'alto tra parentesi il numero di elementi immagini, il cui grado di luminosità è considerato noto. In questo caso i valori dell'entropia (in bit) possono essere riassunti nella seguente tabella: A31,960,690,98-1,77B31,950,360,36 - B32,781,341,952,78-G32,45-2,002,08 A0.68-0 , 56 - B0.35-0.270.26-B - 1.221.181.19G-1.83 --- I risultati dell'ultimo esperimento portano a concludere che per l'immagine povera di dettagli ("faccia") la ridondanza non è inferiore a 90%, e per un'immagine ricca di dettagli ("spettatori") non è inferiore al 60%. Le ragioni di questa discrepanza non sono ancora chiare. Per le immagini televisive a colori, l'informazione è in ordine di grandezza paragonabile all'informazione raddoppiata contenuta nella corrispondente immagine in bianco e nero. CONCLUSIONE In questo lavoro, sono stati fissati i seguenti obiettivi e traguardi. Scopo: studiare i principi della codifica delle informazioni di Shannon - Fano e Huffman e la loro applicazione nella risoluzione dei problemi. Obiettivo: studiare l'entropia e la ridondanza di specifiche tipologie di messaggi per la successiva applicazione ad essi dei principi di Shannon - Fano e Huffman. Dopo aver completato gli obiettivi e gli obiettivi tesi sono state tratte le seguenti conclusioni. Prima della comparsa delle opere di Shannon e Fano, la codifica dei caratteri dell'alfabeto durante la trasmissione di un messaggio sui canali di comunicazione veniva eseguita con lo stesso numero di bit, ottenuto dalla formula di Hartley. Con l'avvento di questi lavori, iniziarono ad apparire metodi che codificano i caratteri con un numero diverso di bit, a seconda della probabilità della loro comparsa nel testo, ovvero i caratteri più probabili vengono codificati con codici brevi e i caratteri rari vengono codificati con quelli lunghi (più lunghi della media). Da quando D.A. Huffman ha pubblicato il suo lavoro "Metodo per la costruzione di codici con ridondanza minima" nel 1952, il suo algoritmo di codifica è diventato la base per enorme quantità ulteriori ricerche in questo campo. Vale la pena notare che a oltre 50 anni dalla data di pubblicazione, il codice di Huffman non ha perso affatto rilevanza e significato. Quindi possiamo dire con sicurezza che ci troviamo di fronte, in una forma o nell'altra (il fatto è che il codice di Huffman viene usato raramente separatamente, più spesso lavorando in combinazione con altri algoritmi), quasi ogni volta che archiviamo file, guardiamo foto , film , invio di fax o ascolto di musica. I vantaggi di questi metodi sono la loro ovvia facilità di attuazione e, di conseguenza, ad alta velocità codifica e decodifica. Lo svantaggio principale è che non sono ottimali nel caso generale. 3
Considera l'algoritmo per il calcolo dei codici Shannon-Fano (per chiarezza, prendiamo la sequenza "aa bbb cccc ddddd" come esempio). Per calcolare i codici è necessario creare una tabella di simboli messaggio univoci c (io) e le loro probabilità p (c (i)) e ordinarlo in ordine di probabilità del simbolo non crescente.
| c (io) | p (c (i)) |
| D | 5 / 17 |
| C | 4 / 17 |
| spazio | 3 / 17 |
| B | 3 / 17 |
| un | 2 / 17 |
Inoltre, la tabella dei simboli è divisa in due gruppi in modo che ciascuno dei gruppi abbia approssimativamente la stessa frequenza nella somma dei simboli. Il primo gruppo è impostato all'inizio del codice a "0", il secondo a "1". Per calcolare i successivi bit dei codici carattere, questa procedura viene ripetuta in modo ricorsivo per ogni gruppo che contiene più di un carattere. Quindi, per il nostro caso, otteniamo i seguenti codici carattere:
Lunghezza del codice s (io) nella tabella risultante è int (-lg p (c (i))), se i sivol potessero essere divisi in gruppi con la stessa frequenza in caso contrario, la lunghezza del codice è int (-lg p (c (i))) + 1.
39 bit di lunghezza. Considerando che l'originale era lungo 136 bit, otteniamo un rapporto di compressione di ~ 28% - non così male.
Guardando la sequenza risultante, sorge la domanda: "Come puoi decomprimere questo ora?" Non possiamo, come nel caso della codifica, sostituire ogni 8 bit del flusso di input con un codice a lunghezza variabile. Durante la decompressione, dobbiamo fare il contrario: sostituire il codice a lunghezza variabile con un carattere a 8 bit. V in questo caso, sarebbe meglio usare un albero binario, le cui foglie saranno simboli (analogo all'albero di Huffman).
La codifica Shannon-Fano è un metodo di compressione abbastanza antico, e oggi non riveste particolare interesse pratico (se non come esercizio nel corso delle strutture dati). Nella maggior parte dei casi, la lunghezza della sequenza compressa, secondo questo metodo, è uguale alla lunghezza della sequenza compressa utilizzando la codifica di Huffman. Ma su alcune sequenze si formano ancora codici Shannon-Fano non ottimali, quindi la compressione con il metodo di Huffman è considerata più efficiente. Ad esempio, considera una sequenza con il seguente contenuto di caratteri: "a" - 14, "b" - 7, "c" - 5, "d" - 5, "e" - 4. Il metodo Huffman la comprime a 77 bit , ma Shannon-Fano fino a 79 bit.
|
Come ci siamo divisi in gruppi? Abbastanza semplice:
A causa di questa ambiguità, alcune persone hanno persino pensieri del genere: "... il programma a volte assegna alcuni simboli ..." e così via - ragionando sulla lunghezza dei codici. Se non stai scrivendo AI, una cosa come "il programma a volte" fa qualcosa di ridicolo. Un algoritmo correttamente implementato funziona rigorosamente.
Lo stesso messaggio può essere codificato diversi modi... Il codice più vantaggioso è quello che impiega il minor tempo nella trasmissione dei messaggi. Se la trasmissione di ogni elemento del carattere (ad esempio, 0 o 1) richiede lo stesso tempo, il codice ottimale sarà tale che quando viene utilizzato per trasmettere un messaggio data lunghezza verrà speso il numero minimo di caratteri elementari. I codici Shannon - Fano sono prefissi, ad es. no parola in codice non è un prefisso di nessun altro. Questa proprietà consente la decodifica univoca di qualsiasi sequenza di parole in codice
Consideriamo il principio di costruzione di uno dei primi algoritmi di compressione, che è stato formulato dagli scienziati americani Shannon e Fano usando l'esempio delle lettere dell'alfabeto russo. L'algoritmo utilizza codici di lunghezza variabile, ad es. un carattere comune è codificato con un codice di lunghezza più corta, uno raro - un codice più lungo.
Per comporre un tale codice, ovviamente, è necessario conoscere la frequenza di occorrenza delle lettere nel testo russo. Queste frequenze sono mostrate nella tabella 1. Le lettere nella tabella sono disposte in ordine decrescente di frequenza.
Tabella 1
Frequenza di comparsa delle lettere dell'alfabeto russo
Utilizzando la tabella è possibile comporre il codice più economico in base a considerazioni relative alle informazioni. Ovviamente, il codice sarà più economico quando trasmetterà ogni carattere elementare massima informazione... Considera un simbolo elementare (cioè, che rappresenta il suo segnale) come sistema fisico con due possibili stati: 0 e 1. L'informazione che questo simbolo fornisce è pari all'entropia di questo sistema ed è massima nel caso in cui entrambi gli stati siano ugualmente probabili; in questo caso il simbolo elementare veicola l'informazione 1 (binaria). Pertanto, la base per una codifica ottimale sarà il requisito che i caratteri elementari nel testo codificato si presentino in media con la stessa frequenza.
L'idea della codifica è che i caratteri codificati (lettere o combinazioni di lettere) siano divisi in due gruppi approssimativamente ugualmente probabili: per il primo gruppo di caratteri, il primo posto della combinazione è 0 (il primo carattere del numero binario che rappresenta il personaggio); per il secondo gruppo - 1. Inoltre, ogni gruppo è nuovamente diviso in due sottogruppi approssimativamente ugualmente probabili; per i simboli del primo sottogruppo si mette 0 al secondo posto; per il secondo sottogruppo - uno, ecc.
Dimostriamo il principio della costruzione del codice Shannon-Fano usando l'esempio del materiale dell'alfabeto russo (vedi Tabella 1). Contiamo le prime sei lettere (da "-" a "t"); sommando le loro probabilità (frequenze), si ottiene 0,498; tutte le altre lettere da "n" a "f" avranno approssimativamente la stessa probabilità di 0,502. Le prime sei lettere (da "-" a "t") avranno in primo luogo il segno binario 0. Le restanti lettere (da "n" a "f") avranno in primo luogo 1. Inoltre, divideremo ancora il primo gruppo in due sottogruppi approssimativamente ugualmente probabili: da "-" a "o" e da "e" a "t"; per tutte le lettere del primo sottogruppo al secondo posto mettiamo zero e il secondo sottogruppo - uno. Continueremo il processo finché non ci sarà esattamente una lettera in ogni suddivisione, che sarà codificata in un certo numero binario... Il meccanismo di costruzione è mostrato nella tabella 2 e il codice stesso è mostrato nella tabella 3.
Tavolo 2
Il meccanismo per costruire il codice Shannon - Fano sull'esempio dell'alfabeto russo
| Segni binari | |||||||||
| Lettere | 1° | 2° | 3° | 4° | 5° | 6° | 7° | 8° | 9° |
| - | |||||||||
| oh | |||||||||
| e | |||||||||
| un | |||||||||
| e | |||||||||
| T | |||||||||
| n | |||||||||
| Con | |||||||||
| R | |||||||||
| v | |||||||||
| io | |||||||||
| a | |||||||||
| m | |||||||||
| D | |||||||||
| P | |||||||||
| in | |||||||||
| io sono | |||||||||
| S | |||||||||
| S | |||||||||
| b, b | |||||||||
| B | |||||||||
| G | |||||||||
| h | |||||||||
| questo | |||||||||
| X | |||||||||
| F | |||||||||
| Yu | |||||||||
| w | |||||||||
| C | |||||||||
| SCH | |||||||||
| eh | |||||||||
| F |
Tabella 3
Il risultato della codifica delle lettere dell'alfabeto russo con il codice Shannon - Fano
Esempio 4. Scriviamo la frase "metodo di codifica" utilizzando il codice Shannon - Fano.
Soluzione: Usiamo la tabella 3 e otteniamo il seguente risultato:
(1001) s (110011) n (001) o (1001) s (001) o (111010) b (000) spazio
(10111) a (001) o (110010) d (0110) e (10100) r (001) o (10101) c
(0101) a (1000) n (0110) e (110110) i
Si noti che non è necessario separare le lettere l'una dall'altra con un carattere speciale, poiché anche senza questa decodifica viene eseguita in modo univoco a causa della proprietà del prefisso: nessuna parola di codice più corta è l'inizio di una parola di codice più lunga. Infatti, la tabella 3 mostra che i più brevi sono i codici per i caratteri "spazio" e "o". Inoltre, non un altro di più codice lungo non ha 000 ("spazio") e 001 ("o") all'inizio della sequenza. Lo stesso si può osservare per tutte le altre sequenze binarie del codice Shannon - Fano, che sono mostrate nella Tabella 3.
Va notato che qualsiasi errore di codifica (commutazione accidentale di 0 o 1 caratteri) con tale codice è fatale, poiché la decodifica dell'intero testo successivo all'errore diventa impossibile.
Esempio 5. Determinare se il codice che abbiamo considerato è ottimale in assenza di errori?
Soluzione: Troviamo l'informazione media per un simbolo elementare (0 o 1) e confrontiamola con il massimo informazioni possibili, che è uguale a uno. Per fare ciò, troviamo prima l'informazione media contenuta in una lettera del testo trasmesso, cioè l'entropia per lettera (vedi formula 8):
Secondo la tabella 1, determiniamo il numero medio di caratteri elementari per lettera:
Pertanto, l'informazione per carattere è molto vicina al suo limite superiore di uno, e codice dato molto vicino all'ottimale.
In caso di utilizzo di un codice binario a cinque bit, informazioni per carattere:
Esempio 6. Lascia che un messaggio (una parola in russo) venga ricevuto tramite il canale di comunicazione codificato con il codice Shannon-Fano: 10111001110010010010100.
È necessario decodificare la sequenza data.
Soluzione: Il processo di decodifica si basa sulla proprietà del prefisso del codice e viene eseguito da sinistra a destra. La tabella 3 mostra che la lunghezza minima del codice è di tre bit. Conterà tre bit dall'inizio della parola di codice ricevuta, otteniamo - 101. Non c'è tale codice nella tabella, quindi aggiungiamo un altro bit, otteniamo - 1011. Anche questo codice non è nella tabella, quindi, è necessario aggiungere un altro bit, otteniamo la combinazione - 10111, che corrisponde alla lettera "k". La codeword 10111 è esclusa dalla codeword ricevuta e viene sostituita dal simbolo originale (lettera "k"). Il processo di decodifica del resto delle lettere messaggio ricevuto si svolge in modo analogo.
Il processo di decodifica completo è mostrato nella Tabella 4. Il segno “-” nella tabella significa che il codice selezionato è assente nella Tabella 3.
Tabella 4
Processo di decodifica dei messaggi
| Sequenza codice ricevuta | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| a | ||||||||||||||||||||||
| a | oh | |||||||||||||||||||||
| a | oh | - | ||||||||||||||||||||
| a | oh | - | ||||||||||||||||||||
| a | oh | - | ||||||||||||||||||||
| a | oh | D | ||||||||||||||||||||
| a | oh | D | - | |||||||||||||||||||
| a | oh | D | e | |||||||||||||||||||
| a | oh | D | e | - | ||||||||||||||||||
| a | oh | D | e | - | ||||||||||||||||||
| a | oh | D | e | R |
Quindi, la parola ottenuta come risultato della decodifica della parola in codice ricevuta è "codificatore".
Codifica ottimale
Il teorema dei codici di Shannon. Metodi di codifica ottimale lettera per lettera. Criteri di ottimalità del codice. Codifica a blocchi. un sistema codifica delle informazioni di testo.
codifica,minimizzazione della ridondanza del codice,si chiama ottimale.
La questione dell'esistenza di tali codici è l'essenza di uno dei principali teoremi della teoria dell'informazione: il teorema della codifica dimostrato da K. Shannon. Ecco una delle formulazioni equivalenti di questo teorema.
teorema di codifica. Messaggi di una fonte di informazione arbitraria Z con entropia H(Z)può essere sempre codificato con sequenze dell'alfabeto B,composto da M caratteri,Così,che la lunghezza media del codice sarà arbitrariamente vicina al valore 
,ma non meno di lei.
A causa della sua complessità, la dimostrazione di questo teorema non viene considerata.
Il teorema afferma che la differenza può essere resa arbitrariamente piccola. Questo è il compito dei metodi di codifica ottimali.
Torniamo alla considerazione di una fonte di informazioni alfabetica che genera messaggi in caratteri alfabetici UN... Poiché la ridondanza del codice è data dalla formula
è ovvio che meno è ottimale il codice. Per diminuire i caratteri ricorrenti dovrebbero essere codificati con parole più brevi e viceversa. Tutti i metodi di codifica ottimali si basano su questo requisito. Inoltre, per garantire la decodifica di un codice irregolare, è importante osservare principio del prefisso: Nessun codice deve essere l'inizio di un altro codice.
Ecco due dei metodi più noti per la codifica ottimale lettera per lettera. Per semplicità, prendiamo alfabeto binario come codice.
Passaggio 1. Disponiamo i simboli dell'alfabeto originale nell'ordine di non aumento delle loro probabilità. (Li scriviamo su una stringa.)
Passaggio 2. Senza modificare l'ordine dei simboli, li dividiamo in due gruppi in modo che le probabilità totali dei simboli nei gruppi siano il più uguali possibile.
Passaggio 3. Assegniamo al gruppo a sinistra "0" e al gruppo a destra "1" come elementi dei loro codici.
Passaggio 4. Sfoglia i gruppi. Se il numero di elementi nel gruppo è più di uno, vai al passaggio 2. Se c'è un elemento nel gruppo, la creazione del codice è completa.
Riso. 4.1. albero binario corrispondente alla codifica Shannon - Fano
Considera l'operazione dell'algoritmo descritto usando l'esempio della codifica dell'alfabeto 
, i cui simboli si presentano con probabilità (0,25; 0,05; 0,25; 0,1; 0,25; 0,1), rispettivamente. Il risultato della codifica è mostrato in Fig. 4.1.
È ovvio che il processo di costruzione del codice nel caso generale contiene ambiguità, poiché non possiamo sempre dividere la sequenza in due sottoinsiemi ugualmente probabili. Sia a sinistra che a destra, la somma delle probabilità sarà maggiore. Il criterio migliore è una minore ridondanza del codice. Si noti inoltre che la corretta lettura del codice - dalla radice dell'albero al simbolo - farà sì che sia prefissato.
